Apparent Error Optimism and Its Corrections

Why Resubstitution Error Is Often Too Small

A discriminant rule is fitted to labelled observations and then used to assign classes to new cases. If its error is measured on those same observations, the rule is being judged on data that helped determine its boundaries, coefficients, or selected variables. This resubstitution error can therefore understate the error expected on future observations. The size of that gap depends on the fitting procedure and the data-generating distribution; it is not a universal constant.

The distinction is important even when a rule has a familiar form, such as linear or quadratic discriminant analysis. The apparent error is a property of the fitted rule and its training sample. Prediction risk is a property of that fitted rule evaluated against a fresh observation from the target population. Because both the rule and its training errors are random, these quantities must be defined before their difference can be studied.

Definition: Let $D_n=(Z_1,\ldots,Z_n)$, where $Z_i=(X_i,Y_i)$ are independent and identically distributed observations from a population $P$. A fitting algorithm produces a classifier $g_{D_n}$. With zero-one loss $\ell(g,(x,y))=\mathbf{1}\{g(x)\ne y\}$, its apparent error is $$ \widehat R_{\mathrm{app}}(D_n)=\frac{1}{n}\sum_{i=1}^n \ell(g_{D_n},Z_i). $$ Its conditional prediction risk is $$ R(P,g_{D_n})=E_{Z\sim P}\!\left[\ell(g_{D_n},Z)\mid D_n\right], $$ where $Z$ is a fresh observation, independent of $D_n$. The expected optimism is $O_n=E[R(P,g_{D_n})-\widehat R_{\mathrm{app}}(D_n)]$.

The conditional risk describes performance for the particular fitted classifier, while $O_n$ averages the difference over repeated training samples. Positive optimism means the apparent error is smaller on average than the conditional prediction risk. The term “optimism” does not itself assert that this difference is positive for every algorithm or every distribution.

An Exact Identity for Expected Optimism

The following identity makes the source of the gap explicit. Assume the fitting rule and loss are measurable, and that the loss is integrable; zero-one loss automatically satisfies this condition. Let $Z_i'$ be an independent draw from $P$, also independent of the training sample. The same fitted rule is evaluated once on an independent replacement observation and once on the training observation it helped fit.

Theorem: Under the conditions above, $$ O_n=\frac{1}{n}\sum_{i=1}^n E\!\left[\ell(g_{D_n},Z_i')-\ell(g_{D_n},Z_i)\right]. $$ If the training observations are identically distributed and the fitting procedure treats their indices symmetrically, all $n$ terms have the same expectation, so $O_n=E[\ell(g_{D_n},Z_1')-\ell(g_{D_n},Z_1)]$.

