本文是机器学习基石系列文章第七篇。介绍了集成学习的基本算法——Blending 和 Bagging。

7 Blending and Bagging

Kernel Model 的作用是将多个特征转化为 Kernel 表示，然后使用不同的机制求解对应的结果。上一节课通过将Kernel 延伸到Ridge Regression中，可以利用Represeter Theorem得到Kernel的形式，但是其结果不是稀疏解，导致训练和预测需要花费更多的时间成本；为了借鉴SVM得到稀疏解，使得权重向量可以被少数的 $z$z 表达出来，通过Regularized Tube Error和拉格朗日对偶，推到得到了Support Vector Regression。本节课程开始学习集成学习（Ensemble Learning）中的相关算法。本节课介绍 Blending 和 Bagging 算法，即将多种不同算法得到的最佳的假设结合起来，让模型预测得更好，这样的模型叫做融合模型（Aggregation Models）。

7.1 Motivation of Aggregation

先看一个例子，直观地了解融合模型：

假设有T个朋友向你推荐要不要买股票，每个人的意见为 $g_i,i=1,2,...,T$gi​,i=1,2,...,T ，那么你应该如何选择呢？有四种想法：

• 选择最信得过的朋友，即选择炒股炒得最好的那位朋友的意见；
• 综合T位朋友的意见选择是否买股票，每个人的意见权重相同；
• 更进一步，给炒股炒得好的朋友的意见赋予更多的权重，再看投票结果；
• 再进一步，根据不同的条件赋予不同的权重，比如有些人科技股票，有些人适合传统产业股票。

有了以上直观地理解，接下来看一下一般的数学表示，记假设函数为 $G(x)$G(x) ，对应四种不同的假设有如下数学表示：

• 从T位朋友的意见中选择最佳的假设函数 $g_{t_{*}}(x)$gt∗​​(x) ，最佳的意思是说在一个比较小的验证集的误差 $E_{val}$Eval​ 最小；
• 根据相等权重的投票选择，推荐买的记为 1，不推荐的记为-1，然后取 sign 函数；
• 更进一步，赋予每个人的投票不同的权重 $\alpha_t$αt​，表示为上式，可以看出前两种假设是该假设的特例；
• 再进一步，根据不同的条件赋予不同的权重，添加 $q_t(x)$qt​(x) 表示条件判断。

接下来看第一种情形：

如果不依据验证集上的的 $E_{val}$Eval​ 做选择，而是使用训练集上的 $E_{in}$Ein​ 做选择可不可以？可以，但是算法复杂度会上升。即如果要求训练误差最小的话，会导致 VC Dimention $d_{VC}$dVC​ 很大。

如果要从 $g^-_t$gt−​ 中选择最佳的假设函数 $g_{t_{*}}$gt∗​​ ，则需要 $g^-_t$gt−​ 中包含有比较好的假设函数矩 $g$g 。即这种情形的假设是已经有了一堆不错的模型（假设函数）或者说至少有一个比较好的模型，从中选择最好的模型（假设函数）。

对选择标准来说，选择一个最佳的假设函数即可。但是，对于融合模型来说，其目的是选择一堆可能看起来不是最好但还可以的假设函数，然后将其融合起来，使假设函数变得更好。这是未来的五节课程探讨的问题。

那么，为什么融合模型的表现更好呢？看一个二分类的例子：

• 第一种情形，只使用水平线（图中灰色的线，有一条）和垂直线（有两条）做超平面，融合模型要做的是将这些水平线和垂直线的某些线段做组合，然后“融合”出分隔超平面，将输入空间的样本点二分；可以看出，虽然每条灰色的线分类效果并不是非常理想，但是其融合后的结果是一个比较复杂的分类边界，可以很好地将输入空间的样本点分开，这就是融合模型的思想所在，也就是说，融合模型结合了不同模型的优点，拓展了模型的能力；直观地说就是一根筷子跟一把筷子的区别。
• 第二种情形，使用感知器做分类，图中有无数条分类超平面（灰色的线），即假设空间中的假设函数，那么应该如何选择呢？对于PLA来说，可能会选择任意一条；对于SVM，会选择边界最“胖”的那一条；现在想，将这些超平面做投票，然后将投票的结果作为最终选择的超平面，如图中黑色的线所示，可以看出，选出了一条比较“中庸”的超平面，这条超平面就跟SVM中边界最胖的超平面类似，相当于说是有正则化约束的情况下选择的 large margin 的超平面。

之前学习的模型中，特征转换和正则化是对立的，将其分别比作油门和刹车。如果进行特征转换，正则化效果就会很差，反之亦然。而通过以上可以看出，融合模型实际上相当于既做了特征转换，又加了正则化约束，相当于油门和刹车都控制的很好，使得模型的表征特征的能力更强，同时还能降低过拟合风险，提高泛化能力。这就是设计融合模型的动机。

习题1：

7.2 Uniform Blending

现在开始看如何将不同的假设函数融合起来，首先看 Blending。直观地解释就像榨果汁，将不同的水果蔬菜混合，榨一杯混合果汁，融合多种营养成分。

首先看Uinform Blending，即上一小节提到的，一人一票，每票同权。如果要做二元分类，其表达式如下：

仍然拿买不买股票的例子说明，+1 表示推荐买，-1表示不推荐买，然后根据多人的意见决定买不买，上式也很容易理解，如果推荐买的人多，那么括号内一定是整的，反之是负的，再取sign函数就变为 +1和-1两种结果。这就是假设函数的 $G(x)$G(x) 的含义。

上图中的三条灰色的垂直或者水平的线（三个不同的假设函数 $g$g）可以将输入空间分割为六个小区域，然后使用三个假设函数对每个小区域进行投票，确定正负类。投票的结果实际上是少数服从多数。如果是多分类的情况，此时就不是简单的加加减减，而是看每个类别得多少票，然后选择最多票的类别。

以上是分类的情况，如果是回归问题应该如何计算呢？

可以看出，相比分类任务，回顾问题没有使用sign这样的函数，将输出离散化，而是对投票结果求平均，通过平均可以削弱某些不好的假设函数 $g$g 的影响，可以得到更好的结果。从理论上说，平均值计算可能是更稳定，更准确的一种估计方式。

如果要使得融合不同假设函数 $g$g 的融合模型可以work，有一个重要的前提是假设函数 $g$g 是不同的，可以想象上图中的灰色的线（对应假设函数 $g$g ），如果 $g$g 都相同，也就是灰色的线都重合了，所以无论有多少水平或者竖直的直线，也只能将输入空间的样本点最多分为四个小区域。这时候，分类边界很有限，也就是说模型的容量太低，提取特征的能力很差，很难拟合数据集，找出一条好的超平面；相反，如果 $g$g 都是不同的，那么可以将输入空间划分为很多的小区域，就可以拟合出更复杂的边界。

融合模型最简单的情形是一人一票，每票同权。根据少数服从多数的原则，对不同的假设函数 $g$g 在划分成小区域的输入空间中，划分分隔超平面。

下面进一步分析回归问题中，Blending为什么表现比较好？

$g_t(x)-f(x)$gt​(x)−f(x) 表示假设函数的预测输出 $g_t(x)$gt​(x) 与期望输出 $f(x)$f(x) 的差值。上式中的平均操作 $avg$avg 其实就相当于 $G(x)$G(x) 公式中的先求和再取平均。 然后将上式中的平方和展开，然后凑平方，进一步推导得到结果。其中， $G(x)$G(x) 是一个整体，可以看做一项，所以对其先求和再求平均，结果还是一样的， $G(x)^2$G(x)2 同理，即 $avg(G(x)^2) = G(x)^2$avg(G(x)2)=G(x)2 。又因为 $G(x) = avg \ g_t$G(x)=avg gt​ 所以可以写为上式中的导数第二步的形式。

以上是对单一的样本 $x$x 操作，如果对整个输入空间内的所有样本操作，则有：

由上式可知，融合模型的误差 $E_{out}(G)$Eout​(G) 要比所有单个假设函数的平均误差 $avg(E_{out}(g_t))$avg(Eout​(gt​)) 要小，说明融合模型的性能更好。

下面考虑一些特殊的 $g_t$gt​ ：

将 $\bar{g}$gˉ​ 记为共识（consensus）， $E_{out}(\bar{g})$Eout​(gˉ​) 记为共识的表现，通常又称为偏差（bias），表示这些共识与目标函数 $f$f 相差多少。 $avg(\varepsilon(g_t-\bar{g})^2)$avg(ε(gt​−gˉ​)2) 记为对共识的期望偏差，通常又称为方差（variance）。Uniform Blending 算法的目的就是减少方差以实现更稳定的性能。

习题2：

7.3 Linear and Any Blending

上一小节讲了 Uniform Blending，是一人一票，每票同权的情况。本小节介绍 Linear Blending，添加投票权重 $\alpha_t$αt​ ，线性如何理解呢，就是通过权重参数 $\alpha$α 对不同的假设函数 $g$g 做线性组合。那么 $\alpha$α 应该如何计算,好的 $\alpha$α 评判标准是什么呢？一个简单的想法是好的 $\alpha$α 是使得 $E_{in}$Ein​ 最低的那个。应该如何求解呢？可以写成关于 $\alpha$α 的目标函数，然后求解最优化，使其对应的 $E_{in}$Ein​ 最低。要求 $\alpha \ge 0$α≥0。

对于使用 Linear Blending 处理回归问题的情况，其目标函数 $E_{in}$Ein​ 如下所示：

其中， $y_n$yn​ 表示期望输出， $g_t(x_n)$gt​(xn​) 表示假设函数 $g$g 的预测输出，可以看出Linear Blending处理回归问题的目标函数与带特征转换（transformation）的线性回归的目标函数是很像的，不同点是 $\alpha_t\ge 0$αt​≥0，而 $w_i$wi​ 的大小没有限制。求解 $\alpha$α 的方法使用两阶段的方法，类似之前介绍的 probabilistic SVM的求解思路。先求出 $g_t{x_n}$gt​xn​，再使用线性回归求出 $\alpha$α。其有三部分组成，与之前相比，多了限制条件（constrains） $\alpha \ge 0$α≥0。有没有办法将这个条件去掉，做如下转换：

在分类问题中，如果 $\alpha_t < 0$αt​<0 ，则 $\alpha_t >0$αt​>0， 如果样本的正类的概率是 $-99 \%$−99% ，也就是说负类的概率是 $+99 \%$+99% ，也就是说效果是相同的。所以可以将这个条件去掉，这样就得到了 Linear Blending 的一般表达式。

Linear Blending中，一般来说，不同的假设函数 $g$g 是通过不同的模型最小化目标函数，即最小化训练集上的误差函数 $E_{in}$Ein​ 得来的，然后从中选择最优的 $g$g。

那么如果还使用训练集上的误差 $E_{in}$Ein​ 来从不同的假设函数中 $g$g 选择最优的假设函数的话，这相当于，既使用训练集来训练不同的模型得到最佳的假设函数 $g$g，又使用训练集从这些不同的假设函数 $g$g ，通过最小化 $E_{in}$Ein​ 选出其中最佳的假设函数 $g$g 。这使得算法复杂度很高，计算成本很高。

所以一般做法是，让不同的模型在验证集上训练，即最小化验证集上的误差 $E_{val}$Eval​，找出这些模型最佳的假设函数 $g^-_1,g^-_2,...,g^-_T$g1−​,g2−​,...,gT−​ ，然后，将这些假设函数在训练集上训练，找出最佳的假设函数 $g_t$gt​。然后求解 $\alpha$α 。

求解一系列假设函数 $g$g 时，不要用训练集上的误差 $E_{in}$Ein​ 求解，因为复杂度高，计算消耗高，容易造成过拟合。应该选择一个验证集上的误差 $E_{val}$Eval​ 最小的假设函数 $g^-$g−。在训练集上通过模型选择找出最佳的 $g_t$gt​。

以上是Linear Blending，还有Any Blending。在 Linear Blending 中，融合模型的假设函数 $G(t)$G(t) 是各个模型假设函数 $g(t)$g(t) 的线性组合；在 Any Blending 中， $G(t)$G(t) 可以是 $g(t)$g(t) 的任意形式，比如非线性，也称它为Stacking。

Any Blending 的优点是模型复杂度比较高，可以获得更好的模型；缺点是容易导致过拟合。所以通常结合正则化的方法，提高模型的泛化能力。

习题3：

7.4 Bagging (Bootstrap Aggregation)

前三小节介绍了Blending算法，已经有了许多个模型训练出来的假设函数 $g$g，如何将它们组合成融合模型，从最简单的 uniform Blending开始，根据投票原则，即一人一票，每票同权；对于分类问题，先求和，再取sign函数；对于回归问题，使用对各个假设函数的预测结果取加权平均。然后 linear Blending，将各种假设函数根据不同的权重进行线性组合。最后是有条件的Blending，即stacking，根据不同的条件决定加权的多少。

那么应该如何得到不同的 $g_t$gt​ 呢？

• 从不同的假设空间 $H$H 中选出不同的假设函数 $g_T$gT​ ，也就是使用不同的模型产生不同的假设函数；
• 设置不同的参数，比如学习率 ；
• 应用算法的随机性，设置不同的随机种子产生随机的PLA算法；
• 应用样本的随机性，比如设置交叉验证来获取假设函数 $g^-$g−。

下面考虑如何从已有的数据集中训练出多个不同的假设函数 $g_t$gt​ ：

回顾第二小节推导的理论，Bias-Variance，也就是说演算法 $A$A 的平均表现可以拆分成 Bias 和 Variance，这样拆分有什么优势呢？Bias表示所有假设函数 $g_t$gt​ 的共识（consensus），Variance是不同假设函数 $g_t$gt​ 之间的差距。 $g_t$gt​ 是通过不同的模型在不同的数据集上计算得到的，但是只有一个数据集的情况下，应该如何构造不同的数据集，从而得到不同的 $g_t$gt​ 呢？其中 $\bar{g}$gˉ​ 是在假设函数个数 T 趋于无穷的条件下，对不同的假设函数 $g_t$gt​ 取平均的假设函数。可以将其做近似，需满足如下两个条件：

• 有限的 T （足够多）；
• 从已知数据集 $D$D 中构造出 t 个数据集 $D_t$Dt​ ，然后通过演算法从这t个数据集中求出t个假设函数 $g_t$gt​ 。

那么应该如何构造 $D_t$Dt​ 呢？

统计学上有种方法叫做 bootstrapping，直接翻译为拔靴法。它要做的事情是从已知数据集中模拟不一样的数据，其实就是有放回取样。利用 bootstrapping 对假设函数进行融合的操作就称为 Bagging，翻译为装袋算法。

下面演示了一个 Bagging Pocket 的例子。

其中灰色线表示 Bagging Pocket 中包含的假设函数算出的分隔超平面，然后使用 bootstrapping 计算得到黑色的线，即最终的分隔超平面。原来的假设函数做出的超平面都是线性的，现在通过Bagging Pocket 融合这些假设函数，得到非线性的分类边界。只有当演算法对数据分布比较敏感时，Bagging Pocket 才有比较好的表现。

习题4：

Summary

本节课介绍了Blending 和 Bagging，都属于集成学习模型。通过将不同演算法得到的假设函数 $g$g 融合（aggregation）得到最终的假设函数 $G(x)$G(x) ，介绍了三种方法来融合不同的假设函数 $g$g ，以使得融合后的假设函数有更好的性能。先从Linear的情况说起，讲解了分类和回归的目标函数；如果要改为non-linear，其实也很简单，只需要做一个两阶段的变换即可。最后介绍了如何通过bootstrapping来得到算法中不同的假设函数 $g$g ，然后再把它们融合。

下一节课开始介绍能不能使用bagging得到更不一样的假设函数，从而得到更不同的最后融合的假设函数 $G(x)$G(x)。