AdaBoost（Adaptive Boosting）

AdaBoost 作为一种经典的提升方法，可以从不同维度去分析理解它。

算法释义

AdaBoost 作为一种提升方法，通过改变训练数据的权值分布，为不同的弱分类器定义不同的权值，从而将一系列弱分类器线性最终组合成一个强分类器。

算法步骤

输入：训练集 T，弱学习算法 g(x)
输出：最终分类器 G(x)
(1) 初始化样本权值：
$D = (w_{1,1}, w_{1,2},..., w_{1,N}), w_i = \frac 1 N, i = 1,2,...,N$

(2) 迭代训练一系列弱分类器：t = 1, 2,..., T
a 训练弱分类器：根据样本权值，训练得到基本分类器 g_t
b 计算分类器误差：
$e_t = \sum_{i = 1}^N \frac {w_{t,i}} {\sum_{i=1}^N w_{t,i}} I(y_i≠g_t(x_i))$

c 计算 g_t 的系数：
$α_t = \ln \sqrt{\frac {1-e_t} {e_t}}$

d 重新计算样本权值：
$\begin{align} w_{t+1,i} = {w_{t,i}} e^{-α_ty_ig_t(x_i)} \\ \end{align}$

(3) 获得最终分类器 G(x)：
$G(x) = sign \left( \sum_{t=1}^T α_t g_t(x) \right)$

直观理解

AdaBoost 中比较关键的两步：1. 更新样本权值，2. 计算弱分类器系数；

通过更新样本权值训练下一个弱分类器，可以理解为增加本轮分类器分类错误的样本的权值，降低本轮分类器分类正确的样本的权值，我们知道每一轮训练的损失函数是和样本权值有关的，这样可以使下一轮弱分类器更加“重视”本轮误分类的样本。
从弱分类器权值的计算公式可以看出，错误率 e_t 越低，其权值越高，从而在最终分类器中占的比重越高，这也符合我们对线性组合分类器的直观理解。

从前向分布算法理解 AdaBoost

加法模型

$f(x) = \sum_{t=1}^T α_tg_t(x;γ_t)$

其中，g_t(x;γ_t) 为基函数，γ_t 为基函数的参数，α_t 为基函数的系数，这种由一系列基函数线性组合生成最终函数的模型称为加法模型。直接用损失函数最小化去解加法模型中的参数是一个复杂的问题，因此一般采用前向分步算法。

前向分步算法

前向分步算法的思想是：每一步学习一个基函数及其系数，使得最终函数逼近损失函数最小化的目标。

算法步骤

输入：训练数据集 T，损失函数 L(y, f(x))，基函数集 {g(x; γ)}
输出：加法模型 f(x)
(1) 初始化 f₀(x) = 0
(2) 迭代训练：t = 1,2,...,T
a. 最小化经验损失函数，得到基函数及其参数
$(α_t, γ_t) = arg\min_{α_t, γ_t} L(y, f_{t-1}(x) + α_tg_t(x;γ_t))$

b. 更新 f_t：
$f_{t}(x) = f_{t-1}(x) + α_tg_t(x;γ_t)$

(3) 得到加法模型：
$f(x) = f_T(x) = \sum_{t=1}^T α_tg_t(x;γ_t)$

理解 AdaBoost

从上面前向分步算法的算法步骤中不难看出其和 AdaBoost 算法很相似，其实 AdaBoost 就是前向分步算法的特例。更具体地，AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法。从加法模型和前向分步算法层面看，AdaBoost 的算法过程和它们如出一辙，但是如何理解 AdaBoost 算法的损失函数是指数函数呢？
假设 AdaBoost 是损失函数为指数函数的前向分步算法，当使用 AdaBoost 算法经过 t-1 轮迭代，学习算法已经学得 f_t-1，那么在第 t 轮迭代，需要计算的是使指数风险函数最小化的 g_t 和 α_t-1：
$\begin{align} & (α_t, g_t(x)) = arg\min_{α_t, g_t} \sum_{i=1}^N e^{-y_i(f_{t-1}(x_i) + α_tg_t(x_i))} \\ & 即：\\ & (α_t, g_t(x)) = arg\min_{α_t, g_t} \sum_{i=1}^N e^{-y_if_{t-1}(x_i)}e^{-y_iα_tg_t(x_i)}\\ & 又因为：e^{-y_if_{t-1}(x_i)} = w_{t,i} \\ & (α_t, g_t(x)) = arg\min_{α_t, g_t} \sum_{i=1}^N w_{t,i} e^{-y_iα_tg_t(x_i)}\\ & 将上述指数函数作一阶泰勒展开：\\ & (α_t, g_t(x)) = arg\min_{α_t, g_t} \sum_{i=1}^N w_{t,i} (1-y_iα_tg_t(x_i))\\ & 又因为 w_{t,i} 为常数项，对最小化没有影响：\\ & (α_t, g_t(x)) = arg\min_{α_t, g_t} \sum_{i=1}^N -w_{t,i} y_iα_tg_t(x_i)\\ & 先求解\, g_t：\\ & g_t(x) = arg\min_{g_t} \sum_{i=1}^N -w_{t,i} y_ig_t(x_i)\\ & 即：\\ & g_t(x) = arg\min_{g_t} \sum_{i=1}^N w_{t,i} I(y_i≠g_t(x_i))\\ & 而我们知道这就是 AdaBoost 每一轮迭代求解的基本分类器，然后求解α_t： \\ & α_t = arg\min_{α_t} \sum_{i=1}^N w_{t,i} e^{-y_iα_tg_t(x_i)} \\ & α_t = arg\min_{α_t} \left( \sum_{y_i=g_t(x)}w_{t,i} e^{-α_t} + \sum_{y_i≠g_t(x)}w_{t,i} e^{α_t} \right) \\ & 用 e_t 表示 g_t(x) 在训练样本上的错误分类率，则： \\ & α_t = arg\min_{α_t} \left( e_t(e^{α_t} - e^{-α_t}) + e^{-α_t} \right) \\ & 对α_t求导令其等于 0 可得：\\ & α_t = \ln{\frac {1-e_t} {e_t}} \\ & 这与 AdaBoost 算得的权值一模一样 \\ \end{align}$

综上所述，AdaBoost 算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的学习方法。

理论保障

有学者曾证明过 Adaboost 算法的泛化性能：
$E_{out} ≤ E_{in} + O (\sqrt{O(d_{vc}(H)·T \log T) · \frac {\log N} N })$

并且只要弱分类器的每轮的误分类率都小于 0.5，在 T = O(logN) 轮之后，E_in 就会等于0，那么上式右边的第二项也会很小，因此 E_out 也会很小。

参考资料

《机器学习技法》，林轩田
《统计学习方法》，李航