背景
微软 DMTK (分布式机器学习工具包)团队在 GitHub 上开源了性能超越其他 boosting 工具的。LightGBM 知乎上有近千人关注“如何看待微软开源的LightGBM？”问题，被评价为“速度惊人”，“非常有启发”，“支持分布式”，“代码清晰易懂”，“占用内存小”等。
历史演进
尽管近年来神经网络复兴并大为流行，但是 boosting 算法在训练样本量有限、所需训练时间较短、缺乏调参知识等场景依然有其不可或缺的优势。
LightGBM相关实验
LightGBM （Light Gradient Boosting Machine）是一个实现 GBDT 算法的框架，支持高效率的并行训练，并且具有以下优点(中文参考)：
- 更快的训练速度
- 更低的内存消耗
- 更好的准确率
- 分布式支持，可以快速处理海量数据
从 LightGBM 的 GitHub 主页上可以直接看到实验结果，在 Higgs 数据集上 LightGBM 比 XGBoost 快将近 10 倍，内存占用率大约为 XGBoost 的1/6，并且准确率也有提升。在其他数据集上也可以观察到相似的结论。
1. 训练速度方面
2. 内存消耗方面
3. 准确率方面
LightGBM vs XGBoost
Xgboost 已经十分完美了，为什么还要追求速度更快、内存使用更小的模型？
常用的机器学习算法，例如神经网络等算法，都可以以 mini-batch 的方式训练，训练数据的大小不会受到内存限制。
但是 GBDT 在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的 GBDT 算法是不能满足其需求的。
LightGBM 提出的主要原因就是为了解决 GBDT 在海量数据遇到的问题，让 GBDT 可以更好更快地用于工业实践。
XGBoost的几个小问题
目前已有的 GBDT 工具(如 xgboost)基本都是基于预排序的方法（pre-sorted）的决策树算法。这种构建决策树的算法基本思想是：
- 预排序耗时耗内存，对所有特征都按照特征的数值进行预排序。
- 其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。
- 找到一个特征的分割点后，将数据分裂成左右子节点。 这样的预排序算法的优点是能精确地找到分割点，但是缺点也很明显：
- 空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存。
- 时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
- 对 cache 优化不友好。（这一部分在xgboot中进行了工程化改进，提高cache命中率）在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对 cache 进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的 cache miss。
LightGBM 的优化点
主要有以下几个比较重要的优化，后续详细展开：
- 基于 Histogram 的决策树算法
- 带深度限制的 Leaf-wise 的叶子生长策略
- 直方图做差加速
- 直接支持类别特征(Categorical Feature)
- Cache 命中率优化
- 基于直方图的稀疏特征优化
- 多线程高效并行
- Gradient-based One-Side Sampling（GOSS）梯度单边采样
- Exclusive Feature Bundling 独立特征合并
Histogram 算法
直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
使用直方图算法有很多优点。首先，最明显就是内存消耗的降低，直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用 8 位整型存储就足够了，内存消耗可以降低为原来的1/8。
然后在计算上的代价也大幅降低，预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(#data#feature)优化到O(k#features)。
当然，Histogram 算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下没有太大的影响。
带深度限制的 Leaf-wise 的叶子生长策略
lightGBM抛弃了大多数 GBDT 工具使用的按层生长 (level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。Level-wise 过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上 Level-wise 是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
Leaf-wise 则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同 Level-wise 相比，在分裂次数相同的情况下，Leaf-wise 可以降低更多的误差，得到更好的精度。Leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在 Leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
直方图差加速
LightGBM 另一个优化是 Histogram（直方图）做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。利用这个方法，LightGBM 可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
直接支持类别特征
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化到多维的0/1 特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。
基于这个考虑，LightGBM 优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1 展开。并在决策树算法上增加了类别特征的决策规则。在 Expo 数据集上的实验，相比0/1 展开的方法，训练速度可以加速 8 倍，并且精度一致。
据我们所知，LightGBM 是第一个直接支持类别特征的 GBDT 工具。
多线程高效并行
在探寻了 LightGBM 的优化之后，发现 LightGBM 还具有支持高效并行的优点。LightGBM 原生支持并行学习，目前支持特征并行和数据并行的两种。
- 特征并行的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。
- 数据并行是让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。
LightGBM 针对这两种并行方法都做了优化:
- 在特征并行算法中，通过在本地保存全部数据避免对数据切分结果的通信；
- 在数据并行中使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行可以得到非常好的加速效果。更具体的内容可以看NIPS2016。
Gradient-based One-Side Sampling（GOSS）
其中文为梯度单边采样。大致的意思是根据样本某一特征上的单梯度作为样本的权值进行训练。其采样的方式有点巧妙：
- 选取前a%个较大梯度的值作为大梯度值的训练样本
- 从剩余的1 - a%个较小梯度的值中，我们随机选取其中的b%个作为小梯度值的训练样本
- 对于较小梯度的样本，也就是b% * (1 - 1%) * #samples，我们在计算信息增益时将其放大(1 - a) / b倍
总的来说就是a% * #samples + b% * (1 - a%) * #samples个样本作为训练样本。而这样的构造是为了尽可能保持与总的数据分布一致，并且保证小梯度值的样本得到训练。
Exclusive Feature Bundling
Exclusive Feature Bundling中文名叫独立特征合并，顾名思义它就是将若干个特征合并在一起。使用这个算法的原因是因为我们要解决数据稀疏的问题。在很多时候，数据通常都是几千万维的稀疏数据。因此我们对不同维度的数据合并一齐使得一个稀疏矩阵变成一个稠密矩阵。这里就有两个问题：
- 如何确定哪些特征用于融合且效果为较好？
- 如何将这些特征合并到一齐？
对于第一个问题，这是一个NP-hard问题。我们把feature看作是图中的点（V），feature之间的总冲突看作是图中的边（E）。而寻找寻找合并特征且使得合并的bundles个数最小，这是一个图着色问题。所以这个找出合并的特征且使得bundles个数最小的问题需要使用近似的贪心算法来完成。
它将问题一换成图着色算法去解决。构建一个以feature为图中的点（V），以feature之间的总冲突为图中的边（E）这里说的冲突值应该是feature之间cos夹角值，因为我们是尽可能保证feature之间非0元素不在同一个row上。首先按照度来对每个点（feature）做降序排序（度数越大与其他点的冲突越大），然后将特征合并到冲突数小于K的bundle或者新建另外一个bundle。算法的时间复杂度为O(#feature^2)。
第二问题是将这些bundles中的特征合并起来。
由于每一个bundle当中，features的range都是不一样，所以我们需要重新构建合并后bundle feature的range。在第一个for循环当中，我们记录每个feature与之前features累积totalRange。在第二个for循环当中，根据之前的binRanges重新计算出新的bin value（F[j]bin[i] + binRanges[j]）保证feature之间的值不会冲突。这是针对于稀疏矩阵进行优化。由于之前Greedy Bundling算法对features进行冲突检查确保bundle内特征冲突尽可能少，所以特征之间的非零元素不会有太多的冲突。
如此一来，数据的shape就变成了#samples * #bundles，且#bundles « #features。EFB降低了数据特征规模提高了模型的训练速度。
如何上手lightGBM
讨论了这么多算法和工程的东西，还是稳扎稳打写点代码吧~
超参数配置
具体的参数配置，可以去lightgbm官网-parameters进行详细了解
- num_leaves :LightGBM使用的是leaf-wise的算法，因此在调节树的复杂程度时，使用的是num_leaves而不是max_depth。 大致换算关系：num_leaves = 2^(max_depth)
- 样本分布非平衡数据集：可以param[‘is_unbalance’]=’true’
- Bagging参数：bagging_fraction+bagging_freq（必须同时设置）、feature_fraction
- min_data_in_leaf、min_sum_hessian_in_leaf
demo代码
这部分可以去lightgbm官网-get-started进行详细了解。
// 01. train set and test set
train_data = lgb.Dataset(dtrain[predictors],label=dtrain[target],feature_name=list(dtrain[predictors].columns), categorical_feature=dummies)
test_data = lgb.Dataset(dtest[predictors],label=dtest[target],feature_name=list(dtest[predictors].columns), categorical_feature=dummies)
// 02. parameters
param = {
'max_depth':6,
'num_leaves':64,
'learning_rate':0.03,
'scale_pos_weight':1,
'num_threads':40,
'objective':'binary',
'bagging_fraction':0.7,
'bagging_freq':1,
'min_sum_hessian_in_leaf':100
}
param['is_unbalance']='true'
param['metric'] = 'auc'
// 03. cv and train
bst=lgb.cv(param,train_data, num_boost_round=1000, nfold=3, early_stopping_rounds=30)
estimators = lgb.train(param,train_data,num_boost_round=len(bst['auc-mean']))
// 04. test predict
ypred = estimators.predict(dtest[predictors])
