XGBoost算法学习总结

一、XGBoost原理详解

前面介绍了提升树算法,其实 XGBoost 就是一种特殊的提升树算法,准确的说它是一种梯度提升决策树(GBDT ,Gradient Boosting Decision Trees)。GBDT 与前面介绍的提升树方法主要的区别就是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中残差的近似值,来拟合一颗回归树,即:

XGBoost 就是对 GBDT 的实现,但是一般来说,gradient boosting 的实现是比较慢的,因为每次都要先构造出一个树并添加到整个模型序列中。

而 XGBoost 的特点就是计算速度快模型表现好,这两点也正是这个项目的目标。

二、XGBoost的目标函数

传统 GBDT 算法的目标函数只有损失函数这一项,而 XGBoost 在此基础上进行了改进,增加了正则项以防止模型过度复杂:

$$Obj =∑^N_{i=1}L(y_i,\hat{y}i)+∑{m=1}^M\Omega(f_m), f_m \in F$$

在这里我们不能够使用 SGD 算法进行优化,因为我们需要寻找的新的函数 f 是一棵树,而不仅仅是一个数值向量。解决方案也是和提升树一样,采用 Boosting 的思想,从一个常量(通常是0)进行预测,每次添加一个新的预测残差的函数
$f_0(x)=0$
$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
$f_M(x)=∑^M_{m=1}T(x;\Theta_m),m=1,2,…,M$

由以上公式我们可以知道,我们所要做的唯一的一件事就是寻找一个方法来确定第$m$轮的函数$f_m(x_i)$。但是怎么确定每一轮迭代的函数$f_m(x)$呢,答案是优化!

三、XGBoost算法学习过程

第$m$轮迭代的预测结果为:
$$\hat{y}_m(x_i)=\hat{y}_{m-1}(x_i)+f_m(x_i)$$

目标函数为:

$Obj_m =∑^N_{i=1}L(y_i,f_m(x_i))+∑_{m=1}^M\Omega(f_m)$

$=∑^N_{i=1}L(y_i,f_{m-1}(x)+f_m(x_i)+\Omega(f_m))+const$

推导到这里,应该就清楚了,我们的目标就是最小化上式去除常量的部分。那么我们首先来考虑一下损失函数为平方(Square)损失的情况,即:

$Obj_m =∑^N_{i=1}(y_i,f_{m-1}(x_i)+f_m(x_i))^2+\Omega(f_m)$

$=∑^N_{i=1}[2(f_{m-1}-y_i)f_m(x_i)+f_m(x_i)^2]+\Omega(f_m)+const$

有上述分析,我们知道对于目标函数当我们将损失函数设定为平方损失的时候,目标函数最终可转化为一个关于 $f_m(x)$ 的二次函数,这时候我们很容易对其进行优化,甚至可以求出它的解析解。

但是,为了算法的通用性和可扩展性的考虑,XGBoost 并没有指定损失函数为平方损失函数,此时我们会发现其实目标函数的表达是还是相当复杂的:

$$Obj_m=∑^N_{i=1}L(y_i,f_{m-1}(x_i)+f_m(x_i))+\Omega(f_m)+const$$

这时候该怎么做呢,陈天奇大神想出了我们高数中学过的泰勒展开式,具体怎么做的呢?

三、泰勒展开时近似损失函数

为了更好的介绍 XGBoost 中是如何使用泰勒展开式来近似损失函数的,首先让我们回顾一下泰勒展开式的二阶形式:

$$f(x+\Delta x)=f(x)+f’(x)\Delta x+\frac 12f’’(x)\Delta x^2+R(\Delta x)$$

其中$R(\Delta x)$表示$\Delta x$的高阶无穷小。因此,有:
$$f(x+\Delta x)\approx f(x)+f’(x)\Delta x+\frac 12f’’(x)\Delta x^2$$

有了泰勒公式,我们给出如下定义:

$$g_i=\partial _{f_{m-1}(x_i)}L(y_i, f_{m-1}(x_i))$$
$$h_i=\partial^2 _{f_{m-1}(x_i)}L(y_i, f_{m-1}(x_i))$$

这里我们把$L(y_i,f_{m-1}(x_i))$看成是$f_{m-1}(x_i)$为自变量的函数,因此$g_i$和$h_i$为其一阶导和二阶导数(其实是偏导),并且我们将目标函数中的$f_m(x_i)$看成上式中自变量的增量$\Delta x$,因此将目标函数按$f_{m-1}(x_i)$进行泰勒展开,得到:

$Obj_m=∑^N_{i=1}L(y_i,f_{m-1}(x_i)+f_m(x_i))+ \Omega(f_m)+const$
$\approx ∑^N_{i=1}[L(y_i,f_{m-1}(x_i))+g_if_m(x_i)+\frac 12h_if^2_m(x_i)] + \Omega(f_m)+const$

