Press "Enter" to skip to content

XGBoost原理讲解

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

基础

 

首先,需要回顾下回归树的知识:丹丹:分类树和回归树。如图所示,假设回归树的叶子结点值为 ;叶子节点所在的样本集合为 ;叶子结点与样本集合的映射关系为 ,即给定一个样本id,找到该样本所在的叶子结点;最终样本 的值为 ;如图中 的样本落在第二个节点,则 ,而 .

 

图一:回归树

因此,这里我们得到回归树及数学表达式为:

 

(1)

 

这里的表达式仅能表示回归树得到后, 样本的最终值,并不能提现树结构。

 

目标函数

 

xgboost也是一个加法模型,它里面的每个基学习器都采用回归树,训练方式是采用前向分步算法逐步优化里面的每个基学习器,加法模型与前项分布算法可详见 丹丹:Adaboost算法讲解 。定义好模型之后,就需要把目标函数写出来,把问题转换成求解最优值的问题,如:把损失函数降到最小,然后再通过各种求解最优值的方法求解凸优化问题,把基学习器中的参数求解出来。接下来先把要用到的数学符号和公式规定一下。

 

表达式

 

模型表达式:加法模型

 

(2)

 

整个模型是有T个基学习器累加而成,每个基学习器,就是上面讲到的回归树。整个模型也可以写成前面T-1棵树累加在加上第T棵树,其中前面的T-1棵树可以写成 ,即

 

(3)

 

前项分布算法指的是,采用贪心策略,逐棵树进行优化,在优化第t棵树的时候,前面的t-1棵树都是已知的,需要优化的仅仅为当前树的参数,假设当前需要优化第小t棵树,前面第t-1棵树的累加值为 ,则前项分布算法公式为:

 

(4)

 

目标函数:预测值与真实值之间的损失。而XGBoost与GBDT不一样的地方就是XGBoost的损失函数多了一个正则项,因此其表达式如下:

 

(5)

 

其中 代表了一颗回归树的复杂度,需要将t课回归树的复杂度给累加起来。

 

优化目标:使得目标函数取得最小值

 

(6)

 

将公式(4)带入得到

 

(7)

 

其中 是已知量,表示前t-1棵树的累加值,所以当前待优化的值只有当前要求的树的参数,即叶子结点代表的节点值。

 

正则项处理

 

的定义如下:

 

(8)

 

其中超参数 和 可以控制我们的惩罚力度, 指的是当前这棵回归树叶子结点的个数, 表示每个叶子结点的纸的平方和,即l2正则项。正则项的作用是为了防止过拟合,如:叶子结点个数 越来越多的时候,就说明树越来越深,那幺他就越容易出现过拟合的情况,所以需要对他进行一个惩罚,其中惩罚力度通过超参数 进行控制;同理,当叶子结点值比较大的时候,就代表这一棵回归树在所有回归树中值的占比较大,这样整个模型过拟合的风险较高,所以需要对树的叶子结点值进行惩罚。

 

将公式(5)改写成

 

(9)

 

其中 是前面t-1棵树的叶子结点个数及节点值,是已知的,所以这部分就是一个常量constant,所以在优化过程中,它相当于没有用,就可以把它去掉,因此公式(9)就变成了

 

(10)

 

因此,正则项只跟当前要优化的这棵回归树的叶子结点值 和叶子结点个数 有关。

 

目标拆解

 

拿到公式(10)的优化目标,一般的做法是用梯度下降算法求解参数,但是决策树无法采用梯度下降算法,因为决策树是阶跃不连续的,无法求导。将公式(10) 按样本遍历决策树损失值改成按节点遍历,则目标函数变为

 

(11)

 

泰勒二阶展开

 

上面已将目标函数拆解为以叶子结点为单位的一个个小目标,每个小目标中只有一个变量。对其中的 部分进行泰勒展开,之前在GBDT中是进行一阶展开的,XGBoost中进行的是二阶展开,泰勒二阶展开公式如下:

 

(12)

 

将 带入二阶泰勒展开公式得到:

 

(13)

 

公式中除 以外的式子都是常量,在做优化的时候,需要求得损失最小,由于 为常量,与不影响最终优化结果,因此去掉,最终得到损失函数的表达:

 

(14)

 

 

(15)

 

(16)

 

带入(14)整理得到

 

