Bagging思想的实质是：通过Bootstrap 的方式对全样本数据集进行抽样得到抽样子集，对不同的子集使用同一种基本模型进行拟合，然后投票得出最终的预测。我们也从前面的探讨知道：Bagging主要通过降低方差的方式减少预测误差。那么，本章介绍的Boosting是与Bagging截然不同的思想，Boosting方法是使用同一组数据集进行反复学习，得到一系列简单模型，然后组合这些模型构成一个预测性能十分强大的机器学习模型。显然，Boosting思想提高最终的预测效果是通过不断减少偏差的形式，与Bagging有着本质的不同。
在Boosting这一大类方法中，笔者主要介绍两类常用的Boosting方式：Adaptive Boosting 和 Gradient Boosting 以及它们的变体Xgboost、LightGBM以及Catboost。
boosting
举例说明，对于一个复杂任务来说，将多个专家的判断进行适当的综合所作出的判断，要比其中任何一个专家单独判断要好。实际上这是一种“三个臭皮匠顶个诸葛亮的道理”。
弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
强学习：识别准确率很高并能在多项式时间内完成的学习算法
Adaboost算法
对于Adaboost来说，解决上述的两个问题的方式是：
- 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。
- 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。
Adaboost算法：(参考李航老师的《统计学习方法》)
假设给定一个二分类的训练数据集：
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}，其中每个样本点由特征与类别组成。特征
x
i
∈
X
?
R
n
x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}
xi?∈X?Rn，类别
y
i
∈
Y
=
{
?
1
,
+
1
}
y_{i} \in \mathcal{Y}=\{-1,+1\}
yi?∈Y={?1,+1}，
X
\mathcal{X}
X是特征空间，
Y
\mathcal{Y}
Y是类别集合，输出最终分类器
G
(
x
)
G(x)
G(x)。Adaboost算法如下：
(1). 初始化训练数据的分布：
D
1
=
(
w
11
,
?
?
,
w
1
i
,
?
?
,
w
1
N
)
,
w
1
i
=
1
N
,
i
=
1
,
2
,
?
?
,
N
D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N
D1?=(w11?,?,w1i?,?,w1N?),w1i?=N1?,i=1,2,?,N
(2) 对于m=1,2,…,M
- 使用具有权值分布 D m D_m Dm?的训练数据集进行学习，得到基本分类器： G m ( x ) : X → { ? 1 , + 1 } G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\} Gm?(x):X→{?1,+1}
- 计算 G m ( x ) G_m(x) Gm?(x)在训练集上的分类误差率 e m = ∑ i = 1 N P ( G m ( x i ) ≠ y i ) = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) em?=∑i=1N?P(Gm?(xi?)?=yi?)=∑i=1N?wmi?I(Gm?(xi?)?=yi?)
- 计算 G m ( x ) G_m(x) Gm?(x)的系数 α m = 1 2 log ? 1 ? e m e m \alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}} αm?=21?logem?1?em??，这里的log是自然对数ln
- 更新训练数据集的权重分布
D m + 1 = ( w m + 1 , 1 , ? ? , w m + 1 , i , ? ? , w m + 1 , N ) w m + 1 , i = w m i Z m exp ? ( ? α m y i G m ( x i ) ) , i = 1 , 2 , ? ? , N \begin{array}{c} D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \\ w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N \end{array} Dm+1?=(wm+1,1?,?,wm+1,i?,?,wm+1,N?)wm+1,i?=Zm?wmi??exp(?αm?yi?Gm?(xi?)),i=1,2,?,N? 这里的 Z m Z_m Zm?是规范化因子，使得 D m + 1 D_{m+1} Dm+1?称为概率分布， Z m = ∑ i = 1 N w m i exp ? ( ? α m y i G m ( x i ) ) Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right) Zm?=∑i=1N?wmi?exp(?αm?yi?Gm?(xi?)) 也就是所有数的总和。
(3) 构建基本分类器的线性组合
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)
f(x)=∑m=1M?αm?Gm?(x)，得到最终的分类器
G
(
x
)
=
sign
?
(
f
(
x
)
)
=
sign
?
(
∑
m
=
1
M
α
m
G
m
(
x
)
)
\begin{aligned} G(x) &=\operatorname{sign}(f(x)) \\ &=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right) \end{aligned}
G(x)?=sign(f(x))=sign(m=1∑M?αm?Gm?(x))?
下面对Adaboost算法做如下说明：
对于步骤(1)，假设训练数据的权值分布是均匀分布，是为了使得第一次没有先验信息的条件下每个样本在基本分类器的学习中作用一样。
对于步骤(2)，每一次迭代产生的基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)在加权训练数据集上的分类错误率
e
m
=
∑
i
=
1
N
P
(
G
m
(
x
i
)
≠
y
i
)
=
∑
G
m
(
x
i
)
≠
y
i
w
m
i
\begin{aligned}e_{m} &=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) =\sum_{G_{m}\left(x_{i}\right) \neq y_{i}} w_{m i}\end{aligned}
em??=i=1∑N?P(Gm?(xi?)?=yi?)=Gm?(xi?)?=yi?∑?wmi??代表了在
G
m
(
x
)
G_m(x)
Gm?(x)中分类错误的样本权重和，这点直接说明了权重分布
D
m
D_m
Dm?与
G
m
(
x
)
G_m(x)
Gm?(x)的分类错误率
e
m
e_m
em?有直接关系。同时，在步骤(2)中，计算基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的系数
α
m
\alpha_m
αm?，
α
m
=
1
2
log
?
1
?
e
m
e
m
\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}
αm?=21?logem?1?em??，它表示了
G
m
(
x
)
G_m(x)
Gm?(x)在最终分类器的重要性程度，
α
m
\alpha_m
αm?的取值由基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的分类错误率有直接关系，当
e
m
?
1
2
e_{m} \leqslant \frac{1}{2}
em??21?时，
α
m
?
0
\alpha_{m} \geqslant 0
αm??0，并且
α
m
\alpha_m
αm?随着
e
m
e_m
em?的减少而增大，因此分类错误率越小的基本分类器在最终分类器的作用越大！
最重要的，对于步骤(2)中的样本权重的更新：
w
m
+
1
,
i
=
{
w
m
i
Z
m
e
?
α
m
,
G
m
(
x
i
)
=
y
i
w
m
i
Z
m
e
α
m
,
G
m
(
x
i
)
≠
y
i
w_{m+1, i}=\left\{\begin{array}{ll} \frac{w_{m i}}{Z_{m}} \mathrm{e}^{-\alpha_{m}}, & G_{m}\left(x_{i}\right)=y_{i} \\ \frac{w_{m i}}{Z_{m}} \mathrm{e}^{\alpha_{m}}, & G_{m}\left(x_{i}\right) \neq y_{i} \end{array}\right.
wm+1,i?={Zm?wmi??e?αm?,Zm?wmi??eαm?,?Gm?(xi?)=yi?Gm?(xi?)?=yi?? 因此，从上式可以看到：被基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)错误分类的样本的权重扩大，被正确分类的样本权重减少，二者相比相差
e
2
α
m
=
1
?
e
m
e
m
\mathrm{e}^{2 \alpha_{m}}=\frac{1-e_{m}}{e_{m}}
e2αm?=em?1?em??倍。
对于步骤(3)，线性组合
f
(
x
)
f(x)
f(x)实现了将M个基本分类器的加权表决，系数
α
m
\alpha_m
αm?标志了基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的重要性，值得注意的是：所有的
α
m
\alpha_m
αm?之和不为1。
f
(
x
)
f(x)
f(x)的符号决定了样本x属于哪一类。
例子
下面，我们使用一组简单的数据来手动计算Adaboost算法的过程：(例子来源：http://www.csie.edu.tw)
训练数据如下表，假设基本分类器的形式是一个分割
x
<
v
x<v
x<v或
x
>
v
x>v
x>v表示，阈值v由该基本分类器在训练数据集上分类错误率
e
m
e_m
em?最低确定。
?序号?
1
2
3
4
5
6
7
8
9
10
x
0
1
2
3
4
5
6
7
8
9
y
1
1
1
?
1
?
1
?
1
1
1
1
?
1
\begin{array}{ccccccccccc} \hline \text { 序号 } & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ y & 1 & 1 & 1 & -1 & -1 & -1 & 1 & 1 & 1 & -1 \\ \hline \end{array}
?序号?xy?101?211?321?43?1?54?1?65?1?761?871?981?109?1??
解：
初始化样本权值分布
D
1
=
(
w
11
,
w
12
,
?
?
,
w
110
)
w
1
i
=
0.1
,
i
=
1
,
2
,
?
?
,
10
\begin{aligned} D_{1} &=\left(w_{11}, w_{12}, \cdots, w_{110}\right) \\ w_{1 i} &=0.1, \quad i=1,2, \cdots, 10 \end{aligned}
D1?w1i??=(w11?,w12?,?,w110?)=0.1,i=1,2,?,10?
对m=1:
- 在权值分布
D
1
D_1
D1?的训练数据集上，遍历每个结点并计算分类误差率
e
m
e_m
em?，阈值取v=2.5时分类误差率最低，那么基本分类器为：
G 1 ( x ) = { 1 , x < 2.5 ? 1 , x > 2.5 G_{1}(x)=\left\{\begin{array}{ll} 1, & x<2.5 \\ -1, & x>2.5 \end{array}\right. G1?(x)={1,?1,?x<2.5x>2.5? - G 1 ( x ) G_1(x) G1?(x)在训练数据集上的误差率为 e 1 = P ( G 1 ( x i ) ≠ y i ) = 0.3 e_{1}=P\left(G_{1}\left(x_{i}\right) \neq y_{i}\right)=0.3 e1?=P(G1?(xi?)?=yi?)=0.3。
- 计算 G 1 ( x ) G_1(x) G1?(x)的系数： α 1 = 1 2 log ? 1 ? e 1 e 1 = 0.4236 \alpha_{1}=\frac{1}{2} \log \frac{1-e_{1}}{e_{1}}=0.4236 α1?=21?loge1?1?e1??=0.4236
- 更新训练数据的权值分布：
D 2 = ( w 21 , ? ? , w 2 i , ? ? , w 210 ) w 2 i = w 1 i Z 1 exp ? ( ? α 1 y i G 1 ( x i ) ) , i = 1 , 2 , ? ? , 10 D 2 = ( 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.07143 , 0.16667 , 0.16667 , 0.16667 , 0.07143 ) f 1 ( x ) = 0.4236 G 1 ( x ) \begin{aligned} D_{2}=&\left(w_{21}, \cdots, w_{2 i}, \cdots, w_{210}\right) \\ w_{2 i}=& \frac{w_{1 i}}{Z_{1}} \exp \left(-\alpha_{1} y_{i} G_{1}\left(x_{i}\right)\right), \quad i=1,2, \cdots, 10 \\ D_{2}=&(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,\\ &0.16667,0.16667,0.16667,0.07143) \\ f_{1}(x) &=0.4236 G_{1}(x) \end{aligned} D2?=w2i?=D2?=f1?(x)?(w21?,?,w2i?,?,w210?)Z1?w1i??exp(?α1?yi?G1?(xi?)),i=1,2,?,10(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)=0.4236G1?(x)?
对于m=2：
- 在权值分布
D
2
D_2
D2?的训练数据集上，遍历每个结点并计算分类误差率
e
m
e_m
em?，阈值取v=8.5时分类误差率最低，那么基本分类器为：
G 2 ( x ) = { 1 , x < 8.5 ? 1 , x > 8.5 G_{2}(x)=\left\{\begin{array}{ll} 1, & x<8.5 \\ -1, & x>8.5 \end{array}\right. G2?(x)={1,?1,?x<8.5x>8.5? - G 2 ( x ) G_2(x) G2?(x)在训练数据集上的误差率为 e 2 = 0.2143 e_2 = 0.2143 e2?=0.2143
- 计算 G 2 ( x ) G_2(x) G2?(x)的系数： α 2 = 0.6496 \alpha_2 = 0.6496 α2?=0.6496
- 更新训练数据的权值分布：
D 3 = ( 0.0455 , 0.0455 , 0.0455 , 0.1667 , 0.1667 , 0.1667 0.1060 , 0.1060 , 0.1060 , 0.0455 ) f 2 ( x ) = 0.4236 G 1 ( x ) + 0.6496 G 2 ( x ) \begin{aligned} D_{3}=&(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667\\ &0.1060,0.1060,0.1060,0.0455) \\ f_{2}(x) &=0.4236 G_{1}(x)+0.6496 G_{2}(x) \end{aligned} D3?=f2?(x)?(0.0455,0.0455,0.0455,0.1667,0.1667,0.16670.1060,0.1060,0.1060,0.0455)=0.4236G1?(x)+0.6496G2?(x)?
对m=3：
- 在权值分布
D
3
D_3
D3?的训练数据集上，遍历每个结点并计算分类误差率
e
m
e_m
em?，阈值取v=5.5时分类误差率最低，那么基本分类器为：
G 3 ( x ) = { 1 , x > 5.5 ? 1 , x < 5.5 G_{3}(x)=\left\{\begin{array}{ll} 1, & x>5.5 \\ -1, & x<5.5 \end{array}\right. G3?(x)={1,?1,?x>5.5x<5.5? - G 3 ( x ) G_3(x) G3?(x)在训练数据集上的误差率为 e 3 = 0.1820 e_3 = 0.1820 e3?=0.1820
- 计算 G 3 ( x ) G_3(x) G3?(x)的系数： α 3 = 0.7514 \alpha_3 = 0.7514 α3?=0.7514
- 更新训练数据的权值分布：
D 4 = ( 0.125 , 0.125 , 0.125 , 0.102 , 0.102 , 0.102 , 0.065 , 0.065 , 0.065 , 0.125 ) D_{4}=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125) D4?=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
于是得到：
f
3
(
x
)
=
0.4236
G
1
(
x
)
+
0.6496
G
2
(
x
)
+
0.7514
G
3
(
x
)
f_{3}(x)=0.4236 G_{1}(x)+0.6496 G_{2}(x)+0.7514 G_{3}(x)
f3?(x)=0.4236G1?(x)+0.6496G2?(x)+0.7514G3?(x)，分类器
sign
?
[
f
3
(
x
)
]
\operatorname{sign}\left[f_{3}(x)\right]
sign[f3?(x)]在训练数据集上的误分类点的个数为0。
于是得到最终分类器为：
G
(
x
)
=
sign
?
[
f
3
(
x
)
]
=
sign
?
[
0.4236
G
1
(
x
)
+
0.6496
G
2
(
x
)
+
0.7514
G
3
(
x
)
]
G(x)=\operatorname{sign}\left[f_{3}(x)\right]=\operatorname{sign}\left[0.4236 G_{1}(x)+0.6496 G_{2}(x)+0.7514 G_{3}(x)\right]
G(x)=sign[f3?(x)]=sign[0.4236G1?(x)+0.6496G2?(x)+0.7514G3?(x)]
越复杂的模型偏差越小，方差越大。
----偏差方差理论
从上面的决策边界图可以看到：Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。也就是说，Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差，但是过程中引入了方差，可能出现过拟合，因此在训练集和测试集之间的性能存在较大的差距，这就简单地回答的刚刚问题。值的注意的是：与单个分类器相比，Adaboost等Boosting模型增加了计算的复杂度，在实践中需要仔细思考是否愿意为预测性能的相对改善而增加计算成本，而且Boosting方式无法做到现在流行的并行计算的方式进行训练，因为每一步迭代都要基于上一部的基本分类器。
前向分步算法
回看Adaboost的算法内容，我们需要通过计算M个基本分类器，每个分类器的错误率、样本权重以及模型权重。我们可以认为：Adaboost每次学习单一分类器以及单一分类器的参数(权重)。接下来，我们抽象出Adaboost算法的整体框架逻辑，构建集成学习的一个非常重要的框架----前向分步算法，有了这个框架，我们不仅可以解决分类问题，也可以解决回归问题。
(1) 加法模型：
在Adaboost模型中，我们把每个基本分类器合成一个复杂分类器的方法是每个基本分类器的加权和，即：
f
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)
f(x)=∑m=1M?βm?b(x;γm?)，其中，
b
(
x
;
γ
m
)
b\left(x ; \gamma_{m}\right)
b(x;γm?)为即基本分类器，
γ
m
\gamma_{m}
γm?为基本分类器的参数，
β
m
\beta_m
βm?为基本分类器的权重，显然这与第二章所学的加法模型。为什么这么说呢？大家把
b
(
x
;
γ
m
)
b(x ; \gamma_{m})
b(x;γm?)看成是即函数即可。
在给定训练数据以及损失函数
L
(
y
,
f
(
x
)
)
L(y, f(x))
L(y,f(x))的条件下，学习加法模型
f
(
x
)
f(x)
f(x)就是：
min
?
β
m
,
γ
m
∑
i
=
1
N
L
(
y
i
,
∑
m
=
1
M
β
m
b
(
x
i
;
γ
m
)
)
\min _{\beta_{m}, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right)
βm?,γm?min?i=1∑N?L(yi?,m=1∑M?βm?b(xi?;γm?))
通常这是一个复杂的优化问题，很难通过简单的凸优化的相关知识进行解决。前向分步算法可以用来求解这种方式的问题，它的基本思路是：因为学习的是加法模型，如果从前向后，每一步只优化一个基函数及其系数，逐步逼近目标函数，那么就可以降低优化的复杂度。具体而言，每一步只需要优化：
min
?
β
,
γ
∑
i
=
1
N
L
(
y
i
,
β
b
(
x
i
;
γ
)
)
\min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)
β,γmin?i=1∑N?L(yi?,βb(xi?;γ))
(2) 前向分步算法：
给定数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}，
x
i
∈
X
?
R
n
x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}
xi?∈X?Rn，
y
i
∈
Y
=
{
+
1
,
?
1
}
y_{i} \in \mathcal{Y}=\{+1,-1\}
yi?∈Y={+1,?1}。损失函数
L
(
y
,
f
(
x
)
)
L(y, f(x))
L(y,f(x))，基函数集合
{
b
(
x
;
γ
)
}
\{b(x ; \gamma)\}
{b(x;γ)}，我们需要输出加法模型
f
(
x
)
f(x)
f(x)。
- 初始化： f 0 ( x ) = 0 f_{0}(x)=0 f0?(x)=0
- 对m = 1,2,…,M:
- (a) 极小化损失函数：
( β m , γ m ) = arg ? min ? β , γ ∑ i = 1 N L ( y i , f m ? 1 ( x i ) + β b ( x i ; γ ) ) \left(\beta_{m}, \gamma_{m}\right)=\arg \min _{\beta, \gamma} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right) (βm?,γm?)=argβ,γmin?i=1∑N?L(yi?,fm?1?(xi?)+βb(xi?;γ))
得到参数 β m \beta_{m} βm?与 γ m \gamma_{m} γm? - (b) 更新：
f m ( x ) = f m ? 1 ( x ) + β m b ( x ; γ m ) f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right) fm?(x)=fm?1?(x)+βm?b(x;γm?)
- (a) 极小化损失函数：
- 得到加法模型：
f ( x ) = f M ( x ) = ∑ m = 1 M β m b ( x ; γ m ) f(x)=f_{M}(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right) f(x)=fM?(x)=m=1∑M?βm?b(x;γm?) 这样，前向分步算法将同时求解从m=1到M的所有参数 β m \beta_{m} βm?， γ m \gamma_{m} γm?的优化问题简化为逐次求解各个 β m \beta_{m} βm?， γ m \gamma_{m} γm?的问题。
(3) 前向分步算法与Adaboost的关系：
由于这里不是我们的重点，我们主要阐述这里的结论，不做相关证明，具体的证明见李航老师的《统计学习方法》第八章的3.2节。Adaboost算法是前向分步算法的特例，Adaboost算法是由基本分类器组成的加法模型，损失函数为指数损失函数。