\begin{aligned} \hat{y}_i^{(0)} & = 0 \\ \hat{y}_i^{(1)} & = f_1(x_i)=\hat{y}_i^{(0)}+f_1(x_i) \\ \hat{y}_i^{(2)} & = f_1(x_i)+f_2(x_i)=\hat{y}_i^{(1)}+f_2(x_i) \\ \dots \\ \hat{y}i^{(t)} & = \Sigma{k=1}^tf_k(x_i)=\hat{y}_i^{(t-1)}+f_t(x_i) \\ \end{aligned}

\hat{y}_i^{(t)} 是第 t次迭代的预测值。
\hat{y}_i^{(t-1)} 是 t-1次迭代的预测值。
f_t(x_i) 是第 t颗树，也就是我们第 t次迭代需要得到的树。

（2）目标函数变换

第一步：根据上面的公式，目标函数可以做如下变形

\begin{aligned} Obj^{(t)} & =\Sigma{i=1}^nl(y_i,\hat{y}_i^{(t)})+\Sigma{k=1}^t\Omega (f_k)\\ & =\Sigma_{i=1}^nl(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega (f_t)+constant \end{aligned}

这里我们考虑平方损失，此时目标函数又可以变形为：

Obj^{(t)}=\Sigma_{i=1}^n(2(y_i-\hat{y}_i^{(t-1)})f_t(x_i)+f_t(x_i)^2)+\Omega (f_t)+constant

第二步：所以我们的目的就是找到 f_t使得目标函数最低。然而，经过上面初次变形的目标函数仍然很复杂，目标函数会产生二次项。

在这里我们引入泰勒展开公式：

f(x+\Delta x)\simeq f(x)+f(x)\Delta x+1/2f(x)\Delta x^2

令 f(x)=\Sigma_{i=1}^nl(y_i,\hat{y}_i^{(t)})
令 \Delta x=f_t

目标函数利用泰勒展开式就可以变成：

Obj^{(t)}\simeq \Sigma_{i=1}^n(l(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+1/2h_if_t(x_i)^2)+\Omega (f_t)+constant

g_i = \partial _{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)})
h_i = \partial _{\hat{y}^{(t-1)}}^2l(y_i,\hat{y}^{(t-1)})

第三部：把常数项提出来，目标函数可以简化为

Obj^{(t)}\simeq \Sigma_{i=1}^ng_if_t(x_i)+1/2h_if_t(x_i)^2+\Omega (f_t)+constant

思考：为什么要做这么多变化而不直接生成树？

理论好处：知道我们在学习什么，收敛。
工程好处：回顾监督学习的要素。
- g_i, h_i都来自损失函数的定义。
函数的学习只通过 g_i, h_i依赖于目标函数。
当被要求为平方损失和逻辑损失实现Bootsted Tree时，可以考虑如何分离代码模块。

（3）重新定义树

在前面，我们使用 f_t(x)代表一颗树，在本小节，我们重新定义一下树：我们通过叶子结点中的分数向量和将实例映射到叶子结点的索引映射函数来定义树：（有点儿抽象，具体请看下图）

f_t(x)=w_q(x), w\in R^T, q:R^d \rightarrow \left\{1,2,3,…,T\right\}

w代表树中叶子结点的权重
q代表的是树的结构

从上图可以看出，共有3个叶子结点，第一个叶子结点的权重为+1，第二个叶子结点的权重为0.1，第三个叶子结点的权重为-1；其中，小男孩属于第1个叶子结点，老奶奶属于第3个叶子结点。

（4）定义树的复杂程度

通过下面的式子定义树的复杂程度（定义并不是唯一的）

\Omega (ft)=\gamma T+\frac{1}{2}\lambda\Sigma{j=1}^Tw_j^2

\gamma T代表了叶子结点的个树
\frac{1}{2}\lambda\Sigma_{j=1}^Tw_j^2叶子结点分数的L2 Norm

（5）重新审视目标函数

定义在叶子结点 j中的实例的集合为：

I_j=\left\{i|q(x_i)=j \right\}

根据每棵叶子重新定义目标函数：

