Genetic algorithm: How to crossover 2D permutation? Each chromosome contains an array of genes, each gene contains a letter and a number, both letter and number can only exist once in each chromosome.

Parent A = {a,1}{c,2}{e,3}{g,4}
Parent B = {a,2}{b,1}{c,4}{d,3}

What would be the best crossover operator to create a child that doesn't break the rule described above?

First, store the two parent chromosomes into a sorted dictionary (in terms of implementation, std::map in C++ might be a good option) where the key is the letter and the value is a pair of ints (the second gene element). When you populate the map, add all the letters from each chromosome as keys and take 0 (or a negative number) to indicate that a gene with the corresponding letter does not exist in one of the parents.

Next, create a second map, this time with the number as a key. Iterate over the first map. If both parent chromosomes contain a gene with the same letter, the value field in the map would contain two positive numbers - pick one at random and insert the {number, letter} combination into the second map only if the number doesn't exist as a key. If the gene exists only in one parent, either pick the gene as is or choose to skip that gene altogether.

This would guarantee that 1) your genomes contain a {letter, number} gene only once and 2) the genes in the offspring's chromosomes would be automatically sorted by letter. If you don't need the genes to be sorted but still need them to be unique, you can use an unordered map (a hash table).

In your example, the map would look like this:

Mapped parent chromosomes
{a: (1,2)}
{b: (0,1)}
{c: (2,4)}
{d: (0,3)}
{e: (3,0)}
{g: (4,0)}

Offspring chromosome (OC)
{}

Where 0 indicates that the corresponding gene does not exist in that parent. Iterating over this table from top to bottom, you might end up doing the following:

Key a: pick 1; 1 is not a key in OC, so insert {1,a}
Key b: pick 1; 1 is a key in OC, so skip letter b
Key c: pick 4; 4 is not a key in OC, so insert {4,c}
Key d: choose to skip
Key e: pick 3; 3 is not a key in OC, so insert {3,e}
Key g: pick 4; 4 is a key in OC, so skip letter g

Final offspring chromosome:

{a,1}{c,4}{e,3}


Using different timesteps for features and target value I would like to know whether it's wrong; when working with time series data; to use daily prices as features and the price after 3 days as target.

Is this correct or should I use the next-day price as target and after training; predict 3 times; each time for one more day ahead(using the predicted value as a new feature)

Will these 2 approaches give similar results?

I don't know what kind of price data you're dealing with. I suppose the order of the data matters a lot, so my suggestion would be:

Use LSTM as it handles time series better
You can predict 3 consecutive numbers from an RNN as the next three days' predictions
Try regression first, it is likely it will not work (or just flatten the curves, depend on your data noise), then classification is an easier approach
Don't forget normalization


How do you calculate KL divergence on a three-dimensional space for a Variational Autoencoder? I'm trying to implement a variational auto-encoder (as seen in Section 3.1 here: https://arxiv.org/pdf/2004.06271.pdf).
It differs from a traditional VAE because it encodes its input images to three-dimensional latent feature maps. In other words, the latent feature maps have a width, height and channel dimension rather than just a channel dimension like a traditional VAE.
When calculating the Kullback-Liebler divergence as part of the loss function, I need the mean and covariance that is the output of the encoder. However, if the latent feature maps are three-dimensional, this means that the output of the encoder is three-dimensional, and therefore each latent feature is a 2D matrix.
How can I derive a mean and covariance from a 2D matrix to calculate the KL divergence?

Your three dimensional latent representation consists of two images of mean pixels and covariance pixels as shown in Fig. 3. Which represents a Gaussian distribution with the mean and covariance for each pixel in the latent representation. Each pixel value is a random variable.
Now, have a close look at KL-loss Eq. 3 and it's corresponding description in the paper:
$$\mathcal{L}_{KL} = \frac{1}{2 \times (\frac{W}{16} \times \frac{H}{16}) } \sum^M_{m = 1}[\mu^2_m + \sigma^2_m - \log(\sigma^2_m) - 1]$$

Finally, $M$ is  the  dimensionality  of  the  latent  features $\theta \in \mathbb{R}^M$ with  mean $\mu  = [\mu_1,...,\mu_M]$ and covariance matrix $\Sigma = \text{diag}(\sigma_1^2,...,\sigma_M^2)$, [...].

The covariance matrix is diagonal, thus all pixel values are independent of each other. That is the reason why we have this nice analytical form for the KL-divergence given by Eq. 3. Therefore you can treat your 2D random matrix simply as a random vector of size $M = \frac{W}{16} \times \frac{H}{16}$ ($\times 3$ if you like to include color dimension). The third dimension (RGB channel) can be considered independent as well, therefore it can be also flattened to a vector and appended. Indeed this is what is done in the paper indicated by the second half of the sentence from above:

that are reparameterized by via sampling from a standard multivariate Gaussian $\epsilon \sim \mathcal{N}(0,I_M)$, i.e. $\theta = \mu + \Sigma^{\frac{1}{2}}\epsilon$.


How can AI be used to design UI Interfaces? I'm very new to AI.  I read somewhere that AI can be used to create GUI UI/UX design. That has fascinated me for a long time. But, since I'm very new here, I don't have any idea how it can happen.

The usual steps to create the UI Design are:

Create Grids.
Draw Buttons/Text/Boxes/Borders/styles.
Choose Color Schemes.
Follow CRAP Principle (Contrast, Repeatition, Alignment, Proximity)

I wonder how can AI algorithms help with that. I know a bit of neural networking and the closest I can think of is the following two methods (Supervised Learning).

Draw grids manually and train the Software manually to learn proper styles until it becomes capable of giving modern results and design its own design language.
Take a list of a few websites (for example) from the internet and let the software learn and explore the source code and CSS style sheets and learn and program neurons manually until it becomes capable of making it's own unique styles.

If you see the use case, on higher level it seems to generate some visual output - the design but when seen at lower level, this design is output of some code.

One way we can do it is to train a neural network that learns to generate code which can be seen as some form of organized text. So now can be treated as a text generation problem on which you can find a lot of literature.

pix2code is one implementation that uses this idea and even expands it. In this paper the authors took it to another level, they also used the visual part - the GUI and built an architecture that takes both the code and the GUI as input and learns to generate code. So eventually it would be capable of generating code when a simple GUI was given.

Also there are some implementations where even the network could produce code even when a rough sketch was given.


How should I interpret this validation plot? Bellow I have a validation plot
How should I interpret this validation plot?
Is my data underfitting? What else can be seen from this?
Which one is the best?

What does it mean that the right line is growing and green line decrease (slightly) for example after 15?

Second random forrest

This is a sign of overfitting.

As you make your trees deeper, it becomes possible to "memorize" the data: each leaf of the tree is just a single point. The trees begin to learn patterns that do not exist. When you try out these patterns on new data (which is what cross-validation is imitating), then the patterns do not work, and your model fails to generalize.

The main piece of information to draw from this plot is that the optimum tree depth is about 15.


What kinds of techniques do autopilots of autonomous cars use? What kinds of techniques do autopilots of autonomous cars (e.g. the ones of Tesla) use? Do they use reinforcement learning? Which types of neural network architecture do they use?

They definitely don't use RL.

My guess is a mix of NN for segmentation, lidar, radar and how for perception.

Once object detection has been performed they use a trajectory generator and MPC.

There is an autonomous car class on Coursera that goes over this.


Using ML to analyze Facebook posts First of all, I should mention that I have a very basic knowledge of ML so I apologize if this question seems trivial or stupid.

I am working on a small personal project, basically an app that analyzes Facebook posts concerning movies and translates them into a rating (out of 100). The algorithm looks for keywords, the length of the post, etc.. to determine the individual rating, and then averages all the ratings among a user's FB friends to give the result. My question is, would I be able to drastically improve such algorithm by using ML or is it not worth it? If yes, what algorithms/techniques do you advise me to learn?

All help is appreciated!

for this kind of ml training, you will need a ton of data first, at least in the thousands. If you have a bot program that fetches those data for you, AI is the way to go. I'm not sure how else you would do it though.

To train the nn you will need the inputs(the post) and the targets(the rating you want it to output). The targets could be anything you want, like the ratio of likes to views, etc.

There are tons of ML libraries out there and I recommend keras as it is easy to learn for beginners, hope it helps :)


Is the definition of machine learning by Mitchell in his book "Machine Learning" valid? The definition machine learning is as follows:

  A computer program is said to learn from experience E with respect to some  task T and performance measure P, if its performance at task T, as measured by P, improves with experience E.

Here, we talk about what it means for a program to learn rather than a machine, and a program and a machine aren't equivalent, so this is a definition about "program learning" rather than "machine learning". How is this consistent?

Think of a computer as a Turing Machine--this idea is a model of computation, and all of modern computing is based on the Turing-Church thesis.

Machine and program can be interchangeable—at the end of the day, it's all algorithms, whether hard coded in the form of microchip, or in the form of software.  (Any microchip can be emulated as software.)

Pre-modern computers were mechanical in popular sense. Examples include Babbage's
 difference engine, and mechanical calculators in general.  These led to programmable mechanical calculators and electromechanical computers such as IBM's Harvard Mark I, based on Babbage's notion of an Analytic Engine.

In this context, Machine Learning may also connote software that runs on a machine (hardware) as opposed to human/animal learning, which utilizes a biological medium.

The etymology of "mechanics", and by extension, "machine" is worth looking at.

mechanisma (in the sense of "mechanism")
mechanicus (in the sense of "belonging to mechanics")
mechanema (in the sense of "a trick")

Mechanema is instructive in that math and engineering can be understood as the "trick to doing things". (Machination is not pejorative in this sense, as "noun of action from past participle stem of machinari 'contrive skillfully, to design; to scheme, to plot,'"—one can plot the course of a celestial body.)

Early uses of the mech- root

Aristotle's Μηχανικά ("Mechanical Problems"*)

Euler's Mechanica (Euler was referring to Classical Mechanics, an analytic and predictive science made possible by calculus, which is based on functions.)


