XGBoost从原理到实践5 从梯度提升开始

XGBoost的G即Gradient-梯度，而Boost是Boosting的缩写，即提升。属于集成学习中的提升算法，下面就从梯度提升算法说起。

梯度提升算法最出名的模型便是GBDT——梯度提升决策树，它和XGBoost的基学习器都是决策树中的CART树(分类回归树)。

下面来看看梯度提升树建模的一般流程，算法符号说明如下：

m：树的下标，总共有M颗树；i：训练样本的下标，总共有n个观测；Xi：特征向量，一个向量对应一条样本；yi：标签向量；L：损失函数；F(Xi)：基学习器函数，此处为决策树，表示前m-1颗树的预测值；t(Xi)：当前第m颗树的预测值；γ：步长，类似梯度下降的学习率。

第一步，初始化一颗决策树F0，随机指定步长γ值，F0要使损失函数L达到最小。如下：

，假设第一颗树F0长成下面的样子。

梯度提升树通过使损失函数的值达到最小，来确定决策树分叉，而不使用信息熵。上图有4个客户，分别为14岁、16岁、24岁和26岁，每个节点会计算一个平均年龄表示该节点的预测值。比如当按照购物金额切分时，损失最小，14和16岁的两人被分到一个叶子节点，预测平均值为15岁。

第二步，计算伪残差。上图给出了真实值和预测值的残差(-1,1,-1,1)，作为下一颗决策树的输入，如A=14-15=-1，这可以看作当损失函数是残差平方和时，损失函数对决策树函数F(Xi)求一阶导的结果，如损失函数L=1/2×(yi-F(Xi))^2，则L的导数为：2×1/2×(yi-F(Xi))=yi-F(Xi)，即真实值与预测值的残差。如果损失函数是其他的形式，例如残差的绝对值，那么L的导数就不一定正好是残差，我们把它称为伪残差，可看作残差的近似值。伪残差的公式如下：

残差只是损失函数为残差平方和时的一种特殊情况。所以提升树实际拟合的是残差或残差的近似值。r的下标m表示由第m-1颗树Fm-1的预测值和实际值算出第m颗树要输出的伪残差。

第三步，拟合下一颗树。有了伪残差r和样本特征向量Xi，就可以拟合一颗新的树t(Xi)，假如第二颗树F1长成下面这个样子。

当然同样要求使得损失达到最小。这一次得到以经常到百度提问或回答分叉为最佳。如第二颗树的预测A的值f(A)=(-1+-1)/2=-1，此时预测值是(伪)残差。

第四步，更新步长γ。在初始化时，我们随机给了一个步长，现在需要根据实际拟合情况进行调整，公式如下：

例如在第二颗树，m=1时更新步长γ。用树F0的预测值减去γ倍的F1的值t(Xi)作为前两步累计的预测值，与真实值yi一起传入损失函数，同样要使得损失最小，求得第m步的步长。

第五步，更新当前步的预测值。梯度提升树在预测第m棵树时，用到了前m-1棵树的预测值。公式如下：

例如我们的模型只有前面提到的两颗树，现在要预测A的年龄，计算如下：

F(A)=15+(1×-1)=15-1=14，为了说明上面的例子，将步长定为1。同理其他人的年龄如下，与真实值完全一致。

B=15+(1×1)=15+1=16

C=25+(1×-1)=25-1=24

D=25+(1×1)=25+1=26

最后，重复上述第二到五步，直到第M棵树完成结束。

以上就是梯度提升树的大致建模流程，它借鉴梯度下降法的思想，通过建立M棵树，即M轮迭代，以步长为学习率，选择梯度（伪残差）最大的方向进行优化，使损失最小化。Xgboost在梯度提升树(GBDT)的基础上进行了损失函数和并行化等的一系列优化。

历史文章回顾