提升树

一、提升树

  1. 提升树boostring tree是以决策树为基本学习器的提升方法。它被认为是统计学习中性能最好的方法之一。

  2. 对分类问题,提升树中的决策树是二叉决策树;对回归问题,提升树中的决策树是二叉回归树。

  3. 提升树模型可以表示为决策树为基本学习器的加法模型:

    其中 :

    • 表示第 个决策树。
    • 为第 个决策树的参数。
    • 为决策树的数量。
  4. 提升树算法采用前向分步算法。

    • 首先确定初始提升树

    • 步模型为: 。其中 为待求的第 个决策树。

    • 通过经验风险极小化确定第 个决策树的参数

      这里没有引入正则化,而在xgboost 中会引入正则化。

  5. 不同问题的提升树学习算法主要区别在于使用的损失函数不同(设预测值为 ,真实值为 ):

    • 回归问题:通常使用平方误差损失函数:
    • 分类问题:通常使用指数损失函数:

1.1 算法

  1. 给定训练数据集 ,其中 为输入空间, 为输出空间。

    如果将输入空间 划分为 个互不相交的区域 ,并且在每个区域上确定输出的常量 , 则决策树可以表示为:

    其中:

    • 参数 表示决策树的划分区域和各区域上的输出。
    • 是决策树的复杂度,即叶结点个数。
  2. 回归问题中,提升树采用平方误差损失函数。此时:

    其中 为当前模型拟合数据的残差。

    所以对回归问题的提升树算法,第 个决策树 只需要简单拟合当前模型的残差。

  3. 不仅是回归提升树算法,其它的boosting 回归算法也是拟合当前模型的残差。

  4. 回归提升树算法:

    • 输入:训练数据集

    • 输出:提升树

    • 算法步骤:

      • 初始化

      • 对于

        • 计算残差: 。构建训练残差 :
        • 通过学习一个回归树来拟合残差 ,得到
        • 更新
      • 得到回归问题提升树:

1.2 GBT

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

    当损失函数是一般函数时,往往每一步优化不是很容易。针对这个问题,Freidman提出了梯度提升算法。

  2. 梯度提升树GBT 是利用最速下降法的近似方法。其关键是利用损失函数的负梯度在当前模型的值作为残差的近似值,从而拟合一个回归树。

    根据:

    则有:

    要使得损失函数降低,一个可选的方案是:

    • 对于平方损失函数,它就是通常意义上的残差。
    • 对于一般损失函数,它就是残差的近似 。
  3. 梯度提升树用于分类模型时,是梯度提升决策树GBDT;用于回归模型时,是梯度提升回归树GBRT

  4. 梯度提升回归树算法GBRT

    • 输入:

      • 训练数据集
      • 损失函数
    • 输出:回归树

    • 算法步骤:

      • 初始化:

        它是一颗只有根结点的树,根结点的输出值为:使得损失函数最小的值。

      • 对于

        • 对于, 计算:

        • 拟合一棵回归树,得到第 棵树的叶结点区域

        • 计算每个区域 上的输出值:

        • 更新

      • 最终得到回归树:

  5. 梯度提升决策树算法GBDTGBRT类似,主要区别是GBDT的损失函数与GBRT的损失函数不同。

