Probably approximately correct learning

In <a href="/facts/Computational_learning_theory/DKMoukIr">computational learning theory</a>, probably approximately correct (PAC) learning is a framework for mathematical analysis of <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a>. It was proposed in 1984 by <a href="/facts/Leslie_Valiant/hA5okAxL">Leslie Valiant</a>.
In this framework, the learner receives samples and must select a generalization function (called the hypothesis) from a certain class of possible functions. The goal is that, with high probability (the "probably" part), the selected function will have low <a href="/facts/Generalization_error/dy5YSgB8">generalization error</a> (the "approximately correct" part). The learner must be able to learn the concept given any arbitrary approximation ratio, probability of success, or <a href="/facts/Empirical_distribution_function/frWIF9F9">distribution of the samples</a>.
The model was later extended to treat noise (misclassified samples). 
An important innovation of the PAC framework is the introduction of <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> concepts to machine learning. In particular, the learner is expected to find efficient functions (time and space requirements bounded to a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> of the example size), and the learner itself must implement an efficient procedure (requiring an example count bounded to a polynomial of the concept size, modified by the approximation and <a href="/facts/Likelihood/1L8P4NBX">likelihood</a> bounds).

Probably approximately correct learning open-in-new

Probably approximately correct learning