14
$\begingroup$

In reinforcement learning, successive states (actions and rewards) can be correlated. An experience replay buffer was used, in the DQN architecture, to avoid training the neural network (NN), which represents the $Q$ function, with correlated (or non-independent) data. In statistics, the i.i.d. (independently and identically distributed) assumption is often made. See e.g. this question. This is another related question. In the case of humans, if consecutive data points are correlated, we may learn slowly (because the differences between those consecutive data points are not sufficient to infer more about the associated distribution).

Mathematically, why exactly do (feed-forward) neural networks (or multi-layer perceptrons) require i.i.d. data (when being trained)? Is this only because we use back-propagation to train NNs? If yes, why would back-propagation require i.i.d. data? Or is actually the optimisation algorithm (like gradient-descent) which requires i.i.d. data? Back-propagation is just the algorithm used to compute the gradients (which is e.g. used by GD to update the weights), so I think that back-propagation isn't really the problem.

When using recurrent neural networks (RNNs), we apparently do not make this assumption, given that we expect consecutive data points to be highly correlated. So, why do feed-forward NNs required the i.i.d. assumption but not RNNs?

I'm looking for a rigorous answer (ideally, a proof) and not just the intuition behind it. If there is a paper that answers this question, you can simply link us to it.

$\endgroup$

3 Answers 3

11
$\begingroup$

There is an assumption behind the theory training a neural network, that also applies to many other supervised learning methods, that a training sample is representative of the data set as a whole - that it has been sampled fairly from the population that the learning algorithm has been set up to approximate.

The term i.i.d. stands for "independent and identically distributed". If you pick trajectories from RL then the sampling (per individual* record as used to train with) is not independent. Even if you choose the start of the trajectory randomly, you will have made one random choice then your remaining choices are made according to the trajectory - technically they are chosen by the policy and environment dynamics over a single step, which is usually not enough to make the second, third etc steps from a trajectory fully independent random samples from the training population. To make the sampled observations independent, you should make a new random choice, and to be identically distributed that choice has to be made fairly over the whole dataset.

If a subset of samples drawn for a mini-batch (or as consecutive individual samples) are correlated for an online algorithm like gradient descent, it causes a problem. For the algorithm to converge towards a globally optimal solution, it needs errors and the gradients they generate to be unbiased samples of the "true" function gradients across the loss function. Whilst correlated data from a trajectory does not do this at all - it exhibits a strong sampling bias, causing weight updates to move consistently in the wrong direction.

You can demonstrate this effect trying to learn any simple function like $y = x^2$ with $x$ from $-1$ to $+1$. Training a NN with randomly selected $x,y$ pairs results in far better results than training it serially with ~2000 records starting $(-1.000, 1.000) (-0.999, 0.998) (-0.998, 0.996)$ etc

So, why do feed-forward NNs required the i.i.d. assumption but not RNNs?

RNNs do need i.i.d. data, but the "unit" of sampling here is each sequence.


* By "individually" I mean in terms of how they are used in the training process. A "unit" here is the smallest set of records that leads to a complete measure of loss in your optimisation.

It is ok to draw longer trajectories at random if your smallest unit of measurable error is from a trajectory, as in Monte Carlo or TD($\lambda$) for RL, or for RNNs. There can be subtle problems with this - the trajectories still have to be i.i.d. as in they represent fair samples from the assumed population of trajectories.

If you are working at the level of longer trajectories, typically this reduces systemic bias: In RL it reduces bias from initial conditions due to bootstrap process. For RNNs I am less sure what this would mean, but suspect there is some equivalent. Typically, it also increases variance, meaning you may need more training samples. There is a bias/variance trade-off, which is why setting $\lambda$ somewhere between 0 and 1 in TD($\lambda$) is often the optimal choice. Note in RL this is a different source of bias and variance than discussed when considering number of parameters and regularisation in supervised learning.

