2011 LIBSVMALibraryforSupportVectorM

(Chang & Lin, 2011) ⇒ Chih-Chung Chang, and Chih-Jen Lin. (2011). “LIBSVM: A Library for Support Vector Machines.” In: ACM Transactions on Intelligent Systems and Technology (TIST) Journal, 2(3). doi:10.1145/1961189.1961199

Subject Headings: LIBSVM.

Notes

Cited By

Quotes

Author Keywords

Classification]], LIBSVM, optimization, regression, support vector machines, SVM.

Abstract

LIBSVM is a library for Support Vector Machines (SVMs). We have been actively developing this package since the year 2000. The goal is to help users to easily apply SVM to their applications. LIBSVM has gained wide popularity in machine learning and many other areas. In this article, we present all implementation details of LIBSVM. Issues such as solving SVM optimization problems, theoretical convergence, multiclass classification, probability estimates and parameter selection are discussed in detail.

1 Introduction

Support Vector Machines (SVMs) are a popular machine learning method for classification, regression, and other learning tasks. Since the year 2000, we have been developing the package LIBSVM as a library for support vector machines. The Web address of the package is at http://www.csie.ntu.edu.tw/~cjlin/libsvm. LIBSVM is currently one of the most widely used SVM software. In this article,1 we present all implementation details of LIBSVM. However, this article does not intend to teach the practical use of LIBSVM. For instructions of using LIBSVM, see the README file included in the package, the LIBSVM FAQ,2 and the practical guide by Hsu et al. (2003). An earlier version of this article was published in Chang and Lin (2011).

LIBSVM supports the following learning tasks.

SVC: support vector classification (two-class and multi-class).
SVR: support vector regression.
One-class SVM.

Table 1: Representative works in some domains that have successfully used LIBSVM.
Domain Representative works
Computer vision LIBPMK (Grauman and Darrell, 2005)
Natural language processing Maltparser (Nivre et al., 2007)
Neuroimaging PyMVPA (Hanke et al., 2009)
Bioinformatics BDVal (Dorfi et al., 2010)

A typical use of LIBSVM involves two steps: first, training a data set to obtain a model and second, using the model to predict information of a testing data set. For SVC and SVR, LIBSVM can also output probability estimates. Many extensions of LIBSVM are available at libsvmtools.3

The LIBSVM package is structured as follows.

. Main directory: core C/C++ programs and sample data. In particular, the file svm.cpp implements training and testing algorithms, where details are described in this article.
. The tool sub-directory: this sub-directory includes tools for checking data format and for selecting SVM parameters.
. Other sub-directories contain pre-built binary files and interfaces to other languages/software.

LIBSVM has been widely used in many areas. From 2000 to 2010, there were more than 250,000 downloads of the package. In this period, we answered more than 10,000 emails from users. Table 1 lists representative works in some domains that have successfully used LIBSVM.

…

2 SVM Formulations

LIBSVM supports various SVM formulations for classification, regression, and distribution estimation. In this section, we present these formulations and give corresponding references. We also show performance measures used in LIBSVM.

2.1 C-Support Vector Classification

Given training vectors [math]\displaystyle{ x_i \in R^n, i = 1...l }[/math], in two classes, and an indicator vector [math]\displaystyle{ y \in R^l }[/math] such that [math]\displaystyle{ y_i \in {1,-1} }[/math], C-SVC (Boser et al., 1992; Cortes and Vapnik, 1995) solves the following primal optimization problem.

[math]\displaystyle{ min w;b;� 1 2 wTw + C Xl i=1 �i,\lt math\gt (1) subject to y_i(wT�(xi) + b) � 1 .. �i; �i � 0; i = 1; : : : ; l; where \lt math\gt \phi(x_i) }[/math] maps [math]\displaystyle{ x_i }[/math] into a higher-dimensional space and C > 0 is the regularization parameter. Due to the possible high dimensionality of the vector variable w, usually we solve the following dual problem.

min

� 1 2 �TQ� .. eT� subject to yT� = 0; (2) 0 � �i � C; i = 1; : : : ; l; where e = [1; : : : ; 1]T is the vector of all ones, Q is an l by l positive semidefinite matrix, Qij � yiyjK(xi; xj), and K(xi; xj) � �(xi)T�(xj) is the kernel function. 3

After problem (2) is solved, using the primal-dual relationship, the optimal w satisfies w = Xl i=1 yiffiff(xi) (3) and the decision function is sgn .. wT�(x) + b � = sgn

Xl i=1 yiffiK(xi; x) + b !

We store yiffi 8i, b, label names,4 support vectors, and other information such as kernel parameters in the model for prediction.

2.2 �-Support Vector Classification

The �-support vector classification (Sch?olkopf et al., 2000) introduces a new parameter � 2 (0; 1]. It is proved that � an upper bound on the fraction of training errors and a lower bound of the fraction of support vectors.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 LIBSVMALibraryforSupportVectorM	Chih-Jen Lin Chih-Chung Chang			LIBSVM: A Library for Support Vector Machines				10.1145/1961189.1961199		2011