Review on Energy Resilience

Machine Leaming, 20, 2 7 3 - 2 9 7 (1995) ~) 1995 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.

Support-Vector Networks

C O R I N N A CORTES V L A D I M I R VAPNIK AT&T Bell Labs., Hohndel, N J 07733, USA

corinna@ neurai.att.com [email protected]

Editor: Lorenza Saitta

A b s t r a c t . The support-vector network is a new leaming machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high- dimension feature space. In this feature space a linear decision surface is constructed. Special properties o f the decision surface ensures h i g h generalization ability o f the learning machine. The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data.

High generalization ability o f support-vector networks utilizing polynomial input transformations is demon- strated. We also compare the performance o f the support-vector network to various classical learning algorithms that all took part in a b e n c h m a r k study o f Optical Character Recognition.

Keywords: pattern recognition, efficient learning algorithms, neural networks, radial basis function classifiers, polynomial classifiers.

1. Introduction

M o r e than 60 y e a r s a g o R.A. Fisher (Fisher, 1936) suggested the first algorithm for pattern recognition. H e c o n s i d e r e d a m o d e l o f two n o r m a l distributed populations, N ( m t , ~ 1 ) and N ( m 2 , ~ 2 ) o f n d i m e n s i o n a l vectors x with m e a n vectors m l and m2 and c o - v a r i a n c e m a t r i c e s E t and E 2 , and s h o w e d that the o p t i m a l (Bayesian) solution is a quadratic decision function:

[ ~ 1 IE2I] (1) Fsq(X) = sign (x - ml)7"E~-~(x - m a ) - ~ ( x - m 2 ) : r E f l ( x - m2) + In 1-~11_] "

In the c a s e w h e r e E1 = E z = ~ the quadratic decision function (1) degenerates to a linear function:

Flin(X) = s i g n [ ( m t - m 2 ) T ~ i - l x - l ( m l r ~ - l m l 2 -- m T ~ - l m 2 ) ] . (2)

To e s t i m a t e the quadratic decision function one has to d e t e r m i n e ~ free p a r a m e t e r s . To e s t i m a t e the linear function only n free p a r a m e t e r s h a v e to b e determined. In the case w h e r e the n u m b e r o f observations is small (say less than 10 n 2) estimating o(n z) p a r a m e t e r s is not reliable. F i s h e r therefore r e c o m m e n d e d , even in the case o f ~1 ~ ~32, to use the linear d i s c r i m i n a t o r function (2) with ~ o f the f o r m :

Y]~ = "gY]l -~- (1 - - "Y)~-]2, ( 3 )

w h e r e r is s o m e constant 1. Fisher also r e c o m m e n d e d a linear decision function for the case w h e r e the two distributions are not normal. A l g o r i t h m s for pattern r e c o g n i t i o n

274 CORTES A N D VAPNIK

[ ]

dot-product I

\ I dot-products

perceptron output weights of the output unit,

e~ 1 . . . . . cc 5

output from the 5 hidden units: z 1 ..... z 5

weights of the 5 hidden units ~ i l

" ~ " output from the 4 hidden units ~ ~ ~ weights of the 4 hidden units

dot-products

ut vector, x

Figure 1. A simple feed-forward perceptron with 8 input units, 2 layers o f hidden units, and I output unit. The gray-shading o f the vector entries reflects their numeric value.

were therefore from the very beginning associated with the construction o f linear deci- sion surfaces.

In 1962 Rosenblatt (Rosenblatt, 1962) explored a different kind of learning machines: perceptrons or neural networks. The perceptron consists o f connected neurons, where e a c h neuron implements a separating hyperplane, so the perceptron as a whole implements a piecewise linear separating surface. See Fig. 1.

No algorithm that minimizes the error on a set of vectors by adjusting all the weights o f the network was found in Rosenblatt's time, and Rosenblatt suggested a scheme where only the weights o f the output unit were adaptive. According to the fixed setting of the other weights the input vectors are non-linearly transformed into the feature space, Z, o f the last layer o f units. In this space a linear decision function is constructed:

I ( x ) = sign(~iotizi(x)) (4) by adjusting the weights oti from the ith hidden unit to the output unit so as to minimize some error measure over the training data. As a result o f Rosenblatt's approach, construction o f decision rules was again associated with the construction of linear hyperplanes in some space.

An algorithm that allows for all weights of the neural network to adapt in order locally to minimize the error on a set of vectors belonging to a pattern recognition problem was found in 1986 (Rumelhart, Hinton & Williams, 1986, 1987; Parker, 1985; LeCun, 1985) when the back-propagation algorithm was discovered. The solution involves a slight modification of the mathematical model of neurons. Therefore, neural networks implement "piece-wise linear-type" decision functions.

In this article we construct a new type of learning machine, the so-called support-vector network. The support-vector network implements the following idea: it maps the input vectors into some high dimensional feature space Z through some non-linear mapping chosen a priori. In this space a linear decision surface is constructed with special properties that ensure high generalization ability of the network.

SUPPORT-VECTOR N E T W O R K S 275

× X

~xX~ O O C) " ~ " ' , ; ~ o p t i m a l margin

o j o 0 = ' o - . , 1 " ' - . \ ~ O 0 0 ö ~ "~'optima, hyperp,an e

F i g u r e 2. An example o f a separable problem in a 2 dimensional space. The support vectors, marked with grey squares, define the margin o f largest separation between the two classes.

EXAMPLE. To obtain a decision surface corresponding to a polynomial o f degree two, one can create a feature space, Z, which has N = @ coordinates of the form:

Z l ~ X 1 , . . . , Z n ~ X n , 2 2

