机器学习之概念学习
发布日期:2022-03-04 12:48:46 浏览次数:19 分类:技术文章

本文共 3414 字,大约阅读时间需要 11 分钟。

一.概念

概念学习:是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。

二.概念学习任务

任何概念学习任务能被描述为:实例的集合、实例集合上的目标函数、候选假设的集合以及训练样例的集合。

              EnjoySport概念学习任务

已知:

  实例集X:可能的日子,每个日子由下面的属性描述:

    sky:(可取值 sunny,Cloudy和Rainy)

    AirTemp:(可取值为Warm和Cold)

    Humidity:(可取值为Normal和High)

    Wind:(可取值为:Strong和Weak)

    Water:(可取值为Warm和Cold)

    Forecast:(可取值为Same和Change)

  假设集H:每个假设描述为6个属性:Sky,AirTemp,Humidity,Wind,Water和Forecast的值约束的合取。约束可以为“?”(表示接受任意值),“ø”(表示拒绝所有值),或一特定值

  目标概念C:EnjoySport: X->{0,1}

  训练样例集D:目标函数的正例和反例

求解:

  H中的一假设h,使对于X中任意x,h(x)=c(x)

 1.术语定义

实例集(X):概念定义的实例集合

目标概念(c):待学习概念或函数

训练样例(D):每个样例为X中的一个实例x以及它的目标概念值c(x)。c(x)=1的实例被称为正例(positive example),c(x)=0的实例为反例(negative example),经常用序偶<x,c(x)>来描述训练样例。

H表示所有可能假设的集合。H中每个假设H表示X上定义的布尔函数,即h:X->{0,1}。机器学习的目标就是寻找一个假设h,使对于X中的所有x,h(x)=c(x)。

归纳学习假设:任一假设如果在足够大的训练样例集中很好地逼近目标函数,它也能在未见实例中很好地逼近目标函数。

 三.作为搜索的概念学习

