9.概念学习剖析

《9.概念学习剖析》由会员分享，可在线阅读，更多相关《9.概念学习剖析（61页珍藏版）》请在金锄头文库上搜索。

1、1,机器学习 概念学习,2,归纳学习概念 概念学习定义 作为搜索的概念学习（搜索策略：偏序） Find-S：寻找极大特殊假设 变形空间和候选消除算法 归纳偏置,OUTLINE,3,归纳学习也可以称作归纳推理或简称归纳，其任务是：给定函数f(未知)的实例集合，返回一个近似于f的函数hh称为假设，所有h的集合称为假设空间 一个好的假设应该能够预测未见过的实例这就是基本的归纳问题 问题实例用一个单变量函数(近似目标函数)来拟合若干数据点，选择最高次数为k的多项式集合作为假设h的集合，即假设空间H,归纳学习,4,数据拟合,5,上图中显示了拟合两两一组数据的不同函数与所有数据一致的函数称为一致假设 如何

2、在多个一致假设之间进行选择？ 答案奥卡姆剃刀原则(Ockhams razor)优先选择与数据一致的最简单假设 原因比数据本身更复杂的假设不能从数据中提取任何模式 此外，对于非确定性函数，在假设的复杂度和数据拟合度之间进行折中不可避免,Ockham剃刀原则,6,归纳学习概念 概念学习定义 作为搜索的概念学习（搜索策略：偏序） Find-S：寻找极大特殊假设 变形空间和候选消除算法 归纳偏置,OUTLINE,7,概念学习 给定某一类别的若干正例和反例，从中获得该类别的一般定义。 搜索的观点 在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。 利用假设空间的偏序结构 算法收敛到正确假设的条件

3、,概念学习,8,概念学习问题的定义 给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。,概念学习,9,例子 enjoy sport,目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport 任务目的，基于某天的各属性，预测EnjoySport的值 一个样例集，每个样例表示为属性的集合,表2-1 目标概念EnjoySport的训练样例,10,基本概念 实例 x : 每一个实例使用若干属性表示，相应属性值构成一个实例,例子 enjoy sport,11,基本

4、概念 实例集 X : 概念定义在一个实例集合之上，这个集合表示为X,例子 enjoy sport,12,基本概念 目标概念 c: 待学习的概念或函数称为目标概念，记作c,例子 enjoy sport,13,基本概念 训练样例 d: 每个样例为X中的一个实例x以及他的目标概念值c(x)。表示为序偶 注意：EnjoySport=yes时c(x)=1 EnjoySport=no时c(x)=0,例子 enjoy sport,14,基本概念 正例: c(x)=1的实例被称为正例 反例: c(x)=0的实例被称为反例,例子 enjoy sport,15,基本概念 训练样例集 D: 训练样例的集合,例子 e

5、njoy sport,16,例子 enjoy sport,基本概念 假设 h: 表示X上定义的布尔函数，即h：X 0,1,假设 h: ,问题：本例中怎样表示假设? 实例的各属性约束的合取值,17,例子 enjoy sport,基本概念 假设 h: ,明确指定的属性值,任意本属性可接受的值,不接受任何值: ,18,例子 enjoy sport,基本概念 假设集合 H: 所有可能假设的集合,19,例子 enjoy sport,已知: 实例集 X 假设集 H 目标概念 c: X0,1 训练样例 D 求解（学习目标）: H中的一假设h，使对于X中任意x，h(x)=c(x),20,归纳学习假设,归纳学习

6、假设 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好的逼近目标函数,21,归纳学习概念 概念学习定义 作为搜索的概念学习（搜索策略：偏序） Find-S：寻找极大特殊假设 变形空间和候选消除算法 归纳偏置,OUTLINE,22,作为搜索的概念学习,概念学习: 可以看作一个在假设空间上搜索的过程,学习: 训练样例 假设空间选取,假设的表示所隐含定义 的整个空间,目标： 能够最好地拟合训练样例的假设,23,作为搜索的概念学习,当假设的表示形式选定后，那么就隐含地为学习算法确定了所有假设的空间 E.g. EnjoySport的实例空间: 3X2X2X2X2X2=96 假

7、设空间H中语法不同的假设: 5X4X4X4X4X4=5120 假设空间H中语义不同的假设:,3+?+,24,假设空间,假设的表示形式: 析取连接词（Disjunctive conjunction） 线性等式（Liner equation） 其它方法 假设空间大小: |H| |X|,25,搜索策略,假设空间中彻底详尽的搜索需要一个策略（顺序） Why? 如何对假设排序? 线性排序 偏序,26,假设的一般到特殊序,假设的一般到特殊序关系 考虑下面两个假设 h1= h2= 任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。 利用这个关系，无需列举所有假设，就能在无限的假设空间中进

