2-3第四章高级求解技术

2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案第四章高级求解技术4-1规则演绎系统4-1-1基本概念工作内存：断言集合。规则：由IF…THEN…构成。其中，IF中的断言（Assertion）部分称为前项（Antecedent），THEN部分称为后项（Consequent），用于规定放入工作内存的新断言。这种基于规则的系统称为规则演绎系统（Rulebaseddeductionsystem）。如果THEN部分用于规定某种动作，则称为反应式系统（Reactionsystem）或产生式系统（Productionsystem）。正向推理（Forwardchaining）：从IF向THEN方向进行的推理（从事实出发）。逆向推理（Backwardchaining）：从THEN部分向IF的推理（从结论出发）。4-1-2规则正向演绎系统1.事实表达式的“与或形”变换：将事实表示为非蕴涵形的“与或形”，作为系统的总数据库。即将事实表示为谓词演算公式，而不是化为子句。步骤如下：①用21WW和21WW的关系，消去蕴涵式。②用DeMorgan定律将否定符号移入括号内，直到每个否定符号的辖域只有一个谓词符号为止。③对表达式进行Skolem替换及变成“前束范式”。④对全称量词改名、量词进行标准化、消去存在量词。⑤删除全称量词（则所有余下的量词都是全称量化的）。2.事实表达式的“与或图”表示（实际上是对子句集的简洁表示）例如：将)]},())()([(),()({)((vuSvPvRuvQvu进行“与或形”变换后成为如下形式：)),())()(((),(vASvPvRAwQ。“与或图”表示如图2-3-1。其中，根表示整个事实表达式，叶节点表示基本事实表达式。3.“与或图”的F规则变换（Forward或正向规则变换）目的：应用1条规则到“与或图”时，用规则的后项代替“与或图”中所有与该规则的前项相同的叶子节点（即基本事实节点），可以由新图的叶子节点，很容易地得到全部消解式。从而证明某个目标公式。)),())()(((),(vASvPvRAwQ),(AwQ),())()((vASvPvR)()(vPvR),(vAS)(vR)(vP图2-3-1事实表达式的“与或图/树”表示图示2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案假设：WL中，L是单文字，W是“与或”形的唯一公式。且出现在该蕴涵式中的所有变量都是全称化变量。那么，单文字前项的任何蕴涵式，都可以化为辖域为整个表达式蕴涵形式。例如：)},()()),,())(){(((uxQuzyxPzyx)},()())],,())([((){(uxQuzyxPzyx消去蕴涵)},()()),,())(){(((uxQuzyxPzyx否定移入)},()())),(,,()(){((uxQuyxfyxPyx进行Skolem化),()),(,,(uxQyxfyxP消去全称量词),()),(,,(uxQyxfyxP恢复蕴涵式应用实例：将ZYXS)(规则运用至图2-3-2(a)的S叶节点上成为图2-3-2(b)所示，其中连接两个S的弧线叫“匹配弧”。图2-3-2中，规则ZYXS)(的子句形式为：ZXS和ZYS。原来的事实表达式子句图解集为（如图2-3-2(a)）：{SQP，SR，UTQP，UTR}。运用规则的两个子句对事实表达式子句集合中的S进行消解，从图上很容易获得其消解式的完备集合：{QPZX，QPZY，))(())((UTSRQP图2-3-2(a)不含变量的“与或图”))(RQP)((UTS)(QPRRPS)(UTTU))(())((UTSRQP))(RQP)((UTS)(QPRQPS)(UTTUSYXZXY图2-3-2(b)应用一条WL规则得到的“与或图”2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案从目标事实的操作过程，从THEN到IF的推理过程。ZXR，ZYR}。4.目标公式（终止条件）运用F规则的目的：从事实公式及规则集出发，证明某一个目标公式。方法：①假设用文字集表示目标公式，且该集合各元素都用析取表示。②用目标文字和规则对“与或图”增加后继节点。当目标节点与图中文字节点n上的一个文字相匹配时，则对节点n添加新后继，标记为匹配的目标文字（即成为新的目标节点），并用匹配弧线连接到其父辈节点上去。③当产生式系统产生一个“与或图”，并且包含一个图解时，系统结束。终止条件：当正向演绎系统产生了一个包含有以目标节点作为终止的解图时，系统就成功地终止。例如：事实：BA规则：DCA，GEB目标：DC规则的子句析取形式集：{CA，DA，EB，GB}图2-3-3终止条件的“与或图”形成过程：①事实节点BA及其或分支文字节点A和B；②A和B分别和两个规则都有相匹配的文字，所以，在A和B之后分别添加以规则为基础的后继节点},{DC和},{GE。③其中的C，D分别和目标匹配。系统结束。目标的否定：},{)(DCDCGC图2-3-4目标公式的反演求证过程：)(BAABABCDCEGG目标节点图2-3-3满足终止条件的“与或图”NILBBAACABGGBG图2-3-4用消解反演求证目标公式的图解规则：DCAGEB匹配弧线BGBG},{ACAC},{BBANIL2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案4-1-3规则逆向演绎系统1.目标表达式的“与或”形式将目标公式化为“与或”形或“与或图”（消去蕴涵，否定移入，量词处理等）如：)))}()((),(()(){)((ySxPyxQxPxy化成：)))())((()),((())((ySyfRyyfQyfP，然后，作变量分离标准化：)))())((()),((())((ySyfRyyfQzfP注1：逆向推理中的“与或图”之K线连接符的目的是用来表达合取关系的。注2：根节点的任一后裔叫做子目标节点，相应的表达式称做子目标。注3：目标公式的子句集合可从“与或图”中得到，即叶节点上文字的合取。如上图的结果如下：)}()),(()),(()),(()),(({ySyyfQyfRyyfQzfP2.“与或图”B规则变换（Backward或逆向规则变换）与F规则变换相比，变成LW形式。同时，对)21(LLW，将其化为两条规则，即1LW和2LW。3.事实节点的一致解图（终止条件）假设：事实表达式均为文字的合取形；当一个文字与“与或图”的文字节点匹配时，可将其后裔事实节点加入“与或图”中去，并将该事实节点与匹配的子目标用mgu弧连接起来；同一事实可以多次重复使用。终止条件：推理形成的“与或图”包含某个终止在事实节点上的一致解图。例假定问题描述如下：事实：F1---)(FIDODOGF2---)(FIDOBARKSF3---)(FIDOTAILWAGSF4---)(MYRTLEMEOWS规则：R1---)1())1()1((xFRIENDLYxDOGxTAILWAGS)))())((()),((())((ySyfRyyfQzfP))((zfP))())((()),((ySyfRyyfQ)),(((yyfQ))())((ySyfR))((yfR))(yS图2-3-5目标公式的“与或图”表示实例2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案R2---)2,2())2()2((xyAFRAIDxBARKSxFRIENDLYR3---)3()3(xANIMALxDOGR4---)4()4(xANIMALxCATR5---)5()5(xCATxMEOWS问题：是否有一只猫不怕一条狗？即)),()()()()((yxAFRAIDyDOGxCATyx求解过程：事实节点、匹配弧以及匹配弧上的置换过程如图2-3-6所示。最后，通过将终止在所有事实节点前的置换（即}/{xMYRTLE和}/{yFIDO）运用到目标表达式（待求解问题的表示式）即可得到问题的一个一致解答如下：)),()()((FIDOMYRTLEAFRAIDFIDODOGMYRTLECAT4-1-4规则双向演绎推理引入原因：正向演绎推理中，THEN表达式为文字析取之组合，逆向演绎推理中，IF的表达式只能为文字的合取之组合。双向演绎推理希望结合两者，使得演绎的事实和规则的表达形式不受约束。主要困难：演绎终止条件的确定。4-2产生式系统（ProductionSystem）（基于规则的系统),()()(yxAFRAIDyDOGxCAT)(xCAT)5(xCAT)(xMEOWS)(MYRTLEMEOWS)(yDOG)(FIDODOG),(yxAFRAID)2,2(xyAFRAID)(yBARKS)(yFRIENDLY)(FIDOBARKS)1(xFRIENDLY)(yTAILWAGS)(yDOG)(FIDOTAILWAGS)(FIDODOG{x/x5}R5{MYRTLE/x}{FIDO/y}{x/y2,y/x2}{FIDO/y}{FIDO/y}{FIDO/y}{y/x1}R2R1匹配弧或者mgu弧图2-3-6逆向推理系统的一个一致解图事实节点注：每条匹配都有一个置换2006-2007年度第1学期信息与计算科学专业2003级5班《人工智能》教案----详案谓词表达形式不同，如：MAN(ZHAO-LING)~WOMAN(ZHAO-LING)Rule-BasedSystem）由Post于1943年提出的产生式规则得名。1965年，Newell和Simon用之建立了第一个人类认知模型。Stanford用之建立了第一个ES系统，即DENDRAL。基本思想：以产生式规则（条件-操作对）表示基本概念和关系。其知识一般分解为静态知识和推理行为与过程两部分。静态知识包括诸如事物、事件及其关系部分。4-2-1产生式系统的组成1.组成：由三部分构成，即产生式规则集合、总数据库和推理控制策略（如图2-3-7）。产生式规则形式：IFCTHENOP。注：产生式不仅仅表示了蕴涵关系，其条件和操作部分还可以有其它表示形式，且可以不受真值表的限制。因此，它比谓词逻辑中的IF…THEN…更为通用。总数据库又称上下文（Context）或当前数据库或暂存器。它存储了所有的相关动态推理信息和所使用的规则信息等。控制策略：控制规则的选择方法与应用过程。2.规则选择方法和步骤①匹配过程将当前数据库与规则的条件匹配，完全匹配者称为触发规则，当规则被选中后，称为启用规则。注：触发规则可以不止一条，所以触发规则不一定被启用。②冲突解决策略a)专一性排序：更有针对性的优先。b)规则排序：排序编号表示优先级别。c)数据排序：按条件数据的重要性排序。d)规模排序：多优先。e)就近排序：查找时，最近的规则优先。f)上下文约束：根据上下文进行分组选择的原则。g)其它方法或原则③操作4-2-2产生式系统的表示1.事实的表示孤立事实的表示：ES中常用(attribute-object-value)三元组表示。如：(AGEZHAO-LING43)(FATHERZHAO-YINZHAO-LING)(GRAMSTAINORGANISMGRAM-POSTIVE)(DOSEDRUG2.0-GRAMS)(MANZHAO-LINGTRUE)(WOMANZHAO-LINGTRUE)事实之间的关系：一般用树状结构（如MYCIN）或网状结构（如控制策略产