[读书笔记]《西瓜书》第八章 集成学习 补充

第八章 集成学习 补充

集成学习这一章节的内容相比于前面神经网络、支持向量机、贝叶斯分类器要相对少一点，同时这一块理解上也要更贴近人类的直观感受，毕竟中国自古有句老话：三个臭皮匠，顶过诸葛亮。所以这一章的内容只需要进行一个简单的总结和补充就可以完结了，相比书上的内容来说，现在无论在 Kaggle 比赛中，还是在工程实施上最常用的 xgboost 和 lightgbm 也借此机会补充一下。好了，开始咱们对这一章的总结和补充吧~

为什么有效？

虽然集成学习的有效性是十分符合直观感受的，但是“是否有效”和“为什么有效”这两个问题在学术上是非常严谨的。于是在网上查找相关的内容的时候，找到了一本PDF电子书《The Handbook of Brain Theory and Neural Network》，在这本书中有一篇 Thomas G. Dietterich 写的 Ensemble Learning 一篇论文，这篇论文中有关于这个问题的详细描述。

统计上的原因

一个学习算法可以理解为在一个假设空间 $\mathcal{H}$ 中选找到一个最好的假设。但是，当训练样本的数据量小到不够用来精确的学习到目标假设时，学习算法可以找到很多满足训练样本的分类器。所以，学习算法选择任何一个分类器都会面临一定错误分类的风险，因此将多个假设集成起来可以降低选择错误分类器的风险。

计算上的原因

很多学习算法在进行最优化搜索时很有可能陷入局部最优的错误中，因此对于学习算法而言很难得到一个全局最优的假设。事实上人工神经网络和决策树已经被证实为是一个 NP 问题。集成算法可以从多个起始点进行局部搜索，从而分散陷入局部最优的风险。

表示上的原因

在多数应用场景中，假设空间 $\mathcal{H}$ 中的任意一个假设都无法表示 (或近似表示) 真正的分类函数 $f$。因此，对于不同的假设条件，通过加权的形式可以扩大假设空间，从而学习算法可以在一个无法表示或近似表示真正分类函数 $f$ 的假设空间中找到一个逼近函数 $f$ 的近似值。

集成学习的分类

在理论上了解了集成学习为什么有效之后，紧接着的问题就是集成学习如何分类，这方面业界应该也算是比较统一了。

从集成效果来看

集成学习可以分为三大类：

• 用于减少方差的 Bagging
• 用于减少偏差的 Boosting
• 用于提升预测结果的 Stacking

从训练过程来看

集成学习方法可以归为如下两大类：

• 串行集成方法，这种方法串行地生成基础模型（如AdaBoost）。

  串行集成的基本动机是利用基础模型之间的依赖。通过给错分样本一个较大的权重来提升性能。

• 并行集成方法，这种方法并行地生成基础模型（如Random Forest）。

  并行集成的基本动机是利用基础模型的独立性，因为通过平均能够较大地降低误差。

从基学习器来看

集成学习方法分类两种类型：

• 同质集成：这种集成学习模型，通过一个基础学习算法来生成一个同质的基学习器，即同类型的学习器。
• 异质集成：使用不同类型的基学习器最终集成在一起，为了集成后的结果表现的更好，异质基础学习器需要尽可能准确并且差异性够大。

三大类型的总结

在上面集成算法分类中，最出名就是三中类型的分类：Bagging、Boosting 和 Stacking。虽然在西瓜书中有相关内容的介绍，但是感觉比较散，这里重新组织和总结一下。

Bagging

Bagging (Boostrap Aggregating) 是由 Breiman 于 1996 年提出，基本思想如下：

• 每次采用有放回的抽样从训练集中取出 $n$ 个训练样本组成新的训练集。
• 利用新的训练集，训练得到 $M$ 个子模型 ${h_1,h_2,…,h_M}$。
• 对于分类问题，采用投票的方法，得票最多子模型的分类类别为最终的类别；对于回归问题，采用简单的平均方法得到预测值。

对于 Bagging 来说，其采用的基本想法就是通过多个估计值取平均的方式来减少模型验证时的方差。这里通过有放回的随机采样来训练 $M$ 个基学习器达到这个效果，因此其对于每一个样本来说，其始终不被采用的概率为 $(1 - \frac{1}{M})^M$ ，这个值取极限的话，意味着存在 36.8% 的训练集样本可以用作验证集对于学习器的泛化能力进行包外估计（out-of-bag estimate）。

在这一类算法中最出名的就是随机森林了，而对于随机森林来说，其本身是一种利用决策树作为基学习器的集成学习算法。

