归纳和学习的结合

1、1 机器学习机器学习 第12章 归纳和分析学习的结合 2 概述概述 纯粹的归纳学习方法通过在训练样例中寻找经 验化的规律来形成一般假设 纯粹的分析方法使用先验知识演绎推导一般假 设 本章考虑将归纳和分析的机制结合起来的方法， 并获得两者的优点：有先验知识时获得更高的 泛化精度和依赖训练数据克服先验知识的不足 所得到的结合的方法比纯粹的归纳方法和分析 方法的性能都要高 本章考虑的归纳分析学习方法同时基于符号 表示和人工神经网络表示 3 动机 在前几章已经见到两种类型的机器学习，归纳方法如决策树归纳 和神经网络反向传播 归纳学习寻找拟合训练数据的一般假设，分析学习寻找拟合先验 知识的一般假设，同时

2、使它覆盖训练数据 归纳方法和分析方法对假设的论证方法有根本区别，因此优缺点 互为补充，将它们结合起来有可能得到更强有力的学习方法 纯粹的分析学习方法的优缺点 优点：可用先验知识从较少的数据中更精确地泛化以引导学习 缺点：当先验知识不足或不正确时，可能产生误导 纯粹的归纳学习方法的优缺点 优点：不需要显示的先验知识，主要基于训练数据学习规律 缺点：训练数据不足时，会失败，会被其中隐式的归纳偏置所 误导 本章考虑的问题是怎样将二者结合成一个单独的算法来获得它们 各自的优点。表12-1概述了以上二者的互补的优点和缺陷。 表表12-1 纯粹的分析学习和纯粹的归纳学习的比较纯粹的分析学习和纯粹的归纳学习

3、的比较 4 归纳和分析学习方法之间的不同可从他们对学习到的假设进 行的论证性质中看出。由纯粹的分析学习输出的假设执行的 是逻辑论证：输出的假设从领域理论和训练数据中演绎派生。 纯粹的归纳学习方法输出的假设执行的是统计论证：输出的 假设从统计论据中派生。他说明训练样本足够大，从而能代 表样例的基本分布。归纳的统计论证在第七章中讨论的PAC 学习中已清晰阐明。 由于分析方法提出逻辑论证的假设，而归纳方法提供统计论 证的假设，很容易看出将两者结合起来的好处是什么。逻辑 论证的强度只相当于他们所给予的假定或先验知识。如果先 验知识不正确或不可知，逻辑论证是不可信和无说服力的。 统计论证的强度依赖于他们

4、基于 的数据和统计假定。当基准 分布不可信或者数据稀少时，统计论证也是不可信且无力的。 简而言之，两种方法针对不同类型的问题时才有效。通过两 者的结合，有望开发出更通用的学习方法，可以覆盖较广的 学习任务。 6 动机（动机（2） 图12-1 概述了学习问题的分布范围，它随着可获得的先验知识和训练数 据不同而变化 在一个极端，有大量的训练数据，但没有先验知识 在另一个极端，有很强的先验知识，但训练数据很少 多数实际学习问题位于这两个极端之间，通常可以从近似的先验 知识开始 举个例子： 通过分析医疗记录的数据库来学习治疗手段X比治疗手段 Y更有效的病症，通常可以从近似的先验知识开始（如， 疾病中内

5、在的因果机制的定性模型），比如认定患者的体 温比他的姓名更相关。类似地，在分析一个股票的市场数 据库来学习目标概念“股票值在后十个月会翻番地公司” 中，如果已经有了经济学的大概知识，可以提出公司地总 利润比公司标志的颜色更相关。这两种问题中，我们的先 验知识是不完整的，但显然，它有助于区分相关不相关的 特征。 本章考虑的问题是： 我们可以设计出什么样的算法，使用近似的先验知 识结合可用数据来形成一般的假设 8 动机（3） 即使使用最纯粹的归纳学习算法，仍有机会基于特定学 习任务的先验知识来选择设计方案 例如：当应用反向传播来解决语音识别这样的问题时， 设计者必须选择输入和输出数据的编码方式、在

6、梯度下 降中被最小化的误差函数、隐藏单元的数量、网络的塔 普结构、学习速率和冲量等。 在做这些选择时，通常设计者将领域特定的知识嵌入到 学习算法中，然而结果仍然是纯粹的归纳算法反向传播 的一个实现，由设计者针对 语音识别任务进行特殊化。 但我们感兴趣的是一个系统能将先验知识和训练数据作 为显示的输入给学习器。这样他们仍然是通用的算法， 但利用了领域的特定知识 概括而言，我们感兴趣的是领域无关算法，这种算法使 用显示输入的领域相关的知识，这种算法具备以下的属 性： 如果没有领域理论，它至少能像纯粹的归纳方法一 样有效学习 如果没有完美的领域理论，它至少能像纯粹的分析 方法一样有效学习 如果领域理

