Computational Intelligence Techniques - Computational Intelligence in Biomedical Engineering - page 105

failed, then all possible combinations were tried. In both heuristics, the
search was started from some random point. The operation of the SMO
algorithm is summarized in the flowchart in Figure 3.18. The random-
ness introduced by the heuristics caused the original SMO algorithm
to have a much slower convergence rate (Keerthi and Gilbert, 2002).
Nevertheless, the SMO algorithm remains today as one of the more
important SVM training algorithms due to the simplicity and speed
of its implementation.

SVM light algorithm . At approximately the same time as SMO, another
SVM training algorithm was proposed by Joachims (1998) following
directly from Zoutendijk's (1960) method of feasible directions for solv-
ing quadratic programs. The update rule is not explicitly referred to
by Joachims but it is generally a steepest search direction method and
the novelty of the algorithm lies in Joachims' focus on the working
set selection method. Joachims' working set selection heuristic did not
have random selection elements and was frequently faster than SMO.
A combination of this working set selection and the SMO update rule
has been further implemented by Lin in his LibSVM software (Chang
and Lin, 2001).
The SVM light method first sorts the points that violate the KKT
conditions into an error list. Let z denote the number of violators at

c.

Success

Start

Y

Select first
violator and
find second
violator

SVM problem
with N
examples

Compute
KKT
violaters

Update pair
using SMO
update rule

#KKT>0?

N

Optimization
complete

Failed

Try any
random
nonbound
SV

Update pair
using SMO
update rule

Success

Failed

Try any
random
example

FIGURE 3.18
Flowchart for selecting working sets in the SMO algorithm. #KKT refers
to the number of Karush-Kuhn-Tucker violations, that is, points with non-
optimal gradients.