How can we get small test error reducing only train error?

Question

My question is about mathematical part of machine learning algorithms, especially about using it in neural networks. We train network reducing train error and I was thinking about how then test error is also small (discarding overfitting and underfitting), what is mathematical proof for it. I found about that in this book http://www.deeplearningbook.org, chapter 5.2. Here is a part of that chapter:

How can we affect performance on the test set when we can observe only the training set? The field of statistical learning theory provides some answers. If the training and the test set are collected arbitrarily, there is indeed little we can do. If we are allowed to make some assumptions about how the training and test set are collected, then we can make some progress. The training and test data are generated by a probability distribution over datasets called the data-generating process. We typically make a set of assumptions known collectively as the i.i.d. assumptions. These assumptions are that the examples in each dataset are independent from each other, and that the training set and test set are identically distributed, drawn from the same probability distribution as each other. This assumption enables us to describe the data-generating process with a probability distribution over a single example. The same distribution is then used to generate every train example and every test example.

I want to transfer this theoretical part to a more concrete example for better understanding. Assume we have images and we need to select train and test datasets. My questions are

1. What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?
2. I totally can't understand why we need to do this assumption: "the examples in each dataset are independent from each other". Maybe I misunderstood the example part in my first question and it's come from that.
3. If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Also, I would be glad if you will give me some references to read about this in other books/topics.

Answer 1

Well, I have to say that the question is rather complicated. I also spent considerable time investigating this issue. Other SE questions (see here, here and here) are strongly related to this one and specially this answer is very enlightening but, at least for me, not completely satisfactory. Also bare in mind that I am an ANN expert, not a statistician. So, here goes my attempt:

What we really want when we train a learning algorithm is that it can generalize well, that means, being able to perform well in unseen examples. The problem is that we have a finite set of collected examples, e.g., pictures where cats or dogs can be present. So, we have here a contradiction, if we want to assess generalization we need unseen examples, but we have only seen examples, namely, the ones we collected. The solution to this contradiction is that we cannot assess generalization, period. But maybe we insist that we do want to assess generalization because we can split the examples we collected in seen examples (we will call these training set) and unseen examples (we will call these test set). Now the problem became (hopefully) more concrete, and the question is:

How do we split the examples, such as the training set can be a good simulation of the seen examples and the test set can be a good simulation of the unseen examples?

At this point, we can start answering your concrete questions. The easiest is

1. What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?

Answer: Yes, every example, that is, every image is a random variable (RV). In my favorite AI book (AIMA), page 708, first paragraph, says exactly that: "Each example data point (before we see it) is a random variable". The same book explains intuitively what a RV is, so we can check if every cat/dog image is indeed a random variable. Let us see: a RV has a domain (the set of possible values it can take on), the domain of the RV example 1, $X^{(1)}$ is $\{cat, dog\}$ and so is the domain of every other example $X^{(i)}$.

Now that we know that we are dealing with random variables, we can continue with our discussion. Let us say we split randomly the collected examples in train and test set. Is the test set that we obtain a good simulation of unseen examples? Not with certainty. For example, let us say our collected examples are mostly images of our cat and one image of the neigbor's dog, i.e, $\{cat, cat, cat, dog, cat\}$ and we obtain (because we had really bad luck) a training set $\{cat, cat, cat, cat\}$ and a test set $\{dog\}$. Obviouly, our learning algorithm will generalize terribly bad: for all instances will predict the wrong class. So, we need more assumptions if we want to have some guaranties.

This is the point where the independence and identically distributed (i.i.d.) come in play. Rather than explaining what that means, I will image scenarios where these assumptions are violated and see what happens. This will help us to answer your second question.

Scenario 1: The examples in the dataset are not mutually independent. That means there are at least two examples that are mutually dependent. We can use here the same argument as above to dissection this scenario:

After splitting, the train set contains the two related examples, but in the test set all other examples are not related to eachother. We do not want this because the test set is not a very good simulation of the unseen examples.

After splitting, the test set contains the two related examples, but in the train set all other examples are not related to each other. We do not want this because the train set is not a very good simulation of the seen examples. Note that a good simulation of the seen examples would be a set that includes some degree (if not the exactly) of relation between the related examples.

Therefore, the only way we can be sure that the split produces the best seen/unseen split is assuming that all examples are independent of each other. That way, we know that no matter how we split our collected examples, we will always have a perfect method to assess generalization.

The above, I think, answers your questions:

How can we get small test error reducing only train error?

2. I totally can't understand why we need to do this assumption: "the examples in each dataset are independent of each other". Maybe I misunderstood the example part in my first question and it's come from that.

We HOPE that we can get small test error by reducing the train error because we HOPE (actually is our goal) that the algorithm is going to generalize well, and we ASSUME that our examples are independent of each other, so we HOPE that, if we reduce the training error, the test error will be reduced as well, since we have ruled out with our independence assumption, a source of error from both sets.

So let us continue with of your third question:

If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Firstly, you have here a misconception (I have to say this is where my understanding starts to diminish, just like you). Not the train and test set are identically distributed, but again the examples in those sets. This completes the i.i.d. assumptions: the examples are identically distributed. This is extremely abstract.

Intuitively, this means that the collected examples must be of similar nature. In one of the answers I early mentioned, the example of students being tested in a class is given:

The kids also need to be "identically distributed", so they cannot come from different countries, speak different languages, be in different ages since it will make it hard to interpret the results (maybe they did not understand the questions and answered randomly).

It appears to me that the matter has not been really grasped. Neither in the deep learning book, nor in AIMA or other probability/statistics books, we can find a natural explanation or treatment. But perhaps this could helps us:

Let us suppose we want to estimate the mean $\mu$ and variance $\sigma^2$ of a Gaussian distribution. Our collected examples are supposed to be drawn from this distribution $X^{(i)} \sim N(\mu, \sigma^2)$. Every example $X^{(i)}$ is distributed according to that specific distribution, that is, they are identically distributed. If we collect examples drawn from another normal with mean $\mu_1$ and variance $\sigma^2_1$ or from another distribution whatsoever, e.g, uniform distribution, we will definitely have problems when assessing generalization. So, we have to assume that our collected examples are indeed identically distributed.

Finally, the 10% and 90% has no theoretical background! The number 10 and 90 do not represent any distribution, it is just what all people do, most like a fashion. You can use 20%/80%, 30%/70% and even 40%/60%. Of course, intuition dictates that we should use most of the data we have to train and the rest to test. Following the example of the students, you want to teach the students most of the time and, eventually examine them, but not the other way around.

Answer 2

Yes, if you are classifying images, each example would be an image. There is some distribution on images that are likely to arise in practice.

We need independence and identical distributions because without it we can't learn. If we practice five times, but then are tested on something entirely different, our practice might not be useful.

The distribution refers to the distribution of each single image. That has nothing to do with how many images you draw from that distribution. Imagine flipping a biased coin. I could flip the coin 100 times; each outcome would be a sample from that (biased) distribution, and that's true whether we have 10 coin flips or 1000 coin flips.