# How does Bishop reformulate SVM into quadratic programming?

In Pattern Recognition and Machine Learning, Bishop gives the following formulation of SVM (section 7.1):

$$\mathrm{argmax}_{w, b} \left\{ \frac{1}{||w||} \min \left[t_n(w^T \phi(x_n) + b) \right] \right\}$$

He then notes that since the objective function $$g(w, b) = \frac{1}{||w||} \min \left[t_n(w^T \phi(x_n) + b) \right]$$ is positively homogeneous of degree 0, we have a degree of freedom in our solutions. So if $(w^*, b^*)$ is a maximum then so is $(\kappa w^*, \kappa b^*)$.

Can someone give a step by step explanation how the solutions of this problem are related to those of the following quadratic programming problem?

\begin{align} \mathrm{argmin}_{w,b} &\frac{1}{2}||w||^2 \\ \text{ such that } &t_n (w^T \phi(x_n) + b) \ge 1 \text{ for } n \in [1..N] \end{align}

I am not convinced by Bishop's argument to take $t_{n^*(w,b)} (w^T \phi(x_{n^*(w,b)}) + b) = 1$ where $n^*(w, b)$ is the minimizer of $t_n (w^T \phi(x_n) + b)$ for a given $w$ and $b$.

I think you are referring to (7.3) and (7.6) of Bishop where the expression: \begin{align*} \arg\max_{\vec{w},b}\left\{\frac{1}{||\vec{w}||}\min_n\left[t_n(\vec{w}^T\vec{\phi}(\vec{x_n})+b)\right]\right\} \end{align*}

is reformulated to: \begin{align*} \arg\min_{\vec{w},b} \frac{1}{2}||\vec{w}||^2 \end{align*}

Consider the two points that are closest to the decision boundary(one from each class). Let's call these two points $\phi^+$ and $\phi^-$. Evaluating the expression $y(\vec{x})=\vec{w}^T\vec{\phi}(\vec{x})+b$ at those two points(and any point not on the boundary) results in a non zero value $m$: \begin{align*} \vec{w}^T\phi^+(\vec{x_n})+b = m \\ \vec{w}^T\phi^-(\vec{x_n})+b = -m \end{align*} Note that the only difference will be the sign of $m$ because the decision boundary goes right through the middle and therefore both points have the same distance from the boundary.

Our aim is to maximize the distance between the two "sub-boundaries" to the left and right of our decision boundary. Let's call this distance $D$. Note that this is two times the margin(which is the distance form the decision boundary to one of the "sub-boundaries" as shown in Figure 7.1 of Bishop).

To calculate this distance we first find the difference vector between our two points and then project this to our weight vector $\vec{w}$. Since we want to get the actual distance we need to normalize this weight vector. \begin{align*} D&=\frac{\vec{w}^T}{||\vec{w}||}\left( \phi^+-\phi^- \right) \\ &=\frac{1}{||\vec{w}||}\left( \vec{w}^T\phi^+-\vec{w}^T\phi^- \right) \\ &=\frac{1}{||\vec{w}||}\left( \vec{w}^T\phi^+ + b - (\vec{w}^T\phi^- + b) \right) \\ &=\frac{1}{||\vec{w}||}\left( m - (-m) \right) \\ &=2\frac{m}{||\vec{w}||}\\ \end{align*}

The argument then is that since I can always rescale the weight vector to "remove" an $m$ out of $||\vec{w}||$ without changing the decision boundary we can rewrite this as $2\frac{1}{||\vec{w}||}$.

Maximizing this, is the same as minimizing its reciprocal: \begin{align*} \arg\min_{\vec{w},b} \frac{1}{2}||\vec{w}|| \end{align*}

Of course the values that minimize this expression will also minimize the same expression with a square on $||\vec{w}||$: \begin{align*} \arg\min_{\vec{w},b} \frac{1}{2}||\vec{w}||^2 \end{align*}

