GBDT

GBDT是集成学习的一种方式，它使用决策树作为基分类器，通过线性加和的模式将各个及分类器组合起来，形成一个比较强的分类模型。

XGBoost

XGBoost在精度和性能方便都对GBDT做了改进。

1. XGBoost将损失函数通过泰勒展开式展开，从而引入了二阶函数信息，能够加快模型的收敛，提高模型的精度。
2. 在损失函数中加入了正则化，从而控制了模型的复杂度，减轻模型过拟合的风险。正则项中考虑到了树的叶子结点数量和叶子结点值的平方和，叶子结点的数量同时也限制了树的高度。引入正则项后，能够提高模型的泛化能力。
3. XGBoost支持并行训练。需要注意的是，这里的并行并不是树层次的并行，因为提升算法本身来讲就是个串行结构，所以在树层次是无法做到并行的。这里的并行是指特征粒度的并行，在树节点分裂的过程中，需要针对多个特征进行验证，并选择信息增益最大的特征和分裂点进行分裂，所以并行是在这个方面上进行的。

LightGBM

GBDT和XGBoost在训练过程中每次迭代树模型时，都会多次遍历整个数据集，这个操作比较耗时，同时如果将数据集全部放入内存，又会占用过多的内存资源，特别是工业界的训练数据量。
所以基于以上的考虑，微软提出了LightGBM算法，算法原理方面和GBDT和XGBoost是一致的，都是对负梯度方向残差的拟合。

树的生长方式

XGBoost中树的生长采用了level-wise的方式，然而LightGBM使用的是带有深度 限制的leaf-wise的方式。

level-wise在分裂节点过程中，会一层一层的分裂叶子节点，同层的叶子节点不加区分地对待，所以某些叶子节点有可能对其分裂增益并不大，从而造成了一些资源和性能浪费。
leaf-wise在分裂节点过程中，会有有限选择增益比较大的叶子节点对其进行分裂，所以leaf-wise相比level-wise会有更高的精度。但同时相对level-wise，其过拟合风险也会更高，所以需要用树的深度加以限制。

分裂节点算法

XGBoost采用了pre-sort预排序算法，LightGBM采用了histogram直方图算法。

pre-sort算法会将每个特征的所有数值进行排序，然后对每个分裂点计算信息增益，最终找到信息增益最大的特征和对应的分裂点，进行分裂该叶子节点。
虽然这种做法能够获得比较精确的分裂点，但是，需要保存排序好的每个特征的数据，所以内存占用是原始数据的两倍。并且在计算时需要对每个分裂点计算信息增益，所以计算量也比较大。

histogram算法会将每个特征进行量化，使得连续相近的值落入不同的桶中，在分裂节点的时候，我们只需要针对每个桶中的离散值作为分裂节点计算信息增益，然后选择信息增益最大的特征和分裂点，进行分裂该叶子节点。
histogram算法只需要保存每个特征的离散值，不需要保存pre-sort的预排序结果，所以内存使用会减少很多。另一方面，其每个分裂点的选择从pre-sort的全体特征数据减少为桶的数量，因为桶的数量会远远少于特征数量，所以会大幅提升训练效率。最后使用桶量化的概念相当于正则化，所以会有更高的泛化准确率。
然后再说不足，histogram算法进行了数据量化，所以在每次分裂时，无法保证获取最准确的特征和相应分裂点。如果桶的数量比较少，有可能会造成欠拟合。

另外使用histogram算法，在对一个叶子节点统计完直方图后，可以父节点的直方图和该叶子节点直方图做差，获得兄弟节点的直方图。