text:
What is the advantage of having a stochastic classification procedure?
What is the advantage of having a stochastic/probabilistic classification procedure?
The classifiers I have encountered so far are as follows. Suppose we have two outcomes $A = \{0,1\}$. Given a feature vector $x$, we have calculated a probability for each outcome and return the outcome $a \in A$ for which the probability is highest.
Now, I encountered a classification procedure as follows: first, map each $x$ to a probability distribution on $A$ by a mapping $H$. To classify $x$, choose an outcome $a$ according to the distribution $H(x)$.
Why not use the deterministic classification? Suppose $H(x)$ is 1 with probability $0.75$. Then, the obvious choice for an outcome would be $1$ and not $0$.

Please, next time, edit your post to clarify it.

There are multiple potential reasons for having stochastic predictions (instead of categorical/binary).
First, it often simplifies training and improves the training outcome when training a classifier on producing probabilities per class. For example, it allows for the usage of many nice loss functions like the Mean Squared Error (MSE), which is compatible with the famous back-prop algorithm. Moreover, improving classification based on the loss computed from stochastic probabilities per class allows for improving the classifier even further when the counting loss computed on predicted class labels has reached 0 already. So, if you only have binary decisions and your classifier gets all classes correct, training can stop immediately since the loss becomes 0. However, when predicting probabilities per class and iteratively driving the probability of the correct class towards 1, training can continue for much longer, even after all classes have been classified correctly already. So, the classifier trained on making probabilistic predictions can in the end perform much better since training can progress for much longer, allowing for increasingly pronounced discrimination between classes with every update. A nice introduction is given in this Stanford lecture recording.
Second, it is often nice for a user to know how much certainty versus uncertainty there is in a classification. If one class has 80% probability, this is a pretty clear decision in favor of the 80%-probability-class. However, if you only get categorical class labels returned by your classifier, you cannot possibly know whether the evidence in favor of the winning class was only marginally higher than that of the other class (as measured by the classifier) or whether there was a clear difference.


text:
Why is non-linearity desirable in a neural network?
Why is non-linearity desirable in a neural network?
I couldn't find satisfactory answers to this question on the web. I typically get answers like "real-world problems require non-linear solutions, which are not trivial. So, we use non-linear activation functions for non-linearity".

Consider what happens if you intend to train a linear classifier on replicating something trivial as the XOR function. If you program/train the classifier (of arbitrary size) such that it outputs XOR condition is met whenever feature a or feature b are present, then the linear classifier will also (incorrectly) output XOR condition is met whenever both features together are present. That is because linear classifiers simply sum up contributions of all features and work with the total weighted inputs they receive. For our example, that means that when the weighted contribution of either feature is sufficient already to trigger the classifier to output XOR condition is met, then obviously also the summed contributions of both features are sufficient to trigger the same response.
To get a classifier that is capable of outputting XOR condition is met if and only if the summed contributions of all input features are above a lower threshold and below an upper threshold, commonly non-linearities are introduced. You could of course also try to employ a quadratic function to solve the two-feature problem, but as soon as the number of variables/features increases again, you run into the same problem again, only in higher dimensions. Therefore, the most general approach to solving this problem of learning non-linear functions, like the XOR, is by setting up large models with enough capacity to learn a given task and equipping them with non-linearities. That simplifies training since it allows for using stochastic gradient descent for training the system/classifier, preventing one from having to solve Higher-Degree polynomial equations analytically (which can get computationally quite expensive quite quickly) to solve some task.
In case you are interested, here's one paper analyzing and dealing with the XOR problem (as one concrete instance of a problem where purely linear models fail to solve some task).
EDIT:
You can consider a layer in a network as a function $y = f(x)$, where $x$ is the input to some layer $f$ and $y$ is the output of the layer. As you propagate $x$, being the network's input, through the network, you get something like $y = p(t(h(g(f(x)))))$, where $f$ is the input layer and $p$ constitutes the output layer, i.e. a set of weights, by which the input to that respective layer gets multiplied.
If $h$, for example, is some non-linear activation function, like ReLU or sigmoid, then $y$, being the network's output, is a non-linear function of input $x$.

I think that a simple diagram that illustrates that a straight-line cannot solve the XOR problem and that you need a non-linear function to solve would give the intuition. I suppose that there are diagrams on the web that show this issue well.

what types of diagrams are you talking about?

@AlankarShukla For example, these diagrams show that a straight-line cannot solve the XOR problem. By the way, next time, tag me with @nbro, otherwise, I may not see your message.

@nbro i wanna know what is a non linear data.how it can introduced in neural networks,how the neural network learns the non linear data for better prediction.

@nbro i can't get the intuition behind it.i want to know what is a non linear data,how it is introduced in neural networks,and how neural networks learn these data for predicting.

@AlankarShukla If you don't know what non-linear data means, then ask another question. That's the correct approach. However, make sure that this answer cannot be easily found on the web.

@AlankarShukla, In a nutshell, non-linearly separable data is any kind of data where a corresponding decision boundary or decision-(hyper-)plane must be (geometrically) bent, i.e. be a non-linear function of the input parameters, in order to separate two or more classes from one another.

@Daniel B i want to know  that using non linear activation functions in the hidden layers, the input data is again and again normalise.so this process leads to learn a non linear function in Neural network?

It doesn't have anything to do with normalization.

For a regressor, it can work fine to have an output layer that is linear.
The composition of two linear functions is also linear, so in a deep neural net, if all layers are linear it can only learn a linear function. As Daniel B explains, XOR is a good example of a function with no useful linear approximation.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
What would happen if we sampled only one tuple from the experience replay?
The concept of experience replay is saving our experiences in our replay buffer. We select at random to break the correlation between consecutive samples, right?
What would happen if we calculate our loss using just one experience instead of a mini-batch of experiences?

The concept of experience replay is saving our experiences in our replay buffer. We select at random to break the correlation between consecutive samples, right?

Yes that is a major benefit of using a replay buffer.
A secondary benefit is the ability to use the same sample more than once. This can lead to beter sample efficiency, although that is not guaranteed.

What would happen if we calculate our loss using just one experience instead of a mini-batch of experiences?

The algorithm is still valid, but the gradient estimate for the update step would be based on a single record of [state, action, reward, next state]. This would be a high variance update process, with many steps in wrong directions, but in expectation over many steps you should still see a correct gradient. You would probably need to compensate for the high variance per sample by reducing the learning rate.
In addition, assuming the standard approach of collecting one time step then making one update to DQN neural network, each piece of experience would only be used once on average before being discarded.
These two effects will likely combine such that the learning process would not be very sample efficient.
The size of the minibatch is one of many hyperparameters you can change in DQN. It might be the case for some problems that choosing a low minibatch size is helpful, provided other adjustments (such as a lower learning rate) are made along with it. If you are not sure, you mostly have to try and see.
In my experience on a small range of problems, a moderate size of minibatch - ranging from 10 to 100 - has worked the best in terms of end results of high scoring agents. However, I have not spent a long time trying to make low batch sizes work.

Can you simplify what you mean by a high variance update ?, does this mean it would give a higher divergence than when a batch is used?

@Chukwudi: High variance = "varies a lot". Statistcally in the sense of mean and variance. If you take more samples and take the mean (which is what a batch does), then the variance of the expected mean is divided by the number of samples.

Oh so the higher number of samples the more accurate the measurements, so the lower the variance right

@Chukwudi: Yes. But of course if takes more time and effort to collect those samples. Meaning you take longer to make updates to your NN. So it is not always clear whether to take small or large batches.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Does the number of parameters in a convolutional neuronal network increase if the input dimension increases?
If I have a convolutional neuronal network, does the input dimension change the number of parameters? And if yes, why? If the sizes and lengths of the filters are still the same, how can the number of parameter in a network increase?

If I have a convolutional neuronal network, does the input dimension change the number of parameters? And if yes, why?

If the convolutional neural network (CNN) only uses convolutional layers, then the number of parameters does not increase as a function of the spatial dimensions ($x$ and $y$) of the input. This is one of the advantages of CNNs!
The reason is quite simple: the parameters of the convolutional layers are the kernels (aka filters), which typically have fixed dimensions and can, nevertheless, be applied to inputs of different spatial dimensions, provided that the necessary padding is used. However, note that padding can create bigger feature maps, but feature maps are not the parameters of the neural network: they are the output of the convolutional layers. That's probably what confuses you, when you see a diagram of a CNN, because you see bigger feature maps and you might think that the number of parameters increases.
Here's a TensorFlow 2 (and Keras) program that shows that the number of parameters does not change as a function of the $x$ and $y$ dimension of the input.
import tensorflow as tf

input_shapes = [(2 * k, 2 * k, 3) for k in range(2, 6)]

