Margins for AdaBoost.
Recently ensemble methods like ADABOOST have been applied successfully in many problems, while seemingly defying the problems of overfitting.ADABOOST rarely overfits in the low noise regime, however, we show that it clearly does so for higher noise levels. Central to the understanding of this fact is the margin distribution. ADABOOST can be viewed as a constraint gradient descent in an error function with respect to the margin. We find that ADABOOST asymptotically achieves a hard margin distribution, i.e. the algorithm concentrates its resources on a few hard-to-learn patterns that are interestingly very similar to Support Vectors. A hard margin is clearly a sub-optimal strategy in the noisy case, and regularization, in our case a mistrust in the data, must be introduced in the algorithm to alleviate the distortions that single difficult patterns (e.g. outliers) can cause to the margin distribution. We propose several regularization methods and generalizations of the original ADABOOST algorithm to achieve a soft margin. In particular we suggest (1) regularized ADABOOSTREG where the gradient decent is done directly with respect to the soft margin and (2) regularized linear and quadratic programming (LP/QP-) ADABOOST, where the soft margin is attained by introducing slack variables.Extensive simulations demonstrate that the proposed regularized ADABOOST-type algorithms are useful and yield competitive results for noisy data.
Introduction
An ensemble is a collection of neural networks or other types of classifiers
(hypotheses) that are trained for the same task. Boosting and other ensemble
learning methods have been used recently with great success for
several applications, e. g. OCR [29, 16]. So far the reduction of the generalization
error by AdaBoost has not been completely understood.
For low noise cases, several lines of explanation have been proposed
as candidates for explaining the well functioning of Boosting methods [28,
7, 27]. Recent studies with noisy patterns [25, 14, 26] have shown that it
is clearly a myth that Boosting methods will not overfit. In this work, we
try to understand why AdaBoost exhibits virtually no overfitting for low
noise and strong overfitting for high noise data. We propose improvements
of AdaBoost to achieve noise robustness and to avoid overfitting.
In section 2 we analyze AdaBoost asymptotically. Due to their sim-
ilarity, we will refer in the following to AdaBoost [10] and unnormalized
Arcing [8] (with exponential function) as AdaBoost-type algorithms (ATA).
We especially have a focus on the error function of ATAs and find that
the function can be written in terms of the margin and every iteration
of AdaBoost tries to minimize this function stepwise by maximizing the
margin [22, 26, 12]. From the asymptotical analysis of this function, we
can introduce the hard margin concept. We show connections to Vapnik's
maximum margin classifiers, to Support Vector (SV) learning [4] and to
linear programming (LP). Bounds on the size of the margin are given.
Noisy patterns have shown that AdaBoost can overfit: this holds for
boosted decision trees [25], RBF nets [26] and also other kinds of classifiers.
In section 3 we explain why the property of AdaBoost to enforce a hard
margin must necessarily lead to overfitting in the presence of noise or in
the case of overlapping class distributions.
Because the hard margin plays a central role in causing overfitting, we
propose to relax the hard margin in section 4 and allow for misclassifications
by using the soft margin concept, that has already been successfully
applied to Support Vector Machines (cf. [9]). Our view is that the margin
concept is the key for the understanding of both, SVMs and ATAs.
So far, we only know how a margin distribution should look like, that a
learner has to achieve for optimal classification in the no-noise case: then
a large hard margin is clearly the best choice [30]. However, for noisy data
there is always the trade-off between believing in the data or mistrusting
it, as the very data point could be mislabeled or an outlier. This leads to
the introduction of regularization, which reflects the prior knowledge that
we have about the problem. We will introduce a regularization strategy
(analogous to weight decay) into AdaBoost and subsequently extend the
LP-AdaBoost algorithm of Grove & Schuurmans [14] by slack variables to
achieve soft margins. Furthermore, we propose QP-AdaBoost and show
its connections to SVMs.
Finally, in section 5 numerical experiments on several artificial and real-world
data sets show the validity and competitiveness of our regularization
approach. The paper is concluded by a brief discussion.
2 Analysis of AdaBoost's Learning Process
2.1 Algorithm
Tg be an ensemble of T hypotheses defined on an
input vector x 2 X and
We will consider only the binary classification case; most
results can be transfered easily to the classification with more than two
classes [27]. In the binary classification case the output is one of two class
labels, i.e. h t
The ensemble generates the label f(x) j f T (x) which is the weighted
majority of the votes, where
In order to train the ensemble, i.e. to find T appropriate hypotheses
and the weights c for the convex combination, several algorithms
have been proposed: e.g. Windowing [24], Bagging [5] and Boosting/Arcing
(AdaBoost [10], ArcX4 [7]). Bagging, where the weighting is simply
where the weighting scheme is more com-
plicated, are the most well-known ensemble learning algorithms. In the
sequel, we will focus on Boosting/Arcing, i.e. AdaBoost-type algorithms.
We omit a detailed description of the ATA and give only the pseudo-code
in figure 1, for details see e.g. [10, 7, 8].
In the binary classification case, we can define the margin for an input-output
Algorithm AdaBoost(OE)
Input: l examples
Initialize:
1. Train neural network with respect to the weighted sample set fZ; wg
and
obtain hypothesis
2. Calculate the training error ffl t of
l
abort if
where \Delta is a small constant
3. Set
4. Update weights w
where Z t is a normalization constant, such that
Output: Final hypothesis
where
jbj and jbj :=

Figure

