True Error
ERM selects a predictor by minimizing its error on the training sample.
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
- 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.
- Draw : independent labelled examples from a seeded random stream.
- 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.
- ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
- Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
- 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.
Loading the simulation…
The Learner's Information Problem
A learner wants a prediction rule that makes few errors on the labeled points it may encounter. The difficulty is that the learner does not directly know the entire probability distribution D that produces examples, and it does not directly inspect the unknown target function that supplies their labels. Instead, the learning algorithm receives a training set S. That sample is the evidence available for comparing prediction rules.
Two Sources for Measuring Error
The same prediction rule h can be evaluated in two related ways. True error, also called risk, asks how likely h is to make an error on labeled points drawn according to the probability distribution D. Empirical risk evaluates h using the training data S. The prediction rule is the object being evaluated; D and S are the different sources used for that evaluation.
True error, or risk, is the error of a prediction rule h evaluated with respect to labeled points drawn according to the probability distribution D.
Why Training Data Becomes the Substitute
The learner cannot directly minimize true error because D is unknown. It does, however, have access to S and can inspect how a prediction rule performs on the training examples. Empirical risk is therefore the training-data measure used to compare prediction rules. This does not change the learner's goal: the desired outcome remains a prediction rule with low true error.
Empirical risk is the prediction error of a rule h evaluated using the available training data S.
ERM Selection on One Sample
Comparing Two Candidate Rules
Suppose the same training set S is used to evaluate two candidate prediction rules, h1 and h2. The training observations show fewer errors for h1 than for h2.
- 1Use the same evidence
Evaluate both h1 and h2 on the same training set S. The training set is the evidence supplied to the learner.
- 2Measure each rule
Determine the prediction errors made by h1 on S and the prediction errors made by h2 on S. These produce the empirical-risk measures for the two rules.
- 3Apply the ERM criterion
Because h1 has fewer measured errors on S in this example, ERM favors h1 over h2.
- 4Keep the distinction visible
This selection is based on empirical risk. It does not mean that the learner directly measured either rule's true error with respect to the unknown distribution D.
ERM selects the candidate with the minimum measured error on the training sample; in this generated example, that candidate is h1.
Labels and Prediction Rules
A training set is sampled from an unknown distribution and labeled by an unknown target function. A prediction rule h makes predictions for the examples. Its error is determined by comparing those predictions with the labels carried by the examples. The learner can use these observed comparisons on S, but it cannot directly inspect the complete target function or the complete source distribution.
Common Confusions
Common mistake Treating training error as true error
What it looks likeA rule makes few errors on S, so the learner concludes that its error with respect to D must also be known.
Why it failsTraining error is observable on S, whereas true error is defined with respect to labeled points drawn according to the unknown distribution D.
Do this insteadCall the training-data measure empirical risk and reserve true error, or risk, for evaluation with respect to D.
Common mistake Saying that ERM directly inspects D
What it looks likeERM chooses a rule by examining the entire probability distribution.
Why it failsThe learner does not know D and cannot directly use knowledge of it.
Do this insteadExplain that ERM uses the accessible training set S to compare predictors.
Common mistake Confusing the target function with the learned predictor
What it looks likeThe prediction rule h is described as the unknown function that labeled the training data.
Why it failsThe source distinguishes the unknown target function that labels the sample from the predictor produced by the learning algorithm.
Do this insteadKeep the roles separate: the target function supplies labels, while h is the prediction rule being evaluated.
Common mistake Claiming that every learning algorithm performs the same candidate search
What it looks likeERM is described as requiring every algorithm to list and mechanically test all possible predictors.
Why it failsThe ERM criterion concerns which measured error is favored; it does not claim that every algorithm follows one identical search procedure.
Do this insteadState the criterion without adding a specific search mechanism: predictors are judged by their error on the training sample, and ERM favors the minimum.
Check Your Understanding
A learning algorithm receives a training set S and compares two prediction rules, hA and hB. hA has the smaller measured error on S. Explain which rule ERM favors, identify whether this comparison uses true error or empirical risk, and state what additional quantity the learner would ideally like to minimize but cannot directly access.
Hints
- Start with the source used for the comparison: S or D.
- ERM favors the candidate with the minimum measured error on the training sample.
- The desired but unavailable measure is the rule's error with respect to the unknown distribution D.
What do you think happens?
A learner can calculate a rule's error on S but does not know D. Which measure can it directly use to compare candidate rules?
Reveal answer
Empirical risk
Empirical risk evaluates prediction error using the training data S, which the learner has. True error is evaluated with respect to the unknown distribution D.
Key Takeaways
- 1True error, or risk, evaluates a prediction rule h with respect to labeled points drawn according to the probability distribution D.
- 2Empirical risk evaluates the same kind of prediction rule using the available training data S.
- 3The learner wants low true error but cannot directly inspect the unknown distribution D or target function.
- 4ERM uses the training set as evidence, compares candidate predictors by their measured errors on S, and favors the predictor with the minimum empirical risk.
- 5Training error and true error are related measures, but they must not be treated as the same quantity.
At a glance
- True error measures how a prediction rule performs with respect to labeled points from the unknown distribution D.
- Empirical risk measures prediction error using the training set S available to the learner.
- The learner wants to minimize true error but directly accesses only training-data evidence.
- Empirical Risk Minimization selects or favors the predictor with the smallest measured error on the training sample.
- The target function supplies labels, while the learned prediction rule h is evaluated against those labels.