PRML读书会第十四章CombiningModels（committees，Boosting，AdaBoost，决策树，条件混合模型）...

主讲人 网神

&＃xff08;新浪微博: &＃64;豆角茄子麻酱凉面&＃xff09;

网神(66707180) 18:57:18 

大家好&＃xff0c;今天我们讲一下第14章combining models&＃xff0c;这一章是联合模型&＃xff0c;通过将多个模型以某种形式结合起来&＃xff0c;可以获得比单个模型更好的预测效果。包括这几部分&＃xff1a;
committees, 训练多个不同的模型&＃xff0c;取其平均值作为最终预测值。

boosting: 是committees的特殊形式&＃xff0c;顺序训练L个模型&＃xff0c;每个模型的训练依赖前一个模型的训练结果。
决策树&＃xff1a;不同模型负责输入变量的不同区间的预测&＃xff0c;每个样本选择一个模型来预测&＃xff0c;选择过程就像在树结构中从顶到叶子的遍历。
conditional mixture model条件混合模型&＃xff1a;引入概率机制来选择不同模型对某个样本做预测&＃xff0c;相比决策树的硬性选择&＃xff0c;要有很多优势。

本章主要介绍了这几种混合模型。讲之前&＃xff0c;先明确一下混合模型与Bayesian model averaging的区别&＃xff0c;贝叶斯模型平均是这样的&＃xff1a;假设有H个不同模型h&＃xff0c;每个模型的先验概率是p(h)&＃xff0c;一个数据集的分布是&＃xff1a;
整个数据集X是由一个模型生成的&＃xff0c;关于h的概率仅仅表示是由哪个模型来生成的 这件事的不确定性。而本章要讲的混合模型是数据集中&＃xff0c;不同的数据点可能由不同模型生成。看后面讲到的内容就明白了。
首先看committes&＃xff0c;committes是一大类&＃xff0c;包括boosting&＃xff0c;首先将最简单的形式&＃xff0c;就是讲多个模型的预测的平均值作为最后的预测。主要讲这么做的合理性&＃xff0c;为什么这么做会提高预测性能。从频率角度的概念&＃xff0c;bias-variance trade-off可以解释&＃xff0c;这个理论在3.5节讲过&＃xff0c;我们把这个经典的图copy过来&＃xff1a;

这个图大家都记得吧&＃xff0c;左边一列是对多组数据分别训练得到一个模型&＃xff0c;对应一条sin曲线&＃xff0c;看左下角这个图&＃xff0c;正则参数lamda取得比较小&＃xff0c;得到一个bias很小&＃xff0c;variance很大的一个模型 。每条线的variance都很大&＃xff0c;这样模型预测的错误就比较大&＃xff0c;但是把这么多条曲线取一个平均值&＃xff0c;得到右下角图上的红色线&＃xff0c;红色线跟真实sin曲线也就是蓝色线 基本拟合。所以用平均之后模型来预测&＃xff0c;variance准确率就提高了很多&＃xff0c;这是直观上来看&＃xff0c;接下里从数学公式推导看下&＃xff1a;
有一个数据集&＃xff0c;用bootstrap方法构造M个不同的训练集bootstrap方法就是从数据集中随机选N个放到训练集中&＃xff0c;做M次&＃xff0c;就得到M个训练集&＃xff0c;M个训练集训练的到M个模型&＃xff0c;用表示&＃xff0c;那么用committees方法&＃xff0c;对于某个x&＃xff0c;最终预测值是:

我们来看这个预测值是如何比单个预测值准确的&＃xff0c;假设准确的预测模型是h(x)&＃xff0c;那么训练得到的y(x)跟h(x)的关系是&＃xff1a;

后面那一项是模型的error
ZealotMaster(850458544) 19:24:34 
能使error趋近于0嘛&＃xff1f;
网神(66707180) 19:25:13 
模型越好越趋近于0&＃xff0c;但很难等于0&＃xff0c;这里committes方法就比单个模型更趋近于0
ZealotMaster(850458544) 19:25:28 
求证明
网神(66707180) 19:25:39 
正在证明&＃xff0c;平均平方和错误如下&＃xff1a;

