text:
Are the capabilities of connectionist AI and symbolic AI the same?
The universal approximation theorem says that MLP with a single hidden layer and enough number of neurons can able to approximate any bounded continuous function. You can validate it from the following statement

Multilayer Perceptron (MLP) can theoretically approximate any bounded, continuous function. There's no guarantee for a discontinuous function.

We can express any MLP in terms of algebraic expressions. And the expressions can be considered as symbolic-AI.
So, can I infer that symbolic AI algorithms can theoretically approximate any bounded continuous function?
If not, then why can't there be a one-one mapping between MLP and symbolic-AI algorithm?

It depends on how one defines connectionist AI. If we define connectionist AI as neural networks that allow for arbitrary real-valued parameters (as required by the universal approximation theorem), it theoretically possesses greater computational capabilities compared to symbolic AI. Unfortunately, real-valued neural networks are only an idealized computational model. To my knowledge, there is no evidence that real-valued neural networks can be realized in the physical world because:

Most real numbers do not have finite representations (in this sense, neural networks cannot be regarded as algebraic expressions); according to modern physics (quantum mechanics), such real numbers cannot be stored;

Operations on real numbers (even very simple cases, like summing two real numbers) are themselves uncomputable. Therefore, if you accept the Church-Turing thesis, even the inference of real-valued neural networks cannot be physically realized.

If the parameters of neural networks are restricted to rational numbers, then neural networks will always have finite representations, and the inference with such neural networks is normally computable in deterministic polynomial time. In this case, based on a recent work:
Zhang et al. 2024: A Theory of Formalisms for Representing Knowledge (available at https://arxiv.org/abs/2412.11855)
there exists some lightweight symbolic formalism of knowledge representation (e.g., a fragment of first-order logic) that is recursively isomorphic (consequently, one-one mapping) to the class of rational neural networks, and thus the capability of connectionist AI in this case would be strictly weaker than that of symbolic AI.

Are the capabilities of connectionist AI and symbolic AI the same?

No, not usually. Why not usually? Neural networks (connectionist AI) are usually used for inductive reasoning (i.e. the process of generalizing given a finite set of observations), while symbolic AI is usually used for deduction (i.e. to logically derive conclusions from premises).
What is inductive reasoning? Let's say that all the birds that you have observed so far in your life fly, so your inductive thought is that all birds must fly, although you haven't seen all birds, so there could be exceptions (like penguins).
What is deductive reasoning? Let's say that you know that all humans are mortal (there's no exception). You know that Socrates is a human. So, you logically deduce that Socrates is mortal. If that was not the case, then either the premise was wrong or maybe Socrates is not a human.

We can express any MLP in terms of algebraic expressions. And the expressions can be considered as symbolic-AI.
So, can I infer that symbolic AI algorithms can theoretically approximate any bounded continuous function?

Now, if MLPs were a subset of symbolic AI, then we could conclude that symbolic AI can approximate bounded continuous functions. However, the definition of symbolic AI is usually restricted to knowledge-based and logic-based systems, so systems that write (e.g. using propositional logic) premises or facts (in knowledge bases) to deduce conclusions (other facts) from them. So, although $f(x) = \sigma(ax + b)$ (which can represent e.g. a perceptron) is a function with symbols $a$, $x$, $b$ and $\sigma(\cdot)$, these symbols are not used in the same way as the symbols in symbolic AI. They are variables that do not represent premises or conclusions.

If not, then why can't there be a one-one mapping between MLP and symbolic-AI algorithm?

I don't know if there can be a one-to-one mapping between some symbolic AI and neural networks.
However, it is possible to combine the two approaches. For example, in the context of knowledge graphs, which can be viewed as a way to represent facts and relations between those facts as a graph, we can learn embeddings (using machine learning), which can later be used to perform inductive reasoning on the knowledge graph.
There are other examples of attempts to combine symbolic AI with machine learning and neural networks. A famous example is the Markov Logic Network (MLN) (by Richardson and Domingos), which combines first-order logic with probabilistic graphical models. A related approach is used, for example, used in OpenCog, which is a software platform for AI and AGI. In fact, I think it is widely believed that inductive and deductive reasoning are both necessary for an AGI. The AGI needs inductive reasoning for situations that involve uncertainty (most cases) and deductive reasoning for the remaining cases (e.g. doing math, i.e. we expect an AGI to be able to prove theorems, as we do). Another example is a combination of knowledge graphs with MLNs.


text:
How to assign tasks to users with ranking?
I'm trying to write an automatic assignment algorithm for the following problem:
I have $N$ tasks and $M$ users. For each task, I have a ranking for each user for "how related it is to that user". The ranking is a floating-point number in the [0, 1.0] range. The sum of all ranks is 1. I need to write an algorithm that will create the overall based assignment for all tasks. It has 2 constraints:

Overall best correctness of assignment.
Properly balanced - I can't have 1 user assigned 20 tasks while all others are assigned 1-2.

So far, from studying multiple input sets, I found that a task that has a user with a rank over 0.7 should be assigned to that user no matter what, because it's a really strong indicator of a correct assignment. After that, I tried to balance all the remaining tasks.
So, for the input of:

tasks = [t1, t2, t3,... , tn]
task_user_scores = [[s11, s12,...s1m], [s21, s22, ..., s2m],..., [sm1, sm2, ..., smm]]
first_iteration_limit = float, [0, 1.0], I use 0.7, as I described earlier.
per_user_limit = int, how many tasks to strive to assign per user.

I do:
Step 1
for ti in tasks
    if some sij > 0.7
        assign ti to user j

Step 2
for ti in unassigned tasks
    compute user deviation(max deviation is abs(n - per_user_limit), udj is abs(assigned_to_j - per_user_limit) from per_user_limit(ud),
    compute adjusted scores as follows sij * (1 - udj).
    Select the user from the list using weighted random, if selected user already has more assigned tasks than per_user_limit, select again(the random select happens a finite number of times, I found that 10 is fine).
    Otherwise, if the user didn't reach per_user_limit assign ti to user j.

Step 3
for ti in unassigned tasks
    assign ti to the user in the top 5 with the least number of tasks assigned to it.

I tried to format your post to improve the clarity, but the pseudocode is still not very clear. I would recommend that you improve that part even further (so that we don't have very long lines). Anyway, just to clarify, when you say you have a "ranking", you mean that you have a ranking for each user of the tasks that they prefer. So, if task 3 is the more preferred task for user 1, then task 3 will have the highest score for user 1, e.g. 0.9.  If, after task 3, we have task 5, then the score will be like 0.8 for user 1. Right?

Although you didn't answer to my question above, you may want to look into linear programming, constrained satisfaction problems and constrained optimization.

source: Stack Exchange

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

sort: votes


text:
How does the distribution of the parameters change in logistic regression?
I have my own data to train a logistic regression model (for a multi-class classification task), and I want to know how the distribution of weight parameters changes after each update with gradient descent.
For example, let's say that there are $f$ many features for each input, and the weight $W$, which is a $c \times f$ matrix, where $c$ is a number of classes, is initialized with uniform distribution $U(-1/\sqrt{f}, 1/\sqrt{f})$, which is LeCun uniform initialization.
For each step of gradient descent with Cross-Entropy loss, it will be updated as
$$
W_{t+1} = W_{t} - \alpha \frac{\partial \mathcal{L}}{\partial W_{t}}
$$
where $\alpha$ is a learning rate and the gradient is given
$$
\frac{\partial \mathcal{L}}{\partial W_{t}} = \frac{1}{n} (\mathbf{y} - \mathbf{p})^{T}\mathbf{X}
$$
where $\mathbf{X} \in \mathbb{R}^{n\times f}$ is an input matrix, $\mathbf{y} \in \mathbb{R}^{n \times c}$ is one-hot encoded labels, and $$\mathbf{p} = \mathrm{softmax}(\mathbf{X}W_{t}^{T}) \in \mathbb{R}^{n \times c}$$
is the model's output (predicted probability for each example & class).
What I want to know is how the distribution of $W_{t}$ changes as $t$ increases, if some information about $\mathbf{X}$ is known. More precisely,

Is it possible to get a bound of $\mathbb{E}[||W_{t}||_{\infty}]$ in terms of $t, \alpha, ...$? We may assume that the input $\mathbf{X}$ is also bounded (in the sense that $||\mathbf{X}||_{\infty} \leq M$ for known $M$.) I have a really rough bound for $||W_{t}||_{\infty}$, but it is not good enough.
Are there any works in this direction for other models, such as MLPs?

When I plotted the value $||W_{t}||_{\infty}$ for each $t$, then it seems that it increases sub-linearly in $t$, but

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


text:
What is the difference between an on-policy distribution and state visitation frequency?
On-policy distribution is defined as follows in Sutton and Barto:

On the other hand, state visitation frequency is defined as follows in Trust Region Policy Optimization:
$$\rho_{\pi}(s) = \sum_{t=0}^{T} \gamma^t P(s_t=s|\pi)$$
Question: What is the difference between an on-policy distribution and state visitation frequency?

Where are you getting the definition of state visitation from, exactly (it's probably S&B again, but I'd like to know which chapter and section)? I am asking because the term is being defined for a purpose - also note unlike the distribution, its value can be above 1 for any given state.

Definition of state visitation is from TRPO paper.

In the TRPO paper, $\rho_{\pi}(s) = P(s_0=s) + \gamma P(s_1=s) + \gamma^2 P(s_2=s) + \dots$ and goes on forever not until $T$, at least, that's how it seems to be defined. You can find it under equation 1 and they don't call it exactly "state visitation frequency" but "(unnormalized) discounted visitation frequencies"

1.First of all. The on-policy distribution $\mu(s)$ is a probability distribution. So, obviously, it is different from state visitation frequency $\rho_\pi(s)$, since $\rho_\pi(s)$ is not normalized to $1$. In the following discussion I'll assume that we are interested in the difference between TRPO's state visitation frequency $\rho_\pi(s)$ and Sutton and Barto's "time spent in a state" $\eta(s)$.
2. Continuing task setting. The TRPO paper you are referring to never considers episodic tasks and your expression for $\rho_\pi(s)$ is not present in the paper. So, first I'll derive the equality for discounted infinite sum. First, we start with basic MDP probability relations:
$$ \begin{array}{rcl}
P(s_0 = s) & = & h(s) \\
P(s_t = s) & = & \displaystyle\sum_{\bar{s}}P(s_{t-1} = \bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a) \quad \text{for}\quad t \ge 1
\end{array}$$
The second equation can be derived using the law of total probability and marginalization.
Multiply the second equation by $\gamma^t$ and summing by $t$. Note that I'm summing form $t=1$ to infinity:
$$ \begin{array}{rcl}
\displaystyle\sum_{t=1}^\infty \gamma^tP(s_t = s) & = & \displaystyle\sum_{t=1}^\infty \gamma^t\displaystyle\sum_{\bar{s}}P(s_{t-1} = \bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)\\
 & = & \gamma \displaystyle\sum_{\bar{s}}\left(\displaystyle\sum_{t=1}^\infty \gamma^{t-1}P(s_{t-1} = \bar{s})\right)\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)
\end{array}$$
Next I'm adding the $P(s_0=s)=h(s)$ equation to both sides, and I'm shifting the summation bounds $(\sum_{t=1}^\infty \alpha_{t-1} = \sum_{t=0}^\infty \alpha_{t} )$ for the sum in curly brackets.
$$ \begin{array}{rcl}
\displaystyle\sum_{t=0}^\infty \gamma^tP(s_t = s) & = & h(s) + \gamma \displaystyle\sum_{\bar{s}}\left(\displaystyle\sum_{t=0}^\infty \gamma^{t}P(s_t = \bar{s})\right)\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)
\end{array}$$
The expression in curly brackets is the same as expression on the lhs and the same as $\rho_\pi(s)$ (for $T=\infty$).
$$\rho_\pi(s) =  h(s) + \gamma \displaystyle\sum_{\bar{s}}\rho_\pi(\bar{s})\displaystyle\sum_{a}\pi(a|\bar{s})p(s|\bar{s},a)
$$
And that is the same equation as Sutton and Barto have for $\eta(s)$ - the "time spent in a state $s$". (They do mention the $\gamma$ factor in the quoted text.) So one can say that TRPO's $\rho_\pi(s)$ is the same as Sutton and Barto's $\eta(s)$ - at least in case of $T=\infty$.
3. Episodic task setting. In the episodic task setting (which is, again, is not considered in the TRPO paper) the derivation above is almost identical. A very important detail is the caveat that is mentioned in the quoted text: the whole expression is defined for the set of non-terminal states $s\in{\mathcal{S}}$. (Check the definitions of $\mathcal{S}$ and $\mathcal{S}^+$ in the section 3.3). The summation over $\bar{s}$ is, thus, also goes over $\mathcal{S}$ and this justifies the "shifting of the summation bounds" step in the derivation above:
$$ \displaystyle\sum_{\bar{s}\in\mathcal{S}}\left(\displaystyle\sum_{t=1}^T\gamma^{t-1}P(s_{t-1} = \bar{s})\right) \cdots = \displaystyle\sum_{\bar{s}\in\mathcal{S}}\left(\displaystyle\sum_{t=0}^T\gamma^{t}P(s_t = \bar{s})\right) \cdots$$
This works because $s_T$ is always the terminal state, so $P(s_T = \bar{s}) = 0$ and one can add this term to the sum.


