light-gbm如何理解对内存利用友好，顺序访问梯度

lightgbm如何理解内存友好，顺序访问梯度

很多地方都会提到lightgbm的一大特点是对Cache命中率优化

也就是说对Cache利用友好，具体体现在很多地方提到的顺序访问梯度（lightgbm官方讲解视频中也是这样说的顺序访问梯度Access gradient continuous）

• different features access gradient by same order
• re-order gradients one time ,and every feature can access gradient continuous

很多地方是这么说的，

• 预排序算法中有两个频繁的操作会导致cache-miss，也就是缓存消失（对速度的影响很大，特别是数据量很大的时候，顺序访问比随机访问的速度快4倍以上 ）。
• 对梯度的访问：在计算增益的时候需要利用梯度，对于不同的特征，访问梯度的顺序是不一样的，并且是随机的

• 对于索引表的访问：预排序算法使用了行号和叶子节点号的索引表，防止数据切分的时候对所有的特征进行切分。同访问梯度一样，所有的特征都要通过访问这个索引表来索引。

  这两个操作都是随机的访问，会给系统性能带来非常大的下降。

LightGBM使用的直方图算法能很好的解决这类问题。

• 首先。对梯度的访问，因为不用对特征进行排序，
• 同时，所有的特征都用同样的方式来访问，所以只需要对梯度访问的顺序进行重新排序(建不同特征直方图的时候相当于对梯度访问的顺序进行重新排序)，所有的特征都能连续的访问梯度。
• 并且直方图算法不需要把数据id到叶子节点号上（不需要这个索引表，没有这个缓存消失问题）

不知道大家理解的怎么样，反正我对后面说的LightGBM使用的直方图算法能很好的解决这类问题。 下面的表述理解了很久。

首先还是要回忆xgboost中如何获取梯度，根据什么去获取梯度。

首先都知道xgb中，每个特征有一个block，有这个特征的特征值排序信息，更准确的说有这个特征带权分位点的信息。

我们对每一个特征带权分位点来判断，根据这个分隔点，能分别将哪些数据分隔到左右节点中去。每行数据都是根据行号来对应样本的导数信息（一阶导，二阶导），从而累加到左右节点的G和H变量中去。

但是不同的特征根据分隔点划分数据是完全随机的，导致每次的根据待选左右节点内的样本，取拉样本的梯度是随机的，这样很不友好，对内存而言。

因为两点，

一，行号->叶子节点是需要索引的，而且随机

二，由于1的随机，导致了叶子节点内的样本梯度也需要根据具体行号取索引，并求和。可以所也是随机的。

上面可能说的不太专业，但不知道如何更好的表述

而在lightgbm中,一开始就没有了特征值的排序，

或者说把特征值的排序转化成了直方图分布（从左到由仍是有序的）这种表现形式。

而在对每个特征建立直方图的每个bin的时候，每个bin所包含的信息中就会累加计算这个bin内所包含样本的梯度信息（一阶导，二阶导），而在对bin进行分割时，划分样本形成新的子节点，该节点的G，H就直接用bin的梯度信息（一阶导，二阶导）来累加就好了，同时兄弟节点的G，H可以做差得到，这样我们把所有特征的直方图的各个bin的信息（包括各bin的阈值和各bin内的导数信息）放入内容，当滑动bin尝试新的 分隔节点时，新加一个bin内的梯度就好了（而这个都是已经提前算好的）。这样一看，xgb的获取梯度的方式是基于直方图的各bin来取的，这种方式，由于各bin内的梯度是提前算好的，是的这种方式下的取梯度自然是内存友好的。

所以再看上面的话

所有的特征都用同样的方式来访问，（方式是指访问直方图各bin内的梯度方式）

所以只需要对梯度访问的顺序进行重新排序(建不同特征直方图的时候相当于对梯度访问的顺序进行重新排序)，

所有的特征都能连续的访问梯度。（连续访问的是各bin内的梯度而不是指直接访问样本的梯度）

个人理解