8、行彻底的搜索,27,假设的一般到特殊序,关系“更一般”的精确定义 任给实例x和假设h，说x满足h，当且仅当h(x)=1 令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)(hk(x)=1)(hj(x)=1) 记为hj more_general_than_or_equal_to hk ，或hj g hk,28,实例、假设和more_general_than关系,x1= x2=,实例X,假设集 H,x1,x2,h1,h2,h3,h1= h2= h3=,specific,general,29,归纳学习概念 概念学习定义 作为搜索的概念学习（搜索策略：偏序） Find-S：寻找极

9、大特殊假设 变形空间和候选消除算法 归纳偏置,OUTLINE,30,Find-s：寻找极大特殊假设算法,使用more_general_than偏序的搜索算法 从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化,Specific hypothesis,31,Find-s算法,Find-S算法 将h初始化为H中最特殊假设 对每个正例x 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的下一个更一般 约束 输出假设h,32,Find-s中的假设空间搜索,x1=, + x2=, + x3=, - x4=, +,实例 X,假设集 H,x1,x2,h0,h1,h2

10、,3,h0= h1= h2= h3= h4=,特殊,一般,x3,h4,x4,33,Find-s的特点,Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。 Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。,34,Find-s存在问题,存在的问题 是否收敛到了正确的目标概念？ Find-s找到了与训练样例一致的假设，但无法确定它是否找到了唯一合适的假设（即目标概念本身）。或者说是否还有其它的

11、假设 为什么要用最特殊的假设？ 如果有多个与D一致的假设，它只找到最特殊的假设 训练样例是否相互一致？ D中出现错误将严重破坏Find-s算法 如果有多个极大特殊假设怎么办？,35,归纳学习概念 概念学习定义 作为搜索的概念学习（搜索策略：偏序） Find-S：寻找极大特殊假设 变形空间和候选消除算法 归纳偏置,OUTLINE,36,变形空间和候选消除算法,候选消除算法概述 概念学习的另一种方法，候选消除算法（candidate-elimination） Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个 候选消除算法输出与训练样例一致的所有假设的集合 候选消除算法在

12、描述这一集合时不需要明确列举所有成员，利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示,37,变形空间和候选消除算法,候选消除算法的应用，化学质谱分析、启发式搜索的控制规则 候选消除算法的缺点，容错性能差,38,变形空间和候选消除算法,输出与训练样例一致的所有假设的集合 “一致”的定义 一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)，即Consistent(h,D)(D) h(x)=c(x),39,变形空间和候选消除算法,变形空间 VSH,D 关于H和D的变型空间，记为VSH,D，是假设空间H中与训练样例D一致的所有假设构成的子

13、集 VSH,D h H|Consistent(h,D),40,变形空间示例,返回,41,列表后消除算法,列表后消除算法：表示变型空间的一种方法是列出其所有成员 算法： 变型空间VSH,D 包含H中所有假设的列表 对每个训练样例 从变型空间中移除所有h(x)c(x)的假设 输出VSH,D中的假设列表,42,列表后消除算法,优点 保证得到所有与训练数据一致的假设 缺点 非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到,43,候选消除算法,变型空间的更简洁表示 变型空间被表示为它的极大一般和极大特殊的成员 这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间。例如 关

14、于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合 关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合,44,候选消除算法算法描述,初始化G和S 如果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的

15、某个成员比h更特殊 从G中移去所有这样的假设：它比G中另一个假设更特殊,45,候选消除算法示例,极大一般,极大特殊,46,候选消除算法示例,极大一般,极大特殊,47,极大一般,极大特殊,s2, s3,G2,G3, ,候选消除算法示例,48,极大一般,极大特殊,正例,s2, s3,G2,G4,候选消除算法示例, ,正例,49,S 边界覆盖了正例相关的信息，因此正例不需要保留 G 边界覆盖了反例相关的信息，因此反例不需要保留 训练样例使用顺序不会影响算法结果（变形空间），但会影响算法效率 正例使S边界一般化，反例使G边界特殊化. 如果S和G覆盖同样的假设，则假设空间中只有一个与训练数据一致的假设. 如果S和G 变为空(二者有一个为空，另一个比为空)，那么假设空间中没有与训练数据一致的假设.,候选消除算法特点,50,练习,考虑积木世界的以下属性和属性值： 颜色=黄色，蓝色，绿色； 形状=圆锥形，球形，长方形； 硬度=硬，软 尺寸=大，小 训练样例如下（“+”表示正例，“-”表示反例） (黄色，圆锥形，软，大，+) (蓝色，长方形，软，小，-) (黄色，球形，软，小，+) (黄色，圆锥形，硬，大，+) (黄色，长方形，软，大，+) (绿色，球形，硬，大，-) (蓝色，圆锥形，软，大，-) 问题：采用变形空间法，学习概念：黄色