(17)

 

将公式(17)带入目标函数公式(11)得到

 

(18)

 

 

(19)

 

(20)

 

代表了在第 个节点所有样本损失函数一阶梯度的和,同理 就代表了其二阶梯度的和,得到目标函数的最终形态如下:

 

(21)

 

最优 与最优obj

 

决策树每个叶子结点的最小值仅与该叶子结点上的值相关而与其他叶子结点无关,因此,每个叶子结点的最小值可以分开单独求解,即:

 

(22)

 

当每个叶子结点的样本确定的时候,G跟H就是定值,公式中只有 是位置变量。首先,判断二元一次方程的开口方向,由于损失函数是一个凸函数,凸函数的二阶导数>0,所以这里 的,而参数 是一个超参数,肯定也是>0的,因此目标函数的一元二次方程开口向上,能够取的最小值。

 

(23)

 

将公式(23)代回公式(21)的到最小的损失值

 

(23)

 

确定树的结构

 

通过前面的推导我们可以得到一棵回归树叶子结点的最优值 ,及树对应的损失 ,但是前面的求解过程是假定整棵树的结构是已知的。当整棵树节点的划分条件不一致的时候,每个叶子节点的样本值是不一样的,对应得到的 及 也是不一样的,也就是说,不同的树结构会得到不同的 和 。对于我们的目标,就是在不同结构的树中,找到 最小的那一棵树作为当前这一轮的基分类器。具体该怎幺做呢?下面列举了几种不同的方法:

 

穷举法

 

首先能想到的最简单最暴力的方法,就是把所有的可能性都计算一遍,然后从里面选择 最小的那一棵树出来,作为当前这一轮的基分类器,这种方法就叫做穷举法。但是这种暴力的求解方式肯定是没有实用价值的,当特征数很多的时候,每个特征的取值范围都非常大的时候,这里面的运算量会非常大,因为可能的组合是非常非常大的,这里面的计算开销根本顶不住,所以穷举法是不可行的。

 

贪心算法理论

 

一棵树的生成过程,可以看成是一个个节点一步步进行分裂的结果,所以每一步的分裂,都只需要关系当前节点怎幺做分裂即可,这样分布生成,每一步只关注一个节点的情况,计算量会小很多,因为不需要考虑节点的组合情况,只需要考虑一个节点所有的可能情况即可。接下来讲讲,如何对一个节点进行划分。

 

图2:贪心算法分裂单个节点

如上图所示,假设总共有 五个节点,每个叶子节点的 (公式15损失函数的一阶导数)和 (公式16损失函数的二阶导数)我们都是已知的,因此我们可以计算分裂前的节点的 ,我们称之为

 

(24)

 

而分裂成2个叶子节点之后的 ,我们称之为 为:

 

(25)

 

同样的道理,当这个特征的划分阈值不同的时候,落入左边节点与有边节点的样本与之前划分方式的结果是不一致,不同的划分方式可以计算得到不同的 。那选择什幺样的值作为最终节点的分割阈值呢?参考决策树的ID3算法用到的信息增益概念,xgboost中增益计算如下:

 

(26)

 

很明显,当增益gian越大,说明损失下降的越多,那当前的划分就越好。所以,我们要做的事情就是计算每个特征,每种可能的划分方式,从里面选出增益 最大的划分,就是该节点所需要的最优划分。

 

将公式(24)和公式(25)带入公式(26),首先我们知道 , ,带入后得到

 

(27)

 

通过公式(27)的增益计算公式,我们可以计算每一种划分方式的gain,再从中找打最大的增益,以这样的方式确定一个具体的节点该如何划分。这样每一步取最大的方式叫做贪婪。

 

这里做下小的总结:对于一棵树的生长,我们按照节点取对它进行划分,比如说首先是根节点,根节点有很多种划分的情况,因为不需要考虑排列组合情况,因此计算次数有限。然后分别计算每个特征下的每种划分方式,得到一系列的增益,从中选取增益最大的那一种方式,作为该节点的划分。往下的每一个节点都按照这种方式进行划分,直到达到停止条件。

 

这里的停止条件可以有

 

 

    1. 最大增益<=0,说明划分之后会使得增益上升,没有必要再进行划分,这里一般设置一个很小的数

 

    1. 叶子结点包含的样本个数<=n

 

    1. 树深/叶子结点个数限制

 

    1. ……

 

 

