Is there a rigorous proof that AGI is possible, at least, in theory? It is often implicitly assumed in computer science that the human mind, or at least some mechanical calculations that humans perform (see the Church-Turing thesis), can be replicated with a Turing machine, therefore Artificial General Intelligence (AGI), defined as a human-like AI, may be possible.
I do not know of any other argument that AGI is possible, and the foregoing argument is extremely weak.
Is there a rigorous proof that AGI is possible, at least, in theory? How do we know that everything the human mind can do can be encoded as a program?

A strong reason why people think the mind can be implemented on a Turing Machine stems from the Computational Theory of Mind (CTOM), which is the leading theory of mind for now.
There are lots of reasons for supporting the CTOM, one of which being that the language of belief/desire psychology (propositional attitudes over mental representations) seems to fit nicely to a computational framework.
But most simply is that the computation analogy is very helpful in fields such as psychology and neuroscience. When we know of an input/output pair, but don't know how it is implemented, we could say "its performing the relevant computation".
And since Turing showed that any computation can be performed on an appropriate Turing Machine, the natural extension is that the mind can be implemented on a computer.
However, the CTOM is more of a useful idea than a complete theory. We still don't know how to analyze thought in a logical syntax, which can be implemented in a computer. And we also don't know how/why "computation" (whatever that means in this sentence) is performed in the brain.


What is the difference between a feed-forward neural network and a liquid state machine? I have used a FFNN and LSM to perform the same task, namely, to predict the sentence "How are you". The LSM gave me more accurate results than FFNN. However, the LSM did not produce perfect prediction and there are missing letters. More specifically, LSM produced "Hw are yo" and the FFNN predicted "Hnw brf ypu".

What is the difference between a FFNN and a LSM, in terms of architecture and purpose?

Liquid State Machines are used in the field of Neuroscience. What you have used is a variant of LSM called Echo State Network (ESN) used in the field of Machine Learning.

ESN's are pretty simple and superfast compared to normal ML paradigms like Feed Forward NN's or RNN's. ESN's are based on a relatively new paradigm called Reservoir Computing. ESN's are mainly used in Sequential ML problems, and it is used to overcome the problems RNN face like vanisihing gradient, exploding gradient, long training times, etc. The basic idea is that you have a reservoir of Neurons (basically a Neural Net with fixed and non-trainable weights, but it can be varied to complex structures) which will echo an input into some form based on which a simple Linear Regression model (or maybe a complex NN) will be trained.

The basic idea of an ESN is very simple, note it works on time series data and the conventions are similar to a RNN:

Just like RNN you have a hidden state $x(n)$ and an input $u(n)$ and some randomly initialized non-trainable weights are assigned to them (the weights with which you dot product these 2 terms).
$$a(n) = W_{in}[1:u(n)] + W[x(n-1)]$$
The next $x(n)$ is produced as some linear function of non-linear transformation of $x(n-1)$ and $u(n)$ multiplied by their respective weights and $x(n-1)$.
$$\tilde x(n) = tanh(a(n))$$
$$ x(n) = (1-\alpha).x(n-1) + \alpha\tilde x(n)$$
The prediction target $y(n)$ is done simply by multiplying $x(n)$ and $u(n)$ with $W_{out}$ which are trainable and the only trainable weights.
$$y(n) = W_{out}[1:u(n):x(n)]$$
Now you apply a suitable Loss Function on your predicted $y(n)$ vs actual target $t(n)$ to train weights $W_{out}$

($:$ means concatenation and follows the usual RNN concatenation rules)

This is a very simple overview of ESN's and it works surprisingly well for Sequential prediction tasks. The main idea and intuition behind the working is that the inputs are echoed in the reservoir of untrainable weights which basically means that the input is converted into a certain 'form' due to the random initialisation of weights and this 'form' trains the $W_{out}$ (the first few training $u(n)$ are run through the network without training for the network to assume a starting state where the input has already been echoed in the network and is now coming finally coming out). There are a few mathematical details for the ESN to train and not blow up by huge oscillations and can be found here in this simple intuitive tutorial.

In terms of difference of purpose, a few are:

Provides superfast training times.
Works on Sequential data mainly.
It is being used as a side network to initialise RNN weights which apparently improves the performance.

Although these networks have some very hard to tune hyperparameters, owing to its simple and superfast training one can easily check a lot of hyperparameters. The network also performs surprisingly well and it has resulted in Reservoir Computing being actually researched very actively. Check this very old question too.


Understanding GLIE conditions for epsilon greedy approach I was going through this course on reinforcement learning (the course has two lecture videos and corresponding slides) and I had a doubt. On slide 18 of this pdf, it states following condition for an algorithm to have regret sublinear in T (T being number of pulls of multi arm bandit).

C2 - Greedy in the Limit: Let exploit(T) denote the number of pulls that are that are greedy w.r.t the empirical mean up to horizon $T$. For sub-linear regret, we need
$$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[exploit(T)]}{T}=1 $$

Here, $exploit(T)$ denote the total number of "exploit" rounds performed in the first $T$ pulls. Given that expectation is defined as "the weighted sum of the outcome values, where the weights correspond to the probabilities of realizing that value",
(Q1) how exactly mathematically we define $\mathbb{E}[exploit(T)]$?
In second video (at 24:44), instructor has said that $\mathbb{E}[exploit(T)]$ is the number of exploit steps.
(Q2) Then how it equals "weighted sum of outcome values"?
(note that instructor assumes that the pulling of arm may give reward which correspond to outcome value of 1 and may not give reward which correspond to ourcome value of 0)
Also in slide 27, for GLIE-ifying $\epsilon_T$-first strategy, he selects $\epsilon_T=\frac{1}{\sqrt{T}}$. Then, the instructor counts $\sqrt{T}$ exploratory pulls and $T-\sqrt{T}$ exploitory pulls. Then to show that this satisfies condition C2, instructor states $$\mathbb{E}[exploit(T)]\geq \frac{T-\sqrt{T}}{T}$$.
Here, $\frac{T-\sqrt{T}}{T}$ is a fraction of exploitory pulls.
(Q3) So, by above equation does the instructor mean, number of exploitory pulls is greater than equal to fraction of number of exploitory pulls?
(Q4) How can we put 2nd equation in first equation and still prove limit in first equation still holds, that is, how following is the case:
$$\lim_{T=\rightarrow\infty}\frac{\frac{T-\sqrt{T}}{T}}{T}=1$$
I guess I am missing some basic concept of expectation here.

For (Q1) we mathematically define $\mathbb{E}[exploit(T)]$ as:
$$\mathbb{E}[exploit(T)] = \sum_{t=1}^T (1-\epsilon_t)$$
where $\epsilon_t$ is the exploration probability at round $t$.
The equation is basically telling us the expected number of times you pull a greedy arm over the time horizon $T$.
A more useful metric would be:
$$\mathbb{E}[explore(T)] = \sum_{t=1}^T \epsilon_t$$
It os obvious that:
$$\mathbb{E}[explore(T)] + \mathbb{E}[exploit(T)] = T$$
First, I would like to gloss over the idea why this formulation produces sublinear regret. Although there are additional assumptions that have clearly not been mentioned in the lecture, I will say it here. There is a paradigm of a 'consistent' algorithm in online learning, which in simple terms mean that the actual best arm will be identified eventually as $T \to \infty$ and by the design of your algorithm, you will be pulling this arm greedily (or with a high probability) after some time giving you a regret better than linear regret.
Now in this case, if you assume the algorithm is 'consistent' it is clear that the number of exploration steps (which is decided by exploration probability) at each step will slowly have a reduced growth as compared to the linear case i.e you are now slowly reducing exploration as your 'consistent' algorithm gurantees you have with high probability identified the best arm. From this definition/intuition given above it is clear that this means that $\mathbb{E}[explore(T)]$ should grow at a slower rate while $\mathbb{E}[exploit(T)]$ should grow at a faster rate with $T$.
From this inutitive idea rises that:
$$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[exploit(T)]}{T}=1 $$
or
$$\lim_{T\rightarrow\infty}\frac{\mathbb{E}[explore(T)]}{T}=0 $$
For (Q2), it is not. It might be in expectation, but in general, it is not. I am unsure of the type of bandits used here so I will not do this calculation. In anyways, whenever sampling is involved, it means you have sampled a trajectory or a particular instance of a joint probability distribution and its expectation can never be equal to one sample (we need $\infty$ samples).(Although I am not clear on this one, the slides are not very clear to me).
For (Q3) Yes. The instructor states an inequality which I could not reproduce (I tried to do it, but it reverses the inequality sign of the instructor, you can try it yourself using the below set of equations and using the fact that $\epsilon_T \leq \epsilon_t, \quad \forall T \geq t$). Now consider the following set of equations:
$$\mathbb{E}[explore(T)] = \sum_{t=1}^T \epsilon_t$$
(a good approximate summation can be found using integrals like this)
$$\mathbb{E}[explore(T)] \approx k \sqrt T$$
where $k$ is a constant.
$$-\mathbb{E}[explore(T)] \approx -k \sqrt T$$
$$T-\mathbb{E}[explore(T)] \approx T - k \sqrt T$$
$$\frac{\mathbb{E}[exploit(T)]}{T} \approx 1-k \frac{1}{\sqrt T}$$
which answers your (Q4) that:
$$\lim_{T \to \infty} \frac{\mathbb{E}[exploit(T)]}{T} \approx \lim_{T \to \infty} 1-k \frac{1}{\sqrt T} = 1$$


In the Markov chain, how are the directions to each successive state defined? I'm watching the David Silver series on YT which has raised a couple of questions:

In the Markov process (or chain), how are the directions to each successive state defined? For example, how are the arrow directions defined for the MP below? What's stopping our sample episodes from choosing A -> C -> D -> F?

Also, how is the probability transition matrix populated? From David's example, the probabilities seem to have already been set. For example:

