Machine Learning Techniques Lecture 7: Blending and Bagging | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 7: Blending and Bagging


 
 

内容:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 


 
 

我们之前讲到的是Kernel Model,做的事情是把很多很多的feature包在kernel里面,然后用不同的机制去求解。我们把kernel model延伸到可以做regression,你可以把原来知道的ridge regression利用representer theorem来得到他的kernel的形式,你也可以参考SVM设计一个新的formulation来得到sparse solution 的Kernel 形式。

 
 

今天开启一个新的主题,如果我们得到了一些hypothesis,这些hypothesis可以帮助我们做预测,我们怎么把这些有预测性的hypothesis合起来让他们变得更好,这样的模型叫做Aggregation model。今天讲两个常用的model,blending and bagging。

 
 


 
 

先来想想为什么想要用aggrregation?

假设今天你有15个朋友,每个人都告诉你明天股市的涨跌预测分析,那你听了以后作的决策是什么。

 
 

你的决策想法可能会有:

  1. 你的朋友里面有人炒股比较厉害,可能他的预测比较有参考价值,因此选择一个可以信赖的人的结果。(就是validation)
  2. 你的朋友每个人都有不同的专长,不知道相信谁,投票决定,看猜测涨的人多就决定相信涨。
  3. 如果你的朋友的炒股能力可以参数化,那就是加权投票看结果。
  4. 你的朋友有的人擅长科技类股票,有的人擅长能源类股票等等,所以呢在不同的条件之下就相信不同的人。

 
 

我们要做的就是把这些情境的处理对应到机器学习里面。做的这件事就是叫做 aggregation model 在做的事情。

 
 


 
 

我们把上面的口语化的表述数学化。

 
 

每个朋友就是 hypothesis 就是 g_n;

  1. 就是选Err_val最小的
  2. Uniformly 和
  3. Non-uniformly 加权和
  4. 函数代表了成立条件再乘以g_n

从一到四更加的泛化,2包含1,3包含2,4包含3。

 
 

Aggregation model 就是这么非常包山包海的丰富,未来的五讲会分别去在各个方向作介绍。

 
 


 
 

先来看比较简单的,比如靠的是selection,从里面选一个最好的。

黄色框就是公式表示,其实在前面的validation的时候的方法就是用到了selection,选一个最好的。

我们使用training error而不是使用validation error是否可以?很危险,非常可能overfitting。

这种方式里面的一个重要假设是:你想要选到一个好的g^-_t最后才能够选到好的。如果你的候选结果都是不好的,那就是废渣里面再怎么选也是废渣。

 
 

如果只靠选择的话,我们只要有一个强者就好了。

但是aggregation想象的是如果今天我们一堆看起来弱弱的,但是其实还算是可以的hypothesis,我们能够不能依靠集体的智慧让最终结果变得更好。也就是说不是靠一个很强的来做最终结果。

 
 


 
 

先来思考一下为什么aggregation可以做得更好?

 
 

先看左边的图,如果要求只能用水平垂直的线来分类,单个怎么样都做得不大好,如果多条水平垂直的线合起来,那么就有左图的折线,把圈圈叉叉完美分开。可能代表aggregation相当于拓展了模型的分类能力。

如果今天有一堆hypothesis如右图,每一条结果都还不错,如果让灰色的线投票的话会很接近比较中庸的线,就如图中的黑色实线,也就大概比较宽的线。这可能代表了aggregation可以有regularization的能力。

也就是说aggregation同时具有让模型更加复杂和简单的能力,如果你能利用好的话,就能得到比较好的学习结果。

 
 


 
 

练习

 
 


 
 

下面我们开始讲怎么样把这些hypothesis合起来。

 
 

第一个概念: blending


Uniform Blending(voting) for classification

这一般使用在我们手上已经有一堆g,怎么把他们的结果合起来变的更强。黄色框表示的就是公式化的投票方式的结果的表述。如果你所有的小g大体都是相同的,那么你的大G也就和他们相同。如果你的一堆小g结果都很不同,怎么去融合?

如右边的图,在横竖分成区块后,每一个区块单独进行投票,少数服从多数,就得到了这个折线结果。也就是说如果今天分类结果很不一样,那么我们可以通过民主投票的机制来获得更加复杂的分类边界,对于多类别的分类也可以做一样的事情。

 
 


 
 

Uniform blending for regression

把大家的输出都通通的加起来求平均得到大G。如果小g统统都一样,这种方式没带来什么好处,但是如果小g比较不一样,可以抵消一些低估和高估,得到一个比较中庸的结果比较好。

 
 

从blending用在classification/regression看出,如果我们这个aggregation要起作用,很重要的是我们的小g要diverse,就是意见要有不一样,这样融合的家过会比较好。

 
 


 
 

我们来进一步分析为什么uniform blending为什么会表现更好?

 
 

x表示输入,在下面都是一样的,写着比较麻烦,就省略了,这里推到的目标是把单个的小g和f的平方错误 的平均 和 大G和f的平方错误联系在一起。

首先展开,再代入G替换一次小g平均,根据目标凑G-f平方,再凑一个大g小g平方,的结果。

蓝色框表示的是单一的小g的结果,如果是对所有的小g则是下面黄色框所示:所有的小g的E_out = 大G的E_out + 大小g的平均的期望值的差(这一项一定是正的)。所以小g的平均E_out要比大G来得大,所以就证明了uniform blending是有好处的。

 
 


 
 

