Question

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

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

3. 提升树模型可以表示为决策树为基本学习器的加法模型： $ MathJax-Element-37 $ 。

   其中 ：

   • $ MathJax-Element-75 $ 表示第 $ MathJax-Element-227 $ 个决策树。
   • $ MathJax-Element-104 $ 为第 $ MathJax-Element-227 $ 个决策树的参数。
   • $ MathJax-Element-42 $ 为决策树的数量。

4. 提升树算法采用前向分步算法。

   • 首先确定初始提升树 $ MathJax-Element-70 $ 。

   • 第 $ MathJax-Element-44 $ 步模型为： $ MathJax-Element-76 $ 。其中 $ MathJax-Element-67 $ 为待求的第 $ MathJax-Element-227 $ 个决策树。

   • 通过经验风险极小化确定第 $ MathJax-Element-227 $ 个决策树的参数 $ MathJax-Element-104 $ ： $ MathJax-Element-50 $ 。

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

5. 不同问题的提升树学习算法主要区别在于使用的损失函数不同（设预测值为 $ MathJax-Element-51 $ ，真实值为 $ MathJax-Element-52 $ )：

   • 回归问题：通常使用平方误差损失函数： $ MathJax-Element-53 $ 。
   • 分类问题：通常使用指数损失函数： $ MathJax-Element-54 $ 。

1.1 算法

1. 给定训练数据集 $ MathJax-Element-79 $ ，其中 $ MathJax-Element-58 $ 为输入空间， $ MathJax-Element-57 $ 为输出空间。

   如果将输入空间 $ MathJax-Element-58 $ 划分为 $ MathJax-Element-59 $ 个互不相交的区域 $ MathJax-Element-60 $ ，并且在每个区域上确定输出的常量 $ MathJax-Element-61 $ ， 则决策树可以表示为： $ MathJax-Element-62 $

   其中：

   • 参数 $ MathJax-Element-63 $ 表示决策树的划分区域和各区域上的输出。
   • $ MathJax-Element-64 $ 是决策树的复杂度，即叶结点个数。

2. 回归问题中，提升树采用平方误差损失函数。此时：

   $ L(\tilde y,f_{m}(\mathbf {\vec x}))=L(\tilde y,f_{m-1}(\mathbf {\vec x})+h_m(\mathbf {\vec x};\Theta_m))\\ =(\tilde y-f_{m-1}(\mathbf {\vec x})-h_m(\mathbf {\vec x};\Theta_m))^{2}=(r-h_m(\mathbf {\vec x};\Theta_m))^{2} $

   其中 $ MathJax-Element-65 $ 为当前模型拟合数据的残差。

   所以对回归问题的提升树算法，第 $ MathJax-Element-227 $ 个决策树 $ MathJax-Element-67 $ 只需要简单拟合当前模型的残差。

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

4. 回归提升树算法：

   • 输入：训练数据集 $ MathJax-Element-79 $

   • 输出：提升树 $ MathJax-Element-81 $

   • 算法步骤：

     • 初始化 $ MathJax-Element-70 $

     • 对于 $ MathJax-Element-83 $

       • 计算残差： $ MathJax-Element-72 $ 。构建训练残差 ： $ MathJax-Element-73 $ 。
       • 通过学习一个回归树来拟合残差 $ MathJax-Element-74 $ ，得到 $ MathJax-Element-75 $ 。
       • 更新 $ MathJax-Element-76 $

     • 得到回归问题提升树： $ MathJax-Element-77 $ 。