text:
Which pre-processing steps are necessary for Deep Learning models to solve a document classification problem?
I have created a data set with 30.000 text documents (each text file is rather small with respect to its length), which are labelled with 0 and 1. Using this data set, I want to train machine learning and deep learning models in order to be able to classify new text files.
On the one hand, I want to use classical machine learning models (such as logistic regression, random forest, SVM, etc.) with the Bag of Words/TF-IDF approach. This requires extensive text pre-processing, such as tokenization, stemming, converting to lower case, removing of stopwords and punctuation, lemmatization, etc.
On the other hand, I want to use new deep learning models (such as RNN, LSTM, BERT, XLNET, etc.).
Which pre-processing steps are necessary/advantageous for these deep learning models? Should I also use tokenization, stemming, converting to lower case, removing of stopwords and punctuation, lemmatization, etc. or can I omit most of these steps?

It depends on the type of model you use and the task, you are attempting to solve.
Almost all the preprocessing steps that you mention remove some information from the text. If you think the removed information is irrelevant (stopwords, suffixes, sentence boundaries), you can happily do it and use your favorite architecture. If you think, the linguistic information in the text is relevant (e.g., you need to care about negations), it is better not to remove any words and only tokenize the text (perhaps into subwords).
In general, lower-casing and stemming can help with data sparsity. However, if you work with a language for which a large pre-trained models exist (and you do not care much about efficiency), it is always better to use a pre-trained BERT-like model. The pre-trained models come with their own preprocessing and tokenization (e.g., WordPiece in case of BERT), and using a different pre-processing would just break them.


text:
Why is the simplest U-Net architecture giving the best (but not good enough) results on a multi-class segmentation on microscopic data?
Currently, I'm trying to optimize a training process of a neural net to improve final results. The problem I'm dealing with is multiclass segmentation on microscopic data.
The paradox is that the best (and not sufficient) result is giving the simplest U-Net architecture on the original dataset. If I try a deeper or more complex model (e.g. r2unet), the final segmentation is significantly worse. If I try on the fly augmentation - worse as well. Changing a complex model into a more shallow one didn't help either (just tried out the other way than making it more complex).
Now, I'm trying to make a custom loss function work to improve the segmentation.
Any ideas what might be a root cause? Or any other ideas that could improve the result?
To get more specific, here's an example of the data. The initial 4000x4000 images are cut to 512x512, which results in a little over 3700 images. Most of them don't include the classes and is just background, that's why I'm trying to make another loss functions work, as well as weighted classes.

So far, I'm using categorical cross-entropy as a loss function, however, dice, Jaccard, the focal losses seem could be more suitable and once I'll finish my computations I'll try to make these work again, so far my tries weren't really compatible with Keras, at least it seemed.
The size of U-Net

depth = 5
first conv layer has 64 filters, goes up to 1024.

R2U-Net

depth 5
first layer 64filter (tried also 32)

Would be helpful to know more info about your training regime. How many images (an example would be nice as well)? Dice, focal loss, cross entropy, something else? U-Net initialize how?

You're using only 3700 training instances? That seems too little. Also, how many test instances do you have?

@nbro - at this very moment I have two versions of data I'm testing to use

these 3700 rotated each by 90,180,270 degrees = almost 15k
on the fly augmentation (horizontal, vertical flipping, cropping, sliiight blurring, rotating from -180 to 180 degrees, all with a certain probability of happening). The paradox is that the simple, 15k datapoint set makes significantly better results.

the 3700/15k is a total number of images that I further split to train, test, validation parts by 75/15/10


text:
How can a neural network distinguish a rotated 6 and 9 digits?
Rotated MNIST is a popular dataset for benchmarking models equivariant to rotations on $\mathbb{R}^2$, described by $SO(2)$ group or its discrete subgroups like $\mathbb{Z}^{n}$:

Group equivariant convolutional networks
Harmonic networks

It consists of all digits from 0 to 9 rotated on an arbitrary angle from $[0, 2 \pi)$. However, what makes me a bit puzzled is that digits $6$ and $9$ seem to be confused by any learning algorithms, since from the view of human perception $6$ rotated by 180 degrees is equivalent to $9$ and vice versa.
The original paper in the description of Rotated MNIST doesn't comment on this point at all, which is strange, since it is a very natural question to ask.

In the paper Oriented Response Networks - authors plot embeddings of rotated digits projected via t-SNE on a 2d plane. There is a clear separation between all rotated versions of 6 and the rotated version of 9 for ORN.

I do not understand how it can be achieved? Probably, the networks understand much more in writing the digit, there are some subtle features, inaccessible to humans, but recognizable by powerful classifier?

I think by writing left to right people create clockwise and counterclockwise patterns in the rounded parts of their typography.
For example, I think it'd be pretty unusual to write a 9 like this -->
I bet you could also detect the original orientation of the 8s if you wanted. The circle that isn't continuous/smooth is most likely at the top.

