西电人工智能确定性推理ar5

ArtificialIntelligence(AI)

人工智能主讲：戚玉涛Email：第三章：确定性推理内容提要第三章：确定性推理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或者IFPTHENQP是产生式的前前提，也称为为前件，它给给出了该产生生式可否使用用的先决条件件，由事实的逻辑组组合来构成。Q是一组结论或或操作，也称称为产生式的的后件，它指指出当前题P满足时，应该该推出的结论或应该执行的动作。产生式的含义义：如果前提P满足，则可推推出结论Q或执行Q所规定的操作作产生式系统产生式与蕴涵涵式的主要区区别：(1)蕴涵式表示的的知识只能是是精确的，产产生式表示的的知识可以是是不确定的。。(2)蕴含式的匹配配一定要求是是精确的，而而产生式的匹匹配可以是不不确定的。产生式与条件件语句的主要要区别：(1)前件结构不同同：产生式的的前件可以是是一个复杂的的的结构，而而程序设计语语言中条件语语句的左部是是布尔表达式式。(2)控制流程不同同：产生式系系统中满足前前提条件的规规则被激活后后，不一定被被立即执行，，能否执行将将取决于冲突突消解策略，，而条件语句句严格执行。。产生式系统产生式系统的的基本结构控制策略产生式规则总数据库总数据库：存放求解问题题的各种当前前信息，如：：问题的初始始状态，输入入的事实，中中间结论及最最终结论等。。推理过程中，，当规则库中中某条规则的的前提可以和和总数据库的的已知事实匹匹配时，该规规则被激活，，由它推出的的结论将被作作为新的事实实放入总数据据库，成为后后面推理的已已知事实。产生式规则：：是一个规则库库，也称知识识库。用于存放与与求解问题有有关的所有规规则的集合产生式系统产生式系统的的基本结构控制策略产生式规则总数据库控制策略：亦称推理机，，用于控制整整个产生式系系统的运行，，决定问题求求解过程的推推理线路。控制系统的主主要任务包括括：选择匹配冲突消解执行操作终止推理路径解释产生式系统产生式系统的的推理正向推理：从一组表示事事实的谓词或或命题出发，，使用一组产产生式规则，，用以证明该该谓词公式或或命题是否成成立。设有规则集合合R1至R3R1：P1→P2R2：P2→P3R3：P3→P4正向推推理过过程产生式式系统统产生式式系统统的推推理逆向推推理：：从表示示目标标的谓谓词或或命题题出发发，使使用一一组产产生式式规则则证明明事实实谓词词或命命题成成立，，即首首先提提出一一批假假设目目标，，然后后逐一一验证证这些些假设设。逆向推推理过过程产生式式系统统产生式式系统统的推推理双向推推理：：双向推推理的的推理理策略略是同同时从从目标标向事事实推推理和和从事事实向向目标标推理理，并并在推推理过过程中中的某某个步步骤，，实现现事实实与目目标的的匹配配。双向推推理过过程产生式式系统统产生式式系统统的例例子：：动物识识别系系统该系统统可以以识别别老虎虎、金金钱豹豹、斑斑马、、长颈颈鹿、、企鹅鹅、信信天翁翁这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该动物是是信天翁翁初始总数数据库包包含的事事实有：：动物有暗暗斑点，，有长脖脖子，有有长腿