LIBSVM: A Library for Support Vector Machines

1 LIBSVM: A Library for Support Vector MachinesChih-Chung Chang and Chih-Jen LinDepartment of Computer ScienceNational Taiwan University, Taipei, TaiwanEmail: version: 2001 Last updated: January 20, 2021 AbstractLIBSVM is a Library for Support Vector Machines (SVMs). We have beenactively developing this package since the year 2000. The goal is to help usersto easily apply SVM to their applications. LIBSVM has gained wide popu-larity in machine learning and many other areas. In this article, we presentall implementation details of LIBSVM. Issues such as solving SVM optimiza-tion problems, theoretical convergence, multi-class classification, probabilityestimates, and parameter selection are discussed in :Classification,LIBSVM, optimization, regression, Support Vector ma-chines, SVM1 IntroductionSupport Vector Machines (SVMs) are a popular machine learning method for classifi-cation, regression, and other learning tasks.

2 Since the year 2000, we have been devel-oping the packageLIBSVMas a Library for Support Vector Machines . The Web addressof the package is ~ cur-rently one of the most widely used SVM software. In this article,1we present allimplementation details ofLIBSVM. However, this article does not intend to teachthe practical use ofLIBSVM. For instructions of usingLIBSVM, see theREADME fileincluded in the package, theLIBSVM FAQ,2and 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 document was created in 2001 and has been maintained ~cjlin/ FAQ: ~cjlin/ 1: Representative works in some domains that have successfully worksComputer visionLIBPMK (Grauman and Darrell, 2005)Natural language processingMaltparser (Nivre et al.)

3 , 2007)NeuroimagingPyMVPA (Hanke et al., 2009)BioinformaticsBDVal (Dorff et al., 2010)1. SVC: Support Vector classification (two-class and multi-class).2. SVR: Support Vector One-class typical use ofLIBSVM involves two steps: first, training a data set to obtain amodel and second, using the model to predict information of a testing data set. ForSVC and SVR,LIBSVMcan also output probability estimates. Many extensions ofLIBSVMare available is structured as Main directory: core C/C++ programs and sample data. In particular, the training and testing algorithms, where details are describedin this Thetoolsub-directory: this sub-directory includes tools for checking dataformat and for selecting SVM Other sub-directories contain pre-built binary files and interfaces to other lan- been widely used in many areas.

4 From 2000 to 2010, there weremore than 250,000 downloads of the package. In this period, we answered more than10,000 emails from users. Table 1 lists representative works in some domains thathave successfully article is organized as follows. In Section 2, we describe SVM formulationssupported inLIBSVM:C- Support Vector classification (C-SVC), - Support vectorclassification ( -SVC), distribution estimation (one-class SVM), - Support Vector re-gression ( -SVR), and - Support Vector regression ( -SVR). Section 3 then discussesperformance measures, basic usage, and code organization. All SVM formulations3 LIBSVM Tools: ~ inLIBSVMare quadratic minimization problems.

5 We discuss the opti-mization algorithm in Section 4. Section 5 describes two implementation techniquesto reduce the running time for minimizing SVM quadratic problems: shrinking some special settings for unbalanced data; details arein Section 6. Section 7 discusses our implementation for multi-class 8 presents how to transform SVM decision values into probability values. Pa-rameter selection is important for obtaining good SVM models. Section 9 presents asimple and useful parameter selection tool inLIBSVM. Finally, Section 10 concludesthis SVM FormulationsLIBSVM supports various SVM formulations for classification, regression, and distri-bution estimation.

6 In this section, we present these formulations and give correspond-ing references. We also show performance measures used Vector ClassificationGiven training vectorsxi Rn,i= 1,..,l, in two classes, and an indicator vectory Rlsuch thatyi {1, 1},C-SVC (Boser et al., 1992; Cortes and Vapnik, 1995)solves the following primal optimization ,b, 12wTw+Cl i=1 i(1)subject toyi(wT (xi) +b) 1 i, i 0,i= 1,..,l,where (xi) mapsxiinto a higher-dimensional space andC >0 is the regularizationparameter. Due to the possible high dimensionality of the Vector variablew, usuallywe solve the following dual 12 TQ eT subject toyT = 0,(2)0 i C, i= 1,..,l,wheree= [1,..,1]Tis the Vector of all ones,Qis anlbylpositive semidefinitematrix,Qij yiyjK(xi,xj), andK(xi,xj) (xi)T (xj) is the kernel problem (2) is solved, using the primal-dual relationship, the optimalwsatisfiesw=l i=1yi i (xi)(3)and the decision function issgn(wT (x) +b)= sgn(l i=1yi iK(xi,x) +b).

7 We storeyi i i,b, label names,4support vectors, and other information such askernel parameters in the model for - Support Vector ClassificationThe - Support Vector classification (Sch olkopf et al., 2000) introduces a new parameter (0,1]. It is proved that an upper bound on the fraction of training errors anda lower bound of the fraction of Support training vectorsxi Rn,i= 1,..,l, in two classes, and a vectory Rlsuch thatyi {1, 1}, the primal optimization problem isminw,b, , 12wTw +1ll i=1 isubject toyi(wT (xi) +b) i,(4) i 0,i= 1,..,l, dual problem ismin 12 TQ subject to0 i 1/l, i= 1,..,l,(5)eT ,yT = 0,whereQij=yiyjK(xi,xj). Chang and Lin (2001) show that problem (5) is feasibleif and only if 2 min(#yi= +1,#yi= 1)l 1,so the usable range of is smaller than (0,1].))

8 4 InLIBSVM, any integer can be a label name, so we map label names to 1 by assigning the firsttraining instance to havey1= + decision function issgn(l i=1yi iK(xi,x) +b).It is shown thateT can be replaced byeT = (Crisp and Burges, 2000;Chang and Lin, 2001). InLIBSVM, we solve a scaled version of problem (5) becausenumerically imay be too small due to the constraint i 1 12 TQ subject to0 i 1, i= 1,..,l,(6)eT = l,yT = is optimal for the dual problem (5) and is optimal for the primal problem(4), Chang and Lin (2001) show that / is an optimal solution ofC-SVM withC= 1/( l). Thus, inLIBSVM, we output ( / ,b/ ) in the Distribution Estimation (One-class SVM)One-class SVM was proposed by Sch olkopf et al.

9 (2001) for estimating the Support ofa high-dimensional distribution. Given training vectorsxi Rn,i= 1,..,lwithoutany class information, the primal problem of one-class SVM isminw, , 12wTw +1 ll i=1 isubject towT (xi) i, i 0,i= 1,.., dual problem ismin 12 TQ subject to0 i 1/( l),i= 1,..,l,(7)eT = 1,whereQij=K(xi,xj) = (xi)T (xj). The decision function issgn(l i=1 iK(xi,x) ).5 More precisely, solving (6) obtains = l. Because =l , we have / = / . Hence, inLIBSVM, we calculate / .5 Similar to the case of -SVC, inLIBSVM, we solve a scaled version of (7).min 12 TQ subject to0 i 1, i= 1,..,l,(8)eT = - Support Vector Regression ( -SVR)Consider a set of training points,{(x1,z1).}

10 ,(xl,zl)}, wherexi Rnis a featurevector andzi R1is the target output. Under given parametersC >0 and >0,the standard form of Support Vector regression (Vapnik, 1998) isminw,b, , 12wTw+Cl i=1 i+Cl i=1 isubject towT (xi) +b zi + i,zi wT (xi) b + i, i, i 0,i= 1,.., dual problem ismin , 12( )TQ( ) + l i=1( i+ i) +l i=1zi( i i)subject toeT( ) = 0,(9)0 i, i C,i= 1,..,l,whereQij=K(xi,xj) (xi)T (xj).After solving problem (9), the approximate function isl i=1( i+ i)K(xi,x) + , we output in the - Support Vector Regression ( -SVR)Similar to -SVC, for regression, Sch olkopf et al. (2000) use a parameter (0,1]to control the number of Support vectors. The parameter in -SVR becomes a6parameter here.)