Why is the larger value, as opposed to the smaller one, chosen, in the hill climbing algorithm? In the hill climbing algorithm, the greater value, compared to the current value, is selected, but I cannot understand why it takes the larger value instead of the smaller one. Why is that?

I greatly appreciate the inclusion of figures in your answers.

When we climb a hill:

We move higher in altitude. The person who is climbing, will always look for rocks/mud on the hill that are higher, so that he can climb higher.
That is what the algorithm does too. We are assuming that there is a hill of numbers. The larger numbers are placed higher than the smaller numbers. So if we want to climb up the hill, we search for the larger numbers.
Comparing this with the real world hill climbing, simply assume that every rock on the hill has a number written on it. The number will be the altitude of the rock, from sea level height. So if you want to climb up, you just have to search for the rock with a higher number than the rock you are standing on now.


How is AlphaZero different from Stockfish or Rybka? I don't know much about AI or chess engines, but what is the fundamental difference between AlphaZero and Stockfish or Rybka?

Stockfish is free software (source while AlphaGo can only be used by employees at Deepmind. This is important, because it means all answers to this question can only rely on the AlphaGo paper. Some decisions during the matches (e.g. giving limited time per move and not per game; giving different computational power) lead to unclarity how good alpha go really is.

Stockfish  uses Alpha-beta search with a hardcoded metric to evaluate how good a position is.

In contrast, AlphaGo uses Monte Carlo tree search and convolutional neural networks. They are trained in an reinforcement learning setting.

AlphaGo is promoted as being almost directly applicable to different settings (Go, Chess), while stockfish is only applied to Chess. The techniques of stockfish can also be applied to Go, but the problem is the board evaluation. For Chess it's easy compared to Go.

References

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, December 2017.
Mastering the Game of Go without Human Knowledge is about Alpha Go Zero


Concrete example of latent variables and observables plugged into the Bayes' rule In the context of the variational auto-encoder, can someone give me a concrete example of the application of the Bayes' rule

$$p_{\theta}(z|x)=\frac{p_{\theta}(x|z)p(z)}{p(x)}$$

for a given latent variable and observable?

I understand with VAE's we're essentially getting an approximation to $p_{\theta}(z|x)$ that models the distribution that we think approximates the latent variables, but I need a concrete example to really understand it.

Let's assume the probability distributions are Gaussian (or normal) distributions. In other words, in the Bayes' rule

\begin{align}
p(z|x)=\frac{p(x|z)p(z)}{p(x)}
\tag{1}\label{1}
\end{align}

The posterior $p(z|x)$, the likelihood $p(x|z)$, the prior $p(z)$ and the evidence (or marginal) $p(x)$ are Gaussian distributions. You can assume this because Gaussian distributions are closed under conditioning and marginalization.

For simplicity, let's further assume that they are univariate Gaussian distributions. Given that the Gaussian distribution is a continuous probability distribution, it has an associated probability density function (rather than a probability mass function, which is associated with discrete probability distributions, such as the Bernoulli distribution). The probability density function of the Gaussian distribution is

\begin{align}
f(x \mid \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2} } e^{ -\frac{(x-\mu)^2}{2\sigma^2} } \tag{2}\label{2}
\end{align}

where $\mu$ and $\sigma^2$ are respectively the mean and variance of the Gaussian distribution and $x$ is a variable (similarly to a variable $x$ in any mathematical function $f(x)$). So, given a concrete value for $x$, for example, $x=1$, then $f(x=1, \mu, \sigma^2)$ is a so-called density value (rather than a probability, which a probability mass function returns, given an input). For example, let's assume that the mean $\mu=0$ and the variance $\sigma^2 = 1$, then, for $x=1$, the density will be

$$
f(1 \mid 0, 1) = \frac{1}{\sqrt{2\pi} } e^{ -\frac{1}{2} }
$$

So, to obtain the concrete density value, I've just replaced the concrete values of $x$, $\mu$ and $\sigma^2$ in equation \ref{2}.

To calculate the posterior $p(z|x)$ in equation \ref{1}, you just need to replace the likelihood $p(x|z)$, the prior $p(z)$ and the evidence $p(x)$ with the Gaussian probability density shown in equation \ref{2}, so you will have

\begin{align}
p(z|x)=\frac{f_{X\mid Z}(x \mid \mu_{X\mid Z}, \sigma^2_{X\mid Z}, z) f_{Z}(z \mid \mu_{Z}, \sigma^2_{Z})}{f_{X}(x \mid \mu_{X}, \sigma^2_{X})}
\tag{3}\label{3}
\end{align}

I've explicitly added a subscript to the means and variances of each probability density, given that, for example, the mean of the probability density $f_{X\mid Z}$ might be different than the mean of the probability density $f_{Z}$ or $f_{X}$, etc. So, to get the actual density value (a real number) that represents $p(z|x)$, you just need to replace $f_{X\mid Z}$, $f_{Z}$ and $f_{X}$ with the definition of the Gaussian density function in \ref{2} with their actual mean and variance values. I'll let you do this, given that this is really just a matter of picking up a concrete value for the means and variances and doing some algebra.

If you assume the posterior, the likelihood, the prior or the evidence to have a different distribution, you will do the same thing, but using the probability density or mass function of your chosen distribution.

In the context of the variational auto-encoder, you will be learning the mean and variance of the distribution, so the mean and variance will not be fixed, but they will be the parameters that you want to find. However, this does not change the way you apply the Bayes' rule.


What are the main differences between sparse autoencoders and convolution autoencoders? What are the main differences and similarities between sparse autoencoders and convolution autoencoders?

When should one be preferred over the other? What are their applications?

(References are welcome. Somehow I was not able to find any comparisons of these autoencoders although I looked in a few textbooks and searched for material online. I was able to find the descriptions of each autoencoder separately, but what I am interested in is the comparison.)

Sparse auto-encoders (SAEs) are auto-encoders that impose constraints on the parameters so that they are sparse (i.e. zero or close to zero). This can be achieved in different ways. For example, you can train an auto-encoder with a loss function that includes a penalty term (to constraint the parameters to be close to zero or zero) or you e.g. set the smallest activations to zero.

Convolution auto-encoders (CAEs) are auto-encoders that use the convolution operation. So, they can be viewed as the auto-encoder version of convolutional neural networks. For this reason, they are particularly suited to compress and reconstruct images. The authors of the original paper, Stacked Convolutional Auto-Encoders for Hierarchical Feature Extraction, train them with gradient descent and back-propagation by minimizing the mean squared error, so there's e.g. no penalty term, but you can probably combine SAEs with CAEs.

Of course, you could say that CAEs are sparse with respect to the traditional auto-encoder (in the same way that you can say that CNNs are sparse with respect to fully connected neural networks), so, in this sense, CAEs are also sparse auto-encoders.


Is it necessary to standardise the expected output Normalisation transform data into a range:
$$X_i = \dfrac{X_i - Min}{Max-Min}$$
Practically, I found out that the model doesn't generalise well when using normalisation of input data, instead of standardisation (another formula shown below).
Before training a neural net, data are usually standardised or normalised. Standardising seems good as it makes the model generalise better, while normalisation may make the model not working with values out of training data range.
So I'm using standardisation for input data (X), however, I'm confusing whether I should standardise the expected output values too?
For a column in input data:
$$X_i = \dfrac{(X_i - Mean)}{Standard\ Deviation\ of\ the\ Column}$$
Should I apply this formula to the expected output values (labels) too?

It depends, as mentioned in comments, on your model and labels. For example how would you use standardisation on multi classification problem?
Generally, standardisation is more flavourable for input data as its mean is around 0.
I assume you have a regression model and in that case using standardisation could be better than normalisation.


Why is learning $s'$ from $s,a$ a kernel density estimation problem but learning $r$ from $s,a$ is just regression? In David Silver's 8th lecture he talks about model learning and says that learning $r$ from $s,a$ is a regression problem whereas learning $s'$ from $s,a$ is a kernel density estimation. His explanation for the difference is that if we are in a stochastic environment and we are in the tuple $s,a$ then there might be a 30% chance the wind will blow me left, and a 70% chance the wind will blow me right, so we want to estimate these probabilities.

Is the main difference between these two problems, and hence why one is regression and the other is kernel density estimation, because with the reward we are mainly concerned with the expected reward (hence regression) whereas with the state transitioning, we want to be able to simulate this so we need the estimated density?

Is the main difference between these two problems, and hence why one is regression and the other is kernel density estimation, because with the reward we are mainly concerned with the expected reward (hence regression) whereas with the state transitioning, we want to be able to simulate this so we need the estimated density?

Yes.

An expected reward function from $s,a$ is all you need to construct valid Bellman equations for value functions. For example

