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