Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces.
We examine methods for constructing regression ensembles based on a linear program (LP). The ensemble regression function consists of linear combinations of base hypotheses generated by some boosting-type base learning algorithm. Unlike the classification case, for regression the set of possible hypotheses producible by the base learning algorithm may be infinite. We explicitly tackle the issue of how to define and solve ensemble regression when the hypothesis space is infinite. Our approach is based on a semi-infinite linear program that has an infinite number of constraints and a finite number of variables. We show that the regression problem is well posed for infinite hypothesis spaces in both the primal and dual spaces. Most importantly, we prove there exists an optimal solution to the infinite hypothesis space problem consisting of a finite number of hypothesis. We propose two algorithms for solving the infinite and finite hypothesis problems. One uses a column generation simplex-type algorithm and the other adopts an exponential barrier approach. Furthermore, we give sufficient conditions for the base learning algorithm and the hypothesis set to be used for infinite regression ensembles. Computational results show that these methods are extremely promising.
Introduction
The past years have seen strong interest in boosting and other ensemble
learning algorithms due to their success in practical classication applications
(e.g. Drucker et al., 1993; LeCun et al., 1995; Maclin & Opitz,
1997; Schwenk & Bengio, 1997; Bauer & Kohavi, 1999; Dietterich,
1999). The basic idea of boosting (and ensemble learning in general)
is to iteratively generate a sequence fh t g T
t=1 of functions (hypotheses)
that are usually combined as
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
regression.tex; 15/01/2001; 20:26; p.1
Yoshua Bengio and Dale Schuurmans (none:kluwer) v.1.3
G. Ratsch, A. Demiriz and K.P. Bennett
are the hypothesis coe-cients used. The hypotheses
h t are elements of a hypothesis class
where P is the index set of hypotheses producible by a base learning
algorithm L. Typically one assumes that the set of hypotheses H is -
nite, but we will also consider extensions to innite hypothesis sets. For
classication, the ensemble generates the label by sign(f  (x)), which is
the weighted majority of the votes. For regression, the predicted value
is f  (x).
Recent research in this eld has focused on the better understanding
of these methods and on extensions that are concerned with robustness
issues (Mason et al., 1998; Bennett et al., 2000; Ratsch et al., 2000b,
2001). It has been shown that most classication ensemble methods can
be viewed as minimizing some function of the classication margin.
Typically this is performed algorithmically using a gradient descent
approach in function space. Recently, it has been shown that the soft
margin maximization techniques utilized in support vector machines
can be readily adapted to produce ensembles for classication (Ben-
nett et al., 2000; Ratsch et al., 2000b). These algorithms optimize
the soft margin and error measures originally proposed for support
vector machines. For certain choices of error and margin norms, the
problem can be formulated as a linear program (LP). At rst glance,
the LP may seem intractable since the number of variables in the linear
program is proportional to the size of the hypothesis space which can
be exponentially large. But in fact, two practical algorithms exist for
optimizing soft margin ensembles. The rst uses column generation in a
simplex algorithm (Bennett et al., 2000). The second uses barrier functions
in an interior-point method (Ratsch et al., 2000). The advantage
of these linear programming approaches is that they produce sparse
ensembles using fast nite algorithms. The purpose of this work is to
tackle regression ensembles using the analogous support vector linear
programming methodology for regression.
To date, relatively few papers have addressed ensembles for regression
Zemel & Pitassi, 2001). One major di-culty is rigorously dening the
regression problem in an innite hypothesis space. For classication
assuming each hypothesis has a nite set of possible outputs, the hypothesis
space is always nite since there are only a nite number of
ways to label any nite training set. For regression, even relatively
simple hypothesis spaces, such as linear functions constructed using
weighted least squares, consist of an uncountable innite set of hypothe-
ses. It is not a priori clear how to even express a regression problem in
an innite hypothesis space. Clearly we can only practically consider
Sparse Regression Ensembles 3
ensemble functions that are a linear combination of some nite subset
of the set of possible hypotheses.
In this work, we study directly the issue of innite hypothesis spaces.
We begin in Section 2 with a review of boosting type algorithms for
classication and regression and examine the relationship between ensemble
methods and linear programming. In Section 3, we review a
linear program approach to sparse regression and show how it is easily
extendible to ensemble regression for the nite hypothesis case. In
Section 3.2 we investigate the dual of this linear program for ensemble
regression. In Section 3.3, we propose a semi-innite linear program
formulation for \boosting" of innite hypothesis sets, rst in the dual
and then in the primal space. The dual problem is called semi-innite
because it has an innite number of constraints and a nite number
of variables. An important sparseness property of the semi-innite regression
problem is that it has a solution consisting of a nite number
of hypotheses. In Section 4, we propose two dierent algorithms for
e-ciently computing optimal ensembles. The exact implementation of
these algorithms is dependent on the choice of base learning algorithms.
In Section 4.3 we investigate three possible base learning algorithms
that result in both innite and nite hypothesis sets. Computational
results are presented in Section 5.
The notational conventions used in this paper can be found in Table I.

Table

