2009-8-20 高级人工智能 ---史忠植 1
第七章 类比学习史忠植中科院计算所
2009-8-20 高级人工智能 ---史忠植 2
内容提要
7.1 什么是类比学习
7.2 类比的形式定义
7.3 基于抽象的有用类比推理
7.4 转换类比
7.5 派生类比
7.6 因果关系型类比学习
7.7 联想类比学习
7.8 约束满足类比
2009-8-20 高级人工智能 ---史忠植 3
7.1 什么是类比学习
类比是人类应用过去的经验来求解新问题的一种思维过程。
类比学习是把两个或两类事物或情形进行比较，找出它们在某一抽象层上的相似关系，并以这种关系为依据，把某一事物或情形的有关知识加以适当整理
（或变换）对应到另一事物或情况，从而获得求解另一事物或情形的知识。
2009-8-20 高级人工智能 ---史忠植 4
类比的重要性：
类比现象普遍存在。
类比在人的思维中扮演着极为重要的角色。
比喻的使用。
在计算机上实现类比问题求解系统可以使计算机也具有创造性思维。
2009-8-20 高级人工智能 ---史忠植 5
类比学习与基于范例的学习
相同之处：
都要依靠记忆的情景知识来指导复杂的问题求解。
不同之处：
类比学习强调对过去情况的修改、改写和验证过程。
CBL注重范例记忆的组织、层次索引和检索。
2009-8-20 高级人工智能 ---史忠植 6
计算机上实现类比存在的限制
Cook(1991)归纳了以下两点限制：
资源耗费大，很少应用于大规模问题，不适于严格标准的商业应用。
缺少灵活性，没有匹配的原范例时无法工作。
2009-8-20 高级人工智能 ---史忠植 7
类比学习模型中的主要问题
知识表示和检索：
快速检索选择源范例。
有利于整个类比过程的实现。
易于修改。
灵活性，不应孤立存在：
把理论和类比策略结合起来。
多个类比的结合。
有效性验证。
2009-8-20 高级人工智能 ---史忠植 8
类比学习的例子
2009-8-20 高级人工智能 ---史忠植 9
类比映射
a
b
e
c
d
f 已知域
a’
b’
e’
c’
d’
f’ 未知域
2009-8-20 高级人工智能 ---史忠植 10
类比推理
根据已知域的情况，用类比来回答关于另一未知域的问题，主要是一个解决问题的过程。
类比推理的基础：
事物
关系
2009-8-20 高级人工智能 ---史忠植 11
类比学习的过程
可以描述为四个主要步骤：
1) 联想搜索匹配
2) 检验相似程度
3) 修正变换求解
4) 更新知识库
2009-8-20 高级人工智能 ---史忠植 12
类比求解过程要明确的问题
1,问题特征怎样抽取
2,相似性测度及计算方法如何确定
3,如何搜索相似的问题
4,怎样找出对应关系，如何匹配
5,老问题的解如何变换地到新问题的解
6,如何更新知识库
2009-8-20 高级人工智能 ---史忠植 13
7.2 类比的形式定义
A
B
A’
B’
α
α’
β β’
类比问题求解的一般模式
2009-8-20 高级人工智能 ---史忠植 14
2009-8-20 高级人工智能 ---史忠植 15
7.3 基于抽象的有用类比推理
NLAG类比推理算法：
1) 寻找核心
2) 例示源概念
3) 例示目标
4) 核准
5) 认可
2009-8-20 高级人工智能 ---史忠植 16
7.4 转换类比
2009-8-20 高级人工智能 ---史忠植 17
7.4.1 手段 -目的分析的问题求解模型
问题空间：
1) 一组可能的问题组合状态集。
2) 一个初始状态。
3) 一个或多个目标状态。
4) 一组变换规则集
5) 差别函数
6) 对可用规则编序的索引函数
7) 一组全局路径限制
8) 差别表
2009-8-20 高级人工智能 ---史忠植 18
S-MEA算法：
1) 比较当前状态和目标状态，得出差别
2) 选择合适的规则，以减少两个状态间的差别
3) 尽可能应用转换规则，直至完成状态转换。
否则保存当前状态，并将 MEA算法递归地应用于其它子问题，直到该子问题确认不能满足该规划的前提条件为止。
4) 当子问题求解后，恢复被保存的当前状态，
再继续求解原来的问题
2009-8-20 高级人工智能 ---史忠植 19
直接抽象方法的主要缺点：
1) 难以处理存储和检索所有可能解的组合问题，
搜索宏操作的开销可能变得比直接用 MEA方法还要大。
2) 忽略路径限制条件，造成新问题的新条件中使当前宏操作失效，使求解过程浪费。
3) 没有考虑如何修改解序列。
2009-8-20 高级人工智能 ---史忠植 20
7.4.2 类比求解问题的计算模型
EMEA的 T-空间包括,
1) 转换空间中每个状态是初始问题的潜在解，包括初始状态、最终状态、操作符序列以及路径限制。
2) 初始状态,O-空间中检索到的相似问题的解序列。
3) 目标状态：求解新问题的解的规范说明。
4) 操作符将一个完整的解序列映射到另一个潜在的解序列。
5) 差别函数：新问题情况下检索解的初始状态、中止状态、路径的约束和应用度之间的差别测度的综合。
6) 差别表：用来检索 T-空间的操作。
7) 没有路径约束，可用更为复杂的差别函数补偿。
8) 可用启发式函数作为规则排序。
2009-8-20 高级人工智能 ---史忠植 21
7.4.3 问题求解状态变换初始状态中间状态 1
OP1
中间状态 2
OP2
中间状态 n-1
OPn-1
初始状态问题求解的状态转换过程
2009-8-20 高级人工智能 ---史忠植 22
类比学习解决新问题的过程：
1) 回忆过程
2) 解序列转换过程
3) 抽象求解方法过程
2009-8-20 高级人工智能 ---史忠植 23
初始状态结束状态路径 Con1
路径 Con2
PC1
PC2
PC1
PC3
PC1
PC2 T-OP1
T-OP2
对新问题的解原空间 T-空间作为搜索的类比问题求解
2009-8-20 高级人工智能 ---史忠植 24
常用 T-操作符：
1) 通用插入
2) 通用删除
3) 子序列拼接
4) 子目标保持替换
5) 终结段连结
6) 初始段连结
7) 序列合并
8) 操作符记录
9) 用参数替换
10)解序列截断
11)序列倒置
2009-8-20 高级人工智能 ---史忠植 25
差别表：
入口形式：
“为简少 <差别 >，应采用 <T-操作符集 >中的一个操作”
2009-8-20 高级人工智能 ---史忠植 26
T-空间的差别测度 Dr（ 差异函数）
Dr的值是四维向量：
新旧问题初态的差别
新旧问题终态的差别
新旧问题路径限制的差别
新旧问题方法可应用度的差别。
2009-8-20 高级人工智能 ---史忠植 27
7.4.4 转换类比学习系统输 入比较器知识库操作表解法库操作模块 解法栈检验模块 输 出转换类比学习系统框图
2009-8-20 高级人工智能 ---史忠植 28
知识库 —— 操作表差 别
d1
d2
…
差 别
OP11,OP12,…
…
OP21,OP22,…
2009-8-20 高级人工智能 ---史忠植 29
知识库 —— 解法表达形式问题类型
S0,S1,S2,…,Sn
初始状态 S0
目标状态 Sn
OP1,OP2,…,OPi,…,OPn
…
2009-8-20 高级人工智能 ---史忠植 30
例：已知“偶数 × 偶数 =偶数”，用类比的方法求证“奇数 × 奇数 =奇数”。
证明“两个偶数之积仍为偶数”的过程
偶数可表示为 2× A的形式 ；
两偶数之积为 (2× m)× (2× n)；
(2× m)× (2× n)=4× m× n；
将 4× m× n表示为 2× A的形式，即令 A=2× m× n。
2009-8-20 高级人工智能 ---史忠植 31
证明“两个奇数之积仍为奇数”的过程
（从关于偶数的证明过程中得到启示）
奇数可表示为 2× A+1的形式 ；
两偶数之积为 (2× m+1)× (2× n+1)；
(2× m+1)× (2× n+1)=4× m× n+2× m+2× n+1；
将结果表示为 2× A+1的形式，即令
A=2× m× n+m+n。
2009-8-20 高级人工智能 ---史忠植 32
解法库中的一个解序列求证类
(2m)× (2n)=2A
4mn=2A
2mn=A
A为整数
(2m)× (2n)=2A
A为整数两项相乘除公因子 2
整数经 +,-、×运算仍为整数
2009-8-20 高级人工智能 ---史忠植 33
操作表差 别参数不同
…
…
差 别参数替换
…
…
前提不满足 子序列拼接
2009-8-20 高级人工智能 ---史忠植 34
输入的问题求证类
(2m+1)× (2n+1)=2A+1
A为整数
…
2009-8-20 高级人工智能 ---史忠植 35
类比求解过程的操作序列求证类
(2m+1)× (2n+1)=2A+1
A为整数
4mn+2m+2n+1=2A+1
4mn+2m+2n=2A
2mn+m+n=A
(2m+1)× (2n+1)=2A+1
两项相乘两边减 1
两边除公因子 2
整数经 +,-、×运算仍为整数
2009-8-20 高级人工智能 ---史忠植 36
7.4.5 类比学习的泛化规则
改善类比学习系统性能的一些方法：
1) 获取解的一般过程。
2) 插曲记忆组织与重构
3) T操作符的改善与获取
2009-8-20 高级人工智能 ---史忠植 37
获取解的一般过程
1) 类比器产生一个新问题后，若经过测试，该解满足新问题的要求，则该解加入正例集 ；
2) 若该解不满足新问题，则记录失败原因，并将该解加入反例集；
3) 归纳正例集和反例集，产生一条规则，能指导所有正例集中的成功解，而不满足反例集中任一不成功解；
4) 通过对反例容易与正例混淆的分析可以提出范化规则结构的正例；
5) 当类比器无法求解时获得的信息可作为加强或产生相似性测度的正例或反例，作为反例去改进相似性测度。
2009-8-20 高级人工智能 ---史忠植 38
插曲记忆组织与重构
目的是为了改进相似性 /差异测度的精确性和对经验 /解的记忆的构造和检索。
采用的方法是以失败驱动的方式进行差异测度调准
2009-8-20 高级人工智能 ---史忠植 39
T-操作符的改善与获取改善：操作符在差别表的对应入口的限制条件。
1) 在 T-空间中比较失败路径解的 T-操作符和成功路径解的 T-操作符。
2) 如果该 T-操作符在差别表中有多个入口，一些入口仅对应于该操作的失败例子，则删除这些入口。
3) 若某个入口对应的失败比成功多得多，说明要减小的差别描述可能太一般，必须分解为更特殊差别的不相交子集。
2009-8-20 高级人工智能 ---史忠植 40
获取：
1) 对问题求解器求得的解和 T-空间中各次尝试转换进行比较。
2) 找出某个最接近实际解的中间状态（ Dr值最小）。
3) 假设某个新的 T-操作符是从这个状态到实际解的转换，并使其可用。
4) 若加入新操作符后，有许多类比求解不成功，导致产生了更多的新的 T-操作符，则应用观察学习技术，
若例子形成很相似的例子集，则可以根据例子集的特征来重新构造 T-操作符。
5) 将新的 T-操作符加入可用 T-操作符集。
6) 在差别表中编序新 T-操作符的入口。
2009-8-20 高级人工智能 ---史忠植 41
7.5 派生类比
2009-8-20 高级人工智能 ---史忠植 42
7.6 因果关系型类比学习
7.6.1类比匹配技术与相似性度量概述
匹配的形式：
1) 等价匹配
2) 选择匹配
3) 规则匹配
4) 启发式匹配
2009-8-20 高级人工智能 ---史忠植 43
相似度测量：
|)()(| 2211 kkjj qV a l u eEqV a l u eE
属性相似度的测量：
对象相似度的测量：
||),(
21
1 2
1 12
1 1
1 11
21
m
j j
m
j j
m
i i
m
i i
im
P
P
P
P
EES
2009-8-20 高级人工智能 ---史忠植 44
7.6.2 知识表示
一个好的表示方法应满足如下条件：
1) 能够使重要的事实清楚的表达出来
2) 能消除一些无关的细节
3) 其表达应是清晰的，决不能含糊其词，模棱两可，更应避免多义性
4) 应能根据自然输入对知识进行计算处理
2009-8-20 高级人工智能 ---史忠植 45
7.6.3 类比匹配
匹配器应具有如下特征：
1) 具有判定对应部分是否相似的函数。
2) 能启发式地搜索所有可能的匹配。
2009-8-20 高级人工智能 ---史忠植 46
寻找两个状态之间的匹配关系时应遵循以下原则：
1) 性质和关系分别与性质和关系相配对
2) 采用特定领域的知识进行启发式选择
3) 考虑适当的分类信息
4) 从重要关系或性质到非重要关系或性质的配对优先原则
5) 对两个具有较多部分的状态配对时可采用分组的方法
6) 匹配进行之前可采用抽象的方法，使一些具体的事件具有一定的普遍性。
7) 具有一定的学习能力。
2009-8-20 高级人工智能 ---史忠植 47
7.6.4 抽取问题的特征特征抽取一般分析方法是，将例子中的概念、特征、行为或其它关系表示成问题空间中一点，
这种表示必须突出问题的主要特性。即概念获取和性质描述过程，使其由外部变为内部形式，
并努力保证该信息的完整。分为静态方法和动态方法。
2009-8-20 高级人工智能 ---史忠植 48
7.6.5 相似度的计算方法特征集 A和 B的相似度 S由下式决定：
)()()(),( ABfBAfBAfBAS
当 时，可以简化为：1
)()()()(),( ABfBAfBfAfBAS
2009-8-20 高级人工智能 ---史忠植 49
7.6.6 最佳对应关系匹配
对象间相似性判别方法采用启发式。
通过动态对特征的抽取，利用重要性制导匹配来决定对象间的相似性。主要步骤是：
1) 以对象的各部分的分类、特性、动作及其它关系线索，根据其重要性，来建立对象间的关系对应，形成一个匹配。
2) 在各种匹配中寻找一个最佳匹配。
3) 对事实进行适当的抽象或细化。
2009-8-20 高级人工智能 ---史忠植 50
7.7 联想类比学习
联想类比学习是把已知领域（源系统）的知识联想到未知领域（目标系统）的类比方法，是一种综合的类比推理方法。
2009-8-20 高级人工智能 ---史忠植 51
已知源系统,目标系统,
联想条件 。
1) 输入,并置 1←i,1←j ；
2) 是否满足，即,若满足转 (5)；
3) 置 i+1←i,若 i≤n 转 (2)；
4) 置 j+1←j,1←I,若 j≤m 转 (2)；
5) 进行类比映射：
niOS ii,.,,,2,1,,,T
mjR j,...,2,1?，
pkTtROS kjii,...,2,1,,,,
jR,,TROS jii
联想类比算法
2009-8-20 高级人工智能 ---史忠植 52
5) 进行类比映射：
(5.1)概念映射
(5.2)关系映射
(5.3)方法映射
6) 重新设置联想条件,转 (2)；
7) 类比成功，进行检验，结束
jR
2009-8-20 高级人工智能 ---史忠植 53
联想类比条件：
同构相似联想
同态相似联想
接近联想
对比联想
模糊联想
2009-8-20 高级人工智能 ---史忠植 54
7.8 约束满足类比
7.8.1 三类约束
结构一致性
语义相似
语用相似
2009-8-20 高级人工智能 ---史忠植 55
7.8.2 约束满足理论
Holyoak和 Thagard（ 1989） 提出了约束满足理论，综述如下：
1) 同构的结构约束适用于两个类比物元素之间关系对应的最大一致性。
2) 语义相似性支持具有相似含义元素之间可能对应的程度。
3) 语用中心适用于元素之间的映射，为了达到目的，相信所使用地类比是重要的。
2009-8-20 高级人工智能 ---史忠植 56
7.8.3 ACMS算法
1) 对于 T中每个命题,使用,对于 S中每个命题 使用,
if 和 是它们各自结构的部分，
并具有相同数目的参数，
then (1)建立,
且 ；
(2)建立连结
(3)建立连结
(4)建立连结
(5)每对 之间建立连结。
ipropT ))a r g...a r g( a r g( 21 iniii TTTp r e d T
ipropS ))a r g...a r g( a r g( 21 iniii SSSp r e d S
ipropT ipropS
iiii p r e d Sp r e d Tp r o p Sp r o p T,
ikik ST a rga rg?
iiii p r e d Sp r e d Tandp r o p Sp r o p T
ikikii STp r o p Sp r o p T a r ga r g 且
ikikii STp r e d Sp r e d T a r ga r g 且
ikik ST a rga rg?
2009-8-20 高级人工智能 ---史忠植 57
2) 在不相容映射的两个单元之间建立禁止连结，通过却省禁止参数 i置以负权值。
3) 对于每个谓词映射单元,基于两个谓词之间的语义相似性建立语义单元连结。如果不相似，则权值最小为 。如果谓词相同，则权值为最大值 。
4) 对于列为 IMPORTMANT的每个元素，包括谓词、对象、命题，
从语用单元到每个有关的映射元素建立连结。 IMPORTMANT
映射的语用中心的权值为参数 。
5) 对于列入 PRESUMED的每个单元，为 PRESUMED映射的语用中心，从语用单元建立连接，权值等于参数 。
ii p re d Sp re d T?
minS maxS
1p
2p
第七章 类比学习史忠植中科院计算所
2009-8-20 高级人工智能 ---史忠植 2
内容提要
7.1 什么是类比学习
7.2 类比的形式定义
7.3 基于抽象的有用类比推理
7.4 转换类比
7.5 派生类比
7.6 因果关系型类比学习
7.7 联想类比学习
7.8 约束满足类比
2009-8-20 高级人工智能 ---史忠植 3
7.1 什么是类比学习
类比是人类应用过去的经验来求解新问题的一种思维过程。
类比学习是把两个或两类事物或情形进行比较，找出它们在某一抽象层上的相似关系，并以这种关系为依据，把某一事物或情形的有关知识加以适当整理
（或变换）对应到另一事物或情况，从而获得求解另一事物或情形的知识。
2009-8-20 高级人工智能 ---史忠植 4
类比的重要性：
类比现象普遍存在。
类比在人的思维中扮演着极为重要的角色。
比喻的使用。
在计算机上实现类比问题求解系统可以使计算机也具有创造性思维。
2009-8-20 高级人工智能 ---史忠植 5
类比学习与基于范例的学习
相同之处：
都要依靠记忆的情景知识来指导复杂的问题求解。
不同之处：
类比学习强调对过去情况的修改、改写和验证过程。
CBL注重范例记忆的组织、层次索引和检索。
2009-8-20 高级人工智能 ---史忠植 6
计算机上实现类比存在的限制
Cook(1991)归纳了以下两点限制：
资源耗费大，很少应用于大规模问题，不适于严格标准的商业应用。
缺少灵活性，没有匹配的原范例时无法工作。
2009-8-20 高级人工智能 ---史忠植 7
类比学习模型中的主要问题
知识表示和检索：
快速检索选择源范例。
有利于整个类比过程的实现。
易于修改。
灵活性，不应孤立存在：
把理论和类比策略结合起来。
多个类比的结合。
有效性验证。
2009-8-20 高级人工智能 ---史忠植 8
类比学习的例子
2009-8-20 高级人工智能 ---史忠植 9
类比映射
a
b
e
c
d
f 已知域
a’
b’
e’
c’
d’
f’ 未知域
2009-8-20 高级人工智能 ---史忠植 10
类比推理
根据已知域的情况，用类比来回答关于另一未知域的问题，主要是一个解决问题的过程。
类比推理的基础：
事物
关系
2009-8-20 高级人工智能 ---史忠植 11
类比学习的过程
可以描述为四个主要步骤：
1) 联想搜索匹配
2) 检验相似程度
3) 修正变换求解
4) 更新知识库
2009-8-20 高级人工智能 ---史忠植 12
类比求解过程要明确的问题
1,问题特征怎样抽取
2,相似性测度及计算方法如何确定
3,如何搜索相似的问题
4,怎样找出对应关系，如何匹配
5,老问题的解如何变换地到新问题的解
6,如何更新知识库
2009-8-20 高级人工智能 ---史忠植 13
7.2 类比的形式定义
A
B
A’
B’
α
α’
β β’
类比问题求解的一般模式
2009-8-20 高级人工智能 ---史忠植 14
2009-8-20 高级人工智能 ---史忠植 15
7.3 基于抽象的有用类比推理
NLAG类比推理算法：
1) 寻找核心
2) 例示源概念
3) 例示目标
4) 核准
5) 认可
2009-8-20 高级人工智能 ---史忠植 16
7.4 转换类比
2009-8-20 高级人工智能 ---史忠植 17
7.4.1 手段 -目的分析的问题求解模型
问题空间：
1) 一组可能的问题组合状态集。
2) 一个初始状态。
3) 一个或多个目标状态。
4) 一组变换规则集
5) 差别函数
6) 对可用规则编序的索引函数
7) 一组全局路径限制
8) 差别表
2009-8-20 高级人工智能 ---史忠植 18
S-MEA算法：
1) 比较当前状态和目标状态，得出差别
2) 选择合适的规则，以减少两个状态间的差别
3) 尽可能应用转换规则，直至完成状态转换。
否则保存当前状态，并将 MEA算法递归地应用于其它子问题，直到该子问题确认不能满足该规划的前提条件为止。
4) 当子问题求解后，恢复被保存的当前状态，
再继续求解原来的问题
2009-8-20 高级人工智能 ---史忠植 19
直接抽象方法的主要缺点：
1) 难以处理存储和检索所有可能解的组合问题，
搜索宏操作的开销可能变得比直接用 MEA方法还要大。
2) 忽略路径限制条件，造成新问题的新条件中使当前宏操作失效，使求解过程浪费。
3) 没有考虑如何修改解序列。
2009-8-20 高级人工智能 ---史忠植 20
7.4.2 类比求解问题的计算模型
EMEA的 T-空间包括,
1) 转换空间中每个状态是初始问题的潜在解，包括初始状态、最终状态、操作符序列以及路径限制。
2) 初始状态,O-空间中检索到的相似问题的解序列。
3) 目标状态：求解新问题的解的规范说明。
4) 操作符将一个完整的解序列映射到另一个潜在的解序列。
5) 差别函数：新问题情况下检索解的初始状态、中止状态、路径的约束和应用度之间的差别测度的综合。
6) 差别表：用来检索 T-空间的操作。
7) 没有路径约束，可用更为复杂的差别函数补偿。
8) 可用启发式函数作为规则排序。
2009-8-20 高级人工智能 ---史忠植 21
7.4.3 问题求解状态变换初始状态中间状态 1
OP1
中间状态 2
OP2
中间状态 n-1
OPn-1
初始状态问题求解的状态转换过程
2009-8-20 高级人工智能 ---史忠植 22
类比学习解决新问题的过程：
1) 回忆过程
2) 解序列转换过程
3) 抽象求解方法过程
2009-8-20 高级人工智能 ---史忠植 23
初始状态结束状态路径 Con1
路径 Con2
PC1
PC2
PC1
PC3
PC1
PC2 T-OP1
T-OP2
对新问题的解原空间 T-空间作为搜索的类比问题求解
2009-8-20 高级人工智能 ---史忠植 24
常用 T-操作符：
1) 通用插入
2) 通用删除
3) 子序列拼接
4) 子目标保持替换
5) 终结段连结
6) 初始段连结
7) 序列合并
8) 操作符记录
9) 用参数替换
10)解序列截断
11)序列倒置
2009-8-20 高级人工智能 ---史忠植 25
差别表：
入口形式：
“为简少 <差别 >，应采用 <T-操作符集 >中的一个操作”
2009-8-20 高级人工智能 ---史忠植 26
T-空间的差别测度 Dr（ 差异函数）
Dr的值是四维向量：
新旧问题初态的差别
新旧问题终态的差别
新旧问题路径限制的差别
新旧问题方法可应用度的差别。
2009-8-20 高级人工智能 ---史忠植 27
7.4.4 转换类比学习系统输 入比较器知识库操作表解法库操作模块 解法栈检验模块 输 出转换类比学习系统框图
2009-8-20 高级人工智能 ---史忠植 28
知识库 —— 操作表差 别
d1
d2
…
差 别
OP11,OP12,…
…
OP21,OP22,…
2009-8-20 高级人工智能 ---史忠植 29
知识库 —— 解法表达形式问题类型
S0,S1,S2,…,Sn
初始状态 S0
目标状态 Sn
OP1,OP2,…,OPi,…,OPn
…
2009-8-20 高级人工智能 ---史忠植 30
例：已知“偶数 × 偶数 =偶数”，用类比的方法求证“奇数 × 奇数 =奇数”。
证明“两个偶数之积仍为偶数”的过程
偶数可表示为 2× A的形式 ；
两偶数之积为 (2× m)× (2× n)；
(2× m)× (2× n)=4× m× n；
将 4× m× n表示为 2× A的形式，即令 A=2× m× n。
2009-8-20 高级人工智能 ---史忠植 31
证明“两个奇数之积仍为奇数”的过程
（从关于偶数的证明过程中得到启示）
奇数可表示为 2× A+1的形式 ；
两偶数之积为 (2× m+1)× (2× n+1)；
(2× m+1)× (2× n+1)=4× m× n+2× m+2× n+1；
将结果表示为 2× A+1的形式，即令
A=2× m× n+m+n。
2009-8-20 高级人工智能 ---史忠植 32
解法库中的一个解序列求证类
(2m)× (2n)=2A
4mn=2A
2mn=A
A为整数
(2m)× (2n)=2A
A为整数两项相乘除公因子 2
整数经 +,-、×运算仍为整数
2009-8-20 高级人工智能 ---史忠植 33
操作表差 别参数不同
…
…
差 别参数替换
…
…
前提不满足 子序列拼接
2009-8-20 高级人工智能 ---史忠植 34
输入的问题求证类
(2m+1)× (2n+1)=2A+1
A为整数
…
2009-8-20 高级人工智能 ---史忠植 35
类比求解过程的操作序列求证类
(2m+1)× (2n+1)=2A+1
A为整数
4mn+2m+2n+1=2A+1
4mn+2m+2n=2A
2mn+m+n=A
(2m+1)× (2n+1)=2A+1
两项相乘两边减 1
两边除公因子 2
整数经 +,-、×运算仍为整数
2009-8-20 高级人工智能 ---史忠植 36
7.4.5 类比学习的泛化规则
改善类比学习系统性能的一些方法：
1) 获取解的一般过程。
2) 插曲记忆组织与重构
3) T操作符的改善与获取
2009-8-20 高级人工智能 ---史忠植 37
获取解的一般过程
1) 类比器产生一个新问题后，若经过测试，该解满足新问题的要求，则该解加入正例集 ；
2) 若该解不满足新问题，则记录失败原因，并将该解加入反例集；
3) 归纳正例集和反例集，产生一条规则，能指导所有正例集中的成功解，而不满足反例集中任一不成功解；
4) 通过对反例容易与正例混淆的分析可以提出范化规则结构的正例；
5) 当类比器无法求解时获得的信息可作为加强或产生相似性测度的正例或反例，作为反例去改进相似性测度。
2009-8-20 高级人工智能 ---史忠植 38
插曲记忆组织与重构
目的是为了改进相似性 /差异测度的精确性和对经验 /解的记忆的构造和检索。
采用的方法是以失败驱动的方式进行差异测度调准
2009-8-20 高级人工智能 ---史忠植 39
T-操作符的改善与获取改善：操作符在差别表的对应入口的限制条件。
1) 在 T-空间中比较失败路径解的 T-操作符和成功路径解的 T-操作符。
2) 如果该 T-操作符在差别表中有多个入口，一些入口仅对应于该操作的失败例子，则删除这些入口。
3) 若某个入口对应的失败比成功多得多，说明要减小的差别描述可能太一般，必须分解为更特殊差别的不相交子集。
2009-8-20 高级人工智能 ---史忠植 40
获取：
1) 对问题求解器求得的解和 T-空间中各次尝试转换进行比较。
2) 找出某个最接近实际解的中间状态（ Dr值最小）。
3) 假设某个新的 T-操作符是从这个状态到实际解的转换，并使其可用。
4) 若加入新操作符后，有许多类比求解不成功，导致产生了更多的新的 T-操作符，则应用观察学习技术，
若例子形成很相似的例子集，则可以根据例子集的特征来重新构造 T-操作符。
5) 将新的 T-操作符加入可用 T-操作符集。
6) 在差别表中编序新 T-操作符的入口。
2009-8-20 高级人工智能 ---史忠植 41
7.5 派生类比
2009-8-20 高级人工智能 ---史忠植 42
7.6 因果关系型类比学习
7.6.1类比匹配技术与相似性度量概述
匹配的形式：
1) 等价匹配
2) 选择匹配
3) 规则匹配
4) 启发式匹配
2009-8-20 高级人工智能 ---史忠植 43
相似度测量：
|)()(| 2211 kkjj qV a l u eEqV a l u eE
属性相似度的测量：
对象相似度的测量：
||),(
21
1 2
1 12
1 1
1 11
21
m
j j
m
j j
m
i i
m
i i
im
P
P
P
P
EES
2009-8-20 高级人工智能 ---史忠植 44
7.6.2 知识表示
一个好的表示方法应满足如下条件：
1) 能够使重要的事实清楚的表达出来
2) 能消除一些无关的细节
3) 其表达应是清晰的，决不能含糊其词，模棱两可，更应避免多义性
4) 应能根据自然输入对知识进行计算处理
2009-8-20 高级人工智能 ---史忠植 45
7.6.3 类比匹配
匹配器应具有如下特征：
1) 具有判定对应部分是否相似的函数。
2) 能启发式地搜索所有可能的匹配。
2009-8-20 高级人工智能 ---史忠植 46
寻找两个状态之间的匹配关系时应遵循以下原则：
1) 性质和关系分别与性质和关系相配对
2) 采用特定领域的知识进行启发式选择
3) 考虑适当的分类信息
4) 从重要关系或性质到非重要关系或性质的配对优先原则
5) 对两个具有较多部分的状态配对时可采用分组的方法
6) 匹配进行之前可采用抽象的方法，使一些具体的事件具有一定的普遍性。
7) 具有一定的学习能力。
2009-8-20 高级人工智能 ---史忠植 47
7.6.4 抽取问题的特征特征抽取一般分析方法是，将例子中的概念、特征、行为或其它关系表示成问题空间中一点，
这种表示必须突出问题的主要特性。即概念获取和性质描述过程，使其由外部变为内部形式，
并努力保证该信息的完整。分为静态方法和动态方法。
2009-8-20 高级人工智能 ---史忠植 48
7.6.5 相似度的计算方法特征集 A和 B的相似度 S由下式决定：
)()()(),( ABfBAfBAfBAS
当 时，可以简化为：1
)()()()(),( ABfBAfBfAfBAS
2009-8-20 高级人工智能 ---史忠植 49
7.6.6 最佳对应关系匹配
对象间相似性判别方法采用启发式。
通过动态对特征的抽取，利用重要性制导匹配来决定对象间的相似性。主要步骤是：
1) 以对象的各部分的分类、特性、动作及其它关系线索，根据其重要性，来建立对象间的关系对应，形成一个匹配。
2) 在各种匹配中寻找一个最佳匹配。
3) 对事实进行适当的抽象或细化。
2009-8-20 高级人工智能 ---史忠植 50
7.7 联想类比学习
联想类比学习是把已知领域（源系统）的知识联想到未知领域（目标系统）的类比方法，是一种综合的类比推理方法。
2009-8-20 高级人工智能 ---史忠植 51
已知源系统,目标系统,
联想条件 。
1) 输入,并置 1←i,1←j ；
2) 是否满足，即,若满足转 (5)；
3) 置 i+1←i,若 i≤n 转 (2)；
4) 置 j+1←j,1←I,若 j≤m 转 (2)；
5) 进行类比映射：
niOS ii,.,,,2,1,,,T
mjR j,...,2,1?，
pkTtROS kjii,...,2,1,,,,
jR,,TROS jii
联想类比算法
2009-8-20 高级人工智能 ---史忠植 52
5) 进行类比映射：
(5.1)概念映射
(5.2)关系映射
(5.3)方法映射
6) 重新设置联想条件,转 (2)；
7) 类比成功，进行检验，结束
jR
2009-8-20 高级人工智能 ---史忠植 53
联想类比条件：
同构相似联想
同态相似联想
接近联想
对比联想
模糊联想
2009-8-20 高级人工智能 ---史忠植 54
7.8 约束满足类比
7.8.1 三类约束
结构一致性
语义相似
语用相似
2009-8-20 高级人工智能 ---史忠植 55
7.8.2 约束满足理论
Holyoak和 Thagard（ 1989） 提出了约束满足理论，综述如下：
1) 同构的结构约束适用于两个类比物元素之间关系对应的最大一致性。
2) 语义相似性支持具有相似含义元素之间可能对应的程度。
3) 语用中心适用于元素之间的映射，为了达到目的，相信所使用地类比是重要的。
2009-8-20 高级人工智能 ---史忠植 56
7.8.3 ACMS算法
1) 对于 T中每个命题,使用,对于 S中每个命题 使用,
if 和 是它们各自结构的部分，
并具有相同数目的参数，
then (1)建立,
且 ；
(2)建立连结
(3)建立连结
(4)建立连结
(5)每对 之间建立连结。
ipropT ))a r g...a r g( a r g( 21 iniii TTTp r e d T
ipropS ))a r g...a r g( a r g( 21 iniii SSSp r e d S
ipropT ipropS
iiii p r e d Sp r e d Tp r o p Sp r o p T,
ikik ST a rga rg?
iiii p r e d Sp r e d Tandp r o p Sp r o p T
ikikii STp r o p Sp r o p T a r ga r g 且
ikikii STp r e d Sp r e d T a r ga r g 且
ikik ST a rga rg?
2009-8-20 高级人工智能 ---史忠植 57
2) 在不相容映射的两个单元之间建立禁止连结，通过却省禁止参数 i置以负权值。
3) 对于每个谓词映射单元,基于两个谓词之间的语义相似性建立语义单元连结。如果不相似，则权值最小为 。如果谓词相同，则权值为最大值 。
4) 对于列为 IMPORTMANT的每个元素，包括谓词、对象、命题，
从语用单元到每个有关的映射元素建立连结。 IMPORTMANT
映射的语用中心的权值为参数 。
5) 对于列入 PRESUMED的每个单元，为 PRESUMED映射的语用中心，从语用单元建立连接，权值等于参数 。
ii p re d Sp re d T?
minS maxS
1p
2p
