集成学习：Bagging和Boosting (AdaBoost)

当我们想要购买一个电脑时，我们不会仅仅听信销售员的一面之词就购买，因为一个人的意见是比较主观的，但是如果询问5个人，例如同事或者你的朋友，甚至更多人，他们大多都推荐同款商品，那基本差不到哪去。机器学习中的集成学习也是类似的思路，它可以结合多种模型来提升整体的性能。

1. 集成学习Ensemble learning

集成学习通过构建并结合多个学习器machine来完成学习任务，有时也被称为多分类系统multi-classifier system、基于委员会的学习committee-based learning等。它由一系列的个体学习器组成individual learner或者称为基学习器based learner,再由不同的策略结合在一起，结合后常可获得比单一学习器更好的泛化性能。

弱学习器 Weak learner: 指其泛化性能略优于随机猜测的学习器 e.g. 二分类问题上精度略高于50%。

在集成学习中，很多时候使用弱学习器作为基学习器。

集成学习

集成学习方法大致可以分成两大类：

1. 个体学习器之间不存在强依赖关系，其代表为Bagging 和随机森林 Random Forest

2. 个体学习器之间存在强依赖关系，其代表为Boosting

2. Bagging

Wiki: Baggin 又名 Boostrap aggregating, 是机器学习中的一种击沉学习算法，它可与其他分类、回归算法结合，提高其准确率、稳定性的同时，通过降低结果的方差，避免过拟合的发生。

自助抽样法 Bootstrapping, 是一种从给定训练集中有放回的均匀抽样，也就是说，每当选中一个样本，它会重新放回到训练集中，可能会被重新抽到。一般子集的大小与原始集的大小相同。

一、 Bagging算法流程：

对于有m个样本的数据集（假设有T个基学习器）

1. 根据 Bootstrap方法重新采样

每次选取1个样本进入采样集，将其放回训练集，反复操作m次，得到一组样本集。因为我们需要训练T个基学习器，所以生成T个分别包含m个样本的数据集（当然样本数量也可以少于m）。注意，T个训练集之间是独立的。

取样

2. 基于每个数据集，训练一个基学习器（weak learner），训练过程同时运行，且彼此独立

3. 结合这些基学习器的学习结果，在结合过程中，

对于分类问题，Bagging通常使用投票法，如果投票结果一样，则随机选择一个

对于回归问题，则采用平均法，即平均多个模型结果

Bagging 过程（图片来源于机器之心）

3. Boosting

Boosting是另外一种集成学习方法，它可以将弱学习器通过加权和提升为强学习器。

$\hat{f}(\boldsymbol{x})=\sum_{i=1}^{N} \alpha_{i} \hat{h}_{i}(\boldsymbol{x})$ ， $\hat{h}_{i}(\boldsymbol{x})$ 代表每个弱学习器模型， $\alpha_{i}$ 是其对应模型的系数。

一、 Boosting算法流程：

1.先从初始训练集中训练出一个基学习器 $h_i(x)$ 与其系数 $\alpha_{i}$ ，再根据其表现对训练样本的权重 $w_{i}^{\mu}$ 进行调整

2. 基于调整后的训练样本训练下一个基学习器 $h_{i+1}(x)$ 与基学习器的系数 $\alpha_{i+1}$ ,并得到新的样本权重

3. 重复进行，直到训练完事先指定的值N

4. 最终将这N个基学习器进行加权结合

主流的Boosting 算法有：AdaBoost（Adaptive Boosting，自适应增强算法）。

（下面介绍的AdaBoost有助于更好地理解Boosting）

Bagging 和Boosting的区别

样本选择

Bagging: 训练集是从原始数据集中有放回地选取，每一轮得到的数据集是独立的。采用均匀取样，每个样本的权重都相等。

Boosting: 每一轮的数据集是不变的，但是数据对于的权重是变化的。通过错误率调整样本权重，错误率越高，权重越大。

基学习器

Bagging: 基学习器可以并行生成，所有基学习器的系数相等。

Boosting: 基学习器按顺序生成，是串行的，不同的基学习器有对应的系数，对于分类误差大的基学习器，具有越小的系数。

4. Bias 和 Variance 方差

Bagging

Bagging对数据重新采样，并训练不同的基学习器，最终结果是对这一系列的模型取平均。由于子样本的相似性，这些基学习器具有近似相等的bias和方差variance。每个子分布 $X_{i}$ 的bias为 $\mu = \mathbb{E}\left[X_{i}\right]$ ,方差为 $\sigma ^{2}$

则bagging后的整体bias： $\mathbb{E}\left[\hat{\mu}_{n}\right]=\mathbb{E}\left[\frac{1}{n} \sum_{i=1}^{n} X_{i}\right]=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}\left[X_{i}\right]=\frac{1}{n} \sum_{i=1}^{n} \mu=\mu$

Variance方差：

$\begin{aligned} Var=\mathbb{E}\left[\left(\hat{\mu}_{n}-\mu\right)^{2}\right] &=\frac{1}{n^{2}} \mathbb{E}\left[\left(\sum_{i=1}^{n}\left(X_{i}-\mu\right)\right)^{2}\right] \\ & =\frac{1}{n^{2}} \mathbb{E}\left[\sum_{i=1}^{n}\left(X_{i}-\mu\right)^{2}+\sum_{i=1}^{n} \sum_{j=1 \atop j \neq i}^{n}\left(X_{i}-\mu\right)\left(X_{j}-\mu\right)\right] \\ &=\frac{1}{n^{2}} \sum_{i=1}^{n}\left(\mathbb{E}\left[\left(X_{i}-\mu\right)^{2}\right]+\sum_{j=1 \atop j \neq i}^{n} \mathbb{E}\left[\left(X_{i}-\mu\right)(X_{j}-\mu) \right]\right) \\ & \end{aligned}$

令 $\rho=\mathbb{E}\left[\left(X_{i}-\mu\right)\left(X_{j}-\mu\right)\right] / \sigma^{2}$ ，可以认为是两两分布之间的相关性，则 $\begin{aligned} Var & =\frac{1}{n^{2}} \sum_{i=1}^{n}\left(\sigma^{2}+\sum_{j=1 \atop j \neq i}^{n} \sigma^{2}\rho\right) \\ &=\frac{1}{n^{2}} n (\sigma^{2}+(n-1)\rho\sigma^{2})=\rho\sigma^{2}+\frac{(1-\rho)\sigma^{2}}{n} \end{aligned}$

因为子分布 $X_{i}$ 相关性较少甚至彼此之间独立，即 $\rho$ 很小甚至趋近于0，所以方差趋近于 $\frac{1}{n}\sigma ^{2}$ 。这也说明，Bagging可以显著降低方差,尽管相对于子分布，整体的bias没什么变化。

（方差的推导参考以下公式）

Boosting

Boosting使用forward-stagewise这种贪心法来最小化损失函数。每一轮训练都是通过最小化误差来生成基学习器，模型的最终结果也必将获得较小的bias。由于每一轮的训练都是依赖于上一次的训练结果，子分布之间存在较强的关联关系，所以方差不能得到显著的降低。

5. AdaBoost

AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，是一种用于二分类的集成学习算法。它是自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

假如对于二分类任务，我们的有数据集 $\mathcal{D}=\left\{\left(\boldsymbol{x}^{\mu}, y^{\mu}\right) | \mu=1,2, \ldots, m\right\}$ 且 $y^{\mu} \in\{-1,1\}$

第i个弱分类器的预测结果为 $\hat{h}_{i}\left(\boldsymbol{x}^{\mu}\right) \in\{-1,1\}$

基学习器的线性组合为 $C_{n}(\boldsymbol{x})=\alpha_{1} \hat{h}_{1}(\boldsymbol{x})+\alpha_{2} \hat{h}_{2}(\boldsymbol{x})+\cdots+\alpha_{n} \hat{h}_{n}(\boldsymbol{x})$

指数损失函数Exponential loss function

它通过最小化指数损失来逐步学习

$min \sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu} C_{n}\left(\boldsymbol{x}^{\mu}\right)}$ ，其中 $y^{u}$ 为真实值， $C_{n}(x)$ 为预测结果。

从下图可以看出，当真实值与预测值同号时即预测正确，损失很小；异号时，损失值很大。

误差函数

基分类器的系数 $\alpha_{n}$

在每一轮训练中都依次加入一个新的弱分类器 $C_{n}(\boldsymbol{x})=C_{n-1}(\boldsymbol{x})+\alpha_{n} \hat{h}_{n}(\boldsymbol{x})$

