高级人工智能-机器学习.ppt

《高级人工智能-机器学习.ppt》由会员分享，可在线阅读，更多相关《高级人工智能-机器学习.ppt（186页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、高级人工智能高级人工智能第第6章章 机器学习机器学习1机器学习机器学习就是计算机自动获取知识，它是知识工程的三个分支(知识获取、知识表示和知识推理)之一，是AI中一个重要的研究领域，一直受到人工智能和认知心理学家们的普遍关注。机器学习涉及计算机科学、数学、心理学、生理学等多个交叉学科，涉及的面比较宽，许多理论和技术的问题尚处于研究阶段。从IJCAI，当前AI中三个研究热点：机器学习、知识表示和推理、多Agent系统2本章内容本章内容参考文献6.1概述6.2机器学习系统的基本模型6.3机械学习(RoteLearning)6.4归纳学习(InductiveLearning)6.5强化学习(Rein

2、forcementLearning)6.6统计学习(StatisticalLearning)6.7多示例学习(Learning)本章小结第6章机器学习3参参考文考文献献(1)(1)蔡自兴，徐光佑.人工智能及其应用.清华大学出版社.2004:第6章TomM.Mitchell,机器学习，曾华军等译，机械工业出版社，2003年1月第一版史忠植.高级人工智能.科学出版社,1998年：第6章/第7章/第8章陆汝钤编著:人工智能(下册)第20章/第21章T.Mitchell,Thedisciplineofmachinelearning,July2006R.E.Schapire(2001),TheBoost

3、ingApproachtoMachineLearningAnOverview,见网页http:/www.cs.princeton.edu/schapire/boost.htmlLawrenceR.Rabiner(1989),AtutorialonHiddenMarkovModels&selectedapplicationsinspeechrecognitiontheProc.ofIEEE(Vol.77,No.2)第6章 机器学习方法4参考文献(2)关于支持向量机学习，一本值得推荐的参考书是：邓乃扬、田英杰著：数据挖掘中的新方法支持向量机，科学出版社，2004年6月/特点：从基础开始讲起、详细、

4、透彻第6章 机器学习方法5机器学习顶级期刊MachineLearningJournalofMachinelearningresearchACMTransactionsonKnowledgeDiscoveryfromDataDataMiningandKnowledgeDiscovery 第6章机器学习6机器学习顶级会议ICML(InternationalConferenceonMachineLearning)ECML(EuropeanConferenceonMachineLearning)76.1概述6.1.1什么是机器学习6.1.2研究机器学习的意义6.1.3机器学习的发展史6.1.4机器学习

5、的主要策略第6章机器学习86.1.1 6.1.1 什么是机器学习：学习的概念什么是机器学习：学习的概念学习的概念：学习是系统改善其性能的过程(西蒙)。即，学习就是系统在不断重复的工作中对本身的一种改变，使其能力得到增强或改进，使得系统在下一次执行同样任务或类似任务时，会比现在做的更好或效率更高/影响较大。学习就是知识获取。由从事专家系统的人提出，因为在专家系统的建造中，知识的自动获取是非常困难的。所以知识获取似乎就成了学习的本质，但是获取的知识有时不会使系统的性能有所改善。技巧的获取往往是通过大量时间或反复的训练进行，在获取技巧时，知识获取只起到了很小的作用。第6章机器学习9学习的概念学习的概

6、念(2)(2)学习是对客观经验表示的构造或修改。客观经验包括对外界事物的感受，以及内部的思考过程，学习系统就是通过这种感受和思考过程来获取对客观世界的认识的。其核心问题就是对这种客观经验的形式进行构造和修改学习是客观规律的发现过程。这种观点将学习看作是从感性认识到理性认识的认识过程，从表层知识到深层知识的特化过程，也就是说学习就是发现事物规律，上升形成理论的过程。学习是一个有特定目的的知识获取过程，其内在行为是获取知识、积累经验、发现规律，其外在表现是使系统性能得到改进、系统实现自我完善、自适应环境。第6章机器学习10机器学习机器学习机器学习是研究如何使用计算机来模拟人类学习活动的一门科学。更