如果今天有这么个抽象的机器学习过程,在每一轮里面有n笔资料,通过已有的演算法来求每一笔资料的小g,结果就是取小g的平均。把上面这件事做无限多次,求平均期望值。

灰色部分就是写出的式子

物理上的解释:演算法表现的期望值 = variance(小g的特性表现) + bias(小g的共识表现),在统计的书里面比较常见,平均的过程就是消除前面这一项,让意见趋于一致。

 
 


 
 

练习

 
 


 
 

接下来讲的是 linear blending (就是加权平均)

什么样是好得票数,能够达到E_in最低的是好的票数,也就是说我们要调整我们的alpha让Ein最低,限制是每一个alpha都是大于等于0的。

因此红色框表示的就是regression的时候的公式,换成后边的框所示,和我们之前讲过的 transform 过的 linear regression 差不多形式,区别在于有alpha>0的条件。也就是说整个学到好的alpha的过程,就是之前讲过的two-level learning,在probilitistic SVM的时候提到的。现在的two-level是先得到一堆g,在做linear regression得到alpha。

 
 


 
 

问题是有了alpha>=0的限制。

如果alpha<0,则表示的是结果是反的,所以把符号相反。举个例子比如你有一个算法做binary classification得到的结果可是说是得到的结果99%是错的,那么反过来用正确率就非常高。

所以真正在做linear blending的时候忽略这个constraint 也没啥问题。

 
 


 
 

还有个问题是小g通常是怎么来的呢?

从各自不同的model通过求最好的E_in得到的。以前曾经提到过如果你选择模型的时候用的也是E_in的时候,你选的是best of best,你要付出的代价很大,所以后来说为什么我们要用validation而不是Ein来做选择。(譬如你要选的是两个班的第一名,你要付出的代价是查询两个班的结果)

这边类似,linear bendling包含了selection,alpha是说到底我的validationerror有没有最小。也就是说如果你用E_in来做blending,你现在选的是把所有的第一名集合起来做,你要付出的代价比best of best还要高(因为你包含best of best当作你的特例),也就是更危险。因此通常我们不建议使用Ein来学alpha,因为很容易就overfit了。【就是说g用了Ein学,alpha不要用Ein再来确定了】

这里建议在算alpha的时候,不要用training的Ein来算,而是采用E_validation来操作。

 
 


 
 

因此真正的操作过程【就是只从用来验证的资料来确定alpha】:

 
 

从一个比较小的Dtrain得到你的一堆g-,然后把你的validation set里面的资料透过这些g-转换成z空间的资料,我们把这个转换叫做phine-。

做完转换后你就可以把你的linear model用在这些新的资料上面求出alpha,这时候G就是这些alpha和phine(x)的线性组合的内积。

这里用的是phine(x)而不是phine-(x)是因为我们希望透过phine,也就是真正的g而不是g-,来让我们的表现更好。

 
 

对于non-linear blending(stacking):同样是做完转换的资料z,不再用linear model,而是任何的model Any,学习到g,最后一样得到的是g和phine(x)的组合即是G回传回去。

Any-blending:模型能力强大,但更容易overfit,使用上要非常小心。

 
 


 
 

故事:

11年的时候KDDCup一个冠军的方法:先学到小g(single model),然后做any-blending,融合后变成一下更强的G,然后再做一次linear-blending,得到了最好的结果。

 
 


 
 

练习

 
 


 
 

Blending:如果你已经透过某些方法得到小g,我们怎么去合起来,我们可以非常公平的投票,也可以加权投票。

更多的时候你更想要知道小g到底是怎么来的,我们能不能一边学小g,一边把它合起来,下面我们会讨论这个问题。

我们首先来看什么时候可以得到不一样的小g:

  1. 从不一样的模型得到不一样的小g
  2. 同一个模型,不同的参数得到不同的小g
  3. 演算法本身就存在randomness产生的不同的小g
  4. 你的资料存在randomness产生的不同的小g

 
 

下面我们探讨能不能拿同一份资料来制造很多的小g?

 
 


 
 

我们回头来看之前推导的理论结果:Bias + variance 概念就是强化共识

前提是我们需要很多不同的资料来获得共识,但问题是我们这里考虑得是同一份资料,怎么处理呢?

 
 

我们的目标是无限多小g的平均,但是我们做不到,因为首先没有办法产生无限多,其次资料要是新鲜的也做不到,现在只有现存的一堆资料。

所以妥协:有限多的大量的数据,通过已有的资料产生长得像新鲜的资料的资料。

 
 

怎么做?

统计学工具:bootstrapping,从你手上已有的资料去模拟不一样的资料。

 
 


 
 

bootstrapping:

重新的从我手上的资料里面去取n笔,取一笔记录一下再放回去,再取一笔记录再放回去,以此类推。有放回的抽样得到的资料在统计学上叫做 bootstrap sample(D_t)。

 
 

Virtual aggregation:每一次找一个新的小D_t得到新的小g_t,最后平均

Bootstrap aggregation(又叫做bagging):每一次从手上资料生一个D_t得到新的g_t,最后平均

 
 

这是一个meta algorithm,就是可以附着在任何基本演算法基础上使用。

 
 


 
 

举例:

已有的资料做bootstrap后得到的资料集用Pocket 算法算出来的结果是浅灰色的线,生出了25条;然后把线合起来得到黑色的线,效果相对会比较好一点。

 
 

这边要注意的是:你的演算法对随机是敏感的,得到的小g越不一样,效果会比较好。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 

下一讲:

我们你能不能得到比bagging更不一样的hypothesis呢?

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags