第五章 范例 推理史忠植中科院计算所第五章 范例 推理史忠植中科院计算所第六章 范例 推理
5.1 概述
5.2 流程
5.3 范例表示
5.4 范例检索
5.5 相似性
5.6 范例复用
5.7 范例推理工具
5.8 范例推理应用概述概述概述范例( case),“范例是一段带有上下文信息的知识,
该知识表达了推理机在达到其目标的过程中能起关键作用的经验”。具体来说,一个范例应具有如下特性:
·范例表示了与某个上下文有关的具体知识,这种知识具有可操作性。
·范例可以是各式各样的,可有不同的形状和粒度,可涵盖或大或小的时间片,可带有问题的解答或动作执行后的效应。
·范例记录了有用的经验,这种经验能帮助推理机在未来更容易地达到目标,或提醒推理机失败发生的可能性有多大等等。
概述人们为了解决一个新问题,先是进行回忆,从记忆中找到一个与新问题相似的范例,然后把该范例中的有关信息和知识复用到新问题的求解之中。
在基于范例推理 (Case-Based Reasoning,简称 CBR)中,
把当前所面临的问题或情况称为目标范例 (target case),
而把记忆的问题或情况称为源范例 (base case)。粗略地说,基于范例推理就是由目标范例的提示而获得记忆中的源范例,并由源范例来指导目标范例求解的一种策略。
概述基于范例推理中知识表示是以范例为基础,范例的获取比规则获取要容易,大大简化知识获取 。 对过去的求解结果进行复用,而不是再次从头推导,可以提高对新问题的求解效率 。 过去求解成功或失败的经历可以指导当前求解时该怎样走向成功或避开失败,这样可以改善求解的质量 。 对于那些目前没有或根本不存在可以通过计算推 导来解决的问题 。 如在法律中的判例,
基于范例推理能很好发挥作用 。
概述基于范例推理中知识表示是以范例为基础,范例的获取比规则获取要容易,大大简化知识获取 。 对过去的求解结果进行复用,而不是再次从头推导,可以提高对新问题的求解效率 。 过去求解成功或失败的经历可以指导当前求解时该怎样走向成功或避开失败,这样可以改善求解的质量 。 对于那些目前没有或根本不存在可以通过计算推 导来解决的问题 。 如在法律中的判例,
基于范例推理能很好发挥作用 。
概述范例推理范例推理概述中国科学院计算技术研究所智能信息处理开放实验室在基于范例推理方面进行了一系列研究。
1991年史忠植、李宝东提出了记忆网模型和范例检索算法。
1993年周涵研制了基于范例学习的内燃机油产品设计系统 EOFDS。
1994年徐众会开发了基于范例推理的天气预报系统。
1996年王军开发了基于范例推理的淮河王家坝洪水预报调度系统 FOREZ。
2000年研制了渔情分析专家系统范例范例问题求解问题求解问题求解问题求解问题求解基于范例学习的一般过程基于范例学习的一般过程范例存储基于范例学习的一般过程新问题新范例 检索 历史范例范例库 复 用保存修正范例 修正 解答范例确认解 建议解主要问题
(1) 范例表示,基于范例推理方法的效率和范例表示紧密相关。范例表示涉及这样几个问题,选择什么信息存放在一个范例中;如何选择合适的范例内容描述结构;范例库如何组织和索引。对于那些数量达到成千上万、而且十分复杂的范例,
组织和索引问题尤其重要。
(2) 分析模型,分析模型用于分析目标范例,从中识别和抽取检索源范例库的信息。
(3) 范例检索,利用检索信息从源范例库中检索并选择潜在可用的源范例。基于范例推理方法和人类解决问题的方式很相近。碰到一个新问题时,首先是从记忆或范例库中回忆出与当前问题相关的最佳范例。后面所有工作能否发挥出应有的作用,很大程度上依赖于这一阶段得到的范例质量的高低,因此这步非常关键。
一般讲,范例匹配不是精确的,只能是部分匹配或近似匹配。因此,它要求有一个相似度的评价标准。该标准定义得好,会使得检索出的范例十分有用,否则将会严重影响后面的过程。
主要问题
(4) 类比映射,寻找目标范例同源范例之间的对应关系。
(5) 类比转换,转换源范例中同目标范例相关的信息,以便应用于目标范例的求解过程中。其中,涉及到对源范例的求解方案的修改。把检索到的源范例的解答复用于新问题或新范例之中。它们分别是,源范例与目标范例间有何不同之处;
源范例中的哪些部分可以用于目标范例。对于简单的分类问题,仅需要把源范例的分类结果直接用于目标范例。它无需考虑它们之间的差别,因为实际上范例检索已经完成了这项工作。而对于问题求解之类的问题,则需要根据它们之间的不同对复用的解进行调整。
(6) 解释过程,对把转换过的源范例的求解方案应用到目标范例时所出现的失败做出解释,给出失败的因果分析报告。有时对成功也同样做出解释。基于解释的索引也是一种重要的方法。
(7) 范例修补,有些类似于类比转换,区别在于修补过程的输入是解方案和一个失败报告,而且也许还包含一个解释,然后修改这个解以排除失败的因素。
主要问题
(8) 类比验证,验证目标范例和源范例进行类比的有效性。
(9) 范例保存,新问题得到了解决,则形成了一个可能用于将来情形与之相似的问题。这时有必要把它加入到范例库中。这是学习也是这是知识获取。此过程涉及选取哪些信息保留,以及如何把新范例有机集成到范例库中。修改和精化源范例库,其中包括泛化和抽象等过程。
在决定选取范例的哪些信息进行保留时,一般要考虑以下几点:和问题有关的特征描述;问题的求解结果;以及解答为什么成功或失败的原因及解释。
把新范例加入到范例库中,需要对它建立有效的索引,这样以后才能对之作出有效的回忆。索引应使得与该范例有关时能回忆得出,与它无关时不应回忆出。为此,可能要对范例库的索引内容甚至结构进行调整,如改变索引的强度或特征权值。
基于范例推理流程检索建议粗略解修正 辩护评批实际评估存储范例的表示在生理学、心理学等领域,已经广泛开展了关于记忆的研究。心理学的研究者们注重研究记忆的一般理论,已经提出了许多记忆模型,
典型的包括情景记忆 (episodic memory),语义记忆 (semantic
memory),联想记忆 (associative memory),Schank 的动态记忆理论 (dynamic memory) 等。
知识是有结构的体系。在某些任务的执行过程中,专家采用语义记忆来存储信息。这种信息记忆方法具有下列优点,
·有利于检索。
·易于组织。可以把它们连接成树形层次或者网络。
·易于管理。知识的改变只对局部产生影响。
·有利于知识的共享。
范例的表示语义记忆单元,是指在学习、分析、理解、记忆知识的过程中所着重关注的其中那些概念、模式、主题等,以及据此形成的关于知识的概念性认识。换言之,这些语义记忆单元是系统对知识经,计算,
之后,抽取其中最能反映知识本身特征且可以很好地使知识内在地联系在一起的那些因素而获得的。
范例的表示我们所记忆的知识彼此之间并不是孤立的,而是通过某种内在的因素相互之间紧密地或松散地有机联系成的一个统一的体系。我们使用记忆网来概括知识的这一特点。一个记忆网便是以语义记忆单元为结点,以语义记忆单元间的各种关系为连接建立起来的网络。
范例的表示
SMU = { SMU_NAME slot
Constraint slots
Taxonomy slots
Causality slots
Similarity slots
Partonomy slots
Case slots
Theory slots
}
范例的表示
(1) SMU_NAME slot,简记为 SMU 槽。它是语义记忆单元的概念性描述,通常是一个词汇或者一个短语。
(2) Constraint slots,简记为 CON 槽。它是对语义记忆单元施加的某些约束。通常,这些约束并不是结构性的,而只是对
SMU 描述本身所加的约束。另外,每一约束都有 CAS 侧面
(facet)和 THY 侧面与之相连。
(3) Taxonomy slots,简记为 TAX 槽。它定义了与该 SMU相关的分类体系中的该 SMU 的一些父类和子类。因此,它描述了网络中结点间的类别关系。
(4) Causality slots,简记为 CAU 槽。它定义了与该 SMU
有因果联系的其它 SMU,它或者是另一些 SMU 的原因,或者是另外一些 SMU 的结果。因此,它描述了网络中结点间的因果联系。
范例的表示
(5) Similarity slots,简记为 SIM 槽。它定义了与该 SMU
相似的其它 SMU,描述网络中结点间的相似关系。
(6) Partonomy slots,简记为 PAR 槽。它定义了与该 SMU
具有部分整体关系的其它 SMU。
(7) Case slots,简记为 CAS 槽。它定义了与该 SMU 相关的范例集。
(8) Theory slots,简记为 THY 槽。它定义了关于该 SMU
的理论知识。
上述 8 类槽可以总地分成三大类。一类反映各 SMU 之间的关系,
包括 TAX 槽,CAU 槽,SIM 槽和 PAR 槽 ; 第二类反映 SMU 自身的内容和特性,包括 SMU 槽和 THY 槽 ; 第三类反映与 SMU相关的范例信息,包括 CAS 槽和 CON 槽。
范例组织范例组织时由两部分组成,一是范例的内容,范例应该包含哪些有关的东西才能对问题的解决有用;二是范例的索引,它和范例的组织结构以及检索有关,反应了不同范例间的区别 。
范例内容
( 1) 问题或情景描述 是对要求解的问题或要理解的情景的描述,
一般要包括这些内容:当范例发生时推理器的目标,完成该目标所要涉及的任务,周围世界或环境与可能解决方案相关的所有特征 。
( 2) 解决方案 的内容是问题如何在一特定情形下得到解决 。 它可能是对问题的简单解答,也可能是得出解答的推导过程 。
( 3) 结果 记录了实施解决方案后的结果情况,是失败还是成功 。
有了结果内容,CBR在给出建议解时有能给出曾经成功地工作的范例,同时也能利用失败的范例来避免可能会发生的问题 。 当对问题还缺乏足够的了解时,通过在范例的表示上加上结果部分能取得较好的效果 。
范例索引建立范例索引有三个原则:
① 索引与具体领域有关 。 数据库中的索引是通用的,目的仅仅是追求索引能对数据集合进行平衡的划分从而使得检索速度最快;而范例索引则要考虑是否有利于将来的范例检索,它决定了针对某个具体的问题哪些范例被复用;
② 索引应该有一定的抽象或泛化程度,这样才能灵活处理以后可能遇到的各种情景,太具体则不能满足更多的情况;
③ 索引应该有一定的具体性,这样才能在以后被容易地识别出来,太抽象则各个范例之间的差别将被消除 。
范例的检索范例检索 —— 从范例库 (Case Base)中找到一个或多个与当前问题最相似的范例; CBR系统中的知识库不是以前专家系统中的规则库,它是由领域专家以前解决过的一些问题组成 。 范例库中的每一个范例包括以前问题的一般描述即情景和解法 。 一个新范例并入范例库时,同时也建立了关于这个范例的主要特征的索引 。 当接受了一个求解新问题的要求后,CBR利用相似度知识和特征索引从范例库中找出与当前问题相关的最佳范例,由于它所回忆的内容,即所得到的范例质量和数量直接影响着问题的解决效果,
所以此项工作比较重要 。 它通过三个子过程,即特征辩识,初步匹配,最佳选定来实现 。
特征辩识指对问题进行分析,提取有关特征,特征提取方式有:
(a)从问题的描述中直接获得问题的特征,如自然语言对问题进行描述并输入系统,系统可以对句子进行关键词提取,这些关键词就是问题的某些特征 。
(b)对问题经过分析理解后导出的特征,如图象分析理解中涉及的特征提取 。
(c)根据上下文或知识模型的需要从用户那里通过交互方式获取的特征,系统向用户提问,以缩小检索范围,使检索的范例更加准确 。
初步匹配指从范例库中找到一组与当前问题相关的候选范例。这是通过使用上述特征作为范例库的索引来完成检索的。由于一般不存在完全的精确匹配,
所以要对范例之间的特征关系进行相似度估计,
它可以是基于上述特征的与领域知识关系不大的表面估计,也可以通过对问题进行深入理解和分析后的深层估计,在具体做法上,则可以通过对特征赋于不同的权值体现不同的重要性。相似度评价方法有最近邻法、归纳法等。
最佳选定指从初步匹配过程中获得的一组候选范例中选取一个或几个与当前问题最相关的范例。这一步和领域知识关系密切。可以由领域知识模型或领域知识工程师对范例进行解释,然后对这些解释进行有效测试和评估,
最后依据某种度量标准对候选范例进行排序,得分最高的就成为最佳范例,比如最相关的或解释最合理的范例可选定为最佳范例。
相似性关系范例的表示表明,范例的情境是由许多属性组成,
范例间的相似度就是根据属性(或变量)之间的相似度定义的。目标范例与源范例之间的相似性有语义相似、结构相似、目标相似和个体相似。
语义相似性两范例之间是可以类比的,首先必须满足语义上具有相似性关系。相似性关系是类比问题求解的基础。两实体的类比可以区分为正类比、反类比、不确定类比。 正类比是由相似性关系所确定的两实体之间的可类比部分,
反类比则是已被确定为两实体间不相似的部分,不确定类比是两实体之间尚未确定是否可类比的部分。两个实体可类比的条件之一是,模型的本质性质和因果关系不构成反类比的一部分。 不确定类比使得类比具有一定的预见性,这种预见可能是正确的,也可能是错误的。
在类比求解中,目标范例的本质特征和源范例的本质特征必须具有相似性关系,才能使类比有了基础。
个体相似性在我们的模型中强调的另一重要约束是个体的类别信息。从不严格的意义上讲,如果两个个体之间具有一些 (或一个 ) 相似的属性,则它们是属于同一类别的。
在概念聚类中,我们使用概念 (或客体 ) 间的相关性或紧致性来对概念 (客体 ) 集进行分类。相关性是指概念的属性之间相似度的平均值。但在这里,我们将把电线和绳索看作是同一类别的,因为它们 均可以用来绑缚物体。
相似性计算
1,绝对值距离 (Manhattan):
其中 Vik 和 Vjk 分别表示范例 i和范例 j的第 k个属性值 。

