湘潭大学-人工智能课件-确定性推理-part-8.ppt

1、Artificial Intelligence (AI)人工智能人工智能第二章：知识第二章：知识表示与推理表示与推理内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理基于规则的演绎推理规则正向演绎系统规则正向演绎系统规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统规则逆向演绎系统规则逆向演绎推理过程是从待证明的问题，即目标公规则逆向演绎推理过程是从待证明的问题，即目标公式的与式的与/或树出发，通过逆向地使用蕴含式（或树出发，通过逆向地使用蕴含式（B规则）

2、，规则），对目标公式的与对目标公式的与/或树进行变换，直到得出包含已知事或树进行变换，直到得出包含已知事实的终止条件为止。实的终止条件为止。目标公式的表示：与目标公式的表示：与/或形变换，与或形变换，与/或树表示或树表示 B规则的表示形式规则的表示形式已知事实的表示形式已知事实的表示形式规则逆向演绎推理过程规则逆向演绎推理过程目标公式的与/或形变换v在与在与/或形逆向演绎推理中，要求或形逆向演绎推理中，要求目标公式采用与目标公式采用与/或形表示或形表示，其化简采用与正向系统中对事实表达，其化简采用与正向系统中对事实表达式处理的式处理的对偶形式。对偶形式。要用要用存在量词存在量词约束变元的约束变

3、元的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) 关于为何需用对

4、偶方式消去量词，这里不作形式证明，仅关于为何需用对偶方式消去量词，这里不作形式证明，仅通过与消解反演方法作对比来加以直观说明：通过与消解反演方法作对比来加以直观说明：在消解反演在消解反演中，需将目标公式取反，存在量词约束变量就成为全称量中，需将目标公式取反，存在量词约束变量就成为全称量词约束变量。词约束变量。 目标公式的与/或树表示v目标公式的与目标公式的与/或形也可用与或形也可用与/或树表示出来，其表或树表示出来，其表示方法与正向演绎推理中事实的与或树表示略有示方法与正向演绎推理中事实的与或树表示略有不同：不同：子表达式之间的子表达式之间的析取析取关系用单一连接符连接，关系用单一连接符连接，

5、表示为表示为或或的关系；的关系；子表达式之间的子表达式之间的合取合取关系则用关系则用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)若把叶节点用它们之间的合若把叶节点用它们之间的合取及析取关系连接起来，就取及析取关系连接起来，就可得到原目标公式的三个子可得到原目标公式的三个子目标：目标

