Week 5 - Infinite hypothesis spaces

In Week 5 - Computational Learning Theory we developed a method to build a PAC learner on a finite dimensional hypothesis space. However this breaks down in infinite dimensions. We need to get around this.

Lets just cheat

Whilst the hypothesis space might be infinite theoretically, the actual number of distinct hypothesises could be finite. Then we can fall back on the previous work.

Discrete problem domain

Let and . Then notice that which is finite. If we had then is infinite as . However, in reality there are at most 11 realised functions here so we have a finite hypothesis space.

VC-dimension

In the problem above the hypothesis space was in some way limited. We want to capture the idea of a limited hypothesis space when looking at proper infinite dimensional hypothesis spaces.

Vapnik-Chervonenkis dimension

Vapnik-Chervonenkis dimension

Suppose we are in the modelling framework with feature space , domain , and we have hypothesis space . The VC-dimension of is the size of the largest set such that for all there exists such that for all .

Link to original

In the example above we have VC dimension 1. As for any two points if and then no such function can set without setting .

VC dimensions roughly follow degrees of freedom

Separator	VC-dimension	parameters
1- demensional hyperplane	1	1
Interval on	2	2
2-dimensional hyper plane	3	3
d-dimesional hyperplane	d + 1	-
Convex polygon in

PAC learnable and VC dimension

PAC learnable bound with VC-dimension

Statement

Lemma

For a learner with a hypothesis space with VC dimension then by drawing i.i.d. samples for training data if there are any hypothesis consistent with then this will be a PAC learner with accuracy with probability .

Proof

Link to original

This formula is out of no where but there is connection with the finite case where

For a finite hypothesis space for we require as we need at last that many hypothesis to split the cases up. Therefore we get a natural upper bound on the VC dimension

This nicely connects the formulas.

PAC learnable if and only if finite VC dimension

PAC-learnable if and only if finite VC dimension

Statement

Lemma

A hypothesis space is PAC learnable if and only if the VC dimension is finite.

Proof

Link to original