从XGboost到lightGBM

XGboost

XGBoost是GBDT的一种高效实现，但是里面也加入了很多独有的思路和方法

我们先回顾一下CART回归树

CART回归树

CART回归树是假设树的结构为二叉树，通过不断将特征进行分裂去完成整个树的构建。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树，即
$R_1(j,s)=\begin{Bmatrix}x|x^{(j)}\leq s \end{Bmatrix}\,\, and \,\,\, R_2(j,s)=\begin{Bmatrix}x|x^{(j)}> s \end{Bmatrix}$R1​(j,s)={x∣x(j)≤s​}andR2​(j,s)={x∣x(j)>s​}

其实质就是在该特征维度上对样本空间进行划分，这种划分是非常复杂度，通常是NP难问题。因此，在决策树模型中是使用启发式方法解决特征划分问题。

典型CART回归树模型的目标函数为：

$L=\sum_{x_i\in R_m}(y_i-f(x_i))^2$L=∑xi​∈Rm​​(yi​−f(xi​))2

我们结合求解最优的切分特征j和最优的切分点s，那么目标函数就转化为求解如下式子：
$\underbrace{min}_{j,s}\left[\underbrace{min}_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\underbrace{min}_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2\right]$j,smin​​⎣⎡​c1​min​​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​​xi​∈R2​(j,s)∑​(yi​−c2​)2⎦⎤​

XGBoost算法原理

XGBoost算法思想就是不断地添加树，不断地进行特征分裂来完成一棵树的构建。每次添加一个树，实际上是学习一个新函数，去拟合上次预测的残差。我们训练完成时会得到k棵树 。当我们要预测一个样本的分数时，根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。如：
$\hat{y}=\phi(x_i)=\sum_{k=1}^Mf_k(x_i) \,\,where\,\, F=\begin{Bmatrix}f(x)=w_{q(x)} \end{Bmatrix}(q:R^m\rightarrow T,w\in R_n^T)$y^​=ϕ(xi​)=∑k=1M​fk​(xi​)whereF={f(x)=wq(x)​​}(q:Rm→T,w∈RnT​)

注:Wq(x)为叶子节点q的分数–可以理解为权重，f(x)为其中一棵回归树 。

损失函数

XGBoost目标函数定义为：$L=\sum_{i=1}^nl(y_i,\hat{y_i})+\sum_{k=1}^K\Omega (f_k)$L=∑i=1n​l(yi​,yi​^​)+∑k=1K​Ω(fk​)
目标函数由两部分构成，第一部分用来衡量预测分数和真实分数的差距，另一部分​则是正则化项。

正则化项同样包含两部分，$\Omega (f)=r T+\frac12\lambda ||w||^2$Ω(f)=rT+21​λ∣∣w∣∣2
T表示叶子结点的个数，w表示叶子节点的分数。r可以控制叶子结点的个数，$\lambda$λ可以制叶子节点的分数不会过大，防止过拟合。
新生成的树是要拟合上次预测的残差的，即当生成t棵树后，预测分数可以写成：$\hat{y_i}^{(t)}=\hat{y_i}^{(t-1)}+f_t(x_i)$yi​^​(t)=yi​^​(t−1)+ft​(xi​)
同时，可以将目标函数改写成： $L=\sum_{i=1}^nl(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\sum_{k=1}^K\Omega (f_k)$L=∑i=1n​l(yi​,yi​^​(t−1)+ft​(xi​))+∑k=1K​Ω(fk​)

很明显，我们接下来就是要去找到一个$f_t$ft​能够最小化目标函数。XGBoost的想法是利用其在$f_t$ft​=0处的泰勒二阶展开近似它。即$f(x+\Delta x)\approx f(x)+f\prime(x)\Delta x+(\frac12f\prime\prime(x)\Delta x^2)$f(x+Δx)≈f(x)+f′(x)Δx+(21​f′′(x)Δx2)

g一阶导数，h 为二阶导数：
$g_i=\partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)})$gi​=∂y^​(t−1)​l(yi​,yi​^​(t−1))
$h_i=\partial_{\hat{y}^{(t-1)}}^2l(y_i,\hat{y_i}^{(t-1)})$hi​=∂y^​(t−1)2​l(yi​,yi​^​(t−1))

