AdaBoost基本思路

分类问题

Adaboost 是 Boosting 算法中有代表性的一个。原始的 Adaboost 算法用于解决二分类问题，因此对于一个训练集

T = {(x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n})}

其中 $x_{i} \in X \subseteq R^{n}, y_{i} \in Y = {- 1, + 1}$ ，，首先初始化训练集的权重

D_{1} = w_{1 i} = (w_{11}, w_{12}, ..., w_{1 n}) \frac{1}{n}, i = 1, 2, ..., n

根据每一轮训练集的权重 $D_{m}$ ，对训练集数据进行抽样得到 $T_{m}$ ，再根据 $T_{m}$ 训练得到每一轮的基学习器 $h_{m}$ 。通过计算可以得出基学习器 $h_{m}$ 的误差为 $e_{m}$

e_{m} = P (h_{m} (x_{i}) \neq = y_{i}) = i = 1 \sum m w_{ki} I (h_{k} (x_{i}) \neq = y_{i})

根据基学习器的误差计算得出该基学习器在最终学习器中的权重系数

α_{m} = \frac{1}{2} ln \frac{1 - e _{m}}{e _{m}}

为什么这样计算弱学习器权重系数？从上式可以看出，如果分类误差率 $e_{k}$ 越大，则对应的弱分类器权重系数 $α_{k}$ 越小。也就是说，误差率小的弱分类器权重系数越大。具体为什么采用这个权重系数公式，见AdaBoost分类问题的损失函数优化。

更新训练集权重

D_{m + 1} = w_{m + 1, i} = (w_{m + 1, 1}, w_{m + 1, 2}, ..., w_{m + 1, n}) \frac{w _{m, i}}{Z _{m}} exp (- α_{m} y_{i} h_{m} (x_{i}))

其中 $Z_{m}$ 为规范化因子

Z_{m} = i = 1 \sum n w_{m, i} exp (- α_{m} y_{i} h_{m} (x_{i}))

从 $w_{m + 1, i}$ 计算公式可以看出，如果第 $i$ 个样本分类错误，则 $y_{i} h_{m} (x_{i}) < 0$ ，导致样本的权重在第 $m + 1$ 个弱分类器中增大，如果分类正确，则权重在第 $m + 1$ 个弱分类器中减少.具体为什么采用样本权重更新公式，见AdaBoost分类问题的损失函数优化。

从而保证 $D_{m + 1}$ 为一个概率分布。最终根据构建的 $M$ 个基学习器得到最终的学习器：

h_{f} (x) = sign (m = 1 \sum M α_{m} h_{m} (x))

回归问题

由于Adaboost的回归问题有很多变种，这里以Adaboost R2算法为准。

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

E_{m} = ma x ∣ y_{i} - h_{m} (x_{i}) ∣ i = 1, 2... n

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

e_{mi} = \frac{∣ y _{i} - h _{m} ( x _{i} ) ∣}{E _{m}}

这里是误差损失为线性时的情况，如果我们用平方误差，则 $e_{mi} = \frac{( y _{i} - h _{m} ( x _{i} ) ) ^{2}}{E _{m}^{2}}$ ,如果我们用的是指数误差，则 $e_{mi} = 1 - e x p （ \frac{- y _{i} + h _{m} ( x _{i} ))}{E _{m}} ）$

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

e_{m} = i = 1 \sum n w_{mi} e_{mi}

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

α_{m} = \frac{e _{m}}{1 - e _{m}}

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

w_{m + 1, i} = \frac{w _{mi}}{Z _{m}} α_{m}^{1 - e_{mi}}

这里 $Z_{m}$ 是规范化因子

Z_{m} = i = 1 \sum n w_{mi} α_{m}^{1 - e_{mi}}

最后是结合策略，和分类问题稍有不同，采用的是对加权的弱学习器取权重中位数对应的弱学习器作为强学习器的方法，最终的强回归器为

f (x) = h_{m}^{*} (x)

其中， $h_{m}^{*} (x)$ 是所有 $l n \frac{1}{α _{m}}, m = 1, 2, .... M$ 的中位数值对应序号 $m^{*}$ 对应的弱学习器。

AdaBoost分类问题的损失函数优化

