We examine the problem of how to discriminate between objects of three or m
ore classes. Specifically, we investigate how two-class discrimination meth
ods can be extended to the multiclass case. We show how the linear programm
ing (LP) approaches based on the work of Mangasarian and quadratic programm
ing (QP) approaches based on Vapnik's Support Vector Machine (SVM) can be c
ombined to yield two new approaches to the multiclass problem. In LP multic
lass discrimination, a single linear program is used to construct a piecewi
se-linear classification function. In our proposed multiclass SVM method, a
single quadratic program is used to construct a piecewise-nonlinear classi
fication function. Each piece of this function can take the form of a polyn
omial, a radial basis function, or even a neural network. For the k > 2-cla
ss problems, the SVM method as originally proposed required the constructio
n of a two-class SVM to separate each class from the remaining classes. Sim
ilarily, k two-class linear programs can be used for the multiclass problem
. We performed an empirical study of the original LP method, the proposed k
LP method, the proposed single QP method and the original k QP methods. We
discuss the advantages and disadvantages of each approach.