N
1k
jkikij VVd
相似性计算
2,欧氏距离 (Euclidean)

N
k
jkikij VVd
1
2)(
相似性计算
3.麦考斯基距离
q/1N
1k
q
jkikij VVd?

范例的复用把检索到的旧范例的解答复用到新问题或新范例之中 。
通过所给问题和范例库中范例比较得到新旧范例之间的不同之处,然后回答哪些解答部分可以复用到新问题之中 。 对于简单的分类问题,仅需要把旧范例的分类结果直接用于新范例,它无需考虑新旧范例之间的差别 。 而对于问题求解类的问题,则需要对领域知识的深入理解,根据范例之间的不同对问题进行调整,
可以是对整个解的某项作一些调整,也可以对整个解的进行微调 。
替换法
(1)重新例化 ( reinstantiation),这是一种很简单的替换操作,仅仅是用新的个体替换旧解中的个体 。 例如,川菜设计系统 CHEF,在根据牛排炒甘蓝菜来设计一道鸡肉炒雪豆菜,
它就是把该菜谱中的所有牛排替换成鸡肉,把甘蓝替换成雪豆 。
(2)参数调整 ( parameter adjustment),这是一种处理数值参数的启发式方法 。 它和具体的输出与输入参数间的关系模型
( 输入发生什么变化,会导致输出产生怎样的相应变化 ) 有关 。
(3)局部搜索 ( local search),使用辅助的知识结构来获得替换值 。 例如,设计点心时缺少桔子,则可使用此法在一个水果语义网知识结构中搜索一个与桔子相近的水果如苹果来代替 。
替换法
(4)查询 ( query),用带条件的查询在范例库或辅助知识结构中获取要替换的内容 。
(5)特定搜索 ( specialized search),同时在范例库和辅助知识结构中进行查询,但在范例库中查询时使用辅助知识来启发式指导如何搜索 。
(6)基于范例的替换 ( case-based substitution),使用其它的范例来建议一个替换 。
转换法转换法包括:常识转换法 ( common-sense transformation),使用明白易懂的常识性启发式从旧解中替换,删除或增加某些组成部分 。 典型的常理转换法是,,删去次要组成部分,。 模型 制导修补法 ( model-guided repair),通过因果模型来指导如何转换 。 故障诊断中就经常使用这种方法 。
特定目标驱动法这种方法主要用于完成领域相关以及要做结构修改的修正 。 该法使用的各种启发式需要根据它们可用的情景进行索引 。 特定目标驱动的修正启发式知识一般通过评价近似解作用,并通过使用基于规则的产生式系统来控制 。
派生重演上述方法所做的修正是在旧解的解答上完成的 。 重演方法则是使用过去的推导出旧解的方法来推导出新解 。 这种方法关心的是解是如何求出来的 。 同前面的基于范例替换相比,派生重演使用的则是一种基于范例的修正手段 。
CBR 工具
CBR Design Explorer - Diagnostic & Design Shell
(Artificial Intelligence Applications Institute at University
of Edinburgh)
CBR Framework for Bioprocessing
(Bioprocesses Group at VTT Biotechnology and Food
Research)
CBR Tools - object oriented software library in JAVA
(AID research group at INRIA Sophia Antipolis)
CBR-Works product family - CBR shell (research licenses
available)
(tec:inno GmbH )
AIAI CBR Diagnostic & Design
Shell Page
Fuzzy logic matching algorithms (latticed,
SmoothFuzzy)
Adaptive confidence measures
Multiple diagnostic algorithms (negative selection,
density selection,omission matching,identify outliers,
best match,one-case one-vote,probabilistic curve,
default)
Adaptive thresholding (adaptive 'k' neighbourhood)
High/low/linearity investigation algorithm
Metaweighting structure for fields by operator type
Adaptive field weighting system (stochastic hill-
climbing)
AIAI CBR Diagnostic & Design
Shell Page
"Create a key" from ASCII with automatic parsing and
operator selection
Key/case base/test base creation/saving support
Unlimited data/field depth - tested to 6000 fields
Serial and parallel testing methods with batch
processing and summary mode
Help system
Night learning cycle
An interactive tutorial with machine learning
example sets
AIAI CBR Diagnostic & Design
Shell Page
The new release will feature:
Next-generation analysis algorithms
Corporate memory components
Genetic algorithm field weight learning
ODBC data base support
Multiple goals
'Overlap' matching of varying length records
Adaptive text parsing algorithms
Meta-induction for rules and indexing
Automatic case builder and tree generation
Dynamic case base reduction and compression
Parsing and data transformation system
CBR*Tools
CBR*Tools is an object-oriented software library for Case-Based
Reasoning (CBR),It provides a basic reusable CBR framework that
supports the development of CBR applications,It can be especially
used for problems addressing behavorial situation retrieval and
indexation.
CBR*Tools
CBR*Tools consists of three packages,namely,the core,time,and
navigation package,The library is specified with the OMT method
and written in Java,Click on the icon (on the right hand side),to get a
full image of the system's main user interface.
CBR*Tools
CBR*Tools
中心渔场预报专家系统鱼类的洄游以及中心渔场的形成受到这几个因素的制约:海水温度 ( 包括海洋表面温度,海洋底层温度 ) ;台站数据,如海水盐度,盐度梯度,长江径流量,风向,风速等;海洋叶绿素浓度 。
但是,鱼类的洄游规律受很多因素制约,变化非常复杂,难以用传统的数学方法和模型描述 。 同时专家关于中心渔场规律的知识是不精确的,不完全的 。 值得庆幸的是,我们已经收集了 20来年东海的渔况海况数据,这是非常宝贵的资料,因此可以从中挖掘出许多有用的信息和知识,根据历年的情况来分析,预测中心渔场的趋势 。 整个系统采用了基于范例推理 ( CBR) 的方案 。 因为
CBR非常适合应用于系统已存在大量历史数据,专家通过实例来描述他们的领域,问题未被完全理解,可用的领域知识很少,系统中有很多例外的规则的情形 。
中心渔场预报专家系统由于大多数海况信息是以周为单位收集的,同时为了便于处理和计算,我们根据实际情况对需求进行了简化,预测的周期规定为一周 。 这样,问题变成了如果知道本周中心渔产 ( 位置,产量和大小 ),预报下周 ( 下下周 ) 中心渔场 ( 位置,产量和大小 ) 。
即使如此,问题也是相当困难的,因为渔场位置,大小是一种空间数据 。 同时,海况信息涉及 600来个空间和非空间属性,回归的方法,
中心渔场预报专家系统在我们的系统中,对空间条件属性,采用三个相似性度量方法
( 函数 ),
·基于渔场位置的相似
sim1 = -∑(Wi * distance(pos(goal) - pos(source))) / ∑wi
·基于温度场的相似
sim2 = -∑(wi * difference(temp(goal) - temp(source))) /
∑wi
·基于温度梯度的相似
sim3 = -∑(wi * difference(delta(goal) - delta(source)))
/ ∑wi
其中,wi是权重 。 如果该温度测试点与样本的中心渔场距离 di越近,权越大 。
中心渔场预报专家系统预处理(聚类)
结果汇总范例保存 修 正可视化接口浏览范例历史数据范例库数据过滤多策略相似检索新范例最终结果相似范例输入数据中心渔场预报专家系统机器翻译基于规则和范例的推理相结合的技术。
对于基于范例的推理,采用基于多功能层次和单词驱动相结合的混合式匹配算法。为了加快检索的速度和提高检索的效率,还在多抽象层次记忆库的基础上,提出了基于模式抽象特征的约束检索方法。
机器翻译针对基于范例类比翻译中的译文构造,通过建立例子译文和目标译文之间的直接转换算子来实现目标相似解构造的方法。
机器翻译机器翻译机器翻译机器翻译