$$q_{\pi}(s,a) = r(s,a) + \gamma\sum_{s'}p(s'|s,a)\sum_{a'}\pi(a'|s')q(s',a')$$

is a valid way of writing the Bellman equation for action values. You can derive this from $r(s,a) = \sum_{r,s'}rp(r,s'|s,a)$ and $q_{\pi}(s,a) = \sum_{r,s'}p(r,s'|s,a)(r + \gamma\sum_{a'}\pi(a'|s')q(s',a'))$ if you have the equations in that form.

However, in general there is no such thing as an "expected state" when there is more than one possible outcome (i.e. in environments with stochastic state transitions). You can take a mean of the state vector representations over the samples you see for $s'$ but that is not the same thing at all and could easily be a representation of an unreachable/nonsense state.

In some cases, the expectation $\mathbb{E}_{\pi}[x(S_{t+1})|S_t=s, A_t=a]$ where $x(s)$ creates a feature vector from any given state $s$, $x(s): \mathcal{S} \rightarrow \mathbb{R}^d$, can be meaningful. The broadest and most trivial example of this is for deterministic environments. You may be able to construct stochastic environments where there is a good interpretation of such a vector, even if it does not represent any reachable state.

Simple one-hot encoded states could maybe made to work like this by representing a probability distribution over states (this would also require re-interpretations of expected reward function and value functions). That is effectively a kernel density function over discrete state space.

In general knowing this $\mathbb{E}_{\pi}[x(S_{t+1})|S_t=s, A_t=a]$ expected value does not help resolve future rewards, as they can depend arbitrarily on specific state transitions.


Is it possible to train the neural network to solve math equations? I'm aware that neural networks are probably not designed to do that, however asking hypothetically, is it possible to train the deep neural network (or similar) to solve math equations?

So given the 3 inputs: 1st number, operator sign represented by the number (1 - +, 2 - -, 3 - /, 4 - *, and so on), and the 2nd number, then after training the network should give me the valid results.

Example 1 (2+2):

Input 1: 2; Input 2: 1 (+); Input 3: 2; Expected output: 4
Input 1: 10; Input 2: 2 (-); Input 3: 10; Expected output: 0
Input 1: 5; Input 2: 4 (*); Input 3: 5; Expected output: 25
and so

The above can be extended to more sophisticated examples.

Is that possible? If so, what kind of network can learn/achieve that?

Yes, it has been done!

However, the applications aren't to replace calculators or anything like that. The lab I'm associated with develops neural network models of equational reasoning to better understand how humans might solve these problems. This is a part of the field known as Mathematical Cognition. Unfortunately, our website isn't terribly informative, but here's a link to an example of such work.

Apart from that, recent work on extending neural networks to include external memory stores (e.g. Neural Turing Machines) tend to use solving math problems as a good proof of concept. This is because many arithmetic problems involve long procedures with stored intermediate results. See the sections of this paper on long binary addition and multiplication.


Is A* with an admissible but inconsistent heuristic optimal? I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows:
Let $P$ and $Q$ be two costs from any respective nodes $p$ and $q$ to the goal. Assume $P<Q$. Let $P'$ be an estimation of $P$. $P'\le P \Rightarrow P'<Q$. It follows from uniform-cost-search that the path through $p$ must be explored.
What I don't understand, is why the idea of an admissible heuristic does not apply as well to "graph-search". If a heuristic is admissible but inconsistent, would that imply that $A*$ is not optimal? Could you please provide an example of an admissible heuristic that results in a non-optimal solution?

It depends on what you mean by optimal.

A* will always find the optimal solution (that is, the algorithm is admissible) as long as the heuristic is admissible. (Note that the definition of admissible is overloaded and means something slightly different for an algorithm and a heuristic.)

If you talk about the set of nodes expanded by A*, then it expands the minimal set of nodes up to tie-breaking even with an inconsistent heuristic.

If you talk about the number of expansions, then A* is not optimal. A* can perform up to $2^N$ expansions of $N$ states with an inconsistent heuristic. This result comes from Martelli, 1977.

Algorithm B has worst-case $N^2$ expansions and budgeted graph search (BGS) has worst-case $N \log C$, where $C$ is the optimal solution cost.

You can see a demo that shows the worst-case performance of A* as well as the performance of BGS here:
https://www.movingai.com/SAS/INC/


What are the risks associated with regulating AI? As part of a research project for college, I would like to understand what many of you astern to be the risks associated with regulating Artificial Intelligence. Such as whether regulation is too risky in regards to limiting progress or too risky in regards to uninformed regulation.

I don't think regulating something necessarily causes that regulation to defacto become a "risk".

Regulation - including overregulation - may, in fact, aid in the dialogue between practitioners, which may end up educating the regulators, the public and the practitioners themselves.

My answers to your survey would most likely be "it depends...", or "no risk", which isn't to say it's not an impediment, but just not a "risk", per se.


On what basis is MATLAB "inflexible" to perform ML/AI research on it? During a course review, I have provided my opinion on the course overall. I stated that MATLAB is also a great environment to program and do research for ML/AI, but my professor seemed to have taken my comments as a joke and told me "If you take a look at the statistics, then you'll see that MATLAB is not a feasible environment to innovate and research topics in ML/AI".
As an undergraduate who is new to machine learning, I would hope to understand more and not debate on which is better (MATLAB vs Python), but rather to know whether there is a bias against MATLAB or there are actually reasons that make MATLAB not a good environment to research and program ML topics.

(This question is could be considered off-topic or opinion-based, but I will answer it by providing facts that could hinder the adoption of MATLAB by AI researchers).
There are 2 main reasons why MATLAB may not be the "best" programming language/environment for research (in AI and other areas too)

It's closed source (i.e. it's more difficult to extend it; the most similar open-source alternative to MATLAB would be Octave)
It's owned by a company (i.e., it's proprietary, so, for you to use MATLAB, you need a license, which could be given to you by your university, which is my case, or you need to buy it, but not everyone can afford this).

In my view, these are clear obstacles for people that want to share their research and make sure that people can reproduce their results or build new ideas on top of them. However, in some cases, using proprietary software for research may be the best (or even only) option (see e.g. this for more info). In fact, I have also seen MATLAB being used for research in artificial intelligence (here is an example), but the choice of MATLAB might have been due to the familiarity of the authors with the language/environment.


Is the paper "Reducing the Dimensionality of Data with Neural Networks" by Hinton relevant? Is the paper "Reducing the Dimensionality of Data with Neural Networks" by G. Hinton and R. Salakhutdinov relevant?

It seems that the deep learning textbook by Goodfellow, Bengio & Courville (2016) doesn't cite that paper.

Does that indicate that paper is not as important as others to Deep learning? If yes, I would skip this one to accelerate my process of learning.

No; there are too many publications around for anybody to keep track of everything, so unless it is a seminal paper, you cannot draw any conclusions from this. They could simply have missed it.

Especially if it is a textbook for beginners, more advanced papers are often not mentioned, as they might be too complex to understand.

So you have to decide for yourself if that paper is relevant to you. To me it sounds like a specific application of neural networks; if the dimensionality of the input data is an issue for you, it might be, otherwise probably not.


How do we compute the target value when the agent ends up in the terminal state? I am working on a deep reinforcement learning problem. Throughout the episode, there is a small positive and negative reward for good or bad decisions. In the end, there is a huge reward for the completion of the episode. So, this reward function is quite sparse.
This is my understanding of how DQN works. The neural network predicts quality values for each possible action that can be taken from a state $S_1$. Let us assume the predicted quality value for an action $A$ is $Q(S_1, A)$, and this action allows the agent to reach $S_2$.
We now need the target quality value $Q_\text{target}$, so that using $Q(S_1, A)$ and $Q_\text{target}$ the temporal difference can be calculated, and updates can be made to the parameters of the value network.
$Q_\text{target}$ is composed of two terms. The immediate reward $R$ and the maximum quality value of the resulting state that this chosen action leaves us in, which can be denoted by $Q_\text{future} = \text{max}_a Q(S_2, a)$, which is in practice obtained by feeding the new state $S_2$ into the neural network and choosing (from the list of quality values for each action) the maximum quality value. We then multiply the discount factor $\gamma$ with this $Q_\text{future}$ and add it to the reward $R$, i.e. $Q_\text{target} = R + \gamma \text{max}_a Q(S_2, a) = R + \gamma Q_\text{future}$.
Now, let us assume the agent is in the penultimate state, $S_1$, and chooses the action $A$ that leads him to the completion state, $S_2$, and gets a reward $R$.
How do we form the target value $Q_\text{target}$ for $S_1$ now? Do we still include the $Q_\text{future}$ term? Or is it only the reward in this case? I am not sure if $Q_\text{future}$ even has meaning after reaching the final state $S_2$. So, I think that, for the final step, the target value must simply be the reward. Is this right?

Now, let us assume the agent is in the penultimate state, $S_1$, and
chooses the action $A$ that leads him to the completion state, $S_2$,
and gets a reward $R$.
How do we form the target value $Q_\text{target}$ for $S_1$ now? Do we still include the $Q_\text{future}$ term? Or is it only the reward
in this case?

Your term "completion state" is commonly called "terminal state". In a terminal state, there are no more actions to take, no more time steps, and no possibility to take any action. So, by definition, in your state $S_2$, the expected future reward is $0$.
Mathematically, this is often noted like $v(S_T) = 0$ or $q(S_T,\cdot) = 0$ with the $T$ standing for last time step of the episode, and dot standing in for the fact that no action need to be supplied, or the specific action value is not relevant. So, therefore using your terms, $Q_\text{future} = \text{max}_a Q(S_2, a) = 0$
That makes the equations work in theory, but does not explain what to do in code. In practice in your code, you would do as you suggest and use just the reward when calculating the TD target for $Q(S_1, A)$. This is typically done using an if block around the done condition e.g.
if done:
  td_target = r
else:
  td_target = r + gamma * np.max(q_future_values)
end

Of course, the details depend on how you have structured and named your variables. You will find code similar to this in most DQN implementations though.
You should not really try to learn $V(S_2)$ or $Q(S_2, A)$, or calculate TD target starting from $S_2$, because the result should be $0$ by definition.


Building Profile Based Off Speech Patterns Has there been research done regarding processing speech then building a "speaker profile" based off the processed speech? Things like matching the voice with a speaker profile and matching speech patterns and wordage for the speaker profile would be examples of building the profile. Basically, building a model of an individual based solely off speech. Any examples of this being implemented would be greatly appreciated.

Yes, there is. An extremely quick search found this:
Multimodal Speaker Identification Based on Text_and_Speech.

Let me tl;dr for you: (My abstract addition in Italics)

Novel method for speaker identification based on both speech utterances and their transcribed text.

They first transcribed text of each speaker’s is processed by using probabilistic latent semantic indexing (PLSI) that models each speaker’s vocabulary which is closely related to his/her identity, function, or expertise.

The speech to text used by users is DARPA's Efficient, Affordable, Reusable Speech-to-Text (EARS) Program in MetadataExtraction (MDE).

By using Melfrequency cepstral coefficients (MFCCs) and dynamic range is quantized to a number of predefined bins in order to compute MFCC local histograms for each speech utterance, which is time-aligned with the transcribed text.

To test they used RT-03 MDE Training Data Text and Annotations corpus distributed by the Linguistic Data Consortium.

As for results: Identification rate versus Probe ID when 44 speakers are employed. Average identification rates for (a) PLSI: 69%; (b) MFCCs: 66%; (c) Both: 67%.

If you need more papers related, you could use a tool like https://the.iris.ai/ to find related papers.

Post edit: Hopefully now this post complies with the standards.


What is the impact of the number of features on the prediction power of a neural network? What is the impact of the number of features on the prediction power of an ANN model (in general)? Does an increase in the number of features mean a more powerful prediction model (for approximation purpose)?
I'm asking these questions because I am wondering if there is any benefit in using two variables (rather than one) to predict one output.
If there is a scientific paper that answers my question, I would thank you.

Based on the clarifications given in the comments on the original question, i will try my best to give an answer.
If the number of features increases, does the approximation capability of an ANN improve theoretically speaking?
It depends on whether this additional feature adds 'usefulness' to the data that was already supported. If you add a feature that is already in the dataset, it obviously will not increase the approximation capabilities. If you add a feature that is not yet in the current set of features and does influence the thing you are trying to approximate, then yes! There are some exceptions in this case of course, such as what if features are multicorrelated etc. It is not super important or measurable in ANNs, but statistics has a bunch of theory on this stuff. Simple statistical multiple regression has 4 assumptions and also checks for multicollinearity to see whether it is possible get 'useful' results from the data etc. As ANNs is super general, this is not applicable, but you could argue that similar practices could be looked into when seeking the best possible 'theoretical' validity of the features that you are using.
Does adding more features make your ANNs produce more accurate results (in practice)?
Again, it depends. If you indeed added a useful feature, then the possibility exists that your ANN will in practice be able to produce more accurate results. But if your ANN is not able to converge to a solution, then your results will be gibberish. It is more likely that a network is unable to converge if you just throw data at it. More data requires bigger networks etc. So it is highly dependent on your training method. AKA, if your added feature is useful and the method you use is sufficient, then I'd argue that, yes, adding a feature will most likely make your ANNs produce more accurate results.


Machine mathematical reasoning by clever substitutions, How to do with AI I have three equations that relates five variables {a, b, c, r, s} with a sum and two ratios.

Eq. 1: a = b + c;
Eq. 2: s = b / a;
Eq. 3: r = b / c.

Given two values for any of the five variables I get a solution. But, this is not the automation problem I want to solve.

I can have the solution of variable r by simply knowing s. This is solved by a "human algorithm" as follows.

Substitute a of Eq. 1 in Eq. 2.
Divide the second term of the new Eq. 2 by the variable c.
Replace b/c by the expression of Eq. 3.

That means s = r / (r+1).

The questions is -How can an AI algorithm solve this?, i.e. the machine should recognize that given the variable r she can obtain directly the variable s and do no require another variable.

What you're asking here is actually not reasoning but rather symbolic computation.  Sympy is an example of a library which does it.
Explaining computer algebra systems could be a series of lectures and this is too broad for a single question. To give you an idea: (1) represent equations symbolically (2) bring them in a normal form (3) substitute.
Although it is not elegant, you can simplify the problem by brute Force: try all combinations of solving for a variable and substituting it in the other equations.
Related:

How do symbolic math software work? | Mathematics Stack Exchange


What kinds of systems have so far failed to be modeled via supervised artificial network training? Artificial networks model systems with a set of inputs and outputs and expected behavior. To train a network for modeling such systems, hundreds, thousands, or millions of example inputs-output pairs may be required. This is called a labelled data set, and the network and its optimization algorithm are meant to find a set of network parameters that best match the I/O of the artificial network with the I/O of the system.

Are there any systems, for which sufficient labelled data sets exist, that have yet to be successfully modeled with artificial networks of any type (recurrent, deep, convolution, etc)?

I haven't seen any dataset where some standard models worked and neural networks utterly failed.

For columnar data (e.g. Excel files / database dumps / CSV files) which contain structured data usually tree-based models like random forests and gradient boosting work better, but neural networks are also usually way better than random.

If you demand other things, e.g. explanations for the decision then Bayesian models might give you an easier time. Or for baselines/simple implementations linear models. Or for real time applications...


How is back-propagation useful in neural networks? I am reading about backpropagation and I wonder why I have to backpropagate.

For example, I would update the network by randomly choosing a weight to change, $w$. I would have $X$ and $y$. Then, I would choose $dw$, a random number from $-0.1$ to $0.1$, for example. Then, I would do two predictions of the neural network and get their losses with the original neural network and one with $w$ changed by $dw$ to get the respective losses $L_{\text{original}}$ and $L_{\text{updated}}$. $L_{\text{updated}} - L_{\text{original}}$ is $dL$. I would update $w$ by $\gamma \frac{d L}{dw}$, where $\gamma$ is the learning rate and $L$ is the loss.

This does not need a gradient backpropagation throughout the system, and must have somehow a disadvantage because no one uses it. What is this disadvantage?

The method you propose is already known, its basically a numerical approximation to the gradient. It is not used to train neural networks because its well... an approximation. You still need to do two forward passes to get an approximation, which introduces noise and might make the training process fail.

Using backpropagation to compute the gradient is an exact solution, so why would you use an approximation if the exact computation is equally efficient?

Numeric approximations of the gradient only make sense if exact computation is not possible.


How can you do AI research by your own? Let's say you want to do AI research and publish some papers just by your own. Would you send them to an AI journal using just your name? Which AI journals are recommended?

Let me preface this by acknowledging that this question is prone to opinion. This answer is, in so far as it is possible, primarily observation based.

My understanding is that, when it comes to publishing in a journal, doing so as an individual (without backing from an institution) is, in general, going to be frowned upon.

As you may know: scientific research, including AI research, is generally subject to peer review. When it comes to journals, this is mandatory. The review process attempts to enhance and preserve the integrety of the information published. As an additional safeguard, submissions will often expected to be backed by endorsement from someone within the academic community (typically an institution).

However, and as Pasaba correctly points out (in his comment on the OP), research and publishing are not neccessarily the same thing. Furthermore, not having an endorsement does not not stop you from making a contribution to the field.

For example, you can publish code and/or articles on websites such as Github, and engage with communities of professional and hobbiest researchers around the web, (e.g. this Stack Exchange).

Note that there is also some scope for endorsement without being a direct member of a research institution. For example: arXiv, whilst not strictly a journal, is an open archive that supports endorsement by request.

Without knowing your circumstances, it's hard to know exactly what to do. However, my general advice is to find and engage with communities, and build a network of collaborative peers, rather than trying to succeed in an isolated fashion.


What is uncontrolled logging policy? I am reading Learning from Logged Implicit Exploration Data

It says

  Formally, given a dataset of the form S = (x, a, r_a)* generated by the interaction of an uncontrolled logging policy

What is such a policy?

This policy is usually referred to as the Behaviour Policy when talking about off-policy learning. It is the policy that actually takes actions in the world. The policy that one wants to learn, such as a greedy policy in Q learning, is know as the target policy. In this way the behaviour policy “logs” experience that the target policy (or policies) may learn from.


Should my agent be taking varying number of steps? My environment is set up so that my self-driving agent can take maximum of 400 steps (which is the end goal) before it resets with a completion reward. Despite attaining the end goal during the $\epsilon$-greedy stage, it still kills/crashes itself in subsequent episodes.
I would like to know if this common in RL (D3QN) scenarios.
A graph showing episodes vs steps has been placed below.

As one can see, the agent reaches 400 steps in episode 1000. But, in the subsequent episode, it falls down below 50 steps.

Your graph looks to me like a typical learning curve plotted for training process in reinforcement learning.
Looking at it in detail I can say:

There is clearly some learning occurring.

There is a strong random element throughout. As you say the epsilon is reduced to near zero by episode 2000, and I would assume a driving simulation is mostly deterministic but with a lot of state hidden from the agent, this mainly implies that episodes are started in different states.

There may be an effect from continued learning that causes the agent performance to vary so much. However, it is more likely towards the end that the agent is encountering new never-seen-before states and making poor decisions in them.

The resulting graph matches to my experience of training DQN agents where some of the hyperparameters are off. Probably you need to do some kind of exploration or search through those parameters.

From your comments:

Perhaps the model is subsequently overfitting? Or maybe there is some catastrophic forgetting?

These are possibilities that I cannot rule out by looking at the graph.
However, I think it is more likely that you have some agent design or hyperparameters that are not a good fit to the problem. Those hyperparameters could be almost anything - not enough episodes to cover variation, neural network too simple, neural network too complicated, epsilon decay too fast, poor choice of regularisation, experience replay memory too small, poor choice of optimiser, etc etc.
It is also possible you have limited the state model to the point that learning is hard or even impossible. A common beginner's mistake here is to use static sensor information such as a single current screenshot on each timestep, so the agent has no way to assess how fast it is going, or which way it is already turning etc (if your input includes direct knowledge of current speed, turning etc then this is probably not a problem for you, I am just raising one of many possibilities).
One thing that may help you understand the agent's learning performance better is instead of plotting the learning episode graph, plot a test graph, perhaps once every ~100 episodes, where you run some number of episodes without learning and with $\epsilon = 0$, and take average of the metrics you are interested in. This will remove some of the randomness from the values you are plotting and give you a much better sense of training progress than your current plot.
With Q learning, you may also get significant benefit by setting a non-zero minimum $\epsilon$, e.g. $\epsilon = \text{max}(\text{eps_decay}(n), 0.01)$ where $\text{eps_decay}(n)$ is your current epsilon decay function for step $n$. That is because the off-policy updates with exploration are still helpful at all stages of learning.


Can we stop training as soon as epsilon is small? I'm new to reinforcement learning.
As it is common in RL, $\epsilon$-greedy search for the behavior/exploration is used. So, at the beginning of the training, $\epsilon$ is high, and therefore a lot of random actions are chosen. With time, $\epsilon$ decreases and we often choose the best action.

I was wondering, e.g. in Q-Learning, if $\epsilon$ is small, e.g. 0.1 or 0.01, do the Q-values really still change? Do they just change their direction, i.e. the best action remains the best action but the Q-values diverge further, or do the values really change again so that the best action always changes for a given state?

If the Q-values really do still change strongly, is it because of the remaining random actions, which we still have at $\epsilon>0$ or would it still change at $\epsilon=0$?

How much the $Q$-values change does not depend on the value of $\epsilon$, rather the value of $\epsilon$ dictates how likely you are to take a random action and thus take an action that could give rise to a large TD error -- that is a large difference between the returns you expected from taking this action as to what you actually observed. How much the $Q$-value changes depends on the magnitude of this TD error.

$Q$-learning is not guaranteed to converge if there is no exploration. Part of the convergence criteria assumes that each state-action pair will be visited infinitely often in an infinite number of episodes, and so if there is no exploration then this will not happen.


How to get top 5 movies recommendations from Auto-Encoder I have trained a model using Auto-encoder on movielens dataset. Below is how i trained the model.

r = model.fit_generator(
  generator(A, mask),
  validation_data=test_generator(A_copy, mask_copy, A_test_copy, mask_test_copy),
  epochs=epochs,
  steps_per_epoch=A.shape[0] // batch_size + 1,
  validation_steps=A_test.shape[0] // batch_size + 1,
)

It is giving good results but now i am confused how should i get the top 5 recommendation on user input.

Just wanted to print the result on console. Can anyone help me please?

That is not what an auto-encoder is doing. An auto-encoder gives you a compressed representation of the input. It is trained by mapping the input data to itself, with the compressed form in between.

To predict recommendations, you need to train your input data on existing user recommendations.


Describing the order of a tensor When describing tensors of higher order I feel like there is an overloading of the term dimension as it may be used to describe the order of the tensor but also the dimensionality of the... "orders"?

Assume one describes the third-order tensor produced by a convolutional layer and wants to refer to its width and height. Do you say spatial dimensions? Would you write about the channel dimension? Or rather the direction? Saying "spatial order" feels really weird. But staying with dimensions makes sentences like "The spatial dimensions are of equal dimensionality." (Disclaimer: Obviously you can avoid the issue here by restructuring, but doing this at every occasion does not feel like a satisfactory solution.).

Ambiguity in Terms

You are correct that there is something like overloading occurring in tensor terminology in posts and in software libraries. Confusing jargon often appears when those without the mathematical background use mathematical terms. You rarely find this confusion when reading NASA, Cambridge, MIT, or Cal-tech materials.

Tensors, Rank, Dimensions, and Channels

A tensor is a grouping of dimensions. The grouping typically represents a relation between quantities describing a system. The order (or rank) of the tensor is the number of dimensions in the grouping.

When this mathematical idea is applied formally to electrical engineering, chemical systems, biological systems, or computing systems, we can say a tensor is the grouping of the inputs and outputs of that system, abstracting the relation between them. The order (or rank) of the tensor is the total number of signal channels going to or from the system. The rank is simply the number of inputs plus the number of outputs.

That original conception was lost a little when the term tensor began to be applied to grouping inputs in one tensor and grouping outputs in another tensor, without any connection with their relationship, which is not formally correct. Those are simply vectors in mathematics, represented by arrays in computer programs.

A labelled data set prepared for machine learning is a discrete tensor formally, however it does not have a mathematical model applied to it yet. When convergence occurs in an artificial network, the result of training is a set of parameters that, if later applied to new inputs, will predict the outputs based on the net and its trained parameters. The configuration of the network cells had become the model and the trained network had become a tensor expression approximating the phenomenon that the training data represents.

The Specific Example in the Question

A third order tensor cannot have only two dimensions, width and height. It must have three dimensions, possibly width, height, and instantaneous value. Width and height are the independent variables, and instantaneous value is the dependent variable. So we have a rank of $1 + 2 = 3$.

There is no clear and formal definition of what dimensionality means, so it would be useful to discontinue its use until academic textbooks contain a consistent definition, but that's unlikely to occur. It will likely continue to be used by non-mathematicians somewhat arbitrarily. Therefore, stating that two tensors are of equal dimensionality remains ambiguous.

Domain and Range

The correct terms are domain and range. These terms unambiguously describe the variability of the independent and dependent variables of a relation respectively. In the case of an array of samples describing a tensor relationship between horizontal position, vertical position, and brightness, the horizontal domain corresponds to the width and the vertical domain corresponds to the height.

Consequently, one would not say, "Width and height are the spacial dimensions," or, "width and height are the channel dimensions."

It could unambiguously be stated, "Width in this article shall refer to the maximum horizontal pixel position minus its minimum plus one." Without saying something that complex, albeit accurate, this would be a clear statement.

  The fourth convolution layer in the network has a domain of 1280, 768 and a range of IEEE 32 bit floats.

It is easily understood and close enough to technically correct to not cause readers with mathematical training to dismiss the writer as uneducated.

The equality question is now solved. The equality of domains could be stated clearly and unambiguously. Whether it sounds unusual is not particularly relevant.

  The horizontal and vertical domains of network layers two and three are equal, both being [1280, 768].

(The reason [1280, 768] is often seen is because compilers of many languages, starting with FORTRAN or maybe even earlier, interpret that as a two dimensional domain for a two dimensional array. So that can be used among software people, although [768, 1280] is more likely used in programs since it is a video tradition to traverse left to right and then top to bottom.)

Misuse of the Term Tensor

It is incorrect to say that adding two arrays is an example of tensors manipulated in software. Tensors are more abstract than arrays. If one were to ...

Make symbolic manipulations to reduce a complex tensor equation to a simple one,
Show that two tensor expressions are equal for given domains, or
Determine the correlation of a set of discrete points to a model represented as a tensor equation,

... then one would be performing tensor mathematics.

There are many pieces of software that perform such symbolic manipulations, but assigning a tensor to an input sample in machine learning is not tensor math. Tensor object classes that are not part of a system of symbolic manipulation are simply an abstraction of the typical programming language's array structure, parameterizing rank in the constructor. Such a trivial abstraction is not nearly as deep as symbolic manipulation of tensor expressions.


What evaluation metric are used for sequence-to-sequence prediction problems? I am solving many sequence-to-sequence prediction problems using RNN/LSTM.

What type of evaluation metrics can be used for sequence prediction problems?

One metric is the mean squared error (MSE) that we can give as a parameter during the training model. Currently, the accuracy of my sequence-to-sequence problems is very low.

What are other ways through which we can compare the performance of our models?

I would recommend taking a look at Bilingual Evaluation Understudy(BELU) score which is commonly used in evaluating machine translation results by sequence to sequence model. Here is the reference https://en.wikipedia.org/wiki/BLEU


How does Continuous Bag of Words ensure that similar words are encoded as similar embeddings? This is related to my earlier question, which I'm trying to break down into parts (this being the first). I'm reading notes on word vectors here. Specifically, I'm referring to section 4.2 on page 7. First, regarding points 1 to 6 - here's my understanding:

If we have a vocabulary $V$, the naive way to represent words in it would be via one-hot-encoding, or in other words, as basis vectors of $R^{|V|}$ - say $e_1, e_2,\ldots,e_{|V|}$. We want to map these to $\mathbb{R}^n$, via some linear transformation such that the images of similar words (more precisely, the images of basis vectors corresponding to similar words) have higher inner products. Assuming the matrix representation of the linear transformation given the standard basis of $\mathbb{R}^{|V|}$ is denoted by $\mathcal{V}$, then the "embedding" of the $i$-th vocab word (i.e. the image of the corresponding basis vector $e_i$ of $V$) is given by $\mathcal{V}e_i$.

Now suppose we have a context "The cat ____ over a", CBoW seeks to find a word that would fit into this context. Let the words "the", "cat", "over", "a" be denoted (in the space $V$) by $x_{i_1},x_{i_2},x_{i_3},x_{i_4}$ respectively. We take the image of their linear combination (in particular, their average):
$$\hat v=\mathcal{V}\bigg(\frac{x_{i_1}+x_{i_2}+x_{i_3}+x_{i_4}}{4}\bigg)$$

We then map $\hat v$ back from $\mathbb{R}^n$ to $\mathbb{R}^{|V|}$ via another linear mapping whose matrix representation is $\mathcal{U}$: $$z=\mathcal{U}\hat v$$

Then we turn this score vector $z$ into softmax probabilities $\hat y=softmax(z)$ and compare it to the basis vector corresponding to the actual word, say $e_c$. For example, $e_c$ could be the basis vector corresponding to "jumped".

Here's my interpretation of what this procedure is trying to do: given a context, we're trying to learn maps $\mathcal{U}$ and $\mathcal{V}$ such that given a context like "the cat ____ over a", the model should give a high score to words like "jumped" or "leaped", etc. Not just that - but "similar" contexts should also give rise to high scores for "jumped", "leaped", etc. For example, given a context "that dog ____ above this" wherein "that", "dog", "above", "this" are represented by $x_{j_1},x_{j_2},x_{j_3},x_{j_4}$, let the image of their average be

$$\hat w=\mathcal{V}\bigg(\frac{x_{j_1}+x_{j_2}+x_{j_3}+x_{j_4}}{4}\bigg)$$

This gets mapped to a score vector $z'=\mathcal{U}\hat w$. Ideally, both score vectors $z$ and $z'$ should have similarly high magnitudes in their components corresponding to similar words "jumped" and "leaped".

Is my above understanding correct? Consider the following quote from the lectures:

  We create two matrices, $\mathcal{V} \in \mathbb{R}^{n\times |V|}$ and $\mathcal{U} \in \mathbb{R}^{|V|\times n}$, where $n$ is an arbitrary size which defines the size of our embedding space. $\mathcal{V}$ is the input word matrix such that the $i$-th column of $\mathcal{V}$ is the $n$-dimensional embedded vector for word $w_i$ when it is an input to this model. We denote this $n\times 1$ vector as $v_i$. Similarly, $\mathcal{U}$ is the output word matrix. The $j$-th row of $\mathcal{U}$ is an $n$-dimensional embedded vector for word $w_j$ when it is an output of the model. We denote this row of $\mathcal{U}$ as $u_j$.

It's not obvious to me why $v_i=\mathcal{V}e_i$ should be the same as or even similar to $u_i$. How does the whole backpropagation procedure above ensure that?

Also, how does the procedure ensure that basis vectors corresponding to similar words $e_i$ and $e_j$ are mapped to vectors in $\mathbb{R}^n$ that have high inner product? (In other words, how is it ensured that if words no. $i_1$ and $i_2$ are similar, then $\langle v_{i_1}, v_{i_2}\rangle$ and $\langle u_{i_1}, u_{i_2}\rangle$ have high values?)

Unlike in skip-gram, the reason similar words have similar embeddings in CBOW is because the words show up in the same contexts of other skipped words.

lets assume two words $e_i$ and $e_j$ pop up in the exact same context of some word $e_k$ with 3 other context words as well. An example would be:

He leaped over the truck
He jumped over the truck

Where the italics represent the words with similar meanings but the bolded words above are the ones being predicted/skipped in CBOW. Lets now show this.

Let the rest of the context be denoted $\{e_r\}_r$ and the skipped word as $e_s$ and so the loss will try to minimize both $-e_s^T log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_i + \sum_re_r)]))$ and $-e_s^T log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_j + \sum_re_r)]))$.

