AdaBoost 算法

ensemble-learning

---

统计学习方法

1. Boosting方法的基本思路

• 强可学习： 在PAC（概率近似正确）学习的框架中，一个概念，如果存在一个多项式的学习算法能够学习他，且正确率恒高，就称这个概念是强可学习的；
• 一个概念，如果存在一个多项式的学习能够学习它，学习的正确率仅比随机猜测略好，那么这个概念 就是弱可学习的，

对于Boosting问题，有两个问题要答：
1. 在每一轮中如何改变训练数据的权值和概率分布
2. 如何将弱分类器组成一个强分类器

Adaboost的思想

1. 对于训练数据，提高那些在前一轮弱分类器错误分类样本的权值， 而降低那些被正确分类样本的权值。
2. 弱分类器的组合，AdaBoost采用 加权多数表决的方式。通过加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。

AdaBoost 算法描述

第一步： 初始化训练数据的权值分布

假设我们有N个训练样本，那么初始的训练数据权值分布如下：

$$D_1 = (w_{11}, \cdots, w_{1i}, \cdots, w_{1N}), \quad w_{1i} = \frac{1}{N}, \quad i=1,2,\cdots, N$$

第二步： 训练M个弱分类器

每个分类器都有以下四个步骤，都需要计算分类器的分类误差率，以及每个分类器的权重系数

1. 使用具有权值分布 $D_t$（t表示训练第t轮） 的训练数据集学习，得到M个基本分类器 $G(x)$

2. 计算 $G(x)$在训练数据集上的分类误差率：
   

   $$e_t = P(G(x_i) \, \neq \, y_i) = \frac{错误分类的数量}{总样本数}$$

3. 计算第t轮时$G(x)$ 的系数
   

   $$a_t = \frac{1}{2} ln \frac{1-e_t}{e_t}$$

4. 更新训练数据集的权值分布
   

   $$Z_t = \sum_{i=1}^{N} w_{t,i} e^{(-a_ty_iG(x_i))} \\ w_{t+1, i} = \frac{w_{i,t}}{Z_t} e^{(-a_t y_i G(x_i)}), i = 1,2 \cdots, N \\ D_{t+1} = (w_{t+1,1}, \cdots, w_{t+1,i}, \cdots, w_{t+1,N} \\ $$

其中， D_{m+1} 是规范化因子， 它使得

第三步： 构建基本分类器的线性组合

$$f(x) = \sum_{i=1}^M a_mG_m(x) \\ G(x) = sign(f(x)) = sign(\sum_{m=1}^M a_m G_m(x))$$

损失函数

Adaboost 选择 指数损失函数作为其损失函数：

$$L(y,f(x)) = \frac{1}{n} \sum_{i=1}^n exp[-yf(x)]$$