VC-Dimension

Question 1

Goal of VC-dimension

Restriction of H to C

Shattering

Definition of VC-dimension

When H is not PAC learnable

Answer 1

Goal: Figure Out which classes H are PAC learnable

Restriction of H to C:
Let H be a class of functions from X to {0,1} and let C = {c1, … , cm} subset of X. The restriction Hc of H to C is:

Hc = {[h(c1), … , h(cm)] : h in H}

where we represent each function from C to {0,1} as a vector in {0,1}ì|C|.

Shattering: Given C subset of X, H shatters C if Hc contains all 2^|C| functions from C to {0,1}

VC-dimension: The VC-dimnesion VCdim(H) of a hypothesis class H, is the maximal size of a set C subset of X that can be shattered by H.

VC dimension measures the complexity of H, how large a dataset that is perfectly classified using the functions in H can be

Question 2

Fundamental Theorems of Statistical Learning and bound on
generalization