机器学习笔记-Blending and Bagging

集成学习系列：

• Blending and Bagging
• Adaptive Boosting
• Decision Tree
• Random Forest
• Gradient Boosted Decision Tree

Blending and Bagging

1 - 为什么要用aggregation

如果我们已经有了一些模型$hypothesis$，或者已经有了一些$feature$，这些$hypothesis$可以帮助我们做预测，我们怎么样将这些已有的$hypothesis$或者是有有预测性的$feature$结合起来，让它们在一起的时候可以work的更好。这样的模型我们称之为$aggregation\ model$，也就是融合起来的模型。本篇介绍在$aggregation$中非常典型的两个做法，$blending$ 和 $bagging$。

那么为什么要用$aggregation$呢？

1.1 - 一个关于aggregation的故事

假如你有15个朋友，这15个朋友都告诉你明天股市的涨跌预测，那么你在听取了这15个朋友的预测之后，如何决定呢？

• $select\ from\ usual\ performance$
  从他们的平常的表现中选择最厉害的那个人，听取他的意见作为最后的决策依据，这也就是我们以前学过的$validation$的方法，
• $mix\ uniformly$
  但是如果只听一个人的，白白浪费了其余人的判断力，浪费了资源。所以另一种方式是以每人一票的方式，让这15个朋友进行投票，综合他们的判断做出最后的结果，
• $mix\ non$-$uniformly$
  但是考虑到可能每一个人的能力确实不尽相同，所以可以选择另外一种投票的方式：可以信赖的人给多一点的票数，不是那么可以信赖的人的票数可以少一点。
• $combine\ conditionally$
  又或者是可以根据具体的情况来进行选择， 例如这些朋友中有些人擅长分析科技类的股票，有些人擅长传统产业的股票，那么在不同的情况下，就选择听取不同的人的意见。
• $\cdots$

我们想要将这15个人的意见融合起来的事情， 就是$aggregation$想要做的事情，将每个人的预测结果融合起来以达到最好的结果。

我们将上述的这个问题用数学的形式表示出来：每一个朋友就代表每一个$hypothesis$：$g_1, g_2, \cdots, g_T$，也就是说这样就一共有15个预测模型。

• $select\ from\ usual\ performance$
  $$G(x) = g_{t_{*}}\ with\ t_{*} = argmin_{t\in{1, 2, \cdots, T}}\ E_{val}(g_t^-)$$
• $mix\ uniformly$
  $$G(x) = sign(\sum_{t=1}^T 1 \centerdot g_t(x))$$
• $mix\ non$-$uniformly$
  $$G(x) = sign\bigg(\sum_{t=1}^T\ \alpha_t \centerdot g_t(x)\bigg)\ with\ \alpha_t \ge 0$$
  通过参数$\alpha$给每一个$g_t$不同的权重。这种情况是包括前两种情况的：
  
  • 当$\alpha_t = |[E_{val}(g_t)\ smallest]|$的时候，是第一种情况。（其中$1 = |[\bigcirc]|, if\ \bigcirc$成立；$0 = |[\bigcirc]|, if\ \bigcirc$不成立）
  • 当$\alpha_t = 1$的时候，是第二种情况。
• $combine\ conditionally$
  $$G(x) = sign\bigg(\sum_{t=1}^{T} q_t(x)\centerdot g_t(x)\bigg)\ with\ q_t(x) \ge 0$$
  权重的参数不再是$\alpha$，而是变成了和输入特征$x$相关的函数$q_t(x)$。
  
  • 当$q_t(x) = \alpha_t$的时候，就是以上的第三种情形。

1.2 - Selection by Validation

$$G(x) = g_{t_{*}}\ with\ t_{*} = \mathop{argmin}\limits_{t\in{1, 2, \cdots, T}}\ E_{val}(g_t^-)$$
考虑上述提出的最简单的第一种情形，利用 $Validation$来选择最好的 $g_t$。这个方法的优点是简单。但是该方法中有一个重要的假设，如果最终想要得到一个比较好的 $g_{t_*}$，那么首先在得到的一堆 $g_t^-$中至少要有一个不错的， 或者说是 $strong$的。如果你的所有的朋友都对股市其实只是一知半解，那么你最终得到的最好的那一个人的意见也不见得会好到那里去。
而这里我们重点要谈论的 $aggregation$不是这样的。 $aggregation$擅长做的事情是，在没有一个很强的$hypothesis$的时候，或者说有一堆比较弱弱的但是还勉强的$hypothesis$的时候，把他们融合起来，通过集体的智慧，可以使得他们变的很强。这篇会讲解具体的不同的$aggregation$的做法。

