【机器学习】Boosting与AdaBoost分类与回归原理详解与公式推导

1.BoostingBoosting族算法的工作机制为：先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，然后基于调整后的样本分布来训练下一个基学习器；重复进行，直到基学习器数目达到事先指定的值；最终将所有基学习器根据结合策略结合，得到最终的强学习器。Boosting中的基学习器是弱学习器，即仅仅比随机猜测好一点的模型，比如一个简单的决策树。使用弱学习器而不是...

邓坤元

11240人浏览 · 2018-12-08 15:04:27

邓坤元 · 2018-12-08 15:04:27 发布

1.Boosting

Boosting族算法的工作机制为：先从初始训练集中训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，然后基于调整后的样本分布来训练下一个基学习器；重复进行，直到基学习器数目达到事先指定的值；最终将所有基学习器根据结合策略结合，得到最终的强学习器。

Boosting中的基学习器是弱学习器，即仅仅比随机猜测好一点的模型，比如一个简单的决策树。使用弱学习器而不是强学习器的原因是，发现一个弱学习器通常要比发现强学习器容易得多，且Boosting方法就是从弱学习器出发，反复学习，组合构成一个强学习器。

Boosting族算法主要关注降低偏差，最着名的算法是AdaBoost和提升树（Boosting tree）。这篇博客主要介绍AdaBoost的原理和算法描述，提升树的相关内容将在下一篇博客中介绍。

2. AdaBoost原理

作为Boosting家族的一员，AdaBoost首先要回答两个问题：

1.如何改变训练样本分布？

2.采用什么样的结合策略来将基学习器结合成一个强学习器。

AdaBoost的做法是：

1.提高那些被前一轮基学习器错误分类的样本的权值，降低那些被正确分类的样本的权值;

2.对所有基学习器采用加权结合，增大分类误差小的基学习器的权值，减少分类误差率大的基学习器的权值。

理论上的AdaBoost可以使用任何算法作为基学习器，但一般来说，使用最广泛的AdaBoost的弱学习器是决策树和神经网络。

3. AdaBoost分类算法描述

输入：训练集 $D = \left\{ \left( x _ { i } , y _ { i } \right) \right\} _ { i = 1 } ^ { m }$ ，其中 $x _ { i } \in \chi \subseteq R ^ { n }$ ， ${y_i} \in {\cal Y} = \left\{ { + 1, - 1} \right\}$ ；基学习算法 $\mathfrak {L}$ ；基学习器个数 $Ť$ 。

过程：

（1）初始化训练样本的权值分布

$\mathcal { D } _ { 1 } = \left( w _ { 11 } , \ldots , w _ { 1 i } , \ldots , w _ { 1 m } \right) , w _ { 1 i } = \frac { 1 } { m } , i = 1,2 , \ldots , m$

（2）对迭代轮次 ${t = 1,2，\ ldots，T}$

（a）使用具有当前分布 ${\mathcal D}_t$ 的训练数据集训练基学习器 ${h_t} = \mathfrak{L}\left( {D,{{\mathcal D}_t}} \right)$ ;

（b）基学习器 $h_t$ 在训练数据集上的分类误差率：

${\ varepsilon _t} = P \ left（{{h_t} \ left（x \ right）\ ne y} \ right）= \ sum \ limits_i ^ m {{w_ {ti}}我\左（{{h_t} \ left（{{x_i}} \ right）\ ne {y_i}} \ right）}$

（c）基学习器 $H T$ 的权重系数 ${\ alpha _t}$ （ ${\ alpha _t}$ 表示 $H T$ 在最终分类器中的重要性，当 ${\ varepsilon _t} \ le \ frac {1} {2}$ 时， ${\ alpha _t} \ ge 0$ ，并且 ${\ alpha _t}$ 随 ${\ varepsilon _t}$ 减少而增大。分类误差率 ${\ varepsilon _t}$ 越小的基学习器在最终强学习器中的权值越高）：

${\ alpha _t} = \ frac {1} {2} \ cdot \ ln \ frac {{1 - {\ varepsilon _t}}} {{{\ varepsilon _t}}}$

（d）更新训练集的样本分布 ${{\ cal D} _ {t + 1}} = \ left（{{w_ {t + 1,1}}，\ ldots，{w_ {t + 1，i}}，\ ldots，{w_ {t + 1，m}}} \ right）$ ：

$w _ { t + 1 , i } = \frac { w _ { t i } } { Z _ { t } } \exp \left( - \alpha _ { t } y _ { i } h _ { t } \left( x _ { i } \right) \right) = \left\{ \begin{array} { l l } { \frac { w _ { t i } } { Z _ { t } } e ^ { - \alpha _ { t } } , } & { h _ { t } \left( x _ { i } \right) = y _ { i } } \\ { \frac { w _ { t i } } { Z _ { t } } e ^ { \alpha _ { t } } , } & { h _ { t } \left( x _ { i } \right) \neq y _ { i } } \end{array} \right.$

${Z_t} = \ sum \ limits_ {i = 1} ^ m {{w_ {ti}} \ exp \ left（{ - {\ alpha _t} {y_i} {h_t} \ left（{{x_i}} \ right ）} \对}}$

其中， ${{Z_t}}$ 是规范化因子，只是为了保证 ${{w_{t + 1,i}}}$ 相加为1， ${{\ cal D} _ {t + 1}}$ 是一个概率分布。

（3）构建基学习器的线性组合 $\sum\limits_t^T {{\alpha _t}{h_t}\left( x \right)}$ ，得到最终的强分类器：

$H( x ) = \operatorname { sign } \left( \sum _ { t = 1 } ^ { T } \alpha _ { t } h _ { t } ( x ) \right)$

输出：强分类器 $H \ left（x \ right）$ 。

4. AdaBoost公式推导

首先介绍一下前向分步算法（forward stagewise algorithm）的基本思想：对加法模型的复杂优化问题，前向分步算法对加法模型的每一步进行单独优化求解。

AdaBoost的算法可以看成是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的一种学习方法。

1.为什么选定指数函数作为损失函数？

这是因为极小化指数损失函数等价于最小化分类误差率，并且由于指数损失函数是连续可微的，具有更好的数学性质，因此用它来代替0/1损失函数作为优化目标。证明如下：

AdaBoost的算法的最终模型是基学习器的线性组合：

$H \ left（x \ right）= \ sum \ limits_t ^ T {{\ alpha _t} {h_t} \ left（x \ right）}$ （1）

指数损失函数是：

$L \ left（{y，H \ left（x \ right）} \ right）= \ exp \ left（{ - yH \ left（x \ right）} \ right）$ （2）

式（2）可化为：

$L \ left（{y，H \ left（x \ right）} \ right）= \ exp \ left（{ - H \ left（x \ right）} \ right）\ cdot P \ left（{y = 1 \离开| x \ right。} \ right）+ \ exp \ left（{H \ left（x \ right）} \ right）\ cdot P \ left（{y = - 1 \ left | x \ right。} \ right）$ （3）

对式（3）求偏导得：

$\ frac {{\ partial L \ left（{y，H \ left（x \ right）} \ right）}} {{\ partial H \ left（x \ right）}} = - \ exp \ left（{ - H \ left（x \ right）} \ right）\ cdot P \ left（{y = 1 \ left | x \ right。} \ right）+ \ exp \ left（{H \ left（x \ right）} \ right）\ cdot P \ left（{y = - 1 \ left | x \ right。} \ right）$ （4）

令偏导为零，得到能最小化指数损失函数的 ${H \ left（x \ right）}$ ：

$H \ left（x \ right）= \ frac {1} {2} \ ln \ frac {{P \ left（{y = 1 \ left | x \ right。} \ right）}} {{P \ left（{y = - 1 \ left | x \ right。} \ right）}}$ （5）

因此，对分类任务而言，有

