text:
Why is the behaviour policy denoted by $\beta$ and the exploration policy by $ \mu'$ in the DDPG paper?
I am learning about the deep deterministic policy gradient (DDPG) (Lillicrap et al, 2016) and got confused about the notation of the behavior policy.
Lillicrap et al. denote the policy gradient by
$$\nabla _{\theta^\mu} J \approx \mathbb{E}_{s_t \sim \rho^\beta} \left[ \nabla _{\theta^\mu} Q(s,a|\theta^Q) | s=s_t, a=\mu(s_t ; \theta ^\mu)  \right],$$
where $\beta$ denotes the behavior policy (equation 5 in the original paper).
However, when they talk about exploration, they denote the exploration policy by $ \mu'$. This notation seems confusing to me since the target actor network is also denoted by $\mu'(s|\theta^{\mu'})$.
As far as I understand, the exploration policy is not directly linked to the target critic network but rather corresponds to the previously mentioned behavior policy $\beta$. Is this correct or am I understanding it wrong?

I think you mean target actor network, not the target critic

Did I answer your question? If not then please let me know and I will amend my answer based on your feedback, if so then please accept the question.

Thank you a lot for your explanations. Just to make sure I understand it correctly: The tuple $(s,a,r,s')$ was sampled with the (back then valid) exploration policy. However, the current exploration policy might have changed. Therefore, the authors have to introduce a new variable $\beta$ denoting "the policies, that were valid at the time back then".

@DavidIreland Yes, I was referring to the actor network. I edited the original post. Thank you

$\beta$ is not a variable, it is a policy. The introduction of $\beta$ means that the tuple $(s, a, r, s')$ does not need to be sampled according to our most recently policy, so we can sample previous experiences that come from the old policy as you say.

You are right, it is sloppy notation by the authors. However, the target network is not necessarily linked to the behaviour policy $\beta$ either.
Essentially when they take the expectation with respect to $\rho^\beta$ they are taking expectation with respect to a state distribution induced by some policy $\beta$ that is not necessarily the same as our current policy -- this is what makes DDPG an off-policy algorithm.
The target actor network $\mu'$ is used in the loss function for the critic; the target for the critic (ignoring parameters for brevity) $y = r + \gamma Q(s', \mu'(s'))$ where $s'$ is the state we transitioned to from $s$ when we took an action $a$.
Now, $a$ was sampled as part of the tuple $(s, a, r, s')$ from our replay buffer, meaning that $a$ will have been chosen according to some past version of our policy, plus some exploration noise $\mathcal{N}$. The way this links to the behaviour policy $\beta$ is that because we have sampled it from some old version of our policy, i.e. not our current policy, it is instead coming from this behaviour policy $\beta$.
The target network $\mu'$ is simply a copy of the current actor network where the weights are updated using the polyak averaging technique and is not really related to the behaviour policy $\beta$, at least not in any useful way for you to think about it.


text:
Normalizing float prices with movements up to a factor of 100
I have a bunch of arbitrary float numbers (asset prices), that I have to feed into a neural network.

In the data set: values are between 1E-10 and 1E6
In a single sample: values may differ by a factor 100
Even slight changes (price movements) are important

I tried a naive "min/max" normalization to the range [0..1], but the performance of the model degrades quickly if the values within a single sample are changing more than by a factor ~5. (The performance is determined by using predictions in a trading-simulation)
My own ideas:

Provide diffs from one float to the next one (change in price from t to t+1).
Split each float number into [0..1] mantissa and exponent

Exponent as one-hot-vector mapping values from -10 to 6
Exponent min/max normalized to [0..1]

How should I correctly normalize such a data to feed into AI?
Requested details of the network:

What are you trying to predict?

Next candle
Expected gain of a long position / raise in price in the next ~5 candles

How are you assessing the performance of the model?

I'm using a trading simulation with predictions on fresh data

Which model?

Multiple parallel 3 layers-LSTMs
Each LSTM process separate consecutive chunk of candles

A regular feedforward neural network?

Yes, multiple inputs goes though LSTMs
Then concatenate to single vector
Plus a bunch of dense layers

With how many layers and which activation functions?

activation functions: relu, sigmoid (for output)
I played with different configurations, e.g.

~ 15 layers total
500.000 trainable params

Which loss function are you using?

mean_squared_error

What do you mean by "it performs ok" or not, in practice? What are you trying to predict? How are you assessing the performance of the model? Which model? A regular feedforward neural network? With how many layers and which activation functions? Which loss function are you using? Edit your post to include these details, which could be useful.

Added all requested information.

@nbro please, let me know, if more information is needed.

Thanks for the details. I am not sure I can help you in this case, because I don't remember having solved a similar problem. However, the range of your data is really wide, and this can indeed make the task more difficult. You could try using a different configuration of the neural network. You have 15 layers, but "only" 500000 parameters. That doesn't seem right. A model with 15 layers can quickly have more parameters. Well, it also depends on the hyper-parameters of these layers (like width).

@nbro Ah! You mean, the small amount of parameters per layer may cause problems by sensing small changes in the input data? Should I invest time and try to go with the Split each float number into [0..1] mantissa and exponent approach? Thank you!

No, I didn't mean that. I meant that, if you have 15 layers, I would expect that the total number of parameters to be higher. Are you sure that the total number of parameters is just 500000? That was my question. Anyway, having 15 layers seems a big number of layers, and it can lead to vanishing/exploding gradients, although if you're using LSTMs, these issues should be mitigated to some extent, at least, compared to vanilla RNNs. Regarding your 2nd approach, I don't really know. Your first one looks more promising to me, but this is just a guess.

@nbro Yes, currently ~500,000. But I can easily increase it. Also my network is only 12 layers deep becaues of 2 output vectors. (Last 3 layers goes in parallel). Which number of training parameters would sound appropriate to you?  Thank you!

Mathematically speaking when dealing with fat tailed distributions or values that varies in a range of several order of magnitude the most common and simplest solution is to move to logarithmic space. Of course that requires positive values before scaling the data, and the log of a number can be negative as well, so you might want to normalize your data before and after. Something like:

normalize data to be positive
move to log space to reduce skewness and magnitude range of the data
normalize again in the proper input range for your model

regarding your ideas:

applying moving average is always a good preprocessing step when dealing with temporal data, but that's more noise cleaning not really data scaling/normalization
splitting mantissa and exponent sounds like a too easy trick to work, plus it doesn't really mathematically tackle the skewness issue.

Log is a great idea! But after log is applied, the small changes in value will become even smaller. How many training parameters on the 1th (and may be 2th) layers do I need to make the network able to sence small changes? Also, my data goes straight into LSTM. Would it be better to introduce a couple of dense layers (operating on each single LSTM input element/row) as a data preprocessor? Thank you!

I wouldn't advice to add dense layers, time series are really specific type of data and there are many well known practices to preprocess them, so I would look into them first. For example identifying the trend-seasonality-rest components, investigating and removing collinearity if you're using multiple variables and so on.

if you have reasons to focus the model on really small changes (which be aware to me sounds like overfitting noise rather than predicting a trend) you could play with the forget gate of the LSTM. Usually a normal sigmoid $1 / 1 + e^{-x}$ is applied to the input and previous cell data. By adding the temperature parameter you can tune how much is forget and how much is retained from past cells $1 / 1 + e^{-x/t}$. Specifically, you want a t value smaller than 1 (so the sigmoid get squeezed close to the y axis, which means more values will be pushed to zero and forget).

source: Stack Exchange

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

sort: votes


text:
Is there any known technique to determine a graph from a 1D signal pattern?
I'd like to evaluate the possibility of using a Machine/Deep Learning technique as a sort of pattern recognition and parameters estimation.
The problem I want to address can be stated as follows: Let's consider that I have a set of interacting "particles" that can be represented as a graph in which the vertices represent the particles and the edges the magnitude of the interaction amongst them. For instance, in the diagram below I'm showing a particle graph formed by 4 interacting particles.

So each particle/vertex has a value (e.g. $A=3.1$, $B = 4.2$, etc.) and each edge contains the magnitude of the interaction between two connected nodes/àrticles (e.g. $AB = 5.3$, $AC = 1.1$, $DB = 0$, etc).
With all this information, there exists a quantum mechanics algorithm that, after some complex calculations, results in a 1D signal (the pattern; essentially a vector of X-Y values). The overall process is illustrated in the figure below:

The appearance of the obtained signal will therefore depend upon the values of the graph. The goal is, in this case, the inverse problem: given one of these 1D signals (that is, a characteristic pattern), is it possible to determine the graph with its corresponding values?
I could create a training set formed by a very large number of simulated graphs with corresponding 1D patterns.
Since my experience with ML has so far focused only on simple classification problems, it is not clear to me which ML method would be more convenient or whether or not this problem can actually be addressed by an ML technique. Any general recommendation or advice would be highly appreciated.

To put in other words what you ask: Given RMN signal is it possible to identify the molecule?

Not really, this is not about molecules. It is about a graph which actually represents a spin system. A spin system can be part of a molecule, but they are not the same thing.

OK. However, conceptually both problems are not that different, are they? We have a 1D signal and we would like to recreate a spatial relationship?

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


text:
Are training sequences for LMs sampled in an IID fashion?
If I understand correctly, when training language models, we take a document and then chunk the document into a sequences of k tokens. So if the document is of length 30 and k=10, then we'll have 20 chunks of 10 tokens each (token 1-11, 2-12, and so on).
However these training sequences are not iid, right? If so, are there any papers that try and deal with this?

Language models explicitly assume that word sequences are not independent and identically distributed (iid). A word-based model that assumed iid within each sequence could only predict probabilities of words according to some other context than surrounding words, which would not be very useful for a language model.
The training processes for statistical models often require iid input/output pairs when sampling e.g. minibatches. Neural networks definitely train better when datasets are shuffled to remove any chance of correlation between examples as they are used to update parameters.
How to resolve these two different needs? When training a sequence-based model on many sequences, it is the distribution of sequences that needs to be iid and representative of the overall population. The distribution of items within the sequence is what is being learned, so should not be obscured or removed.
As an analogy, you do not usually want to shuffle the rows of pixels in an image when training image classifiers. The spatial pattern in the image needs to be preserved in the same way that the sequential pattern in a sentence needs to be preserved, because the pattern is part of the data being modelled. With image data, you accept non-iid relationships between the pixels that are next to each other within a single image, then apply shuffling and stratifying algorithms at the level of individual images.

If so, are there any papers that try and deal with this?

There may be some original papers from 50 years ago which compare iid with non-iid data when training sequences fed into RNNs, but it has been a standard part of engineering practice for decades now to shuffle datasets, and the separate sequences used to train RNNs are no different.
From your comments:

However the sequences that are sampled for training are not iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?

You are correct, the raw set of sequences is not iid if they are collected in that fashion. However, the dataset is always shuffled or resampled for training purposes, it is not fed into training routines in that raw state. The shuffling (of selected sequences which are kept intact internally) happens in-between the raw data collection and the training.

There are some simple statistical models that do not require iid data to train on. This occurs for example in tabular reinforcement learning, which can learn online from a single continuous sequence of states, actions and rewards. An equivalent language model would be word- or letter-based ngrams.

I agree that LMs for a single sequence assume non-iid. However the sequences that are sampled for training are not iid if they are multiple sequences generated sequentially from the same document, which from what I understand happens often?

@Opt: You keep the sequences intact internally, but shuffle the collection of sequences as you would any other dataset that you need to be iid. This is separate to how the data might be collected. It is fine to collect them in order from source documents, the shuffling comes later, i.e. in between collecting the data and training with it

Shuffling necessarily doesn't give iid - see https://math.stackexchange.com/questions/2965518/does-the-shuffling-of-a-sequence-of-measurements-produce-an-i-i-d-sequence

*doesn't necessarily

@Opt: The results in that question are edge cases that are not going to be relevant in most machine learning (including statistical language models), even if they are interesting mathematically.

That's not true -- suppose you split dataset into train/validation and use validation set for early stopping etc. Suppose this is the sentiment analysis task. Then if it's not iid, training data having proportionally more positive sentiment than the overall data will mean validation has proportionally less which lead to suboptimal stopping time, etc.


text:
Q-learning in gridworld with random board
I'm trying to use Q-learning in order to solve Wumpus world environment.
Wumpus world is a toy problem on 4x4 gridworld. The agent starts in entry position of the cave, looks for gold (agent can sense that he is on the gold field), then he has to pick it up and leave cave in the entry position. Some fields are safe, other contain pit or wumpus (monster). If agent move to the pit or wumpus field he dies. The fields next to wumpus or pit (not diagonally!) have properties that agent can sense - stench (wumpus), breeze (pit). Agent achieve positive reward if he leaves cave with gold and negative if he dies. Action space: turn right/left, move forward, shoot arrow (if shot in good direction it can kill wumpus, only 1 available), pick up gold, leave cave. There: https://www.javatpoint.com/the-wumpus-world-in-artificial-intelligence you can find more detailed description of environment.
It is easy to solve this problem if the gridworld is constant. I have a huge problem to even start thinking about it if gridworld is random in every learning episode (random fields and random size) and also random in testing. How should I define it (especially state space)? How should I create q table? I'm using Python.
Thank you in advance for any help.

From your linked description of the game, we can see it has a key property when used normally in AI teaching:

Partially observable: The Wumpus world is partially observable because the agent can only perceive the close environment such as an adjacent room.

This makes sense, the problem of avoiding hazards would be trivial if the full map was revealed to the agent. The problem is also not about learning a specific map.
You could use the agent's perception to construct a simple state table based on current observations:

Current location
Current facing
Boolean flags for stench, breeze, glitter, bump, scream

This would be relatively easy to build into a Q table, and might have some success. However, it would likely perform a lot worse than the propositional logic and planning suggested suggested at https://www.javatpoint.com/the-wumpus-world-in-artificial-intelligence for two reasons:

Agent will not take account of knowledge specific to the current map that it has gathered. This is critical, because the stench and breeze sensors only tell you that at least one of the adjacent rooms has a hazard. In theory you know that this will not be any of the rooms that the agent has already visited, but a simple state representation based on current observations will not capture this.

Agent will not plan using the deterministic rules of the game that you know and could code for.

There are a few different approaches you could take to improve on these issues. Sticking with Q learning and trying to solve this by improving the state representation, you could look at the suggested knowledge-building structure from the java T point site, and replicate something like it as input features:

Current facing
Whether or not the last move forward resulted in a bump
Whether or not there has been a scream
For each allowed room, a binary flag set to true if the room has been visited by the agent
For each allowed room, a set of binary variables covering the three observations that are about the room: stench, breeze, glitter
Either the current location separately, or another binary variable added to each grid square set to true for the one room that the agent is in

When multiplied by 16 to cover each room, you will end up with ~84 binary flags. Although many combinations will not be possible, this is still going to be far too large a state space to use with a Q table. You would probably use a simple neural network and DQN agent to solve this problem using Q learning.

"For each allowed room" - do you mean for each room of the gridworld - 16 in 4x4 grid ? 2) So in the 4x4 grid world there will be: 16 (4x4 - x * y) * 4 (agent's direction) * 2 (if last move forward was bump) * 2 (if scream) * 2 (if visited by agent) * (2 * 2 * 2) (stench, breeze, glitter) * 16 (agent's location) = 65536 ? 3) For each allowed room, a binary flag set to true if the room has been visited by the agent - why do we use this information ?

@Geperd Your state space caclulation is way off, because it is not tracking separate flgas for each room. The state space is around $2^{84}$. We need to use this information because figuring out logical positions of the pits and wumpus is part of the problem, and cannot be done using current observation (this is why I critique the simple observation "Agent will not take account of knowledge specific to the current map that it has gathered."). You need a structure within the agent that summarises information discovered so far - my suggestion at the end of the answer is one way to do this.

Sorry to ask you again and again but i can't see it yet. So the state space is: $2^4$ (direction) * $2^2$ (bump) * $2^2$ (scream) * $2^{16} * 2^2$ (each room if visited) * $2^{16} * 2^2 * 2^{16} * 2^2 * 2^{16} * 2^2$ (for each room stench, breeze, glitter) *  $2^{16} * 2^2$ (if agent is in room) = $2^{98}$ ??? If my calculations are wrong can you please write it in comment in similar fashion as above?

@Geperd You have some extra $2^2$ in there for most of the factors. For instance, a binary flag on each room for "stench" is $2^{16}$, not $2^{16} \times 2^2$. There is some flexibility about how you represent current location and direction, so you may not get exactly $2^{84}$. That is not too important, but you should expect to have something closer to it than $2^{98}$


text:
My cross entropy loss gradient calculation is wrong according to the answer key
Given a neural network model for Covid-19 classification with $C=1$ for positive and $C=0$ for negative

Let $x_1 = 6$ and $x_2=2$ find

Probability if the patient got Covid-19 $p\left(C=1 | x; w,b\right)$
Probability if the patient didn’t get Covid-19 $p\left(C=0 | x; w,b\right)$
Find the gradient of $CE_{Loss}$

My attempt
For the first problem
$$
\begin{aligned}
O_1 &= \text{ReLU} \left( b_1 + \sum{x_iw_i} \right) \\
&= \text{ReLU} \left( 0.2 + 6 \cdot 0.3 - 0.2 \cdot 2 \right) \\
&= \text{ReLU} \left( 1.6 \right) \\
&= 1.6 \\
\end{aligned}
$$
$$
\begin{aligned}
O_2 &= \text{Sig} \left( -0.6 - 0.1 \cdot 2 - 0.2 \cdot 6 \right) \\
&= \text{Sig} \left( -2 \right) \\
&\approx 0.8808 \\
\end{aligned}
$$
$$
\begin{aligned}
O_3 &= \text{Sig} \left( 0.6 - 0.3 \cdot 0.8808 + 1.6 \cdot 0.5 \right) \\
&\approx 0.75690 \\
\end{aligned}
$$
$$
\begin{aligned}
p\left(C=1 | x; w,b\right) = O_3 \approx 0.75690
\end{aligned}
$$
For the second problem
$$
\begin{aligned}
p\left(C=0 | x; w,b\right) = 1 - \left(C=1 | x; w,b\right) = 0.2431
\end{aligned}
$$
For the third problem
Since it is a lot of things to calculate I'll take $\frac{\delta L}{\delta w_6}$ as example
$$
\begin{aligned}
\frac{\delta L}{\delta w_6} &= \frac{\delta L}{\delta \hat{y}} \cdot \frac{\delta \hat{y}}{\delta w_6} \\
&= \left(\hat{y}-y\right)O_2\left(O_3 \left(1-O_3\right)\right)\\
&= \left(O_3-y\right)O_2\left(O_3 \left(1-O_3\right)\right)
\end{aligned}
$$
The answer key says it should be $\left(O_3-y\right)O_2$. Where did I go wrong?

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.

For the first problem your $O_2$ is mistaken and should be corrected as below
$$
\begin{aligned}
O_2 &= \text{Sig} \left( -0.6 - 0.1 \cdot 2 + 0.2 \cdot 6 \right) \\
&= \text{Sig} \left( 0.4 \right) \\
&\approx 0.5987 \\
\end{aligned}
$$
$$
\begin{aligned}
O_3 &= \text{Sig} \left( 0.6 - 0.3 \cdot 0.5987 + 1.6 \cdot 0.5 \right) \\
&\approx 0.7721 \\
\end{aligned}
$$
$$
\begin{aligned}
p\left(C=1 | x; w,b\right) = O_3 \approx 0.7721
\end{aligned}
$$
For the second problem thus corrected to:
$$
\begin{aligned}
p\left(C=0 | x; w,b\right) = 1 - \left(C=1 | x; w,b\right) = 0.2279
\end{aligned}
$$
For the third problem since $w_6$ is one of the weights connecting the output layer and we assume $\hat{y}=g(z^{(3)})$, where $z^{(3)}$ is the net input for the output unit and $g$ is its sigmoid transfer function. Then we arrive at:
$$
\begin{aligned}
\frac{\delta L}{\delta w_6} &= \frac{\delta L}{\delta \hat{y}} \cdot \frac{\delta \hat{y}}{\delta z^{(3)}} \cdot \frac{\delta z^{(3)}}{\delta w_6} \\
\end{aligned}
$$
and since $L$ is the binary cross-entropy loss function, we know $\frac{\delta L}{\delta \hat{y}} = \frac{(\hat{y}-y)}{(1-\hat{y})\hat{y}}$. And from above transfer function we know $\frac{\delta \hat{y}}{\delta z^{(3)}}=(1-\hat{y})\hat{y}$, and $\frac{\delta z^{(3)}}{\delta w_6}=O_2$. Thus finally we simplify as $\frac{\delta L}{\delta w_6}=(O_3-y)O_2$

Thanks for your response. One more thing, for $\frac{\delta L}{\delta w_4}$ is it $\frac{\delta L}{\delta \hat{y}} \cdot \frac{\delta \hat{y}}{\delta z^{(3)}} \cdot \frac{\delta z^{(3)}}{\delta z^{(2)}} \cdot \frac{ \delta z^{(2)}}{\delta w_4} = (O_3-y)(1-O_2)O_2x_2$?

For the hidden layer it's more complex and you need to further chain $\frac{\delta z^{(3)}}{\delta z^{(2)}}$ into $\frac{\delta z^{(3)}}{\delta O_2} \cdot \frac{\delta O_2}{\delta z^{(2)}}$, and then try to simplify from there.


text:
Question regarding the ELBO decomposition proposed by Hoffman&Johnson
recently I'm trying to read a paper by Hoffman and Johnson discussing an alternative decomposition of ELBO in variational autoencoders. In formula (9) and (10) of their original paper, they proposed some pre-requisite assumptions as follows:
\begin{equation}
q(n, z) \triangleq q(n)q(z|n);\ q(z|n) \triangleq q(z|x_n);\ q(n)=1/N
\end{equation}
\begin{equation}
p(n, z) \triangleq p(n)p(z|n);\ p(z|n) \triangleq p(z);\ p(n)=1/N
\end{equation}
where n is the index of a randomly picked instance from a size $N$ subsample from the data distribution $p(x)$. With these preliminaries, H&J derived equation (11):
\begin{equation}
\frac{1}{N}\sum_{n=1}^{N} \mathrm{KL}(q(z_n|x_n)\|p(z_n)) = \mathrm{KL}(q(z)|p(z)) + \log{N} - \mathbb{E}_{q(z)}[\mathbb{H}[q(n|z)]]
\end{equation}
I had no problem deriving (11) from (9) and (10), but why $p(z|n)\triangleq p(z)$? Pardon me if I have missed any critical statement in the context, but these authors seemed not to have given any justification on this formula before using it. How could one assume that the posterior probability $p(z|n)$ to get a specific $z$ given an $x_n$ is independent of $x_n$?
I will really appreciate it if you can provide some better insight! Thank you!

As for your question why $p(z|n)\triangleq p(z)$, it's the same reason for the latent prior ${\displaystyle p_{\theta }(z)}$ of traditional VAE which belongs to the decoder as a regularizer and is independent of any input data $x_n$ and is often assumed to be the standard multivariate Gaussian for continuously valued input data such as images mainly due to analytic simplicity, sampling convenience, and noninformative continuous latent space prior. Note the encoder's latent posterior $q(z|n)$ is different and is dependent of the input $x_n$ as you quoted.


text:
Why in loss function of DQN does the expectation depend on current state $s$?
Please see slide 39 in https://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture14.pdf
Why in loss function of DQN  does the expectation  depend on current state $s$?

In DQN the loss function is designed to minimize the difference between the prediction network's $Q(s,a;\theta)$ and the target network's $Q^*(s,a)$ computed using the Bellman optimality equation as a conditional expectation defined on slide 39 of your reference. Since the target $Q^*(s,a)$ depends on the current state $s$, the expectation is taken over the distribution of transitions $(s,a,r,s′)$ encountered during training from the replay buffer, thus the loss function inherently depends on the current state $s$. The dependence on the current state reflects the idea that we want to learn a policy that is effective across the entire state space, not just for a specific state.


text:
Is $s_0$ the current state in policy gradients?
As far as I understand from here (source: OpenAI), the objective function in Policy Gradient is:
$$J(\pi_{\theta})=E_{\tau\sim\pi_{\theta}}[R(\tau)],$$
where $R(\tau)=r_0+r_1+...+r_T$, with $r_t$ being taken from a trajectory $\tau = (s_0,a_0,s_1,a_1,...)$. $s_0$ is defined as the start state, sampled from a distribution $\rho_0$, and thus does not depends on the parameter $\theta$ for a policy $\pi$.
However, in the earlier tutorial here (source: OpenAI), the definition for the value function $V^{\pi}$ is $V^{\pi}(s)=E_{\tau\sim\pi}[R(\tau)|s_0=s]$. Compared with the definition in Sutton & Barto, i.e. $V^{\pi}(s)=E_{\pi}[G_t|s_t=s]$.
Can I correctly understand that OpenAI is now defining $s_0$ as the current state? If so, it conflicts with the earlier definition in the policy gradient setting, where $s_0$ must be the start state, so that its probability does not depend on the policy.

the 'correct' objective for policy gradient algorithms is to maximise the value function from the initial state $s_0$. this is why there should also be a second discount factor in the policy gradient, to discount the state distribution. however, in practice, this rarely happens. you can look at a paper 'is the policy gradient a gradient?' for a more in depth discussion on this.

@David There are more than one valid PG objectives. Episodic and continuing problems will have different definitions of $J$

@NeilSlater sure but this misunderstanding comes up a lot and is mostly due to the lack of second discount factor that is not added in policy gradient algorithms that people will be familiar with. I'm fairly certain there's a question on this site about why there is a second discount factor in the pseudocode of the Sutton and Barto book which is a common source of confusion

Below is the explanation around your stated OpenAI's earlier tutorial for the value function:

The On-Policy Value Function, $V^{\pi}(s)$, which gives the expected return if you start in state $s$ and always act according to policy $\pi$

Therefore there seems no incompatibility issue of notation of $s_0$ here which is the  initial state of a trajectory $\tau$, for any current state $s$ you can treat it as an initial state of the reward-to-go trajectory $\tau$ from that point on until the end of its episode as mentioned in your first reference.


text:
Interpretation of changing action probability based on policy gradient expression
Please see slide 78 in https://cs231n.stanford.edu/slides/2017/cs231n_2017_lecture14.pdf

$$\nabla_{\theta} J\left(\theta\right) \approx\sum_{t\ge 0}r(\tau) \nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)$$