PS: 这一部分在西瓜书中有详细的说明，并且对于随机森林在构建过程中引入样本扰动和特征扰动的特性也有说明。这里需要补充一点书上没说的内容，即在训练随机森林时需要注意的一些点：

1.在构建决策树的过程中是不需要剪枝的。

2.整个森林的树的数量和每棵树的特征需要人为进行设定。

3.构建决策树的时候分裂节点的选择是依据最小基尼系数的。

Boosting

Boosting 是一种提升算法，可以将弱的学习算法提升 (boost) 为强的学习算法。基本思路如下：

• 利用初始训练样本集训练得到一个基学习器。

• 提高被基学习器误分的样本的权重，使得那些被错误分类的样本在下一轮训练中可以得到更大的关注，利用调整后的样本训练得到下一个基学习器。

• 重复上述步骤，直至得到 $M$ 个学习器。

• 对于分类问题，采用有权重的投票方式；对于回归问题，采用加权平均得到预测值。

对于 Boosting 来说，其采用的基本想法就是将数据通过每一次基学习器的训练结果进行权重修正，最终达到一个比较好的准确性和泛化误差。这种方式最终达到的效果就是我们修改了我们决策平面，因此这是一种对于偏差的修正方式。

在这一类算法中出了书上提及的 Adaboost 之外，我们还需要额外补充一下 GBDT、XGBoost、LightGBM 这三种常见的 Boosting 算法。

PS：对于 Adaboost 来说，额外的知识点并没有太多，书上已经介绍的很详细了，需要着重提的就是更新训练集样本的权重是根据基学习器的误差来定的。

GBDT

GBDT (Gradient Boosting Decision Tree) 是另一种基于 Boosting 思想的集成算法，除此之外 GBDT 还有很多其他的叫法，例如：GBM (Gradient Boosting Machine)，GBRT (Gradient Boosting Regression Tree)，MART (Multiple Additive Regression Tree) 等等。GBDT 算法由 3 个主要概念构成：Gradient Boosting (GB)，Regression Decision Tree (DT 或 RT) 和 Shrinkage。

从 GBDT 的众多别名中可以看出，GBDT 中使用的决策树并非我们最常用的分类树，而是回归树。分类树主要用于处理响应变量为因子型的数据，例如天气 (可以为晴，阴或下雨等)。回归树主要用于处理响应变量为数值型的数据，例如商品的价格。当然回归树也可以用于二分类问题，对于回归树预测出的数值结果，通过设置一个阈值即可以将数值型的预测结果映射到二分类问题标签上，即 $Y=\{−1, +1\}$。

PS：这里说的回归树在前面决策树一章节中，对于补充内容中提到过，CART 树可以用作回归树~

对于 Gradient Boosting 而言，首先，Boosting 并不是 Adaboost 中 Boost 的概念，也不是 Random Forest 中的重抽样。在 Adaboost 中，Boost 是指在生成每个新的基学习器时，根据上一轮基学习器分类对错对训练集设置不同的权重，使得在上一轮中分类错误的样本在生成新的基学习器时更被重视。GBDT 中在应用 Boost 概念时，每一轮所使用的数据集没有经过重抽样，也没有更新样本的权重，而是每一轮选择了不用的回归目标，即上一轮计算得到的残差 (Residual)。其次，Gradient 是指在新一轮中在残差减少的梯度 (Gradient) 上建立新的基学习器。

此外 GBDT 中也应用到了 Shrinkage 的思想，其基本思想可以理解为每一轮利用残差学习得到的回归树仅学习到了一部分知识，因此我们无法完全信任一棵树的结果。Shrinkage 思想认为在新的一轮学习中，不能利用全部残差训练模型，而是仅利用其中一部分，即： $$ r_m=y − sF_m(x),0≤s≤1 $$ 注意，这里的 Shrinkage 和学习算法中 Gradient 的步长是两个不一样的概念。Shrinkage 设置小一些可以避免发生过拟合现象；而 Gradient 中的步长如果设置太小则会陷入局部最优，如果设置过大又容易结果不收敛。

XGBoost

XGBoost 是由 Chen 等人提出的一种梯度提升树模型框架。XGBoost 的基本思想同 GBDT 一样，对于一个包含 $n$ 个样本和 $m$ 个特征的数据集 $D={(x_i, y_i)}$，其中 $ |D| = n, x_i \in \mathbb{R}^m,y_i \in \mathbb{R}$，一个集成树模型可以用 $K$ 个加法函数预测输出：

$$ \hat{y}_i = \phi (x_i) = \sum_{k=1}^K f_k(x_i),f_k \in F $$

