Scaling Up Kernel SVM on Limited Resources: A Low-Rank Linearization Approach

Liang LAN, Zhuang Wang, Shandian Zhe, Wei Cheng, Jun Wang, Kai Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

Kernel support vector machines (SVMs) deliver state-of-the-art results in many real-world nonlinear classification problems, but the computational cost can be quite demanding in order to maintain a large number of support vectors. Linear SVM, on the other hand, is highly scalable to large data but only suited for linearly separable problems. In this paper, we propose a novel approach called low-rank linearized SVM to scale up kernel SVM on limited resources. Our approach transforms a nonlinear SVM to a linear one via an approximate empirical kernel map computed from efficient kernel low-rank decompositions. We theoretically analyze the gap between the solutions of the approximate and optimal rank- k kernel map, which in turn provides guidance on the sampling scheme of the Nyström approximation. Furthermore, we extend it to a semisupervised metric learning scenario in which partially labeled samples can be exploited to further improve the quality of the low-rank embedding. Our approach inherits rich representability of kernel SVM and high efficiency of linear SVM. Experimental results demonstrate that our approach is more robust and achieves a better tradeoff between model representability and scalability against state-of-the-art algorithms for large-scale SVMs.

Original languageEnglish
Article number8392379
Pages (from-to)369-378
Number of pages10
JournalIEEE Transactions on Neural Networks and Learning Systems
Volume30
Issue number2
DOIs
Publication statusPublished - Feb 2019

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Artificial Intelligence

User-Defined Keywords

  • Large-scale learning
  • low-rank approximation
  • metric learning
  • support vector machine (SVM)

Fingerprint

Dive into the research topics of 'Scaling Up Kernel SVM on Limited Resources: A Low-Rank Linearization Approach'. Together they form a unique fingerprint.

Cite this