XGBoost: A Scalable Tree Boostin

1. 背景

在深度学习崛起之前年代，决策树因为其分段函数的性质，对数据有较好的拟合程度且能够直接控制过拟合的程度，在各项机器学习比赛中表现良好。作者对各类决策树算法进行了深入的研究和总结，在addtive tree模型的基础上进行了抽象和改写。并对实现过程进行了数据结构设计、多核并行计算、支持分布式的优化。最终推出了一个风靡全比赛届的开源库，xgboost，并在各项比赛中获得了令人瞩目的佳绩。

2. 公式理论基础

2.1 addtive tree理论基础

XGboost是基于addtive tree的理论基础（也就是gbdt那一系列）进行推演的，其基础理论如下：

image.png 其中， image.png
是预测结果， image.png
是迭代到第k步之后的整个模型（所有k个决策树的累加和），fk是第k棵决策树。addtive tree判断分类时是要把所有的树的预测结果加到一起，判断是否大于0.5，而不是投票。比如adaboost的预测是把每棵树的预测结果乘以加权系数再累加。gbdt是每棵树的预测结果直接相加。这部分的原理网上博客很多，本篇主要介绍的是xgboost，gbdt的原理不再赘述。

2.2 XGBoost理论公式

那么按照机器学习一般的思路，定义目标函数由两部分组成：损失函数和正则化项：

image.png

其中：损失函数可以自由定义，交叉熵或者MSE都行，只要是便于优化的凸函数（n阶可导的那种）就好。而xgboost对正则化项的定义，参考了RGF的正则，还得便于并行化，其具体公式如下：

image.png

其中T是叶子节点的个数，γ是一个超参数，控制叶节点个数。w是叶节点的值（也叫score），加平方控制项（也就是L2正则），λ同样是超参数。

2.3 XGBoost的求解推导

有了理论公式简单，那么如何进行求解呢？以下是求解过程。

对于第t步的迭代来说，我们把 image.png
写成 image.png
。那么目标函数如下： image.png

把y_t看做自变量x的话，f_t(x_i)就相当于△x，那么我们对损失函数l(x)进行二阶泰勒展开可以得到（这个步骤可以类比GBDT中对损失函数进行的一阶泰勒展开）：

image.png

其中gi是损失函数l的一阶导数，hi是损失函数l的二阶导数：

image.png image.png

这两个函数都是可以根据我们自己定义的损失函数而求解出具体数值来的，可以看做是常数。

在第t步迭代中t-1步之前的决策树都是已知具体形式和值的，可以视作常数，在目标函数中移除。目标函数写成如下形式：

image.png

定义I_j ={i|q(x_i) = j}，I是个指示函数，样本x_i满足I的条件q（）即为第j个叶节点。也就是意味着把样本的特征x_i带入到第t轮的决策树f_t（）中可以得到的叶节点值w_j。

image.png image.png

因为我们要求的是第t轮决策树ft，那么这颗树的结构和叶节点值都是未知的。这里把这个w_j看做未知数，利用二元函数求极值的公式可以得到：

image.png

也就是说，在已知树结构的情况下，我们知道样本特征值，直到会落到哪个节点上的话，该节点的值就是w_j^*，才能使得目标函数最小。

将w_j^*代回原式，就得到目标函数的最小值：

image.png

这个式子可以在迭代过程中标志我们决策树的质量，控制迭代轮数和树的生成。

那么，如何才能的得到树的最佳结构呢？正常来说，我们是无法穷举每一种树结构的。所以就像cart树，c4.5那些决策树一样，我们使用贪心策略来建树。每步都找一个能使目标函数更小的划分。

image.png

这样，我们就有了建树策略，也就是得到了第t轮迭代的建树规则：就是生成一个目标函数最小的树。这个建树过程就很像id3/C4.5那样普通的决策树了，只是衡量节点划分的标准不同而已。

那么选择节点就有两种策略：贪心策略和比例划分策略：

image.png image.png

2.4 XGbbost其他防止过拟合的措施

1. 到这里来说，理论上讲，必须把每棵树的预测结果加到一起才能得到最终预测，那么第t棵树预测的还是“残差”。这一点跟gbdt很像，因为两者的理论基础公式是一样的。所以xgboost还参考Friedman的理论，引入了收缩系数的概念来进一步阻止过拟合，就是每步预测的目标不是残差，而是部分残差，也就是说得到第t轮的决策树f_t之后，我的预测函数不是直接加上f_t的预测值，而是加上一个收缩系数f_t ·shrankage ，可以为后来的决策树留下更多的空间。

2. 在每棵树的建树过程中，仿照随机森林的做法，采用部分采样的方式进行决策树的构建，增加随机性。

到这里，其实就已经从理论上实现了完整的xgboost的算法，其分类结果应该和开源库的效果一样。但是没有考虑并行化、数据结构、数据稀疏性等非常具体的问题，计算速度会差很多。

3. XGBoost的并行化策略

其实到了这一步，就已经没什么机器学习算法的东西了，剩下的都是加快计算的规则和技巧。对机器学习代码实现不感兴趣的同学已经可以关了。

