# Analysis of Generalization Ability for Different AdaBoost Variants Based on Classification and Regression Trees

Authors: Shuqiong Wu; Hiroshi Nagahashi
Journal: Journal of Electrical and Computer Engineering
 (2015)

---

## Abstract

As a machine learning method, AdaBoost is widely applied to data classification and object detection because of its robustness and efficiency. AdaBoost constructs a global and optimal combination of weak classifiers based on a sample reweighting. It is known that this kind of combination improves the classification performance tremendously. As the popularity of AdaBoost increases, many variants have been proposed to improve the performance of AdaBoost. Then, a lot of comparison and review studies for AdaBoost variants have also been published. Some researchers compared different AdaBoost variants by experiments in their own fields, and others reviewed various AdaBoost variants by basically introducing these algorithms. However, there is a lack of mathematical analysis of the generalization abilities for different AdaBoost variants. In this paper, we analyze the generalization abilities of six AdaBoost variants in terms of classification margins. The six compared variants are Real AdaBoost, Gentle AdaBoost, Modest AdaBoost, Parameterized AdaBoost, Margin-pruning Boost, and Penalized AdaBoost. Finally, we use experiments to verify our analyses.


---

## Body

## 1. Introduction

In the last two decades, AdaBoost and its variants were used in various fields, such as face detection [1, 2], hands detection [3, 4], and human detection [5]. AdaBoost was first introduced to the machine learning literature by Freund and Schapire [6]; and it has obtained tremendous success in classification. AdaBoost is proved efficient in increasing the classification margins of training data [7]. To describe AdaBoost mathematically, Schapire and Singer proposed Real AdaBoost, which is a generalized version of AdaBoost [8]. Real AdaBoost calculates its weak hypotheses by directly optimizing the upper bounds of training errors. Therefore, it converges faster than AdaBoost in the training [9]. To improve the training speed of Real AdaBoost, Wu and Nagahashi devised Parameterized AdaBoost which utilizes a new weight adjustment policy [10]. In 2000, Friedman et al. used additive logistic models to explain AdaBoost and proposed Gentle AdaBoost which computes weak hypotheses by minimizing the least square errors [11]. Friedman et al. also proved that Gentle AdaBoost is more robust than AdaBoost and Real AdaBoost [11]. For reducing the generalization error of Gentle AdaBoost, A. Vezhnevets and V. Vezhnevets suggested Modest AdaBoost which highlights weak classifiers that work well on difficult-to-classify instances [12]. Modest AdaBoost achieves better generalization errors than Gentle AdaBoost in some data sets [13]. However, its performance is unstable because the accuracy drops occasionally. For the same purpose, Wu and Nagahashi devised Margin-pruning Boost [14] and Penalized AdaBoost [15]. Margin-pruning Boost applies a weight reinitialization approach to reduce the influence from noise-like data, while Penalized AdaBoost improves Margin-pruning Boost by introducing an adaptive weight resetting policy. Moreover, it utilizes a margin distribution to penalize the misclassification of small-margin instances. Freund created BrownBoost to reduce the influence of outliers in training [16]. LPBoost was introduced to optimize the minimal margin of training data by using linear programming [17]. However, a comparison showed that LPBoost overall performs worse than AdaBoost [18]. Similarly to Margin-pruning Boost, MadaBoost and SmoothBoost were devised to increase the robustness against malicious noise data [19, 20]. Some AdaBoost variants such as AdaCost, AdaC1, AdaC2, AdaC3, CSB0, CSB1, CSB2, and RareBoost assign weights to positive training instances and negative training instances differently to obtain a better performance on imbalanced data sets [21–24]. While others trade off the integrity of training data for a faster training [25–28]. In 2004, AdaTree was proposed to speed up the training process. It utilizes the same way as in AdaBoost to select weak classifiers but combines them in a nonlinear manner [29]. Filterboost and Regularized AdaBoost were proposed to solve overfitting problem [30, 31]. Filterboost is based on a new logistic regression technique whereas Regularized AdaBoost requires validation subsets to identify and correct the overfitting iteratively. FloatBoost and FM-AdaBoost filter the less effective weak classifiers so that they can outperform AdaBoost when they have the same number of weak classifiers as AdaBoost [32, 33]. Nevertheless, they require more training cycles than AdaBoost. Nowadays, many novel AdaBoost variants were devised to improve the generalization ability such as SoftBoost, Interactive Boosting, ReweightBoost, Soft-LPBoost, and RobustBoost [34–39]. SoftBoost maximizes a soft margin instead of the hard margin used in AdaBoost [34, 36]. Interactive Boosting gives weights to both features and training instances [37]. ReweightBoost builds a tree structure by reusing the selected weak classifiers. Nevertheless, it can only use stump decision trees as its weak classifiers [38]. Soft-LPBoost combines SoftBoost with LPBoost [39]. While RobustBoost is an extension of BrownBoost [35]. All the five AdaBoost variants can achieve better generalization errors than AdaBoost. However, they suffered from a lot of complicated calculations which may lead to a longer training time. In the last few years, A novel approach called SemiBoost has been developed rapidly. It combines supervised learning with semisupervised learning by using both the labelled and unlabelled training instances [40]. The purpose of SemiBoost is to increase the generalization ability when the labelled training instances are insufficient [41]. In addition, AdaBoost.M1, Conservative.2 AdaBoost, and Aggressive AdaBoost are AdaBoost variants proposed for multiple classification problems [42].With the proposals of many AdaBoost variants, a lot of surveys and comparison studies based on these variants were published. Miao and Heaton compared AdaBoost with Random Forest in ecosystem classification problems and showed that AdaBoost overall outperforms Random Forest [43]. Another comparison of AdaBoost and neural networks proved that AdaBoost ensemble of trees performs better than an individual neural network in experiments using cross validations [44]. Research in [45] applied AdaBoost and SVM to the Synthetic Aperture Radar Automatic Target Recognition Systems and found that AdaBoost is more robust than SVM. Ferreira briefly introduced many boosting algorithms and labelled them as “supervised learning” or “semisupervised learning” [46]. Seiffert et al. compared resampling boost algorithms with reweighting boost algorithms on imbalanced data sets and summarized that boosting by resampling generally outperforms boosting by reweighting [47]. A comparison of LPBoost and AdaBoost based on the experimental results of UCI repository was also conducted in [18]. Hegazy and Denzler evaluated AdaBoost and SoftBoost in generic object recognition and concluded that AdaBoost is more suitable for low-noise data sets while SoftBoost is more suitable for high-noise data sets [48]. Another study which compares AdaBoost with AdaTree was accomplished by Drauschke and Forstner [49]. Its experimental results showed that AdaTree usually performs better than AdaBoost but is prone to overfitting due to its tree-like structure. Jurić-Kavelj and Petrović evaluated three AdaBoost variants (Real, Gentle, and Modest AdaBoost) based on experiments in leg detection and found that Modest AdaBoost can not reduce the error rate as the number of iterations increases [50]. Sun et al. compared Discrete, Real, and Gentle AdaBoost by analyzing the experimental results in license plate detection and explained that Gentle AdaBoost achieves better performance than the other two methods [51]. Comparison in [52] focused on comparing weak classifiers of AdaBoost constructed by Bayes net, naive Bayes, and decision trees, and it showed that decision trees are the best. A review systematically introduced AdaBoost variants proposed during 1999 to 2012. Nevertheless, there is a lack of comparison between different AdaBoost variants [53].In general, the above surveys and comparison studies either introduce the basic ideas of AdaBoost variants or compare different AdaBoost variants by experiments in a specific research. Differently from these studies, we compare the generalization abilities of six AdaBoost variants (Real AdaBoost, Gentle AdaBoost, Modest AdaBoost, Parameterized AdaBoost, Margin-pruning Boost, and Penalized AdaBoost) by analyzing the classification margins. The remainder of this paper is organized as follows. Section2 explains the materials and methods. Section 3 shows experimental results. Section 4 draws a conclusion.


## 2. Materials and Methods

This section describes the training data and weak classifiers used in our research. It also explains the basic ideas of the six compared AdaBoost variants and their generalization abilities in terms of the classification margins.


### 2.1. Training Data and Weak Classifiers

Here we give a brief introduction of the training data. GivenS
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
N
,
y
N
)
} is a training set, where N is the number of instances. We let y
i be 1 if x
i is positive, or −1 if x
i is negative. In this paper, we only discuss binary classification problems. We use CART as weak classifiers [54]. As shown in Figure 1, a CART is a decision tree whose leaves output the classification results and inner nodes split the tree to minimize its error rate. In Figure 1, X
i
=
[
x
i
,
1
,
x
i
,
2
,
…
,
x
i
,
m
] is the feature vector of instance x
i [54].Figure 1
An example of classification and regression tree.


### 2.2. Different AdaBoost Variants

#### 2.2.1. AdaBoost and Real AdaBoost

