第七章-机器学习课件.ppt

1、第六章 机器学习北京物资学院管理科学与工程系赵明茹 机器学习n概述n机器学习系统的基本模型n机械学习n实例学习n解释学习概述n到目前为止的大多数人工智能系统还完全没有或仅有有限的学习能力。n系统中的知识是由人工编程送入的，知识中的错误也不能自动改正。机器的能力是否能超过人的能力？n否定意见：机器是人造的，其性能和动作是由设计者规定的，因此无论如何其能力也不会超过设计者本人。n对于不具备学习能力的机器来说是正确的，可是对于具备学习能力的机器就值得考虑了。n机器学习的不可预测问题。跳棋程序n20世纪50年代末，阿瑟.塞缪尔（samuel）编写了著名的跳棋程序。n启发式搜索技术，跳棋程序可以向前看几

2、步然后再走棋。n可以从经验中学习，从棋谱中学习。不断调整棋盘评价函数，提高自己的棋艺。n经过三年的学习，打败了Samuel，又三年，打败了州冠军。n同时刺激了“搜索”和“机器学习”这两个人工智能的重要领域的发展。塞缪尔塞缪尔n1901年生于美国堪萨斯州的恩波利亚，恩波利亚学院上学。n1923年大学毕业以后，他进入MIT念研究生，1926年取得硕士学位。n留校工作两年以后，他加盟贝尔实验室，从事电子器件的研究。二次世界大战爆发以后，他的研究工作集中于雷达技术。n战争结束后，到伊利诺大学电气工程系任教，积极参与了该校研制电子计算机的工作。n1949年即转至IBM公司在普凯泼茜的研发实验室工作，参与

3、其第一台大型科学计算机701的开发。n塞缪尔在下棋程序方面的工作对IBM公司早期计算机的指令系统产生了很大影响。由于下棋程序是计算机应用中最早的一种典型的非数值计算，因此在701中加入了许多逻辑指令，这类指令后来迅速被所有计算机的设计者所采用和推广，成为计算机指令集中的基本成分。n1966年塞缪尔从IBM公司退休以后，到斯坦福大学从事教学和研究工作，指导博士生，直到1982年。n塞缪尔晚年得了帕金森综合症。病中他开始撰写自传，但只写到20世纪60年代中期，即于1990年7月29日在加利福尼亚州的家中撒手西去。n塞缪尔生前除了获得IZEE的计算机先驱奖以外，没有别的荣誉和奖励。什么是机器学习nS

4、imon认为“学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作”。nMinsky认为“学习是在我们的头脑中进行有用的变化”。n有的观点认为“机器学习就是知识的获取”，但获取的知识有时不会使系统有所改善。学习的基本形式n知识获取 学习的本质就是获取新的知识，包括物理系统、行为的描述和模型的建立，构造客观现实的表示。n技能求精 通过实践改造机制和认知技能。这些技能包括意识的或机制的。这种改变是通过反复实践和从失败中纠正错误来进行的。学习骑自行车。为什么要研究机器学习？n人工智能主要是为了研究人的智能，模仿其机理将其应用于工程的科学，在这个过程中，必然会问到“人类怎么做才能获得这种特

5、殊技能（或知识）？”n当前的人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。n未来的计算机将有自动获取知识的能力，直接从书本中学习，通过与人谈话学习，通过观察学习。通过实践自我完善。n克服人的存储少，效率低，注意力分散，难以传送所获取知识等局限性。n一台计算机获取的知识很容易复制给任何其他机器。为什么要研究机器学习？机器学习实现的困难n预测难：学习后知识库发生了什么变化，系统功能的变化的预测。n归纳推理：现有的归纳推理保假，不保真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多的是假的，给生成知识带来不可靠性。n机器目前很难观察什么重要，什么有意义。机

6、器学习的发展史 第一阶段是在50年代中叶到60年代中叶，属于热烈时期。在这个时期，所研究的是“没有知识”的学习，即“无知”学习；其研究目标是各类自组织系统和自适应系统；指导本阶段研究的理论基础是早在40年代就开始研究的神经网络模型。在这个时期，我国研制了数字识别学习机。机器学习的发展史 第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。本阶段的研究目标是模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器内部描述。这个时期正是我国“史无前例”的十年，对机器学习的研究不可能取得实质进展。机器学习的发展史 第三阶段从70年代中叶至80年代中叶，称为复兴时期。在这个时期，人们从学习单

