In which scenarios are the in-sample error and training error NOT the same?

Question

In Elements of Statistical Learning, Chapter 7 (pages 228-229), the authors define the optimism of the training error rate as:

$$ op\equiv Err_{in}-\overline{err} $$

With the training error $\overline{err}$ defined as: $$ \overline{err} = \frac{1}{N}\sum_{i=1}^{N}{L(y_i,\hat{f}(x_i))} $$

And the in-sample error $Err_{in}$ defined as: $$ Err_{in} = \frac{1}{N}\sum_{i=1}^{N}{E_{Y^0}[L(Y_{i}^{0},\hat{f}(x_i))|\tau]} $$

They also specify that:

The $Y^0$ notation indicates that we observe N new response values at each of the training points $x_i, i = 1, 2, . . . ,N$.

It is counterintuitive that $\overline{err}$ and $Err_{in}$ are not always the same, but according to the text and to this answer, this is because the response $Y_0$ is not deterministic and can change from one realization to another.

This makes sense in the abstract, but in practice I don't get it. All of the supervised learning methods (regression models, NNets, SVM, Tree based methods,...) I can think of will, after training, return the same output for the same input. Any randomness will come from the initial values of the model + the output of the training, but once the training is complete, the model is deterministic. In fact, a model which returned a non deterministic output based on the same input seems to defeat the purpose of supervised learning and would be very hard to manage in production.

Under which scenarios does the output of a trained model have a random component? Are there any specific algorithms for which this is the case?

Answer 1

Let’s take simple linear regression as a working example. The model is $y = \beta_0 +\beta_1 x + \epsilon$ . Now imagine the existence of an infinity of possible observations. You do not observe them, but they exist. In this infinity of possible observations there are many of them which for the same $x$ you notice a different $y$, this happens due to errors $epsilon$ which are independent of $x$. Again, they exist but you do not observe them.

Now you have a training sample. On fitting the line you get some betas and some training errors. The average of those errors is denoted with $\bar{err}$. These is the mean of residuals and you can measure it.

Now imagine what would have happened if you would have been received a different set of observations which by chance would have same set of x as in training sample. The y for this new hypothetical sample would be the same? Maybe yes, but most of the time not. Remember that from that infinity of possible set of observations you can get different y on same x. In the new hypothetical sample the new y, denoted with $Y_0$ is a random variable. The average errors for this new hypothetical sample is in sample error. In sample because you have same set of values for x. The in sample error is not observed, thus can’t be computed. But the concept is there and because is a statistic it can be more or less approximated.