也就是单个模型的期望error是&＃xff1a;

如果用M个模型分别做预测&＃xff0c;其平均错误是:

而如果用committes的结果来做预测&＃xff0c;其期望错误是&＃xff1a;

这个跑到了平方的里面&＃xff0c;如果假设不同模型的error都是0均值&＃xff0c;并且互不相关&＃xff0c;也就是&＃xff1a;

就可以得到&＃xff1a;

在不同模型error互不相关的假设的下&＃xff0c;committes错误是单个模型error的1/M&＃xff0c;但实际上&＃xff0c;不同模型的error通常是相关的&＃xff0c;因此error不会减少这么多&＃xff0c;但肯定是小于单个模型的error&＃xff0c;接下来讲boosting&＃xff0c;可以不考虑那个假设&＃xff0c;取得实质的提高.boosting应该是有不同的变种&＃xff0c;其中最出名的就是AdaBoost, adaptive boosting. 它可以将多个弱分类器结合&＃xff0c;取得很好的预测效果&＃xff0c;所谓弱分类器就是&＃xff0c;只要比随即预测强一点&＃xff0c;大概就是只要准确率超50%就行吧&＃xff0c;这是我的理解。
boosting的思想是依次预测每个分类器&＃xff0c;每个分类器训练时&＃xff0c;对每个数据点加一个权重。训练完一个分类器模型&＃xff0c;该模型分错的&＃xff0c;再下一个模型训练时&＃xff0c;增大权重&＃xff1b;分对的&＃xff0c;减少权重&＃xff0c;具体的算法如下&＃xff0c;我把整个算法帖出来&＃xff0c;再逐步解释&＃xff1a;

大家看下面这个图比较形象&＃xff1a;

第一步&＃xff0c;初始化每个数据点的权重为1/N.接下来依次训练M个分类器&＃xff0c;每个分类器训练时&＃xff0c;最小化加权的错误函数(14.15)&＃xff0c;错误函数看上面贴的算法&＃xff0c;从这个错误函数可以看出&＃xff0c;权重相同时&＃xff0c;尽量让更多的x分类正确&＃xff0c;权重不同时&＃xff0c;优先让权重大的x分类正确&＃xff0c;训练完一个模型后&＃xff0c;式(14.16)计算&＃xff0c;既分类错误的样本的加权比例. 然后式(14.17)计算:

只要分类器准确率大于50%&＃xff0c;就小于0.5, 就大于0。而且越小(既对应的分类器准确率越高)&＃xff0c;就越大&＃xff0c;然后用更新每个数据点的权重&＃xff0c;即式(14.18)&＃xff1a;

可以看出&＃xff0c;对于分类错误的数据点&＃xff0c;大于0&＃xff0c;所以exp(a)就大于1&＃xff0c;所以权重变大。但是从这个式子看不出&＃xff0c;对于分类正确的样本&＃xff0c;权重变小。这个式子表明&＃xff0c;分类正确的样本&＃xff0c;其权重不变 &＃xff0c;因为exp(0)&＃61;1.这是个疑问。如此循环&＃xff0c;训练完所有模型&＃xff0c;最后用式(14.19)做预测:

从上面过程可以看出&＃xff0c;如果训练集合中某个样本在逐步训练每个模型时&＃xff0c;一直被分错&＃xff0c;他的权重就会一直变大&＃xff0c;最后对应的也越来越大&＃xff0c;下面看一个图例&＃xff1a;

图中有蓝红两类样本 &＃xff0c;分类器是单个的平行于轴线的阈值 &＃xff0c;第一个分类器(m&＃61;1)把大部分点分对了&＃xff0c;但有2个蓝点&＃xff0c;3个红点不对&＃xff0c;m&＃61;2时&＃xff0c;这几个错的就变大了&＃xff0c;圈越大&＃xff0c;对应其权重越大 &＃xff0c;后面的分类器似乎是专门为了这个几个错分点而在努力工作&＃xff0c;经过150个分类器&＃xff0c;右下角那个图的分割线已经很乱了&＃xff0c;看不出到底对不对 &＃xff0c;应该是都已经分对了吧。
网神(66707180) 19:59:59 
&＃64;ZealotMaster 不知道是否明白点了&＃xff0c;大家有啥问题&＃xff1f;
ZealotMaster(850458544) 20:00:14 
嗯&＃xff0c;清晰一些了&＃xff0c;这个也涉及over fitting嘛&＃xff1f;感觉m&＃61;150好乱……
苦瓜炒鸡蛋(852383636) 20:02:23 
是过拟合
网神(66707180) 20:02:25

