人工智能原理3-2课件

Review1、SearchEnginePageRank2、DataMiningAssociationRule3、Resolutionbasedonclauseoverview1.Rulebaseddeductionsystem2.Productionsystem3.Uncertaintyknowledgeandreasoning归结反演的策略以上讨论的几种基本的归结策略，在具体应用时可把几种策略组合在一起使用。归结演绎推理是在自动定理证明领域影响较大的一种推理方法，它比较简单且又便于在计算机上实现。但由于它要求把逻辑公式转化成子句集，就可能丢失蕴含式含有的逻辑控制信息。例如下列逻辑公式：

(┐A∧┐B)→C(┐A∧┐C)→B(┐B∧┐C)→A┐A→(B∨C)┐B→(A∨C)┐C→(A∨B)A∨B∨C1规则演绎系统对于许多公式来说，子句形是一种低效率的表达式，因为一些重要信息可能在求取子句形过程中丢失。可以采用易于叙述的ifthen规则来求解问题，这种基于规则的系统叫做规则演绎系统。规则正向演绎系统基于规则的演绎系统和产生式系统，均有两种推理方式：正向推理(forwardchanining)和逆向推理(backwardchaining)。

正向推理：从if部分向then部分推理的过程，它是从事实或状况向目标或动作进行操作的。

逆向推理：从then部分向if部分推理的过程，它是从目标或动作向事实或状况进行操作的。

规则正向演绎系统

1.事实表达式的与或形变换

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，要把一个公式化为与或形，可采用下列步骤(1)利用(W1→W2)和(┐W1∨W2)的等价关系，消去符号→(2)用狄·摩根(DeMorgan)定律把否定符号移进括号内，直到每个否定符号的辖域最多只含有一个谓词为止。(3)对所得到的表达式进行Skolem化和前束化。(4)对全称量词辖域内的变量进行改名和变量标准化，而存在量词量化变量用Skolem函数代替。(5)删去全称量词，且使各主要合取式中的变元不同名。

例如，我们有事实表达式

按上述步骤进行转化后得到与/或形表达式：规则正向演绎系统规则正向演绎系统2、F规则的表示形式在与/或形正向演绎推理中，要求F规则具有如下形式：L→W

其中，L为单文字，W为与/或形。如果领域知识的表示形式不是所要求的形式，则需通过变换将它变成规定的形式。3、目标公式的表示形式在与/或形正向演绎推理中，要求目标公式用子句表示，否则就需要化成子句形式。规则正向演绎系统4、推理过程

应用F规则进行推理的目的在于证明某个目标公式。其推理过程为：

1)首先用与/或树把已知事实表示出来。

2)用F规则的左部和与/或树的叶节点进行匹配，将匹配成功的F规则加入与/或树中。

3)重复进行步骤2)，直到产生一个含有以目标节点作为终止节点的解图为止。规则正向演绎系统规则正向演绎系统规则正向演绎系统规则正向演绎系统规则逆向演绎系统与/或形逆向演绎推理是从待证明的问题出发，逆向使用蕴式(B规则)进行演绎推理，直至得到包含已知事实的终止条件为止。1、目标公式的与/或形及其与/或树表示在与/或形逆向演绎推理中，要求目标公式用与/或形表示，其变换过程与正向演绎推理中对已知事实的变换相似，只是要用存在量词约束的变元的Skolem函数替换由全称量词约束的相应变元，并且消去全称量词，然后再消去存在量词，且使各主要析取式中的变元不同名。规则逆向演绎系统规则逆向演绎系统2、B规则的表示形式

