人工智能：第三章 搜索推理技术

第三章 搜索推理技术 

教学内容：本章在上一章知识表示的基础上研究问题求解的方法，是人工智能研究的又一核心问题。内容包括早期搜索推理技术，如图搜索策略和消解原理；以及高级搜索推理技术，如规则演绎系统、产生式系统、系统组织技术、不确定性推理和非单调推理。 

教学重点：图搜索策略、消解原理、规则演绎系统、产生式系统。 

教学难点：启发式搜索、规则双向演绎系统等。 

教学方法：课堂教学为主，辅以恰当的实验。注意结合前面所学知识表示的基础内容，将其与问题求解方法融为一体。及时提问、收集学生学习情况。尽量使用实例和网络课程中的多媒体素材进行讲解。 

教学要求：重点掌握一般图搜索策略和消解原理，掌握各种搜索方法和产生式系统原理，了解规则演绎系统的基本原理，对系统组织技术、不确定性推理和非单调推理等高级推理技术作一般性了解。 

3.1 图搜索策略 

教学内容：本节介绍图搜索的一般策略，作为各种图搜索技术的基础。 

教学重点：图搜索的一般过程、OPEN表和CLOSE表的概念。 

教学难点：OPEN表和CLOSE表的物理意义。 

教学方法：课堂教学为主，通过提问彻底弄清图搜索的基本概念。 

教学要求：重点掌握图搜索一般策略，掌握OPEN表和CLOSE表的构成及作用。 

1、图搜索策略的定义 

　　图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。 

2、图搜索算法中的几个重要名词术语 

　　（1）OPEN表与CLOSE表 

　　（2）搜索图与搜索树 

3、图搜索(GRAPHSEARCH)的一般过程 