for input_shape in input_shapes:
    model = tf.keras.Sequential()
    model.add(tf.keras.layers.Input(shape=input_shape))
    model.add(tf.keras.layers.Conv2D(10, kernel_size=3, use_bias=True))
    model.summary() # The total number of parameters is always 280

The parameters of a convolutional layer can increase if you increase the size of each kernel and the number of kernels, but this does not necessarily depend on the input.
The parameters of the CNN can also increase if you increase the depth of the input, but that's typically fixed (either $3$ for RGB images or $1$ for grayscale images). The reason is quite simple too: the kernels in the first convolutional layer (connected to the input layer) will have the same depth as the depth of the input.
If your CNN also has fully connected layers, then the number of parameters also depends on the dimensions of the inputs. This is because the parameters of the fully connected layers depend on the number and dimensions of the feature maps (remember the flatten layer before the fully connected layers?), which, as I said, can increase as a function of the input.
If you don't want to use fully connected layers, you may want to try fully convolutional networks (FCNs), which do not make use of fully connected layers, but can, nonetheless, be used to solve classification (and other) tasks.


text:
How to combine several chatbots into one?
I'm in the middle of a project in which I want to generate a TV series script (characters answering to each other, scene by scene) using SOTA models, and I need some guidance to simplify my architecture.
My current intuition is as follows: for a given character C1, I have pairs of sentences from the original scripts where C1 answers other characters, for example, C2 (C2->C1). These are used to fine-tune a data-driven chatbot. At inference time, the different chatbots simply answer each other, and, hopefully, the conversation will have some sense.
This is however unpractical and will be kind of a mess with many characters, especially if I use heavy models.
Is there an architecture out there that could be used for conversational purposes, which could be trained only once with the whole dataset while separating the different characters?
I'm open to any ideas!

What you want to do is you have some character like hulk, thor, caption America, iron man, etc. and you want to Train a response generator for each character like for thor on his dataset, for hulf on his dataset etc... and then you wanted to make a conversation. If I Understood you well then.

You can fine-tune GPT-2 small or GPT-2 Medium using your Dataset for each character. Reference for Finetune

You can decode using simple nucleus sampling at each time step. Use greedy nucleus sampling multiple times in parallel to generate multiple responses. You can generate 30 such responses and also use the last 3-5 dialogue turn as a context or Short term memory. Decoder reference

To Choose the best response out of all generated responses(30 responses as an example). you can use cosine similarity between generated responses and query + last 3-5 dialogue turn.
def cosine_similarity_nd(embd1, embd2):
numerator = np.multiply(embd1, embd2)
numerator = np.sum(numerator, axis=1)
eucli_norm_1 = np.sqrt(np.sum(np.power(embd1, 2), axis=1))
eucli_norm_2 = np.sqrt(np.sum(np.power(embd2, 2), axis=1))
denominator = np.multiply(eucli_norm_1, eucli_norm_2)
denominator = denominator + 1e-10  # remove zeros
cosine_similarity = np.divide(numerator, denominator)
return cosine_similarity.reshape((-1))

Or you can train a reverse model for either all character or mix all character dialogue and use this model to calculate loss of all responses with your query. Reference reverse model

Or you can Combine result of cosine and reverse model to find response out of all the responses.

Define features that describe C1 and C2 (like their ids) and add these features to inputs of your model. Thus your only model will be able to generate the next line for any pair of (C1, C2).


text:
When to use AND and when to use Implies in first-order logic?
I am trying to learn the theory behind first-order logic (FOL) and do some practice runs of converting statements into the form of FOL.
One issue I keep running into is hesitating on whether to use an AND ($\land$) statement or an IMPLIES ($\rightarrow$) statement.
I have seen examples such as "Some boys are intelligent" turned into:
$$
\exists x \text{boys}(x) \land \text{intelligent}(x)
$$
Can I make a general assumption that when I see $x$ is/are $y$, I can use an AND?
With a statement such as "All movies directed by M. Knight Shamalan have a supernatural character", I feel that that statement can be translated to either:
$$
\forall x, \exists y \; \text{directed}(\text{Shamalan}, x) \rightarrow \text{super-natural character}(y)
$$
or
$$
\forall x, \exists y \; \text{directed}(\text{Shamalan}, x) \land \text{super-natural character}(y)
$$
Is there a better way to distinguish between when to use one or the other?

i don't think ∃x boys(x) ∧ intelligent(x) is correct for the statement "Some boys are intelligent". there might be some boys who aren't intelligent, for which the predicate fails.

@nikhilbalwani What would be a clearer more concise way of writing out that statement in terms of first order logic?

When considering the sentence "Some boys are intelligent", it makes sense to express it by ∃x boys(x) ∧ intelligent(x). This is because the existential quantifier makes sure to express that at least some, but not necessarily all boys are intelligent. More specifically, you say that there exists something which is a boy and which is intelligent. But if such a something exists, then there are some boys which are intelligent. Your statement is satisfied.
Using a simple implication → here wouldn't work semantically in that context. For example, ∃x boys(x) → intelligent(x) expresses that: For some x, if x is a boy, then x is intelligent. By rewriting, we would get ∃x ¬boys(x) ∨ intelligent(x). This statement would even be true if all x were not boys, because ¬boys(x) would be true in these cases. So, ∃x boys(x) → intelligent(x) would hold as soon as something in your model wasn't a boy. In that case, ∃x boys(x) → intelligent(x) would be true, but "Some boys are intelligent" would not really be satisfied, since there are simply no boys in your model which could be intelligent. So, you will have to resort to something like ∃x boys(x) ∧ intelligent(x), since otherwise there is no guarantee that boys (even intelligent ones) are present in the resulting model.


text:
In Fast R-CNN, how are input RoIs mapped to the respective RoIs in the feature map before RoI pooling?
I've been reading the Fast R-CNN paper.
My understanding is that the input to one forward pass is the whole input image plus a list of RoIs (generated by selective search or another region proposal method). Then I understand that on the last convolution layer's feature map (let's call it FM), each corresponding RoI gets RoI-pooled, where now the corresponding ROIs are a rectangular (over height and width) slice of the FM tensor over all channels.
But I'm having trouble with two concepts:

How is the input RoI mapped to the corresponding RoI in FM? Each neuron comes from a very wide perceptive field, so, in a deep neural network, there's no way of making a 1:1 mapping between input neurons and neurons in the last convolution layer right?

Disregarding that I'm confused in point 1, once we have a bunch of RoIs in FM and we do the RoI pooling, we have N pooled feature vectors. Do we now run each of these through one FC network one by one? Or do we have N branches of FC networks? (that wouldn't make sense to me)

I have also read the faster R-CNN paper. In the same way, I'm also interested to know about how the proposed regions from RPN map to the input of the RoI pooling in the Fast R-CNN layers. Because actually those proposed regions live in the space of the input image, not in the space of the deep feature map.

The ROIs in the input space are mapped to the feature map space, by dividing it by the net stride at that layer. Say, in a network, after a sequence of four 2x2 pooling layers, your image is reduced to 1/16 of the original size. (A 32*32 image is reduced to 2x2) So, the bounding boxes in the original space are mapped to the feature space by dividing by the net stride, which is 16 here. But here's the catch, the ROI co-ordinates could be a floating point number when divided by 16, so, it is adjusted by either flooring it or ceiling it. This is why ROIPooling is quantized. There is a loss of information when you are rounding off the co-ordinates of the ROI. Nevertheless, now, each region is pooled to a single-size feature map, and each ROI is fed one-by-one to the following layers.
The Mask-RCNN paper brings a change to the mapping to the feature space, by not rounding off the co-ordinates, and by bilinear interpolation, and the loss of information is reduced, thus, the ROIAlign algorithm(which has been described here) performs better at object detection, than the quantized ROIPool algorithm.

As said, each fixed-size feature map vector is processed one-by-one.

Reference


text:
Are there any good alternatives to an LSTM language model for text generation?
I have a trained LSTM language model and want to use it to generate text. The standard approach for this seems to be:

Apply softmax function
Take a weighted random choice to determine the next word

This is working reasonably well for me, but it would be nice to play around with other options. Are there any good alternatives to this?

Sometimes, expert system techniques might be used to generate text, e.g. with CLIPS. You might then be interested by RefPerSys. BTW, I guess that different techniques apply to generate Chinese, Russian, or French, and things are different if you want to generate audio files or UTF-8 textual files, or PDF documents

