Advanced Machine Learning

03: PAC learning

Schedule (you are here )

Outline for the lecture

• Recap: Foundations
• PAC Learning Model & Sample Complexity
• Capacity of Infinite Classes: VC Dimension
• Agnostic PAC & General Loss
• Learning via Uniform Convergence
• Take Home Points

Recap: foundations

Formalized the problem of learning!

• Domain Set ${\cal X}$ (all papayas)
• Label set ${\cal Y} = \{0,1\}$ (sometimes $\{-1, 1\})$
• Training data
  $S = ((x_1,y_1)\dots (x_m, y_m))$.
  Sequence of pairs in $\cal{X}\times\cal{Y}$
• The learner's output
  $h: \cal{X} \rightarrow \cal{Y}$
• A (simple) data-generation model
  • $\cal{D}$ - distribution of papayas
  • $f: \cal{X} \rightarrow \cal{Y}$ - true labeling function
  • $y_i = f(x_i) \forall i$

Introduced measures of success

Learned about overfitting

Introduced inductive bias and some assumptions

The Realizability Assumption: $\exists h^* \in {\cal H} s.t. L_{{\cal D}, f}(h^*)=0 \implies L_S(h^*)=0$

The i.i.d. Assumption: Samples in the training set are independent and identically distributed.

Upperbounded $\delta$

PAC Learning Model

Probably Approximately Correct

Follows

Given a finite $\cal H$, fixed $\delta \in (0,1)$ and $\epsilon > 0$, and $m \ge \ln{(|{\cal H}|/\delta)}/\epsilon$ for any $f, {\cal D}$ (realizability assumption must hold) with probability at least $1-\delta$ over i.i.d samples $S$ of size $m$, for every ERM hypothesis $h_S$:
$L_{({\cal D}, f)}(h_S) \le \epsilon$

Leslie Valliant

PAC Learning

Valiant 1984

