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只内存可以消耗降低为原来的$\frac{1}{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) 把直方图合并的任务分摊到不同的机器。降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。
    • 
• 投票并行

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。

• 在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。
• 大致为两步
  • 1、本地找出top k特征，并基于投票筛选出最可能是最优分割点的特征
  • 2、合并是只合并每个其选出来的特征
  • 

Cache命中率优化

• cache即CPU访问的数据附近数据和最近被访问过的数据[时间局部性和空间局部性]，会被缓存在cache中，如果访问到了且cache有，那么直接过去取。
  • 命中率高即利用率高

对XGboost：

• 预排序之后，特征对梯度的访问是一种随机访问，并且不同的特征访问顺序不一样，无法对cache进行优化。

• 在每一层的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问顺序不一样，会造成较大的cache miss

对LightGBM(所采用的直方图算法对cache天生友好)：

• 1、所有特征都采用相同的方式获得梯度(而XGboost是通过不同特征通过不同的索引获得梯度)，只需要对梯度进行排序并可连续访问，大大提高了cache命中率
• 2、不需要储存行索引到叶子索引的数组，降低了储存消耗，这样在此就不存在cache miss的问题

缺点

• 可能会产生较深的决策树，产生过拟合。因此也才加上最大深度限制。
• boosting族的是迭代算法，每次迭代都是根据上次迭代的结果对权重调整，所以随着迭代误差会越来越小，模型的bias会不断降低。而由于LightGBM是基于偏差的算法，所以对噪声较为敏感。
• 在寻找最优解的时候，没有综合的考虑全部特征