0
$\begingroup$

I was following andrew ng machine learning course. I didn't understand something in the part where he was trying to formulate the optimization problem for svm. Specifically, How can you get formulation 2 from formulation 1. Formulation 1: $$\max_{\gamma, w, b}\gamma$$ subject to: $$y^{(i)}(w^Tx^{(i)}+b)\geq\gamma, i=1,\dots m,\\||w||=1$$

Formulation 2: $$\max_{\hat\gamma, w, b}\dfrac{\hat\gamma}{||w||}$$ subject to: $$y^{(i)}(w^Tx^{(i)}+b)\geq\hat\gamma, i=1,\dots m$$

$\endgroup$
0
$\begingroup$

Remove the $||w||=1$ constraint, and on the previous line replace $w^T$ with $\frac{w^T}{||w||}$ (assuming $||w|| \neq 0$). Now multiply through by $||w||$, this gives: $y^{(i)}(w^Tx^{(i)} + b||w||) \geq ||w||\gamma$.

Define $\hat{\gamma} = ||w||\gamma$. Define $b' = b||w||$, and then (noting that $b$ doesn't appear anywhere else), optimize over $b'$ instead of $b$. This gives you: $$\max\limits_{\hat\gamma, w, b'} \frac{\hat\gamma}{||w||}$$ subject to $$y^{(i)}(w^Tx^{(i)} + b') \geq \hat\gamma, i=1,\dots,m$$ which is the second formulation with $b$ relabeled to $b'$.

| cite | improve this answer | |
$\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.