人工智能第三章课件.ppt

《人工智能第三章课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第三章课件.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Artificial IntelligenceArtificial Intelligence人工智能1/16/2023浙江科技学院浙江科技学院 信息学院信息学院 程志刚程志刚 人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第三章第三章 搜索推理技术搜索推理技术3.1 图搜索策略 3.6 产生式系统3.2 盲目搜索3.7 系统组织技术3.3 启发式搜索3.8 不确定性推理3.4 消解原理3.9 非单调推理3.5 规则演绎系统 3.10 小结人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2NOTE教学内容：教学内容：本章在上一章知识表示的基础上研究问题求解的方

2、法，是人工智能研究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。教学重点教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。教学难点教学难点：启发式搜索、规则双向演绎系统等。教学要求教学要求：重点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.1 图搜索策略图搜索策略图搜索控制策略一种在图中寻找路径的

3、方法。图中每个节点对应一个状态，每条连线代表一个操作符。这些节点与连线（状态与操作符）分别由产生式系统的数据库和规则来标记。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。重要概念OPEN表与CLOSE表搜索图与搜索树人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2图搜索过程图GRAPHSEARCH人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2 盲目搜索盲目搜索特点：不需重排OPEN表种类宽度优先深度优先等代价搜索人工智能导论 浙江科技学院 信息学院 计算机系

4、程志刚2006s23.2.1 宽度优先搜索宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法特点一种高代价搜索，但如有解存在，则必能找到。算法人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2宽度优先搜索框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2例子：八数码难题(8 puzzle problem)2831476512384765初始状态目标状态规则：规则：将数字移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不许移回先辈节点。要扩展26个节点，共生成46个节点后才能求得解人工智能导论 浙江科技学院 信息学院 计算机系 程志刚200

5、6s2人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2.2 深度优先搜索深度优先搜索定义首先扩展最新生成的（即最深的）节点，深度相等的节点可以任意排列。特点搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。算法为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度-深度界限。与宽度优先算法最根本的不同在于：扩展的后继节点放在OPEN表的前端人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.2.3 等代价搜索等代价搜索定义是宽度优先搜索的一种推广，不是沿着等长度路径的断层

6、进行扩展，而是沿着等代价路径断层进行扩展。搜索树种每条连接弧线上的有关代价，表示时间、距离 等花费。算法若所有连接弧具有相同的代价，则简化为宽度优先搜索算法。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2等代价搜索框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3 启发式搜索启发式搜索特点重排OPEN表，选择最有希望的节点进行扩展。种类有序搜索A*算法人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.1 启发式搜索策略和估价函数启发式搜索策略和估价函数盲目搜索可能带来组合爆炸定义：搜索过程中，往往存在许多与具体问题领域相关的

7、特征信息，可以用来加速搜索过程，这种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。启发式搜索策略应用某些准则，利用启发信息，重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有“希望”的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值建立估价函数的一般方法：试

8、图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。应用节点“希望”程度，（估价函数值）重排OPEN表。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.2 有序搜索有序搜索实质选择OPEN表中具有最小f值的节点作为下一个要扩展的节点。有序搜索算法框图人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2例子：八数码难题(8 puzzle problem)2831647512384765初始状态目标状态有序搜索树如下f(n)=d(n)+W(n)人工智能导论 浙江科

9、技学院 信息学院 计算机系 程志刚2006s2八数码难题的有序搜索树02人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.3.3 A*算法算法估价函数的定义对节点n定义f*(n)=g*(n)+h*(n)，表示从节点S开始，约束通过节点n的一条最佳路径的代价。希望估价函数f定义为f(n)=g(n)+h(n)，其中g是g*的估计，h是h*的估计。A*算法的定义定义1：在GRAGHSEARCH过程中，如果第8步中重排OPEN表是根据，f(n)=g(n)+h(n)进行的，则称该过程为A算法。定义2：在A算法中，如果对于所有的x都有h(x)h*(x),则称h(x)为h*(x)的下界，

