AdaBoost算法的详细数学推导过程！！

AdaBoost（Adaptive Boosting）

?

? 提升（boosting）方法是一种常用的统计学习方法，应用广泛且有效。在分类问题 中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

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

? 这样，对提升方法来说，有两个问题需要回答:一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问 题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的 加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器"分而泊之"。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。 具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用:减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

? AdaBoost 算法还有另一个解释， 即可以认为 AdaBoost 算法是模型为**加法模型、 损失函数为指数函数、 学习算法为前向分步算法时的二类分类学习方法。**

-------------------------------------------------------------------------------------------------------------------------------------

输入：线性可分训练数据集$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$

? 其中， x i ∈ X = R n , y i ∈ Y = { ? 1 , + 1 } , i = 1 , 2 , … , N x_i∈X=R^n,y_i∈Y=\{-1,+1\}, i = 1,2,…,N xi?∈X=Rn,yi?∈Y={?1,+1},i=1,2,…,N；弱学习算法

输出： 最终分类器$G(x)$、$f(x)=sign(G(x))$

优化问题：（损失函数为指数损失函数，即：$L(y,f(x))=exp[?yf(x)]$）

目标是使前向分步算法得到的${\alpha }_m$ 和$G_m(x)$ 使$f_m(x)$ 在训练数据集T 上的指数损失最小:
$$\begin{gathered} ({\alpha }_m,G_m(x))=arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_m(x_i))] \\ =arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_{m?1}(x_i)+\alpha G(x_i))] \end{gathered}$$
上面损失函数又可以写为：
$$\begin{gathered} ({\alpha }_m,G_m(x))=arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_{m?1}(x_i)+\alpha G(x_i))] \\ =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N{\hat{w}}_{mi}exp[?y_i\alpha G(x_i)] \end{gathered}$$
这里
$${\hat{w}}_{mi}=exp[?y_i{f}_{m?1}(x)]$$

-------------------------------------------------------------------------------------------------------------------------------------

前向分布算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$
第m-1轮迭代：
$$\begin{gathered} f_{m?1}(x)=f_{m?2}(x)+{\alpha }_{m?1}{G}_{m?1}(x) \\ ={\alpha }_1{G}_1(x)+{\alpha }_2{G}_2(x)+...+{\alpha }_{m?1}{G}_{m?1}(x) \end{gathered}$$
第m轮迭代：
$$\begin{gathered} f_m(x)=f_{m?1}(x)+{\alpha }_m{G}_m(x) \\ ={\alpha }_1{G}_1(x)+{\alpha }_2{G}_2(x)+...+{\alpha }_m{G}_m(x) \end{gathered}$$
-------------------------------------------------------------------------------------------------------------------------------------

AdaBoost算法流程

输入：训练数据集$T=\{(x_1,y_1)、(x_2,y_2),...,(x_N,y_N)\}$其中 x i ∈ X ? R n , y i ∈ Y = { ? 1 , + 1 } x_i∈X\subset R^n, y_i∈ Y = \{-1, +1 \} xi?∈X?Rn,yi?∈Y={?1,+1}；弱学习算法；

输出：最终分类器G(x)。

