• / 34
  • 下载费用:10 金币  

第6.3节 实例学习.ppt

关 键 词:
第6.3节 实例学习.ppt
资源描述:
第6.3节 实例学习,王庆江 计算机科学与技术系 qjwang@ouc.edu.cn,2008-2009学年第1学期,机器学习,实例学习(也称示例学习)是一种典型的归纳学习方法; 对大量事先标注了“正例”或“反例”的示教例子进行分析,归纳得出一般规则; 将低水平的信息(实例)归纳为高水平的信息(规则或概念); 实例学习是机器学习走向实用的先导。,2008-2009学年第1学期,机器学习,积木世界,,,,,,,,,,,,,,,,形状,结构,2008-2009学年第1学期,机器学习,Winston程序在积木世界中对结构的学习,某物体(或景象)的积木结构用语义网络表示。,第1个拱桥的语义网络,B,D,长方体,,A,C,,,,,,,,,有部件,有部件,有部件,被支撑,被支撑,在左边,在右边,不接触,是,2008-2009学年第1学期,机器学习,第2个拱桥的语义网络,B,D,长方体,,A,C,,,,,,,,,有部件,有部件,有部件,被支撑,被支撑,在左边,在右边,不接触,是,楔形体,,是,2008-2009学年第1学期,机器学习,归纳出的语义网络,输入正例时,扩大表示范围,覆盖所有正例,2008-2009学年第1学期,机器学习,第3个语义网络是拱桥的反例,输入反例时,收缩表达范围,使之不保含该反例,2008-2009学年第1学期,机器学习,新归纳出的语义网络,2008-2009学年第1学期,机器学习,从Winston实例学习想到的…,有一个实例空间(即集合),每个例子标注了“正例”或“反例”; 用某种知识表示法(这里是语义网络)表示要学习的概念(这里是拱桥); 知识表示可翻译成一组规则,组成规则空间; 例:(A, is, arch bridge), (B, part-of, A), (C, part-of, A), (D, part-of, A), (B, is, cuboid), (C, is, cuboid), (D, is, cuboid), (B, located_left, D), (D, located_right, B), (C, supported, B), (C, supported, D), (B, untouched, D), (D, untouched, B) 实例被一个个地送入学习系统,系统分析输入的实例,修改规则空间。,2008-2009学年第1学期,机器学习,实例学习的两个空间模型,轮番对实例空间和规则空间进行搜索、匹配,2008-2009学年第1学期,机器学习,什么是实例空间?,扑克牌“五张同花”的例子 {(2, 梅花), (3, 梅花), (5, 梅花), (J, 梅花), (K, 梅花)} 正例 {(8, 梅花), (3, 黑桃), (9, 黑桃), (Q, 红桃), (3, 方块)} 反例 … 这样的例子有多少?,2008-2009学年第1学期,机器学习,个体常量 club(梅花), diamond(方块), heart(红桃), spade(黑桃) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A 个体变量 u, v, x, y, z, c1, c2, c3, c4, c5 谓词 SUIT(ci, x):牌ci的花色是x,1≤ i≤ 5 RANK(ci, x):牌ci的点数是x ,1≤ i≤ 5,2008-2009学年第1学期,机器学习,实例空间∀(c1,c2,c3,c4,c5,u,v,x,y,z)(SUIT(c1, u) ∧SUIT(c2, v)∧ SUIT(c3, x)∧SUIT(c4, y)∧SUIT(c5, z)) “同花”概念的表示∃(c1,c2,c3,c4,c5)(SUIT(c1, x)∧SUIT(c2, x)∧ SUIT(c3, x)∧SUIT(c4, x)∧SUIT(c5, x)),2008-2009学年第1学期,机器学习,实例空间的质量,示教例子的标注要正确 该标“正例”的,却标为“反例”,会导致错误的规则。 示教例子的顺序要合理 正例和反例夹杂送入,会加快学习速度; 可采用某些控制策略,以主动选择例子。,2008-2009学年第1学期,机器学习,什么是对例子的解释?,从例子中提取用于搜索规则空间的信息。 例:将例子变换为易于归纳的形式(如语义基元)(A, is, cuboid),(B, is, cylinder),(A, located_on, B),(C, is, cube),(B, untouched, C),(A, untouched, C),2008-2009学年第1学期,机器学习,什么是规则空间?,在某种表示法下,可表示的所有规则构成规则空间; 规则和实例采用同一种表示法,可方便归纳。 例:“对牌”规则为RANK(c1,x) ∧ RANK(c2,x)├ PAIR 有正例如下: (2,club),(3,diamond),(2,heart),(6,spade),(K,heart)├ PAIR,规则和实例的表示不一致!,2008-2009学年第1学期,机器学习,将正例表示修改为:RANK(c1,2) ∧SUIT(c1,club) ∧ RANK(c2,3) ∧ SUIT(c2,diamond) ∧ RANK(c3,2) ∧ SUIT(c3,heart) ∧ RANK(c4,6) ∧ SUIT(c4,spade) ∧ RANK(c5,K) ∧ SUIT(c5,heart) ├ PAIR 去掉SUIT,得RANK(c1,2) ∧ RANK(c2,3) ∧ RANK(c3,2) ∧ RANK(c4,6) ∧ RANK(c5,K) ├ PAIR 去掉c2、c4、c5的RANK,得RANK(c1,2) ∧ RANK(c3,2) ├ PAIR 把常量2变为变量x,得最后的规则:RANK(c1,x) ∧ RANK(c3,x) ├ PAIR,2008-2009学年第1学期,机器学习,规则空间的推理,归纳推理是由特殊到一般的过程,不保证结论正确; 反复进行示例和归纳,避免归纳的错误结论影响最终结果。常量化为变量 SUIT(c1,club) ∧ SUIT(c2, club) ∧ SUIT(c3, club) ∧ SUIT(c4, club) ∧ SUIT(c5, club) ├ FLUSH(c1, c2, c3, c4, c5) SUIT(c1,spade) ∧ SUIT(c2, spade) ∧ SUIT(c3, spade) ∧ SUIT(c4, spade) ∧ SUIT(c5, spade) ├ FLUSH(c1, c2, c3, c4, c5) 归纳出规则:SUIT(c1,x) ∧ SUIT(c2,x) ∧ SUIT(c3,x) ∧ SUIT(c4,x) ∧ SUIT(c5,x) ├ FLUSH(c1, c2, c3, c4, c5),(扩大表示范围,可能引入错误),2008-2009学年第1学期,机器学习,去掉条件 SUIT(c1,club) ∧ RANK(c1,3) ∧ SUIT(c2, club) ∧ RANK(c2,5) ∧ SUIT(c3, club) ∧ RANK(c3,7) ∧ SUIT(c4, club) ∧ RANK(c4,10) ∧ SUIT(c5, club) ∧ RANK(c5,K) ├ FLUSH(c1, c2, c3, c4, c5) 得规则:SUIT(c1,x) ∧ SUIT(c2,x) ∧ SUIT(c3,x) ∧ SUIT(c4,x) ∧ SUIT(c5,x) ├ FLUSH(c1, c2, c3, c4, c5),(扩大表示范围,可能引入错误),2008-2009学年第1学期,机器学习,增加选择项(即增加析取项) RANK(c1, J) ├ FACE(c1) RANK(c1, K) ├ FACE(c1) 得规则:RANK(c1, J) ∨RANK(c1, K) ├ FACE(c1) 再增加一个选择项,就可得到期望的规则: RANK(c1, J)∨RANK(c1, Q)∨RANK(c1, K)├ FACE(c1) 如果对a)使用“常量改为变量”,会得到错误规则:RANK(c1, x) ├ FACE(c1),2008-2009学年第1学期,机器学习,6.3.2 实例学习方法的分类,先建立包含一些假设规则的空间H; 每输入一个实例,按实例的解释搜索并修改H。 对假设空间H的改进方法 数据驱动方法 变形空间法 改进假设法 模型驱动方法 产生与测试法 方案示例法,2008-2009学年第1学期,机器学习,变形空间法 规则和实例采用同一种表示法; 初始的H满足第1个示教例子和全部假设规则; 每输入一个例子,对H做泛化或特化处理,使之满足全部正例,不满足全部反例; 最后,H收敛为仅含所要的规则。 改进假设法 规则和实例的表示形式不必统一; 每输入一个例子,选择一种操作,对H进行修改。,2008-2009学年第1学期,机器学习,产生与测试法 针对示教例子反复产生和测试假设的规则; 产生假设规则时,使用基于模型的知识,以便只产生可能合理的假设。 方案示例法 使用规则方案的集合来约束可能合理的规则的形式; 其中最符合示教例子的规则方案被认为是最合理的规则。,2008-2009学年第1学期,机器学习,数据驱动方法和模型驱动方法的区别,数据驱动法可逐步接受例子,渐进学习,不需对学习结果的回溯; 模型驱动法通过检查全部实例来测试假设,难以逐步学习,需回溯或重新搜索规则空间; 数据驱动法对例子示教错误敏感,而模型驱动法则抗干扰性好。,2008-2009学年第1学期,机器学习,按任务复杂程度分类,学习单个概念 从概念空间(即规则空间)寻找某个与实例空间一致的概念。 学习多个概念 在概念空间中,寻找若干个概念描述;对每一概念描述,实例空间中都有相应的样本集合与之对应。,2008-2009学年第1学期,机器学习,6.3.3 变形空间法(Mitchell,1977),规则空间的结构 表示规则的点与点之间有一般到特殊的偏序关系; 最一般的点是没有描述的点,可描述任何事物; 最特殊的点对应实例空间中的正例。,2008-2009学年第1学期,机器学习,初始时,G可描述任何概念,S包含全部正例; 规则空间H以G和S为上、下界; 在学习过程中,G向下、S向上移动,H空间逐渐缩小; H仅包含一个“点”(即一条规则)时,学习结束。,2008-2009学年第1学期,机器学习,消除候选元素算法,它把尚未被数据(实例)排除的假设(规则)称为可能假设,所有可能假设组成集合H(称为变形空间); 初始时,H包含所有可能成立的概念; 根据不断提供的示教例子,对H进行泛化和特化处理; 实现降低G、提升S,使H缩小。 直到H只含一个概念为止。,2008-2009学年第1学期,机器学习,消除候选元素法,初始化H G为空描述,即可描述任意概念; S包含所有最特殊概念。为避免S过大,S可仅包含一个正例。 重复接收一个实例, 它为正例时,对H“泛化”。若G有不包含此例的概念,将其删除,即G下移;将S与新例进行归纳,使S覆盖新例,即S上移; 它为反例时,对H“特化”。若S有包含此反例的概念,删除它,S上移;修改G使之不覆盖新例,即G下移; 重复②,直到G = S,且仅含一个元素时; 输出H中的概念(即输出G或S)。,2008-2009学年第1学期,机器学习,例:学习“圆”概念,用二元组表示物体大小和形状; G = {(x, y)} ,S = {(sm, squ), (sm, cir), (sm, tri), (lg, squ), (lq, cir), (lg, tri)} ,初始的变形空间H为,2008-2009学年第1学期,机器学习,(sm, cir, +) (lg, tri, -) (lg, cir, +) …,G满足正例要求,保持不变;S修改为只包含此正例。,(x, y),(sm, y) (lg, y) (x, squ) (x, cir) (x, tri),(sm, squ) (lg, squ) (sm,cir) (lg, cir) (sm, tri) (lg, tri),,,,,,,,,,,,,,,,,,,,,,,,,,,,,2008-2009学年第1学期,机器学习,(sm, cir, +) (lg, tri, -) (lg, cir, +) …,G包含此反例,修改G使之不包含;S不含此反例,保持不变。,(x, y),(sm, y) (lg, y) (x, squ) (x, cir) (x, tri),(sm, squ) (lg, squ) (sm,cir) (lg, cir) (sm, tri),,,,,,,,,,,,,,,,,,,,,,(lg, tri),,,,,,,,2008-2009学年第1学期,机器学习,(sm, cir, +) (lg, tri, -) (lg, cir, +) …,G有不含此例的概念,删除之;S做最小归纳,使之包含此例。,(x, y),(sm, y) (lg, y) (x, squ) (x, cir) (x, tri),(sm, squ) (lg, squ) (sm,cir) (lg, cir) (sm, tri),,,,,,,,,,,,,,,,,,,,,,(lg, tri),,,,,,,,(lg, cir),,,,2008-2009学年第1学期,机器学习,作业,6.11,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第6.3节 实例学习.ppt
链接地址:https://www.weizhuannet.com/p-10036114.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开