前言
Boosting算法是传统机器学习中相当重要的一个分支。在深度学习流行以前，像XGBoost和LightGBM这样的算法几乎可以算是Kaggle竞赛的标配。由于其良好的性能和效果，无论是何场景，基本只要无脑上XGBoost即可。
那为何XGBoost和LightGBM有着这样强大的能力，人们又是如何一步一步锻造出这些强大的武器呢？希望通过本文，可以使大家能对Boosting中一些主流算法的发展历程以及作者设计的思路有一个更好的理解。
什么是Boosting
Boosting是集成学习的其中一种，其中心思想在于训练迭代式地模型来不断逼近最终结果。和Bagging方法不同的是，Boosting希望其基分类器的方差较小而偏差可以较大，也就是说可以欠拟合，但决不能过拟合。这是因为Boosting的每个模型有依赖关系，后一个模型是在前一个模型的基础之上进行训练的，不怕步子迈的小，就怕方向跑偏了。
这里主要介绍一下AdaBoost和Boosting Tree相关的一些算法，其中AdaBoost是通过改变样本权重来不断影响模型结果的，而Boosting Tree则是一个Additive Model，最终的预测结果是所有模型预测结果的累加。我们的重点会放在Boosting Tree相关的一些模型上。
Boosting算法的本质上都可以理解为通过迭代式地改变训练数据概率分布来学习多个弱学习器，并利用这些弱学习器组合成一个强学习器。
AdaBoost
AdaBoost的过程可以简述为迭代式地计算基学习器的误差，根据误差调整样本权重，然后再去训练新的基学习器。训练完所有基学习器后，最终的预测结果就是各个基学习器的加权平均。算法详细地过程、推导和示例可以去参考李航的《统计机器学习方法》，下面说说我认为比较重要的几个点：
(1) AdaBoost的算法中并没有规定基分类器的类型，只要求基分类器 $G_{m}(x):\mathcal{X} \to {-1,+1}$ 。因此，理论上AdaBoost支持任意种类的基分类器。
(2) $G_{m}(x)$ 的系数 $\alpha_{m}$ 的定义—— $\alpha_{m} = \frac{1}{2}log\frac{1-e_{m}}{e_{m}}$[注1] 和训练数据集的权值分布更新公式一起保证了AdaBoost的训练误差是有一个上界的，并且这个上界可以通过在每一轮选取适当的 $G_{m}$ 而减小。当训练任务为二分类任务时，训练误差的上界是以指数速率下降的。
(3) AdaBoost算法是前向分步加法算法的特例。这时模型是由基本分类器组成的加法模型，损失函数是指数函数，即 $L(y, f(x)) = exp[-yf(x)]$ 。
注1：其中 $e_{m} = \sum_{i=1}^{N}P(G_{m}(x_{i}) \ne y_{i}) = \sum_{i=1}^{N}w_{mi}I(G_{m}(x_{i}) \ne y_{i})$ ，是 $G_{m}(x)$ 在训练数据集上的分类误差率
注2：2、3的具体推导见李航的《统计机器学习方法》。
Boosting Tree（提升树）
提升树是一种加法模型，其基学习器为二叉树。提升树模型可以表示为决策树的加法模型：
$ f_M(x) = \sum_{m=1}^{M}T(x;\Theta_{m}) $
其中 $T(x;\Theta_{m})$ 表示决策树，$\Theta_{m}$ 表示决策树的参数， M为树的个数。可以通过最小化经验风险来确定下一个决策树的参数 $\Theta_{m}$ ：
当处理回归问题，且损失函数为平方损失函数时，可以很简单地推导出 $T(x;\Theta_{m})$ 拟合的其实就是残差 $y - f_{m-1}(x)$ 。而当处理二分类问题，并且损失函数为指数损失函数时，这其实就是AdaBoost的一个特殊情况（基分类器为二类分类树）。
注：这里需要注意，二类分类树的叶子节点取值需要等于{-1,+1}，不能是概率值，且y的取值需要是{-1,+1}，不能是{0, 1}。
当然，上面的回归问题中我们只是知道 $T(x;\Theta_{m})$ 需要拟合残差，但仍然不清楚如何得到最优的 $\Theta_{m}$ 。事实上，$\Theta_{m}$ 是很难得到的，通常只能通过启发式算法来获取，例如找到某个切分点，使得新生成的两个叶子节点内的样本平方误差之和最小。
上面的提升树针对的是平方损失函数和指数损失函数，如果想要将其扩展到任意损失函数应该怎么做呢？这里就不得不提到梯度提升树（GBDT）了。
GBDT
梯度提升树，顾名思义就是利用损失函数的负梯度在当前模型的值：
来替代提升树中的残差作为拟合回归树的目标。这近似于最速下降法，即把 $f(x_{i})$ 看做是变量，沿着损失函数相对于它的负梯度进行优化。
和提升树类似，上面的优化仅仅针对目标函数本身，对于单个决策树，我们仍然缺乏一个构建的方式。在GBDT中，通常采用CART回归树作为基本决策树（无论是分类还是回归问题）。有人可能会觉得，在分类问题中采用CART回归树显得很奇怪，因为我们的标签不是是0、1吗？怎么去回归呢？
事实上，假设损失函数为交叉熵，我们可以得到负梯度为 $y - f_{m-1}(x)$ ，居然也是残差（具体推导可以参考这篇文章）。因此我们可以用回归树来拟合真实标签和预测概率之间的残差，从而将一个分类问题转化成一个回归问题。多分类问题也是类似的。
初始值（即 $f_{0}(x)$ ）的设定是使损失函数最小的一个常数。对于平方损失函数就是均值，对于交叉熵就是标签1的先验概率。
XGBoost
前面提到，GBDT是沿着损失函数相对于当前预测结果的负梯度进行优化的，近似于最速下降法。然而，由于只利用了一阶信息，并且也没有一个类似学习率的东西进行控制，因此收敛起来还是比较慢。
XGBoost在GBDT的基础之上做出了诸多改进。从算法角度说，XBGoost在损失函数的优化上引入了二阶信息，加快了收敛速度；同时加入了一个设计好的正则项，有效地防止了过拟合。从工程角度说，XGBoost对寻找分裂节点的部分进行了优化，通过计算特征分位数加预排序减少了这部分的计算量，也更方便进行并行化操作；同时将数据按列存储、针对容易cache missing的问题进行了优化，方便了并行或者减少了计算时间；针对数据存储部分也通过块压缩和块分片的方式进行数据压缩和吞吐量提升。从上面的介绍也可以看出，相比于算法上的改进，XGBoost更多的是聚焦在工程优化上，让其更加scalable。
XGBoost的算法原理在很多地方都有详细地介绍，简单来说其思想就是将损失函数进行二阶泰勒展开，通过最小化二阶泰勒展开之后的结果来近似最小化原损失函数。而二阶泰勒展开的好处就在于可以在优化的时候舍弃只和之前的学习器相关的项，而将重点聚焦在和当前学习器相关的部分：
其中 $g_i$ 和 $h_i$ 相对于当前学习器来说是常数，可以事先计算好。将该损失函数进行变换之后可以得到一个关于 $w$ 的二次函数：
对于 $w$ 求导就可以得到其最优分裂点。另外，这里的正则项把 $w^2$ 考虑了进去，即不希望 $w$ 的值太大，这和Boosting的主线还是很符合的（不希望单个基学习器做太多事）。
LightGBM
从前面也可以基本看出，在算法上，提升树系列算法的改进空间不大了。因为从效果和效率的双重角度考虑，二阶泰勒展开已经具备了足够的信息，并且有着很不错的普适性（对损失函数或者基学习器的要求很少）。因此，后续的改进，例如这里说的LightGBM也更多地把心思放在了效率的优化上。
从LightGBM的论文就可以看出，其相比XGBoost最大的两个改进分别是Gradient-based One-Side Sampling (GOSS)和 Exclusive Feature Bundling (EFB)。其中GOSS针对的是训练数据量的优化（通过采样减少训练耗时），而EFB则是对训练特征量的优化（通过寻找互斥特征组来减少训练特征）。当然这两种方法都是会减少我们训练时用到的信息，而这可能会影响到最终的建模效果，因此在加速的同时也要考虑尽量不降低模型效果。
首先来看GOSS。我们知道，在GBDT中，每个样本的权重是一样的，作者受到AdaBoost的启发，在LightGBM中引入了样本“权重”，但其实本质上是对样本的一个采样，即保留那些“重要”的样本，而删去那些“不重要”的样本（相当于是0-1权重）。回顾一下XGBoost中选择特征切分点时的公式，我们发现那些梯度值较大的样本对于切分的影响很大，而那些梯度值较小的样本则影响较小。由于公式的分子是梯度的平方，因此这种影响会被进一步放大。于是作者使用梯度值作为依据对所有样本进行排序，选出topK，并同时按照一定比例采样未选中的其他样本。不过由于这种采样会改变数据分布，因此需要进行补偿。这里作者选择引入一个常数放大器，来放大计算信息增益时那些低梯度样本的影响。下图是GOSS的全流程：
EFB则是将所有互斥特征（这里并不需要完全互斥）进行一个合并。整个过程分为两步，首先通过一种贪心算法把互斥特征放入一个个筐，其次把筐里的特征进行合并。第一个贪心算法的设计和场景强相关，这里就不说了；第二个特征合并的方式需要尽量保留筐内所有特征的信息，作者利用了LightGBM计算特征直方图而不是精确值的特点，在不同的特征上叠加偏移量，从而使得不同特征的取值范围在不同的区间。例如原来特征A的取值范围是[0, 10]，特征B的取值范围是[0,20]，那么给特征B加上偏移量10，取值范围就变成了[10, 30]，也就和特征A区分开了。这时我们可以很放心的对这两个特征进行合并。
除此之外，在计算最优分裂点时LightGBM引入了特征分布直方图，用直方图来近似真实分布（感觉可以理解为进行了量化和信息压缩），在加快计算速度的同时也减少了存储量。
总结
至此我们便回顾了集成学习中非常重要的Boosting方法是如何一步步发展过来的。从最早显式地改变样本分布（AdaBoost），到之后引入加法模型，通过改变样本标签值来隐式地改变样本分布（提升树）；从一开始对损失函数有所限制（提升树）到后来的可以处理任意目标函数（GBDT，当然最好是凸函数）；从一开始仅仅利用一阶信息（GBDT）到后来利用二阶信息（XGBoost）；从一开始重点在算法效果优化，到后来重点放到工程优化和效率优化（XBGoost和LightGBM），Boosting算法在如今可以说是比较成熟了。在很多传统机器学习的场景中，XGBoost和LightGBM仍然有着举足轻重的地位。因此，个人认为搞清楚Boosting算法的脉络和原理还是很有用和必要的。
希望这篇文章能对阅读的你有所帮助。
