XGBoost原理详解及系统优化

XGBoost,全称“Extreme Gradient Boosting”,和GBDT一样属于Boosting类型的模型,也是一种加法模型。

1 XGBoost原理

1.1 监督学习概念回顾

1.1.1模型和参数

监督学习中模型表示从样本输入x_{i}到预测输出y_{i}的映射关系,参数是我们要学习的部分,比如线性回归模型\hat{y}_{i}=\sum_{j}^{ }\theta _{j}*x_{ij}\theta是我们要学习的参数。

1.1.2 目标函数:损失+正则

模型训练的过程就是寻找最优参数,使得模型能够很好的拟合样本和标签。为了评价模型拟合样本和标签的好快程度,我们需要一个评估指标,即模型的目标函数。

通常目标函数由两部分组成:损失部分和正则部分:obj(\theta ) = L(\theta ) + \Omega (\theta ),其中L是损失函数,衡量模型的预测能力,\Omega是正则项,控制模型的复杂度,防止模型过拟合。

1.2 决策树加法模型

1.2.1 加法模型的训练Additive Training

XGBoost是基于CART决策树的加法模型,形式可以表示为:

\hat{y}_{i}=\sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\epsilon F

其中K表示树的棵数,f是函数空间F中的函数,F代表所有可能的CART树。目标函数表示为

obj(\theta )=\sum_{i}^{n}l(y_{i}, \hat{y}_{i}) + \sum_{k=1}^{K}\Omega(f_{k})

有了目标函数之后,XGBoost的训练过程就是寻找最优参数最小化目标函数。XGBoost的参数是什么呢?XGBoost和GBDT一样,是函数空间的加法模型,其参数为函数,每个函数表示一棵CART树,包含树的结构和树中叶子节点的分数。

XGBoost的加法模型表示为:

\hat{y}_{i}^{(0)} = 0

\hat{y}_{i}^{(1)} = f_{1}(x_{i}) = \hat{y}_{i}^{(0)} + f_{1}(x_{i})

\hat{y}_{i}^{(2)} = f_{1}(x_{i}) + f_{2}(x_{i}) = \hat{y}_{i}^{(1)} + f_{2}(x_{i})

...

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

在每一步中,我们想要学习的函数或CART树必须能够使得目标函数最优:

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

   =\sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})) + \Omega(f_{t}) + constant

使用展开到二阶的泰勒展开式f(x) = \frac{f(x_{0})}{0!} + \frac{f'(x_{0})(x-x_{0})}{1!} + \frac{f''(x_{0})(x-x_{0})^2}{2!} + ...+\frac{f^{(n)}(x_{0})(x-x_{0})^{n}}{n!} + R_{n}(x)

将目标函数展开到二阶项:

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

其中:

g_{i} = \partial_{\hat{y}_{i}^{(t-1)}}l(y_{i}, \hat{y}_{i}^{(t-1)})

h_{i} = \partial_{\hat{y}_{i}^{(t-1)}}^2l(y_{i}, \hat{y}_{i}^{(t-1)})

移除所有的常数项之后,在第t步的目标函数就变为:

obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})

这就是我们每学习一棵新决策树时的优化目标,该优化目标的值只依赖于g_{i}h_{i},这也就是为什么XGBoost支持自定义损失函数的原因:只要损失函数是一阶和二阶可导的,我们就可以一阶导数和二阶导数优化目标函数。

1.2.2 模型复杂度

目标函数中除了损失之外,还有一项:正则项,也就是说我们还需要定义决策树的复杂度。

首先,定义一棵决策树为:

f_{t}(x) = w_{q(x)}, w\epsilon R^T, q: R^d \rightarrow \left \{1,2,...,T\right \}

其中w是表示叶子节点的分数的向量,q表示把每个样本映射到对应叶子节点的函数,T是叶子节点的数量。

基于以上的决策树定义,XGBoost中决策树复杂度定义为:

\Omega(f) = \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^2

当然,决策树复杂度的定义可以有多种,但是这里使用的定义方式在实践中比较有效。很多关于树模型的算法包中经常忽略正则项,是因为传统树的学习重点关注提高节点纯度。XGBoost通过在目标函数中增加决策树复杂度,we can get a better idea of what we are learning and obtain models that perform well in the wild.

1.2.3 模型训练

在定义了决策树复杂度之后,我们在第t步的目标函数可以进一步做如下变换:

obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})

   =\sum_{i=1}^{n}[g_{i}w_{q(x_{i})} + \frac{1}{2}h_{i}w_{q(x_{i})}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2

   =\sum_{j=1}^{T}[(\sum_{i \epsilon I_{j}}^{}g_{i})w_{j} + \frac{1}{2}(\sum_{i \epsilon I_{j}}^{}h_{i} + \lambda )w_{j}^2] + \gamma T

其中I_{j} = \left \{i|q(x_{i}) = j \right \}是分配到叶子节点j的样本集合。由于同属一个叶子节点的样本具有相同的分数,所以可以进行以上的变换。

如果定义:

G_{j} = \sum_{i\epsilon I_{j}}^{}g_{i}

H_{j} = \sum_{i\epsilon I_{j}}^{}h_{i}

那么上面的目标函数可以简化为:

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

上面的目标函数中G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda )w_{j}^2可以看做是关于w_{j}的二次方程,那么使得目标函数取得最优值时的w_{j}以及目标函数的最优值分别为:

w_{j}^* = -\frac{G_{j}}{H_{j}+\lambda }

obj^* = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^2}{H_{j}+\lambda } + \gamma T

对于一棵决策树,w_{j}^2定义了叶子节点的分数,obj^*相当于树的纯度,并且包含了树复杂度的度量。

有了树的度量标准之后,理想情况下可以遍历所有可能的树结构,选择最优的结构。但是在实际中是行不通的,所以我们选择每次优化树的一层结构,即当我们需要把树的一个叶子节点分裂成两个的时候,分裂的Gain为:

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

Gain由四部分组成:1)分裂之后左边叶子节点的分数;2)分裂之后右边叶子节点的分数;3)分裂之前叶子节点的分数;4)一个叶子节点分裂为两个叶子节点时额外增加的正则。

从Gain的表达式可以看出,如果叶子节点分裂的分数差小于\gamma,就不要再进行分裂了。

Gain就是XGBoost在选择分裂点时的评估依据。在实际进行分裂时,为了比较高效的选择最优的分裂点,通常我们先把样本按照候选特征进行排序,然后进行遍历并计算每个可能分裂点的Gain。

2 XGBoost算法优化

2.1 Shrinkage and Column Subsampling

除了使用正则项之外,XGBoost还使用另外两种技术进一步防止过拟合。第一个是shrinkage,由Friedman提出(就是那个提出GBDT算法的Friedman)。Shrinkage对新学习到的树节点的分数进行缩放,类似于梯度优化中的学习率,shrinkage对单棵树的预测结果进行缩放,降低了单棵树的预测结果在模型中的权重,并且给以后的树留出了学习空间。第二个是列采样,列采样通常被用在RandomForest中。列采样相比行采样(也就是对样本进行采样,XGBoost也支持行采样),防止过拟合的效果更好,同时,列采样也一定程度上加速了XGBoost的并行计算。

2.2 最佳分裂点寻找算法

2.2.1 精确贪婪算法

树训练中的一个比较重要的问题就是寻找最佳分裂点。最基本的精确贪婪算法通过遍历所有可能的分裂点,然后计算Gain,选择Gain最大的分裂点。为了提高遍历效率,需要首先对样本按照特征值进行排序。精确贪婪算法的流程见Algorithm1。


image-20200326135621161.png

2.2.2 近似算法

精确贪婪算法因为要遍历所有可能的分裂点,所以总是能够找到最佳的分裂点,但是当数据量足够大,超出内存容量的时候,这种方式就失效了。另外,在分布式计算的情况下,数据分布在不同的节点上,精确贪婪算法也不能进行有效的计算。在这两种情况下,就需要采用近似算法。近似算法首先根据特征值分布的百分位数产生一些候选分割点,然后根据候选分割点把连续的特征离散化,然后计算梯度统计gi和hi,根据梯度统计计算obj*和gain,进而寻找最佳候选分割点。详细的算法流程见Algorithm2.

2.png

根据候选分割点在什么时候产生,近似算法又分成两种形式。第一种是global variant,是在树构造之前首先产生所有的候选分割点,后面在树的每一层进行分裂的时候都使用这些候选分割点。另外一种是Local variant,是在每次节点分裂之后,根据分配到节点的样本重新产生候选分割点。Global variant只产生一次候选分割点,而local variant需要多次产生候选分割点,但是由于属于树中间层节点的样本较少,尤其是随着树的深度增加,local variant相比global variant产生的候选分割点数量更少,而且由于local variant产生候选分割点只依赖于当前节点的样本特征值,因此更适合于deeper tree。

为了对比global variant和local variant,我们在Higgs boson dataset(一个kaggle比赛的数据集)上对两种方式进行试验,试验结果见下图。

3.png

(说明:eps越小,说明产生的候选分割点越多,原因或原理见2.2.3)

