Multicategory Classification by Support Vector Machines.
We examine the problem of how to discriminate between objects of three or more classes. Specifically, we investigate how two-class discrimination methods can be extended to the multiclass case. We show how the linear programming (LP) approaches based on the work of Mangasarian and quadratic programming (QP) approaches based on Vapniks Support Vector Machine (SVM) can be combined to yield two new approaches to the multiclass problem. In LP multiclass discrimination, a single linear program is used to construct a piecewise-linear classification function. In our proposed multiclass SVM method, a single quadratic program is used to construct a piecewise-nonlinear classification function. Each piece of this function can take the form of a polynomial, a radial basis function, or even a neural network. For the k > 2-class problems, the SVM method as originally proposed required the construction of a two-class SVM to separate each class from the remaining classes. Similarily, 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.
Introduction
We investigate the problem of discriminating large real-world datasets with
more than two classes. Given examples of points known to come from k >
classes, we construct a function to discriminate between the classes. The
goal is to select a function that will e#ciently and correctly classify future
points. This classification technique can be used for data mining or pattern
recognition. For example, the United States Postal Service is interested in an
e#cient yet accurate method of classifying zipcodes. Actual handwritten digits
from zipcodes collected by the United States Postal Service are used in our
study. Each digit is represented by a 16 by 16 pixel grayscale map, resulting in
256 attributes for each sample number. Given the enormous quantities of mail
the Postal Service sorts each day, the accuracy and e#ciency in evaluation are
extremely important.
In this paper, we combine two independent but related research directions
developed for solving the two-class linear discrimination problem. The first is
the linear programming (LP) methods stemming from the Multisurface Method
of Mangasarian [12, 13]. This method and it's later extension the Robust Linear
Programming (RLP) approach [6] have been used in a highly successfully breast
cancer diagnosis system [26]. The second direction is the quadratic programming
(QP) methods based on Vapnik's Statistical Learning Theory [24, 25]. Statistical
Learning Theory addresses mathematically the problem of how to best construct
functions that generalize well on future points. The problem of constructing the
best linear two-class discriminant can be posed as a convex quadratic program
with linear constraints. The resulting linear discriminant is known as a Support
Vector Machine (SVM) because it is a function of a subset of the training data
known as support vectors. Specific implementations such as the Generalized
Optimal Plane (GOP) method has proven to perform very well in practice [8].
Throughout this paper we will refer to the two di#erent approaches as RLP and
SVM.
The primary focus of this paper is how the the two research directions have
di#ered in their approach to solving problems with k > 2 classes. The original
SVM method for multiclass problems was to find k separate two-class discriminants
[23]. Each discriminant is constructed by separating a single class from all
the others. This process requires the solution of k quadratic programs. When
applying all k classifiers to the original multicategory dataset, multiply classified
points or unclassified points may occur. This ambiguity has been avoided by
choosing the class of a point corresponding to the classification function that
is maximized at that point. The LP approach has been to directly construct k
classification functions such that for each point the corresponding class function
is maximized [5, 6]. The Multicategory Discrimination Method [5, 6] constructs
a piecewise-linear discriminate for the k- class problem using a single linear
program. We will call this method M-RLP since it is a direction extension of
the RLP approach. We will show how these two di#erent approaches can be
combined two yield two new methods: k-RLP, and M-SVM.
In Section 2, we will provide background on the existing RLP and SVM
methods. While the k-class cases are quite di#erent, the two-class linear discrimination
methods for SVM and RLP are almost identical. They di#er only
in the regularization term used in the objective. We use the regularized form of
RLP proposed in [3] which is equivalent to SVM except that a di#erent norm
is used for the regularization term. For two-class linear discrimination, RLP
generalizes equally well and is more computationally e#cient than SVM. RLP
exploits the fact that state-of-the-art LP codes are far more e#cient and reliable
than QP codes.
The primary appeal of SVM is that they can be simply and elegantly applied
to nonlinear discrimination. With only minor changes, SVM methods can
construct a wide class of two-class nonlinear discriminants by solving a single
QP [24]. The basic idea is that the points are mapped nonlinearly to a higher
dimensional space. Then the dual SVM problem is used to construct a linear
discriminant in the higher dimensional space that is nonlinear in the original
attribute space. By using kernel functions in the dual SVM problem, SVM
can e#ciently and e#ectively construct many types of nonlinear discriminant
functions including polynomial, radial basis function machine, and neural net-
works. The successful polynomial-time nonlinear methods based on LP use a
multi-step approaches. The methods of Roy et al [20, 19, 18] use clustering in
conjuction with LP to generate neural networks in polynomial time. Another
approach is to recursively construct piecewise-linear discriminants using a series
of LP's [13, 2, 15]. These approaches could also be used with SVM but we limit
discussion to nonlinear discriminants constructed using the SVM kernel-type
approaches.
After the introduction to the existing multiclass methods, M-RLP and k-
SVM, we will show how same idea used in the M-RLP, can be adapted to
construct multiclass SVM using a single quadratic program. We adapt a problem
formulation similar to the two-class case. In the two-class case, initially
the problem is to construct a linear discriminant. The data points are then
transformed to a higher dimensional feature space. A linear discriminant is constructed
in the higher dimension space. This results in a nonlinear classification
function in the original feature space. In Section 3, for the k > 2 class case, we
begin by constructing a piecewise-linear discriminant function. A regularization
term is added to avoid overfitting. This method is then extended to piecewise-
nonlinear classification functions in Section 4. The variables are mapped to a
higher dimensional space. Then a piecewise-linear discriminant function is constructed
in the new space. This results in a piecewise-nonlinear discriminant
in the original space. In Section 5, we extend the method to piecewise inseparable
datasets. We call the final approach the Multicategory Support Vector
Machine (M-SVM). Depending on the choice of transformation, the pieces may
be polynomials, radial basis functions, neural networks, etc. We concentrate our
research on the polynomial classifier and leave the computational investigation
other classification functions as future work. Figure 1 shows a piecewise-second-
degree polynomial separating three classes in two dimensions.
M-SVM requires the solution of a very large quadratic program. When
transforming the data points into a higher dimension feature space, the number

