PAC Learning is one of the most famous theories in learning theory. Learning theory concerns in answering questions like:

• What is learnable? Somewhat akin to La macchina di Turing for computability theory.
• How well can you learn something? PAC is a framework that allows to formally answer these questions. Now there is also a bayesian version of PAC in which there is a lot of research.

Some definitions

Empirical Risk Minimizer and Errors

The empirical risk minimizer is defined as

$$\arg \underset{\hat{c}\in \mathcal{H}}{\min }{\hat{R}}_n(\hat{c})$$

Where the inside is the empirical error.

The Generalization error is $R(\hat{c})=P_{x\sim D}(\hat{c}(x)\ne c(x))={\mathbb{E}}_{x\sim D}{1}_{\hat{c}(x)\ne c(x)}$ where $\hat{c}$ is the learned concept (classifier) and $c$ is the true error and $x$ is the instance space.

Empirical error give a certain dataset is just the accuracy:

$${\hat{R}}_n(\hat{c})=\frac{1}{n}\sum _{i=1}^n{1}_{\hat{c}(x)\ne c(x)}$$

It is true that in expectation the empirical error is the same as the generalization error.

It is quite easy to see that ${\mathbb{E}}_{s\sim {\mathcal{D}}^m}[{\hat{R}}_S(\hat{c})]=R(\hat{c})$ This will be important when we will prove some bounds for the inconsistent learner case, see #The Inconsistent Case.

Concepts and Hypothesis

We define a instance space $\mathcal{X}$ that is the space of the object of interest of our learning task. We define a concept a subset of $\mathcal{X}$ (this is why sometimes it is useful to use an indicator function to get a specific concept). A concept class is just a set of concepts. A Hypothesis class is the class of concepts that we are using to learn the true concept class.

Learning Algorithm

Given an Hypothesis Class $\mathcal{H}$ and a concept $c$ a learning algorithm in this context is a computable function that takes in input a labelled dataset $(x_1,y_1),\dots ,(x_n,y_n)$ and outputs an hypothesis $\hat{c}\in \mathcal{H}$. One result that we will have is that we cannot have infinite precision (learn the concept class infinitely well).

PAC Learnability

In words, we say that something is PAC learnable when given a sufficiently large sample, we can learn a concept with high probability. Formally, we say that a concept class $\mathcal{C}$ is PAC learnable if there exists a learning algorithm such that:

• for all $ϵ,\delta >0$ (respectively error parameter and confidence value)
• for all distributions $\mathcal{D}$ over $\mathcal{X}$,
• if the learning algorithm is given a sample of size $m\ge \text{poly}(1/ϵ,1/\delta ,\text{size}(x))$
• => with probability at least $1-\delta$ the algorithm outputs a hypothesis $\hat{c}$ such that $P(\hat{c}(x)\ne c(x))\le ϵ$. So recalling that the above is exactly the definition of risk:

$${\mathbb{P}}_{Z\sim D^n}(R(\hat{c})>ϵ)\le \delta$$

The PAC framework is a distribution-free model : no particular assumption is made about the distribution D from which examples are drawn.

General PAC Learnability

Above we assumed hypothesis where consistent, meaning we could correctly learn all the mappings. This is often not the case as we will probably observe noise in the observations:

$${\mathbb{P}}_{Z\sim D^n}(R(\hat{c})-\underset{c\in \mathcal{C}}{\inf }\mathcal{R}(c)>ϵ)\le \delta$$

Efficiently Learnable

If the sample size just depends on $\epsilon$ and $\delta$ then it is called efficiently learnable.

And one thing we would need to note is that sometimes the true concept is not in the hypothesis, so it's impossible to attain a risk

Example: Axis-aligned rectangles

Suppose we are in ${\mathbb{R}}^2$ and the concept class is the set of all axis-aligned rectangles. We generate some points with these rectangles. Let our learning algorithm return the minimum rectangle that contains all the points that return true. With this learning algorithm we do not have false positives.

