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

ArtificialIntelligence(AI)

人工智能主讲：戚玉涛Email：qi_yutao@163.com第三章：确定性推理内容提要要第三章：：确定性性推理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该动物是是信天翁翁初始总数数据库包包含的事事实有：：动物有暗暗斑点，