日志

LightGBM

LightGBM 是一种基于决策树算法的快速 、 分布式 、 高性能的 GBDT 框架,它是传统 GBDT 算法的一种改进实现,“Light”主要体现在三个方面,即更少的数据 、 更少的特征 、 更少的内存,分别通过 GOSS(单边梯度采样)、 EFB(互斥特征捆绑)和 Histogram(直方图算法)三项技术实现。

GOSS (Gradient-based One Side Sampling 单边梯度采样)

Pasted

GOSS 是一种采样方法,在每次迭代前,先对样本进行采样,保留梯度变化最大的 a% 个样本,为了不改变样本分布,还需要从剩下的梯度变化较小的样本中随机采样 b% 个样本,并给予这 b% 个样本 (1-a)/b 的权重,这两部分样本为最终的训练样本。通过 GOSS 既保留了重要的样本,又在保持样本分布的同时大大减少了训练样本数,从而实现不影响模型准确性的同时大幅度提升训练效率。

GOSS 为什么以梯度作为样本权重?

因为 GBDT 对 loss 的负梯度进行拟合,所以样本误差越大,梯度的绝对值越大,证明模型对该样本的学习还不足够,相反如果越小证明模型对该样本的学习已经很充分,所以梯度的绝对值越大,样本重要性越高。(梯度是某一点最陡峭的地方,梯度大小形容它有多陡峭)

EFB(Exclusive Feature Bundling 互斥特征捆绑)

Pasted

对于具有高维稀疏特征的数据,很多特征是互斥的(即多个特征之间最多只有一个特征的取值为非 0),EFB 通过捆绑多个互斥特征形成一个“大特征”,从而大大减少特征的数量,相当于是一种降维的方法。

例如,特征 A 的取值为 0~10,特征 B 的取值为 0~20,A、B 为互斥特征,那么捆绑 A/B 形成特征 C,特征 C 的取值为 0~30,所以 B=5 与 C=15 是等价的。

构造特征直方图是训练 GBDT 的主要时间消耗,而构造特征直方图的时间取决于需要遍历的特征数量,通过 EFB 方法可以减少特征的数量从而加快训练的效率。

备注:找出最优的 bundle 组合数是一个 NP 问题,LightGBM 通过贪心近似算法解决。即转化为图着色问题,图中的点为特征,非互斥的特征用一条边连接,边的权重为相连特征的总冲突值,那么着色相同的点即为互斥点(特征)

直方图优化算法(Histogram)

Pasted

LightGBM 基于直方图算法优化查找最佳分割点的效率,在训练前首先通过直方图算法将连续特征离散化,相当于对特征的值进行分段划分,形成 k 个 bins(即 k 个离散值),构造一个宽度为 k 的直方图,在遍历数据时,根据离散值在对应 bin 上累积统计量(即梯度 g,样本数 n)。通过累积的统计量计算分裂增益,通过遍历所有 bin 寻找该特征的最佳分割点。

流程总结

  1. 特征离散化,得 k 个 bins,形成宽度为 k 的直方图
  2. 遍历数据,根据离散值在对应 bin 上累积统计量(g、n)
  3. 遍历 bins,通过累积统计量计算不同划分的分裂增益,求得最佳分割点

增益计算公式:

Pasted

其中 S 为梯度之和,n 为样本数,L/R/P 表示左 / 右 / 父节点

