Please enlighten me with Platt's SMO algorithm (for SVM)

Question

From A_Roadmap_to_SVM_SMO.pdf, pg 12.

_{(source: postimg.org)}

Assume I am using linear kernel, how will I be able to get both the first and second inner product?

My guess, inner product of datapoint with datapoint j labelled class A for the first inner product of the equation and inner product of datapoint j with datapoints labelled class B for second inner product?

Answer 1

Your understanding is correct. The point is that equation (8) $$y_i(<\textbf{w}, \phi_i> + b) - 1 = 0$$ is not exactly an equation, but a system of equations, one for each $i$ index of the support vectors (those for each $0<\alpha_i<C$.

The point is that you cannot compute $b$ during the optimization of the dual problem since it does not matter for optimization, you have to go back and compute $b$ from all the other equations you have (one possible way is (8)).

Vapnick suggestion is to not use only one of those equations, but two of them, specifically one support vector for a negative observation and one for a positive observation. In other words two support vectors which have opposite signs for $y_i$.

Let's name $A$ the index of one support vector and $B$ the index of a suport vector of opposite side, baiscally you select from the system of equations at (8) only two of them. Evaluate both of them and take the mean.

From: $$y_A(<\textbf{w},\phi_A>+b)=1$$ $$y_B(<\textbf{w}, \phi_B>+b)=1$$ We get: $$b_A=\frac{1}{y_A}-<\textbf{w},\phi_A>$$ $$b_B=\frac{1}{y_B}-<\textbf{w},\phi_B>$$ Where $b_A$ and $b_B$ are two estimations, then the mean is $$b = (b_A+b_B)/2 = -\frac{1}{2}(<\textbf{w},\phi_A>+<\textbf{w},\phi_B>)=-\frac{1}{2}\sum_{i=1}^{n}y_i\alpha_i(<\phi(x_i),\phi(x_A)>+<\phi(x_i),\phi(x_B)>)$$