（1）初始化训练数据的权值分布
$$D_1=(w_{11},w_{12},...,w_{1i},...,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,...,N$$
（2）对$m=1,2,...,M$

? （a）使用具有权值分布$D_m$的训练数据集学习，得到基本分类器
G m ( x ) : X → { ? 1 , ? + 1 } G_m(x):X→\{-1,\ +1\} Gm?(x):X→{?1,?+1}
? （b）计算$G(x)$在训练数据集上的分类误差率
$$e_m=\sum _{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum _{i=1}^N{w}_{mi}I(G_m(x_i)\ne y_i)$$
? （c）计算$G_m(x)$的系数
$${\alpha }_m=\frac{1}{2}log\frac{1?e_m}{e_m}$$
? （d）更新训练数据集的权值分布
$$\begin{gathered} D_{m+1}=(w_{m+1,1},w_{m+1,2},...,w_{m+1,i},...,w_{m+1,N}) \\ {w}_{m+1,i}=\frac{w_{mi}}{Z_m}exp(?{\alpha }_m{y}_i{G}_m(x_i)),i=1,2,...,N \\ {Z}_m=\sum _{i=1}^{N}exp(?{\alpha }_m{y}_i{G}_m(x_i))是规范化因子,它使得D_{m+1}成为一个概率分布 \end{gathered}$$
（3）构建基本分类器的线性组合
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$
得到最终的分类器：
$$G(x)=sign(f(x))=sign(\sum _{m=1}^M{\alpha }_m{G}_m(x))$$

前向分布算法

?

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

加法模型：
$$f(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$
其中，$b(x;{\gamma }_m)$为基函数，${\gamma }_m$ 为基函数的参数，${\beta }_m$为基函数的系数。

? 学习该加法模型成为损失函数极小化问题：
$$\underset{{\beta }_m,{\gamma }_m}{\min }\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$$
? 前向分步算法(forward stagewise algorithm)求解这一优化问题的想法是:因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复 杂度。

? 每一步都只需要优化如下损失函数：
$$\underset{\beta ,\gamma }{\min }\sum _{i=1}^{N}L(y_i,\beta b(x_i;\gamma ))$$

前向分布算法的算法流程

输入：训练数据集$T=\{(x_1,y_1)、(x_2,y_2),...,(x_N,y_N)\}$损失函数$L(y,f(x))$；函数集 { b ( x ; γ ) } \{b(x;γ)\} {b(x;γ)}；

输出：加法模型$f(x)$。

（1）初始化$f_0(x)=0$

（2）对$m=1,2,...,M$

? （a）极小化损失函数
$$({\beta }_m,{\gamma }_m)=arg\underset{\beta ,\gamma }{\min }\sum _{i=1}^{N}L(y_i,f_{m?1}(x_i)+\beta b(x_i;\gamma ))$$
得到参数${\beta }_m$，${\gamma }_m$

? （b）更新
$$f_m(x)=f_{m?1}+{\beta }_{m}b(x;{\gamma }_m)$$
（3）得到加法模型
$$f(x)=f_M(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$
这样，前向分布算法将同时求解从m=1到M的所有参数${\beta }_m,{\gamma }_m$ 的优化问题简化为逐次求解各个${\beta }_m,{\gamma }_m$的优化问题

前向分布算法与AdaBoost

前向分布算法当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$
当前向分布算法的损失函数是指数损失函数时，其学习的具体操作等价于AdaBoost算法学习的具体操作。
$$L(y,f(x))=exp[?yf(x)]$$

假设经过m-1轮迭代前向分布算法已经得到$f_{m?1}(x)$：
$$\begin{gathered} f_{m?1}(x)=f_{m?2}(x)+{\alpha }_{m?1}{G}_{m?1}(x) \\ ={\alpha }_1{G}_1(x)+{\alpha }_2{G}_2(x)+...+{\alpha }_{m?1}{G}_{m?1}(x) \end{gathered}$$
第m轮迭代得到${\alpha }_m,G_m(x),f_m(x)$：
$$\begin{gathered} f_m(x)=f_{m?1}(x)+{\alpha }_m{G}_m(x) \\ ={\alpha }_1{G}_1(x)+{\alpha }_2{G}_2(x)+...+{\alpha }_m{G}_m(x) \end{gathered}$$
目标是使前向分步算法得到的${\alpha }_m$ 和$G_m(x)$ 使$f_m(x)$ 在训练数据集T 上的指数损失最小:
$$\begin{gathered} ({\alpha }_m,G_m(x))=arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_m(x_i))] \\ =arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_{m?1}(x_i)+\alpha G(x_i))] \end{gathered}$$
上面损失函数又可以写为：
$$\begin{gathered} ({\alpha }_m,G_m(x))=arg\underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[?y_i(f_{m?1}(x_i)+\alpha G(x_i))] \\ =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N{\hat{w}}_{mi}exp[?y_i\alpha G(x_i)] \end{gathered}$$
这里
$${\hat{w}}_{mi}=exp[?y_i{f}_{m?1}(x)]$$

