集成算法终极模型之《手撕 xgboost》—附详细手推公式
全文共 4255 字，阅读全文需 16 分钟
写在前面的话
大家好，我是小一
今天的文章从标题就能看出来，主要是对于 xgb 模型的推导。强烈建议仔细看完写在前面的话再开始阅读正文。
在学习 xgb、lgb 之前我也有些拒绝，因为这部分确实涉及到公式的推导和思维上的跳跃，难以接受是人之常情。
但是我要说的是：涉及到的公式推导并不难，求导会吧？泰勒公式学过吧？会这两个基本就够了。
思维上的跳跃就更容易，遇到的时候不要纠结为什么这样做，跳出问题去看这样做的好处是什么，回过头再看这样就会有种恍然大悟的感觉。
最后你再对比其他模型，特别是同类型的 Adaboost 模型、GBDT 模型你就更会发现 xgb 的妙处，再一次又会加深了理解。
其实，xgb 算法我看了三遍，每次都有收获，建议收藏一波多看几次。
另外，因为 xgb 涉及到的公式推导稍微多了些，小一偷个懒就直接“上手”了。
不是我不自信，也有可能你理解的就是对的，热烈欢迎互相交流，互相学习。
xgboost 介绍
集成学习根据各个弱分类器之间有无依赖关系，分为 Boosting 流派和 Bagging 流派
Boosting 流派：各分类器之间有依赖关系，必须串行，比如 Adaboost、GBDT(Gradient Boosting Decision Tree)、XgBoost、LigthGBM Bagging 流派：各分类器之间没有依赖关系，可各自并行，比如随机森林（Random Forest）
Bagging 流派中各个弱分类器是独立的、每个分类器在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个分类器之间没有啥关系， 最后投票表决。
今天要说的是 Boosting 流派的 xgboost，同样的，前面也有介绍过 Boosting 流派的 AdaBoost 算法：大话系列 | 集成算法之Adaboost
它的算法原理是这样的：AdaBoost：Adaptive Boosting（自适应增强）。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
最主要的一点是在每一轮弱分类器训练的时候，会根据上一轮分类器的训练结果对样本的权重进行调整，而且是加大上一轮分类器分错的样本的权重。这样就会导致当前轮的分类器更加注重前面分错的样本，然后一步步的训练出很多个弱分类器，最后根据弱分类器的变现给每个分类器加上权重，组合成一个强大的分类器。
这就是 AdaBoost 的自适应增强，通过不断修改样本权重， 不断加入弱分类器进行 boosting
另外，Boosting 还有一种方式，叫做 GBDT(Gradient Boost Decision Tree)：梯度下降决策树，和 AdaBoost 不同的是：GBDT 在训练弱分类器的时候关注的是残差。
我们知道 AdaBoost 训练弱分类器关注的是那些被分错的样本，并且在每一次训练都是为了减少错误分类的样本。
而 GBDT 在训练弱分类器的时候关注的是错误的程度，即上一轮弱分类器的预测与正确答案之间的差距，关注的是这个差距具体的值，并且在每一次训练弱分类器的时候，都是为了减少这个差距，进而在残差减少的方向上建立一个新的弱分类器。
考虑一个问题，残差减少的方向处于什么方向上减少最大？
举个例子再来说一下关于残差的减少
猜数游戏中你需要猜中系统随机产生的数是多少，已知这个数是在 0-100 之内，当你猜一个数之后系统会告知你猜大了还是猜小了。
比如说当前的数是 70，正确的方式是先猜50，系统告诉你猜小了；然后你确定这个数是在 50-100 之间，接下来你应该猜 75，系统告诉你猜大了；然后你确定这个数是在 50-75 之间，接下来你应该猜 62...其实猜数过程中只要你每次都取当前范围的中位数，然后缩小范围，再取中位数，再缩小范围，就可以以最快的方式 稳定 猜对。
回顾上面的问题，考虑一下为什么每次猜数都取中位数？这和残差减少有什么关系吗？
从上帝视角去看这个猜数过程：
第一次猜数：50，误差范围变成 0-50 第二次猜数：75，误差范围变成 0-25 第三次猜数：62，误差范围变成 0-12 第四次猜数：68，误差范围变成 0-6 第五次猜数：71，误差范围变成 0-3 第六次猜数：69，误差范围变成 0-1 第七次参数：70，猜对结束
在猜数的过程中，我们每次都是基于上一次的结果去猜新的数，并且不断的减少误差范围，每一次加入新的弱分类器都是在残差减少的方法上建立的。
回答一下上面两个问题：最快速度降低残差的方向就是负梯度方向，即每一轮弱分类器损失函数的负梯度方向。
说到这，我们来看一下 xgb 中的例子：
假设要预测这一家子人中每个人想玩游戏的意愿。XgBoost 解决这个问题的时候首先训练出来第一棵决策树， 预测小男孩想玩游戏的意愿是 2， 然后发现离标准答案差一些，又训练出来了第二棵决策树， 预测小男孩想玩游戏的意愿是 0.9， 那么两个相加就是最终的答案 2.9。
这个其实比较接近标准答案，所以 xgb 得出的结论就是对训练出来的弱分类器的结果进行累加。
从上面两个例子可以看到，xgb 和 GBDT 在策略上是类似的，都是在关注残差，想办法尽可能的缩小残差。区别在于：GBDT 通过不断加入新的树并在负梯度方向上降低残差，而 xbg 可以人为定义损失函数。
换种说法， xgb 可以算作是 gbdt 算法在工程上的一种实现方式。
所以 xgb 的损失函数可以是：最小平方差、logistic loss function、hinge loss function 或者人为定义的等等。在计算的时候我们只需要知道该损失函数对参数的一阶、二阶导数便可以进行 boosting 操作。【后面会提到为什么是一阶、二阶导数】
既然提到一阶二阶导数，顺便看一下 xgb 的介绍：
xgb 算法通过优化结构化损失函数来实现弱学习器的生成，并且直接利用了损失函数的一阶导数和二阶导数值，通过预排序、加权分位数等技术来大大提高了算法的性能。其中 xgb 的结构化损失函数加入了正则项，可以大大降低树模型过拟合的风险。
注意这里的正则项，后面在公式里面会具体提到
xgboost 推导
xgb 的推导有点经典，而且属于集成算法中的一个里程碑，LightGBM 也算是在 xgb 的基础上进行了相关的优化，所以 xgb 的推导就显得更加重要。
虽然 xgb 的推导涉及到大量的公式，但是还是值得花时间去好好推一遍，好好研究一下的。
xgb 的推导将会按照下面的步骤进行，具体的步骤会以手稿的形式展现，感兴趣的朋友可以一起推导一遍。
目标函数的推导和优化 引入 Taylor 公式并继续化简 基于决策树的目标函数【再次化简】 最优切分点划分 贪婪算法进行暴力划分 近似算法进行效率优化 稀疏感知算法对缺失值进行优化
xgb 的小总结
xgb 是多个弱分类器的集成，训练弱分类器的策略是尽量的减少残差，使得答案更加接近真实答案。在训练的过程中，xgb 通过加法进行训练，每次只训练一棵树，最后的预测结果为所有树的和
xgb 的精髓是目标函数的 Taylor 化简并由此引出一阶、二阶导数，并通过原本对样本的遍历转化为对叶子节点的遍历从而转化目标函数并求解。
在建树过程中，xgb 采用贪心策略从根节点一层层的开始建树，当数据量大时，xgb 通过近似算法选择候选分裂点进行优化。
xgb 和 GBDT 的区别
优点
xgb 相比 GBDT 有很多的性能优化，这些 优点 一般会在面试的时候被提到，总结如下：
xgb 的精度更高
相比 GBDT 的一阶泰勒展开，xgb 选择二阶泰勒展开，二阶泰勒展开后更方便自定义损失函数，只要损失函数有一阶、二阶导数即可
xgb 的模型方差更小
xgb 在目标函数中加入正则项，用于控制模型的复杂度。其中正则项里面包含树的叶子节点个数，叶子节点权重的 L2 范式。
学习速率
xgb 在进行完一次迭代后，会将叶子节点的权重乘以该系数，可以削弱每棵树的影响，使得后面的模型有更大的学习空间
列抽样技术
xgb 借鉴了随机森林的做法，支持列抽样，降低过拟合的同时减少计算。
缺失值处理
xgb 的稀疏感知算法，不但使得建树的时候样本更少，加快了节点分类的速度，还可以对缺失数据进行处理。
并行化操作
块结构可以更好的支持并行计算，并行计算在叶节点分裂的时候计算每个特征的最优划分点处体现【属于工程上的优化】
工程上的优化还包括如下几点：
块结果设计。在训练之前根据特征对数据进行排序，并将结果保存在块结构中，方便多次访问 缓存访问优化算法。针对块结构的访问会造成访问空间不连续，将梯度数据放在缓冲区中，可实现非连续空间到连续空间的转换，提高访问效率 “核外”块计算。xgb 独立一个线程专门用于从硬盘读入数据，实现处理数据和读入数据的同时进行。
缺点
同样的，xgb 不可避免的也存在相应的 缺点【部分缺点在 Lightgbm 中已被优化】，总结如下：
计算复杂
虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但是在节点分裂的过程中还是需要遍历数据集【虽然数据量已经优化过】。
空间复杂
预排序的过程需要额外存储特征对应的样本梯度值的索引，原则上相当于消耗了两倍的内存。
写在后面的话
xgb 就这一节，确实比起 Adaboost、GBDT 一下子难度提升了好多，也正是因为这种难度的提升带来了准确率和效率的提升，所以这也是为什么现在在业界吧 xgb 比较流行的原因吧
文章后面也有说到，xgb 确实还是存在部分缺陷的，这个缺陷在 Lightgbm 中也被优化了，后面整理一下关于 Lightgbm 的笔记再分享给大家。
记得点赞！！！
参考文献
我是小一，坚持向暮光所走的人，终将成为耀眼的存在！
期待你的 三连！我们下节见