A Simple Decomposition Method for Support Vector Machines.
The decomposition method is currently one of the major methods for solving support vector machines. An important issue of this method is the selection of working sets. In this paper through the design of decomposition methods for bound-constrained SVM formulations we demonstrate that the working set selection is not a trivial task. Then from the experimental analysis we propose a simple selection of the working set which leads to faster convergences for difficult cases. Numerical experiments on different types of problems are conducted to demonstrate the viability of the proposed method.
Introduction
The support vector machine (SVM) is a new and promising technique for classication.
Surveys of SVM are, for example, Vapnik (1995, 1998) and Scholkopf et al. (1998). Given
training vectors x i in two classes, and a vector y 2 R l such that
1g, the support vector technique requires the solution of the following optimization
problem:
l
Training vectors x i are mapped into a higher (maybe innite) dimensional space by
the function . The existing common method to solve (1.1) is through its dual, a nite
quadratic programming problem:
where e is the vector of all ones, C is the upper bound of all variables, Q is an l by l positive
semidenite is the kernel.
The diculty of solving (1.2) is the density of Q because Q ij is in general not zero. In
this case, Q becomes a fully dense matrix so a prohibitive amount of memory is required to
store the matrix. Thus traditional optimization algorithms such as Newton, Quasi Newton,
etc., cannot be directly applied. Several authors (for example, Osuna et al. (1997), Joachims
(1998), Platt (1998), and Saunders et al. (1998)) have proposed decomposition methods
to conquer this diculty and reported good numerical results. Basically they separate the
of the training set to two sets B and N , where B is the working set and
If we denote B and N as vectors containing corresponding elements,
the objective value is equal to 1 T
N QNN N e T
N N .
At each iteration, N is xed and the following sub-problem with the variable B is solved:
where
QBB QBN
QNB QNN
is a permutation of the matrix Q and q is the size of B. The strict
decrease of the objective function holds and the theoretical convergence was studied in
Chang et al. (1999).
Usually a special storage using the idea of a cache is used to store recently used Q ij .
Hence the computational cost of later iterations can be reduced. However, the computational
time is still strongly related to the number of iterations. As the main thing which
aects the number of iterations is the selection of working sets, a careful choice of B can
dramatically reduce the number of iterations. This will be the main topic of this paper.
Instead of (1.1), in this paper, we decide to work on a dierent SVM formulation:
l
Its dual becomes a bound-constrained problem:
This formulation was proposed and studied by Mangasarian and Musicant (1999), and Friess
et al. (1998). We think it is easier to handle a problem without general linear constraints.
More importantly, when solving (1.2), a numerical diculty is on deciding whether a
variable is at the bound or not because it is generally not recommended to compare a
oating-point number with another one. For example, to calculate b of (1.2), we use the
following KKT condition
y
Therefore, we can calculate b by (1.6) where i is any element in B. However, when implementing
(1.6), we cannot directly compare  i to 0 or C. In SV M light by Joachims (1998), a
small  introduced. They consider  i to be free if  i   a and  i  C  a .
Otherwise, if a wrong  i is considered, the obtained b can be erroneous. On the other hand,
if the bounded formulation is used and appropriate solvers for sub-problem (2.9) are used,
it is possible to directly compare  i with 0 or C without needing an  a . For example, in Lin
and More (1999), they used a method called \project gradient" and in their implementation
all values at bounds are done by direct assignments. Hence it is safe to compare  i with 0
or C. To be more precise, for
oating-point computation, if  i C is assigned somewhere,
a future
oating-point comparison between C and C returns true as they both have the
same internal representation.
Later in this paper we will also show that bounded formulations provide more
exibility
on the selection of the working set. Of course we may worry that (1.5) produces a solution
which is not as good as that of (1.2). Indeed (1.5) is nding a separating hyperplane passing
through the origin with the maximal margin on data [(x i In Mangasarian
and Musicant (1999, Proposition 2.1), they showed that under some conditions, (1.2)
and (1.5) produce the same decision function. However, in Cristianini and Shawe-Taylor
(2000), they showed that this approach can increase the VC-dimension so the error rate for
classifying test data may not be as good as using (1.2). Up to now there is no numerical
experiments on this issue. In this paper we will conduct some comparisons. Results indicate
that practically (1.5) is an acceptable formulation.
In Section 2, through tests of dierent selections of the working set, we show that nding
a good strategy is not a trivial task. Based on our observations, we propose a simple
selection which leads to faster convergences in dicult cases. In Section 3, we implement
the proposed algorithm as the software BSVM and compare it with SV M light (Joachims,
1998) on problems with dierent size. After obtaining classiers from training data, we also
compare error rates for classifying test data by using (1.2) and (1.5). Finally in Section 4,
we present discussions and conclusions.
A preliminary version of the software BSVM is available at the authors' homepage. z
2 Selection of the Working Set
Among existing methods, Osuna et al. (1997), and Saunders et al. (1998) nd the working
set by choosing elements which violate the KKT condition. Platt (1998) has a special
heuristic but his algorithm is mainly on the case when 2. A systematic way is proposed
by Joachims (1998). In his software SV M light , the following problem is solved:
y
where we represent
is the solution at the kth iteration, rf( k )
is the gradient of f() at  k . Note that jfd i j d i 6= 0gj means the number of components
z BSVM is available at http://www.csie.ntu.edu.tw/~cjlin/bsvm
of d which are not zero. The constraint (2.2) implies that a descent direction involving
only q variables is obtained. Then components of  k with non-zero d i are included in
the working set B which is used to construct the sub-problem (2.9). Note that d is only
used for identifying B but not as a search direction. Joachims (1998) showed that the
computational time for solving (2.1) is mainly on nding the q=2 largest and q=2 smallest
elements of y Hence the cost is O(ql) which is aordable in his
implementation.
Therefore, following SV M light , for solving (1.5), a natural method to choose the working
set B is by a similar problem:
d  ; (2.4)
where
C otherwise.
Note that now f() becomes 1
This problem is essentially the same as
except that we strictly enforce 0  Note that in (2.1). if 0 <
it is possible that ( k is not in [0; C]. The use of  is like that you draw a small circle
and then nd the best linear approximation of f() in the intersection of a disk and the
feasible region. Since d is only used for deciding B, if instead any ; 0 <   1 is used
in (2.4), the same B is obtained. Of course we can consider another type of constraints
without restricting the size of d:
We do not consider this as a good method because in nal iterations, any consideration
should be in a small region.
Note that solving (2.3) is very easy by calculating the following vector:
contains indices of the smallest q elements of v. Interestingly, for the bound-
constrained formulation, solving (2.3) is the same as nding maximal violated elements of
the KKT condition. Note that elements which violate the KKT condition are
Hence, the q maximal violated elements are the smallest q elements of v. A similar relation
between the KKT condition of (1.2) and (2.2) is not very easy to see as the KKT condition
of (1.2) involves the number b which does not appear in (2.2). An interpretation is given by
considers possible intervals of b and select the most violated points
through end points of these intervals. These approaches are reasonable as intuitively we
think that nding the most violated elements is a natural choice.
However, unlike SV M light , this selection of the working set does not perform well. In
the rest of this paper we name our implementation BSVM. In Table 2.1, by solving the
problem heart from the Statlog collection (Michie, Spiegelhalter, & Taylor, 1994), we can
see that BSVM is much worse than SV M light .

Table

2.1: Problem heart: comparison in early iterations
light
iter. obj. #free #C y
light takes only 63 iterations but BSVM takes 590 iterations. In this experiment,
we use K(x methods use similar stopping
criteria and the initial solution is zero. The column \#C" presents the number of elements
of  k which are at the upper bound C. Columns y number of elements in B
in two dierent classes. Note that here for easy experiments, we use simple implementation
of SV M light and BSVM written in MATLAB.
We observe that in each of the early iterations, all components of the working set are
in the same class. The decrease of objective values of BSVM is much slower than that of
light . In addition, the number of variables at the upper bound after seven SV M light
iterations is many more than that of BSVM while BSVM produces iterations with more free
variables. We explain this observation as follows. First we make some assumptions for easy
description:
1.  and  + d are solutions of the current and next iterations, respectively.
2. B is the current working set, where all elements are from the same class with y
that is, y In other words, we assume that at one iteration, the situation where
all elements of the working are in the same class happens.
3.
We will show that it is more possible that components with y will be selected in the
next working set. Note that
We also know that
In early iterations, most elements are at zero. If for those nonzero elements, v i of (2.6) are
not too small, (2.3) is essentially nding the smallest elements of rf( d). For the next
iteration, since v will not be included the working set again. For
elements in N , we have
Therefore, if ((Q not small, in the next iteration, elements with y
to be selected because rf(+d) i becomes smaller. For the example in Table 2.1, we really
observe that the sign of most rf() i is changed in every early iteration. The explanation
is similar if y
We note that (2.7) and (2.8) hold because of the RBF kernel. For another popular
kernel: the polynomial kernel
all attributes of data are scaled to [
holds. Hence (2.7) and (2.8) remain valid.
Next we explain that when the above situation happens, in early iterations, very few
variables can reach the upper bound. Since we are solving the following sub-problem:
it is like that the following primal problem is solved:
If components in B are in the same class, (2.10) is a problem with separable data.
Hence that B are in general not equal to C. Thus the algorithm has
diculties to identify correct bounded variables. In addition, the decrease of the objective
function becomes slow. On the other hand, the constraint y T in (2.1) of SV M light
provides an excellent channel for selecting the working set from two dierent classes. To be
more precise, when most are zero, selecting some of the largest elements of y
is like selecting elements with y Conversely, the smallest elements
of y are from data with y This can be seen in the columns
of the number of y 2.1.
Another explanation is from the rst and second order approximations of the optimization
is the current solution which is considered as a xed vector and
d is the variable, problem (1.3) is equivalent to solving
Since
(1.3) is like to select the best q elements such that the linear part of (2.11) is minimized.
Similarly, (2.9) is equivalent to solving
Clearly a main dierence between (2.11) and (2.12) is that y B involves in a term d T (y B y T
(y T
d) 2 in the objective value of (2.12) but for (2.11), y B appears in one of its constraints:
Therefore, since we are now using a linear approximation for selecting the working
set, for (2.12), d T (y B y T
B )d is a quadratic term which is not considered in (2.3). Thus (2.3)
does not know that (y T
d) 2 should not be too large. On the other hand, for
remains as a constraint so it is like that (y T
d) 2 is implicitly minimized. In one word, (2.1)
and (2.3) both come from the linear approximation but one contains more information than
the other.
Based on this observation, we try to modify (2.3) by selecting a d which contains the
best q=2 elements with y and the best q=2 elements with y 1. The new result is
in

Table

2.2 where a substantial improvement is obtained. Now after seven iterations, both
algorithms reach solutions which have the same number of components at the upper bound.
Objective values are also similar.

Table

2.2: Problem heart: a new comparison in early iterations
light
iter. obj. #free #C iter. obj. #free #C
iteration
#free

Figure

2.1: # of free variables (line: BSVM, dashed: SV M light )
However, in Table 2.2, BSVM still takes more iterations than SV M light . We observe very
slow convergence in nal iterations. To improve the performance, we analyze the algorithm
in more detail. In Figure 2.1, we present the number of free variables in each iteration. It
can be clearly seen that BSVM goes through points which have more free variables. Since
the weakest part of decomposition method is that it cannot consider all variables together in
each iteration (only q are selected), a larger number of free variables causes more diculty.
In other words, if a component is correctly identied at C or 0, there is no problem of
numerical accuracy. However, it is in general not easy to decide the value of a free variable
are not considered together. Comparing to the working set selection
(2.1) of SV M light , our strategy of selecting q=2 elements with y
very natural. Therefore, in the middle of the iterative process more variables
are not correctly identied at the upper bound so the number of free variables becomes
larger. This leads us to conjecture that we should keep the number of free variables as
small as possible. A possible strategy to achieve this is by adding some free variables in the
previous iteration to the current working set.

Table

2.3: Working sets of nal iterations: BSVM
iter. B # in iter.+2

Table

2.4: Working set in nal iterations: SV M light
iter. B # in iter.+2
The second observation is on elements of the working set. When we use (2.3) to select
B, in nal iterations, components of the working set are shown in Table 2.3. In Table 2.4,
working sets of running SV M light are presented. From the last column of Table 2.3, it
can be seen that the working set of the kth iteration is very close to that of the
iteration. However, in Table 2.4, this situation is not that serious. For this example, at
nal solutions, there are using (1.5) and 25 by (1.2). For BSVM, in
the second half iterations, the number of free variables is less than 30. Note that in nal
iterations, the algorithm concentrates on deciding the value of free variables. Since in each
iteration we select 10 variables in the working set, after the sub-problem (2.9) is solved,
gradient at these 10 elements become zero. Hence the solution of (2.3) mainly comes from
the other free variables. This explains why working sets of the kth and iterations
are so similar. Apparently a selection like that in Table 2.3 is not an appropriate one.
We mentioned earlier that the weakest part of the decomposition method is that it cannot
consider all variables together. Now the situation is like two groups of variables are never
considered together so the convergence is extermely slow.
Based on these observations, we propose the following scheme for the selection of the
working set:
Let r be the number of free variables at  k
If r > 0, then
Select indices of the largest min(q=2; r) elements in v, where
Select the (q min(q=2; r)) smallest elements in v into B.
else
Select the q=2 smallest elements with y smallest elements with
Algorithm 2.1: Selection of the working set
That is, (q min(q=2; r)) elements are still from a problem like (2.3) but min(q=2; r)
elements are from free components with largest jrf( k in the
previous working set satisfy rf( k there are not too many such elements, most of
them are again included in the next working set. There are exceptional situations where all
are at bounds. When this happens, we choose q=2 best elements with y
best elements with y following the discussion for results in Table 2.2.
The motivation of this selection is described as follows: consider minimizing f() =2
T A e T , where A is a positive semidenite matrix and there are no constraints.
This problem is equivalent to solving If the decomposition method
is used, B k 1 is the working set at the (k 1)st iteration, and A is written as
we have AB k 1
Therefore, similar to what we did in (2.3), we can let B k , the
next working set, contain the smallest q elements of rf( k In other words,
elements violate KKT condition are selected. Thus B k will not include any elements in
only holds at the kth
iteration. When  is updated to  k+1 , the equality fails again. Hence this is like a zigzaging
process. From the point of view of solving a linear system, we think that considering some
inequalities and equalities together is a better method to avoid the zigzaging process. In
addition, our previous obervations suggest the reduction of the number of free variables.
Therefore, basically we select the q=2 most violated elements from the KKT condition and
the q=2 most satised elements at which  i is free.
Using Algorithm 2.1, BSVM takes about 50 iterations which is fewer than that of
light . Comparing to the 388 iterations presented in Table 2.2, the improvement is
dramatic. In Figure 2.2, the number of free variables in both methods are presented. It can
be clearly seen that in BSVM, the number of free variables is kept small. In early iterations,
each time q elements are considered and some of them move to the upper bound. For free
variables, Algorithm 2.1 tends to consider them again in subsequent iterations so BSVM has
more opportunities to push them to the upper bound. Since now the feasible region is like
a box, we can say that BSVM walks closer to walls of this box. We think that in general
this is a good property as the decomposition method faces more diculties on handeling
Algorithm 2.1 belongs to the class of working set selections discussed in Chang et al.
(1999). Therefore, BSVM theoretically converges to an optimal point of (1.5).
iteration
#free

Figure

2.2: # of free variables (line: BSVM, dashed: SV M light )
Computational Experiments
In this section, we describe the implementation of BSVM and present the comparison between
BSVM and SV M light (Version 3.2). Results show that BSVM converges faster than
light for dicult cases. The computational experiments for this section were done on
a Pentium III-500 using the gcc compiler.

Table

3.1: RBF kernel and
light (without shrinking)
Problem n SV(BSV) Mis. Obj. Iter. Time SV(BSV) Mis. Obj. Iter. Time
australian 690 245( 190)
diabetes 768 447( 434) 168 -413.57 130 0.48 447( 435) 168 -413.56 105 0.39
german 1000 599(
vehicle 846 439( 414) 210 -413.27 178 0.85 439( 414) 210 -413.02 332 0.94
letter 15000 569( 538) 104 -451.18 238 22.85 564( 531) 103 -446.98 349 24.38
shuttle 435006190(6185) 1117 -5289.17 2948 479.206164(6152) 1059 -5241.41 1120 449.27
dna 2000 696( 537) 50 -427.91 326 8.56 697( 533) 50 -427.38 253 6.14
segment
fourclass 862 411( 403) 168 -383.87 190 0.73 408( 401) 167 -383.58 124 0.41
web4 7366 856( 285) 123 -326.12 787 13.94 869( 281) 126 -326.07 876 19.82

Table

3.2: RBF kernel and

Table

3.3: Polynomial kernel and
light (without shrinking)
Problem n SV(BSV) Mis. Obj. Iter. Time SV(BSV) Mis. Obj. Iter. Time
australian 690 283( 242) 95 -227.98 117 0.36 284( 238) 95 -227.93 188 0.46
diabetes 768 539( 532) 231 -499.41 105 0.47 538( 532) 230 -499.24 99 0.37
german 1000 624( 527) 202 -516.42 244 1.36 625( 527) 203 -516.24 236 1.03
vehicle 846 440( 412) 212 -422.69 90 0.72 443( 403) 212 -422.18 217 0.69
letter 15000 1034(1020) 172 -783.91 199 31.65 1040(1015) 172 -783.05 223 28.17
shuttle 4350017699(17698) 7248 -15560.58 3706 1084.8617700(17694) 7248 -15560.17 3008 1118.19
dna 2000 1103( 772) 464 -906.09 222 12.39 1103( 772) 464 -905.58 216 7.66
segment
fourclass 862 485( 480) 195 -444.25 236 0.70 485( 479) 195 -443.76 125 0.41

Table

3.4: Polynomial kernel and

Table

3.5: RBF kernel: Using SV M light with shrinking
Problem n SV(BSV) Mis. Obj. Iter. Time SV(BSV) Mis. Obj. Iter. Time
australian 690 245( 190) 98 -201.64 504 0.75 223( 55) 28 -81199.77 119658 176.44
diabetes 768 447( 435) 168 -413.56 105 0.38 377( 273) 128 -302463.70 75141 115.26
german 1000 599( 512) 189 -502.77 311 1.17 509(
vehicle
letter 15000 564( 531) 103 -446.98 349 20.36 152( 52) 6 -55325.74 27290 135.39
shuttle 435006164(6152) 1059 -5241.41 1120 478.281488(1467) 137 -1188414.66 24699 1243.39
dna 2000 697( 533) 50 -427.38 253 6.15 408(
segment
fourclass 862 408( 401) 167 -383.58 124 0.41 89( 74) 2 -53885.74 11866 19.41
iteration
and
(a) SV M light
iteration
and
(b) BSVM

Figure

3.1: Problem fourclass: number of SV(line) and free SV(dashed)

Table

rate by 10-fold cross validation (Statlog) or classifying test
data (adult)
australian 85.36 86.23 85.65 85.51 85.94 84.06 82.17 80.29 77.97
diabetes 76.80 77.19 76.67 76.53 76.01 74.97 74.32 73.02 72.63
german 75.40 75.00 75.90 72.70 69.70 69.00 68.80 69.10 68.70
heart 81.85 80.74 80.37 78.89 77.41 75.56 75.18 74.07 74.07
segment 99.65 99.70 99.70 99.74 99.78 99.78 99.74 99.70 99.83
vehicle 74.95 78.97 79.56 81.67 82.39 85.35 85.23 86.17 85.34
adult1 84.23 83.96 83.03 80.54 80.22 79.59 79.43 79.43 79.43
adult4 84.40 84.19 83.83 81.84 81.00 79.73 79.42 79.28 79.27

Table

3.7: BSVM: Accuracy rate by 10-fold cross validation (Statlog) or classifying test
data (adult)
australian 85.36 86.23 85.65 85.51 85.94 84.06 82.17 80.15 77.97
diabetes 76.93 77.19 76.93 76.53 76.01 75.10 74.32 73.02 72.63
german
heart 82.22 80.74 79.63 78.52 77.41 75.93 75.18 74.07 74.07
segment 99.65 99.70 99.70 99.74 99.78 99.78 99.74 99.74 99.83
vehicle 74.95 78.97 79.56 81.79 82.50 85.23 85.23 86.29 85.34
adult4 84.40 84.19 83.83 81.84 81.00 79.74 79.42 79.28 79.27
light uses the following conditions as the termination criteria:
where  To have a fair comparison, we use similar criteria in BSVM:
Note that now there is no b in the above conditions. For both SV M light and BSVM, we set
We solve the sub-problem (2.9) using the software TRON by Lin and More (1999) x .
TRON is designed for large sparse bound-constrained problems. Here the sub-problem is a
very small fully dense problem so there are some redundant operations. We plan to write a
dense version of TRON in the near future.
As pointed out in existing work of decomposition methods, the most expensive step
in each iteration is the evaluation of the q columns of the matrix Q. In other words, we
maintain the vector Q so in each iteration, we have to calculate Q( k+1  k ) which
involves q columns of Q. To avoid the recomputation of these columns, existing methods
use the idea of a cache where recently used columns are stored. In BSVM, we now have a
very simple implement of the least-recently-used caching strategy. In the future, we plan to
optimize its performance using more advanced implementation techniques. For experiments
in this section, we use 160MB as the cache size for both BSVM and SV M light .
We test problems from dierent collections. Problems australian to segment are from the
Statlog collection (Michie et al., 1994). Problem fourclass is from Ho and Kleinberg (1996).
Problems adult1 and adult4 are compiled by Platt (1998) from the UCI \adult" data set
(Murphy & Aha, 1994). Problems web1 to web7 are also from Platt. Note that all problems
from Statlog (except dna) and fourclass are with real numbers so we scale them to [
Some of these problems have more than 2 classes so we treat all data not in the rst class as
in the second class. Problems dna, adult, and web problems are with binary representation
so we do not conduct any scaling.
We test problems by using RBF and polynomial kernels. For the RBF kernel, we
use problems and fourclass. We use K(x
for adult and web problems following the setting in Joachims (1998). For
the polynomial kernel, we have K(x
cases. For each kernel, we test
Usually is a good initial guess. As it is dicult to nd out
the optimal C, a procedure is to try dierent Cs and compare error rates obtained by cross
validation. In Saunders et al. (1998), they point out that plotting a graph of error rate on
dierent Cs will typically give a bowl shape, where the best value of C is somewhere in the
middle. Therefore, we think it may be necessary to solve problems with large Cs so we test
cases with In addition, the default C of SV M light is 1000.
Numerical results using are presented in Tables 3.1 to 3.4. The column \SV(BSV)"
represents the number of support vectors and bounded support vectors. The column \Mis."
is the number of misclassied training data while the \Obj." and \Iter." columns are objective
values and the number of iterations, respectively. Note that here we present the
objective value of the dual (that is, (1.2) and (1.5)). We also present the computational
time (in seconds) in the last column. SV M light implements a technique called \shrinking"
x TRON is available at http://www.mcs.anl.gov/~more/tron

Table

3.8: Iterations and q: BSVM,
australian 13592 3288 1395 682
diabetes 21190 3478 1201 461
german 16610 6530 3453 2126
vehicle 10594 1964 636 335

Table

3.9: Iterations and q: SV M light ,
australian 101103 71121 62120 34491
diabetes 75506 43160 37158 41241
german 43411 31143 28084 24529
heart 5772 3321 3068 1982
vehicle 177188 113357 107344 90370
which drops out some variables at the upper bound during the iterative process. Therefore,
it can work on a smaller problem in most iterations. Right now we have not implemented
similar techniques in BSVM so in Tables 3.1{3.4 we present results by SV M light without
using this shrinking technique. Except this option, we use all default options of SV M light .
Note that here we do not use the default optimizer of SV M light (version 3.2) for solving
(1.2). Following the suggestion by Joachims (2000), we link SV M light with LOQO (Van-
derbei, 1994) to achieve better stability. To give an idea of eects on using shrinking, in

Table

3.5 we present results of SV M light using this technique. It can be seen that shrinking
is a very useful technique for large problems. How to eectively incorporate shrinking in
BSVM is an issue for future investigation.
From

Tables

3.1 to 3.4, we can see that results obtained by BSVM, no matter number of
support vectors, number of misclassied data, and objective values, are very similar to those
by SV M light . This suggests that using BSVM, a formula with an additional term b 2 =2 in the
objective function, does not aect the training results much. Another interesting property
is that the objective value of BSVM is always smaller than that of SV M light . This is due
to the properties that y T in (1.2) and the feasible region of (1.2) is a subset of that
of (1.5). To further check the eectiveness of using (1.5), in Tables 3.6 and 3.7, we present
error rates of testing small Statlog problems by 10-fold cross validation. There are test
data available for adult problems so we also present error rates for classifying them. Results
suggest that for these problems, using (1.5) produces a classier which is as good as that
of using (1.2).
When light take about the same number of iterations. However,
it can be clearly seen that when methods take many more
iterations. For most problems we have tested, not only those presented here, we observe
slow convergence of decomposition methods when C is large. There are several possible
reasons which cause this diculty. We think that one of them is that when C is increased,
the number of free variables in the iterative process is increased. In addition, the number
of free variables at the nal solution is also increased. Though both the numbers of support
and bounded support vectors are decreased when C is increased, in many cases, bounded
variables when When C is increased, the
separating hyperplane tries to to t as many training data as possible. Hence more points
(i.e. more free to be at two planes w the decomposition
method has more diculties on handling free variables, if the problem is ill-conditioned,
more iterations are required. As our selection of the working set always try to push free
variables to be bounded variables, the number of free variables is kept small. Therefore,
the convergence seems faster. It can be clearly seen that for almost all cases in Tables 3.2
and 3.4, BSVM takes fewer iterations than SV M light .
Problem fourclass in Table 3.2 is the best example to show the characteristic of BSVM.
For this problem, at the nal solution, the number of free variables is small. In the iterative
process of BSVM, many free variables of iterates are in fact bounded variables at the nal
solution. BSVM considers free variables in subsequent iterations so all bounded variables are
quickly identied. The number of free variables is kept small so the slow local convergence
does not happen. However, SV M light goes through an iterative process with more free
variables so it takes a lot more iterations. We use Figure 3.1 to illustrate this observation in
more detail. It can be seen in Figure 3.1(a) that the number of free variables in SV M light is
increased to about 70 in the beginning. Then it is dicult do identify whether they should
be at the bounds or not. Especially in nal iterations, putting a free variable on a bound
can take thousands of iterations. On the other hand, the number of free variables of BSVM
is always small (less than 40).
We also note that sometimes many free variables in the iterative process are still free in
the nal solution. Hence BSVM may pay too much attention on them or wrongly put them
as bounded variables. Therefore, some iterations are wasted so the gap between BSVM and
light is smaller. An example of this is adult problems.
Next we study the relation between number of iterations and q, the size of the working
set. Using the RBF kernel and results are in Tables 3.8 and 3.9. We nd out that
by using BSVM, number of iterations is dramatically decreased as q becomes larger. On
the other hand, using SV M light , the number of iterations does not decrease much. Since
optimization solvers costs a certain amount of computational time in each iteration, this
result shows that SV M light is only suitable for using small q. On the other hand, Algorithm
2.1 provides the potential of using dierent q in dierent situations. We do not conduct
experiments on large problems here as our optimization solver is currently not very ecient
for dense sub-problems.
4 Discussions and Conclusions
From an optimization point of view, decomposition methods are like \coordinate search"
methods or \alternating variables method" (Fletcher, 1987, Chapter 2.2). They have slow
convergences as the rst and second order information is not used. In addition, if the
working set selection is not appropriate, though the strict decrease of the objective value
holds, the algorithm may not converge (see, for example, Powell (1973)). However, Even
with such disadvantages, the decomposition method has become one of the major methods
for SVM. We think the main reason is that the decomposition method is ecient for SVM
in the following situations:
1. C is small and most support vectors are at the upper bound. That is, there are not
in the iterative process.
2. The problem is well-conditioned even though there are many free variables.
For example, we do not think that adult problems with belong to the above cases.
They are dicult problems for decomposition methods.
If for most applications we only need solutions of problems which belong to the above
situations, current decomposition methods may be good enough. Especially a SMO type
(Platt, 1998) algorithm has the advantage of not requiring any optimization solver. How-
ever, if in many cases we need to solve dicult problems (for example, C is large), more
optimization knowledge and techniques should be considered. We hope that practical applications
will provide a better understanding on this issue.
Regarding the SVM formulation, we think (1.5) is simpler than (1.1) but with similar
quality for our test problems. In addition, in this paper we experiment with dierent
implementation of the working set selection. The cost is always the same: O(ql) by selecting
some of the largest and smallest rf( k ). This may not be the case for regular SVM
formulation (1.1) due to the linear constraint y T In SV M light , the implementation
is simple because (2.1) is very special. If we change constraints of (2.1) to 0
the solution procedure may be more complicated. Currently we add b 2 =2 into the objective
function. This is the same as nding a hyperplane passing through the origin for separating
data It was pointed out by Cristianini and Shawe-Taylor (2000) that
the number 1 added may not be the best choice. Experimenting with dierent numbers can
be a future issue for improving the performance of BSVM.
In Section 2, we demonstrate that nding a good working set is not an easy task.
Sometimes a natural method turns out to be a bad choice. It is also interesting to note that
for dierent formulations (1.2) and (1.5), similar selection strategies give totally dierent
performance. Therefore, for any new SVM formulations, we should be careful that existing
selections of the working set may not perform well.
Finally we summarize some possible advantages of BSVM:
1. It uses a simpler formula which is a bound-constrained optimization problem.
2. It keeps the number of free variables as low as possible. This in general leads to faster
convergences for dicult problems.
3. Algorithm 2.1 tends to consider free variables in the current iteration again in subsequent
iterations. Therefore, corresponding columns of these elements are naturally
cached.

Acknowledgments

This work was supported in part by the National Science Council of Taiwan via the grant
NSC 89-2213-E-002-013. The authors thank Chih-Chung Chang for many helpful discussions
and comments. Part of the software implementation beneted from his help. They
also thank Thorsten Joachims, Pavel Laskov, and John Platt for helpful comments.



--R

The analysis of decomposition methods for support vector machines.
An introduction to support vector machines.

Practical methods of optimization.
The kernel adatron algorithm: a fast and simple learning procedure for support vector machines.

Making large-scale svm learning practical



Machine learning
Fast training of support vector machines using sequential minimal optimization.
On search directions for minimization.

Support vector machine reference manual (Tech.

LOQO: An interior point code for quadratic programming (Tech.

Statisical learning theory.
--TR

--CTR
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
Daniela Giorgetti , Fabrizio Sebastiani, Multiclass text categorization for automated survey coding, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Chih-Chung Chang , Chih-Jen Lin, Training -Support Vector Classifiers: Theory and Algorithms, Neural Computation, v.13 n.9, p.2119-2147, September 2001
Nikolas List , Hans Ulrich Simon, General Polynomial Time Decomposition Algorithms, The Journal of Machine Learning Research, 8, p.303-321, 5/1/2007
Wei-Chun Kao , Kai-Min Chung , Chia-Liang Sun , Chih-Jen Lin, Decomposition methods for linear support vector machines, Neural Computation, v.16 n.8, p.1689-1704, August 2004
Rameswar Debnath , Masakazu Muramatsu , Haruhisa Takahashi, An Efficient Support Vector Machine Learning Method with Second-Order Cone Programming for Large-Scale Problems, Applied Intelligence, v.23 n.3, p.219-239, December  2005
Don Hush , Patrick Kelly , Clint Scovel , Ingo Steinwart, QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines, The Journal of Machine Learning Research, 7, p.733-769, 12/1/2006
Daniela Giorgetti , Fabrizio Sebastiani, Automating survey coding by multiclass text categorization techniques, Journal of the American Society for Information Science and Technology, v.54 n.14, p.1269-1277, December
Tzu-Chao Lin , Pao-Ta Yu, Adaptive Two-Pass Median Filter Based on Support Vector Machines for Image Restoration, Neural Computation, v.16 n.2, p.332-353, February 2004
Simon I. Hill , Arnaud Doucet, Adapting two-class support vector classification methods to many class problems, Proceedings of the 22nd international conference on Machine learning, p.313-320, August 07-11, 2005, Bonn, Germany
Tatjana Eitrich , Bruno Lang, Efficient optimization of support vector machine learning parameters for unbalanced datasets, Journal of Computational and Applied Mathematics, v.196 n.2, p.425-436, 15 November 2006
Ningning Guo , Libo Zeng , Qiongshui Wu, A method based on multispectral imaging technique for White Blood Cell segmentation, Computers in Biology and Medicine, v.37 n.1, p.70-76, January, 2007
Luca Zanni , Thomas Serafini , Gaetano Zanghirati, Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems, The Journal of Machine Learning Research, 7, p.1467-1492, 12/1/2006
Cheng-Lung Huang , Mu-Chen Chen , Chieh-Jen Wang, Credit scoring with a data mining approach based on support vector machines, Expert Systems with Applications: An International Journal, v.33 n.4, p.847-856, November, 2007
Tatjana Eitrich , Bruno Lang, On the optimal working set size in serial and parallel support vector machine learning with the decomposition algorithm, Proceedings of the fifth Australasian conference on Data mining and analystics, p.121-128, November 29-30, 2006, Sydney, Australia
support vector machines;decomposition methods;classification