Realistically, does the i.i.d. assumption hold for the vast majority of supervised learning tasks?

Question

The i.i.d. assumption states:

We are given a data set, $\{(x_i,y_i)\}_{i = 1, \ldots, n}$, each data $(x_i,y_i)$ is generated in an independent and identically distributed fashion.

To me, physically this means that we can imagine that the generation of $(x_i,y_i)$ has no affect on $(x_j,y_j)$, $j \neq i$ and vice versa.

But does this hold true in practice?

For example, the most basic machine learning task is prediction on MNIST dataset. Is there a way to know whether MNIST was generated in an i.i.d. fashion? Similarly for thousands of other data sets. How do we "any practitioner" know how the data set is generated?

Sometimes I also see people mentioning shuffling your data to make the distribution more independent or random. Does shuffling tangibly create benefit as compared to a non-shuffled data set?

For example, suppose we create a "sequential" MNIST dataset contained digits arranged in an increasing sequence 1,2,3,4,5,6,..obviously, the data set was not generated in an independent fashion. If you generate 1, the next one must be 2. But does training a classifier on this data set has any difference as compared to a shuffled dataset?

Just some basic questions.

Answer 1

The operational meaning of the IID condition is given by the celebrated "representation theorem" of Bruno de Finetti (which, in my humble opinion, is one of the greatest innovations of probability theory ever discovered). According to this brilliant theorem, if we have a sequence $\mathbf{X}=(X_1,X_2,X_3,...)$ with empirical distribution $F_\mathbf{x}$, if the values in the sequence are exchangeable then we have:

$$X_1,X_2,X_3, ... | F_\mathbf{x} \sim \text{IID } F_\mathbf{x}.$$

This means that the condition of exchangeability of an infinite sequence of values is the operational condition required for the values to be independent and identically distributed (conditional on some underlying distribution function). The theorem can be applied in both Bayesian and classical statistics (see O'Neill 2009 for further discussion), and in the latter case, the empirical distribution is treated as an "unknown constant" and so we usually drop the conditioning notation. Among other things, this theorem clarifies the requirement for "repeated trials" in the frequentist definition of probability.

As with many other probabilistic results, the "representation theorem" actually refers to a class of theorems that apply in various different cases. You can find a good summary of the various representation theorems in Kingman (1978) and Ressel (1985). The original version, due to de Finetti, established this correspondence only for binary sequences of values. This was later extended to the more general version that is the most commonly used (and corresponds to the version shown above), by Hewitt and Savage (1955). This latter representation theorem is sometimes called the de Finetti-Hewitt-Savage theorem, since it is their extension that gives the full power of the theorem. There is another useful extension by Diaconis and Freedman (1980) that establishes a representation theorem for cases of finite exchangeability --- roughly speaking, in this case the values are "almost IID" in the sense that there is a bounded difference in probabilities from the actual probabilities and an IID approximation.

As the other answers on this thread point out, the IID condition has various advantages in terms of mathematical convenience and simplicity. While I do not see that as a justification of realism, it is certainly an ancillary benefit of this model structure, and it speaks to the importance of the representation theorems. These theorems give an operational grounding for the IID model, and show that it is sufficient to assume exchangeability of an infinite sequence to obtain this model. Thus, in practice, if you want to know if a sequence of values is IID, all you need to do is ask yourself, "If I took any finite set of values from this sequence, would their probability measure change if I were to change the order of those values?" If the answer is no, then you have an exchangeable sequence, and hence, the IID condition is met.

Answer 2

Yes, samples in the dataset may not be completely iid, but the assumption is present to ease the modelling. To maximize the data likelihood (in almost all models this is explicitly or implicitly part of the optimization), i.e. $P(\mathcal{D}|\theta)$, without the iid assumption, we'd have to model the dependence between the data samples, i.e. the joint distribution and you won't be able to quickly write the following and maximize:$$P(\mathcal{D}|\theta)=\prod_{i=1}^nP(X_i|\theta)$$

Typically, with lots of samples (random variables), the slight dependencies between small set of samples will be negligible. And, you end up with similar performances (assuming the dependence is modelled correctly). For example, in Naive Bayes, not necessarily the samples but features/words are surely dependent. They're part of the same sentence/paragraph, written by the same person etc. However, we model as if they're independent and end up with pretty good models.

The shuffling is an another consideration. Some algorithms are not affected by shuffling. But, algorithms using gradient descent are probably affected, specifically neural networks, because we don't train them indefinitely. For example, if you feed the network with all $1$'s at first, then $2$'s etc, you'll go all the way to the place where those $1$'s lead you, then try to turn back to the direction where $2$'s lead you and then $3$'s etc. It might end up in plateaus and hard to go back to other directions etc. Shuffling enables you to go in every possible direction a little bit, without going deeper and deeper in some dedicated direction.

Answer 3

For me, the notion of what i.i.d really is and why it is, in many cases, a necessary assumption makes more sense from the Bayesian perspective. Here, instead of data being thought of as i.i.d in an absolute sense, they are though of as conditionally i.i.d. given model parameters.

For instance, consider a normal model from the Bayesian perspective. We specify how we think data were sampled given the parameters:

$X_i|\mu, \sigma^2 \stackrel{iid}{\sim} N(\mu, \sigma^2)$ for $i \in \{1, \ldots, n\}$,

and express prior belief on those parameters:

$\mu \sim P(\mu)$; $\sigma^2 \sim P(\sigma^2)$ (the exact prior used is unimportant).

Conditional independence has to do with the fact that the likelihood factorizes:

$P(X_1, \ldots, X_n|\mu, \sigma^2) = P(X_1|\mu, \sigma^2)\ldots P(X_n|\mu, \sigma^2)$.

But this is not the same thing as saying that the marginal distribution on the data implied by our model factorizes:

$P(X_1, \ldots, X_n) \neq P(X_1)\ldots P(X_n)$.

And, indeed, in our specific case of the normal distribution, getting the marginal distribution on the data by integrating out the parameters indeed yields a joint distribution which is not independent in general, the form of which will depend on which priors you specified.

That is to say: two observations $X_i$ and $X_j$ are not independent; they are only conditionally independent given the model parameters (in math notation, $X_i \perp \!\!\! \perp X_j | \mu, \sigma^2$ but $X_i \not\perp \!\!\! \perp X_j$).

A useful way to think about what the independence of two random variables means is that they do not provide any information about each other. It would be completely absurd to say that two data points don't provide any information about each other: of course the data are related in some way. But by making data conditionally independent given some parameters, we are saying that our model encodes the whole of the relationship between the data: that there's "nothing missing" from our model.

Effectively, an i.i.d. assumption is an assumption that our model is correct: if we are missing something from our model, data will contain information about one another beyond what is encoded in our model. If we know what that is, we should put it into our model and then make an i.i.d. assumption. If we don't know what it is, we are out of luck. But that we have mispecified the model is a constant and unavoidable risk.

And finally, a short note: at first glance, this framework I've described wouldn't seem to fit models such as spatiotemporal models where we have explicit dependence between data hard coded into the model. However, in all cases like this that I am aware of, the model may be reparameterized as one with i.i.d. data and additional (possibly correlated) latent variables.