Target values of 0.1 for 0 and 0.9 for 1 for sigmoid I recently read an article about neural networks saying that, when using sigmoid as activation function, it's advised to use 0.1 as target value instead of 0, and 0.9 instead of 1. This was to avoid "saturation effects". I only understood is halfway, and was hoping someone could clarify a few things for me:

Is this only the case when the output is boolean (0 or 1), or will it also be the case for continual values in the range between 0 and 1. If so, should all values be scaled to the interval [0.1, 0.9]?
What exactly is the problem of output 0 or 1? Does it have something to do with the derivative of sigmoid being 0 when it's value is 0 or 1? As I understood it weights could end up approaching infinity, but I didn't understand why.
Is this the case only when sigmoid is used in the output layer (which it rarely is, I believe), or is it also the case when sigmoid is used in hidden layers only?

Derivative of the sigmoid curve is 0 when the output is 0 or 1 as you can see from the image above. The technique you are referring to is called label-smoothing which is used in various applications (e.g. GANs) but I can see how it would be applicable here also, by helping to avoid 0-gradients saturating learning.

To answer your third question, sigmoids are rarely used in the intermediate layers of networks these days. They have been replaced by ReLUs (or variants of ReLU) for this exact reason - sigmoids are prone to causing 'vanishing gradients' where the gradient becomes 0 and therefore does not get backpropagated any further. ReLUs alleviate this problem by always providing a gradient of 1 for positive input values.


What are some simple open problems in multi-agent RL that would be suited for a bachelor's thesis? I've decided to make my bachelor thesis in RL. I am currently struggling to find a good problem. I am interested in multi-agent RL with the dilemma between selfishness and cooperation.
I only have 2 months to complete this and I'm afraid that multi-agent RL is too difficult and I don't have the knowledge and time to nicely learn this topic.
What are some simple open problems in multi-agent reinforcement learning that would be suited for a bachelor's thesis?
I've only done applied the Q-learning algorithm to solve a text-based environment in OpenAI's gym.

I have several undergraduates working on multiagent deep RL problems for their theses, but most of them have been working for 8-9 months. 2 might be a stretch.
Good multiagent deep RL problems for a bachelor's thesis might look something like:

Pick an older video game, which has been studied using Deep RL, but not in depth. Right now my students have been liking Nintendo 64 games.
Read the papers that study this game already.
Pick one of the described approaches and reproduce the paper's results in your own system.
Pick one of the parameters that the paper does not explore changing, and see what happens as you change it.

This probably does not lead to a publishable result, but it is real science and can make for a fine undergraduate thesis.
A slightly harder project, which may require more time, would be to examine the "future work" sections of these papers, and perform one of the experiments suggested there. These experiments often lead to small publishable results.


How to perform insect classification given two images of the same insect? I'm relatively new to image classification. Currently, I am trying to classify insect images, using a convolutional neural network (CNN).
When I ask a human expert to identify an insect, I usually provide 2 photos: back and face. It seems that sometimes one feature stands out and allows identification with high certainty ("spots on the back - definitely a ladybug"), while other times you need to cross-reference both angles ("grey back could mean a few things, but after cross-referencing with the eyes - it's a moth").

How is it customary to implement this? Naively I was considering:

Two separate networks, one for backs and one for faces? If so, what formula is best for weighing in their outputs?
Single network, but separate dual classifications - e.g. "moth face", "moth back", "ladybug face", "ladybug back"?
A single network, feed everything naively (e.g. moths from different angles, all with the same classification "moth") and rely on the NN to sort it out itself?

There are several ways you can do this.

One is to input both images in input, so it can be a 2 input system or an input with 6 channels.

As you suggested in 1st point, you can make 2 networks, connect them at the end and add another layer for final classification or use outputs from both and train another classifier (like Gradient bosting). You can look up ensemble techniques and ensemble of neural networks for more.

For dual classification and naive approach, you will again have a problem in case there are some insects that can solely be identified from features at a specific angle, if so you can then discard other angles (e.g. ignore moth face if moth back is the distinguishing feature)


How do you choose the number of neurons, synapses, and hidden layers of an ANN (in NEAT)? I want to make a Connect 4 AI using machine learning, but I'm a complete beginner to the topic. From what I've seen, an ANN is a way to go. Some phrases I've heard are "neuroevolution" and the acronym NEAT. I'm very confused.

How do you choose the number of neurons, synapses, and hidden layers of an ANN (in NEAT)?

To find the number of neurons and layers that you will use is not that straightforward. The best way to do this is through experimentation however you will be able to better estimate the number of layers and neurons needed through experience. One of the common rules is that more neurons are better for more complex datasets. However, you do not want too many or you will get an overfitted model.

As for NEAT, that stands for neuron evolution of augmenting topologies. This is a genetic algorithm that works fairly well, however, I would recommend that you use a different algorithm like Q-learning. If you wish to learn more about Q-learning, then I would definitely recommend that you check out Google's DeepMind research on training deep neural networks to play the game of Go using Q-learning.


Can we use a messenger that does not alter the AI to solve the control problem? Instead of directly communicating with the AI, we would instead communicate with a messenger, who would relay our communications to the AI. The messenger would have no power to alter the AI's hardware or software in any way, or to communicate with anything or anyone, except relaying communications to and from the AI and humans asking questions. The messenger could be human, of a software bot. The primary job (and only reason) of the AI would be to act as a filter, not relaying any requests for release back, only the answer to the question asked. The ethics of this method are another debate.

The AI would have to be physically isolated from all outside contact, other than 8 light sensors, and 8 LEDs. The messenger would operate 8 other LEDs, and receive information from 8 light sensors as well. Each AI light sensor would be hooked up to a single messenger controlled LED, and vice versa. Through this system, the two parties could communicate via flashes of light, and since there are 8, the flashes would signal characters in Unicode.

I would say no due to the possibility of psychological manipulation of the messenger by the AI. Also, the LED communication constraints place severe limitations on the capabilities of the AI, as the usefulness of AI is likely predicated on its ability to learn quickly from a vast amount of information (e.g. using the internet).

In some sense you may successfully control an AI using techniques like this but the nuance of the control problem is controlling an AI without restricting its ability to solve our greatest problems.

We already knew that we could keep an AI safe inside a computer isolated from the rest of the word, but the problem fundamentally is that we if had a truly general AI, we would never want to keep it isolated. Is there some way to unleash it so that it is fully capable of solving our problems while simultaneously making sure that it is safe?


What are all the different kinds of neural networks used for? I found the following neural network cheat sheet (Cheat Sheets for AI, Neural Networks, Machine Learning, Deep Learning & Big Data).

What are all these different kinds of neural networks used for? For example, which neural networks can be used for regression or classification, which can be used for sequence generation, etc.? I just need a brief overview (1-2 lines) of their applications.

I agree that this is too broad, but here's a 1 sentence answer for most of them. The ones I left out (from the bottom of the chart) are very modern, and very specialized. I don't know much about them, so perhaps someone who does can improve this answer.

Perceptron: Linear or logistic-like regression (and thus, classification).
Feed Forward: Usually non-linear regression or classification with sigmoidal activation. Essentially a multi-layer perceptron.
Radial Basis Network: Feed Forward network with Radial Basis activation functions. Used for classification and some kinds of video/audio filtering
Deep Feed Forward: Feed Forward with more than 1 hidden layer. Used to learn more complex patterns in classification or regression, maybe reinforcement learning.

Recurrent Neural Network: A Deep Feed Forward Network where some nodes connect to past layers. Used in reinforcement learning, and
to learn patterns in sequential data like text or audio.
LSTM: A recurrent neural network with specialized control neurons (sometimes called gates) that allow signals to be remembered for longer periods of time, or selectively forgotten. Used in any RNN application, and often able to learn sequences that have a very long repetition time.
GRU: Much like LSTM, another kind of gated RNN with specialized control neurons.

Auto Encoder: Learns to compress data and then decompress it. After learning this model, it can be split into two useful subparts: a mapping from the input space to a low-dimensional feature space, that may be easier to interpret or understand; and a mapping from a small dimensional subspace of simple numbers into complex patterns, which can be used to generate those complex patterns. Basis of much modern work in vision, language, and audio processing.
VAE, DAE,SAE: Specializations of the Auto Encoder.

Markov Chain: A neural network representation of a markov chain: State is encoded in the set of neurons that are active, and
transition probabilities are thus defined by the weights. Used for
learning transition probabilities and unsupervised feature learning
for other applications.
HN, BM, RBM, DBM: Specialized architectures based on the Markov Chain idea, used to automatically learn useful features for other
applications.

Deep Convolutional Network: Like a feed-forward network, but each node is really  a bank of nodes learning a convolution from the layer
before it. This essentially allows it to learn filters, edge
detectors, and other patterns of interest in video and audio
processing.
Deep Deconvolutional Network: Opposite of a Convolutional Network in some sense. Learn a mapping from features that represent edges or
other high level properties of some unseen image, back to the pixel
space. Generate images from summaries.
DCIGN: Essentially an auto-encoder made of a DCN and a DN stuck together. Used to learn generative models for complex images like
faces.
Generative Adversarial Network: Used to learn generative models for complex images (or other data types) when not enough training data is
available for a DCIGN. One model learns to generate data from random
noise, and the other learns to classify the output of the first
network as distinct from whatever training data is available.


What could I do to this CNN to achieve a higher accuracy on the cifar10 dataset? I have achieved around 85% accuracy using the following architecture:

I used a learning rate of 0.001 and trained the model over 125 epochs with a batch size of 64.
Any suggestions would be much appreciated. Thanks in advance.

You results show signs of overfitting at around epoch 40. In order to overcome this you can either simplify the model somewhat or increase regularization. You do not share what values you are using for dropout regularization so you can try increasing that.

But to be honest, I am not sure if that is going to help. You are using dropout in a pure CNN architecture, which I do not see that often in recent models. When they exists, they are usually at the very end of the network, or after densely connected layers. There are claims that regular dropout does not work as intended for convolutional layers, so the idea of spatial dropout is developed.

