adaboost算法

1. 算法简介

Boosting, 也称为增强学习或提升法，是一种重要的集成学习技术，能够将预测精度仅比随机猜度略高的弱学习器增强为预测精度高的强学习器，这在直接构造强学习器非常困难的情况下，为学习算法的设计提供了一种有效的新思路和新方法。其中最为成功应用的是，Yoav Freund和Robert Schapire在1995年提出的AdaBoost算法。

AdaBoost是英文”Adaptive Boosting”（自适应增强）的缩写，它的自适应在于：前一个基本分类器被错误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数才确定最终的强分类器。

2. 算法过程

给定训练数据集： $(x_1,y_1),…,(x_N,y_N)$，其中 $y_i \in \{1,-1\}$，用于表示训练样本的类别标签$i=1,…,N$。Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。

3. 算法详细步骤

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

(a) 使用具有权值分布$D_m$的训练数据集学习，得到基本分类器
$G_m(x):f \rightarrow \{-1,+1\}$
(b) 计算$G_m(x)$在训练数据集上的分类误差率
$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)$
(c) 计算$G_m(x)$的系数
$\alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m}$
这里的对数是自然对数

(d) 更新训练数据集的权值分布
$D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,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$是规范化因子
$Z_m = \sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))$
它使$D_{m+1}$成为一个概率分布
构建基本分类器的线性组合
$f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)$
得到最终的分类器
$G(x) = sign(f(x)) = sign(\sum_{m=1}^M\alpha_mG_m(x))$
对AdaBoost算法做下面的说明：

（1）首先，是初始化训练数据的权值分布$D_1$。假设有$N$个训练样本数据，则每一个训练样本最开始时，都被赋予相同的权值$w_1 = \frac{1}{N}$。

（2）然后，训练弱分类器$h_i$。具体训练过程中是：如果某个训练样本点，被弱分类器$h_i$准确地分类，那么在构造下一个训练集中，它对应的权值要减小；相反，如果某个训练样本点被错误分类，那么它的权值就应该增大。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

（3）最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。

换而言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

4. 代码实现
代码实现地址：

https://github.com/StringsLi/ml_scratch_scala/blob/master/src/main/scala/com/strings/model/ensemble/AdaBoost.scala

5. 参考文献
李航《统计学习方法》2012.3

1. 算法简介

2. 算法过程

3. 算法详细步骤

4. 代码实现

5. 参考文献