152
5: Mahesh Pal, Pakorn Watanachaturaporn
5.4.4
Multiclass Objective Function
Instead of creating many binary classifiers to determine the class labels, this
method attempts to directly solve a multiclass problem (Weston and Watkins
1998, 1999; Lee et al. 2001; Crammer and Singer 2001; Scholkopf and Smola
2002). This is achieved by modifying the binary class objective function and
adding a constraint to it for every class. The modified objective function allows
simultaneous computation of multiclass classification and is given by Weston
and Watkins (1998):
[
1 M
k ]
min - L IIwI12 + CLL~i '
w,b,~
2.
.
1= 1
1= 1 riYi
(5.56)
subject to the constraints
W Yi . Xi + b Yi :::: Wr . Xi + br + 2 - ~i for i = 1, ... , k
(5.57)
and
~i :::: 0 for i = 1, ... , k ,
(5.58)
where Yi E {I, ... , M} are the multiclass labels of the data vectors and r E
{I, ... , M} \Yi are multiclass labels excluding Yi.
Lee et al. (2001) and Scholkopf and Smola (2002) showed that the results
from this method and the one-against-the-rest method are similar. However,
in this method, the optimization algorithm has to consider all the support
vectors at the same time. Therefore, although it may be able to handle massive
data sets but the memory requirement and thus, the computational time may
be very high.
Thus, the choice of a multiclass method depends on the problem at hand.
A user should consider the accuracy requirements, the computational time, the
resources available and the nature of the problem. For example, the multiclass
objective function approach may not be suitable for a problem that contains
a large number of training samples and classes due to the requirement oflarge
memory and extremely long computational time.
5.5
Optimization Methods
One of the key processing steps in the development of SVM algorithms is to
employ an optimization method to find the support vectors. A variety of optimization methods may be used. Typically, the conventional SVMs have used an
optimizer based on quadratic programming (QP) or linear programming (LP)
methods to solve the optimization problem. Most of the QP algorithms are
based on a conjugate gradient, quasi-Newton or a prime-dual interior-point
5: Mahesh Pal, Pakorn Watanachaturaporn
5.4.4
Multiclass Objective Function
Instead of creating many binary classifiers to determine the class labels, this
method attempts to directly solve a multiclass problem (Weston and Watkins
1998, 1999; Lee et al. 2001; Crammer and Singer 2001; Scholkopf and Smola
2002). This is achieved by modifying the binary class objective function and
adding a constraint to it for every class. The modified objective function allows
simultaneous computation of multiclass classification and is given by Weston
and Watkins (1998):
[
1 M
k ]
min - L IIwI12 + CLL~i '
w,b,~
2.
.
1= 1
1= 1 riYi
(5.56)
subject to the constraints
W Yi . Xi + b Yi :::: Wr . Xi + br + 2 - ~i for i = 1, ... , k
(5.57)
and
~i :::: 0 for i = 1, ... , k ,
(5.58)
where Yi E {I, ... , M} are the multiclass labels of the data vectors and r E
{I, ... , M} \Yi are multiclass labels excluding Yi.
Lee et al. (2001) and Scholkopf and Smola (2002) showed that the results
from this method and the one-against-the-rest method are similar. However,
in this method, the optimization algorithm has to consider all the support
vectors at the same time. Therefore, although it may be able to handle massive
data sets but the memory requirement and thus, the computational time may
be very high.
Thus, the choice of a multiclass method depends on the problem at hand.
A user should consider the accuracy requirements, the computational time, the
resources available and the nature of the problem. For example, the multiclass
objective function approach may not be suitable for a problem that contains
a large number of training samples and classes due to the requirement oflarge
memory and extremely long computational time.
5.5
Optimization Methods
One of the key processing steps in the development of SVM algorithms is to
employ an optimization method to find the support vectors. A variety of optimization methods may be used. Typically, the conventional SVMs have used an
optimizer based on quadratic programming (QP) or linear programming (LP)
methods to solve the optimization problem. Most of the QP algorithms are
based on a conjugate gradient, quasi-Newton or a prime-dual interior-point