1.3 正则化

  1. 在工程应用中,通常利用下列公式来更新模型:

    其中 称作学习率。

    学习率是正则化的一部分,它可以降低模型更新的速度(需要更多的迭代)。

    • 经验表明:一个小的学习率 () 可以显著提高模型的泛化能力(相比较于 ) 。
    • 如果学习率较大会导致预测性能出现较大波动。
  2. Freidmanbagging 策略受到启发,采用随机梯度提升来修改了原始的梯度提升树算法。

    • 每一轮迭代中,新的决策树拟合的是原始训练集的一个子集(而并不是原始训练集)的残差。

      这个子集是通过对原始训练集的无放回随机采样而来。

    • 子集的占比 是一个超参数,并且在每轮迭代中保持不变。

      • 如果 ,则与原始的梯度提升树算法相同。
      • 较小的 会引入随机性,有助于改善过拟合,因此可以视作一定程度上的正则化。
      • 工程经验表明, 会带来一个较好的结果。
    • 这种方法除了改善过拟合之外,另一个好处是:未被采样的另一部分子集可以用来计算包外估计误差。

      因此可以避免额外给出一个独立的验证集。

  3. 梯度提升树会限制每棵树的叶子结点包含的样本数量至少包含 个样本,其中 为超参数。在训练过程中,一旦划分结点会导致子结点的样本数少于 ,则终止划分。

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

1.4 RF vs GBT

  1. 从模型框架的角度来看:

    • 梯度提升树GBTboosting 模型。
    • 随机森林RFbagging 模型。
  2. 从偏差分解的角度来看:

    • 梯度提升树GBT 采用弱分类器(高偏差,低方差)。梯度提升树综合了这些弱分类器,在每一步的过程中降低了偏差,但是保持低方差。
    • 随机森林RF 采用完全成长的子决策树(低偏差,高方差)。随机森林要求这些子树之间尽可能无关,从而综合之后能降低方差,但是保持低偏差。
  3. 如果在梯度提升树和随机森林之间二选一,几乎总是建议选择梯度提升树。

    • 随机森林的优点:天然的支持并行计算,因为每个子树都是独立的计算。

    • 梯度提升树的优点:

      • 梯度提升树采用更少的子树来获得更好的精度。

        因为在每轮迭代中,梯度提升树会完全接受现有树(投票权为1)。而随机森林中每棵树都是同等重要的(无论它们表现的好坏),它们的投票权都是 ,因此不是完全接受的。

      • 梯度提升树也可以修改从而实现并行化。

      • 梯度提升树有一个明确的数学模型。因此任何能写出梯度的任务,都可以应用梯度提升树(比如 ranking 任务)。而随机森林并没有一个明确的数学模型。

二、xgboost

  1. xgboost 也是使用与提升树相同的前向分步算法。其区别在于:xgboost 通过结构风险极小化来确定下一个决策树的参数

    其中:

    • 为第 个决策树的正则化项。这是xgboostGBT的一个重要区别。
    • 为目标函数。
  2. 定义:

    即:

    • 的一阶导数。
    • 的二阶导数。

    对目标函数 执行二阶泰勒展开:

    提升树模型只采用一阶泰勒展开。这也是xgboostGBT的另一个重要区别。

  3. 对一个决策树 ,假设不考虑复杂的推导过程,仅考虑决策树的效果:

    • 给定输入 ,该决策树将该输入经过不断的划分,最终划分到某个叶结点上去。
    • 给定一个叶结点,该叶结点有一个输出值。

    因此将决策树拆分成结构部分 ,和叶结点权重部分 ,其中 为叶结点的数量。

    • 结构部分 的输出是叶结点编号 。它的作用是将输入 映射到编号为 的叶结点。
    • 叶结点权重部分就是每个叶结点的值。它的作用是输出编号为 的叶结点的值

    因此决策树改写为:

2.1 结构分

  1. 定义一个决策树的复杂度为:

    其中: 为叶结点的个数; 为每个叶结点的输出值; 为系数,控制这两个部分的比重。

    • 叶结点越多,则决策树越复杂。
    • 每个叶结点输出值的绝对值越大,则决策树越复杂。

    该复杂度是一个经验公式。事实上还有很多其他的定义复杂度的方式,只是这个公式效果还不错。

  2. 将树的拆分、树的复杂度代入 的二阶泰勒展开,有:

    对于每个样本 ,它必然被划分到树 的某个叶结点。定义划分到叶结点 的样本的集合为: 。则有:

  3. 定义 :

    • 刻画了隶属于叶结点 的那些样本的一阶偏导数之和。
    • 刻画了隶属于叶结点 的那些样本的二阶偏导数之和。

    偏导数是损失函数 关于当前模型的输出 的偏导数。

    则上式化简为:

    假设 与 与 无关,对 求导等于0,则得到:

    忽略常数项,于是定义目标函数为:

  4. 在推导过程中假设 与 与 无关,这其实假设已知树的结构。

    事实上 是与 相关的,甚至与树的结构相关,因此定义 为结构分。

    结构分刻画了:当已知树的结构时目标函数的最小值。

