梯度提升树(GBDT)，使用树(CART)模型作为基学习器。第n棵树的训练是拟合前n-1颗树与标签之间的残差(当前模型的损失函数的负梯度信息)进行学习的；学完第n棵树后，会对这n棵树的函数使用加权拟合标签。
优点：

  1. 预测阶段计算速度快，树与树之间可以并行化计算。
  2. 在分布稠密的数据集上，泛化能力和表达能力很强。
  3. 有较好的解释性和鲁棒性，能够自动发现特征之间的高阶关系，并且不需要对数据进行预处理。

缺点：

  1. 训练阶段必须串行计算。
  2. GBDT在高纬稀疏数据表现不好。
  3. 不适合于文本分类。

GBDT算法

GBDT伪代码.PNG
图1 GBDT算法伪代码
损失函数对前m-1颗树形成的模型进行求导得到梯度，该梯度的负方向是第m棵树拟合的残差；采用该残差的原因是使学习具有沿着函数梯度反方向下降的效果。每训练完一棵树都会重新训练每棵树的权重，降低每棵树的特性对整个模型的影响。

GBDT中对前m-1个模型形成的整个模型进行求导，m-1模型中每个模型的输出是整个模型的输入，因此该模型既可以使用交叉熵，也可以使用MSE。GBDT使用CART作为基学习器是因为CART既可以用作回归，也可以用作分类问题；既可以处理连续变量，也可以处理分类变量。

XGBOOST、LightGBM对GBDT的优化主要体现在并行化、数据采样、特征采样；例如寻找最大增益特征的时候，并行化计算增益。

XGBOOST的优化

  1. 采用泰勒公式的二阶梯度进行训练，可以提高精度。
  2. 加入了正则化，防止过拟合。
  3. 不仅仅可以采用决策树作为基学器，还可以使用线性分类器作为学习器。
  4. 使用近似算法替代贪心算法寻找最优分割点。
    1. 近似算法本质是对数据进行采样，采样的候选点有Global切分点、Local切分点。
    2. 切分点的选取是根据该特征分布的分位数。
    3. Global切分点只在模型初始化的时候选取一次，并且Global切分点间距越小产生的结果越接近贪心算法。
    4. Local切分点的产生于对树的节点进行分支时。
    5. 切分点的选取不是完全按照个数，而是按照二阶梯度进行选取；使用二阶梯度的原因是在目标函数中，二阶梯度对损失函数具有加权的效果。使用二阶梯度进行切分的时候使用了weighted quantile sketch 算法。
  5. 使用了Shrinkage(每棵树加权)方法降低了每棵树对整体模型的影响；使用列采样加快了计算速度，防止过拟合。
  6. 使用稀疏感知算法对稀疏数据或缺失值进行处理，并且加快了计算速度。
    1. 通过为每棵树学习一个默认的缺省方向，来处理缺失值或稀疏数据。
  7. 学习一棵决策树最耗时的是根据特征的值对数据进行排序，因此XGBOOST进行了预排序，保存在了block中，每个block保存若干个特征，并且使用CSC(稀疏矩阵)格式进行存储。
    1. 对特征值进行排序的时候，不会对稀疏数据进行排序，这样也加快了计算速度。
  8. 内存读写的优化：每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓存区，这样就实现了非连续空间到连续空间的转换，提高了效率。
  9. 硬盘读写的优化：对磁盘中的数据读取也进行了优化，使用块压缩减少空间消耗；使用块分区可以增加吞吐量。

优点:

  1. 采用正则化防止过拟合，降低了模型的方差。
  2. 使用二阶泰勒公式进行学习，增加精度。
  3. 使用Shrinkage削弱每棵树的影响，增大后续的学习空间。
  4. 使用列采样(特征采样)增加训练速度，防止过拟合。
  5. 使用稀疏感知算法增加了模型处理缺失值的能力，并且加快了训练速度。
  6. 使用预排序寻找最优切分点。

缺点：

  1. 每次对树的节点进行分支寻找最优切分点时，仍然需要进行遍历全量数据集。
  2. 预排序不仅仅需要存储特征数据，还需要存储特征对应样本的梯度统计索引，相当于消耗了两倍的存储空间。
    1. 存储索引为了便于计算一阶梯度和二阶梯度。

LightGBM的优化

LightGBM相较于XGBOOST计算速度和存储空间大大减小。

  1. 单边梯度抽样算法
  2. 独立特征捆绑算法
  3. 直方图算法
  4. 基于最大增益的leaf-wise算法
  5. 类别特征最优分割
  6. 特征和数据并行
  7. 缓存优化

    单边梯度抽样算法

    根据梯度大的样本相对于梯度小的样本对增益影响大的原理，对梯度小的数据进行采样，并且乘以GBDT算法 - 图2。其中大梯度样本的采样了a%，小梯度样本采样了b%。

    独立特征捆绑算法

    为了减少特征的数量，对互斥特征进行了捆绑。对特征捆绑的要求是捆绑之后仍然能够恢复原始特征。

    直方图算法

    基本思想是对连续特征进行离散化为k个离散特征，同时构造宽度为k的直方图用于统计信息，无需遍历整个数据，只需要遍历k个bin，就可以知道最优分裂点。
  • 内存占用更小
  • 计算速度更快

虽然该方法会损失精度，但是可以起到正则化的作用。
并且可以使用父节点减去相邻叶子节点进行当前叶子节点的直方图构建，大大减少了计算时间。

基于最大增益的leaf-wise算法

每次对增益最大的叶子节点进行分支，虽然增加了精度的损失，但是加快了训练速度和增加了正则化的作用。

参考文献

  1. 决策树（下）——XGBoost、LightGBM（非常详细）