提升方法学习(AdaBoost、GBDT与XGBoost)

提升(boosting)方法是一种常用的统计学习方法，应用广泛且有效。

一、提升方法的基本思路

二、AdaBoost算法

1.Adaboost算法分析

2.AdaBoost算法的另一种解释：

3.加法模型(additive model)                                     

4.前向分布算法(forward stagewise algorithm)

三、提升树算法

1.提升树模型

2.提升树算法步骤

3.回归树的表示

4.回归问题提升树算法模型

5.回归提升树算法描述

四、梯度提升算法(GBDT)

1.梯度提升算法描述

五、XGBoost算法

1.xgboost的优化思路

2.XGBoost算法的学习过程

3.XGBoost构建步骤流程

六、总结

Boosting算法族

AdaBoost

回归提升树和AdaBoost

GBDT与回归提升树

七、参考文献

一、提升方法的基本思路

思路：提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合得出的判断要比其中任何一个专家单独的判断都好。也就是"三个臭皮匠，顶个诸葛亮"。

理论支持：在PAC(probably approximately correct)框架中，一个概念(类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式学习算法能够学习它，学习的正确率仅比随机猜测好一点，那么就成这个概念是弱可学习的。

后来Schapire证明强可学习与弱可学习是等价的。也就是说，在PAC框架下，一个概念是强可学习的充要条件是这个概念是弱可学习。

综上我们可以通过集成一系列弱学习器来得到一个强学习器。

而发现一个弱学习算法比发现一个强学习算法容易的多。因此我们找到了一条曲线救国的路线：低成本得到多个弱学习算法，再通过组合这些弱学习算法将其提升成一个强学习算法。而具体如何进行提升就是我们需要解决的问题。

对于分类问题而言，给定一个训练样本集合，发现粗糙分类规则(弱分类器)比发现精确分类规则(强分类器)要容易的多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合这些分类器，构成一个强分类器。大多数提升方法都是改变训练数据的概率分布(训练数据的权值分布)，针对不同的训练数据分布调用若学习算法学习一系列弱分类器。

这样提升方法需要解决两个问题：

1. 如何获得多个不同的弱分类器

2. 如何将多个弱分类器组合成一个强分类器

二、AdaBoost算法

AdaBoost(Adaptive Boosting--自适应增强)算法，是Boosting算法的一种实现。是一种二分类器，它使用若分类起的线性组合构造强分类器。

因此针对Bosting算法的两个问题，AdaBoost算法的做法是：

1. 通过提高前一轮弱分类器错误分类样本的权值，降低正确分类的样本权值，从而得到不同的弱分类器

2. 采取加权多数表决的方式组合弱分类器。

     具体的：加大分类误差率小的弱分类器的权值，降低分类错误率高的弱分类器 的权值。

AdaBoot就是依照上面两种规则对Boosting算法的一种具体实现。

• AdaBoost算法是多个弱分类器的线性组合：

表示弱分类器的个数

表示第m个分类器    

为第m个弱分类器的表决权值(反应分类器的重要性)

1.Adaboost算法分析

输入： 

输出：分类器 

1.初始化训练数据的权值分布

2. 

      a.使用具有权值分布

的训练数据集学习，得到基本分类器

      b.计算

在训练数据集上的分类误差率

     c.计算

的系数

               这里的对数是自然对数

     d.更新训练数据集的权值分布

是规范化因子，它使

成为一个概率分布

3.构建基本分类器的线性组合

      得到最终分类器：

    以上是AdaBoost算法基本的分析，更详细的讨论本文不再讨论。更详细的分析和解释大家可以参考李航老师 统计学习方法 第二版 P156~P162。

与GBDT、lambdaMART放在一起，本文更想讨论的是AdaBoost算法的另一种解释。

2.AdaBoost算法的另一种解释：

   可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法的二类分类学习方法。

3.加法模型(additive model)

   其中，

为基函数，

为基函数的参数，

为基函数的系数。显然上式是一个多个基模型进行线性累加的模型。在给定训练数据及损失函数

条件下，学习加法模型

成为经验风险极小化，即损失函数极小化问题：

   上式是一个复杂的优化问题。因此我们借助前向分步算法来求解这样的问题。

4.前向分布算法(forward stagewise algorithm)

前向分步算法的思想是因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，这样可以简化优化的复杂度。具体来说，每步只需优化如下损失函数：   

在给定训练数据集，损失函数和基函数集合的情况下，前向分步算法学习加法模型的算法如下：

输入：

；损失函数

；基函数集

输出：加法模型

1.初始化

2. 对

    a.极小化损失函数

                   得到

    b.更新模型

3.得到加法模型

    用这种方式前向分布算法将同时求解从

到

所有参数的

的优化问题简化为逐次求解各个

的优化问题。因此，当我们把AdaBoost中每一个弱学习器看成加法模型中的一个学习器时，AdaBoost可以看成一个特殊的加法模型，可以通过前向分步算法来学习该加法模型。

    关于AdaBoost的具体证明本文不再赘述，感兴趣可以参考统计学习方法 第二版 P156~P162。

三、提升树算法

1.提升树模型

提升树是以决策树作为基本分类器的提升方法。对于分类问题采用二叉分类树，对回归问题采用二叉回归树。

提升树模型可以表示为决策树的加法模型：

             其中

表示决策树，

为树的参数

2.提升树算法步骤

提升树算法采用前向分步算法。初始化提升树

，第

步的模型如下：

为当前模型

通过经验风险极小化确定下一棵决策树的参数

:

    对于分类问题和回归问题两个问题，提升树算法的主要区别是损失函数不同。对于分类问题，使用指数函数作为损失函数，而对于回归问题，使用平方误差。对于分类问题，提升树算法只需要将上面讨论的AdaBoost算法中的基本分类器限制为二类分类树。此时的提升树算法是一个特殊的AdaBoost算法。这里不再详细讨论，下面主要讨论回归问题的提升树算法。

3.回归树的表示

回归树的数学表达式如下：

为树的叶子结点数

           其中

表示在回归树上，输入

被映射到叶节点

的影射关系，

为叶节点

的输出值。

4.回归问题提升树算法模型

1. 初始化： 

2. 对

3.得到提升树

在第

步，给定当前模型的情况下，求解

                  使用平方损失函数

此时，

为当前模型的预测结果，

为真实结果，令

，即

为当前模型预测结果与真实结果的差值，我们称之为残差。即每一步只需求解：

5.回归提升树算法描述

输入：

输出：回归提升树

1. 初始化 

2. 对

    a. 计算残差 

    b. 拟合上一部残差，得到一个回归树

    c. 更新提升树模型：

3. 得到回归提升树：

四、梯度提升算法(GBDT)

    提升树利用加法模型和前向分布算法实现学习的优化过程。当损失函数是平方损失和指数算是时，每一步的优化是很简单的。但对于一般损失函数而言，每一步的优化往往没有那么容易。针对这一问题，Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值。

作为回归问题提升树算法中的残差的近似值，以此来拟合一个回归树。

1.梯度提升算法描述

输入：

； 

 损失函数为一般损失函数

输出：回归提升树

1. 初始化

2. 对

    a. 对

    b. 对

 拟合一个回归树，得到第

棵树的叶节点区域

 (得到树的结构)

    c.对

 计算

      (得到各叶节点的值)

    d. 更新

3. 得到提升树

GBDT与提升树之间的区别：

在上述算法的第2(a)步使用损失函数的负梯度在当前模型的值，将它作为残差的估计值。在回归提升树中，将损失函数限定为平方损失，此时它就是通常所说的残差，而对于一般的损失函数，它就是残差的近似值。

GBDT算法的缺点：

传统GBDT的目标函数只有损失函数一项，容易引起过拟合。

GBDT的实现是比较慢的。因为每次都要先构造出一棵树，并添加到整个模型序列中，因此引出了xgboost算法。

五、XGBoost算法

XGBoost是一种特殊提升算法，准确的说它是一种梯度提升决策树。(xgboost其实就是GBDT的加速实现)。

XGBoost在目标函数中增加正则项来防止模型过拟合。

1.xgboost的优化思路

    采用Boosting思想，从一个常量(通常为0)进行预测，每次添加一个新的拟合残差的函数。

1. 初始化

2. 对

3. 得到提升模型

需要优化的是第二步，需要寻找一种方法来确定第

轮的函数

。

2.XGBoost算法的学习过程

第

轮迭代预测结果：

目标函数为：

优化目标函数

先考虑损失函数为平方损失的情况：

在第

轮，

已经是一个已知量，因此

 是一个常量。所以目标函数为：

此时目标函数转换成一个关于

的二次函数，此时是很容易求出最优解的。

但是XGBoost并没有限制损失函数必须是平方损失函数，为了算法的通用型和可扩展性，损失函数使用一般损失函数。此时目标函数还是相当复杂的；

神来之笔泰勒公式

泰勒展开式的二阶形式：

           其中，

表示

的高阶无穷小，因此有：

观察我们的目标函数，如果把

看成是

为自变量的函数，把

看做是自变量的增量

,那么就可以把目标函数按

进行泰勒展开，目标函数转化为：

               其中

表示目标函数关于

的一阶导；

表示目标函数关于

的二阶导。

至此，我们得到新的目标函数：

去除常数部分(注意在第

轮时，

是常数)：

至此我们得到一个可以优化的目标函数。

正则项的处理

    目标函数正则化项存在的原因是为了限制模型的复杂度，让模型在训练集上能够取得较好的结果的前提下尽可能的简单。在XGBoost中，在每一步迭代中模型的复杂度就是当前要学习的决策树的复杂度。

在这里我们重新定一下决策树：

    一个决策树，假设其叶子结点数为

，该决策树是由所有叶子结点对应的值组成的向量

,以及一个把样本特征向量映射到叶子节点的索引函数

组成的，因此决策树可以定义为：

。

决策树的复杂度可以定义为：

即决策树的模型的复杂度由生成树叶子结点数和叶子节点对应值的向量的

范数决定。

把决策树复杂度带入到目标函数中：

求目标函数关于

的导数：

令导数为0，有：

因此我们可以得到所有叶节点的值。此时目标函数的值为：

至此，关于第t轮的一个已经分裂好的决策树，我们能够求出其对应的最小化的目标函数。但是如何进行节点分裂得到一棵树？

穷举法：穷举所有可能的树结构，选择使目标函数最小的那颗，但是可能的树结构有无穷多种，在有限的时间内无法找到最 优的那颗决策树。

XGBoost做法：使用贪心策略一步步增长树的结构。即从根节点开始，每个节点不断进行递归分类，直到达到限制条件。

寻找最优分裂点

     根据上面的公式我们知道，一个节点分裂对最优目标函数的影响是不分裂的最优目标函数值减去分裂出的两个子树的最优目标函数值之和，即：

对于任一节点，只有当

为正时，才表示此次分裂有收益。

最优分裂点寻找方法：

1.对每一个待分裂点，枚举出所有特征

2.对于每一个特征。根据该特征g所有的进行排序

3.遍历该特征的每可能值作为分裂点时对应的gain，将获取最大gain的特征及对应的取值作为分裂点进行分裂。

剪枝策略

前剪枝：当前最优分裂点的收益为负，停止分裂。

后剪枝：先将决策树增长到他的最大深度，在递归的进行剪枝。

前剪枝存在的问题是可能存在收益更大的后续分裂。因此一般我们采用后剪枝，建树完成后再减掉那些收益为负的叶子结点。

防止单步过拟合

在AdaBoost中，每个基模型的预测结果都会乘以一个自身的权值，这个权值反应基模型在整个模型中的重要性。在XGBoost中，每个基模型也都会乘以一个权值

，只不过

是固定，它不反应基模型的重要度，而是为了防止单步过拟合，称为学习率。

3.XGBoost构建步骤流程

输入：

； 

输出：梯度提升树 

1. 初始化

2. 对

    a. 对

        计算  

    b. 使用贪心策略构建决策树

，以使得下列目标函数最小化

    c. 更新：

3. 得到XGBoost提升树

六、总结

Boosting算法族

提升(Boosting)是集成学习方法里的一个重要方法，其主要思想是将弱分类器组装成一个强分类器。在PCA(概率近似正确)学习框架下，一定可以将弱分类器组合成强分类器。

AdaBoost、GBDT、XGBoost都属于(加法模型、前向分步、指数损失函数)家族，都实现了将多个弱分类器组合成一个强分类器的过程。

AdaBoost

AdaBoost是一种典型的分类回归树，适合解决二分类问题。

AdaBoost是一种采用加法模型、前向分步算法、损失函数为指数损失函数的提升树，可以认为AdaBoost是Boosting前向分步算法的一个特例。

回归提升树和AdaBoost

回归提升树与AdaBoost不同之处在于它使用平方损失函数来解决回归问题，通过计算残差发现当前模型的问题，并不断拟合残差来构建新的弱分类器(树)。

GBDT与回归提升树

a.梯度提升树看做一种特殊的回归提升树。它通过计算损失函数的负梯度在当前模型的值， 近似替代回归提升树中的残 差，并通过拟合该"残差"构建新的弱分类器。

b.回归提升树初始化

；GBDT初始化时，令基学习器等于使损失函数最小化的常数。

c.回归提升树限制损失函数为平方损失，并以此计算残差；GBDT不限制损失函数，通过损失函数负梯度来计算法残差。

XGBoost与GBDT

1.XGBoost其实是GBDT的高效实现，xgboost中的基学习器出了可以是CART(决策树), 还可以是线性分类器。

2.xgboost在目标函数中显示的加入了正则化项，用于控制模型的复杂度。

3.GBDT使用损失函数的一阶导来计算伪残差，xgboost使用了损失函数的一阶导与二阶导

4.CART回归树中寻找最佳分割点的衡量标准是最小化均方差；xgboost中寻找最优分割点的标准是目标函数最小化

5.列抽样(column subsampling)。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。

七、参考文献

1.李航统计学习方法 第二版

2.提升树算法总结 http://ihoge.cn/2018/boosting.html

3.GBDT与XGBoost详解 https://fengxc.me/GBDT%E8%AF%A6%E8%A7%A3.html

4.机器学习算法系列（36）：GBDT算法原理深入解析

    本文主要是自己学习笔记的整理，在学习参考文献中内容的基础上加了自己一些理解，不能算自己的原创。感兴趣的同学可以同时把参考文献中的内容一起阅读，以加深理解。