从提升树到 XGBoost, 原理简介

| ~ |

提升树是以分类树或回归树为基本分类器的提升方法, 模型表示为决策树的加法模型:

\[F_M(x) = \sum_{m=0}^M f(x;\Theta_m),\]

其中 $M$ 为树的个数, $f(x;\Theta_m)$ 表示决策树, $\Theta_m$ 为其参数.

1. 提升树算法

提升树算法采用向前分步 (forward stagewise) 算法 (本质上是一种贪心算法). 对于训练数据集 $D = \{(x_i, y_i)\}_{i=1}^N$, 首先确定初始提升树 $F_0(x)=0$, 然后第 $m$ 步的模型是

\[F_m(x) = F_{m-1}(x) + f(x;\Theta_m),\]

其中 $F_{m-1}$ 为当前模型, 通过经验风险最小化确定下一颗决策树的参数,

\[\hat\Theta_m = \operatorname*{argmin}_{\Theta}\sum_{i=1}^N l(y_i, F_{m-1}(x_i) + f(x_i;\Theta)),\]

其中 $l$ 为损失函数.

回归问题的提升树可以表示为简单函数

\[f(x;\Theta) = \sum_{j=1}^T w_j 1_{R_j}(x),\]

其中 $R _ j$ 互不相交, $1 _ {R _ j}(x)$ 为示性函数, 当 $x\in R _ j$ 时为 1 否则为 0, $w _ j$ 为常数, 参数 $\Theta=\{(R _ j,w _ j)\} _ {j=1}^T$, $T$ 为叶节点个数.

综上,

回归问题的提升树算法

  1. 初始化 $F_0(x) = 0$.
  2. 对 $m = 1,\dots,M$:
    (a) 通过经验风险最小化学习一个回归树 $f(x;\Theta_m)$.
    (b) 更新 $F_m(x) = F_{m-1}(x) + f(x;\Theta_m)$.
  3. 输出回归问题提升树 $F_M(x) = \sum_{m=1}^M f(x;\Theta_m)$.

2. 梯度提升树 (Gradient Boosting Decision Trees)

对于一般的损失函数, 每一步经验风险最小化都不容易. GBDT 是为了便于计算而提出的方法, 它的主要想法来自于梯度下降法.

记损失函数的梯度在当前模型的值为

\[g_{im} = \left(\frac{\partial l(y_i,F(x_i))}{\partial F(x_i)}\right)_{F = F_{m-1}}.\]

则由梯度下降法,

\[F_m(x_i) = F_{m-1}(x_i) -\rho_m g_{im},\]

其中步长 $\rho_m$ 可以事先固定 (比如为 1), 也可以通过线搜索获得, 即

\[\rho_m = \operatorname*{argmin}_{\rho} \sum_{i=1}^Nl(y_i, F_{m-1}(x_i)-\rho g_{im}).\]

梯度下降法是一个很贪心的算法, 即在当前点取函数下降最快的方向. 但如上这样做的话我们只获得了在训练数据点上的预测, 为了得到可以预测新数据的决策树, 一种可行的做法是, 用 $f$ 逼近负梯度方向, ESL p. 359 使用了平方误差来度量 $f$ 与负梯度的距离, 即

\[\tilde\Theta_m = \operatorname*{argmin}_{\Theta}\sum_{i=1}^N (-g_{im} - f(x_i;\Theta))^2.\]

注意到对于 $l(x,y) = \frac12(x-y)^2$ 的情形, $\tilde\Theta_m$ 与 $\hat\Theta_m$ 相等.

其余操作同提升树算法, 从略.

3. XGBoost

3.1. 总体框架

XGBoost 的主要想法是, 除了原有的损失函数, 在目标函数中加入正则项, 利用二阶 Taylor 近似代替损失函数再极小化目标函数, 其余操作同提升树算法. 回忆之前的梯度提升树只用了一阶导数, 想法是来自梯度下降, 而梯度下降的想法来自用一阶 Taylor 展开近似, XGB 中的 ‘GB’ 由此而来; 而 X 是指 extreme, 指的是 XGB 相比以前的 GB 算法性能有了极大的提升.

