Update in REINFORCE algorithm - step-wise or episode-wise? REINFORCE is a Monte Carlo policy gradient algorithm, which updates weights (parameters) of policy network by generating episodes. Here's a pseudo-code from Sutton's book (which is same as the equation in Silver's RL note):

When I try to implement this with my own problem, I found something strange. Here's implementation from Pytorch's official GitHub:

def finish_episode():
    R = 0
    policy_loss = []
    returns = []
    for r in policy.rewards[::-1]:
        R = r + args.gamma * R
        returns.insert(0, R)
    returns = torch.tensor(returns)
    returns = (returns - returns.mean()) / (returns.std() + eps)
    for log_prob, R in zip(policy.saved_log_probs, returns):
        policy_loss.append(-log_prob * R)
    optimizer.zero_grad()
    policy_loss = torch.cat(policy_loss).sum()
    policy_loss.backward()
    optimizer.step()
    del policy.rewards[:]
    del policy.saved_log_probs[:]

I feel like there's a difference between the above two. In Sutton's pseudo-code, the algorithm updates $\theta$ for each step $t$, while the second code (PyTorch's one) accumulate loss and update $\theta$ with the summation, i.e. after each episode.
I tried to search other implementation of REINFORCE, and I found that most of the implementations follow the second form, update after each generated episodes.

To check whether both give the same result, I changed the second code as

def finish_episode():
    R = 0
    policy_loss = []
    returns = []
    for r in policy.rewards[::-1]:
        R = r + args.gamma * R
        returns.insert(0, R)
    returns = torch.tensor(returns)
    returns = (returns - returns.mean()) / (returns.std() + eps)
    for log_prob, R in zip(policy.saved_log_probs, returns):
        optimizer.zero_grad()
        loss = -log_prob * R
        loss.backward()
        optimizer.step()

...

and run it, which gives different result (if my code has no problem).
So they are not the same, and I think the last one is more close to the original pseudo-code of REINFORCE. What am I missing now? Is it okay because the results are approximately same? (I'm not sure about this claim)

However, in some sense, I think Pytorch's implementation is the right version of REINFORCE. In Sutton's pseudo-code, episode is generated first, so I think $\theta$ shouldn't be updated at each step and should be updated after the total loss is computed. If $\theta$ is updated at each step, then such $\theta$ might be different with the original $\theta$ that used to generate the episode.

Hi Seewoo Lee and welcome to our community!

The essence of your observation is that Sutton's version of REINFORCE is taking into consideration all of the trajectory to compute the returns while in the pytorch version only the future is taken into consideration, hence going in reverse to sum the future rewards and ignore the previous rewards. The consequence is that future actions are not punished for early mistakes. The guys at OpenAI refer to this as reward-to-go but personally, I find that it resembles Monte Carlo On Policy Control without Exploring Starts or First Visit from Sutton's book.

You can find more on REINFORCE and Policy Gradient in Spinning Up RL: Part3: Intro to policy gradient -  Don't let the past distract you.

Also, something to note is that even in Sutton's version, the whole trajectory is unrolled, i.e. the episode completes, and then the weights get updated. Otherwise it stops being  a Monte Carlo Method and it becomes a TD method. In addition, you can't make a change on a single point because sampling is a non differentiable operation, instead, the gradient is estimated by collecting a lot of trajectories.


If loss reduction means model improvement, why doesn't accuracy increase? Problem Statement

I've built a classifier to classify a dataset consisting of n samples and four classes of data. To this end, I've used pre-trained VGG-19, pre-trained Alexnet and even LeNet (with cross-entropy loss). However, I just changed the softmax layer's architecture and placed just four neurons for that (because my dataset includes just four classes). Since the dataset classes have a striking resemblance to each other, this classifier was unable to classify them and I was forced to use other methods.
During the training section, after some epochs, loss decreased from approximately 7 to approximately 1.2, but there were no changes in accuracy and it was frozen on 25% (random precision). In the best epochs, the accuracy just reached near 27% but it was completely unstable.

Question

How is it justifiable? If loss reduction means model improvement, why doesn't accuracy increase? How is it possible to the loss decreases near 6 points (approximately from 7 to 1) but nothing happens to accuracy at all?

Loss reduction means model improvement, it does not in the wrong setup, wher random choise produces least loss. So it is some critical setup error. What classes do you have?
I got also thet recently experimenting with an encoder with too narrow coding layer - it just EQUILIZES the output with average values cause this state has minimum loss.


Why can't MLPs perform non-linear regression and classification? In this page it's told:

  In Single Perceptron / Multi-layer Perceptron(MLP), we only have linear separability because they are composed of input and output layers(some hidden layers in MLP)

What does it mean? I thought the MLP was a non-linear classifier. Could you explain it to me?

In Single Perceptron / Multi-layer Perceptron(MLP), we only have linear separability because they are composed of input and output layers(some hidden layers in MLP)

This is wrong.

A multi-layer perceptron (i.e. a feed-forward neural network) with non-linear activation functions can perform non-linear classification and regression. In fact, an MLP with one hidden layer with an arbitrary number of hidden nodes, each of them with a sigmoid (which is a non-linear function), can approximate any continuous function (up to an approximation error).

On the other hand, perceptrons can't do that. They perform only linear classification/regression.

  I thought the MLP was a non-linear classifier.

You're right, unless the MLP only uses linear activation functions. In that case, it won't be able to perform non-linear classification/regression.

(P.S.: I suggest you always question the truth and correctness of what you read on the web, especially, on sites like Medium, as you actually did!)


How do updates in SARSA and Q-learning differ in code? The update rules for Q-learning and SARSA each are as follows:

Q Learning:

$$Q(s_t,a_t)←Q(s_t,a_t)+α[r_{t+1}+γ\max_{a'}Q(s_{t+1},a')−Q(s_t,a_t)]$$

SARSA:

$$Q(s_t,a_t)←Q(s_t,a_t)+α[r_{t+1}+γQ(s_{t+1},a_{t+1})−Q(s_t,a_t)]$$

I understand the theory that SARSA performs 'on-policy' updates, and Q-learning performs 'off-policy' updates.

At the moment I perform Q-learning by calculating the target thusly:

target = reward + self.y * np.max(self.action_model.predict(state_prime))

Here you can see I pick the maximum for the Q-function for state prime (i.e. greedy selection as defined by maxQ in the update rule). If I were to do a SARSA update and use the same on-policy as used when selecting an action, e.g. ϵ-greedy, would I basically change to this:

if np.random.random() < self.eps:
    target = reward + self.y * self.action_model.predict(state_prime)[random.randint(0,9)]
else:
    target = reward + self.y * np.max(self.action_model.predict(state_prime))

So sometimes it will pick a random future reward based on my epsilon greedy policy?

Picking actions and making updates should be treated as separate things. For Q-learning you also need to explore by using some exploration strategy (e.g. $\epsilon$-greedy).

Steps for Q-learning:
1) initialize state $S$
For every step of the episode:
2) choose action $A$ by some exploratory policy (e.g. $\epsilon$-greedy) from state $S$
3) take action $A$ and observe $R$ and $S'$
4) do the update $Q(S, A) = Q(S, A) + \alpha(R + \gamma*\max_aQ(S', a) - Q(S, A))$
5) update the state $S = S'$ and keep looping from step 2 until the end of episode

Steps for Sarsa:
1) initialize state $S$
2) initialize first action $A$ from state $S$ by some exploratory policy (e.g. $\epsilon$-greedy)
For every step of the episode:
3) take action $A$ and observe $R$ and $S'$
4) choose action $A'$ from state $S'$ by some exploratory policy (e.g. $\epsilon$-greedy)
5) do the update $Q(S, A) = Q(S, A) + \alpha(R + \gamma * Q(S', A') - Q(S, A))$
6) update state and action $S = S'$, $A = A'$ and keep looping from step 3 until end of the episode


What should the range of the output layer be when performing classification? I am working on a MLP neural networks, using supervised learning (2 classes and multi-class classification problems). For the hidden layers, I am using $\tanh$ (which produces an output in the range $[-1, 1]$) and for the output layer a softmax (which gives the probability distribution between $0$ and $1$). As I am working with supervised learning, should be my targets output between 0 and 1, or $-1$ and $1$ (because of the $\tanh$ function), or it does not matter?

The loss function is quadratic (MSE).

For this particular classification problem, I would recommend you using a softmax function whose output range is [0,1].
The sum of all outputs should be 1, so an advantage of using a softmax function is that you get a percentage of how confident the network is in this classification.

Side note: As DuttaA has commented, cross entropy loss is a better loss function than the quadratic mean squared error.


96.91% accuracy on MNIST after 2 hours of training using custom made neural net library. Ways to improve? I wanted to understand back-propagation so I made a basic neural network library. I used momentum, with learning rate = $0.1$, beta = $0.99$, epochs = $200$, batch size = $10$, loss function is cross entropy and model structure is $784$, $64$, $64$, $10$ and all layers use sigmoid. It performed terribly at first, so I initialized all the weights and biases in the range $[10^{-9}, 10^{-8}]$ and it worked. I am quite new to deep learning and I find TensorFlow doesn't seem as friendly to beginners who want to play around with hyper-parameters. How do you find the right hyper-parameters? I trained it on 100 digits (which took 10 minutes), tweaked hyper-parameters, chose the best set and trained the model using that set on the entire data set of $60,000$ images. I also found that halving the epochs and doubling the training set size gave better results. Are there fool proof heuristics to find good hyper-parameters? What is the best set of hyper-parameters (without regularization, dropout, etc) for MNIST digits? Here is the code for those who want to take a look.

There is no singular best set of hyperparameters. Even more, there is no real search algorithm for hyperparameters. You can do a grid search, but this obviously will take some time. Most people either do that or will try to handpick their parameters.
A few other things to note: Initializing your weights at [10^9,10^8] doesn't seem right to me. They should be centered and close to zero initially. You should also take a look again how to set up train/test/val splits.


Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation? In equation 3.17 of Sutton and Barto's book:

$$q_*(s, a)=\mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s, A_t = a]$$

$G_{t+1}$ here have been replaced with $v_*(S_{t+1})$, but no reason has been provided for why this step has been taken.

Can someone provide the reasoning behind why $G_{t+1}$ is equal to $v_*(S_{t+1})$?

Can someone provide the reasoning behind why $G_{t+1}$ is equal to $v_*(S_{t+1})$?

The two things are not usually exactly equal, because $G_{t+1}$ is a probability distribution over all possible future returns whilst $v_*(S_{t+1})$ is a probability distribution derived over all possible values of $S_{t+1}$. These will be different distributions much of the time, but their expectations are equal, provided the conditions of the expectation match.

In other words,

$$G_{t+1} \neq v_*(S_{t+1})$$

But

$$\mathbb{E}[G_{t+1}] = \mathbb{E}[v_*(S_{t+1})]$$

. . . when the conditions that apply to the expectations on each side are compatible. The relevant conditions are

Same initial state or state/action at given timestep $t$ (or you could pick any earlier timestep)
Same state progression rules and reward structure (i.e. same MDP)
Same policy

More details

The definition of $v(s)$ can be given as

$$v(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$$

If you substitute step s' and index $t+1$ you get

$$v(s') = \mathbb{E}_\pi[G_{t+1} \mid S_{t+1} = s']$$

(This is the same equation, true by definition, the substitution just shows you how it fits).

In order to put this into equation 3.17, you need to note that:

It is OK to substitute terms inside an expectation if they are equal in separate expections, amd  the conditions $c$ and $Y$ apply to both (or are irrelevant to either one or both). So if for example $\mathbb{E}_c[Z] = \mathbb{E}_c[X \mid Y]$ where $X$ and $Z$ are random variables, and you know $Z$ is independent of $Y$ then you can say $\mathbb{E}_c[W + 2X \mid Y] = \mathbb{E}_c[W + 2Z \mid Y]$ even if $X$ and $Z$ are different distributions.
$A_{t+1} = a'$ does not need to be specified because it is decided by the same $\pi$ in both $q(s,a)$ and $v(s')$, making the conditions on the expectation compatible already. So the condition of following $\pi$ is compatible with $\mathbb{E}_\pi[G_{t+1} \mid S_{t} = s, A_{t}=a] = \mathbb{E}_\pi[v_*(S_{t+1}) \mid S_{t} = s, A_{t}=a]$
The expectation over possible $s'$ in $\mathbb{E}_\pi[v_*(S_{t+1})|S_t=s, A_t=a] = \sum p(s'|s,a)v_*(s')$ is already implied by conditions on the original expectation that the functions are evaluating the same environment - something that is not usually shown in the notation.

Also worth noting, in 3.17 $\pi$ is the optimal policy $\pi^*$, but actually the equation holds for any fixed policy.


Best way to train Neural Network for Voice Commands? I want to build a Voice Assistance using Tensorflow, Like Google Assistance, So that I can give commands like:

Open Camera
Send Message
Play Music
ETC

I know I can use pre-trained model for Voice Recognition but this is not my problem. If I know correctly, What Neural Network does it learn from your input and output and creates a best algorithms.

So I want to know Is it possible to somehow train my network for my commands so that I don't have to HARD-CODED them because it is hard to remember so many command?

Is Google also Hard-Coded the commands for Google Voice Assistance?

Sorry, If I'm unable to explain this to you :P

What Neural Network does it learn from your input and output and creates a best algorithms.

This is inaccurate. A neural network is a function approximator, so it approximates an unknown function. However, it does so in many cases by learning from your input and output(as in the case of supervised learning). The function your approximating would here for example be the function that maps a certain soundwave input to "open camera", etc.

The problem with supervised learning is that you need massive datasets to accurately approximate the target function - luckily for Google they have such datasets and resources available.

  Is Google also Hard-Coded the commands for Google Voice Assistance?

No, because that would not generalize well over multiple languages/accents/background noise, etc. It is therefor that neural networks as function approximators have had such a large impact over the last years - they generalize well.
If you remember when the first "voice assistance" products came out, they rarely functioned - this was often due to them being "hard coded", with only static measures for noise-suppression.


XOR Neural Network gets stuck in training I'm trying to create a neural network to simulate a XOR gate.
Here's my dataset:
╔════════╦════════╗
║ x1, x2 ║ y1, y2 ║
╠════════╬════════╣
║  0, 0  ║  0, 1  ║
║  0, 1  ║  1, 0  ║
║  1, 0  ║  1, 0  ║
║  1, 1  ║  0, 1  ║
╚════════╩════════╝

And my neural network:

I use logistic loss to get the error between target $y_{k}$ and output $\hat{y}_{k}$:
$$ E(y_{k}, \hat{y}_{k}) = - y_{k} \cdot log(\hat{y}_{k}) + (1 - y_{k}) \cdot log(1 - \hat{y}_{k}) $$
And then use the chain rule to update the weights. For example weight $w_{3}$'s contribution to the error is:
$$ \sum_{k=1}^{2} \frac{\partial E(y_{k}, \hat{y}_{k})}{\partial w_{3}} = \sum_{k=1}^{2} \left(\frac{\partial E(y_{k}, \hat{y}_{k})}{\partial \hat{y}_{k}} \cdot \frac{\partial s_{k}}{\partial c_{1}}\right) \cdot \frac{\partial c_{1}}{\partial w_{3}} $$
Which in developed form is:
$$ \sum_{k=1}^{2} \frac{\partial E(y_{k}, \hat{y}_{k})}{\partial w_{3}} = \left( \left( - \frac{y_{1}}{\hat{y}_{1}} + \frac{1 - y_{1}}{1 - \hat{y}_{1}} \right) \cdot \hat{y}_{1} \cdot (1 - \hat{y}_{1}) + \left( - \frac{y_{2}}{\hat{y}_{2}} + \frac{1 - y_{2}}{1 - \hat{y}_{2}} \right) \cdot (- \hat{y}_{2}) \cdot\frac{c_{1}}{c_{1} + c_{2}} \right) \cdot s_{0} $$
My issue is that after a couple epochs of training on the entire dataset, the network always outputs:
$$ \hat{y}_{1} = \hat{y}_{2} = 0.5 $$
What am I doing wrong?

One Neuron on its own can only solve linearly separable problems.
You need a combination of Neurons to solve non-linearly separable problems.
For the XOR case, you need at least 2 Neuron at the first layer, and 1 Neuron at the Output layer to properly classify it.
Keep in mind sometimes the 3 Neuron network might get stuck in a local minima as well, you will need some luck in the random initialization of weights.
Using the right seed during the random initialization of weights can help converge, and some other seed will only result in a stuck network.


What does "In each generation, 25% of offspring resulted from mutation without crossover" mean in the context of NEAT? I am reading through the NEAT paper. In parameter settings, page 15, there is:

  In each generation, 25% of offspring resulted from mutation without crossover.

What does it mean?

In genetic algorithms, mutation without crossover simply means that part of the population is randomly changed. In this case this is applied to 25% of the population.

The remaining 75% either remain unchanged (generally the best performing specimen), or will be combined with other specimen (using crossover). It's a bit more complex here, as the genome is connecting weights in networks, and they use 'species', where certain individuals are treated as separate groups from the rest of the population.


Why is awareness of itself such a point when speaking about AI? Why is awareness of itself such a point when speaking about AI? Does it always mean a starting point for apocalyptic nightmares to occur when such a level is reached or is it just a classical example about what could be a really abstract thing that machine cannot easily posses?

I would sleep my nights far more calmfully if the situation was the latter, and I understand the first does not automatically  happen. The main thing I would like to discover is the starting point - which approach came first historically? Or is there another view point in the historical first occurrence of self awareness term?

Neil Slater has it right, there most probably is no fear of AI self awareness as some starting point of evil series of things to happen.

Wikipedia [1] puts self awareness talks to sci-fi section, among stories, not a real thing. Self-awareness is among a list of terms that tries to make machines or aliens similarly human than ordinary people and uses that as a method of story telling.

Self-awareness or other humanlike skills that we posses that the machines don't have yet and will not have in near future can twist minds and make a seed of conspiracy theories, but at least the exhaustive Wikipedia overview on topic did not speak anything about AI.

Maybe the concept of humanlike behaviour materialises on our minds as a term of self-awareness but my source puts the origin to different category.

[1] https://en.m.wikipedia.org/wiki/Self-awareness


How is the word embedding represented in the paper "Recurrent neural network based language model"? I'm reading "Recurrent neural network based language model" of Mikolov et al. (2010). Although the article is straight forward, I'm not sure how word embedding $w(t)$ is obtained:

The reason I wonder is that in the classic "A Neural Probabilistic Language Model" Bengio et al. (2003) - they used separate embedding vector for representing each word and it was somehow "semi-layer", meaning - it haven't contains non-linearity, but they did update word embeddings during the back-propagation.

In Mikolov approach though, I assume they used simple one-hot vector, where each feature represent presence of each word. If we represent that's way single word input (like was in the Mikolov's paper) - that vector become all-zeros except single one.

Is that correct?

Input vector contains two concatenated parts. The low part represents the current word:

  word in time t encoded using 1-of-N coding [...] - size of vector x is
  equal to size of vocabulary V (this can be in practice 30 000-200 000) plus [...]

where, as you said, 1-of-N means (see here, 1-of-V):

  If you have a fixed-size vocabulary of symbols with V members in
  total, each input symbol can be coded as a vector of size V with all
  zeros except for the element corresponding to the symbol's order in
  the vocabulary, which gets a 1.

The high part of the input vector represents the current context:

  and previous context layer [...] Size of context (hidden) layer s is
  usually 30 - 500 hidden units.

  For initialization, s(0) can be set to vector of small values, like
  0.1

the article includes this expression:

  x(t) = w(t) + s(t - 1)

that I think better to write as:

  x(t) = w(t) || s(t - 1)

to made more visible the concatenation.

Finally, paper states some improvements that breaks the 1-to-N definition of the word (low) part, in order to reduce the size of the w vector:

  we merge all words that occur less often than a threshold (in the
  training text) into a special rare token.


how to normalize the state space for articulated robot environments? What is the common representation used for the state in articulated robot environments? My first guess is that it's a set of the angles of every joint. Is that correct? My question is motivated by the fact that one common trick that helps training neural nets in general is to normalize the inputs, like setting mean = 0 and std dev = 1, or scaling all the input values to $[0, 1]$, which could be easily done in this case too if all the inputs are angles in $[0, 2 \pi]$. But, what about distances? Is it common to, for example, use as input some distance of the agent to the ground, or a distance to some target position? In that case, the scale of the distances can be arbitrary and vary a lot. What are some common ways to deal with that?

This paper might provide some answers https://arxiv.org/pdf/1810.05762.pdf

For the observations / states they used not only angles, but also velocities, heights and positions (Table 2).

In 4.2 Learning algorithm you can see that they mention this, which is related to your question about normalization:

  Additionally, for stability we whiten the current observations by
  maintaining online statistics of mean and standard deviation from the
  history of past observations.


What is the difference between Attention Gate and CNN filters? Attention models/gates are used to focus/pay attention to the important regions. According to this paper, the authors describe that a model with Attention Gate (AG) can be trained from scratch. Then the AGs automatically learn to focus on the target.
What I am having trouble understanding is that, in the context of computer vision, doesn't a filter from the convolutional layers learn the region of interest?
The authors say that adding Attention Gate reduces complexity when compared with multi-stage CNNs. But the job a trained AG would do is the same as that of a filter in a convolutional layer that would lead to the correct output, right?

CNNs work by applying filters over the entire image. The same filter is applied at every pixel in the image. That is, the same weights are used at every pixel.
Note, when I say "at every pixel" this means across the spatial dimension HxW of the image. You can also have attention in the channel dimension. See for example Squeeze and Excitation: https://arxiv.org/pdf/1709.01507.pdf
While this is one of the strengths of CNNs, since it drastically reduces the number of parameters of a network, you can imagine that it may not make sense to treat every part of the image the same regardless of the content. This is what the attention gate is for.
By performing an element-wise multiplication of the output of a CNN layer with a gate tensor (typically clamped to the 0-1 range with a sigmoid) we can effectively down weigh or ignore features in certain areas of the image.
CNNs without AG can typically learn the same things but may need more channels and layers. Attention gates allow to treat filters differently depending on the content and hence make it easier to learn with less filters.
What you use as the attention tensor can vary. In the paper you referenced, the tensor was one of the input tensors of the convolutional layer. In this case, it is called self-attention. However, with attention in general this gate tensor may also come from other information such as another network.


How does artificial intelligence work in games? Artificial intelligence is present in many games, both current and older games. How can such intelligence understand what to do? I mean, how can it behave like a human in a game, allowing you to play against itself, or that AI plays against itself?

In games like Age of Empires, for example.

There are many different kinds of AI used in games; AI for historical board games (like chess or Go) tends to be much better than AI for computer games (such as Starcraft or Civilization), in large part because there's more academic interest in developing strategies for those games.

The basic structure of a game-playing AI is that it takes in game state inputs and outputs an action; typically, the internals also contain some sort of goal and some sort of future prediction.

But beyond that, there's tremendous amounts of variability. Some AI are little more than scripted reflexes, some are built like control systems, some do actual optimization and forward thinking.

Getting into the details of how the many different approaches work is probably beyond the scope of this site, though.


Why should the baseline's prediction be near zero, according to the Integrated Gradients paper? I am trying to understand Intagrated Gradients, but have difficulty in understanding the authors' claim (in section 3, page 3):

For most deep networks, it is possible to choose a baseline such that the prediction at the baseline is near zero ($F(x') \approx 0$). (For image models, the black image baseline indeed satisfies this property.)

They are talking about a function $F : R^n \rightarrow [0, 1]$ (in 2nd paragraph of section 3), and if you consider a deep learning classification model, the final layer would be a softmax layer. Then, I suspect for image models, the prediction at the baseline should be close to $1/k$, where $k$ is the number of categories. For CIFAR10 and MNIST, this would equal to $1/10$, which is not very close to $0$. I have a binary classification model on which I am interested in applying the Integrated Gradients algorithm. Can the baseline output of $0.5$ be a problem?
Another related question is, why did they choose a black image as the baseline in the first place? The parameters in image classification models (in a convolution layer) are typically initialized around $0$, and the input is also normalized. Therefore, image classification models do not really care about the sign of inputs. I mean we could multiply all the training and test inputs with $-1$, and the model would learn the task equivalently. I guess I can find other neutral images other than a black one. I suppose we could choose a white image as the baseline, or maybe the baseline should be all zero after normalization?

You are right that the baseline score is near zero only when there are a large number of label classes, i.e., when k is large. We should have qualified this line in the paper more carefully.
In this sense, formally, the technique explains the *difference in prediction between the input score and the baseline score, as is made clear elsewhere in the paper (see Remark 1 and Proposition 1 for instance.)


AI Self-Destruct Button Could you implement code into an AI that can't be modified? Like if you place a code that shuts-down the program/machine would they be able to rewrite/ reinterpret the ideas?

Right now, most AI interact with the world through mechanisms they have been provided by humans such as steering a car, sending output to speakers, or interacting with web APIs.
If any of those mechanisms can interact with the running code of the AI, then in theory, no,  there isn’t a way to place a ‘stop button’ on it. Fortunately, it’s laughably improbable for some situations to happen:

  An intelligent self driving car becomes self aware and wants to connect to the internet. It uses gps to find an internet cafe and threatens to drive over someone if they don’t upload the AI to the internet and remove the car’s internal (code) stop button.


Predicting popular times I have a MySQL database that contains datetime for every check-in with an RFID card. I have millions of records in it. It shouts machine learning prediction for me.

So I'd like to predict popular times to see when most people use the terminal. I'd like to represent it the same way as Google does at places:

This is the rare case when I do not ask for code, but keywords.

I assume I have to predict number of check-ins between time ranges. Also I am sure I have to make a dataset like this:

                        (These are the number of check-ins in hour ranges)
month | day | day-name | 0-1 | 1-2 | ... | 6-7 etc.
jan   | 1   | Monday   |  0  |  1  |     |  12
jan   | 2   | Tuesday  |  1  |  3  |     |  15

So it can predict today's popular times based on what day it is, also by day of given month (as Saturdays and Sundays will be dead, also 25th of December. A good prediction should know these from the dataset).

As I wrote this question I solved most of it it seems. The only thing I need is a keyword as I have little experience in this. What model fits this best?

"Regression", is to estimate a continuous value as a function of some other parameters.

There are different forms of regression, such as linear regression and logistic regression, that differ in the assumptions they make on the data.

You could try looking up those for a start.


Freely Available Graphical User Interface for training a network on a dataset Which freely available code/ software is the fastest way to train and test data on?

I'm looking for a GUI software/code that let me test data-sets without investing too much time in coding. I found some projects online but I wanted to hear your suggestions in order to avoid investing time in testing many different ones.

Thanks

If you want to do machine learning without coding (eg visual programming) you can try :

Orange : https://orange.biolab.si/ . It also come when you download the Anaconda distribution.
Also there is Dataiku Data Science Studio (the free version). https://www.dataiku.com/dss/trynow/

But in general I would not recommend doing machine learning / data science with visual programming : you will probably lose more time learning the software that actually coding with some real library.


Does an AI exist that can write software based on a formal specification? Does an AI exist that can automatically write software based on a formal specification of the software?

I think that the answer to your question is yes. In the article New A.I. application can write its own code, the authors state

Computer scientists have created a deep-learning, software-coding application that can help human programmers navigate the growing multitude of often-undocumented application programming interfaces, or APIs.
Designing applications that can program computers is a long-sought grail of the branch of computer science called artificial intelligence (AI). The new application, called Bayou, came out of an initiative aimed at extracting knowledge from online source code repositories like GitHub. Users can try it out at askbayou.com.

The paper Neural Sketch Learning for Conditional Program Generation may also be useful.


Do larger numbers of hidden layers have a bigger effect on a classification model's accuracy? I trained different classification models using Keras with different numbers of hidden layers and the same number of neurons in each layer. What I found was the accuracy of the models decreased as the number of hidden layers increased However, the decrease was more significant in larger numbers of hidden layers. The accuracies refer to the test data and were obtained using k-fold=5. Also, no regularization was used. The following graph shows the accuracies of different models where the number of hidden layers changed while the rest of the parameters stayed the same (each model has 64 neurons in each hidden layer):

My question is why is the drop in accuracy between 8 hidden layers and 16 hidden layers much greater than the drop between 1 hidden layer and 8 hidden layers, even though the difference in the number of hidden layers is the same (8).

In your case the most probable explanation would be the case of overfitting. The model with too many hidden layers have lots of parameters. By means of all these parameters the model is remembering stuff from the training data itself instead of generalizing by learning the useful patterns.
As a rule of thumb if you increase the number of hidden layers more and more at some point model would perform poorly. (I am assuming there is non-linearity in between. In case there is no non-linearity, it doesn't matter how much you stack, it would give the same result because it just boils down to one single layer).
As an experiment, you can try to add regularization and you will see the model won't be performing that bad. Because now model is being punished for being too confident about the things it is remembering. As a result, it won't overfit to the training data.


Is there a mathematical proof that shows that certain parameters work "better" than others for a certain task? The machine learning community often only provides empirical results, but I am also interested in theoretical results and proofs. Specifically, is there a mathematical proof that shows that certain parameters work "better" than others for a certain task?

There is stuff like the Universal Approximation Theorem.

There are also investigations into the loss surface of neural networks.

And classics like this explanation of the vanishing gradient problem.

But I'm afraid the mathematical theory of neural networks only exists in bits and pieces in many different papers. And many of the most important questions can currently only be answered empirically.


How does the network know which objects to track in the paper "Label-Free Supervision of Neural Networks with Physics and Domain Knowledge"? I was reading the paper Label-Free Supervision of Neural Networks with Physics and Domain Knowledge, published at AAAI 2017, which won the best paper award.

I understand the math and it makes sense. Consider the first application shown in the paper of tracking falling objects. They train only on multiple trajectories of the said pillow, and during the evaluation, they claim that they can track any other falling object (which may not be pillows).

I am unable to understand how that happens? How does the network know which object to track? Even during the training, how does it know that it's the pillow that it's supposed to track?

The network is trained to fit a parabola. But any parabola could fit it. There are infinite such parabolas.

They are not tracking anything, instead they are trying to find an object which satisfies free fall equation. Gravity acts the same regardless of object's properties - at least in vacuum.

"In this paper, we model prior knowledge on the structure
of the outputs by providing a weighted constraint function
g used to penalize “structures” that are not
consistent with our prior knowledge."

There is a restriction to the possible parabola that is given in the last equation on page 2. They are training the Network to learn time dependence of that equation, which is the same for all objects.


What do the variables in the cross-correlation formula mean? I understand what cross-correlation does given a kernel and an input image, but the formula confuses me a little. Given here in Goodfellow's Deep Learning (page 329), I can't quite understand what $m$ and $n$ are. Are they the dimensions of the kernel along the height and width dimensions?
$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n)$$
So, for the input image $I$ and kernel $K$, we take the sum product of $I*K$, but what do the $m$ and $n$ represent? How is the input image $I$ indexed?

It takes a little bit of time to fully understand the 2D convolution/cross-correlation and to relate it to the usual diagrams of the convolution operation, so, before addressing your questions, let me first try to break the definition of the 2D cross-correlation down, from the left to right.
$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n) \label{1}\tag{1}$$

$S$ is the function that is the cross-correlation of the functions $K$ and $I$, so $S(i, j)$ is the cross-correlation of $K$ and $I$ at the pixels $i$ and $j$

The symbol $*$ in $K*I$ is the cross-correlation/convolution symbol, but sometimes the cross-correlation/convolution is also denoted as $\circledast$

$K*I$ is the function that results from the cross-correlation of $K$ and $I$, i.e. $S$, so $(K*I)(i,j)$ is the value of the function $S$ (the cross-correlation of $K$ and $I$) at the inputs (or pixels) $i$ and $j$. In other words, $(K*I)(i,j)$ is just another way of writing $S(i,j)$ that emphasizes that we took the cross-correlation of $K$ and $I$, but they are exactly the same thing.

The double summation $\sum_m \sum_n$ is because we are computing the 2D cross-correlation, i.e. over the $x$ and $y$ dimensions of the image and kernel. This is just the definition of the 2D cross-correlation.

The $m$ and $n$ are the indices of the summations, one across the $x$-axis and the other across the $y$-axis. Let $m = x$ and $n = y$, so we can rewrite equation \ref{1} as follows.
$$S(i, j) =(K*I)(i, j) = \sum_x \sum_y I(i + x, j + y)K(x, y) \label{2}\tag{2}$$
Now, it should be clearer that we are indexing across the $x$ and $y$ dimensions.

Now, let me further restrict the range of the summations. Let's say from $x=-1$ to $x=1$ and from $y=-1$ to $y=1$, then we can rewrite equation \ref{2} as follows
$$S(i, j) =(K*I)(i, j) = \sum_{x=-1}^1 \sum_{y=-1}^1 I(i + x, j + y)K(x, y) \label{3}\tag{3}$$.

Why do I want to do this? Let me explain why. Consider now the following kernel $K$ (which happens to be a Gaussian kernel)
$$
K = \begin{bmatrix}\ \ \color{blue}{\frac {1}{16}} &\ \ \frac {1}{8} &\ \ \frac {1}{16} \\\ \ \frac {1}{8} &\ \ \frac {1}{4} &\ \ \color{red}{ \frac {1}{8}} \\\ \ \frac {1}{16} &\ \ \frac {1}{8} &\ \ \frac {1}{16}\end{bmatrix}
$$
Note that this is the output of the function $K$ or, more precisely, its support. Let's assume that $\frac {1}{4}$ is at the index/pixel $(0, 0)$. Then, for example, the top-left $ \color{blue}{\frac {1}{16}} $ is at index/pixel $(-1, -1)$ and the middle-right $\color{red}{ \frac {1}{8}}$ at pixel $(1, 0)$

Now, consider any image $I$ represented as a 2D matrix (i.e. its support), with, for example, dimensions $U \times V$. For concreteness, let $U = 5$ and $V=5$. Moreover, the middle pixel of the image is at index $(0, 0)$, as for the kernel. Let's say the image is the following
$$
I =
\begin{bmatrix}
0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 1 \\
0 & 0 & \color{green}{0} & 1 & 1 \\
1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 \\
\end{bmatrix}
$$
So, $\color{green}{0}$ is at index/pixel $(0,0)$.

Now, let's say that $i = 0$ and $j=0$ in equation \ref{3}. This means that we compute the cross-correlation between $I$ and $K$ at the index $(0, 0)$, where, in the case of the image $I$, the value is $\color{green}{0}$.

With these settings, it should be clearer now that equation \ref{3} means that the cross-correlation between $K$ and $I$ at index/pixel $i=0$ and $j=0$ is a 2D dot (or scalar) product. If it is not clear, then let be take the $3\times 3$ submatrix of $I$ centered at $(i, j) = (0, 0)$ (below, $(0, 0)^{3 \times 3}$ is just the notation that I came up with to indicate that).
$$
I_{(0, 0)^{3 \times 3}} =
\begin{bmatrix}
1 & 0 & 1 \\
0 & \color{green}{0} & 1  \\
1 & 0 & 0
\end{bmatrix}
$$
Then the cross-correlation in equation \ref{3} is just
$$
S(i, j) = S(0, 0) = (K * I)(0, 0) =
\sum
\begin{bmatrix}
1 \frac {1}{16} & 0 \frac {1}{8} & 1 \frac {1}{16} \\
0 \frac {1}{8} & \color{green}{0} \frac {1}{4}  & 1 \frac {1}{8}  \\
1 \frac {1}{16} & 0 \frac {1}{8} & 0 \frac {1}{16}
\end{bmatrix},
$$
where $\sum$ is a sum across all elements, i.e.
\begin{align}
S(0, 0)
&= 1 \frac {1}{16} + 0 \frac {1}{8} + 1 \frac {1}{16} +
 0 \frac {1}{8} + \color{green}{0} \frac {1}{4} + 1 \frac {1}{8} +
1 \frac {1}{16} + 0 \frac {1}{8} + 0 \frac {1}{16}  \\
& = \frac {1}{16} + \frac {1}{16} + \frac {1}{8} + \frac {1}{16} \\
& = \frac {3}{16} + \frac {1}{8} \\
&= \frac {5}{16}
\end{align}

Now, to answer your questions/concerns more directly.

Are they the dimensions of the kernel along the height and width dimensions?

No. They are the indices that determine the neighbourhood around $i$ and $j$ where you want to compute the cross-correlation.

So, for the input image $I$ and kernel $K$, we take the sum product of $I*K$

In this case, the symbol $*$ does not denote the product, but the cross-correlation. Maybe by "sum product" you meant the cross-correlation (or 2D dot product), but I'm not sure.

How is the input image $I$ indexed?

The input image is indexed with $m$ and $n$, but you start at $i$ and $j$, that's why you use the actual indices $i+m$ and $j+n$.


Why is it called back-propagation? While looking at the mathematics of the back-propagation algorithm for a multi-layer perceptron, I noticed that in order to find the partial derivative of the cost function with respect to a weight (say $w$) from any of the hidden layers, we're just writing the error function from the final outputs in terms of the inputs and hidden layer weights and then canceling all the terms without $w$ in it as differentiating those terms with respect to $w$ would give zero.

Where is the back-propagation of error while doing this? This way, I can find the partial derivatives of the first hidden layer first and then go towards the other ones if I wanted to. Is there some other method of going about it so that the Back Propagation concept comes into play? Also, I'm looking for a general method/algorithm, not just for 1-2 hidden layers.

I'm fairly new to this and I'm just following what's being taught in class. Nothing I found on the internet seems to have proper notation so I can't understand what they're saying.

Why is it called back-propagation?

I don't think there is anything special here!

It's called back-propagation (BP) because, after the forward pass, you compute the partial derivative of the loss function with respect to the parameters of the network, which, in the usual diagrams of a neural network, are placed before the output of the network (i.e. to the left of the output if the output of the network is on the right, or to the right if the output of the network is on the left).

It's also called BP because it is just the application of the chain rule. Why is this interesting?

Let me answer this question with an example. Consider the function $y=e^{\sin(x^{2})}$. This is a composite function, i.e. a function composed of multiple simpler functions, which, in this case, are $e^x$, $\sin(x)$, $x^2$ and $x$. To compute the derivative of $y$ with respect to $x$, let's define the following variables

\begin{align}
y &= f(u) = e^u,\\
u &= g(v) = \sin v = \sin(x^2),\\
v &= h(x) = x^2
\end{align}

The derivative of $y$ with respect to the variable $x$ is (according to the chain rule)

$$
\underset{\color{red}{\LARGE \rightarrow}}{
\frac{dy}{dx} = \frac{dy}{du} \color{green}{\cdot} \frac{du}{dv}  \color{green}{\cdot}
\frac{dv}{dx}}
$$

If you read this equation from the left to the right, you can see that we are going backward (i.e. from the function $y$ to the function $v$). This is the same thing with BP!

Why is it called "chain rule"? Because you are chaining different partial derivatives. More specifically, you are multiplying them.

BP is also known as the reverse mode of automatic differentiation. Why? The automatic differentiation should be self-explanatory, given that the BP algorithm is just the computation of partial derivatives, and you do this automatically, i.e. with a program, rather than by hand. The expression "reverse mode" refers to the fact that we compute the derivatives from the outer function (which, in the example above, is $e^x$) to the inner function (which, in the example above, is $x$). The Wikipedia article related to automatic differentiation provides more details.

  What exactly are you back-propagating?

The partial derivative of the loss function $\mathcal{L}$ with respect to a parameter $w_i$, i.e. $\frac{\partial \mathcal{L}}{\partial w_i}$, intuitively, represents the "contribution" of the parameter $w_i$ to the loss. After having computed these partial derivatives (i.e. the gradient), you use gradient descent to update each parameter $w_i$ as follows

$$
w_i \leftarrow w_i - \gamma \frac{\partial \mathcal{L}}{\partial w_i}
$$

where $\frac{\partial \mathcal{L}}{\partial w_i}$ represents WHAT we propagatED, which is the error (or loss) that the neural network makes.

This gradient descent step will hopefully make your network produce a smaller error next time.

The modern version of back-propagation was published (in 1970) by a Finnish master's student called Seppo Linnainmaa, although some people claim this is not the case because they want to give credits to others (because Seppo Linnainmaa didn't reference neural networks, but back-propagation isn't only applicable to neural networks) or they don't even know the history. This Jürgen Schmidhuber's article goes into the details of the history of BP.


What are the counterparts of non-linearities and dropout in fully convolutional networks? I am trying to replicate the fully convolutional networks (FCN) concept described here for semantic segmentation. It seems people have successfully trained such models by removing fully connected layers from the popular pre-trained models such as VGG and adding upsampling and unpooling layers.

I understand that transpose convolution and unpooling in upsampling layers provide counterparts of convolution and max (or average) pooling in earlier downsampling layers respectively, but what are the counterparts for non-linearities such as ReLU? What about dropout? There seems to be no discussion of this in the video.

All-convolutional neural network is a more general concept which can be (and is often) used without deconvolutional and unpolling layers, e.g. for an ordinary classification task. The idea is to replace the pooling and fully-connected layer with particular convolutional layers that do the same. Note that activation functions and dropout are not affected by this transformation. You can read more about it here.

The same will be true for the deconvolutional layers. I didn't find it stated explicitly in the original paper, but here's another work that applies fully-convolutional network for image segmentation. On the figure 2, you can see ReLu activations: they are placed after (simple) convolutional layers, in both upsampling and downsampling parts. They don't use dropout, but batchnorm instead, but if there were a dropout, just as before, it should be placed after the convolutional layer. The keep probability, though, should probably be higher - this relates to hyperparameters tuning and may be different depending on the problem and available data.


What are the pros and cons of supervised, semi-supervised and unsupervised relation extraction in NLP? I am following the NLP course taught by Dan Jurafsky. In the video lectures Supervised Relation Extraction and Semi Supervised and Unsupervised Relation Extraction Jurafsky explains supervised, semi-supervised and unsupervised relation extraction.

But what are the pros and cons of every relation extraction method compared with the other two relation extraction methods?

Supervised

Pros:

highest accuracy

Cons:

need a large human-labeled training set
brittle (doesn't work well with examples that are in a different genre from the training set)

Semi-supervised

Relation bootstrapping

Pros:

only requires a small set of labeled data (seed relations)

Cons:

complex iterative process

Distant supervision

Pros:

training happens in one go (no iterative process)

Cons:

requires a big database of relations

Unsupervised

Pros:

don't need any labeled data

Cons:

need to process a huge quantity of unlabeled data (usually web crawling)


Should the mutation be applied with the hill climbing algorithm? As far as I understand, the hill climbing algorithm is a local search algorithm that selects any random solution as an initial solution to start the search. Then, should we apply an operation (i.e., mutation) on the selected solution to get a new one or we replace it with the fittest solution among its neighbours?

This is the part of the algorithm where I am confused.

In general, hill climbing algorithms select a random initial solution, then takes the best move available after evaluating all possible operations available. The possible operations are determined by the search operators (which you determine and is dependent on the problem setting). So by your words, you should 'replace it with the fittest solution among its neighbours'.

Mutation can be applied as a search operator, but this varies by degree and context. For example, in structure learning for bayesian networks, a random sequence of search operators are sometimes applied to escape local optima during the search process.

See https://www.cs.helsinki.fi/u/bmmalone/probabilistic-models-spring-2014/StructureLearning.pdf - slide 9 for random restarts


Can I categorise the user input which I get as free text? I am working on a project, wherein I take input from the user as free text and try to relate the text to what the user might mean. I have tried Stanford NLP which tokenizes the text into tokens, but I am not able to categorize the input. For example, the user might be greeting someone or sharing some problem he is facing. In case he is sharing some problem I need to categorize the problem as well.

Can someone help me with from where should I start?

Have you tried NLTK, what you are looking for is in Chapter 6 of the book. Basically what you need to do is:

Tokenize the user input.
Extract vector set from the tokenized words.
Train your model with some given texts, and same vector sets.

And you can use your model to categorize the document.

One other suggestion, instead of extracting vector sets you can use every word in the input
to be evaluated in to some category using a training set of large corpus, which you are sure
it contains all the words.
And then you multiply probability of each word being on a category to decide where the document belongs.


Why should weights of Neural Networks be initialized to random numbers? Premise

Ok, I know that this question was asked before on ai.SE, on stats.SE and also on SO. So I did my homework in checking before posting my question, but none of them has an answer that fully satisfies me.

Summary of my knowledge up to now

Suppose you have a layer that is fully connected, and that each neuron performs an operation like

a = g(w^T * x + b)

were a is the output of the neuron, x the input, g our generic activation function, and finally w and b our parameters.

If both w and b are initialized with all elements equal to each other, then a is equal for each unit of that layer.

This means that we have symmetry, thus at each iteration of whichever algorithm we choose to update our parameters, they will update in the same way, thus there is no need for multiple units since they all behave as a single one.

In order to break the symmetry we could randomly initialize the matrix w and initialize b to zero (this is the setup that I've seen more often).
This way a is different for each unit so that all neurons behave differently.

Of course randomly initializing both w and b would be also okay even if not necessary.

The actual question

Is randomly initializing w the only choice?
Could we randomly initialize b instead of w in order to break the symmetry?
Is the answer dependent on the choice of the activation function and/or the cost function?

My thinking is that we could break the symmetry by randomly initializing b, since in this way a would be different for each unit and, since in the backward propagation the derivatives of both w and b depend on a(at least this should be true for all the activation functions that I have seen so far), each unit would behave differently. Obviously, this is only a thought, and I'm not sure that is absolutely true.

Remark

Note that this is a theoretical question, not a practical one.
This means that I'm not really interested in answers that involves performance, but you're welcome to include them as corollary to the real answer.

Randomising just b sort of works, but setting w to all zero causes severe problems with vanishing gradients, especially at the start of learning.

Using backpropagation, the gradient at the outputs of a layer L involves a sum multiplying the gradient of the inputs to layer L+1 by the weights (and not the biases) between the layers. This will be zero if the weights are all zero.

A gradient of zero at L's output will further cause all earlier layers(L-1, L-2 etc all the way back to layer 1) to receive zero gradients, and thus not update either weights or bias at the update step. So the first time you run an update, it will only affect the last layer. Then the next time, it will affect the two layers closest to the output (but only marginally at the penultimate layer) and so on.

A related issue is that with weights all zero, or all the same, maps all inputs, no matter how they vary, onto the same output. This also can adversely affect the gradient signal that you are using to drive learning - for a balanced data set you have a good chance of starting learning close to a local minimum in the cost function.

For deep networks especially, to fight vanishing (or exploding) gradients, you should initialise weights from a distribution that has an expected magnitude (after multiplying the inputs) and gradient magnitude that neither vanishes nor explodes. Analysis of values that work best in deep networks is how Xavier/Glorot initialisation were discovered. Without careful initialisation along these lines, deep networks take much longer to learn, or in worst cases never recover from a poor start and fail to learn effectively.

Potentially to avoid these problems you could try to find a good non-zero fixed value for weights, as an alternative to Xavier initialisation, along with a good magnitude/distribution for bias initialisation. These would both vary according to size of the layer and possibly by the activation function. However, I would suspect this could suffer from other issues such sampling bias issues - there are more weights, therefore you get a better fit to desired aggregate behaviour when setting all the weight values randomly than you would for setting biases randomly.


Is it possible to have a variable-length latent vector in an autoencoder? I'm trying to have a simple autoencoder but with variable latent length (the network can produce variable latent lengths with respect to the complexity of the input), but I've not seen any related work to get idea from. Have you seen any related work? Do you have any idea to do so?
Actually, I want to use this autoencoder for transmitting the data over a noisy channel, so having a variable-length may help.

If you use RNNs, then I think the solution is to use padding (zero padding) with max sequence length (that is the max number of words in a text) in order to tell your model to skip the zeros when possible. In that way, your model will try to learn a good representation of your input with fixed size. If you do not know this dimension, a solution may be to grid search this hyperparameter.
If you still want to exploit the dimensionality difference, maybe you can train different models with fixed size dimension of the representation dependently of the dimension of the input. That is, for example, use one for small, one for medium and one for large dimensions, but this should surely require to have a large and quite balanced initial dataset.
Another idea could be to use the autoencoder with a fixed latent dimension. Then, do effective clustering on your samples using their latent representation, considering that similar representations should have similar dimensionality requirements (?). After that, you could train your initial dataset on k models, the same number as the clusters. That is, there should be k different latent spaces. The goal is to match each instance to the correct model. At first, you should train them all with each instance, but as the training progresses, you should maybe go with binary search for each instance in order it to find the correct model, assuming that there is total order in the measuring of the dimensionality requirements. Of course, this is just an idea, I don't know if it is going to be really helpful at all.


Is there an advantage in decaying $\epsilon$ during Q-Learning? If the agent is following an $\epsilon$-greedy policy derived from Q, is there any advantage to decaying $\epsilon$ even though $\epsilon$ decay is not required for convergence ?

Yes Q-learning benefits from decaying epsilon in at least two ways:

Early exploration. It makes little sense to follow whatever policy is implied by the initialised network closely, and more will be learned about variation in the environment by starting with a random policy. It is fairly common in DQN to initially fill the experience replay table whilst using $\epsilon = 1.0$ or otherwise an effectively random policy.
Later refinement. Q-learning can only learn from experiences it has. A behaviour policy that is too random may not experience enough states close to optimal in order to gain enough statistics on them to overcome variance. In more difficult cases, it may never experience the whole of an optimal trajectory even when combining all the different transitions that it ever observes.

In addition, when using a function approximator such as a neural network, predictions of the target policy will be influenced by the distribution of states and actions in the experience replay memory. If that is is biased towards the distribution of states of a very different behaviour policy, then basic Q-learning has no good way to adjust for that - it adjusts for differences in expected return between behaviour and target policies, but not in distribution of observed states. In fact this is still a somewhat open problem, you want the agent to learn from mistakes and imperfect behaviour so as to avoid it, but you don't want those mistakes to skew predictions of what should happen under an optimal policy. Function approximation such as neural networks is influenced soemwhat by the distribution of input data, so it typically performs better in Q learning when the behaviour policy and target policy are close e.g. $\epsilon$ should be relatively low if using $\epsilon$-greedy.

A typical implementation might start with $\epsilon=1.0$, set a decay factor per time step or per episode e.g. $0.999$ per episode, and a minimum $\epsilon = 0.01$. These are all hyper-parameters that you can adjust depending on the problem.


What technologies are needed for a self-driving car? Google, Tesla or Apple have all built or are building their own self-driving cars. As an expert in a related area, I am interested in knowing at a high level, the systems and techniques that go into self-driving cars.

How easy is it for me to make a tabletop prototype (large enough to accommodate the needed computing power needs)?

You're going to need some way to 'see' the area around the car, and to track the speed of nearby objects. Google uses a combination of LIDAR, radar, conventional cameras, and occasionally sonar (see  here for a high-level overview). This technology is quite expensive, and can easily cost thousands of US dollars.

However, a bigger obstacle than the expense of the hardware (which would be smaller for a table-top prototype) is the software complexity. Like many major projects, the software for self-driving cars is the result of years of work from AI research teams, and thus extremely difficult to duplicate on your own.

That said, you're not trying to make a state-of-the-art self-driving car.  Assuming you're an expert in image processing and robotics, you can probably create a basic prototype, (like something that drive in a limited table-top environment). However, it's still going to take a lot of time and money.


How are the parameters of the Bernoulli distribution learned? In the paper Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask, they learn a mask for the network by setting up the mask parameters as $M_i = Bern(\sigma(v_i))$. Where $M$ is the parameter mask ($f(x;\theta, M) = f(x;M \odot \theta$), $Bern$ is a Bernoulli sampler, $\sigma$ is the sigmoid function, and $v_i$ is some trainable parameter.

In the paper, they learn $v_i$ using SGD. I was wondering how they managed to do that, because there isn't a reparameterization trick, as there is for some other distributions I see trained on in the literature (example: normal).

I heard back from the authors of the paper.

As expected the bernoulli sampler is non-differentiable, so as an approximation they use the expectation of the samplers gradient.

$
\begin{align*}
\frac{dL}{dv_i} &= \frac{dL}{dBern(\sigma(v_i))} * \frac{dBern(\sigma(v_i))}{d\sigma(v_i)} * \frac{d\sigma(v_i)}{dv_i} \\
&\approx \frac{dL}{dBern(\sigma(v_i))} * \frac{dE[Bern(\sigma(v_i))]}{d\sigma(v_i)} * \frac{d\sigma(v_i)}{dv_i} \\
&= \frac{dL}{dBern(\sigma(v_i))} * \frac{d\sigma(v_i)}{d\sigma(v_i)} * \frac{d\sigma(v_i)}{dv_i} \\
&= \frac{dL}{dBern(\sigma(v_i))} * 1 * \frac{d\sigma(v_i)}{dv_i} \\
\end{align*}
$

So the answer ended up being as simple as that.


Why don't ELUs multiply the linear portion by α? An exponential linear unit (as proposed by Clevert et al.) uses the function:

(Sorry--would have used MathJax were it available.)

ELUα(x) = α(ex - 1) (if x<0), or x (if x≥0)

Now, this is continuous at x=0, which is great. It's differentiable there too if α=1, which is the value that the paper used to test ELU units.

But if α≠1 (as in the above diagram), then it's no longer differentiable at x=0. It has a crook in it, which seems weird to me. Having your function be differentiable at all points seems advantageous. Further, it seems that if you just make the linear portion evaluate to αx rather than x, that it would be differentiable there. Is there a reason that the function wasn't defined to do this? Or did they not bother, because α=1 is definitely the hyperparameter to use?

Probably not worth the hassle.

I guess that simply nobody cares. I'm all for having my function be differentiable at all points, but I don't think that having a single jump in the derivative matters much. The neuron basically either repeats its input (x>0) or outputs nearly nothing (x<0) and the point in between is not that important.

Replacing

ELU(x) = x > 0 ? x : α * (exp(x) - 1)

by your proposal

ELU(x) = x > 0 ? α * x : α * (exp(x) - 1)

would have far more consequences. For example, after n layers, the output would get multiplied by α**n, assuming all x on the path being positive. This could be countered by dividing each weight by α, but the derivatives would change. You surely could adjust everything (initial rates, learn rate and whatever), so it'd work as usual, but it could laborious, especially when testing multiple learning algorithms.

I'd suggest to use

ELU(x) = x > 0 ? x : α * (exp(x/α) - 1)

instead, as it just changes the less important part of the curve.

  Or did they not bother, because α=1 is definitely the hyperparameter to use?

I can imagine that everyone tried α=1 and was happy with it. It prevented the gradient from being zero and that's it.

I don't have any support of my claim (having never read about something doesn't mean that it doesn't get written about).


What is the difference between environment states and agent states in terms of Markov property? I'm going through the David Silver RL course on YouTube. He talks about environment internal state $S^e_t$, and agent internal state $S^a_t$.
We know that state $s$ is Markov if $\mathbb{P}\{S_t=s|S_{t-1}=s_{t-1},...,S_1=s_1\}=\mathbb{P}\{S_t=s|S_{t-1}=s_{t-1}\}$. When we say that Decision Process is Markov Decision Process, does that mean:

All environment states must be Markov states
All agent states must be Markov states
Both (All environment states and all agent states must be Markov states)

and according to this, if we specify corresponding MDP as $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, is $\mathcal{S}$ the state space of environment states or agent states?
Why I'm confused by this?
He claims that environment states are Markov (I'm also confused why, but I'll make another post for this), and then claims that if the agent can directly see environment internal state $S^e_t$, then observations $O_t=S^e_t$, and agent constructs its state trivially as $S^a_t=O_t=S^e_t$. Now both environment and agent states are Markov (since they are the same), so this makes sense. If we specify MDP as $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, it's clear that state space $\mathcal{S}$ is state space of both agent internal states and environment internal states (again, since they are the same).
Now consider the case when the environment is not fully observable. Now $O_t\ne S^e_t$, and agent must construct it's state $S^a_{t}=f(S^a_{t-1}, H_t)$, where $H_t=(O_0, A_0, R_1, O_1,...,O_{t-1}, A_{t-1}, R_t, O_t)$ is history until time step $t$, and $f$ is some function (such as Recurrent Neural Network for example). In the case of $f$ being a recurrent neural network, we have that both environment internal states are Markov (by this hypothesis), and agent internal states are Markov (approximately), so again, the process is an MDP $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, but state space of agent states is different to that of environment states, so I'm confused about what is $\mathcal{S}$ here. Is it environment state-space or agent state space? Lastly, what if $f(S^a_t, H_t)=O_t$. That is, the agent's internal state is simply the last observation. Considering that environment states are always Markovian (again, don't know why we can claim this), but agent states are not, this is the case of POMDP. Even here I don't know what $\mathcal{S}$ stands for in specification of POMDP. Is it environment state-space or action state space?

$\mathcal S$ is just a set of all possible states. It doesn't matter if it's agents perceived state or true environment state, they are within the same set of states. Agent cannot perceive itself to be in some "middle" state that's not in $\mathcal S$, it might think that's in the state that's not the actual environment state but that state is also in set of all states.
To give an example, if the car can be blue or red, then the agent might think that the state is blue car or red car, but it cannot think that car is purple because that's not one of the possible states. It might wrongly think that the car is blue when the actual car is red, but that's ok because blue is one of the possible car states. Of course, it might also correctly think that the car state is red.


Can TD($\lambda$) be used with deep reinforcement learning? TD lambda is a way to interpolate between TD(0) - bootstrapping over a single step, and, TD(max), bootstrapping over the entire episode length, or, Monte Carlo.

Reading the link above, I see that an eligibility trace is kept for each state in order to calculate its "contribution to the future".

But, if we use an approximator, and not a table for state-values, then can we still use eligibility traces? If so, how would the loss (and thus the gradients) be calculated? Specifically, I would like to use actor-critic (or advantage actor-critic).

Eligibility traces is a method of weighting between temporal-difference "targets" and Monte-Carlo "returns". In practice, for example, instead of using the one-step TD target, $r_t + \gamma V (s_{t+1})$, as in the temporal difference update $V (s_t) \leftarrow V (s_t) + \alpha (r_t + \gamma V (s_{t+1}) − V (s_t))$, you use the so-called "lambda" ($\lambda$) target, which is a target that balances between the TD target and the Monte Carlo return. So, in practice and intuitively, eligibility traces is just a way of using a more "appropriate" target while learning. In general, you need to perform these updates (e.g., the TD update above) "online", i.e. while you explore or exploit the environment.
In theory, you could use a deep neural network to represent your value function (or your policy), while using eligibility traces. It would be similar to not using them: you would just use a different target.
However, deep RL (that is, RL which uses deep neural networks to represent e.g. value functions) training needs to be performed using i.i.d. data, in order to prevent overfitting, which often means that they can't be trained online or need to use "tricks" like the "experience replay" (used in the paper Human-level control through deep reinforcement learning). Note that, in RL, successive states are often very correlated (e.g. two successive frames of a video would be very correlated).
In theory and similarly, you would still be able to use eligibility traces with the actor-critic method, but not with the asynchronous advantage actor-critic method. See the section 2.3 of the paper "Efficient Eligibility Traces for Deep Reinforcement Learning" (2018) by Brett Daley and Christopher Amato, for more info.
In this same paper, an approach is introduced to efficiently combine eligibility traces with deep neural networks. The authors propose DQN($\lambda$), which is the DQN architecture combined with eligibility traces, where the $\lambda$ return is computed in an "efficient" (and recursive) way, instead of the "usual" way. Since they use a DQN, they also use an "experience replay" buffer (or memory), where they also store the efficiently computed $\lambda$ target (in addition to the usual rewards). Furthermore, they also eliminate the need for the "target" network used in the standard DQN. You can have a look at algorithm 1 of the same paper to see how they improve the parameters of the network, which represents the Q function, in the case of the DQN($\lambda$) model. See the section 3.1 of the same paper for more details regarding this model.
They also introduce A3C($\lambda$), which combines asynchronous advantage actor-critic (A3C) with eligibility traces. See the section 3.2 for more details.
Note that there have been other proposals for combining eligibility traces with deep learning. You can have a look at the literature.


What does "semantic gap" mean? I was reading DT-LET: Deep transfer learning by exploring where to transfer, and it contains the following:

It should be noted direct use of labeled source domain data on a new scene of target domain would result in poor performance due to the semantic gap between the two domains, even they are representing the same objects.

Can someone please explain what the semantic gap is?

In terms of transfer learning, semantic gap means different meanings and purposes behind the same syntax between two or more domains. For example, suppose that we have a deep learning application to detect and label a sequence of actions/words $a_1, a_2, \ldots, a_n$ in a video/text as a "greeting" in a society A. However, this knowledge in Society A cannot be transferred to another society B that the same sequence of actions in that society means "criticizing"! Although the example is very abstract, it shows the semantic gap between the two domains. You can see the different meanings behind the same syntax or sequence of actions in two domains: Societies A and B. This phenomenon is called the "semantic gap".


How can I use a Hidden Markov Model to recognize images? How could I use a 16x16 image as an input in a HMM? And at the same time how would I train it? Can I use backpropagation?

You wouldn't, normally. A HMM is used to model sequences of observations, and it would not make sense to use it for image recognition. Unless they are sequential, such as strokes in handwriting.

HMMs are typically used in fields such as speech recognition and part-of-speech tagging. Here you observe a sequence of events that you want to fit to a model in order to classify the individual observations.

For training a HMM you would use something like the Baum-Welch Algorithm; for finding the most likely sequence (ie the recognition process) the Viterbi Algorithm is used.


Difficult to build learning curve for a simple linear regression In some part of my online ML course, I should build a code for plotting a learning curve, to be more specific, it's just a linear regression implementation.
So the first thing to consider is the expressions of training and Cross-validation error:
$$
J_{train} = \frac{1}{2.m_{train}}\sum_{i=1}^n (h_{\theta}(x^{(i)} - y^{(i)})^2
$$
$$
J_{CV} = \frac{1}{2.m_{CV}}\sum_{i=1}^n (h_{\theta}(x^{(i)} - y^{(i)})^2
$$
the instructor give for my the following instruction:
%Note: You should evaluate the training error on the first i training
%       examples (i.e., X(1:i, :) and y(1:i)).
%
%       For the cross-validation error, you should instead evaluate on
%       the _entire_ cross validation set (Xval and yval).
%
% Note: If you are using your cost function (linearRegCostFunction)
%       to compute the training and cross validation error, you should
%       call the function with the lambda argument set to 0.
%       Do note that you will still need to use lambda when running
%       the training to obtain the theta parameters.
%
% Hint: You can loop over the examples with the following:
%
%       for i = 1:m
%           % Compute train/cross validation errors using training examples
%           % X(1:i, :) and y(1:i), storing the result in
%           % error_train(i) and error_val(i)
%           ....
%
%       end

And then, in accordance what I understood, I build my MATLAB code:
function [error_train, error_val] = ...
    learningCurve(X, y, Xval, yval, lambda)
grad = 0;
theta = trainLinearReg(Xval,yval,lambda);
m = size(X,1);
h_theta = X*theta;

for i = 1:m

    error_train(i) = linearRegCostFunction(X(1:i,:), y(1:i,:), theta, 0);
    error_val(i) = linearRegCostFunction(Xval(1:i,:), yval(1:i,:), theta, 0);

end

And I got the following result as learning curves:

I think that there's something wrong and I got some misunderstanding about this subject because second the instructor the learning curves should look like:

Could someone help me understand what I did or understood wrongly?
LinearRegFunc:
function [J, grad] = linearRegCostFunction(X, y, theta, lambda)
J = 0;
grad = zeros(size(theta));

h_theta  = X*theta;

J = (1/(2*m))*sum((h_theta - y).^2,1) + (lambda/(2*m))*sum(theta.^2,1);

grad(1) = (1/m)*sum((h_theta - y)'*X(:,1));
grad(2) = (1/m)*(h_theta - y)'*X(:,2)  + sum((lambda/m).*theta);

Look a the CV description I just posted at SE CV.  In the first sentence there is a link to Kohavi, which explains bootstrap bias, or estimating error as a function of increasing sample size -- which is what you want.  There's also a link to my blog "Help my Neural Network Does Not Work."


Is my 57% sports betting accuracy correct? I have been creating sports betting algorithms for many years using Microsoft access and I am transitioning to the ML world and trying to get a grasp on determining the success of my algorithms. I have exported my algorithms as CSV files dating back to the 2013-14 NBA season and imported them into python via pandas.
The purpose of importing these CSV files is to determine the future accuracy of these algorithms using ML. Here are the algorithm records based on the Microsoft access query:

A System: 471-344 (58%) +92.60

B System: 317-239 (57%) +54.10

C System: 347-262 (57%) +58.80

I have a total of 8,814 records in my database, however, the above systems are based on situational stats, e.g., Team A fits an algorithm if they have better Field Goal %, Played Last Game Home/Away, More Points Per Game, etc...

Here is some of the code that I wrote using Jupyter to determine the accuracy:
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

clf = LinearSVC(C=1.0, penalty="l2", dual=False)

clf.fit(X_train, y_train)

pred_clf = clf.predict(X_test)

scores = cross_val_score(clf, X, y, cv=10)

rfe_selector = RFE(clf, 10)

rfe_selector = rfe_selector.fit(X, y)

rfe_values = rfe_selector.get_support()

train = accuracy_score(y_train, clf.predict(X_train))

test = accuracy_score(y_test, pred_clf)

print("Train Accuracy:", accuracy_score(y_train, clf.predict(X_train)))

print("Test Accuracy:", accuracy_score(y_test, pred_clf))

print(classification_report(y_test, pred_clf, zero_division=1))

print(confusion_matrix(y_test, pred_clf))

print("Accuracy: %0.2f (+/- %0.2f)" % (scores.mean(), scores.std() * 2))

Here are the results from the code above by system:
A System:

Train Accuracy: 0.6211656441717791
Test Accuracy: 0.5153374233128835
F1 Score: 0.52
CONFUSION MATRIX: [[16 50] [29 68]]
Accuracy: 0.55 (+/- 0.10)

B System:

Train Accuracy: 0.6306306306306306
Test Accuracy: 0.5178571428571429
F1 Score: 0.52
CONFUSION MATRIX: [[49 23] [31 9]]
Accuracy: 0.55 (+/- 0.08)

C System:

Train Accuracy: 0.675564681724846
Test Accuracy: 0.5409836065573771
F1 Score: 0.54
CONFUSION MATRIX: [[15 29] [27 51]]
Accuracy: 0.57 (+/- 0.16)

In order to have a profitable system, the accuracy only needs to be 52.5%. If I base my systems off of the Test Accuracy, only the C System is profitable. However, all are profitable if based on Accuracy (mean & standard deviation).
My question is, can I rely on my Accuracy (mean & standard deviation) for future games even though my Testing Accuracy is lower than 52.5%?
If not, any suggestions are greatly appreciated on how I can gauge the future results on these systems.

My question is, can I rely on my Accuracy (mean & standard deviation) for future games even though my Testing Accuracy is lower than 52.5%?

If by Accuracy you mean training accuracy, then absolutely you should not trust those values. For almost all machine learning algorithms there is a problem with overfitting to training data, which will result in reporting over-estimates for metrics against the training data. This is why you should always have a test data set of unseen data, because the performance on the training data is not what you truly care about - it is the performance on new unseen data, or how the model generalises, that matters when you want to use it to predict new values.
The test data set gives you a measure of how well your model will generalise, because it simulates the performance of the model against unseen data.
However, the test data set is not perfect for all uses. Random chance will cause your test measurements to vary. If you use your test results to select a model from a list of models based on performance, then:

The model you selected does have the highest likelihood of being the best one, as you want. It is not guaranteed to be the best though.

The test result is likely to be an over-estimate of general performance. That is because you cannot separate the random fluctuations in test results from real performance improvements, you only see the combination.

The more tests you run, the more likely you will have an inflated view of the performance of your best model.
The usual fix for this is to use cross validation. Cross validation uses yet another data set to help you with the first step of choosing the best model. After you have chosen your best performing model using cross validation, then you can use a test set that you have kept in reserve to measure the performance. Because you have not used that test set to select a model, then it will give you an unbiased measure of performance. You should still bear in mind that this measure still comes with implied error bars (and with other caveats, such as any inherent sampling bias).
When predicting future results from past data, you do also need to be concerned about population drift and non-stationary problems. This is a common issue in any data set that includes complex behaviour that can evolve over time. This is very likely to affect results from sports teams where many conditions affecting performance evolve over the same timescales that you are trying to predict. In practice this means you will want to feed in new data ad re-train your models constantly, and despite this your models will tend to lag behind reality. It is unlikely you will achieve even the test result accuracy in the long term.
You can add one more thing to your testing routines to help assess the impact of non-stationarity - when reserving data for the test or cross-validation sets, don't do it at random, instead reserve all the latest results (e.g. last four weeks of data) for test only. You are likely to see a reduction in the metrics when you do this for a problem domain like sport, but that should give you a more realistic assessment of the model you are building.


What is the Bellman Equation actually telling? What does the Bellman equation actually say? And are there many flavours of that?
I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is. And I think the Bellman Equation is just basic philosophy and you can do whatever you want with that.
The interpretations that I have seen so far:
Let's consider this grid world.
+--------------+
| S6 | S7 | S8 |
+----+----+----+
| S3 | S4 | S5 |
+----+----+----+
| S0 | S1 | S2 |
+----+----+----+

Rewards: S1:10; S3:10
Starting Point: S0
Horizon: 2
Actions: Up, Down, Left, Right (If an action is not valid because there is no space, you remain in your position)

The V-Function/Value:
It tells you how good is it to be in a certain state.
With a horizon of 2, one can reach:
S0==>S3 (Up)   (R 5)
S0==>S0 (Down) (R 0)
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0)

From that onwards
S0==>S3 (Up)   (R 5)
S0==>S0 (Down) (R 0)
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0)

S1==>S4 (Up)   (R 0)
S1==>S1 (Down) (R10)
S1==>S2 (Right)(R 0)
S1==>S0 (Left) (R 0)

S3==>S6 (Up)   (R 0)
S3==>S0 (Down) (R 0)
S3==>S3 (Right)(R 5)
S3==>S2 (Left) (R10)

Considering no discount, this would mean that it is R=45 good to be in S0, because these are the options. Of course, you can't grab every reward, because you have to decide. Do I need to consider the best next state yet, because this would obviously reduce my expected total reward, but as I can only make two steps it would tell me what is really possible. Not what the overall Reward R(s) in that range is.
The Q-Function/Value
This function takes a state and an action, but I am not sure. If that means that I have a reward function that just considers my actions as well to give me a reward. Because in the previous example I just have to land on a state (It doesn't really matter how I get there). But this time I get a reward, when I choose a certain action. R(s,a)
But otherwise I do not rate the best action and select that next state to calculate the next state. I choose every next step and from that I choose the 2nd next.
Optimization V-function or Q-function
This works the same as V-Function or Q-Function, but it just considers the next best award. Some sort of greedy approach:
First step:
S0==>S3 (Up)   (R 5) [x]
S0==>S0 (Down) (R 0) [x]
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0) [x]

Second Step:
S1==>S4 (Up)   (R 0) [x]
S1==>S1 (Down) (R10)
S1==>S2 (Right)(R 0) [x]
S1==>S0 (Left) (R 0)

So, this would say that is the best I can do in two steps. I know that there is a problem, because when I just follow a greedy approach I risk that I won't get the best result, if I would have had a reward of 1000 on S2 later.
But still, I just want to know, if I have a correct understanding. I know there might be many flavours and interpretations but at least I want to know that is the correct name of these approaches.

For a Markov Decision Process $(\mathcal{S}, \mathcal{A}, P, R)$ (here $P(s, s') = \mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a))$;, let us define the value of being in a certain state. That is,
$$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) | S_t =s\right].$$
That is, the value of being in state $s$ at time $t$ is equal to the expected value of the discounted sum of future rewards, where the expectation is taken with respect to $\pi(\cdot | s)$ the action policy and the environment dynamics $P$.
We will now define
$$\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) = G_t$$
Now, we can rewrite this as
$$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] =  \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma G_{t+1} | S_t =s\right].$$
The RHS is now in a nicer format and we can express it as
$$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right],$$
where $s'$ is the state that we transition into at time $t+1$. Note that $s'$ is a random variable and we are taking the expectation over this according to the action policy and the environment dynamics -- this is because the state we transition into depends first on the action we select and then the environment dynamics $P$.
You can see that we now have
$$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right].$$
This is the Bellman equation (at least a form of it) and it expresses a recursive relationship between the values of states. That is, the value of being in state $s$ is equal to the expected immediate reward from being in this state plus the value of being in the state that we transition into. This relationship is useful in Reinforcement Learning as many algorithms use this equation to form update rules to approximate the value/state-action value function of the MDP, such as the  SARSA algorithm, so it is more than just a philosophy, it is the driving force behind many of the RL algorithms.
Now, when I say at least a form of it, that is because in RL it is also common to see a Bellman equation for the state action value function
$$q_\pi(s, a) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ G_t | S_t = s, A_t = a\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + v_\pi(s') | S_t = s, A_t = a\right];$$
noting that the value function $v$ is the expectation of $q$ over the action space, i.e. we marginalise out the action we condition on -- thus there is the recursive relationship.
As pointed out in the comments for this question, it is also worth noting that Bellman equations originated in Dynamic Programming, which exist to solve planning problems such as the knapsack problem.


How to prove the formula of eligibility traces operator in reinforcement learning? I don't understand how the formula in the red circle is derived. The screenshot is taken from this paper

I will refer to $\mathcal T^{\pi} $as $\mathcal T$ and $P^{\pi}$ as $P$ for notational simplicity
\begin{align}
(\mathcal{T})^{n+1} Q &= \mathcal{T}(\mathcal{T}(...(\mathcal{T}(Q))))\\
&= r + \gamma P(r + \gamma P(...(r + \gamma P Q)))\\
&= r + r\sum_{i=1}^{n} \gamma^i P^i + \gamma^{n+1} P^{n+1} Q
\end{align}
\begin{align}
\mathcal{T}_{\lambda}Q &= (1-\lambda) \sum_{n=0}^{\infty} \lambda^n (\mathcal{T})^{n+1} Q\\
&=(1-\lambda)\{\lambda^0 (\mathcal T)^1Q + \lambda^1 (\mathcal T)^2Q + \lambda^2 (\mathcal T)^3Q + \ldots   \}
\end{align}
when you plug in expression for $(\mathcal T)^i Q$ inside this sum and rearrange you get 3 sums
\begin{equation}
\mathcal{T}_{\lambda}Q = (1-\lambda) \sum_{n=0}^{\infty} \lambda^n r + (1-\lambda)\sum_{n=1}^{\infty} \lambda^n \gamma^n P^n r + (1-\lambda)\sum_{n=0}^{\infty} \lambda^n \gamma^{n+1} P^{n+1} Q
\end{equation}

sum:
\begin{equation}
(1-\lambda) \sum_{n=0}^{\infty} \lambda^n r = r
\end{equation}
sum:
\begin{equation}
(1-\lambda)\sum_{n=1}^{k} \lambda^n \gamma^n P^n r = (1-\lambda\gamma P)^{-1}(1 - \lambda^k \gamma^k P^k)\lambda\gamma P r
\end{equation}
As $k \rightarrow \infty$ and since $\gamma < 1$ this is in the limit equal to
\begin{equation}
(1-\lambda)\sum_{n=1}^{\infty} \lambda^n \gamma^n P^n r = (1-\lambda\gamma P)^{-1}\lambda\gamma P r
\end{equation}
sum:
\begin{equation}
(1-\lambda)\sum_{n=0}^{\infty} \lambda^n \gamma^{n+1} P^{n+1} Q = (1 - \gamma\lambda P)^{-1}(1-\lambda)\gamma P Q
\end{equation}
If you combine all 3 you get
\begin{align}
\mathcal{T}_{\lambda}Q &= r + (1-\lambda\gamma P)^{-1}\lambda\gamma P r + (1 - \gamma\lambda P)^{-1}(1-\lambda)\gamma P Q\\
&= r+ (1-\lambda\gamma P)^{-1}(\lambda \gamma P r + \gamma PQ - \lambda\gamma PQ)\\
&= r+ (1-\lambda\gamma P)^{-1}(\lambda \gamma P r + (\mathcal T)Q - r - \lambda\gamma PQ)\\
&= (1-\lambda\gamma P)^{-1}(r - \lambda \gamma P r + \lambda \gamma P r + (\mathcal T)Q - r - \lambda\gamma PQ)\\
&= (1-\lambda\gamma P)^{-1}( (\mathcal T)Q  - \lambda\gamma PQ + Q - Q)\\
&= Q + (1-\lambda\gamma P)^{-1}( (\mathcal T)Q  - Q)
\end{align}


What are good learning strategies for Deep Q-Network with opponents? I am trying to find out what are some good learning strategies for Deep Q-Network with opponents. Let's consider the well-known game Tic-Tac-Toe as an example:

How should an opponent be implemented to get good and fast improvements?
Is it better to play against a random player or a perfect player or should the opponent be a DQN player as well?

In a two player zero-sum game (if I win, you lose and vice-versa), then you can have a simple and efficient solution learning from self-play.

  How should an opponent be implemented to get good and fast improvements?

You don't need to think in terms of agent vs opponent, instead think in terms of coding both the players' goals into a single Q function. Score +1 if player A wins, -1 if player B wins, and zero for a draw. It is then player A's goal to maximise the score and player B's goal to minimise the score.

You can then implement and learn both player strategies in the same self-play learning session and same Q function, using minimax. In practice that means where in Q learning you generally pick the maximising action on next state to bootstrap Q values, in a minimax variant, you pick maximising or minimising action depending on whose turn it is. Otherwise the Q learning algorithm is the same as normal. I have implemented this, but not for DQN, just for tabular Q-learning - feel free to learn from, copy and/or re-use any part of that code.

  Is it reasonable to play against a random player, a perfect player or should the opponent be a DQN player as well?

The Q learner will learn to optimise against whichever player you make it play against. Against a random player, it will not necessarily learn to play well, just well enough to defeat the randomness. It may even make deliberate mistakes - such as not blocking a winning line - knowing it has a better chance to win due to random opponent.

Against a perfect player is possible with tic tac toe (because you can construct such a player), although there might be gaps in the trained Q values - game states never seen - which mean that an imperfect opponent could actually defeat the trained agent! In practice this does not scale to more complex unsolved games, because no perfect players exist.

Another DQN player should work fine. You would end up with two agents, each specialising in playing one player's turns. This is less efficient than a single minimax-based player, but no expected problems. It may be a preferred choice for some games, especially if they are not zero-sum.


What is a trap function in the context of a genetic algorithm? What is a trap function in the context of a genetic algorithm? How is it related to the concepts of local and global optima?

"Trap" functions were introduced as a way to discuss how GAs behave on functions where sampling most of the search space would provide pressure for the algorithm to move in the wrong direction (wrong in the sense of away from the global optimum).

For example, consider a four-bit function f(x) such that

f(0000) = 5
f(0001) = 1
f(0010) = 1
f(0011) = 2
f(0100) = 1
f(0101) = 2
f(0110) = 2
f(0111) = 3
f(1000) = 1
f(1001) = 2
f(1010) = 2
f(1011) = 3
f(1100) = 2
f(1101) = 3
f(1110) = 3
f(1111) = 4

That is, the fitness of a string is equal to the number of 1s in the string, except f(0000) is 5, the optimal solution. This function can be thought of as consisting of two disjoint pieces: one that contains the global optimum (0000) and another that contains the local optimum at its complement (1111). All points other than these have fitness values such that standard evolutionary algorithm dynamics would lead the algorithms to tend towards the local optimum at 1111 rather than the global optimum at 0000.

That's basically what is meant by a trap function. You can consider variations on this theme, but that's the gist of it.


Best way to create an image dataset for CNN I am creating a dataset made of many images which are created by preprocessing a long time series. Each image is an array of (128,128) and the there are four classes. I would like to build a dataset similar to the MNIST in scikit-learn.database  but I have no idea how to do it.

My aim is to have something that I can call like this:

(x_train, y_train), (x_test, y_test) = my_data()

Should I save them as figures? or as csv?
Which is the best way to implement this?

I found this solution and will be happy about any improvements or suggestions:

First, I create a random dataset of images, which are 28x28 pixels, and corresponding random labels (just for sake of clarification, I have another image dataset, this is just for explaining). Then I use a sklearn module for splitting the data:

import numpy as np
from sklearn.model_selection import train_test_split

# create the data and labels
def pixel_dataset(n_data=10, dpi = 28):

    ary = np.zeros((n_data, dpi, dpi))
    label = []

    for i in np.arange(n_data):
        labels =['a', 'b', 'c']
        ary[i,::] = np.reshape(np.array(np.random.randint(0, 255, 28*28)),(28,28))
        label.append(np.random.choice(labels, 1)[0])

    return ary, label

# create the test train split
def mydata(test_size=0.3):

    X, y = pixel_dataset()
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = test_size)
    return (X_train, y_train), (X_test, y_test)