1.2 GBT

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

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

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

   根据：

   $ L(\tilde y,f_{m}(\mathbf {\vec x}))=L(\tilde y,f_{m-1}(\mathbf {\vec x})+h_m(\mathbf {\vec x};\Theta_m)) =L(\tilde y,f_{m-1}(\mathbf {\vec x}))+\frac{\partial L(\tilde y,f_{m-1}(\mathbf {\vec x}))}{\partial f_{m-1}(\mathbf {\vec x})} h_m(\mathbf {\vec x};\Theta_m) $

   则有：

   $ \Delta L =L(\tilde y,f_{m}(\mathbf {\vec x}))-L(\tilde y,f_{m-1}(\mathbf {\vec x}))=\frac{\partial L(\tilde y,f_{m-1}(\mathbf {\vec x}))}{\partial f_{m-1}(\mathbf {\vec x})} h_m(\mathbf {\vec x};\Theta_m) $

   要使得损失函数降低，一个可选的方案是： $ MathJax-Element-78 $ 。

   • 对于平方损失函数，它就是通常意义上的残差。
   • 对于一般损失函数，它就是残差的近似 。

3. 梯度提升树用于分类模型时，是梯度提升决策树GBDT；用于回归模型时，是梯度提升回归树GBRT。

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

   • 输入：

     • 训练数据集 $ MathJax-Element-79 $
     • 损失函数 $ MathJax-Element-80 $

   • 输出：回归树 $ MathJax-Element-81 $

   • 算法步骤：

     • 初始化： $ MathJax-Element-82 $ 。

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

     • 对于 $ MathJax-Element-83 $

       • 对于 $ MathJax-Element-356 $ , 计算：

         $ r_{m,i}=-\left[\frac{\partial L(\tilde y_i,f(\mathbf{\vec x}_i))}{\partial f(\mathbf{\vec x}_i)}\right]_{f(\mathbf {\vec x})=f_{m-1}(\mathbf {\vec x})} $

       • 对 $ MathJax-Element-85 $ 拟合一棵回归树，得到第 $ MathJax-Element-227 $ 棵树的叶结点区域 $ MathJax-Element-87 $

       • 对 $ MathJax-Element-88 $ 计算每个区域 $ MathJax-Element-89 $ 上的输出值：

         $ c_{m,j}=\arg\min_c\sum_{\mathbf{\vec x}_i \in \mathbf R_{m,j}}L(\tilde y_i,f_{m-1}(\mathbf{\vec x}_i)+c) $

       • 更新 $ MathJax-Element-90 $

     • 最终得到回归树： $ MathJax-Element-91 $ 。

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

1.3 正则化

1. 在工程应用中，通常利用下列公式来更新模型： $ MathJax-Element-92 $ 。

   其中 $ MathJax-Element-246 $ 称作学习率。

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

   • 经验表明：一个小的学习率 ( $ MathJax-Element-94 $ ) 可以显著提高模型的泛化能力（相比较于 $ MathJax-Element-95 $ ) 。
   • 如果学习率较大会导致预测性能出现较大波动。

2. Freidman 从bagging 策略受到启发，采用随机梯度提升来修改了原始的梯度提升树算法。

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

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

   • 子集的占比 $ MathJax-Element-98 $ 是一个超参数，并且在每轮迭代中保持不变。

     • 如果 $ MathJax-Element-97 $ ，则与原始的梯度提升树算法相同。
     • 较小的 $ MathJax-Element-98 $ 会引入随机性，有助于改善过拟合，因此可以视作一定程度上的正则化。
     • 工程经验表明， $ MathJax-Element-99 $ 会带来一个较好的结果。

   • 这种方法除了改善过拟合之外，另一个好处是：未被采样的另一部分子集可以用来计算包外估计误差。

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

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

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

1.4 RF vs GBT

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

   • 梯度提升树GBT 为boosting 模型。
   • 随机森林RF 为bagging 模型。

2. 从偏差分解的角度来看：

   • 梯度提升树GBT 采用弱分类器（高偏差，低方差）。梯度提升树综合了这些弱分类器，在每一步的过程中降低了偏差，但是保持低方差。
   • 随机森林RF 采用完全成长的子决策树（低偏差，高方差）。随机森林要求这些子树之间尽可能无关，从而综合之后能降低方差，但是保持低偏差。

3. 如果在梯度提升树和随机森林之间二选一，几乎总是建议选择梯度提升树。

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

   • 梯度提升树的优点：

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

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

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

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