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 .


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *