Boosting算法进化史

背景：

当前的热门算法中，除了神经网络在图像和文字、音频等领域大放异彩之外，集成学习中的xgboost,lightGBM,CatBoost也在kaggle等机器学习平台上成为了炙手可热的工具。

 

明确概念：

1、Boosting（提升）

2、Adaptive Boosting（自适应增强）

3、Gradient Boosting（梯度提升）

4、Decision Tree（决策树）

 

一、Boosting

关于boosting（提升算法）的概念，上文有简单介绍过，提升算法（这是一类算法族的称呼，不是指某种具体算法）是通过改变训练样本的权重（如果基分类器不支持则通过调整采样的方式改变基分类器的训练样本分布），学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。下面要讲的集成算法都属于提升算法

 

二、Adaboost（Adaptive Boosting自适应增强算法）

 针对分类任务，李航的《统计学习方法》中有详细介绍

 

 

 

总结一下流程如下图所示

 

 

 

 

 

经过上述学习，我们已经可以明确adaboost的核心是

1）计算基分类器的误差

2）计算基分类器的权重

3）更新样本的权重

4）最后的结合策略

针对回归任务，adaboost有以下步骤

 

 

 

 

 

 

三、GBDT（GBDT泛指所有梯度提升树算法，包括XGBoost，它也是GBDT的一种变种，为了区分它们，GBDT一般特指“Greedy Function Approximation：A Gradient Boosting Machine”里提出的算法，只用了一阶导数信息。）

参考自：https://zhuanlan.zhihu.com/p/46445201

GBDT是以CART树（回归树）作为基分类器的boosting算法。与Adaboost通过每次调整样本的权值来训练不同的基分类器不同，GBDT是通过将残差作为拟合目标训练心得基分类器。

先看一下GBDT应用于回归任务的原理

 

 

 

其实，我一直对GBDT中的“梯度提升”很不理解，因为最优化理论中，梯度下降优化算法已经很熟悉了，拿两者进行比较，我总是觉得GBDT依然是“梯度下降”而非“梯度提升”，如下图是某个博客上的对比

 

 ，这分明都是使用的“梯度下降”。

在参考了很多资料之后，我终于明白了GBDT为什么使用“梯度提升”的叫法了。这里的“梯度提升”并不是和“梯度下降”对立的概念，相反，应该把它拆解开来

 “梯度提升”=“梯度”+“提升”

“梯度”是指GBDT算法中使用梯度近似拟合残差的做法

“提升”是指boosting方法中将弱学习器提升为强学习器的做法

再附一个GBDT实际应用于回归任务的例子

 

 

 

GBDT应用于分类任务

 针对二分类任务，

 

 

 

 

 

 

 

 以上，最重要的一点就是，针对分类任务每个基分类器拟合的是真实标签与和对应类别预测概率的残差。

 

 

四、XGBoost（eXtreme Gradient Boosting）

从名字就可以看出，xgboost是GBDT的增强版本。

如果把xgboost对gbdt的所有改进细节列出来，那牵扯的point有点多，所以选择几个点进行阐述。

为了用最容易理解的思路，我们就假设不知道xgboost算法，先去思考GBDT的过程中有哪些点可以改进：

1、基学习器的选择。

GBDT使用CART（回归树）作为基学习器，我们还可以考虑支持其他的基学习器，所以xgboost也支持线性学习器

2、损失函数的选择。

GBDT大多数情况下采用平方误差和作为损失函数，我们还可以考虑更优秀的损失函数，所以xgboost实现了自己的损失函数。

3、特征分裂点及特征选择。

GBDT采用CART树的特征分裂点及特征选择方式，具体为串行遍历所有的特征分裂点和特征，选择平方误差和最小的特征及特征分裂点；

这个过程中，我们注意到各特征及分割点的损失函数的计算可以并行执行，而且如果对样本按照特征排序的结果在全局可以复用，可大大提高计算效率，而xgboost也是这样做的。

另外，GBDT的每棵树的特征选择策略都是相同的，方差较小，多样性不足，我们可以借鉴随机森林中列抽样（随机变量选择）的思想，xgboost也实现了这一点。

4、不同的树对于残差的拟合策略

GBDT采用残差的一阶导数代替残差进行拟合（这里需要说明，许多资料说用一阶导代替残差的原因是残差难以获得，这好扯淡啊，拟合一阶导的优点明明是为了更快地进行拟合，而且当损失函数为平方误差和时，一阶导就等于残差），发散一下我们就想到了梯度下降和牛顿法，那我们能不能使用二阶导来拟合残差呢，答案是肯定的，且xgboost也是这样做的，而且通过二阶导拟合策略计算出了xgboost的损失函数（见步骤2）。损失函数不仅考虑到了经验风险，也考虑到了结构风险，通过结构风险正则化，使得xgboost泛化性能更佳，更不容易过拟合。

 

五、LightGBM

该算法在精度，运行效率和内存消耗等方面在绝大多数数据集上的表现都优于xgboost。

我们沿用上面的思路，继续思考在xgboost的优化基础上，怎样进一步优化GB类的算法。

1、boosting过程中，最耗时的就是特征选择及连续特征分裂点选取的问题，xgboost已经通过pre-sorted预排序的方法进行了优化，但是如果样本对应的特征枚举值过多，还是会导致耗时过长的问题。所以我们可以考虑HistoGram（直方图）算法，通过预先对样本的特征进行分桶（bin）的方式，在选择分裂点的时候遍历各个桶，就可以有效地提高运行效率，虽然会稍微损失一点精度，但是可以通过其它的优化进行弥补。

2、结点的分裂策略。GBDT和xgboost在树的分裂过程中，都采用level-wise（类似层序遍历）的分裂方式，这种方式平等地对待了分裂贡献可能相差很大的同一层的不同子结点。lightGBM采用leaf-wise（类似深度优先遍历）分裂策略，每一步都选择最深的贡献最大的子结点进行分裂。

3、采样方法。无论是GBDT还是xgboost，我们都是在不停地训练基学习器去拟合残差，当残差小于某个阈值时停止训练，可能存在这样一种情况，对于大多数样本来讲，其梯度已经较小，而小部分样本的梯度仍较大，所以我们想到可以在每次训练新的基学习器时，保留梯度较大的样本，减少梯度较小的样本数量（随机采样），这便是GOSS方法(Gradient-based One-Side Sampling)。

 

ok,,,写得自己很不满意，先出第一版，后面迭代优化吧。。。还想补一下catboost。。。

• 还没有人评论，欢迎说说您的想法！