5．4实例学习方法
基于实例的学习是典型的归纳学习方法。该方法的学习过程基于环境提供的大量特殊的实例，系统通过对事先标注了正例、反例的示教例子的分析，进行归纳推理，得到一般的规则。机器将系统的低水平的信息归纳成为高水平的信息，一般情况下，用这些信息（规则）指导执行环节。整个过程有一整套比较完善的算法。
实例方法早在50年代就引起了人工智能学者的注意，是在机器学习领域中研究最充分成果最丰富的一个分支。实例学习在某些系统中的应用已经成为机器学习走向实用的先导。5．4．1实例学习的基本理论
如上一节所述，实例学习是一种归纳学习方法，从大量的学习样本中归纳总结出相应的规则、概念。
首先我们使用Winston（1975年开发）提出的结构化概念学习程序的例子作为模型来说明实例学习的过程。
Winston的程序是对简单的积木世界领域中进行操作，其目的是要建立积木世界中物体概念定义的结构化表示，例如学习房子、帐篷和拱的概念，构造出这些概念定义的结构化描述。
系统的输入是积木世界某物体（或景象）的线条图，使用语义网络来表示该物体结构化的描述。例如，系统要学习拱桥的概念，就给学习程序输入第一个拱桥示例，得到的描述如下图1所
示，这个结构化的描述就是拱桥概念的定义。接着再向程序输入第二个拱桥示例，其描述如图2所示。这时学习程序可归纳出图3所示的描述。
假定下一步向程序输入一个拱桥概念的近似样品，并告知程序，这不是拱桥（即拱桥的反例），则比较程序会发现当前的定义描述（图3）与近似样品的描述只是在B和D节点之间，“不接触”的链接弧有区别。由于近似样品不是拱桥，不是推广当前定义描述去概括它，而是要限制该定义描述适用的范围，因而就要把“不接触”链接修改为“必须不接触”，这是拱桥概念的描述如图4所示。这就是机器最后学习得到的拱桥概念。
图5-4拱桥概念的归纳学习过程
t5_4_1_1a_swf.htm
t5_4_1_1b_swf.htm
t5_4_1_1c_swf.htm
t5_4_1_1d_swf.htm
下图是实例学习的两个空间模型。实例空间是所有示教例子的集合，而规则空间是所有规则的集合。实例学习应在规则空间中搜索、匹配所求的规则，并在实例空间中选择一些示教例子，以便解决规则空间中某些规则的歧义性，系统就是这样在实例空间和规则空间中交替进行搜索，直到找到所要求的规则。
图5-5实例学习的两个空间模型
t5-5_swf.htm
首先由示教者给实例空间提供一些初始示教例子，由于示教例子的形式往往不同于规则的形式，程序必须对示教例子进行解释，然后再利用被解释的示教例子去搜索规则空间。一般情况下，不能一次就从规则空间中搜索到要求的规则，因此还要寻找一些新的示教例子，这个过程就是选择示教例子。解释例子和选择例子这两个过程如此循环，直到搜索到要求的规则。
实例空间和规则空间的例子：
下面考虑教计算机程序扑克牌中“同花”概念的问题，同花是指五张牌同一花色所组成的一手牌。
在这个学习问题中，实例空间是五张牌的全部各手牌的集合。我们把这个空间中单个的点表示为一组五个有序对，比如：{（2，梅花），（3，梅花），（5，梅花），（J，梅花），（K，梅花）}每一有序对指明一张牌的点数和花色。整个实例空间是所有这样的五张牌集合的空间。
这个问题的规则空间是描述一手牌的全部谓词表达式的集合。
这些表达式使用下列符号描述：
谓词：SUIT（花色）、RANK（点数）
表示牌的变量：c1，c2，c3，c4和c5
某些必要的自由变量：x,y,z
某些必要的常量：梅花、方块、红心、黑桃、A、2、3、4、5、6、7、8、9、10、J、Q、K
这样，同花的概念可以表示为下列规则：
(c1,c2,c3,c4,c5)∧SUIT(c1,x)∧SUIT(c2,x)∧SUIT(C3,x)
∧SUIT(c4,x)∧SUIT(c5,x)
实例空间的例子的质量是非常重要的。高质量的示教例子是无二义性的，它可以为规则空间的搜索提供可靠的指导。低质量的示教例子会引起互相矛盾的解释，其结果仅为规则空间的搜索提供试探性的指导，有是甚至会诱导出错误的结论，得到错误的规则。
例如，错误的例子在示教程序“同花”概念时，首先，实例可能有错误，如果实例的描述不正确，会产生测量错误，比如梅花2被错认为黑桃2；其次分类可能有错误，比如把一手非同花的牌误判为同花。如此之类的错误信息都可能会产生二义性，使得程序难以发现正确的概念。
另外，示教例子排列次序也会影响学习的质量。如果示教者对示教的例子事先按特征的重要性进行合理的排序，学习任务就比较容易一些。
例如，示教正确例子的同时相间隔的示教一些错误的例子，可以及时检验纠正学习过程中规则的偏移，加快学习速度。
实例学习对规则空间有三个方面的要求：
1.规则的表示与实例的表示一致
如果示教例子和规则的表示形式相差很大，那么解释例子和选择例子的过程就很复杂。因此，最好采用相同的形式来表示规
则和示教例子。
比如程序要学习“对牌”的概念，对牌是两张点数相同的牌，对牌的规则是
RANK(c1,x)∧RANK(c2,x)PAIR
为了学习这条规则，提供下面的例子
(2,clubs),(3,diamonds),(2,hearts),(6,spades),(K,hearts)PAIR
这样表示的示教例子与规则表示形式差异很大，使得归纳比较困难。如果把例子改用谓词逻辑表示，则上面的例子可表示为：RANK(c1,2)∧SUIT(c1,clubs)∧RANK(c2,3)∧SUIT(c2,diamonds)∧RANK(c3,2)∧SUIT(c3,hearts)∧RANK(c4,6)∧SUIT(c4,spades)∧RANK(c5,K)∧SUIT(c5,hearts)PAIR
这样改写之后，再归纳出规则就比较简单了。我们可以首先去掉五个SUIT条件，然后再去掉c2、c4和c5的RANK条件，最后把常量2变换成变量x，就可以归纳成规则了。
2.规则的表示形式应适应归纳推理
规则空间的表示方法应该支持归纳推理，常用的归纳方法有：把常量变成变量，省略条件，增加选择项，曲线拟合等。
3.规则空间中应能够包含所有可能产生的规则
在有些实例学习的问题中，初始化时，所要求的规则并不一定全都包含在规则空间中，即规则空间的描述语言不一定能够表示全部要求的规则。解决的办法是引入新的术语，扩充规则空间的描述语言，使之能够适应所有的规则。
