监督学习集成模型——XGBoost

一、XGBoost原理

XGBoost的全称为eXtreme Gradient Boosting，即极度梯度提升树，由陈天奇在其论文“XGBoost: A Scalable Tree Boosting System：https://arxiv.org/pdf/1603.02754.pdf

中提出，一度因其强大性能流行于各大数据竞赛，在各种顶级解决方案中屡见不鲜。

XGBoost本质上仍属于GBDT算法，但在算法精度、速度和泛化能力上均要优于传统的GBDT算法。

• 从算法精度上来看，XGBoost通过将损失函数展开到二阶导数，使得其更能逼近真实损失；


• 从算法速度上来看，XGBoost使用了加权分位数sketch和稀疏感知算法这两个技巧，缓存优化和模型并行来提高算法速度；


• 从算法泛化能力上来看，通过对损失函数加入正则化项、加性模型中设置缩减率和列抽样等方法，来防止模型过拟合。

二、XGBoost基本原理

既然XGBoost整体上仍属于GBDT算法系统，那么XGBoost也一定是由多个基模型组成的一个加性模型，所以XGBoost可表示为：

\(y ̂_i=∑_{k=1}^K f_k(x_i)\)

根据前向分步算法，假设第t次迭代的基模型为\(f_t(x)\)，有：

$y ̂_i(t)=∑_{k=1}^t y ̂_i(t−1)+f_t(x_i) $

XGBoost损失函数由经验损失项和正则化项构成：

$L=∑_{i=1}^nl(y_i,y ̂_i)+∑_{i=1}^t Ω(f_i) $

其中\(∑_{i=1}^n l(y_i,y ̂_i)\)为经验损失项，表示训练数据预测值与真实值之间的损失；\(∑_{i=1}^tΩ(f_i)\)为正则化项，表示全部t棵树的复杂度之和，这也是XGBoost控制模型过拟合的方法。

根据前向分步算法，以第t步模型为例，假设模型对第i个样本\(x_i\)的预测值为：

\(y ̂_i (t)=y ̂_i (t−1)+f_t(x_i)\)

其中，\(y ̂_i(t−1)\)是由第t−1步的模型给出的预测值，其作为一个已知常量存在，\(f_t(x_i)\)为第t步树模型的预测值。

所以，损失函数可以改写为：

\(L(t)=∑_{i=1}^n l(y_i,y ̂_i(t))+∑_{i=1}^t Ω(f_i)\)

\(=∑_{i=1}^n l(y_i,y ̂_i(t−1)+f_t(x_i))+∑_{i=1}^tΩ(f_i)\)

$=∑_{i=1}nl(y_i,y ̂_i(t−1)+f_t(x_i))+Ω(f_t)+Constant $

上式对正则化项进行了拆分，因为前t−1棵树的结构已经确定，所以前t−1棵树的复杂度之和也可以表示为常数：

$∑_{i=1}^t Ω(f_i)=Ω(f_t)+∑_{i=1}^t−1Ω(f_i) =Ω(f_t)+Constant $

然后针对损失函数式前半部分\(l(y_i,y ̂_i(t−1)+f_t(x_i))\)，使用二阶泰勒展开式，这里需要用到函数的二阶导数，相应的损失函数经验损失项可以改写为：

\(l(y_i,y ̂_i(t−1)+f_t(x_i))=l(y_i,y ̂_i(t−1))+g_if_t(x_i)+\frac{1}{2}ℎ_if_t^2(x_i)\)

其中，\(g_i\)为损失函数一阶导数，\(ℎ_i\)为损失函数二阶导数，需要注意的是，这里是对\(y ̂_i (t−1)\)求导。

XGBoost相较于GBDT的一个最大的特点就是用到了损失函数的二阶导数信息，所以当自定义或者选择XGBoost损失函数时，需要其二阶可导。将的损失函数二阶泰勒展开式代入，可得损失函数的近似表达式：

$L(t)≈∑_{i=1}^n[l(y_i,y ̂_i (t−1))+g_if_t(x_i)+\frac{1}{2}ℎ_if_t^2(x_i)]+Ω(f_t)+Constant $