Assuming a long run withlarge enough batch-size (so ignoring catastrophic forgetting) we can essentially say it will be minimizing
$$-e_s^T [log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_i + \sum_re_r)])) +\\ log(softmax(\mathcal{U}\mathcal{V}[\frac{1}{R+1}(e_j + \sum_re_r)]))]$$
Now let $\mathcal{U}\mathcal{V}\frac{1}{R+1}\sum_re_r$ be denoted as $c$, $\mathcal{U}\mathcal{V}\frac{1}{R+1}e_i$ as $\hat u_i$, and $\mathcal{U}\mathcal{V}\frac{1}{R+1}e_j$ as $\hat u_j$. So we have to minimize
$$-e_s^T[log(softmax(\hat u_i+c)) + log(softmax(\hat u_j+c))]$$
or equivalently
$$-e_s^T\ log(softmax(\hat u_i+c) * softmax(\hat u_j+c))$$
As we know in crossentropy, we get our critical point when the inside of the log here would equal $e_s$, which is only possible if both $softmax(\hat u_i+c)$ and $softmax(\hat u_j+c)$ were to be equal to $e_s$. softmax is non-invertible and is invariant under addition only, therefore to achieve this we would need $\hat u_i + c$ to equal $\hat u_j + c + K$ where $K$ is just some arbitrary constant vector ($K=[k,k,k,...]$. Subtracting $c$ and multiplying by $R+1$ we make our model want

$$\begin{align}
u_i &= u_j + K \\
\implies K &= \mathcal{U}\mathcal{V}(e_i -e_j) \\
\end{align}$$

This would mean for all common words, we see this activity that $u_{i-j}$ would be a constant, but this is difficult because that means a $\delta$ must exist such that $\mathcal{U}\delta = k*\vec 1$ and that all similar word pairs indexed by $(a,b)$ would have $v_a \approx v_b + const*\delta$ (because $u_a = u_b + K \implies v_b = v_a + \mathcal{U}^{-1}K$ and we denote $\delta = \mathcal{U}^{-1}K$). This constraint is heavy, tough to learn, and would also be difficult to process on multiple word senses that would appear in the vocabulary. This is because if it were to learn this, it enforces constraints on the images of $\mathcal{U}$ and $\mathcal{V}$ along with creating word vectors with highly different magnitudes making the learning process difficult. This would indicate that this constant would be low in practice. Therefore we would get $v_i \approx v_j$.


Why is it not advisable to have a 100 percent exploration rate? During the learning phase, why don't we have a 100% exploration rate, to allow our agent to fully explore our environment and update the Q values, then during testing we bring in exploitation? Does that make more sense than decaying the exploration rate?

No - imagine if you were playing an Atari game and took completely random actions. Your games would not last very long and you would never get to experience all of the state space because the game would end too soon. This is why you need to combine exploration and exploitation to fully explore the state space.


Why does shifting all the rewards have a different impact on the performance of the agent? I am new to reinforcement learning. For my application, I have found out that if my reward function contains some negative and positive values, my model does not give the optimal solution, but the solution is not bad as it still gives positive reward at the end.
However, if I just shift all readings by subtracting a constant until my reward function is all negative, my model can reach the optimal solution easily.
Why is this happening?
I am using DQN for my application.
I feel that this is also the reason why the gym environment mountaincar-v0 uses $-1$ for each time step and $0.5$ at the goal, but correct me if I am wrong.

You have some freedom to re-define reward schemes, whilst still describing the same goals for an agent. How this works depends to some degree on whether you are dealing with an episodic or continuing problem.
Episodic problems
An episodic problem ends, and once an agent reaches the terminal state, it is guaranteed zero rewards from that point on. The optimal behaviour can therefore depend quite critically on balance between positive and negative rewards.

If an environment contains many unavoidable negative rewards, and these outweigh total positive rewards, then the agent will be motivated to complete an episode sooner.

If an environment contains repeatable positive rewards, and these outweigh total negative rewards, then the agent will be motivated to loop through the postive rewards and not end the episode.

Scaling all rewards by the same positive factor makes no difference to the goals of an agent in an episodic problem. Adding a positive or negative offset to all rewards can make a difference though. It is likely to be most notable when such a change moves rewards from positive to negative or vice versa. In the MountainCar example, adding +2 to all rewards would mean the agent would gain +1 for each time step. As it would stop gaining any reward for reaching the goal, even though reaching that goal would score the highest possible +2.5 reward, the fact that this ends the episode means that it now becomes a poor choice. The best action for the car in this modified MountainCar is to stay at the bottom of the valley collecting the +1 reward per time step forever.
Continuing problems
In a continuing problem, there is no way for the agent to avoid the stream of new reward data. That means any positive scaling of all reward values or positive or negative offset, by the same amount, has no impact on what counts as the optimal policy. The calculated value of any state under the same policy, but with rewards all transformed with the same multiplier and offset, will be different, but the optimal policy in that environment will be the same.
If you scale or offset rewards differently to each other, then that can change the goals of the agent and what the optimal policy is. The balance does not really depend on whether rewards are positive or negative in a continuing environment.
There may be some exceptions to this for continuing problems when using a discount factor, and setting it relatively low (compared to the typical state "cycling" length in the problem). That can cause changes in behaviour due to offsets, similar to those seen in episodic problems. If you use an average reward setting this tends to be less relevant. Often in DQN, you will choose a high discount factor e.g. 0.99 or 0.999, and this will tend to behave close to an average reward setting provided rewards are not very sparse.
In general
In either case, if you change a reward system, and that results in an agent that consistently learns a different policy, that will usually mean one of two things:

The original reward system was incorrect. It described a goal that you did not intend, or had "loopholes" that the agent could exploit to gain more reward in a way that you did not intend.

The implementation of the agent was sensitive in some way to absolute values of total reward. That could be due to a hyperparameter choice in something like a neural network for example, or maybe a bug.

Another possibility, that you may see if you only run a few experiments, is that the agent is not learning 100% consistently, and you are accidentally correlating your changes to reward scheme with the noise/randomness in the results. A DQN-based agent will usually have some variability in how well it solves a problem. After training, DQN is usually only approximately optimal, and by chance some approximations are closer than others.


CNN backpropagation with stride>1 I read that to compute the derivative of the error with respect to the input of a convolution layer is the same to make of a convolution between deltas of the next layer and the weight matrix rotated by $180°$, i.e. something like

$$\delta^l_{ij}=\delta^{l+1}_{ij} * rot180(W^{l+1})f'(x^l_{ij})$$

with $*$ convolution operator; This is valid with $stride=1$; but what happens when stride is greater than $1$? is still a convolution with a kernel rotation or I can't make this simplification?

Backpropagation with stride > 1 involves dilation of the gradient tensor with stride-1 zeroes. I created a blog post that describes this in greater detail.


How can a neural network learn when the derivative of the activation function is 0? Imagine that I have an artificial neural network with a single hidden layer and that I am using ReLU as my activating function.
If by change I initialize my bias and my weights in such a form that:
$$
X * W + B < 0
$$
for every input x in X then the partial derivate of the Loss function with respect to W will always be 0!

In a setup like the above where the derivate is 0 is it true that an NN won´t learn anything?

If true (the NN won´t learn anything) can I also assume that once the gradient reaches the value 0 for a given weight, that weight won´t ever be updated?

In a setup like the above where the derivat[iv]e is 0 is it true that an NN won´t learn anything?

There are a couple of adjustments to gradients that might apply if you do this in a standard framework:

Momentum may cause weights to continue changing if any recent ones were non-zero. This is typically implemented as a rolling mean of recent gradients.
Weight decay (aka L2 weight regularisation) is often implemented as an additional gradient term and may adjust weights down even in the absence of signals from prediction errors.

If either of these extensions to basic gradient descent are active, or anything similar, then it is possible for the neural network to move out of the stationary zone that you have created after a few steps and then continue learning.

Otherwise, then yes it is correct that the neural networks weights would not change at all through gradient descent, and the NN would remain unchanged for any of your input values. Your careful initialisation of biases and weights will have created a system that is unable to learn from the given data. This is a known problem with ReLU activation, and can happen to some percentage of artificial neurons during training with normal start conditions. Other activation functions such as sigmoid have similar problems - although the gradient is never zero in many of these, it can be arbitrarily low, so it is possible for parameters to get into a state where learning is so slow that the NN, whilst technically learning something on each iteration, is effectively stuck. It is not always easy to tell the difference between these unwanted states of a NN and the goal of finding a useful minimum error.


Which objective tests have been developed to test the intelligence of AI? Which objective and measurable tests have been developed to test the intelligence of AI?

The classical test is the Turing Test, which has objective criteria and is measurable since it can be measured what percentage of the jury is fooled by the AI.

I am looking for other, more modern tests.

For there to be an objective test for AI intelligence, there has to be an objective test for human intelligence.  Each of the standard testing organizations claim theirs to be the most objective, but none of the test creators publish rigorous systems theory to verifiably justify their claim.

The user stories for human selections are varied.

I want to find people to work on my team so the project is completed on time and in budget.
I need to admit the right people for our training so we can have success stories to tell.
We need a focus group with people who can communicate well in groups and think about our products and their market.

With artificial intelligence the bar is much lower.

We need to sort grapefruits for canning, fruit stand sale, use as a sweetener, or use as composting matter in a way to maximize profit.
We need to beat the other automated drone pilot companies.
Most of the world has online business but their documents are redundant with many nearly identical documents from copying and pasting, and most of them are poorly organized.  We need an automated librarian that organizes and indexes them.

The questioner may have hoped for some general intelligence test for AI better than Turing's imitation game, the current standardized intelligence testing only works on humans.  The AI that exists can't, without specifically training for the standardized tests they are going to take, achieve anything like a normal human score.  Cognition is something AI hopes to achieve.

Here is some work in that area.

https://slate.com/technology/2017/10/a-i-s-iq-is-still-somewhat-meaningless.html
https://arxiv.org/pdf/1712.06440.pdf


Understanding the notation in the definition of the expected reward I am new to RL and I am trying to work through the book Reinforcement Learning: An Introduction I (Sutton & Barto, 2018). In chapter 3 on Finite Markov Decision Processes, the authors write the expected reward as

$$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\sum_{r\in \mathcal{R}}r\sum_{s'\in \mathcal{S}}p(s',r|s,a)$$

I am not sure if the authors mean

$$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\sum_{r\in \mathcal{R}}\left[r\sum_{s'\in \mathcal{S}}p(s',r|s,a)\right]$$

or

$$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\left[\sum_{r\in \mathcal{R}}r\right]\cdot\left[\sum_{s'\in \mathcal{S}}p(s',r|s,a)\right].$$

If the authors mean the first, is there any reason why it is not written like the following?

$$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\sum_{r\in \mathcal{R}}\sum_{s'\in \mathcal{S}}\left[r\,p(s',r|s,a)\right]$$

Your first option is correct:

$$r(s,a) = \mathbb{E}\left[R_t|S_{t-1}=s,A_{t-1}=a\right]=\sum_{r\in \mathcal{R}}\left[r\sum_{s'\in \mathcal{S}}p(s',r|s,a)\right]$$

It's partly a matter of taste, but I prefer not moving the $r$ into the double sum, because its value does not change in the "inner loop". There is a small amount of intuition to be had that way around, especially when it comes to implementation (it is one multiplication after the sum, as opposed to many within the sum).

There are a lot of sums containing sums in Sutton & Barto, and they mainly follow the convention of not using any parentheses or brackets to show the one sum containing the other explicitly.

In this case, the formulae help link to other treatments of RL, which work with the expected reward functions $r(s,a)$ or $r(s,a,s')$, or reward matrices $R_s^a$, $R_{ss'}^a$ such as the first edition of Sutton & Barto's book. The second edition of the book uses $p(s', r|s, a)$ almost everywhere though, and you won't see $r(s,a)$ mentioned much again. So it's not worth getting too concerned about how it is presented and what the author might be saying with the presentation.

Generally you don't need to know the distribution of reward, just its expectation (and how that depends on $s, a, s'$), in order to derive and explain most of the results in RL. So using $r(s,a)$ and similar functions is fine, in places like the Bellman equations. However, the use of $p(s', r|s, a)$ is general without needing to bring in more functions describing the MDP.


How do I handle negative rewards in policy gradients with the cross-entropy loss function? I am using policy gradients in my reinforcement learning algorithm, and occasionally my environment provides a severe penalty (i.e. negative reward) when a wrong move is made. I'm using a neural network with stochastic gradient descent to learn the policy. To do this, my loss is essentially the cross-entropy loss of the action distribution multiplied by the discounted rewards, where most often the rewards are positive.
But how do I handle negative rewards? Since the loss will occasionally go negative, it will think these actions are very good, and will strengthen the weights in the direction of the penalties. Is this correct, and if so, what can I do about it?

Edit:
In thinking about this a little more, SGD doesn't necessarily directly weaken weights, it only strengthens weights in the direction of the gradient and as a side-effect, weights get diminished for other states outside the gradient, correct? So I can simply set reward=0 when the reward is negative, and those states will be ignored in the gradient update. It still seems unproductive to not account for states that are really bad, and it'd be nice to include them somehow. Unless I'm misunderstanding something fundamental here.

It depends on your loss function, but you probably need to tweak it.

If you are using an update rule like loss = -log(probabilities) * reward, then your loss is high when you unexpectedly got a large reward—the policy will update to make that action more likely to realize that gain.

Conversely, if you get a negative reward with high probability, this will result in negative loss—however, in minimizing this loss, the optimizer will attempt to make this loss "even more negative" by making the log probability more negative (i.e. by making the probability of that action less likely)—so it kind of does what we want.

However, now improbable large negative losses are punished more than the more than likely ones, when we probably want the opposite. Hence, loss = -log(1-probabilities) * reward might be more appropriate when the reward is negative.


Why is the stationary distribution independent of the initial state in the proof of the policy gradient theorem? I was going through the proof of the policy gradient theorem here: https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#svpg

In the section "Proof of Policy Gradient Theorem" in the block of equations just under the sentence "The nice rewriting above allows us to exclude the derivative of Q-value function..." they set
$$
\eta (s) = \sum^\infty_{k=0} \rho^\pi(s_0 \rightarrow s, k)
$$
and
$$
\sum_s \eta (s) = const
$$
Thus, they basically assume, that the stationary distribution is not dependent on the initial state. But how can we justify this? If the MDP is described by a block diagonal transition matrix, in my mind this should not hold.

I think your doubt is completely reasonable. Probably there is an additional assumption that they (both Lilian Weng and Rich Sutton (pag.269)) do not make explicit in the proof and that is that your MDP is not only stationary, but also ergodic. A particular property of those systems is that the probability of eventually reaching a state $s$ from a starting point $s_0$ is 1. In such a case it is clear that $\eta(s)$ exists and is independent of any $s_0$ chosen.

Clearly, an MDP with block-diagonal transition matrix does not satisfy such an assumption since the starting point completely restricts those states you can reach in an infinite time.

What I do not understand is why Rich Sutton does mention ergodicity as a necessary condition in the case of a "continuing task", as opposed to "episodic tasks" (pag.275). For me, their proof requires this condition in both cases.

As an additional note, I also think that Lilian Weng does not really explain why we should buy that from the initial reasonable definition $J(\theta)=\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)$ we should accept the much simpler one $J(\theta)=V^{\pi_\theta}(s_0)$. I guess the only reason is that the gradient of the initial expression does require to know the gradient of $d^{\pi_\theta}(s)$ and so you would be accepting the approximation:

