集成学习（3）boosting代表——Adaboost

作者: 蛋仔鱼丸 | 来源:发表于2020-07-01 22:04 被阅读0次

1 Adaboost原理

2.boosting：针对不独立的同质弱学习器。它以一种高度自适应的方法顺序地学习这些弱学习器（每个基础模型都依赖于前面的模型），并按照某种确定性的策略将它们组合起来。

自适应提升算法Adaboost（Adaptive Boosting）是boosting集成学习的入门必备算法，在集成学习（1）模型误差与集成学习中我们已经展示了boosting的流程，Adaboost就是一个完美符合其流程的算法。因此我们本篇就主要说下Adaboost的相关内容。

1.1 从boosting到Adaboost

我们说过，boosting的思想是：先从初始训练集训练出一个弱学习器，再根据其表现对训练样本分布进行调整，使得此弱学习器预测错误的训练样本在接下来的训练中受到更多关注，然后如此迭代进行训练出更多的弱学习器，最后将多个弱学习器通过结合策略进行集成，得到强学习器。Adaboost也是一样的，既然如此，根据上面这个思想就能总结出来我们要实现Adaboost需要解决的三个问题：

使用什么基学习器？
根据基学习器表现，怎样调整样本分布使得错误样本更受关注？
怎么将多个弱学习器进行集成，即结合策略是什么？

我们来以二分类问题为例回答这三个问题，回答完相信大家就能实现一个解决二分类问题的Adaboost了。

（1）使用什么基学习器？

使用什么基学习器（弱学习器，是不是全称“弱基学习器”哈哈哈）得看模型的功能来定，我们知道，boosting能够减少bias，而不会减少方差variance，因此一般采用高偏差低方差的算法作为基学习器，所以满足这个条件的都可以，实际上常用决策树桩（深度为1的决策树）来作为弱学习器，这个深度的决策树当然方差很小，这也是Adaboost不容易虽然不会减少模型的方差，但也一般不会过拟合的原因，如下图，在scikit-learn/Adaboost中默认的基学习器就是决策树桩：

当然也可以使用别的模型，像CART、NN之类的都可以用，别让基学习器本身就过拟合了就好。

（2）怎样调整样本分布？

目标是根据当前基学习器的表现，把预测错误的样本权重放大，使得这些样本点在后面的弱学习器中得到更多的重视，所以我们可以考虑根据预测结果给样本加权，怎么加权呢？我们考虑实现这样两个方面的功能：

预测正确的样本，权重减小，预测错误的样本，权重增大；
预测能力强的模型，其权重增大 / 减小幅度大（因为被比较强的学习器预测错误的样本说明其更容易出错），预测能力弱的模型，其权重增大 / 减小幅度小。

假设我们要解决一个二分类问题，弱学习器 $m$ 的预测能力为 $\alpha_m$ ，权重为 $w_m$ ，其对样本点 $i$ 预测结果为 $\hat{y}_i$ ，可用下式实现每个样本点的权重调整功能：

$w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_i\hat{y}_i )$

其中， $Z_m$ 是规范化因子，保证权重小于1，且权重之和为1：

$Z_m=\sum_{i=1}^N w_{mi}exp(-\alpha_my_i\hat{y}_i )$

对于分类正确的样本， $exp(-\alpha_my_i\hat{y}_i )<1$ ，分类错误的样本 $exp(-\alpha_my_i\hat{y}_i )>1$ ，这使得预测正确的样本，权重减小，预测错误的样本，权重增大；同时，因为弱学习器 $m$ 的预测能力 $\alpha_m$ 在指数上， $\alpha_m$ 越大则权重增大 / 减小幅度大，完美解决了我们对样本权重调整的需求。维基百科对adaptive 的解释：

AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers.

（3）怎么将多个弱学习器进行集成？

对于多个模型的集成，最容易想到的就是让他们投票，不过我们Adaboost中的弱学习器们能力强弱不一，想要预测能力强的集成模型，显然，我们需要更相信那些能力强的学习器，我们可以用弱学习器的预测能力 $\alpha_m$ 来作为其权重，这样能力强的就会起到更大的作用，那么预测能力 $\alpha_m$ 怎么得到呢，可以通过误差率来计算，误差越小的预测能力越强，对于二分类问题来说，错误率和预测能力 $\alpha_m$ 可由下式计算：

$e_m = P(\hat{y}_i \neq y_i) = \sum\limits_{i=1}^{N}w_{mi}I(\hat{y}_i \neq y_i)$

$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$

