Learning From Data – A Short Course: Exercise 8.7

Assume that the data is restricted to lie in a unit sphere.

(a) Show that d_{VC}(\rho) is non-increasing in  \rho.

Suppose a dichotomy is shattered by a hyperplane with margin  \rho then it is also shattered by that hyperplane with margin  \rho' < \rho as there is no margin argument in final hypothesis representation.

(b) In 2 dimensions, show that d_{VC}(\rho) < 3 for  \rho > \frac{\sqrt{3}}{2}.

For each line segment AB (A and B are two endpoints lying on the unit circle), call the center of unit sphere O, by The Law of Cosines, we have:

    \[ AB^{2} = OA^{2} + OB^{2} - 2 \times OA \times OB \times \cos(\hat{AOB}) = 2 - 2 \times \cos(\hat{AOB}) \]

So the line segments AB and A'B' have equal length if and only if  \hat{AOB} = \hat{A'OB'}, the line segments AB > A'B' if and only if  \hat{AOB} > \hat{A'OB'}.

If  AB > \sqrt{3} then  \hat{AOB} > 120 (and  \hat{AOB} \leq 180). Now consider the third point M lying on the unit circle. Suppose OM does not cross AB, then  \hat{MOA} + \hat{MOB} < 360 - 120 = 240, it’s easy to see that if  \hat{MOA} exceeds 120 then  \hat{MOB}  < 120 and we still have two points lie within distance \sqrt{3} of each other, the other case is similar. Now suppose OM crosses AB, then 120 < \hat{MOA} + \hat{MOB} < 180, the arguments go similar.

So for any 3 points lying on the unit circle, there must be two that are within distance \sqrt{3} of each other.

[FROM HERE I WAS FALLEN INTO FALLACY]

In the case that not all 3 points lie on the unit circle, we can consider this simple situation: Suppose M does not lie on the unit circle, we define M' as the intersection of the line OM and the unit circle, by the Law of Cosines, we always have M'A < MA and M'B < MB, so if M'A (M'B) exceeds \sqrt{3} then MA (MB) exceeds \sqrt{3}. The same goes for A and B if they do not lie on the unit circle. But we have argued that for any 3 points lying on the unit circle, there must be two that are within distance \sqrt(3) of each other, so this statement is also true for any 3 points inside the unit circle.

So the statement follows.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

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