7、严格的讲，是研究计算机获取新知识和新技能、识别现有知识、不断改善性能、实现自我完善的方法。机器学习研究的目标人类学习过程的认知模型：对人类学习机制的研究，希望能从中受到启发。通用学习算法：对人类学习过程的研究，探索各种可能的学习方法，建立起独立于具体应用领域的通用学习算法。构造面向任务的专业学习系统：要解决专门的实际问题，并开发完成这些专门任务的学习系统。第6章机器学习11研究机器学习的意义(1)机器学习是研究怎样使用计算机模拟人类学习活动的机器学习是研究怎样使用计算机模拟人类学习活动的科学，是科学，是AIAI中最具有智能特征、最前沿的研究领域之中最具有智能特征、最前沿的研究领域之一，机器学习

8、的一个重大进步就标志着一，机器学习的一个重大进步就标志着AIAI甚至整个计甚至整个计算机科学向前迈进了一步。意义：算机科学向前迈进了一步。意义：学习速度学习速度：人类的学习是一个相当缓慢而又艰苦的过：人类的学习是一个相当缓慢而又艰苦的过程，受到身体生长发育和生理规律的限制。人类学习程，受到身体生长发育和生理规律的限制。人类学习从幼年开始，大约需要从幼年开始，大约需要2020年的时间才能掌握人类生活年的时间才能掌握人类生活中的基本技能，而且还必须中的基本技能，而且还必须“活到老，学到老活到老，学到老”。而。而机器学习却能以惊人的速度进行，而且机器可以不用机器学习却能以惊人的速度进行，而且机器可以

9、不用休息，其学习速度是人类无法比拟的：休息，其学习速度是人类无法比拟的：第6章 机器学习12研究机器学习的意义(2)知识积累知识积累：人类的知识不具有继承性，而机器的知识：人类的知识不具有继承性，而机器的知识具有继承性。一个人一生可能积累了很多知识，但是具有继承性。一个人一生可能积累了很多知识，但是一旦生命结束，这些知识也就随之消失了，不能把知一旦生命结束，这些知识也就随之消失了，不能把知识遗传给后代子孙。如，任何人都必须从小学开始。识遗传给后代子孙。如，任何人都必须从小学开始。如果机器具有学习能力，就可以把知识不断延续下去，如果机器具有学习能力，就可以把知识不断延续下去，避免大量的重复学习，

10、使知识积累达到新的高度。避免大量的重复学习，使知识积累达到新的高度。知识传播知识传播：一个人拥有了很多知识，但是很难让别人：一个人拥有了很多知识，但是很难让别人像他一样拥有这些知识，其他人必须从头学起。对于像他一样拥有这些知识，其他人必须从头学起。对于机器而言，只要一台机器学会了，其他机器只要简单机器而言，只要一台机器学会了，其他机器只要简单复制就学会了。利用机器学习有利于知识传播复制就学会了。利用机器学习有利于知识传播综上所述，机器学习学习速度快、便于知识积累、利综上所述，机器学习学习速度快、便于知识积累、利于知识传播，因此在机器学习领域的一点进步，就会于知识传播，因此在机器学习领域的一点进

11、步，就会使得计算机能力显著增强，从而对人类产生影响。使得计算机能力显著增强，从而对人类产生影响。第6章机器学习13机器学习的应用无处不在网络入侵检测天气预报地震预警互联网搜索引擎。14机器学习的发展史(1)1.从20世纪50年代中期到60年代中期，属于热烈时期研究目标是应用决策理论的方法，研制各类自组织系统、自适应的学习系统；基本思想是：系统是一个由互连的元件组成的网络，网络结构可能是任意的，那么这些元件类似于神经原；如果给系统一组刺激、一个反馈源和一个修改自身组织的自由度，则系统就可以自适应地趋向最优化指导本阶段的理论基础是早在20世纪40年代开始的神经网络模型；典型代表：1957年F.Ro

12、senbatt提出的感知器算法，第一个具有重要学术意义的机器学习算法。第6章机器学习15机器学习的发展史(2)2.从20世纪60年代中期到70年代中叶，属于冷时期研究目标：模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器的内部描述。研究者们力图在高层知识符号表示的基础上建立人类的学习模型，使机器能够采用符号来描述概念，并提出关于概念的各种假设。代表性工作：温斯顿(Winston)的结构学习系统和海斯罗斯(HayesRoth)等的基于逻辑的归纳学习系统虽然这里学习系统取得了较大成功，但只能学习单一概念，并且未能投入实际应用。第6章机器学习16机器学习的发展史(3)3.从20世纪70年代中期