至此，要实现Adaboost的三个问题就解决了，我们可以着手来实现一个二分类Adaboost了。

1.2 二分类AdaBoost算法流程

输入：样本集 $T=\{(x_1,y_1),(x_2,y_2), ...(x_N,y_N)\}$ ，弱学习器（默认决策树桩）, 迭代次数 $M$ ；
输出：集成的强分类器 $f(x)$ 。

初始化样本集权重为

$D_1 = (w_{11}, w_{12}, ...w_{1N}) ;\;\; w_{1i}=\frac{1}{N};\;\; i =1,2...N$

对于 $m=1,2，...,M:$

使用具有权重 $D_m$ 的样本集来训练数据，得到弱分类器 $G_m(x)$ ；

计算弱分类器 $G_m(x)$ 的分类误差率：

$e_m = P(G_m(x_i) \neq y_i) = \sum\limits_{i=1}^{N}w_{ki}I\{G_m(x_i) \neq y_i\}$

计算弱分类器 $G_m(x)$ 的系数

$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$

更新样本集的权重分布，其中 $Z_m$ 是规范化因子：

$w_{m+1,i} = \frac{w_{mi}}{Z_m}exp[-\alpha_my_iG_m(x_i)] \;\; i =1,2,...N$

$Z_m=\sum_{i=1}^N w_{mi}exp[-\alpha_my_iG_m(x_i)]$

构建最终分类器为：

$G(x)=sign(\sum_{m=1}^M α_mG_m(x))=sign(f_M(x))$

可将上述流程描述为下图，方便记忆和理解：

二分类Adaboost流程图

1.3 多分类AdaBoost

以上是二分类Adaboost的流程，如果不用OvO、OvM之类的策略，Adaboost能处理多分类问题吗？其基学习器决策树都可以，那它肯定也是可以的。多分类Adaboost的原理和二分类差不多，区别是二分类要求基学习器的错误率 $e_m>0.5$ ，这在多分类显然就不适用了，比如Adaboost SAMME算法，它对于基学习器的错误率的要求同样是要低于猜测，假设类别数为 $K$ ，瞎猜的正确率就是 $1/K$ ，则有：

$err < \frac{K-1}{K}$

因此对于瞎猜的结果，错误率是正确率的 $K-1$ 倍，设计一个弱分类器的权重系数计算方法：

$\alpha_m=\log \frac{(1-e_m)(K-1)}{e_m} =\log \frac{1-e_m}{e_m} +\log (K-1)$

再把最后的结合策略中的 $sign$ 函数变成 $max$ 函数，取最大值就可以完成多分类任务了：

$G(x)=\arg \max_k(\sum_{m=1}^M α_mI\{G_m(x)=k\})$

1.4 AdaBoost回归流程

除了分类问题外，AdaBoost也可以用来做回归，根据误差情况更新权重这种事情，分类能做到，回归也可以做到，其区别就是计算误差的方式不同，流程如下：

输入：训练数据集 $T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\}$ ，迭代次数M；
输出：回归器 $G(x)$

初始化训练数据的权值分布
$D_1 = (w_{11}, w_{12}, ...w_{1N}) ;\;\; w_{1i}=\frac{1}{N};\;\; i =1,2...N$

对于 $m=1,2，...,M:$

使用具有权重 $D_m$ 的样本集来训练数据，得到弱分类器 $G_m(x)$ ；

计算弱分类器 $G_m(x)$ 的分类误差率：
$E_m=max\left | y_i-G_m(x_i) \right |\quad i=1,2,...,N$

$e_{mi}=\frac{\left ( y_i-G_m(x_i) \right )^2}{E_m^2}$

$e_m=\sum_{i=1}^Nw_{mi}e_{mi}$

计算弱分类器 $G_m(x)$ 的系数

$\alpha_m=\frac{e_m}{1-e_m}$

更新样本集的权重分布，其中 $Z_m$ 是规范化因子，因为 $0\leq\alpha_m\leq1$ ，所以 $1-e_{mi}$ 表示错误率越高权重越大：

$w_{m+1,i}=\frac{w_{mi}}{Z_m}\alpha_m^{1-e_{mi}}$

$Z_k=\sum_{i=1}^{N}w_{ki}\alpha_k^{1-e_{ki}}$

构建最终分类器为：

$G(x)=G_m^*(x)$

其中， $G_m^*(x)$ 是所有 $ln\frac{1}{\alpha_m}, m=1,2,....M$ 的中位数所对应的弱学习器。

到这里相信大家就已经会用Adaboost了，下面主要来分析Adaboost为什么好。

2 AdaBoost算法为什么有效

我们上面对Adaboost的描述，似乎只是从逻辑上解释了其各种处理的优点，告诉大家它是好的，能在学习过程中不断减少训练误差，即在训练数据上的分类误差率，因此能够降低偏差bias，那么能不能用数学的语言来更严谨的说明Adaboost的这一优势呢？

2.1 训练误差分析

我们最终的到的集成模型为： $G(x)=sign(\sum_{m=1}^M α_mG_m(x))=sign(f_M(x))$ ，有AdaBoost的训练误差界定理：

定理1（AdaBoost的训练误差界）： $N$ 为样本数，AdaBoost算法最终分类器的训练误差界为：

$\frac{1}{N} \sum_{i=1}^N I(G(x_i) \neq y_i) \leq \frac{1}{N} \sum_{i=1}^N exp( - y_i f_M(x_i)) = \prod_{m=1}^M Z_m$

证明：

$I(G(x_i) \neq y_i) \leq exp( - y_i f_M(x_i))$ 是显然的，因为分类正确时 $exp( - y_i f_M(x_i))>0=I(G(x_i) \neq y_i)$ ，分类错误时 $exp( - y_i f_M(x_i))>1=I(G(x_i) \neq y_i)$ 。

至于 $\frac{1}{N} \sum_{i=1}^N exp( - y_i f_M(x_i)) = \prod_{m=1}^M Z_m$ ，主要用到：

$Z_m w_{m+1,i} = w_{mi} exp[-\alpha_ky_iG_m(x_i)]$

具体推导就不写了，看《统计学习方法》即可，不是很难理解。

定理2（二分类AdaBoost的训练误差界）： AdaBoost算法最终分类器的训练误差界为：

证明：

不等式由 $e^x$ 和 $\sqrt{1-x}$ 在 $x=0$ 处的泰勒展开式证明。

推论：综合前面两个定理，如果存在 $\gamma >0$ ，对所有m都有 $\gamma_m >\gamma$ ，则有最终分类器的分类误差率：：

结论：这表明在此条件下，随着基学习器数目M越来越大，AdaBoost的训练误差是以指数速率下降的。

本小节内容来自《统计学习方法》

2.2 加法模型角度理解

我们还可以把Adaboost视为加法模型来进行解释。加法模型的相关内容可以看下广义加法模型（Generalized additive model）- 维基百科，其优点就是拟合能力更强，加法模型的形式为：

$f(x)=\sum_{m=1}^{M} \beta_{m}b(x;\gamma_m)$

式中， $b(x;\gamma_m)$ 为基函数， $\beta_{m}$ 为基函数的系数，显然我们Adaboost模型中 $f_M(x)=\sum_{m=1}^M α_mG_m(x)$ 就是一个加法模型的形式。

显然一个加法模型可以写成：

$f(x)=\sum_{m=1}^{M-1} \beta_{m}b(x;\gamma_m)+\beta_{M}b(x;\gamma_M)$

因此Adaboost模型：

$f_M(x)=f_{M-1}(x)+α_MG_M(x)$

在给定训练数据及损失函数 $L(y,f(x))$ 的条件下，学习加法模型成为一个极小化问题：

$\arg_{\beta_{m},\gamma_{m}}\min\sum_{i=1}^{N}L(y_i,\sum_{m=1}^{M}\beta_{m}b(x_i;\gamma_{m}))$

对于二分类Adaboost，我们将损失函数定义为指数损失函数：

$L(y,f(x))=\sum_{i=1}^N exp[-y_if_M(x_i)]$

极小化损失函数：

$\arg\min\sum_{i=1}^{N}exp[-y_if_M(x_i)]=\arg\min_{α_M,G_M}\sum_{i=1}^{N}exp[-y_i(f_{M-1}(x_i)+α_MG_M(x_i))]$

这是前向分步算法的思想，一步一步的减小损失函数，每增加一个基学习器，都通过极小化损失函数来使得损失减少，可以理解成一种贪心的思路。

$\begin{align} L(y,f(x))&=\sum_{i=1}^{N}\exp[-y_{i}(f_{M-1}(x_i)+α_MG_M(x_i))]\\ &=\sum_{i=1}^{N}\exp[-y_{i}f_{M-1}(x_i)]\cdot\exp[-y_{i}α_MG_M(x_i)]\\ &=\sum_{i=1}^{N}\bar{w}_{Mi}\exp[-y_{i}α_MG_M(x_i)] \end{align}$