定义:令hj和hk为在X上定义的布尔函数。称hmore_general_than_or_equal_to hk(记做hjg hk当且仅当(∨x∈X)[(hk(x)=1)->(hj(x)=1)]

hj more_specific_than hk ,当hk more_general_than hj

四.FIND-S:寻找极大特殊假设

从H中最特殊假设开始,然后在该假设覆盖正例失败时将其一般化(当一假设能正确地划分一个正例时,称该假设“覆盖”该正例)。

                            FIND-S算法

   1. 将h初始化为H中最特殊假设

   2.对每个正例x

    对h的每个属性约束ai

    如果x满足ai

    那么不做任何处理

    否则将h中ai替换为x满足的下一个更一般的约束

     3. 输出假设h

五.变换空间和候选消除算法(CANDIDATE-ELIMINATION)

FIND-S输出的假设只是H中能够拟合训练样例的多个假设中的一个。而在候选消除算法中,输出的是与训练样例一致的所有假设的集合。

1.表示

定义:一个假设h与训练样例集合D一致,当且仅当对D中每一个样例<x,c(x)>都有h(x)=c(x)。

       Consistent(h,D)≡(∨<x,c(x)>∈D) h(x)=c(x)

定义:关于假设空间H和训练样例集D的变型空间,标记为VSH,D,是H中与训练样例D一致的所有假设构成的子集。

                     VSH,D≡{h∈H|Consistent(h,D)}

2.列表后消除算法(LIST-THEN-ELIMINATE)

                     列表后消除算法

      1.变型空间VersionSpace<-包含H中所有假设的列表

  2.对每个训练样例<x,c(x)>

    从变型空间中移除所有h(x)≠c(x)的假设h

      3. 输出VersionSpace中个假设列表

3.变型空间的更简洁表示

 

定义:关于假设空间H和训练数据D的一般边界(general boundary)G,是在H中与D相一致的极大一般(maximally general)成员的集合。

 

                     

定义:关于假设空间H和训练数据D的特殊边界(specific  boundary)S,是在H中与D相一致的极大特殊(maximally specific)成员的集合。

       

变型空间的确切组成是:G中包含的假设,S中包含的假设已经G和S直接偏序结果所规定的假设。

定理2.1:变型空间表示定理 令X为任意的实例集合,H为X上定义的布尔假设的集合。另c:X->{0,1}为X上定义的任一个目标概念,并令D为任一训练样例的集合{<x,c(x)>}。对所有的X,H,c,D以及良好定义的S和G:

       

4.候选消除学习算法

 

    使用变型空间的候选消除算法

 

将G集合初始化为H中极大一般假设

 

将S集合初始化为H中极大特殊假设

 

对每个训练例d,进行以下操作:

 

  • 如果d是一正例

 

      • 从G中移去所有与d不一致的假设

 

      • 对S中每个与d不一致的假设s

 

             •从S中移去s

 

      • 把s的所有的极小一般化式h加入到S中,其中h满足

 

             •h与d一致,而且G的某个成员比h更一般

 

      • 从S中移去所有这样的假设:它比S中另一假设更一般

 

  • 如果d是一个反例

 

      • 从S中移去所有d不一致的假设

 

      • 对G中每个与d不一致的假设g

 

             •从G中移去g

 

             •把g的所有的极小特殊化式h加入到G中,其中h满足

 

                   •h与d一致,而且S的某个成员比h更特殊

 

             •从G中移去所有这样的假设:它比G中另一假设更特殊

 

5.算法举例

候选消除算法步骤(EnjoySport)

 

训练样例:

1.<Sunny,Warm,Normal,Strong,Warm,Same>,EnjoySport=Yes

2.<Sunny,Warm,High,Strong,Warm,Same>,EnjoySport=Yes

S0和G0为最初的边界集合,分别对应最特殊和最一般假设。训练样例1和2使得S边界变得更一般,如FIND-S算法中一样,这些样例对G边界没有影响。

训练样例:

3.<Rainy,Cold,High,Strong,Warm,Change>,EnjoySport=No

样例3是一个反例,他把G2边界特殊化为G3。注意在G3中有多个可选的极大一般假设。

 

训练样例:

4.<Sunny,Warm,High,Storage,Cool,Change>,EnjoySport=Yes

正例是S边界更一般,从S3变为S4。G3的一个成员也必须被删除,因为它不再比S4更一般。

 

EnjoySprot概念学习问题中的最终的变型空间

 

六.归纳偏置

1.无偏的学习器

幂集(power set)把集合X的所有子集的集合称为幂集。

新的假设空间H’,它能表示实例的每一个子集,也就是把H’对应到X的幂集。

<Sunny,?,?,?,?,?>∨<Cloudy,?,?,?,?,?>

2.无偏学习的无用性

学习器如果不对目标概念的形式做预先的假定,它从根本上无法对未见实例进行分类。

一般情况下任意的学习算法L以及为任意目标概念提供的任意训练数据Dc={<x,c(x)>}。训练过程结束后,L需要对新的实例xi进行分类。令L(xi,DC)表示在对训练数据Dc学习后L赋予xi的分类(正例或反例),我们可以如下描述L所进行的这一归纳推理过程:

y表示z从y归纳推理得到。

定义:考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念,并令Dc={<x,c(x)>}为c的任意训练样例集合。令L(xi,Dc)表示经过数据Dc的训练后L赋予实例xi的分类。L的归纳偏置是最小断言集合B,它使任意目标概念c和相应的训练样例Dc满足:

 

候选消除算法的归纳偏置:目标概念c包含在给定的假设空间H中。

 

使用假设空间H的候选消除算的输入输出行为,等价于利用了断言“H包含目标概念”的演绎定理证明器。该断言因此被称为候选消除算法的归纳偏置。用归纳偏置来刻画归纳系统,可以便于使用等价的演绎系统来模拟它们。这提供了一种对归纳系统进行比较的方法,即通过它们从训练数据中泛化的策略。

转载地址:https://blog.csdn.net/a364844763/article/details/41643559 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:线性回归及python实现
下一篇:机器学习之决策树

发表评论

最新留言

很好
[***.229.124.182]2024年03月28日 18时06分25秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux 条件判断 取非_Linux awk 系列文章之 awk 多重条件判断 2019-04-21
c语言中如何将字符串的元素一个一个取出_C语言中常用的字符串操作函数 2019-04-21
2d游戏地图编辑器_王者荣耀:新版本爆料!地图编辑器“天工”即将开测,游戏怎么玩由你定!... 2019-04-21
.net framework服务启动后停止_dos命令net图文教程,start启动系统服务stop停止服务批处理脚本... 2019-04-21
8k分辨率需要多大带宽_超乎想象!用RTX3080显卡连索尼8K电视玩游戏感受如何?... 2019-04-21
win10怎么开启aptx_Win10未来的黑科技?微软SurfaceFleet大曝光 2019-04-21
creo视图管理器使用方法_学以致用之中望3D—浅谈使用中望3D的初步感受 2019-04-21
周育如的音标口诀大全_花鸟画口诀大全,实用! 2019-04-21
心电图计算心率公式_医学常用的计算公式口诀(内外妇儿),赶快收藏! 2019-04-21
select 移动端 第一个无法选中_Python爬虫微博(移动端)评论 2019-04-21
华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21