集成学习

1.导言

一个形象的比喻：“三个臭皮匠赛过诸葛亮！”
假设输入$\mathbf{x}$和输出$\mathbf{y}$之间的真实关系为：$\mathbf{y}=h(\mathbf{x})$.对于$\mathbf{M}$个不同的模型$f_1(\mathbf{x}),\cdots ,f_{\mathbf{M}}(\mathbf{x})$，每个模型的期望错误定义如下：
$$\begin{array}{rl}\mathcal{R}(f_m)& =E_{\mathbf{x}}\left[(f_m(\mathbf{x})-h(\mathbf{x}){)}^2\right]\\ & =E_{\mathbf{x}}\left[{ϵ}_m(\mathbf{x}{)}^2\right]\end{array}\text{\hspace{1em}(式1)}$$
其中，${ϵ}_m(\mathbf{x})=(f_m(\mathbf{x})-h(\mathbf{x}))$为模型$\mathbf{m}$在样本$\mathbf{x}$上的错误。
这样一来，所有模型的平均错误为：
$$\bar{\mathcal{R}}(f)=\frac{1}{\mathbf{M}}\sum _{m=1}^{\mathbf{M}}{E}_{\mathbf{x}}\left[{ϵ}_m(\mathbf{x}{)}^2\right]\text{\hspace{1em}(式2)}$$

集成学习（Ensemble Learning）是采取某种策略（比如：直接平均，加权平均）将多个模型集成起来，通过群体决策来提高准确率。集成学习首要的问题是如何集成多个模型。
最直接的策略是：直接平均，即通过“投票”。基于投票的集成模型$F(\mathbf{x})$定义为：
$$F(\mathbf{x})=\frac{1}{\mathbf{M}}\sum _{m=1}^{\mathbf{M}}{f}_m(\mathbf{x})\text{\hspace{1em}(式3)}$$
在这里，通过简单投票机制的集成模型$F(\mathbf{x})=\frac{1}{\mathbf{M}}{\sum }_{m=1}^{\mathbf{M}}{f}_m(\mathbf{x})$,$F(\mathbf{x})$的期望在：$\frac{1}{\mathbf{M}}\bar{\mathcal{R}}(f)$和$\bar{\mathcal{R}}(f)$之间。

【证明】：根据定义，集成模型的期望错误为：
$$\begin{array}{rl}\mathcal{R}(F)& =E_{\mathbf{x}}\left[(\frac{1}{\mathbf{M}}\sum _{m=1}^{\mathbf{M}}{f}_m(\mathbf{x})-h(\mathbf{x}){)}^2\right]\\ & =E_{\mathbf{x}}\left[(\frac{1}{\mathbf{M}}\sum _{m=1}^{\mathbf{M}}{ϵ}_m(\mathbf{x}){)}^2\right]\\ & =E_{\mathbf{x}}\left[\frac{1}{{\mathbf{M}}^2}\sum _{m=1}^{\mathbf{M}}\sum _{n=1}^{\mathbf{M}}{ϵ}_m(\mathbf{x}){ϵ}_n(\mathbf{x})\right]\\ & =\frac{1}{{\mathbf{M}}^2}\sum _{m=1}^{\mathbf{M}}\sum _{n=1}^{\mathbf{M}}{E}_{\mathbf{x}}\left[{ϵ}_m(\mathbf{x}){ϵ}_n(\mathbf{x})\right]\end{array}\text{\hspace{1em}(式4)}$$
其中，$E_{\mathbf{x}}\left[{ϵ}_m(\mathbf{x}){ϵ}_n(\mathbf{x})\right]$为两个不同模型错误的相关性。如果每一个模型的错误是不相关的，则有:
$$\forall m\ne n,E_{\mathbf{x}}\left[{ϵ}_m(\mathbf{x}){ϵ}_n(\mathbf{x})\right]=0\text{\hspace{1em}(式5)}$$
如果，每个模型的错误都是相同的，则:
$$\forall m\ne n,{ϵ}_m(\mathbf{x})={ϵ}_n(\mathbf{x})\text{\hspace{1em}(式6)}$$
且由于：$\forall m,{ϵ}_m(\mathbf{x})\ge 0$,于是得到：
$$\bar{\mathcal{R}}(f)\ge \mathcal{R}(f)\ge \frac{1}{\mathbf{M}}\bar{\mathcal{R}}(f)\text{\hspace{1em}(式7)}$$
也就是说：集成模型的期望错误大于等于所有模型的平均期望错误的$1/M$,小于等于所有模型的平均期望错误。

$⟹$为了得到更好的模型集成效果，则需要每个模型之间具备一定的差异性。且随着模型数量的增多，其错误率也会下降，最终趋近于0.

一个有效的集成学习模型要求各个基模型（弱分类器）之间的差异尽可能大，为了增加基模型之间的差异，可以采用Bagging和Boosting这两类方法。

2.Bagging类方法

Bagging类方法是通过随机构造训练样本，随机选取特征等方法来提高每个基模型之间的独立性，代表性方法有:Bagging和随机森林。
$\to Bagging$:（Bootstrap Aggregating）是通过不同模型的训练数据集的独立性来提高模型之间的独立性。在原始数据集上进行有放回的随机采样，得到$M$个比较小的训练集，并训练$M$个模型，然后通过投票的方法进行模型集成。
$\to$随机森林：（Random Forest）是在Bagging的基础上再引入了随机特征，进一步提高每个基模型之间的独立性。再随机森林中，每个基模型都是一棵决策树。

3.Boosting类方法

