为什么lightgbm比xgb快？

LightGBM采用了基于梯度的单边采样（GOSS）的方法。

在过滤数据样例寻找分割值时，LightGBM 使用的是全新的技术：基于梯度的单边采样（GOSS）；而 XGBoost 则通过预分类算法和直方图算法来确定最优分割。

在 Adaboost 中，样本权重是展示样本重要性的很好的指标。但在梯度提升决策树（GBDT）中，并没有天然的样本权重，因此 Adaboost 所使用的采样方法在这里就不能直接使用了，这时我们就需要基于梯度的采样方法。

梯度表征损失函数切线的倾斜程度，所以自然推理到，如果在某些意义上数据点的梯度非常大，那么这些样本对于求解最优分割点而言就非常重要，因为算其损失更高。

GOSS 保留所有的大梯度样例，并在小梯度样例上采取随机抽样。比如，假如有 50 万行数据，其中 1 万行数据的梯度较大，那么我的算法就会选择（这 1 万行梯度很大的数据+x% 从剩余 49 万行中随机抽取的结果）。如果 x 取 10%，那么最后选取的结果就是通过确定分割值得到的，从 50 万行中抽取的 5.9 万行。

在这里有一个基本假设：如果训练集中的训练样例梯度很小，那么算法在这个训练集上的训练误差就会很小，因为训练已经完成了。

为了使用相同的数据分布，在计算信息增益时，GOSS 在小梯度数据样例上引入一个常数因子。因此，GOSS 在减少数据样例数量与保持已学习决策树的准确度之间取得了很好的平衡。

上文部分转载机器之心

原论文链接如下

LightGBM: A Highly Efficient Gradient Boosting Decision Tree

主要的区别在于搜索策略，lightGBM优化了搜索策略，所以更快。

xgboost的作者这么点评LightGBM的，

“非常赞的工作，实现了和XGBoost不一样的搜索策略，所以在算法效果上并不是完全一样。

- XGBoost在单机默认是exact greedy，搜索所有的可能分割点。分布式是dynamic histogram，每一轮迭代重新estimate 潜在split candidate。

- LightGBM和最近的FastBDT都采取了提前histogram binning再在bin好的数据上面进行搜索。在限定好candidate splits,

- 主要的速度提升似乎来自于两点。 一个是搜索的时候选取delta比较大的叶子扩展。第二个是pre-bin之后的histogram的求和用了一个非常巧妙的减法trick，省了一半的时间。在算法和效果上面最近比较多的工作都开始基于提前限定分割点的近似算法然后快速求histogram。 这一类算法的潜在问题是限制了分割点只能是一开始的定下来的潜在这些。不知道这一点对于实际应用的影响会有多大。理论上数据越多，树越深的时候，需要的潜在分割点越多，可能需要根据训练来动态更新潜在的分割点。在算法上面采用delta比较大的扩展方向可以集中搜索提高比较重要的区域。一个潜在的问题是可能会忽略掉一些未来有潜力的节点。当然这些讨论都和具体的应用场景有关。

个人觉得exact greedy和histogram方法的还会共存一段时间。或许可以比较好的在系统上面对这两个一起支持。”

从纯工程的角度来说，lightgbm更好地处理了多进程（毕竟是微软）。

从优化角度来说，对数值特征找划分点时，lightgbm没有去穷举每个可能的数值，而是利用直方图只去尝试很少数的划分点。

抛砖引玉。