Learning From Data – A Short Course: Exercise 3.12

Page 103:

We know that in the Euclidean plane, the perceptron model $H$ cannot implement all 16 dichotomies on 4 points. That is $m_{H}(4) < 16$ . Take the feature transform $\Phi$ in (3.12).

(a) Show that $m_{H_{\Phi}}(3) = 8$ .

We have proved (in Exercise 2.4) that the hypothesis set of perceptron model in Euclidean plane has $d_{vc} = 3$ , and by the definition of VC dimension, we have: $m_{H_{\Phi}}(3) = 2^{3} = 8$ .

(b) Show that $m_{H_{\Phi}}(4) < 16$ .

If: $m_{H_{\Phi}}(4) \geq 16 = 2^{4}$ , then the hypothesis set of perceptron model in Euclidean plane can shatter $\geq 4$ points so its VC dimension would be $\geq 4$ , which contradicts the fact that its VC dimension is only 3 (as stated above).

(c) Show that $m_{H \cup H_{\Phi}}(4) = 16$ .

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 $m_{H \cup H_{\Phi}}(4) \geq 16$ . However we also have: $m_{H \cup H_{\Phi}}(4) \leq 2^{4} = 16$ . So: $m_{H \cup H_{\Phi}}(4) = 16$ .

Leave a Reply Cancel reply