AdaBoost is a machine learning method. At each round, it increases the weights of misclassified instances and decreases the weights of correctly classified instances. The weight adjustment policy is most important because AdaBoost can focus on difficult-to-classify instances. A generalized version of AdaBoost which is called Real AdaBoost is described as follows.Algorithm 1 (Real AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances to divide the training setS into C partitions. Each leaf of the CART represents a partition. For any partition S
t
j where j
∈
{
1,2
,
…
,
C
}, calculate W
t
+
j and W
t
-
j as follows:
(1)
W
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
i
,
t
.
W
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
i
,
t
.
(b) Compute the weak hypothesis for each partitionS
t
j:
(2)
f
t
j
(
x
)
=
0.5
×
ln
⁡
⁡
W
t
+
j
W
t
-
j
.
For any training instance x
i, let its weak hypothesis f
t
(
x
i
) be f
t
j
(
x
), where j is the index of partition that x
i falls into.
(c) Do weight updating by(3)
w
i
,
t
+
1
=
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
Z
t
,
Z
t
=
∑
i
‍
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In AdaBoost, the values of weak hypotheses are +1 or −1. But in Real AdaBoost, they are real numbers. The sign of each weak hypothesisf
t
j
(
x
) stands for the class of the weighted majority of instances falls into the partition S
t
j, and the absolute value of f
t
j
(
x
) represents a predication confidence.


#### 2.2.2. Gentle AdaBoost

Gentle AdaBoost utilizes the same weight adjustment policy as Real AdaBoost does. However, it computes the weak hypotheses in a different way. Next we introduce Gentle AdaBoost as follows.Algorithm 2 (Gentle AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j:
(4)
f
t
j
(
x
)
=
W
t
+
j
-
W
t
-
j
W
t
+
j
+
W
t
-
j
.
For any training instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In Algorithm2, the weak hypotheses are calculated by optimizing the weighted least square errors. Thus, it is more robust and stable than AdaBoost [11].


#### 2.2.3. Modest AdaBoost

Modest AdaBoost was proposed to suppress the generalization error of Gentle AdaBoost. It is explained by Algorithm3.Algorithm 3 (Modest AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate an inverted weightw
¯
i
,
t by
(5)
w
¯
i
,
t
=
1
-
w
i
,
t
M
t
,
where M
t
=
∑
i
‍
(
1
-
w
i
,
t
). Then compute W
¯
t
+
j and W
¯
t
-
j for each partition S
t
j as
(6)
W
¯
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
¯
i
,
t
,
W
¯
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
¯
i
,
t
.
(c) Compute the weak hypothesis for every partitionS
t
j:
(7)
f
t
j
(
x
)
=
W
t
+
j
(
1
-
W
¯
t
+
j
)
-
W
t
-
j
(
1
-
W
¯
t
-
j
)
.
For an instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Modest AdaBoost uses an “inverted” distribution to decrease the contribution of weak hypotheses that only work well on instances with small weights [12].


#### 2.2.4. Parameterized AdaBoost

Parameterized AdaBoost is shown by Algorithm4. Its purpose is to speed up the training process of Real AdaBoost.Algorithm 4 (Parameterized AdaBoost).
(1) Set the initial conditions in this step by lettingw
i
,
1
=
1
/
N and F
0
(
x
i
)
=
0, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate the weak hypotheses by (2).
(c) LetF
t
(
x
i
)
=
F
t
-
1
(
x
i
)
+
f
t
(
x
i
) and α
∈
(
0,1
). Then update the weights of instances by
(8)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
Z
t
,
(9)
Z
t
=
∑
i
‍
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
.
(3) Output the strong classifierH
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].For tuning parameterα, the training and generalization errors on a data set Gamma Telescope which includes nearly 20000 instances were measured for α
=
{
0.1,0.3,0.5,0.7,0.9
}. The results showed that α
=
0.5 has the best overall performance, so α is set to be 0.5 [10].The difference between Real and Parameterized AdaBoost is the weight updating policy. In Step (2)(c), Parameterized AdaBoost adds a parameter and an absolute item to emphasize the instances whose margins are near 0 [10].


#### 2.2.5. Margin-Pruning Boost

Margin-pruning Boost was designed to decrease the influence of noise-like instances. Next we describe this approach as follows.Algorithm 5 (Margin-pruning Boost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j by (4).
(c) Update the weights of instances as(10)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(d) Set a thresholdQ
t
+
1 by the following equation:
(11)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
50
.
For any instance x
i, if w
i
,
t
+
1
>
Q
t
+
1, reset w
i
,
t
+
1
=
1 and ∑
t
‍
f
t
(
x
i
)
=
0. Compute Z
t
=
∑
i
‍
w
i
,
t
+
1; then do normalization by letting w
i
,
t
+
1
=
w
i
,
t
+
1
/
Z
t.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Margin-pruning Boost restrains the weight increase of potential noise instances by resetting their weights and summed weak hypotheses [14]. Here the resetting of the sum of weak hypotheses can keep the weights of noise-like instances small. On the other hand, the resetting means that the combination of these weak hypotheses (the current strong hypothesis) for these noise-like instances is reset to be 0 because it can not correctly classify these instances.


#### 2.2.6. Penalized AdaBoost

Penalized AdaBoost is an extension of Margin-pruning Boost. It introduces a margin distribution to penalize the misclassification of small-margin instances. Before introducing Penalized AdaBoost, we first explain the classification margins. The classification margin of an instancex
i shows the difference between prediction confidence of weak hypotheses providing correct classification and that of weak hypotheses leading to misclassification [7]. It is in the range [
-
1,1
], and the instance x
i is correctly classified if and only if its margin is positive [7]. Therefore, the margin of instance x
i is defined as [10]
(12)
Margin
T
x
i
=
∑
t
=
1
T
‍
y
i
f
t
x
i
∑
t
=
1
T
‍
f
t
x
i
,
where f
t
(
x
i
) denotes the weak hypothesis for instance x
i at round t and T is the number of total iterations. Next we explain Penalized AdaBoost by the following algorithm.Algorithm 6 (Penalized AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate a margin feedback factorm
i
,
t as shown in
(13)
m
i
,
t
=
exp
⁡
⁡
-
Margin
t
-
1
x
i
D
t
,
where D
t equals ∑
i
‍
exp
⁡
⁡
(
-
Margin
t
-
1
(
x
i
)
). Then compute M
t
+
j and M
t
-
j of every partition S
t
j by
(14)
M
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
m
i
,
t
,
M
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
m
i
,
t
.
(c) Compute the weak hypothesis for eachS
t
j as
(15)
f
t
j
(
x
)
=
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
-
j
)
,
if
W
t
+
j
>
W
t
-
j
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
+
j
)
,
otherwise
.
For each instance x
i, set its weak hypothesis f
t
(
x
i
) to be f
t
j
(
x
), where j is the index of partition which x
i falls into.
(d) Update all instance weights by(16)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(e) For each instancex
i, if w
i
,
t
+
1
>
Q
t
+
1 and Margin
t
(
x
i
)
<
0, reinitialize instance x
i as follows:
(17)
w
i
,
t
+
1
=
1
,
∑
t
‍
f
t
(
x
i
)
=
0
.
(18)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
β
.
Then normalize w
i
,
t
+
1 by letting ∑
i
‍
w
i
,
t
+
1
=
1.
(3) SetF
T
(
x
)
=
∑
t
=
1
T
‍
f
t
(
x
) and output the strong classifier H
(
x
)
=
sign
⁡
[
F
T
(
x
)
].Penalized AdaBoost calculates its weak hypotheses by introducing a margin feedback factor in Steps (2)(b) and (2)(c). Moreover, it improves the thresholding of Margin-pruning Boost in Step (2)(e). The parameterβ in (18) is tuned by the following steps: first the classification performances on 5 data sets with different values of β (β = 10; 30; 50; 70; 90) are evaluated, and then the value with the best performance is assigned to β [15]. Then we will analyze the generalization abilities of the six variants in the next section.


### 2.3. Generalization Ability Analysis

In this section, we analyze the generalization abilities of the six AdaBoost variants by comparing their weak hypotheses and weight updating policies.


#### 2.3.1. Real and Gentle AdaBoost

The difference between Real and Gentle AdaBoost is how they calculate their weak hypotheses. Real AdaBoost computes the weak hypothesis by minimizing the upper bound of training error in each loop [8]. Gentle AdaBoost calculates its weak hypothesis by optimizing the weighted least square error iteratively [11]. Real AdaBoost tries to decrease the training error whereas Gentle AdaBoost aims at reducing the variance of its weak hypotheses. Thus, in most cases, Real AdaBoost converges faster than Gentle AdaBoost in training, but Gentle AdaBoost is more stable than Real AdaBoost with respect to the generalization error.


#### 2.3.2. Real and Parameterized AdaBoost

Comparing Step (2)(c) in Real AdaBoost with that in Parameterized AdaBoost, we find that the weight updating policies of the two variants are different. From (12), we know that the training error converges to 0 if and only if the margins of all training instances are increased to be positive. In Step (2)(c) of Real AdaBoost, instances with small margins obtain more weights so that they are more likely correctly classified in future iterations. However, as Real AdaBoost focuses on instances with small margins, it may lead to an increase of instances whose margins are near 0; that is, these instances change the sign of their margins back and forth in the boosting process. Here we call them “swinging instances.” These swinging instances slow the convergence of training error. To decrease the number of swinging instances, Parameterized AdaBoost introduces parameter α to give them larger weights. From (8), we can see that α
×
|
y
i
F
t
(
x
i
)
| reduces more weight for instances whose margins are far from 0 and less weight for swinging instances. Therefore, swinging instances obtain more attention than nonswinging ones. Parameterized AdaBoost aims at reducing the number of swinging instances by trying to correctly classify them in the early training phase. Thus, Parameterized AdaBoost can converge faster than Real AdaBoost in training. With respect to the generalization error, Parameterized AdaBoost is more prone to overfitting than Real AdaBoost especially when the CART used as weak classifiers has more inner nodes. The reason is that it focuses more on swinging instances at the cost of focusing less on instances with minimal margins. However, it can perform similarly to or slightly better than Real AdaBoost if it uses simple weak classifiers such as stump decision trees because stump trees are more resistant to overfitting than CART with many inner nodes.


#### 2.3.3. Gentle and Modest AdaBoost

Modest AdaBoost utilizes an inverted weight distribution to highlight weak hypotheses that can correctly classify instances with small margins. Nevertheless, the performance of Modest AdaBoost is not stable. Here we give an example to explain the reason. We supposeW
t
+
j
>
W
t
-
j; if W
t
+
j
(
1
-
W
¯
t
+
j
) is also larger than W
t
-
j
(
1
-
W
¯
t
-
j
), the factor (
1
-
W
¯
t
+
j
) assigns higher prediction confidence to weak hypotheses that correctly classify small-margin instances. At the same time, the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost outperforms Gentle AdaBoost. However, if W
t
+
j
(
1
-
W
¯
t
+
j
) is smaller than W
t
-
j
(
1
-
W
¯
t
-
j
) in the case W
t
+
j
>
W
t
-
j, the sign of the weak hypothesis will be negative. This means the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses that correctly classify small-margin instances. Meanwhile, (
1
-
W
¯
t
+
j
) increases the prediction confidence of weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost performs far worse than Gentle AdaBoost.


#### 2.3.4. Gentle and Margin-Pruning Boost

At each round of Gentle AdaBoost, the weights of misclassified instances are increased whereas the weights of correctly classified instances are decreased. This will lead to the phenomenon that the weights of difficult-to-classify instances are increased too large. If these instances are noise data or outliers, the performance of the final strong classifier will be degraded. To solve this problem, Margin-pruning Boost utilizes a threshold to filter instances whose weights are too large and then resets their weights to be 1.Margin-pruning Boost reduces the influence from noise-like instances effectively in the early training phase by restraining the weight increase of filtered instances [14]. However, as the number of iterations increases, the weights of instances filtered by thresholding become smaller and smaller. In the late training phase, the weights of these filtered instances are probably reduced smaller than 1. In that case, resetting their weights to be 1 actually increases the influence of these instances. Thus, the performance of Margin-pruning Boost drops when the number of loops increases.


#### 2.3.5. Margin-Pruning Boost and Penalized AdaBoost

Penalized AdaBoost is an improvement of Margin-pruning Boost. First it introduces a margin feedback factor to assign higher prediction confidence to weak hypotheses that can correctly classify small-margin instances. From (13), (14), and (15), we can see that (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
) are proportional to the margins, and they are computed from the sum of margin feedback factors of misclassified instances. This means that misclassifying small-margin instances will lead to small (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
). Therefore, the prediction confidence of weak hypotheses which misclassify small-margin instances will be degraded. Compared with Gentle AdaBoost and Margin pruning Boost, Penalized AdaBoost can stand out more competent weak hypotheses. Therefore, it is more robust than the other two variants. Modest AdaBoost highlights more competent weak hypotheses in some cases but downplays these weak hypotheses in other cases. By contrast, Penalized AdaBoost attaches importance to these more competent weak hypotheses under any circumstance. Thus it is more stable than Modest AdaBoost.Furthermore, Penalized AdaBoost solves the problem of Margin-pruning Boost by utilizing a more adaptive thresholding method. Penalized AdaBoost also uses the thresholding to filter the large-weight instances similarly to Margin-pruning Boost. However, it only resets the weights of filtered instances with negative margins. This technique guarantees that the reset weights are always smaller than the original ones. For these noise-like instances, Penalized AdaBoost does not completely exclude them because they are not definitely noise. Nevertheless, Penalized AdaBoost keeps their weights small to reduce their influence on the final strong classifier. Thereby, it has better generalization ability than Margin-pruning Boost.


### 2.4. Margin Distribution Comparison

In this section, we compare the generalization abilities of the six different variants by analyzing their margin distributions. Li and Shen showed that reducing the minimal margin of training data plays little role in improving the generalization ability [18]. However, enlarging the whole margin distribution to obtain a balance between the training error and complexity is crucial to the generalization ability [18]. Here we use three kinds of CART as weak classifiers to evaluate the six AdaBoost variants. The three kinds of CART are CART-1 (CART with one inner node), CART-2 (CART with two inner nodes), and CART-3 (CART with three inner nodes). To get the cumulative margin distributions, for each data set, we use 2
/
3 of its data to train the final strong classifiers. Figure 2 shows the cumulative margin distributions based on CART-1 in data set German at iteration 200. Figure 3 shows the generalization errors of the same data set with respect to Figure 2. In Figure 2, Penalized AdaBoost enlarges the whole margin distribution more than the other variants so that it achieves the best generalization error in Figure 3. Real AdaBoost, Gentle AdaBoost, Parameterized AdaBoost, and Margin-pruning Boost perform similarly on the margins. So their generalization errors are also similar when the number of iterations reaches to 200. The margin curve of Modest AdaBoost in Figure 2 is not smooth. That may explain why its generalization error in Figure 3 is not changed gradually.Figure 2
Margin distributions using CART-1 at iteration 200.Figure 3
Generalization errors using CART-1.Margin distributions based on CART-2 in the same data set at iteration 200 are shown in Figure4. Figure 5 shows the generalization errors with respect to Figure 4. From Figures 4 and 5, we notice that the generalization abilities of the six variants are consistent with their performance on the margins. We also evaluate margin distributions using CART-3 on the data set German. Margin curves at iterations 10, 100, and 1000 are shown by Figures 6, 7, and 8, respectively. Comparing the three figures, we find that the margins are enlarged gradually as the number of iterations increases. Furthermore, we notice that Margin-pruning Boost outperforms Gentle AdaBoost in Figures 6 and 7. However it performs worse than Gentle AdaBoost in Figure 8. This demonstrates that the performance of Margin-pruning Boost drops as the number of iterations increases. Differently from Margin-pruning Boost, Penalized AdaBoost outperforms others at most cases. Thus it is most robust and stable. Figure 9 shows the generalization errors of the six variants which use CART-3 as their weak classifiers. In Figure 9, Margin-pruning Boost obtains lower generalization errors than Gentle AdaBoost before iteration 500. Unfortunately, it leads to severe overfitting after iteration 500.Figure 4
Margin distributions using CART-2 at iteration 200.Figure 5
Generalization errors using CART-2.Figure 6
Margin distributions using CART-3 at iteration 10.Figure 7
Margin distributions using CART-3 at iteration 100.Figure 8
Margin distributions using CART-3 at iteration 1000.Figure 9
Generalization errors using CART-3.Figures10 and 11 show margin distributions of other data sets. From these margin curves, we can conclude that Penalized AdaBoost generally outperforms the other five variants on enlarging the whole margin distributions. Real and Gentle AdaBoost perform very similarly, and Parameterized AdaBoost is slightly worse than Real AdaBoost when it uses CART-2 and CART-3. Margin-pruning Boost is better than Gentle AdaBoost if the number of iterations is small, While the margin curves of Modest AdaBoost are not smooth, they may lead to an unstable performance on generalization errors.Margin distributions at iteration 200.
(a)
(b)Margin distributions at iteration 200.
(a)
(b)


## 2.1. Training Data and Weak Classifiers

Here we give a brief introduction of the training data. GivenS
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
N
,
y
N
)
} is a training set, where N is the number of instances. We let y
i be 1 if x
i is positive, or −1 if x
i is negative. In this paper, we only discuss binary classification problems. We use CART as weak classifiers [54]. As shown in Figure 1, a CART is a decision tree whose leaves output the classification results and inner nodes split the tree to minimize its error rate. In Figure 1, X
i
=
[
x
i
,
1
,
x
i
,
2
,
…
,
x
i
,
m
] is the feature vector of instance x
i [54].Figure 1
An example of classification and regression tree.


## 2.2. Different AdaBoost Variants

### 2.2.1. AdaBoost and Real AdaBoost

AdaBoost is a machine learning method. At each round, it increases the weights of misclassified instances and decreases the weights of correctly classified instances. The weight adjustment policy is most important because AdaBoost can focus on difficult-to-classify instances. A generalized version of AdaBoost which is called Real AdaBoost is described as follows.Algorithm 1 (Real AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances to divide the training setS into C partitions. Each leaf of the CART represents a partition. For any partition S
t
j where j
∈
{
1,2
,
…
,
C
}, calculate W
t
+
j and W
t
-
j as follows:
(1)
W
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
i
,
t
.
W
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
i
,
t
.
(b) Compute the weak hypothesis for each partitionS
t
j:
(2)
f
t
j
(
x
)
=
0.5
×
ln
⁡
⁡
W
t
+
j
W
t
-
j
.
For any training instance x
i, let its weak hypothesis f
t
(
x
i
) be f
t
j
(
x
), where j is the index of partition that x
i falls into.
(c) Do weight updating by(3)
w
i
,
t
+
1
=
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
Z
t
,
Z
t
=
∑
i
‍
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In AdaBoost, the values of weak hypotheses are +1 or −1. But in Real AdaBoost, they are real numbers. The sign of each weak hypothesisf
t
j
(
x
) stands for the class of the weighted majority of instances falls into the partition S
t
j, and the absolute value of f
t
j
(
x
) represents a predication confidence.


### 2.2.2. Gentle AdaBoost

Gentle AdaBoost utilizes the same weight adjustment policy as Real AdaBoost does. However, it computes the weak hypotheses in a different way. Next we introduce Gentle AdaBoost as follows.Algorithm 2 (Gentle AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j:
(4)
f
t
j
(
x
)
=
W
t
+
j
-
W
t
-
j
W
t
+
j
+
W
t
-
j
.
For any training instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In Algorithm2, the weak hypotheses are calculated by optimizing the weighted least square errors. Thus, it is more robust and stable than AdaBoost [11].


### 2.2.3. Modest AdaBoost

Modest AdaBoost was proposed to suppress the generalization error of Gentle AdaBoost. It is explained by Algorithm3.Algorithm 3 (Modest AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate an inverted weightw
¯
i
,
t by
(5)
w
¯
i
,
t
=
1
-
w
i
,
t
M
t
,
where M
t
=
∑
i
‍
(
1
-
w
i
,
t
). Then compute W
¯
t
+
j and W
¯
t
-
j for each partition S
t
j as
(6)
W
¯
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
¯
i
,
t
,
W
¯
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
¯
i
,
t
.
(c) Compute the weak hypothesis for every partitionS
t
j:
(7)
f
t
j
(
x
)
=
W
t
+
j
(
1
-
W
¯
t
+
j
)
-
W
t
-
j
(
1
-
W
¯
t
-
j
)
.
For an instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Modest AdaBoost uses an “inverted” distribution to decrease the contribution of weak hypotheses that only work well on instances with small weights [12].


### 2.2.4. Parameterized AdaBoost

Parameterized AdaBoost is shown by Algorithm4. Its purpose is to speed up the training process of Real AdaBoost.Algorithm 4 (Parameterized AdaBoost).
(1) Set the initial conditions in this step by lettingw
i
,
1
=
1
/
N and F
0
(
x
i
)
=
0, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate the weak hypotheses by (2).
(c) LetF
t
(
x
i
)
=
F
t
-
1
(
x
i
)
+
f
t
(
x
i
) and α
∈
(
0,1
). Then update the weights of instances by
(8)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
Z
t
,
(9)
Z
t
=
∑
i
‍
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
.
(3) Output the strong classifierH
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].For tuning parameterα, the training and generalization errors on a data set Gamma Telescope which includes nearly 20000 instances were measured for α
=
{
0.1,0.3,0.5,0.7,0.9
}. The results showed that α
=
0.5 has the best overall performance, so α is set to be 0.5 [10].The difference between Real and Parameterized AdaBoost is the weight updating policy. In Step (2)(c), Parameterized AdaBoost adds a parameter and an absolute item to emphasize the instances whose margins are near 0 [10].


### 2.2.5. Margin-Pruning Boost

Margin-pruning Boost was designed to decrease the influence of noise-like instances. Next we describe this approach as follows.Algorithm 5 (Margin-pruning Boost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j by (4).
(c) Update the weights of instances as(10)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(d) Set a thresholdQ
t
+
1 by the following equation:
(11)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
50
.
For any instance x
i, if w
i
,
t
+
1
>
Q
t
+
1, reset w
i
,
t
+
1
=
1 and ∑
t
‍
f
t
(
x
i
)
=
0. Compute Z
t
=
∑
i
‍
w
i
,
t
+
1; then do normalization by letting w
i
,
t
+
1
=
w
i
,
t
+
1
/
Z
t.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Margin-pruning Boost restrains the weight increase of potential noise instances by resetting their weights and summed weak hypotheses [14]. Here the resetting of the sum of weak hypotheses can keep the weights of noise-like instances small. On the other hand, the resetting means that the combination of these weak hypotheses (the current strong hypothesis) for these noise-like instances is reset to be 0 because it can not correctly classify these instances.


### 2.2.6. Penalized AdaBoost

Penalized AdaBoost is an extension of Margin-pruning Boost. It introduces a margin distribution to penalize the misclassification of small-margin instances. Before introducing Penalized AdaBoost, we first explain the classification margins. The classification margin of an instancex
i shows the difference between prediction confidence of weak hypotheses providing correct classification and that of weak hypotheses leading to misclassification [7]. It is in the range [
-
1,1
], and the instance x
i is correctly classified if and only if its margin is positive [7]. Therefore, the margin of instance x
i is defined as [10]
(12)
Margin
T
x
i
=
∑
t
=
1
T
‍
y
i
f
t
x
i
∑
t
=
1
T
‍
f
t
x
i
,
where f
t
(
x
i
) denotes the weak hypothesis for instance x
i at round t and T is the number of total iterations. Next we explain Penalized AdaBoost by the following algorithm.Algorithm 6 (Penalized AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate a margin feedback factorm
i
,
t as shown in
(13)
m
i
,
t
=
exp
⁡
⁡
-
Margin
t
-
1
x
i
D
t
,
where D
t equals ∑
i
‍
exp
⁡
⁡
(
-
Margin
t
-
1
(
x
i
)
). Then compute M
t
+
j and M
t
-
j of every partition S
t
j by
(14)
M
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
m
i
,
t
,
M
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
m
i
,
t
.
(c) Compute the weak hypothesis for eachS
t
j as
(15)
f
t
j
(
x
)
=
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
-
j
)
,
if
W
t
+
j
>
W
t
-
j
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
+
j
)
,
otherwise
.
For each instance x
i, set its weak hypothesis f
t
(
x
i
) to be f
t
j
(
x
), where j is the index of partition which x
i falls into.
(d) Update all instance weights by(16)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(e) For each instancex
i, if w
i
,
t
+
1
>
Q
t
+
1 and Margin
t
(
x
i
)
<
0, reinitialize instance x
i as follows:
(17)
w
i
,
t
+
1
=
1
,
∑
t
‍
f
t
(
x
i
)
=
0
.
(18)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
β
.
Then normalize w
i
,
t
+
1 by letting ∑
i
‍
w
i
,
t
+
1
=
1.
(3) SetF
T
(
x
)
=
∑
t
=
1
T
‍
f
t
(
x
) and output the strong classifier H
(
x
)
=
sign
⁡
[
F
T
(
x
)
].Penalized AdaBoost calculates its weak hypotheses by introducing a margin feedback factor in Steps (2)(b) and (2)(c). Moreover, it improves the thresholding of Margin-pruning Boost in Step (2)(e). The parameterβ in (18) is tuned by the following steps: first the classification performances on 5 data sets with different values of β (β = 10; 30; 50; 70; 90) are evaluated, and then the value with the best performance is assigned to β [15]. Then we will analyze the generalization abilities of the six variants in the next section.


## 2.2.1. AdaBoost and Real AdaBoost

AdaBoost is a machine learning method. At each round, it increases the weights of misclassified instances and decreases the weights of correctly classified instances. The weight adjustment policy is most important because AdaBoost can focus on difficult-to-classify instances. A generalized version of AdaBoost which is called Real AdaBoost is described as follows.Algorithm 1 (Real AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances to divide the training setS into C partitions. Each leaf of the CART represents a partition. For any partition S
t
j where j
∈
{
1,2
,
…
,
C
}, calculate W
t
+
j and W
t
-
j as follows:
(1)
W
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
i
,
t
.
W
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
i
,
t
.
(b) Compute the weak hypothesis for each partitionS
t
j:
(2)
f
t
j
(
x
)
=
0.5
×
ln
⁡
⁡
W
t
+
j
W
t
-
j
.
For any training instance x
i, let its weak hypothesis f
t
(
x
i
) be f
t
j
(
x
), where j is the index of partition that x
i falls into.
(c) Do weight updating by(3)
w
i
,
t
+
1
=
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
Z
t
,
Z
t
=
∑
i
‍
w
i
,
t
exp
⁡
⁡
-
y
i
f
t
x
i
.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In AdaBoost, the values of weak hypotheses are +1 or −1. But in Real AdaBoost, they are real numbers. The sign of each weak hypothesisf
t
j
(
x
) stands for the class of the weighted majority of instances falls into the partition S
t
j, and the absolute value of f
t
j
(
x
) represents a predication confidence.


## 2.2.2. Gentle AdaBoost

Gentle AdaBoost utilizes the same weight adjustment policy as Real AdaBoost does. However, it computes the weak hypotheses in a different way. Next we introduce Gentle AdaBoost as follows.Algorithm 2 (Gentle AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j:
(4)
f
t
j
(
x
)
=
W
t
+
j
-
W
t
-
j
W
t
+
j
+
W
t
-
j
.
For any training instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].In Algorithm2, the weak hypotheses are calculated by optimizing the weighted least square errors. Thus, it is more robust and stable than AdaBoost [11].


## 2.2.3. Modest AdaBoost

Modest AdaBoost was proposed to suppress the generalization error of Gentle AdaBoost. It is explained by Algorithm3.Algorithm 3 (Modest AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate an inverted weightw
¯
i
,
t by
(5)
w
¯
i
,
t
=
1
-
w
i
,
t
M
t
,
where M
t
=
∑
i
‍
(
1
-
w
i
,
t
). Then compute W
¯
t
+
j and W
¯
t
-
j for each partition S
t
j as
(6)
W
¯
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
w
¯
i
,
t
,
W
¯
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
w
¯
i
,
t
.
(c) Compute the weak hypothesis for every partitionS
t
j:
(7)
f
t
j
(
x
)
=
W
t
+
j
(
1
-
W
¯
t
+
j
)
-
W
t
-
j
(
1
-
W
¯
t
-
j
)
.
For an instance x
i, its weak hypothesis f
t
(
x
i
) equals f
t
j
(
x
), where j is the index of partition that x
i belongs to.
(c) Update instances’ weights by (3).
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Modest AdaBoost uses an “inverted” distribution to decrease the contribution of weak hypotheses that only work well on instances with small weights [12].


## 2.2.4. Parameterized AdaBoost

Parameterized AdaBoost is shown by Algorithm4. Its purpose is to speed up the training process of Real AdaBoost.Algorithm 4 (Parameterized AdaBoost).
(1) Set the initial conditions in this step by lettingw
i
,
1
=
1
/
N and F
0
(
x
i
)
=
0, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate the weak hypotheses by (2).
(c) LetF
t
(
x
i
)
=
F
t
-
1
(
x
i
)
+
f
t
(
x
i
) and α
∈
(
0,1
). Then update the weights of instances by
(8)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
Z
t
,
(9)
Z
t
=
∑
i
‍
exp
⁡
⁡
-
y
i
F
t
x
i
-
α
y
i
F
t
x
i
.
(3) Output the strong classifierH
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].For tuning parameterα, the training and generalization errors on a data set Gamma Telescope which includes nearly 20000 instances were measured for α
=
{
0.1,0.3,0.5,0.7,0.9
}. The results showed that α
=
0.5 has the best overall performance, so α is set to be 0.5 [10].The difference between Real and Parameterized AdaBoost is the weight updating policy. In Step (2)(c), Parameterized AdaBoost adds a parameter and an absolute item to emphasize the instances whose margins are near 0 [10].


## 2.2.5. Margin-Pruning Boost

Margin-pruning Boost was designed to decrease the influence of noise-like instances. Next we describe this approach as follows.Algorithm 5 (Margin-pruning Boost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Compute the weak hypothesis for each partitionS
t
j by (4).
(c) Update the weights of instances as(10)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(d) Set a thresholdQ
t
+
1 by the following equation:
(11)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
50
.
For any instance x
i, if w
i
,
t
+
1
>
Q
t
+
1, reset w
i
,
t
+
1
=
1 and ∑
t
‍
f
t
(
x
i
)
=
0. Compute Z
t
=
∑
i
‍
w
i
,
t
+
1; then do normalization by letting w
i
,
t
+
1
=
w
i
,
t
+
1
/
Z
t.
(3) LetF
T
(
x
i
)
=
∑
t
=
1
T
‍
f
t
(
x
i
) and output the strong classifier H
(
x
i
)
=
sign
⁡
[
F
T
(
x
i
)
].Margin-pruning Boost restrains the weight increase of potential noise instances by resetting their weights and summed weak hypotheses [14]. Here the resetting of the sum of weak hypotheses can keep the weights of noise-like instances small. On the other hand, the resetting means that the combination of these weak hypotheses (the current strong hypothesis) for these noise-like instances is reset to be 0 because it can not correctly classify these instances.


## 2.2.6. Penalized AdaBoost

Penalized AdaBoost is an extension of Margin-pruning Boost. It introduces a margin distribution to penalize the misclassification of small-margin instances. Before introducing Penalized AdaBoost, we first explain the classification margins. The classification margin of an instancex
i shows the difference between prediction confidence of weak hypotheses providing correct classification and that of weak hypotheses leading to misclassification [7]. It is in the range [
-
1,1
], and the instance x
i is correctly classified if and only if its margin is positive [7]. Therefore, the margin of instance x
i is defined as [10]
(12)
Margin
T
x
i
=
∑
t
=
1
T
‍
y
i
f
t
x
i
∑
t
=
1
T
‍
f
t
x
i
,
where f
t
(
x
i
) denotes the weak hypothesis for instance x
i at round t and T is the number of total iterations. Next we explain Penalized AdaBoost by the following algorithm.Algorithm 6 (Penalized AdaBoost).
(1) Set the initial weightsw
i
,
1
=
1
/
N, where i
=
1,2
,
…
,
N.
(2) Do the following tasks fort
=
1,2
,
…
,
T.
(a) Train a weak classifier based on the weighted instances and then calculateW
t
+
j and W
t
-
j for each partition S
t
j the same as in Step (2)(a) of Algorithm 1.
(b) Calculate a margin feedback factorm
i
,
t as shown in
(13)
m
i
,
t
=
exp
⁡
⁡
-
Margin
t
-
1
x
i
D
t
,
where D
t equals ∑
i
‍
exp
⁡
⁡
(
-
Margin
t
-
1
(
x
i
)
). Then compute M
t
+
j and M
t
-
j of every partition S
t
j by
(14)
M
t
+
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
1
‍
m
i
,
t
,
M
t
-
j
=
∑
i
:
x
i
∈
S
t
j
∧
y
i
=
-
1
‍
m
i
,
t
.
(c) Compute the weak hypothesis for eachS
t
j as
(15)
f
t
j
(
x
)
=
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
-
j
)
,
if
W
t
+
j
>
W
t
-
j
(
W
t
+
j
-
W
t
-
j
)
(
1
-
M
t
+
j
)
,
otherwise
.
For each instance x
i, set its weak hypothesis f
t
(
x
i
) to be f
t
j
(
x
), where j is the index of partition which x
i falls into.
(d) Update all instance weights by(16)
w
i
,
t
+
1
=
exp
⁡
⁡
-
y
i
∑
t
‍
f
t
x
i
.
(e) For each instancex
i, if w
i
,
t
+
1
>
Q
t
+
1 and Margin
t
(
x
i
)
<
0, reinitialize instance x
i as follows:
(17)
w
i
,
t
+
1
=
1
,
∑
t
‍
f
t
(
x
i
)
=
0
.
(18)
Q
t
+
1
=
max
⁡
i
⁡
w
i
,
t
+
1
-
max
⁡
i
w
i
,
t
+
1
-
min
⁡
i
w
i
,
t
+
1
β
.
Then normalize w
i
,
t
+
1 by letting ∑
i
‍
w
i
,
t
+
1
=
1.
(3) SetF
T
(
x
)
=
∑
t
=
1
T
‍
f
t
(
x
) and output the strong classifier H
(
x
)
=
sign
⁡
[
F
T
(
x
)
].Penalized AdaBoost calculates its weak hypotheses by introducing a margin feedback factor in Steps (2)(b) and (2)(c). Moreover, it improves the thresholding of Margin-pruning Boost in Step (2)(e). The parameterβ in (18) is tuned by the following steps: first the classification performances on 5 data sets with different values of β (β = 10; 30; 50; 70; 90) are evaluated, and then the value with the best performance is assigned to β [15]. Then we will analyze the generalization abilities of the six variants in the next section.


## 2.3. Generalization Ability Analysis

In this section, we analyze the generalization abilities of the six AdaBoost variants by comparing their weak hypotheses and weight updating policies.


### 2.3.1. Real and Gentle AdaBoost

The difference between Real and Gentle AdaBoost is how they calculate their weak hypotheses. Real AdaBoost computes the weak hypothesis by minimizing the upper bound of training error in each loop [8]. Gentle AdaBoost calculates its weak hypothesis by optimizing the weighted least square error iteratively [11]. Real AdaBoost tries to decrease the training error whereas Gentle AdaBoost aims at reducing the variance of its weak hypotheses. Thus, in most cases, Real AdaBoost converges faster than Gentle AdaBoost in training, but Gentle AdaBoost is more stable than Real AdaBoost with respect to the generalization error.


### 2.3.2. Real and Parameterized AdaBoost

Comparing Step (2)(c) in Real AdaBoost with that in Parameterized AdaBoost, we find that the weight updating policies of the two variants are different. From (12), we know that the training error converges to 0 if and only if the margins of all training instances are increased to be positive. In Step (2)(c) of Real AdaBoost, instances with small margins obtain more weights so that they are more likely correctly classified in future iterations. However, as Real AdaBoost focuses on instances with small margins, it may lead to an increase of instances whose margins are near 0; that is, these instances change the sign of their margins back and forth in the boosting process. Here we call them “swinging instances.” These swinging instances slow the convergence of training error. To decrease the number of swinging instances, Parameterized AdaBoost introduces parameter α to give them larger weights. From (8), we can see that α
×
|
y
i
F
t
(
x
i
)
| reduces more weight for instances whose margins are far from 0 and less weight for swinging instances. Therefore, swinging instances obtain more attention than nonswinging ones. Parameterized AdaBoost aims at reducing the number of swinging instances by trying to correctly classify them in the early training phase. Thus, Parameterized AdaBoost can converge faster than Real AdaBoost in training. With respect to the generalization error, Parameterized AdaBoost is more prone to overfitting than Real AdaBoost especially when the CART used as weak classifiers has more inner nodes. The reason is that it focuses more on swinging instances at the cost of focusing less on instances with minimal margins. However, it can perform similarly to or slightly better than Real AdaBoost if it uses simple weak classifiers such as stump decision trees because stump trees are more resistant to overfitting than CART with many inner nodes.


### 2.3.3. Gentle and Modest AdaBoost

Modest AdaBoost utilizes an inverted weight distribution to highlight weak hypotheses that can correctly classify instances with small margins. Nevertheless, the performance of Modest AdaBoost is not stable. Here we give an example to explain the reason. We supposeW
t
+
j
>
W
t
-
j; if W
t
+
j
(
1
-
W
¯
t
+
j
) is also larger than W
t
-
j
(
1
-
W
¯
t
-
j
), the factor (
1
-
W
¯
t
+
j
) assigns higher prediction confidence to weak hypotheses that correctly classify small-margin instances. At the same time, the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost outperforms Gentle AdaBoost. However, if W
t
+
j
(
1
-
W
¯
t
+
j
) is smaller than W
t
-
j
(
1
-
W
¯
t
-
j
) in the case W
t
+
j
>
W
t
-
j, the sign of the weak hypothesis will be negative. This means the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses that correctly classify small-margin instances. Meanwhile, (
1
-
W
¯
t
+
j
) increases the prediction confidence of weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost performs far worse than Gentle AdaBoost.


### 2.3.4. Gentle and Margin-Pruning Boost

At each round of Gentle AdaBoost, the weights of misclassified instances are increased whereas the weights of correctly classified instances are decreased. This will lead to the phenomenon that the weights of difficult-to-classify instances are increased too large. If these instances are noise data or outliers, the performance of the final strong classifier will be degraded. To solve this problem, Margin-pruning Boost utilizes a threshold to filter instances whose weights are too large and then resets their weights to be 1.Margin-pruning Boost reduces the influence from noise-like instances effectively in the early training phase by restraining the weight increase of filtered instances [14]. However, as the number of iterations increases, the weights of instances filtered by thresholding become smaller and smaller. In the late training phase, the weights of these filtered instances are probably reduced smaller than 1. In that case, resetting their weights to be 1 actually increases the influence of these instances. Thus, the performance of Margin-pruning Boost drops when the number of loops increases.


### 2.3.5. Margin-Pruning Boost and Penalized AdaBoost

Penalized AdaBoost is an improvement of Margin-pruning Boost. First it introduces a margin feedback factor to assign higher prediction confidence to weak hypotheses that can correctly classify small-margin instances. From (13), (14), and (15), we can see that (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
) are proportional to the margins, and they are computed from the sum of margin feedback factors of misclassified instances. This means that misclassifying small-margin instances will lead to small (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
). Therefore, the prediction confidence of weak hypotheses which misclassify small-margin instances will be degraded. Compared with Gentle AdaBoost and Margin pruning Boost, Penalized AdaBoost can stand out more competent weak hypotheses. Therefore, it is more robust than the other two variants. Modest AdaBoost highlights more competent weak hypotheses in some cases but downplays these weak hypotheses in other cases. By contrast, Penalized AdaBoost attaches importance to these more competent weak hypotheses under any circumstance. Thus it is more stable than Modest AdaBoost.Furthermore, Penalized AdaBoost solves the problem of Margin-pruning Boost by utilizing a more adaptive thresholding method. Penalized AdaBoost also uses the thresholding to filter the large-weight instances similarly to Margin-pruning Boost. However, it only resets the weights of filtered instances with negative margins. This technique guarantees that the reset weights are always smaller than the original ones. For these noise-like instances, Penalized AdaBoost does not completely exclude them because they are not definitely noise. Nevertheless, Penalized AdaBoost keeps their weights small to reduce their influence on the final strong classifier. Thereby, it has better generalization ability than Margin-pruning Boost.


## 2.3.1. Real and Gentle AdaBoost

The difference between Real and Gentle AdaBoost is how they calculate their weak hypotheses. Real AdaBoost computes the weak hypothesis by minimizing the upper bound of training error in each loop [8]. Gentle AdaBoost calculates its weak hypothesis by optimizing the weighted least square error iteratively [11]. Real AdaBoost tries to decrease the training error whereas Gentle AdaBoost aims at reducing the variance of its weak hypotheses. Thus, in most cases, Real AdaBoost converges faster than Gentle AdaBoost in training, but Gentle AdaBoost is more stable than Real AdaBoost with respect to the generalization error.


## 2.3.2. Real and Parameterized AdaBoost

Comparing Step (2)(c) in Real AdaBoost with that in Parameterized AdaBoost, we find that the weight updating policies of the two variants are different. From (12), we know that the training error converges to 0 if and only if the margins of all training instances are increased to be positive. In Step (2)(c) of Real AdaBoost, instances with small margins obtain more weights so that they are more likely correctly classified in future iterations. However, as Real AdaBoost focuses on instances with small margins, it may lead to an increase of instances whose margins are near 0; that is, these instances change the sign of their margins back and forth in the boosting process. Here we call them “swinging instances.” These swinging instances slow the convergence of training error. To decrease the number of swinging instances, Parameterized AdaBoost introduces parameter α to give them larger weights. From (8), we can see that α
×
|
y
i
F
t
(
x
i
)
| reduces more weight for instances whose margins are far from 0 and less weight for swinging instances. Therefore, swinging instances obtain more attention than nonswinging ones. Parameterized AdaBoost aims at reducing the number of swinging instances by trying to correctly classify them in the early training phase. Thus, Parameterized AdaBoost can converge faster than Real AdaBoost in training. With respect to the generalization error, Parameterized AdaBoost is more prone to overfitting than Real AdaBoost especially when the CART used as weak classifiers has more inner nodes. The reason is that it focuses more on swinging instances at the cost of focusing less on instances with minimal margins. However, it can perform similarly to or slightly better than Real AdaBoost if it uses simple weak classifiers such as stump decision trees because stump trees are more resistant to overfitting than CART with many inner nodes.


## 2.3.3. Gentle and Modest AdaBoost

Modest AdaBoost utilizes an inverted weight distribution to highlight weak hypotheses that can correctly classify instances with small margins. Nevertheless, the performance of Modest AdaBoost is not stable. Here we give an example to explain the reason. We supposeW
t
+
j
>
W
t
-
j; if W
t
+
j
(
1
-
W
¯
t
+
j
) is also larger than W
t
-
j
(
1
-
W
¯
t
-
j
), the factor (
1
-
W
¯
t
+
j
) assigns higher prediction confidence to weak hypotheses that correctly classify small-margin instances. At the same time, the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost outperforms Gentle AdaBoost. However, if W
t
+
j
(
1
-
W
¯
t
+
j
) is smaller than W
t
-
j
(
1
-
W
¯
t
-
j
) in the case W
t
+
j
>
W
t
-
j, the sign of the weak hypothesis will be negative. This means the factor (
1
-
W
¯
t
-
j
) reduces the prediction confidence for weak hypotheses that correctly classify small-margin instances. Meanwhile, (
1
-
W
¯
t
+
j
) increases the prediction confidence of weak hypotheses misclassifying small-margin instances. In this case, Modest AdaBoost performs far worse than Gentle AdaBoost.


## 2.3.4. Gentle and Margin-Pruning Boost

At each round of Gentle AdaBoost, the weights of misclassified instances are increased whereas the weights of correctly classified instances are decreased. This will lead to the phenomenon that the weights of difficult-to-classify instances are increased too large. If these instances are noise data or outliers, the performance of the final strong classifier will be degraded. To solve this problem, Margin-pruning Boost utilizes a threshold to filter instances whose weights are too large and then resets their weights to be 1.Margin-pruning Boost reduces the influence from noise-like instances effectively in the early training phase by restraining the weight increase of filtered instances [14]. However, as the number of iterations increases, the weights of instances filtered by thresholding become smaller and smaller. In the late training phase, the weights of these filtered instances are probably reduced smaller than 1. In that case, resetting their weights to be 1 actually increases the influence of these instances. Thus, the performance of Margin-pruning Boost drops when the number of loops increases.


## 2.3.5. Margin-Pruning Boost and Penalized AdaBoost

Penalized AdaBoost is an improvement of Margin-pruning Boost. First it introduces a margin feedback factor to assign higher prediction confidence to weak hypotheses that can correctly classify small-margin instances. From (13), (14), and (15), we can see that (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
) are proportional to the margins, and they are computed from the sum of margin feedback factors of misclassified instances. This means that misclassifying small-margin instances will lead to small (
1
-
M
t
-
j
) and (
1
-
M
t
+
j
). Therefore, the prediction confidence of weak hypotheses which misclassify small-margin instances will be degraded. Compared with Gentle AdaBoost and Margin pruning Boost, Penalized AdaBoost can stand out more competent weak hypotheses. Therefore, it is more robust than the other two variants. Modest AdaBoost highlights more competent weak hypotheses in some cases but downplays these weak hypotheses in other cases. By contrast, Penalized AdaBoost attaches importance to these more competent weak hypotheses under any circumstance. Thus it is more stable than Modest AdaBoost.Furthermore, Penalized AdaBoost solves the problem of Margin-pruning Boost by utilizing a more adaptive thresholding method. Penalized AdaBoost also uses the thresholding to filter the large-weight instances similarly to Margin-pruning Boost. However, it only resets the weights of filtered instances with negative margins. This technique guarantees that the reset weights are always smaller than the original ones. For these noise-like instances, Penalized AdaBoost does not completely exclude them because they are not definitely noise. Nevertheless, Penalized AdaBoost keeps their weights small to reduce their influence on the final strong classifier. Thereby, it has better generalization ability than Margin-pruning Boost.


## 2.4. Margin Distribution Comparison

In this section, we compare the generalization abilities of the six different variants by analyzing their margin distributions. Li and Shen showed that reducing the minimal margin of training data plays little role in improving the generalization ability [18]. However, enlarging the whole margin distribution to obtain a balance between the training error and complexity is crucial to the generalization ability [18]. Here we use three kinds of CART as weak classifiers to evaluate the six AdaBoost variants. The three kinds of CART are CART-1 (CART with one inner node), CART-2 (CART with two inner nodes), and CART-3 (CART with three inner nodes). To get the cumulative margin distributions, for each data set, we use 2
/
3 of its data to train the final strong classifiers. Figure 2 shows the cumulative margin distributions based on CART-1 in data set German at iteration 200. Figure 3 shows the generalization errors of the same data set with respect to Figure 2. In Figure 2, Penalized AdaBoost enlarges the whole margin distribution more than the other variants so that it achieves the best generalization error in Figure 3. Real AdaBoost, Gentle AdaBoost, Parameterized AdaBoost, and Margin-pruning Boost perform similarly on the margins. So their generalization errors are also similar when the number of iterations reaches to 200. The margin curve of Modest AdaBoost in Figure 2 is not smooth. That may explain why its generalization error in Figure 3 is not changed gradually.Figure 2
Margin distributions using CART-1 at iteration 200.Figure 3
Generalization errors using CART-1.Margin distributions based on CART-2 in the same data set at iteration 200 are shown in Figure4. Figure 5 shows the generalization errors with respect to Figure 4. From Figures 4 and 5, we notice that the generalization abilities of the six variants are consistent with their performance on the margins. We also evaluate margin distributions using CART-3 on the data set German. Margin curves at iterations 10, 100, and 1000 are shown by Figures 6, 7, and 8, respectively. Comparing the three figures, we find that the margins are enlarged gradually as the number of iterations increases. Furthermore, we notice that Margin-pruning Boost outperforms Gentle AdaBoost in Figures 6 and 7. However it performs worse than Gentle AdaBoost in Figure 8. This demonstrates that the performance of Margin-pruning Boost drops as the number of iterations increases. Differently from Margin-pruning Boost, Penalized AdaBoost outperforms others at most cases. Thus it is most robust and stable. Figure 9 shows the generalization errors of the six variants which use CART-3 as their weak classifiers. In Figure 9, Margin-pruning Boost obtains lower generalization errors than Gentle AdaBoost before iteration 500. Unfortunately, it leads to severe overfitting after iteration 500.Figure 4
Margin distributions using CART-2 at iteration 200.Figure 5
Generalization errors using CART-2.Figure 6
Margin distributions using CART-3 at iteration 10.Figure 7
Margin distributions using CART-3 at iteration 100.Figure 8
Margin distributions using CART-3 at iteration 1000.Figure 9
Generalization errors using CART-3.Figures10 and 11 show margin distributions of other data sets. From these margin curves, we can conclude that Penalized AdaBoost generally outperforms the other five variants on enlarging the whole margin distributions. Real and Gentle AdaBoost perform very similarly, and Parameterized AdaBoost is slightly worse than Real AdaBoost when it uses CART-2 and CART-3. Margin-pruning Boost is better than Gentle AdaBoost if the number of iterations is small, While the margin curves of Modest AdaBoost are not smooth, they may lead to an unstable performance on generalization errors.Margin distributions at iteration 200.
(a)
(b)Margin distributions at iteration 200.
(a)
(b)


## 3. Experiments

In this section, we compare the six AdaBoost variants using 25 binary classification data sets from UCI [55]. For every data set, we used Matlab AdaBoost Toolbox [54] and 3-fold cross validation. First we measure the generalization errors (estimated by the classification error on the test set) of the six variants based on CART-1. Table 1 summarizes the results of the six variants using CART-1 at iteration 200. Tables 2 and 3 show their generalization errors using CART-1 at iterations 500 and 800, respectively. We also compare the generalization errors of the six variants based on CART-2 and CART-3. Table 4 shows the comparison results using CART-2, and Table 5 compares the six variants using CART-3.Table 1
Test results at iteration 200 using CART-1.
Data sets: 25
RAB
GAB
MAB
PAAB
MPB
PAB
Australian
0.1536
0.1435
0.1435
0.1449
0.1391
0.1304
Blood  Transfusion
0.2392
0.2312
0.2352
0.2392
0.2218
0.2298
Banana
0.2732
0.2713
0.2804
0.2672
0.2526
0.2809
Banknote
0.0029
0.0022
0.0372
0.0015
0.0058
0.0080
Breast Cancer
0.0281
0.0246
0.0422
0.0299
0.0669
0.0281
Climate model
0.0704
0.0593
0.0963
0.0759
0.0704
0.0630
Gamma Telescope
0.1525
0.1546
0.2297
0.1489
0.1454
0.1548
German
0.2560
0.2580
0.2950
0.2490
0.2470
0.2450
Heart Disease
0.2259
0.2333
0.1704
0.2185
0.2000
0.1630
Hepatitis
0.2200
0.2130
0.2515
0.2065
0.2129
0.1869
Indian Diabetes
0.2448
0.2578
0.2383
0.2539
0.2318
0.2253
Indian Liver
0.3074
0.3005
0.3230
0.3092
0.2850
0.3126
Image Segment
0.0061
0.0045
0.0076
0.0061
0.0106
0.0061
Parkinson’s
0.0872
0.0872
0.1692
0.0923
0.0974
0.0923
Planning Relax
0.4286
0.4012
0.3519
0.4448
0.4175
0.3186
Ring Norm
0.0269
0.0268
0.0470
0.0293
0.0277
0.0509
Sonar
0.1445
0.1589
0.1637
0.1540
0.2117
0.1734
Spambase
0.0580
0.0546
0.0895
0.0554
0.0528
0.0617
SPECTF Heart
0.2097
0.2285
0.2472
0.2172
0.2584
0.1985
Splice
0.0675
0.0675
0.0919
0.0685
0.0612
0.0639
Steel Plates
0.2277
0.2324
0.2751
0.2344
0.2318
0.2421
Twonorm
0.0303
0.0305
0.0315
0.0324
0.0292
0.0304
Waveform
0.0993
0.0975
0.0962
0.0996
0.0917
0.0853
WBPC
0.2475
0.2727
0.3030
0.2879
0.3081
0.2323
Wine Quality
0.0055
0.0054
0.0240
0.0062
0.0052
0.0054
Sum
3.8128
3.8170
4.2405
3.8727
3.8820
3.5887
VS.GAB
−0.0042
0.0000
0.4235
0.0557
0.0650
−0.2283
No.Best
3
5
0
1
8
9
No.To.GAB
11
—
5
9
15
13Table 2
Test results at iteration 500 using CART-1.
Data sets: 25
RAB
GAB
MAB
PAAB
MPB
PAB
Australian
0.1681
0.1638
0.1435
0.1638
0.1377
0.1333
Blood  Transfusion
0.2446
0.2540
0.2352
0.2500
0.2272
0.2258
Banana
0.2734
0.2725
0.2804
0.2662
0.2547
0.2738
Banknote
0.0029
0.0036
0.0372
0.0022
0.0058
0.0058
Breast Cancer
0.0281
0.0246
0.0369
0.0264
0.0756
0.0246
Climate Model
0.0704
0.0648
0.0963
0.0741
0.0722
0.0593
Gamma Telescope
0.1522
0.1519
0.2292
0.1479
0.1424
0.1473
German
0.2700
0.2730
0.2950
0.2710
0.2490
0.2430
Heart Disease
0.2481
0.2481
0.1704
0.2333
0.2000
0.1852
Hepatitis
0.2262
0.2130
0.2515
0.2132
0.2129
0.2128
Indian Diabetes
0.2487
0.2526
0.2383
0.2565
0.2409
0.2266
Indian Liver
0.3005
0.3074
0.3558
0.2971
0.2953
0.3057
Image Segment
0.0045
0.0045
0.0045
0.0030
0.0061
0.0030
Parkinson’s
0.0821
0.0974
0.1641
0.0923
0.0974
0.0872
Planning Relax
0.4342
0.4397
0.3519
0.4064
0.4175
0.3462
Ring Norm
0.0264
0.0249
0.0309
0.0280
0.0251
0.0318
Sonar
0.1446
0.1638
0.1589
0.1684
0.2548
0.1734
Spambase
0.0593
0.0574
0.0895
0.0578
0.0517
0.0572
SPECTF Heart
0.2097
0.2285
0.2584
0.2060
0.2772
0.2022
Splice
0.0726
0.0746
0.0919
0.0752
0.0622
0.0605
Steel Plates
0.2318
0.2293
0.2777
0.2339
0.2267
0.2334
Twonorm
0.0291
0.0296
0.0286
0.0326
0.0296
0.0276
Waveform
0.0990
0.0984
0.0962
0.1038
0.0950
0.0881
WBPC
0.2475
0.2828
0.3030
0.2424
0.3081
0.2374
Wine Quality
0.0060
0.0054
0.0231
0.0054
0.0060
0.0051
Sum
3.8800
3.9656
4.2484
3.8569
3.9711
3.5963
VS.GAB
−0.0856
0.0000
0.2828
−0.1087
0.0055
−0.3693
No.Best
2
2
1
2
5
15
No.To.GAB
14
—
9
14
16
20Table 3
Test results at iteration 800 using CART-1.
Data sets: 25
RAB
GAB
MAB
PAAB
MPB
PAB
Australian
0.1754
0.1696
0.1435
0.1899
0.1362
0.1348
Blood  Transfusion
0.2487
0.2473
0.2379
0.2527
0.2272
0.2218
Banana
0.2740
0.2753
0.2804
0.2687
0.2530
0.2709
Banknote
0.0036
0.0044
0.0372
0.0022
0.0058
0.0036
Breast Cancer
0.0246
0.0281
0.0369
0.0246
0.0774
0.0246
Climate Model
0.0759
0.0685
0.0963
0.0722
0.0722
0.0611
Gamma Telescope
0.1530
0.1531
0.2290
0.1485
0.1425
0.1448
German
0.2800
0.2770
0.2950
0.2780
0.2550
0.2430
Heart Disease
0.2519
0.2333
0.1704
0.2519
0.2000
0.2111
Hepatitis
0.2197
0.2195
0.2646
0.2068
0.2129
0.2000
Indian Diabetes
0.2513
0.2513
0.2396
0.2591
0.2396
0.2305
Indian Liver
0.2971
0.3005
0.3592
0.2988
0.3022
0.2936
Image Segment
0.0045
0.0045
0.0045
0.0030
0.0061
0.0030
Parkinson’s
0.0872
0.1026
0.1641
0.0821
0.0974
0.0923
Planning Relax
0.4669
0.4287
0.3519
0.4230
0.4175
0.3737
Ring Norm
0.0258
0.0235
0.0273
0.0288
0.0262
0.0288
Sonar
0.1493
0.1542
0.1638
0.1732
0.2500
0.1685
Spambase
0.0593
0.0563
0.0880
0.0572
0.0517
0.0561
SPECTF Heart
0.2172
0.2247
0.2697
0.2060
0.2734
0.2135
Splice
0.0766
0.0772
0.0919
0.0772
0.0642
0.0598
Steel Plates
0.2303
0.2303
0.2736
0.2349
0.2262
0.2318
Twonorm
0.0301
0.0300
0.0286
0.0315
0.0309
0.0269
Waveform
0.0987
0.0981
0.0962
0.1065
0.0956
0.0902
WBPC
0.2424
0.2828
0.2980
0.2475
0.3081
0.2273
Wine Quality
0.0057
0.0058
0.0235
0.0055
0.0072
0.0046
Sum
3.9492
3.9466
4.2711
3.9298
3.9785
3.6163
VS.GAB
0.0026
0.0000
0.3245
−0.0168
0.0319
−0.3303
No.Best
2
1
2
5
4
14
No.To.GAB
14
—
8
13
14
22Table 4
Test results at iteration 200 using CART-2.
Data sets: 25
RAB
GAB
MAB
PAAB
MPB
PAB
Australian
0.1449
0.1478
0.1420
0.1580
0.1420
0.1246
Blood  Transfusion
0.2581
0.2540
0.2366
0.2608
0.2419
0.2204
Banana
0.1021
0.1002
0.2430
0.1006
0.1045
0.1479
Banknote
0.0051
0.0022
0.0058
0.0022
0.0044
0.0029
Breast Cancer
0.0264
0.0229
0.0387
0.0299
0.0316
0.0246
Climate Model
0.0574
0.0574
0.0944
0.0593
0.1019
0.0519
Gamma Telescope
0.1301
0.1317
0.2006
0.1295
0.1320
0.1426
German
0.2710
0.2690
0.2890
0.2850
0.2580
0.2380
Heart Disease
0.2667
0.2000
0.2074
0.2556
0.2889
0.2037
Hepatitis
0.1934
0.2001
0.2320
0.1675
0.2709
0.1934
Indian Diabetes
0.2591
0.2682
0.2357
0.2839
0.2500
0.2370
Indian Liver
0.2953
0.2815
0.3592
0.3005
0.2694
0.3057
Image Segment
0.0091
0.0061
0.0045
0.0045
0.0091
0.0045
Parkinson’s
0.0667
0.0564
0.1385
0.0667
0.0974
0.0769
Planning Relax
0.4117
0.3791
0.3352
0.3731
0.4392
0.3573
Ring Norm
0.0288
0.0284
0.0312
0.0311
0.0276
0.0343
Sonar
0.1396
0.1397
0.1493
0.1443
0.1395
0.1491
Spambase
0.0511
0.0506
0.0798
0.0550
0.0476
0.0546
SPECTF Heart
0.2060
0.2135
0.2472
0.2060
0.2434
0.2135
Splice
0.0431
0.0408
0.0368
0.0481
0.0408
0.0381
Steel Plates
0.2102
0.2020
0.2694
0.2184
0.1999
0.2123
Twonorm
0.0300
0.0303
0.0297
0.0342
0.0288
0.0270
Waveform
0.0908
0.1008
0.0920
0.1032
0.0935
0.0860
WBPC
0.2424
0.2424
0.3030
0.2374
0.2525
0.2222
Wine Quality
0.0051
0.0038
0.0149
0.0042
0.0060
0.0045
Sum
3.5442
3.4289
4.0159
3.5590
3.7208
3.3730
VS.GAB
0.1153
0.0000
0.5870
0.1301
0.2919
−0.0559
No.Best
1
6
4
5
5
8
No.To.GAB
10
—
8
7
12
13Table 5
Test results at iteration 200 using CART-3.
Data sets: 25
RAB
GAB
MAB
PAAB
MPB
PAB
Australian
0.1478
0.1536
0.1333
0.1594
0.1522
0.1203
Blood  Transfusion
0.2863
0.2715
0.2392
0.2984
0.2527
0.2245
Banana
0.1040
0.1028
0.2142
0.1047
0.1002
0.1132
Banknote
0.0036
0.0022
0.0029
0.0015
0.0051
0.0022
Breast Cancer
0.0334
0.0281
0.0246
0.0281
0.0281
0.0281
Climate Model
0.0611
0.0519
0.0944
0.0593
0.0722
0.0500
Gamma Telescope
0.1300
0.1305
0.1770
0.1316
0.1278
0.1360
German
0.2870
0.2660
0.2780
0.2920
0.2750
0.2440
Heart Disease
0.2074
0.2185
0.2074
0.2074
0.2593
0.2000
Hepatitis
0.1932
0.1933
0.2252
0.1998
0.1934
0.2127
Indian Diabetes
0.2513
0.2552
0.2357
0.2695
0.2643
0.2344
Indian Liver
0.2781
0.2781
0.3437
0.3092
0.2867
0.2971
Image Segment
0.0015
0.0015
0.0030
0.0030
0.0061
0.0030
Parkinson’s
0.0718
0.0615
0.1026
0.0821
0.0769
0.0769
Planning Relax
0.3514
0.3844
0.3518
0.3459
0.3899
0.3682
Ring Norm
0.0277
0.0266
0.0296
0.0295
0.0296
0.0309
Sonar
0.1202
0.1395
0.1637
0.1636
0.1347
0.1349
Spambase
0.0528
0.0454
0.0728
0.0519
0.0476
0.0500
SPECTF Heart
0.2210
0.2022
0.2472
0.1948
0.2285
0.1948
Splice
0.0321
0.0361
0.0294
0.0428
0.0428
0.0308
Steel Plates
0.2030
0.2020
0.2653
0.2138
0.2035
0.1999
Twonorm
0.0319
0.0301
0.0288
0.0299
0.0304
0.0265
Waveform
0.1029
0.0972
0.0890
0.1053
0.1038
0.0872
WBPC
0.2323
0.2172
0.3030
0.2525
0.2273
0.2172
Wine Quality
0.0051
0.0038
0.0125
0.0048
0.0042
0.0038
Sum
3.4369
3.3992
3.8743
3.5808
3.5423
3.2866
VS.GAB
0.0377
0.0000
0.4751
0.1816
0.1431
−0.1126
No.Best
4
7
2
3
2
12
No.To.GAB
10
—
9
6
6
17In Tables1, 2, 3, 4, and 5, RAB, GAB, MAB, PAAB, MPB, and PAB denote Real AdaBoost, Gentle AdaBoost, Modest AdaBoost, Parameterized AdaBoost, Margin-pruning Boost, and Penalized AdaBoost separately. The row of VS.GAB shows the residues that the sum of generalization errors of other variants subtracts that of Gentle AdaBoost. Here the bold values show the best performance and No.Best means the number of best generalization errors. No.To.GAB denotes the number of data sets in which Gentle AdaBoost is outperformed by others. From Tables 1, 2, and 3, we can conclude that Real, Gentle, and Parameterized AdaBoost perform similarly when using CART-1 as weak classifiers. Modest AdaBoost performs worse than other variants at most cases. Moreover, its error rates are rarely changed even when the number of loops increases. Comparing No.Best of Margin-pruning Boost in Tables 1, 2, and 3, we find that its performance drops as the number of iterations increases. We can also see that Penalized AdaBoost generally outperforms other variants from VS.GAB, No.Best, and No.To.GAB in Tables 1, 2, and 3. Comparing Tables 1, 4, and 5, we can conclude that increasing the inner nodes of CART is important to reduce the generalization errors. In Tables 4 and 5, we can see that Gentle AdaBoost is slightly better than Real AdaBoost. However, the performance of Parameterized AdaBoost and Margin-pruning Boost drops sharply. This means the two variants are more suitable for CART-1. On the other hand, Modest AdaBoost using CART-2 or CART-3 performs better than that using CART-1. This suggests that Modest AdaBoost is suitable for CART with more inner nodes. From all tables, we notice that the performance of Gentle and Penalized AdaBoost is not degraded neither by the number of inner nodes in CART nor by the number of iterations. Nevertheless, Penalized AdaBoost shows stronger robustness when compared with Gentle AdaBoost.


## 4. Conclusion

This paper analyzes the generalization abilities of six AdaBoost variants mathematically. The novel contributions of our work are listed as follows.(1)
There are many comparison studies of AdaBoost variants. However, we compare three new proposed variants (Parameterized AdaBoost, Margin-pruning Boost, and Penalized AdaBoost) with three traditional variants (Real, Gentle, and Modest AdaBoost). This kind of comparison is new in the machine learning studies.
(2)
Differently from conventional comparison works that draw conclusion from experimental results, we analyze the generalization abilities of the six variants by comparing their classification margins.
(3)
We design experiments to verify our analyses. The experimental results are consistent with our analyses.In general, the analyses and comparison in this paper are useful for researchers who want to improve the classification performance by switching to a new AdaBoost variant. In our current research, we focus on two classification problems. In our future work, we want to extend our analyses to multiclassification problems. In addition, we will compare more kinds of weak classifiers such as SVM and ANN to find out which kind of weak classifiers is suitable for which AdaBoost variant.



---

*Source: 835357-2015-02-10.xml*