【机器学习】AdaBoost原理

基本思想

相较于直接训练出一个强分类器，在训练集中找到一个弱分类器会简单很多。提升方法就是从弱学习算法出发，反复学习，得到一系列的弱分类器（基本分类器），然后组合这些弱分类器，构成一个强分类器。

我们需要解决的问题有两个：

每一轮如何改变训练数据的权值或概率分布？
如何将弱分类器合成一个强分类器？

AdaBoost针对这两个问题，做出以下解答：

假设现在有M轮的弱分类器选择。在每一轮训练中，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值，使得那些没有得到正确分类的数据，由于其权值的加大而收到后一轮的弱分类器的更大关注。（注意，是样本的权值，不是分类器的权值）
使用加权多数表决的方法，加大分类误差率小的弱分类器的组合，使其在表决中起较大作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小作用。

AdaBoost算法

假设有训练数据集$ T=\lbrace (x_1, y_1), …, (x_N, y_N)\rbrace $，标记有$ \lbrace{-1, +1}\rbrace$，我们将从该数据集中学到一系列的弱分类器，最后将它们组合成一个强分类器。

输入：训练数据集

输出：最终的强分类器 $G(x)$

具体步骤：

先初始化训练数据的权值分布，假设训练数据集具有均匀的权值分布，也就是认为每个训练样本此时在本次的学习过程中作用是相同的。 $D_1$ 表示此次的权值分布， $w_{1i}$ 表示的是第一轮第i个样本点的权值。

$D_1 = (w_{11}, .., w_{1N}), w_{1i} = \frac{1}{N}$
循环M次操作，找到M个弱分类器：
- 使用当前加权分布 $D_m$ 学习基本分类器 $G_m$ ，并确定一个阈值，使得分类误差率最小。经过化简得，分类误差率是被 $G_m$ 误分类样本的权值之和。
  
  $e_m = \sum_{G_{m}(x_i) \neq y_i}w_{mi}$
- 此时已知本轮的 $G_m$ 及使得分类误差率最小的阈值 $e_m$ ，就可以计算该分类器的系数了。可以发现，分类误差越大，系数就越小。说明这个分类器的效果比较差，给的权重就小一些。
  
  $\alpha_m = \frac{1}{2} log \frac{1- e_m}{e_m}$
- 更新训练数据集的权值分布， $D_{m+1} = (w_{m+1, 1}...,w_{m+1,N})$
  
  $w_{m+1, i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), i=1,2..N$
  
  $Z_m$ 是规范化因子，它使得 $D_{m+1}$ 成为一个概率分布。
  
  $Z_m = \sum_{i=1} ^N w_{mi}exp(-\alpha_my_iG_m(x_i))$
- 被基本分类器 $G_m$ 误分类样本的权值将扩大，而被正确分类样本的权值将缩小。不改变所给的训练数据，而不断改变训练数据权值的分布。
构建基本分类器的线性组合：

$f(x) = \sum^M_{m=1}\alpha_mG_m(x)$

最终的分类器将加上sign函数

$G(x) = sign(f(x))$