text:
How to prove the formula of eligibility traces operator in reinforcement learning?

I don't understand how the formula in the red circle is derived. The screenshot is taken from this paper

I recently got wondering about pretty much the same question as well. How can, for example, Q-Learning work using Auto-Differentiation when a constant is subtracted from an output of the actual Q-Network, i.e. predicted Q-Value, to compute an update of the predicted Q-Value (given that constants are commonly dropped during differentiation)? That is: why is the baseline estinate/constant, i.e. the part not being dependent on the policy network, not dropped during differentiation?

I will refer to $\mathcal T^{\pi} $as $\mathcal T$ and $P^{\pi}$ as $P$ for notational simplicity
\begin{align}
(\mathcal{T})^{n+1} Q &= \mathcal{T}(\mathcal{T}(...(\mathcal{T}(Q))))\\
&= r + \gamma P(r + \gamma P(...(r + \gamma P Q)))\\
&= r + r\sum_{i=1}^{n} \gamma^i P^i + \gamma^{n+1} P^{n+1} Q
\end{align}
\begin{align}
\mathcal{T}_{\lambda}Q &= (1-\lambda) \sum_{n=0}^{\infty} \lambda^n (\mathcal{T})^{n+1} Q\\
&=(1-\lambda)\{\lambda^0 (\mathcal T)^1Q + \lambda^1 (\mathcal T)^2Q + \lambda^2 (\mathcal T)^3Q + \ldots   \}
\end{align}
when you plug in expression for $(\mathcal T)^i Q$ inside this sum and rearrange you get 3 sums
\begin{equation}
\mathcal{T}_{\lambda}Q = (1-\lambda) \sum_{n=0}^{\infty} \lambda^n r + (1-\lambda)\sum_{n=1}^{\infty} \lambda^n \gamma^n P^n r + (1-\lambda)\sum_{n=0}^{\infty} \lambda^n \gamma^{n+1} P^{n+1} Q
\end{equation}

sum:
\begin{equation}
(1-\lambda) \sum_{n=0}^{\infty} \lambda^n r = r
\end{equation}
sum:
\begin{equation}
(1-\lambda)\sum_{n=1}^{k} \lambda^n \gamma^n P^n r = (1-\lambda\gamma P)^{-1}(1 - \lambda^k \gamma^k P^k)\lambda\gamma P r
\end{equation}
As $k \rightarrow \infty$ and since $\gamma < 1$ this is in the limit equal to
\begin{equation}
(1-\lambda)\sum_{n=1}^{\infty} \lambda^n \gamma^n P^n r = (1-\lambda\gamma P)^{-1}\lambda\gamma P r
\end{equation}
sum:
\begin{equation}
(1-\lambda)\sum_{n=0}^{\infty} \lambda^n \gamma^{n+1} P^{n+1} Q = (1 - \gamma\lambda P)^{-1}(1-\lambda)\gamma P Q
\end{equation}
If you combine all 3 you get
\begin{align}
\mathcal{T}_{\lambda}Q &= r + (1-\lambda\gamma P)^{-1}\lambda\gamma P r + (1 - \gamma\lambda P)^{-1}(1-\lambda)\gamma P Q\\
&= r+ (1-\lambda\gamma P)^{-1}(\lambda \gamma P r + \gamma PQ - \lambda\gamma PQ)\\
&= r+ (1-\lambda\gamma P)^{-1}(\lambda \gamma P r + (\mathcal T)Q - r - \lambda\gamma PQ)\\
&= (1-\lambda\gamma P)^{-1}(r - \lambda \gamma P r + \lambda \gamma P r + (\mathcal T)Q - r - \lambda\gamma PQ)\\
&= (1-\lambda\gamma P)^{-1}( (\mathcal T)Q  - \lambda\gamma PQ + Q - Q)\\
&= Q + (1-\lambda\gamma P)^{-1}( (\mathcal T)Q  - Q)
\end{align}

Add some properties about Markov chain: https://en.wikipedia.org/wiki/Markov_chain


text:
When calculating the cost in deep Q-learning, do we use both the input and target states?
I just finished Andrew Ngs's deep learning specialization, but RL was not covered, so I don't know the basics of RL. So, I have been having trouble understanding the cost function in deep Q-learning. Like other cost functions in machine learning, you usually have $\hat{y}$ (the network prediction) and $y$ (the target, or what the network is being optimized for.)
I've read through a few online articles on deep Q-learning. So far, there has been no mention of setting up a target state ($y$) for the agent to produce. There has been mention of calculating a temporal-difference, however, which is where I am confused.
When calculating the cost function, are you taking the input state ($\hat{y}$) and a target state ($y$) into consideration to determine the temporal-difference?
Otherwise, I'm not sure how the cost function could determine a reward based on the input alone (state of the environment the agent is in.).

I will first explain briefly to you the difference between supervised learning and reinforcement learning to make sure that you don't have any misunderstandings. In supervised learning you are provided with some data $\{(\textbf{x}_i, y_i)\}_{i=1}^n$ where $\textbf{x}_i$ are the features for data point $i$ and $y_i$ is its true label. Now, the aim of supervised learning is to learn a function $f$ that can accurately predict the label of a data point given its features. In deep learning this function is a neural network, $f_\theta(\cdot)$. To optimise the parameters we obtain the models prediction for the label of $y$, denoted typically by $\hat{y} = f_\theta(x)$ and we look to optimise the parameters of the function $\theta$ by minimising the loss $\mathcal{L}(\hat{y}, y)$ (note that here the loss is a function $\mathcal{L}: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}$.
In reinforcement learning things are quite different. We are not provided with any data. Instead we have a Markov Decision Process (MDP) and an environment that we can interact with. The state space is defined by the MDP and we can get samples, mainly tuples of the form $(s, a, r, s')$, that we can use to teach our agent how to find an optimal policy - typically an optimal policy is one that takes an action given the current state that will maximise the sum of the future rewards of the episode. So in reinforcement you can probably see that things are quite different to supervised learning, mainly in the way that we 'obtain' our data.
Of course these explanations are gross oversimplifications of the learning process in both paradigms and should only be used as a brief example to try to emphasise the different between the two learning paradigms.
Now, there are two ways you can parameterise your Q-function using a neural network:

The network takes as input the current state and outputs Q-values for each potential action; i.e. the output is a vector in $\mathbb{R}^{|\mathcal{A}|}$;
The network takes as input the state and action and outputs a real number which is the Q-value for the state, action tuple you pass as input to the network.

The second way is usually reserved for instances where you have a huge action space but only ever would consider a few feasible actions at each state - this saves computational complexity.
Now, to answer your question:
In case 1) you are assumed to have access to a transition tuple $(s, a, r, s')$. The temporal difference, which we will use as the target, is $\hat{y} = r + \max_a Q(s', a)$. Now, as our output of $Q(s', \cdot)$ is an $\mathbb{R}^{|\mathcal{A}|}$ what we do is make a forward pass of the network for the current $(s, a)$ tuple, i.e. we get $x = Q(s, a)$, and then change the element that corresponds to the action which satisfies $\arg\max_a Q(s', a)$ of $x$ to $\hat{y}$, so we have now got our augmented input $\tilde{x}$ which serves as our target.
To make that step a bit clearer, suppose we have a 2-dimensional action space and the $\arg\max_a Q(s', a)$ is the action in the first dimension, then we would change the first dimension of $x$ to be $\hat{y}$.
We then train the network using the Mean Squared Error Loss between $x$ and $\tilde{x}$ - note that no gradient information is retained when we do the forward pass to get $\tilde{x}$; in fact we usually don't use a current version of the $Q$ network, we use an 'old' version of the network called the target network (I imagine there's probably a question about this network on the site already so I won't explain it in detail).
In case 2) the idea is much more simple as the outputs of the network are scalars so you can just train your network using the MSE between the scalar values of $Q(s, a)$ and $\hat{y}$ as defined above, the caveat here is that to calculate $\arg\max_a Q(s', a)$ you have to make $|\mathcal{A}|$ forward passes of the network for all possible $(s', a)$, for fixed $s'$, tuples which is why method 1) is usually preferred.
Now, whilst we may use techniques from supervised learning to optimise the Q-function, you can hopefully see the differences between supervised and reinforcement learning.
In short, the temporal difference is the target that you train your network towards being able to predict, and the state is (typically) the input into your neural network. For a more in depth discussion of RL being framed as supervised learning please see this answer.

source: Stack Exchange

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

sort: votes


text:
How does replacing states with latent representations help RL agents?
I have seen many papers using autoencoders to replace images (states) with latent representations. Some of those methods have shown higher rewards using such techniques. However, I do not understand how this helps the RL agent learn better. Perhaps viewing latent representations allows the agent to generalize to novel states more quickly?
Here are 2 papers I have read -

Deep Spatial Autoencoders for Visuomotor Learning
DAQN: Deep Auto-encoder and Q-Network

