GBDT (Gradient Boosting Decision Tree)是机器学习中一个长盛不衰的模型，其主要思想是利用弱分类器（决策树）迭代训练以得到最优模型，该模型具有训练效果好、不易过拟合等优点。GBDT在工业界应用广泛，通常被用于点击率预测，搜索排序等任务。GBDT也是各种数据挖掘竞赛的致命武器，据统计Kaggle上的比赛有一半以上的冠军方案都是基于GBDT。

LightGBM （Light Gradient Boosting Machine）一个实现GBDT算法的框架，支持高效率的并行训练，并且具有以下优点：

● 更快的训练速度

● 更低的内存消耗

● 更好的准确率

● 分布式支持，可以快速处理海量数据

LightGBM在Higgs数据集上LightGBM比XGBoost快将近10倍，内存占用率大约为XGBoost的1/6，并且准确率也有提升。

Xgboost已经十分完美了，为什么还要追求速度更快、内存使用更小的模型？

对GBDT算法进行改进和提升的技术细节是什么？

一、提出LightGBM的动机

常用的机器学习算法，例如神经网络等算法，都可以以mini-batch的方式训练，训练数据的大小不会受到内存限制。

而GBDT在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。

LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地用于工业实践。

改进的细节

Xgboost是如何工作的？

目前已有的GBDT工具基本都是基于预排序的方法（pre-sorted）的决策树算法(如xgboost)。这种构建决策树的算法基本思想是：

首先，对所有特征都按照特征的数值进行预排序。

其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。

最后，找到一个特征的分割点后，将数据分裂成左右子节点。

这样的预排序算法的优点是能精确地找到分割点。

缺点也很明显：

首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。

其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

二、LightGBM在哪些地方进行了优化？

a) 基于Histogram的决策树算法

b) 带深度限制的Leaf-wise的叶子生长策略

c) 直方图做差加速直接

d) 支持类别特征(Categorical Feature)

e) Cache命中率优化

f) 基于直方图的稀疏特征优化多线程优化。

下面主要介绍Histogram算法、带深度限制的Leaf-wise的叶子生长策略和直方图做差加速。

2.1 Histogram算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。

在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

其算法大致描述如下(当然loss计算有些问题)

仔细看上面的伪代码，相信你有几个问题：

如何将特征映射到bin呢？即如何分桶？

如何构建直方图？直方图算法累加的g是什么？

构建完直方图如何找最优特征，有用到二阶信息么？

如何分桶呢？

首先，在读取数据后，就决定每个特征如何分桶。关于如何分桶，对于数值型特征和类别特征采用不同的做法。

2.2 构建直方图

给定一个特征的取值，我们现在已经可以转化为对应的bin了。现在我们就可以构建直方图了。

可以看到，累加了一阶和二阶梯度，同时还累加了梯度的和还有个数。（当然还有其它的版本，当is_constant_hessian为true的时候是不用二阶梯度的）。

寻找最优切分点

对每个特征都构建好直方图后，就可以进行最优切分点的构建了。

遍历所有的特征，对于每个特征调用FindBestThreshold如下函数：

使用直方图算法有很多优点。首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。

然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data*#feature)优化到O(k*#features)。

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

Boosting）的框架下没有太大的影响。

三、带深度限制的Leaf-wise的叶子生长策略

3.1 层次生长的策略

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

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

在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise)

的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise)算法。

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

3.2 直方图差加速

LightGBM另一个优化是Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。

利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

3.3 数值型特征

就是分裂前的分数！

因此，是和XGBoost一样的。

3.4 直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化到多维的0/1特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。在Expo数据集上的实验，相比0/1展开的方法，训练速度可以加速8倍，并且精度一致。据我们所知，LightGBM是第一个直接支持类别特征的GBDT工具。

LightGBM的单机版本还有很多其他细节上的优化，比如cache访问优化，多线程优化，稀疏特征优化等等，更多的细节可以查阅Github Wiki()上的文档说明。优化汇总对比表:

四、LightGBM的并行

在探寻了LightGBM的优化之后，发现LightGBM还具有支持高效并行的优点。

LightGBM针对这两种并行方法都做了优化，在特征并行算法中，通过在本地保存全部数据避免对数据切分结果的通信；在数据并行中使用分散规约(Reduce scatter)把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行可以得到非常好的加速效果。

4.1 特征并行

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

传统算法的做法如下：

1)垂直划分数据（对特征划分），不同的worker有不同的特征集

2)每个workers找到局部最佳的切分点{feature, threshold}

3）workers使用点对点通信，找到全局最佳切分点

4)具有全局最佳切分点的worker进行节点分裂，然后广播切分后的结果（左右子树的instance indices）

5)其它worker根据收到的instance indices也进行划分

传统算法的缺点是：

a)无法加速split的过程，该过程复杂度为O(#data)，当数据量大的时候效率不高

b)需要广播划分的结果（左右子树的instance indices），1条数据1bit的话，大约需要花费O(#data/8)

LightGBM中的特征并行

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

i)每个workers找到局部最佳的切分点{feature, threshold}

ii)workers使用点对点通信，找到全局最佳切分点

iii)每个worker根据全局全局最佳切分点进行节点分裂

但是这样仍然有缺点：

a)split过程的复杂度仍是O(#data)，当数据量大的时候效率不高

b)每个worker保存所有数据，存储代价高

LightGBM原生支持并行学习，目前支持特征并行和数据并行的两种。

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

4.2 数据并行

数据并行则是让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。

传统算法里，数据并行目标是并行化整个决策学习的过程：

①水平切分数据，不同的worker拥有部分数据

②每个worker根据本地数据构建局部直方图

③合并所有的局部直方图得到全部直方图

④根据全局直方图找到最优切分点并进行分裂

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

A 采用点对点方式(point-to-point communication algorithm)进行通讯，每个worker通讯量为O(#machine∗#feature∗#bin)

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

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

LightGBM中的数据并行

使用“Reduce Scatter”将不同worker的不同特征的直方图合并，然后workers在局部合并的直方图中找到局部最优划分，最后同步全局最优划分。

前面提到过，可以通过直方图作差法得到兄弟节点的直方图，因此只需要通信一个节点的直方图。

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

Voting Parallel

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

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

其算法伪代码描述如下：

①水平切分数据，不同的worker拥有部分数据。

②Local voting: 每个worker构建直方图，找到top-k个最优的本地划分特征

③Global voting: 中心节点聚合得到最优的top-2k个全局划分特征（top-2k是看对各个worker选择特征的个数进行计数，取最多的2k个）

④Best Attribute Identification： 中心节点向worker收集这top-2k个特征的直方图，并进行合并，然后计算得到全局的最优划分

⑤中心节点将全局最优划分广播给所有的worker，worker进行本地划分。

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

↓↓↓免费送！福利！福利！福利↓↓↓

了解七月在线的的小伙伴应该知道2019年七月在线出了两本书《名企AI面试100题》和《名企AI面经100篇》，反响很好，助力数千人拿到dream offer。今年我们又整理出了两本书《2021年最新大厂AI面试题 Q2版》、《机器学习十大算法系列》、《2021年最新大厂AI面试题 Q3版》，七月在线学员拿到书后反响不错。为了让更多AI人受益，七仔现把电子版免费送给大家。

↓ ↓ ↓以下5本书，电子版免费送 ↓ ↓ ↓

《2021年最新大厂AI面试题 Q2版》、《2021年最新大厂AI面试题 Q3版》《机器学习十大算法系列》、《名企AI面试100题》及《名企AI面经100篇》无套路，免费取！

需要的小伙伴评论区发书名，看到后发你。