Skip to content

Statistics · Data science and machine learning

Statistical Learning Theory Foundations and Their Relation to Knowledge Discovery

The core ideas of statistical learning theory, from risk and generalisation to capacity and the bias-variance trade-off, and what they mean for finding reliable patterns in data.

ModQu research article · 679 words · 5 references (APA 7th edition)

Download PDF

Every analysis that looks for patterns in data faces the same question: will what was found in this sample hold for new cases? Statistical learning theory is the branch of statistics and computer science that studies that question formally. It explains when a rule learned from a finite sample can be trusted to generalise, and why a model that fits its training data perfectly can still be useless.

Risk, empirical risk and generalisation

The theory starts from a simple set-up. Data points are drawn independently from an unknown distribution, and a learning method chooses a rule, such as a regression or a classifier, from a set of candidate rules. The quality of a rule is its risk, the expected loss on new data from the same distribution. Risk cannot be computed directly because the distribution is unknown, so methods minimise the empirical risk, the average loss on the training sample. The central concern is the generalisation gap: the difference between empirical risk and true risk (Vapnik, 1999).

Capacity and the bias-variance trade-off

Vapnik and colleagues showed that the size of the gap depends on the capacity of the set of candidate rules, measured for classifiers by the Vapnik-Chervonenkis (VC) dimension. Richer families can fit more patterns, including patterns that are pure noise, so their training error says less about their future error. Valiant (1984) framed the same problem as "probably approximately correct" (PAC) learning, asking how many examples are needed to learn a rule that is nearly right with high probability.

The practical consequence is the familiar trade-off between underfitting and overfitting (Hastie et al., 2009). Simple models have high bias; complex models have high variance. Figure 1 shows the pattern in a small simulation.

Line chart of average prediction error against polynomial degree from 1 to 12 for samples of 30 observations. Training error, in green, falls steadily from about 0.46 to 0.09 as complexity rises. Test error on new data, in orange, falls to a minimum of about 0.20 at degree 5 and then rises steeply, above the top of the scale (0.8) from degree 11. The gap between the two curves is the generalisation gap.
Figure 1. Training error keeps falling as models become more complex, while error on new data reaches a minimum and then rises. Illustrative data; chart by ModQu.

Regularisation and structural risk

Learning theory supplies the logic for structural risk minimisation: choose the model that minimises empirical risk plus a penalty for capacity. Regularisation methods such as ridge regression and the lasso, support vector machines and early stopping in neural networks all apply that principle (Shalev-Shwartz & Ben-David, 2014). In everyday practice, the penalty is usually tuned by cross-validation, which estimates risk directly on held-out data.

A worked illustration makes the idea concrete. Suppose a hypothetical retailer fits a churn model to 2,000 customers using 150 candidate predictors. An unpenalised model with every predictor and many interactions might classify 95% of training customers correctly yet only 70% of new customers. A lasso model that keeps 20 predictors might score 82% on both. The second model has learned less about this particular sample and more about customers in general, which is what the business needs. Learning theory explains why: the penalty limits capacity, and limited capacity keeps the generalisation gap small enough for the training result to be believed.

Relation to knowledge discovery

For anyone mining survey, customer or operational data, the theory carries three lessons.

Key takeaways

Statistical learning theory explains why fitting the data at hand is not the same as learning. Generalisation depends on the balance between sample size and model capacity, and it is protected by regularisation and honest validation. Those principles separate reliable knowledge discovery from the discovery of noise.

References

Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: Data mining, inference, and prediction (2nd ed.). Springer. https://doi.org/10.1007/978-0-387-84858-7

Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press. https://doi.org/10.1017/CBO9781107298019

Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134–1142. https://doi.org/10.1145/1968.1972

Vapnik, V. N. (1999). An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5), 988–999. https://doi.org/10.1109/72.788640

Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3), 107–115. https://doi.org/10.1145/3446776