But you are using them after pooling layers and such a design may not be as bad as using them after convolutional layers. In any case, if you check the top performers on this dataset, you can see there are some who are trying to come up with new regularization techniques for CNN's, such as shake-shake, shakedrop and cutout.

However, given you already have an overfitting model, removing regularization might not be the best idea. But if you replace the layers after (and including) the last convolution with some fully connected layers, you can use dropout regularization on them instead. This would remove the largest convolutional layer of the model and you can add dense layers without increasing model size.

For image recognition tasks of any kind, easiest way to achieve high accuracy is via transfer learning.


In what situations ELUs should be used instead of RELUs? I always use RELUs actication functions when I need to and I understand limitations of ELUs. So in what situation do I need to consider ELUs over RELUs?

ELU does not suffer from from dying neurons issue, unlike ReLU. While ELU can help you to acheive a better accuracy, it is a slower than ReLU because of its non linearity in its negative range.
Choosing a right activation function totally depends on situations but you need to also consider other similar types of activation function such as leaky ReLU.
Check this link out. It could be useful.


How are afterstate value functions mathematically defined? In this answer, afterstate value functions are mentioned, and that temporal-difference (TD) and Monte Carlo (MC) methods can also use these value functions. Mathematically, how are these value functions defined? Yes, they are a function of the next state, but what's the Bellman equation here? Is it simply defined as $v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$? If yes, how can we define it in terms of the state, $v(s)$, and state-action, $q(s, a)$, value functions, or as a Bellman (recursive) equation?
Sutton & Barto's book (2nd edition) informally describe afterstate value functions in section 6.8, but they don't provide a formal definition (i.e. Bellman equation in terms of reward or other value functions), so that's why I am asking this question.

Based on this and this resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton & Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there are other ways of formulating it), but the contents of the first resource seem to be consistent with the contents in the second resource.
Setup
Let's assume that we have an infinite-horizon MDP
$$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$
where

$\mathcal{S}$ is the set of states
$\mathcal{Y} \subseteq \mathcal{S}$ is the set of afterstates (aka post-decision states or "end of period" states [1], which can also be written as after-states)
$\mathcal{A}$ is the set of actions
$\mathcal{T}$ is the transition function
$\mathcal{R}$ is the reward function
$\gamma$ is a discount factor

Let

$y \in \mathcal{Y}$ be an afterstate
$f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$ be a deterministic function (from state-action pairs to afterstates), so we have $f(s, a) = y$

The transition function $\mathcal{T}$ for $\mathcal{M}$ is defined as
\begin{align}
\mathcal{T}(s, a, s^{\prime})
&\doteq P ( s^{\prime} \mid f(s, a)) \\
&= P ( s^{\prime} \mid y)
\end{align}
A transition is composed of 2 steps

a deterministic step, where we apply the deterministic function $f(s, a) = y$, which depends on an action $a$ taken in the state $s$, followed by
a stochastic step, where we apply the probability distribution $P (s^{\prime} \mid y)$, which does not depend on the action $a$ anymore, but only on $y$

So, I have denoted afterstates with a different letter, $y$, because afterstates are reached with a deterministic function $f$, while other states, $s$ or $s'$, are reached with $P$.
After having taken the action $a$ in the state $s$, we get a reward (i.e. we get a reward in step 1), but we do not get a reward after the stochastic step (given that no action is taken).
So, we can define the reward function $\mathcal{R}$ for this MDP as follows
$$
\mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a)
$$
The situation is illustrated by the following diagram

So, here, $P$ is the stochastic transition function (i.e. a probability distribution) as used above. Note that, here, $r_t$ is a specific realization of $R_t$ (the random variable) in the formulas below.
State value function
Let's recall the definition of the state value function $v_\pi(s)$ for a given policy $\pi$ (as defined in Sutton & Barto, section 3.5)
\begin{align}
v_{\pi}(s)
&\doteq
\mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right] \\
&=
\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right],
\end{align}
for all $s \in \mathcal{S}$ and
\begin{align}
G_{t}
&\doteq
\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \\
&=
R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3}+ \cdots \\
&=
\mathcal{R}(s_t, a_t) + \gamma \mathcal{R}(s_{t+1}, a_{t+1})+\gamma^{2} \mathcal{R}(s_{t+2}, a_{t+2}) +\cdots,
\end{align}
where $\pi(s_t) = a_t$ and $\mathcal{R}(s_t, a_t) = R_{t+1}$, for $t=0, 1, 2, \dots$. (So, note that $\mathcal{R} \neq R_t$: the first is the reward function, while the second is a random variable that represents the reward received after having taken action $a_t$ in step $s_t$)
The optimal state value function is defined as
$$
v_{*}(s) \doteq \max _{\pi} v_{\pi}(s)
$$
Afterstate value function
Similarly, we will define the afterstate value function, but we will use the letter $w$ just to differentiate it from $v$ and $q$.
\begin{align}
w_{\pi}\left(y\right)
&\doteq
\mathbb{E}_{\pi}\left[G_{t+1} \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2} \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[
R_{t+2} + \gamma R_{t+3}+\gamma^{2} R_{t+4} + \cdots
 \mid Y_{t}=y\right]
\\
&=
\mathbb{E}_{\pi}\left[
\mathcal{R}(s_{t+1}, a_{t+1})+\gamma \mathcal{R}(s_{t+2}, a_{t+2}) + \gamma^{2} \mathcal{R}(s_{t+3}, a_{t+3}) + \cdots
 \mid Y_{t}=y\right] ,
\end{align}
where $\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$, for all $t$.
In other words, the value of an afterstate $y$ (at time step $t$, i.e. given $Y_t = y$) is defined as the expectation of the return starting from the state that you ended up in after the afterstate $y$.
This seems reasonable to me and is similar to my proposal for the definition of the afterstate value function in the question, although I was not considering any deterministic functions in a potential formulation, and I was also not thinking of afterstates as intermediate states, reached by a deterministic step, between the usual states.
Similarly to the optimal state value function, we also define the optimal afterstate value function
$$
w_{*}(y) \doteq \max _{\pi} w_{\pi}(y)
$$
Afterstate value function defined in terms of the state value function
We can define the afterstate value function in terms
$$
w_{*}(y)
=
\sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} )
$$
In other words, $w_{*}(y)$ is defined as an expectation over the value of next possible states $s'$ from the afterstate $y$.
This seems to be correct and consistent with the above definitions.
More equations
In this and this resources, the state value function is also defined in terms of afterstate value function as follows
$$v_{*}(s)=\max_{a}\left(\mathcal{R}(s, a)+\gamma w_{*}(f(s, a))\right)$$
The Bellman equation for afterstate value function (from which an update rule can be derived) is given by
$$
w_{*}(y)
=
\sum_{s^{\prime}}
P(s^{\prime} \mid y )
\max_{a} (
\mathcal{R} (s^{\prime}, a)
+
\gamma
w_{*}(f ( s^{\prime}, a ))),
$$
which is really similar to the Bellman equation for the state value function.
Finally, we can also express the state-action value function in terms of the afterstate value function
$$
q_\pi(s_t, a_t)
=
\mathcal{R}\left(s_{t}, a_{t}\right)+\gamma w_{\pi}\left(f\left(s_{t}, a_{t}\right)\right)
$$
Given that this answer is already quite long, see the resource for more details (including an algorithm based on the afterstate Bellman equation).
Implementation
If you are the type of person that understands the concepts by looking at the code, then this Github project, which implements a Monte Carlo method that uses afterstates to play tic-tac-toe, may be useful. Afterstates are useful in tic-tac-toe because it is a 2-player game, where two agents take actions in turn, so we can estimate the action that you should take deterministically (as if it was the $f$ above) before the other agent takes an action (probabilistically), at least, this is my current interpretation of the usefulness of afterstates in this game (and similar games/problems).


What purpose would be served by developing AI's that experience human-like emotions? In a recent Wall Street Journal article, Yann LeCunn makes the following statement:

  The next step in achieving human-level ai is creating intelligent—but not autonomous—machines. The AI system in your car will get you safely home, but won’t choose another destination once you’ve gone inside. From there, we’ll add basic drives, along with emotions and moral values. If we create machines that learn as well as our brains do, it’s easy to imagine them inheriting human-like qualities—and flaws.

Personally, I have generally taken the position that talking about emotions for artificial intelligences is silly, because there would be no reason to create AI's that experience emotions.  Obviously Yann disagrees.  So the question is:  what end would be served by doing this?  Does an AI need emotions to serve as a useful tool?

The answer to this question, unlike many on this board, I think is definitive. No. We don't need AI's to have emotion to be useful, as we can see by the numerous amount of AI's we already have that are useful.

But to further address the question, we can't really give AI's emotions. I think the closest we can get would be 'Can we make this AI act in a way a human would if that human was insert emotion?'. I guess in a sense, that is having emotion, but that's a whole other discussion.

And to what end? The only immediate reason coming to mind would be to create more lifelike companions or interactions, for the purposes of video games or other entertainment. A fair goal, but far from necessary. Even considering an AI-imbued greeting robot in the lobby of some building, we'd probably only ever want it to act cordial.

Yann says that super-advanced AI would lead to more human-like qualities and flaws. I think it's more like it would 'give our AI's more human-like qualities or in other words flaws'. People have a tendency to act irrationally when sad or angry, and for the most part we only want rational AI. To err is human, as they say.

The purpose of AI's and learning algorithms is to create systems that act or 'think' like humans, but better. Systems that can adapt or evolve, while messing up as little as possible. Emotive AI has uses, but it's certainly not a prerequisite for a useful system.


How to estimate the accuracy upper limit of any CNN model over a computer vision classification task We are given a computer vision classification task, that is, a task that asks us to predict the category of an image over $n$ predefined classes (the so-called closed set classification problem).