Now let's fix $\epsilon$ and $\delta$ and consider some rectangles on each side, let's make them at most equal to $\frac{\epsilon }{4}$. We have now that the probability of error is:

$$P_{Z\sim D^n}(R(\hat{c})>\epsilon )\le \sum _{i=1}^4{P}_{Z\sim D^n}(Z\cap r_i=\varnothing )\le 4(1-\epsilon /4{)}^m\le 4\exp (-m\epsilon /4)$$

This implies that the number of samples needed is:

$$4\exp (-m\epsilon /4)\le \delta \Rightarrow m\ge \frac{4}{\epsilon }\log \left(\frac{4}{\delta }\right)$$

Often the sample efficiency bounds are derived in this manner in the framework of this theory.

This is a nice example on how to prove PAC related stuff. You should definitely remember the root idea of this example and how to write such proofs. There are nice exercises in the book to see if you are able to solve a PAC proof, refer to (Mohri et al. 2012).

Learning Bounds

Finite Hypothesis Class

If we have finite hypothesis class $\mathcal{H}$ then it is PAC learnable. We can get a consistent hypothesis that always classifies the training set correctly (note that here we are assuming that the dataset does not contain noise!). We need

$$n\ge \frac{1}{\epsilon }\left(\log (|\mathcal{H}|)+\log \left(\frac{1}{\delta }\right)\right)$$

Proof

Let's consider the set ${\mathcal{H}}_{\epsilon }=\left\{h\in \mathcal{H}:R(h)>\epsilon \right\}$. We want to bound the probability that we get a bad hypothesis for consistent learners, that is an hypothesis that can get a zero error on the training set. If we consider the probability of the set:

$$P(\exists h\in {\mathcal{H}}_{\epsilon }:\hat{R}(h)=0)\le \sum _{h\in {\mathcal{H}}_{\epsilon }}\mathbb{P}(\hat{R}(h)=0)\le |{\mathcal{H}}_{\epsilon }|(1-\epsilon {)}^m\le |\mathcal{H}|\exp (-m\epsilon )$$

We want to bound this probability by $\delta$, so we have:

$$|\mathcal{H}|\exp (-m\epsilon )\le \delta \Rightarrow m\ge \frac{1}{\epsilon }\left(\log (|\mathcal{H}|)+\log \left(\frac{1}{\delta }\right)\right)$$

$\square$

In theory, this result strongly suggest that in our finite world, we can PAC-learn everything, we only need to model finite hypothesis worlds (or hypothesis that are small enough). This will is usually the difficult part.

Universal Concept Class is not PAC-learnable

This theorem asserts that given a instance space $\mathcal{X}={\left\{0,1\right\}}^{\ast }$ and the concept class of all possible subsets, then the concept class is not PAC learnable. A simple check suggests that it is probably not learnable (although we wont provide the proof here). The main observation is that the hypothesis class is $|\mathcal{H}|=2^{2^n}$ with this setting and thus our sample complexity bounds becomes:

$$n\ge \frac{1}{\epsilon }\left(2^{n}log2+\log \left(\frac{1}{\delta }\right)\right)$$

Which is not polynomial in $n$.

The Inconsistent Case

Finite Classifier Sets Bound

Now we will tolerate that our learner does not learn the training data perfectly. We leverage Hoeffding's inequality, introduced in Central Limit Theorem and Law of Large Numbers, to prove the following theorem. If we fix an hypothesis $h:\mathcal{X}\to \left\{0,1\right\}$ we have

$${\mathbb{P}}_{S\sim {\mathcal{D}}^m}\left[{\hat{R}}_S(h)-R(h)\ge \epsilon \right]\le |C|\exp (-2m{\epsilon }^2)$$

We can also prove the opposite and have

$${\mathbb{P}}_{S\sim {\mathcal{D}}^m}\left[{\hat{R}}_S(h)-R(h)\le -\epsilon \right]\le |C|\exp (-2m{\epsilon }^2)$$

If we put them together we get:

