Xgboost

XGBoost

XGBoost全称为eXtreme Gradient Boosting, 是大规模并行boosting tree的工具.

加法模型

XGBoost和GBDT两者都是boosting方法. XGBoost也是一个加法模型. 假设第$t$次迭代要训练生成$f_{t}(x)$树, 并假设$\hat{y}_{i}^{(t)}$是$t$轮迭代后, 对样本$i$的输出值, 则根据加法模型, 有:

$$\hat{y}_{i}^{(t)}=\sum_{k=1}^{t} f_{k}\left(x_{i}\right)=\hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)$$

与GBDT在这里并没有区别.

目标函数

GBDT对损失函数/目标函数在函数空间上求负梯度, 然后拟合得到的负梯度, 得到一棵树, 完成一步优化. 那么XGBoost是怎么进行一步优化的呢.

预测偏差

首先确定XGBoost使用的损失函数. 假设共有$n$个训练样本, 对于第$i$个样本, 真实值为$y_i$, 模型的预测值为$\hat{y}_{i}$, 他们之间的偏差使用指定的损失函数$l$度量, 那么训练集中所有样本的总损失记为:

$$L=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}\right)$$

正则项

上面部分度量的是模型的偏差. 此外, XGBoost还度量了模型的方差, 是通过像损失函数中添加正则项来实现, 用于防止过拟合, 从而起到减小方差的作用.

具体来说, 对于每棵树$f_i$, 使用函数$\Omega(f_i)$来度量这棵树的复杂度. 从两个方面度量:

叶子节点的输出值

从之前GBDT中我们知道, 无论是回归任务还是分类任务, 使用的树的叶子节点的输出值都是一个连续的数值. 我们假设拟合生成的一棵树共有$T$个叶子节点, 对第$j$个叶子节点, 其输出值是$w_j$. XGBoost想要控制每个叶子节点的输出大小, 单个节点过大的输出值将带来泛化性的减弱, 因此使用所有节点权重所组成的向量的$L_2$范式来进行正则化:

$$\sum_{j=1}^{T}w_j^2$$

叶子结点的数量

衡量一棵树本身的复杂度, 相对来说分叉越少的树越简单, 因此使用叶子节点的数量$T$也作为其中的正则项.

综合

将叶子结点的数量和叶子节点的输出值结合起来, 在加上权值超参数, 衡量一棵树$f_t$复杂度的表达式为:

$$\Omega\left(f_{t}\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}$$

定义损失函数

XGBoost的损失函数因此由预测偏差和树复杂度的正则项组成, 即:

$$\Phi=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right)$$

前一项是所有样本的损失值之和, 后一项是所有树的复杂度之和.

在第$t$次迭代中, 将要求得的树为$f_t$带入, 有$\hat{y}_{i}^{(t)}=\hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)$, 再带入到损失函数中:

$$\begin{aligned} \Phi^{(t)} &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t)}\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)+\Omega\left(f_{t}\right)+\text { constant } \end{aligned}$$

其中的$\text { constant }$项是前$t-1$树的复杂度衡量, 这些树均是已经固定的, 对应的复杂度值也是固定的.

泰勒展开

与GBDT相似的是, 在生成当前步的弱学习器时, 仍然是在函数空间上考虑移动一小步, 达到最有效降低损失函数值的效果, 而这一小步正是要生成的弱学习器.

与GBDT不同的是, XGBoost不直接拟合负梯度生成一棵树, 而是深入到单棵树每个节点分裂过程, 通过损失函数推导出分裂的最优解, 以及分裂后叶子节点的最优取值.

而这都要借助泰勒公式. 对于函数$f(x)$在点$x$展开到二阶, 有:

$$f(x+\Delta x) \approx f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}$$

类比到XGBoost的损失公式, 在函数空间中, 对衡量单个样本损失的$l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)$在$\hat{y}_{i}^{(t-1)}$出进行展开, 此时我们要训练的第$t$棵树$f_{t}\left(x_{i}\right)$对应上面的微小变化$\Delta x$, 得到:

$$l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)=l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)$$

这里的$g_i$是损失函数的一阶导, $h_i$是损失函数的二阶导, 并假设这里的损失函数$l$是平方损失函数, 则有:

$$\begin{array}{c} l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)=\left(y_{i}-\hat{y}_{i}^{(t-1)}\right)^{2} \\ g_{i}=\frac{\partial l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)}{\partial \hat{y}_{i}^{(t-1)}}=-2\left(y_{i}-\hat{y}_{i}^{(t-1)}\right) \\ h_{i}=\frac{\partial^{2} l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)}{\partial\left(\hat{y}_{i}^{(t-1)}\right)^{2}}=2 \end{array}$$

将预测偏差的展开形式带入到原损失函数的公式中:

$$\Phi^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{t-1}\right)+g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right)+\text { constant }$$

在第$t$步时, $\hat{y}_{i}^{t-1}$是一个已知的值, 因此之前模型的损失$l\left(y_{i}, \hat{y}_{i}^{t-1}\right)$也是一个常数, 将其与常数项合并. 这些常数对优化损失函数不会造成影响, 因此省略掉, 损失函数变为:

$$\begin{aligned} \Phi^{(t)} &\simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &= \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \end{aligned}$$

所以在每一次迭代中, 我们需要求出损失函数的一阶导和二阶导的值, 拟合出最合适的$f_t$, 完成优化目标.

如何拟合一棵树

重新定义决策树

Xgboost拟合树的过程与GBDT中传统的CART决策树拟合负梯度的过程不同, 它在树的生成过程中, 分裂是与样本的一阶梯度, 二阶梯度深度耦合的.

用符号公式重新定义一棵决策树:

• 样本到叶子结点的映射关系记为$q$, 本质是树的分支结构

• 叶子结点的权重向量为$w$

一棵决策树可以记为:

$$f_{t}(x)=w_{q(x)}, \quad w \in \mathbf{R}^{T}, q: \mathbf{R}^{d} \rightarrow\{1,2, \cdots, T\}$$

如下图所示:

可以看到最终使用的决策树与GBDT使用的CART决策树并无二致.

一阶梯度和二阶梯度是如何耦合到树的分裂过程中的呢?

叶子结点归组

将所有属于叶子节点$j$的样本作为一个样本集合, 记为$I_{j}=\left\{i \mid q\left(x_{i}\right)=j\right\}$. 由于所有样本最终都会落在叶子节点上, 那么Xgboost的损失函数可以从样本角度, 切换到叶子节点的角度, 对叶子节点循环累积:

$$\begin{aligned} \Phi^{(t)} & \simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}$$

将一个叶子节点上所有样本的一阶梯度和二阶梯度分别加和, 得到$G_{j}=\sum_{i \in I_{j}} g_{i}$, $H_{j}=\sum_{i \in I_{j}} h_{i}$. 一阶导和二阶导都是标量常数, 代入后损失函数变为:

$$\Phi^{(t)} = \sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T$$

叶子节点最佳权重

在看树节点如何分裂之前, 先确定在得到完整的树之后, 叶子节点的输出权值应该是多少. 且叶子节点之间相互不影响, 可以以一个叶子节点为例进行分析.

对于一个叶子节点, 损失函数为:

$$G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2} + \gamma$$

要求解未知数输出权值$w_j$, 对于二元一次方程, 使用最值公式求出最值点和对应的最值:

$$w^{*}_j = -\frac{b}{2a} = -\frac{G_j}{H_j+\lambda}$$

对应的叶子节点$j$的最小损失值为:

$$-\frac{1}{2} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma$$

因此在确定了树的分支结构后, 对应于叶子节点的最小损失, 其输出权值也就固定了. 权值和对应的最小损失都是有解析解的, 使用这个叶子节点下的所有样本计算.

接下来就要讨论如何进行节点分裂了.

分裂的贪心算法