which is exactly (7.6).

Note that the original formulation is not really dependent on scale - in other words, the object value at $w_1, b_1$ is identical to that at $\alpha w_1, \alpha b_1$ for any $\alpha > 0$.

Therefore, let's define the scaled solution set to be those which have $||w|| = 1$ - to indicate this let's replace $w$ with $v$: $$\arg\max_{b, v: ||v||=1} \min[t_n(v^T\phi(x_n)+b)]$$

In the second problem, divide the constraint through by $\frac{1}{||w||}$, and then note that we can then replace $\frac{w}{||w||}$ with $v$, such that $||v||=1$: \begin{align*} \arg\max_{b,w,v : ||v||=1}& \frac{1}{||w||}\\ \textrm{s.t. } t_n(v^T\phi(x_n) + b) &\geq \frac{1}{||w||}, n \in [1,N] \end{align*}

At this point, $w$ no longer appears as a vector, and we only have a dependency on $\frac{1}{||w||}$, which we can replace with $S > 0$: \begin{align*} \arg\max_{S,b,v : S > 0, ||v||=1}& S\\ \textrm{s.t. } t_n(v^T\phi(x_n) + b) &\geq S, n \in [1,N] \end{align*}

And this clearly is: $$\arg\max_{b,v : ||v||=1} \min[t_n(v^T\phi(x_n)+b)]$$

In other words, the scaled solution sets are the same.

For simplicity of notation, let $y_n = w^T \phi(x_n).$ Also, for convenience, I will suppress $b$ and assume it's part of $w,$ and that one of the elements of $\phi(x_n)$ is unity.

The claim made by Bishop is that

$$\arg \max_w \left\{ \frac{1}{||w||} \min_n y_n t_n \right\}$$ is an infinite parameter family of solutions, and one of those solutions is equivalent to $$\arg \max_w \frac{1}{||w||} \hspace{2mm} \\ s.t. \hspace{1mm} t_n y_n \ge 1 \hspace{1mm} \forall n.$$

This isn't too hard to prove. You can do this in two steps. First, you can show that one of the solutions to the original optimization problems is equivalent to the maximization of $1/||w||$ with the constraint that $\min_n t_n y_n = 1,$ and then just show that this constraint is equivalent to the one expressed above (for this optimization, not in general).

1) Let $w^*$ be a solution to the original optimization problem. (Stressing the word a because there are infinite solutions). Then $\kappa w$ is also a solution, where $\kappa$ is a scalar constant. Since $y_n = w^T \phi(x_n)$ and we can scale $w$ however we want, we are free to choose $\kappa$ such that $\min_n t_n y_n = 1.$ With that choice, let $\omega^* = \kappa w^*.$ Then $\omega^*$ is the solution to the optimization problem, $$\omega^* = \arg \max_w \frac{1}{||w||} \\ s.t. \hspace{1mm} \min_n t_n y_n =1.$$

2) Suppose we want to do the following optimization problem: $$\arg \max_w \frac{1}{||w||} \hspace{2mm} \\ s.t. \hspace{1mm} t_n y_n \ge 1 \hspace{1mm} \forall n.$$

Let $v^*$ be the solution to this optimization, and let $k = \arg \min_n t_n y_n^*$ where $y_n^* = (v^*)^T \phi (x_n).$ We can then say, due to the constraint, that $t_k y_k^* = 1 + \epsilon,$ where $\epsilon \ge 0.$

Suppose $\epsilon > 0.$ Let $\omega^* = v^* / (1 + \epsilon).$ Then $t_k (\omega^*)^T \phi(x_k) = 1,$ which satisfies the above constraint. Also, $1 / ||\omega^*|| > 1 / ||v^*||.$ So $v^*$ must not be the optimal solution. This proves that the solution to the above optimization must yield $\min_n t_n y_n^* = 1.$ Therefore the optimization condition in 2) is equivalent to the optimization condition in 1).