7、论和训练数据都不完美，它应能结合两 者的长处，比单纯的归纳或分析方法的性能要好 它应能处理训练数据中未知程度的差错 它应能处理领域理论中未知程度的差错 这里列出的期望目标很难达到，目前没有算法能以一般 化的方式满足所有这些约束 例如： 处理训练的中的差错，即使在基于统计的归纳方法中，如 果没有某些先验知识和对错分布的假定，这仍然是值得研 究的问题结合归纳和分析学习方法是当前活跃的研究领域。 虽然上面列出的是我们希望算法能够达到的美好性质，目 前没有算法能以完全一般化的方式满足多有的约束。 下一节对结合归纳分析学习的问题做出进一步的讨论后面 季节描述了三种不同的途径，结合近似的先验知识和可用 数

8、据来指导学习期搜索合适的假设。每种途径都已经在多 个问题领域中显示出有纯归纳方法的性能。为方便比较， 我们使用同一个例子来说明这三种途径。 学习的归纳学习的归纳-分析途径分析途径 最好地拟合训练样例和领域理论的确切定义：这句话的具 体含义是什么呢？或者说，是否会选择一个拟合数据程度 较好而拟合理论较差的假设，或反之？为了更精确起见， 需要定义对应数据和对应于领域理论的假设错误率量度， 然后用这些错误率来表示这个问题。回忆一下第五章中 errorD（h）定义为D中被h无分类的样例所占比例。可定 义h关于领域理论B的错误率errorB（h）为：h和B在分类 一个随机抽取实例时的不一致的概率。接下来

