In: Advanced Math
Compute growth function and VC dimension
H ={h: R -> {-1, +1} | h(x) = 1D(x) where D is a finite set of R}
Theorem (Sauer). If H is a class of functions with binary
outputs and its VC dimension is d =
dV C (H). Then for all n ∈ N,