贪心算法实现细节

 

接下来从程序设计角度来看整个过程的代码实现,下面是伪代码:

 

图3:贪心算法伪代码

其中, 表示当前节点的样本集合, 表示特征维度(有多少个特征),这里的m跟d应该是一个含义。

 

整个流程如下:

 

 

    1. 两层for循环,首先对特征进行遍历,k=1,表示第一个特征,k=2表示第二个特征,以此类推

 

    1. 初始化该特征下的 和

 

    1. 对样本按选中的特征的特征值大小进行排序

 

    1. 第二层循环,对排序好的样本集进行遍历

 

    1. 计算

 

    1. 通过G和 计算得到 ,同理计算

 

    1. 以此类推得到该特征下所有分割方式下的gain,这里的score应该是gain

 

    1. 遍历完成所有特征的所有分割点得到最大的gain

 

 

上面的流程中,遍历的每个特征下面,都需要按照该特征的特征值大小对样本进行一次排序,整个计算过程中,最大的耗时就是这一块,接下来讲解该流程的优化方法。

 

优化思路

 

回顾图3中的精确贪心算法,它的复杂度是比较高的,主要有以下两个部分

 

 

    1. 第一层循环次数,特征维度

 

    1. 样本排序

 

    1. 第二层循环的循环次数

 

 

相对应的优化方向就是

 

 

    1. 减少特征数

 

    1. 减少每个特征下面的特征值,或者说是对特征值进行有目的的采样,而不是所有特征值都拿来使用

 

 

上面的方法是以牺牲精度为代价提升运算速率,这个方法就叫做近似算法。

 

近似算法

 

列采样

 

对特征数进行压缩的方式一种方式为列采样,主要有两种方式:按树随机和按层随机。

 

按树随机

 

按树随机表示,在某棵树的根节点进行分裂之前,就筛选出本次基分类器所要用到的特征,后续每个节点的划分,都在筛选出的特征中进行选择。

 

按层随机

 

顾名思义,与按树随机相反,在每一层的节点开始计算之前随机筛选出一批特征,该层的每个节点,都使用事先筛选出的特征进行划分。即,m每一层叶子节点进行分裂的时候,都要进行采样,每一层用以分裂的节点大概率并不一致。

 

两者对比可以发现按层随机比较灵活,按树随机比较固定,在整棵树构建的过程中就会丢失一部分信息。

 

特征值分桶

 

前面的精确贪心算法中可以看到,特征下有多少个特征值,就需要计算多少次gain值,当特征值很多的时候,计算复杂度就会比较高,所以需要从一堆特征值中筛选出一部分特征值,从而减少gain的计算次数。在实际筛选的过程当中,与列采样不一致的是,特征值的筛选并不是随机的,本质上是一个分桶的过程。

 

比如说特征值是1,2,3,4,5,6,7,8,我们需要从中挑选出两个,就相当于将这8个特征值分成了3个桶。在理想的情况下,希望每个桶所包含的样本数不要相差过大,即等频分桶。

 

加权分位法

 

上面的分桶,有一个前提就是,特征值的分布是均匀的,这是一种比较理想化的情况。在很多情况下,样本分布式不均匀的,即有些样本出现较多,有些样本较少,有些样本的影响较大,有些样本的影响较小。因此需要重新采用一种采样方式,称之为加权分位法。

 

先来看一个公式,泰勒二阶展开之后的损失,公式(17), ,目标函数为:

 

(28)

 

对公式(28)进行转换

 

(29)

 

在第三步中,加上一个常量 不影响求极致。从上式中可以看出,目标函数可以看成是要拟合的真实值为 ,权重为 的均方误差损失函数,因此,是使用二阶梯度进行加权的。

 

因此,每个样本进来,都可以计算一个平方损失,平方损失产生的影响,就由它对应的 来决定,那幺这里得到的 就可以看成样本的权值替代。所以,在找分桶的时候,每个样本就不能当成只有一个,具体该看成多少个样本,就由 决定。假设 加起来是27,分成三个桶,那每个桶中的样本量就应该是9个

 

图4:加权分位法划分示意图

在实际划分的时候跟上面的方式有些不一样,会对 进行归一化,并用一个 作为切分阈值。公式如下:

 

