Bagging（随机森林）和Boosting（AdaBoost）

1. 什么是Bagging（随机森林）

Bagging的思想是均匀地、有放回地从大小为D的数据集采样出M个样本构成数据集，总共采样N次用于分别训练N个模型，在预测阶段使用这N个模型共同决定样本的分类或回归结果。在这里，随机森林是一个很好的例子。随机森林就是学习N棵决策树共同决定样本的预测结果。随机森林的随机体现在两点：
(1) 每棵决策树的训练样本是采用有放回的随机获取的。
(2) 每棵决策树在训练时，在选取特征和特征值对决策树进行划分时，首先随机选取$m$个特征，然后再从这$m$个特征中按照某种规则比如信息增益率或基尼系数或某种目标函数等等，选择最佳特征和特征值进行划分。

随机森林有一个特性，就是可以计算袋外错误率。什么是袋外错误率呢？对于每一棵决策树，使用有放回的随机获取训练样本，大约会有$\frac{1}{3}$的样本没有被采样到。反过来说，对于每一个样本，大约会有$\frac{1}{3}$棵决策树没有使用到这个样本进行训练，所以可以使用随机森林这$\frac{1}{3}$的决策树对这个样本进行预测。所有样本的预测错误率就可以称为袋外错误率。这个袋外错误率有什么用呢？首先，袋外错误率可以作为在验证集上的效果看待，所以可以决定每棵决策树的深度，对每棵决策树进行剪枝。其次，袋外错误率还可以评价特征的重要程度，对样本在某个特征处加上噪声，计算袋外错误率的变化，如果变化大说明这个特征很重要，否则说明这个特征重要性并不高。因为有这个袋外错误率，所以随机森林可以不用进行交叉验证。另外，随机森林在计算特征重要性时，除了可以使用袋外错误率，还可以使用基尼指数增益。

随机森林树的个数是否越多越好？首先随着树的个数增多，随机森林在训练时需要占用更多的资源，如果增加树的个数对提升模型效果作用不大，增加树的个数反而会不好。其次，随机森林引入随机抽样和随机抽列使模型鲁棒性更强，对异常点的敏感度减小，如果是树的个数很多，这种随机性反而会下降，使得模型容易过拟合，泛化性能下降。所以树的个数需要根据具体业务需求确定。

Bagging的作用主要是为了降低方差，降低方差的原理是利用对数据集抽样的独立性使得多个模型的方差约等于单个模型方差除以模型数量。Bagging要求模型的训练数据之间应该相互独立，但因为是在同一个有限的数据集上抽样，难免会存在一些相关性，所以随机森林并不是树越多越好，因为树越多，树之间的相关性就会越大。

2. 什么是Boosting（AdaBoost）

Boosting是一种提升的思想，是串行执行的，当前模型重视对前面模型的错误样本进行学习，最后将所有模型合在一起共同决定预测结果。在这里，AdaBoost是一个很好的例子。AdaBoost的算法思想是在当前轮学习中，增大错误样本的权重，从而使得下一轮学习更重视当前轮的错误样本。以二分类任务为例，首先第一步，数据集D含有N个样本，每个样本的权重为$w_i^1=\frac{1}{N}$。使用这N个样本学习得到第一个分类器$f_1$，该分类器的错误率为$\epsilon_1$，使用$\epsilon_1$计算可以得到$\alpha_1$：

$$\epsilon_1=\sum_i{w_iI(f_1(x_i)\ne y_i)}$$ $$\alpha_1=\frac{1}{2}\ln{\frac{1-\epsilon_1}{\epsilon_1}}$$

其中函数$f_1$表示将模型输出映射到分类结果，使用$\alpha_1$更新样本的权重，对于正确分类的样本，使用下式更新权重：

$$w_i^2=\frac{w_i^{1}e^{-\alpha_1}}{Z_1}$$

其中$Z_1$是归一化项，对于错误分类的样本，使用下式更新权重：

