LightGBM

同样也是决策树

从下图实验数据可以看出， LightGBM比XGBoost快将近10倍，内存占用率大约为XGBoost的1/6，并且准确率也有提升。

XGboost的优缺点与LightGBM

1、精确贪心算法

每轮迭代时，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。

2、Level-wise(按层生长)迭代方式

(同时分裂同一层的叶子,从而进行多线程优化,不容易过拟合)

很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销

3、预排序方法（pre-sorted）

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

4、对cache优化不友好

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

LightGBM

基于Histogram的决策树算法
带深度限制的Leaf-wise的叶子生长策略
直方图做差加速
直接支持类别特征(Categorical Feature)
Cache命中率优化
基于直方图的稀疏特征优化
多线程优化
利用了GOSS来做采样算法(基于梯度的one-side采样)
采用EFB(互斥的特征捆绑)来预处理稀疏数据(由于histogram算法对稀疏数据的处理时间复杂度没有pre-sorted好。因为histogram并不管特征值是否为0。)

Histogram算法

直方图算法

1、先把连续的浮点特征值离散化为k个整数，同时构造为k的直方图。
2、在遍历数据的时候，根据离散化后的值作为索引在直方图中积累统计量
3、当遍历一次数据后，直方图积累了需要的统计量，然后根据直方图的离散值，遍历找到最优分割点

简单来说就是离散化了数据，把一定连续的数据合并了(主要是数据量要大)

