第12章归纳和分析学习的结合

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–求解•一个最好地拟合训练样例和领域理论的假设•最好地拟合训练样例和领域理论的确切定义)()(minargherrorkherrorkBBDDHh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–使用先验知识改变可用的搜索步：Focl2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏10使用先验知识得到的初始假设•KBANN技术：一种使用先验知识的方法是将假设初始化为完美拟合领域理论，然后按照需要归纳地精化初始假设以拟合训练数据•这种技术的动机是：如果领域理论是正确的，初始假设将正确分类所有训练样例，而无需再修正；如果初始假设不能完美地分类训练样例，那么它需要被归纳精华，以改进它在训练样例上的拟合度•在纯粹归纳的反向传播算法中，权值一般被初始化为小的随机值，KBANN的含义是：即使领域理论是近似正确的，将网络初始化为拟合领域理论，比初始化为随机值有更好的近似开端2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏11KBANN算法•KBANN假定领域理论用一组命题形式的非递归的Horn子句来表示，输入和输出如下：–已知：•一组训练样例•由非递归命题型Horn子句组成的领域理论–求解：•一个拟合训练样例的被领域理论偏置的人工神经网络•KBANN算法包含两个阶段–创建一个完美拟合领域理论的人工神经网络–使用反向传播算法来精化初始网络以拟合训练样例2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏12表12-2KBANN算法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_Examples2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏13举例•表12-3Cup学习任务–领域理论–训练样例•在KBANN算法的第一步，构建一个与领域理论一致的初始网络，见图12-2–对领域理论中每个Horn子句建立一个sigmoid单元–对该Horn子句的每个先行词，建立其对应的Sigmoid单元作为输入–对于每个对应于非负先行词的输入，权值被设置为某正常量W，对每个对应于负先行词的输入，权值为-W–单元的阈值权w0设为-(n-0.5)W，其中n为非负先行词的数目–附加许多输入到每个阈值单元，它们的权值设置为近似0，从而允许网络能够学习到超出领域理论的依赖关系•在KBANN算法的第二步，使用训练样例和反向传播算法来精化网络权值•图12-3在归纳步发现了全新的依赖关系2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏14KBANN算法说明•KBANN的好处和局限–好处：在给定近似正确领域理论时，能够比反向传播有更高的泛化精度，特别是在训练数据稀少时–局限：只能使用命题领域理论，如果给予很不精确的领域理论，KBANN也可能被误导，从而其泛化精度变得低于反向传播2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏15使用先验知识改变搜索目标•将先验知识合并到梯度下降中需最小化的误差判据，这样网络需要拟合的是训练数据和领域理论的组合函数•TangentProp算法–TangentProp算法接受的领域知识被表示为对应于其输入变换的目标函数的导数–例如，对每个实例xi描述为一个实数，那么每个训练样例的形式可能是xi,f(xi),–图12-5，基于3个训练样例学习目标函数f，通过拟合训练值f(xi)的同时拟合相应的导数，学习器能够实现更好的泛化–概括而言，包含训练导数的效果是为了克服反向传播算法中的归纳偏置，将其替换为所希望的导数的显示输入信息–？？？P248-P249ixxxf)(2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏16TangentProp举例•Simardetal.提供了TangentProp的泛化精度与纯归纳反向传播之间的比较结果–针对任务是为单个数字0到9的图像做标注–给予TangentProp的先验知识是：数字的分类不因图像的水平和垂直平移而改变–表12-4，显示TangentProp的泛化精度高于纯反向传播算法2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏17TangentProp的说明•TangentProp使用的先验知识形式为目标函数对应其输入变换的所希望的导数•TangentProp通过使一个指标函数最小化来结合先验知识和观察到的训练数据，这个指标函数同时度量了网络对应训练样例值的误差和网络对应于导数的误差•值决定了网络在中个误差中拟合这两部分的程度，它由设计者选择•TangentProp的不足：对于先验知识中的错误健壮性不强，而且不能预先知道训练导数中的错误出现程度，因而不能很好地选择常量以确定拟合训练值和训练导数的相对重要程度2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏18TangentProp的说明（2）•TangentProp和反向传播的搜索方法比较–TangentProp通过改变梯度下降最小化的指标函数来影响假设搜索，相当于改变了搜索目标–如果训练样例和先验知识都正确，并且目标函数可用ANN精确表示，那么满足TangentProp指标的权向量集合将为满足反向传播指标的权向量集合的子集，一些不正确的假设会被TangentProp剔除掉•对目标函数的训练导数拟合的另一种方法是，简单地将观察到的训练样例附近的附加训练样例综合起来，使用已知的训练导数来估计这些附近的实例的训练值2003.12.18机器学习-归纳和分析学习的结合作者：Mitchell译者：曾华军等讲者：陶晓鹏19EBNN算法•EBNN是基于解释的神经网络，它用两种方式改进了TangentProp算法–它不依靠用户提供训练导数，而是对每个训练样例自行计算训练导数，计算方法是通过用一套给定的领域理论来解释每个训练样例–涉及了如何确定学习过程中归纳和分析部分相对重要程度的问题，的值是对每个训练样例独立选择的，它基于一个启发式规则，考虑领域理论能否精确预测特定样例的训练值•因此，对于那些能由领