XGBoost(eXtreme Gradient Boosting)，由华盛顿大学计算机系博士陈天奇开创，是一个具有可扩展性的基于树提升算法的机器学习系统。我们习惯称它为XGB算法，该算法在训练过程中通过输入含有特征集和目标值Y的样本，生成一个集成树模型，该模型会对每个样本进行打分作为y的预测值，这里Y既可为数值型，也可以是分类型，也就是说回归预测和分类预测XGB都支持。

既然是集成树模型，不得不提该类模型的两大流派boosting和Bagging，XGB属于前者，因为XGB只能在一棵基树（弱分类器）建好之后才能建下一棵，后面的树建立会依赖前面树。一个模型可能有成百上千棵基树构成，每个样本在每棵基树上都会得到一个分数，n棵树就有n个得分，然后将这n个得分相加就得到了XGB模型对每个样本的预测打分yhat。

那么XGB模型是怎样训练出来的呢，只要搞懂两个关键问题，一个是模型如何从开始只含有一棵树到最终训练成由成百上千个基树组成的模型，一个是每一棵基树是如何建立的。前者指的是模型如何迭代，后者指的是基模型如何构建。

首先看第一个问题。XGB每次迭代都会增加一棵新的基树，新基树通过拟合前面迭代模型对样本的预测值与真实值之间的残差来构建。第1次迭代后模型只有1棵树，第2次迭代模型有2棵树，第n次迭代模型就有n棵基树。比方说某个样本的y值为100分，第n次迭代出的模型预测其为60分，距离100分差了40分，差了很远，就需要加入新的树进行迭代，而新树就是以40分为预测目标，假设新树建立好之后预测为30分，则第n+1次模型的预测值为60+30=90分，逐渐靠近真实分数100。这就是XGB模型迭代的大致过程，也是为什么前面说各个树之前会存在依赖关系。

当然迭代的过程需要构建数学模型来实现，一个模型的构建离不开构造目标函数，XGB的目标函数是在损失函数的基础上加上了衡量模型复杂度的正则化项，前者反映模型的偏差，而后者反映模型的方差。其中，损失函数度量的是预测值与真实值的差异程度，形式不固定，不过后面会讲到需要满足一阶和二阶可导；而正则化项和树的叶子数量、叶子权重有关。模型迭代的过程也就是求解目标函数最优解的过程，这其中就有对目标函数的不断化简处理，包括泰勒二阶展开近似和将样本扫描转化为叶子节点扫描这两种关键方法，最后能将求解一个抽象模型变成了求解一元二次方程的问题（极值理论），而最优解对应的目标函数值我们称之为模型的结构分数，这个结构分数可以判断一棵树构建的有多好，对应的分数计算过程也会用到损失函数的一阶和二阶求导值。

这样，我们对从一棵树的生长过程，到多棵树如何集成为XGB模型就有个认识了。不过模型构建只是XGB的一部分，它最有特点的地方其实是工程上的应用，有很多巧妙的并行计算等设计。这是不是与我们之前介绍过的SynchroTrap系统的设计思路有异曲同工之妙呢。

至此，想必我们对XGB已经有了全局的认识，接下来就要结合数学公式进行说明了。

1.XGB是由k个基模型组成的一个加法模型

以上表示第   个样本   的预测值   ，是将   在各个基模型   上得到的   个预测打分进行相加得到。XGB的基模型不仅支持分类树，还支持线性模型。

l项代表损失函数，即表示模型预测值和真实值的差异程度。函数形式可自定义，常见的损失函数有平方损失函数和逻辑回归损失函数，不过需要一阶和二阶可导（后面有解释）。Ω 项是将   个基模型的复杂度进行求和，将其添加到目标函数中，可抑制模型过拟合，其具体形式后面会介绍。 

目标函数很抽象，要化简。基于前向加法性质，以第   步模型为例，XGB模型对第   个样本 的预测为：

其中，
是第   步的模型给出的预测值，是个常数（注意这里的第   步模型其实是包含多个基模型的），
是我们这次需要加入的新基模型。代入   函数后，第t步模型的目标函数可表示为：

最优化目标函数的过程，相当于求解每一步的 。以基模型为决策树为例，XGB每次迭代都会构建一颗新的决策树，决策树通过预测前面树的预测与真实值之间的残差来构建，至于残差怎么体现在公式里后面会解释。

但是 ，还是很抽象，没法解啊，继续化简。

a. 泰勒化简

直接不好求可以想办法近似啊，泰勒
公式就是一个用函数在某点的信息逼近其附近取值的公式。根据Taylor公式，我们把函数   在
点   处
二阶
展开，可得到：
仔细瞅瞅目标函数中圈红的部分。
对应到上面二阶展开的泰勒公式中
，
 
在
应于我们的损失函
数
，   对应于前   棵树的预测
值，
 对应于我们正在训练的第   棵树（的预测值）。那么有：
其中
是损失函数
的一阶导数， 
是损失函数
的二阶导， 注意这里的求导是对
求导。
这里我们以平方损失函数为例：