目标函数近似为：

$L^{(t)}=\sum_{i=1}^n\left[ l(y_i,\hat{y_i}^{(t-1)})+g_if_t(x_i)+\frac12h_if_t^2(x_i) \right]+\Omega (f_t)$L(t)=i=1∑n​[l(yi​,yi​^​(t−1))+gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)

以上这就是XGboost的特点：通过这种近似，可以自行定义一些损失函数（例如，平方损失，逻辑损失），只需要保证二阶可导即可。由于前t-1棵树的预测分数的残差对目标函数优化不影响[因为t轮是在之前残差基础上进行预测，所以可以看作是常数]，可以直接去掉。简化目标函数为：
$L^{(t)}=\sum_{i=1}^n\left[ g_if_t(x_i)+\frac12h_if_t^2(x_i) \right]+\Omega (f_t)$L(t)=i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)

上式是将每个样本的损失函数值加起来，我们知道，每个样本都最终会落到一个叶子结点中，所以我们可以将所以同一个叶子结点的样本重组起来，过程如下：

$L^{(t)}$L(t)
$=\sum_{i=1}^n\left[ g_if_t(x_i)+\frac12h_if_t^2(x_i) \right]+\Omega (f_t)$=∑i=1n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)

$=\sum_{j=1}^T\left[ g_iw_{q(x_i)}+\frac12h_iw_{q(x_i)}^2 \right]+r T+\frac12\lambda \sum_{j=1}^Tw_j^2$=∑j=1T​[gi​wq(xi​)​+21​hi​wq(xi​)2​]+rT+21​λ∑j=1T​wj2​

$=\sum_{j=1}^T\left[ (\sum_{i\in I_j}g_i)w_j+\frac12(\sum_{i\in I_j}h_i+\lambda)w_j^2 \right]+r T$=∑j=1T​[(∑i∈Ij​​gi​)wj​+21​(∑i∈Ij​​hi​+λ)wj2​]+rT

前两步i=1 to n 其实是对于每一个样本来说，进行遍历
最后一步直接把样本放在叶子结点的结果中去计算，这样可以便于进行计算

因此通过上式的改写，我们可以将目标函数改写成关于叶子结点分数w的一个一元二次函数，求解最优的和目标函数值就变得很简单了。

对于一个固定的结构q(x) ，我们可以计算叶节点j的最优权重$w_j$wj​：

即对w求导，令其等于0

$w_j^*=-\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j}h_i+\lambda}$wj∗​=−∑i∈Ij​​hi​+λ∑i∈Ij​​gi​​

带入可以计算相应的最优损失函数
$L^{(t)}(q)=-\frac12\sum_{j=1}^T\frac{(\sum_{i\in I_j}g_i)^2}{\sum_{i\in I_j}h_i+\lambda}+r T$L(t)(q)=−21​∑j=1T​∑i∈Ij​​hi​+λ(∑i∈Ij​​gi​)2​+rT

分裂结点算法在上面的推导中，我们知道了如果我们一棵树的结构确定了，如何求得每个叶子结点的分数。但我们还没介绍如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点。

XGBoost使用了和CART回归树一样的想法，利用贪心算法，遍历所有特征的所有特征划分点。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。

假设$I_L$IL​和$I_R$IR​是拆分后的左右节点的实例集，且满足$I=I_L\bigcup I_R$I=IL​⋃IR​,拆分之后损失减少为：

$L_{split}=\frac12\left[ \frac{(\sum_{i\in I_L}g_i)^2}{\sum_{i\in I_L}h_i+\lambda}+\frac{(\sum_{i\in I_R}g_i)^2}{\sum_{i\in I_R}h_i+\lambda}-\frac{(\sum_{i\in I}g_i)^2}{\sum_{i\in I}h_i+\lambda} \right]-r$Lsplit​=21​[∑i∈IL​​hi​+λ(∑i∈IL​​gi​)2​+∑i∈IR​​hi​+λ(∑i∈IR​​gi​)2​−∑i∈I​hi​+λ(∑i∈I​gi​)2​]−r

