Training Error

Training error is the error made by a classifier over the particular training sample available to the learner.

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

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 ~ D^{^m} 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 L_{_S} 0.0617). Lowest average L_{_D}(h_{_S}): 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 Learner’s Available Evidence

A learning algorithm must produce a predictor from a training set. The training set is sampled from an unknown distribution and labeled by an unknown target function. Because the learner cannot directly inspect the entire source distribution or the target function, it cannot directly measure the predictor’s error in the complete data-generating situation. It can, however, inspect the training examples it was given.

Key point

Training error is the error made by a classifier over the particular training sample available to the learner.

Which information can the learner inspect to calculate training error, and which information needed for true error is unavailable?

What Training Error Measures

Definition

Training error measures the error made by a classifier on its training sample. The phrase on its training sample is essential: this is a sample-based measurement, not a statement about the classifier’s error everywhere.

The learner has access to the training examples and their labels, so it can check how the classifier performs on those examples. This makes training error observable and calculable. The broader error that would be measured with respect to the unknown data distribution and unknown target function is not directly available to the learner.

Measurement	What it uses	What the learner can do
Training error	The classifier’s errors over the training sample	Calculate it from available information
True error	The broader data-generating situation involving the unknown distribution and target function	It is not directly available

Training error is tied to observed training examples, while true error concerns information the learner cannot directly inspect.

Selecting a Predictor by Sample Error

Empirical Risk Minimization, or ERM, uses the training sample as evidence for comparing predictors. The learner evaluates the errors that candidate predictors incur on that same sample and favors the predictor with the minimum measured error. This describes the selection criterion; it does not claim that every learning algorithm searches through candidates by one identical mechanical procedure.

How does a learner evaluate several candidate predictors on the same training examples and select the one with the fewest mistakes?

Worked example

Comparing Three Candidate Predictors

A learner evaluates three candidate predictors on the same training sample. Predictor A makes 4 measured errors, Predictor B makes 1 measured error, and Predictor C makes 3 measured errors. Which predictor does ERM favor?

1
Measure
The learner evaluates each candidate on the available training sample.
2
Compare
The measured errors are compared using the same sample as evidence for every candidate.
3
Select
Predictor B has the minimum measured error among the three candidates.

Result

ERM favors Predictor B because it incurs the fewest errors on the training sample.

Sample Error Versus Broader Error

What is the difference between counting mistakes on the observed training sample and measuring mistakes over new examples from the unknown data distribution?

Training error and true error answer different questions. Training error asks how many errors the classifier incurs on the particular training sample. True error concerns the broader situation associated with the unknown data distribution and target function. Since the learner cannot directly inspect that full situation, it cannot directly minimize true error. ERM instead uses the measurable sample-based error as its selection criterion.

What do you think happens?

A classifier has the fewest measured errors on the training sample. What can the learner conclude immediately?

That the classifier has the fewest errors everywhere
That the classifier has the fewest measured errors on that training sample
That the unknown target function has been fully identified

Reveal answer

Answer:

That the classifier has the fewest measured errors on that training sample

Training error is tied to the supplied sample. The learner can use it to compare predictors on that evidence, but true error involving the unknown distribution and target function is not directly available.

Names for the Same Sample-Based Idea

You may encounter empirical error and empirical risk used interchangeably with training error. In this context, these terms refer to the error that a classifier incurs over the training sample. The terminology does not change the practical question: how many errors does the classifier make on the finite sample available to the learner?

How are training error, empirical error, and empirical risk related when describing a predictor’s mistakes on a finite sample?

Mistakes About What It Proves

Common mistake
Treating training error as the classifier’s error everywhere.
What it looks like
The classifier made few mistakes on the supplied training sample, so it must make few mistakes in the entire data-generating situation.
Why it fails
Training error is specifically the error over the training sample. It is not directly available information about the full unknown distribution and target function.
Do this instead
State the conclusion narrowly: the classifier made few measured mistakes on that training sample.
Common mistake
Saying that ERM directly minimizes true error.
What it looks like
ERM chooses the predictor with the smallest error under the unknown data distribution.
Why it fails
The learner cannot directly inspect the full source distribution or the target function.
Do this instead
Say that ERM selects a predictor by minimizing its measured error on the training sample.
Common mistake
Treating the training set as irrelevant after the predictor is selected.
What it looks like
The selected predictor is independent of which training set was supplied.
Why it fails
A predictor produced through learning depends on the training set supplied to the algorithm.
Do this instead
Remember that the training set is the evidence used to compare predictors and influences the predictor produced.
Common mistake
Assuming training error, empirical error, and empirical risk are three unrelated measurements in this context.
What it looks like
The learner must calculate three separate kinds of sample error.
Why it fails
The source uses empirical error and empirical risk as terms often interchangeable with training error.
Do this instead
Treat them here as related names for the classifier’s error over the training sample.

Check Your Understanding

MEDIUM

Explain in your own words why a learner can calculate training error but cannot directly calculate true error. Then describe how ERM uses training error to choose between two candidate predictors.

Hints

Begin with the information contained in the training sample.
Mention the unknown data distribution and target function.
End by identifying which candidate has the minimum measured error on the sample.

Your attempt (not saved)

Worked example

Classifying the Measurement

A statement says: A classifier makes two mistakes on the examples supplied to the learning algorithm. Is this a statement about training error or true error?

1
Locate the evidence
The statement refers to examples supplied to the learning algorithm, so it refers to the training sample.
2
Identify the measurement
The classifier’s mistakes over that training sample are the training error.
3
Check the scope
The statement does not describe the classifier’s error over the unknown data distribution and target function.