Adaboost

假设我们的训练集样本是

$$T=\left\{\left(x, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots\left(x_{m}, y_{m}\right)\right\}$$

训练集的在第k个弱学习器的输出权重为

$$D(k)=\left(w_{k 1}, w_{k 2}, \ldots w_{k m}\right) ; \quad w_{1 i}=\frac{1}{m} ; \quad i=1,2 \ldots m$$

二元分类

弱学习器误差

对于二元分类问题，输出为${-1,1}$，则第k个弱分类器$G_{k}(x)$在训练集上的加权误差率为

$$e_{k}=P\left(G_{k}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{m} w_{ki} I\left(G_{k}\left(x_{i}\right) \neq y_{i}\right)$$

弱学习器权重

接着我们看弱学习器权重系数,对于二元分类问题，第k个弱分类器Gk(x)的权重系数为

$$\alpha_{k}=\frac{1}{2} \log \frac{1-e_{k}}{e_{k}}$$

从上式可以看出，如果分类误差率ek越大，则对应的弱分类器权重系数αk越小。也就是说，误差率小的弱分类器权重系数越大。

更新样本权重

第三个问题，更新更新样本权重D。假设第k个弱分类器的样本集权重系数为$D(k)=\left(w_{k 1}, w_{k 2}, \ldots w_{k m}\right)$，则对应的第k+1个弱分类器的样本集权重系数为

$$w_{k+1, i}=\frac{w_{k i}}{Z_{K}} \exp \left(-\alpha_{k} y_{i} G_{k}\left(x_{i}\right)\right)$$

这里Zk是规范化因子
如果第i个样本分类错误，则$y_{i} G_{k}\left(x_{i}\right)<0$，导致样本的权重在第k+1个弱分类器中增大，如果分类正确，则权重在第k+1个弱分类器中减少.

集合成强学习器

最后一个问题是集合策略。Adaboost分类采用的是加权表决法，最终的强分类器为

$$f(x)=\operatorname{sign}\left(\sum_{k=1}^{K} \alpha_{k} G_{k}(x)\right)$$

其中sign函数为符号函数：

$$\operatorname{sign} x=\left\{\begin{array}{ccc}{-1} & { :} & {x<0} \\ {0} & { :} & {x=0} \\ {1} & { :} & {x>0}\end{array}\right.$$

回归问题

弱学习器误差

我们先看看回归问题的误差率的问题，对于第k个弱学习器，计算他在训练集上的最大误差

$$E_{k}=\max \left|y_{i}-G_{k}\left(x_{i}\right)\right| i=1,2 \ldots m$$

然后计算每个样本的相对误差

$$e_{k i}=\frac{\left|y_{i}-G_{k}\left(x_{i}\right)\right|}{E_{k}}$$

最终得到第k个弱学习器的 误差率

$$e_{k}=\sum_{i=1}^{m} w_{k i} e_{k i}$$

弱学习器权重

我们再来看看如何得到弱学习器权重系数α。这里有：

$$\alpha_{k}=\frac{e_{k}}{1-e_{k}}$$

更新样本权重

对于更新更新样本权重D，第k+1个弱学习器的样本集权重系数为

$$w_{k+1, i}=\frac{w_{k i}}{Z_{k}} \alpha_{k}^{1-e_{k i}}$$

集成强回归器

$$f_{M}(x)=\sum_{m=1}^{M} \ln \left(\frac{1}{\alpha_{m}}\right) G_{m}(x)$$

损失函数

我们的算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。也就是说，第k-1轮的强学习器为

$$f_{k-1}(x)=\sum_{i=1}^{k-1} \alpha_{i} G_{i}(x)$$

而第k轮的强学习器为

$$f_{k}(x)=\sum_{i=1}^{k} \alpha_{i} G_{i}(x)$$

上两式一比较可以得到

$$f_{k}(x)=f_{k-1}(x)+\alpha_{k} G_{k}(x)$$

可见强学习器的确是通过前向分步学习算法一步步而得到的。

Adaboost损失函数为指数函数，即定义损失函数为

$$\arg \min \sum_{i=1}^{m} \exp \left(-y_{i} f_{k}(x)\right)$$

利用前向分步学习算法的关系可以得到损失函数为

$$\left(\alpha_{k}, G_{k}(x)\right)=\arg \min \sum_{i=1}^{m} \exp \left[\left(-y_{i}\right)\left(f_{k-1}(x)+\alpha G(x)\right)\right]$$

令$w_{k j}=\exp \left(-y_{i} f_{k-1}(x)\right)$，它的值不依赖于$\alpha,G$,因此与最小化无关。

将这个式子带入损失函数,损失函数转化为

$$\left(\alpha_{k}, G_{k}(x)\right)=\arg \min _{\alpha, G} \sum_{i=1}^{m} w_{k i} \exp \left[-y_{i} \alpha G(x)\right]$$

总结

这里对Adaboost算法的优缺点做一个总结。

　　　　Adaboost的主要优点有：

　　　　1）Adaboost作为分类器时，分类精度很高

　　　　2）在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。

　　　　3）作为简单的二元分类器时，构造简单，结果可理解。

　　　　4）不容易发生过拟合

　　　　Adaboost的主要缺点有：

　　　　1）对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。