\begin{aligned} Obj^{(t)}& \simeq \Sigma_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2]+\Omega (f_t)+constant \\ & = \Sigma_{i=1}^n[g_iw_q(x_i)+\frac{1}{2}h_iw_q(x_i)^2]+\gamma T+\frac{1}{2}\lambda\Sigma_{j=1}^Tw_j^2+constant \\ & = \Sigma_{j=1}^T[(\Sigma_{i\epsilon I_j} g_i)w_j+\frac{1}{2}(\Sigma_{i\epsilon I_j} h_i+\lambda)w_j^2]+\gamma T+constant \end{aligned}

上式是T个独立二次函数的和

（6）计算叶子结点的值

一些知识需要先了解。对于一元二次函数： Gx+\frac{1}{2}Hx^2，我们很容易得到这个函数的最小值和最小值对应的 x。

最小值对应的 x相当于求 Gx+\frac{1}{2}Hx^2的导数，使导数等于0时的值，即 Gx+Hx=0，所以 x=-G/H。
当 x=-G/H，对应的 Gx+\frac{1}{2}Hx^2的值为： -\frac{1}{2}*G^2/H

也就是：

\begin{aligned} argmin_x Gx+\frac{1}{2}Hx^2 & =-\frac{G}{H}, H>0 \\ min_x Gx+\frac{1}{2}Hx^2 & =-\frac{1}{2}\frac{G^2}{H} \end{aligned}

如何求叶子结点最优的值？接着继续变化目标函数：

定义 G_j= \Sigma_{i\epsilon I_j}g_i
定义 H_j = \Sigma_{i\epsilon I_j}h_i

\begin{aligned} Obj^{(t)}&= \Sigma_{j=1}^T[(\Sigma_{i\epsilon I_j} g_i)w_j+\frac{1}{2}(\Sigma_{i\epsilon I_j} h_i+\lambda)w_j^2]+\gamma T+constant\\ & = \Sigma_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T+constant \end{aligned}

假设树的结构 q(x)是固定的，那么每一个叶子结点的权重的最优值为

w_j^*=-G_j/(H_j+\lambda)

目标函数的最优值为

Obj=-\frac{1}{2}\Sigma_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T

下图是前面公式讲解对应的一个实际例子。

这里再次总结一下，我们已经把目标函数变成了仅与 G、H、\gamma、\lambda、T这五项已知参数有关的函数，把之前的变量 f_{t}消灭掉了，也就不需要对每一个叶子进行打分了！

那么现在问题来，刚才我们提到，以上这些是假设树结构确定的情况下得到的结果。但是树的结构有好多种，我们应该如何确定呢？

（7）贪婪算法生成树

上一部分中我们假定树的结构是固定的。但是，树的结构其实是有无限种可能的，本小节我们使用贪婪算法生成树：

首先生成一个深度为0的树（只有一个根结点，也叫叶子结点）
对于每棵树的每个叶子结点，尝试去做分裂（生成两个新的叶子结点，原来的叶子结点不再是叶子结点）。在增加了分裂后的目标函数前后变化为（我们希望增加了树之后的目标函数小于之前的目标函数，所以用之前的目标函数减去之后的目标函数）：

Gain=\frac{1}{2}(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda})-\gamma

\frac{G_L^2}{H_L+\lambda}是左面叶子结点的值
\frac{G_R^2}{H_R+\lambda}是右面叶子结点的值
\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}是未分裂前的值
\gamma是引入了多一个的叶子结点增加的复杂度

接下来要考虑的是如何寻找最佳分裂点。

例如，如果 x_j是年龄，当分裂点是 a的时候的增益gain是多少？

我们需要做的仅仅只是计算每一边的 g和 h，然后计算

Gain=\frac{1}{2}(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda})-\gamma

对排序后的实例进行从左到右的线性扫描就足以决定特征的最佳分裂点。

所以，分裂一个结点的方法是：

对于每个节点，枚举所有特性
对于每个特性，按特性值对实例排序
使用线性扫描来决定该特征的最佳分裂点
采用所有特征中最好的分裂方案

时间复杂度：

对于一个有d个特征，深度为K的树，计算的时间复杂度为：O(dKnlog n)。其中每一层需要花费O(nlog n)的时间做排序。
可以进一步优化（例如使用近似或缓存排序的特性）。
可以扩展到非常大的数据集。

（8）如何处理分类型变量

一些树学习算法分别处理分类变量和连续变量，我们可以很容易地使用我们推导出的基于分类变量的评分公式。但事实上，我们没有必要单独处理分类变量：

