Answers.Body: <p>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.</p>
  <p>The term i.i.d. stands for &quot;independent and identically distributed&quot;. 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 <em>not</em> 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.</p>
  <p>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 &quot;true&quot; 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.</p>
  <p>You can demonstrate this effect trying to learn any simple function like <span class="math-container">$y = x^2$</span> with <span class="math-container">$x$</span> from <span class="math-container">$-1$</span> to <span class="math-container">$+1$</span>. Training a NN with randomly selected <span class="math-container">$x,y$</span> pairs results in far better results than training it serially with ~2000 records starting <span class="math-container">$(-1.000, 1.000) (-0.999, 0.998) (-0.998, 0.996)$</span> etc</p>
  <blockquote>
  <p>So, why do feed-forward NNs required the i.i.d. assumption but not RNNs?</p>
  </blockquote>
  <p>RNNs do need i.i.d. data, but the &quot;unit&quot; of sampling here is each sequence.</p>
  <hr />
  <p>* By &quot;individually&quot; I mean in terms of how they are used in the training process. A &quot;unit&quot; here is the smallest set of records that leads to a complete measure of loss in your optimisation.</p>
  <p>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(<span class="math-container">$\lambda$</span>) 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.</p>
  <p>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 <span class="math-container">$\lambda$</span> somewhere between 0 and 1 in TD(<span class="math-container">$\lambda$</span>) 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-03T14:23:22.933Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115797/discussion-on-answer-by-neil-slater-why-exactly-do-neural-networks-require-i-i-d).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T01:11:56.257Z
Answers.Text: What do you mean by *piecewise learning method*? ReLU network?
Answers.UserDisplayName: nn0p
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-06T06:58:22.947Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-23T20:35:41.423Z
Answers.LastActivityDate: 2021-04-06T07:01:47.587Z
Answers.LastEditDate: 2021-04-06T07:01:47.587Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Suppose that we have some optimization criterion <span class="math-container">$J(x)$</span>, which we aim to optimize (maybe maximize, maybe minimize), which we can compute for a single example <span class="math-container">$x$</span>. </p>
  
  <p>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:</p>
  
  <p><span class="math-container">$$\sum_{x \in \mathcal{P}} J(x),$$</span></p>
  
  <p>where <span class="math-container">$\mathcal{P}$</span> 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 <span class="math-container">$\theta$</span>:</p>
  
  <p><span class="math-container">$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x).$$</span></p>
  
  <hr>
  
  <p>In practice, we do not have this ideal scenario, we do not have access to the complete population <span class="math-container">$\mathcal{P}$</span>. Often, we find ourselves approximating the population with a (hopefully rather large) dataset <span class="math-container">$\mathcal{D}$</span>. This could be a collection of images like ImageNet, or in (Deep) Reinforcement Learning it could be a large experience replay buffer. <strong>If the dataset <span class="math-container">$\mathcal{D}$</span> is an accurate representation of the complete population's distribution</strong>, we can estimate the gradient of the objective we ultimately care about (computed over the complete population) by the gradient computed over the dataset <span class="math-container">$\mathcal{D}$</span>:</p>
  
  <p><span class="math-container">$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{D}} J(x).$$</span></p>
  
  <p>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. <strong>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)</strong>. </p>
  
  <hr>
  
  <p>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 <span class="math-container">$B$</span>. 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 <span class="math-container">$B$</span>:</p>
  
  <p><span class="math-container">$$\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).$$</span></p>
  
  <p>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; <strong>if it's not an accurate approximation, we're optimizing the wrong objective!</strong> 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. <strong>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</strong>.</p>
  
  <hr>
  
  <p>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?</p>
  
  <p>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.</p>
  
  <hr>
  
  <p>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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-03T14:23:16.267Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115796/discussion-on-answer-by-dennis-soemers-why-exactly-do-neural-networks-require-i).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-23T20:39:08.683Z
