机器学习 | XGBoost详解-机器学习 周志华 pdf

 

XGBoost（eXtreme Gradient Boosting）是基于Boosting框架的一个算法工具包（包括工程实现），在并行计算效率、缺失值处理、预测性能上都非常强大。本文参考其原始论文[1]，将主要从算法原理和工程实现方面介绍这一算法。

框架如下（终于发现了思维导图的用处...）

1.算法原理

1.1 目标函数的二阶泰勒展开

和GBDT一样，XGBoost是一个加法模型，在每一步迭代中只优化当前步中的子模型。 在第 mm 步中：

Fm(xi)=Fm−1(xi)+fm(xi)F_m(x_i)=F_{m-1}(x_i)+f_m(x_i) \\

fm(xi)f_m(x_i) 为当前步的子模型，Fm−1(xi)F_{m-1}(x_i) 为训练完已经固定了的前 m−1m-1 个子模型。

目标函数为经验风险+结构风险（正则项）：

Obj=∑i=1NL[Fm(xi),yi]+∑j=1mΩ(fj)(1)=∑i=1NL[Fm−1(xi)+fm(xi),yi]+∑j=1mΩ(fj)\begin{align*} Obj&=\sum_{i=1}^N L[F_{m}(x_i), y_i]+\sum_{j=1}^m \Omega (f_j) \\ &=\sum_{i=1}^N L[F_{m-1}(x_i)+f_m(x_i), y_i]+\sum_{j=1}^m \Omega (f_j) \tag{1} \end{align*}

其中，正则项 Ω(f)\Omega(f) 表示子模型 ff 的复杂度，与二阶泰勒展开无关，将在下一节具体展开。

泰勒公式是将一个在 x=x0x=x_0 处具有 nn 阶导数的函数 f(x)f(x) 利用关于 Δx=x−x0\Delta x=x-x_0 的 nn 次多项式来逼近 f(x)f(x) 的方法。XGBoost运用二阶展开来近似表达损失函数。

f(x0+Δx)≈f(x0)+f′(x0)Δx+f″(x0)2(Δx)2f(x_0+\Delta x) \approx f(x_0)+f^{}(x_0) \Delta x + \frac{f^{}(x_0)}{2} (\Delta x)^2 \\

式（1）中，将 Fm−1(xi)F_{m-1}(x_i) 视作 x0x_0 ，fm(xi)f_m(x_i) 视作 Δx\Delta x , L(yi^,yi)L(\hat{y_i},y_i) 视作关于 yi^\hat{y_i} 的函数，可得：

Obj=∑i=1N[L[Fm−1(xi),yi]+∂L∂Fm−1(xi)fm(xi)+12∂2L∂2Fm−1(xi)fm2(xi)]+∑j=1mΩ(fj)Obj = \sum_{i=1}^N \Big[ L[F_{m-1}(x_i),y_i] + \frac{\partial L}{\partial F_{m-1}(x_i)} f_m(x_i) + \frac{1}{2} \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)} f_m^2(x_i) \Big] +\sum_{j=1}^m \Omega (f_j) \\

前 m−1m-1 个子模型已经确定了，故上式中除了关于 fm(x)f_m(x) 的部分都是常数，不影响对 fm(x)f_m(x) 的优化求解。目标函数可转化为：

(2)Obj=∑i=1N[gifm(xi)+12hifm2(xi)]+Ω(fm)\begin{align*} Obj = \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\Omega (f_m) \tag{2} \end{align*}

其中

gi=∂L∂Fm−1(xi),hi=∂2L∂2Fm−1(xi)g_i = \frac{\partial L}{\partial F_{m-1}(x_i)} ,\ \ h_i = \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)} \\

这里的 LL 是损失函数，度量一次预测的好坏。在 Fm−1(x)F_{m-1}(x) 确定了的情况下，对每个样本点 ii 都可以轻易计算出一个 gig_i 和 hih_i.

1.2 基于树的正则化

XGBoost支持的基分类器包括决策树和线性模型，我们这里只讨论更常见的基于树的情况。为防止过拟合，XGBoost设置了基于树的复杂度作为正则项：

(3)Ω(f)=γT+12λ||w||2\Omega(f)=\gamma T + \frac{1}{2} \lambda ||w||^2 \tag{3}

TT 为树 ff 的叶节点个数，ww 为所有叶节点输出回归值构成的向量，||w||2||w||^2 为该向量L2范数（模长）的平方，γ,λ\gamma, \lambda 为超参数。作为回归树，叶子节点越多、输出的回归值

由（2）（3），目标函数如下：

Obj=∑i=1N[gifm(xi)+12hifm2(xi)]+γT+12λ∑j=1Twj2Obj = \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\

接下来通过一个数学处理，可以使得正则项和经验风险项合并到一起。经验风险项是在样本层面上求和，我们将其转换为叶节点层面上的求和。

定义节点 jj 上的样本集为 I(j)={xi|q(xi)=j}I(j)=\{x_i|q(x_i)=j\}，其中 q(xi)q(x_i) 为将样本映射到叶节点上的索引函数，叶节点 jj 上的回归值为 wj=fm(xi),i∈I(j)w_j=f_m(x_i),i \in I(j).

Obj=∑j=1T[(∑i∈I(j)gi)wj+12(∑i∈I(j)hi+λ)wj2]+γTObj = \sum_{j=1}^{T} \Big[ (\sum_{i\in I(j)} g_i) w_j + \frac{1}{2}(\sum_{i\in I(j)} h_i + \lambda) w_j^2 \Big] + \gamma T \\

进一步简化表达，令 ∑i∈I(j)gi=Gj\sum_{i\in I(j)} g_i=G_j , ∑i∈I(j)hi=Hj\sum_{i\in I(j)} h_i=H_j，注意这里G和H都是关于 jj 的函数：

Obj=∑j=1T[Gjwj+12(Hj+λ)wj2]+γTObj = \sum_{j=1}^{T} \Big[ G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2 \Big] + \gamma T \\

此时，若一棵树的结构已经确定，则各个节点内的样本 (xi,yi,gi,hi)(x_i,y_i,g_i,h_i) 也是确定的，即 GjG_j, Hj,TH_j, T 被确定，每个叶节点输出的回归值应该使得上式最小，由二次函数极值点：

wj∗=−GjHj+λw_j^*=-\frac{G_j}{H_j+\lambda} \\

按此规则输出回归值后，目标函数值也就是树的评分如下，越小代表树的结构越好。观察下式，树的评分也可以理解成所有叶节点的评分之和：

(4)Obj∗=∑j=1T(−12Gj2Hj+λ+γ)\begin{align*} Obj^* = \sum_{j=1}^T \Big( -\frac{1}{2}\frac{G_j^2}{H_j + \lambda} + \gamma \Big) \tag{4} \end{align*}

1.3 节点分裂准则

XGBoost的子模型树和决策树模型一样，要依赖节点递归分裂的贪心准则来实现树的生成。除此外，XGBoost还支持近似算法，解决数据量过大超过内存、或有并行计算需求的情况。

1.3.1 贪心准则

基本思路和CART一样，对特征值排序后遍历划分点，将其中最优的分裂收益作为该特征的分裂收益，选取具有最优分裂收益的特征作为当前节点的划分特征，按其最优划分点进行二叉划分，得到左右子树。

上图是一次节点分裂过程，很自然地，分裂收益是树A的评分减去树B的评分。由（4），虚线框外的叶节点，即非分裂节点的评分均被抵消，只留下分裂后的LR节点和分裂前的S节点进行比较，因此分裂收益的表达式为：

Gain=12[GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ]−γGain = \frac{1}{2} \Big[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} -\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\Big]-\gamma \\

1.3.2 近似算法

XGBoost还提供了上述贪心准则的近似版本，简言之，将特征分位数作为划分候选点。 这样将划分候选点集合由全样本间的遍历缩减到了几个分位数之间的遍历。

具体而言，特征分位数的选取有global和local两种可选策略：global在全体样本上的特征值中选取，在根节点分裂之前进行一次即可；local则是在待分裂节点包含的样本特征值上选取，每个节点分裂前都要进行。通常，global由于只能划分一次，其划分粒度需要更细。

在XGB原始论文中，作者在Higgs Boson数据集上比较了精确贪心准则、global近似和local近似三类配置的测试集AUC，用eps代表取分位点的粒度，如eps=0.25代表将数据集划分为1/0.25=4个buckets，发现global（eps=0.05）和local（eps=0.3）均能达到和精确贪心准则几乎相同的性能。

这三类配置在XGBoost包均有支持。

1.3.3 加权分位数