去除掉常量部分,我们可以得到新的目标函数:
$$Obj_m=∑^N_{i=1}[g_if_m(x_i)+\frac 12 h_if^2_m(x_i)]+\Omega(f_m) $$

这样做的好处是:

理论上的好处:使得我们更加清楚的知道我们在学习什么,以及更好的收敛性;
工程上的好处

  1. $g_i$和$h_i$都来自于损失函数的定义
  2. 函数的学习过程仅仅通过$g_i$和$h_i$依赖于目标函数
  3. 可以利用不同的模块分开实现不同的损失函数,例如平方损失函数和 logistic 损失函数,这样损失函数不会受限制。

五、正则化的处理

目标函数中正则化项存在的原因是为了限制模型的复杂度,让模型在训练集上能够取得较好的结果的前提下尽可能地简单。而前面我们也提到了,在 XGBoost 中,对于采用前向分布方法一步步迭代的优化时,我们模型的复杂度就是当前要定义的决策树的复杂度。

1. 决策树函数的定义

为此,我们首先重新定义树:我们将树定义为一个该树中所有叶子节点的值的向量。并且,每个叶子的索引映射函数映射实例到每个叶子节点上:

2. 定义决策树的复杂度

我们将决策树的复杂度,也就是目标函数定义如下:
$$\Omega (f_m)=\gamma T+\frac 12\lambda∑^T_{j=1}w_j^2$$

其中,$T$树中叶子结点的个数计算如下:

3. 新目标函数的优化

首先,我们对叶子节点$j$中的实例进行如下定义:
$$I_j={i|q(x_i)=j }$$
此时目标函数为:
$$Obj_m\approx ∑^N_{i=1}[g_if_m(x_i)+\frac 12 h_if_m^2(x_i)]+\Omega(f_m)+const$$
$=∑^N_{i=1}[g_iw_{q(x_i)}+\frac 12h_iw^2_{q(x_i)}]+\gamma T+\frac 12 \lambda ∑^T_{j=1}w^2_j$
$=∑^T_{j=1}[(∑_{i\in I_j}g_i)w_i+\frac 12(∑_{i \in I_j}h_i+\lambda)w^2_j]+\gamma T $

首先,我们进行如下定义:

$$G_j=∑_{i \in I_j}g_i,H_j=∑_{i \in I_j}h_i$$

进一步简化目标函数:
$$Obj_m=∑^T_{j=1}[G_jw_j+\frac 12(H_i+\lambda)w^2_j]+\gamma T$$

众所周知,对于一元二次函数,由如下两条结论:
$$arg \min _xG_x + \frac 12Hx^2=-\frac GH,H>0$$
$$\min _xG_x+\frac 12Hx^2=- \frac {G^2}{2H}$$

因此对于目标函数进行最小化,当$w_j=-\frac {G_j}{H_j+\lambda }$时,我们得到:
$$\min _{Obj_m}=∑^T_{j=1}[G_jw_j+\frac 12(H_j+\lambda)w^2_j]+\gamma T$$
$=-\frac 12 ∑^T_{j=1}\frac {G^2_j}{H_j+\lambda }+\gamma T$

至此,对于第 t 轮的一颗已经分裂好的决策树,我们能够求出其对应的最小化的目标函数。但是到目前为止,到底如何进行分裂我们还不知道具体的做法,接下来让我们一起学习 XGBoost 是如何寻找分裂点的。

六、构建决策树

1. 决策树的生成策略

对于回归决策树来说,在目标函数已经确定的情况下,接下来我们的问题是如何寻找对于当前训练样本的最优的决策树结构。当然,我们最容易想到的是穷举法。如果按照穷举法,我们列出所有的可能的决策树的结构$q$,然后基于决策树结构$q$去计算它的目标函数值,在计算完所有可能的决策树结构后,选择目标函数值最小的决策树结构$\hat q$作为最终决策树。

虽然理论上来说,穷举法能够寻找到最优的决策树结构,但是在有限的时间内我们无法去寻找到最优的决策树结构,因为可能的树结构有无穷多种。因此,在应用中我们采用的是贪心的策略来一步步地增长树的结构。也就是从根节点开始,不断地进行递归地分裂,直至在给定的准则下无法进行分裂为止。所以,接下来我们需要知道递归时如何进行合适并有效地分裂当前节点。

2. 寻找最优分裂点

对于一个叶子节点,如何进行分裂我们需要遵循的原则是分裂后的两颗子树的最优目标函数值之和要小于未分裂之前的父节点,为了叙述方便我们定义如下的目标函数值的 “增益”:\
$$Gain=\frac 12[\frac {G^2_L}{H_L+\lambda } + \frac {G^2_R}{H_R+\lambda } - \frac {(G_L+G_R)^2}{H_L+H_R+\lambda } -\gamma ]$$
上式表示的是在某个节点分裂前的目标函数值与分裂后的目标函数值的差值,由于我们的目标是寻找到最优的决策树,也就是说只有当$Gain$的值为正时我们才会选择进行分裂。

