Deriving the optimal value for the intercept term in SVM

Question

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):

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.

Answer 1

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.

Answer 2

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

Answer 3

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