本篇内容为西瓜书第 8 章集成学习 8.1 8.2 8.3 8.4 8.5 的内容：

• 8.1 个体与集成
• 8.2 Boosting
• 8.3 Bagging与随机森林
• 8.4 结合策略
• 8.5 多样性

如移动端无法正常显示文中的公式，右上角跳至网页即可正常阅读。

个体与集成

集成学习 (ensemble learning) 通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统 (multi-classifier system)、基于委员会的学习 (committee-based learning) 等。下图显示出集成学习的一般结构：

集成学习先产生一组“个体学习器”，再用某种策略将它们结合起来。通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。但要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”，即学习器间具有差异。如下图的例子所示：

个体学习器通常由一个现有的学习算法从训练数据产生。只包含同种类型的个体学习器的集成是“同质”的，同质集成中的个体学习器亦称基学习器，基学习器有时也被直接称为弱学习器；包含不同类型的个体学习器的集成是“异质”的。事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心。

弱学习器常指泛化性能略优于随机猜测的学习器。例如在二分类问题上精度略高于 50% 的分类器。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类。一类是个体学习器间存在强依赖关系、必须串行生成的序列化方法，代表是 Boosting；另一类是个体学习器间不存在强依赖关系、可同时生成的并行化方法，代表是 Bagging 和随机森林 (Random Forest)。

Boosting

Boosting 是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本进行分布调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值 $T$，最终将这 $T$ 个基学习器进行加权结合。如下图所示：

提升的理论意义就是如果一个问题存在弱分类器，则可通过提升的办法得到强分类器。因此，需要解决的问题有两个。一个是在每一轮如何改变训练数据的权值或概率分布；另一个是如何将弱分类器组合成一个强分类器。

Adaboost

Boosting 族算法最著名的代表是 AdaBoost。对于以上两个问题 AdaBoost 的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注；并采取加权多数表决的办法来完成弱分类器的组合。具体地，加大分类误差率小的弱分类器权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

总的来说，Adaboost 的思路是：更加重视那些做错的样本，让它的权值升高。下面我们来看 Adaboost 的算法，在李航的《统计学习方法》里解释的很清晰。如下图所示：

对 Adaboost 算法说明如下：

其中，分类器权重更新公式为

$$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$$

这里的对数是自然对数。

更新训练数据集的权值分布的公式为

$$D_{m+1}=(w_{m+1,1}, w_{m+1,2}, ···, w_{m+1,N})\\w_{m+1,i}=\frac{w_{mi}}{z_m}exp(-\alpha_m y_i G_m(x_i)),\quad i=1,2,···,N$$

由第 $m$ 次算第 $m+1$ 次的权值替换。权值更新后，再计算新的 $G_{m+1}(x)$，直到 $M$，得到 $M$ 个基分类器。

这里要解释一个博主认为对于理解 AdaBoost 算法比较重要的东西，就是权值调整和正负样本之间的关系，也就是说，是如何通过判断样本正确与否来达到调整权值的目的。

如果在 $G_m(x)$ 上预测错误，必然有正确值和预测值符号相反，即一个为 +1，一个为 -1。那么，我们来看调整权值的公式：

$$w_{m+1,i}=\frac{w_{mi}}{z_m}exp(-\alpha_m y_i G_m(x_i)),\quad i=1,2,···,N$$

一般分类误差率 $e_m<0.5$，则 $1-e_m>0.5$，即 $1-e_m>e_m$，故 $\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}>0$

可判断得到 $y_iG_m(x_i)$ 的符号必为负，又 $\alpha_m >0$，则有 $exp(-\alpha_m y_i G_m(x_i))>1$，乘上一个大于 1 的数，值一定变大，即这个样本在整个权值中占据更大比重；反之，若预测正确，则有 $exp(-\alpha_m y_i G_m(x_i))<1$，该样本所占权值减小。

下面我们来看一个例子，来更好的理解上述算法的步骤。

我们可以看到训练数据是线性不可分的，因此不能通过一个简单的二分类器达到好的效果。用 AdaBoost 算法来学习一个强分类器。