　　(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。 

　　(2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。 

　　(3) LOOP：若OPEN表是空表，则失败退出。 

　　(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。 

　　(5) 若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。 

　　(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。 

　　(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。 

　　(8) 按某一任意方式或按某个探试值，重排OPEN表。 

　　(9) GO LOOP。 

提问：图搜索是针对什么知识表示方法的问题求解方法？ 

4、图搜索方法分析： 

　　图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。 

提问：什么是图搜索? 其中，重排OPEN表意味着什么，重排的原则是什么? 

3.2盲目搜索 

教学内容：介绍三种盲目搜索方法，即宽度优先搜索、深度优先搜索和等代价搜索。 

教学重点：盲目搜索的特点，宽度优先搜索。 

教学难点：等代价搜索中代价的概念。 

教学方法：以实例强化内容的学习，通过提问引导学生对三种方法的特点进行比较。 

教学要求：掌握盲目搜索的特点，比较三种盲目搜索方法的优缺点。 

3.2.1宽度优先搜索 

1、定义 

　　如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。 

2、特点 

　　这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。 

3、宽度优先搜索算法 

　　(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。 

　　(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 

　　(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。 

　　(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 

　　(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。 

　　(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。 

4、宽度优先搜索方法分析： 

　　宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。 

　　宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。 

5、例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题： 

1 2 3 

8　 4 

7 6 5 

提问：宽度优先搜索方法中OPEN表需要按什么方式进行操作？ 

A．先进后出 B．先进先出 

3.2.2深度优先搜索 

1、定义 

　　在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。 

　　这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。 

2、特点 

　　首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。 

3、深度界限 

　　为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度棗深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。 

4、含有深度界限的深度优先搜索算法 

　　请同学们课后自学，并回答课后思考题。 

思考题：有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？ 

3.2.3等代价搜索 

1、定义 

　　宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。 

2、等代价搜索中的几个记号 

　　起始节点记为S； 

　　从节点i到它的后继节点j的连接弧线代价记为c(i，j)； 

　　从起始节点S到任一节点i的路径代价记为g(i)。 

3、等代价搜索算法 

　　（请同学们课后认真阅读本算法，指出与宽度优先、深度优先算法有何特别之处。） 

4、等代价搜索方法分析 

　　如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法。 

思考：试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因。 

3.3 启发式搜索 

教学内容：启发式搜索策略概述和有序搜索。启发式搜索弥补盲目搜索的不足，提高搜索效率。 

教学重点：启发式搜索策略、启发信息和有序搜索。 

教学难点：估价函数的设计、A*算法原理。 

教学方法：通过实例加深对原理的理解，鼓励同学扩大阅读范围。 

教学要求：掌握启发式搜索策略和估价函数的设计方法，了解A*算法原理。 

3.3.1启发式搜索策略和估价函数 

1、为什么需要启发式搜索 

　　盲目搜索效率低，耗费过多的计算空间与时间，这是组合爆炸的一种表现形式。 

2、定义 

　　进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。 

3、启发式搜索策略 

　　有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数(evalution function)。 

4、估价函数 

　　为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。 　　f(n)——表示节点n的估价函数值　 

　　建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 

3.3.2 有序搜索 

1、定义 

　　用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳优先算法。 

　　尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的：一个节点的希望程序越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。 

2、实质 

　　选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。 

3、有序状态空间搜索算法 

　　(1) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 

　　(2) 如果OPEN是个空表，则失败退出，无解。 

　　(3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。 

　　(4) 把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。 

　　(5) 如果i是个目标节点，则成功退出，求得一个解。 

　　(6) 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： 

  (a)计算f(j)。 

  (b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。 

  (c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则 

  　　(i) 以此新值取代旧值。 

  　　(ii) 从j指向i，而不是指向它的父辈节点。 

  　　(iii) 如果节点j在CLOSED表中，则把它移回OPEN表。 

　　(7) 转向(2)，即GO TO(2)。 

4、有序搜索方法分析 

　　宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，选择f(i)作为节点i的深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径的代价。 

　　有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。 

5、例：八数码难题 

　　采用了简单的估价函数 

f(n)=d(n)+W(n) 

　　其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，起始节点棋局 

2 8 3 

1 　4 

7 6 5 

的f值等于0+4=4。 

3.3.3 A*算法 

　　A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。 

1、几个记号 

　　令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合｛ti｝上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。 

2、估价函数的定义 

　　定义g*为g*(n)=k(S,n) 

　　定义函数f*，使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即 

f*(n)=g*(n)+h*(n) 

　　希望估价函数f是f*的一个估计，此估计可由下式给出： 

f(n)=g(n)+h(n) 

　　其中：g是g*的估计；h是h*的估计。对于g(n)来说，一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)≥g*(n)。h*(n)的估计h(n)依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数。 

3、A*算法定义 

　　定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)参考链接： 图灵测试

全文共2189字，预计学习时长6分钟

 图源：slate

 人工智能正在改变生活的方方面面，大多数专家认为，今天的人工智能进化为人工通用智能只是时间问题，计算机迟早会达到甚至超过人类智能的临界点。但问题是，我们如何知道这种情况何时会发生？

 1950年，艾伦·图灵提出了著名的测试方法，用来判断机器是否真的在思考。这一测试在论文发表后经历了一些演变，其中一个常见的解释是这样的：

 一个人，即审讯者（C），可以通过电脑终端进行交流（现在，我们可能会说通过即时通讯、电子邮件或短信）；在计算机链路的另一端是人（B）或计算机（A）。经过20分钟的键盘通信后，询问者会表明在另一端是人还是计算机。

 如果审讯者认为他在和一个人交谈，但实际上是一台电脑，那么结论就是，这台电脑一定在像人一样思考。为了让计算机“通过”测试，这个实验要进行多次，超过一半的审问者同意。

 最近，对图灵测试的一种改进将对话时间缩短到5分钟，并认为如果计算机愚弄受试者的时间超过30%，测试就通过了。2014年，一个名为Cleverbot 的程序被声称通过了图灵测试，愚弄了33%的审讯者。然而，虽然Cleverbot有一些复杂的反应，但我与它的互动很快暴露了其局限性。

 不过，我宁愿对图灵的测试吹毛求疵，也不愿对Cleverbot s的主张吹毛求疵。我有两个主要担忧：

 ·        图灵测试的名声推动了诸如Cleverbot或Watson等程序的发展，这些程序拥有惊人的语言能力，但却牺牲了针对真正AGI的资源。

 ·        为了通过测试，计算机必须被设定为会说谎。有没有私人问题，比如你多大了？眼睛是什么颜色的?甚至你是一台电脑吗?如果电脑如实回答，那就是泄密。在某种程度上，为了通过测试，一个系统被编程为目标和情感的等价物，这些必须是人类的目标和情感，而不是可能对机器有效的目标和情感。这需要花费大量的开发努力来玩这种本质上属于聚会游戏的游戏

 我对该测试的准确性也有几点担忧：

 ·        测试结果的好坏取决于审讯者的老练or易上当。

 ·        该测试允许在计算机的某一部分上假装有缺陷以掩盖其局限性。例如，为了弥补理解上的缺陷而声称自己是一个孩子。

 ·        它强加了人类层次的约束。如果我们能造出一台具有超人智慧的机器，它会不会因为看起来太聪明而无法通过测试。

 假设有真正的AGI系统，并且位置颠倒了——一个AGI来决定你是计算机还是人，你能做得多好？

 在最近的AGI-20会议上，一位与会者评论说，真正智力的测试应该是设计真正智力测试的能力。没有这样的测试，难道我们就没有真正的智慧吗?

 为了解决这些问题，人们建议调整图灵测试，创造出一套标准类型的问题，用来探究情报的各个方面，而不是由审问者单独或多或少地编造一些随机问题。与其将计算机的反应与个人进行比较，不如将计算机与不同年龄、性别、背景和能力的人类回答者进行比较。

 现在，把审问者重新塑造成法官，他们会给测试结果打分，以判断每个答案是否都是对问题的合理回答。问题和答案应该随机混合，以防止发现得分趋势。例如，如果一个回答者给出了一个低分数的答案，不应该影响该回答者对其他回答的感知质量。

 针对特定智力领域的样本问题可能包括以下内容：

 ·        你能描述现在看到（听到）的东西吗?

 ·        描述一下你在这幅图中看到了什么?

 ·        （模式识别/知识）如果我[动作，比如唱歌，跌倒，掉铅笔，讲笑话]，你的反应会是什么?

 ·        （预测/理解人类行为）如果你[行为，比如讲笑话，偷我的钱包，或者通过这个测试]，我的反应会是什么？

 ·        说出三种类似于[一个物体，如树、花、汽车或电脑]的东西。

 ·        说出你最喜欢的[物体，如食物、饮料、电影明星、书或科学家]。

 ·        （目标导向）解释一种电码。

 ·        使用那个代码，编码这个消息。

 ·        这张照片怎么了？

 “这张照片有什么问题吗?”该问题不仅关于对象识别的图像，还关于现实世界的理解使用和关系的对象。发件人：科赫、克里斯托弗和朱利奥·托诺尼，“关于意识的测试——我们如何知道这台电脑有感知能力?让它解决一个简单的难题” (2011)。

 可以对一个会思考的机器和一个人提出同样的问题，但我们可以假定，会从这两者得到显著不同的答案，而且很容易区分电脑和人。对每个问题的回答由几位评委来评定是否有意义，如果计算机给出的有意义的答案数量相同，它就在思考。

 关键在于，问题需要是开放式的，以便让受访者表明他们真正理解。为了创造无限的集合，题目的类型可以是多种多样的，这可以防止计算机被输入特定的答案。这些问题都需要认真思考。

 同样地，一个法官可能不擅长判断一个人的回答是否合理，但如果有多个法官对多个应答者进行评级，我们应该可以得到一个好的评估。让AGI成为裁判之一怎么样?

 图源：unsplash

 是时候用更好的东西取代图灵测试了，继续致力于在图灵测试中欺骗人类并不是创建AGI的正确方向，该去尝试衡量它的智力。

 推荐阅读专题

 留言点赞发个朋友圈

 我们一起分享AI学习与发展的干货

 编译组：杨娴、符馨元

 相关链接：

 https://www.kdnuggets.com/2020/08/beyond-turing-test.html

 如转载，请后台留言，遵守转载规范

 推荐文章阅读

 ACL2018论文集50篇解读

 EMNLP2017论文集28篇论文解读

 2018年AI三大顶会中国学术成果全链接

 ACL2017论文集：34篇解读干货全在这里

 10篇AAAI2017经典论文回顾

 长按识别二维码可添加关注

 读芯君爱你

争做国内使用体验Z好的开源 Web 富文本编辑器！

为何选择 wangEditor

• 万星项目 Github Star 1w+
• 简洁、轻量级、文档齐全
• QQ 群及时答疑
• 开源团队维护，非个人单兵作战

初见

npm 安装 npm i wangeditor --save ，几行代码即可创建一个编辑器。

import E from 'wangeditor'
const editor = new E('#div1')
editor.create()

更多使用配置，请阅读使用文档。

demo

在线体验 demo 可到 codepen.io/collection/DNmPQV 。

注意，如果打不开，可以去查看 github examples 的源码。

浏览器兼容性

• 兼容主流 PC 浏览器，IE11+
• 不支持移动端和 ipad

遇到问题

• 加入 QQ 群：901247714，164999061(人已满)，710646022(人已满)
• 提交问题和建议

贡献代码

欢迎非团队成员贡献代码，提交 Pull Request，请一定参考贡献代码流程。

谁在维护

wangEditor 现有一个开源团队在维护，团队可以保证答疑、bug 修复和迭代效率。

查看开发团队，或想加入开发团队

为我们点赞

如果你感觉有收获，欢迎给我打赏，以激励我们更多输出优质开源内容。

 ～P∨Q(即P→Q) 

\          / \        / 

 消解式Q 

  (2) 

 合并 

　　(3) 重言式 

　　(4) 空子句(矛盾) 

　～P       ～Q［F(Y)］   置换σ+｛F(Y)?X｝  　　　　　　P［F(Y)］  #>$>$ 消解反演求解过程  !、基本思想  　　把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思想十分相似。  @、消解反演  　　反演求解的步骤  　　给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：  　　(!)否定L，得～L；  　　(@)把～L添加到S中去；  　　(#)把新产生的集合｛～L，S｝化成子句集；  　　($)应用消解原理，力图推导出一个表示矛盾的空子句NIL。  　　反演求解的正确性  　　设公式L在逻辑上遵循公式集S，那么按照定义满足S的每个解释也满足L。决不会有满足S的解释能够满足～L的，所以不存在能够满足并集S∪｛～L｝的解释。如果一个公式集不能被任一解释所满足，那么这个公式是不可满足的。因此，如果L在逻辑上遵循S，那么S∪｛～L｝是不可满足的。可以证明，如果消解反演反复应用到不可满足的子句集，那么最终将要产生空子句NIL。因此，如果L在逻辑上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后将产生空子句；反之，可以证明，如果从S∪｛～L｝的子句消解得到空子句，那么L在逻辑上遵循S。  #、反演求解过程  　　步骤：  　　(!)把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。  　　(@)按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。  　　(#)用根部的子句作为一个回答语句。  　　分析：  　　答案求取涉及到把一棵根部有NIL的反演树变换为在根部带有可用作答案的某个语句的一颗证明树。由于变换关系涉及到把由目标公式的否定产生的每个子句变换为一个重言式，所以被变换的证明树就是一棵消解的证明树，其在根部的语句在逻辑上遵循公理加上重言式，因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。  例：储蓄问题  前提：每个储蓄钱的人都获得利息。  结论：如果没有利息，那么就没有人去储蓄钱  思考：应用消解反演求解如下问题：  “如果无论约翰(JOHN)到哪里去，菲多(FIDO)也就去那里，那么如果约翰在学校里，菲多在哪里呢?”  #>% 规则演绎系统  教学内容：规则演绎系统属于高级搜索推理技术，用于解决比较复杂的系统和问题。本节介绍规则演绎系统的定义及其三种推理方法：规则正向演绎系统、规则逆向演绎系统和规则双向演绎系统。  教学重点：规则演绎系统的定义、正向推理和逆向推理过程。  教学难点：双向演绎的匹配问题等。  教学方法：课堂教学为主。通过比较揭示正向推理、逆向推理和双向推理的特点。  教学要求：掌握规则演绎系统的定义和正向推理、逆向推理的过程，了解规则双向演绎系统。  　　规则演绎系统的定义：  　　基于规则的问题求解系统运用下述规则来建立：  　　IF→THEN  　　其中，IF部分可能由几个IF组成，而THEN部分可能由一个或一个以上的THEN组成。  　　在所有基于规则系统中，每个IF可能与某断言(ASSERTION)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，THEN部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(RULE BASED DEDUCTION SYSTEM)。在这种系统中，通常称每个IF部分为前项(ANTECEDENT)，称每个THEN部分为后项(CONSEQUENT)。  #>%>!规则正向演绎系统  !、定义  　　正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从IF到THEN的方向进行推理的。  @、正向推理过程  　　（!）事实表达式的与或形变换  　　把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似。  　　注意：我们不想把这些事实化为子句形，而是把它们表示为谓词演算公式，并把这些公式变换为叫做与或形的非蕴涵形式。  　　例：有事实表达式  　　　　(U)(V)｛Q(V，U)∧～［(R(V)∨P(V))∧S(U，V)］｝把它化为  　　　　Q(V<A)∧｛［～R(V)∧～P(V)］∨～S(A<V)｝  　　对变量更名标准化，使得同一变量不出现在事实表达式的不同主要合取式中，得：  　　　　Q(W<A)∧｛［～R(V)∧～P(V)］∨～S(A<V)｝  　　（@）事实表达式的与或图表示  　　将上例与或形的事实表达式用与或图来表示，见图#>!。  图 #>! 一个事实表达式的与或树表示  　　一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。上节的与或图表示，就是按通常方式画出的，即目标在上面。  　　（#）与或图的F规则变换  　　这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。把允许用作规则的公式类型限制为下列形式：  L→W  　　式中：L是单文字；W为与或形的唯一公式。  　　将这类规则应用于与或图进行推演。假设有一条规则L+>W，根据此规则及事实表达式F(L)，可以推出表达式F(W)。F(W)是用W代替F中的所有L而得到的。当用规则L+>W来变换以上述方式描述的F(L)的与或图表示时，就产生一个含有F(W)表示的新图；也就是说，它的以叶节点终止的解图集以F(W)子句形式代表该子句集。这个子句集包括在F(L)的子句形和L+>W的子句形间对L进行所有可能的消解而得到的整集。该过程以极其有效的方式达到了用其它方法要进行多次消解才能达到的目的。  　　（$）作为终止条件的目标公式  　　应用F规则的目的在于从某个事实公式和某个规则集出发来证明某个目标公式。在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式。用文字集表示此目标公式，并设该集各元都为析取关系。  　　结论：  　　当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。  #>%>@ 规则逆向演绎系统  !、定义  　　基于规则的逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实的操作过程，从THEN到IF的推理过程。  @、逆向推理过程  　　（!）目标表达式的与或形式  　　逆向演绎系统能够处理任意形式的目标表达式。首先，采用与变换事实表达式同样的过程，把目标公式化成与或形。  　　（@）与或图的B规则变换  　　B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为  W→L (#>$)  形式的表达式。其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。  　　（#）作为终止条件的事实节点的一致解图  　　逆向系统成功的终止条件是与或图包含有某个终止在事实节点上的一致解图。  提问：逆向推理与正向推理的区别有哪些？  #>%># 规则双向演绎系统  !>基于规则的正向演绎系统和逆向演绎系统的特点和局限性 　　正向演绎系统能够处理任意形式的IF表达式，但被限制在THEN表达式为由文字析取组成的一些表达式。逆向演绎系统能够处理任意形式的THEN表达式，但被限制在IF表达式为文字合取组成的一些表达式。双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。  @>双向 (正向和逆向)组合演绎系统的构成 　　正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正。  #>终止条件  　　组合演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。当用F规则和B规则对图进行扩展之后，匹配就可以出现在任何文字节点上。  　　在完成两个图间的所有可能匹配之后，目标图中根节点上的表达式是否已经根据事实图中根节点上的表达式和规则得到证明的问题仍然需要判定。只有当求得这样的一个证明时，证明过程才算成功地终止。若能够断定在给定方法限度内找不到证明时过程则以失败告终。  #>^ 产生式系统  教学内容：本节介绍产生式系统的定义、组成和推理技术。  教学重点：产生式系统与规则演绎系统的差别和产生式系统的组成。  教学难点：产生式系统的控制策略等。  教学方法：课堂教学和实验相结合。重点讲解原理，通过实验进一步领会系统的精髓。充分利用网络课程中的多媒体素材来表示抽象概念。  教学要求：掌握产生式系统的组成结构，通过实践掌握产生式系统的设计和工作过程。  　　定义：  　　在基于规则系统中，每个IF可能与某断言(ASSERTION)集中的一个或多个断言匹配，THEN部分用于规定放入工作内存的新断言。当THEN部分用于规定动作时，称这种基于规则的系统为反应式系统(REACTION SYSTEM)或产生式系统(PRODUCTION SYSTEM)。  提问：产生式系统与规则演绎系统有什么区别？  #>^>! 产生式系统的组成  !>产生式系统的组成 　　产生式系统由#个部分组成，即总数据库(或全局数据库)、产生式规则和控制策略，如图#>@所示。   图#>@ 产生式系统的主要组成  　　总数据库 有时也被称作上下文，当前数据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。例如在上述例子中，在得出该动物是食肉动物的结论之前，必须在总数据库中存有“该动物是哺乳动物”和“该动物吃肉”这两个事实。执行产生式规则的操作会引起总数据库的变化，这就使其他产生式规则的条件可能被满足。   　　产生式规则是一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性，将对产生式系统的运行效率和工作性能产生重要影响。  　　控制策略为一推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。产生式系统的控制策略随搜索方式的不同可分为可撤回策略、回溯策略、图搜索策略等。  @>产生式系统的控制策略  　　控制策略的作用是说明下一步应该选用什么规则，也就是如何应用规则。通常从选择规则到执行操作分#步：匹配、冲突解决和操作。  　　（!）匹配  　　在这一步，把当前数据库与规则的条件部分相匹配。如果两者完全匹配，则把这条规则称为触发规则。当按规则的操作部分去执行时，称这条规则为启用规则。被触发的规则不一定总是启用规则，因为可能同时有几条规则的条件部分被满足，这就要在解决冲突步骤中来解决这个问题。在复杂的情况下，在数据库和规则的条件部分之间可能要进行近似匹配。  　　（@）冲突解决  　　当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。  　　（#）操作  　　操作就是执行规则的操作部分，经过操作以后，当前数据库将被修改。然后，其他的规则有可能被使用。  #>^>@ 产生式系统的推理  !>正向推理 　　从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。  　　一般策略：先提供一批事实（数据）到总数据库中。系统利用这些事实与规则的前提相匹配，触发匹配成功的规则，把其结论作为新的事实添加到总数据库中。继续上述过程，用更新过的总数据库的所有事实再与规则库中另一条规则匹配，用其结论再次修改总数据库的内容，直到没有可匹配的新规则，不再有新的事实加到总数据库中。  @>逆向推理   　　从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。 　   　　一般策略：首先假设一个可能的目标，然后由产生式系统试图证明此假设目标是否在总数据库中。若在总数据库中，则该假设目标成立；否则，若该假设为终叶（证据）节点，则询问用户。若不是，则再假定另一个目标，即寻找结论部分包含该假设的那些规则，把它们的前提作为新的假设，并力图证明其成立。这样反复进行推理，直到所有目标均获证明或者所有路径都得到测试为止。  #>双向推理  　　双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。  #>^>#产生式系统举例  说明：请同学们课后认真阅读本部分内容，并以此为参考进行实验准备！  思考：规则演绎系统和产生式系统有哪几种推理方式?各自的特点为何?  #>& 系统组织技术  教学内容：系统组织技术属于高级搜索推理技术，能够用于求解比较复杂的系统。本节简要介绍三种系统组织技术：议程表法、黑板法和△极小搜索法。  教学重点：系统组织技术如何实现模块之间的合作。  教学难点：无要求。  教学方法：课堂教学。  教学要求：了解系统组织技术的基本原理。  #>&>!议程表  !>定义 　　议程表(AGENDA)是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。  @>模块间的合作  　　从组织大系统的观点看，议程表方法的意义在于它允许几个独立模块进行通讯。其通讯方法是每个模块可将支持(或反对)某个具体任务的证据，加到一个证明选择该任务是正确的表中。这样就使系统能够选出从各方面都有充分证据的任务。虽然各模块共同使用关于为什么要执行各项任务的证据，但一个模块并不需要了解其它模块如何工作，以及它们所包含的知识。这样，议程表方法便具有大系统中模块化的一切优点，而无相互隔离的缺点。  #>&>@黑板法  !>定义 　　黑板法(THE BLACKBOARD APPROACH)首先是在HEARSAY_Ⅱ语音理解系统中发展起来的。它的思想比较简单。整个系统由一组称为知识资源(KS)的独立模块和一块黑板组成。这里，知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。  @>模块间的合作  　　当一个KS被激发时，它检查当时黑板上的内容，并应用其知识产生一个新的假设写到黑板上，直到完成任务为止。当时间表没有发现未解决的活动记录时，系统便停止执行。  #>&># Δ_极小搜索法  !、定义  　　Δ值表示一假设的级别与参加竞争的最佳假设的级别之差，提供了一种选择最有希望假设的技术。  @、工作过程   　　一次接受一串输入，顺序地处理，使其形成一个关于输入的统一而相容的解释。Δ_极小法是这样来解决这类问题的：在适当的时刻，触发某KS，然后为它生成所有它认为是可能的假设，并赋给某个假设一种级别。由这些级别计算出的Δ值，表示一假设的级别与参加竞争的最佳假设的级别之差。而在该假设最后导致不相容时，再考虑参加竞争的另一假设。  #>* 不确定性推理  教学内容：本节介绍两种不确定性(UNCERTAINTY)，即关于证据的不确定性和关于结论的不确定性。  教学要点：不确定性如何表示和推理。  教学难点：不确定性的推理。  教学方法：课堂教学为主。  教学要求：了解不确定性的表示和推理方法。  #>*>!关于证据的不确定性  !>不确定性的表示 　　一般通过对事实赋于一个介于)和!之间的系数来表示事实的不确定性。!代表完全确定，)代表完全不确定。这个系数被称为可信度(也有一些专家系统，如MYCIN和EXPERT等，取可信度的范围为_!到+!)。  @>不确定性的处理  　　当规则具有一个以上的条件时，就需要根据各条件的可信度来求得总条件部分的可信度。已有的方法有两类：  　　（!）以模糊集理论为基础的方法  　　按这种方法，把所有条件中最小的可信度作为总条件的可信度。这种方法类似于当把几根绳子连接起来使用时，总的绳子强度与强度最差的绳子的相同。  　　（@）以概率为基础的方法  　　这种方法同样赋予每个证据以可信度。但当把单独条件的可信度结合起来求取总的可信度时，它取决于各可信度的乘积。  #>*>@关于结论的不确定性  !、不确定性的表示  　　关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在)和!之间的系数的方法来表示的。  　　例：有以下规则：  　　如果 启动器发生刺耳的噪声那么这个启动器坏的可能性是)>%。  　　以上规则表示，如果“启动器发生刺耳的噪声”这事实完全肯定的可信度为!>)，那么得出“这个启动器坏”的结论的可信度为)>*。  @、不确定性的处理  　　如果规则的条件部分不完全确定，即可信度不为!时，如何求得结论的可信度的方法有以下两种：  　　(!)取结论可信度为条件可信度与上述系数的乘积。 　　(@)按照某种概率论的解释，我们假设规则的条件部分的可信度 CIN 和其结论部分的可信度 COUT 存在某种关系，这种关系可用来代表规则的不确定性。  #>*>#多个规则支持同一事实时的不确定性  　　当多个规则支持同一事实时，这些规则之间的关系是析取。如何根据证据的可信度求得事实的可信度? 与关于证据的可信度类似，也有两种方法，分别基于模糊集理论和概率理论。  !>基于模糊集理论的方法   　　取支持这个事实的各规则的可信度的最大值作为事实的可信度。  @>基于概率论的方法   　　这里介绍的只是基于概率的方法中的一种。按这种方法由一组规则支持的事实的可信度，可用以下方法求得，首先把各个证据的可信度转换成可信性比例R。可信性比例R和可信度C之间的关系可表示为  　　把各证据的可信性比例简单地相乘就可以求得这些证据所支持的事实的可信性比例。然后，再利用上述公式转换回相应的可信度。这样就求得这个事实的可信度。  #>( 非单调推理  教学内容：用于解决现实问题领域中的#类情况：不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。本节简要介绍两种非单调推理技术：缺省推理和正确性维持系统TMS。  教学要点：缺省推理和正确性维持系统TMS的基本原理。  教学难点：无特别要求。  教学方法：课堂教学。  教学要求：了解缺省推理和正确性维持系统TMS的基本原理。  #>(>!缺省推理  !>定义 　　当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(DEFAULT REASONING)。  　　缺省推理的定义!：如果X不知道，那么得结论Y。  　　缺省推理的定义@：如果X不能被证明，那么得结论Y。  　　缺省推理的定义#：如果X不能在某个给定的时间内被证明，那么得结论Y。  @>例子  　　一个安排会议程序：程序必须求解一个约束满足问题，即找出每个参加者都有空闲的开会日期与时刻，并有可供开会的房间。  #>(>@非单调推理系统  !>正确性维持系统 (TRUTH MAINTENANE SYSTEM<TMS) 　　这是一个已经实现的非单调推理系统。它用以协助其它推理程序维持系统的正确性，所以它的作用不是生成新的推理，而是在其它程序所产生的命题之间保持相容性。一旦发现某个不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。  @>工作原理  　　在TMS中，每一命题或规则均称为节点，且对任一节点，以下两种状态必居其一：   IN 相信为真   OUT 不相信为真，或无理由相信为真，或当前没有可相信的理由。  　　IN节点是指那些至少有一个在当前说来是有效证实的节点。OUT结点则指那些当前无任何有效证实的节点。  　　在系统中，有两种方式可用来证实一个节点的有效性可依赖于其它节点的有效性：  　　(!) 支持表 (SL (IN_节点) (OUT_节点))  　　(@) 条件证明 (CP (结论)  　　(IN_假设)  　　(OUT_假设))  #>!) 小 结  　　对本章讨论过的各种搜索推理技术加以归纳总结。  FROM: HTTP:??NETCLASS>CSU>EDU>CN?JPKC@))#?RENGONGZHINENG?RENGONGZHINENG?JIAOAN?CHAPTER#>HTM