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: .