Answers.LastActivityDate: 2019-02-24T14:51:25.967Z
Answers.LastEditDate: 2019-02-24T14:51:25.967Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <h2>Short answer</h2>
  <p>One reason why we assume/require i.i.d. data is that <strong>it simplifies the computations</strong>. More specifically, if we assume the samples to be i.i.d., their joint probability is then simplified to a product of marginal probabilities.</p>
  <h2>Long answer</h2>
  <p>In a dataset <span class="math-container">$D$</span>, suppose we have <span class="math-container">$n$</span> samples. We define their joint probability (i.e. the probability of these samples occurring at the same time) as follows</p>
  <p><span class="math-container">$$P(z_1, z_2, \dots, z_n) \tag{1}\label{1}$$</span></p>
  <p>For instance, if each <span class="math-container">$z_i$</span> is binary (i.e. can take one of two values, e.g. <span class="math-container">$0$</span> or <span class="math-container">$1$</span>). Then, to define the probability distribution over all possible values of all <span class="math-container">$z_i$</span>, we need to compute <span class="math-container">$2^n$</span> probabilities (which corresponds to all combinations of the values of all <span class="math-container">$z_i$</span>s).</p>
  <p>More importantly, if the samples are correlated, this probability must be calculated as a product of <em>conditional</em> probabilities (<a href="https://en.wikipedia.org/wiki/Joint_probability_distribution" rel="nofollow noreferrer">by definition</a>).</p>
  <p>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>
  <p><span class="math-container">$$P(z_1, \dots, z_n)=\prod_{i}P(z_i) \tag{2}\label{2}$$</span></p>
  <p>which may be <em>simpler</em> than calculating with conditional probabilities because marginal probabilities may be simpler to compute.</p>
  <h3>Example: binary cross-entropy</h3>
  <p>In the case of a binary classification problem, we assume to have a labelled dataset <span class="math-container">$D = \{(x_i, y_i) \}$</span>, where <span class="math-container">$y_i$</span> would be the binary label (<span class="math-container">$0$</span> or <span class="math-container">$1$</span>) for the corresponding input <span class="math-container">$x_i$</span>. So, we could define our likelihood function parametrized by the parameters <span class="math-container">$w$</span> as follows</p>
  <p><span class="math-container">$$\ell(w) = P(y_1, y_2, \dots, y_n \mid x_1, x_2, \dots, x_n; w) \tag{3}\label{3}$$</span></p>
  <p>If we assume <span class="math-container">$(x_i, y_i)$</span> to be independent of <span class="math-container">$(x_i, y_j)$</span>, for all <span class="math-container">$i \neq j$</span>, 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.</p>
  <p><span class="math-container">$$\ell(w) = \prod_i P(y_i \mid x_i; w) \tag{4}\label{4}$$</span></p>
  <p>For numerical stability (because sums are more stable than products of small numbers), rather than considering the likelihood, we can consider the <em>log-likelihood</em>, which is just the logarithm of <span class="math-container">$\ell$</span>. However, this transforms the product in (\ref{4}) into a sum (note that this is just a rule of logarithms!).</p>
  <p><span class="math-container">$$\log \ell(w) = \sum_i \log P(y_i \mid x_i; w) \tag{5}\label{5}$$</span></p>
  <p>We can also do this because the logarithm is a strictly increasing function, so the maxima/minima of <span class="math-container">$\ell$</span> are attained at the same parameters as the maxima/minima of <span class="math-container">$\log \ell$</span>.</p>
  <p>So, now, the goal is to find the parameters <span class="math-container">$w$</span> 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).</p>
  <p><span class="math-container">$$\text{CE}(w) = - \log \ell(w)$$</span></p>
  <p>So, minimizing the cross-entropy <span class="math-container">$\text{CE}(w)$</span> is exactly the same thing as maximizing the <span class="math-container">$\log \ell(w)$</span>.</p>
  <p>Given that the labels <span class="math-container">$y_i$</span> are binary, we can assume that <span class="math-container">$P(y_i \mid x_i; w)$</span> in (\ref{5}) is a Bernoulli distribution, so we could define the probability that the label is equal to <span class="math-container">$1$</span> (or <span class="math-container">$0$</span>, it's the equivalent) as follows</p>
  <p><span class="math-container">$$P(y_i=1 \mid x_i; w)=\hat{p}^{y_i} (1-\hat{p})^{(1-{y_i})},$$</span></p>
  <p>where <span class="math-container">$\hat{p}$</span> is the output of the neural network <span class="math-container">$f(x_i; w) = \hat{p}$</span> when fed with <span class="math-container">$x_i$</span>, and <span class="math-container">$\hat{p}$</span> is just an estimate of the parameter <span class="math-container">$p$</span> of the Bernoulli distribution we try to learn.</p>
  <p>So, now, our cross-entropy <span class="math-container">$\text{CE}(w)$</span> can be written as follows</p>
  <p><span class="math-container">$$\text{CE}(w) = \sum_i \log \left( \hat{p}^{y_i} (1-\hat{p})^{(1-y_i)} \right) $$</span></p>
  <p>So, now, we just need to estimate <span class="math-container">$w$</span> to produce <span class="math-container">$\hat{p}$</span>. So, basically, we have avoided the computation of conditional probabilities of the labels.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-16T00:39:33.710Z
Answers.LastActivityDate: 2021-10-17T15:15:04.133Z
Answers.LastEditDate: 2021-10-17T15:15:04.133Z
Answers.UserDisplayName: Green Falcon
Body: <p>In reinforcement learning, successive states (actions and rewards) can be correlated. An <a href="http://www.incompleteideas.net/lin-92.pdf" rel="noreferrer">experience replay</a> buffer was used, in the <a href="https://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf" rel="noreferrer">DQN architecture</a>, to avoid training the neural network (NN), which represents the <span class="math-container">$Q$</span> function, with correlated (or non-independent) data. In statistics, the i.i.d. (independently and identically distributed) assumption is often made. See e.g. <a href="https://stats.stackexchange.com/q/213464/82135">this question</a>. <a href="https://qr.ae/TUfiQ2" rel="noreferrer">This</a> 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).</p>
  <p>Mathematically, why exactly do (feed-forward) neural networks (or multi-layer perceptrons) require i.i.d. data (when being trained)? Is this only because <a href="https://www.ijcai.org/Proceedings/07/Papers/121.pdf" rel="noreferrer">we use back-propagation to train NNs</a>? 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.</p>
  <p>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?</p>
  <p>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.</p>
  