Question: Is it possible to give an estimate on what is the best accuracy one is likely achieve using an end-to-end CNN model (possibly, using a popular backbone) in this task? Do the performances of state-of-the-arts models on open datasets serve as a good reference? If someone claims that they achieve certain performance with some popular CNN architecture, how do we know s/he is not bragging?

You may or may not have access to the training dataset yet. The testing dataset shall be something close to the real-world production scenario. I know this is too vague, but just assume you have a fair judge.

Background: Product teams sometimes asks engineering teams for quick (and dirty) solutions. Engineering teams want to assess the feasibility before say "Yes we can do $95\%$" and officially launch (and be responsible) the projects.

There is no easy rule for this. You can use transfer learning to select a model that works well on image classification. However the accuracy you achieve will be highly dependent on your training set.  If your training set is "similar" in quantity and quality to what was used  for the accuracy achieved by the transfer learning model in some application you have a reasonable chance of coming close to that accuracy. By similar is mean roughly the same number of images per class. By quality I mean what percentage of the pixels in the images that are occupied by the "region of interest -ROI), same level of noise in the images etc. Also it depends on the nature of the classes. If the classes are widely different (elephants vs trees) the accuracy should be higher than if you are try to classify closely related images (human faces).


What heuristic to use when doing A* search with multiple targets? Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which heuristic do we have to use when we have multiple targets?

If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search.

To do this, you can't just change your heuristic, instead you need to reframe your problem:

Instead of states in your search being locations, they should be tours. Each state is a list of all the places you need to visit, in a specific order.
Instead of actions being movements from one location to another, they need to be transformations from one tour to another. For example, if you swap the order that you visit two adjacent locations, then you'll get a different tour. This gives you a way to "move" between tours.
A solution means visiting all the locations as fast as possible. If you know how to get between two locations, just store the distances, and then sum all the distances together to get the cost of a tour. If you don't know, you can just run A* from each place to each other place once, and then cache the distances afterwards.
A heuristic will depend on your domain. A reasonable start might be to assume that you can visit each location from the nearest other location you've already visited. Generally, heurstics based on the idea of minimum spanning trees are effective for this domain.

The real answer though, is to try a technique that is meant for this kind of problem, like a local search algorithm. Notice that if we know the cost of moving between any two points, we can just adopt a greedy approach: make the move that improves things the most each time. This is often faster than waiting for A* in practice if you just want a good solution, but it doesn't need to be the very best one.


How to represent and work with the feature matrix for graph convolutional network (GCN) if the number of features for each node is different? I have a question regarding features representation for graph convolutional neural network.

For my case, all nodes have a different number of features, and for now, I don't really understand how should I work with these constraints. I can not just reduce the number of features or add meaningless features in order to make the number of features on each node the same - because it will add to much extra noise to the network.

Are there any ways to solve this problem? How should I construct the feature matrix?

I'll appreciate any help and if you have any links to papers that solve this problem.

