2009-8-20 高级人工智能 -解释学习 史忠植 1
第八章 解释学习史忠植中科院计算所
2009-8-20 高级人工智能 -解释学习 史忠植 2
内容
8.1 概述
8.2 解释学习模型
8.3 解释泛化学习方法
8.4 全局取代解释泛化方法
8.5 解释特化学习方法
8.6 解释泛化的逻辑程序
8.7 基于知识块的 SOAR系统
8.8 可操作性标准
8.9 不完全领域知识下的解释学习
2009-8-20 高级人工智能 -解释学习 史忠植 3
8.1 概述基于解释的学习：
一种从单个观察中抽象出通用规则的方法
目标是下次可以快速地解决类似的问题
记忆 —— 通过保存结果和避免从零开始解决问题来提高速度
更进一步 EBL从观察到规则
2009-8-20 高级人工智能 -解释学习 史忠植 4
解释学习解释学习 (Explanation-Based Learning,
简称 EBL)是一种分析学习方法，在领域知识指导下,通过对单个问题求解实例的分析,构造出求解过程的因果解释结构,并获取控制知识,以便用于指导以后求解类似问题。
2009-8-20 高级人工智能 -解释学习 史忠植 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)学习方法
2009-8-20 高级人工智能 -解释学习 史忠植 6
为什么要用 EBL
解释为什么一个想法是好的比提出一个想法容易得多
一旦理解了一件事，就可以泛化并重用于其它情况
从例子中抽象出通用规则
通过对一棵证明树的常量变量化,EBL可以同时创建两棵证明树
2009-8-20 高级人工智能 -解释学习 史忠植 7
基本的 EBL
给定一个例子，使用背景知识构建一棵证明树
同时，为可变化的目标构建一棵泛化证明树
构建一条新规则（叶子 => 根）
去掉所有与目标中变量真正无关的条件
2009-8-20 高级人工智能 -解释学习 史忠植 8
解释学习
(1)通过分析一个求解实例来产生解释结构 ;
(2)对该解释结构进行泛化,获取一般的控制规则。
2009-8-20 高级人工智能 -解释学习 史忠植 9
解释的含义
1) 对所产生的结论的推理过程作详细说明，
以增加系统的可接受性；
2) 对错误决策进行追踪，发现知识库中知识的缺陷和错误的概念；
3) 对初学的用户进行训练。
2009-8-20 高级人工智能 -解释学习 史忠植 10
解释的方法
1) 预制文本法。预先用自然语言写好，并插入程序中；
2) 执行追踪法。遍历目标树，通过总结与结论相关的目标，检索相关规则，以说明结论是如何得到的；
3) 策略解释法。明确表示控制知识，即用元知识概括地描述，与领域规则完全分开。
从策略的概括表示中产生解释，能为用户提供问题求解策略的解释。
2009-8-20 高级人工智能 -解释学习 史忠植 11
EBL的效率
选择一条通用规则
太多规则 -> 推理太慢
目标驱动 - 极大地提高了速度
尽可能的通用
可操作性 - 一个子目标是可操作的，意思是容易解决
可操作性和通用性之间的平衡
对 EBL学习效率的实验分析
2009-8-20 高级人工智能 -解释学习 史忠植 12
8.2 解释学习模型概念描述空间 概念空间 例子空间
D1
不可操作的可操作
D2
C1 I1
I2
I3
解释学习的空间描述
2009-8-20 高级人工智能 -解释学习 史忠植 13
可操作特性系 统 可 变 性 粒 度 确 定 性
GENESIS 动态 二进制 不保证
LEX2 动态 二进制 不保证
SOAR 动态 二进制 不保证
PRODIGY 静态 连续 不保证
MetaLEX 动态 连续 保证
2009-8-20 高级人工智能 -解释学习 史忠植 14
解释学习的模型
EXE 概念描述的转换 结果是否可操作D1 D2
KB PS
Y
N
2009-8-20 高级人工智能 -解释学习 史忠植 15
8.3 解释泛化学习方法解释泛化学习问题：
已知：
目标概念
训练例
领域理论
可操作性标准
欲求：
训练实例的泛化，使之满足以下条件
1) 是目标概念的充分概念描述
2) 满足可操作性标准
2009-8-20 高级人工智能 -解释学习 史忠植 16
EBL方法
1,解释
利用领域理论知识解释为什么训练例满足目标概念的定义
2,泛化
确定解释成立的最通用的条件
2009-8-20 高级人工智能 -解释学习 史忠植 17
例子
目标概念：一对物体 <x,y>,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)
…
2009-8-20 高级人工智能 -解释学习 史忠植 18
领域知识：
VOLUME(p1,v1)∧DENSITY(p1,d1)→WEIGHT(p1,v1*d1)
WEIGHT(p1,w1)∧WEIGHT(p2,w2)∧LESS(w1,w2)→LIG
HTER(p1,p2)
ISA(p1,ENDTABLE)→WEIGHT(p1,5)(default)
LESS(.1,5)
…
可操作标准：概念定义必须要用描述实例中的谓词，或者选自领域知识易于评测的谓词。
确定：
训练实例的泛化是对目标概念给以充分定义，并且满足可操作性标准。
2009-8-20 高级人工智能 -解释学习 史忠植 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)
2009-8-20 高级人工智能 -解释学习 史忠植 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}
2009-8-20 高级人工智能 -解释学习 史忠植 21
解释与泛化交替进行
1,问题的逻辑描述
逻辑的表示方法使 EBG的语义更为清楚，
为学习提供了方便的语言环境
2,产生解释结构
从目标开始反向推理，分解目标。应用规则时，同时将规则应用到变量化的目标概念上，这样就同时生成了解释结构和泛化的解释结构
3,生成控制规则
将泛化的解释结构的所有叶结点的合取作为前件，以定点的目标概念为后件，
略去解释结构的中间部件，生成泛化的产生式规则。
2009-8-20 高级人工智能 -解释学习 史忠植 22
8.4 全局取代解释泛化方法
1986年 DeJong和 Mooney提出全局取代解释泛化方法。在 EBG方法中，通过实例解释结构的目标概念回归，忽略析取实现泛化。
2009-8-20 高级人工智能 -解释学习 史忠植 23
STRIPS的例子
初始世界模型：
),( 1RR O B O TI N R O O M
),( 21 RB O XI N R O O M
),,( 211 RRDC O N N E C T S
)( 1B OXB OX
..
)],,(),,()[,,( yzxC O N N E C T SzyxC O N N E C T Szyx
)],()()[( 1RxI N R O O MxB O Xx
),,( 321 RRDC O N N E C T S
目标公式：
2009-8-20 高级人工智能 -解释学习 史忠植 24
STRIPS采用的操作符如下：
),,( 21 rrdG O T H R U
),,,(),(:Pr 211 rrdC O N N E C T SrR O B O TI N R O O Meo n d i t i o n?
),,(,1rR O B O TI N R O O Ml i s tD el et e
),(,2rR O B O TI N R O O Ml i s tA d d
),,,( 21 rrdbP U S H T H R U
),,(),(:Pr 211 rrdC O N N E C T SrR O B O TI N R O O Meo n d i t i o n?
),,(,1rR O B O TI N R O O Ml i s tD el et e
),(,2rR O B O TI N R O O Ml i s tA d d
),,( 1rbI N R O O M
),( 2rbI N R O O M
),,( 1rbI N R O O M?
2009-8-20 高级人工智能 -解释学习 史忠植 25
三角表
),( 1RR O B O TI N R O O M
),,( 211 RRDC O N N E C T S ),,( 21 rrdG O T H R U
),( 2RR O B O TI N R O O M),( 21 RB O XI N R O O M
),,( 211 RRDC O N N E C T S
),,( zyxC ON N E C T S
),,( yzxC ON N E C T S?
),,,( 21 rrdbP U S H T H R U
),( 1RR O B O TI N R O O M
),( 11 RB OXI N R OO M
2009-8-20 高级人工智能 -解释学习 史忠植 26
泛化三角表
),( 2pR O B O TI N R O O M
),,( 523 pppC O N N E C T S ),,( 523 pppG O T H R U
),( 5pR O B O TI N R O O M),( 56 ppI N R O O M
),,( 598 pppC O N N E C T S
),,( zyxC ON N E C T S
),,( yzxC ON N E C T S?
),,,( 9586 ppppP U S H T H R U
),( 9pR O B O TI N R O O M
),( 96 ppI N R O O M
2009-8-20 高级人工智能 -解释学习 史忠植 27
EGGS问题描述给定：
领域理论：
领域中对象的种类和特性的定义
一组关于对象特性和相互关系的推理规则
一组问题求解的操作和已知的泛化图式
目标：目标状态的一般规约。
初始世界状态：关于世界及其特性的规约。
观察到的操作 /状态序列。
确定
达到目标状态的一个新模式
2009-8-20 高级人工智能 -解释学习 史忠植 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)
1e 2e
1e 2e
1e?2e
1e?2e
1e?2e
2009-8-20 高级人工智能 -解释学习 史忠植 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,
ip jp
'ip? ip
'jp? jp
'ip 'jp
kp
kp?kp
2009-8-20 高级人工智能 -解释学习 史忠植 30
8.5 解释特化学习方法从多种目标概念学习，其解释过程是对每个目标概念进行详细描述。解释过程结束后，把得到在有关目标概念的描述转换成一条相应的控制规则。可以用这些规则来选择合适的节点、
子目标、算子及约束。较好地克服了 EBG方法中过分一般化的缺点。
2009-8-20 高级人工智能 -解释学习 史忠植 31
PRODIGY体系结构问 题
PS跟踪求 解控制知识规 划 库领域知识抽象层次
EBL
派生抽取抽象生成器实 验外部处理用户问题问题求解器派生重演 多级
2009-8-20 高级人工智能 -解释学习 史忠植 32
PRODIGY的学习
1,解释过程
如果概念是原语，则不改变返回。
访问识别器，取出规则；获得子概念，特化子概念；重命名变量；置换并简化。
返回。
2,学习控制规则
由成功概念学到 preference rules；
由失败概念学到 rejection rules；
由其它选择都失败学到 selection rules；
3,知识表示
领域层公理
构筑层公理
2009-8-20 高级人工智能 -解释学习 史忠植 33
8.6 解释泛化的逻辑程序工作原理归结原理：设两个短句 C1,C2无公共变量，
L1和 L2分别是 C1和 C2的两个文字，若 L1和
L2存在一个最一般的合一置换，那么子句
（ C1-L1) (C2-L2)就是两个子句 C1和 C2的归结式。
2009-8-20 高级人工智能 -解释学习 史忠植 34
Turbo Prolog的合一算法
1) 自由变量可以和任意项合一。合一后该自由变量约束为与之合一的项。
2) 常量可与自身或自由变量合一。
3) 若两个复合项的函子相同且函子所带参量个数一样，则这两个复合项可以合一的条件是：所有子项能对应合一。约束变量要用合一后的约束值替换。
2009-8-20 高级人工智能 -解释学习 史忠植 35
解释泛化的逻辑程序设计
1,解释
合一算法作为基础，用 Prolog谓词来完成
把领域理论用内部数据库的形式存储。
2,泛化
包括常量用变量代替、新项合成等工作。
3,解释和泛化交叉进行
2009-8-20 高级人工智能 -解释学习 史忠植 36
Prolog简单的元解释器
prolog(Leaf),-clause(Leaf,true).
prolog((Goal,Goal2)),-
prolog(Goal1),
prolog(Goal2).
Prolog(Goal),-
clause(Goal,Clause),
prolog(Clause).
2009-8-20 高级人工智能 -解释学习 史忠植 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).
2009-8-20 高级人工智能 -解释学习 史忠植 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).
2009-8-20 高级人工智能 -解释学习 史忠植 39
suicide(john)的解释结构
suicide(john)
kill(john,john)
weapon(gun1)hate(john,john) possess(john,gun1)
depressed(john) buy(john,gun1) gun(gun1)
2009-8-20 高级人工智能 -解释学习 史忠植 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}
2009-8-20 高级人工智能 -解释学习 史忠植 41
8.7 基于知识块的 SOAR系统记忆块：用一种符号来标记另一些符号的存储结构模型。
SOAR的学习机制：由外部专家的指导来学习一般的搜索控制知识。外部指导可以是直接劝告，也可以是给出一个直观的简单问题。系统把外部指导给定的高水平信息转化为内部表示，
并学习搜索记忆块。
2009-8-20 高级人工智能 -解释学习 史忠植 42
SOAR的体系结构记忆块机制对 象优 先语境站决策过程工作存储器管理器产生式存储器工作存储器
2009-8-20 高级人工智能 -解释学习 史忠植 43
九宫问题
2 3 1
8 4
7 6 5
初始状态
1 2 3
8 4
7 6 5
目标状态
2009-8-20 高级人工智能 -解释学习 史忠植 44
求解过程
1,G1 solve-eight puzzle
2,P1 eight-puzzle sd
3,S1
4,O1 place-blank
5,=>G2 (resolve-no-change)
6,P2 eight-puzzle
7,S1
8,=>G3 (resolve-tie-operator)
9,P3 tie
10.S2 (left,up,down)
2 3 1
8 4
7 6 5
2009-8-20 高级人工智能 -解释学习 史忠植 45
11.O5 evaluate-object(O2(left))
12.=>G4 (resolve-no-change)
13.P2 eight-puzzle
14.S1
15.O2 left
16.S3
17.O2 left
18.S4
19.S4
20.O8 place-1
2 3 1
8 4
7 6 5
2009-8-20 高级人工智能 -解释学习 史忠植 46
8.8 可操作性标准如果给定：
1) 一个概念描述。
2) 一个执行系统，它利用概念描述改善执行情况。
3) 改善执行系统的各种要求，应明确各要求的类型和程度。
那么若满足下列二条件则该概念描述是可操作的：
1) 可用性：执行系统可以使用该概念描述
2) 效用型：使用概念描述时，系统的运行得到要求的改善
2009-8-20 高级人工智能 -解释学习 史忠植 47
PRODIGY的效用控制规则的可用性：
Utility = (AvrSavings ApplicFreq) - AvrMatchCost
其中：
AvrMatchCost = 匹配该规则的平均耗费
AvrSavings = 应用该规则时，平均节约的时间
ApplicFreq = 应用该规则的频度
2009-8-20 高级人工智能 -解释学习 史忠植 48
SOAR系统的可操作性
SOAR系统主要通过 Chunking来获取知识，因此有意忽略了可用性：
1,假设 Chunking是自动完成的；
2,SOAR系统的性能是由完成一项任务所需做的抉择次数来衡量的。
2009-8-20 高级人工智能 -解释学习 史忠植 49
MRS-EBG的可操作性将可操作性标准处理为可证明的。
可操作性是在解释过程中确定的，一旦某一分支由于没有可操作的定义而终结，就立即进行回溯，寻找该分支的另一能够产生一可操作的概念定义的证明。这样，一定能得到目标概念的可操作性描述。
2009-8-20 高级人工智能 -解释学习 史忠植 50
META-LEX的处理方法通过经验来评估可操作性：在系统中使用概念描述，然后看系统的行为是否达到了事先提出的系统目标。
2009-8-20 高级人工智能 -解释学习 史忠植 51
8.9 不完全领域知识下的解释学习领域知识的不完善性可能有以下三种情况：
不完整 (incomplete),缺少规则、知识
不正确 (incorrect),有些规则不合理
难处理的 (intractable),过于繁杂
2009-8-20 高级人工智能 -解释学习 史忠植 52
逆归结方法当解释过程由于缺乏某条规则而无法继续下去时，
学习过程即告失败。可以采用逆归结方法克服这个问题。
逆归结原理是根据归结子句和一条原子句，求另一条原子句。
C1
C
C2
2009-8-20 高级人工智能 -解释学习 史忠植 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(S0,S):-intransitive-verb(S0,S).
2009-8-20 高级人工智能 -解释学习 史忠植 54
依赖表如下：
谓词符号 Head Body 基本谓词
sentence 1 intransitive_verb,
name,
determiner,noun.
noun-phrase 2,3 1 name,determiner,
noun.
verb-phrase 4 1 intransitive_verb.
2009-8-20 高级人工智能 -解释学习 史忠植 55
解释树生成算法
1) 对目标概念开始做逆向推理，逐渐扩展解释树，该解释树是一棵与或树。
2) 遇到失败节点，调用逆归结算法。
3) 分析得到的完整解释树，进行泛化，得到目标概念的新描述。
2009-8-20 高级人工智能 -解释学习 史忠植 56
逆归结算法
1) 若当前失败结点 F是可操作的，回溯；若当前失败结点 F
不可操作，转到 (2)。
2) 与点 F的父结点 P对应的谓词符号为 Pred,利用依赖表，
检查 Pred是否有其他路径。没有，转到 (4)。
3) 对依赖表中 Pred的其它路径，检查其对应的可操作谓词是否被训练实例满足。
若存在满足训练例的路径，则选择此路径，完成解释树，结束算法。
依赖表中 Pred的其它路径对应的可操作谓词与训练例冲突或不为训练例具备，转到 (4)。
4) 先对结点 P除结点 F以外的子结点进行推理，所有子结点处理完之后，回到结点 F。
5) 用未使用的训练属性，采用逆归结的方法，得到结点 F与剩余属性间的一条伪规则，完成整个解释树的建立过程，
结束算法。
2009-8-20 高级人工智能 -解释学习 史忠植 57
基于深层知识方法实例领域知识库 深层知识库实例解释假设建立泛化执行单元假设生成失败失败成功成功成功
2009-8-20 高级人工智能 -解释学习 史忠植 58
基于深层知识方法
1) 由环境提供一实例。
2) 实例解释阶段：使用基于解释的学习方法对该实例进行解释。成功则进入 (5)，失败则进入 (3)。
3) 猜想生成阶段：系统试图确立自身相对于当前实例的知识断口，并建立一个有可能弥补该断口的猜想。
4) 猜想建立阶段：调用深层知识库，确立猜想的目标端与数据端在深层知识中是否具有共同的属性。若失败，
退回 (3)；成功则进入 (5)。
5) 泛化：将已确立的猜想加以泛化。
6) 将泛化的结果交执行单元使用。
第八章 解释学习史忠植中科院计算所
2009-8-20 高级人工智能 -解释学习 史忠植 2
内容
8.1 概述
8.2 解释学习模型
8.3 解释泛化学习方法
8.4 全局取代解释泛化方法
8.5 解释特化学习方法
8.6 解释泛化的逻辑程序
8.7 基于知识块的 SOAR系统
8.8 可操作性标准
8.9 不完全领域知识下的解释学习
2009-8-20 高级人工智能 -解释学习 史忠植 3
8.1 概述基于解释的学习：
一种从单个观察中抽象出通用规则的方法
目标是下次可以快速地解决类似的问题
记忆 —— 通过保存结果和避免从零开始解决问题来提高速度
更进一步 EBL从观察到规则
2009-8-20 高级人工智能 -解释学习 史忠植 4
解释学习解释学习 (Explanation-Based Learning,
简称 EBL)是一种分析学习方法，在领域知识指导下,通过对单个问题求解实例的分析,构造出求解过程的因果解释结构,并获取控制知识,以便用于指导以后求解类似问题。
2009-8-20 高级人工智能 -解释学习 史忠植 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)学习方法
2009-8-20 高级人工智能 -解释学习 史忠植 6
为什么要用 EBL
解释为什么一个想法是好的比提出一个想法容易得多
一旦理解了一件事，就可以泛化并重用于其它情况
从例子中抽象出通用规则
通过对一棵证明树的常量变量化,EBL可以同时创建两棵证明树
2009-8-20 高级人工智能 -解释学习 史忠植 7
基本的 EBL
给定一个例子，使用背景知识构建一棵证明树
同时，为可变化的目标构建一棵泛化证明树
构建一条新规则（叶子 => 根）
去掉所有与目标中变量真正无关的条件
2009-8-20 高级人工智能 -解释学习 史忠植 8
解释学习
(1)通过分析一个求解实例来产生解释结构 ;
(2)对该解释结构进行泛化,获取一般的控制规则。
2009-8-20 高级人工智能 -解释学习 史忠植 9
解释的含义
1) 对所产生的结论的推理过程作详细说明，
以增加系统的可接受性；
2) 对错误决策进行追踪，发现知识库中知识的缺陷和错误的概念；
3) 对初学的用户进行训练。
2009-8-20 高级人工智能 -解释学习 史忠植 10
解释的方法
1) 预制文本法。预先用自然语言写好，并插入程序中；
2) 执行追踪法。遍历目标树，通过总结与结论相关的目标，检索相关规则，以说明结论是如何得到的；
3) 策略解释法。明确表示控制知识，即用元知识概括地描述，与领域规则完全分开。
从策略的概括表示中产生解释，能为用户提供问题求解策略的解释。
2009-8-20 高级人工智能 -解释学习 史忠植 11
EBL的效率
选择一条通用规则
太多规则 -> 推理太慢
目标驱动 - 极大地提高了速度
尽可能的通用
可操作性 - 一个子目标是可操作的，意思是容易解决
可操作性和通用性之间的平衡
对 EBL学习效率的实验分析
2009-8-20 高级人工智能 -解释学习 史忠植 12
8.2 解释学习模型概念描述空间 概念空间 例子空间
D1
不可操作的可操作
D2
C1 I1
I2
I3
解释学习的空间描述
2009-8-20 高级人工智能 -解释学习 史忠植 13
可操作特性系 统 可 变 性 粒 度 确 定 性
GENESIS 动态 二进制 不保证
LEX2 动态 二进制 不保证
SOAR 动态 二进制 不保证
PRODIGY 静态 连续 不保证
MetaLEX 动态 连续 保证
2009-8-20 高级人工智能 -解释学习 史忠植 14
解释学习的模型
EXE 概念描述的转换 结果是否可操作D1 D2
KB PS
Y
N
2009-8-20 高级人工智能 -解释学习 史忠植 15
8.3 解释泛化学习方法解释泛化学习问题：
已知：
目标概念
训练例
领域理论
可操作性标准
欲求：
训练实例的泛化，使之满足以下条件
1) 是目标概念的充分概念描述
2) 满足可操作性标准
2009-8-20 高级人工智能 -解释学习 史忠植 16
EBL方法
1,解释
利用领域理论知识解释为什么训练例满足目标概念的定义
2,泛化
确定解释成立的最通用的条件
2009-8-20 高级人工智能 -解释学习 史忠植 17
例子
目标概念：一对物体 <x,y>,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)
…
2009-8-20 高级人工智能 -解释学习 史忠植 18
领域知识：
VOLUME(p1,v1)∧DENSITY(p1,d1)→WEIGHT(p1,v1*d1)
WEIGHT(p1,w1)∧WEIGHT(p2,w2)∧LESS(w1,w2)→LIG
HTER(p1,p2)
ISA(p1,ENDTABLE)→WEIGHT(p1,5)(default)
LESS(.1,5)
…
可操作标准：概念定义必须要用描述实例中的谓词，或者选自领域知识易于评测的谓词。
确定：
训练实例的泛化是对目标概念给以充分定义，并且满足可操作性标准。
2009-8-20 高级人工智能 -解释学习 史忠植 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)
2009-8-20 高级人工智能 -解释学习 史忠植 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}
2009-8-20 高级人工智能 -解释学习 史忠植 21
解释与泛化交替进行
1,问题的逻辑描述
逻辑的表示方法使 EBG的语义更为清楚，
为学习提供了方便的语言环境
2,产生解释结构
从目标开始反向推理，分解目标。应用规则时，同时将规则应用到变量化的目标概念上，这样就同时生成了解释结构和泛化的解释结构
3,生成控制规则
将泛化的解释结构的所有叶结点的合取作为前件，以定点的目标概念为后件，
略去解释结构的中间部件，生成泛化的产生式规则。
2009-8-20 高级人工智能 -解释学习 史忠植 22
8.4 全局取代解释泛化方法
1986年 DeJong和 Mooney提出全局取代解释泛化方法。在 EBG方法中，通过实例解释结构的目标概念回归，忽略析取实现泛化。
2009-8-20 高级人工智能 -解释学习 史忠植 23
STRIPS的例子
初始世界模型：
),( 1RR O B O TI N R O O M
),( 21 RB O XI N R O O M
),,( 211 RRDC O N N E C T S
)( 1B OXB OX
..
)],,(),,()[,,( yzxC O N N E C T SzyxC O N N E C T Szyx
)],()()[( 1RxI N R O O MxB O Xx
),,( 321 RRDC O N N E C T S
目标公式：
2009-8-20 高级人工智能 -解释学习 史忠植 24
STRIPS采用的操作符如下：
),,( 21 rrdG O T H R U
),,,(),(:Pr 211 rrdC O N N E C T SrR O B O TI N R O O Meo n d i t i o n?
),,(,1rR O B O TI N R O O Ml i s tD el et e
),(,2rR O B O TI N R O O Ml i s tA d d
),,,( 21 rrdbP U S H T H R U
),,(),(:Pr 211 rrdC O N N E C T SrR O B O TI N R O O Meo n d i t i o n?
),,(,1rR O B O TI N R O O Ml i s tD el et e
),(,2rR O B O TI N R O O Ml i s tA d d
),,( 1rbI N R O O M
),( 2rbI N R O O M
),,( 1rbI N R O O M?
2009-8-20 高级人工智能 -解释学习 史忠植 25
三角表
),( 1RR O B O TI N R O O M
),,( 211 RRDC O N N E C T S ),,( 21 rrdG O T H R U
),( 2RR O B O TI N R O O M),( 21 RB O XI N R O O M
),,( 211 RRDC O N N E C T S
),,( zyxC ON N E C T S
),,( yzxC ON N E C T S?
),,,( 21 rrdbP U S H T H R U
),( 1RR O B O TI N R O O M
),( 11 RB OXI N R OO M
2009-8-20 高级人工智能 -解释学习 史忠植 26
泛化三角表
),( 2pR O B O TI N R O O M
),,( 523 pppC O N N E C T S ),,( 523 pppG O T H R U
),( 5pR O B O TI N R O O M),( 56 ppI N R O O M
),,( 598 pppC O N N E C T S
),,( zyxC ON N E C T S
),,( yzxC ON N E C T S?
),,,( 9586 ppppP U S H T H R U
),( 9pR O B O TI N R O O M
),( 96 ppI N R O O M
2009-8-20 高级人工智能 -解释学习 史忠植 27
EGGS问题描述给定：
领域理论：
领域中对象的种类和特性的定义
一组关于对象特性和相互关系的推理规则
一组问题求解的操作和已知的泛化图式
目标：目标状态的一般规约。
初始世界状态：关于世界及其特性的规约。
观察到的操作 /状态序列。
确定
达到目标状态的一个新模式
2009-8-20 高级人工智能 -解释学习 史忠植 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)
1e 2e
1e 2e
1e?2e
1e?2e
1e?2e
2009-8-20 高级人工智能 -解释学习 史忠植 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,
ip jp
'ip? ip
'jp? jp
'ip 'jp
kp
kp?kp
2009-8-20 高级人工智能 -解释学习 史忠植 30
8.5 解释特化学习方法从多种目标概念学习，其解释过程是对每个目标概念进行详细描述。解释过程结束后，把得到在有关目标概念的描述转换成一条相应的控制规则。可以用这些规则来选择合适的节点、
子目标、算子及约束。较好地克服了 EBG方法中过分一般化的缺点。
2009-8-20 高级人工智能 -解释学习 史忠植 31
PRODIGY体系结构问 题
PS跟踪求 解控制知识规 划 库领域知识抽象层次
EBL
派生抽取抽象生成器实 验外部处理用户问题问题求解器派生重演 多级
2009-8-20 高级人工智能 -解释学习 史忠植 32
PRODIGY的学习
1,解释过程
如果概念是原语，则不改变返回。
访问识别器，取出规则；获得子概念，特化子概念；重命名变量；置换并简化。
返回。
2,学习控制规则
由成功概念学到 preference rules；
由失败概念学到 rejection rules；
由其它选择都失败学到 selection rules；
3,知识表示
领域层公理
构筑层公理
2009-8-20 高级人工智能 -解释学习 史忠植 33
8.6 解释泛化的逻辑程序工作原理归结原理：设两个短句 C1,C2无公共变量，
L1和 L2分别是 C1和 C2的两个文字，若 L1和
L2存在一个最一般的合一置换，那么子句
（ C1-L1) (C2-L2)就是两个子句 C1和 C2的归结式。
2009-8-20 高级人工智能 -解释学习 史忠植 34
Turbo Prolog的合一算法
1) 自由变量可以和任意项合一。合一后该自由变量约束为与之合一的项。
2) 常量可与自身或自由变量合一。
3) 若两个复合项的函子相同且函子所带参量个数一样，则这两个复合项可以合一的条件是：所有子项能对应合一。约束变量要用合一后的约束值替换。
2009-8-20 高级人工智能 -解释学习 史忠植 35
解释泛化的逻辑程序设计
1,解释
合一算法作为基础，用 Prolog谓词来完成
把领域理论用内部数据库的形式存储。
2,泛化
包括常量用变量代替、新项合成等工作。
3,解释和泛化交叉进行
2009-8-20 高级人工智能 -解释学习 史忠植 36
Prolog简单的元解释器
prolog(Leaf),-clause(Leaf,true).
prolog((Goal,Goal2)),-
prolog(Goal1),
prolog(Goal2).
Prolog(Goal),-
clause(Goal,Clause),
prolog(Clause).
2009-8-20 高级人工智能 -解释学习 史忠植 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).
2009-8-20 高级人工智能 -解释学习 史忠植 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).
2009-8-20 高级人工智能 -解释学习 史忠植 39
suicide(john)的解释结构
suicide(john)
kill(john,john)
weapon(gun1)hate(john,john) possess(john,gun1)
depressed(john) buy(john,gun1) gun(gun1)
2009-8-20 高级人工智能 -解释学习 史忠植 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}
2009-8-20 高级人工智能 -解释学习 史忠植 41
8.7 基于知识块的 SOAR系统记忆块：用一种符号来标记另一些符号的存储结构模型。
SOAR的学习机制：由外部专家的指导来学习一般的搜索控制知识。外部指导可以是直接劝告，也可以是给出一个直观的简单问题。系统把外部指导给定的高水平信息转化为内部表示，
并学习搜索记忆块。
2009-8-20 高级人工智能 -解释学习 史忠植 42
SOAR的体系结构记忆块机制对 象优 先语境站决策过程工作存储器管理器产生式存储器工作存储器
2009-8-20 高级人工智能 -解释学习 史忠植 43
九宫问题
2 3 1
8 4
7 6 5
初始状态
1 2 3
8 4
7 6 5
目标状态
2009-8-20 高级人工智能 -解释学习 史忠植 44
求解过程
1,G1 solve-eight puzzle
2,P1 eight-puzzle sd
3,S1
4,O1 place-blank
5,=>G2 (resolve-no-change)
6,P2 eight-puzzle
7,S1
8,=>G3 (resolve-tie-operator)
9,P3 tie
10.S2 (left,up,down)
2 3 1
8 4
7 6 5
2009-8-20 高级人工智能 -解释学习 史忠植 45
11.O5 evaluate-object(O2(left))
12.=>G4 (resolve-no-change)
13.P2 eight-puzzle
14.S1
15.O2 left
16.S3
17.O2 left
18.S4
19.S4
20.O8 place-1
2 3 1
8 4
7 6 5
2009-8-20 高级人工智能 -解释学习 史忠植 46
8.8 可操作性标准如果给定：
1) 一个概念描述。
2) 一个执行系统，它利用概念描述改善执行情况。
3) 改善执行系统的各种要求，应明确各要求的类型和程度。
那么若满足下列二条件则该概念描述是可操作的：
1) 可用性：执行系统可以使用该概念描述
2) 效用型：使用概念描述时，系统的运行得到要求的改善
2009-8-20 高级人工智能 -解释学习 史忠植 47
PRODIGY的效用控制规则的可用性：
Utility = (AvrSavings ApplicFreq) - AvrMatchCost
其中：
AvrMatchCost = 匹配该规则的平均耗费
AvrSavings = 应用该规则时，平均节约的时间
ApplicFreq = 应用该规则的频度
2009-8-20 高级人工智能 -解释学习 史忠植 48
SOAR系统的可操作性
SOAR系统主要通过 Chunking来获取知识，因此有意忽略了可用性：
1,假设 Chunking是自动完成的；
2,SOAR系统的性能是由完成一项任务所需做的抉择次数来衡量的。
2009-8-20 高级人工智能 -解释学习 史忠植 49
MRS-EBG的可操作性将可操作性标准处理为可证明的。
可操作性是在解释过程中确定的，一旦某一分支由于没有可操作的定义而终结，就立即进行回溯，寻找该分支的另一能够产生一可操作的概念定义的证明。这样，一定能得到目标概念的可操作性描述。
2009-8-20 高级人工智能 -解释学习 史忠植 50
META-LEX的处理方法通过经验来评估可操作性：在系统中使用概念描述，然后看系统的行为是否达到了事先提出的系统目标。
2009-8-20 高级人工智能 -解释学习 史忠植 51
8.9 不完全领域知识下的解释学习领域知识的不完善性可能有以下三种情况：
不完整 (incomplete),缺少规则、知识
不正确 (incorrect),有些规则不合理
难处理的 (intractable),过于繁杂
2009-8-20 高级人工智能 -解释学习 史忠植 52
逆归结方法当解释过程由于缺乏某条规则而无法继续下去时，
学习过程即告失败。可以采用逆归结方法克服这个问题。
逆归结原理是根据归结子句和一条原子句，求另一条原子句。
C1
C
C2
2009-8-20 高级人工智能 -解释学习 史忠植 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(S0,S):-intransitive-verb(S0,S).
2009-8-20 高级人工智能 -解释学习 史忠植 54
依赖表如下：
谓词符号 Head Body 基本谓词
sentence 1 intransitive_verb,
name,
determiner,noun.
noun-phrase 2,3 1 name,determiner,
noun.
verb-phrase 4 1 intransitive_verb.
2009-8-20 高级人工智能 -解释学习 史忠植 55
解释树生成算法
1) 对目标概念开始做逆向推理，逐渐扩展解释树，该解释树是一棵与或树。
2) 遇到失败节点，调用逆归结算法。
3) 分析得到的完整解释树，进行泛化，得到目标概念的新描述。
2009-8-20 高级人工智能 -解释学习 史忠植 56
逆归结算法
1) 若当前失败结点 F是可操作的，回溯；若当前失败结点 F
不可操作，转到 (2)。
2) 与点 F的父结点 P对应的谓词符号为 Pred,利用依赖表，
检查 Pred是否有其他路径。没有，转到 (4)。
3) 对依赖表中 Pred的其它路径，检查其对应的可操作谓词是否被训练实例满足。
若存在满足训练例的路径，则选择此路径，完成解释树，结束算法。
依赖表中 Pred的其它路径对应的可操作谓词与训练例冲突或不为训练例具备，转到 (4)。
4) 先对结点 P除结点 F以外的子结点进行推理，所有子结点处理完之后，回到结点 F。
5) 用未使用的训练属性，采用逆归结的方法，得到结点 F与剩余属性间的一条伪规则，完成整个解释树的建立过程，
结束算法。
2009-8-20 高级人工智能 -解释学习 史忠植 57
基于深层知识方法实例领域知识库 深层知识库实例解释假设建立泛化执行单元假设生成失败失败成功成功成功
2009-8-20 高级人工智能 -解释学习 史忠植 58
基于深层知识方法
1) 由环境提供一实例。
2) 实例解释阶段：使用基于解释的学习方法对该实例进行解释。成功则进入 (5)，失败则进入 (3)。
3) 猜想生成阶段：系统试图确立自身相对于当前实例的知识断口，并建立一个有可能弥补该断口的猜想。
4) 猜想建立阶段：调用深层知识库，确立猜想的目标端与数据端在深层知识中是否具有共同的属性。若失败，
退回 (3)；成功则进入 (5)。
5) 泛化：将已确立的猜想加以泛化。
6) 将泛化的结果交执行单元使用。
