2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 1
机器学习第 12章 归纳和分析学习的结合
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
纯粹的归纳学习方法通过在训练样例中寻找经验化的规律来形成一般假设
纯粹的分析方法使用先验知识演绎推导一般假设
本章考虑将归纳和分析的机制结合起来的方法，
并获得两者的优点：有先验知识时获得更高的泛化精度和依赖训练数据克服先验知识的不足
所得到的结合的方法比纯粹的归纳方法和分析方法的性能都要高
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
归纳学习寻找拟合训练数据的一般假设，分析学习寻找拟合先验知识的一般假设，同时使它覆盖训练数据
归纳方法和分析方法对假设的论证方法有根本区别，
因此优缺点互为补充，将它们结合起来有可能得到更强有力的学习方法
纯粹的分析学习方法的优缺点
– 优点：可用先验知识从较少的数据中更精确地泛化以引导学习
– 缺点：当先验知识不足或不正确时，可能产生误导
纯粹的归纳学习方法的优缺点
– 优点：不需要显示的先验知识，主要基于训练数据学习规律
– 缺点：训练数据不足时，会失败，会被其中隐式的归纳偏置所误导
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
表 12-1 纯粹的分析学习和纯粹的归纳学习的比较归纳学习 分析学习目标 拟合数据的假设 拟合领域理论的假设论证 统计推理 演绎推理优点 需要很少先验知识 从稀少的数据中学习缺陷 稀少的数据，不正确的偏置不完美的领域理论
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
动机（ 2）
图 12-1
– 概述了学习问题的分布范围，它随着可获得的先验知识和训练数据不同而变化
– 在一个极端，有大量的训练数据，但没有先验知识
– 在另一个极端，有很强的先验知识，但训练数据很少
– 多数实际学习问题位于这两个极端之间，通常可以从近似的先验知识开始
本章考虑的问题是：
– 什么样的算法，使用近似的先验知识结合可用数据来形成一般的假设
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
动机（ 3）
即使使用最纯粹的归纳学习算法，仍有机会基于特定学习任务的先验知识来选择设计方案
通常设计者将领域特定的知识嵌入到学习算法中，但我们感兴趣的是一个系统能将先验知识和训练数据作为显示的输入给学习器
概括而言，我们感兴趣的是领域无关算法，这种算法使用显示输入的领域相关的知识，这种算法具备以下的属性：
– 如果没有领域理论，它至少能像纯粹的归纳方法一样有效学习
– 如果没有完美的领域理论，它至少能像纯粹的分析方法一样有效学习
– 如果领域理论和训练数据都不完美，它应能结合两者的长处，比单纯的归纳或分析方法的性能要好
– 它应能处理训练数据中未知程度的差错
– 它应能处理领域理论中未知程度的差错
这里列出的期望目标很难达到，目前没有算法能以一般化的方式满足所有这些约束
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
学习的归纳 -分析途径
本章考虑的学习问题
– 已知
一个训练样例集合 D，可能包含差错
一个领域理论 B，可能包含差错
候选假设的空间 H
– 求解
一个最好地拟合训练样例和领域理论的假设
最好地拟合训练样例和领域理论的确切定义
)()(m ina r g he r r o rkhe r r o rk BBDDHh
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
学习的归纳 -分析途径（ 2）
确定先验知识和数据权值的一种解决方法是使用贝叶斯观点
– 贝叶斯定律描述了怎样计算给定训练数据 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)概率分布的完美知识
贝叶斯公式没有提供将这些近似已知的概率分布与观察数据结合起来的方法
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
假设空间搜索
大多数学习任务可以刻画为假设空间上的搜索任务,而决定这个搜索任务的 4个参数是：
– 假设空间 H
– 搜索的初始假设 h0
– 定义单个搜索步的搜索算子集合 O
– 指定搜索目标的判据 G
本章探索了 3种方法，它们用先验知识来改变纯归纳方法执行的搜索
– 使用先验知识推导出搜索起步的初始假设,Kbann
– 使用先验知识来改变假设空间搜索的目标,Ebnn
– 使用先验知识改变可用的搜索步,Focl
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
使用先验知识得到的初始假设
KBANN技术：一种使用先验知识的方法是将假设初始化为完美拟合领域理论,然后按照需要归纳地精化初始假设以拟合训练数据
这种技术的动机是：如果领域理论是正确的，初始假设将正确分类所有训练样例，而无需再修正；如果初始假设不能完美地分类训练样例，那么它需要被归纳精华，以改进它在训练样例上的拟合度
在纯粹归纳的反向传播算法中，权值一般被初始化为小的随机值,KBANN的含义是：即使领域理论是近似正确的，将网络初始化为拟合领域理论，比初始化为随机值有更好的近似开端
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
KBANN算法
KBANN假定领域理论用一组命题形式的非递归的 Horn子句来表示，输入和输出如下：
– 已知：
一组训练样例
由非递归命题型 Horn子句组成的领域理论
– 求解：
一个拟合训练样例的被领域理论偏置的人工神经网络
KBANN算法包含两个阶段
– 创建一个完美拟合领域理论的人工神经网络
– 使用反向传播算法来精化初始网络以拟合训练样例
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 12-2 KBANN算法
KBANN(Domain_Theory,Training_Examples)
Domain_Theory：非递归命题型 Horn子句集
Training_Examples：目标函数的 <input,output>对的集合
分析步：创建一个等价于领域理论的初始网络
– 对每个实例属性创建一个网络输入
– 对 Domain_Theory的每个 Horn子句，创建如下的网络单元
连接此单元的输入到此子句的先行词测试的属性
对子句的每个非负先行词，赋予权值 W给对应的 sigmoid单元输入
对子句的每个负先行词，赋予权值 -W给对应的 sigmoid单元输入
设置此单元的阈值 w0为 -(n-0.5)W，其中 n为子句的非负先行词的数目
– 在网络单元之间增加附加的连接，连接深度为 i的每个网络单元到深度为 i+1的所有网络单元的输入层上，赋予这些附加的连接为接近 0的随机权值
归纳步：精化此初始网络
– 应用反向传播算法来调整初始网络权值以拟合 Training_Examples
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
举例
表 12-3 Cup学习任务
– 领域理论
– 训练样例
在 KBANN算法的第一步，构建一个与领域理论一致的初始网络，
见图 12-2
– 对领域理论中每个 Horn子句建立一个 sigmoid单元
– 对该 Horn子句的每个先行词，建立其对应的 Sigmoid单元作为输入
– 对于每个对应于非负先行词的输入，权值被设置为某正常量 W，对每个对应于负先行词的输入，权值为 -W
– 单元的阈值权 w0设为 -(n-0.5)W，其中 n为非负先行词的数目
– 附加许多输入到每个阈值单元，它们的权值设置为近似 0，从而允许网络能够学习到超出领域理论的依赖关系
在 KBANN算法的第二步，使用训练样例和反向传播算法来精化网络权值
图 12-3在归纳步发现了全新的依赖关系
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
KBANN算法说明
KBANN的好处和局限
– 好处：在给定近似正确领域理论时，能够比反向传播有更高的泛化精度，特别是在训练数据稀少时
– 局限：只能使用命题领域理论，如果给予很不精确的领域理论,KBANN也可能被误导，
从而其泛化精度变得低于反向传播
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
使用先验知识改变搜索目标
将先验知识合并到梯度下降中需最小化的误差判据，
这样网络需要拟合的是训练数据和领域理论的组合函数
TangentProp算法
– TangentProp算法接受的领域知识被表示为对应于其输入变换的目标函数的导数
– 例如，对每个实例 xi描述为一个实数，那么每个训练样例的形式可能是 <xi,f(xi),>
– 图 12-5，基于 3个训练样例学习目标函数 f，通过拟合训练值
f(xi)的同时拟合相应的导数，学习器能够实现更好的泛化
– 概括而言，包含训练导数的效果是为了克服反向传播算法中的归纳偏置，将其替换为所希望的导数的显示输入信息
–？？？ P248-P249
ixx
xf )(
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
TangentProp举例
Simard et al.提供了 TangentProp的泛化精度与纯归纳反向传播之间的比较结果
– 针对任务是为单个数字 0到 9的图像做标注
– 给予 TangentProp的先验知识是：数字的分类不因图像的水平和垂直平移而改变
– 表 12-4，显示 TangentProp的泛化精度高于纯反向传播算法
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
TangentProp的说明
TangentProp使用的先验知识形式为目标函数对应其输入变换的所希望的导数
TangentProp通过使一个指标函数最小化来结合先验知识和观察到的训练数据，这个指标函数同时度量了网络对应训练样例值的误差和网络对应于导数的误差
值决定了网络在中个误差中拟合这两部分的程度，它由设计者选择
TangentProp的不足：对于先验知识中的错误健壮性不强，而且不能预先知道训练导数中的错误出现程度，
因而不能很好地选择常量?以确定拟合训练值和训练导数的相对重要程度
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
TangentProp的说明（ 2）
TangentProp和反向传播的搜索方法比较
– TangentProp通过改变梯度下降最小化的指标函数来影响假设搜索，相当于改变了搜索目标
– 如果训练样例和先验知识都正确，并且目标函数可用 ANN精确表示，那么满足 TangentProp指标的权向量集合将为满足反向传播指标的权向量集合的子集，
一些不正确的假设会被 TangentProp剔除掉
对目标函数的训练导数拟合的另一种方法是，
简单地将观察到的训练样例附近的附加训练样例综合起来，使用已知的训练导数来估计这些附近的实例的训练值
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
EBNN算法
EBNN是基于解释的神经网络，它用两种方式改进了 TangentProp算法
– 它不依靠用户提供训练导数，而是对每个训练样例自行计算训练导数，计算方法是通过用一套给定的领域理论来解释每个训练样例
– 涉及了如何确定学习过程中归纳和分析部分相对重要程度的问题,?的值是对每个训练样例独立选择的，它基于一个启发式规则，考虑领域理论能否精确预测特定样例的训练值
因此，对于那些能由领域理论正确解释的训练样例，学习的分析成分被强化，而对不能正确解释的样例，分析成分被弱化
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
EBNN算法（ 2）
EBNN的输入包括：
– 形式为 <xi,f(xi)>的一组训练样例，不包含训练导数
– 一组领域理论，表示为一组预先训练过的神经网络，而不是
KBANN采用的 Horn子句
EBNN的输出：一个能逼近目标函数 f的新的神经网络，
学习到的网络能够拟合训练样例以及从领域理论中抽取的 f的训练导数
图 12-7，图的上面部分显示的是目标函数 Cup的领域理论，每一方块表示领域理论中一个神经网络，图的下面是要学习的新神经网络，称为目标网络
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
EBNN算法（ 3）
EBNN通过执行 TangentProp算法来学习目标网络
– EBNN把接收到的输入训练值 <xi,f(xi)>和从领域理论中计算出的导数提供给 TangentProp
EBNN计算训练导数的方法
–？？？
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
EBNN算法的说明
概括地说,EBNN算法使用的领域理论被表示为一组预先学习到的神经网络，然后领域理论与训练样例一起训练其输出假设
对每个训练样例,EBNN使用其领域理论来解释它，然后从此解释中抽取训练导数
对实例的每个属性计算出一个训练导数，以描述按照领域理论，目标函数值是怎样被属性值的微小变化影响的
Prolog-EBG与 EBNN的区别
– EBNN能够处理不完美的领域知识，而 Prolog-EBG不能
– Prolog-EBG学习到逐渐增长的 Horn子句集，而 EBNN学习到固定大小的神经网络
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
使用先验知识来扩展搜索算子
FOCL是纯归纳算法 FOIL的一个扩展，它们的区别在于：搜索单个 Horn子句的一般到特殊过程中候选假设生成的方法
– FOIL生成每个候选特化式是通过加入一个新文字到子句前件中得到的
– FOCL使用同样的方法产生候选特化式，但还基于领域理论生成了附加的特化式
操作型文字和非操作型文字
– 操作型文字：当一个文字可被用于描述一个输出假设
– 非操作型文字：只出现在领域理论中作为中间特征但不是实例的原子属性的文字
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
FOCL算法
FOCL使用下面两种算子扩展当前假设 h
– 对不是 h一部分的每个操作型文字，创建 h的一个特化式，方法是加入文字到前件中
– 按照领域理论，创建一个操作型的且是目标概念的逻辑充分条件，将这组文字加入到 h的当前前件中，最后修剪 h的前件，
移去对于训练数据不需要的文字，具体过程如下：
首先选择一条领域理论子句，它的头部匹配目标概念，如果有多个这样的子句，选择其中子句体关于训练样例有最高信息增益的
所选子句的前件形成了目标概念的一个逻辑充分条件，在这些充分条件中，再次使用领域理论，每个非操作型文字被替换掉，将子句前件代入到子句后件中
这个展开的过程持续到充分条件被表述为操作型文字，如果有多个可选的展开，那么用贪婪法选择有最大信息增益的一个
最后，修剪充分条件。对表达式中的每个文字，除非文字的移除会降低训练样例上的分类精度，否则它被移去
上面的讨论很容易扩展到一阶表示中，类似第 10章
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
FOCL的说明
图 12-9比较了 FOCL和纯归纳的 FOIL执行的假设空间搜索
– FOCL中领域理论推举的特化式对应 FOIL搜索中的一个宏步，
其中多个文字在一步中被加入
FOCL使用语法生成候选特化式的同时，还在搜索中每一步使用领域理论驱动生成候选特化式
领域理论的使用方式是使学习器偏置：优先选择最相似于领域理论涵蕴的操作型的逻辑充分条件的 Horn子句
结合分析和归纳的方法，还没有一个在大范围的问题领域中被彻底测试或证明，仍是一个很活跃的研究领域
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
小结
结合归纳和分析学习的方法可以获得两者（归纳和分析）的优点，减小样本复杂度，并且否决不正确的先验知识
结合的方法通过领域理论影响假设空间的搜索来实现，主要有,1）影响初始假设； 2）影响当前假设的搜索算子集合； 3）影响搜索目标
KBANN影响初始假设，使用领域理论建立初始神经网络，然后使用反向传播算法进行精化
TangentProp使用先验知识被表示为目标函数所希望的导数，并改变了指标函数
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
小结（ 2）
EBNN使用领域理论改变神经网络搜索的假设空间的目标。领域理论由预先学习的神经网络组成，需要的导数信息来自神经网络
FOCL使用领域理论来扩展搜索中考虑的候选集，结合了 FOIL的贪婪的、一般到特殊的搜索策略以及分析方法中的规则链分析推理
还有很多算法试图结合归纳和分析学习，比如第 6章讨论的学习贝叶斯网的方法提供了另一种途径
机器学习第 12章 归纳和分析学习的结合
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 2
概述
纯粹的归纳学习方法通过在训练样例中寻找经验化的规律来形成一般假设
纯粹的分析方法使用先验知识演绎推导一般假设
本章考虑将归纳和分析的机制结合起来的方法，
并获得两者的优点：有先验知识时获得更高的泛化精度和依赖训练数据克服先验知识的不足
所得到的结合的方法比纯粹的归纳方法和分析方法的性能都要高
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 3
动机
归纳学习寻找拟合训练数据的一般假设，分析学习寻找拟合先验知识的一般假设，同时使它覆盖训练数据
归纳方法和分析方法对假设的论证方法有根本区别，
因此优缺点互为补充，将它们结合起来有可能得到更强有力的学习方法
纯粹的分析学习方法的优缺点
– 优点：可用先验知识从较少的数据中更精确地泛化以引导学习
– 缺点：当先验知识不足或不正确时，可能产生误导
纯粹的归纳学习方法的优缺点
– 优点：不需要显示的先验知识，主要基于训练数据学习规律
– 缺点：训练数据不足时，会失败，会被其中隐式的归纳偏置所误导
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 4
表 12-1 纯粹的分析学习和纯粹的归纳学习的比较归纳学习 分析学习目标 拟合数据的假设 拟合领域理论的假设论证 统计推理 演绎推理优点 需要很少先验知识 从稀少的数据中学习缺陷 稀少的数据，不正确的偏置不完美的领域理论
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 5
动机（ 2）
图 12-1
– 概述了学习问题的分布范围，它随着可获得的先验知识和训练数据不同而变化
– 在一个极端，有大量的训练数据，但没有先验知识
– 在另一个极端，有很强的先验知识，但训练数据很少
– 多数实际学习问题位于这两个极端之间，通常可以从近似的先验知识开始
本章考虑的问题是：
– 什么样的算法，使用近似的先验知识结合可用数据来形成一般的假设
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 6
动机（ 3）
即使使用最纯粹的归纳学习算法，仍有机会基于特定学习任务的先验知识来选择设计方案
通常设计者将领域特定的知识嵌入到学习算法中，但我们感兴趣的是一个系统能将先验知识和训练数据作为显示的输入给学习器
概括而言，我们感兴趣的是领域无关算法，这种算法使用显示输入的领域相关的知识，这种算法具备以下的属性：
– 如果没有领域理论，它至少能像纯粹的归纳方法一样有效学习
– 如果没有完美的领域理论，它至少能像纯粹的分析方法一样有效学习
– 如果领域理论和训练数据都不完美，它应能结合两者的长处，比单纯的归纳或分析方法的性能要好
– 它应能处理训练数据中未知程度的差错
– 它应能处理领域理论中未知程度的差错
这里列出的期望目标很难达到，目前没有算法能以一般化的方式满足所有这些约束
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 7
学习的归纳 -分析途径
本章考虑的学习问题
– 已知
一个训练样例集合 D，可能包含差错
一个领域理论 B，可能包含差错
候选假设的空间 H
– 求解
一个最好地拟合训练样例和领域理论的假设
最好地拟合训练样例和领域理论的确切定义
)()(m ina r g he r r o rkhe r r o rk BBDDHh
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
学习的归纳 -分析途径（ 2）
确定先验知识和数据权值的一种解决方法是使用贝叶斯观点
– 贝叶斯定律描述了怎样计算给定训练数据 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)概率分布的完美知识
贝叶斯公式没有提供将这些近似已知的概率分布与观察数据结合起来的方法
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
假设空间搜索
大多数学习任务可以刻画为假设空间上的搜索任务,而决定这个搜索任务的 4个参数是：
– 假设空间 H
– 搜索的初始假设 h0
– 定义单个搜索步的搜索算子集合 O
– 指定搜索目标的判据 G
本章探索了 3种方法，它们用先验知识来改变纯归纳方法执行的搜索
– 使用先验知识推导出搜索起步的初始假设,Kbann
– 使用先验知识来改变假设空间搜索的目标,Ebnn
– 使用先验知识改变可用的搜索步,Focl
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
使用先验知识得到的初始假设
KBANN技术：一种使用先验知识的方法是将假设初始化为完美拟合领域理论,然后按照需要归纳地精化初始假设以拟合训练数据
这种技术的动机是：如果领域理论是正确的，初始假设将正确分类所有训练样例，而无需再修正；如果初始假设不能完美地分类训练样例，那么它需要被归纳精华，以改进它在训练样例上的拟合度
在纯粹归纳的反向传播算法中，权值一般被初始化为小的随机值,KBANN的含义是：即使领域理论是近似正确的，将网络初始化为拟合领域理论，比初始化为随机值有更好的近似开端
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
KBANN算法
KBANN假定领域理论用一组命题形式的非递归的 Horn子句来表示，输入和输出如下：
– 已知：
一组训练样例
由非递归命题型 Horn子句组成的领域理论
– 求解：
一个拟合训练样例的被领域理论偏置的人工神经网络
KBANN算法包含两个阶段
– 创建一个完美拟合领域理论的人工神经网络
– 使用反向传播算法来精化初始网络以拟合训练样例
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 12-2 KBANN算法
KBANN(Domain_Theory,Training_Examples)
Domain_Theory：非递归命题型 Horn子句集
Training_Examples：目标函数的 <input,output>对的集合
分析步：创建一个等价于领域理论的初始网络
– 对每个实例属性创建一个网络输入
– 对 Domain_Theory的每个 Horn子句，创建如下的网络单元
连接此单元的输入到此子句的先行词测试的属性
对子句的每个非负先行词，赋予权值 W给对应的 sigmoid单元输入
对子句的每个负先行词，赋予权值 -W给对应的 sigmoid单元输入
设置此单元的阈值 w0为 -(n-0.5)W，其中 n为子句的非负先行词的数目
– 在网络单元之间增加附加的连接，连接深度为 i的每个网络单元到深度为 i+1的所有网络单元的输入层上，赋予这些附加的连接为接近 0的随机权值
归纳步：精化此初始网络
– 应用反向传播算法来调整初始网络权值以拟合 Training_Examples
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
举例
表 12-3 Cup学习任务
– 领域理论
– 训练样例
在 KBANN算法的第一步，构建一个与领域理论一致的初始网络，
见图 12-2
– 对领域理论中每个 Horn子句建立一个 sigmoid单元
– 对该 Horn子句的每个先行词，建立其对应的 Sigmoid单元作为输入
– 对于每个对应于非负先行词的输入，权值被设置为某正常量 W，对每个对应于负先行词的输入，权值为 -W
– 单元的阈值权 w0设为 -(n-0.5)W，其中 n为非负先行词的数目
– 附加许多输入到每个阈值单元，它们的权值设置为近似 0，从而允许网络能够学习到超出领域理论的依赖关系
在 KBANN算法的第二步，使用训练样例和反向传播算法来精化网络权值
图 12-3在归纳步发现了全新的依赖关系
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
KBANN算法说明
KBANN的好处和局限
– 好处：在给定近似正确领域理论时，能够比反向传播有更高的泛化精度，特别是在训练数据稀少时
– 局限：只能使用命题领域理论，如果给予很不精确的领域理论,KBANN也可能被误导，
从而其泛化精度变得低于反向传播
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
使用先验知识改变搜索目标
将先验知识合并到梯度下降中需最小化的误差判据，
这样网络需要拟合的是训练数据和领域理论的组合函数
TangentProp算法
– TangentProp算法接受的领域知识被表示为对应于其输入变换的目标函数的导数
– 例如，对每个实例 xi描述为一个实数，那么每个训练样例的形式可能是 <xi,f(xi),>
– 图 12-5，基于 3个训练样例学习目标函数 f，通过拟合训练值
f(xi)的同时拟合相应的导数，学习器能够实现更好的泛化
– 概括而言，包含训练导数的效果是为了克服反向传播算法中的归纳偏置，将其替换为所希望的导数的显示输入信息
–？？？ P248-P249
ixx
xf )(
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
TangentProp举例
Simard et al.提供了 TangentProp的泛化精度与纯归纳反向传播之间的比较结果
– 针对任务是为单个数字 0到 9的图像做标注
– 给予 TangentProp的先验知识是：数字的分类不因图像的水平和垂直平移而改变
– 表 12-4，显示 TangentProp的泛化精度高于纯反向传播算法
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
TangentProp的说明
TangentProp使用的先验知识形式为目标函数对应其输入变换的所希望的导数
TangentProp通过使一个指标函数最小化来结合先验知识和观察到的训练数据，这个指标函数同时度量了网络对应训练样例值的误差和网络对应于导数的误差
值决定了网络在中个误差中拟合这两部分的程度，它由设计者选择
TangentProp的不足：对于先验知识中的错误健壮性不强，而且不能预先知道训练导数中的错误出现程度，
因而不能很好地选择常量?以确定拟合训练值和训练导数的相对重要程度
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
TangentProp的说明（ 2）
TangentProp和反向传播的搜索方法比较
– TangentProp通过改变梯度下降最小化的指标函数来影响假设搜索，相当于改变了搜索目标
– 如果训练样例和先验知识都正确，并且目标函数可用 ANN精确表示，那么满足 TangentProp指标的权向量集合将为满足反向传播指标的权向量集合的子集，
一些不正确的假设会被 TangentProp剔除掉
对目标函数的训练导数拟合的另一种方法是，
简单地将观察到的训练样例附近的附加训练样例综合起来，使用已知的训练导数来估计这些附近的实例的训练值
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
EBNN算法
EBNN是基于解释的神经网络，它用两种方式改进了 TangentProp算法
– 它不依靠用户提供训练导数，而是对每个训练样例自行计算训练导数，计算方法是通过用一套给定的领域理论来解释每个训练样例
– 涉及了如何确定学习过程中归纳和分析部分相对重要程度的问题,?的值是对每个训练样例独立选择的，它基于一个启发式规则，考虑领域理论能否精确预测特定样例的训练值
因此，对于那些能由领域理论正确解释的训练样例，学习的分析成分被强化，而对不能正确解释的样例，分析成分被弱化
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
EBNN算法（ 2）
EBNN的输入包括：
– 形式为 <xi,f(xi)>的一组训练样例，不包含训练导数
– 一组领域理论，表示为一组预先训练过的神经网络，而不是
KBANN采用的 Horn子句
EBNN的输出：一个能逼近目标函数 f的新的神经网络，
学习到的网络能够拟合训练样例以及从领域理论中抽取的 f的训练导数
图 12-7，图的上面部分显示的是目标函数 Cup的领域理论，每一方块表示领域理论中一个神经网络，图的下面是要学习的新神经网络，称为目标网络
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
EBNN算法（ 3）
EBNN通过执行 TangentProp算法来学习目标网络
– EBNN把接收到的输入训练值 <xi,f(xi)>和从领域理论中计算出的导数提供给 TangentProp
EBNN计算训练导数的方法
–？？？
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
EBNN算法的说明
概括地说,EBNN算法使用的领域理论被表示为一组预先学习到的神经网络，然后领域理论与训练样例一起训练其输出假设
对每个训练样例,EBNN使用其领域理论来解释它，然后从此解释中抽取训练导数
对实例的每个属性计算出一个训练导数，以描述按照领域理论，目标函数值是怎样被属性值的微小变化影响的
Prolog-EBG与 EBNN的区别
– EBNN能够处理不完美的领域知识，而 Prolog-EBG不能
– Prolog-EBG学习到逐渐增长的 Horn子句集，而 EBNN学习到固定大小的神经网络
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
使用先验知识来扩展搜索算子
FOCL是纯归纳算法 FOIL的一个扩展，它们的区别在于：搜索单个 Horn子句的一般到特殊过程中候选假设生成的方法
– FOIL生成每个候选特化式是通过加入一个新文字到子句前件中得到的
– FOCL使用同样的方法产生候选特化式，但还基于领域理论生成了附加的特化式
操作型文字和非操作型文字
– 操作型文字：当一个文字可被用于描述一个输出假设
– 非操作型文字：只出现在领域理论中作为中间特征但不是实例的原子属性的文字
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
FOCL算法
FOCL使用下面两种算子扩展当前假设 h
– 对不是 h一部分的每个操作型文字，创建 h的一个特化式，方法是加入文字到前件中
– 按照领域理论，创建一个操作型的且是目标概念的逻辑充分条件，将这组文字加入到 h的当前前件中，最后修剪 h的前件，
移去对于训练数据不需要的文字，具体过程如下：
首先选择一条领域理论子句，它的头部匹配目标概念，如果有多个这样的子句，选择其中子句体关于训练样例有最高信息增益的
所选子句的前件形成了目标概念的一个逻辑充分条件，在这些充分条件中，再次使用领域理论，每个非操作型文字被替换掉，将子句前件代入到子句后件中
这个展开的过程持续到充分条件被表述为操作型文字，如果有多个可选的展开，那么用贪婪法选择有最大信息增益的一个
最后，修剪充分条件。对表达式中的每个文字，除非文字的移除会降低训练样例上的分类精度，否则它被移去
上面的讨论很容易扩展到一阶表示中，类似第 10章
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
FOCL的说明
图 12-9比较了 FOCL和纯归纳的 FOIL执行的假设空间搜索
– FOCL中领域理论推举的特化式对应 FOIL搜索中的一个宏步，
其中多个文字在一步中被加入
FOCL使用语法生成候选特化式的同时，还在搜索中每一步使用领域理论驱动生成候选特化式
领域理论的使用方式是使学习器偏置：优先选择最相似于领域理论涵蕴的操作型的逻辑充分条件的 Horn子句
结合分析和归纳的方法，还没有一个在大范围的问题领域中被彻底测试或证明，仍是一个很活跃的研究领域
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
小结
结合归纳和分析学习的方法可以获得两者（归纳和分析）的优点，减小样本复杂度，并且否决不正确的先验知识
结合的方法通过领域理论影响假设空间的搜索来实现，主要有,1）影响初始假设； 2）影响当前假设的搜索算子集合； 3）影响搜索目标
KBANN影响初始假设，使用领域理论建立初始神经网络，然后使用反向传播算法进行精化
TangentProp使用先验知识被表示为目标函数所希望的导数，并改变了指标函数
2003.12.18 机器学习 -归纳和分析学习的结合 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 27
小结（ 2）
EBNN使用领域理论改变神经网络搜索的假设空间的目标。领域理论由预先学习的神经网络组成，需要的导数信息来自神经网络
FOCL使用领域理论来扩展搜索中考虑的候选集，结合了 FOIL的贪婪的、一般到特殊的搜索策略以及分析方法中的规则链分析推理
还有很多算法试图结合归纳和分析学习，比如第 6章讨论的学习贝叶斯网的方法提供了另一种途径