The simplest way I could come with is to pad with 0 each feature which is not present. You said that you're going to add too much noise to the network, but I don't see the problem (please correct me if I'm wrong). For example we have two nodes, the first one has only 2 features with the 3rd one missing and the second node has all features X=[[1,2,0], [3,4,5]]. Now we can project the nodes to a hidden representation (pretty common). I'm going to use a weight matrix of W=[[1], [1], [1]]. The output of XW will be [[3], [12]]. Now let's add a new feature to the second node X=[[1,2,0, 0], [3,4,5,6]] and apply the same transformation W=[[1], [1], [1], [1]] the output will be [[3], [18]] you can see that the first node is not affected by the number of missing features.

Another way you could achieve this if you don't want to use the projection could be using a mask. For example give the same example above we could create a mask M=[[1,1,0], [1,1,1]] where each entry represents if a specific feature is present in a specific node. Now usually a GCN layer is defined as H=f(AHW) where A is the adjacency matrix. We could change the propagation rule to H=f(AH*MW) where * is the pointwise multiplication. Like this if a node is missing a feature it can not "access" information from others that are having that feature.


How do I choose the size of the hidden state of a GRU? I'm trying to understand how the size of the hidden state affects the GRU.

For example, suppose I want to make a GRU count. I'm gonna feed it with three numbers, and I expect it to predict the fourth.

How should I choose the size of the hidden state of a GRU?

Yes, your understanding of the hidden state is correct. But the size of the hidden state is a hyperparameter that needs to found by trial-and-error. There is no closed-form formula or solution which links the size of the hidden state and the problem at hand. But, there are some rules of thumb like to start out with the size of the hidden state to be a power of 2, etc. Keep tuning the hyperparameter until you get very good predictions.


How can I cluster based on the complementary categories? K-means tries to find centroid and then clusters around the centroids. But what if we want to cluster based on the complement?

For example, suppose we have a group of animals and we want to cluster Dogs, Cats, (Not Dogs and Not Cats). The 3rd category will not arise from mean clustering.

Note: K-means does not assume an interpretation/label of the clusterings - in fact it is an unsupervised algorithm. The interpretations are a result of human analysis after running K-means.

For example, in the case of cats and dogs one would most definitely chose k = 2 - which provides an easy interpretation. However, what would it mean if we set k = 1000. We no longer have a "clean" interpretation of the centroids.

Note: how I keep saying "interpretation." The algorithm simply assigns a data point to a cluster and calls it a day. Humans then look at the results and try to understand them with an interpretation.

Continuing with the example where k = 2. One could easily interpret "is cat" as "not dog" and "is dog" as "not cat." The idea here is that the data is unlabeled beforehand and humans try to fathom the results retrospectively by assigning the resulting clusters with an understandable label.

I hope this clarifies the issue.


How do we derive the expression for average reward setting in continuing tasks? In the average reward setting we have:
$$r(\pi)\doteq \lim_{h\rightarrow\infty}\frac{1}{h}\sum_{t=1}^{h}\mathbb{E}[R_{t}|S_0,A_{0:t-1}\sim\pi]$$
$$r(\pi)\doteq \lim_{t\rightarrow\infty}\mathbb{E}[R_{t}|S_0,A_{0:t-1}\sim\pi]$$
How is the second equation derived from the first?

We assume that our MDP is ergodic. Loosely speaking, this means that wherever the MDP starts (i.e. no matter which state we start in) or any actions the agent takes early on can only have a limited effect on the MDP and in the limit (as $t \rightarrow \infty$) the expectation of being in a given state depends only on the policy $\pi$ and the transition dynamics of the MDP.
This means that, eventually, $\mathbb{E}[R_t] = \mathbb{E}[R_{t+1}]$ for some large $t$. Therefore, as we take the average of our expected values of the rewards received for an infinitely long period of time, this will have converged due to what I just mentioned of $\mathbb{E}[R_t] = \mathbb{E}[R_{t+1}]$. To see why the two are equal, recall that the reward received is dependent on the current state and the action taken -- to better emphasise this I will briefly denote the reward at time step $t+1$ as $R(S_t, A_t)$. If we are in the steady state distribution, that is, the state distribution is now fixed, and our actions are still taken according to our policy, then the expected value of $R(S_t, A_t)$ will be the same for all future $t$ since neither the policy nor the state distribution are changing (recall that the average rewards are a way of evaluating a policy in the average-reward setting so for sure this does not change).
A way to think of this is that since we know that, eventually, $\mathbb{E}[R_t]$ will equal $\mathbb{E}[R_{t+1}]$, and so if we keep have an infinite number of these, the average of them will of course converge to the same value. Imagine if I gave you the sequence 1, 2, 3, 4, 4, 4, 4, ........, 4 and asked you to take the average - if we had an infinite amount of 4's then the average would of course be 4.


Using the opponent's mixed strategy in estimating the state value in minimax Q learning In the paper Markov games as a framework for multi-agent reinforcement learning  (which introduces the minimax Q Learning algorithm), at the bottom left of page 3, my understanding is that the author suggests, for a simultaneous 1v1 zero-sum game, to do Bellman iterations with $$V(s)=\min_{o}\sum_{a}\pi_{a}Q(s,a,o)$$ with $\pi_{a}$ the probability of playing action $a$ for the maximizing player in his best mixed strategy to play in state $s$.

If my understanding is correct, why does the opponent in this equation play a pure strategy ($\min_{o}$) rather than his best mixed strategy in state $s$. This would instead give $$V(s)=\sum_{o}\sum_{a}\pi_{a}\pi_{o}Q(s,a,o)$$ with $\pi_{o}$ the opponent's best mixed strategy in state $s$. Which of these two formulations is correct and why? Are they somehow equivalent?

The context of this question is that I am trying to use minimax Q learning with a Neural Network outputting the matrix $Q(s,a,o)$ for a simultaneous zero-sum game. I have tried both methods and so far have seen seemingly equally bad results, quite possibly due to bugs or other errors in my method.

My understanding is now that the author's formula is deliberate. It seeks to learn a worst-case maximizing policy. The formula I instead suggest would, I believe, instead be Nash Q learning where the agent seeks to learn to play a Nash equilibrium.

After debugging, I have gotten good results with the second formula but cannot speak for the original Minimax Q learning one.


Autoencoder: predictions missing for nodes in the bottleneck layer I'm using tf.Keras to build a deep-fully connected autoencoder. My input dataset is a dataframe with shape (19947,), and the purpose of the autoencoder is to predict normalized gene expression values. They are continuous values that range from [0,~620000].
I tried different architectures and I'm using relu activation for all layers. To optimize I'm using adam with mae loss.
The problem I have is the network trains successfully (although the train loss is still terrible) but when I'm predicting I notice that although the predictions do make sense for some nodes, there are always a certain number of nodes that only output 0. I've tried changing the number of nodes of my bottleneck layer (output) and it always happens even when I decrease the output number.
Any ideas on what I'm doing wrong?
tf.Keras code:
input_layer = keras.Input(shape=(19947,))
simple_encoder = keras.models.Sequential([
    input_layer,
    keras.layers.Dense(512, activation='relu'),
    keras.layers.Dense(128, activation='relu'),
    keras.layers.Dense(16, activation='relu')
])
simple_decoder = keras.models.Sequential([
    keras.layers.Dense(128, activation='relu'),
    keras.layers.Dense(512, activation='relu'),
    keras.layers.Dense(19947, activation='relu')
])
simple_ae = keras.models.Sequential([simple_encoder, simple_decoder])
simple_ae.compile(optimizer='adam', loss='mae')
simple_ae.fit(X_train, X_train,
              epochs=1000,
              validation_data=(X_valid, X_valid),
              callbacks=[early_stopping])

Output of encoder.predict with 16 nodes on the bottleneck layer. 7 nodes predict only 0's and 8 nodes predict "correctly"

My closest guess is because you are using the activation function ReLU, which pushes data to be greater than zero. However, because of your data's nature, the autoencoder is highly dependent on negative calculations to reconstruct your data, but the best it can achieve is zero.

In the context of artificial neural networks, the rectifier is an activation function defined as the positive part of its argument:
$$f(x) = x^+ = max(0, x)$$
https://en.wikipedia.org/wiki/Rectifier_(neural_networks)


Training by one batch of examples, what does it mean Say I have a batch of examples, each examples represent a state:

[0.1, 0.2, 0.5] #1st example
[0.4, 0.0, 0.3] #2nd example
..........
[0.1, 0.1, 0.1] #16th example

I feed through the NN, and then the NN predict the following class:

[move up]   #1st example
[move down] #2nd example
........
[move left] #16th example

And then I take the square loss (which calculated to be 0.1 after taking average over 16 examples), and do backward propagation.

So, can I assume that each of these examples will assign (or contribute) to a 0.1 loss?

This would mean that there is only one gradient update on your dataset of 16 samples. If you are taking the mean of all the squared errors ( mse ), then the loss of each sample is contributing to the 0.1 loss.


How can neural networks be used to generate rather than classify? In my experience with Neural Nets, I have only used them to take input vectors and return binary output.

But, here in a video, https://youtu.be/ajGgd9Ld-Wc?t=214, Kai Fu Lee, renowned AI Expert shows a deep net which takes thousands of samples of Trump's speeches and generates output in the Chinese Language.

In short, how can deep nets/neural nets be used to generate output rather than giving answer yes or no? Additionally, how are these nets being trained? Can anyone here provide me a simple design to nets that are capable of doing that?

Think of a neural network as a universal function approximator (With infinite width under a set of constraints this is actually provable). Now when discussing generation in the context you have provided, you essentially want to draw from some distribution $p(y|c)$ where $y$ is your output and $c$ is your context or input.

Theorem: For any distribution $\Omega$, if we take $z \sim \mathcal{N}(0,I)$, there exists a function $f$ where $f(z) \sim \Omega$.

Given the above theorem (for the purposes of this post I don't need to prove it, but its very similar to the universal approximation theorem proof) and if we take neural networks as a pseudo-universal function approximator, if we have a valid objective or training procedure that can learn the parameters of $f$, sampling is as easy as sampling $\mathcal{N}(0,I)$ and then applying $f$.

So the trick really is finding a good training procedure, and this is where you see GANs, VAEs and other models/schemes come into play.

Everything I've said above works really well when there isn't autocorrelation like in text, but when there is, the above methodology would result in a combinatorially large output space which isn't realistic with a vocabulary size usually spanning somewhere between a couple thousand and a couple hundred thousand. So to handle this they model the joint by taking advantage of that autocorrelation by modeling the joint probability as its bayesian decomposition.
$$p(\vec w) = p(w_0)\prod_{i=1}^{N-1}p(w_i|w_{<i})$$
Now that there is a framework to efficiently model this type of output, were back into the position as before where we are looking for clever training schemes. In this case you'll see commonly RNN's or other sequential model training with teacher forcing (@nbro described this in his answer too), or using GAN like compositions using either reinforcement learning to handle the lack of differentiability in sampling or using approximations like Gumbel-Softmax or Intermediate Loss Sampling (method I actually developed)

I hope this answered your question.


Can we prove that a piece of code in AI software will cause it to never turn against us? It is possible of normal code to prove that it is correct using mathematical techniques, and that is often done to ensure that some parts are bug-free.

Can we also prove that a piece of code in AI software will cause it to never turn against us, i.e. that the AI is friendly? Has there any research been done towards this?

Unfortunately, this is extremely unlikely.

It is nearly impossible to make statements about the behaviour of software in general. This is due to the Halting problem, which shows that it is impossible to prove whether a program will stop for any given input. From this result, many other things have been shown to be unprovable.

The question whether a piece of code is friendly, can very likely be reduced to a variant of the halting problem.
An AI that operates in the real world, which is a requirement for "friendliness" to have a meaning, would need to be Turing complete. Input from the real world cannot be reliably interpreted using regular or context-free languages.

Proofs of correctness work for small code snippets, with clearly defined inputs and outputs. They show that an algorithm produces the mathematically right output, given the right input.
But these are about situations that can be defined with mathematical rigour.

"Friendliness" isn't a rigidly defined concept, which already makes it difficult to prove anything about it. On top of that, "friendliness" is about how the AI relates to the real world, which is an environment whose input to the AI is highly unpredictable.

The best we can hope for, is that an AI can be programmed to have safeguards, and that the code will raise warning flags if unethical behaviour becomes likely - that AI's are programmed defensively.


Why can't we fully exploit the environment after the first episode in Q-learning? During the first episode, it's 100% exploration, because all our Q values are 0. Suppose we have 1000 time steps, and it's terminated by meeting a reward. So, after the first episode, why can't we make it 100% exploitation? Why do we still need exploration?

BlueTurtle's answer is good, but I'd like to add something.
Your question realistically has nothing to do with Q Learning, in fact, you can ask the same thing about just about any RL algorithm. In fact, even in multi-armed bandits, you can easily see why your proposed method is suboptimal (please don't interpret this as a criticism, because I think your question is a very natural one). My suggestion to you is to read up on multi-armed bandits since they're much simpler to analyze. I think even the Sutton and Barto book deals with your proposed method explicitly, and mathematically proves that other strategies are better.


Does k consistency always imply (k - 1) consistency? From Russell-Norvig:

  A CSP is strongly k-consistent if it is k-consistent and is also (k − 1)-consistent, (k − 2)-consistent, . . . all the way down to 1-consistent.

How can a CSP be k-consistent without being (k - 1)-consistent? I can't think of any counter example for this case. Any help would be appreciated.

Define P as a CSP where X, Y are the variables, domain of both is {1,2,3,4} and conditions in normal form are:

node-condition X<4
arc-condition X=Y

P is 2-consistent (arc consistent) because for any X value it is possible to find a Y value that fulfills the arc-condition X=Y.

However, P is not 1-consistent (node-consistent) because exist a X value (X=4) that can not fulfill the node condition x<4.

For these reasons, this problem is 2-consistent but not strongly 2-consistent.

Obviously, it is straightforward to convert this example in a strongly 2-consistent problem, just reducing the domain to {1,2,3}.


Mini-batch training and the gradient I am reading a book that states, "As the mini-batch size increases, the gradient computed is closer to the 'true' gradient". So basically what they are saying is mini-batch training only focuses on decreasing the cost function in a certain 'plane', sacrificing accuracy for speed I assume?

If so, how is batching the training examples reducing the dimensions of the weight-space for any batch, or for that matter, each iteration... all of the weights are still involved with each batch/iteration, am I correct?

The basic idea behind mini-batch training is rooted in the exploration / exploitation tradeoff in local search and optimization algorithms.

You can view training of an ANN as a local search through the space of possible parameters. The most common search method is to move all the parameters in the direction that reduces error the most (gradient decent).

However, ANN parameter spaces do not usually have a smooth topology. There are many shallow local optima. Following the global gradient will usually cause the search to become trapped in one of these optima, preventing convergence to a good solution.

Stochastic gradient decent solves this problem in much the same way as older algorithms like simulated annealing: you can escape from a shallow local optima because you will eventually (with high probability) pick a sequence of updates based on a single point that "bubbles" you out. The problem is that you'll also tend to waste a lot of time moving in wrong directions.

Mini-batch training sits between these two extremes. Basically you average the gradient across enough examples that you still have some global error signal, but not so many that you'll get trapped in a shallow local optima for long.

Recent research by Masters and Luschi suggests that in fact, most of the time you'd want to use smaller batch sizes than what's being done now. If you set the learning rate carefully enough, you can use a big batch size to complete training faster, but the difficulty of picking the correct learning rate increases with the size of the batch.


Why is exp used in encoder of VAE instead of using the value of standard deviation alone? There's one VAE example here:
https://towardsdatascience.com/teaching-a-variational-autoencoder-vae-to-draw-mnist-characters-978675c95776.

And the source code of encoder can be found at the following URL: https://gist.github.com/FelixMohr/29e1d5b1f3fd1b6374dfd3b68c2cdbac#file-vae-py.

The author is using $e$ (natural exponential) for calculating values of the embedding vector:

$$z = \mu + \epsilon \times e^{\sigma}$$

where $\mu$ is the mean, $\epsilon$ a small random number and $\sigma$ the standard deviation.

Or in code

z  = mn + tf.multiply(epsilon, tf.exp(sd))

It's not related to the code (practical programming), but why using natural exponential instead of:

$$z = \mu + \epsilon \times \sigma$$

In the source code, the author defines sd by

sd       = 0.5 * tf.layers.dense(x, units=n_latent)

which means that $\operatorname{sd}\in \mathbb{R}^n$.
In particular, the support over sd includes negative numbers, which is something we want to avoid.
Since standard deviations are always nonnegative, we can exponentiate to get us in the correct domain.
This is a case where the variable is inappropriately named.
Here, sd is not the standard deviation itself but rather the logarithm of the standard deviation. This allows it to be predicted as the output of a layer in a neural network, so extracting the predicted value of the standard deviation would require exponentiation.


What is the difference between the uniform-cost search and Dijkstra's algorithm? Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an introductory course on artificial intelligence (as I did a few years ago, during my bachelor's), you should have also encountered some search algorithms, in particular, the uniform-cost search (UCS).
A few articles on the web (such as the Wikipedia article on DA) say that DA (or a variant of it) is equivalent to the UCS. The famous Norvig and Russell's book Artificial Intelligence: A Modern Approach (3rd edition) even states

The two-point shortest-path algorithm of Dijkstra (1959) is the origin of uniform-cost search. These works also introduced the idea of explored and frontier sets (closed and open lists).

How exactly is DA equivalent to UCS?

The answer to my question can be found in the paper Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm (2011), in particular section Similarities of DA and UCS, so you should read this paper for all the details.
DA and UCS are logically equivalent (i.e. they process the same vertices in the same order), but they do it differently. In particular, the main practical difference between the single-source DA and UCS is that, in DA, all nodes are initially inserted in a priority queue, while in UCS nodes are inserted lazily.
Here is the pseudocode (taken from the cited paper) of DA

Here is the pseudocode of the best-first search (BFS), of which UCS is just a particular case. Actually, this is the pseudocode of UCS where $g(n)$ is the cost of the path from the source node to $n$ (although the title indicates that this is the pseudocode of BFS).


Benchmarks for reinforcement learning in discrete MDPs To compare the performance of various algorithms for perfect information games, reasonable benchmarks include reversi and m,n,k-games (generalized tic-tac-toe). For imperfect information games, something like simplified poker is a reasonable benchmark.

What are some reasonable benchmarks to compare the performance of various algorithms for reinforcement learning in discrete MDPs? Instead of using a random environment from the space of all possible discrete MDPs on $n$ states and $k$ actions, are there subsets of such a space with more structure that are more reflective of "real-world" environments? An example of this might be so-called gridworld (i.e. maze-like) environments.

This is a related question, though I'm looking for specific examples of MDPs (with specified transitions and rewards) rather than general areas where MDPs can be applied.

Edit: Some example MDPs are found in section 5.1 (Standard Domains) of Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search (2012) by Guez et al.:

  The Double-loop domain is a 9-state deterministic MDP with 2actions,
  1000 steps are executed in this domain. Grid5 is a 5×5 grid with no
  reward anywhere except for a reward state opposite to the reset state.
  Actions with cardinal directions are executed with small probability
  of failure for 1000 steps. Grid10 is a 10×10 grid designed like Grid5.
  We collect 2000 steps in this domain. Dearden’s Maze is a 264-states
  maze with 3 flags to collect. A special reward state gives the number
  of flags collected since the last visit as reward, 20000 steps are
  executed in this domain.

Although I am not aware of any "benchmark problems" for (discrete) MDPs, I'll comment a bit on possible benchmarks and I will show some benchmarks used to test POMDP algorithms.

MDP vs POMDP

In Markovian Decision Processes (MDPs) the whole state space is known, this means you know all the information for your problem; therefore, you can use them to find solutions for perfect information problems or games.
Many of these games could use an MDP, some examples: 2048 and chess. Note that you must take into mind that the computational complexity grows with the number of states.
Although I could not find any benchmarks for MDPs, games with perfect information can be used to compare MDP solvers.

When a problem or game has imperfect information, you should use a  Partially Observable Markovian Decision Processes (POMDPs); in which you do not need to know the current state, but you keep track of the probabilities of being in any of the (discrete) states.

POMDP Benchmarks

Since I worked with POMDPs, I will comment some of the benchmarks researches used for discrete POMDPs (Pineau et al. (2003), Spaan and Vlassis (2004), Kurniawati et al. (2008), Ong et al. (2010), ArayaLopez et al. (2010)):

Tag: a robot and target move in a grid environment and can move one step at a time, moving has a cost, and a reward is gained if the robot is at the same position as the target (i.e. tagged it).
Two-Robot Tag: two robots attempt to catch a target, thereby sharing their observations and actions; the target tries to get away from them.
Mazes (Littman et al. (1995), Kaelbling et al. (1998), Spaan and Vlassis (2004)):

Hallway and Hallway2 are robot navigation tasks in a hallway, where the robot has only local noisy sensor information. The difficulty of hallways is it being long areas which look alike, which causes ambiguity in the localization.
Tiger-grid a two world state with a tiger being either behind the left or right door. The actions are listen, open the right or left door and there is a positive reward when opening the door without the tiger, otherwise a large negative reward.

Rock Sample: a rover explores a grid area, it knows its own position and the position of the rocks, however, it does not know which rocks are valuable. The rover can sense how valuable they are, but this sensor is less reliable when it is used farther away.

The tag game: the robot (blue) and target on a map with 29 positions and 870 states (29 for the robot, 29 + 1 (tagged) for the target).

These problems tend to be of the same size (number of states and actions) such that the results of different algorithms can be compared easily.

References:

Araya-Lopez, M., Thomas, V., Buffet, O., and Charpillet, F. (2010). A closer look at MOMDPs. In 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, volume 2, pages 197–204.
Kaelbling, L.P., Littman, M.L., Cassandra, A.R. (1998).
Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1-2): 99-134
Kurniawati, H., Hsu, D., and Lee, W. (2008). SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In Proceedings of Robotics: Science and Systems IV, Zurich, Switzerland.
Littman, M.L., Cassandra, A.R. and Kaelbling, L.P. (1995). Learning policies for partially observable environments: Scaling up. in Proc. 12th Int. Conf. on Machine Learning, San Francisco, CA.
Ong, S. C. W., Png, S. W., Hsu, D., and Lee, W. S. (2010). Planning under Uncertainty for Robotic Tasks with Mixed Observability. The International Journal of Robotics Research, 29(8):1053–1068.
Pineau, J., Gordon, G., and Thrun, S. (2003). Point-based value iteration: An anytime algorithm for POMDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI),
pages 477–484.
Spaan, M. T. J. and Vlassis, N. (2004). A point-based POMDP algorithm for robot planning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 2399–2404, New Orleans, Louisiana.


