Calculating the value of $b^{*}$ in an SVM

Question

In Andrew Ng's notes on SVMs, he claims that once we solve the dual problem and get $\alpha^*$ we can calculate $w^*$ and consequently calculate $b^*$ from the primal to get equation (11) (see notes)

$$b^* = -\frac{\max_{i:y^{(i)} = -1}{w^*}^Tx^{(i)} + \min_{i:y^{(i)} = 1}{w^*}^Tx^{(i)}}{2}$$

I am not sure how this was derived from the primal. The generalized lagrangian is (see equation 8)

$$\mathcal{L}(w, b, \alpha) = \frac{1}{2}w^Tw - \sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^Tx^{(i)} + b\right) - 1\right]$$

and the primal is, by definition,

$$\theta_{\mathcal{P}}(w, b) = \max_{\alpha\geq0} \mathcal{L}(w, b, \alpha)$$

To find $b^*$ we must the optimal solution of

$$\min_{w, b}\theta_{\mathcal{P}}(w, b)$$

Since we know $w^*$ we can write this as

$$\min_{w, b}\theta_{\mathcal{P}}(w, b) = \min_{b}\theta_{\mathcal{P}}(w^*, b)\tag{$*$}$$

Further, note that $\theta_{\mathcal{P}}(w^*, b) = \infty$ if for any $i$, $y^{(i)}\left({w^*}^Tx^{(i)} + b\right) < 1$. Otherwise, $\theta_{\mathcal{P}}(w^*, b) = \frac{1}{2}{w^*}^T{w^*}$. Hence, the solution to $(*)$ must be

$$\min_{b}\theta_{\mathcal{P}}(w^*, b) = \frac{1}{2}{w^*}^Tw^*$$

and the optimal solution $b^*$ must be such that $y^{(i)}\left({w^*}^Tx^{(i)} + b^*\right) \geq 1$ for each $i$. This only gives a range of values of $b^*$ and not a particular value. How do I mathematically get to equation (11)? More generally, how can I get $b^*$ for the soft-margin classifier?

Answer 1

For SVMs the decision boundaries are given by $\omega^{*T}x^{(i)} + b = \pm 1$, and $\frac{-b}{||\omega||}$ is the distance from the origin to the hyperplane.

The closest positive and negative examples to the separating hyperplane are,

$\arg\max_{i:y^{(i)} = -1} \omega^{*T}x^{(i)}$, resp. $\arg \min_{i:y^{(i)} = 1} \omega^{*T}x^{(i)}$

These verify (because the must be support vectors) the equations for the decision boundaries, that is,

$\max_{i:y^{(i)} = -1} \omega^{*T}x^{(i)} + b = -1$, resp. $\min_{i:y^{(i)} = 1} \omega^{*T}x^{(i)} + b = 1$

Add the two and solve for $b$.

In the soft margin case (see for example Buerge's A Tutorial on Support Vector Machines for Pattern Recognition), you have the following quadratic problem,

$$ \begin{array}{c} \min \frac{1}{2} ||w||^2 + \frac{C}{n}\sum_i \xi_i + \sum_i \alpha_i (1-y_i w^T x_i - \xi_i) - \sum_i \lambda_i \xi_i \\ \alpha_i \geq 0, \xi_i \geq 0, \lambda_i \geq 0 \end{array} $$

where $\xi_i$ are the slack variables which allow for some samples to lie on the wrong side of the margin. When you calculate the dual, the problem becomes

$$ \begin{array}{c} \max \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i\alpha_jy_iy_jx_ix_j \\ \alpha_i \geq 0 \\ \lambda_i \geq 0 \\ \alpha_i + \lambda_i = \frac{C}{n} \end{array} $$

which implies that $0 \leq \alpha_i \leq C$. It means that allowing for some errors, limits how much weight we put on each sample. Now, once you solve for it, you still only need to consider those cases for which $\alpha_i > 0$ and for which $\xi_i = 0$. That is where the marging exactly lies.

More specifically, if $\alpha_i > 0$, then $y_i w^T x_i = 1-\xi_i \leq 1$. It either lies exactly on the margin, or on the wrong side of it. In other words, the condition for support vectors lying exactly on the separating hyperplane is the same in both the hard and soft cases, namely

$$ 1 = y_i (w^T x_i + b) = y_i(\sum_{j \in SV} \alpha_j y_jx_j^T x_i + b) $$

where $SV$ stands for the set of indices corresponding to the support vectors. Since $y_i \in \{1, -1\}$ then $y_i^2 = 1$, and we can multiply both sides by $y_i$ to get

$$ b = y_i - \sum_{j \in SV} \alpha_j y_jx_j^T x_i $$

Answer 2

I am also following Andrew Ng's note on SVM and had the same question. Inspired by OP's description and the first answer, I believe I have found a "natural" way of arriving at the solution

$$b^*=-\frac{\max_{i:y_i=-1}w^*\cdot x_i + \min_{i:y_i=1} w^*\cdot x_i}{2}$$

In question description, the OP tries to solve for $b^*$ by plugging $w^*$ into the generalized Lagrangian $\mathcal{L} (w,b,a)$. We expect setting the partial derivative against $b$ to 0 should give us a lead on finding $b^*$. But same as shown in the note, $\frac{\partial}{\partial b}\mathcal{L} (w,b,a)=0$ yields $\sum_i a_i y_i=0$. Which has nothing to do with $b$! This is saying the value of $b$ does not affect the minimum value of $\mathcal{L} (w,b,a)$. So we can choose an arbitrary value for $b$?

Not really. Because minimizing $\mathcal{L} (w,b,a)$ is not the only goal $b$ is involved in. It is also involved in the constraint, $$y_i(w^* \cdot x_i + b) \ge 1, i = 1, ..., m$$ Here we already replaced $w$ with the optimal value $w^*$. Recall that the decision boundaries are defined by Support Vectors, so there must be one or more Support Vectors on both decision boundaries. Also recall the relationship between functional margin $l$ and geometric margin $d$ is given by $d_i = \frac{l_i}{\|w^*\|}, l_i = y_i(w^* \cdot x_i + b)$. Support Vectors are, by definition, the closest to the hyperplane $w^* \cdot x+b=0$, meaning they have the smallest $d$, meaning that they have the smallest $l$. So for Support Vectors on the positive decision boundary ($y_i=1$), we have $$ \min_{i;y_i=1} l_i = \min_{i;y_i=1} 1 * (w^* \cdot x_i + b) = 1 $$

Similarly, for Support Vectors on the negative decision boundary, we have $$ \min_{i;y_i=-1} -1 * (w^* \cdot x_i + b) = 1 $$

Since both equations equals to 1, we connect them together to write $$ \min_{i;y_i=1} 1 * (w^* \cdot x_i + b) = \min_{i;y_i=-1} -1 * (w^* \cdot x_i + b)\\ b = \frac{\min_{i;y_i=-1} -1 * (w^* \cdot x_i) - \min_{i;y_i=1} 1 * (w^* \cdot x_i + b)}{2} $$ Note $\min_{i;y_i=-1} -1 * w^* \cdot x_i$ is the same as $\max_{i;y_i=-1} w^* \cdot x_i$, also pull out the negative sign to the front, we arrive at $$b = b^* = -\frac{\max_{i:y_i=-1}w^*\cdot x_i + \min_{i:y_i=1} w^*\cdot x_i}{2}$$

This conclueds my 2 cents on solving for $b^*$, kindly let me know if you spotted something funny along this answer.