【ML】通篇尽是工业风的XGBoost

c0d3n4m · 发表于 2022-4-4 13:25

前言

Machine Learning在学生时代用得比较多些，工作之后可能主要聚焦于深度学习和自然语言处理方面的学习和应用。但无可否认的是，机器学习中很多的知识点很重要，当然数据挖掘，风控等场景很多都用的是ML，因此在学习NLP的同时，还是需要回过头来进一步学习、体会和理解ML相关算法，增强、加深自己的知识面广度和深度。

论文：

XGBoost背景知识

介绍

GBDT：梯度提升决策树（Gradient Boosting Decision Tree，GBDT）是一种基于boosting集成思想的加法模型，训练时采用前向分步算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前t-1棵树的预测结果与训练样本真实值的残差。
XGBoost(eXtreme Gradient Boosting)极致梯度提升，是GBDT工程化的进阶版模型。在并行计算效率、缺失值处理、预测性能上都非常强大。
XGBoost算法主要在GBDT算法基础上对损失函数进行了修改，加上了树模型的正则化项，对整个GBDT集成模型的所有树的参数做了约束。

XGBoost的基本思想和GBDT相同，优化点主要在于：
算法本身的优化

弱学习器选择上：GBDT只支持决策树，XGBoost支持决策树和其他模型；
损失函数上：XGBoost除了本身的损失，还加上了正则化项；GBDT损失函数无正则项，只会在每次迭代增加收缩系数作为正则化参数；
算法优化方式上：GBDT的损失函数只对误差部分做负梯度(一阶泰勒)展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。

算法运行效率的优化

对每个弱学习器，比如决策树的建立过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有特征的值进行排序分组，方便并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。
Boosting算法的弱学习器无法并行迭代，但单个弱学习器里面最耗时的是决策树的分裂过程，XGBoost针对这个分裂做了比较大的并行优化。对于不同特征的特征值划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益。

算法健壮性的优化

对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式【模型自动选择最优的缺失值默认切分方向：通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向】。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

特征缺失值的子树切分方式

针对缺失值的情况，大概就是通过上图所示方案，将缺失值全部划分到左节点(右节点)，然后将所有非缺失值划归右节点(左节点)，同时针对非缺失值的节点采用节点分裂算法进行子树分裂，同时也大大提升了模型整体计算速度【数据量大大减小】。

XGBoost具有高效、灵活和轻便的特点，在数据挖掘、推荐系统等领域得到广泛的应用。

XGBoost防止过拟合方式

1.正则化损失函数；
2.Shrinkage“学习率”;
3.列采样(特征采样)【如RF】。

XGBoost模型

XGBoost的基学习器

XGBoost可以使用Regression Tree(CART)作为基学习器，也可以使用线性分类器作为基学习器。以CART作为基学习器时，其决策规则和决策树一样，但CART的每一个叶节点具有一个权重【叶节点得分/预测值】。

图1中为两颗回归树(左右两颗)，其中树下方的输出值即为叶节点的权重(得分)，当进行一个样本的预测时，根据每个内部节点的决策条件进行节点划分，最终被划分到的叶节点的权重即为该样本的预测输出值。

模型及模型学习

XGBoost模型定义为：给定一个包含n个样本m个特征的数据集， $|D|=\left\{ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) \right\}$ ，集成模型的预测输出表示为： $\tilde{y_{i}}=\phi(x_{i})=\sum_{k=1}^{K}{f_{k}(x_{i})} , ··········(1)$
其中，K表示回归树的数量，表示回归树。

模型学习

PS:这一部分由于公式实在是忒多了，我可能主要会手写一些公式及相关推导。

XGBoost目标函数：

公式右边第一部分是度量预测值与真实值之间的损失函数，第二部分表示对模型复杂度的惩罚项(正则项)。 $\gamma、\lambda$ 表示惩罚系数，T表示给定的一棵树的叶子结点数， $||w||^{2}$ 表示每棵树叶子结点上的输出数的平方【L2正则】。从XGBoost的目标函数可以看出它的模型复杂度考虑了每棵树的叶子节点数，以及每棵树叶子结点权重值的平方和。
因此，正则化项包含的是：

叶子结点的数量；
叶子结点权重向量的L2范数；

目标函数优化
在通常模型中针对这类目标函数可以使用梯度下降的方式进行优化，但注意到表示的是一颗树，而非一个数值型的向量，所以不能使用梯度下降的方式去优化该目标函数。而只能采用前向分步算法。

$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$
树的生成

基于贪心算法，来递归地生成树，通过相应节点切分前后的收益变化(Gains)来判定是否对相应的节点进行切分。
节点分裂准则

