《学习规则集合》由会员分享，可在线阅读，更多相关《学习规则集合（53页珍藏版）》请在金锄头文库上搜索。
1、2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,1,机器学习,第10章 学习规则集合,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,2,概述,对学习到的假设，最具有表征力的和最能为人类所理解的表示方法之一是if-then规则的集合 本章探索若干能学习这样的规则集合的算法 其中，最重要的是学习包含变量的规则集合，或称一阶Horn子句集合 由于一阶Horn子句集合可被解释为逻辑编程语言Prolog中的程序，学习的过程常被称为归纳逻辑编程 本章考察了多种学习规则集合的途径，其中一种是基于机器定理
2、证明器中演绎算子的逆转,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,3,简介,在许多情况下，有必要学习一个由若干if-then规则共同定义的目标函数，比如 决策树 遗传算法 本章我们讨论一组不同的算法，它们直接学习规则集合，与前面算法有两点关键的不同 可学习包含变量的一阶规则集合（一阶子句的表达能力比命题规则要强得多） 使用序列覆盖算法，一次学习一个规则，以递增的方式形成最终的规则集合,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,4,简介（2）,一阶规则集合的例子 if Parent
3、(x,y) then Ancestor(x,y) if Parent(x,z) Ancestor(z,y) then Ancestor(x,y) 这个规则集合很紧凑地描述了一个递归函数，它很难用决策树或其他命题的方法来表示 Prolog程序就是一阶规则的集合，因此一个可以学习这种规则集合的通用算法，可被看作是从样例中自动推导出Prolog程序的算法 一阶表示的学习系统在实践中的应用 在质谱仪中学习哪一个化学药品能粘合碎片 学习哪一个化学亚结构会产生诱导有机体突变的放射性物质 学习有限单元网以分析物理结构中的应力,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军
4、等 讲者：陶晓鹏,5,内容安排,先介绍能够学习命题规则集的算法（命题规则可看作不含变量的一阶规则），算法搜寻假设空间学习析取规则集合 将上面算法扩展到一阶规则 讨论归纳逻辑的两种通用途径以及归纳和演绎推理的基本关系,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,6,序列覆盖算法,序列覆盖算法 学习一个规则，移去它覆盖的数据，再重复这一过程 假定已有一个子程序Learn-One-Rule，它的输入是一组正例和反例，输出是单个规则，它能够覆盖许多正例而覆盖很少的反例 我们要求输出的规则有较高的精确度，但不必有较高的覆盖度,2003.12.18,
5、机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,7,序列覆盖算法（2）,序列覆盖算法的过程 在所有可用训练样例上执行Learn-One-Rule 再移去由其学到的规则覆盖的正例 重复上面的过程，直到规则集覆盖正例达到希望的程度 序列覆盖算法按次序学习到一组规则，它们共同覆盖了全部正例 规则集中的规则可排序，分类新实例时可先应用精度最高的规则,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,8,表10-1 学习析取规则集的序列覆盖算法（CN2）,Sequential-Covering(Target_attribut
6、e, Attributes, Examples, Threshold) Learned_rules RuleLearn-One-Rule(Target_attribute, Attributes, Examples) 当Performance(Rule, Examples)Threshold Learned_rulesLearned_rules+Rule ExamplesExamples-被Rule正确分类的样例 RuleLearn-One-Rule(Target_attribute, Attributes, Examples) Learned_rules按照在Examples上的Perfor
7、mance排序的Learned_rules 返回Learned_rules,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,9,序列覆盖算法（3）,序列覆盖算法将问题化简为一系列简单的问题，执行的是一种贪婪搜索，它不能保证找到能覆盖样例的最小或最佳规则集 下面重点讨论Learn-One-Rule的设计，我们希望算法能够得到较高精度的规则集，但不必覆盖所有的正例,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,10,一般到特殊的柱状搜索,一种方法是，将假设空间搜索过程设计为与ID3算法中相似的
8、方式，但在每一步只沿着最有希望的分支进行，即产生最佳性能的属性-值对，而不是用增长子树的办法覆盖所选属性的所有可能值 与ID3类似，可定义最佳分支，它覆盖的样例有最低的熵 与其他贪婪算法一样，上面算法的缺陷是，它的每一步都可能做出次优的选择 用柱状搜索来减小风险，即每一步保留k个最佳候选分支，每一步对k个候选分支进行处理，然后再将结果集削减至k个最可能成员,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,11,表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索,Learn-One-Rule(Target_attribute
9、, Attributes, Examples, k) 初始化Best_hypothesis为最一般的假设 初始化Candidate_hypotheses为集合Best_hypothesis 当Candidate_hypotheses不空，做以下操作 生成下一个更特殊的候选假设 All_constraints所有形式为(a=v)的约束集合，其中，a为Attributes的成员，v为出现在当前Examples集合中的a的值 New_candidate_hypotheses 对Candidate_hypotheses中每个h，循环 对All_constraints中每个c，循环 通过加入约束c创建一
10、个h的特化式 New_candidate_hypotheses中移去任意重复的、不一致的或非极大特殊化的假设 更新Best_hypothesis 对New_candidate_hypotheses中所有h做以下操作 如果Performance(h,Examples,Target_attribute)Performance(Best_hypothesis,Examples,Target_attribute) 则Best_hypothesish 更新Candidate_hypotheses Candidate_hypothesesCandidate_hypotheses中k个Performance
11、最佳成员 返回如下形式的一个规则 “如果Best_hypothesis”，则prediction 其中，prediction为在与Best_hypothesis匹配的Examples中最频繁的Target_attribute值,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,12,表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索（2）,Performance(h, Examples, Target_attribute) h_examples与h匹配的Examples子集 返回-Entropy(h_examples)，En
12、tropy是关于Target_attribute的熵,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,13,对表10-2的Learn-One-Rule算法的说明,算法主循环中考虑的每个假设都是属性-值约束的合取 每个合取假设对应于待学习规则的候选前件集合，它由其覆盖的样例的熵来评估 搜索算法不断特化候选假设，直到得到一个极大特殊假设，它包含所有可用的属性 规则的后件在算法的最后一步产生，在其前件确定后，算法构造出的规则后件用于预测在前件所能覆盖的样例中最常见的目标属性值 尽管使用了柱状搜索，贪婪搜索仍可能产生次优的规则,2003.12.18,
13、机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,14,序列覆盖算法的几种变型,只学习覆盖正例的规则，对该规则没有覆盖的实例默认地赋予其反例分类 正例在整个群体中所占比例很小，所以规则集只标定正例的类别，而对其他样例默认分类为反例，这样规则集更简洁易懂 这一方法对应于Prolog中的失败否定策略，其中不能证明为真的表达式都默认为假 需要修改Learn-One-Rule算法 增加输入变量，指定感兴趣的目标值 Performance使用假设覆盖正例的比例,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,15,序列覆盖算
14、法的几种变型（2）,AQ算法 AQ明确地寻找覆盖特定目标值的规则，然后，对每个目标值学习一个析取规则集 AQ算法学习单个规则的方法也不同于Learn-One-Rule，当它对每个规则执行一般到特殊柱状搜索时，他围绕单个正例来进行 搜索中只考虑被某正例满足的属性，以得到逐渐特殊的假设，每次学一个新规则时，它从那些未覆盖的样例中也选择一个新的正例，以指引新析取项的搜索,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,16,学习规则集：小结,串行与并行的差异 序列学习算法（CN2）每次学习一个规则，而ID3每一步并行学习整个析取项的集合，ID3可称
15、为并行覆盖算法 ID3在每一搜索步中根据它对数据产生的划分选择不同的属性，CN2选择的是不同的属性-值对 为了学习到n个规则的集合，每个规则前件包含k个属性值测试，CN2需要nk次基本搜索步，而ID3独立选择次数要少得多 CN2需要较大数量的训练数据,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,17,学习规则集：小结（2）,搜索方向的差异 Learn-One-Rule的搜索方向是从一般到特殊，而其他算法是从特殊到一般 从一般到特殊的一个优点是只有一个极大一般假设可作为搜索起始点 而多数假设空间中有很多特殊假设，因此有许多极大特殊假设，从特
16、殊到一般的算法难以确定搜索的起点,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,18,学习规则集：小结（3）,生成再测试与样例驱动搜索的差异 样例驱动搜索算法包括：Find-S、候选消除、AQ算法、Gigol 样例驱动算法中，对假设的生成或修正是由单独的训练样例驱动的，而且结果是一个已修正的假设，它对此单个样例的性能得到改善 Learn-One-Rule是生成再测试搜索 生成再测试搜索方法中，后续的假设的生成只基于假设表示的语法，然后基于这些假设在全部样例上的性能来进行选择 生成再测试的一个优点是搜索中每一步的选择都基于在许多样例上的假设性能，因此噪声数据的影响被最小化,2003.12.18,机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏,19,学习规则集：小结（4）,规则的后修剪和后修剪的方法 Learn-One-Rule也有可能形成过度拟合，解决的方法也可以是后修剪 性能函数的定义 相对频率：令n代表规则所匹配的样例数目，nc代表其中它能正确分类的数目，则规则
