LightGBM 简介
速度和内存算法
许多提升算法使用预排序的算法。
LightGBM使用直方图算法。 使用直方图的算法包括
- 减少的计算分裂收益的消耗
- 直方图相减
- 减少内存使用
- 减少通讯的开销
特征并行
通常使用one-hot编码来表示类别特征，但是这种方式不是
基本想法是，根据训练目标
传统的算法
特征并行的目的是采用并行的方式“找到最好分叉” 。传统的特征并行的步骤是
- 将数据做竖方向划分（不同的机器有不同的特征集合）
- 每个worker在当前特征找到最好的分裂点
- 交流不同的局部最好的分裂点，确定最好的分裂点
- 拥有最好的分裂点的worker将划分数据，并且将划分结果发送给别的workers
- 其他的workers根据划分结果将特征划分
传统算法的缺点
- 具有计算的开销，无法加速分裂
- 需要交流划分结果
LightGBM中的特征并行
#data很大的时候，特征并行不能提速很多。在LightGBM里，我们做了一点修改：我们不将数据做纵向划分，想法每一个worker都会保留所有数据。于是，LightGBM不需要交流划分的结果，因为每一个worker都知道如何划分数据。
LightGBM里的特征并行的过程如下：
- 所有workers找到最好的局部分裂点{feature, threshold}.
- 交流不同的局部最好的分裂点，确定最好的分裂点。
- 使用最好的分裂划分数据
但是，当#data很大的时候，这种特征并行算法依然有计算开销。所以，当#data很大的时候，最好使用数据并行。
数据并行
传统算法
数据并行的目的是并行整个角色学习。数据并行的过程是：
- 横向划分数据
- workers使用局部数据构造局部直方图
- 合并局部直方图成全局直方图
- 从合并的全局直方图找到最好的分裂点，实施划分
传统数据并行的缺点是
- 很高的通讯开销。如果使用点对点的通讯算法，通讯开销大约是
O(#machine * #feature * #bin)