1
$\begingroup$

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?

$\endgroup$
2
+50
$\begingroup$

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 $$

$\endgroup$
4
  • $\begingroup$ "The closest positive and negative examples to the separating hyperplane..." - how does this follow from the mathematics? That is to say, how does the formulation of the optimization problem imply that the equalities you mentioned do, in fact, hold. Ideally, once the optimization problem has been formulated we should not need to refer to the SVM setting at all. The reason I want a mathematical derivation is that your argument does not help in finding $b*$ for the soft margin case $\endgroup$
    – Gerard
    Mar 3 '20 at 16:54
  • $\begingroup$ These equalities corresponds to the active constraints (see the section on the KKT conditions), that is, the vectors lying exactly on the separating hyperplane. $\endgroup$
    – jpmuc
    Mar 3 '20 at 17:55
  • $\begingroup$ Could you elaborate a bit on that with maybe some hints on how to deal with the soft margin case? $\endgroup$
    – Gerard
    Mar 5 '20 at 15:31
  • $\begingroup$ added the soft case in the answer $\endgroup$
    – jpmuc
    Mar 6 '20 at 13:00
1
$\begingroup$

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.

$\endgroup$

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.