xgboost是华盛顿大学博士陈天奇创造的一个梯度提升（Gradient Boosting）的开源框架。至今可以算是各种数据比赛中的大杀器，被大家广泛地运用。
一、Xgboost和GBDT差异比较
在GBDT中，我们每次生成下一个弱学习器，都是把损失函数的梯度作为学习目标，相当于利用梯度下降法进行优化来逼近损失函数的最小值，也就是使得损失函数为0，最终学习器尽可能接近真实结果。
而xgboost中，我们则是把损失函数的二阶泰勒展开的差值作为学习目标，相当于利用牛顿法进行优化，来逼近损失函数的最小值，也就是使得损失函数为0。
那为什么可以这么逼近呢？这就涉及到泰勒展开：
梯度下降法就是用一阶泰勒展开来近似函数：
而牛顿法则是用二阶泰勒展开来近似函数：
之后具体的迭代收敛原理请看最优化方法。
正则项是为了防止模型过拟合。于是，一般的损失函数L(x)就变成了目标函数 L(x)+O(x)。这样，随着树的复杂度增大，对应的目标函数也就变大，这样就有效防止了过拟合。叶子节点个数(T)，叶节点分数(w)
对叶子节点个数进行惩罚，相当于在训练过程中做了剪枝。
将xgboost的目标函数进行化简
令 其导数为0，解得每个叶节点的最优预测分数为：
代入目标函数，得到最小损失为：
精确算法：遍历所有特征的所有可能分割点，来寻找使目标函数最小的分割点。
近似算法：对于每个特征，只考察分位点，减少计算复杂度。
而XGBoost不是简单地按照样本个数进行分位，而是以二阶导数值作为权重(Weighted Quantile Sketch)，比如:
1.shrinkage（收缩）方法：相当于学习系数eta。对每颗子树都要乘上该系数，防止过拟合。
2.列采样：对特征进行降采样，灵感来源于随机森林，除了能降低计算量外，还能防止过拟合。
3.行采样：
4.缺失值处理：通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向。
5.xgboost工具支持并行。一般决策树中，我们需要每次都对特征的值进行排序，来寻找分割点，极其费时。xgboost中，我们先对每个特征进行分块（block）并排序，使得在寻找最佳分裂点的时候能够并行化计算。这个结构加速了split finding的过程，只需要在建树前排序一次，后面节点分裂时直接根据索引得到梯度信息。这是xgboost比一般GBDT更快的一个重要原因。
6.out-of-core, cache-aware优化内存等方法来加速计算。
二、Xgboost原理
在Xgboost中，选择树模型为基学习器，我们需要正则的对象，或者说需要控制复杂度的对象就是这K颗树,通常树的参数有树的深度，叶子节点的个数，叶子节点值的取值（Xgboost里称为权重weight)。
所以，我们的目标函数形式如下：
其中第一部分是训练损失，如上面所述的平方损失或者Logistic Loss等，第二部分是每棵树的复杂度的和。因为现在我们的参数可以认为是在一个函数空间里面，我们不能采用传统的如SGD之类的算法来学习我们的模型，因此我们会采用一种叫做additive training的方式。即每次迭代生成一棵新的回归树，从而使预测值不断逼近真实值（即进一步最小化目标函数）。每一次保留原来的模型不变，加入一个新的函数f 到模型里面：
所以，对于第K次的目标函数为：
其中constant为前K−1颗树的正则化项和，是一个常数。
根据公式（0），进一步为：
上面的式子意义很明显，只需要寻找一颗合适的树fK使得目标函数最小。然后不断的迭代K 次就可以完成K 个学习器的训练。
那么我们这颗树到底怎么找呢？
在GBDT里面（当然GBDT没有正则），我们的树是通过拟合上一颗树的负梯度值，建树的时候采用的启发式准则，如MSE等。
然而，在Xgboost里面，它是通过对损失函数进行二阶泰勒展开：
对损失函数二阶泰勒展开：
经过简化得到：
(8)式即为叶子结点取值的表达式。(9)式为目标函数的值。
到这里，我们一直都是在围绕目标函数进行分析，这个到底是为什么呢？这个主要是为了后面我们寻找f k ( x )，也就是建树的过程。具体来说，我们回忆一下建树的时候需要做什么，建树的时候最关键的一步就是选择一个分裂的准则，也就如何评价分裂的质量。比如在前面文章GBDT的介绍里，我们可以选择MSE，MAE来评价我们的分裂的质量，但是，我们所选择的分裂准则似乎不总是和我们的损失函数有关，因为这种选择是启发式的。比如，在分类任务里面，损失函数可以选择logloss，分裂准确选择MSE，这样看来，似乎分裂的好坏和我们的损失并没有直接挂钩。
但是，在Xgboost里面，我们的分裂准则是直接与损失函数挂钩的准则，这个也是Xgboost和GBDT一个很不一样的地方。
三、手动计算还原Xgboost的过程
数据集的样本条数只有15条，2个特征。具体如下：
这里为了简单起见，树的深度设置为3(max_depth=3)，树的颗数设置为2(num_boost_round=2),学习率为0.1(eta=0.1)。另外再设置两个正则的参数,λ=1,γ=0。损失函数选择logloss。由于后面需要用到logloss的一阶导数以及二阶导数，这里先简单推导一下。
在一阶导的基础上再求一次有（其实就是sigmod函数求导)
所以样本的一阶导数值
样本的二阶导数值
建树的时候从根节点开始(Top-down greedy)，在根节点上的样本有ID1～ID15。那么回顾Xgboost的算法流程，我们需要在根节点处进行分裂，分裂的时候需要计算式子(10)。
那么式子(10)表达是：在结点处把样本分成左子结点和右子结点两个集合。分别求两个集合的G L、H L、GR 、H R ，然后计算增益G a i n 。而这里，我其实可以先计算每个样本的一阶导数值和二阶导数值，但是这里你可能碰到了一个问题，那就是第一颗树的时候每个样本的预测的概率yi,pred 是多少？这里和GBDT一样，应该说和所有的Boosting算法一样，都需要一个初始值。而在Xgboost里面，对于分类任务只需要初始化为(0,1)中的任意一个数都可以。具体来说就是参数base_score。（其默认值是0.5）(值得注意的是base_score是一个经过sigmod映射的值，可以理解为一个概率值，提这个原因是后面建第二颗树会用到，需要注意这个细节）这里我们也设base_score=0.5。然后我们就可以计算每个样本的一阶导数值和二阶导数值了。具体如下表：
那么把样本如何分成两个集合呢？这里就是上面说到的选取一个最佳的特征以及分裂点使得Gain最大。
比如说对于特征x 1 x1x1，一共有[1,2,3,6,7,8,9,10]8种取值。可以得到以下这么多划分方式。
以1为划分时(x1<1)：
左子节点包含的样本IL =[]
右子节点包含的样本IR=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
那么左子节点为空，G L =0和HL=0
右子节点的一阶导数和：
右子节点的二阶导数和：
最后我们在计算一下增益Gain，可以得到Gain=0。计算出来发现Gain=0,不用惊讶,因为左子结点为空，也就是这次分裂把全部样本都归到右子结点，这个和没分裂有啥区别？所以，分裂的时候每个结点至少有一个样本。
下面，我再计算当以2划分时的增益Gain。
以2为划分时(x1<2)：
下面，我再计算当以2划分时的增益Gain。
以2为划分时(x1<2)：
左子结点包含的样本I L =[1,4]
右子节点包含的样本I R ==[2,3,5,6,7,8,9,10,11,12,13,14,15]
左子结点的一阶导数和：
左子结点的二阶导数和：
右子结点的一阶导数和：
右子结点的二阶导数和：
最后计算一下增益Gain：
其他的值[3,6,7,8,9,10]类似，计算归总到下面表，供大家参考
从上表我们可以看到，如果特征x1以x1<10分裂时可以得到最大的增益0.615205。
按照算法的流程，这个时候需要遍历下一个特征x2，对于特征x2也是重复上面这些步骤，可以得到类似的表如下，供大家参考。
可以看到，以x2特征来分裂时，最大的增益是0.2186<0.615205。所以在根节点处，我们以x1<10来进行分裂。由于我设置的最大深度是3，此时只有1层，所以还需要继续往下分裂。
左子节点的样本集合I L=[1,2,3,4,5,6,7,8,9,10,11,12,14,15]
右子节点的样本集合I R =[13]
右子节点此时只剩一个样本，不需要分裂了，也就是已经是叶子结点。可以计算其对应的叶子结点值了，按照公式(8)：
那么下面就是对左子结点I L进行分裂。分裂的时候把此时的结点看成根节点，其实就是循环上面的过程，同样也是需要遍历所有特征(x1,x2)的所有取值作为分裂点，选取增益最大的点。在此不展开叙述。
这里直接给出第一个树的结构。
至此，我们学习完了第一颗树。
这里，我们开始拟合我们第二颗树。其实过程和第一颗树完全一样。只不过对yi ,pred需要进行更新，也就是拟合第二颗树是在第一颗树预测的结果基础上。这和GBDT一样，因为大家都是Boosting思想的算法。
在第一颗树里面由于前面没有树，所以初始yi ,pred= 0.5
假设此时，模型只有这一颗树(K=1)，那么模型对样例x i 进行预测时，预测的结果表达是什么呢？
由加法模型
其中：
所以，我们可以得到第一棵树预测的结果为下表（预测后将其映射成概率）
比如对于ID=1的样本，其落在-0.04这个节点。那么经过sigmod映射后的值为
有了这个之后，根据公式（11）（12）我们就可以计算所有样本新的一阶导数和二阶导数的值了。具体如下表：
之后，我们和第一颗树建立的时候一样以公式(10)去建树。
拟合完后第二颗树如下图:
后面的所有过程都是重复这个过程，这里就不再啰嗦了。
至此，整个Xgboost的训练过程已经完了。
原文链接：https://blog.csdn.net/anshuai_aw1/article/details/82970489
联系客服