1 The AdaBoost-type algorithm (ATA) [22]. For we retrieve the original
AdaBoost algorithm [10]. ATA is a specialization of unnormalized Arcing [6] (with exponential
l and l denotes the number of training patterns. The margin
at z is positive, if the right class of the pattern is predicted. As the
positivity of the margin value increases, the decision correctness, i.e. decision
stability, becomes larger. Moreover, if
1]. The margin ae of a decision line is the smallest margin
of a pattern in the training set, i.e.
We define d(z c) as the rate of incorrect classification (cf. edge in Breiman
[6]) for one pattern by
We will also use this definition with
b (instead of c) which is just an unnormalized version of c, i.e. usually we
have jbj 6= 1 (cf. (4) and (7) in figure 1).
2.2 Error Function of AdaBoost
An important question in the analysis of ATAs is what kind of error function
is optimized. From the algorithmic formulation (cf. figure 1), it is not
straight forward to understand what the aim of this algorithm is. So to
consider why one should use the weights of the hypotheses c t and of the
patterns w t (z i ) in the manner of equation (4) and (5), let us remember
the following facts:
1. The weights w t (z i ) in the t-th iteration are chosen such that the
previous hypothesis has exactly a weighted training error ffl of 1=2
[28].
2. The weight c t of a hypothesis is chosen such that it minimizes a
functional G introduced in Breiman [8]. Essentially, this functional
depends on the rate of incorrect classification of all patterns and is
defined by
l
exp
where OE is a constant. This functional can be minimized analytically
[8, 26] and one gets the explicit form of equation (4) as solution of
3. To train the t-th hypothesis (step 1 in figure 1) we can either use
bootstrap replicates of the training set (sampled according to w t ) or
minimize a weighted error function of the base learning algorithm.
We observed that the convergence of the ATA is faster if the weighted
error function is used.
Taking a closer look at the definition of G, one finds that the computation
of the sample distribution w t (cf. equation (5)) can be derived directly
from G. Let us assume G is the error function which is minimized by the
ATA. Essentially, G defines a loss function over all margin distributions,
which depends on the value of jbj. The larger the margins mg(z i ) (i.e. the
smaller the rate of incorrect classification), the smaller the value of G.
The gradient @G
gives an answer to the question, which pattern
should increase its margin to decrease G maximimally (gradient descent).
This information can be used to compute a sample distribution w t for
training the next hypothesis h t . If it is important to increase the margin
of a pattern z i , the weight w t (z i ) should be high - otherwise low (because
the distribution w t sums to one). Surprisingly, this is exactly what ATAs
are doing.
Lemma 1 The computation of the pattern distribution w t+1 in the t-th
iteration is equivalent to normalizing the gradient of G(b
respect to mg(z
l
The proof can found in the appendix A.
From Lemma 1, the analogy to a gradient descent method is (almost)
complete. In a gradient descent, at first we compute the gradient of the
error function with respect to the parameters which are to be optimized.
This corresponds to computing the gradient of G with respect to the mar-
gins. At second, the step size in this direction is determined (usually by
a line-search). This is comparable to the minimization of G mentioned in
point 2 in the list above.
Therefore, AdaBoost can be related to a gradient descent method,
which aims to minimize the functional G by constructing an ensemble of
classifiers [22, 26, 12]. This also explains point 1 in the list, because in a
gradient descent method, the new search direction is perpendicular to the
previous one.
But the analogy is not perfect. There is a "gap" between having the
pattern distribution and having a classifier. It is difficult to find a classifier
which minimizes G by only knowing the pattern distribution [26].
As we mentioned above, there are two ways of incorporating the sample
distribution. The first way is to create a bootstrap replicate, which is
sampled according to the pattern distribution. Usually there are a lot
of random effects, which hide the "true" information contained in the
distribution. Therefore, some information is lost - the gap is larger. The
more direct way is to use a weighted error function and employ weighted
minimization (Breiman [8]), therefore we will need more iterations with
bootstrap than with weighted minimization 1 . The fastest convergence can
be obtained, if one uses G directly for finding the hypothesis (cf. [12]).
These considerations explain point 3 in the list.
In Friedman et al. [12] it was mentioned, that sometimes the randomized version shows
a better performance, than the version with weighted minimization. In connection with the
discussion in section 3 this becomes clearer, because the randomized version will show an
overfitting effect (possibly much) later and overfitting maybe not observed, whereas it was
observed using the more efficient weighted minimization.
2.3 AdaBoost as an Annealing Process
From definition of G and d, equation (11) can also be written as
exp
Inspecting this equation more closely, we see that AdaBoost uses a softmax
function [3] with parameter jbj that we would like to interpret as
an annealing parameter [22]. If the temperature # := 1=jbj is high, the
system is in a state with high energy - all patterns have relevant high
weights. If the temperature goes down, the patterns with smallest margin
will get higher and higher weights. In the limit, we arrive at the maximum
function. Only the pattern(s) with the highest rate of incorrectness d
(i.e. smallest margin) will be considered and get a non-zero weight.
Lemma 2 If, in the learning process of an
weighted training errors ffl t are bounded by ffl t -
then jbj increases at least linearly with the number of iterations t.
Proof 3 With (4), the smallest value for b t is achieved, if ffl
Then we have b
\Delta). We also have
and hence also Therefore, the smallest value of b t is log q
which is always bigger than a constant fl, which only depends on OE and \Delta.
Thus, we have jb
If the annealing speed is low, the achieved solution should have larger
margins. The reason is the same as for an usual annealing process [15]:
in the error surface, a better local minimum could be obtained locally, if
the annealing is slow enough. From equation (4), we observe that if the
training error ffl t takes a small value, b t becomes large. So, strong learners
can reduce their training errors strongly and will make jbj large after only
a few ATA iterations. The asymptotic point is reached faster. To reduce
the annealing speed, OE or the complexity of the base hypotheses has to be
decreased (with the constraint ffl t ! OE \Gamma \Delta).

Figure

shows some error functions for classification. Among them,
the error function for different values of jbj and OE is shown. In
figure 2 (left), the AdaBoost
2 ), the Squared
and the Kullback-Leibler Error ln mg(z)= ln 2 are plotted. Squared and
Kullback-Leibler are very similar to the error function of AdaBoost
for As jbj increases (in our experiments often up to 10 2 after 200
iterations), the ATA error function approximates a 0=1 loss: all patterns
with margin smaller than 0 (or more general loss others
have loss 0. If it is possible to reduce the error of all patterns to 0 (as
in the AdaBoost case), then this is asymptotically (jbj ! 1) equivalent
to the 0=1-loss around 0 AdaBoost with
The loss function for OE 6= 1
shown in figure 2 (right), demonstrate the
different offsets of the step exhibited by the 0=1 loss.
10.51.52.5loss

Figure

Loss functions for estimating a function f(x) for classification. The abscissa
shows the margin yf(x) of a pattern and the y-coordinate shows the monotone loss for that
pattern: 0=1-Loss (solid), Squared Error (dashed), Kullback-Leibler Error (dash-dotted) and
100g. On the left panel is and on the right plot OE is one
out of f1=3; 2=3g. OE controls the position of the step of the 0=1-Loss which is
asymptotically approximated by the AdaBoost loss function.
2.4 Asymptotical Analysis
2.4.1 How large is the Margin?
The main point in the explanation of ATA's good generalization performance
is the size of the (hard) margin that can be achieved [28, 8]. In the
low noise case, the hypothesis with the largest margin will have a good
generalization performance [30, 28]. Thus, it is interesting to see how large
the margin is and on what it is depending.
Generalizing theorem 5 of Freund et al. [10] to the case OE 6= 1
2 we get
Theorem 4 Assume, ffl are the weighted classification errors of
were generated while running an
. Then the following inequality holds for all ' 2 [\Gamma1; 1]:l
l
I (y i
Y
where f is the final hypothesis and
The proof can be found in appendix B.
Corollary 5 An distributions
with a margin ae, which is bounded by
ae -
Proof 6 The maximum of ffl 1\Gamma'
with respect to ffl t is reached for2
increasing monotonically in ffl t .
Therefore, we can replace ffl t by ffl in equation (13) for ' - ae:
ii
If the basis on the right hand side is smaller than 1, then asymptotically
we have P (x;y)-Z [yf(x) - Asymptotically, there is no example
that has a smaller margin than '. For the biggest possible margin ' max we
have
We can solve this equation for ' max and we get
We get the assertion, because ae is always bigger or equal ' max .
From equation (14), we can see the interaction between OE and ffl: if the
difference of ffl and OE is small, the right hand side of (14) is small. The
smaller OE the more important is this difference. From theorem 7.2 of [8]
we also have the weaker bound ae - 1 \Gamma 2OE and so, if OE is small then ae must
be large, i.e. choosing a small OE results in a larger margin on the training
patterns. An increase of the complexity of the basis algorithm leads to an
increased ae, because the error ffl t will decrease.
2.4.2 Support Patterns
A decrease in the functional G(c; jbj) := G(b) (with predominantly
achieved by improvements of the margin mg(z i ; c). If the margin
c) is negative, then the error G(c; jbj) takes clearly a big value,
which is additionally amplified by jbj. So, AdaBoost tries to decrease the
negative margin efficiently to improve the error G(c; jbj).
let us consider the asymptotic case, where the number of iterations
and therefore also jbj take large values (cf. Lemma 2). In this
case, the values of all mg(z are almost the same, small
differences are amplified strongly in G(c; jbj).
For example, when the margin mg(z another margin
the difference is amplified to the difference
between exp
i.e. to a factor of e 5 - 150.
Obviously the function G(c; jbj) is asymptotically very sensitive to
small differences between margins of the training patterns. From equation
(12), when the annealing parameter jbj takes a big value, AdaBoost
learning becomes a hard competition case: only the patterns with smallest
margin will get high weights, other patterns are effectively neglected
in the learning process. Therefore, the margins mg(z i ; c) are expected to
asymptotically converge to a fixed value ae and a subset of the training
patterns will asymptotically have the same smallest margin ae. We call
these patterns Support Patterns (cf. figure 3).
In order to confirm that the above theoretical analysis is correct, asymptotic
numerical simulations on toy data (several Gauss blobs in two di-
mensions; cf. figure are made. The training data is generated from
cumulative
probability
cumulative
probability

Figure

3 Margin distributions for AdaBoost for different noise levels oe
9% (dashed), 16% (solid) with RBF nets (13 centers) as base hypotheses (left) and with 7
centers in the base hypotheses for data with oe
AdaBoost iterations. These graphs experimentally confirm the expected trends from
equation (14).
several (nonlinearly transformed) Gaussian and uniform blobs 2 , which are
additionally disturbed by uniformly distributed noise U(0:0; oe 2 ). In our
simulations, we used 300 patterns and oe 2 is one out of 0%, 9%, and 16%.
In all simulations, radial basis function (RBF) networks with adaptive
centers are used as learners (cf. Appendix C for a detailed description).

Figure

3 shows the margin distributions after 10 4 AdaBoost iterations at
different noise levels oe 2 (left) and for different strengths of the base hypotheses
(right). From these figures, it becomes apparent that the margin
distribution asymptotically makes a step at fixed size of the margin for
some training patterns. From figure 3, one can see the influence of noise
in the data and the strength of the base hypotheses on the margin ae. If the
noise level is high or the complexity is low, one gets higher training errors
ffl t and therefore a smaller value of ae. These numerical results support our
theoretical asymptotic analysis.
Interestingly, the margin distributions of ATAs resembles the one of
Support Vector Machines (SVMs) for the separable case [4, 9, 30] (cf. figure
6). In an example (cf. figure almost all patterns, that are Support
Vectors (SVs), also lie within the step part of the margin distribution for
AdaBoost. So, AdaBoost achieves a hard margin asymptotically, such as
the SVMs for the separable case.
In an earlier study [26] we observed, that usually there is high overlap
among the Support Vectors and Support Patterns. Intuitively this is
clear, because the most difficult patterns are in the margin area. They
are emphasized strongly and become Support Patterns or Support Vectors
asymptotically. The degree of overlap depends on the kernel (SVM)
and on the base hypothesis (ATA) which are used. For the SVM with
RBF kernel the highest overlap was achieved, when the average widths of
the RBF networks was used as kernel width for the Support Vector Ma-
detailed description of the generation of the toy data used in the asymptotical simulations
can be found in the Internet http://www.first.gmd.de/~raetsch/data/banana.txt.
Figure

Training patterns with decision lines for AdaBoost (left) with RBF nets (13
centers) and SVM (right) for a low noise case with similar generalization errors. The positive
and negative training patterns are shown as '+' and '\Lambda' respectively, the Support Patterns
and Support Vectors are marked with 'o'.
chine [26]. We have observed the similarity of Support Patterns (SP) of
AdaBoost and SV of the SVM also in several other applications.
In the sequel, we can often assume the asymptotical case, where a hard
margin is achieved. The more hypotheses we combine, the better is this
approximation. And indeed, if for example (as often after 200
AdaBoost iterations on benchmark data used in section 5), already then
the approximation to a hard margin is good (cf. equation (12)). This is
illustrated by figure 5, which shows typical distributions after
To recapitulate our findings of this section:
1. AdaBoost-type algorithms aim to minimize a functional, which depends
on the margin distribution. The minimization is done through
an approximate gradient descent with respect to the margin (cf. [26,
12]).
2. Annealing is a part of the algorithm. It depends on an annealing
parameter jbj, which controls how good the 0=1-loss (around
is approximated. The size of the margin is decided by a certain
annealing process. The speed of annealing depends on the parameter
OE and is an implicit function of the strength of the learner in the
training process.
3. Some training patterns, which are in the area of the decision bound-
ary, have asymptotically the same margin. We call these patterns
Support Patterns. They have a large overlap to the SVs found by a
SVM.
4. Asymptotically, a hard margin is achieved, which is comparable to
the one of the original SV approach [4].
5. Larger hard margins can be achieved, if ffl t and/or OE are small (cf. Corollary
5). For the low noise case, a choice of ' 6= 1
can lead to a better
generalization performance, as shown for OCR in [22].
Hard Margin and Overfitting 11
cumulative
probability

Figure

5 Typical margin distribution
graphs of (original) AdaBoost after 20
(dotted), 70 (dash-dotted), 200 (dashed)
iterations. Here, the toy
example (300 patterns,
networks with centers are used. After
already 200 iterations the asymptotical
convergence is almost reached.
10.10.30.50.70.9cumulative
probability

Figure

6 Typical margin distribution graphs
(normalized) of a SVM with hard margin
(solid) and soft margin with
and Here, the same
toy example and a RBF kernel (width=0:3) is
used. The generalization error of the SVM with
hard margin is more than two times larger as
with
3 Hard Margin and Overfitting
In this section, we give reasons why the ATA is not noise robust and
exhibits suboptimal generalization ability in the presence of noise. We give
several references and examples why the hard margin approach will fail in
general if noise is present. According to our understanding, noisy data has
at least one of the following properties: (a) overlapping class probability
distributions, (b) outliers and (c) mislabeled patterns. All three kinds of
noise appear very often in data analysis. Therefore the development of a
noise robust version of AdaBoost is very important.
The first theoretical analysis of AdaBoost in connection with margin
distributions was done by Schapire et al. [28]. Their main result is a
bound on the generalization error P z-D [mg(z) - 0] depending on the VC-dimension
d of the base hypotheses class and on the margin distribution
on the training set. With probability at least
l
is satisfied, where ' ? 0 and l denotes the number of patterns. It was stated
that the reason for the success of AdaBoost, compared to other ensemble
learning methods (e.g. Bagging), is the maximization of the margin. They
experimentally observed that AdaBoost maximizes the margin of patterns
which are most difficult, i.e. have the smallest margin. However, by increasing
the minimum margin of a few patterns, AdaBoost also reduces
the margin of the rest of the other patterns.
Hard Margin and Overfitting 12
number of iterations
generalization
error

Figure

7 Typical overfitting behavior in the generalization error (smoothed) as a function
of the number of iterations (left) and a typical decision line (right) generated by AdaBoost
using RBF networks (30 centers) in the case of noisy data (300 patterns,
16%). The positive and negative training patterns are shown as '+' and '\Lambda' respectively,
the Support Patterns are marked with 'o'. An approximation to the Bayes decision line is
plotted dashed.
In Breiman [8], the connection between the smallest margin and the
generalization error was analyzed experimentally and could not be confirmed
on noisy data.
In Grove et al. [14] the Linear Programming (LP) approach of Freund
et al. [11] and Breiman [8] was extended and used to maximize the smallest
margin of an existing ensemble of classifiers. Several experiments with LP-
AdaBoost on UCI benchmarks (often noisy data) were made and it was
unexpectedly observed, that LP-AdaBoost performs in almost all cases
worse than the original AdaBoost algorithm, even if the smallest margins
are larger.
Our experiments have shown that as the margin increases, the generalization
performance becomes better on datasets with almost no noise
(e.g. OCR), however, on noisy data, we also observed that AdaBoost
overfits (for a moderate number of combined hypotheses).
As an example for overlapping classes, figure 7 (left) shows a typical
overfitting behavior in the generalization error for AdaBoost on the same
data as in section 2. Here, already after only 80 AdaBoost iterations the
best generalization performance is achieved. From equation (14) it is clear
that AdaBoost will asymptotically achieve a positive margin (if OE ! 1) and
all training patterns are classified according to their possibly wrong labels
(cf. figure 7 (right)), because the complexity of the combined hypotheses
increases more and more. The achieved decision line is far away from the
Bayes optimal line (cf. dashed line in figure 7 (right)).
To discuss the bad performance of a hard margin classifier in presence
of outliers and mislabeled patterns, we analyze the toy example in figure
8. Let us first consider the case without noise (left). Here, we can estimate
the optimal separating hyper-plane correctly. In figure 8 (middle) we
have an outlier, which corrupts the estimation. AdaBoost will certainly
concentrate its weights to this outlier and spoil the good estimate that we
would get without outlier. Next, let us consider more complex decision
lines. Here the overfitting problem gets even more distinct, if we can gen-
3Figure

8 The problem of finding a maximum margin "hyper-plane" on reliable data (left),
data with outlier (middle) and with a mislabeled pattern (right). The solid line shows the
resulting decision line, whereas the dashed line marks the margin area. In the middle and
on the left the original decision line is plotted with dots. The hard margin implies noise
sensitivity, because only one pattern can spoil the whole estimation of the decision line.
erate more and more complexity through combining a lot of hypotheses.
Then all training patterns even mislabeled ones or outliers can be classified
correctly. In figure 7 (right) and figure 8 (right) we see that the decision
surface is much too shaky and gives a bad generalization.
From these cartoons, it becomes apparent that AdaBoost is noise sensitive
and maximizing the smallest margin in the case of noisy data can
(and will) lead to bad results. Therefore, we need to allow for a possibility
of mistrusting the data.
From the bound (15) it is indeed not obvious, that we should minimize
the smallest margin: the first term on the right hand side of equation (15)
takes the whole margin distribution into account. If we would allow a
non-zero training error in the settings of figure 8, then the first term of the
right hand side of (15) becomes non-zero (' ? 0). But then ' can be larger,
such that the second term is much smaller. In Mason et al. [18] a similar
bound was used to optimize the margin distribution (a piecewise linear
directly. This approach was more successful on noisy data
than a maximization of the smallest margin.
In the following we introduce the possibility to mistrust parts of the
data, which leads to the soft margin concept.
4 Improvements using a Soft Margin
The original SV algorithm [4] had similar problems as the ATA with respect
to hard margins. In the SV approach, training errors on data with
overlapping classes were not allowed and the generalization performance
was poor on noisy data. The introduction of soft margins then gave a new
algorithm, which achieved much better results compared to the original
algorithm [9] (cf. figure 6).
In the sequel, we will show how to use the soft margin idea for ATAs.
In section 4.1 we change the error function (10) by introducing a new
which controls the importance of a pattern compared to its achieved
margin. In section 4.2 we show how the soft margin idea can be built
into the LP-AdaBoost algorithm and in section 4.3 we show an extension
to quadratic programming - QP-AdaBoost - with its connections to the
Support Vector approach.
4.1 Margin vs. Influence of a Pattern
First, we propose an improvement of the original AdaBoost by using an
regularization term in (10) in analogy to weight decay. For this we define
the influence of a pattern to the combined hypotheses h r by
which is the (weighted) average weight of a pattern computed during the
ATA's learning process (cf. pseudo-code in figure 1). A pattern which is
very often misclassified (i.e. difficult to classify), will have a high average
weight (high influence). The definition of the influence clearly depends on
the base hypotheses space H.
From Corollary 5 and Theorem 2 of [8], all training patterns will get
a margin mg(z i ) larger or equal than 1 \Gamma 2OE after many iterations (cf. figure
2 and discussion in section 2). Asymptotically, we get the following
inequalities
(or even better bounded by equation (14)). We can see the
relation between ae and G(b) for a sufficient large value of jbj in equation
as G(b) is minimized, ae is maximized. After many iterations, these
inequalities are satisfied and as long as OE - 1
2 , the hard margin ae - 0
is achieved [28], what will lead to overfitting in the case of noise. In the
following we will consider only the case
generalizations are straight
forward.
We define a soft margin of a pattern f
trade-off between the
margin and the influence of the pattern to the final hypothesis as follows
f
where C - 0 is a fixed constant and p a fixed exponent. With C and p one
can modify this trade-off. We can reformulate AdaBoost's optimization
process in terms of soft margins. With (16) and (17) we get
f
which is equivalent to
where we use i t (z i simplicity. Other functional forms of i
can also be used (depending on our prior).
In these inequalities, i t (z i ) are positive and if a training pattern has
high weights, i t (z i ) is increasing. In this way, we do not force outliers to
be classified according to their possibly wrong labels (if this would imply
a high influence), but we allow for some errors. So we get the desired
trade-off between margin and influence. If we choose
(19), the original AdaBoost algorithm is retrieved. If C is chosen high,
the data is not taken seriously and for retrieve the
Bagging algorithm [5].
From inequality (18), we can derive the new error function (cf. equation
(10)), which aims to maximize the soft margin
G Reg (b t
l
exp
ae
\Gamma2
f
oe
l
exp
ae
\Gamma2
\Theta mg(z
oe
The weight w t+1 (z i ) of a pattern is computed as the derivative of equation
(20) subject to f
and is given by
For get an update rule for the weight of a training pattern in the
t-th iteration [26]
It is more difficult to compute the weight b t of the t-th hypothesis. Es-
pecially, it is hard to derive the weight analytically. However, we can get
b t by a line search procedure [23] over (20), which has an unique solution
because @
G Reg (b t ) ? 0 is satisfied for b t ? 0. The line search procedure
can be implemented efficiently.
We can interpret this approach as regularization analogous to weight
decay, whereby we want to incorporate the prior knowledge that some
patterns are probably not reliable. Therefore, in the noisy case we prefer
hypotheses, which do not rely on only a few patterns with high weights 3 .
Instead, we are looking for hypotheses with smaller values of i(z i ). So by
this regularization, AdaBoost is not changed for easy classifiable patterns,
but only for the most difficult patterns.
The variables i(z i ) in equation (19) can also be interpreted as slack-
variables (cf. SV approach and next section), which are non-linearly involved
in the error function. Bigger values of i(z i ) for some patterns allow
a larger (soft-) margin ae.
Summarizing, this modification of AdaBoost is constructed to produce
a soft margin and therefore to avoid overfitting.
For a comparison of the soft margin distributions of a single RBF
classifier and AdaBoost Reg see figure 9.
3 Interestingly, also the (soft) SVM generates much more SV in the high noise case than
in the low noise case. Therefore, the SVM shows a trend to need more patterns to find a
hypothesis if the patterns are noisy [30].
cumulative
probability
cumulative
probability

Figure

9 Margin distribution graphs of the RBF base hypothesis (scaled) trained with
Mean Squared Error (left) and AdaBoostReg (right) with different values of C for the toy data
set after 10 3 iterations. Note that for some values for C the graphs of AdaBoostReg are quite
similar to the graphs of the singe RBF net.
4.2 Linear Programming with Slack Variables
Grove et al. [14] showed how to use linear programming to maximize the
smallest margin for a given ensemble and proposed LP-AdaBoost (cf. algorithm
(23)). In their approach, they first compute a gain (or margin)
for the given hypotheses set, which is defined by
The matrix G gives information, which hypothesis contributes a positive
(or negative) part to the margin of a pattern and is used to formulate the
following maxi-min problem: find a weight vector c 2 R T for hypotheses
t=1 , which maximizes the smallest margin ae := min i=1;::: ;l mg(z i ).
That can be solved by linear programming [17]:
Maximize ae subject to
This linear program achieves a larger hard margin than the original
AdaBoost algorithm. From the reasoning in section 3, LP-AdaBoost can
not generalize well on noisy data, since it even stronger overemphasizes difficult
patterns, e.g. outliers. Now, we define again a soft-margin for a pattern
f
to introduce regularization for LP-AdaBoost.
Technically, this approach is equivalent to the introduction of slack
variables to LP-AdaBoost and we arrive at the algorithm LP Reg -AdaBoost
[26], which solves the following linear program:
subject to
This modification allows that some patterns have smaller margins than
ae (especially lower than 0). There is a trade-off: (a) make all margins
bigger than ae and (b) maximize ae \Gamma C
This trade-off is controlled
by the constant C.
4.3 Quadratic Programming and the connection
to Support Vector Machines
In the following section, we extend the LP Reg -AdaBoost algorithm to
quadratic programming by using similar techniques as in Support Vector
Machines [4, 9, 17]. This gives interesting insights to the connection
between SVMs and AdaBoost.
We start with transforming the LP Reg -AdaBoost algorithm, which
maximizes ae, while jcj is kept fixed, to an linear program, in which ae is
fixed (to e.g. 1) and jbj is minimized. Unfortunately, there is no equivalent
linear program. But we can use Taylor expansions 4 to get the following
linear program (compare with linear programming approaches related to
learning e.g. [31, 13, 1]):
Minimize
subject to
Essentially, this is the same algorithm as (24), but the slack variables are
acting differently, because only the Taylor expansion of 1=jbj was used.
Therefore, we will achieve different soft margins as in the previous section
(cf. figure 10).
Instead of using the l 1 norm in the optimization objective of (25), we
can also use the l p norm. Clearly, each p will imply its own soft margin
characteristics. For will lead to an algorithm similar to the SVM.
4 From (24), it is straight forward to get the following problem, which is for any fixed S ? 0
equivalent to (24):
i subject to S
In this problem we can set ae + to 1 and try to optimize S. To retrieve a linear program, we
use the Taylor expansion around 1: 1
For
The optimization objective of a SVM is to find a function h w which
minimizes a functional of the form [30]
l
subject to the constraints
Here, the variables - i are the slack-variables, which make a soft margin
possible. The norm of the parameter vector w is a measure of the complexity
and the size of the margin of hypothesis h w [30]. With functional
(26), we get a trade-off (controlled by C) between the complexity of the
hypothesis and the "grade how much the hypothesis may differ from the
training patterns" (
For ensemble learning, we do not (yet) have such a measure of com-
plexity. Empirically, we observed the following: the more different the
weights for the hypotheses are, the higher the complexity of the ensem-
ble. With this in mind, we can use the l p norm (p ? 1) of the hypotheses
weight vector kbk p as a complexity measure. For example, assume
then kbk p this is a small value, if the elements are approximately equal
(analogous to bagging) and kbk p has high values, when there are some
strongly emphasized hypotheses (far away from bagging). This is intuitively
clear, because Bagging generates usually less complex classifiers
(with lower kbk p ) than, for example, LP-AdaBoost (which can generate
very sparse representations for which kbk p is large).
Note that this arguments holds only if the hypotheses are weak enough,
otherwise the kbk p will not carry the desired complexity information.
Hence, we can apply the optimization principles of SVMs to AdaBoost
and get the following quadratic optimization problem:
Minimize kbk 2
with the constraints given in equation (25). This algorithm, we call it
QP Reg -AdaBoost, is motivated by the connection to LP Reg -AdaBoost
(cf. algorithm (25)) and by the analogy to the Support Vector algorithm.
It is expected, that QP Reg -AdaBoost achieves large improvements over
the solution of the original AdaBoost algorithm - especially in the case
of noise. In comparison with LP Reg -AdaBoost we expect a similar per-
formance. Each "type of soft margin", which is implied by the norm of
the weight vector, can have merits, which may be needed by some specific
dataset.
Summarizing, we introduced a soft margin to AdaBoost by (a) regularizing
the objective function (10), (b) LP Reg -AdaBoost, which uses slack
variables and (c) QP Reg -AdaBoost, which has an interesting relation to
SVMs. For an overall comparison of the margin distributions of original
AdaBoost, SVM, AdaBoost Reg and LP/QP-AdaBoost see figures 5, 6, 9
and 10.
5 Experiments
In order to evaluate the performance of our new algorithms, we make an
extensive comparison among the single RBF classifier, the original AdaBoost
algorithm, AdaBoost Reg , L/QP Reg -AdaBoost and a Support Vector
Machine (with RBF kernel).
cumulative
probability
cumulative
probability

Figure

Margin distribution graphs of LPReg-AdaBoost (left) and QPReg-AdaBoost
(right) with different values of C for the toy data set after 10 3 iterations. LPReg-AdaBoost
sometimes generates margins on the training set, which are either 1 or -1 (step in the distri-
bution).
5.1 Experimental Setup
For this, we use 13 artificial and real world datasets from the UCI, DELVE
and STATLOG benchmark repositories: banana (toy data set used in the
previous sections), breast cancer 5 , diabetes, german, heart, image segment,
ringnorm, flare sonar, splice, new-thyroid, titanic, twonorm, waveform. Some
of the problems are originally not binary classification problems, hence
a random partition into two classes was used 6 . At first we generate 100
partitions into training and test set (mostly - 60% : 40%). On each
partition we train a classifier and get its test set error.
In all experiments, we combined 200 hypotheses. Clearly, this number
of hypotheses may be not optimal, however AdaBoost with optimal early
stopping is often worse than any of the soft margin algorithms.
As base hypotheses we used RBF nets with adaptive centers as described
in appendix C. On each data set we used cross validation to find
the best single classifier model, which is then used in the ensemble learning
algorithms.
The parameter C of the regularized versions of AdaBoost and the parameters
(C; oe) of the SVM are optimized by the first five training datasets.
On each training set 5-fold-cross validation is used to find the best model
for this dataset 7 . Finally, the model parameters are computed as the median
of the five estimations. This way of estimating the parameters is
surely not possible in practice, but will make this comparison more robust
and the results more reliable.
5 The breast cancer domain was obtained from the University Medical Center, Inst. of
Oncology, Ljubljana, Yugoslavia. Thanks go to M. Zwitter and M. Soklic for providing the
data.
6 A random partition generates a mapping m of n to two classes. For this a random \Sigma1
vector m of length n is generated. The positive classes (and the negative respectively) are
then concatenated.
7 The parameters selected by the cross validation are only near-optimal. Only 10-20 values
for each parameter are tested in two stages: first a global search (i.e. over a wide range of
the parameter space) was done to find a good guess of the parameter, which becomes more
precise in the second stage.
Table

Comparison among the six methods: Single RBF classifier, AdaBoost(AB),
AdaBoostReg (ABR;p=2), L/QPReg-AdaBoost (L/QPR-AB) and a Support Vector Machine
Estimation of generalization error in % on 13 datasets (best method in bold face,
second emphasized). AdaBoostReg gives the best overall performance.
RBF AB ABR LPR-AB QPR-AB SVM
Banana 10.8\Sigma0.6 12.3\Sigma0.7 10.9\Sigma0.4 10.7\Sigma0.4 10.9\Sigma0.5 11.5\Sigma0.6
B.Cancer 27.6\Sigma4.7 30.4\Sigma4.7 26.5\Sigma5.5 26.8\Sigma6.1 25.9\Sigma4.6 26.0\Sigma4.7
Diabetes 24.1\Sigma1.9 26.5\Sigma2.3 23.9\Sigma1.6 24.1\Sigma1.9 25.4\Sigma2.2 23.5\Sigma1.7
German 24.7\Sigma2.4 27.5\Sigma2.5 24.3\Sigma2.1 24.8\Sigma2.2 25.2\Sigma2.1 23.6\Sigma2.1
Heart 17.1\Sigma3.3 20.3\Sigma3.4 16.6\Sigma3.7 14.5\Sigma3.5 17.2\Sigma3.4 16.0\Sigma3.3
Image 3.3\Sigma0.6 2.7\Sigma0.7 2.7\Sigma0.6 2.8\Sigma0.6 2.7\Sigma0.6 3.0\Sigma0.6
Ringnorm 1.7\Sigma0.2 1.9\Sigma0.3 1.6\Sigma0.1 2.2\Sigma0.5 1.9\Sigma0.2 1.7\Sigma0.1
F.Sonar 34.4\Sigma2.0 35.7\Sigma1.8 34.2\Sigma2.2 34.8\Sigma2.1 36.2\Sigma1.8 32.4\Sigma1.8
Splice 9.9\Sigma1.0 10.3\Sigma0.6 9.5\Sigma0.7 9.9\Sigma1.4 10.3\Sigma0.6 10.8\Sigma0.6
Thyroid 4.5\Sigma2.1 4.4\Sigma2.2 4.4\Sigma2.1 4.6\Sigma2.2 4.4\Sigma2.2 4.8\Sigma2.2
Titanic 23.3\Sigma1.3 22.6\Sigma1.2 22.6\Sigma1.2 24.0\Sigma4.4 22.7\Sigma1.1 22.4\Sigma1.0
Twonorm 2.9\Sigma0.3 3.0\Sigma0.3 2.7\Sigma0.2 3.2\Sigma0.4 3.0\Sigma0.3 3.0\Sigma0.2
Waveform 10.6\Sigma1.0 10.8\Sigma0.6 9.8\Sigma0.8 10.5\Sigma1.0 10.1\Sigma0.5 9.9\Sigma0.4
Mean % 6.6\Sigma5.8 11.9\Sigma7.9 1.7\Sigma1.9 8.9\Sigma10.8 5.8\Sigma5.5 4.6\Sigma5.4
Note, to perform the simulations of this setup we had to train more
than adaptive RBF nets and to solve more than 10 5 mathematical
programming problems - a task that would have taken altogether 2 years of
computing time on a single Ultra-SPARC machine, if we hadn't distributed
it over computers.
5.2 Experimental Results
In table 1 the average generalization performance (with standard devia-
tion) over the 100 partitions of the data sets are shown. The second last
line in table 1 shows the line 'Mean %', which is computed as follows: For
each dataset the average error rates of all classifier types are divided by
the minimum error rate and 1 is subtracted. These resulting numbers are
averaged over the 13 datasets and the variance is given, too. The last
line shows the probabilities that a particular method wins, i.e. gives the
smallest generalization error, on the basis of our experiments (mean and
variance over all 13 datasets).
Our experiments on noisy data (cf. table 1) show that:
\Pi The results of AdaBoost are in almost all all cases worse than the
single classifier. This shows clearly the overfitting of AdaBoost. It is
not able to deal with noise in the data.
\Pi The averaged results for AdaBoost Reg are slightly better (Mean%
and Win%) than the results of the SVM, which is known to be an
excellent classifier. The single RBF classifier wins less often than the
SVM (for a comparison in the regression case see [20]).
-AdaBoost improves the results of AdaBoost. This is due
to the established soft margin. But the results are not as good as
the results of AdaBoost Reg and the SVM. One reason is that the
hypotheses generated by AdaBoost (aimed to construct a hard mar-
may provide not the appropriate basis to generate a good soft
margin with the mathematical programming approaches.
Conclusion 21
\Pi We can observe that quadratic programming gives slightly better results
than linear programming. This may be due to the fact that
the hypotheses coefficients generated by LP Reg -AdaBoost are more
sparse (smaller ensemble); bigger ensembles may have a better generalization
ability (e.g. due to the reduction of variance [7]). Further-
more, with QP-AdaBoost we prefer ensembles, which have approximately
equal weighted hypotheses. As stated in section 4.3, this
implies a lower complexity of the combined hypothesis, which can
lead to a better generalization performance.
\Pi The results of AdaBoost Reg are in all cases (much) better than
those of AdaBoost and better than that of the single RBF classi-
fier. AdaBoost Reg wins most often and shows the best average per-
formance. This demonstrates the noise robustness of the proposed
algorithm.
The slightly inferior performance of SVM compared to AdaBoost Reg may
be explained with (a) the fixed oe of the RBF-kernel for SVM (loosing
multi-scale information), (b) the coarse model selection, and (c) a bad
error function of the SV algorithm (noise model).
Summarizing, the original AdaBoost algorithm is only useful for low
noise cases, where the classes are easily separable (as shown for OCR
[29, 16]). L/QP Reg -AdaBoost can improve the ensemble structure through
introducing a soft margin: the same hypotheses (just with another weight-
ing) can result in an ensemble, which shows a much better generalization
performance.
The hypotheses, which are used by L/QP Reg -AdaBoost may be sub-
optimal, because they are not part of the optimization process, which
aims for a soft margin. AdaBoost Reg does not have this problem: the hypotheses
are generated such that they are appropriate to form the desired
soft-margin. AdaBoost Reg extends the applicability of Boosting/Arcing
methods to non-separable cases and should be applied, if the data is noisy.
6 Conclusion
We have shown that AdaBoost performs an approximate gradient decent
in an error function, that optimizes the margin (cf. equation 10, see also
[8, 22, 12]). Asymptotically, all emphasis is concentrated on the difficult
patterns with small margins, easy patterns effectively do not contribute
to the error measure and are neglected in the training process (very much
similar to Support Vectors). It is shown theoretically and experimentally
that the cumulative margin distribution of the training patterns in the
margin area converges asymptotically to a step and therefore AdaBoost
asymptotically achieves a hard margin for classification. The asymptotic
margin distribution of AdaBoost is very similar to the margin distribution
of a SVM (for the separable case), accordingly the patterns lying in the
step part (Support Patterns) show a large overlap to the Support Vectors
found by a SVM. However, the representation found by AdaBoost is often
less sparse than for SVMs.
We discussed in detail that AdaBoost-type algorithms, and hard margin
classifiers in general, are noise sensitive and able to overfit. We introduced
three regularization-based AdaBoost algorithms to alleviate the
overfitting problem of AdaBoost-type algorithms for high noise data: (1)
direct incorporation of the regularization term into the error function
Proof of Lemma 1 22
(AdaBoost Reg ), use of (2) linear and (3) quadratic programming with slack
variables. The essence of our proposal is to achieve a soft margin (through
regularization term and slack variables) in contrast to the hard margin
classification used before. The soft-margin approach allows to control how
much we trust the data, so we are permitted to ignore noisy patterns
(e.g. outliers) which would otherwise have spoiled our classification. This
generalization is very much in the spirit of Support Vector Machines that
also trade-off the maximization of the margin and the minimization of the
classification errors by introducing slack variables.
In our experiments on noisy data the proposed regularized versions of
AdaBoost: AdaBoost Reg and L/QP Reg -AdaBoost show a more robust behavior
than the original AdaBoost algorithm. Furthermore, AdaBoost Reg
exhibits a better overall generalization performance than all other algorithms
including the Support Vector Machines. We conjecture that this
unexpected result is mostly due to the fact that SVM can only use one
oe and therefore loose multi-scaling information. AdaBoost does not have
this limitation, since we use RBF nets with adaptive kernel widths as base
hypotheses.
Our future work will concentrate on a continuing improvement of Ada-
Boost-type algorithms for noisy real world applications. Also, a further
analysis of the relation between AdaBoost (QP Reg -AdaBoost) and Support
Vector Machines from the margin's point of view seems promising, with
particular focus on the question of what good margin distributions should
look like. Moreover, it is interesting to see how the techniques established
in this work can be applied to AdaBoost in a regression scenario (cf. [2]).

Acknowledgements

We thank for valuable discussions with B. Sch-olkopf,
A. Smola, T. Frie-, D. Schuurmans and B. Williamson. Partial funding
from EC STORM project number 25387 is gratefully acknowledged.
A Proof of Lemma 1
Proof 7 We define - t (z i ) :=
and from definition
of G and d we get
exp
e
where e
By definition, we have - t (z
1=l. Thus, we get
e
e
Z
e
e
Z (cf. step 4 in figure 1).
Proof of Theorem 4 23
B Proof of Theorem 4
The proof follows the one of Theorem 5 in [28]. Theorem 4 is a generalization
for OE 6= 1Proof 8 If yf(x) - ', then we have
y
and also
exp
Thus,
l
exp
exp
l
l
exp
y iT
where
l
exp
l
exp
exp
exp
exp
e bT =2
exp
because
With
recursively
Y
RBF nets with adaptive centers 24
Plugging in the definition for b t we get
Y
Y
OE
/s
OE
s
OE
Y
OE
Y
Y
C RBF nets with adaptive centers
The RBF nets used in the experiments are an extension of the method
of Moody and Darken [19], since centers and variances are also adapted
(see also [3, 21]). The output of the network is computed as a linear
superposition of K basis functions
denotes the weights of the output layer. The
Gaussian basis functions g k are defined as
k denote means and variances, respectively. In a first step,
the means - k are initialized with K-means clustering and the variances oe k
are determined as the distance between - k and the closest - i (i
Kg). Then in the following steps we perform a gradient descent in
the regularized error function (weight decay)
l
2l
Taking the derivative of equation (29) with respect to RBF means - k and
variances oe k we obtain
l
RBF nets with adaptive centers 25
Algorithm RBF-Net
Input:
Sequence of labeled training patterns
Number of RBF centers K
Regularization constant -
Number of iterations T
Initialize:
Run K-means clustering to find initial values for - k and determine oe
as the distance between - k and the closest - i (i 6= k).
1. Compute optimal output weights
l I
2a. Compute gradients @
E as in (31) and (30) with optimal w
and form a gradient vector v
2b. Estimate the conjugate direction v with Fletcher-Reeves-Polak-Ribiere
CG-Method [23]
3a. Perform a line search to find the minimizing step size ffi in direction v; in
each evaluation of E recompute the optimal output weights w as in line3b. Update - k and oe k with v and ffi
Output: Optimized RBF net

Figure

Pseudo-code description of the RBF net algorithm, which is used as base learning
algorithm in the simulations with AdaBoost
and
l
These two derivatives are employed in the minimization of equation (29)
by a conjugate gradient descent with line search, where we always compute
the optimal output weights in every evaluation of the error function during
the line search. The optimal output weights
notation can be computed in closed form by
l
I
and denotes the output vector, and I an identity matrix.
For this corresponds to the calculation of a pseudo-inverse of G.
So, we simultaneously adjust the output weights and the RBF centers
and variances (see figure 11 for pseudo-code of this algorithm). In this
way, the network fine-tunes itself to the data after the initial clustering
step, yet, of course, overfitting has to be avoided with careful tuning of
the regularization parameter, the number of centers K and the number of
iterations (cf. [3]). In our experiments we always used
to ten CG iterations.


--R

Combining support vector and mathematical programming methods for induction.
A boosting algorithm for regression.
Neural Networks for Pattern Recognition.
A training algorithm for optimal margin classifiers.
Bagging predictors.
Arcing the edge.

Prediction games and arcing algorithms.
Support vector networks.
A decision-theoretic generalization of on-line learning and an application to boosting
Game theory
Additive logistic regres- sion: a statistical view of boosting

Boosting in the limit: Maximizing the margin of learned ensembles.
Optimization by simulated annealing: Quantitative studies.
Learning algorithms for classification: A comparism on handwritten digit recognistion.
Nonlinear Programming.
Improved generalization through explicit optimization of margins.
Fast learning in networks of locally-tuned processing units
Using support vector machines for time series prediction.
Using support vector machines for time series prediction.
An asymptotic analysis of AdaBoost in the binary classification case.
Numerical Recipes in C.

Boosting first-order learning
Ensemble learning methods for classifi- cation
Improved boosting algorithms using confidence-rated predictions
Boosting the margin: a new explanation for the effectiveness of voting methods.
AdaBoosting neural networks.
The Nature of Statistical Learning Theory.
Density estimation using sv machines.
--TR
A training algorithm for optimal margin classifiers
Numerical recipes in C (2nd ed.)
C4.5: programs for machine learning
The nature of statistical learning theory
Networks
Bagging predictors
Game theory, on-line prediction and boosting
Improved boosting algorithms using confidence-rated predictions
The connection between regularization operators and support vector kernels
Boosting in the limit
Using support vector machines for time series prediction
Combining support vector and mathematical programming methods for classification
Regularizing AdaBoost
Improved Generalization Through Explicit Optimization of Margins
Neural Networks for Pattern Recognition
Boosting the margin
AdaBoosting Neural Networks
A Boosting Algorithm for Regression
Theoretical Views of Boosting
Barrier Boosting
Boosting First-Order Learning

--CTR
Masayuki Nakamura , Hiroki Nomiya , Kuniaki Uehara, Improvement of Boosting Algorithm by Modifying the Weighting Rule, Annals of Mathematics and Artificial Intelligence, v.41 n.1, p.95-109, May 2004
Rong Jin , Huan Liu, Robust feature induction for support vector machines, Proceedings of the twenty-first international conference on Machine learning, p.57, July 04-08, 2004, Banff, Alberta, Canada
Theodore B. Trafalis , Alexander M. Malyscheff, An Analytic Center Machine, Machine Learning, v.46 n.1-3, p.203-223, 2002
Yuan (Alan) Qi , Thomas P. Minka , Rosalind W. Picard , Zoubin Ghahramani, Predictive automatic relevance determination by expectation propagation, Proceedings of the twenty-first international conference on Machine learning, p.85, July 04-08, 2004, Banff, Alberta, Canada
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
Jacek ski, Ho--Kashyap classifier with generalization control, Pattern Recognition Letters, v.24 n.14, p.2281-2290, October
E. Andeli , M. Schaffner , M. Katz , S. E. Krger , A. Wendemuth, Kernel least-squares models using updates of the pseudoinverse, Neural Computation, v.18 n.12, p.2928-2935, December 2006
Alain Rakotomamonjy, Variable selection using svm based criteria, The Journal of Machine Learning Research, 3, 3/1/2003
Rong Jin , Jian Zhang, A smoothed boosting algorithm using probabilistic output codes, Proceedings of the 22nd international conference on Machine learning, p.361-368, August 07-11, 2005, Bonn, Germany
Ulrike von Luxburg , Olivier Bousquet , Bernhard Schlkopf, A Compression Approach to Support Vector Model Selection, The Journal of Machine Learning Research, 5, p.293-323, 12/1/2004
Training algorithms for fuzzy support vector machines with noisy data, Pattern Recognition Letters, v.25 n.14, p.1647-1656, 15 October 2004
Saharon Rosset , Ji Zhu , Trevor Hastie, Boosting as a Regularized Path to a Maximum Margin Classifier, The Journal of Machine Learning Research, 5, p.941-973, 12/1/2004
Yoshikazu Washizawa , Yukihiko Yamashita, Kernel projection classifiers with suppressing features of other classes, Neural Computation, v.18 n.8, p.1932-1950, August 2006
Steve A. Billings , Kian L. Lee, Nonlinear Fisher discriminant analysis using a minimum squared error cost function and the orthogonal least squares algorithm, Neural Networks, v.15 n.2, p.263-270, March 2002
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
Takashi Takenouchi , Shinto Eguchi, Robustifying AdaBoost by Adding the Naive Error Rate, Neural Computation, v.16 n.4, p.767-787, April 2004
Manfred K. Warmuth , Jun Liao , Gunnar Rtsch, Totally corrective boosting algorithms that maximize the margin, Proceedings of the 23rd international conference on Machine learning, p.1001-1008, June 25-29, 2006, Pittsburgh, Pennsylvania
Olivier Chapelle , Vladimir Vapnik , Olivier Bousquet , Sayan Mukherjee, Choosing Multiple Parameters for Support Vector Machines, Machine Learning, v.46 n.1-3, p.131-159, 2002
Koji Tsuda , Motoaki Kawanabe , Gunnar Rtsch , Sren Sonnenburg , Klaus-Robert Mller, A new discriminative kernel from probabilistic models, Neural Computation, v.14 n.10, p.2397-2414, October 2002
N. Louw , S. J. Steel, Variable selection in kernel Fisher discriminant analysis by means of recursive feature elimination, Computational Statistics & Data Analysis, v.51 n.3, p.2043-2055, December, 2006
Wei Chu , S. Sathiya Keerthi , Chong Jin Ong, Bayesian trigonometric support vector classifier, Neural Computation, v.15 n.9, p.2227-2254, September
Stefano Merler , Bruno Caprile , Cesare Furlanello, Parallelizing AdaBoost by weights dynamics, Computational Statistics & Data Analysis, v.51 n.5, p.2487-2498, February, 2007
Cesare Furlanello , Maria Serafini , Stefano Merler , Giuseppe Jurman, Semisupervised Learning for Molecular Profiling, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.2, p.110-118, April 2005
Jimmy Liu Jiang , Kia-Fock Loe , Hong Jiang Zhang, Robust face detection in airports, EURASIP Journal on Applied Signal Processing, v.2004 n.1, p.503-509, 1 January 2004
Carl Gold , Alex Holub , Peter Sollich, Bayesian approach to feature selection and parameter tuning for support vector machine classifiers, Neural Networks, v.18 n.5-6, p.693-701, June 2005
Daniel S. Yeung , Defeng Wang , Wing W. Ng , Eric C. Tsang , Xizhao Wang, Structured large margin machines: sensitive to data distributions, Machine Learning, v.68 n.2, p.171-200, August    2007
Peter Bhlmann , Bin Yu, Sparse Boosting, The Journal of Machine Learning Research, 7, p.1001-1024, 12/1/2006
Senjian An , Wanquan Liu , Svetha Venkatesh, Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression, Pattern Recognition, v.40 n.8, p.2154-2162, August, 2007
Arthur Tenenhaus , Alain Giron , Emmanuel Viennet , Michel Bra , Gilbert Saporta , Bernard Fertil, Kernel logistic PLS: A tool for supervised nonlinear dimensionality reduction and binary classification, Computational Statistics & Data Analysis, v.51 n.9, p.4083-4100, May, 2007
G. Blanchard , C. Schfer , Y. Rozenholc , K.-R. Mller, Optimal dyadic decision trees, Machine Learning, v.66 n.2-3, p.209-241, March     2007
Gonzalo Martnez-Muoz , Alberto Surez, Using boosting to prune bagging ensembles, Pattern Recognition Letters, v.28 n.1, p.156-165, January, 2007
Gilles Blanchard, Different Paradigms for Choosing Sequential Reweighting Algorithms, Neural Computation, v.16 n.4, p.811-836, April 2004
Yoram Baram , Ran El-Yaniv , Kobi Luz, Online Choice of Active Learning Algorithms, The Journal of Machine Learning Research, 5, p.255-291, 12/1/2004
E. K. Tang , P. N. Suganthan , X. Yao, An analysis of diversity measures, Machine Learning, v.65 n.1, p.247-271, October   2006
Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
Gunnar Rtsch , Manfred K. Warmuth, Efficient Margin Maximizing with Boosting, The Journal of Machine Learning Research, 6, p.2131-2152, 12/1/2005
Michael E. Tipping, Sparse bayesian learning and the relevance vector machine, The Journal of Machine Learning Research, 1, p.211-244, 9/1/2001
Jiann-Ming Wu, Natural discriminant analysis using interactive Potts models, Neural Computation, v.14 n.3, p.689-713, March 2002
Nigel Duffy , David Helmbold, Boosting Methods for Regression, Machine Learning, v.47 n.2-3, p.153-200, May-June 2002
X. Hong , R. J. Mitchell, Backward elimination model construction for regression and classification using leave-one-out criteria, International Journal of Systems Science, v.38 n.2, p.101-113, 01 February 2007
Mathias M. Adankon , Mohamed Cheriet, Optimizing resources in model selection for support vector machine, Pattern Recognition, v.40 n.3, p.953-963, March, 2007
Robust Loss Functions for Boosting, Neural Computation, v.19 n.8, p.2183-2244, August 2007
Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002
Rong Jin , Jian Zhang, Multi-Class Learning by Smoothed Boosting, Machine Learning, v.67 n.3, p.207-227, June      2007
Philip M. Long , Vinsensius Berlian Vega, Boosting and Microarray Data, Machine Learning, v.52 n.1-2, p.31-44, July-August
W. John Wilbur , Lana Yeganova , Won Kim, The Synergy Between PAV and AdaBoost, Machine Learning, v.61 n.1-3, p.71-103, November  2005
Kai-Quan Shen , Chong-Jin Ong , Xiao-Ping Li , Einar P. Wilder-Smith, Feature selection via sensitivity analysis of SVM probabilistic outputs, Machine Learning, v.70 n.1, p.1-20, January   2008
Philip M. Long, Minimum majority classification and boosting, Eighteenth national conference on Artificial intelligence, p.181-186, July 28-August 01, 2002, Edmonton, Alberta, Canada
Hochreiter , Klaus Obermayer, Support vector machines for dyadic data, Neural Computation, v.18 n.6, p.1472-1510, June 2006
Masashi Sugiyama, Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis, The Journal of Machine Learning Research, 8, p.1027-1061, 5/1/2007
Roman Krepki , Gabriel Curio , Benjamin Blankertz , Klaus-Robert Mller, Berlin Brain-Computer Interface-The HCI communication channel for discovery, International Journal of Human-Computer Studies, v.65 n.5, p.460-477, May, 2007
Gavin C. Cawley , Nicola L. C. Talbot, Preventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters, The Journal of Machine Learning Research, 8, p.841-861, 5/1/2007
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
Ralf Herbrich , Thore Graepel , Colin Campbell, Bayes point machines, The Journal of Machine Learning Research, 1, p.245-279, 9/1/2001
Gunnar Rtsch , Ayhan Demiriz , Kristin P. Bennett, Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces, Machine Learning, v.48 n.1-3, p.189-218, 2002
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
classification;support vectors;arcing;ADABOOST;soft margin;large margin