XGBoost子模型和决策树模型一样，要依赖节点递归分裂的贪心准则实现树的生成。XGB还支持近似算法，解决数据量大超内存、或者并行计算的需求场景问题。
基本思路同CART树，对特征值排序后遍历划分点，将其中最优的分裂收益作为特征分裂收益，选取具有最优分裂收益的特征作为当前节点的划分特征，将其最优划分点一分为二，得到左右子树。

分裂收益是分裂前后的评分相减，即树A的减树B的。
分裂收益表达式为： $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}]-\lambda$
Gain越大，说明分裂后能使目标函数减少越多，就越好，节点得分裂。若我们每次做左右子树分裂时，可以最大程度地减少损失函数就是最好的。
节点分裂算法

精确贪心算法

因为精确贪心算法需要遍历所有特征和取值，当数据量非常大时，无法将所有数据同时加载进内存时，精确贪心算法会非常耗时，所以XGBoost也引进了近似算法。

近似算法

近似算法对特征值进行了近似处理，即根据每个特征k的特征值分布，确定出候选切分点 $S_{k}={s_{k1},s_{k2},...,s_{kl}}$ ，即按特征分布将连续的特征值划分到 $l$ 个候选点对应的桶(bucket)中，并且对每个桶中每个样本的一二阶导数进行累加。候选切分点的划分以及的累加过程如下：

就有两种划分方式，第一种方式，即第一个桶( $0\sim\frac{1}{3}$ percentile)的样本被切分到左节点中，第二、三个桶的样本被切分到右节点中。其增益Gain为max函数中第二项。第二种划分方式为，第一、二个桶中的样本切分到左节点中，第三个桶中的样本切分到右节点中，其增益为max函数中第三项。max函数第一项表示的是其他特征切分点确认后的最大增益，与当前特征的两种切分方式比较，选择最优的特征及其切分点。
注意到例子在对样本进行划分时，考虑的是样本的个数，即每个桶中样本个数相同为出发点来划分的，如果样本有权重呢？直观上的想法是，那就考虑权重而不是个数。那么每个样本应该赋予什么样的权重?又怎样去处理这个权重？

XGBoost的节点分割算法——加权分位数

为了处理带权重的候选切分点的选取，作者提出了Weighted Quantile Sketch算法。加权分位数略图算法提出一种数据结构，这种数据结构支持merge和prune操作。

稀疏感知分裂——针对稀疏、缺失数据

实际工程中一般会出现特征值稀疏的情况。比如数据缺失、one-hot编码都会造成输入数据稀疏。关于稀疏值的处理，该文思路是：对于缺失数据让模型自动学习默认的划分方向。算法具体的方法如下：

从算法中可以看出，作者采用的是在每次的切分中，让缺失值分别被切分到左节点或右节点，通过计算得分值比较两种切分方法哪一个更优，则会对每个特征的缺失值都会学习到一个最优的默认切分方向。乍一看这个算法会多出相当于一倍的计算量，但其实不是的。因为在算法的迭代中只考虑了非缺失值数据的遍历，缺失值数据直接被分配到左右节点，所需要遍历样本量大大减小。

作者通过在Allstate-10K数据集上进行了实验，从结果可以看到稀疏算法比普通算法在处理数据上快了超过50倍。
如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。

工程化优化

列分块并行

在树生成过程中，需要花大量时间在特征选择与切分点选择上，并且这部分时间中大部分又花费在了特征值排序上。如何减小这个排序时间？作者提出按特征进行分块并排序，在块里面保存排序后的特征值及对应样本的引用，以便于获取样本的一阶、二阶导数值。具体流程是：

整体训练数据可以看做一个 $n \times m$ 的超大规模稀疏矩阵；
按照mini-batch的方式横向分割，可以切成很多个“Block”；
每一个“Block”内部采用一种Compress Sparse Column的稀疏短阵格式，每一列特征分别做好升序排列，便于搜索切分点，整体的时间复杂度有效降低。

具体方式如下图：

通过顺序访问排序后的块遍历样本特征的特征值，方便进行切分点的查找。此外分块存储后多个特征之间互不干涉，可以使用多线程同时对不同的特征进行切分点查找，即特征并行化处理。
时间复杂度分析：

精确贪心算法：
原始稀疏感知算法复杂度： $O(Kd||x||_{0}logn)$ , $||x||_{0}$ 表示训练数据中的非缺失值数量；
分块结构算法时间复杂度： $O(Kd||x||_{0}+||x||_{0}logn)$ , $||x||_{0}logn$ 表示的是数据预处理过程中排序算法需要的时间复杂度。
近似算法：
原始近似算法时间复杂度： $O(Kd||x||_{0}log q)$ ,q表示数据集候选切分数；
分块结构算法时间复杂度： $O(Kd||x||_{0}+||x||_{0}logB)$ ,B是每个block中的最大的数据行数。