$$\nabla_\theta J(\theta)=\nabla_\theta\left(\sum_\mathcal S d^{\pi_\theta}(s)V^{\pi_\theta}(s)\right)\approx\sum_\mathcal S d^{\pi_\theta}(s)\nabla_\theta V^{\pi_\theta}(s),$$

where the last term is just $\nabla_\theta V^{\pi_\theta}(s_0)$ under the ergodicity assumption.


How much can an inclusion of the number of iterations have on the training of an MLP? My doubt is like this :

Suppose we have an MLP. In an MLP, as per the backprop algorithm (back-propagation algorithm), the correction applied to each weight is :

$$ w_{ij} := -\eta\frac{\partial E}{\partial w_{ij}}$$
($\eta$ = learning rate, $E$ = error in the output, $w_{ij}$ = $i^{\text{th}}$ neuron in the $j^{\text{th}}$ row or layer)

Now, if we put an extra factor in the correction as:

$$ w_{ij} := -k\eta  \frac{\partial E}{\partial w_{ij}}$$ ($k$ denotes the number of iterations at the time of correction)

how much will that factor affect the learning of the network ? Will it affect the convergence of the  network such that it takes time to fit to the data ?

NB : I am only asking this as a doubt. I haven't tried any ML projects recently, so this is not related to anything I am doing.

