Multi-prototype Support Vector Machine

1 Introduction

Automatic multiclass classification, i.e. the process to auto­ matically assign exactly one from a prefixed set of labels to a stream of input instances, is a central task for many real world problems like speech recognition, OCR, text categorization etc. Many supervised learning methods have been studied that help on these tasks. Recently, kernel-based methods, like SVM, have been well studied especially for binary settings, and they yielded state-of-art performance in many different tasks. SVM searches for a high margin linear discriminant model in a very high dimensional space (feature space) where examples are implicitly mapped via a function ~(x) . Since kernel-based algorithms need only of dot products in feature space, it is possible to resort to the so called kernel trick if these dot products can be computed efficiently with a kernel function K ( x, y) = ~ ( x) · ~ (y). When the number of exam­ ples (or support vectors) is large, these approaches tend to be less efficient w.r.t. the time spent for classifying new vectors since they require to work with the implicit characterization of the discriminant model.

One of the most effective SVM extension able to deal with general multiclass problems has been recently provided [Crammer and Singer, 2000] and it has shown very good re­ sults. In this paper, we extend the multiclass SVM to the multi-prototype setting where for each class there can be more than one prototype vector. This allowed us to get very expressive decision functions by using simple models without necessarily requiring the use of kernels.

Alessandro Sperduti

Dept. of Pure and Applied Mathematics University ofPadova, Italy sperduti@math. unipd. it

1.1 Preliminaries and notation

LetS = { (x1, cl), .. , (xn, en)} be a set of n training exam­ ples, Xi EX~ JRd and Ci E C = {1, .. ,m}. A single-label multi-class classifier is a function h : X -+ C that maps in­ stances x E X to labels c E C. We focus on the class of winner-take-all linear classifiers with form:

where Mr is the r-th prototype vector, R is the set of proto­ type indexes and C (r) the function returning the class associ­ ated to the prototype indexed r. Given a classifier hM(x) and a training example (xi, Ci) we will say that hM(x) misclassi­ fies Xi if hM(Xi ) =j; Ci.

