加载中…
个人资料
yfx416
yfx416
  • 博客等级:
  • 博客积分:0
  • 博客访问:103,799
  • 关注人气:75
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Probably approximately correct learning

(2011-10-02 22:41:30)
标签:

样本

误判率

学习方法

学习机

误差

分类: 数据挖掘

Probably approximately correct learning, 简称PAC学习,用来指代一类学习机.在这类学习机中,我们的样本往往遵从一种分布,我们的目标就是估计这种分布.假设我们估计出了这种分布,称之为H,那么我们希望在这种分布假设H的情况下,样本出现的概率尽可能的高,同时H与真实的样本分布的误差比较小.(想想最大似然估计)

这样说可能比较晦涩,举个例子吧.我们假设要学习一个回归树,我们用它来预测某些对象的值.我们有一些训练样本,我们的任务是通过学习这个训练样本来学习出这个分类树.然而由于我们训练的时候可能采用了训练样本的不同部分,或者说训练方法中的一些随机变量的影响(比如样本的读取顺序),会导致我们的分类树不是某一个确定的分类树,而是可能的一类分类树(a certain class of possible functions),这类分类树都是基于某一个学习方法从这些样本中生成的.所以说这个分类方法的产生的分类树遵循着一种分布,我们的分类方法是这类分类树的一种泛化.我们选取另外一批样本作为验证样本,把这一类分类树应用到这些验证样本中,我们可以得到一组误差(比如误判率),这类分类树中的每一个分类树都对应一个误差(误判率).我们设置一个误差阈值,如果这类分类树中的大部分的分类树的误差都比阈值小,那么这个学习方法就比较理想了,反之,这样的学习方法就比较差.

定义:

EX(c,D)用来描述样本,D表示样本x的分布,c(x)用来表述样本的正确分类

所谓PAC learner,是指如果基于数据样本EX(c,D),对任意的满足0<threshHold_error,threshHold_pro < 0.5条件的误差(比如误判率)阈值threshHold_erro和概率阈值threshHold_pro,如果有一个学习方法(比如CART分类法),它产生一组可能的分类树集合(就是上文中的一类分类树),针对验证样本所有的特征,都能保证误判率低于threshHold_error的分类树在这类分类树集合的概率是大于1-threshHold_pro的,那么我们就可以说这个学习方法是PAC learner.如果该算法的运行时间与1/threshHold_error,1/threshHold_pro成多项式关系,那么该算法可以称之为强PAC学习机。

如果只有某对threshHold_error,threshHold_pro 满足上述方法,称之为弱学习机。

PAC是boosting算法的理论基础。

参考:

[1] http://en.wikipedia.org/wiki/Probably_approximately_correct_learning

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有