Tags: <neural-networks><reinforcement-learning><statistical-ai><experience-replay><iid>
Title: Why exactly do neural networks require i.i.d. data?
UserDisplayName: nbro
ThreadText: # Why exactly do neural networks require i.i.d. data?
  
  (Asked by: username_0 on 2019-02-23)
  
  In reinforcement learning, successive states (actions and rewards) can be correlated. An [experience replay](http://www.incompleteideas.net/lin-92.pdf) buffer was used, in the [DQN architecture](https://web.stanford.edu/class/psych209/Readings/MnihEtAlHassibis15NatureControlDeepRL.pdf), 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](https://stats.stackexchange.com/q/213464/82135). [This](https://qr.ae/TUfiQ2) 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](https://www.ijcai.org/Proceedings/07/Papers/121.pdf)? 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.
  
  **Tags:** neural-networks, reinforcement-learning, statistical-ai, experience-replay, iid
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-02-23. Score: 11
  
  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.
  
  > **Comments:**
  > **username_0**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115797/discussion-on-answer-by-neil-slater-why-exactly-do-neural-networks-require-i-i-d).  
  > **username_2**: What do you mean by *piecewise learning method*? ReLU network?  
  > **username_1**: @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.  
  
  ---
  
  ### Answer by username_3 on 2019-02-23. Score: 8
  
  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).
  
  > **Comments:**
  > **username_0**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115796/discussion-on-answer-by-dennis-soemers-why-exactly-do-neural-networks-require-i).  
  
  ---
  
  ### Answer by username_4 on 2020-11-16. Score: 1
  
  ## 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](https://en.wikipedia.org/wiki/Joint_probability_distribution)).
  
  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.
  
  
  ---
  
  