If anything, you want the learning rate to decrease as the number of iterations increases.
When you're looking for a good spot and you're clueless, take large steps. When you've found a pretty good spot, take small steps, so you don't end up far away.
In other fields of machine learning, there are studies of how the learning rate should scale. For example, in traditional reinforcement learning methods, if $\alpha_i$ is the learning rate at step $i$, then we want to have the following two criteria, to make sure we get convergence to the optimal policy:

$\sum_{i=0}^{\infty} \alpha_i = \infty$. This makes sure that, no matter how bad our initial experience was, we can eventually forget it and replace it with better information.
$\sum_{i=0}^{\infty} \alpha_i^2 < \infty$. This guarantees eventual convergence.

A typical choice here is $\alpha_i = \frac{1}{1+i}$, which fits both criteria.
I am unaware of similar criteria for MLPs, but if you're going to modify the step sizes, I would follow a similar approach. Make the step sizes decrease, but not too fast.


Is the Turing Test a blinded experiment? Did Alan Turing expect the AIs to be aware they were being Turing tested while the game was being played?

I think it's slightly harder to look like a duck while pretending to be a duck than when you believe you are a duck. It is a step further.

Aside from all other criticisms of original article, did Alan Turing have the time and motivation to address the point in any later writing?

First, I think it is important to mention that the Turing Test as is currently accepted is an updated version of Alan Turing's proposed imitation game, so your question is twofold. I don't think Turing makes this distinction that you propose. To Turing the question was "Can machines think?" and he explores this by way of the imitation game.

  The new form of the problem can be described in terms of a game which we call the
  'imitation game." It is played with three people, a man (A), a woman (B), and an
  interrogator (C) who may be of either sex. The interrogator stays in a room apart front the
  other two. The object of the game for the interrogator is to determine which of the other
  two is the man and which is the woman. He knows them by labels X and Y, and at the
  end of the game he says either "X is A and Y is B" or "X is B and Y is A." The
  interrogator is allowed to put questions to A and B

  It is A's object in the game to try and
  cause C to make the wrong identification

  The object of the game for the third player (B) is to help the interrogator.

This is Turing's outline of the imitation game (shortened) between a man and a woman. The only difference between this game and the one we care about is that we replace party A with a machine and the only requirement on B is that they are human.

So yes, in Turing's imitation game the machine is privy to the information that it is not actually human. Whether the machine uses this information is up to the machine.

To talk about your statement on pretending to be a duck versus believing you are a duck lets examine the base imitation game with ducks and frogs. Let's say player A is a frog (either pretending to be a duck or truly believing that it is a duck)  and player B is a duck. Suppose for this example, the frogs and ducks are able to speak English and follow the rules of the game. The interrogator may ask "what is the color of your beak?" The duck will respond yellow, assuming its beak is yellow (I am no bird expert), and then our smart frog pretending to be a duck will look up the color of the beaks of ducks and respond yellow as well.