Great explanation and great examples, @pip.pip!!  Using your insight, I think I can pick out the 6's and 9's in many examples in the post.  (I think I can also pick out the top and bottom of the 8's.)  Having said that, it seems like the separation between 6's and 9's in the paper is perhaps a little too good, no?

"... since from the view of human perception 6 rotated by 180 degrees is equivalent to 9 and vice versa.".

Only with some typefaces, and almost never with handwritten text; someone would have to make an extra effort to make their text ambiguous when rotated (or mirrored).
A "6" has a bent tail, while a "9" tends to be straighter.
Similarly with a "4", tending to have a closed top and a flattened midline, while an "h" can never have a closed bottom and usually has a curved midline.
It's how the character is written in its natural orientation that determines its appearance, rotation (and scaling) has no effect on that.
With a 9-pin Dot Matrix Printer all bets are off, since the usual font was not designed to differentiate between rotated characters.

If anything, the fontographer cheated and rotated the characters whenever possible to avoid the effort of creating a new character from scratch.
Later fonts such as Data-70 were able to avoid rotation ambiguities at the cost of readability, and increased geekiness.


text:
What exactly is embedding layer used in RNN encoders?
I am reading about RNN encoders. I came across the following line from this code. And I am facing difficulty in understanding the theoretical details regarding it.
emb = self.drop(self.encoder(input))

The input is a tensor of shape $[32, 100]$. Here 32 is the batch size and 100 is the length of the sentence. Hundred elements are indices to the words (from the dictionary) that are used in the sentence. We can observe that the output emb is later passed to the rnn (LSTM/GRU) layer.
output, hidden = self.rnn(emb, hidden)

So, to me, it looks like that self.encoder is the necessary step while using the RNN encoder. So, I am interested in what it actually does.
When we see about self.encoder, it is an Embedding layer. The description for this layer is as follows

A simple lookup table that stores embeddings of a fixed dictionary and
size.
This module is often used to store word embeddings and retrieve them
using indices. The input to the module is a list of indices, and the
output is the corresponding word embeddings.

When we see about self.drop, it randomly keeps zero in the embeddings.

During training, randomly zeroes some of the elements of the input
tensor with probability p using samples from a Bernoulli distribution.
Each channel will be zeroed out independently on every forward call.

The outputs for both self.encoder(input) and self.drop(self.encoder(input)) are $[32, 100, 3000]$.
I have doubt(s) on the bolded parts of the description of the Embedding layer. The description is saying the Embedding layer uses/contains(?) a lookup table. The description says Embedding layer stores and retrieves word embeddings.
The doubts are

Generally, does an embedding layer calculate word embeddings or just store and retrieve them from the table? If it does not calculate them, then who will calculate the embeddings? If you can also comment on the specifics of PyTorch, I would appreciate it.

What exactly is an embedding layer? Is it a collection of neurons or any other?

If you look at the source code of PyTorch's Embedding layer, you can see that it defines a variable called self.weight as a Parameter, which is a subclass of the Tensor, i.e. something that can be changed by gradient descent (you can do that by setting the parameter requires_grad of the Parameter to True). In other words, the Embedding layer is not just a look-up table, but it's a layer where you have parameters (i.e. the embeddings, which are stored in self.weight) that can also be learnable. You can also initialize these embeddings (i.e. the self.weight parameter) from pre-trained ones using Embedding's method from_pretrained. In this case, you should set require_grad to False.
Generally, one can define an embedding layer $\mathcal{f}$ as a function that receives the raw inputs $\mathbf{i}$ (e.g. in the case of word embeddings, the raw inputs might be integers: one for each word) and transforms them to embeddings $\mathbf{e}$, which can be statically defined (e.g. from pre-trained embeddings or hardcoded), randomly initialized and/or learnable (during the training of the neural network). In other words, $f(\mathbf{i}) = \mathbf{e}$. So, that's why we pass $f(\mathbf{i})$, i.e. the embeddings, rather than $\mathbf{i}$.

I will maybe improve this answer later by referring to word2vec.


text:
Is there some way for us to know if the neural network internally finds an association between labels?
I have a question about the association between labels. Say my neural network performs multi-labeling in its output layer. Now, if one of the labels is for whether a person lives in city $X$, another for if they have a wiki article, and finally a third for if that person is a millionaire. Let us assume that these are highly correlated.
Is there some way for us to know if the neural network internally finds an association between these three labels?

As far as I understand, no. Neural networks are not explainable AI. Explainable AI is more based on symbolic AI (expert systems, inference rules, etc....) like RefPerSys hopes to become in 2022


text:
Is image machine translation done in two steps?
Suppose I have images of hand-written Japanese text. If I want to translate those images, would my ML algorithm be a 2-step model (for example, a CNN to convert the image into Japanese characters/tokens and then feed those tokens in an RNN)? Is this normally how it would be done, or is there an end-to-end solution?

As far as I know, this is always done in separate steps. The reason is the availability of training data. For the recognition task (scene text recognition or handwriting recognition), the available data are monolingual.
A solution would be generating synthetic visual data from parallel corpora. Very recently, there was a paper at EMNLP 2021 that did exactly this and show high robustness towards OCR errors. However, they do not evaluate the model on real-world images and still assume two steps: recognition and translation.
There is also a domain mismatch between what is typically in handwriting and how the usual data machine translation data look like. From the machine translation perspective, this could be best approached as a domain adaptation problem (e.g, using domain-specific back-translated data). This would quite unhandy with an end-to-end recognition and translation system.


text:
What exactly do gradient-based saliency map tell us?
As far as I understand, gradients are supposed to tell us 1) the magnitude and 2) direction, to update a parameter such as to minimize the loss function.
Regarding saliency maps, which use gradients with respect to the input, do the gradients give us the same information?
Consider vanilla saliency maps [1] (i.e. gradients-only) and integrated-gradients [2] (using a baseline image), with grayscale images.
Do the (vanilla) gradients give us the amount and direction a pixel-value needs to change? OR does the magnitude tell us for the amount of in loss based on a minimal change in pixel-value?
In simpler terms: does magnitude signify:

amount of change required in a pixel-value to have some change (in loss?) or

amount of change in (loss?) based on a minimal/local change in pixel-value?

Saliency Map:  https://arxiv.org/abs/1312.6034 (Specifically section 3)
Integrated Gradients:  https://arxiv.org/abs/1703.01365

I believe the magnitude will be related to how sensitive that input variable is. That is: If you only look at the gradient of the output with respect to the input: then a change of a specific input feature, then the gradient is how much it will affect the output. So: a small change in input could be a large change in output. If you want more interpretation on what it means, it would vastly change based on implementation and is problem specific.


text:
Fine tuning BERT for token level classification
I want to try self-supervised and semi-supervised learning for my task, which relates to token-wise classification for the 2 sequences of sentences (source and translated text). The labels would be just 0 and 1, determining if the word level translation is good or bad on both the source and target sides.
To begin, I used XLMRoberta, as I thought it would be best suited for my problem. First, I just trained normally using nothing fancy, but the model overfits after just 1-2 epochs, as I have very little data to fine-tune on (approx 7k).
I decided to freeze the BERT layers and just train the classifier weights, but it performed worse.
I thought of adding a more dense network on top of BERT, but I am not sure if it would work well or not.
One more thought that occurred to me was data augmentation, where I increased the size of my data by multiple factors, but that performed badly as well. (Also, I am not sure what should be the proper number to increase the data size with augmented data.)
Can you please suggest which approach could be suitable here and if I am doing something wrong? Shall I just use all the layers for my data or freezing is actually a good option? Or you suspect I am ruining somewhere in the code and this is not what is expected.

What do you mean by "I just trained normally using nothing fancy"? Do you mean you're using supervised learning with a labelled dataset? Or are you using self-supervised learning? Or maybe semi-supervised learning, as you wrote at the beginning of your post? It's not clear how much data you're using and for what. Are you just fine-tuning this "XLMRoberta", or training it from scratch? It seems that you also tried to fine-tune it, so I assume that you also trained it from scratch.

In both cases, you need to explain 1. how much training, validation and test data do you have 1.1. when you train from scratch, 1.2. when you fine-tune.

Thanks @nbro , sorry for the less information. By nothing fancy, i meant i fine tuned the xlmroberta for the problem without augmentation, just the normal training dataset(7k) and validated for 1k dataset. I havent used semi supervised learning as of now, i am just doing a typical supervised fashion. I cannot train the model from scratch as i have a little dataset , so i was trying ti improve my finetuning with augmented dataset, which did not helped.


text:
What would be a reasonable option for clustering for unknown number of clusters and a lot of outliers?
I am implementing the CV detection pipeline with the use of SIFT and KNN Matcher.
Image keypoints matched to the query keypoints produce the following image:

The matched objects have a lot of key points on them and there are some false matches. I would like to consider spots with a lot of matches as detections of the query object and ignore isolated points.
What would be an appropriate clustering method, where one can put a limit on points in a neighborhood of some radius to declater this set of points a cluster?
KMeans is not a good idea, since it takes a fixed number of points and doesn't throw outliers.
From the algorithms proposed in sklearn, seems like DBSCAN and Agglomerative clustering are a good choice, since they allow for variable number of clusters, unknown apriori and outlier removal.
Or there is better alternative?


text:
Which value to propagate in Monte Carlo Tree Search in a non-zero-sum game?
Usually, when I read about Monte Carlo Tree Search, values between 0 and 1 (or values between -1 and 1) are backpropagated, depending on whether the simulation was a win or loss.
Now, suppose you have an AI which needs to play a game in which it is also important to score as high as possible. For example, it needs to score as many points as possible in the game of Carcassonne against one other player.
What kind of options are there for the values being backpropagated in such cases? Can you just backpropagate the number of points, and then, depending on the node, use the points of only the players in UCT? Or would that lead to the search converging to a worse move than the optimal move?

In theory: yes, you can backpropagate any sort of scores you want to maximise. They don't have to be restricted to just a small, discrete set of values such as $\{-1, 0, 1\}$, and also do not have to be in any particular range like $[-1, 1]$ or $[0, 1]$.
However, in practice it may still be useful if you can normalise whatever "raw" scores you have down to some smaller range (like the ranges mentioned above). This can primarily be useful for hyperparameter tuning. For example, consider the UCB1 equation that we normally use in UCT during tree traversal:
$$a^* = {\arg\max}_a \left( Q(s, a) + C \sqrt{\frac{\ln(\sum_{a'}N(s,a'))}{N(s,a)}} \right).$$
We typically have a $C$ hyperparameter / constant in there, which controls our tradeoff between exploration and exploitation. Higher $C$ means more exploration, lower $C$ means more exploitation. The $Q(s,a)$ term is the average of the scores backpropagated so far for action $a$ in state $s$. In this equation, the $Q(s, a)$ and the $C$ terms are sort of "competing" against each other, so their optimal values are closely related to each other. If you take an existing problem and multiply all the score values by, say, $100$, you'd probably also want to multiply whatever your $C$ constant used to be by $100$ to get the same behaviour again from your tree search.
Actually, what really matters for this story is not even the raw magnitudes of your $Q$ values, but rather the magnitudes of the typical differences you see between $Q$ values for different actions in the same state. So, if your problem only has $Q$ values that lie in the range $[99, 101]$, you'll actually want a similar $C$ constant as when you have $Q$ values in the range $[-1, 1]$, but if your problem has $Q$ values in the range $[-100, 100]$, you'll likely want about $100$ times as big a $C$ value too.
If you can roughly normalise your values down to approximately a $[-1, 1]$ or $[0, 1]$ range, you can feel relatively confident that similar kinds of $C$ values as typically used by other people in zero-sum settings will also work fine (like, $C$ values somewhere in the range $[0, 2]$, more often than not below $1$.... but the ideal constant can also very often depend on lots of other factors).

Aside from all that, I usually also tend to prefer values that do not have a crazy high magnitude because it makes me feel like I won't have to worry about annoying things like numerical overflow when summing up lots of values from lots of different iterations through the same node.

What if you are playing a game where the maximum reward is unbounded or unknown, i.e. when you don't know how to normalize values or Q to, say [-1, 1]?