由于前一步的
是已知的， 项，   和   都是可以计算出来的，都是常数。这样左边公式中唯一的变量就是 ，就可以通过最优化目标函数，得到每一步的  ，最后根据加法模型得到一个整体模型。

b. 结构化简

嗯 还
是看不懂…树没法建起来，继续化简。以基模型为决策树为例，需要将样本x映射到一个相对应的叶子节点才可以。

通过决策树遍历样本，其实就是在遍历叶子节点，因为样本最终会落在叶子节点上，叶子节点的值就是对样本的预测值，只不过一个叶子上可能有多个样本。因此可以遍历叶子节点，然后获取叶子节点上的样本集合，最后再求损失函数。这样就能把决策树模型定义成
, 其中
代表了该样本在哪个叶子节点上，
表示该叶子节点上的权重（即得分）。所以
就代表了每个样本的取值（预测得分），
而
 

 
为
第   个叶子节点的样本集合。
这里给出了Ω的表达式。决策树的复杂度可由叶子数T组成，叶子节点越少模型越简单，此外叶子节点也不应该含有过高的权重w（类比LR的每个变量的权重），所以可把正则项定义为：

为简化表达式，我们定义   
， 
 
，如   
表示叶子结点 
 所包含样本的一阶偏导数累加之和，是一个常量。
则目标函数最终化简为：

这里要注意   和   是前   步得到的结果，其值已知，只有最后一棵树的叶子节点 的值不确定。

这不就是求一元二次方程的极值点吗，初中的公式想起来没有？其实就是将目标函数对
求一阶导，并令其等于0，就能得到最优解下叶子节点   对应的权值。

代入后，目标函数又可以进行化简：
这个就是基于决策树的XGB目标函数的最终版本了。
上面的
代表了当指定一个树的结构的时候，在目标上最多能够减少多少。建立一个树不就是让残差尽可能的小吗，到底小多少呢？这个
就是衡量这个的，把它称为结构分数。类似于基尼系数那样对树结构打分的一个函数。

obj计算示例

btw. 对于目标函数
，实际上其各个叶子节点下的目标函数子式（如下）是相互独立的，也就是说   和   
是已知的，当每个叶子结点的子式都达到最值点时，整个目标函数   
才
达到最值点。

结构分数可以判断出来一棵树究竟好不好，那么树要怎么建立起来？一棵树的结构近乎无限多，总不能一个一个去测算它们的好坏程度吧。当建立一棵树时，一个非常关键的问题是如何找到叶子节点的最优切分点，其实就是就是应该在哪个特征的哪个点上进行分裂，XGB支持两种分裂节点的方法，贪心算法和近似算法。

a. 贪心算法

即遍历所有特征以及所有分割点，每次选最好的那个。
在分裂一个特征节点时，我们会有很多个候选分割点，寻找最佳分割点的步骤为：

1. 从树的深度为0开始，对每个叶节点枚举所有的可用特征
2. 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益（每个特征的收益计算是可以并行处理的）
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集（如果出现缺失值，XGB会先把它放到左子树上计算一下收益，再放到右边计算计算下，哪个大就把它放到哪棵树上）
4. 回到第1步，递归执行到满足特定条件为止

那么每个特征的分裂收益该如何计算呢？比如ID3使用信息增益，C4.5计算信息增益比和CART计算基尼系数。XGB使用的是分裂前后的结构分数之差，来衡量每个特征点上分裂之后的收益，btw这个收益也可作为特征重要性输出的重要依据。
分裂前：

分裂后：

分裂后的收益为：
普通的决策树在切分的时候并不考虑树的复杂度，所以才有了后续的剪枝操作，而XGB在切分的时候就已经考虑了树的复杂度（那个γ），所以不需要进行单独的剪枝操作。

b. 分位点近似算法

贪心算法可以得到最优解，但每次分类都要枚举所有特征可能的分割方案，当数据量太大时无法读入内存进行计算，而近似算法可以给出接近最优解。近似法对每个特征按照特征值排序后，采用类似分位点选取的方式，仅仅选出有限的特征值作为该特征的候选切分点，然后基于这些候选切分点把相应的样本放入对应的桶中，对每个桶的进行计算。在提出候选切分点时有两种策略：

• Global：学习每棵树前就提出候选切分点，并在每次分裂时都采用这种。

• Local：每次分裂前将重新提出候选切分点。直观上来看，Local策略需要更多的计算步骤，而Global策略会需要更多的候选点以覆盖每次分裂要求。

实验发现在候选点数取值合理的情况下，分位数策略可以获得与贪心算法相同的精度。

三分位示例

实际上，XGB是想让loss在左右子树上分布的均匀一些，而不是样本数量的均匀，因为每个样本对降低loss的贡献可能不一样，所以不是简单地按照样本个数找出分位点，而是以二阶导数值   作为样本的权重进行划分。为了处理带权重的候选切分点的选取，作者提出了Weighted Quantile Sketch算法，即加权分位数略图算法。

样本带h权重的三分位示例

这里
 
 
就是前面说的损失函数在样本
处的二阶导数。但是为啥它就能代表样本对降低loss的贡献程度？
我们知道模型的目标函数为：

