Hypothesis Classes and VC-Dimension
Approximation error measures the gap between the best hypothesis in a class and the true hypothesis.
Two Sources of Error
When a learned model performs poorly, its error can come from at least two different sources. The hypothesis class may be unable to represent the underlying relationship well. This is approximation error. Alternatively, the class may be capable of representing a good relationship, but the learning process may select a poor hypothesis because it learned from only a finite sample. This is estimation error. Separating these possibilities matters because they suggest different remedies.
The Class Before Learning
A hypothesis class is the collection of hypotheses that the learning procedure is allowed to consider. Approximation error asks a class-level question: how close is the best hypothesis in that class to the true hypothesis? It does not ask how well the particular hypothesis eventually selected performed on the training sample. A class can therefore have a limitation even before any finite data is used for learning.
Training and Validation Evidence
Separating the Learned Model from the Class
Suppose a learning procedure selects one hypothesis from a hypothesis class. The selected hypothesis has low risk on the training sample, but its validation risk is much larger. What does this evidence suggest?
Identify the two measurements: Training risk is measured on the sample used to fit the hypothesis. Validation risk is measured on a validation set rather than relying only on that training sample.
Compare the risks: A large gap between empirical risk and true risk is associated with overfitting. Validation provides information about how the learned hypothesis performs outside the training sample.
State the limitation: This evidence concerns the selected hypothesis. It does not directly reveal how close the best member of the entire hypothesis class is to the true hypothesis.
The pattern is evidence about the learned hypothesis and is consistent with estimation error or overfitting. It is not, by itself, a direct measurement of approximation error.
Validation is useful because it evaluates the learned hypothesis on data outside the training sample. The source states that the difference between distribution risk and validation risk can be bounded quite tightly using Theorem 11.1. Thus, validation helps assess the true risk of the learned hypothesis. It does not automatically reveal the performance of the best possible member of the class, so it cannot by itself directly estimate approximation error.
Risk Patterns as Complexity Changes
Training risk and the empirical-to-true-risk gap provide diagnostic evidence, but neither is necessarily a direct estimate of approximation error. A large empirical risk indicates underfitting in the source's diagnostic pattern. A large gap between empirical risk and true risk indicates overfitting. These patterns describe the learned model's behavior; they do not directly answer what the best member of the hypothesis class could achieve.
Selecting a Remedy
A useful diagnosis begins by asking whether the evidence points to a class limitation or to a poor hypothesis selected from the class. Large empirical risk suggests underfitting and makes approximation-related limitations plausible, although it does not directly measure approximation error. A large empirical-to-true-risk gap suggests overfitting and estimation error caused by learning from a finite sample. The remedy should follow the diagnosis rather than relying only on whether training risk is high or low.
Use validation to assess the learned hypothesis, compare training and validation behavior, and keep the class-level question separate. If the learned hypothesis has high training risk, investigate whether the available class is too limited or otherwise unable to represent the relationship well. If training risk is low but the validation or true-risk evidence is much worse, investigate overfitting and estimation error. Neither diagnosis should be treated as a direct numerical estimate of approximation error.
Common Diagnostic Mistakes
Treating low training risk as proof of low approximation error.
Training risk concerns the selected hypothesis on one finite sample, while approximation error concerns the best member of the class compared with the true hypothesis.
Fix:
Use validation to assess the learned hypothesis, and keep the class-level approximation question separate.Calling every poor result underfitting.
A large empirical-to-true-risk gap is associated with overfitting, not with the large empirical risk pattern associated with underfitting.
Fix:
Compare training evidence with validation or true-risk evidence before choosing a diagnosis.Assuming validation directly measures approximation error.
Validation assesses the learned hypothesis, not automatically the best member of the entire class.
Fix:
Use validation as diagnostic information about the selected hypothesis and recognize that approximation error remains harder to estimate directly.Ignoring estimation error because the hypothesis class is expressive.
Learning from a finite sample can still produce a poor selected hypothesis, creating a difference between empirical and true risk.
Fix:
Inspect the empirical-to-true-risk gap and use validation to assess the learned hypothesis.
Practice Diagnosis
A learned hypothesis has high training risk. In a second case, a learned hypothesis has low training risk but a large gap between empirical risk and true risk. For each case, identify the more plausible diagnostic pattern and state whether you should investigate a limitation of the hypothesis class or a finite-sample learning problem first.
Hints
- The source associates large empirical risk with underfitting.
- The source associates a large empirical-to-true-risk gap with overfitting.
- Approximation error concerns the best member of the class, while estimation error concerns learning from a finite sample.
What do you think happens?
If training risk is low but validation risk is much larger, which explanation is more consistent with the supplied diagnostic pattern?
Reveal answer
Answer: A large empirical-to-true-risk gap associated with overfitting
Validation provides evidence about the learned hypothesis outside the training sample. The pattern does not directly measure approximation error or establish how well the best class member matches the true hypothesis.
Key Takeaways
- Approximation error is the gap between the true hypothesis and the best hypothesis available in a class.
- Estimation error is the difference between empirical risk and true risk caused by learning from a finite sample.
- Validation helps estimate the true risk of a learned hypothesis, but it does not directly reveal the class's approximation error.
- Large empirical risk is associated with underfitting, while a large empirical-to-true-risk gap is associated with overfitting.
- Training risk and validation evidence are diagnostic tools, not interchangeable measurements of approximation error.
Key Takeaways
- Approximation error concerns the best hypothesis a class can provide; estimation error concerns the hypothesis learned from finite data.
- Validation assesses the learned hypothesis on data outside the training sample.
- High empirical risk suggests underfitting, while a large empirical-to-true-risk gap suggests overfitting.
- Low training risk alone cannot establish low approximation error.
- Choose the next investigation by separating class limitations from finite-sample learning problems.