Support Vector Machines
153
method, which are implemented through a number of optimization packages such as CPLEX (CPLEX Optimization Inc. 1992), MINOS (Murtagh and
Saunders 1987), and LOQO (Vanderbei 1997). The major disadvantage of QP
algorithms is the storage requirement of the kernel data matrix in the memory.
When the size of the kernel data matrix is large, it requires huge memory, which
may not always be available. Therefore, these algorithms may be suitable for
small datasets and may have limitations in processing large datasets such as
hyperspectral images. Alternate optimization methods may therefore have to
be considered.
Bennett and Campbell (2000) and Campbell (2002) have suggested an optimization method that sequentially updates the Lagrange multipliers based
on the Hildreth's optimization technique called the Kernel Adatron (KA) algorithm (Campbell and Cristianini 1998; Luenberger 1984). This method is
relatively easy to implement. However, it is not as fast as most of the QP and
LP optimization algorithms, especially for small datasets.
Other alternatives that work on a smaller or a subset of the whole dataset
are chunking and decomposition methods. These methods are based on the
assumption that the number of support vectors is quite small in comparison
to the total number of training samples. Instead of sequentially updating the
Lagrange multipliers, these methods update the Lagrange multipliers in parallel since they update many parameters in each iteration unlike other methods
that update one parameter at a time. In the chunking method, QP is used
to optimize an initial arbitrary subset of data. The support vectors found by
the optimizer from this subset are kept while other data points are discarded.
A new subset is then selected based on these support vectors and the additional
data. The process is then repeated until the margin is maximized. However,
the chunking method fails when the training data set is too large or most of
the training data points become support vectors. The decomposition method,
on the other hand, works on the fixed size working dataset rather than an arbitrary size as in the chunking method. A QP optimizer updates the Lagrange
multipliers on the fixed size working dataset only; the other Lagrange multipliers that are not in the working set are kept fixed. To summarize, the chunking
and decomposition methods use a QP or LP optimizer to solve the problem
by considering many small datasets rather than a single huge dataset. The Sequential Minimal Optimization (SMO) algorithm (Platt 1999) is a special case
of the decomposition method when the size of working dataset is fixed at two
such that an analytical solution is derived in very few numerical operations.
This discards the use of QP or LP optimizer. This method needs more number
of iterations but requires a small number of operations thus resulting in an
increase in optimization speed for very large data sets.
Mangasarian and Musicant (1998) introduced the Successive Over relaxation
method (SOR) for SVM, which combines SVM with SOR, and uses linear
programming to solve the optimization problem. This is done by introducing
an extra term in the objective function (5.14) and (5.32), which results in the
elimination of the equality constraint (5.24), (5.43) and (5.52). The optimization
problem requires the adjustment of only one point (one Lagrange multiplier)
at a time rather than two points during each iteration as in the SMO algorithm.
153
method, which are implemented through a number of optimization packages such as CPLEX (CPLEX Optimization Inc. 1992), MINOS (Murtagh and
Saunders 1987), and LOQO (Vanderbei 1997). The major disadvantage of QP
algorithms is the storage requirement of the kernel data matrix in the memory.
When the size of the kernel data matrix is large, it requires huge memory, which
may not always be available. Therefore, these algorithms may be suitable for
small datasets and may have limitations in processing large datasets such as
hyperspectral images. Alternate optimization methods may therefore have to
be considered.
Bennett and Campbell (2000) and Campbell (2002) have suggested an optimization method that sequentially updates the Lagrange multipliers based
on the Hildreth's optimization technique called the Kernel Adatron (KA) algorithm (Campbell and Cristianini 1998; Luenberger 1984). This method is
relatively easy to implement. However, it is not as fast as most of the QP and
LP optimization algorithms, especially for small datasets.
Other alternatives that work on a smaller or a subset of the whole dataset
are chunking and decomposition methods. These methods are based on the
assumption that the number of support vectors is quite small in comparison
to the total number of training samples. Instead of sequentially updating the
Lagrange multipliers, these methods update the Lagrange multipliers in parallel since they update many parameters in each iteration unlike other methods
that update one parameter at a time. In the chunking method, QP is used
to optimize an initial arbitrary subset of data. The support vectors found by
the optimizer from this subset are kept while other data points are discarded.
A new subset is then selected based on these support vectors and the additional
data. The process is then repeated until the margin is maximized. However,
the chunking method fails when the training data set is too large or most of
the training data points become support vectors. The decomposition method,
on the other hand, works on the fixed size working dataset rather than an arbitrary size as in the chunking method. A QP optimizer updates the Lagrange
multipliers on the fixed size working dataset only; the other Lagrange multipliers that are not in the working set are kept fixed. To summarize, the chunking
and decomposition methods use a QP or LP optimizer to solve the problem
by considering many small datasets rather than a single huge dataset. The Sequential Minimal Optimization (SMO) algorithm (Platt 1999) is a special case
of the decomposition method when the size of working dataset is fixed at two
such that an analytical solution is derived in very few numerical operations.
This discards the use of QP or LP optimizer. This method needs more number
of iterations but requires a small number of operations thus resulting in an
increase in optimization speed for very large data sets.
Mangasarian and Musicant (1998) introduced the Successive Over relaxation
method (SOR) for SVM, which combines SVM with SOR, and uses linear
programming to solve the optimization problem. This is done by introducing
an extra term in the objective function (5.14) and (5.32), which results in the
elimination of the equality constraint (5.24), (5.43) and (5.52). The optimization
problem requires the adjustment of only one point (one Lagrange multiplier)
at a time rather than two points during each iteration as in the SMO algorithm.