Feasible Direction Decomposition Algorithms for Training Support Vector Machines.
The article presents a general view of a class of decomposition algorithms for training Support Vector Machines (SVM) which are motivated by the method of feasible directions. The first such algorithm for the pattern recognition SVM has been proposed in Joachims, T. (1999, Schlkopf et al. (Eds.) Advances in kernel methods-Support vector learning (pp. 185208). MIT Press). Its extension to the regression SVMthe maximal inconsistency algorithmhas been recently presented by the author (Laskov, 2000, Solla, Leen, & Mller (Eds.) Advances in neural information processing systems 12 (pp. 484490). MIT Press). A detailed account of both algorithms is carried out, complemented by theoretical investigation of the relationship between the two algorithms. It is proved that the two algorithms are equivalent for the pattern recognition SVM, and the feasible direction interpretation of the maximal inconsistency algorithm is given for the regression SVM. The experimental results demonstrate an order of magnitude decrease of training time in comparison with training without decomposition, and, most importantly, provide experimental evidence of the linear convergence rate of the feasible direction decomposition algorithms.
Introduction
Computational complexity of SVM training algorithms is attracting increasing
interest, as applications of SVM extend to problems of larger and larger size.
Requests have been recently made for algorithms capable of handling problems
containing examples [14]. The basic training algorithm [16] involves
a solution to a quadratic programming problem the size of which depends on
the size of the training data set. For the training data set of size l, the pattern
recognition SVM quadratic program has l variables with non-negativity
constraints, l inequality constraints and one equality constraint. The regression
quadratic program has 2l variables with non-negativity constraints, 2l
inequality constraints and one equality constraint. In addition, the basic formulation
of the SVM training algorithm requires storage of the kernel matrix of
size l \Theta l or 2l \Theta 2l respectively. Thus, the running time and storage of the kernel
matrix are the two main optimization-related bottlenecks of SVM training
algorithms 1 .
Another possible bottleneck is computation of the kernel matrix. If real dimension of
data points is large, this time may become comparable with training time. However
First SVM implementations used general purpose optimization packages (such
as MINOS, LOQO and others) that were not designed for problems of such
size. It was soon discovered that these packages were not suitable for solutions
to problems involving more than a few hundred examples. The early special-purpose
methods, proposed to speed-up training, have not brought much relief.
Chunking [15] prescribes iteration through the training data, accumulating support
vectors and adding a "chunk" of new data until no more changes to the
solution occur. The main problem with this method is that when the percentage
of support vectors is high it essentially solves the problem of almost the
full size more than once. Another method proposed by Kaufmann [4] modifies
traditional optimization algorithms (a combination of Newton's and conjugate
gradient methods) to yield the overall complexity of O(s 3 ) per iteration, where
s is the (a priori unknown) number of support vectors. This can be a significant
improvement over O(l 3 ), however the number of support vectors in not
guaranteed to be small.
Decomposition was the first practical method for solving large-scale SVM
training problems. It was originally proposed for the pattern recognition SVM
[9] and subsequently extended to the regression SVM in [8]. The key idea of
decomposition is to freeze all but a small number of optimization variables, and
to solve a sequence of constant-size problems. The set of variables optimized
at a current iterations is denoted as the working set. Because the working set
is re-optimized, the value of the objective function is improved at each itera-
tion, provided the working set is not optimal before re-optimization. Iteration
is stopped when termination criteria, derived from Karush-Kuhn-Tucker (KKT)
conditions, are satisfied to a required precision.
Selection of the working set is the most important issue in the decomposition
algorithms. First, the provision that the working set must be sub-optimal before
re-optimizaiton, is crucial to prevent the algorithm from cycling. Therefore, it
is important to have criteria to test sub-optimality of any given working set.
Second, working set selection affects the rate of convergence of the algorithm:
if sub-optimal working sets are selected more or less at random the algorithm
converges very slowly. Finally, working set selection is imporant in theoretical
analysis of decomposition algorithms; in particular, in the recent convergence
proof by Chang et. al. [2].
The original decomposition algorithm essentially addressed only the first
issue-the design of its termination criteria in all but pathological cases prevents
composition of already optimal working sets. Its implementation featured
some unpublished heuristics which provided reasonable convergence speed. Ob-
viously, a formal framework for working set selection was highly desirable. One
such framework is the method of feasible directions, proposed in the optimization
theory in 1960 by Zoutendijk [18]. The connection between this method and
the working set selection problem was first discovered by Joachims in a paper
it will be assume in the rest of this article that kernel computation is not the main
factor contributing to the complexity of training.
that has drawn wide attention [3]. However, Joachims' algorithm is limited to
the pattern recognition case because it uses the fact that the labels are \Sigma1.
The main goal of the current article is to provide a unified treatment of
the working set selection problem within the framework of the method of feasible
directions. Specifically, the first two issues raised above are addressed, in a
common way for the pattern recognition and the regression SVM:
- a criterion is proposed to identify sub-optimal working sets
- a heuristic, which shares the motivation with the optimality criterion, is
proposed for (approximately) optimal working set selection.
The new algorithm, termed the "maximal inconsistency algorithm", is applicable
for both pattern recognition and the regression SVM. To further reveal
the machinery of the new algorithm, it is shown that for the pattern recognition
SVM the new algorithm is equivalent to Joachims' algorithm, and for the
regression SVM a similar algorithm exists based on the feasible direction princi-
ple. Similar to the pattern recognition case, the maximal inconsistency algorithm
satisfies theoretical requirements crucial for the proof of convergence. These relationships
allow to classify both algorithms as "feasible direction decomposition"
algorithms.
The article is organized as follows. Section 2 provides basic formulations of
decomposition algorithms for the pattern recognition and the regression SVM.
Section 3 presents the method of feasible directions. Sections 4 and 5 cover
the issues related to feasible direction decomposition algorithms for the pattern
recognition and the regression SVM respectively. Exposition in these sections is
carried out in different fashion. Section 4 is presented in a more or less chronological
order. It starts with Joachims' algorithm, fully motivated by the feasible
direction method. Then the criterion for testing optimality of a working set is
presented, and the maximal inconsistency working set selection rule is derived
from this criterion. Finally, equivalence between the maximal inconsistency algorithm
and Joachims' algorithm is proven. The order of presentation is reversed
for the regression SVM in Section 5. The maximal inconsistency algorithm is
introduced first, followed by its interpretation as a feasible direction decomposition
algorithm. Experimental results for the regression SVM are presented in
Section 6.
The classical problem of training the SVM, given the data f(x
and hence, the kernel matrix can be expressed as the following
quadratic program:
Maximize W ( ~
ff T D ~
ff
subject to: c T ~
~
~
where interpretation of symbolilc components of (1) varies between the pattern
recognition and the regression cases. For the pattern recognition SVM,
~
For the regression SVM,
~
ff
ff *
\Gammay
K \GammaK
\GammaK K
Details of formulation of SVM training problems can be found in [16], [17], [11],
[13].
As it was mentioned in the introduction, the main idea of decomposition is
to allow only a subset of optimization variables to change weights at a current
iteration. The iteration process is repeated until the termination conditions are
met.
Let ~
ff B denote the variable included in current working set (of fixed size q)
and let ~
ff N denote the rest of the variables. The corresponding parts of vectors
c and ~
y will also bear subscripts N and B. Matrix D will be partitioned into
NB and DNN . It will be further required that, for the regression
SVM, both ff i and ff *
are either included in or omitted from the working set. 2
Optimization of the working set turns out to be also a quadratic program.
This can be seen by rearranging the terms of the objective function and the
equality constraint in (1), and dropping the terms independent of ~
ff B from the
objective. The resulting quadratic program (sub-problem) is formulated as follows

Maximize WB ( ~
subject to: c T
~
~
The termination conditions of the decomposition algorithm are derived from
the KKT conditions ([9], [8]). It is best to consider them separately for the two
types of SVM.
For the pattern recognition SVM, let
l
where b is the threshold of SVM computed as [3]:
l
Strictly speaking this rule is not required in decomposition, however it facilitates
formulation of sub-problems to be solved at each iteration.
Then the point satisfies the KKT provided:
For the regression SVM, let
l
where
l
Then the point satisfies the KKT conditions provided:
Conditions (7) or (10) are checked for individual points : if, at a given iteration,
one of them is violated for some point, this point is exchanged with some point
in the current working set. Thus, the new working set is sub-optimal, and a strict
improvement of the overall objective function is achieved.
The problem with using conditions (7) or (10) is that they require knowledge
of the threshold b which is also the Lagrange multiplier for the equality constraint
of the SVM problem. The formulas given in (6) and (9) require that the set SV
of unbounded support vectors is non-empty. Usually this assumption is true,
however it cannot be guaranteed. While a simple trick can rectify the problem
for the pattern recognition SVM, by letting
a similar trick doesn't work for the regression SVM.
Overcoming this problem has been the initial motivation for the new termination
condition proposed in this article. Instead of individual points, optimality
of the entire working set will be considered. The new condition is described in
detail in Section 4.2.
Intelligent selection of working sets is possible by utilizing ideas of the method
of feasible directions introduced next.
3 The Method of Feasible Directions
Let\Omega be a feasible region of a general constrained optimization problem. Then
a vector d is said to be a feasible direction at the point ff
2\Omega , if there exists
such that ff
2\Omega for all 0     .
The main idea of the method of feasible direction is to find a path from the
initial feasible solution to the optimal solution by making steps along feasible
directions. At each iteration the feasible direction algorithm proceeds as follows:
- find the optimal feasible direction-that is, the feasible direction providing
the largest rate of increase of the objective function.
- determine the step length along the feasible direction that maximizes the
objective function ("line search").
The algorithm terminates when no feasible direction can be found which improves
the objective function. For a general constrained optimization problem
in the form
Maximize f(ff)
subject to: Aff  b
the optimal feasible direction is found by solving the direction finding linear
program:
Maximize rf T d
subject to: Ad  0
The method of feasible directions can be applied directly to SVM training
[8]. In this case, the respective optimal feasible direction problem can be stated
as follows:
Maximize ~ g T d (13)
subject to: c T
where the definitions of ~ g and c vary between the two SVM formulations.
It turns out that solving the linear problem of the full size at each iteration
is expensive, and the overall performance of this method for SVM training is inferior
to traditional optimization methods. However, with a slight modification,
an approximate solution to the optimal feasible direction problem can be obtained
in linear time, and this solution provides a powerful guidance for working
set selection. This approximate solution lies at the core of the feasible direction
decomposition algorithms described in the ensuing sections.
4 Feasible Direction Decomposition of the Pattern
Recognition SVM
4.1 Joachim's Decomposition Algorithm
The key observation of Joachims is that adding a requirement that only q components
of d be non-zero provides a straightforward working set selection rule:
the variables corresponding to those non-zero components are to be included in
the new working set. Unlike Zoutendijk's method, the optimal feasible direction
vector is not to be followed exactly. With re-optimization assumed to be cheap,
one can afford finding an optimal solution in the entire subspace spanned by
non-zero components of d, instead of doing line search strictly along d. Unfor-
tumately, with the additional constraint, the optimal feasible direction problem
becomes intractable. Therefore, one has to seek an approximate solution. One
such solution is realized in Joachims' algorithm. In the rest of this section a detailed
account of this solution is presented-in order to provide some insight and
to underline the ideas used in the extension of this algorithm to the regression
SVM.
The approximate solution is obtained by changing the normalization constraint
(17) to
With this normalization, in order to satisfy the equality constraint (14) (recall
that for the pattern recognition SVM the equality constraint is y T
suffices that the number of elements with sign matches between d i and y i is equal
to the number of elements with sign mismatches between d i and y i . Obviously,
for a working set of size q this condition holds only when each number is equal to
q=2. Therefore, the equality constraint (14) can be enforced by performing two
passes on the data: the "forward pass" selects q=2 elements with sign mismatches,
and the "backward pass"-q=2 elements with sign matches 3 .
How should directions be determined for the elements? Recall that the goal
is to maximize the objective function (13) subject to constraints. In the absense
of constraints the maximum of the objective function would have been achieved
by selecting q points with the highest values of jg i j and assigning directions
them. Let's consider the largest contribution fl k to the objective
function provided by some point k, subject to equality constraints. During the
forward pass the signs of d k and y k must be different, therefore:
(\Gammag
and hence, combining the subscripts,
3 The motivation for the names "forward" and "backward" will be clear shortly.
Likewise, for the backward pass the signs of d k and y k must be the same, therefore

(\Gammag
and hence, combining the subscripts,
Thus the quantity g i y i reflects the element's contribution to the objective function
subject to the equality constraint. The working set composition rule can
then be stated as follows: sort data elements by g i y i in increasing order 4 and
select q=2 elements from the front of the list (hence, the "forward pass"), and
q=2 elements from the back of the list (hence, the "backward pass").
Finally, to account for inequality constraints (15) and (16), some points may
have to be skipped if they violate one of these constraints. For such points, the
direction leading to improvement of the objective function of the optimal feasible
direction problem is infeasible.
Joachims' algorithm is summarized in Algorithm 1.
Algorithm 1 Joachims' SVM decomposition algorithm.
Let S be a list of all samples.
while (termination conditions (7) are not met)
in increasing order
select q=2 samples from the front of S such that
(15) and (16) (forward pass)
select q=2 samples from the back of S such that
(15) and (16) (backward pass)
- re-optimize the working set
4.2 Optimality of a Working Set
As it was mentioned earlier, pointwise termination criteria in Osuna's and Joachims'
algorithms require knowledge of the threshold b of the SVM. This threshold
can be difficult to calculate, especially for the regression SVM. In this section
an alternative termination condition is presented which allows to determine
In practice, sorting which takes O(n log n) operations can be replaced with heap-based
algorithms yielding the complexity of O(n log q) or O(q log n) depending on
how the heap is built.
whether or not the entire working set is sub-optimal and hence suitable for re-
optimization. The new conditions are based on examination of KKT conditioins
for the standard form of a quadratic program. The exposition in this section
concentrates on the pattern recognition SVM, whereas a similar result for the
regression SVM is presented in section 5.1.
Consider the quadratic problem (1)-(2) of the pattern recongition SVM. The
standard form of a quadratic program is obtained by transforming all constraints
to either quality on non-negativity constraints, adding the slack variables when
necessary. In particular, to cast the problem (1)-(2), a vector of slack variables
added for every ff i ! C constraint, and a slack variable
with the 0 value is added to represent the requirement for equality constraint
to be satisified. For notational purposes the following matrices and vectors are
introduced:
I
In the matrix notation (18) all constraints of the original problem (1)-(2) can
be compactly expressed as:
z  0 (19)
Now the Karush-Kuhn-Tucker Theorem ([1], p. 36) can be stated as follows:
Theorem 1 (Karush-Kuhn-Tucker Theorem). The primal vector z solves
the quadratic problem (1) if and only if it satisfies (19) and there exists a dual
vector
\Upsilon  0 (21)
It follows from the Karush-Kuhn-Tucker Theorem that if for all u satisfying
conditions (21) - (22) the system of inequalities (20) is inconsistent then the
solution of problem (1) is not optimal. Since the sub-problem (4) was obtained
by merely re-arranging terms in the objective function and the constraints of
the initial problem (1), the same conditions guarantee that the sub-problem (4)
is not optimal. Thus, the main strategy for identifying sub-optimal working sets
will be to enforce inconsistency of the system (20) while satisfying conditions
Notice that all constant terms in (20) represent the negative gradient vector
y. Thus each inequality in (20) can be written as follows:
Consider three cases, according to the values that ff i can take:
In this case, the complementarity condition (22) implies that
\Gammag
2. ff In this case, the complementarity condition (22), implies that AE
Then inequality (23) becomes
\Gammag
3. In this case, the complementarity condition (22), implies that
Then inequality (23) becomes
\Gammag
It can be easily seen that enforcing the complementarity constraint (22) causes
to become the only free variable in the system (20). Each point restricts  to
a certain interval on a real line. Such intervals will be denoted as -sets in the
rest of the article. The rules for computation of -sets can be summarized as
follows:
\Gammag i ]; if ff
[\Gammag
The development in this section is summarized in the following theorem:
Theorem 2. The vector ff solves the quadratic program (1) - (2) if and only if
intersection of -sets computed by (27) is non-empty.
It also follows from the expressions (27) that if at least one ff i is strictly
between the bounds, then at the optimal solution the intersection of all -sets
(which is non-empty by the Kuhn-Tucker theorem) is a single point set. This is
consistent with the known property of SVM that at the optimal solution
The intersection of -sets at the optimal solution can only be a non-empty, non
single point set if all variables are at the bounds. In this case any point from
the intersection of -sets can be taken as b; in particular, the value suggested in
(11).
4.3 Maximal Inconsistency Algorithm
While inconsistency of the working set at each iteration guarantees convergence
of decomposition, the rate of convergence is quite slow if arbitrary inconsistent
working sets are chosen. A natural heuristic is to select "maximally inconsistent"
working sets, in a hope that such choice would provide the greatest improvement
of the objective function. The notion of "maximal inconsistency" is easy to
define: let it be the gap between the smallest right boundary and the largest left
boundary of -sets of elements in the training set:
0!i!l
l
0!i!l
r
where  l
i are the left and the right boundaries respectively (possibly minus
or plus infinity) of the -set M i . It is convenient to require that the largest
possible inconsistency gap be maintained between all pairs of points comprising
the working set. The obvious implementation of this strategy is to select q=2
elements with the largest values of  l and q=2 elements with the smallest values
of  r .
One feature of Joachims' method needs to be retained - rejection of Zoutendijk-
infeasible points (cf. (15), (16)). Inclusion of such points into the working set
doesn't make sense anyway because their values of ff will not change after re-
optimization. In the pattern recognition case, the -set constraints are not capable
of encoding feasibility 5 . Since the notion of the direction is not explicitly
maintained in the maximal inconsistency algorithm the feasibility test needs
tobe modified slightly: the point is infeasible if ff
and
The maximal inconsistency strategy is summarized in Algorithm 2.
Algorithm 2 Maximal inconsistency algorithm for the pattern recognition
SVM.
Let S be a list of all samples.
while (intersection of all -sets is empty)
according to the rules (27) for all elements in S
select q=2 feasible samples with the largest values of  l ("left pass")
select q=2 feasible samples with the smallest values of  r ("right pass")
- re-optimize the working set
4.4 Equivalence between Joachims' Algorithm and the Maximal
Inconsistency Algorithm
So far the motivation for the maximal inconsistency algorithm has been purely
heuristic. Does inconsistency gap indeed provide a good measure of optimality
5 They will be in the regression case.
for a working set at a given iteration? An affirmative answer is developed in
this section, by showing the equivalence between Joachims' algorithm and the
maximal inconsistency algorithm.
To show that the algorithms are equivalent we have to prove that they produce
identical working sets at each iteration 6 and that their termination conditions
are equivalent. The two propositions below handle each claim.
Proposition 1. The working set of Joachims' algorithm is identical to the working
set of maximal inconsistency algorithm at each iteration.
Proof. The statement above will be proved for the half of the working set;
namely, that the set of elements selected by the "forward pass" of Joachims'
algorithm is identical to the set of elements selected by the "right pass" of the
maximal inconsistency algorithm. Similar argument allows to establish equivalence
of the other half of working sets.
Let F be the set of all feasible samples at some iteration. Let r J (p) denote
the rank (position) of sample p in the array obtained by sorting F by y i
r I (p) be the rank of sample p in the array obtained by sorting F by  r
Let the set H q=2g be the half of the working set selected by
the "forward pass" of Joachims' algorithm. Let
p be the sample whose r J
q=2, i.e. the element in H J with the largest value of the key. Let H I
r (p)   r (p)g. We are going to prove that H J j H I .
For any sample p i selected by the "forward pass" d \Gammay i . Considering the
possible values of ff i , we conclude that, for any p 2
We can see that the order of  r (p) is preserved when mapping H J 7! H I .
Therefore, if
To prove set equivalence, it remains to be shown that if p 2 H I then p 2 H J .
Suppose, by the way of contradiction this is not the case, i.e. there exists an
sample ~
p such that  r (~p) !  r (p) and ~
What is  r (~p) equal to? Three possible cases are covered in (28), and in each of
them  r . In this case  r (~p) !  r (p) ) r J (~p) ! r J (p) which contradicts
our previous conclusion that r J (~p)  r J (p). In the remaining two cases of (27)
which contradicts our assumption that  r (~p) !  r (p). Thus we can
conclude that H J j H I .
Proposition 2. Termination conditions of the Joachims' algorithm are satisfied
if and only if the termination conditions of the maximal inconsistency algorithm
are satisfied.
6 Since both algorithms use identical feasibility check for every sample, it is obvious
that infeasible samples will never be included in a working set in both algorithms.
Proof. The maximal inconsistency algorithm terminates when the system (20)
is consistent while at the same time conditions (21) - (22) are enforced. Hence,
the KKT conditions are satisfied, and consequently, the algorithm terminates
if and only if the optimal solution is found. Likewise, termination conditions
have an "if and only if" relationship to the KKT conditions and
hence to the optimality of the solution, except when the solution contains all
variables strictly at the bounds and (11) is used for calculation of b. In the
latter case, however, condition (11) satisfies the KKT conditions of the primal
SVM training problem (to which the problem (1) - (2) is a dual). Then it follows
from Dorn's duality theorem ([6]. p. 124), that the solution of the dual problem is
also optimal. Hence, both algorithms terminate at the same point in the solution
space.
5 Feasible Direction Decomposition of the Regression
5.1 Maximal Inconsistency Algorithm
We now turn our attention to the maximal inconsistency algorithm for the regression
SVM. Recall that the quadratic program for the latter is given by equations
(1) and (3). The derivation will progress in the same way as in the pattern recognition
case and will consist of: (a) stating the Karush-Kuhn-Tucker Theorem for
the standard form of QP, (b) derivation of rules for computation of -sets, and
(c) defining the inconsistency gap to be used for working set selection in the
algorithm.
The standard form of QP for the regression SVM is defined by the following
matrices:
I
~
in terms of which the constraints can expressed in the same way as in the pattern
recognition case:
~
z  0 (30)
The statement of the Karush-Kuhn-Tucker Theorem, as well as its use to test
optimality of the working set, remain the same (see Theorem 1 and the ensuing
discussion).
For the regression SVM, each inequality in (20) has one of the following
forms:
*
where
l
Considering the possible values of ff i we have:
1. In this case s
Then inequality (31) becomes:
2. ff
becomes:
3.
inequality (31) becomes:
Similar reasoning for ff *
i and inequality (32) yields the following results:
1. ff *
2. ff *
3.
Finally, taking into account that for the regression SVM ff i ff *
the rules
for computation of -sets for the regression SVM are the following:
For the regression SVM, the new termination condition is stated in the following
theorem.
Algorithm 3 Maximal inconsistency algorithm for the regression SVM.
Let S be a list of all samples.
while (intersection of -sets is empty)
according to the rules (34) for all elements in S
select q=2 feasible samples with the largest values of  l ("left pass")
select q=2 feasible samples with the smallest values of  r ("right pass")
- re-optimize the working set
Theorem 3. The vector ff solves the quadratic program (1) - (3) if and only if
intersection of -sets computed by (34) is non-empty.
The maximal inconsistency algorithm for the regression SVM is summarized
in Algorithm 3.
Feasibility of samples is tested by the following rule: during the left pass
skip samples with ff during the right pass skip samples with
Justification of this rule is given in Lemma 1 in Section 5.2.
5.2 Interpretation of the Maximal Inconsistency Algorithm in the
Feasible Direction Framework
As it was shown in Section 4.4, the maximal inconsistency algorithm is equivalent
to Joachims' algorithm which was motivated by Zoutendijk's feasible direction
problem. In this section it will be demonstrated that the maximal inconsistency
algorithm for the regression SVm can also be interpreted as a feasible direction
algorithm.
Recall the SVM optimal feasible direction problem stated in (13) - (17).
The problem-specific components ~
and c have the following expressions for the
regression SVM:
~
*
where
*
and OE is defined in (33). In addition, a feasible direction algorithm must satisfy
the constraint
To develop an equivalent feasible direction algorithm, we will construct a
mapping \Phi ~
ff which maps the state of the maximal inconsistency algorithm to a
direction vector d, and a normalization Nd similar to Joachims' normalization
which replaces (17). The construction will possess the following properties:
1. At each iteration, \Phi ~
ff is the solution to the optimal feasible direction problem
with normalization Nd .
2. Termination condition of the maximal inconsistency algorithm holds if and
only if the solution to the optimal feasible direction problem is a zero direction

Intuitively, the first property shows that working sets selected by the maximal
inconsistency algorithm are the same as those selected by a feasible direction
algorithm using normalization Nd . The second property ensures that both algorithms
terminate at the same time.
Consider the normalization
and the mapping
(\Phi ~
or (0; \Gamma1), whichever is feasible, during the left pass
or (0; 1), whichever is feasible, during the right pass
(0; 0), if sample i is infeasible or not reached
For the sake of brevity, the optimal feasible direction problem comprising equations
will be denoted as the feasible direction problem.
First, we need to make sure that \Phi ~
ff is not ambiguous, i. e. that only one of
the non-zero directions suggested in (39) is feasible.
Lemma 1. Mapping \Phi ~
ff is not ambiguous.
Proof. Let us denote directions (1; 0); (0; \Gamma1); (\Gamma1; 0); (0; 1) as Ia, Ib, IIa, IIb
(Type I directions are assigned during the left pass, and Type II directions-
during the right pass). Table 1 shows feasibility of different directions depending
on the values of optimization variables: Infeasibility of directions marked by y

Table

1. Feasibility of directions
Optimization variables Feasible Infeasible
is due to the special property of regression SVM that ff i ff *
It follows from
the table that at each pass only one direction is feasible.
This lemma justifies the feasibility test of the maximal inconsistency algo-
rithm. It is clear from Table 1 that during the left pass there is no feasible
direction for samples with ff
during the right pass there
is no feasible direction for samples with ff
The next two lemmas show that \Phi ~
ff provides a solution to the feasible direction
problem.
Lemma 2. \Phi ~
ff satisfies all constraints of the feasible direction problem.
Proof. The equality constraint of the optimal feasible dirction problem for the
regression SVM has the form:
l
l
d *
be the number of selected elements with directions f1; 0g,f\Gamma1; 0g,
f0; \Gamma1g, f0; 1g respectively. Then
l
l
d *
By the selection policy:
from which it follows that
Hence, \Phi ~
ff satisfies the equality constraint of the optimal feasible direction problem

Inequality constraints and the cardinality constraint are trivially satisfied by
the construction of \Phi ~
ff .
Lemma 3. \Phi ~
ff provides the optimal value of the objective function of the feasible
direction problem.
Proof. Let B l and B r denote the halves of the working set selected by the
left and the right passes respectively. Suppose, by the way of contradiction, that
there exists a feasible sample i such that g i d i ?
For any element k considered during the left pass
k if (0; \Gamma1) is feasible
Therefore, if
which contradicts the hypothesis that
Likewise, for any element k considered during the right pass
k if (0; 1) is feasible
Therefore, if
\Gammag
which contradicts the hypothesis that
Lemma 4. Intersection of -sets is non-empty if an only if the feasible direction
problem has a zero solution.
Proof. By Theorem 3, non-empty intersection of -sets implies optimality of
the solution to the quadratic program (1) - (3) which rules out existence of a
non-zero feasible direction which would otherwise have have led to a new optimal
solution.
On the other hand, if the optimal solution to the feasible direction problem
is zero, this implies that all other feasible directions have negative projections
on the gradient vector, and hence decrease the value of the objective function.
It follows that the solution of the quadratic program (1) - (3) is optimal, and
hence intersection of -sets is non-empty.
prove the two properties of the mapping \Phi ~
ff and the normalization
Nd claimed earlier in this section.
6 Experimental Results
The aim of this section is to provide insight into some properties of feasible direction
decomposition algorithms that might explain their behaviour in different
situations. In particular, the following issues are addressed:
scaling factors. This is the traditional way of analyzing performance
of SVM training algorithms, introduced by Platt [10] and Joachims [3]. To
perform at least qualitative comparison with their results, a similar evaluation
is performed for the maximal inconsistency algorithm.
- Experimental convergence rates. In traditional optimization literature algorithms
are most often evaluated in terms of their convergence rates. Since the
decomposition algorithms borrow their core ideas from optimization theory
and are iterative, it is natural to attempt to establish their rates of con-
vergence. It will be shown that the maximal inconsistency algorithm seems
to have linear rate of convergence which is consistent with known linear
convergence rates for gradient descent methods.
Profiled scaling factors. While decreasing the number of iterations is highly
desirable, it must not be achieved at a cost of significantly increasing the
cost of an iteration. It is therefore important to investigate the "profile" of
one iteration of the decomposition algorithm.
Experimental evaluation of the new algorithm was performed on the modified
KDD Cup 1998 data set. The original data set is available under
http://www.ics.uci.edu/kdd/databases/kddcup98/kddcup98.html.
The following modifications were made to obtain a pure regression problem:
- All 75 character fields were eliminated.
fields CONTROLN, ODATEDW, TCODE and DOB were elimi-
tated.
The remaining 400 features and the labels were scaled between 0 and 1.
Initial subsets of the training database of different sizes were selected for evaluation
of the scaling properties of the new algorithm. Experiments were run
on a SUN4U/400 Ultra-450 workstation with 300MHz clock and 2048M RAM.
RBF kernel with cache size of 300M
were used. The value of the box constraint C was 1, and the working set of size
was used. Two sets of experiments were performed: one using the full set of
400 features, another one using only the first 50 features ("reduced set"). As it
turns out, the second problem is more constrained, with a larger proportion of
bounded support vectors. Also, for the full set of features kernel computation
dominates the overall training time.
6.1 Overall Scaling Factors
The training times, with and without decomposition, for different samples sizes,
are displayed in Tables 2 and 3, for the full and the reduced sets of features
respectively. The scaling factors are computed by plotting training times versus
sample sizes on a log-log scale and fitting straight lines. The SV-scaling factors
are obtained in the same fashion, only using the number of unbounded support
vectors instead of the sample size as an abscissa. The actual plots are shown in

Figure

1.
It can be easily seen that decomposition improves the running time by an
order of magnitude. It's scaling factors are also significantly better. The scaling
factors are consistent with the scaling factors presented by Platt [10] and
Joachims [3] for the pattern recognition SVM.
A number of other interesting findings can be made from the results above.
First, it is easily seen that the training with decomposition does not produce
an identical solution to training without. The solutions differ in the number of
support vectors, especially for the more constrained problem with the reduced
set of features. This difference is due to the fact that the termination conditions
7 In order for the results to be conceptually compatible with Joachims' I used the old
point-wise termination conditions.

Table

2. Training time (sec) and number of SVs for the KDD Cup problem.
Examples no dcmp dcmp
time total SV BSV time total SV BSV
1000 91.193 454 0 24.907 429 0
2000 665.566 932 2 118.131 894 2
5000 10785.4 2305 7 914.359 2213 7
10000 92684.7 4598 28 4958.26 4454 26
scaling factor: 3.03 2.29
SV-scaling factor: 2.86 2.13

Table

3. Training time (sec) and number of SVs for the KDD Cup problem, reduced
feature set.
Examples no dcmp dcmp
time total SV BSV time total SV BSV
500 16.958 114 29 14.175 128 26
1000 129.591 242
2000 998.191 445 114 178.752 656 104
5000 10759.6 977 323 929.523 1667 255
10000 79323.2 1750 633 2782.35 3383 491
scaling factor: 2.80 1.76
SV-scaling factor: 3.12 1.60
logT
Scaling factors for SVM training with and without decomposition
(a)
logT
Scaling factors for SVM training with and without decomposition
(b)
Fig. 1. Scaling factor fits: (a) full set of features (Table 2), (b) reduced set of features

Table

of the decomposition algorithm require that KKT conditions be satisfied only
to a given numerical precision. Thus the decomposition algorithm does have a
disadvantage of producing an approximate solution, which can be further seen
from

Tables

4 and 5. These tables display the values of the objective functions
attained by training with and without decomposition, and their ratio. The latter
shows that in the relative turns, a solution of the more constrained problem with
the reduced feature set is roughly 10 times worse that the solution of the less
constrained problem with the fulls feature set. However, no deviation of the
accuracy with the sample size is observed.
Another important observation is that the scaling factors and the SV-scaling
factors vary among different problems. For the two particular problems, a possible
explanation might be that the fixed termination accuracy is in fact looser for
the more constrained problem, thereby producing a less accurate solution but
taking less time in doing so. In general, however, the results above demonstrate
that the scaling factors produce a rather crude measure of performance of the
decomposition algorithms 8 .

Table

4. Objective function values for KDD Cup problem.
Examples no dcmp dcmp ratio
1000 0.43501 0.43488 0.99970
2000 1.27695 1.27662 0.99974
5000 3.19561 3.19414 0.99953
10000 6.74862 6.74507 0.99947

Table

5. Objective function values for KDD Cup problem, reduced feature set.
Examples no dcmp dcmp ratio
500 1.11129 1.10823 0.99724
1000 3.25665 3.24853 0.99750
2000 6.41472 6.39787 0.99456
5000 14.5490 14.5164 0.99776
10000 26.9715 26.9119 0.99779
8 The scaling factors also vary in the results of Joachims [3].
6.2 Convergence Rates
In optimization literature, a common performance measure for iterative algorithms
is convergence rate. The notion of the convergence rate is generally defined
for any numeric sequence; for the purpose of analysis of decomposition
algorithms we will be concerned with the sequence of objective function values.
The following definitions are taken from [7].
Let x k be a sequence in IR n that converges to x * . Convergence is said to be
Q-linear if there is a constant r 2 (0; 1) such that
sufficiently large,
The prefix "Q" stands for "quotient" because the quotient of successive distances
from the limit point is considered. Likewise, convergence is said to be
Q-superlinear if
lim
and is said to be of order p (for p ? 1) or quadratic (for
M; for all k sufficiently large.
where M is a positive constant not necessarily less than 1. It can be easily
seen that a Q-convergent sequence of order strictly greater than 1 converges
Q-superliearly 9 .
Convergence rates can be observed experimentally by recording the values of
the objective function through the course if iteration and plotting the respective
ratios versus the iteration number. Sample plots are shown in Figures 2 and 3
for both problems on a training sample of size 10000. Limit points have been
obtained from training without decomposition. Similar plots have been observed
in other experiments.
It is evident from the convergence plots that the decomposition algorithm
converges linearly but not superlinearly or quadratically 10 . The plots also reveal
that the training problem is very ill-conditioned, as the ratio stays very close to
1.
The above results are consistent with known linear convergence rates for gradient
descent methods for unconstrained optimization. Noteworthy is particular
semblance for the full feature set problem in which most of the variables stay
away from the upper bounds and thus resemble an unconstrained case. Another
important message is that convergence analysis (experimental or theoretical) is
of special importance for decomposition algorithms. Unlike the scaling factors it
reveals the effects of conditioning on the algorithm's performance.
9 The prefix "Q" will be omitted in the rest of the presentation in this section.
It is difficult to see from the plot for the reduced feature set, but there is a tiny
margin of  0:0001 which seprates the ratios from 1.
0.9920.9940.9960.998iteration
linear
ratio
(a) linear
1000 2000 3000 4000 5000 6000 7000 8000 90000.961.021.06
iteration
ratio
1000 2000 3000 4000 5000 6000 7000 8000 9000100200300
iteration
quadratic
ratio
(c) quadratic
Fig. 2. Convergence rates for the full feature space
1000 2000 3000 4000 5000 6000 70000.9910.9930.9950.9970.999
iteration
linear
ratio
(a) linear
1000 2000 3000 4000 5000 6000 70000.960.981.011.03
iteration
ratio
1000 2000 3000 4000 5000 6000 70001216iteration
quadratic
ratio
(c) quadratic
Fig. 3. Convergence rates for the reduced feature space
6.3 Profiled Scaling Factors
The overall processing performed during an iteration of the feasible direction
decomposition algorithm can be broken up into 5 main steps:
1. Optimization: optimization proper and calculation of support vectors.
2. Update of gradients.
3. Kernel evaluation: all requests for dot products (from all modules of the
system). Notice that with caching of kernel evaluations, this operation is not
equally distributed across iterations: at the beginning it takes longer when
kernels must be computed; towards the end all kernels end up in cache 11 .
4. Selection: computation of maximal violation of KKT conditions, left and
right passes.
5. Evaluation: computation of objective function and threshold.
In the following section the scaling factors per iteration are established for the
five factors (overall scaling factors for kernel evaluation).
Optimization scaling factors. The values of obtained selection scaling factors
are 0.237 for the full feature space and 0.176 for the reduced feature space,
however the quality of fits is low. The expected behavior was constant-time
per iteration, because the working sets are of constant size. Perhaps, for larger
data sets conditioning of sub-problems deteriorates slightly, thus increasing the
number of iterations in the optimizer 12 . The fits are displayed in Figure 4
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
-3.6
-3.4
-3.2
-2.6
-2.4
-2.2
log
logT
opt
Optimization scaling factor
(a) full set of features
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
-3.6
-3.4
-3.2
-2.6
-2.4
-2.2
log
logT
opt
Optimization scaling factor
(b) reduced set of features
Fig. 4. Optimization scaling factor fits.
11 In the experiments above enough memory was allocated for the kernel cache to hold
the values of kernels for all support vectors.
12 The current implementation uses MINOS to solve optimization problems.
Update scaling factors. The values of obtained update scaling factors are
1.060 for the full feature space and 1.064 for the reduced feature space. This
coinsides with the theoretical expectations of linear growth order of update op-
eration. The fits are displayed in Figure 5.
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
-2.6
-2.4
-2.2
-1.4
-1.2
log
logT
update
Update scaling factor
(a) full set of features
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
-2.6
-2.4
-2.2
-1.4
-1.2
log
logT
update
Update scaling factor
(b) reduced set of features
Fig. 5. Update scaling factor fits.
Kernel scaling factors. Kernel scaling factors are computed based on the
timing accumulated over the entire run. The obtained values are 2.098 and 2.067
for the full and the reduced sets of features respectively. This coincides with the
expected quadratic order of growth. The fits are displayed in Figure 6.
logT
kernel
Kernel scaling factor
(a) full set of features
logT
kernel
Kernel scaling factor
(b) reduced set of features
Fig. 6. Kernel scaling factor fits.
Selection scaling factors. The values of obtained selection scaling factors
are 1.149 for the full feature space and 1.124 for the reduced feature space.
This is close to the theoretical expectations of linear growth order of selection
operation 13 . The fits are displayed in Figure 7.
2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4
-2.6
-2.4
-2.2
-1.4
-1.2
(a) full set of features
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
-2.6
-2.4
-2.2
-1.4
-1.2
log
logT
selection
Selection scaling factor
(b) reduced set of features
Fig. 7. Selection scaling factor fits.
Evaluation scaling factors. The values of obtained evaluation scaling factors
are 1.104 for the full feature space and 1.118 for the reduced feature space.
This is close to the theoretical expectations of linear growth order of evaluation
operation. The fits are displayed in Figure 8.
Conclusions
The unified treatment of the working set selection in decomposition algorithms
presented in this article provides a general view of decomposition methods based
on the principle of feasible direction, regardless of the particular SVM formula-
tion. Implementation of the maximal inconsistency strategy is straightforward
for both pattern recognition and regression SVM, and either of the termination
conditions can be used. Formal justification of the maximal inconsistency
strategy provides a useful insight into the mechanism of working set selection.
The experimental results demonstrate that, similar to the pattern recognition
case, significant decrease of training time can be achieved by using the decomposition
algorithm. While the scaling factors of the decomposition algorithms
are significantly better than those of straightforward optimization, a word of
13 The implementation uses heap-based method whose theoretical running time order
is O(n log q). The logarithmic factor does not feature in the scaling factor because q
is assumed constant.
2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
log
logT
evaluation
Evaluation scaling factor
(a) full set of features
2.2 2.4 2.6 2.8 3.2 3.4 3.6 3.8 4
log
logT
evaluation
Evaluation scaling factor
(b) reduced set of features
Fig. 8. Evaluation scaling factor fits.
caution needs to be said with regard to the constants. It can be seen from the
profiled experiments that the worst-case growth orders can only be given on a
per-iteration basis, and the number of iterations, which depends on the convergence
rate and the required precision, adds another dimension to running time
analysis. The linear convergence rate observed in the experiments suggests that
the progress towards the optimal solution can be slow. Additional investigation
of the impact of problem conditioning is necessary.
A number of open questions remain regarding the SVM decomposition al-
gorithms. Can the linear convergence rate be established theoretically? Can a
super-linear or a quadratic convergence rate be achieved by a different algo-
rithm? Finally, extremely far-reaching results can be borne by investigation of
conditioning of the training problem: since the latter is a by-product of a number
of factors, such as the choice of kernel, the box constraint, the risk functional,
etc, conditioning of the optimization problem might be useful to guide the choice
of SVM parameters.



--R

Quadratic Programming.
The analysis of decomposition methods for support vector machines.
Making large-scale support vector machine learning practical
Solving the quadratic problem arising in support vector classi- fication
An improved decomposition algorithm for regression support vector machines.
Nonlinear Programming.
Numerical Optimization.
Support Vector Machines: Training and Applications.
Improved training algorithm for support vector machines.
Fast training of support vector machines using sequential minimal optimization.
Support Vector Learning.
Advances in Kernel Methods - Support Vector Learning
Learning with Kernels.
A tutorial on support vector regression.
Estimation of Dependences Based on Empirical Data.
The Nature of Statistical Learning Theory.
Statistical Learning Theory.
Methods of Feasible Directions.
--TR

--CTR
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
Chih-Wei Hsu , Chih-Jen Lin, A Simple Decomposition Method for Support Vector Machines, Machine Learning, v.46 n.1-3, p.291-314, 2002
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
Nikolas List , Hans Ulrich Simon, General Polynomial Time Decomposition Algorithms, The Journal of Machine Learning Research, 8, p.303-321, 5/1/2007
Pavel Laskov , Christian Gehl , Stefan Krger , Klaus-Robert Mller, Incremental Support Vector Learning: Analysis, Implementation and Applications, The Journal of Machine Learning Research, 7, p.1909-1936, 12/1/2006
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
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
Hyunjung Shin , Sungzoon Cho, Neighborhood Property--Based Pattern Selection for Support Vector Machines, Neural Computation, v.19 n.3, p.816-855, March 2007
support vector machines;training;working set selection;decomposition algorithms;methods of feasible directions