XGBoost 和 Lightgbm 笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  XGBoost 和 LightGBM 是现在非常流行的两种 Boosting Tree 的实现,本文对它们做一些笔记以及比较。Boosting Tree 的基本原理本文就不赘述了,可以看这篇文章

RF 与 GBDT 的区别

  我们列出 RF 与 GBDT 的一些区别:

  • 集成学习:RF 属于 bagging 思想,而 GBDT 是 boosting 思想
  • 偏差-方差权衡:RF 不断的降低模型的方差,而 GBDT 不断的降低模型的偏差
  • 训练样本:RF 每次迭代的样本是从全部训练集中有放回抽样形成的,而 GBDT 每次使用全部样本
  • 并行性:RF 的树可以并行生成,而 GBD T只能顺序生成(需要等上一棵树完全生成)
  • 最终结果:RF 最终是多棵树进行多数表决(回归问题是取平均),而 GBDT 是加权融合
  • 数据敏感性:RF 对异常值不敏感,而 GBDT 对异常值比较敏感
  • 泛化能力:RF 不易过拟合,而 GBDT 容易过拟合

XGBoost

  和随机森林一样,XGBoost 实际上也是由很多棵树组成,是一个加法模型,也是一个集成模型。

Objective Function

  目标函数很简单,就是经验风险加上结构风险:

\[ \begin{array}{l} \mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right) \\ \text { where } \Omega(f)=\gamma T+\frac{1}{2} \lambda\|w\|^{2} \end{array} \]

  损失函数是可微的凸函数,结构复杂度的定义有点意思,是叶子结点的数量加上叶子结点权重向量的L2范数。   XGBoost 是一个加法模型,很显然我们可以一棵一棵树去学习,当我们学习第 \(t\) 树时,损失函数可以表示为:

\[ \mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right) \]

  这实际上也是一个贪心算法,当我们学习第 \(t\) 棵树时,前面 \(t-1\) 棵树已经固定了,我们对损失函数做一个二阶的泰勒展开(\(f(x+\Delta x) \simeq f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^{2}\)):

\[ \mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right) \\ g_{i}=\partial_{\hat{y}}(t-1) l\left(y_{i}, \hat{y}^{(t-1)}\right) \\ h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right) \]

  因为 \(l(y_{i}, \hat{y}^{(t-1)})\) 实际上在前 \(t-1\) 树已经被计算出来了,优化 \(t\) 棵树时可以不再考虑它:

\[ \tilde{\mathcal{L}}^{(t)}=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right) \]

  我们用 \(I_{j}=\left\{i | q\left(\mathbf{x}_{i}\right)=j\right\}\) 来表示叶子结点 \(j\) 包含的样本。目标函数进一步可改写为:

\[ \begin{aligned} \tilde{\mathcal{L}}^{(t)} &=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned} \]   我们可以很简单的计算出最优值:

\[ w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda} \]

  代入目标函数可继续化简为:

\[ \tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T \]

  这其实也就可以作为判断一个数结构的 score function,示意图如下:

Split Method

  那么如何判断要不要分裂一个结点呢,在决策树中我们通常是通过判断分裂后的信息增益是否大于 0 来判断是否需要分裂节点的,在 XGBoost 中也是这么做的,只不过信息增益的定义我们可以用上节中推导出的目标函数来代替,这也是非常自然的:

\[ \mathcal{L}_{s p l i t}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma \]   但是在我们分裂一个结点时,会有很多个候选分割点,如果我们暴力的搜索每个分割点,开销显然是不可接受的,所以通常会使用一种 exact greedy algorithm,它的伪代码如下:

  大体思路就是遍历每个结点的每个特征,对每个特征,按特征值大小将特征值排序,线性扫描,找出每个特征的最佳分裂特征值,在所有特征中找出最好的分裂点(分裂后增益最大的特征及特征值),这是一种贪心的方法,每次进行分裂尝试都要遍历一遍全部候选分割点,也是一种全局扫描法。但当数据量过大导致内存无法一次载入或者在分布式的环境下,贪心算法的效率就会变得很低,全局扫描法不再适用。
  因此 XGBoost 采取了一种近似算法,选取一些分位点作为 candidate split point,在提出这些点时有两种策略:

  • Global:学习每棵树前就提出候选切分点,并在每次分裂时都采用这种分割;
  • Local:每次分裂前将重新提出候选切分点。

  直观上来看,Local 策略需要更多的计算步骤,而 Global 策略因为节点没有划分所以需要更多的 candidate。

  其实就是对每个特征按照特征值排序后,采用类似分位点选取的方式,仅仅选出常数个特征值作为该特征的候选分割点,在寻找该特征的最佳分割点时,从候选分割点中选出最优的一个。
  判断让树停止生长通常有两种方法,它们其实也就是连个超参数:

  • 设置树的最大深度
  • 最小样本权重和,计算叶子节点的样本权重和是否大于最小样本权重和,这样如果一个叶子节点包含的样本数量太少也会放弃分裂,防止树分的太细,这也是过拟合的一种措施,样本权重和为 \(w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}\)