Boosting类方法，是按照一定顺序来先后训练不同的基模型，每个模型都针对前序模型的错误进行训练。根据前序模型的结果，来调整训练样本的权重，增加不同基模型之间的差异性。Boosting类方法的代表有：Adaboost方法。
$\to AdaBoost$:Boosting类的集成模型的目标是学习到一个加性模型，即:
$$F(\mathbf{x})=\sum _{m=1}^{\mathbf{M}}{\alpha }_m{f}_m(\mathbf{x})\text{\hspace{1em}(式8)}$$
其中，$f_m(\mathbf{x})$为弱分类器，或者基分类器。${\alpha }_m$为弱分类器的集成权重，$F(\mathbf{x})$就为强分类器。

Boosting类方法的关键：
怎样训练确定每一个弱分类器$f_m(\mathbf{x})$及其权重${\alpha }_{\mathbf{m}}$。做法为：采用迭代的方式来学习每一个弱分类器，也就是按照一定的顺序依次训练每一个弱分类器。具体为：”假设已经训练了$m$个弱分类器，再训练第$m+1$个弱分类器的时候，增加已有弱分类器错分样本的权重，使得第$m+1$个弱分类器更加关注已有弱分类器错分的样本“。这样增加每个弱分类器的差异，最终提升集成分类器的准确率。这种方法叫做：AdaBoost算法。

二分类AdaBoost算法过如下：

AdaBoost算法的统计学解释：
AdaBoost算法可以视为一种分步优化的加性模型。损失函数定义如下:
$$\begin{array}{rl}\mathfrak{L}(F)& =exp(-yF(\mathbf{x}))\\ & =exp(-y\sum _{m=1}^{\mathbf{M}}{\alpha }_m{f}_m(\mathbf{x}))\end{array}\text{\hspace{1em}(式9)}$$
其中， y , f m ( x ) ∈ { − 1 , + 1 } y,f_m{(\boldsymbol{x}})\in\{-1,+1\} y,fm​(x)∈{ −1,+1}.
若前$m-1$次迭代之后得到:
$$F_{m-1}(\mathbf{x})=\sum _{t=1}^{m-1}{\alpha }_t{f}_t(\mathbf{x})\text{\hspace{1em}(式10)}$$
则第$m$次迭代的目标是找到一个${\alpha }_m$和$f_m(\mathbf{x})$使得损失函数最小，即：
$$\mathfrak{L}({\alpha }_m,f_m(\mathbf{x}))=\sum _{n=1}^{N}exp(-y^{(n)}(F_{m-1}({\mathbf{x}}^{(n)})+{\alpha }_m{f}_m({\mathbf{x}}^{(n)})))\text{\hspace{1em}(式11)}$$
令$w_m^{(n)}=exp(-y^{(n)}{F}_{m-1}({\mathbf{x}}^{(n)}))$,那么上式可以写为：$$\mathfrak{L}({\alpha }_m,f_m(\mathbf{x}))=\sum _{n=1}^N{w}_m^{(n)}exp(-{\alpha }_m{y}^{(n)}{f}_m(\mathbf{x}{)}^{(n)}))\text{\hspace{1em}(式12)}$$
因为： y , f m ( x ) ∈ { − 1 , + 1 } y,f_m(\boldsymbol{x})\in\{-1,+1\} y,fm​(x)∈{ −1,+1},则有:
$$y{f}_m(\mathbf{x})=1-2I(y\ne f_m(\mathbf{x}))\text{\hspace{1em}(式13)}$$
其中，$I(\mathbf{x})$为指示函数。
将损失函数进行二阶泰勒展开，得到:
$$\begin{array}{rl}\mathfrak{L}({\alpha }_m,f_m(\mathbf{x}))& =\sum _{n=1}^N{w}_m^{(n)}\left(1-{\alpha }_m{y}^{(n)}{f}_m({\mathbf{x}}^{(n)})+\frac{1}{2}{\alpha }_m^2\right)\\ & \propto {\alpha }_m\sum _{n=1}^N{w}_m^{(n)}I(y\ne f_m(\mathbf{x}))\end{array}\text{\hspace{1em}(式14)}$$
可以得到，当${\alpha }_m>0$时，最优分类器$f_m(\mathbf{x})$为：样本权重是$w_m^{(n)},1\le n\le N$时的加权错误最小的分类器。
这样一来，求出了$f_m(\mathbf{x})$,则式12可以写成：
$$\begin{array}{rl}\mathfrak{L}({\alpha }_m,f_m(\mathbf{x}))& =\sum _{y^{(n)}\ne f_m((\mathbf{x}{)}^{(n)})}{w}_m^{(n)}exp({\alpha }_m)+\sum _{y^{(n)}=f_m((\mathbf{x}{)}^{(n)})}{w}_m^{(n)}exp(-{\alpha }_m)\\ & \propto {ϵ}_{m}exp({\alpha }_m)+(1-{ϵ}_m)exp(-{\alpha }_m)\end{array}\text{\hspace{1em}(式15)}$$
其中，${ϵ}_m$为分类器$f_m(\mathbf{x})$的加权错误率。
$${ϵ}_m=\frac{{\sum }_{y^{(n)}\ne f_m((\mathbf{x}{)}^{(n)})}{w}_m^{(n)}}{{\sum }_n{w}_m^{(n)}}\text{\hspace{1em}(式16)}$$
于是求取式15关于${\alpha }_m$的导数并令为零：
$$\alpha =\frac{1}{2}\log \frac{1-{ϵ}_m}{{ϵ}_m}\text{\hspace{1em}(式17)}$$