xgboost面试题整理

xgboost面试问题整理！

什么是gbdt？

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，它是属于 Boosting 策略。GBDT 由三个概念组成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和 Shrinkage（一个重要演变）。GBDT 的核心在于累加所有树的结果作为最终结果，所以 GBDT 中的树都是回归树，不是分类树 ， GBDT 的每一棵树都是以之前树得到的残差来更新目标值，这样每一棵树的值加起来即为 GBDT 的预测值。而残差其实是最小均方损失函数关于预测值的反向梯度。也就是说，预测值和实际值的残差与损失函数的负梯度相同，但是基于残差的GBDT 容易对异常值敏感，所以回归类的损失函数一般为： 绝对损失或者 Huber 损失函数

GBDT 的每一步残差计算其实变相地增大了被分错样本的权重，而对于分对样本的权重趋于 0 。

Shrinkage思想：在GBDT中，Shrinkage仍以残差为学习的目标，但对于残差学习的结果只累加一小部分，来逐渐逼近目标，从而有一种渐变的效果，Shrinkage会为每棵树设置一个weight权重（可以再附加学习率来控制渐变情况），通过乘以权重进行渐进。

什么是xgboost？

xgboost是一种boosting集成学习方法，它的核心思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。

它主要的创新在于：

对损失函数进行了二阶泰勒展开，同时使用一阶二阶导数
加入正则项控制模型的复杂度（正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和，正则项降低了模型的variance）

xgboost相比gbdt的优化？

算法本身的优化：首先GBDT只支持决策树，Xgboost除了支持决策树，可以支持多种弱学习器，可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART；其次GBDT损失函数化简的时候进行的是一阶泰勒公式的展开，而Xgboost使用的是二阶泰勒公式的展示。还有一点是Xgboost的目标函数加上了正则项，这个正则项是对树复杂度的控制，防止过拟合。
可以处理缺失值。尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向
运行效率：并行化，单个弱学习器最耗时的就是决策树的分裂过程，对于不同特征的特征分裂点，可以使用多线程并行选择。我自己理解，这里应该针对的是每个节点，而不是每个弱学习器。
从最优化的角度来看:

GBDT采用的是数值优化的思维, 用的最速下降法去求解Loss Function的最优解, 其中用CART决策树去拟合负梯度, 用牛顿法求步长.

XGboost用的解析的思维, 对Loss Function展开到二阶近似, 求得解析解, 用解析解作为Gain来建立决策树, 使得Loss Function最优.

Xgboost用泰勒二阶展开的原因？

Xgboost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式，而其他目标函数，如logloss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。这是从为什么会想到引入泰勒二阶的角度来说的。而且泰勒的本质是尽量去模仿一个函数，猜二阶泰勒展开已经足以近似大量损失函数。

二阶信息本身就能让梯度收敛更快更准确。这一点在优化算法里的牛顿法里已经证实了。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。这是从二阶导本身的性质，也就是为什么要用泰勒二阶展开的角度来说的。

为什么xgboost泰勒二阶展开后效果就比较好了呢？

牛顿法和二阶泰勒展开的关系

xgboost的目标函数优化问题？

LR可以通过SGD来优化，xgboost是一个离散型的优化问题。

1.近似目标函数，引入二阶泰勒

2.把树的结构参数化引入到目标函数

3.贪心算法/近似算法优化

xgboost的优缺点？

优点

精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，（使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题））。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合；
Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间；
列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算；
缺失值处理：XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度；
可以并行化操作：块结构可以很好的支持并行计算。

缺点

虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

基于决策树的xgboost的时间复杂度？

决策树的复杂度可由叶子数 $T$ 组成，叶子节点越少模型越简单，此外叶子节点也不应该含有过高的权重 $w$ （类比 LR 的每个变量的权重），所以目标函数的正则项可以定义为：

$\Omega(f_t)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 \\$

即决策树模型的复杂度由生成的所有决策树的叶子节点数量，和所有节点权重所组成的向量的 $L_2$ 范式共同决定。

如何计算每个特征的分裂收益呢？

假设我们在某一节点完成特征分裂，则分列前的目标函数可以写为：

$Obj_{1} =-\frac12 [\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}] + \gamma \\$

分裂后的目标函数为：

$Obj_2 = -\frac12 [ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}] +2\gamma \\$

则对于目标函数来说，分裂后的收益为：

0.5*(左子树分数+右子树分数-不分割可以得到的分数)-加入新节点引入的复杂度的代价

$Gain=\frac12 \left[ \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}\right] - \gamma \\$

注意该特征收益也可作为特征重要性输出的重要依据。

在决策树的生长过程中，如何找到叶子的节点的最优切分点？

贪心算法
1. 从深度为0的树开始，对每个叶节点枚举所有的可用特征；
2. 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
4. 回到第 1 步，递归执行到满足特定条件为止
近似算法

贪婪算法可以的到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。该算法会首先根据特征分布的分位数提出候选划分点，然后将连续型特征映射到由这些候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点。

XGBoost在寻找splitpoint的时候，不会枚举所有的特征值，而会对特征值进行聚合统计，按照特征值的密度分布，构造直方图计算特征值分布的面积，然后划分分布形成若干个bucket(桶)，每个bucket的面积相同，将bucket边界上的特征值作为splitpoint的候选，遍历所有的候选分裂点来找到最佳分裂点。

XGBoost 不是简单地按照样本个数进行分位，而是以二阶导数值 $h_i$ 作为样本的权重进行划分（通过目标函数推导而来）。

xgboost如何处理数据缺失？

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

xgboost的块结构实现，为什么能够并行计算？

决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。

每一个块结构包括一个或多个已经排序好的特征；
缺失特征值将不进行排序；
每个特征会存储指向样本梯度统计值的索引，方便计算一阶导和二阶导数值；

这种块结构存储的特征之间相互独立，方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。

xgboost分别是如何处理二分类和多分类问题的？

XGBoost 用 gbtree 做基分类器的话是用每次迭代构建一棵回归树，每棵树都是二叉树，二分类问题就看对应落到哪个叶子节点上，最后用加法模型算出最终的结果。

XGboost用于分类时用logloss损失函数，因为在使用提升树一类算法（包括XGboost）求损失函数的极值的时候，我们需要用到牛顿法、梯度下降法等方法。logloss损失函数的优点是可以求一阶导数，二阶导数来应用牛顿法，梯度下降法等方法去最小化损失函数。

xgboost多分类速度慢。

xgboost特征的重要性是如何评估的？

weight ：该特征在所有树中被用作分割样本的特征的总次数。
gain ：该特征在其出现过的所有树中产生的平均增益（我自己的理解就是目标函数减少值总和的平均值，这里也可以使用增益之和）。
cover ：该特征在其出现过的所有树中的平均覆盖范围。

这里有一个细节需要注意，就是节点分割的时候，之前用过的特征在当前节点也是可以使用的，所以weight才是有意义的。

xgboost抑制过拟合的方式？

行采样：行采样是bagging的思想,每次只抽取部分样本进行训练,不使用全部的样本,可以增加树的多样性。

列采样：随机森林的思想，相当于在做随机特征筛选，进入模型的特征个数越少(即模型变量越少)，模型越简单，根据机器学习理论（方差偏差理论），模型越简单，模型泛化性越好

shrinkage：XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间

参数：树的深度，树个数，最小信息增益，最大装箱数，每个节点的最少样本数。

xgboost为什么要用负梯度拟合残差？

首先，残差实际上默认是损失函数为MSE平方损失下的真实值和某一轮模型预测值的差值即 yi - f(xi)。其实这个是对平方损失函数求导之后的结果，也就是说在平方损失下求完导，他的负梯度就是残差。因为Loss的正梯度是上升的方向，负梯度是下降的方向。在传统的LR等Model中，训练的时候是用梯度下降来尽可能逼近Loss的近似最优值，所以在Boosting里面，也是通过沿着负梯度不断拟合这个值来使得整体的偏差尽可能的沿着Loss最小的方向走。

xgboost相比nn模型的优势？

1.可解释性强

xgboost代码调参

框架参数：

booster：弱学习器类型
objective：分类还是回归问题以及对应的损失函数
n_estimators：弱学习器的个数

弱学习器参数：

max_depth：树的深度
min_child_weight：最小节点的权重阈值，小于这个值，节点不会再分裂；
gamma：节点分裂带来损失最小阈值，我们使用目标函数之差计算增益，小于这个阈值的时候，不再分裂
learning_rate:控制每个弱学习器的权重缩减系；这个系数会乘以叶子节点的权重值，它的作用在于削弱每个树的影响力，如果学习率小，对应的弱学习器的个数就应该增加。

xgboost增量训练？

xgboost树模型的特征怎么做？

LightGBM

LightGBM 为了解决XGBoost 的缺点提出了以下几点解决方案：

单边梯度抽样算法；
直方图算法；
互斥特征捆绑算法；
基于最大深度的 Leaf-wise 的垂直生长算法；
类别特征最优分割；
特征并行和数据并行；
缓存优化。

单边梯度抽样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。
直方图算法

直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

优势：内存占用小，计算代价小。

虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。
带深度限制的 Leaf-wise 算法
- Level-wise：基于层进行生长，直到达到停止条件；
- Leaf-wise：每次分裂增益最大的叶子节点，直到达到停止条件。
XGBoost 采用 Level-wise 的增长策略，方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，降低了计算量；LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。
LightGBM 相对于 XGBoost 的优点，内存和速度
- 内存更小
1. XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 $O(2*\#data)$ 降低为 $O(\#bin)$ ，极大的减少了内存消耗；
2. LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
3. LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
- 速度更快
1. LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
2. LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
3. LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
4. LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
5. LightGBM 对缓存也进行了优化，增加了Cache hit的命中率。

参考

一篇文章搞定GBDT、Xgboost和LightGBM的面试

【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）

ID3、C4.5、CART、RF、boosting、Adaboost、GBDT、xgboost模型

XGBoost的技术剖析

一文搞定XGboost 面试常见问题