决策树(decision tree, DT)作为一类基于树的分类模型,拥有非常好的可解释性与可视化能力,也具有非常强劲的性能。从1966年至今,经后人的探索,DT从装袋(Bootstrap AGGregatING, Bagging)、随机森林(Random Forest, RF)、提升(Boosting)、梯度提升(Gradient Boosting, GB)、极限梯度提升(eXtreme Gradient Boosting, XGBoost),逐步优化形成了现如今的轻量梯度提升机(light gradient boosting machine, LightGBM)。相较于原始的DT模型而言,LightGBM在精度、训练时间与并行度上都有不小的提升。本文就这一发展历程简述其优化思想。

从DT到XGBoost

DT

if 纹理 == 模糊 then
 return 坏瓜
if 纹理 == 稍糊 then
    if 触感 == 硬滑 then
        return 好瓜
...

决策树的分类本质上可以被表示为一套if-then式的离散规则,通过对属性的分割形成对样本的分类规则,与人类的的逻辑很是相似,这也是决策树模型很容易被解释的原因。

西瓜书决策树图例

当然,决策树形式上也可以被表示为一颗有根树,树的非叶内部节点的实质就是对某一属性的测试,而叶节点则是对应的某一样本类别。

很显然,在这个算法思想下,对于特征的选择显得尤为重要,主要体现在树的非叶节点上选择什么特征进行划分(连续问题还要考虑离散化),由此引入信息熵解决这一问题。

熵本来是物理学的概念,用于描述一个系统的混乱程度。1984年,信息学之父香农首次将这一概念引入信息论,用于表述对不确定性的一种描述。在DT算法里,利用规则划分数据可以理解为利用一套规则消除不确定性的过程,在这个过程中我们需要贪婪地选择能够提供更多信息的特征。

例如,对于ID3算法而言,其使用信息增益(infomation gain)来选择属性。通过计算余下各个属性对样本分类任务的信息增益,每次选择增益最大的属性进行划分。由此构建的决策树可以仅通过一次规则的制定而得出适用于整个数据集的一套规则。

Bagging

Bagging并不是基于树的,它的思想用“三个臭皮匠,顶一个诸葛亮”一句形容再合适不过。

西瓜书集成学习图例

通过把数据集划分为多个子集的方法,在每个子集上构建多个弱分类器,用“投票”的方式选择得票最多的分类选项,如此将多个弱分类器组合成一个强分类器。这也是集成学习的思想。

RF

接上节,RF便是Bagging的一种特化版本。相比于Bagging横向划分数据集,RF通过训练多棵DT并进行进行属性随机选择,使得每棵DT都是“属性不足”情况下的最优规则。组合这些DT,就可以得到一个RF。

RF基于集成学习的思想,相比单棵DT而言具有更强的泛化性能,也具有一定的抗噪声能力。

Boosting

Boosting也是一类集成学习的典范,但与Bagging不同,它采用对弱学习器加权组合的方式来集成。

例如,对于AdaBoost,算法过程是这样的:

  • 初始化样本权重,在此数据集上训练出第一个弱学习器。
  • 对训练错误的数据样本进行增强,即提高其惩罚权重。
  • 在增强的样本集上继续训练下一个弱学习器,并对所有弱学习器进行加权组合,从而得到最后的组合模型。

可以看出来,Boosting算法的执行是串行迭代的,推导出下一个学习器依赖于前一个的生成。

GB

