NO.47.tip： LightGBM

背景

前面已经指出了 XGBoost 的一些弱点，特别是当面对维度高、数据量大的问题时，XGBoost 的效率和可扩展性仍然不尽人意。其中一个主要原因是对于每个特征，需要遍历所有的数据实例来估计所有可能分割点的信息增益，这非常耗时。

LightGBM是 Light Gradient Boosting Machine 的简称，是一个免费和开源的分布式梯度提升框架，最初由微软开发。它基于决策树算法，用于排名、分类和其他机器学习任务，其开发的重心是性能和可扩展性。

LightGBM 框架支持不同的算法，包括 GBT、GBDT、GBRT、GBM、MART 和 RF。LightGBM 具有 XGBoost 的许多优点，包括稀疏优化、并行训练、多损失函数、正则化、套袋（bagging）和早期停止。两者之间的一个主要区别在于树的构建。LightGBM 并不像其他大多数实施逐层……那样逐级生长树——逐行生长。此外，LightGBM 不使用被广泛应用的基于排序的决策树学习算法，相反，LightGBM 实现了一种高度优化的基于直方图的决策树学习算法，在效率和内存消耗方面都有很大的优势。

LightGBM 算法采用了两种新技术，即基于梯度的单边采样（Gradient-based One-Side Sampling，GOSS）和互补特征压缩（Exclusive Feature Bundling，EFB），这使得该算法在保持高精确度的同时运行得更快。

使用 GOSS 排除了很大比例的小梯度数据实例，只用剩下的实例来估计信息收益。由于具有较大梯度的数据实例在计算中起更重要的作用，GOSS 可以用更小的数据量对信息增益进行相当准确的估计。

源与流

LightGBM 核心原理

基于直方图的最优分割点查找算法

学习最优决策树是 GBDT 主要的时间花销，而这个过程中找到最优分割点最消耗时间。目前主要采用预排序算法来找到最优分割点，这种方法会列举预排序中所有可能的分割点，虽然能够得到最优的切分点，但在训练速度和内存消耗方面效率较低。另一种流行算法是直方图算法（histogram-based algorithm）。直方图算法并不通过特征排序找到最优的切分点，而是将连续的特征值抽象成离散的分箱，并使用这些分箱在训练过程中构建特征直方图，这种算法在训练速度和内存消耗上都更加高效，LightGBM 使用此种算法。

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

直方图算法可简单理解为：首先确定对于每一个特征需要多少个箱子，为每一个箱子分配一个整数；然后将浮点数的范围均匀分成若干区间，区间个数与箱子个数相等，将属于该箱子的样本数据更新为箱子的值；最后用直方图表示。这一过程其实就是直方图统计，将大规模的数据放在了直方图中。

直方图离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。对于直方图算法来说比较直观的有以下两个优点：