Z n + 1 ~-- X { , . . . , Z 2 n ~ X n ,

Z2n+l ~ X l X 2 , . . . , Z N ~ X n X n - 1 ,

n coordinates,

n coordinates, n(n - 1) - - coordinates,

2

where x = (xl . . . . . xn). The hyperplane is then constructed in this space.

Two problems arise in the above approach: one conceptual and one technical. The con- ceptual problem is how to find a separating hyperplane that will generalize well: the dimen- sionality o f the feature space will be lauge, and not all hyperplanes that separate the training data will necessarily generalize well 2. The technical problem is how computationally to treat such high-dimensional spaces: to construct polynomial of degree 4 or 5 in a 200 dimensionai space it m a y be necessary to construct hyperplanes in a billion dimensional feature space.

The conceptual part o f this problem was solved in 1965 (Vapnik, 1982) for the case of optimal hyperplanes for separable classes. An optimal hyperplane is here defined as the linear decision function with maximal margin between the vectors o f the two classes, see Fig. 2. It was observed that to construct such optimal hyperplanes one only has to take into acconnt a small amount o f the training data, the so called support vectors, which determine this margin. It was shown that if the training vectors are separated without errors by an optimal hyperptane the expectation value of the probability of committing an error on a test example is bounded by the ratio between the expectation value of the number o f support vectors and the number o f training vectors:

E [ n u m b e r of support vectors] E[Pr(error)] _< (5)

number o f training vectors

276 C O R T E S A N D V A P N I K

Note that this bound does not explicitly contain the dimensionality o f the space o f separation. It follows from this bound, that if the optimal hyperplane can be constructed from a small number o f support vectors relative to the training set size the generalization ability will be high----even in an infinite dimensional space. In Section 5 we will demonstrate that the ratio (5) for a real life problems can be as low as 0.03 and the optimal hyperplane generalizes well in a billion dimensional feature space.

Let

w o • z + bo = 0

be the optimal hyperplane in feature space. We will show, that the weights w0 for the optimal hyperplane in the feature space can be written as some linear combination o f support vectors

W0 = ~ OtiZi. (6) support vectors

The linear decision function I (z) in the feature space will accordingly be of the form:

l ( z ) = s i g n ( ~ otizi.z+bo) , \support vectors

(7)

where zi • z is the dot-product between support vectors zi and vector z in feature space. The decision function can therefore be described as a two layer network (Fig. 3).

However, even if the optimal hyperplane generalizes well the technical problem of how to treat the high dimensional feature space remains. In 1992 it was shown (Boser, Guyon, & Vapnik, 1992), that the order o f operations for constructing a decision function can be interchanged: instead o f making a non-linear transformation of the input vectors fol- lowed by dot-products with support vectors in feature space, one can first compare two vectors in input space (by e.g. taking their dot-product or some distance measure), and then make a non-linear transformation o f the value of the result (see Fig. 4). This en- ables the construction of rich classes of decision surfaces, for example polynomial decision surfaces o f arbitrary degree. We will call this type of learning machine a support-vector network 3.

The technique o f support-vector networks was first developed for the restricted case o f separating training data without errors. In this article we extend the approach o f support- vector networks to cover when separation without error on the training vectors is impossible. With this extension we consider the support-vector networks as a new class o f learning machine, as powerful and universal as neural networks. In Section 5 we will demonstrate how well it generalizes for high degree polynomial decision surfaces (up to order 7) in a high dimensional space (dimension 256). The performance of the algorithm is compared to that o f classical learning machines e.g. linear classifiers, k-nearest neighbors classifiers, and neural networks. Sections 2, 3, and 4 are devoted to the major points of the derivation of the algorithm and a discussion o f some of its properties. Details of the derivation are relegated to an appendix.

SUPPORT-VECTOR NETWORKS 277

B cation

w WN

£ U ~ ~ ~ ] suppOrtvectOrs .. in feature space

input vector in feature space

n-linear transformation

" input vector, x

Figure 3. Classification by a support-vector network of an unknown pattern is conceptually done by first trans- forming the pattem into some high-dimensional feature space. An optimal hyperplane constructed in this feature space determines the output. The similarity to a two-layer perceptron can be seen by comparison to Fig. 1.

2. Opümal Hyperplanes

I n t h i s s e c t i o n w e r e v i e w t h e m e t h o d o f o p t i m a l h y p e r p l a n e s (Vapnik, 1982) for s e p a r a t i o n o f t r a i n i n g d a t a w i t h o u t errors. I n t h e n e x t s e c t i o n w e i n t r o d u c e a n o t i o n o f soff m a r g i n s ,

t h a t w i l l a l l o w f o r a n a n a l y t i c t r e a t m e n t o f l e a r n i n g w i t h errors o n t h e t r a i n i n g set.

2.1. The Optimal Hyperplane Algorithm

T h e s e t o f l a b e l e d t r a i n i n g p a t t e r n s

(Yl, Xl) . . . . . (Ye, x~), Yi ~ { - 1 , 1} (8)

is s a i d to b e l i n e a r l y s e p a r a b l e i f t h e r e exists a v e c t o r w a n d a s c a l a r b s u c h t h a t t h e i n e q u a l i t i e s

w . xi + b > 1 i f Yi = 1 ,

w . x i + b < - 1 i f Yi = - 1 , (9)

278 CORTES A N D VAPNIK

A

classification

