LightGBM

Posted on Edited on In Views:
LightGBM总结

1. Abstract

在之前我介绍过XGBoost，这次想跟大家分享一下LightGBM，它是一款常用的GBDT工具包，由微软亚洲研究院（MSRA）进行开发。LightGBM论文的标题为A Highly Efficient Gradient Boosting Decision Tree。这说明LightGBM它是对于XGB提升性能的版本。而LightGBM相对于其他GBM来说具有相近的准确率而且是其训练速度20倍。

2. Comparse with XGB

LightGBM主要的对比对象就是XGB，所以我们先说一下XGB有什么优缺点先。

优点：

  • XGB利用了二阶梯度来对节点进行划分，相对其他GBM来说，精度更加高。
  • 利用局部近似算法对分裂节点的贪心算法优化，取适当的eps时，可以保持算法的性能且提高算法的运算速度。
  • 在损失函数中加入了L1/L2项，控制模型的复杂度，提高模型的鲁棒性。
  • 提供并行计算能力，主要是在树节点求不同的候选的分裂点的Gain Infomation（分裂后，损失函数的差值）
  • Tree Shrinkage，column subsampling等不同的处理细节。

缺点：

  • 需要pre-sorted，这个会耗掉很多的内存空间（2 * #data * # features）
  • 数据分割点上，由于XGB对不同的数据特征使用pre-sorted算法而不同特征其排序顺序是不同的，所以分裂时需要对每个特征单独做依次分割，遍历次数为#data * #features来将数据分裂到左右子节点上。
  • 尽管使用了局部近似计算，但是处理粒度还是太细了
  • 由于pre-sorted处理数据，在寻找特征分裂点时（level-wise），会产生大量的cache随机访问。

因此LightGBM针对这些缺点进行了相应的改进。

  1. LightGBM基于histogram算法代替pre-sorted所构建的数据结构，利用histogram后，会有很多有用的tricks。例如histogram做差，提高了cache命中率（主要是因为使用了leaf-wise）。
  2. 在机器学习当中，我们面对大数据量时候都会使用采样的方式（根据样本权值）来提高训练速度。又或者在训练的时候赋予样本权值来关于于某一类样本（如Adaboost）。LightGBM利用了GOSS来做采样算法。
  3. 由于histogram算法对稀疏数据的处理时间复杂度没有pre-sorted好。因为histogram并不管特征值是否为0。因此我们采用了EFB来预处理稀疏数据。

下来我们针对这些改进来说明一下。

3 Histogram算法

直方图算法的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