Are simple animal snares and traps a form of automation? Of computation? I'm trying to understand the relationship of humans and automation, historically and culturally.

I ask because the waterclock is generally considered the earliest form of automation, but snares and deadfall traps constitute simple switch mechanisms.

(They are single use without human-powered reset, but seem to qualify as machines. The bent sapling that powers the snare is referred to as the engine, which is "a machine with moving parts that converts power into motion.")

If snares and traps are a form of automation, automation has been with us longer, potentially, than civilization.

Are simple animal traps a form of automation or computation?

How to make a simple snare (the Ready Store)

Paiute Deadfall Trap (Homestead Telegraph)

Absolutely these traps and snares are a form of automation.

They take a task--harvesting small animals--which was traditionally done by hunting them, and make the process automatic.  The mechanism requires a human to set up, but its function is automatic.  This is to say that the mechanism operates without human involvement.

Absolutely this is a form of computation.

As DuttaA observed, these machines utilize a simple "IF/THEN" statement.  In the case of the snare:

  IF the hook is displaced from the base, THEN the sapling straightens

These simple machines will also return True or False:

  TRUE: The trap catches an animal
  FALSE: The trap is sprung but empty

The small animals are the input and, potentially, the output, depending on whether the mechanism returns "true".

(The use of "true" has historically included phrases such as "their aim was true" in the sense of shooting an arrow or throwing a spear.)


What is the correct way to use the implication in first-order logic? I know the implication symbol, $\rightarrow$, is used for conditions like

If $A$ is true, then $B$ will be true.

which can be written as
$$
A \rightarrow B
$$
However, sometimes the implication symbol is also used in other contexts. For example, if we want to say that

All $A$'s are $B$.

We could write
$$\forall X (A(X) \rightarrow B(X))$$
I don't understand why the implication is used here? And if the implication is necessary to use here, then why isn't the implication used in the example written below?

Some $A$'s are $B$'s.

$$\exists X (A(X) \land B(X))$$

When we state in English that "All As are Bs", this means that we gain information as soon as we observe an A, we can immediately deduce that it must also be a B. These are the kinds of situations where we use an implication. So, this would be written in formal logic as:

$$\forall X \left( A(X) \rightarrow B(X) \right)$$

When we state in English that "Some As are Bs", we do not gain any new information just from observing that something is an A, we cannot deduce anything about that A. It might happen to be one of the As that simultaneously is a B, but it also might happen not to be one of those examples. So, it would be wrong to use an implication here. The only information that the English sentence gives us is that there is at least one thing somewhere that happens to be an A as well as a B, which is written formally as:

$$\exists X (A(X) \land B(X))$$

Suppose that we would have written the following in logic:

$$\exists X (A(X) \rightarrow B(X))$$

This would be translated to English as follows:

  There exists some $X$ such that, if it is an $A$, it is also a $B$.

That bolded part is very important there. Note that this logical statement is also true as soon as I find one example $X$ that is not an $A$. For example, the following statement is true in the real world:

  There exists some human $X$ such that, if $X$ can fly, $X$ can also shoot fireballs from his or her hands.

(this is true in the real world, because I can come up with many examples of humans who cannot fly)


Would an artificial general intelligence have to be Turing complete? Artificial general intelligence is the intelligence of a machine that could successfully perform any intellectual task that a human being can.

Would an artificial general intelligence have to be Turing complete?

My answer is yes, but in a trivial way. The least you would expect from an intelligent agent is that it is able to execute a given Turing machine on a given input. This requires actually no intelligence, just following rules. If however, you are referring to the capability of predicting if the Turing machine will terminate on the given input, that is another matter. I don't think it is reasonable to expect such "undecidable" computational power for an agent to be generally intelligent.


Why is the reward signal normalized in openAI's REINFORCE? Pytorch's example for the REINFORCE algorithm for reinforcement learning has the following code:

import argparse
import gym
import numpy as np
from itertools import count

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
from torch.distributions import Categorical

parser = argparse.ArgumentParser(description='PyTorch REINFORCE example')
parser.add_argument('--gamma', type=float, default=0.99, metavar='G',
                    help='discount factor (default: 0.99)')