~ j ~ L a g r a n g e mu[tipliers

~ ~ comparison I ~'1 I J l I ~ 1 u ¢ K ( x k , x

^ I support vectors, x k

[ 2 ] inputvector, x

Figure 4. Classification o f an unknown pattern by a support-vector network. The pattern is in input space zompared to support vectors. The resulting values are non-linearly transformed. A linear function o f these Iransformed values determine the output o f the classifier.

are valid for all elements of the training set (8). Below we write the inequalities (9) in the forma:

yi(W" X i -~- b) > 1, i = 1 . . . . . •. (10)

The optimal hyperplane

w o - x + bo = 0 (11)

is the unique one which separates the training data with a maximal margin: it determines the direction w/Iwl where the distance between the projections of the training vectors of two different classes is maximal, recall Fig. 2. This distance p(w, b) is given by

X ' W X ' W p ( w , b ) = min - - - max (12)

{x:y=l} IW[ {x:y=--l} Iwl

The optimal hyperplane (Wo, bo) is the arguments that maximize the distance (12). It follows from (12) and (10) that

2 2 p(wo, bo) . . . . (13)

Iwol , / ~ . wo

SUPPORT-VECTOR NETWORKS 279

This m e a n s that the o p t i m a l h y p e r p l a n e is the unique one that m i n i m i z e s w • w u n d e r the constraints (10). Constructing an o p t i m a l h y p e r p l a n e is therefore a quadratic p r o g r a m m i n g p r o b l e m .

Vectors xi f o r w h i c h Yi ( W . x i -1- b ) = 1 will b e t e r m e d s u p p o r t v e c t o r s . In A p p e n d i x A. 1 w e show that the v e c t o r wo that d e t e r m i n e s the optimal h y p e r p l a n e can b e written as a linear c o m b i n a t i o n o f training vectors:

£

WO : Z yiot?xi' (14) i=1

w h e r e «o >_ 0. Since « > 0 only for support vectors (see A p p e n d i x ) , the expression (14) represents a c o m p a c t f o r m o f writing Wo. W e also show that to find the v e c t o r o f p a r a m e t e r s of i:

Aó = («0 . . . . . ~ o ) ,

one has to solve the following quadratic p r o g r a m m i n g p r o b l e m :

W ( A ) = A r l - 1 A r D A (15) 2

with r e s p e c t to A v = («1 . . . . . de), subject to the constraints:

A > 0, (16)

A T y = 0, (17)

w h e r e I T = (1 . . . . . 1) is an g - d i m e n s i o n a l unit vector, y r = (Yl . . . . . y~) is the g - d i m e n - sional v e c t o r o f labels, and D is a s y m m e t r i c £ × £ - m a t r i x with e l e m e n t s

D i j = y i Y j X i • x j , i, j = 1 . . . . . 1. (18)

T h e inequality (16) describes the nonnegative quadrant. We therefore have to m a x i m i z e the quadratic f o r m (15) in the nonnegative quadrant, subject to the constraints (17).

W h e n the training data (8) can b e separated without errors w e atso show in A p p e n d i x A the f o l l o w i n g relationship b e t w e e n the m a x i m u m o f the functional (15), the pair (A0, bo), and the m a x i m a l m a r g i n Po f r o m (13):

2 W ( A o ) = ~ o 2. (19)

I f for s o m e A . and large constant Wo the inequality

W ( A , ) > Wo (20)

is valid, one can a c c o r d i n g l y assert that all h y p e r p l a n e s that separate the training data (8) have a m a r g i n

J~ p <

2 8 0 CORTES AND VAPNIK

I f the training set (8) cannot b e separated by a hyperplane, the m a r g i n b e t w e e n patterns o f the two classes b e c o m e s arbitrary small, resulting in the value o f the functional W ( A ) turning arbitrary large. M a x i m i z i n g the functional (15) under constraints (16) and (17) o n e t h e r e f o r e either reaches a m a x i m u m (in this case o n e has constructed the h y p e r p l a n e with the m a x i m a l m a r g i n Po), or one finds that the m a x i m u m exceeds s o m e given (large) constant Wo (in w h i c h case a separation o f the training data with a m a r g i n larger then

is impossible). T h e p r o b l e m o f m a x i m i z i n g functional (15) under constraints (16) and (17) can be solved

v e r y efficiently using the following scheme. Divide the training data into a n u m b e r o f portions with a r e a s o n a b l e small n u m b e r o f training vectors in each portion. Start o u t b y s o l v i n g the quadratic p r o g r a m m i n g p r o b l e m determined b y the first portion o f training data. F o r this p r o b l e m t h e r e are t w o p o s s i b l e outcomes: either this portion o f the data c a n n o t b e separated b y a h y p e r p l a n e (in which case the full set o f data as well c a n n o t be separated), or the o p t i m a l h y p e r p l a n e f o r separating the first portion o f the training data is found.

L e t t h e v e c t o r that m a x i m i z e s functional (15) in the case o f separation o f the first portion be A1. A m o n g the coordinates o f v e c t o r A1 s o m e are equal to zero. T h e y c o r r e s p o n d to n o n - s u p p o r t training vectors o f this portion. M a k e a new set o f training data containing the s u p p o r t vectors f r o m the first portion o f training data and the vectors o f the second portion that do not satisfy constraint (10), w h e r e w is determined b y A1. For this set a new functional W2(A) is constructed and m a x i m i z e d at A2. Continuing this p r o c e s s o f i n c r e m e n t a l l y constructing a solution vector A , c o v e r i n g all the portions o f the training data o n e either finds that it is i m p o s s i b l e to separate the training set without error, or one constructs the o p t i m a l separating h y p e r p l a n e for the full data set, A , = A0. Note, that during this p r o c e s s the value o f the functional W ( A ) is m o n o t o n i c a l l y increasing, since m o r e and m o r e training vectors are considered in the optimization, leading to a s m a l l e r and smaller separation b e t w e e n the t w o classes.

3. The Soft Margin Hyperplane

C o n s i d e r the case w h e r e the training data c a n n o t be separated without error. In this case o n e m a y w a n t to s e p a r a t e the training set with a m i n i m a l n u m b e r o f errors. To express this f o r m a l l y let us introduce s o m e non-negative variables ~i > O, i = 1 . . . . . ~.

W e c a n n o w m i n i m i z e the functional

i=1

(21)

for small ~r > 0, subject to the constraints

yi(w" xi + b) > 1 - ~i, i = 1 . . . . . ~, (22) ~i > 0, i = 1 . . . . . £. (23)

F o r sufficiently small ~r the functional (21) describes the n u m b e r o f the training errors 5. M i n i m i z i n g (21) o n e finds s o m e m i n i m a l subset o f training errors:

(Yi~, xit) . . . . . (yi~,xi~).

SUPPORT-VECTOR NETWORKS 281

If these data are excluded from the training set one can separate the remaining part of the training set without errors. To separate the remaining part of the training data orte can construct an optimal separating hyperplane.

This idea can be expressed formally as: minimize the functional

~w2+CF ( ~ ~ ~ ) i = 1 (24)

subject to constraints (22) and (23), where F(u) is a monotonic convex function and C is a constant.

For sufficiently large C and sufficiently small « , the vector Wo and constant b0, that minimize the functional (24) under constraints (22) and (23), determine the hyperplane that minimizes the number of errors on the training set and separate the rest of the elements with maximal margin.

Note, however, that the problem of constructing a hyperplane which minimizes the number of errors on the training set is in general NP-complete. To avoid NP-completeness of our problem we will consider the case of cr = 1 (the smallest value of a for which the optimization problem (15) has a unique solution). In this case the functional (24) describes (for sufficiently large C) the problem of constructing a separating hyperplane which minimizes the sum of deviations, ~, of training errors and maximizes the margin for the correctly classified vectors. I f the training data can be separated without errors the constructed hyperplane coincides with the optimal margin hyperplane.

In contrast to the case with a < 1 there exists an efficient method for finding the solution of (24) in the case of a = 1. Let us call this solution the soff margin hyperplane.

In Appendix A we consider the problem of minimizing the functional

subject to the constraints (22) and (23), where F(u) is a monotonic convex function with F(0) = 0. To simplify the formulas we only describe the case of F(u) = u 2 in this section. For this function the optimization problem remains a quadratic programming problem.

In Appendix A we show that the vector w, as for the optimal hyperplane algorithm, can be written as a linear combination of support vectors x i :

£ w o ~-~ ~_£ « ° N I X i .

1 i=1 To find the vector A r = (~q . . . . . oee) one has to solve the dual quadratic programming problem of maximizing

W ( A , ~ ) = A r l - I [ A T D A + ~ ] (26)

subject to constraints A T y = 0, (27)

a > 0, (28)

0 < A < a l , ( 2 9 )

282 C O R T E S A N D V A P N I K

where 1, A, Y, and D are the same elements as used in the optimization problem for constructing an optimal hyperplane, 3 is a scalar, and (29) describes coordinate-wise in- equalities.

Note that (29) implies that the smallest admissible value 3 in functional (26) is

~ - Œ m a x = m a x ( « l , . . . , otg).

Therefore to find a soft margin classifier one has to find a vector A that maximizes

W(A) = AT1 - A r D A + (30)

under the constraints A > 0 and (27). This problem differs from the problem ofconstructing an optimal margin classifier only by the additional term with Otmax in the functional (30). Due to this term the solution to the problem of constructing the soft margin classifier is unique and exists for any data set.

The functional (30) is not quadratic because of the term with Otm~x. Maximizing (30) subject to the constraints A > 0 and (27) belongs to the group of so-called convex pro- gramming problems. Therefore, to construct a soft margin classifier one can either solve the convex programming problem in the £-dimensional space of the parameters A, or one can solve the quadratic programming problem in the dual £ + 1 space of the parameters A and 3. In our experiments we construct the soft margin hyperplanes by solving the dual quadratic programming problem.

4. T h e M e t h o d o f C o n v o l u t i o n o f t h e D o t - P r o d u c t in F e a t u r e S p a c e

The algorithms described in the previous sections construct hyperplanes in the input space. To construct a hyperplane in a feature space one first has to transform the n-dimensional input vector x into an N-dimensional feature vector through a choice of an N-dimensional vector function qS:

¢: ffP ---> 9t N.

An N dimensional linear separator w and a bias b is then constructed for the set of transformed vectors

~ ( X i ) : t~l ( X i ) , ~b2(Xi) . . . . . ~ N ( X i ) , i : 1 . . . . . 6 .

Classification of an unknown vector x is done by first transforming the vector to the sepa- rating space (x w-~ ¢ (x)) and then taking the sign of the function

f ( x ) = w - ¢ ( x ) + b. (31)

According to the properties of the soff margin classifier method the vector w can be written as a linear combination of support vectors (in the feature space). That means

£

W : Z yioli~)(Xi)" i=1

(32)

SUPPORT-VECTOR NETWORKS 283

The linearity of the dot-product implies, that the classification function f in (31) for an unknown vector x only depends on the dot-products:

f ( x ) = q~(x)- w + b = S Yi°ti~(x)" ~b(xi) + b. i = 1

(33)

The idea of constructing support-vector networks comes from considering general forms of the dot-product in a Hilbert space (Anderson & Bahadur, 1966):

~b (u)- <p (v) - K (u, v). (34)

According to the Hilbert-Schmidt Theory (Courant & Hilbert, 1953) any symmetric function K ( u , v), with K ( u , v) ~ Le, can be expanded in the form

o o

K ( u , v) = Z ~i~i(u) - ~ßi(V), i = l

(35)

where ~-i c ~t and qSi are eigenvalues and eigenfunctions

f K (u, v)q~i ( u ) d u = ),i ~bi (v).

of the integral operator defined by the kernel K (u, v). A sufficient condition to ensure that (34) defines a dot-product in a feature space is that all the eigenvalues in the expansion (35) are positive. To guarantee that these coefficients are positive, it is necessary and sufficient (Mercer's Theorem) that the condition

f f K ( u , v)g(u)g(v)dudv > 0 is satisfied for all g such that

f g2(u)du < oo.

Functions that satisfy Mercer's theorem can therefore be used as dot-products. Aizerman, Braverman and Rozonoer (1964) consider a convolution of the dot-product in the feature space given by function of the form

K ( u , v ) = exp(- l u ~ v l ) , (36)

which they call Potential Functions. However, the convolution of the dot-product in feature space can be given by any function

satisfying Mercer's condition; in particular, to construct a polynomial classifier o f degree d in n-dimensional input space one can use the following function

K ( u , v) = (u- v + 1) d. (37)

284 CORTES AND VAPNIK

Using different dot-products K (u, v) one can construct different learning machines with arbitrary types of decision surfaces (Boser, Guyon & Vapnik, 1992). The decision surface of these machines has a form

f ( x ) = ~ y i o t i K ( x , Xi), i=1

where xi is the image of a support vector in input space and «i is the weight of a support vector in the feature space.

To find the vectors xi and weights «i one follows the same solution scheme as for the original optimal margin classifier or soft margin classifier. The only difference is that instead of matrix D (determined by (18)) one uses the matrix

D i j : Yi Yj K (xi, x j), i, j = 1 . . . . . 1.

5. General Features of Support-Vector Networks

5.1. Constructing the Decision Rules by Support-Vector Networks is Efficient

To construct a support-vector network decision rule one has to solve a quadratic optimization problem:

W(A) = A r l - ~ A r D A + ,

under the simple constraints:

0 _ < A < 8 1 ,

A T y ----= 0,

where matrix

D i j : YiYj K (xi, x j ), i, j = 1 . . . . . I.

is determined by the elements of the training set, and K (u, v) is the function determining the convolution of the dot-products.

The solution to the optimization problem can be found efficiently by solving intermediate optimization problems determined by the training data, that currently constitute the support vectors. This technique is described in Section 3. The obtained optimal decision function is unique 6.

Each optimization problem can be solved using any standard techniques.

5.2. The Support-Vector Network is a Universal Machine

By changing the function K ( u , v) for the convolution of the dot~product one can implement different networks.

SUPPORT-VECTOR NETWORKS 285

In the next section we will consider support-vector network machines that use polynomial decision surfaces. To specify polynomials of different order d one can use the following functions for convolution o f the dot-product

K ( u , v) ---- ( u . v + 1) d.

Radial Basis Function machines with decision functions of the form

f ( x ) = sign O~ i e x p ä f \ i=1

can be implemented by using convolutions of the type

/ ,o«,~j K (u, v) = exp ~-i "

In this case the support-vector network machine will construct both the centers xi o f the approximating function and the weights «i.

One can also incorporate a priori knowledge of the problem at hand by constructing special convolution functions. Support-vector networks are therefore a rather general class o f learning machines which changes its set o f decision functions simply by changing the form o f the dot-product.

5.3. Support-Vector Networks and Control of Generalization Ability

To control the generalization ability of a learning machine one has to control two different factors: the error-rate on the training data and the capacity of the learning machine as measured by its VC-dimension (Vapnik, 1982). There exists a bound for the probability of errors on the test set o f the following form: with probability 1 - r/the inequality

Pr(test error) < Frequency(training error) + Confidence Interval (38)

is valid. In the bound (38) the confidence interval depends on the VC-dimension of the learning machine, the number of elements in the training set, and the value o f r/.

The two factors in (38) form a trade-off: the smaller the VC-dimension o f the set of functions o f the learning machine, the smaller the confidence interval, but the larger the value o f the error frequency.

A general way for resolving this trade-off was proposed as the principle o f structural risk minimization: for the given data set one has to find a solution that minimizes their sum. A particular case of structural risk minimization principle is the Occam-Razor principle: keep the first term equal to zero and minimize the second one.

It is known that the VC-dimension o f the set o f linear indicator functions

l ( x ) = s i g n ( w . x + b ) , I x [ < C x

with fixed threshold b is equal to the dimensionality o f the input space. However, the VC-dimension o f the subset

l ( x ) = s i g n ( w , x + b), [xm _< C, [wg _< Cw

286 C O R T E S A N D V A P N I K

(the set o f functions with bounded norm o f the weights) can be less than the dimensionality of the input space and will depend on Cw.

From this point of view the optimal margin classifier method executes an Occam-Razor principle. It keeps the first term of (38) equal to zero (by satisfying the inequality (9)) and it minimizes the second term (by minimizing the functional w . w). This minimization prevents an over-fitting problem.

However, even in the case where the training data are separable one may obtain better generalization by minimizing the confidence term in (38) even further at the expense o f errors on the training set. In the soft margin classifier method this can be done by choosing appropriate values o f the parameter C. In the support-vector network algorithm one can control the trade-off between complexity of decision rule and frequency o f error by changing the parameter C, even in the more general case where there exists no solution with zero error on the training set. Therefore the support-vector network can control both factors for generalization ability of the learning machine.

6. Experimental Analysis

To demonstrate the support-vector network method we conduct two types of experiments. We construct artificial sets o f patterns in the plane and experiment with 2nd degree poly- nomial decision surfaces, and we conduct experiments with the real-life problem o f digit recognition.

6.1. Experiments in the Plane

Using dot-products of the form

K ( n , v ) = ( u . v + 1) a (39)

with d = 2 we construct decision rules for different sets of patterns in the plane. Results o f these experiments can be visualized and provide nice illustrations of the power o f the algorithm. Examples are shown in Fig. 5. The 2 classes are represented by black and white

Figure 5. E x a m p l e s o f th e d o t - p r o d u c t (39) w i t h d = 2, S u p por t patterns are i n d i c a t e d w i t h d o a b l e circles, errors w i t h a cross.

SUPPORT-VECTOR NETWORKS 287

7 7 4 8 0 1 - 4

8 7 4 8 7 3 7

Figure 6. Examples of patterns with labels from the US Postal Service digit database.

bullets. In t h e figure w e i n d i c a t e s u p p o r t p a t t e r n s with a d o u b l e circle, and errors w i t h a cross. T h e s o l u t i o n s are o p t i m a l in the sense that no 2nd d e g r e e p o l y n o m i a l s e x i s t that m a k e less errors. N o t i c e that the n u m b e r s o f s u p p o r t p a t t e r n s r e l a t i v e to the n u m b e r o f t r a i n i n g p a t t e r n s are s m a l l .

6.2. Experiments with Digit Recognition

O u r e x p e r i m e n t s for c o n s t r u c t i n g s u p p o r t - v e c t o r n e t w o r k s m a k e use o f two d i f f e r e n t data- b a s e s for b i t - m a p p e d d i g i t r e c o g n i t i o n , a s m a l l and a large d a t a b a s e . T h e s m a l l one is a US P o s t a l S e r v i c e d a t a b a s e that c o n t a i n s 7,300 t r a i n i n g p a t t e r n s and 2,000 test patterns. T h e r e s o l u t i o n o f t h e d a t a b a s e is 16 x 16 p i x e l s , and s o m e t y p i c a l e x a m p l e s are s h o w n in F i g . 6. O n this d a t a b a s e w e r e p o r t e x p e r i m e n t a l r e s e a r c h with p o l y n o m i a l s o f v a r i o u s d e g r e e .

T h e l a r g e d a t a b a s e c o n s i s t s o f 60,000 t r a i n i n g and 10,000 test patterns, and is a 5 0 - 5 0 m i x t u r e o f the N I S T 7 t r a i n i n g and test sets. T h e r e s o l u t i o n o f t h e s e p a t t e r n s is 28 x 28 y i e l d i n g an i n p u t d i m e n s i o n a l i t y o f 784. On this d a t a b a s e w e h a v e o n l y c o n s t r u c t e d a 4th d e g r e e p o l y n o m i a l classifier. T h e p e r f o r m a n c e o f this classifier is c o m p a r e d to o t h e r t y p e s o f l e a r n i n g m a c h i n e s that t o o k p a r t in a b e n c h m a r k s t u d y (Bottou, 1994).

In all our e x p e r i m e n t s ten separators, one for each class, are constructed. E a c h h y p e r - s u r f a c e m a k e s u s e o f the s a m e d o t p r o d u c t and p r e - p r o c e s s i n g o f the data. C l a s s i f i c a t i o n o f an u n k n o w n p a t t e r n s is d o n e a c c o r d i n g to the m a x i m u m o u t p u t o f t h e s e ten classifiers.

6.2.1. Experiments with US Postal Service Database. T h e US P o s t a l S e r v i c e D a t a b a s e has b e e n r e c o r d e d f r o m a c t u a l m a i l p i e c e s and results f r o m this d a t a b a s e have b e e n r e p o r t e d b y s e v e r a l r e s e a r c h e r s . In Table 1 w e list the p e r f o r m a n c e o f various classifiers c o l l e c t e d

Table L Performance of various classifiers collected from publications and own experiments. For references see text.

Classifier Raw error, %

Human performance 2.5 Decision tree, CART 17 Decision tree, C4.5 16 Best 2 layer neural network 6.6 Special architecture 5 layer network 5.1

288 CORTES AND VAPNIK

Table 2. Results obtained for dot products of polynomials of various degree. The number of "support vectors" is a mean value per classifier.

Degree of Raw Support Dimensionality of polynomial error, % vectors feature space

1 12.0 200 256 2 4.7 127 ~33000 3 4.4 148 ~1 x 106 4 4.3 165 ~ I x 109 5 4.3 175 ~1 x 1012 6 4.2 185 ~1 x 1014 7 4.3 190 ~1 x 1016

f r o m publications and own experiments. The result o f h u m a n performance was reported by J. B r o m l e y & E. Sackinger (Bromley & Sackinger, 1991). The result with C A R T was carried out by Daryl Pregibon and Michael D. Riley at Bell Labs., Murray Hill, NJ. T h e results o f C4.5 and the best 2-layer neural network (with optimal n u m b e r o f hidden units) were obtained specially for this paper b y Corinna Cortes and Bernard S c h o e l k o p f respee- tively. T h e result with a special purpose neural network architecture with 5 layers, L e N e t l , was obtained b y Y. L e C u n e t a l . (1990).

O n the experiments with the US Postal Service Database we used pre-processing (cen- tering, de-slanting and smoothing) to incorporate knowledge about the invariances o f the problem at hand. T h e effect o f smoothing o f this database as a pre-processing for support- vector networks was investigated in (Boser, G u y o n & Vapnik, 1992). For our experiments w e chose the s m o o t h i n g kernel as a Gaussian with standard deviation ~r = 0.75 in agreement with (Boser, G u y o n & Vapnik, 1992).

In the experiments with this database we constructed polynomial indicator functions based o n dot-products o f the f o r m (39). The input dimensionality was 256, and the order o f the p o l y n o m i a l r a n g e d f r o m 1 to 7. Table 2 describes the results o f the experiments. T h e training data are not linearly separable.

N o t i c e that the n u m b e r o f support vectors increases very slowly. The 7 degree p o l y n o - mial has only 30% m o r e support vectors than the 3rd degree p o l y n o m i a l - - a n d even less than the first degree polynomial. The dimensionality o f the feature space for a 7 degree p o l y n o m i a l is h o w e v e r 101° times larger than the dimensionality o f the feature space for a 3rd degree p o l y n o m i a l classifier. Note that performance almost does not c h a n g e with increasing dimensionality o f the s p a c e - - i n d i c a t i n g no over-fitting problems.

T h e relatively high n u m b e r o f support vectors for the linear separator is due to non- separability: the n u m b e r 200 includes both support vectors and training vectors with a non- zero ~-value. I f ~ > 1 the training vector is misclassified; the n u m b e r ofmis-classifications on the training set averages to 34 per classifier for the linear case. For a 2nd degree classifier the total n u m b e r o f mis-classifications on the training set is down to 4. These 4 patterns are shown in Fig. 7.

It is remarkable that in all our experiments the bound for generalization ability (5) holds when w e consider the n u m b e r o f obtained support vectors instead o f the expectation value o f this number. In all cases the upper bound on the error probability for the single classifier does not exceed 3% (on the test data the actual error does not exceed 1.5% for the single classifier).

SUPPORT-VECTORNETWORKS 289

~ 1 1 4 1 ~ 1 ~ :.~ 4 4 8 5

Figure 7. Labeled examples of errors on the training set for the 2nd degree polynomial support-vector classifier.

T h e t r a i n i n g t i m e for c o n s t r u c t i o n o f p o l y n o m i a l classifiers d o e s not d e p e n d on the d e - g r e e o f the p o l y n o m i a l - - - o n l y the n u m b e r o f s u p p o r t vectors. E v e n in the w o r s t c a s e it is f a s t e t than the b e s t p e r f o r m i n g neural n e t w o r k , c o n s t r u c t e d s p e c i a l l y for the task, L e N e t l ( L e C u n , et al., 1990). T h e p e r f o r m a n c e o f this neural n e t w o r k is 5.1% r a w error. P o l y n o - m i a l s w i t h d e g r e e 2 or h i g h e r o u t p e r f o r m L e N e t l .

6.2.2. E x p e r i m e n t s w i t h the N I S T Database. T h e N I S T d a t a b a s e w a s u s e d f o r b e n c h m a r k studies c o n d u c t e d o v e r j u s t 2 weeks. T h e l i m i t e d t i m e f r a m e e n a b l e d o n l y the c o n s t r u c t i o n o f 1 t y p e o f classifier, for w h i c h w e c h o s e a 4th d e g r e e p o l y n o m i a l w i t h no p r e - p r o c e s s i n g . O u r c h o i c e was b a s e d on our e x p e r i e n c e w i t h the U S P o s t a l d a t a b a s e .

T a b l e 3 lists the n u m b e r o f s u p p o r t v e c t o r s for e a c h o f the 10 classifiers and gives the p e r f o r m a n c e o f the c l a s s i f i e r on the t r a i n i n g and test sets. N o t i c e that even p o l y n o m i a l s o f d e g r e e 4 (that h a v e m o r e t h a n 108 free p a r a m e t e r s ) c o m m i t errors on this t r a i n i n g set.

T h e a v e r a g e f r e q u e n c y o f t r a i n i n g errors is 0 . 0 2 % ~ 12 p e r class. T h e 14 m i s c l a s s i f i e d test p a t t e r n s for c l a s s i f i e r 1 are s h o w n in Fig. 8. N o t i c e a g a i n h o w the u p p e r b o u n d (5) h o l d s for the o b t a i n e d n u m b e r o f s u p p o r t vectors.

T h e c o m b i n e d p e r f o r m a n c e o f the ten classifiers on the test set is 1.1% error. T h i s r e s u l t s h o u l d b e c o m p a r e d to t h a t o f o t h e r p a r t i c i p a t i n g classifiers in the b e n c h m a r k study. T h e s e o t h e r classifiers i n c l u d e a l i n e a r classifier, a k = 3 - n e a r e s t n e i g h b o r classifier w i t h 60,000 p r o t o t y p e s , and two n e u r a l n e t w o r k s s p e c i a l l y c o n s t r u c t e d for d i g i t r e c o g n i t i o n ( L e N e t l and L e N e t 4 ) . T h e authors o n l y c o n t r i b u t e d with results for s u p p o r t - v e c t o r n e t w o r k s . T h e results o f the b e n c h m a r k are g i v e n in F i g . 9.

W e c o n c l u d e this s e c t i o n b y c i t i n g the p a p e r (Bottou, et al., 1994) d e s c r i b i n g results of the b e n c h m a r k :

F o r q u i t e a l o n g t i m e L e N e t l was c o n s i d e r e d state o f the a r t . . . T h r o u g h a series o f e x p e r i m e n t s in architecture, c o m b i n e d w i t h an a n a l y s i s o f the c h a r a c t e r i s t i c s o f r e c o g n i t i o n error, L e N e t 4 was crafted . . . . T h e s u p p o r t - v e c t o r n e t w o r k has e x c e l l e n t accuracy, w h i c h is m o s t r e m a r k a b l e , be- c a u s e u n l i k e the o t h e r h i g h p e r f o r m a n c e classifiers, it d o e s n o t i n c l u d e k n o w l e d g e

Table 3. Results obtained for a 4th degree polynomial classifier on the NIST database. The size of the training set is 60,000, and the size of the test set is 10,000 patterns.

C1. 0 C1. 1 CI. 2 C1. 3 C1. 4 CI. 5 CI. 6 CI. 7 C1. 8 C1, 9

Supp. patt, 1379 989 1958 1900 1224 2024 1527 2 0 6 4 2 3 3 2 2765 Error train 7 16 8 11 2 4 8 16 4 1 Error test 19 14 35 35 36 49 32 43 48 63

290 CORTES AND VAPNIK

I ~1«1~1 ~ II ~ l t l ~ 1 6 1 9 6 6 1

1~ I ~ [ n l J ~~ 1[ 1, l z~ I~1 9 1 1 1 1 1 1

Figure 8. The 14 misclassified test pattems with iabels for classifier 1. Patterns with label "1" are false negative. Patterns with other labels are false positive.

Test erroi

2~

Figure 9.

l i n e a r classifier

k = 3 - n e a r e s t neighbor

Results from the benchmark study.

L e N e t l LeNet4 S V N

about the geometry o f the problem. In fact the classifier would do as weil if the image pixels were encrypted e.g. by a fixed, random permutation.

The last remark suggests that further improvement of the performance o f the support- vector network can be expected from the construction of functions for the dot-product K ( u , v) that reflect a priori information about the problem at hand.

7. Conclusion

This paper introduces the support-vector network as a new learning machine for two-group classification problems.

The support-vector network combines 3 ideas: the solution technique from optimal hy- perplanes (that allows for an expansion of the solution vector on support vectors), the idea of convolufion o f the dot-product (that extends the solution surfaces from linear to non-linear), and the notion o f soft margins (to allow for errors on the training set).

S U P P O R T - V E C T O R N E T W O R K S 291

The algorithm has been tested and compared to the performance o f other classical al- gorithms. Despite the simplicity o f the design in its decision surface the new algorithm exhibits a very fine performance in the comparison study.

Other characteristics like capacity control and ease o f changing the implemented decision surface render the support-vector network an extremely powerful and universal learning machine.

A. Constructing Separating Hyperplanes

In this appendix we derive both the method for constructing optimal hyperplanes and soft margin hyperplanes.

A.1. O p t i m a l H y p e r p l a n e A l g o r i t h m

It was shown in Section 2, that to construct the optimal hyperplane

W o . x + b o = 0 , (40)

which separates a set o f training data

( Y l , X l ) . . . . . ( Y e , X e ) ,

one has to minimize a functional

q b = W ' W ,

subject to the constraints

Yi (Xi • W -1- b) > 1, i = 1 . . . . . £. (41)

To do this we use a standard optimization technique. We construct a Lagrangian

1 L(w, b, A ) = ~ w . w - Z o l i [ Y i ( X i • w + b ) - 1], (42)

i = l

where A T = («1 . . . . . ole) is the vector o f non-negative Lagrange multipliers corresponding to the constraints (41).

It is known that the solution to the optimization problem is determined by the saddle point o f this Lagrangian in the 2e + 1-dimensional space o f w, A, and b, where the minimum should be taken with respect to the parameters w and b, and the m a x i m u m should be taken with respect to the Lagrange multipliers A.

At the point o f the minimum (with respect to w and b) one obtains:

w w o ( ~ ) O L ( w , b, A ) - ~ _ , « i y i x i 0, (43)

0 W = W 0 = i = l

O L ( w , b, A) b=bo ~--d = yioti = O. (44) Ob «,

292 CORTES A N D V A P N I K

F r o m e q u a l i t y (43) w e d e r i v e

Wo = ~ oliYiXi, (45) i=1

w h i c h e x p r e s s e s , that the o p t i m a l h y p e r p l a n e s o l u t i o n can b e written as a l i n e a r c o m b i n a - tion o f t r a i n i n g vectors. N o t e , that o n l y t r a i n i n g vectors xi with ~i > 0 h a v e an e f f e c t i v e c o n t r i b u t i o n to the s u m (45).

S u b s t i t u t i n g (45) and (44) into (42) w e o b t a i n

1 W ( A ) : ~ o~ i - - ~ w 0 • Wo (46)

i=1

1 e e = Z o t i - "~ Z 2 oti«jyiyjxi . x j . (47)

i=1 i=l j = l

In v e c t o r n o t a t i o n this can b e r e w r i t t e n as

W ( A ) = A r l - 1 A T D A , (48) 2

w h e r e 1 is an l - d i m e n s i o n a l unit vector, and D is a s y m m e t r i c £ x & m a t r i x with e l e m e n t s

Dij : yiyjxi • xj.

To find the d e s i r e d s a d d l e p o i n t it r e m a i n s to l o c a t e the m a x i m u m o f (48) u n d e r the constraints (43)

A T Y = 0,

w h e r e y T = (Yl . . . . . Ye), and

A > 0 .

T h e K u h n - T u c k e r t h e o r e m p l a y s an i m p o r t a n t part in the t h e o r y o f o p t i m i z a t i o n . A c - c o r d i n g to this t h e o r e m , at o u r s a d d l e p o i n t in wo, bo, Ao, any L a g r a n g e m u l t i p l i e r « o and its c o r r e s p o n d i n g c o n s t r a i n t are c o n n e c t e d b y an e q u a l i t y

oli[Yi(Xi • Wo + bo) - l ] = 0, i = 1 . . . . . ~.

F r o m this e q u a l i t y c o m e s that n o n - z e r o values « i are o n l y a c h i e v e d in the c a s e s w h e r e

Yi ( x i • W 0 -~- b 0 ) - 1 = 0 .

In o t h e r w o r d s : « i ¢ 0 o n l y for c a s e s w e r e the inequality is m e t as an equality. W e c a l l v e c t o r s xi for w h i c h

Yi (Xi - WO -k- bo) = 1

for s u p p o r t - v e c t o r s . N o t e , that in this t e r m i n o l o g y the Eq. (45) states that the s o l u t i o n v e c t o r Wo can b e e x p a n d e d on s u p p o r t vectors.

S U P P O R % V E C T O R N E T W O R K S 293

A n o t h e r observation, based on the Kuhn-Tucker Eqs. (44) and (45) for the optimal solution, is the relationship between the m a x i m a l value W ( A 0 ) and the separation distance

P o :

w o . w o = E ° t ° y i x i ' w ° = E °e°(1 - y i b o ) = E °t°" i= 1 i= 1 i = 1

Substituting this equality into the expression (46) for W ( A o ) we obtain

* 1 w o • w o W(Ao) = ~ o , ° - ~wo. w o - ~ -

i = 1

Taking into a c c o u n t the expression (13) f r o m Section 2 w e obtain

2 W(Ao) »° 2,

where Po is the margin for the optimal hyperplane.

A.2. Soff Margin Hyperplane Algorithm

Below w e first consider the case o f F ( u ) = u k. Then we describe the general result for a m o n o t o n i c convex function F ( u ) .

To construct a soft margin separating hyperplane w e m a x i m i z e the functional

1 (~)~ = - w . w + C ~i ,

2 k > l ,

under the constraints

yi(xi - W -t- b) > 1 -- ~i, i = 1 . . . . . •, (49)

~i > 0, i = 1 . . . . . e. (50)

The L a g r a n g e functional for this p r o b l e m is

L ( w , ~, b, A , R)

1 g g = - - W " W + C ~ i - o l i [ Y i ( X i • W + b ) - 1 + ~ i ] - r i ~ i , ( 5 1 )

2 _ i = 1

where the non-negative multipliers A r = (oq, oe2 . . . . . Œl) arise f r o m the constraint (49), and the multipliers R r = (rl, re . . . . . rt) enforce the constraint (50).

W e have to find the saddle point o f this functional (the m i n i m u m with respect to the variables wi, b, and ~i, and the m a x i m u m witll respect to the variables oei and ri).

Let us use the conditions for the m i n i m u m o f this functional at the extremum point:

OL e = WO - - E o t i Y i X i ~ - O,

w=wo i = I (52)

294 C O R T E S A N D V A P N I K

O L e : y ~ o t i y i ~ - O ,

" ~ b = b o i = I

~/~0~ ( ~ 1 ~-1 O L = k C ~ o _ ol i _ r i "

(53)

(54)

I f w e d e n o t e

, (±)~ Z~«°= i = l ~k C k , ] '

(55)

w e can rewrite Eq. (54) as

~ - - Oli - - r i = 0 . (56)

F r o m the equalities (52)-(55) w e find

W O = Z o l i Y i X i ,

i=1

_ o t i Y i = O ,

i=1

8 = ot i "-I- r i .

(57)

(58)

Substituting the expressions for Wo, bo, and 8 into the L a g r a n g e functional (51) w e obtain

W ( A ' 8 ) = Y ~ ~ ° t i - - 2 i~.a j~l .= .= (kC)l/k_ 1 1-- . (59)

To find the soft margin h y p e r p l a n e solution one has to m a x i m i z e the f o r m functional (59) under the constraints (57)-(58) with respect to the non-negative variables « i , ri with i = 1 . . . . . I. I n vector notation (59) can be rewritten as

W ( A , ô) = A r l - A ~ D A + ( k C ) l / ~ _ l 1 - , (60)

where A and D are as defined above. To find the desired saddle point one therefore has to find the m a x i m u m o f (60) under the constraints

and

A T y = 0, (61)

A + R = 81, (62)

A > 0, (63)

R > 0. ( 6 4 )

F r o m (62) and (64) one obtains that the vector A should satisfy the conditions

0 < A < 81. ( 6 5 )

S U P P O R T - V E C T O R N E T W O R K S 295

From conditions (62) and (64) one can also conclude that to maximize (60)

3 = 0tma x = m a x 0 x l . . . . . o~e).

Substituting this value o f ~ into (60) we obtain

W(A) = A T I _ [ 1 A T D A + °tkm/kaZ . ( l - k ) ] ( k C ) l / k - 1

(66)

To find the soft margin hyperplane one can therefore either find the m a x i m u m o f the quadratic form (51) under the constraints (61) and (65), or one has to find the m a x i m u m of the convex function (60) under the constraints (61) and (56). For the experiments reported in this paper we used k = 2 and solved the quadratic programming problem (51).

For the case o f F(u) = u the same technique brings us to the problem o f solving the following quadratic optimization problem: minimize the functional

1 r W ( A ) = AT1 -- - A D A ,

2

under the constraints

and

O < A < C 1 ,

A T y = 0.

The general solution for the case of a monotone convex function F(u) can also be obtained from this technique. The soft margin hyperplane has a form

e

w --~ ~ _ ~ i Y i X i , i = 1

where Ao r = (n ° . . . . . oe °) is the solution o f the following dual convex programming prob- lem: maximize the functional

W ( A ) = A r l - [ 1 A r D A + ( o t m a ~ f - I ( - ~ ) ) - C F ( f - 1 ( ~ - ~ ) ) I ,

A T y = 0,

A > _ 0 ,

where we denote f ( u ) = F'(u).

For convex monotone functions F(u) with F(O) = 0 the following inequality is valid:

uF'(u) > F(u).

Therefore the second term in square brackets is positive and goes to infinity when Otmax goes to infinity.

under the constraints

296 CORTES AND VAPNIK

Finally, we can consider the hyperplane that minimizes the form

- - W • W - I - ~ i 2

subject to the constraints (49)-(50), where the second term minimizes the least square value for the errors. This lead to the following quadratic programming problem: maximize the functional

1 [ A r D A + I A r A ] (67) W(A) = A ~ I - ä

in the non-negative quadrant A _> 0 subject to the constraint A T y = 0.

Notes

I. The optimal coefflcient for ~ was found in the sixties (Anderson & Bahadur, 1966).

2. Recall Fisher's concerns about small amounts o f data and the quadratic discriminant function.

3. With this name we emphasize how crucial the idea of expanding the solution on support vectors is for these learning machines. In the support-vectors learning algorithm the complexity o f the construction does not depend on the dimensionality o f the feature space, but on the number o f support vectors.

4. Note that in the inequalities (9) and (10) the right-hand side, but not vector w, is normalized.

5. A training error is here defined as a pattern where the inequality (22) holds with ~ > 0.

6. The decision function is unique but not its expansion on support vectors.

7. National Institute for Standards and Technology, Special Database 3.

References

Aizerman, M., Braverman, E., & Rozonoer, L. (1964). Theoretical foundations o f the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837.

Anderson, T.W., & Bahadur, R.R. (1966). Classification into two multivariate normal distributions with different covariance matrices. Ann. Math. Stat., 33:420--431.

Boser, B.E., Guyon, I., & Vapnik, V.N. (1992). A training algorithm for optimal margin classifiers. In Proceedings o f the F(fth Annual Worlaghop o f Computational Learning Theory, 5, 144-152, Pittsburgh, ACM.

Bottou, L., Cortes, C., Denker, J.S., Drucker, H., Guyon, I., Jackel, L.D., LeCun, Y., Sackinger, E., Simard, P., Vapnik, V., & Miller, U.A. (1994). Comparison o f classifier methods: A case study in handwritten digit recognition. Proceedings o f 12th International Conference on Pattern Recognition and Neural Network.

Bromley, J., & Sackinger, E. (1991). Neural-network and k-nearest-neighbor classifiers. Technical Report 11359- 910819-16TM, AT&T.

Courant, R., & Hilbert, D. (1953). Methods ofMathematical Physics, Interscience, New York. Fisher, R.A. (1936). The use o f multiple measurements in taxonomic problems. Ann. Eugenics, 7:111-132. LeCun, Y. (1985). Une procedure d'apprentissage pour reseau a seuil assymetrique. Cognitiva 85: A la Frontiere

de l'Intelligence Artificielle des Sciences de la Connaissance des Neurosciences, 599-604, Paris. LeCun, Y., Boser, B., Denker, J.S., Henderson, D., Howard, R.E., Hubbard, W., & Jackel, L.D. (1990). Handwritten

digit recognition with a back-propagation network. Advances in Neural Information Processing Systems, 2, 396- 404, Morgan Kaufman.

Parker, D.B. (1985). Learning logic. Technical Report TR-47, Center for Computational Research in Economics and Management Science, Massachusetts Institute o f Technology, Cambridge, MA.

Rosenblatt, F. (1962). Principles ofNeurodynamics, Spartan Books, New York.

SUPPORT-VECTORNETWORKS 297

Rumelhart, D.E., Hinton, G.E., & Williams, R.J. (1986). Learning intemal representations by backpropagating errors. Nature, 323:533-536.

Rumelhart, D.E., Hinton, G.E., & Williams, R.J. (1987). Learning intemal representations by error propagation. In James L. McClelland & David E. Rumelhart (Eds.), Parallel Distributed Processing, 1, 318-362, MIT Press.

Vapnik, V.N. (1982). Estimation ofDependences Based on Empirical Data, Addendum 1, New York: Springer- Verlag.

Received May 15, 1993 Accepted February 20, 1995 Final Manuscript March 8, 1995