Support Vector Machines for Multi-class Pattern Recognition 1. K-class Pattern Recognition 2. Solving K-class Problems with Binary Svms
The solution of binary classiication problems using support vector machines (SVMs) is well developed, but multi-class problems with more than two classes have typically been solved by combining independently produced binary classiiers. We propose a formulation of the SVM that enables a multi-class pattern recognition problem to be solved in a single optimisation. We also propose a similar generalization of linear programming machines. We report experiments using benchmark datasets in which these two methods achieve a reduction in the number of support vectors and kernel calculations needed. The k-class pattern recognition problem is to construct a decision function givenìid (independent and identically distributed) samples (points) of an unknown function, typically with noise: class of the sample. A natural loss function is the number of mistakes made. For the binary pattern recognition problem (case k = 2), the support vector approach has been well developed 3, 5]. The classical approach to solving k-class pattern recognition problems is to consider the problem as a collection of binary classiication problems. In the one-versus-rest method one constructs k classiiers, one for each class. The n th classiier constructs a hyperplane between class n and the k ? 1 other classes. A particular point is assigned to the class for which the distance from the margin, in the positive direction (i.e. in the direction in which class \one" lies rather than class \rest"), is maximal. This method has been used widely in