title: "从提升树到 XGBoost, 原理简介" categories:
提升树是以分类树或回归树为基本分类器的提升方法, 模型表示为决策树的加法模型:
$$ FM(x) = \sum{m=0}^M f(x;\Theta_m), $$
其中 $M$ 为树的个数, $f(x;\Theta_m)$ 表示决策树, $\Theta_m$ 为其参数.
<!-- more -->提升树算法采用向前分步 (forward stagewise) 算法 (本质上是一种贪心算法). 对于训练数据集 $D = \{(x_i, yi)\}{i=1}^N$, 首先确定初始提升树 $F_0(x)=0$, 然后第 $m$ 步的模型是
$$ Fm(x) = F{m-1}(x) + f(x;\Theta_m), $$
其中 $F_{m-1}$ 为当前模型, 通过经验风险最小化确定下一颗决策树的参数,
$$ \hat\Thetam = \operatorname*{argmin}{\Theta}\sum_{i=1}^N l(yi, F{m-1}(x_i) + f(x_i;\Theta)), $$
其中 $l$ 为损失函数.
回归问题的提升树可以表示为简单函数
$$ f(x;\Theta) = \sum_{j=1}^T wj 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$ 为叶节点个数.
综上,
回归问题的提升树算法
- 初始化 $F_0(x) = 0$.
- 对 $m = 1,\dots,M$:
(a) 通过经验风险最小化学习一个回归树 $f(x;\Theta_m)$.
(b) 更新 $Fm(x) = F{m-1}(x) + f(x;\Theta_m)$.- 输出回归问题提升树 $FM(x) = \sum{m=1}^M f(x;\Theta_m)$.
对于一般的损失函数, 每一步经验风险最小化都不容易. GBDT 是为了便于计算而提出的方法, 它的主要想法来自于梯度下降法.
记损失函数的梯度在当前模型的值为
$$ g_{im} = \left(\frac{\partial l(y_i,F(x_i))}{\partial F(xi)}\right){F = F_{m-1}}. $$
则由梯度下降法,
$$ F_m(xi) = F{m-1}(x_i) -\rhom g{im}, $$
其中步长 $\rho_m$ 可以事先固定 (比如为 1), 也可以通过线搜索获得, 即
$$ \rhom = \operatorname*{argmin}{\rho} \sum_{i=1}^Nl(yi, F{m-1}(xi)-\rho g{im}). $$
梯度下降法是一个很贪心的算法, 即在当前点取函数下降最快的方向. 但如上这样做的话我们只获得了在训练数据点上的预测, 为了得到可以预测新数据的决策树, 一种可行的做法是, 用 $f$ 逼近负梯度方向, ESL p. 359 使用了平方误差来度量 $f$ 与负梯度的距离, 即
$$ \tilde\Thetam = \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$ 相等.
其余操作同提升树算法, 从略.
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 来降低过拟合风险, 即 $Fm = F{m-1} + \nu f_m$, 其中 $0<\nu<1$, 可以看为学习率 (就是上面提到的步长), 原来的做法相当于取 $\nu=1$. 这么做主要的理由是减少每颗树对总模型的影响, 防止前几颗树拟合地太好 (过拟合) 以至于后面的树没有了学习空间.
对目标函数做二阶 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)
扔掉第一个常数项, 记 $I_j = \{i: x_i\in R_j\}$ 表示被归到第 $j$ 个叶节点的全体实例 (的脚标) 集合, 则右边写为
$$ \sum{j=1}^T \left[ \left(\sum{i\in I_j} g_i \right) wj + \frac12 \left(\sum{i\in I_j} h_i + \lambda\right) w_j^2 \right] + \gamma T, $$
注意到 $h_i>0$ 可以保证二阶项系数为正, 可得最优权重为
$$ wj^\ast = -\frac{\sum{i\in I_j}gi}{\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}gi)^2}{\sum{i\in I_L} hi + \lambda} + \frac{(\sum{i\in I_R}gi)^2}{\sum{i\in I_R} hi + \lambda} - \frac{(\sum{i\in I}gi)^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}gi$, $H \leftarrow \sum{i\in I}h_i$
for $k=1$ to $d$ do
$G_L \leftarrow 0$, $HL \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}$) 那步), 取适当的分位数作为分裂候选点进行贪心算法.
主要分为两种情况:
注: 按照原论文的说法, 作者似乎把缺失和稀疏时的 0 都统称为 "稀疏/缺失", 用同样的方式处理, [5] 也证实了这一点.
图中 $m$ 应该为 $d$, score 应该为 gain. 据论文作者所言, 这是一种新颖的处理稀疏数据的方法, 而且效果很好 (事实上这并不是什么新颖的方法).
首先关于之前讲的 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 在处理多分类时比较菜.
2020/10/14
一般原则: 对同一优先级的参数, 先粗粒度调整, 决定了最优值后再细粒度调整.
- It is difficult to get a very big leap in performance by just using parameter tuning or slightly better models.
- A significant jump can be obtained by other methods like feature engineering, creating ensemble of models, stacking, etc.