B规则的表示形式为：W→L其中，W为任一与/或形公式，L为文字。如果已知的B规则不是所要求的形式，可以把它化成规定的形式。比如：W→(L1∧L2)W→(L1∨L2)？W→L1,W→L23、已知事实的表示形式在逆向演绎推理中，要求已知事实是文字的合取形式，即形如F1∧F2∧…∧Fn规则逆向演绎系统4、推理过程应用B规则进行逆向演绎推理的目的是求解问题，从目标公式的与/或树出发，通过运用B规则来进行求解。其推理过程为：1)先用与/或树把目标公式表示出来。2)用B规则的右部和与/或树的叶节点进行匹配，将匹配成功的B规则加入到与/或树中。3)重复进行步骤2)，直到产生某个终止在事实节点上的一致解图为止。规则逆向演绎系统规则逆向演绎系统规则双向演绎系统规则双向演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。用对应的mgu来标记匹配。代换的一致性

无论对于正向演绎、逆向演绎还是双向演绎，都要求推理过程中所用的代换集合具有一致性。剪枝策略剪枝策略的基本思想：每当选用一条规则时，就进行一次一致性检查，如果当前的部分解图是一致的，则继续向下扩展，否则就放弃该规则而选用其他侯选规则。剪枝策略2产生式系统美国数学家Post，1943年提出了一种计算形式体系里所使用的术语。主要是使用类似文法的规则，对符号串做替换运算。这就是最早的一个产生式系统。到了60年代，产生式系统成为认知心理学研究人类心理活动中信息加工过程的基础，由此心理学家认为，人脑对知识的存储就是产生式形式。因此，用它来建立人类认知模型。到目前为止，产生式系统已发展成为人工智能系统中最典型最普遍的一种结构。产生式表示方法是专家系统中知识表式的第一选择。产生式系统组成产生式系统由3个部分组成，即总数据库(或全局数据库)、产生式规则和控制策略。各部分间的关系如图所示。

产生式系统组成①产生式规则是一个以“如果满足这个条件，就应当采取某些操作”形式表示的语句。P→Q或ifPthenQ例如，

规则:

if某种动物是哺乳动物，并且吃肉

then

这种动物被称为食肉动物②总数据库有时也被称作上下文，全局数据库，GlobalData-base。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足。

产生式系统组成控制策略其作用是说明下一步应该选用什么规则，也就是如何应用规则。通常从选择规则到执行操作分3步：匹配、冲突解决和操作。

(1)匹配在这一步，把全局数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。匹配结果分为：完全匹配,近似匹配,不匹配

产生式系统组成(2)冲突解决当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。举例如下:设有以下两条规则,

规则R1IFfourthdawnshortyardageTHENpunt

规则R2IFfourthdawnshortyardagewithin30yards(fromthegoalline)THENfieldgoal全局数据库包括：”fourthdawn””shortyardage””within30yards”

产生式系统组成有很多种冲突解决策略，其中一种策略是先使用规则R2，因为R2的条件部分包括了更多的限制，因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略，称为专一性排序。还有不少其他的冲突解决策略产生式系统组成(a)专一性排序如果某一规则条件部分规定的情况，比另一规则条件部分规定的情况更有针对性，则这条规则有较高的优先级。(b)

规则排序

如果规则编排的顺序就表示了启用的优先级，则称之为规则排序。(c)数据排序

把规则条件部分的所有条件按优先级次序编排起来，运行时首先使用在条件部分包含较高优先级数据的规则。(d)规模排序

按规则的条件部分的规模排列优先级，优先使用被满足的条件较多的规则。(e)就近排序

把最近使用的规则放在最优先的位置。这和人类的行为有相似之处。如果某一规则经常被使用，则人们倾向于更多地使用这条规则。(f)上下文限制

把产生式规则按它们所描述的上下文分组，也就是说按上下文对规则分组。在某种上下文条件下，只能从与其相对应的那组规则中选择可应用的规则。产生式系统组成控制策略(1)匹配(2)冲突解决(3)操作操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用产生式系统表示1、事实的表示：一般用三元组（对象，属性，值）或 （关系，对象1，对象2）例：（Lee,Age,35）,(Friend,Lee,Chang)产生式系统表示2、规则表示例子：MYCIN系统中典型规则的定义：

<rule>=(IF<antecedent>THEN<action>(ELSE<action>))

<antecedent>=(AND<condition>)

