How is the convolution layer is usually implemented in practice? Following an earlier question, I'm interested in understanding the basics of Conv2d and especially how the kernel is applied, summed, and the propagated.
I understand that:

a kernel has size W x H and that more than one kernel is applied (e.g., S x W x H) where S is the amount of kernels.
A stride or step is used when iterating the network input
Padding may or may not be used by being added to the network input.

What I would ideally like to see is either a description, or a python sample (pytorch or tensorflow) of how that is done, what the dimensionality of the output is, and any operation I may be missing (some YouTube videos say that the kernel is summarised and then divided to hold one new unique value representing the feature activation?)

I don't think that to understand convolution you need to dig into the nested code of huge libraries, since the code becomes quickly really hard to understand and convoluted (ba dum tsss!). Joking apart, in PyTorch Conv2d is a layer that applies another low level function, conv2d, written in c++.

Luckily enough, the guys from PyTorch wrote the general idea of how convolution is implemented in the documentation:

From this paragraph, we already have some important information like the input and output dimensions. The number of channels should be easy to understand, if we have an RGB image, for example, the channels are 3, one for each color, so they are just different matrices representing different features.

The next important element is the reference to the cross correlation, the function applied to our input images through the kernel k. Why cross-correlation? Because it is almost identical to a convolution, as you can see comparing their formulas:

The only difference consists in the way the indexing of the width is implemented, which causes the operation to start from the bottom right of the input matrix for the convolution and from the top left of the input image from the cross-correlation (the circles in the squares in the previous pic). Since, in most programming languages, matrix indexing starts from top left, cross-correlation is the most common choice to implement.

But how do these formulas work in practice? Here's another picture taken from Chapter 9 of Deep Learning (Goodfellow, Bengio, Courville), which I strongly suggest you to read.

Basically, from the input matrix, a submatrix is extracted, with the same dimension of the kernel, then the sub-matrix and the kernel are multiplied elementwise and all the resulting product summed together to produce a single output element that will form a 'pixel' of the resulting feature map (the output matrix).

