Does Hard-SVM maximize the margin by shrinking the norm of $w$ a normal to the hyperplane?

Question

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.

Answer 1

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.

Answer 2

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.