LightGBM里默认的训练决策树时使用直方图算法，XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序，直方图算法是一种牺牲了一定的切分准确性而换取训练速度以及节省内存空间消耗的算法

  • 在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算，所以时间复杂度是$O(\#data)$而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复杂度为$O(\#bins)$，时间效率上大大提高了(初始构造直方图是需要一次$O(\#data)$的时间复杂度，不过这里只涉及到加和操作)
  • 直方图做差进一步提高效率，计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到，所以每次分裂只需计算分裂后样本数较少的子节点的直方图然后通过做差的方式获得另一个子节点的直方图，进一步提高效率。
  • 节省内存
    • 将连续数据离散化为直方图的形式，对于数据量较小的情形可以使用小型的数据类型来保存训练数据
    • 不必像预排序一样保留额外的对特征值进行预排序的信息
  • 减少了并行训练的通信代价

现在来看看直方图优化是如何优化的，当然这个优化也是在处理节点分裂的时候。在处理连续特征的时候，如果你想要快速找到最佳的分裂节点要么像之前说到的那样对特征值采用预排序的方式来快速得到最佳的分裂特征值，在这里直方图就是先将特征值先做装箱处理，装箱处理是特征工程中常见的处理方式之一了，下面给个例子说明特征装箱操作。

[0,0.3)—>0

[0.3,0.7)—->1

就是将某个区间的数据映射到离散的数据值。

说完了装箱操作现在看一下微软论文中提到的直方图优化的流程图：

在这里插入图片描述

最外面的 for 循环表示的意思是对当前模型下所有的叶子节点处理，gbdt 会训练多个树模型，这个举例可能是其中任何一个模型吧。

第二个 for 循环开始要对某个叶子分裂处理处理，这一步就开始遍历所有的特征了，你选取的样本可能有 50、100 或者 1000 维等特征，为了找出的最佳的特征作为分裂的依据，那么这一个 for 循环就是干这件事情。

依次往下看，对于当前这个特征新建一个直方图，现在又碰到一个 for 循环了 ，这个 for 循环干的事情就是遍历所有的样本来构建直方图，哈哈，此时就用到了之前所描述的装箱操作了，直方图的每个 bin 中包含了一定的样本，在此计算每个 bin 中的样本的梯度之和并对 bin 中的样本记数。

其中f.bins[i]为特征f在样本i的对应bin；H[f.bins[i]]则表示对bin进行累加，该bin就是特征f在样本i的对应bin。

下面就是最后一个 for 循环了，这个开始遍历所有的 bin，找到适合分裂的最佳 bin，解释一下这其中涉及到达变量定义

$S_L$是当前分裂 bin 左边所有 bin 的集合，对比理解$S_R$，那么$S_P$其中的 P 就是 parent 的意思，就是父节点，传统的决策树会有分裂前后信息增益的计算，典型的 ID3 或者 C45 之类，在这里我们也会计算，但是 $S_R$ 中所有 bin 的梯度之和不需要在额外计算了，直接使用父节点的减去左边的就得到了，是不是觉得很厉害的样子。反正我觉得这点是真的很神奇的地方，虽然看起来很简单，但是也是一个小魔法。

公式的中 loss 就是来衡量分裂的好坏的，在遍历完所有的特征之后根据 loss，理论上 loss 最小的特征会被选中作为最佳的分裂节点。

这样的化这个这个直方图优化处理的流程应该就说明白的，基本上都是按照论文中的流程来一步一步解释。下面就来看看这种直方图优化的优缺点吧！

直方图算法小结：

优点：

  • 首先，最明显就是内存消耗的降低，因为pre-sorted算法需要保存起来每一个特征的排序结构，所以其需要的内存大小是2 * #data * #feature * 4Bytes（不仅需要保持每个样本对应的排序存储索引，还要保存每个样本对应每个特征的梯度值，即行为样本，列为特征，中间表格内容为各个样本对应在该特征的值，用float_32保存特征值；但进行split finding时候，需要对每列值进行从小到大排序，故而需要每行样本不仅要保存对应特征下的特征值，还需保存对应特征的排序索引，这个排序索引值用int_32保存，而histogram只需保存离散值bin value（EFB会谈到bin）而且我们不需要原始的feature value，所以占用的内存大小为：data * # feature * 1Byte，因为离散值bin value使用uint8_t已经足够了，内存消耗可以降低为原来的 1/8。（bin value本身就是按照大小进行分箱的结果，而histogram更多是将样本特征值映射到直方图上，也正是因为这一特性，故而连排序也省了，再加上分箱的粗粒度操作，最后只需保存bin value即可，用uint_8保存bin value，总体内存消耗降为原来的 1/8。此外也正是这一特性，直方图在内存空间连续存储，这也进一步有助于提高缓存命中率，因为它访问梯度是连续的（直方图）；）

    比如离散为256个Bin时，只需要用8位整形就可以保存一个样本被映射为哪个Bin(这个bin可以说就是转换后的特征)，对比预排序的Exact greedy算法来说（用int_32来存储索引+ 用float_32保存特征值），可以节省7/8的空间。

  • 计算效率也得到提高，预排序的Exact greedy对每个特征都需要遍历一遍数据，并计算增益，复杂度为O(#feature×#data)。而直方图算法在建立完直方图后，只需要对每个特征遍历直方图即可，复杂度为O(#feature×#bins)。

  • 提高缓存命中率，因为它访问梯度是连续的（直方图）。

  • 此外，在数据并行的时候，直方图算法可以大幅降低通信代价。（数据并行、特征并行在本文后面讲解）

缺点：

  • 当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。
  • 预处理能够忽略零值特征，减少训练代价；而直方图不能对稀疏进行优化，只是计算累加值（累加梯度和样本数）。但是，LightGBM 对稀疏进行了优化：只用非零特征构建直方图。

LightGBM 为何使用直方图这种比较粗的分割节点方法，还能达到比较好的效果？

虽然分割的精度变差了，但是对最后结果的影响不是很大，主要由于决策树是弱模型， 分割点是不是精确并不是太重要 ；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。

4. 直方图算法改进

直方图算法仍有优化的空间，建立直方图的复杂度为O(#feature×#data)，如果能降低特征数或者降低样本数，训练的时间会大大减少。以往的降低样本数的方法中，要么不能直接用在GBDT上，要么会损失精度。而降低特征数的直接想法是去除弱的特征（通常用PCA完成），然而，这些方法往往都假设特征是有冗余的，然而通常特征是精心设计的，去除它们中的任何一个可能会影响训练精度。因此LightGBM提出了GOSS算法和EFB算法。

4.1 Gradient-based One-Side Sampling（GOSS）——用于减少训练样本数（行）

在AdaBoost中，权重向量w很好的反应了样本的重要性。而在GBDT中，则没有这样的直接权重来反应样本的重要程度。但是梯度是一个很好的指标，如果一个样本的梯度很小，说明该样本的训练误差很小，或者说该**样本已经得到了很好的训练(well-trained)**。

要减少样本数，一个直接的想法是抛弃那些梯度很小的样本，但是这样训练集的分布会被改变，可能会使得模型准确率下降。LightGBM提出 Gradient-based One-Side Sampling (GOSS)来解决这个问题。

GOSS的做法伪代码描述如下：

算法分析：

  1. 根据梯度的绝对值将样本进行降序排序
  2. 选择前a×100%的样本，这些样本称为A
  3. 剩下的数据(1−a)×100% 的数据中，随机抽取b×100%的数据，这些样本称为B
  4. 在计算增益的时候，放大样本B中的梯度(1−a)/b 倍
  5. 关于g，在具体的实现中是一阶梯度和二阶梯度的乘积，见Github的实现（ LightGBM/src/boosting/goss.hpp）

使用GOSS进行采样，使得训练算法更加的关注没有充分训练(under-trained)的样本，并且只会稍微的改变原有的数据分布。

原有的在特征 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)
$$

其中：

  • O为在决策树待分裂节点的训练集
  • $n_o = \sum I(x_i \in O)$
  • $n_{l|O}^j(d) = \sum I[x_i \in O: x_{ij} \le d]\ and\ 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)$
其中：

  • $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\}$

