关于 SlimGBM

近几天在wepe用 python 实现的tgboost的基础上,用 python 写了下slimgbm,见 https://github.com/zgw21cn/slimgbm. 1. 使用 histogram 寻找最优分割点 2. leaf-wise进行树增长

此博客对slimgbm 作了一下小结,包括 xgboost 的原理及作的2点改进。

1. 微软LightGBM

微软开源了新的 GBDT框架LightGBM,其与 xgboost 性能对比如下,来源于Benchmarking LightGBM: how fast is LightGBM vs xgboost?

image.png LightGBM 主要在哪些地方进行了优化呢? 1. 基于Histogram的split value 2. 带深度限制的Leaf-wise的叶子生长策略 3. 直方图做差加速 4. 直接支持类别特征(Categorical Feature) 5. Cache命中率优化 6. drop out 方法引入等

相较于 xgboost 的精确寻找分割点方法,即先对各个特征排序,然后对特征的每个取值计算 gain,这种寻找分割点方法慢但是精确;lightgbm将连续的特征值划分到不同的分箱(bin)中,这里各个 bin 尽量等频。当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。这种方法寻找分割点快但不是那么精确。

在 Histogram 算法之上,lightgbm 采用了 leaf-wise 的树增长方法。xgboost一般按层生长,即树按层尽量生长,见下图。

ndzMl3yAspi1xVMzgJzQ_fix.png

而lightgbm 的 leaf-wise 每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环。同时为了避免因为会长出比较深的决策树,产生过拟合,LightGBM在Leaf-wise之上增加了一个最大深度的限制。见下图。

1QpbhyGsAkf8YnF0_m2A_fix.png

2. xgboost原理

2.1 目标函数

目标函数为 math L(\phi)=\sum_il(y_i,\hat{y}_i)+\sum_k\Omega(f_k) 这里,采用 gradient boosting的方法来学习$\hat{y}i$。在进行进行模型学习时,保留原来的模型不变,加入新的$f$。 $$\hat{y}i^{(0)}=0$$ $$\hat{y}i^{(1)}=f1(xi)=\hat{y}i^{(0)}+f1(xi)$$ $$\hat{y}i^{(2)}=f1(xi)+f2(xi)=\hat{y}i^{(1)}+f2(xi)$$ $$...$$ $$\hat{y}i^{(t)} =f1(xi)+f2(xi)+...+ ft(xi) = \hat{y}i^{(t-1)}+ft(xi)$$ 下面我们需要选择合适的函数$f$,使得目标函数尽可能地小。

记$\hat{y}i^{(t)}$为第$i$个样本第$t$轮迭代,则 $$L^{(t)}=\sumi^nl(yi,\hat{y}i^{(t-1)}+ft(xi))+\sumk\Omega(fk)$$ 对误差函数$l(yi,x)$在$\hat{y}i^{(t-1)}$处进行二阶泰勒展开,有 $$l(yi,x)=l(yi,\hat{y}i^{(t-1)})+\frac {\partial l(yi,\hat{y}i^{(t-1)})}{\partial \hat{y}i^{(t-1)}} (x-\hat{y}i^{(t-1)})+\frac {\partial^2 l(yi,\hat{y}i^{(t-1)})}{\partial \hat{y}i^{(t-1)}} (x-\hat{y}i^{(t-1)})^2$$ 如果令$x=\hat{y}^{(t-1)}+ft(xi)$, 且记一阶导数$gi=\frac {\partial^2 l(yi,\hat{y}i^{(t-1)})}{\partial \hat{y}i^{(t-1)}}$, 二阶导数$hi=\frac {\partial^2 l(yi,\hat{y}i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}$

这样可以得到$l(yi,\hat{y}^{(t-1)}+ft(xi))$的二阶泰勒展开。 $$l(yi,\hat{y}^{(t-1)})+gift(xi)+\frac{1}{2}hift^2(xi)$$

代入目标函数,有 $$L^{(t)} \cong \sum{i=1}^n [l(yi,\hat{y}^{(t-1)})+gift(xi)+\frac{1}{2}hift^2(xi)]+\Omega(f_k)$$

移除第一项常数项后, $$L^{(t)} \cong \sum{i=1}^n [gift(xi)+\frac{1}{2}hift^2(xi)]+\Omega(fk)$$

到目前为止,我们讨论了目标函数中训练误差的部分。下面再来看如何定义树的复杂度。树的复杂度可定义为一棵树里节点的个数,以及每个叶子节点上面输出分数的$L2$模平方。

$$ \Omega(ft) = \gamma T + {1 \over 2}\lambda \sum wj^2$$

在这种定义下,可以将目标函数进行如下改写。其中$I$被定义为每个叶子上面样本集合$Ij =\{ i|q(xi)=j \} $,这里结构函数$q$把输入映射到叶子的索引号上面去,而$w$给定了每个索引事情对应的叶子分数是什么。

原目标函数可以改写为

$$L^{(t)} \cong \sum{i=1}^T [gift(xi)+ \frac{1}{2} hi ft^2(xi) ]+ \gamma T + {1 \over 2}\lambda \sum wj^2$$

$$ = \sum{j=1}^T [(\sum gi)wj+ \frac{1}{2}(\sum hi+\lambda )wj^2]+\gamma T $$

这里我们定义$Gj= \sum gi$ 及$Hj= \sum hi$,那么可以对这个目标函数求出$w$,以及最优$w$对应的目标函数最大的增益。

$$L^{(t)} = \sum{i=1}^T [Gjwj+\frac{1}{2}(Hj+\lambda)w_j^2]+\gamma T$$

对此一元二次函数求最优解,解得 $$wj^*=- \frac{Gj}{H_j+ \lambda }$$

$$obj=-\frac{1}{2} \sum{j=1}^T \frac{Gj^2}{H_j+ \lambda }+\gamma T$$

2.2 贪心算法寻找最优分割点

遍历特征中所有可能的分割点位置,根据下式找到最佳分割点。 $$Gain=\frac{1}{2} [\frac {GL^2}{HL+\lambda}+\frac{GR^2}{HR+\lambda}-\frac{(GL+GR)^2}{HL+HR+\lambda}]-\gamma$$

这里$\frac {GL^2}{HL+\lambda}$表示分割点左子树分数,$\frac{GR^2}{HR+\lambda}$表示分割点右子树分数,而$\frac{(GL+GR)^2}{HL+HR+\lambda}$表示不分割的话的分数。

3 slimGBM

3.1 Histogram寻找最优分割点

采用贪心算法需要把数据读入内存中,因此lightGBM提出了histogram方法进行近似查找。步骤如下。

  1. 对于特征 $xk$ , 按照等频找到特征的分界点集合 $ S= \{ s1,s2,...sl \} $。
  2. 对于S中每个分割点,对$x_k$中的值进行分桶。桶中的$G$,$H$值可进行累加。
  3. 按1.2中的计算Gain的公式,计算Gain值,找到最佳分割点。
3.2 leaf_wise 树增长策略

这里不需要多说了,每次分裂时,只对分裂收益大的叶子节点继续进行分裂。同时需要限制树的增长深度。

参考