其中，$\mathcal{F} = \{f \left(\mathbf{x}\right) = w_{q \left(\mathbf{x}\right)}\} \left(q: \mathbb{R}^m \to T, w \in \mathbb{R}^T\right)$ 为回归树 (CART)，$q$ 表示每棵树的结构，其将一个样本映射到最终的叶子节点，$T$ 为叶子节点的数量，每个 $f_w$ 单独的对应一棵结构为 $q$ 和权重为 $w$ 的树。不同于决策树，每棵回归树的每个叶子节点上包含了一个连续的分值，我们用 $w_i$ 表示第 $i$ 个叶子节点上的分值。

XGBoost 首先对损失函数进行了改进，添加了 L2 正则项，同时进行了二阶泰勒展开。损失函数表示为： $$ \begin{equation} \begin{split} \mathcal{L} \left(\phi\right) = \sum_{i}{l \left(\hat{y}_i, y_i\right)} + \sum_{k}{\Omega \left(f_k\right)} \\
\text{where} \ \Omega \left(f\right) = \gamma T + \dfrac{1}{2} \lambda \left| w \right|^2 \end{split} \end{equation} $$ 其中，$l$ 为衡量预测值 $\hat{y}_i$ 和真实值 $y_i$ 之间差异的函数，$\Omega$ 为惩罚项，$\gamma$ 和 $\lambda$ 为惩罚项系数。

我们用 $\hat{y}_i^{(t)}$ 表示第 $t$ 次迭代的第 $i$ 个实例，我们需要增加 $f_t$ 来最小化如下的损失函数：

$$ \mathcal{L}^{\left(t\right)} = \sum_{i=1}^{n}{l \left(y_i, \hat{y}_i^{\left(t-1\right)} + f_t \left(\mathbf{x}_i\right)\right)} + \Omega \left(f_t\right) $$

对上式进行二阶泰勒展开有：

$$ \mathcal{L}^{\left(t\right)} \simeq \sum_{i=1}^{n}{\left[l \left(y_i, \hat{y}_i^{\left(t-1\right)}\right) + g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}_i\right)\right]} + \Omega \left(f_t\right) $$

其中，$g_i = \partial_{\hat{y}^{\left(t-1\right)}} l \left(y_i, \hat{y}^{\left(t-1\right)}\right), h_i = \partial_{\hat{y}^{\left(t-1\right)}}^{2} l \left(y_i, \hat{y}^{\left(t-1\right)}\right)$ 分别为损失函数的一阶梯度和二阶梯度。去掉常数项，第 $t$ 步的损失函数可以简化为：

$$ \tilde{\mathcal{L}}^{\left(t\right)} = \sum_{i=1}^{n}{\left[ g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}_i\right)\right]} + \Omega \left(f_t\right) $$

令 $I_j = \{i \ | \ q \left(\mathbf{x}_i\right) = j \}$ 表示叶子节点 $j$ 的实例集合，上式可重写为：

$$ \begin{equation} \begin{split} \tilde{\mathcal{L}}^{\left(t\right)} &= \sum_{i=1}^{n}{\left[ g_i f_t \left(\mathbf{x}_i\right) + \dfrac{1}{2} h_i f_t^2 \left(\mathbf{x}_i\right)\right]} + \gamma T + \dfrac{1}{2} \lambda \sum_{j=1}^{T}{w_j^2} \\
&= \sum_{j=1}^{T}{\left[\left(\sum_{i \in I_j}{g_i}\right) w_j + \dfrac{1}{2} \left(\sum_{i \in I_j}{h_i + \lambda}\right) w_j^2\right]} + \gamma T \end{split} \end{equation} $$

对于一个固定的结构 $q \left(\mathbf{x}\right)$，可以通过下式计算叶子节点 $j$ 的最优权重 $w_j^*$： $$ w_j^* = - \dfrac{\sum_{i \in I_j}{g_i}}{\sum_{i \in I_j}{h_i} + \lambda} $$ 进而计算对应的最优值： $$ \tilde{\mathcal{L}}^{\left(t\right)} \left(q\right) = - \dfrac{1}{2} \sum_{j=1}^{T}{\dfrac{\left(\sum_{i \in I_j}{g_i}\right)^2}{\sum_{i \in I_j}{h_i} + \lambda}} + \gamma T $$ 上式可以作为评价树的结构 $q$ 的评分函数。通常情况下很难枚举所有可能的树结构，一个贪心的算法是从一个节点出发，逐层的选择最佳的分裂节点。令 $I_L$ 和 $I_R$ 分别表示分裂后左侧和右侧的节点集合，令 $I = I_L \cup I_R$，则分裂后损失的减少量为： $$ \mathcal{L}_{\text{split}} = \dfrac{1}{2} \left[\dfrac{\left(\sum_{i \in I_L}{g_i}\right)^2}{\sum_{i \in I_L}{h_i} + \lambda} + \dfrac{\left(\sum_{i \in I_R}{g_i}\right)^2}{\sum_{i \in I_R}{h_i} + \lambda} - \dfrac{\left(\sum_{i \in I}{g_i}\right)^2}{\sum_{i \in I}{h_i} + \lambda}\right] - \gamma $$ XGBoost 也采用了 Shrinkage 的思想减少每棵树的影响，为后续树模型留下更多的改进空间。同时 XGBoost 也采用了随机森林中的特征下采样 (列采样) 方法用于避免过拟合，同时 XGBoost 也支持样本下采样 (行采样)。XGBoost 在分裂点的查找上也进行了优化，使之能够处理无法将全部数据读入内存的情况，同时能够更好的应对一些由于数据缺失，大量零值和 One-Hot 编码导致的特征稀疏问题。除此之外，XGBoost 在系统实现，包括：并行化，Cache-Aware 加速和数据的核外计算 (Out-of-Core Computation) 等方面也进行了大量优化，相关具体实现请参见论文和 文档。