However, our frog that believes he is a duck will think "I am a duck so to discern the answer I must only look at my beak." And thus, our frog will say "I do not have a beak, but my mouth is green." This will oust the frog.


How can I develop a reinforcement learning agent that plays memory cards game? I am new to RL, and I am thinking of doing a little project. The goal of the project is to learn an agent play the memory game with cards.

I already created the program for detecting the cards on the table (with YOLO) and classifying them what kind of object they are.

I want an agent to be able to play the memory game by itself, without being explicitly told the rules and such.

Any tips on how to get started to make the RL process easier?

The main thing to keep in mind when designing a reinforcement learning agent is that you need to develop an interactive environment in which the agent can learn and define the possible moves the agent can make. In your case, the environment is the memory cards.

Next you need to define how the agent can interact with the environment, that is choosing a card or flipping a card etc. Also how the environment will behave when the agent chooses a move.

Finally you need to define the fitness function, in this case the score (number of pairs created) should be fine. You should have a look at some online RL competitions to get a better understanding of the architecture. AWS DeepRacer


Representing inputs and outputs for a card game neural network I'm attempting to create an AI for a card game using reinforcement learning.  The basics of the game are that you can have (theoretically) up to 35 cards in your hand, you can also have to up to 35 cards 'in play' and so can your opponent.  In normal play you would have ~6 cards in your hand and maybe ~3 each in play.  There are roughly 300 unique cards in total.

How should I represent the game state for the input and how should I represent the action to take in the output?

Assuming there's no ordering to the hand (i.e. it doesn't matter what order cards were added to it), then a reasonable approach is to use one input neuron for the number of each kind of card that is present in a player's hand.

You don't describe how the game is played, but a common approach for extracting actions is to have one output neuron for each possible action. To select an action, you would pick the one corresponding to the neuron with the highest output response to a given input.


Chess policy network I am interested in making a simple chess engine using neural networks. I already have a fairly good value network but I can't figure out how to train a policy network. I know that Leela chess zero outputs the probability of any of the about 1800 possible moves. But how do you train such a network? How do you calculate the loss when you  only have the 1 move that was played in the game
to work with?

It may come as a surprise, after learning all about dynamic programming, temporal difference learning, SARSA/Q-learning, to then discover that there is yet another whole dimension to reinforcement learning (on top of choices for on-policy/off-policy, model-based/model-free, bootstrap/monte carlo etc). That is value-based vs policy-based methods. Policy-based methods are often taught after value-based methods, because they are more complex.

You can learn the parameters of a policy function by training it using a policy gradient method. The archetypical policy gradient method is REINFORCE, although that is not very efficient. You may have heard of policy gradient methods developed recently: A3C, A2C, DDPG, TRPO, PPO . . . there are a few.

  How do you calculate the loss when you only have the 1 move that was played in the game to work with?

You can pre-train a policy network using supervised learning (perhaps using the moves of winning players in high quality games) - that would use multi-class cross-entropy loss that you may be familiar with from supervised classification problems.

Policy Gradient methods work with a reward summation function defined as expected reward given the distribution of states. If your network parameters are $\theta$, then that may look like this:

$$J(\theta) = \sum_{s \in \mathcal{S}} \rho_{\pi}(s) \sum_{a \in \mathcal{A}} \pi(a|s,\theta)q_{\pi}(s,a)$$

where $\rho_{\pi}(s)$ is the expected proportion of time steps spent in state $s$. There is a way to take a sample gradient of this that can be used for gradient ascent - the derivation is called the Policy Gradient Theorem. It's a bit long to include in this answer, but the upshot is that you can use your sampled single step to generate an approximate gradient towards improving the policy. There are a few variations, but for instance advantage actor critic uses this:

$$\nabla J(\theta) = \hat{A}(s,a)\nabla\text{log}(\pi(a|s,\theta))$$

where $\hat{A}(s,a)$ is your current estimate of the advantage (or $Q(s,a) - V(s)$) for taking a specific action in state s.

The related loss function is

$$\mathcal{L}(\theta) = -A(s,a)\text{log}(\pi(a|s,\theta))$$

The $\text{log}$ function looks like an odd addition, but is just a consequence of adjusting $\nabla J$ to take account of ratios in which actions are taken in the current policy. In fact $\nabla\text{log}(\pi(a|s,\theta)) = \frac{\nabla\pi(a|s,\theta)}{\pi(a|s,\theta)}$ and it may help your intuition to keep it in that form (the $\text{log}$ form is concise and used elsewhere in statistics as the "score function", but it is not necessary for anything specific in RL).

The variations in policy gradients may use other functions than the advantage function, and it is not clear that there is any "best" one. The policy gradient theory basically gives us ways of estimating relative benefits of actions, and allows for any offset to estimated return from $(s,a)$ that does not further depend on the choice of action $a$. So you can use any method for getting an estimated return, and offset it with anything that you think might normalise the updates - common choices for the latter include subtracting average reward, or subtracting the state value function.


If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal? If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?

UCS is optimal (but not necessarily complete)
Let's first recall that the uniform-cost search (UCS) is optimal (i.e. if it finds a solution, which is not guaranteed unless the costs on the edges are big enough, that solution is optimal) and it expands nodes with the smallest value of the evaluation function $f(n) = g(n)$, where $g(n)$ is the length/cost of the path from the goal/start node to $n$.
Is bidirectional search with UCS optimal?
The problem of bidirectional search with UCS for the forward and backward searches is that UCS does not proceed layer-by-layer (as breadth-first search does, which ensures that when the forward and backward searches meet, the optimal path has been found, assuming they both expand one level at each iteration), so the forward search may explore one part of the search space while the backward search may explore a different part, and it could happen (although I don't have the proof: I need to think about it a little bit more!), that these searches do not meet. So, I will consider both cases:

when the forward and backward searches do not "meet" (the worst case, in terms of time and space complexity)

when they meet (the non-degenerate case)

Degenerate case
Let's consider the case when the forward search does not meet the backward search (the worst/degenarate case).
If we assume that the costs on the edges are big enough and the start node $s$ is reachable from $g$ (or vice-versa), then bidirectional search eventually degenerates to two independent uniform-cost searches, which are optimal, which makes BS optimal too.
Non-generate case
Let's consider the case when the forward search meets the backward search.
To ensure optimality, we cannot just stop searching when we take off both the frontiers the same $n$. To see why, consider this example. We take off the first frontier node $n_1$ with cost $N$, then we take off the same frontier node $n_2$ with cost $N+10$. Meanwhile, we take off the other frontier node $n_2$ with cost $K$ and the node $n_1$ with cost $K + 1$. So, we have two paths: one with cost $N+(K + 1)$ and one with cost $(N+10)+K$, which is bigger than $N+(K + 1)$, but we took off both frontiers $n_2$ first.
See the other answer for more details and resources that could be helpful to understand the appropriate stopping condition for the BS.


In unsupervised learning, what is meant by "finding the probability of an image"? The specific problem I'm having is with a Fully Visible Belief Network. It is an explicit density model (though I don't know what quantifies something being such) that uses the chain rule to decompose the likelihood of an image x into a product of 1-d distributions.

What is meant by "the likelihood of an image x"? With respect to what? I assume it refers to how common this image would be in the data set it is selected from? Like if you had 1000 images, 800 of which were white and 200 of which were black, the model should ideally output 0.2 for any black image inputted? Obliviously with more complicated clustering like dogs vs cats it'd be a bit different, but that's my intuition. Is that correct?

Also as a side question, that equation looks very wrong. If you have an image of $1048\times720$ pixels, and say every pixel evaluates to have a probability of 0.9, you'd expect the final probability of the image to be 0.9 or 90%. But according to that equation, it's $0.9^{720*1048}$, which is stupidly small, essentially 0. What's going on here?

When you say likelihood, you are invoking several other concepts like events, sample, parameters, model, probability density function (PDF), etc (it would be helpful if you learn more about these concepts). In essence, a likelihood function $l(x|\theta)$ is a PDF that quantifies how likely is that event $x$ happens out of a set of possible events, given the parameters $\theta$ that define your model.

In the specific case of images, the set of possible events is usually one of two options: 1) all the available images in a dataset, or 2) all the existing images. Usually you want to model the likelihood in the option 2), but only having access to a sample of all the possible images. In either case, the likelihood is just the probability that you select one image out of all the possible ones. If you consider only images of $1048\times 720$ pixels, the possible amount of images is $(256\times3)^{1048\times 720}$, where I am assuming that each pixel consists of 3 colors and each color can take 256 values. Since the amount of possible images is so so big, it is very common that the probability of selecting a specific one is very very small. This is a reason why you usually work with log-likelihood (the logarithm of the likelihood) instead of directly using likelihoods. For example, if all your images were equally probable, the likelihood would be in the order of $10^{-{10^7}}$, while the log-likelihood would be around $-10^7$.

To solve your paradox with the probability of images and pixels, consider that instead of pixels you have coins and instead of images you have sequences of coins. Let's say that you have a fair coin, so the probability of tails ($T$) after tossing the coin is 0.5. If you toss a second coin, the probability of having $T$ again is naturally 0.5 as well, but what is the probability that both results where $T$? It is the product (0.25) since the events are independent. Similarly, the probability of the other three sequences $TH$, $HT$ and $HH$ is just 0.25. You can see that since the probability needs to be shared between 4 sequences equally probable, they are less probable with respect to the probabilities of the sequences of length 1. If you toss the coin 3 times, then the probability of all these coins being tails is just $0.5^{3}$. Again, there are now 8 possible sequences, all sharing the same amount of probability. You can see what's going on. Since the amount of possible options becomes large, the probability of each possible sequence of coins becomes small. Clearly, you would never toss a coin 10 times and expect to obtain all $T$, right? Well, exactly the same happens in the case of the pictures.


What are modern state-of-the-art solutions in prediction of time-series? I wanted to ask you about the newest achievements in time series analysis (mostly prediction).
What state-of-the-art solutions (as in frameworks, papers, related projects) do you know that can be used for analysing and predicting time series?

I am interested in something possibly better than just RNN, LSTM and GRU :)

