|
||||
|
||||||||
归纳推理 吉林大学计算机系 李爱中李爱中 |
|
归纳推理的含义 归纳推理（ｉｎｄｕｃｔｉｖｅ ｉｎｆｅｒｅｎｃｅ）是一个从部分到整体、从特 殊到一般、从个体到全体的推理过程（引自Ｗｅｂｓｔｅｒ’ｓＤｉｃｔｉｏｎａｒｙ） 。 对归纳推理的研究可以追溯到亚里士多德（Ａｒｉｓｔｏｔｌｅ）。他把知识分成两 类：一种是可以通过演绎来证明的；另一种是不能通过演绎来证明的，作为演绎的原始的 前提的知识，只能通过归纳来获得。归纳是演绎的基础，没有归纳就没有演绎。归纳推理 可以发现全新的一般性的知识或假说；而演绎虽不可能发现全新的知识，却可以使已蕴含 在前提之中的知识得到明确的表达。故此，没有演绎，归纳的结果的应用势必受到限制。 为此，归纳和演绎是相辅相承、缺一不可的。 同演绎相比，对归纳的研究还不成熟。演绎推理的结论具有逻辑上的保真性，即从正 确的前提可以演绎出正确的结论并称之为定理。而归纳推理的结论却具有或然性，它只能 保证在当时情形下为真而非永真，故此一般称归纳的结果为假说。对于归纳，一直是争论 众多，同时也是一个特别活跃的研究领域。在人工智能领域中研究归纳推理是不可避免的 。 人工智能的目标是建造基于知识的智能系统。为此，必须建造知识库以使机器能利用 知识。然而，知识获取和知识集成已被公认为“瓶颈”，阻碍了智能系统的建立及其功能 的提高，其原因在于人类专家所具备的仅是大量的经验或不完整的知识，并且很难人为地 转换成计算机可用的形式。 另外，随着数据处理技术的快速发展，已使得大型数据的系统化组织成为很方便的日 常活动。因而使得直接从大量数据中自动地开发或求精知识成为了可能。 从大量数据中自动地归纳出知识不但是必须的要求，同时也是可能的；另外，现在已 有了一些成功的实例。如国际上公认的第一个实用化的专家系统ＤＥＮＤＲＡＬ可以从质 谱数据中归纳出分子结构而归在化学上广泛使用；ＡＱ１１从大量的实例中归纳出大豆病 害诊断规则，而且发现了１５种诊断规则，其正确诊断率达到了９７．６％，比人类专家 提高了２６．８％，对农业生产起到了促进作用；另外，ＢＡＣＯＮ系统可从数据中发现 科学定律，为美国宇航局从大量数据中得到了不少新发现。 归纳推理可以描述为下列过程： 已知： ·一组数据、例子或观察，并以某种语言描述； ·假说空间，以某种语言描述的假说的集合； ·背景知识，对数据和假说的限制； 求： ·一个假说，严格或近似地符合数据并满足背景知识。 数据是归纳的材料，假说是归纳的结果，背景知识是归纳的条件或归纳的限制。由于 归纳并不是一个单输出的确定过程，对于一组数据有时可能存在两个以上的假说同时符合 数据；这时，从符合数据的众多假说中选择一个假说是必须的，选择的根据是背景知识。 另外，背景知识对于限制归纳过程中搜索的假说空间的大小和结构起着重要的作用，是提 高归纳推理效率的关键。 归纳推理的基本方法 归纳推理的基本方法分两类：通用方法和实用方法。 １．通用的归纳推理方法 通用的归纳推理方法基本上是一种枚举辨识（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ｂｙ ｅｎｕｍｅｒａｔｉｏｎ）的极限过程。 设假说空间为Ｈ，Ｈ的一个枚举为ｈ［，１］，ｈ［，２］，…，ｈ［，ｎ］，…满 足 ∞ ｈ［，ｋ］＝Ｈ ｋ＝１ 枚举辨识的步骤如下： （１）ｋ＝１ （２）检查ｈ［，ｋ］是否符合数据和背景知识，若满足，则以ｈ［，ｋ］为结果并 结束；否则ｋ：＝ｋ＋１，转向（２）。 枚举辨识具有广泛的归纳能力，可以说枚举辨识和停机可计算的相对应。例如，任何 一个不含死循环或终止的程序均可以从输入输出对中归纳推理出来。但是，枚举辨识却是 低效的，所以实际中很少采用，然而却说明了归纳的能力。 ２．实用的归纳推理方法 实用的归纳推理方法往往是针对各个特殊假说空间而提出的，具有实用性而缺乏普遍 性。 （１）空间搜索法 一个有用的归纳推理方法是对假说空间进行组织使之具有一定的结构，并利用这种结 构来实现空间搜索的。一个合适的组织结构可以允许一次同时测试多个、甚至无穷多个假 说是否符合数据，因而大大地提高了归纳效率。 例如，从已知的正反例中归纳出一个最少状态的有穷状态自动机，尽管在理论上已证 明此问题是ＮＰ－ｈａｒｄ。然而，由有穷状态自动机组成的假说空间具有十分有用的结 构。这种结构使得我们在当前假说不符合数据时，直接推知一些假说必然不符合这组数据 ，因而永远不需进行对这些假设的测试。 另外，在以谓词逻辑公式为假说空间时，定义谓词公式间的包含（ｓｕｂｓｕｍｐｔ ｉｏｎ）关系。根据这种关于一般或特殊的序关系，可以加速归纳推理。如果Ａ不符合数 据中的正例，那么比Ａ特殊的假说均不必考虑了；反之，如果Ａ符合了数据中的反例，那 么比Ａ一般的假说均不必考虑了。这种包含关系在Ｈｏｒｎ子句型逻辑中得到了进一步的 应用，用于归纳Ｐｒｏｌｏｇ程序。 （２）剪枝法 和（１）类似，剪枝的目的是在当前假说不符合数据时剪去一组假说而使之永远不在 考虑之列。如在归纳Ｐｒｏｌｏｇ程序时，如果当前程序和数据不符合，由用户指出当前 假说中的某一子句为假，此子句将做为剪枝的条件永远不出现在以后所考虑的假说之中。 （３）爬山法 爬山法是搜索邻近的假说直至当前假说为局部最优为止。该方法对优化假说很有用。 前两种方法主要用于发现假说，而爬山法主要在于优化假说。 （４）跳跃法 空间搜索和剪枝法是很保守的，它保证了永远不会跳过一个符合数据的假说，而无论 符合数据的假说有多少个。跳跃法经常是使用数据中的一些特征来形成假说，极大地减少 了考虑的假说数目，甚至减少到一个。这和启发式方法是一致的。例如在树自动机、树文 法方面已得到应用，在ＢＡＣＯＮ中也有类似的启发式信息。 （５）高效的特别方法 前面的一些实用方法的效率并不是很好，现在已有几种多项式算法，但其假说范围很 小，离实用尚差一段距离，在此不详述。 （６）Ｌｉｓｐ程序归纳方法 Ｌｉｓｐ程序的归纳一直是归纳推理研究的重要方向之一。 在归纳Ｌｉｓｐ程序中引入了几个重要的概念，如：辅助变量、辅助函数，并应用了 递归的概念。例如：从输入输出对｛〈（Ａ），Ａ〉，〈（Ａ，Ｂ），Ｂ〉，〈（Ａ，Ｂ ，Ｃ），Ｃ〉｝中可以归纳出递归Ｌｉｓｐ程序： ｆ（ｘ）＝ｉｆ ａｔｏｍ（ｃｄｒ（ｘ）） ｔｈｅｎ ｃａｒ（ｘ） ｅｌｓｅ ｆ（ｃｄｒ（ｘ）） 辅助变量和辅助函数的自动引入，已成为现行归纳推理的重要手段，即可以加快推理 速度，又可以扩大推理能力。例如：通过引入辅助函数＋和辅助变元，可以把＊转化为十 ： ｘｙ： ０ｙ＝０ （ｘ＋１）ｙ＝ｘｙ＋ｙ 设ｆ（ｘ，ｙ）＝ｘｙ，则 ｆ（０，ｙ）＝０ ｆ（ｘ＋１，ｙ）＝ｆ（ｘ，ｙ）＋ｙ 其中＋为辅助函数，ｆ（ｘ，ｙ）为辅助变元用来定义ｆ（ｘ＋１，ｙ）。上述过程 中应用了递归手段。 归纳推理的研究状况 对于归纳推理的研究主要分两类：一是理论上的研究，二是实际应用的研究。 近年来，在归纳推理的理论研究上取得了一些重要的成果：正反例精确地或近似地归 纳有穷状态自动机，或命题逻辑的析取范式，或合取范式是ＮＰ－ｈａｒｄ。这说明了归 纳推理是一个十分复杂的过程。以统计学为基础的近似归纳推理的研究，特别是“可能近 似正确”归纳方法的研究，为检测归纳方法提出了定量的评价方法。以统计学和符号方法 为基础的决策树（Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ）的归纳，以ＩＤ［，３］为代表，日益 成熟而且效率很高。以ＡＱ为代表的符号归纳系统为专家系统的知识库建造提供了工具， 并得到了扩充。另外，以应用递归和增添理论项（即辅助变元或辅助函数）为手段的归纳 式逻辑程序设计（ｉｎｄｕｃｔｉｖｅ ｌｏｇｉｃ ｐｒｏｇｒａｍｍｉｎｇ），在归 纳逻辑程序（如Ｐｒｏｌｏｇ程序）方面取得了可喜的进展，现在已有一些系统通过利用 递归机制和自动地引入新理论项，使得归纳过程更为直观、易懂并且提高了效率和归纳能 力；更为重要的是，归纳的结果是递归的，具有反馈的信息，可以刻画一些反馈系统，从 而更具有实际应用前景。 在实际应用研究方面，主要在两个方面展开：一是加深或扩充归纳推理现有方法的应 用；二是针对特殊的假说空间提出高效的方法。例如，ＤＥＮＤＲＡＬ系统，经过２０多 年的不断改进，其归纳推理能力不断提高。对特殊的函数空间已有了一些很好的高效归纳 方法，如多项式的归纳、利用溯因（ａｂｄｕｃｔｉｏｎ）的分式和代数式的归纳，以及 递归多项式的归纳，等等，使得归纳的能力不断提高，并应用了归约方法，使得系统的设 计更为简便、合理、具有层次性。在较低的层次归纳更加有效，而高层次是通过转换归约 为低层次的归纳而完成的。层次的选择可以由用户控制。从而，从解决归纳的复杂性和归 纳能力的矛盾中找到一种可行的方式。 归纳推理的应用 归纳推理具有十分广泛的应用领域，下面分几个领域予以简述。 在计算机科学领域内，程序设计一直是一项由手工完成的工作。利用归纳推理可以从 大量的输入输出对中自动地归纳出程序，从而完成程序的自动设计。现在已有了关于Ｌｉ ｓｐ和Ｐｒｏｌｏｇ的程序自动设计系统。在人工智能领域内，知识的自动获取和自动集 成可利用归纳推理来实现，从而提高效率；如ＡＱ系统在这方面已做了很多工作。在数据 库，特别是演绎数据库中，利用归纳推理可自动地生成数据的内涵或规则描述以及数据库 的完整性限制规则，为数据库向知识库过渡提供了手段，同时也为数据库的完整性和保密 性做出了贡献。现在关于从数据库中发现知识（ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒ ｙ ｆｒｏｍｄａｔａｂａｓｅ，ＫＤＤ）已成为一个专门的研究领域。 在语言学方面，利用归纳推理直接从大量的实例中归纳出语法规则，实现语言的获取 。 在模式识别方面，人为地设计语法来适合大量的样本数据是十分困难的。为此，在７ ０年代初期就开始了从样本数据中直接归纳样本分类文法的研究，并在随机文的归纳方面 取得了成功的应用。机器翻译，同样也涉及到类似的问题，现在已有一些学者在研究如何 从大量的例句中自动地归纳出翻译规则，以实现机器翻译的部分或全部自动化。 在科学研究领域，归纳推理起着十分重要的作用。ＤＥＮＤＲＡＬ可以从大量的质谱 数据中自动地归纳出分子的分解规则，并取到了成功的应用，发现了一些化学结构。在物 理学上，ＢＡＣＯＮ系统重新发现了大量的物理学定律，特别是，ＢＡＣＯＮ为美国宇航 局从大量数据中发现了新规律，并应用于航天飞机的控制之中。在数学领域中，ＡＭ系统 重新发现了数论中著名的质因式唯一分解定理，并被冠以“数学家的ＡＭ”。ＡＭ具有发 现新概念和新猜想的能力。 在自动控制和系统辨识方面，利用归纳推理自动地构造或识别系统的模型并对之加以 控制的研究已取得了众多的成果。如在机器人控制中，从已有的一些经验中自动归纳一般 的控制规则的研究，特别是发现一些启发式控制规则以简化控制过程的研究。 在管理决策和预测方面，利用归纳推理对经验数据进行分析，自动地构造管理模型， 从而实现决策和预测的自动化。例如，美国一家信用卡公司，通过用户过去使用信用卡的 情况分析，来自动地决定是否允许用户使用信用卡，从而有效地减少了恶性透支和欺骗行 为，每年减少了几千万美元的损失。该系统获得了巨大的成功并正在不断扩充。 总之，归纳推理是一种重要的推理方式，可谓无处不在，无处不用，具有广泛的应用 前景。 结束语 归纳推理在近年来已取得了令人瞩目的进展，其应用范围不断扩大，并已在众多领域 取得了成功的应用。但是仍存在一些基本问题有待于解决，如何解决归纳推理能力和效率 的矛盾一直是一个关键问题。归纳推理的理论还未成熟，然而事实上关于归纳推理的实际 应用在各个方面均取得了令人震惊的成就。我们相信归纳推理的应用，比其理论本身的发 展会更快。就目前发展状况而言，归纳推理还是一门和具体领域相关的技术性领域，但它 却具有十分诱人的魅力。 （计算机世界报 1994年 第22期） |
周报全文频道联系方式：010-68130909 |
||||||
| 【关于我们】 【广告服务】 【周报发行】 【投稿指南】 【投稿声明】 【联系方式】 【法律声明】 【媒体手册】 【编读往来】 |
||||||
| Copyright© ccw.com.cn,All rights reserved | ||||||
| 中国计算机世界出版服务公司版权所有 | ||||||