7、个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。本阶段已开始把学习系统与各种应用结合起来，中国科学院自动化研究所进行质谱分析和模式文法推断研究，表明我国的机器学习研究得到恢复。n1980年西蒙来华传播机器学习的火种后，我国的机器学习研究出现了新局面。机器学习的发展史n机器学习的最新阶段始于1986年。一方面，由于神经网络研究的重新兴起，另一方面，对实验研究和应用研究得到前所未有的重视。我国的机器学习研究开始进入稳步发展和逐渐繁荣的新时期。机器学习的主要策略机器学习的主要策略n学习过程与推理过程是紧密相连的，按照学习中使用推理的多少，机器学习所采用的策略大体上可分为：机械学习、传授学

8、习、演绎学习、类比学习和归纳学习。n学习中所用的推理越多，系统的能力越强。机械学习n机械学习又称为记忆学习，是最简单的学习策略。n这种学习策略不需要任何推理过程。外面输入知识的表示方式与系统内部表示方式完全一致，不需要任何处理和变化。传授学习n传授学习又称指导式学习或指点学习。n在使用传授学习系统时，外界输入知识的表达方式与系统内部表达方式不完全一致，系统在接受外部知识时，需要一点推理、翻译和转化工作。演绎学习n在演绎学习中，学习系统由给定的知识进行演绎的保真推理，并存储有用的结论。归纳学习n归纳学习是应用归纳推理进行学习的一类学习方法。按其又无教师的指导，可以分为实例学习及观察与发现学习。实

9、例学习n实例学习又称为概念获取，它是通过向学习者提供某一概念的一组正例和反例，使学习者从这些正反例中归纳推理出概念的一般描述，这个描述应能解释所有给定的正例并排除所有给定的反例。n这些正反例是由信息源提供的，信息源可能是已经知道概念的教师，也可以是学习者本身，还可能是学习者以外的外部环境。观察与发现学习n观察与发现学习又称为描述的一般化。这类学习没有教师的指导，它要产生对所有或大多数观察到的规律和规则的解释。n这类学习包括概念聚类、构造分类、曲线拟合（使方程符合数据）、发现并解释观察到的定律并形成理论。类比学习n类比学习就是在遇到新的问题时，可以学习以前解决过的类似问题的解决方法，来解决当前的

10、问题。n所以寻找与当前问题相似的已知问题就很重要，并且必须要能够发现当前任务与已知任务的相似之点，由此制定出完成当前任务的方案。n类比学习可以由系统已有的某一领域知识得到另一领域中类似的知识。机器学习系统的基本模型n以西蒙关于学习的定义作为出发点，建立机器学习系统的基本模型。环境学习环节知识库执行环节学习系统的基本模型n环境和知识库是以某种知识表示形式表达的信息的集合，分别代表外界信息来源和系统所具有的知识；“学习环节”和“执行环节”代表两个过程。n“环境”向系统的“学习环节”提供某些信息，而“学习环节”则利用这些信息对系统的“知识库”进行改进，以增进系统“执行环节”完成任务的效能，“执行环节

11、”根据知识库中的知识来完成某种任务，同时把获得的信息反馈给“学习环节”。环境n环境可以是系统的工作对象，也可以包括工作对象和外界条件。例如在医疗系统中，环境就是病人当前的症状、检验的数据和病历。在模式识别中，环境就是待识别的图形或景物。n环境就是为学习系统提供获取知识所需的信息。信息的水平和质量，对学习系统获取知识的能力有很大的影响。学习环节n学习环节通过获得外部信息，并将这些信息与执行环节所反馈回的信息进行比较。一般情况下环境提供的信息水平与执行环节所需的信息水平之间往往有差距，经分析、综合、类比、归纳等思维过程，学习环节就要从这些差距中获取相关对象的知识，并将这些知识存入知识库中。知识库n

