3
$\begingroup$

I need help in verifying/understanding a step in formulating an optimization problem used for support vector machines (though this question doesn't need any background in SVM). Consider a bunch of $m$ points $x_1, x_2,\ldots,x_m\in\mathbb{R}^n$, a vector $w\in\mathbb{R}^n$ and let $$\gamma_i=\frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|}$$

where $b=-c\|w\|$ and $c$ is a constant. For this question, assume that $\gamma_i$ is positive for all $i$. Define $$\gamma\equiv \min_{i=1,\ldots,m} \gamma_i$$ and consider the optimization problem

$$\max_{w,b} \gamma \\\text{subject to}\ \frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|}\geq\gamma $$

Letting $\hat \gamma=\gamma\|w\|$, the above can be rephrased as:

$$\max_{w,b} \frac{\hat\gamma}{\|w\|} \\\text{subject to}\ \langle x_i,w\rangle + b\geq\hat\gamma $$

Now we have $\hat\gamma=\min_i (\langle x_i,w\rangle + b)$ and assuming that $w'=w/\hat\gamma$ (which implies $b'=b/\hat\gamma$ since $w$ and $b$ are proportional), we see that $\min_i (\langle x_i,w'\rangle + b')=1$. So we can finally rephrase the optimization problem as (note that earlier we were maximizing w.r.t. $w, b$; now we're maximizing w.r.t. $w',b'$)

$$\max_{w',b'} \frac{1}{\|w'\|} \\\text{subject to}\ \langle x_i,w'\rangle + b'\geq 1 $$

Is this chain of reasoning correct or have I missed something/made an error in any step? Also, this problem is based on the following lecture. The optimization problem is stated on page 6 and the objective is $\max_{\gamma, w, b}\gamma$. Shouldn't it be $\max_{w,b}\gamma$, since we're only allowed to freely change $w$ and $b$?

$\endgroup$
2
+25
$\begingroup$

The idea of this proof is essentially correct, the confusion about the difference between maximizing over $\gamma, w, b$ and over $w, b$ seems to be because there are two different possible ways to formulating the problem: One where you define $\gamma = \min_i \gamma_i$, as you do above. The other way is to specify constraints where $\gamma \le \gamma_i$ for all $i$ and optimize over $\gamma$ (which is essentially equivalent since the optimal choice of $\gamma$ will be the minimum of the $\gamma_i$).

The optimization problem as you have written it is sort of redundant, since $\frac{\langle x_i,w\rangle}{\|w\|} + \frac{b}{\|w\|} \ge \gamma$ is true just by your definition, and there is no need to write it out as a constraint. For it to be a linear program, technically you would have to do away with the definition that $\gamma = \min_i \gamma_i$, and just let $\gamma$ be a variable you optimize over.

$\endgroup$
  • $\begingroup$ Sorry for the late reply and thanks for the answer! Could you please elaborate on your first paragraph a bit more? The second paragraph makes complete sense. If you refer to this: cs229.stanford.edu/notes/cs229-notes3.pdf , then basically what I'm struggling to understand is the jump from the second last formulation (as in my question) with $\hat\gamma/\|w\|$ to the last formulation in which $\hat\gamma$ is replaced by $1$. This jump is described at the end of page 6 and the start of page 7 in the linked notes. If that makes sense to you, could you please explain that to me as well? $\endgroup$ – Shirish Kulhari May 25 at 10:23
  • 1
    $\begingroup$ Pg.5 in the same notes lines 14-21 describes about scaling factor for $(w,b)$ s.t $\hat \gamma = 1$.The idea is since you deal with $\frac{w}{\|w\|}$ unit vector and such the $\gamma$ is really an invariant when you replace say $w$ with $3w$ etc. What it says you choose appropriate values of $w$ and $b$ such that $\hat \gamma = 1$ $\endgroup$ – Gopal Anantharaman May 30 at 19:26

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.