优点:

  1. 传统的 pre-sorted 算法(例如 XGBoost 的 exact greedy 算法)在计算某个特征的分裂增益时需要遍历所有的特征值的划分情况,而直方图算法只需要遍历 k 个 bins 的划分情况,时间复杂度从 O(#data * #features) 降到 O(#bins * #features),大大减少了计算量。
  2. 传统的 pre-sorted 算法需要对特征预排序,而直方图算法没有排序要求,进一步提升了效率。
  3. 直方图算法可以通过做差加速,即只需要知道父节点的直方图,和任一子节点的直方图,即可通过做差得到其兄弟节点的直方图,效率提升一倍。
  4. 由于直方图算法没有排序要求,因此不用额外存储排序索引,另外离散化后的特征值可以用更小的数据类型表示(例如 256 个 bin 则只需要用 8 位整型表示,即从通常的 4 字节降到 1 字节),以上两点都可以大大减少内存的占用。

分析:直方图算法主要围绕着训练更快 、 内存占用更少两个方面进行优化,虽然它找到的并不是最精确的分割点,但对最终的模型精度影响并不大,而且较粗的分割点本身也有正则化的效果,有时甚至会有更好的精度。另外,对于 bosting 框架而言,决策树本身是弱模型,单棵树的误差变化稍大,对最终的结果没有太大的影响。

并行学习(Parallel Optimization)

特征并行:

Pasted

每个 worker 负责计算各自特征子集的最佳分割点,然后再汇总计算全局最佳分割点,包含最佳特征的 worker 将分裂结果广播到所有 worker。由于 LightGBM 的各个 worker 都包含完整数据(即知道所有特征,但每个 worker 依然只负责一部分特征),所以每个 worker 只需要根据全局最佳分割点在本地分裂即可,不需要广播分裂信息到所有 worker, 从而减少通信量,代价是需要额外的存储空间。

数据并行:

Pasted

水平切分数据,每个 worker 根据局部数据统计局部直方图,然后再进行全局合并,根据全局直方图计算最佳分割点。LightGBM 对全局合并做了优化,每个 worker 负责合并不同特征的直方图,从而减少通信量,另外通过直方图做差加速可以进一步减少通信量。

基于投票的数据并行:

Pasted

水平切分数据,每个 worker 根据局部数据选出局部最优的 top-k 个特征,汇总每个 worker 的 top-k 个特征作为全局候选特征,基于全局候选特征进行数据并行处理。

LightGBM 对并行学习最主要的优化就是降低通信开销

LightGBM 与 XGBoost 对比

1.决策树生长方式不同:

Pasted

LightGBM 是 leaf-wise(按叶子)生长,即每次只在 loss 变化最大的叶子节点上进行分裂。XGBoost 则是 level-wise(按层) 生长, 即每次对所有叶子节点进行分裂(可能产生无必要的分裂),逐层生长直到满足最大深度。

A.level-wise 容易实现多线程优化,即同时对同一层的叶子进行分裂,但由于其不加区分的对待同一层的叶子,容易带来不必要的开销,因为很多叶子的分裂增益很低

B.对于小数据集,level-wise 通常表现更佳,因为 leaf-wise 在小数据集下容易导致过拟合(相当于数据简单但树太深,即模型太复杂,可以通过设置 max_depth 限制树的最大深度避免过拟合)。

C.对于大型数据集,leaf-wise 相比 level-wise 的训练效率更高,且模型精度通常会更高(叶子数相同时,leaf-wise 方式的树更深,loss 减少更多)。

备注:XGBoost 已支持 leaf-wise,即设置 grow_policy = lossguid

2.通过 GOSS + EFB 算法,LightGBM 的训练时间比 XGBoost 快得多
3.LightGBM 基于直方图算法(Histogram)将连续特征转化为离散特征,相比 XGBoost 的 Pre-sorted 方法效率更快,且内存占用更小。

备注:XGBoost 已支持 hist 和 approx 两种方式(tree_method),两者均实现将连续特征离散化,前者等价于 Histogram,后者即为加权分位点近似算法,前者只需要构建一次,后者需要每次迭代都重新构建。

4.LightGBM 直接支持类别特征,不需要做 one-hot 编码,避免了 one-hot 带来的特征维度膨胀。

Pasted

优点

  1. 快速 、 高效(GOSS、EFB、Histogram-based)
  2. 更少的内存(Histogram-based)
  3. 精准度高(leaf-wise 倾向于生成更复杂的模型,有过拟合风险,需要控制最大深度)
  4. 分布式支持,快速处理海量数据
转载请注明出处:

© http://hejunhao.me