9
$\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$
10
$\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 '20 at 14:23
  • $\begingroup$ What do you mean by piecewise learning method? ReLU network? $\endgroup$
    – nn0p
    Apr 6 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 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 '20 at 14:23
0
$\begingroup$

The reason is very simple. It is due to the cost function. For instance, for making the binary cross-entropy cost function, we discard the joint probability by considering the i.i.d condition. So we will have products of marginal probabilities. The final result will be the sum that we have in the binary cross-entropy cost function after applying the logarithm.

Update due to the request:

In a dataset, suppose we have n examples. Our goal is to maximize the probability of examples to happen. Consequently, we demand to maximize the following probability:

$P(x_1, x_2, ..., x_n)$

As it can be observed, the joint probability is hard to be interpreted. The point is that it is hard to be calculated. Suppose each example is binary. Then the probability distribution will need $2^n$ number of values to be defined properly.

If we sample the examples i.i.d the above distribution becomes the product of marginal probabilities:

$P(x_1, ..., x_n)=\prod_{i}P(x_i)$

The above probability is far easier to compute. We tend to maximize this probability. Due to the fact that logarithm is a strictly increasing function, we can take the logarithm of the above formula for numerical stability, because while multiplying many numbers, the outcome can become very small or big soon.

On the other hand, we try to minimize the negative of the maximization problem. It is more common among optimization practitioners.

$log P(x_1, ..., x_n)=\sum_i{log(P(x_i))}$

$Cost=-\sum_i{log(P(x_i))}$

This is our goal to maximize the likelihood.


The probability distribution is a Bernoulli distribution for binary classification problems and in neural networks, we demand to find $P(y=1|x)$ for each example:

$P(y=1|x)=\hat{p}^y(1-\hat{p})^{(1-y)}$

where $\hat{p}$ is the output of the network. Our goal is to maximize the probability of all the dataset. Like above, we minimize the cost function which will be like the following:

$cost=-\sum_i{y^{(i)}log(\hat{y}^{(i)}) + (1-y^{(i)})log(1-\hat{y}^{(i)})}$

$\endgroup$
5
  • $\begingroup$ Ok, how does this answer my question that neural networks require i.i.d. data? At most, that answers the question "why is the independence assumption?" useful. I think you can make this answer clearer by just emphasizing this point, i.e. "By making the independence assumption, some of the computations can be simpler. So, in this answer, I am not focusing on how learning proceeds when the i.i.d. assumption is made, but how computations are simplified. Moreover, note that this is just about the independence assumption and not the other i (identically distributed) in i.i.d.". $\endgroup$
    – nbro
    Nov 16 '20 at 12:31
  • $\begingroup$ Something like this sentence should be your first sentence. $\endgroup$
    – nbro
    Nov 16 '20 at 12:33
  • $\begingroup$ @nbro unfortunately your voice is aggressive and hostile. By the way, this is my answer. And as a side note, the cost function will be useful to minimize if we sample our data in a way that we assumed to make the cost function. Your answer was exactly in the first paragraph: "we discard the joint probability by considering the i.i.d condition", and your question: "Why exactly do neural networks require i.i.d. data?" $\endgroup$
    – Media
    Nov 16 '20 at 12:54
  • $\begingroup$ What I was saying is that this answer can be improved significantly (from an explanation/pedagogical point of view), although what you say (about the simplifications of computations) is true. I will upvote it if you improve it as I suggested. For example, you say "As it can be observed, the joint probability is hard to be interpreted". The main problem is not "interpretability", but computation. In fact, that joint probability, without the IID assumption, is computed as a product of conditional probabilities (as opposed to just marginals). That's the main point. $\endgroup$
    – nbro
    Nov 16 '20 at 17:47
  • $\begingroup$ Moreover, as I said, the initial explanation, at the top of your answer, is very unclear (e.g. "we discard the joint probability by considering the i.i.d condition": that's not what we do: we do not discard anything, but we assume the IID, then the joint can be written as a product of marginals; maybe this is just a language problem), though your update clarifies it. Also, your answer applies to any model, in the sense that the IID assumption is not just useful for neural networks, but also e.g. for naive Bayes. $\endgroup$
    – nbro
    Nov 16 '20 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.