AdaBoost

AdaBoost 与随机森林一样，都是通过多个树形分类器群策群力，最后得出最终结果的集成学习模型。与随机森林不同的是，每个弱分类器并不是独立的个体，而是每一个分类器都是建立在上一个分类器基础上形成的。

AdaBoost 中每个弱分类器不再是平等的，它们的头顶上都有着一个权值 $\alpha_k$，来控制着他们的话语权：加大分类误差率小的弱分类器权值，减少分类误差率大的弱分类器权值。而每一个样本，也有着相应的权值 $w_i$，如果他在上一个弱学习器被错误分类，那么这个样本将会在下一次分类时增大权值，让下一个学习器多多照顾到这类样本。

现在有一个二分类的训练数据集

$$T = \{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(m)},y^{(m)})\}$$

其中 $x^{(i)} \in \mathbb R^n$，$y^{(i)} \in {-1,1}$。

首先为所有的样本初始化权重分布

$$D_1 = (w^{(1)}_1,w^{(2)}_1,\dots,w^{(m)}_1);\quad w^{(i)}_1=\frac 1 m,\quad i=1,2,\dots,m$$

之后，根据训练集 $T$ 以及权值 $D_1$ 对弱学习器 $G_1$ 进行训练，计算在训练集上的误差率 $e_1$

$$e_1 = P\left(G_1(x^{(i)}) \neq y^{(i)}\right)=\sum_{i=1}^mw^{(i)}_1I\left(G_1(x^{(i)}) \neq y^{(i)}\right)$$

从上式可以看出误差率就是被分类错误的样本所对应的权值之和。

再之后，计算 $G_1$ 的系数 $\alpha_1$

$$\alpha_1 = \frac1 2\log\frac{1-e_m}{e_m}$$

当 $e_1\leq\frac 1 2$ 时，$\alpha_1 \geq 0$，并且 $\alpha_1$ 随着 $e_1$ 的减小而增大。当然，如果 $e_1>\frac 1 2$，那这个分类器就和瞎猜没什么两样了。

第一个训练器 $G_1$ 就已经训练好了，下面更新数据集的权值分布 $D_2$

$$D_2 = (w^{(1)}_2,w^{(2)}_2,\dots,w^{(m)}_2)\qquad w^{(i)}_2=\frac{w^{(i)}_1}{Z_1}\exp\left(-\alpha_1y^{(i)}G_1(x^{(i)})\right)$$

其中 $Z_1$ 是规范化因子

$$Z_1 = \sum_{i=1}^mw^{(i)}_1\exp\left(-\alpha_1y^{(i)}G_1(x^{(i)})\right)$$

如果将分类正确与分类错误分开来看，就会有

$$w_2^{(i)} = \begin{cases} \begin{align} &\frac{w_1^{(i)}}{Z_1}\exp(-\alpha_m),\quad &G_1(x^{(i)})=y^{(i)}\\ &\frac{w_1^{(i)}}{Z_1}\exp(\alpha_m),\quad &G_1(x^{(i)})\neq y^{(i)} \end{align} \end{cases}$$

如果样本被分类错误，那么权值就会被扩大。

之后便可以继续迭代，生成更多的训练模型 $G_2,G_3,\dots,G_K$。

得到所有分类器的线性组合

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

得到最终分类器

$$G(x)=\text{sign}\left(f(x)\right)=\text{sign}\left( \sum_{k=1}^K\alpha_kG_k(x) \right)$$

误差分析

这里的误差指的是训练误差，在研究 AdaBoost 之前，先说一下加权线性规划。

加权最小二乘

刚接触 AdaBoost 的时候很是疑惑，这个带权重的分类器到底应该如何训练。发现样本加权这个事情在最小二乘法中就有应用。

如果样本 $x^{(i)}$ 的权重为 $wi$；$\sum_i w_i = 1$，训练出的学习器为 $f\theta(x)$，评价模型的代价函数 $J(\theta)$ 为：

$$J(\theta) = \frac 1 {2m}\sum_{i=1}^m w_i\left( y^{(i)} - f_\theta(x^{(i)}) \right)^2$$

是这样的，在每项的代价函数前面乘上自己的权重，就是加权最小二乘法了。

---

下面来说 AdaBoost，根据训练误差分析，可知 AdaBoost 算法的最终分类器的误差训练界为

$$\frac 1 m\sum_{i=1}^mI\left(G_1(x^{(i)}) \neq y^{(i)}\right) \leq \prod_{k=1}^KZ_k$$

具体的推导过程可以看《统计学习方法》的 142 页。

👇

通过上不等式可以发现，在每一轮选取适当的 $G_k$ 可以使的 $Z_k$ 最小，则会让训练误差快速下降。

再看

$$Z_k = \sum_{i=1}^mw^{(i)}_k\exp\left(-\alpha_ky^{(i)}G_{k}(x^{(i)})\right)$$

$Z_k$ 像不像是上面的代价函数 $J(\theta)$。那么选取适当的 $G_k$ 可以使的 $Z_k$ 最小这一句可不可以近似称线性规划中的：选取适当的 $f$ 可以使得 $J(\theta)$ 最小。

👆

对于二分类问题，有

$$\prod_{k=1}^KZ_k \leq \exp\left( -2\sum_{k=1} ^K\gamma_k^2 \right);\qquad\gamma_k = \frac 1 2 - e_k$$

若存在 $\gamma>0$，对所有 $k$ 有 $\gamma_k \geq\gamma$，则

$$\frac 1 m\sum_{i=1}^mI\left(G_1(x^{(i)}) \neq y^{(i)}\right) \leq \exp(-2K\gamma^2)$$

观察上式可以得出，随着弱学习器的增加，AdaBoost 的误差成指数速率下降。