Press "Enter" to skip to content

Boosting硬核入门-XGBoost

1 Boosting 方法概述

 

本文需要读者有以下的前置知识储备:决策树算法、梯度下降法、泰勒展开式。

 

1.1 集成方法

 

集成方法( Ensemble Learning )是一种应用得非常广泛的机器学习方法,主流的集成方法包括 Bagging 、 Boosting 、 Stacking 。

 

俗话说“三个臭皮匠,顶个诸葛亮”,这就是集成方法的思路。很多时候,我们无法直接训练出优质的模型(强学习机),而只能得到一些较差的模型(弱学习机)。集成方法就是将多个弱学习机的预测结果综合起来,以达到甚至是超过强学习机的预测效果。

 

Bagging 采用并行组合弱学习机的思路,代表算法是随机森林( RF , RandomForest ), Bagging 在降低方差方面有很好的效果。

 

Boosting 采用串行组合弱学习机的思路,代表算法是 XGBoost 和 LightGBM , Boosting 在降低偏差方面有很好的效果。

 

本文将要介绍的是 Boosting 。

 

1.2 Boosting 方法

 

Boosting 是一种串行的集成方法,每轮迭代后算法会计算当前模型预测值和样本实际值的差异度,下一轮迭代会针对这个差异度来继续训练模型。这个差异度有时也叫残差,它可以是平方损失函数、指数损失函数( AdaBoost )、对数损失函数(逻辑回归)、 Hinge 损失函数( SVM ),等等。

 

AdaBoost 算法 是早期的经典 Boosting 算法,它是前向分布算法的一个特例。 AdaBoost 采用指数损失函数来评估差异度,指数损失函数的缺点是对于异常点非常敏感,因而在噪音比较多的数据集上经常表现不佳。

 

GBDT 算法 在健壮性方面做了改进:它结合了 CART 决策树和梯度提升方法,由于 CART 树是复杂度低的树,所以方差很小,能够很好地解决过拟合的问题;同时 GBDT 可以使用任何损失函数 ( 只要损失函数是一阶连续可导的 ) ,这样一些比较健壮的损失函数就能得以应用,使模型抗噪音能力得到增强。

 

XGBoost 和 LightGBM 是现在最流行的 Boosting 算法,它们被广泛用于 kaggle 、天池等竞赛中。 Boosting 共有的缺点是模型串行训练,难以并行处理,这样在数据量增大时,无法通过大数据技术提高训练速度,而 xgb 和 lgb 在这方面做出了突破,极大地提高了训练速度,这在后文中会详细说明。

 

2 AdaBoost 算法和 GBDT 算法

 

2 节将会简要地介绍 AdaBoost 算法和 GBDT 算法,偏重于应用而非理论的读者,可以跳过本节。

 

2.1 AdaBoost 算法概述

 

如前文所述, AdaBoost 是一个串行算法,通过 M 轮迭代,在每轮迭代中都训练出 1 个分类器(分类器可以根据需要,采用任意合适的模型),最后将这 M 个分类器相加,得到最终的预测模型。

 

在构建模型的过程中,我们需要对被错误预测的样本赋予更多的关注,让这些样本在下一轮迭代过程中能够更大地影响分类器模型的构建,所以我们要 提高被错误预测的样本的权重 。

 

在最后组合模型的过程中,我们需要让预测效果更好的模型,起到更大的作用,以提高最终模型的预测效果,所以我们要 提高预测效果好的分类器的权重 。

 

以上两点,就是 AdaBoost 在构建模型的过程中,需要遵循的思路。

 

2.2 AdaBoost 算法流程

 

我们利用 AdaBoost 算法,对一个包含有 N 个样本的数据集,进行 M 轮迭代,构建预测模型。

 

其中,表达式的下标 m 表示迭代的次数,下标 i 表示样本标号。

 

算法流程如下:

 

( 1 )初始化样本权重,将每个样本的权重 w 设置为 1/N 。

 

( 2 )进行 M 次循环迭代,依次求得 M 个分类器

 

( 2.1 )通过计算,获取此次迭代的最优分类器(根据实际需要,采用合适的分类模型) :

 

( 2.2 )计算此次迭代分类器的误差:

 

 

( 2.3 )计算此次迭代分类器的权重:

 

 

如此设置分类器权重的思路是:在构建最终模型时,要对 M 个分类器加权相加,为了得到更好的分类效果,就要赋予误差低的分类器高权重,赋予误差高的分类器低权重。

 