An interesting model I encountered in a course is Facebook Prophet. Prophet takes into account trends, seasonality, and holidays for its predictions. As you can probably guess, this is a model that fits Facebook's needs very well. I'll give a brief introduction then provide a link where you can read more. Prophet fits a couple of functions of time represented by a few terms. The general form of the timeseries predictions are,

$$y(t)=g(t)+s(t)+h(t)+\epsilon_t$$

$g(t)$ deals with the trends I mentioned above. This is exactly what you would think it is, and accounts for non-periodic features of the data. It takes the form of a piecewise linear or logistic function.

$s(t)$ accounts for seasonality - in other words these are periodic changes in our timeseries (maybe an increase of sunscreen purchases in the summer). As this is periodic, the natural way to model this term is with Fourier decomposition to identify important frequencies in the signal.

$h(t)$ deals with predictable changes in the timeseries but is for events like holidays (this can happen at different times year to year so this is not necessarily periodic, think Easter). The user provides a list of events and how they want to account for it.

$\epsilon_t$ is just an error term to deal with anything that cannot be addressed with the rest of the model.

This page has a great explanation if you want more detail. I highly recommend you check it out because it is very cool!


What is the equation of the separation line for this neuron with identity activation? I have a single neuron with 2 inputs, and identity activation, where f is activation function and u is output:

$u = f(w_1x_1 + w_2x_2 + b) = w_1x_1 + w_2x_2 + b$

My guessing for the separation line equation:

$u = w_1x_1 + w_2x_2 + b$
$\implies x_2 = \dfrac{u - w_1x_1 - b}{w_2}$
$\implies x_2 = (\dfrac{-w_1}{w_2})x_1 + \dfrac{u-b}{w_2}$

And the questions are:

1) Is the separation line equation above correct?

2) And when f is not identity function, is the separation line equation still the same? or different?

I found the answer, the output u is not related to plotting x2 against x1 here, coz u is like z axis and seeing the separation line is looking perpendicularly to the x1x2 plane, and whatever u value is, it's just a dot.

Put u as zero for the solving steps in the question.

So the separation line equation is this (with any activation function):

$x_2 = \dfrac{-w_1}{w_2}x_1 + \dfrac{-b}{w_2}$


How to recover the target Q network's weights solely from the snapshots of the primary Q network's weights in DQN? Suppose that I have a DQN agent, which has two neural networks: one is the primary Q network and the other is the target Q network. In every update, the target Q network is updated with a soft update strategy:
$$Q_{target} = (1-\tau) \times Q_{target} + \tau \times Q_{prime}$$
I saved the primary Q network's weights every $n$ episodes (say $n=10$), but, unfortunately, I did not save the target Q network's weights.
Say that my training process is aborted for some reason, and now I would like to continue the training using the latest saved weights. I can load the primary Q network's weights, but what about the target Q network's weights? Should I also use the latest primary Q network's weights for the target Q network's weights, or should I use the primary Q network's weights from several episodes ago, or how should it be?

Let's add a step index to your expression
$$Q_{target}^{n} = (1-\tau)Q^{n-1}_{target} + \tau\, Q^{n-1}_{primary}$$
We can expand it one step further
$$Q_{target}^{n} = (1-\tau)^2Q^{n-2}_{target} + (1-\tau)\tau\, Q^{n-2}_{primary} + \tau\, Q^{n-1}_{primary}$$
And further
$$Q_{target}^{n} = (1-\tau)^3Q^{n-3}_{target} + (1-\tau)^2\tau\, Q^{n-3}_{primary} + (1-\tau)\tau\, Q^{n-2}_{primary} + \tau\, Q^{n-1}_{primary}$$
So, I guess, we can write a general formula for $m$ steps behind like:
$$Q_{target}^{n} = (1-\tau)^{n-m}Q^{n-m}_{target} + \tau\,\sum_{i=0}^{m-1} (1-\tau)^i Q^{n-i-1}_{primary} $$
For $n-m$ large enough $(1-\tau)^{n-m}$ should be close to 0 and you should be able to approximately reconstruct your $Q_{target}^n$ using only the history of $Q_{primary}$es
Edit: I've missed that you only have snapshots with some step between them. This is not ideal, but a possible way out would be to use, say, a linear interpolation between snapshot points.


Why is second-order backpropagation useful? Raul Rojas's book on Neural Networks dedicates section 8.4.3 to explaining how to do second-order backpropagation, that is, computing the Hessian of the error function with respect to two weights at a time.
What problems are easier to solve using this approach rather than first-order backpropagation?

Second-order optimization algorithms like Hessian optimization have more information on the curvature of the loss function, so converge much, much faster than first-order optimization algorithms like gradient descent. I remember reading somewhere that if you have $n$ weights in the neural network, one iteration of a second-order optimization algorithm will reduce the loss function at approximately the same rate as $n$ iterations of a standard first-order optimization algorithm. However, with recent advancements to gradient descent (momentum, adaptive rates, etc), the difference isn't as large anymore -- @EmmanuelMess pointed out a paper that states:

The performance of the proposed first order and second order methods with adaptive gain (BP-AG, CGFR-AG, BFGS-AG) with standard second order methods without gain (BP, CGFR, BFGS) in terms of speed of convergence evaluated in the number of epochs and CPU time. Based on some simulation results, it’s showed that the proposed algorithm had shown improvements in the convergence rate with 40% faster than other standard algorithms without losing their accuracy.

Here is a great post explaining the background behind the math of why this is the case.
Also, second-order gradients can help the optimizer identify states like saddle points, and help the solver get out of those states. Saddle points give standard gradient descent a lot of issues, as the gradient descent has difficulty and is slow to move out of the saddle point. Fixing the saddle point issue is one of the motivations for improving gradient descent over the last two decades (SDG with momentum, adaptive learning rates, ADAM, etc). More info.

The issue though is that to compute the second-order derivative requires a matrix $n^2$ in size, as opposed to gradient descent which requires a matrix $n$ in size. The memory and computation become intractable for large networks, especially if you have millions of weights.
Some approaches exist which efficiently approximates the second-order optimizations, solving the tractability problem. A popular one is L-BFGS. I haven't played around with it much, but I believe L-BFGS is not as popular as gradient descent algorithms (such as SGD-M, ADAM) because it is still very memory demanding (requires storing about 20-100 previous gradient evaluations), and cannot work in a stochastic context (you cannot sample mini-batches to train on; you must train the entire dataset in one pass per iteration). If those two are not an issue for you, then L-BFGS works pretty well I believe.


How can I use deep neural networks to recognize characters on vehicle license plate? I was able to extract the license plate from a given car image, using Matlab. I would like to use deep neural networks to recognize the characters on the plate now. How can i proceed further? I don't have any experience with deep neural networks implementation.

Before jumping into any machine learning task it is good to consider your dataset and the features you wish to use. License plates are unique thus feeding the entire plate into a machine learning algorithm would not yield very accurate results. First, you will want to make sure that the extracted license plate images are similar in size. Then you will want to separate the license plate such that you can separate the different digits and letters into their own respective images. Thus your dataset that will be used to train your network will consists of many single character images which contain either a letter or a digit. When you have finished training your model, future license plates will also have to be broken down in this way, classified and then the outputs be combined to get the license plate number.

What is a neural network?

A neural network (NN) is a series of nodes which contain a simple, continuous, differentiable function such as logistic regression. Alone these nodes are not very powerful, however, the beauty comes in when they are connected in networks. The tuning of such a network can learn highly complex functions. Typically, a NN is set up with three layers. The input layer, where you will feed in your features, the hidden layer and the output layer. Naturally, if you want a deep NN then you just need to add more hidden layers. But, there is a trap. The deeper your network is the harder it will be to train, thus you will need MORE data.

The input-layer

This is where you will be feeding in your images. If you have a 16*16 pixel image then you will have 256 input nodes. This layer typically does not perform any function on the input, it is simply taking in the input. It will then feed the input to the hidden layer. You can use some dimensionality reduction techniques to try and eliminate some useless information from your dataset such as the white spaces in the corner of the image. The less input nodes you have, the more informative your samples become, thus with higher information entropy your network will be able to learn faster, or more rigidly with the same amount of data.

The hidden layers

You are free here to choose how many layers you want and how many nodes you want in each layer. I suggest using grid search and cross-validation as a means to determine which configuration is ideal for your dataset. Too many layers and nodes and you will not end up with a fully trained networks once you run out of training data (too much bias). Too little nodes, your network will not be able to learn the subtleties which are embedded within the data (too much variance). You want to find yourself at the crossroad where these two are minimized. Choose wisely.

The output layer

This layer can be configured in a few different ways. Typically people like to do one output node for each class. In your case there are 26 letters in the alphabet and 10 digits. This gives 36 possible output classes. So you will need 36 nodes in your output layer.

How do I train this?

The training of the NN is by tuning the weights that will be applied to the inputs of each of your nodes. Try to draw your dense network, for each line connecting nodes you will have a weight. I am sure you can see how this becomes quite huge. You will initialize your weights randomly to start. Then you will take each of your examples and pass them through your network. This is called a feed-forward pass through. This will provide you with an output. You will compare your output with your ground truth value using a cost function. This is often the root mean squared error (RMSE) but there are many other options. Then using the derivative you will back-propagate the error through your network to see which weights caused the error and to what extent. The derivative will then allow you to update those weights proportionately.

WOW do I need to program all that?

Nope not anymore!!! You can use Keras in python (my recommendation) or other similar frameworks which have made it a real tea sipping pleasure to program a variety of NN configurations.

My recommendation

I would start with a simple NN and see what kind of accuracy I can achieve. From there I would try to use convolutional neural networks which have been shown to garner much better results on datasets comprised of images. These can also be implemented in Keras. CNN require more data than typical NN thus you might need to get access to more images.

It is always best to train your dataset only on images you have in your original data. However, when it comes to images, adding to your data by artificially shifting images by 1-5 pixels or rotating by 1-5 degrees can add variability which can supplement your original data.

Make sure that the license plate pictures you are using to train your network are taken with a similar system as the images you will be using in the future. You will not get very good results if you train your network on images taken directly behind cars and then you expect to implement your solution in traffic cameras monitoring traffic from above.