Estimation Error

Choosing Among Classifiers

When a learning algorithm produces a poor predictor, the poor result alone does not tell you why it failed. The model may be too limited to represent the underlying relationship, or it may be so complex that it has fitted noise in the available data. Estimation error is part of the second problem: it concerns the difficulty of accurately estimating the model's true parameters from finite data. To diagnose model selection correctly, first ask whether the chosen hypothesis class is too simple or too rich.

Class Complexity and Containment

Imagine comparing a small hypothesis class with a richer one. The richer class contains more possible classifiers, so it has more flexibility when representing the real classification problem. A small class offers fewer choices. That restriction can make learning more manageable from a finite sample, but it can also prevent the class from containing a good or optimal classifier.

Containment is useful because it makes the two pressures visible. A richer class gives the algorithm more candidates and is less likely to block a good solution. A smaller class gives the algorithm fewer candidates to distinguish among, which can reduce estimation error, but the class itself may impose a larger limitation on what can be represented.

Tracing the Two Errors

Approximation error is caused by the hypothesis class itself. It appears when the class is not rich enough to contain the optimal classifier. Estimation error has a different source: the learner must use a finite sample to choose and estimate a model, and the difficulty of doing that is related to both sample size and hypothesis-class complexity.

Increasing richness does not guarantee lower total error. It removes one possible limitation—the class being unable to express a good classifier—but creates more ways to fit the particular sample. With insufficient data, that extra flexibility can increase estimation error. Moving toward a smaller class reverses the pressure: estimation error may decrease while approximation error may increase.

Underfitting and Overfitting

Balancing the Selection

Model selection seeks a hypothesis class whose approximation error is not excessively high while its estimation error remains reasonable. A class that is too small may fail to express the real classification problem. A class that is too rich may offer so many alternatives that finite data cannot support reliable estimation. The goal is therefore not maximum simplicity or maximum richness, but a useful balance between the two sources of error.

In theory, the ideal hypothesis class would contain only the Bayes optimal classifier. That would avoid choosing among unnecessary alternatives. In practice, this class is generally unavailable because the Bayes optimal classifier depends on the underlying distribution, and that distribution is unknown. If the distribution were already known, there would be little need for learning. This is why practical model selection relies on a reasonable balance rather than a theoretically perfect class.

Using Prior Knowledge

Prior knowledge about the problem can guide the design of a hypothesis class. The knowledge does not need to provide a complete description of the optimal classifier. Even a reasonable conjecture about the structure of the classification problem can help produce a class with acceptable approximation and estimation errors.

Common Diagnostic Mistakes

• Assuming the richest hypothesis class must be best.

  Richness can reduce approximation error, but finite data may make estimation error larger.

  Fix: Look for a class that is expressive enough while keeping estimation error reasonable.

• Treating approximation error and estimation error as the same limitation.

  A small class may perform poorly because it cannot contain the optimal classifier, which is an approximation-error limitation.

  Fix: Separate the class's representational limitation from the difficulty of estimating a model from finite data.

• Calling every poor predictor overfitting.

  A poor predictor may be underfitting because it is too simple, or overfitting because it is too complex and fits noise.

  Fix: First determine whether the model is too limited or too closely tied to noise.

• Assuming that the theoretically ideal class is available in practice.

  The Bayes optimal classifier depends on an unknown distribution.

  Fix: Use prior knowledge and seek a practical balance between the two errors.

Practice Diagnosis

Key Takeaways

1. A hypothesis class is the set of classifiers from which the learning algorithm chooses.
2. Approximation error comes from a class that is not rich enough to contain the optimal classifier.
3. Estimation error is related to finite sample size and hypothesis-class complexity.
4. A small class may cause underfitting and higher approximation error, while a very rich class may cause overfitting and higher estimation error.
5. Good model selection balances expressive power with reliable estimation and uses prior knowledge when available.