日志

LightGBM

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

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

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

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

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

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

对于具有高维稀疏特征的数据,很多特征是互斥的(即多个特征之间最多只有一个特征的取值为非 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)

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

流程总结

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

增益计算公式:

其中 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)

阅读全文

日志

XGBoost

xgboost 是对传统 GBDT 算法的一种改进实现,主要包括损失函数 、 正则化 、 分裂点查找优化 、 稀疏特征感知 、 并行化等方面.

原理推导

假设迭代训练 k 次,那么 xgboost 的模型函数可以表示为:

其中 k 表示决策树的数目,f 表示一棵 CART 树。那么,前 t 棵树的预测值可以表示为:

需要优化的目标函数为:

那么训练第 t 棵树的目标函数可表示为:

在前 t-1 棵树处进行二阶泰勒展开:

由于去除常数项 L 后不影响问题优化,因此目标函数化简为:

xgboost 定义正则项如下:

其中 T 为叶子数,wj 为第 j 个叶子节点的预测值(权重,prediction score)。目标函数为:

对于样本 xi ,在第 t 棵树的预测值表示为:

其中 q 表示树结构, q(xi) 表示样本 xi 在中被分到的叶子节点索引,wj 表示第 j 个叶子节点的预测值,因此原目标函数由样本表示形式(sample-wise)改写成树结构表示形式(structure-wise):

化简得:

其中 Gj 和 Hj 分别表示被分到第 j 个叶子节点的所有样本的 loss 的一阶(二阶)导数值之和,wj 表示第 j 个叶子节点的预测值(权重),T 表示叶子节点数。

对目标函数求关于 wj 的导数等于 0 即可得最优的预测值 wj^* 使得目标函数最小化:

将 wj^* 代入目标函数 obj^(t) 得 xgboost 的终极目标函数:

上式度量了一棵结构为 q(x) 的树的好坏,值越小越好!!!!

例子:

实际上我们无法枚举所有的树结构然后选择最优的树,xgboost 通过逐层优化的方式构建树模型。将一个叶子节点分裂为左右两个新的叶子节点带来的增益可以表示为:

上式就是 xgboost 的特征选择准则, Gain 越大代表分裂后带来的 loss 减少量越多,所以 Gain 越大越好.

策略:当 gain>0 或大于某个阈值时进行分裂,否则不分裂(相当于剪枝)

分裂点查找算法(split finding algorithm)

阅读全文

日志

GBDT

GBDT 是一种以梯度提升(Gradient Boosting )作为训练策略,以回归决策树(Decision Tree,通常是 CART 回归树)作为弱模型的集成学习算法。其中梯度提升指每次迭代中通过拟合当前模型损失函数的负梯度(伪残差)来学习新的模型 ,从而通过结合新的模型使得模型损失进一步降低,而最终将多个模型结合的过程就是损失函数最小化的过程。

GBDT 分为 G、B、DT 三个部分

DT:即 decision tree 决策树,准确来说是回归树
B:即 boosting,指串行集成的模型结构
G:gradient,它通过拟合当前模型的损失函数的负梯度(残差)来学习新的模型

当以最小平方损失(LeastSquaresError)作为损失函数,此时损失函数的负梯度与残差(真实值 – 预测值)等价:

因此,每个弱模型的生成都是对前面所有模型的累加结果的残差的修正。

GBDT 原始论文算法描述

阅读全文

日志

决策树 (Decision Tree)

决策树是一种非参数的监督学习算法,用于分类和回归任务,具有很强的解释性。决策树算法通过学习训练样本的特征,构建树状决策模型,最终生成一系列决策规则用于预测。

ID3 ( 信息增益, 分类算法,只支持类别特征,多叉树结构 )

特征选择准则

信息熵 : 随机变量 Y 的不确定程度

条件熵 : 在某一条件 X 的限制下,随机变量 Y 的不确定程度

信息增益 (Information Gain): 条件 X 减少随机变量 Y 的不确定性的程度

信息增益 = 信息熵 – 条件熵

说明 : 是否 PlayGolf 这件事的不确定性为 0.940,如果知道 outlook 的话,那么这种不确定性会减少 0.247

ID3 决策树构建步骤

  1. 计算每个特征的信息增益
  2. 选择信息增益最大的特征作为决策树的节点,并根据其特征取值分裂出分支节点
  3. 如果分支节点的熵为 0( 即该节点的分类决策完全一致 ),则该节点为叶子节点,如果熵大于 0,则继续分裂。
  4. 重复 1-3 的步骤,直到所有特征的信息增益小于阈值或没有特征可用为止。

ID3 算法只有树的生成,所以该算法产生的树容易过拟合。

C4.5 ( 信息增益率,分类算法,支持类别特征 + 连续特征,多叉树结构 )

C4.5 是对 ID3 的一种改进,ID3 使用信息增益作为特征选择准则,但信息增益有一个缺点,它偏向于选择特征取值种类多的特征,即特征取值种类多的特征信息增益往往比较大。例如,以身份证号码作为特征,由于每个样本的身份证号码都是唯一的,每个取值只有一个样本,一个分类,所以每个取值的条件熵为:

那么信息增益会被最大化,但这种特征显然不是合理的分裂节点,因为通过已知的身份证号码来预测未知用户显然是不可取的。

信息增益率 (Gain-Ratio)

c4.5 采用信息增益率作为特征选择的准则

例如 :outlook 特征取值为 sunny(5 个 ), overcast(4 个 ), rainy(5 个 ),总样本数 14 个,则 outlook 这个特征的分裂信息为 :

信息增益率为 :

启发式特征选取

信息增益率偏向于选择特征取值种类数较少的特征 ( 某个 Si 趋向于 S 时,分裂信息接近 0,信息增益率会非常大 ),可以通过启发式策略,先选取信息增益大于平均值的特征,再从这些特征中选取信息增益率最大的特征作为分裂节点。

连续特征处理

处理连续特征首先需要对连续特征进行离散化处理,即设定一个阈值分割连续特征,使其成为二类特征,而关键点在于如何选择合适的分割阈值。
1. 对连续特征的所有取值进行排序
2. 分别选取每两个取值之间的中点作为候选分割点。如果有 n 种取值,则有 n-1 个候选分割点
3. 计算不同分割方式的信息增益,信息增益最大的分割点作为最优分割点,并计算该分割方式下的信息增益率作为该特征的信息增益率。

例如:
连续特征 :0.5, 1.2, 3.4, 5.4, 6.0
以 (0.5 + 1.2)/ 2 = 0.85 作为分割点,计算信息增益 :

其中 l 是分割点左边的样本数,r 是分割点右边的样本数,N 是样本总数.
以 (1.2+3.4) / 2 = 2.3 作为分割点,计算信息增益 … 以此类推

CART( 基尼指数,分类 、 回归算法,支持类别特征和连续特征,二叉树结构 )

阅读全文