[计算机软件及应用]aai08解释学习 高级人工智能 史忠植.ppt

2019/3/29,高级人工智能-解释学习 史忠植,1,第八章 解释学习,史忠植 中科院计算所,2019/3/29,高级人工智能-解释学习 史忠植,2,内容,8.1 概述 8.2 解释学习模型 8.3 解释泛化学习方法 8.4 全局取代解释泛化方法 8.5 解释特化学习方法 8.6 解释泛化的逻辑程序 8.7 基于知识块的SOAR系统 8.8 可操作性标准 8.9 不完全领域知识下的解释学习,2019/3/29,高级人工智能-解释学习 史忠植,3,8.1 概述,基于解释的学习： 一种从单个观察中抽象出通用规则的方法 目标是下次可以快速地解决类似的问题 记忆通过保存结果和避免从零开始解决问题来提高速度 更进一步EBL从观察到规则,2019/3/29,高级人工智能-解释学习 史忠植,4,解释学习,解释学习(Explanation-Based Learning, 简称EBL)是一种分析学习方法，在领域知识指导下, 通过对单个问题求解实例的分析, 构造出求解过程的因果解释结构, 并获取控制知识,以便用于指导以后求解类似问题。,2019/3/29,高级人工智能-解释学习 史忠植,5,解释学习,1983年美国Illinois大学的DeJong提出。 1986年, Mitchell, Keller 和 Kedar-Cabelli 提出了解释的泛化(Explanation-Based Generalization, 简称EBG)的统一框架, 1986年DeJong 和Mooney提出全局取代解释泛化Explanation Generalization using Global Substitutions, 缩写EGGS) 方法 1987年卡耐基-梅隆大学的Minton 和 Carbonell提出解释特化 (Explanation-Based Specialization，简写EBS)学习方法,2019/3/29,高级人工智能-解释学习 史忠植,6,为什么要用EBL,解释为什么一个想法是好的比提出一个想法容易得多 一旦理解了一件事，就可以泛化并重用于其它情况 从例子中抽象出通用规则 通过对一棵证明树的常量变量化, EBL可以同时创建两棵证明树,2019/3/29,高级人工智能-解释学习 史忠植,7,基本的EBL,给定一个例子，使用背景知识构建一棵证明树 同时，为可变化的目标构建一棵泛化证明树 构建一条新规则（叶子 = 根） 去掉所有与目标中变量真正无关的条件,2019/3/29,高级人工智能-解释学习 史忠植,8,解释学习,(1)通过分析一个求解实例来产生解释结构; (2)对该解释结构进行泛化, 获取一般的控制规则。,2019/3/29,高级人工智能-解释学习 史忠植,9,解释的含义,对所产生的结论的推理过程作详细说明，以增加系统的可接受性； 对错误决策进行追踪，发现知识库中知识的缺陷和错误的概念； 对初学的用户进行训练。,2019/3/29,高级人工智能-解释学习 史忠植,10,解释的方法,预制文本法。预先用自然语言写好，并插入程序中； 执行追踪法。遍历目标树，通过总结与结论相关的目标，检索相关规则，以说明结论是如何得到的； 策略解释法。明确表示控制知识，即用元知识概括地描述，与领域规则完全分开。从策略的概括表示中产生解释，能为用户提供问题求解策略的解释。,2019/3/29,高级人工智能-解释学习 史忠植,11,EBL的效率,选择一条通用规则 太多规则 - 推理太慢 目标驱动 - 极大地提高了速度 尽可能的通用 可操作性 - 一个子目标是可操作的，意思是容易解决 可操作性和通用性之间的平衡 对EBL学习效率的实验分析,2019/3/29,高级人工智能-解释学习 史忠植,12,8.2 解释学习模型,概念描述空间,概念空间,例子空间,D1 不可操作的,可操作 D2,C1,I1,I2,I3,解释学习的空间描述,2019/3/29,高级人工智能-解释学习 史忠植,13,可操作特性,系 统,可 变 性,粒 度,确 定 性,GENESIS,动态,二进制,不保证,LEX2,动态,二进制,不保证,SOAR,动态,二进制,不保证,PRODIGY,静态,连续,不保证,MetaLEX,动态,连续,保证,2019/3/29,高级人工智能-解释学习 史忠植,14,解释学习的模型,EXE,概念描述的转换,结果是否可操作,D1,D2,KB,PS,Y,N,2019/3/29,高级人工智能-解释学习 史忠植,15,8.3 解释泛化学习方法,解释泛化学习问题： 已知： 目标概念 训练例 领域理论 可操作性标准 欲求： 训练实例的泛化，使之满足以下条件 是目标概念的充分概念描述 满足可操作性标准,2019/3/29,高级人工智能-解释学习 史忠植,16,EBL方法,解释 利用领域理论知识解释为什么训练例满足目标概念的定义 泛化 确定解释成立的最通用的条件,2019/3/29,高级人工智能-解释学习 史忠植,17,例子,目标概念：一对物体，SAFE-TO-STACK(x,y)，其中STACK(x,y)NOT(FRAGILE(y)LIGHTER(x,y)。 训练实例： ON(OBJ1,OBJ2) ISA(OBJ1,BOX) ISA(OBJ2,ENDTABLE) COLOR(OBJ1,RED) COLOR(OBJ2,BLUE) VOLUME(OBJ1,1) DENSITY(OBJ1,.1) ,2019/3/29,高级人工智能-解释学习 史忠植,18,领域知识： VOLUME(p1,v1)DENSITY(p1,d1)WEIGHT(p1,v1*d1) WEIGHT(p1,w1)WEIGHT(p2,w2)LESS(w1,w2)LIGHTER(p1,p2) ISA(p1,ENDTABLE)WEIGHT(p1,5)(default) LESS(.1,5) 可操作标准：概念定义必须要用描述实例中的谓词，或者选自领域知识易于评测的谓词。 确定： 训练实例的泛化是对目标概念给以充分定义，并且满足可操作性标准。,2019/3/29,高级人工智能-解释学习 史忠植,19,SAFE-TO-STACK(OBJ1,OBJ2)解释树,SAFE-TO-STACK(OBJ1,OBJ2),LIGHTER(OBJ1,OBJ2),WEIGHT(OBJ1,.1),LESS(.1,5),WEIGHT(OBJ2,5),VOLUME(OBJ1,1),DENSITY(OBJ1,.1),ISA(OBJ2,ENDTABLE),2019/3/29,高级人工智能-解释学习 史忠植,20,SAFE-TO-STACK(OBJ1,OBJ2)解释的泛化过程,SAFE-TO-STACK(p1,p2),LIGHTER(x,y),WEIGHT(p1,v1*d1),WEIGHT(x,w1) LESS(w1,w2) WEIGHT(y,w2),WEIGHT(p2,5),VOLUME(p1,v1),DENSITY(p1,d1),ISA(p2,ENDTABLE),SAFE-TO-STACK(x,y),LIGHTER(p1,p2),LIGHTER(p1,p2),WEIGHT(p1,w1),LESS(w1,w2),WEIGHT(p2,w2),x/p1,v1*d1/w1,y/p2,5/w2,VOLUME(x,v1) DENSITY(x,d1) LESS(v1*d1,5),ISA(y,ENDTABLE),R3:,R4:,R2:,R1:,x/p1,y/p2,x/p1,y/p2,2019/3/29,高级人工智能-解释学习 史忠植,21,解释与泛化交替进行,问题的逻辑描述 逻辑的表示方法使EBG的语义更为清楚，为学习提供了方便的语言环境 产生解释结构 从目标开始反向推理，分解目标。应用规则时，同时将规则应用到变量化的目标概念上，这样就同时生成了解释结构和泛化的解释结构 生成控制规则 将泛化的解释结构的所有叶结点的合取作为前件，以定点的目标概念为后件，略去解释结构的中间部件，生成泛化的产生式规则。,2019/3/29,高级人工智能-解释学习 史忠植,22,8.4 全局取代解释泛化方法,1986年DeJong和Mooney提出全局取代解释泛化方法。在EBG方法中，通过实例解释结构的目标概念回归，忽略析取实现泛化。,2019/3/29,高级人工智能-解释学习 史忠植,23,STRIPS的例子,初始世界模型：,目标公式：,2019/3/29,高级人工智能-解释学习 史忠植,24,STRIPS采用的操作符如下：,2019/3/29,高级人工智能-解释学习 史忠植,25,三角表,2019/3/29,高级人工智能-解释学习 史忠植,26,泛化三角表,2019/3/29,高级人工智能-解释学习 史忠植,27,EGGS问题描述,给定： 领域理论： 领域中对象的种类和特性的定义 一组关于对象特性和相互关系的推理规则 一组问题求解的操作和已知的泛化图式 目标：目标状态的一般规约。 初始世界状态：关于世界及其特性的规约。 观察到的操作/状态序列。 确定 达到目标状态的一个新模式,2019/3/29,高级人工智能-解释学习 史忠植,28,泛化过程的形式化描述,for each equality between expression and in the explanation structure: if is the antecedent of a domain rule and is the consequent of a domain rule then let = the most general unifier of and let = (* update SPECIFIC substitution) let = the most general unifier of and let = (* update GENERAL substitution) else let = the most general unifier of and let = (* update SPECIFIC substitution),2019/3/29,高级人工智能-解释学习 史忠植,29,EGGS解释泛化算法,let be the null substitution . for each equality between and in the explanation structure do: let be the result of applying to . let be the result of applying to . let be the MGU of and . let be . for each pattern in the explanation structure do: replace with .,2019/3/29,高级人工智能-解释学习 史忠植,30,8.5 解释特化学习方法,从多种目标概念学习，其解释过程是对每个目标概念进行详细描述。解释过程结束后，把得到在有关目标概念的描述转换成一条相应的控制规则。可以用这些规则来选择合适的节点、子目标、算子及约束。较好地克服了EBG方法中过分一般化的缺点。,2019/3/29,高级人工智能-解释学习 史忠植,31,PRODIGY体系结构,问 题,PS跟踪,求 解,控制知识,规 划 库,领域知识,抽象层次,EBL,派生抽取,抽象生成器,实 验,外部处理,用户问题,问题求解器,派生 重演,多级,2019/3/29,高级人工智能-解释学习 史忠植,32,PRODIGY的学习,解释过程 如果概念是原语，则不改变返回。 访问识别器，取出规则；获得子概念，特化子概念；重命名变量；置换并简化。 返回。 学习控制规则 由成功概念学到preference rules； 由失败概念学到rejection rules； 由其它选择都失败学到selection rules； 知识表示 领域层公理 构筑层公理,2019/3/29,高级人工智能-解释学习 史忠植,33,8.6 解释泛化的逻辑程序,工作原理 归结原理：设两个短句C1、C2无公共变量，L1和L2分别是C1和C2的两个文字，若L1和L2存在一个最一般的合一置换，那么子句（C1-L1) (C2-L2)就是两个子句C1和C2的归结式。,2019/3/29,高级人工智能-解释学习 史忠植,34,Turbo Prolog的合一算法,自由变量可以和任意项合一。合一后该自由变量约束为与之合一的项。 常量可与自身或自由变量合一。 若两个复合项的函子相同且函子所带参量个数一样，则这两个复合项可以合一的条件是：所有子项能对应合一。约束变量要用合一后的约束值替换。,2019/3/29,高级人工智能-解释学习 史忠植,35,解释泛化的逻辑程序设计,解释 合一算法作为基础，用Prolog谓词来完成 把领域理论用内部数据库的形式存储。 泛化 包括常量用变量代替、新项合成等工作。 解释和泛化交叉进行,2019/3/29,高级人工智能-解释学习 史忠植,36,Prolog简单的元解释器,prolog(Leaf): -clause(Leaf, true). prolog(Goal, Goal2): - prolog(Goal1), prolog(Goal2). Prolog(Goal): - clause(Goal, Clause), prolog(Clause).,2019/3/29,高级人工智能-解释学习 史忠植,37,EBG程序,prolog_ebg(X_Goal, X_Gen, X_Goal, X_Gen: -clause(X_Goal, true). prolog_ebg(X_Goal, Y_Goal), (X_Gen, Y_Gen), Proof, GenProof):- prolog_ebg(X_Goal, X_Gen, X_Proof, X_GenProof), prolog_ebg(Y_Goal, Y_Gen, Y_Proof, Y_GenProof), concat(X_Proof, Y_Proof, Proof), concat(X_GenProof, Y_GenProof, GenProof). prolog_ebg(X_Goal, X_Gen, Proof, GenProof):- clause(X_Gen, Y_Gen), copy(X_Gen: -Y_Gen), (X_Goal: -Y_Goal), prolog_ebg(Y_Goal, Y_Gen, Y_Proof, Y_GenProof), concat(X_Goal, Y_Proof, Proof), concat(X_Gen, Y_GenProof, GenProof).,2019/3/29,高级人工智能-解释学习 史忠植,38,例子“自杀”,目标概念：suicide(x) 领域理论：一组子句或称规则。 suicide(x)：-kill(x,x). kill(A,B)：-hate(A,B), possess(A,C), weapon(C). hate(A,A)：-depressed(A). possess(A,C)：-buy(A,C). weapon(Z)：-gun(Z). 训练例：一组事实子句。 depressed(john). buy(john,gun1). gun(gun1). suicide(john). 可操作性标准：暂时简单地处理为静态标准。 operational(depressed). operational(gun). operational(buy).,2019/3/29,高级人工智能-解释学习 史忠植,39,suicide(john)的解释结构,suicide(john),kill(john,john),weapon(gun1),hate(john,john),possess(john,gun1),depressed(john),buy(john,gun1),gun(gun1),2019/3/29,高级人工智能-解释学习 史忠植,40,目标概念suicide(x)的泛化过程,suicide(a),kill(x,x),weapon(C),hate(A,B),possess(A,C),depressed(A),buy(A,Z),gun(Z),suicide(x),goal concept,kill(a,a),kill(A,B),weapon(C),hate(x,x),possess(x,C),R5 weapon(C),R3 hate(A,B),R4 possess(A,C),depressed(x),x/A,buy(x,Z),x/A,Z/C,Z/C,R2,R1,x/a,x/A,x/B,2019/3/29,高级人工智能-解释学习 史忠植,41,8.7 基于知识块的SOAR系统,记忆块：用一种符号来标记另一些符号的存储结构模型。 SOAR的学习机制：由外部专家的指导来学习一般的搜索控制知识。外部指导可以是直接劝告，也可以是给出一个直观的简单问题。系统把外部指导给定的高水平信息转化为内部表示，并学习搜索记忆块。,2019/3/29,高级人工智能-解释学习 史忠植,42,SOAR的体系结构,记忆块机制,对 象,优 先,语境站,决策过程,工作存储器管理器,产生式存储器,工作存储器,2019/3/29,高级人工智能-解释学习 史忠植,43,九宫问题,2,3,1,8,4,7,6,5,初始状态,1,2,3,8,4,7,6,5,目标状态,2019/3/29,高级人工智能-解释学习 史忠植,44,求解过程,G1 solve-eight puzzle P1 eight-puzzle sd S1 O1 place-blank =G2 (resolve-no-change) P2 eight-puzzle S1 =G3 (resolve-tie-operator) P3 tie S2 (left, up, down),2,3,1,8,4,7,6,5,2019/3/29,高级人工智能-解释学习 史忠植,45,O5 evaluate-object(O2(left) =G4 (resolve-no-change) P2 eight-puzzle S1 O2 left S3 O2 left S4 S4 O8 place-1,2,3,1,8,4,7,6,5,2019/3/29,高级人工智能-解释学习 史忠植,46,8.8 可操作性标准,如果给定： 一个概念描述。 一个执行系统，它利用概念描述改善执行情况。 改善执行系统的各种要求，应明确各要求的类型和程度。 那么若满足下列二条件则该概念描述是可操作的： 可用性：执行系统可以使用该概念描述 效用型：使用概念描述时，系统的运行得到要求的改善,2019/3/29,高级人工智能-解释学习 史忠植,47,PRODIGY的效用,控制规则的可用性： Utility = (AvrSavings ApplicFreq) - AvrMatchCost 其中： AvrMatchCost = 匹配该规则的平均耗费 AvrSavings = 应用该规则时，平均节约的时间 ApplicFreq = 应用该规则的频度,2019/3/29,高级人工智能-解释学习 史忠植,48,SOAR系统的可操作性,SOAR系统主要通过Chunking来获取知识，因此有意忽略了可用性： 假设Chunking是自动完成的； SOAR系统的性能是由完成一项任务所需做的抉择次数来衡量的。,2019/3/29,高级人工智能-解释学习 史忠植,49,MRS-EBG的可操作性,将可操作性标准处理为可证明的。 可操作性是在解释过程中确定的，一旦某一分支由于没有可操作的定义而终结，就立即进行回溯，寻找该分支的另一能够产生一可操作的概念定义的证明。这样，一定能得到目标概念的可操作性描述。,2019/3/29,高级人工智能-解释学习 史忠植,50,META-LEX的处理方法,通过经验来评估可操作性：在系统中使用概念描述，然后看系统的行为是否达到了事先提出的系统目标。,2019/3/29,高级人工智能-解释学习 史忠植,51,8.9 不完全领域知识下的解释学习,领域知识的不完善性可能有以下三种情况： 不完整(incomplete)：缺少规则、知识 不正确(incorrect)：有些规则不合理 难处理的(intractable)：过于繁杂,2019/3/29,高级人工智能-解释学习 史忠植,52,逆归结方法,当解释过程由于缺乏某条规则而无法继续下去时，学习过程即告失败。可以采用逆归结方法克服这个问题。 逆归结原理是根据归结子句和一条原子句，求另一条原子句。,2019/3/29,高级人工智能-解释学习 史忠植,53,依赖表例子,知识库： Rule 1. Sentence(S0,S):-noun-phrase(S0,S1), verb-phrase(S1,S). Rule 2. noun-phrase(S0,S):-determiner(S0,S1), noun(S1,S). Rule 3. noun-phrase(S0,S):-name(S0,S). Rule 4. verb-phrase(