刚才上一节我们讲到了分类Adaboost的弱学习器权重系数公式和样本权重更新公式。但是没有解释选择这个公式的原因，其实它可以从Adaboost的损失函数推导出来。

从另一个角度讲，Adaboost是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

模型为加法模型好理解，我们的最终的强分类器是若干个弱分类器加权平均而得到的。

前向分步学习算法也好理解，我们的算法是通过一轮轮的弱学习器学习，利用前一个强学习器的结果和当前弱学习器来更新当前的强学习器的模型。也就是说，第 $m - 1$ 轮的强学习器为

f_{m - 1} (x) = i = 1 \sum m - 1 α_{i} h_{i} (x)

第 $m$ 轮的强学习器为

f_{m} (x) = f_{m - 1} (x) + α_{m} h_{m} (x)

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

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

α, h a r g min i = 1 \sum n e x p (- y_{i} f_{m} (x_{i}))

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

(α_{m}, h_{m} (x)) = α, h a r g min i = 1 \sum n e x p [(- y_{i}) (f_{m - 1} (x_{i}) + α h (x_{i}))]

令 $w_{mi}^{^{'}} = e x p (- y_{i} f_{m - 1} (x_{i}))$ , 它的值不依赖于 $α, h$ ，因此与最小化无关，仅仅依赖于 $f_{m - 1} (x)$ ,随着每一轮迭代而改变。

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

(α_{m}, h_{k} (x)) = α, h a r g min i = 1 \sum n w_{mi}^{^{'}} e x p [- y_{i} α h (x_{i})]

首先，我们求 $h_{m} (x)$ ，

i = 1 \sum n w_{mi}^{^{'}} e x p (- y_{i} α h (x_{i})) = y_{i} = h_{m} (x_{i}) \sum w_{mi}^{^{'}} e^{- α} + y_{i} \neq = h_{m} (x_{i}) \sum w_{mi}^{^{'}} e^{α} = (e^{α} - e^{- α}) i = 1 \sum n w_{mi}^{^{'}} I (y_{i} \neq = h_{m} (x_{i})) + e^{- α} i = 1 \sum n w_{mi}^{^{'}}

h_{m} (x) = h a r g min i = 1 \sum n w_{mi}^{^{'}} I (y_{i} \neq = h (x_{i}))

对 $α$ 求导，使其等于0，则就得到了

(e^{α} + e^{- α}) i = 1 \sum n w_{mi}^{^{'}} I (y_{i} \neq = h_{m} (x_{i})) - e^{- α} i = 1 \sum n w_{mi}^{^{'}} = 0

注意到

e_{m} = \frac{i = 1 \sum n w _{mi}^{^{'}} I ( y _{i} \neq = h ( x _{i} ))}{i = 1 \sum n w _{mi}^{^{'}}}

将 $e_{m}$ 的表达式带入上面导数为0 的表达式，我们得到：

(e^{α} + e^{- α}) e_{m} - e^{- α} = 0

即，

α_{m} = \frac{1}{2} l n \frac{1 - e _{m}}{e _{m}}

最后看样本权重的更新。利用 $f_{m} (x) = f_{m - 1} (x) + α_{m} h_{m} (x)$ 和 $w_{mi}^{'} = e x p (- y_{i} f_{m - 1} (x_{i}))$ ，即可得：

w_{m + 1, i}^{^{'}} = w_{mi}^{^{'}} e x p [- y_{i} α_{m} h_{m} (x_{i})]

这样就得到了上面的样本权重更新公式。

AdaBoost多元分类

对于Adaboost多元分类算法，其实原理和二元分类类似，最主要区别在弱分类器的系数上。比如Adaboost SAMME算法，它的弱分类器的系数

α_{k} = \frac{1}{2} l o g \frac{1 - e _{k}}{e _{k}} + l o g (R - 1)

其中 $R$ 为类别数。从上式可以看出，如果是二元分类， $R = 2$ ，则上式和我们的二元分类算法中的弱分类器的系数一致。

Adaboost小结

前面有一个没有提到，就是弱学习器的类型。理论上任何学习器都可以用于Adaboost.但一般来说，使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。

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

Adaboost的主要优点有：

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

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

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

4）不容易发生过拟合

Adaboost的主要缺点有：

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

Reference

集成学习之Adaboost算法原理小结

#

!