#paper 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA. 论文地址：https://proceedings.neurips.cc/paper/2017/file/6449f44a102fde848669bdd9eb6b76fa-Paper.pdf 项目文档：https://lightgbm.readthedocs.io/en/latest/Features.html 在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基于预排序方法的决策树算法。这种构建决策树的算法基本思想是：首先，对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。 这样的预排序算法的优点是能精确地找到分割点。但是缺点也很明显：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。 为了避免上述XGBoost的缺陷，并且能够在不损害准确率的条件下加快GBDT模型的训练速度，lightGBM在传统的GBDT算法上进行了如下优化： 基于Histogram的决策树算法。 单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。 互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。 带深度限制的Leaf-wise的叶子生长策略：大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法。 直接支持类别特征(Categorical Feature) 支持高效并行 Cache命中率优化 其中两个加速GBDT训练的算法：Gradient-based One Side Sampling (GOSS) 和 Exclusive Feature Bundling (EFB)。在不影响精度的情况下，两个算法分别减少了GBDT训练中所需的数据量和特征量，从而加速了GBDT的训练。 GOSS: 在每一次迭代前，利用了GBDT中的样本梯度和误差的关系，对训练样本进行采样: 对误差大（梯度绝对值大）的数据保留；对误差小的数据采样一个子集，但给这个子集的数据一个权重，让这个子集可以近似到误差小的数据的全集。这么采样出来的数据，既不损失误差大的样本，又在减少训练数据的同时不改变数据的分布，从而实现了在几乎不影响精度的情况下加速了训练。 EFB：在特征维度很大的数据上，特征空间一般是稀疏的。利用这个特征，我们可以无损地降低GBDT算法中需要遍历的特征数量，更确切地说，是降低构造特征直方图（训练GBDT的主要时间消耗）需要遍历的特征数量。在稀疏的特征空间中，很多特征是exclusive的（即在同一个样本里，这一组特征里最多只有一个特征不为0）。每一组exclusive feature都可以无损地合并成一个“大特征”。构造直方图的时候，遍历一个“大特征”可以得到一组exclusive feature的直方图。这样只需要遍历这些“大特征”就可以获取到所有特征的直方图，降低了需要遍历的特征量。这里还需要解决的是Exclusive feature的分组问题，这是一个NP问题，可以转成Graph Coloring (Graph coloring - Wikipedia) 问题，并用贪心的近似方法来求解。 值得一提的是，XGBoost 也实现了 histogram 算法，比原来presorted算法快了不少。但相比LightGBM，还是慢了一些，且内存占用还是比较大。

#paper DOI: 10.1145/2939672.2939785，XGBoost: A Scalable Tree Boosting System 陈天奇这篇论文是16年在KDD上提出的，目前在树模型有更快更强的LightGBM，也有魔改catboost。大忙但是我们想要找到从GBDT到更快更强的树模型，还是要从这篇XGBoost开始。 XGBoost算法的在性能，速度方面都超越了其他算法。之所以这么好，主要得益于以下几个方面： 是一个基于多个弱分类器组成的模型，可以有降低防过拟合的风险。 提出了一种加权分桶，减少计算量。 对稀疏数据进行默认划分，减少计算量。 对内存的优化和做了并行化处理、 对CPU缓存的优化 对存储的优化 1. 正则化的目标函数来看，XGBoost 是一种加法模型，它包含多个个基学习器，每个基学习器可以选择 CART 或者线性函数，损失函数包含损失函数和正则项，防止过拟合。 2. 二阶泰勒展开求解来看，在求得使得目标函数最小化时，可以像 GBDT 一样计算目标函数梯度，然后让新的 CART 去拟合负梯度。不过 XGBoost 用了更优的方法，有点类似牛顿法，但又不完全一样。牛顿法是把目标函数在当前点做二阶泰勒展开，然后求解二次方程最优点。而 XGBoost 是在上一步处只对损失函数这项做了二阶泰勒展开，之后再求解最优点。 3. 缩减（shrinkage）和列抽样：这里的缩减和 GBDT 里的缩减一样，都是为了降低单棵树的影响，给后面的树留有空间。因此引入一个学习率，用它去乘每步生成的目标函数。列抽样在 GBDT 和随机森林里都有用到，它可以牺牲偏差来降低方差。实现方法就是在分裂节点的时候只用一部分特征。 4.树节点分裂：节点分裂的目标是找出一个特征，按照这个特征的某个节点分裂后，能够使目标函数降低最多。所以这里面有两层循环，外层是特征遍历，内层是特征值遍历。特征遍历没得说了，只能一个一个找，但是特征值遍历可以优化一些，缩短寻找最优分裂节点的耗时。 5. 稀疏感知：机器学习经常会碰到数据稀疏的问题，有三种情况会导致数据稀疏：1.数据存在大量缺失值2.数据中存在大量的 0 元素3.特征工程中使用了 one-hot 编码，产生了大量的 0；所以让算法能够感知数据的稀疏模式是非常重要的。XGBoost 的解决方法是在每个节点中设置一个默认方向，缺失值或者 0 元素直接走默认方向，不参与树模型的学习。 6.效率优化之分块并行：决策树学习过程中，最耗时的部分是分裂时对数据的反复排序。为了提高速度，XGBoost 用了空间换时间的方法。对于一列特征，它创建了等量的指针，每个指针都跟一个特征值绑定，采并指向对应样本，按照特征大小排序，把每一个特征的排好序的指针保存在块结构中，就实现了训练前对特征排序的目标，这样速度提升了，但是也因此需要额外空间存储指针。分条来说，块结构的设计有以下特点：1.采用 CSC（Compressed Sparse Column Format）这种稀疏格式存储数据 2.存储的特征已排好序。3.存储了指向样本的指针，因为要存取一阶导和二阶导等信息。4.由于 CSC 是按列存储的，所以可以在每次分裂时对特征使用多线程并行计算 7.缓存感知（Cache-aware）访问：提出的块结构能够优化节点分裂的时间复杂度，但是在索引样本时，存在对内存的非连续访问问题。这是因为我们是按特征大小顺序对样本进行访问，但样本不按这个顺序。对内存的非连续访问将降低 CPU 的缓存命中率。XGBoost 针对精准贪心算法和近似算法设计了两种不同的优化策略。 8.块的核外（Out-of-core）计算：当数据没办法被一次全部读入内存时，就需要用到核外计算方法，单开一个线程从硬盘上读取需要用到的数据，解决内存不够地问题。但是从硬盘读取数据相对于处理器来说是很慢的，所以 XGBoost 采用了两种方法平衡两者速度：块压缩。对于行索引，用当前索引减去开始的块索引，前面提到块大小为所以用 16 位的整数存储这个算出来的偏移，用这个偏移替代原先更占空间的索引。块分片。把数据分开存储到不同的硬盘上，等用的时候多个硬盘一起开工，提高读取速度。