1.3 - 为什么Aggregation可以work的很好呢

为什么$aggregation$可以很好的$work$呢，讨论如下的一个二分类的问题，假设我们只可以使用垂直的线和水平的线对上述的$data$进行分类(这样的话模型的复杂度很低)，那么只用一条分割线无论如何都是不能完全划分的。但是如果可以将不同的垂直的线和水平的线结合起来对数据进行划分呢(这里垂直的线和水平的线就是不同的$hypothesis$)，可能就可以得到比较好的结果。如下是结合了三条线对数据进行了划分。

从以上的结果可以看出来，如果只有一些弱弱的$hypothsis$，即那些只能是垂直或者是水平的线，但是如果将他们通过一定的方式合并起来的话，可能就会得到比较好的结果， 这里例子中就是得到了一个比较复杂的分类边界。这可能说明$aggregation$拓展了$model$的复杂度，这样看来$aggregation$的作用就好像是$feature\ transform$一样。

另一个对$aggregation$可以$work$的不错的解释是，当使用$PLA$算法对如下的$data$进行划分的时候，会得到不同的分割线，其中的每一个都能将数据完美的分开，但是我们知道如果通过$SVM$的话，可以得到有$large$-$margin$的分隔超平面。而使用$PLA$得到的可能就是图中灰色的任意一条，但是通过$aggregation$，或者说所有的这些灰色的线投票之后，就会得到一条比较$largin\ margin$的线，在这种情况下$aggregation$就会有$large\ margin$的类似于$regularization$的效果。

以前我们的认识是，$feature\ transform$和$regularization$是在做相反的事情，前者就像在踩油门，后者像是在踩刹车。而在做$aggregation$的时候，好像同时在做这两件事情：可能是$feature\ transform$，使得$model$更加的$powerful$；也可能是$regularization$，在帮助模型做一个比较适中的选择。 所以如果可以把$aggregation$做好的话，可能就同时将$feature\ transform$和$regularization$做好了。

2 - Uniform Blending

上面比较直观的讲解了$aggregation$的好处，接下来我们开始讲解应该怎么样来做$aggregation$，即怎么样把这些$hypothesis$融合起来。
我们可以使用$blending$的方法来做$aggregation$，$blending$这种方法主要用在我们已经收集到了一堆$hypothesis$，即已经有了一些已知的模型，需要对它们进行融合的情形。

如果对所有的$hypothesis$一视同仁，即给每一个$g(x)$相同的权重来进行组合的话，这种方式成为$uniform\ blending。$

2.1 - Uniform Blending用于分类

对于二元分类$binary\ classification$来说，$uniform\ blending$给每一个$hypothesis$相同的权重（所以叫$uniform$）来进行融合。根据融合的结果给出最终的判断，如下：

$$G(x) = sign\bigg(\sum_{t=1}^{T}\ 1 \centerdot g_t(x)\bigg)$$

• 如果所有已知的$g(x)$是相同的，那么$aggregation$是没有效果的
• 如果所有已知的$g(x)$差距很大，多数的意见会纠正少数的意见。例如在以下的问题中，共有三个$g(x)$：两个垂直线，一个水平线。对于数据点1和2来说，有两条线说它们是 $\circ$（左边的垂直线和水平线），一条线（右边的的垂直线）说它们是 $\times$，所以它们被划分为 $\circ$。对于其他的数据点来说也是使用这样的规则来进行划分的。
  
• 如果是多分类问题：那么我们就需要统计数据点在每一个类别上的“得票数”，将得票数最多的为该数据点的类别。 $$G(x) = \mathop{argmax}\limits_{1\le k \le K}\sum_{t=1}^{T}|[g_t(x) = k]|$$

2.2 - Uniform Blending用于回归

$uniform\ blending$将所有回归的值取平均：

$$G(x) =\frac1T\sum_{t=1}^{T}g_t(x)$$

• 如果所有已知的$g(x)$是相同的，那么$aggregation$是没有效果的
• 如果所有已知的$g(x)$差距很大，那么对于一个数据点来说，有些$g(x)$可能低估了， 有些$g(x)$可能高估了，这样的话，它们的平均值就可能会估计的更准确一下。

小结： 如果$aggregation$这样的方法想要$work$的很好的话，有一个很重要的前提是$g(x)$要有一定的多样性$diverse$。当$g(x)$有一定的多样性的时候，即使只是做很简单的融合的操作，例如说$uniform\ blending$，也会有很好的结果。

2.3 - Uniform Blending的理论分析

针对$uniform\ blending$用于$regression$，我们可以做简单的理论分析来解释为什么通过这样的$aggregation$的方式可以得到比单个的$hypothesis$更好的结果。
$uniform\ blending$用于$regression$的一般方式是：

$$G(x) =\frac1T\sum_{t=1}^{T}g_t(x)$$
如果只是针对特定的 $x$，那么上式可以写作：
$$G =\frac1T\sum_{t=1}^{T}g_t$$
接下来我们想要分析的问题是： $\frac1T\sum\big((g_t-f)^2\big)=avg(g_t - f)^2$ 和 $(G-f)^2$的大小关系，前者表示的是所有 $g$在 $x$上的平均错误，也可以理解为任选一个 $g$在 $x$上的平均错误；后者是经过 $aggregation$得到的 $G$在 $x$上的平均错误。
即比较$g$的平均错误（因为取到哪个都是不一定的）和$G$的错误的大小关系。
$$\begin{align} avg\ ((g_t - f)^2) & = avg(g_t^2 - 2g_tf+f^2) \\ & = avg(g_t^2) - 2Gf + f^2 \\ &= avg(g_t^2) - G^2 + (G-f)^2 \\ & = avg(g_t^2) - 2G^2 + G^2 + (G-f)^2 \\ & = avg(g_t^2 - 2g_tG + G^2) + (G-f)^2 \\ & = avg((g_t - G)^2) + (G - f)^2 \end{align}$$

当对所有的$x$进行计算的时候，可以得到如下的等式：

$$avg(E_{out}(g_t)) = avg(\varepsilon(g_t - G)^2) + E_{out}(G)$$
所以可以得到的是：

$$avg(E_{out}(g_t)) \ge E_{out}(G)$$
也就是说在使用 $uniform\ blending$这样的 $aggregation$做 $regression$的时候，得到的结果 $G$确实要比所有 $g$的平均表现好。尽管不知道是不是比最好的那个 $g$表现好。

2.4 - variance，bias

偏差$bias$度量了学习算法的期望预测和真实结果之间的偏离程度，即刻画了学习算法本身的拟合能力；
方差 $variance$度量了同样大小的训练集的变动所导致的学习性能的变化，刻画了数据的扰动所造成的影响。

假设在每一轮的学习中，由N笔资料训练得到$g_t$，共进行T轮的学习，每一轮使用来自同一分布的不同的资料。假设T可以取到无穷多，则得到：

$$\bar{g} = \mathop{lim}\limits_{T\rightarrow\infty}G = \mathop{lim}\limits_{T\rightarrow\infty}\frac1T\sum_{t = 1}^{T}g_t = \mathop{\varepsilon}\limits_{D}\ \mathcal{A}(D)$$

$$avg(E_{out}(g_t)) = avg(\varepsilon(g_t - \bar{g})^2) + E_{out}(\bar{g})$$

$avg(E_{out}(g_t))$代表的是学习算法$\mathcal{A}$表现的期望；$E_{out}$称为$bias$，也就是学习算法的期望预测和真实结果之间的偏离程度；$avg(\varepsilon(g_t - \bar{g})^2)$称为方差$variance$，不知道为什么要写一个$\varepsilon$，西瓜书上是没有的。
所以一个学习算法的表现可以拆分为两项，这个学习算法产生的共识和每一个$g_t$和这个共识的差异。

这块和西瓜书上写的有点不符合：日后补充
$E(f, D) = bias^2(x) + var(x) + \varepsilon^2$ (西瓜书)

所以通过这样的$aggregation$的方式，可以看到降低了$variance$，使得最终的学习算法的表现变好。

3 - Linear and Any Blending

$linear\ blending$是要给每一个$g_t$不同的权重（票数）$\alpha_t$，模型如下所示：

$$G(x) = sign\bigg(\sum_{t=1}^{T}\alpha_t \centerdot g_t(x)\bigg)\ with\ \alpha_t \ge 0$$
那么现在的问题就是要求解这些参数 $\alpha_t$，求解的方法就是最小化 $E_{in}$。
如果我们现在要做的是 $Regression$问题的话，我们求解 $\alpha$的策略当然就是最小化 $square\ error$。