当树的深度为0时, 可以看做所有的样本都在一个叶子节点上, 现在的目标是分裂为两个节点, 生成两个新的叶子节点, 将样本映射到新的叶子节点上.

如何分裂. 分裂的目标应当是分裂后两个叶子节点的损失应当小于分裂前的节点, 且减小程度应当最大. 根据上面一小节, 对于一个叶子节点, 其损失函数为:

$$-\frac{1}{2} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma$$

我们把分裂后映射到左节点的所有样本一阶梯度之和记为$G_L$, 右节点为$G_R$, 相应的, 左节点二阶梯度之和记为$H_L$, 右节点为$H_R$.

因此, 一个节点分裂前, 该节点的损失大小为:

$$-\frac{1}{2}\left[\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]+\gamma$$

分裂后左右节点的损失函数之和为:

$$-\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}\right]+2 \gamma$$

将分裂后左右节点的损失之和, 减去分裂前节点的损失, 得到一个正数, 将其称为分裂收益:

$$\text { Gain }=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma$$

有了评价分裂提升效果的方法后, 就可以枚举所有分裂方案, 然后挑出分裂收益最大的方案, 作为本次分裂的依据. 具体来说:

• 遍历所有特征

  • 对于每个特征, 把属于该节点的训练样本根据该特征值进行升序排列, 通过线性扫描的方式来决定该特征的最佳分裂点, 并记录该特征的分裂收益

  • 选择收益最大的特征作为分裂特征, 用该特征的最佳分裂点作为分裂位置, 在该节点上分裂出左右两个新的叶节点, 并为每个新节点关联对应的样本集

• 递归执行直到满足终止条件为止

这里补充一点, Xgboost模型包中, 训练得到的模型, 有对特征重要程度的衡量, 其根据就是分裂过程中的特征收益.

对于每次分裂, 我们都需要枚举所有特征可能的分割方案, 如何高效地枚举所有的分割呢. 假设我们要枚举某个特征所有$x \lt a$的样本, 对于某个特定的分割点$a$我们要计算左边和右边的导数之和.

对于所有的分裂点$a$, 只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和, 然后用上面的公式计算每个分割方案的收益就可以了.

另外, 观察分裂后的收益, 我们会发现节点划分不一定会使得结果变好, 因为我们有一个引入新叶子的惩罚项, 也就是说引入的分割带来的增益如果小于一个阈值的时候, 我们可以剪掉这个分裂, 这就是正则项带来的剪枝, 进而带来的泛化性.

分裂的近似算法

贪心算法可以得到最优解, 但当数据量太大时则无法读入内存进行计算, 且计算量大计算缓慢, 近似算法主要针对贪心算法这一缺点给出了近似最优解.

贪心算法对于每个特征, 考虑所有分裂的可能性, 所以要排序后, 依次计算所有可能分裂点的分裂收益. 近似算法认为, 不需要考虑到每个分裂点这么细致, 只需要考察分位点即可达到近似的效果, 可以减少计算复杂度.

该算法首先根据特征分布的分位数提出候选划分点, 然后将连续型特征映射到由这些候选点划分的桶中, 聚合统计信息找到所有区间的最佳分裂点.

选择候选切分点时有两种策略:

• Global: 学习每棵树前就计算得到候选切分点, 并在每次分裂时都采用这种分割

• Local: 每次分裂前将重新计算当前节点下所有样本对应的候选切分点

直观上来看, Local策略需要更多的计算步骤, 而Global策略需要更多的候选点才能达到较好的效果(否则对于较深的层分裂时, 样本数量较少, 极端情况可能都会集中在一个桶中).

上图是各种切分候选点策略下, AUC评价指标随迭代变化的情况. eps衡量近似的精度, 其倒数为桶的数量, 值越小桶数越多, 近似越细致精确. 可以看到:

• 当划分比较粗略时, local显著比global策略好

• global策略划分精细时(eps小), 可以取得和local策略划分粗略时(eps大)相近的效果

