前言

今天，听了贪心学院的一个公开课，讲解的是xgboost的算法原理，感觉获益匪浅，老师带你手推公式，吹爆！！！在这里将我的学习笔记整理一下，大家一起来学习探讨。
XGBoost公开课
涉及到的论文是陈天奇的《XGBoost：A Scalable Tree Boosting System》
论文

boosting和bagging的区别

bagging

像是随机森林，这种bagging系的算法，它们的思想是训练多个模型每个模型去预测一个结果，然后对这些结果进行加权平均得到最终的预测结果。

boosting

而boosting则是基于残差的训练，每个模型在上一个模型预测结果与真实值的残差的基础上再进行训练，达到迭代次数或设定的阈值后停止，最终将各个模型的结果进行求和得到。

总结来说，bagging是过拟合的weak learner是，而boosting是欠拟合的weak learner。

提升树-基于残差的训练

在介绍XGBoost之前，还要介绍一下提升树的概念，其实提升树的算法思想是跟XGBoost相同的。



就像上面的三幅图像展示的那样，模型2在模型1的残差基础上进行拟合预测，而模型3则在模型2的基础上进行，最终的结果就像下面的图所示的那样是多个模型预测结果的和。

学习路径

XGBoost的介绍流程将会像图片展示的那样进行，算法的核心也就是这四个步骤。在第一步构建目标函数后，后面的三步则更倾向于是对目标函数的优化。由于构造的目标函数并不能够像逻辑回归那样是连续的，可以直接使用SGD进行优化，因此在算法的第二步使用了泰勒级数的方法去展开目标函数，将一些常量给提取分离出来，能够简化计算；在第三步中，则是考虑如何将树的结构进行参数化，带入到目标方程；第四步则是要查找结构最优的一棵树，而在查找的过程中采用贪心的算法进行，整个查找的过程是一个NP难问题。

构造目标函数

我们最终的预测结果是k棵树预测结果之和，而目标函数的组成有两部分，第一部分是损失函数，表示真实值与预测值的差距，具体的损失函数可以选用MSE、交叉熵等，在这篇博客中不做详细介绍；第二部分则是在控制树的复杂度，是一个惩罚项，经典的示例是正则化。树的复杂度可能会涉及到树的叶节点数、深度、叶节点值等，但具体如何去参数化实现我们还不太清楚，这个会在后面进一步讲解。

Additive Training(叠加式的训练)

上面的推导，我们做的主要工作是将前k-1个模型的相关表示和第k个模型给分开，这样当我们在训练第k个模型时前k-1个的相关表示便是常量，能够简化运算。
观察上面经过简化的目标函数，我们现在不知道是fk(xi)和Ω(fk)这两个函数如何表达，这将会在下面两节中进行介绍。

泰勒展开近似目标函数

泰勒展开在我们大学的高等数学中就已经学过了，它的主要思想是用多项式的形式去近似一些复杂函数，使得在实际工程能够求解得到算数解。
在我们学习优化算法时，梯度下降算法就是利用了一阶的泰勒展开，而牛顿法则是使用的二阶泰勒展开，所以在实际的使用中，牛顿法比梯度下降收敛得更快。
下面我们来推导一下，如何将化简后的目标函数用泰勒级数进行展开。

树结构的参数化

重新定义一棵树

上图中定义了如何用公式表示fk(xi)，图中公式使用的符号与我上面推导使用的符号有些许的不同，但应该能够看明白，t等价于那个k。
这里详细介绍一下，各个符号的含义。
ω是一个向量，存储的是叶子节点的值；q(x)表示样本x的位置，即它属于哪一个叶节点，在公式中用作表示ω的下标；再需要定义一个Ij，是一个集合，表示落在j节点的样本。
Ij用作解决函数中q(x)为ω的下标问题，这种表示方式并不标准化，Ij就用来将这个公式给标准化。
比如I1就是那个小男孩。

树的复杂度

从上面的图，我们可以看到，构建了一棵树，按照上面的变量定义，我们知道ω=[2,0.1,1]
T是节点数，γ和λ控制权重，是树的叶节点数更重要呢，还是叶节点的值更重要呢？

这样，将上面得到的表达式带入到我们化简得到的目标函数中，得

上面红框部分依旧是常数，我们用Gi和Hi表示，得

其实，得到的这个函数本质上是一个一元二次函数，因此在ωi=-b/2a时，能够取到整个函数的最值。

这样就得到了第k棵树的最优解。

贪心寻找最优结构树

其实，上面我们的所有讨论都有一个大前提就是已经知道了第k棵树的结构，在知道第k棵树的结构后，才推导得出了目标函数的最优解。
但是，实际计算中，我们并不知道第k棵树的结构，因此我们需要去寻找得到这棵树的结构。

寻找的思路与决策树的构建是一致的，都是去最大程度降低系统的混乱度，比如说，ID３算法每次寻找某个特征去分割节点时，依据的标准就是让信息增益最大，也就是让整个系统的混乱度降低。
在这里采用的不是熵，而是Obj的值,每次分割节点都是依据Obj值的增量尽可能的大。

小结

终于写完了，写这个花了我好几个小时，希望能给大家带来帮助。其实，这篇博客只是介绍了论文的前两章内容，算法的核心思想，后面的内容是在讲如何去进一步优化，我也不是很理解，大家可以去文章开头的链接里下载论文阅读。文章开头还有公开课的链接，大家也可以去看看，老师讲的比我好多了。