图5:切分方式

尽量让每个桶的归一化权重值的和接近 ,这样桶数才能尽量的少。因此,桶的数量是由 决定的,一般的算法中没有特征的分桶数量这个超参数,一般通过调节 去调节桶的数量,比如说调大 就会使得区间数减少,反之亦然。

 

图6:加权分位法划最终方案分示意图

全局策略

 

前面讲了如何对特征值进行分桶,那幺在实际使用中,什幺时候进行分桶有两种策略,全局策略与局部策略。

 

与列采样一致,所谓的全局策略就是在最开始的时候就对特征进行分桶,往后的每一次节点分裂,都采用已经最先分好桶之后的特征值。该方法的特点就是分桶固定,比较死板,一点都不灵活,第二就是如果分桶的值数量过少,那幺他会限制整棵树的生长,也就是说,可能划分到某个节点就停止了,所以采样需要尽可能多才能有较好的效果。

 

局部策略

 

与全局策略对应的是局部策略,顾名思义就是每个节点进行划分的时候,采样值都是不一样的,也就是每一次重新去进行一遍采样。比如某个特征在根节点,采样3,5,7,在根节点分完之后的左节点分裂的时候采样1,2。那幺这样有什幺好处呢?很明显就是比较灵活,并且也可以根据当前节点所包含的样本的一些情况,去重新进行划分。

 

图7:作者实验效果

其中两个蓝色的圈是精确贪婪算法,它的auc效果最好。global eps=0.3是全局策略特征值采样比较少的情况,效果远差于局部策略local eps=0.3。

 

缺失值处理

 

在节点的生产过程中,样本在某个特征上面的值有可能是为null的,但是样本的 和 是存在的,如果将其分到左右的某个节点是可以计算损失的,那幺将其分到哪个节点,就损失是最小的呢?

 

第一想到的是穷举法,但是穷举法比较耗时,当缺失值很多的时候,将有缺失值的样本各自分到左右节点的穷举方式是无法计算的。

 

其次是贪心算法,挨个对有缺失值的样本进行处理,首先将样本分到左边计算gain1,再放到右边计算gain2,看哪种方式gain更大,就放到哪边,依次处理每个样本。这样是可行的,但是运算的计算量就增大了。为了提高整体的算法的运算效率,论文的作者就想到了第三种方式。

 

第三种方案:将全部的缺失值样本作为一组,首先放到左节点,计算gain1,然后放到右节点计算gain2,看哪个更大,就全体放到哪边。

 

需要注意的是,在排序和分桶的时候,也就是执行分位数算法的时候,缺失值是不参与排序和分位数计算的。

 

在论文中将该方法称之为Sparsity-aware Split Find,能对缺失值进行自动处理。

 

Shrinkage(学习率)

 

在Xgboost中也加入了步长 ,也叫做收缩率Shrinkage:

 

(30)

 

也就是给我们的每一个基学习器加上步长 ,这有助于防止过拟合,通常设置0.1。

 

系统设计

 

核外块运算

 

假设数据集非常庞大,是不可能一下子全部加载到内存当中的。假设一共有10个样本,内存一次能加载4个样本,那剩下的样本会被分成一块块存在磁盘当中,且一般存储在不同的磁盘中,以提高磁盘的吞吐率。当内存中处理完一部分样本内存释放出来的时候,就从磁盘中读取待处理的样本。但是内存处理与cpu计算相比磁盘读写相对较快,也就是说,内存中的数据已经处理完了,但是新的数据还没读进来,这样就比较浪费时间。

 

Xgboost解决这个问题的方法就是单独开启一个线程来读取数据,也就是内存的数据在处理的同时已经提前的在从磁盘中同步的进数据的读取。

 

其次,磁盘中存储的数据是采用压缩算法存储的,按列进行压缩,所以线程读取数据的过程中,首先要进行解压的过程。这种方式就叫块压缩。每个块存储到不同的磁盘上,叫做块拆分。

 

分块并行

 

分块并行是比较核心的设计,让Xgboost能实现并行化处理和分布式处理。在构建回归树中,最耗时的是节点分裂的时候,每个特征下面的样本排序操作。前面说到可以减少特征值来加快排序的操作,尽管如此,它还是非常耗时的操作,首先排序是 每个节点 分裂时,每个特征下样本都会重新进行的操作。其次,在计算节点分裂值的时候,每个特征计算不同阈值划分的gain是互不影响的,也就是,特征之间可以并行计算各自的最优化分。针对以上两个问题,提出以下优化方案。

 