4.2 Exclusive Feature Bundling（EFB）——用于减少训练特征（列）

一个有高维特征空间的数据往往是稀疏的，而稀疏的特征空间中，许多特征是互斥的。所谓互斥就是他们从来不会同时具有非0值（一个典型的例子是进行One-hot编码后的类别特征）。

LightGBM利用这一点提出Exclusive Feature Bundling（EFB）算法来进行互斥特征的合并，从而减少特征的数目。做法是先确定哪些互斥的特征可以合并（可以合并的特征放在一起，称为bundle），然后将各个bundle合并为一个特征。

这样建立直方图的时间将从O(#feature×#data)变为O(#bundle×#data)，而#bundle<<#feature，这样GBDT能在精度不损失的情况下进一步提高训练速度。

那么，问题来了：

  1. 如何判断哪些特征应该放在一个Bundle中？
  2. 如何将bundle中的特征合并为一个新的特征？

4.2.1 Greedy bundle

对于第1个问题，将特征划分为最少数量的互斥的bundle是NP问题（可以根据图着色问题来证明）。

因此，同样采用近似算法。我们可以构建一张图，图上的顶点代表特征，若两个特征不互斥，则在他们之间连一条边。

更进一步的，通常有少量的特征，它们之间并非完全的独立，但是绝大多数情况下，并不会同时取非0值。若构建Bundle的算法允许小的冲突，就能得到更少数的bundle，进一步提高效率。可以证明，随机的污染一部分特征则最多影响精度$O([1-\gamma]n)^{-2/3}$, $\gamma$ 为最大的特征冲突率，也是在速度和精度之间达到平衡的有效手段。

因此，LightGBM的构建bundle算法描述如下（算法3）：

即：

  1. 构造带权图G，边的权重代表两个feature之间冲突的数量

  2. 对特征按度降序排序

  3. 按顺序对排好序的特征进行遍历，对于当前特征i，查看是否能加入已有的bundle（冲突要小），若不行，则新建一个bundle

    上述的算法复杂度为O(#$feature^2$)，当特征数很大的时候，仍然效率不高。

算法3可以进一步优化：不建立图，直接按特征的非0值的个数进行排序。（这也是一种贪心，非0值越多，越可能冲突）。

4.2.2 Merge Exclusive Features

现在来回答第2个问题，我们已经有了一个个的bundle，如何将bundle中的特征合并为一个新的特征呢？

回想起在直方图算法中，我们将连续的特征变为一个个离散的bins值，这是以特征为粒度的，即一个特征一张直方图。而合并后，一个很关键的点是合并后原本不同特征的值要有所体现，这样在新的特征中遍历直方图才能相当于遍历原来好几个直方图，从而找到切分点。

这可以通过对原始特征的值添加偏移来实现，从而将互斥的特征放在不同的bins中。例如，一个Bundle中有两个特征A和B，$A \in [0,10),\ B \in [0,20)$，可以给特征B添加偏移量10，使得B的值域范围变为 $B \in [10,30)$，然后，A和B就可以合并成值域为[0,30]新特征。这就是Merge Exclusive Features（MEF）算法。

伪代码描述如下：

通过MEF算法，将许多互斥的稀疏特征转化为稠密的特征，降低了特征的数量，提高了建直方图的效率。

5. 补充

5.1 树的生成策略

在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

而LightGBM采用的是Leaf-wise tree growth：

Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

注：当采用相同叶子节点时候，leaf-wise tree growth 策略比level-wise tree growth 策略，模型准确率更高。

5.2 LightGBM具体优化

5.2.1 Histogram optimization

一个区间的范围内作为一个bin，简化为以分桶为粒度的直方图来做，这样一来，数据的表示更加简化，减少了内存的适用，而且直方图带来了一定的正则化的效果，使得我们训练出的模型不容易over-fitting到training-data上面，从而具备更好的推广性。

上图是做过直方图优化之后的求解直方图的算法细节。这是按照bin来索引histogram的，所以不需要按照每个feature来排序，也不需要一一地对比不同feature的值，大大地减少了运算量。

5.2.2 Memory usage optimization

当我们用feature的bin来描述数据的特征的时候，带来的变化，首先是我们不需要像预排序算法那样去存储每一个feature排序后对应的data的序列，也就是上图最左边的灰色方块。

其二是我们使用bin来表示feature，一般bin的个数都是控制在比较小的范围内，这样我们可以使用更少的Byte来存储，如上图，使用Byte来存，而原先的feature value可能是float，需要用4个Bytes来存储。

所以总体上来说，LightGBM内存的使用量往往会降到XGBoost对应sorted策略的八分之一，

5.2.3 Leaf-wise with max depth limitation

LightGBM使用了带有深度性质的leaf-wise长树的方法，来提高模型的精度；leaf-wise是一种比较level-wise更高效的长树的方法，在叶子数量一样的时候，leaf-wise可以降到更多的训练误差，带来更好的精度。

但单纯地使用leaf-wise的生长，可能会长出比较深的树，在小数据集上可能会造成过拟合，因此，我们在leaf-wise的基础之上，多加了深度的限制。

5.2.4 Histogram subtraction

LIghtGBM还使用了直方图做差的优化，达到了两倍的加速。

可以观察到：一个叶子节点的直方图，可以由它的父亲节点的直方图减去它的兄弟节点的直方图得到。

根据这一点，我们可以构造出来计算 数据量比较小的叶子节点上的直方图，然后用直方图做差，得到数据量较大的叶子节点上的直方图，达到加速的效果。

5.2.5 Increase cache hit chance

Pre-sorted 的算法当中，有两个操作频繁的地方，会造成cache-miss。

  • 对梯度的访问，在计算gain的时候，需要利用梯度，但不同的feature访问梯度顺序都是不一样的，而且是随机的。

  • 对于索引表的访问，pre-sorted使用一个行号和叶子节点号的索引表，防止数据切分的时候，对所有的feature进行切分。对访问梯度一样，所有的feature都要通过访问这个索引表，所以，都是随机的访问，这个时候，会带了非常大的系统性能的下降。

LightGBM使用直方图算法则是天然的cache friendly，首先，对梯度的访问，因为不需要对feature进行排序，同时，所有的feature都采用同样的方式进行访问，所以只需要对梯度访问的顺序进行一个重新的排序，所有的feature都能连续地访问梯度。

此外，直方图算法不需要数据id到叶子id的一个索引表，没有这样一个cache-miss的问题。事实上，在cache-miss这样一个方面，对速度的影响是很大的，尤其在数据量很大的时候，MRSA研究人员进行过测试，在数据量很多的时候，相比于随机访问，顺序访问的速度可以快4倍以上，这其中速度的差异基本上就是由cache-miss而带来的。

5.2.6 Categorical feature support

传统的机器学习工具一般，不能直接输入类别特征，需要预先做离散化，抓换为很多，多维的0,1特征，这样的做法无论在时间上还是空间上，效率都不高。

LightGBM通过更改决策树算法的决策规则，直接原生支持类别特征，不需要额外的离散化。并且通过一些实验，MRSA研究人员验证了直接使用离散特征可以比使用0-1离散化后的特征，速度快到8倍以上 。

5.2.7 Parallel Learning Support

LightGBM原生支持多种并行算法：

  • 其中Feature Parallelizaton通常适用于小数据且feature比较多的场景；
  • Data Parallelization则适用于数据量比较大，但feature比较少的场景；
  • Voting Parallelization则适用于数据量比较大，feature也比较多的场景；

具体论述看5.3小节。

5.3 并行计算

本小节主要根据LightGBM的官方文档中提到的并行计算优化进行讲解。

在本小节中，工作的节点称为worker

5.2.1 特征并行

特征并行主要是并行化决策树中寻找最优划分点(“Find Best Split”)的过程，因为这部分最为耗时。

传统算法：

传统算法的做法如下：

  1. 垂直划分数据（对特征划分），不同的worker有不同的特征集
  2. 每个workers找到局部最佳的切分点{feature, threshold}
  3. workers使用点对点通信，找到全局最佳切分点
  4. 具有全局最佳切分点的worker进行节点分裂，然后广播切分后的结果（左右子树的instance indices）
  5. 其它worker根据收到的instance indices也进行划分

img

传统算法的缺点是：

  1. 无法加速split的过程，该过程复杂度为O(#data)，当数据量大的时候效率不高
  2. 需要广播划分的结果（左右子树的instance indices），1条数据1bit的话，大约需要花费O(#data/8)

LightGBM中的特征并行

每个worker保存所有的数据集，这样找到全局最佳切分点后各个worker都可以自行划分，就不用进行广播划分结果，减小了网络通信量。过程如下：

  1. 每个workers找到局部最佳的切分点{feature, threshold}
  2. workers使用点对点通信，找到全局最佳切分点
  3. 每个worker根据全局全局最佳切分点进行节点分裂

但是这样仍然有缺点：

  1. split过程的复杂度仍是O(#data)，当数据量大的时候效率不高
  2. 每个worker保存所有数据，存储代价高

5.2.2 数据并行

传统算法

数据并行目标是并行化整个决策学习的过程：

  1. 水平切分数据，不同的worker拥有部分数据
  2. 每个worker根据本地数据构建局部直方图
  3. 合并所有的局部直方图得到全部直方图
  4. 根据全局直方图找到最优切分点并进行分裂

img

在第3步中，有两种合并的方式：

  • 采用点对点方式(point-to-point communication algorithm)进行通讯，每个worker通讯量为O(#machine∗#feature∗#bin)
  • 采用collective communication algorithm(如“All Reduce”)进行通讯（相当于有一个中心节点，通讯后在返回结果），每个worker的通讯量为O(2∗#feature∗#bin)

可以看出通信的代价是很高的，这也是数据并行的缺点。

LightGBM中的数据并行

  1. 使用“Reduce Scatter”将不同worker的不同特征的直方图合并，然后workers在局部合并的直方图中找到局部最优划分，最后同步全局最优划分。
  2. 前面提到过，可以通过直方图作差法得到兄弟节点的直方图，因此只需要通信一个节点的直方图。

通过上述两点做法，通信开销降为O(0.5∗#feature∗#bin)

5.2.3 Voting Parallel

LightGBM采用一种称为PV-Tree的算法进行投票并行(Voting Parallel)，其实这本质上也是一种数据并行。

PV-Tree和普通的决策树差不多，只是在寻找最优切分点上有所不同。

其算法伪代码描述如下：

img

  1. 水平切分数据，不同的worker拥有部分数据。
  2. Local voting: 每个worker构建直方图，找到top-k个最优的本地划分特征
  3. Global voting: 中心节点聚合得到最优的top-2k个全局划分特征（top-2k是看对各个worker选择特征的个数进行计数，取最多的2k个）
  4. Best Attribute Identification： 中心节点向worker收集这top-2k个特征的直方图，并进行合并，然后计算得到全局的最优划分
  5. 中心节点将全局最优划分广播给所有的worker，worker进行本地划分。

img

可以看出，PV-tree将原本需要#feature×#bin 变为了2k×#bin，通信开销得到降低。此外，可以证明，当每个worker的数据足够多的时候，top-2k个中包含全局最佳切分点的概率非常高。

小结

LightGBM 和 XGBoost对比如下：

Note:

  1. 引入bundles之后，将互斥（近似互斥）的特征放在一起，原来是每个特征对应一个直方图，意味着每个bundle对应着多个直方图（对应bundle有几个特征，则对应几个直方图），现在通过引入偏移，将bundles里的互斥特征引入到一个直方图中，这样，就将每个bundle中互斥（不同时出现非零值）的稀疏特征转换为稠密的单特征（每个bundle对应一个特征），大大降低了计算量。

  2. 在Greedy Bunding中，判断是否将一个特征加入现在有的bundles中的判定方法是

    1
    2
    3
    cnt  = ConflictCnt(bundles[j], F[i])
    if cnt + bundlesConflict <= K then
    	bundles[j].add(F[i]), needNew = False

    即不仅考虑了当前特征与bundle的冲突数（即当前特征与bundle中任意特征同时存在的个数），也考虑了bundle内部累积的冲突数。

  3. AdaBoost与Gradient Boosting区别：

在这里插入图片描述

  • Adaboost：Emphases error by changing the distribution of samples.

  • Gradient Boosting: Emphases error by changing training targets.

    Adaboost主要是根据当前的loss来改变样本的权重，也就是说这个样本，在当前的学习过程中误差比较大，那么在下一轮，会给他分配一个比较大的权重，反之，如果当前轮该样本的loss比较小，在下一轮训练中就会给样本赋予一个更小的权重；从而控制了接下来子模型的产生。

    Gradient boosting则是直接去修改样本的label，实际上新的样本的label将会变成原来的label与集成中模型预测值之间的残差。

    从直观上来看，Gradient Boosting似乎更加针对降低训练误差的角度去完成算法设计。

  1. Gradient Boosting

在这里插入图片描述

对Gradient Boosting，完整的模型是由很多base learner组成的，学习过程当中，是一个个增加这些子模型，并在这个过程当中，希望loss能不断减小，如果我们把符合函数 f 当做自变量来看，我们希望能能够改变这个符合函数 f 使得loss下降，那么无疑沿着loss相对于 f 的梯度方向是一个合理的选择。换句话说，我们新加入的子模型，使得 f 沿着loss相对于f的梯度方向变了，那么我就得到了我们希望要的新一轮的子模型 f。

当损失函数用平法损失时候，新加入的 f 沿着 loss的梯度方向进行拟合，其实质就是拟合残差 $\hat{y}i = y_i - F{m-1}(x_i)$

  1. AdaBoost, XGBoost, LightGBM三者联系与区别

    Boosting是一个集成策略，其主要包含两种实现方式，一种是AdaBoost，一种是GBDT，其中：

    • Adaboost：Emphases error by changing the distribution of samples.

    • Gradient Boosting: Emphases error by changing training targets.

 XGBoost与Lightgbm都是Gradient Boosting的实现框架（工具包，两篇论文都明确说明两者是"a gradient boosting framework"）（注：是Gradient Boosting的实现架构而非GBDT的实现架构，因此也常有面试官经常追问XGBoost与GBDT的区别），而GBDT也是Gradient Boosting的一种实现，只是限定比较多，如基学习器为cart树，损失函数虽然会依据分类或者回归需要进行选择，但都是在现有损失函数的基础上进行操作，不支持自定义损失函数功能，训练模型只是用梯度一阶导等。

 而XGBoost则在GBDT的基础上进行了扩展，不再局限于基模型为树模型，同样也支持基模型为线性模型（包括线型回归与logistic回归），支持损失函数自定义，加入正则项等；

 而LIghtgbm则是在XGBoost的基础上做了一些模型训练加速工作，具体见上文。

 > 注：XGBoost在GBDT的基础上又加入了正则项，并不是说GBDT不含正则项，事实上，GBDT支持L1，L2正则项，只是XGBoost在L1或L2的基础上进一步引入了正则项 $\gamma T$，其中$T$为叶子节点数。（同样用于限制过拟合）
  1. XGBoost 两种树生成方案优劣：

参考文献

  1. LightGBM: A Highly Efficient Gradient Boosting Decision Tree
  2. A Communication-Efficient Parallel Algorithm for Decision Tree
  3. LightGBM之直方图优化理解
  4. 如何玩转LightGBM
  5. 细语呢喃：集成学习（四）LightGBM
  6. LightGBM论文阅读总结.ipynb