I was reading thispaper related to kernel SVM. It states

Support Vector Machine (SVM) (Cortes and Vap- nik, 1995) as the state-of-the-art classification algo- rithm has been widely applied in various scientific do- mains. The use of kernels allows the input samples to be mapped to a Reproducing Kernel Hilbert S- pace (RKHS), which is crucial to solving linearly non- separable problems. While kernel SVMs deliver the state-of-the-art results, the need to manipulate the k- ernel matrix imposes significant computational bottle- neck, making it difficult to scale up on large data.

I didn't get what they mean by manipulate the kernel matrix. I mean lets say I am using the RBF kernel. Then my kernel matrix will have elements of the form

$exp^{\sigma {||x_i-x_j||}_2}{}$

which I can calculate once and then have it there. So what is meant by kernel manipulation

  • $\begingroup$ Can you provide a link to the article in question? $\endgroup$ – Michael Grant Apr 13 '13 at 16:36
  • $\begingroup$ @MichaelGrant. I have added the link to the paper $\endgroup$ – user34790 Apr 13 '13 at 17:06

They are simply referring to the fact that the kernel matrix itself is a central quantity in the algorithm. The problem is that it is $O(n^2)$ in size, where $n$ is the number of points being examined. So the storage and computational requirements surrounding the kernel matrix rapidly become impractical as $n$ gets large.

  • $\begingroup$ Thats what I didn't get even in the linear svm, we can have the matrix which simply consists of the elements $x^Tx$. So it also consumes space isn't it? $\endgroup$ – user34790 Apr 13 '13 at 14:20
  • $\begingroup$ For the linear SVM you never need to form the kernel. $\endgroup$ – Michael Grant Apr 13 '13 at 16:26
  • $\begingroup$ I'm hoping someone else can provide a fuller answer---I am out of town an responding on my iPhone ;) Honestly I think context will help. Kernel methods are styled as a means of regaining efficiency. But it still requires solving a fuller QP. $\endgroup$ – Michael Grant Apr 13 '13 at 16:45

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.