令 $w_{n}^{\mu}=\mathrm{e}^{-y^{\mu} C_{n-1}\left(\boldsymbol{x}^{\mu}\right)}$ 且 $w_{1}^{\mu}=\frac{1}{m}$ ， $\mu$ 取决于样本数， $n$ 取决于迭代数，即基函数的数量

则损失函数可以化简为

$\begin{aligned} l=\left(\alpha_{n}\right) &=\sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu} C_{n}\left(\boldsymbol{x}^{\mu}\right)}=\sum_{\mu=1}^{m} \mathrm{e}^{-y^{\mu}\left(C_{n-1}\left(\boldsymbol{x}^{\mu}\right)+\alpha_{n} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)\right)} \\ &=\sum_{\mu=1}^{m} w_{n}^{\mu} \mathrm{e}^{-\alpha_{n} y^{\mu} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} \\ & = \sum_{\mu: \boldsymbol{y}^{\mu} \neq \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} ^{m} w_{n}^{\mu} e^{\alpha_{n} } + \sum_{\mu: \boldsymbol{y}^{\mu} = \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} ^{m} w_{n}^{\mu} e^{-\alpha_{n} } \end{aligned}$

$y^{\mu} , h_{n}\in\{-1,1\}$ ,分类正确时 $y^{\mu} \hat{h}_{n}=1$ ，即 $\mathrm{e}^{-\alpha_{n} y^{\mu} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}=e^{-\alpha_{n}}$ ；分类错误则为 $\mathrm{e}^{\alpha_{n} }$ 。用下图来解释则为 $3*\mathrm{e}^{-\alpha_{n} }+2*\mathrm{e}^{\alpha_{n} }$ （当然，请不要忽略权值w）

误差化简

为了最小化损失，对损失函数进行求导，并让其为0

$\frac{\partial l}{\partial \alpha_{n}}=\sum_{\mu: y^{\mu} \neq \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}^{\mu} w^{\mu}\mathrm{e}^{\alpha_{n}}-\sum_{\mu: y^{\mu}=\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)} w^{\mu}\mathrm{e}^{-\alpha_{n}}=0$ 可得 $\alpha_{n}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)$

每一轮的误差为 $e_{n}= \sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}$ , 则 $\alpha_{n}=\frac{1}{2} \log \frac{ 1-e_{n}}{ e_{n}}$

AdaBoost算法步骤：

1. 初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：1/m, 即 $D_{1}(x)=\frac{1}{m}$ , $D_{1}$ 有m个样本，每个的权值都为1/m

for n=1,2,...,N do

2. 基于具有权值分布 $D_{n}$ 的训练数据集进行训练，计算误差（选择最小的），从而得到基学习器

$e_{n}= \sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}$

4. 计算基分类器的系数，更新模型

$\alpha_{n}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)=\frac{1}{2} \log \frac{ 1-e_{n}}{ e_{n}}$

5. 更新训练数据集的权值分布

$w_{n+1}^{\mu}=\frac{w_{n}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{n} \hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}}{Z_{n}}$ ，即 $D_{n+1} = \left\{ w_{n+1}^{1}, w_{n+1}^{2}.., w_{n+1}^{m}\right\}$

其中， $Z_{n}=\sum_{\mu=1}^{m} w_{n+1}^{\mu}$ ,是一个规范化因子，来确保 $D_{n+1}$ 是一个分布，即确保权值<=1

6. 得到强分类器

$H(x)=sign(\sum\nolimits_{n=1}^N \alpha_{n}h_{n}(x) )$

AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，它不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱，但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。

题目

原始数据

由于以上的数据可以分成{0 1 2},{3 4 5},{6 7 8},{9}这几类,所以根据主观的感觉，数据的分隔点分别为2.5、5.5、8.5

1. 初始化权值w1=0.1 $D1=\left\{ 0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1 \right\}$

2. 迭代训练弱分类器

第1次迭代：

（1）阈值T=2.5时，误差率为0.3（x>2.5，取值-1，此时{6,7,8}分类错误）

阈值T=5.5时，误差率为0.4（x>5.5，取值-1，此时{0,1,2,9}分类错误）

阈值T=8.5时，误差率为0.3（x>8.5，取值-1，此时{3,4,5}分类错误）

最小的阈值为0.3，分别为T=2.5 和T=8.5，随机取T=2.5，此时e=0.3, 第一个基分类器为 $h_{1}(x)=\left\{\begin{array}{ll}{1,} & {x<2.5} \\ {-1,} & {x>2.5}\end{array}\right.$

（2）计算第一个基分类器的系数

$\alpha_{1}=\frac{1}{2} \log \left(\frac{\sum_{\mu: y^{\mu} =\hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}{\sum_{\mu: y^{\mu}\neq\hat{h}_{n}\left(\boldsymbol{x}^{\mu}\right)}w^{\mu}}\right)= \frac{1}{2} \log \frac{1-e}{e} = 0.4236$

(3)计算权值 $w_{2}^{\mu}=\frac{w_{1}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{1} \hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)}}{Z_{1}}$

错误的分类，第7个数据即 x=6,它新的权值为 $w_{2,7}^{\mu}=w_{1,7}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{1} \hat{h}_{1}\left(\boldsymbol{x}^{\mu}\right)} = w_{1,6}^{\mu} \mathrm{e}^{\alpha_{1}}$

正确的分类x=1, $w_{2,2}^{\mu}=w_{1,2}^{\mu} \mathrm{e}^{-\alpha_{1}}$

对他们进行标准化，即把每个新的w除以 $Z_{1}$ , $Z_{1}=\sum_{1}^{10} w_{2,i} ^{\mu}$ ,可得

$w_{2,7}^{\mu}=0.1* \mathrm{e}^{\alpha_{1}}/Z_{1}=0.1666$ , $w_{2,2}^{\mu}=0.1* \mathrm{e}^{-\alpha_{1}}/Z_{1}=0.0715$

$D2=\left\{ 0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,\underline{ 0.1666,0.1666,0.1666},0.0715 \right\}$

第2次迭代：

（1）阈值T=2.5时，误差率为0.1666*3（x>2.5，取值-1，此时{6,7,8}分类错误）

阈值T=5.5时，误差率为0.0715*4（x>5.5，取值-1，此时{0,1,2,9}分类错误）

阈值T=8.5时，误差率为0.0715*3（x>8.5，取值-1，此时{3,4,5}分类错误）

选取最小的阈值T=8.5，e=0.0715*3, 第2个基分类器为 $h_{2}(x)=\left\{\begin{array}{ll}{1,} & {x<8.5} \\ {-1,} & {x>8.5}\end{array}\right.$

（2）计算第2个基分类器的系数 $\alpha_{2}=\frac{1}{2} \log \frac{ 1-e_{2}}{ e_{2}} = 0.6496$

（3）计算权值

根据公式 $w_{3}^{\mu}=\frac{ w_{2}^{\mu} \mathrm{e}^{-y^{\mu} \alpha_{2} \hat{h}_{2}\left(\boldsymbol{x}^{\mu}\right)}} {Z_{2}}$ $Z_{2}=\sum_{i=1}^{10} w_{3,i} ^{\mu}$ ，可得 $D3=\left\{ 0.0455, 0.0455, 0.0455,\underline{ 0.1666,0.1666,0.1666},0.1060, 0.1060, 0.1060, 0.0455 \right\}$ ,可见被错误分类的权值会被提高

第3次迭代：

（1）阈值T=2.5时，误差率为0.1065*3（x>2.5，取值-1，此时{6,7,8}分类错误）

阈值T=5.5时，误差率为0.0455*4（x>5.5，取值-1，此时{0,1,2,9}分类错误）

阈值T=8.5时，误差率为0.1667*3（x>8.5，取值-1，此时{3,4,5}分类错误）

选取最小的阈值T=5.5，e=0.0455*4, 第3个基分类器为 $h_{3}(x)=\left\{\begin{array}{ll}{1,} & {x<5.5} \\ {-1,} & {x>5.5}\end{array}\right.$

（2）计算第3个基分类器的系数 $\alpha_{2}=\frac{1}{2} \log \frac{ 1-e_{3}}{ e_{3}} = 0.7514$

（3）计算权值,可得新的样本分布如下

$D4=\left\{ \underline{0.125, 0.125, 0.125}, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, \underline{0.125} \right\}$

3. 合并得到强分类器 $H3(x)=0.4236 h1(x) + 0.6496h2(x)+0.7514h3(x)$ , 至此，整个训练过程结束。

Reference

https://www.jiqizhixin.com/articles/2018-07-28-3

https://blog.csdn.net/v_JULY_v/article/details/40718799

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