人工智能2012(7).ppt

1、第七章 机器学习,7.1 机器学习的定义、研究意义与发展历史 7.2 机器学习的主要策略与基本结构 7.3 7.7 几种常用的学习方法 7.8 知识发现 7.9 小结,7.1 机器学习的定义和发展历史,7.1.1 机器学习的定义 什么是机器学习 人类的最大特点：学习 目前我们怎样使计算机具有和人类一样强大的学习能力？ 机器学习的定义 顾名思义,机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍为严格的提法是：机器学习是一门研究机器获取新知识和新技 能,并识别现有知识的学问。,7.1.2机器学习的发展史,机器学习的发展分为4个时期 第一阶段是在50年代中叶到60年代中叶，属于热烈时期。

2、第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。 第三阶段从70年代中叶至80年代中叶，称为复兴时期。 机器学习的最新阶段始于1986年 。,7.1 机器学习的定义和发展历史,机器学习进入新阶段的表现 机器学习已成为新的边缘学科并在高校形成课程。 综合各种学习方法 机器学习与人工智能问题的统一性观点正在形成。 各种学习方法的应用范围不断扩大。 数据挖掘和知识发现的研究已形成热潮 。 与机器学习有关的学术活动空前活跃 。,7.1 机器学习的定义和发展历史,机器学习本质上讲是多学科的领域，他吸取了人工智能、概率统计、计算机复杂性理论、控制论、信息论、哲学、神经生物学等学科。,7.

3、2 机器学习的主要策略和基本结构,7.2.1 机器学习的主要策略 按照学习中使用推理的多少，机器学习所采用的策略大体上可分为4种机械学习、通过传授学习、类比学习和通过事例学习。 机械学习 传授学习策略 类比学习系统 通过事例学习策略,7.2.2 机器学习系统的基本结构 1.学习系统的基本结构,7.2 机器学习的主要策略和基本结构,2.影响学习系统设计的要素 影响学习系统设计的最重要因素是环境向系统提供的信息，或者更具体地说是信息的质量。 知识库是影响学习系统设计的第二个因素。知识的表示有特征向量、一阶逻辑语句、产生式规则、语义网络和框架等多种形式。,7.2 机器学习的主要策略和基本结构,7.3

4、 机械学习 1.机械学习模式 机械学习是机器学习最简单的学习方法。机械学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。它是一种最基本的学习过程。,7.3 机械学习,Lenat，Hayes-Roth，和Klahr等人于1979年关于机械学习提出一种有趣的观点，见图7.2。,7.3 机械学习,2.机械学习的主要问题 存储组织信息：要采用适当的存储方式，使检索速度尽可能地快。 环境的稳定性与存储信息的适用性问题： 机械学习系统必须保证所保存的信息适应于外界环境变化的需要。 存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率。,7.3 机械学习,7.4

5、归纳学习,归纳学习（induction learning）是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察与发现学习。 7.4.1 归纳学习的模式和规则 归纳学习的模式,试验规划过程通过对实例空间的搜索完成实例选择，并将这些选中的活跃实例提交给解释过程，解释过程对实例加以适当的转换，把活跃实例变换为规则空间中的特定概念，以引导规则空间的搜索,归纳概括规则,将常量转化为变量 (c1,红桃) (c2,红桃) (c3,红桃) (c4,红桃) (c5,红桃) 同花(c1, c2, c3, c4, c5) (c1,梅花) (c2,梅花) (c3,梅花) (c4,梅花)

6、 (c5,梅花) 同花(c1, c2, c3, c4, c5) (c1,方片) (c2,方片) (c3,方片) (c4,方片) (c5,方片) 同花(c1, c2, c3, c4, c5) (c1, x) (c2, x) (c3, x) (c4, x) (c5, x) 同花(c1, c2, c3, c4, c5),归纳概括规则,将取消部分条件 CTX S K 等价于CTX K,归纳概括规则,放松条件 (c1,J) 花脸(c1) (c1, Q) 花脸(c1) (c1, K) 花脸(c1) (c1, J ) (c1, Q) (c1, K) 花脸(c1),归纳学习是研究得比较深入的一种机器学习形式，

