2
$\begingroup$

I've been reading about Hard-SVM a little and I've ran into the analysis presented in "Understanding Machine learning" by Shai-Shalev Schwartz, there on pages 168-169 he presents a short proof of the following:

The distance between a point $x$ and the hyperplane defined by $(w,b)$ where $||w||=1$ is $|\langle w,x\rangle+b|$

So That explains why we are interested in $w\in\mathbb R^d$ with norm of 1, otherwise we would have to revise the formula for the margin from $min_{i\in[m]} (|\langle w,x\rangle+b|)$ to $min_{i\in[m]} (\frac{|\langle w,x\rangle+b|}{||w||})$

Then he also presents the following quadratic program:

$(w_0,b_0)=argmin_{(w,b)} ||w||^2$ s.t. $\forall i\in[m]: y_i(\langle w,x_i\rangle+b)\geq 1$

output: $\hat w = \frac{w_0}{||w_0||}, \hat b=\frac{b_0}{||w_0||}$

I'm a little confused by the fact that we minimize the norm of $w$ and then always return a $w$ with norm 1. Why would we do that? I guess it has something to do with how the margin was defined (for $w$ with norm 1), but doesn't that defeat the purpose of minimizing the norm of $w$?

Reference(pages 203-204 in this pdf version)

Thanks in advance.

$\endgroup$
5
  • $\begingroup$ I think the output: line is not part of the usual SVM formulation (although I may be a bit rusty). It may be something done for subsequent analysis of the weight vector? If you are only interested in discrete classification, then the decision surface doesn't depend on the norm of the weight vector, just it's direction, which isn't changed by normalising it. $\endgroup$ Feb 3, 2021 at 11:44
  • $\begingroup$ @DikranMarsupial, but what if we're interested in a classifier with a large margin?(for better generalization\ less overfitting) This is where the norm actually matters, isn't it? $\endgroup$
    – giorgioh
    Feb 3, 2021 at 12:14
  • $\begingroup$ The classifier still has the same margin as before (i.e. the distance in the feature space from the decision boundary to the nearest data point), it is just that the output of the classifier has a different value at the margin (and is no longer -1 or +1). $\endgroup$ Feb 3, 2021 at 12:41
  • 1
    $\begingroup$ The constraint should be $y_i(<w_i,x_i>+b)\geq 1$ $\endgroup$
    – gunes
    Feb 3, 2021 at 13:14
  • $\begingroup$ @gunes, Thanks. I fixed it. $\endgroup$
    – giorgioh
    Feb 3, 2021 at 13:31

2 Answers 2

1
$\begingroup$

I think it is because of the previous section, which shows that

The distance between a point x and the hyperplane defined by(w, b) where ‖w‖ = 1 is |〈w,x〉+b|.

If you are not interested in the (absolute) measurement of the margin, just in defining the hyper-plane that maximises the margin for some sample of data, then you can just solve the constrained quadratic optimisation problem and the margin will I think be 1/‖w‖^2 , which is what most implementations seem to do (and omit the normalisation step).

I suspect there may be some theoretical results in the book that require an absolute measurement of the margin, rather than a scaled one? It has been on my reading list for some time, but haven't got round to reading it yet.

$\endgroup$
2
  • 1
    $\begingroup$ Regarding your comment, it's right. I overlooked the values at the margin. I've deleted my answer. $\endgroup$
    – gunes
    Feb 3, 2021 at 13:13
  • 1
    $\begingroup$ @gunes was a good point about the margin calculation, was helpful in me understanding what I think the issue might be. $\endgroup$ Feb 3, 2021 at 13:14
0
$\begingroup$

If you notice in the book the previous section says that the purpose of Hard Margin SVM is the following:

$$argmax_{(w,b): ||w||=1} \min_{i \in [m]} | \langle w,x_i\rangle+b| \quad s.t\quad \forall i, \quad y_i(\langle w,x_i\rangle+b) \geq 0$$.

So theoretically lets say the optimal hyperplane for this is $w^*, b^*$ i.e it maximizes among all the minimum possible margins (calculated from all of the dataset).

Thus clearly:

$$\min_{i \in [m]} | \langle w^*,x_i\rangle+b| = \delta$$. Then clearly,

$(\frac{w^*}{\delta}, \frac{b^*}{\delta})$ is the hyperplane which gives a margin of $1$ for all the examples $i \in [m]$. And that is the reason for the same. You are trying to find the hyperplane which provides correct classification, and you that by finding a classifier which classifies with a large margin i.e $(\frac{w^*}{\delta}, \frac{b^*}{\delta})$ and the associated problem is actually a convex optimization problem unlike the actual objective which is very difficult to optimize (I believe it is called min-max problems). And then so that the actual problem is solved i.e $||w|| = 1$ you scale it after solving the convex optimization problem.

$\endgroup$

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.