XGBoost是当前炙手可热的算法，适合抽象数据的分析问题，在Kaggle等比赛中率获佳绩。市面上虽然有大量介绍XGBoost原理与使用的文章，但少有能清晰透彻的讲清其原理的。本文的目标是对XGBoost的原理进行系统而深入的讲解，帮助大家真正理解算法的原理。文章是对已经在清华达成出版社出版的《机器学习与应用》（雷明著）的补充。在这本书里系统的讲解了集成学习、bagging与随机森林、boosting与各类AdaBoost算法的原理及其实现、应用。AdaBoost与梯度提升，XGBoost的推导都需要使用广义加法模型，对此也有深入的介绍。
理解XGBoost的原理需要决策树（尤其是分类与回归树），集成学习，广义加法模型，牛顿法等基础知识。其中，决策树在SIGAI之前的文章“理解决策树”中已经做了深入的讲解。集成学习在之前的文章“随机森林概述”，“大话AdaBoost算法”，“理解AdaBoost算法”中已经做了讲解。牛顿法在之前的文章“理解梯度下降法”，“理解凸优化”，“理解牛顿法”中已经进行了介绍。如果读者对这些知识还不清楚，建议先阅读这些文章。
分类与回归树
决策树时机器学习中古老的算法，可以看做是一组嵌套的判定规则，这组规则通过训练得到。从数学上看，决策树是一个分段常数函数，每个叶子节点对应空间中的一片区域，落入此区域的向量x被预测为该叶子节点的值。
分类与回归树是二叉决策树的一种，既可以用于分类问题，也可以用于回归问题。训练时要解决的核心问题是寻找最佳分裂来确定内部节点，递归构建树，为叶子节点赋予标签值。对于分类问题，寻找最佳分裂时的目标是最大化Gini纯度值，简化后的计算公式为
其中NL是分裂之后左子节点的训练样本数，NL,i是左子节点中第i类样本数；NR是分裂之后右子节点的训练样本数，NR,i是右子节点中第i类样本数。对于回归问题，寻找最佳分裂时优化的目标是最大化回归误差的下降值
因为特征向量中有多个特征，因此实现时需要为每个特征分量计算最佳分裂阈值，然后取其中最优的。为单个特征计算最佳分裂阈值时，首先将该节点的所有训练样本按照该特征分量从小到大排序，然后依次以每个特征值作为阈值，将样本集分为左右两个子集，然后计算上面的分裂指标，取其最优值。具体原理在《机器学习与应用》一书中已经详细讲述。
第二个问题是叶子节点值的设定。对于分类问题，将叶子节点的值设置成本节点的训练样本集中出现概率最大的那个类；对于回归树，则设置为本节点训练样本标签值的均值。
集成学习
集成学习是机器学习中的一大类算法，它代表了一种朴素的思想：将多个机器学习模型组合起来使用，得到一个更强的模型。被组合的模型称为弱学习器，组合之后的模型称为强学习器。根据组合的策略不同，诞生了各种不同的算法。其中最常用的是bagging与boosting。前者的代表作是随机森林，后者的代表作是AdaBoost，梯度提升，XGBoost。
广义加法模型
在弱学习器的组合方案中，如果使用加法，即将多个弱学习器的预测函数相加得到强学习器，则称为广义加法模型。广义加法模型拟合的目标函数是多个基函数的线性组合
其中γi为基函数的参数，βi为基函数的权重系数。训练时要确定的是基函数的参数和权重值，如果用决策树充当基函数，则参数为比较特征、比较阈值，叶子节点值等。训练时的目标是最小化对所有样本的损失函数
训练算法采用了逐步求精的策略，依次确定每个基函数的参数和权重，然后将其加入强学习器中，使得强学习器的精度提升。实际实现时，将当前已经得到的强学习器对训练样本的输出值当做常数。然后采用分阶段优化策略，先固定住权重值βi，优化弱学习器。然后再将弱学习器当做常数，优化权重值βi。
以AdaBoost算法为例，强分类器对单个训练样本的损失为指数损失函数
将广义加法模型的预测函数代入上面的损失函数中，得到算法训练时要优化的目标函数为
这里将指数函数拆成了两部分，已有的强分类器Fj-1，以及当前弱分类器f对训练样本的损失函数，前者在之前的迭代中已经求出，因此Fj-1 (xi )可以看成常数。这样目标函数可以简化为
其中
它只和前面的迭代得到的强分类器有关，与当前的弱分类器、弱分类器权重无关，这就是AdaBoost算法的样本权重。这个问题可以分两步求解，首先将β看成常数，优化f(xi)；然后固定f(xi)，优化β。由此得到了AdaBoost的训练算法。
从广义加法模型可以推导出种AdaBoost算法，它们的弱分类器不同，训练时优化的目标函数也不同，分别是：
离散型AdaBoost
实数型AdaBoost算法
LogitBoost
Gentle型AdaBoost
各种AdaBoost算法的原理以及广义加法模型在《机器学习与应用》一书中有详细的讲述，限于篇幅，在这里不过多介绍。
除AdaBoost算法之外，boosting还有其他实现算法，如梯度提升算法。梯度提升算法采用了不同的思路，同样是使用广义加法模型，但在求解时采用了最速下降法（梯度下降法的变种）。同样是依次训练每个弱学习器，但训练弱学习器时没有为训练样本加上权重，而是为其计算伪标签值，该伪标签值是损失函数对当前已经求得的强学习器对训练样本的预测值Fj-1 (xi )的导数的负值：
然后用此次迭代时要训练的若学习器来拟合该目标。具体实现时分为了训练弱学习器，寻找最优步长的直线搜索（line search）这两步。
牛顿法
牛顿法是求解函数极值的数值优化（近似求解）算法。根据微积分中的Fermat定理，函数在点x*处取得极值的必要条件是导数（对于多元函数是梯度）为0，即：
称x*为函数的驻点。因此可以通过寻找函数的驻点求解函数的极值。直接计算函数的梯度然后解上面的方程组一般来是非常困难的，如果函数是一个复杂的非线性函数，这个方程组是一个非线性方程组，不易求解。因此大多采用迭代法近似计算。它从一个初始点x0开始，反复使用某种规则从xk移动到下一个点xk 1，直至到达函数的极值点。这些规则一般会利用一阶导数信息即梯度；或者二阶导数信息即Hessian矩阵。牛顿法采用了一阶导数与二阶导数信息。
对多元函数在x0处作二阶泰勒展开，有：
忽略二次及以上的项，将函数近似成二次函数，并对上式两边同时对x求梯度，得到函数的梯度为：
其中▽2 f(x0)即为Hessian矩阵H。令函数的梯度为0，则有：
解这个线性方程组可以得到：
由于在泰勒展开中忽略了高阶项，因此这个解并不一定是函数的驻点，需要反复用这个公式进行迭代。从初始点x0处开始，反复计算函数在处的Hessian矩阵和梯度向量，然后用下面的公式进行迭代：
最终会到达函数的驻点处。其中-H-1g称为牛顿方向。迭代终止的条件是梯度的模接近于0，或者函数值下降小于指定阈值。对于一元函数，Hessian矩阵即为二阶导数，梯度向量即为一阶导数，迭代公式为
在XGBoost的推导中将会使用此方法。
XGBoost
XGBoost是对梯度提升算法的改进，求解损失函数极值时使用了牛顿法，将损失函数泰勒展开到二阶，另外在损失函数中加入了正则化项。训练时的目标函数由两部分构成，第一部分为梯度提升算法损失，第二部分为正则化项。XGBoost的损失函数定义为
其中n为训练样本数，l是对单个样本的损失，yi'为预测值,yi为样本真实标签值，Φ为模型的参数。正则化项定义了模型的复杂程度
其中γ和λ为人工设置的系数，w为决策树所有叶子节点值形成的向量，T为叶子节点数。正则化项由叶子节点数，叶子节点值向量的模平方两项构成，第一项体现了决策树结构的复杂程度，第二项体现了决策树预测值的复杂程度。定义q为输入向量X到决策树叶子节点编号的映射，即根据输入向量确定用决策树的第几个叶子节点值来预测它的输出值
其中d为特征向量的维数。因此q定义了树的结构，w定义了树的输出值。决策树的映射函数可以写成
与梯度提升算法相同，采用加法模型表示强学习器。假设yi,t'为第i个样本在第t次迭代时的强学习器预测值，训练时依次确定每一个弱学习器函数ft，加到强学习器预测函数中，即最小化如下目标函数
实现时用贪婪法将ft加入到模型中，以最小化目标函数值。注意，在这里yi是常数，yi,t-1' f(xi）是损失函数的自变量，而yi,t-1'也是常数。对于一般的损失函数无法求得上面优化问题的公式解。采用牛顿法近似求解，对目标函数在yi,t-1'点处作二阶泰勒展开后得到
损失函数的一阶导数为
与梯度提升算法相同，是将之前已经训练得到的强学习器对样本的预测值当做变量求导，这一点一定要理解，很多读者困惑的地方在于不知道这个导数是对谁求导。损失函数的二阶导数为
去掉与ft(xi）无关的常数项，可以得到化简后的损失函数为
如果定义集合
即预测值为第j个叶子节点的训练样本集合（样本下标集合）。由于每个训练样本只属于某一个叶子节点，目标函数可以拆分成对所有叶子节点损失函数的和
首先介绍叶子节点的值如何确定。如果决策树的结构即q(x)确定，根据牛顿法可以得到第j个叶子节点的最优值为
这是单个叶子节点的损失函数对wj求导并令导数为0后解方程的结果。前面已经假定对单个样本的损失函数是凸函数，因此必定是极小值。单个叶子节点的损失函数对wj的一阶导数为
令其为0，即可得到上面的结果。
接下来说明如何确定决策树的结构，即寻找最佳分裂。将wj的最优解代入损失函数，得到只含有q的损失函数
此函数可以看做是对决策树结构优劣的一个度量，要求其极小值，类似于决策树寻找分裂时的不纯度指标。假设节点在分裂之前的训练样本集为I，分裂之后左子节点的训练样本集为IL，右子节点的训练样本集为IR。分裂之后的叶子节点数增加1，因此上面目标函数的第二项由γT变为γ(T 1)，二者的差值为γ。将上面的目标函数取反，求Lt (q)的极小值等价于求-Lt (q)的极大值。寻找最佳分裂的目标是使得损失函数的下降值最大化
γ是常数，因此上式最右边的-γ可以忽略。除了使用不同的分裂指标，其他过程与标准的决策树训练算法相同。在实现时将上面公式中的求和项定义为几个变量，分别是所有训练样本的一阶导数，二阶导数之和
左右子集样本的一阶导数，二阶导数之和
寻找最佳分裂的算法流程为
输入数据I：，当前节点的训练样本集，训练样本数为n
输入数据d：，特征向量维数
初始化分裂质量：score ← 0
计算所有样本的一阶导数，二阶导数之和：G←∑i∈I gi ,H ←∑i∈I hi
循环，对k=1,...,d
对所有训练样本按照第k个特征升序排序
初始化左子集所有训练样本的一阶导数，二阶导数之和：GL ←0,HL =0
循环，对j=1,...,n，以第j个样本的第k个特征分量xjk作为分裂阈值
计算左子集所有样本的一阶导数和二阶导数之和，在之前的基础上加上本次
被从右
边分到左边的样本的一阶导数和二阶导数值即可：GL ←GL gi,HL ←HL hj
计算右子集所有样本的一阶导数和二阶导数之和，可以根据总和，左子集的和快速
计算：GR ←G-GL,HR ←H-HL
计算分裂分数的最大值：
结束循环
返回：最大分裂质量score及其对应分裂（包括选用的特征，分裂阈值）
XGBoost实现时还使用了权重收缩与列采样技术，以抵抗过拟合。权重收缩的做法是在每训练出一棵决策树之后将其权重进行缩放，乘上系数η。权重收缩降低了之前的决策树的影响，为将来要生成的决策树留下了更多的空间。列采样的做法与随机森林相同，每次寻找最佳分裂时只考虑一部分随机抽取的特征分量。
参考文献
[1] Jerome H Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics. 2001.
[2] Tianqi Chen, Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. knowledge discovery and data mining. 2016.
[3] Jerome Friedman, Trevor Hastie and Robert Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics 28(2), 337–407. 2000.