( 2.4 )更新样本的权重:

 

 

如此设置样本权重的思路是:为了能够让被错误分类的样本,在下一轮迭代中对分类器的构建产生更大的影响,从而达到纠正错误的目的,就需要赋予被错误分类的样本高权重,赋予被正确分类的样本低权重。

 

最后对样本权重进行归一化:

 

 

归一化的目的是:保证所有样本的权重和为 1 。

 

( 3 )最后,将所有分类器加权求和,获得最终分类器:

 

 

2.3 前向分布算法流程

 

前向分布算法比 AdaBoost 算法更为简洁,我们可以通过学习前向分布算法,进一步了解 Boosting 算法的思路。

 

另外,可以证明, AdaBoost 算法是前向分布算法的一个特例(证明过程见李航《统计学习方法》 8.3.2 )。

 

前向分布算法流程如下,其中表达式的下标 m 表示迭代的次数(一共迭代 M 次),下标 i 表示样本标号(一共有 N 个样本):

 

( 0 )记损失函数为:

 

 

并初始化:

 

 

( 1 )进行 M 次循环迭代,依次求得 M 个分类器(求得分类器的参数和权重)

 

( 1.1 )求解最优化问题,通过极小化损失函数,求得 βγ

 

 

( 1.2 )根据求得的 βγ ,更新 f(x)

 

 

( 2 )整理得到最终模型:

 

 

2.4 GBDT 算法概述

 

AdaBoost 算法使用指数损失函数作为损失函数,所以求解最优化问题的过程较为简单,与之类似还有平方损失函数。但是,如果采用其它损失函数, 求解最优化问题就有可能较为困难 。

 

为了解决这个问题,同时也为了能够采用一些更健壮的损失函数以 减小异常点 的影响,我们 采用损失函数的梯度作为残差 。我们可以采用任意损失函数,只要这个损失函数一阶可导。

 

由于 CART 树模型较为简单 , GBDT 算法利用 CART 树作为基本学习机,这样能够弥补 Boosting 算法方差较高的缺点。

 

2.5 GBDT 算法流程

 

我们要利用 GBDT 算法,对一个包含有 N 个样本的数据集,进行 M 轮迭代,构建预测模型。

 

其中,表达式的下标 m 表示迭代的次数,下标 i 表示样本标号。

 

算法流程如下:

 

( 1 )初始化 f(x) , 并记为 T0(x)

 

 

( 2 )进行 M 次循环迭代,依次求得 M 个决策树。

 

( 2.1 )遍历所有样本,对每个样本的损失函数求导,记为样本的残差:

 

 

( 2.2 )将所有样本的值,替换成残差。

 

( 2.3 )以所有样本的新值(残差)为训练样本,训练并输出决策树模型:

 

其中,每个叶子节点输出的值 w

 

 

在这里, w 不是一个常数,在不同的叶子节点区域, w 取不同的常数值。

 

在这一步中,需要求得决策树模型两方面的内容,一是决策树的结构(使用哪些特征进行分割,分割点的值是多少),二是叶子节点的输出值。

 

( 2.4 )根据 T(x,w) ,更新 f(x)

 

 

( 3 )最后,整理输出最终的 GBDT 模型

 

 

3 XGBoost 算法

 

3.1 概述

 

Boosting 算法最大的缺点有两个:一是方差过高,容易过拟合;二是模型的构建过程是串行的,难以应用于大数据场景。这两个问题在 XGB 算法中,都得到了很大的改善。

 

过拟合的问题还算好解决,很多类似的研究结论都可以被拿来借鉴。所以,在我看来, XGB 最大的贡献,就是创造性地给出了 Boosting 算法的并行计算思路,使之能够适应大数据场景,应用于大数据分布式集群环境中。

 

下面,我们将先学习 XGB 算法,然后对它的特性进行归纳总结。

 

3.2 目标函数

 

要构建一个模型,我们首先要确定要以什幺目标来衡量模型的好坏,然后再围绕这个目标,一步步地改进模型。所以,在 XGB 算法中,我们要先确定算法的目标函数。随后, XGB 模型的构建,就是以实现这个目标函数最小化为目标。

 

XGBoost 的目标函数包括损失函数和正则项两个部分。

 

损失函数 衡量的是模型输出值和样本真实值的差异度,差异度的值越低,模型越好。

 

正则项 衡量的是模型的复杂度,复杂度越高,模型越容易过拟合,所以正则项的值越低,模型越好。

 

