8
$\begingroup$

I was reading andrew ng's machine learning lecture notes on SVM. I came across the following equation (finding the optimal value for the intercept term $b$ in the SVM problem):

enter image description here

However, I have no idea how the intercept term $b$ is derived by solving the primal problem ?

I believe the primal's Lagrangian is:

$$\min_{w,b} \max_{\alpha} \mathcal{L}(w,b,\alpha) = \min_{w,b} \max_{\alpha} \frac{1}{2} ||w||^2 - \sum_{i=1}^m \alpha_i [y_i (w^T x_i + b) - 1]$$

But how do I solve for $b$ ? Any help will be great. Thank you very much.

$\endgroup$
2
  • $\begingroup$ That is not a primal problem. This is primal's Lagrangian. $\endgroup$
    – Gnattuha
    Mar 25, 2014 at 15:12
  • $\begingroup$ Please correct me if I am wrong. Or maybe tell me how to derive $b$ above ? Thanks $\endgroup$ Mar 25, 2014 at 15:26

3 Answers 3

9
$\begingroup$

I have geometric explanation. Think of SVM as a maximum margin classifier. In that sense we seek separating hyperplane which will be equidistant from all negative and all positive examples. This includes that the distance from hyperplane from the closest to it's negative example would be as large as the distance to the closest positive. Let $w^*$ be known, then $$\max_{i: y^{(i)}=-1} w^{*T}x^{(i)}$$ is the closest (worst case) distance from all possible negative examples. Similarly $$\min_{i: y^{(i)}=1} w^{*T}x^{(i)}$$ is the closest (worst case) distance from all possible positive examples. How can we choose intercept so that the worst case distance for all (worst case) examples is maximum? Yes, we take the average of two.

The '-' sign.

Strictly speaking, $\max_{i: y^{(i)}=-1} w^{*T}x^{(i)}$ is not a distance because it is negative, while $\min_{i: y^{(i)}=1} w^{*T}x^{(i)}>0$. So in order to bring hyperplane from the worst negative to the worst positive direction we need the '-' sign.

$\endgroup$
1
  • 2
    $\begingroup$ your intuition is great, but I am looking for a mathematical derivation. Thanks anyway. $\endgroup$ Mar 25, 2014 at 15:54
6
$\begingroup$

First, for support vectors 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,

$argmax_{i:y^{(i)} = -1} \omega^{*T}x^{(i)}$, resp. $argmin_{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$.

P.S. why is $\frac{-b}{||\omega||}$ is the distance from the origin to the hyperplane? We could solve it with some algebra (like here), or as a optimization problem :) The distance to a line is the norm of the vector point closest to the origin. That is, we would like to solve,

$$ min ||x||^{2} $$ subject to $\omega^{T}x + b = 0$. By introducing Lagrange multipliers we get, $$ L = \frac{1}{2}||x||^{2}-\lambda(\omega^{T}x + b) $$ If we derive with respect to $x$, equal to zero and solve for $x$, we get $x=\lambda \omega$. Subtitute back in the constraint and find $\lambda = \frac{-b}{||\omega||^{2}}$.

$\endgroup$
1
  • $\begingroup$ your answer is good. I just want to ask why is $-\frac{b}{||w||}$ the distance from the origin to the hyperplane ? Can you elaborate (mathematically) on this a little bit please ? $\endgroup$ Mar 27, 2014 at 13:48
2
$\begingroup$

I know it's late but just in case it helps I'll give an equivalent explanation to the earlier responses which may also help.

Firstly, our primal problem here is: $$ \min_w \frac{1}{2}\lVert{w}\rVert^2$$ $$ s.t. \rightarrow y^i(w^Tx^i+b)\geq1=\hat{\gamma}$$

From this primal problem and just like jpmuc says, the closest data points ($x^i$) of the training set to the decision boundary will satisfy:

$$\min_{y^i=1} (w^{*T}x^i) + b^*= 1 \iff y^i=1$$ and $$\max_{y^i=-1}(w^{*T}x^i) + b^*= -1 \iff y^i=-1$$

This is because we have earlier set the functional margin of the whole dataset ($\hat{\gamma}$) to $1$.

Now, we know that the margin of the positive points to the decision boundary (hyperplane) has to be equal to the margin of the negative points to the hyperplane. Otherwise the margin of one set of the points (negative or positive) wouldn't be equally maximized.

Given this, and the two latter equations (from the primal problem) we can arrive to the desired value $b^*$ by adding them up and solving for $b^*$:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.