Interpretation:

-If $r(\tau)$ is high, push up the probabilities of the actions seen.

-If $r(\tau)$ is low, push down the probabilities of the actions seen.

Question: It is not clear to me how this interpretation is done based on the mathematical expression. I will be happy for a detailed explanation.

Bear in mind $\nabla_{\theta} J$ is used to update parameters $\theta$ in each step and $r(\tau)$ is the total reward of a sampling trajectory $\tau$ where we can rewrite the policy gradient equation as $$\nabla_{\theta} J(\theta) \approx r(\tau) \sum_{t\ge 0} \nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)$$ If $r(\tau)$ is positively great then the above policy gradient ascent algorithm intuitively intends to update the parameters in a direction so that each term $\log \pi_{\theta}\left(a_{t} \mid s_{t}\right)$ is pushed up. And since the $\log$ function is monotone, each term $\pi_{\theta}\left(a_{t} \mid s_{t}\right)$ is pushed up too which is nothing but exploitation viewed from the thesis of exploration vs exploitation of RL. This is why your reference claims it might seem simplistic to say that if a trajectory is good then all its actions were good.
If this cannot convince you, let's use a simple grid world example where an agent starts at the left corner and aims to reach a goal at the right corner. Suppose there are only two possible actions in any state $s$: $UP$ and $RIGHT$, and initial probabilities of taking these actions under the policy $\pi_{\theta}$ are $\pi_{\theta}(UP∣s)=0.5,\pi_{\theta}(RIGHT∣s)=0.5$. The reward $r(τ)$ for a trajectory $τ$ is $+10$ if it reaches the goal using the action $RIGHT$. For simplicity, let's say the softmax parameterization for actins in any state $s$ is: $π_θ(UP∣s)=\frac{e^{θ_1}}{e^{θ_1}+e^{θ_2}}, π_θ(RIGHT∣s)=\frac{e^{θ_2}}{e^{θ_1}+e^{θ_2}}$. Apparently, only by choosing action $RIGHT$ at each state $s$ the parameters $\theta$ will be pushed up in the direction of $θ_2$ per above policy gradient algorithm and thus $π_θ(RIGHT∣s)=\frac{e^{θ_2}}{e^{θ_1}+e^{θ_2}}$ is pushed up as well.