It's not possible, as in the chain illustrated there are no transitions between A and C, C and D, and D and F. Only sequences where transitions exist are possible. The choice of transitions is arbitrary; it depends on what you want to model with it.

As DuttaA says in his comment, you can imagine that all nodes are linked with all other nodes, but those links have a transition probability of 0.0; so the probability of observing the sequence ACDF is actually 0.0 as well. In order to make the diagram more easy to understand, zero-probability transitions are generally not shown.

There is no prescribed method of populating the transition probabilities. You can define the probabilities manually, randomly, or however you like. You could derive them from observable training data.

Re updating: this depends on the application. If you are modelling a process with known probabilities, you would not update the probabilities; if you are modelling a dynamic process which changes over time, then this is something you might want to consider. However, from my own experience (HMMs in speech recognition), once they have been assigned, they are generally kept as they are.

A Markov chain is really a fairly basic model; it gets more complex with a Hidden Markov Model, where you would generally use a learning algorithm to assign the transition and emission probabilities.


XOR-solving neural network is suffering from local minima import torch
import torch.nn as nn
import torch.optim as optim
from torch.autograd import Variable
import matplotlib.pyplot as plt
import numpy as np
x_data = torch.tensor([[0, 0], [0, 1], [1, 0], [1, 1]]).float()
y_data = torch.tensor([0, 1, 1, 0]).float()

class Model(nn.Module):
    def __init__(self, input_size, H1, output_size):
        super().__init__()
        self.linear_input = nn.Linear(input_size, 2)
        self.linear_output = nn.Linear(2, output_size)
        self.sigmoid = torch.nn.Sigmoid()

    def forward(self, x):
        x = self.sigmoid(self.linear_input(x))
        x = self.sigmoid(self.linear_output(x))
        return x

    def predict(self, x):
        return (self.forward(x) >= 0.5).float()

model = Model(2,2,1)
lossfunc = nn.BCELoss()
optimizer = optim.Adam(model.parameters(), lr=0.01)
epochs = 2000
losses = []

for i in range(epochs):
    pred = model(x_data).view(-1)
    loss = lossfunc(pred, y_data)
    print("epochs:", i, "loss:", loss.item())
    losses.append(loss.item())
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

def cal_score(X, y):
    y_pred = model.predict(X)
    score = float(torch.sum(y_pred.squeeze(-1) == y.byte().float())) / y.shape[0]
    return score

print('test score :', cal_score(x_data, y_data))
def plot_decision_boundray(X):
    x_span = np.linspace(min(X[:, 0]), max(X[:, 0]))
    y_span = np.linspace(min(X[:, 1]), max(X[:, 1]))
    xx, yy = np.meshgrid(x_span, y_span)
    grid = torch.tensor(np.c_[xx.ravel(), yy.ravel()]).float()
    pred_func = model.forward(grid)
    z = pred_func.view(xx.shape).detach().numpy()
    plt.contourf(xx, yy, z)
    plt.show()

plot_decision_boundray(x_data)

As you can see, it's a simple neural network which consists of one hidden layer using BCELoss and Adam.

Normally, it results in the correct one like above.

However, it is sometimes stuck in a local minima and a decision boundary becomes awkward.

Because the input data is limited, I guess that preprocessing of those data might not be possible and only initial weights matter in this problem. I tried initializing them with normal distribution but it didn't work. How can I approach this problem?

From the log you can see that the loss value is still big compared to the first image, but at least it decrease on each iteration (even very very small). So I suggest you to:

try to use bigger learning rate, I think you model is underfiting.
try to use another weight initialization method

I think the first solution will solve this problem as I see no problem in the code.


Why do non-linear activation functions not require a specific non-linear relation between its inputs and outputs? A linear activation function (or none at all) should only be used when the relation between input and output is linear. Why doesn't the same rule apply for other activation functions? For example, why doesn't sigmoid only work when the relation between input and output is "of sigmoid shape"?

It is correct to say that a sigmoid activation function would only work well as a model if the desired output is close to the sigmoid function applied to the input.  This is a trivial fact that applies to a single layer perceptron.  This is true for for the single layer case for any activation function, also a trivial fact.

When the layer number is between one and infinity (two or more), the theory bifurcates.  The identity function becomes a special case:  Any number of layers that conform to a first degree polynomial, $ax + b$, can be replaced with a single identity layers.  The alternative case, where there are multiple layers that functionally do not conform to a first degree polynomial, $ax + b$, cannot be replaced by a single layer of some equally simple function.  The complexity increases geometrically, which is the entire point of multilayer perceptrons.

Under particular constraints, the multilayer perceptron can produce a wide variety of functional behaviors that do not resemble the activation functions of the layers.

For instance, a properly trained network using sigmoid activation functions, with sufficient layer depth and sufficient massive allocation of computing resources, could theoretically approximate the topography of the Himalayas.


Input/output encoding for a neural network to learn a grid-based game I am writing a simple toy game with the intent of training a deep neural network on top of it. The games rules are roughly the following:

