Linear Programming Boosting via Column Generation.
We examine linear program (LP) approaches to boosting and demonstrate their efficient solution using LPBoost, a column generation based simplex method. We formulate the problem as if all possible weak hypotheses had already been generated. The labels produced by the weak hypotheses become the new feature space of the problem. The boosting task becomes to construct a learning function in the label space that minimizes misclassification error and maximizes the soft margin. We prove that for classification, minimizing the 1-norm soft margin error function directly optimizes a generalization error bound. The equivalent linear program can be efficiently solved using column generation techniques developed for large-scale optimization problems. The resulting LPBoost algorithm can be used to solve any LP boosting formulation by iteratively optimizing the dual misclassification costs in a restricted LP and dynamically generating weak hypotheses to make new LP columns. We provide algorithms for soft margin classification, confidence-rated, and regression boosting problems. Unlike gradient boosting algorithms, which may converge in the limit only, LPBoost converges in a finite number of iterations to a global solution satisfying mathematically well-defined optimality conditions. The optimal solutions of LPBoost are very sparse in contrast with gradient based methods. Computationally, LPBoost is competitive in quality and computational cost to AdaBoost.
Introduction
Recent papers [16] have shown that boosting, arcing, and related ensemble methods (hereafter summarized as
boosting) can be viewed as margin maximization in function space. By changing the cost function, di#erent
boosting methods such as AdaBoost can be viewed as gradient descent to minimize this cost function. Some
authors have noted the possibility of choosing cost functions that can be formulated as linear programs (LP)
but then dismiss the approach as intractable using standard LP algorithms [14, 6]. In this paper we show
that LP boosting is computationally feasible using a classic column generation simplex algorithm [11]. This
method performs tractable boosting using any cost function expressible as an LP.
We specifically examine the variations of the 1-norm soft margin cost function used for support vector
machines [15, 3, 9]. One advantage of these approaches is that immediately the method of analysis for
support vector machine problems becomes applicable to the boosting problem. In Section 2, we prove that
the LPBoost approach to classification directly minimizes a bound on the generalization error. We can adapt
the LP formulations developed for support vector machines. In Section 3, we discuss the soft margin LP
formulation. By adopting linear programming, we immediately have the tools of mathematical programming
at our disposal. By use of duality theory and optimality conditions, we can gain insight into how LP boosting
works mathematically. In Section 4 we examine how column generation approaches for solving large scale
LPs can be adapted to boosting.
For classification, we examine both standard and confidence-rated boosting. Standard boosting algorithms
use weak learners that are classifiers, that is, whose outputs are in the set {-1, +1}. Schapire and
Singer [17] have considered boosting weak learners whose outputs reflected not only a classification but
also an associated confidence encoded by a value in the range [-1, +1]. They demonstrate that so-called
confidence-rated boosting can speed convergence of the composite classifier, though the accuracy in the long
term was not found to be significantly a#ected. In Section 5, we discuss the minor modifications needed for
LPBoost to perform confidence-rated boosting.
The methods we develop can be readily extended to any boosting problem formulated as an LP. We
demonstrate this by adapting the approach to regression in Section 6. Computational results and practical
issues for implementation of the method are given in Section 7.
Motivation for Soft Margin Boosting
We begin with an analysis of the boosting problem using methodology developed for support vector machines.
The function classes that we will be considering are of the form
a set of weak learners which we assume is closed under complementation. Initially, these will be classification
functions with outputs in the set {-1, 1}, though this can be taken as [-1, 1] in confidence-rated boosting.
We begin, however, by looking at a general function class and quoting a bound on the generalization error
in terms of the margin and covering numbers. We first introduce some notation. If D is a distribution
on inputs and targets, X -1, 1}, we define the error err D (f) of a function f # F to be the probability
we assume that we obtain a classification function by thresholding at 0 if
f is real-valued.
Definition 2.1. Let F be a class of real-valued functions on a domain X. A #-cover of F with respect
to a sequence of inputs set of functions A such that for all f # F, there
exists #. The size of the smallest such cover is denoted by
N(F, S, #), while the covering numbers of F are the values
N(F, S, #).
In the remainder of this section we will assume a training set . For a real-valued
function f # F we define the margin of an example (x, y) to be yf(x), where again we implicitly assume
that we are thresholding at 0. The margin of the training set S is defined to be m S
Note that this quantity is positive if the function correctly classifies all of the training examples. The
following theorem is given in [8] but it is implicit in the results of [18].
Theorem 2.1. Consider thresholding a real-valued function space F and fix # R + . For any probability
distribution D on X -1, 1}, with probability 1 - # over m random examples S, any hypothesis f # F that
has margin m S (f) # on S has error no more than
err D (f) #(m, F,
# log N(F, 2m, #)
We now describe a construction originally proposed in [19] for applying this result to cases where not
all the points attain the margin #. Let X be a Hilbert space. We define the following inner product space
derived from X.
Definition 2.2. Let L(X) be the set of real-valued functions f on X with countable support supp(f), that
is, functions in L(X) are non-zero only for countably many points. Formally, we require
countable and
We define the inner product of two functions f, g # L(X) by #f - g# x#supp(f) f(x)g(x). This implicitly
defines a norm # 2 . We also introduce
|f(x)|.
Note that the sum that defines the inner product is well-defined by the Cauchy-Schwarz inequality.
Clearly the space is closed under addition and multiplication by scalars. Furthermore, the inner product is
linear in both arguments.
We now form the product space X - L(X) with the corresponding function class F - L(X) acting on
via the composition rule
Now for any fixed 1 # > 0 we define an embedding of X into the product space X - L(X) as follows:
where # x # L(X) is defined by # x
Definition 2.3. Consider using a class F of real-valued functions on an input space X for classification by
thresholding at 0. We define the margin slack variable of an example with respect to
a function f # F and target margin # to be the quantity # ((x i , y
that # i > # implies incorrect classification of
The construction of the space X-L(X) allows us to obtain a margin separation of # by using an auxiliary
function defined in terms of the margin slack variables. For a function f and target margin # the auxiliary
function with respect to the training set S is
It is now a simple calculation to check the following two properties of the function (f,
1. (f, g f ) has margin # on the training set # (S).
2. (f, g f )#
Together these facts imply that the generalization error of f can be assessed by applying the large margin
theorem to (f, g f ). This gives the following theorem:
Theorem 2.2. Consider thresholding a real-valued function space F on the domain X. Fix
choose G # F - L(X). For any probability distribution D on X -1, 1}, with probability
random examples S, any hypothesis f # F for which (f, g f ) # G has generalization error no more than
err D (f) #(m, F, #) =m
# log N(G, 2m, #)
2/#, and there is no discrete probability on misclassified training points.
We are now in a position to apply these results to our function class which will be in the form described
we have left open for the time being what the class H of
learners might contain. The sets G of Theorem 2.2 will be chosen as follows:
a h h, g #
Hence, the condition that a function satisfies the conditions of Theorem 2.2 for
simply
(1)
Note that this will be the quantity that we will minimize through the boosting iterations described in later
sections, where we will use the parameter C in place of 1/# and the margin # will be set to 1. The final
piece of the puzzle that we require to apply Theorem 2.2 is a bound on the covering numbers of GB in terms
of the class of weak learners H, the bound B, and the margin #. Before launching into this analysis, observe
that for any input x,
2.1 Covering Numbers of Convex Hulls
In this subsection we analyze the covering numbers N(GB , m, #) of the set
a h h, g #
in terms of B, the class H, and the scale #. Assume first that we have an #/B-cover G of the function class
H with respect to the set is a class of binary-valued functions
then we will take # to be zero and G will be the set of dichotomies that can be realized by the class. Now
consider the set V of vectors of positive real numbers indexed by G # {1, . , m}. Let VB be the function
class suppose that U be an (# -cover of VB . We
claim that the set
is a #-cover of GB with respect to the set # (S). We prove this assertion by taking a general function
h, g # GB , and finding a function in A within # of it on all of the points # (x i ). First,
for each h with non-zero coe#cient a h , select - h # G, such that #h(x i
m. Now we form the function -
which lies in the set VB , since # h#G a h
Furthermore we have that
Since U is a # cover of VB there exists - v # U such that -
f on # It follows that -
f is within # of f on this same set. Hence, A forms a # cover of
the class GB . We bound |A| = |U | using the following theorem due to [20], though a slightly weaker version
can also be found in [1].
Theorem 2.3. [20] For the class VB defined above we have that
log N(VB , m,
log
Hence we see that optimizing B directly optimizes the relevant covering number bound and hence the
generalization bound given in Theorem 2.2 with . Note that in the cases considered |G| is just the
growth function BH (m) of the class H of weak learners.
Boosting LP for Classification
From the above discussion we can see that a soft margin cost function should be valuable for boosting
classification functions. Once again using the techniques used in support vector machines, we can formulate
this problem as a linear program. The quantity B defined in Equation (1) can be optimized directly using
an LP. The LP is formulated as if all possible labelings of the training data by the weak learners were
known. The LP minimizes the 1-norm soft margin cost function used in support vector machines with the
added restrictions that all the weights are positive and the threshold is assumed to be zero. This LP and
variants can be practically solved using a column generation approach. Weak learners are generated as
needed to produce the optimal support vector machine based on the output of the all weak learners. In
essence the base learner become an 'oracle' that generates the necessary columns. The dual variables of the
linear program provide the misclassification costs needed by the learning machine. The column generation
procedure searches for the best possible misclassification costs in dual space. Only at optimality is the actual
ensemble of weak learners constructed.
3.1
Let the matrix H be a m by n matrix of all the possible labelings of the training data using functions from
is the label (1 or - 1) given by weak learner h j # H on the training point x i .
Each column H .j of the matrix H constitutes the output of weak learner h j on the training data, while each
row H i gives the outputs of all the weak learners on the example x i . There may be up to 2 m distinct weak
learners.
The following linear program can be used to minimize the quantity in Equation (1):
min a,# n
a
(2)
where C > 0 is the tradeo# parameter between misclassification error and margin maximization. The dual
of LP (2) is
Alternative soft margin LP formulations exist, such as this one for the #-LP Boosting 1 . [14]:
a
a
We remove the constraint # 0 since # > 0 at optimality under the complementation assumption.
The dual of this LP (4) is:
min u,#
These LP formulations are exactly equivalent given the appropriate choice of the parameters C and D.
Proofs of this fact can be found in [15, 5] so we only state the theorem here.
Theorem 3.1 (LP Formulation Equivalence). If LP (4) with parameter D has a primal solution (-a, -
#) and dual solution (-u, -
#), then
are the primal and dual solutions of LP (2)
with parameter
. Similarly, if LP 2 with parameter C has primal solution (-a
#) and dual solution
a-
#) and ( -
#) are the primal and dual solutions of
LP (4) with parameter
#.
Practically we found #-LP (4) with
m#
preferable because of the interpretability of the
parameter. A more extensive discussion and development of these characteristics for SVM classification can
be found in [15]. To maintain dual feasibility, the parameter # must maintain 1
<= D <= 1. By picking #
appropriately we can force the minimum number of support vectors. We know that the number of support
vectors will be the number of points misclassified plus the points on the margin, and this was used as a
heuristic for choice of #. The reader should consult [14, 15] for a more in-depth analysis of this family of
cost functions.
3.2 Properties of LP formulation
We now examine the characteristics of LP (4) and its optimality conditions to gain insight into the properties
of LP Boosting. This will be useful in understanding both the e#ects of the choice of parameters in the
model and the performance of the eventual algorithm. The optimality conditions [11] of LP (4) are primal
feasibility:
a
dual feasibility:
and complementarity here stated as equality of the primal and dual objectives:
Complementarity can be expressed using many equivalent formulations. For example, from the complementarity
property, the following equations hold:
a
As in SVM, the optimality conditions tell us many things. First we can characterize the set of base
learners that are positively weighted in the optimal ensemble. Recall that the primal variables a i multiply
each base learner. The dual LP assigns misclassification costs u i to each point such that the u i sum to 1.
The dual constraint # m
"scores" each weak learner h .j . The score is the weighted sum of the
correctly classified points minus the weighted sum of the incorrectly classified points. The weak learners with
lower scores have greater weighted misclassification costs. The formulation is pessimistic in some sense. The
set of best weak learners for a given u will all have a score of #. The dual objective minimizes # so the optimal
misclassification cost u will be the most pessimistic one, i.e., it minimizes the maximum score over all the
learners. From the complementary slackness condition, a
the weak learners with scores equal to # can have positive weights a j in the primal space. So the resulting
ensemble will be a linear combination of the weak learners that perform best under the most pessimistic
choice of misclassification costs. This interpretation closely corresponds to the game strategy approach of
[6] (which is also a LP boosting formulation solvable by LPBoost.) A notable di#erence is that LP (5) has
an additional upper bound on the misclassification costs u, 0 # that is produced by
the introduction of the soft margin in the primal.
From SVM research, we know that both the primal and dual solutions will be sparse and the degree of
sparsity will be greatly influenced by the choice of parameter
. The size of the dual feasible region
depends on our choice of #. If # is too large, forcing D small, then the dual problem is infeasible. For large
but still feasible # (D very small but still feasible), the problem degrades to something very close to the
equal-cost case, u All the u i are forced to be nonzero. Practically, this means that as # increases,
the optimal solution is frequently a single weak learner that is best assuming equal costs. As # decreases
(D grows), the misclassification costs, u i , will increase for hard-to-classify points or points on the margin
in the label space and will go to 0 for points that are easy to classify. Thus the misclassification costs u
become sparser. If # is too small (and D too large) then the meaningless null solution, a = 0, with all points
classified as one class, becomes optimal.
For a good choice of #, a sparse solution for the primal ensemble weights a will be optimal. This implies
that few weak learners will be used. Also a sparse dual u will be optimal. This means that the solution will
be dependent only on a smaller subset of data (the support vectors.) Data with are well-classified
with su#cient margin, so the performance on these data is not critical. From LP sensitivity analysis, we
know that the u i are exactly the sensitivity of the optimal solution to small perturbations in the margin.
In some sense the sparseness of u is good because the weak learners can be constructed using only smaller
subsets of the data. But as we will see in Section 7, this sparseness of the misclassification costs can lead to
problems when practically implementing algorithms.
LPBoost Algorithms
We now examine practical algorithms for solving the LP (4). Since the matrix H has a very large number of
columns, prior authors have dismissed the idea of solving LP formulations for boosting as being intractable
using standard LP techniques. But column generation techniques for solving such LPs have existed since the
1950s and can be found in LP text books; see for example [11, Section 7.4]. Column generation is frequently
used in large-scale integer and linear programming algorithms so commercial codes such as CPLEX have
been optimized to perform column generation very e#ciently [7]. The simplex method does not require that
the matrix H be explicitly available. At each iteration, only a subset of the columns is used to determine the
current solution (called a basic feasible solution). The simplex method needs some means for determining
if the current solution is optimal, and if it is not, some means for generating some column that violates the
optimality conditions. The tasks of verification of optimality and generating a column can be performed by
the learning algorithm. A simplex-based boosting method will alternate between solving an LP for a reduced
H corresponding to the weak learners generated so far and using the weak learning algorithm to
generate the best-scoring weak learner based on the dual misclassification cost provided by the LP. This will
continue until a well-defined exact or approximate stopping criterion is reached.
The idea of column generation (CG) is to restrict the primal problem (2) by considering only a subset of
all the possible labelings based on the weak learners generated so far; i.e., only a subset -
H of the columns
of H is used. The LP solved using -
H is typically referred to as the restricted master problem. Solving the
restricted primal LP corresponds to solving a relaxation of the dual LP. The constraints for weak learners
that have not been generated yet are missing. One extreme case is when no weak learners are considered.
In this case the optimal dual solution is -
(with appropriate choice of D). This will provide the
initialization of the algorithm.
If we consider the unused columns to have -a then -a is feasible for the original primal LP. If (-u, -
#) is
feasible for the original dual problem then we are done since we have primal and dual feasibility with equal
objectives. If - a is not optimal then (-u, -
#) is infeasible for the dual LP with full matrix H. Specifically, the
# is violated for at least one weak learner. Or equivalently, # m
# for
some j. Of course we do not want to a priori generate all columns of H (H .j ), so we use our weak learner
as an oracle that either produces H.j,
# for some j or a guarantee that no such H .j exists.
To speed convergence we would like to find the one with maximum deviation, that is, the weak learning
algorithm H(S, u) must deliver a function - h satisfying
Thus -
becomes the new misclassification cost, for example i, that is given to the weak learning machine to
guide the choice of the next weak learner. One of the big payo#s of the approach is that we have a stopping
criterion. If there is no weak learner h for which
#, then the current combined hypothesis
is the optimal solution over all linear combinations of weak learners.
We can also gauge the cost of early stopping since if max h#H # m
#, for some # > 0,
we can obtain a feasible solution of the full dual problem by taking (-u, -
#). Hence, the value V of the
optimal solution can be bounded between -
#. This implies that, even if we were to potentially
include a non-zero coe#cient for all the weak learners, the value of the objective # -D # m
can only be
increased by at most #.
We assume the existence of the weak learning algorithm H(S, u) which selects the best weak learner from
a set H closed under complementation using the criterion of equation (10). The following algorithm results
Algorithm 4.1 (LPBoost).
Given as input training set: S
learners
a # 0 All coe#cients are 0
, . , 1
Corresponding optimal dual
REPEAT
Find weak learner using equation
hn #H(S,u)
Check for optimal solution:
If
H in # hn
Solve restricted master for new costs:
argmin #
s.t.
END
a # Lagrangian multipliers from last LP
return
Note that the assumption of finding the best weak learner is not essential for good performance on the
algorithm. Recall that the role of the learning algorithm is to generate columns (weak learners) corresponding
to a dual infeasible row or to indicate optimality by showing no infeasible weak learners exist. All that we
require is that the base learner return a column corresponding to a dual infeasible row. It need not be
the one with maximum infeasibility. This is merely done to improve convergence speed. In fact, choosing
columns using "steepest edge" criteria that look for the column that leads to the biggest actual change in
the objective may lead to even faster convergence. If the learning algorithm fails to find a dual infeasible
learner when one exists than the algorithm may prematurely stop at a nonoptimal solution.
small changes this algorithm can be adapted to perform any of the LP boosting formulations by
simply changing the restricted master LP solved, the costs given to the learning algorithm, and the optimality
conditions checked. Assuming the base learner solves (10) exactly, LPBoost is a variant of the dual simplex
algorithm [11]. Thus it inherits all the benefits of the simplex algorithm. Benefits include: 1) Well-defined
exact and approximate stopping criteria. Typically, ad hoc termination schemes, e.g. a fixed number of
iterations, must be used for the gradient-based boosting algorithms. 2) Finite termination at a globally
optimal solution. In practice the algorithm generates few weak learners to arrive at an optimal solution.
The optimal solution is sparse and thus uses few weak learners. 4) The algorithm is performed in the
dual space of the classification costs. The weights of the optimal ensemble are only generated and fixed at
optimality. 5) High-performance commercial LP algorithms optimized for column generation exist that do
not su#er from the numeric instability problems reported for boosting [2].
5 Confidence-rated Boosting
The derivations and algorithm of the last two sections did not rely on the assumption that L ij # {-1, +1}.
We can therefore apply the same reasoning to implementing a weak learning algorithm for a finite set of
confidence-rated functions F whose outputs are real numbers. We again assume that F is closed under
complementation. We simply define apply the same algorithm as before.
We again assume the existence of a weak learner F (S, u), which finds a function -
The only di#erence in the associated algorithm is the weak learner which now optimizes this equation.
Algorithm 5.1 (LPBoost-CRB).
Given as input training set: S
learners
a # 0 All coe#cients are 0
Corresponding optimal dual
REPEAT
Find weak learner using equation
Check for optimal solution:
H in # f n
Solve restricted master for new costs:
argmin #
s.t.
END
a # Lagrangian multipliers from last LP
return
6 LPBoost for Regression
The LPBoost algorithm can be extended to optimize any ensemble cost function that can be formulated as a
linear program. To solve alternate formulations we need only change the LP restricted master problem solved
at each iteration and the criteria given to the base learner. The only assumptions in the current approach are
that the number of weak learners be finite and that if an improving weak learner exists then the base learner
can generate it. To see a simple example of this consider the problem of boosting regression functions. We
use the following adaptation of the SVM regression formulations. This LP was also adapted to boosting
using a barrier algorithm in [13]. We assume we are given a training set of data
but now y i may take on any real value.
First we reformulate the problem slightly di#erently:
s.t. -H i a
We introduce Lagrangian multipliers (u, u #), construct the dual, and convert to a minimization problem
to yield:
s.t.
restricted to all weak learners constructed so far becomes the new master problem. If the base
learner returns any hypothesis H .j that is not dual feasible, i.e. # m
#), then the ensemble
is not optimal and the weak learner should be added to the ensemble. To speed convergence we would like
the weak learner with maximum deviation, i.e.,
This is perhaps odd at first glance because the criteria do not actually explicitly involve the dependent
variables y i . But within the LPBoost algorithm, the u i are closely related to the error residuals of the
current ensemble. If the data point x i is overestimated by the current ensemble function by more than #,
then by complementarity u i will be positive and u at the next iteration the weak learner will
attempt to construct a function that has a negative sign at point x i . If the point x i falls within the # margin
then the u and the next weak learner will try to construct a function with value 0 at that
point. If the data point x i is underestimated by the current ensemble function by more than #, then by
complementarity will be positive and u at the next iteration the weak learner will attempt to
construct a function that has a positive sign at point x i . By sensitivity analysis, the magnitudes of u and
are proportional to the changes of the objective with respect to changes in the margin.
This becomes even clearer using the approach taken in the Barrier Boosting algorithm for this problem
[13]. Equation (15) can be converted to a least squares problem. For
So the objective to be optimized by the weak learner can be transformed as follows:
The constant term v 2
can be ignored. So e#ectively the weak learner must construct a regularized least
squares approximation of the residual function.
The final regression algorithm looks very much like the classification case. The variables u i and u # i
can
be initialized to any initial feasible point. We present one such strategy here assuming that D is su#ciently
large. Here (a) denotes the plus function.

Table

1: Average Accuracy and Standard Deviations of Boosting using Decision Tree Stumps
of stumps in final ensemble
LPBoost (n) AB-100 AB-1000
Cancer
Ionosphere
Algorithm 6.1 (LPBoost-Regression).
Given as input training set: S
learners
a # 0 All coe#cients are 0
Corresponding feasible dual
REPEAT
Find weak learner using equation
Check for optimal solution:
H in # hn
Solve restricted master for new costs:
s.t.
END
a # Lagrangian multipliers from last LP
return
a
7 Computational Experiments
We performed three sets of experiments to compare the performance of LPBoost, CRB, and AdaBoost on
three classification tasks: one boosting decision tree stumps on smaller datasets and two boosting C4.5 [12].
For decision tree stumps six datasets were used. For the C4.5 experiments, we report results for four large
datasets with and without noise. Finally, to further validate C4.5, we experimented with ten more additional
datasets. The rationale was to first evaluate LPBoost where the base learner solves (10) exactly, then to
examine LPBoost in a more realistic environment by using C4.5 as a base learner. All of the datasets were
obtained from the UC-Irvine data repository [10]. For the C4.5 experiments we performed both traditional
and confidence- rated boosting.
7.1 Boosting Decision Tree Stumps
We used decision tree stumps as a base learner on the following six datasets: Cancer (9,699), Diagnostic
(30,569), Heart (13,297), Ionosphere (34,351), Musk (166,476), and Sonar (60,208). The number of features
and number of points in each dataset are shown, respectively, in parentheses. We report testing set accuracy
for each dataset based on 10-fold Cross Validation (CV). We generate the decision tree stumps based on the
mid-point between two consecutive points for a given variable. Since there is limited confidence information
in stumps, we did not perform confidence-rated boosting. All boosting methods search for the best weak
learner which returns the least weighted misclassification error at each iteration. LPBoost can take advantage
of the fact that each weak learner need only be added into the ensemble once. Thus once a stump is added
to the ensemble it is never evaluated by the learning algorithm again. The weights of the weak learners are
adjusted dynamically by the LP. This is an advantage over AdaBoost, since AdaBoost adjust weights by
repeatedly adding the same weak learner into the ensemble.
The parameter # for LPBoost was set using a simple heuristic: 0.1 added to previously-reported error
rates on each dataset in [4] except for the Cancer dataset. Specifically the values of # in the same order
of the datasets given above were (0.2, 0.1, 0.25, 0.2, 0.25, 0.3 ). Results for AdaBoost were reported for a
maximum number of iterations of 100 and 1000. The 10-fold average classification accuracies and standard
deviations are reported in Table 1.
LPBoost performed very well both in terms of classification accuracy, number of weak learners, and
training time. There is little di#erence between the accuracy of LPBoost and the best accuracy reported
for AdaBoost using either 100 or 1000 iterations. The variation in AdaBoost for 100 and 1000 iterations
illustrates the importance of well-defined stopping criteria. Typically, AdaBoost only obtains its solution in
the limit and thus stops when the maximum number of iterations (or some other heuristic stopping criteria)
is reached. There is no magic number of iterations good for all datasets. LPBoost has a well-defined stopping
criterion that is reached in a few iterations. It uses few weak learners. There are only 81 possible stumps
on the Breast Cancer dataset (nine attributes having nine possible values), so clearly AdaBoost may require
the same tree to be generated multiple times. LPBoost generates a weak learner only once and can alter
the weight on that weak learner at any iteration. The run time of LPBoost is proportional to the number
of weak learners generated. Since the LP package that we used, CPLEX 4.0 [7], is optimized for column
generation, the cost of adding a column and reoptimizing the LP at each iteration is small. An iteration
of LPBoost is only slightly more expensive that an iteration of AdaBoost. The time is proportional to the
number of weak learners generated. For problems in which LPBoost generates far fewer weak learners it is
much less computationally costly.
In the next subsection, we test the practicality of our methodology on di#erent datasets using C4.5.
7.2 Boosting C4.5
LPBoost with C4.5 as the base algorithm performed well after some operational challenges were solved.
In concept, boosting using C4.5 is straightforward since the C4.5 algorithm accepts misclassification costs.
One problem is that C4.5 only finds a good solution not guaranteed to maximize (10). This can e#ect the
convergence speed of the algorithm and may cause the algorithm to terminate at a suboptimal solution.
Another challenge is that the misclassification costs determined by LPBoost are sparse, i.e.
of the points. The dual LP has a basic feasible solution corresponding to a vertex of the dual feasible region.
Only the variables corresponding to the basic solution can be nonnegative. So while a face of the region
corresponding to many nonnegative weights may be optimal, only a vertex solution will be chosen. In practice
we found that when many LPBoost converged slowly. In the limited number of iterations that we
allowed (25), LPBoost frequently failed to find weak learners that improved significantly over the initial
equal cost solution. The weak learners generated using only subsets of the variables were not necessarily
good over the full data set. Thus the search was too slow. Alternative optimization algorithms may alleviate
this problem. For example, an interior point strategy may lead to significant performance improvements.
Note that other authors have reported problems with underflow of boosting [2]. When LPBoost was solved
to optimality on decision tree stumps with full evaluation of the weak learners, this problem did not occur.
Boosting unpruned decision trees helped somewhat but did not completely eliminate this problem.
Stability and convergence speed was greatly improved by adding minimum misclassification costs to the

Table

2: Large Dataset Results from Boosting C4.5
LPBoost CRB AdaBoost C4.5
Original Forest 0.7226 0.7259 0.7370 0.6638
Original Adult 0.8476 0.8461 0.8358 0.8289
Original USPS 0.9123 0.9103 0.9103 0.7833
Original OptDigits 0.9249 0.9355 0.9416 0.7958
dual
min
and
. The corresponding primal problem is
The primal problem maximizes two measures of soft margin: # corresponds to the minimum margin obtained
by all points and # i measures the additional margin obtained by each point. AdaBoost also minimizes a
margin cost function based on the margin obtained by each point.
This is just one method of boosting multiclass problems. Further investigation of multiclass approaches is
needed. We ran experiments on larger datasets: Forest, Adult, USPS, and Optdigits from UCI[10]. LPBoost
was adopted to the multiclass problem by defining h j instance x i is correctly classified by weak
learner h j and -1 otherwise. Forest is a 54-dimension dataset with seven possible classes. The data are
divided into 11340 training, 3780 validation, and 565892 testing instances. There are no missing values.
The 15-dimensional Adult dataset has 32562 training and 16283 testing instances. One training point that
has a missing value for a class label has been removed. We use 8140 instances as our training set and the
remaining 24421 instances as the validation set. Adult is a two-class dataset with missing values. The default
handling in C4.5 has been used for missing values. USPS and Optdigits are optical character recognition
datasets. USPS has 256 dimensions without missing value. Out of 7291 original training points, we use
1822 points as training data and the rest 5469 as validation data. There are 2007 test points. Optdigits
on the other hand has 64 dimensions without missing values. Its original training set has 3823 points. We
use 955 of them as training data and the remaining 2868 as validation data. Parameter selection for both
LPBoost and AdaBoost was done based on validation set results. Since initial experiments resulted in the
same parameter set for both LPBoost and CRB, we set the parameters equal for CRB and LPBoost to
expedite computational work. In order to investigate the performance of boosted C4.5 with noisy data, we
introduced 15% label noise for all four datasets.
The # parameter used in LPBoost and the number of iterations of AdaBoost can significantly a#ect
their performance. Thus accuracy on the validation set was used to pick the parameter # for LPBoost and
the number of iterations for AdaBoost. Due to the excessive computational work, we limit the maximum
number of iterations at 25 for all boosting methods as in [2]. We varied parameter # between 0.03 and 0.11.
Initial experiments indicated that for very small # values, LPBoost results in one classifier which assigns all
training points to one class. On the other extreme, for larger values of #, LPBoost returns one classifier
Parameter0.800.840.03
Parameter0.800.84
(a) Forest Dataset (b) Adult Dataset
Parameter0.900.94
Parameter0.920.96
(c) USPS Dataset (d) Optdigits Dataset

Figure

1: Validation Set Accuracy by # Value. Triangles are no noise and circles are with noise.
which is equal to the one found in the first iteration. Figure 1 shows the validation set accuracy for LPBoost
on all four datasets. Based on validation set results, we use (22,19), (25,4), (22,25), and (25,25) number
of iterations for original and 15%noisy data respectively for AdaBoost in the Forest, Adult, USPS, and
Optdigits datasets. The testing set results using the value of # with the best validation set accuracy are
given in Table 2. LPBoost was very comparable with AdaBoost in terms of CPU time. As seen in Table
2, LPBoost is also comparable with AdaBoost in terms of classification accuracy when the validation set is
used to pick the best parameter settings. AdaBoost performs better in the case of noisy data. CRB is the
least e#ective method in terms of classification accuracy among boosting methods. All boosting methods
outperform C4.5.
The computational costs of 25 iterations of LPBoost (either variant) and AdaBoost were very similar. We
provide some sample CPU times. These timings should be considered only rough estimates. Our experiments
were performed on a cluster of IBM RS-6000s used in batch mode. Since the machines are not all identical
and are subject to varying loads, run times vary considerable from run to run. For each dataset we give
the seconds of CPU time on an RS-6000: Forest AdaBoost =717, LPBoost = 930; Adult AdaBoost = 107,
We also conducted experiments by boosting C4.5 on small datasets. Once again there was no strong
evidence of superiority of any of the boosting approaches. In addition to six UCI datasets used in decision
tree stumps experiments, we use four additional UCI datasets here. These are the House(16,435), Hous-
datasets. As in the decision tree stumps experiments, we
report results from 10-fold CV. Since the best # value for LPBoost varies between 0.05 and 0.1 for the large
datasets, we pick parameter the small datasets. Results are reported in Table 3. C4.5 performed
the best on the House dataset. AdaBoost performed the best in four datasets out of ten. LPBoost and CRB
had the best classification performance for three and two datasets respectively. When we drop CRB in Table
2 The continuous response variable of Housing dataset was categorized at 21.5.

Table

3: Small Dataset Results from Boosting C4.5
LPBoost CRB AdaBoost C4.5
Cancer 0.9585 -
House 0.9586 -
Housing
Ionosphere 0.9373 -
3, LPBoost would in this case perform the best in five datasets, although the parameter # has not been
tuned.
8 Discussion and Extensions
We have shown that LP formulations of boosting are both attractive theoretically in terms of generalization
error bound and computationally via column generation. The LPBoost algorithm can be applied to any
boosting problem formulated as an LP. We examined algorithms based on the 1-norm soft margin cost
functions for support vector machines. A generalization error bound was found for the classificaiton case.
The LP optimality conditions allowed us to provide explanations for how the methods work. In classification,
the dual variables act as misclassification costs. The optimal ensemble consists of a linear combination of
learners that work best under the worst possible choice of misclassification costs. This explanation
is closely related to that of [6]. For regression as discussed in the Barrier Boosting approach to the same
formulation [13], the dual multipliers act like error residuals to be used in a regularized least square problem.
We demonstrated the ease of adaptation to other boosting problems by examining the confidence-rated
and regression cases. Extensive computational experiments found that the method performed well versus
AdaBoost both with respect to classification quality and solution time. We found little clear benefit for
confidence-rated boosting of C4.5 decision trees. From an optimization perspective, LPBoost has many
benefits over gradient-based approaches: finite termination, numerical stability, well-defined convergence
criteria, fast algorithms in practice, and fewer weak learners in the optimal ensemble. LPBoost may be more
sensitive to inexactness of the base learning algorithm. But through modification of the base LP, we were able
to obtain very good performance over a wide spectrum of datasets even in the boosting decision trees where
the assumptions of the learning algorithm were violated. The questions of what is the best LP formulation
for boosting and the best method for optimizing the LP remain open. Interior point column generation
algorithms may be much more e#cient. But clearly LP formulations for classification and regression are
tractable using column generation, and should be the subject of further research.

Acknowledgements

This material is based on research supported by Microsoft Research, NSF Grants 949427 and IIS-9979860,
and the European Commission under the Working Group Nr. 27150 (NeuroCOLT2).



--R

Learning in Neural Networks
An empirical comparison of voting classification algorithms: Bagging
Combining support vector and mathematical programming methods for classification.

A column generation approach to boosting.
Prediction games and arcing algorithms.

An Introduction to Support Vector Machines.
Generalized support vector machines.
UCI repository of machine learning databases.
New York

Barrier boosting.
Robust ensemble learning.

Boosting the margin: A new explanation for the e
Improved boosting algorithms using confidence-rated predictions
Structural risk minimization over data-dependent hierarchies
Margin distribution bounds on generalization.
Analysis of regularised linear functions for classification problems.
--TR

--CTR
Cynthia Rudin , Ingrid Daubechies , Robert E. Schapire, The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins, The Journal of Machine Learning Research, 5, p.1557-1595, 12/1/2004
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
Robust Loss Functions for Boosting, Neural Computation, v.19 n.8, p.2183-2244, August 2007
Yi Zhang , Samuel Burer , W. Nick Street, Ensemble Pruning Via Semi-definite Programming, The Journal of Machine Learning Research, 7, p.1315-1338, 12/1/2006
Yijun Sun , Sinisa Todorovic , Jian Li, Increasing the Robustness of Boosting Algorithms within the Linear-programming Framework, Journal of VLSI Signal Processing Systems, v.48 n.1-2, p.5-20, August    2007
Michael Collins, Parameter estimation for statistical parsing models: theory and practice of distribution-free methods, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
Axel Pinz, Object categorization, Foundations and Trends in Computer Graphics and Vision, v.1 n.4, p.255-353, December 2005
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
linear programming;boosting;ensemble learning;soft margin;sparseness