In short, it is much easier for the agent to learn from a smaller dimensional state space. This is because the agent must also do representation learning; i.e. it must also infer what the state is telling it as part of the learning process. If you think of the architecture used in DQN to solve Atari, they had a CNN that outputted a vector which was then passed through some dense layers. Here the representation learning was done by the CNN and was trained using an end-to-end approach i.e. all updates to the network weights were done through the reinforcement learning objective; that is there is no supervised or unsupervised learning that takes place.
This can be particularly difficult when you combine images with sparse rewards as there is not a lot of feedback so the representation learning can take a long time. This paper gives a good description of the problem of decoupling representation learning from reinforcement learning with a nice solution.
The other main 'problem setting' I have seen images replaced with a latent state is when the authors are looking at planning. The problem with doing any kind of planning is that a model of the transition dynamics, $p(s' | s, a)$, is needed. For high dimensional state spaces such as images, this can be very difficult to predict and even relatively small errors will quickly compound so if you use the model to predict multiple time steps into the future the planner is useless because of these compounding errors. I think there is a discussion on this in this paper (certainly there will be references therein that point you in the right direction).

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


text:
What is the smoothness assumption in SVMs?
In this research paper, we have the following claim

the smoothness assumption that underlies many kernel methods such as Support Vector Machines (SVMs) does not hold for deep neural networks trained through backpropagation

Does smoothness here refer to no sharp rise/fall in gradients?

Smoothness here is the mathematical definition, so as you implied smoothness is ruled out by output data with sharp spikes or discontinuous jumps (and possibly the data of the gradient, the gradient's gradient, ad infinitum, depending on who defines smoothness).
By any definition a lot of activation functions are not smooth, for example RELU. This means neural networks in general are not smooth.


text:
Bounding Box Regression - An Adventure in Failure
I've solved many problems with neural networks, but rarely work with images.  I have about 18 hours into creating a bounding box regression network and it continues to utterly fail.  With some loss functions it will claim 80% accuracy during training and validation (with a truly massive loss on both) but testing the predictions reveals a bounding box that only moves one or two pixels in any given direction and seems to totally ignore the data.  I've now implemented a form of IoU loss, but find that IoU is pinned at zero... which is obviously true based on the outputs after training. :). I'd like someone to look this over and give me some advice on how to proceed next.
What I Have
I am generating 40000 examples of 200x100x3 images with a single letter randomly placed in each.  Simultaneously I am generating the ground truth bounding boxes for each training sample.  I have thoroughly validated that this all works and the data is correct.
What I Do To It
I am then transforming the 200x100x3 images down to greyscale to produce a 200x100x1 image.  The images are then normalized and the bounding boxes are scaled to fall between 0 and 1.  In simplified form, this happens:
x_train_normalized = (x_data - 127.5) / 127.5
y_train_scaled = boxes[:TRAIN]/[WIDTH,HEIGHT,WIDTH,HEIGHT]

I've been through this data carefully, even reconstituting images and bounding boxes from it.  This is definitely working.
Training
To train, after trying mse and many others, all of which fail equally badly, I have implemented a simple custom IOU loss function.  It actually returns -ln(IoU).  I made this change based on a paper since the loss was (oddly?) pinned at zero over multiple epochs.
(Loss function:)
import tensorflow.keras.backend as kb
def iou_loss(y_actual,y_pred):
    b1 = y_actual
    b2 = y_pred
#    tf.print(b1)
#    tf.print(b2)
    zero = tf.convert_to_tensor(0.0, b1.dtype)
    b1_ymin, b1_xmin, b1_ymax, b1_xmax = tf.unstack(b1, 4, axis=-1)
    b2_ymin, b2_xmin, b2_ymax, b2_xmax = tf.unstack(b2, 4, axis=-1)
    b1_width = tf.maximum(zero, b1_xmax - b1_xmin)
    b1_height = tf.maximum(zero, b1_ymax - b1_ymin)
    b2_width = tf.maximum(zero, b2_xmax - b2_xmin)
    b2_height = tf.maximum(zero, b2_ymax - b2_ymin)
    b1_area = b1_width * b1_height
    b2_area = b2_width * b2_height

    intersect_ymin = tf.maximum(b1_ymin, b2_ymin)
    intersect_xmin = tf.maximum(b1_xmin, b2_xmin)
    intersect_ymax = tf.minimum(b1_ymax, b2_ymax)
    intersect_xmax = tf.minimum(b1_xmax, b2_xmax)
    intersect_width = tf.maximum(zero, intersect_xmax - intersect_xmin)
    intersect_height = tf.maximum(zero, intersect_ymax - intersect_ymin)
    intersect_area = intersect_width * intersect_height

    union_area = b1_area + b2_area - intersect_area
    iou = -1 * tf.math.log(tf.math.divide_no_nan(intersect_area, union_area))
    return iou

The Network
This has been through many, many iterations.  As I said, I've solved many other problems with NNs... This is the first one to get me completely stuck.  At this point, the network is dramatically stripped down but continues to fail to train at all:
import tensorflow as tf
from tensorflow import keras
from tensorflow.keras import layers, optimizers

tf.keras.backend.set_floatx('float32') # Use Float32s for everything

input_shape = x_train_normalized.shape[-3:]
model = keras.Sequential()
model.add(layers.Conv2D(4, 16, activation = tf.keras.layers.LeakyReLU(alpha=0.2), input_shape=input_shape))
model.add(layers.MaxPooling2D(pool_size=(3, 3), strides=(2, 2)))
model.add(layers.Dropout(0.2))
model.add(layers.Flatten())
model.add(layers.Dense(200, activation = tf.keras.layers.LeakyReLU(alpha=0.2)))
model.add(layers.Dense(64, activation=tf.keras.layers.LeakyReLU(alpha=0.2)))
model.add(layers.Dense(4, activation="sigmoid"))

model.compile(loss = iou_loss, optimizer = "adadelta", metrics=['accuracy'])
history = model.fit(x_train_normalized, y_train_scaled, epochs=8, batch_size=100, validation_split=0.4)

All pointers are welcome!  In the meantime I'm implementing a center point loss function to see if that helps at all.

In the end, this problem turned out to be largely a matter of the gradient descent falling into local minima.
For those reading for posterity, one of the issues in ML that is difficult to work around is that we cannot intuitively choose reasonable initial values for the weights, biases, and kernels (in the CNN).  As a result, we typically allow them to initialize randomly.  This can present some challenges.
One of the biggest challenges is that when you start from a random starting point, it's difficult to tell someone how to completely replicate your experiments.  This isn't terribly important in the end since you can provide them with the saved parameters from your trained model.  However, this can also lead to networks that appear to be "bad" that are in fact perfectly fine.
In this case, I had spent much of the time initializing the CNN with a uniform initializer (not present in the code above).  I will sometimes use a random seed or some other function to generate initial values so that I can better improve networks through genetic search tools.
It seems that the uniform initializers combined with the various network iterations and this particular data lead to absolutely abysmal training performance and non-convergence.
When I ran the network as above with random initializations and one or two tweaks, it converged well.  Some training iterations will pin one of the sides of the bounding box at the edge, some will never converge, but I've managed to successfully train several that are in the 96-98% accuracy range for the bounding boxes in my test set of 20000, so all is well!

When you say "When I ran the network as above with random initializations and one or two tweaks", which specific initialization technique did you use in the end? Note that uniform initialization is also random. What tweaks did you use?

I had been using hm_uniform.  I simply allowed the default initialization to take place.  I need to plug this into one of my genetic search algorithms after finding a good seed that produces good results to better refine the model.


text:
How to train a policy model incrementally to solve a problem similar to the vehicle routing problem?
I have a problem similar to the vehicle routing problem (VRP) that I want to solve with reinforcement learning. In this problem, the agent starts from the point $(x_0, y_0)$, then it needs to travel through $N$ other points, $(x_1, y_1), \dots, (x_n, y_n)$. The goal is to minimize the distance traveled.
Right now, I am modeling a state as a point $(x, y)$. There are 8 possible actions: go east, go north-east, go north, go north-west, go-west, go south-west, go south, go south-east. Each action goes by a pace of 100 metres.
After reaching near a destination point, that destination point is removed from the list of destination points.
The reward is the reciprocal of total distance until all destination points reached (there's a short optimisation to arrange the remaining points for a better reward).
I'm using a DNN model to keep the policy of a reinforcement learning agent, so this DNN maps a certain state to suitable action.
However, after every action of the agent with a good reward, the training data are added with 1 more sample, it's kinda incremental learning.
Should the policy model be trained again and again with every new sample added in? This does take too much time.
Any better RL approach to the problem above?

Hello. Which RL algorithm are you using or planning to use to find the policy?

i may brute force, or i may do some greedy to find good rewards

Why don't you want to use some existing RL algorithm, such as Q-learning? Can you please describe more in detail your problem that you're trying to solve with RL (i.e. state space, action space and reward function)? Is this a toy problem that you came up with?

@nbro i've just added some details in the question

Thanks! Your post is way clearer now :) btw, you can use mathjax/latex on this site. As far as I recall, one good approach to the travelling salesman problem (something similar to what you're trying to do) are ant colony optimization algorithms. I don't know if RL is the best approach for this problem, but it can certainly be applied to this problem too.

@nbro i know RL isn't good for TSP, just trying out to see whether it's better than the supervised model

Ok, then I think you should clarify that you want to use RL (and not another approach), otherwise, people may think that you're also looking for other types of solutions given your question "Any better tactics for the problem above? ". Btw, ACO algorithms are not necessarily supervised. They are meta-heuristics, in the same way that genetic algorithms are also meta-heuristics.

do you have to use the action space that you have proposed? I have seen TSP solved using RL but the action space is usually just the cities (here it would be your points), i.e. which city to visit next.

the model is DNN, and there r thousands of destinations, and won't be able to classify to destination indices (city indices)

I found out a concept called 'Experience Replay', which trains a single step every time a new data sample is added instead of training to max epochs.
That is, instead of this training loop:
for i in range(max_paces):
    find action for max reward;
    add to trajectory to make inp;
    train(batch_size=len(inp), epochs=max_epochs)

Do training this way (for a single-episode ML problem, no incremental):
for i in range(max_epochs):
    reset environment;

    for j in range(max_paces):
        find action for max reward;
        add to trajectory to make inp;
        train(batch_size=len(inp), epochs=1)

Do training this way (for a multi-episode ML problem, incremental data):
for i in range(max_epochs):
    reset environment;
    inc_trajectory = get_random_past_data();

    for j in range(max_paces):
        find action for max reward;
        add to inc_trajectory to make inp;
        train(batch_size=len(inp), epochs=1)

For multiple-episode problems especially those problems with unlimited episodes, the training loop needs to forget (ie. exclude from training) old episodes which are very distant in the past, or select a random number of old episodes (consider them a batch, random batch) to be in every round of experience replay. Anyway, without eliminating some old data, the amount of training data are too much since it's unlimited number of episodes.


text:
What is the difference between Q-learning, Deep Q-learning and Deep Q-network?
Q-learning uses a table to store all state-action pairs. Q-learning is a model-free RL algorithm, so how could there be the one called Deep Q-learning, as deep means using DNN; or maybe the state-action table (Q-table) is still there but the DNN is only for input reception (e.g. turning images into vectors)?
Deep Q-network seems to be only the DNN part of the Deep Q-learning program, and Q-network seems the short for Deep Q-network.
Q-learning, Deep Q-learning, and Deep Q-network, what are the differences? May be there a comparison table between these 3 terms?

In Q-learning (and in general value based reinforcement learning) we are typically interested in learning a Q-function, $Q(s, a)$. This is defined as
$$Q(s, a) = \mathbb{E}_\pi\left[ G_t | S_t = s, A_t = a \right]\;.$$
For tabular Q-learning, where you have a finite state and action space you can maintain a table lookup that maintains your current estimate of the Q-value. Note that in practice even the spaces being finite might not be enough to not use function approximation, if e.g. your state space contains a large number, say $10^{10000}$, of states, then it might not be manageable to maintain a separate Q-function for each state-action pair
When you have an infinite state space (and/or action space) then it becomes impossible to use a table, and so you need to use function approximation to generalise across states. This is typically done using a deep neural network due to their expressive power -- aka, a deep Q-network (DQN). As a technical aside, the Q-networks don't usually take state and action as input, but take in a representation of the state (e.g. a $d$-dimensional vector, or an image) and output a real valued vector of size $|\mathcal{A}|$, where $\mathcal{A}$ is the action space.
Now, it seems in your question that you're confused as to why you use a model (the neural network) when Q-learning is, as you rightly say, model-free. The answer here is that when we talk about RL algorithms being model-free we are not talking about how the value-functions or policy are parameterised, we are actually talking about whether the algorithms use a model of the transition dynamics to help with their learning. That is, a model free algorithm doesn't use any knowledge about $p(s' | s, a)$ (other than implicitly through repeated interactions with the environment), whereas model-based methods look to use this transition function explicitly - it can be known exactly such as in Atari environments, or it can approximated/learnt - to perform planning with the dynamics, or generate artificial data to learn from, etc.

what is that q-network output vector? kinda softmax prob values of all actions?

no, just real valued numbers. If you look at the expectation, it is not a probability nor does it have any bounds, so the output of the network reflects this.

Here is a table that attempts to systematically show the differences between tabular Q-learning (TQL), deep Q-learning (DQL), and deep Q-network (DQN).

Tabular Q-learning (TQL)
Deep Q-learning (DQL)
Deep Q-network (DQN)

Is it an RL algorithm?
Yes
Yes
No (unless you use DQN to refer to DQL, which is done often!)

Does it use neural networks?
No. It uses a table.
Yes
No. DQN is the neural network.

Is it a model?
No
No
Yes (but usually not in the RL sense)

Can it deal with continuous state spaces?
No (unless you discretize them)
Yes
Yes (in the sense that it can get real-valued inputs for the states)

Can it deal with continuous action spaces?
Yes (but maybe not a good idea)
Yes (but maybe not a good idea)
Yes (but only the sense that it can produce real-valued outputs for actions).

Does it converge?
Yes
Not necessarily
Not necessarily

Is it an online learning algorithm?
Yes
No, if you use experience replay
No, but it can be used in an online learning setting

Note that, when I say that neural networks are not online learning algorithms, I'm viewing neural networks as models and not algorithms. However, given that a specific neural network (with specific weights) computes some function and functions are algorithms (see lambda calculus), they could also be considered algorithms. In most cases, the best way to think of a neural network is as a model (i.e. something that you can use to approximate the desired function), but, sometimes, it's also useful to think of a neural network as a function.

Q-learning
Q-learning is a basic reinforcement learning algorithm. It uses a Q-table to store and update the value of each state-action pair. The algorithm updates the Q-values using the Bellman equation based on the reward received and the estimated value of the next state. It's model-free, meaning it doesn't require a model of the environment and learns from interactions.
Deep Q-learning
Deep Q-learning is an extension of Q-learning that uses a deep neural network (DNN) instead of a Q-table. The Q-table becomes impractical in environments with large or continuous state spaces because it would need to store a Q-value for every possible state-action pair. Deep Q-learning uses a DNN to approximate the Q-values, allowing it to handle more complex environments.
Deep Q-network (DQN)
Deep Q-network (DQN) refers to the specific neural network architecture used in Deep Q-learning to approximate the Q-values. The DQN receives the state (often processed by convolutional layers in the case of image inputs) and outputs Q-values for all possible actions in that state.


text:
Are Genetic Algorithms suitable for problems like the Knuth problem?
We all know that Genetic Algorithms can give an optimal or near-optimal solution. So, in some problems like NP-hard ones, with a trade-off between time and optimal solution the near-optimal solution is good enough.
Since there is no guarantee to find the optimal solution, is GA considered to be a good choice for solving the Knuth problem?
According to Artificial intelligence: A modern approach (third edition), section 3.2 (p. 73):

Knuth conjectured that, starting with the number 4, a sequence of
factorial, square root, and floor operations will reach any desired
positive integer.

For example, 5 can be reached from 4:

floor(sqrt(sqrt(sqrt(sqrt(sqrt((4!)!))))))

So, if we have a number (5) and we want to know the sequence of the operations of the 3 mentioned ones to reach the given number, each gene of the chromosome will be a number that represents a certain operation with an additional number for (no operation) and the fitness function will be the absolute difference between the given number and the number we get from applying the operations in a certain order for each the chromosome (to min). Let's consider that the number of the iterations (generations) is done with no optimal solution and the nearest number we have is 4 ( with fitness 1), the problem is that we can get 4 from applying no operation on 4 while for 5 we need many operations, so the near-optimal solution is not even near to the solution.
So, is GA is not suitable for this kind of problems? Or the suggested chromosome representation and fitness function are not good enough?

Before trying to answer your question more directly, let me clarify something.
People often use the term genetic algorithms (GAs), but, in many cases, what they really mean is evolutionary algorithms (EAs), which is a collection of population-based (i.e. multiple solutions are maintained at the same time) optimization algorithms and approaches that are inspired by Darwinism and survival of the fittest. GAs is one of these approaches, where the chromosomes are binary and you have both the mutation and cross-over operation. There are other approaches, such as evolution strategies or genetic programming.
As you also noticed, EAs are meta-heuristics, and, although there is some research on their convergence properties [1], in practice, they may not converge. However, when any other potential approach has failed, EAs can be definitely useful.
In your case, the problem is really to find a closed-form (or analytical) expression of a function, which is composed of other smaller functions. This really is what genetic programming (in particular, tree-based GP) was created for. In fact, the Knuth problem is a particular instance of the symbolic regression problem, which is a typical problem that GP is applied to. So, GP is probably the first approach you should try.
Meanwhile, I have implemented a simple program in DEAP that tries to solve the Knuth problem. Check it here. The fitness of the best solution that it has found so far (with some seed) is 4 and the solution is floor(sqrt(float(sqrt(4)))) (here float just converts the input to a floating-point number, to ensure type safety).  I used the difference as the fitness function and ran the GP algorithm for 100 generations with 100 individuals for each generation (which is not a lot!). I didn't tweak much the hyper-parameters, so, maybe, with the right seed and hyper-parameters, you can find the right solution.
To address your concerns, in principle, you could use that encoding, but, as you note, the GA could indeed return $4$ as the best solution (which isn't actually that far away from $5$), which you could avoid my killing, at every generation, any individuals that have just that value.
I didn't spend too much time on my implementation and thinking about this problem, but, as I said above, even with genetic programming and using only Knuth's operations, it could get stuck in local optima. You could try to augment my (or your) implementation with other operations, such as the multiplication and addition, and see if something improves.

Thank you very much, I checked the code so thank you again, so in summary it is better to use other approach (not GA) to solve this problem

@yaminoyuki I'm not sure which other approach would work better than GA or GP for this problem. So, I think that GP is probably your best bet, if you want to find a reasonable solution, but you have to tweak my implementation.


text:
What do the variables in the cross-correlation formula mean?
I understand what cross-correlation does given a kernel and an input image, but the formula confuses me a little. Given here in Goodfellow's Deep Learning (page 329), I can't quite understand what $m$ and $n$ are. Are they the dimensions of the kernel along the height and width dimensions?
$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n)$$
So, for the input image $I$ and kernel $K$, we take the sum product of $I*K$, but what do the $m$ and $n$ represent? How is the input image $I$ indexed?

It takes a little bit of time to fully understand the 2D convolution/cross-correlation and to relate it to the usual diagrams of the convolution operation, so, before addressing your questions, let me first try to break the definition of the 2D cross-correlation down, from the left to right.
$$S(i,j) =(K*I)(i,j) = \sum_m \sum_n I(i+m, j+n)K(m,n) \label{1}\tag{1}$$

$S$ is the function that is the cross-correlation of the functions $K$ and $I$, so $S(i, j)$ is the cross-correlation of $K$ and $I$ at the pixels $i$ and $j$

The symbol $*$ in $K*I$ is the cross-correlation/convolution symbol, but sometimes the cross-correlation/convolution is also denoted as $\circledast$

$K*I$ is the function that results from the cross-correlation of $K$ and $I$, i.e. $S$, so $(K*I)(i,j)$ is the value of the function $S$ (the cross-correlation of $K$ and $I$) at the inputs (or pixels) $i$ and $j$. In other words, $(K*I)(i,j)$ is just another way of writing $S(i,j)$ that emphasizes that we took the cross-correlation of $K$ and $I$, but they are exactly the same thing.

The double summation $\sum_m \sum_n$ is because we are computing the 2D cross-correlation, i.e. over the $x$ and $y$ dimensions of the image and kernel. This is just the definition of the 2D cross-correlation.

The $m$ and $n$ are the indices of the summations, one across the $x$-axis and the other across the $y$-axis. Let $m = x$ and $n = y$, so we can rewrite equation \ref{1} as follows.
$$S(i, j) =(K*I)(i, j) = \sum_x \sum_y I(i + x, j + y)K(x, y) \label{2}\tag{2}$$
Now, it should be clearer that we are indexing across the $x$ and $y$ dimensions.

Now, let me further restrict the range of the summations. Let's say from $x=-1$ to $x=1$ and from $y=-1$ to $y=1$, then we can rewrite equation \ref{2} as follows
$$S(i, j) =(K*I)(i, j) = \sum_{x=-1}^1 \sum_{y=-1}^1 I(i + x, j + y)K(x, y) \label{3}\tag{3}$$.

Why do I want to do this? Let me explain why. Consider now the following kernel $K$ (which happens to be a Gaussian kernel)
$$
K = \begin{bmatrix}\ \ \color{blue}{\frac {1}{16}} &\ \ \frac {1}{8} &\ \ \frac {1}{16} \\\ \ \frac {1}{8} &\ \ \frac {1}{4} &\ \ \color{red}{ \frac {1}{8}} \\\ \ \frac {1}{16} &\ \ \frac {1}{8} &\ \ \frac {1}{16}\end{bmatrix}
$$
Note that this is the output of the function $K$ or, more precisely, its support. Let's assume that $\frac {1}{4}$ is at the index/pixel $(0, 0)$. Then, for example, the top-left $ \color{blue}{\frac {1}{16}} $ is at index/pixel $(-1, -1)$ and the middle-right $\color{red}{ \frac {1}{8}}$ at pixel $(1, 0)$

Now, consider any image $I$ represented as a 2D matrix (i.e. its support), with, for example, dimensions $U \times V$. For concreteness, let $U = 5$ and $V=5$. Moreover, the middle pixel of the image is at index $(0, 0)$, as for the kernel. Let's say the image is the following
$$
I =
\begin{bmatrix}
0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 & 1 \\
0 & 0 & \color{green}{0} & 1 & 1 \\
1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 \\
\end{bmatrix}
$$
So, $\color{green}{0}$ is at index/pixel $(0,0)$.

Now, let's say that $i = 0$ and $j=0$ in equation \ref{3}. This means that we compute the cross-correlation between $I$ and $K$ at the index $(0, 0)$, where, in the case of the image $I$, the value is $\color{green}{0}$.

With these settings, it should be clearer now that equation \ref{3} means that the cross-correlation between $K$ and $I$ at index/pixel $i=0$ and $j=0$ is a 2D dot (or scalar) product. If it is not clear, then let be take the $3\times 3$ submatrix of $I$ centered at $(i, j) = (0, 0)$ (below, $(0, 0)^{3 \times 3}$ is just the notation that I came up with to indicate that).
$$
I_{(0, 0)^{3 \times 3}} =
\begin{bmatrix}
1 & 0 & 1 \\
0 & \color{green}{0} & 1  \\
1 & 0 & 0
\end{bmatrix}
$$
Then the cross-correlation in equation \ref{3} is just
$$
S(i, j) = S(0, 0) = (K * I)(0, 0) =
\sum
\begin{bmatrix}
1 \frac {1}{16} & 0 \frac {1}{8} & 1 \frac {1}{16} \\
0 \frac {1}{8} & \color{green}{0} \frac {1}{4}  & 1 \frac {1}{8}  \\
1 \frac {1}{16} & 0 \frac {1}{8} & 0 \frac {1}{16}
\end{bmatrix},
$$
where $\sum$ is a sum across all elements, i.e.
\begin{align}
S(0, 0)
&= 1 \frac {1}{16} + 0 \frac {1}{8} + 1 \frac {1}{16} +
 0 \frac {1}{8} + \color{green}{0} \frac {1}{4} + 1 \frac {1}{8} +
1 \frac {1}{16} + 0 \frac {1}{8} + 0 \frac {1}{16}  \\
& = \frac {1}{16} + \frac {1}{16} + \frac {1}{8} + \frac {1}{16} \\
& = \frac {3}{16} + \frac {1}{8} \\
&= \frac {5}{16}
\end{align}

Now, to answer your questions/concerns more directly.

Are they the dimensions of the kernel along the height and width dimensions?

No. They are the indices that determine the neighbourhood around $i$ and $j$ where you want to compute the cross-correlation.

So, for the input image $I$ and kernel $K$, we take the sum product of $I*K$

In this case, the symbol $*$ does not denote the product, but the cross-correlation. Maybe by "sum product" you meant the cross-correlation (or 2D dot product), but I'm not sure.

How is the input image $I$ indexed?

The input image is indexed with $m$ and $n$, but you start at $i$ and $j$, that's why you use the actual indices $i+m$ and $j+n$.


text:
Is the working of RNNs, LSTM and GRU sequential or parallel?
You take any blog or any example and all they tell you about is the given picture below.

It has 4 different matrices and 3 of whose weights are shared. So, I'm wondering how is this achieved in practice?
Please correct me:
I think the first word "hello" goes in as a one-hot encoded form and changes the Hidden matrix. And then after it, "world" goes and gets multiplied and then changes the matrix again and so on. What people make it look like is that all of the words going are in Parallel. It can't be the case because the Hidden matrix is dependent on the previous word and without changing the matric, you can not pass the current word. Please correct if my idea is wrong but I think the execution is in sequential order.

Yes, you are correct and it was one of original motivations, which inspired the invention of the Attention mechanism in seq2seq problems https://arxiv.org/pdf/1706.03762.pdf.
There is a quote from this paper:

Recurrent models typically factor computation along the symbol
positions of the input and output sequences. Aligning the positions to
steps in computation time, they generate a sequence of hidden states $h_t$,
as a function of the previous hidden state $h_{t−1}$ and the input for
position $t$. This inherently sequential nature precludes parallelization
within training examples, which becomes critical at longer sequence
lengths, as memory constraints limit batching across examples.

On the other hand, Transformer architectures have a loot loom for parallelization, because they take the whole sequence at once, and multiple heads can be executed in parallel.

Thanks man! And one more thing, apart from the H (Hiddne State MAtrix) here, everything else is shared. WhX, WhY, F are all shared. Right?

And also, All of these 4 matrices have the same dimensionality which we define by (Number of Neurons) right?

WhX, WhY, F are shared. In fact you have only one cell - only the inputs x_t and h_t change. However, I would not call F a matrix - it is usually an activation function. About the dimensinality - no, in general setting. The dimension of the output y_t doesn't need to be equal to x_t or h_t. And x_t and h_t can have different dimensionality as well. This WhX and WhY are of different size.

So how can you decide the size of WhX and WhY? Also, if F is an activation function, then there are only 3 matrices not 4 right? But I thought there are 4 matrices one of which has all 0s in starting and is responsible for the state change? Right? See this link 4 matrices and 2 biases.

In your link I see only 3 matrices. There is a matrix Wxh which mutliplies the input and is added to form the hidde state, matrix Whh from hidden state to hidden state, and the matrix Why from hidden state to output y. x, h, y can be of different dimensionality. Thus, Wxh is a dim_x * dim_h matrix, Whh is a dim_h * dim_h and so on.

Actually I was taking the Hidden Vector as a matrix too. Thats why I got confused. Thanks anyways for helping so long.


text:
What is the difference between out of distribution detection and anomaly detection?
I'm currently reading the paper Likelihood Ratios for Out-of-Distribution Detection, and it seems that their problem is very similar to the problem of anomaly detection. More precisely, given a neural network trained on a dataset consisting of classes $A,B,$ and $C$, then they can detect if an input to the neural network is anomalous if it is different than these three classes. What is the difference between what they are doing and regular anomaly detection?

You observation is correct although the terminology needs a little explaining.
The term 'out-of-distribution' (OOD) data refers to data that was collected at a different time, and possibly under different conditions or in a different environment, then the data collected to create the model.  They may say that this data is from a 'different distribution'.
Data that is in-distribution can be called novelty data.  Novelty detection is when you have new data (i.e. OOD) and you want to know whether or not it is in-distribution.  You want to know if it looks like the data you trained on.
Anomaly detection is when you test your data to see if it is different than what you trained the model.  Out-of-distribution detection is essentially running your model on OOD data.  So one takes OOD data and does novelty detection or anomaly detection (aka outlier detection).
Below is a figure from What is anomaly detection?

In time series modeling, the term 'out-of-distribution' data is analogous to 'out-of-sample' data and 'in-distribution' data is analogous with 'in-sample' data.

Thanks for the answer. What do you mean by "Out-of-distribution detection is essentially running your model on OOD data." and "So one takes OOD data and does novelty detection or anomaly detection (aka outlier detection)."?

I updated the answer with a figure which might help although it could be better written.  The data on the left is what was used to train the model.  The data on the right, for single and multi-class, are OOD.


text:
What are support values in a support vector machine?
I started reading up on SVM and very little is defined of what are support values. I reckon it's they are denoted as $\alpha$ in most formulations.

In the least-squares SVM (LS-SVM) the non-zero Lagrange multipliers ($\alpha$) are the support values.  The corresponding data points are the support vectors.  Johan Suykens explains this in Least Squares Support Vector Machines.


text:
How should I generate datasets for a SARSA agent when the environment is not simple?
I am currently working on my master's thesis and going to apply Deep-SARSA as my DRL algorithm. The problem is that there is no datasets available and I guess that I should generate them somehow. Datasets generation seems a common feature in this specific subject as stated in [1]

When a dataset is not available, learning is performed through experience.

I am wondering how to generate datasets when the environment is not as simple as a tic-tac-toe or a maze problem and what the experience means.
PS: The environment consists of 15 mobile users and 3 edge servers, each of which covers a number of mobile users. Each mobile user might generate a computationally heavy-load task and at the beginning of each timestep and can process the task itself or requests its associated edge server to do the processing. If the associated edge server is not capable of processing, due to some reasons, it requests a nearby edge server to lend it a hand. The optimization problem (reward) is to reduce time and energy consumption (multi-objective optimization). Each server has a DRL agent that makes offloading decisions.
I'd really appreciate your suggestions and help.

I am wondering how to generate datasets when the environment is not as simple as a tic-tac-toe or a maze problem

There is no difference in concept, which is why tic-tac-toe and maze problems are used to teach.
As you have noted, the main difference between reinforcement learning (RL) and supervised learning is that RL does not use labeled datasets. If you are using SARSA then you would not expect to use any record of previous experience either because SARSA is designed to work on-policy and online - which means that data needs to be generated during training. Training data for SARSA is typically stored only temporarily before being used, or is used immediately (you might keep a log of it for analysis or to help document your thesis, but that log will not be used for further training by the agent). This is different to Q-learning and DQN, which could in theory make use of longer-term stored experience.
You have two main choices for acquiring data:

Use a real environment. In your case, set up 15 mobile users and 3 edge servers. Instrument the environment to collect state and reward data for the agent. Implement the agent as the real decision maker in this environment.

Simulate the environment. Write a simulation that models user behaviour and server loading. Instrument that to provide state and reward data, and integrate your learning agent with it. Typically the agent will call the environment's step function, passing the action choice as an argument and receiving reward and state data back.

If you can simulate the environment, this is likely to be preferable to you since you will likely use less compute resources (than 3 servers and 15 mobile phones) and can run the training faster than real time. Deep reinforcement learning can use a large amount of experience to converge on near-optimal policies, and fast simulations can help because they generate experience faster than reality.
You can also do both approaches. Train an initial agent in simulation, then implement the real version once it reaches a good level of performance in simulation. You can even have the agent continue to learn and refine behaviour in production. Given that you are working with SARSA, this may be an important part of the intent of your project, that the agent continues to adapt to changes in user behaviour and server load over time. In fact this is a key advantage of SARSA over Q-learning, that it should be more reliable and safe to use in such a continuous learning scenario deployed to production.

and what the experience means.

The experience in reinforcement learning is the record of states, actions and rewards that the agent encounters during training.

It's not fully clear to me this part "You have two main choices for collecting data ...": so are you suggesting to "collect data" in the sense that the OP should really store a dataset first and then replay that dataset to perform SARSA somehow offline? Or are you suggesting to "collect data", but you're actually referring to where SARSA can be trained (i.e. gain experience)? It seems more the second, but the suggestion would be applicable to both cases, anyway.

@nbro: "Collecting data" is not meant to imply a dataset or offline training. I think I make clear the lack of labelling and duration of useful storage in the previous paragraph. However, there is still data involved in the proceess and it has to be acquired somehow. "Collect" also has the meaning of "fetch" (as in "I collected the kids from school"). I have changed to more neutral "acquire", but open to suggestions


text:
In OCR, how should I deal with the warped text on the sides of oval objects?
Consider an image that contains one can (or bottle, or any similar oval object), which has texts all over it. In the image below, I have many bottles, but you can assume that each image only contains one such object.

As we can see, in each can, the text can flow from left to right, and any OCR system may miss the text on the left and right sides of the can, as they are not aligned with the camera angle.
So, is there any solution/s for this, like preprocessing in a certain way, so that we can read the text or make this round object into a straight one? (If there is any Python program that can solve this problem, could you please share it with me?)

Comments are not for extended discussion; this conversation has been moved to chat.

There are many papers on this but the following is a good start:

How to unwrap wine labels programmatically.  The author includes source code in Python.

You mentioned you do not want to do a panoramic view but that has more than one meaning.  If I assume you mean you do not want to rotate the can while taking multiple photos, or you don't want to take multiple photos from different angles, you could try a pericentric lens.  This would require some image processing to do the unwrapping.  More resolution is needed as the wrapping is much more severe.  The advantage though is that you will have a single image of the full cylindrical surface and won't miss any features or text.


text:
Have I understood the loss function from the original U-Net paper correctly?
In the original U-Net paper, it is written

The energy function is computed by a pixel-wise soft-max over the final
feature map combined with the cross entropy loss function.
...
$$
E=\sum_{\mathbf{x} \in \Omega} w(\mathbf{x}) \log \left(p_{\ell(\mathbf{x})}(\mathbf{x})\right) \tag{1}\label{1}
$$

where $w(\mathbf{x})$ is a weight map (I'm not interested in that part right now), and $p_{k}(\mathbf{x})$ is
$$
p_{k}(\mathbf{x})=\exp \left(a_{k}(\mathbf{x})\right) /\left(\sum_{k^{\prime}=1}^{K} \exp \left(a_{k^{\prime}}(\mathbf{x})\right)\right)
$$
The pixel-wise softmax with $a_{k}(\mathbf{x})$ being the activation in feature channel $k$ at pixel position $\mathbf{x}$ and $K$ the number of classes. Then $\ell(\mathbf{x})$ from $p_{\ell(\mathbf{x})}$ is the true label of each pixel, i.e. if the pixel at position $\mathbf{x}$ is part of class $1$, then $p_{\ell(\mathbf{x})}$ is equal to $p_1(\mathbf{x})$.
As far as is understand $-E$ should be the cross-entropy function. Right? I've already done the math for the binary case (ignoring $w(\mathbf{x})$) and it seemed to be equal.

Yes, $E$ is the cross-entropy function and a direct generalization of the binary case.
For the binary case, probability to belong to the class $1$ is given by a sigmoid function $\sigma(x)$ of the output $x$, and the probability to belong to the class $0$ is $1 - \sigma(x)$.
Therefore the binary crossentropy will give:
$$
-\sum_i (l_i \log \sigma(x) + (1 - l_i)  \log (1 - \sigma(x))
$$
Where the sum is over all samples in the dataset. Because $l_i$ is a binary variable one of these two terms would be zero. The gradient descent forces the model to predict true label with more confidence.
For the multiclass case, now the output is a $K$-vector and the softmax function forces its elements to sum to one:
$$
\sum_{i = 1}^{K} p_i = 0
$$
The true label is one-hot encoded vector, with $1$ on the position of the true label, and $0$ elsewhere. The generalization of the binary case is:
$$
-\sum_i \sum_{j = 1}^{K}(l_{ij} \log \sigma_j(x) + (1 - l_{ij})  \log (1 - \sigma_j(x))
$$
In this case, there will be $K$ non-vanishing contributions.The minization of $E$ forces the classifier to predict the true label more confidently, and all other (to make $\log(1 - \sigma_j(x))$) as small  as possible.


text:
When updating the state-action value in the Monte Carlo method, is the return the same for each state-action pair?
Referring to this post, in the following formula to update the state-action value
$$ Q(s,a) = Q(s,a) + \alpha (G − Q(s,a)),$$
is the value of $G$ (the return) the same for every state-action $(s,a)$ pair?
I am a little confused about this point, so I will thank any clarification.

The discussion uses poor notation, there should be a time index. You obtain a list of tuples $(s_t, a_t, r_t, s_{t+1})$ and then, for every visit MC, you update
$$Q(s_t, a_t) = Q(s_t, a_t) + \alpha (G_t - Q(s_t, a_t))\;;$$
where $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$, for each $t$ in the episode. You can see that the returns for each time step are calculated for time timestep onwards, and so are not necessarily the same across time steps.

Thank you @DavidlIreland. So, in the case that there is only one reward at the final step as in chess, will every state-action pair, sampled in this episode, have the same return? Or generally, in the case that there are succesive actions with no rewards, will they share the return value in order to update themselves?

They would be the same if the discount factor used is 1, if not then they will still be different.


text:
Why is the derivative of the softmax layer shaped differently than the derivative of other neurons?
If the derivative is supposed to give the rate of change of a function at that point, then why is the derivative of the softmax layer (a vector) the Jacobian matrix, which has a different shape than the output/softmax vector? Why is the shape of the softmax vector's derivative (the Jacobian) different than the shape of the derivative of the other activation functions, such as the ReLU and sigmoid?

This blog post could also be useful.

When you use the softmax activation function is usually as a last layer of your network and to get an output that is a vector. Now your confusion is about shapes, so let's review a bit of calculus.
If you have a function $$f:\mathbb{R}\rightarrow\mathbb{R}$$
the derivative is a function on its own and you have $$f':\mathbb{R}\rightarrow\mathbb{R}.$$
If you increase the dimension of the input space have
$$f:\mathbb{R}^n\rightarrow\mathbb{R}.$$
The "derivative" in this case is called gradient and it is a vector collecting the $n$ partial derivatives of $f$. The input space of the gradient function is $\mathbb{R}^n$ (the same as for $f$), but the output is the collection of the $n$ derivatives, so the output space is also $\mathbb{R}^n$. In other words
$$\nabla f:\mathbb{R}^n\rightarrow\mathbb{R}^n,$$
which makes sense as for each point $x$ of the input space you get a vector ($\nabla f(x)$) as output.
So far so good, but what happens if you consider a function that takes a vector as input and spits out a vector as output, i.e.
$$f:\mathbb{R}^n\rightarrow\mathbb{R}^m?$$
How to compute the equivalent of the derivative? (This is the softmax case, where you have a vector as input and a vector as output.)
You can reduce this case to the previous case considering $f=(f_1, \dots, f_m)$, where $f_i:\mathbb{R}^n\rightarrow\mathbb{R}.$ Now for each $f_i$ you can compute the gradient $\nabla f_i$ and end up with $m$ gradients. When you evaluate them at a point $x\in\mathbb{R}^n$ you get $m$ $n-$dimensional vectors. These vector can be collected in a matrix, which is the Jacobian; formally
$$Jf:\mathbb{R}^n\rightarrow\mathbb{R}^{m\times n}.$$
Finally, to answer your question, you get a Jacobian "instead"  of a gradient (they all represent the same concept) because the output of the softmax is not a single number but a vector.
By the way the sigmoid and relu are functions with one dimensional input and output, so they don't really have a gradient but a derivative. The trick is that people write $\sigma(W)$, where $W$ is vector or a matrix, but they mean that $\sigma$ is applied component-wise, as a function from $\mathbb{R}$ to $\mathbb{R}$ (I know, it's confusing).
(I know, I kind of skipped your other question, but this answer was already long and I think you can convince yourself that the dimensions match correctly (with the Jacobian) for the update rule to work. If not I'll edit)

Comments are not for extended discussion; this conversation has been moved to chat.


text:
Does it make sense to include constant states into reinforcement learning formulation?
Does it make sense to incorporate constant states in the Markov Decision Process and employ a reinforcement learning algorithm to solve it?
For instance, for applications of personalization, I would like to include users' attributes, like age and gender, as states, along with other changing states. Does it make sense to do so? I have a sequential problem, so I assume the contextual bandit does not fit here.

It is, I suppose, a philosophical question whether data that describes a whole episode and does not respond to events within it is part of the state, or is part of some other structure.
However, the practical response is to view such descriptive data as defining an instance of a class of related environments, and to include it in the state features. This may be done for two main reasons:

The static data is a relevant parameter of the environment, affecting state transitions and rewards.

It is possible to generalise over the population of all values that the parameters can take.

In simple environments, generalisation might only be that the same agent can learn about all variations in a single combined training session. You could use a tabular RL method, starting randomly with one of the possible variations until all were sufficiently covered.
In more complex environments, generalisation may also occur through functon approximation, in a similar manner to contextual bandits. In your personalisation example, you are not expecting to train the agent for all possible user descriptions, but hope that people with similar age, gender etc descriptions will respond similarly to an agent that personalises content.
Philosophically, the contextual data is either part of a larger state space (with a restriction that transitions between different contexts do not happen within an episode), or it is metadata that impacts the "real" state transitions and rewards. Pragmatically, to allow the data to influence value functions and policies, it is necessary to use it in the arguments of those functions. Whether you then view it as part of the state feature vector or as something that is concatenated to state features is a personal choice. Most of the literature I have seen assumes without comment that it is part of the state.


text:
What is the derivative of a specific output with respect to a specific weight?
If I have a neural network, and say the 6th output node of the neural network is:
$$x_6 = w_{16}y_1 + w_{26}y_2 + w_{36}y_3$$
What does that make the derivative of:
$$\frac{\partial x_6}{\partial w_{26}}$$
I guess that it's how is $x_6$ changing with respect to $w_{26}$, so, therefore, is it equal to $y_2$ (since the output, $y_2$, will change depending on the weight added to the input)?

Formally speaking $x_6$ is a function of $w_{16},\ w_{26}$ and $w_{36}$, that is $$x_6 =f(w_{16}, w_{26}, w_{36})=w_{16}y_1 + w_{26}y_2 + w_{36}y_3.$$
The derivative w.r.t. $w_{26}$ is
$$\frac{\partial x_6}{\partial w_{26}}= \frac{\partial w_{16}y_1}{\partial w_{26}} +\frac{\partial w_{26}y_2}{\partial w_{26}}  +\frac{\partial w_{36}y_3}{\partial w_{26}} = 0 +y_2 \frac{\partial w_{26}}{\partial w_{26}} + 0= y_2.$$
The first equality is obtained using the fact that the partial derivative is linear (so the derivative of the sum is the sum of the derivatives); the second equality comes from again from the linearity and from the fact that $w_{16}y_1$ and $w_{36}y_3$ are constants with respect to $w_{26}$, so their partial derivative w.r.t. this variable is $0$.
Bonus
Not really asked in the original question, but since I'm here let me have a bit of fun ;).
Let's say $x_6$ is the output of the sixth node after you apply an activation function, that is $$x_6 =\sigma(f(w_{16}, w_{26}, w_{36}))=\sigma(w_{16}y_1 + w_{26}y_2 + w_{36}y_3).$$
You can compute the partial derivative applying the properties illustrated above, with the additional help of the chain rule
$$\frac{\partial x_6}{\partial w_{26}}=\frac{\partial \sigma(w_{16}y_1 + w_{26}y_2 + w_{36}y_3)}{\partial w_{26}}=\sigma'\frac{\partial w_{16}y_1}{\partial w_{26}} +\sigma'\frac{\partial w_{26}y_2}{\partial w_{26}}  +\sigma'\frac{\partial w_{36}y_3}{\partial w_{26}}=y_2\sigma'$$
$\sigma'$ denotes the derivative of sigma with respect to its argument.


text:
Training a classifier on different datasets with different image conditions for different labels causes the model to infer using the background
I have an interesting problem related to training the model on two different datasets for the target feature on images taken on different conditions, which might affect the model's ability to generalize.
To explain I will give examples of images from the two different datasets.
Dataset 1 sample image:

Dataset 2 sample image:

As you see the images are captured in two completely different conditions. I am afraid that the model will infer from the background information that it shouldn't use to predict the plant diseases, what makes the problem worse is that some plant diseases only exist in one dataset and not the other, if all the diseases are contained in both datasets then I wouldn't think there would be a problem.
I am assuming I need a way to unify the background by somehow detecting the leaf pixels in the images and unifying the background in a way that makes the model focuses on the important features.
I've tried some segmentation methods but the methods I tried don't always give desirable results for all the images.
What is the recommended approach here? All help is appreciated
Further explanation of the problem.
Ok so I will explain one more thing, my model on the two datasets works fine when training and validating, It got a 94% accuracy.
The problem is, even though the model performs well on the datasets I have, I am afraid that when I use the model on real-life conditions (say someone capturing an image with their phone) the model will be heavily biased towards predicting labels in the second dataset (the one with actual background) since the background is similar and it somehow associated the background with the inference process.
I have tried downloading a leaf image of a label that is contained on the first dataset ( the one with the white background), where the image had a real-life background, the model as expected failed to predict the correct label and predicted a label contained in the second dataset, I am assuming it was due to the background. I have tried this experiment multiple times, and the model consistently failed in similar scenarios
I used some Interpretability techniques as well to visualize the important pixels and it seems like the model is using the background for inference, but I am not an expert in interpreting these graphs so I am not 100% sure.

I am afraid that the model will infer from the background information that it shouldn't use to predict the plant diseases, what makes the problem worse is that some plant diseases only exist in one dataset and not the other

I am afraid that when I use the model on real-life conditions (say someone capturing an image with their phone) the model will be heavily biased towards predicting labels in the second dataset (the one with actual background) since the background is similar and it somehow associated the background with the inference process.

You are right to be concerned about this. However, you are not alone in having a neural network model that relies heavily on the background or other confounding factors for your classification task.
A small paper that addresses a similar issue is Context Augmentation for Convolutional Neural Networks. Table 1 from this paper shows how the model trained and tested on only the background performs better than model trained and tested on only the foreground. They address this by making a training set where the foreground objects are given many backgrounds. Given your imbalanced datasets, with some diseases only present in one dataset and not the other, I think context augmentation might work for you. The main barrier here is that you do not have segmentation maps for these. Are your datasets too large to segment yourself? You might consider automatic segmentation networks - especially for the images with white backgrounds.
As for your interpretability methods, you should not expect too much from them though some groups are able to get good results with them using GradCAM.
Here is an alternative idea that may also solve your problem: If you are trying to make a system that can be used in the field, is it possible to have the technician or photographer put a white board under the diseased leaf?


text:
Where is the mistake in my derivation of the GAN loss function?
I was pondering on the loss function of GAN, and the following thing turned out
\begin{aligned}
 L(D, G)
& = \mathbb{E}_{x \sim p_{r}(x)} [\log D(x)] + \mathbb{E}_{x \sim p_g(x)} [\log(1 - D(x)] \\
& = \int_x \bigg( p_{r}(x) \log(D(x)) + p_g (x) \log(1 - D(x)) \bigg) dx \\
& =-\left[CE(p_r(x), D(x))+CE(p_g(x), 1-D(x)) \right] \\
\end{aligned}
Where CE stands for cross-entropy. Then, by using law of large numbers:
\begin{aligned}
L(D, G)
& = \mathbb{E}_{x \sim p_{r}(x)} [\log D(x)] + \mathbb{E}_{x \sim p_g(x)} [\log(1 - D(x)] \\
& =\lim_{m\to \infty}\frac{1}{m}\sum_{i=1}^{m}\left[1\cdot \log(D(x^{(i)}))+1\cdot \log(1-D(x^{(i)}))\right]\\
& =- \lim_{m \to \infty} \frac{1}{m}\sum_{i=1}^{m} \left[CE(1, D(x))+CE(0, D(x))\right]
\end{aligned}
As you can see, I got a very strange result. This should be wrong intuitively because in the last equation first part is for real samples, and the second is for generated samples. However, I am curious about where are the mistakes?
(Please explain with math).

I guess the issue is you lost track of where the samples came from and since you requested a math explanation I'll try to go step by step using my notation and without checking other material to avoid being biased by how other authors present it
So we start from
$$ L(D,G) = E_{x \sim p_{r}(x)} \log(D(x)) + E_{x \sim p_{g}(x)}\log(1 - D(x)) $$
then you apply the definition of $E_{\cdot}(\cdot)$ operator in the continuous case
$$ L(D,G) = \int_{x} \log(D(x)) p_{r}(x)dx + \int_{x}\log(1 - D(x))p_{g}(x)dx $$
then you Monte Carlo sample it to approximate it
$$ L(D,G) = \frac{1}{n} \sum_{i=1}^{n} \log(D(x_{i}^{(r)}))  + \frac{1}{m} \sum_{j=1}^{m}\log(1 - D(x_{j}^{(g)})) $$
As you can see here I have kept the samples from the 2 distributions separated and used a notation that allows to track their origin so now you can use the right label in the Cross Entropy
$$ L(D,G) = \frac{1}{n} \sum_{i=1}^{n} L_{ce}(1, D(x_{i}^{(r)}))  + \frac{1}{m} \sum_{j=1}^{m} L_{ce}(0, D(x_{j}^{(g)})) $$
But you could also have decided to merge the 2 integrals before to have
$$ L(D,G) = \int_{x} \left( \log(D(x)) p_{r}(x) + \log(1 - D(x))p_{g}(x) \right) dx $$
which is mathematically legit operation, however the issue is when you try to
discretize this with Monte Carlo sampling.
You can't just replace the integral with one sum since you are Monte Carlo sampling and here, contrary to what we have done above, you do not have 1 distribution per integral to sample but in the same integral you have 2 distributions and for each sample you have to say what distribution it comes from which is where the issue is in your notation since you lost track of this information and it seems all the samples come from one distribution

Thanks a lot for the answer. Could you suggest me any resource or reading about this aspect of Monte Carlo Sampling (or in general)

Also, When we focus on distribuitons individually, $ CE(p_r(x), D(x))= \lim_{m \to \infty} \frac{1}{m} CE(1, D(x)) $. Is it valid equation?

I guess what you would like to do is
$$ \lim_{m \rightarrow \infty} \frac{1}{m} \sum_{i=1}^{m} CE(1, D(x_{i}^{(r)})) $$
but this is not approximating what you have on the left side since the above assumes this is a real sample (see the $r$ at the top) while on the left it is a generic sample, meaning you do not know what distribution it comes from, and this is reflected in first argument of the cross entropy: one is the real sample distribution and the other is a Dirac Delta since it is by construction real

$\textbf{Remark.}$ I'd leave this as a comment if I could.
Regarding notation (which I believe may be the cause of your issue here), the loss function is better written as
\begin{align*}
\operatorname{Loss} &= \frac{1}{m}\sum_{i=1}^m \left(\log D\big(x^{(i)}\big) + \log\Big(1-D\big(G\big(z^{(i)}\big)\big)\right)\\
&\approx \mathbb{E}_x[\log D(x)] + \mathbb{E}_z[\log(1-D(G(z)))],
\end{align*}
where the noise vectors, $z$, come from a suitable distribution, and $G(z)$ denotes the output of the generator; the $\approx$ symbol here implicitly assumes that the appropriate form of the Law of Large Numbers (LLN) applies.
Most importantly, the dependence on G is not trivial (for instance, what if $G$ never learns and always produces the same output?).
Also, the expectations should depend on their respective distributions, even when using LLN. For example, think of how you calculate the expectation of a discrete random variable.

Thanks for the contribution. However, output of G(z) is another probability distribution over x i.e. p_g(x). So, we can write that equation like I wrote with confidence. Also, in the original paper It is also written like that (https://arxiv.org/pdf/1406.2661.pdf at part 4.1). Also, when we convert two expectation into sigma form, they have same sigma in the same domain (x), so I thought it is okay.

That's fine, but you're assuming that p_r(x) and p_g(x) come from the same distribution just because they have the same domain.
For example, apply your original argument to some random variable X and any function f. It would imply that X and f(X) have the same mean, which clearly isn't true in general.

Also, When we focus on distribuitons individually, $ CE(p_r(x), D(x))= \lim_{m \to \infty} \frac{1}{m} CE(1, D(x)) $. Is it valid equation?


text:
In the machine learning literature, what does it mean to say that something is "embedded" in some space?
In the machine learning literature, I often see it said that something is "embedded" in some space. For instance, that something is "embedded" in feature space, or that our data are "embedded" in dot product space, etc. However, I've never actually seen an explanation of what this is supposed to mean. So what does it actually mean to say that something is "embedded" in some space?

Your question is different, but the answer can be found here.

Embedding is the process of representing data (from a source domain) in a new (or target) domain. Usually, the source domain is discrete, and the target domain is continuous. For example, embedding words into the continuous vector space can be done by the word2vec method.
The main reason behind using the embedding is doing meaningful mathematical computations in the target domain, which is not possible or straightforward in the source domain. For example, summing two words "brother" - "man" + "woman" not meaningful in the word and character levels. However, when using word2vec, embedding("brother") - embedding("man") + embedding("woman") can be meaningful and comparable with other embedded vectors; It should be near the embedded vector of "sister".

While this is of course correct, I'd add that also more abstract things like manifolds can be said to exist in a higher dimensional embedding space. In that case, one refers to an arbitrary vector space as the embedding space (as well), but wants to express that the data under consideration lives/varies (meaningfully) essentially only along a subset of the dimensions used to represent the data, where this subset of dimensions is called Manifold. Also the manifold is embedded in a (higher dimensional) space.


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

I edited this post to simplify and clarify it, and to make it more consistent with the answer that you accepted. Please, make sure that I did not change the meaning of it. If I did, you can just edit your post again and clarify what you're asking. If not, please, flag this comment for deletion.

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

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

Source code:

Video Classification
Video Classification Using 3D ResNet


text:
What is a unified neural network model?
In many articles (for example, in the YOLO paper, this paper or this one), I see the term "unified" being used. I was wondering what the meaning of "unified" in this case is.

One example where you see the evolution from "multiple components" to a more "unified neural network" is the family of R-CNN models. If you look at the initial R-CNN, it's composed of more than one component. The successive R-CNNs, such as Fast R-CNN, Faster R-CNN, and Mask R-CNN, if I remember correctly (and maybe not in all cases), try to unify some components to get to a single neural network that is able to do all the intermediate tasks (that should be the Mask R-CNN). I could be wrong because it's been a while since I had to deal with them, but it may be worth reading those papers.

@nbro Thank you for the opposite example.

A unified neural network model consists of one neural network as opposed to other models that rely on two or more neural networks.
For example, from page two of the YOLO paper:

2. Unified Detection
We unify the separate components of object detection into a single neural network. Our network uses features from the entire image to predict each bounding box. It also predicts all bounding boxes across all classes for an image simultaneously. This means our network reasons globally about the full image and all the objects in the image. The YOLO design enables end-to-end training and realtime speeds while maintaining high average precision.

In the paper by Xu and Wang, they add a branch to handle tracking to the Faster R-CNN architecture, which was designed for object detection.  This is a 'unification' of two models.
In the paper by Ebrahimi et al., on pages 42-43, you can see they are fusing multiple neural networks into one unified model:

We propose a unified user geolocation method that relies on a fusion of neural networks, incorporating different types of available information: tweet message, users' social relationships, and metadata fields embedded in tweets and profiles.


text:
What is a codon in grammatical evolution?
The term codon is used in the context of grammatical evolution (GE), sometimes, without being explicitly defined. For example, it is used in this paper, which introduces and describes PonyGE 2, a Python library for GE, but it's not clearly defined.  So, what is a codon?

Grammatical evolution
To understand what a codon is, we need to understand what GE is, so let me first provide a brief description of this approach.
Grammatical evolution (GE) is an approach to genetic programming where the genotypes are binary (or integer) arrays, which are mapped to the phenotypes (i.e. the actual solutions, which can be represented as trees, which, in turn, represent programs or functions), using a grammar (for example, expressed in Backus-Naur form). So, the genotypes (i.e. what is mutated, combined, or searched) and the phenotypes (the actual solutions, which are programs) are different in GE, and the genotype needs to be mapped to the phenotype to get the actual solution (or program), but this is not the case in all GP approaches (for example, in tree-based GP, the genotype and the phenotype are the same, i.e. trees, which represent functions).
Codons
In GE, a codon is a subsequence of $m$ bits of the genotype (assuming that genotypes are binary arrays). For example, let's say that we have only two symbols in our grammar, i.e. a (a number) and b (another number). In this case, we only need 2 bits to differentiate the two. If we had 3 symbols,  a, b and + (the addition operator), we would need at least a sequence of 2 bits to define each symbol. So, in this case, we could have the following mapping

a is represented by 00 (or the integer 0),
b is represented by 01 (or 1), and
+ is represented by 10 (or 2)

The operation a+b could then be represented by the binary sequence 001001 (or the integer sequence 021). The 2-bit subsequences 00, 01 and 10 (or their integer counterparts) are the codons.
What do we need codons for?
In GE, codons are used to index the specific choice of a production rule. To understand this, let's define a simple grammar, which is composed of

a set of non-terminals (e.g. functions) $N = \{ \langle \text{expr} \rangle, \langle \text{op} \rangle, \langle \text{operand} \rangle, \langle \text{var} \rangle \}$
,
a set of terminals (e.g. specific numbers or letters) $\mathrm{T}=\{1,2,3,4,+,-, /, *, \mathrm{x}, \mathrm{y}\}$,
a set of production rules $P$, and
an initial production rule $S = \langle \text{expr} \rangle $.

In this case, the set of production rules $P$ is defined as follows
\begin{align}
\langle \text{expr} \rangle & ::=
\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle \; | \;  \langle \text{operand} \rangle \\
\langle \text{op} \rangle & ::= + \;  | \;  - \;  | \; * \; | \; / \\
\langle \text{operand} \rangle & ::= 1 \;  | \; 2 \; | \;  3 \; | \;  4 \;  | \;  \langle \text{var} \rangle \\
\langle \text{var} \rangle & ::= \mathrm{x} \; | \;  \mathrm{y}
\end{align}
So, there are four productions rules. To be clear, $\langle \text{var} \rangle  ::= \mathrm{x} \; | \;  \mathrm{y}$ is a production rule. The symbol $|$ means "or", so the left-hand side of each production is a non-terminal (and note that all non-terminals are denoted with angle brackets $\langle \cdot \rangle$), which is defined as (or can be replaced with) one of the right-hand choices, which can be a non-terminal or terminal. The first choice of each production rule is at index $0$. The second choice at index $1$, and so on. So, for example, in the case of the production $\langle \text{var} \rangle  ::= \mathrm{x} \; | \;  \mathrm{y}$, $\mathrm{x}$ is the choice at index $0$ and $\mathrm{y}$ is the choice at index $1$.
The codons are the indices that we use to select the production rule's choice while transforming (or mapping) the genotype into a phenotype (an actual program).
So, we start with the first production, in this case, $S = \langle \text{expr} \rangle$. If it's a non-terminal, then we replace it with one of its right-hand side choices. In this case, there are two choices

$\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$ (choice at index $0$)
$\langle \text{operand} \rangle$ (choice at index $1$)

If our genotype (integer representation) is, for example, $01$ (note that this is a sequence of integers), we would replace $\langle \text{expr} \rangle$ with $\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$, then we would replace the first $\langle \text{expr} \rangle$ in $\langle \text{expr} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$ with $\langle \text{operand} \rangle$, so we would get $\langle \text{operand} \rangle \langle \text{op} \rangle \langle \text{expr} \rangle$, and so on and so forth, until we get an expression that only contains terminals, or the genotype is terminated. There can be other ways of mapping the genotype to the phenotype, but this is the purpose of codons.
Codons in biology
The term codon has its origins in biology: a subsequence of 3 nucleotides is known as a codon, which is mapped to an amino acid in order to produce the proteins. The set of all mappings from codons to amino acids is known as genetic code. Take a look at this article for a gentle introduction to the subject. So, in GE, codons also have a similar role to the role of codons in biology, i.e. they are used to build the actual phenotypes (in biology, the phenotypes would be the proteins or, ultimately, the organism).
Notes
Codons do not have to be 2-bit subsequences, but they can be $m$-bit subsequences, for some arbitrary $m$. The term codon is similar to the term gene, which is also often used to refer to specific subsequences of the genotype (for example, in genetic algorithms), although they may not be synonymous (at least in biology, genes are made up of sequences of codons, so they are not synonymous). Moreover, the binary $m$-bit codons can first be mapped to integers, so codons can also just be integers, as e.g. used here or illustrated in figure 2.2 of this chapter.
Further reading
You can find more info about codons in the book Genetic Programming: An Introduction by Wolfgang Banzhaf et al., specifically sections 9.2.2. (p. 255), 9.2.3. (an example) and 2.3 (p. 39), or in chapter 2 of the book Foundations in Grammatical Evolution by Dempsey et al.


text:
How do I prove that the MSE is zero when all predictions are equal to the corresponding labels?
In the back-propogation algorithm, the error term is:
$$
E=\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2,
$$
where $\hat{y}_k$ is a vector of outputs from the network, $y_k$ is the vector of correct labels (and we work out the error by calculating predicted-observed, squaring the answer, and then summing the answers for each $k$ (and dividing by 2).
How do you prove that if this answer is $0$ (i.e., if $E=0$), then $\hat{y}_k=y_k$ for all $k$?

This is very easy to prove.
Let's first prove that, if $\hat{y}_k = y_k$, then the $E = 0$. I will leave all steps, so that it's super clear.
\begin{align}
E
&=\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2 \\
&=\frac{1}{2}\sum_k(y_k - y_k)^2\\
&=\frac{1}{2}\sum_k(0)^2\\
&=\frac{1}{2}\sum_k 0\\
&=\frac{1}{2} 0\\
&=0\\
\end{align}
To prove the other way around, i.e. if $E = 0$, then $\hat{y}_k = y_k$, you can do as follows
\begin{align}
\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2
&=E\\
&=0
\end{align}
Recall now that any number squared is non-negative (i.e. positive or zero). Given that $(\hat{y}_k - y_k)^2 $ is non-negative, then $\sum_k(\hat{y}_k - y_k)^2$ is a sum of non-negative numbers. The only way that a sum of non-negative numbers is equal to zero is if all numbers are zero, so we must have $\hat{y}_k = y_k$ (because any non-zero number squared is non-zero).
(Note that $E$ is the mean squared error, i.e. a loss function, and it's not the back-propagation algorithm, which is just the algorithm that you use to compute partial derivatives of $E$ with respect to the parameters of the model, which are not even visible in the way you wrote $E$).


text:
What ensemble methods are used in the state-of-the-art models?
What ensemble methods are used in the state-of-the-art models?
When I surveyed the state-of-the-art methods of classification and detection, e.g. ImageNet, COCO, etc., I noticed that are few or even no references to the use of ensemble methods like bagging or boosting.
Is it a bad idea to use them?
However, I observed that many use ensemble in Kaggle competitions.
What makes it so different between the two groups of researchers?

In my opinion, it is not because ensemble methods are not good, just the state-of-the-art and Kaggle competitions are two different fields.
Kaggle competitions can be understood as an industry project where the target (accuracy, distance value, etc) is the most important, and they can select some computationally expensive way such as ensemble methods to reach it.
The state-of-the-art models in other ways belong to the research area, where the most important is the contribution for science, you can not just combine a lot of models then call it is the research (and so unfair with some small researcher groups). If you want to contribute something depend on ensemble idea, it should be like this paper.

I think it's possible to publish something that only shows that the combination of multiple models can achieve better performance than single models (maybe in some applied ML journal or something), although no example comes to my mind right now. In any case, you're right that research is different than Kaggle competitions. In research, ideas and novelty are fundamental, while the goal in Kaggle competitions is to achieve the highest performance (according to some metric).

Note, though, a lot of research (especially in DL) that attracts people and funds is the one that shows a model is better than another according to some performance measure (for example, AlphaFold). Moreover, novelty doesn't necessarily need to be radical, but it can just be a combination or improvement of other ideas: this is actually very common.

@nbro Agree, ResNext in image classification or YOLO in object detection is a good example of ideas combination


text:
How to derive matrix form of the Bellman operators?
Reading the Retrace paper (Safe and efficient off-policy reinforcement learning) I saw they often use a matrix form of the Bellman operators, for example as in the picture below. How do we derive those forms? Could you point me to some reference in which the matter is explained?
I am familiar with the tabular RL framework, but I'm having trouble understanding the steps from operators to this matrix form. For example, why does $Q^{\pi} = (I -\gamma P^{\pi})^{-1}r$? I know that for the value $V$ we can write
\begin{align}
V =  R + \gamma P^{\pi} V \\
V - \gamma P^{\pi} V =  R \\
V (I -\gamma P^{\pi}) =  R \\
V = R(I - \gamma P^{\pi})^{-1}
\end{align}
but this seems slightly different.
Picture from Safe and efficient off-policy reinforcement learning:

Here you have a related but more general question.

There's not much to derive here it's simply a definition of Bellman operator, it comes from Bellman equation. If you're wondering why
\begin{equation}
Q^{\pi} = (I - \gamma P^{\pi})^{-1}r \tag{1}
\end{equation}
they state that $Q^{\pi}$ is a fixed point which means if you apply Bellman operator to it you get the same value
\begin{equation}
T^{\pi}(Q^{\pi}) = Q^{\pi}
\end{equation}
You can easily check that since from $(1)$
\begin{equation}
r = (I-\gamma P^{\pi})Q^{\pi}
\end{equation}
if you plug it in definition of Bellman operator you get
\begin{align}
T^{\pi}(Q^{\pi}) &= r + \gamma P^{\pi} Q^{\pi}\\
&= (I - \gamma P^{\pi})Q^{\pi}+  \gamma P^{\pi} Q^{\pi}\\
&= Q^{\pi}
\end{align}

In other words, this proof shows that, if you have some value function $Q^\pi$, such that $r = (I - \gamma P^\pi)Q^\pi$, then $Q^\pi$ is a fixed-point of $T^\pi$. So, to actually answer the question: $Q^{\pi} = (I - \gamma P^{\pi})^{-1}r$ is true because that's what makes $Q^{\pi}$ a fixed point. Note that you could have just used $Q$ (rather than $Q^\pi$) in this derivation, i.e. any value function $Q$ such that $r = (I - \gamma P^\pi)Q$ is a fixed-point.

What is the exact meaning of the matrix notation in this context? I ask this in particular because the operator $P^{\pi}$ is defined as
\begin{equation}
(P^{\pi}Q)(s, a) = \sum_{s'}P(s'\vert s, a)\sum_{a'}\pi(a'\vert s') Q(s', a')
\end{equation}
which makes $P^{\pi}Q$ not being a common matrix-matrix multiplication

In particular, isn't here $P^{\pi}$ a tensor? When we use the Bellman operators on the value function we are marginalizing out the actions, but here we apply it explicitly to $Q(s, a)$ for each action, thus $P^{\pi}$ needs to be an $S\times S \times A$ tensor?

David Silver lecture (especially slides 22 onwards) can give you more insight into matrix equation, or you can just ask another question on website. $P$ could be a tensor or it could be a matrix of dimensions $(S \times A) \times S$ with appropriate reshaping.


text:
Can you use machine learning for data with binary outcomes?
I am totally new to artificial intelligence and neural networks and have a broad question that I hope is appropriate to ask here.
I am an ecologist working in animal movement and I want to use AI to apply to my field. This will be one of the few times this has been attempted so there is not much literature to help me here.
My dataset is binary. In short, I have the presence (1) and absence (0) of animal locations that are associated with a series of covariates (~20 environmental conditions such as temperature, etc.). I have ~1 million rows of data to train the model on with a ratio of 1:100 (presence:absence).
Once trained, I would like a model that can predict if an animal will be in a location (or give a probability) based on new covariates (environmental conditions).
Is this sort of thing possible using AI?
(If so, where should I be looking for resources? I write in R, should I learn Python?)

Potentially, even a simple method such as logistic regression will do. You could maybe try applying it at least as a baseline method.

Of course, you can use AI (especially Deep Learning) in your application. Your covariates will be the input to your AI model and the model should predict the probability of presence. The model has no problem with binary data and binary data is common in this field.
Also, note that the 1:100 ratio is not good and the network will probably learn to output absence for any input (this way it gets 99% accuracy but really it's not doing anything). So, you should probably balance them (using almost the same data, or telling the network to pay more attention to presence data (by weighting the related loss)).
I think nowadays you can find Deep Learning in any popular coding language. But most of the DL community uses Python and it's really easy to learn. If you want to learn Deep Learning there are a lot of sources on the internet. But I suggest you the Deep Learning courses of Deeplearning.ai in Coursera (If you have a lot of time) and CS231n of Stanford university on youtube (If you have time).


text:
Is there a proof to explain why XOR cannot be linearly separable?
Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)?
I understand why it's not linearly separable if you draw it graphically (e.g. here), but I can't seem to find a formal proof somewhere, I wanted to try and understand it with either an equation or example written down. I'm wondering if one exists (I guess it has to do with contradictions?), but I can't seem to find it? I have seen this, but it's more a reason than a proof.

Before proving that XOR cannot be linearly separable, we first need to prove a  lemma:
Lemma 1
Lemma: If 3 points are collinear and the middle point has a different label than the other two, then these 3 points cannot be linearly separable.

Proof: Let us label the points as point $A$, $B$, and $C$. $A$ and $C$ have the same label, and $B$ has a different label. They are all collinear with line $\mathcal{L}$.
Assume the contradiction, so a line can linearly separate $A$, $B$, and $C$. This means a line must cross between segment $AB$, and segment $BC$ to linearly separate these three points (by definition of linear separability). Let us label the point where the line crosses segment $AB$ and point $Y$, and the point where the line corsses segment $BC$ and point $Z$.
However, since segments $AB$ and $BC$ are collinear to line $\mathcal{L}$, points $Y$ and $Z$ also falls on line $\mathcal{L}$. Since only one unique line can cross 2 points, it must be that the only line that passes segments $AB$ and $BC$ and (therefore separates points $A$, $B$, and $C$) is line $\mathcal{L}$.
However, line $\mathcal{L}$ cannot linearly separate $A$, $B$, and $C$, since line $\mathcal{L}$ also crosses them. Therefore, no line exists can separate $A$, $B$, and $C$.
Main proof

Consider these 4 points that represent a XOR table. Let us label them clock-wise, so the top-left point as $A$, top-right point as $B$, bottom-right point as $C$, and bottom-left point as $D$. So $A$ and $C$ have the same label, and $B$ and $D$ have the same label. We want to show that points $A, B, C$ and $D$ cannot be linearly separable.
Assume the contradiction, and that there is a line that can separate these 4 points.
Imagine a fifth point that lies in the center, and let us label this as point $E$.
Since $E$ lies in the center, the three points $A, E$ and $C$ are collinear. Similarly, since $E$ lies in the center, the three points $B, E$ and $D$ are collinear.
Because we assume a line can linearly separate $A, B, C$ and $D$, then this line must label point $E$ as some label. If $E$ shares the same label as $A$ and $C$, then the points $B, E$ and $D$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable. Likewise, if $E$ shares the same label as $B$ and $D$, then the points $A, E$ and $C$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable.
Therefore it is impossible to give a label to $E$ while satisfying linear separability. As a result, our assumption must be false, and the four points $A, B, C$ and $D$ cannot be linearly separable.

It may be worth mentioning the perceptron and how it relates to your proof (i.e. is the perceptron only a linear model, i.e. a line?). The original post contained the word "perceptron" in the title, so I guess we're talking about the perceptron here.

Here is a similar contradiction based answer using basic coordinate geometry.

Is there a proof to explain why $XOR$ cannot be linearly separable?

Let us suppose, if possible, that the $XOR$ function, given by following table, is linearly separable.
\begin{array}{|c|c|c|}
\hline
  x& y & x \text{ xor } y\\
\hline
   0&0&0\\
\hline
   0&1&1\\
\hline
  1&0&1\\
\hline
   1&1&0\\
\hline
\end{array}
This ensures the existence of a line $L:ax+by+c=0$ such that the points $(0,0)$ $\&$ $(1,1)$ both lie on the same side of $L$ and the points $(0,1)$ $\&$ $(1,0)$ also lie on same side of $L$ but opposite to that of $(0,0)$ $\&$ $(1,1).$
Also from basic coordinate geometry, we know that if the points $(x_1,y_1)$ $\&$ $(x_2,y_2)$ lie on same side of a line given by $px+qy+r=0$ then,
$$(px_1+qy_1+r)\cdot(px_2+qy_2+r)>0$$
and if they are on opposite sides of the line then,
$$(px_1+qy_1+r)\cdot(px_2+qy_2+r)<0$$
Since $(0,0)$ and $(1,1)$ lie on same side of $L$, so
\begin{equation}
c\cdot(a+b+c)>0
\tag{1}
\end{equation}
And, as $(1,0)$ and $(1,1)$ lie on different sides of $L$, so
\begin{equation}
(a+c)\cdot(a+b+c)<0.
\tag{2}
\end{equation}
Similarly as  $(0,1)$ and $(1,1)$ lie on different sides of $L$,
\begin{equation}
(b+c)\cdot(a+b+c)<0
\tag{3}
\end{equation}
On adding equations $(2)$ and $(3)$ we get,
$$(a+b+2c)\cdot(a+b+c)<0$$
$$\implies (a+b+c)\cdot(a+b+c)+c\cdot(a+b+c)<0$$
$$\implies (a+b+c)^2+c\cdot(a+b+c)<0$$
Since $(a+b+c)^2\geq0$ for any choice of numbers $a,b,c,$ so
$$c\cdot(a+b+c)<-(a+b+c)^2\leq0$$
$$c\cdot(a+b+c)<0$$
which is a contradiction of equation $(1)$, proving the non-existence any such line $L.$

The $XOR$ function is not linearly separable.


text:
What does "class-level discriminative feature representation" mean in the paper "Semi-Supervised Deep Learning with Memory"?
I am reading the paper Semi-Supervised Deep Learning with Memory (2018) by Yanbei Chen et al.  The topic is the classification of images using semi-supervised learning. The authors use a term on page 2 in the middle of the page that I am not familiar with. They write:

The key to our framework design is two-aspect: (1) the class-level discriminative feature representation and the network inference uncertainty are gradually accumulated in an external memory module; (2) this memorised information is utilised to assimilate the newly incoming image samples on-the-fly and generate an informative unsupervised memory loss to guide the network learning jointly with the supervised classification loss

I am not sure what the term discriminative feature representation means.
I know that a discriminative model determines the decision boundary between the classes, and examples include: Logistic Regression (LR), Support Vector Machine (SVM), conditional random fields (CRFs) and others.
Moreover, I know that, in machine learning, feature learning or representation learning is a set of techniques that allows a system to automatically discover the representations needed for feature detection or classification from raw data.
Any insights on the definition of this term much appreciated.

Discriminative models give the probability of an element in the feature space $x \in X$ belonging to a class $y \in Y$, i.e. $p(Y|X)$, where $Y$ is the set of classes in a classification problem.
The discriminative feature representation in this context means the feature map/s  which are the output/s of the convolutional layers of the backbone (the convolutional layers of the neural network) which (presumably) differ on the basis of their class, and can be used to discriminate which class the original image belongs to, in the case of image classification.