xgboost预排序
xgb计算分裂点时采用预排序。如果不用预排序的话，在分裂节点的时候，选中某一个特征后，需要对A按特征值大小进行排序，然后计算每个阈值的增益，这个过程需要花费很多时间。而xgb预排序的做法是，每一次残差计算好之后，对每维特征做预先排序，排好序后，对每一个维度不同阈值，计算增益，选择最佳分裂。
即预排序算法的步骤是：
- 对于每个节点，遍历所有特征
- 对于每个特征，根据特征值分类样例
- 进行线性扫描，根据当前特征的基本信息增益，确定最优分割
- 选取所有特征分割结果中最好的一个
预排序算法的优点是在计算最优分裂时，各个特征的增益可以并行计算。
缺点主要是空间消耗大，预排序后需要保存特征值及排序后的索引，因此需要消耗两倍于训练数据的内存。
Histogram算法
LightGBM 选择了基于 histogram 的决策树算法。相比于另一个主流的算法 pre-sorted（如 xgboost 中的 exact 算法），histogram 在内存消耗和计算代价上都有不少优势。其思想是将连续的浮点特征离散成k个离散值，构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
优点
- 内存消耗降低。Pre-sorted 算法需要的内存约是训练数据的两倍(2$\times$data$\times$features$\times$4Bytes)，它需要用32位浮点来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位的存储空间。对于 histogram 算法，则只需要(data$\times$features$\times$ 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 binvalue 用 uint8_t (256bins) 的类型一般也就足够了。
- 决策树算法在节点分裂时有两个主要操作组成，一个是“寻找分割点”，另一个是“数据分割”。从算法时间复杂度来看，在“寻找分割点”时，pre-sorted 算法需要O(#feature$\times$#distincted value )。而Histogram 算法需要O(#feature$\times$#bin )(#bin是histogram 的横轴的数量) 。
- Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅。速度提升了一倍。
缺点
Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
leaf-wise的生长策略
它摒弃了现在大部分GBDT使用的按层生长（level-wise）的决策树生长策略，使用带有深度限制的按叶子生长（leaf-wise）的策略。level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
支持类别特征
实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，转化one-hotting特征，降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑，LightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。
GOSS EFB
包含了两个新颖的技术：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采样和互斥的特征捆绑）来处理大数据量和高维特征的场景。
GOSS是一种在减少数据量和保证精度上平衡的算法。GOSS保留所有的梯度较大的实例，在梯度小的实例上使用随机采样。为了抵消对数据分布的影响，计算信息增益的时候，GOSS对小梯度的数据引入常量乘数。GOSS首先根据数据的梯度绝对值排序，选取top a个实例。然后在剩余的数据中随机采样b个实例。接着计算信息增益时为采样出的小梯度数据乘以(1-a)/b，这样算法就会更关注训练不足的实例，而不会过多改变原数据集的分布。
高维的数据通常是稀疏的，这种稀疏性启发我们设计一种无损地方法来减少特征的维度。特别的，稀疏特征空间中，许多特征是互斥的，例如One-hot之后的类别特征他们从不同时为非零值。我们可以绑定互斥的特征为单一特征，通过仔细设计特征臊面算法，我们从特征捆绑中构建了与单个特征相同的特征直方图。这种方式的间直方图时间复杂度从O(#data $\times$#feature)降到O(#data $\times$#bundle)，由于#bundle << # feature，我们能够极大地加速GBDT的训练过程而且损失精度。
并行优化
特征并行
特征并行算法目的是在决策树生成过程中的每次迭代中，快速地找到最优特征分裂点。特征并行的主要思想是在拥有不同的特征的不同机器上分别寻找最优的分割点，然后在机器间同步最优的分割点。
presorted 的特征并行算法
- 将数据集进行垂直切分。（不同机器worker有不同的特征子集）
- 每个worker寻找局部的最优分裂特征以及分裂点。
- 不同worker之间进行网络传输，交换最优分裂信息，最终得到最优的分裂信息。
- 具有最优分裂特征的worker，局部进行分裂，并将分裂结果广播到其他worker。
- 其他worker根据接收到的数据进行切分数据。
LightGBM的特征并行算法
LightGBM并没有垂直的切分数据集，而是每个worker都有全量的训练数据，因此最优的特征分裂结果不需要传输到其他worker中，只需要将最优特征以及分裂点告诉其他worker，worker随后本地自己进行处理。处理过程如下：
- 每个worker在基于局部的特征集合找到最优分裂特征。
- workder间传输最优分裂信息，并得到全局最优分裂信息。
- 每个worker基于全局最优分裂信息，在本地进行数据分裂，生成决策树。
我的理解是，传统的特征并行中，假设有3个特征A B C分别分布在三个机器A B C上，那么每个机器上只存有相应特征排好序后的特征值以及排序后的索引，当最优的分裂信息确定好之后，设最优的分裂为特征B，阈值为x，那么数据分裂时，只有机器B知道该如何分裂，而机器A和C均无法根据“特征B 阈值x”这一信息分裂。因此需要机器B先分裂，将分裂的结果（索引）告诉机器A C，机器A C 根据接收到的索引进行切分数据。因此传统的特征并行需要一个O（data）的通信代价，然后在每个机器上也需要O(data)的代价进行数据分割。而Lightgbm的特征并行其实并没有垂直的切分数据，即每个机器都有全量的数据（这可靠吗？因为LGB存储的是离散化后的bin值，因此内存消耗减少，理论上可以在每个机器上保存全量的数据），当最优的分裂信息确定好之后，设最优的分裂为特征B，阈值为x，那么数据分裂时，由于机器 A B C上都有全量的数据，因此机器A B C都可以根据“特征B 阈值x”这一信息分裂，因此只是O(#data)的复杂度，没有通信代价。
然而，当数据量很大时，特征并行算法还是受限于特征分裂效率。因此，当数据量大时，推荐使用数据并行算法。
数据并行
传统的数据并行算法：
- 水平切分数据集。
- 每个worker基于数据集构建局部特征直方图（Histogram）。
- 归并所有局部的特征直方图，得到全局直方图。
- 找到最优分裂信息，进行数据分裂。
缺点：网络传输代价比较大，如果使用point-to-point的传输算法，每个worker的传输代价为O(#machine #feature * #bin). 如果使用All Reduce并行算子，传输代价为O(2* #feature * #bin).
LightGBM的数据并行算法
LightGBM算法使用Reduce Scatter并行算子归并来自不同worker的不同特征子集的直方图，然后在局部归并的直方图中找到最优局部分裂信息，最终同步找到最优的分裂信息。
顺序访问梯度
预排序算法中有两个频繁的操作会导致cache-miss，也就是缓存消失（对速度的影响很大，特别是数据量很大的时候，顺序访问比随机访问的速度快4倍以上 ）。
对梯度的访问：在计算增益的时候需要利用梯度，对于不同的特征，访问梯度的顺序是不一样的，并且是随机的
对于索引表的访问：预排序算法使用了行号和叶子节点号的索引表，防止数据切分的时候对所有的特征进行切分。同访问梯度一样，所有的特征都要通过访问这个索引表来索引。
这两个操作都是随机的访问，会给系统性能带来非常大的下降。
LightGBM使用的直方图算法能很好的解决这类问题。首先。对梯度的访问，因为不用对特征进行排序，同时，所有的特征都用同样的方式来访问，所以只需要对梯度访问的顺序进行重新排序，所有的特征都能连续的访问梯度。并且直方图算法不需要把数据id到叶子节点号上（不需要这个索引表，没有这个缓存消失问题）
cache miss
cache主要用于CPU与内存之间的高速缓存。Cache作为内存局部区域的副本，用来存放当前活跃的程序和数据，它利用程序运行的局部性，把局部范围的数据从内存复制到Cache中，使CPU直接高速从Cache中读取程序和数据，从而解决CPU速度和内存速度不匹配的问题。高速缓冲存储器最重要的技术指标是它的命中率。 CPU在Cache中找到有用的数据被称为命中，当Cache中没有CPU所需的数据时（这时称为未命中），CPU才访问内存。
预排序算法中，假设梯度信息存在一个数组g[i]中，在对特征A进行增益时，需要根据特征A排序后的索引找到g[i]中对应的梯度信息。特征值$A_1$对应的样本行号可能是3，对应的梯度信息在g[3]，而特征值$A_2$对应的样本行号可能是9999，对应的梯度信息在g[9999]，即对于不同的特征，访问梯度的顺序是不一样的，并且是随机的。
而LGB算法中
$$
For\ i \ in \ (0,num\ of\ rows):\\
\ H[f.bins[i]].g += g_i;\\
\ H[f.bins[i]].n+=1
$$
也就是对梯度数组g[i]的访问是顺序的，不是随机的，大大提高的cache的命中率。
总结
主要的特点如下：
- 使用直方图简化计算，计算split时只考虑直方图的bin做划分点，而不细化到每个sample。
- 使用leaf-wise替代level-wise，每次选择delta-loss最大的节点做分割。
- 计算直方图时，两个子节点只用计算其中一个，另一个通过root和前一个做差可得。
- 基于histogram的算法，在寻找最佳split时，可以先顺序访问data的gradient，填入对应bin中，提高cache hit。
- 对于category类型的feature，可以直接作为特征输入，不需要转化成one-hot之类的编码，据说在准确度差不多的情况下速度能快8倍以上。
建直方图的过程如下：
- 首先对原数据排序；
- 然后统计出distinct value 以及对应的 count；
- 如果distinct value数目小于max bin数，则正好每个value放入一个bin；
- 如果distinct value大于max bin，计算bin大小的均值，按一定规则将sample放入bin，保证相同value的放入同一bin，bin包含的sample数尽量平均。
- 注：max bin的默认值是256。
对于category类型的feature，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。
在求split时，对于category类型的feature，算的是"按是否属于某个category值划分"的gain，这和数值型feature是完全不同的，它的实际效果就是类似one-hot的编码方法。
参考
如何看待微软新开源的LightGBM?
『 论文阅读』LightGBM原理
LightGBM的并行优化
LightGBM——提升机器算法
cache替换算法总结
浅谈决策树、GBDT、LightGBM