How to predict the best from a set of messages - best practice Suppose I have a set of messages A,B,C,D and I want to produce the best message for a website user at a given time.
For training I plan to show random users a random single message [A/B/C/D] and fill these columns (i'm simplifying the data for illustration)

converted before
funnel state (e.g awareness, search, decision)
number of page views
message shown [A-D]
Time to convert (this will be updated later if there is a conversion)

I want to predict what is the best message to show to a specific user in order to maximise the chance of conversion (=min time to convert).
I'm not sure how to represent this for training and inference. Its not a simple prediction like predicting one of the given data points.
One option is to run prediction of time to buy for each of the messages but
1- its not efficient
2- It will prefer messages that are shown closer to purchase time regardless if they fit the current user time.

One way you can definitely approach the problem is by using (Deep) Reinforcement Learning (DRL).
YouTube is actually using DRL as well to suggest videos to users in order to maximize users' engagement with their website. For more information (and further references to papers explaining how other major companies implement their recommendation systems), see this paper. Just as a bit of motivation.
Other research into that direction could be found here.
Actually, there are different DRL algorithms available and each might be suitable for approaching the problem you described above from a slightly different angle.
The way how I would roughly approach your problem is as follows:
As I understand it, the goal is the following.
You want to show either of four messages to a user (only one at a time) and always display the message, which is expected to reduce some metric (=conversion time), to the user.
In that case, an DRL algorithm, or agent, could directly be trained on minimizing the conversion time without having to explicitly produce conversion time estimates per message & user. That might make phrasing the problem at hand much easier (in terms of modelling the learning task).
The outcome of training an DRL agent consists of a so-called optimal policy network, which dictates the agent which message to display to a given user, upon observing the provided user data, such that conversion time gets minimized for that user. The aforementioned network is a simple artificial Neural Network (NN) or Recurrent NN (RNN).
Training the DRL agent will consist of two steps being repeated many times in alternating order.
One step will include the sampling/generation of training data.
For this step, the algorithm (initially being untrained) will be applied to the problem at hand and predict messages for given users. Then, (in addition to the provided user data that was fed as input to the agent) each user's response (i.e. the conversion time) is recorded. This can later be used as the reward that the agent receives for having selected the selected message given the provided user data. Here, a low conversion time translates to a high reward.
In the second step, the agent's policy network will be trained in order to make the agent's predictions more accurate in the next round of generating training data. Here, the data recorded during the previous step will be used.
How the policy network is optimized largely depends on which DRL algorithm you choose. The range of different methods varies vastly. Some algorithms try to estimate utilities (i.e. measures of goodness) per action given a certain state (here, state = provided user data used to generate a prediction). In this case, an action would be choosing message A or choosing message B etc. A popular algorithm implementing this procedure is Deep Q-Learning.
However, if you rather want to predict probabilities per action, then Proximal Policy Optimization might rather be what you are looking for.
Upon convergence, i.e. stabilization of the goal metric (=convergence time per user), the algorithm has arrived at its optimal policy (ideally speaking).
The only drawback with this approach is that DRL usually requires quite a lot of training. But maybe you are lucky and pre-trained recommendation system models exist.
If there is still anything unclear, feel free to ask in the comments.


What is the difference between encoders and auto-encoders? How are the layers in a encoder connected across the network for normal encoders and auto-encoders? In general, what is the difference between encoders and auto-encoders?

Theory

Encoder

In general, an Encoder is a mapping $f : X \rightarrow Y $ with $X$ Input Space and $Y$ Code Space
In case of Neural Networks, it is a Generative Model hence a function which is able to compute a Representation out of some input (like GAN)

The point is: how would you train such an encoder network ?

The general answer is: it depends on what you want your code to be and ultimately depends on what kind of problem the NN has to solve, so let's pick one

Signal Compression

The goal is to learn a compressed representation for your input that allows to reconstruct the original input minimizing the loss of information

In this case hence you want the dimensionality of $Y$ to be lower than the dimensionality $X$ which in the NN case means the code space will be represented by less neurons than the input space

Autoencoder

Focusing on the Signal Compression problem, what we want to build is a system which is able to

take a given signal with size N bytes
compress it into another signal with size M<N bytes
reconstruct the original signal, starting from the compressed representation, as good as possible

To be able to achiebve this goal, we need basically 2 components

an Encoder which compresses its input, performing the $f : X \rightarrow Y$ mapping
a Decoder which decompresses its input, performing the $f: Y \rightarrow X$ mapping

We can approach this problem with the Neural Network Framework, defining an Encoder NN and a Decoder NN and training them

It is important to observe this kind of problem can be effectively approached with the convenient learning strategy of unsupervised learning : there is no need to spend any human work (expensive) to build a supervision signal as the original input can be used for this purpose

This means we have to build a NN which operates essentially between 2 spaces

the $X$ Input Space
the $Y$ Latent or Compressed Space

The general idea behind the training is to make a certain input go along the encoder + decoder pipeline and then compare the reconstruction result with the original input with some kind of loss function

To define this idea a bit more formally

The final autoencoder mapping is $f : X \rightarrow Y \rightarrow X$ with

the $x$ input
the $y$ encoded input or latent representation of the input
the $\hat x$ reconstructed input

Eventually you will get an architecture similar to

You can train this architecture in an unsupervised way, using a loss function like $f : X \times X \rightarrow \mathbb{R}$ so that $f(x, \hat x)$ is the loss associated to the $\hat x$ reconstruction compared with the $x$ input which is also the ideal result

Code

Now let's add a simple example in Keras related to the MNIST Dataset

from keras.layers import Input, Dense
from keras.models import Model

# Defines spaces sizes

## MNIST 28x28 Input
space_in_size = 28*28

## Latent Space
space_compressed_size = 32

# Defines the Input Tensor
in_img = Input(shape=(space_in_size,))

encoder = Dense(space_compressed_size, activation='relu')(in_img)

decoder = Dense(space_in_size, activation='sigmoid')(encoder)

autoencoder = Model(in_img, decoder)

autoencoder.compile(optimizer='adam', loss='binary_crossentropy')


How to embed/deploy an arbitrary machine learning model on microcontrollers? Say I have a machine learning model trained on a laptop and I then want to embed/deploy the model on a microcontroller. How can I do this?
I know that TensorflowLite Micro generates a C header to be added in the project and then be embedded, but every example I read shows how it is done with neural networks, which seems legit as TensorFlow is primarily used for deep learning.
But how can I do the same with any type of model, like the ones there is in scikit-learn? So, I'm not interested in necessarily doing this with TensorflowLite Micro, but I'm interested in the general approach to solve this problem.

There are a few possible approaches to deploying a ML model to a microcontroller.
The main limiting factor to deployment on microcontollers is that ML models are usually a representation of a set of parameters that are intended to be used as input to a prediction algorithm alongside a new datapoint. Most such models assume the presence of an accompanying library that implements the algorithm in question. However, a microcrontoller may use an exotic chip architecture, or have very several or unusual resource constraints that prevent these standard libraries from being deployed easily.
Presumably you will already have some way to get input into your microcontroller and to program it in order to call some function that you can write. If not, you will need to first figure out how to do that, and the right methods depend on your microcontroller. A common approach is to write assembly code or code in a very limited subset of C or another language. An alternative is to find a distribution of an interpreter for another language (e.g. Java, Python) that has been compiled to work on your chip. Either way, you will need some way to program the chip.
Presuming you can program the chip, you have two fundamental challenges in deploying the model:

Most models are trained with very wide floating point numbers for their parameters. For example, 128-bit numbers may be used. On a standard computing environment, the CPU or GPU will be equipped to perform operations on wide datatypes efficiently. On a microcontroller, you may be limited to 8-bit or 16-bit integers. To work with your model parameters in an environment like this, you will need to either make the parameters smaller (usually by rounding them to fit in a much smaller numeric format, a process called "quantization"), or by finding or writing software that can simulate the operations you want (probably addition and multiplication) on a large datatype that is represented as a collection of smaller datatypes. The first approach may make the model perform poorly. The second may make model prediction very slow.

You need an implementation of the algorithm. Some algorithms like linear regression, linear discriminant analysis, or even decision trees are extremely easy to implement prediction for, and may require only addition, multiplication, and/or comparison. You might be able to write these yourself in a simple subset of C, or even in assembly (for example, prediction with linear regression should be just a simple loop). Other algorithms, like deep neural networks, may contain more complex operations, and may contain many such operations performed in complicated sequences. For these, you generally will need to find an distribution of a library that implements the algorithms, or compile one yourself. Compiling one yourself will require setting up a build toolchain for your specific microcontroller, and can be quite involved.


Why does regular Q-learning (and DQN) overestimate the Q values? The motivation for the introduction of double DQN (and double Q-learning) is that the regular Q-learning (or DQN) can overestimate the Q value, but is there a brief explanation as to why it is overestimated?

The overestimation comes from the random initialisation of your Q-value estimates. Obviously these will not be perfect (if they were then we wouldn't need to learn the true Q-values!). In many value based reinforcement learning methods such as SARSA or Q-learning the algorithms involve a $\max$ operator in the construction of the target policy. The most obvious case is, as you mentioned, Q-learning. The learning update is
$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$
The Q-function for the state-action tuple we are considering is shifted towards the max Q-function at the next state where the $\max$ is taken with respect to the actions.
Now, as mentioned our initial estimates of the Q-values are initialised randomly. This naturally leads to incorrect values. The consequence of this is that when we calculate $\max_aQ(s', a)$ we could be choosing values that are grossly overestimated.
As Q-learning (in the tabular case) is guaranteed to converge (under some mild assumptions) so the main consequence of the overestimation bias is that is severely slows down convergence. This of course can be overcome with Double Q-learning.
The answer above is for the tabular Q-Learning case. The idea is the same for the the Deep Q-Learning, except note that Deep Q-learning has no convergence guarantees (when using a NN as the function approximator) and so the overestimation bias is more of a problem as it can mean the parameters of the network get stuck in sub-optimal values.
As someone asked in the comments about always initialising the values to be very low numbers, this would not really work.
Consider the following MDP taken from Sutton and Barto:
We start in state A, from which we can either go right with reward 0 leading to a terminal state or go left with reward 0 to state B. From state B we can take, say, 100 different actions, all of which lead to a terminal state and have reward drawn from a Normal distribution with mean -0.1 and variance 1.
Now, clearly the optimal action from state A is to go right. However, when we go left and take an action in state B there is an (almost) 0.5 probability of getting a reward bigger than 0. Now, recall that the Q-value is shifted towards $r(s, a) + \max_a Q(s', a)$; because of the stochastic rewards when transitioning out of state B and the fact that we will likely see a positive reward the $\max_a Q(s', a)$ will be positive.
This means that when we take the left action the Q-value (Q(A, left)) is shifted towards a positive value, meaning that when we are in state A the value of moving left will be higher than moving right (which will gradually be being shifted towards the true value of 0) and so when following the $\epsilon$-greedy policy the greedy action will be to go left when in fact this is sub-optimal.
Now, of course, we know that the true Q-values will eventually converge but if we do have, say, 100 actions then you can probably see that the time it will take for the Q-values to converge to the true value will potentially be a long time as we would have to keep choosing all the overestimated values until we had convergence.


What is the difference between a learning algorithm and a hypothesis? What's the distinction between a learning algorithm $A$ and a hypothesis $f$?
I'm looking for a few concrete examples, if possible.
For example, would the decision tree and random forest be considered two different learning algorithms? Would a shallow neural network (that ends up learning a linear function) and a linear regression model, both of which use gradient descent to learn parameters, be considered different learning algorithms?
Anyway, from what I understand, one way to vary the hypothesis $f$ would be to change the parameter values, maybe even the hyper-parameter values of, say, a decision tree. Are there other ways of varying $f$? And how can we vary $A$?

In computational learning theory, a learning algorithm (or learner) $A$ is an algorithm that chooses a hypothesis (which is a function) $h: \mathcal{X} \rightarrow \mathcal{Y}$, where $\mathcal{X}$ is the input space and $\mathcal{Y}$ is the target space, from the hypothesis space $H$.
For example, consider the task of image classification (e.g. MNIST). You can train, with gradient descent, a neural network to classify the images. In this case, gradient descent is the learner $A$, the space of all possible neural networks that gradient descent considers is the hypothesis space $H$ (so each combination of parameters of the neural network represents a specific hypothesis), $\mathcal{X}$ is the space of images that you want to classify, $\mathcal{Y}$ is the space of all possible classes and the final trained neural network is the hypothesis $h$ chosen by the learner $A$.

For example, would the decision tree and random forest be considered two different learning algorithms?

The decision tree and random forest are not learning algorithms. A specific decision tree or random forest is a hypothesis (i.e. function of the form as defined above).
In the context of decision trees, the ID3 algorithm (a decision tree algorithm that can be used to construct the decision tree, i.e. the hypothesis), is an example of a learning algorithm (aka learner).
The space of all trees that the learner considers is the hypothesis space/class.

Would a shallow neural network (that ends up learning a linear function) and a linear regression model, both of which use gradient descent to learn parameters, be considered different learning algorithms?

The same can be said here. A specific neural network or linear regression model (i.e. a line) corresponds to a specific hypothesis. The set of all neural networks (or lines, in the case of linear regression) that you consider corresponds to the hypothesis class.

Anyway, from what I understand, one way to vary the hypothesis $f$ would be to change the parameter values, maybe even the hyper-parameter values of, say, a decision tree.

If you consider a neural network (or decision tree) model, with $N$ parameters $\mathbf{\theta} = [\theta_i, \dots \theta_N]$, then a specific combination of these parameters corresponds to a specific hypothesis. If you change the values of these parameters, you also automatically change the hypothesis. If you change the hyperparameters (such as the number of neurons in a specific layer), however, you will be changing the hypothesis class, so the set of hypotheses that you consider.

Are there other ways of varying $f$?

Off the top of my head, only by changing the parameters, you change the hypothesis.

And how can we vary $A$?

Let's consider gradient descent as the learning algorithm. In this case, to change the learner, you could change, for example, the learning rate.


Does elitism cause premature convergence in genetic algorithms? I have a genetic algorithm which is working fairly well. It's got all the standard operators, including initial random population, crossover ratio, mutation rate, degree of mutation, etc.
This works fairly well, and I have tuned and optimized the hyperparameters as much as possible, including some adaptive variants. The one thing that ruins the results EVERY TIME is when I implement elitism. It does not seem to matter if I include 1 elite, or a certain percentage of elites. I have tried 1% through 10%, tried a decay variable so that elites would only survive a certain number of generations, and numerous other tactics. Every single time I add elitism, the solution gets stuck in a local optimum so deeply that there is no escape.
Most of the literature recommends to have elites, but the elites ruin my GA every single time, without fail.
Ideas?

There are many ideas to escape from local optima in GA. One solution is selecting the population for the next iteration based on the probability that is defined based on the individual score. In that case, you have a chance to select a bad score individual to escape from the local optima.
Another efficient solution is playing with the mutation rate to get rid of local optima. In that way, you can increase the rate smoothly, to find a proper rate.


Can rule induction be considered a way to "hybridize" probabilistic / statistical approaches and symbolic approaches? In years past, GOFAI (Good Old Fashioned AI) was heavily based on "rules" and symbolic computation based on rules.  Unfortunately, that approach ran into stumbling blocks, and the world moved heavily towards statistical/probabilistic approaches leading to the current wave of interest in "machine learning".

It seems though, that the symbolic/rule-based approach probably still has application. So, could one "learn" rules using a probabilistic rule induction method, and then layer symbolic computation on top? If so, how could the whole process be made truly two-way, so that something "learned" from processing rules, can be fed back into how the system learns rules?

Sure! This is a somewhat hot area right now.

There are lots of ways to do it.

Probably the main line of research is with Bayesian Networks (1980's) and Casual Networks (1990's). These are basically rule-based systems for reasoning probabilistically. They rely on a user-designed model, which corresponds well to rules (e.g. when blood pressure is high, then heart attack rates are elevated), but provide a robust way to reason about uncertainties in the presence of these rules. Contrast this with a pure learning approach, like a decision tree or a neural network, which tends to rely less on rules. Modern research in this area focuses on learning the structure of the network (which corresponds to the learning probabilistic rules) from data.

While it's possible to learn rules from data and then do symbolic reasoning atop them using other techniques (e.g. rule induction), this approach runs into the same problems that plague the learning of the structure of Bayesian networks: when is correlation causation? Causal Diagrams are the only good tool for answering this question, but my impression is that inferring their structure automatically is still an open question.


Learning an arbitrary function using a feedforward net I would like to get a simple example running in matlab that will use a neural net to learn an arbitrary function from input output data (basically model identification) and then be able to approximate that function from just the input data. As means of training this net I have implemented a simple back propagation algorithm in matlab but I was not able to get anywhere close to satisfactory results. I would like to know what I may be doing wrong and also what approach I may use instead.

The goal is to have the network represent an identified function f(x) which takes a series x as input and outputs the learned mapping from x -> y.

Here is the GNU octave code I have so far:

pkg load control signal

function r = sigmoid(z)
    r = 1 ./ (1 + exp(-z));
end

function r = linear(z)
    r = z;
end

function r = grad_sigmoid(z)
    r = sigmoid(z) .* (1 - sigmoid(z));
end

function r = grad_linear(z)
    r = 1;
end

function r = grad_tanh(z)
    r = 1 - tanh(z) .^ 2;
end

function nn = nn_init(n_input, n_hidden1, n_hidden2, n_output)
    nn.W2 = (rand(n_input, n_hidden1) * 2 - 1)'
    nn.W3 = (rand(n_hidden1, n_hidden2) * 2 - 1)'
    nn.W4 = (rand(n_hidden2, n_output) * 2 - 1)'
    nn.lambda = 0.005;
end

function nn = nn_train(nn_in, state, action)
    nn = nn_in;

    [out, nn] = nn_eval(nn, state);

    d4 = (nn.a4 - action) .* grad_linear(nn.W4 * nn.a3);
    d3 = (nn.W4' * d4) .* grad_tanh(nn.W3 * nn.a2);
    d2 = (nn.W3' * d3) .* grad_tanh(nn.W2 * nn.a1);

    nn.W4 -= nn.lambda * (d4 * nn.a3');
    nn.W3 -= nn.lambda * (d3 * nn.a2');
    nn.W2 -= nn.lambda * (d2 * nn.a1');
end

function [out,nn] = nn_eval(nn_in, state)
    nn = nn_in;

    nn.z1 = state;
    nn.a1 = nn.z1;

    nn.a2 = tanh(nn.W2 * nn.a1);
    nn.a3 = tanh(nn.W3 * nn.a2);
    nn.a4 = linear(nn.W4 * nn.a3);

    out = nn.a4;
end

nn = nn_init(1, 100, 100, 1);
t = 1:0.1:3.14*10;
input = t;
output = sin(input);
learned = zeros(1, length(output));

for j = 1:500
    for i = 1:length(input)
        nn = nn_train(nn, [input(i)], [output(i)]);
    end
    j
end

for i = 1:length(input)
    learned(i) = nn_eval(nn, [input(i)]);
end

plot(t, output, 'g', t, learned, 'b');

pause

Here is the result:

The result is not even close to where I want it to be. Has it got something to do with my implementation of back propagation?

What changes do I need to do to the code to get a better approximation going?

You need to scale the input. Neural networks work best with a limited input domain, and train badly when it is exceeded.

For statistical data, you would typically scale your input to have mean 0, standard deviation 1.

Here, you will be better off fitting the input to roughly -1 to 1.

Up to you where you scale the values, but usually this is done outside of the NN code. So I would do something like:

nn_input = (t - 15)/15

And then use nn_input in the training and evaluation loops. As you are putting these directly into a sorted array for plotting, you won't need to do any further re-mapping back or maintain a conversion function. However, in the more common case of arbitrary inputs, you would need to store the conversion factors somewhere (in this case just hardcoded as a function perhaps) in order to make use of the trained NN.

Another thing that may help is shuffling your input/output data pairs during training to remove correlation between sequence of input pairs.


Precise description of one-shot learning I am working on classifying the Omniglot dataset, and the different papers dealing with this topic describe the problem as one-shot learning (classification). I would like to nail down a precise description of what counts as one-shot learning.
It's clear to me that in one-shot classification, a model tries to classify an input into one of $C$ classes by comparing it to exactly one example from each of the $C$ classes.
What I want to understand is:

Is it necessary that the model has never seen the input and the target examples before, for the problem to be called one-shot?

Goodfellow et. al. describe one-shot learning as an extreme case transfer learning where only one labeled example of the transfer task is presented. So, it means they are considering the training process as a kind of continuous transfer learning? What has the model learned earlier, that is being transferred?

The model has learnt the "features" for the type of inputs, eg. faces.
For the problem to be called one-shot, it needs to also correctly classify/compare any new samples. For example, in face recognition application, any new person's images should also result a positive for their own image and negative for any other seen or unseen image.

Since we are using euclidean distance of the final feature layer and not performing any final classification, we can say we are using the weights of a pretrained network and computing final value using that(distance), thus transfer learning. There is no backprop in this, but what you want to do with the embeddings, such as learning a threshold function can be considered learning.


Is intelligence limited to thoughts it is able to associate words with? It appears to me that the thoughts in our heads, or at least mine, are a result of the language they know. I do not have any thought that is not a consequence of the information that is contained within the language I know. I have thoughts that occur as the words we use in language and are particular to my voice  The structure of that language forms constraints as to the depth of thought that my mind can possibly come up with as far as I can perceive.
Is intelligence limited to thoughts it is able to associate words with, since the mind's language is a result of a recursive association of words associated with those thoughts? Is there a limit of conception bound by a language, which is limited by its dictation? If so, there would also be a limit upon the perception of that so-called intelligence.
Consequently, given that artificial intelligence systems are created by humans, aren't they limited by our language and knowledge of it?

First thing we were taught in AI:
Humans didn't create airplanes by studying and mimicing birds, they studied aerodynamics and physics.
Although difficult to articulate I've had very similar thought patterns to yours when I was thinking about AI and further I watched very closely the development of my child from being a newborn to where he is now, a year and a bit old.  The human brain is far more complex than what we'll understand, it would take a multi-discipline team effort to even scratch the surface.  So to create a human brain-like thought process and try to put it into a formal language box would be impossible.
I think the breakthrough in AI isn't going to be someone putting together multiple complex algorithms or even a fancy NN running on a supercomputer.  It's going to be something we haven't figured out yet.
Still, fun to think about...  I'd say it's more of a philosophical question than an AI one though...
Just my humble opinion.


Can the agent wait until the end of the episode to determine the reward in SARSA? From Sutton and Barto's book Reinforcement Learning (Adaptive Computation and Machine Learning series) (p. 99), the following definition for first-visit MC prediction, for estimating $V \sim V_\pi$ is given:

Is determining the reward for each action a requirement of SARSA? Can the agent wait until the end of the episode to determine the reward?

For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.

Does this mean then that depending on the task it is not always possible to determine reward at time step $t$, and the agent must wait until the end of an episode? If the agent does not evaluate reward until the end of an episode, is the algorithm still SARSA?

There are a couple of things to break down here.

The first thing is to correct this:

  For example, the reward for the game tic-tac-toe is decided at the end of the episode, when the player wins, loses, or draws the match. The reward is not available at each step $t$.

In a Markov Decision Process (MDP), there is always an immediate reward for each time $t$ from $t=1$ to $t=T$ (terminal state). This is the reward distribution that the algorithms refer to as $R_t$.

It does not matter if nearly all the rewards are $0$. That is still a reward value, even if it is not an interesting or informative one. Some environments will have non-zero rewards on nearly all time steps. Some environments might have zero rewards for every transition apart from one or two important exceptions that define the goal of the agent.

So in tic-tac-toe, if the game has not ended, the reward will be $0$ because neither player has won or lost, and obtaining a win is a learning objective. If you use $0$ reward value for all incomplete time steps in tic-tac-toe, and SARSA algorithm as written from Sutton & Barto, then it will work as expected. You don't need to wait until the end of the episode, and the algorithm will still learn to predict values of moves despite experiencing many $r_t = 0$ during start and middle of the game.

You show the MC prediction algorithm, which does wait until the end of each episode until calculating estimated values, using the experienced return.

I think one of the things that you might want to review is the difference between immediate reward following a timestep (noted $R_{t+1}$) and return (noted $G_t$). There is a relationship between the two $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$. All the value based methods, such as MC prediction, or SARSA, are ways to estimate the expected return $\mathbb{E}_{\pi}[G_t]$ given some context, such as the state or state and action at time $t$.

Given that, this should answer your other questions.

  Is determining the reward for each action a requirement of SARSA?

It is a general requirement for MDPs, and is expected by all solvers. However, a default of $0$ is fine, if that's how the environment works. The reinforcement learning (RL) algorithms can all cope with delays to important reward values (such as those from winning or losing a game). Bigger delays - e.g. thousands of $0$ reward steps between more meaningful values - are often associated with harder problems to solve, so the simpler algorithms might not be practical. But they all cope in theory given enough experience.

  Can the agent wait until the end of the episode to determine the reward?

No, you should always be able calulate an immediate reward value $r_{t+1}$ after taking each action $a_t$ from state $s_t$.

However, it is OK in general to wait until you have summed up more of those rewards (e.g. $r_{t+1}$ to $r_{t+n}$) before making an estimate of the return $g_t$ to update a value estimate. Single step SARSA (sometimes called SARSA(0)) does not wait - it makes update steps using a single immediate reward value. However, other agent types including Monte Carlo (MC), and some variants of SARSA, can and do wait - sometimes just for some steps, sometimes until the end of each episode.

It is a choice you can make when designing agents, there are consequences. Waiting until end of the episode (as in MC) means you have unbiased estimates of value, but takes longer, and leads to higher variability in updates. Using reward values after each step (as in SARSA(0)) means you get to make more frequent updates which may converge fatser, but you start with biased incorrect values.


How to handle extremely 'long' images? After transforming timeseries into an image format, I get a width-height ratio of ~135. Typical image CNN applications involve either square or reasonably-rectangular proportions - whereas mine look nearly like lines:

Example dimensions: (16000, 120, 16) = (width, height, channels).

Are 2D CNNs expected to work well with such aspect ratios? What hyperparameters are appropriate - namely, in Keras/TF terms, strides, kernel_size (is 'unequal' preferred, e.g. strides=(16, 1))? Relevant publications would help.

Clarification: width == timesteps. The images are obtained via a transform of the timeseries, e.g. Short-time Fourier Transform. channels are the original channels. height is the result of the transform, e.g. frequency information. The task is binary classification of EEG data (w/ sigmoid output).

Relevant thread

I had recently used a slightly unorthodox method to process such images, which involved using RNNs.

Assume the image dimensions to be (16000, 120, 16) = (width, height, channels), as in the question.

Apply a 2D convolution (or multiple such convolutions) of shape(1, k, c),
such that the output of the convolutions becomes (16000, 1, c). So if you only use a single convolutional layer, k=120.

Then, squeeze the extra dimension, to get the shape (16000, c).

The problem has now been transformed back into a sequence problem! You can use RNN variants for further processing.


How to combine backpropagation in neural nets and reinforcement learning? I have followed a course on machine learning, where we learned about the gradient descent (GD) and back-propagation (BP) algorithms, which can be used to update the weights of neural networks, and reinforcement learning, in particular, Q-learning. I implemented these concepts separately.
Now, I was thinking about using a neural network to approximate the Q-function, $Q(s, a)$, but I don't really know how to design the neural network and how to use back-propagation to update the weights of this neural network (NN).

What should the inputs and outputs of this NN be?

How can I use GD and BP to update the weights of such an NN? Or should I use a different algorithm to update the weights?

Gradient descent and back-propagation
In deep learning, gradient descent (GD) and back-propagation (BP) are used to update the weights of the neural network.
In reinforcement learning, one could map (state, action)-pairs to Q-values with a neural network. Then GD and BP can be used to update the weights of this neural network.
How to design the neural network?
In this context, a neural network can be designed in different ways. A few are listed below:

The state and action are concatenated and fed to the neural network. The neural network is trained to return a single Q-value belonging to the previously mentioned state and action.

For each action, there is a neural network that provides the Q-value given a state. This is not desirable when a lot of actions exist.

Another option is to construct a neural network that accepts as input the state. The output layer consists of $K$-units where $K$ is the number of possible actions. Each output unit is trained to return the Q-value for a particular action.

Q-learning update rule
This is the Q-learning update rule

So, we choose an action $a_t$ (for example, with $\epsilon$-greedy behavior policy) in the state $s_t$. Once the action $a_t$ has been taken, we end up in a new state $s_{t+1}$ and receive a reward $r_{t+1}$ associated with it. To perform the update, we also need to choose the Q-value in $s_{t+1}$ associated with the action $a$, i.e. $\max _{a} Q\left(s_{t+1}, a\right)$. Here, $\gamma$ is the discount factor and $\alpha$ is the learning rate.
Back-propagation and Q-learning
If we use a neural network to map states (or state-action pairs) to Q-values, we can use a similar update rule, but we use GD and BP to update the weights of this neural network.
Here's a possible implementation of a function that would update the weights of such a neural network.
def update(self, old_state, old_action, new_state,
  reward, isFinalState = False):

  # The neural network has a learning rate associated with it.
  # It is advised not to use two learning rates
  learningRate = 1

  # Obtain the old value
  old_Q = self.getQ(old_state, old_action)

  # Obtain the max Q-value
  new_Q = -1000000
  action = 0
  for a in self.action_set:
    q_val = self.getQ(new_state, a)
    if (q_val > new_Q):
      new_Q = q_val
      action = a

  # In the final state there is no action to be chosen
  if isFinalState:
    diff = learningRate * (reward - old_Q)
  else:
    diff = learningRate * (reward + self.discount * new_Q - old_Q)

  # Compute the target
  target = old_Q + diff

  # Update the Q-value using backpropagation
  self.updateQ(action, old_state, target)

In the pseudocode and in the Q-learning update formula above, you can see the discount factor $\gamma$. This simply denotes whether we are interested in an immediate reward or a more rewarding and enduring reward later on. This value is often set to 0.9.


Which predictive algorithm can be used to predict a number given other numbers? I am currently searching for a supervised learning algorithm that can be used to predict the output given a large enough training set.

Here's a simple example. Suppose the training dataset is {[A=1, B=330, C=1358.238902], result=234.244378} and the test dataset {[A=893, B=34, C=293], result=?}

My intention is to predict ? using the input values and result given in the training dataset.

What algorithm would be effective for this problem given the wide range of my input/output values? Would this require some sort of regression algorithm?

Impossible to solve until you define an error measurement ( by example $|R-R'|$ or $(R-R')^2$ ) and how this error changes when A, B and C change.
Extreme example: assume $R()$ is random (unrelated to A, B, C values) but static (always same $R(A,B,C)$ for same values of A,B,C). Given some values of A, B, C, you can only answer the value of $R(A,B,C)$ when A,B,C was in the training set. $R(A,B,C)$ is undefined and no predictable when A,B,C was not in the training set.
Moreover, improvements can be done if $R()$ has some properties, by example, if it is possible to state that $R(A,B,C)=R(B,A,C)$ or that $R(A1,B1,C1)=R(A2,B2,C2)$ if $A1+B1+C1=A2+B2+C2$.


Features Map convolutional neural network I have a question about convolutional neural newtork.

Consider this image: conv example

We have a part of an input matrix and a filter. Ok, now we can do the convolution and the result is a scalar, if it is a large number the future was found otherwise no. So, the features map is a matrix where each number indicates the points where a feature was found. I understood this.
The output of this convolution is a features map (after activation function).
My misunderstanding start here.

The next convolution, will find another feature. I don't understand how this filter, can find a new feature from a representation of where the previous feature was found. The feature maps, output of the first convolution is a rappresentation of indicates only where the features were found.

Shouldn't be the features found instead of a number that indicates how much was found this feature??
How exactly does this work?

Since the kernel size is limited. A feature can encompass more than 3 pixels or say 5 pixels, for that we cannot find it in 1 layer. So by adding 2 layers and having an activation function that is not like a step function which you would prefer, we extend the feature to 5 or 9 pixels. And with n layers, a feature covering 2n+1, or 4n+1 can be seen.

PS. You have some spelling errors. Take your time to frame well. Welcome!


Deep Reinforcement Learning Atari: how does the agent understand motion? Basic deep reinforcement learning methods use as input an image for the current state, do some convolutions on that image, apply some reinforcement learning algorithm and it is solved.
Let us take the game Breakout or Pong as an example. What I do not understand is, how does the agent understand when an object is moving towards it or away from it ? I believe that the action it chooses must be different in these two scenarios and from a single image as input, there is no notion of motion.

In the article Playing Atari with Deep Reinforcement Learning, Mnih et al, 2013, which was a major outbreak in Deep Reinforcement learning (especially in Deep Q learning), they don't feed only the last image to the network. They stack the 4 last images :

For the experiments in this paper, the function φ from algorithm 1
applies this preprocessing to the last 4 frames of a history and stacks
them to produce the input to the Q-function

So they add the motion through sequentiality. From various articles and own coding experiences, this seems to me to be the main common approach. I don't know if other techniques have been implemented.
One thing we could imagine would be to compute the Cross-correlation between a previous frame and the last one, and then feed the cross correlation product to the net.
Another idea would be to train previously a CNN to extract motion features from a sequence of frames, and feed these extracted features to your net. This article (Performing Particle Image Velocimetry using Artificial Neural Networks: a proof-of-concept), Rabault et al, 2017 is an example of a CNN to extract motion features.


What's wrong with getting a dynamic RNN's output at the end of a padded sequence? Would it not even be more helpful? It will have more time to transform the input with the extra zeros padded to the end.

There is nothing wrong in theory. It is reasonable to expect that for some problems it will work worse than taking the immediate answer on the last known part of the sequence, some it will have roughly the same effect, and for others it might result in a better result.

A trained RNN is essentially a learned arbitrary program. If a computer program that processed arrays would get a better result by running more iterations at the end of an array, then so might a RNN. One example that comes to mind is predicting the end point of a trajectory of an observed object, when you have a variable number of observations at the start. A program that simulated each timestep in a simple fashion could well perform better than one that attempted to analyse and project directly from whatever the last observed state was.

On the other hand, you may face some practical problems:

One practical detail of not padding sequences is that it may reduce computation time since the network is run less often.
A padded sequence will only get a gradient to learn from with the last output, after the padding. This could make learning harder than it needs to be with vanishing or exploding gradients (these are more of a problem, the more time steps you need take back through the network in order to assign correct weights due to influence of first input).

The usual way to find out is to try it in an experiment. See which approach does better on a hold-out test set when training with or without padding. Bear in mind that whatever the answer it will not hold in general, but is likely to hold for problems similar to the one you tested with.


Do we have cross-language vector space for word embedding? Do we have cross-language vector space for word embedding?

When measure similarity for apple/Pomme/mela/Lacus/苹果/りんご, they should be the same

If would be great if there's available internet service of neuron network which already be trained by multiple language

You can try to read about MUSE (Multilingual Unsupervised and Supervised Embeddings) by Facebook. You can read it from its Github or this article. They also provide the FastText dictionary format (.vec file) for some languages.

Their original paper shows how it aligns the vector of words from two different languages:


How to calculate the advantage in policy gradient functions? From my understanding of the REINFORCE policy gradient method, we gently nudge the probabilities of actions based on the advantages. More specifically, the positive advantages increase the probabilities, negative advantages reduce the probabilities.

So, how do we compute the advantages given the real discounted rewards (aggregated rewards from the episode) and a policy network that only outputs the probabilities of actions?

First let us note the definition of the advantage function:

$$A(s,a) = Q(s,a) - V(s) \; ,$$

where $Q(s,a)$ is the action-value function and $V(s)$ is the state-value function. In theory you could represent these by two different function approximators, but this would be quite inefficient. However, note that
$$Q(s,a) = \sum_{s',r} \mathbb{P}(s',r|s,a)(r + V(s') = \mathbb{E}[r + V(s')|a,s]\;,$$
so we can actually use a single function approximation, for $V(s)$, to completely represent the advantage function. To optimise this function approximator you would use the returns at each step of the episode as in e.g. the REINFORCE algorithm like you mentioned.


Does the input layer have bias and are there bias neurons? I have seen two different representations of neural networks when it comes to bias. Consider a "simple" neural network, with just an input layer, a hidden layer and an output layer. To compute the value of a neuron in the hidden layer, the weights and neurons from the input layer are multiplied, shifted by a bias and then activated by the activation function. To compute the values in the output layer, you may choose not to have a bias and have an identity activation function on this layer, so that this last calculation is just "scaling".
Is it standard to have a "scaling" layer? You could say that there is a bias associated with each neuron, except those in the input layer correct (and those in the output layer when it is a scaling layer)? Although I suppose you could immediately shift any value you're given. Does the input layer have a bias?
I have seen bias represented as an extra unchanging neuron in each layer (except the last) having value 1, so that the weights associated with the connections from this neuron correspond to the biases of the neurons in the next layer. Is this the standard way of viewing bias? Or is there some other way to interpret what bias is that is more closely described by "a number that is added to the weighted sum before activation"?

The purpose of the input layer is just to conceptually represent the input and, in case it is necessary, define the dimensions of the input that the neural network expects. In fact, some neural networks, such as multi-layer perceptrons, expect a fixed-size input, but not all of them: fully convolutional networks can deal with inputs of different dimensions.
The input layer doesn't contain neurons (although in the diagrams that you will come across they are usually represented as circles, like the neurons, and that's probably why you are confused!), so it also does not contain biases, linear transformations, and non-linearities. In fact, in the context of neural networks, you could define a neuron as some unit/entity that performs a linear or non-linear transformation (to which you can add a bias). Note that the hidden and output layers can contain biases because they contain neurons that perform a linear or non-linear transformation.
However, although I have never seen it (or I don't recall having seen it), I would not exclude the existence of an input layer that transforms or augments the inputs before passing them to the next layer. For example, one could implement a neural network that first scales the input to a certain range, and the input layer could do this, although, in practice, this is typically done by some object/class that does not belong to the neural network (e.g. tf.data.Dataset).


How successfully can convnets detect NSFW images? For example, search engine companies want to classify their image searches into 2 categories (which they already do that) such as: NSFW (nudity, porn, brutality) and safe to view pictures.

How can artificial neural networks achieve that, and at what success rate? Can they be easily mistaken?

The 2015 paper entitled "Applying deep learning to classify pornographic images and videos" applied various types of convnets for detecting pornography. The proposed architecture achieved 94.1% accuracy on the NPDI dataset, which contains 800 videos (400 porn, 200 non-porn "easy" and 200 non-porn "difficult"). More traditional computer vision methods achieved 90.9% accuracy. The proposed architecture also performs very well regarding the ROC curve.

There does not seem to exist any works regarding the other aspects of NSFW yet.


How can I do video classification while taking into account the temporal dependencies of the frames? I need to solve a video classification problem. While looking for solutions, I only found solutions that transform this problem into a series of simpler image classification tasks. However, this method has a downside: we ignore the temporal relationship between the frames.
So, how can I perform video classification, with a CNN, by taking into account the temporal relationships between frames?

Look at spatio-temporal CNNs which extend the image-based CNN in 2D to 3D to handle time.  These are commonly used to detect or classify action in a video.  People have used them to identify specific actions in various sports such as kicking a soccer ball, throwing a baseball or dribbling a basketball.  They have been used to identify fire, smoke, deep fakes, and violence in videos.  Below are some articles to help get started.

Introduction to Video Classification, by Connor Shorten
Are you ready for a Video Classification Challenge? Preparation Guide for Video Classification, by Neha Goel
MiCT-Net for Human Action Recognition in Videos, by Florent Mahoudeau

Source code:

Video Classification
Video Classification Using 3D ResNet


How to let the agent choose how to populate a state space matrix in RL (using python) I have an agent (drone) that has to allocate subchannels for different types of User Equipment.
I have represented the subchannel allocation with a 2-dimentional binary matrix, that is initialized to all zeros as there is no requests at the beginning of the episode.
When the agent chooses an action, it has to choose which subchannels to allocate to which UEs, hence populating the matrix with 1s.
I have no idea how to do it.

I think this question is hinting at the problem of choosing an exploration strategy.
The simplest strategy is to use the so called epsilon-greedy strategy (or $\epsilon$-greedy). This means that you select an action at random $x$ percent of the times that an agent has to select an action. The other times, the agent takes the action that its current policy dictates. Usually, $x$ declines throughout the learning process.
There are many different exploration strategies to choose from, with the aforementioned one being really the most simple one. For getting an impression of how diverse these different approaches to exploration strategies are, please be referred to Google Scholar (searching for "reinforcement learning exploration strategies").


Is there a full and precise formulation of Theorem 1 in the Integrated Gradients paper? Theorem 1 (page 5)  in the paper about Integrated Gradients states that

Integrated gradients is the unique path method that is symmetry-preserving.

What I miss is

A precise formulation of the theorem: in particular, the exact properties that must be satisfied by the function $f$ used in the proof (continuity, differentiability, etc.). Also, should the paths be assumed to be monotonic?

A consistent definition of function $f$ in the proof - note that $f$ is defined inconsistently, e.g. in the region where $x_i<a$ and $x_j>b$, where it is not clear whether its value should be $0$ or $(b-a)^2$.

Point 2 is easy to fix with an appropriate redefinition (e.g. replacing "if $\text{max}(x_i,x_j)\geq 0$" with "else if $\text{max}(x_i,x_j)\geq 0$"). What it is not clear if whether there is a redefinition that:

preserves the properties that have been assumed in the rest of the paper, in particular in Proposition 1 (proving completeness), where the function is assumed to be continuous everywhere, and the set of discontinuous points of each of its partial derivatives along each input dimension has measure zero, and

the function is a constant for $t \notin [t_1,t_2]$.

Does anybody have a precise formulation and full proof of the theorem?

After working on it for a while this is what I got.
Concerning proposition 1 in the paper, a rigorous statement could be the following version of the Gradient Theorem for line integrals:
Proposition 1. (Gradient Theorem for Lipschitz Continuous Functions).
Let $U$ be an open subset of $\mathbb{R}^n$.  If
$F : U \to \mathbb{R}$ is Lipschitz continuous, and
$\gamma : [0,1] \to U$ is a smooth path such that $F$ is
differentiable at $\gamma(t)$ for almost every $t\in [0,1]$, then
$$
    \int_{\gamma} \nabla F(\mathbf{x}) \cdot d\mathbf{x} = F(\gamma(1)) - F(\gamma(0))
    \,.
  $$
I found theorem 1 about symmetry-preserving harder to state rigurously while still fully capturing its intended meaning - this is the best I got:
Theorem 1.
Given $i,j\in \{1,\dots,n\}$, $i\neq j$, real numbers $a<b$, and a
strictly monotonic smooth path $\gamma : [0,1] \to (a,b)^n$
such that $\gamma_i(0)=\gamma_j(0)$ and $\gamma_i(1)=\gamma_j(1)$,
then the following statements are equivalent:
(1) For every $t\in [0,1]$, $\gamma_i(t) = \gamma_j(t)$.
(2) For every function $F : [a,b]^n \to \mathbb{R}$ symmetric
in $x_i$ and $x_j$ and verifying the premises of
proposition 1 with $U=(a,b)^n$ we have
$\int_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x_i} \, dx_i
= \int_{\gamma} \frac{\partial F(\mathbf{x})}{\partial x_j} \,
dx_j$.
Further details and proofs: Symmetry-Preserving Paths in Integrated Gradients


What are the major differences between multi-armed bandits and the other well-known algorithms (DQN, A3C, PPO, etc)? I have studied in the past different algorithms, i.e. DQN, DDQN, REINFORCE, A3C, PPO, TRPO, so on. I am doing an internship this summer where I have to use a multi-armed bandit (MAB). I am a bit confused between MAB and the other above algorithms.
What are the major differences between MAB and REINFORCE, for instance? What are the major differences between MAB and the other well-known algorithms (DQN, A3C, PPO, etc)?
EDIT
The @Kostya's answer is fine, but it would be interested for me to have a deeper answer for that question. I am still a bit confused.
Question: Do we use the Markov Reward formula $$G_t = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$ the same way in a Multi-Armed bandit problem versus a DQN problem?

You should start with the general definition of Reinforcement Learning problem. And what Markov Decision Process is.
DQN, A3C, PPO and REINFORCE are algorithms for solving reinforcement learning problems. These algorithms have their strengths and weaknesses depending on the details of the underlying problem.
Multi-Armed Bandit is not even an algorithm - it is a subclass of reinforcement learning problems, where your environment (usually) doesn't have any state transitions and your actions are just a single choice from (usually) fixed and finite set of choices.
Multi-Armed Bandit is used as an introductory problem to reinforcement learning, because it illustrates some basic concepts in the field: exploration-exploitation tradeoff, policy, target an estimate, learning rate and gradient optimization. All these concepts are basic vocabulary in RL. I recommend reading (and, very importantly, doing all the exercises) the Sutton and Barto book chapter two to get familiarized with it.
Edit: since the answer got popular, I'll address the comments and the question edit.
Being a special simplified subset of Markov Decision Processes, Multi Armed Bandit problems allow deeper theoretical understanding. For example, (as per @NeilSlater comment) the optimal policy would be to always go for the best arm. So it makes sense to introduce "regret" $\rho$ - the difference between a potential optimal reward and the actual collected reward by agent following your strategy:
$$\rho(T) = \mathbb{E}\left[T\mu^* -\sum_{t=1}^T\mu(a_t)\right]$$
One can then study asymptotic behavior of this regret as a function of $T$ and devise strategies with different asymptotic properties. As you can see, the reward here is not discounted ($\gamma=1$) - we usually can study the behavior of it as a function of $T$ without this regularization.
Although, there is one famous result that uses discounted rewards - the Gittins index policy (note, though, that they use $\beta$ instead of $\gamma$ to denote the factor).


How does Atlas from Boston Dynamics have human-like movement? Discussing the video More Parkour Atlas, a friend asked how the robot's movement was so similar to the one from a real human and wondering how this is achieved?
To my knowledge, this is not something the developer "programmed", but instead emerged from the learning algorithm.
Could you provide an overview and some reference on how this is achieved?

Because Boston Dynamics is a private, for-profit, company, we cannot know for sure how they achieve their results. However, we can examine the available public information and make educated guesses.
In the information posted with the video, Boston Dynamics tells us that they use

... an optimization algorithm transforms high-level descriptions of
each maneuver into dynamically-feasible reference motions.  Then Atlas
tracks the motions using a model predictive controller that smoothly
blends from one maneuver to the next.

This sounds like three older AI approaches have been blended together to create the video.
First, they mention using an optimization algorithm to assemble complex motions from "dynamically-feasible reference motions". This sounds like they have first learned, or possibly pre-programmed, a range of simple movements that, on their own, are not very impressive, but that can be composed together into more complex movements. This approach is called Layered Learning, and was pioneered by Peter Stone and Manuela Veloso in the late 1990s. It is widely and successfully used in academic robotics competitions. Basically, this algorithm tries out different combinations and sequences of simple actions until it finds one that is close to the desired complex action. This is usually done with a local search algorithm, or sometimes with other optimization tools.
The second technique is, of course, actually learning to perform the basic actions that layered learning can compose together into more complex actions. This is usually done with some form of reinforcement learning, but sometimes is done by a programming who explicitly solves the equations for the movement of a simple system.
Finally, they need to use a model predictive controller to smoothly interpolate between the sequence of actions that the layered learning approach has come up with. In this approach, the engineers designing the robot have very carefully measured, for this specific robot, exactly how parts of it tend to move or continue moving, and written this down as a mathematical model called a dynamical system. This model allows the algorithm to figure out how this specific robot's movements are slipping away from the planned ones as it executes the motions. The slippage occurs because of things like friction (the robot's parts are not all perfectly smooth, and may have different amounts of lubrication, or a motor might slip). The algorithm can then make small changes to the motion to smooth out these unexpected bumps. That's the part that makes everything look so smooth.
It's worth noting too, that the video is not fully representative of the typical results their algorithm obtains. Boston Dynamics claims in the video caption that their algorithm "succeeds" in achieving a desired motion about 80% of the time. They don't tell us what "success" means, but the video is probably just the best of many takes for a carefully planned and filmed routine.


Is AlphaFold just making a good estimate of the protein structure? In the news, DeepMind's AlphaFold is said to have solved the protein folding problem using neural networks, but isn't this a problem only optimised quantum computers can solve?
To my limited understating, the issue is that there are too many variables (atomic forces) to consider when simulating how an amino acid chain would fold, in which case only a quantum computer can be used to simulate it.
Is the neural network just making a very good estimate, or is it simulating the actual protein structure?

AlphaFold (version 1 and 2) predicts (so estimates) the 3D shape of the protein from the sequence of amino acids. AlphaFold's performance is measured with the global distance test (GDT), which is a measure of similarity between two protein structures (the prediction and the ground-truth) that ranges from 0 to 100.
There is a short video and a longer one (both by DeepMind) that summarise the issue of protein folding, how it is important, how well AlphaFold approximately solves it (in the competition Critical Assessment of protein Structure Prediction (CASP)), i.e. AlphaFold 2 achieves a median GDT score of 92.4 (and 87 on the hardest proteins), which is a lot higher than AlphaFold 1's GDT score of 58 (which was the highest achieved score at the time), where, according to John Moult (president of CASP), a score around 90 is considered a satisfactory solution to the protein folding problem. You can find more details about AlphaFold 2 in this DeepMind blog post and about AlphaFold 1 in this other blog post or the associated paper published in Nature this year. You can find the code for AlphaFold 1 here, but there are other community/open-source implementations.
Despite the importance of the problem and achievement, there is clearly a lot of hype about this breakthrough (given also that it was achieved by DeepMind). This is also discussed in this video by Lex Fridman.


How to use a conv2d layer after a flatten? I am not familiar with Deep learning and Pytorch. And I want to know how to deal, in general with such a situation. So, I was wondering if I used a pretrained model (EfficientNet for example) if I want to change the _fc attribute and use conv2d in it, how can I recover a 2D structure? Because the pretrained model flattens it just before _fc.
for example, the pretrained model outputs a flattened feature vector of 1280 elements what I did is the following:
self.efficient_net._fc = nn.Sequential(
                nn.Linear(1280, 1225),
                nn.Unflatten(dim=1, unflattened_size=(1, 35, 35)),
                nn.Conv2d(1, 35, kernel_size=1),
                ...,
                )

I didn't have a specific height and width to recover in the 2D structure, so I assumed that h = w = some size and I use a linear layer whose output is equal to the square of the "some size". In the example above 35² = 1225. I am not sure if the unflatten is the correct way to do this. Then I added the conv2d. My code works but it doesn't give good results which probably means that the 2D structure I recovered does not capture any meaningful information.
Can anyone enlighten me with general knowledge about how things are done in my situation, or give me some comments? Thank you!

To answer the question in the title, your enclosed method is a valid way to use 2d convs after a flattened feature vector. However, the bad results you experience could come from the structure of your model or from the way you train it. Regarding you last question, it is very hard to give you an advice without knowing your intentions in detail. Regardless, here are my two cents.
First of all, in the case you actually want to use this approach, to have a pretrained model and add your layers after one of its layers, you might want to keep the parameters of the original network intact at least until your newly initialized layers get trained properly. To achieve that, you need to use the gradients for updating only the parts you added as described in this comment. (You definitely should read the other comments there as well to get a better picture.)
Secondly, it might be worth reconsidering if you really want to add your layers after the very last layers of the pretrained network. Depending on your goals, using the output of some prior layers as the input to your layers might be more beneficial to you. (Just do not forget to keep the parameters of the pretrained model intact as I advised in the prior point.)
Lastly, the structure of your layers should also be reconsidered. 2d convs with a kernel size of 1x1 in this situation seems strange to my limited experience, but without knowing what you want to do, its hard to give any solid advice in this regard.
Therefore you might be better off splitting your question into smaller parts and work your way through them one by one.
(My reputation is not high enough otherwise I would have left a comment.)


How should I change the hyper-parameters of the C51 algorithm, in order to obtain higher reward? I have a scenario where, in an ideal situation, the greedy approach is the best, but when non-idealities are introduced which can be learned, DQN starts doing better. So, after checking what DQN achieved, I tried C51 using the standard implementation from tf.agents (link). A very nice description is given here. But, as shown in the image, C51 does extremely bad.

As you can see, C51 stays at the same level throughout. When learning, the loss right from the first iteration is around 10e-3 and goes on to 10e-5, which definitely impacts the change in the weights. But I am not sure how this can be solved.
The scenario is

1 episode consists of 10 steps and the episode only ends after the 10th step, the episode never ends earlier.

states at each step are integer values and can take values between 0 and 1. In the image, states are of shape 20*1.

actions have the shape 20*1

learning rate = 10e-3

exploration factor $\epsilon$ starts out at 0.2 and decays up to 0.01

C51 has 3 additional parameters, which help it to learn the distribution of q-values
num_atoms = 51 # u/param {type:"integer"}
min_q_value = -20 # u/param {type:"integer"}
max_q_value = 20 # u/param {type:"integer"}

num_atoms is the number of support that the learned distribution will have, and min_q_value and max_q_value are the endpoints of the q-value distribution. I set them as 51 (the first paper and other implementations keep it as 51 and hence the name 51), and the min and max are set as the min and max possible rewards.
So, if anyone could help me with fine-tuning the parameters for C51 to work, I would be very grateful.

Here is what I discovered empirically, trial and error. Since tuning the parameters are going to be environment specific, I'll lay out mine to give a better understanding of what I found to work for my case. Hopefully someone with better understanding of the algorithm will weigh in:
Environment: A 2D map where an agent controls a simulated PC mouse pad and must navigate from a random spawn point to a random reward point.
Action Space: Discrete(24) -- This was flattened from the original implementation to allow for use in the Q* algorithms.

0-7, mouse buttons, each with one of two states pressed or depressed

public ButtonPressState Left;
public ButtonPressState Middle;
public ButtonPressState Right;
public ButtonPressState Touch;
public ButtonPressState ScrollUp;
public ButtonPressState ScrollDown;
public ButtonPressState IncreaseScroll;
public ButtonPressState DecreaseScroll;

8-15: Angle to move if Touch is in state pressed, incremented by 45°, starting at 0 °up to 315°

public enum D8Dir
{
    UP = 0,         //   0°
    UP_RIGHT = 1,   //  45°
    RIGHT = 2,      //  90°
    DOWN_RIGHT = 3, // 135°
    DOWN = 4,       // 180°
    DOWN_LEFT = 5,  // 225°
    LEFT = 6,       // 270°
    UP_LEFT = 7     // 315°
}

16-23: Speed, an exponent of 2^N representing how may cells to move per step.

Distance normalization: Trial and error led me to normalizing the space. This also brings the benefit of allowing the same trained algorithm to be used for different world sizes, eg a 2x3 vs a 3x2 vs a 3x3 on up to large common monitor dimensions. Specifically, distances are normalized between -1 and 1 for the height and the width of the space. So no matter the dimensions all points map to x and y between -1 and 1. In the case the height and the width differ the smaller is scaled to the size of the larger.
Reward space: After having agents reward exploit iteration after iteration of reward scheme, Rewards are given when an agent moves closer to the target - with closer taking into consideration both "birds eye" and Euclidian distance. After first, took "theoretical" maximum sum of the total rewards summed up to 1 and were assigned by taking the maximum distance an agent might move in a given 2D space to gain a reward. This works out to be the diagonal of the 2D space. I say "theoretical" because unless the agent randomly spawns exactly in one corner and the reward is placed exactly in the other corner, the actual total reward that can be achieved is lower. So in practice the maximum reward for a given episode is the sum of normalized distances between the agent and the reward.
To avoid reward exploitation, only .70% of the reward if the agent moves closer vertically or horizontally when a diagonal move was available. This is to get the agent to take the shortest path moving diagonally with only the sqrt(2) bird's eye reward. Otherwise and agent might move up, then left and collect a reward of 2 normalized units instead of the ~=1.4142 normalized reward units collected for moving diagonally. The .70% keeps the reward for an vertical then horizontal (or vice versa) move to 1.4 which is less than the ~=1.4142 diagonal reward.
Originally, the agent could collect up to a total reward of up to 1 and then 3 additional reward points for reach the target. Using the stock TensorFlow c51 DQN agent against this reward scheme, using the default min_q_value=-10 and max_q_value=10 values (I believe they are referred to as VMIN and VMAX in the literature) I found learning achieved the following results on very small world sizes:
[5/2/2021 5:39:19 PM] Training Started
[5/2/2021 5:39:33 PM] Training Environment (1, 2): 5/2/2021 5:39:33 PM
[5/2/2021 5:40:11 PM] Mastered (1, 2) in 00:00:38.8244035 - Steps 2565 Episode 948  Average: 3.000000000000002
[5/2/2021 5:40:11 PM] Training Environment (2, 1): 5/2/2021 5:40:11 PM
[5/2/2021 5:41:01 PM] Mastered (2, 1) in 00:00:49.1426355 - Steps 5802 Episode 1242  Average: 3.000000000000002
[5/2/2021 5:41:01 PM] Training Environment (2, 2): 5/2/2021 5:41:01 PM
[5/2/2021 5:43:42 PM] Mastered (2, 2) in 00:02:41.2581146 - Steps 16573 Episode 3248  Average: 3.0551471839999977
[5/2/2021 5:43:42 PM] Training Environment (2, 3): 5/2/2021 5:43:42 PM
[5/2/2021 5:53:44 PM] Mastered (2, 3) in 00:10:01.8163250 - Steps 56732 Episode 11226  Average: 3.0981306360000063
[5/2/2021 5:53:44 PM] Training Environment (3, 2): 5/2/2021 5:53:44 PM
[5/2/2021 5:59:13 PM] Mastered (3, 2) in 00:05:29.5753945 - Steps 78612 Episode 6276  Average: 3.108986006000001
[5/2/2021 5:59:13 PM] Training Environment (3, 3): 5/2/2021 5:59:13 PM
[5/2/2021 6:22:50 PM] Mastered (3, 3) in 00:23:37.2302437 - Steps 173577 Episode 25603  Average: 3.1401708113999938
[5/2/2021 6:22:50 PM] Training Environment (4, 4): 5/2/2021 6:22:50 PM
[5/2/2021 7:10:04 PM] Mastered (4, 4) in 00:47:13.5879491 - Steps 363685 Episode 46441  Average: 3.1596743723999965
[5/2/2021 7:10:04 PM] Training Environment (5, 5): 5/2/2021 7:10:04 PM
[5/2/2021 7:20:08 PM] Mastered (5, 5) in 00:10:04.1529582 - Steps 404256 Episode 8916  Average: 3.182016046800004
[5/2/2021 7:20:08 PM] Training Environment (6, 6): 5/2/2021 7:20:08 PM
[5/3/2021 12:33:49 AM] Killed 6x6 - No Convergence: Step 1671400: Reward 1.8765 loss = 2.90894175 (00:00:02.9459997) (eps: 2.9459996999999998)

As can be seen, even for a simple 6x6 world C-51 DQN did not converge even after over 4 hours of wall time on GTX-3080 sampling 1,671,400 steps so I killed it.
So I modified the total possible reward to for the agent moving to sum up to .5. This was simply a matter of dividing the old reward scheme in half (or rather *.5).
I then changed the target reached reward from 3 to .5.
The theoretical maximum reward then totaled to 1, so I changed min_q_value=0 and max_q_value=1 to match the sum of the rewards an agent might achieve. This resulted in wall times ever larger than before.
My latest attempt I used min_q_value=0 and max_q_value=.5 to match the maximum cumulative reward the agent could recieve before the collecting the .5 target reached reward, (which BTW is also a terminal state in my environment).
The new rewards, normalized to total to 1 run orders of a magnitude faster for the larger spaces. The 6x6 world "converged" after 05 minutes, 43 secs using 88721 total steps in  88721 in 4624 total episodes.
I still find this slow, but clearly the q values matching the range of cumulative rewards is an improvement.
[5/3/2021 12:49:35 AM] Training Environment (1, 2): 5/3/2021 12:49:35 AM
[5/3/2021 12:50:12 AM] Mastered (1, 2) in 00:00:36.8244207 - Steps 2424 Episode 981  Average: 0.5000000000000002
[5/3/2021 12:50:12 AM] Training Environment (2, 1): 5/3/2021 12:50:12 AM
[5/3/2021 12:50:37 AM] Mastered (2, 1) in 00:00:24.6645133 - Steps 4075 Episode 700  Average: 0.5000000000000002
[5/3/2021 12:51:52 AM] Mastered (2, 2) in 00:01:15.0585713 - Steps 8135 Episode 1419  Average: 0.5314644659999993
[5/3/2021 12:51:52 AM] Training Environment (2, 3): 5/3/2021 12:51:52 AM
[5/3/2021 12:52:39 AM] Mastered (2, 3) in 00:00:47.0126118 - Steps 11266 Episode 961  Average: 0.5455624971999997
[5/3/2021 12:52:39 AM] Training Environment (3, 2): 5/3/2021 12:52:39 AM
[5/3/2021 12:52:56 AM] Mastered (3, 2) in 00:00:17.6139995 - Steps 12447 Episode 395  Average: 0.5650996157999993
[5/3/2021 12:52:56 AM] Training Environment (3, 3): 5/3/2021 12:52:56 AM
[5/3/2021 12:55:56 AM] Mastered (3, 3) in 00:02:59.7056623 - Steps 24472 Episode 3403  Average: 0.5863068707999991
[5/3/2021 12:55:56 AM] Training Environment (4, 4): 5/3/2021 12:55:56 AM
[5/3/2021 1:00:07 AM] Mastered (4, 4) in 00:04:11.2932882 - Steps 41259 Episode 4240  Average: 0.6052226153999957
[5/3/2021 1:00:07 AM] Training Environment (5, 5): 5/3/2021 1:00:07 AM
[5/3/2021 1:06:11 AM] Mastered (5, 5) in 00:06:03.8448782 - Steps 65641 Episode 5502  Average: 0.6209708242799977
[5/3/2021 1:06:11 AM] Training Environment (6, 6): 5/3/2021 1:06:11 AM
[5/3/2021 1:11:54 AM] Mastered (6, 6) in 00:05:43.2033837 - Steps 88721 Episode 4624  Average: 0.6089312343400013

FYI: The paper states that Transitions to a terminal state are handled with γt = 0.

Update:
The 9x9 environment took 294,897 steps, in 37,025 episodes over 51 minutes and 38 seconds. It may be the case that the max_q_value=1 works better in the larger world sizes where an agent might collect more movement reward. In any case, these values are nearly quadratically better than the default values from the tutorial.
I will experiment with them more.
Additionally, tuning n-steps might help. My implementation may also have an issue using the replay buffer memories from smaller world sizes as I am changing the world size dynamically an currently not clearing the buffer.
[5/3/2021 2:03:33 AM] Mastered (9, 9) in 00:51:38.4201434 - Steps 294897 Episode 37025  Average: 0.6425936848799915


Defining rules for an expert system I'm doing a project for my last university examination but I'm having some troubles! I'm making an expert system who should be able to assemble a computer after asking some questions to the user. It works but according to my teacher I need to define more rules, could you give me some suggestions please? I have facts like these:

processor(P, Proc_price, Price_range),
motherboard(M, Motherboard_price, Price_range),
ram(R, Ram_price, Price_range),
case(C, Case_price, Price_range),
ali(A, Ali_price, Price_range),
video_card(V, Vga_price, Price_range),
ssd(S, Ssd_price, Price_range),
monitor(D, Monitor_price, Price_range),
hdd(H, Hdd_price, Price_range).

I ask these questions to the user: 1) choose the price range 2) choose the display size 3) choose hard disk size Then I ask 3 questions about computer utilization to define the user: 1) do you surf on internet? 2) do you play? 3) do you use editing programs?