The current state of the art in natural language generation are all auto-regressive transformer models. Transformers no longer use recurrent neural networks such as LSTM, because the recurrences makes long dependencies messy to calculate. Instead, Transformers only keep the attention layers, and apply attention on all the existing text so far, which can be done in parallel so therefore very fast, while being able to attend to long dependencies (e.g. understanding that "it" refers to "John" from 3 sentences ago). They are also faster to train than LSTMs (on powerful GPUs at least). The downside is more memory requirement, and you need large models and large datasets (LSTMs work better for small models and small datasets). Here is some background info on how they work.
Auto-regressive transformer models only use the decoder for text generation, and removes the encoder. Given an input, they predict the next word.
The most well-known one is GPT (GPT-3 has 175B parameters; GPT-2 has 1.5B parameters, and GPT-1 has 175M parameters) GPT is developed by OpenAI and is a commercial, paid-software if you want to use their official model, but I'm sure with a little digging you can find community-trained models that will perform slightly worse but is at least free to use. GPT is basically a vanilla transformer, but trained on a huge, huge dataset with a huge, huge model to achieve state-of-the-art performance.
Other auto-regressive transformer models include:

CTRL by Salesforce, which uses the novel idea of control codes to guide the style of generation (e.g. to generate Wikipedia article style text or book review style text).
XLNet by Google AI Brain team, which handles longer sequences more accuractely than the others because it re-introduces reccurrence back in the transformer model, allowing it to remember past sequences. Otherwise, vanilla transformers cannot handle dependencies that crosses sequences (note: a sequence is limited by the max length you can feed into the model, bottle-necked by your memory requirement, and can contain many sentences or paragraphs).
Reformer by Google Research, which is a more efficient transformer that significantly reduces the memory requirement while also being faster to compute on long sequences.

If your goal is just to generate English or another commonly researched language, you can use an existing pre-trained language model and avoid doing any training yourself. This saves a lot of time, and there should at least be free community-trained models readily available. Otherwise, for obscure tasks, you'd have to train one yourself, and these state of the art models will take immense resources.


text:
How should I define the action space for a card game like Magic: The Gathering?
I'm trying to learn about reinforcement learning techniques. I have little background in machine learning from university, but never more than using a CNN on the MNIST database.
My first project was to use reinforcement learning on tic-tac-toe and that went well.
In the process, I thought about creating an AI that can play a card game like Magic: The Gathering, Yu-gi-oh, etc. However, I need to think of a way to define an action space. Not only are there thousands of combinations of cards possible in a single deck, but we also have to worry about the various types of decks the machine is playing and playing against.
Although I know this is probably way too advanced for a beginner, I find attempting a project like this, challenging and stimulating. So, I looked into several different approaches for defining an action space. But I don't think this example falls into a continuous action space, or one in which I could remove actions when they are not relevant.
I found this post on this stack exchange that seems to be asking the same question. However, the answer I found didn't seem to solve any of my problems.
Wouldn't defining the action space as another level of game states just mask the exact same problem?
My main question boils down to:
Is there an easy/preferred way to make an action space for a game as complex as Magic? Or, is there another technique (other than RL) that I have yet to see that is better used here?

There are several different ways you can model the state and action spaces in such sequential (extensive-form) environments/games. For environments with small action spaces or those typically introduced to beginning-RL students, the state space and action space remains constant along an agent's trajectory (termed normal form games when there are multiple agents). In sequential games which can be illustrated as trees, a "state" is analogous to "information set" which is defined as the sequence (tuple) of actions and observations since the beginning of the game's episode. Terminal states (leaf nodes) exist, and the action space $\mathcal{A}[x]$ at an information set $x$ can be defined as a union of action sequences that can be taken to each terminal state, not counting terminal states that cannot be reached from the current information set.
In the above examples, I discussed games such as the examples you stated where more than one agent can interact with the environment, but this is a generalization over RL and can be applied to when only one agent is maximizing its reward.

Thank you so much for your response. I'll probably take a look at a single minimaxing agent first. Then, I'll look into some of the other resources you raised.
Again, thank you!