$\operatorname { sign } ( H ( x ) ) = \operatorname { sign } \left( \frac { 1 } { 2 } \ln \frac { P ( y = 1 | x ) } { P ( y = - 1 | x ) } \right)\\ = \left\{ \begin{array} { c c } { 1 , } & { P ( y = 1 | x ) > P ( y = - 1 | x ) } \\ { - 1 , } & { P ( y = 1 | x ) < P ( y = - 1 | x ) } \end{array} \right.$ （6）

（6）式说明极小化指数损失函数等价于最小化分类误差率，证明了指数损失函数是分类任务0/1损失函数的一致替代。

2.由于同时求解所有最优基学习器 $h_t ^ *$ 及其权重系数 $\ alpha _t ^ *$ 十分困难，AdaBoost的算法利用前向分步算法优化。为什么前向分步算法求解得到的基学习器及其权重系数，就是最终模型的最优基学习器及权重呢？

证明如下：

假设经过 $T-1$ 轮迭代，前向分步算法已经得到 ${H_ {t - 1}}$ 。

第 $Ť$ 轮迭代将要得到：

${H_t}\left( x \right) = {H_{t - 1}}\left( x \right) + {\alpha _t}{h_t}\left( x \right)$ （7）

那么第 $Ť$ 轮迭代的目标是得到能最小化 ${H_t} \ left（x \ right）$ 的指数损失函数的 ${\ alpha _t}$ 、 ${h_t}\left( x \right)$ ，即：

$\ begin {array} {l} \ begin {array} {* {20} {l}} {\ left（{{\ alpha _t}，{h_t}} \ right）= \ mathop {\ arg \ min} \限制_ {\ alpha，h} \ sum \ limits_ {i = 1} ^ m {\ exp \ left [{ - {y_i} {H_t} \ left（{{x_i}} \ right）} \ right]}} \ \ {= \ mathop {\ arg \ min} \ limits _ {\ alpha，h} \ sum \ limits_ {i = 1} ^ m {\ exp \ left [{ - {y_i} \ left（{{H_ {t - 1}} \ left（{{x_i}} \ right）+ {\ alpha _t} {h_t} \ left（{{x_i}} \ right）} \ right）} \ right]}} \ end {array} \ \ = \ mathop {\ arg \ min} \ limits _ {\ alpha，h} \ sum \ limits_ {i = 1} ^ m {\ exp \ left [{ - {y_i} {H_ {t - 1}} \ left （{{x_i}} \ right）} \ right] \ exp \ left [{ - {y_i} {\ alpha _t} {h_t} \ left（{{x_i}} \ right）} \ right]} \ end {数组}$ （8）

令 ${\overline w _{ti}} = \exp \left[ { - {y_i}{H_{t - 1}}\left( x \right)} \right]$ ，（8）式可化为：

$\left( {{\alpha _t},{h_t}} \right) = \mathop {\arg \min }\limits_{\alpha ,h} \sum\limits_{i = 1}^m {{{\overline w }_{ti}}\exp \left[ { - {y_i}{\alpha _t}{h_t}\left( x_i \right)} \right]}$ （9）

${{{\ overline w} _ {ti}}}$ 不依赖于 $\α$ 和 $H$ ，与最小化无关，只依赖于 ${H_{t - 1}}$ 。也就是说，第 $Ť$ 轮迭代得到的最优 $h_t ^ *$ 、 $\alpha _t^*$ 就是最终模型的 $h_t ^ *$ 、 $\ alpha _t ^ *$ 。这就证明了由前向分步算法求解损失函数得到的结果与真实结果一致。

3. 基学习器权重公式和样本分布更新公式是怎么来的？

首先，求 $h_t ^ *$ 。最优 $h_t ^ *$ 由下式得到：

${h_t} = \mathop {\arg \min }\limits_h \sum\limits_{i = 1}^m {{{\overline w }_{ti}}exp\left( {{\alpha _t}} \right) \cdot \exp \left[ { - {y_i}{h_t}\left( x_i \right)} \right]}$ （10）

对任意给定的 $\alpha_t$ ， $\exp \left( \alpha _ { t } \right)$ 都是一个常数，不影响最优化结果。因此（11）式可以化为式（12），得到最优 $h_t ^ *$ 。

$\begin{array}{l} {h_t} = \mathop {\arg \min }\limits_h \sum\limits_{i = 1}^m {{{\overline w }_{ti}}\exp \left[ { - {y_i}{h_t}\left( x_i \right)} \right]} \\ = \mathop {\arg \min }\limits_h \sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) \ne {y_i}} \right)} \end{array}$ （11）

然后，求解 $\alpha _t^*$ 。最优 $\ alpha _t ^ *$ 由下式得到：

${\alpha _t} = \mathop {\arg \min }\limits_\alpha \sum\limits_{i = 1}^m {{{\overline w }_{ti}}\exp \left[ { - {y_i}{\alpha _t}{h_t}\left( {{x_i}} \right)} \right]}$ （12）

将公式进行变换得到：

$\begin{array}{l} \sum\limits_{i = 1}^m {{{\overline w }_{ti}}\exp \left[ { - {y_i}{\alpha _t}{h_t}\left( {{x_i}} \right)} \right]} \\ = {e^{ - \alpha }}\sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) = {y_i}} \right)} + {e^\alpha }\sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) \ne {y_i}} \right)} \end{array}$ （13）

将式（11）得到的 $h_t$ 代入上式，并对 ${\alpha _t}$ 求偏导，使偏导为0，得到最优 $\ alpha _t ^ *$ ：

${\alpha _t} = \frac{1}{2}\ln \frac{{\sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) = {y_i}} \right)} }}{{\sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) \ne {y_i}} \right)} }} = \frac{1}{2}\ln \frac{{1 - {\varepsilon _t}}}{{{\varepsilon _t}}}$ （14）

由此，便得到了基学习器的权值公式——式（14）。

其中， ${{\varepsilon _t}}$ 是分类误差率：

${\varepsilon _t} = \frac{{\sum\limits_{i = 1}^m {{{\overline w }_{ti}}I\left( {{h_t}\left( {{x_i}} \right) \ne {y_i}} \right)} }}{{\sum\limits_{i = 1}^m {{{\overline w }_{ti}}} }} = \sum\limits_{i = 1}^m {{w_{ti}}I\left( {{h_t}\left( {{x_i}} \right) \ne {y_i}} \right)}$ （15）

最后来看每一轮样本权值的更新，由 ${\ overline w _ {ti}} = \ exp \ left [{ - {y_i} {H_ {t - 1}} \ left（x \ right）} \ right]$ 和式（7）可以得到：

${\overline w _{t + 1,i}} = {\overline w _{ti}}\exp \left[ { - {y_i}{\alpha _t}{h_t}\left( {{x_i}} \right)} \right]$ （16）

在右边除以一个规范化因子，便可得到样本分布更新公式。

5. AdaBoost回归算法描述

输入：训练集 $D = \left\{ \left( x _ { i } , y _ { i } \right) \right\} _ { i = 1 } ^ { m }$ ，其中 $x _ { i } \in \chi \subseteq R ^ { n }$ ， $y _ { i } \in \mathcal { Y }$ ；基学习算法 $\mathfrak {L}$ ；基学习器个数 $Ť$ 。