1
$\begingroup$

This is from the textbook "Understanding Machine Learning" by Shalev-Schwarz p. 169. enter image description here

Can anyone help me understand why the solutions to this optimization problem need to be divided by the norm of w? (Other resources online mention this translation to quadratic programming, but omit the division part.)

Thank you very much!!

$\endgroup$
1
$\begingroup$

You want to maximize the margin, so that all points of each class are as far as possible into their halfspace. Mathematically this implies your equation: $$y_i\left(\langle\mathbf{w},\mathbf{x_i}\rangle+b\right) > 1 \;\;\;\;\; \forall_i$$ Let's think about what this actually means.

If you divide both sides of the inequality by $||\mathbf{w}||$ you get: $$y_i\left(\langle\frac{\mathbf{w}}{||\mathbf{w}||},\mathbf{x_i}\rangle+\frac{\mathbf{b}}{||\mathbf{w}||}\right) > 1/||\mathbf{w}|| \;\;\;\;\; \forall_i$$

The expression: $$\langle\frac{\mathbf{w}}{||\mathbf{w}||},\mathbf{x_i}\rangle+\frac{\mathbf{b}}{||\mathbf{w}||}$$ basically expresses the distance of each point from your hyperplane, which is parameterized by the normal-vector $\frac{\mathbf{w}}{||\mathbf{w}||}$ (hyperplane orientation) and $\frac{\mathbf{b}}{||\mathbf{w}||}$ (hyperpplane bias), since you are projecting $\mathbf{X_i}$ on a unit-length vector.

Now if you maximize the righthand side of the equation (minimizing $\mathbf{w}$), it will necessarily maximize the lefthand side as well, due to the inequality direction, but, assuming that your representation is normalized as described above.

Hopes this helps shed some light here.

$\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.