text:
How do I select the (number of) negative cases, if I'm given a set of positive cases?
We were given a list of labeled data (around 100) of known positive cases, i.e. people that have a certain disease, i.e. all these people are labeled with the same class (disease). We also have a much larger amount of data that we can label as negative cases (all patients that are not on the known positive patient's list).
I know who the positives are, but how do I select negative cases to create a labeled dataset of both positives and negatives, on which to first train a neural network, and then test it?
This is a common problem in the medical field, where doctors have lists of patients that are positive, but, in our case, we were not given a specific list of negative cases.
I argued for picking a number that represents the true prevalence of the disease (around 1-2%). However, I was told that this isn't necessary and to do a 50:50 split of positives to negatives. It seems that doing it this way will not generalize outside our test and train datasets.
What would you do in this case?

I worry that changing the class imbalance could give a false improvement in accuracy.

It will, but accuracy is a bad choice of metric for such an imbalanced dataset. For medical diagnoses you also will care a lot about false positive rate (it is common to get more false positive than true positives with such imbalances which may lead to lots of unwanted stress and non-necessary treatments). Hopefully someone can answer with more detail.

Thanks for your thoughts. Do you think an F1 would be better?

I think someone who knows more about the context here should answer. I have edited in salient detail to the title and this is a common enough problem that there is a tag for it, too

Short answer
To select the proper dataset to construct, you should first figure out a metric to use to compare, and then select the dataset construction that gives the better metric. There is no single best metric, it depends on the task and your interpretation on what type of error is more important.
If you believe it is important that errors should not be normalized across class, then use the overall accuracy, and keep your dataset distribution same as the natural distribution (so 1-2% positive cases).
If you believe it is important that errors should be normalized across class, then use PR-AUC or ROC-AUC, and re-balance your dataset so that the samples a little more closer to 1:1. The exact ratio will only be determined after testing and comparing the PR-AUC or ROC-AUC metrics.
How to select the best metric?
Two popular metrics are ROC-AUC and PR-AUC. ROC curves (Receiver Operating Characteristics) plot the true positive rate vs false positive rate, while PR curves (Precision and Recall) plot the precision vs recall. AUC stands for "area under curve", because you can achieve any single point in the curve by specifying the classifier threshold, so the sum of all points (i.e. the entire area under the curve) is the most general way of comparing if one model is doing better than another.
Although both ROC curves and PR curves equalize class imbalance at some capacity, PR curves are more sensitive to class imbalance. The paper The Relationship Between Precision-Recall and ROC Curves concludes that if the PR-AUC is good then the ROC-AUC will always also be good, but not the other way around. The difference is due to the fact that if the dataset has huge class imbalance, a false positive hurts PR curves significantly more than ROC curves.
On the other hand, total accuracy does not normalize class imbalance at all, so therefore favors the majority class.
As a result:

if you do not care about normalizing the measures of class imbalance, choose total accuracy, which will optimize for the most # of correct cases (regardless of class)
if you want to normalize your metric across class imbalance, and normalizing false positive errors across classes is at all important to you, choose PR-AUC
if you want to normalize your metric across class imbalance, and don't care about normalizing false positive errors, PR-AUC or ROC-AUC may both be good for you

If it helps, for most imbalance problems, people usually go for PR curves.
By the way, (this paper) studies class imbalance in neural networks by optimizing the ROC curves, and show that you should definitely have equal numbers of positive and negative examples. So if you want the best performance in terms of ROC-AUC, you should do the 50:50 split. I haven't read any similar study that optimizes for PR-AUC, but my intuition tells me that it will have the same conclusion (you should do 50:50 split to optimize for PR-AUC as well).


text:
What does the depth of a decision tree depend on?
In these notes, we have the following statement

The depth of a learned decision tree can be larger than the number of training examples used to create the tree

This statement is false, according to the same notes, where it is written

False: Each split of the tree must correspond to at least one training example, therefore, if there are $n$ training examples, a path in the tree can have length at most $n$
Note: There is a pathological situation in which the depth of a learned decision tree can be larger than number of training examples $n$ - if the number of features is larger than $n$ and there exist training examples which have same feature values but different labels.

I had written on my notes that the depth of a decision tree only depends on the number of features of the training set and not on the number of training samples. So, what does the depth of the decision tree depend on?

As stated in the other answer, in general, the depth of the decision tree depends on the decision tree algorithm, i.e. the algorithm that builds the decision tree (for regression or classification).
To address your notes more directly and why that statement may not be always true, let's take a look at the ID3 algorithm, for instance. Here's the initial part of its pseudocode.
ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
...

So, in general, the depth of the tree may not depend on the number of features, but it may just depend on the labels or training examples (which is a degenerate case), although, in most cases, it will also depend on the number of features, because each node represents a split of the training examples based on some condition that needs to be true for some feature (e.g. the height of the people must be less than 150cm).

While this sounds obvious, the depth of the tree depends on how your algorithm builds the tree. For a fixed dataset $\mathcal{D}$, there're many algorithms, such as ID3, C4.5, CART, etc. (and their variants) to build your tree. For the most part, these algorithms recursively partition the dataset, so it's never possible to get a tree larger than $|\mathcal{D}|$. Large/deep trees are also prone to overfitting and are computationally expensive, so these algorithms typically prune the tree so it's much smaller than $|\mathcal{D}|$.
In fact,
Kearns and Mansour showed that under the weak learning assumption (i.e. at each node, there's a split that classifies the data at this node better than a random classifier, by $\gamma$) to achieve $\epsilon$ training error, it suffices to make $(1/\epsilon)^{\mathcal{O}(\log(1/\epsilon)/\gamma^2)}$ splits (and thus depth is upper bounded by this).
But of course, you can always cook up trees of arbitrary depth...

@Sara Imagine the tree was deeper than the amount of of examples. Then, when you assign all examples to the leaves of the tree, there will be some leaves that are empty. The parent of these leaves makes a distinction that doesn't improve the accuracy on the training set (if you removed that distinction, you would get the same result), so while there could be an algorithm that creates such a tree, it would have to be based on assumptions about unseen data.


text:
Are the state-action values and the state value function equivalent for a given policy?
Are the state-action values and the state value function equivalent for a given policy? I would assume so as the value function is defined as $V(s)=\sum_a \pi(a|s)Q_{\pi}(s,a)$. If we are operating a greedy policy and hence acting optimally, doesn't this mean that in fact the policy is deterministic and then $\pi(a|s)$ is $1$ for the optimal action and $0$ for all others? Would this then lead to an equivalence between the two?
Here is my work to formulate some form of proof where I start with the idea that a policy is defined to be better than a current policy if for all states then $Q_{\pi}(S,\pi^∗(s))\geq Vπ_{\pi}(s)$ :
I iteratively apply the optimal policy to each time step until I eventually get to a fully optimal time step of rewards
$$Vπ_{\pi}(s)≤Q_{\pi}(S,\pi^∗(s))$$
$$=Eπ[R_{t+1}+\gamma V_{\pi}(St+1)|St=s]$$
$$\leq E[Rt+1+\gamma Q_{\pi}(S_{t+1},\pi^∗(S_{t+1})|S_t=s]$$
$$\leq E[Rt+1+\gamma Rt+2+\gamma 2Q \pi^*(S_{t+2},\pi^∗(S_{t+2})|S_t=s]$$
$$\leq E[R_{t+1}+\gamma R_{t+2}+....|S_t=s]$$
$$=V\pi^∗(s)$$
I would say that our final two lines are in fact inequalities, and for me this makes intuitive sense in that if we are always taking a deterministic greedy action our value function and Q function are the same. As detailed here, for a given policy and state we have that $V(s)=\sum_a \pi(a|s)Q_{\pi}(s,a)$ and if the policy is optimal and hence greedy then $\pi(a|s)$ is deterministic.

In general they are not the same and that should be clear as to why -- mathematically you are conditioning on an extra random variable being known in the state-action value function. You have the correct relationship between them, but I think your understanding of the two may be slightly off. The state-action value function is a function of both $s$ and $a$ whereas the value function is a function of just $s$. As you have noted, the value function is equal to the expected value of the state-action value function, with the expectation taken over the action distribution induced by the policy.
However, if you have a deterministic policy, then two are equivalent only if you evaluate the state-action value function at the action that the deterministic policy gives. That is, $v_\pi(s) = Q(s, \pi(s))$. This is because, as you say, for a given state the policy will assign probability one to a certain action and 0 to all other actions in the action space and so the equation I just wrote is what the expectation in your question reduces to.
Now, you might think 'well the policy is deterministic so we are always going to choose this action, so my theory was correct'. This is not true. The definition of the state-action value function is the value of the expected future (possibly discounted) returns given that we are in state $s$ and given that we have taken action $a$. This means that we have already chosen our action and we are not choosing it according to the policy -- the policy will only choose all future actions.
You also say that "If we are operating a greedy policy and hence acting optimally" which is not true. Just because we act greedily it does not imply we are acting optimally. Value functions are functions of a policy. If the policy is completely random then you would get certain value and state-action value functions which you could act greedily to but this would not be optimal.

Hi @DavidIreland I completely agree about the last paragraph. What I was trying to say was that acting greedily WITH an optimal policy then we would be acting optimally. Would this be correct? Given we have found an optimal policy and there is no noise in the environment if we act greedily then it should also be optimal, correct?

Your other points also makes sense, we are saying that in fact they wont be equivalent because although we evaluate all future steps with the optimal policy, the current step was chosen for this state, as defined by the definition of state action values. Is this correct?

If you are acting greedily according to optimal action-value functions then yes you are acting optimally.
with regards to the second comment, yes that is indeed what we are saying. All future steps would agree except the returns would differ depending on what the current action taken was.


text:
When we have multiple traces, do we average over traces or the total number of times we have visited that state?
I am confused about the workings of the first- and every-visit MC.
My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?
So, in the example:
$$\tau_1 = \text{House} +3, \text{House} +2, \text{School} -4, \text{House} +4, \text{School} -3, \text{Holidays}$$
$$\tau_2 = \text{House} -2, \text{House} +3, \text{School} -3, \text{Holidays},$$
where we have states of either House, Holidays, or School, with the numerical values being the immediate rewards.
For every-visit MC to find the state value of HOUSE, with $\gamma$=1, my intuition would be to create a return list, R, that looks like the following
$$R_1=[3+2−4+4−3, 2−4+4−3, 4−3]= [2, −1, 1]$$
$$R_2=[−2+3−3, 3−3]=[−2, 0]$$
$$R_1+R_2=[2,−1, 1,−2, 0]$$
which, when averaged over 5 visits, is 0 and the correct answer, but I would like if you could confirm if the methodology is correct?
However, another approach would be to compute the average returns for each trace. Which is correct?

To me, this post is not fully clear. Although you already accepted an answer, and I understand that answer, I don't understand everything in this post. For example, in your trajectories, what would it mean to sum a state and a number, as you do in $\tau_1$ (e.g. House + 3)? What does that mean? Maybe you can formulate that part more clearly, because that's not very clear.

For every visit MC you create a list for each state. Every time you enter a state you calculate the returns for the episode and append these returns to a list. Once you have done this for all the episode you want to average over you simply calculate the value of a state to be the average of this list of returns for the state.
First visit MC is almost the same except that you only append the returns to the state returns list for the first time you visit the state in an episode.
Your workings are correct, you average over the number of times you have visited the state (in every visit MC). So, in your example, you would get the value of HOUSE to be 0, as you stated. If you were doing first visit MC then the returns for episode 1 would be 2 and the returns for episode 2 would be -2, which you would then average over the two first visits to again give you 0 (this would not always be the case that they are equal after 2 episodes but in the limit both methods do converge to the true state value function).

as a follow up, the case you mentioned for First Visit, if $\gamma = 1$, would I include the discounted return of all future states also? Your approach of only including the immediate reward for the given state suggests that you are assuming $\gamma = 0$.

For first visit you do exactly what you have done for every visit, except you only do it for the first time you enter the state. I didn't assume $\gamma = 1$ -- in first visit you take the discounted (here $\gamma = 1 so no discounting) returns for HOUSE's first visit which, for episode 1, was 3 + 2 - 4 + 4 - 3 = 2 -- this is because you only calculate the returns from your first visit.


text:
In AlphaZero, do we need to store the data of terminal states?
I have a question about the training data used during the update/back-propagation step of the neural network in AlphaZero.
From the paper:

The data for each time-step $t$ is stored as ($s_t, \pi_t, z_t$) where $z_t = \pm r_T$ is the game winner from the perspective of the current player at step $t$. In parallel (Figure 1b), new network parameters $\Theta_i$ are trained from data ($s,\pi, z$) sampled uniformly among all time-steps of the last iteration(s) of self-play

Regarding the policy at time $t$ ($\pi_t$), I understood this as the probability distribution of taking some action that is proportional to the visit count to each child node, i.e. during MCTS, given some parent node (state) at time $t$, if some child node (subsequent state) $a$ is visited $N_a$ times and all children nodes are visited $\sum_b N_b$ times, then the probability of $a$ (and its corresponding move) being sampled is $\frac{N_a}{\sum_b N_b}$, and this parametrizes the distribution $\pi_t$. Is this correct? If this is the case, then for some terminal state $T$, we can't parametrize a distribution because we have no children nodes (states) to visit. Does that mean we don't add ($s_T, \pi_T, z_T$) to the training data?
Also, a followup question regarding the loss function:

$l = (z-v)^2 - \pi^T log\textbf{p} + c||\Theta||^2$

I'm confused about this $\pi^T$ notation. My best guess is that this is a vector of actions sampled from all policies in the $N$ X $(s_t, \pi_t, z_t)$ minibatch, but I'm not sure. (PS the $T$ used in $\pi^T$ is different from the $T$ used to denote a terminal state if you look at the paper. Sorry for the confusion, I don't know how to write two different looking T's)

I'm not 100% sure whether or not they added any data for terminal game states, but it's very reasonable to indeed make the choice not to include data for terminal game states. As you rightly pointed out, we don't have any meaningful targets to update the policy head towards in those cases, and this is not really a problem because we would also never actually make use of the policy output in a terminal game state. For the value head we could provide meaningful targets to update towards, but again we would never actually have to make use of such outputs; if we encounter a terminal game state in a tree search, we just back up the true value of that terminal game state instead of making a call to the network to obtain a value function approximation.
In theory, I could imagine some cases where training the value head on terminal game states might be slightly beneficial despite not being strictly necessary; it could enable generalisation to similar game states that are not terminal (but close to being terminal), and speed up learning for those. For example, if you have a game where the goal is to complete a line of $5$ pieces, training the value head on terminal states where you actually have a line of $5$ pieces and have entirely won the game might generalise and speed up learning for similar game states where you may not yet have $5$ pieces in a line, but are very close to that goal. That said, intuitively I really don't feel like this would provide a big benefit (if any), and we could probably also come up with cases where it would be harmful.

In the $\pi^{\text{T}}$ notation, $\pi$ is a vector (for any arbitrary time step, the time step is not specified here) containing a discrete probability distribution over actions (visit counts of MCTS, normalised into a probability distribution), and the $\text{T}$ simply denotes that we take the transpose of that vector. Personally I don't like the notation though, I prefer something like $\pi^{\top}$ which is more clearly distinct from a letter $T$ or $\text{T}$.
Anyway, once you understand that to denote the transpose, you'll see that $\pi^{\top}\log(\mathbf{p})$ is a dot product between two vectors, which then ends up being a single scalar.


text:
Is there a taxonomy of adversarial attacks?
I am a medical doctor working on methodological aspects of health-oriented ML. Reproducibility, replicability, generalisability are critical in this area. Among many questions, some are raised by adversarial attacks (AA).
My question is to be considered from a literature review point of view: suppose I want to check an algorithm from an AA point of view:

is there a systematic methodology approach to be used, relating format of the data, type of models, and AA? Conceptually, is there a taxonomy of AA? If so, practically, are some AA considered as gold standards?

There are already a couple of papers in the literature that attempt to provide a taxonomy and survey of adversarial attacks. I will just list the two that I think are reliable enough that you can probably use as a reference.

A taxonomy and survey of attacks against machine learning (2019) by Nikolaos Pitropakis et al., published in Computer Science Review

Adversarial Examples: Attacks and Defenses for Deep Learning (2019) by Xiaoyong Yuan et al., published in IEEE Transactions on Neural Networks and Learning Systems.

Needless to say, there are different adversarial attacks, such as the Fast Gradient Signed Method (FGSM), and they can be classified into different categories, such as evasion attacks or poising attacks. You can find a lot more info in these cited papers.


text:
How to calculate the distance between the camera and an object using Computer Vision?
I want to create a Deep Learning model that measures the distance between the camera and certain objects in an image. Is it possible? Please, let me know some resources related to this task.

In general, calculation of distance between camera and object is impossible if you don't have further scene dependent information.
To my knowledge you have 3 options:
Stereo Vision
If you have 2 cameras looking at the same scene from a different point of view you can calculate the distance with classical Computer Vision algorithms. This is called stereo vision, or also multiview geometry.
Stereo Vision is the reason why humans can infer the distance to objects around them (because we have 2 eyes).
Structure from Motion
You move your camera and therefore change your viewpoint and can essentially do stereo mapping over time. Structure from Motion
Scene Understanding
Why is it then still possible for a one-eyed person to infer depth to some extent? Because humans have lots of scene dependent understanding. If you see a rubber duck that takes half of your field of view, you know it's pretty close because you know a rubber duck is not big. If you don't know the size of rubber ducks it is impossible to know whether you see a big rubber duck that is far away or a small rubber duck that is really close.
This is where Deep Learning based models come into play. A recent overview over monocular
depth estimation can be found in Zhao2020

You can use libraries OpenCV and Python to find the distance.
You can refer this : Vehicle detection and distance estimation.
Since you didn't mention about dataset,you may consider datasets and methods in this paper.
If your camera is fixed/has many objects infront of it,you might use nearest object around camera approach..This approach is extremely useful if you want to deal with latitudes and longitudes.


text:
How is the DQN loss derived from (or theoretically motivated by) the Bellman equation, and how is it related to the Q-learning update?
I'm doing a project on Reinforcement Learning. I programmed an agent that uses DDQN. There are a lot of tutorials on that, so the code implementation was not that hard.
However, I have problems understanding how one should come up with this kind of algorithms by starting from the Bellman equation, and I don't find a good understandable explanation addressing this derivation/path of reasoning.
So, my questions are:

How is the loss to train the DQN derived from (or theoretically motivated by) the Bellman equation?
How is it related to the usual Q-learning update?

According to my current notes, the Bellman equation looks like this
$$Q_{\pi} (s,a) = \sum_{s'} P_{ss'}^a (r_{s,a} + \gamma \sum_{a'} \pi(a'|s') Q_{\pi} (s',a')) \label{1}\tag{1} $$
which, to my understanding, is a recursive expression that says:
The state-action pair gives a reward that is equal to the sum over all possible states $s'$ with the probability of getting to this state after taking action $a$ (denoted as $P_{ss'}^a$, which means the environment acts on the agent) times the reward the agent got from taking action $a$ in state $s$ + discounted sum of the probability of the different possible actions $a'$ times the reward of the state, action pair $s',a'$.
The Q-Learning iteration (intermediate step) is often denoted as:
$$Q^{new}(s,a) \leftarrow  Q(s,a) + \alpha (r + \gamma \max_a Q(s',a') - Q(s,a)) \label{2}\tag{2}$$
which means that the new state, action reward is the old Q value + learning rate, $\alpha$, times the temporal difference, $(r + \gamma \max_a Q(s',a') - Q(s,a))$, which consists of the actual reward the agent received + a discount factor times the Q function of this new state-action pair minus the old Q function.
The Bellman equation can be converted into an update rule because an algorithm that uses that update rule converges, as this answer states.
In the case of (D)DQN, $Q(s,a)$ is estimated by our NN that leads to an action $a$ and we receive $r$ and $s'$.
Then we feed in $s$ as well as $s'$ into our NN (with Double DQN we feed them into different NNs). The $\max_a Q(s',a')$ is performed on the output of our target network. This q-value is then multiplied with $\gamma$ and $r$ is added to the product. Then this sum replaces the q-value from the other NN. Since this basic NN outputted $Q(s,a)$ but should have outputted $r + \gamma \max_a Q(s',a')$ we train the basic NN to change the weights, so that it would output closer to this temporal target difference.

The Bellman equation in RL is usually defined $$v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)\left[r + v_\pi(s')\right] = \mathbb{E}_{s' \sim p, a \sim \pi}\left[r(s, a) + v_\pi(s')\right] \; .$$
The way you have written it is correct, but I just thought I would point this out. Regardless, your intuition is correct in that it expresses a recursive relationship such that the value of your current state $s$ is equal to the sum of the expected reward from this state plus the expected value of the state you transition into.
You do, in fact, implement the Q-learning update in Deep Q-Learning. The loss function that you minimise in DQN is
$$ L(\theta) = \mathbb{E}_{(s,a,r,s')\sim U(D)}\left[\left( r + \gamma \max_{a'}Q(s', a'; \theta^-) - Q(s, a; \theta)\right)^2 \right]\;$$
where $U(D)$ denotes uniformly at random from replay buffer $D$ and $\theta$ are your network parameters (the network parameterises the Q-function), and $\theta^-$ are a previous iteration of the parameters that are updated every $c$ episodes to help with convergence of the network.
As you can see, the loss function is minimising the 'Bellman error' error from your equation 2. Lets think about why this is.
The TD update you provide is gradually shifting the Q value for $(s, a)$ towards $r + \max_a Q(s', a)$ - this is what we want after all since it eventually converges to the optimal Q-function.
Now lets think about the Deep Q-learning case. We want our network to approximate $Q(s, a)$ and so if we train the network, using the MSE loss, with $r + \max_a Q(s', a)$ as our target then our network will gradually be shifted towards predicting $r + \max_aQ(s', a)$ (which again would give us optimal Q-values for state-action pairs), just like with the TD update.
This is assuming that you know how training of neural networks works so if you don't then I would recommend asking/searching for a relevant question that explains this.

I'm not sure why you're saying that the actual Bellman equation is an equation that is a function of the state only. There are different Bellman equations in the context of RL. You also have the Bellman equation in terms of a state-action function, for instance. In general, when someone mentions the "Bellman equation", that means we're talking about a recursive equation. This pops up a lot in many CS contexts, such as all those dynamic programming algorithms in the CLRS book.

The second thing that you're not explaining is: why the minimization of the MSE is equivalent to the TD update, if that's what you're saying.

Yes, can you please explain why minimization of the MSE is equivalent to the TD update

When people mention the bellman equation in the context of RL I typically think of it in terms of the value function rather than the state-value function. It also looks neater than OP’s. I can add an explanation about why minimising MSE is equivalent to the TD update.


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

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

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

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

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

The info in this answer seems to be consistent with my knowledge, which is not very extensive though. I would maybe add 1-2 papers that have attempted to apply second-order methods to train NNs and you could briefly describe their results in terms of convergence and memory requirements (to confirm your claims). This would make your answer more reliable. You can also point to (Python) libraries that support the training of NNs with second-order methods (e.g, does TensorFlow support them?). Although this was not the question, this would allow people to play with these methods more rapidly.

I found a paper analizing the time of first order vs second order bp: https://core.ac.uk/download/pdf/187245955.pdf

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

@EmmanuelMess Although the paper may be valuable, it has not been cited many times. Maybe when you look for a paper you should also take a look where or if it's been published and how many times it's been cited. That's something that I had to learn too (and that my advisor also had told me). You can probably find more papers on Google Scholar with keywords such as "second order" and "backpropagation". Anyway, thanks for sharing that paper. If I have time, I will take a look at it and other papers and maybe also provide an answer.

I have found this article that describes how higher-order derivatives could be computed in TensorFlow. This article talks about BFGS and L-BFGS in the context of TensorFlow Probability. You also have tf.hessians. There are probably other implementations of other specific methods around, such as psgd_tf (which I never tried though).


text:
Can we use transformers for audio classification tasks?
Since transformers are good at processing sequential data, can we also use them for audio classification problems (same as RNNs)?

Yes, Transformers can be used to work with audio data, such as audio processing (audio classification, speaker identification, etc) (Audio ALBERT), speech-to-text (Streaming Automatic Speech Recognition with the Transformer Model), and text-to-speech (Neural Speech Synthesis with Transformer Network).


text:
What is different in each head of a multi-head attention mechanism?
I have a difficult time understanding the "multi-head" notion in the original transformer paper. What makes the learning in each head unique? Why doesn't the neural network learn the same set of parameters for each attention head? Is it because we break query, key and value vectors into smaller dimensions and feed each portion to a different head?

The reason each head is different is because they each learn a different set of weight matrices $\{ W_i^Q, W_i^K, W_i^V \}$ where $i$ is the index of the head. To clarify, the input to each attention head is the same. For attention head $i$:
\begin{align}
Q_i(x) &= x W_i^Q \\
K_i(x) &= x W_i^K \\
V_i(x) &= x W_i^V \\
\text{attention}_i(x) &= \text{softmax} \left(\frac{Q_i(x) K_i(x)^T}{\sqrt{d_k}} \right) V_i(x).
\end{align}
Notice that the input to each head is $x$ (either the semantic + positional embedding of the decoder input for the first decoder layer, or the output of the previous decoder layer). More info
The question as to why gradient descent learns each set of weight matrices $\{ W_i^Q, W_i^K, W_i^V \}$ to be different across each attention head is very similar to "Is there anything that ensures that convolutional filters don't end up the same?", so maybe you might find the answer there helpful for you:

No, nothing really prevents the weights from being different. In practice though they end up almost always different because it makes the model more expressive (i.e. more powerful), so gradient descent learns to do that. If a model has n features, but 2 of them are the same, then the model effectively has n−1 features, which is a less expressive model than that of n features, and therefore usually has a larger loss function.

I think this problem would be a bit different from convolution networks. In convolution layers, the input to each kernel is the same. I thin in attention, the inputs are also different. Is it the case that we break the inputs into smaller chunks in attention?

The original transformer paper words it a bit confusing, but the input to each attention head is the same. For attention head $i$, $Q_i(x) = x W_i^Q$, $K_i(x) = x W_i^K$, and $V_i(x) = x W_i^V$. The output of attention head $i$ is $attention_i(x) = softmax \left(\frac{Q_i(x) K_i(x)^T}{\sqrt{d_k}} \right) V_i(x)$. The input to each head is $x$ (either the semantic + positional embedding of the decoder input for the first decoder layer, or the output of the previous decoder layer). For more info, read the section "Self-Attention in Detail": http://jalammar.github.io/illustrated-transformer/

I did more research into this and it seems that both ways exist in attention literature. We have "narrow self-attention" in which the original input is split into smaller chunks and each head get it's own small input. We also have "wide self-attention" in which the whole input gets fed into each head separately. Wide self-attention gives better results at the cost of memory and computation time. See http://peterbloem.nl/blog/transformers

Interesting, thanks for the share! Are there more publications on wide vs narrow self-attention? I wanted to research further, but couldn't find any literature or academic papers on it. I know that the original transformer code in Tensor2Tensor, and also BERT's code, uses attention the way I described (which is considered "wide self-attention")

No unfortunately that's all I could find.

Multiple attention heads in a single layer in a transformer is analogous to multiple kernels in a single layer in a CNN: they have the same architecture, and operate on the same feature-space, but since they are separate 'copies' with different sets of weights, they are hence 'free' to learn different functions.
In a CNN this may correspond to different definitions of visual features, and in a Transformer this may correspond to different definitions of relevance:1
For example:

Architecture
Input
(Layer 1)Kernel/Head 1
(Layer 1)Kernel/Head 2

CNN
Image
Diagonal edge-detection
Horizontal edge-detection

Transformer
Sentence
Attends to next word
Attends from verbs to their direct objects

Notes:

There is no guarantee that these are human interpretable, but in many popular architectures they do map accurately onto linguistic concepts:

While no single head performs well at many relations, we find that particular heads correspond remarkably well to particular relations. For example, we find heads that find direct objects of verbs, determiners of nouns, objects of prepositions, and objects of possesive pronouns...

What Does BERT Look at? An Analysis of BERT’s Attention (2019)

Multiple heads was originally proposed as a way to mitigate the lack of descriptive power of a single head in self-attention has:

In these models, the number of operations required to relate signals from two arbitrary input or output positions grows in the distance between positions [...] This makes it more difficult to learn dependencies between distant positions [12]. In the Transformer this is reduced to a constant number of operations, albeit at the cost of reduced effective resolution due to averaging attention-weighted positions, an effect we counteract with Multi-Head Attention...

Attention is All You Need (2017)


text:
What is the difference between the heuristic function and the evaluation function in A*?
I am reading college notes on state search space. The notes (which are not publicly available) say:

To do state-search space, the strategy involves two parts: defining a heuristic function, and identifying an evaluation function.

The heuristic is a smart search of the available space. The evaluation function may be well-defined (e.g. the solution solves a problem and receives a score) or may itself be the heuristic (e.g. if chess says pick A or B as the next move and picks A, the evaluation function is the heuristic).

Understand the difference between the heuristic search algorithm and the heuristic evaluation function.

I'm trying step 3 (to understand). Can I check, using the A* search as an example, that the:
Heuristic function: estimated cost from the current node to the goal, i.e. it's a heuristic that's calculating the simplest way to get to the goal (in A*; $h(n)$), so the heuristic function is calculating $h(n)$ for a series of options and picking the best one.
Evaluation function: $f(n) = g(n) + h(n)$.

What is the difference between the heuristic function and the evaluation function in A*?

The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand during one iteration of A* (i.e. decide which node to take from the frontier, determine the next possible actions and which next nodes those actions lead to, and add those nodes to the frontier). Typically, you expand the node $n$ such that $f(n)$ is the smallest, i.e. $n^* = \operatorname{argmin}f(n)$.
In the case of informed search algorithms (such as A*), the heuristic function is a component of $f$, which can be written as $f(n) = g(n) + h(n)$, where $h(n)$ is the heuristic function. The heuristic function estimates the cost of the cheapest path from $n$ to the goal. Just for completeness, $g(n)$ is the actual cost from the start node to $n$ (which can be computed exactly during the search). In the case of uninformed search algorithms, you can actually view the evaluation function as just $f(n) = g(n)$, i.e. the heuristic function is always zero.
So, you're right.
For more details, you can take a look at section 3.5 (p. 92) of the book Artificial Intelligence: A Modern Approach (3rd edition), by Norvig and Russell (you can find the pdf online).


text:
Are there some notions of distance between two policies?
I want to determine some distance between two policies $\pi_1 (a \mid s)$ and $\pi_2 (a \mid s)$, i.e. something like $\vert \vert \pi_1 (a \mid s) - \pi_2(a \mid s) \vert \vert$, where $\pi_i (a\mid s)$ is the vector $(\pi_i (a_1 \mid s), \dots, \pi_i(a_n \mid s))$. I am looking for a sensible notion for such a distance.
Are there some standard norms/metrics used in the literature for determining a distance between policies?

Given that policies are probability distributions, in principle, you can use any metric or measure of distance that can be used to compare two probability distributions. (Note that notions of distance are not necessarily metrics in a mathematical sense).
A common measure is the Kullback–Leibler divergence (which is not a metric, in a mathematical sense, given that it does not satisfy certain required conditions for being a metric). For example, in section 4 of the PPO paper, the KL divergence is used as a regulariser (which is actually quite common, for instance, in the context of variational Bayesian neural networks). The TRPO also uses the KL divergence.
The Wasserstein metric has also been used in RL, for instance, in distributional RL (but, in this case, not to compare policies but distributions over value functions).
You can find more info about statistical distances here. The specific distance that you use may depend on the problem that you want to solve and the properties that you want your distance to have. For example, the KL divergence is unbounded above, so, if that's not desirable, you could choose another one. The paper On choosing and bounding probability metrics (2002, by Gibbs and Su) may also be useful. Here I also talk about the KL divergence and total variation.

Worth noting the Wasserstein metric requires there to be metric over the term that the distribution applies to, so may not apply well to discrete action spaces where there is no conceptual space or ordering between terms (e.g. what is the distance between "up" and "left" actions on a game console?)

@NeilSlater Thanks for pointing this out. Right now, I am only familiar with the details of the KL divergence, although, as I say in this answer, I know that the Wasserstein metric has also been used in RL and I would guess that other measures of distance have been used. If you are familiar with the details of other measures (other than the KL divergence, which is quite popular), I think it may be worth providing another answer with another perspective, which maybe provides some guidance on how to choose it in the context of RL.


text:
Understanding multi-iteration updates of the model in the Proximal Policy Optimization algorithm
I have a general question about the updating of the network/model in the PPO algorithm.
If I understand it correctly, there are multiple iterations of weight updates done on the model with data that is created from the environment (with the model before the update). Now, I think that the updates of the model weights are not correct anymore after the first iteration/optimization step, because the model weights changed and therefore the training data is outdated (since the model would now give different actions in the environment and therefore different rewards).
Basically, in the pseudo-code of the algorithm, I don't understand the line "Optimize surrogate L ... with K epochs...". If the update is done for multiple epochs, the data that is learned is outdated already after the first iteration of optimization, since the model's weights changed. In other algorithms, like A2C, there is only one optimization step done, instead of $K$ epochs.

Is this some form of approximation or augmentation on the data by using the data that was created by an older model for multiple iterations or am I missing something here? If yes, where was this idea first introduced or better described? And where is an (empirical) proof that this still leads to a correct weight updating?

Seems this question was asked and answered in openai/baselines github issue. The issue has been closed for a while.
Below is an answer provided by @matthiasplappert which has the most "thumbs up":

To clarify: PPO is an on-policy algorithm so you are correct that going over the same data multiple times is technically incorrect.
However, we found that PPO is actually quite okay with doing this and we still get stable convergence. This is likely due to the proximal trust region constrained that we enforce, which means that the policy cannot change that much anyway when going over the current set of transitions multiple times, making it still approximately on-policy. You can of course get rid of this but then you'll need more samples.


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

I'm not sure 1. if you're looking for a theoretical result on the approximation capabilities of neural networks when the number of features changes, or 2. if you're just asking if adding features can, in practice, make your NN produce more accurate results (e.g. in terms of accuracy). Can you clarify this?

yes, I mean 1 and 2

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

Are you sure that the approximation capabilities of neural networks change depending on the number of features? According to which "theory" is this true? For example, does the VC dimension of a neural network change if you change the number or type of features?

I am not very knowledged about the VC dimensions theory or similar theories that apply more generally to NNs. If you are, please do elaborate on them. My approach here was to give a semi-intuitive understanding of when to expect 'more' approximation capabilities. I guess you could argue that my first stance on the 'theoretical' side could also be put as more 'practical', but I don't think it matters too much here.


text:
Do I need to know in advance all possible number of states in Q-Learning?
In Q-learning, is it mandatory to know all possible states that can the agent may end up in?
I have a network with 4 source nodes, 3 sink nodes, and 4 main links. The initial state is the status network where the sink nodes have its resources at its maximum. In a random manner, I generate service requests from the source nodes to the sink nodes. These service requests are generated at random timesteps, which means that, from state to state, the network status may stay the same.
When a service request is launched, the resources from the sink nodes change, and the network status changes.
The aim of the agent is to balance the network by associating each service request to a sink node along with the path.
I know that in MDP you are supposed to have a finite set of states, my question is: if that finite set of states is supposed to be all possible states that can happen, or is just a number that you consider enough to optimize the Q-table?

When you start off learning about Q-learning, you start with a simple example that has a few states. For each of the states, you try to estimate what the 'value' is of that state. Because there are so few states, it is possible to store these values in a table (it is also useful for the intuitiveness of the explanation).
However, if you start trying to solve more 'real-life' problems, the number of states can be insanely huge. The essence however will stay the same. You are trying to estimate what you want to do next, based on an estimation of how good each state is that you can end up in. However, now the values are 'most of the times' not stored in a table anymore, as the approach will often come down to using an ANN to estimate the value function.
Answer to your question: You are going to run into a lot of problems when training some model with Q-learning if your table is not able to store the values of possible states that it can come across. In practice, most implementations do not use a Q-table and just use an ANN, which alleviates the problem of having to 'define' how many states your problem consists of.

If you feel like this answer answered your questions correctly or sufficiently, make sure to approve the answer by clicking the checkmark :)


text:
Transformers: how does the decoder final layer output the desired token?
In the paper Attention Is All You Need, this section confuses me:

In our model, we share the same weight matrix between the two embedding layers [in the encoding section] and the pre-softmax linear transformation [output of the decoding section]

Shouldn't the weights be different, and not the same? Here is my understanding:
For simplicity, let us use the English-to-French translation task where we have $n^e$ number of English words in our dictionary and $n^f$ number of French words.

In the encoding layer, the input tokens are $1$ x $n^e$ one-hot vectors, and are embedded with a $n^e$ x $d^{model}$ learned embedding matrix.

In the output of the decoding layer, the final step is a linear transformation with weight matrix $d^{model}$ x $n^f$, and then applying softmax to get the probability of each french word, and choosing the french word with the highest probability.

How is it that the $n^e$ x $n^{model}$ input embedding matrix share the same weights as the $d^{model}$ x $n^f$ decoding output linear matrix? To me, it seems more natural for both these matrices to be learned independently from each other via the training data, right? Or am I misinterpreting the paper?

I found the answer by reading the paper referenced by that section, Using the output embedding to improve language models

Based on this observation, we propose threeway weight tying (TWWT), where the input embedding of the decoder, the output embedding of
the decoder and the input embedding of the encoder are all tied. The single source/target vocabulary of this model is the union of both the source
and target vocabularies. In this model, both in the
encoder and decoder, all subwords are embedded
in the same duo-lingual space.

It seems like they learned a single embedding matrix ($n^e + n^f$) x $d^{model}$ in dimension.

Well actually the dictionary does not contain entire words but rather byte pair encodings. At the end of chapter 3 of the paper that you listed they briefly mention that around 85-90% of the subwords are shared between english and french (see also Table 1). So in this case sharing the weights between the source embedding layer and the target embedding layer makes a lot of sense.
I think that if you are in a different setting (e.g. english to chinese), where your final layer contains $n^e + n^f$ outputs, then this doesn't make much sense because during decoding you actually want to generate words only from the target language, and training this huge softmax layer might be really tricky and hard to do.
Now regarding sharing the weights between the decoder embedding layer and the decoder output layer. I think this is a very nice idea, and you can always do this regardless of the source language or the task altoghether. However, you might want to be careful with the initialization of these weights. You can checkout this if you want to read more.


text:
Why is the policy implied by Q-learning deterministic, when it always chooses the action with highest probability?
Q-learning uses the maximizing value at each step, which implies that there is a probability distribution and it happens to choose the one with the highest probability. There is no direct mapping between a particular state to ONLY a particular action but a bunch of actions with varying probabilities. I don't understand.

"which implies that there is a probability distribution", what implies that? Probability distribution over what? What does "maximization" have to do with a probability distribution? Q-learning, to compute the target, chooses the value associated with the action of the highest value (i.e. it computes the target as if you assumed that you will take the greedy action). This post is very confusing. Please, next time, before drawing or making possibly wrong assumptions and conclusions, ask a question about what you don't know. That's better than asking a question that is based on wrong assumptions.

@nbro: I think that the OP is honestly confused about what the Q values represent and where probabilities come into it. I am not sure we will get a better description of the issue.

Q-learning uses the maximizing value at each step,

Mostly true. The target policy that Q-learning learns the action values of is the one with the maximum value. While training, Q-learning will take one action randomly (typically with a high probability of taking the action with maximum value), whilst it makes updates to value estimates assuming it will always take the maximising action next.

which implies that there is a probability distribution and it happens to choose the one with the highest probability.

Not true. This is not implied at all. The action values that Q-learning estimates are not probabilities, but expected sums of future reward. The probability distribution for exploring actions is added outside of the Q table or Q function estimate. There is no implied probability distribution of actions in the target policy. When implementing the target policy, you may decide to break ties randomly, but that is not an important detail.
It is worth noting that even if you were working with a table of action probabilities, then an agent that always chose the one with the maximum probability would be deterministic. A list of numbers from a table or non-stochastic function (which is how a Q table or Q function is implemented, and also how policy functions are implemented for methods that do process probabilities), even if it represents probabilities, cannot be random in itself. Instead, it must be interpreted by a process that decides how to use them. A process that includes a random number generator can use the numbers to generate a probability distribution that it samples from.
In Q-learning, the process that updates the Q table estimates does not include a random number generator, so as a consequence it is deterministic. However, the choice of which actions to explore is often random, and it is sometimes the case that the environment includes randomness in state transitions or reward values. So Q-learning taken as a whole is a random process.

Based on the last paragraph, is it sufficient to conclude whether or not a policy is stochastic or deterministic depends on how the TD target ( max Q for Q learning) is updated, and not depends on behavior policy?

@AungKhant You should read and understand any RL method you want to understand in detail, as the functions used vary a lot. As a rule of thumb most RL control methods will converge towards deterministic policies, but many will represent a current target policy which is stochastic. Q learning and other off-policy value-based methods have target policies which are not random, but are instead deterministic greedy action choice over the current value estimates.


text:
Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$?
Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$?
The return for an MDP is usually defined as
$$G_t=R_{t+1}+R_{t+2}+ \dots +R_T$$
Why is this defined as the return? Is there anything useful about this?
It seems like it's more useful to define the return as $$G_t=R_0+ \dots+R_t,$$ because your "return", so to speak, is the "profit from investment" so it seems like your return will be your accumulated reward from taking actions up to that point.

It wouldn't make sense to define the return as you propose, from time 0 to $t$. Once we are in a state at time $t$ we don't care what the returns have been, rather what they will be in the future, thus returns are defined as the total sum of discounted rewards from the current time step onwards. This allows the agent to make decisions about which actions to take based on how valuable taking said action is in the current state at time $t$ -- clearly the rewards previous to this have no effect upon that.

You say "Once we are in state $t$", but the return does not necessarily depend on any state. I think you're referring to the definition of the state-action (or state) value function, which is the expected return for taking action $a$ in state $s$ and then following a certain policy, so you should clarify that (although the OP accepted this answer, so I guess he's happy with it).

I meant to say a state. Once we are in state $s$ at time $t$ then we are interested in future returns from this time step onwards, regardless of what has happened.

Yes, we want to predict the future, but maybe the original doubt arouse because the OP was thinking something like "Shouldn't we also use the past to predict the future?".


text:
For episodic tasks with an absorbing state, why can't we both have $\gamma=1$ and $T= \infty$ in the definition of the return?
For episodic tasks with an absorbing state, why can't $\gamma=1$ and $T= \infty$?
In Sutton and Barto's book, they say that, for episodic tasks with absorbing states that becomes an infinite sequence, then the return  is defined by:
$$G_t=\sum_{k=t+1}^{T}\gamma^{k-t-1}R_k$$
This allows the return to be the same whether the sum is over the first $T$ rewards, where $T$ is the time of termination or over the full infinite sequence, with $T=\infty$ xor $\gamma=1$.
Why can't we have both? I don't see how they can both be set to those parameters. It seems like, if you have an absorbing state, the rewards from terminal onward will just be 0 and not be affected by $\gamma$ or $T$.
Here's the full section of the book on page 57 in the 2nd edition

I think the reasoning behind this also leads to why for policy evaluation where
$$v_\pi(s)=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]$$
"Has an existence and uniqueness guarantee only if $\gamma < 1$ or termination is guaranteed under $\pi$"(page 74). This part I'm also a bit confused by, but seems related.

$T = \infty$ and $\gamma = 1$ cannot be both true at the same time because the return defined in equation 3.11 is supposed to be a unified definition of the return for both continuing and episodic tasks. In the case of continuing tasks, $T = \infty$ and $\gamma = 1$ cannot be true at the same time, because the return may not be finite in that case (as I think you already understood).
Moreover, note that, in that specific example of the book, they assume that the agent ends up in an absorbing state, so this specific sum is finite, no matter whether $T$ is finite or $\infty$, given that, once you enter the absorbing state, you will always get a reward of $0$. Of course, if you discount those specific rewards, the sum will still be finite. However, in general, if you had a different MDP where the absorbing state is not reachable (i.e. the episode never ends), then the return could not be finite.


text:
What happens when the agent faces a state that never before encountered?
I have a network with nodes and links, each of them with a certain amount of resources (that can take discrete values) at the initial state. At random time steps, a service is generated, and, based on the agent's action, the network status changes, reducing some of those nodes and links resources.
The number of all possible states that the network can have is too large to calculate, especially since there is the random factor when generating the services.
Let's say that I set the state space large enough (for example, 5000), and I use Q-Learning for 1000 episodes. Afterwards, when I test the agent ($\max Q(s,a)$), what could happen if the agent faces a state that did not encounter during the training phase?

Having too many states to actually visit is a common problem in RL. This is exactly why we often use function approximation. If you replace your q table with a good function approximator such as a neural network, it should be able to generelize well to states it has not yet encountered.
If you do not use a function approximator but stick with a table, the agent will have no idea what to do when it encounters a new state. For more information,  see Reinforcement Learning  by Sutton and Barto, chapter 9.

I will try to explain this problem with the very tangible example of chess. In chess, the number of possible states is any configuration that you can make with the pieces on the board. So, the starting position is a state, and after you did one move you are in a different state. The total number of chess states is more than $10^{100}$. It is therefore very unlikely that a chess bot has seen all the states in training when playing a match.
So, how does the algorithm solve this? For the answer, we have to look at how an RL algorithm chooses which move is the best. This obviously depends on the implementation of the algorithm, but, generally, the calculation of 'how good' a move is, is done with the use of an approximation taking into account the 'potential future reward'. If you capture the queen, that would probably be good (not a chess expert here), even though you have not seen this exact state before. If you go further than this, a network might be able to approximate what happens many moves in the future. The specifics come down to implementation, etc., but this is the gist of it.

I'm not sure how this answers the question: "what could happen if the agent faces a state that did not encounter during the training phase?". In this answer, it seems that you're just describing what a value function is (apart from giving the example of chess, but that was not the question). So, can you clarify how this answers the question?

@nbro not an answer, but a valid commentary on the underlying problem in general, with a relatable example (chess) for which there has been robust validation of statistical techniques.

@DukeZhou This answer contains some useful info, right, but it needs to be edited to more directly address the question. It seems that some info is missing.


text:
Why does each component of the tuple that represents an action have a categorical distribution in the TRPO paper?
I was going through the TRPO paper, and there was a line under Appendix D "Approximating Factored Policies with Neural Networks" in the last paragraph which I am unable to understand

The action consists of a tuple $(a_1, a_2..... , a_K)$ of integers $a_k\in\{1, 2,......,N_k\} $ and each of these components is assumed to have a categorical distribution.

I can't seem to get how each component has a categorical distribution. I think it should be the tuple that has a categorical distribution.
I think I am getting something wrong.

I'm not sure specifically which Atari games present this type of action space, but you can imagine a game in which you can perform multiple different types of actions at the same timestep (i.e. the different "factors" they mention in the paper).
As an example, imagine a game in which you can both move and jump at the same time. In that case, you might have a 4-dimensional discrete action space for moving (NSWE), and a 2-dimensional discrete action space for jumping (yes/no jump), both of which will require a Categorical distribution which has the size of that factor ($N_k$ in the paper).
So in this case, you would need to have a categorical distribution for each factor, unless you were to turn these two factors into 1 joint 4*2-dimensional factor and learn a single categorical distribution on that (which would likely be less efficient).