这个公式通常被用于评估分割候选集（选择最优分割点），其中前两项分别是切分后左右子树的的分支之和，第三项是未切分前该父节点的分数值，最后一项是引入额外的叶节点导致的复杂度。同时可以设置树的最大深度、当样本权重和小于设定阈值时停止生长去防止过拟合。

正则化

XGBoost的正则化项为：
$\Omega (f)=r T+\frac12\lambda \sum_{j=1}^Tw_j^2$Ω(f)=rT+21​λ∑j=1T​wj2​
这里的r和$\lambda$λ，这是XGBoost自己定义的，在使用XGBoost时，你可以设定它们的值，显然，r越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。$\lambda$λ越大也是越希望获得结构简单的树。

总结

作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：

一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以直接很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。

二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。

三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

lightGBM

对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。

这样的预排序算法的优点是能精确地找到分割点。但是缺点也很明显：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。

最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

• 基于Histogram的决策树算法。
• 单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。
• 互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
• 带深度限制的Leaf-wise的叶子生长策略：大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法。
• 直接支持类别特征(Categorical Feature)
• 支持高效并行

Histogram的决策树算法

Histogram algorithm应该翻译为直方图算法，直方图算法的基本思想是：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

直方图算法简单理解为：首先确定对于每一个特征需要多少个箱子（bin）并为每一个箱子分配一个整数；然后将浮点数的范围均分成若干区间，区间个数与箱子个数相等，将属于该箱子的样本数据更新为箱子的值；最后用直方图（#bins）表示。看起来很高大上，其实就是直方图统计，将大规模的数据放在了直方图中。

我们知道特征离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。对于直方图算法来说最直接的有以下两个优点：

• 内存占用更小： 直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。也就是说XGBoost需要用32位的浮点数去存储特征值，并用32位的整形去存储索引，而 LightGBM只需要用8位去存储直方图，内存相当于减少为1/8；
  