PAC learnability: ${\cal H}$ is PAC learnable if $\exists m_{\cal H}: (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following properties:

• $\forall \epsilon, \delta \in (0,1), {\cal D}, f$
• $\forall \cal D$ over $\cal X$ and $\forall f:{\cal X} \rightarrow \{0, 1\}$
• when realizability assumption holds
• when running on $m \ge m_{\cal H}(\epsilon, \delta)$ i.i.d samples the learning algorithm returns $h_S$ s.t.
• $\underset{S\sim{\cal D}}{\PP}[L_{({\cal D},f)}(h_S) \le \epsilon] \ge 1 - \delta$

Sample Complexity

Sample Complexity for finite classes

What about infinite classes?

VC Dimension: "Effective Size" of $\cal H$

The Labeling Game & Shattering:
Give me $d$ data points and arbitrarily assign each as ● or ○.
If ${\cal H}$ can reproduce every one of the $2^d$ possible labelings, then ${\cal H}$ shatters those $d$ points.
VC dimension $\text{VCdim}({\cal H})$ is the largest $d$ for which some arrangement of $d$ points can be shattered.

VC Dimension: Three Canonical Examples

Why do we care? VC dimension & PAC

Recall activity

1. What do we mean by learner?
A process of turning training data $S$ into functions (classifiers).
2. What is generalization error?
Probability of randomly (according to ${\cal D}$) choosing an example $x$ for which $h(x)\ne f(x)$
3. What is overfitting?
Excellent performance on $S$ and poor in real world.
4. What is a fundamental question in learning theory?
Which hypothesis classes ERM$_{\cal H}$ learning will not overfit

Going more general

Beyond Binary Classification

Going more general

Releazing the Realizability Assumption

The Realizability Assumption: $\exists h^* \in {\cal H} s.t. \PP_{x\sim{\cal D}}[h^*(x) = f(x)]=1$

True and Empirical Errors Revisited

Thomas Bayes

The Bayesian Optimal Predictor

Thomas Bayes

The Bayesian Optimal Predictor

• No hope to find $h$ with better error: Bayesian error is the optimum.
• Without assumptions on $\CD$ no algorithm can be as good as Bayesian optimum.
• Alas, we do not know $\CD$ and cannot utilize the predictor.
• Instead, search for predictor with error not much larger than the best possible error.

Agnostic PAC Learning

${\cal H}$ is agnostic PAC learnable if $\exists m_{\cal H}: (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following properties:

• $\forall \epsilon, \delta \in (0,1), {\cal D}$ over ${\cal X}\times {\cal Y}$
• when running on $m \ge m_{\cal H}(\epsilon, \delta)$ i.i.d samples returns $h_S$ s.t.
• $\underset{S\sim{\cal D}}{\PP}[L_{\CD}(h_S) \le \underset{h' \in {\cal H}}{\min} L_{\CD}(h') + \epsilon] \ge 1 - \delta$

Multiclass Classification

document classification

Multiclass Classification: BCI

Multiclass Classification: next word

Regression

Regression: history

Francis Galton

Regression: why the name

The term "regression" was coined by Francis Galton in the nineteenth century to describe a biological phenomenon. The phenomenon was that the heights of descendants of tall ancestors tend to regress down towards a normal average (a phenomenon also known as regression toward the mean).

Regression: loss

Expected square difference:
$L_{\CD}(h) \def \underset{(x,y)\sim\CD}{\mathbb{E}} (h(x) - y)^2$

Mean squared error:
$L_{\CD}(h) \def \frac{1}{m} \sum_{i=1}^{m} (h(x_i) - y_i)^2$

Generalized Loss Function

0-1 loss

Square Loss

Agnostic PAC Learning for General Loss Function

${\cal H}$ is agnostic PAC learnable with respect to $Z$ and $\loss: \hclass\times Z \rightarrow \RR_+$if $\exists m_{\cal H}: (0, 1)^2 \rightarrow \mathbb{N}$ and a learning algorithm with the following properties:

• $\forall \epsilon, \delta \in (0,1), {\cal D}$ over $Z$
• when running on $m \ge m_{\cal H}(\epsilon, \delta)$ i.i.d samples returns $h_S$ s.t.
• $\underset{S\sim{\cal D}}{\PP}[L_{\CD}(h_S) \le \underset{h^\prime \in {\cal H}}{\min} L_{\CD}(h^\prime) + \epsilon] \ge 1 - \delta$,
• where $L_{\CD}(h) = \underset{z\sim \CD}{\EE}[\loss(h,z)]$

Learning via Uniform Convergence

Learning Algorithm Function

• Receive the training set $S$
• $\forall h\in\hclass$ evaluate $L_S(h)$
• Return $h$ for which $L_S(h)$ is minimized

Informally

Suffices to show that empirical risk $\forall h\in \hclass$ is a good approximation of the true risk.

formal definition

$\epsilon$-representative sample: A training set is called $\epsilon$-representative (w.r.t. $Z$, $\hclass$, $\loss$, and $\CD$) if
$\forall h\in \hclass, \mid L_S(h) - L_{\CD}(h)\mid \le \epsilon$

Assume $S$ is $\frac{\epsilon}{2}$-representative (w.r.t. $Z$, $\hclass$, $\loss$, and $\CD$), then output of ERM$_{\hclass}(S)$ ($h_s\in \argmin_{h\in\hclass}L_S(h)$) satisfies:
$L_{\CD}(h_S) \le \underset{h\in\hclass}{\min}L_{\CD}(h)+\epsilon$

Proof:
$L_{\CD}(h_S) \le L_S(h_S) + \frac{\epsilon}{2} \le L_S(h) + \frac{\epsilon}{2}$
$L_S(h) + \frac{\epsilon}{2} \le L_{\CD}(h) + \frac{\epsilon}{2} + \frac{\epsilon}{2} = L_{\CD}(h) + \epsilon$

To ensure that ERM rule is an agnostic PAC learner, it suffices to show that with probability of at least $1-\delta$ over the random choice of a training set, it will be an $\epsilon$-representative training set.

without a proof

Finite hypothesis classes are agnostic PAC learnable

who to blame (mostly)

Vladimir Vapnik and Alexey Chervonenkis 1971

Leslie Valiant 1984

Take Home Points

Formalizing the Problem of Learning

Take Home Points

• Generalization > Memorization: The objective is low true risk $L_{\CD}(h)$, not zero empirical training error $L_S(h)$.
• Inductive Bias is Essential: Unrestricted ERM overfits (memorizer); we must restrict search to a hypothesis class ${\cal H}$.
• PAC Learnability ($\epsilon, \delta$): Guarantees error $\le \epsilon$ with confidence $\ge 1-\delta$ when sample size $m \ge m_{\cal H}(\epsilon, \delta)$.
• Finite Classes: Sample complexity scales with $\ln|{\cal H}|$ (counting hypotheses): $m = O\left(\frac{\ln|{\cal H}| + \ln(1/\delta)}{\epsilon}\right)$.
• Infinite Classes & VC Dimension: Finiteness is not required. Flexibility is measured by $\operatorname{VCdim}({\cal H})$ (independent binary decisions). A class is PAC learnable $\iff \operatorname{VCdim}({\cal H}) < \infty$.
• Agnostic PAC & Uniform Convergence: Without realizability, uniform convergence ($\forall h, |L_S(h) - L_{\CD}(h)| \le \epsilon/2$) guarantees ERM finds a near-optimal hypothesis.