人工智能17-28讲述.ppt

第17章 基于知识的系统 面对现实世界 用Horn子句进行推理 动态知识库的维持 基于规则的专家系统 规则学习 补充读物和讨论 17.1 面对现实世界 逻辑推理系统有三个主要的理论特性：合理性、完备性和易处理性。为了确信一个推导的结论是真的，需要合理性。为了确信推论最终将产生真的推论，需要完备性。为了确信推论是可行的，需要易处理性。 17.1 面对现实世界 关于谓词演算，归结反驳是合理的和完备的。归结反驳能被用来证明，如果一个合式公式ω被一个合式公式集逻辑涵蕴，那么它是完备的；否则，归结反驳过程可能永不能终止。因此，我们不能用归结作为一个完全的决策过程（decision procedure）。 可以证明没有其他方法总能告诉我们什么时候一个合式公式ω不是由合式公式集合?逻辑地派生，什么时候是。因此，我们说谓词演算是不完全决策的。当然，不完全决策性导致了谓词演算固有的不易于处理性。 即使对那些归结反驳终止的问题，那个过程是NP难题——就像对一阶谓词演算的任何合理和完备推理过程一样。虽然有很多推理问题能被公式化为归结反驳问题，但对非常大的问题，该方法是不易处理的，这个事实导致很多人对在大规模推理问题中使用正式的逻辑方法感到失望。 然而，由于人类进行复杂推理，一定有启发性的和特定的公式允许易处理的计算。 17.1 面对现实世界 第一，我们能在坚持推理规则的合理性前，使用那些偶尔会“证明”一个不正确的公式过程。 第二，在坚持完备性前，使用不能保证找到正确公式证据的过程。这两种修改可以使推理更有效。 第三，我们能使用一种比完全谓词演算表达力弱的语言。 一个表达力弱的语言的例子仅仅使用了Horn子句。使用Horn子句的推理典型地讲更有效，它们可以满足很多应用。 17.2 用Horn子句进行推理 Horn子句定义为至多有一个正文字的子句。如果有至少一个负文字和一个正文字，Horn子句就能被写为一个蕴涵，它的前项是正文字的合取，它的后项是单个正文字，这样的子句被称为一个规则。 λh :- λb1,…, λbn 在子句中可以没有负文字，在这种情况下，我们把它记为一个蕴含，它的前项为空，后项是一个单一正文字，这样的子句被叫做一个事实。 λh :- 或者在子句中可能没有正文字，在这种情况下，我们记作后项为空，前项是一个正文字列表的蕴含，这样的子句称为一个目标。 :- λb1,…, λbn 17.2 用Horn子句进行推理 在PROLOG语言中，这些子句用作该语言的语句，写成如下格式： 规则： λh :- λb1,…, λbn 这是表示蕴含λb1,…, λbn ? λh 的一种特殊形式，每个λi是一个正文字。文字λh叫做子句的头，文字λb1,…, λbn叫做子句的体。 事实： λh :- 目标：:- λb1,…, λbn 目标和规则体中的文字是有序列表，这个顺序在一个PROLOG语言的执行中起到重要的作用 17.2 用Horn子句进行推理 在方框中的节点集对应程序语句（目标、规则及事实）。节点用程序中的文字标识。有两种弧：匹配弧和规则弧。匹配弧把一个规则（或一个目标节点）的一个体节点连向一个等价的另一个规则的标识头节点（或到一个事实）。 在“与或”证明树中，体节点被称为AND节点，因为它们必须被全部证明。 如果有另一个可能的归结，通过一个匹配弧对一个证明树的有哪些信誉好的足球投注网站会产生另外的节点，称为OR节点。 17.2 用Horn子句进行推理 这些PROLOG程序说明了如何将Horn子句规则用于推理问题。在PROLOG语言中，推理“向后”进行，从要建立的目标开始，顺着规则链，最后锚定在事实上。与归结反驳类似 使用目标规则和事实执行这类向后推理的AI系统被称为执行反向链。也可用正向链，在这种情况下，推理向前进行，从事实开始，顺着规则链，最后产生目标。 有一种计算机语言OPS5是基于正向链的。已经用OPS5写出了几个实际有效的推理系统。 17.2 用Horn子句进行推理 在正向链系统中，如果一个规则的前项文字的每一个都能与一个相应的事实（用一致的置换）合一，那么它是可应用的。由于事实是基本原子，变量仅出现在可被合一的一对表达式中。这种受限的合一形式常叫做模式匹配。 当可应用多于一个规则时，某些外部冲突归结被用来决定将应用哪个规则。 当有大量的规则和事实时，必须被尝试的合一数量成为障碍。OPS5使用一个叫RETE的算法过程。 17.3 动态知识库的维持 我们能延伸扩展行以包含任何数量的前提和规则，这样一个结构可作为一种动态知识库。推理过程被机制化，与显示的单元值无关。 考虑一个命题演算原子知识库。用原子“前提”（premiss）代替事实，因为我们想能够推理各种“假设分析”的可能性。 一个规则的正向推理链允许我们把R和S作为新原子加到KB中。考虑到这