XGBoost（Extreme Gradient Boosting）

XGBoost 是对 GBDT 算法的改进。其改进主要如下：

1. 损失函数求解使用了泰勒二阶展开;
2. 损失函数中添加了正则化项;

XGBoost 损失函数如下：

第一部分真实值和预测值之间的经验损失，第二部分是正则化项。一般来讲，我们可以把正则化项理解为新增加的优化方向，也就是说，添加了正则化项之后，我们不仅仅要考虑经验损失，也需要考虑其他指标带来的损失。正则化项如下：

T 表示叶子节点数量，我们知道一棵树的叶子节点数量越多，其结构就越复杂，反之，则结构就越简单。所以，我们需要在梯度提升算法损失的基础上，还要考虑树的复杂度这个因素。γ 用于调节树的复杂度，γ 越大，就意味着树的复杂度对最终的损失值影响就越大，当两棵梯度提升树的损失值一样时，优先选择结构更加简单的那棵树。

w 是一个由叶子节点输出值组成的向量。这一项考虑到了一棵树的输出预测值的复杂度。当该值非常大时，就意味着预测的值距离要目标值波动就越大，或者也可能由于某些异常样本导致波动性比较大。当两棵树的损失值一样时，我们优先选择预测值波动较小的那棵树。

这样的损失函数究竟如何影响我们的模型呢?

有了这个损失函数，我们就可以从是否能够降低结构化损失的角度来考虑弱决策树的每次分类了。比如：当我们要确定树是否要继续分裂时，可以计算下分裂前和分裂后的损失值，如果分裂后的损失值小于分裂前，则应该分裂，并且我们知道决策树的拟合能力非常强，在损失函数中加入正则化项，一定程度上能够降低学习过拟合的影响。

对于 XGBoost 算法最重要的一点还是其损失函数如何简化，由于 XGBoost 是由多个弱学习器串行组成，所以在构建整个强学习器的时候，我们无法站在全局的角度去考虑损失最小化，而是利用贪心思想，只能确保截止到目前为止的损失最小化。 XGB 的损失函数如下：

我们知道 XGBoost 的基学习器是串行表示的，如下图：

当我们训练第 t 个学习器时，需要在第 t-1 个学习器的经验下构建。但是【图-3】的损失函数并没有体现出第 t-1 学习器的信息，所以，我们可以将【图-3】的损失函数转换为如下形式：

这是因为第 t 棵树的预测值 = t-1 棵树的输出 + 当前这棵树的输出，所以【图-3】公式就可以转换为【图-5】形式。此时，我们就可以考虑下在 t-1 棵树的现状下，构建第 t 个学习器。也就是说，当前这棵树怎么构建，能够使得强学习的损失最小，模型能够更加逼近目标值。

但是【图-5】公式优化并不那么简单，我们先对其在 y_{i,t-1} 点出进行泰勒二阶求导，得到如下形式：

【图-6】表示对损失函数的一阶导，【图-7】表示对损失函数的二阶导，此时，【图-5】公式可转换为：

我们去掉【图-8】损失函数中的常数项。为什么说是常数项，因为前 t-1 棵树已经构建完了，不需要考虑如何构建了，所以前 t-1 部分的损失将其再次进行简化为：

此时，w 表示一个由当前树叶子节点输出值组成的向量 (w₁、w₂…w_n)，而 f_t(x_i) 表示所有样本节点输出值。在逻辑回归、线性回归、SVM、神经网络中也有 w_?，那些算法模型中的 w 表示的是特征权重，注意区分。

为了能够继续简化我们的公式，我们转换下公式，将公式中从不同角度的描述的各个部分，转换为相同的角度。接下来，我们把【图-9】公式中的各个部分做个转换：

I_j 表示属于第 j 个叶子节点的所有样本的集合。虽然公式样子变了，但是表示的同一个含义。

最重要的 3 部分我们都转换成了从叶子节点角度的问题，现在将【图-10】、【图-11】、【图-12】替换到【图-9】中，得出：

上面的式子太复杂了，我们令：

G_i 表示叶子结点上所有样本的一阶导之和，H_i 表示叶子结点上所有样本的二阶导之和。当确定损失函数时，就可以通过计算得到结果。得到【图-13】的式子如下：

w_j 表示某个叶子节点的输出值。也就是说，我们得知道当叶子结点的输出值 w 为多少时，能降低损失。我们可以通过对【图-15】中 w 求导，并令导数为 0，计算叶子节点的最优值：

此时，将 【图-16】代入到【图-15】公式中，得到：

此时，【图-17】就是损失函数，那么这个公式应该怎么用呢？

例如：我们有训练样本集 S，分裂之后属于左子树的所有样本集合为S_左 , 属于右子树的所有样本集合为S_右 。每次分裂时，叶子节点数量会增加 1。所以，当考虑某个切分点时，需要考虑以该切分点进行分裂之后的树的优劣，我们可以用分裂前的损失值减去分裂后的损失来作为分裂指标，这其实就表示分裂之后是损失提高了，还是降低了。以该值最大的划分点来作为分裂点，可以用公式表示如下：

这个公式也叫做 XGB 算法的增益计算公式。当我们构建第 N 课弱决策树时，可以通过计算候选的每个切分点的增益值，从而确定是否进行此次分裂。并且每次的分裂过程，都能够降低强学习器总损失，使得模型的预测结果越来越逼近真实目标值，并且这个过程中也考虑到了决策树过拟合的问题。