– Learned_rulesLearned_rules+Rule – ExamplesExamples-{被Rule正确分类的样例} – RuleLearn-One-Rule(Target_attribute, Attributes, Examples)
• Learned_rules按照在Examples上的Performance排序的 Learned_rules • 返回Learned_rules
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 7
表10-1 学习析取规则集的序列 覆盖算法（CN2）
Sequential-Covering(Target_attribute, Attributes, Examples, Threshold) • Learned_rules{} • RuleLearn-One-Rule(Target_attribute, Attributes, Examples) • 当Performance(Rule, Examples)>Threshold
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
8
序列覆盖算法（3）
• 序列覆盖算法将问题化简为一系列简单 的问题，执行的是一种贪婪搜索，它不 能保证找到能覆盖样例的最小或最佳规 则集 • 下面重点讨论Learn-One-Rule的设计，我 们希望算法能够得到较高精度的规则集， 但不必覆盖所有的正例
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 4
内容安排
• 先介绍能够学习命题规则集的算法（命 题规则可看作不含变量的一阶规则）， 算法搜寻假设空间学习析取规则集合 • 将上面算法扩展到一阶规则 • 讨论归纳逻辑的两种通用途径以及归纳 和演绎推理的基本关系
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 9
一般到特殊的柱状搜索
• 一种方法是，将假设空间搜索过程设计为与ID3算法中 相似的方式，但在每一步只沿着最有希望的分支进行， 即产生最佳性能的属性-值对，而不是用增长子树的办 法覆盖所选属性的所有可能值 • 与ID3类似，可定义最佳分支，它覆盖的样例有最低的 熵 • 与其他贪婪算法一样，上面算法的缺陷是，它的每一 步都可能做出次优的选择 • 用柱状搜索来减小风险，即每一步保留k个最佳候选分 支，每一步对k个候选分支进行处理，然后再将结果集 削减至k个最可能成员
机器学习
第10章 学习规则集合
2003.12.18
机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏
1
概述
• 对学习到的假设，最具有表征力的和最能为人 类所理解的表示方法之一是if-then规则的集合 • 本章探索若干能学习这样的规则集合的算法 • 其中，最重要的是学习包含变量的规则集合， 或称一阶Horn子句集合 • 由于一阶Horn子句集合可被解释为逻辑编程语 言Prolog中的程序，学习的过程常被称为归纳 逻辑编程 • 本章考察了多种学习规则集合的途径，其中一 种是基于机器定理证明器中演绎算子的逆转
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 2
简介
• 在许多情况下，有必要学习一个由若干if-then 规则共同定义的目标函数，比如
– 决策树 – 遗传算法
• 本章我们讨论一组不同的算法，它们直接学习 规则集合，与前面算法有两点关键的不同
– 可学习包含变量的一阶规则集合（一阶子句的表达 能力比命题规则要强得多） – 使用序列覆盖算法，一次学习一个规则，以递增的 方式形成最终的规则集合
• Prolog程序就是一阶规则的集合，因此一个可以学习这 种规则集合的通用算法，可被看作是从样例中自动推 导出Prolog程序的算法 • 一阶表示的学习系统在实践中的应用
– 在质谱仪中学习哪一个化学药品能粘合碎片 – 学习哪一个化学亚结构会产生诱导有机体突变的放射性物质 – 学习有限单元网以分析物理结构中的应力
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 10
表10-2 Learn-One-Rule的一种实现：一般到特殊柱状搜索
Learn-One-Rule(Target_attribute, Attributes, Examples, k) • 初始化Best_hypothesis为最一般的假设 • 初始化Candidate_hypotheses为集合{Best_hypothesis} • 当Candidate_hypotheses不空，做以下操作
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 3
简介（2）
• 一阶规则集合的例子
if Parent(x,y) then Ancestor(x,y) if Parent(x,z) Ancestor(z,y) then Ancestor(x,y) – 这个规则集合很紧凑地描述了一个递归函数，它很难用决策 树或其他命题的方法来表示
2003.12.18
机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者算法
– 学习一个规则，移去它覆盖的数据，再重复这一过 程
• 假定已有一个子程序Learn-One-Rule，它的输 入是一组正例和反例，输出是单个规则，它能 够覆盖许多正例而覆盖很少的反例 • 我们要求输出的规则有较高的精确度，但不必 有较高的覆盖度
2003.12.18 机器学习-学习规则集合 作者：Mitchell 译者：曾华军等 讲者：陶晓鹏 6
序列覆盖算法（2）
• 序列覆盖算法的过程
– 在所有可用训练样例上执行Learn-One-Rule – 再移去由其学到的规则覆盖的正例 – 重复上面的过程，直到规则集覆盖正例达到希望的 程度
• 序列覆盖算法按次序学习到一组规则，它们共 同覆盖了全部正例 • 规则集中的规则可排序，分类新实例时可先应 用精度最高的规则