Learning From Data – A Short Course: Exercise 3.12
Page 103:
We know that in the Euclidean plane, the perceptron model
cannot implement all 16 dichotomies on 4 points. That is
. Take the feature transform
in (3.12).
(a) Show that
.
We have proved (in Exercise 2.4) that the hypothesis set of perceptron model in Euclidean plane has , and by the definition of VC dimension, we have:
.
(b) Show that
.
If: , then the hypothesis set of perceptron model in Euclidean plane can shatter
points so its VC dimension would be
, which contradicts the fact that its VC dimension is only 3 (as stated above).
(c) Show that
.
Look at the Figure 2.1 (c) / 43, apart from 14 dichotomies established from lines, we can establish 2 more dichotomies through eclipses (1 eclipse bounds 2 blue points and 1 eclipse bounds 2 red points as shown in the figure). Hence . However we also have:
. So:
.