$${\mathbb{P}}_{S\sim {\mathcal{D}}^m}\left[\left|R(h)-{\hat{R}}_S(h)\right|\ge \epsilon \right]\le 2|C|\exp (-2m{\epsilon }^2)$$

But note that this works for a fixed $h$. If we use learned hypothesis $\hat{c}$ it is not guaranteed that the above holds as $\hat{c}$ is a random variable dependent on the samples drawn (i.e. it could actually be bigger)! In my opinion, this has quite strong limits on the theory part. What is an unapplicable theory for? It seems to be more useful for philosophical insights on learnability.

Proof: We will prove the first inequality for the general case of finite $h$, the idea is similar for the single hypothesis case.

$$\begin{array}{rl}{P}_{S\sim {\mathcal{D}}^m}\left[{\hat{R}}_S(h)-R(h)\ge \epsilon \right]& \le P_{S\sim {\mathcal{D}}^m}\left[\underset{c\in C}{\sup }{\hat{R}}_S(c)-R(c)\ge \epsilon \right]\\ & =P_{S\sim {\mathcal{D}}^m}\left[\bigcup _{c\in C}{\hat{R}}_S(c)-R(c)\ge \epsilon \right]\\ & \le \sum _{c\in C}{P}_{S\sim {\mathcal{D}}^m}\left[{\hat{R}}_S(c)-R(c)\ge \epsilon \right]\\ \text{Hoeffding’s Inequality}& \le |C|\exp (-2m{\epsilon }^2)\end{array}$$

We note that $P({\max }_i{X}_i>\epsilon )=P(X_1>\epsilon \vee \dots X_n>\epsilon )$, this is the same argument put forward for the sup. By doing the same thing for the other side, we get the result.

A looser Inequality

Usually VC Inequality is used to address another looser inequality that is close, but not exactly that: If we consider ${\hat{c}}_n\in \arg {\min }_{c\in \mathcal{C}}{\hat{R}}_n(c)$ and $c^{\ast }\in \arg {\min }_{c\in \mathcal{C}}R(c)$, then we have that:

$$\begin{array}{rl}R({\hat{c}}_n)-R(c^{\ast })& =R({\hat{c}}_n)-{\hat{R}}_n({\hat{c}}_n)+{\hat{R}}_n({\hat{c}}_n)-R(c^{\ast })\\ & \le |{\hat{R}}_n({\hat{c}}_n)-R({\hat{c}}_n)|+{\hat{R}}_n(c^{\ast })-R(c^{\ast })\\ & \le \underset{\begin{array}{c}\text{“Optimization"}\\ \text{Uniform Convergence}\end{array}}{\underbrace{\underset{c\in \mathcal{C}}{\sup }|{\hat{R}}_n(c)-R(c)|}}+\underset{\begin{array}{c}\text{“Prediction"}\\ \text{Pointwise Convergence}\end{array}}{\underbrace{{\hat{R}}_n(c^{\ast })-R(c^{\ast })}}\\ & \le 2\underset{c\in \mathcal{C}}{\sup }|{\hat{R}}_n(c)-R(c)|\end{array}$$

There is a tradeoff between the optimization and the prediction part. I can get pointwise convergence with more samples, but this does not generalize to the real unseen risk, the uniform convergence.

Generalization Inequality: single hypothesis

Given a fixed hypothesis $h$ the following inequality is a simple consequence of the above bounds.

$$R(h)\le {\hat{R}}_S(h)+\sqrt{\frac{1}{2m}\log \left(\frac{2}{\delta }\right)}$$

Proof: We see that given $m$ samples and confidence of error $\delta$ we have that the value of $\epsilon$ is :

$$2\exp (-2m{\epsilon }^2)<\delta ⟹\epsilon >\sqrt{\frac{1}{2m}\log \left(\frac{2}{\delta }\right)}$$

Plugging this into the previous stuff we get the result.

Generalization inequality: Finite H

