Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,Click to edit Master title style,,,,,,Artificial Intelligence (AI),人工智能,第二章：知识表示与推理,内容提要,,第二章：知识表示与推理,,1.,推理的基本概念,,2.,搜索策略,,3.,自然演绎推理,,4.,消解演绎推理,,5.,基于规则的演绎推理,,二、确定性推理,基于规则的演绎推理,规则演绎系统,,规则正向演绎系统,,规则逆向演绎系统,,规则双向演绎系统,,规则逆向演绎系统,规则逆向演绎推理过程：,,规则逆向演绎推理过程是从待证明的问题，即目标公式的与,/,或树出发，通过逆向地使用蕴含式（,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→L,1,∧L,2,时，则可化件为两条规则,W→L,1,和,W→L,2,进行处理已知事实的表示形式,已知事实的表示形式,,反向演绎系统的事实表达式限制为,文字,合取形式，如：,,,F,1,∧F,2,∧ …∧F,n,,其中，每个,F,i,（,i=1,2,…,n,）都为,单文字,，且都可单独起作用，因此可表示为如下集合形式,,,{ F,1,，,F,2,，,…,，,F,n,},规则逆向演绎推理过程,规则逆向演绎推理,,从目标公式的与,/,或树出发，通过运用,B,规则最终得到了某个终止在事实节点上的,一致解图,，推理就可成功结束,,推理过程,,1,）首先用与,/,或树把目标公式表示出来；,,2,）用,B,规则的右部和与,/,或树的叶节点进行匹配，并将匹配成功的,B,规则加入到与,/,或树中；,,3,）重复进行步骤,2,，直到产生某个终止在事实节点上的一致解图为止。
这里的,“一致解图”,是指在推理过程中所用到的,置换应该是一致的,规则逆向演绎推理过程,例：设有如下事实及规则,,事实：,,f,1,: DOG(Fido),Fido,是一只狗,,f,2,:,¬,,BARKS(Fido),Fido,是不叫的,,f,3,: WAGS-TAIL(Fido),Fido,摇尾巴,,f,4,: MEOWS(Myrtle),猫咪的名字叫,Myrtle,规则逆向演绎推理过程,规则：,,r,1,: (WAGS-TAIL(x,1,)∧DOG(x,1,))→ FRIENDLY(x,1,),,,摇尾巴的狗是温顺的狗,,r,2,: (FRIENDLY(x,2,)∧,¬,,BARKS(x,2,))→,¬,,AFRAID(y,2,, x,2,),,温顺又不叫的东西是不值得害怕的,,r,3,: DOG(x,3,)→ANIMAL(x,3,),：,狗为动物,,r,4,: CAT(x,4,)→ANIMAL(x,4,),：,猫为动物,,r,5,: MEOWS(x,5,)→CAT(x,5,),：,猫咪是猫,,规则逆向演绎推理过程,问题：,,是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗？,,该问题的目标公式为：,,(,∃,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(x,5,),MEOWS(x),MEOWS(Myrtle,),DOG(Fido,),¬AFRAID(y,2,,x,2,),¬BARKS(y),¬BARKS(Fido),FRIENDLY(y),FRIENDLY(x,1,),WAGS-TAIL(y),DOG(y),WAGS-TAIL(Fido),DOG(Fido),,,,,,,,,{,Fido/y,},{,x,5,/x,},{y,2,/x , x,2,/y},r,5,r,2,r,1,{,Myrtle/x,},{,Fido/y,},{x,1,/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.,搜索策略,,3.,自然演绎推理,,4.,消解演绎推理,,5.,基于规则的演绎推理,,二、确定性推理,,6.,产生式系统推理,产生式系统,产生式表示法,,事实的表示,,确定性知识，事实可用如下三元组表示：,,（对象，属性，值）,或,（关系，对象,1,，对象,2,）,,如,:,（雪，颜色，白）,或,（热爱，王峰，祖国）,,非确定性知识，事实可用如下四元组表示：,,（对象，属性，值，可信度因子）,,其中，“可信度因子”是指该事实为真的相信程度可用,[0,1],之间的一个实数来表示产生式系统,产生式表示法,,规则的表示：,P,→,Q,或者,IF P THEN Q,,P,是产生式的前提，也称为前件，它给出了该产生式可否使用的先决条件，由,事实的逻辑组合,来构成。
Q,是一组结论或操作，也称为产生式的后件，它指出当前题,P,满足时，应该推出的,结论,或应该,执行的动作,产生式的含义：,如果前提,P,满足，则可推出结论,Q,或执行,Q,所规定的操作,产生式系统,产生式与蕴涵式的主要区别：,,(1),蕴涵式表示的知识只能是精确的，产生式表示的知识可以是不确定的2),蕴含式的匹配一定要求是精确的，而产生式的匹配可以是不确定的产生式与条件语句的主要区别：,,(1),前件结构不同：产生式的前件可以是一个复杂的结构，而程序设计语言中条件语句的左部是布尔表达式2),控制流程不同：产生式系统中满足前提条件的规则被激活后，不一定被立即执行，能否执行将取决于冲突消解策略，而条件语句严格执行产生式系统,产生式系统的基本结构,控制策略,产生式规则,总数据库,总数据库：,存放求解问题的各种当前信息，如：问题的初始状态，输入的事实，中间结论及最终结论等推理过程中，当规则库中某条规则的前提可以和总数据库的已知事实匹配时，该规则被激活，由它推出的结论将被作为新的事实放入总数据库，成为后面推理的已知事实产生式规则：,是一个规则库，也称知识库,,用于存放与求解问题有关的,所有规则的集合,.,产生式系统,产生式系统的基本结构,控制策略,产生式规则,总数据库,控制策略：,亦称推理机，用于控制整个产生式系统的运行，,决定,问题求解过程的,推理线路,。
控制系统的主要任务包括：,,选择匹配,,冲突消解,,执行操作,,终止推理,,路径解释,产生式系统,产生式系统的推理,,正向推理：,从一组表示事实的谓词或命题出发，使用一组,产生式规则,，用以证明该谓词公式或命题是否成立设有规则集合,R,1,至,R,3,,R,1,：,P,1,,→ P,2,,,R,2,：,P,2,,→ P,3,,,R,3,：,P,3,,→ P,4,,,正向推理过程,,,,已知,,,P,1,P,2,P,3,推出,,,P,4,规则,3,规则,2,规则,1,产生式系统,产生式系统的推理,,逆向推理：,从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先,提出,一批假设目标，然后逐一,验证,这些假设逆向推理过程,产生式系统,产生式系统的推理,,双向推理：,双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的,某个步骤,，,实现,事实与目标的,匹配,双向推理过程,产生式系统,产生式系统的例子：,动物识别系统,,该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这,6,种动物其规则库包含如下,15,条规则：,,r,1,: IF,该动物有毛发,THEN,该动物是哺乳动物,,r,2,: IF,该动物有奶,THEN,该动物是哺乳动物,,r,3,: IF,该动物有羽毛,THEN,该动物是鸟,,r,4,: IF,该动物会飞,AND,会下蛋,THEN,该动物是鸟,,r,5,: IF,该动物吃肉,THEN,该动物是食肉动物,,r,6,: IF,该动物有犬齿,AND,有爪,AND,眼盯前方,,,THEN,该动物是食肉动物,产生式系统,产生式系统的例子：,动物识别系统,,r,7,: IF,该动物是哺乳动物,AND,有蹄,THEN,该动物是有蹄类动物,,r,8,: IF,该动物是哺乳动物,AND,是嚼反刍动物,THEN,该动物是有蹄类动物,,r,9,: IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐,AND,身上有暗斑点,THEN,该动物是金钱豹,,r,10,: IF,该动物是哺乳动物,AND,是食肉动物,AND,是黄褐色,AND,身上有黑色条纹,THEN,该动物是虎,,r,11,: IF,该动物是有蹄类动物,AND,有长脖子,AND,有长腿,AND,身上有暗斑点,THEN,该动物是长颈鹿,,产生式系统,产生式系统的例子：,动物识别系统,,r,12,: IF,动物是有蹄类动物,AND,身上有黑色条纹,THEN,该动物是斑马,,r,13,: IF,该动物是鸟,AND,有长脖子,AND,有长腿,AND,不会飞,AND,有黑白二色,THEN,该动物是鸵鸟,,r,14,: IF,该动物是鸟,AND,会游泳,AND,不会飞,AND,有黑白二色,THEN,该动物是企鹅,,r,15,: IF,该动物是鸟,AND,善飞,THEN,该动物是信天翁,,初始总数据库包含的事实有：,,动物有暗斑点，有长脖子，有长腿，有奶，有蹄,产生式系统,该例子的部分推理网络如下：,,长颈鹿,斑马,长脖子,长腿,暗斑点,有蹄类,黑条纹,有蹄,哺乳动物,有毛,r,2,r,7,r,11,r,12,有奶,r,1,图中最上层的结点称为“假设”或“结论”,,中间结点称为“中间假设”；,,终结点称为“证据”或“事实”；,产生式系统,产生式系统的主要优点,,自然性：,采用“如果,……,，则,……”,的形式，人类的判断性知识基本一致。
模块性：,规则是规则库中最基本的知识单元，各规则之间只能通过总数据库发生联系，而不能相互调用，从而增加了规则的模块性有效性：,产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，既有利于表示启发性知识，又有利于表示过程性知识产生式系统,产生式系统的主要缺点,,效率较低：,各规则之间的联系必须以总数据库为媒介并且，其求解过程是一种反复进行的“匹配,—,冲突消解,—,执行”过程这样的执行方式将导致执行的低效率不便于表示结构性知识：,由于产生式表示中的知识具有一致格式，且规则之间不能相互调用，因此那种具有结构关系或层次关系的知识则很难以自然的方式来表示问题？,。