1
$\begingroup$

In a tutorial on SVM by Andrew N.G http://cs229.stanford.edu/notes/cs229-notes3.pdf, on page 6,7 he has explained SVM in connection to functional margins and then has replaced it by 1 reasoning that W can be rescaled appropriately.

But then in the final formulation there is nothing that talks about scaling of W, so when we will solve the optimization problem it may not be appropriately scaled and moreover constraints say that y_i*(w.x+b) >= 1. So how are both formulation of the problem equivalent unless we explicitly make sure to scale w while we implement the solution.

I am very much confused about the affect of functional margin and geometric margin on the formulation of SVM optimization problem.

$\endgroup$
1
$\begingroup$

I find the following a convenient way to think about SVM:

solve for $y_i(\langle w, x_i \rangle + b) \geq K - \xi_i$ where $2K$ is our functional margin, and $\xi_i$ is the amount by which we haven't achieved that functional margin. The geometric margin will be $\frac{2K}{||w||}$. There can be additional error terms multiplied by some weights.

We then have several different approaches to solving from an optimization perspective:

  1. Maximize the functional margin (or solve for $\min -K$ plus error terms). But, then we could keep multiply through $w$ and $K$ by some $\beta > 1$, and the objective would improve without changing our hyperplane direction. So we'd need to require that $||w||^2 \leq 1$ for example, to prevent run-away growth (i.e., objective of minus infinity). And then at the solution we know that we'll get $||w||^2 = 1$.
  2. Similar to step 1, but rather than constrain $||w||^2 \leq 1$ add on some regularization term to $||w||^2$ to the objective, where we now need a new constant to weigh the $K$ term relative to it: $\min \frac{||w||^2}{2} - \nu K$ plus error terms. This is the approach used by $\nu$-SVM.
  3. Fix $K$ to a constant, e.g. $K=1$. Then the geometric margin is maximized by minimizing $||w||$ or equivalently $\frac{||w||^2}{2}$. This is the approach taken by $C$-SVM.
$\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.