7、可分为两类：有指导的学习和无指导的学习，前者也叫示例学习，后者称为观察与发现学习。示例学习主要包括两种学习算法，即覆盖算法和决策树算法(也叫分治算法)。 归纳学习的算法理论(或称计算学习理论)相对研究得比较透彻，因而构成了比较完整的体系。本章将介绍有指导学习的覆盖算法。,16,7.4.2 覆盖算法,一、 版本空间与覆盖 1. 实例与概念 有指导的学习是通过对实例的指示，具体来说就是指明哪些是正例、哪些是反例，从而指导机器根据正例和反例的集合得到更加抽象的表示，即概念。所以叫做示例学习。这样的学习过程就是从实例中归纳出可以概括例子的某种概念的过程。 2. 概念的层次 概念根据抽象程度不同，可以分

8、成若干层次。上一层次的概念可以包含(或者叫覆盖)下一层次的概念，直到最底层是实例。对于某个概念来说，满足这个概念(被概念所包含)的例子称为正例，不满足的(未被包含的)称为反例。,许多概念与概念之间或概念与实例之间的关系都是ISA关系。如：方便面是一种食品。但更普遍的是相关关系，如下面图7.3表示概念层次关系 图7.3 为了使概念层次局限在一定范围之内，图中使用了顶元素和底元素表示，表示抽象化或具体化到此为止。,3. 版本空间（变型空间） 因为每个概念都包含若干实例(或下层概念)，所以概念代表了一个实例(或概念)集合。集合之间的包含关系可以用偏序关系来刻画，因此概念之间的包含关系也就可以用偏序关

9、系来表示了。 这里的偏序关系就是概念之间的层次关系，Mitchell把具有这种偏序关系的概念和实例的集合称为版本空间，用H表示 偏序关系用表示，概念a概念b可以解释为a低于b(a是b下层概念)或b高于a(b是a上层概念) 4. 版本空间上的函数定义 假设H是版本空间，总有一个最大元素，对于xH, yH，H上定义下列函数： (1)求所有层次低于x的概念：low(x)=y| yx, yx low(x)是所有层次比概念x低的概念(或实例)的集合,(2)求所有层次高于概念x的概念：high(x)=y| xy, yx high(x)是所有层次比x高的概念的集合。 (3)求集合的下界：min(B)=x|

