AdaBoost

抄袭/参考资料

• 台湾大学《机器学习技法》视频
• 李航《统计学习方法》
• 周志华《机器学习》
• 深入浅出ML之Boosting家族
• Adaboost - 新的角度理解权值更新策略

---

Adaboost算法是Boosting集成框架下的一种具体实现，在分类问题中的主要特点：通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。

先回顾下Boosting两个问题：

1. 在每一轮学习之前，如何改变训练数据的权值分布？

   提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

2. 如何将一组弱分类器组合成一个强分类器？

   弱分类器的组合，AdaBoost采取加权多数表决的方法。

---

AdaBoost算法

（一）、假设训练数据集具有均匀（相同）的权值分布，即每个训练样本在基本分类器的学习中作用相同。这一假设保证第一步能够在原始数据上学习基本分类器$G_1(x)$
$$
D_1 = (w_{1i},w_{12},…w_{1M})\\
w_{1i}=\frac{1}{M}
$$

（二）、AdaBoost反复学习基本分类器，在每一轮$k=1,2,⋯,K$顺序地执行下列操作：

1. 学习基本分类器：使用当前分布加权的训练数据集，学习基本分类器；

$$
G_k(x): \mathcal{X} \rightarrow \{-1, +1\}
$$

2. 计算当前训练数据集上的分类误差率

$$
e_k = P(G_k(x^{(i)}) \not= y^{(i)}) = \sum_{i=1}^{M} w_{ki}I(G_k(x^{(i)}) \not= y^{(i)})
$$

3. 计算本次学习到的分类器的系数/权重

$$
\alpha_k = \frac{1}{2} \log \frac{1-e_k}{e_k} \quad(e是自然对数)
$$

4. 更新训练数据集的权值分布，为学习下个分类器做准备

$$
D_{k+1} = (w_{k+1,1}, w_{k+1,2}, \cdots, w_{k+1,M})\
w_{k+1,i} = \frac{w_{k,i}}{Z_k} \exp(-\alpha_k y^{(i)} G_k(x^{(i)})), \quad i=1,2,\cdots,M
$$

5. 构建基本分类器的线性组合

$$
f(x) = \sum_{k=1}^{K} \alpha_k G_k(x)
$$

（三）、得到最终的分类器
$$
G(x) = sign (f(x)) = sign \left(\sum_{k=1}^{K} \alpha_k G_k(x) \right)
$$