西电人工智能15确定性推理part8

ArtificialIntelligence(AI)人工智能,主讲：戚玉涛,Email：qi_yutao,第三章：确定性推理,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,6.产生式系统,基于规则的演绎推理,规则演绎系统规则正向演绎系统规则逆向演绎系统规则双向演绎系统,规则逆向演绎系统,规则逆向演绎推理过程：规则逆向演绎推理过程是从待证明的问题，即目标公式的与/或树出发，通过逆向地使用蕴含式（B规则），对目标公式的与/或树进行变换，直到得出包含已知事实的终止条件为止。规则逆向演绎系统目标公式的表示：与/或形变换，与/或树表示B规则的表示形式已知事实的表示形式规则逆向演绎推理过程,目标公式的与/或形变换,在与/或形逆向演绎推理中，要求目标公式采用与/或形表示，其化简采用与正向系统中对事实表达式处理的对偶形式。转化步骤要用存在量词约束变元的Skolem函数来替换由全称量词约束的相应变元，消去全称量词。（隐含着变量受存在量词的约束）再消去存在量词，并进行变元换名，使主析取元之间具有不同的变元名。,目标公式的与/或形变换,例如，有如下目标公式：(y)(x)(P(x)(Q(x)(R(x)S(y)Skolem化后为P(f(y)(Q(f(y),y)(R(f(y)S(y)变元换名后为P(f(z)(Q(f(y),y)(R(f(y)S(y)关于为何需用对偶方式消去量词，这里不作形式证明，仅通过与归结反演方法作对比来加以直观说明：在归结反演中，需将目标公式取反，存在量词约束变量就成为全称量词约束变量。,目标公式的与/或树表示,目标公式的与/或形也可用与/或树表示出来，其表示方法与正向演绎推理中事实的与或树表示略有不同：子表达式之间的析取关系用单一连接符连接，表示称或的关系；子表达式之间的合取关系则用k线连接符连接，表示为与的关系。例如：对上述目标公式的与/或形，可用如下的与/或树表示。,目标公式的与/或树表示,若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标：,P(f(z)；Q(f(y),y)R(f(y)；Q(f(y),y)S(y),子目标是文字的合取式,B规则的表示形式,B规则的表示形示形式WL其中，前项W为任一与/或形公式，后项L为一单文字。这里要求B规则的右边为文字，是因为推理时要用它与目标与或树中的叶节点进行匹配（合一），而目标与或树中的叶节点是文字。如果已知的B规则不是要求的形式，可用与转化F规则类似的方法把它转化为规定的形式。特别地，当B规则为WL1L2时，则可化件为两条规则WL1和WL2进行处理。,已知事实的表示形式,已知事实的表示形式反向演绎系统的事实表达式限制为文字合取形式，如：F1F2Fn其中，每个Fi（i=1,2,n）都为单文字，且都可单独起作用，因此可表示为如下集合形式F1，F2，Fn,规则逆向演绎推理过程,规则逆向演绎推理从目标公式的与/或树出发，通过运用B规则最终得到了某个终止在事实节点上的一致解图，推理就可成功结束推理过程1）首先用与/或树把目标公式表示出来；2）用B规则的右部和与/或树的叶节点进行匹配，并将匹配成功的B规则加入到与/或树中；3）重复进行步骤2，直到产生某个终止在事实节点上的一致解图为止。这里的“一致解图”是指在推理过程中所用到的代换应该是一致的。,规则逆向演绎推理过程,例：设有如下事实及规则事实：f1:DOG(Fido)Fido是一只狗f2:BARKS(Fido)Fido是不叫的f3:WAGS-TAIL(Fido)Fido摇尾巴f4:MEOWS(Myrtle)猫咪的名字叫Myrtle,规则逆向演绎推理过程,规则：r1:(WAGS-TAIL(x1)DOG(x1)FRIENDLY(x1)摇尾巴的狗是温顺的狗r2:(FRIENDLY(x2)BARKS(x2)AFRAID(y2,x2)温顺又不叫的东西是不值得害怕的r3:DOG(x3)ANIMAL(x3)：狗为动物r4:CAT(x4)ANIMAL(x4)：猫为动物r5:MEOWS(x5)CAT(x5)：喵喵叫的是猫,规则逆向演绎推理过程,问题：是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗？该问题的目标公式为：(x)(y)(CAT(x)DOG(y)AFRAID(x,y)改目标公式经变换后得到CAT(x)DOG(y)AFRAID(x,y)用逆向推理求解该问题的演绎过程如下图所示：,规则逆向演绎推理过程,该图有8条匹配弧，每条弧上都有一置换。其中终止在事实节点上的置换为Myrtle/x和Fido/y。把它们应用到目标公式，就得到该问题的解：,CAT(MyrtleDOG(Fido)AFRAID(Myrtle,Fido,基于规则的演绎推理,规则演绎系统规则正向演绎系统规则逆向演绎系统规则双向演绎系统,规则双向演绎系统,规则双向演绎系统与/或形正向演绎推理要求目标公式是文字的析取（目标公式用子句表示，每一个子句是文字的析取）与/或形逆向演绎推理要求事实公式是文字的合取正向和逆向的演绎推理都存在一定的局限性。为了克服这些局限，充分发挥各自的长处，可进行双向演绎推理。,规则双向演绎系统,与/或形双向演绎推理是建立在正向演绎推理和逆向演绎推理基础上的，它由表示目标及表示一直事实的两个与/或树结构组成，这些与/或树分别由正向演绎的F规则和逆向演绎的B规则进行操作，并且仍然限制F规则为单文字的左部，B规则为单文字的右部。双向演绎推理的难点在于终止条件，只有当正向和逆向推理的与/或树对应的叶节点都可合一时，推理才能结束。其时机与判断都难于掌握。更实用化的方式是将复杂的问题求解任务划分为相对简单的若干子任务，然后根据子任务的特点选用正向或逆向演绎推理方式，以便充分发挥两种方式各自的优势。,内容提要,第三章：确定性推理,1.推理的基本概念,2.搜索策略,3.自然演绎推理,4.归结演绎推理,5.基于规则的演绎推理,6.产生式系统,产生式系统,产生式表示法事实的表示确定性知识，事实可用如下三元组表示：（对象，属性，值）或（关系，对象1，对象2）如:（雪，颜色，白）或（热爱，王峰，祖国）非确定性知识，事实可用如下四元组表示：（对象，属性，值，可信度因子）其中，“可信度因子”是指该事实为真的相信程度。可用0,1之间的一个实数来表示。,产生式系统,产生式表示法规则的表示：PQ或者IFPTHENQP是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成。Q是一组结论或操作，也称为产生式的后件，它指出当前题P满足时，应该推出的结论或应该执行的动作。产生式的含义：如果前提P满足，则可推出结论Q或执行Q所规定的操作,产生式系统,产生式与蕴涵式的主要区别：(1)蕴涵式表示的知识只能是精确的，产生式表示的知识可以是不确定的。(2)蕴含式的匹配一定要求是精确的，而产生式的匹配可以是不确定的。产生式与条件语句的主要区别：(1)前件结构不同：产生式的前件可以是一个复杂的的结构，而程序设计语言中条件语句的左部是布尔表达式。(2)控制流程不同：产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于冲突消解策略，而条件语句严格执行。,产生式系统,产生式系统的基本结构,总数据库：存放求解问题的各种当前信息，如：问题的初始状态，输入的事实，中间结论及最终结论等。推理过程中，当规则库中某条规则的前提可以和总数据库的已知事实匹配时，该规则被激活，由它推出的结论将被作为新的事实放入总数据库，成为后面推理的已知事实。,产生式规则：是一个规则库，也称知识库。用于存放与求解问题有关的所有规则的集合,产生式系统,产生式系统的基本结构,控制策略：亦称推理机，用于控制整个产生式系统的运行，决定问题求解过程的推理线路。控制系统的主要任务包括：选择匹配冲突消解执行操作终止推理路径解释,产生式系统,产生式系统的推理正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。设有规则集合R1至R3R1：P1P2R2：P2P3R3：P3P4,正向推理过程,产生式系统,产生式系统的推理逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。,逆向推理过程,产生式系统,产生式系统的推理双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。,双向推理过程,产生式系统,产生式系统的例子：动物识别系统该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物。其规则库包含如下15条规则：r1:IF该动物有毛发THEN该动物是哺乳动物r2:IF该动物有奶THEN该动物是哺乳动物r3:IF该动物有羽毛THEN该动物是鸟r4:IF该动物会飞AND会下蛋THEN该动物是鸟r5:IF该动物吃肉THEN该动物是食肉动物r6:IF该动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物,产生式系统,产生式系统的例子：动物识别系统r7:IF该动物是哺乳动物AND有蹄THEN该动物是有蹄类动物r8:IF该动物是哺乳动物AND是嚼反刍动物THEN该动物是有蹄类动物r9:IF该动物是哺乳动物AND是食肉动物AND是黄褐AND身上有暗斑点THEN该动物是金钱豹r10:IF该动物是哺乳动物AND是食肉动物AND是黄褐色AND身上有黑色条纹THEN该动物是虎r11:IF该动物是有蹄类动物AND有长脖子AND有长腿AND身上有暗斑点THEN该动物是长颈鹿,产生式系统,产生式系统的例子：动物识别系统r12:IF动物是有蹄类动物AND身上有黑色条纹THEN该动物是斑马r13:IF该动物是鸟AND有长脖子AND有长腿AND不会飞AND有黑白二色THEN该动物是鸵鸟r14:IF该动物是鸟AND会游泳AND不会飞AND有黑白二色THEN该动物是企鹅r15:IF该动物是鸟AND善飞THEN该动物是信天翁初始总数据库包含的事实有：动物有暗斑点，有长脖子，有长腿，有奶，有蹄,产生式系统,该例子的部分推理网络如下：,图中最上层的结点称为“假设”或“结论”中间结点称为“中间假设”；终结点称为“证据”或“事实”；,产生式系统,产生式系统的主要优点自然性：采用“如果，则”的形式，人类的判断性知识基本一致。模块性：规则是规则库中最基本的知识单元，各规则之间只能通过总数据库发生联系，而不能相互调用，从而增加了规