我们可以使用one-hot方式处理分类变量：

z_{j}=\left\{\begin{array}{ll} 1 & \text { if } x \text { is in category } j \\ 0 & \text { otherwise } \end{array}\right.

如果有太多的分类的话，矩阵会非常稀疏，算法会优先处理稀疏数据。

（9）修剪和正则化

回顾之前的增益，当训练损失减少的值小于正则化带来的复杂度时，增益有可能会是负数：

Gain=\frac{1}{2}(\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda})-\gamma

此时就是模型的简单性和可预测性之间的权衡。

前停止（Pre-stopping）：当最佳分裂是负数时，停止分裂；但是一个分裂可能会对未来的分裂有益；
后剪枝（Post-Pruning）：把一颗树生长到最大深度，递归修剪所有分裂为负增益的叶子。

2.XGBoost核心原理归纳解析

1）目标函数与泰勒展开

XGBoost也是一个Boosting加法模型，每一步迭代只优化当前步中的子模型。

第 m步我们有：

Fm(x_i) = F{m-1}(x_i) + f_m(x_i)

f_m(x_i)为当前步的子模型。
F_{m-1}(x_i) 为前 m-1个完成训练且固定了的子模型。

目标函数设计为「经验风险」+「结构风险」（正则项）：

\begin{aligned} O b j &=\sum_{i=1}^{N} L\left[F_{m}\left(x_{i}\right), y_{i}\right]+\sum_{j=1}^{m} \Omega\left(f_{j}\right) \\ &=\sum_{i=1}^{N} L\left[F_{m-1}\left(x_{i}\right)+f_{m}\left(x_{i}\right), y_{i}\right]+\sum_{j=1}^{m} \Omega\left(f_{j}\right) \end{aligned}

正则项 \Omega (f)表示子模型 f的复杂度，用于控制过拟合。

在数学中，我们可以用泰勒公式近似 f(x)，具体如下式。XGBoost对损失函数运用二阶展开来近似。

f(x_0+\Delta x) \approx f(x_0)+f^{'}(x_0) \Delta x + \frac{f^{''}(x_0)}{2} (\Delta x)^2

（更多数学知识推荐阅读ShowMeAI的AI数学基础系列教程图解AI数学基础：从入门到精通系列教程）。

对应XGBoost的损失函数，我们在上式里将 F_{m-1}(x_i)视作 x_0， f_{m}(x_i)视作 \Delta x， L(\hat{y_i},y_i)视作关于 \hat{y_i}的函数，得到：

Obj = \sum_{i=1}^N \Big[ L[F_{m-1}(x_i),y_i] + \frac{\partial L}{\partial F_{m-1}(x_i)} f_m(x_i) + \frac{1}{2} \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)} f_m^2(x_i) \Big] +\sum_{j=1}^m \Omega (f_j) \\

又因前 m-1个子模型已经确定了，故上式中除了关于 f_{m} (x)的部分都是常数，不影响对 f_{m} (x)的优化求解。目标函数可转化为：

O b j=\sum_{i=1}^{N}\left[g_{i} f_{m}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{m}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{m}\right)

g_i = \frac{\partial L}{\partial F_{m-1}(x_i)}
h_i = \frac{\partial^2 L}{\partial^2 F_{m-1}(x_i)}
这里的 L代表损失函数，衡量一次预测的好坏程度
在 F_{m-1}(x)确定了的情况下，对每个样本点 i都可以轻易计算出一个 g_i和 h_i

2）XGBoost的正则化

实际上，XGBoost的基分类器对决策树和线性模型都支持，这里我们只讨论更常见的「基于树」的情况。为防止过拟合，XGBoost设置了基于树的复杂度作为正则项：

\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2

T为树 f的叶节点个数
w为所有叶节点输出回归值构成的向量， ||w||^2为该向量L2范数（模长）的平方
\gamma、 \lambda为超参数

作为回归树，叶子节点越多、输出的回归值越大，树的复杂度越高。

最终目标函数如下：

Obj = \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\

下面是一个数学转换处理，为了使正则项和经验风险项合并到一起。我们把在样本层面上求和的经验风险项，转换为叶节点层面上的求和。

定义节点 j上的样本集为 I(j)=\{x_i|q(x_i)=j\}，其中 q(x_i)为将样本映射到叶节点上的索引函数，叶节点 j上的回归值为 w_j=f_m(x_i),i \in I(j)。

