机器学习技法-Blending and Bagging
大纲
上节课我们主要介绍了Support Vector Regression,将kernel model引入到regression中。首先,通过将ridge regression和representer theorem结合起来,得到kernel ridge regression。但是其解是dense的,即不部分不为零。为了得到sparse解,我们将regularized tube error和Lagrange dual结合起来,利用SVM dual的推导方法,得到support vector regression的sparse解。本系列1-6节课主要介绍Kernel Models及其应用,从本节课开始,讲介绍Aggregation Models,即如何将不同的hypothesis和features结合起来,让模型更好。本节课将介绍其中的两个方法,一个是Blending,一个是Bagging
Motivation of Aggregation
1 An Aggregation Story
假设你有T个朋友分别给你买股票的建议,对应的建议表示为
你可以选取一个对股票预测能力最强的人的建议
如果每个朋友在股票预测方面都是比较厉害的,都有各自的专长,那么就同时考虑T个朋友的建议,将所有结果做个投票,一人一票,最终决定出对该支股票的预测。
如果每个朋友水平不一,有的比较厉害,投票比重应该更大一些,有的比较差,投票比重应该更小一些。那么,仍然对T个朋友进行投票,只是每个人的投票权重不同。
第四种方法与第三种方法类似,但是权重不是固定的,根据不同的条件,给予不同的权重。比如如果是传统行业的股票,那么给这方面比较厉害的朋友较高的投票权重,如果是服务行业,那么就给这方面比较厉害的朋友较高的投票权重。
2 Aggregation with Math Notations
我们把每种方法都用数学化的形式来表示
-
第一种方法
G(x)=gt∗(x)with t∗=argmin{t∈1,2,...T}Eval(g−t) -
第二种方法
G(x)=sign(∑t=1T1⋅gt(x)) - 第三种方法
G(x)=sign(∑t=1Tαt cdotgt(x)) with αt≥0 - 第四种方法
G(x)=sign(∑t=1Tqt(x)⋅gt(x)) with qt(x)≥0
3 Recall: Selection by Validation
我们回顾一下第一种方法
简单并且常用
一般都是用验证集来挑选最佳模型,从而保证泛华能力
需要有一个强的
g−t 来保证小的Eval
第一种方法只是从众多可能的hypothesis中选择最好的模型,并不能发挥集体的智慧。而Aggregation的思想是博采众长,将可能的hypothesis优势集合起来,将集体智慧融合起来,使预测模型达到更好的效果。
4 Why Might Aggregation Work?
首先看左图,平面上分布着一些待分类的点。如果要求只能用一条水平的线或者垂直的线进行分类,那不论怎么选取直线,都达不到最佳的分类效果。这实际上就是上面介绍的第一种方法:validation。但是,如果可以使用集体智慧,比如一条水平线和两条垂直线组合而成的图中折线形式,就可以将所有的点完全分开,得到了最优化的预测模型。这个例子表明,通过将不同的hypotheses均匀地结合起来,得到了比单一hypothesis更好的预测模型。这就是aggregation的优势所在,它提高了预测模型的power,起到了特征转换(feature transform)的效果。
接着看右图,同样是平面上分布着一些待分类的点,使用PLA算法,可以得到很多满足条件的分类线,这无数条PLA选择出来的直线对应的hypothesis都是满足分类要求的。但是我们最想得到的分类直线是中间那条距离所有点都比较远的黑色直线,这与之前SVM目标是一致的。如果我们将所有可能的hypothesis结合起来,以投票的方式进行组合选择,最终会发现投票得到的分类线就是中间和黑色那条。这从哲学的角度来说,就是对各种效果较好的可能性进行组合,得到的结果一般是中庸的、最合适的,即对应图中那条黑色直线。所以,aggregation也起到了正则化(regularization)的效果,让预测模型更具有代表性。
基于以上的两个例子,我们得到了aggregation的两个优势:feature transform和regularization。我们之前在机器学习基石课程中就介绍过,feature transform和regularization是对立的,还把它们分别比作踩油门和踩刹车。如果进行feature transform,那么regularization的效果通常很差,反之亦然。也就是说,单一模型通常只能倾向于feature transform和regularization之一,在两者之间做个权衡。但是aggregation却能将feature transform和regularization各自的优势结合起来,好比把油门和刹车都控制得很好,从而得到不错的预测模型。
Uniform Blending
那对于我们已经选择的性能较好的一些
1 Uniform Blending (Voting) for Classification
第一种情况,如果每个候选的
gt 都差不多,那么Blending之后,跟任意一个单独的gt 效果都差不多第二种情况,如果候选的
gt 存在分歧,那么Blending之后,我们可以利用多数意见来修正少数意见,从而得到好的模型。第三种情况,如果是多分类问题,选择投票数最多的那一类即可
2 Uniform Blending for Regression
第一种情况是每个候选的
gt 都完全一样,这跟选其中任意一个gt 效果相同;第二种情况是每个候选的
gt 都有一些差别,有的gt>f(x) ,有的gt<f(x) ,此时求平均值的操作可能会消去这种大于和小于的影响,从而得到更好的回归模型。
分歧假设:如果每个候选的
3 Theoretical Analysis of Uniform Blending
考虑单个样本的情形,经过推导,我们发现
考虑全部样本,从结果上来看,
4 Some Special gt
我们考虑这样一个Blending过程
- 从某个分布中采样N个数据
- 利用演算法训练数据得到
gt g¯=limT⇒∞1T∑t=1Tgt=ξDA(D)
当
我们将不同
gt 的共识的误差,即Eout(g¯) 叫做偏差我们把
gt 与共识的差距是多少,反映gt 之间的偏差,用方差variance表示。
也就是说,一个演算法的平均表现可以被拆成两项。即bias和variance。而uniform blending的操作时求平均的过程,这样就削减弱化了上式第一项variance的值,从而演算法的表现就更好了,能得到更加稳定的表现。
Linear and Any Blending
1 Linear Blending
每个
如何确定
例如对于linear blending for regression,
我们也可以理解为两阶段学习,类似于以前我们学过的probabilistic SVM。这里,我们先计算
总得来说我们把linear Blending 看做线性模型+通过假设函数进行特征转换+约束
2 Constraint on αt
实践中我们通常省略约束条件
3 Linear Blending versus Selection
利用
4 Any Blending
我们一般利用训练集训练不同的基模型,然后利用验证集进行Blending.如下图所示
在Blending的过程中,我们不仅可以进行线性Blending,我们可以采用不同的模型进行Blending.这样得到的模型更加强大,可以实现conditional blending.但是要小心会过拟合。
5 Blending in Practice
Bagging(Bootstrap Aggregation)
1 What we have done
总结一些上面讲的内容,blending的做法就是将已经得到的
现在考虑一个问题:如何得到不同的
选取不同的模型
同一个模型选取不同的参数
算法的随机性
数据的随机性
2 Revisit of Bias-Variance
首先,我们回顾一下之前介绍的bias-variance,即一个演算法的平均表现可以被拆成两项,一个是所有
其中,
有限但大的T
由已有数据集D构造出
Dt∈PN ,独立同分布
3 Bootstrap Aggregation
bootstrapping的做法是,假设有N笔资料,先从中选出一个样本,再放回去,再选择一个样本,再放回去,共重复N次。这样我们就得到了一个新的N笔资料,这个新的
Bootstrap Aggregation是一个处于基算法之上的一种元算法
4 Bagging Pocket in Action
如图中黑线所示。可以看出,虽然bootstrapping会得到差别很大的分类线(灰线),但是经过blending后,得到的分类线效果是不错的,则bagging通常能得到最佳的分类模型。
如果基算法对于数据的随机性比较敏感,那么通常bagging会work