去掉常数项后，上式可简化为：\(L^(t)≈∑_{i=1}^n[g_if_t(x_i)+\frac{1}{2}ℎ_if_t^2(x_i)]+Ω(f_t)\)

关于XGBoost的推导并没有到此结束，为了计算XGBoost决策树结点分裂条件，我们还需要进一步的推导。

我们对决策树做一下定义。假设一棵决策树是由叶子结点的权重向量w和样本实例到叶子结点的映射关系q构成，这种映射关系可以理解为决策树的分支结构。所以一棵树的数学表达可以定义为：

\(f_t(x)=w_q(x)\)

然后定义决策树复杂度的正则化项。模型复杂度Ω可由单棵决策树的叶子结点数T和叶子权重w决定，即损失函数的复杂度由所有决策树的叶子结点数和叶子权重所决定。

\(Ω(f_t)=γT+\frac{1}{2}λ∑_{j=1}^T w_j^2\)

下面对决策树所有叶子结点重新进行归组。将属于第j个叶子结点的所有样本\(x_i\)划入一个叶子结点的样本集合中，即\(I_j=\{i|q(x_i)=j\}\)，因而简化后的XGBoost损失函数式又可以改写为：

\(L(t)≈∑_{i=1}^n[g_if_t(x_i)+\frac{1}{2}ℎ_if_t^2(x_i)]+Ω(f_t)\)

\(=∑_{i=1}^n[g_iw_q(x_i)+\frac{1}{2}ℎ_iw_q(x_i)^2]+γT+\frac{1}{2}λ∑_j1^Tw_j^2\)

$=∑_{j=1}^T[(∑_{i∈I_j }g_i)w_j+\frac{1}{2}(∑_{i∈I_j}ℎ_i+λ)w_j^2]+γT $

定义\(G_j=∑_{i∈I_j}g_i，H_j=∑_{i∈I_j}ℎ_i\)

其中：

• \(G_j\)可以理解为叶子结点j所包含样本的一阶偏导数累加之和


• \(H_j\)可以理解为叶子结点j所包含样本的二阶偏导数累加之和

\(G_j\)和\(H_j\)均为常量，将\(G_j\)和\(H_j\)代入上式，损失函数又可以变换为：

\(L(t)=∑_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+λ)w_j^2]+γT\)

对于每个叶子结点j，将其从目标函数中单独取出：

\(G_jw_j+\frac{1}{2}(H_j+λ)w_j^2\)

在树结构固定的情况下，对上式求导并令其为0，可得最优点和最优值为：

$w_j^∗=−\frac{G_j}{H_j}+λ $

$L=−\frac{1}{2}∑_{j=1}^T \frac{G_j^2}{H_j+λ}+γT $

假设决策树模型在某个结点进行了特征分裂，分裂前的损失函数写为：

$L_{before}=−[\frac{(G_L+G_R)^2}{H_L+H_R+λ}]+γ $

分裂后的损失函数为：

\(L_{after}=−\frac{1}{2}[ \frac{G_L^2}{H_L+λ} + \frac{G_R^2}{H_R+λ}]+2γ\)

分裂后的信息增益为：

\(Gain=\frac{1}{2}[ \frac{G_L^2}{H_L+λ} + \frac{G_R^2}{H_R+λ}−\frac{(G_L+G_R)^2}{H_L+H_R+λ}]-γ\)

如果增益Gain>0，即分裂为两个叶子结点后，目标函数下降，则考虑此次分裂的结果。实际处理时需要遍历所有特征寻找最优分裂特征。

以上就是XGBoost相对完整的数学推导过程，核心是通过损失函数展开到二阶导数来进一步逼近真实损失。XGBoost的推导思路和流程简化后如下图所示。

三、XGBoost常见问题

https://zhuanlan.zhihu.com/p/81368182

1.介绍一下XGBoost的原理

• XGBoost是基于GBDT的一种算法或者说工程实现。


• GBDT是一种基于boosting集成思想的加法模型，训练时采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。


• XGBoost的基本思想和GBDT相同，但是做了一些优化，如默认的缺失值处理，加入了二阶导数信息、正则项、列抽样，并且可以并行计算等。

2.XGBoost和GBDT的不同点

• GBDT是机器学习算法，XGBoost是该算法的工程实现。


• 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。


• GBDT在模型训练时只是用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。（好处：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。需要注意的是，损失函数需要二阶可导。）


• 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。


• 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行列采样。


• 传统的GBDT没有涉及对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。


• 特征维度上的并行化。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。

3.XGBoost的并行是怎么做的？

由于XGBoost是一种boosting算法，树的训练是串行的，不能并行。这里的并行指的是特征维度的并行。在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

4.XGBoost算法防止过拟合的方法有哪些？

• 在目标函数中添加了正则化。叶子节点个数+叶子节点权重的L2正则化。


• 列抽样。训练时只使用一部分的特征。


• 子采样。每轮计算可以不使用全部样本，类似bagging。


• early stopping。如果经过固定的迭代次数后，并没有在验证集上改善性能，停止训练过程。


• shrinkage。调小学习率增加树的数量，为了给后面的训练留出更多的空间。

5.使用XGBoost训练模型时，如果过拟合了怎么调参？

• 控制模型的复杂度。包括max_depth,min_child_weight,gamma 等参数。


• 增加随机性，从而使得模型在训练时对于噪音不敏感。包括subsample,colsample_bytree。


• 减小learning rate，但需要同时增加estimator 参数。

6.XGBoost的正则项是什么？

叶子节点个数和叶子节点权重的L2正则。

7.XGBoost为什么对缺失值不敏感？

一些涉及到对样本距离的度量的模型，如SVM和KNN，如果缺失值处理不当，最终会导致模型预测效果很差。

而树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。原因就是，一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。

另外，XGBoost还有一些处理缺失值的方法。

8.XGBoost怎么处理缺失值？

这是XGBoost的一个优点。具体处理方法为：

• 在某列特征上寻找分裂节点时，不会对缺失的样本进行遍历，只会对非缺失样本上的特征值进行遍历，这样减少了为稀疏离散特征寻找分裂节点的时间开销。


• 另外，为了保证完备性，对于含有缺失值的样本，会分别把它分配到左叶子节点和右叶子节点，然后再选择分裂后增益最大的那个方向，作为预测时特征值缺失样本的默认分支方向。


• 如果训练集中没有缺失值，但是测试集中有，那么默认将缺失值划分到右叶子节点方向。

9.XGBoost中的一棵树的停止生长条件

• 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。


• 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。


• 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。

10.XGBoost可以做特征选择，它是如何评价特征重要性的？

XGBoost中有三个参数可以用于评估特征重要性：

• weight ：该特征在所有树中被用作分割样本的总次数。


• gain ：该特征在其出现过的所有树中产生的平均增益。


• cover ：该特征在其出现过的所有树中的平均覆盖范围。覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点。

11.随机森林和GBDT的异同点

相同点：

• 都是由多棵树组成，最终的结果都是由多棵树一起决定。

不同点：

• 集成学习：RF属于bagging思想，而GBDT是boosting思想。


• 偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差。


• 训练样本：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本。


• 并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)。


• 最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合。


• 数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感。


• 泛化能力：RF不易过拟合，而GBDT容易过拟合。

12.XGBoost中如何对树进行剪枝

• 在目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的L2模的平方，控制树的复杂度。


• 在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益小于该阈值，则不分裂。


• 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。


• XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。

13.XGBoost如何选择最佳分裂点？

XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构。

因此，可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据的场景。XGBoost还提供了一种直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率。

14.XGBoost的延展性很好，怎么理解？

可以有三个方面的延展性：

• 基分类器：弱分类器可以支持CART决策树，也可以支持LR和Linear。


• 目标函数：支持自定义loss function，只需要其二阶可导。因为需要用二阶泰勒展开，得到通用的目标函数形式。


• 学习方法：Block结构支持并行化，支持 Out-of-core计算。