混合（blending）是将已学到的不同假设以均匀、线性或非线性的方式融合起来。若先从 boostrapped 数据集学到各种不同的假设，然后再混合，就称为自助聚集（bagging, bootstrap aggregating）。
混合在实际中很有用，但也增加了计算复杂度。
融合简介
假设$T$个👬朋友$g_1,\ldots,g_T$给出参考意见$g_t(\mathbf x)$预测股票是否会涨，如何决策呢？
- 验证法（validation）：听从最懂股票那个朋友的意见， \begin{equation*} G(\mathbf x)=g_{t_*}(\mathbf x)，\qquad t_*=\underset{t\in\{1,2,\ldots,T\}}{\arg\min}E_{val}\left(g_t^-\right)， \end{equation*} 首先在稍小训练集（去除了验证集）上得到所有候选$\{g_t^-\}$，然后在验证集上筛选出最优$g_{t_*}^-$，最后在全训练集（包含验证集）上得到$g_{t_*}$。
- 投票法（vote）：一人投一票，听从多数人的意见， \begin{equation} G(\mathbf x)=\mbox{sign}\left(\sum_{t=1}^T1\cdot g_t(\mathbf x)\right)。 \label{eq:uniform-blending-hypothesis} \end{equation}
- 加权投票法：每人投票数不一样，听从多数票的意见， \begin{equation} G(\mathbf x)=\mbox{sign}\left(\sum_{t=1}^T\alpha_t\cdot g_t(\mathbf x)\right),\qquad\alpha_t\geq 0。 \label{eq:linear-blending-hypothesis} \end{equation} 当$\alpha_t=[[E_{val}\left(g_{t}^-\right)\mbox{ smallest}]]$时，与方法1一样；当$\alpha_t=1$时，与方法2一样。
- 有条件的组合：比如科技股听从擅长这方面的朋友，传统行业股票听从那些…… \begin{equation} G(\mathbf x)=\mbox{sign}\left(\sum_{t=1}^T q_t(\mathbf x)\cdot g_t(\mathbf x)\right),\qquad q_t(\mathbf x)\geq 0， \label{eq:conditional-blending-hypothesis} \end{equation} 当$q_t(\mathbf x)=\alpha_t$时，与方法3一样，也就是包含了前面所有情况。
上述1的验证法，若用$E_{in}(g_t)$代替$E_{val}(g_t)$选择模型，可能会付出很大VC维的代价。这种方法需要一个强大优秀的$g_t^-$，否则也只是差中择优。上述的 2～4 称为融合模型（aggregation model），其目的在于综合多个假设（可能是比较弱的）让效果更好。
图：［左］：水平垂直线投票［右］PLA投票
上图展示的投票法中，灰色的判别界表示参与投票的分类器，合理的融合方法能提升分类性能。上图左，水平和垂直线将平面分割成 6 块区域，可得绿色标注的投票结果，相当于组合成了黑色的判别界。上图左的投票方法，具有特征变换的效果；上图右的感知器投票，具有正则化的效果。
均匀混合
均匀混合（uniform blending）也就是投票法\eqref{eq:uniform-blending-hypothesis}。对于多个不同的假设，简单的混合法则也可得到比单一假设更好的结果。如果所有$g_t$都一样，等价于采用任一$g_t$；如果$g_t$千差万别，就是少数服从多数。该方法可以直接推广到多类的情况， \[ G(\mathbf x)=\arg\max_{1\leq k\leq K}\sum_{t=1}^T[[g_t(\mathbf x)=k]]。 \]
均匀混合解决回归问题的方法是 \[ G(\mathbf x) = {1\over T}\sum_{t=1}^Tg_t(\mathbf x)。 \] 如果所有$g_t$都一样，等价于采用任一$g_t$；对于不同的$g_t$，可能得到比单个$g_t$更准确的结果。
对于均匀混合的回归， \[ \begin{aligned} avg\left(\left(g_t(\mathbf x)-f(\mathbf x)\right)^2\right) =&avg\left(g_t^2-2g_t^2f+f^2\right)\\ =&avg\left(g_t^2\right)-2Gf+f^2\\ =&avg\left(g_t^2\right)-G^2+(G-f)^2\\ =&avg\left(g_t^2\right)-2G^2 + G^2 +(G-f)^2\\ =&avg\left(g_t^2-2g_tG + G^2\right) +(G-f)^2\\ =&avg\left(\left(g_t-G\right)^2\right) +(G-f)^2。 \end{aligned} \]
若对产生$\mathbf x$分布的所有点都进行上述运算，然后取期望可得 \[ avg\left(E_{out}\left(g_t\right)\right)=avg(\varepsilon(g_t-G)^2)+E_{out}(G)\geq E_{out}(G)， \] 也就是说，均匀混合方法的效果会比选择其中一个好。
从$P^N$采集大小为$N$的$T$个数据集，利用上述公式，衡量演算法$\mathcal A$的表现。通过$\mathcal A(\mathcal D_t)$获得$g_t$，对其平均 \[ \bar g=\lim_{T\rightarrow\infty}G=\lim_{T\rightarrow\infty}{1\over T}\sum_{t=1}^Tg_t=\varepsilon_{\mathcal D}\mathcal A(\mathcal D)， \] 算法$\mathcal A$的性能期望为 \begin{equation} avg(E_{out}(g_t))=avg(\varepsilon(g_t-\bar g)^2)+E_{out}(\bar g)。 \label{eq:bias-variance-decomposition} \end{equation}
上述公式中：
- $avg(E_{out}(g_t))$：算法$\mathcal A$的期望性能；
- $E_{out}(\bar g)$：算法共识（consensus）的性能（$\bar g$就是从$\mathcal D_t\sim P^N$期望获得的$g_t$），通常称为bias；
- $avg(\varepsilon(g_t-\bar g)^2)$：偏离共识的期望，通常称为variance。
通过bias和variance，将演算法的表现拆分为两部分。均匀混合通过减小variance获得更稳定的性能。
线性混合
通过\eqref{eq:linear-blending-hypothesis}，赋予不同假设不同的权重就是线性混合（linear blending）。线性回归的线性混合目标为 \[ \min_{\alpha_t\geq 0}{1\over N}\sum_{n=1}^N\left(y_n-\sum_{t=1}^T\alpha_tg_t(\mathbf x_n)\right)^2， \] 将$g(\mathbf x)$视为特征变换$\phi(\mathbf x)$，换一种表达形式 \[ \min_{\mathbf w}{1\over N}\sum_{n=1}^{N}\left(y_n-\sum_{i=1}^{\tilde d}w_i\phi_i(\mathbf x_n)\right)^2， \] 这就类似两阶（two-level）的学习方法。
线性混合＝［1］线性模型＋［2］假设（hypothesis）视为变换＋［3］约束条件， \[ \min_{\alpha_t\geq 0}{1\over N}\sum_{n=1}^Nerr\left(y_n,\sum_{t=1}^T\alpha_tg_t(\mathbf x_n)\right)。 \] 对于二分类问题 \[ \alpha_tg_t(\mathbf x)=|\alpha_t|(-g_t(\mathbf x))\qquad\mbox{if }\alpha_t<0， \] 正负对分类器本质上没有差别，实际上有“线性混合＝线性模型＋假设（hypothesis）视为变换”，不需要$\alpha_t$的约束条件。
在实际中，$g_t$通常是用$E_{in}$从各模型中选的最优，$g_1\in\mathcal H_1,g_2\in\mathcal H_2,\dots,g_T\in\mathcal H_T$。如果在这些$g_t$中用$E_{in}$再选最优的，就是 best of best，将付出高复杂度$d_{VC}=\left(\bigcup\limits_{t=1}^T\mathcal H_t\right)$的代价。如果在这些$g_t$中用$E_{in}$再采用线性混合，就是 aggregation of best，将付出高于$d_{VC}=\left(\bigcup\limits_{t=1}^T\mathcal H_t\right)$的代价。实际上通常采用$E_{val}$替代$E_{in}$，通过最小化$E_{train}$（也就是$E_{in}$）得到$g_t^-$。
线性混合算法
- 在$\mathcal D_{train}$上选出$g_1^-,g_2^-,\ldots,g_T^-$；
- 在$\mathcal D_{val}$中将$(\mathbf x_n,y_n)$转换为$(\mathbf z_n=\phi^-(\mathbf x_n),y_n)$，其中$\phi^-(\mathbf x)＝(g_1^-(\mathbf x),g_2^-(\mathbf x),\ldots,g_T^-(\mathbf x))$；
- 计算$\boldsymbol\alpha=\mbox{LinearModel}\left(\{(\mathbf z_n, y_n)\}\right)$；
- 返回 $G_{LINB}(\mathbf x)=\mbox{LinearHypothesis}_\boldsymbol\alpha(\phi(\mathbf x))$，其中$\phi(\mathbf x)＝(g_1(\mathbf x),g_2(\mathbf x),\ldots,g_T(\mathbf x))$。
如果将3、4两步换为：
- 计算$\tilde g=\mbox{AnyModel}\left(\{(\mathbf z_n, y_n)\}\right)$；
- 返回$G_{ANYB}(\mathbf x)=\tilde g(\phi(\mathbf x))$。
这就是 any blending（stacking）的方法。any blending 方法强大，可以实现 conditional blending，但是也存在过拟合的风险。
stacking（any blending）也称为 stacked generalization，在有监督学习（比如回归[1]）和无监督学习（比如密度估计[2]）中都有成功应用，也可用于估计自助聚集的错误率[3][4]。它的性能优于贝叶斯模型平均法[5]。在 Netflix 的竞赛中，有两只优胜队伍采用了 stacking 技术[6]。
图：混合方法使用实例
上图的流程中，Val.-Set Blending 就是 any blending 的方法，使得$E_{test}$降低到$456.24$。将上百个$g_t$用近似的$\tilde E_{test}$（若$\tilde E_{test}$好，真正的$E_{test}$也会好）进行线性混合得到$G$。
自助聚集
对于均匀融合（其它融合方法也如此），不同模型（假设）参与融合是关键，获取不同模型的方法包括：
- 从不同假设集获取模型：$g_1\in\mathcal H_1,g_2\in\mathcal H_2,\ldots,g_T\in\mathcal H_T$；
- 采用不同的参数：例如梯度下降法采用$\eta=0.001,0.01,\ldots,10$；
- 利用算法的随机性：例如用不同的初始化进行 PLA；
- 利用数据的随机性：交叉验证采用不同验证集。
回顾\eqref{eq:bias-variance-decomposition}，算法的性能被拆分为 bias 和 variance 两部分进行评估。当采用不同$g_t$融合时，共识（融合）的结果比$\mathcal A(\mathcal D)$的单一$g_t$效果好。能否通过有限的$T$和单一数据集$\mathcal D$得到不同$g_t$和近似的$\bar g$？✅
bootstrapping 是一种通过重采样（re-sample）$\mathcal D$模拟$\mathcal D_t$的统计学工具。bootstrap 得到$\tilde{\mathcal D}_t$的方法：从$\mathcal D$中随机抽取一个点，纪录该点后然后放回，重复该过程直到抽取到$N’$个数据。利用 bootstrap 的不同$\tilde{\mathcal D}_t$可以得到不同的$g_t$。
自助聚集（bootstrap aggregating）
- 利用bootstrapping技术得到$N’$点的数据集$\tilde{\mathcal D}_t$；
- 利用$\mathcal A(\tilde{\mathcal D}_t)$，算法$\mathcal A$在数据集$\tilde{\mathcal D}_t$上得到$g_t$；
- $G=\mbox{Uniform}(\{g_t\})$。
像自助聚集这种，建立在其它基础算法（base algorithm）$\mathcal A$之上的算法称为元算法（meta algorithm）。
bagging pocket 方法
上图是 bagging pocket 方法的效果，通过 bagging 得到各不相同的$g_t$，然后通过融合得到合适的非线性分类器。
如果基础算法（base algorithm）对数据的随机性很敏感，或者说基础算法不稳定（instability），那么训练数据的扰动或参数的微调能使分类结果发生明显变化，通过 bagging 就能提升分类精度[7]。k最近邻算法是稳定的，不适合作为 bagging 的基础算法[8]。
参考资料
- [1]L. Breiman, “Stacked regressions,” Machine learning, vol. 24, no. 1, pp. 49–64, 1996.
- [2]P. Smyth and D. Wolpert, “Linearly combining density estimators via stacking,” Machine Learning, vol. 36, no. 1-2, pp. 59–83, 1999.
- [3]L. Rokach, “Ensemble-based classifiers,” Artificial Intelligence Review, vol. 33, no. 1-2, pp. 1–39, 2010. [Online]
- [4]D. H. Wolpert and W. G. Macready, “An efficient method to estimate bagging’s generalization error,” Machine Learning, vol. 35, no. 1, pp. 41–55, 1999.
- [5]B. Clarke, “Comparing Bayes model averaging and stacking when model approximation error cannot be ignored,” The Journal of Machine Learning Research, vol. 4, pp. 683–712, 2003.
- [6]J. Sill, G. Takács, L. Mackey, and D. Lin, “Feature-weighted linear stacking,” arXiv preprint arXiv:0911.0460, 2009.
- [7]L. Breiman, “Bagging predictors,” Machine learning, vol. 24, no. 2, pp. 123–140, 1996.
- [8]L. Breiman, “Out-of-bag estimation,” Citeseer, 1996.