In the following, we denote by y[ the constant that is equal to 1 ifC(r) = Ci and -1 otherwise. For a given example Xi, we denote by Pi = { r E R : y[ = 1} the set of "positive" prototypes indexes and by Ni = {r E R : y[ = -1} the set of "negative" prototypes indexes. Finally, the real value sr(x) = Mr ·xis referred to as similarity score (or simply score) of the r-th prototype on the instance x.

2 Single-prototype multi-class SVM

An effective multi-class extension to SVM has been already proposed in [Crammer and Singer, 2000]. The resulting classifier is of the same form of (1) where each class has associated exactly one prototype, i.e. R = C and C(r) = r. The solution is obtained through the minimization of a convex quadratic constrained problem. In this section, we present a simpler derivation of an equivalent formulation that will be extended in the next section to the multi-prototype framework.

In the multiclass setting, in order to have a correct classi­ fication of the instance Xi, the prototype of the correct class should have a score that is greater than the maximum among the scores of the prototypes associated to incorrect classes. We can formally write the constraints for a correct classifica­ tion of the example Xi with a margin greater or equal to 1 by requmng:

where Yi = Ci is the index of the prototype vector associated to the correct class for the example Xi· To allow for margin violations, for each example, we introduce soft margin slack variables ~i ~ 0, s.t.

where [x]+ denotes the hinge loss equal to x if x > 0 and 0 otherwise. Notice that the value ~i is an upper bound to the 0 - 1 loss for the example x;, and consequently its aver­ age value over the training set will be an upper bound for the empirical error.

Motivated by the structural risk minimization (SRM) prin­ ciple in [Vapnik, 1998], we want to search for a set of pro­ totype vectors M = {M1 , .. ,M1c1} with small norm such to minimize the empirical error on the training set. For this, we can formulate the problem in a SVM-style by requiring a set of prototypes of minimal norm that fulfill the soft con­ straints given by the classification requirements. Thus, the single-prototype multiclass SVM (SProtSVM) will result in:

Notice that, as desired, the optimal solution for 8; will be the maximum value among the negative scores for the instance x;. This problem is convex and it can be solved in the stan­ dard way by resorting to the optimization of the Wolfe dual problem. In this case, the lagrangian is:

subject to the constraints ai, >.; ~ 0. By differentiating the lagrangian with respect to the primal variables and impos­ ing the optimality conditions we obtain the set of constraints (KKT conditions) that the variables must fulfill in order to be an optimal solution:

By using the fact af' = ~ l:r ai and substituting condi­ tions (4) in (3) and omitting constants that do not change the solution, the problem can be restated as:

The next section includes an efficient optimization pro­ cedure for the more general multi-prototype setting that in­ cludes the single-prototype case as a particular instance.

3 Multi-prototype multi-class SVM

In this section, the SProtSVM model previously defined will be extended to the case of multiple prototypes per class. The basic idea is that, given multiple prototype vectors, we have a correct classification iff at least one of the prototypes associ­ ated to the correct class has a score higher than the maximum of the scores of the prototypes associated to incorrect classes.

In this case, we write the constraints for a correct classifi­ cation of the example x; with a margin greater or equal to 1 requiring:

To allow for margin violations, for each example X;, we introduce soft margin slack variables ~i ~ 0, one for each positive prototype, s.t.

Given a pattern x;, we arrange the soft margin slack variables ~i in a vector ~i E ]RIP· 1. Let us now introduce, for each example x;, a new vector 7r; E {0, 1 }IP· I, whose components are all zero except one component that is 1. In the following, we refer to 7r; as the assignment of the pattern x;. Notice that the dot product 1r i · ~i is always an upper bound to the 0 - 1 loss for the example x; independently from its assignment.

Now, we are ready to formulate the multi-prototype prob­ lem by requiring a set of prototypes of small norm and the best assignment for the examples able to fulfill the soft con­ straints given by the classification requirements.

Thus, the MProtSVM formulation will result in:

Unfortunately, this is a mixed integer problem that is not convex and it is a difficult problem in general but, as we will see in the following, it is prone to an efficient optimization procedure that approximates the global optimum. At this point, it is worth noticing that, since the effective formulation is itself an (heuristic) approximation to the structural risk minimization principle, a good solution, although not opti­ mal, can anyway give good results. As we see after, this claim is confirmed by the results obtained in our experimental work.

Let suppose now that the assignments are kept fixed. In this case the reduced problem becomes convex and can be solved as above by resorting to the optimization of the Wolfe dual problem. In this case, the lagrangian is:

subject to the constraints ai, >.i ~ 0. As above, by differen­ tiating the lagrangian of the reduced problem and imposing the optimality conditions, we obtain:

Notice that the second condition requires the dual variables associated to positive prototypes and not assigned to the as­ sociated pattern to be 0. By denoting now as y; the unique index r E P; such that rr[ = 1, once using the conditions (8) in (7) and omitting constants that do not change the obtained solution, the reduced problem can be restated as:

It can be trivially shown that this formulation is consistent with the formulation for SProtSVM's given above.

3.1 Optimization with static assignments

When patterns are statically assigned to the prototypes via constant vectors 1r i, the convexity of the associated MProtSVMproblem implies that the optimal solution for the primal problem in (6) can be found through the maximization of the lagrangian in (9) .

Assuming an equal number q of prototypes per class, the dual involves n x m x q variables which lead to a very large scale problem. Anyway, the independence of constraints among the different patterns allows for the separation of the variables in n disjoint sets of m x q variables.

The algorithm we propose for the optimization of the prob­ lem in (9) is inspired by the ones already presented in [Cram­ mer and Singer, 2000; Aiolli and Sperduti, 2002a] and con­ sists in iteratively selecting patterns from the training set and optimizing with respect to the variables associated to that pat­ tern. From the convexity, each iteration leads to an increase of the lagrangian until no more improvement is possible since the optimal solution for the lagrangian has been found.

After selecting a pattern x;, to enforce the constraint LrEN, a[ + ..\i = /, ..\i 2: 0, two elements from the set of variables {a[, r E Ni} U { ..\;} will be optimized in pair while keeping the solution inside the feasible region. In par­ ticular, let w1 and w2 be the two selected variables, we restrict the updates to the form w1 +- w1 + p and w2 +- w2 - p with optimal choices for p. Iterating the application of this basic step over different pairs and then doing the same for different patterns will guarantee to reach the optimum for the overall problem.

Let now compute the optimal value for p. First of all, we observe that the update will affect the squared norm of the prototype vector Mr of an amount

Now, we show how to analytically solve the associated problem with respect to an update involving a single variable a;, r E Ni and the variable ..\p. Since ..\p does not influence the value of the objective function, it is possible to solve the associated problem with respect to the variable a; and a~P to keep the constraint a~p = LrEN p a; satisfied and then to enforce the constraints ..\p = 1 - LsEN, a~ 2: 0. Thus, in this case we have:

Since l'::,.Mr = -pxp, l'::,.My, = pxp and l'::,.Ms = 0 for s ~ {r,y;}, we obtain t::,.IIMII 2 = t::,.IIMrll 2 + t::,.IIMy, 11 2 = 2p 2 llxPW + 2p(syp(xp) - sr(xp)) and l'::,.L(a) = 2p(1Syp(xp) + sr(Xp)- PllxpW) . Since this last formula is con­ cave on p, it is possible to find the optimal value when the first derivative is null, i.e.

If the values of a; and a~P , after being updated, would turn out to be not feasible for the constraints a; 2: 0 and a~P ~ / , we select the value for p such to fulfill the violated constraint bounds at the limit.

Now, we show how to analytically solve the associated problem with respect to an update involving a pair of vari­ ables a; 1 , a; 2 such that r1 , r2 E N; and r1 =/:- r 2. Since, in this case, the update must have zero sum, we have:

In this case, 6.Mr 1 = -pxp, 6.Mr 2 = pxp and D.Ms = 0 for s ~ {r1,r2}, we obtain t::,.IIMII 2 = t::,.IIMr1 ll 2 + t::,.IIMr2ll = 2p 2 llxpll 2 + 2p(Sr2 (Xp) - Sr1 (Xp)) and l'::,.L(a) = 2p(Sr 1 (xp)- Sr 2 (xp)- PllxpW). Since also this last formula is concave on p, it is possible to find the optimal value

Similarly to the previous case, if the values of the aj/ and a; 2 , after being updated, would turn out to be not feasible for the constraints ar 1 2: 0 and a; 2 2: 0 we select the value for p such to fulfill the violated constraint bounds at the limit.

Iterating multiple times the basic step described above on pairs of variables chosen among that associated to a given pattern it is guaranteed to find the optimality condition for the pattern. This has been exploited in [Aiolli and Sper­ duti, 2002a] to devise an incremental algorithm that uses the method on the reduced problem of a single example and then iterates over different examples. This optimization proce­ dure can be considered incremental in the sense that the so­ lution previously found for a given pattern forms the initial condition when the pattern is selected again for optimiza­ tion. In this version, the basic step of optimization of the reduced problem can require the optimization over all the ((m - 1) x q + 1)((m - 1) x q)/2 pairs of variables not constrained to 0 associated with the selected pattern. Thus the complexity of the optimization of the reduced problem is o(I x (m x q) 2 ) where I is the number of iterations.

Now, we perform a further step by giving an algorithm that at each iteration has a complexity o(m x q). For this, we ob­ serve that for the variables {a; , ..\p} associated to the pattern Xp to be optimal, the feasible analytic solution p must be 0 for each pair.

In particular, for the first case above, in order to be able to apply the step, it is required that, one of the following two conditions are verified, i.e.:

while for the second case we must have:

Notice that these facts can be checked in linear time. It is easy to show that the solution obtained at a certain step can be improved iff one of these facts are verified. This suggests an efficient procedure, shown in Figure 1 (Top), that tries to greedily fulfill the previous condition of optimality.

3.2 Optimization of general MProtSVM

In this section, we present an efficient procedure that guaran­ tees to reach a local minimum of the objective function of the problem in (6) associated to MProtSVM. This procedure will try to optimize also with respect to the assignments 7r i.

Let suppose to start with a given assignment 7r(1) for the patterns. In this case, as we have already seen, the associated problem is convex and can be efficiently solved by using the algorithm given in Section 3.1. Once that the optimal value for the primal P,;_(l) has been reached, we observe that the so­ lution can be further improved by updating the assignments in such a way to assign each pattern x; to a positive prototype with minimal slack value, i.e. by setting the vector 7r;(2) such to have the unique 1 corresponding to the best perform­ ing positive prototype. However, with this new assignment 7r(2), the variables a might not fulfill the second KKT con­ dition in eq. (8) anymore. If it is the case, it simply means that the current solution a is not optimal for the new assign­ ment. Thus, a lagrangian optimization done by satisfying constraints dictated by KKT conditions for the new assign­ ment is guaranteed to obtain a new a with a better optimal primal value P,;_(2). For the optimization algorithm to suc­ ceed, however, the KKT conditions on the a must be restored in order to return back to a feasible solution and then finally resuming the lagrangian optimization with the new assign­ ment 7r(2). We restore the KKT conditions by setting a; = 0 whenever there exists r E P; such that aj > 0 1\ rri = 0.

Performing the same procedure over different assignments, each one obtained from the previous one by the procedure just mentioned, implies the convergence of the algorithm to a local solution for the primal problem when no improvements are possible and the KKT conditions are all fulfilled by the current solution. This is due to the fact that every step induces an improvement on the primal value.

The first problem with this procedure is that it results oner­ ous when dealing with many prototypes since we must per­ form many lagrangian optimizations. For this, we observe that for the procedure to work, at each step, it is sufficient to stop the optimization of the lagrangian when we find a value

AnnealedMProtSVM() T :=To; randomly initialize 1r(l); compute the primal E(1) := P7r(l) (0); fort= 1, .. , tmax do for all the examples Xp E S ap = OptimizeOnPattern(xp , ~:); ·until P1r(t)(a) < E(t); compute a new assignment 1r(t + 1) using T(t, T0 ); compute the new primal E(t + 1) := P7r(t+l) (a) ; restore KKT conditions on a; /*see Section 3.2*/ end;

for the primal better than the last found and this is going to happen for sure since the last solution has been found not op­ timal. This requires only a periodic check of the primal value when optimizing the lagrangian.

The second and more stringent problem is that the proce­ dure will lead to a local minimum that can be very far from the best possible. For this, we suggest to update the assign­ ments on the basis of a stochastic annealed function instead of the hard decision function described above.

Specifically, let us view the value of the primal as an energy function

Let suppose to have a pattern X; having slack variables er ' r E P; and suppose that the probability for the assignment to be in the state s (i.e. with the s-th component set to 1) follows the law

where Tis the temperature of the system and 6.E8 = 'Y(et­ et) the variation of the system energy when the pattern X; is assigned to the s-th prototype. By multiplying every term p;(r) bythenormalizationtermexp('Y(ef' -e?)) wheree? = minrEP; er and considering that probabilities over alternative states must sum to one, i.e. I:rEP; p;(r) = 1, we obtain

with Z = I: rEP; exp( -'Y( er -e?) jT) the partition function. Thus, when assigning the pattern x; , each positive proto­ type s will be selected with probability p; ( s) . Notice that, when the temperature of the system is low, the probability for a pattern to be assigned to a prototype different from the one having minimal slack value tends to 0 and we obtain a behavior similar to the not annealed version of the algorithm. The simulated annealing is typically implemented by decreas­ ing the temperature as the number of iterations increases by a monotonic decreasing function T = T(t, T0 ) . The full algo­ rithm is depicted in Figure 1 (Bottom).

4 Experimental Results

We tested our model against three datasets that we briefly de­ scribe in the following:

• NIST: it consists of a 1 0-class task of 10705 digits randomly taken from the NIST-3 dataset. The training set con­ sists of 5000 randomly chosen digits, while the remain­ ing 5705 digits are used in the test set.
• USPS: it consists of a 1 0-class OCR task (digits from 0 to 9) whose input are the pixels of a scaled digit image. There are 7291 training examples and 2007 test examples.
• LETTER: it consists of a 26-class task (alphabetic letters A-Z). Inputs are measures of the printed font glyph. The first 16000 examples are used for training and the last 4000 for testing.

Even if any kernel function can be in principle used, for the following preliminary experiments, we used the linear kernel K ( x, y) = ( x · y + 1) . This allowed us to write an optimized code for training and classification that works directly with the explicit (compact) version of the model M .

Since we are primarily interested into the evaluation of MProtSVM w.r.t. SProtSVM, for each dataset, we performed validation on the parameter 'Y for the SProtSVM model and we re-used the obtained value for training every MProtSVM generated for the same dataset. This approach seems us any­ way a pessimistic estimate of the performance ofMProtSVM.

The annealing process required by MProtSVM has been implemented by decreasing the temperature of the system with the exponential law:

where 0 < r < 1 and T0 > 0 are external parameters. We used T0 = 10 for all the following experiments.

Table 2: (a) Test error of MProtSVM on the USPS dataset ('Y = 0.01, T = .05, [J = 0.137 x q), with an increasing number of prototypes; (b) Test error of MProtSVM on the LETTER dataset ('Y = 10, r = 0.1, fJ = 0.043 x q), with an increasing number of prototypes.

A set of experiments have been performed to compare the generalization performance of our (linear) model versus LVQ [Kohonen eta/. , 1996] which seemed to us the most compa­ rable model. For this, we have reported the best results that have been obtained by LVQ on the NIST dataset. Specifi­ cally, they have been obtained with the LVQ2.1 version of the algorithm (see [Sona and Sperduti, 2000]). As it is possi­ ble to see in Table 1, MProtSVM performs significantly better when few prototypes per class are used, while the difference gets lower when the number of prototypes per class increases. This can be due to the more effective control of the margin for SVM w.r.t. LVQ models. On the same dataset, the tangent­ distance based TVQ algorithm [Aiolli and Sperduti, 2002b] has obtained the best result, a remarkable 2.1% test error, and polynomial SVM's have obtained a 2.82% test error. In addition, we tested the MProtSVM on the UCI Irvine USPS and LETTER datasets. As it is possible to see in Table 2, by combining a reasonably high number oflinear prototypes, we have obtained performances almost comparable with the ones obtained in literature by using non-linear models. In fact, on the USPS dataset, we have been able to get a 4.63% error, using a SProtSVM with polynomial kernel of degree 3 and without preprocessing the data, while for LETTER, we re­ fer to the 1.95% obtained in [Crammer and Singer, 2001] by SProtSVM with exponential kernel. Although obtained with a slightly different split of the LETTER dataset ( 15000 exam­ ples for training and 5000 for test), we would like to mention the results reported in [Michie eta/., 1994] where LVQ and k-NN yielded a 7.9% and 6.8% error, respectively.

Notice that MProtSVM returns far more compact models with respect to state of the art non-linear kernel methods, thus allowing a (one or two order) reduced response time in classification. Defining a sort of model complexity fac­ tor (3 = 100 x (m x q)fn, i.e. the number of prototypes produced as a fraction of the cardinality of the training set, the above experiments have shown very low value for (3 (e.g. 15 x 26 prototypes in the LETTER dataset gives (3 = 0.65% and 20 x 10 prototypes for USPS gives (3 = 2.74%). Notice that (3 can be directly compared with the fraction of support vectors in kernel machines. Thus, MProtSVMs also give us a way to decide (before training) the complexity of the model.

Finally, in Table 3 we have reported the values of the ob­ jective function of the primal problem in (6) along with their corresponding test errors obtained with the USPS dataset us­ ing different configurations and lowering the parameter T. As expected, fixed a raw in the table, better values for the pri­ mal can be obtained with lower values ofT. Moreover, as the number of prototypes per class increases, the choice of small T tends to be more crucial. Anyway, higher values for T, and thus not optimal values for the primal, can neverthless lead to good generalization performances. This can be due to the fact that the primal value is just a way to approximate the theorethical SRM principle.

5 Conclusion

We have proposed an extension of multiclass SVM able to deal with several prototypes per class. This extension defines a non-convex problem. We suggested to solve this problem by using a novel efficient optimization procedure within an annealing framework where the energy function corresponds to the primal of the problem. Experimental results on some popular benchmarks demonstrated that it is possible to reach very competitive performances by using few linear models per class instead of a single model per class with kernel. This allows the user to get very compact models which are very fast in classifying new patterns. Thus, according to the com­ putational constraints, the user may decide how to balance the trade-off between better accuracy and speed of classification. Finally, it should be noted that the proposed approach com­ pares favorably versus LVQ, a learning procedure that, simi­ larly to the proposed approach, returns a set of linear models per class.