A geometric approach to leveraging weak learners.
AdaBoost is a popular and effective leveraging procedure for improving the hypotheses generated by weak learning algorithms. AdaBoost and many other leveraging algorithms can be viewed as performing a constrained gradient descent over a potential function. At each iteration the distribution over the sample given to the weak learner is proportional to the direction of steepest descent. We introduce a new leveraging algorithm based on a natural potential function. For this potential function, the direction of steepest descent can have negative components. Therefore, we provide two techniques for obtaining suitable distributions from these directions of steepest descent. The resulting algorithms have bounds that are incomparable to AdaBoost's. The analysis suggests that our algorithm is likely to perform better than AdaBoost on noisy data and with weak learners returning low confidence hypotheses. Modest experiments confirm that our algorithm can perform better than AdaBoost in these situations.
Introduction
Algorithms like AdaBoost [7] that are able to improve the hypotheses generated
by weak learning methods have great potential and practical benefits. We call
any such algorithm a leveraging algorithm, as it leverages the weak learning
method. Other examples of leveraging algorithms include bagging [3], arc-x4 [5],
and LogitBoost [8].
One class of leveraging algorithms follows the following template to construct
master hypotheses from a given sample
The leveraging algorithm begins with a default master hypothesis H 0
and then for
- Constructs a distribution D t over the sample (as a function of the
sample and the current master hypothesis H possibly t).
- Trains a weak learner using distribution D t over the sample to obtain
a weak hypothesis h t .
Picks ff t and creates the new master hypothesis,
authors were supported by NSF Grant CCR 9700201.
This is essentially the Arcing paradigm introduced by Breiman [5, 4] and the
skeleton of AdaBoost and other boost-by-resampling algorithms [6, 7]. Although
leveraging algorithms include arcing algorithms following this template, leveraging
algorithms are more general. In Section 2, we introduce the GeoLev algorithm
that changes the examples in the sample as well as the distribution over them.
In this paper we consider 2-class classification problems where each y
+1g. However, following Schapire and Singer [15], we allow the weak learner's
hypotheses to be "confidence rated," mapping the domain X to the real num-
bers. The sign of these numbers gives the predicted label, and the magnitude is a
measure of confidence. The master hypotheses produced by the above template
are interpreted in the same way.
Although the underlying goal is to produce hypotheses that generalize well,
we focus on how quickly the leveraging algorithm decreases the sample error.
There are a variety of results bounding the generalization error in terms of the
performance on the sample [16].
Given a sample the margin of a hypothesis h on instance
x i is y i h(x i ) and the margin of h on the entire sample is the vector
hypothesis that correctly labels the sample has a margin
vector whose components are all positive. Focusing on these margin vectors
provides a geometric intuition about the leveraging problem.
In particular, a potential function on margin space can be used to guide the
choices of D t and ff t . The distribution D t is the direction of steepest descent
and ff t is the value that minimizes the potential of H Leveraging
algorithms that can be viewed in this way perform a feasible direction descent
on the potential function. An amortized analysis using this potential function can
often be used to bound the number of iterations required to achieve zero sample
error. These potential functions give insight into the strengths and weaknesses
of various leveraging algorithms.
Boosting algorithms have the property that they can convert weak PAC
learning algorithms into strong PAC learning algorithms. Although the theory
behind the Adaboost algorithm is very elegant, it leads to the somewhat intriguing
result that minimizing the normalization factor of a distribution will
reduce the training error [14, 15]. Our search for a better understanding of how
AdaBoost reduces the sample error led to our geometric algorithms, GeoLev and
GeoArc. Although the performance bounds for these algorithms are too poor to
show that they have the boosting property, these bounds are incomparable to
AdaBoost's in that they are better when the weak hypotheses contain mostly
low-confidence predictions.
The main contributions of this paper are as follows:
We use a natural potential function to derive a new algorithm for leveraging
learners, called GeoLev (for Geometric Leveraging algorithm).
We highlight the relationship between AdaBoost, Arcing and feasible direction
linear programming [10].
- We use our geometric interpretation to prove convergence bounds on the
algorithm GeoLev. These bound the number of iterations taken by GeoLev
to achieve ffl classification error on the training set.
We provide a general transformation from GeoLev to an arcing algorithm
GeoArc, for which the same bounds hold.
We summarize some preliminary experiments with GeoLev and GeoArc.
We motivate a novel algorithm, GeoLev, by considering the geometry of "margin
space." Since many empirical and analytical results show that good margins on
the sample lead to small generalization error [2, 16], it is natural to seek a master
hypothesis with large margins. One heuristic is to seek a margin vector with
uniformly large margins, i.e. a vector parallel to 1). This indicates
that the master hypothesis is correct and equally confident on every instance in
the sample. The GeoLev algorithm exploits this heuristic by attempting to find
hypotheses whose margin vectors are as close as possible to the 1 direction.
We now focus on a single iteration of the leveraging process, dropping the
time subscripts. Margin vectors will be printed in bold face and often normalized
to have Euclidean length one. Thus H is the margin vector of the master
hypothesis H , whose i th component is
Let the goal vector,
p m), be 1 normalized to length one.
Recall that m is the sample size, so all margin vectors lie in ! m , and normalized
margin vectors lie on the m dimensional unit sphere. Note that it is easy to
re-scale the confidences - multiplying the predictions of any hypothesis H by a
constant does not change the direction of H's margin vector. Therefore we can
assume the appropriate normalization without loss of generality.
The first decision taken by the leverager is what distribution D to place on
the sample. Since distribution D has m components, it can also be viewed as a
(non-negative) vector in ! m .
The situation in margin-space at the start of the iteration is shown in Figure
1. In order to decrease the angle ' between H and g we must move the head
of H towards g. All vectors at angle ' to the goal vector g lie on a cone, and
their normalizations lie on the "rim" shown in the figure.
If h, the weak hypothesis's margin vector (which need not have unit length),
is parallel to H or tangent to the "rim", then no addition of h to H can decrease
the angle to g. On the other hand, if the line H cuts through the cone,
then the angle to the goal vector g can be reduced by adding some multiple of
h to H. The only time the angle to g cannot be decreased is when the h vector
lies in the plane P which is tangent to the cone and contains the vector H, as
shown in Figure 2.
theta
Fig. 1. Situation in margin space at the start of an iteration.
If the weak learner learns at all, then its hypothesis h is better than random
guessing, so the learners "edge", E i-D (y i h(x i )), will be positive. This means
that D \Delta h is positive, and if distribution D (viewed as a margin vector) is
perpendicular to plane P then h lies above P . Therefore the leverager is able to
use h to reduce the angle between H and g.
As suggested by the figures, the appropriate direction for D is
In general neither jjDjj
If all components of D are positive, it can be normalized to yield a distribution
on the sample for the weak learner. However, it is possible for some
components of D to be negative. In this case things are more complicated 1 . If a
component of D is negative, then we flip both the sign of that component and
the sign of the corresponding label in the sample. This creates a new direction
D 0 which can be normalized to a distribution D 0 and a new sample S 0 with the
same x i 's but (possibly) new labels y 0
. The modified sample S 0 and distribution
D 0 are then used to generate a new weak hypothesis, h. Let h 0 be the margins
of h on the modified sample S 0 , so h 0
In fact it is this complication which differentiates GeoLev from Arcing algorithms.
Arcing algorithms are not permitted to change the sample in this way. A second
transformation avoiding the label flipping is discussed in section 5.
Fig. 2. The direction D for the distribution used by GeoLev.
as the sign flips cancel.
The second decision taken by the algorithm is how to incorporate the weak
hypothesis h into its master hypothesis H . Any weak hypothesis with an "edge"
on the distribution D described above can be used to decrease '. Our goal is
to find the coefficient ff so that H
jjH+ffhjj2 decreases this angle as much as
possible. Taking derivatives shows that ' is minimized when
From this discussion we can see that GeoLev performs a kind of gradient
descent. If we consider the angle between g and the current H as a potential on
margin space, then D is the direction of steepest descent. Moving in a direction
that approximates this gradient takes us towards the goal vector. Since we have
only little control over the hypotheses returned by the weak learner, an approximation
to this direction is the best we can do. The step size is chosen adaptively
to make as much use of the weak hypothesis as possible.
The GeoLev Algorithm is summarized in Figure 3.
3 Relation to Previous Work
Breiman [5, 4] defines arcing algorithms using potential functions that can be expressed
as component-wise functions of the margins having the form 2
Breiman allows the component-wise potential f to depend on the sum of the ff i 's in
some arcing algorithms.
Input: A sample
a weak learning algorithm.
Initialize master hypothesis H to predict 0 everywhere
m)
Repeat:
do
if
add
else
add
do
call weak learner with distribution D over S 0 , obtaining hypothesis h
Fig. 3. The GeoLev Algorithm.
Breiman shows that, under certain conditions on f , arcing algorithms converge
to good hypotheses in the limit. Furthermore, he shows that AdaBoost is an arcing
algorithm with is an arcing algorithm with polynomial
f(x).
For completeness, we describe the AdaBoost algorithm and show in our notation
how it is performing feasible direction gradient descent on the potential
function
AdaBoost fits the template outlined in the introduction,
choosing the distribution
Z
where Z is the normalizing factor so that D sums to 1. The master hypothesis
is updated by adding in a multiple of the new weak hypothesis. The coefficient
ff is chosen to minimize
exp
the next iteration's Z value. Unlike GeoBoost, the margin vectors of AdaBoost's
hypotheses are not normalized.
We now show that AdaBoost can be viewed as minimizing the potential
by approximate gradient descent. The direction of steepest descent (w.r.t. the
components of the margin vector) is proportional to (5), the distribution AdaBoost
gives to the weak learner.
Continuing the analogy, the coefficient ff given to the new hypothesis should
minimize the potential, X
of the updated master hypothesis, which is identical to (6). Thus AdaBoost's
behavior is approximate gradient descent of the function defined in (7), where the
direction of descent is the weak learner's hypothesis. Furthermore, the bounds on
AdaBoost's performance proven by Schapire and Singer are implicitly performing
an amortized analysis over the potential function (8).
Arc-x4 also fits the template outlined in the introduction, keeping an unnormalized
master hypothesis. In our notation the distribution chosen at trial t is
proportional to
This algorithm can also be viewed as a gradient descent on the potential function
at the t th iteration. Rather than computing the coefficient ff as a function of
the weak hypothesis, arc-x4 always chooses ff = 1. Thus each h t has weight 1=t
in the master hypothesis, as in many gradient descent methods. Unfortunately,
the dependence of the potential function on t makes it difficult to use in an
amortized analysis.
This connection to gradient descent was hinted at by Freund [6] and noted by
Breiman and others [4, 8, 13]. Our interpretation generalizes the previous work
by relaxing the constraints on the potential function. In particular, we show how
to construct algorithms from potential functions where the direction of steepest
descent can have negative components. The potential function view of leveraging
algorithms shows their relationship to feasible descent linear programming, and
this relationship provides insight into the role of the weak learner.
Feasible direction methods try to move in the direction of steepest descent.
However, they must remain in the feasible region described by the constraints. A
descent direction is chosen that is closest to the (negative) gradient \Gammarf while
satisfying the constraints. For example, in a simplified Zoutendijk method, the
chosen direction d satisfies the constraints and maximizes \Gammarf \Delta d . Similarly, the
leveraging algorithms discussed are constrained to produce master hypotheses
lying in the span of the weak learner's hypothesis class. One can view the role
of the weak learner as finding a feasible direction close to the given distribution
(or negative gradient). In fact the weak learning assumption used in boosting
and in the analysis of GeoLev implies that there is always a feasible direction d
such that \Gammarf \Delta d is bounded above zero.
The gradient descent framework outlined above provides a method for deriving
the corresponding leveraging algorithm from smooth potential functions
over margin space.
The potential functions used by AdaBoost and arc-x4 have the advantage
that all the components of their gradients D are positive, and thus it is easy
to convert D into a distribution. On the other hand, the methods outlined in
the previous section and section 5 can be used to handle gradients with negative
components. The approach used by R-atsch et al. [13] can similarly be interpreted
as a potential function of the margins.
Recently, Friedman et al. [8] have given a maximum likelihood motivation
for AdaBoost, and introduced another leveraging algorithm based on the log-likelihood
criteria. They indicate that minimizing the square loss potential,
performed less well in experiments than other monotone potentials, and
conjecture that its non-monotonicity (penalizing margins greater than 1) is a
contributing factor. Our methods described in section 5 may provide a way to
ameliorate this problem.
Convergence Bound
In this section we examine the number of iterations required by GeoLev to
achieve classification error ffl on the sample. The key step shows how the sine
of the angle between the goal vector g and the master hypothesis H is reduced
each iteration. Upper bounding the resulting recurrence gives a bound on how
rapidly the training error decreases.
We begin by considering a single boosting iteration. The margin space quantities
are as previously defined (recall that g and H are 2-normed,
while D and h are not). In addition, let H 0 denote the new master hypothesis
at the end of the iteration, and ' 0 the angle between H 0 and g. We assume
throughout that the sample is finite.
(D \Delta h) to be the edge of the weak learner's hypothesis h with
respect to the distribution given to the weak learner. Our bound on the decrease
in ' will depend on h only through r and jjhjj 2 . Note that r was chosen to
maintain consistency with the work of Schapire and Singer [15] and that
At the start of the iteration
and at
the end of the iteration sin(' 0
Recall that
H 0 is H+ ffh normalized, and since H already has unit length,
Lemma 1. The value cos 2 (' 0 ) is maximized (and sin(' 0 ) minimized) when
(g
Proof The lemma follows from examination of the first and second derivatives
of cos 2 (' 0 ) with respect to ff. 2
Using this value of ff a little algebra shows that
Although we desire bounds that hold for all h, we find it convenient to first
minimize (15) with respect to (H \Delta h). The remaining dependence on h will be
expressed as a function of r and jjhjj 2 in the final bound.
Lemma 2. Equation (15) is minimized when (H
Proof Again the lemma follows after examining the first and second derivatives
with respect to (H \Delta h). 2
This considerably simplifies (15), yielding
(D
Recall that
(D
Therefore,
We will bound this in two ways, using different bounds on jjDjj 1 . The first
of these bounds is derived by noting that jjDjj 1 - jjDjj 2 . Recall that
('). Combining this with (18)
and the bound on jjDjj 1 yields
sin
s
jjhjj 2: (20)
Repeated application of this bound yields the following theorem.
Theorem 1. If r are the edges of the weak learner's hypotheses during
the first T iterations, then the sine of the angle between g and the margin vector
for the master hypothesis computed at iteration T is at most
Y
s
We can bound jjDjj 1 another way to obtain a a bound which is often better.
Note that jjDjj 1 - (D \Delta
Substituting this
into (18) and continuing as before yields
sin
Continuing as above results in the following theorem.
Theorem 2. Let r be the edges of the weak learner's hypotheses and
be the angles between g and the margins of the master hypotheses at
the start of the first T iterations. If ' T+1 is the angle between g and the margins
of the master hypothesis produced at iteration T then
Y
s
To relate these results to the sample error we use the following lemma.
Lemma 3. If sin(') !
is the angle between g and a master hypothesis
H, then the sample error of H is less than ffl.
Proof Assume sin(') !
R=m, so
is 2-normed, this can only hold if H has more than m
positive components. Therefore the master hypothesis correctly classifies more
examples and the sample error rate is at most (R \Gamma 1)=m. 2
Combining Lemma 3 and Theorem 2 gives the following corollary.
Corollary 1. After iteration T , the sample error rate of GeoLev's master hypothesis
is bounded by
Y
The recurrence of Theorem 2 is somewhat difficult to analyze, but we can
apply the following lemma from Abe et al. [1].
Lemma 4. Consider a sequence fg t g of non-negative numbers satisfying g t+1 -
positive constant. If f
c
all t 2 N .
Given a lower bound r on the r t values and an upper bound H 2 on jjh t jj 2 ,
then we can apply this lemma to recurrence (22). Setting
and
H 2m shows that
sin 2: (25)
This, and the previous results lead to the following theorem.
Theorem 3. If the weak learner always returns hypotheses with an edge greater
than r and H 2 is an upper bound on jjh t jj 2 , then GeoLev's hypothesis will have
at most ffl training error after
iterations.
Similar bounds have been obtained by Freund and Schapire [7] for AdaBoost.
Theorem 4. After T iterations, the sample error rate of AdaBoost's master
hypothesis is at most
Y
s
2: (27)
The dependence on jjhjj 1 is implicit in their bounds and and can be removed
when h t
Comparing Corollary 1 and Theorem 4 leads to the following observations.
First, the bound on GeoLev does not contain the square-root. If this were the
only difference, then it would correspond to a halving of the number of iterations
required to reach error rate ffl on the sample. This effect can be approximated by
a factor of 2 on the r 2 terms.
A more important difference is the factors multiplying the r 2 terms. With
the preceding approximation GeoLev's bound has 2m sin 2 (' t )=jjh t jj 2
aboost's bound has 1/jjh t jj 2
1 . The larger this factor the better the bound. The
dependence on sin 2 (' t ) means that GeoLev's progress tapers off as it approaches
zero sample error.
If the weak hypotheses are equally confident on all examples, then jjh t jj 2
2 is
times larger than jjh t jj 2
1 and the difference in factors is simply 2 sin 2 (' t ). At
the start of the boosting process ' t is close -=2 and GeoLev's factor is larger.
However, sin 2 (' t ) can be as small as 1=m before GeoLev predicts perfectly on the
sample. Thus GeoLev does not seem to gain as much from later iterations, and
this difficulty prevents us from showing that GeoLev is a boosting algorithm.
On the other hand, consider the less likely situation where the weak hypotheses
produce a confident prediction for only one sample point, and abstain
on the rest. Now jjh t jj 2
1 , and GeoLev's bound has an extra factor of
about 2m sin 2 (' t ). GeoLev's bounds are uniformly better 3 than AdaBoost's in
this case.
5 Conversion to an Arcing Algorithm
The GeoLev algorithm discussed so far does not fit the template for Arcing
algorithms because it modifies the labels in the sample given to the weak learner.
3 We must switch to recurrence (20) rather than recurrence (22) when sin 2 (' t ) is very
small.
This also breaks the boosting paradigm as the weak learner may be required to
produce a good hypothesis for data that is not consistent with any concept in
the underlying concept class. In this section we describe a generic conversion
that produces arcing algorithms from leveraging algorithms of this kind without
placing an additional burden on the weak learner. Throughout this section we
assume that the weak learner's hypotheses produce values in [\Gamma1; +1].
The conversion introduces an wrapper between the weak learner and leveraging
algorithm that replaces the sign-flip trick of section 2. This wrapper takes the
weighting D from the leveraging algorithm, and creates the distribution
by setting all negative components to zero and re-normalizing. This modified
distribution D 0 is then given to the weak learner, which returns a hypothesis h
with a margin vector h. The margin vector is modified by the wrapper before
being passed on to the leveraging algorithm: if D(x i ) is negative then h i is set
to \Gamma1. Thus the leveraging algorithm sees a modified margin vector h 0 which it
uses to compute ff and the margins of the new master hypothesis.
The intuition is that the leveraging algorithm is being fooled into thinking
that the weak hypothesis is wrong on parts of the sample when it is actually
correct. Therefore the margins of the master hypothesis are actually better than
those tracked by the leveraging algorithm. Furthermore, the apparent "edge" of
the weak learner can only be increased by this wrapping transformation. This
intuition is formalized in the following theorems.
Theorem 5. If
is the edge of the weak learner with
respect to the distribution it sees, and r
is the edge of the
modified weak hypothesis with respect to the (signed) weighting D requested by
the leveraging algorithm, then r 0 - r.
Proof
ensures that both D 0 otherwise, and
The assumption on h implies r - 1, so r 0 is minimized at
Theorem 6. No component of the master margin vector
t used by
the wrapped leveraging algorithm is ever greater than the actual margins of the
master hypothesis
Proof The theorem follows immediately by noting that each component of h 0
is no greater than the corresponding component of h t . 2
We call the wrapped version of GeoLev, GeoArc, as it is an Arcing algorithm.
It is instructive to examine the potential function associated with GeoArc:
ip
min
This potential has a similar form to the following potential function which is
zero on the entire positive orthant:
ip
The leveraging framework we have described together with this transformation
enables the analysis of some undifferentiable potential functions. The full
implications of this remain to be explored.
6 Preliminary Experiments
We performed experiments comparing GeoLev and GeoArc to AdaBoost on a
set of 13 datasets(the 2 class ones used in previous experiments) from the UCI
repository. These experiments were run along the same lines as those reported
by Quinlan [12]. We ran cross validation on the datasets for
two class classification. All leveraging algorithms ran for 25 iterations, and used
single node decision trees as implemented in MLC++ [9] for the weak hypotheses.
Note that these are \Sigma1 valued hypotheses, with large 2-norms. It was noticed
that the splitting criterion used for the single node had a large impact on the
results. Therefore, the results reported for each dataset are those for the better of
mutual information ratio and gain ratio. We report only a comparison between
AdaBoost and GeoLev, GeoArc performed comparably to GeoLev. The results
are illustrated in figure 4. This figure is a scatter plot of the generalization error
on each of the datasets. These results appear to indicate that the new algorithms
are comparable to AdaBoost.
Further experiments are clearly warranted and we are especially interested
in situations where the weak learner produces hypotheses with small 2-norm.
7 Conclusions and Directions for Further Study
We have presented the GeoLev and GeoArc algorithms which attempt to form
master hypotheses that are correct and equally confident over the sample. We
found it convenient to view these algorithms as performing a feasible direction
gradient descent constrained by the hypotheses produced by the weak learner.
The potential function used by GeoLev is not monotonic: its gradient can have
negative components. Therefore the direction of steepest descent cannot simply
be normalized to create a distribution for the weak learner.
We described two ways to solve this problem. The first constructing a modified
sample by flipping some of the labels. This solution is mildly unsatisfying as
it strengthens the requirements on the weak learner - the weak learner must now
deal with a broader class of possible targets. Therefore we also presented a second
transformation that does not increase the requirements on the weak learner.
In fact, using this second transformation can actually improve the efficiency of
GeoLev
AdaBoost
Fig. 4. Generalization error of GeoLev versus AdaBoost after 25 rounds.
the leveraging algorithm. One open issue is whether or not this improvement
can be exploited to improve GeoArc's performance bounds. A second open issue
is to determine the effectiveness of these transformations when applied to other
non-monotonic potential functions, such as those considered by Mason et al. [11].
We have upper bounded the sample error rate of the master hypotheses
produced by the GeoLev and GeoArc algorithms. These bounds are incomparable
with the analogous bounds for AdaBoost. The bounds indicate that Ge-
oLev/GeoArc may perform slightly better at the start of the leveraging process
and when the weak hypotheses contain many low-confidence predictions. On
the other hand, the bounds indicate that GeoLev/GeoArc may not exploit later
iterations as well, and may be less effective when the weak learner produces
valued hypotheses. These disadvantages make it unlikely that the GeoArc
algorithm has the boosting property.
One possible explanation is that GeoLev/GeoArc aim at a cone inscribed in
the positive orthant in margin space. As the sample size grows, the dimension of
the space increases and the volume of the cone becomes a diminishing fraction of
the positive orthant. AdaBoost's potential function appears better at navigating
into the "corners" of the positive orthant.
However, our preliminary tests indicate that after 25 iterations the generalization
errors of GeoArc/GeoLev are similar to AdaBoost's on 13 classification
datasets from the UCI repository. These comparisons used 1-node decision tree
classifiers as the weak learning method. It would be interesting to compare their
relative performances when using a weak learner that produces hypotheses with
many low-confidence predictions.

Acknowledgments

We would like to thank Manfred Warmuth,Robert Schapire, Yoav Freund, Arun
Jagota, Claudio Gentile and the EuroColt program committee for their useful
comments on the preliminary version of this paper.



--R

Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence
A training algorithm for optimal margin classifiers.
Bagging predictors.
Arcing the edge.

Boosting a weak learning algorithm by majority.
A decision-theoretic generalization of on-line learning and an application to boosting
Additive logistic re- gression: a statistical view of boosting
Data mining using MLC

Improved generalization through explicit optimization of margins.
Bagging, boosting and c4.
margins for adaboost.
Boosting the margin: a new explanation for the effectiveness of voting methods.
Improved boosting algorithms using confidence-rated predictions
Estimation of Dependences Based on Empirical Data.
--TR
A theory of the learnable
What size net gives valid generalization?
Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence
Equivalence of models for polynomial learnability
A training algorithm for optimal margin classifiers
The design and analysis of efficient learning algorithms
Learning Boolean formulas
An introduction to computational learning theory
Boosting a weak learning algorithm by majority
Bagging predictors
Exponentiated gradient versus gradient descent for linear predictors
A decision-theoretic generalization of on-line learning and an application to boosting
General convergence results for linear discriminant updates
An adaptive version of the boost by majority algorithm
Drifting games
Additive models, boosting, and inference for generalized divergences
Boosting as entropy projection
Prediction games and arcing algorithms
Improved Boosting Algorithms Using Confidence-rated Predictions
An Empirical Comparison of Voting Classification Algorithms
Margin Distribution Bounds on Generalization
classification;boosting;learning;gradient descent;ensemble methods