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 Answer 1

2
$\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
    Commented Mar 24, 2020 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$ Commented Mar 25, 2020 at 2:33

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.