Weighted Quantile Sketch

  按照分位点寻找 candidate split points 也是有讲究的,它定义了一个 rank 函数:

\[ r_{k}(z)=\frac{1}{\sum_{(x, h) \in \mathcal{D}_{k}} h} \sum_{(x, h) \in \mathcal{D}_{k}, x<z} \]

  然后通过下面的条件找出符合的 candidate split point \(\left\{s_{k 1}, s_{k 2}, \cdots s_{k l}\right\}\)

\[ \left|r_{k}\left(s_{k, j}\right)-r_{k}\left(s_{k, j+1}\right)\right|<\epsilon, \quad s_{k 1}=\min _{i} \mathbf{x}_{i k}, s_{k l}=\max _{i} \mathbf{x}_{i k} \]

  事实上, XGBoost 不是简单地按照样本个数进行分位,而是以二阶导数值 \(h_i\) 作为样本的权重进行划分,使用 \(h_i\) 作为样本权重的理由也很直观:

\[ \begin{aligned} \operatorname{Obj}^{(t)} & \approx \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)+\frac{1}{2} \frac{g_{i}^{2}}{h_{i}}\right]+\Omega\left(f_{t}\right)+ constant (\frac{1}{2}\frac{g_{i}^{2}}{h_{i}}和constant均为常数,不影响目标函数的值)\\ &=\sum_{i=1}^{n} \frac{1}{2} h_{i}\left[f_{t}\left(x_{i}\right)-\left(-\frac{g_{i}}{h_{i}}\right)\right]^{2}+\Omega\left(f_{t}\right)+constant \end{aligned} \]

  可以看出 \(h_i\) 就是平方损失函数中样本的权重。对于样本权值相同的数据集来说,找到候选分位点已经有了解决方案(GK 算法),当样本权值不一样时,作者提出了一种叫 Weighted Quantile Sketch 的算法,论文给出的补充材料里有详细的证明,这里就不赘述了。  

Sparsity-aware Split Finding

  XGBoost 还专门针对稀疏的输入作了优化,例如下图所示的存在 missing value 的情况,它会指定一个 default direction:

  学习 default direction 可以通过下面这个算法,主要是利用 non-missing 的样本,在寻找最佳 split point 时,不会对该列特征 missing 的样本进行遍历,而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历,通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销:

  同时,为了保证完备性,会将该特征值 missing 的样本分别分配到左叶子结点和右叶子结点,两种情形都计算一遍后,选择分裂后增益最大的那个方向(左分支或是右分支),作为预测时特征值缺失样本的默认分支方向。

Parallel

  树学习中,最耗时的往往是将数据进行排序,为此,XGBoost 在训练之前,预先对每个特征按照特征值大小进行排序,然后保存为 block 结构,后面的迭代计算中会重复地使用这个结构,这使计算量大大减小。同时由于各个特性已预先存储为 block 结构,XGBoost 支持利用多个线程并行地计算每个特征的最佳分割点,这大大提升了结点的分裂速度,也极利于大规模训练集在分布式环境下的适应性扩展。
  XGBoost 还做了一些内存和硬盘上的优化:

  • Cache-aware Access:使用缓存预取的方法,对每个线程分配一个连续的buffer,读取每个block中样本的梯度信息并存入连续的Buffer中。
  • Blocks for Out-of-core Computation:Block预先放入内存;Block按列进行解压缩;将Block划分到不同硬盘来提高吞吐。

Overfitting

  除了给目标函数添加正则项和对样本采样,XGBoost 中也采取了另外两种防止过拟合的方法:

  • weight shrinkage [3]:相当于学习速率,XGBoost 在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。
  • column(feature) subsampling:队列进行采样,类似 RF 的做法,不仅能降低过拟合,还能减少计算。

