集成学习 - 《神经网络与深度学习》邱锡鹏

机器学习问题的两种优化策略：

• 尝试各种模型，选择其中表现最好的模型做重点调参优化
• 集成学习：将多个单独的分类器（基分类器）集成起来，融合这些模型的结果以做出最终的决策
  • eg. XGBoost：在 Kaggle 竞赛中所向披靡

1、集成学习的种类

问题一：集成学习分为哪几种？他们有何异同？

基分类器的错误：偏差 + 方差

• 偏差：分类器的表达能力有限导致的系统性错误，表现在训练误差不收敛
• 方差：训练样本数较少时，产生过拟合

两种集成学习方法：

• Boosting：
  • 训练基分类器时采用串行的方式，各个基分类器之间有依赖
  • 主要思想：迭代式学习
  • 算法实例：梯度提升决策树 GBDT（Gradient Boosting Decision Tree）
  • 基本思路：将基分类器层层叠加
    • 训练：对前一层基分类器分错的样本，赋予更高的权重
    • 测试：根据基分类器的结果的加权得到最终结果（stacking）
  • 通过逐步聚焦于基分类器分错的样本，减小集成分类器的偏差 （解决欠拟合问题）
• Bagging：
  • 训练基分类器时可以并行训练，各个基分类器之间无强依赖
  • 算法实例：基于决策树基分类器的随机森林
  • 主要思想：集体投票决策
  • 基本思路：
    • 训练：将训练集分为若干子集（可以有重叠），每个基分类器单独学习
    • 测试：每个基分类器单独作出判断，再通过投票的方式做出最后的集体决策（voting）
  • 通过对训练样本多次采样，并分别训练出多个不同的模型，然后做综合，减小集成分类器的方差 （解决过拟合问题）

2、集成学习的步骤和例子

问题一：集成学习有哪些基本步骤？请举几个集成学习的例子

集成学习的三个基本步骤：

1. 找到误差互相独立的基分类器：实际上，任何分类模型都可以作为基分类器，但树形模型由于结构简单且较易产生随机性所以比较常用
2. 训练基分类器：
3. 合并基分类器的结果：2 种方法
   • voting 投票：获得最多选票的结果作为最终的结果
   • stacking：用串行的方式，把前一个基分类器的结果输出到下一个分类器，将所有基分类器的输出结果相加（or 更复杂的融合算法，eg. 将各分类器的输出作为特征，使用逻辑回归作为融合模型进行最后的结果预测）作为最终的输出

集成学习的例子：

• Adaboost：
  • 确定基分类器：选用 ID3 决策树作为基分类器
  • 训练基分类器：
    • 从训练集种初始化采样分布
    • 迭代训练 T 个基分类器
      • 根据采样分布，采样出训练子集
      • 训练基分类器
      • 计算基分类器的错误率
      • 计算基分类器的权重（后续合并基分类器结果时的权重）
        • 错误率低的分类器的权重更大
      • 设置下一次采样分布
        • 对分类错误的样本保持 or 升高权重；对分类正确的样本降低权重
  • 合并基分类器：输出分类结果是将各个基分类器的结果进行加权，错误率低的分类器权重更大
• GBDT 梯度提升决策树：每一棵树学的是之前所有树结论和的残差（真实值 - 之前所有树的结论和）

3、基分类器

问：为什么很多集成模型都选择决策树作为基分类器？

问题一：常用的基分类器是什么

决策树：最常用的基分类器，有 3 点原因：

• 决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样的方法来调整样本权重
• 决策树的表达能力和泛化能力，可以通过调节树的层数来做折中
• 由于数据样本地扰动对于决策树的影响较大，不同子样本集合生成的决策树基分类器随机性就会较大，而这样的“不稳定学习器”更适合作为基分类器。并且，决策树节点分裂的时候，随机选择一个特征子集，从中找出最有分裂属性，很好地引入随机性

神经网络模型：也适合作为基分类器

• 神经网络模型也比较“不稳定”，因此适合作为基分类器
• 还可以通过调整神经元数量、连接方式、网络层数、初始权值等方式引入随机性

问题二：可否将随机森林中的基分类器，由决策树替换为线性分类器或 K-近邻？请解释为什么？

答：不可以

• 随机森林是 Bagging 类的集成学习
• Bagging 的主要优点是使得集成模型的方差比基分类器小，因此 Bagging 采用的基分类器最好是对样本分布较为敏感的（不稳定分类器）
• 而线性分类器 or K-近邻 都是较为稳定的分类器，本身方差就不大，用他们作为基分类器使用 Bagging 并不能在原基分类器的基础上得到更好的表现，反而可能因为 Bagging 的采样导致基分类器在训练中难以收敛，造成最后集成分类器的偏差增大

4、偏差与方差

问题一：什么是偏差和方差？

偏差-方差分解 - 《神经网络与深度学习》邱锡鹏

有监督学习中，模型的泛化误差来源于偏差和方差

• 偏差：由所有采样得到的大小为 m 的训练数据集训练出的所有模型的输出的平均值和真实模型输出之间的偏差
  • 通常是对学习算法做了错误假设导致的，可能模型过于简单，拟合能力不足，不能有效拟合（欠拟合）
• 方差：由所有采样得到的大小为 m 的训练数据集训练出的所有模型的输出的方差
  • 通常是由于模型的复杂度相对于训练样本数 m 过高导致的，过拟合，泛化能力不足