缓存访问

在顺序访问特征值时，访问的是一块连续的内存空间，但通过特征值持有的索引（样本索引）访问样本获取一阶、二阶导数时，这个访问操作访问的内存空间并不连续，这样可能造成cpu缓存命中率低，影响算法效率。
为了减小非连续内存的访问带来缓存命中率低问题，作者提出了缓存访问优化机制。思路是：既然是非连续内存访问带来问题，那么去掉非连续内存访问就可以解决。转非连续为连续----缓存预取。即提前将要访问的非连续内存空间中的梯度统计信息(一阶、二阶导数)放置到连续内存空间中。具体的操作上就是为每个线程在内存空间中分配一个连续的buffer缓存区，将需要的梯度统计信息存放在缓冲区中。这种方式对数据量大的时候很有用，因为大数据量时，不能把所有样本都加入到内存中，因此可以动态的将相关信息加入到内存中。

上图给出了在Higgs数据集上使用缓存访问和不使用缓存访问的式样对比。可以发现在数据量大的时候，基于精确的贪心算法使用缓存预取的处理速度几乎是普通情况下的2倍。作者通过实验证明选择每个块存放个样本时效率最高。

&#34;核外&#34;块计算

当数据量非常大时，无法将所有数据加载到内存中。那么就必须的将一部分需要加载进内存的数据先存放在硬盘中，当需要时再加载进内存。这样操作具有很明显的瓶颈，即硬盘IO操作速度远远低于内存的处理速度，那么肯定会存在大量等待硬盘IO操作的情况【性能瓶颈是磁盘IO】。针对这个问题作者提出了“核外”块计算的优化方法。
具体操作是将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存，这样算法在内存中处理数据就可以和从硬盘读取数据同时进行。为了加载这个操作过程，作者提出了以下两种方法：
块压缩：论文使用的是按列进行压缩，读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后用16位的整数保存与该block第一个索引的差值。作者通过测试在block设置为个样本大小时，压缩比率几乎达到26%~29%；
块分片：块分片是将特征block分区存放在不同的硬盘上，以此来增加硬盘IO的吞吐量。

反正文中提到了XGBoost能支持17亿的数据训练，只要机器管够，应该还能进一步提升该量级，XGBoost模型的工业风可见一斑。

小结

和GBDT的比较

基分类器的差异：GBDT算法只能利用CART树作为基学习器；XGBoost算法除了回归树之外还支持线性的基学习器。
节点分类方法的差异：GBDT算法主要是利用基尼系数(分类问题)/均方误差(回归问题)针对特征进行节点划分；XGBoost通过weighted quantile sketch划分方法，依据影响Loss的程度来确定连续特征的切分值。
损失函数差异：GBDT使用的是损失函数一阶导数，相当于函数空间中的梯度下降；而XGBoost还使用了损失函数二阶导数，相当于函数空间中的牛顿法。
防止过拟合差异：GBDT算法无正则项，可能出现过拟合；XGBoost显式地加入了正则项来控制模型复杂度，能有效防止过拟合。
列采样：XGBoost采用了随机森林中的做法，每次节点分裂前进行随机列采样；GBDT没有进行列采样，只进行了子采样(无放回抽样)，当然XGBoost也支持子采样。
缺失值处理：XGBoost运用稀疏感知策略处理缺失值，而GBDT没有设计缺失策略。
并行高效：XGBoost的列块设计能有效支持并行运算，提高效率【注意不是tree维度的并行，而是特征维度的并行】；GBDT没有并行化策略。

yukamu · 发表于 2022-4-4 13:25

你这理解还是太浅，为什么二阶泰勒展开？叶子节点值怎么得出？都没搞很清楚。。

Baste · 发表于 2022-4-4 13:32

感谢提出批评意见，我会再加深学习理解！

RecursiveFrog · 发表于 2022-4-4 13:40

二阶泰勒不就为了更加精确吗[飙泪笑]

XGundam05 · 发表于 2022-4-4 13:47

更精确更快吧

BlaXuan · 发表于 2022-4-4 13:50

我理解的是这样，二阶泰勒肯定比一阶泰勒精确到二次项了，快应该不是在这体现的，我理解的是在构造树的过程中在时间复杂度上体现的、

		自动登录	找回密码
密码			立即注册

【ML】通篇尽是工业风的XGBoost

本帖子中包含更多资源