text:
Is it possible to train a perceptron to tell if a picture is a dog or cat?
I know perceptron is a linear classifier that tells linearly separable binary class data, such as iris setosa vs. iris versicolor via their sepal's length and width.
I'd just like to know if I have 2 groups of photos, one is for dog and the other is for cat, is it possible to train a perceptron to tell if a picture is a dog or cat?

Hello. What do you mean by "iris photos, one is for dog and the other is for cat", if the iris dataset is not a dataset that contains photos of dog and cat? I guess that's a typo, but I just wanted you to clarify this.

I would say in general no, but it depends on the data. If all pictures of dogs have a certain colour etc. and all cats a different colour then they can certainly be separated. A single perceptron is not going to be able to detect shapes though, that's what conv nets are for

It probably is possible but will have 80-90% accuracy while a CNN should get 98% + accuracy.

If you really want to know just follow this tutorial https://machinelearningmastery.com/how-to-develop-a-convolutional-neural-network-to-classify-photos-of-dogs-and-cats/ and make the model a vanilla perception. You'll run into a couple snags though. The perceptron requires a fixed-size set of weights so you'll need to resale the image to something know if you really want to try this.


text:
Does it make sense for a logistic regression model to perform better than a neural network on the Iris data set?
Per a review post, a simple Logistic Regression model on the Iris data set gets about 97% test accuracy on iris dataset whereas a neural network gets just 94%. The neural network model used in Keras is
model = tf.keras.Sequential([
    tf.keras.layers.Dense(500, input_dim=4, activation='relu'),
    tf.keras.layers.Dense(256, activation='relu'),
    tf.keras.layers.Dense(256, activation='relu'),
    tf.keras.layers.Dense(128, activation='relu'),
    tf.keras.layers.Dropout(0.2),
    tf.keras.layers.Dense(128, activation='relu'),
    tf.keras.layers.Dense(3, activation='softmax')
])
model.compile(loss='categorical_crossentropy',
              optimizer='adam',
              metrics=['accuracy'])

The model is fit for 30 epochs using a batch size of 20.
Note that I did try fewer neurons and layers but none of them got better performance.
Does this make sense? Can any other neural network get a higher test accuracy than a logistic regression model?

The most likely explanation is that the neural network model proposed has a much higher model capacity than the logistic regression model.
In fact, the neural network used in the code has 246,343 trainable parameters; the full Iris data set has only 150 samples and only four features – so the model is much more complex than the training data. A neural network model with fewer neurons or layers will likely generalise much better. A logistic regression model is much simpler and has far fewer parameters, so it is in some sense forced to "learn"
better.
The neural network may simply overfit to the training data as the capacity of the model is large enough; an analogous idea is trying to fit a line to data, then trying to fit a degree 100 polynomial. While the polynomial may fit the training
data better, it is less likely to generalise well.
The hyperparameters used in the training of the network might also not be optimal; I haven't experimented, but neural network training can be a little sensitive to the choices made during training.

Thanks for your reply. I did try fewer neurons and layers but none of them got better performance.

Yes, it absolutely makes sense as the Iris dataset is linearly separable (in the sense that linear decision boundaries are near optimal).  This can just about be seen in the scatter plots:

Particularly look at petal width versus petal length, two linear decision boundaries for that pair of variables gives a very low error rate already.  This shouldn't be surprising as the dataset was introduced in a paper by Fisher describing his linear discriminant method (about 1936?).
As @htl (+1) rightly points out, a large neural network has way too much capacity for this problem and will likely overfit.  However you will probably find that a small neural network fares no better than a linear classifier for this problem.
There is a lot of excitement about deep neural networks over the last few years, but they are no better than most existing classifiers for these sorts of benchmark dataset.  They are best (IMHO) for problems with very large datasets, or where convolutional layers are useful.
The comp.ai.neural-nets (an old Usenet news group that we used before the WWW - I trained my first neural net back in 1990) FAQ is well worth a read for anyone wanting to experiment with neural networks.  It contains a lot of folk wisdom that is good to know.  From part 3:

Subject: How many hidden layers should I use?
You may not need any hidden layers at all. Linear and generalized
linear models are useful in a wide variety of applications (McCullagh
and Nelder 1989). And even if the function you want to learn is mildly
nonlinear, you may get better generalization with a simple linear
model than with a complicated nonlinear model if there is too little
data or too much noise to estimate the nonlinearities accurately.

This is excellent advice.
BTW I this case, you might want to try and diagnose the problem by training your neural network on a two-dimensional version of the problem, so that you can plot the decision boundary of the model and see what it is doing.  Sepal Width -v- Sepal Length might be a good choice.  Experimenting with low dimensional problems that can be directly visualised is often very informative.  I Often use Brian Ripley's synthetic dataset in my work because you can easily generate as much data as you could want.


text:
How to prevent update a pretrained model if a model is optimized with backpropagation?
These are components in my model:

A generator
An encoder: a pretrained, and should not updated.
A loss function.

Input is passed to the encoder to generate X, X is then passed to generator to generated a value Y. Y is passed to the encoder to get Z. The loss function computes error between Z and X. I detached X to prevent update the encoder. But I cannot detach Z, otherwise, the generator cannot be updated. But I also realize if Z is not detached then the encoder is also updated.
In the case, how can I prevent the encoder being updated, and still allow the generator get feedback from the loss?

It depends on the framework you use

I used pytorch, and could you explain how it depends on the framework?

according to the rules of this community, programming questions are not allowed, so you better ask your question on StackOverflow. but there are a couple of ways to achieve it. You can disable backpropagation for specific layers or you can call loss.backward() to calc the gradients and optimizer.step() to update the weights for a specific part of your model

You can freeze a model's parameters in pytorch using the following code:
for param in encoder_model.parameters():
    param.requires_grad = False

or you can simply not pass the encoder's parameters to the optimizer
optim = optim.Adam(generator_model.parameters())


text:
GAN with multiple discriminators
I am looking for literature recommendations regarding GANs with multiple discriminators.
In particular, I am looking for examples where each discriminator has a slightly different learning objective, rather than learning on different data. My thinking was that the generator sometimes is exposed to reward sparsity: i.e. its samples get constantly rejected. Having multiple objectives be optimised through multiple discriminators might help alleviate this problem to a certain extent, as it increases the chance of positive feedback from one of the discriminators. Do you know of any examples, and does GAN training with multiple discriminators generally make sense or does it make training more unstable for some reason I have not considered?

As Sadaf pointed out, MD-GAN is a well-known one. But it doesn't have multiple objectives as you wanted.
One GAN architecture that has 2 discriminators, where both have different objectives, is FairGAN, which tries to increase synthetic data fairness by having an additional discriminator which tries to see if the data is fair (supervised on some feature of the data). I personally love the paper, and I think it is along the lines of what you are looking for.
For your question, "Does GAN training with multiple discriminators generally make sense?" Having multiple objectives is not necessarily sensical. For FairGAN, they have 2 objectives, namely 'generating realistic data' and 'generating fair data'. Hence, 2 discriminators makes sense. However, this only works if you have particular data characteristics, such that you can train a second discriminator on that data (because you often need labels). I think that having multiple objectives is only possible in specific situations where you have data which suits such a multi-objective solution. In general, generative models are self-supervised and hence super easily applicable. This is not the case for multi-objective stuff, as the added objective probably needs some data-characteristic.
In a different light, ADS-GAN has the additional objective of generating private data, and does so by adding an additional loss component which can be computed directly using the generated data. This is not an additional discriminator but is an additional objective.
Seeing you specifically mentioned 'rather than learning on different data', I'm assuming you know about PATE-GAN, which employs multiple discriminators to make the generative model have differential privacy by having each teacher discriminator train on a disjoint set of data. (I simply added this for others seeing this later).

Thank you for your thorough reply. Thinking about it, what I actually want to do is pre-train a second generator, D2, on another objective and use it later to give the generator feedback, but freeze the weights of D2. So G and D will alternately learn like usual, but D2 is only there to provide more feedback to G, not to learn by itself. I have two objectives that share a common goal but have a different dificulty level. Do you know of instances where this has been done?

Could you check if you used the terms discriminator and generator correctly everywhere? You say you want to pretrain a generator D2? Im assuming you mean a discriminator? If you pretrain it, (and not during the rest of training), its basically operating as a loss function, so i'd refer you to the ADS-GAN paper i linked.

I meant a second discriminator, my apologies. Once I noticed the mistake I could no longer edit my comment. And thank you, I will have a look at the ADS-GAN paper.

MD-GAN (multi-Discriminator Generative Adversarial Networks for Distributed Datasets ) would be among the ones that you might be looking for. It has been proposed a while ago now.
This has been proposed so that we can utilize high computation over distributed computing.
Most of the work has been done around multiple generators than on discriminators like Mc-GAN,S-GAN,Mg-GAN etc.
The probable reason is, that Discriminators are usually doing good, as their job is mostly classification while Generation is the hard problem, hence most research is around that only


text:
Cheap differentiable similarity metrics of vectors
I am looking to compute the similarity between a large set of vectors during neural network training - a process that is considerably expensive when choosing the wrong metric. So far, I am making use of cosine similarity, but I found that the training gets slowed down by several orders of magnitude because of that. Each batch, I compute batch_size^2 similarities of vectors with 9000 entries containing non-sparse floating-point numbers. Is there an alternative metric to cosine similarity that is much faster but also differentiable?

You probably are not going to get much faster than cosine similarity, the main reason why your calculations are slow is the fact that you execute your operation batch_size$^2$ times which results in a runtime complexity of $O(N^2)$ no matter which metric you choose. However, just to test how much of an improvement you will get by a simpler metric, you might just try the $\infty$-norm: $d(u, v) = \max_i | u_i - v_i |$ or the dot product (i.e. cosine similarity without normalizing the vectors). Just to see whether a simpler metric will actually provide you significant performance improvements.
If you then find out that its not the metric, you can check out Linformer by Wang et al.. As you might know the Transformer architecture also compares N vectors pairwisely. Wang et al. deviced a method how to get memory and time complexity from $O(N^2)$ to $O(N)$. This fits your problem exactly, so maybe it is a good read for you.

Sampling is also a good idea if you can afford missing out on some comparisons - I think the sampling strategy would depend on your usecase. Do you maybe have a prior on the vector similarities which you could use to speed up the process? Can you provide a bit more information on what exactly you want to do? maybe something else comes to mind

Firstly, nice summary of what you are planning - As this is only a sort of regularization term, I think you should easily get away with sampling in this case. However, by minimizing the pairwise distance between the latent vectors, all vectors should move closer together and ultimately approach some point $p$, right?

I wonder if you would get similar behavior by just taking the euclidean vector norms instead of the pairwise stuff. If you do that, all vectors should approach the $0$-vector and thus also move closer together. So in the end, the effect should be the same(?). Doing that would also be linear instead of $N^2$. However, I am not sure I completely understand the idea in general: It's not super intuitive to me why term should promote disentanglement. Since you worked with VAEs, you probably know about $\beta$-VAE? Apparently it generates more disentangled representations.


text:
What are possible reasons for the validation loss increasing with more data?
I trained a neural network on an NLP problem and compared the loss and BLEU score on the validation data with the same training parameters in two scenarios: a) when I trained on 25% of the data, b) when I trained on 100% of the data. I observed a peculiar pattern: the validation loss and BLEU score is much lower in b) as compared to a). What could this mean? My guess is that there are duplicates in the training data, which lead to overfitting, but I still have to investigate that.

As you pointed out, duplicates can be a possible reason for such behavior.
There are a few more possibilities:

Class Imbalance - data is skewed towards a particular class(if you are solving a classification problem).

Model isn't learning well for 100% of data for given parameters. Try changing the learning rate, or adding some constraints such as:

if t == int(args.num_iter * 0.5):
     lr = some_small_value*lr
if t == int(args.num_iter * 0.75):
     lr = smaller_value*lr

It may so happen that the model you have selected is unable to handle weights when input data is large. Try changing the model and see if some other model works better.

I hope this helps.

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Hi, thank you for your answer. I don't have a classification problem, but it's useful to point that out. Your second point simply looks like a learning rate scheduler, which I could indeed implement. I don't know what you mean with 3., though. It seems like rather general advice, so can you specify what you mean by "unable to handle weights when input data is large"?

It's similar to the reason we need LSTM/GRU over RNN. Also, LSTM has some variations like peephole LSTM to further increase the capacity of the model to process data and store weights. It may so happen that your model is as good as an RNN, i.e. it can handle data when its size is less, but as you increase the data, you need a more advanced model such as a LSTM.

I am using GRUs, but I will look into peephole LSTM to understand the difference you are talking about.


text:
Phonetic similarity metric for NLP (English)
I am looking for similarity metrics of phonemes (expressed in IPA) in English. In other words, given two phonemes A and B (both written), I want to know how similar they are based on some metric, M. For example, M(ɒ, oʊ) would yield a higher score than M(æ,ɔɪ).

Distance metrics like Leveshtein or Hamming distance working on IPA phoneme symbols are simply comparing arbitrary symbols; and the phoneme /a/ would be as distant from /b/ as the much closer /p/ would be. Also, most of these metrics only work on sequences of phonemes, not individual phonemes.
What I would do is to describe each phoneme by a feature vector, including

place of articulation (labiar, alveolar, etc)
voiced/unvoiced
type of articulation (plosive, fricative, etc)

You can then use a distance metric on this feature vector to decide how similar phonemes are. For example:

/b/: bilabial, plosive, voiced
/s/: dental, fricative, unvoiced
/p/: bilabial, plosive, unvoiced

A simple binary measure would easily tell you that /b/ and /p/ are closer to each other than /b/ and /s/. A suitable metric to use would be the Dice coefficient.


text:
Predicting the probability of a periodically happening event occurring at a given time
I have encountered this problem on how to predict the probability of a periodically happening event occurring at a given time.
For example, we have an event called being_an_undergrad. There are many data points: bob is an undergrad from (1999 - 2003), Bill is an undergrad from (1900 - 1903), Alice is an undergrad from (1900 - 1905), and there are many other data points such as (2010 - 2015), (2011 - 2013) ....
There are many events(data points) of being_an_undergrad. The lasting interval varies, it might be 1 year, 2 years, 3 years, .... or even 10 years. But the majority is around 4 years.
However, I am wondering given all the data points above. If I now know that Jason starts college in 2021, and how can I calculate/predict the probability that he will still be an undergrad in 2022? and 2023? and 2024 .... 2028, etc.
My current dataset consists of 10000 tuples representing events of different relations. The relations are all continuous relations similar to the example above. There are about 10 continuous relations in total in this dataset, such as isMarriedTo, beingUndergrad, livesIn, etc. For each relation, there are about 1000 data points(1000 durations) about this relation, for example,
<Leo, isUndergrad, Harvard, 2010 - 2011>, <Leo, isUndergrad, Stanford, 2013 - 2016>.....

<Jason, livesIn, US, 1990 - 2021>, <Richard, livesIn, UK, 1899- 1995> ...

My problem now is that I want to get a confidence level(probability) when I want to predict one event happening at a specific time point. For example, I want to predict the probability that event <Jason, livesIn, US, 2068> happens, given:
1.the above datasets which includes info about the relation: livesIn
2.the starting time when Mike lives in US, say he started to live in US since 2030.
I have used normal distribution to simulate, but I am wondering if there are any other better AI / ML / Stats approaches. Thanks a lot!

If the only data you have is samples from population of period lengths, and you want to predict probability of a new randomly sampled one (from the same population), then this looks like a basic question in statistics, which is not really an AI question. If you still think this is an AI question, could you explain where AI is involved? For instance, if there was a lot more contextual data about the time periods, then this might be a suitable problem for machine learning. If that is the case, please use [edit] to explain roughly what contextual data you have.

Hi @NeilSlater! Thanks a lot for your comment. Yup, initially I thought of using statistics approaches such as survival function or poisson distribution. But their accuracy is not that good. Thus, I am thinking of using AI/ML to do the prediction. Actually from my point of view, AI is also like a way of modelling(just like physics/math). For example, we can also use ML/DL to learn the Newton's rules right haha(by inputting lots of experiment data to train the Newton's rule's model). Thus, I was wondering if there are similar time-series approaches in ML/DL that could tackle this problem.

Unless there is some context that you have not explained in your data, a simple statistics approach will get the best accuracy, most ML methods should get close to it but will not be better, and can easily be worse. ML cannot improve on basic probabilities when the prediction is essentially a guessing game.

Advanced AI might even be able to use information such as the student's name, because that may be correlated with demographics that do affect length of the course and likelihood to complete it. It is still not clear from your question that this is what you are asking though.

Hi @NeilSlater! Thank you so much for your very detailed explanation : ) Actually in my context, I have a dataset of continuous relations similar to the example above. There are about 10 relations in total, such as isMarriedTo, beingUndergrad, livesIn, etc. For each relation, there are about 1000 data points about this relation(1000 durations), such as  <Leo, isUndergrad, 2010 - 2011> and <Leo, isUndergrad, 2013 - 2016> ........