如下式所示,第一项 L(y,y’) 表示的是模型的损失函数,第二项 Ω( δ ) 表示的是模型的正则项。

 

其中 f(x) 表示前 m 次迭代生成模型之和, δ (x) 表示当前迭代轮次生成的模型,表达式的下标 m 表示迭代的次数(一共迭代 M 次),下标 i 表示样本标号(一共有 N 个样本),下标 j 表示叶子节点标号(一共有 T 个叶子结点):

 

 

将损失函数进行泰勒展开,并且记 g(x)L(y,y’) 的一阶导数, h(x)L(y,y’) 的二阶导数:

 

(注: g(x)h(x) 均为损失函数 L(y,y’) 对变量 y’ 的求导,此时 y 为常数)

 

 

正则项表示如下,其中 T 表示叶子节点的个数, w 表示叶子节点的输出值

 

 

注:本文中使用的是 L2 范数。在 XGB 的实际应用中,可以使用 L1 范数。

 

最后,代入以上损失函数和正则项的表达式(第 2 行),删除常数项(第 3 行),最后按叶子节点汇总(第 4 、 5 行),可得:

 

 

其中 Tj 表示属于不同叶子节点(模型输出的预测值,而非真实值)的样本的集合。 i ∈ Tj 表示经过当前迭代轮次模型的预测,第 i 个样本被分到叶子节点 j 处。

 

确定了目标函数,下一步就是构建决策树模型。决策树模型的构建包括两个方面:一是要确定决策树模型的结构,包括每个节点使用什幺特征进行分割,分割点的值是多少;二是要确定每个叶子节点的输出值。

 

接下来的两个小节,将分别通过计算叶子节点的输出值和进行节点分裂判定,来完成对决策树模型的构建。

 

3.3 计算叶子节点输出值

 

我们先假设决策树的结构已经被确定了,那幺在这个前提条件下,我们尝试计算叶子节点的最优输出值。

 

观察目标函数:

 

 

最后一项 γ T 只与决策树的结构有关,在结构确定的情况下是常数,可以忽略。

 

第一大项可以按叶子节点 j 进行分解,分解后的子项互不相关。所以可以根据以下表达式,按叶子节点 j 进行划分,各自单独求解 w 的最优值:

 

 

显而易见的,这是一个一元二次多项式, w 的最优解为:

 

 

其中,为便于书写和记忆,记:

 

 

3.4 节点分裂判定

 

在求得叶子节点的最优输出值后,我们接下来求解决策树的结构。

 

由于树的组成结构有无穷多种,我们无法穷举遍历所有的情况,所以我们采用贪婪算法,在每个节点都进行一次判定,决定是否该分裂这个节点,以及该如何分裂这个节点,以此逐步迭代构成一棵决策树。

 

我们先将上一节求得的 w 的最优解代入目标函数,可以得到目标函数的表达式:

 

 

当我们判定一个叶子节点是否需要分裂时,需要计算分裂操作执行前后,目标函数的变化情况。记待分裂节点为 t

 

分裂前整棵树的代价函数:

 

 

分裂后整棵树的代价函数:

 

 

将以上两式相减,可得:

 

 

这个式子即为是否分裂节点的判别公式。如果该式大于 0 ,则表示目标函数的值减少了,分裂是有增益效果的,可以分裂。如果该式小于 0 ,则表示分裂后的目标函数反而增加了,则不建议分裂。

 

注:

 

在单机版的 XGB 算法中,使用的是精准贪婪节点分裂算法。算法会遍历所有特征的所有值,以判定:是否分裂、如果分裂的话采用哪个特征进行分裂、分裂点选取为什幺数值。

 

在数据无法全部放到内存中的场合,或者在分布式应用的场合, XGB 使用近似节点分裂算法。 XGB 首先根据样本数据的百分位分布计算出备选分割点,然后将连续的样本数据分配到由这些备选分割点确定的桶( bucket )里,最后汇总数据(不同分布式集群上的数据、或不同处理线程上的数据),并求出最优分割点。

 

3.5 XGBoost 算法流程

 

在这一小节,我对前面几个小节得出的结论进行整理,归纳出 XGBoost 的算法流程。

 

其中, f(x) 表示前 m 次迭代生成模型之和, δ (x) 表示当前迭代轮次生成的模型,表达式的下标 m 表示迭代的次数(一共迭代 M 次),下标 i 表示样本标号(一共有 N 个样本),下标 j 表示叶子节点标号(一共有 T 个叶子节点):

 