$\endgroup$
3
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – nbro
    Nov 3, 2020 at 14:23
  • $\begingroup$ What do you mean by piecewise learning method? ReLU network? $\endgroup$
    – nn0p
    Apr 6, 2021 at 1:11
  • $\begingroup$ @nn0p: I mean that it learns from a finite set of samples of a target function that have been provided to it. It does appear that the term is used elsewhere for othe rmeanings, so I will change that sentence. $\endgroup$ Apr 6, 2021 at 6:58
8
$\begingroup$

Suppose that we have some optimization criterion $J(x)$, which we aim to optimize (maybe maximize, maybe minimize), which we can compute for a single example $x$.

In an "ideal world", where we have no restrictions on computation time and memory, we would generally want to run training algorithms on the complete "ground truth" population. For example, if we're training a model (may be a DNN, but may also be some other kind of Machine Learning model), we'd ideally train it on the complete population of all "real-world" images that have ever been produced, ever will be produced, or ever could be produced (and, of course, all with accurate labels). We could write our full optimization criterion as:

$$\sum_{x \in \mathcal{P}} J(x),$$

where $\mathcal{P}$ denotes the complete population. If we have a model that we would like to train using gradient descent (such as a Neural Network), this means we have to compute the gradient with respect to some trainable parameters $\theta$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x).$$


In practice, we do not have this ideal scenario, we do not have access to the complete population $\mathcal{P}$. Often, we find ourselves approximating the population with a (hopefully rather large) dataset $\mathcal{D}$. This could be a collection of images like ImageNet, or in (Deep) Reinforcement Learning it could be a large experience replay buffer. If the dataset $\mathcal{D}$ is an accurate representation of the complete population's distribution, we can estimate the gradient of the objective we ultimately care about (computed over the complete population) by the gradient computed over the dataset $\mathcal{D}$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{D}} J(x).$$

Collecting such a dataset rather than the complete population is often actually feasible in practice. If we can afford to compute the objective/gradient over such a complete dataset, that's great. Note that in such a case, the data can already be viewed as being i.i.d.: it's the best approximation we have of a single, complete distribution (the population distribution).


However, computing the objective / gradient over a large complete dataset is often still prohibitively expensive in terms of computation time. This is one of the reasons (not the only one) why we often use minibatches $B$. Then, we approximate the gradient of the objective of the dataset (which is itself an approximation of the gradient for the complete population) by computing it only over a minibatch $B$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{D}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{B}} J(x).$$

If we're repeatedly (over many, many training iterations) going to use such an approximation to take gradient descent steps, it is crucial that the gradient computed over this minibatch is actually an accurate approximation of the "true" gradient over the complete population; if it's not an accurate approximation, we're optimizing the wrong objective! In my opinion, this means that we have an even stronger requirement for our minibatch than just wanting it to be identically distributed. It's not sufficient for our minibatch to be sampled from any arbitrary identical distribution. We want the instances in our minibatch to be sampled from one very specific identical distribution; the dataset/population distribution! If they're not all sampled from that particular distribution, they're an unreliable approximation of the objective we truly care about.


Now, you may wonder if it wouldn't be possible for multiple biased, "unrepresentative" minibatches with "opposite" biases to "cancel each other out" if they're used in different, subsequent gradient descent steps. Couldn't we first run a bunch of gradient descent steps on minibatches that only contain images of dogs, and afterwards "cancel out" any errors by also running a bunch of updates on minibatches containing only images of cats?

If you're lucky, it might work sometimes, but it's unreliable. One problem is that the first iterations using only dog images may cause you to end up in a poor area of the "parameter space", which you would never have ended up in if had used a correct mix of cat and dog images all along. Escaping that poor area may be much more difficult than simply ensuring you never reach it. Another problem is that it would be extremely difficult to find the "correct" number of gradient descent updates to run with cat images. Run too few, you're still stuck recognising only dogs. Run too many, and you may forget how to recognise dogs at all and only start recognising cats. Things like momentum in more sophisticated optimizers will exacerbate this issue.