Then your dataset could work nicely with a nonlinear ML approach, perhaps xgboost would be good. Please use [edit[ to add a little bit about the dataset, how you intend to use it, plus where you are stuck understanding or using ML. Out of interest, have you used any ML before for other problems?

@NeilSlater Hi Neil! Thanks a lot for your suggestions, I have just done the editing. : ) To be honest, this is actually my first project using ML haha. I am very new to ML haha and I have just started to learn it.


text:
How to prevent machine learning to learn misleading correlations
I am currently training a Random Forest model on about 400 features per instance. The training ROC was about 0.95 which is pretty high I think. However, when visualizing the variable importance of the Random Forest model, I found that the most important features for the models are the availability flags.
That is, since I have some kind of irregular data, I aggregated data with statistical values such as mean, median, and so on. To note whether these values could be calculated in the last observation window, I added a binary flag. That is, if the flag is true, the statistical values are calculated, if the flag is false, the missing values were replaced with 0. Now these flags have a high variable importance, which means that there is some correlation that for class 1 the data is more likely to be present than for class 0.
However, this is not what the model is basing its prediction on, as it is just a percularity of the underlying data collection process. How do you normally deal with this?

If your model learns correlations using data, then those correlations are necessarily in the data. The only way for the model to not learn those correlations is to change your data.
You can either accept that there is a correlation with the flag variable, leading to a high result, or you can just remove the flag from the data you feed to your model. If you do not want the model to learn anything based on the flag, remove the flag altogether.

I see your point. However, removing the data would probably lead to the fact that correlations are learned with the replaced value of missing data. Is it a good idea to randomize these values using for replacement of missing value?

If the imputed missing data is correlating with the end result, your missing data might not be suited for imputation in the simple form in which you did. If there is structurally missing data, you might need to deal with it differently then you did. I recommend looking up 'different types of missing data' and what to do about it.


text:
MicroPython MicroMLP: How do I reward the program based on state?
I have been trying to use MicroMLP to teach a small neural network to converge to correct results.  Ultimately, I want to have three outputs, one which is high priority (X must be as close to XTarget as possible; Y and Z must be within bounds, and should approach YTarget and ZTarget as best as possible).  Right now, I'm just trying to get convergence of one variable to understand this library.
The below code works for xor, but I don't really understand why it works, or how to extend this to reward behavior:
from microMLP import MicroMLP
import utime
import random
import machine
import gc

DEPTH=3
mlp = MicroMLP.Create( neuronsByLayers           = [DEPTH, DEPTH, 1],
                       activationFuncName        = MicroMLP.ACTFUNC_GAUSSIAN,
                       layersAutoConnectFunction = MicroMLP.LayersFullConnect )

nnFalse  = MicroMLP.NNValue.FromBool(False)
nnTrue   = MicroMLP.NNValue.FromBool(True)

led = machine.Pin(25, machine.Pin.OUT)
tl = 0
xor = []
c=0
for i in range(5000):
    if not i % 100:
        led.toggle()
        gc.collect()
        print(" Iteration: %s \t Correct: %s of 10" % (i,c))
        c = 0
    xor.clear()
    xorOut = nnFalse
    for j in range(DEPTH):
        if random.random() > 0.5:
            xor.append(nnTrue)
            xorOut = nnFalse if xorOut == nnTrue else nnTrue
        else:
            xor.append(nnFalse)
    p = mlp.Predict(xor)
    mlp.QLearningLearnForChosenAction(None, xorOut, xor, 0)
    if p[0].AsBool == xorOut.AsBool:
        c += 1

led.off()

print( "LEARNED :" )

c = 0
tries = 0
for i in range(100):
    led.toggle()
    gc.collect()
    xor.clear()
    xorOut = nnFalse
    for j in range(DEPTH):
        if random.random() > 0.5:
            xor.append(nnTrue)
            xorOut = nnFalse if xorOut == nnTrue else nnTrue
        else:
            xor.append(nnFalse)
    tries += 1
    p = mlp.Predict(xor)
    c += 1 if mlp.Predict(xor)[0].AsBool == xorOut.AsBool else 0

print( "  %s of %s" % (c, tries) )

del mlp
print(gc.mem_alloc())
gc.collect()
print(gc.mem_alloc())

I'm trying to achieve two goals, first for me to understand, second for the machine to do useful work.
Goal #1:  learn to adjust a value properly.
Inputs:

Target (0,1)
Value (0,1)

Outputs:

An adjustment toward Value (-1,1)

Possibly this has to be (0,1) so I've considered using the adjustment as adjustment - 0.5 to put it into the (-0.5,0.5) range

I want to reward the thing based on the degree to which value comes closer to the target.  (As a special case, if it's impossible to adjust that far given the output, I want to maximize its reward for making the maximum adjustment.)  I don't want to know the value adjustment should target; I only want to know that whatever value it gave produced a state I like better, and what that value was.  If I can know the correct output, I don't need deep learning.
Goal #2, the later one I expect to be able to do myself if I can get one variable working, is to have several inputs and three outputs.  These inputs relate to the current targets and the deviation from those targets.  One of these is of the highest priority to track toward a target value; the other two should track toward a target value, but are allowed to deviate by some amount with no harm done.  If I can just figure out how to use the neural network, I should be able to assemble that.
Does this sound reasonable?  Is this the correct tool, or is Q-Learning wrong for this?
Feel free to suggest a better package for regular Python as well, although MicroMLP is the only usable one of which I'm aware for the platform I'm targeting.  I'll likely want a much more powerful one that I can use with extra available hardware if present.
If I get something I can work with, I'll write documentation and submit a PR to the MicroMLP repo so nobody has to ask this again.


text:
Optimizer that prevents parameters from oscillating
When we perform gradient descent, especially in an online setting where the training data is presented in a non-random order, a particular 1-dimensional parameter (such as an edge weight) may first travel in one direction, then turn around and travel the other way for a while, then turn around and travel back, and so forth.  This is wasteful, and the problem is that the learning rate for that parameter was too high, making it overshoot the optimal point.  We don't want parameters to oscillate as they are trained; instead, ideally, they should settle directly to their final values, like a critically damped spring.
Is there an optimizer that sets learning rates based on this concept?  Rprop seems related, in that it reduces the learning rate whenever the gradient changes direction.  The problem with Rprop is that it only detects oscillations of period 2.  What if the oscillation is longer, e.g. the parameter is moving in a sine wave with a period of dozens or hundreds of time steps?  Looking for an optimizer that can suppress oscillations of any period length.
Let's be specific.  Say that $w$ is a parameter, receiving a sequence of gradient updates $g_0, g_1, g_2, ... $ .  I am looking for an optimizer that would pass the following tests:

If $g_t = sin(t) - w$, then $w$ should settle to the value 0.
If $g_t = sin(t) + 100 - 100 cos(0.00001t) - w$, then $w$ should settle to the value 100.
If $g_t = sin(t) - w$ for $0 < t < 1000000$, and $g_t = sin(t) + 100 - w$ for $1000000 \leq t$, then $w$ should at first settle to the value 0, and then not too long after time step $1000000$ it should settle to the value 100.
If $g_t = sin(t) - w$ for $floor(t / 1000000)$ even, and $g_t = sin(t) + 100 - w$ for $floor(t / 1000000)$ odd, then $w$ should at first settle to the value 0, then not too long after time step $1000000$ it should settle to the value 100, and then not too long after step $2000000$ it should settle back to 0, but eventually after enough iterations it should settle to the value 50 and stop changing forever after.

This is an old problem that is still an open area of research. SGD with Momentum also tries to solve this issue. The problem is that optimization takes place in a multidimensional space, where each dimension can have a different scale. That is, for each dimension we need its own learning rate. However, batch normalization can mitigate this problem. Take a look at this article


text:
Why does the implementation of REINFORCE algorithm minimize the gradient term but not the loss?
I read the book "Foundation of Deep Reinforcement Learning,  Laura Graesser and Wah Loon Keng", and when I go through the REINFORCE algorithm, they show the objective function:
$$
J\left(\pi_{\theta}\right)=\mathbb{E}_{\tau \sim \pi_{\theta}}[R(\tau)]=\mathbb{E}_{\tau \sim \pi_{\theta}}\left[\sum_{t=0}^{T} \gamma^{t} r_{t}\right]
$$
and the gradient of the objective:
$$
\nabla_{\theta} J\left(\pi_{\theta}\right)=\mathbb{E}_{\tau \sim \pi_{\theta}}\left[\sum_{t=0}^{T} R_{t}(\tau) \nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right)\right]
$$
But when they implement it,
class Pi(nn.Module):
    def __init__(self, in_dim, out_dim):
        super(Pi, self).__init__()
        layers = [
                nn.Linear(in_dim, 64),
                nn.ReLU(),
                nn.Linear(64, out_dim)
        ]
        self.model = nn.Sequential(*layers)
        self.onpolicy_reset()
        self.train()

    def onpolicy_reset(self):
        self.log_probs = []
        self.rewards = []

    def forward(self, x):
        pdparam = self.model(x)
        return pdparam

    def act(self, state):
        x = torch.from_numpy(state.astype(np.float32))
        pdparam = self.forward(x) # (1, num_action), each number represent the raw logits for that specific action
        # model contain the paremeters theta of the policy, pd is the probability
        # distribution parameterized by model's theta
        pd = Categorical(logits = pdparam)
        action = pd.sample()
        log_prob = pd.log_prob(action)
        self.log_probs.append(log_prob)
        return action.item()

def train(pi, optimizer):
    T = len(pi.rewards)
    rets = np.empty(T, dtype = np.float32)
    future_ret = 0.0
    for t in reversed(range(T)):
        future_ret = pi.rewards[t] + gamma*future_ret
        rets[t] = future_ret

    rets = torch.tensor(rets)
    log_probs = torch.stack(pi.log_probs)
    loss = -log_probs*rets
    loss = torch.sum(loss)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()
    return loss

def main():
    env = gym.make('CartPole-v0')
    # in_dim is the state dimension
    in_dim = env.observation_space.shape[0]
    # out_dim is the action dimension
    out_dim = env.action_space.n
    pi = Pi(in_dim, out_dim)
    optimizer = optim.Adam(pi.parameters(), lr = 0.005)
    for epi in range(300):
        state = env.reset()
        for t in range(200): # max timstep of cartpole is 200
            action = pi.act(state)
            state, reward, done, _ = env.step(action)
            pi.rewards.append(reward)
        # env.render(mode='rgb_array')
            if done:
                break
        loss = train(pi, optimizer)
        total_reward = sum(pi.rewards)
        solved = total_reward > 195.0
        pi.onpolicy_reset()
        print(f'Episode {epi}, loss: {loss}, total reward: {total_reward}, solve: {solved}')
    return pi

In train(), they minimize the gradient term, and I can not understand why is that.
Can someone shed light on that?
I am new to this so please forget me if this question is stupid.

Because we want to maximise the objective $J$, i.e we want to maximise expected future returns.

I am sorry for some confusion in the question, where I ask "why do they minimize the gradient but not the loss", but actually they maximize the gradient of the objective. However, the point is why the gradient but not the objective function to be maximized?

They are not maximizing the gradient, the gradient is of the form
\begin{equation}
\nabla_{\theta} J \approx \sum_{t=0}^T G_t \nabla_{\theta} \log(\pi_{\theta}(a_t|s_t))
\end{equation}
that means that when implementing it in software you can form your objective as
\begin{equation}
J = \sum_{t=0}^T G_t \log(\pi_{\theta}(a_t|s_t))
\end{equation}
and then taking the gradient of that objective is equal to the policy gradient.

I appreciate you taking the time to answer my naive question!

@HaoHuynhNhat you should upvote and accept the answer if it has answered your question.

@DavidIreland Yeah thanks for your reminder! this is my first question so I didn't know that!


text:
Bellman Expectation Equation leading to results where value iteration would not converge to the optimal policy
When applying the bellman expectation equation:
$$v(s)=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s\right]$$
to the MRP below, states further away from the terminal state will have the same value ${v(s)}$ as states closer to the terminal states. Even though it is clear that the expected total reward from states further away is lower. If the discount factor $\gamma$ would be even lower states further away would get a higher value. If we now make this an MDP where the agent can decide to go either direction from all states (with the first state having an action leading to itself), the agent would then choose to go further away from the terminal. Getting less reward over the whole episode. So, this seems to be an example where policy/value iteration would not converge to an optimal policy. I know there is something wrong with the reasoning here. I just cannot seem to figure out what.
What am I missing here?

EDIT: So, the problem actually was that I didn't take into account that the terminal state has to get a value of 0. If you put it at 0 at all times this will converge as expected because all the other states will get lower and lower values while, assuming a greedy policy, the one-to-last state will retain a value of -1. After a bit over 10 iterations (if gamma is close to 1) it will converge because the states further away will get a value less than -1.

What am I missing here?

You are not missing anything mathematically.
Potentially what you are missing is that the discount factor $\gamma$, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any action. If you use a discount factor, then it affects the return calculation, which in turn may affect which behaviours are optimal.
If you choose $gamma$ such that an agent would move away from a terminal state to receive the highest expected return, then you have defined the problem such that this behaviour is optimal.
This can be an issue when solving RL problems and you have taken a free choice for reward functions and definition of return (this is quite common, often it is the researcher's problem to set these values up to define the agent's goals). Often you can use a discount factor to make a problem more numerically stable, because it will keep sums of rewards over many time steps within bounds. Also, it can be used as a way to search for faster solutions - i.e. in less time steps to reach episode end - because the agent will prioritise reaching higher values sooner if it can. Your example MDP deliberately puts those two effects in opposition to each other.
Assuming you want the agent to find the terminal state by getting over the larger negative reward just before it: Probably you should not use a discount factor for your MDP. Alternatively, if the reward signal is more of a free choice for that problem, you could offset it (by $+0.1$) and then most values of discount factor will still resolve to reaching the terminal state as optimal behaviour.
There are a few common ways to mitigate or avoid the issue of changing problem definition by selecting $\gamma$:

Use a value of $\gamma$ derived from the problem. In some cases, the value of $\gamma$ is a realistic physical part of a problem. For instance in financial problems, cash now is often preferable to cash later.

Set $\gamma$ to relavtively high value, such as $0.99$ or $0.999$, depending on episode length and relative sizes of rewards. This can work well enough for a wide range of problems. It is a common solution when using DQN. Effectively this approximates the next approach (average rewards) for a low cost.

Use average reward settings. There are separate Bellman equations, TD updates etc based on maximising expected average reward per time step as opposed to maximising expected discounted return.

Thank you for the input. However, I believe with this MDP, value iteration will converge to the optimal policy even with a discount factor of 0. Im not 100% sure yet about 0 but anything above 0 it will converge.

@Paternostro Yes it will converge. But it may be a different optimal policy, because by changing $\gamma$ you have changed what it means to be optimal.

I meant converging to the policy with the highest return. You're right about y changing what is optimal.


text:
Current state of the art and datasets for combining NLP and CV?
I was considering a scenario where natural language processing (NLP) and computer vision (CV) are combined, for example in extended reality systems that get as input both natural language and non-verbal information, e.g. human gestures, and can comprehend it. For example, the agent would get language and non-verbal input and talk to a user.
How could this be realized? My naive guess would be a conditional transformer, where the conditioning happens on the non-verbal input, but I'm not sure how exactly the conditioning could happen. What is a current state-of-the-art model for combining NLP and CV?
Also, are there datasets available for the aforementioned use case? I'm thinking of the scenario where a sentence, e.g.

