XGBoost 详细讲解-xb1破解

 

XGBoost[1]（eXtreme Gradient Boosting），是一种 Boosting 算法，他对 GBM 算法做了大量的理论和工程优化，准确率和运行效率都大大提升。XGBoost 通常使用 CART 作为基学习器。不熟悉 CART 和 GBM 的朋友，推荐先看下我之前写的两篇文章。

目录

一、整体流程 / 正则化的目标函数、二阶泰勒展开求解、缩减和列采样

二、树节点分裂 / 精准贪心算法、近似算法、加权分位数缩略图、稀疏感知

三、效率优化 / 分块并行、缓存感知访问、块的核外计算

一、整体流程

1. 正则化的目标函数

XGBoost 是一种加法模型，它包含 KK 个基学习器，每个基学习器会对第 ii 个输入样本 xix_i 进行预测，然后把每个预测结果 fk(xi)f_k(\mathbf{x}_i) 相加，作为最终的输出 y^i\hat{y}_i 。

基学习器可以选择 CART 或者线性函数，通常都用 CART，这里就以 CART 为例。那么当基学习器为 CART 时，上式标蓝的 fk(xi)f_k(\mathbf{x}_i) 可以写的更具体一些，如下式。这里去掉了脚标。

这个式子有点绕，我解释下：假设决策树有 TT 个叶子，w=(w1,w2,⋯,wT)\boldsymbol{w} = (w_1, w_2, \cdots, w_T) 是由各个叶子权重组成的权重向量。角标 q(x)∈{1,2,⋯,T}q(x) \in \{1,2,\cdots,T\} 代表具体的叶子序号，这个 qq 函数就代表决策树的决策过程。所以 wq(x)w_{q(\mathbf{x})} 就是输入 x\mathbf{x} 被 qq 函数分到的叶子节点的权重。举个例子，比如像下图，有个输入 xi\mathbf{x}_i， qq 函数对它做出判断，认为它应该被分到 3 号叶子节点，这样函数 f(x)f(\mathbf{x}) 就会把 3 号节点的权重 w3w_3 作为输出结果返回。

XGBoost 的目标函数由损失函数 ll 和正则项 Ω\Omega 组成：

损失函数这一项就是让预测值更加接近真实值，但过于接近可能会导致过拟合，所以增加一个正则项，控制基学习器的模型复杂度。对于 CART，正则项为：

因为我们是想让目标函数尽可能地小，所以正则项也是越小越好，这样叶子数目 TT 和权重向量 w\boldsymbol{w} 也是越小越好。如此一来，CART 的模型结构会简单很多，同时权重也不会太大。

2. 二阶泰勒展开求解

现在假设我们处在前向分布算法的第 tt 步，前面 t−1t-1 步的模型和预测结果都已经得到了，那么当前的预测结果可以表示为：

目标函数可以写成：

那么现在该如何求出使目标函数最小的 ftf_t 呢？我觉得可以像 GBDT 一样计算目标函数梯度，然后让新的 CART 去拟合负梯度。不过 XGBoost 用了更优的方法，有点类似牛顿法，但又不完全一样。牛顿法是把目标函数在当前点做二阶泰勒展开，然后求解二次方程最优点。而 XGBoost 是在 y^i(t−1)\hat{y}_i^{(t-1)} 处只对损失函数这项做了二阶泰勒展开，之后再求解最优点。那么损失函数在进行了二阶泰勒展开后，目标函数变成这样：

其中 l(yi,y^i(t−1))l(y_i, \hat{y}_i^{(t-1)}) 是常数，可以跟最后的常数项合并，同时目标函数中的常数项其实对 ftf_t 求解没有影响，所以可以删掉全部常数，化简结果如下：

一下子清爽了！但是我们现在还没法求出他的最优点，因为正则项没有 ft(xi)f_t(x_i) ，损失函数和正则项形式上是不一致的。所以公式还要继续变形、展开。

定义一个 Ij={i|q(xi)=j}I_j = \left\{ i|q(x_i)=j \right\} ，表示被分到 jj 号叶子节点的输入样本索引集合。那么目标函数可以转换为：

为了书写方便，用 GjG_j 和 HjH_j 分别代替 ∑i∈Ijgi\sum_{i \in I_j} g_i 和 ∑i∈Ijhi\sum_{i \in I_j} h_i ，公式化简后如下：

我们发现 ∑\sum 里面的每一项都是关于 wjw_j 的二次方程，可以令他的导数等于 0，求出最优权重 wj∗w_j^* 。

把它代入目标函数中，权重变量就消掉了。

现在 L~(t)\mathcal{\tilde L}^{(t)} 就可以像基尼指数和平方误差一样，指导第 tt 棵决策树分裂了。我们希望每次节点分裂都能使目标函数降低最多，降低程度的表达式如下：

所以 IL,IRI_L,I_R 如何划分完全根据 Lsplit\mathcal{L}_{split} 来决定。

3. 缩减（shrinkage）和列抽样

这里的缩减和 GBDT 里的缩减一样，都是为了降低单棵树的影响，给后面的树留有空间。因此引入一个学习率 η\eta ，用它去乘每步生成的 ft(x)f_t(x) 。

列抽样在 GBDT 和随机森林里都有用到，它可以牺牲偏差来降低方差。实现方法就是在分裂节点的时候只用一部分特征。

二、树节点分裂

节点分裂的目标是找出一个特征，按照这个特征的某个节点分裂后，能够使目标函数降低最多。所以这里面有两层循环，外层是特征遍历，内层是特征值遍历。特征遍历没得说了，只能一个一个找，但是特征值遍历可以优化一些，缩短寻找最优分裂节点的耗时。

我们分四步来看节点分裂：

精准贪心算法：每个位置都试下，精准定位最优分裂节点近似算法：按分位数查找，找出近似最优的分裂节点加权分位数缩略图：按 hh 的加权分位数，找出比前一种更好些的分裂节点稀疏感知分裂：针对存在稀疏性或缺失值的数据做了一点优化

首先了解下最基本的方法——精准贪心算法

1. 精准贪心算法

首先，每个特征要排序，排序过后，分裂节点左边和右边的一阶导数加和 GG 与二阶导数加和 HH 就好计算了。回顾下他俩的定义：

你应该注意到了， gi,hig_i, h_i 是根据 t−1t-1 轮结果计算的，当前是在求解第 tt 轮的树结构，所以 gi,hig_i, h_i 在当前是已知的、计算好的。

精准贪心算法如下图，红线是分割线，在每一个地方都分割一次，计算一次 Lsplit\mathcal{L}_{split} 。分割线左侧的 g,hg, h 分别加起来就是左侧 GL,HLG_L, H_L ，分割线右侧的 g,hg, h 分别加起来就是右侧 GR,HRG_R, H_R 。

那么遍历一遍后选择目标函数降低最多的分裂点进行节点分裂，也就是在 Lsplit\mathcal{L}_{split} 最大的分裂点处进行节点分裂。

2. 近似算法

精准贪心算法的问题显而易见：候选节点太多，耗时太长。因此有了近似它的算法。最优切分点没必要找的那么精确，因为我们训练的基学习器是弱学习器，所以没必要让他学得特别准，后面还有 Boosting 来提高他的准确率呢。那么基于这种想法，可以把这个候选节点范围缩小下，不再枚举，而是只选用分位点。比如下图选择了两个三分位点，也可以用四分位点或者其他更多的点。本质上就是把特征分到多个桶里，让数据粒度变粗，只跟桶打交道，降低计算量。

这里存在一个划分时机的问题，是在一棵树分裂前就按分位数给划分好（全局分裂点），还是在每个节点分裂时进行划分（局部分裂点）？两者都可以，但是后者需要的划分次数更少，因为后者对父节点用过的特征会分的更细。

比如 1 号特征在父节点用过一次，那么对于局部分裂情况，孩子节点再用这个特征的时候是在它分到的那部分样本里重新选择候选分裂点；而全局分裂是在一开始就把候选分裂点固定下来，当孩子节点再次使用时不会在细分样本集合里重新选择。

作者对于全局分裂点选取和局部分裂点选取这两种方法进行了实验测试，图中 eps 是后面会提到的参数，1/eps 可以近似代表前面提到的分位数个数。可以看到，全局分裂模式在分的细时能够和精准贪心算法获得一样的精度，而局部分裂模式大概分一下，在训练后期就能获得同等精度。

3. 加权分位数缩略图

前面用分位数选点的方法还有优化的空间。分位数选点的方法没有关注到误差大的样本，他对于排序后的所有样本一视同仁，这样其实不太好。如果能够在误差比较大的样本处分的更细一些，效果会更好。所以就有了加权分位数缩略图的想法，用权重来表示误差大小。XGBoost 文章中用的二阶导数 hh 代表权重， hh 累加到一定值的时候做一次切分。比如下图是累加到 0.3 的时候做一次切分。XGBoost 在这里还做了些细节上的工作，比如如何通过 eps 作为 hh 累加和的阈值，来选择加权分位点，具体可以参考原文。

为什么选择 hh 作为权重呢？可以从两个角度来看。

第一个角度是从目标函数的形式上来看。原来的目标函数可以经过恒等变换，配出平方项。

Σ\Sigma 里面是一个关于 −gihi-\frac{g_i}{h_i} 的加权平方误差，当 hih_i 大的时候，这个平方误差在目标函数中所占比例相对来说就会大一些，所以会把 hh 作为权重。

第二个角度是从 hh 的表达式来看。当损失函数选择用于回归的平方误差时，即

l(yi,y^(t−1))=(yi−y^(t−1))2l(y_i, \hat{y}^{(t-1)}) = \left( y_i - \hat{y}^{(t-1)} \right)^2 \\

