搜索推理技术2课件

搜索推理技术(2)主要内容产生式系统不确定性推理非单调性推理MachineIntelligence产生式系统概述“产生式”—1943年Post首先在一种计算形式体系中提出的术语。60年代开始，产生式系统成为专家系统的最基本的结构。产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程。

MachineIntelligence产生式规则的语义：如果前提P被满足，则可推出结论Q或执行Q所规定的操作例：R:IF动物会飞AND会下蛋

THEN该动物是鸟产生式系统MachineIntelligence产生式系统的组成三要素：1、一个总数据库

存放问题求解过程中各种当前信息的数据结构；2、一组产生式规则

描述相应领域内的知识3、一个控制系统

选择规则库中与当前综合数据库相匹配的规则并执行，必要时进行冲突消解。产生式系统MachineIntelligence产生式规则库综合数据库控制系统产生式系统的基本结构产生式系统MachineIntelligence规则库用于描述相应领域内知识的产生式集合称为规则库有效的表达领域内的过程性的知识对知识进行合理的组织和管理综合数据库用于存放问题求解过程中各种当前信息的数据结构初始状态、事实或证据中间推理结论最后结果产生式系统MachineIntelligence产生式系统的推理正向推理从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。例：总数据库：P1

规则集合：R1:P1->P2R2:P2->P3R3:P3->P4产生式系统MachineIntelligence产生式系统的推理逆向推理从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。例：总数据库：P1

规则集合：R1:P1->P2R2:P2->P3R3:P3->P4产生式系统MachineIntelligence产生式系统产生式系统的推理正逆向推理的比较

项目正向推理逆向推理驱动方式推理方法启动方法推理方向典型系统数据驱动从一组数据出发向前推导结论从一个事件启动由底向上推理CLIPS，OPS目标驱动从可能的解答出发，向后推理验证明解答由询问关于目标状态的一个问题而启动由顶向下推理PROLOGMachineIntelligence一个简单的例子问题：设字符转换规则

A∧B→C A∧C→D B∧C→G B∧E→F D→E

已知：A，B

求：F产生式系统MachineIntelligence一个简单的例子（续1）综合数据库

{x}，其中x为字符规则集

1：IFA∧BTHENC 2：IFA∧CTHEND 3：IFB∧CTHENG 4：IFB∧ETHENF 5：IFDTHENE产生式系统MachineIntelligence一个简单的例子（续2）控制策略 顺序排队初始条件

{A，B}结束条件

F∈{x}产生式系统MachineIntelligence一个简单的例子（续3）综合数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F1，IFA∧BTHENC 2，IFA∧CTHEND3，IFB∧CTHENG 4，IFB∧ETHENF5，IFDTHENE求解过程产生式系统MachineIntelligencer6：若某动物是哺乳动物且吃肉，则它是食肉动物。

r7：若某动物是哺乳动物且有蹄，则它是有蹄动物。

r8：若某动物是有蹄动物且反刍食物，则它是偶蹄动物。

r9：若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。r10：若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。r11：若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。产生式系统MachineIntelligence

r12：若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。

r13：若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。

r14：若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。

r15：若某动物是鸟且善飞且不怕风浪，则它是海燕。产生式系统MachineIntelligence动物分类正向推理树

老虎食肉动物哺乳动物有毛发吃肉黄褐色有黑色条纹产生式系统r2r6r6r9r9r9MachineIntelligence图5—5动物分类反向推理树产生式系统逆向推理，判断该动物是否为老虎：MachineIntelligence局限性：（1）效率不高：求解过程是“匹配-冲突消解-执行”的过程，若规则库较大，易引起组合爆炸。（2）不能表示具有结构性的知识：产生式适合于表示具有因果关系的过程性知识，不能表示具有结构关系的事物间的区别与联系。产生式系统MachineIntelligence证据的不确定性结论的不确定性不确定性推理MachineIntelligence证据的不确定性一般通过对事实赋予一个介于0和1之间的系数来表示事实的不确定性。这个系数被称为可信度。当规则具有一个以上的条件时，需要根据各条件的可信度来求得总条件的可信度。有两类方法：以模糊集理论为基础的方法以概率为基础的方法不确定性推理MachineIntelligence证据的不确定性不确定性推理赋予每个证据以可信度,当把单独条件的可信度结合起来求取总的可信度时,它取决于各可信度的乘积.0.90.51.00.45证据可信度的概率论处理法MachineIntelligence结论的不确定性结论的不确定性也叫规则的不确定性，表示当规则的条件被完全满足时，产生某种结论的不确定性程度。不确定性的表示：通过赋予一个介于0和1之间的系数来表示不确定性。不确定性推理MachineIntelligence结论的不确定性不确定性的处理如果规则的条件部分不完全确定，则求得结论的可信度的方法有两种：取结论可信度为条件可信度与系数的乘积；不确定性推理0.5CinCout0.40.8MachineIntelligence结论的不确定性按照某种概率论的解释，可以假设规则的条件部分的可信度Cin和其结论部分的可信度Cout间存在某种关系，用这种关系来代表规则的不确定性；不确定性推理CinCoutCinCoutCinCoutMachineIntelligence不确定性推理结论的不确定性多个规则支持同一事实的不确定性基于模糊集理论的方法取支持这个事实的多个规则的可信度的最大值作为事实的可信度。基于概率论的方法