Here's another example with fake numbers that I made. I hope the double notation for filter/kernel doesn't generate confusion, I actually found that sometimes it is inconsistent (in the chapter I linked they don't even use the filter at all). In practice they actually mean the same thing, I usually call kernel the actual matrix that is multiplied to the input and with filter I refer to the sliding window on the input image (that has, of course, must have the same dimension of the kernel).

Lastly, when you apply padding, the filter can actually move also outside the 'edges' of the input matrix, in which case all the elements outside would be considered to be zero. The computation is exactly the same, but since there are more splitting steps, the output matrix will have bigger dimension.

Please note that with multiple input channels you can perform either 2d convolution or 3d convolution, the difference relies in the filter dimension, in case of 2d convolution it would be a square whereas in 3d convolution it would be a cube. This means that for an RGB image a 2d convolution would treat each color layer independently, mixing the information from each channel with further computations like pooling (averaging the resulting feature maps of each color or select the max value among the feature maps for each pixel, etc..) while 3d convolution would mix together the color layers already during convolution thanks to the 3d kernel which will sum together elements from different layers.


Can variations in microphones used in training set and test set impact the accuracy of speech recognition models? If I train a speech recognition model using data collected from N different microphones, but deploy it on an unseen (test) microphone - does it impact the accuracy of the model?

While I understand that theoretically an accuracy loss is likely, does anyone have any practical experience with this problem?

Yes it can. However, other differences between training and test data with audio could have greater effect:

Identity of the speaker (including effects from gender, age, physical build, local accent, amongst others)
Acoustics of the recording environment (including proximity to the microphone, size of space, presence of hard surfaces, background noise)

If any of these may vary from your training data, then it becomes harder to predict your generalised accuracy during training and early model selection.

One possibility is to ensure your cross-validation set (which you absolutely should have) also separates data out by things that will vary from training to test. So instead of random train/cv split, you split by data that is key for generalisation. This is sometimes called a stratified train/test split.

If your only concern is variation in microphone, then split your train/cv sets by microphone type. You will get a better assessment early on in the model selection process how well the training is generalising, and can focus your search on models that do well despite this expected difference.


What is meant by the number of channels of a network? Currently, I am reading Rethinking Model Scaling for Convolutional Neural Networks. The authors are talking about a different way of scaling convolutional neural networks by scaling all dimensions simultaneously and relative to each dimension. I understand the scaling methods regarding the depth of a network (# layers) and the resolution (size of the input image).
What I was stumbling is the concept of the network's width (# channels). What is meant by the width or the number of channels of a network? I don't think it is the number of color channels, or is this the case? The number of color channels was the only link I found regarding the terms "ConvNets" and "number of channels".

It is exactly that - the number of color channels or any other analogue to color that you use.


What is the difference between machine learning and quantum machine learning? What is the difference between machine learning and quantum machine learning?

The difference is much simpler than you might have anticipated: In the quantum computing community, machine learning algorithms designed to be used on quantum computers as opposed to classical computers, would fall under "quantum machine learning". There's really nothing more to it!
There is a short paper published in Nature called "Quantum Machine Learning" which was mentioned before, and it might give you all the answers you need about what "Quantum Machine Learning" is.


How can I fix jerky movement in a continuous action space I am training an agent to do object avoidance. The agent has control over its steering angle and its speed. The steering angle and speed are normalized in a $[−1,1]$ range, where the sign encodes direction (i.e. a speed of −1 means that it is going backwards at the maximum units/second).
My reward function penalises the agent for colliding with an obstacle and rewards it for moving away from its starting position. At a time $t$, the reward, $R_t$, is defined as
$$
R_t=
\begin{cases}
r_{\text{collision}},&\text{if collides,}\\
\lambda^d\left(\|\mathbf{p}^{x,y}_t-\mathbf{p}_0^{x,y}\|_2-\|\mathbf{p}_{t-1}^{x,y}-\mathbf{p}_0^{x,y}\|_2 \right),&\text{otherwise,}
\end{cases}
$$
where $\lambda_d$ is a scaling factor and $\mathbf{p}_t$ gives the pose of the agent at a time $t$. The idea being that we should reward the agent for moving away from the inital position (and in a sense 'exploring' the map—I'm not sure if this is a good way of incentivizing exploration but I digress).
My environment is an unknown two-dimensional map that contains circular obstacles (with varying radii). And the agent is equipped with a sensor that measures the distance to nearby obstacles (similar to a 2D LiDAR sensor). The figure below shows the environment along with the agent.

Since I'm trying to model a car, I want the agent to be able to go forward and reverse; however, when training, the agent's movement is very jerky. It quickly switches between going forward (positive speed) and reversing (negative speed). This is what I'm talking about.
One idea I had was to penalise the agent when it reverses. While that did significantly reduce the jittery behaviour, it also caused the agent to collide into obstacles on purpose. In fact, over time, the average episode length decreased. I think this is the agent's response to the reverse penalties. Negative rewards incentivize the agent to reach a terminal point as fast as possible. In our case, the only terminal point is obstacle collision.
So then I tried rewarding the agent for going forward instead of penalising it for reversing, but that did not seem to do much. Evidently, I don't think trying to correct the jerky behaviour directly through rewards is the proper approach. But I'm also not sure how I can do it any other way. Maybe I just need to rethink what my reward signal wants the agent to achieve?
How can I rework the reward function to have the agent move around the map, covering as much distance as possible, while also maintaining smooth movement?

I think you should try to reason in terms of total "area" explored by the agent rather than "how far" it moves from the initial point, and also you should add some reward terms to push the agent steering more often. I think that the problem with your setting is more or less this: The agent go as straight as it can because you're rewarding it for it, it start sensing an obstacle so it stops, there is no reward for steering so the best strategy to go away from the obstacle and not end the episode is just to go backwards.
Considering that you have information about the grid points at any time you could rewrite the reward function in terms of grid squared explored by checking at each move if the agent end up in a new square grid:
$$
R_t=
\begin{cases}
r_{\text{collision}}\\
\lambda^d\left(\|\mathbf{p}^{x,y}_t-\mathbf{p}_0^{x,y}\|_2-\|\mathbf{p}_{t-1}^{x,y}-\mathbf{p}_0^{x,y}\|_2 \right) + r_{new-squared-explored}
\end{cases}
$$
Moreover it would be useful to add some reward terms also related to how the agent avoid the obstacle, for example a penalisation when the sensor goes and remain under a certain threshold (to make the agent learn to not go and stay too close to an obstacle) but also a rewarding term when an obstacle is detected and the agent manage to maintain a certain distance from it (even though if not well tuned this term could lead the agent to learn to just run in circles around a single obstacle, but if tuned properly I think it might help to make the agent movements smoother).


Extracting algebraic constraints from the input data I would appreciate your help with this (naive) question of mine.

Given the set of points located on a circle, $x_{i}, y_{i}$ as the input data, Can a deep/machine learning algorithm infer that radius of the circle is constant ? In other words, given the data $x_{i}, y_{i}$ is there way that algorithm discovers the constraint: $x_{i}^2 + y_{i}^2 = \text{constant}$ ?

I would also appreciate any related reference on the subject.

I'm assuming the question intends to find the maximally constraining bounding relation from among a large variety of other possible relations.

The bounding relation is likely linked to the chaos idea of attractors$^1$. Some contemporary visualizations of attractors in phase space are visualized as bounds rather than translucent paths or cross-sectional means.

The simple form used as an example, the circle, never actually exist in nature. It is an approximation of a differential equation for an orbit with a eccentricity of zero in three space projected onto a parallel plane. But even if this problem is restricted to $\mathbb{R}^2$, the concepts of attractors may pertain.

If quadratic or cubic approximation is adequate for your purposes then it is a matter of finding the zero terms in the generalization. To find non-polynomial relations, the differential equations are the first things to find, but there may be no equivalent closed form in algebra

[1] http://ijfritz.byethost4.com/Chaos/ch_close.htm?i=1


What is the difference between Inductive Learning and Connectionist Learning? According to what we know about inductive and connectionist learning, what is the difference between them ?

For those who do not know about :

Inductive Learning, like what we have in decision tree and make a decision based on amount of samples

Connectionist Learning, like what we have in artificial neural network

All of the statistical learning is about inductive learning.

What is the difference between inductive learning and connectionist learning?

Inductive learning is about identifying patterns from examples. It is more related to statistics. Connectionist learning is more about finding a common pattern and predicting as well as self-learning(learning from the experience of prediction).

Connectionist learning is where learning occurs by modifying connection strengths based on experience. This is not the case with inductive learning. In inductive learning, we are not modifying things based on experience. Inductive learning just finds common patterns, not self-learning based on experience.

  Learning requires both practice and rewards

In inductive learning, we learn the model from raw data (so-called training set), and in the deductive learning, the model is applied to predict the behaviour of new data.

  Connectionist Learning is a group of inductive learning and deductive learning.


Which nodes are expanded in the expansion phase of MCTS? I'm confused regarding a specific detail of MCTS.

To illustrate my question, let's take the simple example of tic-tac-toe.
After the selection phase, when a leaf node is reached, the tree is expanded in the so-called expansion phase. Let's say a particular leaf node has 6 children. Would the expansion phase expand all the children and run the simulation on them? Or would the expansion phase only pick a single child at random and run simulation, and only expand the other children if the selection policy arrives at them at some later point?

Alternatively, if both of these are accepted variants, what are the pros/cons of each one?

By far the most common (and likely also the most simple / straightforward) implementation is to expand exactly one node in the Expansion Phase; specifically, the node corresponding to the very first state selected (semi-)randomly by the Play-Out Phase. This is also pretty much the bare minimum you have to do if you want any form of tree growing at all (which you do).

Other variants are possible too, but are much less common. The variant you suggest in the question is to expand all the children of the final node encountered during the Selection Phase, and run a Play-Out for all of them. I am not familiar with any literature on such a strategy really, never tried that myself. Intuitively, I would expect it to perform very similarly, perhaps slightly worse. Essentially what this would do is that it moves the "behaviour" of the search algorithm slightly more towards Breadth-First Search behaviour, rather than Best-First search behaviour. You spend a bit less of your computation time in the Selection Phase, because every Selection Phase is followed up by for example 6 (or whatever branching factor you have) Play-Outs instead of just a single one. On average I'd expect this to be slightly worse, because the Selection Phase is the primary source of the "Best-First Search" behaviour of the algorithm. I certainly don't expect a change like this to cause a large difference in performance though, if any. It will also likely be domain-dependent; worse in some cases, better in other cases.

A different variant that I did once use myself is to expand every node in the complete line of play followed by the Play-Out phase. You can visualize this as a very "thin", but "deep" expansion, whereas your suggestion discussed above would be visualized as a "shallow" but "wide" expansion (and the conventional expansion strategy of a single node would be "thin" and "shallow").

For this strategy, it is much easier to clearly define the advantages and disadvantages that it has in comparison to the standard strategy. The main advantage is that you retain more information from your Play-Outs, you throw less information away. This is because the Backpropagation phase, after the Play-Out terminates, can only store information in nodes that exist. If you immediately expand the complete line of play followed in the Play-Out Phase, you can store the result (the evaluation in the terminal state) in all of those nodes. If you don't expand the complete Play-Out (e.g. only expand the very first node), you'll have to "skip" all of those nodes which you didn't expand yet (they don't exist), and you can't store results in there yet.

The main disadvantage of this approach is that it requires more memory, the tree grows a lot more quickly.

I would personally recommend this approach if you have very strict limitations on computation time, if you expect to be able to only run very few iterations of the MCTS algorithm. For example, I personally used this in my General Video Game AI agent; this is a real-time game where you have to make decisions every ~40 milliseconds. In such a low amount of time, you cannot run many MCTS simulations. This means that:

You do not expect to run out of memory, even if you grow your tree very quickly, so the increased memory requirements become a non-issue.
Due to the low expected number of iterations, it is extremely important to retain as much information as possible, not throw any information away. If we can't run many simulations, we want to make sure to squeeze every little bit of information we can out of each of them.

For contrast, if you're developing an agent to play a board game, and it has in the order of multiple minutes of thinking time per turn, the standard approach of only expanding a single node per Expansion Phase becomes a lot more appealing. If you're capable of running tens of thousands of iterations or more, it really doesn't hurt if you "forget" about a little bit of information deep down in the tree. The risk of running out of memory also becomes a lot more serious if you're running many iterations, so you don't want to grow the tree too quickly.


Can we create a conscious agent by having two units: one rational and the other conscious? Suppose we create two units (or programs) that run in parallel and we label them as a cognitive unit and the conscious cognitive unit.

A human has two units analogously. A rational analyzer and not so rational analyzer. (Is there any third thing?)

In my opinion, consciousness is an extra layer of decision making. This resembles the way metaheuristics work. We have a set of rules for decision making and we analyze them and tune those rules dynamically.

Global search algorithms mimic conscious behavior whereas the local search algorithms work as a rational mind.

So, is it possible to create a conscious agent by having two units as I described above?

Jürgen Schmidthuber has a similar concept of consciousness, maybe check out this article:

  I would like to claim we had little, rudimentary, conscious learning systems for at least 25 years. Back then, already, I proposed rather general learning systems consisting of two modules.

There you also have one module that is occupied with decision making. The other module's job is to create a model of the world.

Of course, a philosopher will tell you that we have no idea what consciousness is or "what it feels like to be ai with two units".


Difference between Neural Compute Stick 2 and Google Coral USB for edge computing I am trying understand machine learning inferece, and i would like to know what exactly is the difference between Google Coral USB and Movidius Intel Neural Compute Stick 2. From what i could gather the google coral USB speeds up the frame rate, but that doesn't look clear to me. My questions are:
What exactly is the benefit from both of them in units? Like, is it frame rate? prediction speed? Are both visual processing units? And lastly, do i need to keep my neural network in a single computer board for training or can i have it at a cloud?

I do not know much about the Neural Compute Stick but I can tell you a little bit about the Coral Edge TPU, since I used it myself (which I think also applies to the Neural Compute Stick).
The Edgte TPU is a specialized ASIC which is very efficient at the main calculations (convolutions, relu etc.) for neural network inferencing. That means it cannot be used for training* a neural network but for deploying a neural network in production after it has been trained and optimized/quantized (precision reduced from float32 to int8). But I think you already new that, as it seems from your question.
Now to your actual question in terms of speed: You cannot really compare speed of such chip in terms of framerate alone, nor can you call it a visual processing unit or not. The google coral is a general ASIC that is very fast at doing convolutions/relus etc. For what you gonna use your neural network (like Image recognition, or maybe stock predicitons) is complitly up to you, and especially up to your neural network for which task it was trained for. The only limitation you have here is regarding the supported layer operations. E.g. it is not possible to do operations like 3D convolutions or some fancy new non-linear activation functions (There was an overview of supported operations in the docs that I cannot find right now).
Furthermore the framerate also depends on your NN architecture, image resolution etc. so a comparison here is completly misleading. If you want to have a general indication of speed look at how many int8 operations it can handle per second (TOPS) also under what energy consuption (Watts), if you care.
The main advantage of this unit compared to a GPU that is usually used for training+inferencing is much lower energy consumption and unit cost. With roughly 4 Watts on the Edge TPU (as far as I can remember) compared to e.g. 250 Watts GPU. Energy consumption also dictates the necessary cooling solution, which can just be a passive for the Edge Tpu in many cases. Regarding the unit costs, I guess you can easily sees that yourself, if you keep in mind that you can get "nearly" similar inferencing speeds than with a full workstation class GPU. Furthermore, such unit has a much smaller formfactor and weight, which makes it perfect for applications at the edge. (I should also add that the efficiency gain is also a lot due to the precision reduction to int8 (quantization). Quantization is also possible on GPUs.)

And lastly, do i need to keep my neural network in a single computer board for training or can i have it at a cloud?

I am not quite sure what you mean with this. The general workflow would look like this: you use a GPU for training your neural network, after training you optimize/quantize your network, and lastly you deploy your neural network to the "computer board" of your choice that just needs to have a CPU and the Edge TPU and do inferencing operations/predictions for your task.
*Transfer learning is possible of e.g. the last layer. But no backpropagation for full NN training.


What is meant by the expected BLEU cost when training with BLEU and SIMILE? Recently I was reading a paper based on a new evaluation metric SIMILE. In a section, validation loss comparison had been made for SIMILE and BLEU. The plot showed the expected BLEU cost when training with BLEU and SIMILE.

What I'm unable to understand is what is meant by the expected BLEU cost when training with BLEU and SIMILE? Are there any separate cost functions defined for these scores?

I'm attaching the image of the graph.

It looks like the method they use for training takes a set of candidate hypotheses $\mathcal{U}(x)$, along with associated probabilities, and then minimizes the expected value of the cost function over that distribution. Section 3 has the loss function being minimized:

$ \mathcal{L}_{Risk} = \sum\limits_{u \in \mathcal{U}(x)} cost(t, u) \frac{p(u|x)}{\sum_{u' \in \mathcal{U}(x)} p(u'|x)} $.

One of the cost functions used is $1 - \texttt{BLEU}(t, h)$, where $t$ is the target and $h$ is the generated hypothesis. I'm not sure where $p(u|x)$ is coming from, but $1 - \mathcal{L}_{Risk}$ for the BLEU cost function is probably what they're refering to when they mention Expected BLEU.


Does the alpha/beta value of parent nodes change if the alpha beta value of the child node changes? I want to do alpha-beta pruning on this tree:

Consider nodes J and K. K is the max. Therefore, node D has an alpha value of 20, node B has a beta value of 20.

Move to Node E. Pass the beta value of 20 to node E. Node L has an alpha value of 30, therefore, at this point 30 (alpha) > 20 (beta) and we can prune the E to M branch.

Now is my question. My original beta value at node B was 20, and the alpha value passed up to node A was 20. Then, in step 2, I changed the alpha value to be 30. Do i then change the beta value at node B to be 30, and the alpha value at node A to be 30? (and therefore pass 30 as the alpha value to node C)? Or do I keep the original value of 20 at node B, A and C?

I couldn't understand your question clearly, however, it think you are making a slim mistake. let's look at the flowing code from "Russell " and do pruning step by step:

Assume your are In D and you have traversed its both children, Alpha at D becomes 20. We then return back to B, Beta becomes 20 (note that Alpha is -Inf in D). We go to E then L and then back to E. 30 is greater than Beta, so the rest is pruned. Not that Alpha remains -Inf in E, though its value here isn't important. we go back to B the value of Beta remains on changed 20. If we go to F and return back to B Beta remains unchanged and is still 20 (Note that Alpha is still -Inf). We return to A, Alpha becomes 20, And Beta remains +Inf.
So, Considering the code, the max node does not get the Alpha value from its children, rather it decides on its own by setting Alpha = max(Alpha, and returned value of its child) after visiting each child. the same is true for Beta.


How to create an AI snake for a video game? I am creating a snake game in Unity and I would like to implement AI snakes that wander around the globe while avoiding collision with the other snakes on the globe, and if possible I would also like to make the AI snakes purposefully trap other snakes so that the other snakes would collide and die.

The AI snakes must meet the following requirements:

They must move in a certain way. A snake is controlled by a user using the arrow keys on a keyboard, therefor I would also like the AI snakes to move using this form of input.
The AI snakes must move on a sphere

As I know, creating Artificial Intelligence is not an easy task and I would like to know if there are some open source projects that I can use for accomplishing this task.

A relatively simple option which uses AI techniques that are 'traditional' for adversarial games (and which is therefore less of a 'research project' than the use of Machine Learning) is Minimax.

The ingredients for this are:

A list of all the actions that a snake can immediately perform from its current position.
A measure of quality (a.k.a. 'fitness') for the resulting world state.

Traditionally specified for two opponents, the minimax algorithm looks a specified number of moves ahead (alternating between opponents at each turn) and attempts to find the world state that maximizes the quality measure for one opponent whilst minimizing it for the other.

An extension of the two-player algorithm to n opponents (as seemingly required by the OP) is given in this paper.


Why is the equation $r(s', a, s') =\sum_{r \in \mathcal{R}} r \frac{p\left(s^{\prime}, r \mid s, a\right)}{p\left(s^{\prime} \mid s, a\right)}$true? I am referring to eq. 3.6 (page 49) based on Sutton's online book  and can be found in an image below.

I could not make sense of the final derivation of the equation $r(s, a, s')$. My question is actually how do we come to that final derivation?
Surprisingly, the denominator of $p(s'|s, a)$ can literally be replaced by $p(s', r|s, a)$ as eq. 3.4 suggests, then it will end up with "$r$" term only due to cancellation of numerator $p(s', r|s, a)$ and denominator $p(s'|s, a)$.
Any explanation on that would be appreciated.

No, the substitution you suggest based on Equation (3.4) is not correct because you forgot about the $\sum_{r \in \mathcal{R}}$ in the right-hand side Equation (3.4).

Equation (3.4) says (leaving out the middle part):

$$p(s' \vert s, a) \doteq \sum_{r \in \mathcal{R}} p(s', r \vert s, a).$$

If you plug this into Equation (3.6) to substitute the denominator, you can't forget about that sum, you have to include the complete sum in the denominator. Because we have two different sums summing over all rewards in $\mathcal{R}$, I'll change the symbol used in the second sum to $r'$ rather than $r$. This yields:

$$r(s, a, s') \doteq \sum_{r \in \mathcal{R}} r \frac{p(s', r \vert s, a)}{\sum_{r' \in \mathcal{R}} p(s', r' \vert s, a)}.$$

The numerator and denominator are different and will not cancel out.

Intuitively, the numerator is just a single probability; the probability of observing a specific next state $s'$ and a reward $r$ given a specific current state $s$ and action $a$.

The denominator is a sum of many such probabilities, for all possible rewards $r'$ rather than just one specific reward $r$. Because this sum "covers" all possible events for the rewards, it essentially represents simply the probability of observing state $s'$  given state $s$ and action $a$, paired with any arbitrary reward. That can more simply be denoted as $p(s' \vert s, a)$.... which makes sense because that's the very thing we started with :D

Equation (3.6) is as follows (again leaving the middle part out):

$$r(s, a, s') \doteq \sum_{r \in \mathcal{R}} r \frac{p(s', r \vert s, a)}{p(s' \vert s, a)}.$$

In normal English, the left-hand side says "what reward do we expect to get (on average) if we transition from state $s$ to state $s'$ by executing action $a$?"

Such an $\color{red}{\text{expectation of a quantity }r}$ can always be computed by multiplying $\color{blue}{\text{the possible values that }r\text{ can take}}$ by $\color{orange}{\text{the probability of each particular value occurring}}$, and summing up those multiplications. In math, this looks like:

$$\color{red}{r(s, a, s')} = \sum_{\color{blue}{r \in \mathcal{R}}} \color{blue}{r} \times \color{orange}{p(r \vert s, a, s')}.$$

Now, there is a rule in probability that says (see Rule of Multiplication on https://stattrek.com/probability/probability-rules.aspx):

$$p(A, B) = p(A) \times p(B \vert A),$$

so, if we take $A = s'$, $B = r$, and $s, a$ as additional givens for all probabilities, we get:

$$p(s', r \vert s, a) = p(s' \vert s, a) \times p(r \vert s, a, s').$$

This can be rewritten (dividing both sides of the equation by $p(s' \vert s, a)$ and swapping the left-hand and right-hand sides) to:

$$p(r \vert s, a, s') = \frac{p(s', r \vert s, a)}{p(s' \vert s, a)}.$$

Plugging this in for the orange term in the coloured equation above (which itself is hopefully fairly easy to understand intuitively) yields Equation (3.6).


LSTM implementation in KERAS I would like to build an LSTM to predict the correct words order given a sentence. My dataset is composed of sentences, where each sentence has a variable number of words (each word is embedded). The dataset then is an array of matrices, where each matrix is an array of embedded words.

Now, I'm looking to implement it with Keras but I'm not sure how to fit the necessary parameters wanted by the LSTM layer in Keras, like timesteps and batch_size.

Reading on the web, I notice that timesteps is the length of the sequence, so in my case I believe that corresponds to the length of the sentence. But I want to train my LSTM with one sentence at a time, so would the batch_size be 1?

As you read, in keras the input dimensions for a LSTM layer are:  (batch_size, timesteps, input_dim). Where:

batch_size: number of samples (sentences in your case) to compute the loss before running the gradient descent. So number of sentences to train on before compute loss and optimize your model.
timesteps: length of the sequence, in your case length of the sentence
input_dim: the features of your data (the words)

The nice thing about Keras is that you can train with an specific batch size, say batch_size=16, that: helps the model convergence (because it averages the loss of the 16 sentences prediction) and boosts the speed (since the weights are updated only once every 16 sentences).

But then you can infer (or do the predictions) with batch_size=1, meaning, one sentence at a time.

So, if you want to train, specifically with one sentence at a time: batch_size=1. But if you want to take the advantage of using mini-batch then use batch_size=16 or higher for training and batch_size=1 for inference.

BONUS: Keras allows for dynamic batch size change in the models. When a dimension is dynamic in Keras has the value of None, that is why when you do model.summary() you can see: (batch_size, timesteps, input_dim) = (None, 40, 100). This None allows for different batch_size in training and inference


How to simplify policy gradient theoram to $E_{\pi}[G_t \frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}]$? In "Introduction to Reinforcement Learning" (Richard Sutton) section 13.3(Reinforce algorithm) they have the following equation:
\begin{align}
 \nabla_{\theta}J &\propto \sum_s \mu(s) \sum_a q_{\pi}(s,a)\nabla_{\theta}\pi(a|s,\theta) \\
                  &= E_{\pi}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)] \tag{1}\label{1}
\end{align}
But in my opinion equation 1 should be expectation over state distribution: $$E_{\mu}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)]$$
If I am right here then the rest of the lines follows like this:
\begin{align}
\nabla_{\theta}J &= E_{\mu}[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t,\theta)] \\
                  &= E_{\mu}[\sum_a \pi(a|S_t,\theta) q_{\pi}(S_t,a) \frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}] \\
                   &= E_{\mu}[E_{\pi}[q_{\pi}(S_t,A_t)\frac{\nabla_{\theta}\pi(A_t|S_t,\theta)}{\pi(A_t|s,\theta)}]]\\
                   &= E_{\mu}[E_{\pi}[G_t\frac{\nabla_{\theta}\pi(a|S_t,\theta)}{\pi(a|S_t,\theta)}]]
\end{align}
Now the final update rule using stochastic gradient descent will be:
$$\triangle \theta = \alpha E_{\pi}[G_t\frac{\nabla_{\theta}\pi(A_t|S_t,\theta)}{\pi(A_t|S_t,\theta)}] \tag{2}$$
I think I am doing something wrong here because this equation 2 does not match with book also with other materials. Can anyone please show me where I am doing wrong?

When the authors write go from
$$\nabla_{\theta}J \propto \sum_s \mu(s) \sum_a q_{\pi}(s,a)\nabla_{\theta}\pi(a|s;\theta)\;$$
to
$$\nabla_{\theta}J = E_{\pi}\left[\sum_a q_{\pi}(S_t,a) \nabla_{\theta}\pi(a|S_t;\theta)\right]\;$$
they are simply taking an expectation where the only random variable is the state $S_t$. This is because, as they say in the book, the Policy Gradient Theorem is a sum over a state distribution, therefore it can be written as an expectation. The expectation is over the states wrt the state distribution; the $\pi$ subscript here does not mean we are taking expectation with respect to the action policy $\pi$, they use the notation $\pi$ to emphasise that the state distribution is induced by the current policy $\pi$ -- this is what makes REINFORCE an on-policy algorithm because the state distribution with which we take the expectation must come from the current policy $\pi$, not some arbitrary distribution.
Now, as you don't seem to understand how they go from this to the Stochastic Gradient Ascent (SGA) (NOT descent as you keep referring to it as) update rule in the book, I will explain further. As you rightly say we can go from my previous equation to the following
$$\nabla_{\theta}J = E_{\pi}\left[G_t \nabla_{\theta}\log\pi(A_t|S_t;\theta)\right]\;$$
by doing some re-arranging and noting that $G_t$ is an unbiased estimate of $q_\pi(s, a)$ when taking expectation over the actions and states. Now, this expectation we have is with respect to the actions and states; your first mistake is that you have made it an expectation over the actions without signifying that the action is now a random variable (maybe you could look up expectations and random variables to understand really what this means).
Your second mistake is by not seeing how you can use this gradient to optimise the policy parameters. As we want to maximise this objective we want to perform SGA to it; that is we want to perform
$$\theta = \theta + \alpha \nabla_\theta J\;;$$
but $\nabla_\theta J$ is an expectation. It would be costly to evaluate this at every single state-action pair that we see in an episode, thus we only perform SGA for one state-action tuple at a time. Now, you might think that this is not correct, but it is in fact an unbiased estimate as we will sample lots of state-action pairs; this kind of estimation is known as Monte Carlo Sampling. Therefore, we can write our REINFORCE update rule as
$$\theta = \theta + \alpha G_t \nabla_\theta \log \pi(A_t | S_t; \theta)\;;$$
which is exactly the update rule in the book.
Note that at the start of the chapter in Sutton and Barto they also make it clear that we wish to perform
$$\theta = \theta + \alpha \hat{\nabla J(\theta)} \;;$$
where $\hat{\nabla J(\theta)}$ is a stochastic estimate whose expectation approximates the true gradient; this is exactly what we are doing, $G_t \nabla_\theta \log \pi(A_t | S_t; \theta)$ is our stochastic estimate.


Examples of ontologies made with AI I'm looking for more or less successful artificial intelligence usage examples to build an ontology or rationale why it can't be done. I found a lot of articles on how to use ontologies for AI, but not succeded vice versa.

Ontology learning is a relatively new field that aims to automatically (or semi-automatically) learn or create ontologies (using machine learning, text mining, knowledge representation and reasoning, information retrieval and natural language processing techniques) from some text or corpus.

Ontology learning can be divided into different phases or tasks

the acquisition of terms that refer to specific concepts (named-entity
recognition)
the recognition of synonyms among these terms
the identification of taxonomic relations (such as the "is-a" relation)
the establishment of non-hierarchical relations
the derivation of new knowledge, i.e. knowledge that is not explicitly
encoded by the ontology.

See also Ontology Learning from Text: An Overview (2003) and A survey of ontology learning techniques and applications (2018) for more details.

In the paper Ontology Learning with Deep Learning: a case study on Patient Safety using PubMed (2016), the authors investigate how continuous bag-of-words (CBOW) and skip-gram (two language models based on artificial neural networks) can be used to aid ontology development for patient safety, using PubMed citations as a corpus.

Latent Dirichlet allocation (LDA) has also been used for ontology learning, for example, in the paper Terminological ontology learning and population using latent Dirichlet allocation. (2014).


Is $\min(h_1(s),\ h_2(s))$ consistent? If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?

You can easily find a counterexample. Suppose that there are three nodes $s$, $p$, and $goal$ such that $s \rightarrow p \rightarrow goal$. The real cost of going from $s$ to $p$ is $c(s,p) = 10$ and $c(p, goal) = 10$. Also, $h_1(s) = 18$, $h_1(p) = 9$, $h_1(goal) = 0$, $h_2(s) = 17$, $h_2(p)  = 1$.On the other hand, $h^*(s) = 19$ and $h^*(p) = 10$.
Now, $h_1(s) \leqslant c(s,p) + h_1(p)$ and $h_1(s) \leqslant c(s, goal) + h_1(goal)$ that satisfies the consistency constraint of $h_1$. Also, $h_2(s) \leqslant h^*(s)$ and $h_2(s) \leqslant h^*(p)$ that approve $h_2$ is admissible.
However, for any node $n$, if we define $h_3(n) = \min(h_1(n), h_2(n))$:
$$h_3(s) = \min(h_1(s), h_2(s)) = 17 \not\leqslant c(s,p) + \min(h_1(p), h_2(p)) =
$$
$$c(s,p) + h_3(p) = 10 + 1 = 11. $$
It means that $h_3$ as a heuristic function is not consistent.


Are there any pretrained models for human recognition from all angles? I need to be able to detect and track humans from all angles, especially above.

There are, obviously, quite a few well-studied models for human detection and tracking, usually as part of general-purpose object detection, but I haven't been able to find any information that explicitly works for tracking humans from above.

There were no pre-trained models for human that were taken from all angles (which is a somewhat extreme requirement) or specifically from above.  This condition may change due to the high value of such to the surveillance industry.

There are already several projects for which there is human specific pattern recognition and there have emerged some data sets to support this more specific field of objectives, some of which are based on moving rather than stationary images.  This is for two reasons.

Multiple frames has the potential (should computing resource utilization be overcome) to produce higher accuracy and reliability in human recognition partly because of the identification of joints in movement and partly because there is simply more information available on each object that could be a human.
Trajectory of pedestrians is important for both law enforcement and security and for avoiding pedestrians in vehicle automation.

These are some of the projects and download sites that are related to the goal of the question, but unfortunately do not seem to provide data sets of humans from above or pre-trained networks from that visual perspective.

https://software.intel.com/en-us/openvino-toolkit/documentation/pretrained-models
https://docs.microsoft.com/en-us/azure/machine-learning/studio-module-reference/pretrained-cascade-image-classification
https://github.com/matterport/Mask_RCNN
https://drive.google.com/drive/folders/1zvl89AgFAApbH0At-gMuZSeQB_LpNP-M
https://github.com/tensorflow/models/blob/master/research/object_detection/g3doc/detection_model_zoo.md
https://modelzoo.co/model/human-pose-estimation-with-tensorflow


Is traditional machine learning obsolete given that neural networks typically outperform them? I have been coming across visualizations showing that the neural nets tend to perform better as compared to the traditional machine learning algorithms (Linear regression, Log regression, etc.)

Assuming that we have sufficient data to train deep/neural nets, can we ignore the traditional machine learning topics and concentrate more on the neural network architectures?

Given the huge amount of data, are there any instances where traditional algorithms outperform neural nets?

"Assuming that we have sufficient data..." — that's quite a big assumption. Also, traditional methods are well understood, while neural networks (and especially deep learning) is still something of a black box: you train it, and then you get a mapping from input to output. But you don't really know how that mapping is achieved.

It's not only about performance, it's also about efficiency (speed, use of power, etc) and transparency (being able to explain why something happens).

So there are several reasons why we don't put all our eggs into the NN basket:

it is a lot easier to see what's happening and diagnose errors with 'traditional' methods which are well-understood. This is an important point in real-life applications
in many cases we do not have the required amount of training data available that is necessary for deep learning approaches to work
training a DL system is much more time- (and energy) consuming than other algorithms

I'd much rather have a nuclear power plant operated by a traditional algorithm that makes a few mistakes, but nothing drastic (and being aware that it makes these kinds of mistakes allows you to guard against them), than have a total black box doing it where I have no idea why decisions are reached and what happens in edge cases not covered by the training data.

It's fine for toy projects where the stakes are low, but in real-world applications there are often different constraints that DL systems cannot satisfy.


Why do we apply the mutation operation after generating the offspring? Why do we apply the mutation operation after generating the offspring, in genetic algorithms?

The mutation operation is (usually) needed to introduce new genes not found in the population.

For example, suppose that you have 4 possible genes $A$, $B$, $C$, and $D$, and that your chromosomes have a non-binary encoding. In that case, if no member of your population has the gene $D$, then no amount of crossover operations will result in the introduction of that gene.

However, if your chromosomes use a binary encoding, then new genes could be introduced as a side effect of crossover operations. But it is always safer to have some kind of mutation to ensure that all genes can be accessed.

See also the paper Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator, which mentions several non-binary encodings for the TSP.


Why should we study causation in artificial intelligence? Judea Pearl won the 2011 Turing Award

  For fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning.

He is credited with the invention of Bayesian networks and a framework for causal inference.

Why should we study causation and causal inference in artificial intelligence? How would causation integrate into other topics like machine learning? There are facts or relations that cannot be retrieved from data (e.g. cause-effect relations), which is the driving force of ML. Are there other reasons for studying causation?

There are two intermixed elements in your question:

Why have people already studied causality in AI?
Why would people like to continue studying causality in AI?

tl;dr: AI systems can't function in the real world without some way of understanding uncertainty. The best ways we have to understand uncertainty don't work well unless we also understand causal structure. Getting most of the way towards this understanding was a huge accomplishment for AI research, but there's still a big problem waiting to be solved here.

For part 1, let's think about where research into causality comes from. Pearl originally set out to solve a major problem plaguing AI researchers in the 1980s: reasoning under uncertainty. This area is so central to AI systems that it has its own, large, conference: UAI. The need for reasoning under uncertainty arose because the real world is filled with uncertainty. Consider even a simple problem, like have a robot navigate an empty room. Even if the robot knows its initial position exactly, it is not likely to know its true position for long. The robots' wheels might have a certain specification, but wheels stick and slip (friction), and they do so unpredictably (e.g. maybe one part of the floor didn't get polished as much as the others). The robot might have sensors, but sensors are imperfect. Does a light sensor value of 0.25 mean a wall is near, or just that the sun is coming through the window at an unfortunate angle? Or maybe just that the shade of paint is slightly different there? Does our acoustic sensor reading of 1.35 mean that we're 1.35 meters from the wall, or did the signal get reflected, and return to us by a different path?

One of Pearl's major contributions was showing how we can use the rules of probability to reason about these events correctly. Although others had done the basics of this long ago, Pearl proposed the idea of Bayesian Networks. Thrun and many others used these techniques to solve problems like the robot navigation task discussed above.

A problem with Bayesian Networks is that, if built incorrectly, they lose much of their efficiency benefits. The correct construction is usually the one that best captures known causal relations between factors. Further, algorithms for inference in a Bayesian Network can not easily answer questions about counterfactuals. They cannot tell our robot what would happen in a world where certain actions were taken. They can only say whether certain behaviors are likely co-occur.

These outstanding issues led Pearl to work on causality and causal networks. It is important for our systems to be able to answer counterfactual questions, because often the answers to those questions determine how the system aught to act. Pearl's do-calculus (nicely summarized here, and in Pearl's The Book of Why) has solved this problem, and shown how causes can often be inferred from observation alone. It's super exciting!

Hopefully you're now convinced that Causality was worth studying within AI. You might now wonder why it's still worth studying.

The main open problem right now is that to do causal reasoning, we need to already have a network that describes causal relations. These networks are hard to construct by hand, so we'd like to be able to learn the structures of these networks. Unfortunately, this looks like a very hard problem, both to solve exactly (it's #P-hard if I recall correctly), and to approximate. There are no known general algorithms, at least as of 2018. Getting this would be a major breakthrough in AI research, and more generally, in statistics, philosophy of science, and epistemology. Even getting something that mostly worked, most of the time, would be huge. Peter Van Beek has been doing some work on this recently, which could be a good starting place if you want to read more.


How can I train a deep learning model to predict a matrix? I am trying to train a deep learning model to predict an 8*2 matrix. The predicted matrix would have complex values and the input matrix would be real numbers. Can it be done? Thank you for your time.

You could use a CNN or Fully Connected Network and output a matrix of size 8*2*2. The first 8*2 matrix is the real number and the second is the imaginary number. Example code below uses keras.

'''
input: numpy array of shape(batch_size,input_dim_0,input_dim_1,1)
Y: keras tensor of shape(batch_size,8,2,2)

'''

model = Sequential()
model.add(Conv2d(64,3,input_dim =(input_dim_0,input_dim_1,1))
model.add(Conv2d(64,3)
model.add(Conv2d(2,3)

model.compile(loss='MSE',metrixs=['accuracy'])
model.fit(input,Y)


What are the (general) sizes of AlphaGo and Deep Blue? I'm trying to get a gauge on just how big the programs and databases are these automata.  I understand that this is a changing number, particularly in regard to Machine Learning.

Q: How large was Deep Blue when it beat Gary Kasparov?

Q: How big was AlphaGo when it beat Lee Sedol?

AlphaGo used data from the KGS Go Server, which had 160,000 games and 29 million board/next-move pairs. But crucially, after it was trained on the dataset, AlphaGo was trained through self-play, so its competence shouldn't be measured strictly in terms of its database.

I'm not 100% sure how Deep Blue worked, but I think it was a mix of 1. a "book" of opening theory 2. explicitly coded board evaluation functions 3. a "book" of endgames. So there isn't a "database" in your traditional "ML by big data" sense. But in any case, I would assume the bulk of the work is done by the evaluation function, so again its strength cannot be measured in terms of if its database.


Why does the accuracy drop while the loss decrease, as the number of epochs increases? I've been trying to find the optimal number of epochs that I should train my neural network (that I just implemented) for.
The visualizations below show the neural network being run with a variable number of epochs. It is quite obvious that the accuracy increases with the number of epochs. However, at 75 epochs, we see a dip before the accuracy continues to rise. What is the cause of this?

Decrease of loss does not essentially lead to increase of accuracy (most of the time it happens but sometime it may not happen). To know why, you can have a look at this question. The network cares about decreasing the loss and it does not care about the accuracy at all. So it's no surprise to see what you presented.
Additional note: If you use batch approaches to teach your network, or if you choose a big step size you may also see that the loss increases sometimes but in the case of batching, the hope is that its trend is to be decreased.


How to build a Neural Network to approximate the Q-function? I am learning reinforcement learning with Q-learning using online resources, like blog posts, youtube videos, and books. At this point, I have learned the underpinning concepts of reinforcement learning and how to update the q values using a lookup table.
Now, I want to create a neural network to replace the lookup table and approximate the Q-function, but I am not sure how to design the neural network. What would be the architecture for my neural network? What are the inputs and outputs?
Here are the two options I can think of.

The input of the neural network is $(s_i, a_i)$ and the output is $Q(s_i,a_i)$

The input is $(s_i)$ and the output is a vector $[Q(s_i,a_1), Q(s_i,a_2), \dots, Q(s_i,a_N)]$

Is there any other alternative architecture?
Also, how to reason about which model would be logically better?

I had the same question when I first learned RL. The architectural design may depend on the task you're considering. Since you're moving from a tabular Q-learning to function approximation, I'm suspecting that you are considering a relatively small action space; in this case, you should use option 2 where the input is the state and the number of output nodes matches the number of available actions.
One main reason for this choice: when exploiting the learnt function (i.e. policy is $\arg \max_a Q(s,a)$), for option (1) you would have to repeatedly run a forward pass for all available actions, whereas option (2) requires a single forward pass and run arg max either through numpy or the framework you're using.


When does backward propagation occur in n-step SARSA? I am trying to understand the algorithm for n-step SARSA from Sutton and Barto (2nd Edition). As I understand it, this algorithm should update n state-action values, but I cannot see where it is propagated backward. Can someone explain to me how that works?

The important part, where you can see a single reward value is used for $n$ different updates, is the part where a sum of $R_i$ values with $i$ ranging from $\tau + 1$ to $\tau + n$ is assigned to $G$.

So yes, the outer loop of the algorithm always does at most one update per iteration, but for that update it uses multiple previously observed $R_i$ values. Each of those $R_i$ values is used for multiple updates (not multiple updates at the same time, but multiple updates spread out over different iterations).


An intuitive explanation of Adagrad, its purpose and its formula It (Adagrad) adapts the learning rate to the parameters, performing smaller updates
  (i.e. low learning rates) for parameters associated with frequently occurring features, and larger updates (i.e. high learning rates) for parameters associated with infrequent features.

From Sebastian Ruder's Blog

If a parameter is associated with an infrequent feature then yes, it is more important to focus on properly adjusting that parameter since it is more decisive in classification problems. But how does making the learning rate higher in this situation help?

If it only changes the size of the movement in the dimension of the parameter (makes it larger) wouldn't that make things even more imprecise? Since the network depends more on those infrequent features, shouldn't adjusting those parameters be done more precisely instead of just faster? The more decisive parameters should have a higher "slope", thus why should they also have high learning rates? I must be missing something, but what is it?

Further, in the article, the formula for parameter adjustments with Adagrad is given. Where exactly in that formula do you find the information about the frequency of a parameter? There must be a relationship between the gradients of a parameter and the frequency of features associated with it because it's the gradients that play an important role in the formula. What is that relationship?

TLDR: I don't understand both the purpose and formula behind Adagrad. What is an intuitive explanation of it that also provides an answer to the questions above, or shows why they are irrelevant?

I found a somewhat more accessible introduction here:

https://medium.com/konvergen/an-introduction-to-adagrad-f130ae871827

Let me start from the last part of your question. The frequency of a parameter is in G_t, which is the accumulated sum of squared gradients from all the time steps up to step t. If the gradient vanishes in many of the previous steps, then you divide the learning rate with a smaller number for that parameter.

And for the first part, you want the parameter that is more frequent to have a smaller learning rate as it is updated on more iterations compared to a parameter which is updated only a small number of times.


What are the criteria for a system to be considered intelligent? For example, could you provide reasons why a sundial is not "intelligent"?
A sundial senses its environment and acts rationally. It outputs the time. It also stores  percepts. (The numbers the engineer wrote on it.)

What properties of a self driving car would make it "intelligent"?

Where is the line between non intelligent matter and an intelligent system?

Typically, I think of intelligence in terms of the control of perception. [1] A related, but different, definition of intelligence is the (at least partial) restriction of possible future states. For example, an intelligent Chess player is one whose future rarely includes 'lost at chess to a weaker opponent' states; they're able to make changes that move those states to 'won at chess' states.

These are both broad and continuous definitions of intelligence, where we can talk about differences of degree. A sundial doesn't exert any control over its environment; it passively casts a shadow, and so doesn't have intelligence worth speaking of. A thermostat attached to a heating or cooling system, on the other hand, does exert control over its environment, trying to keep the temperature of its sensor within some preferred range. So a thermostat does have intelligence, but not very much.

Self-driving cars obviously fit those definitions of intelligence.

[1] Control is meant in the context of control theory, a branch of engineering that deals with dynamical systems that perceive some fact about the external world and also have a way by which they change that fact. When perception is explicitly contrasted to observations, it typically refers to an abstract feature of observations (you observe the intensity of light from individual pixels, you perceive the apple that they represent) but here I mean it as a superset that includes observation. The thermostat is a dynamical system that perceives temperature and acts to exert pressure on the temperature it perceives.

(There's a philosophical point here that the thermostat cares directly about its sensor reading, not whatever the temperature "actually" is. I think that's not something that should be included in intelligence, and should deserve a name of its own, because understanding the difference between perception and reality and seeking to make sure one's perceptions are accurate to reality is another thing that seems partially independent of intelligence.)


What are the steps to follow to learn artificial intelligence? I know nothing about AI. Can anybody tell me what steps I have to follow to learn artificial intelligence?

Are there any special technologies, or anything else, I have to learn?

A really good introduction is the Berkeley CS188 class videos and projects.  You can find those materials at http://ai.berkeley.edu/home.html

You probably also want to get ahold of a copy of Artificial Intelligence: A Modern Approach by Norvig and Russell.

For more on the "machine learning" aspects of AI, including an introduction to Neural Networks, take the Andrew Ng "Machine Learning" class on Coursera.

Another book I would recommend is Introduction to Artificial Intelligence by Philip C. Jackson. It's older, which is exactly what makes it valuable.  It's a good overview of techniques and ideas that aren't "en vogue" right now, but which may still be useful to you.


Neural nets for novices Stories like this one are quite popular these days.

The idea of training a neural net to do something silly like this may sound trivial to experts like you,  but for a novice like me it could be an interesting learning experience.

Is there novice-friendly software I could play with to train a neural net to do something like this or is there necessarily a steep learning curve?

An intuitive NN playground can be found in TensorFlow Playground

Also, check the Google ML crash course for coders as they promised to add more practicals.


How do randomly initialized neural networks behave? I am wondering how the output of randomly initialized MLPs and ConvNets behave with respect to their inputs.  Can anyone point to some analysis or explanation of this?

I am curious about this because in the Random Network Distillation work from OpenAI, they use the output of randomly initialized network to generate intrinsic reward for exploration.  It seems that this assumes that similar states will produce similar outputs of the random network.  Is this generally the case?

Do small changes in input yield small changes in output, or is it more chaotic?  Do they have other interesting properties?

The output of randomly initialised neural networks will be random. I am not sure if I understand your question correctly but I would like to try and explain what OpenAI is trying to achieve with their RND Distillation approach.

Any re-enforcement or supervised "learning" algorithm such as a neural network (NN) with back-propagation, genetic algorithm, partial swarm etc requires a fitness function. The fitness function "directs" the algorithm to a solution.

The basic idea is that the algorithm is randomly initialised. The algorithm is run, and then parts of the algorithm are changed. In this case the weights of the NN.

A number of algorithms exist to update the weights, the most common back propagation / gradient decent as used in the paper. To update the weights the output of the NN is compared to the optimum output. Sometimes the optimum is known. Other times it is not. In the case of a game the optimum output is not known. It is assumed that the more points gained the better the NN does. In this case the fitness function or policy is the sum of points gained when playing the game. But gradient descent needs an error (i.e difference between output and expected output), which does not exist when playing a game, because you don't know what the points should be. However the NN could play one round of the game score some points, then run the NN again on the next move to determine a prediction of future points. The difference between the points gained and the prediction is then the error, which gradient descent can use. [Hope this makes sense]

This is fine for games like pong, a NN could play the game pong randomly and score point at each prediction, which will direct gradient descent into updating the weights to maximise points.

However, games such as Montezuma’s Revenge, requires a lot of complex actions before points are gained. If the points stay 0, how does gradient descent determine if the weights should be decreased or increased?

Instead, the authors initialise a second random neural network which remains the same for the duration of training. As mentioned above the output of a randomly initialised neural network is random.

The output of the actual NN, and world state is then passed through the random NN (RND), which will return a random value. The NN is then required to not only determine a game action but also determine the result of the RND.

The policy function is extended from just points to also predict the result of the RND. The greater the prediction error the more bonus points are allocated to the policy function. This encourages gradient descent to change the weights of the NN to explore unseen parts of the game as this increases the prediction error of the RND which increases points. At the same time gradient descent must update the weights of the NN to predict the RND.

I hope this answers your question.

In summary randomly initialised NN include multilayered perceptrons or convolutional networks will behave randomly with respect to their inputs. The RND network is randomly set once at the star of training, and used to basically remind the NN undergoing training that it has done this before do not do this again - i.e. rewards the NN for doing something new (exploration).


Why do we have to dot product in the Low-rank Bilinear Pooling? I was reading this paper Hadamard Product for Low-rank Bilinear Pooling. I understand what they are trying to say, but I don't know why we have to convert the element-wise multiplication into a scalar (using the dot product)
$$
\mathbb{1}^{T}\left(\mathbf{U}_{i}^{T} \mathbf{x} \circ \mathbf{V}_{i}^{T} \mathbf{y}\right)+b_{i} \tag{2}\label{2}
$$
Why do we have to multiply the resulting vector by the one vector? We would still use the multiplicative interaction between elements if we did not consider multiplying by that one vector.

The paper (which I was not familiar with) proposes a new pooling method, which they name "Low-rank Bi-linear Pooling". Because it is a pooling method, its output should be a single value over some input spatial region (the goal of pooling is to down-sample an input representation). They do not want to use the resulting vector from the element-wise multiplication, they want to get a single scalar. Notice their initial formula:
$$
f_{i}=\sum_{j=1}^{N} \sum_{k=1}^{M} w_{i j k} x_{j} y_{k}+b_{i}=\mathbf{x}^{T} \mathbf{W}_{i} \mathbf{y}+b_{i}\label{1}\tag{1}
$$


What do the values of the leaves of the decision tree represent? This is more of a technical question rather than a practical one.

I've exported a decision tree made with python/scikit learn and would like to know what the "value" field of each leaf corresponds to.

Decision tree nodes are split bases on the number of data samples, these numbers indicate the number of data samples they are fit to.
In your case samples = 256. It is further split into two nodes of 154 and 102.


What is the difference between one-shot learning, transfer learning and fine tuning? Lately, there are lots of posts on one-shot learning. I tried to figure out what it is by reading some articles. To me, it looks like similar to transfer learning, in which we can use pre-trained model weights to create our own model. Fine-tuning also seems a similar concept to me.

Can anyone help me and explain the differences between all three of them?

They are all related terms.

From top to bottom:

One-shot learning aims to achieve results with one or very few examples. Imagine an image classification task. You may show an apple and a knife to a human and no further examples are needed to continue classifying. That would be the ideal outcome, but for algorithms.

In order to achieve one-shot learning (or close) we can rely on knowledge transfer, just like the human in the example would do (we are trained to be amazing at image processing, but here we would also exploit other knowledge like abstract reasoning abilities, and so on).

This brings us to transfer learning. Generally speaking, transfer learning is a machine learning paradigm where we train a model on one problem and then try to apply it to a different one (after some adjustments, as we'll see in a second).

In the example above, classifying apples and knives is not at all trivial. However, if we are given a neural network that already excels at image classification, with super-human results in over 1000 categories... perhaps it is easy to adapt this model to our specific apples vs knives situation.

This "adapting", those "adjustments", are essentially what we call fine-tuning. We could say that fine-tuning is the training required to adapt an already trained model to the new task. This is normally much less intensive than training from scratch, and many of the characteristics of the given model are retained.

Fine-tuning usually covers more steps. A typical pipeline in deep learning for computer vision would be this:

Get trained model (image classifier champion)
Note the head of our model does not match our needs (there's probably one output per category, and we only need two categories now!)
Swap the very last layer(s) of the model, so that the output matches our needs, but keeping the rest of the architecture and already trained parameters intact.
Train (fine-tune!) our model on images that are specific to our problem (only a few apples and knives in our silly example). We often only allow the last layers to learn at first, so they "catch up" with the rest of the model (in this case we talk about freezing and unfreezing and discriminative learning rates, but that's a bit beyond the question).

Note that some people may sometimes use fine-tuning as a synonym for transfer learning, so be careful about that!


How do I label images for deep learning classification? I have roughly 30,000 images of two categories, which are 'crops' and 'weeds.' An example of what I have can be found below:

The goal will use my training images to detect weeds among crops, given an orthomosaic GIS image of a given field. I guess you could say that I'm trying to detect certain objects in the field.
As I'm new to deep learning, how would one go about generating training labels for this task? Can I just label the entire photo as a 'weed' using some type of text file, or do I actually have to draw bounding boxes (around weeds) on each image that will be used for training? If so, is there an easier way than going through all 30,000 of my images?
I'm very new to this, so any specific details would really help a lot!

If each photo is intended to show a photo of weed or crops you should give one label. If your task is different where you also try to localize weed or crops in the image, then you need to label accordingly. My understanding is you are trying to do the first case, therefore, there should be one label for each image.


DQN stuck at suboptimal policy in Atari Pong task I am in the process of implementing the DQN model from scratch in PyTorch with the target environment of Atari Pong. After a while of tweaking hyper-parameters, I cannot seem to get the model to achieve the performance that is reported in most publications (~ +21 reward; meaning that the agent wins almost every volley).

My most recent results are shown in the following figure. Note that the x axis is episodes (full games to 21), but the total training iterations is ~6.7 million.

The specifics of my setup are as follows:

Model

class DQN(nn.Module):
    def __init__(self, in_channels, outputs):
        super(DQN, self).__init__()
        self.conv1 = nn.Conv2d(in_channels=in_channels, out_channels=32, kernel_size=8, stride=4)
        self.conv2 = nn.Conv2d(in_channels=32, out_channels=64, kernel_size=4, stride=2)
        self.conv3 = nn.Conv2d(in_channels=64, out_channels=64, kernel_size=3, stride=1)
        self.fc1 = nn.Linear(in_features=64*7*7 , out_features=512)
        self.fc2 = nn.Linear(in_features=512, out_features=outputs)

    def forward(self, x):
        x = F.relu(self.conv1(x))
        x = F.relu(self.conv2(x))
        x = F.relu(self.conv3(x))
        x = x.view(-1, 64 * 7 * 7)
        x = F.relu(self.fc1(x))
        x = self.fc2(x)
        return x    # return Q values of each action

Hyperparameters

batch size: 32
replay memory size: 100000
initial epsilon: 1.0
epsilon anneals linearly to 0.02 over 100000 steps
random warmstart episodes: ~50000
update target model every: 1000 steps
optimizer = optim.RMSprop(policy_net.parameters(),  lr=0.0025, alpha=0.9, eps=1e-02, momentum=0.0)

Additional info

OpenAI gym Pong-v0 environment
Feeding model stacks of 4 last observed frames, scaled and cropped to 84x84 such that only the "playing area" is visible.
Treat losing a volley (end-of-life) as a terminal state in the replay buffer.
Using smooth_l1_loss, which acts as Huber loss
Clipping gradients between -1 and 1 before optimizing
I offset the beginning of each episode with 4-30 no-op steps as the papers suggest

Has anyone had a similar experience of getting stuck around 6 - 9 average reward per episode like this?

Any suggestions for changes to hyperparameters or algorithmic nuances would be greatly appreciated!

Incase you still haven't been able to resolve the problem, here's a link to the answer to my own question, which has the step-wise changes I made to achieve a +18 average score saturation using just a 10000 replay buffer size and a normal Double DQN (DDQN), trained for about 700-800 episodes. The updated code can also be found here.

No fancy changes like Prioritized Replay Buffer or any secret hyperparameter changes are required. It's usually something simple, like a small problem with the input preprocessing step.


What is the meaning of "stationarity of statistics" and "locality of pixel dependencies"? I'm reading the ImageNet Classification with Deep Convolutional Neural Networks paper by Krizhevsky et al, and came across these lines in the Intro paragraph:

  Their (convolutional neural networks') capacity can be controlled by varying their depth and breadth, and they also make strong and mostly correct assumptions about the nature of images (namely, stationarity of statistics and locality of pixel dependencies). Thus, compared to standard feedforward neural networks with similarly-sized layers, CNNs have much fewer connections and parameters and so they are easier to train, while their theoretically-best performance is likely to be only slightly worse.

What's meant by "stationarity of statistics" and "locality of pixel dependencies"? Also, what's the basis of saying that CNN's theoretically best performance is only slightly worse than that of feedforward NN?

locality of pixel dependencies probably means that neighboring pixels tend to be correlated, while faraway pixels are usually not correlated. This assumption is usually made in several image processing techniques (e.g. filters). Of course, the size and the shape of the neighborhood could vary, depending on the region of the image (or whatever), but, in practice, it is usually chosen to be fixed and rectangular (or squared).

stationarity of statistics might mean that the values of the pixels do not change over time, so this could be related to diffusion techniques in image processing. stationarity of statistics might also mean that the values of the pixels do not change much in a spatial neighborhood, even though, stationarity, e.g. in reinforcement learning, usually means that something does not change over time (so, if that's the case, the terminology stationarity is at least misleading and confusing, in this context), so this might be related to the locality of pixel dependencies property. Possibly, stationarity of statistics could also indirectly mean that you can use the same filter to detect the same feature in different regions of the image.

With while their theoretically-best performance is likely to be only slightly worse the authors probably thought that, theoretically, CNNs are not as powerful as feedforward neural networks. However, both CNNs and FFNNs are universal function approximators (but, at the time, nobody probably had yet investigated seriously the theoretical powerfulness of CNNs).


Why do we update all layers simultaneously while training a neural network? Very deep models involve the composition of several functions or layers. The gradient tells how to update each parameter, under the assumption that the other layers do not change. In practice, we update all of the layers simultaneously.

The above is an extract from Ian Goodfellow's Deep Learning  - which talks about the need for batch normalization.

Why do we update all the layers simultaneously? Instead, if we update layers one at a time during backpropagation - it will eliminate the need for batch normalization, right?

Reference: A Gentle Introduction to Batch Normalization for Deep Neural Networks

P.S. The attached link says: Because all layers are changed during an update, the update procedure is forever chasing a moving target. Apart from the main question, it would be great if someone could explain why exactly a moving target is being referred to in the above sentence.

Why do we update all layers simultaneously while training a neural network?

We typically train a neural network with gradient descent and back-propagation. Gradient descent is the iterative algorithm used to update the parameters and back-propagation is the algorithm used to compute the gradient of the loss function with respect to each of these parameters.

Let's denote a vector that contains all learnable parameters of a neural network $M$ by $\mathbf{w} = \left[w_1, \dots, w_n \right] \in \mathbb{R}^n$ (so $M$ contains $n$ learnable parameters), the loss function of $M$ by $\mathcal{L}$,  the gradient of the loss function with respect to each parameter $w_i$ of $M$ by $ \nabla \mathcal{L} = \left[ \frac{\partial \mathcal{L}}{\partial w_1}, \dots, \frac{\partial \mathcal{L}}{\partial w_n}  \right] \in \mathbb{R}^n$, then the gradient descent step to update all parameters is

\begin{align}
\mathbf{w} \leftarrow \mathbf{w} - \gamma * \nabla \mathcal{L} \tag{1} \label{1}
\end{align}

where $\gamma \in \mathbb{R}$ is the learning rate.

In equation \ref{1}, we are assigning to $\mathbf{w}$ the value $\mathbf{w} - \gamma * \nabla \mathcal{L}$, so we are updating all parameters $\mathbf{w}$ simultaneously, so we are also updating all layers simultaneously.

In principle, you could update each parameter $w_i$ individually. To be more precise, you would have the following update rule

\begin{align}
w_i \leftarrow w_i - \gamma * \frac{\partial \mathcal{L}}{\partial w_i}, \; \forall i\tag{2} \label{2}
\end{align}

So, you could update first $w_1$, then $w_2$, and so on.

Actually, you don't need to update the parameters sequentially (also because there is no real order of the parameters). You can actually update them in any other way. You can update the parameters in any way because, although the computation of the gradient highly depends on the structure of the neural network (so if you change the structure, the computation of the gradient also changes), once the gradient is computed, you already have all information to update each parameter independently of each other.

You typically update all parameters (or layers) simultaneously because, in practice, you work with vectors and matrices rather than scalars in order to take benefit from efficient matrix multiplication algorithms and hardware (i.e. GPUs).


What should we do when the selection step selects a terminal state? In Monte Carlo tree search, what should we do when the selection step selects a terminal state (i.e. a won or lost state), which is, by definition, a leaf node? Expansion and simulation is not in order, as it's game over, but does the tree (score/visits) need to be updated (backpropagation)? Won't this particular node be selected continuously?

In the basic form, if you encounter a terminal leaf, you add visits and score depending on whether it is a win or loss, and backpropagate accordingly. The same as if you made a simulation step, but in this case the "simulation" is instant.

But you can improve that: If the leaf is losing, you can give it a very large negative score or even $-\infty$, so in the next selection step it surely won't be chosen, unless other moves are as bad. But if it is a winning leaf, you not only can give it a very big positive score or $\infty$, but also add a negative score for the immediate parent, so the parent won't be chosen, as it is obviously a losing state for him. This way we can save some simulations. I had encountered that situation many times in my game and Monte Carlo tree searches.

Suppose the parent has $200$ unexplored children, $10$ of which are immediate wins for the opponent. Your search may explore $100$ non-winning children and have a score of 80/100. But then it encounters the terminate child. After that, normally, it would have $80/101$, so, still, a big chance to be chosen in the next iteration. And it would take many iterations to see that this is not a good move, as it would need to get like $80/150$ or more. But if we cancel out the score or give it a negative one like $-1/101$, then we ensure it won't be chosen.

It seems in literature it's called "MCTS solver", to backpropagate proven wins and losses.


What parameters can be tweaked to avoid a generator or discriminator loss collapsing to zero when training a DC-GAN? Sometimes when I am training a DC-GAN on an image dataset, similar to the DC-GAN PyTorch example (https://pytorch.org/tutorials/beginner/dcgan_faces_tutorial.html), either the Generator or Discriminator will get stuck in a large value while the other goes to zero. How should I interpret what is going on right after iteration 1500 in the example loss function image shown below ? Is this an example of mode collapse? Any recommendations for how to make the training more stable? I have tried reducing the learning rate of the Adam optimizer with varying degrees of success. Thanks!

GANs are notably hard to train and it is not uncommon to have large bumps in the losses. The learning rate is a good start but the instability may come from a wide variety of reasons. I'm assuming that you have no bug in your code or data.

For one, gradient descent is not well suited to the 2-player game we're playing. I've personally found ExtraAdam to yield much more stable training (code, paper).

It could also come from the loss and many tricks have been developed and one of the most popular one is enforcing smoothness in the gradient (see W-GAN, W-GAN-GP etc.). SpectralNorm (code paper) is a very popular and recent normalization technique for the discriminator.

There are a number of additional tricks to make GANs work like label smoothing and flipping, different update rates for the discriminator and generators (as in BigGAN for instance). I suggest you have a look at this nice repo of (somewhat seasoned) tricks: ganhacks.


Does this hyperparameter optimisation approach yield the optimal hyperparameters? Say I have a ML model which is not very costly to train. It has around say 5 hyperparameters.

One way to select best hyperparameters would be to keep all the other hyperparamaters fixed and train the model by changing only one hyperparameter within a certain range. For the sake of mathematical convenience, we assume for the hyperparameter $h^1$, keeping all other hyperparameters fixed to their initial values, the model performs best when  $h^1_{low} < h^1 < h^1_{high}$ (which we found out by running the model on a huge range of $h^1$). Now we, fix $h^1$ to one of the best values and tune $h^2$ the same way, where $h^1$ is chosen and the rest of the hyperparameters are again fixed on their initial values.

My question is: Does this method find the best hyperparameter choices for the model? I know if the hyperparameters are independent, then this definitely does find the best solution, but in a general case, what is the general theory around this? (NOTE: I am not asking about the problem of choosing hyperparamaters, but I am asking about the aforementioned approach of choosing hyperparameters)

After you've computed $h^{1}_{optimal}$ the only thing you can be sure is that this is the best (assuming constrained case) value of $h^1$ (with respect to some model performance metric) given your initial values for $h^2, ..., h^n$. If you change a bit any of $h^2, ..., h^n$ you're no longer certain that the value $h^1$ you found is the optimal one. So yes, the key here is the assumption about the independence.


What is the relation between self-taught learning and transfer learning? I am new to transfer learning and I start by reading A Survey on Transfer Learning, and it stated the following:

according to different situations of labeled and unlabeled data in the source domain, we can
further categorize the inductive transfer learning setting into two cases:
case $(a)$ (It is irrelevant to my question).
case $(b): $ No labeled data in the source domain are
available. In this case, the inductive transfer
learning setting is similar to the self-taught
learning setting, which is first proposed by Raina
et al. [22]. In the self-taught learning setting, the
label spaces between the source and target
domains may be different, which implies the
side information of the source domain cannot be
used directly. Thus, it’s similar to the inductive
transfer learning setting where the labeled data
in the source domain are unavailable.

From that, I understand that self-taught learning is inductive transfer learning.
But I opened the paper of self-taught learning that was mentioned (i.e paper by Raina
et al. [22].), and It stated the following in the introduction:

Because
self-taught learning places significantly fewer restrictions on
the type of unlabeled data, in many practical applications
(such as image, audio or text classification) it is much easier
to apply than typical semi-supervised learning or transfer learning
methods.

And here it looks like transfer learning is different from self-taught learning.
So what is the right relation between them?

After a lot of searches, I think self-taught learning is a Transfer learning category, I think when Self-taught learning paper published (2007), there isn't any good survey on transfer learning, and as seen by high citation of the paper of Pan, his paper (which published in 2009) describes transfer learning in a clear way that did not exist before it.
Also, it is reasonable to consider Self-Taught learning a transfer learning category because he actually transfers the knowledge learned from unlabelled data to use it in the supervised task that we want to do (there is no need for the unlabeled data (that used for training) to follow the same class labels or generative distribution as the labelled data that will be used for the supervised task).
If someone could find something wrong with my answer or there is something missing, then please tell me.


What is the motivation behind using a deterministic policy? What is the motivation behind using a deterministic policy? Given that the environment is uncertain, it seems stochastic policy makes more sense.

You're right! Behaving according to a deterministic policy while still learning would be a terrible idea in most cases (with the exception of environments that "do the exploring for you"; see comments). But deterministic policies are learned off-policy. That is, the experience used to learn the deterministic policy is gathered by behaving according to a stochastic behavior policy.

Under some reasonable assumptions--like that the environment is fully-observed and is stationary--an optimal deterministic policy always exists. The proof can be found in chapter 6 of "Markov Decision Process -- Discrete Stochastic Dynamic Programming" by Martin L. Puterman. The same cannot be said for stochastic polices. For this kind of environment (even if it's stochastic) an optimal policy is hardly ever stochastic.

So, a motivation for wanting to learn a deterministic policy is often because we know that there is an optimal deterministic policy.

It's possible your question was also tangentially about off-policy learning. "Why learn a deterministic policy directly (off-policy) when we can just use something like decaying $\epsilon$-greedy?" Briefly, off-policy learning is very powerful and general. It's necessary in any algorithm that uses experience replay, for example. A discussion about the merits of off-policy learning is probably best left to another question, but reading Section 5.5 of Sutton and Barto's RL book should get you started.

Finally, directly learning a deterministic policy could be more computationally efficient if using deterministic policy gradients. In the setting with continuous state and action spaces, the deterministic policy gradient exists and has a simpler expectation than the stochastic policy gradient.

Stochastic policy gradient:

$$\begin{align*}
\nabla_\theta J(\pi_\theta) &= \int_\mathcal{S} \rho^\pi (s) \int_\mathcal{A} \nabla_\theta \pi_\theta (a|s) Q^\pi (s,a) \text{d}a\text{d}s\\
& = \mathbb{E}_{s\sim \rho^\pi, a\sim\pi_\theta}[\nabla_\theta \log \pi_\theta (a|s) Q^\pi (s,a)]
\end{align*}$$

Deterministic policy gradient:
$$\begin{align*}
\nabla_\theta J(\mu_\theta) &= \int_\mathcal{S} \rho^\mu (s) \nabla_\theta \mu_\theta (s) \nabla_a Q^\mu (s,a)|_{a=\mu_\theta (s)}\text{d}s\\
& = \mathbb{E}_{s\sim \rho^\mu}[\nabla_\theta \mu_\theta (s) \nabla_a Q^\mu (s,a)|_{a=\mu_\theta (s)}]
\end{align*}$$

Notice that the expectation in the deterministic policy gradient isn't over the action space. Estimating this expectation would require many fewer samples in the setting of a continuous, high-dimensional action space.

To recap:

Optimal policies are often deterministic, not stochastic
Learning deterministic policies directly (off-policy) is powerful and general
It can also be more efficient if in a continuous, high-dimensional action space


Untrained CNNs as feature extractors? I've heard somewhere that due to their nature of capturing spatial relations, even untrained CNNs can be used as feature extractors? Is this true? Does anyone have any sources regarding this I can look at?

Yes, it has been demonstrated that the main factor for CNNs to work is its architecture, which exploits locality during the feature extraction. A CNN with random weights will do a random partition of the feature space, but still with that spatial prior that works so well, so those random features are OK for classification (and sometimes even better than trained ones, as they don't introduce additional bias).

You can read more in these papers:

D. Ulyanov et al. Deep Image Prior
A. Rosenfeld and J. K. Tsotsos. Intriguing Properties of Randomly Weighted Networks: Generalizing While Learning Next to Nothing.


Is ReLU a non-linear activation function? According to this blog post

  The purpose of an activation function is to add some kind of non-linear property to the function

The sigmoid is typically used as an activation function of a unit of a neural network in order to introduce non-linearity.

Is ReLU a non-linear activation function? And why? If not, then why is it used as an activation function of neural networks?

Short Answer: Yes

Visually:

if you see the image from wikipedia, it shown that ReLU (the blue line) is non-Linear (the line is not straight, it turns in 0). You can also check "visual" definition of linear function in wikipedia:

  "In calculus and related areas, a linear function is a function whose graph is a straight line"

Mathematically:

Linear function of one variable can be defined as:

$ f(x) = ax + b $

If you plot that function in 2D, it will give you a straight line. Then, the form of linear function with multi variables:

$ f(x_1, x_2, ..., x_n) = a_1x_1 + a_2x_2 + ... + a_nx_n + b $

If you again plot that function in the correct dimension it also give you a straight line. And if you that function carefully, it similar with calculation that happen in a neuron. That's why neuron addition and multiplication is a linear function:

$ f(x_1, x_2, ..., x_n) = w_1x_1 + w_2x_2 + ... + w_nx_n + b $

Adding more layer of linear functions doesn't make the function become "complex" for example, if you have $f(x)$ like below and then you put another layer of linear function $g(x)$ on top of it:

$f(x) = ax + b$

$g(x) = cf(x) + d = cax + cb + d$

as the neural network is trained to find the value of $a,b,c,d$, we can group the constant from the formula above, and then rewrite to:

$h(x) = mx + n$

with $m=ca$ and $n=cb+d$. So without non-linear function the layer of neural network is useless, it only give you another "simple" linear function

ReLU formula is a $f(x)=max(0,x)$, it produces non-linearity as you can't write to linear function format. Using this function will give you "complexity" when you add more layer on top of it.


Would convolutional NN recognize patterns in encoded images? I have a set of images that I already trained a CNN to classify successfully. I wonder if it would be possible to encode the images (using XOR in combination with a key of the same length as the image) and train a new net on them.

Thinking logically, the features still exist in the same relation to each other, just in a different form (encoded). Considering that neural networks are incredible at pattern recognition, I assume that it would still be doable.

For people, who cannot imagine how a xor-encoded image would look like:

For a human, it may look like rubbish, but the information is definitely there.

Would love to read your opinion.

First you should give it a try, because anyone's guess could be off, as there isn't really a complete high level analytic model of how neural networks behave on real data. Most results with neural networks are informed by theory, but involve a whole lot of experimental testing.

I suspect your network might at least learn something from the new images, but would struggle to get anything like the same accuracy as without the noise, because the CNN filters rely on being able to detect similar features at different positions. In your scrambled image, there will not be any meaningful and consistent edges/corners etc that a single learned feature detector could learn to match (and therefore present to the next layer).

A fully-connected network would not have this limitation, and would learn just as well on a set of binary features that have been xor'd identically in each position for each example, as it did on the original copy (i.e. only if the picture was 1 bit depth). It would learn less well if each feature was a scaled 8-bit pixel value that was xor'd with the same 8 bit random number in each pixel position, because that would introduce many more non-linear mappings between input and output. Of course a fully-connected network will generally not learn image tasks as well as CNNs in the first place . . . but if it could learn anything useful at all for your image problem, then it will probably out-perform CNNs after the scrambling effect.

As a CNN usually has a few fully-connected layers, then it may be possible to get something from your scrambled images.

  Thinking logically, the features still exist in the same relation to each other, just in a different form (encoded)

In terms of being recognisable in the way that a CNN filter extracts them, then the features do not exist. That is a problem.


Is it possible to do K-nearest-neighbours before training DNN The following X-shape alternated pattern can be separated quite well and super fast by K-nearest Neighbour algorithm (go to https://ml-playground.com to test it):

However, DNN seems to face great struggles to separate that X-shape alternated data. Is it possible to do K-nearest before DNN, ie. set the DNN weights somehow to simulate the result of K-nearest before doing DNN training?
Another place to test the X-shape alternated data: https://cs.stanford.edu/people/karpathy/convnetjs/demo/classify2d.html

There are two factors that will change the ability of a deep neural network to fit a given dataset: either you need more data, or a deeper and wider network. Since the pattern is only 2-d, it can likely be approximated by some sort of simple periodic function. A DNN can approximate periodic functions pretty well, so the issue is probably that you don't have enough data.

If you have an apriori belief that the pattern is well approximated by K-nearest neighbors, then you could do the following:

Fit a K-NN model to the data.
Generate $N$ new points uniformly at random from the input space.
Label the $N$ new points using the K-NN model.
Fit your DNN to the original dataset, plus the $N$ new points.