@Darkdragon84 Such a setting is more annoying, but it is possible to work around it by tracking your min/max bounds online, and normalising based on those (also updating by re-normalizing throughout the tree later on if you observe new minima/maxima). This paper has some details (in second-to-last paragraph of Section 4.4): https://jair.org/index.php/jair/article/view/11099

thanks for the quick reply @Dennis Soemers


text:
What is the definition of a trace of a tensor?
Tensor is a multi-dimensional ordered collection of elements, which is used in deep learning to store and process data as well as intermediate steps.
We are aware of the trace of a two-dimensional tensor i.e. matrix. It is defined as the sum of the diagonal elements of the matrix.
Is there any definition for the trace of a tensor?

The concepts of trace and tensor also appear in other contexts outside of machine learning (ML), like quantum computing, so an answer to your question may be given independently of ML, but that may not be useful, as these concepts may be defined and implemented differently in the context of ML, which seems to be the case.
The concept of trace, in mathematics, is apparently known as tensor contraction. I don't know if that definition is consistent with the definition(s)/implementation(s) of trace used in machine learning.
I found at least 2 (different) definitions of tensor trace in machine learning. The first definition is provided by the TensorFlow implementation of the trace of a tensor. For completeness, let me write here their definition of the trace.

trace(x) returns the sum along the main diagonal of each inner-most matrix in x. If x is of rank k with shape [I, J, K, ..., L, M, N], then output is a tensor of rank k-2 with dimensions [I, J, K, ..., L] where output[i, j, k, ..., l] = trace(x[i, j, k, ..., l, :, :]).

So, essentially, for each most inner 2d matrix in this tensor, you compute the trace (for that matrix), then return the result as another tensor, which has 2 fewer dimensions than the original tensor (because a matrix has 2 dimensions, and, by computing the tensor of a matrix, you reduce a matrix to a number, which is a 0-dimensional tensor).
They give these examples
x = tf.constant([[1, 2], [3, 4]])
tf.linalg.trace(x)  # 5

x = tf.constant([[1, 2, 3],
                 [4, 5, 6],
                 [7, 8, 9]])
tf.linalg.trace(x)  # 15

x = tf.constant([[[1, 2, 3],
                  [4, 5, 6],
                  [7, 8, 9]],
                 [[-1, -2, -3],
                  [-4, -5, -6],
                  [-7, -8, -9]]])
tf.linalg.trace(x)  # [15, -15]

I think this definition is easy to understand, but I don't remember having ever used it, but I could be wrong.
In fact, PyTorch does not seem to implement the trace for tensors, but only matrices. If you executed the following code, you should get an error that tells you that's not possible.
import torch  # install also numpy

x = torch.tensor([[[1, 2, 3],
                   [4, 5, 6],
                   [7, 8, 9]],
                  [[-1, -2, -3],
                   [-4, -5, -6],
                   [-7, -8, -9]]])

print(torch.trace(x))  # [15, -15]? No, you get an error.

So, as I was suspecting, the tensor trace may not be terribly useful in ML, at least, for tensors with more than 2 dimensions.
By the way, in the paper A Survey on Tensor Techniques and Applications in Machine Learning (2019) Yuwang Ji et al. (p. 6 of the pdf), you find another definition of tensor trace, which I don't think it's equivalent to the definition used by the TF implementation.


text:
Is there a mathematical formalism to deal with a missing reward signal?
Typically, a Reinforcement Learning learning problem is formalized as finding an optimal policy for a Markov Decision Process (MDP). In many real-life situations, however, an agent can only get partial information from the environment. For example, Partially Observable MDPs are used to model the case where the agent does not fully observe the state.
I was wondering whether there is any well-established formalism for the case where the agent does not fully observe the reward signal.
In particular, I am thinking about the case where for every state-action pair $(s, a)$ the agent receives the reward $R(s, a)$ with probability $1 - \varepsilon$ and does not receive anything with probability $\varepsilon$. Of course, in principle, this setting can be thought as a regular MDP with a stochastic reward, but here I would like the agent to behave optimally w.r.t. to $R$.
I would really appreciate if you could point some relevant literature to me!

This does not directly answer your question (I think), but there are ways of dealing with problems where the reward function (RF) is not specified or it's not easy to specify it correctly. The basic idea is to learn the RF itself (this is sometimes known as inverse RL or reward learning, especially when you are given an optimal policy: that's why it's called IRL because, usually, in an RL problem, you want to find the policy from the RF), but you can also use behaviour cloning (i.e. you don't use a reward function at all, and learn a policy from examples taken from another policy).

@nbro Thanks for the comment! Good point! In fact I asked this question precisely because I am reading about IRL at the moment :)
Oversimplifying, RL deals with MDP with observable reward function and IRL deals with the case where the reward function is missing.  I was wondering whether some intermediate scenarios have been studied..

I am not sure if it's intermediate, but in the paper "Inverse Reward Design", if I remember correctly, they formulate the problem of learning a "correct" function from "observed RFs" (i.e. non-optimal or partial/incomplete ones) in a Bayesian/probabilistic setting. So, in a way, if I remember correctly, they kind of combine IRL with RL because they need to solve the RL problem too (but I could be recalling that wrongly, so you may want to check the paper).

Let me know if this answers your question so that I eventually give a formal answer below with this info.

@nbro Thanks a lot for the paper! I'll have a look and I'll let you know!

Your setting (of randomly dropping out reward signals) impacts expected future reward by multiply everything by a common factor $(1-\epsilon)$.
As reinforcement learning (RL) control is based on maximising expected future reward, and multiplying by a positive constant does not affect ranking of action values, all existing RL methods will cope just fine without modification. They will behave optimally in the limit of training - with all the usual caveats of course - although learning will be slower due to added variance, and value estimates lower.
If the agent is allowed to observe that the reward signal is missing (as opposed to being an observed zero reward), then it could additionally estimate $\epsilon$, and correct its learned value function. I would recommend this is handled at the end of training as a separate function instead of modifying $Q(s,a)$ during training. That is because initial estimates for $\epsilon$ are likely to be inaccurate and make learning even slower (at least for TD learning due to bootstrapping on less accurate values).
Whether any corrected value function makes sense will depend on what it means to "not observe" the reward, and what the reward represents in terms of the environment and agent's goals. You may not need to know if all you care about is whether the agent is behaving optimally.
The setting becomes more complex if $\epsilon$ is made a function of $a$, $s$ or both, and solutions will be different depending on whether this function is known or unknown.

Thank you very much! You are totally right.. Yeah, the way I have formulated the problem is actually very trivial, as you correctly noticed.  As you pointed out, the situation is less trivial if $\varepsilon$ depends on $s$ and/or $a$.
Do you think there could be any other meaningful notion of "partial observability" for the reward function?


text:
How the vector-space isomorphism between $\mathbb{R}^{m \times n}$ and $\mathbb{R}^{mn}$ guarantees reshaping matrices to vectors?
Consider the following paragraph from section 5.4 Gradients fo Matrices of the chapter Vector Calculus from the textbook titled Mathematics for Machine Learning by Marc Peter Deisenroth et al.

Since matrices represent linear mappings, we can exploit the fact that
there is a vector-space isomorphism (linear, invertible mapping)
between the space $\mathbb{R}^{m \times n}$ of $m \times n$ matrices
and the space $\mathbb{R}^{mn}$ of mn vectors. Therefore, we can
re-shape our matrices into vectors of lengths $mn$ and $pq$,
respectively. The gradient using these $mn$ vectors results in a
Jacobian Matrices can be of size $mn \times pq$. .... In practical
applications, it is often desirable to re-shape the matrix into a
vector and continue working with this Jacobian matrix: The chain
rule... boils down to simple matrix multiplication, whereas in the
case of a Jacobian tensor, we will need to pay more attention to what
dimensions we need to sum out.

What I understood from the paragraph is: There is always a one-one mapping(?) between $\mathbb{R}^{m \times n}$ and $\mathbb{R}^{mn}$. So, we use this property to replace any element in $\mathbb{R}^{m \times n}$ (matrix) to an element in $\mathbb{R}^{mn}$.
I have doubt on how the property allows us to replace the matrix by vector without any discrepancies?

Can you please provide more details about your doubt? Why do you think that we cannot map $m \times n$ matrices to $m*n$ vectors without "any discrepancies"? What discrepancies or problems do you potentially see here? I am asking this question because I don't see any problem, but I am not thinking about all problems now. So, maybe, there's a problem or this has side-effects/consequences for certain operations.

@nbro The paragraph is saying vector-space isomorphism as the only requisite for reshaping. So, I asked with the intention of how it can assure compatibility with all tasks.

An isomorphism $T$ between vector spaces $V$ and $W$ over the same field $K$ (for example, $K = \mathbb{R}$) is defined as a bijective (i.e. 1-to-1 and onto, which makes a bijection an invertible function) transformation (a function) that preserves the 2 main properties

scalar multiplication: $T(c\mathbf {u} )=cT(\mathbf {u} )$, where $c \in K$ and $\mathbf {u} \in V$
vector addition: $T(\mathbf {u} +\mathbf {v} )=T(\mathbf {u} )+T(\mathbf {v})$, where $\mathbf {u}, \mathbf {v} \in V$

Linear maps preserve these 2 properties, but not all linear maps are bijective, so not all linear maps are isomorphisms. In fact, linear maps that are bijective are called linear isomorphisms. You can denote an isomorphism between $V$ and $W$ as follows (to emphasize that it's not just a linear map): $T: V {\overset {\sim }{\to }} W$.
The fact that an isomorphism is invertible means that there exists a function $T^{-1}$ that transforms any element of $W$ to any element of $V$.
So, if there's an isomorphism $T$ between $V = \mathbb{R}^{n \times m}$ and $W = \mathbb{R}^{nm}$ (note that I am not proving it here, but it's probably not complicated to prove), then it implies that, for each $\mathbf {v}_W \in \mathbb{R}^{nm}$, you can use $T^{-1}: \mathbb{R}^{nm} {\overset {\sim }{\to }} \mathbb{R}^{n \times m}$ to retrieve the corresponding vector $\mathbf {v}_V \in \mathbb{R}^{n \times m}$ (not that, in the context of vector spaces, matrices are also vectors, which is just the name used to denote objects in vector spaces).
This should prove why, if reshaping is an isomorphism, then you can perform operations first on $\mathbf {v}_W$ and then go back to $\mathbf {v}_V$.