查看（2）式表示的目标函数，令偏导为0易得 fm∗(xi)=−gihif_m^*(x_i)=-\frac{g_i}{h_i}，此目标函数可理解为以 hih_i 为权重， −gihi-\frac{g_i}{h_i} 为标签的二次损失函数：

Obj=∑i=1N[gifm(xi)+12hifm2(xi)]+Ω(fm)=∑i=1N12hi[fm(xi)−(−gihi)]2+Ω(fm)+C\begin{align*} Obj &= \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\Omega (f_m) \\ &= \sum_{i=1}^N \frac{1}{2} h_i\Big[ f_m(x_i)-(-\frac{g_i}{h_i}) \Big]^2+\Omega (f_m) + C \end{align*} \\

因此，在近似算法取分位数时，实际上XGBoost会取以二阶导 hih_i 为权重的分位数（Weighted Quantile Sketch），如下图表示的三分位。

1.4 列采样和学习率

XGBoost还引入了两项特性：列采样和学习率。

列采样，即随机森林中的做法，每次节点分裂的待选特征集合不是剩下的全部特征，而是剩下特征的一个子集。是为了更好地对抗过拟合（我不是很清楚GBDT中列采样降低过拟合的理论依据。原文这里提到的动机是某GBDT的软件用户反馈列采样比行采样更能对抗过拟合），还能减少计算开销。

学习率，或者叫步长、shrinkage，是在每个子模型前（即在每个叶节点的回归值上）乘上该系数，削弱每颗树的影响，使得迭代更稳定。可以类比梯度下降中的学习率。XGBoost默认设定为0.3。

1.5 稀疏感知

缺失值应对策略是算法需要考虑的。特征稀疏问题也同样需要考虑，如部分特征中出现大量的0或干脆是one-hot encoding这种情况。XGBoost用稀疏感知策略来同时处理这两个问题：概括地说，将缺失值和稀疏0值等同视作缺失值，再将这些缺失值“绑定”在一起，分裂节点的遍历会跳过缺失值的整体。这样大大提高了运算效率。

0值在XGB中被处理为数值意义上的0还是NA，不同平台上的默认设置不同，可参考本处。总的来说需要结合具体平台的设置，预处理区分开作为数值的0（不应该被处理为NA）和作为稀疏值的0（应该被处理为NA）。

分裂节点依然通过遍历得到，NA的方向有两种情况，在此基础上对非缺失值进行切分遍历。或者可以理解NA被分到一个固定方向，非缺失值在升序和降序两种情况下进行切分遍历。

如上图所示，若某个特征值取值为1,2,5和大量的NA，XGBoost会遍历以上6种情况（3个非缺失值的切分点 × 缺失值的两个方向），最大的分裂收益就是本特征上的分裂收益，同时，NA将被分到右节点。

2.工程优化

2.1 并行列块设计

XGBoost将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量 gi,hig_i,h_i 对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。

2.2 缓存访问

特征值排序后通过索引来取梯度 gi,hig_i,h_i 会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，XGBoost为每个线程分配一个单独的连续缓存区，用来存放梯度信息。

2.3 核外块计算

数据量过大时，不能同时全部载入内存。XGBoost将数据分为多个blocks并储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。为了进一步提高磁盘读取数据性能，XGBoost还使用了两种方法：一是通过压缩block，用解压缩的开销换取磁盘读取的开销；二是将block分散储存在多个磁盘中，有助于提高磁盘吞吐量。

3.和GBDT的比较

性质：GBDT是机器学习算法，XGBoost除了算法内容还包括一些工程实现方面的优化。

基于二阶导：GBDT使用的是损失函数一阶导数，相当于函数空间中的梯度下降；而XGBoost还使用了损失函数二阶导数，相当于函数空间中的牛顿法。[2]

正则化：XGBoost显式地加入了正则项来控制模型的复杂度，能有效防止过拟合。

列采样：XGBoost采用了随机森林中的做法，每次节点分裂前进行列随机采样。

缺失值处理：XGBoost运用稀疏感知策略处理缺失值，而GBDT没有设计缺失策略。

并行高效：XGBoost的列块设计能有效支持并行运算，提高效率。

参考资料

[1] XGBoost: A Scalable Tree Boosting System: https://arxiv.org/pdf/1603.02754.pdf

[2] wepon GBDT PPT: http://wepon.me/files/gbdt.pdf

[3] 阿泽：【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）