Perceptron

Perceptron

random.randstudent() (guest) 30 Jan 2015 23:54

Hi.

I saw that the margin in the perceptron algorithm is defined as min{(w*x)/||x||}. (See rec6 theorem 6.1).
My question is: Why do we divide by the norm of x?
As I understand it, w*x is |w||x|cos(a) where "a" is the angle between w and x. so dividing this by ||w|| should give us the distance of x from the seperating hyperplane.
As I understand it, by this you have also decided the creteria in the "Margin Perceptron Algorithm" presented in rec6.
(I assume this is why we calculate there (w*x)/||w|| and compare it to (gamma)/2.

Thanks in advance.

Re: Perceptron

Regev Schweiger 31 Jan 2015 07:59

This is indeed different than the "usual" definition of a margin, e.g. in the SVM the case. I agree this might be confusing.

We should divide by $||w^*||$ because of the reason you mentioned - but in the margin definition, we use a unit vector $w^*$ that defines the hyperplane, so this is not needed. When $w$ is not unit vector, like in the middle of the algorithm, we indeed need to divide by its norm.
We do divide by $||x||$ - note however that we assumed all the points $x$ are normalized to be unit vectors, so this is also redundant.
The question is therefore why normalize the points - the answer is, because it doesn't change the fact the points are separable or not, and it makes the analysis of the number of mistakes possible.