To prove reshaping is an isomorphism, you need to prove it's bijective and show that it preserves scalar and vector addition. This shouldn't be too difficult (I think, at least if you had one course in linear algebra), but if you have problems, let me know and I can try to help.

I think the textbook is making it unnecessarily complicated. $\mathbb{R}^{n\times m}$ and $\mathbb{R}^{nm}$ both represent the same vector space, a real vector space of dimension $nm$. (So clearly they are isomorphic because they are the same.)
The interpretation of them being either a space of vectors or a space of matrices is an artificial distinction in this context.

$\mathbb{R}^{n\times m}$ and $\mathbb{R}^{nm}$ are different spaces: matrices and vectors. Each real value in a matrix has a row and a column. Each value in a vector has just an index. There are two standard mappings between them: row-major and column-major, plus many uncommon mappings. Therefore they are not "the same" space (although they are isomorphic.) You must specify which mapping you want to use before moving between them. The author is teaching math, not engineering, and therefore must make this distinction.

@Eponymous Both of them describes a vector space of dimension $nm$. In this case, multiple automorphisms exist for this object, two of which you gave as example. An automorphism always exists for any object (the identity mapping), and that is what the OP wanted to show.

@Eponymous "the author is teaching maths, not engineering" absolute savage hahahaha


text:
Where do the objective functions proposed in this paper by Carlini-Wagner attack come from?
I'm trying to understand the paper by Carlini and Wagner on deep neural networks adversarial attacks. On page 44, in Section V-A, it is explained how the loss function to the described problem was designed. One part of this loss function is called "objective function".
There are 7 such functions proposed on which experiments are made, but there is no information provided on where they came from and why those are chosen.
Is this some commonly known thing in the Deep Learning area? Do you recognize them and can tell me where they came from and why they were chosen?
\begin{align}
f_{1}\left(x^{\prime}\right) &= -\operatorname{loss}_{F, t}\left(x^{\prime}\right)+1 \\
f_{2}\left(x^{\prime}\right) &= \left(\max _{i \neq t}\left(F\left(x^{\prime}\right)_{i}\right)-F\left(x^{\prime}\right)_{t}\right)^{+} \\
f_{3}\left(x^{\prime}\right) &= \operatorname{softplus}\left(\max _{i \neq t}\left(F\left(x^{\prime}\right)_{i}\right)-F\left(x^{\prime}\right)_{t}\right)-\log (2) \\
f_{4}\left(x^{\prime}\right) &= \left(0.5-F\left(x^{\prime}\right)_{t}\right)^{+} \\
f_{5}\left(x^{\prime}\right) &= -\log \left(2 F\left(x^{\prime}\right)_{t}-2\right) \\
f_{6}\left(x^{\prime}\right) &= \left(\max _{i \neq t}\left(Z\left(x^{\prime}\right)_{i}\right)-Z\left(x^{\prime}\right)_{t}\right)^{+} \\
f_{7}\left(x^{\prime}\right)&= \operatorname{softplus}\left(\max _{i \neq t}\left(Z\left(x^{\prime}\right)_{i}\right)-Z\left(x^{\prime}\right)_{t}\right)-\log (2)
\end{align}

Hello. Welcome to Artificial Intelligence Stack Exchange! It seems that you're asking us about the origin of multiple functions. I would recommend that you focus on 1 (objective) function for each post. If you have multiple questions, ask each of them in a separate post (note that asking us to explain a full paper and say it's only one question is not the correct approach).

Having said that, I just opened the pdf you're linking us to, but it has only 19 pages (while you point us to the 44 page). In this linked paper, the page should be 6. I would also recommend that you tell us what you read from the paper and briefly tell us what you know about the topic and/or machine learning in general. Finally, in the paper, they tell us in the paper why they enumerate these functions, i.e. they should meet the requirements that they talk about in the paper just before these equations. So, what exactly are you asking here?

ok, so my guess was that functions used here are from some set of functions used in machine learning for this specific task. Just like we've got a few different loss functions (cross entropy, MSE, MAE), a few different activation functions (sigmoid, ReLU) etc. So maybe those presented on image also have some common name?

so in other words I'm not asking about 7 functions separately. I am interested in what the whole collection represents, not the individual elements. Btw: you have page numbers written at the bottom of each page

In the paper, they write "We define an objective function $f$ such that [this constraint is met]. There are many possible choices for...".


text:
How much labelling is required for NER with SpaCy?
I have transaction data and I would like to extract the merchant from the transaction description. I am new to this but I just came across Named Entity Recognition and SpaCy. I have hundreds of thousands of different merchants.
Some questions that I have:

How much labelling do I need to do given the number of merchants I need to extract?

How many different instances of the same merchant I need to label to get decent results?

Could you provide an example of a transaction description? (with fake name of course). Unless the descriptions are really extensive it sounds hard to me to believe that the pre trained model from spacy perform badly and require further training.

There is no specific number of labels that is "enough". For simple cases you can start with a few hundred examples, but normally you'll want several thousand.
Since you have a large number of classes your problem might be a harder one, but on the other hand it could be easy if most of your text is like "This merchant is called XXX".

It depend on your workflow, language of text. Your official guide at here https://github.com/explosion/assets/blob/main/Prodigy/Prodigy_NER_flowchart_v2_0_0_light.pdf . You can know how many data is enough. You can see few number 4000, 25%, 2000, etc.

In my experience with NER with Spacy, and disagreeing with this stackoverflow solution and as @polm23 rightly mentioned, a several thousand samples for each entity should generate/predict entities, otherwise spacy would just recognise them based on default spacy entity types (mainly 'work-of-art')

As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review


text:
Are derived or computed inputs bad for CNNs?
I am building a CNN and am wondering if inputting derived or computed inputs are generally bad for the effectiveness of CNNs? Or just NNs in general?
By derived or computed values I mean data that is not "raw" and instead is computed based on the raw data. For example, in a very simple form, using time-series data as the "raw" data and computing a 30 day SMA as a "derived/computed" value, and as another input.
Is this bad practice at boosting the effectiveness of the network? If it is not a bad practice, are there any tips on what kind of computed values someone should consider when adding new inputs?
The goal of my NN is for building predictions in time-series data.

It seems to me that, you're basically asking whether feature engineering is bad or not. It's not necessarily bad, but the main advantage of deep neural networks stem from the fact that they do feature engineering for you. The earlier layers learn/extract useful features, and the last layer (usually a fully-connected one), just does some kind of regression on the extracted features.
All in all, feature engineering is not necessarily bad, but rather, the deep neural networks do it for you instead. So, they render feature engineering somewhat obsolete. However, if you've rather small amount of data, or using a shallow network for whatever reason, feature engineering can still benefit you a lot.

What you are describing could be considered feature engineering as noted by @SpiderRico, and I fully agree with his response.  However, what you are describing can also be considered preprocessing.  (I will not get into whether preprocessing is really just a form of feature engineering. That is a topic for another day.)
Preprocessing such as centering or scaling of features can also be considered "derived or computed inputs".  Preprocessing is not only not considered bad practice, it is--dare I say--almost considered standard or even best practice for the deep learning.  Preprocessing can improve speed of convergence and model performance.
For time series data, 1D kernels of you CNNs will learn "smoothening" operations if relevant to the target.  See Kaggle, Computer Vision course, Lesson 4 Exercise.  That is probably not a "preprocessing" step that you would need to do.  However, you may still need to do some sort of normalization of your time series data.


text:
Are Genetic Algorithms suitable for a problem with a non-unique optimal solution?
I was wondering if a genetic algorithm is useful if the optimization problem has several optimal solutions.
My thought was that I should not use it since when combining two members of a population who have good fitness but are close to different optimal solutions, the child will get retarded.
Is this thinking wrong? If so, why?

It sounds as though your approach results in a single child.  In our genetic implementations, we always have multiple children; some are averages, some are mutations, etc.  However, our generations always additionally contain $n$ top performers from the previous generation and slightly mutated versions of those top performers.  We find this allows us to find multiple optimal solutions since we allow multiple paths to be followed.

have you checked this article on wikipedia about evolutionary multimodal optimization? https://en.wikipedia.org/wiki/Evolutionary_multimodal_optimization

I don't think I've ever seen a genetic algorithm applied to a problem where there was a unique optimal solution!

Genetic algorithms (GA) have populations where it has an offspring in every generation usually the same quantity than the original population, so, if a child results from two good solutions (parents) but very different and it has a bad fitness, it will be not selected for being part of the next generation (elitism, where only the best n individual survive). But maybe you can find a new and good solution from that combination, and, in that case, it will be part of the new generation.
Maybe, if your problem has multiple solutions, the population can be formed by clusters of solutions that improve between them.
But there are many algorithms in GA (and Evolutionary Algorithms in general), so you need to read the details. Fortunately, there are many frameworks where only you need to define your problem and it can rapidly make comparisons between them.

Genetic algorithms like many other machine learning algorithms have two forces in action, exploration and exploitation.
For GAs these are crossover and mutation.  Crossover (the production of a child from two parent members) can often produce wildly different children dispersing them around the solution space.  Exploring the solution space, if you will.
If two parents are near optimal solutions and their alleles are significantly different unless the crossover happens to also be near another optimal solution it is likely to produce a poorly scoring child.
But that is not the only mechanism.  Mutation makes minor adjustments to a member of the population.  Along with elitism, often nudging the population towards nearby optimums, exploiting their proximity to a good solution.
So, while crossover between two parents near different optimums may not produce strong children, mutation may move the children of similar parents towards a local optimum.  Lastly, lets not forget that crossover need not necessarily widely spread children.  It is possible in both single and two point crossover to produce a child which differs from a parent by a single allele.


text:
What is the "contradictory loss" in the "Old Photo Restoration via Deep Latent Space Translation" paper?
In page 4 of the paper Old Photo Restoration via Deep Latent Space
Translation, it says the encoder $E_{R,X}$ of $VAE_1$ tries to fool the discriminator with a contradictory loss to ensure that $R$ and $X$ are mapped to the same space. What do they mean by "contradictory loss"?