内存占用更小：直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的 1/8。也就是说，XGBoost 需要用 32 位的浮点数存储特征值，并用 32 位的整型存储索引，而 LightGBM 只需要用 8 位存储直方图，内存相当于减少为原来的 1/8。
计算代价更小：预排序算法 XGBoost 每遍历一个特征值就需要计算一次分裂增益，而直方图算法 LightGBM 只需要计算 $k$ 次（ $k$ 是常数，表示直方图的箱子个数），直接将时间复杂度从 $O (k \cdot # data \cdot # feature)$ 降低到 $O (k \cdot # feature)$ ，而我们知道 $# data ≫ k$ 。

当然，直方图算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是否精确并不是太重要；较粗的分割点也有正则化的效果，可以有效防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升的框架下没有太大的影响。

直方图算法都需要为每个数据检索特征区间值。如果基于直方图的 GBDT 能够有效利用特征中的 0 值，那么将会有很好的性能。事实上，XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略——只用非零特征构建直方图。

下面给出直方图算法的流程。

算法：基于直方图的算法

输入：训练数据 I，最大深度 d。
输入：特征维度 m。
nodeSet ← {0}                        ▷ 当前层次的树节点
rowSet  ← {{0,1,2,…}}                ▷ 树节点中的数据索引
for i = 1 to d do
    for 节点 in nodeSet do
        usedRows ← rowSet[node]
        H ← new histogram()
        for j in usedRows do
            bin ← I.f[k][j].bin
            H[bin].y ← H[bin].y + I.y[j]
            H[bin].n ← H[bin].n + 1
        end
        在直方图 H 上找到最佳分割
        根据最佳分割点更新 rowSet 和 nodeSet
    end
end

LightGBM 的另一个优化是用直方图做差加速。一个叶子的直方图可以由父亲节点的直方图与其兄弟节点的直方图做差得到，在速度上可以提升一倍。通常构造直方图时，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的 $k$ 个桶。

带深度限制的逐叶子生长策略

在直方图算法之上，LightGBM 做了进一步的优化。它抛弃了大多数 GBDT 工具使用的逐层生长（level-wise）的决策树生长策略，而使用了带有深度限制的逐叶子生长（leaf-wise）的策略。

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

基于梯度的单边采样

在 AdaBoost 中，样本权重是反映样本数据重要性的指标。然而在 GBDT 中没有原始样本权重，不能应用权重采样。幸运的是，我们观察到 GBDT 中每个数据都有不同的梯度值，这对采样十分有用。具有不同梯度的数据实例在计算信息增益时扮演不同的角色。

训练误差也比较小，说明数据已经被模型学习得很好了。根据信息增益的定义，具有较大梯度的数据实例（即训练不足的实例）将对信息增益做出更多贡献。因此，我们应该更好地保留那些具有较大梯度的实例（例如，大于预先定义的阈值或者是最高百分位数）的实例。因此，一个直接的想法就是丢掉梯度小的数据。然而这样做会改变数据集的分布，从而影响训练模型的精确度。为了避免此问题，提出了 GOSS 算法。

GOSS 算法从减少数据量和保证精度上寻求平衡的算法。

GOSS 保留所有梯度较大的实例，在梯度小的实例上使用随机采样。目的是丢弃一些对计算信息增益没有帮助的样本，但是如果直接将所有梯度较小的数据都丢弃，势必会影响数据的总体分布。所以，GOSS 首先将要进行分裂计算信息增益的时候，GOSS 对小梯度的数据引入常量乘数。选取绝对值最大的 $a \cdot 100%$ 个数据。然后在剩下的较小梯度数据中随机选择 $b \cdot 100%$ 个数据。接着将这 $b \cdot 100%$ 个数据乘以一个常数 $\frac{1 - a}{b}$ ，这样算法就会更关注训练不足的样本，而不会过多改变原始数据集的分布。最后使用这 $(a + b) \cdot 100%$ 个数据来计算信息增益。GOSS 的算法流程如下所示。

算法：基于梯度的单边采样

输入：训练数据 I，迭代 d。
输入：大梯度数据的采样比 a。
输入：小梯度数据的采样比 b。
输入：损失函数 loss，弱学习器 L。
models ← {}, fact ← b/a
for i = 1 to d do
    preds ← models.predict(I)
    g ← loss(I, preds), w ← {1,1,…}
    topN ← a × len(I), randN ← b × len(I)
    sorted ← GetSortedIndices(abs(g))
    topSet ← sorted[1 : topN]
    randSet ← RandomPick(sorted[topN : len(I)], randN)
    usedSet ← topSet + randSet
    w[randSet] ← fact              ▷ 将权重 fact 赋给小梯度数据
    newModel ← L(I[usedSet], -g[usedSet], w[usedSet])
    models.append(newModel)
end

互斥特征压缩

在实际应用中，虽然有大量的特征，但特征空间相当稀疏，这为我们设计几乎无损的方法来减少有效特征的数量提供了可能性。特别地，在稀疏特征空间中，许多特征是（几乎）排他性的，即它们很少同时取非零值。如果两个特征并不是完全互斥的（部分情况下两个特征都是非零值），则可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率。当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。

通过仔细设计特征扫描算法，我们从特征捆绑中构建了与单个特征相同的特征直方图。这种方式构建直方图的时间复杂度从 $O (# d a t a \times # f e a t u re)$ 降到 $O (# d a t a \times # b u n d l e)$ ，同时不损失精度。（注： $# b u n d l e ≪ # f e a t u re$ ，我们能够极大地加速 GBDT 的训练过程而且不损失精度。）

在训练的时候，遍历一个“捆绑的大特征”可以得到一组互斥特征的直方图，降低了需要遍历的特征量。

“大特征”就可以承载所有特征的直方图，降低了需要遍历的特征量。

现在有两个问题：

怎么判定哪些特征应该绑在一起？
怎么把特征绑为一个？

首先考虑怎么判定哪些特征应该绑在一起。将相互独立的特征进行绑定是一个NP难问题。LightGBM 的 EFB 算法将这个问题转化为图着色问题来求解，将所有的特征视为图的各个顶点，将不相互独立的特征用一条边连接起来，边的权重就是两个相连的特征的冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。

我们注意到通常有很多特征，尽管不是 100% 相互排斥，但也很少同时取非零值。如果算法允许一小部分的冲突，则可以得到更少的特征包，进一步提高计算效率。经过简单的计算，随机污染小部分特征值将影响精度最多 $O ([(1 - γ) n]^{- 2/3})$ ， $γ$ 是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。算法的具体步骤总结如下：

建立一个加权无向图，每个顶点代表特征，每个边有权重，其权重与两个特征间的冲突相关。
根据节点的度进行降序排序，度越大，与其他特征的冲突越大。
遍历排序之后的每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。算法允许两两特征并不完全互斥，从而增加特征捆绑的数量，通过设置最大冲突比率 $γ$ 来平衡算法的精度和效率。

EFB 算法的时间复杂度是 $O ((# feature)^{2})$ ，训练之前只处理一次，其时间复杂度在特征不是特别多的情况下是可以接受的，但难以应对百万维度的特征。为了继续提高效率，LightGBM 提出了一种更加高效的无图的排序策略：将特征按照非零值个数排序，这和用图节点的度排序相似，因为更多的非零值通常会导致冲突。EFB 的算法流程如下所示。

算法：贪心绑定算法

输入：特征 F，最大冲突计数 K。
构建图 G
searchOrder ← G.sortByDegree()
bundles ← {}, bundlesConflict ← {}
for i in searchOrder do
    needNew ← True
    for j = 1 to len(bundles) do
        cnt ← bundlesConflict[j], F[i]
        if cnt + bundlesConflict[j], F[i] ≤ K then
            bundles[j].add(F[i]), needNew ← False
            break
        end
    end
    if needNew then
        将 F[i] 作为一个新包添加到 bundles 中
    end
end
输出：bundles

接下来考虑怎么把特征绑在一起，即特征合并（merging features）。特征合并算法的关键在于原始特征能从合并的特征中分离出来。绑定几个特征在同一个束里需要保证绑定前的原始特征值在束中可被识别，鉴于直方图算法存储离散值而不是连续特征值，我们通过将互斥特征放在不同的分箱中来构建束。这可以通过在特征原始值中加一个偏置常量来解决。比如，我们在束中绑定了两个特征 A 和 B，A 特征的原始取值为区间 $[0, 10]$ ，B 特征的原始取值为区间 $[0, 20]$ 。我们可以在 B 特征的取值上加一个偏置常量 10，将其取值范围变为 $[10, 30]$ 。通过这种做法，就可以安全地将 A、B 特征合并，绑定后的特征取值范围为 $[0, 30]$ 。具体的特征合并算法如下所示。

算法：互斥特征合并算法

输入：数据的数量 numData。
输入：一个独有特性的束 F。
binRanges ← {0}, totalBin ← 0
for f in F do
    totalBin += f.numBin
    binRanges.append(totalBin)
end
newBin ← new Bin(numData)
for i = 1 to numData do
    newBin[i] ← 0
    for j = 1 to len(F) do
        if F[j].bin[i] ≠ 0 then
            newBin[i] ← F[j].bin[i] + binRanges[j]
        end
    end
end
输出：newBin，binRanges。

EFB 算法能够将许多互斥的特征变为低维稠密的特征，有效避免不必要 0 值特征的计算。对每一个特征建立一个记录数据中非零值的表，通过用这个表来忽略零值特征，达到优化基础直方图算法的目的。通过扫描表中的数据，建直方图的时间复杂度将从 $O (# data)$ 降到 $O (# non_zero_data)$ 。当然，这种方法在构建树的过程中需要额外的内存和计算开销来维持表。我们在 LightGBM 中将此优化作为基本函数，因为当束是稀疏的时候，这种优化与 EFB 不冲突（可以用于 EFB）。

LightGBM 系统设计及其并行化加速

直接支持类别特征

现实中，大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征通过独热编码转成 0/1 特征。但我们知道对于决策树来说并不推荐使用独热编码，尤其是在类别个数很多的情况下，会存在以下问题：

独热编码后会在每一个决策节点上只能使用一对多的切分方式。例如，动物类别切分后，会产生"是否为狗、是否为猫"等一系列特征，这一系列特征上只有少量样本为 1，大量样本为 0。这时候切分样本会产生不平衡，这意味着切分增益也会很小。较小的切分样本集占总样本的比例太小，无论增益多大，乘以该比例之后几乎都可以忽略。比较直观的理解就是不平衡的切分和不切分几乎没有区别。
影响决策树的学习。即使可以对这个类别特征进行切分，独热编码也会把数据切分到很多零散的小空间上。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习效果会变差。

类别特征的使用在实践中是很常见的。为了解决独热编码处理类别特征的不足，LightGBM 优化了对类别特征的支持，可以直接输入类别特征，不需要额外的 0/1 展开。LightGBM 采用类别特征用每一步梯度提升时的梯度统计（Gradient Statistics，GS）来表示。采用多对多的切分方式将类别特征分为两个子集，实现类别特征的最优切分。基于 Fisher 的论文 "On Grouping For Maximum Homogeneity" 实现了 $O (k lo g k)$ 的时间复杂度。

假设某维特征有 $k$ 个类别，则有 $2^{(k - 1)} - 1$ 种可能，时间复杂度为 $O (2^{k})$ ，LightGBM……（算法流程如下：在枚举分割点之前，先把直方图按照每个类别对应的标签均值进行排序，然后按照排序的结果依次枚举最优分割点。Sum(y)/Count(y) 为类别的均值。当然，这种方法很容易过拟合，所以 LightGBM 还增加了很多对于这种方法的约束和正则化。）

高效并行化加速方法

LightGBM 原生支持并行学习，目前支持特征并行（feature parallelism）、数据并行（data parallelization）和基于投票的数据并行（voting parallelization）。

特征并行的主要思想是在不同机器、不同特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。

XGBoost 使用的就是这种特征并行方法。但这种方法有一个很大的缺点：对数据进行垂直划分后每台机器所含数据不同，使用不同机器找到不同特征的最优分裂点，划分结果需要通过通信告知每台机器，增加了额外的复杂度。LightGBM 则不进行数据垂直划分，而是在每台机器上保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

数据并行中使用分散规约（reduce scatter）把直方图合并的任务分摊到不同的机器，降低了通信量和计算量，并利用直方图做差进一步减少了一半的通信量。

传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行合并，最后在合并的直方图上面寻找最优分割点。这种数据划分方式有一个很大的缺点：通信代价过大。如果使用点对点通信，一台机器的通信开销大约为 $O (2 \times # machine \times # feature \times # bin)$ ，如果使用集成通信，则通信开销为 $O (2 \times # feature \times # bin)$ 。LightGBM 在数据并行中使用分散规约。

基于投票的数据并行进一步优化了数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，投票并行只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。大致分为两步：

本地找出 top K 特征，并基于投票筛选出可能是最优分割点的特征。
合并时只合并每个机器选出来的特征。

cache 命中率优化

XGBoost 对 cache 优化不友好。在预排序后，特征对梯度的访问是随机的，并且不同的特征访问的顺序不一样，无法对 cache 进行优化。同时，在每一层树生长的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，会造成较大的 cache 失效。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问算法对此进行改进。

而 LightGBM 所使用的直方图算法对 cache 天生友好。首先，所有的特征都采用相同的方式获得梯度（区别于 XGBoost 的不同特征通过不同的索引获得梯度），只需要对梯度进行排序便可实现连续访问，大大提高了缓存命中率。其次，因为不需要存储行索引到叶子索引的数组，所以降低了存储消耗，而且也不存在 cache 失效的问题。

LightGBM的优缺点

LightGBM 的优点主要是相对于 XGBoost 而言的，下面从内存和速度两方面进行介绍。

速度更快：

LightGBM 采用直方图算法将遍历样本转变为遍历直方图，极大地降低了时间复杂度。
LightGBM 在训练过程中采用单边梯度算法过滤梯度小的样本，减少了大量的计算。
LightGBM 采用基于逐叶子算法的增长策略构建树，减少了很多不必要的计算量。
LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略。
LightGBM 对缓存也进行了优化，增加了缓存命中率。

内存更小：

XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用直方图算法将特征值转变为箱子值，且不需要记录特征到样本的索引，将空间复杂度从 $O (2 \times # data)$ 降低为 $O (# bin)$ ，极大地减少了内存消耗。
LightGBM 采用直方图算法将存储特征值转变为存储箱子值，降低了内存消耗。
LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

LightGBM 的缺点如下：

可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在逐叶子算法之上增加了一个最大深度限制，在保证高效率的同时防止过拟合。
提升族是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行权重调整，所以随着迭代不断进行，误差会越来越小，模型的偏差会不断降低。由于 LightGBM 是基于偏差的算法，所以会对噪点较为敏感。
在寻找最优解时，依据的是最优切分变量，没有将最优解是全部特征的综合这一理念考虑进去。

概率统计100问

NO.47.tip： LightGBM

背景

源与流