13、到80年代中叶，属于复兴时期研究从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。知识学习的过程一般都建立在大规模知识库上，实现知识强化学习把学习系统与具体应用相结合，取得了很大成功，促进了机器学习的发展1980年，在美国的卡内基梅隆大学召开了第一届机器学习国际研讨会，标志着机器学习已在全世界兴起，从此人工智能进入应用阶段1986年，MachineLearning创刊，迎来了机器学习蓬勃发展的新时期第6章机器学习17机器学习的发展史(4)4.从1986年开始，机器学习进入新阶段从事神经元模型研究的学者们，经过10多年的潜心研究，克服了神经元模型的局限性，使得神经网络的研究重新

14、兴起。实验研究和应用研究得到前所未有的重视。第6章机器学习18机器学习的主要策略(1)学习过程与推理过程是紧密相连的，学习中使用的推理方法称为学习策略学习过程中推理过程实际上就是一种变换过程，它将系统外部提供的信息变换为符号系统内部表达的新的形式，以便对信息进行存储和使用。这种变换的性质就决定了学习策略的类型。几种基本的学习策略：机械学习：又称记忆学习。不需要任何推理过程，外面输入知识的表示方式与系统内部表示方式完全一致，不需要任何处理和变换。利用计算机的存储容量大，检索速度快，记忆精确。如下棋程序，将棋局及得分放入电脑，走棋时尽量选使自己分数高的棋局第6章机器学习19机器学习的主要策略(2)

15、传授学习：又称指导式、示教学习。外界输入知识的表示方式与系统内部表达方式不完全一致，系统在接受外部知识时，需要一点推理、翻译和转化工作。演绎学习：系统由给定的知识进行演绎的保真推理，并存储有用的结论。最近几年才成为一种独立的学习策略。演绎学习包括知识改造、知识演绎、产生宏操作、保持等价的操作和其他保真变换。归纳学习：应用归纳推理进行学习。按其有无教师指导，可以分为实例学习及观察与发现学习：实例学习：概念获取，通过向学习者提供某一概念的一组正例和反例，使学习者从这些正反例中归纳推理出概念的一般描述/这个描述应能理解所有给定的正第6章机器学习20机器学习的主要策略(3)例并排除所有给定的反例。这些

16、正反例是由信息源提供的，信息源可能是已知概念的教师，也可以是学习者本身，还可以是学习者以外的环境观察和发现学习：描述的一般化。没有教师指导，它要产生对所有或大多数观察到的规律和规则。这类学习包括概念聚类、构造分类、曲线拟合、发现并解释观察到的定律并形成理论。类比学习：在遇到新问题时，可以学习以前解决过的类似问题的解决方法，来解决当前问题。寻找与当前问题相似的已知问题很重要，并且必须能够发现当前任务与已知任务的相似之处，由此制定完成当前任务的方案。第6章机器学习21基于解释的学习(Explanation-basedlearning,EBL)。学生根据教师提供的目标概念、该概念的一个例子、领域理论

17、及可操作准则，首先构造一个解释来说明为什该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。EBL已被广泛应用于知识库求精和改善系统的性能。著名的EBL系统有迪乔恩（G.DeJong）的GENESIS,米切尔（T.Mitchell）的LEXII和LEAP,以及明斯顿（S.Minton）等的PRODIGY。基于解释的学习从本质上说属于演绎学习，它是根据给定的领域知识，进行保真的演绎推理,存储有用结论，经过知识的求精和编辑，产生适于以后求解类似问题的控制知识。22机器学习方法的分类从训练样本的歧义性（ambiguity），分为监督学习：它通过对具有概念标记（conceptl

18、abel）的训练样例进行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。/所有训练例的概念标记都是已知的，因此训练样本的歧义性最低。无监督学习：它通过对没有概念标记的训练例进行学习，以发现训练例中隐藏的结构性知识/这里的训练例的概念标记是不知道的，因此训练样本的歧义性最高。强化学习：它通过对没有概念标记、但与一个延迟奖赏或效用（可视为延迟的概念标记）相关联的训练例进行学习，以获得某种从状态到行动的映射。这里本来没有概念标记的概念，但延迟奖赏可被视为一种延迟概念标记，因此其训练样本的歧义性介于监督学习和非监督学习之间。23半监督学习（semi-supervisedlearning）：部

19、分标记。用户期望用未标记的样本来辅助对已标记样本的学习。246.3机械学习(RoteLearning)6.3.1机械学习的过程6.3.2机械学习系统要考虑的问题第6章机器学习25机械学习(RoteLearning)机械学习：记忆学习、死记硬背式学习：直接记忆或存储环境提供的新知识，并在以后通过对知识库的检验来直接使用这些知识，而不再需要进行任何的计算和推导。机械学习是一个基本的学习过程，虽然它没有独立处理事物的能力，但存储对于任何智能型的程序来说，都是必要和基本的。记忆学习是任何学习系统的一部分，任何学习系统都要将它所获取的知识存储在知识库中，以便利用这些知识。第6章机器学习26机械学习过程(

20、1)机械学习的学习过程是这样的：执行机构每解决一个问题，系统就记住这个问题和它的解。把执行机构抽象地看成是某一函数F，该函数得到输入是(x1,x2,xn)，经推导计算后得到输出为(y1,y2,yn)，如果经过评价得知该计算是正确的，则就把联想对(x1,x2,xn)，(y1,y2,yn)存入知识库中，在以后需要计算F(x1,x2,xn)时，系统的执行机构就直接从知识库中把(y1,y2,yn)检索出来，而不需要再重复计算。第6章机器学习27学习过程应用过程(x1,x2,xn)计算(y1,y2,yn)存储(x1,x2,xn),(y1,y2,yn)(x1,x2,xn)检索(y1,y2,yn)输出(x1

21、,x2,xn),(y1,y2,yn)28应用举例(1)例：要设计一个汽车修理成本估算系统。该系统的输入信息是关于待修理汽车的描述，包括制造厂商、出厂日期、车型、汽车损坏部件以及损坏程度；输出则是该汽车的修理成本。为了进行估算，系统必须在知识库中找同一厂商、同一出厂日期、同一车型、同样损坏情况的汽车，然后把知识库中对应的数据作为修理成本的估算数据输出给用户/如果在知识库中没有找到这样的汽车，则系统将请求用户给出大概的费用并进行确认，系统则将该车的描述和经过确认的费用存储到知识库中，以便下次查找使用。虽然机械学习在方法上看来很简单，但是由于计算机的存储量大、检索速度快、记忆准确，因此也能产生意想不

22、到的结果。第6章机器学习29举例(2)应用记忆学习的一个典型例子是塞缪尔的CHECKERS跳棋程序。该程序采用极大极小方法搜索博奔树在约定的搜索深度用估价函数F对格局进行评分，然后通过倒推计算求出上层节点的例推值，以决定当前的最佳走步。CHECKERS的学习环节把每个格局的倒推值都记录下来，当下次遇到相同的情况时，就直接利用“记住”的例推值决定最位走步，而不必重新计算。例如，设在某一格局A时轮到CHECKERS走步它向前搜索三步，得到如图所示的搜索树。30在上图中，根据对端节点的静态伯值，可求得A的例推值为6，最佳走步是走向c。这时CHECKERS就记住A及其倒推值6。假若在以后的博弈中又出现

23、了格局A且轮到它走步，则它就可以通过检索直接得到A的倒推值，而不必再做倒推计算，这就提高了效率。31机械学习系统要考虑的问题机械学习系统要考虑的问题(1)(1)机械学习系统不具备推理能力，只是将所有的信息存入计算机来增加知识，其实质上是以存储空间换取计算时间。虽然节省了计算时间，但却多用了存储空间。因此，机械学习系统设计时需要考虑三个问题知识库的存储结构;只有当对知识的检索所需时间少于重新计算的时间时，机械学习才有效。为了快速检索知识库的内容，要合理组织。因此，采用适当的存储方式，使检索速度尽可能的快，是机械式学习中的重要问题。环境的稳定性与存储信息的适用性：在急剧变化的情况下，机械学习不适用

24、。机械学习的一个重要假设是认为保存的知识或信息以后仍然有效。如果环境变化快，这个假设就破坏了。因此，机械学习必须保证所保存的信息适应于外界环境变化的需要，即所谓的信息适用性问题。第6章机器学习32机械学习系统要考虑的问题机械学习系统要考虑的问题(2)(2)随时监控环境的变化，不断更新知识库中保存的信息或知识。例如当发现某种汽车被淘汰了，则把与这种汽车相关的知识删除。存储与计算之间的衡量在解决一个新问题时，是利用知识库的知识还是重新计算，需要权衡比较二者的代价。在权衡到底是存储还是利用计算时，考虑两方面：在首次得到一条信息时，确定是否要保存它，这时要考虑该信息以后的使用概率、存储空间和计算代价为

25、了保证足够的检索速度，需要尽量精简知识库的内容(存储的越多检索速度越慢)。因此，对保存的内容在读取时加上时间标志，表示最后使用的时间，当保存一项新内容时，要删除一项未使用时间最长的旧内容。第6章机器学习336.4归纳学习(InductiveLearning)实例学习/观察与发现学习第6章机器学习34归纳学习归纳是人类拓展认识能力的重要方法，是一种从个别到一般、从部分到整体的推理行为归纳推理利用归纳方法，从足够多的具体实例中归纳出一般性知识，提取事物的一般性规律，它是一种从个别到一般的推理归纳推理的特点：能够产生新知识，但不保真，保假归纳学习是应用归纳推理进行学习的一种方法；归纳学习旨在根据给定

26、关于某个概念的一系列已知的正例和反例，归纳出一个一般的概念描述。它是机器学习最核心、最成熟的分支。根据有无教师指导，归纳学习分为实例学习和观察与发现学习。前者有导师，后者没有导师第6章机器学习356.6.1实例学习(Learningfromexamples)通过从环境中取得若干与某概念相关的例子，经归纳得出一般性概念的一种方法。在这种学习中，外部环境(教师)提供给系统一些特殊的例子，这些实例事先由教师将其分为正例和反例两类实例学习系统根据这些实例进行归纳推理，得到一般性的规则或知识，这些一般性的知识应能解释所有的正例，排除所有给定的反例 早在20世纪50年代，实例学习就引起了AI学者的注意，是

27、机器学习领域中研究最充分、成果最丰富的一个分支实例学习在某些系统中的应用已经成为机器学习走向实用的先导第6章机器学习36实例学习实例学习的任务：给定由N个“输入-输出”对样例组成的训练集(x1,y1),.(xN,yN)，其中每个yi由未知函数y=f(x)生成发现一个函数h，它逼近真实函数fx和y不限于数值，可以是任何形式的值(属性值向量表示法)函数h是一个假说学习是一个搜索过程，它在可能假说空间寻找一个不仅在训练集上，而且在新样例上具有高精度的假说为了测量假说h的精确度，一般给学习系统一个由样例组成的测试集，它不同于训练集所谓一个假说泛化泛化地好是指他能正确预测新样例的y值拟合：指假设能够很好

28、地在训练集上模拟f有的时候，函数f是随机的，而不是x的严格函数，其实要学的是一个条件概率分布P(Y|x)37当输出y的值为有限集合时，学习问题称为是分类若值集只包括两个元素，称为布尔或二元分类若y值是数值型的，则学习问题称为回归一个例子：在某些数据点上拟合一个单变量函数样例是(x,y)平面上的点，在真实函数f未知的情况下，用假设空间H的一个函数h逼近它假说空间是诸如x5+3x2+2形式的多项式集合38图(a)表示能用直线确切拟合某些数据/该假设称为一致假说，因为它与所有的数据相符图(b)为一个与同样数据一致的高阶多项式。图(a)图(b)39这说明了归纳学习中的一个基本问题：如何从多个假设中进行

29、抉择？答案是选择与数据一致的最简单假说这个原理基于奥卡姆剃刀原理一般来说，在较好的拟合训练数据的复杂假说和更好泛化的简单假说之间存在着折中40例如，给出肺炎与肺结核两种病的一些病例(实例)。每个病例都含有五种症状：发烧(无、低、高)，咳嗽(轻度、中废、剧烈)，x光所见阴影(点状、索条状、片状、空洞)，皿沉(正常、快)听诊(正常、干鸣音、水泡音)。4142实例学习算法的一般步骤1.预处理训练实例集2.对新事物分类预处理训练实例集，包括6个部分：离散化连续值型属性，将连续型属性的值划分为有穷多个小区间；过滤无关属性，过滤掉与目标概念无关的属性，一般可采用统计属性重要性，最小充分属性等办法来实现；处