The contradictory loss is the same loss function that the discriminator would normally use, except with deliberately incorrect labels. That is, when you train the generator, the output of the generator is fed to the discriminator, but instead of the correct label (typically $0$ for a false image), the opposite label is applied (e.g. $1$ for a real image).
This label is condractictory in that it is incorrect and the opposite of the ground truth. However, this is useful, because reducing the loss of this signal represents the goal of the generator. It is important to note that during this phase of the training, you should not update any parameters of the discriminator. The process is followed in order to find gradients for improving the generator only.


text:
Is it possible to use self-supervised learning on different images for the pretext and downstream tasks?
I have just come across the idea of self-supervised learning. It seems that it is possible to get higher accuracies on downstream tasks when the network is trained on pretext tasks.
Suppose that I want to do image classification on my own set of images. I have limited data on these images and maybe I can use self-supervised learning to achieve better accuracies on these limited data.
Let's say that I try to train a neural network on a pretext task of predicting the patch position relative to the center patch on different images that are readily available in quantity, such as cats, dogs, etc.
If I try to initialise the weights of my neural network, then do image classification on my own images, which are vastly different from that of the images used in the pretext task, would self-supervised learning work because the images for the pretext and downstream tasks are different?
TLDR: Must the images used in the pretext task and the downstream tasks be the same?

This question is related to https://ai.stackexchange.com/q/17231/2444, but probably not a duplicate, and no answer there actually answers the/your question.

No, the images do not need to be same. You can use different images for downstream task however you need to do some changes in model definition while loading model state_dict as CNN architecture used for pretext task 'relative patch location', assume Alexnet will expect 2 patches as input.


text:
What is the intuition behind equations 10, 11 and 12 of the paper "Noise2Noise: Learning Image Restoration without Clean Data"?
Can anyone help me understand these functions described in the paper Noise2Noise: Learning Image Restoration without Clean Data
I have read the portion A.4 in the appendix but need a more detailed and easier to understand explanation. Especially where signum or sign function (sgn) is coming from along with other explanations.
(10),(11),(12)


text:
What's the purpose of layers without biases?
I noticed that the TensorFlow library includes a use_bias parameter for the Dense layer, which is set to True by default, but allows you to disable it. At first glance, it seems unfavorable to turn off the biases, as this may negatively affect data fitting and prediction.
What is the purpose of layers without biases?

Before anything, having option is not bad. Besides I think some applications do not need bias. For example if if I'm not wrong, in CBOW (Continuous Bag Of Words for word embedding) you don't need bias.

@amin You say "Besides I think some applications do not need bias.", but I think the question is really: "Why do some applications not use/need bias". If you don't have the answer to this question, besides providing the usual explanation of why the bias can be useful, then I think you should upvote this question/post, so that maybe it attracts someone that knows the answer. Personally, I don't know the answer of when you would strictly not need the bias (and thus when you can disable it), so it would be nice to have some guidance on when to disable it (because not really necessary).

@nbro, is this the right stackexchange to ask questions like this, or it is more datascience? Where is the line drawn?

@markmark This is a theoretical ML question, so it is perfectly suitable for AI SE, and I think it's a question that other people could also have, so I think it's useful. Unfortunately, it has not received too much attention, but this is more or less normal (especially, in the last months): sadly, there aren't many people contributing to the site as much as I would like. In any case, I think this question would also be on-topic on Data Science SE and Cross Validated SE.

Bias is one of the hyperparameters in neural networks, which let you shift activation function. Disabling bias means setting bias to be zero.
Even though, in many cases, bias is a big help for successful learning, in some cases, you may want to add an extra constraint to your neural network in finding the objective function. For example, in the paper below, a zero-bias layer as the last layer helps increase the output's interpretability.
https://ieeexplore.ieee.org/abstract/document/9173537

It would be nice if you could describe in which sense no bias makes the output more interpretable (according to that paper).


text:
Suppose every-visit MC was used instead of first-visit MC on blackjack. Would you expect the results to be different?
This is a question from page 94 of Sutton and Barto's RL book 2020.
I read in someone's compiled GitHub answers to this book's exercises their answer was: "No because each state in an episode of blackjack is unique."
I think my answer is more yes, but I'm thinking in terms of casino blackjack, where they have multiple decks shuffled together and add in the dropped cards back into the deck every X games in order to prevent card counting and 1 game can be seen as an episode. I think in this case that first-visit MC and every-visit MC would have drastically different results, given that, at the start of the new episode, the state of the deck, which is only partially observed, will change the value of taking an action given a state (because I believe the cards left in the deck affect the value of an action, but the deck is not totally observable).
If this is blackjack, where the discarded cards are added back in and shuffled every episode, I'll agree that it shouldn't make a difference.
Are there any flaws in my conjecture?

Can you please provide the link to the specific Sutton and Barto's book that you're reading (given that there are many versions online)? Also, you say "someone's compiled GitHub answers to this book's exercises". Can you provide the link to the repo?

I believe the question is here: http://incompleteideas.net/book/RLbook2020.pdf#page=94 The so-called GitHub solution is here: https://github.com/mharbuz/rlbook-exercises/blob/master/chapter5.md Now I have found an arguably more authoritative answer from here https://tams.informatik.uni-hamburg.de/lectures/2015ss/vorlesung/ML/folien/rl2.pdf#page=52 which reads "states never recur in the task, so no difference between first-visit and every-visit MC"

In the book, Sutton and Barto, second edition (Reinforcement Learning: An Introduction) example 5.1 (Blackjack) in the second paragraph the author explicitly states that the version of Blackjack he is considering has in infinite deck with replacement - and so there is no utility to keeping track of the cards dealt.


text:
What is the impact of changing the crossover and mutation rates?
What is the impact of using a:

low crossover rate

high crossover rate

low mutation rate

high mutation rate

The crossover rate, $p_c \in [0, 1]$, is a hyper-parameter that controls the rate at which solutions are subjected to crossover. So, the higher $p_c$, the more crossovers you perform, so the more diversity (in terms of solutions/chromosomes) you may introduce in the population. Typical values of $p_c$ are in the range $[0.5, 1.0]$.  For example, in this simple implementation, I used $p_c = 0.8$. In this case, I manually searched for this value (and it didn't take me much time to make the GA find the solution I was looking for), but in other cases/problems you may need to perform some hyper-parameter optimization (e.g. with grid search).
The mutation rate, $p_m \in [0, 1]$ (also a hyper-parameter) controls the rate at which you mutate single chromosomes or the genes of single chromosomes. For example, if you have a binary chromosome of $n$ bits, you could flip the $i$th bit with probability $p_m$, for all $i$ independently. Mutation can prevent premature convergence, but, if $p_m$ is very high, the genetic algorithm becomes a random search, so the value of $p_m$ is typically not high. This paper (which you probably should read because it contains more information about the mutation and crossover operations, although it is a bit old) states that typical values are in the range $[0.005, 0.05]$, but, in this implementation, I used $p_m = 0.5$.
So, in general, higher values of these rates promote exploration at the expense of exploitation. In this sense, this is similar to the $\epsilon$ in the $\epsilon$-greedy behaviour policy in Q-learning (a famous reinforcement learning algorithm).
However, note that each of these operations may undo the other operation. For instance, let's suppose that we have the binary chromosomes $p_1 = [0, 1, 0]$  and $p_2 = [0, 0, 1]$, which we can combine by replacing (with probability $p_c$) the bit at position $i$ of $p_1$ with the bit of the chromosome $p_2$ at the same position $i$. So, after the crossover, you could get the children $c_1 = [0, 0, 0]$ and $c_2 = [0, 1, 1]$. If you perform a mutation by flipping the bits, then you could end up with the same chromosomes as the original ones, that's also one of the reasons why you may not want to have a very high mutation rate. So, it's not completely true that, the higher the mutation rate, the more you explore, because you can end up with the same solutions as before, so you have not explored anything.
You could also have an adaptive value for these parameters. See e.g. this paper for an example of such an adaptive schedule.


text:
How did the variance and double summation of the covariance come to the L2 minimization equation?
I am trying to understand the last two lines of this math notation (from this paper).

How did the Var and double summation of the Cov come to the equation?
The first two lines I understood something like $(a-b)^2 = a^2 -2ab +b^2$.

As in the second line, the first two terms are $\mathbb{E}_{\hat{y}}$, it means the variable of the expectation is $\hat{y}_i$ and you can take out $y_i$s from $\mathbb{E}_{\hat{y}}$s. Now we can use $\mathbb{E}\{\hat{y}_i\} = y_i$ and rewrite the terms of the second line likes the following:
$$
\mathbb{E}_{\hat{y}}(\sum_i y_i)^2 = (\sum_i y_i)^2 \\
\mathbb{E}_{\hat{y}}\left[(\sum_i y_i)(\sum_i \hat{y}_i)\right] = (\sum_i y_i) \mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i) = (\sum_i y_i)^2
$$
The second line is written based on linearity of the expectation and $\mathbb{E}\{\hat{y}_i\} = y_i$. Hence, we can rewrite the second line like the following as $\sum_i y_i = \mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i)$:
$$
\frac{1}{N^2}\left[\mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i)^2 - \left(\mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i)\right)^2\right]
$$
And the final step is using this formula $Var(X) = E(X^2) - (E(X))^2$  and take $X = \sum_i \hat{y}_i$:
$$
\frac{1}{N^2}\left[\mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i)^2 - \left(\mathbb{E}_{\hat{y}}(\sum_i \hat{y}_i)\right)^2\right] = \frac{1}{N^2} Var(\sum_i \hat{y}_i)
$$
From variance to covariance, you can use this formula: $$Var(\sum_{i=1}^nX_i) = \sum_{i=1}^n\sum_{j=1}^n cov(X_i, X_j)$$


text:
Why should variance(output) equal variance(input) in Xavier Initialisation?
In a lot of explanations online for Xavier Initialization, I see the following:

With each passing layer, we want the variance to remain the same. This helps us keep the signal from exploding to a high value or vanishing to zero. In other words, we need to initialize the weights in such a way that the variance remains the same for x and y. This initialization process is known as Xavier initialization.

