Learning From Data – A Short Course: Exercise 8.1

Assume D contains two data points (x_{+}, + 1) and (x_{-}, -1). Show that:

(a) No hyperplane can tolerate noise radius greater than \frac{1}{2}\left \| x_{+} - x_{-} \right \|.

Assume such hyperplane exists and we call it h.

    \[ \left\{\begin{matrix} \text{dist}(x_{+},h) > \frac{1}{2}\left \| x_{+} - x_{-} \right \|\\ \text{dist}(x_{-},h) > \frac{1}{2}\left \| x_{+} - x_{-} \right \| \end{matrix}\right. \Rightarrow \text{dist}(x_{+},h) + \text{dist}(x_{-},h) > \left \| x_{+} - x_{-} \right \| [1] \]

Let d is the line connecting two points x_{+} and x_{-}, as two points stay on different sides seperated by the hyperplane h, it’s always true that d crosses h at some point and we call that point a and:

    \[ \left \| x_{+} - x_{-} \right \| = \left \| x_{+} - a \right \| + \left \| x_{-} - a \right \| \]

It is also true that:

    \[ \left\{\begin{matrix} \left \| x_{+} - a \right \| \geq \text{dist}(x_{+},h) \\ \left \| x_{-} - a \right \| \geq \text{dist}(x_{-},h) \end{matrix}\right. \Rightarrow \left \| x_{+} - a \right \| + \left \| x_{-} - a \right \| \geq \text{dist}(x_{+},h) + \text{dist}(x_{-},h) \]

So:

    \[ \left \| x_{+} - x_{-} \right \| \geq  \text{dist}(x_{+},h) + \text{dist}(x_{-},h) [2] \]

Fact [1] and [2] contradicts each other, so the statement follows.

(b) There is a hyperplane that tolerates a noise radius \frac{1}{2}\left \| x_{+} - x_{-} \right \|

Let d is the line connecting two points x_{+} and x_{-}, and a = \frac{(x_{+} + x_{-})}{2} , the hyperplane h that satisfies the condition is orthogonal to d and contains a.


Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

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