From A_Roadmap_to_SVM_SMO.pdf, pg 12.

a busy cat
(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?


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


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.