PAC — Probably Approximately Correct

Parent: learning-theory Prereq: learning-theory — defines c, H, h, D, err(h), ε, δ, m.

Valiant's (1984) framework for learning from random examples — the definition of "learnable."

PAC-learnable

A target concept c lives in a known hypothesis class H; labeled examples are drawn i.i.d. from an unknown distribution D. The class is PAC-learnable if there is an algorithm such that, for any accuracy ε, confidence δ, and distribution D, using a number of samples m polynomial in 1/ε and 1/δ, it outputs h ∈ H with error(h) ≤ ε — approximately correct — with probability ≥ 1−δ — probably.

Two independent tolerances: ε = accuracy (how wrong h may be) and δ = confidence (how often the whole run may fail). You never demand exact truth with certainty — only ε-close, 1−δ of the time.

How much data? (sample complexity)

For a finite class, a bound that suffices is

Read it: richer hypotheses (ln|H| large) cost more data; tighter accuracy (1/ε) costs more; higher confidence (ln(1/δ)) costs a little more. For infinite H, the ln|H| term is replaced by the VC dimension.

Concrete example — learning a rectangle

Target: an unknown axis-aligned rectangle; a point is + inside, − outside. Algorithm: output the tightest rectangle enclosing the seen + points.

Where can it be wrong? Only on the thin frame between the true rectangle and the (smaller) learned one — points there are truly + but predicted −. Split the frame into 4 strips; each strip's probability shrinks as you see more + points, and with m = O((1/ε) ln(1/δ)) samples every strip has probability ≤ ε/4 with confidence 1−δ. Total error ≤ ε. PAC-learned — and note the answer is only probably approximately the true rectangle, never exactly it.

Realizable vs agnostic

• Realizable: some h ∈ H is perfect (the truth is in the class).
• Agnostic: no perfect h; you settle for h within ε of the best-in-class. Same shape of guarantee, 1/ε² samples.