Computational Learning Theory & PAC Learning

Source: Unit 5 §10

Computational learning theory (CoLT)

CoLT studies the complexity of learning algorithms - a theoretical analysis of when learning can succeed and when it is impossible.

≡FactsThe big questions

• Is a model always capable of learning? How many instances are sufficient? When is learning impossible?
• Can we identify inherently hard and easy problem classes, independently of the algorithm used?

Quantity	Question it answers
Sample Complexity	How many training examples are needed to converge, with high probability?
Computational Complexity	How much compute is needed to converge?
Mistake Bound	How many misclassifications happen before converging?

◎Exam cueThe two areas that get examined

PAC Learning and VC Dimension. Their applications are worth remembering too: PAC underpins boosting, and VC theory underpins SVMs.

The PAC problem setting

We are given instances $X$, hypotheses $H$, target concepts $C$ where $c: X \to \{0, 1\}$, and a fixed, unknown distribution $D$ over $X$. The learner $L$ sees examples $\langle x, c(x) \rangle$ and outputs a hypothesis $h$ that estimates $c$, which is then evaluated on new instances drawn from $D$.

Error	Definition
Training error	Whether h(x) = c(x) on the training instances
**True error error_D(h)**	The probability that h misclassifies an instance drawn at random from D

Two relaxations: why "probably approximately correct"

≡FactsWhat each word gives up

1. Approximately - we do not demand zero error, just error bounded by $\varepsilon$, a small number.
2. Probably - we do not demand success on every sample, just a failure probability bounded by $\delta$.

PAC drops two impossible demands at once: exact correctness becomes error under ε, and guaranteed success becomes success with probability 1 − δ.

The PAC framework

A concept class $C$ is PAC-learnable by $L$ using $H$ if, for all $c \in C$, for all distributions $D$, and for $0 \le \varepsilon, \delta \le \tfrac{1}{2}$, the learner $L$ outputs a hypothesis $h \in H$ with $\text{error}_D(h) \le \varepsilon$, with probability at least $(1 - \delta)$, in time polynomial in $1/\varepsilon$, $1/\delta$, $n$ and $\text{size}(c)$.

$$P\left[\, \Pr\big(c(x) \neq h(x)\big) \le \varepsilon \,\right] \ge 1 - \delta$$

≡FactsThe two things we expect from L

1. Output $h$ with high probability $(1 - \delta)$ and low error $\varepsilon$.
2. Do it in efficient time - polynomial in $1/\varepsilon$, $1/\delta$, $n$ and $\text{size}(c)$.

⚠GotchaNo free lunch

To guarantee that the hypothesis is correct on all instances you would have to check all the examples. Generalization is impossible without assumptions, which is precisely why the PAC guarantee is stated in terms of $\varepsilon$ and $\delta$ rather than certainty.

Sample complexity for consistent learners

A consistent learner outputs an $h$ that fits the training examples perfectly whenever that is possible, so $h \in VS_{H,D}$, the version space.

ε-exhausted version space: $VS_{H,D}$ is ε-exhausted with respect to $c$ and $D$ if every $h$ in it has $\text{error}_D(h) < \varepsilon$.

The version space is ε-exhausted when no hypothesis inside it still has true error above ε. Haussler bounds how often m examples fail to reach that state.

Haussler's Theorem (1988) - for finite $H$ and $m$ i.i.d. examples:

$$P\big(VS_{H,D} \text{ is NOT } \varepsilon\text{-exhausted}\big) \le |H| \, e^{-\varepsilon m}$$

→StepsDerivation sketch

1. A "bad" hypothesis - one with $\text{error} > \varepsilon$ - is consistent with a single example with probability at most $(1 - \varepsilon)$.
2. So it is consistent with all $m$ examples with probability at most $(1 - \varepsilon)^m$.
3. With $k \le |H|$ bad hypotheses, the union bound gives at most $|H|(1 - \varepsilon)^m$.
4. Using $1 - \varepsilon \le e^{-\varepsilon}$, this is at most $|H| e^{-\varepsilon m}$.
5. Set the failure probability to at most $\delta$: $|H| e^{-\varepsilon m} \le \delta$, and solve for $m$.

Sample complexity bound:

$$m \ge \frac{1}{\varepsilon}\left( \ln|H| + \ln\frac{1}{\delta} \right)$$

◎Exam cueHow the bound scales

Sample complexity grows as the natural log of $|H|$, as $\ln(1/\delta)$, and linearly in $1/\varepsilon$. Halving the error you will tolerate doubles the data you need; halving the failure probability barely costs anything.