6、： P(f(z)； Q(f(y), y) R(f(y)； Q(f(y), y) S(y)B规则的表示形式 WL其中，前项其中，前项W为任一为任一与与/或形公式或形公式，后项，后项 L为一为一单文字单文字。这里要求这里要求B规则的右边为文字，是因为推理时要用它与规则的右边为文字，是因为推理时要用它与目标与或树中的叶节点进行匹配（合一），而目标与或目标与或树中的叶节点进行匹配（合一），而目标与或树中的叶节点是文字。树中的叶节点是文字。如果已知的如果已知的B规则不是要求的形式，可用与转化规则不是要求的形式，可用与转化F规则类规则类似的方法把它转化为规定的形式。似的方法把它转化为规定的形式。特别地，当

7、特别地，当B规则为规则为WL1L2时，则可化件为两条规时，则可化件为两条规则则WL1和和WL2进行处理。进行处理。已知事实的表示形式反向演绎系统的事实表达式限制为反向演绎系统的事实表达式限制为文字文字合取形合取形式，如：式，如： F1F2 Fn其中，每个其中，每个Fi（i=1,2,n）都为）都为单文字单文字，且都，且都可单独起作用，因此可表示为如下集合形式可单独起作用，因此可表示为如下集合形式 F1，F2， ，Fn 规则逆向演绎推理过程从目标公式的与从目标公式的与/或树出发，通过运用或树出发，通过运用B规则最终得到了规则最终得到了某个终止在事实节点上的某个终止在事实节点上的一致解图一致解图，推

8、理就可成功结束，推理就可成功结束1）首先用与）首先用与/或树把目标公式表示出来；或树把目标公式表示出来；2）用）用B规则的右部和与规则的右部和与/或树的叶节点进行匹配，并将匹或树的叶节点进行匹配，并将匹配成功的配成功的B规则加入到与规则加入到与/或树中；或树中；3）重复进行步骤）重复进行步骤2，直到产生某个终止在事实节点上的，直到产生某个终止在事实节点上的一致解图为止。这里的一致解图为止。这里的“一致解图一致解图”是指在推理过程中是指在推理过程中所用到的所用到的置换应该是一致的置换应该是一致的。规则逆向演绎推理过程p f1: DOG(Fido) Fido是一只狗是一只狗p f 2: BARKS

9、(Fido) Fido是不叫的是不叫的p f 3: WAGS-TAIL(Fido) Fido摇尾巴摇尾巴p f 4: MEOWS(Myrtle) 猫咪的名字叫猫咪的名字叫Myrtle规则逆向演绎推理过程pr1: (WAGS-TAIL(x1)DOG(x1) FRIENDLY(x1) 摇尾巴的狗是温顺的狗摇尾巴的狗是温顺的狗pr2: (FRIENDLY(x2) BARKS(x2) AFRAID(y2, x2) 温顺又不叫的东西是不值得害怕的温顺又不叫的东西是不值得害怕的pr3: DOG(x3)ANIMAL(x3) ：狗为动物狗为动物 pr4: CAT(x4)ANIMAL(x4)：猫为动物猫为动物p

10、r5: MEOWS(x5)CAT(x5)：猫咪是猫猫咪是猫规则逆向演绎推理过程p是否存在这样的一只猫和一条狗，使得这只猫不害怕是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗？这只狗？p该问题的目标公式为：该问题的目标公式为： (x) (y) (CAT(x)DOG(y)AFRAID(x, y)p改目标公式经变换后得到改目标公式经变换后得到 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(y

11、2,x2)BARKS(y)BARKS(Fido)FRIENDLY(y)FRIENDLY(x1)WAGS-TAIL(y)DOG(y)WAGS-TAIL(Fido)DOG(Fido)Fido/yx5/xy2/x , x2/yr5r2r1Myrtle/xFido/yx1/yFido/y 该图有该图有8条匹配弧，每条弧上都有条匹配弧，每条弧上都有一置换。其中一置换。其中终止在事实节点上的置终止在事实节点上的置换为换为Myrtle/x和和Fido/y。把它们应把它们应用到目标公式，就得到该问题的解：用到目标公式，就得到该问题的解： CAT(MyrtleDOG(Fido)AFRAID(Myrtle, Fi

12、do基于规则的演绎推理规则正向演绎系统规则正向演绎系统规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统规则双向演绎系统与与/ /或形正向演绎推理要求或形正向演绎推理要求目标公式是文字的析目标公式是文字的析取取（目标公式用子句表示，每一个子句是文字（目标公式用子句表示，每一个子句是文字的析取）的析取）与与/ /或形逆向演绎推理要求或形逆向演绎推理要求事实公式是文字的合事实公式是文字的合取取正向和逆向的演绎推理都存在一定的局限性。正向和逆向的演绎推理都存在一定的局限性。为了克服这些局限，充分发挥各自的长处，可为了克服这些局限，充分发挥各自的长处，可进行双向演绎推理。进行双向演绎推理

13、。规则双向演绎系统与与/ /或形双向演绎推理是建立在正向演绎推理和逆向演或形双向演绎推理是建立在正向演绎推理和逆向演绎推理基础上的，它由表示绎推理基础上的，它由表示目标目标及表示已知及表示已知事实事实的的两两个与个与/ /或树或树结构组成，这些与结构组成，这些与/ /或树分别由正向演绎的或树分别由正向演绎的F F规则规则和逆向演绎的和逆向演绎的B B规则规则进行操作，并且仍然限制进行操作，并且仍然限制F F规规则为单文字的左部，则为单文字的左部，B B规则为单文字的右部。规则为单文字的右部。双向演绎推理的双向演绎推理的难点在于终止条件难点在于终止条件，只有当正向和逆，只有当正向和逆向推理的与向

14、推理的与/ /或树对应的叶节点都可合一时，推理才能或树对应的叶节点都可合一时，推理才能结束。其时机与判断都难于掌握。结束。其时机与判断都难于掌握。更实用化的方式是将复杂的问题求解任务划分为相对更实用化的方式是将复杂的问题求解任务划分为相对简单的若干子任务，然后根据子任务的特点选用正向简单的若干子任务，然后根据子任务的特点选用正向或逆向演绎推理方式，以便充分发挥两种方式各自的或逆向演绎推理方式，以便充分发挥两种方式各自的优势。优势。内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则

15、的演绎推理6.6.产生式系统产生式系统内容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演绎推理自然演绎推理4.4.消解演绎推理消解演绎推理5.5.基于规则的演绎推理基于规则的演绎推理6.6.产生式系统推理产生式系统推理产生式系统事实的表示事实的表示p确定性知识，事实可用如下三元组表示：确定性知识，事实可用如下三元组表示： （对象，属性，值）（对象，属性，值）或或（关系，对象（关系，对象1，对象，对象2） 如如:（雪，颜色，白）（雪，颜色，白）或或（热爱，王峰，祖国）（热爱，王峰，祖国）p非确定性知识，事实可用如下四元组表示：非确定性知识，事实可用如下四元组表示：

16、 （对象，属性，值，可信度因子）（对象，属性，值，可信度因子） 其中，其中，“可信度因子可信度因子”是指该事实为真的相信程是指该事实为真的相信程度。可用度。可用0,1之间的一个实数来表示。之间的一个实数来表示。 产生式系统规则的表示：规则的表示： PQ 或者或者 IF P THEN QpP是产生式的前提，也称为前件，它给出了该产生是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由式可否使用的先决条件，由事实的逻辑组合事实的逻辑组合来构成。来构成。pQ是一组结论或操作，也称为产生式的后件，它指是一组结论或操作，也称为产生式的后件，它指出当前题出当前题P满足时，应该推出的满足时，应

17、该推出的结论结论或应该或应该执行的动执行的动作作。p产生式的含义：产生式的含义：如果前提如果前提P满足，则可推出结论满足，则可推出结论Q或或执行执行Q所规定的操作所规定的操作产生式系统 (1) 蕴涵式表示的知识只能是精确的，产生式表示的知识可蕴涵式表示的知识只能是精确的，产生式表示的知识可以是不确定的。以是不确定的。 (2) 蕴含式的匹配一定要求是精确的，而产生式的匹配可以蕴含式的匹配一定要求是精确的，而产生式的匹配可以是不确定的。是不确定的。 (1) 前件结构不同：产生式的前件可以是一个复杂的结构，前件结构不同：产生式的前件可以是一个复杂的结构，而程序设计语言中条件语句的左部是布尔表达式。而

18、程序设计语言中条件语句的左部是布尔表达式。 (2) 控制流程不同：产生式系统中满足前提条件的规则被激控制流程不同：产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于冲突消解策略，活后，不一定被立即执行，能否执行将取决于冲突消解策略，而条件语句严格执行。而条件语句严格执行。产生式系统控制策略产生式规则总数据库p 总数据库：总数据库：存放求解问存放求解问题的各种当前信息，如：题的各种当前信息，如：问题的初始状态，输入的问题的初始状态，输入的事实，中间结论及最终结事实，中间结论及最终结论等。论等。p 推理过程中，当规则库推理过程中，当规则库中某条规则的前提可以和中某条规则的前

19、提可以和总数据库的已知事实匹配总数据库的已知事实匹配时，该规则被激活，由它时，该规则被激活，由它推出的结论将被作为新的推出的结论将被作为新的事实放入总数据库，成为事实放入总数据库，成为后面推理的已知事实。后面推理的已知事实。p 产生式规则：产生式规则：是一个规则库，也称知识是一个规则库，也称知识库库 。用于存放与求解问题有关的。用于存放与求解问题有关的所有规则所有规则的集合的集合.产生式系统控制策略产生式规则总数据库p 控制策略：控制策略：亦称推理亦称推理机，用于控制整个产生机，用于控制整个产生式系统的运行，式系统的运行，决定决定问问题求解过程的题求解过程的推理线路推理线路。p 控制系统的主要

20、任务控制系统的主要任务包括：包括： 选择匹配选择匹配 冲突消解冲突消解 执行操作执行操作 终止推理终止推理 路径解释路径解释产生式系统正向推理：正向推理：从一组表示事实的谓词或命题出发，使从一组表示事实的谓词或命题出发，使用一组用一组产生式规则产生式规则，用以证明该谓词公式或命题是否，用以证明该谓词公式或命题是否成立。成立。设有规则集合设有规则集合R1至至R3p R1：P1 P2 p R2：P2 P3 p R3：P3 P4 正向推理过程正向推理过程已知已知 P1P2P3推出推出 P4规则规则3规则规则2规则规则1产生式系统逆向推理：逆向推理：从表示目标的谓词或命题出发，使用一从表示目标的谓词或

21、命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先组产生式规则证明事实谓词或命题成立，即首先提出提出一批假设目标，然后逐一一批假设目标，然后逐一验证验证这些假设。这些假设。 逆向推理过程逆向推理过程产生式系统双向推理：双向推理：双向推理的推理策略是同时从目标向事双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的实推理和从事实向目标推理，并在推理过程中的某个某个步骤步骤，实现实现事实与目标的事实与目标的匹配匹配。双向推理过程双向推理过程产生式系统动物识别系统动物识别系统该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅

22、、信天翁这信天翁这6种动物。种动物。其规则库包含如下其规则库包含如下15条规则：条规则：p r1: IF 该动物有毛发该动物有毛发 THEN 该动物是哺乳动物该动物是哺乳动物 p r2: IF 该动物有奶该动物有奶 THEN 该动物是哺乳动物该动物是哺乳动物p r3: IF 该动物有羽毛该动物有羽毛 THEN 该动物是鸟该动物是鸟p r4: IF 该动物会飞该动物会飞 AND 会下蛋会下蛋 THEN 该动物是鸟该动物是鸟p r5: IF 该动物吃肉该动物吃肉 THEN 该动物是食肉动物该动物是食肉动物p r6: IF 该动物有犬齿该动物有犬齿 AND 有爪有爪 AND 眼盯前方眼盯前方 THE

23、N 该动物是食肉动物该动物是食肉动物产生式系统动物识别系统动物识别系统pr7: IF 该动物是哺乳动物该动物是哺乳动物 AND 有蹄有蹄 THEN 该动物是有蹄类该动物是有蹄类动物动物pr8: IF 该动物是哺乳动物该动物是哺乳动物 AND 是嚼反刍动物是嚼反刍动物 THEN 该动物是该动物是有蹄类动物有蹄类动物pr9: IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐是黄褐AND 身上有暗斑点身上有暗斑点 THEN 该动物是金钱豹该动物是金钱豹pr10: IF 该动物是哺乳动物该动物是哺乳动物 AND 是食肉动物是食肉动物 AND 是黄褐色是黄褐色 AND

24、 身上有黑色条纹身上有黑色条纹 THEN 该动物是虎该动物是虎pr11: IF 该动物是有蹄类动物该动物是有蹄类动物 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 身上有暗斑点身上有暗斑点 THEN 该动物是长颈鹿该动物是长颈鹿产生式系统动物识别系统动物识别系统pr12: IF 动物是有蹄类动物动物是有蹄类动物 AND 身上有黑色条纹身上有黑色条纹 THEN 该动物该动物是斑马是斑马pr13: IF 该动物是鸟该动物是鸟 AND 有长脖子有长脖子 AND 有长腿有长腿 AND 不会不会飞飞 AND 有黑白二色有黑白二色 THEN 该动物是鸵鸟该动物是鸵鸟pr14: IF 该动物是鸟该

25、动物是鸟 AND 会游泳会游泳 AND 不会飞不会飞 AND 有黑白有黑白二色二色THEN 该动物是企鹅该动物是企鹅pr15: IF 该动物是鸟该动物是鸟 AND 善飞善飞 THEN 该动物是信天翁该动物是信天翁 初始总数据库包含的事实有：初始总数据库包含的事实有：p 动物有暗斑点，有长脖子，有长腿，有奶，有蹄动物有暗斑点，有长脖子，有长腿，有奶，有蹄产生式系统该例子的部分推理网络如下：该例子的部分推理网络如下：长颈鹿长颈鹿斑马斑马长脖子长脖子长腿长腿暗斑点暗斑点有蹄类有蹄类黑条纹黑条纹有蹄有蹄哺乳动物哺乳动物有毛有毛r2r7r11r12有奶有奶r1p图中最上层的结点称为图中最上层的结点称为“

26、假设假设”或或“结论结论”p中间结点称为中间结点称为“中间假中间假设设”；p终结点称为终结点称为“证据证据”或或“事实事实”；产生式系统自然性：自然性：采用采用“如果如果，则，则”的形式，人类的形式，人类的判断性知识基本一致。的判断性知识基本一致。模块性：模块性：规则是规则库中最基本的知识单元，各规规则是规则库中最基本的知识单元，各规则之间只能通过总数据库发生联系，而不能相互调则之间只能通过总数据库发生联系，而不能相互调用，从而增加了规则的模块性。用，从而增加了规则的模块性。有效性：有效性：产生式知识表示法既可以表示确定性知识，产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，既有

27、利于表示启发性知又可以表示不确定性知识，既有利于表示启发性知识，又有利于表示过程性知识。识，又有利于表示过程性知识。产生式系统效率较低：效率较低：各规则之间的联系必须以总数据库为媒各规则之间的联系必须以总数据库为媒介。并且，其求解过程是一种反复进行的介。并且，其求解过程是一种反复进行的“匹配匹配冲突消解冲突消解执行执行”过程。这样的执行方式将导致执过程。这样的执行方式将导致执行的低效率。行的低效率。不便于表示结构性知识：不便于表示结构性知识：由于产生式表示中的知识由于产生式表示中的知识具有一致格式，且规则之间不能相互调用，因此那具有一致格式，且规则之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自然的种具有结构关系或层次关系的知识则很难以自然的方式来表示。方式来表示。