7.梯度提升树 - 一、提升树 - 《AI算法工程师手册》

一、提升树

提升树boostring tree是以决策树为基本学习器的提升方法。它被认为是统计学习中性能最好的方法之一。
对分类问题，提升树中的决策树是二叉决策树；对回归问题，提升树中的决策树是二叉回归树。
提升树模型可以表示为决策树为基本学习器的加法模型：。

其中：
- 表示第个决策树。
- 为第个决策树的参数。
- 为决策树的数量。
提升树算法采用前向分步算法。
- 首先确定初始提升树。
- 第步模型为：。其中为待求的第个决策树。
- 通过经验风险极小化确定第个决策树的参数：。
  
  这里没有引入正则化，而在xgboost 中会引入正则化。
不同问题的提升树学习算法主要区别在于使用的损失函数不同（设预测值为，真实值为 )：
- 回归问题：通常使用平方误差损失函数：。
- 分类问题：通常使用指数损失函数：。

提升树中，当损失函数是平方损失函数和指数损失函数时，每一步优化都很简单。因为平方损失函数和指数损失函数的求导非常简单。

当损失函数是一般函数时，往往每一步优化不是很容易。针对这个问题，Freidman提出了梯度提升算法。
梯度提升树GBT 是利用最速下降法的近似方法。其关键是利用损失函数的负梯度在当前模型的值作为残差的近似值，从而拟合一个回归树。

根据：

则有：

要使得损失函数降低，一个可选的方案是：。
- 对于平方损失函数，它就是通常意义上的残差。
- 对于一般损失函数，它就是残差的近似。
梯度提升树用于分类模型时，是梯度提升决策树GBDT；用于回归模型时，是梯度提升回归树GBRT。
梯度提升回归树算法GBRT：
- 输入：
  - 训练数据集
  - 损失函数
- 输出：回归树
- 算法步骤：
  - 初始化：。
    
    它是一颗只有根结点的树，根结点的输出值为：使得损失函数最小的值。
  - 对于
    - 对于, 计算：
    - 对拟合一棵回归树，得到第棵树的叶结点区域
    - 对计算每个区域上的输出值：
    - 更新
  - 最终得到回归树：。
梯度提升决策树算法GBDT与GBRT类似，主要区别是GBDT的损失函数与GBRT的损失函数不同。

在工程应用中，通常利用下列公式来更新模型：。

其中称作学习率。

学习率是正则化的一部分，它可以降低模型更新的速度（需要更多的迭代）。
- 经验表明：一个小的学习率 () 可以显著提高模型的泛化能力（相比较于 ) 。
- 如果学习率较大会导致预测性能出现较大波动。
Freidman 从bagging 策略受到启发，采用随机梯度提升来修改了原始的梯度提升树算法。
- 每一轮迭代中，新的决策树拟合的是原始训练集的一个子集（而并不是原始训练集）的残差。
  
  这个子集是通过对原始训练集的无放回随机采样而来。
- 子集的占比是一个超参数，并且在每轮迭代中保持不变。
  - 如果，则与原始的梯度提升树算法相同。
  - 较小的会引入随机性，有助于改善过拟合，因此可以视作一定程度上的正则化。
  - 工程经验表明，会带来一个较好的结果。
- 这种方法除了改善过拟合之外，另一个好处是：未被采样的另一部分子集可以用来计算包外估计误差。
  
  因此可以避免额外给出一个独立的验证集。
梯度提升树会限制每棵树的叶子结点包含的样本数量至少包含个样本，其中为超参数。在训练过程中，一旦划分结点会导致子结点的样本数少于，则终止划分。

这也是一种正则化策略，它会改善叶结点的预测方差。

从模型框架的角度来看：
- 梯度提升树GBT 为boosting 模型。
- 随机森林RF 为bagging 模型。
从偏差分解的角度来看：
- 梯度提升树GBT 采用弱分类器（高偏差，低方差）。梯度提升树综合了这些弱分类器，在每一步的过程中降低了偏差，但是保持低方差。
- 随机森林RF 采用完全成长的子决策树（低偏差，高方差）。随机森林要求这些子树之间尽可能无关，从而综合之后能降低方差，但是保持低偏差。
如果在梯度提升树和随机森林之间二选一，几乎总是建议选择梯度提升树。
- 随机森林的优点：天然的支持并行计算，因为每个子树都是独立的计算。
- 梯度提升树的优点：
  - 梯度提升树采用更少的子树来获得更好的精度。
    
    因为在每轮迭代中，梯度提升树会完全接受现有树（投票权为1）。而随机森林中每棵树都是同等重要的（无论它们表现的好坏），它们的投票权都是，因此不是完全接受的。
  - 梯度提升树也可以修改从而实现并行化。
  - 梯度提升树有一个明确的数学模型。因此任何能写出梯度的任务，都可以应用梯度提升树（比如 ranking 任务）。而随机森林并没有一个明确的数学模型。