为什么lightgbm比xgb快?

  统计/机器学习 监督式学习    浏览次数:7471        分享
2

为什么lightgbm比xgb快那么多?感觉速度可能是xgb的5倍,但是精度、auc什么的都差不多。

lightgbm是用了什么独家窍门吗?


 

信春哥   2017-12-16 16:44



   3个回答 
8

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



SofaSofa数据科学社区DS面试题库 DS面经

sasa   2018-03-26 11:48

补充几个: 1.互斥特征绑定(EFB),如果说GOSS减少了样本数量,那么EFB则减少了特征数量。 2.lightGBM原生支持类别特征,生长过程中,自动将类别划分到俩个子集,并且可以以O(NlogN)的复杂度找到最优划分。 3.leaf-wise按叶生长,更加高效,当然也容易过拟合。 4.优化了并行的通信。 而预排序,直方图做差,稀疏识别在xgboost,lightgbm中都有体现 - nobodyoo1   2018-07-29 19:18
2

主要的区别在于搜索策略,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方法的还会共存一段时间。或许可以比较好的在系统上面对这两个一起支持。”

SofaSofa数据科学社区DS面试题库 DS面经

Zeus1998   2022-05-15 20:45

0

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

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

抛砖引玉。

SofaSofa数据科学社区DS面试题库 DS面经

高代兄   2017-12-19 11:31



  相关讨论

stack多个xgboost效果并不理想

到底什么时候用lightgbm什么时候用xgb

xgboost怎么调参?

xgboost展开到二阶导数有什么好处啊

GBDT和XGBoost在叶子节点权重计算上有什么不同?

xgboost为什么会有seed?随机性体现在哪里?

xgboost中的决策树的复杂度是怎么定义的?

xgboost是怎么做到regularization的?

GBDT和XGBoost使用的都是回归树,原理上是怎么支持解决分类问题的?

xgboost里的每棵树是不是等权重的?

  随便看看

'str' object has no attribute 'decode' 代码运行时有错误呢?请高手帮忙解决

R里线性回归结果中最后的F-statistic什么意思?有什么用?

pytorch里view(-1, 1)什么意思?

协方差矩阵一定是半正定的吗?

概率论中的鞅是什么?