《人工智能与知识工程搜索推理技术2》由会员分享，可在线阅读，更多相关《人工智能与知识工程搜索推理技术2（121页珍藏版）》请在金锄头文库上搜索。
1、1,3.5 消解原理 3.6 规则演绎系统 3.7 产生式系统 3.8 系统组织技术,3搜索推理技术,2,推理的基本概念,推理是指按照某种策略从已知事实出发去推出结论的过程。其中，推理所用的事实可分为两种：一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论。通常，智能系统的推理过程是通过推理机来完成的。所谓推理机就是智能系统用来实现推理的那些程序。 例，在医疗诊断专家系统中，所有与诊断有关的医疗常识和专家经验都被保存在知识库中。当系统开始诊断疾病时，首先把病人的症状和检查结果放到事实库中，然后再从事实库中的这些初始证据出发，按照某种策略在知识库中寻找可以匹配的知识，如果得到的是
2、一些中间结论，则需要把它们作为已知事实放入事实库中，并继续寻找可以匹配的知识，如此反复进行，直到推出最终结论为止。由初始事实出发到推出最终结论的过程就是推理，实现这一推理过程的程序称为推理机。,3,推理的基本概念（续）,智能系统的推理包括两个基本问题：一个是推理的方法；另一个是推理的控制策略。 推理方法主要解决在推理过程中前提与结论之间的逻辑关系，以及在非精确性推理中不确定性的传递问题。,4,推理的基本概念（续）,1. 按推理的逻辑基础分类 按照推理的逻辑基础，常用的推理方法可分为演绎推理、归纳推理和默认推理。 (1)演绎推理。 演绎推理是从已知的一般性知识出发，去推出组合在这些已知知识中适合
3、于某种个别情况的结论的过程。它是一种由一般到个别的推理方法，其核心是三段论，即假言推理、拒取式推理和假言三段论。常用的三段论是由一个大前提、一个小前提和一个结论三部分组成的。其中，大前提是由已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；结论是由大前提推出的，并且适合于小前提的判断。,5,推理的基本概念（续）,（2）归纳推理 归纳推理的前提是一些关于个别事物或现象的命题，而结论则是关于该类事物或现象的普遍性命题。归纳推理的结论所断定的知识范围超出了前提所断定的知识范围，因此，归纳推理的前提与结论之间的联系不是必然性的，而是或然性的。也就是说，其前提真而结论假
4、是可能的，所以，归纳推理是一种或然性推理。 基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认。 如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理。,6,推理的基本概念（续）,3)默认推理。 默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理，因此也称为缺省推理。在推理过程中，如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论，重新对新情况进行推理。由于默认推理容许在推理过程中假设某些条件是成立的，这就解决了在一个不完备的知识集中进行推理的问题。,7,推理的基本概念（续）,2. 按照所用知识的确定性分类 确定性推理和不确定性推理
5、 3. 按推理过程的单调性分类 按照推理过程的单调性，或者说按照推理过程所得到的结论是否越来越接近目标，推理可分为单调推理与非单调推理两类。 4. 按照方法论分类 按照方法论，常见的推理有基于知识的推理、统计推理和直觉推理等。 基于知识的推理，是指根据已掌握的事实，通过运用知识进行的推理。例如：医生诊断疾病时，根据病人症状及检验结果，运用医学知识进行推理，给出诊断结论及治疗方案。 统计推理，是指根据对某事物的数据统计进行的推理。例如，农民根据对农作物产量统计得出是否增产的结论，从而找出增产或者减产的原因。 直觉推理又称为常识性推理，是指根据常识进行的推理。例如，当你猛然发现头上有一物体掉落时，
6、立即会意识到危险，并立即躲开，这就是直觉推理。,8,推理的基本概念（续）,推理的控制策略 智能系统的推理过程相当于人类的思维过程，即求解问题的过程。问题求解的质量与效率不仅依赖于所采用的求解方法，而且还依赖于求解问题的策略，即推理的控制策略。 推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。由于智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。其中，推理策略主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等，,9,推理的基本概念（续）,推理方向用来确定推理的控制方式，即用来确定推理过程是从初始证据开始
7、到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理可分为正向推理、逆向推理、混合推理及双向推理等4种。 求解策略是指仅求一个解，还是求所有解或最优解等。 限制策略是指为了防止无穷的推理，以及推理过程太长而对推理的深度、宽度、时间、空间等进行限制的策略。 冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。目前已有多种消解冲突的策略，其基本思想都是对知识进行排序，比如：按针对性排序；按已知事实的更新程度排序；按匹配程度排序；按产生知识冗余大小排序；按产生结论的条件个数排序等。,10,3.5消解原理,3.5.1 子句集的求取 3.5.2 消解
8、推理规则 3.5.3 含有变量的消解式 3.5.4 消解反演求解过程,11,3.5消解原理(续),知识表示方式: 谓词公式 解决问题: 定理的自动证明 问题的自动求解 消解原理由Robinson于1965年提出，又称为归结原理。 将要证明的前提及结论合并在一起, 化为子句集,利用消解原理对子句集进行消解, 如果得到空子句则成立,否则失败. 例:如果存在某个公理 E1E2 和另一公理E2 E3 ，那么 E1E3 在逻辑上成立。这就是消解，而称 E1 E3 为 E1E2 和E2 E3 的消解式（resolvent ）。,12,3.5.1 子句集的求取,相关概念 文字: 原子谓词公式及其否定统称为文
9、字。 子句: 任何文字的析取式称为子句。 空子句: 不包含任何文字的子句称为空子句。记为：或NIL 子句集:由子句和空子句所构成的集合称为子句集 例: P(x, y)Q(x, y),P(x,y)U(x)V(y),Q(x, y)U(y) 在谓词逻辑中，任一谓词演算公式可以化成一个子句集,13,3.5.1 子句集的求取（续）,子句集的化简步骤: 例: (z)(x)(y)(P(x)Q(x)R(y)U(z) （1）利用等价关系消去蕴涵和双条件符(“”或“”) PQ PQ , PQ ( PQ)( QP ) 对于本例有: ( P(x)Q(x) R(y) ( P(x)Q(x)R(y) (z)(x)(y) (
10、P(x)Q(x)R(y)U(z),14,3.5.1 子句集的求取（续）,（2）减小否定符号的辖域使得否定符只作用于谓词符号(原子公式)。 狄摩根定律和量词转换率 ( PQ ) PQ， ( PQ ) PQ (x) P (x) P， (x) P (x)P 对于本例有: (z)(x)(y) (P(x)Q(x)R(y)U(z),15,3.5.1 子句集的求取（续）,（3）对变量标准化（变元换名） 在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合式公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的
11、哑元。 (x) P (x) (y) P (y) (x) P (x) (y) P (y) 例： (x)A(x)(x)B(x) 化为： (x)A(x)(y)B(y),16,3.5.1 子句集的求取（续）,（4）消去存在量词( skolem化) Skolem函数: 在公式( y)( x)P(x,y)中，存在量词是在全称量词的辖域内，我们允许所存在的x可能依赖于y值。令这种依赖关系明显地由函数g(y)所定义，它把每个y值映射到存在的那个x。这种函数叫做Skolem函数。 如果用Skolem函数代替存在的x,我们就可以消去全部存在量词，并写成： ( y)P(g(y),y) 不在任何全称量词辖域内的存在量
12、词约束的变元用具体没有出现过的常量代替。( x)P(x)化为P(A) 在全称量词辖域内的存在量词约束的变元用新的skolem函数符号代替。 (z)(x)(y)(P(x)Q(x)R(y)U(z) 化为 (x)(P(x)Q(x)R(g(x)U(a),17,3.5.1 子句集的求取（续）,（5）化为前束范式（量词左移） 到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即 前束形 = (前缀) (母 式) 全称量
13、词串 无量词公式,18,3.5.1 子句集的求取（续）,（6）化为合取范式(Skolem标准形) 合取范式: 谓词公式或谓词公式的否定的析取的有限集合组成的合取, 叫做合取范式。 结合律, 分配率 ( PQ )R P( QR ) ( PQ ) R P( QR ) P( QR ) ( PQ ) ( PR ) P( QR ) ( PQ ) ( PR ) 对于本例有: (x)(P(x)Q(x)R(g(x)U(a) 化为 (x)P(x)Q(x)R(g(x)U(a)结合律 化为 (x)P(x)R(g(x)U(a)Q(x)R(g(x)U(a),19,3.5.1 子句集的求取（续）,（7）消去全称量词: 每
14、个全称量词的辖域都是整个公式。 P(x)R(f(x)U(a)Q(x)R(f(x)U(a) （8）消去连词符号（表示为子句集） 方法: 用A,B代替(AB) 对于本例有： P(x)R(f(x)U(a),Q(x)R(f(x)U(a),20,3.5.1 子句集的求取（续）,（9）更换变量名称 使任意两个子句不出现同名的变量。 对于本例有： P(x)R(f(x)U(a),Q(y)R(f(y)U(a),21,3.5.1 子句集的求取（续）,例： (x) P(x) (y) P(y) P(f(x, y)(y)Q(x, y) P(y) 1：消去蕴含符号 (x) P(x) (y) P(y) P(f(x, y)(
15、y)Q(x, y) P(y) 2：减否定符号辖域 (x) P(x) (y) P(y) P(f(x, y)( y)Q(x, y) P(y) 3:对变量标准化 (x) P(x) (y) P(y) P(f(x, y)( q)Q(x, q) P(q) 4：消去存在变量(Skolem函数:q=W(x) (x) P(x) (y) P(y) P(f(x, y)Q(x, W(x) P(W(x) 5:化为前束形 (x) (y) P(x) P(y) P(f(x, y)Q(x, W(x) P(W(x) 6:化为合取范式 (x) (y) (P(x) P(y) P(f(x, y)(P(x) Q(x, W(x) ) (P(x) P(W(x),22,3.5.1 子句集的求取（续）,7:消去全称变量 (P(x) P(y) P(f(x, y)(P(x)