h=2h=2 是个常数，退化为分位数选点；但是当损失函数选择用于分类的交叉熵时，即

l(yi,y^(t−1))=−[ylog(p)+(1−y)log(1−p)]p=11+e−y^(t−1)l(y_i, \hat{y}^{(t-1)}) = -\left[ ylog(p) + (1-y)log(1-p) \right] \\ p = \frac{1}{ 1+e^{ -\hat{ y }^{ (t-1) } } }

h=p(1−p)h=p(1-p) ，当 p=0.5p=0.5 附近时 hh 最大，而预测概率等于 0.5 就意味着这个样本点在分类过程中左右摇摆，需要重点关注下， hh 的大小刚好能够用来反映这个摇摆程度，所以选择 hh 作为权重。

4. 稀疏感知

机器学习经常会碰到数据稀疏的问题，有三种情况会导致数据稀疏：

数据存在大量缺失值数据中存在大量的 0 元素特征工程中使用了 one-hot 编码，产生了大量的 0

所以让算法能够感知数据的稀疏模式是非常重要的。XGBoost 的解决方法是在每个节点中设置一个默认方向，缺失值或者 0 元素直接走默认方向，不参与树模型的学习。比如在下图中就是直接走默认的红色虚线的方向。

这个默认方向该怎么选呢？两边都试试，看看哪边带来的 Lsplit\mathcal{L}_{split} 更大，就选哪边。具体来说就是在节点分裂的时候，把缺失值或 0 元素样本先分到左边的节点计算下 Lsplit\mathcal{L}_{split} ，然后再分到右边的节点计算下 Lsplit\mathcal{L}_{split} ，选择大的那边作为默认方向。

对于一个正在分裂的节点来说，因为所选特征对应的稀疏样本其实都被当成了一类，所以在找最优分裂点的时候是不需要考虑稀疏值的，只考虑非稀疏值即可，从而减小了计算量，缩短了运算耗时。

作者做了一个稀疏数据的实验，用了稀疏感知算法，速度能够提升 50 倍左右。

三、效率优化

1. 分块并行

决策树学习过程中，最耗时的部分是分裂时对数据的反复排序。为了提高速度，XGBoost 采用了空间换时间的方法。对于一列特征，它创建了等量的指针，每个指针都跟一个特征值绑定，并指向对应样本，按照特征大小排序，把每一个特征的排好序的指针保存在块结构中，就实现了训练前对特征排序的目标，这样速度提升了，但是也因此需要额外空间存储指针。分条来说，块结构的设计有以下特点：

采用 CSC（Compressed Sparse Column Format）这种稀疏格式存储数据存储的特征已排好序存储了指向样本的指针，因为要存取一阶导和二阶导等信息由于 CSC 是按列存储的，所以可以在每次分裂时对特征使用多线程并行计算

2. 缓存感知（Cache-aware）访问

提出的块结构能够优化节点分裂的时间复杂度，但是在索引样本时，存在对内存的非连续访问问题。这是因为我们是按特征大小顺序对样本进行访问，但样本不按这个顺序。对内存的非连续访问将降低 CPU 的缓存命中率。XGBoost 针对精准贪心算法和近似算法设计了两种不同的优化策略。

对于精准贪心算法，采用缓存感知的预读取算法进行解决。在内存中开辟一个新的缓冲区（buffer），在 CPU 访问数据前，先把它要访问的数据存在这个缓冲区，把非连续的数据变成连续数据，这样就能提高 CPU 的缓存命中率，为 CPU 节省了一定的数据读取时间。

对于近似算法，包括加权分位数和稀疏感知这两种情况，通过降低块大小解决这一问题。缓存命中率低，一个原因是块太大了，没法全部存进缓存，如果把块的大小降到 CPU 缓存可以完全容纳的程度，就不会出现没命中了。但是块太小又会导致并行效率低。作者在尝试了多种块大小后，选择了最优的 2^{16} ，每个块存储 2^{16} 个样本。实验结果如图。

3. 块的核外（Out-of-core）计算

当数据没办法被一次全部读入内存时，就需要用到核外计算方法，单开一个线程从硬盘上读取需要用到的数据，解决内存不够地问题。但是从硬盘读取数据相对于处理器来说是很慢的，所以 XGBoost 采用了两种方法平衡两者速度：

块压缩。对于行索引，用当前索引减去开始的块索引，前面提到块大小为 2^{16} ，所以用 16 位的整数存储这个算出来的偏移，用这个偏移替代原先更占空间的索引。块分片。把数据分开存储到不同的硬盘上，等用的时候多个硬盘一起开工，提高读取速度。

XGBoost 是个好算法，但时代在进步。从算法速度上来看，它已经被 LightGBM 超越了。

参考

^XGBoost: A Scalable Tree Boosting System https://dl.acm.org/doi/10.1145/2939672.2939785