以下内容选自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的方式来获得一定随机性的样本，同时对于聚合的方法，分类问题可以采用投票，回归问题可以采用平均。
因为采用了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对特征也进行了随机的选择
VR-Tree模型是随机森林的一个变种，它在每一步加入了一个概率选择的过程，以一定概率随机划分节点
Further Readings
随机树的集成学习模型还可以做密度估计和异常检测等问题，此处不具体展开了。