Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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$$
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'$.