首先，遍历 0.5、1.5、2.5、······ 9.5，初次划分的阈值取 2.5 时分类误差率最低，得到基本分类器 $G_1(x)$，有误差率 $e_1$，并计算 $G_1(x)$ 的系数 $\alpha_1$。有分类器 $sign[f_1(x)]$。更新训练数据的权值分布，计算 $D_2$，为了给下一个基本分类器使用。在权值分布为 $D_2$ 的训练数据上，得到基本分类器 $G_2(x)$，有误差率 $e_2$，系数 $\alpha_2$。和分类器 $sign[f_1(x)]$ 叠加后，有分类器 $sign[f_2(x)]$。再次更新数据权值分布，重复上述步骤，得到分类器 $sign[f_3(x)]$ 在训练数据集上误分类点个数为 0，即最终分类器为 $G(x)=sign[f_3(x)]$。

以第 8 个样本为例，我们来测验。由分类器

$$G(x)=sign[f_3(x)]=sign[0.4326G_(x)+0.6469G_2(x)+0.7514G_3(x)]$$

计算得

$$0.4326 \times(-1)+0.6469\times(1)+0.7514\times(1)=0.9657>0$$

故预测为 +1，预测正确。对于其他样本点也可通过同样的方式来进行预测。

可以认为 AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二类分类学习方法。

XGBoost

XGBoost (eXtreme Gradient Boosting)，由华盛顿大学的陈天奇博士在梯度提升决策树 (Gradient Boosting Decision Tree, GBDT) 算法的基础上提出的，并开发了 C++ 版本。该算法由于精度高、可并行化处理和可移植性，被广泛应用于各个领域，也是 Kaggle 竞赛者最常用的方法之一。

GB (梯度提升算法)：
在提升算法中，如果每一步的弱预测模型生成都是依据损失函数的梯度方向，则称之为梯度提升 (gradient boosting, GB)。该算法首先给定一个目标损失函数，它的定义域是所有可行的弱函数集合（基函数）；提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部极小值。GB 其实是一个算法框架，可以将已有的分类或回归算法放入其中，得到一个性能很强大的算法。这种在函数域的梯度提升观点对机器学习的很多领域有深刻影响。

GBDT (梯度提升决策树算法)：
GB 算法中最典型的基学习器是决策树，尤其是 CART，正如名字的含义，GBDT 是 GB（梯度提升）和 DT（决策树）的结合。要注意的是这里的决策树是回归树，且 GBDT 中的决策树是弱模型。

相对于传统的 GBDT，XGBoost 的优势主要体现在以下几个方面。

$\quad$基分类器的选择：传统的 GBDT 以 CART (Classification And Regression Tree) 为基分类器，而 XGBoost 不仅支持 CART，还支持线性分类器。

$\quad$二阶泰勒展开：XGBoost 对代价函数进行了二阶泰勒展开，使用了一阶和二阶导数，同时在代价函数中加入了正则项，降低了模型的方差，使学习到的模型更加简单，避免了过拟合。

$\quad$列抽样：XGBoost 支持列抽样，这样不仅能降低过拟合，还能减少模型的计算量；同时，XGBoost 支持并行化计算，加快了模型的训练速度。

下面我们来推导 XGBoost 算法。首先给出一个提升算法的框架，然后考虑使用二阶导信息，计算出目标函数，最后构造决策树的结构。要做的事其实有两个，计算叶权值和构造树结构，这也是一棵决策树的核心。

提升算法

给定输入向量 $x$ 和输出变量 $y$ 组成的若干训练样本 $(x_1,y_1), (x_2,y_2),···,(x_n,y_n)$，目标是找到近似函数 $\hat F (\vec{x})$，使得损失函数 $L(y,F(x))$ 的损失值最小。

$L(y,F(x))$ 的典型定义如下，若 $y$ 服从高斯分布，则

$$L(y,F (\vec{x})) = \frac{1}{2}(y-F (\vec{x}))^2$$

若 $y$ 服从拉普拉斯分布，则

$$L(y,F (\vec{x})) = |y-F (\vec{x})|$$

假定最优函数为 $F^*(\vec(x))$，即

$$F^*(\vec{x})=\mathop{\arg\min}_{F}E_{(x,y)}[L(y,F(\vec{x}))]$$

假定 $F(x)$ 是一族基函数 $f_i(x)$ 的加权和

$$F(\vec{x})=\sum_{i=1}^{M}r_if_i(x)+const$$

我们要思考的一个问题是，假定当前已经得到了 $m-1$ 棵决策树，是否可以通过现有样本和决策树的信息，对第 $m$ 棵决策树的建立产生有益的影响呢？这就是我们下面要介绍的想法。

梯度提升方法寻找最优解 $F(x)$ 使得损失函数在训练集上的期望最小。方法如下：

$\quad$ 首先，给定常函数 $F_0(x)$

$$F_0(\vec{x})=\mathop{\arg\min}_{\gamma} \sum_{i=1}^{n}L(y_i,\gamma)$$

以贪心的思路扩展得到 $F_m(x)$

$$F_m(\vec{x})=F_{m-1}(\vec{x})+\mathop{\arg\min}_{f \in H} \sum_{i=1}^{n}L(y_i,F_{m-1}(\vec{x})+f(\vec{x}))$$

考虑使用二阶导信息

目标函数：

$$J(f_t)=\sum_{i=1}^{n}L(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+C$$

根据 Taylor 展式

$$f(x+\Delta x) \approx f(x)+f'(x)\Delta x+\frac{1}{2}f''(x)\Delta x^2$$

令

$$g_i=\frac{\partial L(y_i,\hat y_i^{(t-1)})}{\partial y_i^{(t-1)}}\\h_i=\frac{\partial L^2(y_i,\hat y_i^{(t-1)})}{\partial y_i^{(t-1)}}$$

得

$$J(f_t) \approx \sum_{i=1}^{n}[L(y_i,\hat y_i^{(t-1)}+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)+C$$

决策树的描述

使用决策树对样本做分类（回归），是从根结点到叶结点的细化过程；落在相同叶结点的样本的预测值是相同的。

假定某决策树的叶结点数目为 $T$，每个叶结点的权值为 $\vec{w}=(w_1,w_2,···,w_T)$，决策树的学习过程，就是构造如何使用特征得到划分，从而得到这些权值的过程。

样本 $x$ 落在叶结点 $q$ 中，定义 $f$ 为：$f_t(x)=w_{q(x)}$。

正则项的定义

决策树的复杂度可考虑叶结点数和叶权值。如使用叶结点总数和叶权值平方和的加权

$$\Omega(f_t)=\gamma·T_0+\lambda·\frac{1}{2}\sum_{j=1}^{T}w_j^2$$

举个例子来说明，如图：

可计算得 $\Omega=\gamma·3+\frac{1}{2}\lambda(4+0.01+1)$

目标函数的计算

目标函数

$$J(f_t) \approx \sum_{i=1}^{n}[L(y_i,\hat y_i^{(t-1)}+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)+C$$

化简后得

$$J(f_t)=\sum_{j=1}^{T}[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma·T+C$$

定义

$$G_j=\sum_{i \in I_j}g_i \quad H_j=\sum_{i \in I_j}h_i$$

对 $w$ 求偏导，得

$$\frac{\partial J(f_t)}{\partial w_j}=G_j+(H_j+\lambda)w_j=0$$

则有

$$w_j=-\frac{G_j}{H_j+\lambda}$$

回代入目标函数，得

$$J(f_t)=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma·T$$

这个式子表示了什么呢？我们还是以上个例子为例：

构造决策树的结构

构造决策树的结构即解决对于当前结点，应该如何进行字数划分的问题。

遍历可行的分割点，选择增益最大的划分，继续同样的操作，直到满足满足某阈值或所有记录的目标变量值相同。

XGBoost小结

XGBoost 与 GBDT 主要的不同在于其目标函数使用了正则项并利用了二阶导数信息。

以上即为 XGBoost 使用的核心推导过程。

Bagging与随机森林

Bagging 是并形式集成学习方法最著名的代表。Bagging 的基本流程是通过自助采样法 (bootstrap sampling) 得到 $T$ 个含 $m$ 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。如下图所示：

自助采样法的含义：给定包含 $m$ 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过 $m$ 次随机采样操作，我们得到含 $m$ 个样本的采样机，初始训练集中有的样本在采样集里多次出现，有的则从未出现，初始训练集中约有 63.2% 的样本出现在采样集中。

在对预测输出进行结合时，Bagging 通常对分类任务使用简单投票法，对回归任务使用简单平均法。Bagging 的算法描述如下图所示：

随机森林 (Random Forest, RF) 在 Bagging 的基础上做了修改。它的基本流程为：从样本集中用 Bootstrap 采样选出 $n$ 个样本，从所有属性中随机选择 $k$ 个属性，选择最佳分割属性作为结点建立 CART 决策树；重复以上步骤 $m$ 次，即建立了 $m$ 棵 CART 决策树，这 $m$ 棵 CART 决策树形成随机森林，通过投票表决结果，决定数据属于哪一类。

具体地说，RF 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。即传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；而在 RF 中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $k$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。

这样一来，Bagging 中基学习器的“多样性”仅通过样本扰动（对初始训练集的采样）而来，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。参数 $k$ 控制了随机性的引入程度，一般情况下，推荐值 $k=log_2d$。

因此，随机森林的训练效率常优于 Bagging，因为在个体决策树的构建过程中，Bagging 使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的“随机型”决策树则只需考察一个属性子集。

结合策略

假定集成包含 $T$ 个基学习器 $\{h_1,h_2,···,h_T \}$，其中 $h_i$ 在示例 $x$ 上的输出为 $h_i(x)$。对于基分类器 $h_i$ 进行结合的常见策略有以下几种：

• 简单平均法

$$H(x)=\frac{1}{T}\sum_{i=1}^{T}h_i(x)$$

适用于数值型输入 $h_i(x) \in R$。

• 加权平均法

$$H(x)=\sum_{i=1}^{T}w_ih_i(x)$$

其中 $w_i$ 是个体学习器 $h_i$ 的权重，通常要求 $w_i \ge 0,\sum_{i=1}^{T}w_i=1 $

一般而言，在个体学习器性能相差较大时，宜使用加权平均法；而在个体学习器性能相近时，宜使用简单平均法。

• 投票法

对分类任务来说，学习器 $h_i$ 将从类别标记集合 $\{c_1,c_2,···,c_N \}$ 中预测出一个标记，最常见的结合策略是使用投票法 (voting)。

$\quad$简单投票机制
$\qquad$一票否决（一致表决）
$\qquad$少数服从多数
$\qquad$阈值表决

$\quad$贝叶斯投票机制

下面我们来举个例子来说明投票机制举例。假定有 N 个用户可以为 X 个电影投票（假定投票者不能给同一电影重复投票），投票有 1、2、3、4、5 星共 5 档。

我们来考虑如何根据用户投票，对电影排序。这本质上仍然是分类问题：对于某个电影，有 N 个决策树，每个决策树对该电影有一个分类，求解这个电影属于哪一类。这里我们给出一种可能的方案：

$$WR=\frac{v}{v+m}R+\frac{m}{v+m}C$$

$WR$：加权得分
$R$：该电影的用户投票平均得分
$C$：所有电影的平均得分
$v$：该电影的投票人数
$m$：排名前 250 名的电影的最低投票数

• 学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking 是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器。

Stacking 先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

多样性

对于增强多样性，一般思路在学习过程中引入随机性，常见做法主要是对数据样本、输入属性、输出表示、算法参数进行扰动，并且不同的多样性增强机制可同时使用。

最后，我们来插入一个偏差与方差的话题。

给定数据 $D$，自变量 $x$ 的相应真实值为 $y(x)$，预测值为 $h_\theta(x,D)$，使用平方误差作为目标函数 $E_D[y(x)-h_\theta(x,D)]^2$，对这个式子变形可以得到

$$E_D[y(x)-h_\theta(x,D)]^2=E_D[\{y(x)-E_D[y(x)]\}^2]+\{E_D[y(x)]-h_\theta(x,D)\}^2$$

其中，$E_D[\{y(x)-E_D[y(x)]\}^2]$ 表示方差 (Variance)，$\{E_D[y(x)]-h_\theta(x,D)\}^2$ 表示偏差 (Bias)。我们用图示的方式来解释二者的区别：

圆心为完美预测的模型，深蓝色的点代表某个模型的学习结果。离靶心越远，准确率越低。低 Bias 表示离圆心近，高 Bias 表示离圆心远；高 Variance 表示学习结果分散，低 Variance 表示学习结果集中。

从偏差-方差分解的角度看，Bagging 能够减少训练方差，对于不剪枝的决策树、神经网络等易受样本扰动的学习器有良好的集成效果；Boosting 减少偏差，能够基于泛化能力较弱的学习器构造强学习器。

参考链接：
机器学习提升算法之Adaboost、GB、GBDT与XGBoost算法
adaboost和GBDT的区别以及xgboost和GBDT的区别
详解AdaBoost算法
雷雪梅, 谢依彤. 用于高血压菜谱识别的基于遗传算法的改进XGBoost模型[J]. 计算机科学, 2018(s1).
一步一步理解GB、GBDT、xgboost
GB和GBDT算法流程及分析
决策树之 CART
Introduction to Boosted Trees
Understanding the Bias-Variance Tradeoff

不足之处，欢迎指正。

$$$$