AdaBoost

1.算法流程

设训练数据集 T = {(x₁, y₁), (x₂, y₂), ⋯, (x_N, y_N)}, x_i ∈ 𝒳 ⊆ Rⁿ, x_i ∈ 𝒴 = {−1, +1}

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

(2)对 m = 1, 2, ⋯, M ，使用具有权重分布的 D_m 进行训练，得到基本分类器

G_m(x) : 𝒳 → {−1, +1}

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

将 用 表示更好理解，w_mi 表示第 m 轮中第 i 个实例的权重， 。计算 G_m(x) 的系数：

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

D_m + 1 = (w_{m + 1, 1}, ⋯, w_{m + 1, i}, ⋯, w_{m + 1, N})

当 y_i = G_m(x_i) 时 y_iG_m(x_i) = 1 ，因此被分类正确的样本权重在减小，而误分类的样本权重在增大。 Z_m 是规范因子：

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

得到最终分类器：

其中，

2.示例

给定训练样本：

初始化数据权值分布：

D₁ = (w₁₁, w₁₂, ⋯, w₁₁₀), w_1i = 0.1, i = 1, 2, ⋯, 10

迭代过程1， m = 1

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

2. G₁(x) 在训练数据集上误差率 e₁ = P(G₁(x_i) ≠ y_i) = 0.3 .

(c)计算 G₁(x) 系数：

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

D₂ = (0.07143, 0.07143, 0.07143, 0.07143, 0.07143, 0.07143, 0.16667, 0.16667, 0.16667, 0.07143)

f₁(x) = 0.4236G₁(x) ，分类器 sign(f₁(x)) 在训练集上有3个误分类点。

迭代过程2， m = 2 ,

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

2. G₂(x) 在训练数据集上误差率 e₂ = 0.2143 .

(c)计算 α₂ = 0.6496 .

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

D₃ = (0.0455, 0.0455, 0.0455, 0.16667, 0.16667, 0.16667, 0.1060, 0.1060, 0.1060, 0.0455)

f₂(x) = 0.4236G₁(x) + 0.6496G₂(x) ，分类器 sign(f₂(x)) 在训练集上有3个误分类点。

迭代过程3， m = 3 ,

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

2. G₃(x) 在训练数据集上误差率 e₃ = 0.1820 .

(c)计算 α₃ = 0.7514 .

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

D₄ = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)

f₃(x) = 0.4236G₁(x) + 0.6496G₂(x) + 0.7514G₃(x) ，分类器 sign(f₃(x)) 在训练集上有0个误分类点。分类器最终为：

G(x) = sign[f₃(x)] = sign[0.4236G₁(x) + 0.6496G₂(x) + 0.7514G₃(x)]

3.AdaBoost训练误差分析

AdaBoost误差上界为：

当 G(x_i) ≠ y_i 时，y_if(x_i) < 0 ,因此 exp (−y_if(x_i)) ≥ 1 ,前半部分得证。

后半部分，别忘了有：

推导如下：

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

其中 .

证明：

当 y_i = G_m(x_i) 时 y_iG_m(x_i) = 1 ,当 y_i ≠ G_m(x_i) 时 y_iG_m(x_i) = −1 , , .

至于不等式：

可由 e^x 和 在 x = 0 处的泰勒展开推出 ,进而得到。

另外，如果存在 γ > 0 ,对所有 m 有 γ_m ≥ γ ,则：

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

4.AdaBoost算法另一种解释

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

4.1.前向分步算法

加法模型(additive model)如下：

其中 b(x; γ_m) 为基函数， γ_m 为基函数参数， β_m 为基函数系数。

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

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

这就是向前分步算法。

向前分步算法流程

输入：训练数据集T = {(x₁, y₁), (x₂, y₎, ⋯, (x_N, y_N)};损失函数 L(y, f(x)) ;基函数集{b(x; γ)}。

输出：加法模型 f(x)

(1)初始化 f₀(x) = 0

(2)对 m = 1, 2, ⋯, M

(a)极小化损失函数

得到参数 β_m, γ_m

(2)更新

f_m(x) = f_m − 1(x) + β_mb(x; γ_m)

(3)得到加法模型

前向分步算法将同时求解从 m = 1 到 M 所有参数 β_m, γ_m 的优化问题简化为逐次求解各个 β_m, γ_m 的优化问题。

4.2.前向分步算法与AdaBoost

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

AdaBoost的基本分类器为 G_m(x) ,其系数为 α_m , m = 1, 2, ⋯, M ,AdaBoost的最终模型即最终的加法模型为：

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

下面证明前向分步算法的损失函数是指数损失函数 L(y, f(x)) = exp [−yf(x)] 时，其学习的具体操作等价于AdaBoost算法学习的具体操作。

假设经过 m − 1 轮迭代前向分步算法已经得到 f_m − 1(x):

f_m − 1(x) = f_m − 2(x) + α_m − 1G_m − 1(x) = α₁G₁(x) + ⋯ + α_m − 1G_m − 1(x)

在第 m 轮迭代得到 α_m, G_m(x) 和 f_m(x) :

f_m(x) = f_m − 1(x) + α_mG_m(x)

目标是使前向分步算法得到的 α_m 和 G_m(x) 使 f_m(x) 在训练数据集 T 上的指数损失最小，即

假定 G₁(x), ⋯, G_m − 1(x) 和 α₁, ⋯, α_m − 1(x) 为已知参数，现在求解 G_m(x), α_m ,并令与 α, G 都无关，所以与最小化无关，只依赖于与 f_m − 1(x) ,并随着每一轮迭代而发生改变，于是上式可以表示为

接下来,便是要证使得上式达到最小的α_m^*和G_m^*(x)就是Adaboost算法所求解得到的 α_m 和 G_m(x) .

接下来先求G_m^*(x)再求α_m^*,对任意 α > 0 ,使上式 (α_m, G_m(x)) 最小的 G(x) 由下式得到：

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

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

之后求 α_m^* ，式 (α_m, G_m(x)) 后半部分为：

将 G_m^* 代入，并对 α 求导，使导数等于0：

即，

可得：

这里的 α_m^* 与 AdaBoost 算法的 α_m 完全一致。

最后看每一轮样本的权值更新，由 f_m(x) = f_m − 1(x) + α_mG_m(x) 以及可得：

可得，，这与 AdaBoost 算法中 w_{m + 1, i}

只差规范因子 Z_m ：

因而二者等价。

参考

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论文