Bagging Predictors论文简介及其笔记| 论文笔记好用的论文笔记工具

Bagging Predictors

小木 Machine Learning 1996-07 3002 2017/02/06 09:58:08

#### 目录

[toc]

bagging是“**b**ootstrap **agg**regat**ing**”的首字母缩写。是集成学习的一种思想。这篇文章的作者是Leo Breiman，是bagging方法的原始论文。在这里我们记录一下这篇文章的主要思想。bagging方法的基本原理很简单，就是对m个来自同一个任务的数据集，对m个预测方法取平均值或者投票得到结果（对于没有m个数据集合来说，可以采用自主抽样的方法bootstrap sampling得到）。

#### bagging基本原理
假设我们有个数据集合$\\{(y_n,x_n),n=1,...,N\\}$，其中y既可以是类标签（分类），也可以是数值（回归）。我们使用这些数据构造一个预测算法$\phi(x,\mathcal{L})$。现在，假设给定一个学习的集合$\\{\mathcal{L}\_k\\}$，由来自相同的潜在的分布$\mathcal{L}$的N个独立的观测值组成。bagging的任务是使用$\\{\mathcal{L}\_k\\}$得到一个预测方法，能比单一的预测器$\phi(x,\mathcal{L})$效果好（分类任务的模型是分类器，回归的方法叫做预测，这里使用预测器代表二者）。
bagging方法的基本思想很简单。当y是数值型（回归），我们使用多个预测方法的均值表示最终预测结果，即：
```math
\phi_A(x) = E_\mathcal{L}\phi(x,\mathcal{L})
```
这里公式左侧下表A表示Aggregating，是bagging的预测模型，右边的$E\_\mathcal{L}$表示$\mathcal{L}$的期望。如果y是类标签，那么bagging的预测结果通过所有分类器的投票结果决定。即当$N_j=nr\\{k;\phi(x,\mathcal{L}\_k=j)\\}$时候：
```math
\phi_A(x) = \text{argmax}_jN_j
```
实际中，如果我们只有一个学习集合$\mathcal{L}$，那么，我们可以模仿上述过程，通过从$\mathcal{L}$中有放回的重复抽样得到自助样本（bootstrap samples）$\\{\mathcal{L}^{(B)}\\}$，形成$\phi(x,\mathcal{L}^{(B)})$，如果y是数值型的，那么：
```math
\phi_B(x)=av_B\phi(x,\mathcal{L}^{(B)})
```
如果y是类标签，那么使用$\\{\phi(x,\mathcal{L}^{(B)})\\}$投票得到$\phi_B(x)$。上述过程就是bagging。简单来说，bagging就是把多个样本的预测结果结合起来得到一个集成的预测结果，集成过程就是使用均值或者投票。如果没有多个数据集，就从单一数据集中有放回地重复抽样。论文中，作者说，影响bagging效果的一个重要因素是预测器$\phi$的稳定性。当$\mathcal{L}$变动小，$\phi$变动也小的时候，bagging结果和原来的预测器结果类似，当较小的数据变动得到较大的$\phi$变动结果时，bagging方法冥想好于原来的方法。至于为什么这样，后面有解释。

#### 为什么bagging有效
作者从数学原理中证明了bagging的有效。我们也来简单解释一下。
##### 数值预测
通过前面的描述，我们知道，对于数值预测，我们的bagging算法结果是：
```math
\phi_A(x) = E_\mathcal{L}\phi(x,\mathcal{L})
```
其中x是输入值，y是预测结果，那么
```math
E_\mathcal{L}(y-\phi(x,\mathcal{L}))^{2}=y^2-2yE_\mathcal{L}\phi(x,\mathcal{L})+E_\mathcal{L}\phi(x,\mathcal{L})^2
```
我们知道，均值不等式$EZ^2 \geq (EZ)^2$，因此当$E\_\mathcal{L}\phi(x,\mathcal{L})=\phi_A(x)$时候，上式右侧最后一个元素大于等于$\phi_A(x)^2$，于是我们有：
```math
E_\mathcal{L}(y-\phi(x,\mathcal{L}))^2 \geq (y-\phi_A(x))^2
```
将二者两边同时积分掉x和y我们就可得到$\phi_A(x)$的均方根误差小于$\phi(x,\mathcal{L})$。结果提升多少取决于不等式的两边差值，即：
```math
[E_\mathcal{L}\phi(x,\mathcal{L})]^2 \leq E_{\mathcal{L}}\phi^2(x,\mathcal{L})
```
刚才说的，其它分类器的不稳定性的影响在这里看也是非常直观的。如果$\phi(x,\mathcal{L})$并不随着数据的变动变化比较大的话，那么上述不等式之间差就很小，因此bagging的效果就提升不明显了。反之则很明显。但最终，bagging总是好于之前的方法。对于重复抽样的结果也是一样，bagging的效果不仅取决与x，也取决于从$\mathcal{L}$中抽取的样本概率分布P。也就是说，$\phi_A=\phi_A(x,P)$，同时bagged估计也变成了如下形式：
```math
\phi_B(x)=\phi_A(x,P_\mathcal{L})
```
其中$P\_\mathcal{L}$是一个集中在1/N的分布，点是来自于$(y\_n,x\_n)\in \mathcal{L}$，在这里$P\_\mathcal{L}$是P的自助近似，bootstrap approximation）。

##### 标签预测
分类的目标是标签预测，一个分类器$\phi(x,\mathcal{L})$预测一个类标签$j \in {1,...,J}$可以表示如下：
```math
Q(j|x)=P(\phi(x,\mathcal{L})=j)
```
在这里，$Q(j|x)$可以描述为：在很多独立的重复学习集合（数据）$\mathcal{L}$中，$\phi$在输入值x的预测结果是标签j的相对频率是$Q(j|x)$。用P(j|x)表示x产生标签j的概率。那么分类器在x处产生正确的概率为：
```math
\sum_j Q(j|x)P(j|x)
```
那么所有正确的分类器是：
```math
r = \int [\sum_jQ(j|x)P(j|x)]P_X(dx)
```
这里$P_X(dx)$是x的概率分布。那么对于任意的$Q(j|x)$，我们有

```math
\sum_j Q(j|x)P(j|x) \leq \text{max}_jP(j|x)
```

赏

支付宝扫码打赏

如果文章对您有帮助，欢迎打赏鼓励作者