Choosing Multiple Parameters for Support Vector Machines.
The problem of automatically tuning multiple parameters for pattern recognition Support Vector Machines (SVMs) is considered. This is done by minimizing some estimates of the generalization error of SVMs using a gradient descent algorithm over the set of parameters. Usual methods for choosing parameters, based on exhaustive search become intractable as soon as the number of parameters exceeds two. Some experimental results assess the feasibility of our approach for a large number of parameters (more than 100) and demonstrate an improvement of generalization performance.
Introduction
In the problem of supervised learning, one takes a set of input-output pairs
and attempts to construct a classier function f
that maps input vectors x 2 X onto labels y 2 Y. We are interested here in
pattern recognition or classication, that is the case where the set of labels
is simply 1g. The goal is to nd an f 2 F which minimizes the
error (f(x) 6= y) on future examples. Learning algorithms usually depend
on parameters which control the size of the class F or the way the search
is conducted in F . Several techniques exist for performing the selection of
these parameters. The idea is to nd the parameters that minimize the
generalization error of the algorithm at hand. This error can be estimated
either via testing on some data which has not been used for learning (hold-
out testing or cross-validation techniques) or via a bound given by theoretical
analysis.
Tuning multiple parameters Usually there are multiple parameters to
tune at the same time and moreover, the estimates of the error are not
explicit functions of these parameters, so that the only applicable strategy
which is exhaustive search in the parameter space becomes intractable since
it would correspond to running the algorithm on every possible value of the
parameter vector (up to some discretization). We propose here a methodology
for automatically tuning multiple parameters for the Support Vector
Machines (SVMs) which takes advantage of the specicity of this algorithm.
The SVM algorithm Support vector machines (SVMs) realize the following
idea: map an n-dimensional input vector x 2 R n 1 into a high dimensional
(possibly innite dimensional) feature space H by  and construct an
optimal separating hyperplane in this space. Dierent mappings construct
dierent SVMs.
When the training data is separable, the optimal hyperplane is the one
with the maximal distance (in H space) between the hyperplane and the closest
image of the vector x i from the training data. For non-separable
training data a generalization of this concept is used.
Suppose that the maximal distance is equal to M and that the images
of the training vectors x are within a sphere of radius
R. Then the following theorem holds true [19].
Theorem 1 Given a training set of size ', a
feature space H and an hyperplane (w; b), the margin M(w; b; Z) and the
radius R(Z) are dened by
kwk
The maximum margin algorithm takes as input a
training set of size ' and return an hyperplane in feature space such that the
margin M(w; b; Z) is maximized. Note that supposing the training separable
1 In the rest of this article, we will reference to vectors and matrices using the bold
notation
means that M > 0. Under this assumption, for all probability measures P
underlying the data Z, the expectation of the misclassication probability
has the bound
The expectation is taken over the random draw of a training set Z of size
for the left hand side and size ' for the right hand side.
This theorem justies the idea of constructing a hyperplane that separates
the data with a large margin: the larger the margin the better the
performance of the constructed hyperplane. Note however that according to
the theorem the average performance depends on the ratio EfR 2 =M 2 g and
not simply on the large margin M .
Why multiple parameters ? The SVM algorithm usually depends on
several parameters. One of them, denoted C, controls the tradeo between
margin maximization and error minimization. Other parameters appear in
the non-linear mapping into feature space. They are called kernel parame-
ters. For simplicity, we will use a classical trick that allows to consider C
as a kernel parameter, so that all parameters will be treated in a unied
framework.
It is widely acknowledged that a key factor in an SVM's performance
is the choice of the kernel. However, in practice, very few dierent types
of kernels have been used due to the di-culty of appropriately tuning the
parameters. We present here a technique that allows to deal with a large
number of parameters and thus allows to use more complex kernels.
Another potential advantage of being able to tune a large number of
parameters is the possibility of rescaling the attributes. Indeed, when no a
priori knowledge is available about the meaning of each of the attributes,
the only choice is to use spherical kernels (i.e. give the same weight to each
attribute). But one may expect that there is a better choice for the shape of
the kernel since many real-world database contain attributes of very dierent
natures. There may thus exist more appropriate scaling factors that give
the right weight to the right feature. For example, we will see how to use
radial basis function kernels (RBF) with as many dierent scaling factors as
input dimensions:
The usual approach is to consider and to try to pick up
the best value for . However, using the proposed method, we can choose
automatically good values for the scaling factors  i . Indeed, these factors
are precisely parameters of the kernel.
Moreover, we will demonstrate that the problem of feature selection can
be addressed with the same framework since it corresponds to nding those
attributes which can be rescaled with a zero factor without harming the
generalization.
We thus see that tuning kernel parameters is something extremely useful
and a procedure that allows to do this would be a versatile tool for various
tasks such as nding the right shape of the kernel, feature selection, nding
the right tradeo between error and margin, etc. All this gives a rationale
for developing such techniques.
Our approach We thus see that our goal is not only to nd the hyperplane
which maximizes the margin but also the values of the mapping parameters
that yield best generalization error. To do so, we propose a minimax ap-
maximize the margin over the hyperplane coe-cients and minimize
an estimate of the generalization error over the set of kernel parameters.
This last step is performed using a standard gradient descent approach.
What kind of error estimates We will consider several ways of assessing
the generalization error.
Validation error: this procedure requires to reduce the amount of data
used for learning in order to save some of it for validation. Moreover,
the estimates have to be smoothed for proper gradient descent.
Leave-one-out error estimates: this procedure gives an estimate of the
expected generalization as an analytic function of the parameters.
We will examine how the accuracy of the estimates in
uences the whole procedure
of nding optimal parameters. In particular we will show that what
really matters is how the variations of the estimate relate to the variations
of the test error rather than how their values are related.
Outline The paper is organized as follows. The next section introduces
the basics of SVMs. The dierent possible estimates of their generalization
error are described in section 3 and section 4 explains how to smooth theses
estimates. Then we introduce in section 5 a framework for minimizing those
estimates by gradient descent. Section 6 deals with the computation of
gradients of error estimates with respect to kernel parameters. Finally, in
section 7 and 8, we present experimental results of the method applied to a
variety of databases in dierent contexts. Section 7 deals with nding the
right penalization along with the right radius for a kernel and with nding
the right shape of a kernel. In section 8 are presented results of applying
our method to feature selection.
Learning
We introduce some standard notations for SVMs; for a complete description,
see [18]. Let f(x be a set of training examples, x i 2 R n which
belong to a class labeled by y 1g. In the SVM methodology, we map
these vectors into a feature space using a kernel function K(x
denes an inner product in this feature space. Here, we consider a kernel
K  depending on a set of parameters . The decision function given by an
is:
where the coe-cients  0
are obtained by maximizing the following functional

i2
under the constraints
The coe-cients  0
dene a maximal margin hyperplane in a high-dimensional
feature space where the data are mapped through a non-linear function
such that
This formulation of the SVM optimization problem is called the hard
margin formulation since no training errors are allowed. Every training point
satises the inequality y corresponding
an equality is satised. These points are called support vectors.
Notice that one may require the separating hyperplane to pass through
the origin by choosing a xed This variant is called the hard margin
SVM without threshold. In that case, the optimization problem remains the
same as above except that the constraint
disappears.
Dealing with non-separability For the non-separable case, one needs
to allow training errors which results in the so called soft margin SVM
algorithm [4]. It can be shown that soft margin SVMs with quadratic penalization
of errors can be considered as a special case of the hard margin
version with the modied kernel [4, 16]
where I is the identity matrix and C a constant penalizing the training
errors. We will focus in the remainder on the hard margin SVM and use
(3) whenever we have to deal with non-separable data. Thus C will be
considered just as another parameter of the kernel function.
3 Estimating the performance of an SVM
Ideally we would like to choose the value of the kernel parameters that minimize
the true risk of the SVM classier. Unfortunately, since this quantity
is not accessible, one has to build estimates or bounds for it. In this section,
we present several measures of the expected error rate of an SVM.
3.1 Single validation estimate
If one has enough data available, it is possible to estimate the true error on
a validation set. This estimate is unbiased and its variance gets smaller as
the size of the validation set increases. If the validation set is f(x 0
the estimate is
where is the step function:
3.2 Leave-one-out bounds
The leave-one-out procedure consists of removing from the training data one
element, constructing the decision rule on the basis of the remaining training
data and then testing on the removed element. In this fashion one tests all '
elements of the training data (using ' dierent decision rules). Let us denote
the number of errors in the leave-one-out procedure by L(x It
is known [10] that the the leave-one-out procedure gives an almost unbiased
estimate of the expected generalization error:
err is the probability of test error for the machine trained on a sample
of size ' 1 and the expectations are taken over the random choice of the
sample.
Although this lemma makes the leave-one-out estimator a good choice when
estimating the generalization error, it is nevertheless very costly to actually
compute since it requires running the training algorithm ' times. The
strategy is thus to upper bound or approximate this estimator by an easy
to compute quantity T having, if possible, an analytical expression.
If we denote by f 0 the classier obtained when all training examples are
present and f i the one obtained when example i has been removed, we can
which can also be written as
Thus, if U p is an upper bound for y p (f 0 get the
following upper bound on the leave-one-out error:
since for hard margin SVMs, y monotonically increasing

3.2.1 Support vector count
Since removing a non-support vector from the training set does not change
the solution computed by the machine (i.e. U
non-support vector), we can restrict the preceding sum to support vectors
and upper bound each term in the sum by 1 which gives the following bound
on the number of errors made by the leave-one-out procedure [17]:
where N SV denotes the number of support vectors.
3.2.2 Jaakkola-Haussler bound
For SVMs without threshold, analyzing the optimization performed by the
SVM algorithm when computing the leave-one-out error, Jaakkola and Haussler
[8] proved the inequality:
which leads to the following upper bound:
Note that Wahba et al. [20] proposed an estimate of the number of errors
made by the leave-one-out procedure, which in the hard margin SVM case
turns out to be
which can be seen as an upper bound of the Jaakkola-Haussler one since
3.2.3 Opper-Winther bound
For hard margin SVMs without threshold, Opper and Winther [12] used
a method inspired from linear response theory to prove the following: under
the assumption that the set of support vectors does not change when
removing the example p, we have
where K SV is the matrix of dot products between support vectors; leading
to the following estimate:

3.2.4 Radius-margin bound
For SVMs without threshold and with no training errors, Vapnik [18] proposed
the following upper bound on the number of errors of the leave-one-out
procedure:
where R and M are the radius and the margin as dened in theorem 1.
3.2.5 Span bound
Vapnik and Chapelle [19, 3] derived an estimate using the concept of span
of support vectors.
Under the assumption that the set of support vectors remains the same
during the leave-one-out procedure, the following equality is true:
is the distance between the point and the set  p where
This gives the exact number of errors made by the leave-one-out procedure
under the previous assumption:
The span estimate can be related to other approximations:
Link with Jaakkola-Haussler bound
If we consider SVMs without threshold, the constraint
be removed in the denition of the span. Then we can easily upper
bound the value of the span: S 2
thus recover the
Jaakkola-Haussler bound.
Link with R 2 =M 2
For each support vector, we have y
the number of errors made by the leave-one-out procedure is
bounded by: X
It has been shown [19] that the span S p is bounded by the diameter
of the smallest sphere enclosing the training points and since
the number of errors made by the leave-one-out procedure is
bounded by
Link with opper-Winther
When the support vectors do not change, the hard margin case without
threshold gives the same value as the opper-Winther bound, namely:
4 Smoothing the test error estimates
The estimate of the performance of an SVM through a validation error (4) or
the leave-one-out error (5) requires the use of the step function . However,
we would like to use a gradient descent approach to minimize those estimates
of the test error. Unfortunately the step function is not dierentiable. As
already mentioned in section 3.2.5, it is possible to bound (x 1) by x
for x  0. This is how the bound R 2 =M 2 is derived from the leave-one-out
error. Nevertheless by doing so, large errors count more than one, therefore
it might be advantageous instead to use a contracting function of the form
However, the choice of the constants A and B is di-cult. If A is too
small, the estimate is not accurate and A is too large, the resulting estimate
is not smooth.
Instead of trying to pick up the good constants A and B, one can try
to get directly a smooth approximation of the test error by estimating posterior
probabilities. Recently, Platt proposed the following estimate of the
posterior distribution P of an SVM output f(x) [13]:
~
4.0 -3.0 -2.0 -1.0 -0.0 1.0
-2.348
-0.306

Figure

1: Validation error for dierent values of the width of an RBF kernel.
Top left: with a step function,
otherwise. Note that on the bottom picture, the minimum is not at the
right place
where f(x) is the output of the SVM. The constants A and B are found
by minimizing the Kullback-Leibler divergence between ~
P and an empirical
approximation of P built from a validation set
This optimization is carried out using a second order gradient descent algorithm
[13].
According to this estimate the best threshold for our SVM classier f is
such that
PA  ;B (x) 0:5). Note that if B  6= 0, we obtained a
correction comparable to the usual SVM threshold.
By denition the generalization error of our classier is
Z
Z
This error can be empirically estimated as
~
min
~
Note that the labels of the validation set are not used directly in this
last step but indirectly through the estimation of the constants A and B
appearing in the parametric form of ~
PA  ;B  . To have a better understanding
of this estimate, let us consider the extreme case where there is no error on
the validation set. Then the maximum likelihood algorithm is going to yield
PA  ;B (x) will only take binary values. As a consequence, the
estimate of the error probability will be zero.
5 Optimizing the kernel parameters
Let's go back to the SVM algorithm. We assume that the kernel k depends
on one or several parameters, encoded into a vector
thus consider a class of decision functions parametrized by , b and :
We want to choose the values of the parameters  and  such that W (see
equation (2)) is maximized (maximum margin algorithm) and T , the model
selection criterion, is minimized (best kernel parameters). More precisely,
for  xed, we want to have  choose  0 such that
When  is a one dimensional parameter, one typically tries a nite number
of values and picks the one which gives the lowest value of the criterion
We note ~
as an abbreviation for ~
PA  ;B  (x)
T . When both T and the SVM solution are continuous with respect to ,
a better approach has been proposed by Cristianini et al. [5]: using an incremental
optimization algorithm, one can train an SVM with little eort
when  is changed by a small amount. However, as soon as  has more than
one component computing T (; ) for every possible value of  becomes
intractable, and one rather looks for a way to optimize T along a trajectory
in the kernel parameter space.
Using the gradient of a model selection criterion to optimize the model
parameters has been proposed in [2] and demonstrated in the case of linear
regression and time-series prediction. It has also been proposed by [9] to
optimize the regularization parameters of a neural network.
Here we propose an algorithm that alternates the SVM optimization
with a gradient step is the direction of the gradient of T in the parameter
space. This can be achieved by the following iterative procedure:
1. Initialize  to some value.
2. Using a standard SVM algorithm, find the maximum of the
quadratic form W:
3. Update the parameters  such that T is minimized.
This is typically achieved by a gradient step (see below).
4. Go to step 2 or stop when the minimum of T is reached.
Solving step 3 requires estimating how T varies with . We will thus
restrict ourselves to the case where K  can be dierentiated with respect
to . Moreover, we will only consider cases where the gradient of T with
respect to  can be computed (or approximated).
Note that  0 depends implicitly on  since  0 is dened as the maximum
of W . Then, if we have n kernel parameters derivative
of respect to  p is:
0 xed
Having computed the gradient r  T way of performing step 3
is to make a gradient step:
for some small and eventually decreasing ". The convergence can be improved
with the use of second order derivatives (Newton's method):
where the Laplacian operator  is dened by
In this formulation, additional constraints can be imposed through projection
of the gradient.
6 Computing the gradient
In this section, we describe the computation of the gradient (with respect to
the kernel parameters) of the dierent estimates of the generalization error.
First, for the bound R 2 =M 2 (see Theorem 1), we obtain a formulation of
the derivative of the margin (section 6.1) and of the radius (section 6.2).
For the validation error (see equation (4)), we show how to calculate the
derivative of the hyperplane parameters  0 and b (see section 6.3). Finally,
the computation of the derivative of the span bound (7) is presented in
section 6.4.
We rst begin with a useful lemma.
Suppose we are given an (n1) vector v  and an (nn) matrix
smoothly depending on a parameter . Consider the function:
where
Let
x be the the vector x where the maximum in L() is attained. Then
@
@
x:
In other words, it is possible to dierentiate L with respect to  as if  x did
not depend on . Note that this is also true if one (or both) of the constraints
in the denition of F are removed.
Proof: We rst need to express the equality constraint with a Lagrange
multiplier  and the inequality constraints with Lagrange multipliers
At the maximum, the following conditions are veried:
We have
@
@
@
(v  P   x);
where the last term can be written as follows,
@
(v  P
@
b @ x
@
Using the derivatives of the optimality conditions, namely
@
@
@
@
and the fact that either
@
@
hence
@
(v  P
and the result follows.
6.1 Computing the derivative of the margin
Note that in feature space, the separating hyperplane
has the following expansion
and it is normalized such that
min
It follows from the denition of the margin in Theorem 1 that this latter is
1=kwk. Thus we write the bound R 2 =M 2 as R 2 kwk 2 .
The previous lemma enables us to compute the derivative of kwk 2 . In-
deed, it can be shown [18]
and the lemma can be applied to the standard SVM optimization problem
(2), giving
6.2 Computing the derivative of the radius
Computing the radius of the smallest sphere enclosing the training points
can be achieved by solving the following quadratic problem [18]:
under constraints
We can again use the previous lemma to compute the derivative of the
radius:
where  0 maximizes the previous quadratic form.
6.3 Computing the derivative of the hyperplane parameters
Let us rst compute the derivative of  0 with respect to a parameter
of the kernel. For this purpose, we need an analytical formulation for  0 .
First, we suppose that the points which are not support vectors are removed
from the training set. This assumption can be done without any loss of
generality since removing a point which is not support vector does not aect
the solution. Then, the fact that all the points lie on the margin can be
| {z }
where K Y
there are n support vectors, H is a (n
matrix. The parameters of the SVMs can be written as:
We are now able to compute the derivatives of those parameters with respect
to a kernel parameter  p . Indeed, since the derivate of the inverse of a matrix
M depending on a parameter  p can be written 3
it follows that
and nally
We can easily use the result of this calculation to recover the computation
@p . Indeed, if we denote ~
~
T H~  and it turns out that:
~
@ ~
~
~
3 This inequality can be easily proved by dierentiating MM
~
6.4 Computing the derivative of the span-rule
let us consider the span value. Recall that the span of the support
vector x p is dened as the the distance between the point and the set
dened by (6). Then the value of the span can be written as:
Note that we introduced a Lagrange multiplier  to enforce the constraint
Introducing the extended vector ~
and the extended matrix
of the dot products between support vectors
~
the value of the span can be written as:
where H is the submatrix of ~
K SV with row and column p removed, and v
is the p-th column of ~
K SV .
From the fact that the optimal value of ~
is H 1 v, it follows:
The last equality comes from the following block matrix identity, known as
the \Woodbury" formula [11]
A A 2
The closed form we obtain is particularly attractive since we can compute
the value of the span for each support vector just by inverting the matrix
K SV .
Combining equation (12) and (11), we get the derivative of the span

~
@ ~
~
pp
Thus, the complexity of computing the derivative of the span-rule with
respect to a parameter  p of the kernel requires only the computation of
and the inversion of the matrix ~
K SV . The complexity of these operations
is not larger than that of the quadratic optimization problem itself.
There is however a problem in this approach: the value given by the span-
rule is not continuous. By changing smoothly the value of the parameters
, the coe-cients  p change continuously, but span S 2
does not. There is
actually a discontinuity for most support vectors when the set of support
vectors changes. This can be easily understood from equation (6): suppose
that when changing the value of the parameter from  to  + ", a point xm
is not a support vector anymore, then for all other support vectors
the set  p is going to be smaller and a discontinuity is likely to appear for
the value of S
The situation is explained in gure 2: we plotted the value of the span of
a support vector x p versus the width of an RBF kernel . Almost everywhere
the span is decreasing, hence a negative derivative, but some jumps appear,
corresponding in a change in the set of support vectors. Moreover the span
is globally increasing: the value of the derivate does not give us a good
indication of the global evolution of the span.
One way to solve is this problem is to try to smooth the behavior of
the span. This can be done by imposing the following additional constraint
in the denition of  p in equation
is a constant.
Given this constraint, if a point xm is about to leave or has just entered the
set of support vectors, it will not have a large in
uence on the span of the
other support vectors, since  0
m will be small. The eect of this constraint
is to make the set  p become \continuous" when the set of support vectors
changes.
However this new constraint prevents us from computing the span as
e-ciently as in equation (12). A possible solution is to replace the constraint
74e-376e-378e-380e-3

Figure

2: Value of
p , the sum of the span of the training points for
dierent values of the width of an RBF kernel varying in the small vicinity
by a regularization term in the computation of the span:

With this new denition of the span, equation (12) becomes:
where D is a diagonal matrix with elements
i and D
As shown on gure 3 , the span is now much smoother and its minimum is
still at the right place. In our experiments, we took
Note that computing the derivative of this new expression is no more
di-cult than the previous span expression.
It is interesting to look at the leave-one-out error for SVMs without
threshold. In this case, the value of the span with regularization writes:

As already pointed out in section 3.2.5, if the value of span is:
2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.077e-385e-393e-3
Figure

3: Left: the minima of the span with regularization (dashed line)
and without regularization (solid line) are close. Right: detailed behavior
of the span for dierent values of the regularizer,
and we recover the opper-Winther bound.
On the other hand, if
In this
case, the span bound is identical to the Jaakkola-Haussler one.
In a way, the span bound with regularization is in between the bounds
of opper-Winther and Jaakkola-Haussler.
7 Experiments
Experiments of dierent nature have been carried out to assess the performance
and feasibility of our method.
The rst set of experiments consists in nding automatically the optimal
value of two parameters: the width of an RBF kernel and the constant C in
equation (3). The second set of experiments corresponds to the optimization
of a large number of scaling factors in the case of handwritten digit
recognition. We then show that optimizing scaling factors leads naturally
to feature selection and demonstrate the application of the method to the
selection of relevant features in several databases.
7.1 Optimization details
The core of the technique we present here is a gradient descent algorithm.
We used the optimization toolbox of Matlab to perform it. It includes second
order updates to improve the convergence speed.
Cross-validation R 2 =M 2 Span-bound
Breast Cancer 26.04  4.74 26.84  4.71 25.59  4.18
Diabetis 23.53  1.73 23.25  1.7 23.19  1.67
Heart 15.95  3.26 15.92  3.18 16.13  3.11
Thyroid 4.80  2.19 4.62  2.03 4.56  1.97

Table

1: Test error found by dierent algorithms for selecting the SVM
parameters C and . The rst column reports the results from [14]. In the
second and last column, the parameters are found by minimizing R 2 =M 2
and the span-bound using a gradient descent algorithm.
7.2 Benchmark databases
In a rst set of experiments, we tried to select automatically the width  of
a RBF kernel,
along the constant C penalizing the training error appearing in equation
(3).
In order to avoid adding positivity constraints in the optimization problem
(for the constant C and the width  of the RBF kernel), we use the
parameterization turns out to give a more
stable optimization.
We used benchmark databases described in [14]. Those databases as
long as the 100 splits training /test sets are available at
http://ida.first.gmd.de/raetsch/data/benchmarks.htm.
We followed the same experimental setup as in [14]. On each of the
rst 5 training sets, the kernel parameters are estimated using either 5-fold
cross-validation, minimization of R 2 =M 2 or the span-bound. Finally, the
kernel parameters are computed as the median of the 5 estimations.
The results are shown in table 1.
It turns out that minimizing R 2 =M 2 or the span estimates yields approximately
the same performances as picking-up the parameters which minimize
the cross-validation error. This is not very surprising since cross-validation
is known to be an accurate method for choosing the hyper-parameters of
any learning algorithm.
But more interesting is to compare the computational cost of these meth-
Cross-validation R 2 =M 2 Span-bound
Breast Cancer 500 14.2 7
Diabetis 500 12.2 9.8
Heart 500 9 6.2
Thyroid 500 3 11.6
Titanic 500 6.8 3.4

Table

2: Average number of SVM trainings on one training set needed to
select the parameters C and  using standard cross-validation or by minimizing
or the span-bound.
ods.

Table

shows how many SVM trainings in average are needed to select
the kernel parameters on each split. The results for cross-validation are the
ones reported in [14]. They tried 10 dierent values for C and  and performed
5-fold cross-validation. The number of SVM trainings on each of the
5 training set needed by this method is
The gain in complexity is impressive: in average 100 times less SVM
training are required to nd the kernel parameters. The main reason for
this gain is that there were two parameters to optimize. Because of computational
reasons, exhaustive search by cross-validation can not handle the
selection of more than 2 parameters, whereas our method can, as highlighted
in the next section.
Discussion As explained in section 3.2, R 2 =M 2 can seem to be a rough
upper bound of the span-bound, which is in an accurate estimate of the test
error [3]. However in the process of choosing the kernel parameters, what
matters is to have a bound whose minimum is close to the optimal kernel
parameters. Even if R 2 =M 2 cannot be used to estimate the test error, the
previous experiments show that its minimization yields quite good results.
The generalization error obtained by minimizing the span-bound (cf gure
are just slightly better. Since the minimization of the latter is more
di-cult to implement and to control (more local minima), we recommend
in practice to minimize R 2 =M 2 . In the experiments of the following section,
we will only relate experiments with this bound, but similar results have
been obtained with the span-bound.
7.3 Automatic selection of scaling factors
In this experiment, we try to choose the scaling factors for an RBF and
polynomial kernel of degree 2. More precisely, we consider kernels of the
following
and

Most of the experiments have been carried out on the USPS handwritten
digit recognition database. This database consists of 7291 training examples
and 2007 test examples of digit images of size 16x16 pixels. We try to classify
digits 0 to 4 against 5 to 9. The training set has been split into 23 subsets of
317 examples and just of this subset has been used during the experiments.
To assess the feasibility of our gradient descent approach for nding
kernel parameters, we rst used only 16 parameters, each one corresponding
to a scaling factor for a squared tile of 16 pixels as shown on gure 4.

Figure

4: On each of the 16 tiles, the scaling factors of the 16 pixels are
identical.
The scaling parameters were initialized to 1. The evolution of the test
error and of the bound R 2 =M 2 are plotted versus the number of iterations in
the gradient descent procedure in gures 5 (polynomial kernel) and 6 (RBF
Note that for the polynomial kernel, the test error went down to 9%
whereas the best test error with only one scaling parameter is 9.9%. Thus,

Figure

5: Evolution of the test error (left) and of the bound R 2 =M 2 (right)
during the gradient descent optimization with a polynomial kernel

Figure

Evolution of the test error (left) and of the bound R 2 =M 2 (right)
during the gradient descent optimization with an RBF kernel
by taking several scaling parameters, we managed to make the test error
decrease.
It might be interesting to see which scaling coe-cients have been found.
For this purpose, we took 256 scaling parameters (one per pixel) and minimized
with a polynomial kernel. The map of the scaling coe-cient
is shown in gure 7.
The result is quite consistent with one could expect in situation: the
coe-cients near the border of the picture are smaller than those in the
middle of the picture, so that these coe-cients can be directly interpreted
as measures of the relevance of the corresponding feature.

Figure

7: Scaling factors found by the optimization procedure: darker means
smaller scaling factor
Discussion This experiment can be considered as a sanity check experi-
ment. Indeed, it proves it is feasible to choose multiple kernel parameters
of an SVM and that it does not lead to overtting. However, the gain in
test error was not our main motivation since we did not expect any signi-
cant improvement on such a problem where most features play a similar role
(taking all scaling factors equal on this database seems a reasonable choice).
However as highlighted by gure 7, this method can be a powerful tool to
perform feature selection.
8 Feature selection
The motivation for feature selection is three-fold:
1. Improve generalization error
2. Determine the relevant features (for explanatory purposes)
3. Reduce the dimensionality of the input space (for real-time applications

Finding optimal scaling parameters can lead to feature selection algo-
rithms. Indeed, if one of the input components is useless for the classica-
tion problem, its scaling factor is likely to become small. But if a scaling
becomes small enough, it means that it is possible to remove it without
aecting the classication algorithm. This leads to the following idea
for feature selection: keep the features whose scaling factors are the largest.
This can also be performed in a principal components space where we scale
each principal component by a scaling factor.
We consider two dierent parametrization of the kernel. The rst one
correspond to rescaling the data in the input space:
where  2 R n .
The second one corresponds to rescaling in the principal components
space:
where  is the matrix of principal components.
We compute  and  using the following iterative procedure:
1. Initialize
2. In the case of principal component scaling, perform
principal component analysis to compute the matrix .
3. Solve the SVM optimization problem
4. Minimize the estimate of the error T with respect to
with a gradient step
5. Discard dimensions corresponding to small elements in
and return to step 2.
We demonstrate this idea on two toy problems where we show that feature
selection reduces generalization error. We then apply our feature selection
algorithm to DNA Micro-array data where it is important to nd
which genes are relevant in performing the classication. It also seems in
these types of algorithms feature selection improves performance. Lastly, we
apply the algorithm to face detection and show that we can greatly reduce
the input dimension without sacricing performance.
8.1 Toy data
We compared several algorithms
The standard SVM algorithm with no feature selection
Our feature selection algorithm with the estimate R 2 =M 2 and with
the span estimate
The standard SVM applied after feature selection via a lter method
The three lter methods we used choose the m largest features according
to: Pearson correlation coe-cients, the Fisher criterion score 4 , and the
Kolmogorov-Smirnov test 5 . Note that the Pearson coe-cients and Fisher
criterion cannot model nonlinear dependencies.
In the two following articial datasets our objective was to assess the
ability of the algorithm to select a small number of target features in the
presence of irrelevant and redundant features [21].
For the rst example, six dimensions of 202 were relevant. The probability
of equal. The rst three features were drawn
as and the second three features fx 4 were drawn as
a probability of 0:7, otherwise the rst three were drawn
as and the second three as x 1). The remaining
features are noise x
For the second example, two dimensions of 52 were relevant. The probability
of equal. The data are drawn from the following: if
are drawn from N(
ability,
are drawn again from two normal distributions with equal probability, with
and the same  as before. The rest of the
features are noise x
In the linear problem the rst six features have redundancy and the rest
of the features are irrelevant. In the nonlinear problem all but the rst two
features are irrelevant.
We used a linear kernel for the linear problem and a second order polynomial
kernel for the nonlinear problem.
We imposed the feature selection algorithms to keep only the best two
features. The results are shown in gure (8) for various training set sizes,
taking the average test error on 500 samples over runs of each training
set size. The Fisher score (not shown in graphs due to space constraints)
performed almost identically to correlation coe-cients.
In both problem, we clearly see that our method outperforms the other
classical methods for feature selection. In the nonlinear problem, among the
r
, where
r is the mean value for the r-th feature in the positive
and negative classes and
ris the standard deviation
5 KS tst
where fr denotes the r-th
feature from each training example, and ^
P is the corresponding empirical distribution.
lter methods only the Kolmogorov-Smirnov test improved performance over
standard SVMs.
RW-Bound & Gradient
Standard SVMs
Correlation Coefficients
Kolmogorov-Smirnov Test
RW-Bound & Gradient
Standard SVMs
Correlation Coefficients
Kolmogorov-Smirnov Test
(a) (b)

Figure

8: A comparison of feature selection methods on (a) a linear problem
and (b) a nonlinear problem both with many irrelevant features. The x-axis
is the number of training points, and the y-axis the test error as a fraction
of test points.
8.2 DNA Microarray Data
Next, we tested this idea on two leukemia discrimination problems [6] and a
problem of predicting treatment outcome for Medulloblastoma [1]. The rst
problem was to classify myeloid versus lymphoblastic leukemias based on
the expression of 7129 genes. The training set consists of 38 examples and
the test set 34 examples. Standard linear SVMs achieve 1 error on the test
set. Using gradient descent on R 2
we achieved an error of 0 using
and an error of 1 using 1 gene. Using the Fisher score to select features
resulted in 1 error for both 1 and genes.
The second leukemia classication problem was discriminating B versus
T cells for lymphoblastic cells [6]. Standard linear SVMs makes 1 error for
this problem. Using either the span bound or gradient descent on R 2
results
in 0 errors made using 5 genes. Using the Fisher score results in 2 errors
made using 5 genes.
The nal problem is one of predicting treatment outcome of patients
that have Medulloblastoma. Here there are 60 examples each with 7129 expression
values in the dataset and we use leave-one-out to measure the error
rate. A standard SVM with a Gaussian kernel makes 24 errors, selecting
genes using the gradient descent on R 2
we achieved an error of 15.
8.3 Face detection
The trainable system for detecting frontal and near-frontal views of faces in
gray images presented in [7] gave good results in terms of detection rates.
The system used gray values of 1919 images as inputs to a second-degree
polynomial kernel SVM. This choice of kernel lead to more than 40,000 features
in the feature space. Searching an image for faces at dierent scales
took several minutes on a PC. To make the system real-time reducing the
dimensionality of the input space and the feature space was required. The
feature selection in principal components space was used to reduce the dimensionality
of the input space [15].
The method was evaluated on the large CMU test set 1 consisting of 479
faces and about 57,000,000 non-face patterns. In Figure 9, we compare the
ROC curves obtained for dierent numbers of selected components.
The results showed that using more than 60 components does not improve
the performances of the system [15].

Figure

9: ROC curves for dierent number of PCA gray features.
9 Conclusion
We proposed an approach for automatically tuning the kernel parameters
of an SVM. This is based on the possibility of computing the gradient of
various bounds on the generalization error with respect to these parame-
ters. Dierent techniques have been proposed to smooth these bounds while
preserving their accuracy in predicting the location of the minimum of test
error. Using these smoothed gradients we were able to perform a gradient
descent to search the kernel parameter space, leading to both an improvement
of the performance and a reduction of the complexity of the solution
(feature selection). Using this method, we chose in the separable case appropriate
scaling factors. In the non separable case, this method allows us
to choose simultaneously scaling factors and parameter C (see equation 3).
The benets of this technique are many. First it allows to actually
optimize a large number of parameters while previous approaches only could
deal with 2 parameters at most. Even in the case of a small number of
parameters, it improves the running time by a large amount. Moreover
experimental results have demonstrated that an accurate estimate of the
error is not required and that a simple estimate like R 2 =M 2 has a very good
behaviour in terms of allowing to nd the right parameters. In a way this
renders the technique even more applicable since this estimate is very simple
to compute and derive. Finally, this approach avoids holding out some data
for validation and thus makes full use of the training set for the optimization
of parameters, contrary to cross-validation methods.
This approach and the fact that it has be proven successful in various
situation opens new directions of research in the theory and practice of Support
Vector Machines. On the practical side, this approach makes possible
the use of highly complex and tunable kernels, the tuning of scaling factors
for adapting the shape of the kernel to the problem and the selection of
relevant features. On the theoretical side, it demonstrates that even when
a large number of parameter are simultaneously tuned the overtting eect
remains low.
Of course a lot of work remains to be done in order to properly understand
the reasons. Another interesting phenomenon is the fact that the
quantitative accuracy of the estimate used for the gradient descent is only
marginally relevant. This raises the question of how to design good estimates
for parameter tuning rather than accurate estimates.
Future investigation will focus on trying to understand these phenomena
and obtain bounds on the generalization error of the overall algorithm, along
with looking for new problems where this approach could be applied as well
as new applications.

Acknowledgments

The authors would like to thank Jason Weston and
Elodie Nedelec for helpful
comments and discussions.



--R

Medulloblastoma diagnosis and outcome prediction by gene expression pro

Model selection for support vector ma- chines
Support vector networks.
Dynamically adapting kernels in support vector machines.

Face detection in still gray images.
Probabilistic kernel regression models.
Adaptive regularization in neural network modeling.
On estimation of characters obtained in statistical procedure of recognition.

Gaussian processes and svm: Mean
Probabilities for support vector machines.

Feature selection for face detection.
Robust bounds on generalization from the margin distribution.
The Nature of Statistical Learning Theory.
Statistical Learning Theory.
Bounds on error expectation for support vector machines.
Generalized approximate cross-validation for support vector machines : another way to look at margin- like quantities
Feature selection for support vector machines.
--TR

--CTR
Alex D. Holub , Max Welling , Pietro Perona, Hybrid Generative-Discriminative Visual Categorization, International Journal of Computer Vision, v.77 n.1-3, p.239-258, May       2008
Dit-Yan Yeung , Hong Chang , Guang Dai, Learning the kernel matrix by maximizing a KFD-based class separability criterion, Pattern Recognition, v.40 n.7, p.2021-2028, July, 2007
Tobias Glasmachers , Christian Igel, Gradient-Based Adaptation of General Gaussian Kernels, Neural Computation, v.17 n.10, p.2099-2105, October 2005
Kristin P. Bennett , Michinari Momma , Mark J. Embrechts, MARK: a boosting algorithm for heterogeneous kernel models, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Yoram Baram, Learning by Kernel Polarization, Neural Computation, v.17 n.6, p.1264-1275, June 2005
Carl Gold , Alex Holub , Peter Sollich, Bayesian approach to feature selection and parameter tuning for support vector machine classifiers, Neural Networks, v.18 n.5-6, p.693-701, June 2005
Koji Tsuda , Shinsuke Uda , Taishin Kin , Kiyoshi Asai, Minimizing the Cross Validation Error to Mix Kernel Matrices of Heterogeneous Biological Data, Neural Processing Letters, v.19 n.1, p.63-72, February 2004
Carlos Soares , Pavel B. Brazdil, Selecting parameters of SVM using meta-learning and kernel matrix-based meta-features, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
Tristrom Cooke, Two Variations on Fisher's Linear Discriminant for Pattern Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.268-273, February 2002
Carlos Soares , Pavel B. Brazdil , Petr Kuba, A Meta-Learning Method to Select the Kernel Width in Support Vector Regression, Machine Learning, v.54 n.3, p.195-209, March 2004
Sayan Mukherjee , Qiang Wu, Estimation of Gradients and Coordinate Covariation in Classification, The Journal of Machine Learning Research, 7, p.2481-2514, 12/1/2006
Alain Rakotomamonjy, Variable selection using svm based criteria, The Journal of Machine Learning Research, 3, 3/1/2003
Malte Kuss , Carl Edward Rasmussen, Assessing Approximate Inference for Binary Gaussian Process Classification, The Journal of Machine Learning Research, 6, p.1679-1704, 12/1/2005
Keith M. Sullivan , Sean Luke, Evolving kernels for support vector machine classification, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Mingrui Wu , Bernhard Schlkopf , Gkhan Bakir, Building Sparse Large Margin Classifiers, Proceedings of the 22nd international conference on Machine learning, p.996-1003, August 07-11, 2005, Bonn, Germany
Andreas Argyriou , Raphael Hauser , Charles A. Micchelli , Massimiliano Pontil, A DC-programming algorithm for kernel selection, Proceedings of the 23rd international conference on Machine learning, p.41-48, June 25-29, 2006, Pittsburgh, Pennsylvania
Huseyin Ince , Theodore B. Trafalis, A hybrid model for exchange rate prediction, Decision Support Systems, v.42 n.2, p.1054-1062, November 2006
Sayan Mukherjee , Ding-Xuan Zhou, Learning Coordinate Covariances via Gradients, The Journal of Machine Learning Research, 7, p.519-549, 12/1/2006
Mingrui Wu , Bernhard Schlkopf , Gkhan Bakr, A Direct Method for Building Sparse Kernel Learning Algorithms, The Journal of Machine Learning Research, 7, p.603-624, 12/1/2006
Liefeng Bo , Ling Wang , Licheng Jiao, Feature Scaling for Kernel Fisher Discriminant Analysis Using Leave-One-Out Cross Validation, Neural Computation, v.18 n.4, p.961-978, April 2006
Alain Rakotomamonjy , Francis Bach , Stphane Canu , Yves Grandvalet, More efficiency in multiple kernel learning, Proceedings of the 24th international conference on Machine learning, p.775-782, June 20-24, 2007, Corvalis, Oregon
Xue-wen Chen , Jong Cheol Jeong, Minimum reference set based feature selection for small sample classifications, Proceedings of the 24th international conference on Machine learning, p.153-160, June 20-24, 2007, Corvalis, Oregon
Training algorithms for fuzzy support vector machines with noisy data, Pattern Recognition Letters, v.25 n.14, p.1647-1656, 15 October 2004
Francis R. Bach , Gert R. G. Lanckriet , Michael I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Proceedings of the twenty-first international conference on Machine learning, p.6, July 04-08, 2004, Banff, Alberta, Canada
R. Kumar , A. Kulkarni , V. K. Jayaraman , B. D. Kulkarni, Symbolization assisted SVM classifier for noisy data, Pattern Recognition Letters, v.25 n.4, p.495-504, March 2004
Sren Sonnenburg , Gunnar Rtsch , Christin Schfer , Bernhard Schlkopf, Large Scale Multiple Kernel Learning, The Journal of Machine Learning Research, 7, p.1531-1565, 12/1/2006
Kai-Quan Shen , Chong-Jin Ong , Xiao-Ping Li , Einar P. Wilder-Smith, Feature selection via sensitivity analysis of SVM probabilistic outputs, Machine Learning, v.70 n.1, p.1-20, January   2008
Zhihua Zhang , James T. Kwok , Dit-Yan Yeung, Model-based transductive learning of the kernel matrix, Machine Learning, v.63 n.1, p.69-101, April     2006
Kai-Min Chung , Wei-Chun Kao , Chia-Liang Sun , Li-Lun Wang , Chih-Jen Lin, Radius margin bounds for support vector machines with the RBF kernel, Neural Computation, v.15 n.11, p.2643-2681, November
Ming-Wei Chang , Chih-Jen Lin, Leave-One-Out Bounds for Support Vector Regression Model Selection, Neural Computation, v.17 n.5, p.1188-1222, May 2005
Keem Siah Yap , Izham Z. Abidin , Abdul Rahim Ahmad , Zahrul Faizi Hussien , Hooi Loong Pok , Fariq Izwan Ismail , Abdul Malik Mohamad, Abnormalities and fraud electric meter detection using hybrid support vector machine & genetic algorithm, Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology, p.388-392, April 02-04, 2007, Phuket, Thailand
Olivier Chapelle, Training a Support Vector Machine in the Primal, Neural Computation, v.19 n.5, p.1155-1178, May 2007
Guang Dai , Dit-Yan Yeung, Kernel selection forl semi-supervised kernel machines, Proceedings of the 24th international conference on Machine learning, p.185-192, June 20-24, 2007, Corvalis, Oregon
Yiming Ying , Ding-Xuan Zhou, Learnability of Gaussians with Flexible Variances, The Journal of Machine Learning Research, 8, p.249-276, 5/1/2007
Christian Igel , Tobias Glasmachers , Britta Mersch , Nico Pfeifer , Peter Meinicke, Gradient-Based Optimization of Kernel-Target Alignment for Sequence Kernels Applied to Bacterial Gene Start Detection, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.2, p.216-226, April 2007
Lior Wolf , Amnon Shashua, Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach, The Journal of Machine Learning Research, 6, p.1855-1887, 12/1/2005
Baback Moghaddam , Ming-Hsuan Yang, Learning Gender with Support Faces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.707-711, May 2002
A. Rakotomamonjy, Analysis of SVM regression bounds for variable ranking, Neurocomputing, v.70 n.7-9, p.1489-1501, March, 2007
Yi Wu , Edward Y. Chang, Distance-function design and fusion for sequence data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Abdul Majid , Asifullah Khan , Anwar M. Mirza, Combination of support vector machines using genetic programming, International Journal of Hybrid Intelligent Systems, v.3 n.2, p.109-125, January 2006
Qiang Wu , Yiming Ying , Ding-Xuan Zhou, Multi-kernel regularized classifiers, Journal of Complexity, v.23 n.1, p.108-134, February, 2007
Shin Ando , Hitoshi Iba, Classification of Gene Expression Profile Using Combinatory Method of Evolutionary Computation and Machine Learning, Genetic Programming and Evolvable Machines, v.5 n.2, p.145-156, June 2004
Giorgio Valentini , Thomas G. Dietterich, Bias-Variance Analysis of Support Vector Machines for the Development of SVM-Based Ensemble Methods, The Journal of Machine Learning Research, 5, p.725-775, 12/1/2004
Fabien Lauer , Ching Y. Suen , Grard Bloch, A trainable feature extractor for handwritten digit recognition, Pattern Recognition, v.40 n.6, p.1816-1824, June, 2007
R. Brunelli, verification through finger matching: A comparison of Support Vector Machines and Gaussian Basis Functions classifiers, Pattern Recognition Letters, v.27 n.16, p.1905-1915, December, 2006
R. Brunelli, verification through finger matching: a comparison of support vector machines and Gaussian basis functions classifiers, Pattern Recognition Letters, v.27 n.16, p.1905-1915, December 2006
Gavin C. Cawley , Nicola L. C. Talbot, Constructing Bayesian formulations of sparse kernel learning methods, Neural Networks, v.18 n.5-6, p.674-683, June 2005
Gavin C. Cawley , Nicola L. C. Talbot, Fast exact leave-one-out cross-validation of sparse least-squares support vector machines, Neural Networks, v.17 n.10, p.1467-1475, December 2004
Piyush Kumar , Joseph S. B. Mitchell , E. Alper Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, Journal of Experimental Algorithmics (JEA), 8,
Saher Esmeir , Shaul Markovitch, Anytime Learning of Decision Trees, The Journal of Machine Learning Research, 8, p.891-933, 5/1/2007
Sbastien Gadat , Laurent Younes, A Stochastic Algorithm for Feature Selection in Pattern Recognition, The Journal of Machine Learning Research, 8, p.509-547, 5/1/2007
K. Pelckmans , J. A. Suykens , B. Moor, Additive Regularization Trade-Off: Fusion of Training and Validation Levels in Kernel Methods, Machine Learning, v.62 n.3, p.217-252, March     2006
Gavin C. Cawley , Nicola L. C. Talbot, Preventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters, The Journal of Machine Learning Research, 8, p.841-861, 5/1/2007
Mathias M. Adankon , Mohamed Cheriet, Optimizing resources in model selection for support vector machine, Pattern Recognition, v.40 n.3, p.953-963, March, 2007
Mingkun Li , Ishwar K. Sethi, Confidence-based classifier design, Pattern Recognition, v.39 n.7, p.1230-1240, July, 2006
Ataollah Abrahamzadeh , Seyed Alireza Seyedin , Mehdi Dehghan, Digital-signal-type identification using an efficient identifier, EURASIP Journal on Applied Signal Processing, v.2007 n.1, p.63-63, 1 January 2007
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
Zexuan Zhu , Yew-Soon Ong , Manoranjan Dash, Markov blanket-embedded genetic algorithm for gene selection, Pattern Recognition, v.40 n.11, p.3236-3248, November, 2007
support vector machines;gradient descent;leave-one-out procedure;kernel selection;feature selection