1. abstract

需要做的笔记：

作者想解决什么问题？question

作者通过什么理论/模型来解决这个问题？method

作者给出的答案是什么？answe

1. question

   The efficiency and scalability are still unsatisfactory when the features dimension is high and data is large when it comes to some algorithm like XBGoost. for each features, they need t scan all the data instance to estimate the information gain of all possible split points.

2. method

   1. Grandient-based on-side sampling(GOSS)

      we should keep those instances with large gradients and only randomly drop those instance with small gradients.

      事实证明数据实例具有更大的梯度对于信息增益的计算影响越大。

   2. exclusvie feature bundling(EFB)

      when some features‘ space is quite sparse, we can safely bundle those feature to reduce features.

      mutually exclusive: 互斥特征

3. 提出了基于直方图的算法(histogram-based algorithm)

   在训练的过程中，把连续性的特征放在离散的直方图里面并且形成特征直方图。因为在计算效率(computation efficient) 和内存消耗(memory cosumption)都有更好的表现。具体如下：

   • computation efficient

     建立直方图\(O(data ?feature)\)分裂节点寻找\(O(data?feature)\)为\(bin\)通常都比\(data\)小很多，所以直方图可以减少计算消耗。

算法

GOSS（gradient-based one-side sampling）

在GDBT的算法中，我们发现那些梯度比较小的实例，他们的训练误差非常小或者可以说已经被训练地很好了。但是，数据分布就会被改变，对于我们的准确性预测就很差，所以为了解决这个问题，提出了GOSS算法。GOSS算法保存了所有梯度大的实例，并且抽样小梯度的实例。而为了弥补对数据分布带来的影响，我们来计算信息增益(information gain)。

• 首先，对所有实例进行绝对梯度的大小进行排序并且选取top \(\alpha?100%\) 选取实例。
• 随机从剩下的实例中选取样本 \(\beta?100%\) ，并且再对于梯度下的实例乘上一个系数 \(\frac{1-\alpha}{\beta}\)(正则项）

EFB

高维度的数据经常都是非常离散的。所以，这些离散数据提供给了我们一种方法去减少特征数。特别的是，当这些数据离散的情况之下，很多都是互斥的。所以我们可以绑定数据。当我们利用直方图的时候，直方图建立的复杂度从\(O(data?feature)\)到\(O(data?bundle)\)减少了时间复杂度。

分析

GOSS的算法准确率比起SGD更好，当他们用同样的抽样的话。再加上EFB，完美了。

对比

（1）xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。

（2）lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact 算法，histogram算法在内存和计算代价上都有不小优势。

1）内存上优势：很明显，直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features* 4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。

2）计算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)

3）lightgbm支持直接输入categorical 的feature，在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。

4）xgboost在每一层都动态构建直方图，因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。

其适用场景根据实际项目和两种算法的优点进行选择。

论文阅读： LGB

原文：https://www.cnblogs.com/louieowrth/p/12586111.html