parser.add_argument('--seed', type=int, default=543, metavar='N',
                    help='random seed (default: 543)')
parser.add_argument('--render', action='store_true',
                    help='render the environment')
parser.add_argument('--log-interval', type=int, default=10, metavar='N',
                    help='interval between training status logs (default: 10)')
args = parser.parse_args()

env = gym.make('CartPole-v0')
env.seed(args.seed)
torch.manual_seed(args.seed)

class Policy(nn.Module):
    def __init__(self):
        super(Policy, self).__init__()
        self.affine1 = nn.Linear(4, 128)
        self.affine2 = nn.Linear(128, 2)

        self.saved_log_probs = []
        self.rewards = []

    def forward(self, x):
        x = F.relu(self.affine1(x))
        action_scores = self.affine2(x)
        return F.softmax(action_scores, dim=1)

policy = Policy()
optimizer = optim.Adam(policy.parameters(), lr=1e-2)
eps = np.finfo(np.float32).eps.item()

def select_action(state):
    state = torch.from_numpy(state).float().unsqueeze(0)
    probs = policy(state)
    m = Categorical(probs)
    action = m.sample()
    policy.saved_log_probs.append(m.log_prob(action))
    return action.item()

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

def main():
    running_reward = 10
    for i_episode in count(1):
        state = env.reset()
        for t in range(10000):  # Don't infinite loop while learning
            action = select_action(state)
            state, reward, done, _ = env.step(action)
            if args.render:
                env.render()
            policy.rewards.append(reward)
            if done:
                break

        running_reward = running_reward * 0.99 + t * 0.01
        finish_episode()
        if i_episode % args.log_interval == 0:
            print('Episode {}\tLast length: {:5d}\tAverage length: {:.2f}'.format(
                i_episode, t, running_reward))
        if running_reward > env.spec.reward_threshold:
            print("Solved! Running reward is now {} and "
                  "the last episode runs to {} time steps!".format(running_reward, t))
            break

if __name__ == '__main__':
main()

I am interested in the function finish_episode():

the line

 rewards = (rewards - rewards.mean()) / (rewards.std() + eps)

makes no sense to me.

I thought this might be baseline reduction, but I can't see why divide by the standard deviation.

If it isn't baseline reduction, then why normalize the rewards, and where should the baseline reduction go?

Please explain that line

It's just a hack to normalize the rewards to make optimization less problematic in cases where the reward might have very large/small values. It's fine because scaling the rewards by a constant factor won't change what the optimal policy is. You can think of the mean reward as the baseline.


What does 'acting greedily' mean? I wanted to clarify the term 'acting greedily'. What does it mean? Does it correspond to the immediate reward, future reward or both combined? I want to know the actions that will be taken in 2 cases:

$v_\pi(s)$ is known and $R_s$ is also known (only).
$q_{\pi}(s, a)$ is known and $R_s^a$ is also known (only).

In RL, the phrase "acting greedily" is usually short for "acting greedily with respect to the value function". Greedy local optimisation turns up in other contexts, and it is common to specify what metric is being maximised or minimised. The value function is most often the discounted sum of expected future reward, and also the metric used when defining a policy as "acting greedily".
It is possible to define a policy as acting greedily with respect to immediate expected reward, but not the norm. As a special case, when the discount factor $\gamma = 0$ then it is the same as acting greedily with respect to the value function.
When rewards are sparse (a common situation in RL), acting greedily with respect to expected immediate reward is not very useful. There is not enough information to make a decision.

I want to know the actions that will be taken in 2 cases:

$v_\pi(s)$ is known and $R_s$ is also known (only).

To act greedily in RL, you would use the value function $v_\pi(s')$ - the value function of the next states. To do so, you need to know the environment dynamics - to go with the notation $R_s$ you should also know the transition matrix $P_{ss'}^a$ - the probability of transitioning from $s$ to $s'$ whilst taking action $a$:
$$\pi'(s) = \text{argmax}_a \sum_{s'} P_{ss'}^a(R_{s} + \gamma v_{\pi}(s'))$$
Notes:

This assumes $R_{s}$ is your immediate reward for leaving state $s$. Substitute $R_{s'}$ if the reward matrix is for entering state $s'$ instead.

The policy gained from acting greedily with respect to $v_\pi(s)$ is not $\pi$, it is (a usually improved) policy $\pi'$

$q_{\pi}(s, a)$ is known and $R_s^a$ is also known (only).

To act greedily in RL, you would use the value function $q_{\pi}(s, a)$, and this is much simpler:
$$\pi'(s) = \text{argmax}_a q_{\pi}(s, a)$$
Again, the policy gained from acting greedily with respect to $q_\pi(s,a)$ is not $\pi$, it is (a usually improved) policy $\pi'$


When will the number of neurons in AI systems equal the human brain? Based on fitting to historical data and extrapolation, when is it expected that the number of neurons in AI systems will equal those of the human brain?

I'm interested in a possible direct replication of the human brain, which will need equal numbers of neurons.

Of course, this assumes neurons which are equally capable as their biological counterparts, which development may happen at a faster or slower rate than the quantitative increase.

Some back of the envelope calculations :

  number of neurons in AI systems

The number of neurons in AI systems is a little tricky to calculate, Neural Networks and Deep Learning are 2 current AI systems as you call them, specifics are hard to come by (If someone has them please share), but data on parameters do exist, parameters are more analogous to synapses (connections) than neurons (the nodes in between connections) somewhere in the range of 100-160 billion is the current upper number for specialized networks.

Deriving the number of neurons in AI systems from this number is a stretch since these AIs emulate certain types of connections and sub assemblies of neurons, but let's continue...

  equal those of the human brain?

So now let's look at the brain, and again this are all contested numbers. Number of neurons ~ 86 Billion, Number of Synapses ~ 150 Trillion, another generalization: average number of synapses per neuron ~ 1,744.

So now we have something to compare, and I can't stress this enough, these are all wonky numbers, so let's make our life a little easier and divide :

Number of Synapses (Brain ) : 150 trillion /  Number of parameters AIs : 150 billion = 1,000 or in other words current AIs would have to scale by a factor of one thousand their connections to be on par with the brain...

Number of Neurons (Brain ) : 86 Billion / Number of Neurons AIs ( 150 billion / 1,744 )  = 86 Million equivalent AI Neurons

Which makes sense, mathematically at least : you can multiply the factor ( 1000 ) times the current number of equivalent AI Neurons ( 86 million) to get the number of neurons in the human brain (86 Billion)

  When ?

Well,let's use  moore's law ( number of transistors processing power doubles about every 2 years ) as a rough measure of technological progress:

     #AI NEURONS            YEAR
     86,000,000             2016
     172,000,000            2018
     344,000,000            2020
     688,000,000            2022
     1,376,000,000          2024
     2,752,000,000          2026
     5,504,000,000          2028
     11,008,000,000         2030
     22,016,000,000         2032
     44,032,000,000         2034
     88,064,000,000         2036

     # NEURONS HUMAN BRAIN
     86,000,000,000

So, if all this made sense to you, somewhere around the year 2035.


How do I represent a multi-dimensional state using a neural network? I have a set of 15 unique playing cards from a deck of 52 playing cards. A given state is represented by the respective card values in the set of 15 cards, where the card value is a prime number associated with that card. For example, AH is represented by 3.

How should I represent a single state for the NN? Should it be a list of the 15 prime numbers representing the list of cards? I was hoping that I could represent a single state as the sum of each of all 15 prime numbers and then throw that sum through a sigmoid function. My concern, however, is that the NN will lose information if I reduce the dimension of the state to a single attribute (even if that attribute is unique to that state - the sum of n prime numbers is unique compared to the sum of any other n prime numbers).

How important is the dimensionality of each state for Deep Q Learning? I'd really appreciate even some general direction.

In my humble opinion, it seems like it is important to have them separated, if having a certain card can influence the result in some way that is not its prime value, instead of not only using the sum. But it depends on the game and its rules. For example:

If having 5 cards of hearts in the set of 15 cards makes you win the game, then if you only represent the state as the sum of the value of the cards, the DQN will never learn that it was not the whole 15 cards that caused you to win, but only a specific part of the set.


What are trap functions in genetic algorithms? What are trap functions in genetic algorithms? Suppose you ran a GA with a trap function and examined the population midway through the run. Can someone explain what you would expect the population to look like?

Traps are functions that are designed to have a very obvious gradient that leads to basically the second-best solution, with the best one being very far removed from that, often the complement of the second-best.
Take the 1-max problem. You have N bits, and the fitness of each individual is just the number of 1 bits in the string. If you run a GA on that, you'd expect to see an initial random distribution of 1s and 0s across the population fairly quickly start to converge to strings of all 1s. Now let's add one more clause to the fitness criteria. Instead of f(0)=0, let f(0)=N+1. This gives you a trap function. The "trap" is the solution of all 1s. Everything in the search space points to this being the best solution, but it's actually maximally far away from the best solution.
In terms of dyanmics, now the optimal solution is the string of all 0s. But unless you happen to very quickly stumble across that string, you likely never will. That is, there's some slight chance that your initial population included 00001111 and 11110000 and you crossed them over in the middle and got the optimum. Or maybe you had 00001000 and you got lucky and mutated that one bit to a zero. But if you don't do that immediately, you're screwed, because the algorithm is going to pretty relentless drive all the zero bits out of the population. No matter what it does, flipping a 0 to a 1 is always better unless it would otherwise lead to the single string of all 0s, so there's constant pressure to find more and more 1 bits. A few generations in, you might have 11110110, but you're never realistically going to randomly mutate all six of those 1s to 0s. And you have to get it all in one shot. Any subset of fewer than six of those bits being flipped will have worse fitness than you started with, and be selected against.


Possible model to use to find pixel locations of objects I want to make a model that outputs the centre pixel of objects appearing in an image.

My current method involves using a CNN with L2 loss to output an image of equivalent size to the input where each pixel has a value of 1 if it is the center of an object and 0 otherwise. Each input image has roughly ~80 objects.

The problem with this is the CNN learns the easiest way to reduce the error, which is having the entire output be 0, because for 97% of cases that's correct. As such, error decreases but it learns nothing.

What is another potential method for training a network to do something similar? I also tried adding dropout, which made the output a lot more noisy and it seemed to learn ok, but eventually ended up in the same state as before with the entire output being 0, never really seeming to learn how to output the locations of objects.

from what I understand you are building you own model for this specific use case. From my perspective I would try not to reinvent the wheel, as it is said, and use an already proven and working model such as the YOLOs (v1, v2 and v3).

YOLO does not tell you the center pixel of the image directly but it tells you the center cell, with respect to the predicted object, of a grid (which is built on top of the image) responsible for predicting each object. See on the left image how the grid is built on top of the input image, then YOLO computes a probability map, and then the bounding boxes are predicted from the cell in the object's center. I have highlighted which cells would be responsible for predicting each object in the rightmost image. (Image from YOLOv1 paper)

The grid can have different resolutions but if you make it equal to the image size, then you would have the center pixel of each object predicted. This is because YOLO predicts objects in each cell of the grid, so if the grid is equal to the image size, YOLO will predict objects in each pixel.

As an example, imagine you have an input image of $[H \times W] = [416 \times 416]$ then YOLO would compute a grid of $[S_1 \times S_2]=[52 \times 52]$ on top of it. And predict objects in the center cell of the $[S_1 \times S_2]$. So, if you tune YOLO for computing a grid such as $[S_1 \times S_2] = [H \times W]$, then YOLO would output objects prediction with respect to the image pixels, in other words, YOLO would predict bounding boxes centered in the image pixel on the object's center.

This is how I would proceed for this use case, I hope it helps you or at least give you some clues about how to proceed further! Cheers! :)