Obj = \sum_{j=1}^{T} \Big[ (\sum_{i\in I(j)} g_i) w_j + \frac{1}{2}(\sum_{i\in I(j)} h_i + \lambda) w_j^2 \Big] + \gamma T \\

进一步简化表达，令 \sum_{i\in I(j)} g_i=G_j， \sum_{i\in I(j)} h_i=H_j注意这里G和H都是关于 j的函数：

Obj = \sum_{j=1}^{T} \Big[ G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2 \Big] + \gamma T \\

转化到这个形式后，我们可以看出，若一棵树的结构已经确定，则各个节点内的样本 (x_i,y_i,g_i,h_i)也是确定的，即 G_j， H_j、 T被确定，每个叶节点输出的回归值应该使得上式最小，由二次函数极值点：

w_j^*=-\frac{G_j}{H_j+\lambda}

按此规则输出回归值后，目标函数值也就是树的评分如下公式，其值越小代表树的结构越好。观察下式，树的评分也可以理解成所有叶节点的评分之和：

Obj^* = \sum_{j=1}^T \Big( -\frac{1}{2}\frac{G_j^2}{H_j + \lambda} + \gamma \Big)

3）节点分裂准则

我们之前文章【决策树模型详解】里给大家讲到了决策树模型是递归生长形成的，而XGBoost的子模型树也一样，需要要依赖节点递归分裂的贪心准则来实现树的生成。

我们之前文章决策树模型详解里给大家讲到了决策树模型是递归生长形成的，而XGBoost的子模型树也一样，需要要依赖节点递归分裂的贪心准则来实现树的生成。

（1）贪心准则

XGBoost子树的基本处理思路和CART一样，会对特征值排序后遍历划分点，将其中最优的分裂收益作为该特征的分裂收益，选取具有最优分裂收益的特征作为当前节点的划分特征，按其最优划分点进行二叉划分，得到左右子树。

上图是一次节点分裂过程，很自然地，分裂收益是树A的评分减去树B的评分。虚线框外的叶节点，即非分裂节点的评分均被抵消，只留下分裂后的LR节点和分裂前的S节点进行比较，因此分裂收益的表达式为：

Gain = \frac{1}{2} \Big[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} -\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\Big]-\gamma \\

（2）近似算法

基于性能的考量，XGBoost还对贪心准则做了一个近似版本，简单说，处理方式是「将特征分位数作为划分候选点」。这样将划分候选点集合由全样本间的遍历缩减到了几个分位数之间的遍历。

展开来看，特征分位数的选取还有global和local两种可选策略：

global在全体样本上的特征值中选取，在根节点分裂之前进行一次即可；
local则是在待分裂节点包含的样本特征值上选取，每个节点分裂前都要进行。

这两种情况里，由于global只能划分一次，其划分粒度需要更细。

XGB原始paper中对Higgs Boson数据集进行了实验，比较了精确贪心准则、global近似和local近似三类配置的测试集AUC，用eps代表取分位点的粒度，如 eps=0.25代表将数据集划分为1/0.25=4个buckets，发现global（eps=0.05）和local（eps=0.3）均能达到和精确贪心准则几乎相同的性能。

XGBoost工具包支持上述提到的3类配置。

（3）加权分位数

查看目标函数 Obj=\sum_{i=1}^{N}\left[g_{i} f_{m}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{m}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{m}\right)，令偏导为0易得 f_m^*(x_i)=-\frac{g_i}{h_i}，此目标函数可理解为以 h_i为权重， -\frac{g_i}{h_i}为标签的二次损失函数：

\begin{aligned} Obj &= \sum_{i=1}^N \Big[g_i f_m(x_i)+\frac{1}{2} h_i f_m^2(x_i)\Big]+\Omega (f_m) \\ & = \sum_{i=1}^N \frac{1}{2} h_i\Big[ f_m(x_i)-(-\frac{g_i}{h_i}) \Big]^2+\Omega (f_m) + C \end{aligned}

在近似算法取分位数时，实际上XGBoost会取以二阶导 h_i为权重的分位数（Weighted Quantile Sketch），如下图表示的三分位。

4）列采样与学习率

XGBoost为了进一步优化效果，在以下2个方面进行了进一步设计：