Linear blending for regression

$$\mathop{min}\limits_{\alpha_t \ge 0}E_{in}(\alpha) = \mathop{min}\limits_{\alpha_t \ge 0}\frac1N\sum_{n=1}^{N}\bigg(y_n - \sum_{t = 1}^{T}\alpha_tg_t(x_n)\bigg)^2$$

如果将$(g_1, g_2, \cdots, g_T)$看做是$x_n$的特征转化 $\Phi$ ，那么以上的问题就可以变为我们熟悉的带有特征转换的线性模型，如下（1）所示，只不过是多了一个条件。并且这个过程和$probability\ SVM$中的$two\ level\ learning$的方法很相像：第一步将$SVM$用作一个特征的转换，然后使用$logReg$做微调。

linear regression + transformation

$$\mathop{min}\limits_{w_i\ge0}\frac1N\sum_{n=1}^{N}\bigg(y_n - \sum_{i =1}^{\tilde d}w_i\phi_i(x_n)\bigg) \tag1$$

所以我们可以说：$linear\ blending$就等于一个将许多的$hypothesis$当成一个特征转化的线性模型，外加一个限制条件。即：
$linear\ blending = linar\ model + hypothesis\ as\ transform + constraints。$

$$\mathop{min}\limits_{\alpha_i \ge 0}\frac1N\sum_{n=1}^{N}err\bigg(y_n， \sum_{t = 1}^{T}\alpha_tg_t(x_n)\bigg)$$

这个问题的求解不同于以往的仅仅是多了个$constraints$。对于$binary\ classification$问题来说，如果在求解之后发现$\alpha_t <0$，那么说明学习算法觉得这个$\alpha_t$对应的$g_t$反过来用能更好的$fitting$数据。所以在实际操作中通常都不考虑$\alpha_t > 0$这个条件限制。

所以$linear\ blending$的解法就是加了$feature\ transform$的$linear\ model$的解法，其中的$linear\ model$可以是线性回归，或者是逻辑斯蒂回归。

现在我们来关注一下一个基本的问题：那些$g_t$是怎么产生的？通常这些$g_t$是在各自不同的$model$下最小化$E_{in}$得到的。
所以如果在做$selection$（见本篇第一节，$aggregation$的第一种方式）的时候，如果是根据$E_{in}$来做选择的话，模型的复杂度就会更大（是不是可以理解为越复杂的模型越容易被选到，因为它可以拟合的很好，做到$E_{in}$很小），所以我们通常会用$E_{validation}$来做选择。
同样的，如果我们使用$E_{in}$作为最小化的目标来做$linear\ aggregation$，会导致更大的模型的复杂度，更加容易导致过拟合。也就是说，在实际应用中通常不使用$E_{in}$来学习$\alpha$，因为这样很容易$overfitting$，而是在$D_{val}$上训练 $\alpha$使得$E_{val}$最小。并且在$D_{train}$上得到一些$g^-$，

3.1 - Linear Blending

$Linear\ Blending$

1. 将数据分为$train\ data$和$validation\ data$
2. 从$D_{train}$得到$g_1^-, g_2^-, \cdots, g_T^-$
3. 将$D_{val}$中的数据$(x_n, y_n)$利用$g_1^-, g_2^-, \cdots, g_T^-$这些“特征转换”变换为$(z_n = \Phi^-(x_n), y_n)$，其中$\Phi^-(x) = (g_1^-(x), \cdots, g^-_T(x))$
4. 利用线性模型求解资料$\{(z_n, y_n)\}$上的$\alpha$，$\alpha = Lin(\{(z_n, y_n)\})$
5. 返回最后的结果$G_{LinB}(x) = Lin(innerprob(\alpha, \Phi(x)))$，

需要注意的是，$\Phi(x) = (g_1(x), \cdots, g_T(x))$

3.2 - Any Blending

在第4步中，我们也可以考虑不使用线性模型，而是使用非线性的模型$(nonlinear\ SVM)$，这样的方式称为Any Blending或者Stacking。

$Any\ Blending$

1. 将数据分为$train\ data$和$validation\ data$
2. 从$D_{train}$得到$g_1^-, g_2^-, \cdots, g_T^-$
3. 将$D_{val}$中的数据$(x_n, y_n)$利用$g_1^-, g_2^-, \cdots, g_T^-$这些“特征转换”变换为$(z_n = \Phi^-(x_n), y_n)$，其中$\Phi^-(x) = (g_1^-(x), \cdots, g^-_T(x))$
4. $g = Any(\{(z_n, y_n)\})$
5. 返回$G_{anyB} = g(\Phi(x))$

这样模型会更加的$powerful$，但是同时也更加容易$overfitting$。所以$any\ blending$要非常的小心， 要加$regularization$等等。

4 - Bagging (Bootstrap Aggregation)

如果已经通过某些方法得到了很多的$g$，我们可以通过$blending$的方式将它们融合起来，使得最后的分类器表现的很好。如果每一个$g$的权重（票数）是相同的， 那么可以得到$uniform\ blending$的$aggregation$方式；如果权重不是相同的， 那么就得到了$linear\ blending$；如果想要得到更为复杂的模型，在考虑在不同的模型下使用不同的权重的话，可以使用$stacking$来做。

这里有有一个很关键和很基础的问题是，这些$g$是怎么来的呢，我们是不是可以一边学习$g$，一边对它们进行融合。这是我们接下来要谈论的问题。因为$aggregation$在$g$非常的$diverse$的时候会做的很好，所以我们就考虑怎么样可以得到不一样的$g$呢？

• 不同的模型可能会得到不同的$g$
  • 对于用一个模型，不同的参数可能会得到不同的模型：例如对于$GD$算法来说，当$\eta = 0.001, 0.01, 0.1 \cdots 10$的时候会得到不同的模型。
  • • 不同的初始值可能会得到不同的模型，例如$PLA$算法
    • 资料的不同可以得到不同的模型，例如当在做$cross\ validation$的时候，不用的几份数据可能会得到不同的$g$。

    接下来我们使用的方式是使用同一份资料来制作不用的$g$（不同于$cross\ validation$只能得到不同的$g^-$），利用的工具称为$bootstrapping$，它的作用是从手上已有的资料来模拟一些不一样的资料。

    4.1 - Bootstrapping Aggregation

    bootstrapping：从原有的$N$笔资料中做$N$次有放回的采样（$sampling\ with\ replacement$）。既然是有放回的，那么就可能存在原资料中的某一笔被采样到了多次，或者一次都没有被采样到的情形。通过$bootstrapping$这样的方式得到的资料记为$\tilde D_t$。

    $bagging（bootstrap\ aggregation）$

    1. 通过$bootstrapping$的方式抽取大小为$N'$的资料$\tilde D_t$
    2. 从资料$\tilde D_t$利用算法$\mathcal{A}$中得到不同的$g_t$
    3. 对$g_t$做融合 $G(x) = Uniform(\{g_t\})$

    这样的方法我们称为$bootstrap\ aggregation$， 一般我们称之为$BAGging$。我们把底层的算法$\mathcal{A}$称为$base\ algorithm$，建筑在其上的演算法称为$meta\ algorithm$。

    $Bagging$通过利用$bootstrap$这样的机制生出一系列的$g$， 然后使用$uniform$的方式进行$aggregation$ 。

    4.2 - Bagging Pocket的表现

    由于$pocket$算法对于不同的资料表现会有很不同，如下图中的灰色的线是使用$pocket$算法在利用$boostrap$机制得到的25组不同的资料上得到的25条不同的线。通过将这些线进行融合得到了一个非线性的边界，如图中黑色的线所示。

    
    

    如果算法$base\ algorithm$ $\mathcal{A}$对于数据的随机性越敏感，那么就会得到越多样性的$g$，这样通过$aggregation$的方式融合起来就会得到更好表现。

    5 - 总结

    这篇主要是$aggregation$的基础概念和方法的介绍。提到了$blending$和$bagging$，它们都属于$aggregation$的方法。$aggregation$就是要把一堆的$g$通过一定的方式进行融合变成一个$G$， 这个$G$可能更复杂，或者可能更“中庸”,这样就可能达到了$feature\ transform$或者是$regularization$的效果。 其中有一些基本的方式，例如$uniform\ blending$；或者稍微复杂的$linear\ blending$和$any\ blending（stacking）$，这些可以通过$two\ level\ learning$的求解其中的权重。 最后我们介绍了怎么通过$bootstrapping$的机制得到不同的 g g <script type="math/tex" id="MathJax-Element-900">g</script>来对它们进行融合。