若读者对深度学习有所了解,想必对梯度这一概念毫不陌生,梯度有两个方向——正梯度方向(函数正增长率最大方向)与负梯度方向(函数负增长率最大的方向)。基于梯度的算法将所要完成的任务视作一个函数$f(x)$,根据函数性质的不同不断降低或提升函数,方向就是$f^{'}(x)$的某个方向。

例如,定义损失函数为目标范围与预测范围的重合比例(这实际上是IoU,常用于目标检测等领域),学习器的目标则是不断降低损失函数的值,此为梯度下降。若定义目标函数的方向与上例相反,将目标函数值越大视作越好则为梯度上升。这二者的本质是相同的。

而这一节所要提到的GB与梯度上升并不相同,它是加了梯度的Boosting算法,本质上与Boosting的思想是一致的,只是在参数优化的过程中是朝着梯度的方向优化,所以其收敛速度要高于一般的Boosting算法。

GB算法也可以和树算法(如分类回归树(Claasification And Regression Tree, CART))相结合,即为梯度提升树(Gradient Boosting Decision Tree, GBDT)。

XGBoost

既然多了个极限(eXtreme),想必XGBoost在梯度提升方面将传统的GBDT做到了极致。

相较于传统的GBDT,XGBoost的优化主要体现在以下几点:

  • 在代价函数里引入正则项,惩罚复杂模型。
  • 在代价函数中引入二阶导数,使模型收敛更快。
  • 削减历史决策树的权值,让后期具有更大的学习空间。
  • 特征抽样,参考RF的做法防止过拟合的通知减少计算量。
  • 对缺失值的自动处理。
  • 对特征预排序,以此支持以block为粒度的并行。

XGBoost作为GBDT的一个优化实现,中的很多思想并不是第一次提出,但是它是在工程意义上恰到好处的一个。

LightGBM

在海量数据的工业界,传统的GBDT算法对于内存的消耗已经到了难以接受的地步,这也是LightGBM的提出动机。

LightGBM主要的是对决策树算法中对属性最佳分割点处进行了优化。

传统的GBDT算法(如XGBoost)在这方面使用的是基于预排序算法。先对所有特征按照数值进行排序,其寻找最佳分割点的时间复杂度为$O(\#data)$级别,但是这也导致需要存储预排序结果,同时每次计算分裂点增益贡献的时间复杂度也不可小觑。

所以LightGBM提出了一种基于直方图的特征最优分割点选择算法,其基本思想是将连续的特征进行离散化,在此基础上也就形成了#feature个直方图,如此操作便不需要再去保存所有的样本了。用离散化后的值进行索引,便可以很轻松地寻找到最优分割点,时间复杂度也从$O(\#data*\#feature)$优化到了$O(k*\#feature)$(k为离散后的bin的数量)。虽然这样做会损失一定的精度,但是实验表明这样的牺牲是值得的(详见源论文)。

LightGBM还对叶子生长策略进行了优化。它采用的是深度限制的叶子生长(leaf-wise)策略,即在每次在所有叶子结点中寻找增益贡献最大的叶子进行分裂。相比其它绝大多数GBDT算法采用的层生长(level-wise)策略,它可以减少很多没有必要分裂的节点的产生,同时加入了叶子深度限制以防止过拟合。这样做无疑在并行的优化方向上带来了困难,但考虑到直方图算法带来的优化,无疑又是一个最佳选择。

除了以上两点,LightGBM还有其它一些优化,如:直方图作差加速、支持类别特征、Cache访问优化等,这里就不再展开了,有兴趣的读者可以阅读参考文献(下附[1])。

LightGBM源论文

以上是LightGBM源论文中关于AUC与NDCG两个指标的实验结果。可见,在时间相同的情况下,LightGBM的性能远高于XGBoost,这主要得益于基于直方图优化的特征选择算法。

后记

写了这么多,本文也只不过是在“抓主干”,毕竟DT的第一个算法发表至今已过去50多年,就连LightGBM开源也过去了6年有余,期间无数学者作出的研究不是我写一篇文章能说清楚的。但有时候梳理算法演变逻辑也是梳理研究思路的一种方法,本文就这一方面希望给大家带来灵感,如有错误也望指出。


Ref

  1. https://mp.weixin.qq.com/s/M25d_43gHkk3FyG_Jhlvog
  2. https://towardsdatascience.com/https-medium-com-vishalmorde-xgboost-algorithm-long-she-may-rein-edd9f99be63d
  3. 《机器学习》,周志华著
  4. 《Machine Learning》, Mitchell
  5. https://zh.wikipedia.org/wiki/%E6%A2%AF%E5%BA%A6%E6%8F%90%E5%8D%87%E6%8A%80%E6%9C%AF
  6. https://www.zhihu.com/question/41354392
  7. https://stats.stackexchange.com/questions/202858/xgboost-loss-function-approximation-with-taylor-expansion
  8. https://zhuanlan.zhihu.com/p/99069186
Last modification:February 14, 2022
博客维护不易,如果你觉得我的文章有用,请随意赞赏