基于归纳的学习

6.2.3　基于归纳的学习

所谓归纳学习，就是系统根据有关的数据或实例，应用归纳推理推导出一般性规则或结论。归纳学习可以迅速地产生知识库，是一种有效的自动化学习方法。

1.归纳学习的原理

归纳学习是通过执行归纳推理来实现的。什么是归纳推理呢?归纳推理就是从已知事实和背景知识推导出结论的处理过程，该结论描述已知事实。归纳推理是由特殊到一般，若推导出的规则是正确的，那么不仅可将它用于其他特例，还可用于一般情况。

为了从实例描述推导出规则，或将一条规则转换为较一般性的规则，需要应用各种归纳操作。适合于学习系统的归纳推理规则可分为以下两大类型。

(1)选择归纳。选择归纳包括:

①减少条件:就是从AND操作符连接的表达式中删掉一个或几个条件，那么所得规则比原规则较一般化。例如，

原规则:如果一个学生又聪明又很勤奋，那么他的学习一定很好。新规则:如果一个学生很勤奋，那么他的学习一定很好。

②将常量转换为变量:将事实描述或规则条件中的常量代换为一个变量。例如，likes(Liming，football)转为likes(X，football)，则变量X可代表任何一个人，即任何一个人都喜欢足球。

③增加选择项:就是将可能的情形用OR操作符号连入规则的条件中。例如Flag(X)=Red，转为Flag(X)=Red OR Blue。

④放宽条件:例如Height=25，转为Height＞24。

⑤转换AND为OR:就是将条件中的AND操作符转为OR操作符。例如A AND B，转为A OR B。

⑥应用“相对扩展(Extend Against)”操作，扩展规则的条件。

(2)构造归纳。构造归纳包括:

①计算参数满足一个条件，例如曲线拟合法，可从已存实例推导出新规则。例如，对于(X，Y，Z)三元组有以下三个实例:

实例1:(0，2，7)

实例2:(6，－1，10)

实例3:(－1，－5，－16)

其中X，Y是输入，Z是输出。采用最小平方回归分析，可推出规则:Z=2X+3Y+1。

②探索概念之间的从属关系，用较广义的概念代换较狭义的概念。例如用“图书馆”代换“大学图书馆”。

③用蕴含性质代换一个性质。例如，A蕴含B，则可用A代换B。

2.归纳学习模式

归纳学习模式可描述如下:

已知:观察描述或事实(F)、当前的归纳命题、背景知识(Background Knowledge)、假设的选择标准。

寻找:一个归纳命题/假设(H)，它蕴含观察描述(或事实)，并满足假设的选择标准。

例如:

前提:张华、李红和王刚都是中国人。

背景知识:他们都是哲学家。

哲学家都是人。

中国人都是人。

选择标准:产生的规则能确定哲学家的国籍。

推出结论:所有哲学家都是中国人。

所有人都是中国人。

选择结论:所有哲学家都是中国人。

归纳学习模式还要求具备实例集合、规则集合和归纳学习算法这3个基本元素。

(1)实例集合

实例集合形成归纳推理的基础。训练实例的质量对学习系统的执行起着非常重要的作用。准确的、完整的实验实例，可产生高质量的规则;不完整的或没有适当表示的实例集合可能产生质量较差的规则。每个训练实例描述一个对象。每个实例的性质由一组属性来描述。这些性质形成了影响归纳的因素。它们可以是描述型的，如大、中、小;也可以是整型值、实数值及逻辑描述，如真、假等。

所有实例可以分为不同的类，用于产生决策或分类规则。

(2)规则集合

归纳系统包含不同的规则集合，如背景知识规则集和假设规则集。整个规则空间通常用项和所执行的各种运算来定义。学习系统设计者在选择规则空间时，既要求它便于搜索，又要求它能包括所有有关的规则。

搜索规则空间的方法可概括为三种:

①数据驱动方法。它是由下而上，使用训练实例控制搜索过程。

②模型驱动方法。它是自顶向下，使用一种先验模型指导搜索，仅产生符合要求的假设，例如最一般的假设或最特殊的假设。

③星方法。星方法是一种混合方法。首先使用数据驱动法，每次考察一个新的训练实例，通过与H的模式匹配，决定对当前的假设集合H应该进一步扩展还是应该精练。在加工假设的每一步，仅维护固定个数的具有最大可能的候选者，候选者由预先描述的评估模式确定。

(3)归纳学习算法

学习系统要具备有效的归纳推理算法用来从实例集合归纳出规则。从实例集合的查找、归纳能力及处理输入中的错误与干扰等方面来看，有许多不同的归纳算法。

归纳结果的质量依赖于所有以上元素。换句话说，仅当好的算法用于适当表示的、丰富的实例集合，才能产生好的归纳结果。如果实例包含不确定信息，就不能应用算法表达概念。为了执行算法，还必须有合适的描述语言表达操作中所有必要概念。

3.归纳学习方法

(1)根据是否有教师指导，归纳学习可分为通过实例学习和通过观察与发现学习两类。

通过实例学习，由教师提供正面实例和反面实例，由计算机独立进行模型间的匹配，自动寻找差异，决定优先级别和做出相应处理，完成模型的修改。通过实例学习，可从部分信息推导整体规则，从实例信息推导类的特性。它还可从离散的操作事件推导一般的问题求解步骤。

通过观察与发现学习，是根据环境提供的事例以及一些规则，机器独立地发现正例和反例，并进行推理，发现新概念，做出新猜想。例如概念聚类学习和BACON的发现学习。

(2)根据信息提供的方式，归纳学习可分为增量式学习和非增量式学习。

非增量式学习的模式是:

已知:正、反实例集合和背景知识。

寻找:一般性的概念描述(规则)，它覆盖所有的正面例子，不包括反面实例。

所有实例一次提供给程序。

增量式学习的模式是:

已知:正面实例集合与反面实例集合、背景知识和输入假设集合。

寻找:一般性的概念描述，它覆盖所有的正面实例和输入假设，不包括反面实例。

在增量式学习过程中，实例分为若干组，逐次将每组实例加入输入数据，同时，将前面程序运行的结果作为输入假设，逐渐修改和精练以前产生的规则和正在产生的规则。

著名的归纳学习算法有:①TDIDT系列(Quinlan)，采用决策树的自顶向下的归纳方法;②AQ系列(Michalski)，采用决策树或规则的形式从训练实例中归纳知识。