Bagging vs Boosting

问题1：Bagging？

Bagging的名字由来是从Bootstrap来的，（B-ootstrap AGGregat-ING）意思是自助抽样集成。用Bootstrap的方式将训练集分成m个新的训练集，然后在每个新训练集上构建一个模型，各自不相干，最后预测时我们将这个m个模型的结果进行整合，得到最终结果。

• 分类问题，用投票方式整合；

• 回归问题，用求取均值方式整合。

子问题1.1 Bootstrap？

精髓在于：数据集大小为N，有放回的随机抽样N次，这样的过程重复m次，用于构成m个数据集。可以通过极限知，会有约36.8%的样本一次都没有被选中：

$$\mathop{lim}\limits_{n\to\infty} \big(\frac{N-1}{N}\big)^N = \frac{1}{e} = 36.8\%$$

好处在于：

对于样本比较少的时候，很有用。（如果换用train-test这种分割得到话，样本更小了，那么分布的bias会更大）

子问题1.2 Random Forest？

精髓在于：

1. 弱学习器定为了决策树（Decision Tree）的Bagging模型（分类模型）

2. 分裂的候选特征集并不是全集，而是在候选特征中随机抽样后，找最大增益的作为分裂点

3. 一定程度避免了过拟合：因为首先在数据采样时，就进行了随机采样；选择分裂点的时候，又引入了随机抽取一部分候选特征，进一步引入随机采样

问题3：Boosting？

弱学习器之间存在先后顺序，每个样本有权重，初始化时，每个样本的权重是相等的，训练过程中调整正确和错误样本的权重。同时，每个学习器的权重也是不一样的。

Boosting中，最重要的方法包括AdaBoost和GBDT。

子问题2.1 AdaBoost？

AdaBoost的训练过程：

1. 用全部数据训练第1个弱学习器，计算当前学习器的权重alpha，权重alpha计算公式如下：

   $$\varepsilon = \frac{未正确分类的样本数量}{所有样本数量}$$

   $$\alpha = \frac{1}{2}ln\bigg(\frac{1-\varepsilon}{\varepsilon}\bigg)$$
2. 将第1个学习器学错的样本加入到总样本中，训练第2个弱学习器，计算学习器的权重；

3. 将第1、2个学习期学错的样本加入到总样本，训练第3个弱学习器，计算学习器的权重；

模型的总结： AdaBoosting方式每次使用的是全部的样本，每轮训练改变样本的权重。下一轮训练的目标是找到一个函数f 来拟合上一轮的残差。当残差足够小或者达到设置的最大迭代次数则停止。

2个层级上的权重调整：

• 样本级的权重调整：Boosting会减小在上一轮训练正确的样本的权重，增大错误样本的权重。

• 模型级的权重调整：对于错误比较多的学习器会赋予一个较小的权重，错误比较少的学习器会赋予一个较大的权重。

问题3：Bagging与Boosting的区别？

1. 从样本角度：

   Bagging的每一轮次的数据集是有放回的随机选取（不是全集），各训练集之间独立，样本权重相同；

   Boosting的每一轮次的数据集是全集，样本权重不同（根据上一轮次训练集调整的）

2. 从学习器整合角度：

   Bagging每个学习器的权重是等权重的

   Boosting每个学习器的权重是由当前学习器的错误率决定的

3. 从并行角度：

   Bagging可以并行生成：各学习器相对独立，可独自运行

   Boosting只能顺序生成：因为后一个模型的需要前一个模型的结果

4. （重中之重）从偏差-方差角度：

子问题3.1 为什么bagging是减少方差，boosting是减少bias？

参考资料：https://www.zhihu.com/question/26760839/answer/40337791

• Bagging：由于有放回的随机选取，子数据集有相似性，Bagging后的bias与单个子模型的近似，不能显著降低bias；另一方面，若子模型独立，这时候可以显著降低variance，若子模型全部相同，variance不变，Bagging的模型介于完全独立和完全相同的中间（在Radom Forest中的特征候选是采样的），而且不同学习器的数据集也是采样的，不完全相同，因此是一定程度可以降低模型variance的。

• Boosting：从优化的角度看，后一棵树的输入是建立在上一棵树的输出上，使用的forward-stagewise的贪心思想，在sequential地最小化Loss，因此bias自然逐步降低；但是，因为树与树之间是强相关的，子模型之和显然并不能显著降低variance。