-首先把各个证据的可信度转换成可信性比例r。可信性比例r和可信度c之间的关系可表示为

-将各证据的可信度比例简单地相乘就可以求得这些证据所支持的事实的可信性比例。

-利用公式将可信性比例转换为可信度。

MachineIntelligence单调推理：新的命题的加入不会推翻原来的命题，随着时间的推移，系统内含的知识有增无减，如建立在谓词逻辑基础上的系统。非单调推理：新的命题的加入有可能会推翻原有命题，随着时间的推移，系统内含的知识不一定是增加。非单调性推理MachineIntelligence需要非单调推理的理由知识的不完全，由于知识的不完全性，只能对某些问题做暂时的假设，这些假设可能对也可能不对，可在以后进一步修正；一个有限的信念集合仅仅是现实世界的近似描述，会有很多的例外；客观世界变化太快；非单调性推理MachineIntelligence缺省推理定义：当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(defaultreasoning)。

Reiter的缺省逻辑：“S在缺省的条件下成立”是指“当且仅当没有事实证明S不成立时S是成立的”非单调性推理MachineIntelligence非单调推理系统：正确性维持系统定义：正确性维持系统(TruthMaintenanceSystem,简称TMS)是一个已经实现了的非单调系统，用以协助其他推理程序维持系统的正确性，其在其它程序所产生的命题之间保持相容性。非单调性推理MachineIntelligence非单调推理系统：正确性维持系统工作原理：在TMS中，每一命题或规则均称为节点，且对任一节点以下两种状态必居其一：IN相信为真OUT不相信为真，或无理由相信为真，或当前没有可相信的理由。

IN节点是指那些至少有一个在当前说来是有效证实的节点。OUT结点则指那些当前无任何有效证实的节点。

非单调性推理MachineIntelligence非单调推理系统：正确性维持系统工作原理：在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：

(1)支持表(SL(IN-节点)(OUT-节点))

(2)条件证明(CP(结论)

(IN-假设)

(OUT-假设))非单调性推理MachineIntelligence非单调推理系统：正确性维持系统工作原理：

(1)支持表(SL(IN-节点)(OUT-节点))

-如果某个结论中所有IN节点表中提到的节点当前都是IN，且在OUT节点表中提到的节点当前都是OUT，那么该结论当前是有效的。例：a.现在是冬天(SL()())

b.天气是寒冷的(SL(a)())非单调性推理MachineIntelligence非单调推理系统：正确性维持系统工作原理：

(2)条件证明(CP(结论)

(IN-假设)

(OUT-假设))条件证明可以表示出现矛盾的原因，一个矛盾存在是该表中的理由所致。非单调性推理MachineIntelligence非单调推理系统：正确性维持系统工作原理：

(2)条件证明

例：a.日期（会议）=星期三（SL()(b))b.日期（会议）≠星期三

非单调性推理c.时刻（会议）=14:00(SL(h,j,k)())d.矛盾(SL(a,c)())e.不相容(CP(a,c)())SL((e)())MachineIntelligence消解原理

-子句集的求取

-消解推理

-消解反演产生式系统

-产生式系统的组成

-产生式系统的推理总结MachineIntelligence作业已知：规则1：任何人的兄弟不是女性；规则2：任何人的姐妹必是女性；事实：Mary