Learning theory (statistics)

In statistics, learning theory is a mathematical field related to the analysis of machine learning algorithms.

Machine learning algorithms take a training set, form hypotheses or models, and make predictions about the future. Because the training set is finite and the future is uncertain, learning theory usually does not yield absolute guarantees of performance of the algorithms. Instead, probabilistic bounds on the performance of machine learning algorithms are quite common.

There are several difference branches of learning theory, which are often mathematically incompatible. This incompatibility arises from using different inference principles: principles which tell you how to generalize from limited data.

Examples of different branches of learning theory include:

• Probably approximately correct learning (PAC learning), proposed by Leslie Valiant;
• Statistical learning theory, proposed by Vladimir Vapnik;
• Bayesian inference, arising from work first done by Thomas Bayes.
• Algorithmic learning theory, from the work of E. M. Gold.

Learning theory has led to practical algorithms. For example, PAC theory inspired boosting, statistical learning theory led to support vector machines, and Bayesian inference led to belief networks (by Judea Pearl). See also:

• information theory

External Links

• On-line book: Information Theory, Inference, and Learning Algorithms, by David MacKay, gives a detailed account of the Bayesian approach to machine learning.
• Review of An Introduction to Computational Learning Theory
• Review of The Nature of Statistical Learning Theory
• Basics of Bayesian inference