10、它表示某种偏于保守的估计。定义3：采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4 消解原理消解原理基本概念原子公式（atomic formulas）文字 一个原子公式及其否定子句-由文字的析取组成的合式公式谓词公式、推理规则、置换合一等消解 对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.1 子句集的求取子句集的求取标准9步（P68）例子：例子：将下列为此演算公式化为一个子句集 (x

11、)P(x)=(y)P(y)=P(f(x,y)(y)Q(x,y)=P(y)开始：人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第一步：消去蕴含符号。只应用和符号，以AB替换AB。第二步：减少否定符号的辖域。每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第三步：对变量标准化。对哑元(虚构变量)改名以保证每个量词有其自己唯一的哑元。第四步：消去存在量词。用Skolem函数代替存在量词内的约束变量，即可消去存在量词 人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第五步：化为前束形。把

12、所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。第六步：把母式化为合取范式。任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第七步：消去全称量词。消去明显出现的全称量词。第八步：消去连词符号。用A，B代替(AB)，消去符号，最后得到一个有限集，其中每个公式是文字的析取。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2第九步：更换变量名称。可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。人工智能导论 浙江科技学院 信息学院 计算机系 程志

13、刚2006s23.4.2 消解推理规则消解推理规则消解式的定义令L1,L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一者，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。消解式的求法：取各子句的析取，然后消去互补对。假言推理合并重言式空子句（矛盾）链式（三段论）人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.3 含有变量的消解式含有变量的消解式含有变量的子句之消解式为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互补文字。例子（P72）消解

14、推理的常用规则人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.4.4 消解反演求解过程消解反演求解过程1、消解反演给出一个公式集S和目标公式L(1)否定L，得L；(2)把L添加到S中去；(3)把新产生的集合L，S化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。例子：存储问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2证明1、规定原子公式S(x,y)表示“x存储y”M(x)表示“x是钱”I(x)表示“x是利息”E(x,y)表示“x获得y”2、用谓词公式分别表示

15、前提和结论前提(x)(y)(S(x,y)M(y)=(y)(I(y)E(x,y)结论(X)I(x)=(x)(y)(M(y)-S(X,Y)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23、化为子句形前提化为子句形(1)S(x,y)M(y)I(f(x)(2)S(x,y)M(y)E(x,f(x)结论化为子句形(3)I(z)(4)S(a,b)(5)M(b)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s24、消解反演求NIL子句(1)子句(3)子句(4)子句(6)子句(7)子句(5)S(x,y)M(y)M(b)NILf(x)/za/x,b/y储蓄问题反演树储蓄问题反演

16、树人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2反演求解过程从反演树求取答案步骤把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的 反演树变换为在根部带有可用作答案的某个语句的一颗证明树。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5 规则演绎系统规则演绎系统定义基于规则的问题求解系统运用IfThen规则来建立。每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规

17、则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rule based deduction system)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then部分为后项(consequent)。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.1 规则正向演绎系统规则正向演绎系统定义正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。求解过程事实表达式的与或形变换：把事实表示为非蕴涵形式的与或形，作为系统的总数据库。事实表达式的与或图表示（k线分

18、开析取关系）人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2与或图的F规则变换：这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式：LW 式中：L是单文字；W为与或形的唯一公式。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.2 规则逆向演绎系统规则逆向演绎系统定义从then到if的推理过程。即从目标到事实或条件进行的推理过程。求解过程目标表达式的与或形式（k线分开合取关系）与或图的B规则变换作为终止条件的事实节点的一致解图人工智能导

19、论 浙江科技学院 信息学院 计算机系 程志刚2006s23.5.3 规则双向演绎系统规则双向演绎系统1.正向演绎系统和逆向演绎系统的特点和局限性 正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。2.双向(正向和逆向)组合演绎系统的构成 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。人工

20、智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.终止条件 组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6 产生式系统产生式系统定义定义在基于规则系统中，每个if可能与某断言(

21、assertion)集中的一个或多个断言匹配，then部分用于规定放入工作内存的新断言。当then部分用于规定动作时，称这种基于规则的系统为反应式系统(reaction system)或产生式系统(production system)。实质实质在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为，由于这类系统的知识库主要用于存储规则，因此又称此类系统为基于规则的系统。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6.1 产生式系统的组成产生式系统的组成总数据库产生式规则控制策略产生式系统的主要组成产生式系

22、统的主要组成人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2选择规则到执行操作的步骤选择规则到执行操作的步骤匹配把当前的数据库与规则的条件部分相匹配冲突当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。操作执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.6.2 产生式系统的推理产生式系统的推理正向推理从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。逆向推理从表示目标的谓词或命题出发，使用一组

23、产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7 系统组织技术系统组织技术系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后再考虑各子模块间在求解时的合作问题人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7.1 议程表议程表1.1.定义定义 议程表(agenda)是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任

24、务的理由和表示对该任务是有用的证据总权的评价。2.2.模块间的合作模块间的合作 允许几个独立模块进行通讯。其通讯方法是每个模块可将支持(或反对)某 个具体任务的证据，加到一个证明选择该任务是正确的表中。这样就使系统能够选出从各方面都有充分证据的任务。虽然各模块共同使用关于为什么要执行各项任务 的证据，但一个模块并不需要了解其它模块如何工作，以及它们所包含的知识。这样，议程表方法便具有大系统中模块化的一切优点，而无相互隔离的缺点。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7.2 黑板法黑板法1.1.定义定义 黑板法(the Blackboard Approach)首先

25、是在HEARSAY-语音理解系统中发展起来的。它的思想比较简单。整个系统由一组称为知识资源(KS)的独立模块和一块黑板组成。这里，知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。2.2.模块间的合作模块间的合作 当一个KS被激发时，它检查当时黑板上的内容，并应用其知识产生一个新的假设写到黑板上，直到完成任务为止。当时间表没有发现未解决的活动记录时，系统便停止执行。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.7.3 -极小搜索法极小搜索法 1 1、定义、定义值表示一假设的级别与参加竞争的最佳假设的级别之差，提供了一种选择最有希望假设的技术。2

26、 2、工作过程、工作过程 一次接受一串输入，顺序地处理，使其形成一个关于输入的统一而相容的解释。-极小法是这样来解决这类问题的：在适当的时刻，触发某KS，然后为它生成所有它认为是可能的假设，并赋给某个假设一种级别。由这些级别计算出的值，表示一假设的级别与参加竞争的最佳假设的级别之差。而在该假设最后导致不相容时，再考虑参加竞争的另一假设。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8 不确定性推理不确定性推理不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。人工智能导论 浙江科技学院 信息学院 计算机系 程

27、志刚2006s23.8.1 关于证据的不确定性关于证据的不确定性以模糊集理论为基础的方法把所有条件中最小的可信度作为总条件的可信度。以概率为基础的方法把所有条件的可信度的乘积作为总的可信度。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8.2 关于结论的不确定性关于结论的不确定性不确定性的表示不确定性的表示关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。不确定性的处理不确定性的处理如果规则的条件部分不完全确定，求得结论的可信度的方法有以下两种：(1)取结论可信度为条件可信

28、度与上述系数的乘积。(2)按照某种概率论的解释，我们假设规则的条件部分的可信度Cin和其结论部分的可信度Cout存在某种关系，这种关系可用来代表规则的不确定性。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.8.3 多个规则支持同一事实时的多个规则支持同一事实时的不确定性不确定性 1.基于模糊集理论的方法基于模糊集理论的方法 取支持这个事实的各规则的可信度的最大值作为事实的可信度。2.基于概率论的方法基于概率论的方法 首先把各个证据的可信度转换成可信性比例r。可信性比例r和可信度c之间的关系可表示为把各证据的可信性比例简单地相乘就可以求得这些证据所支持的事实的可信性比例。

29、然后，再利用上述公式转换回相应的可信度。这样就求得这个事实的可信度。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9 非单调推理非单调推理缘由：缘由：基于谓词逻辑的系统，为真的命题数目随时间严格增加，新命题的加入不会导致已知为真或已被证明的命题变成无效。定义定义非单调推理用来处理那些不适合用谓词逻辑表示的知识它能够较好得处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9.1 缺省推理缺省推理定义定义 当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构

30、造这种猜想称为缺省推理(default reasoning)。缺省推理的定义缺省推理的定义1：如果X不知道，那么得结论Y。缺省推理的定义缺省推理的定义2：如果X不能被证明，那么得结论Y。缺省推理的定义缺省推理的定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。例子例子 一个安排会议程序：程序必须求解一个约束满足问题，即找出每个参加者都有空闲的开会日期与时刻，并有可供开会的房间。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.9.2 正确性维持系统（正确性维持系统（TMS）正确性维持系统正确性维持系统(Truth Maintenane System,TMS)这是一个

31、已经实现的非单调推理系统。它用以协助其它推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保持相在其它程序所产生的命题之间保持相容性容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s2工作原理工作原理 在TMS中，每一命题或规则均称为节点，且对任一节点以下两种状态必居其一：IN 相信为真OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。IN节点是指那些至少有一个在当前说来是有效证实的节点。OUT结点则指那些当前无任何有效证实的节点。在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：(1)支持表(SL(IN-节点)(OUT-节点)(2)条件证明(CP(结论)(IN-假设)(OUT-假设)人工智能导论 浙江科技学院 信息学院 计算机系 程志刚2006s23.10 小结小结经典搜索推理技术经典搜索推理技术图搜索技术消解反演高级推理搜索技术高级推理搜索技术规则演绎系统产生式系统系统组织技术不确定性推理非单调推理