Proof. Conditional on $D_n$, each $Z_i'$ has distribution $P$ and is independent of the fitted rule. Consequently, $E[\ell(g_{D_n},Z_i')\mid D_n]=R(P,g_{D_n})$. Taking expectations and averaging gives $$ E[R(P,g_{D_n})]=\frac{1}{n}\sum_{i=1}^n E[\ell(g_{D_n},Z_i')]. $$ By the definition of apparent error, $$ E[\widehat R_{\mathrm{app}}(D_n)]=\frac{1}{n}\sum_{i=1}^n E[\ell(g_{D_n},Z_i)]. $$ Subtracting these two equalities proves the stated identity. Under index symmetry and identical sampling, each paired expectation is equal, which gives the final expression. $\square$

The identity is exact, but it is not by itself a numerical correction: its expectation depends on the population and on how the fitting algorithm responds to its training data. It also explains why there is no general theorem that optimism must be positive. Training an algorithm to improve its performance on the observed sample tends to make the in-sample loss unusually low, but other procedures or distributions can yield zero or even negative expected differences.

Worked Example: A Fitted Linear Rule With No Class Signal

Let $n=2$. Each response $Y_i$ and each of two predictors $X_{i1},X_{i2}$ takes values $-1$ and $+1$, independently with probability $1/2$; all these variables are mutually independent. Thus neither predictor contains information about the class. Fit a linear classifier by choosing the predictor with the largest absolute training association and choosing its orientation to agree with that association.

For predictor $j$, write $S_j=\sum_{i=1}^2Y_iX_{ij}$. Select $J$ to maximize $|S_j|$, breaking ties by choosing the smaller index, and set the orientation to $\operatorname{sign}(S_J)$, using $+1$ when $S_J=0$. The fitted rule is $g_{D_2}(x)=\operatorname{sign}(S_J)x_J$. Its number of training errors is $(2-|S_J|)/2$, so $$ \widehat R_{\mathrm{app}}=\frac{1}{2}-\frac{\max(|S_1|,|S_2|)}{4}. $$

For each $j$, the two products $Y_iX_{ij}$ are independent fair signs. Hence $S_j$ is $2$ or $-2$ with probability $1/4$ each, and is $0$ with probability $1/2$. The two sums are independent: conditional on the responses, the predictor columns are independent, and each column produces this same distribution, which does not depend on the response values. Thus $|S_j|=2$ with probability $1/2$; the maximum is $2$ unless both absolute sums are zero, an event of probability $1/4$. Therefore $$ E[\max(|S_1|,|S_2|)]=2\left(1-\frac14\right)=\frac32, \qquad E[\widehat R_{\mathrm{app}}]=\frac12-\frac{3/2}{4}=\frac18. $$

For a fresh case, the selected predictor and orientation are fixed given the training data, but its value is an independent fair sign and the fresh response is another independent fair sign. The probability of disagreement is therefore $1/2$, conditional on every training sample. So $R(P,g_{D_2})=1/2$ and $O_2=1/2-1/8=3/8$. The large gap here results from choosing among predictors using the same two observations on which error is reported.

Analytical Corrections and Their Assumptions

An analytical optimism correction adds an estimate of the expected gap to the apparent error: $$ \widehat R_{\mathrm{corr}}=\widehat R_{\mathrm{app}}+\widehat O. $$ The identity above says what $O_n$ is, not how to know it from one data set. In a tractable model, one may calculate optimism from the assumed population and the full fitting procedure. More commonly, a model-based correction substitutes estimated population parameters into a formula or approximation for optimism. Either approach relies on assumptions about the sampling distribution and the fitting process. If those assumptions poorly describe the data, the correction can be inaccurate even when its algebra is correct.

The no-signal example gives an exact correction when its specified population is known: add $3/8$ to the observed apparent error on average. In applications, the population is not known, and the expected optimism will generally not be available in closed form. An estimated correction should therefore be understood as an estimate, not as a guaranteed repair. In particular, a correction derived for a fixed rule does not automatically account for searching over predictors, selecting a model, or adjusting tuning choices using the same data.

Worked Example: Applying a Known Analytical Correction

In the no-signal setup above, suppose a particular training sample gives $S_1=2$ and $S_2=0$. The selected classifier has no training errors, so its apparent error is $0$. Under the stated population and algorithm, the expected optimism is $3/8$. The corrected estimate of prediction risk is therefore $$ \widehat R_{\mathrm{corr}}=0+\frac38=\frac38. $$

This value is a corrected estimate for that observed sample, not the conditional risk of its fitted classifier. In this example the conditional risk is exactly $1/2$, as shown above. The correction equals the expected gap across repeated samples; it need not equal the gap for each individual sample. Confusing these two claims would overstate what an expected-optimism result establishes.

Independent Test-Set Error

An independent test set offers a direct alternative. Fit the rule using $D_n$, then evaluate it on $m$ new observations $Z_1^*,\ldots,Z_m^*$ drawn independently from the target population and independently of the training data. Define $\widehat R_{\mathrm{test}}=m^{-1}\sum_{k=1}^m\ell(g_{D_n},Z_k^*)$. The rule is random before training, but conditional on the training data it is fixed. That conditioning gives a simple justification for the test estimate.

Theorem: If the test observations are independent draws from $P$ and are not used to fit or select the classifier, then $$ E[\widehat R_{\mathrm{test}}\mid D_n]=R(P,g_{D_n}),\qquad \operatorname{Var}(\widehat R_{\mathrm{test}}\mid D_n) =\frac{R(P,g_{D_n})[1-R(P,g_{D_n})]}{m}. $$

Proof. Conditional on $D_n$, each test loss is an independent Bernoulli random variable with success probability $R(P,g_{D_n})$, since it equals one precisely when the fitted rule misclassifies the test case. The conditional expectation of their average is therefore $R(P,g_{D_n})$. The variance of each Bernoulli loss is $R(P,g_{D_n})[1-R(P,g_{D_n})]$; independence makes the variance of the average $1/m$ times this quantity. $\square$

Worked Example: Reading a Test-Set Estimate

Suppose a fitted discriminant rule makes $40$ errors among $200$ independent test observations. Then $\widehat R_{\mathrm{test}}=40/200=0.20$. Treating the fitted rule as fixed, the estimated standard error is $$ \sqrt{\frac{0.20(1-0.20)}{200}}=\sqrt{0.0008}\mathrel{\approx}0.0283. $$ A rough normal-approximation interval is $0.20\pm1.96(0.0283)$, or approximately $0.145$ to $0.255$. This describes sampling uncertainty in the test error for this fitted rule; it does not account for variation from drawing a different training sample or for a test sample that fails to represent the target population.

How to Choose and Interpret an Estimate

A model-based correction and an independent test estimate answer related but not identical practical needs. A correction can use the training sample efficiently, but its accuracy rests on its model and on whether it accounts for the actual fitting procedure. A test estimate avoids the need to calculate the expected optimism under a specified model, but it uses a finite sample and can be imprecise. Both target performance on a stated population; neither makes the target population irrelevant.

Worked Example: Comparing Two Estimates

Suppose a fitted rule has apparent error $0.12$. A model-based calculation estimates optimism as $0.06$, producing corrected error $0.18$. On a separate test set of $200$ observations, the rule makes $40$ errors, giving test error $0.20$. The two estimates differ by $0.02$, which is small relative to the test estimate's approximate standard error of $0.0283$ from the preceding calculation.

This agreement is reassuring but does not prove that either estimate is exact: the model-based correction may be misspecified, and the test estimate fluctuates. If the test set had also been used to choose the classifier, its independence condition would fail, and its error could itself become optimistic. The data used for evaluation must remain separate from any decisions whose performance is being reported.

Common Mistakes and Practical Implications

Calling apparent error the classifier's risk. The apparent error is computed on observations used for fitting. Risk averages loss on a fresh draw from the target population.
Assuming optimism is always positive. Fitting and selection often make apparent error too low, but the exact identity is a difference of expectations and gives no universal sign guarantee.
Adding a correction as if it were exact for each sample. An expected-optimism correction targets an average gap. The gap for a particular fitted classifier can differ.
Treating an independent test estimate as error-free. It is conditionally unbiased under the stated sampling conditions, but has finite-sample variability and may not represent the intended population.
Reusing evaluation data for model decisions. If test results guide fitting or selection, the test observations are no longer independent evaluations of a fixed rule.

Key takeaway: Resubstitution error is not an independent assessment of a fitted discriminant rule. Expected optimism is the expected loss difference between a fresh observation and a training observation under the same fitted rule. Correct it only with a method whose assumptions match the fitting process, or assess the fixed rule on genuinely independent test data and report its sampling uncertainty.

Check Your Understanding

Use the definitions and results above to explain your reasoning.

Why is conditional prediction risk defined using a fresh observation independent of the training sample?
State the exact expected-optimism identity and explain the role of the independent replacement observation.
In the no-signal example, why does selecting the predictor with the strongest observed association reduce apparent error without reducing test accuracy?
Does an expected optimism correction have to equal the optimism for each training sample? Explain.
What independence conditions make the test-set error conditionally unbiased for the fitted rule's risk?