• 根据一定精度划分候选点, global策略就能取得与贪心方法极为相似的精度, 也即最优精度

因此使用Global策略配合一定精度的候选点切分策略, 就可以在满足效果的前提下, 最大程度的降低计算量了.

近似算法具体来说过程如下:

根据指定特征$k$的分布, 来确定$l$个候选切分点. 要切分的对象是所有样本(Global)或当前节点包含的样本(Local), 且每个样本都有自己对应的权值.

• 首先计算出当前所有样本的权值总和

• 然后将根据样本特征$k$的值升序排序, 由低到高累积每个样本的权值, 每积累满足权值总和的$\frac{1}{l+1}$, 说明填满了一个桶, 因此也产生了一个切割点. 使用这种方法得到$l$个切割点$S_{k}=\left\{s_{k 1}, s_{k 2}, \ldots, s_{k l}\right\}$

• 计算每个桶中所有样本一阶梯度和二阶梯度的累加$G$, $H$, 计算每个切分点分裂后产生的收益, 取收益最大的分裂点作为特征$k$的最佳分裂点

上面这种求分割点集合的方法称为加权分位数缩略图(Weighted Quantile Sketch)方法.

样本权值

上面提到, 确定候选分割点会使用样本自己的权值. 实际上, Xgboost在确定候选点时, 不是简单地按照样本个数得到分位点进行分位, 而是以二阶导数值$h_i$作为样本权重加权划分. 划分的方式见上述过程.

为什么用二阶梯度$h_i$作为样本的权值呢?

对损失函数进行变换:

