How can I apply reinforcement learning to solve this asteroid game? Introduction
An attractive asteroid game was described in the paper Learning Policies for Embodied Virtual Agents through Demonstration (2017, Jonathan Dinerstein et al.):

In our first experiment, the virtual agent is a spaceship pilot, The pilot's task is to maneuver the spaceship through random asteroid fields

In theory, this game can be solved with reinforcement learning or, more specifically, with a support vector machine (SVM) and epsilon-regression scheme with a Gaussian kernel. But it seems that this task is harder than it looks like, as the authors of the same paper write

Although many powerful AI and machine learning techniques exist, it remains difficult to quickly create AI for embodied virtual agents.

it is quite challenging to achieve natural-looking behavior since these aesthetic goals must be integrated into the fitness function

Questions
I really want to understand how reinforcement learning works. I built a simple game to test this. There are squares falling from the sky and you have the arrow keys to escape.

How could I code the RL algorithm to solve this game? Can I do this manually in Javascript according to what I think should happen? How can I do this without having to map the positions of the rectangles and mine, just giving the agent the keyboard arrows to interact and three information:

Player life
Survival time
Maximum survival time

A closely related question and a minimal implementation written in Python.

That program implements the reinforcement learning technique 'Q-Learning'.

The idea is for the program to take in an observation of the environment (which could be a screenshot if learning a computer game, or sensor data for a robot) and output a decision in the form of a vector of values. Each cell in that output vector corresponds to a possible action (left, right, shoot, etc) and the highest valued cell shows the action that the agent/player should take. The values in that output vector are called the Q-Values, and it is the mapping from the input data to the vector of Q-Values that we are trying to learn.
In your case, the function that takes in an observation of the environment and spits out a vector of decision choices is your SVM.

The question linked above contains a description of the training algorithm. It boils down to playing the game multiple times while storing the input vector, output vector and output decision for each step until you reach a termination condition (ie hitting an asteroid) and receiving a score (in this case a negative score since you want to avoid the asteroids). Then, going backwards through the the output vectors, assigning a slowly reducing amount of the output score to the particular cell in each output vector corresponding to the decision that was made at that step of the game.
The array of input vectors from the game, and the array of output decision vectors that you have just created become the training data for your machine learning system. Once you have completed a training run, play the game again with your trained system and keep repeating until it is a good as you need it to be, or it stops getting any better.

To address your question directly, I don't think that you are going to be able to train your system without giving it information about the position of the asteroids (assuming that they are positioned at random). However, you could try just having a very simple input vector such as 3 integer values where each value corresponds to the presence (1) or absence (0) of an asteroid in the 3 squares to the above left, above and above right of the player. That might be enough to encourage it to dodge away from falling rocks...

There are some Support Vector Machines implemented in JavaScript, although I have never used them, but since SVMs are basically two-class classifiers you would have to check that the library can easily support multi-class SVMs. In your case the SVM would be trying to classify each input into a particular player choice (left, right, shoot, etc).