$$\underset{\text{Expected Error}}{\underbrace{R(h)}}\le \underset{\text{Emprirical Error}}{\underbrace{{\hat{R}}_S(h)}}+\underset{\text{Variance}}{\underbrace{\sqrt{\frac{1}{2m}\log \left(\frac{2|\mathcal{H}|}{\delta }\right)}}}$$

In practice, the bounds were quite loose. If $\hat{R}$ is smaller, that is some suggestion of overfitting.

Proof: This proof leverages the same idea of the previous proof in the sample complexity of finite hypothesis class. We have that:

$$P(\exists h\in \mathcal{H}:|{\hat{R}}_S(h)-R(h)|>\epsilon )\le 2|\mathcal{H}|\exp (-2m{\epsilon }^2))$$

Then we see that we can bound the probability that the generalization error is bigger than $\epsilon$ by $\delta$:

$$\epsilon >\sqrt{\frac{1}{2m}\log \left(\frac{2|\mathcal{H}|}{\delta }\right)}=\sqrt{\frac{\log |\mathcal{H}|-\log (\delta /2)}{2m}}$$

Vapnik-Chervonenkis' Bound

1974 theorem. Consider $|\mathcal{H}|<\infty$ and $R(c^{\ast })=0$. Then for every $n$ and $\epsilon >0$ it holds that:

$$P(R(\hat{c})>\epsilon )\le |\mathcal{H}|\exp (-n\epsilon )))$$

And:

$$\mathbb{E}[R(\hat{c})]\le \frac{1+\log |\mathcal{H}|}{n}$$

Proof:

$$\begin{array}{rl}P(R(\hat{c})>\epsilon )& \le P(\underset{c\in \mathcal{H},{\hat{R}}_n(c)=0}{\max }R(c)>\epsilon )\\ & =\mathbb{E}[\underset{c\in \mathcal{H},{\hat{R}}_n(c)=0}{\max }{1}_{R(c)>\epsilon })]\\ & \le \sum _{c\in \mathcal{H},R(c)>\epsilon }\underset{(1-\epsilon {)}^n}{\underbrace{P({\hat{R}}_n(c)=0)}}\\ & \\ & \le |\mathcal{H}|\exp (-n\epsilon )\end{array}$$

Which ends the proof of the first part. Note that this is just a different bound for the same thing we have proved in #Finite Hypothesis Class. This is very similar to the VC inequality.

Uncountable Hypothesis

In the case where we have uncountably large hypothesis classes the bound becomes:

$$P(\mathcal{R}({\hat{c}}_n^{\ast })-\underset{c\in \mathcal{C}}{\inf }\mathcal{R}(c)>\epsilon )\le 9n^{V{C}_{\mathcal{C}}}\exp (-n{\epsilon }^2/32)$$

Fingering Argument

Suppose you have $n$ points. Suppose you want to take a subset $d$ of these points, and associate to each subset two possible different hypothesis, the d-dimensional hyperplanes that passes through the points (two possible labelling, this is why we set 2). This set of hypothesis has size $2\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. Let's consider the one that has the best empirical error among these. Call this hypothesis $\hat{\varphi }$ and the value that it can achieve to be $L$, and ${\varphi }^{\ast }$ the best possible among all linear classifiers. What we want to show is that $\hat{\varphi }$ is a good classifier.

Good classifier

The interesting thing of this setting is that we can use finitely many hypothesis to approximate an infinite hypothesis set.

One can show that in the infinite set of all possible classifiers, there is no classifier $\varphi$ whose empirical error is smaller than $\hat{L}(\hat{\varphi })-\frac{d}{n}$. This is easy to see: by choosing $d$ points, it can disagree at a maximum of $d$ points, leading to that empirical error.

Standard result

One can prove that given the setting above it is true that

$$P(\mathcal{R}(\hat{c})-\underset{c\in \mathcal{C}}{\inf }\mathcal{R}(c)>\epsilon )\le \exp \left(2d\epsilon -n\frac{{\epsilon }^2}{2}\right)(2(\genfrac{}{}{0ex}{}{n}{d})+1)$$

