Content
Summary
Statistical learning formalizes deriving predictors from labeled data to minimize true error on unseen instances. The Empirical Risk Minimization (ERM) paradigm selects hypotheses that minimize training error, though this approach risks overfitting if not managed carefully.
Intuition
Imagine you are trying to learn a rule for classifying items, but you cannot see the underlying truth or the full population. You only have a small sample of examples. The goal is to create a model that works well on future, unseen data, not just the data you already have. Since you don't know the true distribution of the world, you have to guess based on your sample. The most natural guess is to pick the rule that makes the fewest mistakes on your sample. However, if your rule is too specific to your sample, it might fail when it encounters new data.
Key equations
True error, the probability that hypothesis h misclassifies a random instance from distribution D.
Training error, the fraction of misclassified examples in the training set S of size m.
Derivation
- Define the learning setup with an instance space X, label set Y, and an unknown distribution D.
- Generate a training set S of size m by sampling pairs (x_i, y_i) where y_i = f(x_i).
- Identify the goal: minimize true error L_{D,f}(h) on unseen data.
- Recognize that D and f are unknown, making true error incalculable.
- Substitute true error with training error L_S(h), which is calculable from S.
- Apply Empirical Risk Minimization (ERM) by selecting h that minimizes L_S(h).
- Acknowledge the risk: minimizing training error does not guarantee minimizing true error due to overfitting.
Worked example
A student has a training set S of 10 examples. They propose two hypotheses, h1 and h2. h1 makes 0 errors on S, while h2 makes 1 error on S. Which hypothesis does ERM select, and what is the risk?
- Calculate L_S(h1) = 0/10 = 0.
- Calculate L_S(h2) = 1/10 = 0.1.
- ERM selects the hypothesis with the minimum training error, so h1 is selected.
- Risk: h1 might have memorized the training data (overfitting) and perform poorly on unseen data, whereas h2 might generalize better.
Answer ERM selects h1 because it has lower training error, but this choice risks overfitting.
Common mistakes
- Assuming the learner knows the underlying distribution D or the labeling function f.
- Confusing true error (generalization error) with training error (empirical risk).
- Assuming that minimizing training error always leads to a good predictor.