2
$\begingroup$

I'm trying to follow Andrew Ng's notes on Support Vector Machines and had the following question.

In his notes, Ng, transforms the following optimization problem [using the notion of geometric margin] of the SVM

SVM Optimization Problem #1

into the following equivalent problem [using the notion of functional margin]

SVM Optimization Problem #2

My question is this: how are the conditions the same? I understand how $\gamma = \frac{\hat{\gamma}}{\Vert w\Vert}$, but what is the proof of the equivalence of the "s.t." conditions?

$\endgroup$

1 Answer 1

0
$\begingroup$

In the first formulation, we're trying to maximize geometric margin. The condition

$$y^{(i)}(w^Tx^{(i)} + b) \geq \gamma, \forall i = 1, \dots, m$$

can be re-written as

$$y^{(i)}((\frac{w}{\|w\|})^Tx^{(i)} + \frac{b}{\|w\|}) \geq \gamma, \forall i = 1, \dots, m$$

since we've imposed an additional constraint in the first formulation, i.e. $\|w\|=1$. Now, in the second formulation we replace $\gamma$ with $\hat{\gamma}$, and can thus write

$$y^{(i)}((\frac{w}{\|w\|})^Tx^{(i)} + \frac{b}{\|w\|}) \geq \frac{\hat{\gamma}}{\|w\|}, \forall i = 1, \dots, m$$

since $\frac{\hat{\gamma}}{\|w\|} = \gamma$. Ensuring that the second constraint from the first formulation is met in the second formulation, we set $\|w\| = 1$ and can thus write

$$y^{(i)}(w^Tx^{(i)} + b) \geq \hat{\gamma}, \forall i = 1, \dots, m$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.