I. Notational conventions
n; N counter and number of patterns
counter and number of hypotheses if nite
t; T counter and number of iterations
index-set for hypotheses
space, dimensionality of X
training data: input, targets, both
y a training pattern and the label
set of base hypotheses and an element of H
set of linear combinations of H and element of F
hypothesis weight vector
d weighting on the training set
w a weight vector for linear models
I() the indicator function:
" the tube size
the tube parameter (determines ")
C the regularization (complexity) parameter
weighted classication error
k  kp the 'p-norm,
product and scalar product in feature space
4 G. Ratsch, A. Demiriz and K.P. Bennett
2. Boosting-type Algorithms
We brie
y review and discuss existing boosting-type algorithms. In
Section 2.1 we start with the classication case and describe AdaBoost
closely related, Arc-GV (Breiman,
1997). Then we discuss properties of the solutions generated by boosting
and show connections to a linear program (LP) for maximizing
the margins. In Section 2.2 we brie
y review some recent regression
approaches that are mainly motivated from a gradient-descent understanding
of Boosting.
2.1. Classification Boosting and LP
For the classication case, it is generally assumed the hypotheses class
dened by a base learning
algorithm L. In each iteration the base learner is used to select the
next hypothesis using certain criteria. The ensemble generates the label
which is the weighted majority of the votes by sign(f  (x)). Note that
the hypothesis class is always nite because there at most 2 N distinct
labelings of the training data.
Consider the AdaBoost algorithm. For more details see e.g. (Freund
1997). The main idea of AdaBoost is to
introduce weights d n on the training patterns Z :=
)g. They are used to control the importance of
each single pattern for learning a new hypothesis (i.e., while repeatedly
running the base algorithm). Training patterns that are di-cult to
learn (which are misclassied repeatedly) become more important by
increasing their weight.
It has been shown that AdaBoost minimizes an error function
(Breiman, 1997; Frean & Downs, 1998; Friedman et al., 1998; Ratsch
et al., 2001) that can be expressed in terms of margins, namely it
iteratively solves the problem
min
with   0
The optimization strategy of AdaBoost has also been called \gradient
descent" in function space (Mason et al., 1999; Friedman et al., 1998),
as one eectively optimizes along restricted gradient directions in the
space of linearly combined functions f . This can also be understood as
a coordinate descent method (e.g. Luenberger, 1984) to minimize G()
over all possible weightings of hypotheses from H (Ratsch et al., 2000).
One hypothesis is added at a time and its weight is never changed
unless the same hypothesis is added again.
Sparse Regression Ensembles 5
It is widely believed (Breiman, 1997; Freund & Schapire, 1996;
Schapire et al., 1997; Ratsch et al., 2001, 2001) that AdaBoost approximately
maximizes the smallest margin, %
on the training set. This problem can be solved exactly by the following
linear programming problem over the complete hypothesis set H
(cf. Grove and Schuurmans (1998), assuming a nite number of basis
with y n f
(1)
Breiman (1997) proposed a modication of AdaBoost { Arc-GV {
making it possible to show the asymptotic convergence of %( t
1) to a global solution % lp of (1). In Grove and Schuurmans (1998)
the LP (1) was solved using an iterative linear programming based
approach that retrospectively can be considered as a column generation
algorithm. Unfortunately, neither approach performed well in practice.
margin versions of this linear program based on ideas from
support vector machines perform very well both in practice and theoretically
in terms of generalization bounds (Ratsch et al., 2000b; Bennett
et al., 2000). For example, a soft margin version could be
with y n f
In Bennett et al. (2000) the column generation algorithm for classication
was proposed to e-ciently solve these LPs. This algorithm
and those closely related in Ratsch et al. (2001), Kivinen and Warmuth
(1999) dier from the gradient-boosting idea used to motivate
boosting-type algorithms (Mason et al., 1999; Friedman et al., 1998).
At each iteration, all generated hypothesis weights are optimized with
respect to a maximum margin error function. The gradient approach
xes hypothesis weights as the hypotheses are generated. The purpose
of this paper is to examine the extensions of these approaches to the
regression case.
6 G. Ratsch, A. Demiriz and K.P. Bennett
2.2. Previous Regression Approaches
Several regression boosting methods have been proposed. We provide a
brief description of three of them. Note that the rst two described here
and also those of (Fisher, 1997; G. Ridgeway, 1999) reduce the problem
to a series of classication tasks, thus eliminating any consideration of
innite hypothesis spaces. The last approach (Friedman, 1999) has been
applied to innite hypothesis spaces, but does not dene what it means
to boost in an innite hypothesis space.
2.2.1. AdaBoost-R:
The rst boosting-type algorithm for regression { AdaBoost.R { was
proposed in Freund and Schapire (1994). It is based on a reduction to
the classication case. The algorithm aims to nd a regression function
problem with this algorithm is that it uses a piece-wise
linear function on [0; 1] whose number of branch-points increases
exponentially with the number of iterations. Therefore, the algorithm
is computationally intractable.
2.2.2. AdaBoost-R:
Another reduction for nding f : x 7! [0; 1] to the classication case
was proposed in Bertoni et al. (1997). Here, a pattern that is predicted
with error less than some  > 0 is counted as correctly classied and
as misclassied otherwise. The combined regression function is given
by
Again, a probability weighting d on the training patterns is used.
Under the assumption that the weighted \classication error"
in each iteration is smaller than 1
> 0), the number of training patterns for which jf(x n ) y
converges quickly to zero. From our experience it turned out that (i) the
choice of  is rather di-cult and (ii) the selection of the next hypothesis
by the base learner is a demanding problem, as the weighted error
usually converges quickly to 1
2 and the algorithm has to stop.
2.2.3. Gradient Boosting for Regression (Friedman, 1999):
Based on the understanding of boosting as a gradient descent method,
other regression algorithms have been proposed { e.g. in the very interesting
paper of Friedman (Friedman, 1999). Here, the derivative @G
of a cost function G (e.g. squared loss:
with respect to the output f(x n ) of the regression function. Then the
Sparse Regression Ensembles 7
projected gradient direction (a basis function h 2 H) that is most in
the direction of the true gradient is found by
@G
This idea has been worked out for squared loss, linear absolute loss, and
Huber's loss. However, the gradient direction found in (2) is optimal
for the squared loss only. For the linear absolute loss, this has been
specialized to the Tree-Boost algorithm (Friedman, 1999). Here, the
task of nding the next hypothesis is posed as a classication problem,
where the sign of the gradient determines the class membership. In this
algorithm, the aim is to maximize the correlation between the gradient
and the output of the base hypothesis. This approach is similar to the
algorithm proposed in Section 4.3.3.
This approach works well in practice. It does not explicitly deal with
the innite hypothesis case. Like all gradient descent algorithms it oers
convergence only in the limit { even for nite hypothesis spaces. Since
regularization is not used, it can potentially overt so development of
good stopping criteria is essential. In the next section, we will develop
an alternative approach based on linear programming. The advantages
of the LP approach include extensibility to the innite hypothesis case,
sparse solution, guarantee of the existence of sparse nite solutions,
and practical fast nite algorithms.
3. Linear Programs for Regression
In this section, we develop nite and semi-innite LP formulations for
the sparse ensemble regression. We begin with the primal LP for the
nite case, then investigate the dual nite LP. Then we extend this to
the dual and primal innite hypothesis cases.
3.1. Finite Sparse Linear Regression
R be some i.i.d. (training) data. The
regression problem is often stated as nding a function f  2
that minimizes the regularized risk functional (Vapnik, 1995;
R[f ]; (3)
8 G. Ratsch, A. Demiriz and K.P. Bennett
where l() is a loss function, P[] a regularization operator, and C the
regularization parameter, determining the trade-o between loss and
complexity (i.e., size of the function class).
In this paper we consider the well-known "-insensitive loss (Vapnik,
1995; Scholkopf et al., 1999) as loss function:
This does not penalize errors below some "  0, chosen a priori. It has
been shown to have several nice properties { as we will see later (cf.
Smola, 1998). However, in principle the analysis and algorithms also
work for other loss functions (cf. Ratsch, 2001).
In this paper we consider F to be the space of linear combinations
of base hypotheses of another space H { the so-called base hypothesis
space { including a bias, i.e.
f
Here we assume H has a nite number of hypotheses (J of them).
This will be generalized to innite hypothesis classes in Sections 3.3
and 3.4. Throughout the paper we assume that H is closed under
complementation Hence, one may enforce
eectively changing F .
Let us consider the ' 1 -norm of the hypothesis coe-cients as a regularization
Using (4), minimizing (3)
can be stated as a linear program, which we call the LP-Regression
problem:
min
with y n f
as in (5) and "  0 is a xed constant.
The regularization operator jjjj 1 is frequently used in sparse favoring
approaches, e.g. basis pursuit (Chen et al., 1995) and parsimonious
least norm approximation (Bradley et al., 1998). Roughly speaking, a
reason for the induced sparseness is the fact that vectors far from the
coordinate axes are \larger" with respect to the ' 1 -norm than with
respect to p-norms with p > 1. For example, consider the vectors (1;
and (1=
2). For the two norm,
Sparse Regression Ensembles 9
but for the ' 1 -norm,
2. Note that
using the ' 1 -norm as regularizer the optimal solution is always a vertex
solution (or can be expressed as such) and tends to be very sparse. It
can easily be shown (cf. Corollary 4) that independent of the size of a
(nite) hypothesis space H, the optimal number of hypotheses in the
ensemble is not greater than the number of samples. The optimization
algorithms proposed in Section 4 exploit this property.
A nice property of (6) is that its solution is robust with respect to
small changes of the training data:
Proposition 1 (Smola et al. (1999)). Using Linear Programming
Regression with the "-insensitive loss function (4), local movements of
target values of points inside and outside (i.e. not on the edge of) the
"-tube do not in
uence the regression.
The parameter " in (6) is usually di-cult to control (Muller et al.,
1997; Scholkopf et al., 2000), as one usually does not know beforehand
how accurately one is able to t the curve. This problem is partially
resolved in the following optimization problem (Smola et al., 1999) for
min

with y n f
The dierence between (6) and (7) lies in the fact that " has become a
positively constrained variable of the optimization problem itself. The
core aspect of (7) can be captured in the proposition stated below.
Proposition 2 (Smola et al. (1999)). Assume " > 0. The following
statements hold:
(i)  is an upper bound on the fraction of errors (i.e. points outside
the " tube).
(ii)  is a lower bound on the fraction of points not inside (i.e. outside
or on the edge of) the " tube.
(iii) Suppose the data were generated i.i.d. from a distribution P (x;
ically,  equals both the fraction of points not inside the tube and
the fraction of errors.
G. Ratsch, A. Demiriz and K.P. Bennett
Summarizing, the optimization problem (7) has two parameters: (i)
the regularization parameter C, which controls the size of the hypothesis
set and therefore the complexity of the regression function, and (ii)
the tube-parameter , which directly controls the fraction of patterns
outside the "-tube and indirectly controls the size of the "-tube.
3.2. Dual Finite LP Formulation
In this section we state the dual optimization problem of (7) by introducing
Lagrangian multipliers d n for the rst constraint which computes
the error if the target is underestimated, and d
n which the error
measures if the target is overestimated. See any linear programming
text book for specics on how to construct a dual LP problem.
The dual problem of (7) is
d;d
with
where the constraint
comes from the reparameterization
of " with . Here, we have 2N xed constraints and
J := jHj constraints, one for each hypothesis h 2 H. At optimality
for each point, the quantity p
n denes an error residual.
By complementarity, we know that if the "-error is zero (that is if
If the point is underesti-
if the
point is overestimated, f
Thus the point is within the -tube, p n > 0 when the
point falls below the -tube, and p n < 0 if the point falls above the
-tube. The magnitude of p n re
ects the sensitivity of the objective to
changes in . The larger the change in error, the larger p n . The quantity
in the constraints
re
ects how well the hypothesis
addressed the residual errors. If
positive and large
in size then the hypothesis will be likely to improve the ensemble. But
it must be su-ciently large to oset the penalty for increasing kk 1 .
3.3. Generalization to Infinite Hypotheses
Consider now the case where there is an innite set of possible hypotheses
H. Say we select any nite subset H 1 of H, then the primal and
dual regression LPs on H 1 are well dened. Now say we increase the
Sparse Regression Ensembles 11
subset size and dene H 2  H 1 of H. What is the relationship between
the optimal ensembles created on the two subsets? A solution of the
smaller H 1 LP is always primal feasible for the larger H 2 LP. If the H 1
solution is dual feasible for the larger H 2 LP, then the solution is also
optimal for the problem H 2 . So dual feasibility is the key issue. Dene
the base learning algorithm L for a xed p as
If
dual feasibility is
violated; h p is a good hypothesis that should be added to the ensemble,
and the solution may not be optimal.
By thinking of h as a function of as in (9),
we can extend the dual problem (8) to the innite hypotheses case. The
set of dual feasible values of p is equivalent to the following compact
polyhedron:
The dual SILP-regression problem is
d;d
with
This is an example of semi-innite linear program (SILP), a class of
problems that has been extensively studied in mathematical program-
ming. The problem is called semi-innite because it has an innite
number of constraints and a nite number of variables. The set P is
known as the index set. If the set of hypotheses producible by the base
learner is nite, e.g. if fh nite, then the
problem is exactly equivalent to LP-Regression problem (8).
We will establish several facts about this semi-innite programming
problem using the results for general linear semi-innite programs summarized
in the excellent review paper (Hettich & Kortanek, 1993). To
simplify the presentation, we simplied the results in Hettich and Kortanek
(1993) to the case of SILP with an additional set of nite linear
constraints. The results presented can be easily derived from (Hettich
through a change in notation and by increasing
G. Ratsch, A. Demiriz and K.P. Bennett
the index set to include the additional nite set of traditional linear
constraints. To be consistent with our derivation of the SILP-regression
problem, we will refer to the problem with innitely many constraints
as the dual problem and the problem with innitely many variables as
the primal problem. Care should be taken, since this is the reverse of
the convention used in the mathematical programming literature.
We dene the generic dual SILP as
are compact
sets, a() is a function from B to R N , and b() is a function from R N to
R. We will make the additional assumption that the problem is always
feasible and that the feasible region is compact. Clearly the maximum
value is always obtained since we are maximizing a continuous function
over a compact set.
Ideally, we would like the solution of a linear program to correspond
to the optimal solution of the semi-innite problem. We now dene a
necessary condition for the existence of a nite linear program whose
optimal solution also solves the semi-innite program. We will denote
the generic dual SILP restricted to a nite subset
B as (D(PN )). This is a linear program since it has a nite number
of constraints.
The rst theorem gives necessary conditions for the optimal solution
of a generic dual SILP to be equivalent to the solution of a nite linear
program (Theorem 4.2 in Hettich & Kortanek, 1993):
Theorem 3 (Necessary condition for nite solution). Assume
the following Slater condition holds: For every set of N
z such that ha(p n
N , and Q^z < r. Then there exists
1.
2. There exist multipliers  n  0, , such that
This result immediately applies to the dual SILP regression problem
since the strictly interior point
1) satises the Slater condition.
Corollary 4 (Finite solution of regression ensemble). For Prob-
lem
D) (11) with  < 1, there exists
that
D(PN )).
Sparse Regression Ensembles 13
The signicance of this result is that there exists an optimial ensemble
that consists of at most N hypotheses where N is the number of
data points and that this is true even if the set of possible hypotheses
is innite.
3.4. Primal Regression SILP
Next we look at the corresponding primal problem for the semi-innite
case. We would like our semi-innite dual problem to be equivalent to
a meaningful primal problem that simplies to the original primal for
the nite hypothesis case.
be the set of nonnegative Borel measures on B. The
subset
R
denotes the set of nonnegative generalized nite sequences. The primal
problem of the generic SILP (12) is
In nite linear programming, the optimal objective values of the
primal and dual problems are always equal. This is not always true
for the semi-innite case. Weak duality always holds, that is, (P
(D). We must ensure that there is no duality gap, i.e., that (P
(D). From Hettich and Kortanek (1993) (Theorem 6.5) we have the
following
Theorem 5 (Su-cient conditions for no duality gap). Let the
convex cone
a(p)
a(p)
be closed, then (P primal minimum is attained.
For the regression problem,
is the set of base hypotheses (evaluated at the training points) obtainable
by our learning algorithm, and constant. Thus the
theorem can be simplied as follows.
Corollary 6 (Su-cient conditions for base learner). Let the convex
cone
14 G. Ratsch, A. Demiriz and K.P. Bennett
be closed,
then
D) and primal minimum is attained.
This corollary imposes conditions on the set of possible base hy-
potheses. Some examples of sets of base hypothesis that would satisfy
this condition are:
The set of possible hypotheses is nite, e.g. fh
Pg is nite.
The function h continuous with respect to p.
These two conditions are su-cient to cover all the base hypotheses
considered in this paper, but other conditions are possible.
4. LP Ensemble Optimization Algorithms
In this section we propose two algorithms for optimizing nite and
innite regression linear programs. The rst uses column generation
to execute a simplex-type algorithm. The second adopts an exponential
barrier strategy that has connections to boosting algorithms for
classication (Ratsch et al., 2000).
4.1. Column Generation Approach
The basic idea of Column Generation (CG) is to construct the optimal
ensemble for a restricted subset of the hypothesis space. LP (8)
is solved for a nite subset of hypotheses. It is called the restricted
master problem. Then the base learner is called to generate a hypothesis
. Assuming the base learner nds the
best hypothesis satisfying condition (9), if
the current ensemble is optimal as all constraints are fullled. If not,
the hypothesis is added to the problem. This corresponds to generating
a column in the primal LP or SILP or a row of the dual LP or SILP.
The CG-Regression algorithm (cf. Algorithm 1) assumes that the base
learner L(X; p) is nite for any p 2 P.
Algorithm 1 is a special case of the set of SILP algorithms known as
exchange methods. These methods are known to converge. Clearly if
the set of hypotheses is nite, then the method will converge in a nite
number of iterations since no constraints are ever dropped. But one
can also prove that it converges for SILP (cf. Theorem 7.2 in Hettich
Theorem 7 (Convergence of Algorithm 1). Algorithm 1 stops after
a nite number of steps with a solution to the dual regression
Sparse Regression Ensembles 15
Algorithm 1 The CG-Regression algorithm.
argument:Sample
Regularization constant C, Tube parameter  2 (0; 1)
returns: Linear combination from H.
function CG-Reg(X;
repeat
Let [d; d  ] be the solution of (8) using t 1 hypotheses
until
Let [; b] be the dual solution to [d; d  ], i.e. a solution to (7)
return
SILP or the sequence of intermediate solutions (d; d  ) has at least one
accumulation point and each of these solves the dual regression SILP.
This theorem holds for a more general set of exchange methods
than Algorithm 1. For example, it is possible to add or drop multiple
constraints at each iteration, and the convergence result is unchanged.
In practice, we found the column generation algorithm stops at an
optimal solution in a small number of iterations for both LP and SILP
regression problems.
4.2. A Barrier Algorithm
In the following we propose an algorithm (see also Ratsch et al., 2000)
that uses the barrier optimization technique (Bertsekas, 1995; Frisch,
1994). For details on the connection between
Boosting-type algorithms and barrier methods see Ratsch et al.
(2000, 2001). A similar algorithm has been proposed in Duy and Helmbold
(2000), which has been developed independently. In this sequel,
we will give a very brief introduction to barrier optimization.
The goal of barrier optimization is to nd an optimal solution of the
problem min 2S f(), where f is a convex function over a non-empty
convex set of feasible solutions. This
problem can be solved using a so called barrier function (e.g. Bertsekas,
1995; Cominetti & Dussault, 1994; Mosheyev & Zibulevsky, 1999; Censor
Zenios, 1997), the exponential barrier being a particularly useful
G. Ratsch, A. Demiriz and K.P. Bennett
choice for our purposes,
exp
being a penalty parameter. By nding a sequence of (uncon-
strained) minimizers f t g t to (18), using any sequence f t g t with
these minimizers can be shown to converge to a global
solution of the original problem, i.e. it holds:
min
min
The barrier minimization objective for the problem (7) using the exponential
barrier can be written as:
exp
for simplicity we have omitted
the constraints   0. The rst line in (20) is the objective of (7), the
second line corresponds to the constraints  n ;
The last line
implements the constraints - n
n .
Note that by setting r  E 0, we can nd the
minimizing slack variables ;   of (20) for given ,  and b. Thus,
the problem of minimizing (20) is greatly simplied, as there are 2N
variables less to optimize.
In this section, we propose an algorithm (cf. Algorithm 2) that {
similar to the column generation approach of the last section { solves
a sequence of optimization problems, the so called restricted master
problems. In each iteration t of the algorithm, one selects a hypothesis
and then solves (or approximately solves) an unconstrained optimization
problem in t These variables are the t hypothesis
coe-cients of the previous iterations, the bias b and the tube size ".
The solution of the restricted master problem with respect to the
master problem 1 is clearly suboptimal and one cannot easily apply (19).
However, it is known how fast one can decrease  if the intermediate
1 The (full) master problem has J
Sparse Regression Ensembles 17
Algorithm 2 The Barrier-Regression algorithm
argument:Sample
Number of iterations T, Regularization constant C
Tube parameter  2 (0; 1)
constants:  start > 0
returns: Linear combination from H.
function BarReg(X;
do
endfor
if
endfor
return
solutions are suboptimal (cf. Proposition 1 in Cominetti & Dussault,
1994; Ratsch et al., 2000): Roughly speaking one has to ensure that
to achieve the desired convergence in the sense
of (19), where the gradient is taken with respect to all variables.
The base learner needs to nd a hypothesis with a large edge
as such hypotheses correspond to violated constraints
in the dual problem. Whereas in the classication case the maximum
edge is minimized, we have in regression just that all edges have to be
below 1. Therefore, we dene the corrected edge with respect to the
constraint
which is
positive, if the constraint is violated. We now consider the case where
the base learner nds a hypothesis, which is only -optimal with respect
to the corrected edge. By this we mean that it nds a hypothesis that
is not much worse than the best hypothesis in H, i.e.

for some constant - 2 (0; 1]. Note that the correction in the edge comes
from the regularization term kk 1 . Then we get:
G. Ratsch, A. Demiriz and K.P. Bennett
Lemma 8. While running Algorithm 2 using a base learner satisfying
(21), the barrier parameter  is decreased only if   -krE  k 1 , where
the gradient is taken with respect to all variables "; b;
Proof. The gradient of E  with respect to " and b is always zeros as
they are unbounded variables in the minimization in line \+". The
gradient of E  with respect to  j is
")=). We have
two cases:
The hypothesis is already in the restricted master problem: If
line \+") we get  j  0 or if r  j
Note that the case r  j
happen. Thus, the
gradient projected on the feasible set (  0) is always zero.
The hypothesis has not already been included: If r  j
the last constraint in (8) is violated for j and the hypothesis h j
needs to be included in the hypothesis set.
Thus, one can exploit the property (21) of the base learner to upper-bound
the gradient of the master problem at the current solution. If
the learner returns a hypothesis by (21) there does
not exist another hypothesis with an edge larger than by a factor of
. Assume there exists a violated constraint. Then by line \",  is
decreased if -krE  k 1
Using this Lemma one gets the desired convergence property of Algorithm
2:
Theorem 9. Assume H is nite and the base learner L satises condition
(21). Then for T !1 the output of the algorithm converges to
a global solution of (7).
Proof. Let E  be given by (20). By Proposition 1 of (Cominetti & Dus-
sault, 1994) (see Ratsch et al., 2000), one knows that any accumulation
point of a sequence f t g t satisfying kr  E  t
global solution of (7). By Lemma 8 we have that  is decreased only if
> -krE  k 1 . If  is not decreased, the gradient will be reduced in a
nite number of iterations such that -krE  k 1 < . Thus  ! 0 and
Sparse Regression Ensembles 19
Similar conditions can be used to prove the convergence of Algorithm 1
in the case of non-optimal base learners in the sense of (21).
Barrier methods have also been applied to semi-innite programming
problems. In Kaliski et al. (1999) a similar barrier algorithm using
the log-barrier has been used (cf. also Mosheyev & Zibulevsky, 1999).
It is future work to rigorously prove that Algorithm 2 also converges
to the optimal solution when the hypothesis space is innite.
The algorithms proposed here are incomplete without descriptions
of the base hypothesis space and the base learner algorithm. In the next
section, we consider choices of the hypothesis space and base learner,
and how they eect the algorithms.
4.3. Choice of Hypothesis Space and Base Learner
Recall that both algorithms require the hypothesis h p that solves or
approximately solves
So the question is how do we solve this for dierent types of base
learners. If the set of base learners is compact, then this maximum
must exist.
4.3.1. Kernel functions
Suppose we wish to construct ensembles of functions that themselves
are linear combinations of other functions (e.g. of kernel functions)
using coe-cient
, i.e. functions of the form k n ()  k(x n ;
The set fh
g is an innite hypothesis set and is unbounded, if
is
unbounded. So, one has to restrict
{ here we consider bounding the ' 1 -
norm of
by some constant, e.g. H := fh
g. Then
the problem (22) has a closed form solution: Let j  be the maximum
absolute sum of the kernel values weighted by p:
with
is a solution to (22), where
P N
. This means, if we boost linear combinations
of kernel functions bounded by the ' 1 -norm of
, then we will
G. Ratsch, A. Demiriz and K.P. Bennett
be adding in exactly one kernel basis function k(x j  ; ) per iteration.
The resulting problem will be exactly the same as if we were optimizing
a SVM regression LP (e.g. Smola et al., 1999) in the rst place. The
only dierence is that we have now dened an algorithm for optimizing
the function by adding one kernel basis at a time. So while we posed
this problem as a semi-innite learning problem it is exactly equivalent
to the nite SVM case where the set of hypotheses being boosted is the
individual kernel functions k(x
If the
were bounded using dierent norms then this would no
longer be true. We would be adding functions that were the sum of
many kernel functions (for using the ' 2 -norm, see Ratsch et al., 2000a).
Likewise, if we performed an active kernel strategy, where the set of
kernels is parameterized over some set then the algorithm would change.
We consider this problem in the next section.
4.3.2. Active Kernel Functions
Now consider the case where we chose a set of (kernel) functions parameterized
by some vector . By the same argument above, if we impose
the bound k
need only consider one such basis function
at a time. But in this case since the kernel is parameterized over a
set of continuous values
, we will have an innite set of hypothesis.
Say for example we wish to pick the a RBF kernel with parameters
(the center) and  2 (the variance), i.e.
we chose the
hypothesis function
exp

with parameters that maximize the correlation between weight
p and the output (the so-called edge), i.e.
With reasonable assumptions, this is a bounded function that is in p.
Thus all of the above results for the semi-innite case hold.
There are several ways to e-ciently nd ^
. The straight-forward
way is to employ some standard nonlinear optimization technique
to maximize (24). However, for RBF kernels with xed variance
2 there is a fast and easy to implement EM-like strategy. By setting
and Z is a normalization factor such that
1. By this update,
we are computing the weighted center of the data, where the weights
Sparse Regression Ensembles 21
depend on p. Note, for given vector q, one can compute (M-step) the
optimal center . However, q depends on  and one has to iteratively
recompute q (E-step). The iteration can be stopped, if
does not change anymore. As the objective function has local minima,
one may start at a random position, e.g. at a random training point.
4.3.3. SVM Classication Functions
Here we consider the case of using a linear combination of classica-
tion functions whose output is 1 to form a regression function. An
example of such an algorithm is the Tree-Boost algorithm of Friedman
1999). For absolute error functions, Tree-Boost constructs
a classication tree where the class of each point is taken to be the
sign of the residual of each point, i.e. points that are overestimated are
assigned to class -1 and points that are underestimated are assigned
to class 1. A decision tree is constructed, then based on a projected
gradient descent technique with an exact line-search, each point falling
in a leaf node is assigned the mean value of the dependent variables of
the training data falling at that node. This corresponds to a dierent
t for each node of the decision tree. So at each iteration, the virtual
number of hypotheses added in some sense corresponds to the number
of leaf nodes of the decision tree.
Here we will take a more simplied view and consider one node
decision trees where the decision trees are linear combinations of the
data. Specically our decision function at each node is f(x;
b). Thus at each iteration of the algorithm we want to
w;b
Note that there are only nitely many ways to label N points so this
is a nite set of hypotheses. There are innitely many possible (w; b)
but any that produce the same objective value are equivalent to the
boosting algorithm.
The question is how to practically optimize such a problem. Clearly
an upper bound on the best possible value of the above equation is
obtained by any (w; b) solution satisfying
So in some sense, we can consider the sign(p n ) to be the desired class of
x n . Now it frequently may not be possible to construct such a f . Each
x n that is misclassied will be penalized by exactly jp n j. Thus we can
think of jp n j as the misclassication cost of x n . Given these classes, and
misclassication weights, we can use any weight sensitive classication
algorithm to construct a hypothesis.
22 G. Ratsch, A. Demiriz and K.P. Bennett
In this study we used the following problem converted into LP form
to construct f :
with sign(p n )(hw; x
becomes a parameter of the problem.
Some interesting facts about this formulation. The choice of - controls
the capacity of the base learners to t the data. For a xed
choice of -, classication functions using a relatively xed number of
w d nonzero. So the user can determine based on experimentation on
the training data, how - eects the complexity of the base hypothesis.
Then the user may x - according to the desired complexity of the base
hypothesis. Alternatively, a weighted variation of -SVMs (Scholkopf
et al., 2000) could be used to dynamically chose -.
Like in TreeBoost, we would like to allow each side of the linear
decision to have a dierent weight. We describe the changes required
to Algorithm 1 to allow this. At each iteration, LP (26) is solved to nd
a candidate hypothesis
instead of adding a single column
to the restricted master LP (12), two columns are added. The rst
column is
and the second column is h
0). The algorithms stop if both of these hypotheses
do not meet the criteria given in the algorithm. The algorithm should
terminate if
2. We call this variant
of the algorithm CG-LP. This change has no eect on the convergence
properties.
5. Experiments
In this section we present some preliminary results indicating the feasibility
of our approaches. We will start in Section 5.1 with showing
some basic properties of the CG and barrier algorithms for regression.
We show that both algorithms are able to produce excellent ts on a
noiseless and several noisy toy problems.
As base learners we use the three proposed in Section 4.3. We
will denote by CG-k, CG-ak and CG-LP, the CG algorithms using
RBF kernels, active RBF kernels and classication functions as base
learners, respectively. Likewise for Bar-k, Bar-ak and Bar-LP using the
barrier algorithm. Not all of these possible combinations have been
implemented.
Sparse Regression Ensembles 23
To show the competitiveness of our algorithms we performed a benchmark
comparison in Section 5.2 on time-series prediction problems that
have been extensively studied in the past.
Moreover, we give an interesting application to a problem derived
from computer-aided drug-design in Section 5.3. There, we in particular
show that the approach using classication functions as base learner is
very well suited for datasets where the dimensionality of the problem
is high, but the number of samples is very small.
5.1. An Experiment on toy data
To illustrate (i) that the proposed regression algorithm converges to
the optimal (i.e. zero error) solution and (ii) is capable of nding a
good t to noisy data (signal:noise=2:1) we applied it to a toy example
{ the frequently used sinc function in the
range [ 2; 2]. For our demonstration (cf. Fig. 1) we used two base
hypothesis spaces: (i) RBF kernels in the way described in Section 4.3.1,
i.e.
with classication functions as described in Section
4.3.3. In the rst case we used the CG and the Barrier approch
{ leading to the algorithms CG-k and Bar-k. The latter case is included
for demonstration purposes only, the CG-LP is designed for
high-dimensional data sets and does not perform well in low dimensions
due to the severely restricted nature of the base hypothesis set.
To keep the results comparable between dierent data sets we use
a normalized measure of error { the Q 2 -error (also called normalized
mean squared error), which is dened as:
is meaningless since simply predicting the mean target value
will result in a Q 2 -value of one.
Let us rst consider the case of RBF-kernels. In the noise-free case
(left panel of Fig. 1) we observe { as expected from Proposition 2 {
that the (automatically determined) tube size " is very small (0.0014),
while it is kept large (0.12) for the high noise case (right panel). Using
the right tube size, one gets an almost perfect t (Q
the noise-free case and an excellent t in the noisy case (Q {
without re-tuning the parameters.
The CG-LP produced a piecewise-constant function based on only
two classication functions. The same solution of produced
in both the noisy and noise-free cases. Interestingly in the noisy
G. Ratsch, A. Demiriz and K.P. Bennett
Figure

1. Toy example: The left panel shows the t of the sinc function without
noise using RBF-kernels (solid) and classication functions (dashed). The solid t is
almost perfect (Q while the dashed function is too simple (Q
The right panel shows a t using RBF-kernels (Q on noisy data (sig-
100). The tube size is automatically adapted by the algorithm
(right)), such that a half of the patterns lie inside
the tube
case it produces almost an identical function. Because the hypothesis
space only consists of linear classication functions constructed by LP
(26), the set of base hypothesis is extremely restricted. Thus high bias,
but low variance behavior can be expected. We will see later than on
high dimensional datasets the CG-LP can perform quite well.
Let us now compare the convergence speed of CG- and Barrier-
Regression in the controlled setting of this toy example. For this we run
both algorithms and record the objective values of the restricted master
problem. In each iteration of the barrier algorithm one has to nd the
minimizing or almost minimizing parameters (; "; b) of the barrier
function E  for the restricted master problem. In our implementation
we use an iterative gradient descent method, where the number of
gradient steps is a parameter of the algorithm. The result is shown
in Fig. 2. One observes that both algorithms converge rather fast to
the optimal objective value (dotted line). The CG algorithm converges
faster than the barrier algorithm, as in the barrier parameter usually
decreases not quick enough to compete with the very e-cient Simplex
method. However, if the number of gradient descent steps is large
enough (e.g. 20), the barrier algorithm produces comparable results in
the same number of iterations. Note that if one does only one gradient
descent step per iteration, this approach is similar to the algorithm
proposed in Collins et al. (2000) that uses parallel coordinate descent
steps (similar to Jacobi iterations).
Sparse Regression Ensembles 25
Objective
value
Iteration
replacements
Objective value
Iteration

Figure

2. Convergence on the toy example: The convergence of the objective function
CG-Regression (solid) and Barrier-Regression to
the optimal value (dotted) over the number of iterations. Left for no noise and
right for large normal noise 1). For Barrier-Regression we did 1
(dash-dotted) and 20 (dashed) gradient descent steps in each iteration, respectively.
We used
5.2. Time Series Benchmarks
In this section we would like to compare our new methods to SVMs
and RBF networks. For this we chose two well-known data sets that
have been frequently used as benchmarks on time-series prediction:
(i) the Mackey-Glass chaotic time series (Mackey & Glass, 1977) and
(ii) data set D from the Santa Fe competition (Weigend & N.A. Gershenfeld
(Eds.), 1994). We x the following experimental setup for our
comparison. We use seven dierent models for our comparison: three
models that have been used in Muller et al. (1999) (RBF nets and SVM-
Regression (SVR) with linear and Huber loss) and four new models:
CG-k, CG-ak, Bar-k and Bar-ak.
All models are trained using a simple cross validation technique.
We choose the model with the minimum prediction error measured on
a randomly chosen validation set (originally taken from Muller et al.,
1999). The data including our experimental results can be obtained
from http://ida.first.gmd.de/~raetsch/data/ts.
5.2.1. Mackey Glass Equation
Our rst application is a high-dimensional chaotic system generated by
the Mackey-Glass delay dierential equation
dt
26 G. Ratsch, A. Demiriz and K.P. Bennett
with delay t originally introduced as a model
of blood cell regulation (Mackey & Glass, 1977) and became quite
common as an articial forecasting benchmark. After integrating (28),
we added noise to the time series. We obtained training (1000 patterns)
and validation (the following 194 patterns) sets using an embedding
dimension 6. The test set (1000 patterns)
is noiseless to measure the true prediction error. We conducted experiments
for dierent signal to noise ratios 2 (SNR) using uniform
noise.
In

Table

II we state the results given in the original paper (Muller
et al., 1999) for SVMs using "-insensitive loss and Huber's robust loss
(quadratic/linear) and RBF networks. Moreover, we give the results
for the CG and the barrier algorithm using RBF kernels and active
RBF-kernels. 3 We also applied the CG algorithm using classication
functions (CG-LP), but the algorithm performed very poorly (Q 2
0:16), because it could not generate complex enough functions. From

Table

II we observe that all four algorithms perform on average as
good as the best of the other algorithms (in 11 cases better and in 13
cases worse). The 100 step prediction at low noise levels is rather poor
compared to SVMs, but it is great on the higher noise levels.
Note that the CG and the barrier algorithm do not perform significantly
dierent (CG is in 5 cases better and in 7 cases worse). This
shows that the simple barrier implementation given in Algorithm 2
achieves a high enough accuracy to compete with a sophisticated simplex
implementation used in the CG-algorithms.
5.2.2. Data Set D from the Santa Fe Competition
Data set D from the Santa Fe competition is articial data generated
from a nine-dimensional periodically driven dissipative dynamical system
with an asymmetrical four-well potential and a slight drift on the
parameters (Weigend & N.A. Gershenfeld (Eds.), 1994). The system
has the property of operating in one well for some time and then switching
to another well with a dierent dynamical behavior. Therefore, we
rst segment the time series into regimes of approximately stationary
dynamics. This is accomplished by applying the Annealed Competition
of Experts (ACE) method described in Pawelzik et al. (1996), Muller
et al. (1995) (no assumption about the number of stationary subsystems
was made). Moreover, in order to reduce the eect of the continuous
We dene the SNR in this experiment as the ratio between the variance of the
noise and the variance of the data.
3 On the entries set as italic, the model selection failed completely. In this case
we selected the model manually by chosing the model on the 10th percentile of the
test errors over all tested models.
Sparse Regression Ensembles 27
drift, only the last 2000 data points of the training set are used for
segmentation. After applying the ACE algorithm, the data points are
individually assigned to classes of dierent dynamical modes. We then
select the particular class of data that includes the data points at the
end of Data Set D as the training set. 4
This allows us to train our models on quasi-stationary data and we
avoid having to predict the average over all dynamical modes hidden in
the full training set (see also Pawelzik et al. (1996) for further discus-
sion). However, at the same time we are left with a rather small training
set requiring careful regularization, since there are only 327 patterns in
the extracted training set. As in the previous section we use a validation
set (50 patterns of the extracted quasi-stationary data) to determine
the model parameters of SVMs, RBF networks and CG-Regression.
The embedding parameters used, are the same for
all the methods compared in Table III.

Table

III shows the errors (Q 2 -value) for the 25 step iterated predic-
tion. 5 In the previous result of (Muller et al., 1999) the Support vector
machine with "-ins. loss is 30% better than the one achieved by Pawelzik
et al. (Pawelzik et al., 1996). This is the current record on this dataset.
Given that it is quite hard to beat this record, our methods perform
4 Hereby we assume that the class of data that generated the last points in the
training set is the one that is also responsible for the rst couple of steps of the
iterated continuation that we aim to predict.
5 Iterated prediction means that based on the past predictions (and not on the
original data) the new prediction is computed.

Table

II. 1S denotes the 1-step prediction error (Q 2 ) on the test set. 100S is
the 100-step iterated autonomous prediction. \SNR" is the ratio between the
variance of the respective noise and the underlying time series.
SNR 6.2% 12.4% 18.6%
test error 1S 100S 1S 100S 1S 100S
SVM "-ins. 0.0007 0.0158 0.0028 0.0988 0.0057 0.4065
28 G. Ratsch, A. Demiriz and K.P. Bennett
quite well. CG-ak improves the result in Pawelzik et al. (1996) by 28%,
while CG-k is 26% better. 6 This is very close to the previous result.
The model-selection is a crucial issue for this benchmark competition.
The model, which is selected on the basis of the best prediction on the
50 validation patterns, turns out to be rather suboptimal. Thus, more
sophisticated model selection methods are needed here to obtain more
reliable results.

Table

III. Comparison (under competition condi-
tions) of 25 step iterated predictions (Q 2 -value) on
Data set D. A prior segmentation of the data according
to (Muller et al., 1995; Pawelzik et al., 1996) was
done as preprocessing.
CG SVM Neural Net
CG-k CG-ak "-ins. Huber RBF PKM
5.3. Experiments on Drug data
This data set is taken from computer-aided drug design. The goal
is to predict bio-reactivity of molecules based on molecular structure
through the creation of Quantitative Structure-Activity Relationship
models. Once a predictive model has been constructed, large
databases can be screened cost eectively for desirable chemical prop-
erties. Then this small subset of molecules can then be tested further
using traditional laboratory techniques. The target of this dataset LC-
CKA is the logarithm of the concentration of each compound that is
required to produce 50 percent inhibition of site \A" of the Cholecys-
tokinin (CCK) molecule. These CCK and CCK-like molecules serve important
roles as neuro-transmitters and/or neuro-modulators. 66 compounds
were taken from the Merck CCK inhibitor data set. The dataset
originally consisted of 323 descriptors taken from a combination of
\traditional" 2D, 3D, and topological properties and electron density
derived TAE (Transferable Atomic Equivalent) molecular descriptors
derived using wavelets (Brenema et al., 2000). All data was scaled to be
between 0 and 1. The data can be obtained from http://www.rpi.edu/
~bennek.
It is well known that appropriate feature selection on this dataset
and others is essential for good performance of QSAR models due to the
6 We have not performed experiments with the barrier algorithm on this data,
since the performance is expected to be similar.
Sparse Regression Ensembles 29
small amount of available data with known bio-reactivity and the large
number of potential descriptors, see for example (Embrechts et al.,
1998). In an unrelated study (Bennett et al., 2001) feature selection
was done by constructing a ' 1 -norm linear support vector regression
machine (like in equation (6) but where the features are the input
dimensions) to produce a sparse weighting of the descriptors. Only the
descriptors with positive weights were retained. We take the reduced
set of 39 descriptors as given. We refer to the full data set as LCCKA
and the reduced dataset as LCCKA-R.
The typical performance measured used to evaluate QSAR data is
the average sum squared error between the predicted and true target
values divided by the true target variance. This is Q 2 as dened in (27).
A Q 2 of less than 0:3 is considered very good. To measure the perfor-
mance, 6-fold cross validation was performed. We report the out-of-
sample averaged over the 6 folds. In this preliminary study, model-selection
using parameter selection techniques was not performed. As
models we consider CG-LP (CG with classication functions) and CG-
k (CG with non-active kernels) described in Sections 4.3.3 and 4.3.1.
For CG-k, we used only three dierent values for the regularization
constant C, the tube-parameter  and the parameter of the base learner
(kernel-width) and - (complexity parameter in (26)), respectively.
Thus, we examined 27 dierent parameter combinations. For CG-LP,
we used parameter values found to work well on a reduced dataset in
Bennett et al. (2001) and then chose C and - such that the number of
hypotheses and attributes per hypothesis were similar on the training
data. Research is in progress to repeat these studies using a more appropriate
model selection technique { leave-one-out cross validation. Model
selection is critical for performance of these methods, thus e-cient
model selection techniques is an important open question that needs
to be addressed.
First we tried CG-k on the full data set LCCKA, but it failed to
achieve good performance (Q while the simple approach CG-
LP performed quite well with 0:33. This is because CG-LP is able
to select the discriminative features based on subsets of the attributes,
while the kernel-approaches get confused by the uninformative features.
For the reduced set LCCKA-R, where the features are already pre-
selected, the kernel approach improves signicantly (Q
is not signicantly dierent than CG-LP methods
produced sparse ensembles.
On the full dataset, using parameters
CG-LP used on average ensembles containing 22 hypotheses consisting
of, on average, 10:1 of the possible 323 attributes, while CG-k with
RBF-kernel used 45 hypotheses. On the reduced
G. Ratsch, A. Demiriz and K.P. Bennett
dataset, using parameters used on
average ensembles containing 23:5 hypotheses consisting of, on average,
10:7 attributes, while the CG-k approach used on average 30:3
hypotheses 0:1). The slight dierence between CG-LP and CG-k
might be explained again by the presence of uninformative features.
Summarizing, the CG-LP approach seems to be a very robust method
to learn simple regression functions in high-dimensional spaces with
automatic feature selection.
6. Conclusion
In this work we examined an LP for constructing regression ensembles
based on the ' 1 -norm regularized -insensitive loss function used for
support vector machines rst proposed for ensembles of nite hypothesis
sets in Smola et al. (1999). We used the dual formulation of the
nite regression LP: (i) to rigorously dene a proper extension to the
innite hypothesis case and (ii) to derive two e-cient algorithms for
solving them. It is shown theoretically and empirically that even if the
hypothesis space is innite, only a small nite set of the hypotheses is
needed to express the optimal solution (cf. Corollary 4). This sparseness
is possible due to the use of the ' 1 -norm of the hypothesis coe-cient
vector, which acts as a sparsity-regularizer.
We proposed two dierent algorithms for e-ciently computing optimal
nite ensembles. Here, the base-learner acts as an oracle to nd
the constraints in the dual semi-innite problem that are violated. For
the rst algorithm (the CG algorithm for regression), which is based
on a simplex method, we proved the convergence for the innite case
(cf. Theorem 7). The second algorithm { the Barrier algorithm for
Regression { is based on an exponential barrier method that has connections
to the original AdaBoost method for classication (cf. Ratsch
et al., 2000). This algorithm converges for nite hypothesis classes
(cf. Theorem 9). Using recent results in the mathematical programming
literature (e.g. Mosheyev & Zibulevsky, 1999; Kaliski et al., 1999) we
claim that it is possible to generalize it to the innite case. Computationally
both algorithms nd a provably optimal solution in a small
number of iterations.
We examined three types of base learning algorithms. One, based
on boosting kernel functions chosen from a nite dictionary of ker-
nels, is an example of a nite hypothesis set. We also consider active
kernel methods where the kernel basis are selected from an innite
dictionary of kernels. Finally, we consider the case using the nite set
of linear classication functions constructed using an LP. This is a
Sparse Regression Ensembles 31
very limited hypothesis space that is specically designed to work on
underdetermined high-dimensional problems such as the drug design
data discussed in this paper.
Our preliminary simulations on toy and real world data showed that
the proposed algorithms behave very well in both nite and innite
cases. In a benchmark comparison on time-series prediction problems
our algorithms perform as well as the current state of the art regression
methods such as support vector machines for regression. In the
case of \Data set D" of the Santa Fe competition we obtained results
that are as good as the current record (by SVM) on this dataset.
The LP classication-based approach worked extremely well on the
high-dimensional drug design datasets, since the algorithm inherently
performs feature selection essential for success on such datasets.
The primary contribution of this paper has been a theoretical and
conceptual study of LP-based ensemble regression algorithms in nite
and innite hypothesis spaces. For future work we plan a more rigorous
investigation of the computational aspects of our approach. One open
question is how to best perform selection of the LP model parame-
ters. Another open question involves the best algorithmic approaches
for solving the semi-innite linear program. While they work well in
practice, the column generation and barrier interior-point methods
described here are not the current state of the art for semi-innite linear
programming. A primal-dual interior point algorithm may perform
even better both theoretically and empirically especially on very large
datasets. Lastly, the ability to handle innite hypothesis sets opens up
the possibility of many other possible types of base learning algorithms.

Acknowledgments

G. Ratsch would like to thank Sebastian Mika,
Klaus-R. Muller, Bob Williamson and Manfred Warmuth for valuable
discussions. This work was partially funded by DFG under contracts
JA 379/91, JA 379/71 and MU 987/1-1 and by the National Science
Foundation under Grant No. 970923 and No. 9979860.



--R

An empirical comparison of voting classi


A boosting algorithm for regression.
Nonlinear Programming.
Parsimonious least norm approximation.
Prediction games and arcing algorithms.
Wavelet representations of molecular electronic properties: Applications in adme

Parallel Optimization: Theory
Atomic decomposition by basis pursuit.
Adaboost and logistic regression uni
A stable exponential penalty algorithm with superlinear convergence.
An experimental comparison of three methods for constructing ensembles of decision trees: Bagging


computationally intelligent data mining for the automated design and discovery of novel pharmaceuticals.

A simple cost function for boost- ing
Game theory
A decision-theoretic generalization of on-line learning and an application to boosting
Experiments with a new boosting algorithm.
Additive logistic regression: a statistical view of boosting.
Greedy function approximation.
The logarithmic potential method of convex pro- gramming


Logarithmic barrier decomposition methods for semi-in nite programming
Submitted to Elsevier Science.
Boosting as entropy projection.



Linear and Nonlinear Programming (second edition).
Oscillation and chaos in physiological control systems.
An empirical evaluation of bagging and boosting.
Improved generalization through explicit optimization of margins.
Functional gradient techniques for combining hypotheses.




Advances in Kernel Methods









Boosting the margin: a new explanation for the e



New support vector algorithms.
AdaBoosting neural networks.
In Gerstner

Learning with Kernels.

The nature of statistical learning theory.
Time Series Pre- diction: Forecasting the Future and Understanding the Past

A gradient-based boosting algorithm for regression problems
--TR

--CTR
Gilles Blanchard , Gbor Lugosi , Nicolas Vayatis, On the rate of convergence of regularized boosting classifiers, The Journal of Machine Learning Research, 4, 12/1/2003
Pierre Geurts , Louis Wehenkel , Florence d'Alch-Buc, Gradient boosting for kernelized output spaces, Proceedings of the 24th international conference on Machine learning, p.289-296, June 20-24, 2007, Corvalis, Oregon
Jinbo Bi , Tong Zhang , Kristin P. Bennett, Column-generation boosting methods for mixture of kernels, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
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
P. M. Granitto , P. F. Verdes , H. A. Ceccatto, Neural network ensembles: evaluation of aggregation algorithms, Artificial Intelligence, v.163 n.2, p.139-162, April 2005
Peter Bhlmann , Bin Yu, Sparse Boosting, The Journal of Machine Learning Research, 7, p.1001-1024, 12/1/2006
Gunnar Rtsch , Manfred K. Warmuth, Efficient Margin Maximizing with Boosting, The Journal of Machine Learning Research, 6, p.2131-2152, 12/1/2005
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
Robust Loss Functions for Boosting, Neural Computation, v.19 n.8, p.2183-2244, August 2007
Sebastian Mika , Gunnar Rtsch , Jason Weston , Bernhard Schlkopf , Alex Smola , Klaus-Robert Mller, Constructing Descriptive and Discriminative Nonlinear Features: Rayleigh Coefficients in Kernel Feature Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.623-633, May
Gunnar Rtsch , Sebastian Mika , Bernhard Schlkopf , Klaus-Robert Mller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
boosting;semi-infinite programming;ensemble learning;regression;sparseness