9、就可以尝试 使用这些错误率的形式刻画所希望的输出假设。 11 )()(minargherrorkherrork BBDD Hh 例如:我们可以要求假设使上述错误率的某种综合度量最 小化，如： 虽然看起来这很合理，但还不知道怎么确定KD的和KB的 值来指定拟合数据和拟合理论两者的相对重要程度。如果 有非常差的理论，却有大量可靠数据，最好是errorD（h） 的权值增大会得到更好的结果。当然如果学习器预先不知 道领域理论和训练数据的质量，它就不清楚怎样为这两部 分错误率加权。 怎样确定先验知识和数据权值的一种解决办法是使用贝叶 斯的观点。 13 学习的归纳-分析途径（2） 确定先验知识和数据权值的

10、一种解决方法是使用贝叶斯 观点 贝叶斯定律描述了怎样计算给定训练数据D时假设h 的后验概率 贝叶斯定律基于观察到的数据D以及先验知识计算后 验概率，以P(h), P(D)和P(D|h)的形式表示 我们可以把P(h), P(D)和P(D|h)看作是某种形式的背 景知识 贝叶斯理论可看作一种为领域理论加权的方法，它 与观察到的数据D一起，赋予h的后验概率为P(h|D) 按照贝叶斯的观点，所选择的假设应该为后验概率 最大的那一个，并且贝叶斯公式提供了为先验知识 和观察到数据的贡献加权的方法 但是，贝叶斯公式隐含假定了关于P(h), P(D), P(D|h)概率 分布的完美知识，当这些量都是近似已知时

11、，单独的贝叶 斯公式没有规定加何将其与观察数据结合起来（在此情况 下，一种方法是假定有P（h）、P（D）和P（D|h）之上 的先验概率分布，然后加un厚颜概率P(h|D)的期望值。然 而这要求有P（h）、P（D）和P（D|h）之上的先验分布 方面的附加知识，因此并没有真正的解决此问题。 当考虑特定算法时，我们会再次考虑“最佳”拟合假设和数 据是什么含义。现在，我们只是简单地说，学习问题是为 了使假设在数据和领域理论上的错误率的某种综合度量最 小化。 15 假设空间搜索假设空间搜索 如何将领域理论和训练数据最好的结合起来，从而限制可 接受假设的搜索呢？这在机器学习中仍是需要研究的问 题。本章考察

12、了几种已提出的方法，其中许多要对已讨 论过的归纳方法（如，反向传播，FOIL）进行扩展。 为了了解可能途径的范围，一种办法是回到前面对学习的 看法，即将其看作是一种搜索多个可选假设空间的任务。 为了将大多数学习任务可以刻画为假设空间上的搜索任 务,而决定这个搜索任务的4个参数是： 假设空间H 搜索的初始假设h0 定义单个搜索步的搜索算子集合O 指定搜索目标的判据G 本章探索了3种方法，它们用先验知识来改变纯归纳方 法执行的搜索 使用先验知识推导出搜索起步的初始假设：Kbann 使用先验知识来改变假设空间搜索的目标：Ebnn 使用先验知识改变可用的搜索步：Focl 使用先验知识推导出搜索起步的初

13、始假设： 使用先验知识来改变假设空间搜索的目标： 使用先验知识改变可用的搜索步： 19 使用先验知识得到的初始假设 KBANN技术：一种使用先验知识的方法是将假设初始 化为完美拟合领域理论，然后按照需要归纳地精化初始 假设以拟合训练数据。这种方法被用于KBANN算法中、 在KBANN中，首先建立一个初始的网络。对每个可能 的实例，网络赋予他的分类等于领域理论赋予的分类。 然后应用反向传播算法来调整初始网络，使其拟合训练 样例 这种技术的动机是：如果领域理论是正确的，初始假设 将正确分类所有训练样例，而无需再修正；如果初始假 设不能完美地分类训练样例，那么它需要被归纳精华， 以改进它在训练样例上

14、的拟合度 21 KBANN算法算法 KBANN运用领域理论来初始化假设。其中KBANN假定领 域理论用一组命题形式的非递归的Horn子句来表示， 输入和输出如下： 已知： 一组训练样例 由非递归命题型Horn子句组成的领域理论 求解： 一个拟合训练样例的被领域理论偏置的人工神经网络 KBANN算法包含两个阶段 创建一个完美拟合领域理论的人工神经网络 使用反向传播算法来精化初始网络以拟合训练样例 22 表12-2 KBANN算法 KBANN(Domain_Theory, Training_Examples) Domain_Theory：非递归命题型Horn子句集 Training_Example

15、s：目标函数的对的集合 分析步：创建一个等价于领域理论的初始网络 对每个实例属性创建一个网络输入 对Domain_Theory的每个Horn子句，创建如下的网络单元 连接此单元的输入到此子句的先行词测试的属性 对子句的每个非负先行词，赋予权值W给对应的sigmoid单元输入 对子句的每个负先行词，赋予权值-W给对应的sigmoid单元输入 设置此单元的阈值w0为-(n-0.5)W，其中n为子句的非负先行词的数目 在网络单元之间增加附加的连接，连接深度为i的每个网络单元到 深度为i+1的所有网络单元的输入层上，赋予这些附加的连接为接 近0的随机权值 归纳步：精化此初始网络 应用反向传播算法来调整

16、初始网络权值以拟合Training_Examples 表12-3 Cup学习任务 领域理论 训练样例 24 举例 在KBANN算法的第一步，构建一个与领域理论一致 的初始网络，例如，从Cup的领域理论中构建的网络 描绘于见图12-2中。 一般说来，网络的构建是通过对领域理论中每个 Horn子句建立一个sigmoid单元。KBANN遵从惯例， sigmoid输出值大鱼0.5时被解释为真，小于0.5则解 释为假。因此每个单元的构建方法为：当对应的 Horn子句存在时，单元的输出就大于0.5. 对该Horn子句的每个先行词，建立其对应的Sigmoid 单元作为输入，然后设置Sigmoid单元的权值，

17、使其 计算得出其输入的逻辑与。 确切的讲，对于每个对应于非负先行词的输入，权 值被设置为某正常量W，对每个对应于负先行词的 输入，权值为-W 单元的阈值权w0设为-(n-0.5)W，其中n为非负先行 词的数目 当单元输入值为1或者0的时候，这保证了当且仅当 所有的子句先行词满足时，输入的加权和加上W0为 正。注意，对于sigmoid单元，第二层及以后的层中 单元输入不一定为1或者0，上面的命题无法应用于 此。然而如果为W选择足够大的值，此KBANN算法 可以对任意深度的网络进行领域理论编码。T & S在 多次试验中使用W=4.0. 每个sigmoid单元输入被连接到适当的网络输入或另 一个si

18、gmoid单元的输出，一反应领域理论中对应属性 的依赖关系图。最后一步，又附加许多输入到每个阈值 单元，它们的权值设置为近似0，从而允许网络能够学 习到超出领域理论的依赖关系。图12-2中的粗实线表明 权值W的单元输入，而细实线表明初始权值约为0的连 接。很容易验证对于足够大的W值，此网络输出值对于 领域理论的预测。 在KBANN算法的第二步，使用训练样例和反向传播 算法来精化网络权值。当然，如果领域理论与训练数据 不一致，所以此步骤会改变初始网络的权值。细线表明 可忽略的权值。虽然初始网络无分类了表12-3中几个训 练样例，但图12-3中精化的网络能完美的分类所有的训 练样例。 29 KBA

19、NN算法说明算法说明 概括的来讲，可KBANN用分析的方式创建了等价于给定领域理 论的网络，然后归纳的精化此初始假设以更好的拟合训练数据。 在此过程中，它为了改变领域理论和训练数据不一致的情况而 修改网络权值。 与純归纳的反向传播相比，KBANN的好处在于，它在给定近似 正确领域理论时，能够比反向传播有更高的泛化精度，特别是 在训练数据稀少的情况。在几种实际系统中KBANN和其他几个 初始化假设的途径已显示出优于純归纳的系统。例如：Towell 描述了将KBANN应用于分子遗传问题，任务是学习识别称为激 发区域的DNA片段，它影响基因的活性。在此实验中，KBANN 的领域理论从一个分析遗传学家

20、那里获取，而激发区域的训练 样例包含53个正例和53个反例。性能评估使用了留一法，系统 运行106次，每次循环中KBANN用105个样例训练，并在剩余的 样例上测试，这106次试验结果被积聚起来提供对真实错误的估 计。 KBANN错误率为4/106，而标准的反向传播错误率为 8/106.KBANN的一个变种由Fu实现的，他报告在同样的 数据上的错误率为2/106，因此先验知识在这些实验中很 大程度上减少了错误率。 Fu和Towell都报告：从最终训练过的网络中抽取的Horn子 句，可提供一个更好拟合训练数据的领域理论。虽然有时 可能从学习到的网络权值设置没有直接对应的Horn子句。 Crave

21、n & Shavlik和Craven描述了另外的方法从学习过的 网络中抽取符号规则。 未了解KBANN的定义，有必要考虑其中的假设搜索与純 归纳的反向算法中有什么区别。这两种算法中执行的假设 空间搜索在图12-4示意。如其中显示的，关键区别在于执 行权值调节所给予的初始假设。 在有多个假设能拟合数据的情况下，KBANN更有可能收 敛到这样的假设，它从训练数据中的泛化与领域理论的预 测更为相似。另一方面，反响传播收敛道德特定假设更可 能是小权值的假设，它大致对应于在训练样例间平滑差值 的泛化偏置。简要的说，KBANN使用一个领域特定的理 论来偏置泛化，而反向传播算法使用一个领域无关的语法 偏置。

22、简要的说，KBANN使用一个领域特定的理论来偏 置泛化，而反向传播算法使用一个与领域无关的语法偏置。 注意，在此概述中我们忽略了搜索中的局部极小值的影响。 KBANN的局限性之一是只能使用命题领域理论，即无变 量的Horn子句集。如果给与很不精确的领域理论， KBANN也可能被误导，从而其泛化精度变得低于反向传 播，不过，KBANN和相关算法在若干实际问题中很有用。 KBANN是结合分析和归纳学习的初始化假设途经中的一种。这一途 径的其他例子包括Fu、Gallant、Bradshaw等等。这些途径不同之处 再与建立初始化假设的实际使用的技术、权值调整的反向传播的应用 以及从精化的网络中抽取符号

23、描述的方法。Pratt描述的一个初始化假 设途径中，先验知识是通过先前对相关任务学习到的神经网络来提供 的。训练贝叶斯的值的放方法也可能被看作是用先验知识来初始化假 设的。这里先验知识对于一组条件独立性假定，它确定了贝叶斯网的 图结构，然后期条件概率表从训练数据中归纳得到。 使用先验知识改变搜索目标使用先验知识改变搜索目标 将先验知识合并到梯度下降中需最小化的误差 判据，这样网络需要拟合的是训练数据和领域 理论的组合函数 TangentProp算法 TangentProp算法接受的领域知识被表示为对应于 其输入变换的目标函数的导数 例如，对每个实例xi描述为一个实数，那么每个训 练样例的形式可

24、能是 图12-5，基于3个训练样例学习目标函数f，通过拟 合训练值f(xi)的同时拟合相应的导数，学习器能 够实现更好的泛化 概括而言，包含训练导数的效果是为了克服反向传 播算法中的归纳偏置，将其替换为所希望的导数的 显示输入信息 ？P248-P249 i x x xf )( 33 34 TangentProp举例举例 Simard et al.提供了TangentProp的泛化精度 与纯归纳反向传播之间的比较结果 针对任务是为单个数字0到9的图像做标注 给予TangentProp的先验知识是：数字的分类不因 图像的水平和垂直平移而改变 表12-4，显示TangentProp的泛化精度高于纯反

25、向 传播算法 35 TangentProp的说明 TangentProp使用的先验知识形式为目标函数对应其输入变换的所 希望的导数 TangentProp通过使一个指标函数最小化来结合先验知识和观察到 的训练数据，这个指标函数同时度量了网络对应训练样例值的误 差和网络对应于导数的误差 值决定了网络在中个误差中拟合这两部分的程度，它由设计者选 择 TangentProp的不足：对于先验知识中的错误健壮性不强，而且不 能预先知道训练导数中的错误出现程度，因而不能很好地选择常 量以确定拟合训练值和训练导数的相对重要程度 36 TangentProp的说明（2） TangentProp和反向传播的搜索

26、方法比较 TangentProp通过改变梯度下降最小化的指标函数来 影响假设搜索，相当于改变了搜索目标 如果训练样例和先验知识都正确，并且目标函数可 用ANN精确表示，那么满足TangentProp指标的权向 量集合将为满足反向传播指标的权向量集合的子集， 一些不正确的假设会被TangentProp剔除掉 对目标函数的训练导数拟合的另一种方法是，简单地将观察到的 训练样例附近的附加训练样例综合起来，使用已知的训练导数来 估计这些附近的实例的训练值 37 EBNN算法 EBNN是基于解释的神经网络，它用两种方式改进了TangentProp 算法 它不依靠用户提供训练导数，而是对每个训练样例 自行

27、计算训练导数，计算方法是通过用一套给定的 领域理论来解释每个训练样例 涉及了如何确定学习过程中归纳和分析部分相对重 要程度的问题，的值是对每个训练样例独立选择的， 它基于一个启发式规则，考虑领域理论能否精确预 测特定样例的训练值 因此，对于那些能由领域理论正确解释的训练样例，学习 的分析成分被强化，而对不能正确解释的样例，分析成分 被弱化 38 EBNN算法（2） EBNN的输入包括： 形式为的一组训练样例，不包含训练导数 一组领域理论，表示为一组预先训练过的神经网络， 而不是KBANN采用的Horn子句 EBNN的输出：一个能逼近目标函数f的新的神经网络，学习到的 网络能够拟合训练样例以及从

28、领域理论中抽取的f的训练导数 图12-7，图的上面部分显示的是目标函数Cup的领域理论，每一方 块表示领域理论中一个神经网络，图的下面是要学习的新神经网 络，称为目标网络 39 EBNN算法（算法（3） EBNN通过执行TangentProp算法来学习目标 网络 EBNN把接收到的输入训练值和从领域 理论中计算出的导数提供给TangentProp EBNN计算训练导数的方法 ？ 40 EBNN算法的说明 概括地说，EBNN算法使用的领域理论被表示为一组预先学习到的 神经网络，然后领域理论与训练样例一起训练其输出假设 对每个训练样例，EBNN使用其领域理论来解释它，然后从此解释 中抽取训练导数

29、对实例的每个属性计算出一个训练导数，以描述按照领域理论， 目标函数值是怎样被属性值的微小变化影响的 Prolog-EBG与EBNN的区别 EBNN能够处理不完美的领域知识，而Prolog-EBG 不能 Prolog-EBG学习到逐渐增长的Horn子句集，而 EBNN学习到固定大小的神经网络 41 使用先验知识来扩展搜索算子 FOCL是纯归纳算法FOIL的一个扩展，它们的区别在于：搜索单个 Horn子句的一般到特殊过程中候选假设生成的方法 FOIL生成每个候选特化式是通过加入一个新文字到 子句前件中得到的 FOCL使用同样的方法产生候选特化式，但还基于领 域理论生成了附加的特化式 操作型文字和非操作型文字 操作型文字：当一个文字可被用于描述一个输出假 设 非操作型文字：只出现在领域理论中作为中间特征 但不是实例的原子属性的文字 42 FOCL算法 FOCL使用下面两种算子扩展当前假设h 对不是h一部分的每个操作型文字，创建h