LIBSVM: A library for support vector machines

1 27 LIBSVM: A library for support vector MachinesCHIH-CHUNG CHANG and CHIH-JEN LIN, National Taiwan UniversityLIBSVM is a library for support vector machines (SVMs). We have been actively developing this packagesince the year 2000. The goal is to help users to easily apply SVM to their applications. LIBSVM has gainedwide popularity in machine learning and many other areas. In this article, we present all implementationdetails of LIBSVM. Issues such as solving SVM optimization problems theoretical convergence multiclassclassification probability estimates and parameter selection are discussed in and Subject Descriptors: [Pattern Recognition]: Design Methodology Classifier designand evaluation; [Numerical Analysis]: Optimization Quadratic programming methodsGeneral Terms: Algorithms, Performance, ExperimentationAdditional Key Words and Phrases: ClassificationLIBSVM optimization regression support vector machinesSVMACM Reference Format:Chang, and Lin, : A library for support vector machines .

2 ACM Trans. Intell. 2, 3, Article 27 (April 2011), 27 INTRODUCTIONS upport vector machines (SVMs) are a popular machine learning method for clas-sification, regression, and other learning tasks. Since the year 2000, we have beendeveloping the packageLIBSVMas a library for support vector one of the most widely used SVM software. In this article,2we present allimplementation details ofLIBSVM. However, this article does not intend to teach thepractical use ofLIBSVM. For instructions of usingLIBSVM,seetheREADME file includedin the package, theLIBSVM FAQ,3and the practical guide by Hsu et al. [2003].LIBSVM supports the following learning tasks.(1) SVC: support vector classification (twoclass and multiclass);(2) SVR: support vector regression.(3) One-class Web address of the package is at document was created in 2001 and has been maintained cjlin/ FAQ: cjlin/ work was supported in part by the National Science Council of Taiwan via the grants NSC 89-2213-E-002-013 and NSC addresses: Chang and Lin (corresponding author), Department of Computer Science,National Taiwan University, Taipei 106, Taiwan; email: to make digital or hard copies of part or all of this work for personal or classroom use is grantedwithout fee provided that copies are not made or distributed for profit or commercial advantage and thatcopies show this notice on the first page or initial screen of a display along with the full citation.

3 Copyrights forcomponents of this work owned by others than ACM must be honored. Abstracting with credit is copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of thiswork in other works requires prior specific permission and/or a fee. Permissions may be requested fromPublications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax+1 (212)869-0481, or 2011 ACM 2157-6904/2011/04-ART27 $ Transactions on Intelligent Systems and Technology, Vol. 2, No. 3, Article 27, Publication date: April Chang and LinTable I. Representative Works in Some Domains that have SuccessfullyUsed worksComputer visionLIBPMK [Grauman and Darrell 2005]Natural language processingMaltparser [Nivre et al.]

4 2007]NeuroimagingPyMVPA [Hanke et al. 2009]BioinformaticsBDVal [Dorff et al. 2010]A typical use ofLIBSVM involves two steps: first, training a dataset to obtain a modeland second, using the model to predict information of a testing dataset. For SVC andSVR,LIBSVMcan also output probability estimates. Many extensions ofLIBSVM areavailable is structured as follows.(1) Main directory: core C/C++ programs and sample data. In particular, the training and testing algorithms, where details are describedin this article.(2) Thetoolsubdirectory. This subdirectory includes tools for checking data formatand for selecting SVM parameters.(3) Other subdirectories contain prebuilt binary files and interfaces to other lan- been widely used in many areas. From 2000 to 2010, there were morethan 250,000 downloads of the package.

5 In this period, we answered more than 10,000emails from users. Table I lists representative works in some domains that have suc-cessfully article is organized as follows. In Section 2, we describe SVM formulations sup-ported inLIBSVM:C- support vector Classification (C-SVC), - support vector Classifi-cation ( -SVC), distribution estimation (one-class SVM), - support vector Regression( -SVR), and - support vector Regression ( -SVR). Section 3 then discusses perfor-mance measures, basic usage, and code organization. All SVM formulations supportedinLIBSVMare quadratic minimization problems. We discuss the optimization algo-rithm in Section 4. Section 5 describes two implementation techniques to reduce therunning time for minimizing SVM quadratic problems: shrinking and some special settings for unbalanced data; details are in Section 6.

6 Section 7discusses our implementation for multiclass classification. Section 8 presents how totransform SVM decision values into probability values. Parameter selection is impor-tant for obtaining good SVM models. Section 9 presents a simple and useful parameterselection tool inLIBSVM. Finally, Section 10 concludes this SVM FORMULATIONSLIBSVM supports various SVM formulations for classification, regression, and distribu-tion estimation. In this section, we present these formulations and give correspondingreferences. 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] solves4 LIBSVM Tools: Transactions on Intelligent Systems and Technology, Vol.

7 2, No. 3, Article 27, Publication date: April : A library for support vector Machines27:3the following primal optimization problem:minw,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 problem:min 12 TQ eT subject toyT =0,(2)0 i C,i=1,..,l,wheree=[1,..,1]Tis the vector of all ones,Qis anlbylpositive semidefinite matrix,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).We storeyi i i,b, label names,5support vectors, and other information such as kernelparameters in the model for - support vector ClassificationThe - support vector classification [Sch olkopf et al.]

8 2000] introduces a new parameter (0,1]. It is proved that an upper bound on the fraction of training errors and alower bound of the fraction of support training vectorsxi Rn,i=1,..,l, in two classes, and a vectory Rlsuchthatyi {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 to 0 i 1/l,i=1,..,l,(5)eT ,yT =0,5 InLIBSVM, any integer can be a label name, so we map label names to 1 by assigning the first traininginstance to havey1=+ Transactions on Intelligent Systems and Technology, Vol. 2, No. 3, Article 27, Publication date: April Chang and LinwhereQij=yiyjK(xi,xj). Chang and Lin [2001] show that problem (5) is feasible ifandonlyif 2min(#yi=+1,#yi= 1)l 1,so the usable range of is smaller than (0,1].))

9 The decision function issgn(l i=1yi iK(xi,x)+b).It is shown thateT can be replaced byeT = [Crisp and Burges 2000; Changand Lin 2001]. InLIBSVM, we solve a scaled version of problem (5) because numerically imay be too small due to the constraint i 1 12 TQ subject to 0 i 1,i=1,..,l,(6)eT = l,yT =0If 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. [2001] for estimating the support of ahigh-dimensional distribution. Given training vectorsxi Rn,i=1,..,lwithout anyclass information, the primal problem of one-class SVM isminw, , 12wTw +1 ll i=1 isubject towT (xi) i, i 0,i=1.

10 , dual problem ismin 12 TQ subject to 0 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) ).6 More precisely, solving (6) obtains = l. Because =l ,wehave / = / .Hence,inLIBSVM,wecalculate / .ACM Transactions on Intelligent Systems and Technology, Vol. 2, No. 3, Article 27, Publication date: April : A library for support vector Machines27:5 Similartothecaseof -SVC, inLIBSVM, we solve a scaled version of (7).min 12 TQ subject to 0 i 1,i=1,..,l,(8)eT = - support vector Regression ( -SVR)Consider a set of training points,{(x1,z1),..,(xl,zl)}, wherexi Rnis a feature vectorandzi R1is the target output. Under given parametersC>0and >0, the standardform 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.