机器学习技法笔记 – Blending and Bagging(混合与装袋)

Motivation of Aggregation

本章将讨论Aggregation在已知Hypotheses上的应用,通过Mix(混合)或者Combine(组合),得到表现更加的Predictor和Classifier。

以下是四种Aggregation方式的例子:

  • Select with validation:

选择\(E_{in}\)最小的\(g_*(x)\),即经过Validation后表现最好的\(g(x)\):

  • Mix uniformly:

每个\(g(x)\)平权投票:

  • Mix non-uniformly:

每个\(g(x)\)非平权投票:

  • Combine conditionally:

每个\(g(x)\)的票数由一个\(q_t(x)\)决定:

为什么需要Aggregation?

假设我们现在有一些比较弱的Hypotheses,通过Aggregation,例如Mix uniformly,我们可以得到一个泛化能力更强的\(G(x)\),这个\(G(x)\)在数据集上的表现更好,如下图:

Uniform Blending

接下来我们将介绍一种Aggregation的方法,称之为Uniform Blending,即Mix uniformly,所有\(g(x)\)平权投票:

上式是Uniform Blending用于分类的形式,对于预测类的问题,Uniform Blending具有以下形式:

下面将给出证明来说明为什么Uniform Blending相对于单独的\(g(x)\)表现更好:

其中,\(avg\)可以视为\(\sum_{t=1}^{N} \frac{g_t(x)}{N}\),而\(G=\sum_{t=1}^{N} g_t(x)\)

所以有以下结论:

即Uniform Blending相对于单独的\(g(x)\)表现更好。

Linear and Any Blending

接下来介绍非平权投票的Aggregation方式,即Linear Blending:

上式的Cost Function如下:

通过最小化\(E_{in}\)即上式,求得最优的\(\alpha\)矩阵。

对于分类问题,约束\(\alpha_t≥0\),是可有可无的,因为如果求出的\(\alpha_n<0\),则只需要将\(g(x)\)取相反数即可。

上文介绍了\(\alpha\)矩阵的求解方法,它和求解一般的Linear Regression的思路大同小异,最后求得的\(\alpha\)矩阵是一个解析解。

通过在数据集上最小化\(E_{in}\)得到\(g_t(x)\)后,在最小化\(\alpha_n\)所带来的复杂度非常高。

这样可能会导致Overfitting。

通过以下方法可以一定程度降低Overfitting的风险。

首先将原始数据集分为\(D_{train}\)与\(D_{val}\),通过\(D_{train}\)训练得到\(g^-(x)\),然后让\(g^-(x)\)作用在\(D_{val}\)上,得到\(z_n = \phi^-(x) = \sum^{N}{t=1} g_t(x)\),这样一定程度避免了两次最小化\(E{in}\)可能造成的Overfitting。

上述Aggregation方法即是Linear Blending,如果需要更强大的泛化能力,可以在计算\(\phi^-(x)\)时采用更加复杂的模型。

这种方法即是Any Blending,但是具有更高的Overfitting风险。

Bagging

与Blending不同的是,Bagging不需要事先从数据集训练出各种\(g(x)\),而是一边训练,一边组合的。

对于如何训练出不同的\(g(x)\),通常有以下方法:

即从不同的模型训练得到、从不同的参数得到、从算法的随机性得到、从数据的随机性得到。

接下来我们将介绍一种从数据的随机性训练出不同的\(g(x)\)的方法,这种方法通过在数据集上随机选取N个数据,重复T次,在这N个数据中通过Pocket算法训练出\(g_t(x)\),然后将他们做Uniform Blending,得到最终的\(G(x)\),效果如下图:

我们可以发现通过这样的方法,依然可以做到非线性的分类,仍然具有不错的泛化能力。

以上是对Blending and Bagging在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Adaptive Boosting。