Will CNNs kill CAPTCHAs or can they survive in an evolved form? CAPTCHAs, which are often seen in web applications, are working under the assumption, that they pose a challenge which a human can solve easily while a machine will most likely fail. Prominent examples are identifying distorted letters or categorizing certain objects in images.

Neural networks are threatening this approach, as they are capable of solving problems that are easy for humans and difficult for classic algorithms. Especially with the incredible results modern CNN architectures have achieved in image recognition during the last years, the established forms of CAPTCHAs won't be able to distinguish a human and a machine using a neural network anymore.

Is this the end of CAPTCHAs as we know them or are there evolved versions available or at least in the making that still pose a challenge to modern neural networks?

Clarification: I am talking about challenges that are feasible for use in web applications and do not have an unjustifiable impact on usability.

I think that captchas can be substituted or augmented by questions which require understanding of context, for example:

How many hands keep the rose?

Or

Which number of books under the bench and in hands?

These examples are simple, but they can be improved, for example, by generation of images with random  numbers of objects and their positions

It looks like it will be hard to use CNN to hack such kind of captchas, especially if we have a large amount of different objects and their combinations

In addition, it can be improved by adding more complicated logical questions to compositions on pictures


How to reduce over-fitting on training set? Currently I'm feeding spectrogram of audio to the CNN with 3 convolution.

Each convolution is followed by a max pool of filter size 2.

First -> 5x5x4

Second - > 5x5x8

Third - > 5x5x16

and final layer is a fully connected with 512 unit.

But while training with dropout of 0.25, getting train accuracy of 0.97 with 150 iterations.
and on test data accuracy is just 0.60.

Tell me how to improve the results.

Yes both train and test data come from same distribution.

The problem of overfitting is given that your model is being too flexible with the training data. The approaches you could take will be:

Download pretrained models (VGG-16) and use transfer learning.
Increase the value of your dropout (e.g. from 0.25 to 0.50).
Use data augmentation for your images.
Reduce the number of fully connected layers.


A few doubts on back propagation I'm having trouble wrapping my head around some details of neural nets and back prop.

For example's sake, consider the following net, where I have separated the 'neurons' into linear nodes plus activation (in this case sigmoid) nodes, more like a general computation graph. L2 is the squared loss function.

This is a 3 part question (parts 1 and 2 disregarding linear algebra / vectorization).

1. I want to confirm that I cannot just apply chain rule all the way from the L2 to the inputs and get the derivatives for weights at different layers.

For example:

But

For w5, at o1 I took the derivative with respect to w5. But for w1, at o1 I had to instead take the derivative with respect to ah1 to keep moving backwards.

2. I want to confirm that at any node that branches into more than one node at forward time (i.e. ah1), when I back prop, I have to add the derivatives of all it's branches: in this case do1/dah1 and do2/ah1.

3. If these 2 things are as I say, then how can I implement backprop in vectorized + linear algebra way without branching or using conditional logic.

The forward pass is easy:

x1 + x2 are a single input vector.
h1 + h2 are a matrix of 2 rows (number of output / units) and 2 columns (number of inputs).
ah1 + ah2 are a single function that can operate on vectors (i.e. 1/(1 + np.exp()))

The same for the next layer. So to do a forward pass, I just do:
L2(y, a_o(W_o @ a_h(W_h @ x))) (@ = matrix mul)

But for the back pass not so much, since I'd have to check which derivative to use at o1 and I'd have to sum o1 and o2 at ah1 and ah2.

http://neuralnetworksanddeeplearning.com/chap2.html this shows that in theory it can be done by always transposing the previous weight matrix, but I haven't fully understood it yet.

So as far as I understood your problem is of mathematical nature, especially about back-propagation derivatives. Just a quick clarification, the squared loss function is not the only cost function, there might be other types of cost function. Anyways, coming to the first part of the question:

You can just actually apply chain rule directly from L2 to wherever you want. The weights are independent variables, they don't depend on each other. So dw5/dw1 will turn out to be 0 i.e you are differentiating a constant, in this case w5 with respect to w1. Why do we write this

instead of this

is because we can differentiate the loss function L2 w.r.t to a single independent variable only (of our choice), you cannot differentiate it w.r.t to an independent variable and still go on differentiating w.r.t to another independent variable. Its purposeless since you want to find the variation of L2 w.r.t to a particular weight only.
Here are 2 links for better understanding of partial derivatives:
Intuitive reasoning behind the Chain Rule in multiple variables? and Chain Rule Intuition

Yes, you certainly have to add the derivatives of all the branches. Basically first we look from the frame of reference of o1 and o2. From this frame o1 and o2 are independent variables and L2 is dependent on them and so we differentiate L2 w.r.t them. Then we move a step back and check what is o1 and o2 dependent on. How you go about doing this simply experience and an understanding of the thing you are doing. There is no steadfast algorithm from a simple point of view.
The vectorized implementation requires you follow a certain framework, it will be very lengthy here to explain the framework, but I am linking you to certain lecture videos which will make you aware of the convention being followed for vectorized implementation. Just check week 2 and week 3.

Also the thing I was talking about having different L2's in the begining is important in the sense is that in the future we may come up with weights which are dependent on other weights and so now we may have to do a dw_n/dw_m step since w_n is dependent on w_m, but lets keep that for another day.
Hope this helps!

EDIT: this might give you a sense of why I am  calling variables as independent variables How do I know if my back-propagation is implemented correctly?


What are the best machine learning models for music composition? What are the best machine learning models that have been used to compose music? Are there some good research papers (or books) on this topic out there?
I would say, if I use a neural network, I would opt for a recurrent one, because it needs to have a concept of timing, chord progressions, and so on.
I am also wondering how the loss function would look like, and how I could give the AI so much feedback as they usually need.

There are a few of them. The most recent I've found is from DeepMind: The challenge of realistic music generation: modelling raw audio at scale. This video is a great analysis of it.


What's the difference between LSTM and GRU? I have been reading about LSTMs and GRUs, which are recurrent neural networks (RNNs). The difference between the two is the number and specific type of gates that they have. The GRU has an update gate, which has a similar role to the role of the input and forget gates in the LSTM.
Here's a diagram that illustrates both units (or RNNs).

With respect to the vanilla RNN, the LSTM has more "knobs" or parameters. So, why do we make use of the GRU, when we clearly have more control over the neural network through the LSTM model?
Here are two more specific questions.

When would one use Long Short-Term Memory (LSTM) over Gated Recurrent Units (GRU)?

What are the advantages/disadvantages of using LSTM over GRU?

On the same problems, sometimes GRU is better, sometimes LSTM.

In short, having more parameters (more "knobs") is not always a good thing. The training process needs to learn those parameters. There is a higher chance of over-fitting, amongst other problems.

The parameters are assigned specific roles inside either GRU or LSTM, so if that role is less important for a specific learning challenge, then it can be wasteful or even counter-productive to have the system attempt to learn values for them.

The only way to find out if LSTM is better than GRU on a problem is a hyperparameter search. Unfortunately, you cannot simply swap one for the other, and test that, because the number of cells that optimises a LSTM solution will be different to the number that optimises a GRU.

  When would one use Long Short-Term Memory (LSTM) over Gated Recurrent Units (GRU)?

When it proves better, experimentally. In some problem domains, this may be established and you can check. However, in other problem domains if either GRU or LSTM works well enough to solve a problem (and the superiority of either LSTM or GRU is not the main point of the work), then it may not so clear.


Neural network for reinforcement learning I’m using a simple neural network to solve a reinforcement learning problem.

The configuration is:

X-inputs: The current state
Y-outputs: The possible actions

Whenever the network yields a “good” solution, i “reward” the network by training it a number of times.

Whenever the network yields a “bad” or “neutral” solution, i ignore it.

This seems to be working somewhat, but from what i read, everyone else (in broad terms) seems to be using a 2 neural network configuration for similar tasks. (Policy network and value network)

Am i missing something? - and are there any obvious caveats of the “single network” method i am using?

Supplemental question: Are there other methods of “rewarding” a network, aside from simply training it?

Thanks,

From your description, it seems that you are implementing a version of an algorithm called REINFORCE. This algorithm belongs to a family called Policy Gradient methods, which directly optimizes the policy network $\pi(a_t|s_t)$ from rewards without ever worrying about estimating a value function. This type of algorithm is usually pretty slow and presents high variance.

The methods that you recognize as the ones using two neural networks correspond to a family called Actor-Critic methods. This type of algorithm uses the trajectories of rewards to estimate a value network $q(s_t,a_t)$ (called the critic), and, contrary to the previous family of methods, it uses the value network to train the policy network $\pi(a_t|s_t)$ (called the actor), instead of directly using the trajectory of rewards. This indirect dependence usually makes variance smaller and also learning faster. I recommend you have a look at chapter 13 of the book An Introduction to Reinforcement Learning.

So, to answer your first question: it seems you are missing the family of Actor-Critic methods. I recommend you learn about them since they are very powerful (e.g., read about DDPG or SAC).

About your second question, the standard method to "reward" a policy network is not by training it. Usually, you have a reward function $r(s_t,a_t)$ that depends on your current state $s_t$ and action $a_t$ and you modify the parameters $\theta$ of your network in such a way that the probability of an action $\pi(a_t|s_t)$ increases if the reward is positive or decreases if it is negative. More specifically, you perform stochastic gradient ascend steps like this one:

$$\theta_t\leftarrow\theta_t+\alpha\mathbb E\left[\sum_{k=t}^{T+t} \gamma^{k-t}r(s_k,a_k)\right]\nabla \log\pi(a_t|s_t,\theta_t)$$

What this formula says is that if in the time-step $t$ you take an action $a_t$ in the state $s_t$, wait $T$ steps and collect the rewards from $r(s_t,a_t)$ to $r(s_{t+T},a_{t+T})$, then, you should modify your parameters in the direction that the policy increases the most (i.e., $\nabla \log\pi(a_t|s_t,\theta_t)$) if the expected return $E\left[\sum_{k=t}^{T+t} \gamma^{k-t}r(s_k,a_k)\right]$ is positive, or in the direction that the policy decreases the most if that expected return is negative.


