博文
人工智能书评二则
||||
建立人工智能的数学体系
——介绍《Logical Foundations of Artificial Intelligence》
王飞跃
在人工智能三十多年的历史中，有关这一学科的性质，基本问题和方法的争论从未间断过。大体上，从事人工智能的研究者可分两个学派，即所谓的“纯净”派（Neats）和所谓的“邋遢”派（Scruffies）。“纯净”派认为要建立一个人工的智能系统，必须首先彻底地了解其形式上的特点；他们倾向于以数学为解析工具来研究人工智能。而“邋遢”派则采取比较“进化”的观点，他们不太关心证明，认为最紧要的是干下去，先建立这样的系统再说；启发性的智能程序设计，是他们的主要手段。两派争论的焦点之一就是单纯的程序设计能不能作为人工智能的理论基础（Partridge 1987）。当然，从理论上揭示智能的性质，在工程上建立智能机器，是所有人工智能研究者的共同目标（Schank 1987）。
以数理逻辑（Mathematical Logic）为工具来表示和研究智能系统的形式特性是“纯净”学派的基础出发点之一。从20世纪60年代的Robinson归结原理到现在的非单调推理，关于这一方面的研究已取得许多成果与进展。美国Stanford大学的Genesereth和Nilsson教授的新著Logical Foundations of Artificial Intelligence正是有关这方面研究的最新、最全面的总结。
全书共三十章，外加一个题解附录。前十章详细介绍了以数理逻辑为基础研究人工智能的主要方法、问题和结果。其中前五章（引言、陈述性知识、推理、归纳、归结策略）是经典数理逻辑的内容，主要讨论了概念化结构、谓词演算等陈述性知识（Declarative Knowledge）的表示形式，以及以归结原理为主的推理方法。这部分的内容同Nilsson的前一部著作(Nilsson 1980)的对应部分基本相同。第六章（非单调推理）详细地介绍了数理逻辑的新近发展¾非单调推理理论。作者论述了封闭世界假设、谓词完备化和界限（Circumscription）等处理限定问题（Qualification Problem）的方法、相关的问题及一致性结果。本章基本概况了目前关于非单调推理的主要研究结果。由于几乎所有的人工智能问题都设计某种形式的非单调推理，有关这方面的结果十分重要；实际上，可以认为非单调推理理论标志着动态应用数理逻辑的开始。第七章（归纳）以概念构成（Concept Formation）和试验生成（Experiment Generation）为主介绍了归纳方法。许多机器学习理论都是以这两种方法为基础的。第八章（不确定信念下的推理）讨论了不确定推理的概率方法，这些方法在实际专家系统的设计中十分有用。本章的内容主要以Nilsson等发展的概率逻辑为主，对专家系统和其它问题中日益广泛应用的模糊逻辑和Dempster-Shafer证据理论没有叙及。第九章（知识与信念）讨论了知识与信念（Belief）的表示与推理证明，主要介绍了Knonolige的命题逻辑（Sentential Logic）和Krikpe的可能世界逻辑（Possible-Worlds Logic）两种模态逻辑方法及发展。有关知识与信念的研究涉及许多哲学上的知识问题，这方面的结果将有助于我们加深对知识的理解，更好地处理常识性知识。第十章（元知识和元推理）实际上涉及有关高阶逻辑理论的内容，即对元知识的元推理。本章给出了与相应的一阶理论结果并行的高阶理论结果（合一算法、归结原理等）。这两章所涉及的研究还在发展，应用结果也不很多。在最后的三章中，作者以前十章的结果为基础讨论了智能系统的结构，有关状态和行动，以及规划的知识的表示。第十一章（状态与变化）介绍了状态与变化知识的表示，包括框架（画画）问题和行动理论。第十二章（规划）主要讨论了基于归结方法的规划产生，以及各种改进规划效率的方法。在最后一章中，介绍了几种基本的智能系统结构，并详细地讨论了一些系统的忠实性（Fidelity，即只执行指定的行动，避免禁止的行动），从示如何用逻辑的方法对智能系统的行为进行分析。本书每一章的后面都附有文献和历史评述，提供问题的背景和有关的研究工作。作者引用了366篇文献，对研究者来说，这是十分有价值的参考资料。每篇最后的习题，也有助于读者加深对内容的理解。
基本上，这部专著是现有研究成果的集成，对于许多问题的讨论，并不十分深入。这实际上也反映了这方面研究的现状。不管怎样，它的出版无疑朝向建立人工智能的完备的数学体系的重要一步。可以说，对每一个从事这方面研究的学者，这是一本必备的参考书。
一个完备的人工智能数学体系的建立，将为人工智能的研究提供一个坚定的基础和更完善的标准（McCarthy 1984）。这一基础和标准，必将使“人工智能”一词免于变为一个失去价值的陈腐标签的危险（Partridge 1987）。然而，同其它数学分支不同，由于数理逻辑从开始就是以抽象概念为研究对象，而内在的组合爆炸问题又使它在具体系统中的应用长期没有大的突破，以致有人称其一片“不育之地”（Vamos 1987）。人工智能的发展虽使之渐发生机，但是要在这片“不育之地”上结出丰硕的果实，使之真正成为人工智能数学体系的基石，还需要研究者们的长期不懈努力。
Genesereth, M.R. and Nilsson, N.J., Logical Foundations of Artificial Intelligence, Morgan Kaufmann Publishers Inc., Los Altos, C. A., 1987.
McCarchy, J. President’s Message: We Need Better Standards for AI Research, AI Magazine, Vol.5, No.3, pp.7-11, 1984.
Nilsson, N.J. Principles of Artificial Intelligence, Morgan Kaufmann Publishers Inc., Los Altos, C. A., 1980.
Partridge, D. Workshop on the Foundations of AI: Final Report, AI Magazine, Vol.8, No.1, pp.55-59, 1987.
Schank, R. C., What is AI, AnyWay?, AI Magazine, Vol.8, No.4, pp.56-66, 1987.
Vamos, T. Metalanguages-Conceptual Models: Bridge Between Machine and Hunman Intelligence”, Proc. 1st International Symposium on AI and Expert Systems, Berlin, pp.237-287, 1987.
本文发表于1989年《计算机科学》第2期
—————————————————————————————————————————————————————
逻辑程序：第五代计算机的语言
——介绍Foundations of Logic Programming第二版
王飞跃
从1974年Kowalski提出“谓词逻辑作为程序设计语言”的著名观点至今，逻辑程序设计已有了自己的一套严整的理论和一批实际程序系统，其中影响最大的是Prolog。尤其是在日本人决定在其雄心勃勃的十年规划中，以逻辑程序作为联接知识信息处理和并行计算机结构的“桥梁”，使之成为目标中的第二代计算机的核心语言之后，更是大大推动力着这方面的研究（有关1985年初之前的文献请参见Balbin与Lecot合编的Logic Programming：a Classified Bibliography）。
然而，真正了解逻辑程序的人并不多。甚至在许多人眼里，“逻辑程序”一词具有“万能”的神秘色彩。造成这种现象的主要原因之一就是人们对逻辑程序的期望太多，把广义的逻辑和狭义的逻辑（如Horn从句）混淆起来。特别是许多有关著作都是从实际程序设计的角度来介绍逻辑程序，不但没能对此予以澄清，反而留下更多的问号。澳大利亚Lloyd教授所著Foundations of Logic Programming（以下简称为《F》）一书的第一版（Springer 符号计算——人工智能专注丛书之七，1984），是第一本全面严格地介绍逻辑程序设计理论的著作。
《F》的第二版于1987年出版，比起第一版，新版增加了70%的新内容，并有很强的数据库特色，其中第四、五章是新添的，前三章的内容也作过修改和调整。第二章补进了关于任何可计算函数都可由某一限定程序来计算的证明。新版基本反映了近年逻辑程序设计研究的新成果。这些新成果，有的业已实施，更多的正在孕育着程序技术的新突破。
新版共六章，按数学基础（第一章），逻辑程序理论（第二、三、四、六章）和在数据库中的应用（第五章）三个主题展开。每章之后都附有许多习题，书末给出了有关的112篇参考文献。第一章：准备知识，在简洁介绍逻辑程序的发展史后，作者给出了逻辑程序的数学基础概念和理论，即一阶理论、解释与模型。合一算法和不定点理论，其中与逻辑程序最密切相关的概念是逻辑结论，Herbrand解释与模型，完全格点上的映射的最大与最小不动点，和限定程序，即体（body）全为肯定文字的程序语句的有限集合。第二章，限定程序（Definite Programs），本章讨论了限定程序设计理论的最基本材料。可以说，掌握了本章的内容，对Prolog的理论实质就清楚了。限定程序的陈述性定义是由其最小Herbrand模型刻画的。本章首先证明了一个限定程序的最小Herbrand模型恰好是其基本原子逻辑结论的结合，并且等于其Kowalski映射的最小不动点。在陈述性语义中，一个限定程序和限定目标的输出是由正确答案，即程序和目标的逻辑结论来描述的，而在过程语句中与之对应的概念是计算答案。过程语义由SLD（亦称LUSH）归结原理所定义的。本章证明了每一个计算答案都是正确的，反之，每一个正确答案都是一个计算答案的特例，从而建立SLD归结原理的有效性和完备性，即SLD只产生正确答案，并且是所有的正确答案。本章另两个重要结果是：计算规则的无关性，即SLD归结的反演是否与计算规则的选择无关；以及任何可计算的函数都可由某个限定程序来计算，这个结论显示了限定程序的计算威力，换言之，逻辑程序与通常的程序（如Fortran等）理论上具有同等的计算能力。此外，本章还从理论上讨论了Prolog中的两个实际问题；即在合一算法中略去查名（occur check，变量名检查之意）和在SLD树搜索中采用Cut。略去查名是因为它实际上很少需要，但带与不带查名步骤会使合一算法的计算复杂性从指数复杂退为线性复杂，但略去查名后，SLD的有效性不再成立。同样，引入Cut是为了避免搜索SLD树时出现无限循环，但它的使用却破坏了SLD的完备性。因此，通常的Prolog系统并不是绝对完善的。第三章：标准程序（Normal Programs）。本章试图将第二章的结果推广到标准程序，即体中允许否定文字出现的程序语句的有限集合。由于一个程序的逻辑结论只能是肯定性的，要推导否定性的结论必须引入一些特别的规则。作者主要讨论了三种这个否定规则：Reiter的封闭世界假设（CWA），Clark的否定作为失败（NF），和程序的完备性（CP）。对于标准程序，主要的研究对象是它的完备性，而不是其本身。因此，关于标准程序的推理不是单调的，即新的公理的引入会使一些定理不再成立。但是对于限定程序，其完备化所导出的任何肯定性结论都与由它本身所导出的结论相同，所以对限定程序，就肯定性结论而言，推理仍是单调的。在标准程序的陈述性语义中，一个程序和标准目标的输出，即正确答案被定义为其完备化和目标的逻辑结论，而对应的过程语义概念，即计算答案，由SLDNF归结原理（SLD加NF）定义。在SLDNF中，为了保证有效性，在选取目标的否定文字时引入了“安全性条件”，即只有基本的否定文字才可以选，安全性条件确保了NF和SLDNF的有效性，但它使得NF变为纯粹的检验，不产生任何的变量结合。与有效性相比，关于SLDNF的完备性结果却很不理想，本章只证明了对于限定程序和目标，以及对于采用完全计算规则的阶层（Hierarchical）标准程序和一般标准目标、NF的完备性。然而，由阶层条件禁止了任何的递归形式，这些结果不是很有用。鉴于NF和SLDNF完备性在理论和应用上的重要性，对这方面的新结果的要求十分迫切。目前最希望得到的是对分层（Stratified）标准程序的SLDNF的完备性结果。本章还讨论了Cut对SLDNF的影响。我们看到，Cut不但破坏了SLDNF的完备性，同时也破坏了它的有效性。第四章：一般程序（Programs）。一旦在程序语句体中允许否定文字的出现，就不应再限制一般形式的语句体，因为理论上任一个阶公式都与一个前束合取形式逻辑上等价。本章正是按这种思想将第三章的结果推广到一般程序，即体为任意一阶公式的程序语句的有限集合。一般程序的引入，主要是增加逻辑程序的表达能力，使之能更方便地用于专家系统、数据库和通用程序的设计等。本章通过将一般程序转变为某个标准程序（称为标准形），证明了对一般程序和目标的ＮＦ和SLDNF的有效性，以及对阶层一般程序SLDNF的完备性，这一章的另一部分是关于陈述性错误诊断问题，并给出了一个诊断器，它可用以检查采用高级控制机制和一般语句的和程序的错误。这部分首先是有关错误的定义及其形式化，证明程序的不正确只能是两种情况：存在没有包括的原子公式或不正确的语句基例，然后证明了所给的诊断器的有效性和完全性，即诊断器的每一个解都给出程序的一个没有包括的原子公式或不正确的语句基例，反之，程序的每一个错误答案或漏丢的答案都对应着诊断器的一个解，当然，诊断器不能用来发现导致无限循环之类的错误。陈述性错误诊断是实现纯粹陈述性程序设计（逻辑程序的最诱人之处）所不可少的，它的使用可实现在不了解系统的计算机制，只知道程序的预期解释的情况下，进行程序调试。第五章，演绎数据库（Deductive Database）。自Reiter首先从逻辑的观点考察了数据库以来，在这方面已经获得了许多重要结果。理论方面，逻辑程序的证明方式将数据库理论纳入一般的一阶理论，从而能够证明方式将数据库理论纳入了一般的一阶理论，从而能够自然地将关系数据库理论纳入了一般的演绎数据库，并为数据库系统提供一整套的数学理论。应用方面，逻辑的使用扩大了数据的表示能力，简化了表示方式，并为数据表示，询问，完整性结束（IC），程序设计等提供了一个统一的语言。特别重要的是，逻辑程序的方式促进了陈述与过程性概念的分离，而陈述性定义给出了一个量度实施方法的正确性的标准，实际上，不将陈述性概念分离出来，连有效性和完备性定理也无从表述。本章首先将演绎数据库的基本概念，如数据库、询问、正确答案和IC等形式化，表明数据库只是程序语句体为类型化一阶公式的一般程序而已，从而开劈了直接将一般程序理论应用于演绎数据库的途径，采用类型化公式（Typed Formulas），只是为了能表示关系数据库中的域（domain）的概念，但实际上类型化公式可直接转变成一般的无类型公式，将类型化公式转为无类型公式后，第五章有关一般程序的SLDNF的有效性和完备性结果就可以修正为相应的演绎数据库询问赋值过程的有效性和完备性结果，但是，如果在数据库完备化的定义中不包括附加的域闭合公理，询句赋值的有效性就不再成立。本章还证明了决定一个数据库是满足还是违反IC的标准方法的有效性，并给出了一个检查IC的简化方法及其有效性证明。简化方法的基本思想是利用修正前的数据库满足IC。再检查修正后的数据库是否继续满足IC，在检查修正后的数据库是否继续满足IC时，只查IC的一些基例，而不是IC全部。作者还讨论了如何引入停止规则以避免在检查IC时出现无限循环。应指出的是，在简化检查方法中，主要的计算只涉及数据库中的规则，而与其中的事实无关，但对于多数据库来说，其规则数据目远小于事实数目。本章所给出的多数是作者自己的最新研究结果，鉴于关系数据库的巨大成功，作者预言几年后一定会出现有商用价值的演绎数据库，10年后演绎数据库将会像关系数据库为目前的标准的数据库一样，成为下一个时代的标准数据库。第六章，永久过程（Perpetual Processes）。永久过程是指永不停止，却在某种意义下作看有用计算的限定程序。所谓的“某种意义”是针对在无穷远处可计算这一概念而言的，比如Fibonacci序列就是无穷远处可计算的，但它是无限的，所以它的计算过程只能是永久的。本章首先利用树结构给出无限项的定义，并证明无限项空间是一个（超）度量空间，当且仅当项空间的符号集是有限时，空间才是紧的。基于无限项空间，作者引入了完备的Herbrand论域，基，解释和模型等概念。所谓“完备”是相对于项空间（或由其诱导出）的拓扑结构说的。因为在拓扑的意义下，完备的Herbrand论域等是基于有限项的对应Herbrand概念的完备性，反之，有限项的Herbrand论域等是对应的无限项的Herbrand概念的非紧稠密子集。同在有限项时一样，Kowalski映射在永久过程的分析中起着十分重要的作用，而且，完备Herbrand论域和基的紧与完备性又使它具有更加丰富的特性。其中最显要的性质是其最大不动点等于项元的有限变换的最大下界。这一结果对偶于有限项时，其时小不动点为底元的有限变换的最小上界的结果，但它在有限项情况下并不成立。由于这一性质，使映射的最大不动点成为永久过程的预期解释，与有限项时限定程序以最小不动点作为预期解释相呼应。本章的主要结果是证明了永久过程的SLD归结的有效性，即所有远穷远处可计算的原子公式的集合属于Kowalski映射的最大不动点，再次与有限项时限定程序的成功原子公式集合等于最小不动点的结果类似。然而，正是“属于”与“等于”的差别使得永久过程的SLD的完备性不再成立，要得到SLD的完备性，必须进一步引入限制条件。目前，关于永久过程的研究还在进行，本章留下许多问题没有解答，特别是在语义方面。但这里的结果可做为进一步研究的基础，随着Prolog在并行系统，特别是操作系统中的应用的深入，将会有越来越多的程序成为永久过程，因此，可以期望，关于永久过程的结果不久就会完备。
综观全书，《F》的组织结构十分简洁和清楚，使读者能在大片的定义定理的背后体会到问题的核心和结构的意义，特别地，除了最后一章，书中没有用到太深的数据学方法，其中归纳法从头使用到尾。当然，本书也有一些小的不足之处，比如，没有讨论更好的合一算法，没有说明Prolog的严格语义和功能，也没有给出较有趣的程序例子。但总的说，本书可以称得上是一本优秀的教学和研究参考书；随着时间的流逝，它不但不会被遗忘，反而会成为这一领域的经典之著。
Logic Programming: The language for the Fifth Generation Computers
——Review 《Foundations of Logic Programming》 2nd Edition
本文发表于1989年《计算机进展》
读书荐书
https://m.sciencenet.cn/blog-2374-452612.html
上一篇：给AAAI大会的25岁生日礼物： 人工智能需要重启？
下一篇：读报的“代价”
