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'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
into the following equivalent problem [using the notion of functional margin]
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?
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$$
