（应用数学专业论文）概念学习中finds算法和后选删除算法的比较研究.pdf

摘要归纳学习中的中心问题是一类称之为概念学习的算法。概念学习是指从特殊的训练样例中归纳出覆盖正例排斥反例的一般规律。概念学习可以看作是一个搜索过程，它在预定义的假设空间中按着某种搜索策略进行搜索，使学到的概念与训练样例有最佳的拟合度。本文首先介绍机器学习和概念学习的一些基础知识，然后对于概念学习中的非常有代表意义的两种算法即f i n d s 算法和候选删除法进行详细的比较研究。对于这两种算法来说，都是利用一般到特殊序的偏序结构来完成整个搜索过程。这种偏序结构可以推广到任何概念学习的问题中，从而对整个概念学习的算法有着重要的指导意义。文章的比较研究指出了两种算法各自的优点和不足，它为实际问题中如何选取这两种算法提供了一定的指导。关键词机器学习；概念学习；变型空间；f i n d s 算法；候选删除法a b s t r a c tt h ec e n t r a li d e ao fi n d u c t i v el e a r n i n gi sa l g o r i t h m so fc o n c e p tl e a r n i n g c o n c e p tl e a n i n gi st oi n d u c et h eg e n e r a lr u l e sf r o ms p e c i f i ct r a i n i n ge x a m p l e sa n dt h er u l e sa r ee x p e c t e dt ob o t hc o v e rt h ep o s i t i v ee x a m p l e sa n de x c l u d et h en e g m i v ee x a m p l e s c o n c e p tl e a r n i n gc a nb ef o r m u l a t e da sap r o b l e mo fs e a r c h i n gt h r o u g hap r e d e f i n e ds p a c eo fp o t e n t i a lh y p o t h e s e sf o rt h eh y p o t h e s i st h a tb e s tf i t st h et r a i n i n ge x a m p l e s f i r s to fa l l ，t h i sp a p e rb r i e f l yp r e s e n t ss o m eb a s i ck n o w l e d g ei nm a c h i n el e a r n i n ga n dc o n c e p tl e a r n i n g ，a n dt h e nm a k e sac o m p a r a t i v er e s e a r c ho nt h ef i n d sa n dc a n d i d a t ee l i m i n a t i o na l g o r i t h m s ，b o t ho fw h i c ha r et h em o s tr e p r e s e n t a t i v ea l g o r i t h m sf o rc o n c e p tl e a r n i n g t h et w oa l g o r i t h m sf o rc o n c e p tl e a r n i n ge f f i c i e n t l yc o m p l e t et h ew h o l es e a r c ht h r o u g ht h eh y p o t h e s i ss p a c eb a s e do nav e r yu s e f u ls t r u c t u r e ：t h eg e n e r a l - t o - s p e c i f i cp a r t i a lo r d e r t h i sp a r t i a lo r d e rs t r u c t u r ec a l lb ee x t e n d e dt oa n yc o n c e p tl e a r n i n gp r o b l e m ，a n dt h e r e f o r e ，i tp l a y sa ni n s t r u c t i v er o l ei na l la l g o r i t h m sf o rc o n c e p tl e a r n i n g t h ec o m p a r a t i v es t u d yi nt h i sp a p e rs h o w st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h el w oa l g o r i t h m s i ta i m st op r o v i d es o m eu s e f u lg u i d e l i n e sf o rs e l e c t i n ga 1 1a p p r o p r i a t eo n ef r o mt h et w oa l g o r i t h m sw h e nt h e ya r ea p p l i e dt or e a lp r o b l e m s k e yw o r d s ：m a c h i n ei e a r n i n g ；c o n c e p tl e a r n i n g ；v e m i o ns p a c e ；f i n s - sm e t h o d ；c a n d i d a t e e l i m i n a t i o nm e t h o di i河北大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了致谢。作者签名：叠丝!日期：丛年生月且一日学位论文使用授权声明本人完全了解河北：赶学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被鸯阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。本学位论文属于l 、保密口，在年月曰解密后适用本授权声明。2 、不保密吖。( 请在以上楣应方格内打“4 ”)作者签名导师签名隆丝：逆些日期：垄! 兰年丛一月王厶一目曰期：五罐年l 月4 日1 引言1 1 课题背景和研究现状1 引言机器学习研究作为一门科学的前沿和交叉学科，在过去的时间内已经取得了很天的发展；在国际国内都兴起了热潮，这使得机器学习在我国也得以迅速传播和发展。机器学习是继专家系统之后人工智能应用的又一重要研究领域，也是人工智能和神经计算的核心研究课题之一。现在的计算机系统和人工智能系统虽然有一定的学习能力，但是却不能满足科技和生产提出的新要求，为此机器学习的专家和学者们都在努力探索机器学习的问题，而对于机器学习来说，从特殊的训练样例中归纳出一般函数是机器学习的中心问题。一个好的算法无异于一条捷径，因此，对于算法的研究越来越引起学科专家学者的注意，在机器学习的算法中，归纳学习是研究最广的一种符号学习方法，它表示从例子设想出假设的过程。在进行归纳学习时，学习者从所提供的事实或观察到的假设进行归纳推理，获得某个概念。归纳推理是个从部分到全体，从特殊到一般的推理过程，从应用的角度看，归纳学习可分为概念学习、概念聚集和启发学习三种，而对于概念学习来说，可以将其看作是搜索预定义潜在假设空间的过程；而对于假设的一般到特殊偏序结构可以定义在任何概念学习问题中，它提供了一种有用的结构以便于假设空间的搜索；在概念学习中比较宥代表意义的算法是：f i n d - s 算法和候选删除算法。概念学习以及使用一般到特殊序的相关研究由来已久。b r u n e re ta 1 ( 1 9 5 7 ) 早就研究了人类的概念学习，而h u n t h o v l a n d ( 1 9 6 3 ) 将其自动化。w i n s t o n ( 1 9 7 0 ) 的著名的博士论文中将概念学习看作是包含一般化和特殊化操作的搜索过程。变型空间和候选删除法由m i t c h e l l ( 1 9 7 7 ，1 9 8 2 ) 提出，这一算法已经应用于质谱分析中的规则推理以及应用于学习搜索控制规则。候选删除法的一个最大的实际限制是它要求训练数据是无噪声的。m i r c h e l l ( 1 9 7 9 ) 描述了该算法的一种扩展，以处理可预见的有限数量的误分类样例，h i r s h ( 1 9 9 0 ，1 9 9 4 ) 提如种良好的扩展以处理具有实数值属性的训练样例中的有限噪声。h i r s h ( 1 9 9 0 ) 描述了种递增变型空间合并算法，它将候选河北大学理学硕士学位论论文取删除法扩展到能处理由不同类型的值约束表示的训练信息。来自每个约束的信息由变型空间来表示，然后用交叠变型空间的办法合并这些约束。1 2 研究目的和研究意义概念学习就是给定一样例集合以及每个样倒是否属于菜概念的标注，怎么样自动推断出这个概念的一般定义。我们也可以把它称为从样例中逼近布尔值函数，或者可阻说概念学习是搜索预定义潜在假设空间的过程。对于f i n d - s 算法和候选删除算法，虽然它们有自身的优点，但也存在着各自的不足，由它们对概念学习的特殊性而言，对于假设的般到特殊偏序结构可以定义在任何概念学习问题中它提供了一种有用的结构以便于假设空间的搜索，所以我们可阻认识到这两种算法的现实意义和作用。1 3 本文所做的工作( t ) 介绍机器学习的基础知识( 2 ) 术语定义( 3 ) f i n d s 算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，以寻找与样例一致的最特殊假设。( 4 ) 候选删除算法使用一般到特殊序，通过渐进地计算极大特殊假设集合s 和极大般假设集合g 计算变型空间f 即所有与训i 练数据一致的假设集) 。( 5 ) f i n d - s 算法和候选删除算法的比较( 5 ) f 1 n d - - s 算法和候选删除算法的比较( 6 ) 结论2 机器学习的基础知识2 机器学习的基础知识2 1机器学习的定义及研究意义与发展历史2 1 1 机器学习的定义自从计算机问世以来，人们就想知道它们能不能自我学习。如果我们理解了它们学习的内在机制，即怎样使它们根据经验来自动提高，那么影响将是空前的。想象一下，在未来，计算机能从医疗记录中学习，获取治疗新疾病最有效的方法：住宅管理系统分析住户的用电模式，以降低能源消耗；个人软件助理跟踪用户妁兴趣，并为其选择最感兴趣的在线早间新闻。对计算机学习的成功理解将开辟出许多全新的应用领域，并使其计算能力和可以定制性上升到新的层次。同时，透彻理解机器学习的信息处理算法，也会有助于更好地理解人类的学习能力及缺陷。目前，我们还不知道怎样使计算机具备和人类一样强大的学习能力。然而，一些针对特定学习任务的算法已经产生。关于学习的理论认识已丌始逐步形成。人们玎发出很多实践性的计算机程序来实现不同类型的学习，一些商业化的应用也已经出现。例如，对于语音识别这样的课题，迄今为止，基予机器学习的算法明显胜过其他的方法。在数据挖掘领域，机器学习算法理所当然地被用来从包含设备维护记录、借贷申请、金融交易、医疗记录等此类信息的大型数据库中发现有价值的信息。随着对计算机认识的同益成熟，机器学习必将在计算机科学和技术中扮演越来越重要的角色。我们可以通过一些专项成果看到机器学习这门技术的现状：计算机已经能够成功地识别人类的讲话、预测肺炎患者的康复率、检测信用卡的欺诈、在高速公路上自动驾驶汽车、以接近人类世界冠军的水平对弈西洋双陆棋这样的游戏等。已有很多理论成果能够对训练样例数量、假设空间大小和已知假设中的预期错误这三者闻的基本关系进行刻画。人类正开始获取人类和动物学习的原始模型，用以理解它们和计算机的学习算法间的关系。在过去的十年中，无论是应用、算法、理论，还是尘物系统的研究，都取得了令人瞩目的进步。河北大学理学硕十学位论论文e 日目_ iiii e e s ! ! | 目“机器学习- 般被定义为一个系统自我改进的过程，但仅仅从这个定义来理解和实现机器学习是困难的。从最初的基于神经元模型以及函数逼近论的方法研究，到以符号演算为基础的规则学习和决策树学习的产生，和之后的认知心理学中归纳、解释、娄比等概念的引入，至最新的计算学习理论和统计学习的兴起当然还包括基于马尔可夫过程的增强学习，机器学习一直都在相关学科的实践应用中起着主导作用。研究人员们借鉴了各个学科的思想来发展机器学习，但关于机器学习问题的实质究竟是什么尚无定论。不同的机器学习方法也各有优缺点，只在其适用的领域内才有良好的效果。因此，以枚举的方法描述机器学习中的各个理论和算法可能是最合适的途径。2 1 2 机器学习的主要策略与基本结构学习是人类具有的一种重要智能行为。按照人工智能大师h s i m o n 的观点，学习就是系统在不断重复的工作中对本身能力的增强或改进，使得系统在下一次执行同样或相类似的任务时，会比原来做得更好或效率更高。机器学习研究的是如何使机器通过识别和利用现有知识来获取新知识和新技能。一个人不管他有多深的学问、多大的本领，如果不善于学习，他的能力总是停瞬在个固定的水平上，不会创造出新奇的东西。但一个人若具有很强的学习能力，则不可等闲视之了。也许他现在的能力不是很强，但是“士别三f 1 ，当刮日相看”。机器具备了学习能力，其情形完全跟人一样。l9 5 9 年美国的samue 】设计了一个下棋程序，它具有学习能力，可以在不断的对弈中改善自己的棋艺。四年盾这个程序战胜了设计者本人。又过了三年，它战胜了美国一个保持八年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力，提出了许多令人深思的社会问题与哲学问题。机器学习系统的基本结构如下：圃一臣至圃一匝圈一口夏圃图1 学习系统的基本结构环境；系统中的环境包括工作对象和外界条件。比如在医疗系统中，环境就是病人当2 机器学习的萋础知识e | 目_ ii 自e t e 蜷前的症状、物理化学检验的报告和病历等信息；在模式识别中，环境就是待识别的图形或景物；在控制系统中，环境就是受控的设备或生产流程。学习环节：学习环节是系统的学习机构，是学习系统的核心，它通过对环境的搜索取得外部信息，然后经分析、综合、类比、推理等思维过程获得知识，并将这些知识送入知识库中，供执行环节使用。知议库：学习系统的另一个重要总是就是知识库的形成设计以及其内容。知识库的形式就是知识表示的形式，选择知识表示方法簧考虑下面几个准则：可表达性、推理难度、可修改性、可扩充性。执行环节：执行环节实际上由执行环节和评价环节两部分组成。环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增强系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体应用中环境、知识库和执行部分决定了具体的工作内容，学习部分所需要解决的问题完全由上述三部分确定。机器学习这门学科研究的是能通过经验自动改进的计算机算法，其应用从数据挖掘程序到信息过滤系统，再到自动机工具，已经非常丰富。机器学习从很多学科吸收了成果和概念，包括人工智能、概率论与数理统计、哲学、信息论、生物学、认知科学和控制论等，并以此来理解问题的背景、算法和算法中的隐含假定。机器学习一词中的机器主要指的是电脑( 电予计算机) ，意思是让电脑自己学习或让电脑像人一样具有学习能力。随羞数据库技术的迅速发展以及因特网的广泛应用，个人或单位积累的数据资料( 各类电子文档) 会有一个爆炸性的增长。激增的数据背后隐藏着许多重要的信息知识。人们希望能够对这些大量的数据通过机器学习的手段进行分析、提炼，以挖掘发现有用的信息知识。目前数据库系统可以高效地实现数据的录入、查询、统计等功能，但很难发现数据间存在的关联，很难根据现有的数据预测来来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，出现了“数据爆炸但知识贫乏”的现象。据了解，人工智能自1 9 5 6 年诞生之后取得了重大进展，先后经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是机器学习。机器学习是人工智能的最重要的分支之一，被公认是人工智能发展的瓶颈。机器学习的研究在人工智能的发现( 尤其是专家系统的发展) 中起着举足轻重的作用。对机器学习的研究促进了人工智能在理弼北大学理学酿十学位论论文论方法和实际应用上的迅速发展。学习是人类获取智慧的根本途径。学习和解决问题是人类最重要的两个智能行为。机器学习是让计算机模拟和实现人类的学习的过程，目的是获取知识。机器学习也是让计算机获取智能的最主要的手段。机器学习具有快速、可复制、自主性差、机械、学习方法单一等特点。由于机器不存在人类所具有的生理因素的限制，因此，机器可以“不知疲倦”地学习，而且，在对一些数理化的知识的学习上，机器也比人的速度要快得多。而且，由于计算机程序易于复制，因此，计算机的学习是不会终止的，其所具有的知识也可以一直保留下来。但是，计算机的学习方法单一，只能根据有限的学习方法进行机械学习，本身不能创造方法，尤其是不具有人类学习所特有的“灵感思维”，这也是机器学习在目前来说尚不可克服的缺陷。机器学习是用计算机模拟人类学习的一门科学，强前比较成熟的算法有归纳学习算法、决策树法、神经网络、遗传算法等。归纳学习算法有别于传统的归纳学习，是指在不确定环境下示例学习的研究，是由传统的归纳学习、软计算技术与模糊集合理论交叉而成。机器学习有着众多的分支，归纳学习是其最主要的分支，它主要研究如何从大量数据中抽取规则( 知识) 。归纳学习可分为有导师学习和无导师学习。用数据库管理系统柬存储数据，用机嚣学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结含促成了机器学习的一个新分支：数据库中的知识发现的产生。( k d d k n o w l e d g ed i s c o v e r yi nd a t a b a s e )为达到改善科学进程的目的，机器学习方法也面临着多种困难。其一，大多数机器学习方法主要是处理矢量数据，这就限制了它在更为丰富豹非矢量关系的数据( 如图表、文本数据) 中的应用。其二，在生物信息和网络中的数据处理方法还相当新而且不成熟。其三，大多数机器学习都是先假定一个固定的模型结构，而实际上我们常希望模型结构是可变的，在研究初期尤其如此。因此从系统的观点来看，还需要做很多工作。现在，机器学习研究的个令人振奋的方向是许多经典线性方法( 如p c a 法、k 近邻分类法、f i s h e r 分类法等) 的非线性m e r c e r 核函数形式以及特殊领域的核函数。这些核函数可以对高维特征空i 旬中的高精度模型进行学习，菇且能够克服传统学习方法中的“维数灾难”问题。因此，机器学习方法的突破包括两个方面，一是设计新的算法，二是设计强大的特殊领域中的核函数。2 机器学习的基础知识在科学研究中，每个科学领域都有自己的研究形式，但都有一个一般过程：观察、提出假设、实验检验、反复建立易理解易检测的模型或理论。而每一个阶段的科学抽象，都在机器学习、模式识别和统计学推论中有相关的发展，进而产生未知的但具有广阔的潜在应用前景的半自动支持工具。为达到改善科学进程的目的，机器学习方法也面临着多种困难。其一，大多数机器学习方法主要是处理矢量数据，这就限制了它在更为丰富的非矢量关系的数据( 如图表、文本数据) 中的应用。其二，在生物信息和网络中的数据处理方法还相当新而且不成熟。其三，大多数机器学习都是先假定一个固定的模型结构，而实际上我们常希望模型结构是可变的，在研究初期尤其如此。因此从系统的观点来看，还需要做很多工作。现在，机器学习研究的一个令人振奋的方向是许多经典线性方法( 如p c a 法、k 近邻分类法、f i s h e r 分类法等) 的非线性m e r c e r 核函数形式以及特殊领域的核函数。这些核函数可以对高维特征空间中的高精度模型进行学习，并且能够克服传统学习方法中的“维数灾难”问题。因此，机器学习方法的突破包括两个方面，一是设计新的算法，二是设计强大的特殊领域中的核函数。学习是人类获取智慧的根本途径。学习和解决问题是人类最重要的两个智能行为。机器学习是让计算机模拟和实现人类的学习的过程，目的是获取知识。机器学习也是让计算机获取智能的最主要的手段。机器学习具有快速、可复制、自主性差、机械、学习方法单一等特点。由于机器不存在人类所具有的生理因素的限制，因此，机器可以“不知疲倦”地学习，而且，在对一些数理化的知识的学习上，机器也比人的速度要快得多。而且，由于计算机程序易于复制，因此，计算机的学习是不会终止的，其所具有的知识也可以一直保留下来。但是，计算机的学习方法单一，只能根据有限的学习方法进行机械学习，本身不能创造方法，尤其是不具有人类学习所特有的“灵感思维”，这也是机器学习在目前来说尚不可克服的缺陷。机器学习是用计算机模拟人类学习的一门科学，目前比较成熟的算法有归纳学习算法、神经网络、遗传算法等。用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了机器学习的一个新分支：数据库中的知识发现和产生。河北大学理学硕士学位论论文_ _ _ 一ii _ _ _ _ _ _ _ 日_ _ _ _2 1 3 机器学习研究意义与发展历史机器学习是人工智能研究较为年轻的分支，它的发展过程大体上可分为四个时期。第一个阶段是在5 0 年代中叶到6 0 年代中叶，属于热烈时期，在这个时期，所研究的是“没有知识的举习”，即“无知”学习；其研究蟊标是各类组织系统和自适应系统：其主要研究方法是为断个性系统的控制参数以改进系统的执行能力，不涉及具体任务有关的知识。第二阶段在6 0 年代中叶到7 0 年代中叶，被称为机器学习的冷静时期。这个阶段的研究目标是模拟人类的概念学习过程，并采用逻辑结构可圈结构作为机器内部描述。机器能够采用符号来描述概念( 符号概念获取) ，并提出关于学习概念的各种假设。第三阶段是从7 0 年代中叶到8 0 年代中叶，称为复兴时期。在这个时期，人们从学习单个概念扩展到多个概念，探索不同的学习策略和各种学习方法。机器学习的过程般都建立在大规模的知识库上，实现知识强化学习。机器学习的最新阶段开始于1 9 8 6 年。一方面，由于神经网络研究的重新兴起，对连接机制学习方法的研究方兴未义，机器学习的研究已在全世界范围内出现新的高潮，对机器学习的基本理论和综合系统的研究得到加强和发展。另一方面，对实验研究和应用研究得到前所未有的重视。随着人工智能技术和计算机技术的快速发展，已为机器学习提供了新的更强有力的研究手段和环境。2 1 4 机器学习瓤阶段的重要表现机器学习进入新阶段的重要表现在下列诸方面：机器学习己成为新的边缘学科并在高校形成一门课程，它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。结合各种学习方法，取长补短的多种形式的集成学习系统研究正在兴起。特别是连接学习符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。机器学习与人工智能各种基础问题的统一性观点正在形成。例如学习与问题求解结合进行、知识表达便于学习的观点产生了通用智能系统s o a r 的组块学习。类比学习与问题求解结合的基于案例方法已经成为经验学习的重要方向。2 机器学习的基础知识各种学习方法的应用范围不断扩大，一部分已经形成商品。归纳学习的知识获取工具已经在诊断分类型专家系统中广泛使用。连接学习在声图文识别中占优势。分析学习已经用于设计综合专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研讨会外，还有计算机学习理论会议以及遗传算法会议。2 2 概念学习机器学习是人工智能的一个关键领域，是使机器获取智能最根本的途经。计算智能( 主要包括模糊逻辑、神经网络和遗传算法) 是机器学习的延伸，被称为现代人工智能。机器学习被公认为专家系统发展的瓶颈，它在整个人工智能领域占有举足轻重的地位许多机器学习问题涉及到从特殊训练样例中得到一般概念，每个概念可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或者是在这个较大集合中定义的布尔函数。，给定一样例集合以及每个样例是否属于某一概念的标注，怎样自动推断出该概念的一般定义，这一问题被称为概念学习，或者称从样例中逼近布尔函数。概念学习也可以看作是一个搜索过程，它在预定的假设空间中搜索假设，使其与训练样例有最佳的拟合度。多数情况下，可以利用假设空间中一种自然形成的结构即一般到特殊偏序结构。从特殊的训1 练样例中归纳出一般函数是机器学习的中心问题。利用覆盖所有正例排斥所有反例的思想来寻找规则，最后形成目标概念。 可北大学理学硕士学位论论文i i 曹3 术语定义、定理及训练样例概念学习问题：给定某一类别的若干正例和反例，从中获得该类别的一般定义。概念学习也可以看作是一个搜索问题的过程，它在预定义的空间中搜索假设，使其与训练样例有最佳的拟合度。多数情形下，为了高效的搜索，可以利用假设空间中一种自然形成的结构：一般到特殊偏序结构。偏序结构：设h 是集合h 中的一个关系，如果h 满足下列三个条件：自反的反对称的传递的，则称h 是集合h 的偏序关系，用符号“”表示。目标函数：是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。二值逻辑：对于一个命题，只取真、假二值，称为二值逻辑，通常用“1 ”表示“真”，用“0 ”表示“假”概念学习：能够用布尔表达式表示的函数称为布尔函数。模糊逻辑：通常将研究模糊命题的逻辑称为连续值逻辑，也称为模糊逻辑，它是二值逻辑的推广，是对经典的二值逻辑的模糊化。一个公式的真值，在二值逻辑中只能是取两上值( 0和1 ) ，而在模糊逻辑中可取【o 1 】区间中的任何值，其数值表示这个模糊命题真的程度。概念学习的训练样例：目标概念是：m a r y 进行水上运动的同子每个样例表示为属性的集合。e n j o y s p o r t 表示这一天m a r y 是否乐于进行水上运动。这个任务的目的：基于某天的各属性，预测出该天e n j o y s p o r t 的值。表1 训练样例3 术语定义、定理及训练样例1 ? 表示接受任意值2 明确指明值( 如w a r ms u n n y 等)3 o 表示不接受任何值由上所述：e n j o y s p o r t 这个概念学习的任务是使e n j o y s p o r t = y e s 的日子，并将其表示为属性约束的合取式。一般来说，任何概念学习任务能被描述为：实例的集合，实例集合上的目标函数，候选假设的集合以及训练样例的集合。袭2 学习任务b 知：蛮俊集x ：司能桷b 子每个& 子由 蕊的羁性描述s k y ( 可取懂为s u n n y 、c l o u d y 和r a i n y )a i 卜t e m p ( 可取值为w a r m 和c o l d )h u m i d i t y ( 可取值为n o r m a l 席q h i g h )w i n dt 可取值为s t r o n g 幕iw e a k )w a t e r ( 可取值必w a r m 拳1c 0 0 1 )f o r e c a s t ( - 7 嚣( e x js a m e 霸1c h a n g e )假设集h ：每个馁设描述为6 个强性s k y , a i r - t e m p 合取约柬i 3 以是任意馕“。一个特定埴或者是讴绝爨森值“0 ”曷标概念c ：e n j o y - s p o r tx 一 。| l3i l 缫t # 觏集d ：目标萤敬正确释反钠求解：h 中的一个假设h 馒对于x 中任意x h ( x ) = c x )概念定义在一个实例集合之上，这个集合表示为x ，待学习的概念或函数称为目标概念，记作c ，c 可以是定义在实例集x 上的任意布尔函数，即c ：一 o ，1 ，在本例中：e n j o y - s p o r t = y e s 时，c ( x ) = 1 ，e n j o y - s p o n = - n o 时，c ( x ) = o 。在学习目标概念时，必须提供一套训练样例，d 表示训练样例的集合，序偶= c c ( x ) ) 来描述训练样例，表示其包含了实例x 和目标概念值c ( x ) 。河北人学理学硕士学位论论文t _ _ s _ _ _ 目- - - - - - _ - _ _ - - _ - _ - _ i i ii _ _ 目_ - _ 目_ 目_ - 自_ _ e e _ _ _ _ _ _ _ _ 觑给定目标概念c 的训练样例集，学习器面临的问题就是假设或估计c 。h 用来表示所有可能假设的集合，这个集合才是为确定目标概念所考虑的范围。通常h由设计者所选择的假设表示而定。h 中每个的假设h 表示x 上定义的布尔函数，即h ：x 4 0 ，1 l 。机器学习的目标就是寻找一个假设h ，使对于x 中的所有x ，h ( x ) = c ( c )一致：一个假设h 与训练样例集合d 一致，当且仅当对d 中每一个样例 都有h ( x ) = c ( x ) 。c o n s i s t e n t ( h ，d ) # ( v d ) h ( x ) = c ( x )请大家注意，在这晕定义的一致和前面定义的满足是不一样的：个样例在h ( x ) = l 时称不满足假设h ，不论x 是目标概念的正例还是反例。在这里一致表示的含义剐是与目标概念有关，也就是说是否有h ( x ) = c ( x ) 。变型空间：关于假设空间h 和训练样例集d 的变型空间，标记为v s 。d ，是h 中与训练样例d一致的所有假设构成的子集。v s ms h e h ic o n s is t e n t ( h ，d ) i比更一般( m o r e g e n e r a i t h a n o r e q u a i t o )令hj 和h 女为在x 上定义的布尔函数。称hjm o r e _ g e n e r a l t h a n o r e q u a l t oh ( 记作h 。h ) ，当且仪当( h ，。h ) h 。h ，比更特殊( m o r e s p e c i f i c t h a n )令hj 和h l 为在x 上定义的布尔函数。称h ，m o r es p e c i f i c t h a nh ，当h m o r e g e n e r a l t h a nhj 。一般边界：关于假设空间h 和训练数据d 的一般边界( g e n e r a lb o u n d a r y ) g ，是在h 中与d 相致的极大一般( m a x i m a l l yg e n e r a l ) 成员的集合。g - = g e hc o n s i s t e n t ( g ，m ) 八( - 、3 9 h ) ( g # g ) c o n s i s t e n t ( g ，d ) 1 特殊边界：1 2 3 术语定义、定理及训练样例! i i i i i i e e | | 日日日| e 日日s e e e e 日日疃关于假设空间h 和训练数据d 的特殊边界( s p e c if i cb o u n d a r y ) s ，是在h 中与d 相致的极大特殊( m a x i m a l l ys p e c i f i c ) 成员的集合。s i s h | c o n s i s t e n t ( s ，d ) 八( 一3s h ) ( s 。s ) 八c o n s i s t e n t ( s ，d ) )变型空阀表示定理：令x 为一任意的实例集合，h 为x 上定义的布尔假设的集合。令c ：xo1 0 ，1j 为x上定义的任一目标概念，并令d 为任意一个训练样例的集合i 。对所有的x ，h ，c ，d 以及良好定义的s 和g ：v s h d = h hi ( j s e s ) ( j g g ) ( g g h ss )也就是说变型空间的确切组成是：g 中包含的假设，s 中包含的假设以及g 和s 之间的偏序结构所规定的假设。覆盖：当一个假设能正确地划分一个正例时，称该假设覆盖此正例。河j e 大学理学硕士学位论论文4 fln d - s 算法及候选删除算法的具体内容4 1f i n d - s 算法的具体内容当我们使用m o r e g e n e r a l t h a n 偏序来找到对训练样例相一致的假设时，我们从h 中最特殊的假设开始，当这个假设覆盖正例失败时，将其一般化。表3f i n d - s 算法 1 】将h 初始化为h 中最特殊的假设f 2 】对每个正例x ：对h 的每个属性约束a 。如果x 满足a 那么不傲任何处理否则将h 中a 替换为下一个更一般约束【3 】输出假设h下面我们来具体看一下f i n d - s 算法的过程：假定给予学习器的一系列训练样例为表1 所给内容。第一步：将h 初始化为h 中最特殊的假设：h 。第二步：当我们看表中的第一个训练样例时，见下图我们可以看到，它正好是一个j f 例，因为这时的h 太特殊，“表示不接受任何值，所以h 中的每一个约束都不被满足，由f i n d - s 算法我们知道，此时，每个属性值都被4 。f j n d s 算法及候选删除髯法的具体内窬! e - ii ii e i e e 目| 自自! ，!替换成能拟合该例的下一个更一般的约束，也就是说，此时的h 就应该是这一样例本身的属性值：h 这时的h 还是太特殊，因为它除了把第一个样例划分为正例外，把其它所有的样例都划分为反例。我们继续往下进行。第三步：当我们看表1 中的第二个训练样例时，见下图因为在第二例中，我们看到仍然是一个f 例，由f i n d s 算法我们应该进一步将h 一般化。我们用“? ”来代替h 中不能被满足的属性值，这时，h 将变为：h2 第四步：当我们看表1 中的第三个训练样例时，见下图这里我们看到的是一个反例，由f i n d s 算法我们知道，h 不变。为什么在f i n d s算法中遇到反例，我们就不需要对h 做任何修改? 一般情况下，只要我们假定假设空间h 确实包含真正的目标概念c ，而且训练样例不包含错误，那么我们就不需要对h 做任何修改，对当前假设h 来说，它是h 中与所观察到的正例相致的最特殊的假设，由于假定目标概念c 在h 中，而且它一定是与所有芷例相致的，那么c 一定比h 更股，而目标概念c 不会覆盖一个反例，所以h 也不会覆盖一个反例( 出m o r e g e n e r a l t h a n的定义可知) 。所以对于反例，我们不做任何更改。h3 第扛步：当我们看表1 中的第四个训练样例时，见下图河北大学理学硕士学位论论文曼置- _ _ _ - - i - 鼻_ _ l l _ _ - - 由_ - _ _ - _ _ _ - _ _ _ _ _ - l i _ 曩暑鼍嘲- - _ _ 墨暑掌鼍!我们看到仍然是一个斧例，由f i n d s 算法我们应该进一步将h 一般化。我们用“? ”来代替h 中不能被满足的属性值，这时，h 将变为：h 。这就是我们通过训练样例得到的最后的假设。f i n d s 算法让我们看到了一种用m o r e g e n e r a l t h a n 偏序方法来搜索假设空间的方法。它从最特殊的假设开始，沿着偏序链逐渐转移到一般的假设。4 2 候选删除算法的内容为了精确描述候选删除算法，我们在前面已经弓 入一些基本的定义。首先，我们要明确一致性( c o n s i s t e n t ) 的定义，知道了一致性的定义后，我们来看候选删除算法遵循的原则：原则上，只要假设空间是有限的，就可以使用候选删除算法。在候选删除算法中交型空间被表示成它的极大般成员( 在本文中标为g ) 和极大特殊成员( 在本文中标为s ) ，这些成员形成了一般和特殊边界的集合，这些边界( s 、g ) 在整个偏序结构中划分出变型空间( v s 。) 。表4 候选删除算法将g 集合初始纯为h 中极大一般假设将s 巢台初始纯为h 中极大特砾弦设对每个l i 练样俩d 进行以b 操佧：如果d 是一班谤j从g 中移击辑菊sd 不一致携骰设对s 中每个s d 不一致的假设s烈s 串移去s4 f i n d s 算法及候选删除算法的具体内容把s 的断有的极小一般纯式h 加入孰s 中其中h 满跫h s d 一致。蔼盈g 的某个或爨比h 更一般从s 孛移去瞬鸯这样的假设：它眈s 孛另一佼设更一般如果d 是一个反钠扶s 中穆去所有与d 不一致的佼设对g 中每个s d 不一致的假设g 以g 乒萨若g把g 拍辑有的极小特豫纯式h 抽入孰g 中其中h 满是h - f f d 一致雨量s 韵某个战员比h 矍特殊扶g 中移去新南这样的锻莰：它眈g 中另一假设更特殊下面，我们用表1 中的训练样例来看一下候选消除法的运行步骤：第一步：初始化边界：s 。是h 中最特殊的假设，g 。是h 中最一般的假设so ： g 。：( 如下图所示：s o - 匝互巫卫e 。：瓜万瓦而r 1 - ，- - - - - - - - - - - - - - - - - - - - - - _ jso 和go 垦最初的边界集台t 分别对麻最特殊羊n 最一般假设-图2 候选消除法步骤l第二步：当我们看表1 中的第一个训练样例时，见下图1 7 河北大学理学硕士学位论论文这是一个正例，候选消除法检查s 边晃，可以知道这个边界过于特殊了，它不能覆盖正例，我们来修改边界s ，参照第一个训练样例，我们可以知道s 。要被换成s ，而边界g 不用修改，因为g 。可以覆盖这个样例。所以有：s ，：( )g l = go ： )如下图所示so ： 上i go ，g i ：l )r 。1我们荐看第二个样例：样例1 使得s 边界变得更一般，但此例对g 边界没有影响图3 候选消除法步骤2 - 1 ( 样例1 )这也是一个正例，候选消除法检查s 边界，可以知道这个边界也特殊，它不能覆盖正例，我们来修改边界s ，参照第二个训练样例，我们可以知道s ，要被换成s ：，而边界g 不用修改，因为g 。可以覆盖这个样例。所以有：s2 ：( )g2 = g 1 = go ： )4 f i n d s 算法及候选删除算法的具体内容! e e e 自嘲ii 日薯e 自| 5 e s 目8 舞如下图s 】：，s2 ：so ： 上l )上t )go , 匝互至互样例2 也使得s 边界变褥更一般，但此例对g 边界也没有影响图4 候选消除法步骤2 2 ( 样例2 )在这两个正例中，通过修改s 的值，使变型空间的s 边界逐渐一般化。第三步：当我们看表1 中的第三个训练样例时，见下图这里我们看到的是一个反例，由候选消除法知道，g 边界过于一般了，g 会将这个反例判断为正例，所以我们要修改g 边界，使其特殊化。我们可以看到有6 个属性可以使g ，特殊化，比如h _ 是g ，的一个极小特殊化式，它可以把第三个样例划分为反例，但是它和前面遇到的正例不一致，由s ，： ) 我们知道，这个h 并不比特殊边界s2 更一般，所以这个h 我们就不必放在g ，的范围中了。实际上，变型空间的s 边界形成了以往f 例的摘要说明，它可以用来判断任意给定的假设是否与以往的样例一致。任何比s 更一般的假设能够覆盖所有以往的j 下例。g 边界说明了以往所有反例的信息。也就是说，任何比g 更特殊的假设能保证与所有反例相一致。河北人学理学硕士学位论论文所以有：s3 ： g3 ：( ( ? ，? ，? ，? ，? ，s a m e 如下图所示：跨趴。匝三三三三三三习g3 ：i 下一g2 ：( f h s = 样伊j3 是一个厦例t 它把边界g2 特殊化为g3 。此时，在g3 中有多个可迸的极人一般假设。图5 候选消除法步骤3 ( 样例3 )第四步：当我们看表1 中的第四个训练样例时，见下图这也是一个正例，候选消除法检查s 边界，可以知道这个边界也特殊，它不能覆盖正例，我们来修改边界s ，参照第四个训练样铡，我们可以知道s ，要被换成s 。，丽边界g 也要修改为g 。，g ，中的一个成员 将被删除，因为它不能覆箍新的正例。前面我们知道s 边界用来使边界一般化，也就是说是针对于j 下例来说的，而g 是用来使边界特殊化的，也就是针对于反例来说的，那为什么这罩要出于正倒的出现而修改g 边界昵? 因为我们知道，对于这个假设来说 ，它不能再被特殊化，因为它不能覆盖新的正例。它也不能被一般化，因为按照g 的定义，4 f i n d s 算法及候选删除算法的具体内容任何更一般的假设至少会覆盖一个反例。所以我们要把这一假设从g 中移去，也就相当于移去了变型空间偏序结构中的一个分支。所以有：s 。： )g 。： ， )如下图所示：s3s4 ：【 )土 jg 4 ： 。 )?i 由于样例4 是一个正例，它使边界s 更一般从s3 变为s4 。此时，g3 中的一个成员也必须删除，阁为它不比s4 更一般圈6 候选消除法步骤4 ( 样例4 )当我们对所有的训练样例进行完操作后，边界集合s ；和g 。划分出的变型空间v s 。包含了与样例一致的所有假设的集合。由此我们得到的变型空间由六个元素组成，即： s4 ) 、g4 ： ， ) 及 ) 、 ) 、 ) ，这一交型空间不依赖于训练样本的出现次序，因为变型空间v s 。包含了与训练样例集一致的所有假设，如暴我们提供更多的训练数据，s和g 边界会继续单调移动并相互靠近，划分出越来越小的变型空间。在下图中，就是我们经过概念学习后得到的变型空间，这个变型空间与前边的f i n d s河北丈学理学硕士学位论论文一ii ii e 墨算法所产生的空间相比，对于本文中所给的四个实例，经过训练后得到的结果是；h 。这其实只是h 中所有与训练样例一致的6 个假设之一，这6 个假设构成了与该数据集合和假设表示相对应的变型空间。见下图：s4f 图7 概念学习问题中最终的变型空间5 f i n d s 算法和候选删除两种算法的比较! 日| | e 自一i ii | e e | | | 自_5 fin d - s 算法和候选删除两种算法的比较5 1fln d - s 算法与候选消除法的特点5 1 1f l n d - s 算法的特点在f i n d - s 算法中，对以属性约束的合取式描述的假设