AdaBoost

AdaBoost，是“adaptive boosting”（自适应增强）的缩写，是一种机器学习方法，由Yoav Freund和Robert Schapire提出。AdaBoost方法的自适应在于：后面的分类器会在那些被之前分类器分错的样本上训练。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，相比于大多数学习算法，AdaBoost方法对于过拟合问题不够敏感。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但其分类效果只要比随机好一点（比如它的二分类错误率略小于0.5），就能够改善最终模型。即使是那些错误率高于随机分类器的弱分类器也是有用的，因为在最终的多个分类器的线性组合中，可以给它们赋予负系数，反过来也能提升分类效果。
AdaBoost方法是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较困难（更富信息）的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，劲儿训练分类器C_k。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器C_k。整个训练过程如此迭代地进行下去。

AdaBoost算法

用 xⁱ 和 y_i 表示原始样本集D的样本点和它们的类标。用 W_k(i) 表示第k次迭代时全体样本的权重分布。这样就有如下所示的AdaBoost算法：

1. begin initial D={x¹，y₁，...，xⁿ，y_n}，k_max，W_k(1)=1/n，i=1，...，n
2. k ← 0
3. do k ← k+1
4. 训练使用按照 W_k(i) 采样的 D 的若学习器 C_k
5. E_k ← 对使用 W_k(i) 的 D 测量的 C_k 的训练误差
6. $\alpha _{k}\gets {\tfrac {1}{2}}\ln {\frac {1-E_{k}}{E_{k}}}$
7. $W_{k}(i+1)\gets {\dfrac {W_{k}(i)}{Z_{k}}}\times {\begin{cases}e^{-\alpha _{k}},&{\mbox{if}}h_{k}(x^{i})=y_{i}\\e^{\alpha _{k}},&{\mbox{if}}h_{k}(x^{i})\neq y_{i}\end{cases}}$
8. until k=k_max
9. return C_k和α_k，k=1，...，k_max（带权值分类器的总体）
10. end

注意第5行中，当前权重分布必须考虑到分类器 C_k 的误差率。在第7行中， Z_k只是一个归一化系数，使得 W_k(i) 能够代表一个真正的分布，而 h_k(xⁱ) 是分量分类器 C_k 给出的对任一样本点xⁱ的标记（+1或-1）， h_k(xⁱ) = y_i 时，样本被正确分类。第8行中的迭代停止条件可以被换为判断当前误差率是否小于一个阈值。
最后的总体分类的判决可以使用各个分量分类器加权平均来得到：
$g(x)=[\sum _{k=1}^{k_{max}}\alpha _{k}h_{k}(x)]$
这样，最后的判定规则简单的就是 Sgn[g(x)] 。