Press "Enter" to skip to content

Boosting模型:lightGBM 算法原理

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

本文将基于lightGBM的原始paper,对其原理进行归纳总结,以供后续参详,温习之用。

 

前言

 

为了确保文章的连续性,读者需对Boosting系列有一定的理解,在阅读本文核心内容之前,还读者预先在心里回答下下面几个问题:

 

 

    1. XGBoost的目标函数表达式?

 

    1. XGBoost在GBDT的基础上做了哪些优化?

 

    1. XGBoost的exact greedy Algorithm for split finding是什幺?

 

    1. XGBoost寻找分裂点的增益计算方法?

 

    1. XGBoost的近似算法原理?

 

    1. 解释下Weighted Quantile Sketch原理?

 

 

如果对上面的问题模棱两可的,可前往上一篇文章: Boosting模型:XGBoost原理剖析 ,回顾一下。接下来将会针对XGBoost的不足进一步探讨lightGBM模型,相对于GBDT,lightGBM的精度与它相差不大,但是速度可以提升20倍。By the way,在学习lightGBM的时候,可以思考下下面几个问题(本文不会直接给出结论,读完之后,读者自然就明白了):

 

 

    1. Adaboost、GBDT、XGBoost的样本梯度都是什幺?

 

    1. XGBoost的不足之处在哪里(lightGBM因何诞生,解决了什幺问题)?

 

    1. XGBoost的近似算法与lightGBM的histogram-based方法的区别?

 

    1. 什幺是lightGBM?

 

    1. lightGBM与XGBoost的结构有什幺区别?

 

 

不管是XGBoost还是lightGBM,模型的优化方向上必不可少的就是决策树的分裂上。下面,将重点介绍lightGBM算法在寻找最佳切分点上所做出的努力。

 

寻找最佳分裂点

 

lightGBM引入的核心思想包括两个方面:

 

 

    1. Histogram: 基于特征的数值进行分bin,然后基于bin的值寻找最佳分裂的bin值。

 

    1. GOSS(Gradient based One Side Sampling): 移除小梯度样本,使用余留的样本做增益计算;

 

    1. EFB(exclusive Feature Bundling):bundle不会同时为零的特征(互斥),达到减少特征数量的目的。

 

 

Histogram分桶策略

 

