理解和比较GBDT、XGBoost和LightGBM

学习目标

• 理解掌握各种集成学习算法的思路
• 从Boosting的发展脉络学习，理解每一种Boosting算法的原理和特点
• 可先从实例入手，再理解算法过程，反复消化
• 综合对比多种算法的区别，再仔细理解每一个差异点

Adaboost

• AdaBoost对每一个样本分配一个权重，对每一轮的弱分类器也分配一个权重。
• AdaBoost通过分类误差率来更新后一轮的样本权重，提高被错误分类的样本权重，降低正确分类的样本权重，这样没有被正确分类的数据，在后一轮得到更大关注。
• 同时对基分类器分配权重，加大误差率小的弱分类器权重，使其在表决中起较大作用。
  
  

Adaboost 例子

CART回归树

• 首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树都是都是CART回归树。
• 为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。
• 树算法最重要是寻找最佳的划分点，分类树用纯度来判断最佳划分点使用信息增益（ID3算法），信息增益比（C4.5算法），基尼系数（CART分类树）。但是在回归树中的样本标签是连续数值，可划分点包含了所有特征的所有可取的值。所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

CART回归树算法1

CART回归树算法2

提升树-回归问题例子

GBDT（梯度提升树）

• GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树
• 上面两节分别介绍了Decision Tree和Gradient Boosting，将这两部分组合在一起就是GBDT
• 提升树利用加法模型与前向分布算法实现学习的优化过程
• 当损失函数是平方损失或指数损失函数时，优化简单；当一般损失函数时，优化困难
• Freidman提出梯度提升，利用最速下降的近似方法，利用损失函数的负梯度拟合一个回归树
  
  

GBDT 例子

c=(1.1+1.3+1.7+1.8)/4=1.475

GBDT总结

• GBDT是基于Boosting的思想，串行地构造多棵决策树来进行数据的预测，对损失函数做梯度下降，每轮迭代都去拟合损失函数在当前模型下的负梯度，把待求的决策树模型当作参数，从而使得参数朝着最小化损失函数的方向更新。
• 相比AdaBoost, Gradient Boosting可以使用更多类型的损失函数，因此可以解决更多的问题。
• 最常见的损失函数是平方损失函数，square loss的优点是便于理解和实现，它的负梯度就是残

XGBoost

• XGBoost是对GBDT进一步改进
• 传统GBDT在优化时只用到一阶导数信息，XGBoost则对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。
  -XGBoost在损失函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。

XGBoost的近似算法

XGBoost的特点

• Shrinkage（缩减），XGBoost在进行完一次迭代后，会将叶子节点的权重乘上该学习率，削弱每棵树的影响，让后面有更大的学习空间。GBDT的实现也有学习速率
• 列抽样（column subsampling）。XGBoost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是XGBoost异于传统GBDT的一个特性。
• 稀疏值处理，sparsity-aware split finding。对缺失值自动学习出它的分裂方向（左子树或右子树）。

XGBoost的系统设计

• 分块并行，决策树最耗时是找最优的切分点，而这个过程中，最耗时的部分是将数据排序。为了减少排序的时间，XGBoost提出Block结构存储数据。
• 数据按列存储，可多线程并行执行。
• Block按列压缩
• Block Sharding， 将数据划分到不同硬盘上，提高磁盘吞吐率
  

LightGBM

• LightGBM是一个实现GBDT算法的分布式高效框架

LightGBM的直方图算法

LightGBM的leaf-wise分裂

• 对于树的分裂方法，它通过leaf-wise分裂产生比level-wise分裂更复杂的树，能够实现更高的准确率
• Level-wise同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂
  

LightGBM的GOSS采样算法

• GOSS算法全称为Gradient-based One-Side Sampling，即基于梯度的单边采样算法。
• 其主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度。只对梯度绝对值较小的样本按照一定比例进行采样，而保留了梯度绝对值较大的样本。
• 这就是所谓的单边采样。由于目标函数增益主要来自于梯度绝对值较大的样本，因此这种方法在计算性能和计算精度之间取得了很好的平衡。
  

LightGBM的EFB算法

• EFB算法全称是Exclusive Feature Bundling，即互斥特征绑定算法。可有效减少用于构建直方图的特征数量，从而降低计算复杂度，尤其是特征中包含大量稀疏特征的时候。
• 在许多应用场景下，数据集中会有大量的稀疏特征，这些稀疏特征大部分样本都取值为0，只有少数样本取值非0。通常可以认为这些稀疏特征是互斥的，即它们几乎不会同时取非零值。利用这种特性，可以通过对某些特征的取值重新编码，将多个这样互斥的特征捆绑成为一个新的特征。
• 对于指定为类别特征的特征，LightGBM可以直接将每个类别取值和一个bin关联，从而自动地处理它们，而无需预处理成onehot编码多此一举。

LightGBM的3个算法优化

• XGBoost模型训练的总体的复杂度可以粗略估计为：
  训练复杂度 = 树的棵数✖️每棵树上叶子的数量✖️生成每片叶子的复杂度。
  生成一片叶子的复杂度 = 特征数量✖️候选分裂点数量✖️样本的数量。

• LightGBM的3个算法改进：

  • Hitogram算法的主要作用是减少候选分裂点数量
  • GOSS算法的作用是减少样本的数量
  • EFB算法的作用是减少特征的数量
  LightGBM特征并行

LightGBM特征并行

• 李航《统计学习方法》
• 陈天齐《Introduction to Boosted Trees》
• GBDT算法原理以及实例理解
  https://blog.csdn.net/zpalyq110/article/details/79527653
  https://github.com/Freemanzxp/GBDT_Simple_Tutorial
• XGBoost论文解读
  https://jozeelin.github.io/2019/07/19/XGBoost/
• GBDT算法原理与系统设计简介
  http://wepon.me/files/gbdt.pdf
• AdaBoost、GBDT、RF、XGboost、LightGBM的对比分析
  https://zhuanlan.zhihu.com/p/56137208
• 贪心科技机器学习高阶班