机器学习技法笔记(9)-Blending and Bagging(模型融合)

文章目录
  1. 为什么要进行模型融合
  2. Uniform Blending(均匀融合)
  3. Linear Blending(线性融合)
  4. Bootstrap Aggregation(Bagging)

前面的课程着重介绍某单一模型,比如逻辑回归,SVM等,从这一节开始以及接下来的3,4节的课程都是在介绍多个模型之间的融合得到一个新的模型的问题。

为什么要进行模型融合

我们针对某个问题,使用不同的演算法得到了很多模型g,个模型都会有自己擅长的部分,也有不擅长的部分,如果能够可以把它们混合起来,那新模型的效果就可能很好。假设我们已经得到了\(g_1,g_2,...,g_T\)等T个model,那我们怎么把它们混合为一个新的模型呢\(G(x)\)?方法很多,例如:

  • 最简单的,直接在所有的模型里面,选择验证误差最小的作为最后的模型: \(G(\mathbf x)=\arg\min\limits_{t \in {1,2,..T}} E_{val}(g_t^{-})\)
  • 直接采取所有\(g_t\)的意见,对它们同等信任,比如分类问题: \(G(\mathbf x) = sign(\sum\limits_{t=1}^{T}1 \cdot g_t(\mathbf x))\)
  • 比上一种情况,再更近一层,给每个\(g\)不同的投票数目,也就是说它们权重不再相同\(G(\mathbf x)=sign(\sum\limits_{t=1}^T\alpha_t \cdot g_t(\mathbf x))\),这个权重\(\alpha_t \geq 0\)可以通过训练得到。
  • 再特殊一点,根据不同的数据的特点,来赋予不同的权重: \(G(\mathbf x)=sign(\sum\limits_{t=1}^Tq_t(\mathbf x) \cdot g_t(\mathbf x))\), 其中\(q_t \geq 0\)

除了上面的四种融合之外,还有很多其它的没有列举出来。其中第一种就是前面基石课程中的模型选择的做法,此外这里的\(g_{t}^{-}(\mathbf x)\)是指在减去了验证数据集之后的数据作为训练数据得到的模型。

换句话说,有几个很weak的假设空间,通过融合等手段,得到一个更加powerful的假设空间,从而得到效果更好的模型,如下:

比如我们有一些只能划分水平与竖直方向的分界线的假设空间,如上图中的灰色的线,分类效果肯定很差,但是如果将这些弱的分类器组合起来,就可以得到一个不错的边界,如上图的黑色的线。因此看起来如果对多个模型进行一个合适的融合(aggregaton),或许就可以得到效果更好的模型。

Uniform Blending(均匀融合)

这一部分从误差的角度介绍最基本的Uniform Blending(均匀融合)的一些理论依据,Uniform Blending的分类的模型如下,实际上就是少数服从多数的原则:

\[G(\mathbf x)=sign \left( \sum\limits_{t=1}^{T}1 \cdot g_t(\mathbf x)\right)\]

回归模型如下,直接求T个模型g的结果的平均值:

\[G(\mathbf x)= {1\over T}\sum\limits_{t=1}^{T}1 \cdot g_t(\mathbf x)\]

下面以回归问题分析误差。

预期\(g_1,g_2,\cdots,g_T\)的效果应该参差不齐,比如一些\(g(\mathbf x)<f(\mathbf x)\),还有一些\(g(\mathbf x) > f(\mathbf x)\),这里的\(f(\mathbf x)\)是理想的未知的函数,这样通过融合平均下来得到的结果会更加准确。反过来,如果每个\(g\)的结果都差不多,那就没有必要做融合了。下面来分析融合前后的误差比较。

比较\(g_t\)\(f\)的均方误差与融合之后的\(G\)\(f\)的均方误差:

关于上述式子的展开有几个细节需要注意:

  • \(avg(g_t) = {1\over T}\sum g_t = G\)
  • f与avg无关

这样我们就可以得到下面的结论,(如果没有看过基石课程的话,这里的\(E_{out}\)可以理解为g与f的差距平方):

\[avg(E_{out}(g_t)) \geq E_{out}(G)\]

可以看出\(g_t\)的平均误差比融合之后的\(G\)要大,也就是说融合模型效果应该会更好。

基于上述的证明,现在考虑一个假想的极限情况,假设我们每次从数据分布中拿出N个数据\(\mathcal{D}_t\),然后通过演算法\(\mathcal {A(D_t)}\)得到\(g_t\),(因为每次的数据\(D_t\)都不一样,因此每个\(g\)的差别也就会变大,这也正是我们所期望的,得到不同给的模型)。如果数量T趋向于无穷大,我们就可以得到一个理想的\(\overline{g}\),它可以被认为在所有的数据得到的模型,可以体现出演算法\(\mathcal A\)的在所有的\(\mathcal D\)中的表现了

应用上面的结论,有:

其中\(\overline{g}\)可以代表一堆\(g_t\)的达成的共识(consensus)。式子的第一部分称为我们的演算法\(\mathcal A\)的在不同的数据集上\(D_1,...D_T\)的平均表现,右边式子\(E_{out}(\overline g)\)的第二部分就是共识的误差,一般称为 bias,描述的是共识与理想函数f的差距;第一部分\(avg\)则描述的是一种方差,\(g_t\)\(\overline g\)的平均差别,一般叫做variance, 因此衡量一个演算法的表现,就是bias+varience。 那么我们的Uniform Blending其实就是减少varience的过程。

