根据基学习器的生成方式，目前集成学习方法主流分成两大类，即Boosting 和 Bagging。Boosting集成是每个基学习器存在强依赖关系，必须串行生成，目前比较有代表性的工业界框架有AdaBoost、GBDT、XGBoost 和 LightGBM，其中后三者工业界比较常用；Bagging集成是每个基学习器间不需要存在依赖关系、可并行化，其中比较具有代表性的是随机森林（即 Random Forest）。
这篇笔记主要记录集成学习Boosting的思想，关于Bagging的思想可参考上一篇笔记。这篇笔记首先记录Boosting的基本思路；其次详细记录经典且具有代表性的提升算法AdaBoost；然后记录基分类器为决策树的boosting集成树模型（boosting tree）；最后记录一种特殊的boosting集成方法即梯度提升（gradient boosting）。
Boosting方法的基本思路
Boosting方法基于的思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好，就是“三个臭皮匠顶个诸葛亮”的道理。在1990年，Schapire证明一个类强可学习与一个类弱可学习是等价的，即一个类是强可学习的充分必要条件是这个类是弱可学习的。
这样一来，如果已经发现了“弱学习算法”，那么能否将它提升为“强学习算法”。发现弱学习算法通常要比发现强学习算法容易得多，那么如何具体实施提升，便成为开发提升方法时所要解决的问题。经典的具有代表的提升方法是AdaBoost算法。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。Boosting集成就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称基本分类器），然后组合这些弱分类器，构成一个强分类器。
AdaBoost
AdaBoost（Adaptive Boosting）有自适应集成之意。对于AdaBoost而言，有两个重点：一是在每一轮如何改变训练数据的权值；二是如何将弱分类器组合成一个强分类器。关于第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值，这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，于是，分类问题被一系列的弱分类器“分而治之”。至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法，具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率较大的弱分类器的权值，使其在表决中起较小的作用。AdaBoost的巧妙之处就在于它将这些想法自然且有效地实现在一种算法里。
AdaBoost算法描述
假设给定一个二类分类的训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 。其中，每个样本点由实例与标记组成。实例 $x_i \in X \subseteq R^n$ ，标记 $y_i \in Y=\{-1,+1\}$ ，$X$ 是实例空间，$Y$ 是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器，并将这些弱分类器线性组合成为一个强分类器。
AdaBoost算法描述
输入：训练集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中 $x_i \in X \subseteq R^n$ ，标记 $y_i \in Y=\{-1,+1\}$ ；弱学习算法；
输出：最终分类器 $G(x)$；
(1) 初始化训练数据的权值分布 $D_1=\{w_{11},...,w_{1i},...,w_{1N}\}, w_{1i}=\frac{1}{N}, i=1,2,...,N$ 。
(2) 对 $m=1,2,...,M$
(a) 使用具有权值分布 $D_{m}$ 的训练数据集学习，得到基本分类器 $G_m(x):X \rightarrow \{-1,+1\}$ ；
(b) 计算 $G_m(x)$ 在训练数据集上的分类误差率 $e_m=P(G_m(x_i) \neq y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i) \neq y_i)$ ，其中 $I(x)$ 为指示函数；
(c) 计算 $G_m(x)$ 的系数 $a_m=\frac{1}{2} log \frac{1-e_m}{e_m}$ ，这里的对数是自然对数；
(d) 更新训练数据集的权值分布 $D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$ ，其中 $w_{m+1,i}=\frac{w_{mi}}{Z_m}e^{-a_m \cdot y_i \cdot G_m(x_i)}, i=1,2,...,N$ ，这里 $Z_m$ 是规范化因子，$Z_m=\sum_{i=1}^{N}w_{mi} \cdot e^{-a_my_iG_m(x_i)}$ ，它使 $D_{m+1}$ 成为一个概率分布；
(3)构建基本分类器的线性组合 $f(x)=\sum_{m=1}^{M} a_m G_m(x)$ ，得到最终分类器 $G(x)=sign(f(x))$ ，其中 $sign(x)$ 为符号函数；
AdaBoost算法说明
步骤（1）：假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器 $G_1(x)$ 。
步骤（2）：AdaBoost反复学习基本分类器，在每一轮 $m=1,2,...,M$ 顺次地执行下列操作：
(a)使用当前分布 $D_m$ 加权的训练集，学习基本分类器 $G_m(x)$ ；
(b)计算基分类器 $G_m(x)$ 在加权训练集上的分类误差率：$e_m=P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i) \neq y_i} w_{mi}$ ，这里，$w_{mi}$ 表示第 $m$ 轮中第 $i$ 个实例的权值，$\sum_{i=1}^{N}w_{mi}=1$ 。这表明，$G_m(x)$ 在加权的训练集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和，由此可以看出数据权值分布 $D_m$ 与基本分类器 $G_m(x)$ 的分类误差率的关系。
(c) 计算基本分类器 $G_m(x)$ 的系数 $a_m$ ，$a_m$ 表示 $G_m(x)$ 在最终分类器中的重要性。由式 $a_m=\frac{1}{2}log\frac{1-e_m}{e_m}$ 可知，当 $e_m \leqslant \frac{1}{2}$ ，$a_m \geqslant 0$ ，并且 $a_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
(d) 更新训练数据的权值分布为下一轮作准备，式 $w_{m+1,i}=\frac{w_{mi}}{Z_m}e^{-a_m \cdot y_i \cdot G_m(x_i)}$ 可以写成：
$w_{m+1,i}= \begin{cases} \frac{w_{mi}}{Z_m} \cdot e^{-a_m} , && G_m(x_i)=y_i \\ \frac{w_{mi}}{Z_m} \cdot e^{a_m} , && G_m(x_i) \neq y_i \end{cases}$
由此可知，被基本分类器 $G_m(x)$ 误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大 $e^{2a_m}=\frac{e_m}{1-e_m}$ 倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。这在一定程度上类似“残差逼近”的思想。
步骤（3）：线性组合 $f(x)$ 实现 $M$ 个基分类器的加权表决。系数 $a_m$ 表示了基本分类器 $G_m(x)$ 的重要性，这里，所有 $a_m$ 之和并不为1。$f(x)$ 的符号决定实例 $x$ 的类，$f(x)$ 的绝对值表示分类的确信度。
AdaBoost例子
直接看AdaBoost算法描述可能比较抽象，这里举一个例子，（截图来自《统计学习方法》第二版 P158~P160）。假定如下表所示的训练集。假设弱分类器由 $x<v$ 或 $x > v$ 产生，其阈值 $v$ 使该分类器在训练集上分类误差率最低。
AdaBoost算法推导
关于AdaBoost的算法推导细节可参考《统计学习方法》第二版 P162-165 ，《机器学习》西瓜书虽与《统计学习方法》推导整体流程一致，但《西瓜书》中抽象符号较多会相对比较难看懂。基本看《统计学习方法》就可以了，这里摘抄自《统计学习方法》，大致算法推导流程如下：
(1) 损失函数定义为指数损失函数，即 $L(y,f(x))=e^{-y \cdot f(x)}$ ，其中第 $m$ 轮迭代 $f_m(x)=f_{m-1}(x)+a_mG_m(x)$ ；
(2) 求解使在第 $m$ 轮最小的 $G_m(x)$ ，即 $G_m^*(x) = \mathop{\arg\min}_{G} \sum_{i=1}^{N} \overline{w}_{mi} \cdot I(y_i \neq G(x_i))$ ，其中 $\overline{w}_{mi} = e^{-y_i \cdot f_{m-1}(x_i)}$ 为常数；
(3) 对 $\sum_{i=1}^{N} \overline{w}_{mi} e^{-y_i \cdot a \cdot G(x_i)}$ 中 $a$ 求导并使导数为0，可以求得使其最小的 $a$ ，即 $a_m^* = \frac{1}{2}log \frac{1-e_m}{e_m}$ ；其中 $e_m$ 为常数（即分类误差率）；
样本更新权重可以推导得 $\overline{w}_{m+1,i} = \overline{w}_{m,i} e^{-y_i \cdot a_m \cdot G_m(x)}$ ，以上便可求得算法过程中的关键参数 $a_m$ 和 $G_m(x)$ 。
Boosting Tree
Boosting Tree又称提升树，它是以分类树或回归树为基本分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。提升树对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。Boosting Tree可以表示为决策树的加法模型：$f_M(x)= \sum_{m=1}^{M}T(x;\Theta_m)$ ，其中 $T(x;\Theta)$ 表示决策树；$\Theta_m$ 为决策树的参数；$M$ 为树的个数。
Boosting Tree算法描述
首先确定初始提升树 $f_0(x)=0$ ，第 $m$ 步的模型是 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$ ，其中，$f_{m-1}(x)$ 为当前模型通过经验风险极小化确定下一棵决策树的参数 $\Theta_m$ ，$\Theta_m^* = \mathop{\arg\min}_{ \Theta_m} \sum_{i=1}^{N} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$ ，由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。
针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。对于二分类问题，提升树算法将AdaBoost算法中的基分类器限制为二类分类就是一种以指数为损失函数的提升树。
对于更一般地提升树，已知一个训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}, x_i \in X \subseteq R^n$ ，$X$ 为输入空间，$y_i \in Y \subseteq R$ ，$Y$ 为输出空间。如果将输入空间 $X$ 划分为 $J$ 个互不相交的区域 $R_1,R_2,...,R_J$ ，并且在每个区域上确定输出的常量 $c_j$ ，那么树可表示为 $T(x; \Theta) = \sum_{j=1}^{J} c_j I(x \in R_j)$ ，其中，参数 $\Theta = \{(R_1,c_1),(R_2,c_2),...,(R_J,c_J)\}$ 表示树的区域划分和各区域上的常数，$J$ 是回归树的复杂度即叶结点个数。回归问题提升树使用以下前向分步算法：
$f_0(x)=0$
$f_m(x) = f_{m-1}(x) + T(x;\Theta_m), m=1,2,...,M$
$f_M(x) = \sum_{m=1}^{M} T(x,\Theta_m)$
在第 $m$ 步，给定当前模型 $f_{m-1}(x)$ ，需求解 $\Theta_m^* = \mathop{\arg\min}_{ \Theta_m} \sum_{i=1}^{N} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)$ 得到 $\Theta_m^*$ ，即第 $m$ 棵树的参数。当采用平方误差损失函数时，$L(y,f(x))=(y-f(x))^2$ ，其损失变为 $L(y,f(x))=[r-T(x;\Theta_m)]^2$ ，其中 $r=y-f_{m-1}(x)$ 是当前模型拟合数据的残差（residual），所以重点是如何拟合当前模型的残差。
Boosting Tree算法描述
输入：训练集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},x_i \in X \subseteq R^n,y_i \in Y \subseteq R$ ；
输出：提升树 $f_M(x)$
(1) 初始化 $f_0(x)=0$
(2) 对 $m=1,2,...,M$
(a) 计算残差 $r_{mi}=y_i - f_{m-1}(x_i), i=1,2,...,N$
(b) 拟合残差 $r_{mi}$ 学习一棵决策树（解决分类回归问题都可以，取决于目标函数的定义），得到 $T(x;\Theta_m)$
(c) 更新 $f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
(d) 得到 Boosting Tree： $f_M(x) = \sum_{m=1}^{M}T(x;\Theta_m)$
Boosting Tree例子
直接看Boosting Tree算法描述会比较抽象，下面列举一个Boosting Tree的例子，摘自《统计学习方法》 P168-170，如下：
Gradient Boosting
Gradient Boosting 又称梯度提升。这里摘抄自《深度理解XGBoost》里的内容，2001年梯度提升算法被提出，这是近似方法，其关键是利用损失函数的负梯度在当前模型的值 $-[\frac{\partial L(y,F(x_i))}{\partial F(x_i)}]_{F(x)=F_{m-1}(x)}$ 作为回归问题提升树算法中的残差的近似值。
Gradient Boosting
Gradient Boosting算法描述
输入：训练集，损失函数 $L(y,F(x))$ ，训练轮数 $M$ 。
输出：最终模型 $F_M(x)$ 。
算法：
1）通过常数初始化模型 $F_0(x) = \mathop{\arg\min}_{ \gamma } \left ( \sum_{n=1}^{N} L(y_i, \gamma ) \right )$ ；
2）对 $m=1,2,...,M$ ，执行以下步骤。
(a) 计算负梯度 : $r_{im} = -\left [ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right ]_{F(x)=F_{m-1}(x)}, i=1,2,...,n$ ；
(b) 训练一个子模型 $h(x)$ ，用来拟合 $r_{im}$ ；
(c) 计算步长 $\gamma_m$ : $\gamma_m = \mathop{\arg\min}_{ \gamma } \left ( \sum_{n=1}^{N} L(y_i, F_{m-1}(x_i) + \gamma \cdot h_m(x_i) ) \right )$
(d) 更新模型: $F_m(x)=F_{m-1}(x) + \gamma_m \cdot h_m(x)$
3）输出 $F_M(x)$ 。
Gradient Boosting算法解释
注意算法描述中的 $r$ 和 $\gamma$ 是两个符号，$r$ 是残差，而 $\gamma$ 是步长。
算法第1步初始化一个常数作为初始模型。在第2步中，每一轮均在前面训练的基础上训练一个新的子模型 $h(x)$ 。第2步(a)计算损失函数的负梯度，将其作为残差；第2步(b)训练一个子模型 $h(x)$ ，以拟合第2步(a)中的残差；第2步(c)通过线性搜索找到最优步长 $\gamma_m$ ，使得损失函数最小。最后，经过 $M$ 轮训练更新模型，第3步输出最终模型。
Gradient Tree Boosting
Gradient Tree Boosting是Gradient Boosting应用最为广泛的一种实现，它以决策树作为子模型，其中最具有代表性的以CART作为子模型。Gradient Tree Boosting算法和Gradient Boosting类似，区别只在于Gradient Tree Boosting 子模型为树模型。
Gradient Tree Boosting算法描述
输入：训练集，损失函数 $L(y,F(x))$ ，训练轮数 $M$ 。
输出：最终模型 $F_M(x)$ 。
算法：
1）通过损失函数最小化初始化模型： $F_0(x) = \mathop{\arg\min}_{ \gamma } \left ( \sum_{n=1}^{N} L(y_i, \gamma ) \right ) $ ；
2）对 $m=1,2,...,M$ ，执行以下步骤。
(a) 计算负梯度 : $r_{im} = -\left [ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right ]_{F(x)=F_{m-1}(x)}, i=1,2,...,n$
(b) 训练一个回归树去拟合目标值 $r_{im}$ ，树的终端区域为 $R_{jm} (j=1,2,...,J_m)$ 。
(c) 对 $j=1,2,...,J_m$ ，计算步长 $\gamma_{jm}$ 。 $\gamma_{jm} = \mathop{\arg\min}_{\gamma} \left ( \sum_{x_i \in R_{jm}} L(y_i, F_{m-1}(x_i) + \gamma \right ) $
(d) 更新模型： $F_m(x) = F_{m-1}(x) + \sum_{j=1}^{J_m} \gamma_{jm} \cdot I(x \in R_{jm}) $ 。
3) 输出 $F_M(x)$ 。
Gradient Tree Boosting算法解释
注意算法描述中的 $r$ 和 $\gamma$ 是两个符号，$r$ 是残差，而 $\gamma$ 是步长。
该算法与Gradient Boosting算法数学表达上不同之处在于第2步的(b)和(c)。但其本质是一致的，Gradient Boosting中训练出的 $h(x)$ 在此处相当于 $I(x \in R_{jm})$ 指示区域函数，其中 $I(x \in R_{jm})$ 相当于 $h(x)$ 具体的树模型的实现。Gradient Tree Boosting算法通过拟合一棵回归树去拟合负梯度，$I(x \in R_{jm})$ 指示的终端区域可以理解为叶子节点。在第2步(c)生成新的回归树时，此处步长 $\gamma_{jm}$ 相当于给每个叶节点计算一个权重 $\gamma_{jm}$ 。
总结
这篇笔记首先介绍了Boosting的基本思想；其次介绍了经典的Boosting方法的AdaBoost算法，给出算法描述、例子和算法大致推导过程，AdaBoost在更新样本分布阶段一定程度上类似“残差逼近”的思想；再介绍了提升树算法（Boosting Tree），给出算法描述和例子，提升树算法通过例子可以比较容易理解，其关键是每次拟合残差的方式来逼近；最后介绍了梯度提升（Gradient Boosting）算法，其包括一般梯度提升（Gradient Boosting）和梯度提升树（Gradient Tree Boosting），其关键是在一般提升的基础上引入了梯度残差逼近的方式，我认为引入梯度间接优化的优点在于：直接优化转为间接优化，以梯度（即上一轮的斜率趋势方向）为目标进行分组，对每个组分别进行线性搜索估计，从一定程度上缩小了假设空间搜索范围。
参考文献
- 周志华 《机器学习》P173-177
- 李航 《统计学习方法》第二版 P155-173
- 何龙 《深入理解XGBoost》P151-154