use(gaming) :- ask("Do you play games? (y/n)").

    use(editing) :- ask("Do you use editing programs? (y/n)").

    use(surfing) :- ask("Do you surf internet?(y/n)").

    user(base) :-
        use(surfing),  \+ use(gaming), \+ use(editing).

    user(gamer) :-
        use(gaming), use(surfing), \+ use(editing).

    user(professional) :-
        use(editing), \+ use(gaming), use(surfing).

I should make more questions about user definition to make user definition more complex too and add some rules. Please help me, I'm desperate

We cannot do homework for students in this network, however I can suggest that several items affecting cost and several usage patterns are missing and the number of rules is shy by an order of magnitude.  I wholeheartedly agree with the educational directives you received.

Consider first developing your lists further to include peripherals like DVD burner, USB devices, and audio.  Whether the user does scientific programming, watches movies on the monitor, develops software, and other specific usage scenarios is also more specific and therefore will produce a better tailored system than the answer to the question of whether the user is a professional.

It is not the metric of the number of rules that is of most importance.  It is the number of operations contained in the rule set that is the guiding metric.  This is because rules in Prolog can be aggregated.  The rough estimate of rule operator count to complete a system is sqrt(i*o)/4, where i is the number of input permutations and o is the number of output permutations.

(This is the application of Shannon Information Theory, that number of bits n = log2 (P'/P), where P' and P are the a posteriorii and a priori probabilities respectively.  The divisor of four is because there are about 16 = 24 operators normally used.)

You may end up with thirty or forty rules.

Create some use cases that exercise the extremes as well as some of the typical cases from among the permutations in inputs and outputs.  Run your system on those cases and observe the system behavior.  Learn how to debug by outputting intermediate results or stepping through rule execution.

There are no shortcuts to researching and developing other than not wasting time worrying about how much time it will take.  You can also optimize your homework time by learning the tools and then stepping back, taking a deep breath, and saying, "I can do this!"


Can we use a pre trained Encoder (BERT, XLM ) with a Decoder (GPT, Transformer-XL) to build a Chatbot instead of Language Translation? I was wondering if the BART or T5 models can do the task of generating sentences in English. Most of the models I have mentioned are trained to translate from English to German or French. Is is it possible that I can use the output of BERT as an input to my Decoder? My theory is that when I already have the trained Embeddings, I do not need to train the Encoder part. I can just add the outputs of sentences to the decoder to generate the sentences.

In place of finding the loss value from the translated version, Can I compute loss on the reply of a sentence?

Can someone point me towards a tutorial where I can use the BERT output as for the decoder part. I have a data of conversation with me. I want to build a Chatbot from that data.

I have already implemented LSTM based Sequence2sequence model but it is not providing me satisfactory answer.

After some research, 2 such models are there as T5 and BART which are based on the same idea.

If possible, can someone tell me how can I use BART or T5 to make a conversational bot?

=> I don't have more ideas about BART and T5 Right now. but I had created a chatbot Based on GPT-2 Model-based on Microsoft DialoGPT. Which is fine-tuned on millions of parameters of Reddit. you can fine-tune on your own data using DialoGPT. I had not found a public decoding method. So, We tried to generate diverse responses using simple nucleus sampling at each time step. So, We used greedy nucleus sampling multiple times in parallel to generate multiple candidates responses. We generated 30 such responses for each turn and also used the last 3 turn conversation history as extra context for generator. So, We can generate responses related to the current Context of Conversation.

We used Code reference from here. you need to implement greedy nucleus sampling multiple on this code.

=>Now To Choose the best-matched response from response generated I created a Reranker.I used two sub-component.

=>Component one Counts Cosine similarity between Response and Query using sentence Encoder.

=>In Component Two we cross-entropy error for generating original query from the response.For that I used reverse-generator of DialogueGPT.

We Combined Score of Both Component as Score=norm(comp1Score)+norm(1-comp2Loss). Using this score you can find best response.

For Tutorial My Favourite Hugging Face they have BERT,GPT, GPT-2, XLNET,etc...
and Second Favourite Facebook ParlAI,
try Blender Model also.


What are the differences between network analysis and geometric deep learning on graphs? Both of them deal with data of graph structure like a network community. Is there a big difference there?

Network analysis does not necessarily use deep learning techniques, while geometric deep learning (GDL) on graphs uses only deep learning techniques (that is, you train a neural network using gradient descent or other optimization methods). You can do some network analysis using GDL.


How to perform structure learning for Bayes Net given already partially constructed net? Let assume that we have dataset of variables (random events), I apriori would like to set dependency conditions between some of them and perform structure learning to figure out the rest of the net. How it can be done practically (e.g. some libs like bnlearn etc.) or at least in theory?

I was trying to google it but haven't found anything related

Hill Climbing algo or Constraint-based structure learning algorithms implemented accept whitelist or blacklist arguments permitting or prohibitting some arcs.


Effects of translating RL action probability through non linearity I am training an RL agent (specifically using the PPO algorithm) on a game environment with 2 possible actions left or right.

The actions can be taken with varying "force"; e.g. go left 17% or go right 69.3%. Currently, I have the agent output 21 actions - 10 for left (in 10% increments), 10 for right in 10% increments and 1 for stay in place (do nothing). In other words, there is a direct 1-1 mapping in 10% increments between the agent output and the force the agent uses to move in the environment.

I am wondering, if instead of outputting 21 possible actions, I change the action space to a binary output and obtain the action probabilities. The probabilities will have the form, say, [70, 30]. That is, go left with 70% probability and go right with 30% probability. Then I take these probabilities and put them through a non-linearity that translates to the actual action force taken; e.g an output of 70% probability to go left, may in fact translate to moving left with 63.8% force.

The non linear translation is not directly observed by the agent but will determine the proceeding state, which is directly observed.

I don't fully understand what the implications of doing this will be. Is there any argument that this would increase performance (rewards) as the agent does not need to learn direct action mappings, rather just a binary probability output?

Have you considered using a continuous action space? It might be worth looking into. If you aren't familiar with it, here are a few resources for discrete vs continuous action spaces -

Modeling and Planning in Large State and Action Spaces

Deep Reinforcement Learning in Continuous Action Spaces:a Case Study in the Game of Simulated Curling


Multi-label classification (e.g. as used in Keras) using DNN I have data with about 100 numerical features and a multi-labelling that encodes ownership of a certain product (i.e. my labels are of the form $[x_i, i=1, \dots, n]$ where n is the number of products and $x_i$ is either 0 or 1). My neural network approach to this currently looks like this

model = Sequential()
model.add(Dense(1024, activation='relu', input_dim=X_train.shape[1]))
model.add(Dense(1024, activation='relu'))
model.add(Dense(1024, activation='relu'))
model.add(Dense(1024, activation='relu'))
model.add(Dense(y_train.shape[1], activation='softmax'))

in Keras (i.e. a couple of dense layers with ReLu activation, then an output layer with softmax).

Now my question is: will the network consider labels of the other products when considering a probability to assign to the label of one product? I would like that to happen, but I can't quite grasp whether it does (my suspicion is no).

I'm new to multilabel classification and relatively new to NN in general, so I hope this isn't too inept a question.

Firstly you should use sigmoid in your last layer instead of softmax. Softmax returns a probability distribution, meaning that when one labels probability increases the other will decrease, which is not always the case. Secondly in order for keras to use all the labels you should use binary_crossentropy as the loss function.


Relationship between Rewards and Q Value (Graph between Q(s, a) vs episodes) I'm employing the Actor-Critic algorithm. The critic network approximates the action-value function, i.e. $Q(s, a)$, which determines how good a particular state is, when provided with an action.
$Q(s, a)$ is approximated using the backpropagation of the temporal difference error (TD error). We can understand that $Q(s, a)$ has been approximated properly when TD error is minimized, i.e. when it is saturated at lower values.
My question is, when exactly can you say that $Q(s, a)$ is approximated properly, if you don't have TD error, i.e. if you have to plot the graph between $Q(s, a)$ vs episodes, then what would be the optimal behaviour?
Will it be increasing exponential with saturation value around reward values, or increasing exponential with saturation (around any value)?
Follow up: What can be the possible mistake, if the output of Q-value function is around 5x the rewards, and not saturating?

TLDR;
The output of Q-value function will eventually saturate. Can't say when, but it will surely do.
Detailed Answer

if you don't have TD error

It meant, if I don't have logs of the error.

$Q(s, a)$ vs Episodes Graph

To understand, how $Q(s, a)$ behaves as the episodes increase.
I was under a wrong impression that, the $Q(s, a)$ will saturate around the values given by the reward function.
As evident from Loss vs Training Episodes Curve, we can see that loss (TD Error) is almost saturated.
However, $Q(s, a)$ vs training episodes curve is not saturated yet.

The only explanation for the above two graphs could be given as follows:
The target estimate ($r + \gamma Q(s', a')$) and $Q(s, a)$ are almost similar due to which, the error is quite low. But, $Q(s, a)$ is still nowhere near optimal value $Q^{*}(s, a)$.
Hence, I gave it another shot and made it run for twice training episodes i.e. 20000, and below are the results.
A nearly saturated loss

and a nearly saturating $Q(s, a)$.
.
Note that, the value of $Q(s, a)$ saturating is around 250 - 300 (will run it for more iterations) and it is nowhere around the reward values $ \in [-100, 35]$.
Hence, the $Q(s, a)$ vs episodes will saturate.


What is the intuition behind the dot product attention? I am watching Attention all you need, In that what is the intuition behind the dot product attention?

$$A(q,K, V) = \sum_i\frac{e^{q.k_i}}{\sum_j e^{q.k_j}} v_i$$

becomes:

$$A(Q,K, V) = softmax(QK^T)V$$

Let's start with a bit of notation and a couple of important clarification.

Q refers to the query vectors matrix, $q_i$ being a single query vector associated with a single input word.

V refers to the values vectors matrix, $v_i$ being a single value vector associated with a single input word.

K refers to the keys vectors matrix, $k_i$ being a single key vector associated with a single input word.

Where do these matrices come from? Something that is not stressed out enough in lot of tutorials is that these matrices are the result of a matrix product between the input embeddings and 3 matrices of trained weights: W$_{\textbf{q}}$, W$_{\textbf{v}}$, W$_{\textbf{k}}$.

The fact that these three matrices are learned during training explain why the query, value and key vectors end up being different despite the identical input sequence of embeddings. It also explain why it make sense to talk about multi-head attention. Performing multiple attention steps on the same sentence produce different results because for each attention 'head' new W$_{\textbf{q}}$, W$_{\textbf{v}}$, W$_{\textbf{k}}$ are randomly initialised.

Another important aspect not stressed out enough is that for the encoder and decoder first attention layers, all the three matrices comes from the previous layer (either the input or the previous attention layer) but for the encoder/decoder attention layer, the Q matrix comes from the previous decoder layer, whereas the V and K matrices come from the encoder. And this is a crucial step to explain how the representation of two languages in an encoder are mixed together.

Once computed the three matrices, the transformer move on on the calculation of the dot product between query and key vectors.
As nbro wrote in its comment, the dot product is used to compute a sort of similarity score between the query and key vectors. Indeed, the authors used the names query, key and value to indicate that what they propose is similar to what is done in information retrieval. For example in question answering usually given a query you want to retrive the closer sentence in meaning among all possible answers, and this is done by computing the similarity between sentences (question vs possible answers).

Of course here the situation is not exactly the same, but the guy who did the video you linked did a great job in explaining what happened during the attention computation (the two equations you wrote are exactly the same in vector and matrix notation and represent these passages):

closer query and key vectors will have higher dot products.
applying the softmax will normalise the dot product scores between 0 and 1.
multiplying the softmax results to the value vectors will push down close to zero all value vectors for words which had a low dot product score between query and key vector.

In the paper the authors explain the attention mechanisms saying that the purpose is to determine which words of a sentence the transformer should focus on. I personally prefer to think at attention as a sort of coreference resolution step, the reason why I think so is the following image (taken from this presentation by the original authors).

This image shows basically the result of the attention computation (at a specific layer that they don't mention). Bigger lines connecting words mean bigger values in the dot product between the words query and key vectors, which means basically that only those words value vectors will pass for further processing to the next attention layer. But please note that some words are actually related even if not similar at all, for example 'Law' and 'The' are not similar, they are simply related to each other in this specific sentences (that's why I like to think to attention as coreference resolution). Computing similarities between embeddings would never provide information about this relation in a sentence, the only reason why transformer learn these relationship is the presences of the trained matrices W$_{\textbf{q}}$, W$_{\textbf{v}}$, W$_{\textbf{k}}$ (plus the presence of positional embeddings).


Skip-Gram Model Training Suppose we want to predict context words $w_{i-h}, \dots, w_{i+h}$ given a target word $w_i$ for a window size $h$ around the target word $w_i$. We can represent this as: $$p(w_{i-h}, \dots, w_{i+h}|w_i) = \prod_{-h \leq k \leq h, \ k \neq 0} p(w_{i+k}|w_i)$$ where we model the probabilities of a word $u$ given another word $v$ as $$p(u|v) = \frac{\exp(\left<\phi_u, \theta_v \right>)}{\sum_{u' \in W} \exp(\left<\phi_{u'}, \theta_v \right>)}$$ where $\phi_u, \theta_v$ are some vector representations for words $u$ and $v$ respectively and $\left<\phi_u, \theta_v \right>$ is the dot product between these vector representations (which represents some sort of similarity between the words) and $W$ is a matrix of all the words.

