PAC Learning - Probably Approximately Correct
Updated 2026-08-01
INTRODUCTION
English translation pending.
CORE DEFINITION
Introduced by Leslie Valiant. Probably Approximately Correct learning asks not whether an algorithm can identify a target concept exactly, but whether it can, with probability at least 1 minus delta, output a hypothesis whose error is at most epsilon, using a polynomial number of samples and computation. Sample complexity depends on the accuracy and confidence parameters and on the complexity of the hypothesis class, often measured by VC dimension.
SCAFFOLDING EFFECT
Reduce cognitive load
- Set the bar: define acceptable error and confidence before demanding a perfect model - Size the data: check that sample volume matches the accuracy and confidence you want - Accept approximation: treat approximately correct output as a valid result rather than a failure
Anchor fast decisions
Exact identification of a concept from finite data is generally impossible, since unseen cases can always differ. PAC shifts the goal to bounding error probabilistically: with enough samples, the best hypothesis on the data is unlikely to be far off on unseen data. The required sample size grows with the desired precision and with the richness of the hypothesis class.
MINIMUM ACTION
In progress 0/1Practice this model in one real situation:
account_treeGenealogyexpand_more
menu_bookReferencesexpand_more
Source support: Explicit
- en.wikipedia.orghttps://en.wikipedia.org/wiki/Probably_approximately_correct_learningverified
PRIVATE NOTES · Only visible to you
SAVED Q&A
ENTRY Q&A · Private saving available
Ask with a clear boundary
thinkingmodels answers from published entry context only.
Your question is sent to thinkingmodels. The answer uses public entry context only.