上手机器学习系列-第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，也是一个基于树模型的集成算法，而它的卖点就在于可以直接处理类别型变量。
敬请继续关注本人公众号文章。如果您阅读中有所收获，也期望您能转发给身边同样爱好大数据技术的朋友~