10、xB(yB(x yyx) min(B)是集合B中去掉所有比B中其他元素层次高的元素以后得到的集合，因此都是B中最低层次的概念，称为B的下界。此时min(B)中各个概念之间都是同层次的或者无直接关系的，没有层次高低的关系。 (4)求集合的上界：max(B)=x| xB(yB(yxyx) max(B)是集合B中去掉所有比B中其他元素层次低的元素以后得到的集合，因此都是B中最高层次的概念，称为B的上界。此时max(B)中各个概念之间都是同层次的或者无直接关系的，没有层次高低的关系。 (5)求x的特化：down(x)=max(low(x) 所有比概念x层次低的元素中层次最高的元素的集合，相当于从概念x

11、沿概念层次关系网络向下走一个层次的所有概念的集合，也称为特化。,(6)求集合的特化：down(B)= xB down(x) ，集合B中所有元素的down集合的并集 (7)求x的泛化：up(x) =min(high(x) 所有比x层次高的元素中层次最低的元素的集合，相当于从x沿概念层次关系向上走一层以后得到的概念集合，也称为泛化。 (8)求集合的泛化：up(B)= xB up(x) 集合B中所有元素的up集合的并集。 (9)求最低限度特化：spe(B, y)= 求集合B对于概念y的最低限度的特化，这是一个递归定义。如果B中每个x都不存在yx关系，则B就是y的最低限度特化；否则，除了保留无yx关系

12、的元素x以外，对于B中所有满足yx关系(层次高于y的)概念x都向下走一个层次(作特化)，得到新集合B，然后再求B对于y的最低限度特化，直到集合中不存在yx的概念，最后作一个并集。,(10)求最低限度泛化：gen(B,y)= 求集合B对于概念y的最低限度的泛化，也是一个递归定义。如果B中每个x都存在层次 (yx)关系，则B就是y的最低限度泛化；否则，除了保留具有yx关系的元素x以外，对于B中所有满足xy关系或者y,x无关的概念x都向上走一个层次(作泛化)，得到新集合B，然后再求B对于y的最低限度泛化，直到集合中不存在层次不高于y的概念，最后作一个并集。 例1：在图7.3中，有下列函数结果： lo

13、w(住)=睡袋，亭子间，旅行车， high(睡袋)=衣，住， min(衣，中山装，食，方便面)=中山装，方便面 max(衣，中山装，)=衣 down(住)=睡袋，亭子间，旅行车， down(食，行)=方便面，旅行车,up(旅行车)=住，行，up(睡袋，方便面)=衣，住，食 spe(衣，食，中山装)=食，睡袋 spe(，旅行车)=食，衣，睡袋，亭子间 说明：“”下一层中“食，衣”与“旅行车”无关，“住，行”是“旅行车”上层概念，故去掉；再下一层是“睡袋，亭子间，旅行车”，前2个与“旅行车”无关，故保留，“旅行车”去掉，因为yx，最后是所得结果。 gen(中山装，旅行车)= 说明：“中山装”不高于

14、“旅行车”，所以向上走一步得“衣”，仍然不高于“旅行车”，故再向上走一步得，已经高于它，终止。 5. 单个概念学习 定义：(1)给定由全体实例组成的一个实例空间，每个实例具有某些属性；(2)给定一个描述语言，该语言的描述能力包括描述每个实例(通过描述该实例的属性来实现)以及某些实例的集合，称为概念；,(3)每次学习时，由实例空间抽出某些实例，这些实例构成的集合称为正例集；再从实例空间中抽出另一些实例，其集合称为反例集； (4)如果能在有限步骤内(假定实例个数有限)找到一个概念A，它完全包含正例集，并且与反例集的交集为空，则A就是所要学的单个概念，学习成功，否则学习失败； (5)如果存在一个确定

15、的算法，使得对于任意给定的正例集和反例集，学习都是成功的，则称实例空间在该表示语言之下是可学习的。 上述定义表明，单个概念的学习所学到的概念可能不唯一。只有在正例集+反例集=实例空间时，才是唯一的。否则，如果实例空间中剩余部分的元素个数为d，则可能学到的概念总数为2d。 例2：实例空间=所有人，正例集=华罗庚，李四光，竺可桢，吴有训，反例集=罗斯福，丘吉尔，斯大林，则可能学到的概念是：中国人、或科学家、或中国科学家、或中国自然科学家、或已故中国自然科学家等等。但不可能学到名人、男人、已故的人、已故名人、已故著名男人等等概念。,6. 版本空间中的覆盖和覆盖有关的定义如下 (1)覆盖：设版本空间为

16、H，如果每个正例a都是概念集合X中某个概念x的一个特化(即ax)，则称x覆盖a，或概念集X(包括所有a，可能还有其他)称为一个覆盖。 (2)无反例覆盖：设有H中一个覆盖G，如果G中每个概念都不覆盖任何反例，则G称为一个无反例覆盖。 (3)全能覆盖：设有H中一个无反例覆盖G，如果G中每个概念都能覆盖所有正例，则G称为一个全能覆盖。 (4)互补覆盖：设有H中一个无反例覆盖G，它也可以称为一个互补覆盖，即其中所有概念的并集可以覆盖全部正例。 (5)精确覆盖：设有H中一个全能覆盖G，如果不存在另一个全能覆盖G，使得对每个概念xG，都存在一个概念yG，使yx成立，且G使得至少存在一个 tG和wG，使wt

17、及wt成立，则G称为一个精确覆盖。(解释：此定义要求每一个G中概念都是覆盖全部实例的最低层次概念，就是说不存在另一个G中有比G还低层次的全能覆盖，至多只能相等。),(6)无冗余覆盖：设H中有一个互补覆盖G，如果不存在xG及G的子集G，使得x G且x覆盖的正例集是G覆盖的正例集的子集(如果有G外的一个x能覆盖一个G的子集，显然说明x与G中的一个或数个概念所覆盖的内容相同，不满足互补性定义，所以x在G中是冗余的，不能存在这样的现象。)，则G称为一个无冗余覆盖。 例3：在图7.4中有4个覆盖，其中 图7.4 对于(A)，x是覆盖，但不是无反例覆盖(图中表示反例)； 对于(B)，x, y是全能覆盖，也

18、是精确覆盖，但不是无冗余覆盖； 对于(C)，x是全能覆盖和无冗余覆盖，但不是精确覆盖； 对于(D)，x, y是互补覆盖和无冗余覆盖，但不是全能覆盖和精确覆盖。,7.4.3 穷举式搜索示例学习算法 1. 穷举式学习算法 所谓穷举式学习算法，就是穷尽式搜索整个版本空间，判断彼此间的层次关系(偏序关系)，确定(求出)覆盖，从而得到所要学习的概念。穷举式学习算法可以分为三个方面： (1)只有正例的学习，用于从一组实例中抽象出它们的共同特征； (2)有正例和反例的学习，可以从正反两个方面来确定一个概念的特性； (3)既有正例和反例、又有未知实例的学习，用于预测将来遇到的未知实例属于哪个概念，这才是学习的

19、真正目的。,2. 正例覆盖算法 算法1 正向搜索求精确全能覆盖 正向搜索就是从实例出发向上进行搜索。 (1)令R=(结果集合)，全体实例集合S，|S|1(实例个数)； (2)若|S|=1则学习完成，算法结束，实例本身就是所求概念； (3)在版本空间H中进行正向搜索，即：S出发向上走一步即S1=up(S)； (4)令S2=min(S1)，S3=x| xS2x覆盖所有实例，R=RS3； (5)若S2=S2S3不空，则令S=S2，转(3)；否则算法结束，所学概念在min(R)中。 例1：设有关于中国科学家的版本空间H如图7.5所示，其中实例全部为正例。试用算法1求所学概念。为了更好地说明算法，在“李

20、四光”和“地学家”之间省略了“地质学家”。 (1)S=华罗庚，李四光，竺可桢，吴有训，R=，进行第1轮搜索； (2)S1=up(S)=数学家，地学家，气象学家，物理学家，江苏人，湖北人，浙江人，江西人；,图7.5 (3)因为“气象学家”“地学家”，所以S2=min(S1)=数学家，气象学家，物理学家，江苏人，湖北人，浙江人，江西人，S3=，R=； (4)S=S2，进行第2轮搜索； (5)S1=up(S)=科学家，地学家，华东地区人，华中地区人；,(6)S2=min(S1)=地学家，华东地区人，华中地区人，S3=，R=； (7)S=S2，进行第3轮搜索； (8)S1=up(S)=科学家，中国人，

21、S3=S2=S1，R=S3=科学家，中国人为所学概念。 算法2 反向搜索求精确全能覆盖 反向搜索就是从H的最顶元素集出发向下进行搜索。 (1)令R=(结果集合)，全体实例集合S，|S|1(实例个数)，G=； (2)若|S|=1则学习完成，算法结束，实例本身就是所求概念； (3)在版本空间H中进行反向搜索，即：从G出发向下走一步即G1=down(G)； (4)删去G1中不能覆盖全部实例的元素y，得G2，令G3=x| x覆盖全部正例ydown(x)y已被删除(即y的上层元素，此处目的是使x为最低层次的覆盖全部实例的概念，以满足精确覆盖的要求)，R=RG3； (5)若G2不空，则令G=max(G2)

22、，转(3)；否则算法结束，所学概念在min(R)中。,可以验证，对于例1，使用反向学习算法求得的结果也是科学家，中国人 图7.6 例2：设有版本空间H如图7.6所示，使用反向搜索求精确全能覆盖。 第1轮搜索：G=, G1=x, y, G2=G1, G3=,R=； 第2轮搜索：G=x, y, G1=a, b, c, z, t, G3=x, y, z, R=G3，G2=z； 第3轮搜索：G=z, G1=a, b, c，G2=, G3=z, R=RG3=x, y, z，min(R)=x, z为求得结果。,因为在算法1和算法2中要反复使用比较操作xy，如是否覆盖全部实例，两个概念之间的层次关系等等。如

23、果每次用到时再来计算，会产生许多重复，降低了算法的效率。如果事先将H中每个元素之间的关系都计算出来存在一个表中，如H中每个元素的up集。用时只需检查一下即可。 3. 正反例覆盖算法 如果实例集中包含正例和反例，可以通过下述算法进行概念的学习。该算法也可称为Mitchell算法。 正向：覆盖正例；反向：不覆盖反例 算法3 双向搜索求全能覆盖 (1)令G=，S=； (2)对每个新的正例b，进行如下操作：(正向) 除去G中不能覆盖b的元素，即xG(bxDel x)； 如果G=，则学习失败，算法结束； 对S中每个不能覆盖b的元素作最小限度的泛化，即S1=gen(S, b)； 令S2=min(S1)，删

24、去S2中不受G覆盖的部分，即S3=y| yS2, zG, yz；,如果S3=，则学习失败，算法结束，否则S=S3，等待新的例子输入； (3)对每个新的反例c，进行如下操作：(反向) 除去S中覆盖c的元素，即xS(cxDel x)； 如果S=，则学习失败，算法结束； 对G中每个覆盖c的元素作最小限度的特化，即G1=spe(G, c)； 令G2=max(G1)，删去G2中不覆盖S的部分，即G3=y| yG2, zS, zy； 如果G3=，则学习失败，算法结束，否则G=G3，等待新的例子输入； (4)如果正反例均已输入完毕，而G、S均不为空，则 对于H中任何元素x，如果满足yG，xy，zS，zx，则

25、x可被认为是本次学习得到的一个概念； 如果G=S，则本次学习得到的每个概念都是精确的，既不能被泛化，也不能特化； 如果G=S且只有一个元素，则本次学习取得了它本来意义上的成功，学到了唯一的概念。,例3：设版本空间H如图7.3所示，输入反例“旅行车”和正例“中山装、睡袋”，使用算法3求学习的概念。学习步骤如下： (1)G=，S= (2)反例N1=“旅行车” (3)G1=spe(, 旅行车)=食，衣，睡袋，亭子间 (4)G2=max(G1)=食，衣，亭子间，G=G2 (5)正例P1=“中山装” (6)除去G中不覆盖P1的元素，G=衣 (7)S1=gen(, 中山装)=中山装，衣， (8)S2=mi

26、n(S1)=中山装，S=S2 (9)正例P2=“睡袋” (10)G覆盖P2，S1=gen(中山装, 睡袋)=衣，S=S1 此时，G=S=衣，学习成功。 ,以上介绍的都是求全能覆盖的算法，而实际上版本空间H中在某个层次上可能不存在全能覆盖(除了顶元素以外)，那么算法就会失败。因此算法3标明了失败出口。但是，求互补覆盖却可能成功，因为它不要求每个概念都覆盖全部正例，而是一组概念覆盖全部正例。 对求全能覆盖和互补覆盖是有区别的：全能覆盖的目的是找到一组实例的共同特性的刻划，这种刻划越精确越好，因为信息量就越大，所以算法1算法3都是求精确全能覆盖。而互补覆盖的目的是要找到一组只覆盖正例而不覆盖反例的概

27、念，因此组内的概念数目越少越好，因为此时概念集概括程度越高。 4. 求互补覆盖算法 介绍双向搜索求最抽象互补覆盖的算法，正向和反向搜索求互补覆盖算法可以通过修改对应的求全能覆盖算法来实现。此时要删去覆盖反例的概念，并把放入R的学习结果取上限即max(R)。,算法4 双向搜索求最抽象互补覆盖算法 (1)令R=，P=全体正例；|P|1； (2)如果|P|=1，则学习完成，算法结束，该正例本身即为所求； (3)如果P=，则学习完成，算法结束，学习结果=max(R)； (4)否则，令G=，从P中取正例a ，令S=a； (5)对每个反例c反复执行算法3中的(3)，使G不覆盖反例而覆盖a； (6)将G中元

28、素全部存入R； (7)从P中除去G中元素所覆盖的全部正例； (8)转(3)。 本算法的要点就是Michalski的Aq算法，并且包含了出错处理(在调用部分)。,5. 预测覆盖算法 包含大量未知实例的覆盖学习就是要预测那些和已知的正例与反例都不一样的例子是否属于正例。求覆盖的过程中，有乐观预测算法和保守预测算法，所谓乐观，就是搜索概念时只要不覆盖反例就尽量作泛化，尽量多地包括未知实例；而保守算法则是在搜索概念时，去掉那些可能包括在反例概念中的未知实例，然后再在剩下的未知实例中求被正例概念所覆盖的那些部分。 算法5 乐观预测正向求最抽象互补覆盖 (1)令R=(结果集合)，全体正例集合S，|S|1；

29、 (2)在版本空间H中进行正向搜索，即：S出发向上走一步即S1=up(S)； (3)删去S2=S1中覆盖反例的元素，S3=x| xSup(x)S2，R=RS3； (4)若S1=S1S2不空且|S1|1，则S=S1，转(2)；否则算法结束，当S1=时，R=RS1，所学概念在min(R)中。,算法6 保守预测正向求最抽象互补覆盖 (1)设P为正例集，N为反例集，U为未知实例集； (2)把N视为正例集，P视为反例集，U视为未知实例集，调用算法5求得覆盖F； (3)把P视为正例集，F视为反例集，UF视为未知实例集，调用算法5求得覆盖F，F即为所求。 图7.7 例4：图7.7中为正例，为反例，为未知，则

30、乐观算法求得结果=x，保守算法求得结果=y。,启发式搜索示例学习算法 至少有三种情况需要启发式搜索： 正例或反例数量非常大，或者不能一次获取时，需要分批处理，此时学习得到的概念只是相对正确(实例不全)； 版本空间非常大，穷举式搜索代价过高，需要对版本空间进行分割，然后在其子空间中进行搜索，但学习的结果可能不是最优的，甚至因为空间分割而造成学习失败； 正例和反例的分布十分复杂、互相交叉，甚至描述相同，则需要在容忍部分反例的情况下求正覆盖，此时必须对容忍程度即正反例覆盖的比例上作出决定。 相应地，有关启发式搜索学习算法也有三类： 第一类：限制搜索时参加的正例和反例个数，同时也限制作为正例泛化的中间

31、概念个数，使版本空间的搜索呈条状推进，因此可称为带宽搜索算法；,第二类：把版本空间分为若干子空间，子空间的全体等于H，每个子空间都覆盖全体实例。搜索在各个子空间内进行，只要有一个子空间可求得一组互补覆盖，则学习任务即可认为完成。如果各子空间均不能找到满意的覆盖，则把各子空间中搜索剩余的部分合并在一起进行搜索。 第三类：不要求所求概念集合为无反例集，而只要求它们覆盖的正例和反例数有一个合理的比例。 因为这些算法相对都比较复杂，本章只就第三类算法作概要介绍。其基本原理就是生成-测试方法。其要点包括： 确定某种原则找到H中一组概念ci，计算每个ci覆盖的正例和反例个数，甚至未知实例个数，然后给出一个

32、评分决定保留或舍弃ci，然后根据全部保留的概念决定是否停止算法。,算法7 爬山法 (1)给定正例集P、反例集N、版本空间H及H的子空间H； (2)根据某种原则在H中找到一组概念G=ci； (3)计算每个ci覆盖的正例和反例个数，如果可能也计算未知实例个数，然后根据某种公式计算ci的评分； (4)对每个ci作泛化或者特化操作得到ci，并和ci一样计算相应的评分； (5)比较ci和ci的评分，决定：保留ci、舍弃ci；或者保留ci、舍弃ci；或者ci和ci都保留；或者ci和ci都舍弃； (6)根据某个原则决定算法是否继续，若是则转(4)，否则结束算法，ci全体为学习结果。 算法中的第(2)步所说的

33、某种原则可以理解为各种求覆盖的算法，如前面介绍的。第(3)步的公式和第(5)步的比较都体现了启发式的思想。,7.5 类比学习,7.5.1 类比推理和类比学习方式 类比学习（learning by analogy）就是通过类比，即通过对相似事物加以比较所进行的一种学习 。 其推理过程如下 ： 回忆与联想- 选择 - 建立对应关系 -转换,7.5.2 类比学习过程与研究类型,类比学习主要包括如下四个过程： 输入一组已知条件和一组未完全确定的条件 。 对两组出入条件寻找其可类比的对应关系。 根据相似转换的方法，进行映射。 对类推得到的知识进行校验。,类比学习的研究可分为两大类： (1) 问题求解型的

34、类比学习 (2) 预测推定型的类比学习。它又分为两种方式： 一是传统的类比法 另一是因果关系型的类比,7.6.1 解释学习的过程 基于解释的学习(Explanation Based Learning)兴起于80年代中期(开创性工作：Mitchell/De Jong等) EBL依靠一个丰富的知识库。学习时用知识库中的知识证明具体实例属于某个概念，此过程称为解释过程。记录下该过程，作为一种控制解题的知识，再作适当推广，使推广后的知识不仅覆盖这一实例，而且能覆盖更多情况。记录并推广即把学习到的知识加入到数据库，从而提高以后解题的效率,7.6 基于解释学习,1. 基本的解释学习算法 算法1 基本EBL

35、算法思想 (1)给定一个具有丰富领域知识的知识库. (2)给定一个目标概念G. (3)输入一个实例e. (4)使用知识库中的领域知识或在专家的帮助下证明e是G的一个实例. 这一步称为解释. (5)对上一步中获得的解释进行推广, 得到一个更一般的解题过程. 这一步称为泛化. (6)把通过泛化得到的知识加进知识库中. 其中两个关键点：解释和泛化。如何生成一个解释，有两种方法：机器人规划程序STRIPS(Nilsson)中的目标回归法；与领域无关的解题器PRODIGY中基于解释的特化方法。通过解释结构进行泛化,2. 目标回归法 算法2 目标回归法 (1)设目标概念为G1G2Gn. (2)用实例的参数

36、代入目标概念后得到(可能是部分例化的)具体目标G1G2Gn. (3)把实例提供的信息（一般为例化的谓词）作为事实送入知识库中. (4)如果知识库中的信息使目标至少部分地得到满足, 则只考虑目标的剩余部分. 若剩余部分为空, 则回归完成. 算法结束. (5)如果目标未全部完成, 则取出其中的一个, 比如说G1 (6)使用向后推理进行回归：寻找这样的规则a和最一般合一置换 ，使得G1经过合一置换后成为当前状态应增加的谓词，而所有其他的目标(包括目标中已经被满足的那些部分)经过合一置换后又不会因使用本规则而被删除(即不受规则和置换操作的影响)。这就是变换目标（即向后推理）的过程，由此得到新目标。,(

37、7)如果存在一个回归序列，使最后的子目标全由知识库中的事实或最基本的谓词组成，则算法结束，此回归序列（即应用规则和置换的序列）就是所求的解释. 3. 实例 使用简化的例子，产生式规则中只有前提和增加表(条件函数和动作函数)两部分 目标概念: get-a-ticket (x) 领域理论 (知识库) : give(y, ticket, x)get-a-ticket(x) mk-friend(u,v) has(u, ticket) give(u, ticket, v) offer(x, gift, y) invite(x, y, restaurant) mk-friend(y, x) invite(

38、x, y, restaurant) invite(x, y, sauna) mk-friend(y, x) pay(x, fee, y) has(y, ticket) honest(y) give(y, ticket, x) pay(x, fee, y) has (y, ticket) honest(y) give(y, ticket, x) relative(x, y) mk-friend(y, x),设刘二想观看中韩足球对抗赛，但门票紧张，因此想到表弟王五在体育场看大门，可以弄到一张门票。于是刘二开始请客送礼，即先送两瓶二锅头，再请吃一次烧烤。然后王五大悦，送给刘二一张门票。 对此实例解释

39、的过程如下图，得到一条规则是： offer(刘二，二锅头，王五) invite(刘二，王五，烧烤) has(王五，门票) get-a-ticket(刘二) 本解释为苦于买不到门票的球迷提供了一条启发信息，需要推广,4. 基于解释的特化 算法3 基于解释的特化 (1)若目标概念为下列子概念的合取 F1F2Fn= F 则对目标概念的特化归结为对每个子概念的特化, 并得到如下的新目标: (Spec F1) (Spec F2) (Spec Fn ) = Spec F (其中Spec表示特化) (2)若目标概念为下列子概念的析取 F1F2 Fn= F 则有 Spec F = Spec Fj 其中Fj是诸

40、Fi中第一个与实例一致 (不矛盾) 的子概念. (3)若目标概念是如下形式的一个循环: F= (FORALL(x, ) SUCH THAT F1, F2),它的含意是: 求所有满足条件F1 (x, )的F2. 此时应做的操作是先找出F2的所有实例, 然后用条件F1 (x, )检查之, 设共有n个F2的实例满足此条件, 则结果为: (Spec F2) 1 (Spec F2) 2(Spec F2) n 其中每个括号内的F2代表一个实例 (4) 若目标概念是F, 则不加改变地送回结果F. (5) 若目标概念是原子命题 p(x1, x2, ,xn) , 则不加改变地送回结果p(x1, x2, ,xn)

41、, 此处原子命题是未用任何规则定义的命题. (6) 若目标概念是非原子命题 p(x1, x2, ,xn) , 则 (a)找到定义此命题的规则 规则条件p(y1, y2, , yn) 要求该规则与实例是一致的. (b) 用相应的xi代入诸yi. (c) 对规则条件中各变量相应地重新命名. (d) 把 (Spec规则条件) 作为结果送回.,5. 泛化 一个未经泛化的解释学习很难有实用价值。因为对实例解释得到的知识只适用于该实例，如上面实例中只适合球迷搞门票。甚至日期、体育场、足球赛都不能改。实际上搞到任何紧俏商品的路数都可以参考此处的知识。要把具体实例的剖析上升为经验，泛化是必由之路。 算法4(算

42、法思想) 泛化策略 下述策略可用于泛化一个解释 (1)删去所有与学习目标无关的具体属性 (2)把常量换成变量 (3)更换解释当中的子结构 (4)在解释结构中增加新的析取子结构 (5)推广各子结构的顺序关系 (6)推广各子结构出现的次数,以上例为例，泛化策略的运用为： (1)删去无关属性：如刘二请客花了100元，解释时即已经删去 (2)把常量换成变量：将烧烤泛化任何一个餐厅，具体人名泛化为任意一个人 规则泛化前： offer(刘二，二锅头，王五) invite(刘二，王五，烧烤) has(王五，门票) get-a-ticket(刘二) 泛化后： offer(X，gift，Y) invite(X，

43、Y，restaurant) has(Y，ticket) get-a-ticket(X) (3)更换解释当中的子结构：进一步搜索，可发现relative(刘二，王五)。按照知识库中规则，利用亲戚关系也可以弄到门票，则刘二就不必请客送礼了。此时可得新的解释结构（也可视作替换） relative(X, Y) has(Y，ticket) get-a-ticket(X) 此外还可以有其他解释,(4)在解释结构中增加新的析取子结构：如请客之外送礼或者请洗桑拿浴均可，故可在合取当中出现析取 (5)推广各子结构的顺序关系：获得规则中的顺序可以改变，如invite和offer改变次序 (6)推广各子结构出现的次

44、数：如送礼不嫌多，将offer改为 . offer(x, gift, y)n . get-a-ticket(X) 6. 泛化方法 在各类基于解释的学习系统中,泛化并非都是自动进行的,大致有如下三种方法. (1)按照事先确定的机制, 由学习系统机械地执行. (2)按照某种启发式原则, 由学习系统实行试探式的泛化, 然后由专家给予证实. (3)直接由专家给出泛化.,7. 可操作性 可操作性概念对于基于解释的学习来说是很重要的。不同研究者认识不尽相同。一般说，有如下定义。 定义1概念的可用性：一个概念称为是可用的，如果存在一个算法能在有限步内判断任何实例是否属于此概念。 定义2概念的有用性：概念称为

45、有用的，如果此算法的复杂性是可接受的。 定义3概念的可有效使用性：如果此算法是高效的。 定义4概念的可操作性：使一个概念可操作就是把该概念从不可用的变为可用的，或者从可用的变为有用的，或者从有用的变为可有效使用的，或者使有效使用性更好。,7.6.2 解释学习的应用 主要介绍解释学习用于知识库维护(PRODIGY系统)和自然语言句法分析 1. PRODIGY系统中的执行模块(知识的例化) 算法5 (解释过程) (1)从搜索树中选择一个叶节点. (2)为该节点选择一个目标. (3)为该目标选择一个合适的操作. (4)把该操作中的变量例化为当前求解问题的实际参数. (5)若例化后的操作能够应用, 则

46、应用之. (6)若上述第1至第4步都不能成功, 则考虑把一个可能的目标分解为子目标, 然后对各子目标实施上面的第3至5步. 各个子目标的解都求出后, 就把它们综合成一个总体解.,2. 获取制定决策的控制知识 算法6 (多角度学习) 下列四方面的控制知识都是PRODIGY 学习的内容： (1)关于成功的知识，如果算法5的第5步能够（在某一次执行中）成功，则把第1至第4步的各项选择记录下来作为一条成功的经验，称为优先规则. (2)关于失败的知识, 如果算法5的第5步没有成功, 则把第1至第4步的选择作为失败的教训记录下来, 称为拒绝规则. (3)关于唯一选择的规则. 如果在本算法的第1步记录下来的优先规则是算法5在当时情况下的唯一可能的选择(其它的选择都导致失败), 则把这条优先规则记录为单选规则. (4)关于目标相互作用的规则. 如果在执行算法5的过程中由于第5步的失败而导致回溯, 则回溯过程被记录成一条优先规则.,在“弄门票”例子当中，对本算法可能有如下一些应用： (1)刘二因请王五吃烧烤而得到了门票，于是“请客”作为优先规则记录下来 (2)刘二因拿着