问题二：如何从减小偏差和方差的角度解释 Boosting 和 Bagging 的原理

Boosting 能提升弱分类器（基分类器）性能的原因是降低了偏差：

• 原因：Boosting 在训练好一个弱分类器后，需要计算该弱分类器的错误 or 残差，作为下一个分类器的输入。因此，这个过程本身就是在不断减小损失函数，使得模型不断逼近“靶心”，使得模型偏差不断降低
• 缺点：但是 Boosting 的过程并不会显著降低方差：因为 Boosting 的训练过程使得各弱分类器之间是强相关的，缺乏独立性

Bagging 能提升弱分类器性能的原因是降低了方差：

• 原因：Bagging（全称 Bootstrap Aggregating），意思是再抽样，然后在每个样本上训练出来的模型取平均。对 n 个独立不相关的模型的预测结果取平均，方差是原来单个模型的 1/n。当然模型之间不可能完全独立，因此 Bagging 追求基分类器之间的独立性，eg.：
  • 随机森林算法中，每次选取节点分裂属性时，会随机抽取一个属性子集，而不是从所有属性中选取最优属性，只是为了避免弱分类器之间过强的相关性
  • 训练集的重采样也能带来弱分类器之间的一定独立性

要综合考虑偏差和方差，选择合适复杂度的模型进行训练：

• 若模型复杂度过低，方差很小，但偏差很大
• 若模型复杂度过高，偏差降低，但方差会很高

5、梯度提升决策树 GBDT 的基本原理

梯度提升决策树 GBDT（Gradient Boosting Decision Tree）：属于 Boosting 算法的一种模型，体现了 Boosting 算法从错误中学习的理念，基于决策树预测的残差进行迭代的学习
Boosting 在每一轮的迭代中，基于已生成的弱分类器集合（即当前模型）的预测结果，新的弱分类器会重点关注那些还没有被正确预测的样本。

问题一：GBDT 的基本原理是什么？

GBDT：

• 使用的弱分类器是决策树 Decision Tree（通常为 CART），
• 融合的方法（训练方法）是梯度提升 Gradient Boosting

梯度提升 Gradient Boosting：

• 基本思想：根据当前模型损失函数的负梯度信息来训练新加入的弱分类器，然后将训练好的弱分类器以累加的形式结合到现有模型中
• 算法流程：每一轮迭代中：
  • 首先计算出当前模型在所有样本上的负梯度（伪残差）
  • 然后以该值为目标训练一个新的弱分类器进行拟合
  • 并计算出弱该分类器的权重，加权融合到现有模型中，实现对模型的更新

训练举例见书 p292

问题二：梯度提升和梯度下降的区别和联系是什么？

联系：

• 两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新

区别：

• 在梯度下降中：模型是以参数化形式表示，从而模型的更新等价于参数的更新
• 在梯度提升中：模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可使用的模型类型 | 梯度提升 | 函数空间 F |
  |
  | | —- | —- | —- | —- | | 梯度下降 | 参数空间 W |
  |
  |

问题三：GBDT 的优点和局限性有哪些？

GBDT 的优点：

• 预测阶段树与树之间可以并行化计算，计算速度快
• 在分布稠密的数据集上，泛化能力和表达能力都很好
• 采用决策树作为弱分类器使得 GBDT 模型具有较好的可解释性和鲁棒性，能够自动发现特征之间的高阶关系，并且也不需要对数据进行特殊的预处理，eg. 归一化等

GBDT 的缺点：

• 在高维稀疏的数据集上，表现不如支持向量机 or 神经网络
• 在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显
• 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度

6、XGBoost 和 GBDT 的联系和区别

GBDT 与 XGBoost 的区别和联系：

• GBDT 是机器学习算法，XGBoost 是 GBDT 算法的工程实现
• 在使用 CART 作为基分类器时，XGBoost 显式地加入了正则化项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力
  • 原始的 GBDT 算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝，而 XGBoost 在决策树构建阶段就加入了正则项 ，T 是决策树 的叶子节点个数， 是第 j 个叶子节点的预测值
  • XGBoost 构建第 t 棵基决策树时，损失函数为 ， 表示现有的 t- 1 棵数的最优解
• GBDT 在模型训练时只使用了代价函数的一阶导数信息，XGBoost 对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数
  • 对损失函数在 处进行二阶泰勒展开：
    • 
  • 通过令损失函数相对于 的导数为 0，可以求出在最小损失函数的情况下各叶子节点上的预测值
    • 但是从所有树结构中寻找最优的树结构是 NP-hard 问题，因此在实际中往往采用贪心法来构建出一个次优的树结构，基本思想是：从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根绝特定的准则选取最优的分裂
  • 将预测值 代入到损失函数中可求得损失函数的最小值
  • 因此，分裂前后损失函数的差值为
    • XGBoost 采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式
• 传统的 GBDT 采用 CART 作为基分类器，XGBoost 支持多种类型的基分类器，比如线性分类器
• 传统的 GBDT 在每轮迭代时使用全部的数据，XGBoost 则采用了与随机森林相似的策略，支持对数据进行采样
• 传统的 GBDT 没有设计针对缺失值进行处理，XGBoost 能够自动学习出缺失值的处理策略（将缺失值划分到默认方向）