An Object-Oriented Support Vector Machine Toolbox for Matlab

Gavin C. Cawley ^{∗}

September 15, 2000

Abstract

1 Introduction

1.1 Support Vector Classification

The support vector machine (Boser et al., 1992; Cortes and Vapnik, 1995), given labelled training data

D = {(x_{i}, y_{i})}_{i=1}^{ℓ} , x_{i} ∈ X ⊂ ℝ^{d}, y_{i} ∈ Y = {−1, +1},

constructs a maximal margin linear classifier in a high dimensional feature space, Φ(x), defined by a positive definite kernel function, k(x, x′), specifying an inner product in the feature space,

Φ(x).Φ(x′) = k(x, x′).

A common kernel is the Gaussian radial basis function (RBF),

k(x, x′) = e^{−||x−x′||^{2}/2σ^{2}}.

The function implemented by a support vector machine is given by

f(x) = {∑_{i=1}^{ℓ} α_{i}y_{i}k(x_{i}, x)} − b.  (1)

To find the optimal coefficients, α, of this expansion it is sufficient to maximise the functional,

W (α) = ∑_{i=1}^{ℓ} α_{i} − \frac{1}{2} ∑_{i,j=1}^{ℓ} y_{i}y_{j}α_{i}α_{j}k(x_{i}, x_{j}),  (2)

∗G. C. Cawley is with the School of Information Systems, University of East Anglia, Norwich, Norfolk, U.K. NR4 7TJ. E-mail: gcc@sys.uea.ac.uk .

in the non-negative quadrant,

0 ≤ α_{i} ≤ C,  i = 1, …, ℓ,  (3)

subject to the constraint,

∑_{i=1}^{ℓ} α_{i}y_{i} = 0.  (4)

C is a regularisation parameter, controlling a compromise between maximising the margin and minimising the number of training set errors. The Karush-Kuhn-Tucker (KKT) conditions can be stated as follows:

α_{i} = 0 ⟹ y_{i}f(x_{i}) ≥ 1,  (5)
0 < α_{i} < C ⟹ y_{i}f(x_{i}) = 1,  (6)
α_{i} = C ⟹ y_{i}f(x_{i}) ≤ 1.  (7)

These conditions are satisfied for the set of feasible Lagrange multipliers, α^{0} = {α_{1}^{0}, α_{2}^{0}, …, α_{ℓ}^{0}}, maximising the objective function given by equation 2. The bias parameter, b, is selected to ensure that the second KKT condition is satisfied for all input patterns corresponding to non-bound Lagrange multipliers. Note that in general only a limited number of Lagrange multipliers, α, will have nonzero values; the corresponding input patterns are known as support vectors. Let I be the set of indices of patterns corresponding to non-bound Lagrange multipliers,

I = {i : 0 < α_{i}^{0} < C},

and similarly, let J be the set of indices of patterns with Lagrange multipliers at the upper bound C,

J = {i : α_{i}^{0} = C}.

Equation 1 can then be written as an expansion over support vectors,

f(x) = { ∑_{i∈{I,J }} α_{i}^{0}y_{i}k(x_{i}, x)} − b.  (8)

For a full exposition of the support vector method, see the any of the excellent books (Vapnik, 1995; Vapnik, 1998; Cristianini and Shawe-Taylor, 2000) or tutorial articles () available.

2 Training Algorithms

3 Model Selection

4 Summary

5 Acknowledgements

References

Boser, B., Guyon, I., and Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on computational learning theory, pages 144–152, Pittsburgh. ACM.

Cortes, C. and Vapnik, V. (1995). Support vector networks. Machine Learning, 20:1–25.

Cristianini, N. and Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines (and other kernel-based learning methods). Cambridge University Press, Cambridge, U.K.

Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer-Verlag, New York.

Vapnik, V. N. (1998). Statistical Learning Theory. Wiley Series on Adaptive and Learning Systems for Signal Processing, Communications and Control. Wiley, New York.