Approximation Error
A hypothesis class is the set of possible classifiers from which the learning algorithm chooses.
The Choice Behind Learning
A learning algorithm does not choose from every classifier that could possibly exist. It chooses from a hypothesis class: the set of possible classifiers made available to the algorithm. That design choice creates a trade-off. If the class is too small, it may be unable to represent the classifier needed for the problem. If it is too rich, the available data may not be sufficient to choose reliably among all its possibilities.
The richest possible hypothesis class is not automatically the best one. A useful class must be flexible enough to avoid a large approximation error while remaining manageable enough to keep estimation error reasonable.
Two Sources of Difficulty
Approximation error comes from the hypothesis class itself. It occurs when the class is not rich enough to contain the optimal classifier. Even if the learning algorithm had ideal information for choosing within that class, the desired classifier would still be unavailable.
Estimation error comes from having to learn with a finite sample and from the complexity of the hypothesis class. A richer class offers more possible classifiers, so the available sample may not be sufficient to choose reliably among them. In the source discussion, this difficulty is associated with overfitting.
A Class That Is Too Simple
When flexibility is missing
Imagine a classification problem whose optimal classifier is not included in a small hypothesis class.
Restrict the choices: The learning algorithm can select only from the classifiers in the small class.
Search within the class: The algorithm may choose the best available classifier, but the optimal classifier remains unavailable.
Identify the remaining error: Because the class cannot contain the optimal classifier, the class restriction creates approximation error.
A small hypothesis class can reduce estimation error while increasing approximation error.
The important point is that more data alone does not change what the class can represent. If the optimal classifier is absent from the class, the representation limitation remains. This is why an overly restricted class may lead to underfitting.
A Class That Is Too Rich
When flexibility creates uncertainty
Imagine expanding a hypothesis class so that it contains many additional classifiers.
Add possible classifiers: The learner gains more flexibility and is less likely to be blocked by the class when searching for a good solution.
Increase the number of plausible fits: The same flexibility creates more ways to fit the particular finite sample.
Check the trade-off: The richer class may lower approximation error, but estimation error might increase if the sample is not sufficient to choose reliably.
A rich hypothesis class can reduce approximation error while increasing estimation error and the risk of overfitting.
Complexity Trade-Off
| Hypothesis-class choice | Approximation error | Estimation error | Typical risk |
|---|---|---|---|
| Very small | May increase because the optimal classifier may be absent | Tends to decrease because there are fewer choices | Underfitting |
| Very rich | Tends to decrease because more classifiers are available | May increase because finite data may not distinguish the choices reliably | Overfitting |
| Reasonably designed | Not excessively high | Reasonable | A practical balance |
Increasing class richness gives the learner more possible classifiers. Approximation error therefore decreases because the class is less likely to block a good solution. At the same time, estimation error might increase because it depends on both finite sample size and hypothesis-class complexity. Decreasing richness produces the reverse pressure.
Using Prior Knowledge
Choosing a hypothesis class is not only a contest between the smallest and richest possible classes. Prior knowledge about the problem can guide which classifiers should be included. Even a reasonable conjecture about the structure of the problem can help produce a class whose approximation error is not excessively high while its estimation error remains reasonable.
A domain-informed class
Suppose prior knowledge suggests that the classification problem has a particular structure, but the optimal classifier is unknown.
Use the available knowledge: Design a hypothesis class that includes classifiers consistent with the suspected structure.
Avoid unnecessary alternatives: Do not automatically include every possible classifier merely because a richer class might contain the optimum.
Balance the errors: Evaluate the design by asking whether it avoids excessive approximation error while keeping estimation error reasonable.
Prior knowledge helps define a practical class without requiring a complete description of the optimal classifier.
Practice Check
A learner moves from a small hypothesis class to a richer one. State the likely direction of change for approximation error and the possible direction of change for estimation error. Then explain why neither a very small nor a very rich class is automatically best.
Hints
- Ask first whether the richer class contains more possible classifiers.
- Separate the class's ability to represent the optimal classifier from the finite sample's ability to support a reliable choice.
- Use the terms underfitting and overfitting only after explaining the underlying trade-off.
What do you think happens?
If a class becomes richer, which error is most directly expected to decrease, and which error might increase?
Reveal answer
Answer: Approximation error decreases; estimation error might increase
A richer class is less likely to exclude the optimal classifier, but its additional choices can make reliable learning from a finite sample more difficult.
Key Takeaways
- A hypothesis class is the set of possible classifiers from which the learning algorithm chooses.
- Approximation error occurs when the class is not rich enough to contain the optimal classifier.
- Estimation error is related to finite sample size and hypothesis-class complexity.
- A small class tends to reduce estimation error but may increase approximation error; a rich class tends to reduce approximation error but may increase estimation error.
- Prior knowledge can guide the design of a class that balances representational flexibility with reliable learning.
Key Takeaways
- Approximation error is caused by a hypothesis class that cannot represent the optimal classifier.
- Estimation error is connected to finite sample size and the complexity of the hypothesis class.
- Increasing class richness usually lowers approximation error but may raise estimation error.
- A practical hypothesis class should balance flexibility with reliable learning.
- Prior knowledge can help select a useful class even when the optimal classifier is unknown.