Learning theory (statistics)

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. Other forms of bound include the maximal number of mind changes required to converge to a solution in the limit.

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

• Review of An Introduction to Computational Learning Theory (http://www.santafe.edu/~shalizi/reviews/kearns-vazirani/)
• Review of The Nature of Statistical Learning Theory (http://www.santafe.edu/~shalizi/reviews/vapnik-nature/)
• Basics of Bayesian inference (http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm)