模型聚合的动机
如果已经得到了一些特征或假设，这些假设可以做预测，那么如何将这些有预测性的特征或假设合起来，让它们变得更好？这种模型就称为模型聚合
为什么要做模型聚合呢？举个例子，假设今天有15个朋友，每个人都会对股市的涨跌做一个预测，那么在得到这些预测以后应该怎么办？其实可以做的事情非常多，例如
- 根据过往的情况，选择最可靠的朋友，听ta的意见（类似于机器学习中的验证方法）
- 让朋友们一人一票，看投票结果
- 让朋友们投票，其中比较可靠的给的票数多（非平等投票）
- 根据每个人的特长，在不同的情况下听从不同人群的意见
以上做法都可以对应于机器学习中的某种算法。总的来说，将这些人意见融合起来的过程，就可以类比为模型聚合的算法过程。可以使用更加形式化的方法来描述上述做法。假设有\(T\)个朋友对应于\(T\)个假设函数\(g_1, \ldots, g_T\)，每个朋友\(t\)做出的预测为\(g_t({\bf x})\)，则（假设每个人只预测涨跌，涨记为\(+1\)，跌记为\(-1\)）
- 验证法的形式化表示为\(G({\bf x}) = g_{t_\ast}({\bf x}){\rm\ with\ }t_\ast = \mathop{\rm arg\min}_{t \in \{1,2,\ldots, T\}}E_{\rm val}(g_t^-)\)
- 平等投票法的形式化表示为\(G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T 1\cdot g_t({\bf x})\right)\)，这里每个\(g_t({\bf x})\)前面乘的1就是每个人的权重
- 非平等投票法的形式化表示为\(G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T \alpha_t\cdot g_t({\bf x})\right), \alpha_t \ge 0\)。注意这种方式包含了前面提到的验证法和平等投票法。当\(\alpha_t = 1\)时，该方法退化为平等投票法；当\(\alpha_t = [\![E_{\rm val}(g_t^-)\ {\rm smallest}]\!]\)时，该方法退化为验证法
- 根据特长选择法的形式化表示为\(G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T q_t({\bf x})\cdot g_t({\bf x})\right), q_t({\bf x}) \ge 0\)。这里\(q_t({\bf x})\)实际上是根据输入对\(t\)做判断给ta几票的函数。当\(q_t({\bf x}) = \alpha_t\)时，该方法退化为非平等投票法
可见，聚合模型是一个很大的模型族
在正式介绍聚合模型法之前，有必要先从验证法入手，分析一下验证法与（其它）聚合模型法之间的不同。回忆之前讲过的验证法的过程，不难发现验证法最后返回的\(g_t^-\)是一个很强的模型，因为使用验证的目的就是让被选出的模型有足够小的\(E_{\rm out}\)，对该模型的评估也是要求其有足够小的\(E_{\rm val}\)。再次强调，验证法最后只返回一个模型。而聚合模型的出发点是，如果我们手里有多个假设模型，是否可以做得更好（尽管这些模型可能每个单拿出来效果都不是太好）？
为什么模型聚合以后的效果会比较好？可以看下面两个例子
上图左描述了这样一个问题：对于图示中的数据集，只允许用水平和竖直的线做分类器，将数据集完全分开（但是可以对分类器产生的结果进行组合）。可以看到，图中选择的两条竖直线和一条水平线各自都没有将数据集完全分开的能力，但是它们组合（投票）的结果却可以完成目标。这表明若干弱分类器聚合的结果可能会突破个体的能力限制，完成某种类似于“特征变换”的功能
上图右描述了另一个问题：对于图示中的数据集，PLA算法可能会产生无限多条线将样本完全分开（因为PLA算法有随机性）。这些线有的可能会偏向红方，有的可能会偏向蓝方，但是它们组合（投票）的结果最后可能得到的是图中的黑色实线，这条实线比较中庸平均，离两边都不近——而这条线很有点像使用SVM算法得到的分类器。这说明从另一方面，模型经过聚合以后可能可以达到正则化的目的
在之前的课程里，以开车为例，特征变换使模型变得强大，有点像踩油门；而正则化使模型不要过分复杂，有点像踩刹车。从上面的例子中，可以看到这两个效果都可以通过模型聚合达到，因此可以初步判断说，恰当的聚合可以使模型的效果更好
均匀混合
均匀混合法，对应于之前提到的平等投票法。其原理是对于若干个已经知道了形式的假设函数\(g_t\)（这里首先考虑二元分类问题，因此假设每个函数返回都是+1或者-1），给它们分配相等的权重，对分类的结果进行统计，即 \[ G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T 1\cdot g_t({\bf x})\right) \] 如果所有\(g_t\)返回的结果都一样，那么跟使用其中任何一个\(g_t\)也没什么差别。但是如果每个\(g_t\)返回的结果很不一样，那么大多数模型的结果可以对小部分模型的异端结果做出纠正（少数服从多数）——当然，如果要解决的是多元分类问题，可以采用类似的思想。不过此时具体\(G({\bf x})\)的形式稍有不同，为 \[ G({\bf x}) = \mathop{\rm arg\max}_{1\le k \le K}\sum_{t=1}^T [\![g_t({\bf x}) = k]\!] \] 对于回归问题，均匀混合法应如何做？直观（且的确是可行）的方法就是把所有分类器预测的结果做平均，即 \[ G({\bf x}) = \frac{1}{T}\sum_{t=1}^Tg_t({\bf x}) \] 假设\(g_t\)返回的结果很不一样，那么很可能出现的结果是一部分\(g_t({\bf x}) > f({\bf x})\)，另一部分\(g_t({\bf x}) < f({\bf x})\)。求均值的结果是将这些盈余和不足都抵消掉，最后的结果会比每个独立\(g_t\)预测的结果都更靠近\(f\)
综上所述，如果各个\(g_t\)的结果都很不一样，即使最后聚合模型的时候采用的是非常简单的均匀混合法，得到的结果也比任意一个单个假设返回的结果要好一些
对于回归问题，有一个更理论的证明，可以表明\(G({\bf x})\)的结果肯定比单一模型的结果更好。从最简单的情况入手，先考虑对一个数据点\(\bf x\)的情况。为了记法上的方便，可以把\(\bf x\)都省略掉，即记为\(G = \frac{1}{T}\sum_{t=1}^Tg_t = {\rm avg}(g_t)\)。因此 \[ \begin{align*} {\rm avg}\left((g_t({\bf x}) - f({\bf x}))^2\right) &= {\rm avg}(g_t^2 - 2g_tf + f^2) \\ &= {\rm avg}(g_t^2) - 2Gf + f^2 \\ &= {\rm avg}(g_t^2) - G^2 + (G-f)^2 \\ &= {\rm avg}(g_t^2) - 2G^2 + G^2 + (G-f)^2 \\ &= {\rm avg}(g_t^2 - 2g_tG +G^2) + (G-f)^2 \\ &= {\rm avg}((g_t-G)^2) + (G-f)^2 \end{align*} \] 上面讨论的是对一个数据点的情况。将其扩展到整个数据集上，有如下关系式 \[ \begin{align*} {\rm avg} (E_{\rm out}(g_t)) &= {\rm avg}\left(\mathcal{E}(g_t-G)^2\right) &+ E_{\rm out}(G) \\ &\ge &+E_{\rm out}(G) \end{align*} \] \(\blacksquare\)
那么如何运用这个模型聚合的方法呢？可以想象一个虚拟的机器学习过程：对每个\(t=1,2\ldots, T\)，假设有\(N\)条来自于某个分布\(P^N\)的数据，组成数据集\(\mathcal{D}_t\)（满足独立同分布性）。假设每个\(g_t\)都是用不同的\(N\)条数据根据算法\(\mathcal{A}(\mathcal{D}_t)\)学习得出，那么所有这些\(g\)的均值，记为\(\bar{g}\)，有 \[ \bar{g} = \lim_{T\rightarrow \infty}G = \lim_{T\rightarrow \infty}\frac{1}{T}\sum_{t=1}^Tg_t = \mathcal{E_D A(D)} \] 套用上面的结论，有 \[ {\rm avg} (E_{\rm out}(g_t)) = {\rm avg}\left(\mathcal{E}(g_t-\bar{g})^2\right) + E_{\rm out}(\bar{g}) \] 这里各项可以解释如下：
- \({\rm avg} (E_{\rm out}(g_t))\)：算法\(\mathcal{A}\)效果的期望
- \(E_{\rm out}(\bar{g})\)：是各\(g_t\)“共识”的效果，称作偏差（bias）
- \({\rm avg}\left(\mathcal{E}(g_t-\bar{g})^2\right)\)：各个\(g_t\)与它们“共识”之间偏离量的期望，称作方差（variance）。方差衡量了\(g_t\)内部的“混乱程度”
而均匀混合的过程实际是减少方差的过程，因此模型的表现更加稳定
线性混合与任意混合法
线性混合法比均匀混合法更复杂一些，每个\(g_t\)的权重不再相等，而是各自有一个\(\alpha_t\)作为权重与之对应，形式为 \[ G({\bf x}) = {\rm sign}\left(\sum_{t=1}^T \alpha_t\cdot g_t({\bf x})\right), \alpha_t \ge 0 \] 可以看到，其实就是对\(g_t({\bf x})\)做了一个线性组合，这也是线性混合法这个名称的来历。这里最核心的问题就是怎样的\(\alpha_t\)最好。一个简单且直接的想法就是，最好的\(\alpha_t\)肯定使\(E_{\rm in}\)最小，即满足\(\min_{\alpha_t \ge 0}E_{\rm in}(\boldsymbol{\alpha})\)。对应的优化问题为（以回归问题举例） \[ \min_{\alpha_t \ge 0}\frac{1}{N}\sum_{n=1}^N\left(y_n - \sum_{t=1}^T \alpha_tg_t({\bf x}_n)\right)^2 \] 这个优化问题的形式很像线性回归+多项式变换的问题，求解则像概率SVM那样，使用两阶段学习的方法求解：第一步先学习出\(g_t\)，第二步再做线性回归学习出\(\alpha_t\)。因此线性混合可以理解为下面的过程：总体是一个线性模型，每个\(g_t\)看作是多项式变换，然后再加上条件说\(\alpha_t \ge 0\)。但是有了限制条件以后怎么求解？对那些小于0的\(g_t\)，只需要反过来用就行，即\(\alpha_t g_t({\bf x}) = |\alpha_t|(-g_t({\bf x}))\)（尤其是在二元分类中，99%的错误率实际就是99%的正确率）。因此在真正使用时，通常不考虑限制条件
在现实世界中，这些\(g_t\)通常来自于不同的假设集合，即\(g_1 \in \mathcal{H}_1, g_2 \in \mathcal{H}_2, \ldots, g_T \in \mathcal{H}_T\)。一个直观的做法是我们使用不同的假设集合，在每个集合上都找到\(E_{\rm in}\)最小的\(g_t\)，将它们混合起来。但是回忆之前的课程曾经提过，在一堆最好的假设函数里再选择一个更好的假设函数（称为best of best），模型的复杂度其实是\(d_{\rm VC}\left(\bigcup_{t=1}^T\mathcal{H}_t\right)\)，需要对最后的模型做小心的验证。而线性混合法中的一个特例是验证法，这就表示用\(E_{\rm in}\)来做线性混合的标准，复杂度要\(\ge d_{\rm VC}\left(\bigcup_{t=1}^T\mathcal{H}_t\right)\)（因为best of best只是特例而已）。因此在实践中不建议用\(E_{\rm in}\)来选择，而是选择让\(E_{\rm val}\)最小的\(\boldsymbol{\alpha}\)，而且各个\(g_t\)要用从训练集得到的\(g_t^-\)
所以，这里推荐的做法为
- 使用训练数据\(\mathcal{D}_{\rm train}\)得到\(g_1^-, g_2^- ,\ldots, g_T^-\)
- 对验证集\(\mathcal{D}_{\rm val}\)中的每条数据做变换得到\(({\bf z}_n = \boldsymbol{\Phi}^-({\bf x}_n), y_n)\)，其中\(\boldsymbol{\Phi}^-({\bf x}) = (g_1^-({\bf x}), \ldots, g_T^-({\bf x}))\)
在经过上述训练和转换后，线性混合法对\(\{({\bf z}_n, y_n)\}\)做线性模型得到最优的\(\boldsymbol{\alpha}\)，然后返回的\(G_{\rm LINB}({\bf x})\)是\(\boldsymbol{\alpha}\)与\(\boldsymbol{\Phi}({\bf x})\)内积的线性模型，这里\(\boldsymbol{\Phi}({\bf x}) = (g_1({\bf x}), \ldots, g_T({\bf x}))\)
当然，这里可以不必要拘泥于线性模型，甚至可以使用非线性模型。此时整个过程称为任意混合法，或者称为堆叠法（stacking）。即首先计算\(\tilde{g} = {\rm Any}(\{({\bf z}_n, y_n)\})\)，最后返回\(G_{\rm ANYS}({\bf x}) = \tilde{g}(\boldsymbol{\Phi}({\bf x}))\)。堆叠法能力更强，实际上实现了前面提到的条件混合法（根据特长混合法），但是也更容易过拟合
经典案例：KDD Cup 2011冠军队的解决方案
Bagging
前面讲的混合模型的方法基本都是在得到\(g_t\)以后的进一步处理。那么有没有可能一边学\(g_t\)一边将它们聚合起来？首先，由前面均匀混合模型一节的讲解，混合模型的关键是所有\(g_t\)必须非常不一样。这种多样性从何而来？可以有这么几个方面：
- \(g_t\)来自于不同的模型集合，即\(g_1 \in \mathcal{H}_1, g_2 \in \mathcal{H}_2, \ldots, g_T \in \mathcal{H}_T\)
- \(g_t\)来自于同一个模型集合的不同超参数，例如GD时设置学习率\(\eta = 0.001, 0.01, \ldots, 10\)
- 算法本身有随机性，例如使用不同的随机种子来得到不同的PLA
- 数据本身具有随机性，例如交叉验证时得到不同的\(g_v^-\)
那么有没有可能进一步，我们使用同一份数据，对这份数据施加一些随机性，又不使用\(g^-\)，而是制造很多不同的\(g\)？回顾前面讲到的偏差-方差之间的关系，可知大家的“共识”比直接使用\(\mathcal{A(D)}\)要稳定，但是代价是每次都要新鲜的数据集\(\mathcal{D}_t\)。此外，\(\bar{g}\)是从无限多个\(g\)产生，这个无限也不可能达到。因此，需要做两个妥协：使用有限多但是足够大的\(T\)，以及只使用一份\(\mathcal{D}\)来模拟产生\(T\)份不同的数据集。对于后者，要用到统计学上一个重要的工具——bootstrapping（直译为“拔靴法”，或者意译为“自助法”），其核心做法是通过对原始数据集\(\mathcal{D}\)进行有放回抽样，每取\(N'\)条数据形成一个\(\mathcal{D}_t\)（\(N'\)不一定非要等于\(N\)）。由于有放回的动作，因此每个\(\mathcal{D}_t\)中都会有某几条数据重复了若干次，同时又有若干条数据没有出现
这样，就可以得到一个bootstrapping模型聚合的过程：对\(t=1,2, \ldots, T\)，通过bootstrapping得到一个大小为\(N'\)的数据集\(\tilde{\mathcal{D}}_t\)，在这个数据集上运行算法\(\mathcal{A}\)得到\(g_t\)。最后，对得到的\(T\)个\(g_t\)，通过均匀混合的方法得到\(G\)。这种元算法（建立在基算法\(\mathcal{A}\)之上的算法）称为Bootstrap AGgregration，简写为BAGging（中文译为装袋法或者引导聚集算法）
如果基算法对随机性比较敏感，那么bagging的结果会比较好
