数学是一种理性的精神，使人类的思维得以运用到最完善的程度。
--克莱茵
XGBoost 的全称是eXtreme Gradient Boosting，由华盛顿大学的陈天奇博士提出，在Kaggle的希格斯子信号识别竞赛中使用，因其出众的效率与较高的预测准确度而引起了广泛的关注。
在前几期文章中，我们深入剖析了集成算法的思想和原理，并以AdaBoost、GBDT为例进行了深刻的挖掘和推导。XGBoost本质上是一堆CART树群，由多个相关联的决策树联合决策。决策树算法的终极目标是最终叶子节点的纯度越高越好，但需要平衡的一个问题就是纯度越高越容易出现过拟合。为了实现这个平衡剪枝、限制树的深度等，都是常用的手段。XGBoost用一堆树来拟合一个目标函数，这些树的生成是有前后顺序的，下一棵决策树输入样本会与前面决策树的训练和预测有关。所以XGBoost所要面临和解决的问题和GBDT一样：1、分裂点划分的依据是什么；2、分类后节点预测值是多少；3、防止模型过于复杂（避免过拟合）。
XGBoost的原理在本质上与GBDT相同，GBDT算法只利用了一阶的导数信息，xgboost对损失函数做了二阶的泰勒展开，并在目标函数之外加入了正则项对整体求最优解，用以权衡目标函数的下降和模型的复杂程度，避免过拟合。所以不考虑细节方面，两者最大的不同就是目标函数的定义，接下来就着重从xgboost的目标函数定义上来进行介绍。
XGBoost原理推导
xgboost的目标函数定义如下：
其中，
表示第t轮所生成的树模型，
表示正则项
。
泰勒展开
为什么要进行泰勒展开？
这是XGBoost与GBDT的最根本的区别，概括如下：
GBDT在函数空间中利用梯度下降法进行优化
XGBoost在函数空间中用牛顿法进行优化
XGBoost与GBDT的比较优势其实就是牛顿法与梯度下降法的比较优势：
· 梯度下降法用目标函数的一阶偏导、以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质，搜寻路线往往曲折往返；
· 牛顿法在二阶导数的作用下，从函数的凸性出发，直接搜索怎样到达极值点，也就是说在选择方向时，不仅考虑当前坡度是否够大，还会考虑走了一步之后，坡度是否会变得更大；
· 梯度下降是线性收敛，牛顿法是超线性的，至少二阶收敛
总之，牛顿法要比梯度下降法更具有全局判断能力。
再从步长的角度分析：
1、GBDT只用到了一阶信息，无法确定步长，所以只能用常数步长根据一阶梯度方向去不断逼近；
2、XGBoost用二阶信息去逼近函数，所以可以利用二阶信息确定更新步长，比只利用一阶信息的GBDT用更少的迭代获得更好的效果。
接下来推导XGBoost，我们使用泰勒展开:
来定义一个近似的目标函数如下：
因为
的值由之前的过程决定，所以本轮不变，也不影响本轮的训练，所以将这两者其去掉，得到：
现在的目标函数有一个非常明显的特点，它只依赖于每个数据点在误差函数上的一阶导数和二阶导数。
对
的定义做一下细化，将树拆分成结构部分
，
给出对应的叶子序号，根据叶子序号得到叶子权重：
终端节点的数量和树的深度可以看作是树模型的复杂度度量。
所以，对树的复杂度进行定义：
可以看到叶子的权重就是GBDT例子中叶子结点的值，而就是将某个样本点映射到某个叶子结点的函数。有了上边的两个式子后，继续对目标函数进行如下改写：
上面的公式需要遍历每一个样本，计算比较复杂，因为每一个样本最终都要落在叶子节点上，因此可以简化为遍历节点。
是对样本累加；
是对节点累加。
我们将他们统一起来，通过定义：
目标函数改为按叶子节点累加的形式：
二次优化
现在这个目标函数包含了T个相互独立的单变量二次函数，我们定义：
代表叶子节点内所有样本的目标函数的一阶导数的累加值；
代表叶子节点内所有样本的目标函数的二阶导数的累加值；
于是，我们就得到了最终的目标函数样子：
现在我们假设
已知，通过将上式对
求导并令其等于0，就可以求出令目标函数最小的：
代入目标函数，得到最小损失为：
推导到此，XGBoost的问题演变为，每轮加进来的模型，该怎么样构造，按照什么样的标准评估。
Obj代表了当我们指定一个树结构的时候，我们在目标上面最多减少多少，可以把它叫做结构分数。类似于基尼系数一样，是对树结构进行打分的函数。
有了打分函数，我们可以很轻易的得到分裂增益：
贪心策略
有了计算增益的公式，接下来要选择分裂成两个节点的特征，如何选择？
在分裂的时候，注意到，每次节点分裂，影响损失函数的只有这个节点的样本，因而每次分裂，计算分裂的增益（损失函数减少量）只需要关注当前分裂的那个节点的样本。
但是满足给定样本属性条件下，节点的分裂策略有很多，找到其中能使目标函数最优的决策树是一个NP-hard问题，我们贪心算法的策略来近似求解。
假设存在一个游标，先将分支下的样本按照一个属性进行排序，再滑动游标按照这个属性从小到大遍历，分别将样本分为两部分，将两部分的样本带入上一节求得的目标函数最小值公式，再相加，与不分裂的样本的目标函数做差，即为分裂后的"收益"。贪心策略就是找出收益最大的分裂"游标"的位置。
XGBoost为什么往往表现比较好？
第一：集成思想
Boosting算法非常精妙，首先使用单个简单的模型去拟合数据，得到一个比较一般的结果，然后不断向模型中添加简单模型（多数情况下为层数较浅的决策树），随着树的增多，整个集成模型的复杂度逐渐变高，直到接近数据本身的复杂度，此时训练达到最佳水平。 因此，集成算法要取得良好效果，要求每棵树都足够"弱"，使得每次增加的复杂度都不大，这样，就可能通过增加树的总数目，增加模型复杂度，来提高决策水平。
所以，XGBoost对每棵树的叶子节点数做了惩罚，从而限制了叶子节点的增长，使得每棵树都是"弱"的，同时引入学习速率，进一步降低了每棵树的影响。这样做的代价是，数的总数目会多一些，从其取得的效果上看，这样做是值得的。
第二：牛顿法
牛顿法与梯度下降法不同之处，前面已经详细解释了。我们更加凝炼的概括的一下就是：它们学习树结构的方式不同；还有学习确定树结构终端叶节点权重的方式不同。
可以发现牛顿树提升有Hessian矩阵，其在确定树结构方面发挥了关键性的作用，XGBoost使用的Hessian是一种更高阶的近似，可以学习到更好的树结构。
在损失函数的应用性方面，牛顿树提升因为要使用Hessian矩阵，所以要求损失函数是二次可微的。所以它在选择损失函数上要求更加严格，必须要是凸的。
当Hessian每一处都等于1时，这两种方法就是等价的，这就是平方误差损失函数的情况。因此，如果我们使用平方误差损失函数之外的任何损失函数，在牛顿树提升的赞助下，XGBoost 能更好地学习出树的结构。
第三：防止过拟合
终端节点的数量和树的深度可以看作是树模型的复杂度度量。
机器学习就是模型对数据的拟合。对于一组数据，使用过于复杂的模型去拟合，往往会发生过拟合，这时就需要引入正则化项来限制模型复杂度，然而正则化项的选取、正则化系数的设定都是依赖经验的，比较难做到最佳。而如果使用过于简单的模型，由于模型能力有限，很难把握数据中蕴含的规律，导致效果不佳。XGBoost通过巧妙的设计目标函数，先是在分母上加一个λ，来降低分支的收益"灵敏度"，这个"灵敏度"可以通过修改此参数来控制。当收益小于一个阈值则剪枝，从而达到防止过拟合的目的。另外一个参数γ，从最后每次分割后的收益函数可以看到，这个参数的"物理意义"就是每分裂一次，减去一个视为惩罚的常数。
同样，当样本权重和小于设定阈值时则停止建树涉及到一个超参数-最小的样本权重和最少的样本数，就是一个叶子节点样本太少了，也终止，同样是为了防止过拟合。
第四：支持并行化
从集成算法的原理可以看出，Boosting过程是串行的结构，并不能并行。注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。
我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程并行。
树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
全文总结
原理、过程阐述清楚后，再回过头来看XGBoost，除了集成算法的思想原理，我们会发觉XGBoost精妙之处，关键在于数学思想的充分应用，牛顿法与梯度下降法的比较优势，我们学过优化算法的都知道，但是被陈天奇大牛用在了XGBoost上。精妙还体现在对避免过拟合的思想的充分应用，通篇都会发觉XGBoost一是尽量增加树的数量，另一方面尽量减少树的深度和节点的数量，达到模型复杂与避免过拟合的平衡。
