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

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理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))∨¬S(y))¬P(f(z))Q(f(y),y)∧(¬R(f(y))∨¬S(y))Q(f(y),y)¬R(f(y))∨¬S(y)¬R(f(y))¬S(y)若把叶节点用它们之间的合取及析取关系连接起来，就可得到原目标公式的三个子目标：¬P(f(z))；Q(f(y),y)∧¬R(f(y))；Q(f(y),y)∧¬S(y)子目标是文字的合取式西安电子科技大学B规则的表示形式B规则的表示形示形式W→L其中，前项W为任一与/或形公式，后项L为一单文字。这里要求B规则的右边为文字，是因为推理时要用它与目标与或树中的叶节点进行匹配（合一），而目标与或树中的叶节点是文字。如果已知的B规则不是要求的形式，可用与转化F规则类似的方法把它转化为规定的形式。特别地，当B规则为W→L1∧L2时，则可化件为两条规则W→L1和W→L2进行处理。西安电子科技大学已知事实的表示形式已知事实的表示形式反向演绎系统的事实表达式限制为文字合取形式，如：F1∧F2∧…∧Fn其中，每个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)用逆向推理求解该问题的演绎过程如下图所示：西安电子科技大学规则逆向演绎推理过程CAT(x)∧DOG(y)∧¬AFRAID(x,y)CAT(x)DOG(y)¬AFRAID(x,y)CAT(x5)MEOWS(x)MEOWS(Myrtle)DOG(Fido)¬AFRAID(y2,x2)¬BARKS(y)¬BARKS(Fido)FRIENDLY(y)FRIENDLY(x1)WAGS-TAIL(y)DOG(y)WAGS-TAIL(Fido)DOG(Fido){Fido/y}{x5/x}{y2/x,x2/y}r5r2r1{Myrtle/x}{Fido/y}{x1/y}{Fido/y}该图有8条匹配弧，每条弧上都有一置换。其中终止在事实节点上的置换为{Myrtle/x}和{Fido/y}。把它们应用到目标公式，就得到该问题的解：CAT({Myrtle}∧DOG(Fido)∧¬AFRAID({Myrtle,Fido}西安电子科技大学基于规则的演绎推理规则演绎系统规则正向演绎系统规则逆向演绎系统规则双向演绎系统西安电子科技大学规则双向演绎系统规则双向演绎系统与/或形正向演绎推理要求目标公式是文字的析取（目标公式用子句表示，每一个子句是文字的析取）与/或形逆向演绎推理要求事实公式是文字的合取正向和逆向的演绎推理都存在一定的局限性。为了克服这些局限，充分发挥各自的长处，可进行双向演绎推理。西安电子科技大学规则双向演绎系统与/或形双向演绎推理是建立在正向演绎推理和逆向演绎推理基础上的，它由表示目标及表示一直事实的两个与/或树结构组成，这些与/或树分别由正向演绎的F规则和逆向演绎的B规则进行操作，并且仍然限制F规则为单文字的左部，B规则为单文字的右部。双向演绎推理的难点在于终止条件，只有当正向和逆向推理的与/或树对应的叶节点都可合一时，推理才能结束。其时机与判断都难于掌握。更实用化的方式是将复杂的问题求解任务划分为相对简单的若干子任务，然后根据子任务的特点选用正向或逆向演绎推理方式，以便充分发挥两种方式各自的优势。西安电子科技大学内容提要第三章：确定性推理1.推理的基本概念2.搜索策略3.自然演绎推理4.归结演绎推理5.基于规则的演绎推理6.产生式系统西安电子科技大学产生式系统产生式表示法事实的表示确定性知识，事实可用如下三元组表示：–（对象，属性，值）或（关系，对象1，对象2）–如:（雪，颜色，白）或（热爱，王峰，祖国）非确定性知识，事实可用如下四元组表示：–（对象，属性，值，可信度因子）–其中，“可信度因子”是指该事实为真的相信程度。可用[0,1]之间的一个实数来表示。西安电子科技大学产生式系统产生式表示法规则的表示：P→Q或者IFPTHENQP是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成。Q是一组结论或操作，也称为产生式的后件，它指出当前题P满足时，应该推出的结论或应该执行的动作。产生式的含义：如果前提P满足，则可推出结论Q或执行Q所规定的操作西安电子科技大学产生式系统产生式与蕴涵式的主要区别：(1)蕴涵式表示的知识只能是精确的，产生式表示的知识可以是不确定的。(2)蕴含式的匹配一定要求是精确的，而产生式的匹配可以是不确定的。产生式与条件语句的主要区别：(1)前件结构不同：产生式的前件可以是一个复杂的的结构，而程序设计语言中条件语句的左部是布尔表达式。(2)控制流程不同：产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于冲突消解策略，而条件语句严格执行。西安电子科技大学产生式系统产生式系统的基本结构控制策略产生式规则总数据库总数据库：存放求解问题的各种当前信息，如：问题的初始状态，输入的事实，中间结论及最终结论等。推理过程中，当规则库中某条规则的前提可以和总数据库的已知事实匹配时，该规则被激活，由它推出的结论将被作为新的事实放入总数据库，成为后面推理的已知事实。产生式规则：是一个规则库，也称知识库。用于存放与求解问题有关的所有规则的集合西安电子科技大学产生式系统产生式系统的基本结构控制策略产生式规则总数据库控制策略：亦称推理机，用于控制整个产生式系统的运行，决定问题求解过程的推理线路。控制系统的主要任务包括：选择匹配冲突消解执行操作终止推理路径解释西安电子科技大学产生式系统产生式系统的推理正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。设有规则集合R1至R3R1：P1→P2R2：P2→P3R3：P3→P4P1已知规则1P2规则2P3规则3P4推出正向推理过程西安电子科技大学产生式系统产生式系统的推理逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。P1事实规则1P2规则2P3规则3P4假设目标假设假设结论P4逆向推理过程西安电子科技大学产生式系统产生式系统的推理双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。P1事实规则1P2规则2规则n-2Pn-1假设目标匹配Pn规则n-1双向推理过程西安电子科技大学产生式系统产生式系统的例子：动物识别系统该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这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善飞TH