$$w_i^2=\frac{w_i^1e^{\alpha_1}}{Z_1}$$

总结一下就是：

$$w_i^2=\frac{w_i^1e^{-\alpha_1y_if_1(x_i)}}{Z_1}$$

这样就完成了第一轮的学习，接着进入第二轮的学习，由此类推，当学习了M个分类器后，使用下式组合M个分类器的结果：

$$F(x)=\sum_i{\alpha_if_i(x)}$$ $$G(x)=sign(F(x))$$

对于AdaBoost为什么这样计算各个分类器的权重与这样进行样本权重的更新，实际上这是由AdaBoost在处理二分类问题时最小化指数损失函数决定的。所以在使用AdaBoost处理多分类问题或回归问题时，使用其他类型的损失函数，需要针对最小化损失函数来决定各个学习器的权重与各个样本权重的更新方式。现在证明一下为什么AdaBoost这样计算分类器权重以及为什么样本权重是这样更新的。已知损失函数是指数损失函数，且AdaBoost是加法模型，所以有：

$$L=\sum_i{e^{-y_iF_m(x_i)}}$$ $$=\sum_i{e^{-y_iF_{m-1}(x_i)}e^{-y_i\alpha_mf_m(x_i)}}$$ $$=\sum_i{w_ie^{-y_i\alpha_mf_m(x_i)}}$$ $$=e^{-\alpha_m}\sum_iw_iI(y_i=f_m(x_i))+e^{\alpha_m}\sum_iw_iI(y_i\ne f_m(x_i))$$ $$=e^{-\alpha_m}\sum_iw_i+(e^{\alpha_m}-e^{-\alpha_m})\sum_iw_iI(y_i\ne f_m(x_i))$$

对$\alpha_m$求导并令导数为0，可以得到：

$$-e^{-\alpha_m}\sum_iw_i+(e^{\alpha_m}+e^{-\alpha_m})\sum_iw_iI(y_i\ne f_m(x_i))=0$$ $$==> -e^{-\alpha_m}\sum_i\frac{w_i}{Z}+(e^{\alpha_m}+e^{-\alpha_m})\sum_i\frac{w_i}{Z}I(y_i\ne f_m(x_i))=0$$

其中$Z$是归一化因子，这样可以得到：

$$-e^{-\alpha_m}+(e^{\alpha_m}+e^{-\alpha_m})\epsilon_m=0$$

可以求得：

$$\alpha_m=\frac{1}{2}\ln\frac{1-\epsilon_m}{\epsilon_m}$$

这样就求出来$\alpha_m$了，现在还需要求$w_i$：

$$w_{m,i}=e^{-y_iF_m(x_i)}=e^{-y_i\alpha_mf_m(x_i)}e^{-y_iF_{m-1}(x_i)}=e^{-y_i\alpha_mf_m(x_i)}w_{m-1,i}$$

这样就求出来$w_i$的更新方式了。

Boosting的主要作用是降低偏差，降低偏差的原理是使用加法模型，利用目标函数对加法模型的每个基模型求导并令梯度为零，使得每次添加一个模型都使目标函数达到当前加法模型的极小值。需要注意的是，每次添加模型，虽然都求得极小值，但极小值并不一定呈递减的关系，所以Boosting也不是越多基模型越好。Boosting在降低偏差的同时，可能会提升方差，Boosting的方差大小取决于基模型的方差大小，所以一般要求基模型是弱模型，因为弱模型的方差小。

3. 什么是Stacking

Stacking的思想是将一些模型的输出经过组合当作特征输入到另一些模型中学习，最终的输出作为预测结果。需要注意的是，是先使用数据训练好第一层的模型，然后再使用模型的输出作为输入训练第二层的模型，然后再训练完第二层的模型才能继续将输出作为输入送入下一层，每一层的模型是有顺序分开训练的，不是同时训练的。同时训练的应该将其看作同一个模型的不同层。