不同的分割线&＃xff0c;也就是不同的模型&＃xff0c;是主要针对不同的点的&＃xff0c;针对哪些点&＃xff0c;由模型组合时的系数来影响。
苦瓜炒鸡蛋(852383636) 20:04:50 

这是韩家炜 那个数据挖掘书的那一段&＃xff1a;
网神(66707180) 20:04:56 
嗯&＃xff0c;这章后面也讲到了boosting对某些错分的样本反应太大&＃xff0c;一些异常点会对模型造成很大的影响。

&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;

接下来讲boosting的错误函数&＃xff0c;我们仔细看下对boosting错误函数的分析&＃xff0c;boosting最初用统计学习理论来分析器泛化错误的边界bound&＃xff0c;但后来发现这个bound太松&＃xff0c;没有意义。实际性能比这个理论边界好得多&＃xff0c;后来用指数错误函数来表示。从优化指数损失函数来解释adaboost比较直观&＃xff0c;每次固定其他分类器和系数将常量分出来&＃xff0c;能推出单分类器的损失函数及系数&＃xff0c;再根据常量的形式能得出下一步数据权重的更新方式。指数错误函数如下&＃xff1a;

其中N是N个样本点&＃xff0c;是多个线性分类器的线性组合:

是分类的目标值。我们的目标是训练系数和分类器的参数&＃xff0c;使E最小。
最小化E的方法&＃xff0c;是先只针对一个分类器进行最小化&＃xff0c;而固定其他分类器的参数&＃xff0c;例如我们固定和其系数&＃xff0c;只针对做优化&＃xff0c;这样错误函数E可以改写为&＃xff1a;

也就是把固定的分类器的部分都当做一个常量&＃xff1a;&＃xff0c;只保留相关的部分。我们用表示分对的数据集&＃xff0c;表示分错的数据集&＃xff0c;E又可以写成如下形式&＃xff1a;
上式中&＃xff0c;因为将数据分成两部分&＃xff0c;也就确定了个是否相等&＃xff0c;所以消去了这两个变量
看起来清爽点了&＃xff1a;

这里面后一项是常量&＃xff0c;前一项就跟前面boosting的算法里所用的错误函数&＃xff1a;形式一样了。

上面是将&＃xff1a;对做最小化得出的结论,即指数错误函数就是boosting里求单个模型时所用的错误函数.类似&＃xff0c;也可以得到指数错误函数里的就是boosting里的&＃xff0c;确定了根据以及

可以得到&＃xff0c;更新w的方法&＃xff1a;

又因为有&＃xff1a;这又跟boosting里更新数据点权重的方法以一致。
总之&＃xff0c;就是想说明&＃xff0c;用指数错误函数可以描述boosting的error分析,接下来看看指数错误函数的性质&＃xff0c;再贴一下指数错误函数的形式&＃xff1a;

其期望error是&＃xff1a;

然后最所有的y(x)做variational minimization,得到&＃xff1a; 
这是half the log-odds &＃xff0c;看下指数错误函数的图形&＃xff1a;


绿色的线是指数错误函数可以看到&＃xff0c;对于分错的情况&＃xff0c;既z<0时&＃xff0c;绿色的线呈指数趋势上升&＃xff0c;所以异常点会对训练结果的影响很大。图中红色的线是corss-entropy 错误&＃xff0c;是逻辑分类中用的错误函数&＃xff0c;对分错的情况&＃xff0c;随错误变大&＃xff0c;其函数值基本是线性增加的&＃xff0c;蓝色线是svm用的错误函数&＃xff0c;叫hinge 函数。

PRML读书会讲稿PDF版本以及更多资源下载地址&＃xff1a;http://vdisk.weibo.com/u/1841149974