首先,在基学习器进行学习之前,对每个特征下面的样本按特征值大小进行排序,然后将排序后的结果保存到一个特定的数据结构Block中,在Block中,对数据按列进行存储,即每个特征之间是互不影响,相互独立的。而每列除了保存特征值之外,还保存了样本的索引。假设有A,B,C,D,E五个样本,存储示意图如下图所示:

 

图8:Block存储方式

Block里面存储的数据是以CSC的格式进行存储的。Block的作用是存储数据,且是按列存储的,方便后面进行并行化操作,并且因为排序的顺序已经存储好了,相当于已经保存起来,在后续节点的划分过程当中,直接读取Block中的排序结果即可,而不需要进行重新排序。这个操作就相当于以空间换时间,因此数据的存储量会变得更大。每次需要计算gain的时候,从Block中读取特征值及样本索引,就能查询到样本的 和 用以计算gain。

 

同时,block这个数据结构还有一个特点就是按列存储,因此可以进行并行处理,在每一次计算最优化分节点的时候,只需要从上到下扫描一遍Block,就可以把最优的gain选出来。对应图3中的伪代码,就相当于外层的for循环没有了,并行的进行了计算。

 

关于分布式运行,跟大数据中分布式运算差不多,将block进行分块,如下图所示:

 

图9:分布式运算

扫描的时候,各自做各自的扫描,讲结果汇报到调度中心,通过调度中心去综合计算结果,得到最终的gain。

 

缓存命中率

 

Block这种数据结构,会导致缓存命中率低。先来解释下什幺是缓存命中率。

 

图10:程序运行逻辑

一个程序运行的时候,需要从磁盘中将数据加载到内存中,同时将程序运行需要的数据加载到内存,当程序需要进行运算的时候,cpu从内存中获取相应的数据,进行计算,计算完毕后,再将数据写回到内存当中。这里会有一个时间差,因为cpu的计算速度比较快,而读写数据的过程相对与运算来讲是比较慢。

 

举个例子,假设一个人在一楼批改文件,而文件的储存室在三楼,批改文件相比到三楼取文件速度更快。这个时候,在cpu和内存之间开辟一个缓存,如在二楼设置一个文件中转站,当然它的大小是小于内存的。假设3楼的文件储存室一共有十个文件,现在cpu要批改第一个文件,那幺他会跑到三楼去一次性按顺序取一批文件,如5个文件,把这批取到的文件先放到缓存中,取第一个文件进行批改,批改完成后放回缓存;然后再去缓存看一下有没有2号文件,有的话直接拿出来进行批改,批改完成送回去。缓存中完成的文件,内存会进行回收。假设几轮之后,要批改的文件6号不在内存中了,cpu先到缓存中找一下有没有6 号,发现没有6号,只能到内存中再次读取一部分数据放入缓存,以此类推。当cpu要处理的文件在缓存中的时候,称为缓存命中。再考虑一种情况,假设cpu要处理的文件为1,6号文件,处理1号文件的时候,缓存中没有查到,跑到内存中按顺序读取1-5号文件,放到缓存处理完毕。当处理6号文件的时候,缓存中还是没有,又得取内存中取,这个时候缓存的命中率很低,整个程序的运算效率低。

 

图11:缓存逻辑举例

同理,当我们用Block将排序结果存储起来的时候,其中存储的是样本的序号,且并不按照顺序进行,而内存中存储的样本是按顺序进行,因此访问顺序是乱的,从而导致缓存命中率非常低,读写速度很慢。

 

图12:Block下面的缓存命中示意图

缓存优化

 

Xgboost是如何优化缓存命中率低的问题呢?首先,Xgboost会给每一个特征分配一个buffer,这个buffer是一个存储空间,里面存的是样本对应的 跟 ,因为只有这些数据是参与实际的运算过程,所以buffer其实存的是样本的梯度信息。这些梯度信息通过buffer存在内存当中,这样就能提高每个特征在进行gain计算的时候的缓存本命中率。

 

参考资料

 

躺懂XGBoost,学不会来打我(doge)_哔哩哔哩_bilibili

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。