<condition>=(OR｛<condition>｜(<predicate><associative_triple>)

<associative_triple>=(<attribute><object><value>)

<action>=｛<consequent>｝｜｛<procedure>｝

<consequent>=(<associative_triple><certainty_factor>)

产生式系统表示规则的内容：

前提条件

◆

细菌革氏染色阴性

◆

形态杆状

◆

生长需氧

结论

该细菌是肠杆菌属，CF=0.8。

产生式系统推理1.正向推理

正向推理又称为正向链接推理，其推理基础是逻辑演绎的推理链，它从一组表示事实的谓词或命题出发，使用一组推理规则，来证明目标谓词公式或命题是否成立。

实现正向推理的一般策略是：先提供一批数据(事实)到总数据库中，系统利用这些事实与规则的前提匹配，触发匹配成功的规则(即启用规则)，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库中的所有事实再与规则库中另一条规则匹配，用其结论再修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库为止。产生式系统推理产生式系统推理动态演示产生式系统推理产生式系统推理2.反向推理

反向推理又称为后向链接推理，其基本原理是从表示目标的谓词或命题出发，使用一组规则证明事实谓词或命题成立，即提出一批假设(目标)，然后逐一验证这些假设。产生式系统推理产生式系统推理3.双向推理

双向推理又称为正反向混合推理，它综合了正向推理和逆向推理的长处，克服了两者的短处。双响推理的策略是同时从目标向事实推理和从事实想目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。产生式系统举例建立一个动物识别系统，用以识别虎、金钱豹、斑马、长颈鹿、企鹅、驼鸟、信天翁等七种动物。规则库：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该动物是信天翁产生式系统举例(1)分类的思想(2)知识的合理组织与管理{r1、r2、r5、r6、r7、r8、r9、r10、r11、r12}{r3、r4、r13、r14、r15}产生式系统的特点①用产生式系统结构求解问题的过程和人类求解问题时的思维很相像。因而可以用它来模拟人类求解问题的思维过程。②可以把产生式系统作为人工智能系统的基本结构单元或基本模型看待。因而研究产生式系统的基本问题就具有一般意义。③表示的格式固定、形式单一、规则间相互独立。所以建立容易；推理方式单纯、知识库与推理机分离，修改方便、容易理解。3知识的不确定性

在各种实际应用领域中，严格精确的和确定的知识并不多见，大量的知识是不精确的和不确定的，需要采用不确定推理或称为不精确推理对不确定知识进行处理。可以说，不确定性(Uncertainty)是智能问题的本质特征，因此，智能系统的能力更主要反映在求解不确定性问题的能力上。知识的不确定性现实生活中的事物有时很难用精确的概念来描述，比如高、矮、胖、瘦等。对于不确定性知识要用不确定推理来处理，否则有可能得出一些荒谬的结论。专家系统中的不确定性表现在三个方面，第一是证据或事实的不确定性，第二是规则的不确定性，第三是推理的不确定性。知识的不确定性1、证据的不确定性(1)证据的歧义性：如“同意总理开会”

“Isawamanwithatelescope.”(2)证据的不完全性

①证据尚未收集完全

②证据的特征值不完全(3)证据的不精确性：如“大约是1.7米”(4)证据的模糊性：如“年轻”(5)证据的可信性(6)证据的随机性知识的不确定性2、规则的不确定性产生式规则的不确定性主要有以下几个方面。(1)构成规则前件的模式的不确定性如：有一条产生式规则“如果患者发高烧且常流清鼻涕，则患者感冒”知识的不确定性(2)观察证据的不确定性例如，患者发高烧的体温观察值并不是恒定的。晚上可能是39℃，早上可能是38.5℃。(3)规则前件的证据组合的不确定性例如，有一位患者的体温一直都是40℃，流清鼻涕，但并不是常流清鼻涕。知识的不确定性(4)规则本身的不确定性每一条规则并不都具有100%的信任度，这就是规则的不确定性，或称为规则强度(5)规则结论的不确定性由于规则的前件包含有各种不确定性因素，运用不确定的规则，导出的结论也就不可避免地是不确定的。知识的不确定性此外，在规则使用过程中，还有两种典型的使用规则的不确定性。(1)冲突消解策略包含有使用规则的不确定性(2)选择假设进行反向推理验证的不确定性知识的不确定性3、推理的不确定性由于证据的不确定性和规则的不确定性在推理过程中的动态积累和传播从而导致推理结论的不确定性。因此，需要采用某种不确定性的测度，并能在推理过程中来传递和计算这种不确定性的测度，最总得到结论的不确定性测度。

在不确定推理中，不确定性测度的计算有以下三种基本的计算模式。知识的不确定性知识的不确定性知识的不确定性知识的不确定性一、不确定性推理及实现1.基本概念

(1)什么是不确定性推理不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推出具有一定程度的不确定性但却合理或者近乎合理的结论的思维过程。

4不确定性推理

(2)不确定性推理中的基本问题在不确定性推理中，知识和证据都具有某种程度的不确定性，这就为推理机的设计与实现增加了复杂性和难度。它除了必须解决推理方向、推理方法、控制策略等基本问题外，一般还需要解决不确定性的表示和量度、不确定性匹配、不确定性的传递算法以及不确定性的合成等重要问题。

不确定性推理

(3).

不确定性匹配算法及阈值的选择

对于不确定性推理，由于知识和证据都具有不确定性，而且知识所要求的不确定性与证据实际具有的不确定性程度不一定相同，因而就出现了“怎样才算匹配成功”的问题。

不确定性推理不确定性推理

对于这个问题，目前常用的解决方法是：设计一个算法用来计算匹配双方相似的程度，另外再指定一个相似的“限度”，用来衡量匹配双方相似的程度是否落在指定的限度内。如果落在指定的限度内，就称它们是可匹配的，相应知识可被应用。

•

用来计算匹配双方相似程度的算法称为不确定性匹配算法

•

用来指出相似的“限度”称为阈值(4)不确定性的传递算法

推理过程中不确定性的传递过程，包括如下两个密切相关的子问题：

•在每一步推理中，如何把证据及知识的不确定性传递给结论；

•在多步推理中，如何把初始证据的不确定性传递给最终结论。

不确定性推理不确定性推理

对前一个问题，在不同的不确定推理方法中所采用的处理方法各不相同。对第二个问题，各种推理方法所采用的处理方法基本相同，即：把当前推出的结论及其不确定性程度作为证据放入数据库中，供以后推理使用。

(5).

结论不确定性的合成

推理时有时会出现这样的情况：用不同的知识进行推理得到了相同的结论，但不确定性的程度却不同。此时，需要用合适的算法对它们进行合成。在不同的不确定推理方法中所采用的处理方法各不相同。不确定性推理不确定性推理二、常用的不确定性推理方法介绍(1)基于概率的不确定推理

利用新的信息将先验概率P(H)更新为后验概率P(H|E)的一种计算方法.基于概率的不确定推理于1976年提出，其首先在Prospector专家系统中使用，它以概率论中的全概率公式和Bayes公式为基础。基于概率的不确定推理基于概率的不确定推理基于概率的不确定推理

(2)可信度方法(CertaintyFactor)

可信度方法是由E.H.Shortliffe等人在确定性理论的基础上，结合概率提出的一种不确定性推理方法，首先在Mycin系统中得到了成功的应用。

其核心思想是：利用确定性因子CF（值）

Ⅰ.

联系于具体的断言

Ⅱ.

联系于每条规则

Ⅲ.

通过CF的计算传播不确定性

不确定性推理

(1)可信度根据经验对一个事物或现象为真的相信程度。

(2)C-F模型

C-F模型是基于可信度表示的不确定性推理的基本方法。

可信度方法

Ⅰ.

知识不确定性的表示

在C-F模型中，知识是用产生式规则表示的，其一般形式是：

ifEthenH(CF(H,E))

其中，

E：是知