In Skip-Gram Negative Sampling, we want to learn the embeddings $\phi_u, \theta_v$ that maximize the following: $$\sum_{u \in W} \sum_{v \in W} n_{uv} \log \sigma(\left<\phi_u, \theta_v \right>) +k \mathbb{E}_{\bar{v}} \log \sigma(-\left<\phi_u, \theta_{\bar{v}} \right>)$$

  Question. How exactly does this work? For example, suppose $k=5$, the target word $w_i$ is $\text{apple}$ and we want to find
  $p(\text{pie}| \text{apple})$. Let $n_{uv} = 10$ (number of times pie
  co-occurs with apple). Then we sample $5$ random words $\bar{v}$ that
  did not occur with $\text{apple}$ and whichever term in the sum is
  bigger is the one we predict? For example, if the first term in the
  sum is larger than the second term then we would predict that
  $p(\text{pie}| \text{apple}) \approx 1$? Otherwise we predict that
  $p(\text{pie}| \text{apple}) \approx 0$? Is this the correct
  intuition?

Source. Here at around the 10:05 mark.

Almost, but no. When you maximize that objective function, you do so by adjusting the parameters $\phi$ and $\theta$. After you're done with training, you can use your word embeddings for other NLP tasks. You don't, however, do any prediction directly from the skip-gram model.

To maximize the first term, co-occuring words must have large inner products. That is, they must be "similar". To maximize the second term**, the randomly sampled words must have a small inner product with $\phi_u$. That is, they must be "dissimilar" to $\phi_u$. Moving these word embeddings around in the vector space to make some words similar and others not is the only thing that happens during skip-gram training.
$$$$

** $\sigma(-x)=1-\sigma(x)$, so maximizing $\sigma(-x)$ is minimizing $\sigma(x)$


Why do the inputs and outputs of a convolutional layer usually have the same depth? Here's the famous VGG-16 model.

Do the inputs and outputs of a convolutional layer, before pooling, usually have the same depth?  What's the reason for that?
Is there a theory or paper trying to explain this kind of setting?

Keeping the same channel size allows the model to maintain rank but i would say the main reason is convenience. Its easier book keeping.

Also in many model cases output features need some form of alignment with the input (example being all models using residual units -- $\hat{x} = F(x) + x$