记

\[\begin{align*} F_m(x_i) &= \hat y_i^{(m)},\\ \hat y_i^{(0)} &= 0,\\ \hat y_i^{(m)} &= \hat y_i^{(m-1)} + f_m(x_i), \quad m=1,\dots,M. \end{align*}\]

同前, $f_m$ 表示第 $m$ 轮时所得的树, 是由最小化目标函数而得; $\hat y_i^{(m)}$ 表示第 $m$ 轮时 $y_i$ 的预测值.

第 $m$ 轮目标函数为

\[\mathrm{Obj}^{(m)} = \sum_{i=1}^N l\left(y_i, \hat y_i^{(m-1)} + f_m(x_i)\right) + \Omega(f_m),\]

其中 $l$ 为损失函数; $\Omega$ 为正则项, 是人为定义的复杂度, 可以降低模型复杂度, 减小过拟合的风险, 在原论文中定义为

\[\Omega(f) = \gamma T + \frac12 \lambda\sum_{j=1}^T w_j^2,\]

其中 $\gamma$, $\lambda$ 为参数, $T$ 为 $f$ 表示的树的叶节点数, $w_j$ 为第 $j$ 个叶节点的预测值 (权重).

除了加入正则项外, 还可以通过 shrinkage 来降低过拟合风险, 即 $F_m = F_{m-1} + \nu f_m$, 其中 $0<\nu<1$, 可以看为学习率 (就是上面提到的步长), 原来的做法相当于取 $\nu=1$. 这么做主要的理由是减少每颗树对总模型的影响, 防止前几颗树拟合地太好 (过拟合) 以至于后面的树没有了学习空间.

3.2. 寻找分裂点

对目标函数做二阶 Taylor 展开, 略去更高阶的无穷小量. 记

\[g_i = \frac{\partial l(y_i, \hat y_i^{(m-1)})}{\partial{\hat y^{(m-1)}}},\quad h_i = \frac{\partial^2 l(y_i, \hat y_i^{(m-1)})}{\partial{\left(\hat y^{(m-1)}\right)^2}}.\]

例如对于平方损失函数 $(y_i - \hat y_i^{(m-1)})^2$ 来说, $g_i = 2(\hat y_i^{(m-1)} - y_i)$, $h_i = 2$.

展开

\[\mathrm{Obj}^{(m)} \approx \sum_{i=1}^N \left( l\left(y_i, \hat y_i^{(m-1)}\right) + g_i f_m(x_i) + \frac12 h_i f_m^2(x_i) \right) + \Omega(f_m),\]

扔掉第一个常数项, 记 $I_j = \{i: x_i\in R_j\}$ 表示被归到第 $j$ 个叶节点的全体实例 (的脚标) 集合, 则右边写为

\[\sum_{j=1}^T \left[ \left(\sum_{i\in I_j} g_i \right) w_j + \frac12 \left(\sum_{i\in I_j} h_i + \lambda\right) w_j^2 \right] + \gamma T,\]

注意到 $h_i>0$ 可以保证二阶项系数为正, 可得最优权重为

\[w_j^\ast = -\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j} h_i + \lambda}.\]

一般而言, 穷举所有可能的树结构是不可能的, 作为代替, 我们考虑贪心算法. 从一个叶节点开始二分, 假设 $I_L$ 和 $I_R$ 分别表示分裂后归为左节点和右节点的实例集合, 记 $I = I_L \cup I_R$, 则易得分裂后的目标函数减少值 (loss reduction) 为

\[\frac12\left[\frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L} h_i + \lambda} + \frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R} h_i + \lambda} - \frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I} h_i + \lambda}\right] - \gamma\]

把上式第一项视为 gain, 则 $\gamma$ 相当于设置了分裂所需的最小的 gain, 起到了剪枝的作用.