30、理“未知”属性值，有3种途径：赋一个特殊值；赋一个最可能的值；按条件概率赋所有可能的值。第6章机器学习43处理不重要的属性值，不重要的属性值只会使实例集增大，导致学习复杂性增加，预测精度下降。清理无意义的属性值，将训练实例和将来要分类的实例中无意义的属性值去掉；数据清理，从训练集中选择一个好的实例集，以便减少噪音和不一致性，同时使得到的实例集更具有代表性。对新事物分类构造分类器的目的就是要检查新事例是否与目标概念的分类规则匹配。44按最后得到规则的表示形式，分为覆盖算法(coveringalgorithms)：归纳生成规则，一般用析取范式表示。知名的覆盖算法：AQ11(MichabkiChil

31、ausky,1980)及其扩充EQll(Michabki，Hong等，l986)，AEl(Hong，1985)及其改进AE9(赵美德、洪家荣，1995)、HCV(wM，1992)，HCV(陈格、洪家荣，1996)，GS(洪家荣，1987)，扩张TU45分治算法(divideandconquer)：归纳生成树状结构。知名的分治算法有CLS(Hunt等，1966)及其改进ID3(QuinLan,1983)、C4.5(QuinLan,1984)。第6章机器学习洪家荣.归纳学习算法、理论和应用。科学出版社,199746覆盖算法假定有两组人，其中每个人具有如下三个特征：身材：高或矮发色：金色、黑色或红色

32、眼睛(颜色)：黑色、蓝色或灰色每个人一个向量来表征，即下表给出了这两组人向量特征的集合(例子的集合)实例学习的目的就是从两类或多类例子的集合中找出描述其中一类而排出其余类的一般规则如，对于上例运行某种覆盖算法，得到两个规则4748为了讨论方便，通常把一个离散符号集映射到非负整数集上，并且把正、反例集PE与NE列成矩阵的形式并仍记为PE与NE49基本概念设E是一个n维离散符号的有穷向量空间，E=D1D2Dn，其中Dj是有穷离散符号集，jN，N=1，2,n为变元下标集。E中的元素e称为一个例子，记作e=，其中vjDj。选择子是形为xj#Aj的关系语句，其中xj是第j个变元，AjDj，关系#=,。公

33、式或复合为选择子的合取式，记为已知例子e=，选择子S=xj#Aj及公式当e满足选择子所定义的条件时，称e满足选择子；当e满足L所定义的条件时，称e满足公式L，也称为L覆盖e。给定一个正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=50正例集PE在反例集NE背景下满足公式L当且仅当每个正例都满足L，而每个反例不满足L。已知正例集PE、反例集NE，以及学习算法A。算法A归纳产生覆盖PE但排除NE的规则记为Cover(PE,NE,A)或Cover(PE,NE)51星算法与AQ11最早的覆盖算法是Michalski的Aq，其意为准优算法(quasi-optimala

34、lgorithm)，Aq算法的核心是星算法，其定义如下。已知正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=。一个正例ei+在反例ej-背景下的星记为G(ei+|ej-)，是所有覆盖ei+而排除ej-的极大复合的集合。这里一个极大复合是除覆盖ei+排除ej-之外覆盖最多数目的其他正例的复合。正例ei+在反例集NE背景下的星记为G(ei+|NE)，是所有覆盖ei+而排除NE中所有反例的极大复合的集合。引理：ei+=在反例ej-=背景下的星G(ei+|ej-)是一个逻辑公式，为ei+ej-52 即(x1=vi1+x2=vi2+xn=vin+)(x1=vj1-x2

35、=vj2-xn=vjn-)，即，(x1=vi1+x2=vi2+xn=vin+)(x1vj1-x2vj2-xn=vjn+)展开式中那些极大复合的集合。正例ei+在反例集NE背景下的星G(ei+|NE)是逻辑公式ei+NE展开式中那些极大复合的集合。易见G(ei+|NE)的展开式中共有nm个复合，其中n是变元数，m是反例数，从中寻找极大复合的问题是NP完全的，因此直接构造星是不实际的，而Aq中使用缩小的星。531980，AQ11(MichabkiChilausky,1980)扩充AQll(Michabki，Hong等，l986)AEl(Hong，1985)AE9(赵美德、洪家荣，1995)HCV(

36、XindongWu，1992)HCV(陈格、洪家荣，1996)GS(洪家荣，1987)1991年洪家荣提出扩张矩阵EM1997郭茂祖扩张图54分治算法分治算法是用属性对例子集逐级划分，直到一个结点仅含有同一类的例子为止。分治算法的结果是一棵决策树(decisiontree)最早的分治算法是Hunt等的CLS(ConceptLearningSystem)，后来又出现了Quinlan的ID3、C4.5等。决策树每一个节点表示对样本实例的某个属性值进行测试，该节点后相连接的各条路径上的值表示该属性的可能取值（二叉，三叉，）叶子节点即为实例所属的分类。每一个叶子产生一条规则，规则由根到该叶子的路径上所

37、有节点的55决策树的说明条件，规则的结论是叶子上标注的结论（决策，分类，判断）决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)一般是二值分类(真或假)56决决策策树树例子例子 第6章 机器学习方法OutlookWindHumiditySunnyOvercastRainHigh Normal Strong WeakYesNoYesNoYes(Outlook=Sunny)(Humidity=Normal)(Outlook=Overcast)(Outlook=Rain)

38、(Wind=Weak)57决策树适用问题决策树学习的适用问题：实例是由“属性-值”对表示的固定的属性+离散或连续的取值目标函数具有离散的输出值析取表达式训练数据可以包含错误决策树学习的鲁棒性好训练数据可以包含缺少属性值的实例第6章 机器学习方法58基本的决策树学习算法大多数决策树学习算法是一种核心算法CLS的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表决策树学习包括2个步骤：从实例中归纳出决策树(建立决策树)利用决策树对新实例进行分类判断ID3的构建决策树的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复以上过程，用每个分

39、支关联的训练样例来选取该节点被测试的最佳属性。59表3-1用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令E

40、xamplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）返回root60属性选择ID3算法的核心问题是选取在树的每个结点要测试的属性。希望选择最有助于分类实例的属性。/目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例ID3衡量分类属性区分训练样例能力的标准是“信息增益”。即，ID3在构建树的每一步使用这个信息增益标准从候

41、选属性中选择属性。为了定义信息增益，现定义信息论中广泛使用的一个度量标准熵，它刻画了样例集的纯度。61熵一个信息的大小是通过它的不确定性来衡量的。p(x)表示随机变量x的概率，那么用s(x)表示X的信息量。如果p(x)=1或0，则s(x)=0;一个随机变量x(假设x有n个可能取值)的平均信息量，即熵是这样计算的：对于包含关于某个目标概念的正反样例集S，那么S相对于这个布尔型分类的熵为，其中p1和p2分别表示S中正例的比例和反例的比例62熵的物理意义熵用于衡量样本集的纯度；如果样例集S中所有成员均属于一类，则S的熵为0；如果S中正反例数目相当，其熵为1。熵值越大，表示样例越不纯，同时信息量越多；

42、反之则样例越纯，信息量越小6364信息增益有了用熵度量训练样例集纯度的标准，现在可以定义属性分类训练数据能力的度量标准。一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。即，一个属性A相对于样例集合S的信息增益Gain(S,A)被定义为：其中，values(A)表示属性A所有可能值的集合，Sv是S中属性A的值为v的子集，Entropy(S)表示原集合S的熵，Entropy(Sv)表示用A分类S后的熵。65例：假定S是一套有关天气的训练样例，描述它的属性为可具有weak和Strong两个值的Wind。假定S中有14个样例，其中正例9个，反例5个。在这14个样例中，假定正例中的6个

43、和反例中的2个有Wind=weak，其他的是Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益计算如下：6667在ID3中，每次要选择增益最大的属性如何理解选信息增益最大的属性？第6章 机器学习方法G开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知G随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减小了G到达叶子节点，分类完成，此时不确定性为零G综上所述，构建决策树的过程是熵不断下降的过程。G要提高决策树的分类效率，就要求熵值下降的更快/这样，ID3算法的实质就是构造一棵熵值下降平均最快的决策树G每次选

44、择信息增益最大的属性，就相当于是选择平均熵下降最快的属性；68决策树算法的要点是在构造决策树的每一层次(从根向下)时，从尚未检测的属性中挑选一个信息增益最高的属性进行分解69例子著名的隐形眼镜例子对于是否可配戴隐形眼镜，可把人们分为3类：类1：适于配戴硬性隐形眼镜；类2：适于配戴软性隐形眼镜；类3：不适于配戴隐形眼镜为了判断一个人是否适合配戴隐形眼镜，需要检查以下4种属性：属性a：配戴者年龄，取值a=属性b：配戴者的视力缺陷，取值b=属性c：配戴者是否有散光，取值c=属性d：配戴者泪腺分泌情况，取值d=第6章 机器学习方法70隐隐形眼形眼镜镜例子例子(1)(1)上述属性和人群分类一律按顺序用数

