AdaBoost提升方法

提升方法的基本思想是通过改变训练样本的权重学习多个分类器，并将这些线性分类器进行线性组合，提高分类性能。

AdaBoost

• 提高前一轮被分类错误样本的权值，降低前一轮被分类正确的权值；
• 加大分类误差率小的弱分类器。

算法
输入：训练集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中$x_i\in X?R^n$， y i ∈ Y ? { ? 1 , 1 } y_i\in Y \subseteq\{-1,1\} yi?∈Y?{?1,1}；弱学习算法。
输出：最终分类器$G(n)$。

1. 初始化训练数据的权值分布
   $$D_1=(w_{1}1,...,w_{1}i,...,w_{1N}),w_{1}i=\frac{1}{N}$$

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

   • 使用具有权值分布$D_m$的训练集学习，得到基本分类器：
     G m ( x ) : X ? { ? 1 , 1 } G_m(x):X\longrightarrow\{-1,1\} Gm?(x):X?{?1,1}
   • 计算$G_m(x)$在训练集上的分类误差率 ：
     $$\begin{gathered} e_m=\sum _{i=1}^{N}P(G_m(x_i)\ne y_i) \\ =\sum _{i=1}^N{w}_{m}iI(G_m(x_i)\ne y_i) \\ =\sum _{G_m(x_i)\ne y_i}{w}_{m}i \end{gathered}$$
   • 计算$G_m(x)$的系数：
     $${\alpha }_m=\frac{1}{2}log\frac{1?e_m}{e_m}$$
   • 更新训练集的权值分布
     $$D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$$
     $$w_{m+1,i}=\frac{w_{m,i}}{Z_m}exp(?{\alpha }_m{y}_i{G}_m(x_i)),i=1,2,...,N$$
     其中$Z_m$是规范化因子
     $$Z_m=\sum _{i=1}N{w}_{m,i}exp(?{\alpha }_m{y}_i{G}_m(x_i))$$
     它使得$D_{m+1}$成为一个概率分布，即${\sum }_{i=1}^N{w}_{m,i}=1$。

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))$$
   注：式①可写成
   $$w_{m+1,i}=?\begin{array}{r}\frac{w_{m,i}}{Z_m}{e}^{?{\alpha }_m},G_m(x_i)=y_i\\ \frac{w_{m,i}}{Z_m}{e}^{{\alpha }_m},G_m(x_i)\ne y_i\end{array}$$
   可知误分类样本在每一轮学习后权重会被放大$e^{2{\alpha }_m}=\frac{1?e_m}{e_m}$倍，系数${\alpha }_m$表示分类器$G_m(x)$的重要性，所有${\alpha }_m$之和并不等于1。