How does L2 regularization make weights smaller? I'm learning logistic regression and $L_2$ regularization.
The cost function looks like below.
$$J(w) = -\displaystyle\sum_{i=1}^{n} (y^{(i)}\log(\phi(z^{(i)})+(1-y^{(i)})\log(1-\phi(z^{(i)})))$$
And the regularization term is added. ($\lambda$ is a regularization strength)
$$J(w) = -\displaystyle\sum_{i=1}^{n} (y^{(i)}\log(\phi(z^{(i)})+(1-y^{(i)})\log(1-\phi(z^{(i)}))) + \frac{\lambda}{2}\| w \|$$
Intuitively, I know that if $\lambda$ becomes bigger, extreme weights are penalized and weights become closer to zero. However, I'm having a hard time to prove this mathematically.
$$\Delta{w} = -\eta\nabla{J(w)}$$
$$\frac{\partial}{\partial{w_j}}J(w) = (-y+\phi(z))x_j + \lambda{w_j}$$
$$\Delta{w} = \eta(\displaystyle\sum_{i=1}^{n}(y^{(i)}-\phi(z^{(i)}))x^{(i)} - \lambda{w_j})$$
This doesn't show the reason why incrementing $\lambda$ makes weight become closer to zero. It is not intuitive.

Here is my take.
The larger the $\lambda$, the more the corresponding regularization term for a coefficient will be big, so when minimizing the cost function, the coefficient will be reduced by a bigger factor, you can see this effect in the derivation of the update rule for gradient descent for example:
\begin{align*} \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \end{align*}
\begin{align*} \theta_j := \theta_j (1- \alpha \frac{\lambda}{m})\left( \frac{\alpha}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \end{align*}
From this derivation, it is clear that at every update the coefficients get reduced by a factor that is usually a little less than 1 and directly proportional to $\lambda$, so, as $\lambda$ gets bigger, the weights get reduced more and more; eventually, for very big values of $\lambda$, we risk to totally underfit the data, since only the regularization term will remain in the cost function and all the weights will go to zero.
This is for linear regression, but it is essentially the same logic also for logistic regression.
This is taken from Andrew Ng's course on Coursera. A more mathematical precise (and complex) traction of the problem can be found in the Bloomberg machine learning course material.
PS: in the derivation of the update rule for gradient descent, the $\lambda$ should be divided by the number of training examples, this is important in choosing the right $\lambda$ because we want this relationship to be inversely proportional, otherwise the coefficient won't be decreased.


Face liveness detection using face landmark points How to detect liveness of face using face landmark points?
I am getting face landmarks from android camera frames. And I want to detect liveness using these landmark points.
How to tell if a human is making a specific movement that can be useful for liveness detection?

One approach would be to obtain labeled ("yes/no") samples, e.g. via Mechanical Turk, it costs though) and approach it as supervised learning task. E.g. a neural network will discover itself through the learning what features (landmark positions) are helpful for detection.

There should be examples around for mood detection etc.


Does replacing 3x3 filters with 3x1 and 1x3 filters improve the performance? Recently I have come up with a VGG16 model for my binary classification task. I have relatively simple signal images

Therefore (maybe?) other deeper models like resnet18 and Inceptionv3 were not as good. As known, VGG uses 3x3 filters for convolving the images to make feature maps. I have tried several hyper-parameters to get a desired performance. However, there are still some things I need to do. I was thinking of replacing the 3x3 conv filters with 3x1 followed by 1x3 filters to reduce the compute. I think it will definitely do so considering the multiplications (9 operations for 3x3and 6 for 3x1 followed by 1x3).
Then I came to think: If I replace all the 3x3 filters with separable filters, will I get any performance improvement?
What are the benefits of replacing 3x3 filters with separable ones?
Thanks

If the filter is separable, that is, the NxM kernel can be mathematically equal to the convolution of a Nx1 filter and a 1xM filter, there are a very important increase in performance.
Using separable convolution, the network can made an optimal usage of the shared memory and of the parallelism in memory access. See this excellent article for details. These improvements are bigger for bigger kernels.
Also the training is improved, starting by the simple fact that a NxM filter has a number of parameters proportional to N*M but the related separable one has N+M.


How to explain that a same DNN model have radically different behaviours with each new initialization and training? I'm trying to predict the continuous values of a variable $y$ using a Fully Connected Neural Network while providing it with data from a $(3300, 13)$ matrix $X$ where $X[i, :]=[0,...,1,...,0,x_{i}]$. So the first $12$ elements of a data vector are all zeros except for one element which is equal to $1$ to denote  the belonging of this data to a category. I'd like to add that my $X$ data is normalized with regard to the $13$-th column and that both $X$ and $y$ are shuffled in the same manner. Please find below my code for my model:
model = Sequential()
model.add(Input(shape=(13,)))
model.add(Dense(6, activation = 'relu'))
model.add(Dense(2, activation = 'relu'))
model.add(Dense(1))

model.compile(loss = 'mean_squared_error',
              optimizer = 'adam',
              metrics = ['RootMeanSquaredError'])

history = model.fit(X, y, validation_split = 0.1, epochs=64)

When trying to plot the learning curve using:
plt.plot(history.history['loss'])
plt.plot(history.history['val_loss'])
plt.title('model loss')
plt.ylabel('rmse')
plt.xlabel('epoch')
plt.legend(['train', 'val'], loc='upper left')
plt.show()

I get these curves:

There's already an "unusual" element to point here; I've noticed that throughout the training the loss decreases but sometimes in an oscillating manner but we don't notice that on the training learning curve.  For example the last four values of the loss are: $2.5176$, $3.4718$, $3.0704$ and it settles down on $3.8177$. I've also noticed that the losses provided by history.history are different than those shown during training, I suspect ones are computed before the epoch and ones after but I'm not sure.
I've tried to predict on the $275$ first elements of the training data. Most of the predictions took the value $4.2138872e+00$ but there are other predictions who took lesser values. I've computed the maximum of the predictions on the whole training set and it is $4.2138872e+00$.
I've also tried to train on the whole training set without a validation set to see what'll happen. I've made sure to rerun the cells of the model so that it doesn't take the weights it already found. I've noticed the same behaviour for the loss during training, but this time there is no constant predicted value that comes up as a maximum limit for the predictions.
I've already asked this question here and a user suggested to me that I should ask this question separately while providing the whole code. I ran the same code I was running and that was giving me the same predictions for no matter for my input vectors.
I think, as the user @Kostya that answered my previous question pointed out, what's happening here is called "dying ReLus". It's the same code that I'm running over and over but gives different predictions and the only random parameters are the weights and the biases. I'm sure the biases are initially initialized to zero but I don't know how the weights are handled. I suppose they're randomly generated by a centered and reduced normal distribution.
I have last came to this question: does the number of neurons, hence the number of weights influence the phenomena of "dying ReLus" ? I came to think that because if we had a large number of weights, their values are likely to fill that interval where the majority of the probability mass is concentrated. And since we have a small number of weights, we can get some "outlier" weights which lead to dyind ReLus.

I'm sure the biases are initially initialized to zero but I don't know how the weights are handled.

Looking at the Dense layer docs: by default Dense layers biases are initialized with zeros (bias_initializer='zeros') and weights are initialized with Glorot uniform (kernel_initializer='glorot_uniform').

... "unusual" element to point here;  I've noticed that throughout the training the loss decreases but sometimes in an oscillating manner.

There's nothing unusual about the oscillations. Quite on the contrary - your curves are suspiciously too smooth.

I've also noticed that the losses provided by history.history are different

Yes, so this is a little gotcha in the keras implementation. For training loss, keras does a running average over the batches throughout an epoch, while for the validation loss it computes it after the epoch finishes. (link)
That also explains why your validation loss starts slightly lower than the training one - it actually lags behind the training loss by $\sim1/2$  of an epoch.
The fact that both losses stay almost equal suggests that your model don't really rely on training data for prediction - it got saturated ("dying ReLus") almost instantly.
Couple of suggestions that I can make:

I don't see you setting up a learning rate. Try making it smaller (like, much smaller). And see if there's any difference.

MSE is a nasty loss - especially at large values. Have you tried standardizing the target values?

Does the number of neurons, hence the number of weights influence the phenomena of "dying ReLus" ?

Yes, the less neurons you have the higher the chance that all of the neurons will die out. You can get some intuition about it on https://playground.tensorflow.org/ - following the link, I've got a relu network that trains reasonably well. Try increasing the learning rate and observe saturation in the neurons. Reduce the number of neurons and see how the whole net gets stuck.


Can machine learning be used to improve the average case complexity of an algorithm? I am developing an algorithm that, in certain moment, must explore an exponential number of objects derived from a graph:

for o in my_graph.getDerivedObjects():
  if hasPropertyX(o):
    process(o)
    break;

If one of the derived objects has property $X$, then the algorithm process it and then stops. The theory ensures that at least one of these derived objects has property $X$. Now, I strongly suspect that there is a strong correlation between some topological aspects of the graph, and which derived objects actually have property $X$. I want to predict some of the derived objects that have property $X$ using Machine Learning. So, the idea is:

Predict a derived object $o$ that supposedly has property $X$ - or maybe predict $n$ of them for some number $n$.
If any of them is useful, I use them. If not, I run the exponential algorithm.

Of course, this isn't an optimization in the worst-case complexity of the algorithm. Also, I suppose I should also develop some statistical tests in order to show that the prediction algorithm actually works.

Is this type of optimizations common? Could you please provide some examples? The literature on the subject would also be greatly appreciated.

To the best of my knowledge, there haven't yet been many academic publications in this area, which could be broadly said to fall within Search-Based Software Engineering. Here are the ones I know of.

Jerry Swan and Nathan Burles. Templar - A Framework for Template-Method Hyper-Heuristics. In: Genetic Programming - 18th European Conference, EuroGP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. 2015, pp. 205–216. DOI: 10.1007/978-3-319-16501-1_17.

This paper describes 'Hyper-quicksort', a quicksort variant that uses Machine Learning (ML) to generate a pivot function:

A. E. I. Brownlee, N. Burles, and J. Swan. Search-Based Energy Optimization of Some Ubiquitous Algorithms. In: IEEE Transactions on Emerging Topics in Computational Intelligence 1.3 (2017), pp. 188–201.

This paper uses ML to generate energy-efficient variants of some widely-used algorithms

David R. White, Leonid Joffe, Edward Bowles, and Jerry Swan. Deep Parameter Tuning of Concurrent Divide and Conquer Algorithms in Akka. ISBN: 978-3-319-55792-2.

This paper uses ML to optimise the FFT, matrix multiplication and quicksort for concurrency

Nathan Burles, Edward Bowles, Alexander E. I. Brownlee, Zoltan A. Kocsis, Jerry Swan, and Nadarajen Veerapen. Object-Oriented Genetic Improvement for Improved Energy Consumption in Google Guava. DOI: 10.1007/978-3-319-22183-0_20.

This one optimises Google Guava for energy consumption

Zoltan A. Kocsis, Geoff Neumann, Jerry Swan, Michael G. Epitropakis, Alexander E. I. Brownlee, Saemundur O. Haraldsson, and Edward Bowles. Repairing and Optimizing Hadoop hashCode Implementations. In: Search-Based Software Engineering: 6th International Symposium, SSBSE 2014, DOI: 10.1007/978-3-319-09940-8_22.

This one fixes broken hashCodes by using ML to generate new ones

There was also one (from Microsoft Research, I think) entitled something like "The case for self-adjusting data structures". I'll add an edit if I can find it.


What is the difference between the study of evolutionary algorithms and optimization? I have a course named "Evolutionary Algorithms", but our teacher is always mentioning the word "optimization" in his lectures.

I am confused. Is he actually teaching optimization? If yes, why is the name of the course not "Optimization"?

What is the difference between the study of evolutionary algorithms and optimization?

Optimization problems are formally defined by two things:

Optimization objective: $$\min_{x \in \mathbb{R}} f(x)$$
List of constraints: $\text{s.t. } x > 0$; $\text{s.t. } x^2 < 100$, ...

Optimization theory as a field deals with variations of such problems. The algorithms that are part of optimization include gradient descent and variants, the simplex algorithm, simulated annealing and many more. I would also include evolutionary algorithms as one of the algorithms in this field.

I am confused. Is he actually teaching optimization? If yes, why is the name of the course not "Optimization"?

Evolutionary algorithms are a subfield of optimization. The name of the course is evolutionary algorithms as you likely don't deal with the other aspects of optimization theory (e.g. the algorithms mentioned above).


Interpretation of a good overfitting score As shown below, my deep neural network is overfitting :

where the blue lines is the metrics obtained with training set and red lines with validation set

Is there anything I can infer from the fact that the accuracy on the training sets is really high (almost 1) ?

From what I understand, it means that the complexity of my model is enough / too big. But does it means my model could theoretically reach such a score on validation set with same dataset and appropriate hyperparameters ? With same hyperparameters but bigger dataset ?

My question is not how to avoid overfitting.

It doesn't tell you very much, to be honest. It does mean that (assuming your training and validation distributions are similar) your model could get the same results on your validation set should you train on that, but that would still be overfitting.

Really, the only useful thing overfitting tells you is that you don't have enough regularisation.


Are embeddings in multi-lingual language models comparable across languages? Facebook has just pushed out a bigger version of their multi-lingual language model XLM, called XLM-R. My question is: do these kind of multi-lingual models imply, or even ensure, that their embeddings are comparable between languages? That is, are semantically related words close together in the vector space across languages?

Perhaps the most interesting citation from the paper that is relevant to my question (p. 3):

  Unlike Lample and Conneau (2019), we do not use language embeddings,
  which allows our model to better deal with code-switching.

Because they do not seem to make a distinction between languages, and there's just one vocabulary for all trained data, I fail to see how this can be truly representative of semantics anymore. The move away from semantics is increased further by the use of BPE, since morphological features (or just plain, statistical word chunks) of one language might often not be semantically related to the same chunk in another language - this can be true for tokens themselves, but especially so for subword information.

So, in short: how well can the embeddings in multi-lingual language models be used for semantically comparing input (e.g. a word or sentence) of two different languages?

Embeddings generated by transformers like Bert or XLM-R are fundamentally different from embeddings learned through language models like GloVe or Word2Vec.
The latter are static, i.e. they are just dictionaries containing a vocabulary with n-dimensional vectors associated to each word. Because of this they can be plotted through PCA and the distance between them can be easily calculate with whatever metrics you prefer.

When training Bert or XLM-R instead you are not learning vectors, but the parameters of a transformer. The embedding for each token are then generated once a token is fed into the transformer. This implies several things, the most important being that the hidden representation (the embedding) for the token change depending on the context (recall that XML-R use as input also the hidden states generated by the previous token). This means that there are no static vectors to compare by plotting them or by calculating the cosine similarity.
Nevertheless, there are way to analyse and visualise the syntax and semantics encoded in the parameters, this paper show some strategies: https://arxiv.org/pdf/1906.02715.pdf

On a more linguistic side, I would also ask why vectors of same words should show the same semantic properties across languages. Surely there are similarities for lot of words translated literally, but the use of some expressions is inherently different across languages. To make a quick example: in English the clock 'works', in Dutch the clock 'lopen' (it walks) and in Italian the clock 'funziona' (it functions). Same expression, three different words in different languages that do not necessarily share the same neighbours in their monolingual latent spaces.
The point of transformers is exactly to move from static representations to dynamic ones that are able to learn that all those three verbs (in their specific language) can appear early in a sentences and close to the word clock.


What is a state in a recurrent neural network? I am Reading "Supervised Sequence Labelling with Recurrent Neural Networks" written by Alex Graves to try to understand LSTM networks and I am a bit confused about the equations.

Specifically, what I am confused about is the term "state". When used in an equation (section 4.5.2), it says:

I know that some system can be in a state, for example, due to the setup of values of different nodes in a graph. But how can a state be described in the case of a neural network and how can the equation above be explained other than that it is the state (or states of several timesteps as in recurrent neural networks) of a neural network?

So the equation that you mentioned is used during the backward pass in which back proppogation is performed in order to make the neural network more accurate. I think you are talking about the state during the forward pass which is completely different. In the forward pass, the neural network is simply run in order to evaluate or it is simply used as a model. The repeating module in long short term memory networks looks like this:

As you can see there are many different parts to this module. There are three main parts. The first is the forget gate layer. This layer tells the cell state or the line running across the stop what to keep. The cell state is kept by this line:
The entire network is based off of manipulating this cell state in order to get accurate results. The equation that you mentioned was related to backprop which is used to train the neural network. This is related to the cell state because it is used to calculate it during the backwards pass. @BlueMoon93 mentioned that this equation has t+1 one in it, but this is because as the recurrent neural network propogates backwards through each module the time goes from high to low. So to conclude, the cell state in an LSTM is one of the vectors that the neural network modifies based on input.


What is the purpose of the arrow $\leftarrow$ in this formula? What is the purpose of the arrow $\leftarrow$ in the formula below?

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]$$

I presume it's not the same as 'equals'.

I assume this is an iterative function. It means the current $V(S_t)$ is the sum of the previous plus some adjustment. The arrow is like an assignment.

In code, you would do

vst = vst + alpha * (gt - vst)

So vst will be overwritten.


What are the prerequisites to start using the TensorFlow Probability library? I have some familiarity with the regular Tensorflow library and have been able to create a number of working models with it. There are more than enough resources out there to get up and running and answer most questions on the standard library.

But I recently came across the video on some high-level capabilities of the Tensorflow Probability library, TensorFlow Probability: Learning with confidence (TF Dev Summit '19), and I would like to learn it.

The issue is that there are very few resources out there on TFP and given my lack of a formal background in math/statistics, I find myself aimlessly googling to get a grasp of what's going on in the docs. I'm more than willing to invest the time needed, but I just need to know where I can start in terms of resources I can access online.  Specifically, I'm looking to get the necessary domain knowledge needed to work with the library given the lack of courses/tutorials on the library itself.

Although this question is slightly primarily opinion-based and too broad (and I will probably close it as such) and a good answer will necessarily depend on your background, I will list some of the main theoretical prerequisites that everyone should ideally be familiar with before diving into TensorFlow Probability (TFP).

I am familiar with TFP, given that I've been using it for a project, but I've not used all of its functionalities, such as the bijectors. I've only used the Bayesian layers, distributions, etc., so I will try to give an answer based on my experience.

You definitely need to be familiar with the basic concepts of probability theory, such as distributions, random variables, expectations, etc. A full university-level course in probability and statistics would definitely be helpful!

If you want to use Bayesian layers, you also need to be familiar with Bayesian neural networks (BNNs). To understand BNNs, you need to understand the basic concepts of Bayesian inference (BI), given that most BNNs are based on BI. If you are already familiar with variational auto-encoders (VAEs), then it will be easier to understand BNNs. To understand BNNs, you should start reading the paper Weight Uncertainty in Neural Networks. If this paper is difficult to follow, you should first read the paper Variational Inference: A Review for Statisticians and then it may also be useful to read and be familiar with the VAE paper. Therefore, you will need to be familiar with concepts such as Kullback–Leibler divergence and Monte Carlo sampling.

The blog post Regression with Probabilistic Layers in TensorFlow Probability is the first blog post you should read. If you don't understand it, then it probably means you need to learn its prerequisites (i.e. you need to be familiar with at least linear regression).

TFP also provides several implementations of other more advanced concepts such as BNNs. The easiest example to follow is probably the logistic regression example. LR is relatively easy to follow compared to the topics I mentioned above, but, of course, you need to be familiar with logistic regression.

Of course, I cannot list all the theoretical prerequisites (and that's why your post is too broad!) and there are definitely others, but this is a start. Bear in mind that these are not trivial topics, so it is normal to get stuck.


LinUCB with Hybrid Linear Models In Li et al. (2010)'s highly cited paper, they talk about LinUCB with hybrid linear models in Section 3.2.

They motivate this by saying, "In many applications including ours, it is helpful to use features that are shared by all arms, in addition to the arm-specific ones. For example, in news article recommendation, a user may prefer only articles about politics for which this provides a mechanism."

I don't quite understand what they mean by this. Is anyone willing to provide a different example? Also it would greatly help if you can clarify what Equation 6's "$\mathbf{z}$" and "$\mathbf{x}$" refer to in the context they talk about (news recommendation), or the example you give?

Equation (6) from the paper:

  $$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$

Let's first take a look at equation 6:

$$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$

Some quick observations:

The feature vector $\mathbf{z}_{t, a}$ has time $t$ and arms $a$ as subscripts. This means that we can have different vectors $\mathbf{z}_{t, a}$ for every time step $t$ and every arm $a$.
The feature vector $\mathbf{x}_{t, a}$ has time steps $t$ and arms $a$ as subscripts. These are exactly the same subscripts we also saw in $\mathbf{z}_{t, a}$. So, again, this means that we can have different feature vectors $\mathbf{x}_{t, a}$ for every time step $t$ and every arm $a$.
The parameters or weights vector $\boldsymbol{\beta}^*$ does not have any subscripts. This is the optimal vector (the star denotes optimality) that we aim to approximate through learning. This means that we learn only a single vector $\boldsymbol{\beta}$ that is used across all timesteps and all arms (of course, since we're learning it, it does actually actually change over time in practice; not because it should inherently change over time, but because we're still learning it).
The optimal parameter vector $\boldsymbol{\theta}_a^*$ (which we aim to approximate as $\boldsymbol{\theta}_a$ through learning) has arms $a$ as a subscript. This means that, for every arm $a$, we'll learn a separate parameter vector $\boldsymbol{\theta}_a$.

First a couple of corrections, some things I don't think are correct / clear in the paper:

In the paper, as you also quoted in the question, they say "it is helpful to use features that are shared by all arms, in addition to the arm-specific ones." This is in reference to the new feature vectors $\mathbf{z}_{t, a}$ that they're introducing there. However, we've just observed above that, due to having subscripts $a$, these feature vectors are in fact arm-specific, and not shared by all arms. However, we use these feature vector to take a dot product with a learned parameter vector $\boldsymbol{\beta}$, which in turn is shared across all arms. Intuitively, this means that we're saying that these feature vectors $\mathbf{z}_{t, a}$ can have different feature values per arm, but the "importance" of every value in such a vector is the same regardless of the arm we're looking at.
Since we assume that feature vectors $\mathbf{z}_{t, a}$ can be relevant for predicting rewards, it should also be included in the expectation on the left-hand side of equation 6, which should therefore be changed to:

$$ \mathbf{E} \left[ r_{t,a} \vert \mathbf{x}_{t, a}, \mathbf{z}_{t, a} \right] = \mathbf{z}_{t, a}^{\top} \boldsymbol{\beta}^* + \mathbf{x}_{t, a}^{\top} \boldsymbol{\theta}_a^* $$

Example

Suppose at every time $t$, a new customer enters our shop, and we have to pick one of a set of books (arms $a$) to try selling to that customer (note; this is actually very similar to news article recommendation, or selecting which Ad to display, or any other common MAB problem).

In feature vectors $\mathbf{x}_{t, a}$, we want features that we expect to have different influences on our chances of a successful sale per book. For example:

Age (kids will tend to prefer certain books, adults will tend to prefer others)
A measure of how many other books in the same genre that particular customer has bought before
etc.

In feature vectors $\mathbf{z}_{t, a}$, we want features that we expect to have the same influence on our chances of a successful sale regardless of what book we're looking at (note; the feature values may still be different per arm $a$ or time step $t$, we just expect their influence or importance to be the same / similar. For example:

A variable that is e.g. $1$ if the customer $t$ has enough money to buy a book $a$, or $-1$ if they don't have enough money. Note that the feature value can differ per customer and per book (different customers have different amounts of money, and different books have different prices), but we expect the influence to always be the same; if they have enough money, they might buy it, otherwise, they're very unlikely to buy it.
Age: yes, I'm aware that I already put this feature in the other list above as well. We might want to have it in both feature vectors. We put it in the previous list because we expect there to be book-specific preference levels depending on age. However, it might also be the case that certain age groups tend to buy more books than other age groups in general, so it might be beneficial to simply have it in both feature vectors (for different expected effects).


Calculating accuracy for cross validation I'm struggling with calculating accuracy
when I do cross-validation for a deep learning model.
I have two candidates for doing this.
1. Train a model with 10 different folds and get the best accuracy of them(so I get 10 best accuracies) and average them.
2. Train a model with 10 different folds and get 10 accuracy learning curves. Now, average these learning curves by calculating the mean of 10 accuracies of each epoch. So now we get one averaged accuracy learning curve and find the highest accuracy from this curve.

Among these two candidates which one is correct??

I guess you could train your model with 10 different folds and in each fold calculate the average accuracy. So you would have 10 values - one corresponding to each fold. And then take the mean of all of them to get the average accuracy of your model.

Your first option doesn't seem great because you take the highest accuracy among folds. If for some reason, the variance between accuracies is high for a fold, this would bias your numbers. Taking mean or maybe median of accuracies might be more reasonable.

Does that help?


How is the performance of a model affected by adding a ReLU to fully connected layers? How significant is adding a ReLU to fully connected (FC) layers? Is it necessary, or how is the performance of a model affected by adding ReLU to FC layers?

ReLU is piecewise linear function that outputs the received input directly if it's positive, or outputs a zero. i.e., $max(0, x)$

How significant is adding relu to full connected layers?
ReLU, being an activation function, will determine what the output of the nodes in your FCs are. Since it's a non-linear function, one significance is it will allow the nodes in your model to learn  complex mappings between the inputs and the outputs. Compared to using a linear function, it will allow back-propagation since it has a derivative, allowing the neural network to have the advantage of stacking of multiple FC layers.
Is it necessary?
ReLU (and non-linear activation functions in general) will introduce non-linear properties in a neural network that enables it to learn more complex arbitrary structures in the inputs. Without activation functions between the layers, your neural network will simply be a linear function, regardless of the number of layers it has. Why? A linear function + linear function gives a linear function. Additionally, see this answer.
How is the performance affected by adding ReLU?
Compared to no activation function at all, it will be slower to train but will only behave like a linear regression model. So ReLU will increase the power of the model by making it non-linear.
However, compared to other non-linear activation functions like tanH, ReLU will speed up training as (1) its computation step is cheaper i.e., $0.0$ or $x$ without additional operations (2) its gradient just depends on the sign of the input $x$. See this answer


How to keep track of the subject/entity in a sentence? I'm working on Sentiment Analysis, using HuggingFace to perform sentiment analysis on articles
 classifier = pipeline('sentiment-analysis', model="nlptown/bert-base-multilingual-uncased-sentiment")
 classifier(['We are very happy to show you the  Transformers library.',  "We hope you don't hate it."])

This returns

label: POSITIVE, with score: 0.9998

label: NEGATIVE, with score: 0.5309

Now I'm trying to understand how to keep track of a subject when performing the sentiment analysis.
Suppose I'm given a sentence like this.

StackExchange is a great website. It helps users answer questions.  Hopefully, someone will help answer this question.

I would like to keep track of the subject when performing sentiment analysis. In the example above, in the 2nd sentence 'it' refers to 'StackExchange'. I would like to be able to do track a subject between sentences.
Now, I could try to manually try to parse this by finding the verb and trying to figure find the phrase that comes before it. However, it doesn't sound like a very safe or accurate way to find the subject.
Alternatively, I could train similar to a Named Entity Recognition. However, finding a dataset for this is very hard, and training it would be very time-consuming.
How can I keep track of an entity within an article?

What you're describing is known as coreference resolution. More specifically, this example is anaphora resolution. The short answer is that this is an open research question and there is no well-established solution.
You mentioned Hugging Face in your question. The neuralcoref module in spaCy is itself from Hugging Face (note the reflexive anaphor used for emphasis in this sentence). If you're not a spaCy kind of person, then there's also Stanford's CoreNLP in Java that has coreference resolution. A Python wrapper is also available.
I also wanted to address a couple other topics you mentioned. You are right in that they're all somewhat connected. But you need to scope down your goal/research question because what you're aiming to achieve is too difficult for a first task. Named entity recognition, constituency parsing, and sentiment analysis. Pick just one to focus on.


What do we mean by saying "VC dimension gives a LOOSE, not TIGHT bound"? From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice.

But, the literature (i.e. Learning from Data) states that VC gives a loose bound, and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension. So, a good rule of thumb would be to require at least 10xVC dimension examples in order to get decent generalization.

I am having trouble interpreting what loose bound means. Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.

But, the literature (i.e. Learning from Data) states that VC gives a loose bound and that in real applications, learning models with lower VC dimension tend to generalize better than those with higher VC dimension.

It's true that people often use techniques such as regularisation to avoid over-parametrized models. However, I think it's dangerous to say that, in real applications, those models are really generalizing better, given that you're typically assessing their generalization ability by using a finite validation dataset (possibly selected in a biased way). Moreover, note that the validation dataset is often ignored in certain bounds and the only thing that is taken into account is the expected risk and the empirical risk (on the training data).

In any case, the $\mathcal{VC}$ bounds may be "loose" because

the $\mathcal{VC}$ dimension is often expressed with the big-$\mathcal{O}$ notation (e.g. see this answer)
the bounds often involve probabilities and uncertainties (e.g. see this other answer)
there aren't stricter bounds (i.e. no one found better bounds yet)

  Is the VC generalization bound loose due to its universality? Meaning, its results apply to all hypothesis sets, learning algorithms, input spaces, probability distributions, and binary target functions.

I think the answer is yes. In fact, often, the specific tasks or learning algorithms are ignored in the analyses, but, in general, you may exploit your knowledge of the problem to improve e.g. the number of useful examples that the learning algorithm could use.


Would linked Watson supercomputers be even "smarter" than one Watson? If you had a web of linked Watson-level super-computers, would they be more effective at problem-solving than a single Watson computer alone?

For example, if you asked the Watson-web to diagnose a person's as-yet-undiagnosed disease, would the web be able to do so more quickly?

I guess that they would be only marginally better. And be aware that Watson itself is already a cluster of (quite big) computers (citing Wikipedia):

  Watson employs a cluster of ninety IBM Power 750 servers, each of which uses a 3.5 GHz POWER7 eight-core processor, with four threads per core. In total, the system has 2,880 POWER7 processor threads and 16 terabytes of RAM

Because of the rules of Jeopardy, Watson was not allowed to use the Web during the game. At some very high level, it contains a digested cache of some of the Web contents. Giving access to the Internet would improve slightly Watson's performance, but not that much.

  if you asked the Watson-web to diagnose a person's as-yet-undiagnosed disease, would the web be able to do so more quickly?

Even if by "web" you mean a more powerful cluster accessing the entire Internet, I don't think that it would answer much more quickly & accurately.

AI is a diversity of sub-domains, and is not advancing as dramatically as some believe. It follows a gradual progression, with in some limited fields (playing Go, or Jeopardy) some spectacular progresses. See also Everything but the essential blog entry by J.Pitrat.


Difference in continuing and episodic cases in Sutton and Barto - Introduction to RL, exercise 3.5 Excercise 3.5 The equastions in Section 3.1 are for the continuing
  case and need to be modified (very slightly) to apply to episodic
  tasks. Show that you know the modifications needed by giving the
  modified version of (3.3).

$\displaystyle\sum_{s^{\prime} \in S} \displaystyle\sum_{r \in R} = p(s^{\prime}, r
| s,a) = 1$ , for all $s\in S, a \in A(s)$    (3.3)

Is it just about final states? So for $s \in S$ when S is not final?

Is it just about final states? So for $s \in S$ when S is not final?

You are thinking the right way, but to represent what you mean you don't need to write out "when $s$ is not final" - although that would be fine (and is used in some places), there is a more concise way of saying that given to you by the book.

As this is a formal exercise from the book, I don't want to write out an answer that could be cut&paste for all students.

Instead I suggest you take a look at the notations section at the beginning of the book, and find how Sutton & Barto use different set labels for all states including terminal states, and all states excluding terminal states. Also, check carefully which of those sets needs to be summed over.


How can I automate the choice of the topology of a neural network for an arbitrary problem? Assume that I want to solve an issue with a neural network that either I can't fit to already existing topologies (perceptron, Konohen, etc) or I'm simply not aware of the existence of those or I'm unable to understand their mechanics and I rely on my own instead.

How can I automate the choice of the topology (that is, the number of layers, the type of activations, the type and direction of the connections, etc.) of a neural network for an arbitrary problem?

I'm a beginner, yet I realized that in some topologies (or, at least in perceptrons) it is very hard if not impossible to understand the inner mechanics as the neurons of the hidden layers don't express any mathematically meaningful context.

I think in this case, you'll probably want to use a genetic algorithm to generate a topology rather than working on your own. I personally like NEAT (NeuroEvolution of Augmenting Topologies).

The original NEAT paper involves evolving weights for connections, but if you only want a topology, you can use a weighting algorithm instead. You can also mix activation functions if you aren't sure which to use. Here is an example of using backpropagation and multiple neuron types.


How to identify too small network in reinforcement learning? I am using Open AI's code to do a RL task on an environment that I built myself.

I tried some network architectures, and they all converge, faster or slower on CartPole.

On my environment, the reward seems not to converge, and keeps flickering forever.

I suspect the neural network is too small, but I want to confirm my belief before going the route of researching the architecture.

How can I confirm that the architecture is the problem and not anything else in a neural network reinforcement learning task?

Check the function loss.
It might be that your environment is impossible to learn. However, most likely the network simply can't handle it. By measuring the loss during the learning stage, if you find it is always very high and does not decrease, it's a strong indication this might be the issue.
Because the network is too simple, when you optimize for some states, you ruin others. There is not formal way to find out if this is the case, but since the same algorithm works elsewhere, it's either a problem of your environment, or of the network.


Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$? I am new to Reinforcement learning and am currently reading up on the estimation of Q $\pi(s, a)$ values using MC epsilon-soft approach and chanced upon this algorithm. The link to the algorithm is found from this website.

https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/

def monte_carlo_e_soft(env, episodes=100, policy=None, epsilon=0.01):

if not policy:
    policy = create_random_policy(env)
# Create an empty dictionary to store state action values
Q = create_state_action_dictionary(env, policy)

# Empty dictionary for storing rewards for each state-action pair
returns = {} # 3.

for _ in range(episodes): # Looping through episodes
    G = 0 # Store cumulative reward in G (initialized at 0)
    episode = run_game(env=env, policy=policy, display=False) # Store state, action and value respectively

    # for loop through reversed indices of episode array.
    # The logic behind it being reversed is that the eventual reward would be at the end.
    # So we have to go back from the last timestep to the first one propagating result from the future.

    # episodes = [[s1,a1,r1], [s2,a2,r2], ... [Sn, an, Rn]]
    for i in reversed(range(0, len(episode))):
        s_t, a_t, r_t = episode[i]
        state_action = (s_t, a_t)
        G += r_t # Increment total reward by reward on current timestep

        # if state - action pair not found in the preceeding episodes,
        # then this is the only time the state appears in this episode.

        if not state_action in [(x[0], x[1]) for x in episode[0:i]]: #
            # if returns dict contains a state action pair from prev episodes,
            # append the curr reward to this dict
            if returns.get(state_action):
                returns[state_action].append(G)
            else:
                # create new dictionary entry with reward
                returns[state_action] = [G]

            # returns is a dictionary that maps (s,a) : [G1,G2, ...]
            # Once reward is found for this state in current episode,
            # average the reward.
            Q[s_t][a_t] = sum(returns[state_action]) / len(returns[state_action]) # Average reward across episodes

            # Finding the action with maximum value.

            Q_list = list(map(lambda x: x[1], Q[s_t].items()))
            indices = [i for i, x in enumerate(Q_list) if x == max(Q_list)]
            max_Q = random.choice(indices)

            A_star = max_Q # 14.

            # Update action probability for s_t in policy
            for a in policy[s_t].items():
                if a[0] == A_star:
                    policy[s_t][a[0]] = 1 - epsilon + (epsilon / abs(sum(policy[s_t].values())))
                else:
                    policy[s_t][a[0]] = (epsilon / abs(sum(policy[s_t].values())))

return policy

This algorithm computes the $Q(s, a)$ for all state action value pairs that the policy follows. If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q_{\pi^*}(s, a)$ (optimal Q function)?

From this website, they claim to have been able to find the optimal policy when running through this algorithm.

I have read up a bit on Q-learning and the update equation is different from MC epsilon-soft. However, I can't seem to understand clearly how these 2 approaches are different.

If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q_{\pi^*}(s, a)$ (optimal Q function)?

Assuming that the estimates for $Q_{\pi}(s,a)$ have converged to close to correct values from many samples, then a policy based on $\pi'(s) = \text{argmax}_a Q_{\pi}(s,a)$ is not guaranteed to be an optimal policy unless the policy $\pi$ being measured is already the optimal policy.

This is because the action value $Q_{\pi}(s,a)$ gives the expected future reward from taking action $a$ in state $s$, and from that point on following the policy $\pi$. The function does not, by itself, adapt to the idea that you might change other action choices as well. It is a measure of immediate differences between action choices at any given time step. Therefore if there are any long-term dependencies where your action choice at $t$ would be different if only you could guarantee a certain choice at $t+1$ or later, this cannot be resolved by simply taking the maximum $Q_{\pi}(s,a)$ when $\pi$ was a simple random policy.

However, if you do decide to change the policy such that you always follow actions $\pi'(s) = \text{argmax}_a Q_{\pi}(s,a)$ for all states, then you can say this: For each state, $V_{\pi'}(s) \ge V_{\pi}(s)$. I.e.  $\pi'(s)$ is no worse than, and may be a strict improvement over $\pi(s)$. Better than that, $\pi'(s)$ will be a strict improvment over $\pi(s)$ if $Q_{\pi}(s,a)$ is accurate and $\pi(s)$ is not already the optimal policy $\pi^*(s)$. This is the basis for the Policy Improvement Theorem which shows that if you repeat the process of measuring $Q_{\pi^k}$ and then creating a new policy $\pi^{k+1}(s) = \text{argmax}_a Q_{\pi^k}(s,a)$ that you will eventually find the optimal policy. You only have to repeat your idea many times to eventually find $\pi^*$

The Dynamic Programming technique Policy Iteration does this exactly. All other value-based Reinforcement Learning methods are variations of this idea and rely at least in part on this proof.


Why are CNN binary classifier output probability distributions often skewed? I've been working on a lot of simple resnet18 binary classifiers lately and I've started to notice that the probability distributions are often skewed one way or the other. This figure shows one such example. The red and blue color code the negative and positive ground truths respectively. And the bottom axis is the output prediction of the binary classifier (sigmoid activated output neuron). Notice how the red is more bunched towards 0, but the blue has quite some spread.

At first I began to reason this to myself with arguments like "well the positive clues in the image have a small footprint, so they are hard to find, therefore the model should be unsure about positives more of the time."
Later I found oppositely skewed distributions and tried to say "well the positive clues in the image have a small footprint, so it might be easy to confuse some other things for the positive clues, therefore the model should be unsure about negatives more of the time"
You can see where I'm going with this. It took me training up quite a few models like this in a short amount of time to realise I was kidding myself. Even the exact same architecture and similar dataset may produce a different skew over different training runs. And if you think about it, negative probability is just the complement of positive probability, so any argument you make in favor of one over the other can be easily reversed.
So what's influencing this skew? Why is there a skew at all? If there's a skew, is it because of something "real", or is it just random?
These all may seem like philosophical questions, but they have great practical significance. Because that skew basically tells me where I should put my decision threshold in production level inference!

Yes, due to this issue, you should use temperature scaling after training your model. It will calibrate your probability and you will start to get the same kind of distributions. Here are a good article along with implementation on it.


Does TD(0) prediction require Robbins-Monro conditions to converge to the value function? Does the learning rate parameter $\alpha$ require the Robbins-Monro conditions below for the TD(0) algorithm to converge to the true value function of a policy?

$$\sum \alpha_t =\infty \quad \text{and}\quad \sum \alpha^{2}_t <\infty$$

The paper Convergence of Q-learning: A Simple Proof (by Francisco S. Melo) shows (theorem 1) that Q-learning, a TD(0) algorithm, converges with probability 1 to the optimal Q-function as long as the Robbins-Monro conditions, for all combinations of states and actions, are satisfied. In other words, the Robbins-Monro conditions are sufficient for Q-learning to converge to the optimal Q-function in the case of a finite MDP. The proof of theorem 1 uses another theorem from stochastic approximation (theorem 2).

You are interested in the prediction problem, that is, the problem of predicting the expected return (i.e. a value function) from a fixed policy. However, Q-learning is also a control algorithm, given that it can find the optimal policy from the corresponding learned Q-function.

See also the question Why doesn't Q-learning converge when using function approximation?.


When adding a feature is useless? "simple" issue:
I'm building a model, where from a feature set A I want to predict a target set C; I need to understand if another feature set B, together with A, can improve my model performances, instead of using only A.
Now I want to check if I can predict B directly from A, since, in my understanding, this would mean that info on B is already inside A.
If I get good predictions when testing the model A -> B, is it true then that adding B to A in predicting C is completely useless ?
And furthermore, are there smarter ways to decide if/when a feature is useless ?

Now I want to check if I can predict B directly from A, since, in my understanding, this would mean that info on B is already inside A.

This will help inform you how much redundancy there is between A and B. However, even if you can predict B with 100% accuracy from A, you may still be better off using A+B (instead of A alone) to predict C.

If I get good predictions when testing the model A -> B, is it true then that adding B to A in predicting C is completely useless ?

It is an indicator that adding B probably won't make great improvements to your prediction of C.
The only way to be sure is to make the model that uses A+B and compare its performance against a model that uses only A. If collecting B costs time or other resources, then perform this check by limiting both models to only learn from the subset of data where you have all of A, B, C available.

And furthermore, are there smarter ways to decide if/when a feature is useless ?

Another thing you can do is to try and predict C from B alone. It doesn't need to score well, but may indicate that something useful is in the data if you get better than chance results. Scoring badly unfortunately doesn't rule it out for working well in combination with A.
Generally, if you cannot reason it clearly one way or another from theory, the accepted method is to build variations of your model with and without a feature and test them. You do have to be aware of the chances of spurious correlation though, so usually you need to have some basis or motivation for considering any new feature, from your domain knowledge that applies to the model.


Training network to detect spelling mistakes I would like to know what kind of dataset I need (to prepare) for training the network to recognize the spelling mistakes in individual words for English text.

Given the large database of words, having correct one for each incorrect. What kind of input is more efficient for that tasks? Is it using one input per each letter, syllable, whole word or I should use different pattern syllable?

Then the input should be incorrect word, output correct, and if the word doesn't need correction, then both input and output should be the same. Is that the right approach?

I'd personally be more inclined to try longstanding deterministic methods such as Damerau (for typing errors) or Soundex (for homonyms arising from transcribed speech). At the very least, I'd use those as a baseline for any more 'AI-based' approach.


What are some resources on computational learning theory? Pretty soon I will be finishing up Understanding Machine Learning: From Theory to Algorithms by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble finding a book that could come after this. Ultimately, my goal is to read papers in JMLR's COLT.

Is there a book similar to "Understanding Machine Learning: From Theory to Algorithms" that would progress my knowledge further and would go well after reading UML?
Is there any other materials (not a book) that could allow me to learn more or prepare me for reading a journal like the one mentioned above?

(Also, taking courses in this is not really an option, so this will be for self-study).

(Note that I have also asked this question here on TCS SE, but it was recommended I also ask here.)

Although I have only partially read (or not read at all) some of the following resources and some of these resources may not cover more advanced topics than the ones presented in the book you are reading, I think they can still be useful for your purposes, so I will share them with you.
I would also like to note that if you understand the contents of the book you are currently reading, you are probably already prepared for reading some (if not most of) the research papers you wish to read. Initially, you may find them a little bit too succinct and sometimes unclear or complex, but you need to get used to this format, so there's nothing stopping you from trying to read them and learn even more by doing this exercise.
Books

An Introduction to Computational Learning Theory (1994) by Kearns and Vazirani

No free PDF available

The Nature of Statistical Learning Theory (1995, 2000) by Vapnik
Machine Learning (1997) by Mitchell
Statistical Learning Theory (1998) by Vapnik
Prediction, Learning, and Games (2006) by Cesa-Bianchi and Lugosi
Foundations of Machine Learning (2012) by Mohri et al.
Boosting: Foundations and Algorithms (2012) by Schapire and Freund
Bandit Algorithms (2020) by Lattimore and Szepesvári (with associated solutions to the exercises)

Papers

A theory of the learnable (1984) by Valiant
An overview of statistical learning theory (1999) by Vapnik
Introduction to Statistical Learning Theory (2014) by Bousquet et al.

Courses (videos)

Learning from Data (Caltech) (2012) by Yaser Abu-Mostafa
Machine Learning Theory (2015) by Shai Ben-David

Lecture notes

Introduction to Machine Learning (2009) by Shai Shalev-Shwartz

Concentration-of-measure inequalities (2009) by Gábor Lugosi

Stat 928: Statistical Learning Theory (2011) by Sham Kakades

COMS E6253, Advanced Topics in Computational Learning Theory (2012) Rocco Servedio

9.520: Statistical Learning Theory and Applications, Spring 2012 by Tomaso Poggio et al.

STAT928: Statistical Learning Theory and Sequential Prediction (2014) by Alexander Rakhlin and Karthik Sridharan

ECE 543, Statistical Learning Theory (2019) by Bruce Hajek and Maxim Raginsky

Other
See also this list of resources https://kiranvodrahalli.github.io/links/#resources-notes-textbooks-monographs-classes-etc compiled by Kiran Vodrahalli.


Which reward function works for recommendation systems using knowledge graphs? I've been reading this paper on recommendation systems using reinforcement learning (RL) and knowledge graphs (KGs).

To give some background, the graph has several (finitely many) entities, of which some are user entities and others are item entities. The goal is to recommend items to users, i.e. to find a recommendation set of items for every user such that the user and the corresponding items are connected by one reasoning path.

I'm attaching an example of such a graph for more clarity (from the paper itself) -

In the paper above, they say

  First, we do not have pre-defined targeted items for any user, so it is not applicable to use a binary reward indicating whether the user interacts with the item or not. A better design of the reward function is to incorporate the uncertainty of how an item is relevant to a user based on the rich heterogeneous information given by the knowledge graph.

I'm not able to understand the above extract, which talks about the reward function to use - binary, or something else. A detailed explanation of what the author is trying to convey in the above extract would really help.

I found the answer further into the paper! I'll post it here for everyone.

Given any user, there is no pre-known targeted item in the KGRE-Rec (Knowledge Graph Reasoning for Explainable Recommendation) problem, so it is unfeasible to consider binary rewards indicating whether the agent has reached a target or not.

Instead, the agent is encouraged to explore as many “good” paths
as possible. In the context of recommendations, a “good” path is one that leads to an item that a user will interact with, with high probability. To this end, a soft reward is given only for the terminal state $s_T = (u,e_T,h_T)$ based on a scoring function $f(u,i)$. The terminal reward $R_T$ is given as -

where the value of $R_T$ is normalized to the range $[0,1]$. Details about $f(u,i)$, the scoring function, can be found in the paper.

References:

Reinforcement Knowledge Graph Reasoning for Explainable
Recommendation [Yikun Xian, Zuohui Fu, S. Muthukrishnan, Gerard
de Melo, Yongfeng Zhang]


What is the relationship between the reward function and the value function? To clarify it in my head, the value function calculates how 'good' it is to be in a certain state by summing all future (discounted) rewards, while the reward function is what the value function uses to 'generate' those rewards for it to use in the calculation of how 'good' it is to be in the state?

I think it is pedagogically useful to distinguish between the theory (equations) and the practice (algorithms).
If you're talking about the definition of the value function (the theory)
\begin{align}
v_{\pi}(s)
& \dot{=} \mathbb{E}_{\pi} \left[ G_t \mid S_t = s \right]\\
&= \mathbb{E}_{\pi} \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \bigl\vert S_t = s \right]\\
\end{align}
for all $s \in \mathcal{S}$, where $\dot{=}$ means "is defined as" and $\mathcal{S}$ is the state space, then the value function can be defined in terms of the reward, as it can be clearly seen above. (Note that $R_{t+k+1}$, $G$ and $S_t$ are random variables, and, in fact, expectations are taken with respect to random variables).
The definition above can actually be expanded to be a Bellman equation (i.e. a recursive equation) defined in terms of the reward function $R(s, a)$ of the underlying MDP. However, often, rather than the notation $R(s, a)$, you will see $p(s', r \mid s, a)$ (which represents the combination of the transition probability function and the reward function). Consequently, the value is a function of the reward.
If you're estimating a value function (the practice), e.g. using Q-learning, you don't necessarily use the reward function of the Markov decision process. You can estimate the value function by just observing the rewards that you receive while exploring the environment, without really knowing the reward function. But, by exploring the environment, you can actually estimate the reward function. For example, if every time you're in state $s$ you take action $a$ and you receive reward $r$, then you already know something about the actual underlying reward function. If you explore enough the MDP, you could potentially learn the reward function too (unless it keeps on changing, in that case, it may be more difficult to learn it).
To conclude, yes, value functions are certainly very related to reward functions and rewards, in ways that you immediately see from the equations that define the value functions.


When using PCA for dimensionality reduction of the feature vectors to speed up learning, how do I know that I'm not letting the model overfit? I'm following Andrew Ng's course for Machine Learning and I just don't quite understand the following.
Using PCA to speed up learning

Using PCA to reduce the number of features, thus lowering the chances for overfitting

Looking at these two separately, they make perfect sense. But practically speaking, how am I going to know that, when my intention is to speed up learning, I'm not letting the model over-fit?
Do I've to find a middle-ground between these two scenarios when applying PCA? If so how exactly can I do that?

I'm not sure if I understood your question correctly, but here's my take anyway.
So, PCA is a technique that you can apply to data to reduce the number of features.
In return, (i) this can speed-up training, as there are less features to do computation with, (ii) and can prevent overfitting, as you lose some information on your data.
To detect overfitting, you usually monitor the validation and training losses during the training. If your training loss decreases, but your validation loss stays constant or increases, it's likely that your model is overfitting on the training data. In practice, this means your model generalizes worse and you can observe this by measuring the test accuracy.
All in all, you can apply PCA, train a new model, and measure your model's test accuracy to see if PCA has successfully prevented overfitting. In case it didn't, you can re-train with other regularization techniques such as weight decay and so on.
After your edit that put the slides
Basically, what slides claim is, PCA could be a bad way to prevent overfitting when compared to using standard regularization methods. To actually see whether this is the case, the standard way would be measuring your model's performance on a validation dataset. So, if PCA throws away lots of information, and hence causes your model to underfit, your validation accuracy should rather be poor wrt to using standard regularization techniques.


Interested in what Google AI can do. Know nothing about AI at all Trying to figure out what Google is offering in the article at this link
https://www.nytimes.com/2018/01/17/technology/google-sells-ai.html.

I also need to know if their offerings are limited to visual scans and if so, the range of photographical types it can work with (heat maps for example, or continuous video feed).

We are a small road construction company looking for ways to start using AI on some of our projects so I am in the process of gathering information on exactly what it can do.

Google is just one of the vendors for AI and their initial AI self-service is limited to image analysis. Their are other AI vendors (Microsoft, Amazon) that have other services also. AI is definitely capable of continuous video feed analysis. The self-driving car technology uses live video feed analysis. Are you exploring AI in general or specific use cases? I did a presentation on AI use cases for oil & gas engineering and construction that could give you some ideas.

AI Vision 2020 for Oil & Gas


Is there a probabilistic version of minimax? How would a probabilistic version of minimax work?

For example, we may choose a move that could result in a very bad outcome, but that outcome might just be extremely unlikely so we might think it would be worth the risk.

Yes, there is at least one probabilistic version of minimax, which is called expectiminimax. In expectiminimax, in addition to min and max nodes, there are also chance nodes, which perform a weighted sum of the successors, so the probabilities associated with chance nodes must be known. Given that expectiminimax assumes the existence of random events (represented by the chance nodes), the decisions are thus based on expected values.

Section 5.5 of the book Artificial Intelligence: A Modern Approach provides a description of the expectiminimax algorithm, which was introduced by Donald Michie in Game-playing and game-learning automata (1966). The paper Optimal strategy in games with chance nodes (2007) also gives a decent description of the expectiminimax algorithm.


How well can CNN for bounding box detection generalise? Suppose a CNN is trained to detect bounding box of a certain type of object (people, cars, houses, etc.)

If each image in the training set contains just one object (and its corresponding bounding box), how well can a CNN generalize to pick up all objects if the input for prediction contains multiple objects?

Should the training images be downsampled in order for the CNN to pick out multiple objects in the prediction?

I don't have a specific one in mind. I was just curious about the general behavior.

I suggest you to go through the r-cnn paper or go through a tutorial on it . CNNs transform the image into high dimensional vector in their last layer , in case of classification this vector is sent to a "softmax" layer , in case of bounding box regression , four values :length , breadth , location of one of the points of the bounding box , are regressed from this vector , so if you use a cnn with one regression head you end up with one bounding box irrespective of the training set.


Dice loss gives binary output whereas binary crossentropy produces probability output map On recommendation of Kanak on stackoverflow I am posting this question here:

Currently I am experimenting with various loss functions and optimizers for my binary image segmentation problem. The loss functions that I use in my Unet however give different output segmentation maps.

I have a highly imbalanced dataset, thus I am trying dice loss for which the customized function is given below.

    def dice_coef(y_true, y_pred, smooth=1):
        """
        Dice = (2*|X & Y|)/ (|X|+ |Y|)
             =  2*sum(|A*B|)/(sum(A^2)+sum(B^2))
        ref: https://arxiv.org/pdf/1606.04797v1.pdf
        """
        intersection = K.sum(K.abs(y_true * y_pred), axis=-1)
        return (2. * intersection + smooth) / (K.sum(K.square(y_true), -1) + K.sum(K.square(y_pred), -1) + smooth)

    def dice_coef_loss(y_true, y_pred):
        return 1 - dice_coef(y_true, y_pred)

Binary cross entropy results in a probability output map, where each pixel has a color intensity that represents the chance of that pixel being the positive or negative class. However, when I use the dice loss function, the output is not a probability map but the pixels are classed as either 0 or 1.

My questions are:

1.How is it possible that these different loss functions have these vastly different results?

Is there a way to customize the dice loss function so that the output segmentation map is a probability map similar to the one of binary crossentropy loss.

The probability map / output isn't produced by your loss function, but your output layer, which is activated either by softmax or sigmoid.

In other words, your dice loss output is also a probability map. It's simply very confident in itself. If you forget about the problem with potential overfitting for a moment and train your binary crossentropy model longer, the probability values will eventually all converge to the 2 ends (0 and 1).

In my experience, dice loss and IOU tend to converge much faster than binary crossentropy for semantic segmentation, so if you stop the training early on, dice loss will produce a probability map that resembles a binarized output more so than binary crossentropy.


How should I define the loss function for a multi-object detection problem? I'm trying to create a text recognition project using CNN. I need help regarding the text detection task.

I have the training images and bounding box details for them. But I'm unable to figure out how to create the loss function.

Can anyone help me by telling how to take the output from the CNN model and compare it to the bounding box labels?

Okay so your CNN model is taking an Image and outputting the bounding boxes for them. That means the last layer of CNN model must be having four outputs which are generating real numbers. This is a regression problem.
In that case, you can take L1 loss (mean absolute error) or L2 loss (mean square error) as your loss function. I have created a similar project, I have used L1 loss.
Suppose your input image is x and predicted_bb is the model output and real_bb is your original bounding box for image x. Then you should proceed as follows
predicted_bb = model(x)

# CALCULATE LOSS BETWEEN THE ACTUAL & PREDICTED BB COORDINATES

loss_bb = torch.nn.functional.l1_loss(predicted_bb, real_bb, reduction="none").sum(1)

# SET GRADIENTS TO ZERO

optimizer.zero_grad()

# BACKPROPOGATE THE LOSS

loss.backward()

For tensorflow keras
predicted_bb = Dense(4, activation='relu')(x)

model = Model(inputs = image_input, outputs = [predicted_bb])
model.compile(loss=['mae'], optimizer='adam', metrics =['accuracy'])


Is the play of strong Chess AI easily distinguishable from human play? I don't play nearly enough Chess to be able to answer.  For context, AlphaGo is stronger than the current strongest human player, but AlphaGo's game play has been cast as "inhuman" in the sense that it doesn't resemble human play. (In Go, this can involve aesthetic qualities.)

Really I'm wondering about "narrow" application of the Imitation Game/Turing Test, where one might design an automata to play more like a human, so that human players would be unable to determine if their opponent was a human or an automata.

There are three cases in which it is easily possible to distinguish strong AI play from the strong human play:

The AI is playing at superhuman skill level

This seems obvious, but I want to mention it for the sake of completeness. The current skill ceiling of top-level chess is well known and an opponent playing way above this skill ceiling must either be an AI or a chess guru who hid in a cave for the last centuries. Applying Occam's razor I would go with the AI. So to mimic human play the AI must make sure to stay at a human ELO level.

The AI plays an obvious weak move in a losing or strange situation

When the AI is in a bad situation and still tries to win the game without any reasonable move available, it might be tempted to play an obviously bad move, because the decision engine assigns it the highest probability of success. Such moves are considered rude at high-level play and a human player would not play them but resign. The most famous example of this is move 101 in the fourth game between Lee Sedol and AlphaGo. AlphaGo just lost a big group but still played T9 to extend it even further. This is a move a rookie player stops making after his first 10 games because it is that obvious that it does not work. A professional go player would never do this under normal circumstances. AlphaGo was out of options and played the rude move instead of resigning. This doesn't mean an AI cannot be programmed to avoid such behavior, but dire or simply very strange situations might induce moves like this, giving the nature of the AI away.

Other factors than the actual moves are considered

Depending on the test scenario, the AI might give away its nature through other means than the actual moves. Things like moving too fast or playing without breaks for hours. But I assume the question was just focused on the actual play and not the surrounding factors.
Those are the obvious examples where an AI might give away his true nature. I highly doubt that a strong AI, playing at the strong human level, can really be identified because of his "inhuman" style. I think it is more of a psychological pitfall to consider innovative moves from an AI "inhuman" and the same move from a pro player as "brilliant" if you know who is who. I am an amateur 3dan Go player - far from the top but with several years of experience under the belt - and at least I wasn't able to see anything "inhuman" in AlphaGos play so far. Ingo, it is well known that there are different styles of play, and after reviewing enough pro games one gets a sense of which player might have been educated in Korea, China, or Japan because certain patterns of strategies are more or less common in those countries. The lack of such an individual nuance might be an indication, that the player is actually a strong AI, but I am confident, that even the strongest pro wouldn't have a high success rate guessing who is human and who is the AI.
In chess, there are significantly fewer options at every move, many fixed patterns especially in the opening, and therefore less room for an individual style. Therefore I consider the same challenge even more difficult than in go. So if an AI has reason to "play like a human", this should be possible with the current level of AI technology.


How feasible is it to perform pose estimation on a Raspberry Pi 4 using a Pi-Cam? I want to estimate hand poses and recognize gestures using an open-source library like OpenPose on live video. Considering the fact that such libraries are very computationally intensive.

How likely is it that it will run on a Raspberry Pi 4 using a Pi-Cam while giving me something above 15 fps? Assume that the models are pre-trained.

If using TFLite python API, you may reach to 1/2 FPS. On downscaled custom Pose architectures you may get more FPS. You can try the TFLite c++ API as well, it might be a bit faster than the python one.
To reach more than this you would need a TPU or a library that could use GPU computation of the Pi. Nevertheless, I doubt that it would reach 15 FPS with OpenPose open-source library.


What do we mean by "infrequent features"? I am reading this blog post: https://ruder.io/optimizing-gradient-descent/index.html. In the section about AdaGrad, it says:

It adapts the learning rate to the parameters, performing smaller updates (i.e. low learning rates) for parameters associated with frequently occurring features, and larger updates (i.e. high learning rates) for parameters associated with infrequent features.

But I am not sure about the meaning of infrequent features: is it that the value of a given feature changes rarely?

We will describe the input to the network as a vector, called features vector. Each component of this vector is usually related to some "real world" information, by example "age of the person", "number of atoms", "...".
In very usual situations, a specific component of the input vector will have near than always the same value. This is more usual in binary components or components that has a small set of possible values.
However, usually in the cases where this component has a value different from the most usual one, this component is very important and informative.
These values of this kind of components are called infrequent features.
(example: "rains?" is in my city 99.9% of time "false". However, when it is true, it is a key factor to all questions about the behavior of the population).
The problem with these features: as unusual values are infrequent, the net has few chances to learn from them, and some learning algorithms could fail to give them the weight that they must (taken into account that, as has been said, these components are very important when they take a value different to the most frequent one).
Some adaptive learning rate algorithms as AdaGrad tries to solve this issue.


What are the keys and values of the attention model for the encoder and decoder in the "Attention Is All You Need" paper? I have recently encountered the paper on NLP. It is very new to me and I am still unable to see how that works. I have used all the resources over there from the original paper to Youtube videos and the very famous "Illustrated Transformer".

Suppose I have a training example of "I am a student" and I have the respective French as "Je suis etudient".

I want to know how these 3 words are converted to 4 words. What are the query, keys, values?

This is my understanding of the topic so far.

The encoder part is:

Query: a single word embedded in a vector form. such as "I" expressed as a vector of length 5 as $[.2, 0.1, 0.4, 0.9, 0.44]$.
Keys: the matrix of all the vectors or in simple words, a matrix that has all the words from a sentence in the form of embeddings.
Values = Keys

For decoder:

Query: the input word in the form of a vector (which is output given by the decoder from the previous pass).
Keys = values = outputs from the encoder's layers.

BUT there are 2 different attention layers and one of which do not use the encoder's output at all. So, what are the keys and values now? (I think they are just like encoder, but just the generated until that pass)?

BUT there are 2 different attention layers and one of which do not use the encoder’s output at all. So, what are the keys and values
now?

The first attention layer in the decoder is the "Masked Multi-Head Attention" layer and is the self-attention layer, calculating how much each word is related to each word in the same sentence. However, our aim in the decoder is to generate the next French word and so for any given output French word we can use all the English words but only the French words previously seen in the sentence. We, therefore, "mask" the words that appear later in the French sentence by transforming these to 0 so the attention network cannot use them.

How these 3 words are converted to 4 words

The second attention block in the decoder is where the English to French word mapping happens. We have a query for every output position in the French sentence and a key/value for every English input word. We calculate relevance scores from the dot product of the query and key and then obtain output scores for each predicted word from multiplying the relevance and value. The following diagram is useful to visualise how, for each predicted word, we can have relevance scores that can predict that one English word can be translated to multiple, or no French word.

In summary, the encoder discovers interesting things about the English sentence whilst the decoder predicts the next French word in the translation. It should be noted they use "Multi-Head Attention", meaning that a number (8 in the original paper) of attention vectors are calculated to learn attention mechanisms to pay attention to different things, for example, grammar, vocabulary, tense, gender, and the output is a weighted average of these.


How much of a problem is white noise for the real-world usage of a DNN? I read that deep neural networks can be relatively easily fooled (link) to give high confidence in recognition of synthetic/artificial images that are completely (or at least mostly) out of the confidence subject.

Personally, I don't really see a big problem with DNN giving high confidence to those synthetic/artificial images but I think giving high confidence for white noise (link) may be a problem since this is a truly natural phenomenon that may the camera see in the real world.

How much of a problem is white noise for the real-world usage of a DNN? Can such false positives be detected from plain noise be prevented somehow?

The white noise that fools DNNs isn't really white noise. It has been altered in the same way as the synthetic misclassified pictures have been altered. You have to change many input pixels in exactly such a way, that these little changes aren't perceptible, but propagated through the network add up to a misclassification. This is not going to happen by chance.


DQN Agent helped by a controller: on which action should I perform backprop? Background

I am working on a robotic arm controlled by a DQN + a python script I wrote.
The DQN receives the 5 joint states, the coordinates of a target, the coordinates of the obstacle and outputs the best action to take (in terms of joint rotations).
The python script checks if the action suggested by the DQN is safe. If it is, it performs it. Otherwise, it performs the second highest-ranking action from the DQN; and so on. If no action is possible, collision: we fail.

During training, this python functionality wasn't present: the arm learned how to behave without anything else to correct his behaviour. With this addition on the already-trained network, the performance raised from 78 to 95%.
Now my advisor (bachelor's thesis) asked me to leave the external controller on during training to check whether this improves learning.

Question

Here's what happens during training; at each step:

the ANN selects an action
if it is legal, the python script executes it, otherwise it chooses another one.

Now... On which action should I perform backprop? The one proposed by the arm or the one which was really executed? (So, which action should I perform backprop on?)

I am really confused. On the one hand, the arm did choose an action so my idea was that we should, in fact, learn on THAT action. On the other hand, during the exploration phase ($\epsilon$ greedy), we backprop on the action which was randomly selected and executed, with no interest on what was the output of the arm. So, it would be rational too, in this case, to perform backprop on the action really executed; so the one chosen by the script.

What is the right thing to do here?. (Bonus question: is it reasonable to train with this functionality on? Wouldn't it be better to train the Network by itself, and then later, enhance its performance with this functionality?)

Q-learning - which DQN is based on - is an off-policy reinforcement learning (RL) method. That means it can learn a target policy of optimal control whilst acting using a different behaviour policy. In addition, provided you use single step learning (as opposed to n-step or Q($\lambda$) variants), you don't need to worry much about the details of the behaviour policy. It is more efficient to learn from behaviour policies closer to the current best guess at optimal, but possible to learn from almost anything, including random behaviour.

So it doesn't really matter too much if you change the behaviour during training.

In your case, the script is actually doing more than just changing the behaviour. It is consistently filtering out state/action pairs that you have decided should never be taken, as a domain expert. This has two major consequences:

It reduces the search space by whatever fraction of state/actions are now denied by your safety script.
It prevents the agent from ever learning about certain state/action pairs, as they are never experienced.

The first point means that your learning should in theory be more efficient. As for how much, you will have to try and see. It might only be a small amount if the problem states and actions are unlikely to be reached during exploration from near-optimal behaviour.

The second point means that your agent will never learn by itself to avoid the problem state/action combinations. So you will always need to use the safety script.

In fact you can view the safety script as a modification to the environment (as opposed to a modification to the agent), if its decisions are strict and consistent. Filtering available actions is a standard mechanism in RL when action space may vary depending on state.

  On which action should I perform backprop?

In DQN, you don't "perform backprop" on an action. Instead you either use directly or store some observed data about the step: $s, a, r, s'$ where $s$ is the start state, $a$ the action taken, $r$ the immediate reward, and $s'$ the resulting state. You then update the the current action value estimate(s) based on a TD target $\delta = r + \gamma \text{max}_{a'} Q(s,a')$ either online or from the experience table.

When Q-learning learns, it updates the estimate for the action value $Q(s, a)$ - and $a$ is taken from the actual behaviour (otherwise the agent will update its estimate of an action that it didn't take). So your answer here is to use - or more likely store in the experience table - the action actually taken. If the action recommended as optimal at that time is different, ignore the difference, what matters is the observed experience.


Monte Carlo Tree Search: What kind of moves can easily be found and what kinds make trouble? I want to start with a scenario that got me thinking about how well MCTS can perform:
Let's assume there is a move that is not yet added to the search tree. It is some layers/moves too deep. But if we play this move the game is basically won. However let's also assume that all moves that could be taken instead at the given game state are very very bad. For the sake of argument let's say there are 1000 possible moves and only one of them is good (but very good) and the rest is very bad. Wouldn't MCTS fail to recognize this and not grow the search tree towards this move and also rate this subtree very badly?
I know that MCTS eventually converges to minimax (and eventually it will build the whole tree if there is enough memory). Then it should know that the move is good even though there are many bad possiblities. But I guess in practice this is not something that one can rely on.
Maybe someone can tell me if this is a correct evaluation on my part.

Apart from this special scenario I'd also like to know if there are other such scenarios where MCTS will perform badly (or extraordinary well).

Whether the move is found and how quick it is found depends on a few things. If I understand correctly, there is a sequence of many "bad" moves which lead to the "big win" move, and you are afraid that the MCTS algorithm will not get to the "big win" move because it will be selecting more promising moves further up the tree. Some things to think about (read also the Wikipedia MCTS article):

when doing playouts, you can do play your game only for a few further moves or down to the game end. Playing only a few moves further is obviously quicker, but in the extreme case you described it would not be the best choice. If you know about the existence of such scenarios, ensure to play the game to the end in the playouts.
when doing playouts, you can choose your moves/actions either randomly or based on some simple, greedy (quick) heuristics tailored to your problem. Are there maybe greedy heuristics designed to find or take into account such scenarios for your game/problem? If yes, implement them. It is then called a "heavy playout". Compare the results to playouts using random moves.
If you choose the actions using UCT (Upper Confidence Bound applied to Trees), then the first part of the expression is responsible for exploitation. Moves with high average win ratio are preferred. The second part though corresponds to exploration. If the exploration parameter is set high enough (test empirically for your problem), then moves with few simulations will be preferred. High exploration would be another way to find your golden move, in detriment of exploitation (read about the exploration/exploitation dilemma).

If you describe a realistic game or problem scenario, we may be able to help you come up with a suitable strategy.


What are state-of-the-art ways of using greedy heuristics to initially set the weights of a Deep Q-Network in Reinforcement Learning? I am interested in the current state-of-the-art ways to use quick, greedy heuristics in order to speed up the learning in a Deep Q-Network in Reinforcement Learning. In classical RL, I initially set the Q-value for a state-action pair (S,a) based on the result of such a greedy heuristic run from state S with action a. Is this still a good idea in the setting of a neural network for the approximation of the Q-function, and if yes, what are the optimal ways of doing it? What are other ways of aiding the DQN with the knowledge from the greedy heuristics?

References to state-of-the-art papers would be highly appreciated.

You can check out Bootstrapped DQN, with a demonstration video. Without reading much of the paper, it seems the authors use a different sampling strategy and an action-guide for specific instances.

Another way to initially set weights for the network is to create a dataset of moves (correct, incorrect, etc, as long as they are relevant) and have the network initially learn the dataset. This also helps debugging, as you can see whether the network can actually learn the policy used in the dataset. After learning the dataset, use the same learned network with DQN and start with a smaller exploration rate (like 0.5 instead of 1.0).


Is there a clear distinction between Artificial Intelligence and running a sequential program? Artificial Intelligence (AI) is often defined as a machine that is intelligent, or one that can think rationally.
From a high-level perspective, things like self-driving car or Alpha-Go can easily be classified as an AI system, while things like a washing machine that follows a strict sequential program is not considered as AI.
However, what confused me is that when looking at the definition from a low-level perspective, there does not seem to be a clear distinction between AI and non-AI.
For example, consider an Artificial Neural Network from Deep Learning. Fundamentally, it is just a complex non-linear function. Why is this considered AI while a washing machine is not considered that?
Is it because of the learning involved? But then path-finding will not considered as AI too.
Is it because of the calculations? But then traditional calculators will be considered as AI.
Is there even a clear distinction between AI and a sequential program? Or is it just a vague term that is only valid when viewed from a high-level perspective?

No. As of now, there is no clear distinction between AI and a sequential program. The biggest reason is that there is no officially agreed definition of AI. Since AI researchers themselves hold different opinions of AI, the field itself is constantly redefined regularly, there is no clear-cut distinction between AI and non-AI.