列采样
- 和随机森林做法一致，每次节点分裂并不是用全部特征作为候选集，而是一个子集。
- 这么做能更好地控制过拟合，还能减少计算开销。
学习率
- 也叫步长、shrinkage，具体的操作是在每个子模型前（即每个叶节点的回归值上）乘上该系数，不让单颗树太激进地拟合，留有一定空间，使迭代更稳定。XGBoost默认设定为0.3。

5）特征缺失与稀疏性

XGBoost也能对缺失值处理，也对特征稀疏问题（特征中出现大量的0或one-hot encoding结果）做了一些优化。XGBoost用「稀疏感知」策略来同时处理这两个问题：

简单说，它的做法是将缺失值和稀疏0值等同视作缺失值，将其「绑定」在一起，分裂节点的遍历会跳过缺失值的整体。这样大大提高了运算效率。 0值在XGB中被处理为数值意义上的0还是NA，需要结合具体平台的设置，预处理区分开作为数值的0（不应该被处理为NA）和作为稀疏值的0（应该被处理为NA）。

依然通过遍历得到分裂节点，NA的方向有两种情况，在此基础上对非缺失值进行切分遍历。

如上图所示，若某个特征值取值为1，2，5和大量的NA，XGBoost会遍历以上6种情况（3个非缺失值的切分点×缺失值的两个方向），最大的分裂收益就是本特征上的分裂收益，同时，NA将被分到右节点。

3.XGBoost工程优化

1）并行列块设计

XGBoost将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。

2）缓存访问优化

特征值排序后通过索引来取梯度 g_i，h_i会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，XGBoost为每个线程分配一个单独的连续缓存区，用来存放梯度信息。

3）核外块计算

数据量非常大的情形下，无法同时全部载入内存。XGBoost将数据分为多个blocks储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。

为了进一步提高磁盘读取数据性能，XGBoost还使用了两种方法：

① 压缩block，用解压缩的开销换取磁盘读取的开销。
② 将block分散储存在多个磁盘中，提高磁盘吞吐量。

4.XGBoost vs GBDT

我们对之前讲解过的GBDT（参考ShowMeAI文章【GBDT算法详解】）和这里的XGBoost做一个对比总结：

GBDT是机器学习算法，XGBoost在算法基础上还有一些工程实现方面的优化。
GBDT使用的是损失函数一阶导数，相当于函数空间中的梯度下降；XGBoost还使用了损失函数二阶导数，相当于函数空间中的牛顿法。
正则化：XGBoost显式地加入了正则项来控制模型的复杂度，能有效防止过拟合。
列采样：XGBoost采用了随机森林中的做法，每次节点分裂前进行列随机采样。
缺失值：XGBoost运用稀疏感知策略处理缺失值，GBDT无缺失值处理策略。
并行高效：XGBoost的列块设计能有效支持并行运算，效率更优。

更多监督学习的算法模型总结可以查看ShowMeAI的文章 AI知识技能速查 | 机器学习-监督学习。

图解机器学习算法&实战 ◉ 从入门到精通

图解机器学习 | XGBoost模型详解

引言

1.算法原理可视化解读

1）监督学习中的一些重要概念

（1）监督学习核心要素

（2）监督学习进阶知识

（3）目标函数及偏差方差权衡

2）回归树（Regression Tree）和集成（Ensemble）

（1）回归树（Regression Tree）

（2）回归树集成（Regression Tree Ensemble）

（3）树集成方法

（4）Boosted Tree的模型和参数

（5）在单变量上学习Boosted Tree

（6）一般情形的Boosted Tree

3）Gradient Boosting（如何学习）

（1）解决方案

（2）目标函数变换

（3）重新定义树

（4）定义树的复杂程度

（5）重新审视目标函数

（6）计算叶子结点的值

（7）贪婪算法生成树

（8）如何处理分类型变量

（9）修剪和正则化

2.XGBoost核心原理归纳解析

1）目标函数与泰勒展开

2）XGBoost的正则化

3）节点分裂准则

（1）贪心准则

（2）近似算法

（3）加权分位数

4）列采样与学习率

5）特征缺失与稀疏性

3.XGBoost工程优化

1）并行列块设计

2）缓存访问优化

3）核外块计算

4.XGBoost vs GBDT

ShowMeAI系列教程推荐

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