上手机器学习系列-第6篇(下)-LightGBM原理篇
前言
前面的文章分享过了LightGBM的实践编码,本篇让我们一起来读一下算法论文《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》,从原理层面上去深入一层。
推荐大家在读论文的同时,参考LightGBM官网材料([https://lightgbm.readthedocs.io/en/latest/Features.html])来理解,这样可以对论文中省略掉的思路过程做一些补充。
论文解读
我们先来快速把握这篇论文的中心思想。它提出了两个具有创新性的方法:
- GOSS(Gradient-based One-Side Sampling),该方法的目的是缩减用于计算信息增益的样本集数量,参与计算的数据量少了,计算性能就更好了;
- EFB(Exclusive Feature Bundling),该方法目的在于减少用于参与分裂点筛选计算的特征变量数量,同样的,因为参与计算的对象少了,性能就提升了。
决策树算法的核心点就在于每来到一个树的分叉点时,选择哪个特征变量,以及选择哪个数值进行拆分。传统的做法就是遍历所有特征变量的所有可用于分裂的数值点(遍历所有样本记录),根据定义好的某个损失函数来进行最优化选择。面对海量数据时,这种算法往往会遇到计算性能瓶颈,容易想到的方法就是要么减少参与计算的样本量,要么减少特征变量的数量。但这并不是一个轻易的工作。作者的论文就是围绕这两点来展开的。
先说GOSS
这一段论文描述在直观上还是容易理解的,但有没有一种感觉:好像哪里还是模模糊糊的。比如我问你:每个样本实例的梯度怎么计算?为什么梯度大的,对于信息增益的贡献也大?筛选的阈值或比例怎么确定?
首先,回忆一下在通常的GBDT模型中,梯度代表了什么?
答案是代表了在当前boost轮次中,每个样本实例在损失函数计算中的“权重”。以平方和损失函数为例,笔者的思考如下:
其次,关于筛选的阈值,我们在论文中找到答案:
所以,这里涉及到了两个超参数(需要人工设定的参数)。并不是完全丢弃了小梯度的样本,而是随机选择了b%,并且在计算最后的信息增益时,把这部分小梯度的数据人为“放大”了(1-a)/b 倍。
读到这里,笔者建议大家在脑海里思考两个问题:1)a、b的值可能的取值区间会是什么?2) 对于小梯度的样本,为什么又人为乘了一个系数?这个系数又是怎么定义出来的? 这两个问题笔者也没有答案,其实想到什么程度并不重要,重要的是有没有尝试去往下再想一层,再想一层,直到我们无法参透为止。
其实,我们所谓的学习,到底是学什么呢?记住一些知识点吗?知道每个模型的步骤是啥?参数怎么设置?接口怎么调用?这些都还只是应用,笔者觉得最重要的是我们要学习如何去思考。世界这么大,人与人的差距是一个很残酷又很现实的情况,我们可能无力改变自己的很多方面,但一定要努力去改善自己的处世方式,向NB的人去学习“道”的东西,只有把如何思考学到手,才能做到知识迁移。否则以后遇到新的问题,我们仍然无从着手。
啰嗦病一犯又跑题了,再回来我们的论文阅读。
有了对于样本的处理后,还是要回答在单棵CART树(还记得吗?GBDT类的算法是集成了若干个回归树,而不是决策树)在每个节点上如何进行分裂,总得有一个量化的计算指标。在分类决策树中往往采用信息熵的差值来作为信息增益、信息增益率。在回归树中,常用残差平方和做为当前步骤的损失函数,那分裂后,就会有一个新的残差平方和,用原来的值减去新的值,就是分支动作带来的收益了。
作者论文中定义了下面这样一个信息增益量:
因为GOSS对样本做了缩减,且对于梯度小的样本乘了一个系数,所以其变种为:
论文中说该指标越大越好,所以对于不同的分裂点的选择标准就是最大化上述指标,对应的分裂点即最优选择。
BUT, 我们暂停一下来想想,1)为什么这里的信息增益是这样定义的?为什么说它等同于方差呢?2)缩减样本意味着什么?
我们先回想一下在离散变量情况下使用的信息增益,用熵来代表一个集合中的不确定性程度,熵越大,代表集合中的不确定性越高。那么决策树分支后,应该是每个分支越纯越好,也就是单个分支的熵值越小越好。在连续变量情况下,如果每个元素越靠近均值,则方差越小,元素值的分布差异性越大,整体的方差越大。因为我们希望分支后的纯度提升,其实就是要求分布的差异化越大越好,即方差越大越好。逻辑上有了这个感觉,形式上又该怎么理解呢?
我们回忆一下样本方差的统计学定义:
也有很多地方是直接将这里的n-1写作n的(其实写成n-1才是无偏估计)。
下面来尝试理解一下形式上的演变:
至于前面乘了一个系数,因为它等于分支前的样本总数,是一个常数,不影响对于极值的讨论。笔者就是这样从逻辑和形式上来理解论文的意思。
同时,LightGBM每次选择带来上述信息增益最大的节点进行分支,也即所谓的 leaf-wise 模式。
再聊EFB
这段话也很直观,意思就是把互斥的变量绑定到一起,这样就减少了总体的特征变量个数。但是,什么叫绑定呢?在选择分支节点的时候又具体怎么操作呢?
这个算法的实现手段有两个操作:1)对于确实互斥(不同时出现非零值)的特征,可以放心地把它们放到同一个bund里;2)对于不完全互斥的特征,在一定的噪声程度内,也允许它们放到同一个bund里,这样就进一步地减少了bund的数量。该算法的思路如下表:
我们思考这样一个问题:排序在前面的特征更容易被分到一个bund中,还是排在后面呢?笔者是这样想的,既然它是按照特征的度(相当于与多少个其它特征有关联,即不互斥),那排在前面的特征就更容易形成新的bund,排在后面的特征更容易被合并到同一个bund中。定性的理解如下图所示:
形成bund后,怎样去表示同一个bund中的N个特征变量呢?论文的方法是用bund中的N个变量来构造一个新的变量,原文描述如下:
这里笔者形象地理解如下:
这样一来,就把bund变成了一个特征变量,原来的N个特征就变成了现在的M个新的bund合并特征,只要M远小于N,计算量就得到了足够显著地降低。
到此,该论文的两大创新思想就理解完毕了。论文后面是从实验数据上证实自己的算法如何较其它方法更优。这里不赘述。
结语
本文带领大家一起走读了一下LightGBM的论文,对其中部分知识点稍做展开讨论,并用形象化的方法来加深理解。我们也注意到本文中并对提及对于类型变量如何处理(默认肯定还是需要进行one-hot-encoding喽),因为在下一篇中我们介绍CatBoost,也是一个基于树模型的集成算法,而它的卖点就在于可以直接处理类别型变量。
敬请继续关注本人公众号文章。如果您阅读中有所收获,也期望您能转发给身边同样爱好大数据技术的朋友~