2.2 分解结点

  1. 现在的问题是:如何得到最佳的树的结构,从而使得目标函数全局最小。

2.2.1 贪心算法

  1. 第一种方法是对现有的叶结点加入一个分裂,然后考虑分裂之后目标函数降低多少。

    • 如果目标函数下降,则说明可以分裂。
    • 如果目标函数不下降,则说明该叶结点不宜分裂。
  2. 对于一个叶结点,假如给定其分裂点,定义划分到左子结点的样本的集合为: ;定义划分到右子结点的样本的集合为: 。则有:

  3. 定义叶结点的分裂增益为:

    其中:

    • 表示:该叶结点的左子树的结构分。
    • 表示:该叶结点的右子树的结构分。
    • 表示:如果不分裂,则该叶结点本身的结构分。
    • 表示:因为分裂导致叶结点数量增大1,从而导致增益的下降。

    每次分裂只一个叶结点,因此其它叶结点不会发生变化。因此:

    • ,则该叶结点应该分裂。
    • ,则该叶结点不宜分裂。
  4. 现在的问题是:不知道分裂点。对于每个叶结点,存在很多个分裂点,且可能很多分裂点都能带来增益。

    解决的办法是:对于叶结点中的所有可能的分裂点进行一次扫描。然后计算每个分裂点的增益,选取增益最大的分裂点作为本叶结点的最优分裂点。

  5. 最优分裂点贪心算法:

    • 输入:

      • 数据集 ,其中样本
      • 属于当前叶结点的样本集的下标集合
    • 输出:当前叶结点最佳分裂点。

    • 算法:

      • 初始化:

      • 遍历各维度:

        • 初始化:

        • 遍历各拆分点:沿着第 维 :

          • 如果第 维特征为连续值,则将当前叶结点中的样本从小到大排序。然后用 顺序遍历排序后的样本下标:

          • 如果第 维特征为离散值 ,设当前叶结点中第 维取值 样本的下标集合为 ,则遍历

      • 选取最大的 对应的维度和拆分点作为最优拆分点。

  6. 分裂点贪心算法尝试所有特征和所有分裂位置,从而求得最优分裂点。

    当样本太大且特征为连续值时,这种暴力做法的计算量太大。

2.2.2 近似算法

  1. 近似算法寻找最优分裂点时不会枚举所有的特征值,而是对特征值进行聚合统计,然后形成若干个桶。

    然后仅仅将桶边界上的特征的值作为分裂点的候选,从而获取计算性能的提升。

  2. 假设数据集 ,样本

    对第 个特征进行分桶:

    • 如果第 个特征为连续特征,则执行百分位分桶,得到分桶的区间为: ,其中

      分桶的数量、分桶的区间都是超参数,需要仔细挑选。

    • 如果第 个特征为离散特征,则执行按离散值分桶,得到的分桶为: ,其中 为第 个特征的所有可能的离散值。

      分桶的数量 就是所有样本在第 个特征上的取值的数量。

  3. 最优分裂点近似算法:

    • 输入:

      • 数据集 ,其中样本
      • 属于当前叶结点的样本集的下标集合
    • 输出:当前叶结点最佳分裂点。

    • 算法:

      • 对每个特征进行分桶。 假设对第 个特征上的值进行分桶为:

        如果第 个特征为连续特征,则要求满足

      • 初始化: