AI 版 (精华区)

发信人: samuel (孔雀翎), 信区: AI
标  题: 拙作——关于《机器学习》第12章
发信站: 哈工大紫丁香 (2003年06月12日11:03:15 星期四), 站内信件

纯粹的应付老师的，大家多提意见
归纳与分析学习的结合
孔雀翎
(哈尔滨工程大学计算机科学与技术学院,哈尔滨,150001)

摘要:纯粹的归纳学习方法通过在训练样例中寻找经验化的规律来形成一般假设。纯粹的分
析方法使用先验知识演绎推导一般假设。本文考虑将归纳和分析的机制结合起来的方法，
获得两者的优点：由先验知识时更高的泛化精度和依赖训练数据克服先验知识的不足。所
得到的结合的方法比纯粹的归纳学习方法和纯粹的分析学习方法性能都要高。本文考虑的
归纳-分析学习方法同时基于符号表示和人工神经网络表示。

关键词: 人工智能 机器学习 归纳学习 分析学习

一、    引言
纯粹的分析学习方法优点在于，可用先验只是从较少的数据中更精确的泛化以引导学习，
然而当先验只是不正确或不足时，这一方法可能会产生误导。纯粹的归纳方法具有的优点
是不需要显式的先验知识，并且主要基于训练数据学习规律。然而，若训练数据不足时它
会失败，并且会被其中隐式的归纳偏置所误导，而归纳偏置侍从观察数据中泛化所必需的
。
 
有纯粹的分析学习输出的假设执行的是逻辑论证：输出的假设从领域理论和训练数据中演
绎派生。纯粹的归纳学习方法输出的假设执行的是统计论证：输出的假设从统计论据中派
生。
由于分析方法提出逻辑论证的假设，而归纳方法提供统计论证的假设，很容易看出将两者
结合起来的好处是什么。逻辑论证的强度只相当于它们所基于的假定和先验知识。如果先
验知识不确定或不可知，逻辑论证是不可信和无说服力的。统计论证的强度依赖于它们基
于的数据和统计假定。当基准分布不可信或数据稀少时，统计论证也是不可信且无力的。
简而言之，两种方法针对不同类型的问题才有效。通过两者的结合，有望开发出更通用的
学习方法，可以覆盖较广的学习任务。
多数实际学习问题位于这两个极端之间。
 
本文要考虑的问题是："我们可以设计出怎样的算法，使用近似的先验知识结合可用数据来
形成一般假设？"
二、    国内外研究状况
1．一种使用先验知识的方法是，将假设初始化为完美拟合领域理论，然后按照需要归纳地
精化此初始假设以拟合训练数据。很容易看出，该技术的动机在于：如果领域理论是正确
的，初始假设将正确分类所有的训练样例,而无需再修正。然而，如果初始假设不能完美的
分类训练样例，那么它需要被归纳精化，以改进它在训练样例上的拟合度。这种方法被用
于KBANN算法中。
 
注意领域理论并不是和训练样例完全一致的。
 
每个单元的构建方法为：当对应的Horn子句存在时，单元的输出就大于0.5。确切的讲，对
于每个对应于非负先行词的输入，权值被设置为某正常量W。对每个对应于负先行词的输入
，权值设置为-W。单元的阈值权w0设为-(n-0.5)W，其中n为非负先行词的数目。
 
概括的讲，KBANN用分析的方法创建了等价于给定领域理论的网络，然后归纳的精化此处使
假设以更好的拟合训练数据。在此过程中，它为了改变领域理论和训练数据不一致的情况
而修改网络权值。
 
与纯归纳的反向传播相比，KBANN的好处在于，它在给定近似正确领域理论时，能够比反向
传播有更高的泛化精度，特别是在训练数据稀少时。
 
2．使用先验知识的另一方法是将它合并到梯度下降中需最小化的误差判据，这样的网络需
要拟合的是训练数据和领域理论的组合函数。下面描述的TANGENTPROP算法训练神经网络，
使其同时拟和训练值和训练导数。
 
在TANGENTPROP中，误差函数中新增了一项以惩罚训练导数和学习到的神经网络函数的实际
导数之间的分歧。
 
在一个实验中，TANGENTPROP和反向传播都用不同大小的训练集合进行训练，然后基于它们
在独立的160个样例的测试集合上评估性能。给予TANGENTPROP的先验知识为：数字的分类
不因图像的水平和垂直平移而改变。
 
概括的说，TANGENTPROP使用的先验知识形式为目标函数对应其输入变换的所希望的导数。
它通过使一个指标函数最小化来结合先验知识和观察到的训练数据，这个指标函数同时度
量了网络对应训练样例值的误差（拟合数据）和网络对应于导数的误差（拟合先验知识）
。
 
3．还可以考虑使用先验知识来改变假设空间搜索的第三种方法：即改变搜索中定义合法搜
索步的算子集合。这一途径被用于FOCL系统。
 
此过程可悲看成是将一个可能以后被考虑的假设提升为立即被考虑的假设。如果领域理论
是正确的，训练数据会显示初次假设相对于其他假设的优越性，因此它被选择。如果领域
理论不正确，对所有候选的经验化评估会将搜索导向另为一条途径。
 
三、    主要研究方法
1．近似的先验知识在许多实际学习问题中是可利用的。决策树和神经网络反向传播这样的
纯归纳方法不能利用这样的领域理论，因此在数据缺少时性能较差。Prolog-EBG这样的纯
分析学习方法能够利用这样的领域理论，但在给定不完美的先验知识是会产生不正确的假
设。集合归纳和分析学习的方法可以获得两者的优点，减小样本复杂度，并且否决不正确
的先验知识。
2．看待结合归纳和分析学习算法的一种方法时，考虑领域理论是如何影响假设空间搜索的
。
3．使用领域理论来初始化假设的一个系统是KBANN。此算法使用一套编码为命题规则的领
域理论来分析的创建等价于领域理论的神经网络。然后此网络被反向传播算法归纳的精化
，以改进它在训练数据上的性能。结果是一个被原始领域理论偏置的网络，它的权值基于
训练数据被归纳的精化。
4．TANGENTPROP使用的先验知识被表示为目标函数所希望的导数。在某些领域里，如图像
处理，这是表示先验知识的一个很自然的方法。TANGENTPROP通过改变指标函数使用这一知
识，此函数在搜索假设空间的梯度下降中被最小化。
5．FOCL使用领域理论来扩展每步搜索中考虑的候选集。它使用表示为一阶Horn子句的近似
领域理论来学习一组逼近目标函数的Horn子句。FOCL应用了序列覆盖算法，通过一般到特
殊搜索过程来学习每个Horn子句。领域理论被用于扩大此搜索中每步考虑的下一个更特殊
的候选假设集。然后候选假设基于它在训练数据上的性能被评估。以这种方法，FOCL结合
了FOIL的贪婪的、一般到特殊的搜索策略以及分析方法中的规则链分析推理。
6．如何最好的融合先验知识到新观察事物中的问题，仍是机器学习中主要的待解决问题之
一。
四、    应用实例
1 数据库知识发现研究的兴起
　　近年来已有越来越多的研究者加入到数据库知识发现KDD(Knowledge Discovery in 
Databases)研究的行列。KDD也称数据挖掘(data mining), 它的研究引起了人们的极大兴
趣。自1989年始已经举行了四届有关 KDD专题的国际讨论会,并且取得了一些相当有意义的
成果。
　　随着大量的大规模的数据库迅速不断地增长,人们对数据库的应用已不满足于仅对数据
库进行查询和检索。仅用查询检索不能帮助用户从数据中提取带有结论性的有用信息。这
样数据库中蕴藏的丰富知识,就得不到充分的发掘和利用。从而造成了信息的浪费,由此也
会产生大量的数据垃圾。 
　　从人工智能应用来看,专家系统的研究虽然取得了一定的进展。但是,知识获取仍然是
专家系统研究中的瓶颈。知识工程师从领域专家处获取知识是非常复杂的个人到个人之间
的交互过程，具有很强的个性,没有统一的办法。因此,有必要考虑从数据库中自动挖掘新
的知识。
　　这些都需要新的数据处理技术，KDD便应运而生。KDD的研究内容是，能自动地去处理
数据库中大量的原始数据,从中挖掘搜索出具有必然性的、富有意义的模式(pattern)。KDD
的一个主要问题是数据库中潜在的可能关系模式的数量太大了，因此使得要想搜索到有用
模式，必须借用人工智能技术，特别是来自机器学习领域的方法。
　　科技信息是巨大的社会财富，科学数据库是将科技信息转化为生产力的重要手段。由
于各种科技数据和文献的急剧增长，利用传统的工具和方法已不能有效地处理和传播，于
是不得不求助于计算机和先进的通信技术，从而大大推进了科学数据库及信息技术的发展
和应用。随着科学数据库的发展，数据库知识发现必然会发挥极其重要的作用，从各种学
数据库获取有用的知识，发现各门学科数据所反映的规律性。
2 数据库知识发现的研究内容和方法
　　KDD中要分析的数据的范围是非常广泛的,从自然科学、社会科学、商业数据，到科学
处理产生的数据或卫星观测得到的数据。它们的数据表示也各种各样，有关系型，也有层
次型。由于关系数据库应用广,具有规整统一的组织结构,通用的查询语言,特别是关系之间
及属性之间具有平等性优点。因此，目前KDD的主要对象仍是关系数据库。 
KDD可发现的知识也有各种表示形式,如法则(RULES)、规则(REGULARITY)、科学定律、方程
或概念网等等。
　　KDD的发现过程主要有三个步骤：用户定义要发现的问题；系统根据问题进行数据搜索
、模式抽取；评价所发现的知识的质量的好坏。三者之中，核心技术是第二步，即搜索及
模式抽取方法。下面介绍几种典型的模式抽取方法。 
2.1 依赖关系分析
　　数据依赖关系代表一类重要的可发现的知识。一个依赖关系存在于两个元素之间。如
果一个元素A的值可以推出另一个元素B的值(A→B)，则称B依赖于A。这个元素可以是字段,
也可以是字段间的关系。 
　　在发现系统中,依赖关系分析的结果有时可以直接提供给终端用户。然而,通常强的依
赖关系反映的是固有的领域结构而不是什么新的或有兴趣事物。自动地查找依赖关系可能
是一种有用的方法,这类知识可被其它模式抽取算法使用，比如可用于解释造成某种变化的
原因。 
2.2 分类 
　　通过把记录分组为有意义的类，可为用户直接提供其他所感兴趣的某种知识,或者为其
它模式抽取算法提供有用的信息。传统的模式识别、数据分类以及较近发展起来的概念聚
类领域都研究了大量的聚类算法。尽管现成的算法有用，但同人类识别聚类的能力还有一
定的区别,特别是在处理低维数据和具有可视化处理情形时。这时采用交互式的算法，以结
合高性能计算机的计算能力、人类特有的知识以及可视化技术。 
2.3 概念描述 
　　用户常常还需要抽象的有意义的描述。经过归纳的抽象描述能概括大量的关于类的信
息。有两种典型的描述:特性描述和判别描述。特性用于描述类的所有记录它们的共同之处
，而判别则描述了两个或更多个类之间有何差异。
2.4 偏差检测 
　　通过发现异常，可以引起人们对特殊情况的加倍注意。异常包括如下几种可能引起人
们兴趣的模式:不满足常规类的异常例子;出现在模式边缘的特异点;与父类或兄弟类有显著
不同的类;在不同时刻发生了显著变化的某个元素或集合;观察值与模型推算出的期望值之
间有显著的差异的事例。偏差分析的一个重要特征就是它可以有效地过滤大量的不感兴趣
的模式。
3 数据库知识发现的难点 
　　KDD的许多技术源于机器学习方法，但由于现实世界数据库存在一些固有的特点,因此
给KDD带来一些难点。正是这些关键之处，才形成了KDD领域自己独特的研究方向。下面略
加描述。 
3.1 动态变化的数据 
　　数据的动态变化是大多数数据库的一个主要特点。一个联机系统应能够保证数据的变
化不会导致错误的发现。 
3.2 噪声 
　　由于人为因素的影响，如数据的手工录入以及主观选取数据等，从而使得数据具有噪
声。带噪声的数据会影响抽取的模式的准确性。 
3.3 数据不完整 
　　数据库中某些个别的记录其属性域可能存在空值现象，另外对某一发现来说还可能完
全不存在其所必需的记录域。这种数据的不完整性将给发现、评估和解释一些重要的模式
带来困难。
3.4 冗余信息 
　　数据库中同一信息有时存储在多个地方。函数依赖就是一个通常的冗余形式。冗余信
息可能造成错误的知识发现,至少有些发现是用户完全不感兴趣的。为避免这种情况发生,
系统需要知道数据库中有哪些固有的依赖关系。
3.5 数据稀疏 
　　相应于可能的巨大的发现空间,数据库中所记录的实际数据的密度是非常稀疏的。这对
传统的经验定律发现方法是个挑战。
3.6 超大数据量 
　　数据库中数据的迅速增长是KDD得以发展的原因之一。这也正是对KDD研究的挑战。穷
举法、经验分析方法对数兆字节,数吉咖字节甚至数太拉字节的数据显得无能为力。此时KD
D系统必须采用一定的数据汇集方法,根据用户定义的发现任务,选择有关的域空间,采取随
机抽样的方法,对样本进行分析。
　　以上是现实世界数据库中存在的一些不利因素。在KDD发展的道路上,还有许多困难要
加以克服，有许多问题有待研究，如不适当的统计意识,过多的冗余模式,现有系统的集成,
多策略系统等等。
4 典型系统简介
4.1 SKICAT
　　U.Fayyad等(Jet Propulsion Laboratory)开发的 SKICAT ( sky image 
cataloguing and analysis tool)是一个用于分析大规模天空观测数据库的自动系统。对
数太字节的图像数据库用人工分类是不可能的。 SKICAT采用了许多新型机器学习方法，能
识别比以往用人工方法所识别的天体对象要暗一个数量级,并且取得了大约94%的精度。
4.2 49er
　　49er(Forth-Niner)系统是由美国J.M.Zytkow和 R.Zembowciz开发的一个通用KDD系统
。该系统可处理多个数据子集上的大规模的检索,通过产生列联表，精化初始规则,进而生
成强通用规则和有用的概念。49er结合了几种查询方法，每一种适用于一类规则的一个不
同方面。
4.3 EXPLORA
　　EXPLORA是由Hoschka和 Klosgen 开发的一个用于概念性的分析数据和搜索感兴趣关系
的集成化系统。该系统的运行是通过模板来寻找"事实",完成图的搜索。一个事实是一个模
式模板的具体的数据实例。利用交互式浏览,终端用户可以得到有序的事实集，并可产生面
向用户的最终报告。用户也可以通过介入发现过程去创建新的模板,修改验证方法。
4.4 KDW (Knowledge Discovery Workbench)
　　KDW是交互式的大型数据库的分析工具。该系统由美国 G. Piatetsky.Shapiro等人开
发,已开发有多种版本，所有版本都提供了一整套图形用户界面工具。该系统可用于存取数
据库表和创建新字段，数据汇集定义，图形显示数据和结果，选用发现算法及处理领域知
识。KDW系统包括的模式抽取算法有:识别简单线性类别的聚类;用决策树方法获取分类规则
; 能识别各类间有显著差异的偏差检测;用于发现和显示随机依赖关系的依赖关系分析。

5 动态与展望
　　以上仅从KDD的研究内容、方法和关键问题及典型系统等方面,对KDD作了一个简单综述
。由于篇幅所限,还有许多问题未能涉及,如:可听或可视化技术的应用。
KDD的研究正方兴未艾具有非常广阔的前景。利用粗糙集(rough set)作为KDD的工具,面向
多数据库的KDD,文本数据库中的知识发现,贝叶斯网络模型的使用,面向多策略和合作的发
现系统，面向对象的KDD,结合多媒体技术的应用等等都是新的研究方向。
目前,KDD研究的重点,正从理论转向应用，可说凡是用到数据库的地方,就有KDD的课题等待
人们去探讨。我们准备在河流水情预报的KDD应用方面做一些探索,为促进KDD在我国的应用
做一点尝试。KDD与科学数据库的结合对科技的发展必定会起到很大的促进作用，具有广泛
的应用前景。
五、    存在问题
为了精确起见，需要定义对应数据和对应两于理论的假设错误率度量，然后用这些错误率
来表示问题。可以定义errorD(h)为D中被h误分类的样例所占比例。还可定义h关于领域理
论B的错误率errorB(h)为h与B在分类一个随时抽取实例时不一致的概率。接下来就可以场
使用这些错误率的形式刻画所希望的输出假设。例如，我们可以要求假设使上述错误率的
某种综合度量最小化，如：
argminkDerrorD(h) + kBerrorB(h)
但是这时还不知道kD和kB的值来指定拟合数据和拟合理论两者的相对重要程度。如果有非
常差的理论，却有大量可靠数据，最好使errorD(h)的权值更大。相反，如果有很好的理论
，而数据样本很小且存在大量噪声，把errorB(h)的权值增大会得到最好的结果。
确定先验知识和数据权值的一种解决方案时使用贝叶斯的观点。按照贝叶斯的观点，所选
择的假设应为后验概率中最大的一个，并且贝叶斯公式提供了为此先验知识和观察到   数
据的贡献加权的良好方法。遗憾的是，贝叶斯公式隐含假定拥有P(h)、P(D)、P(D|h)概率
分布的完美的知识。因此贝叶斯方法并不能真正的解决此问题。
六、    结论
    以作者的观点，似乎可以采用软件工程领域正在实践的RUP方法，利用迭代，把学习的
过程拟合成一种增量过程。这有点类似反向传播算法，但有有所不同。RUP方法适合处理在
项目需求不明确，而且随着项目的进程，需求不断变化的软件过程，刚好适合处理领域理
论和训练数据都不足的情况下的学习过程。对于这方面的问题，作者正在做专门研究，时
间关系，不可能在5月20日之前取得结论，另文备后详述。

参考文献：
[1] Mitchell，T.M. Machine Learning. -Beijing.2003
[2] Yu Jiangsheng(2002).Bayesian Learning. Institute of Computational 
Linguistics Peking University
[3] Yu Jiangsheng(2002).Evaluating Hypotheses. Institute of Computational 
Linguistics Peking University
[4] D.Michie, D.J.Spiegelhalter, C.C.Taylor(1999). Machine Learning, Neural 
and Statistical Classification.
[5] Yu Jiangsheng(2002).Machine Learning(1). Institute of Computational 
Linguistics Peking University
[6] (美)米歇尔著；曾华军等译.机器学习.-北京：机械工业出版社，2003.1
[7] 杨飞. 从OLTP到OLAM与知识管理到知识发现. 重庆青年管理干部学院计算机系
[8] 车东. 基于Google的学习过程，http://www.chedong.com/tech/study.html
[9] 王军. 数据挖掘技术. 中国科学院计算技术研究所
[10]    史忠植，张庆杰，张治洪，王军. 知识发现与科学数据库. 中国科学院计算技术
研究所
[11]    方明，李天太，杨军全，黄炜. 自适应软件应用平台的模型设计. 西安交通大学
管理学院
[12]    罗晓沛. 数据挖掘在科学数据库中的应用探索. 中国科学技术大学研究生院