Note that I don't think the requirement for i.i.d. batches is necessarily unique to gradient descent. Other learning techniques may have the same requirement (maybe for similar reasons, maybe for different reasons).

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – nbro
    Nov 3, 2020 at 14:23
1
$\begingroup$

Short answer

One reason why we assume/require i.i.d. data is that it simplifies the computations. More specifically, if we assume the samples to be i.i.d., their joint probability is then simplified to a product of marginal probabilities.

Long answer

In a dataset $D$, suppose we have $n$ samples. We define their joint probability (i.e. the probability of these samples occurring at the same time) as follows

$$P(z_1, z_2, \dots, z_n) \tag{1}\label{1}$$

For instance, if each $z_i$ is binary (i.e. can take one of two values, e.g. $0$ or $1$). Then, to define the probability distribution over all possible values of all $z_i$, we need to compute $2^n$ probabilities (which corresponds to all combinations of the values of all $z_i$s).

More importantly, if the samples are correlated, this probability must be calculated as a product of conditional probabilities (by definition).

However, if the samples are i.i.d., then the join probability in equation (\ref{1}) can be computed as a product of marginal probabilities

$$P(z_1, \dots, z_n)=\prod_{i}P(z_i) \tag{2}\label{2}$$

which may be simpler than calculating with conditional probabilities because marginal probabilities may be simpler to compute.

Example: binary cross-entropy

In the case of a binary classification problem, we assume to have a labelled dataset $D = \{(x_i, y_i) \}$, where $y_i$ would be the binary label ($0$ or $1$) for the corresponding input $x_i$. So, we could define our likelihood function parametrized by the parameters $w$ as follows

$$\ell(w) = P(y_1, y_2, \dots, y_n \mid x_1, x_2, \dots, x_n; w) \tag{3}\label{3}$$

If we assume $(x_i, y_i)$ to be independent of $(x_i, y_j)$, for all $i \neq j$, then this joint probability (\ref{3}) of labels given the inputs can also be written as a product of the marginals of the labels given the inputs.

$$\ell(w) = \prod_i P(y_i \mid x_i; w) \tag{4}\label{4}$$

For numerical stability (because sums are more stable than products of small numbers), rather than considering the likelihood, we can consider the log-likelihood, which is just the logarithm of $\ell$. However, this transforms the product in (\ref{4}) into a sum (note that this is just a rule of logarithms!).

$$\log \ell(w) = \sum_i \log P(y_i \mid x_i; w) \tag{5}\label{5}$$

We can also do this because the logarithm is a strictly increasing function, so the maxima/minima of $\ell$ are attained at the same parameters as the maxima/minima of $\log \ell$.

So, now, the goal is to find the parameters $w$ of the log-likelihood such that the probability of the samples is maximized. Equivalently, rather than maximizing the log-likelihood, we can minimize its negative (this is what is usually done in practice!), which leads to what people call the cross-entropy function (which is just the negative log-likelihood).

$$\text{CE}(w) = - \log \ell(w)$$

So, minimizing the cross-entropy $\text{CE}(w)$ is exactly the same thing as maximizing the $\log \ell(w)$.

Given that the labels $y_i$ are binary, we can assume that $P(y_i \mid x_i; w)$ in (\ref{5}) is a Bernoulli distribution, so we could define the probability that the label is equal to $1$ (or $0$, it's the equivalent) as follows

$$P(y_i=1 \mid x_i; w)=\hat{p}^{y_i} (1-\hat{p})^{(1-{y_i})},$$

where $\hat{p}$ is the output of the neural network $f(x_i; w) = \hat{p}$ when fed with $x_i$, and $\hat{p}$ is just an estimate of the parameter $p$ of the Bernoulli distribution we try to learn.

So, now, our cross-entropy $\text{CE}(w)$ can be written as follows

$$\text{CE}(w) = \sum_i \log \left( \hat{p}^{y_i} (1-\hat{p})^{(1-y_i)} \right) $$

So, now, we just need to estimate $w$ to produce $\hat{p}$. So, basically, we have avoided the computation of conditional probabilities of the labels.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .