0
$\begingroup$

I am trying to understand SVMs in depth watching lectures from MIT.

The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and margin boundaries as following:

Fat Boundaries

Note that $\frac1{||\theta||}$ is the distance between the margin boundaries and the decision boundary ($\gamma_i$ is just the signed distance, but we don't care for this question).

We then proceeds to note that our goal is:

  • To maximize $\frac1{||\theta||}$
  • while minimizing the Hinge Loss

Now, it is apparent that these two terms will co-exist in the objective function we are trying to form $(1)$.

The Objective Function $$\text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 \quad (1) $$

Given the fact that he wants to create a minimization problem he describes the maximization of the distance to be equal to the minimization of it's inverse squared divided by 2, i.e: $$\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$$

This does not make sense, as far as I can understand. In my mind this is the correct way of doing it:

$$\max\frac1{||\theta||}=\min||\theta||$$

Why did he insert a square and a division into the equation?

$\endgroup$
4
  • 3
    $\begingroup$ The distances are all positive, so in this region the square function $f(x)=x^2$ is monotonically increasing, meaning that $arg \min \|\theta\| = arg \min \|\theta\|^2$ and since division by 2 does not change who the minimum value is (only what that value is), then $arg \min \|\theta\|^2 = arg \min \frac{\|\theta\|^2}{2}$. Notice we are interested in $arg \min$ and $arg\max$ and not $\min$ and $\max$ $\endgroup$
    – nir shahar
    Feb 28, 2021 at 12:39
  • 1
    $\begingroup$ However I don't know to answer why such decision happened. $\endgroup$
    – nir shahar
    Feb 28, 2021 at 12:41
  • 1
    $\begingroup$ The squared norm is easier to compute and the objective function contains some more parameters too; there is no objective "best" solution for a soft SVM problem. It inherently contains some tradeoffs between the slack variables and the margin size -- that is why $\lambda$ shows up here. $\endgroup$ Feb 28, 2021 at 15:12
  • $\begingroup$ "Notice we are interested in $argmin$ and $argmax$ and not $min$ and $max$". That was actuary very helpful. Thank you! $\endgroup$ Mar 1, 2021 at 4:04

1 Answer 1

1
$\begingroup$

Minimizing $\|\theta\|$ is equivalent to minimizing $\|\theta\|^2/2$, in the sense that the minimum is achieved for the same value of $\theta$. Since our goal is primarily to find $\theta$, this substitution is not unreasonable.

Why was the substitution done? I don't know. Perhaps because it makes the resulting optimization easier; or just because it seemed simpler. Note that while $\|\theta\|$ might look "simpler", in some sense it is an uglier function, as it involves a square root, which can be messy to deal with. The way to figure out would be to understand the basic derivation using $\|\theta\|^2/2$, and then try replacing with $\|\theta\|$ and see if the same logic goes through or if there is a barrier.

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