GBDT是以决策树为基学习器的ensemble模型,在每次迭代中,GBDT都通过拟合负梯度来学习决策树,其中代价最大最耗时的就是寻找最佳切分点过程。一种方法是采用了预排序的算法,然后枚举所有可能的切分点,再寻找到增益最大的分裂点;另一中方法是基于histogram的算法,如下图所示。histogram算法并不是在预排序的特征值当中寻找最佳切分点,而是将连续的特征值进行离散化bin并放入不同的bucket,在训练的时候基于这些bin来构建特征histogram。这种做法效率更高,速度更快。如Algorithm 1所示,构建histogram的时间复杂度为O(#data $\times$ #feature),寻找最佳分裂点的时间复杂度O(#bin $\times$ #feature)。

左侧为histogram分桶策略,右侧为GOSS采样方法

 

GOSS采样策略

 

样本的梯度越小,则样本的训练误差越小,表示样本已经训练的很好了。最直接的做法就是丢掉这部分样本,然而直接扔掉会影响数据的分布,因此lightGBM采用了one-side 采样的方式来适配:GOSS。GOSS保留了所有的大梯度样本,对小梯度样本进行随机采样,同时为了保证分布的一致性,在计算信息增益的时候,将采样的小梯度样本乘以一个常量:$\frac{1-a}{b}$,$a$表示Top $a \times 100\%$的大梯度样本比例值,$b$表示小梯度样本的采样比值(很多文章里面理解成从省下的小梯度样本中采样b%的比例,其实是有误解的,这里的百分比是相对于全部样本而言的,即$b \% \times N$)。例如:100个样本中,大梯度样本有20个,小梯度样本80个,小梯度样本量是大梯度样本数据量的$4$倍,则大样本采样比率$a$等于$0.2$,假设小梯度样本的采样率为$30\%$,则$b=0.3$,那幺小梯度样本的采样数目等于$b \times 100=30$个,为了保证采样前后样本的分布保持一致,最后小梯度样本采样得到的数据在计算梯度时需要乘以$\frac{1-a}{b}=\frac{1-0.2}{0.3}=\frac{8}{3}$(解释一下,乘以$1-a$是因为大梯度样本采样的整体是整个样本集$N$,小梯度样本采样的候选样本集为$(1-a)N$,除以$b$是因为采样导致小梯度样本的整体分布减少,为此需要将权重放大$\frac{1}{b}$倍)。整个过程如上图Algorithm 2所示。

 

原始情况下,在第$j$个特征,值为$d$处进行分裂带来的增益可以定义为:

 

$$

 

V_{j|O}(d) = \frac{1}{n_O}\left(\frac{(\sum_{x_i\in O:x_{ij} \le d}g_i)^2}{n_{l|O}^j(d)} + \frac{(\sum_{x_i\in O:x_{ij} \gt d}g_i)^2}{n_{r|O}^j(d)} \right)

 

\tag{1}\label{1}

 

$$

 

其中O为在决策树待分裂节点的训练集,$n_o = \sum I(x_i \in O)$,$n_{l|O}^j(d) = \sum I[x_i \in O: x_{ij} \le d]\ $ 并且$\ n_{r|O}^j(d) = \sum I[x_i \in O: x_{ij} \gt d]$。

 

采用GOSS之后,分裂的增益可表示为为:

 

$$

 

V_{j|O}(d) = \frac{1}{n_O}\left(\frac{(\sum_{x_i\in A_l} g_i + \frac{1-a}{b} \sum_{x_i\in B_l} g_i)^2 }{n_{l}^j(d)} + \frac{(\sum_{x_i\in A_r} g_i + \frac{1-a}{b} \sum_{x_i\in B_l} g_r)^2 }{n_{r}^j(d)} \right)

 

\tag{2}\label{2}

 

$$

 

其中$A_l = {x_i \in A: x_{ij} \le d}, A_r = {x_i \in A: x_{ij} \gt d}$,$B_l = {x_i \in B: x_{ij} \le d}, B_r = {x_i \in B: x_{ij} \gt d}$.

 

EFB特征合并

 

高维数据通常是非常稀疏的,而且很多特征是互斥的(即两个或多个特征列不会同时为0),lightGBM对这类数据采用了名为EFB(exclusive feature bundling)的优化策略,将这些互斥特征分组合并为#bundle个维度。通过这种方式,可以将特征的维度降下来,相应的,构建histogram所耗费的时间复杂度也从O(#data $\times$ #feature)变为O(#data $\times$ #bundle),其中#feature << #bundle。方法说起来虽然简单,但是实现起来将面临两大难点:

 

 

    1. 哪些特征可以bundle在一起;

 

    1. 如何构建bundle,实现特征降维。

 

 

针对这两个问题,paper里面提到了两种算法:Greedy Bundling和Merge Exclusive feature。

 

对于第一个问题,将特征划分为最少数量的Bundle本质上属于NP-hard problem。原理与图着色相同,给定一个图G,定点为$V$,表示特征,边为$E$,表示特征之间的互斥关系,接着采用贪心算法对图进行着色,以此来生成bundle。不过论文中指出,对于特征值得互斥在一定程度上是可以容忍的,具体的读者可以参考下原paper(文献1)。具体的算法流程如Algorithm 3所示。

 

 

    1. 首先构建一张带权重的图,权重为特征间的总冲突数;

 

    1. 对特征按照在图内的度进行降序排序;

 

    1. 检查排好序的特征,并将其划分到一个冲突较小的bundle里,如果没有就创建一个bundle。

 

 

采用这种方法对于特征数目不大的数据,还算OK,但是对于超大规模的特征将会出现性能瓶颈。一个优化的方向就是:采用非0值得个数作为排序的值,因为非零值越多通常冲突就越大。

对于第二个问题:应该如何如何构建bundle?关键在于 构建前的特征的值在构建后的bundle中能够识别 。由于基于histogram的方法存储的是离散的bin而不是连续的数值,因此我们可以将不同特征的bin值设定为不同的区间即可。例如,特征A的bin值为[0,10),特征B的bin值为[0,20),要想将两个特征bin合并,我们可以将特征B的特征bin的值加上10,其取值区间将变为[0,30)。整个方法描述如下图所示。

leaf-wise生长策略

 

另外,在树的生成方式上,lightGBM与XGBoost也是有区别的。lightGBM的生长策略是leaf-wise,XGBoost中决策树的生长策略是level-wise。对比之下,level-wise策略维持的是一颗平衡树,leaf-wise策略以降低模型损失最大化为目的,对当前level中切分增益最大的leaf节点进行切分。不过leaf-wise存在一个弊端,就是最后会得到一颗非常深的决策树,为了防止过拟合,可以在模型参数中设置决策树的深度。

左侧为level-wise(XGBoost),右侧为leaf-wise(

 

结束语

 

lightGBM主要提出了两个新颖的方法:GOSS和EFB。两者都对算法性能的提升有着重要的贡献,其中GOSS是针对分裂时样本的数目进行采样优化(行优化),EFB是针对特征进行合并,达到特征减少的目的(列优化)。实际上,XGBoost和lightGBM都属于GBDT的一种实现,旨在优化算法的性能,提升算法的训练速度,与XGBoost相比,lightGBM更适应于数据量更大的场景。从GBDT->XGBoost->lightGBM,在模型训练阶段,是不能百分百地断定lightGBM就比GBDT和XGBoost好,因为数据量的大小也决定了模型的可行性。所以实际场景中,还是建议一一尝试之后再做抉择,因为训练一个XGBoost或lightGBM,都是非常简单的事情。OK,基于Boosting模型的学习终于告一段落,后续将对基于深度学习的排序方法或CTR预估方法进行探讨,感谢读者耐心读完本文。

Be First to Comment

发表评论

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