Source https://prateekvjoshi.com/2016/03/29/understanding-xavier-initialization-in-deep-neural-networks/
However, the intuition behind why var(output) should equal var(inputs) is never explained. Does anyone know why intuitively var(output) should equal var(inputs)?

I have asked also this question and no answers are given. All the posts/blogs just refer to this but never touch on why this must be the case. Have you checked the original paper if they provide a justification?


text:
How can we derive a Convolution Neural Network from a more generic Graph Neural Network?
Convolution Neural Network (CNNs) operate over strict grid-like structures ($M \times N \times C$ images), whereas Graph Neural Networks (GNNs) can operate over all-flexible graphs, with an undefined number of neighbors and edges.
On the face of it, GNNs appear to be neural architectures that can subsume CNNs. Are GNNs really generalized architectures that can operate arbitrary functions over arbitrary graph structures?
An obvious follow-up - How can we derive a CNN out of a GNN?
Since non-spectral GNNs are based on message-passing that employ permutation-invariant functions, is it possible to derive a CNN from a base-architecture of GNN?

Why do you think that GNNs generalize CNNs? Where did you read this?

GNNs generalize in the sense that they can learn arbitrary functions over graphs of any size/shape, and that CNNs perform a more specific convolution operation over fixed dimension grid-like structures.

As far as I remember, the "convolution" performed by GNNs is not really the same as the convolution/cross-correlation performed by CNNs. I am not even sure why they called it convolution: as you say, it's a messaging passing algorithm, and I am not sure what the relationship between this message passing algorithm and the convolution is. Can you provide a link to a reliable source (e.g. a research paper) that talks about "GNNs being able to learn arbitrary functions over graphs" and how this relates to CNNs and the convolution?

@nbro, GNNs is the same as CNN except that CNN only works in euclidean space( I mean grid). GNN also extracts features via convolution operation on a graph just like CNN.

@SwaksharDeb I would like to see a complete proof that shows that the "graph convolution" (if we really can call it like that) is a generalization of the convolution used in CNNs. If I remember correctly, in GNNs, there's no concept of shifting a kernel, but you only have an aggregation step for each node (or edge), as far as I recall, and you do this for every node (or edge). These message passing operations have some similarities with CNN's convolution, i.e. they may do some kind of dot product, but I don't think that's sufficient to say that they are equivalent.

It's been a while I had to deal with GNNs, even when I had written the comments above, so I don't really remember the details. Right now, I remember that there are different variants of these message passing algorithms used in GNNs. Some of them work also on edges and not just nodes. So, I see it as a non-trivial task to fully show some kind of equivalence between the operations and CNN's convolution, if possible, but I don't exclude the possibility. Anyway, this is what this and the other duplicate question are asking people to show. If you know the complete answer, feel free to write it.

@nbro, your aforementioned argument is correct I am not saying it is wrong, just think it like this, in case of spectral graph convolution we transform the filter from the time domain to frequency domain and perform the convolution on frequency domain. This is the same convolution operation except that we are doing it in frequency domain in case of spectral graph convolution

Yes, a CNN can be formalized as a specific kind of GNN where nodes are connected together in a 2D lattice structure and the outer edge is padded with zeros. Down-sampling techniques or pooling layers are an additional operation which remove edge nodes or low activation nodes. Convolutional layers act in the same manner as GNN weights by comparing each node with it's neighbors.
Yes, GNNs are generalized architectures of CNNs. A CNN is derivable by treating the image as a lattice graph and augmenting pooling and/or down-sampling layers. N w x w convolutional kernels has a node with feature of length N interacting with a w-hop neighborhood. Any node of distance w is considered adjacent.
I am an expert on convolutional networks and not graph neural networks. Maybe these two articles would also be helpful.
https://towardsdatascience.com/understanding-graph-convolutional-networks-for-node-classification-a2bfdb7aba7b?gi=4c06cb6c8e30
https://medium.com/@rmwkwok/gnn-notes-series-explain-graph-convolutional-networks-gcn-with-knowledge-in-cnn-b827be1c872b
My goal in writing this was to provide a more novice accessible answer than the  others on this post.

Nice answer. Voted

Spectral Graph Convolution
We use the Convolution Theorem to define convolution for graphs. The Convolution Theorem states that the Fourier transform of the convolution of two functions is the pointwise product of their Fourier transforms:
$$\mathcal{F}(w*h) = \mathcal{F}(w) \odot \mathcal{F}(h) \tag{1}\label{1} $$
$$ w * h = \mathcal{F}^{-1}(\mathcal{F}(w)\odot\mathcal{F}(h))  \tag{2}\label{2}$$
Here $w$ is the filter in spatial domain(time domain) and $h$ is the signal in spatial domain(time domain). For images this signal $h$ is a $2D$ matrix and for other cases this $h$ can be a $1D$ signal.
Assume we have $n$ number of node in a graph. In graph fourier transform the eigenvalues carry the notion of frequency. $\Lambda$ is the $ n \times n$ egenvalue matrix and it is a diagonal matrix. We can write equation 2 as:
$$w * h = \phi(\phi^{T}w \odot \phi^{T}h) = \phi\hat{w}(\Lambda)\phi^{T}h \tag{3}$$
Here $\phi$ is the eigenvector matrix of graph Laplacian $\in R^{n \times n}$,
$\hat{w}(\Lambda)$ is the filter in spectral domain(frequency domain) $\in R^{n \times n}$ a diagonal matrix, $h$ is the $1D$ graph signal $\in R^{n}$ in spatial domain and w is the filter in spatial domain $\in R^{n}$.
Vanilla Spectral GCN
We define the spatial convolutional layer such that given layer $h^{l}$ , the activation of the next layer is:
$$h^{l+1}=\sigma(w^l*h^l)  \tag{4}\label{4},$$
where $\sigma$ represents a nonlinear activation and $w^l$ is a spatial filter and $h$ is the graph signal.
We can perform the above equation in terms of spectral graph convolution operation as:
$$h^{l+1}=\sigma(\hat{w}^l*\hat{h}^l)  \tag{5}\label{5},$$
where $\hat{w}$ is the same filter but in the spectral domain(frequency domain). In case of vanilla GCN this equation yeild to:
$$ h^{l+1} = \sigma(\phi\hat{w}^{l}(\Lambda)\phi^{T}h)  \tag{6}\label{6}$$
Now, we will learn the $\hat{w}$ using backpropagation.
This vanilla GCN has several limitations, like larger time complexity and this does not guarantee localization in the spatial domain that we get from CNN's filter.
In next works, such as SplineGCNs, ChebNet, Klipf and Welling's GCN, and many other works address those issues, and try to solve them.
Note that we can think of ChebNet and Klipf and Welling's GCN as a message-passing system, but, in the background, they are computing spectral convolution and also they use some standard assumption that's why we do not need any eigenvector and we implement them in the spatial domain, but still they are spectral convolution.
There is also another branch in graph convolution called spatial graph convolution. I only talked about the spectral graph convolution.

Ok, there are some terms here that I think you should define (in order to be fully clear). First, what do you mean by "graph signal"? What do you mean by "spectral" or "spectral domain"? Maybe you could link to this answer (written by me, btw) if you think it's correct and useful. Another thing that is unclear is how do you get from equation 4 to equation 5, and what is $\Lambda$.

Finally, to clarify, although in the past I actually came across all these concepts and now I recall them, you're essentially saying that, by performing a multiplication between $w$ and $h$ (e.g. in the spectral domain), we are performing actually a convolution in the spatial domain, because of the Convolution Theorem. I suggest that you edit this answer, which seems good, to emphasize this after you have shown equation 5. Another thing that you could clarify is: what is the dimensionality of $\hat{w}$ and what is the $\phi$ and $\Lambda$ actually defined.

Another thing that you should try to clarify is how what you have said relates to the actual convolution in the CNN. I know this may seem obvious, but you could try to make
a mapping between the two, in terms of symbols involved. Maybe you could also point to a resource that talks about the convolution in the spatial domain. If you clarify all these points (I know they are many, but I think it would be nice to have a complete answer), I will surely upvote this answer, as it seems consistent with my knowledge (which I now recall, given that you mentioned the convolution theorem).

@SwaksharDeb I like your answer. I voted for you. You had a -1, now it's 0 :)


text:
How significant is the decoder part of the capsule network?
Capsule Networks use an encoder-decoder structure, where the encoder part consists of the capsule layers (PrimiaryCaps and DigitCaps) and is also the part of the capsule network which performs the actual classification. On the other hand, the decoder attempts to reconstruct the original image from the output of the correct DigitCap. The Decoder in the Capsule Network is used as the regularizer of the network as it helps the network learn better features.
I can see how the decoder is helpful for datasets such as MNIST where all image classes have clear differences and the input size if the image is quite small. However, if the input has large dimensions and differences between image classes are quite small, I see the decoder network as overkill, as it will find it hard to reconstruct images for different classes.
In my case, my dataset consists of 3D MRI images of patients which have Alzheimer's Disease and those who do not. I am down-sampling the images and producing 8 3D patches which will be used as input to the network. The patches still have high dimensions considering that these are 3D, and there are not many clear differences between patches of the two image classes.
My questions here are:

How significant is the decoder part of the capsule network? CNNs that perform image classification, usually do not have a decoder part. Why does the capsule network rely on the decoder to learn better features?

Are there any alternatives to the decoder within the capsule network, acting as a regularizer? Can the decoder be ignored completely?


text:
What constitutes a large space state (in Q-learning)?
I know this might be specific to different problems, but does anyone know if there is any rule of thumb or references on what constitutes a large state space?
I know that, according to multiple papers, tabular Q-learning is not suitable for these problems with large state spaces, but I can't find any indication of what would constitute a large state space
I've been working on a problem where my state space is about 30x30 and updating my Q-learning with the tabular method runs and works well. Would 100x100 start to become too big or 400x400?

I know that this is true, but maybe you should cite 1-2 papers that state that Q-learning is not suitable for problems with "large" state spaces.

I know this might be specific to different problems but does anyone know if there is any rule of thumb or references on what constitutes a large state space?

Not really, it is all relative. There are two main ways in which the scale of a value table might be too much:

Memory required to represent the table. This is relatively simple to calculate for any size.