3.1 贪心策略

贪心策略就是先把特征值排序，然后逐点划分，看看哪一个可以得到最优分割点。

3.2 按比例划分策略

贪心策略虽然简单，但是面对大数据量和并行化计算的需要有些力不从心，所以作者查阅文献，总结出两套按比例划分的策略：一次划分策略和多次划分策略。

一次划分策略就是直接划分。多次划分策略就是先进行一次粗划分，然后再从粗划分的基础进行二次划分。一般来说多次划分所需枚举的节点数要少于一次划分，而且效果要比一次划分好。而作者决定对这两种策略都进行实现上的支持。

3.3 xgboost的按比例划分规则

为了确保划分节点之后的左右两部分节点有较好的区分性，作者提出了一个仅从特征值和label值来进行区分的计算系数：

image.png

这个r_k(z)表示特征值小于z的label之和占总label之和的比例。也就是说，我们希望划分的那个节点可以有效的把label值分成两个不同的部分。把节点排序为{sk1; sk2; · · · skl}，那么我们可以给定一个限度ε，来控制划分点。

image.png

ε越小，划分节点就越多，划分之后每个部分的label值就越接近一些。不过吧，其实根据每轮的“残差”不同，每轮的目标函数就不太一样，那么每个样本对于目标函数的贡献值其实是不一样的。我们可以把最初的目标函数变成这个形式：

image.png

也就是说，每个样本对目标函数的贡献大致正比于hi，所以我们可以根据这个性质，对节点划分进行加权，权重就是hi的值。关于加权之后节点划分是否总能得到最优解，这部分的理论推导在另一篇文献中http://homes.cs.washington.edu/~tqchen/pdf/xgboost-supp.pdf。感兴趣的小伙伴可以看一下（我已经跪了，不打算看这篇证明了）。

3.4 数据稀疏性问题的解决

数据稀疏性问题的来源很多啊，比如：

1. 数据本身就是缺失的。

2. 统计时本来就有很多0值

3. 特征工程中独热向量产生的0值

必须对这些大量稀疏的0值进行处理，以减少在无效数据上的计算资源浪费，加快计算进程。作者用了一个非常简单的策略啊，因为事先对特征值进行了排序，所以我们可以选择把所有空缺值（或0值）全部放在二叉树的左节点或者右节点，直接进行判断哪种放置更好。

image.png

这种操作避免了在0值中来回遍历和节点划分，有效的提高了计算效率。作者拿了一份数据进行对比：

image.png

4. 数据结构设计

4.1 为并行化而设计的列存储

因为算法中需要进行按特征值大小顺序进行划分的操作，所以需要频繁的排序操作。如果不对排序的结果进行存储的话，会导致很多重复操作。已经对稀疏性进行处理的情况下，其算法的复杂度大致为：

image.png

其中k代表决策树个数，d代表树的深度，|X|₀代表非零值的个数，n代表样本数（在比例划分算法中代表后选划分点的个数）。

而如果对排序好的结果进行存储的话，就只需要进行一次排序，乘法就变成了加法。其时间复杂度为：

image.png

所以这个对排序结果的存储非常重要，作者设计了列存储的数据结构，并且存入之前要先进行排序。其大致结构如下：

image.png

4.2 缓存设计

为了减少排序的时间复杂度，我们设计了数据按特征值列存储，但是这样就造成每列所特征值都存了一个index，再由index去找其他的属性。这样就会拖慢计算过程。在数据量较大的情况下，我们又不可能一次性将所有数据加载到内存中，还可能产生内存不命中。为了解决这个问题，作者为贪心策略和比例划分策略设计了两种不同的办法。

贪心策略来说，作者使用预读取策略，因为累加是分为多线程进行（mini-batch），所以预读取也是多线程，各自预读取各自需要统计的数据，有点类似前端的双缓冲绘图的意思。

比例划分策略来说，除了多线程预读取，还需要考虑块的大小问题，快太小就不能充分的并行，块太大就会导致内存不命中。作者尝试了不同的块，结果如下：

image.png

最后决定用2¹⁶作为块的大小，所以这其实是个经验值啦。

4.3 核外计算的块设计

所谓的核外计算（out-of-core computation）就是利用除了内存和CPU之外的资源进行计算。作者主要用了两个方法来进行：

1. 块压缩：因为数据存储是经过压缩的，那么由一个独立线程进行解压的时候就可以进行一部分计算，这样就减少了数据遍历和读盘的次数。

2. 块分片：当磁盘有多个片的时候，多线程读取数据可以充分利用多个磁盘片，然后训练线程从读取线程中交替读取得到的数据。以达到增加磁盘io效率的目的。

5. 总结

到这里，XGBoost就已经介绍完了。像很多论文一样，作者提出了改进思路，设计了计算代码，对计算过程进行了优化。更棒的是，作者还公开了这份代码，做成了一个通用的端到端的优化方案，惠及广大机器学习玩家。作为一个只能读大佬论文的菜逼，我非常感谢作者的贡献。