集成学习：Bagging和Boosting (AdaBoost)

作者: jieyao | 来源:发表于2020-02-07 08:49 被阅读0次

05 集成学习 - Boosting - GBDT初探
集成学习：Bagging和Boosting (AdaBoost)
《统计学习方法》之随机森林Random Forest
Ensemble
机器学习-集成学习
CV-模型集成
【集成学习】boosting-bagging-random fo
随机森林：这或许是集成学习中最经典的一个 Bagging 算法了
Boost-GBDT
adaboost、adaboost.m1、adaboost.m2

当我们想要购买一个电脑时，我们不会仅仅听信销售员的一面之词就购买，因为一个人的意见是比较主观的，但是如果询问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

05 集成学习 - Boosting - GBDT初探
04 集成学习 - Boosting - AdaBoost算法构建回顾：1、Bagging-随机森林是一个并行模...
集成学习：Bagging和Boosting (AdaBoost)
当我们想要购买一个电脑时，我们不会仅仅听信销售员的一面之词就购买，因为一个人的意见是比较主观的，但是如果询问5个人...
《统计学习方法》之随机森林Random Forest
1. Bagging和Boosting 在集成学习方法中，Bagging和Boosting是具有代表性的两大方法，...
Ensemble
集成学习（ensemble learning）：Stacking，boosting，bagging（bootstr...
机器学习-集成学习
outline 集成学习 Boosting Bagging 随机森林结合策略 Stacking 集成学习(ens...
CV-模型集成
集成学习方法集成学习能够提高预测精度，常见的集成学习方法有stacking、bagging和boosting，同...
【集成学习】boosting-bagging-random fo
集成学习中三个著名的算法boosting、bagging和random forest. bagging算法使用了重...
随机森林：这或许是集成学习中最经典的一个 Bagging 算法了
在集成学习概述中已经知道了常用的集成算法有两种：Bagging 和 Boosting。而在 Bagging 中，随...
Boost-GBDT
GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost...
adaboost、adaboost.m1、adaboost.m2
集成学习常见的两种集成方案为bagging和boosting，其中bagging是一种基于投票的并行方案，boos...

集成学习：Bagging和Boosting (AdaBoost)

1. 集成学习Ensemble learning

2. Bagging

3. Boosting

Bagging 和Boosting的区别

4. Bias 和 Variance 方差

5. AdaBoost

指数损失函数Exponential loss function

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

Reference

相关文章

05 集成学习 - Boosting - GBDT初探

集成学习：Bagging和Boosting (AdaBoost)

《统计学习方法》之随机森林Random Forest

Ensemble

机器学习-集成学习

CV-模型集成

【集成学习】boosting-bagging-random fo

随机森林：这或许是集成学习中最经典的一个 Bagging 算法了

Boost-GBDT

adaboost、adaboost.m1、adaboost.m2

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读