Concepts / True Error and Empirical Error

True Error and Empirical Error

Zero empirical error means that the hypothesis has no observed error on the training set. It does not mean that the hypothesis has zero true error.

  • Programming
Interactive lab

Try it: Empirical Risk Minimization

How ERM picks the hypothesis in a finite class H with the smallest empirical risk on a random sample , how far its true risk can be from , how often ERM misses ε over many samples compared with the finite-class sample-complexity bounds, and how a richer class trades approximation error for estimation error until memorising the sample overfits.

How it works

  1. D is known: x is uniform over n points in [0, 1] and its label is a target rule f (a threshold or an interval), flipped with probability η; so every can be computed exactly.
  2. Draw : independent labelled examples from a seeded random stream.
  3. For every h in H (thresholds or intervals on a grid, listed in order), count its mistakes on S to get , and compute its true risk from . For the class of all functions, ERM simply memorises S: the majority label at each seen point, 0 elsewhere.
  4. ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
  5. Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
  6. Run the same samples through richer and richer classes: falls, the average rises, and memorising (all functions) reaches small with a large .

Default run (16 steps): D: x uniform over 20 points in [0, 1], label f(x) = 1[x >= 0.4] flipped with probability η = 0.1. H = thresholds on the grid i/10, |H| = 11. The learner never sees D; it gets S ~ Dm with m = 20. … Richer classes on the same 200 samples: ε_app falls from 0.42 (thresholds, k = 1) to 0.1 (all functions), while the average ε_est rises to 0.2282 for all functions (average LS 0.0617). Lowest average LD(hS): thresholds, k = 5 (0.1136).

Simplified: A toy domain of 8-40 equally likely points on a line, a target that is a threshold or an interval, and symmetric label noise, so is an exact finite sum rather than an integral over a continuous distribution. Hypotheses are thresholds or intervals with endpoints on a grid i/k, or all functions on the n points. ERM ties are broken towards the first hypothesis in listing order (for all functions: towards label 0), where the textbook allows any minimiser. Failure frequencies come from at most 400 seeded samples, so they estimate the probability rather than compute it; the bounds use the natural logarithm.

Educational simulation

Loading the simulation…

The Training-World Trap

A hypothesis can perform perfectly on the training set and still perform poorly on examples from the true data distribution. This is the central warning of overfitting: success on the observed sample does not necessarily mean success in the true world.

Training sampleobserved examplesHypothesisperformance can differTrue datadistributiontrue-world examplesevaluates observed performanceevaluates true-world performance
What is contained in the finite training sample, what belongs to the underlying data distribution, and where can a hypothesis behave differently?
Definition

Overfitting is a mismatch between excellent training performance and poor true-distribution performance.

Two Ways to Measure Performance

Empirical error describes how a hypothesis performs on the observed training set. True error describes how that hypothesis performs on the true data distribution. The two measures can disagree because excellent performance on the training sample does not guarantee excellent performance in the true world.

h_Sone hypothesisEmpirical error0True error1/2training performancetrue-distribution performance
How can a hypothesis classify every training example correctly while still making errors on examples drawn from the true data distribution?
Key point

Zero empirical error means that the hypothesis has no observed error on the training set. It does not mean that the hypothesis has zero true error.

A Perfect Training Score

Worked example

The h_S Example

Interpret the case in which the empirical error of h_S is 0 while its true error is 1/2.

  1. 1
    Read the empirical error

    The value 0 means that h_S has no error on the training set.

  2. 2
    Read the true error

    The value 1/2 means that h_S has nonzero error on the true data distribution.

  3. 3
    Compare the two results

    The hypothesis is perfect on the observed training data but performs poorly on the true distribution.

  4. 4
    Name the pattern

    This mismatch is overfitting.

Result

Training success alone is not enough to establish good true-distribution performance.

h_Sone hypothesisTraining seterror 0True distributionerror 1/2performanceperformance
Which performance pattern indicates that h_S fits the observed training examples but performs poorly on unseen examples from the true distribution?

Why ERM Can Overfit

An empirical risk minimization algorithm selects a hypothesis because it minimizes empirical error. Its selection is therefore based on performance measured on the training data. If a hypothesis has the lowest observed training error but poor performance on the true data distribution, ERM may select that overfitting hypothesis.

Candidatehypothesesmultiple choicesEmpirical errortraining dataLowest observed errorselection criterionSelected hypothesismay overfitcomparerank observed errorchoose
How does empirical risk minimization compare candidate hypotheses and select one with the lowest observed training error even when that hypothesis has higher true error?
Key point

ERM may choose an overfitting hypothesis not because its true error is lowest, but because its empirical error is lowest.

Following the Mismatch

To recognize overfitting, compare the hypothesis's performance on the training data with its performance on the true data distribution. The overfitting pattern appears when training performance is excellent while true-distribution performance is poor.

Training errornot yet minimizedTraining error0True errornot specifiedTrue error1/2fit training sampleevaluate true distribution
What changes as a model fits the training sample more closely, and how can empirical error and true error differ?
Best practice

Whenever a training result looks excellent, ask a second question: how does the hypothesis perform on the true data distribution? This comparison is necessary for detecting the mismatch that defines overfitting.

Mistakes in Error Interpretation

  • Common mistake

    Treating zero empirical error as zero true error.

    What it looks like

    A hypothesis has empirical error 0, so it is described as error-free everywhere.

    Why it fails

    The zero applies to the training set, while true error concerns the true data distribution.

    Do this instead

    State precisely which error is zero and check the other measure separately.

  • Common mistake

    Assuming the hypothesis selected by ERM must have the lowest true error.

    What it looks like

    ERM selects the hypothesis with the lowest observed training error, so that hypothesis is declared best in the true world.

    Why it fails

    ERM minimizes empirical error, and the source example shows that empirical success can coexist with nonzero true error.

    Do this instead

    Describe ERM's selection criterion as empirical error and avoid equating it automatically with true-distribution performance.

  • Common mistake

    Ignoring the difference between the observed sample and the true data distribution.

    What it looks like

    A result on the training examples is treated as a result on all examples from the true distribution.

    Why it fails

    Overfitting is precisely the mismatch between these two performance settings.

    Do this instead

    Name the evaluation setting whenever you report a performance result.

Check Your Interpretation

EASY

A hypothesis has empirical error 0 and true error 1/2. What does this tell you about its training performance, its true-distribution performance, and whether the pattern is overfitting?

Hints
  • Interpret empirical error using the training set.
  • Interpret true error using the true data distribution.
  • Compare the two results before naming the pattern.

What do you think happens?

If ERM selects a hypothesis with the lowest empirical error, can that selected hypothesis still be overfitting?

  • Yes

  • No

Reveal answer
Answer:

Yes

ERM minimizes empirical error, but the selected hypothesis can still have poor performance on the true data distribution.

Key Takeaways

  1. 1
    Empirical error concerns performance on the observed training set.
  2. 2
    True error concerns performance on the true data distribution.
  3. 3
    Overfitting is the mismatch between excellent training performance and poor true-distribution performance.
  4. 4
    A hypothesis can have zero empirical error and nonzero true error, as in the example with true error 1/2.
  5. 5
    ERM may select an overfitting hypothesis because it minimizes empirical error.

At a glance

  • Empirical error and true error measure performance in different settings.
  • Zero empirical error does not guarantee zero true error.
  • Overfitting occurs when training performance is excellent but true-distribution performance is poor.
  • ERM can select an overfitting hypothesis because its selection is based on empirical error.
  • The pattern L_S(h_S) = 0 and L_D(h_S) = 1/2 demonstrates why training success alone is not enough.

More concepts starting with T