AdaBoost

1.算法流程

设训练数据集

(1)初始化时训练数据的权重

(2)对 ，使用具有权重分布的 进行训练，得到基本分类器

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

将 用 表示更好理解， 表示第 轮中第 个实例的权重， 。计算 的系数：

当 时， ，并且 随着 的减小而增大，因此分类误差越小的基本分类器在最终分类器中的作用越大，更新训练数据集的权重分布：

当 时 ，因此被分类正确的样本权重在减小，而误分类的样本权重在增大。 是规范因子：

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

得到最终分类器：

其中，

2.示例

给定训练样本：

初始化数据权值分布：

迭代过程1，

(a)在权值分布为 的训练数据上，阈值 取2.5时分类误差率最低，基本分类器为：

2. 在训练数据集上误差率 .

(c)计算 系数：

(d)更新训练数据的权值分布：

，分类器 在训练集上有3个误分类点。

迭代过程2， ,

(a)在权值分布为 的训练数据上，阈值 取8.5时分类误差率最低，基本分类器为：

2. 在训练数据集上误差率 .

(c)计算 .

(d)更新训练数据的权值分布：

，分类器 在训练集上有3个误分类点。

迭代过程3， ,

(a)在权值分布为 的训练数据上，阈值 取5.5时分类误差率最低，基本分类器为：

2. 在训练数据集上误差率 .

(c)计算 .

(d)更新训练数据的权值分布：

，分类器 在训练集上有0个误分类点。分类器最终为：

3.AdaBoost训练误差分析

AdaBoost误差上界为：

当 时， ,因此 ,前半部分得证。

后半部分，别忘了有：

推导如下：

因此我们可以在每一轮选取适当的 使得 最小，从而使训练误差下降的最快。对于二分类问题，有如下结果：

其中 .

证明：

当 时 ,当 时 , , .

至于不等式：

可由 和 在 处的泰勒展开推出 ,进而得到。

另外，如果存在 ,对所有 有 ,则：

这个结论表明，AdaBoost的训练误差是以指数速率下降的。另外，AdaBoost算法不需要事先知道下界 ，AdaBoost具有自适应性，它能适应弱分类器各自的训练误差率。

4.AdaBoost算法另一种解释

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

4.1.前向分步算法

加法模型(additive model)如下：

其中 为基函数， 为基函数参数， 为基函数系数。

在给定训练数据和损失函数 的条件下，学习加法模型 成为经验风险极小化即损失函数极小化问题：

该问题可以作如此简化：从前向后，每步只学习一个基函数及其系数，逐步逼近上式，即每步只优化如下损失函数：

这就是向前分步算法。

向前分步算法流程

输入：训练数据集;损失函数 ;基函数集。

输出：加法模型

(1)初始化

(2)对

(a)极小化损失函数

得到参数

(2)更新

(3)得到加法模型

前向分步算法将同时求解从 到 所有参数 的优化问题简化为逐次求解各个 的优化问题。

4.2.前向分步算法与AdaBoost

AdaBoost算法是前向分步加法算法的特例。其模型是由基本分类器组成的加法模型，其损失函数是指数函数。

AdaBoost的基本分类器为 ,其系数为 , ,AdaBoost的最终模型即最终的加法模型为：

前向分步算法逐一学习基函数的过程，与Adaboost算法逐一学习各个基本分类器的过程一致。

下面证明前向分步算法的损失函数是指数损失函数 时，其学习的具体操作等价于AdaBoost算法学习的具体操作。

假设经过 轮迭代前向分步算法已经得到

在第 轮迭代得到 和 :

目标是使前向分步算法得到的 和 使 在训练数据集 上的指数损失最小，即

假定 和 为已知参数，现在求解 ,并令与 都无关，所以与最小化无关，只依赖于与 ,并随着每一轮迭代而发生改变，于是上式可以表示为

接下来,便是要证使得上式达到最小的和就是Adaboost算法所求解得到的 和 .

接下来先求再求,对任意 ,使上式 最小的 由下式得到：

其中. 算法中的误差率 为：

即为AdaBoost算法中所求的 ,它是在第 轮加权训练数据时，使分类误差率最小的基本分类器;在Adaboost算法的每一轮迭代中，都是选取让误差率最低的阈值来设计基本分类器。

之后求 ，式 后半部分为：

将 代入，并对 求导，使导数等于0：

即，

可得：

这里的 与 算法的 完全一致。

最后看每一轮样本的权值更新，由 以及可得：

可得，，这与 算法中

只差规范因子 ：

因而二者等价。

参考

1. 李航 《统计学习方法》
2. 周志华 《机器学习》
3. 集成学习之Adaboost算法原理小结
4. Adaboost 算法的原理与推导
5. 第06章：深入浅出ML之Boosting家族
6. 提升树GBDT详解
7. 梯度提升树(GBDT)原理小结
8. 『机器学习笔记 』GBDT原理-Gradient Boosting Decision Tree
9. 机器学习算法系列（7）：GBDT
10. xgboost 算法原理
11. xgboost中的数学原理
12. 树模型(六)：XGBoost
13. Xgboost论文