Figure

1: Piecewise-polynomial separation of three classes in two dimensions
of variables will grow exponentially. For example, a second degree polynomial
classifier in two dimensions requires the original variables x 1 and x 2 as well as
the variables x 2
2 , and x 1 x 2 . In the primal problem, the problem size will
explode as the degree of the polynomial increases. The dual problem, however,
remains tractable. The number of dual variables is k - 1 times the number
of points regardless of what transformation is selected. In the dual problem,
the transformation appears as an inner product in the high dimensional space.
Inexpensive techniques exist for computing these inner products. Each dual
variable corresponds to a point in the original feature space. A point with a
corresponding positive dual variable is referred to as a support vector. The goal
is to maintain a high accuracy while using a small number of support vectors.
Minimizing the number of support vectors is important for generalization and
also for reducing the computational time required to evaluate new examples.
Section 6 contains computational results comparing the two LP approaches k-
RLP and M-RLP; and the the two QP approaches k-SVM and M-SVM. The
methods were compared in terms of generalization (testing set accuracy), number
of support vectors, and computational time.
The following notation will be used throughout this paper. Mathematically
we can abstract the problem as follows: Given the elements of the sets, A i ,
1, . , k, in the n-dimensional real space R n , construct a a discriminant function
is determined which separates these points into distinct regions. Each region
should contains points belonging to all or almost all of the same class. Let A j be
a set of points in the n-dimensional real space R n with cardinality m j . Let A j
be an m j -n matrix whose rows are the points in A j . The i th point in A j and
the i th row of A j are both denoted A j
. Let e denote a vector of ones of the
appropriate dimension. The scalar 0 and a vector of zeros are both represented
by 0. Thus, for x # R n , x > 0 implies that x i > 0 for Similarly,
n. The set of minimizers of f(x) on the
set S is denoted by arg min
x#S
f(x). For a vector x in R n , x+ will denote the vector
in R n with components (x+ n. The step function
x # will denote the vector in [0, 1] n with components
n. For the vector x in R n and the matrix A in
R n-m , the transpose of x and A are denoted x T and A T respectively. The dot
product of two vectors x and y will be denoted x T y and
Background
This section contains a brief overview of the RLP and SVM methods for clas-
sification. First we will discuss the two-class problem using a linear classifier.
Then SVM for two classes will be defined. Then RLP will be reviewed. Finally,
the piecewise-linear function used for multicategory classification in M-RLP will
be reviewed.
2.1 Two Class Linear Discrimination
Commonly, the method of discrimination for two classes of points involves determining
a linear function that consists of a linear combination of the attributes
of the given sets. In the simplest case, a linear function can be used to separate
two sets as shown in Figure 2. This function is the separating plane x T
PSfrag replacements

Figure

2: Two linearly separable sets and a separating plane
where w is the normal to the plane and # is the distance from the origin. Let
A 1 and A 2 be two sets of points in the n-dimensional real space R n with
cardinality m 1 and m 2 respectively. Let A 1 be an m 1 - n matrix whose rows
are the points in A 1 . Let A 2 be an m 2 - n matrix whose rows are the points in
A 2 . Let x # R n be a point to be classified as follows:
The two sets of points, A 1 and A 2 , are linearly separable if
where e is a vector of ones of the appropriate dimension. If the two classes are
linear separable, there are infinitely many planes that separate the two classes.
The goal is two choose the plane that will generalize best on future points.
Both Mangasarian [12] and Vapnik and Chervonenkis [25] concluded that
the best plane in the separable case is the one that minimizes the distance of
the closest vector in each class to the separating plane. For the separable case
the formulations of Mangasarian's Multi-surface Method of Pattern Recognition
[13] and those of Vapnik's Optimal Hyperplane [24, 25] are very similar [3]. We
will concentrate on the Optimal Hyperplane problem since it the basis of SVM,
and it is validated theoretically by Statistical Learning Theory [24]. According
to Statistical Learning Theory, the Optimal Hyperplane can construct linear
PSfrag replacements
Class A 1
Class A 2

Figure

3: Two supporting planes and the resulting optimal separating plane
discriminants in very high dimensional spaces without overfitting. The reader
should consult [24] for full details of Statistical Learning Theory not covered in
this paper.
The problem in the canonical form of Vapnik [24] becomes to determine two
parallel planes
and the margin or distance between the two planes is maximized. The margin
of seperation between the two supporting planes is 2
#w#
. An example of such
a plane is shown in Figure 3. The problem of finding the maximum margin
becomes[24]:
min
In general it is not always possible for a single linear function to completely
separate two given sets of points. Thus, it is important to find the linear function
that discriminates best between the two sets according to some error minimization
criterion. Bennett and Mangasarian [4] minimize the average magnitude of
the misclassification errors in the construction of their following robust linear
programming problem (RLP).
min
subject to y
z -A 2 w
are the misclassification costs. To avoid the null
solution
are the cardinalities
of A 1 and A 2 respectively. The RLP method is very e#ective in practice.
The functions generated by RLP generalize well on many real-world problems.
Additionally, the computational time is reasonably small because its solution
involves only a single linear program. Note however that the RLP method no
longer includes any notion of maximizing the margin. Statistical Learning Theory
indicates that the maximizing the margin is essential for good generalization.
The SVM approach [8, 23] is a multiobjective quadratic program which minimizes
the absolute misclassification errors, and maximizing the separation margin
by minimizing #w# 2 .
min
fixed constant. Note that Problem 6 is equivalent to RLP
with the addition of a regularization term #
A linear programming version of (6) can be constructed by replacing the
norm used to minimize the weights w [3]. Recall that the SVM objective
minimizes the square of the 2-norm of w, #w# The 1-norm of w,
|w|, can be used instead. The absolute value function can be removed
by introducing the variable s and the constraints -s # w # s. The
SVM objective is then modified by substituting e T s for w T w. At optimality,
k. The resulting LP is:
min
w,#,y,z,s
We will refer to this problem as RLP since yields the original RLP method.
As in the SVM method, the RLP method minimizes both the average distance
of the misclassified points from the relaxed supporting planes and the
maximum classification error. The main advantage of the RLP method over the
SVM problem is that RLP is a linear program solvable using very robust algorithms
such as the Simplex Method [17]. SVM requires the solution of quadratic
program that is typically much more computationally costly for the same size
problem. In [3], the RLP method was found to generalize as well as the linear
SVM but with much less computational cost.
It is more e#cient computationally to solve the dual RLP and SVM prob-
lems. The dual RLP problem is
min
u,v
#e
In this paper we use #
but # 1 and # 2 may be any positive
weights for the misclassification costs. The dual SVM problem and its extension
to nonlinear discriminants is given in the next section.
2.2 Nonlinear Classifiers Using Support Vector Machines
The primary advantage of the SVM (6) over RLP (7) is that in its dual form it
can be used to construct nonlinear discriminants. using polynomial separators,
radial basis functions, neural networks, etc. The basic idea is to map the original
problems to a higher dimensional space and then to construct a linear discriminant
in a higher dimensional space that corresponds to a linear discriminant
in the original space. So for example, to construct a quadratic discriminant
for a two dimensional problems, the input attributes [x 1 , x 2 are mapped into
and a linear discriminant function is constructed in the
new five-dimensional space. Two examples of possible polynomial classifiers
are given in Figure 4. The dual SVM is applied to the mapped points. The
regularization term in the primal objective helps avoid overfitting the higher
dimensional space. The dual SVM provides a practical computational approach
through the use of generalized inner products or kernels.

Figure

4: Two examples of second degree polynomial separations of two sets
The dual SVM is as follows: as follows:
min
To formulate the nonlinear case it is convenient to rewrite the problem in
summation notation. Let A be the set of all points A 1 and A 2 . Define
2 to be the total number of points. Let #
be such that for x i # A t
To construct the nonlinear classification function, the original data points
x are transformed to the higher dimension feature space by the function #(x) :
n. The dot product of the original vectors x T
replaced
by the dot product of the transformed vectors (#(x i
The first term of the objective function can then be written as the sum:
Using this notation and simplifying the problem becomes:
min
s.t.
In the support vector machine (SVM), Vapnik replaces the inner product
with the inner product in the Hilbert space K(x, x i ). This symmetric
function K(x, x i ) must satisfy Theorem 5.3 in [23]. This theorem ensures
is an inner product in some feature space. The choice of K(x, x i ) determines
the type of classifier that is constructed. Possible choices include polynomial
classifiers as in Figure 4 (K(x, x d is the degree of
the polynomial), radial basis function machines (K # (|x-x i
where |x - x i | is the distance between two vectors and # is the width parame-
ter), and two-layer neural networks (K(x, x
sigmoid function) [23]. Variants of SVM (10) have proven to be quite successful
in paractice [21, 22, 7].
Note that the number of variables in Program (10) remains constant as
increases in dimensionality. Additionally, the objective function remains
quadratic and thus the complexity of the problem does not increase. In
fact, the size of the problem is dependent on the number of nonzero dual variables
. The points x i corresponding to these variables are called the support
vectors. According to Statistical Learning Theory, the best solution for a given
misclassification error uses the minimum number of support vectors.
The final classification function with the generalized kernel function K(x, x i
is:
support vectors
PSfrag replacements
A 3

Figure

5: Piecewise-linear separation of sets A 1 , A 2 , and A 3 by the convex
piecewise-linear function f(x).
2.3 Multicategory Discrimination
In multicategory classification a piecewise-linear separator is used to discriminate
points. We will examine
two methods for accomplishing this. The first used in SVM [24] is two construct
a discriminate function to separate one class from the remaining k - 1
classes. This is process is repeated k times. In the separable case, the linear
discriminant for each class must satisfy the following set of inequalities. Find
(w
To classify a new point x, compute f i
one i then clearly the point belongs to Class A i . If more than one f i (x) > 0 or
then the class is ambiguous. Thus the general rule is
that the class of a point x is determined from (w i , # i finding i
such that
is maximized. Figure 5 shows a piecewise-linear function
R that separates three sets.
Note either SVM (10) or RLP can be used to construct the k two-class
discriminants. For clarity, we will call this method used with SVM (10), k-
SVM. We will denote this method used with RLP (8), k-SVM. The advantage
of k-SVM is that it can used for piecewise-nonlinear discriminants which k-RLP
is limited to piecewise-linear discriminants. For both k-SVM and k-RLP to
attain perfect training set accuracy, following inequalities must be satisfied:
This inequality can be used as a definition of piecewise-linear separability.
Definition 2.1 (Piecewise-linear Separability) The sets of points A i ,
1, . , k, represented by the matrices A i
are piecewise-
linearly separable if there exist w i
Equivalent to Definition 2.1, finding the piecewise-linear separator involves
solving the equation A i w i
e,
can be rewritten as 0 # -A i (w i
e,

Figure

6 shows an example of a piecewise-linear separator for three classes in two
dimensions. The linear separating functions are represented by the quantities
PSfrag replacements
A 3

Figure

Three classes separated by a piecewise-linear function.
(w i
1, . , k.
The M-RLP method 1 proposed and investigated in [5, 6] can be used to find
(w
min
In M-RLP (15), if the optimal objective value is zero,
then the dataset is piecewise-linearly separable. If the dataset is not piecewise-
linearly separable, the positive values of the variables y ij
l are proportional to the
1 The method was originally called Multicategory Discrimination
magnitude of the misclassified points from the plane x T (w i
This program (15) is a generalization of the two-class RLP linear program (5)
to the multicategory case. Like the original RLP (5) M-RLP does not include
any terms for maximizing the margin and it does not directly permit the use of
generalized inner products or kernels to allow extension to the nonlinear case.
So in the next section we will show how M-RLP and SVM can be combined by
including margin maximization and generalized inner products into M-RLP.
3 Formulation of M-SVM: Piecewise-linear Separable
Case
We now propose to construct piecewise-linear and piecewise-nonlinear SVM using
a single quadratic program. Analogous to the two class case we start by
formulating the "optimal" piecewise-linear separator for the separable case. Assume
that the k sets of points are piecewise-linearly separable, i.e., there exist
The class of a point x is determined from (w i , # i finding i such
that
is maximized.
For this piecewise-linearly separable problem, infinitely many (w i , exist
that satisfy (16). Intuitively, the "optimal" (w i , # i ) provides the largest margin
of classification. So in an approach analogous to the two class support vector
machine (SVM) approach, we add regularization terms. The dashed lines in

Figure

7 represent the margins for each piece (w i
of the piecewise-linear
separating function. The margin of separation between the classes i and
j, i.e. the distance between
and
is 2
# . So, we would like to minimize # w i
# for all
Also, we will add the regularization term 1k
to the objective. For the
piecewise-linearly separable problem we get the following:
min
s.t. A i (w i
To simplify the notation for formulation of the piecewise-linear SVM, we
rewrite this in matrix notation. See Appendix A for complete matrix definitions
for general k. For the three class problem the following matrices are
Let
PSfrag replacements
(w 1
A 3
(w 1
(w 2
(w 1
(w 1

Figure

7: Piecewise-linear separator with margins for three classes.
where I # R n-n is the identity matrix.
Let
where A i
is a vector of
ones.
Using this notation for fixed k > 2 the program becomes:
min
, . , w k T
The dual of this problem can be written as:
A T u
To eliminate the variables w and # from this problem we will first show that
the matrix
C) is nonsingular.
Proposition 3.1 (Nonsingularity of
C)) The inverse of matrix (I+
C) for k > 2 is
I nk+1 I n - 1
I nk+1 I n
. 1
I nk+1 I n - 1
I nk+1 I n
where I n indicates the n - n identity matrix.
Proof. To show that
C) is nonsingular for some k > 2, we will calculate
its inverse. The matrix -
C as defined in Appendix A has size (n
(i - 1)-
kn). Recall that n indicates the dimension of the feature space.
-In
. -In
-In -In (k - 1)I n
has size kn - kn.
Therefore
I kn
kIn -In -In
-In
. -In
-In -In kIn
Through simple calculations it can be shown that the inverse of this matrix
is
I nk+1 I n - 1
I nk+1 I n
. 1
I nk+1 I n - 1
I nk+1 I n
Using Proposition 3.1 the following relationship results:
A T . (22)
It follows from Problem (20) and equation (22) that
A T
A T u. (23)
Using this relationship, we eliminate w from the dual problem. Additionally, #
is removed because -
After some simplification the new dual problem becomes:
A T u
To construct the multicategory support vector machine, it is convenient to
this problem in summation notation. Let the dual vector
,
, . , u 1k T
,
,
, . , u k(k-1) T
. The resulting dual problem for piecewise-linear datasets is:
l
li
l
l
l # 0 for
is the number of points in class i.
Recall, for the piecewise-linear classification function, the class of a point x
is determined by finding
is maximized. From equation (23),
A T u.
Solving for w i in summation notation we get:
Therefore,
4 Formulation of M-SVM: Piecewise-nonlinearly
Separable Case
Just like in the two-class case, M-SVM can be generalized to the piecewise-
nonlinear functions. To construct the separating functions, f i (x), in a higher
dimension feature space, the original data points x are transformed by some
8]. The function f i (x) is now related to the sum
of dot products of vectors in this higher dimension feature space:
According to [23], any symmetric function K(x, x
Theorem [9] can replace the dot product (#(x) - #(x i )). Mercer's Theorem guarantees
that any eigenvalue # j in the expansion K(x, x
is positive. This is a su#cient condition for a function K(x, x i ) to define a dot
product in the higher dimension feature space. Therefore we let K(x, x
Returning to dual Problem (25), the objective function contains the sum of
dot products A j
T of two points in the original feature space. To transform
the points A j
p to a higher dimension feature space we replace these dot products
by
The resulting M-SVM for piecewise-linearly separable datasets is:
l
li
, A l
l
l
l # 0 for
The points A i
l corresponding to nonzero dual variables u ij
l
are referred to as support vectors. It is possible for A i
l to correspond with more

Figure

8: Piecewise-polynomial separation of three classes in two dimensions.
Support vectors are indicated with circles.
than one nonzero variable
l In Figure 8, support vectors
are represented by a circle around the point. Some points have double circles
which indicate that two dual variables u ij
l > 0, By the
complementarity within the KKT conditions [14],
l
l (w i
Consequently the support vectors are located "closest" to the separating func-
tion. In fact, the remainder of the points, those that are not support vectors,
are not necessary in the construction of the separating function. The resulting
nonlinear classification problem for a point x is to find such that
the classification function
support vectors
support vectors
is maximized.
5 Formulation of M-SVM: Piecewise Inseparable
Case
The proceeding sections provided a formulation for the piecewise-linearly and
piecewise-nonlinear separable cases. To construct a classification function for a piecewise-
linearly inseparable dataset, we must first choose an error minimization crite-
rion. The technique used in the preceeding sections of formulating the M-SVM
for piecewise-linearly separable datasets can be combined with the 1-norm error
criterion used in Problem (15) of Bennett and Mangasarian [6]. The result is
the M-SVM for piecewise-linearly inseparable problems.
Using the same matrix notation as in Section 3, we add the terms 1
to the objective of Problem (15). The resulting primal problem is as
follows:
min
w,#,y
13 , . , y T
Solving for the dual, substituting
A T u, and simplifying produces
the following problem:
A T u
As shown in Proposition 5.1, Problem (30) maximizes a concave quadratic
objective over a bounded polyhedral set. Thus there exists a locally optimal
solution that is globally optimal.
Proposition 5.1 (Concavity of objective) The function u T e- 1
A T u
is concave.
Proof. The matrix -
A T is always positive semi-definite and symmetric.
Thus the Hessian matrix (= - 1
A T ) is negative semi-definite. Therefore,
the objective is a concave function.
Problem (30) is identical to Problem (24) in the piecewise-linearly separable
case except the dual variables are now bounded by 1-#
# . Therefore, transforming
the data points A i
l will proceed identically as in Section 4. Using the function
to denote the dot product in some feature space, the final M-SVM
results:
l
li
, A l
l # 1-#
# for
As in Sections 3 and 4, the class of a point x is determined by finding the
maximum function
support vectors
support vectors
To determine the threshold values # i , we solve the primal problem
with w fixed, where -
Aw is transformed to the higher dimension feature
space. This problem is as follows:
min
#,y
l
s.t.
r
l
, A l
r
li
r
r
l
, A l
r
r
l # 0,
The right side of the constraints are constant. Thus Problem (33) is a linear
program and is easily solved.
6 Computational Experiments
In this section, we present computational results comparing M-SVM (32), M-
RLP (15), k-SVM using SVM (10), and k-RLP using RLP (8). Several experiments
on real-world datasets are reported. A description of each of the
datasets follows this paragraph. Each of these methods was implemented using
the MINOS 5.4 [17] solver. The quadratic programming problems for M-
SVM and k-SVM were solved using the nonlinear solver implemented in Minos
5.4. This solver uses a reduced-gradient algorithm in conjunction with a quasi-Newton
method. In M-SVM, k-SVM and M-RLP, the selected values for #
are given. Better solutions may result with di#erent choices of #. Addition-
ally, it is not necessary for the same value of # to be used for both methods.
The kernel function for the piecewise-nonlinear M-SVM and k-SVM methods is
, where d is the degree of the desired polynomial.
Wine Recognition Data The Wine dataset [1] uses the chemical analysis
of wine to determine the cultivar. There are 178 points with 13 features. This is
a three class dataset distributed as follows: 59 points in class 1, 71 points in class
2, and 48 points in class 3. This dataset is available via anonymous file transfer
protocol (ftp) from the UCI Repository of Machine Learning Databases and
Domain Theories [16] at ftp://ftp.ics.uci.edu/pub/machine-learning-databases.
Glass Identification Database The Glass dataset [11] is used to identify
the origin of a sample of glass through chemical analysis. This dataset is comprised
of six classes of 214 points with 9 features. The distribution of points by
class is as follows: 70 float processed building windows, 17 float processed vehicle
windows, 76 non-float processed building windows, 13 containers, 9 tableware,
and 29 headlamps. This dataset is available via anonymous file transfer protocol
(ftp) from the UCI Repository of Machine Learning Databases and Domain
Theories [16] at ftp://ftp.ics.uci.edu/pub/machine-learning-databases.
US Postal Service Database The USPS Database [10] contains zipcode
samples from actual mail. This database is comprised of separate training and
testing sets. There are 7291 samples in the training set and 2007 samples in the
testing set. Each sample belongs to one of ten classes: the integers 0 through
9. The samples are represented by 256 features.
Two experiments were performed. In the first, the datasets were normalized
between -1 and 1. 10-fold cross validation was used to estimate generalization
on future data. The second experiment was conducted on two subsets of the
United States Postal Service (USPS) data. This data contains handwriting
samples of the integers 0 through 9. The objective of this dataset is to quickly
and e#ectively interpret zipcodes. This data has separate training and testing
sets, each of which consist of the 10 integer classes. We compiled two individual
training subsets from the USPS training data. The first subset contains 1756
examples each belonging to the classes 3, 5, and 8. We call this set USPS-1
training data. The second subset contains 1961 examples each belonging to the
classes 4, 6, and 7. We call this set USPS-2 training data. Similarly two subsets
are created from the testing data. In all of these datasets, the data values are
scaled by 1. Testing set accuracies are reported for all four methods. The
total numbers of unique support vectors in the resulting classification functions
for the M-SVM and k-SVM methods are given.

Table

contains results for M-RLP, k-RLP, M-SVM, and k-SVM on the
Wine and Glass datasets. As anticipated, adding the regularization term to
M-SVM 97.19 97.19 97.75 96.63 96.63
Glass M-RLP 64.95 -
k-SVM 43.46 55.61 64.95 70.56 72.43

Table

1: Percent testing set accuracies and (total number of support vectors)
for M-SVM and k-SVM.05 for k-RLP, M-SVM, and k-SVM.
the degree one problem in M-SVM produced better testing generalization than
M-RLP on the Wine dataset. The Wine dataset is piecewise-linearly separable.
Therefore, the M-RLP method has infinitely many optimal solutions. How-
ever, the testing accuracy for M-SVM with degree one on the Glass data was
much lower than the M-RLP accuracy. This may indicate that the choice of
# is too large. However, as the degree increases the accuracy of the M-SVM
method improves and exceeds the M-RLP results. The k-SVM method generalized
surprisingly well. The testing accuracies reported for k-SVM on the Wine
dataset are higher than those of M-SVM. The linear k-RLP method performed
just as well as the quadratic k-SVM program on the Wine dataset and better
than the M-SVM and M-RLP methods. On the Glass data, as the degree in-
creases, both methods, M-SVM and k-SVM, improve dramatically in testing
accuracy. Using higher degree polynomials the M-SVM and k-SVM methods
surpass the accuracies of M-RLP and k-RLP. This demonstrates the potential
for polynomial and piecewise-polynomial classification functions over linear and
piecewise-linear functions.

Table

contains results for the four methods on the USPS data subsets.
Similar observations as above can be made. Both of these datasets are piecewise-
linearly separable. The solution that m-RLP has found for each of these datasets
tests significantly lower than the other methods. The k-SVM method generalizes
slightly better than M-SVM. The k-RLP method reports similar accuracies
as the k-SVM method. Additionally, it is solving linear programs rather than
quadratic programs, so the computational training time is significantly smaller
than the other methods. Changing the parameter # may further improve gener-
alization. The M-SVM method consistently finds classification functions using
fewer support vectors than those of k-SVM. With fewer support vectors, a sam-
M-SVM 91.26 91.87 92.28 92.07 92.28
k-SVM 91.67 92.28 92.89 92.68 92.48
M-SVM 94.58 94.97 95.36 94.97 94.00
k-SVM 96.13 96.52 96.13 95.16 94.58

Table

2: Percent testing set accuracies and (total number of support vectors)
for M-SVM and SVM.05 for k-SVM and
Degree

Table

3: Total computational training time (in seconds) for M-RLP,k-RLP,
M-SVM, and k-SVM on USPS-1.
ple can be classified more quickly since the dot-product of the sample with each
support vector must be computed. Thus the M-SVM would be a good method
to choose when classification time is critical.
CPU times for training all four methods on the USPS-1 dataset are reported
in

Table

3. The times for all the datasets are not listed because the programs
were run using a batch system on clusters of machines so the timing was not
reliable. However, the trends were clear. The k-RLP method is significantly
faster than the other methods. In the M-SVM and k-SVM methods, as the
degree increased the computational time would decrease and then after a certain
degree is reached it would increase. The degree of the polynomial for which it
starts to increase varies by dataset. Surprisingly, for the USPS datasets the
k-SVM method was faster than the M-RLP method. This was not the case for
the Wine and Glass datasets. The M-RLP method had faster training times
than k-SVM for these datasets. The times reported are for IBM RS6000 model
590 workstations with 128 MB RAM.
Conclusions
We have examined four methods for the solution of multicategory discrimination
problems based on the LP methods of Mangasarian and the QP methods for
SVM of Vapnik. The two-class methods, RLP and SVM are di#er only in the
norm of the regularization term. In the past two di#erent approaches had been
used for the k > 2 class case. The method we called k-SVM, constructed k
two-class discriminants using k quadratic programs. The resulting classifier was
a piecewise-linear or piecewise nonlinear discriminant function depending on
what kernel function was used in the SVM. The original multicategory RLP
for k classes, constructed a piecewise-linear discriminant using a single linear
program. We proposed two new hybrid approaches. Like the k-SVM method, k-
RLP uses LP to construct k two-class discriminants. We also formulated a new
approach, M-SVM. We began the formulation by adding regularization terms to
M-RLP. Then like k-SVM with piecewise-nonlinear discriminants, the nonlinear
pieces are found by mapping the original data points into a higher dimension
feature space. This transformation appeared in the dual problem as an inner
product of two points in the higher dimension space. A generalized inner product
was used to make the problem tractable. The new M-SVM method requires
the solution of a single quadratic program. We performed a computational
study of the four methods on four datasets. In general we found that the k-
SVM and k-RLP generalized. However, M-SVM used fewer support vectors - a
counter-intuitive result since for the two-class class Statistical Learning Theory
predicts that fewer support vector should result in better generalization. The
theoretic justification of the better generalization of k-SVM and k-RLP and M-
SVM and M-RLP is an open question. The k-RLP method provided accurate
and e#cient results on the piecewise-linear separable datasets. The k-SVM
also tested surprisingly well but requires the solution of k quadratic programs.
Thus providing solutions with smaller classification time. On the piecewise-
linearly inseparable dataset, the polynomial and piecewise-polynomial classifiers
provided an improvement over the M-RLP and k-RLP methods. On the other
datasets, the k-RLP method found solutions that generalized best or nearly best
in less computational time.
A Matrix Representations for Multicategory Support
Vector Machines
This appendix contains the definitions of the matrices used for the general k-class
SVM formulation (18):
min
Let
I -I
I
. 0 . 0
. 0 0 . 0
I
. 0 . 0
. 0 . 0
where I # R n-n is the identity matrix. The matrix -
C has n
. 0 . 0
. 0 0 .
. 0 . 0
. -
. 0 . 0
. 0 . 0
where A i
. The matrix -
A has
. 0 . 0
. 0 0 .
. 0 . 0
. -
. 0 . 0
. 0 . 0
is a vector of ones. The matrix -



--R

Comparison of classifiers in high dimensional settings.
Decision tree construction via linear programming.
Geometry in learning.
Neural network training via linear programming.
Multicategory discrimination via linear programming.
Serial and parallel multicategory discrimination.

Support vector networks.
Methods of Mathematical Physics.

Rule induction in forensic science.
Linear and nonlinear separation of patterns by linear programming.

Nonlinear Programming.
Mathematical programming in machine learning.
UCI repository of machine learning databases.
MINOS 5.4 user's guide.
An algorithm to generate radial basis function (RBF)-like nets for classification problems
A polynomial time algorithm for the construction and training of a class of multilayer perceptrons.
Pattern classification using linear program- ming
Incorporating invariances in support vector machines.
Comparing support vector machines with gaussian kernels to radial basis function classifiers.
The Nature of Statistical Learning Theory.
The Nature of Statistical Learning Theory.
Theory of Pattern Recognition.
Multisurface method of pattern separation for medical diagnosis applied to breast cytology.
--TR
A polynomial time algorithm for the construction and training of a class of multilayer perceptrons
An algorithm to generate radial basis function (RBF)-like nets for classification problems
The nature of statistical learning theory
Networks
Feature minimization within decision trees
Feature Selection via Concave Minimization and Support Vector Machines
Incorporating Invariances in Support Vector Learning Machines
Comparison of View-Based Object Recognition Algorithms Using Realistic 3D Models
Comparing Support Vector Machines with Gaussian Kernels to Radial Basis Function Classifiers

--CTR
Tie-Yan Liu , Yiming Yang , Hao Wan , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, Support vector machines classification with a very large-scale taxonomy, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.36-43, June 2005
Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
Rong Jin , Jian Zhang, Multi-Class Learning by Smoothed Boosting, Machine Learning, v.67 n.3, p.207-227, June      2007
Glenn M. Fung , O. L. Mangasarian, Multicategory Proximal Support Vector Machine Classifiers, Machine Learning, v.59 n.1-2, p.77-97, May       2005
Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
Yiguang Liu , Zhisheng You , Liping Cao, A novel and quick SVM-based multi-class classifier, Pattern Recognition, v.39 n.11, p.2258-2264, November, 2006
Ping Zhong , Masao Fukushima, Second-order cone programming formulations for robust multiclass classification, Neural Computation, v.19 n.1, p.258-282, January 2007
Andreas Albrecht , Chak-Kuen Wong, Approximation of Boolean Functions by Local Search, Computational Optimization and Applications, v.27 n.1, p.53-82, January 2004
Isabelle Guyon , Jason Weston , Stephen Barnhill , Vladimir Vapnik, Gene Selection for Cancer Classification using Support Vector Machines, Machine Learning, v.46 n.1-3, p.389-422, 2002
Fabien Lauer , Ching Y. Suen , Grard Bloch, A trainable feature extractor for handwritten digit recognition, Pattern Recognition, v.40 n.6, p.1816-1824, June, 2007
support vector machines;data mining;classification;linear programming;machine learning