Learning Theory: Cheat Sheet

The whole topic compressed for the night before the exam.

Concept learning

#NumbersCounting the spaces

• $d$ binary attributes give $2^d$ objects, and therefore $2^{2^d}$ concepts.
• Conjunctive concepts number $\mathbf{3^d + 1}$. For $d = 3$ that is $27 + 1 = 28$, down from 256.

≡FactsThe two algorithms

• Find-S - start from h = Ø; for each positive example, pairwise-AND, generalizing to ? wherever the values differ. It ignores negatives and returns the most specific hypothesis.
• Version space - the set of all hypotheses consistent with the training data, meaning $h(x_i) = c(x_i)$ for every $i$.

PAC learning

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

≡FactsPAC in four lines

• PAC-learnable means the above holds in time polynomial in $1/\varepsilon$, $1/\delta$, $n$ and $\text{size}(c)$. Probably ($\delta$) Approximately ($\varepsilon$) Correct.
• True error is the probability of misclassifying an instance drawn from $D$.
• ε-exhausted version space - every $h$ in the version space has error below $\varepsilon$.
• Haussler: $P(VS \text{ not } \varepsilon\text{-exhausted}) \le |H| e^{-\varepsilon m}$.

$$\textbf{Sample complexity:} \quad m \ge \frac{1}{\varepsilon}\left( \ln|H| + \ln\frac{1}{\delta} \right)$$

VC dimension

≡FactsShattering and capacity

• The finite-$H$ bound fails for infinite $H$, which is where VC dimension takes over.
• $H$ shatters $S$ if it realizes all $2^{|S|}$ dichotomies of $S$.
• $VC(H)$ = the largest set $H$ can shatter. For finite $H$, $VC(H) \le \log_2|H|$.

Hypothesis class	VC dimension
Interval on the real line	2
Linear surfaces / perceptron in ℝʳ	r + 1 (a line in 2D gives 3)
Conjunction of n literals	n
Sine wave a · sin(bx)	∞, on only 2 parameters

$$\text{testError} \le \text{trainError} + f(n, h = VC, p)$$

◎Exam cueThe generalization one-liner

Big $H$ against small $n$ means overfitting. A constrained $H$, or a large $n$, means low training error really does imply low generalization error.

Provenance: two VC-Dimension decks exist (Lec60 plus an alternate); both are merged here, including the alternate deck's bias-variance and generalization-bound material. The numeric examples on these pages - VC of an interval = 2, VC of a hyperplane in the plane = 3, and the sample-complexity bound - were independently recomputed and verified.