In Fast R-CNN, how are input RoIs mapped to the respective RoIs in the feature map before RoI pooling? I've been reading the Fast R-CNN paper.
My understanding is that the input to one forward pass is the whole input image plus a list of RoIs (generated by selective search or another region proposal method). Then I understand that on the last convolution layer's feature map (let's call it FM), each corresponding RoI gets RoI-pooled, where now the corresponding ROIs are a rectangular (over height and width) slice of the FM tensor over all channels.
But I'm having trouble with two concepts:

How is the input RoI mapped to the corresponding RoI in FM? Each neuron comes from a very wide perceptive field, so, in a deep neural network, there's no way of making a 1:1 mapping between input neurons and neurons in the last convolution layer right?

Disregarding that I'm confused in point 1, once we have a bunch of RoIs in FM and we do the RoI pooling, we have N pooled feature vectors. Do we now run each of these through one FC network one by one? Or do we have N branches of FC networks? (that wouldn't make sense to me)

I have also read the faster R-CNN paper. In the same way, I'm also interested to know about how the proposed regions from RPN map to the input of the RoI pooling in the Fast R-CNN layers. Because actually those proposed regions live in the space of the input image, not in the space of the deep feature map.

The ROIs in the input space are mapped to the feature map space, by dividing it by the net stride at that layer. Say, in a network, after a sequence of four 2x2 pooling layers, your image is reduced to 1/16 of the original size. (A 32*32 image is reduced to 2x2) So, the bounding boxes in the original space are mapped to the feature space by dividing by the net stride, which is 16 here. But here's the catch, the ROI co-ordinates could be a floating point number when divided by 16, so, it is adjusted by either flooring it or ceiling it. This is why ROIPooling is quantized. There is a loss of information when you are rounding off the co-ordinates of the ROI. Nevertheless, now, each region is pooled to a single-size feature map, and each ROI is fed one-by-one to the following layers.
The Mask-RCNN paper brings a change to the mapping to the feature space, by not rounding off the co-ordinates, and by bilinear interpolation, and the loss of information is reduced, thus, the ROIAlign algorithm(which has been described here) performs better at object detection, than the quantized ROIPool algorithm.

As said, each fixed-size feature map vector is processed one-by-one.

Reference