Yeah, I like him too!

can either mean what is said, and the non-verbal input could be that the person saying it is smiling. However, if the non-verbal input is some laughter, then the above sentence might be meant ironically. Is there any dataset for this, where sentences and non-verbal inputs are combined? (Please note that I'm not talking about the generation of a sentence to an image, I'm referring to a combination of NLP and CV.)
Thanks a lot!

I don't know the answer, but just in case no one else responds, I can tell you where to look. That's called "multimodal sentiment analysis" in the literature, and the answer you're looking for is probably in this Google Scholar search.

Your question is very interesting !
Actually your example is about multimodal sarcasm detection, one of the last paper on this task (as far I know) is Detection of Sarcasm through Tone Analysis on video and Audio files: A Comparative Study On Ai Models Performance (The smallest title of the year)
They create their own dataset using humoristic Youtube video and labelled it manually.
From the title, it seems to be talking about CV but actually, they are using the first 13 dimensions of MFCC thanks to that they get information about prosody, (pitch and tone) and the shape of the vocal tract, the authors add that information to textual data as input to train their models. (LSTM, CNN and Bi-LSTM)
Images/videos are not that used yet in Sarcasm identification.
So, nowadays I think the most achieved combination of NLP and CV is the image text extraction task and its language translation (used in Google Lens for example) which is a combination of Optical Character Recognition and Google Neural Machine Translator.
If you are looking for a dataset to join CV and NLP recently there is VT-SSum: A Benchmark Dataset for Video Transcript Segmentation and Summarization


text:
Is it a good practice to split sparse from dense features?
I have a mixture of real (float) and categorical features to use as input in a neural network. I encode the categorical features using one-hot / multi-hot encoding.
If I want to use all the features as input what is usually/empirically the best practice:

Concatenating all the features - sparse one-hot/multi-hot vectors and float values features - in one vector which is part dense part sparse and using this as input, or

Splitting the sparse one-hot/multi-hot vectors from the dense features and using an extra separate layer for the sparse features to make them dense before concatenating them with the other already dense features.

Same as 2 but maybe using a separate layer for the dense features too so we concatenate "embeddings" instead of features and embeddings.

What, in your experience / opinion, should I do, trial-and-error aside?


text:
How does one handle different player turns in MCTS?
Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree correspond to different player's turns.
So, for instance, in the root node it is Player1's turn to play, in the children of the root node it is Player2's turn to play, in the children of those children it is Player1's turn again, etc.
Is that correct?
If so, is it really prudent to treat nodes where it's the enemy's turn to play the same as those where we choose the next action (i.e. by averaging rollout results in backpropagation). Since, it's not us choosing the next action but the enemy, shouldn't we "pick" the minimum "return" (like in minimax) in those cases instead of the average like we do for nodes where we get to pick the next action?
By picking I mean to only count the win ratio of that child node (i.e. the minimum win ratio).
I suspect I am missing something (e.g. that might mess up exploration vs exploitation with UCT) but I can't put my finger on it.
What do you guys think about this?
Edit: Maybe a solution to this is only considering good moves for the opponent? But then again.. how do we define good? Heuristics?

I think I came up with an intuitively good solution. During the selection phase, if in the current state it's the opponent's turn to play then the winrate in the UCT formula becomes 1.0 - winrate instead. This should make us invest more in good opponent moves rather than bad ones.
I am implementing MCTS for Quoridor at the moment I ll update if it works better or not when I am done.
Edit: Yup, this seems to be the way. Now the tree is symmetrical and we can also generate moves for the opponent as well.

The original (vanilla) MCTS use random rollouts.  In some games this is enough to produce a strong agent.  However, in most of the games, using a heuristic that finds the opponent's likely moves makes stronger agents.  There is another line of practice that uses Opponent Modeling to predict the opponent moves.  That is important in games where you have several opponent "types" or when an opponent can go for different goals.
From my experience, a good heuristic can greatly improve the agent.  I have implemented UCT agents for Spades (the card game).  I made a vanilla UCT and one that uses a different (simpler) agent as heuristic.  The second UCT is stronger.
Picture from wiki:MCTS

The four phases of MCTS:

Selection: Start from root R and select successive child nodes until a leaf node L is reached. The root is the current game state and a leaf is any node that has a potential child from which no simulation (playout) has yet been initiated. The section below says more about a way of biasing choice of child nodes that lets the game tree expand towards the most promising moves, which is the essence of Monte Carlo tree search.

Expansion: Unless L ends the game decisively (e.g. win/loss/draw) for either player, create one (or more) child nodes and choose node C from one of them. Child nodes are any valid moves from the game position defined by L.

Simulation: Complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).

Backpropagation: Use the result of the playout to update information in the nodes on the path from C to R.

Interesting input. I am not talking about the rollout phase though. I am talking about the tree itself.
For example, I believe AlphaGo prunes candidate moves in the tree by only considering moves deemed "worthy" from a neural network. That is, it doesn't fully expand each node based on all possible moves.
Hence it won't consider bad moves for the opponent, therefore avoiding our agent from dreaming that it will ever get to such states (where he would probably win).

Added a picture from wiki that describe the four phases of a MCTS step.  What phase are you asking about?  I think you are talking about the Simulation phase, where the algorithm plays for all the players until it reaches a the game's end and can evaluate the score.

No, I am talking about the selection phase and the moves we consider there on each expansion. Those moves could be all of the legal moves but maybe it should be only good moves to prevent the problem I discuss in my post.

In the selection phase, MCTS choses the node to expand, those nodes are the agent's moves.  I think the problem you talking about is in the Simulation phase, where the algorithm guesses the opponents' moves.

Wiki:MCTS explains the four phases well.  In the Selection phase we only choose a node, then expend it by 1 move (our move), then in the simulation phase we playout to the game's end (only here we consider opponents moves).

To quote your answer Child nodes are any valid moves from the game position defined by L.. Some child nodes are caused by possible opponent moves on a state. These are the moves I am refering to.

No, it is the agent turn to play, all the moves are her to play.  Selection phase will select one of her moves to expend. In the Simulation phase the agent will need to decide what the opponent might do in case we get to that state.

Wait a second. That's what I asked in the beginning. You re saying that in the game tree all the edges correspond to moves from our agent? What about the enemy moves? We can't assume what the enemy will play and continue. We need to expand according to enemy moves as well. I believe that's what the coloring signifies in your picture; whose turn it is to play the next move.


text:
Is the policy gradient expression in Fundamentals of Deep Learning wrong?
I don't understand the policy gradient as explained in Chapter-9 (Deep Reinforcement Learning) of the book Fundamentals of deep learning.
Here is the whole paragraph:
Policy Learning via Policy Gradients

In typical supervised learning, we can use stochastic gradient descent to update our parameters to minimize the loss computed from our network's output and the true label. We are optimizing the expression:
$$
\arg \min _{\theta} \Sigma_{i} \log p\left(y_{i} \mid x_{i} ; \theta\right)
$$
In reinforcement learning, we don't have a true label, only reward signals. However, we can still use SGD to optimize our weights using something called policy gradients. We can use the actions the agent takes, and the returns associated with those actions, to encourage our model weights to take good actions that lead to high reward, and to avoid bad ones that lead to low reward. The expression we optimize for is:
$$
\arg \min _{\theta}-\sum_{i} R_{i} \log p\left(y_{i} \mid x_{i} ; \theta\right)
$$
where $y_{i}$ is the action taken by the agent at time step $t$ and where $R_{i}$ is our discounted future return. A In this way, we scale our loss by the value of our return, so if the model chose an action that led to negative return, this would lead to greater loss. Furthermore, if the model is very confident in that bad decision, it would get penalized even more, since we are taking into account the log probability of the model choosing that action. With our loss function defined, we can apply SGD to minimize our loss and learn a good policy.

The first expression about the loss computed in a network already seems false since the log of a probability is always negative, and taking the $θ$ (weights) for which the expression is minimal doesn't seem right because it would favor very unsure answers.
The same goes with the next expression on policy gradient. A very negative $R_i$ and very unsure $p(y_i)$ would both be big negatives and multiplied together give a big positive value. Since there is a - sign in front of the expression, this would be the best configuration for the argmin. Meaning we are looking for weights in the policy that give highly negative rewards and for highly unsure actions. This just doesn't make sense to me.
Is it just a sign error (or we could just change to argmax)? Or is there more to it?

There is no sign error and we should not change to $\arg\max$. With Policy Gradients I find that it is not useful to think about things such as a 'loss'.
In short, we want to first find the derivative of the RL objective $J(\theta) = v_\pi(s_0)$, where $\pi$ is our policy that depends on some parameters $\theta$. The policy gradient theorem tells us that
$$\nabla_\theta J(\theta) = \mathbb{E}_{a\sim\pi, s\sim\mu}\left[ G_t \nabla_\theta \log\pi(A_t|S_t)\right]\;;$$
where $\mu$ is our state distribution induced by the policy $\pi$ and $G_t$ are the discounted returns.
Now, as we want to maximise our objective $J(\theta)$, we want to perform gradient ascent. That is, our parameters should be updated according to
$$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta)\;.$$
The reason that you will often see the update written as a minimisation problem is because most software is built to minimise functions, rather than maximise. This is not a problem though as finding the maximum of $f$ is just the same as finding the minimum of $-f$. Using this, we can then say our parameters can be updated using gradient descent on the negative of our objective, i.e. we get our parameter update rule to be
$$\theta_{t+1} = \theta_t - \alpha \nabla_\theta (-J(\theta))\;;$$
which is exactly what you have in the book.


text:
What are some strong algorithms for Perfect Information, Deterministic Multiplayer Games?
I have a series of games with the following properties:

3 or more players, but purely non-cooperative (i.e., no coalition forming);
sequential moves;
perfect information;
deterministic state transitions and rewards; and
game size is large enough to make approximate methods required (e.g. $1000^{120}$ for certain problems).

For example, Chinese Checkers, or, for a more relevant example to my work, a multi-player knapsack problem (where each player, in round-robin fashion, can choose without replacement from a set of items with the goal of maximizing their own knapsack value).
Question: what policy improvement operators or algorithms a) converge to optimality or b) provide reasonably strong results on these games?
What have I researched

