Support vector machines with indefinite kernels

Ibrahim Alabdulmohsin, Xin Gao, Xiangliang Zhang

Research output: Contribution to journalConference articlepeer-review

21 Scopus citations

Abstract

Training support vector machines (SVM) with indefinite kernels has recently attracted attention in the machine learning community. This is partly due to the fact that many similarity functions that arise in practice are not symmetric positive semidefinite, i.e. the Mercer condition is not satisfied, or the Mercer condition is difficult to verify. Previous work on training SVM with indefinite kernels has generally fallen into three categories: (1) positive semidefinite kernel approximation, (2) non-convex optimization, and (3) learning in Krein spaces. All approaches are not fully satisfactory. They have either introduced sources of inconsistency in handling training and test examples using kernel approximation, settled for approximate local minimum solutions using non-convex optimization, or produced non-sparse solutions. In this paper, we establish both theoretically and experimentally that the 1-norm SVM, proposed more than 10 years ago for embedded feature selection, is a better solution for extending SVM to indefinite kernels. More specifically, 1-norm SVM can be interpreted as a structural risk minimization method that seeks a decision boundary with large similarity margin in the original space. It uses a linear programming formulation that remains convex even if the kernel matrix is indefinite, and hence can always be solved quite efficiently. Also, it uses the indefinite similarity function (or distance) directly without any transformation, and, hence, it always treats both training and test examples consistently. Finally, it achieves the highest accuracy among all methods that train SVM with indefinite kernels with a statistically significant evidence while also retaining sparsity of the support vector set.

Original languageEnglish (US)
Pages (from-to)32-47
Number of pages16
JournalJournal of Machine Learning Research
Volume39
Issue number2014
StatePublished - 2014
Event6th Asian Conference on Machine Learning, ACML 2014 - Nha Trang, Viet Nam
Duration: Nov 26 2014Nov 28 2014

Bibliographical note

Publisher Copyright:
© 2014 I. Alabdulmohsin, X. Gao & X. Zhang.

Keywords

  • Indefinite kernels
  • Linear programming
  • Similarity-based classification
  • Supervised learning
  • Support vector machines

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Support vector machines with indefinite kernels'. Together they form a unique fingerprint.

Cite this