$\bar{w}_{Mi}=\exp[-y_{i}f_{M-1}(x_i)]$ ，它的值不依赖于 $α_M,G_M$ ，与最小化无关。上式中， $α_M,G_M$ 存在耦合关系，在不确定 $G_M$ 的形式时无法直接用导数求极值，因为 $y_{i}G_M(x_i)$ 只能是 $+1$ 或 $-1$ ，所以可以将上式转化为：

$L(y,f(x))=\sum_{y_i=G_M(x_i)} \bar{w}_{Mi}e^{-α_M}+\sum_{y_i\neq G_M(x_i)} \bar{w}_{Mi}e^{α_M}$

$=(e^{α_M}-e^{-α_M})\sum_{i=1}^{N}\bar{w}_{Mi}I\{G_M(x_i)\neq_{}y_{i}\}+e^{-α_M}\sum_{i=1}^{N}\bar{w}_{Mi}$

所以：

$α_M^*,G_M^*=\arg\min_{α_M,G_M}[(e^{α_M}-e^{-α_M})\sum_{i=1}^{N}\bar{w}_{Mi}I\{G_M(x_i)\neq_{}y_{i}\}+e^{-α_M}\sum_{i=1}^{N}\bar{w}_{Mi}]$

先确定 $G_M^*$ ，显然 $α_M>0$ 时，使损失最小的 $G_M$ 就是错误率最小的 $G_M$ ，可得：

$G_M^*(x) = arg\min_{G_M}\sum\limits_{i=1}^{N}\bar{w}_{Mi}I\{G_M(x_i)\neq_{}y_{i}\}$

将 $G_M^*$ 带入损失函数，并对 $α_M$ 求导求极值，可得：

$\alpha_M = \frac{1}{2}log\frac{1-e_m}{e_m}$

式中， $e_m$ 即为基学习器的错误率：

$e_k = \frac{\sum\limits_{i=1}^{N}\bar{w}_{Mi}I(y_i \neq G_M(x_i))}{\sum\limits_{i=1}^{N}\bar{w}_{Mi}} = \sum\limits_{i=1}^{N}\bar{w}_{Mi}I(y_i \neq G_M(x_i))$

还有一个重点是权重的更新，我们有： $\bar{w}_{Mi}=\exp[-y_{i}f_{M-1}(x_i)]$ ， $f_M(x)=f_{M-1}(x)+α_MG_M(x)$ ，很容易得到：

$w_{M+1,i}^{’} = w_{Mi}^{’}exp[-y_i\alpha_MG_M(x)]$

可以发现，以加法模型来理解的每一步更新的参数 $e_m，\alpha_M，w_{Mi}$ 都跟我们之前从boosting出发设计的方案是一样的（权值更新相差规范化因子，可视为等价），这就从加法模型的角度证明了Adaboost的特点是一步步的优化损失函数，是的偏差bias减小。

3 总结

Adaboost算法虽然实现起来不难，逻辑上也很好理解，但是要证明他的好处确实还挺麻烦的，不过证明一下咱们用起来也更踏实，下面来总结一下Adaboost的优缺点：

优点

预测能力强，准确度高，这是作为boosting算法的优势；
能做二分类、多分类也能做回归，且实现简单，易于理解；
选好基学习器，一般不会过拟合；

缺点

对异常值敏感，因为异常值容易出现预测错误，这样Adaboost会增大其权重，重点处理，影响较大。

主要参考
《机器学习》——周志华
《统计学习方法》——李航
Multi-class AdaBoost——Ji Zhu等

集成学习（3）boosting代表——Adaboost

1 Adaboost原理

1.1 从boosting到Adaboost

（1）使用什么基学习器？

（2）怎样调整样本分布？

（3）怎么将多个弱学习器进行集成？

1.2 二分类AdaBoost算法流程

1.3 多分类AdaBoost

1.4 AdaBoost回归流程

2 AdaBoost算法为什么有效

2.1 训练误差分析

2.2 加法模型角度理解

3 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

集成学习（3）boosting代表——Adaboost

1 Adaboost原理

1.1 从boosting到Adaboost

（1） 使用什么基学习器？

（2） 怎样调整样本分布？

（3） 怎么将多个弱学习器进行集成？

1.2 二分类AdaBoost算法流程

1.3 多分类AdaBoost

1.4 AdaBoost回归流程

2 AdaBoost算法为什么有效

2.1 训练误差分析

2.2 加法模型角度理解

3 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

（1）使用什么基学习器？

（2）怎样调整样本分布？

（3）怎么将多个弱学习器进行集成？