《机器学习-概念学习》由会员分享，可在线阅读，更多相关《机器学习-概念学习（36页珍藏版）》请在金锄头文库上搜索。
1、2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,1,机器学习,第2章 概念学习和一般到特殊序,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,2,提纲,概念学习 给定某一类别的若干正例和反例，从中获得该类别的一般定义。 搜索的观点 在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。 利用假设空间的偏序结构 算法收敛到正确假设的条件 归纳学习的本质，从训练数据中泛化的理由,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,3,简介,许多机器学习涉及
2、到从特殊训练样例中得到一般概念。 概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。 概念学习问题的定义 给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义。又称从样例中逼近布尔函数。 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,4,概念学习任务,一个例子 目标概念，Aldo进行水上运动的日子，表示为布尔函数EnjoySport 任务目的，基于某天的各属性，预测EnjoySport的值 一个样例集，
3、每个样例表示为属性的集合,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,5,概念学习任务（2）,Yes,Change,Cool,Strong,High,Warm,Sunny,4,Yes,Change,Warm,Strong,High,Cold,Rainy,3,Yes,Same,Warm,Strong,High,Warm,Sunny,2,Yes,Same,Warm,Strong,Normal,Warm,Sunny,1,EnjoySport,Forecast,Water,Wind,Humidity,AirTemp,Sky,Example,表2-1
4、目标概念EnjoySport的训练样例,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,6,概念学习任务（3）,表示假设的形式 一个简单的形式，实例的各属性约束的合取式 令每个假设为6个约束（或变量）的向量，每个约束对应一个属性可取值范围，为 ？任意本属性可接受的值 明确指定的属性值 不接受任何值 假设的例子/ 所有的样例都是正例/ 所有的样例都是反例,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,7,概念学习任务（4）,EnjoySport概念学习任务 已知 实例集X 每个实例x由6个属性描述，
5、每个属性的取值范围已确定 假设集H 每个假设h描述为6个属性的取值约束的合取 目标概念c 一个布尔函数，变量为实例 训练样例集D 目标函数（或目标概念）的正例和反例 求解 H中的一假设h，使对于X中任意x，h(x)=c(x),2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,8,术语定义,实例x 实例集X 概念 目标概念c 训练样例x 训练样例集D 正例，目标概念成员 反例，非目标概念成员 假设h 假设集H 机器学习的目标就是寻找一个假设h，使得对所有的h，都有h(x)=c(x),2003.12.18,机器学习-概念学习 作者：Mitchell 译
6、者：曾华军等 讲者：陶晓鹏,9,归纳学习假设,什么是归纳学习？ 从特殊的样例得到普遍的规律 归纳 只能保证输出的假设能与训练样例相拟合 归纳假设的一个基本假定 对于未见实例最好的假设就是与训练数据最佳拟合的假设 归纳学习假设 任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,10,作为搜索的概念学习,概念学习可以看作一个搜索的过程 搜索范围：假设的表示所隐含定义的整个空间 搜索目标：能够最好地拟合训练样例的假设 当假设的表示形式选定后，那么就隐含地为学习算
7、法确定了所有假设的空间 例子EnjoySport的假设空间,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,11,假设的一般到特殊序,假设的一般到特殊序关系 考虑下面两个假设 h1= h2= 任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。 利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,12,假设的一般到特殊序（2）,关系“更一般”的精确定义 任给实例x和假设h，说x满足h，当且仅当h(x)=1 令hj和h
8、k是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)(hk(x)=1)(hj(x)=1) 记为hj more_general_than_or_equal_to hk，或hj g hk,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,13,假设的一般到特殊序（3）,“更一般”的严格情形 hj g hk，当且仅当，(hj g hk) (hk g hj) “更特殊”关系的定义 hj g hk，当且仅当，hk g hj 以EnjoySport为例说明上面的定义 偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂
9、。 这个偏序关系的定义与目标概念无关,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,14,Find-S：寻找极大特殊假设,使用more_general_than偏序的搜索算法 从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化表2-3 Find-S算法 将h初始化为H中最特殊假设 对每个正例x 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的另一个更一般约束 输出假设h,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,15,Find-S：寻找极大特殊假设
10、（2）,Find-S算法在例子EnjoySport上的应用 h h h 遇到反例，h不变（因为h已经能够正确地识别反例） h,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,16,Find-S：寻找极大特殊假设（3）,Find-S算法演示了一种利用more_general_than偏序来搜索假设空间的方法，沿着偏序链，从较特殊的假设逐渐转移到较一般的假设。因此，每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设。 Find-S的重要特点：对以属性约束的合取式描述的假设空间H，保证输出为H中与正例一致的最特殊的假设。 存在的问题 是否收敛到
11、了正确的目标概念？ 为什么要用最特殊的假设？ 训练样例是否相互一致？ 如果有多个极大特殊假设怎么办？,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,17,变型空间和候选消除算法,候选消除算法概说 概念学习的另一种方法，候选消除算法（candidate-elimination） Find-S算法的不足，输出的假设只是H中能够拟合训练样例的多个假设中的一个 候选消除算法输出与训练样例一致的所有假设的集合 候选消除算法在描述这一集合时不需要明确列举所有成员 利用more_general_than偏序结构，可以维护一个一致假设集合的简洁表示 候选消除算
12、法的应用，化学质谱分析、启发式搜索的控制规则 候选消除算法的缺点，容错性能差,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,18,变型空间和候选消除算法（2）,“一致”的定义 一个假设h与训练样例集合D一致，当且仅当对D中每一个样例都有h(x)=c(x)，即Consistent(h,D)(D)h(x)=c(x) “一致”与“满足”的关系 变型空间（version space） 与训练样例一致的所有假设组成的集合 表示了目标概念的所有合理的变型 关于H和D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集VSH,D=hH|Co
13、nsistent(h,D),2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,19,变型空间和候选消除算法（3）,列表后消除算法 表示变型空间的一种方法是列出其所有成员 变型空间包含H中所有假设的列表 对每个训练样例，从变型空间中移除所有h(x)c(x)的假设 输出Version Space中的假设列表 优点 保证得到所有与训练数据一致的假设 缺点 非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,20,变型空间和候选消除算法（4）,变型空间的
14、更简洁表示 变型空间被表示为它的极大一般和极大特殊的成员 这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间 以EnjoySport为例,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,21,变型空间和候选消除算法（5）,形式化定义 极大一般 极大特殊 关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合 关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,22,变型空间和候
15、选消除算法（6）,变型空间表示定理，令X为一任意的实例集合，H为X上定义的布尔假设的集合。令c: X0,1为X上定义的任一目标概念，并令D为任一训练样例集合。对所有的X, H, c, D以及良好定义的S和G：VSH,D=hH|(sS)( gG)(gghgs) 证明：只需证明：1）每一个满足上式右边的h都在VSH,D中，2）VSH,D的每个成员都满足都满足等式右边。,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,23,变型空间和候选消除算法（7）,候选消除算法 初始化G和S 如果d是一个正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的
16、假设s 从S中移去s 把s的所有的极小泛化式h加入到S中，其中h满足 h与 d一致，而且G的某个成员比h更一般 如果d是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特殊化式h加入到G中，其中h满足 h与d一致，而且S的某个成员比h更特殊 从G中移去所有这样的假设：它比G中另一个假设更特殊,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,24,变型空间和候选消除算法（8）,算法举例,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,25,变型空间和候选消除的说明,候选消除算法收敛到正确的假设 训练样例中没有错误 H中确实包含描述目标概念的正确假设 如果样例中存在错误 如果给定足够的训练数据，我们会发现S和G边界收敛得到一个空的变型空间 如果目标概念不能由假设表示方式所描述 相似情况出现,2003.12.18,机器学习-概念学习 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,