LightGBM

LightGBM 是由微软研究院的 Ke 等人提出了一种梯度提升树模型框架。之前的 GBDT 模型在查找最优分裂点时需要扫描所有的样本计算信息增益，因此其计算复杂度与样本的数量和特征的数量成正比，这使得在处理大数据量的问题时非常耗时。LightGBM 针对这个问题提出了两个算法：

• Gradient-based One-Side Sampling (GOSS)
• Exclusive Feature Bundling (EFB)

Gradient-based One-Side Sampling

在 AdaBoost 中，样本的权重很好的诠释了数据的重要性，但在 GBDT 中并没有这样的权重，因此无法直接应用 AdaBoost 的采样方法。幸运的是 GBDT 中每个样本的梯度可以为我们的数据采样提供有用的信息。当一个样本具有较小的梯度时，其训练的误差也较小，表明其已经训练好了。一个直观的想法就是丢弃这些具有较小梯度的样本，但是这样操作会影响整个数据的分布，从而对模型的精度造成损失。

GOSS 的做法是保留具有较大梯度的样本，并从具有较小梯度的样本中随机采样。同时为了补偿对数据分布的影响，在计算信息增益的时候，GOSS 针对梯度较小的样本引入了一个常数乘子。这样就保证了模型更多的关注未得到较好训练的数据，同时又不会对原始数据分布改变过多。整个算法流程如下：

Exclusive Feature Bundling

高维数据往往是稀疏的，特征空间的稀疏性为我们提供了可能的近似无损的特征降维实现。进一步而言，在稀疏的特征空间中，很多特征之间是互斥的，也就是说它们不同时取非零值。因此，我们就可以将这些互斥的特征绑定成一个特征。由于 $bundle≪ feature$，因此构建直方图的复杂度就可以从 $O(data \times features)$ 减小至 $O(data \times bundle)$，从而在不损失精度的情况下加速模型的训练。这样我们就需要解决如下两个问题：

• 确定对哪些特征进行绑定。
• 如果对这些特征进行绑定。

对哪些特征进行绑定可以利用 图着色问题 进行解决。对于一个图 $G=(V,E)$，将 $G$ 的 关联矩阵 中的每一行看成特征，得到 $|V|$ 个特征，从而可以得出图中颜色相同的节点即为互斥的特征。算法如下：

上述算法的复杂度为 $O(feature^2)$ ，并且仅在模型训练前运行一次。对于特征数不是很大的情况是可以接受的，但当特征数量很大时算法效率并不令人满意。进一步的优化是在不构造图的情况下进行高效的排序，即根据非零值的数量进行排序，更多的非零值意味着更高的冲突概率。

合并特征的关键在于确保原始特征的值能够从合并后的特征之中识别出来。由于基于直方图的算法保存的是原始特征的离散桶，而非连续的值，因此我们可以将互斥的特征置于不同的桶内。算法如下：

EFB 算法可以将大量的互斥特征合并为少量的稠密特征，从而通过避免对零值特征的计算提高算法的运行效率。

PS：结合上面的模型和之前在总结神经网络章节补充内容中的正则化时，一些算法在解决稀疏性问题的时候往往可以用来作为特征工程中特征选取的功能！

Reference

• 《The Handbook of Brain Theory and Neural Network》

• Ensemble Learning to Improve Machine Learning Results

• Chen, T., & Guestrin, C. (2016). XGBoost: A Scalable Tree Boosting System. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 785–794).

• XGBoost Documentation — xgboost 1.4.0-SNAPSHOT documentation

• Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., … Liu, T.-Y. (2017). LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 30 (pp. 3146–3154).