1、54实例学习方法基于实例的学习是典型的归纳学习方法。该方法的学习过程基于环境提供的大量特殊的实例，系统通过对事先标注了正例、反例的示教例子的分析，进行归纳推理，得到一般的规则。机器将系统的低水平的信息归纳成为高水平的信息，一般情况下，用这些信息（规则）指导执行环节。整个过程有一整套比较完善的算法。实例方法早在50年代就引起了人工智能学者的注意，是在机器学习领域中研究最充分成果最丰富的一个分支。实例学习在某些系统中的应用已经成为机器学习走向实用的先导。541实例学习的基本理论如上一节所述，实例学习是一种归纳学习方法，从大量的学习样本中归纳总结出相应的规则、概念。首先我们使用Winston（197
2、5年开发）提出的结构化概念学习程序的例子作为模型来说明实例学习的过程。Winston的程序是对简单的积木世界领域中进行操作，其目的是要建立积木世界中物体概念定义的结构化表示，例如学习房子、帐篷和拱的概念，构造出这些概念定义的结构化描述。系统的输入是积木世界某物体（或景象）的线条图，使用语义网络来表示该物体结构化的描述。例如，系统要学习拱桥的概示，这个结构化的描述就是拱桥概念的定义。接着再向程序输入第二个拱桥示例，其描述如图2所示。这时学习程序可归纳出图3所示的描述。念，就给学习程序输入第一个拱桥示例，得到的描述如下图1所假定下一步向程序输入一个拱桥概念的近似样品，并告知程序，这不是拱桥（即拱桥
3、的反例），则比较程序会发现当前的定义描述（图）与近似样品的描述只是在和节点之间，不接触”的链接弧有区别。由于近似样品不是拱桥，不是推广当前定义描述去概括它，而是要限制该定义描述适用的范围，因而就要把“不接触”链接修改为“必须不接触”，这是拱桥概念的描述如图4所示。这就是机器最后学习得到的拱桥概念。图5-拱4桥概念的归纳学习过程下图是实例学习的两个空间模型。实例空间是所有示教例子的集合，而规则空间是所有规则的集合。实例学习应在规则空间中搜索、匹配所求的规则，并在实例空间中选择一些示教例子，以便解决规则空间中某些规则的歧义性，系统就是这样在实例空间和规则空间中交替进行搜索，直到找到所要求的规则。图
4、5-实5例学习的两个空间模型首先由示教者给实例空间提供一些初始示教例子，由于示教例子的形式往往不同于规则的形式，程序必须对示教例子进行解释，然后再利用被解释的示教例子去搜索规则空间。一般情况下，不能一次就从规则空间中搜索到要求的规则，因此还要寻找一些新的示教例子，这个过程就是选择示教例子。解释例子和选择例子这两个过程如此循环，直到搜索到要求的规则。实例空间和规则空间的例子：下面考虑教计算机程序扑克牌中“同花”概念的问题，同花是指五张牌同一花色所组成的一手牌。在这个学习问题中，实例空间是五张牌的全部各手牌的集合。我们把这个空间中单个的点表示为一组五个有序对，比如（2梅花），（3梅花），（5梅花）
5、，（J梅花），（,梅花）每一有序对指明一张牌的点数和花色。整个实例空间是所有这样的五张牌集合的空间。这个问题的规则空间是描述一手牌的全部谓词表达式的集合。这些表达式使用下列符号描述：谓词：（花色）、（点数）表示牌的变量：，和某些必要的自由变量：x,yz,某些必要的常量：梅花、方块、红心、黑桃、4、5、6、7、8、9、10、J、Q、K1.1.15223.3.22323235,222.规则的表示形式应适应归纳推理542实例学习方法的分类实例学习的方法有几种，可以根据搜索策略的不同进行分类，也可以根据所处理的任务的复杂度的不同进行分类。1按搜索方法分类1按搜索方法分类：也就是搜索规则空间的方法，可分
6、为数据驱动方法和模型驱动方法。主要有：变形空间法、改进假设法、产生与测试法、方案示例法。学习的最终目的是为了搜索，有了假设空间H的基础，在该空间中进行搜索。改进假设空间的假设规则集，以便得到所要求的规则。下面介绍几种搜索规则空间的方法。这些方法都具有一个假设规则集合H，不同的仅仅是对H的改进方法。口变型空间法：变型空间法(version-spacmeethod)是一种数据驱动方法（data-drivemethod）。这种方法对规则和实例都采用同一种表示形式。初始的假设规则集H包括满足第一个示教例子和全部规则。在得到下一个示教例子时，对集合H进行一般化或特殊化处理，最后使集合H收敛为仅含要求的规
7、则。口改进假设法：改进假设皿hypothesis-refinememnethod)也是一种数据驱动方法。这种方法表示规则和实例的形式不统一。程序根据例子选择一种操作，用该操作去改进假设规则集H中的规则。产生与测试法：产生与测试法(generateandtes)t是一种模型驱动方法(model-drivenmethod)。这种方法针对示教例子反复产生和测试假设的规则。在产生假设规则时，使用基于模型的知识，以便只产生可能合理的假设。方案示例法：方案示例皿schemainstantiat)也是一种模型驱动方法。该方法使用规则方案的集合来约束可能合理的规则的形式，其中最符合示教例子的规则方案被认为是最
8、合理的规则。数据驱动方法的优点是可以逐步接受示教例子，以渐进方H，因此一个错误实例就会造成集合式学习，特别是变型空间法，它很容易修改集合回溯就可以考虑新的实例。模型驱动方法难以逐步学习，假设。在使用新假设时，它必须回溯或重新搜索规则空间。因为原来对假设的测试已不适用于新实例加入后的情况。模型驱动方法的优点是抗干扰性良好。合，程序就可以对假设进行统计测量。它不因一、二个错误实例而放弃正确的假设。当前新的实例去修改集合的混乱。解决的方法是每次用新实例去修改集合小的修改，这样可以减少错误实例带来的影响，得学习的进程变慢了。H，不要求程序它是通过检查全部实例来测试由于使用整个实例集在用错误实例测试假设
9、时，而数据驱动方法用HH时，只作较当然这也同时使2按任务复杂程度55系统的任务不同，相应的学习方法的目的、方法也不同。可以分为：学习单个概念、学习多个概念、学习执行多步任务。学习单个概念是最基本的理论方法，本节只介绍学习单个概念的方法步骤。学习多个概念是在学习单个概念的基础上进行的，但不仅仅是简单的运算次数的增加。学习执行多步任务时，执行环节对任务要进行规划，这也是学习的目标之一。对于单概念学习，学习的目的是从概念空间（即规则空间）中寻找某个与实例空间一致的概念；对于多概念学习，任务是在概念空间中找出若干概念描述，对于每一概念描述，实例空间中均有相应的空间与之相应。下图给出了两种学习方法实例空
10、间划分上的差异。图5-单6个概念与多个概念学习空间划分示意图单概念学习系统实例空间划分多概念学习系统实例空间划分单个概念的学习是提供给系统一个概念的若干正例和若干反例，系统由此构成规则空间，并可得到在这个规则空间中的一个概念。这个概念应包含所有的正例，但不包含任何反例。该学习方法有两个假设，其一是示教例子必须是系统所学的概念的例子，要么是正例，要么是反例（如果违反了这一假设，那么就变55543变型空间法15.4.3.155少有一张梅花牌且至少有一张红心牌，它比前两个概念更特殊。图中的箭头用来指向从特殊概念到一般概念。图中最下面一行的各点是正例直接对应的概念，每一个点的概念只符合一个正例。现在一
11、手牌，例子是每张牌的花色和点数，比如：SUIT(CLUBS.JARANK7)这是一个正例，一个最特殊的概念。而概念是规则空间中的点，它比没有描述要特殊，比示教正例要一般。示教例子应该是有具体花色、具体点数的某一张或一组牌。规则空间结构图如下：图5-规8则空间的结构如图所示，规则空间中最一般的元素构成子集；规则空间中最特殊的元素构成的子集为。在假设规则集合是以为上确界和以为下确界的一段。因此，可以用和来表示集合。学习过程就是向下、向上变化的过程，也就是说学习时规则空间的形状在发生变化，所以称为变形空间法。最后，成为一个点，学习结束。上图中规则空间初始时，最上边是一般规则(概念)，没有描述、没有条