文章目录
- XGBoost不足之处
- 直方图算法
- 单边梯度抽样算法(GOSS)
- 互斥特征捆绑算法(EFB)
- 带深度限制的 Leaf-wise 算法
- LightGBM的工程优化
- 直接支持类别特征
- 特征并行
- 数据并行
- 投票并行
- Cache命中率优化
- LightGBM的优缺点
文章图片
LightGBM是轻量级（Light）的梯度提升机器（GBM）,是GBDT模型的另一个进化版本。它延续了 XGBoost 的那一套集成学习的方式，相对于xgboost， 具有训练速度快和内存占用率低的特点。
XGBoost不足之处 XGBoost的核心思想： xgboost是属于boosting家族，是GBDT算法的一个工程实现， 在模型的训练过程中是聚焦残差，在目标函数中使用了二阶泰勒展开并加入了正则，在决策树的生成过程中采用了精确贪心的思路，寻找最佳分裂点的时候，使用了预排序算法， 对所有特征都按照特征的数值进行预排序， 然后遍历所有特征上的所有分裂点位，计算按照这些候选分裂点分裂后的全部样本的目标函数增益，找到最大的那个增益对应的特征和候选分裂点位，从而进行分裂。这样一层一层的完成建树过程， xgboost训练的时候，是通过加法的方式进行训练，也就是每一次通过聚焦残差训练一棵树出来， 最后的预测结果是所有树的加和表示。
在这个过程中，不足之处在于：xgboost在进行最优分裂点的选择上是先进行预排序，然后对所有特征的所有分裂点计算这些分裂点分裂后的全部样本的目标函数增益，这个过程的空间复杂度和时间复杂度很大。虽然xgboost的近似分割的算法对分裂点进行了分桶了（这和lightgbm里面的直方图的思路一致），减少了计算量，起到了一定的优化作用，但lightgbm直方图算法进行了更好的优化。所以，基于XGBoost寻找最优切分点的复杂度体现在以下三点：
（1）分裂点的数量
（2）样本的数量
（3）特征数量
LightGBM 正是从这三个角度出发，对XGBoost算法进行优化。分别对应了lgb的三大算法思想。
（1）为了解决分裂点数量过多的问题，LightGBM采用直方图算法。
（2）为了解决样本数量过多的问题， Lightgbm采用单边梯度抽样算法。
（3）为了解决特征数量过多的问题，Lightgbm采用互斥特征捆绑算法
直方图算法 直方图算法说白了就是对特征进行分桶。先把连续的浮点特征值离散化成k k k 个整数，同时构造一个宽度为k k k的直方图， 并根据特征所在的bin对其进行梯度累加和个数统计，在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。然后根据直方图的离散值，遍历寻找最优的分割点。
文章图片
文章图片
bins的数量是远小于样本不同取值的数量的，所以分桶之后要遍历的分裂点的个数会少了很多，减少了计算量。用图形表示如下：
文章图片
这个过程其实就是直方图统计，将大规模的数据放在了直方图中。也就是分箱的过程。
特征离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。对于直方图算法来说有以下两个优点：
（1）占用更少的内存。
XGboost需要用32位的浮点数去存储特征值， 并用32位的整型去存储索引，而Lightgbm的直方图算法一般用8位的整型保存特征离散化后的值，内存消耗可以降低为原来的1/8。
文章图片
（2）计算代价更小
XGboost预排序算法每遍历一个特征的值就需要计算一次分裂的增益，时间复杂度为：
O ( ( 特 征 值 个 数 ? 1 ) ? 特 征 数 ) O((特征值个数-1)*特征数) O((特征值个数?1)?特征数)
Lightgbm直方图算法只需要计算k次（k：每个特征的分箱的个数），时间复杂度为：
O ( ( k ? 1 ) ? 特 征 数 ) O((k-1)*特征数) O((k?1)?特征数)
每个特征的分箱的个数k远小于每个特征的特征值的个数。所以Lightgbm计算的时间复杂度较低。
直方图作差加速
LightGBM另一个优化是Histogram（直方图）做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍。在实际构建树的过程中，LightGBM还可以先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就可以用非常微小的代价得到它兄弟叶子的直方图。
文章图片
举例如下：
文章图片
注意： XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。
直方图算法优点：起到正则化的效果，有效地防止模型的过拟合（bin数量决定了正则化的程度，bin越少惩罚越严重，欠拟合风险越高）。 直方图算法可以起到的作用就是可以减小分割点的数量， 加快计算。
与XGboost的分桶算法对比:
xgboost的分桶是基于 h i h_i hi? 的分布去找候选分割点，这样带来的一个问题就是每一层划分完了之后，下一次依然需要构建这样的直方图，毕竟样本被划分到了不同的节点中，二阶导分布也就变了。 所以xgboost在每一层都得动态构建直方图， 因为它这个直方图算法不是针对某个特定的feature的，而是所有feature共享一个直方图（每个样本权重的二阶导）。 而lightgbm对每个特征都有一个直方图，这样构建一次就OK， 并且分裂的时候还能通过直方图作差进行加速。 故xgboost的直方图算法是不如lightgbm的直方图算法快的。
单边梯度抽样算法(GOSS) 单边梯度抽样算法(Gradient-based One-Side Sampling)是从减少样本的角度出发， 排除大部分权重小的样本，仅用剩下的样本计算信息增益，它是一种在减少数据和保证精度上平衡的算法。
AdaBoost中，样本权重是数据重要性的指标。然而在GBDT中没有原始样本权重，不能应用权重采样。幸运的是，我们观察到GBDT中每个数据都有不同的梯度值，对采样十分有用。即梯度小的样本，训练误差也比较小，说明数据已经被模型学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练模型的精确度，为了避免此问题，提出了GOSS算法。
GOSS算法的亮点在于：根据样本的权重信息对样本进行抽样，减少了大量梯度小的样本，但是还能不会过多的改变数据集的分布
GOSS在进行数据采样的时候只保留了梯度较大的数据，但为了避免丢弃梯度小的数据而带来样本分布的改变，在计算增益时为梯度小的样本引入一个常数进行平衡。GOSS算法首先将要进行分裂的特征的所有取值按照绝对值大小降序排序，选取绝对值最大的 $a% $ 个数据。然后在剩下的较小梯度数据中随机选择 b % b\% b%个数据。接着将这b % b\% b%个数据乘以一个常数 1 ? a b \frac{1?a}{b} b1?a? ，这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布。最后使用这 ( a + b ) % (a+b)\% (a+b)%个数据来计算信息增益。举例说明：
文章图片
通过采样的方式，选出了两个梯度大的6号和7号，然后又从剩下的样本里面随机选了2个梯度小的4号和2号，如果直接把另外四个给删掉的话，这时候会改变数据的分布，但应该怎么做呢？ 也就是乘以一个常数 1 ? a b \frac{1?a}{b} b1?a? ，如下图所示：
文章图片
梯度小的样本乘上相应的权重之后，我们在基于采样样本的估计直方图中可以发现Ni的总个数依然是8个， 虽然6个梯度小的样本中去掉了4个，留下了两个。 但是这2个样本在梯度上和个数上都进行了3倍的放大，所以可以防止采样对原数数据分布造成太大的影响， 这也就是论文里面说的将更多的注意力放在训练不足的样本上的原因。
PS：小雨姑娘机器学习笔记中的那个例子挺有意思： GOSS的感觉就好像一个公寓里本来住了10个人，感觉太挤了，赶走了6个人，但是剩下的人要分摊他们6个人的房租。
互斥特征捆绑算法(EFB) 高维度的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。EFB算法就是通过捆绑特征来降低特征的维度。未使用EFB算法的时间复杂度为：
O ( 样 本 数 × 原 始 特 征 维 度 ) O(样本数\times原始特征维度 ) O(样本数×原始特征维度)
使用EFB算法后的特征维度为：
O ( 样 本 数 × 进 行 特 征 捆 绑 后 的 特 征 维 度 ) O(样本数\times进行特征捆绑后的特征维度 ) O(样本数×进行特征捆绑后的特征维度)
接下来通过例子说明：
文章图片
特征捆绑过程类似one-hot的逆过程。图片上通过特征捆绑把4个特征捆绑成一个特征。减少了维度。那么算法是怎么判定哪些特征应该绑在一起（build bundled）？
EFB 算法利用特征和特征间的关系构造一个加权无向图，构建图的过程中采用贪心策略，主要有以下几个步骤：
（1）将特征看成图中的各个顶点，如果两个特征之间存在同时不为0的样本 ，用一条边将这两个特征连接起来，特征同时不为0的样本的个数为边的权重。
（2）然后按照节点的度对特征降序排序， 度越大，说明与其他特征的冲突越大
（3）设置一个超参数阈值，对每一个特征，遍历已有的特征簇，如果发现该特征加入到特征簇中的矛盾数不超过某一个阈值，则将该特征加入到该簇中。 如果该特征不能加入任何一个已有的特征簇，则新建一个簇，将该特征加入到新建的簇中。
文章图片
这个过程的时间复杂度为 O ( 特 征 数 的 平 方 ) O(特征数的平方) O(特征数的平方) ，第一步遍历特征，第二步对每个特征还要遍历所有的簇。所以在特征数过多时，时间复杂度较高。为了提高效率，将特征按照非零值个数排序，这和使用图节点的度排序相似，因为更多的非零值通常会导致冲突，新算法在算法3基础上改变了排序策略。
通过上述过程，Lightgbm挑出了一些特征绑在一起，那么怎么把特征绑为一个（merge feature）呢？
特征合并算法，其关键在于原始特征能从合并的特征中分离出来。通过在特征值中加入一个偏置常量来解决。
比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间 [0,10)[0,10) ，B特征的原始取值为区间[0,20)，我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为[10,30)，绑定后的特征取值范围为 [0,30)，这样就可以放心的融合特征A和B了。
文章图片
通过EFB，减少了特征的数量，提高了训练速度，同时，对于类别型特征，如果进行one-hot编码，那么EFB算法会将其重新捆绑成为一个特征，所以在特征工程中没必要进行one-hot。
带深度限制的 Leaf-wise 算法 回顾GDBT的树生长算法：按层生长的决策树生长策略，如下图所示：
文章图片
遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。缺点在于：不加区别的对待同一层的叶子，但是很多叶子的分裂增益较低，没有必要进行搜索和分裂，导致了一些无用的计算开销。
而Lightgbm采用带有深度限制的按叶子生长 (leaf-wise) 算法。如下图所示：
文章图片
该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。Level-wise相比，优点在于：在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。缺点在于：可能会长出比较深的决策树，产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
LightGBM的工程优化 直接支持类别特征 对于类别型特征机器学习算法一般是通过one-hot来处理的，但对于决策树算法来说不推荐使用one-hot，因为当类别种类较多时，会使得：
（1）产生样本切分不平衡的问题，切分增益会非常小。使用 one-hot编码，意味着在每一个决策节点上只能使用one vs rest（例如是不是狗，是不是猫等）的切分方式。例如，动物类别切分后，会产生是否狗，是否猫等一系列特征，这一系列特征上只有少量样本为 111，大量样本为 000，这时候切分样本会产生不平衡，这意味着切分增益也会很小。较小的那个切分样本集，它占总样本的比例太小，无论增益多大，乘以该比例之后几乎可以忽略；较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零。比较直观的理解就是不平衡的切分和不切分没有区别。
（2）会影响决策树的学习。因为就算可以对这个类别特征进行切分，独热编码也会把数据切分到很多零散的小空间上，如下图左边所示。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习效果会变差。但如果使用下图右边的切分方法，数据会被切分到两个比较大的空间，进一步的学习也会更好。下图右边叶子节点的含义是X=A或者X=C放到左孩子，其余放到右孩子。
文章图片
而类别特征的使用在实践中是很常见的。且为了解决one-hot编码处理
类别特征的不足，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的 0 / 1 0/1 0/1 展开。LightGBM采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设某维特征有 k 个类别，则有 2 ( k ? 1 ) ? 1 2^{(k-1)} -1 2(k?1)?1 种可能，时间复杂度为 O ( 2 k ) O(2^k) O(2k) ，LightGBM 基于 Fisher的《On Grouping For Maximum Homogeneity》论文实现了O ( k l o g k ) O(klogk) O(klogk) 的时间复杂度
其基本思想在于每次分组时都会根据训练目标对类别特征进行分类，在枚举分割点之前，先把直方图按照每个类别对应的label均值进行排序；然后按照排序的结果依次枚举最优分割点。看下面这个图：
文章图片
从上面可以看到， s u m ( y ) c o u n t ( y ) \frac{sum(y)}{count(y)} count(y)sum(y)? 为类别的均值。当然，这个方法很容易过拟合，所以LightGBM里面还增加了很多对于这个方法的约束和正则化。 实验结果证明，这个方法可以使训练速度加速8倍。
特征并行 特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。XGBoost使用的就是这种特征并行方法。这种特征并行方法有个很大的缺点：就是对数据进行垂直划分，每台机器所含数据不同，然后使用不同机器找到不同特征的最优分裂点，划分结果需要通过通信告知每台机器，增加了额外的复杂度。
LightGBM 则不进行数据垂直划分，而是在每台机器上保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。具体过程如下图所示。
文章图片
数据并行 传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信。
LightGBM在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。具体过程如下图所示。
文章图片
投票并行 基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。具体过程如下图所示。
大致步骤为两步：
- 本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
- 合并时只合并每个机器选出来的特征。
文章图片
Cache命中率优化 XGBoost对cache优化不友好，如下图所示。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问算法进行改进。
文章图片
而 LightGBM 所使用直方图算法对 Cache 天生友好：
首先，所有的特征都采用相同的方式获得梯度（区别于XGBoost的不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中率；
其次，因为不需要存储行索引到叶子索引的数组，降低了存储消耗，而且也不存在 Cache Miss的问题。
文章图片
LightGBM的优缺点 速度更快
（1）LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
（2）LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
（3）LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
（4）LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
（5）LightGBM 对缓存也进行了优化，增加了缓存命中率；
内存更小
（1）LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，且不需要特征值到样本的索引，降低了内存消耗；
（2）LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。
缺点
（1）可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合；
（2）Boosting族是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行权重调整，所以随着迭代不断进行，误差会越来越小，模型的偏差（bias）会不断降低，所以会对噪点较为敏感；
（3）在寻找最优解时，依据的是最优切分变量，没有将最优解是全部特征的综合这一理念考虑进去；
参考文章
深入理解LightGBM
【LightGBM详解】白话机器学习算法理论+实战番外篇之LightGBM