Should I apply image processing techniques to the inputs of convolution networks? After working for some time with feature-based pattern recognition, I am switching to CNN to see if I can get a higher recognition rate.

In my feature-based algorithm, I do some image processing on the picture before extracting the features, such as some convolution filters to reduce noise and segmentation into the foreground and background, and finally identifying and binarization of objects.

Should I do the same image processing before feeding data into my CNN, or is it possible to feed raw data to a CNN and expect that the CNN will adapt automatically without per-image-processing steps?

The whole interest of using deep learning-based solutions is that you don't have to do all those pre-processings, i.e. binarization, segmentation of background. CNNs, such as YOLO or FasterRCNN, can learn how to retrieve that information by themselves.


Can an RL algorithm trained in one environment be successful in a different one? Can an RL algorithm trained in one environment be successful in a different one?

For example, if I train a model to go through one labyrinth, could this model also go through a different but similar labyrinth or would it need a new training process?

By similar, I mean like these two:

But with this one being not similar:

Can an RL algorithm trained in one environment be succesfull on a different one?

Strictly the answer here is "no". You train an agent to solve a single environment. If a second environment is similar enough, you can probably re-train the agent on the new environment with little or no changes to the agent, and to get results just as good in the second agent.

In some cases, you could even start with the trained agent and "fine tune" it to the new environment. That probably would not work well with the labyrinth example though, especially if the start and end points are moved.

  Example: If I train a model to go through one labyrinth, could this model also go through different but similar labyrinth or would it need a new training process?

This could be subtly different. It is down to how you define the environment. It is possible to define an environment not as "this maze" but for example "all possible mazes in a 30x20 grid pattern". To do so, you need to make the maze configuration part of the environment's state.

Expanding from a singular environment example to all similar environments has a cost. In the labyrinth example, this is significant. A single 30x20 maze has 600 states, which is a trivial problem in RL. All possible mazes of the same size has closer to $2^{1200}$ states, which is much larger and requires different kinds of approaches, different RL methods.

You would expect to train on many example mazes (typically a randomly generated new one for each episode) and use some kind of generalisation - e.g. a neural network, maybe a CNN due to the grid design - when handling the value function or policy function. Training time for a single maze will be under a second, and the policy will be perfect. Training time for all possible mazes measured in hours or days and the policy will still get things wrong from time-to-time.


How can a system recognize if two strings have the same or similar meaning? How can a system recognize if two strings have the same or similar meaning?

For example, consider the following two strings

Wikipedia provides good information.
Wikipedia is a good source of information.

What methods are available to do this?

Getting the intent of the sentence is not an easy task. To get you started on what to do, have a look on word vectors. You can also download pre-trained word2vec models. They help in getting similarity of words and reasoning with words. To get the intent of a sentence, you can use LSTM.

Fun fact most NLP algorithms strip away punctuation with is sufficient for most cases, but to give a counter example.

The defendant, who looked apologetic, was found guilty.
The defendant who looked apologetic was found guilty.

They mean different things and are difficult to catch the intent even with the best algorithms.

PS: For those wondering the difference, in the second sentence it seems like there were two defendants, and it was the one who looked apologetic who was found guilty while the other walked away free.


Reinforcement Learning (RL) how to obtain $p(s',r|s,a)$ I am trying to study the book Reinforcement Learning: An Introduction (Sutton & Barto, 2018). In chapter 3.1 the authors state the following exercise

  Exercise 3.5 Give a table analogous to that in Example 3.3, but for $p(s',r|s,a)$. It should have columns for $s$, $a$, $s'$, $r$, and
  $p(s',r|s,a)$, and a row for every 4-tupel for which $p(s',r|s,a)>0$.

The following table and graphical representation of the Markov Decision Process is given on the next page.

I tried to use $p(s'\cup r|s,a)=p(s'|s,a)+p(r|s,a)-p(s' \cap r|s,a)$ but without a significant progress because I think this formula does not make any sense as $s'$ and $r$ are not from the same set. How is this exercise supposed to be solved?

EDIT: Maybe this exercise intends to be solved by using

$$p(s'|s,a)=\sum_{r\in \mathcal{R}}p(s',r|s,a)$$

and

$$r(s,a,s')=\sum_{r\in \mathcal{R}}r\dfrac{p(s',r|s,a)}{p(s|s,a)}$$

and

$$\sum_{s'\in\mathcal{S}}\sum_{r\in\mathcal{R}}p(s',r|s,a)=1$$

the resulting system is a linear system of 30 equation with 48 unknowns. I think I am missing some equations...

The function $r(s,a,s')$ gives the expected reward in each scenario, but not the distribution of rewards that lead to values $r_{search}$ and $r_{wait}$

The text explains that reward is $+1$ for each can found, and that different distributions of numbers of cans are expected when waiting as opposed to searching. However, it does not give any description of the actual distributions, just summarises them as the two expected rewards, and suggests $r_{search} \gt r_{wait}$

You have two main ways to answer the exercise:

Invent some parameters for the distributions of $r_{search}$ and $r_{wait}$ in order to split up single values of $p(s'|s,a)$ into multiple values of $p(s', r|s,a)$. E.g you could decide that $r_{search}$ consists of $0  \eta_0 + 1  \eta_1 + 2 \eta_2 + 3 \eta_3$ where $\eta_0, \eta_1, \eta_2, \eta_3$ are probabilities that sum to $1$ - each row that currently has $r_{search}$ as the output of $r(s,a,s')$ would then split into 4 rows with reward 0, 1, 2, 3 to complete the new table . . . $r_{wait}$ would need a different set of parameters.
Ignore the details of the distribution, move column $r(s,a,s′)$ to the left and call it $r$, changing $p(s|s,a)$ to $p(s', r|s,a)$. It might be all that's expected given the lack of information.

My personal opinion is that the authors want you to think about solution 1 - the only issue is that it requires you to invent some new parameters that were not provided. The ones I name are only a suggestion, they do not represent a specific "correct" answer in terms provided by the book, because the book omits those details.

As an example to start with, if you start solution 1, and use parameters as I have labelled them, you will end up with a first row looking like this:

$s\qquad \qquad a\qquad  \qquad  s'\qquad  \qquad   r \qquad       p(s', r| s, a)$
$high  \qquad \quad search  \qquad  high  \qquad \quad   0  \qquad   \alpha \eta_0$


How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions? I know how a machine can learn to play Atari games (Breakout): Playing Atari with Reinforcement Learning. With the same technique, it is even possible to play FPS games (Doom): Playing FPS Games with Reinforcement Learning. Further studies even investigated multiagent scenarios (Pong): Multiagent Cooperation and Competition with Deep Reinforcement Learning.
And even another awesome article for the interested user in the context of deep reinforcement learning (easy and a must-read for beginners): Demystifying Deep Reinforcement Learning.
I was thrilled by these results and immediately wanted to try them in some simple "board/card game scenarios", i.e. writing AI for some simple games in order to learn more about "deep learning". Of course, thinking that I can apply the techniques above easily in my scenarios was stupid. All examples above are based on convolutional nets (image recognition) and some other assumptions, which might not be applicable in my scenarios.
I have two main questions.

If you have a card game and the AI shall play a card from its hand, you could think about the cards (amongst other stuff) as the current game state. You can easily define some sort of neural net and feed it with the card data. In a trivial case, the cards are just numbered. I do not know the net type, which would be suitable, but I guess deep reinforcement learning strategies could be applied easily then.
However, I can only imagine this, if there is a constant number of hand cards. In the examples above, the number of pixels is also constant, for example. What if a player can have a different number of cards? What to do, if a player can have an infinite number of cards? Of course, this is just a theoretical question as no game has an infinite number of cards.

In the initial examples, the action space is constant. What can you do, if the action space is not? This more or less follows from my previous problem. If you have 3 cards, you can play cards 1, 2, or 3. If you have 5 cards, you can play cards 1, 2, 3, 4 or 5, etc. It is also common in card games, that it is not allowed to play a card. Could this be tackled with a negative reward?

So, which "tricks" can be used, e.g. always assume a constant number of cards with "filling values", which is only applicable in the non-infinite case (anyways unrealistic and even humans could not play well with that)? Are there articles, which examine such things already?

Instead of having the AI learn what action to take, you can alternatively train it to judge how "good" a position is. In order to determine what move to make, you don't ask the AI "This is the current state, what move should I make", you iterate through all possible moves, and feed the the resulting state into the AI asking "How good do you think this new state is?". You then chose the move with the resulting state that the AI liked best. (Or you probably even can combine this with a traditional MinMax approach)
I'm new to this area myself, but I'd guess you would use this approach when the action space is large, and in particular when most possible actions are not a legal option in most states.


Is PReLU superfluous with respect to ReLU? Why do people use the $PReLU$ activation?

$PReLU[x] = ReLU[x] + ReLU[p*x]$

with the parameter $p$ typically being a small negative number.

If a fully connected layer is followed by a at least two element $ReLU$ layer then the combined layers together are capable of emulating exactly the $PReLU$, so why is it necessary?

Am I missing something?

Lets assume we have 3 Dense layers, where the activations are $x^0 \rightarrow x^1 \rightarrow x^2$, such that $x^2 = \psi PReLU(x^1) + \gamma$ and $x^1 = PReLU(Ax^0 + b)$

Now lets see what it would take to conform the PReLU into a ReLU

$\begin{align*}
PReLU(x^1) &= ReLU(x^1) + ReLU(p \odot x^1)\\
&= ReLU(Ax^0+b) + ReLU(p\odot(Ax^0+b))\\
&= ReLU(Ax^0+b) + ReLU((eye(p)A + eye(p)b)x^0)\\
&= ReLU(Ax^0+b) + ReLU(Qx^0+c) \quad s.t. \quad Q = eye(p)A, \ \ c = eye(p)b\\
&= [I, I]^T[ReLU(Ax^0+b), ReLU(Qx^0+c)]\\
\implies x^2 &= [\psi, \psi][ReLU(Ax^0+b), ReLU(Qx^0+c)]\\
&= V*ReLU(Sx^0 + d) \quad V=[\psi, \psi], \ \ S=[A, Q] \ \ d=[b, c]
\end{align*}$

So as you said it is possible to break the form of the intermiediary $PReLU$ into a pure $ReLU$ while keeping it as a linear model, but if you take a second look at the parameters of the model, the size increase drastically. The hidden units of S doubled meaning to keep $x^2$ the same size $V$ also doubles in size. So this means if you dont want to use the $PReLU$ you are learning double the parameters to achieve the same capability (granted it allows you to learn a wider span of functions as well), and if you enforce the constraints on $V,S$ set by the $PReLU$ the number of paramaters is the same but you are still using more memory and more operations!

I hope this example convinces you of the difference


What are methods human actors use to imitate robots? Robot technology is usually thought from an engineering perspective. A human programmer writes a software this executed in a robot who is doing a task.

But what would happen, if the project is started with the opposite goal? The idea is, that the human becomes the robot by himself. That means, the human is using makeup to make his face more mechanically, buys special futuristic clothing which mirrors the light and imitates in a roleplay the working of a kitchen robot.

What are methods human actors use to imitate robots?

The great acting teacher Stella Adler wrote about mannerisms being a powerful tool for actors. Method acting in general focuses on natural performances based roughly on understanding the mindset of the character portrayed.

It's possible actors who have portrayed androids have observed industrial robots to inform their physicality, and many performances convey the idea, via movement, of a mechanical inner structure.  (It is often said that an "actor's body is their instrument".)

What is more interesting is actors trying to convey the cognitive structure of the androids.

With Arnold, and Terminator robots in general, the baseline performance is decidedly robotic, to convey their inhumanity. But the more advanced Terminators are able to mimic naturalistic human mannerisms, and even established human characters, to trick humans.

Lieutenant Data often used head motions, such as cocking his head slightly, to convey computation.  Here the character arc involved working to become more human, as this character draws heavily on Pinocchio, the wooden puppet that became a boy.  Overall Data's performance conveyed a lack of emotion, a definite reference to the logic-oriented Mr. Spock, although I recall episodes where Data experimented with "emotional circuits" and "humor circuits", where the output was intentionally inconsistent with natural human behavior.

Blade Runner, where the Tyrell Corporation's motto was "More Human than Human", presented the cutting edge Nexus-6 androids as having emotions, but, due to their artificially short life-spans, were portrayed as childlike in trying to reconcile extremely powerful feelings.  The Voight-Kampff Test, a form of Turing Test, used in the film to identify androids, relied on the emotional response to questions.

The key plot point of Do Androids Dream of Electric Sheep, the novel the film was based on, utilized what would be formalized as evolutionary game theory to hypothesize that empathy is a natural function of intelligence sufficiently advanced.  Deckard, who may or may not have been an android, and Rachel, who definitely was, are both capable of love.  This capacity informed their performances, to the extent that the androids came off as more human than the actual humans, due to the depth of their emotion.  This is also reflected in Blade Runner 2049 via the girlfriend-bot Joi, who us the most limited android, but the most human character in the film per her capacity to love (or at least simulate it.)

In the recent HBO Westworld reboot, the Androids replicate natural human mannerisms when playing their designated roles, but reset to more mechanical mannerisms when acting under their own agency.  This is reflected in Ex Machina, where the android mimics human emotions to pass a Turing Test and trick the human subject, only to revert to purely alien mannerisms after the android is free.  ("Alien" here used in the sense of non-human--it's possible the android is sentient as it seems to convey some degree of emotion in regarding the simulated human skin it will wear.)

The most interesting recent android performance may come from the recent Alien: Covenant where Michael Fassbender plays two identical androids, David and Walter, which have two distinct neural structures.  (David has the capacity to be creative, where Walter cannot.  In the film it is mentioned that David made people uncomfortable, so the creative functions were removed from subsequent models.)  The key difference in the performance seems to be that David demonstrates passion, and even emotions, where Walter is more clearly "robotic".

In general, the underlying approach of actors seems to have been to show the androids being distinct from humans, drawing a clear, though sometimes subtle, contrast.
Actors portraying androids have typically utilized robotic mannerisms to convey an artificial entity.


Feature Selection algorithm for a high featured data I have a cancer patient database from mass spectrometry on patients which consists of more than half million features. My task is to apply a feature selection algorithm to extract the most relevant features from it. My question is, which feature selection model would be the most appropriate in this case? Any suggestion from practical experience for these types of data is appreciated.

Have you tried any possibilities?

You have many possible approaches.

FeatureMiner (http://featureselection.asu.edu/index.php) or SkLearn (https://scikit-learn.org/) are popular options for your purposes.

The documentation from these two possibilities is also interesting.


Training Keras Towards Or Against Analog Value? For example, if I want to do a cat and mouse AI, the cat would wish to minimize the time taken for it to catch the mouse and the mouse would want to maximize that time. The time is analog and thus I cannot use a traditional Xy method but need another method that goes like this:

network.train_against_value(X, y, determinator)

Here, X is more like where the cat and mouse are. y is where the cat or mouse should move, and determinator is the time taken for the mouse to be caught, where the mouse wishes to maximize this value through its output of y and the cat wishes to minimize it. There is one Xy pair for each decision made by the cat and mouse, but one determinator throughout one game. Many games are played to train the AI.

Example: X: (300, 300, 200, 200) -> (mousex, mousey, catx, caty)

Y: (1,3) -> (xmove, ymove) direction, the numbers are then tuned by code for the actual movement to be always 1.

Determinator: 50 -> time for mouse to be caught in seconds

Where it would train so that with every X inputted it outputs a y so that determinator is minimum. Is there a method for train_towards_value as well? If there is no prebuilt method, how do I create one? What is the technical name for this kind of training?

I have two neural networks for the cat and mouse, where the cat is slower than the mouse but is larger and could eat the mouse. Just consider the mouse is difficult to control from the neural network because of inefficiencies so that it is possible for the cat to catch the mouse.

What is the technical name for this kind of training?

The name for the problem is Sequential Decision Making or Optimal Control.
There are a few different approaches you can take when solving this kind of problem. However, I think that the way that you are describing your project, Reinforcement Learning (RL) would match your approach the best.

I cannot use a traditional Xy method but need another method that goes like this:
network.train_against_value(X, y, determinator)

Although this method signature could probably be made to work by re-structuring one or other RL frameworks, it is more usual when using RL with neural networks to treat the experience-gathering and scoring systems - the core ideas behind RL - as a data generator for either a supervised learning problem or in some cases directly producing the output layer gradients.
One approach you could use is called Deep Q Networks (DQN) which effectively generates mini-batches for supervised learning of a neural network, based on gathering experiences.
In brief, DQN trains a neural network to predict what you are calling the "determinator", but that RL would call the "value" of each action. So you may move the action choice (y) to the input of the neural network, or alternatively predict multiple values (one output for each possble action) - the RL theory is the same for each approach here, it is an implementation detail. The agent (cat or mouse) would then pick the action with the highest predicted value by default (with the cat's values being the negative of the mouse's), trying other actions at random whilst training so as to learn all values. Whenever the agent gained new experience, it would add that to the training data so it could improve its predictions.
RL is a complex subject in its own right, and to begin understanding it properly you would do well to start by tackling even simpler problems that don't require neural networks or running two agents against each other. There is a good introductory book on the subject with the option to read a free PDF version: Reinforcement Learning: An Introduction (Sutton & Barto)


What is the role of embeddings in a deep recurrent Q network? When describing the model architecture for a deep recurrent q network, the authors of the paper Learning to Communicate with Deep Multi-Agent Reinforcement Learning

each agent consists of a recurrent neural network (RNN), unrolled for $T$ time-steps, that maintains an internal state $h$, an input network for producing a task embedding $z$, and an output network for the Q-values and the messages $m$. The input for agent $a$ is defined as a tuple of $\left(o_{t}^{a}, m_{t-1}^{a^{\prime}}, u_{t-1}^{a}, a\right)$.

Can someone explain what the purpose of the embedding layer is in this specific context?
Implementation can be found here.

The purpose of the input network is to embed the input tuple into a state/task representation, that can then be fed into the RNN hidden state at each time step.
$(o^a_t,m^a′_{t−1},u^a_{t−1},a)$ (input) $\rightarrow$ input network (embedding) $\rightarrow$ $z_t$ (task representation)

According to to section 6.1 of the paper, the input is a tuple represented as $(o^a_t,m^a′_{t−1},u^a_{t−1},a)$. Each of these  terms is described in sec 3 as:

$o_t$ - The observation. The authors assume a POMDP

Two types of actions:

$u_t$ - An environment action selects by all the agents at each time step in exchange for a team reward
$m_t$ - A communication action, observed by other agent but has no direct impact on the reward or env

$a$ - The agent (This being a multi-agent DQN algorithm)

They form the input to the Deep Recurrent Q-Network architecture.
The purpose of the embedding network is to receive a tuple of these inputs and produce a state
embedding $z$. This state embedding is then fed  into a hidden state $h^a_{t-1}$ of the RNN.
Though the authors refer to it as an input network that produces embedding, in practice, they use different embedding functions for each of these inputs. The final task/state embedding $z_t^a$ is expressed as a sum:
$$
z_t^a = \text{MLP}(o_t^a) + \text{MLP}(m_{t-1}) + \text{LookupTable}(u_{t-1}) + \text{LookupTable}(a)
$$
The summed embeddings are all of the same size.
This answer makes an assumption that by "embedding layer" you meant the input embedding network. Since the paper makes no reference to a single embedding layer in the model architecture.


Is there a possibility that there is no relationship between some inputs and outputs? I'm doing machine learning projects. I took a look at many datasets I worked with, mostly there are already famous datasets that everyone uses.

Let's say I decided to make my own dataset. Is there a possibility that my data are so random so that no relationship exists between my inputs and outputs? This is interesting because if this is possible, then no machine learning model will achieve to find an inputs outputs relationship in the data and will fail to solve the regression or classification problem.

Moreover, is it mathematically possible that some values have absolutely no relationship between them? In other words, there is no function (linear or nonlinear) that can map those inputs to the outputs.

Now, I thought about this problem and concluded that, if there is a possibility for this, then it will likely happen in regression because maybe the target outputs are in the same range and the same features values can correspond to the same output values and that will confuse the machine learning model.

Have you ever encountered this or a similar issue?

Of course, it's possible to define a problem where there is no relationship between input $x$ and output $y$. In general, if the mutual information between $x$ and $y$ is zero (i.e. $x$ and $y$ are statistically independent) then the best prediction you can do is independent of $x$. The task of machine learning is to learn a distribution $q(y|x)$ that is as close as possible to the real data generating distribution $p(y|x)$.

For example, looking at the common cross-entropy loss, we have
$$
\begin{align}
H(p,q) = -\mathbb{E}_{y,x \sim p}\left[\log q(y|x)\right] & = \mathbb{E}_{x\sim p}\left[\text{H}(p(y|x)) + \text{D}_{\text{KL}}(p(y|x)\|q(y|x))\right]  \\
& = \text{H}(p(y)) + \mathbb{E}_{x \sim p}\left[\text{D}_{\text{KL}}(p(y)\|q(y|x))\right],
\end{align}
$$
where we have used the fact that $p(y|x)=p(y)$ since $y$ and $x$ are independent. From this, we can see that the optimal predicted distribution $q(y|x)$ is equal to $p(y)$, and actually independent of $x$. Also, the best loss you can get is equal to the entropy of $y$.


Is there a trade-off between flexibility and efficiency? A "general intelligence" may be capable of learning a lot of different things, but possessing capability does not equal actually having it. The "AGI" must learn...and that learning process can take time. If you want an AGI to drive a car or play Go, you have to find some way of "teaching" it. Keep in mind that we have never built AGIs, so we don't know how long the training process can be, but it would be safe to assume pessimistic estimates.

Contrast that to a "narrow intelligence". The narrow AI already knows how to drive a car or play Go. It has been programmed to be very excellent at one specific task. You don't need to worry about training the machine, because it has already been pre-trained.

A "general intelligence" seems to be more flexible than a "narrow intelligence". You could buy an AGI and have it drive a car and play Go. And if you are willing to do more training, you can even teach it a new trick: how to bake a cake. I don't have to worry about unexpected tasks coming up, since the AGI will eventually figure out how to do it, given enough training time. I would have to wait a long time though.

A "narrow intelligence" appears to be more efficient at its assigned task, due to it being programmed specifically for that task. It knows exactly what to do, and doesn't have to waste time "learning" (unlike our AGI buddy here). Instead of buying one AGI to handle a bunch of different tasks poorly, I would rather buy a bunch of specialized narrow AIs. Narrow AI #1 drives cars, Narrow AI #2 plays Go, Narrow AI #3 bake cakes, etc. That being said, this is a very brittle approach, since if some unexpected task comes up, none of my narrow AIs would be able to handle it. I'm willing to accept that risk though.

Is my "thinking" correct? Is there a trade-off between flexibility (AGI) and efficiency (narrow AI), like what I have just described above? Or is it theoretically possible for an AGI to be both flexible and efficient?

The cleanest result we have on this issue is the "no free lunch" theorem. Basically, in order to make a system perform better at a specific task, you have to degrade its performance on other tasks, and so there is a flexibility-efficiency tradeoff.

But to the broader question, or whether or not your thinking is correct, I think it pays to look more closely at what you mean by a "narrow intelligence." The AI systems that we have that play Go and drive cars did not pop into existence able to do those things; they slowly learned how through lots and lots of training examples and a well-chosen architecture that mirrors the problem domain.

That is, "neural networks" as a methodology seems 'general' in a meaningful way; one could imagine that a general intelligence could be formed by solving the meta-learning problem (that is, learning the architecture that best suits a particular problem while learning the weights for that problem from training data).

Even in that case, there will still be a flexibility-efficiency tradeoff; the general intelligence that's allowed to vary its architecture will be able to solve many different problems, but will take some time to discover what problem it's facing. An intelligence locked into a particular architecture will perform well on problems that architecture is well-suited for (better than the general, since it doesn't need to discover) but less well on other problems it isn't as well-suited for.


Why does my model overfit on pseudo-random numbers training data? I am trying to predict pseudo-random numbers using the past numbers with a multiplayer perceptron. The error while training is very low. However, as soon as I test it with a test set, the model overfits and returns very bad results. The correlation coefficient and error metrics are both not performing well.

What would be some of the ways to solve this issue?

For example, if I train it with 5000 rows of data and test it with 1000, I get:

Correlation coefficient                  0.0742
Mean absolute error                      0.742
Root mean squared error                  0.9407
Relative absolute error                146.2462 %
Root relative squared error            160.1116 %
Total Number of Instances             1000

As mentioned, I can train it with as many training samples as I want and still have the model overfits. If anyone is interested, I can provide/generate some data and post it online.

Simply said, predicting pseudo random number is just not possible for now. Pseudo random numbers generated now have a high enough "randomness" so that it cannot be predicted. Pseudo random numbers is the basis of modern cryptography which is widely used in the world wide web and more. It may be possible in the future through faster computers and stronger AI, but for now it is not possible. If you train a model to fit on pseudo random numbers, the model will just overfit and thus creating a scenario as shown in the question. The training loss will be very low while test loss will be extremely high. The model will just "remember" the training data instead of generalising to all pseudo random numbers, thus the high test loss.

Also, as a side note, loss is not represented by %, instead it is just a raw numeric value.

See this stack exchange answer for details.


What is the meaning of Model(s, a) in the prioritized sweeping algorithm? I'm reading the book "Reinforcement Learning: An Introduction" (by Andrew Barto and Richard S. Sutton).

The authors provide the pseudocode of the prioritized sweeping algorithm, but I do not know what is the meaning of Model(s, a). Does it mean that Model(s, a) is the history of rewards gained when we are in state s and the action a is taken?

Does R, S_new = Model(s,a) mean that we should take a random sample from rewards gained in state s and action a is taken?

I think pseudocode was made for tabular case with an assumption of deterministic environment. $Model(s, a)$ would then be a table with information of the next state and reward after taking action $a$ from state $s$. The size of that table would be same as the size of Q table. Because the environment is deterministic you wouldn't take a random sample because there is only one possible transition so you would take the transition remembered in model table.


What kind of body (if any) does intelligence require? In the mid 1980s, Rodney Brooks famously created the foundations of "the new AI". The central claim was that the symbolist approach of 'Good Old Fashioned AI' (GOFAI) had failed by attempting to 'cream cognition off the top', and that embodied cognition was required, i.e. built from the bottom up in a 'hierarchy of competances' (e.g. basic locomotion -> wandering around -> actively foraging) etc.

I imagine most AI researchers would agree that the 'embodied cognition' perspective has now (at least tacitly) supplanted GOFAI as the mainstream.

My question takes the form of a thought experiment and asks: "Which (if any)  aspects of 'embodied' can be relaxed/omitted before we lose something essential for AGI?"

This is something of an orthogonal answer, but I think Brooks didn't go about his idea the right way. That is, subsumption architecture is one in which the 'autopilot' is replaced by a more sophisticated system when necessary. (All pieces receive the raw sensory inputs, and output actions, some of which turn off or on other systems.)

But a better approach is the normal hierarchical control approach, in which the target of a lower level system is the output of a higher level system. That is, the targeted joint angle of a robot leg is determined by the system that is trying to optimize the velocity, which is determined by a system that is trying to optimize the trajectory, which is determined by a system that is trying to optimize the target position, and so on.

This allows for increasing level of complexity while maintaining detail and system reusability.

That said, I don't think you actually need what one would naively call 'embodied cognition' in order to get the bottom-up hierarchy of competencies that Brooks is right to point towards. The core feature is the wide array of inputs and outputs, which are understood in a hierarchical fashion that allows systems to be chained together vertically. I think you could get a functional general intelligence whose only inputs and outputs involve going through an Ethernet cable, and doesn't have anything like a traditional body that it actuates or senses through. (This is a claim that the hierarchical structure is what matters, not the content of what we use that structure for.)

(The main place to look for more, I think, is actually a book about human cognition, called The Control of Perception by William T. Powers.)


Create captions based on a series of images I'd like to generate subtitles for a silent film. Is there an open source project out there capable of creating captions based on a series of images (such as a scene from a movie)?

EDIT: thanks for the comments below. To clarify, what i'm looking for is an algorithm which can generate a caption for a sequences of images within a movie  describing what happens in the sequence. This is for preliminary research, so accuracy is less important.

What you might want to look for is called video captioning. Earlier examples from this line of research is:

Venugopalan et. al. Sequence to Sequence – Video to Text, in ICCV 2015
Pasunuru et.al. Multi-Task Video Captioning with Video and
Entailment Generation, in ACL 2017

Below is a screenshot of the results (positive and negative) reported in those papers:

For the ICCV paper, it's not hard to find some implementations, e.g. here.

For more recent results, I would suggest to look into the ActivityNet 2017 Challenge - dense captioning or its 2018 version. Some winning solutions include:

Jointly Localizing and Describing Events for Dense Video Captioning
RUC+CMU: System Report for Dense Captioning Events in Videos

However I am not sure whether any open-source implementation has been released.


Understanding lemma 2 of the "Trust Region Policy Optimization" paper In the Trust Region Policy Optimization paper, in Lemma 2 of Appendix A, I did not quite understand deriving inequality (31) from (30), which is:

$$\bar{A}(s) = P(a \neq \tilde{a} | s) \mathbb{E}_{(a, \tilde{a}) \sim (\pi, \tilde{\pi})|a \neq  \tilde{a}} \left[ A_{\pi}(s, \tilde{a}) - A_{\pi}(s,a) \right]$$
$$|\bar{A}(s)| \le \alpha. 2 \max_{s,a} |A_{\pi}(s,a)|$$

Would you mind let me know how the inequality is derived?

We can start with equation (30):

$$
\bar{A}(s) = P(a \neq \tilde{a}) \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]
$$

Taking the absolute value of both sides, the equality remains true. We can pull the probability term out of the absolute value since it is guaranteed to be nonnegative.

$$
|\bar{A}(s)| = P(a \neq \tilde{a}) |\mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]|
$$

By Definition 1, $P(a \neq \tilde{a}) \leq \alpha$. Substituting this definition in, we get:

$$
|\bar{A}(s)| \leq \alpha \cdot |\mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [A_\pi(s, \tilde{a}) - A_\pi(s, a)]|
$$

By Jensen's Inequality, we can take the absolute value inside the expectation.

$$
|\bar{A}(s)| \leq \alpha \cdot \mathbb{E}_{(a,\tilde{a})\sim(\pi,\tilde{\pi}|a\neq\tilde{a})} [|A_\pi(s, \tilde{a}) - A_\pi(s, a)|]
$$

The expectation of a random variable is always upper bounded by the max value of that variable.

$$
|\bar{A}(s)| \leq \alpha \cdot \max_{a,\tilde{a}|a\neq\tilde{a}} |A_\pi(s, \tilde{a}) - A_\pi(s, a)|
$$

This part is a little strange, and I'm not sure if this is the logic that the authors followed, but it is still true. For any $a,b$, we have that $|a - b| \leq |a| + |b|$.

$$
|\bar{A}(s)| \leq \alpha \cdot \max_{a,\tilde{a}|a\neq\tilde{a}} (|A_\pi(s, \tilde{a})| + |A_\pi(s, a)|)
$$

For $a \neq \tilde{a}$, it must be that either $|A_\pi(s, \tilde{a})| \geq |A_\pi(s, a)|$ or vice versa. We can use this to replace the pair of advantage functions with 2 times the max of the two.

$$
|\bar{A}(s)| \leq \alpha \cdot 2 \max_{a} |A_\pi(s, a)|
$$

Now, if we take the max over $a$ and $s'$, our inequality still holds, since we are taking the maximum over a set that contains $s$. Making this substitution gives us (31).

$$
|\bar{A}(s)| \leq \alpha \cdot 2 \max_{a,s'} |A_\pi(s', a)|
$$


Why is "-0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp())" in Pytorch equivalent to the KL? I found this code for the loss function of a VAE:
-0.5 * torch.sum(1 + sigma - mu.pow(2) - sigma.exp())

From this link: https://debuggercafe.com/getting-started-with-variational-autoencoder-using-pytorch/
In PyTorch and this is apparently equivalent to the KL loss. mu is the mean parameter that comes out of the model and sigma is the sigma parameter out of the decoder. I don't see how this calculates the KL for the latent.

The code is correct. Since OP asked for a proof, one follows.
The usage in the code is straightforward if you observe that the authors are using the symbols unconventionally: sigma is the natural logarithm of the variance, where usually a normal distribution is characterized in terms of a mean $\mu$ and variance. Some of the functions in OP's link even have arguments named log_var.$^*$
If you're not sure how to derive the standard expression for KL Divergence in this case, you can start from the definition of KL divergence and crank through the arithmetic. In this case, $p$ is the normal distribution given by the encoder and $q$ is the standard normal distribution.
$$\begin{align}
D_\text{KL}(P \| Q) &= \int_{-\infty}^{\infty} p(x) \log\left(\frac{p(x)}{q(x)}\right) dx \\
&= \int_{-\infty}^{\infty} p(x) \log(p(x)) dx - \int_{-\infty}^{\infty} p(x) \log(q(x)) dx
\end{align}$$
The first integral is recognizable as almost definition of entropy of a Gaussian (up to a change of sign).
$$
\int_{-\infty}^{\infty} p(x) \log(p(x)) dx = -\frac{1}{2}\left(1 + \log(2\pi\sigma_1^2) \right)
$$
The second one is more involved.
$$
\begin{align}
-\int_{-\infty}^{\infty} p(x) \log(q(x)) dx
&= \frac{1}{2}\log(2\pi\sigma_2^2) - \int p(x) \left(-\frac{\left(x - \mu_2\right)^2}{2 \sigma_2^2}\right)dx \\
&= \frac{1}{2}\log(2\pi\sigma_2^2) + \frac{\mathbb{E}_{x\sim p}[x^2] - 2 \mathbb{E}_{x\sim p}[x]\mu_2 +\mu_2^2} {2\sigma_2^2} \\
&= \frac{1}{2}\log(2\pi\sigma_2^2) + \frac{\sigma_1^2 + \mu_1^2-2\mu_1\mu_2+\mu_2^2}{2\sigma_2^2} \\
&= \frac{1}{2}\log(2\pi\sigma_2^2) + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2}
\end{align}
$$
The key is recognizing this gives us a sum of several integrals, and each can apply the law of the unconscious statistician. Then we use the fact that $\text{Var}(x)=\mathbb{E}[x^2]-\mathbb{E}[x]^2$. The rest is just rearranging.
Putting it all together:
$$
\begin{align}
D_\text{KL}(P \| Q) &= -\frac{1}{2}\left(1 + \log(2\pi\sigma_1^2) \right) + \frac{1}{2}\log(2\pi\sigma_2^2) + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2} \\
&= \log (\sigma_2) - \log(\sigma_1) + \frac{\sigma_1^2 + (\mu_1 - \mu_2)^2}{2\sigma_2^2} - \frac{1}{2}
\end{align}
$$
In this special case, we know that $q$ is a standard normal, so
$$
\begin{align}
D_\text{KL}(P \| Q) &= -\log \sigma_1 + \frac{1}{2}\left(\sigma_1^2 +
\mu_1^2 - 1 \right) \\
&= - \frac{1}{2}\left(1 + 2\log \sigma_1- \mu_1^2 -\sigma_1^2   \right)
\end{align}
$$
In the case that we have a $k$-variate normal with diagonal covariance for $p$, and a multivariate normal with covariance $I$, this is the sum of $k$ univariate normal distributions because in this case the distributions are independent.
The code is a correct implementation of this expression because $\log(\sigma_1^2) = 2 \log(\sigma_1)$ and in the code, sigma is the logarithm of the variance.

$^*$The reason that it's convenient to work on the scale of the log-variance is that the log-variance can be any real number, but the variance is constrained to be non-negative by definition. It's easier to perform optimization on the unconstrained scale than it is to work on the constrained scale in $\eta^2$. Also, we want to avoid "round-tripping," where we compute $\exp(y)$ in one step and then $\log(\exp(y))$ in a later step, because this incurs a loss of precision. In any case, autograd takes care of all of the messy details with adjustments to gradients resulting from moving from one scale to another.


Predict next event based on previous events and discrete reward values Suppose, I have several sequences that include a series of text (the length of sequence can be varied). Also, I have some related reward value. however, the value is not continuous like the text. It has many missing values. Here is an example of the dataset.
Sequence 1        Sequence 2 .............. Sequence n
------------      ----------                -------------
Action  Reward    Action  Reward            Action  Reward
  A                 C                          D
  B       5         A                          B      6
  C                 A       7                  A
  C       6         B       10                 D
  A                 C                          A
  B       2         A                          B
  ..                ...                        ...
 ...               .....                      .....
  D       5         C      4                   D

Now I want to predict the next action based on the reward value. The idea is I want to predict the actions that leads to more rewards. Previously, I used only action data to predict the next action using LSTM and GRU. However, how could I use this reward value in this prediction? I was if thinking Reinforcement learning (MDP) could solve the problem. However, as the rewards are discrete, I am not sure if RL could do that. Also, is it possible to solve this problem with Inverse RL? I have some knowledge of deep learning. However, I am new to reinforcement learning. If anyone gives me some suggestion or provide me useful papers link regarding this problem, it could help me a lot.

Your problem does look like it could be a good match to reinforcement learning, or at least the related idea of contextual bandits. Whether or not it would be a good match to the full reinforcement learning algorithm depends on whether any of the data you are processing could be considered part of an environment state, and whether or not that state evolves based on rules that an agent could learn to take advantage of.

Previously, I used only action data to predict the next action using LSTM and GRU. However, how could I use this reward value in this prediction?

There are a few different ways to do this using reinforcement learning theory. The simplest is to build a regression predictor that approximates a sum of future rewards (also known as the return or utility) depending on a proposed action from the current state. Then you could use the value function approximator (formal name for the predictor you just built) to predict results from each possible action and pick the maximising one. It is possible to learn such a value function from a historical dataset using methods such as Q learning.
The subject is too complex to teach from scratch in a single answer here. A good learning resource is Reinforcement Learning: An Introduction by Sutton & Barto, which the authors have made available for free.

However, as the rewards are discrete, I am not sure if RL could do that.

Yes it can. Reinforcement learning just requires that rewards in each situation follow a consistent distribution of values. Always returning discrete values is not a problem, neither is always returning the same value in the same situation. Randomness in the reward value - such as sometimes returning a discrete value and other times not in the same situation - is also OK. You can treat missing values as zero, since you are concerned only with the sum of received rewards, using zero when no value is available has no effect on what will be considered the optimal solution.

Also, is it possible to solve this problem with Inverse RL?

Probably not. Inverse RL is concerned with figuring out the parameters that an existing agent is working with by observing it. For instance you could use it to observe a creature's behaviour and figure out which rewards were more valuable to it. In your case you have the reward values, so you don't need to figure them out.
Caveat: You need to figure out what constitutes state in your environment. If there is some state that can be used for predictions, but the agent's behaviour never changes the state, then you may want to spend some time modelling your problem as a contextual bandit instead. Bandit algorithms are introduced in the same book, Reinforcement Learning: An Introduction, but only as much is needed to teach about the full RL problem - bandit solvers can get far more sophisticated than the book considers.
Note that if the history of agent actions impacts the reward (e.g. it is a matter of timing when to take the right action), then that history is part of the state, and you likely do have a full reinforcement learning problem to solve.


Is the bias also a "weight" in a neural network? I'm learning about how neural networks are trained. I understand how a neuron works, backpropagation, and all that. In neurons, there is a clear distinction between a "weight" and a "bias".
$$
Y= \sigma(\text{weight} * \text{input})+ \text{bias}
$$
However, all the sources I've found when you train the network you just adjust the weights. Not the bias.

However, they never mention what the bias should do, which leads me to think that you just merge all weights and biases in a $W$ vector and call it weights, even though there are also biases. Is that correctly understood?

Yes, it is not unusual to omit the bias by adding a neuron which always outputs a constant 1, which will then be multiplied by an appropriate weight to give the same formula as you would get using an explicit bias.
One notable text using this convention is Understanding Machine Learning: From Theory to Algorithms by  Shai Shalev-Shwartz and Shai Ben-David. In section 20.1 there is a diagram of a neural network where a neuron outputting a constant value is added to each layer which you might find helpful.
To understand why this works, suppose the outputs of the previous layer are $u_1, \dots, u_n, u_{n + 1}$, where $u_{n + 1}$ is always $1$. Then a neuron in the next layer (without a bias) computes
$$ \sigma\left(\sum_{i = 1}^{n + 1} w_i u_i \right) = \sigma\left(\sum_{i = 1}^n w_i u_i + w_{n + 1}\right),$$
where $\sigma$ is the activation function. So, the weight $w_{n + 1}$ just serves as the bias because it is multiplied by $u_{n + 1} = 1$.


How could AI solve planet's major problems? I had been reading that AI could solve planet's major problems. How could it be done? For example, how exactly could AI be applied to address climate change? What are examples of applications of AI to solve these problems?

There's indeed a lot of research work being done in this field.

Here are a few ways in which AI can help/is helping in fighting major problems:

Climate change

Identify deforestation and the rate at which it's happening using computer vision and help in fighting back based on how critical the rate is.The World Resources Institute had entered into a partnership with Orbital Insight on this.

Protecting Nature

Researchers and institutes are using computer vision to accurately identify total remaining members of extremely threatened species to observe their behavior and patterns that can help in protecting them, keep track and monitor at an individual level.
Environmental/ Research agencies are trying to detect sounds from ocean audio from which they can identify inhabiting fish and route the ships away from threatened habitats.

Energy

Optimise energy usage based on consumption in big companies to save energy for public use and in turn reduce energy overall demands on the grid.
Predict the demand for energy and ensure continuous supply matching the demand. For example, Google's Deepmind is in talks National Grid of UK on this.

Of course, these ideas might look too tiny or too broad at first sight, but I feel taking one step at a time and then quickly expanding the ideas into wider areas would be the way to go, like how DeepMind is doing it in the area of energy. Other areas like education, transportation, and healthcare are seeing lots of activity with the involvement of AI too.

For further reading, here's what World Economic Forum thinks about how AI can help solve world's problems.


Why can't computers be random? I talked with a graduate computer science who said one challenge of making artificial human-like is making random decisions, and that computers can't be random, that they always need a "seed." But, if a computer's outcomes are determined by the chaotic movements of electrons, it doesn't seem like it should be difficult to program inherent uncertainty into a computer. So, what exactly is stopping people from harnessing this basic component of reality to allow artificial intelligence to make randomized decisions? I mean, all you'd need is different neural pathways that rely on the superposition of electrons, and that's it.

Computers (the processor in combination with the memory) are designed to be deterministic.  Otherwise no software would ever work, because the computer would be executing it randomly.

The computer's outcomes are not determined by the chaotic movements of electrons, but by the much strong deterministic currents and voltages between the transistors.  A digital machine is, simply speaking, not affected by noise.  The noise is always present,  but 0.13 volts or whatever gets rounded to 0 V (logic 0) and 3.02 volts or whatever gets rounded to 3.3 V (logic 1).

It is however possible to take advantage of the chaotic movement of electrons as well.  This is done in special hardware called "hardware random number generators", (some use different forms of true randomness such as nuclear decays).


Should we fear an AGI if it will be equivalent to a human? It seems to me that the first AGIs ought to be able to perform the same sort and variety of tasks as people, with the most computationally strenuous tasks taking an amount of time compared to how long a person would take. If this is the case, and people have yet to develop basic AGI (meaning it's a difficult task), should we be concerned if AGI is developed? It would seem to me that any fears about a newly developed AGI, in this case, should be the same as fears about a newborn child.

There are basically two worries:

If we create an AGI that is a slightly better AGI-programmer than its creators, it might be able to improve its own source code to become even more intelligent. Which would enable it to improve its source code even more etc. Such a selfimproving seed AI might very quickly become superintelligent.

The other scenario is that intelligence is such a complicated algorithmic task, that when we finally crack it, there will be a significant hardware overhang. So the "intelligence algorithm" would be human level on 2030 hardware, but we figure it out in 2050. In that case we would immediately have superintelligent AI without ever creating human level AI. This scenario is especially likely because development often requires a lot of test runs to tweak parameters and try out different ideas.


What are the criteria for choosing Turing award winners? Why does not a researcher like Geoffrey Hinton with his valuable works in machine learning (especially neural networks) get Turing award?

The ACM A.M. Turing Award is an annual prize given by the Association
  for Computing Machinery (ACM) to "an individual selected for
  contributions of a technical nature made to the computing community".
  It is stipulated that the contributions "should be of lasting and
  major technical importance to the computer field". The Turing Award is
  generally recognized as the highest distinction in computer science
  and the "Nobel Prize of computing".


Why does the policy network in AlphaZero work? In AlphaZero, the policy network (or head of the network) maps game states to a distribution of the likelihood of taking each action. This distribution covers all possible actions from that state.

How is such a network possible? The possible actions from each state are vastly different than subsequent states. So, how would each possible action from a given state be represented in the network's output, and what about the network design would stop the network from considering an illegal action?

The output of the policy network is as described in the original paper:

  A move in chess may be described in two parts: selecting the piece to move, and then
  selecting among the legal moves for that piece. We represent the policy π(a|s) by a 8 × 8 × 73
  stack of planes encoding a probability distribution over 4,672 possible moves. Each of the 8×8
  positions identifies the square from which to “pick up” a piece. The first 56 planes encode
  possible ‘queen moves’ for any piece: a number of squares [1..7] in which the piece will be
  moved, along one of eight relative compass directions {N, NE, E, SE, S, SW, W, NW}. The
  next 8 planes encode possible knight moves for that piece. The final 9 planes encode possible
  underpromotions for pawn moves or captures in two possible diagonals, to knight, bishop or
  rook respectively. Other pawn moves or captures from the seventh rank are promoted to a
  queen.

So each move selector scores the relative probability of selecting a piece in a given square and moving it in a specific way. For example, there is always one output dedicated to representing picking up the piece in A3 and moving it to A6. This representation includes selecting opponent pieces, selecting empty squares, making knight moves for rooks, making long diagonal moves for pawns. It also includes moves that take pieces off the board or through other blocking pieces.

The typical branching factor in chess is around 35. The policy network described above always calculates discrete probabilities for 4672 moves.

Clearly this can select many non-valid moves, if pieces are not available, or cannot move as suggested. In fact it does this all the time, even when fully trained, as nothing is ever learned about avoiding the non-valid moves during training - they do not receive positive or negative feedback, as there is never any experience gained relating to them. However, the benefit is that this structure is simple and fixed, both useful traits when building a neural network.

The simple work-around is to filter out impossible moves logically, setting their effective probability to zero, and then re-normalise the probabilities for the remaining valid moves. That step involves asking the game engine for what the valid moves are - but that's fine, it's not "cheating".

Whilst it might be possible to either have the agent learn to avoid non-valid moves, or some clever output structure that could only express valid moves, these would both distract from the core goal of learning how to play the game optimally.


How to formulate discounted return in cartpole? I am trying to formulate a problem that aims to prolong the lifetime of the simulation, the same as the Cartpole problem. I aware that there are two types of return:

finite horizon undiscounted return (used for episodic problems)

$G = \sum_{t=0}^T R_t$

infinite horizon discounted return (used for non-episodic problems).

$G = \sum_{t=0}^\infty \gamma^t R_t$
However, I'm confusing that "Is Cartpole episodic task?". Ideally, the simulation lasts forever.  This is my final objective (prolonging the lifetime). But it still has some termination states. Should I introduce the termination state and use it with a discounted return like:
$G = \sum_{t=0}^T \gamma^t R_t$

It's not true that finite horizon MDP can't use a discount factor. Any discount factor $\gamma \leq 1$ is fine for finite horizon.
Whether or not cartpole is a finite or infinite horizon depends on the environment implementation. The default environment in openai gym uses $T=200$ as the horizon. This is customizable, and most papers I see which use cartpole as a test environment use $T=1000$ instead. The task is considered "solved" when the agent can reach $T$ timesteps consistently (e.g., the last 100 episodes have all reached $T$ timesteps).
If you want to treat cartpole as an infinite horizon task, that's fine too. Clearly you need $\gamma < 1$ here, and you can just $T$ to some arbitrary large number.


Can the opponent's turn affect the reward for a DQN agent action? I made an engine for a 2 players card game and now I am trying to make an environment similar to OpenAI Gym envs, to ease out the training.

I fail to understand this thing however:

If I use step(agentAction), I play the agent's turn in the game,
calculate the reward.
Play the opponent's turn (which will be either a random AI or a rule-based one).

Question:
Does the opponent's turn affect the calculated rewards? As far as I know, the reward should only be the result of the agent's action right?

Thank you.

Does the opponent's turn affect the calculated rewards?

Yes, in general it can. Obvious case, in a two player game where the opponent could win or lose on their turn, but has other options.

  As far as I know, the reward should only be the result of the agent's action right?

In a well-defined MDP, the reward should be a stochastic function of the current state and the agent's action. The stochastic part can include any changes due to an opponent player.

If the opponent player is random, or follows a well-defined and fixed policy, then you consider them part of the environment. So this requirement is met technically. The reward does only depend on current state and the agent's action. The actual result may happen on the opponent's turn, but that does not matter.

In a card game where the opponent's cards are hidden and affect their strategy, this may not strictly be the case, because the visible state will not determine the opponent's behaviour. The problem stops being an MDP, and starts being a POMDP. Whether or not that impacts the agent will depend on how much strategy relies on the hidden nature of these cards. In blackjack, there is little impact to not knowing an opponent's cards before they are played out - there is little difference between hidden cards and cards that are randomly determined after the agent plays. So you can get away with pretending it is a normal MDP. In poker, the knowledge of hidden cards is almost everything about the game, so a POMDP or other approach that tracks possible hidden state is required.

Note that learning to defeat a random or expert player is usually not the same as learning to play optimally (unless your expert player is already optimal). For that you may need self-play and an agent which learns both players' policies.


What is experience replay in laymen's terms? I've been reading Google's DeepMind Atari paper and I'm trying to understand the concept of "experience replay". Experience replay comes up in a lot of other reinforcement learning papers (particularly, the AlphaGo paper), so I want to understand how it works. Below are some excerpts.

  First, we used a biologically inspired mechanism termed experience replay that randomizes over the data, thereby removing correlations in the observation sequence and smoothing over changes in the data distribution.

The paper then elaborates as follows (I've taken a screenshot, since there are a lot of mathematical symbols that are difficult to reproduce):

What is experience replay and what are its benefits in laymen's terms?

In reinforcement learning (RL), an agent interacts with an environment in time steps. At each time step $t$, the agent and the environment are in some state $s_t$. From that state $s_t$, the agent chooses and executes an action $a_t$ and the environment emits a reward $r_t$ (which values the just taken action $a_t$). Finally, the agent and the environment move to the next state, $s_{t+1}$. This interaction proceeds until either the agent dies or some other termination criterion is met.

The goal of the agent is to obtain the highest amount of reward in the long run (that is, not just in the next time step, but in all successive time steps). To do that, ideally, the agent needs to find a way of behaving "optimally". In RL, the behaviour of the agent is called a "policy". An optimal policy is a policy that allows the agent to obtain the (expected) highest amount of reward in the long run.

In this context, we can describe a full and finite (in terms of time steps) interaction between an agent and an environment as a sequence (sometimes called a "rollout" or a "trajectory") of states, actions, rewards and next states. So, a rollout might look like this $$(s_t, a_t, r_t, s_{t+1}, a_{t+1}, r_{t+1}, s_{t+2}, \dots, s_{T-1}, a_{T-1}, r_{T-1}, a_{T}),$$ where $T$ is the last time step of the interaction between the agent and the environment. During the interaction between the agent and the environment, the agent might decide to store this "experience" in a "buffer" (e.g. an array), so that it can use it later (you will see below a use case).

The elements of this type of sequences are often temporally correlated. What does this mean? For example, suppose that states are frames of a video game (that is, each frame is a different state). In this context, successive frames (or states) are similar to each other, which mathematically means that they are correlated.

It turns out that neural networks (NNs) are able to approximate (almost) any function. In RL, a policy is also a function: it is a function from a state to an action (or probability distribution over actions). So, we can represent a policy using a NN. (Deep RL is essentially a combination of traditional RL algorithms, like Q-learning, with NNs).

Moreover, it also turns out that training a NN using back-propagation with data that is temporally correlated might lead the NN not to capture the essential characteristics of the data, which, in practice (during training), means that we are not able to find the NN that represents the optimal policy (or another function, e.g. $Q(s, a)$, used later to retrieve the policy). In such cases, we often say that the training of the NN is not stable.

In the case of RL, the data used to train such types of neural networks (which represent the policy, or other functions that are used in RL) are the "rollouts", which contain elements that are often temporally correlated. Hence, we can't just feed the NN with a rollout, in the same order that the elements (states, actions, rewards and next states) are collected. So, in order to use uncorrelated data to train an NN, we can randomly take tuples of the form $\langle s_h, a_h, r_h, s_{h+1} \rangle$ from the rollout (where $h$ is some time step between $t$ and $T$). For example, suppose we take (or "sample") $3$ tuples $\langle s_7, a_7, r_7, s_{8} \rangle$, $\langle s_{97}, a_{97}, r_{97}, s_{98} \rangle$ and $\langle s_{2}, a_{2}, r_{2}, s_{3} \rangle$. Given that these elements have been observed at quite different points in time, they are likely to be less correlated than e.g. $\langle s_7, a_7, r_7, s_{8} \rangle$, $\langle s_{8}, a_{8}, r_{8}, s_{9} \rangle$ and $\langle s_{9}, a_{9}, r_{9}, s_{10} \rangle$ (which are successive "tuples of experience").

In this context, "experience replay" (or "replay buffer", or "experience replay buffer") refers to this technique of feeding a neural network using tuples (of "experience") which are less likely to be correlated (given that "random sampling" procedure). The "buffer" part refers to a data structure (e.g. an array or list) that stores the trajectory (or rollout), that is, it stores the "experience" of the agent (hence the name "experience"). The "replay" refers to the fact that this "experience" is reused (or "replayed") by randomly sampling from it to train the NN.

See also this question Why exactly do neural networks require i.i.d. data? regarding the fact that NNs often require i.i.d. data.


If an image contains two distinct objects, should I create a copy of this image with distinct labels for each copy? Suppose we want to detect whether an object is one of the following classes: $\text{Object}_1, \text{Object}_2, \text{Object}_3$ and $\text{Person}$. Should the annotated images only contain bounding boxes for either a person or an object? In other words, suppose an image has both $\text{Object}_1$ and $\text{Person}$. Should you create a copy of this image where the first version only has a bounding box on the object and the second copy only has a bounding box on the person?

You should use both classes together. Let's say you use the method you proposed. Then they will be contradicting each other as one teaches the network to recognize people, not objects and the other teaches the network to recognizes objects not person. There is no need for seperation of the two classes, unless you are making two seperate classifier. Hope I can help you.


Explain the difference in graphical patterns between discriminator fake loss and generator loss in GAN In GAN (generative adversarial networks), let us take "binary cross-entropy" as the loss function for discriminator $$(overall \; loss = -\sum log(D(x_i)) -\sum log(1-D(G(z_i))) $$
$$ where \; x_i = real \; image \; pixel \; matrix$$
$$ and \; z_i = a \; vector \; from \; latent \; space$$.
Let us define discriminator real loss and fake loss:
$$ d_{fake \; loss} = -\sum log(1-D(G(Z)))$$
$$ d_{real \; loss} = -\sum log(D(x))$$
$$ d_{fake \; loss} \; implies \; discriminator \; loss \; against \; fake \; images$$
$$ d_{real \; loss} \; implies \; discriminator \; loss \; against \; real \; images$$
Generator Loss :
$$ g_{loss} = -\sum log(D(G(z_i)))$$
Since the functions are similar, we should be expecting some similarity in graphical patterns (i.e since none of the functions are inherently oscillatory, I expect that if one comes out to be oscillatory, the other one should be the same as well). But, If you refer to chapter 10 of the book "Generative Adversarial Networks with python by Jason Brownlee", we find some difference. The following are the graphs published in the book

Can anyone explain the difference in the plots between discriminator fake loss and generator loss (mathematically)?

Your statement that  we should be expecting some similarity in graphical patterns is not correct. The GAN loss takes the following form:
$$
\min_G \max_D V(D,G) = \mathbb{E}_{x \sim p_{data}(x)} [\log D(x)] + \\
+ \mathbb{E}_{z \sim p_z(z)} [\log (1 - D(G(z)))]\label{minimax}
$$
We want to maximize this loss w.r.t. D in order to distinguish between real and fake samples ($D(x)\rightarrow 1$ and $D(G(z))\rightarrow 0$), whereas the task of G is exactly the opposite. We want to minimize the function w.r.t. G so that the difference between real and generated data will be minimal. Thus, the problem becomes a minimax non-cooperative game. Here is a good explanation of the loss.
Training GANs requires finding a Nash equilibrium of a non-convex game with continuous, high dimensional parameters. GANs are typically trained using gradient descent techniques that are designed to find a low value of a cost function, rather than to find the Nash equilibrium of a game. Two models are trained simultaneously and each model updates its cost independently with no respect to another player in the game.
In other words, as soon as D becomes better, G becomes also better. Updating the gradient of both models concurrently cannot guarantee a convergence. For more information, see Improved Techniques for Training GANs and Wasserstein GAN.
Moreover, since D and G play a non-cooperative game, it can be shown that there are some cases when it is impossible to find a Nash equilibrium at all:


What is the difference between artificial intelligence and computational intelligence? Having analyzed and reviewed a certain amount of articles and questions, apparently, the expression computational intelligence (CI) is not used consistently and it is still unclear the relationship between CI and artificial intelligence (AI).

According to IEEE computational intelligence society

  The Field of Interest of the Computational Intelligence Society (CIS) shall be the theory, design, application, and development of biologically and linguistically motivated computational paradigms emphasizing neural networks, connectionist systems, genetic algorithms, evolutionary programming, fuzzy systems, and hybrid intelligent systems in which these paradigms are contained.

which suggests that CI could be a sub-field of AI or an umbrella term used to group certain AI sub-fields or topics, such as genetic algorithms or fuzzy systems.

What is the difference between artificial intelligence and computational intelligence? Is CI just a synonym for AI?

What is the difference between Artificial Intelligence and Computational Intelligence?

The short answer is that they are two parallel research efforts working on similar problems, but with different methodologies and histories. Essentially, they study similar things, but with different tools. In the modern context, computational intelligence tends to use bio-inspired computing, like evolutionary and genetic algorithms. AI tends to prefer techniques with stronger theoretical guarantees, and still has a significant community focused on purely deductive reasoning. The main area of overlap is in machine learning, especially neural networks.

The longer answer is that your source from 1948 says they are synonyms in part because it predates the split in the research community, which took place later.
The two communities have always some overlap in topics, but in my experience, mostly are skeptical of each other's methodologies, and mostly publish in separate journals. Some authors consider CI to be a subset of AI however, particularly those writing in the 1990s.
Example topics that are solidly in AI but definitely not in CI are logical and expert systems, and statistical approaches to machine learning like regression.
Example topics that are solidly in CI but perhaps not in AI (depending on whether one views CI as a subset of AI or not) are genetic programming, fuzzy logic, and ant colony optimization.
As a rule, AI-rooted techniques have better theoretical guarantees, and better developed theory in general (there are exceptions though). For example, Fuzzy Logic has been strongly criticized for the lack of a solid theoretical foundation (good modern summary here), as have genetic and evolutionary approaches (most famously, both lack a proof of convergence within finite time to a global optimum on a smooth surface, even though they do quite well in practice).
CI-rooted techniques nonetheless often see major performance advantages in specific problems (see, for instance, deep learning results), and tend to have a strong experimental and engineering tradition. The No Free Lunch theorems are often used to justify their use when theoretical certainty is missing. Basically, the theorems say that, in learning and optimization problems, a technique can only perform well on a problem by performing poorly on some other problem. CI authors argue that there are some problem domains in which their techniques work well (which must be true, because simpler algorithms like hill-climbing outperform them on simple problems).
Check out this paper for lots more references on CI, or this book for a list of core topics in the field.


Do the eigenvectors represent the original features? I've got a test dataset with 4 features and the PCA produces a set of 4 eigenvectors, e.g.,

EigenVectors: [0.7549043055910286, 0.24177972266822534, -0.6095588015369825, -0.01000612689310429]
EigenVectors: [0.0363767549959317, -0.9435613299702559, -0.3290509434298886, -0.009706951562064631]
EigenVectors: [-0.001031816289317291, 0.004364438034564146, 0.016866154627905586, -0.999847698334029]
EigenVectors: [-0.654824523403971, 0.2263084929291885, -0.7210264051508555, -0.010499173877772439]

Do the eigenvector values represent the features from the original dataset? E.g., is feature 1 & 2 explaining most of the variance in eigenvector 1?

Am I interpreting the results correct to say that features 1 and 2 are therefore the most important in my dataset since PC1 represents 90% of the variance?

I'm trying to map back to the original features but am unsure how to interpret the results.

The principal components (eigenvectors) correspond to the direction
  (in the original n-dimensional space) with the greatest variance in
  the data.

  The corresponding eigenvalue is a number that indicates how much
  variance there is in the data along that eigenvector (or principal
  component).

Thus, feature 2 is the most important (based on eigenvalue alone). Then feature 1. The other 2 features have little impact and theoretically could be removed as a part of your data reduction effort.

Also, it is important to point out that

  When performing PCA, it is typically a good idea to normalize the data
  first. Because PCA seeks to identify the principal components with the
  highest variance, if the data are not properly normalized, attributes
  with large values and large variances (in absolute terms) will end up
  dominating the first principal component when they should not.

IOW, if you didn't normalize your data then your PCA analysis is quite likely meaningless.

*The above quoted text is from http://www.lauradhamilton.com/introduction-to-principal-component-analysis-pca


Have GANs been used to solve regression problems? I've noticed that in the last 2 years GANs have become really popular. I know that initially they have been proposed for image classification but I was curious if any of you are aware of any papers where GANs are used to solve regression problems?

In reality GANs are not made for image classification, but for data generation, and they have gained popularity on image generation. They are also used for tabular data generation, see for example TGAN, or for time series generation, e.g. Quant GAN. You have even some application for the field of graphs and networking, e.g. NetGAN and GraphGAN.


Why is the "reward to go" replaced by Q instead of V, when transitioning from PG to actor critic methods? While transitioning from simple policy gradient to the actor-critic algorithm, most sources begin by replacing the "reward to go" with the state-action value function (see this slide 5).

I am not able to understand how this is mathematically justified. It seems intuitive to me that the "reward to go" when sampled through multiple trajectories should be estimated by the state-value function.

I feel this way since nowhere in the objective function formulation or resulting gradient expression do we tie down the first action after reaching a state. Alternatively, when we sample a bunch of trajectories, these trajectories might include different actions being taken from the state reached in timestep $t$.

So, why isn't the estimation/approximation for the "reward to go" the state value function, in which the expectation is also over all the actions that may be taken from that state as well?

When you say simple policy gradient, I assume you mean something like REINFORCE.

The main difference between actor-critic and REINFORCE-like algorithms is in how they estimate the reward to go:

in REINFORCE, you wait until a trajectory terminates to make any updates, and your estimator of the reward to go is the actual reward to go that was observed in the trajectory.
in actor critic algorithms, instead of using an entire trajectory to estimate a reward to go, you use the action value function (note that this way, you can compute updates at every time step). The reason why you use the action-value function is because at each transition, you have already committed to some action.

The benefit of the actor critic estimator is that it exhibits much less variance. REINFORCE estimators are Monte Carlo estimators, which are known to exhibit extremely high variance.

Now, the actor critic method in the slides you posted takes variance reduction one step further. Instead of estimating reward to go, it's estimating advantage -- that is, the difference between the current action value and your estimated state value. The state value function term doesn't depend on the action, so it doesn't affect the expected value of the policy gradient. However, it serves as a 'baseline', which helps reduce the variance of the reward to go estimator even further.


Reason for issues with correlation in the dataset in DQN From the paper Human level Control through DeepRL,  the correlation in the data causes instability in the network and may causes the network to diverge. I wanted to understand what does this instability and divergence mean ? And why correlated data causes this instability.

I wanted to understand what does this instability and divergence mean ?

These are with reference to learning curves for the neural network. If a neural network is stable and converges, it means that the value of the error or cost function reduces consistently over time and reaches a stable point of minimum error.

In practice this is often a noisy process and not smooth. There are degrees of noise that are expected and acceptable when solving real problems. However, an instable learning curve will oscillate wildly, and a divergent learning curve will get consistently worse error function during training.

A typical stable, converging learning curve, cost function versus training data consumed, might look like this:

Whilst an instable, diverging learning curve might look like this:

These are not using the same vertical scale - the lowest point of the unstable curve will typically be higher than most or even all of the stable curve.

  And why correlated data causes this instability.

This is because for gradient descent to work, it needs gradient samples that it uses on every weight update step to be unbiased estimates of a true gradient. In RL you have either an online learning process or non-stationary targets (and usually both), so you must use stochastic or mini-batch gradient descent, working with a few samples at a time. You need those samples to be independent, not related to each other other than by random chance, otherwise the gradient value will be biased and gradient descent will consistently make updates in the wrong overall direction.

A good way to illustrate the difference is to use a really simple example, using gradient descent updates to estimate a mean value (this is roughly equivalent to training a neural network with one neuron, with weight fixed to zero and learning a bias value to represent the mean of the target- no actual input is required).

Say we have an array of values from 0 to 200 inclusive (example code is in Python):

import numpy as np
train_y = np.arange(0, 201)

If this array is kept sorted, then sequential values are highly correlated. If you plot consecutive pairs against each other, you will get a straight line.

We can estimate the mean value by setting a "bias" value to some arbitrary number, and running an update rule based on MSE (between current bias and observed value):

mean_estimate = 0.0
alpha = 0.1
for y in train_y:
    mean_estimate += alpha * (y - mean_estimate)
print(mean_estimate)

This prints (roughly) $191$ as the estimate for the mean, almost double.

However, if we shuffle the array first, it removes the correlation. If you plot consecutive pairs against each other, you will get a scatter graph with no apparent pattern. Adding the one line np.random.shuffle(x) to do this changes the results radically:

mean_estimate = 0.0
alpha = 0.1
np.random.shuffle(x)
for y in train_y:
    mean_estimate += alpha * (y - mean_estimate)
print(mean_estimate)

We get much better estimates (typically between $90$ and $110$), closer to the true value of $100$, and not biased to be higher or lower (run it enough times and you would find the expected result of this algorithm is very close to the true value).

This is because in the first version of the code, the gradient of the error was not sampled fairly - it kept pointing "up" even for high estimates due to the correlation. In the shuffled version, gradients are likely to be in either direction depending only on the current estimate, and will appear roughly in the ratios necessary to find the correct value.

As an exercise you could extend this simple example with mini-batches and repeated "epochs" to show that the effect persists with those changes, and the shuffling is the most important change here for better estimates.


Which algorithm for scheduling race grid? I want to plot a schedule of races based on rules. Rules like "each team needs at least 2 races between their next race" and some teams (e.g. collegiate) need to be clumped near each other.

What would be the best algorithm to approach this? So far, all I've found is genetic algorithm. Are there any other alternatives I could look into?

What you're looking for is most likely constraint programming (CP). Essentially, with a CP model you declare a set of variables and a set of constraints (and an objective, optionally). Then a solver will solve your model and find a solution if one exists (if you had specified an objective, it will find the best solution).

Here is an example which is very silimar to your problem (a MiniZinc model which solves the problem is included). You can download MiniZinc and try it out for yourself.