Then learnability is obvious: binomials grow polynomial, while $n$ decreases exponentially, so it is bounded.

And that for $n>d$ we have:

$$\mathbb{E}[\mathcal{R}(\hat{c})-\mathcal{R}]\le \sqrt{\frac{2}{n}(d+1)(\log (n)+2)}$$

Classifiers with vanishing errors

If we have the above assumptions plus that the best classifier has risk $\mathcal{R}(c^{\ast })=0$ then one can prove that the best classifier with the same hyperplane logic as above has this for $n>d$ and $\epsilon \le 1$:

$$P(\mathcal{R}({\hat{c}}_n)>\epsilon )\le 2\left(\genfrac{}{}{0ex}{}{n}{d}\right)\exp (-\epsilon (n-d))$$

Note that if $\mathcal{R}(c^{\ast })=0$ means that in our set exists a classifier with $\hat{R}(c)\le \frac{d}{n}$ (this is the fingering assumption).

VC Dimension

When a theory is too powerful, that theory is not falsifiable in a Popperian sense. Meaning every type of data can be explained by that theory, suggesting that the theory does not explain anything. This is why for Buhmann says about Vapnik's work in 1982 was so interesting. In his opinion, it was able to bridge philosophy of science and mathematics.

What is VC Dimension

The Growth Function

The growth function of a hypothesis class $\mathcal{H}$ is the maximum number of dichotomies that can be induced by $\mathcal{H}$ on a set of $n$ points.

$$m_{\mathcal{H}}(n)=\underset{x_1,\dots ,x_n\in \mathcal{X}}{\max }|\left\{(h(x_1),\dots ,h(x_n)):h\in \mathcal{H}\right\}|$$

Intuitively, the growth function is the maximum number of ways that the hypothesis class can split the data, this is later used to define the VC dimension. For example, an hypothesis class with a single hypothesis that just returns a constant, has growth function constant equal to $1$.

Shattering

We say that a set of point $S$ of $m\ge 1$ is shattered by some hypothesis class $\mathcal{H}$ if the growth function is $2^m$. That is, the hypothesis class can split the data in all possible ways.

Intuitively, we say that an hypothesis class shatters a set of point $m$ if whatever assignment of $y$ we have to those point, there exists a $h\in \mathcal{H}$ that learns it.

Definition of VC Dimension

The VC dimension is kinda the opposite of the Shattering number: if in the shattering we keep the set constant and try to see what hypothesis class shatters it, here we set the hypothesis class fixed, and ask The VC dimension of a hypothesis class $\mathcal{H}$ is the cardinality of the largest set shattered by $\mathcal{H}$. This can be seen as some sort of opposite of the growth function. While the growth function focused on the number of data points, keeping $\mathcal{H}$ fixed, the VC dimension focuses on the number of points that $\mathcal{H}$ can shatter.

$$\text{VC}(\mathcal{H})=\max \left\{m:m_{\mathcal{H}}(m)=2^m\right\}$$

Sauer's Lemma

Sauer's lemma states the following: Given an hypothesis $\mathcal{H}$ with VC dimension $d$ then $\forall m\in \mathbb{N}$ the following holds:

$${\Pi }_{\mathcal{H}}(m)\le \sum _{i=1}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)$$

Infinite VC dimension are not Learnable

TODO

Examples with VC-dimensions

For this section, check chapter 3 of (Mohri et al. 2012).

Hyperplanes in ${\mathbb{R}}^d$

It can be proven that the VC dimension of the set of all hyperplanes in ${\mathbb{R}}^d$ is $d+1$. One simple example is the XOR function in ${\mathbb{R}}^2$, that is not linearly separable. The proof is not so simple and requires the use of Radon's theorem.

Sine Waves

It can be shown that the family of functions $h(x)=\sin (wx)$ has infinite VC dimension. TODO. I have no idea how VC could be proved formally

References

[1] Mohri et al. “Foundations of Machine Learning” The MIT Press 2012