$$\begin{aligned} \Phi^{(t)} & \simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[\frac{2 g_{i} f_{t}\left(x_{i}\right)}{h_{i}}+f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[\frac{2 g_{i} f_{t}\left(x_{i}\right)}{h_{i}}+f_{t}^{2}\left(x_{i}\right)+\left(\frac{g_{i}}{h_{i}}\right)^{2}-\left(\frac{g_{i}}{h_{i}}\right)^{2}\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[f_{t}\left(x_{i}\right)-\left(-\frac{g_{i}}{h_{i}}\right)\right]^{2}+\Omega\left(f_{t}\right)-\sum_{i=1}^{n} \frac{1}{2} \frac{g_{i}^{2}}{h_{i}} \\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[f_{t}\left(x_{i}\right)-\left(-\frac{g_{i}}{h_{i}}\right)\right]^{2}+\Omega\left(f_{t}\right)-\text { constant } \end{aligned}$$

其中的$g_i$, $h_i$都是常数, 那么公式中最后一项$\sum_{i=1}^{n} \frac{1}{2} \frac{g_{i}^{2}}{h_{i}}$是一个常数, 忽略掉. 转换后的损失公式从单个样本角度看, 是有$h_i$起着加权的作用.

稀疏感知算法

工程中的特征矩阵一般都会出现不同程度的稀疏情况, 数据的却是, One-Hot方法引入的0值都会造成输入数据的稀疏. XGBoost在构建树的节点过程中只考虑非缺失值的数据遍历, 当样本相应的特征值缺失时, 分别枚举特征缺省的样本归为左右分支后的增益, 选择增益最大方向作为该特征缺省方向.

XGBoost的工程技巧

列块并行学习

在树生成过程中, 最耗时的一个步骤就是在每次寻找最佳分裂点时都需要对特征的值进行排序. 而XGBoost在训练之前会根据特征对数据进行排序, 然后保存到块结构中, 并在每个块结构中都采用了稀疏矩阵存储格式(Compressed Sparse Columns Format, CSC)进行存储, 后面的训练过程中会重复地使用块结构, 可以大大减小计算量.

通过按特征进行分块并排序, 在块里面保存排序后的特征值及对应样本的引用, 以便于获取样本的一阶, 二阶梯度值. 通过顺序访问排序后的块遍历样本特征的特征值, 方便进行切分点的查找:

此外分块存储后多个特征之间互不干涉, 可以使用多线程同时对不同的特征进行切分点查找, 即特征的并行化处理. 在对节点进行分裂时需要选择增益最大的特征作为分裂, 这时各个特征的增益计算可以同时进行, 这也是XGBoost能够实现分布式或者多线程计算的原因.

缓存访问

列块并行学习的设计可以减少节点分裂时的计算量, 在顺序访问特征值时, 访问的是一块连续的内存空间, 但通过特征值持有的索引(样本索引)访问样本获取一阶, 二阶导数时, 这个访问操作访问的内存空间并不连续, 这样可能造成cpu缓存命中率低, 影响算法效率.

为了解决缓存命中率低的问题, XGBoost 提出了缓存访问算法: 为每个线程分配一个连续的缓存区, 将需要的梯度信息存放在缓冲区中, 这样就实现了非连续空间到连续空间的转换, 提高了算法效率. 此外适当调整块大小, 也可以有助于缓存优化.

核外块计算

当数据量非常大时, 我们不能把所有的数据都加载到内存中. 那么就必须将一部分需要加载进内存的数据先存放在硬盘中, 当需要时再加载进内存. 这样具有明显的IO瓶颈. 针对这个问题作者提出了核外计算的优化方法.

将数据集分成多个块存放在硬盘中, 使用一个独立的线程专门从硬盘读取数据，加载到内存中, 这样算法在内存中处理数据就可以和从硬盘读取数据同时进行.

此外XGBoost还用了两种方法来降低对硬盘读写的开销:

• 块压缩(Block Compression): 按列进行压缩, 读取的时候用另外的线程解压. 对于行索引, 只保存第一个索引值, 然后用16位的整数保存与该block第一个索引的差值

• 块分区(Block Sharding): 块分区是将特征block分区存放在不同的硬盘上, 以此来增加硬盘IO的吞吐量

XGBoost特点

• 高精度: XGBoost引入二阶梯度, 增加了损失函数的近似精度. 二阶信息本身就能让梯度收敛更快更准确(这一点在优化算法里的牛顿法中已经证实). 可以简单认为一阶导指引梯度方向, 二阶导指引梯度方向如何变化

• 高灵活性

  • GBDT以CART为基学习器, XGBoost还可以使用线性分类器(此时相当于带L1和L2正则化的逻辑回归模型)

  • 支持任意有一阶梯度和二阶梯度的自定义损失函数

• 正则化: 目标函数中加入了正则项, 正则项里包含了树的叶子节点个数, 叶子节点权重的L2范式, 用于控制模型的复杂度, 降低了模型的方差, 有助于防止过拟合

• Shrinkage: 相当于学习率衰减. XGBoost在进行完一次迭代后, 会将之前树的叶子节点权重乘上该系数, 主要是为了削弱每棵树的影响, 让后面有更大的学习空间. 这在GBDT中也有使用

• 列抽样: XGBoost借鉴了随机森林的做法, 支持列抽样, 不仅能降低过拟合, 还能减少计算

• 缺失值处理: 对于特征的值有缺失的样本, XGBoost采用的稀疏感知算法可以自动学习出它的分裂方向

• 近似算法: 树节点在进行分裂时, 使用近似算法代替了贪心算法, 在保持精度的同时, 大大减小了分裂时的计算量

• 并行: XGBoost的并行是在特征粒度上的. XGBoost在训练之前, 预先对数据进行了排序, 然后保存为block结构, 后面的迭代中重复地使用这个结构, 大大减小计算量, 也使得并行成为了可能. 在进行节点的分裂时, 需要计算每个特征的增益, 最终选增益最大的那个特征去做分裂, 那么各个特征的增益计算就可以开多线程进行

• 高内存消耗: 预排序过程的空间复杂度过高, 不仅需要存储特征值, 还需要存储特征对应样本的梯度统计值的索引, 相当于消耗了两倍的内存

参考资料

• 深入理解XGBoost