45、字1,2表示，可以假设根据属性a、b、c、d有如下表的分类(纯属虚拟)计算S初始熵值和各属性分解熵值如下：初始熵值为Entropy(S)=-p1logp1-p2logp2-p3logp3属于第1类4个/第2类5个/第3类15个Entropy(S)=-=-(4/24)log(4/24)-(5/24)log(5/24)-(15/24)log(15/24)=0.4308+0.4715+0.4238=1.3261第6章 机器学习方法71隐隐形眼形眼镜镜例子例子(2)(2)第6章 机器学习方法72隐隐形眼形眼镜镜例子例子(3)(3)为了方便地计算各个属性的信息增益，给出下表从表中可得，X中属性a=2/3

46、的w1元素只有1个，a=1的w1元素是2个/而属性d=1的w3元素共有12个，而此时没有w1/w2分类/如此等等第6章 机器学习方法73隐隐形眼形眼镜镜例子例子(4)(4)利用上表，可以得到如下计算：Entospy(a=1)=-(2/8)log(2/8)-(2/8)log(2/8)-(4/8)log(4/8)=0.5+0.5+0.5=1.5Entospy(a=2)=-(1/8)log(1/8)-(2/8)log(2/8)-(5/8)log(5/8)=0.375+0.5+0.4238=1.2988Entospy(a=3)=-(1/8)log(1/8)-(1/8)log(1/8)-(6/8)log

47、(6/8)=0.375+0.375+0.3113=1.0613由此得Gain(S,a)=E(S)-p(a1)Entospy(a=1)-p(a2)Entospy(a=2)-p(a3)Entospy(a=3)=1.3261-(8/24)*1.5+(8/24)*1.2988+(8/24)*1.0613=1.3261-0.5-0.4329-0.3538=0.0394第6章 机器学习方法74隐隐形眼形眼镜镜例子例子(5)(5)同样可得：Gain(S,b)=1.3261-(12/24)*(0.5+0.4308+0.4536)+12/24)*(0.2987+0.5+0.3900)=1.3261-0.6922

48、-0.5944=0.0395Gain(S,c)=1.3261-(12/24)*(0+0.5263+0.4536)+(12/24)*(0.5283+0+0.3900)=1.3261-0.4900-0.4592=0.3769Gain(S,d)=1.3261-(12/24)*(0.5283+0.5263+0.5)=0.5488第6章 机器学习方法75隐隐形眼形眼镜镜例子例子(6)(6)根据以上计算数据，选择信息增益最大的Gain(S,d)，即以属性d作为第一次划分/此时d=1分支中的元素全部为w=3类别，只需对d=2分支继续进行熵值计算/d=2分支为(X,a,b,c)，X是去掉d=1的元素之后剩下的

49、集合(12个元素)第6章 机器学习方法X,dd=1d=2w3X76隐隐形眼形眼镜镜例子例子(7)(7)缩小以后集合S的属性取值表如下第6章 机器学习方法77隐隐形眼形眼镜镜例子例子(8)(8)接着进行计算，注意在集合S下Entropy(S)Gain(S,a)=.Gain(S,b)=Gain(S,c)=Gain(S,d)=经过反复计算，可得如图示的决策树第6章 机器学习方法78隐隐形眼形眼镜镜例子例子(9)(9)第6章 机器学习方法该例子给出的数据完整情况(请考虑实例不完整情况下如何建立决策树？)79算法的评价 一个学习算法产生的假设(或者分类)应该对未知的实例进行很好的预测如何评价预测的质量也

50、就是学习算法的性能？有2种方式预先估计预测的质量计算学习理论，回答为什么学习是可行的事后考察预测的质量实验验证(训练集/测试集)第6章 机器学习方法80实验验证策略预留法（holdoutcrossvalidation）随机将数据分为训练集和测试集，训练集用于学习算法产生h，测试集用于评估h的精度缺点：不能利用所有可用数据，得到的低劣假说或低劣估计K-折交叉验证（k-foldcrossvalidation）能从数据中获取更多东西，并仍然获得精确估计每个样例既作为训练数据又做为测试数据81基本思想：将数据划分为k个规模相等的子集执行k轮次学习在每次学习中，选择1个子集作测试集，然后k-1个作为训练