Does PAC mean perfectly correct?

No. It explicitly allows an error tolerance and a probability of failing to meet the target.

Can noisy tasks be studied?

Yes. Agnostic PAC learning compares performance with the best hypothesis in the class rather than assuming a perfect one exists.

Is a larger hypothesis class always better?

No. It may express better predictors, but its complexity also affects generalization analysis and the difficulty of finding an appropriate hypothesis.

AI Glossary / Graphs and symbolic AI / Intermediate

Probably approximately correct

Definition

Probably approximately correct, usually abbreviated PAC, describes a mathematical learning guarantee. Roughly, with sufficiently many appropriately sampled examples, a learner returns a predictor whose error is small with high probability. “Approximately” concerns the allowed error; “probably” concerns the chance that the learning procedure fails to achieve that error target.

What it means

The distinction involves two kinds of uncertainty. A trained classifier has a true error rate under a specified data distribution. Before training, the random sample may lead the learner to a better or worse classifier. PAC statements control the probability of obtaining a classifier with excessive true error.
Write epsilon for the error tolerance and delta for the allowed failure probability. In realizable classification, the candidate class contains a perfectly correct classifier. In agnostic learning, that assumption is removed: the target is error within epsilon of the best achievable in the chosen class. Efficient PAC learning additionally requires suitable polynomial resource bounds.

How it works

Define the hypothesis class, loss, sampling assumptions, and learning rule. A classical setting draws independent, identically distributed labeled examples from a fixed distribution. Prove that, above a sample-size threshold, the probability of returning a hypothesis outside the required error tolerance is at most delta.
For a finite, realizable classification class H, a consistent learner returns a hypothesis making no training mistakes. A standard sufficient bound is m ≥ [ln(|H|) + ln(1/delta)]/epsilon. Here ln is the natural logarithm. This is a sufficient upper bound on the required number of examples, not a universal minimum. Infinite classes require other complexity measures and appropriate results.

Three practical examples

A learning-theory lesson can compare how error tolerance and confidence affect the number of examples needed for a small rule class.
An analyst designing a restricted binary tagging system can examine whether a finite-class guarantee applies to the planned sampling process.
A research team can distinguish a learnability result from a claim that its particular implementation finds the required hypothesis efficiently.

Think of it this way

Think of repeatedly receiving random training packs and producing a classifier from each pack. Most packs should lead to a classifier whose future error stays within a chosen tolerance. The analogy is limited because the guarantee concerns the specified sampling distribution and learning assumptions, not every imaginable future example or every shift in operating conditions.

Worked example

Suppose an invented binary learning task has exactly 100 candidate classifiers. Assume one is perfectly correct, labels are accurate, examples are independent draws from the target distribution, and the learner can return a classifier consistent with every training example.
Choose epsilon = 0.05 and delta = 0.05. The finite-class sufficient bound is [ln(100) + ln(20)]/0.05, approximately 152.018. Rounding upward gives 153 examples. Under these assumptions, the learner's returned classifier has true error at most 5% with probability at least 95% over the training sample.
As a check, the proof's failure bound at 153 is 100 × exp(−0.05 × 153), approximately 0.0476, below 0.05. Halving epsilon to 0.025 changes the unrounded requirement to about 304.036, requiring 305 examples. This calculation does not mean 153 examples suffice for an arbitrary business classifier.

Illustrative case study

Fictional case: Amber Records proposes to choose among 100 fixed document-tagging rules and uses the calculation above to discuss a pilot. During review, staff discover that ambiguous labels prevent any candidate rule from fitting the training data consistently.
The team withdraws the realizable-case calculation as its project guarantee. It investigates an agnostic formulation and conducts a separate evaluation of the actual tagging task. The lesson is about checking theorem assumptions before using a number in a delivery plan. No real organization, measured accuracy gain, or successful certification is implied.

Common misconceptions and mistakes

Do not read 95% confidence as a promise that each individual prediction has 95% correctness probability. In the example, the bound concerns repeated training samples and the returned classifier's overall error.
Zero training error alone does not establish a useful generalization guarantee. “Distribution-free” also does not mean immune to changes between training and deployment: the statement must hold for any fixed distribution in its scope, with the sampling relationship preserved. A statistical existence result need not provide a practical, fast algorithm. Finally, avoid presenting a sufficient worst-case bound as the exact amount of data a project needs.

Business use

PAC reasoning gives teams a disciplined vocabulary for discussing generalization: what counts as error, how much is tolerated, how failure probability is defined, and which model class is considered. It helps expose a mismatch between a mathematical claim and a proposed collection process.
For a practical pilot, record the theorem's assumptions alongside the calculation. Check labeling quality and whether repeated records undermine independence. Track class changes when adding new candidate rules. Continue empirical evaluation and monitoring; a valid bound does not measure every operational consequence, subgroup pattern, or future distribution change that matters to users.

Check your understanding

In the worked example, is delta = 0.05 the classifier's permitted true error rate?

Answer: No. Epsilon = 0.05 sets that error tolerance. Delta = 0.05 bounds the probability, over the training procedure's randomness, of returning a classifier whose true error exceeds the tolerance. They happen to have equal numerical values here.

Related terms

Learn next

Learn sample complexity and VC dimension next. Keep the worked example's class and epsilon fixed, change delta from 0.05 to 0.01, and recompute the sufficient sample size. Explain why greater confidence increases the requirement even though the permitted error rate has not changed.

Sources

Matt Gormley, Carnegie Mellon University, PAC Learning lecture: https://www.cs.cmu.edu/~mgormley/courses/10601-s21/slides/lecture25-pac.pdf Danica J. Sutherland, University of British Columbia, Statistical Learning Theory, PAC learning: https://www.cs.ubc.ca/~dsuth/532D/26w1/notes/html/chap_pac-nfl.html

Previous: Probability theory Next: Probalistic imputation