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

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