In a small enough game (e.g., 3-person Nim with (3,4,5) starting board), full tree search is possible.
In a one-person setting, certain exact Dynamic Programming formulations can reduce complexity. For example, in a one-person setting with a small enough knapsack, any standard array-based approach can solve the problem. I'm unsure if or how these "cost-to-achieve" shortest path formulations carry over to multi-player games.
In a one-person setting, policy improvement approaches like rollout algorithms and fortified rollout algorithms have the cost improvement property. I'm unsure if this property carries over to multi-player versions.
Work has been done (for example, this thesis) to demonstrate that Monte Carlo Tree search strategies can generate powerful policies on the types of games I'm interested in. I believe it's been proven that they converge to Nash Equilibrium in two-player perfect information games, but am not aware of any guarantees regarding multiplayer games.
For imperfect information games, Monte Carlo Counterfactual Regret Minimization (e.g. here) is required for any convergence guarantees. Given I am working in a perfect information environment, these seem like overkill.


text:
Do larger numbers of hidden layers have a bigger effect on a classification model's accuracy?
I trained different classification models using Keras with different numbers of hidden layers and the same number of neurons in each layer. What I found was the accuracy of the models decreased as the number of hidden layers increased However, the decrease was more significant in larger numbers of hidden layers. The accuracies refer to the test data and were obtained using k-fold=5. Also, no regularization was used. The following graph shows the accuracies of different models where the number of hidden layers changed while the rest of the parameters stayed the same (each model has 64 neurons in each hidden layer):

My question is why is the drop in accuracy between 8 hidden layers and 16 hidden layers much greater than the drop between 1 hidden layer and 8 hidden layers, even though the difference in the number of hidden layers is the same (8).

In your case the most probable explanation would be the case of overfitting. The model with too many hidden layers have lots of parameters. By means of all these parameters the model is remembering stuff from the training data itself instead of generalizing by learning the useful patterns.
As a rule of thumb if you increase the number of hidden layers more and more at some point model would perform poorly. (I am assuming there is non-linearity in between. In case there is no non-linearity, it doesn't matter how much you stack, it would give the same result because it just boils down to one single layer).
As an experiment, you can try to add regularization and you will see the model won't be performing that bad. Because now model is being punished for being too confident about the things it is remembering. As a result, it won't overfit to the training data.

In general, yes.
Stacking more layers and adding non-linearities will form a better function approximation (neural nets are basically function approximators), and when trained with the current regularization for each layer (such as L2 or L1) will cause your model to learn a better mapping, and hence generalize better.
If you don't regularize, it will overfit.
They are overparameterized, but why they don't overfit more (or in other words, why they generalize so well to unseen data) with increasing number of parameters is an effect that is even yet to be understood by the ML theory community [1]
[1] - https://arxiv.org/abs/1806.11379


text:
How to add prior information when predicting using deep learning models?
Background
I'm building a binary classification model for a pair match problem using CNN, e.g. whether person A1 likes product B1 or not. Model input features are sequence features (text descriptions) of the person and the product. The model accuracy is around 78%. So for a new person, the model can predict the probability whether he likes each product in our dataset.
Problem
The model is good if we know nothing about the person. However, in the real scenario, we already know the new person likes one or two products. We want to predict whether he likes other products. Is there any way to incorporate this prior information to improve the model?
My thought
A simple method would just retrain the model, giving the new person's pair higher sample weight. But we can't do this for each new person.
Any suggestion would be appreciated. Thanks


text:
Relation between discounted MDP and stochastic shortest path problems in RL
I have been reading about discounted MDPs and Stochastic Shortest Path (SSP). I recently came to know (from a friend) that every discounted MDP can be converted to an equivalent SSP but not the other way around. Questions:

Is this claim true? Is the discount factor equal to 1 when the MDP is converted to an SSP?
More generally, what is the relationship between these two problem categories?

Could you provide a reference for where you found this claim?

Yes, the claim sounds really strange - can you provide some references?

My friend told me about it. The proposed reason was as follows: Since discounted MDPs don't have a terminal state, they use discount factor as a proxy to reach the terminal state. I can't wrap my head around it.

@user529295 this "friend" of yours - does he by any chance supervises your PhD?

@Kostya I ain't no PhD student. I happen to learn RL and have a friend who does too.

This is discussed in [1], where the authors provide the following proposition:

If $FH$ is the class of finite-horizon MDPs, $IFH$ the class of
infinite-horizon MDPs and $SSP$ are stochastic shortest-path MDPs,
then
$$ FH \subset SSP \\ IFH \subset SSP $$

Here, SSP stands for "Stochastic Shortest Path", FH for "Finite Horizon", and IFH for "Infinite Horizon" MDPs. The proofs are summarized below:

Basically, you transform a $FH$ MDP into $SSP$ MDP by:

Add timestep as a state variable to every state and adjust the transition and reward function accordingly.
Set every state with a timestep at the horizon as a goal state.

For $IFH$ MDP, the transformation into $SSP$ MDP is done this way:

Add a unique goal state to the MDP that can be reached from every state with any action with probability $\gamma$ (the discount factor). This transition will give 0 reward/cost.
Scale all other probabilities in the transition function by
$(1-\gamma)$.

The chapter concludes that this is why we can focus on developing $SSP$ algorithms. However, some methods may be made more efficient by leveraging specific properties of the subclasses.
[1]: Mausam and Kolobov, Planning with Markov Decision Processes: An AI Perspective, chapter 2, Theorem 2.21

Welcome to AI Stack Exchange. Images of textbooks are not a very useful format. They could be copyright material, and also the site will not index them, or make them accessible to screen readers etc. Could you please paraphrase the relevant content from the book that helps answer the question, and remove the images

I know that if you use a discount factor $0 < \gamma < 1$ you "shrink" the values of expected accumulated costs (or expected accumulated negative reward) so they converge instead of diverging to infinity for histories originated by some policy.
What I'm not convinced is that this would mean that we can convert the discounted MDP to an SSP because, for example, we would have to define what the goal states are.
This paper for example covers some use of discounted SSPs (goal states are necessarily defined), bot not necessarily discounted MDPs (goal states are not necessarily defined).


text:
Why don't we bootstrap terminal state in n-step temporal difference prediction update equation?
In the algorithm below, when $\tau + n \geq T$, shouldn't the algorithm bootstrap with the value of the next state? For instance, when $T=5, \tau=3, \& \; n=2$, we don't bootstrap the sample return with $V_{(\tau+n)}$, i.e., $V_5$ or the terminal state.

Also, on line 4, what do we mean by "can take their index mod $n + 1$"?

Because the value of the terminal state is 0 by definition. There is no further reward to be obtained once you reach the terminal state.


text:
How does n-step Temporal Difference remove the notion of time-step?
How does n-step TD removes the notion of time-step as referenced in Sutton and Barto (2nd edition, Page 163) below?

Another way of looking at the benefits of n-step methods is that they free you from the tyranny of the time step. With one-step TD methods the same time step determines how often the action can be changed and the time interval over which bootstrapping is done. With one-step TD methods, these time intervals are the same, and so a compromise must be made. n-step methods enable bootstrapping to occur over multiple steps, freeing us from the tyranny of the single time step.

Consider the following example.
We know our n-step update equation as: $$V_{t+n}(S_t) = V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)]$$
Now, let $t=0$ and $n=2$. This gives us: $V_2(S_0) = V_1(S_0) + \alpha [G_{0:2} - V_1(S_0)]$.
Before our n-step TD prediction algorithm starts, we initialize with $V_0$. But we use $V_1$. Why? And how do we calculate $V_1$?

It seems to me you're asking 2 distinct questions here. "how do we calculate V1?" and "how does n-step TD removes the notion of time-step?". Please, edit your post to leave just one question per post, although the questions are related to the same topic. Ask the second question in a different post.

Actually, I wanted to use the former question as an example to illustrate actual question I would like to be answered. I edited the question again. If the issue still persists, I'll split the questions into different post.


text:
Can we combine policy evaluation and value iteration steps for solving model-based MDP?
In Sutton & Barto (2nd edition), at the very end on page 83, the following is mentioned:

In general, the entire class of truncated policy iteration algorithms can be thought of as sequences of sweeps, some of which use policy evaluation updates and some of which use value iteration updates.

and this on the beginning of page 84:

max operation is added to some sweeps of policy evaluation.

I understand that the entire class of truncated policy iteration algorithms can be classified as generalized policy iteration (GPI). Also, I know value iteration (VI) is a combination of one sweep of policy evaluation (PE) and one sweep of policy improvement.
My question: What do we mean by combining multiple PE and VI updates in truncated policy iteration?


text:
Is the bias also a "weight" in a neural network?
I'm learning about how neural networks are trained. I understand how a neuron works, backpropagation, and all that. In neurons, there is a clear distinction between a "weight" and a "bias".
$$
Y= \sigma(\text{weight} * \text{input})+ \text{bias}
$$
However, all the sources I've found when you train the network you just adjust the weights. Not the bias.

However, they never mention what the bias should do, which leads me to think that you just merge all weights and biases in a $W$ vector and call it weights, even though there are also biases. Is that correctly understood?

bias is just a simple kind of weight to shift the separation line, it can be imagined as a weight which is connected to input (original or previous layer) of value 1 always

Yes, it is not unusual to omit the bias by adding a neuron which always outputs a constant 1, which will then be multiplied by an appropriate weight to give the same formula as you would get using an explicit bias.
One notable text using this convention is Understanding Machine Learning: From Theory to Algorithms by  Shai Shalev-Shwartz and Shai Ben-David. In section 20.1 there is a diagram of a neural network where a neuron outputting a constant value is added to each layer which you might find helpful.
To understand why this works, suppose the outputs of the previous layer are $u_1, \dots, u_n, u_{n + 1}$, where $u_{n + 1}$ is always $1$. Then a neuron in the next layer (without a bias) computes
$$ \sigma\left(\sum_{i = 1}^{n + 1} w_i u_i \right) = \sigma\left(\sum_{i = 1}^n w_i u_i + w_{n + 1}\right),$$
where $\sigma$ is the activation function. So, the weight $w_{n + 1}$ just serves as the bias because it is multiplied by $u_{n + 1} = 1$.