A Simple Method For Solving The Svm Regularization Path For Semidefinite Kernels

Keywords

Active set method; Homotopy methods; Regularization path; support vector machine (SVM)

Abstract

The support vector machine (SVM) remains a popular classifier for its excellent generalization performance and applicability of kernel methods; however, it still requires tuning of a regularization parameter, C, to achieve optimal performance. Regularization path-following algorithms efficiently solve the solution at all possible values of the regularization parameter relying on the fact that the SVM solution is piece-wise linear in C. The SVMPath originally introduced by Hastie et al., while representing a significant theoretical contribution, does not work with semidefinite kernels. Ong et al. introduce a method improved SVMPath (ISVMP) algorithm, which addresses the semidefinite kernel; however, Singular Value Decomposition or QR factorizations are required, and a linear programming solver is required to find the next C value at each iteration. We introduce a simple implementation of the path-following algorithm that automatically handles semidefinite kernels without requiring a method to detect singular matrices nor requiring specialized factorizations or an external solver. We provide theoretical results showing how this method resolves issues associated with the semidefinite kernel as well as discuss, in detail, the potential sources of degeneracy and cycling and how cycling is resolved. Moreover, we introduce an initialization method for unequal class sizes based upon artificial variables that work within the context of the existing path-following algorithm and do not require an external solver. Experiments compare performance with the ISVMP algorithm introduced by Ong et al. and show that the proposed method is competitive in terms of training time while also maintaining high accuracy.

Publication Date

4-1-2016

Publication Title

IEEE Transactions on Neural Networks and Learning Systems

Volume

27

Issue

4

Number of Pages

709-722

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TNNLS.2015.2427333

Socpus ID

84929791815 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84929791815

This document is currently not available here.

Share

COinS