12、知识库用于存放由学习环节所学到的知识。n影响学习系统设计的第二个因素是知识库的形式和内容。知识库的形式就是知识表示的形式。n选择知识表示方法要考虑下列准则：可表达性、推理难度、可修改性和可扩充性。表达能力强n人工智能系统研究的一个重要问题是所选择的表示方式能很容易地表达有关的知识。例如，如果我们研究的是一些孤立的木块，则可选用特征向量表示方式。用(,)这样形式的一个向量表示木块，比方说(红，方，大)表示的是一个红颜色的大的方形木块，(绿，方，小)表示一个绿颜色的小方形木块。但是，如果用特征向量描述木块之间的相互关系，比方说要说明一个红色的木块在一个绿色的木块上面，则比较困难了。(x)(y)xy

13、(RED(X)GREEN(Y)ONTOP(X,Y)易于推理 在具有较强表达能力的基础上，为了使学习系统的计算代价比较低，我们希望知识表示方式能使推理较为容易。例如，在推理过程中经常会遇到判别两种表示方式是否等价的问题。在特征向量表示方式中，解决这个问题比较容易；在一阶逻辑表示方式中，解决这个问题要花费较高的计算代价。因为学习系统通常要在大量的描述中查找，很高的计算代价会严重地影响查找的范围。因此如果只研究孤立的木块而不考虑相互的位置，则应该使用特征向量表示。容易修改知识库n学习系统的本质要求它不断地修改自己的知识库，当推广得出一般执行规则后，要加到知识库中。当发现某些规则不适用时要将其删除。n

14、因此学习系统的知识表示，一般都采用明确、统一的方式，如特征向量，产生式规则等，以利于知识库的修改。n从理论上看，知识库的修改是个较为困难的课题，因为新增加的知识可能与知识库中原有的知识矛盾，有必要对整个知识库做全面调整。删除某一知识也可能使许多其它的知识失效，需要进一步做全面检查。知识表示易于扩展n随着系统学习能力的提高，单一的知识表示已经不能满足需要；一个系统有时同时使用几种知识表示方式。不但如此，有时还要求系统自己能构造出新的表示方式，以适应外界信息不断变化的需要。因此要求系统包含如何构造表示方式的元级描述。现在，人们把这种元级知识也看成是知识库的一部分。这种元级知识使学习系统的能力得到极

15、大提高，使其能够学会更加复杂的东西，不断地扩大它的知识领域和执行能力。执行环节n执行环节是整个机器学习系统的核心。执行环节用于处理系统面临的现实问题，即应用知识库中所学到的知识求解问题，如智能控制、自然语言理解和定理证明等，并对执行的效果进行评价，将评价的结果反馈回学习环节，以便系统进一步的学习。n执行环节的问题复杂性、反馈信息和执行过程的透明度都对学习环节有影响。执行环节n执行部分是整个学习系统的核心，因为执行部分的动作就是学习部分力求改进的动作。同执行部分有关的问题有3个：复杂性、反馈和透明性。n复杂的任务比简单的任务需要更多的知识，对于这类简单任务，有一条分组规则就可以了。有的要使用几百

16、条规则。对于通过例子学习的计算机系统，最简单的执行任务是按照单一的概念或规则进行分类或预测。比较复杂一点的任务涉及多个概念。学习系统最复杂的任务是小型计划任务，系统必须给出一组规则序列，执行部分依次执行这些规则。反馈信息n所有的学习系统必须以某种方式评价学习部分提出的假设。有些程序有一部分独立的知识专门从事这种评价。例如AM系统就有许多探索规则评价学习部分提出的新概念的意义。然而最常用的方法是由教师提出外部执行标准，然后观察执行部分相对这个标准做的如何，再把执行结果反馈给学习部分，以决定假设的取舍。透明性n透明性即要求从系统执行部分的动作效果可以很容易地对知识库的规则进行评价。例如下完一盘棋之

17、后从输赢总的效果判断所走每一步的优劣则比较困难，但若记录了每一步之后的局势，从局势判断优劣则比较直观和容易。机械学习n机械学习是最简单的机器学习方法。机械学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。n机械学习又是最基本的学习过程。任何学习系统都必须记住它们获取的知识。n在机械学习系统中，知识的获取是以较为稳定和直接的方式进行的，不需要系统进行过多的加工。n当机械学习系统的执行部分解决好问题之后，系统就记住该问题及其解。我们可把学习系统的执行部分抽象地看成某个函数，该函数在得到自变量输入值(X1,X2,Xn)之后，计算并输出函数值(Y1,Y2,Yp)。n机械学习在存

18、储器中简单地记忆存储对(X1,X2,Xn),(Y1,Y2,Yp)。当需要f(X1,X2,Xn)时,执行部分就从存储器中把(Y1,Y2,Yp)简单地检索出来而不是重新计算它。机械学习的主要问题机械学习的主要问题（1 1）存储组织信息：采用适当的存储方式，使检）存储组织信息：采用适当的存储方式，使检索速度，尽可能地快，是机械学习中的重要问索速度，尽可能地快，是机械学习中的重要问题。题。（2 2）环境的稳定性与存储信息的适用性问题：机）环境的稳定性与存储信息的适用性问题：机械学习系统必须保证所保存的信息适应于外界械学习系统必须保证所保存的信息适应于外界环境变化的需要，这也就是所谓的信息适用性环境变化

19、的需要，这也就是所谓的信息适用性问题。问题。（3 3）存储与计算之间的权衡：对于机械学习来说）存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率很重要的一点是它不能降低系统的效率归纳学习n归纳学习按有无教师的指导可分为实例学习和观察与发现学习两种形式。n在归纳学习中，变换过程是对输入信息的一般化和选择最合理的预期结果，这就是归纳推理。实例学习n实例学习又称为示例学习或通过事例学习。它是通过例子，经归纳得出一般性概念的一种方法。n在这种学习方法中，外部环境提供给系统一些特殊的实例，这些实例事先又被施教者划分为正例和反例。n实例学习系统由此进行归纳推理，得到一般的规则或一般性

20、的知识，这些一般性知识应能解释所有给定的正例，并排除所有给定的反例。实例学习的两个空间模型n实例学习中有两个重要的概念：例子空间和规则空间。n例子空间就是向系统提供的训练例子集合，如教系统识别狗时提供的狗、其它动物和物品。n规则空间是事物所具有的某种规律，例如“狗有四条腿”、“狗有两只眼睛”、“狗有一条尾巴”等实例学习的两个空间模型例子空间要考虑的问题n示教例子的质量：要求无二义性。n例子空间的组织和搜索方法：选择适当的例子以便证实或否决规则空间中某些假设规则集。n为了提高搜索效率，需要设计合适的搜索算法，并把它与例子空间的组织结构进行统筹考虑。规则空间要考虑的问题n所谓规则空间用规定的描述语

21、言可以表示的所有规则的集合即为规则空间。n与规则空间有关的两个问题是对规则空间的要求和规则空间的搜索方法。n规则的表示与实例的表示一致。n规则的表示形式应适应归纳推理。n规则空间中应包括所有可能产生的规则。常用的几种归纳推理方法n常量化成变量n去掉条件n增加选择n曲线拟合常量化成变量n示例1：花色(C1,梅花)花色(C2,梅花)花色(C3,梅花)花色(C4,梅花)花色(C5,梅花)同花(C1,C2,C3,C4,C5)n示例2：花色(C1,红桃)花色(C2,红桃)花色(C3,红桃)花色(C4,红桃)花色(C5,红桃)同花(C1,C2,C3,C4,C5)n其中示例1表示5张梅花牌是同花，示例2表示

22、5张红桃牌是同花。把常量“梅花”和“红桃”换成变量x，就归纳出一条假设规则。n规则1：花色(C1,x)花色(C2,x)花色(C3,x)花色(C4,x)花色(C5,x)同花(C1,C2,C3,C4,C5)去掉条件n去掉条件就是把示例中的某些无关的子条件去掉。如：示例3：花色(C1,红桃)点数(C1,3)花色(C2,红桃)点数(C2,5)花色(C3,红桃)点数(C3,7)花色(C4,红桃)点数(C4,10)花色(C5,红桃)点数(C5,K)同花(C1,C2,C3,C4,C5)n为了得到上述规则1，不但要把常量“红桃”化为变量x，而且要去掉所有的“点数”谓词。增加选择n例如要程序来学习“人面牌”的概

23、念，“人面牌”是指点数为J、Q、K的牌。提供的两个真例是：示例4：点数（C1，J）人面牌（C1）n示例5：点数（C1，K）人面牌（C1）n将两个示例的前件进行析取合并后等价地得到点数（C1，J）点数（C1，K）人面牌（C1）如果在析取条件中增加一种选择，就得到要求的规则规则2：点数（C1，J）点数（C1，Q）点数（C1，K）人面牌（C1）增加选择就是在析取条件中增加一个新的析取项。“常量化成变量”是一种由具体到一般的演变或归纳；“去掉条件”就是去掉合取项，也就是去掉部分约束；“增加选择”就是增加析取项，也就是扩大范围。后两种方法都是直接扩大范围，但方法更强，归纳过快，因此更容易出错，方法较弱，

24、不易出错，但归纳较慢。例如对示例4和示例5使用方法就会得到下列错误：点数（C1，x）人（C1）.(错误)归纳推理n这个结果说明归纳过程很容易出错，归纳推理不是保真的，是保假的（前提为真则结论不一定为真，前提为假则结论一定为假）。n归纳过程就是从多种归纳方法中选择正确的方法，以得到正确的结果。n因此归纳过程就是搜索过程，在归纳的过程中，出现错误后要进行回溯。n发现错误的方法，一般是选用新的例子去否定归纳出的错误规则，在实例学习的两个空间模型中也正是这样表示的。规则空间的要求：n规则表示与例子表示的一致性n规则表示方法应适应归纳推理 n规则空间应包含所要求的规则搜索规则空间的方法n搜索规则空间的方

25、法有两大类，一类称为数据驱动方法，另一类称为模型驱动方法。n数据驱动方法就是指从例子空间出发，通过对例子进行解释，再根据解释，在规则空间中搜索合适的规则，例子空间的例子就看做是搜索的前提数据。n模型驱动是指从规则集中找到一个合适的规则（模型），然后到例子空间去选取例子，对规则进行验证。变型空间法n变型空间方法是一种数据驱动方法，这种方法使用统一的形式表示规则和例子。该方法以整个规则空间作为初始的假设规则集合H，H中包括满足第一个示教正例的所有规则，在得到下一个示教例子时，依据示教例子中的信息，对集合H进行一般化或特殊化处理，逐步缩小集合H，最后使H收敛为只含有所要求的规则。由于被搜索的空间H逐

26、步缩小，故称为变形空间。变型空间方法n变型空间方法的优点是可以逐步接受示教例子逐步学习，不需要程序回溯就可以利用例子空间中的新例子，对规则集合H进行修改。其缺点是抗干扰能力差。变型空间方法难以处理有干扰的例子。由于学习算法所得到的概念应满足每一个示教例子的要求，因此例子空间中的一个错误例子就会造成很大影响，使学习系统得到错误的概念，有时甚至得不到概念，这时H将称为空集。泛化特化更一般更特殊没有描述GS四、变型(版本)空间方法(Version Space)以整个规则空间为初始的假设规则集合H，依据训练例子中的信息，对集合H进行泛化和特化处理，逐步缩小集合H。Mitchell假定这个空间是一偏序结

27、构，并将单个概念学习定义为在这个空间的搜索。n步骤：把集合G初始化为最一般的概念，把集合S初始化为包含所有可能的情况，G=(x,y)S=(sm,squ),(sm,cir),(sm,tri),(lg,squ),(lg,cir),(lg,tri)现在提供第一个示教正例(sm,cir)，表示小圆是圆。由于集合G满足正例的要求，所以不发生变化，而集合S原有的元素太多，先将其删去，仅保留符合该次正例的元素，接下来的学习过程中，再由陆续示教的正例进行补充集合S。S=(sm,cir)步骤：接受新的示教例子，这个例子是(lg,tri)。这表示大三角不是圆。这个是反例，必须删去G中符合反例的元素，使得G集合特殊

28、化。在规则空间中的变化是G下降。由于示教的是反例，所以集合S没有变化。得到：G=(x,cir),(sm,y)S=(sm,cir)如图所示，此时H仅含有二个概念。这二个概念是满足第一个例子，但不满足第二个例子的全部概念。接受第三个示教例子(lg,cir)，这是一个正例，表示大圆是圆。首先从G中删除不满足此正例的概念(sm,y)，再对S中原有的元素S=(sm,cir)和本示教例子的(lg,cir)做一般化操作（将常量变成变量），得到：G=(x,cir)S=(x,cir)n步骤：由于此时G=S，且两个集合中仅包含一个元素，因此算法结束，并输出概念：(x,cir)初始变形空间第一个示教例子后的变形空间第二个示教例子后的变形空间