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

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等

最后编辑于：2020.07.08 10:58:51

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,509评论 6赞 504
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,806评论 3赞 394
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 163,875评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,441评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,488评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,365评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,190评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,062评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,500评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,706评论 3赞 335
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,834评论 1赞 347
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,559评论 5赞 345
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,167评论 3赞 328
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,779评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,912评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,958评论 2赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,779评论 2赞 354