( 1 )根据实际场景需求,设计损失函数 L(y,y’) 和正则项 Ω( δ ) 。进行 f0(x) 的初始化

 

( 2 )进行 M 次循环迭代,依次求得 M 个决策树。

 

( 2.1 )在每次迭代开始前,遍历所有样本,计算所有样本的损失函数 L(y,y’) 关于 y’ 的一阶导数 g 和二阶导数 h

 

( 2.2 )使用以下表达式,进行节点分裂判定。逐步迭代生成树,以确定决策树结构:

 

 

表达式大于 0 则可以分裂,小于 0 则不建议分裂。

 

( 2.3 )决策树结构确定后,根据下式,计算当前迭代轮次决策树的叶子节点输出值:

 

 

( 2.4 )根据当前迭代轮次生成的决策树 δ (x) ,更新模型 f(x)

 

 

( 3 )整理输出最终的 XGBoost 模型:

 

 

在接下来的几个小节里,我将会对 XGB 的特性进行归纳总结,包括前文提及的过拟合预防方法、大数据场景实现方法、以及其它的一些特性。

 

3.6 大数据场景实现方法

 

( 1 )样本间并行计算:在每次迭代前,需要遍历所有样本,求解损失函数的一次导数 g 和二次导数 h ,由于不同样本间无相关性,故此时可以对不同的样本使用并行计算。

 

( 2 )特征间并行计算:在进行节点分裂判定时,需要遍历所有特征,此时可以对不同的特征使用并行计算,最后再汇总不同特征的判定结果,输出最优解。

 

( 3 )预排序:在每次迭代前,事先将样本数据按照不同的特征,根据其数值进行预排序,方便后续在节点分裂判定环节,顺序访问样本数据,对一阶导数和二阶导数进行取数和累加。(注:在构建树的过程中,耗时最长的步骤,就是对样本数据进行排序)

 

( 4 )块压缩技术 (Block Compression) :按列(特征)对数据进行压缩,在数据被读取入内存时,通过一个额外的线程进行解压。这个技术是将磁盘读写的时间耗费,转嫁到内存解压缩的时间耗费上。

 

( 5 )块共享技术 (Block Sharding) :将数据存储到不同的磁盘上,通过额外的线程预读取数据,将数据提前读取到不同磁盘各自的内存缓冲区里,在需要的时候,再将数据送到模型训练线程中。这个技术减小了磁盘读写的时间耗费。

 

( 6 )数据预读取:建立一个独立的线程,在模型执行运算操作的同时,用这个线程向磁盘读取后续需要用到的数据。但是,由于程序在计算模型时常常也要读写磁盘,所以这个方法未必很有效。

 

( 7 )构建树的算法包括精确贪婪算法和近似算法(直方图算法),近似算法对每维特征按照分位数进行分桶 (bucket) 。

 

3.7 过拟合预防方法

 

( 1 )学习效率参数 shrinkage :类似于其它算法的学习效率参数 LearningRate 。

 

( 2 )引入正则项:包括树的叶子节点数量,叶子节点输出值的 L1 或 L2 范数。

 

( 3 )列(特征)采样:在迭代时只使用一部分特征来构建模型。列采样不仅缩短了计算时间,还提高了模型的预测效果。列采样方法源自于随机森林算法。

 

( 4 )行(样本)采样:在迭代时只使用一部分样本来构建模型。

 

3.8 其它特性

 

( 1 )自定义目标函数: XGB 可以自定义目标函数,只需要目标函数满足二次可导。

 

( 2 )基分类器:不仅可以采用 CART 树作为基分类器(本文中默认使用 CART 树),也可以使用线性模型。

 

( 3 )分裂准则:节点分裂时,能够直接根据目标函数(损失函数 + 正则项)进行判定。

 

( 4 )有效处理缺失值和稀疏值:对于特征值缺失或特征值稀疏的样本,分别尝试将缺失 \ 稀疏数据划分到左叶子和右叶子,计算增益并进行对比,选择增益更大的划分方案。

 

(注:产生稀疏矩阵的三个常见原因:数据缺失,数据本身含有大量零值,使用了 one-hot 方法。)

 

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

 

( 6 )支持加权数据:陈天奇在论文里提了一下,但是没给出具体算法。

 

参考资料

 

[1] Tianqi Chen AScalable Tree Boosting System

 

[2] Tianqi Chen Introductionto Boosted Trees

 

[3] 李航 统计学习方法 清华大学出版社

 

本文转载自公众号: 数论遗珠,作者:阮智昊

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注