寻找分裂点的精确贪心算法 (原论文中本段有一些 typo)
输入: $I$, 当前节点的实例集; $d$, 特征维数 (个数).
初始化 $\mathrm{gain} \leftarrow 0$
$G \leftarrow \sum_{i\in I}g_i$, $H \leftarrow \sum_{i\in I}h_i$
for $k=1$ to $d$ do
     $G_L \leftarrow 0$, $H_L \leftarrow 0$
     for $j$ in sorted ($I$, by $x_{jk}$) do
         $G_L\leftarrow G_L + g_j$, $H_L\leftarrow H_L + h_j$
         $G_R \leftarrow G-G_L$, $H_R \leftarrow H- H_L$
         $\mathrm{gain} \leftarrow \max(\mathrm{gain}, \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda})$
输出: 最大 gain 的分裂

精确贪心法是在所有特征上, 对所有可能的分裂点都进行遍历, 在数据量大的时候是不现实的. 一个简单的近似方法是, 排序后 (for $j$ in sorted ($I$, by $x_{jk}$) 那步), 取适当的分位数作为分裂候选点进行贪心算法.

3.3. 稀疏数据的分裂点寻找 (sparsity-aware)

主要分为两种情况:

  1. 若数据有缺失值, 则把缺失值都归到同一个节点 (即所谓默认方向, 把缺失值统一归到左子节点或右子节点). 这是处理缺失值的常用方法之一 (另一种常用方法是用适当的方法填补缺失值), 这使得 XGB 可以直接训练和预测带有缺失值的数据.
  2. 若数据稀疏 (比如 one-hot 编码, 使得数据包含大量的 0), 则把 0 当做缺失值处理. 这个做法的关键点在于遍历时只对非缺失 (非零) 数据遍历, 在稀疏数据的情况下会大大提高训练速率.

注: 按照原论文的说法, 作者似乎把缺失和稀疏时的 0 都统称为 “稀疏/缺失”, 用同样的方式处理, [5] 也证实了这一点.

来自原论文

图中 $m$ 应该为 $d$, score 应该为 gain. 据论文作者所言, 这是一种新颖的处理稀疏数据的方法, 而且效果很好 (事实上这并不是什么新颖的方法).

3.4. XGB 的优点

  • XGB 把决策树的许多启发式的想法通过最小化目标函数统一起来处理.
  • 除了使用近似算法, 在系统设计上, 通过并行处理, 优化缓存等技术, 大幅提高了运行速度. 我认为工程方面才是 XGB 比较关键的贡献.

3.5. 处理多分类

首先关于之前讲的 GBDT, 强烈推荐阅读 1.11. Ensemble methods — scikit-learn 0.23.2 documentation, 写得特别清楚.

多分类时训练的依旧是回归树. 比如有 $K$ 个类, 那么 one-hot encoding 成 $K$ 维向量, 每轮迭代训练 $K$ 个树, 得出 $K$ 个值分别对应那 $K$ 维, 然后照常拟合. 每个类的概率为 $\mathrm{softmax}(F_M(x_i))$.

所以 GBDT 在处理多分类时比较菜.

4. 调参

2020/10/14

一般原则: 对同一优先级的参数, 先粗粒度调整, 决定了最优值后再细粒度调整.

  1. 先固定较高的学习率, 然后决定最优的迭代次数.
    • learning_rate (float) – Boosting learning rate (xgb’s “eta”).
    • n_estimators (int) – Number of gradient boosted trees. Equivalent to number of boosting rounds. 迭代次数
  2. 调节模型复杂度
    • max_depth (int) – Maximum tree depth for base learners.
    • min_child_weight (float) – Minimum sum of instance weight (hessian) needed in a child.
    • gamma (float) – Minimum loss reduction required to make a further partition on a leaf node of the tree. 预剪枝
  3. 加入噪声
    • subsample (float) – Subsample ratio of the training instance.
    • colsample_bytree (float) – Subsample ratio of columns when constructing each tree.
  4. 调节正则化参数
    • reg_alpha (float (xgb’s alpha)) – L1 regularization term on weights.
    • reg_lambda (float (xgb’s lambda)) – L2 regularization term on weights.
  5. 降低学习率, 再调整迭代次数.
  1. It is difficult to get a very big leap in performance by just using parameter tuning or slightly better models.
  2. A significant jump can be obtained by other methods like feature engineering, creating ensemble of models, stacking, etc.

5. References