宏观理解

XGBoost是大佬陈天奇开源的一套梯度提升树模型，其前身就是大名鼎鼎的GBDT。所以xgboost可以说是作者看到了GBDT可优化的潜力而优化过的一种GBDT。 陈天奇在介绍XGBoost时介绍到：“Both xgboost and gbm follows the principle of gradient boosting. There are however, the difference in modeling details. Specifically, xgboost used a more regularized model formalization to control over-fitting, which gives it better performance.” 也就是说其实xgboost用了更多正则化的手段来更高效的避免了过拟合的发生。

微观分析

决策树回顾：

我们在学习一个决策树的时候学习的是3个东西：1. 树的形状 2.每个决策的阈值theta 3. 叶节点的值。但是学习树的结构（structure learning）是很难的，所以目前只有greedy算法，分类问题在每次分裂的时候都要根据信息熵来选择信息增益最大的分裂节点。回归问题的时候可以通过方差/标准差来选择分裂节点。那么什么时候分裂结束呢？怎么控制它的节点数量呢？比如可以设定树的最大深度，或者当叶节点里的样本个数少于阈值（可通过交叉验证选择）时就停止分裂。

集成模型回顾：

分为两大类，bagging和boosting，意义就是三个臭皮匠胜于诸葛亮。（详细的请看机器学习分类中的集成模型章节） Bagging比如说随机森林，它对数据的采样实现来数据的多样性，也就实现了model的多样性。Bagging有很多个base learner，但是每个都比较弱，因为他们都会过拟合，原因是在训练的时候我们不会在意每个base learner的拟合程度，往往会让每个learner都学习的特别好。 Boosting比如说GBDT、XGBoost。它也有很多的base learner，每个也都比较弱，因为他们都会欠拟合，原因是在训练的时候我们都会用上一颗树的残差feed给下一棵树，所以我们要求每个learner都不需要学的太好。

XGBoost:

是一种基于残差的训练模型，也就是说在第一个基模型训练完后，可以计算出它的结果和标准答案的差别，这种差别叫做残差。然后我们再把这个残差交给下一个基模型去拟合传过来的残差。所以最终的预测结果也就是 = 模型1的预测 + 模型2的预测 + … + 模型n的预测

1. 如何构造目标函数？

假设我们已经训练好了k颗树，则对于第i个样本的预测值为： 其中fk表示第k颗树。 所以我们的目标函数。第一个部分是损失函数部分，如果是回归问题，我们的loss function可以用MSE等，如果是分类问题，可以用entropy loss等。第二部分是正则项，用来控制复杂度减少过拟合。其中Omega(fk)就代表在第k颗树上加入的正则项。所以我们目前还不知道怎么去参数化这个损失函数、正则项和树的结构。 一棵树的结构复杂度影响因素很多，比如叶节点的个数，树的深度，叶节点的值（因为如果每个叶节点的值变小，意味着我们需要更多的base learner来相加，所以导致树的数量增多）等。

2. 目标函数直接优化很难，如何近似？

假设已知我们有了k-1棵树，想要训练第k颗树时：

可是我们还是不能参数化fk(xi)和Omega(fk)。

3. 如何把树的结构引入到目标函数？

我们接下来来重新定义一下一棵树，假设叶节点有编号1-n，我们使用q(x) = 样本x的位置，也就是落在来哪个叶节点上。用Wq(x)来表示落在的叶节点位置上对应的叶节点值。用I(j)来表示落在j叶节点上有多少个样本数。那么我们可以把复杂度表示为,其中T为叶节点的个数，w为叶节点的值，即sum之后为这棵树所有叶节点的值的总和。gamma和lambda都是超参数。 然后我们便可以代入公式，其中我们已知的是每个fk(x)的值就是当前样本x落在的节点的值，也就是等于Wq(x)，所以

所以我们要最小化的也就是这个公式，但是因为我们未知的只有w，所以我们可以用y = ax^2 + bx + c的公式代入，即可求出最小值 所以我们现在可以得出结论：在树的结构已知的情况下，可以得到最优化的Wj和Objk。

4. 怎么得到树的结构来进行优化？

那么问题就变成了我们怎么才能知道树的结构呢？ 第一种方式：简单粗暴，考虑所有可能的树的结构，分别计算出Objk，选择最小的值对应的树。但问题是穷举的话树的个数将会是指数级别。 第二种方式：使用贪心算法，类似于决策树的信息收益，我们可以在分裂每个节点的时候按照新旧的obj的值

总结

对于XGBoost我们已经知道了目标函数，从第一棵树开始，我们默认第一棵树的y值是0，那么从第二颗树开始，我们就可以推导出每一棵树的目标函数优化以及他对应的结构了。但是目前除了贪心算法还没有一个可以计算出全局最优的算法来找到树的结构。