7
$\begingroup$

If you open any SVM guide you will see that 1/||w|| is proportional to margin size (which is meant to be maximized by SVM). But how did you get this result?

On the picture below you may see 2 plots. One is $x_{1} = -5x_{2} + 5$ and second is $x_{1} = -5x_{2} - 5$ according to my understanding of comments margin should have size equal to 10 in this case. But if you look at plots you will see its is slightly less than 2.

enter image description here

$\endgroup$
0

1 Answer 1

9
$\begingroup$

I assume that you understand that the margin is given by the equation $\langle w,x\rangle+b=\pm k$ where the width of the margin is equal to $2k$ and one has to maximise the width $k$.

Notice that the equation represents a hyperplane with normal vector $w$. Furthermore, if $w$ is a normal vector, then $\lambda w$ is also a normal vector (where $\lambda$ is a scalar). So we can just as well write $\langle \lambda w, x \rangle + b = \pm k$ or $\langle w , x \rangle + \frac{b}{\lambda} = \pm \frac{k}{\lambda}$. So by ''re-scaling" the vector $w$ with a factor $\lambda$ we can reduce the equation to $\langle w, x \rangle + b = \pm 1$.

If you want to compute the distance of a point $x_0$ to a hyperplane (see my answer to Getting distance of points from decision boundary with linear SVM?) than you have to compute

$\frac{| \langle w, x_0 \rangle +b |}{\sqrt{ \langle w,w \rangle}}$. (note that ${\sqrt{ \langle w,w \rangle}}=||w||$). If I take $x_0$ a point on the margin, then is must fullfill the equation of the margin, so $\langle w, x_0 \rangle +b=\pm 1$ so for a point on the margin the distance is equal to $\frac{| \langle w, x_0 \rangle +b |}{\sqrt{\langle w,w \rangle}}=\frac{| \pm 1 |}{\sqrt{\langle w,w \rangle}}$

EDIT: you added the picture and asked an additional question:

For equation $x_1+5x_2=5$ we see that when $x_1=0$ then $x_2=1$ and for $x_2=0$ we have $x_1=5$, so the $x_1$ axis is vertical and $x_2$ horizontal (you see that when you look for these points on your graph).

The point $(x_1,x_2)=(5,0)$ is on the red line (note that your $x_1$ is vertical) , $w$ is the vector $(1,5)$ and your equation is $x_1+5x_2+0=0$, so you have to compute $\langle w, x \rangle + 0 = 1 \times 5 + 5 \times 0 + 0 = 5$ and divide this by the norm of $w$ which is $\sqrt{1 \times 1 + 5 \times 5} \approx 5.1$, so half the margin is $\frac{5}{5.1}$

EDIT: Added after the question in your comments

The reason for 'eliminating' the $k$ is technical: because of the fact that the normal vector is only known op to a constant, the problem has no unique solution. So either you have to fix the norm of w or you have to fix the k. You could see both cases as choosing a different unit for measuring distances.

$\endgroup$
9
  • $\begingroup$ Thank you for answer. Suppose I have 2 dimension case with margins 1*x1 + 1*x2 + 0 = ±1. I say that margin size is equal to sqrt(2) not 2. Why I am not right? $\endgroup$ Aug 24, 2015 at 13:18
  • $\begingroup$ @Marat Zakirov: you don't have to thank me, it's better to vote for the answer (but only of you like it of course). The answer works in multi-dimensions: $\langle w, x \rangle=\sum_i w_i x_i$, $x$ and $w$ are vectors, $b$ is a scalar. $\endgroup$
    – user83346
    Aug 24, 2015 at 13:30
  • $\begingroup$ @user777: thanks (+1), I will edit the answer $\endgroup$
    – user83346
    Aug 24, 2015 at 13:30
  • $\begingroup$ I do not enough reputation to vote. Actually there is some misunderstanding. Maybe it will be great if I post some picture. $\endgroup$ Aug 24, 2015 at 13:39
  • $\begingroup$ @Marat Zakirov: Normally it should be possible to edit yor question and add a picture. I you do that I will see whether I can help you. (Is it impossible to vote for answers on your own question ?) $\endgroup$
    – user83346
    Aug 24, 2015 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.