Bagging

以下内容选自Ensemble Methods Foundations and Algorithms (Zhihua Zhou) 。

Two Ensemble Paradigms

与Boosting相对的，就是Bagging方法，Boosting属于一种串行的集成方式，而Bagging是一种并行的集成方式。集成学习方法都用到了基学习器的独立性，Boosting串行的方式是通过自助(boost)的方式来降低残差，而Bagging则是通过结合独立的弱分类器来降低误差。我们定义基分类器$h_i(x)$ 的误差为 $$P(h_i(x)\neq f(x))=\epsilon$$ 结合$T$ 个基分类器 $$H(x)=sign(\sum^T_{i=1}h_i(x))$$ 根据Hoeffding Inequality，总体的泛化误差的upper bound为 $$P(H(x)\neq f(x))=\sum^{[T/2]}_{k=0}C^k_T(1-\epsilon)^k\epsilon^{T-k}\leq\exp(-\frac{1}{2}T(2\epsilon-1)^2)$$ 即随着$T$ 增大，泛化误差会趋近于$0$ 。但是实际中，我们并不能得到真正独立的基学习器，因为他们是通过同一个训练数据集得到的，较少独立性的基学习器可以通过随机的方式得到，这样的集成学习方式可以得到较好的泛化能力。

Bagging的另一个优势是可以并行训练，通过多进程加速训练过程。

Bagging

Bagging的名字来自于Bootstrap AGGregatING，正如这个模型的名字，Bagging的两个关键在于Bootstrap和aggregation。

Bagging采用了Bootstrap的方式来获得一定随机性的样本，同时对于聚合的方法，分类问题可以采用投票，回归问题可以采用平均。

1

因为采用了Bootstrap的方式，所以会有大于$36.8\%$ 的数据是不会被采到的，而这部分数据可以用作包外估计(out-of-bag estimation) $$H^{oob}(x)=\underset{y\in \mathcal{Y}}{\arg\max}\sum^T_{t=1}\mathbb{I}(h_t(x)=y)\cdot\mathbb{I}(x\notin \mathcal{D}_t)$$

$${err}^{oob}=\frac{1}{|\mathcal{D}|}\sum_{(x,y)\in\mathcal{D}}\mathbb{I}(H^{obb}(x)\neq y)$$

Theoretical Issues

Bagging可以有效减少方差，特别是对于不稳定的基学习器。 $$H(x)=\mathbb{E}_{\mathcal{D}_{bs}}[h(x)]$$ 其中$\mathcal{D}_{bs}$ 表示bootstrap的抽样分布，因为$(\mathbb{E}[X])^2\leq \mathbb{E}[X^2]$ 有 $$(f(x)-H(x))^2\leq\mathbb{E}_{\mathcal{D}_{bs}}[(f(x)-h(x))^2]$$ 因此，通过对两边积分，我们可以知道$H(x)$ 的均方误差会比所有$h(x)$ 的均方误差的平均值小，而且不同的程度依赖于下面这个不等式的不等程度 $$(\mathbb{E}_{\mathcal{D}_{bs}}[h(x)])^2\leq\mathbb{E}_{\mathcal{D}_{bs}}[h(x)^2]$$ 这说明了基分类器的instability的重要性，如果$h(x)$ 在Bootstrap的样本上差异不够大，那么最后的结合也不会产生很好的效果，但如果差异很大的话，结合带来的改善就会变得更多，这就是为什么Bagging对于unstable的弱分类器更有效并且能降低variance。

Random Tree Ensembles

随机森林算是Bagging模型的一个代表，不同点在于RF对特征也进行了随机的选择

2

VR-Tree模型是随机森林的一个变种，它在每一步加入了一个概率选择的过程，以一定概率随机划分节点

3

Further Readings

随机树的集成学习模型还可以做密度估计和异常检测等问题，此处不具体展开了。