• 计算代价更小： 预排序算法XGBoost每遍历一个特征值就需要计算一次分裂的增益，而直方图算法LightGBM只需要计算k次（ k可以认为是常数），直接将时间复杂度从O(#data*#feature)降低到 O(k*#feature) ，而我们知道#data>>k。

LightGBM另一个优化是Histogram（直方图）做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍。通常构造直方图时，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。在实际构建树的过程中，LightGBM还可以先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就可以用非常微小的代价得到它兄弟叶子的直方图。

注意： XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

带深度限制的 Leaf-wise 算法

在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。

XGBoost 采用 Level-wise 的增长策略，该策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂，因此带来了很多没必要的计算开销。

LightGBM采用Leaf-wise的增长策略，该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，Leaf-wise的优点是：在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度；Leaf-wise的缺点是：可能会长出比较深的决策树，产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

单边梯度采样算法

Gradient-based One-Side Sampling 应该被翻译为单边梯度采样（GOSS）。GOSS算法从减少样本的角度出发，排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。

AdaBoost中，样本权重是数据重要性的指标。然而在GBDT中没有原始样本权重，不能应用权重采样。幸运的是，我们观察到GBDT中每个数据都有不同的梯度值，对采样十分有用。即梯度小的样本，训练误差也比较小，说明数据已经被模型学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练模型的精确度，为了避免此问题，提出了GOSS算法。

GOSS是一个样本的采样算法，目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的。根据计算信息增益的定义，梯度大的样本对信息增益有更大的影响。因此，GOSS在进行数据采样的时候只保留了梯度较大的数据，但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布。所以，GOSS首先将要进行分裂的特征的所有取值按照绝对值大小降序排序（XGBoost一样也进行了排序，但是LightGBM不用保存排序后的结果），选取绝对值最大的$\alpha$α * $100$100个数据。然后在剩下的$1-\alpha$1−α * $100$100个数据较小梯度数据中随机选择$b$b * $100$100个数据。接着将这$b$b * $100$100个数据乘以一个常数$\frac{1-a}b$b1−a​ 【计算信息增益时将其放大】，这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布。最后使用这$a$a个数据来计算信息增益。下图是GOSS的具体算法。

互斥特征捆绑算法

高维度的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

• 哪些特征应该绑在一起
  将相互独立的特征进行绑定是一个 NP-Hard 问题，LightGBM的EFB算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外，我们注意到通常有很多特征，尽管不是
  100％相互排斥，但也很少同时取非零值。如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。经过简单的计算，随机污染小部分特征值将影响精度最多$O([(1-r)n]^{-\frac23})$O([(1−r)n]−32​) ，$r$r 是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。具体步骤可以总结如下：

  • 构造一个加权无向图，顶点是特征，边有权重，其权重与两个特征间冲突相关；
  • 根据节点的度进行降序排序，度越大，与其它特征的冲突越大；
  • 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。

  算法允许两两特征并不完全互斥来增加特征捆绑的数量，通过设置最大冲突比率$r$r来平衡算法的精度和效率。EFB 算法的伪代码如下所示：
  
  算法3的时间复杂度是$O(feature^2)$O(feature2)，训练之前只处理一次，其时间复杂度在特征不是特别多的情况下是可以接受的，但难以应对百万维度的特征。为了继续提高效率，LightGBM提出了一种更加高效的无图的排序策略：将特征按照非零值个数排序，这和使用图节点的度排序相似，因为更多的非零值通常会导致冲突，新算法在算法3基础上改变了排序策略。

• 解决怎么把特征绑为一捆
  特征合并算法，其关键在于原始特征能从合并的特征中分离出来。绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle中识别，考虑到histogram-based算法将连续的值保存为离散的bins，我们可以使得不同特征的值分到bundle中的不同bin（箱子）中，这可以通过在特征值中加一个偏置常量来解决。比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间[0,10]，B特征的原始取值为区间[0,20，我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为[10,30]，绑定后的特征取值范围为[0,30] ，这样就可以放心的融合特征A和B了。具体的特征合并算法如下所示：
  

LightGBM 相对于 XGBoost 的优点

1. 速度更快

• LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
• LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
• LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
• LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
• LightGBM 对缓存也进行了优化，增加了缓存命中率；

2. 内存更小

• XGBoost使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 降低为 ，极大的减少了内存消耗；
• LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
• LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

代码测试

为了测试时间我们需要使用一个比较大的数据集，所以选取了大家熟悉的MNIST数据集

先上XGboost

tt = time.time()
#dmatrix 格式 在xgboost当中运行速度更快，性能更好。
dtrain = xgb.DMatrix(x_train, label=y_train)
dtest = xgb.DMatrix(x_valid, label=y_valid)

xgb_params = {
    'seed': 0,
    'eta': 0.1,
    'colsample_bytree': 0.5,
    'silent': 1,
    'subsample': 0.5,
    'objective': 'multi:softmax',
    'num_class':10,
    'max_depth': 4,
    'min_child_weight': 3
}


bst = xgb.train(xgb_params, dtrain, 100, evals=[(dtrain,'train'), (dtest,'test')])

preds = bst.predict(dtest)
auc = accuracy_score(y_valid, preds)

print(auc)
print('Time used: {} sec'.format(time.time()-tt))

0.959
Time used: 1098.1514909267426 sec

再看看lightgbm

tt = time.time()
# 转换为Dataset数据格式
train_data = lgb.Dataset(x_train, label=y_train)
validation_data = lgb.Dataset(x_valid, label=y_valid)

# 参数
params = {
    'learning_rate': 0.1,
    'lambda_l1': 0.1,
    'lambda_l2': 0.2,
    'max_depth': 4,
    'objective': 'multiclass',  # 目标函数
    'num_class': 10,
}
# 模型训练
gbm = lgb.train(params, train_data, valid_sets=[validation_data])

# 模型预测
y_pred = gbm.predict(x_valid)
#print(y_pred)
y_pred = [list(x).index(max(x)) for x in y_pred]
print(y_pred)

# 模型评估
print(accuracy_score(y_valid, y_pred))
print('Time used: {} sec'.format(time.time()-tt))

0.9568
Time used: 74.20362401008606 sec

我们可以看到两者的准确率相差不大，但是时间上lightGBM快了很多
这里要提高准确率，可以自己调参进行测试，当然最好找一个比较小的数据集

后续：DeepGBM

参考：
https://mp.weixin.qq.com/s/zejkifZnYXAfgTRrkMaEww
https://blog.csdn.net/Andy_shenzl/article/details/105631577