3
$\begingroup$

I posted this question in the datascience stackexchange but no one answered so I thought I would post it here aswell:

Ok, so I've been trying to read up on how SVM:s work and started with maximal margin classifiers. At page 132 in ESL (Elements of Statistical Learning) the authors "reformulates" the optimization problem but I can't seem to understand what they are doing from 4.47 to 4.48. Does anyone know?

Here is an excerpt:

enter image description here

What I don't understand is why we can arbitrarly set the magnitude of beta to 1/M. What does a positively scaled multiple mean in this case? Just a multiple larger than 0?

$\endgroup$
1
$\begingroup$

For reference, the optimization problem in hand is \begin{gather}\tag{1} \max_{\beta, \beta_0} M\\ \text{subject to }y_i(x_i^T\beta + \beta_0)\geq M\|\beta\|, \forall i. \end{gather}

Assume the pair $(\widehat{\beta}, \widehat{\beta}_0)$ is a solution to this problem and let $\widehat{M}$ be the achieved objective value. Also assume that $(\beta^*, \beta_0^*)$ is a solution to $(4.48)$. We have \begin{equation*} y_i(x_i^T\widehat{\beta} + \widehat{\beta}_0) \geq \widehat{M}\| \widehat{\beta} \|, \forall i \end{equation*} which is equivalent to \begin{equation*} y_i \left( x_i^T \frac{\widehat{\beta}}{\| \widehat{\beta} \|\widehat{M}} + \frac{\widehat{\beta}_0}{\| \widehat{\beta} \|\widehat{M}} \right) \geq 1,\forall i \end{equation*} therefore, the pair $\left( \frac{\widehat{\beta}}{\|\widehat{\beta}\|\widehat{M}}, \frac{\widehat{\beta}_0}{\| \widehat{\beta}\| \widehat{M}} \right)$ satisfies the constraints of $(4.48)$. Since $(\beta^*, \beta_0^*)$ is a solution to $(4.48)$, we get \begin{equation*} \| \beta^*\| \leq \left\| \frac{\widehat{\beta}}{\| \widehat{\beta} \| \widehat{M}}\right\| = \frac{1}{\widehat{M}} \qquad\Rightarrow\qquad 1 \geq \widehat{M}\| \beta^* \|. \end{equation*} But also \begin{equation*} y_i \left( x_i^T \beta^* + \beta_0^* \right) \geq 1 \geq \widehat{M}\| \beta^*\|,\forall i \end{equation*} hence, $(\beta^*, \beta_0^*)$ satisfy the constraints of $(1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ okay, I'm with you on the first part but how do we get the two expressions before "But also" if B* and B0* is a solution to 4.48? $\endgroup$ – E.K Mar 24 at 22:26
  • $\begingroup$ We assumed that $(\beta^*, \beta_0^*)$ is a solution to (4.48). This means that among all other pairs $(z, z_0)$ that also satisfy the constraints of (4.48), $\|\beta^*\|^2$ must be less than or equal to $\| z\|^2$ (since the norm squared was our minimization objective and $(\beta^*, \beta_0^*)$ was the solution that minimizes it). Dropping the squares and letting $(\widehat{\beta}/(\| \widehat{\beta} \|\widehat{M}), \widehat{\beta}_0/(\| \widehat{\beta} \|\widehat{M}))$ be our $(z, z_0)$, the result above follows. $\endgroup$ – EuxhenH Mar 24 at 23:29

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.