1
$\begingroup$

We know that the if $α=0$ in below equation it is not a support vector; support vectors have $α \ne 0$.

$$ L(w, b, α) = \sum_{i=1}^m α_i − \frac12 \sum_{i,j=1}^m y^{(i)} y^{(j)} α_i α_j (x^{(i)})^T x^{(j)}. $$

However, the kernel function i calculated for all pairs of vectors even if $α=0$.

Can we say that kernel is calculated for all vectors, but only support vector contribute to the final decision boundary?

Or actually is the kernel only calculated for support vectors?

It confuse me that because only support vector decide the boundary, why is the kernel need to calculate all pair of vectors in sample?

$\endgroup$
2
$\begingroup$

You don't know in advance which inputs are going to be support vectors; you need to do the optimization to figure that out.

One way to do that is to pre-compute the kernel matrix for all pairs of inputs, then run the solver on that.

Some more efficient SVM solvers will actually only compute the kernel function when it's needed, and can (using various techniques based on only a few kernel evaluations) figure out that a point isn't going to be a support vector, then not compute the kernel between those points and the rest of the dataset. But how those work exactly is complicated.

$\endgroup$
2
  • $\begingroup$ +1 Can you provide some key references or papers about the "more efficient SVM solvers"? This sounds very interesting and I would like to know more! $\endgroup$
    – Sycorax
    Sep 16 '19 at 19:46
  • $\begingroup$ @Sycorax The old-school classic SMO solvers do this, and I think more modern fancy SVM solvers do as well, though I don't know those very well. $\endgroup$
    – Danica
    Sep 16 '19 at 20:04

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.