COMBINING INDUCTIVE AND ANALYTICAL LEARNING
samuel

(Harbin engineering university, Harbin, 150001)

Abstract:  Purely inductive learning methods formulate general hypotheses by 
finding empirical regularities over the training examples. Purely analytical 
methods use prior knowledge to derive general hypotheses deductively. This 
chapter considers methods that combine inductive and analytical mechanisms to 
obtain the benefits of both approaches: better generalization accuracy when 
prior knowledge is available and reliance on observed training data to 
overcome shortcomings in prior knowledge. The resulting combined methods 
outperform both purely inductive and purely analytical learning methods. This 
chapter considers inductive-analytical learning methods based on both 
symbolic and artificial neural network representations.

Key words:  Artificial Intelligence  Machine Learning  Inductive Learning   
Analytical Learning

 
--
三年硕士五年博，身变皮骨腰变驮。昨日豪情遭磨难，今朝两鬓见斑驳。
囊中通货常恨少，腹内草莽日渐多。墙上芦苇浅根底，山间竹笋空外壳。
有心飘洋求深造，无奈拦路有G 托。终日昏昏书中死，彻夜迷迷网上活。
人依电脑哥俩个，情寄足球心一颗。偶有红袖添香事，南柯梦醒愁更多。
不毛之地空求雨，梧桐树矮愧凤落。寄言诸位同窗友，莫效小子这般活。
轻浮小舟难下海，空虚岁月易蹉跎。此中言语皆肺腑，敬请大家细琢磨。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.43.254]