试验结果:1)global eps=0.05和exact greedy对比说明,近似算法的global variant如果产生足够多数量的候选分裂点,基本达到和精确贪婪算法同样的模型效果;2)global eps=0.3和local eps=0.3对比说明,产生候选分裂点数量相同的情况下,local variant相比global variant能达到更好的模型效果(因为在树的非根节点,相同数量的候选分裂点的情况下,实际上local variant要比global variant划分的更加精细),或者反过来说也可以,要达到同样的模型效果,local variant相比global variant需要更少的候选分裂点。

2.2.3 加权的百分位数候选分裂点产生方法(weighted quantile sketch)

近似算法中重要的一步就是产生合理的候选分裂点,通常是根据特征值的百分位数点产生候选分割点,这样可以把特征值平均的分成若干个区间。实际上,XGBoost中采取的方法是,计算D_{k} = \left\{(x_{1k}, h_{1}), (x_{2k}, h_{2}), ... (x_{nk}, h_{n})\right\},其中x_{nk}表示第k个特征的第n个样本的值,h_{n}表示目标函数关于x_{nk}的二阶导数,然后定义排序函数r_{k}, R\rightarrow \left [0,+\infty \right ]

r_{k}(z)=\frac{1}{\sum_{(x,h)\epsilon D_{k}}^{}h}\sum_{(x,h)\epsilon D_{k},x<z}^{}h

表示在D_{k}中特征值小于z的样本加权占比,权重为h。

为什么把二阶导数作为权重呢?原因来源于目标函数表达式:

obj^{(t)} \approx \sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})

对以上表达式变换一下:

\sum_{i=1}^{n}[g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})

=\sum_{i=1}^{n}\frac{1}{2}h_{i}(f_{t}(x_{i}) - \frac{g_{i}}{h_{i}})^2 + \Omega(f_{t}) + constant

这个表达式格式可以看做是以\frac{g_{i}}{h_{i}}为label,以h_{i}为权重的加权平方损失。

定义排序函数的目标是寻找候选分裂点\left\{s_{k1},s_{k2}, ...s_{kl}\right\},候选分裂点必须满足:

|r_{k}(s_{k}, j) - r_{k}(s_{k}, j+1)| < \epsilon , s_{k1}=\underset{i}{min}\mathbf{x}_{ik},s_{kl}=\underset{i}{max}\mathbf{x}_{ik}

这里\epsilon是一个超参数(2.2.2中的eps就是指的这个超参数),直观上可以理解为,候选分裂点的数量大概为\frac{1}{\epsilon }.

2.2.4 稀疏数据的最佳分裂点寻找算法

在实际应用中,最常见的是类型是稀疏类型的特征,就是特征里面可能包含大量的缺失值。为了使XGBoost能够适用大量缺失值的场景,在树分裂的时候,给缺失值一个默认的分裂方向(全部分裂到左子节点或者全部分裂到右子节点),默认的分裂方向是通过在训练数据上学习得到的。学习默认分裂方向的算法见Algorithm3。算法只遍历没有缺失的样本,然后把有缺失值的样本当做一个整体,通过全部将其分到左子节点或右子节点,比较分到左边或右边的效果更好,就把全部缺失值样本分到哪边。

clip_image001.png

大多数已有的树学习算法要么仅针对密集数据进行了优化,要么需要特定的过程来处理有限的情况,例如分类编码。 XGBoost以统一的方式处理所有稀疏模式。 更重要的是,我们的方法利用了稀疏性,使计算复杂度与输入中非缺失项的数量呈线性关系。

2.3 并行学习(Column Block for Parallel Learning)

XGBoost中最耗时的部分是对特征进行排序。为了提高排序的效率,我们采取事先把数据存储在被称为block的内存单元里,每个block中的数据是以列压缩(CSC)的格式存储,每列都按照该列的数值大小进行排序。这种输入数据只需要在训练之前计算一次,就可以重复用于之后每棵树的迭代训练。

在精确贪婪算法中,我们把整个数据集存储在同一个block中,并且存储在block中的数据已经是按照每列的特征值进行排序后的,所以只需要遍历一次block,并且根据每个样本点属于哪个叶子节点,就能同时为每个叶子节点寻找到最佳分裂点。下图表示了如何把数据集转换成列压缩(CSC)的格式,并且使用block高效的完成寻找最佳分裂点。

5.png