分裂点寻找方法

  • 对每一个待分裂节点,枚举出所有的特征;
  • 对于每一个特征,根据该特征将所有的实例进行排序;
  • 使用线性扫描的方法计算该特征的每个可能的值作为分裂点时对应的 $Gain$对所有特征,使用上述扫描过程中找到的 $Gain$ 值大时特征及其对应的取值作为分裂点,将当前节点一分为二。

3. 离散变量处理

传统的 GBDT 算法对连续型变量和离散型变量是进行分开处理的。例如 Spark 中的 GBDT 就是这样的,当我们的实例特征中有离散型变量的时候,就需要通过参数指定该离散型变量的种类,这样使得算法的用户友好性变得十分的糟糕。

而 XGBoost 在设计时就考虑到了这一点。实际上,我们不需要将离散型特征变量进行分开处理,XGBoost 使用 one-hot 编码的方式对离散型变量进行处理。

4. 剪枝策略

  • 前剪枝
    • 当最优分裂点对应的增益值为负时停止分裂
    • 但是这也会存在问题,即将来的某个时刻能够获取更高的增益
  • 后剪枝
    • 将决策树增长到它的最大深度,递归的进行剪枝,剪去那些使得增益值为负值的叶子节点。

5. 前向分步的步长

在 XGBoost 提升过程中,每产生一颗对当前残差最优化的决策树 $f_m(x)$时,并不是直接将决策树$f_m(x)$加入到模型中,而是对它乘以一个固定的算法参数 $\eta$之后才加入到模型中:

$$f_m(x)=f_{m-1}(x)+\eta f_m(x)$$

这样做的好处是防止单步决策树过拟合,以减少每棵树对最终木星的影响。

七、XGBoost构建步骤

输入:训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)},x_1 \in \chi ⊆ R^n$,$y_i \in Y ⊆ R$;
输出:梯度提升树$\hat{f}(x) = \hat f_M(x)$;

(1)初始化$f_0(x)=0$

(2)对$m=1,2,…,M$,依次进行循环迭代:

(a)对每个样本点,分别计算:
$$g_i= \partial _{f_{m-1}(x_i)}L(y_i,f_{m-1}(x_i))$$
$$h_i= \partial ^2_{f_{m-1}(x_i)}L(y_i,f_{m-1}(x_i))$$
(b)使用贪心策略构建一棵树$f_m(x)$,以使得下列的目标函数最小化:
$$Obj=-\frac 12 ∑^T_{j=1}\frac {G_j^2}{H_j+\lambda }+\gamma T$$
(c)更新:$f_M(x)=f_{m-1}(x)+\eta f_m(x)$
(3)得到XGBoost提升树:
$$f(x)=f_M(x)=∑^M_{m=1}\eta f_m(x)$$

八、XGBoost优缺点

1. 优点

  1. 正则化

XGBoost 在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score 的 L2 模的平方和。从 Bias-variancetradeoff 角度来讲,正则项降低了模型的 variance,使学习出来的模型更加简单,防止过拟合,这也是 XGBoost 优于传统 GBDT 的一个特性。

  1. 并行处理

XGBoost 工具支持并行。Boosting 不是一种串行的结构吗?怎么并行的?注意 XGBoost 的并行不是 tree 粒度的并行,XGBoost 也是一次迭代完才能进行下一次迭代的(第 t 次迭代的代价函数里包含了前面 t-1 次迭代的预测值)。XGBoost 的并行是在特征粒度上的。

我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),XGBoost 在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个 block 结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

  1. 灵活性

XGBoost 支持用户自定义目标函数和评估函数,只要目标函数二阶可导就行。

  1. 缺失值的处理

对于特征的值有缺失的样本,XGBoost 可以自动学习出它的分裂方向。

  1. 剪枝

XGBoost 先从顶到底建立所有可以建立的子树,再从底到顶反向进行剪枝。比起 GBM,这样不容易陷入局部最优解。

  1. 内置交叉验证

XGBoost 允许在每一轮 Boosting 迭代中使用交叉验证。因此,可以方便地获得最优 Boosting 迭代次数。而 GBM 使用网格搜索,只能检测有限个值。

2. 缺点

虽然说 XGBoost 在 Kaggle 比赛中获得了不错的成绩,但并不代表 XGBoost 是一个完美的算法,它当然也有自己的缺点和不足之处:

  1. 算法参数过多

调参复杂,需要对 XGBoost 原理十分清楚才能很好的使用 XGBoost。

  1. 只适合处理结构化数据

相对于深度学习算法来说,XGBoost 算法只适合处理结构化的特征数据,而对于类似图像中的目标检测等任务重的非结构化数据没有很好的处理能力。

  1. 不适合处理超高维特征数据

XGBoost 算法对于中低维数据具有很好的处理速度和精度,但是对于例如大规模图像物体识别,或者是推荐算法的某些场景中会出现的超高维特征的数据就无能为力了,这时候我们就需要借助于深度学习等算法。