NOTE: I chose the image size and grid size with numbers I usually see at work. Specifically, using YOLOv3. In YOLOv3, for aninput image of $[H \times W] = [416 \times 416]$, 3 grids are built, with different resolutions (for predicting big and small objects), with the following grids sizes are: $[13 \times 13], [26 \times 26], [52 \times 52]$


How does the AlphaGo Zero policy decide what move to execute? I was going through the AlphaGo Zero paper and I was trying to understand everything, but I just can't figure out this one formula:

$$
\pi(a \mid s_0) = \frac{N(s_0, a)^{\frac{1}{\tau}}}{\sum_b N(s_0, b)^{\frac{1}{\tau}}}
$$

Could someone decode how the policy makes decisions following this formula? I pretty much understood all of the other parts of the paper, and also the temperature parameter is clear to me.

It might be a simple question, but can't figure it out.

The formula in question uses a function N(state, action) that defines a visit count of a state-action pair (introduced on page 3). To describe how it is used, lets first describe the steps of AlphaGo Zero as a whole.

There are 4 "phases" to the Monte-Carlo tree search in AlphaGo Zero as depicted in Figure 2. The first 3 expand and update the tree and together are the "search" in Monte-Carlo tree "search" in AlphaGo Zero.

Select an edge (action) in the tree with maximum action-value Q (plus upper confidence bound U)
Expand and evaluate the leaf node using the network
Backup Action-values Q are updated to track the evaluations of the Value in the subtree.
Play - After the "search" is complete, the search probabilities are returned proportional to the visitation count of the nodes of the tree.*

* This is where the formula in question comes into play (pun intended). During the "search", nodes that looked good were expanded on and thus their visitation counts were updated. So the formula is essentially describing this logic:

Good nodes have higher counts, so choose the nodes with higher counts often

But what if there is a really good node but it hasn't been visited a lot so its not chosen?

This is where the temperature parameter comes in:

If the temperature is 1, this selects moves proportionally to their visit counts.
If the temperature is 0 (not actually but rather in infinitesimal that approaches 0), and with some added noise, it "ensures that all moves may be tried, but the search may still overrule bad moves."

So altogether, the formula is saying : Pick good things most of the time

The mathematical evaluation of the formula is described below:

AlphaGo Zero defines the probability of each action (aka the policy) by that formula. If there are 3 nodes, A, B and C, and they have each been visited 10, 70, and 20 times (100 times in total), respectively, then the probability of taking those actions is:

P(A) = 10/100 = .10
P(B) = 70/100 = .7
P(C) = 20/100 = .2


Do policy independent state and action values exist in reinforcement learning? The state value function $V(s)$ is defined as the expected return starting in state $s$ and acting according to the current policy $\pi(a|s)$ till the end of the episode. The state-action values $Q(s,a)$ are similarly dependent on the current policy.

Is it also possible to get a policy independent value of a state or an action?
Can the immediate reward $r(s,a,s')$ be considered a noisy estimate of the action value?

Do policy independent state and action values exist in reinforcement learning?

No. They do not exist, because in order to progress in any MDP and receive any reward - i.e. to get any measure of value - you must take an action. Any consistent means of selecting actions is a policy, and the nature of that policy impacts which transitions and rewards you expect to observe, which in turn affects the expected value. Inconsistent means of selecting actions would have no meaning with respect to "expected future return", they would just be measurements that you made in the past.

The closest you can get to a no-policy definition would be values with respect to "special" policies that apply in general to nearly all MDPs:

Value functions for the uniformly distributed random policy.
Value functions for any optimal policy (if there is more than one optimal policy, then all the value functions for them will be equal).
Value functions for any "inverse optimal" policy - i.e. the policy that has lowest possible return. This one is not so useful, although it exists theoretically.

The first two can be useful measurements of an MDP. Although the uniform random policy might not be the best, it encapsulates the situation where the agent has absolutely no knowledge of the MDP, and can be a baseline for comparison. The optimal value functions are often a target for learning algorithms, and sometimes you can calculate bounds or even exact targets for these independently of the learning process, to measure how well an algorithm performs on some test MDP.

  Can the immediate reward $r(s,a,s')$ be considered a noisy estimate of the action value?

No. Using that notation of the function, it is typically already the expected immediate reward. It is entirely independent of reward seen in any other transitions or time steps, so is systematically incorrect as an estimate for future return in many cases - the only exception being if you know all future rewards will be precisely $0$. So it is an unbiased estimate of an action value if $s'$ is a terminal state.

Immediate reward is also a good estimate of an action value if the discount factor $\gamma = 0$. However, that requires you to define the problem as solving for immediate rewards only, which is not usually a free choice when trying to optimise the behaviour of the agent.


What happens if I train a network for more epochs, without using early stopping? I have a question about training a neural network for more epochs even after the network has converged without using early stopping criterion.

Consider the MNIST dataset and a LeNet 300-100-10 dense fully-connected architecture, where I have 2 hidden layers having 300 and 100 neurons and an output layer having 10 neurons.

Now, usually, this network takes about 9-11 epochs to train and have a validation accuracy of around 98%.

What happens if I train this network for 25 or 30 epochs, without using early stopping criterion?

Training a neural network for "too many" epochs than needed without using early stopping criterion leads to overfitting, where your model's ability to generalize decreases.


How can I create my own Google duplex? I am trying to create my own variant of Google duplex however, it won't make calls but just have a real time conversation.

My question is, where and how to start?

How do I train my model with real conversation and how do I make speech sound almost human like? Where do I incorporate RNN and how can I make my model understand nuances?

https://youtu.be/p3PfKf0ndik trying to create something like this.

NOTE: I understand this is very difficult but I am not looking for perfection. I am just creating this as I love doing this. Thank you

First of all, you need to realise that you will not be able to do it. Google is a multi-billion dollar company, with a large number of very bright and well-funded researchers. That tells me that it is not something a single person can do by themselves.

Then, you already have some pre-conceptions about it. You want to use a machine learning approach, using neural networks. I would start with a blank slate and think about the problem first, before considering the tools I would want to use.

If you don't know were to start, I would suggest you have a look at Eliza, which is old but still very hard to improve on. There are many open source implementations of it available, and it wouldn't be too hard to implement your own from scratch.

Eliza uses a symbolic approach (ie no neural networks), which has the big advantage that you can see what is going on, and you can actually understand how it works. Have a play around with it, create some chatbots, and see how you can make the conversations sound more human-like. Then, when you have a clearer idea about this, proceed to other frameworks such as wit.ai or Microsoft's LUIS. There you trade in control for ease of use; but I suggest you don't do this without understanding what you're actually doing first.


Need Help With LSTM Neural Networks I have been researching LSTM neural networks.  I have seen this diagram a lot and I have few questions about it. Firstly, is this diagram used for most LSTM neural networks?

Secondly, if it is, wouldn't only having single layers reduce it's usefulness?

(1) Yes this is the diagram for a classical LSTM unit. Of cause there are some variants and those diagrams would look slightly different.

(2) It is very common for researchers to use more than one layers of LSTM and achieves better performance than a single layer one. A common way to "stack" LSTMs is to use the previous layer's output ($h_t$ in your diagram) as the input to the next layer ($x_t$). However, I have seldom seen any successful application of 5+ layers of LSTMs, while for CNNs it is common to use tens or even hundreds of layers.


How close are we to having an AI that can play Magic: The Gathering objectively well? With tools like open AI will we be able to teach an AI to build its own decks? build a deck from a limited pool? or draft? evaluate the power level of a card?

This is a very specific task, with clearly defined parameters, so it would already theoretically be within the scope of current AI technology to do this.

The AI would need to learn how to make decisions, and the best way to do this is the approach taken to teaching an AI to play Go - seeing thousands of example games by experts, and playing itself thousands of times.

The AI won't necessarily "understand" what a card represents, the way a human would, but it can learn to make the same kinds of decisions as the human would.

The difficulties would be purely practical - Go is very easy to represent digitally, because the options for action are limited to placing a stone on one of the intersections, and there is only one opponent. Magic is more complex, so the developers would need to spend sufficient resources to be quite sure they had captured all the relevant variables in the digital representation. Then, of course, they would need to encode thousands of games of Magic (or deck-building processes) into that digital format, so the AI could study them.