1
$\begingroup$

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:

Excerpt

Edit: I guess, what I don't understand is why we can arbitrarly set the magnitude of beta to $\frac1M$. What does a positively scaled multiple mean in this case? Just a multiple larger than $0$?

$\endgroup$
1
1
$\begingroup$

If $(\beta, \beta_0)$ satisfies the inequality $(4.47)$, then for any positive $k$, $k>0$, $(k\beta, k\beta_0)$ would satisfies the inequality as well.

Also, $(\hat{\beta}, \hat{\beta}_0)=\left( \frac{\beta}{M\|\beta\|}, \frac{\beta_0}{M\|\beta\|} \right)$ satiesfies the inequlity as well since

$$y_i(x_i^T\hat{\beta}+\hat{\beta}_0)=\frac{y_i}{M\|\beta\|}(x_i^T\beta+\beta_0) \ge \frac{M\|\beta|}{M\|\beta\|}=1=M\|\hat{\beta}\|$$

Let's find $\hat{\beta}$ and $\hat{\beta}_0$ directly. Note that $\hat{\beta}$ satisfies the property that $\|\hat{\beta}\|=\frac1M.$

Hence we let $\|\hat{\beta}\|$ to be $\frac1M$, hence reducing the inequality to be

$$y_i(x_i^T\hat{\beta} + \hat{\beta}_0) \ge 1$$ $$\|\hat{\beta}\|=\frac1M$$

We want to maximize $M$, hence, we minimize $\frac1M$, which is equivalent to minimizing $\frac12\|\hat{\beta}\|^2$.

$\endgroup$
2
  • $\begingroup$ Thank you for answering. Okay, I understand the scaling part now. However I still don't get how we can just set beta to equal one over M. Isn't M what we want to optimize which should change between iterations of optimization? $\endgroup$ – E.K Mar 24 '20 at 21:52
  • $\begingroup$ Yes, I shouldn't have used the word "fix". I have tried to improve the answer. Yes, $M$ changes if you use an iterative algorithm to find $M$. $\endgroup$ – Siong Thye Goh Mar 25 '20 at 2:33

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.