The game has a board made up of hexagonal cells.
Both players have the same collection of pieces that they can choose to position freely on the board.
Placing different types of pieces award points (or decrease opponent's points) depending on their position and configuration wrt one another.
Whoever has more points win.

There are additional rules (about turns, number and types of pieces, etc...) but they are not important in the context of this question. I want to devise a deep neural network that can iteratively learn by playing against itself. My questions are about representation of input and output. In particular:

Since pattern of pieces matter, I was thinking to have at least some convolutional layers. The board can be of various size but in principle very small (6x10 on my tests, to be expanded by few cells). Does it make sense? What kind of pooling can I use?
How to represent both sides? In this paper about go, authors use two input matrices, one for white stones and one for black stones. Can it work in this case too? But remember I have different types of pieces, say A, B, C and D. Should I use 2x4 input matrices? It seem very sparse and of little efficiency to me. I fear it will be way too sparse for the convolutional layers to work.
I thought that the output could be a distribution of probabilities over the matrix representing board positions, plus a separate array of probabilities indicating what piece to play. However, I also need to represent the ability to pass the turn, which is very important. How can I do it without diluting its significance among other probabilities?
And most importantly, do I enforce winning moves only or losing moves too? Enforcing winning moves is easy because I just set desired probabilities to 1. However when losing, what can I do? Set that move probability to 0 and all the others to the same value? Also, does it make sense to enforce moves by the final score difference, even though this would go against the meaning of the outputs, which are roughly probabilities?

Also, I developed the game engine in node.js thinking to use Synaptic as framework, but I am not sure it can work with convolutional networks (I doubt there's a way to fix the weights associated to local perceptive fields). Any advice on other libraries that are compatible with node?

To represent the pieces, you should be able to use a single input matrix. Just designate an integer number for the different types of pieces. White stones can be positive integers and black stones can be negative.
You can use sigmoid for board position confidence and linear activation for piece identifier. pass would be another sigmoid output. I don't think you'll have to worry about pass being diluted. Since it is such a valuable action, the score will depend a lot on the pass output and it will have a large gradient. If you need to select the pass action with high frequency for reinforcement learning purposes, then just attribute a higher probability to the pass action in your random choice function.
The final score difference has a large impact on the desirability of the moves. A large score difference should result in a large impact on the function. Therefore you might want to include the magnitude of score difference in your loss function.

This is the type of job that Deep Q Learning does. Perhaps you'll want to look into that too.


What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation? I came across this 2 algorithms but I cannot understand the difference between these  2 both in terms of implementation as well as intuitionally.
So what difference does the second point in both the slides referring to?

The first-visit and the every-visit Monte-Carlo (MC) algorithms are both used to solve the prediction problem (or, also called, "evaluation problem"), that is, the problem of estimating the value function associated with a given (as input to the algorithms) fixed (that is, it does not change during the execution of the algorithm) policy, denoted by $\pi$. In general, even if we are given the policy $\pi$, we are not necessarily able to find the exact corresponding value function, so these two algorithms are used to estimate the value function associated with $\pi$.

Intuitively, we care about the value function associated with $\pi$ because we might want or need to know "how good it is to be in a certain state", if the agent behaves in the environment according to the policy $\pi$.

For simplicity, assume that the value function is the state value function (but it could also be e.g. the state-action value function), denoted by $v_\pi(s)$, where $v_\pi(s)$ is the expected return (or, in other words, expected cumulative future discounted reward), starting from state $s$ (at some time step $t$) and then following (after time step $t$) the given policy $\pi$. Formally, $v_\pi(s) = \mathbb{E}_\pi [ G_t \mid S_t = s ]$, where $G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$ is the return (after time step $t$).

In the case of MC algorithms, $G_t$ is often defined as $\sum_{k=0}^T  R_{t+k+1}$, where $T \in \mathbb{N}^+$ is the last time step of the episode, that is, the sum goes up to the final time step of the episode, $T$. This is because MC algorithms, in this context, often assume that the problem can be naturally split into episodes and each episode proceeds in a discrete number of time steps (from $t=0$ to $t=T$).

As I defined it here, the return, in the case of MC algorithms, is only associated with a single episode (that is, it is the return of one episode). However, in general, the expected return can be different from one episode to the other, but, for simplicity, we will assume that the expected return (of all states) is the same for all episodes.

To recapitulate, the first-visit and every-visit MC (prediction) algorithms are used to estimate $v_\pi(s)$, for all states $s \in \mathcal{S}$. To do that, at every episode, these two algorithms use $\pi$ to behave in the environment, so that to obtain some knowledge of the environment in the form of sequences of states, actions and rewards. This knowledge is then used to estimate $v_\pi(s)$. How is this knowledge used in order to estimate $v_\pi$? Let us have a look at the pseudocode of these two algorithms.

$N(s)$ is a "counter" variable that counts the number of times we visit state $s$ throughout the entire algorithm (i.e. from episode one to $num\_episodes$). $\text{Returns(s)}$ is a list of (undiscounted) returns for state $s$.

I think it is more useful for you to read the pseudocode (which should be easily translatable to actual code) and understand what it does rather than explaining it with words. Anyway, the basic idea (of both algorithms) is to generate trajectories (of states, actions and rewards) at each episode, keep track of the returns (for each state) and number of visits (of each state), and then, at the end of all episodes, average these returns (for all states). This average of returns should be an approximation of the expected return (which is what we wanted to estimate).

The differences of the two algorithms are highlighted in $\color{red}{\text{red}}$. The part "If state $S_t$ is not in the sequence $S_0, S_1, \dots, S_{t-1}$" means that the associated block of code will be executed only if $S_t$ is not part of the sequence of states that were visited (in the episode sequence generated with $\pi$) before the time step $t$. In other words, that block of code will be executed only if it is the first time we encounter $S_t$ in the sequence of states, action and rewards: $S_0, A_0, R_1, S_1, A_1, R_2 \ldots, S_{T-1}, A_{T-1}, R_T$ (which can be collectively be called "episode sequence"), with respect to the time step and not the way the episode sequence is processed.  Note that a certain state $s$ might appear more than once in $S_0, A_0, R_1, S_1, A_1, R_2 \ldots, S_{T-1}, A_{T-1}, R_T$: for example, $S_3 = s$ and $S_5 = s$.

Do not get confused by the fact that, within each episode, we proceed from the time step $T-1$ to time step $t = 0$, that is, we process the "episode sequence" backwards. We are doing that only to more conveniently compute the returns (given that the returns are iteratively computed as follows $G \leftarrow G + R_{t+1}$).

So, intuitively, in the first-visit MC, we only update the $\text{Returns}(S_t)$ (that is, the list of returns for state $S_t$, that is, the state of the episode at time step $t$) the first time we encounter $S_t$ in that same episode (or trajectory). In the every-visit MC, we update the list of returns for the state $S_t$ every time we encounter $S_t$ in that same episode.

For more info regarding these two algorithms (for example, the convergence properties), have a look at section 5.1 (on page 92) of the book "Reinforcement Learning: An Introduction" (2nd edition), by Andrew Barto and Richard S. Sutton.


Why "Exploratory moves do not result in any learning"? In Chapter 1 of the book Reinformcement Learning An Introduction 2nd Edition by Richard S. Sutton and Andrew G.Barto, there is one statement "Exploratory moves do not result in any learning".

This sentence is in Figure 1.1.

  Figure 1.1: A sequence of tic-tac-toe moves. The solid black lines represent the moves taken during a game; the dashed lines represent moves that we (our reinforcement learning player) considered but did not make. Our second move was an exploratory move, meaning that it was taken even though another sibling move, the one leading to e⇤, was ranked higher. Exploratory moves do not result in any learning, but each of our other moves does, causing updates as suggested by the red arrows in which estimated values are moved up the tree from later nodes to earlier nodes as detailed in the text.

It confuses me. In my understanding, exploration should contribute to learning in almost all RL algorithms. So, why does the book state "Exploratory moves do not result in any learning" in this case?

I believe this is a pedagogical decision. Because the sentence occurs in the first chapter of the book, I think the authors are trying to avoid the objection that a neophyte might make: learning from random movements seems like it will cause you to learn strange behaviors.

Certainly, the statement is inaccurate. We need only reach page 26 to see a counterexample: The Q-learning equation (2.1) sums over all actions, not just the greedy ones. This also applies to the temporal difference learning method specified in Chapter 6, which is the method Figure 1.1 is discussing.


How can I detect thin objects (like pens and pencils) without a bounding box but only 2 endpoints and the orientation? I am looking to detect thin objects, like pens, pencils, and surgical instruments. The bounding box is not important, but I am looking to see if I can train a model to detect both the object as well as its orientation.
Typical object detection networks, like R-CNN, YOLO, and SSD encode the class name and bounding boxes. Instead of bounding boxes, I'm looking to encode only 2 points, one starting $x,y$ point and one ending $x,y$ point.  The start point for objects is where one would grip the object.  For instance:

The pencil eraser(start point) is pointed 50 degrees to the top right.
The surgical instrument is 10 degrees from the x-axis and the handle is pointed to the bottom right.
Pen tip (endpoint) is pointing vertically upwards.
Fork, the start point would be the grip handle part, and the endpoint would be in the middle where the 4 prongs are.

As long as I can encode the start and endpoints, then I can determine the orientation. I would need to define these points during training.
The question is whether there is an existing model (mobile net/inception/RCNN) that I can encode this information in?  One potential way I was thinking was to use YOLO and for the bounding box, the top left $x,y$ would be the starting point $x,y$ (handle), whereas the bounding box's width and height would be replaced with the endpoint $x,y$ (pencil writing tip, fork prongs.

Recent work achieves a similar task: Object recognition together with the bounding box (e.g. YOLO---there are quite a few on Github too). The bounding box is not enough in your case, but it is an interesting pattern: Recognition plus some form of measurement. Such architectures could be good candidate to start with, and repurpose for stick orientation.

The problem could also leverage the current results in gait recognition. In fact, this looks closer to the problem at hand than object recognition. An example is this model based on multiview (many pictures input) recognition, with a demonstration on Github. Gait recognition is also popular these days, and many inspiring papers and OSS implementations are available.

The above presents two approaches your problem could benefit from, as a "combination". My gut feeling is that tilt and orientations may be easier than direction (i.e. where is the tip?).

The question calls for training a model. An alternative approach, perhaps to start with and get more insight, could be to go with "standard" computer vision algorithms, such as the Hough Transform. This transforms allows to find lines in an image. The mathematics are at reach, and it may work well enough for a quick demo. Also, your handle name suggests "embedded mobile" engineer, and a simple Hough Transform could be cheap on mobile.


Can we use Multiple data as Input in a NN for a single Output? So I am new to NN and I'm trying to go deep and apply it to my subject. I would like to ask: the input of the NN can be 2 or more values for example-> the measurement of a value, distance, and time? An example of input data would be [ [1,2,3, ....],[11,22,33, .....],[5] ] whose output is a value 1 for example or cat or an generated model.

Yes, it can be those multiple inputs, you would have to design the network like that (to have 3 input layers and then pool them afterwards).
But, an easier solution would be to flatten this array and put it through 1D CNN and finally put it through a softmaxx.


How difficult is this sound classification? I want a microphone to pick up sounds around me (let's say beyond a 3 foot radius), but ignore sounds made at my desk, such as the rustling of paper, clicking a mouse and typing, my hands brushing up on the table, putting a pen down, etc.

How hard would it be for AI to be able to distinguish these sounds from surrounding sounds, such as someone knocking on my door or a random loud sound from further away? How would you implement this? Is it possible that a pre-trained model could accomplish this, and work reliably for most people at their desk? I don't have any experience in AI.

I think if you got the dataset, then a standard 1d convolutional neural network would work to some extent. It's not that there is some property of nearby sounds that it would pick up on. It would just memorize all the sounds that tend to come from your desk. I think the coding part would be pretty standard stuff. But collecting the data will be hard. You have to get a really big labeled dataset of sounds coming from your desk and sounds coming beyond a 3 foot radius. This dataset has to be realistic and representative of the real world. Getting that dataset would be pretty tricky but it is doable if you put multiple microphones in your house in order to triangulate the exact positions of all sounds. It would be like GPS but using sounds waves instead of light waves.


What makes GAN or VAE better at image generation than NN that directly maps inputs to images Say a simple neural network's input is a collection of tags (encoded in some way), and the output is an image that corresponds to those tags. Say this network consists of some dense layers and some reverse (transpose) convolution layers.

What is the disadvantage of this network, that directs people to invent fairly complicated things like GANs or VAEs?

The only disadvantage and difference between these generative models and the method you describe, is the input. You describe inputting tags, where as for a GAN, or VAE, the generation segment of the model takes in some representation of a probability distribution. For a GAN, it's mostly random noise, and for a VAE it is some latent space (see nbros answer).
Your described method prevents the network from properly learning fluid generation. If you have a discrete input, the network will attempt to perform a sort of classification on the input, rather then generation, and so when you try to generate a new image, you will most likely get the image equivalent of gibberish.
In fact, that's why a standard auto-encoder (not variational) doesn't work very well for generation. You would think that you could feed in your own custom input into the latent space:
But if you tried this, you would end up telling the network to try and generate something from a latent space it can't interpret.
Hence where the "variational" part of the VAE comes in. This helps the network learn to generate from a continuous distribution, so no matter what input you use, the network will be able to interpret it and give an appropriate output.
As for a GAN, it is simply fed random noise at each training step, so it too generates based on a continuous distribution.
If you were to try and train your method of generation, I would predict that you would find an average of all images that share similar tags (say you have the tags of cat, dog and brown haired, if you input "dog=1, cat=0, brown haired=1" you would get an average of all brown haired dogs), but if you tried to input a combination of tags the network has not seen, as it has not learnt from a continuous distribution, the resultant image would not be anything like what you'd expect from those tags.


Historical weakness of GOFAI in relation to partisan combinatorial games? I was recently perusing the paper Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress (A.L. Samuel, 1967), which is interesting historically.

I was looking at this figure, which involved Alpha-Beta pruning.

It occurred to me that the types of non-trivial, non-chance, perfect information, zero-sum, sequential, partisan games utilized (Chess, Checkers, Go) involve game states that cannot be precisely quantified. For instance, there is no way to ascribe an objective value to a piece in Chess, or any given board state.  In some sense, the assignment of values is arbitrary, consisting of estimates.

The combinatorial games I'm working on are forms of partisan Sudoku, which are bidding/scoring (economic) games involving territory control.  In these models, any given board state produces an array of ratios allowing precise quantification of player status. Token values and positions can be precisely quantified.

This project involves a consumer product, and the approach we're taking currently is to utilize a series of agents of increasing sophistication to provide different levels challenge for human players.  These agents also reflect what is known as a "strategy ladder".

Reflex Agents (beginner)
Model-based Reflex Agents (intermediate)
Model-based Utility Agents (advanced)

Goals may also be incorporated to these agents such as desired margin of victory (regional outcome ratios) which will likely have an effect on performance in that narrower margins of victory appear to entail less risk.

The "respectably weak" vs. human performance of the first generation of reflex agents suggests that strong GOFAI might be possible. (The branching factors are extreme in the early and mid-game due to the factorial nature of the models, but initial calculations suggest that even a naive minimax lookahead will be able to look farther more effectively than humans.) Alpha-Beta pruning in partisan Sudoku, even sans a learning algorithm, should provide greater utility than in previous combinatorial game models where the values are estimates.

Is the historical weakness of GOFAI in relation to non-trivial combinatorial games partly a function of the structure of the games studied, where game states and token values cannot be precisely quantified?

Looking for any papers that might comment on this subject, research into combinatorial games where precise quantification is possible, and thoughts in general.

I'm trying to determine if it might be worth attempting to develop a strong GOFAI for these models prior to moving up the ladder to learning algorithms, and, if such a result would have research value.

There would definitely be commercial value in that strong GOFAI with no long-term memory would allow minimal local file size for the apps, which must run on lowest-common-denominator smartphones with no assumption of connectivity.

PS- My previous work on this has involved defining the core heuristics that emerge from the structure of the models, and I'm slowly dipping my toes into the look ahead pool.  Please don't hesitate to let me know if I've made any incorrect assumptions.

Nice question!

I think there are a couple of issues at work here.

  Is the historical weakness of GOFAI in relation to non-trivial
  combinatorial games partly a function of the structure of the games
  studied, where game states and token values cannot be precisely
  quantified?

I think the short answer is yes. The real issue is in the last part:

  token values cannot be precisely quantified

The most successful GOFAI approaches to these games were all some variation on A* search, combining combinatorial search with some form of heuristic function that estimated the value of the pieces and their positions in any given state. Piece counting is probably a better heuristic than not counting anything at all, but it's still clearly incorrect, because a player with less material may still have an overwhelming positional advantage. Some heuristics can try to estimate this positional advantage as well however.

The real problem that GOFAI encounters in these games is that positional advantage can be emergent in ways that require incredible heuristic power to detect. Checkers is a good example. In the 1990's, the Chinook project at the University of Alberta set out to solve it completely. Checkers is notable because it had the same world champion for more than 15 consecutive years, Marion Tinsley. Tinsley lost a total of 7 competitive matches over 40 years of play. This makes him an especially interesting person to examine when we look at combinatorial games. Figuring out how Tinsley plays can help us understand how human intelligence works in games like this. In the course of solving checkers, the researchers noted that Tinsley was making moves that required up to 42 move lookaheads to reveal an advantage (See Schaeffer et al., AI Magazine, Vol. 17, Issue 1).

This strongly suggests that Tinsley was not methodically considering each possible move. Instead, by his own admission, his thinking was guided by a combination of memory over his 40 year career (in one match against Chinook in 1992, he indicated he was trying to recall a sequence from a match 30 years prior when making a move (AI Magazine Volume 14, Number 2); and of attentional heuristics (i.e. not thinking about every move sequence, and being able to reliably rule out parts of the search space without looking at them).

The key is that for GOFAI to solve checkers without heuristics (i.e. to solve it exactly), required enormous amounts of computational power, because some moves yield positional advantages that require 40+ moves of followthrough. Even an incredibly simple game (branching factor of 2) would be hard under that constraint.

In contrast though, self-play techniques like those pioneered in Backgammon with TD-Gammon (Tesauro, Comm. of the ACM 1995) mimic the process through which Tinsley became so good: they play lots and lots of games, learn a good heuristic estimate of position and material value, and more importantly, can learn to remember odd circumstances that require careful play. TD-Gammon achieved worldclass play despite only explicitly looking 2 moves ahead. GOFAI search techniques weren't even close despite searching much more deeply.

Modern research on attention could salvage the GOFAI approach however. If you can learn to tell what's important, you might be able to get a lot more value out of deeper lookaheads. This seems even closer to how Tinsley played: great ability to estimate value was used to guide an explicit analysis of a specific chain of moves.


Why is it that the state visitation frequency equals the sum of state visitation frequency from initial time step to the horizon? In the maximum entropy inverse reinforcement learning paper, Ziebart et al. show that the state visitation frequency $\rho(s)$ of a state $s$ can be computed as
$$
\rho_{\pi}(s) = \sum_{t}^{T} P(s_t=s|\pi),
$$
which is the sum of the probability that the state being visited at each time step.
I just don't understand why is it the sum? From my perspective, a frequency should be the less than one, so that it should be the average value
$$
\rho_{\pi}(s) = \frac{1}{T}\sum_{t}^{T} P(s_t=s|\pi).
$$

It should be the average and this is rarely mentioned by people except for a IRL summer camp at UCB. You can check this GithubIssue for details.


Multicamera Tracking vs Single Fisheye Camera Suppose you want to detect objects and also track objects and people. Is it better to train a model using a single fisheye camera or using multiple cameras that mimic the view of the fisheye camera?

Also, what can be done to remove objects that are washed out? Like for very small objects, how do you make them more visible? Would multicamera tracking be better in this scenario?

Fisheye camera is always worst. Both convolutional networks object detectors and feature-based object detectors rely on the "isometry" of planar image - lack of strong distortions. Multiple camera have added benefit of several independent sources of information - ensembling. If each camera processed by separate network that may help in verification of objects by voting. With very small objects no simple methods would help. Multiple camera may help a little if all camera output processed together (stacked) as single network input, but don't hold much hope - detecting few pixel objects is very difficult, if possible at all.


Why did ML only become viable after Nvidia's chips were available? I listened to a talk by panel consisted of two influential Chinese scientists: Wang Gang and Yu Kai and others.

When being asked about the biggest bottleneck of the development of artificial intelligence in the near future (3 to 5 years), Yu Kai, who has a background in the hardware industry, said that hardware would be the essential problem and we should pay most of our attention to that. He gave us two examples:

In the early development of the computer, we compare our machines by its chips;
Artificial intelligence which is very popular these years would be almost impossible if not empowered by Nvidia's GPU.

The fundamental algorithms existed already in the 1980s and 1990s, but artificial intelligence went through 3 AI winters and was not empirical until we can train models with GPU boosted mega servers.

Then Dr. Wang commented to his opinions that we should also develop software systems because we cannot build an automatic car even if we have combined all GPUs and computation in the world together.

Then, as usual, my mind wandered off and I started thinking that what if those who can operate supercomputers in the 1980s and 1990s utilized the then-existing neural network algorithms and train them with tons of scientific data? Some people at that time can obviously attempt to build AI systems we are building now. But why did AI become a hot topic and become empirical until decades later? Is it only a matter of hardware, software and data?

There is a lot of factors for the boom of AI industry. What many people miss though is the boom has mostly been in the Machine Learning part of AI. This can be attributed to various simple reasons along with their comparisons during earlier times:

Mathematics:  The maths behind ML algorithms are pretty simple and known for a long time (whether it would work or not was not known though). During earlier times it was not possible to implement algorithms which require high precision of numbers, to be calculated on a chip, in an acceptable amount of time. One of the main arithmetic operations division of numbers still takes a lot of cycles in modern processors. Older processors were magnitude times slower than modern processors (more than 100x), this bottleneck made it impossible to train sophisticated models on contemporary processors.
Precision: Precision in calculations is an important factor in ML algorithms. 32 bit precision in processor was made in the 80's and was probably commercially available in the late 90's (x86), but it was still hella slow than current processors. This resulted in scientists improvising on the precision part and the most basic Perceptron Learning Algorithm invented in the 1960's to train a classifier uses only $1$'s and $0$'s, so basically a binary classifier. It was run on special computers. Although, it is interesting to note that we have come a full circle and Google is now using TPU's with 8-16 bit accuracy to implement ML models with great success.
Parallelization : The concept of parallelization of matrix operations is nothing new. It was only when we started to see Deep Learning as just a set of matrix operations we realized that it can be easily parallelized on massively parallel GPU's, still if your ML algorithm is not inherently parallel then it hardly matters whether you use CPU or GPU (e.g. RNN's).
Data: Probably the biggest cause in the ML boom. The Internet has provided opportunities to collect huge amounts of data from users and also make it available to interested parties. Since an ML algorithm is just a function approximator based on data, therefore data is the single most important thing in a ML algorithm. The more the data the better the performance of your model.
Cost: The cost of training a ML model has gone down significantly. So using a Supercomputer to train a model might be fine, but was it worth it? Super computers unlike normal PC's are tremendously resource hungry in terms of cooling, space, etc. A recent article on MIT Technology Review points out the carbon footprint of training a Deep Learning model (sub-branch of ML). It is quite a good indicator why it would have been infeasible to train on Supercomputers in earlier times (considering modern processors consume much lesser power and gives higher speeds).
Although, I am not sure but I think earlier supercomputers were specialised in "parallel+very high precision computing" (required for weather, astronomy, military applications, etc) and the "very high precison part" is overkill in Machine Learning scenario.

Another important aspect is nowadays everyone has access to powerful computers. Thus, anyone can build new ML models, re-train pre-existing models, modify models, etc. This was quite not possible during earlier times,

All this factors has led to a huge surge in interest in ML and has caused the boom we are seeing today. Also check out this question on how we are moving beyond digital processors.


How should I decay $\epsilon$ in Q-learning? How should I decay the $\epsilon$ in Q-learning?

Currently, I am decaying epsilon as follows. I initialize $\epsilon$ to be 1, then, after every episode, I multiply it by some $C$ (let it be $0.999$), when it reaches $0.01$. After that, I keep $\epsilon$ to be $0.01$ all the time. I think this has a terrible consequence.

So, I need a $\epsilon$ decay algorithm. I haven't found script or formula about it, so can you tell me?

The way you have described tends to be the common approach. There are of course other ways that you could do this e.g. using an exponential decay, or to only decay after a 'successful' episode, albeit in the latter case I imagine you would want to start with a smaller $\epsilon$ value and then decay by a larger amount.


What is the difference between Sentiment Analysis and Emotion Recognition? I found Sentiment Analysis and Emotion Recognition as two different categories on paperswithcode.com. Should both be the same as my understanding? If not what's the difference?

It's just as in common use. Sentiment is a superset of emotion, further including feelings, intuition, and rational conclusions drawn from past experience. Analysis is also a superset of recognition, which also includes taking emotions like contentment, happiness, humor affected, anger, rage, and passion and determining what sequences of them mean in the context of the scene or senario.


How should we pad an image to be fed in a CNN? As everyone experienced in deep learning might know, in an image classification problem we normally add borders to images then resize it to the input size of a CNN network. The reason of doing this is to keep aspect ratio of the original image and retain it's information.

I have seen people fill black (0 pixel value for each channel), gray (127 pixel value for each channel), or random value generated from gaussian distribution to the border.

My question is, is there any proof that which of these is correct?

If the computational components of the forward feed through the network have no curvature, which is normally the case in a sum of products, then it can be proven that any constant pixel value is equivalent in terms of effect on convergence results.  We wouldn't expect a proof for that, since it would be too trivial to spend time writing up for publication.  In general, functioning vision systems have feed forward computational components with curvature, so the padding is likely significant.

Even the convolutional layers may have activation functions or something even more complex going forward, as noted in Gauge Equivariant Convolutional Networks and the Icosahedral CNN (Taco S. Cohen, Maurice Weiler, Berkay Kicanaoglu, Max Welling, 2019).

If purely stochastic values with value distributions like that of the un-padded coordinates are used, it may be possible to prove that some gain is made, but none appeared in a few academic article searches just made.  Not surprisingly, there are many proofs regarding the properties of various message padding strategies for cryptography.

Short of the inclusion of thermal or quantum noise acquisition devices in VLSI circuitry and exposure of those devices in software, purely stochastic values cannot be generated.  This leaves the risk of a learning approach expected to extract features from frames learning features of the pseudo-random noise generator used to pad.

The answer is that none are universally correct and there appears to be much work to do in proving advantages between different techniques in as many cases as such advantages can be proven.


What is meant by degrees of freedom of latent variables? ...Designing such a likelihood function is typically challenging; however, we observe that features like spectrogram are effective when latent variables have limited degrees of freedom. This motivates us to infer latent variables via methods like Gibbs sampling, where we focus on approximating the conditional probability of a single variable given the others.

Above is an excerpt from a paper I've been reading, and I don't understand what the author means by degrees of freedom of latent variables. Could someone please explain with an example, or add more details?

References
Shape and Material from Sound (31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA)

A good example is the degree of freedom in Student's distribution:

 The degrees of freedom refers to the number of independent observations in a set of data.

For example:

When estimating a mean score or a proportion from a single sample, the number of independent observations is equal to the sample size minus one.

e.g, if we have 100 observation $X_1, \ldots, X_{100}$ and we want to estimate their mean $\bar{X}$, as $\bar{X} = \frac{X_1 + \cdots + X_{100}}{100}$, if we know the mean, just we need to find the value of 99 variables from $X_1, \ldots, X_{100}$. Hence, here the degree of freedom is 99.
Your referenced paragraph is a general explanation in the paper as well. However, base on the above example, the degree of freedom in the paragraph depends on the likelihood function and number of observations that we have from spectrograms.
Now, as the DoF of latent variables is not high, using Gibbs sampling we will approximate some observations, and then using them we will compute the value of the latent variables.


What is the order of execution of steps in back-propagation algorithm in a neural network? I am a machine learning newbie. I am trying to understand the back-propagation algorithm. I have a training dataset of 60 instances/records.
What is the correct order of the process? This one?

Forward pass of the first instance. Calculate the error.
Weight update using backpropagation.
Forward pass of the second instance. Calculate the error.
Weight update using backpropagation. And so on...

Or

Forward pass of all instances one by one. Keep track of the error as a vector.
Weight update using backpropagation.

This video https://www.youtube.com/watch?v=OwdjRYUPngE is similar to the second process. Is it correct?

Both are feasible.
A generalization is to apply the modification of the weights after the presentation of $n$ examples. If $n=1$, this is online training. If $n=60$ ($60$, in your case, is the size of the dataset), this is batch training. In other cases, this is mini-batch training.
The main difference is not the computation complexity of the algorithm, but the theoretical speed of convergence to an "optimal" set of weights.
It is now generally admitted that online training is faster. Online training performs a stochastic approximation of the gradient descent method. The true gradient of the cost function over the whole training set is approximated by a gradient at each presentation of a training example.
Intuitively, with batch learning the weights are modified by an average of the gradient over the whole training set and averaging destroys information.
While with stochastic (or mini-batch learning), each example has his word to say. One after the other.
This has also been discussed here.


Creating a NLP driven chatbot I would like to create a chat bot for an e-commerce website that sells a wide range of general merchandize items, from t-shirts, jumpers to calculators. Its primary objective is to develop a Q&A option for visitors/potential customers, to improve engagement on the website. As such, the chat bot is required to be fairly conversational.
I am experienced in classification et al, but know only the very basics on NLP. Can you provide suggestions on where to begin, e.g., recommended readings/ sources?
Also note, there is currently has no chat bot system in place, and hence no historical conversation data of any form.

The deeplearning.ai Natural Language Processing Specialization, is a great place to start. It'll brush up some basic concepts of NLP and then get into SOTA methods  such as Transformers. There's even a project in one of the courses about building a chatbot using transformers, it also has a ton of papers and other sources mentioned.

Rasa is a great software tool/package to get started with chatbots too. It's a great engaging community so your queries should be quickly answered.


What would motivate a machine? Currently, within the AI development field, the main focus seems to be on pattern recognition and machine learning. Learning is about adjusting internal variables based on a feedback loop.

Maslow's hierarchy of needs is a theory in psychology proposed by Abraham Maslow that claims that individuals' most basic needs must be met before they become motivated to achieve higher-level needs.

What could possibly motivate a machine to act? Should a machine have some sort of DNA-like structure that would describe its hierarchy of needs (similar to Maslow's theory)? What could be the fundamental needs of a machine?

The current method to implement motivation is some kind of artificial reward. Deepmind's DQN for example is driven by the score of the game. The higher the score, the better. The AI learns to adjust its actions to get the most points and therefore the most reward. This is called reinforcement learing. The reward motivates the AI to adapt its actions, so to speak.

In a more technical term, the AI wants to maximize utility, which depends on the implemented utility function. In the case of DQN, this would be maximizing the score in the game.

The human brain functions in a similar fashion, although a little more complex and often not as straight forward. We as humans usually try to adjust our actions to produce a high output of dopamine and serotonin. This is in a way similar to the reward used to control AIs during reinforcement learning. The human brain learns which actions produce the most amount of those substances and finds strategies to maximize the output. This is, of course, a simplification of this complex process, but you get the picture.

When you talk about motivation, please don't mix it up with consciousness or qualia. Those are not required for motivation at all. If you want to discuss consciousness and qualia in AI, that's a totally different ball game.

A child isn't curious for the sake of curiosity. It gets positive reinforcement when exploring because the utility function of the child's brain rewards exploration by releasing rewarding neurotransmitters. So the mechanism is the same. Applying this to AI means defining a utility function that rewards new experiences. There is no inner drive without some kind of reinforcing reward.


Can neural networks deal with unbounded numbers as inputs? I want to train an ANN. The problem is that the input features are completely unbounded (There are no boundaries as maximum and minimum for them).

For example, the following input vectors $(42, 54354354)$ and $(0.4, 47239847329479324732984732947)$ are both valid.

I know RNNs that can add up input neurons, which are pretty similar to my case, but the number of the digits was limited in all of the implementations.

Is there a way to implement an ANN that can add up the input numbers of any magnitude?

Depending on the activation functions in the first layer, this is not a real problem, many functions such as $\tanh(x)$ and $\sigma(x)$ (sigmoid) have asymptotic upper and lower bounds, so the huge input values swamp all other inputs in the corresponding neurons, but the output is well-behaved.

However, a conversion before the input layer may be appropriate for some kind of data. For example, you might want to take the $\log(x)$ of the input values such that the initial weight networks work with the relation of the values instead of their absolute magnitude. This may be useful for audio data such as speech or music and many other measurements of signals that may be attenuated before the measurement.

If your numbers don't actually represent magnitudes of some kind but arbitrary sequences of digits, you should use a network that can deal with sequences, of course.


REINFORCE algorithm for portfolio optimization - problem while training I'm trying to implement the Reinforce algorithm (Monte Carlo policy gradient) in order to optimize a portfolio of 94 stocks on a daily basis (I have suitable historical data to achieve this). The idea is the following: on each day, the input to a neural network comprises of the following:

historical daily returns (daily momenta) for previous 20 days for each of the 94 stocks
the current vector of portfolio weights (94 weights)

Therefore states are represented by 1974-dimensional vectors. The neural network is supposed to return a 94-dimensional action vector which is again a vector of (ideal) portfolio weights to invest in. Negative weights (short positions) are allowed and portfolio weights should sum to one. Since the action space is continuous I'm trying to tackle it via the Reinforce algorithm. Rewards are given by portfolio daily returns minus trading costs. Here's a code snippet:

class Policy(nn.Module):
    def __init__(self, s_size=1974, h_size=400, a_size=94):
        super().__init__()
        self.fc1 = nn.Linear(s_size, h_size)
        self.fc2 = nn.Linear(h_size, a_size)
        self.state_size = 1974
        self.action_size = 94
    def forward(self, x):
        x = F.relu(self.fc1(x))
        x = self.fc2(x)
        return x
    def act(self, state):
        state = torch.from_numpy(state).float().unsqueeze(0).to(device)
        means = self.forward(state).cpu()
        m = MultivariateNormal(means,torch.diag(torch.Tensor(np.repeat(1e-8,94))))
        action = m.sample()
        action[0] = action[0]/sum(action[0])
        return action[0], m.log_prob(action)

Notice that in order to ensure that portfolio weights (entries of the action tensor) sum to 1 I'm dividing  by their sum. Also notice that I'm sampling from a multivariate normal distribution with extremely small diagonal terms since I'd like the net to behave as deterministically as possible. (I should probably use something similar to DDPG but I wanted to try out simpler solutions to start with).

The training part looks like this:

optimizer = optim.Adam(policy.parameters(), lr=1e-3)

def reinforce(n_episodes=10000, max_t=10000, gamma=1.0, print_every=1):
    scores_deque = deque(maxlen=100)
    scores = []
    for i_episode in range(1, n_episodes+1):
        saved_log_probs = []
        rewards = []
        state = env.reset()
        for t in range(max_t):
            action, log_prob = policy.act(state)
            saved_log_probs.append(log_prob)
            state, reward, done, _ = env.step(action.detach().flatten().numpy())
            rewards.append(reward)
            if done:
                break
        scores_deque.append(sum(rewards))
        scores.append(sum(rewards))

        discounts = [gamma**i for i in range(len(rewards)+1)]
        R = sum([a*b for a,b in zip(discounts, rewards)])

        policy_loss = []
        for log_prob in saved_log_probs:
            policy_loss.append(-log_prob * R)
        policy_loss = torch.cat(policy_loss).sum()

        optimizer.zero_grad()
        policy_loss.backward()
        optimizer.step()

        if i_episode % print_every == 10:
            print('Episode {}\tAverage Score: {:.2f}'.format(i_episode, np.mean(scores_deque)))
            print(scores[-1])

    return scores, scores_deque

scores, scores_deque = reinforce()

Unfortunately, there is no convergence during training even after fiddling with the learning rate so my question is the following: is there anything blatantly wrong with my approach here and if so, how should I tackle this?

One thing you could try to simplify the output logic would be to use a softmax output and then with your outputs set a var to = (max_output - min_output)/2 then treat that number as your long/short "threshold" and this ensures that your ouput always sums to 1 while still allowing the net to learn to output short signals. I would also check to make sure you have 1.0 bias nuerons since I imagine at times (especially first epoch) you are passing in zeros for the portfolio weights.


What is the reason AMD Radeon is not widely used for machine learning and deep learning? What is the reason AMD Radeon is not widely used for machine learning and deep learning? Is it mainly an issue of lack of software? Or is Radeon's GPU not as good as NVIDIA's?

The main reason that AMD Radeon graphics card is not used for deep learning is not the hardware and raw speed. Instead it is because the software and drivers for deep learning on Radeon GPU is not actively developed. NVIDIA have good drivers and software stack for deep learning such as CUDA, CUDNN and more. Many deep learning library also have CUDA support. However for AMD there is little support on software of GPU. There is ROCM but it is not well optimized and also a lot of deep learning libraries don't have ROCM support.

Also on the hardware side, AMD lacks deep learning specific features like tensor cores. AMD also don't have data centre specific cards like the Tesla lineup. The performing of AMD cards also is not very good until recently with the RDNA architecture.

Lastly, data centres don't change hardware very often. NVIDIA flourished in the deep learning field very early on so many companies bought a lot of Tesla GPU. Even if AMD caught up in the deep learning field it is very hard as many companies have used NVIDIA from a long time ago, and switching to a very different architecture of GPU is troublesome, especially for a data centre with couple hundred or more servers.

AMD has also "given up" on deep learning market. They don't actively tries to make effort in deep learning data centres using AMD hardware. Many data centre also use very old Tesla hardwares like Tesla K80 of M series.

Hope this can help you.


Can HMM, MRF, or CRF be used to classify the state of a single observation, not the entire observation sequence? I learn that the Viterbi algorithm used for Hidden Markov Model (HMM) can classify a sequence of hidden states from the corresponding observations; Markov Random Field (MRF) and Conditional Random Field (CRF) can also do it.

Can these algorithms be used to classify a single future state?

Yes this is possible and is exactly what a Markov process aims to accomplish.

The Hidden Markov Model can be considered a simple dynamic Bayesian network. This means that it will generate a probabilistic outcome for a number of states (classes) given a sequence of inputs.

This can be used for a classification task based on a threshold probability to make a confirmed decision.

Let's take a simple example

The above example is a model to determine  how a person will be feeling given some sample data of the previous days.

# Sample data
data = ['Healthy', 'Healthy', 'Fever']

Using this data, it's possible to calculate the probability of each possible state (outcome).

# Probability after 2 Healthy and 1 Fever day
P = 0.6 * 0.7 * 0.3

# Final day state 'Fever'
# Calculating probabilities for each state
Dizzy  = P * 0.6
Cold   = P * 0.3
Normal = P * 0.1

We can calculate the probability of each state and this will be unique for every unique sequence of historical data.


Does balancing the training data set distribution for a neural network affect its understanding of the original distribution of data? I have a very imbalanced dataset of two classes: 2% for the first class and 98% for the second. Such imbalance does not make training easy and so balancing the data set by undersampling class 2 seemed like a good idea.

However, as I think about it, should not the machine learning algorithm expect the same data distribution in nature as in its training set? I know, for sure, that the distribution of data in nature matches my imbalanced dataset. Does that mean that the balanced dataset will negatively affect the neural net performance with testing? when it assumed a different distribution of data caused by my balanced data set.

This is a very good question. Your problem is the classic classification problem of Neural Networks. In this problem the main objective of the Neural Network is to transform the data by some non-linear (in general) transformation so that the data becomes linearly separable for the final layer to perform classification.

Point to Note: This is not a regression problem, so that you are trying to fit a curve. Whenever there is a regression problem logically you can use a PDF to write some kind of information about new data. You can express mathematically the probability of your data falling within a certain range of error, since this is a optimising continuous function problem (generally RMSE).

This is not in the case of classifier. Classifier follow Bernoulli probability (though we represent the cost function as continuous). So current event is independent of past events. This makes a classifier harder to train for unbalanced class. So if we write:

func foo(data):
    return True

It pretty much has 98% accuracy, but you can understand we do not want this type of classifier.

In general we want both classes to have good accuracy scores, sometimes this is measured by $F1_{score}$ but I like to think it in terms of proportionality. If we have $n$ examples with $m$ in one class, then and the classifier $a_1$ and $a_2$ correct predictions in both classes respectively, then I would check both the metric $ \frac {a_1}{m}$ and $ \frac {a_2}{n-m}$, which gives you the general idea.

Also in practical the identification 2% is sometimes far more important than the rest 98% (air-plane defects, cancer detection). So we use special ML algorithm called Anomaly Detectors for such type of problems.


What is the meaning of test data set in naive bayes classifier or decision trees? What is the benefit of a test data set, especially for naive bayes estimator or decision tree construction?

When using a naive bayes classifier the probabilities are a fact. As far as I know there is nothing one could tune (like the weights in a neural net). So what is the purpose of the test data set? Simply to know if one can apply naive bayes or not?

Similiarly what is the benefit of the test data set when constructing a decision tree. We alread use the gini impurity to construct the best possibe decision tree and there is nothing we could do when we get bad results with the test data set.

Your assumption about the test data is not correct completely. Maybe you use the test data to tune your learning algorithm to work better on the test data, but it's not the whole thing. Sometimes you need to know that the ML method is working or not and have a sense about how much does it work!

You have other scenarios that you want to evaluate your method:

Compare the result of the leaner with other techniques. For example, you are considering DT versus an SVM classifier over a data set. If you want to compare them, you need a value to found such a sense about the comparison.
Sometimes you are using an ensemble method and you want to tune some parameters to balance between using different ML methods. Hence, you need to evaluate these learning methods (DT, Naive Bayes) to improve the ensemble method.


Can augmented reality be a training system for computer vision? Is augmented reality a training system for computer vision? As in, Augmented systems use their data to help train computer vision algorithms, or is augmented reality computer vision itself?

Let me re-frame your question before answering:

  Can augmented reality be a training system for computer vision?

Yes, why not! Also, I'm pretty sure the big companies who have their aug. reality products out there are secretly optimizing their CV algorithms(although we'll have no proof).

A very similar(but a different) example would be how Comma.ai's app pays users for recording their driving, and then uses it to train their own self-driving cars.

So, if that can be done, I don't see why augmented reality cannot be used to train CV algos. In fact, it's a much more richer, localized dataset.


Upper limit to the maximum cumulative reward in a deep reinforcement learning problem Is there an upper limit to the maximum cumulative reward in a deep reinforcement learning problem? For example you want to train an DQN agent in an environment and you want to know what is the highest possible value you can get from the cumulative reward, so you can compare this with your agents performance.

In any reinforcement learning problem, not just Deep RL, then there is an upper bound for the cumulative reward, provided that the problem is episodic and not continuing.
If the problem is episodic and the rewards are designed such that the problem has a natural ending, i.e. the episode will end regardless of how well the agent does in the environment, then then you could work it out by calculating the max possible reward in each step of the episode; however this is potentially non-trivial depending on your environment.
For an example in a trivial setting, however, imagine the problem of cartpole -- I could define the MDP to have a reward of +1 for every time step that the agent is able to balance the pole upright, and 0 when the pole falls. If I also defined that the problem terminates after 200 time steps then the upper bound on cumulative rewards for this problem would be 200.
In general, if the problem is continuing then in theory the problem goes on infinitely and so there is no upper bound, as the episode never ends -- this is partly why we use the discount factor, to ensure that $\sum_{k=0} \gamma^k R_{t+k}$ converges.


Which NN would you choose to estimate a continuous function $f:\mathbb R^2 \rightarrow \mathbb R$? Suppose we want to estimate a continuous function $f:\mathbb R^2 \rightarrow \mathbb R$ based on a sample using a NN (around 1000 examples). This function is not bounded. Which architecture would you choose ? How many layers/neurons ? Which activation functions ? Which loss function ?
Intuitively, I would go with one hidden layer, 2 neurons, $L^2$ loss, and maybe the Bent identity for the output and a sigmoid in the hidden layer ?
What are the advantages of doing something "fancier" than that ?
Would you also have chosen to use a NN for this job or would you have considered a regression SVM for example or something else (knowing that precision is the goal)?

It depends on the complexity of your problem. $\mathbb{R}^2 \rightarrow \mathbb{R}^1$ looks simple, but I can give you some nonsense complicated examples that need a deep network. So, the complexity of the problem sets the number of layers and neurons. The kind of problem will determine the architecture of your network (if it needs memory or not). In most cases, the mean squared error is ok. However, for the activation function, I would go with the ReLU.
If the SVM is good enough for your problem, then go with it. Your question is general and an exact answer needs more information about the problem.


Which algorithm can be used for extracting text patterns in tabular data? I am working with tabular data that is similar to the below:

Name
Phone Number
ISO3 Country
Amount
Email
...
...
Outcome
Possible Reason

Leona Sunfurry
(555)-555-5555
United States
58.96
leo_sun@gmail.com
...
...
0
Not ISO3 country

Diana Moonglory
(333)-555-5555
USA
8.32
di.moon@gmail.com
...
...
1

Fiora Quik
(111)-555-5555
FRA
0.35
null
...
...
1

Darius Guy
12345678901234
CAN
555.01
null
...
...
0
Too many digits in phone

LULU
(333)-555-5555
CAN
0.00
null
...
...
0
Odd name format

Eve K.
(111)-555-5555
FRA
69.25
e.k@gmail.com
...
...
1

Lucian Light
(999)-555-5555
ENG
65.00
null
...
...
1

Lux D.
(333)-555-5555
USA
11.64
test@test.com
...
...
1

Jarvin Crown
(333)-555-5555
USA
1357.13
j4@gmail.com
...
...
0
Unknown reason

The table contains information about users. Some of the fields are user-generated while others are generated by the program (like device location, amount, etc.). When this data is collected, it is sent to third parties (we will say a bank). Sometimes the bank rejects the data and it is not good for our users. The rejection could have happened because the user did not input the data correctly or the banks did not like how a field is formatted despite the data being correct and acceptable to other banks.
So we want to find the fields that are causing the most errors and how to fix the issue.
Does it make sense to do pattern recognition on the values to find the reason why the row was rejected? It would need to be an alpha-numeric type of algorithm, it seems.
We know the outcomes from the bank which is labeled as Outcome.  Although we have labeled data, it still feels like we need an unsupervised learning algorithm because we do not have labels on why the rows of data were rejected.
Does anyone know what type of algorithm would be best? Any feedback would be appreciated!

You should first segregate the rejected samples. You can use then use string matching or something more complex (like creating embeddings and then, taking L2 distance between them) between the different field names you have and the comment for rejection. Whichever field gets the highest score, you increase the rejection count for that field. In the end, you will have a tally of who is your biggest enemy.
You can create some rules which prevent injection of wrong data (like your password should be 7 characters long or something along these lines) or post-process your entries to match a uniform format.


Is the summation of consistent heuristic functions also consistent? Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?

Is there any proof or counterexample to show the contradiction?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.

s --1-- g

Assume that $h_0$ and $h_1$ are perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an undirected graph the heuristic will be inconsistent because $|h(s)-h(g)| > d(s, g)$.

If you'd like to understand the conditions for the sum of heuristics to be consistent and admissible, I would look at the work on additive PDB heuristics.


Programming Collective Intelligence Is Programming Collective Intelligence by Toby Segaran a good book to enter in the AI and neural networks world for a novice?

I read the second chapter in that book for my project on recommendation systems. It is an awesome book and it starts by addressing concepts from the basics( At least chapter 2 was like that). Book explains concepts with python. You will need a bit of knowledge on python basics . The book transits slowly from beginner to an intermediate level. Hope this answers your question. I would recommend it.


What is the difference between asymmetric and depthwise separable convolution? I have recently discovered asymmetric convolution layers in deep learning architectures, a concept which seems very similar to depthwise separable convolutions.

Are they really the same concept with different names? If not, where is the difference? To make it concrete, what would each one look like if applied to a 128x128 image with 3 input channels (say R,G,B) and 8 output channels?

NB: I cross-posted this from stackoverflow, since this kind of theoretical question is maybe better suited here. Hoping it is OK...

They are not the same thing.

asymmetric convolutions work by taking the x and y axes of the image separately. For example performing a convolution with an $(n \times 1)$ kernel before one with a $(1 \times n)$ kernel.

On the other-hand depth-wise separable convolutions separate the spatial and channel components of a 2D convolution. It will first perform the $(n \times n)$ convolution on each channel separately (full kernel shape will be $(n \times n \times 1)$ rather than $(n \times n \times k)$ where $k$ is the number of channels in the previous layer) before doing a $(1 \times 1)$ convolution to learn a relationship between the channels (full kernel size for that being $(1 \times 1 \times k)$)


Can CNNs be made robust to tricks where small changes cause misclassification? I while ago I read that you can make subtle changes to an image that will ensure a good CNN will horribly misclassify the image. I believe the changes must exploit details of the CNN that will be used for classification. So we can trick a good CNN into classifying an image as a picture of a bicycle when any human would say it's an image of a dog. What do we call that technique, and is there an effort to make image classifiers robust against this trick?

These are known as adversarial attacks, and the specific examples that are misclassified are known as adversarial examples.
There is a reasonably large body of work on finding adversarial examples, and on making CNNs more robust (i.e. less prone to these attacks). An example is the DeepFool algorithm, which can be used to find perturbations of data which would cause the label to change.
There are several techniques in the literature which are used to fight against adversarial attacks. Here is a selection:

Augmenting the training data with various random perturbations. This is intended to make the model more robust to the typical adversarial attack where random noise is added to an image. An example of this approach is discussed in [1].

Constructing some sort of model to "denoise" input before feeding into the CNN. An example of this is Defense-GAN [2], which uses a generative adversarial model which models the "true" image distribution and finds an approximation of the input closer to the real distribution.

References
[1] Ian J. Goodfellow, Jonathon Shlens & Christian Szegedy. Explaining and Harnessing Adversarial Examples. ICLR (2015). URL.
[2] Pouya Samangouei, Maya Kabkab, Rama Chellappa. Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models. ICLR (2018). URL.


Smallest possible network to approximate the $sin$ function The main goal is: Find the smallest possible neural network to approximate the $sin$ function.
Moreover, I want to find a qualitative reason why this network is the smallest possible network.
I have created 8000 random $x$ values with corresponding target values $sin(x)$. The network, which am currently considering, consists of 1 input neuron, 3 neurons in two hidden layers, and 1 output neuron:
Network architecture:

The neural network can be written as function
$$y = sig(w_3 \cdot sig(w_1 \cdot x) + w_4 \cdot sig(w_2 \cdot x)),$$
where $\text{sig}$ is the sigmoid activation function.
$tanh$ activation function:
When I use $tanh$ as an activation function, the network is able to hit the 2 extrema of the $sin$ function:
$tanh$ activation function" />
Sigmoid activation function:
However, when I use the sigmoid activation function $\text{sig}$, only the first extremum is hit. The network output is not a periodic function but converges:

My questions are now:

Why does one get a better approximation with the $tanh$ activation function? What is a qualitative argument for that?
Why does one need at least 3 hidden neurons? What is the reason that the approximation with $tanh$ does not work anymore, if one uses only 2 hidden neurons?

I really appreciate all your ideas on this problem!

Before anything, the function you have wrote for the network lacks the bias variables (I'm sure you used bias to get those beautiful images, otherwise your tanh network had to start from zero).
Generally I would say it's impossible to have a good approximation of sinus with just 3 neurons, but if you want to consider one period of sinus, then you can do something. for clarity look at this picture:

I've write the code for this task in colab and you can find it here, and you can play with it if you want.
If you run the network several times you may get different results (because of different initializations) and you can see some of them at the Results section of the link above. What you showed us in the images above are just two possibilities. But it's interesting that you can get better results with tanh rather than sigmoid and if you want to know why, I highly recommend you to look at this lecture of CS231n. In summary it's because tanh has the negative part and the network can learn better with it.
But actually their power of approximation are almost similar because 2*sigmoid(1.5*x) - 1 almost looks the same as tanh(x) and you can find it by looking the picture below:

So why you can't get the same results as tanh? that's because tanh suits the problem better and if the network wants to get the same result as tanh with sigmoid it should learn their transformation parameters and learning these parameters makes the learning task harder. So It's not impossible to get the same result with sigmoid but it's harder. And to show you that its possible, I have set the parameters of the network using sigmoid manually and got the result below (you can get better results if you have more time):

At last if you want to know why you can't get the same result with 2 neurons instead of 3 neurons, it's better to understand what does the network do with 3 neurons.
If you look at the output of the first layer, you may see something like this (which are outputs of two neurons it has):

Then the next layer gets the difference between the output of these two neurons (which is like sinus) and applies sigmoid or tanh to it, and that's how you get a good result. But when you have just one neuron in the first layer, you can't imagine some scenario like this and approximating one period of sinus is out of it's ability (underfitting).


How are exploding numbers in a forward pass of a CNN combated? Take AlexNet for example:

In this case, only the activation function ReLU is used. Due to the fact ReLU cannot be saturated, it instead explodes, like in the following example:

Say I have a weight matrix of [-1,-2,3,4] and inputs of [ReLU(4), ReLU(5), ReLU(-2), Relu(-3)]. The resultant matrix from these will have large numbers for the inputs of ReLU(4) and ReLU(5), and 0 for ReLU(-2) and ReLU(-3). If there are even just a few more layers, the numbers are quick to either explode or be 0.

How is this typically combated? How do you keep these numbers towards 0? I understand you can take subtract the mean at the end of each layer, but for a layer that is already in the millions, subtracting the mean will still result in thousands.

The most effective way to prevent both the forward and backward propagation of exploding is keeping the weights in a small range. The main way this is accomplished is through their initialization.

For example in the case of He initialization, the authors show (given some assumptions) that the variance of the output of the final layer $L$ of the network is:

$$
Var[y_L] = Var[y_1] \left( \prod_{i=2}^L{\frac{1}{2} \, n_l \, Var[w_l]} \right)
$$

where $n_l$ and $w_l$ are the number of connections and weights of layer $l$. In order to keep the outputs from exploding the product above should not exponentially magnify its inputs. In order to do this the authors elect to initialize the weights so that:

$$
\frac{1}{2} \, n_l \, Var[w_l] = 1
$$

Now this is helps keeping the outputs from exploding. They then go and prove that the same strategy helps preventing the gradients from exploding.

Another similar strategy is the so-called Glorot (or Xavier) Initialization.
These techniques are extremely effective in helping the models converge!


In CNNs, why do we sum the filter derivatives w.r.t the loss function to get the final gradient? In a Convolutional Neural Network, unlike the fully connected layers, the same filter is used multiple times on the input while convolving - so during backpropagation, we get multiple derivatives for the filter parameters w.r.t the loss function. My question is, why do we sum all the derivatives to get the final gradient? Because, we don't sum the output of the convolution during forward pass. So, isn't it more sensible to average them? What is the intuition behind this?
PS: although I said CNN, what I'm actually doing is correlation for simplicity of learning.

I really liked the question. Yes, we sum over derivatives. First of all think what backpropagation is trying to do: finding the affect of each parameter on the loss.
So as you said:

the same filter is used multiple times on the input while convolving

meaning that each kernel affects the final loss in several ways, so those affects should be summed together, not averaged.


Is there a reliable website about artificial intelligence that is frequently updated? Is there a reliable website about artificial intelligence that is updated regularly?

Like there is now TensorFlow 2.0 and they write some information about it. Or a magazine which can be subscribed. So a site where all news of AI are collected to be always up to date.

For sites, https://towardsdatascience.com/ maybe a good choice. The articles on there is about AI. You can read a lot of articles about state-of-the-art AI networks there. You can also subscribe to their newsletter for emails everyday on new AI discoveries. However, as stated by @DuttaA, take the articles with caution. The articles may or may not be entirely true as they are written by the community. Choose articles with large number of likes to read.

The YouTube channel two minutes paper is also a great resource. The channel posts videos about AI and also computer science periodically, and the content is easy to understand and enjoyable.

Reminder: for the towards data science site, you should disable cookies for it so that there will not be a limit on how many articles you read.

Hope I can help you and have a nice day


Why does reinforcement learning using a non-linear function approximator diverge when using strongly correlated data as input? While reading the DQN paper, I found that randomly selecting and learning samples reduced divergence in RL using a non-linear function approximator (e.g a neural network).
So, why does Reinforcement Learning using a non-linear function approximator diverge when using strongly correlated data as input?

It is not so much the problem of using Reinforcement Learning to train the neural networks, it is the assumptions made about the data given to standard Neural Networks. They are not capable of handling strongly correlated data which is one of the motivations for introducing Recurrent Neural Networks, as they can handle this correlated data well.


How does novelty search work? In this article, the author claims that guiding evolution by novelty alone (without explicit goals) can solve problems even better than using explicit goals. In other words, using a novelty measure as a fitness function for a genetic algorithm works better than a goal-directed fitness function. How is that possible?

As explained in an answer to this AI SE question, GAs are 'satisficers' rather than 'optimizers' and tend not to explore 'outlying' regions of the search space. Rather, the population tends to cluster in regions that are 'fairly good' according to the fitness function.

In contrast, I believe the thinking is that novelty affords a kind of dynamic fitness, tending to push the population away from previously discovered areas.


How can I minimize the number of answers that are relevant to a machine learning model? Problem:

We have a fairly big database that is built up by our own users.
The way this data is entered is by asking the users 30ish questions that all have around 12 answers (x, a, A, B, C, ..., H). The letters stand for values that we can later interpret.

I have already tried and implemented some very basic predictors, like random forest, a small NN, a simple decision tree etc.

But all these models use the full dataset to do one final prediction. (fairly well already).

What I want to create is a system that will eliminate 7 to 10 of the possible answers a user can give at any question. This will reduce the amount of data we need to collect, store, or use to re-train future models.

I have already found several methods to decide what are the most discriminative variables in the full dataset.  Except, when a user starts filling the questions I start to get lost on what to do. None of the models I have calculate the next question given some previous information.

It feels like I should use a Naive Bayes Classifier, but I'm not sure. Other approaches include recalculating the Gini or entropy value at every step. But as far as my knowledge goes, we can't take into account the answers given before the recalculating.

You don't need to re-train on the fly. What you're looking for is an embedded feature selection algorithm, and even more precisely, one that minimizes the number of responses required.

I think this might be one of the rare cases where genetic and evolutionary approaches are the obviously correct choice.

Genetic Programming is a technique for finding models that are simply computer programs. You generate a bunch of computer programs at random, and then breed the "better" ones together. Repeating this process over time leads to highly optimized programs.

A nice feature of GP is that it is extremely flexible when picking what to optimize. So instead of "better" meaning just "more accurate", "better" can mean the sum of accuracy and $\frac{1}{\#answers\_used}$. The algorithm works the same way, and, with carefully chosen rewards, you may be able to get the best of both worlds.

There are lots of variations on this. I would probably start with a simple toolkit like EJC, and standard, boring, genetic programming.

There are specialized techniques for things like your problem too, but you'll probably get 80% of the benefit without needing to pursue them.


Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$? I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$.

While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches and goes after one according to the heuristic function. It doesn't expand the rest like BFS. Perceiving this as similar to what depth-first search does, I understand that the worst time complexity is $\mathcal{O}(b^m)$. But I don't understand the space complexity.

Shouldn't it be the same as DFS, $\mathcal{O}(bm)$, since it only will be expanding $b*m$ nodes during the search in one path?

I was struggling with the same question. This is what I came up with after thinking it through.
With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and the children of these ancestors. Which translates in m*b where m is the max path length (so max number of ancestors) and b is the branching factor (number of children per ancestor).
With greedy search when you backtrack you can jump to any evaluated but unexpanded node, you passed going down on paths earlier. So the algorithm, when backtracking, can make pretty random jumps throughout the tree leaving lots of sibling nodes unexpanded. You will have to remember the value of the evaluation function for all these unexpanded nodes though because possibly they are next up when backtracking occurs. So in a theoretical very worst-case scenario that could mean that almost the whole tree needs to be remembered. Hence O(b^m).
I know there are still gaps in the reasoning but intuitively this makes me understand it best.


Should I train different models for detecting subsets of objects? Suppose we have $1000$ products that we want to detect. For each of these products, we have $500$ training images/annotations. Thus we have $500,000$ training images/associated annotations. If we want to train a good object detection algorithm to recognize these objects (e.g. YOLO) would it be better to have multiple detection models? In other words, should we have 10 different YOLO models where each YOLO model is responsible for detecting 100 products? Or is it good enough to have one YOLO model that can detect all 1000 products? Which would be better in terms of mAP/recall/precision?

This is called decomposition of multi-class classifier. Your proposed method is called one vs all.

  One vs. all provides a way to leverage binary classification. Given a classification problem with $N$ possible solutions, a one-vs.-all solution consists of $N$ separate binary classifiers—one binary classifier for each possible outcome. During training, the model runs through a sequence of binary classifiers, training each to answer a separate classification question.

Source: https://developers.google.com/machine-learning/crash-course/multi-class-neural-networks/one-vs-all.

According to this article. The author of the article did experiments on SVM on 8 different benchmark problems. According to the results, this method is sometimes as good as others, but usually not the best. It is also never substantially better than any other method. The article also stated that the best method is usually problem dependent.

Also, this method will decrease inference speed a lot, and used substantial amount of GPU memory. According to the source, it does not improve performance a lot, so you best bet for getting a higher performance is probably to use a different model architecture, for example the FPN FRCN, which is stated in the YOLO v3 paper having the best performance, but not fast inference speed. YOLOv3 is designed to have a fast inference speed, to provide real time object detection system, so for performance you should probably use other model architecture instead.


Can someone explain me what does this loss curve says? I was training a CNN model on TensorFlow. After a while I came back and saw this loss curve:

The green curve is training loss and the gray one is validation loss. I know that before epoch 394 the model in heavily overfitted, but I have no idea what happened after that.
Also, this is accuracy curves if it helps:

I'm using categorical cross-entropy and this is the model I am using:

and here is link to PhysioNet's challenge which I am working on: https://physionet.org/content/challenge-2017/1.0.0/

Follow this answer from StackOverflow, I think your problem related to the second cases where your loss gets Nan value.
Maybe you should try to use the larger datatype (for example float 16 -> float 32)


What is wrong with equation 7.3 in Sutton & Barto's book? Equation 7.3 of Sutton Barto book:
$$\text{Equation: } max_s|\mathbb{E}_\pi[G_{t:t+n}|S_t = s] - v_\pi| \le \gamma^nmax_s|V_{t+n-1}(s) - v_\pi(s)| $$
$$\text{where }G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + .....+\gamma^{n-1} R_{t+n} + \gamma^nV_{t+n-1}(S_{t+n})$$
Here $V_{t+n-1}(S_{t+n})$ is the estimate of $V_\pi(S_{t+n})$
But the Left Hand Side of the above equation should be zeros as, for any state s, $G_{t:t+n}$ is an unbiased estimate of $v_\pi(s)$ hence $\mathbb{E}_\pi[G_{t:t+n}|S_t = s] = v_\pi(s)$.

In general, $\mathbb{E}_\pi[G_{t:t+n}|S_t = s] \neq v_\pi(s)$. $v_\pi(s)$ is defined as $\mathbb{E}_\pi[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s]$, so you should be able to see why the two are not equal when the LHS is an expectation of the $n$th step return. They would only be equal as $n \rightarrow \infty$.