因为${\hat{w}}_{mi}$既不依赖$\alpha$也不依赖G，所以与最小化无关。但是${\hat{w}}_{mi}$依赖于$f_{m?1}(x)$，随着每一轮的迭代而发生改变。

求解
$$({\alpha }_m,G_m(x))=arg\underset{\alpha ,G}{\min }\sum _{i=1}^N{\hat{w}}_{mi}exp[?y_i\alpha G(x_i)]$$
分为两步：第一步，首先求$G_m^{?}(x)$；第二步，求${\alpha }_m^{?}$。

①：对于任意的$\alpha ＞0$，使得上式最小的$G(x)$由下式得到：
$$G_m^{?}(x)=arg\underset{G}{\min }\sum _{i=1}^N{\hat{w}}_{mi}I(?y_i\ne G(x_i))$$
推导如下：
$$\begin{gathered} \sum _{i=1}^N{\hat{w}}_{mi}{e}^{?y_i\alpha G(x_i)}=\sum _{y_i=G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{\alpha } \\ =\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{\alpha }?\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i=G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha } \\ =\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))(e^{\alpha }?e^{?\alpha })+\sum _{i=1}^N{\hat{w}}_{mi}{e}^{?\alpha } \end{gathered}$$
所以：
$$G_m^{?}(x)=arg\underset{G}{\min }\sum _{i=1}^N{\hat{w}}_{mi}I(?y_i\ne G(x_i))$$
②：求解${\alpha }_m^{?}$
$$\begin{gathered} \sum _{i=1}^N{\hat{w}}_{mi}{e}^{?y_i\alpha G(x_i)}=\sum _{y_i=G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{\alpha } \\ =\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{\alpha }?\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i\ne G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i=G(x_i)}{\hat{w}}_{mi}{e}^{?\alpha } \\ =\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))(e^{\alpha }?e^{?\alpha })+\sum _{i=1}^N{\hat{w}}_{mi}{e}^{?\alpha } \end{gathered}$$
将已求得的$G_m^{?}(x)$代入，对$\alpha$求导并令导数为0：
$$\begin{gathered} \frac{{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))(e^{\alpha }?e^{?\alpha })+{\sum }_{i=1}^N{\hat{w}}_{mi}{e}^{?\alpha }}{?\alpha } \\ =\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))e^{\alpha }+\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))e^{?\alpha }?\sum _{i=1}^N{\hat{w}}_{mi}{e}^{?\alpha } \\ =(\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))?\sum _{i=1}^N{\hat{w}}_{mi})e^{?\alpha }+\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))e^{\alpha } \\ =\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))e^{2\alpha }+\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))?\sum _{i=1}^N{\hat{w}}_{mi}(令)=0 \\ \to e^{2\alpha }=\frac{{\sum }_{i=1}^N{\hat{w}}_{mi}?{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))} \\ \to \alpha =\frac{1}{2}ln\frac{{\sum }_{i=1}^N{\hat{w}}_{mi}?{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))} \\ \to \alpha =\frac{1}{2}ln\frac{1?e_m}{e_m} \\ {e}_m=\frac{{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))}{{\sum }_{i=1}^N{\hat{w}}_{mi}}=\sum _{i=1}^N{w}_{mi}I(y_i\ne G(x_i)) \\ =\sum _{G_m(X_i)\ne y_i}{w}_{mi}(注:w_{mi}表示第m轮中第i个实例的权值,\sum _{i=1}^N{w}_{mi}=1) \end{gathered}$$
每一轮的权值更新，由：
$$f_m(x)=f_{m?1}(x)+{\alpha }_m{G}_m(x)$$
以及${\hat{w}}_{mi}=e^{?y_i{f}_{m?i(x_i)}}$可得：
$${\hat{w}}_{m+1,i}={\hat{w}}_{mi}{e}^{?y_i{\alpha }_m{G}_m(x)}$$
至此推导完毕！