关于XGBoost常问的一些问题的总结_xgboost为什么用二阶导不用三阶

l Xgboost和GBDT有什么异同？

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

• 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

• xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）

• 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

 

l 为什么xgboost训练会那么快，主要优化点是什么？

• 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

• xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

 

l Xgboost是如何处理缺失值的？

        原是论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。

 

l Xgboost和lightGBM有哪些异同？

• 在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算，所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复杂度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度，不过这里只涉及到加和操作)

• 直方图做差进一步提高效率，计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到，所以每次分裂只需计算分裂后样本数较少的子节点的直方图然后通过做差的方式获得另一个子节点的直方图，进一步提高效率

• 节省内存

  • 将连续数据离散化为直方图的形式，对于数据量较小的情形可以使用小型的数据类型来保存训练数据

  • 不必像预排序一样保留额外的对特征值进行预排序的信息

• 减少了并行训练的通信代价

 

l Xgboost为什么要使用泰勒展开式，解决什么问题？

实际上使用二阶泰勒展开是为了xgboost能够【自定义loss function】。

二阶泰勒展开实际不是最小二乘法，平方损失函数的二阶泰勒展开=最小二乘法。但陈佬为何想用二阶泰勒展开呢，我猜是为了xgboost库的可扩展性，因为任何损失函数只要二阶可导即能【复用】陈大佬所做的关于最小二乘法的任何推导。而且泰勒的本质是尽量去模仿一个函数，我猜二阶泰勒展开已经足以近似大量损失函数了，典型的还有基于分类的对数似然损失函数。嘿，这样同一套代码就能完成回归或者分类了，而不是每次都推导一番，重写训练代码。

 

l Xgboost是如何寻找最优特征的？

 

参考资料：

机器学习算法中GBDT和XGBOOST的区别有哪些？

BAT面试题7和8：xgboost为什么用泰勒展开？是有放回选特征吗？(https://cloud.tencent.com/developer/article/1360822)

XGBoost、LightGBM的详细对比介绍