LightGBM

  我们可以发现 XGBoost 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量,但在节点分裂过程中仍需要遍历数据集。并且预排序过程的空间复杂度过高,不仅需要存储特征值,还需要存储特征对应样本的梯度统计值的索引,相当于消耗了两倍的内存,这是 XGBoost 最主要的两个缺点。
  而 LightGBM 在这些方面都作了大量优化,相比 XGBoost,LightGBM 可以说是速度更快,消耗的内存更少。
  论文中更主要提出了 Gradient- based One-Side Sampling (GOSS)和 Exclusive Feature Bundling (EFB) 两种技术,我们分别介绍下。

直方图加速

  在介绍 GOSS 和 EFB 前,我们先介绍下 LightGBM 中用到的直方图的思想,算法如下:

  直方图算法的基本思想很简单,就是是将连续的特征离散化分桶为 \(k\) 个离散特征,同时构造一个宽度为 \(k\) 的直方图用于统计信息,即 \(k\) 个 bin。这样做的话我们就不需要遍历所有数据,只需要遍历 \(k\) 个 bin,就可找到最佳的分裂点。寻找最佳分裂点的时间复杂度大大减小,从 \(O(\#data \times \#feature)\) 降到了 \(O(\#bin \times \#feature)\)。内存占用也更小了,XGBoost 需要用 32 位的浮点数去存储特征值,并用 32 位的整型去存储索引,而 LightGBM 只需要用 8 位去存储直方图。
  因为是近似算法,特征离散化后无法找到精确的分割点,可能会对模型的精度产生一定的影响,但这种近似的粗粒度的分割也起到了正则化的效果,在一定程度上降低了模型的方差。
  XGBoost 在进行预排序时只对含有 non-missing 的样本进行分裂,而 LightGBM 也采用类似策略:只用 non-missing 的样本构建直方图。
  我们还可以进一步加速直方图的构建,在构建叶节点的直方图时,可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建,从而减少了一半的计算量。因此,在实际操作过程中,可以先计算直方图小的叶子节点,然后利用直方图作差来获得直方图大的叶子节点,大大减少了计算。

GOSS

  如我们在 XGBoost 里提到的,梯度大小可以反应样本的权重,梯度越小说明模型拟合的越好,XGBoost 利用了二阶梯度,而 LightGBM 利用了一阶梯度。GOSS 利用这一信息对样本进行抽样,保留了梯度大的样本,并对梯度小的样本进行随机抽样,在训练时丢弃了大量梯度小的样本,在接下来的计算中只需关注梯度高的样本,极大的减少了计算量。同时,为了不改变样本的数据分布,在计算增益时为梯度小的样本引入一个常数进行平衡。算法如下:

EFB

  很高维的特征通常是稀疏的,特征间可能是互斥的(如两个特征不同时取非零值),如果两个特征并不完全互斥(如只有一部分情况下是不同时取非零值),可以用互斥率表示互斥程度。EFB 将一些特征进行融合绑定来降低特征数量,这也涉及到了两个问题,哪些特征可以一起绑定?特征绑定后特征值如何确定?
  针对第一个问题 EFB 利用特征和特征间的关系构造一个加权无向图,并将其转换为图染色问题,图染色问题是 NP-Hard 的,因此只能采用贪心算法得到近似解:

  思想也很简单,就是构造一个加权无向图,顶点是特征,边是两个特征间互斥程度,然后根据节点的度进行降序排序,度越大,与其他特征的冲突越大,最后遍历每个特征,将它分配给现有特征包,或者新建一个特征包,使得总体冲突最小。这个算法使得构建直方图的复杂度从 \(O(\#data \times \#feature)\) 降到了 \(O(\#data \times \#bundle)\)
  当特征很多时,计算图的度数开销会变大,因此算法进一步做出优化,不按度数排序,而是按每个特征里的非零值的个数去做排序,因为非零值越多的越容易造成 conflict。
  针对第二个问题,论文给出了特征合并算法,它通过给某些特征添加一个 offset,使得原始特征能从合并的特征中分离出来:

Comparison

  下图是 XGBoost 和 LightGBM 的一个对比:

树生长策略

  XGBoost 中,树的增长是 Level-wise,它基于层进行生长,直到达到停止条件,这样做方便并行计算每一层的分裂节点,提高了训练速度,但同时也因为节点增益过小增加了很多不必要的分裂,增加了计算量。
  而 LightGBM 里是 Leaf-wise,每次分裂增益最大的叶子节点,直到达到停止条件。这样可以减少了计算量,配合最大深度的限制防止过拟合,由于每次都需要计算增益最大的节点,所以无法并行分裂。

分割点查找算法

  XGBoost 使用特征预排序算法,LightGBM 使用基于直方图的切分点算法,其优势如下:

  • 减少内存占用,比如离散为 256 个bin时,只需要用 int8 就可以保存一个样本被映射为哪个 bin,对比预排序的 exact greedy 算法来说(用 int32 来存储索引 + float32 保存特征值),可以节省 \(\frac{7}{8}\) 的空间。空间复杂度从 \(O(2 * \#data)\) 降低为 \(O(2 * \#bin)\)
  • 计算效率提高:预排序的 Exact greedy 对每个特征都需要遍历一遍数据,并计算增益,而直方图算法在建立完直方图后,只需要对每个特征遍历直方图即可,LightGBM 还可以使用直方图做差加速,一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到,从而加速计算

但实际上 XGBoost 的近似直方图算法也类似于 LightGBM 这里的直方图算法,为什么 XGBoost 的近似算法比 LightGBM 还是慢很多呢?XGBoost 在每一层都动态构建直方图,因为 XGBoost 的直方图算法不是针对某个特定的特征,而是所有特征共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图,而 LightGBM 中对每个特征都有一个直方图,所以构建一次直方图就够了。

支持离散变量

  无法直接输入类别型变量,因此需要事先对类别型变量进行编码(例如独热编码),而 LightGBM 可以直接处理类别型变量,主要采用 many-vs-many 的切分方式将类别特征分为两个子集,实现类别特征的最优切分。

Cache 命中率

  XGBoost 使用 Block 结构的一个缺点是取梯度的时候,是通过索引来获取的,而这些梯度的获取顺序是按照特征的大小顺序的,这将导致非连续的内存访问,可能使得 CPU cache 缓存命中率低,从而影响算法效率。而 LightGBM 是基于直方图分裂特征的,梯度信息都存储在一个个 bin 中,所以访问梯度是连续的,缓存命中率高。

并行策略:

  • 特征并行:LightGBM 特征并行的前提是每个 worker 留有一份完整的数据集,但是每个 worker 仅在特征子集上进行最佳切分点的寻找。worker之间需要相互通信,通过比对损失来确定最佳切分点。然后将这个最佳切分点的位置进行全局广播,每个 worker 进行切分即可。XGBoost 的特征并行与 LightGBM 的最大不同在于 XGBoost 每个 worker 节点中仅有部分的列数据,也就是垂直切分,每个 worker 寻找局部最佳切分点,worker 之间相互通信,然后在具有最佳切分点的 worker 上进行节点分裂,再由这个节点广播一下被切分到左右节点的样本索引号,其他 worker 才能开始分裂。二者的区别就导致了 LightGBM 中 worker 间通信成本明显降低,只需通信一个特征分裂点即可,而 XGBoost 中要广播样本索引。
  • 数据并行:当数据量很大,特征相对较少时,可采用数据并行策略。LightGBM 中先对数据水平切分,每个 worker 上的数据先建立起局部的直方图,然后合并成全局的直方图,采用直方图相减的方式,先计算样本量少的节点的样本索引,然后直接相减得到另一子节点的样本索引,这个直方图算法使得 worker 间的通信成本降低一倍,因为只用通信以此样本量少的节点。XGBoost 中的数据并行也是水平切分,然后单个 worker 建立局部直方图,再合并为全局,不同在于根据全局直方图进行各个 worker 上的节点分裂时会单独计算子节点的样本索引,因此效率慢,每 个worker 间的通信量也就变得很大。
  • 投票并行(LightGBM):当数据量和维度都很大时,选用投票并行,该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大,尤其是当特征维度很大时。大致思想是:每个 worker 首先会找到本地的一些优秀的特征,然后进行全局投票,根据投票结果,选择 top 的特征进行直方图的合并,再寻求全局的最优分割点。

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. RF 与 GBDT 的区别
  3. 3. XGBoost
    1. 3.1. Objective Function
    2. 3.2. Split Method
      1. 3.2.1. Weighted Quantile Sketch
      2. 3.2.2. Sparsity-aware Split Finding
    3. 3.3. Parallel
    4. 3.4. Overfitting
  4. 4. LightGBM
    1. 4.1. 直方图加速
    2. 4.2. GOSS
    3. 4.3. EFB
  5. 5. Comparison
    1. 5.1. 树生长策略
    2. 5.2. 分割点查找算法
    3. 5.3. 支持离散变量
    4. 5.4. Cache 命中率
    5. 5.5. 并行策略:
  6. 6. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...