Time required to populate the table with accurate estimates. This depends on how you are collecting that data, and how much variance there is given the same state, action choices.

If you are using action values you need to allow for the fact that the table size is not just $|\mathcal{S}|$, but $|\mathcal{S} \times \mathcal{A}|$.
If you are running fast, local simulations of the environment, then table sizes of a million or even a hundred million are not unreasonable. Software language or library choice for the simulation and agent can have a significant impact at these larger scales.
If any of the state description is a continuous variable, then the table size would become infinite in theory, so no finite table that could actually be realised on a computer could fully capture it. You must use some form of approximation to get practical results. However, even then you can still use tabular approaches when approximation involves discretising the state variable directly - there are a few different methods used in machine learning to do that - e.g. tile coding. You can also use tile coding in large discrete spaces.

I've been working on a problem where my state space is about 30x30 and updating my Q-learning with the tabular method runs and works well. Would 100x100 start to become too big or 400x400?

It depends on the action space too, but 400x400 gives state space of 160,000. Assuming < 10 actions, then this is still well within the realm of tabular methods. You probably have less than 1,000,000 parameters to handle for a tabular method, which compares well to a moderately-sized neural network, with the advantage of better stability and possibility to create a fully optimal agent. If simulating the environemnt is fast, something at that scale may only take a few minutes to a few hours to fully optimise in tabular form.
As with most machine learning though, if you care about some optimisation, such as memory size of the agent, speed at which it solves the problem, or some other metric, then you will need to try experiments with different approaches. Then you will have some knowledge about best approach for your problem, given your definition of "best agent". The experience you gain with that might extend and apply to similar problems in future.


text:
What should the value of epsilon be in the Q-learning?
I am trying to understand Reinforcement Learning and already explored different Youtube videos, blog posts, and Wikipedia articles.
What I don't understand is the impact of $\epsilon$. What value should it take? $0.5$, $0.6$, or $0.7$?
What does it mean when $\epsilon = 0$ and $\epsilon = 1$? If $\epsilon = 1$, does it mean that the agent explores randomly? If this intuition is right, then it will not learn anything - right? On the other hand, if I set $\epsilon = 0$, does this imply that the agent doesn't explore?
For a typical problem, what is the recommended value for this parameter?

What does it mean when ϵ=0 and ϵ=1? If ϵ=1, does it mean that the agent explores randomly? If this intuition is right, then it will not learn anything - right? On the other hand, if I set ϵ=0, does this imply that the agent doesn't explore?

You are correct, when  ϵ=1 the agent acts randomly. When  ϵ=0, the agent always takes the current greedy actions. Both of these scenarios are not ideal. Always acting greedily will prevent the agent from exploring possibly better parts of the  state space, and instead the agent may get stuck in a local optimum. And always exploring randomly is obviously not ideal as well. Thus, we need to balance between these two. This is often called the balance between exploration and exploitation.

For a typical problem, what is the recommended value for this parameter?

ϵ is a hyper parameter. It is impossible to know in advance what the ideal value is, and it is highly dependent on the problem at hand. There is no general answer to this question.
That being said, the most common values that I have seen typically range between 0.01 and 0.1. But I want to stress, there is no ideal value that works for all problems. A typical strategy is to try several values and see which one works best. For more information, you might want to look up hyper parameter tuning.
Another common practice is slowly decaying epsilon over time (often this is called "annealing" or "simulated annealing"). Depending on the algorithm, decaying epsilon to zero may be a requirement for convergence. In some contexts, an algorithm that decays epsilon over time is called a GLIE algorithm. For example, see this.

You say "agent explores randomly.", but this is misleading because "to explore" in RL already implies (usually) that it's randomly, i.e. you take a random action. So, I think that this answer can be made more precise. By the way, you can type epsilon in latex here as $\epsilon$. Moreover, there may be cases/problems where $\epsilon$ needs to be higher  or smaller. To be honest, right now, no such an example comes to my mind, but it's likely there are some guidelines. It may also be worthing mentioning schedules to decay the this parameter.

@nbro. I will update answer. Regarding your final point, one example that comes to mind is in certain on policy algorithms, epsilon must he decayed to guarantee convergence. Sutton calls this GLIE.

Regarding guidelines for a higher epsilon: it is easy to construct a toy MDP where a higher epsilon converges faster. One classic example is a K armed bandit with very high variance. But its hard to draw a general guideline as to when it should be higher.

I wouldn't call annealing of the epsilon "simulated annealing" as "SA" refers to a specific algorithm/meta-heuristic, though it's possible that this term is also used in the context of annealing the epsilon. I don't remember that though.


text:
Why does off-policy learning outperform on-policy learning?
I am self-studying about Reinforcement Learning using different online resources. I now have a basic understanding of how RL works.
I saw this in a book:

Q-learning is an off-policy learner. An off-policy learner learns the value of an optimal policy independently of the agent’s actions, as long as it explores enough.

An on-policy learner learns the value of the policy being carried out by the agent, including the exploration steps.

However, I am not quite understanding the difference. Secondly, I came across that off-policy learner works better than the on-policy agent. I don't understand why that would be i.e. why off-policy would be better than the on-policy.

Here's a very related question https://stats.stackexchange.com/q/184657

You say "Secondly, I came across that off-policy learner works better than the on-policy agent. ". Where did you hear/read this?

This post contains many answers that describe the difference between on-policy vs. off-policy.
Your book may be referring to how the current (DQN-based) state-of-the-art (SOTA) algorithms, such as Ape-X, R2D2, Agent57 are technically "off-policy", since they use a (very large!) replay buffer, often filled in a distributed manner. This has a number of benefits, such as reusing experience and not forgetting important experiences.
Another benefit is that you can collect a lot of experience distributedly. Since RL is typically not bottlenecked by the computation for training but rather from collecting experiences, the distributed replay buffer in Ape-X can enable much faster training, in terms of seconds but not sample complexity.
However, it's important to emphasize that these replay-buffer approaches are almost on-policy, in the sense that the replay buffer is constantly updated with new experiences. So, the policy in the replay buffer is "not too different" from your current policy (just a few gradient steps away). Most importantly, this allows the policy to learn from its own mistakes if it makes any...
Off-policy learning, in general, can also refer to batch RL (a.k.a. offline RL), where you're provided a dataset of experiences from another behavior policy, and your goal is to improve over it. Notably, you don't get to rollout your current policy in any way! In this case, algorithms that worked well with a replay-buffer (like DQN, SAC) fail miserably, since they over-estimate the value of actions when they extrapolate outside the "support" of the dataset. See the BCQ paper which illustrates how a lot of "off-policy" algorithms like DQN fail when the "distance between the two policies is large". For this task, SOTA is a form of weighted behavioral cloning called Critic Regularized Regression (CRR).
It's also worth noting that importance sampling can correct off-policy gradients to be on-policy; but the farther away your target policy is, the larger the variance. This is especially deadly for long horizon tasks (often called curse of horizon).
To summarize, using replay-buffer (which makes the algorithm off-policy), especially a distributed one, can offer a lot of benefits over pure on-policy algorithms. However, this is a very special class of off-policy algorithms, where the behavioral policy is close to your policy.
But in general, off-policy is a lot harder than on-policy; you'll suffer from extrapolation bias if you use DQN-based approaches, and exponential variance blow-up if you use importance sampling to correct for it.

thanks for the response. But your answer goes way above my head :-(

which part do you want clarification on? do you understand on-policy vs. off-policy after reading @mugoh's post?

Maybe you should cite a paper that supports this "in this case, a lot of the traditional "off-policy" algos like DQN, SAC fail miserably, and the SOTA is a form of weighted behavioral cloning called Critic Regularized Regression (CRR)", for those not familiar with the SOTA. It's also not clear what you mean by the last sentence and in particular "but in general on-policy is much easier than off-policy!" (easier in terms of what?). Also, not sure why you say that DQN-based algorithms are "almost on-policy". That seems like saying that there are almost no off-policy algorithms.

I would actually say that off-policy algorithms can become on-policy, i.e. they generalize on-policy ones, but they are not "almost on-policy", if you want to be precise. Well, at least, I don't fully get what you mean by that.

This answer contains useful information, but I think it is pitched incorrectly to level of knowledge displayed in the question.

@nbro - being "almost on policy" means that the distribution of action choice between behaviour policy and target policy is close - e.g. a low KL divergence (although that is probably not the right measure for RL policy comparisons). If there was a high divergence in off-policy RL, then the learning rate per time step experienced can slow down dramatically, as the amount of data received that is relevant to the target policy will be low.

@NeilSlater Yes, sure you can measure the distance between two probability distributions, so that makes sense to say "almost on-policy" provided that is really true in the cases the OP is mentioning. When you say "high-variance", do you mean variance in the type of experience received? If the behaviour policy is very different from the target policy, I guess that having low variance of the experience received with the behaviour policy may not necessarily be a good thing. In any case, that statement is very compact and it's not fully/precisely clear what you mean by that.

@nbro: The variance in estimated returns increases, the more you have to correct for difference between on-policy and off-policy distributions.

@nbro you're right that off-policy generalizes on-policy, but as the two policies become more and more different, the MSE in the estimate will become very large

@kaiwenw yes, that's what Neil was saying above, and I see your point now. Can you please edit your answer to include these details? I think they are useful, then I could clean up all these comments (that may just be noisy).


text:
How can I use this Reformer to extract entities from a new sentence?
I have been looking at the NER example with Trax in this notebook. However, the notebook only gives an example for training the model. I can't find any examples of how to use this model to extract entities from a new string of text.
I've tried the following:

Instantiate the model in 'predict' mode. When trying this I get the same error reported in https://github.com/google/trax/issues/556 AssertionError: In call to configurable 'SelfAttention' (<class 'trax.layers.research.efficient_attention.SelfAttention'>)
Instantiate the model in 'eval' mode and then running model(sentence) as I would with other models. In this case the instantiation works but I get the following error when running the model: TypeError: Serial.forward input must be a tuple or list; instead got <class 'numpy.ndarray'>. Presumably this is because in 'eval' mode the model needs 2 entries passed in rather than one sentence

How can I use this Reformer to extract entities from a new sentence?

@SauravMaheshkar This is code you contributed to the trax repo. Are you able to help?