VC Dimension

Question 1

What are dichotomies?

Answer 1

Dichotomies are hypothesis limited to the eyes of inputs. We look at the maximum kind of lines w.r.t N inputs, which is <= 2^N. When the change in Eout and Ein is small, the two hypothesis are similar.

Question 2

What is the growth function to calculate the maximum number of dichotomies.

Answer 2

mH(n).

The larger mH(n), the more expensive or more complicated. Dependent on H and N

Question 3

When does H shatter x1,..,xn?

Answer 3

When the hypothesis set is able to generate all 2^N dichotomies.

Question 4

What is the break point for dichotomies?

Answer 4

If no k inputs can be shattered by H, k is a break point for H.

e.g. for 2D perceptron’s, the break point is N = 4

Question 5

Why is mH(n) not a good replacement for M?

Answer 5

Because it is exponential. However, when N is large we can change the upper bound such that its polynomial

Question 6

What is the Ein Eout inequality using the growth function?

Answer 6

P[|Ein(g) - Eout(g) > ε|] <= 4 mH(2N) exp(-1/8 ε^2 N)

If k exists, we can replace the bound with 4(2N)^k-1 exp(-1/8 ε^2 N)

Question 7

What is the VC dimension of a hypothesis?

Answer 7

dvc(H) is the largest value for N for which H can shatter all N training examples. It is the maximum non-breaking point

Question 8

What does a high dvc(H) mean?

Answer 8

A high dvc means a higher model complexity but smaller in-sample error