Bagging and Boosting

Bagging (Bootstrap aggregating) 和 Boosting 是两种集成方法 (ensemble methods)。

所谓的集成方法就是秉承着“三个臭皮匠胜于诸葛亮”的思想，通过组合多个单一模型得到强大的整体性能。

这里边就有两个问题，单一模型该如何训练？如何整合其各自的输出？

Bagging

训练

Bagging方法中每个单一模型（ $h_i$ ）的训练是平行进行的。

每个单一模型的训练集（ $S_i$ ）大小相同但内容各不相同，均是通过有放回地从原训练集中随机抽取若干训练实例得到的。

整合

投票或取平均。

好处

假设整合后的系统 $h = \frac{1}{m}\sum_{i=1}^mh_i$ ，且各单一模型相互独立（由于训练集容量有限，实际上各模型的训练集存在相似性，不能说是完全无关的），由偏差和方差的另一种解释，我们知道模型的泛化能力受到方差 $\text{variance} = E[h^2]-E[h]^2$ 和偏差 $\text{bias} = (E[f]-E[h])^2$ 的限制。

首先考察方差：

$\begin{split} E[h^2]-E[h]^2 &= E[(h-E[h])^2] \\ &= E[\left(\frac{1}{m}\sum_{i=1}^mh_i - E[\frac{1}{m}\sum_{i=1}^mh_i]\right)^2]\\ & = E[\left(\frac{1}{m}\sum_{i=1}^mh_i - \frac{1}{m}\sum_{i=1}^mE[h_i]\right)^2]\\ & = \frac{1}{m^2}E[\left(\sum_{i=1}^m(h_i-E[h_i])\right)^2]\\ & = \frac{1}{m^2}\sum_{i=1}^mE[h_i-E(h_i)^2]\\ & = \frac{1}{m} \left(\frac{1}{m}\sum_{i=1}^mE[h_i-E(h_i)^2]\right)\\ & = \frac{\text{the average variance of single models}}{m} \end{split}$

可见Bagging方法能线性地减小方差（在单一模型互不相关的情况下）。

再考察偏差：

$\begin{split} (E[f] - E[h])^2 &= (E[f] - \frac{1}{m}\sum_{i=1}^mE[h_i])^2 \\ & =\left( \frac{1}{m}\sum_{i=1}^m(E[f] -E[h_i]) \right)^2 \\ \text{from Jensen's inequality }& \le \frac{1}{m}\sum_{i=1}^m(E[f]-E[h_i])^2\\ & = \text{the average bias of single model} \end{split}$

可见Bagging并不能保证减小偏差。

Boosting

训练

在同一训练集上依次训练多个模型。

得到第 $i$ 个模型 $h_i$ 后，对训练集中 $h_i$ 预测错误的样例，增加其权重；反之减低其权重。

整合

求（带权）平均

AdaBoost

boosting中有一种能自适应地调节样例权重以及最终模型权重的方法：AdaBoost。