2020/2/16 LightGBM原理之论文详解
https://mp.weixin.qq.com/s?__biz=MzU0MDQ1NjAzNg==&mid=2247485823&idx=1&sn=03cc300eef5a588c337452c759c787d1&chksm=fb39ac7…
1/9
LightGBM原理之论文详解
作者：立刻有
链接：
https://blog.csdn.net/shine19930820/article/details/79123216
编辑：石头
原文：LightGBM : A Highly Efficient Gradient Boosting Decision Tree
原文下载：后台回复“LightGBM"
【Abstract】
Gradient Boosting Decision Tree (GBDT)非常流行却鲜有实现，只有像XGBoost和pGBRT。当特征维
度较高和数据量巨大的时候，其实现中仍然存在效率和可扩展性的问题。一个主要原因就是对于每一个特征
的每一个分裂点，都需要遍历全部数据计算信息增益，这一过程非常耗时。针对这一问题，本文提出两种新
方法：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度
的one-side采样和互斥的特征捆绑）。在GOSS中，我们排除了重要的比例-具有小梯度的实例，只用剩下
的来估计信息增益，我们证明，这些梯度大的实例在计算信息增益中扮演重要角色，GOSS可以用更小的数
据量对信息增益进行相当准确的估计。对于EFB，我们捆绑互斥的特征（什么是互斥特征：例如特征间很少
同时非零。），来降低特征的个数。我们证明完美地捆绑互斥特征是NP难的，但贪心算法能够实现相当好
的逼近率，因此我们能够在不损害分割点准确率许多，有效减少特征的数量。（牺牲一点分割准确率降低特
征数量），这一算法命名为LightGBM。在多个公共数据集实验证明，LightGBM加速了传统GBDT训练过
程20倍以上，同时达到了几乎相同的精度 。
1. Introduction
GBDT因为其的有效性、准确性、可解释性，成为了广泛使用的机器学习算法。GBDT在许多机器学习任务
上取得了最好的效果（ state-of-the-art），例如多分类，点击预测，排序。但最近几年随着大数据的爆
发（特征量和数据量），GBDT面临平衡准确率和效率的调整。
GBDT缺点：对于每一个特征的每一个分裂点，都需要遍历全部数据来计算信息增益。因此，其计算复杂度
将受到特征数量和数据量双重影响，造成处理大数据时十分耗时。
解决这个问题的直接方法就是减少特征量和数据量而且不影响精确度，有部分工作根据数据权重采样来加速
boosting的过程，但由于gbdt没有样本权重不能应用。而本文提出两种新方法实现此目标。
Gradient-based One-Side Sampling (GOSS)：GBDT虽然没有数据权重，但每个数据实例有不同的梯
度，根据计算信息增益的定义，梯度大的实例对信息增益有更大的影响，因此在下采样时，我们应该尽量保
立刻有 2019-02-17机器学习算法那些事
资源评论