使用直方图的好处就是可以数据压缩。(基于XGboost的近似算法的百分比)
- 内存消耗变小：不需要额外的保存与排序的结果，而且可以只保存特征离散化后的值，而这个值用8为整型储存就行了。XGBoost需要用32位的浮点数去存储特征值，并用32位的整形去存储索引，而 LightGBM只内存可以消耗降低为原来的$1\over 8$
- 计算代价变小：
  - 预排序每遍历一个特征值就需要计算一次分类的增益，而直方图只需要计算k次(k可以被认为是常数)，直接把时间复杂度从O(#data#feature)降低到O(k#feature)
  - 从混合排序变成了桶排，期望少了个log
- 用每个桶的值代替了原来的信息相当于增加了正则化，降低了过拟合
坏处也很明显：
- 相似的数据被搞在一起就没有了差异性，很多细节特征放弃了
- k的数量决定了正则化的程度，k越少惩罚越重，容易欠拟合

直方图做差加速

这个算法还能进一步的加速，主要在于父节点向下传递这一块

一个子节点的Hisogram可以直接有父节点的Histogram和兄弟节点的Histogram做差得到。这样能提升一倍的速度
- 通常在构造Histogram的时候，需要遍历该叶子节点上的所有数据，但直方图做差仅需遍历直方图的k个桶
- 所以在建树的时候用启发式的方法，先计算数量小的子节点，做差得到大的

带深度限制的Leaf-wise的叶子生长策略

大多数GDBT结构使用的都是level-wise的按层生长策略，而这里使用的是带有深度限制的按叶子生长的方法(leaf-wise)
- XGboost每遍历一次同时分裂同一层的叶子
  - 虽然这样可以多线程优化，但是这样其实是一种低效的算法，因为他不加区别的对待同一层的叶子，实际上很多的叶子没有必要进行搜索和分裂，这样带来了狠毒没必要的计算开销
- LightGBM则是每次对从当前的所有叶子，找到分裂增益最大的一个叶子节点，然后分裂
  - 优点：可以降低更多的误差，得到更好的精度。且高效。
  - 缺点：可能会产生比较深的决策树，产生过拟合。==因此会加上最大深度限制==

单边梯度采样算法(GOSS)

Gradient-based One-Side Sampling
GOSS从减少样本的角度出发，排出大部分小梯度的样本，仅用剩下的样本计算信息增益
- 它是一种在减少数据量和保证精度上平衡的算法

对比adaboost，样本权重是数据重要性的指标。然后在GDBT中没有原始样本权重，不能采用权重采样。

不过，GDBT中每个数据都有不同的梯度值，对采样非常有用。即如果梯度小的样本，训练误差小，那么模型已经学的很好了。

==所以直接的想法就是==,丢掉这些梯度小的数据。不过显然，这样做会改变数据的分布，将会影响驯良模型的精确度，为了避免此问题，就提出了GOSS算法

1、首先，要将所有进行分裂的特征按绝对值从大到小排序

2、选取绝对值较大梯度前的$a%$个数据

3、然后从梯度较小梯度数据中随机选择$b%$个数据

4、然后我们对这些较小梯度的样本，在计算的时候乘上$\frac{1-a}{b}$，这样让信息增益放大，从而不会过多的改变数据分布

5、然后用着$(a+b)%$的数据来进行计算—>得到下采样的数据(下采样，总数据分布比例不均衡的数据中抽取数据来训练)

其实就是一个把一部分数据值缩放后的下采样方法

互斥特征捆绑算法(EFB)

Exclusive Feature Bundling

高维的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来较少特征的维度，而不是直接PCA之类的

通常，被捆绑的数据都是互斥的(即特征不会同时为非零值，像one-hot)，这样两个特征捆绑起来才不会丢失信息
如果两个特征并不是完全互斥，可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小的时候，我们就可以让他们捆绑

所以这个算法通过捆绑特征，最后可以简化直方图的时间复杂度，捆绑后的特征数远小于原始的特征数

解决哪些特征应该被捆绑在一起

将相互独立的特征进行捆绑是一个NP-hard问题(从无向图中把带权完全图都抽出来)

不过这不需要完全正确，错误尽量小就行，所以就贪心

1、构造一个无向图，顶点是特征，边带权重

2、根据节点的度降序排序，度越大，与其他特征的冲突越大

3、遍历每个特征，将它分配给现有的特征包或建立一个新的特征包，使得总体冲突最小

首先算法要允许两两特征并不完全互斥来增加捆绑的数量的话，那么就要通过设置最大冲突比率来平衡算法和效率

上面这个复杂度是O(#feature^2)的，在feature较小的时候可以接受，不过特征多的情况下，为了继续提高效率，LightGBM提出了一个更高效的排序策略：

将特征按照非零的个数排序，这和使用节点的度相似(就是在很多特征的情况下0的情况会比较多)

解决怎么捆绑

特征合并算法，关键在于原始特征能从合并的特征中分离出来。

绑定几个特征在同一个bundle中，需要保证绑定前的特征能从bundle中识别出来

考虑到histogram可以将连续值保存为离散值的bins(箱子)，我们可以使得不同特征的值分到bundle中的不同bin中

这可以在特征值总加一个偏置常量来解决
- 如，有两个区间[0,10),[10,20]，我们对于数据可以用区间的左index来偏置这个数据

工程优化

直接支持类别特征

大多数机器学习工具都无法直接支持类别特征，一般要把类别特征通过one-hot编码转化到多维的0/1特征，然后对决策树来说是不推荐使用one-hot编码的，因为会出现下面的问题

1、会产生样本切分不平衡的问题，导致切分增益非常小。
- 使用这个编码，在一个决策节点上只能使用one vs rest的切分方式(就如是每次切除一个出来)如果这个特征所占的比例太小，所贡献的增益是非常小的，较大的那个拆分集，几乎就是原始样本集，增益几乎为0。这就是问题所在
2、会影响决策树的学习。
- 用onehot切分会搞的比较的散，使得最后叶子的数据量都较小且树的深度还会变高，如左图
- 但是如果是右边的方法则会且的比较均匀

所以LightGBM优化了对类别特征的支持，可以直接输入类别特征，不用额外的0/1展开

LightGBM采用many vs many的方式来切分数据，将数据分为两个数据集
- 假如某个特征有k个类别，那么时间复杂度就是$O(2^k)$，但是LightGBM实现了个O(k log k)的复杂度的方法(还是用了贪心的思想)
  - 1、在枚举分割点之前，先把直方图按照每个类别均值进行排序
  - 2、然后按照排序的结果一次枚举最有分割点。
    - 如上图，$\frac{Sum(y)}{Count(y)}$为类别的均值
  - 3、这种方法很容易过拟合，所以还要加上约束和正则
- 结果发现，这种方法相比onehot，快乐8倍，精度还一样

支持高效并行

特征并行
- 不同机器在不同的特征集合上分别寻找最优的分割点，然后机器减同步最有的分割点（
  - XGboost就是用的这种方法。不过这个方法有个很大的缺点就是对数据进行垂直划分(类似数据库中垂直划分：按照特征的不同的数据库和服务器，这种划分缺点就是特征很多的时候不得行)，每台机器的数据不同，找到的最有分割点也不同，通知别的机器要额外的复杂度
- LightGBM不进行数据垂直划分，而是在每台机器上保留全部的训练数据，在得到最佳划分方案后可以在本地执行而减少不必要的通信
数据并行
- 传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。
  - 这样的通信开销很大
- LightGBM使用分散规约 (Reduce scatter) 把直方图合并的任务分摊到不同的机器。降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。
投票并行