Efficient SVM Regression Training with SMO.
The sequential minimal optimization algorithm (SMO) has been shown to be an effective method for training support vector machines (SVMs) on classification tasks defined on sparse data sets. SMO differs from most SVM algorithms in that it does not require a quadratic programming solver. In this work, we generalize SMO so that it can handle regression problems. However, one problem with SMO is that its rate of convergence slows down dramatically when data is non-sparse and when there are many support vectors in the solutionas is often the case in regressionbecause kernel function evaluations tend to dominate the runtime in this case. Moreover, caching kernel function outputs can easily degrade SMO's performance even more because SMO tends to access kernel function outputs in an unstructured manner. We address these problems with several modifications that enable caching to be effectively used with SMO. For regression problems, our modifications improve convergence time by over an order of magnitude.
Introduction
A support vector machine (SVM) is a type of model that is optimized so that prediction error
and model complexity are simultaneously minimized [13]. Despite having many admirable
qualities, research into the area of SVMs has been hindered by the fact that quadratic
programming (QP) solvers provided the only known training algorithm for years.
In 1997, a theorem [6] was proved that introduced a whole new family of SVM training
procedures. In a nutshell, Osuna's theorem showed that the global SVM training problem
can be broken down into a sequence of smaller subproblems and that optimizing each
subproblem minimizes the original QP problem. Even more recently, the sequential minimal
optimization algorithm (SMO) was introduced [7, 9] as an extreme example of Osuna's
theorem in practice. Because SMO uses a subproblem of size two, each subproblem has an
analytical solution. Thus, for the rst time, SVMs could be optimized without a QP solver.
In addition to SMO, other new methods [5, 2] have been proposed for optimizing SVMs
online without a QP solver. While these other online methods hold great promise, SMO is
the only online SVM optimizer that explicitly exploits the quadratic form of the objective
function and simultaneously uses the analytical solution of the size two case.
e
While SMO has been shown to be eective on sparse data sets and especially fast for
linear SVMs, the algorithm can be extremely slow on non-sparse data sets and on problems
that have many support vectors. Regression problems are especially prone to these issues
because the inputs are usually non-sparse real numbers (as opposed to binary inputs) with
solutions that have many support vectors. Because of these constraints, there have been no
reports of SMO being successfully used on regression problems.
In this work, we derive a generalization of SMO to handle regression problems and
address the runtime issues of SMO by modifying the heuristics and underlying algorithm so
that kernel outputs can be eectively cached. Conservative results indicate that for high-
dimensional, non-sparse data (and especially regression problems), the convergence rate of
SMO can be improved by an order of magnitude or more.
This paper is divided into six additional sections. Section 2 contains a basic overview of
SVMs and provides a minimal framework on which the later sections build. In Section 3,
we generalize SMO to handle regression problems. This simplest implementation of SMO
for regression can optimize SVMs on regression problems but with very poor convergence
rates. In Section 4, we introduce several modications to SMO that allow kernel function
outputs to be eciently cached. Section 5 contains numerical results that show that our
modications produce an order of magnitude improvement in convergence speed. Finally,
Section 6 summarizes our work and addresses future research in this area.
2 Introduction to SVMs
Consider a set of data points,
d is an input and
y i is a target output. An SVM is a model that is calculated as a weighted sum of kernel
function outputs. The kernel function can be an inner product, Gaussian basis function,
polynomial, or any other function that obeys Mercer's condition. Thus, the output of an
SVM is either a linear function of the inputs, or a linear function of the kernel outputs.
Because of the generality of SVMs, they can take forms that are identical to nonlinear
regression, radial basis function networks, and multilayer perceptrons. The dierence between
SVMs and these other methods lies in the objective functions that they are optimized
with respect to and the optimization procedures that one uses to minimize these objective
functions.
In the linear, noise-free case for classication, with y i 2 f1; 1g, the output of an SVM
is written as f(x; and the optimization task is dened as:
subject to y i
Intuitively, this objective function expresses the notion that one should nd the simplest
model that explains the data. This basic SVM framework has been generalized to include
slack variables for miss-classications, nonlinear kernel functions, regression, as well as other
extensions for other problem domains. It is beyond the scope of this paper to describe the
derivation of all of these extensions to the basic SVM framework. Instead, we refer the
reader to the excellent tutorials [1] and [11] for introductions to SVMs for classication and
regression, respectively. We delve into the derivation of the specic objective functions only
as far as necessary to set the framework from which we present our own work.
In general, one can easily construct objective functions similar to Equation 1 that include
slack variables for misclassication and nonlinear kernels. These objective functions can also
be modied for the special case of performing regression, i.e., with y i 2 R instead of y
1g. Such objective functions will always have a component that should be minimized
and linear constraints that must be obeyed. To optimize the objective function, one converts
it into the primal Lagrangian form which contains the minimization terms minus the linear
constraints multiplied by Lagrange multipliers. The primal Lagrangian is converted into a
dual Lagrangian where the only free parameters are the Lagrange multipliers. In the dual
form, the objective function is quadratic in the Lagrange multipliers; thus, the obvious way
to optimize the model is to express it as a quadratic programming problem with linear
constraints.
Our contribution in this paper uses a variant of Platt's sequential minimal optimization
method that is generalized for regression and is modied for further eciencies. SMO solves
the underlying QP problem by breaking it down into a sequence of smaller optimization
subproblems with two unknowns. With only two unknowns, the parameters have an analytical
solution, thus avoiding the use of a QP solver. Even though SMO does not use a
QP solver, it still makes reference to the dual Lagrangian objective functions. Thus, we
now dene the output function of nonlinear SVMs for classication and regression, as well
as the dual Lagrangian objective functions that they are optimized with respect to.
In the case of classication, with y i 2 f1; 1g, the output of an SVM is dened as:
where K(x a ; x b ) is the underlying kernel function. The dual objective function (which
should be minimized) is:
subject to the box constraint 0   i  C; 8 i and the linear constraint
0: C is
a user-dened constant that represents a balance between the model complexity and the
approximation error.
Regression for SVMs minimize functionals of the form:N
where jj  is an -insensitive error function dened as:
jxj  otherwise
and the output of the SVM now takes the form of:
e
Intuitively,
i and  i are \positive" and \negative" Lagrange multipliers (i.e., a single
weight) that obey 0
The dual form of Equation 4 is written as
where one should minimize the objective function with respect to   and , subject to the
constraints:
The parameter C is the same user-dened constant that represents a balance between the
model complexity and the approximation error.
In later sections, we will make extensive use of the two dual Lagrangians in Equations 3
and 6, and the SVM output functions in Equations 2 and 5.
3 SMO and Regression
As mentioned earlier, SMO is a new algorithm for training SVMs. SMO repeatedly nds
two Lagrange multipliers that can be optimized with respect to each other and analytically
computes the optimal step for the two Lagrange multipliers. When no two Lagrange multipliers
can be optimized, the original QP problem is solved. SMO actually consists of two
parts: (1) a set of heuristics for eciently choosing pairs of Lagrange multipliers to work
on, and (2) the analytical solution to a QP problem of size two. It is beyond the scope
of this paper to give a complete description of SMO's heuristics. More information can be
found in Platt's papers [7, 9].
Since SMO was originally designed (like SVMs) to only be applicable to classication
problems, the analytical solution to the size two QP problem must be generalized in order
for SMO to work on regression problems. The bulk of this section will be devoted to deriving
this solution.
3.1 Step Size Derivation
We begin by transforming Equations 5,6, and 7 by substituting
. Thus, the new unknowns will obey the box constraint C   i  C; 8 i . We will
also use the shorthand . The model output
and objective function can now be written as:
e
with the linear constraint
Our goal is to analytically express the minimum of
Equation 9 as a function of two parameters. Let these two parameters have indices a and
b so that  a and  b are the two unknowns. We can rewrite Equation 9 as
a k aa +2  2
a  b k ab +  a v
a
where L c is a term that is strictly constant with respect to  a and  b , and v
i is dened as
a k ai
with f
Note that a superscript  is used above to explicitly indicate that
values are computed with the old parameter values. This means that these portions of the
expression will not be a function of the new parameters (which simplies the derivation).
If we assume that the constraint,
true prior to any change to  a and  b ,
then in order for the constraint to be true after a step in parameter space, the sum of  a and
b must be held xed. With this in mind, let s
a
b . We can now rewrite
Equation 10 as a function of a single Lagrange multiplier by substituting s
a
To solve Equation 12, we need to compute its partial derivative with respect to  b ; however,
Equation 12 is not strictly dierentiable because of the absolute value function. Neverthe-
less, if we take djxj=dx = sgn(x), the resulting derivative is algebraically consistent:
@L d
a
setting Equation 13 to zero yields:
a v
a f
a k aa
a
a k aa
a
a f
From Equation 14, we can write a recursive update rule for  b in terms of its old value:
[y b y a
a f
While Equation 15 is recursive because of the two sgn()
functions, it still has a single solution that can be found quickly, as will be shown in the
next subsection.
a < 0 <  b

Figure

1: The derivative as a function of  b
If the kernel function obeys Mercer's condition, then
the derivative (Equation 13) will always be strictly increasing.
3.2 Finding Solutions

Figure

how the partial derivative (Equation 13) of the dual Lagrangian function
with respect to  b behaves. If the kernel function of the SVM obeys Mercer's condition (as
all common ones do), then we are guaranteed that will always be
true. If  is strictly positive, then Equation 13 will always be increasing. Moreover, if s  is
not zero, then it will be piecewise linear with two discrete jumps, as illustrated in Figure 1.
Putting these facts together means that we only have to consider ve possible solutions
for Equation 13. Three possible solutions correspond to using Equation 15 with (sgn( a )
set to -2, 0, and 2. The other two candidates correspond to setting  b to one of
the transitions in Figure 1:
We also need to consider how the linear and boxed constraints relate to one another.
In particular, we need lower and upper bounds for  b that insure that both  a and  b are
within the C range. Using:
with L and H being the lower and upper bounds, respectively, guarantees that both parameters
will obey the boxed constraints.
3.3 KKT Conditions
The step described in this section will only minimize the global objective function if one or
both of the two parameters violates a Karush-Kuhn-Tucker (KKT) condition. The KKT
conditions for regression are:
These KKT conditions also yield a test for convergence. When no parameter violates
any KKT condition, then the global minimum has been reached within machine precision.
3.4 Updating the Threshold
To update the SVM threshold, we calculate two candidate updates. The rst update, if
used along with the new parameters, forces the SVM to have f a = y a . The second forces
neither update for the other two parameters hits a constraint, then the two
candidate updates for the threshold will be identical. Otherwise, we average the candidate
updates.
a
a y a new
a  old
a new
b  old
new
a  old
a new
b  old
These update rules are nearly identical to Platt's original derivation.
Complete Update Rule
SMO can work on regression problems if the following steps are performed.
Pick two parameters,  a and  b , such that at least one parameter violates a KKT
condition as dened in Equation 18.
Compute
{ Try Equation 15 with (sgn( a ) sgn( b )) equal to -2, 0, and 2. If the new value
is a zero to Equation 13, then accept that as the new value.
{ If the above step failed, try  b equal to 0 or s  . Accept the value that has the
property such that all positive (negative) perturbations yield a positive (negative)
value for Equation 13.
If  raw
new
b < L, set  new
L. Otherwise, set  new
Set  new
a
b  new
b .
Set  new
specied in Equations 19 and 20.
The outer loop of SMO|that is, all of the non-numerical parts that make up the heuristics|
can remain the same. As will be discussed in Section 5, further modications can be made
to SMO that improve the rate of convergence on regression problems by as much as an
order of magnitude.
e
While further progress can be made:
1. If this is the rst iteration, or if the previous iteration made no progress, then
let the working set be all data points.
2. Otherwise, let the working set consist only of data points with non-bounded
Lagrange multipliers.
3. For all data points in the working set, try to optimize the corresponding Lagrange
multiplier. To nd the second Lagrange multiplier:
3.1. Try the best one (found from looping over the non-bounded multipliers)
according to Platt's heuristic, or
3.2. Try all among the working set, or
3.3. Try to nd one among the entire set of Lagrange multipliers.
4. If no progress was made and working set was all data points, then done.

Figure

2: Basic Pseudo-code for SMO
4 Building a Better SMO
As described in Section 2, SMO repeatedly nds two Lagrange multipliers that can be
optimized with respect to each other and analytically computes the optimal step for the two
Lagrange multipliers. Section 2 was concerned with the analytical portion of the algorithm.
In this section, we concentrate on the remainder of SMO which consists of several heuristics
that are used to pick pairs of Lagrange multipliers to optimize. While it is beyond the scope
of this paper to give a complete description of SMO, Figure 2 gives basic pseudo-code for
the algorithm. For more information, consult one of Platt's papers [7, 9].
Referring to Figure 2, notice that the rst Lagrange multiplier to work on is chosen at
line 3; and its counterpart is chosen at line 3.1, 3.2, or 3.3. SMO attempts to concentrate
its eort where it is most needed by maintaining a working set of non-bounded Lagrange
multipliers. The idea is that Lagrange multipliers that are at bounds (either 0 or C for
classication, or 0 or C for regression) are mostly irrelevant to the optimization problem
and will tend to keep their bounded values.
At best, each optimization step will take time proportional to the number of Lagrange
multipliers in the working set and, at worst, will take time proportional to the entire data
set. However, the runtime is actually much slower than this analysis implies because each
candidate for the second Lagrange multiplier requires three kernel functions to be evaluated.
If the input dimensionality is large, then the kernel evaluations may be a signicant factor
in the time complexity. All told, we can express the runtime of a single SMO step as
O (p  W  d is the probability that the second Lagrange multiplier
is in the working set, W is the size of the working set, and d is the input dimensionality.
The goal of this section is to reduce the runtime complexity for a single SMO step down
e
to O (p 0  W Additionally, a method for reducing the total
number of required SMO steps is also introduced, so we also reduce the cost of the outer
most loop of SMO as well. Over the next ve subsections, several improvements to SMO
will be described. The most fundamental change is to cache the kernel function outputs.
However, a naive caching policy actually slows down SMO since the original algorithm tends
to randomly access kernel outputs with high frequency. Other changes are designed either
to improve the probability that a cached kernel output can be used again or to exploit the
fact that kernel outputs have been precomputed.
4.1 Caching Kernel Outputs
A cache is typically understood to be a small portion of memory that is faster than normal
memory. In this work, we use cache to refer to a table of precomputed kernel outputs. The
idea here is that frequently accessed kernel outputs should be stored and reused to avoid
the cost of recomputation.
Our cache data structure contains an inverse index, I, with M entries such that I i refers
to the index (in the main data set) of the ith cached item. We maintain a two-dimensional
MM array to store the cached values. Thus, for any 1 <
we either have the precomputed value of k ab stored in the cache or we have space allocated
for that value and a
ag set to indicate that the kernel output needs to be computed and
saved.
The cache can have any of the following operations applied to it:
returns one of three values to indicate that k ab is either (1) not in
the cache, (2) allocated for the cache but not present, or (3) in the cache.
ab and force it into the cache, if it is not present already.
The least recently used indices in I are replaced by a and b.
return k ab by the fastest method available.
mark indices a and b as the most recently used elements.
We use a least recently used policy for updating the cache as would be expected but
with the following exceptions:
For all i, k ii is maintained in its own separate space since it is accessed so frequently.
If SMO's working set is all Lagrange multipliers (as determined in step 1 of Figure 2),
then all accesses to the cache are done without tickles and without inserts.
If the working set is a proper subset and both requested indices are not in part of the
working set, then the access is done with neither a tickle nor an insert.
Without the above modication, caching kernel outputs in SMO usually degrades the
runtime because of the frequency of cache misses and the extra overhead incurred. Our
modied caching policy makes caching benecial; however, the next set of heuristic can
improve the eectiveness of caching even more.
4.2 Eliminating Thrashing
As shown in lines 3.1, 3.2, and 3.3 of Figure 2, SMO uses a hierarchy of selection methods
in order to nd a second multiplier to optimize along with the rst. It rst tries to nd a
very good one with a heuristic. If that fails, it settles for anything in the working set. But
if that fails, SMO then starts searching through the entire training set.
Line 3.3 causes problems in SMO for two reasons. First, it entails an extreme amount
of work that results in only two multipliers changing. Second, if caching is used, line 3.3
could interfere with the update policies of the cache.
To avoid these problems, we use a heuristic which entails a modication to SMO such
that line 3.3 is executed only if the working set is the entire data set. We must execute it,
in this case, to be sure that convergence is achieved. Platt [8] has proposed a modication
with a similar goal in mind.
In our example source code (which can be accessed via the URL given at the end of this
paper) this heuristic corresponds to using the command-line option -lazy, which is short
for \lazy loops".
4.3 Optimal Steps
The next modication to SMO takes advantage of the fact that cached kernel outputs can
be accessed in constant time. Line 3.1 of Figure 2 searches over the entire working set
and nds the multiplier that approximately yields the largest step size. However, if kernel
outputs for two multipliers are cached, then computing the change to the objective function
that results from optimizing the two multipliers takes constant time to calculate. Thus, by
exploiting the cached kernel outputs, we can greedily take the step that yields the most
improvement.
Let  b be the rst multiplier selected in line 3 of Figure 2. For all a such that k ab is
cached, we can calculate new values for the two multipliers analytically and in constant
time. Let the old values for multipliers use  superscripts, as in
a and
b . Moreover, let
i be shorthand for the new and old values for the SVM output. 1
The change to the classication objective function (Equation 3) that results from accepting
the new multipliers is:
y a  a k aa  0 )
a y a (f
y a
a k aa
ab (y a y b  a  b y a y b
a
a
Equation 21 is derived by substituting  for  in Equation 3, and rewriting the equation
so that all terms are trivially dependent or independent on  a and/or  b . Afterwards,
the dierence between two choices for the two multipliers can be calculated without any
summations because the independent terms cancel.
1 Note that in this section, we refer to all Lagrange multipliers by  and not . We do this to maintain
consistency with earlier sections, even though this notation con
icts with Equations 3 and 6.
e
The change to the regression objective function (Equation can be similarly calculated
a (f
a y a2
a k aa
b y b2
k ab (
a
b  a  b
Thus, we modify SMO by replacing line 3.1 in Figure 2 with code that looks for the best
second multiplier via Equation 21 or 22 for all a such that k ab is cached.
In our example source code, this heuristic corresponds to using the command-line option
-best, which is short for \best step".
4.4 On Demand Incremental SVM Outputs
The next modication to SMO is a method to calculate SVM outputs more rapidly. Without
loss of generality, assume we have an SVM that is used for classication and that the output
of the SVM is determined from Equation 2 (but with  substituted for ). There are at
least three dierent ways to calculate the SVM outputs after a single Lagrange multiplier,
Use Equation 2, which is extremely slow.
Change Equation 2 so that the summation is only over the nonzero Lagrange multipliers

Incrementally update the new value with f
Clearly, the last method is the fastest. SMO, in its original form, uses the third method to
update the outputs whose multipliers are non-bounded (which are needed often) and the
second method when an output is needed that has not been incrementally updated.
We can improve on this method by only updating outputs when they are needed, and
by computing which of the second or third method above is more ecient. To do this, we
need two queues with maximum sizes equal to the number of Lagrange multipliers and a
third array to store a time stamp for when a particular output was last updated. Whenever
a Lagrange multiplier changes value, we store the change to the multiplier and the change
to  0 in the queues, overwriting the oldest value.
When a particular output is required, if the number of time steps that have elapsed
since the output was last updated is less than the number of nonzero Lagrange multipliers,
we can calculate the output from its last known value and from the changed values in the
queues. However, if there are fewer nonzero Lagrange multipliers, it is more ecient to
update the output using the second method.
Since the outputs are updated on demand, if the SVM outputs are accessed in a nonuniform
manner, then this update method will exploit those statistical irregularities. In our
example source code, this heuristic corresponds to using the command-line option -clever,
which is short for \clever outputs".
4.5 SMO with Decomposition
Using SMO with caching along with all of the proposed heuristics yields a signicant runtime
improvement as long as the cache size is at nearly as large as the number of support vectors
in the solution. When the cache size is too small to t all of the kernel outputs for each
support vector pair, accesses to the cache will fail and runtime will be increased. This
particular problem can be addressed by combining Osuna's decomposition algorithm [6]
with SMO.
The basic idea is to iteratively build an M M subproblem with 2 < M < N , solve the
subproblem, and then iterate with a new subproblem until the entire optimization problem
is solved. However, instead of using a QP solver to solve the subproblem, we use SMO and
choose M to be as large as the cache.
The benets of this combination are two-fold. First, much evidence indicates that
decomposition can often be faster than using a QP solver. Since the combination of SMO
and decomposition is functionally identical to standard decomposition with SMO as the QP
solver, we should expect the same benet. Second, using a subproblem that is the same
size as the cache guarantees that all of the kernel outputs required will be available at every
SMO iteration except for the rst for each subproblem.
However, we note that our implementation of decomposition is very naive in the way
it constructs subproblems, since it essentially works on the rst M randomly selected data
points that violate a KKT condition. In our example source code, this heuristic corresponds
to using the command-line option -ssz M , which is short for \subset size".
5 Experimental Results
To evaluate the eectiveness of our modications to SMO we chose the Mackey-Glass system
[4] as a test case because it is highly chaotic (making it a challenging regression problem)
and well-studied. The Mackey-Glass system is described by the delay-dierential equation:
dx
dt
For all experiments, we used the parameter settings
1 (for numerical integration), which yields a very chaotic time series with an embedding
dimension of 4.
To perform forecasting, we use a time-delay embedding [12] to approximate the map:
with equal to 4, 6, or 8. Thus, we are predicting 85 time steps into
the future with an SVM with 4, 6, or 8 inputs.
The purpose of this work is not to evaluate the prediction accuracy of SVMs on chaotic
time series as has been done in [5]. Our focus is on the amount of time required to optimize
a support vector machine. Since the objective function for optimizing SVMs is quadratic
with linear constraints, all SVMs will have either a single global minimum or a collection
of minima that are identical in the objective function valuation. Hence, excepting minor
numerical dierences between implementations, all SVM optimization routines essentially
0.60.811.21.4
(a)
true
predicted0.50.70.91.11.30 50 100 150 200 250 300 350 400
true
predicted0.611.4
(c)
true
support vector0.611.4
true
support vector

Figure

3: The Mackey-Glass system: actual and predicted time series for (a)
two-dimensional phase space plots to show the location of support vectors for (c)
and (d)
nd the same solution; they only dier in how they nd the solution, how long it takes to
get there, and how much memory is required.

Figure

3 shows four plots from two training runs that illustrate the Mackey-Glass time
series and phase-space. The time series plots show predictions for the two values of , and
the phase-space plots show the location of the support vectors in a two dimensional slice of
the time-delay embedding.
The rst part of our experimental results are summarized in Tables 1 and 2. In these
experiments, the time series consisted of 500 data points which, depending on the values of
d, , and T , yield a number of exemplars less than 500. The major blocks (three in each
table) summarize a specic problem instance which has a unique set of values for  and d.
Within each block, we performed all combinations of using SMO with and without caching,
with and without decomposition, and with and without all three heuristics.
Each block in the tables also contains results from using the Royal Holloway / AT&T
/ GMD FIRST SV Machine code (RAGSVM) [10]. RAGSVM can work with three dier-
ent optimization packages, but only one optimizer is freely available for research that can
be used on regression problems: BOTTOU, an implementation of the conjugate gradient
method. Entries in the blocks labelled as \QP" use RAGSVM with BOTTOU without the
chunking option. Entries labelled as \QP/Chunk" use \sporty chunking" which uses the
decomposition method with the specied subset size and the QP solver on the subproblem.
In general, the training runs were congured as similarly as possible, each using Gaussian
kernels of the form: K(x a
all congurations produces results nearly identical to RAGSVM with respect to the value
of the objective function found. However, the run times are dramatically dierent for the
two implementations. For these sets of experiments, SMO with caching and the heuristics
consistently gave the fastest run times, often performing orders of magnitude faster than
regular SMO, QP, and decomposition. The speed improvements for SMO ranged from a
factor of 3 to as much as 25.
Interestingly, on these experiments, SMO with decomposition consistently yielded inferior
run times compared to SMO without decomposition, regardless of other runtime
options. Our motivation for combining SMO with decomposition was to make caching effective
on problems with many data points. Since the rst set of experiments only used
500 data points, we used the same Mackey-Glass parameters to generate a time series with
10,000 data points for further experimentation.

Table

3 summarizes the second set of experiments. For these experiments, we chose
to only vary whether SMO was used with or without decomposition. As can be seen in
the table, SMO without decomposition gives nearly an order of magnitude improvement in
runtime compare to RAGSVM while SMO with decomposition yields even faster run times.
However, SMO with decomposition yields a very high standard deviation with the fastest
and slowest run times being 391 and 1123 seconds, respectively. We suspect that the high
standard deviation is a result of our naive implementation of decomposition. Nevertheless,
the worst case for SMO with decomposition is nearly as good as the best for SMO without
decomposition. Moreover, on this problem set, SMO with decomposition can be nearly 25
times faster than decomposition with a QP solver. In fact, the solutions found by SMO
in all experiments from Table 3 are superior to the RAGSVM solutions in that the nal
objective function values are signicantly larger in magnitude in the SMO runs.
e
training subset cache options objective number CPU std.
method size size (for SMO) value of SVs time dev.
problem instance:
SMO 100 100 none 15:9198 70:5 42:72 7:53
SMO 100 100 all 15:9247 67:9 7:64 1:04
QP | | | 15:9002 63 85:22 |
QP/Chunk 100 | | 15:8809 59 20:24 |
problem instance:
SMO 100 100 none 5:4620 63:2 35:70 6:25
SMO 100 100 all 5:4636 62:7 6:06 0:93
QP | | | 5:4698 59 62:86 |
QP/Chunk 100 | | 5:4619
problem instance:
SMO 100 100 none 2:3005 55:4 13:65 3:80
SMO 100 100 all 2:3031 53 3:45 0:59
QP | | | 2:2950 51 40:86 |
QP/Chunk 100 | | 2:2899 38 6:30 |

Table

1: Experimental results (part 1/2): all SMO results are averaged over ten trials. Entries
where heuristics have the value of \all" indicate that \lazy loops" (from Section 4.2), \best step"
(Section 4.3), and \clever outputs" (Section 4.4) are all used. The entries for the subset size indicate
the size for decomposition (with \0" meaning no decomposition). All times are in CPU seconds on
a 500 MHz Pentium III machine running Linux.
Ecient SVM Training Flake & Lawrence
training subset cache options objective number CPU std.
method size size (for SMO) value of SVs time dev.
problem instance:
SMO 100 100 none 84:0284 196:8 184:12 22:32
SMO 100 100 all 83:8655 195:3 40:60 5:69
QP | | | 84:0401 194 186:63 |
QP/Chunk 100 | | 84:0290 188 316:54 |
problem instance:
SMO 100 100 none 48:1120 170:5 278:76 31:27
SMO 100 100 all 48:1283 169 75:09 14:38
QP | | | 48:1430 159 245:67 |
QP/Chunk 100 | | 48:1505 164 310:21 |
problem instance:
SMO 100 100 none 27:8421 164:9 289:26 29:13
SMO 100 100 all 27:8663 159:8 76:66 12:69
QP | | | 27:8958 149 257:40 |
QP/Chunk 100 | | 27:8941 144 329:91 |

Table

2: Experimental results (part 2/2): all SMO results are averaged over ten trials. Entries
where heuristics have the value of \all" indicate that \lazy loops" (from Section 4.2), \best step"
(Section 4.3), and \clever outputs" (Section 4.4) are all used. The entries for the subset size indicate
the size for decomposition (with \0" meaning no decomposition). All times are in CPU seconds on
a 500 MHz Pentium III machine running Linux.
e
training subset cache options objective number CPU std.
method size size (for SMO) value of SVs time dev.
SMO 500 500 all 93:8975 393:25 625:45 295:85
QP/Chunk 500 | | 87:2486 287 9314:89 |

Table

3: Experimental results for problem instance data points in
the time series. SMO statistics are over four trials. All times are in CPU seconds on a 500 MHz
Pentium III machine running Linux.
But why does SMO with decomposition help on large data sets? For a caching policy
to be eective, the cached elements must have a relatively high probability of being reused
before they are replaced. On large data sets, this goal is far more dicult to achieve.
Moreover, SMO must periodically loop over all exemplars in order to check for convergence.
Using SMO with decomposition makes caching much easier to implement eectively because
we can make the subset size for decomposition the same size as the cache, thus guaranteeing
that cached elements can be reused with high probability.
6 Conclusions
This work has shown that SMO can be generalized to handle regression and that the run-time
of SMO can be greatly improved for datasets dense with support vectors. Our main
improvement to SMO has been to implement caching along with heuristics that assist the
caching policy. In general, the heuristics are designed to either improve the probability
that cached kernel outputs will be used or exploit the fact that cached kernel outputs can
be used in ways that are infeasible for non-cached kernel outputs. Our numerical results
show that our modications to SMO yield dramatic runtime improvements. Moreover, our
implementation of SMO can outperform state-of-the-art SVM optimization packages that
use a conjugate gradient QP solver and decomposition.
Because kernel evaluations are more expensive the higher the input dimensionality, we
believe, but have not shown, that our modications to SMO will be even more valuable
on larger datasets with high input dimensionality. Preliminary results indicate that these
changes can greatly improve the performance of SMO on classication tasks that involve
large, high-dimensional, and non-sparse data sets.
Future work will concentrate on incremental methods that gradually increase numerical
accuracy. We also believe that the improvement to SMO described in [3] can be adapted
to regression problems as well. Moreover, altering our decomposition scheme should yield
further improvements.

Acknowledgements

We thank Tommy Poggio, John Platt, Edgar Osuna, Constantine Papageorgious, and Sayan
Mukherjee for helpful discussions. Special thanks to Tommy Poggio and the Center for
Biological and Computational Learning at MIT for hosting the rst author during this
research.
e
A Source Code Availability
The source code used in this work is part of NODElib, the Neural Optimization and Development
library. NODElib is freely available under a \copyleft" licensing agreement, and can
be downloaded from http://www.neci.nj.nec.com/homepages/flake/nodelib.tgz.



--R

A tutorial on support vector machines for pattern recognition.
The Kernel-Adatron: a fast and simple learning procedure for support vector machines
Improvements to Platt's SMO algorithm for SVM classi
Oscillation and chaos in physiological control systems.
Nonlinear prediction of chaotic time series using support vector machines.
An improved training algorithm for support vector machines.
Fast training of support vector machines using sequential minimal optimiza- tion
Private communication
Using sparseness and analytic QP to speed training of support vector ma- chines


Detecting strange attractors in turbulence.
The Nature of Statistical Learning Theory.
--TR

--CTR
Gary W. Flake , Eric J. Glover , Steve Lawrence , C. Lee Giles, Extracting query modifications from nonlinear SVMs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
Adriano L. I. Oliveira, Letters: Estimation of software project effort with support vector regression, Neurocomputing, v.69 n.13-15, p.1749-1753, August, 2006
Shuo-Peng Liao , Hsuan-Tien Lin , Chih-Jen Lin, A note on the decomposition methods for support vector regression, Neural Computation, v.14 n.6, p.1267-1281, June 2002
Chih-Chung Chang , Chih-Jen Lin, Training v-support vector regression: theory and algorithms, Neural Computation, v.14 n.8, p.1959-1977, August 2002
Vivek Sehgal , Lise Getoor , Peter D Viechnicki, Entity resolution in geospatial data integration, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
Quan Yong , Yang Jie , Yao Lixiu , Ye Chenzhou, An improved way tomake large-scale SVR learning practical, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.1135-1141, 1 January 2004
Jian-xiong Dong , Adam Krzyzak , Ching Y. Suen, Fast SVM Training Algorithm with Decomposition on Very Large Data Sets, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.4, p.603-618, April 2005
support vector machines;optimization;regression;caching;quadratic programming;sequential minimal optimization