前面说过XGB的迭代会聚焦在残差上面，但是单看目标函数的话并没有找到残差的身影，我们再对损失函数进行变形试试（loss项为常数项，迭代过程可忽略）：

BTW. XGB引入了二阶导之后，相当于在模型降低残差的时候给各个样本根据贡献度不同加入了一个权重，这样就能更好的加速拟合和收敛，GBDT只用到了一阶导数，这样只知道梯度大的样本降低残差效果好，梯度小的样本降低残差不好，但是好与不好的这个程度，在GBDT中无法展现，而XGB就通过二阶导可以展示出来，这样模型训练的时候就有数了。

至于如何分箱(桶)也比较简单，还是以上面三分位为例，计算出所有样本的总贡献度为1.8，每个箱的贡献度就是0.6了，在基于   排序好的的样本对   累加计算，就能找到这些样本要分到三个箱中的哪个箱了。

此外，xgb通过稀疏感知算法可以处理缺省值，比如数据缺失、one-hot编码都会造成输入数据稀疏。XGB在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时（或者指定缺省值），可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。其归类方法也很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

6.通过收缩率系数让模型学习过程更平滑（模型预测）
图中每一次迭代得到的新模型前面有个
（让树的叶子节点权重乘以这个系数），叫做收缩率，加入它的目的是削弱每棵树的作用，让后面有更大的学习空间。也就是，我不完全信任每一个残差树，每棵树只学到了模型的一部分，希望通过更多棵树的累加来来弥补，让这个学习过程更平滑，而不会出现陡变。和正则化防止过拟合的原理不一样，这里是削弱模型的作用，而正则化是控制模型本身的复杂度。

7.XGB的工程实现

a. 列块并行学习

在树生成过程中，最耗时的一个步骤就是在每次寻找最佳分裂点时都需要对特征的值进行排序。XGB在训练之前，预先对每个特征按照特征值大小进行排序，然后保存为block结构，在块里面保存排序后的特征值及对应样本的引用，后面的迭代中会重复地使用这个结构，使计算量大大减小。由于各个特性已预先存储为block结构，XGB支持利用多个线程并行地计算每个特征的最佳分割点，即获取样本的一阶、二阶导数值计算收益，提升节点的分裂速度的同时，也极利于大规模训练集的适应性扩展。

b. 缓存访问

列块并行学习的设计可以减少节点分裂时的计算量，在顺序访问特征值时，访问的是一块连续的内存空间，但通过特征值持有的索引（样本索引）访问样本获取一阶、二阶导数时，这个访问操作访问的内存空间并不连续，这样可能造成cpu缓存命中率低，影响算法效率。为此，XGB提出了缓存访问算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就实现了非连续空间到连续空间的转换，提高了算法效率。此外适当调整块大小，也可以有助于缓存优化。

c. “核外”块计算

当数据量非常大时，不能把所有数据都加载到内存中，就必须将一部分数据先存到硬盘中，需要时再加载进内存。这样操作也有瓶颈，即硬盘的IO操作速度远远低于内存的处理速度，会存在大量等待硬盘IO操作的情况。为此作者提出了”核外”计算方法，将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存中，这样算法在内存中处理数据就可以和从硬盘读取数据同时进行。此外，XGB还用了块压缩和块分区两种方法来降低硬盘读写的开销。

8.XGBoost的优缺点

• 精度更高：GBDT只用到一阶泰勒展开，而XGB对损失函数进行了二阶泰勒展开，二阶泰勒展开也可近似大量损失函数。
• 灵活性更强：GBDT以CART作为基分类器，XGB除了CART还支持线性分类器。此外，XGB支持自定义损失函数，只需函数支持一阶和二阶可求导。
• 正则化：XGB在目标函数中加入了正则项，用于控制模型的复杂度，抑制过拟合。正则项里包含了树的叶子节点个数，叶子节点权重的L2范式。这也是优于传统GBDT的一个方面。
• Shrinkage（缩减）： 相当于学习速率。主要是为了削弱每棵树的影响，让后面有更大的学习空间，让学习过程更加平缓，GBDT也有这一点。
• 列抽样：XGB借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。
• 缺失值处理：对于特征的值有缺失的样本，XGB采用的稀疏感知算法可以自动学习出它的分裂方向。
• XGB支持并行：XGB的并行是在特征粒度上的。决策树的学习最耗时的一个步骤就是确定最佳分割点，XGB在训练之前，预先对数据进行排序并将其保存为block结构，后面的迭代中可以重复使用这个结构。这个block结构也使得并行成为了可能，在进行节点的分裂时，各个特征的增益计算就可以开多线程进行。

• 可并行的近似算法：树节点在进行分裂时，除了使用贪心法来枚举计算每个特征的分类收益，XGB提出了一种可并行的分位数近似算法，用于高效地生成候选的分割点。

b. 缺点

• 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集。

9.参考文献

• xgboost论文原文：https://arxiv.org/pdf/1603.02754.pdf
• 深入理解XGBoost

• 【白话机器学习】算法理论+实战之Xgboost算法

题图来源：网站Pexels

THE END