关于这部分\(\mathcal {A,D},g\)等概念,请见机器学习基石笔记

Linear Blending(线性融合)

上面的均匀融合每个g的作用相同,最后的模型可能会变得中庸一些,稍加改变,如果每个g都一个不同的投票权重,效果应该就会更好,这就是线性融合(Linear Blending):

假设我们已经得到了T个\(g_t\),那么应该如何确定\(\alpha_t\)呢,思路就是\(\min E_{in}\),这个式子之前其实遇到过,回想在Linear Regression+Transformation的情况,使用均方误差:

再看看Linear Blending的做回归时候的目标函数:

二者其实是很类似的,我们也可以将\(g_t(\mathbf x)\)作为一种feature transform,这样我们将原始数据转换为: \((\mathbf z_n, y_n), \mathbf z_n=(g_1(\mathbf x_n),...,\mathbf g_T(\mathbf x_n))\),从这个角度来看与Linear Regression就完全一样了,这时候就可以直接用线性回归的方式来求解\(\alpha\)

然而有一点需要注意的是,Linear Blending有一个约束\(\alpha_t \geq 0\),因为每个模型的投票数不能为负数,而Linear Regression则没有这个约束。其实可以从这角度考虑,来去掉这个限制。对于那些\(\alpha_t < 0\),我们可以认为是\(\alpha_t g_t = |\alpha_t|(-g_t)\),这样就没有问题了,在物理意义上也可以解释,比如在一个分类问题中,对于那些效果很差的g,我们取其相反数,那么就可以得到一个好的g。到此,Linear Blending 与 Linear Regression + Feature Transform 等价了。

求出了\(\alpha\),我们还需要注意下如何选择一堆的\(g_t\):

\[g_1 \in \mathcal H_1, g_2 \in \mathcal H_2...g_T \in \mathcal{H}_T\]

一种思路是求出每个\(\mathcal H_t\)\(E_{in}\)最小的\(g\),第二种则是\(E_{val}\)最小的\(g^{-}\),显然为了防止过拟合,应该使用\(g^{-}\)

注: \(g^{}-\)就是使用总数据的N-K个数据做训练,然后用K个数据做验证,选择验证中err最小的g,而非训练误差最小的g。

简单总结下Linear Blending的流程:

  • 通过\(\min E_{val}\)的方式训练得到T个\(g^{-}\)
  • "特征转化": \(\mathbf z_n = \phi^{-}(\mathbf x_n) = (g_1^{-}(\mathbf x_n), g_2^{-}(\mathbf x_n)...g_{T}^{-}(\mathbf x_n))\),数据变为\((z_n, y_n)\)
  • Blengding: 计算\(\alpha\), 现在是一个很简单的线性问题了,通过之前的线性回归,逻辑回归等方法得到投票权重
  • 最终的模型: \(G(\mathbf x)=LinearModel(\sum\limits_{n=1}^{N}\alpha^T \phi(\mathbf x))\)

注: 最后的\(\phi=(g_1,g_2....)\)而非\(g^{-}\),因为通常,使用N-K个数据训练得到\(\min E_{val}\)得到最好的\(g^{-}\),之后,一般再用全部的N个数据重新训练一遍,得到\(g\),因为一般数据量越大,模型泛化性能就好.

其实除了Linear Blending之外,在得到\((z_n, y_n)\)之后,完全可以用一些其它的非线性的模型去解决这个分类或者回归问题,这样可能更加Powerful,但是也就更容易过拟合,因此还是那句话: Linear First。

模型融合在实际数据挖掘中,还是很常用的。在2011的KDDCup上,林老师的台大队伍最后加了使用测试数据的linear blending在比赛封榜最后一个小时,成功逆袭,从第二成为第一,夺得冠军。

Bootstrap Aggregation(Bagging)

前面的一堆的\(g\)是通过很多份数据来得到的,但是如果我们只有一份数据呢,也就是只有N个样例,怎么来得到区分度更好的\(g\)呢,下面利用一种叫Bootstrap的采样方式来利用已有的数据来采样得到新的数据集。

Bootstrapping: 在已有的\(\mathcal D\)中每次有放回的取样,重复N次,得到一组数据\(D_t^{t}\), 包含N个样例,这个采样过程便叫做Bootstrap

上面的原理很简单,这样得到的每个\(D_t\)中有很大的可能出现重复数据,不过这个不影响,反正我们有很多的\(g\),之后再用上面的Blending的方式进行Aggregation,这种方式一般叫做 Bootstrap Aggregation,通常简称Bagging。 这种方式在实际中应用很多,尤其是数据不足的情况下。

这部分与机器学习基石课程中的一些基础的理论有很大的关系,包括算法,模型,假设空间, \(E_{in}, E_{out}\)等概念,还有validation的过程等。 可能是因为这部分还没有写代码实践,因此理解的可能还不到位,整理的有点乱,希望能看到这里的同学多指正。