0
$\begingroup$

I am studying SVM algorithm and its optimization problem. When we are constructing optimization problem, we say, that we are searching for such separating hyperplane, so that we rescale $w$ and $b$, so that $|w^T x + b|=1$ for those points in each class nearest to the hyperplane. After the rescaling, the distance from the nearest point in each class to the hyperplane is $\frac{1}{||W||}$.

So we state optimization problem

$$\min_{ w, b} \frac{1}{2}{||W||^2}$$ s.t. : $$y^{(i)}(w^Tx^{(i)}+b)\geq 1, i=1,\dots m.$$

Question: I don't see which constraint ensures, that for the nearest point to hyperplane in each class is going to hold $y^i(w^Tx^{(i)}+b)= 1$. I understand that there will be some point for which $y^{(i)}(w^Tx^{(i)}+b)=1$, but I don't understand which constraint ensures that on both sides of margin there will be such point.

I think I don't understand something simple here. If you have any explanation for this I would appreciate it very much.

$\endgroup$
0
$\begingroup$

Note that you are trying to find the minimum value that $w$ can have given that the constraint $y^{(i)}(w^Tx^{(i)}+b) \geqslant 1$ holds for all $i$. Also, note that the smaller the value of $w$ the larger is the distance from the hyperplane of the points. Now suppose that for some $w=w_1$ all points on one side of the hyperplane have $y^{(i)}(w_1^Tx^{(i)}+b) > 1$ (note the only greater than and not greater than equal to sign). This means that we can increase the margin on that side without violating the original constraint that we have. Note that increasing the margin is the same as decreasing $w$ (as they are inversely proportional). Therefore, we can find some $w_2<w_1$ for which the constraint too holds.

Hence, in short the fact that you are trying to minimize $w$ ensures that there is always some point on each side of the margin that has $y^{(i)}(w^Tx^{(i)}+b) = 1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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