An Introduction to Support Vector Machines

Bernhard Schölkopa bernhard.schoelkopf@tuebingen.mpg.de    a Max-Planck-Institut für biologische Kybernetik, Spemannstr. 38, Tübingen, Germany

This article gives a short introduction to the main ideas of statistical learning theory, support vector machines, and kernel feature spaces.1

1 An Introductory Example

Suppose we are given empirical data

1y1,…,xmym∈X×±1.

Here, the domain is some nonempty set that the patterns xi are taken from; the yi are called labels or targets. Unless stated otherwise, indices i and j will always be understood to run over the training set, i.e., i, j = 1,…, m.

Note that we have not made any assumptions on the domain other than it being a set. In order to study the problem of learning, we need additional structure. In learning, we want to be able to generalize to unseen data points. In the case of pattern recognition, given some new pattern ∈X, we want to predict the corresponding y ∈ {± 1}. By this we mean, loosely speaking, that we choose y such that (x, y) is in some sense similar to the training examples. To this end, we need similarity measures in and in {± 1}. The latter is easier, as two target values can only be identical or different. 2 For the former, we require a similarity measure

:X×X→ℝ,xx′→kxx′,

i.e., a function that, given two examples x and x′, returns a real number characterizing their similarity. For reasons that will become clear later, the function k is called a kernel [12,1,6].

A type of similarity measure that is of particular mathematical appeal are dot products. For instance, given two vectors ,x'∈ℝN, the canonical dot product is defined as

⋅x′:=∑n=1Nxnx′n.

Here, [x]n denotes the n-th entry of x.

The geometrical interpretation of this dot product is that it computes the cosine of the angle between the vectors x and x′, provided they are normalized to length 1. Moreover, it, allows computation of the length of a vector x as ⋅x, and of the distance between two vectors as the length of the difference vector. Therefore, being able to compute dot products amounts to being able to carry out all geometrical constructions that can be formulated in terms of angles, lengths and distances.

Note, however, that we have not made the assumption that the patterns live in a dot, product space. In order to be able to use a dot product as a similarity measure, we therefore first need to embed them into some dot, product space , which need not be identical to N. To this end, we use a map

:X→ℋx↦x:=Φx.

The space is called a feature space. To summarize, embedding the data into has three benefits.

1. It lets us define a similarity measure from the dot product in ,

xx′:=x⋅x′=Φx⋅Φx′.

2. It allows us to deal with the patterns geometrically, and thus lets us study learning algorithms using linear algebra and analytic geometry.

3. The freedom to choose the mapping Φ will enable us to design a large variety of learning algorithms. For instance, consider a situation where the inputs already live in a dot product space. In that case, we could directly define a similarity measure as the dot product. However, we might still choose to first apply a nonlinear map Φ to change the representation into one that is more suitable for a given problem and learning algorithm.

We are now in the position to describe a simple pattern recognition algorithm. The idea is to compute the means of the two classes in feature space,

1=1m1∑i:yi=+1xi,

2=1m2∑i:yi=−1xi,

where m1 and m2 are the number of examples with positive and negative labels, respectively. We then assign a new point x to the class whose mean is closer to it. This geometrical construction can be formulated in terms of dot products. Half-way in between c1 and c2 lies the point c := (c1 + c2) /2. We compute the class of x by checking whether the vector connecting c and x encloses an angle smaller than π/2 with the vector w := c1 − c2 connecting the class means, in other words

=sgnx−c⋅wy=sgnx−c1+c2/2⋅c1−c2=sgnx⋅c1−x⋅c2+b.

Here, we have defined the offset

:=12∥c2∥2−∥c1∥2.

It will prove instructive to rewrite this expression in terms of the patterns xi in the input domain . Note that we do not have a dot product in , all we have is the similarity measure k (cf. (5)). Therefore, we need to rewrite everything in terms of the kernel k evaluated on input patterns. To this end, substitute (6) and (7) into (8) to get the decision function

=sgn1m1∑i:yi=+1x⋅xi−1m2∑i:yi=−1x⋅xi+b=sgn1m1∑i:yi=+1kx⋅xi−1m2∑i:yi=−1kxxi+b.

Similarly, the offset becomes

:=121m22∑ij:yi=yj=−1kxixj−1m12∑i:jyi=yj=+1kxixj.

Let us consider one well-known special case of this type of classifier. Assume that the class means have the same distance to the origin (hence b = 0), and that k can be viewed as a density, i.e., it is positive and has integral 1,

Xkxx′dx=1forallx′∈X.

In order to state this assumption, we have to require that we can define an integral on .

If the above holds true, then (10) corresponds to the so-called Bayes decision boundary separating the two classes, subject to the assumption that the two classes were generated from two probability distributions that are correctly estimated by the Parzen windows estimators of the two classes,

1x:=1m1∑i:yi=+1kxxi

2x:=1m2∑i:yi=−1kxxi.

Given some point x, the label is then simply computed by checking which of the two, p1(x) or p2(x), is larger, leading to (10). Note that this decision is the best we can do if we have no prior information about the probabilities of the two classes, or a uniform prior distribution. For further details, see [15].

The classifier (10) is quite close to the types of learning machines that we will be interested in. It is linear in the feature space (Equation (8)), while in the input domain, it is represented by a kernel expansion (Equation (10)). It is example-based in the sense that the kernels are centered on the training examples, i.e., one of the two arguments of the kernels is always a training example. This is a general property of kernel methods, due to the Representer Theorem [11,15]. The main point where the more sophisticated techniques to be discussed later will deviate from (10) is in the selection of the examples that the kernels are centered on, and in the weight that is put on the individual kernels in the decision function. Namely, it will no longer be the case that all training examples appear in the kernel expansion, and the weights of the kernels in the expansion will no longer be uniform. In the feature space representation, this statement corresponds to saying that we will study all normal vectors w of decision hyperplanes that can be represented as linear combinations of the training examples. For instance, we might want to remove the influence of patterns that are very far away from the decision boundary, either since we expect that they will not improve the generalization error of the decision function, or since we...