在近似算法寻找最佳分裂点中, 采取的block存储方式与精确贪婪算法中有所不同,近似算法中采取用多个block对数据进行存储,每个block对应于一部分样本数据,并且block可以分布在不同的机器上,或存储在磁盘上。因为每个block是根据特征值预先排序的(此处,我理解应该是整体数据集先排序之后,然后分散在不同的block中),近似算法中的分位数搜索就变成了线性搜索,尤其是在local proposal模式下,候选分割点需要在每个分支下搜索产生,线性搜索相比分位数搜索极大的提高了效率。

收集每列的梯度统计信息可以并行进行,从而为我们提供了一种候选分裂点查找的并行算法。另外重要的是,CSC列压缩存储格式和block存储结构支持列采样,所以可以很方便的选择block中的部分列。

2.4 Cache-aware Access缓存感知访问

block结构降低了选取候选分裂点的计算复杂度,但是由于block中的数据是按照CSC的列压缩格式存储的,并且每列是按照特征值排序的,除了特征值之外,还存储了指针从特征值指向样本索引,所以在选取候选分割点的时候,会不断的根据特征值对应的样本索引去取梯度统计值,也就是说CPU会不断地访问非连续的内存单元,增加CPU的负担。最简单的实现方法是,CPU读取一次内存单元中的梯度统计值,就进行一次累计计算,就回引起CPU在累计计算和访问非连续的内存单元之间的读写依赖关系。如果block中的梯度统计数据不能进入CPU缓存(比如block太大等原因),或者发生缓存丢失cache miss,就会降低候选分裂点选取的效率。

对于精确的贪婪算法,我们可以通过缓存感知的预提取算法来缓解问题。 具体来说,我们给每个线程分配一个内部缓冲区,将梯度统计信息提取到其中,然后以小批量的方式执行累加。 这种预提取将直接读/写依赖关系更改为更长的依赖关系,并在行数较大时帮助减少运行开销。在数据集较大时,精确贪婪算法的可感知缓存的运行速度是普通版本的两倍。

对于近似算法,我们通过选择合适的block大小来解决该问题。 我们将block大小定义为一个block中包含的最大样本数,因为这反映了梯度统计信息的缓存存储成本。 选择过小的block大小会较小每个线程的工作量,但是同时也会降低并行化效率。 另一方面,太大的block会导致高速缓存丢失cache miss,因此 block大小的选择应该要平衡这两个因素。 通过在不同数据集上的测试,block大小设置为2^{16}是个合适的选择。

2.5 Block for Out-of-core Computation核外计算

为了充分利用机器的资源来实现可扩展的学习,除了处理器和内存之外,利用磁盘空间来处理不能放在主内存的数据也很重要。 为了实现核外计算,我们将数据分为多个block,并将每个block存储在磁盘上。 在计算过程中,重要的是要使用独立的线程将block预提取到主存储器缓冲区中,这样就可以在读取磁盘的同时进行计算。 但是,磁盘读取占用了大部分计算时间,所以要减少开销并增加磁盘IO的吞吐量。 我们主要使用两种技术来改进核外计算。

1)block压缩

将block按列进行压缩,然后在加载到内存时通过独立的线程解压缩,相当于用解压缩时间换取磁盘读取成本。我们使用通用压缩算法来压缩特征值。 对于行索引,我们把block中每个样本的索引值都减去开始索引,并使用16位整数存储每个样本的索引偏移量。 在我们测试的大多数数据集中,我们实现了大约26%至29%的压缩率。

2)block分片

将block中的数据分片到多个磁盘上,并且给每个磁盘分配独立的线程,将数据提前取入内存缓冲区中,然后,训练线程可以从每个缓冲区读取数据。 当有多个磁盘可用时,这有助于增加磁盘读取的吞吐量。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容

  • 初看Xgboost,翻了多篇博客发现关于xgboost原理的描述实在难以忍受,缺乏逻辑性,写一篇供讨论。 ——以下...
    chaaffff阅读 1,800评论 0 8
  • 之前介绍过梯度下降法与牛顿法,GBDT与XGBoost就与这两种方法有关。 boosting(包括GBDT、XGB...
    小松qxs阅读 24,073评论 0 31
  • 本章涉及到的知识点清单:1、boosting模式2、集成学习模型的偏差和方差3、bagging的偏差和方差4、bo...
    PrivateEye_zzy阅读 4,783评论 0 6
  • 一年一度的年会开始喽,对一年来说也是个圆满的结束吧……感恩,一年在巨木开始很开心,大家处的还是挺好的,各司其职,还...
    不一样的Jing阅读 467评论 0 0
  • 由于测试需要,原表中只有1万条数据,现在随机复制插入记录,快速达到100万条。 运行几次下面代码。随机取1000条...
    cuzz_阅读 2,361评论 0 13