台湾林智仁教授开发libsvm编译软件

LIBSVM: a Library for Support Vector Machines

Chih-Chung Chang and Chih-Jen Lin

∗

Last updated: February 27, 2009

Abstract

LIBSVM is a library for support vector machines (SVM). Its goal is to help

users to easily use SVM as a tool. In this document, we present all its imple-

mentation details. For the use of LIBSVM, the README file included in the

package and the LIBSVM FAQ provide the information.

class SVM), -support vector regression (-SVR), and ν-support vector regression

(ν-SVR). We discuss the implementation of solving quadratic problems in Section 3.

Section 4 describes two implementation techniques: shrinking and caching. We also

support different penalty parameters for unbalanced data. Details are in Section 5.

Then Section 6 discusses the implementation of multi-class classification. Parameter

selection is important for obtaining good SVM models. LIBSVM provides simple and

useful tools, which are discussed in Section 7. Section 8 presents the implementation

of probability outputs.

2 Formulations

2.1 C-Support Vector Classification

1

following primal problem:

min

1

2

w

w + C

ξ

Its dual is

subject to y

α = 0, (2.2)

Here training vectors x

by the function φ.

The decision function is

y

K(x

, x) + b

.

such that y

1

2

w

w − νρ +

ξ

2

The dual is:

min

1

2

Qα

subject to 0 ≤ α

e

α ≥ ν, y

α = 0.

In (Crisp and Burges, 2000; Chang and Lin, 2001), it has been shown that e

α ≥ ν

can be replaced by e

α = ν. With this property, in LIBSVM, we solve a scaled version

of (2.3):

e

α = νl,

y

α = 0.

We output α/ρ so the computed decision function is:

sgn

y

(α

, x) + b)

2.3 Distribution Estimation (One-class SVM)

One-class SVM was proposed by Sch¨olkopf et al. (2001) for estimating the support of

a high-dimensional distribution. Given training vectors x

, i = 1, . . . , l without

any class information, the primal form in (Sch¨olkopf et al., 2001) is:

w − ρ +

1

νl

ξ

3

The dual is:

4

where Q

= K(x

) ≡ φ(x

)

2.5 ν-Support Vector Regression (ν-SVR)

Similar to ν-SVC, for regression, Sch¨olkopf et al. (2000) use a parameter ν to control

the number of support vectors. However, unlike ν-SVC, where ν replaces with C,

here ν replaces with the parameter  of -SVR. The primal form is

w

w + C(ν +

∗

)) (2.7)

, ξ

∗

) = 0, e

0 ≤ α

, α

Similarly, the inequality e

(α + α

∗

LIBSVM, we consider C ← C/l, so the dual problem solved is:

∗

) = 0, e

0 ≤ α

, α

The decision function is

5