Skip to content
Last Dictionary
Plane
Mathematics & StatisticsMachine Learning

PAC learning

nounAlso: probably approximately correct learning, PAC, PAC learnability, PAC model, sample complexity, PAC-Bayes

In plain wordsA mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.

  1. A framework of computational learning theory that defines successful learning as a two-parameter guarantee: given examples drawn i.i.d.i.i.d., abbr.: Short for 'independent and identically distributed': every data point is produced the same way, and none influences any other — like repeated rolls of one fair die. from an unknown distribution and labeled by an unknown target concept in a known class, the learner must, except with probability at most δ, return a hypothesis whose error on that same distribution is no more than ε — hence 'probably approximately correct'. A class is efficiently PAC-learnable if this takes a number of examples — the sample complexity — and computation polynomial in 1/ε, 1/δ and the problem size. For a finite hypothesis class, about (log |H| + log 1/δ)/ε examples suffice; for infinite classes the VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably. decides learnability and sample complexity. PAC learning gave machine learning its first rigorous notion of generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers., tied learnability to computational complexity and cryptography, and inspired boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made.; PAC-Bayes bounds extend it to randomized predictors and yield some of the few non-vacuous generalization bounds for deep networks.

    In the PAC model, halving the error target roughly doubles the number of examples needed.

Pr⁡S∼Dm[ errD(hS)≤ε ]≥1−δ\Pr_{S\sim\mathcal{D}^m}\big[\,\mathrm{err}_{\mathcal{D}}(h_S) \le \varepsilon\,\big] \ge 1 - \delta

Origin

Introduced by Leslie Valiant in 'A Theory of the Learnable' (Communications of the ACM, 1984); the label 'probably approximately correct' and the acronym PAC came into use over the following years. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler and Manfred Warmuth tied PAC learnability to the VC dimension (1989). Valiant received the 2010 Turing Award, in part for this work.

Related

See also
  • VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably.
  • statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones.
  • empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data.
  • generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers.
  • boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made.
  • no free lunch theoremno free lunch theorem, n.: A mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others.

Sources

  1. Valiant, L. G. (1984). A Theory of the Learnable. Communications of the ACM, 27(11).

Mentioned in

boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made., empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data., generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers., i.i.d.i.i.d., abbr.: Short for 'independent and identically distributed': every data point is produced the same way, and none influences any other — like repeated rolls of one fair die., inductive reasoninginductive reasoning, n.: Reasoning from particular examples to a general rule or prediction — every swan I have seen is white, so swans are probably white — which is useful but can always turn out wrong., learninglearning, n.: Getting better at something through experience. For a machine, it means changing its internal settings based on data so that it performs a task better than before., Occam's razorOccam's razor, n.: A rule of thumb for choosing between explanations: if two fit the evidence equally well, bet on the one that assumes less. In AI it motivates preferring simpler models, which are less likely to fit noise., sample efficiencysample efficiency, n.: How much practice an AI needs to learn something — an agent that learns a game in a hundred tries is far more sample-efficient than one that needs millions., Vladimir VapnikVladimir Vapnik, prop. n.: A Soviet-born American mathematician who built the statistical theory of how machines learn from examples and co-invented support vector machines, a leading method before deep learning., hypothesis spacehypothesis space, n.: The full menu of possible models a learning method is allowed to choose from — for example, all straight lines. Learning means picking the item on the menu that best fits the data., Leslie ValiantLeslie Valiant, prop. n.: A British computer scientist who in 1984 gave the first rigorous definition of what it means for a computer to learn from examples, founding the theory of machine learning., no free lunch theoremno free lunch theorem, n.: A mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others., statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones., VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably.