9 人工智能与专家系统(2011)8

1第七章机器学习7.1机器学习概述7.2机械式学习7.3解释学习7.4归纳学习7.5类比学习2机器学习经典定义：利用经验改善系统自身的性能[T.Mitchell,Book97]随着该领域的发展，主要做智能数据分析典型任务：预测例如：天气预报3机器学习的重要性美国航空航天局JPL实验室的科学家在《Science》（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发展。生物信息学计算金融学分子生物学行星地质学……工业过程控制机器人……遥感信息处理信息安全机器学习4重要性：例子—网络安全入侵检测：是否是入侵？是何种入侵？如何检测？•历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现……•对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络决策树支持向量机k近邻序列分析聚类…………5重要性：例子—生物信息学常用技术：神经网络支持向量机隐马尔可夫模型k近邻决策树序列分析聚类…………67.1机器学习概述机器学习的概念学习系统模型机器学习分类机器学习的研究历史机器学习的研究目标7①机器学习的概念⑴什么是学习Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。Minsky认为：学习是在人们头脑中（心理内部）进行有用的变化。当前关于机器学习的许多文献中大体认为：学习是系统积累经验以改善其自身性能的过程。8①机器学习的概念（2）什么是机器学习学习是获取知识、积累经验、改进性能、发现规律、适应环境的过程。其基本机制是设法将在一种情形下成功的表现行为转移到另一类似的新情形中去。机器学习是使系统做一些适应性的变化，使得系统在下一次完成类似的任务时比前一次更有效（3）人类学习与机器学习●人类学习是个漫长的过程●人类学习不存在复制的过程●人类学习可以遗忘●人类学习是逐渐积累的过程9②机器学习系统如果一个系统能够从某个过程或环境的未知特征中学习到有关信息，并能把学到的信息用于对未来的估计、分类、决策或控制，以便改进系统的性能，那么它就是一个学习系统。10学习系统基本构成环境学习环节知识库执行与评价11一个学习系统至少应具有以下几部分●环境：包括工作对象和外界条件●学习环节：它通过对环境的搜索获取外部信息，然后经分析、综合、类比、推理等思维过程获得知识，并竟这些知识送入知识库。●知识库：知识库的形式就是知识表达的形式。知识表达形式应具有◆可表达性◆推理难度◆可修改性◆可扩展性●执行环节②机器学习系统12机器学习系统的条件和能力具有适当的学习环境具有一定的学习能力能应用学到的知识求解问题能提高系统的性能13③机器学习分类⑴基于推理策略的分类●机械学习●讲授学习●演绎学习●解释学习●类比学习●归纳学习⑵基于系统性的分类●归纳学习●分析学习●联结学习●遗传学习141）有导师学习（监督学习）：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。2）无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。（3）基于学习方式的分类15④机器学习的研究历史⑴神经元模型研究阶段：W.S.McCulloch和W.Pitts（1943）的模拟神经元的理论。⑵符号概念获取研究阶段：60年代初进入⑶符号学习发展阶段：70年代中期⑷联结学习和符号学习共发展阶段：80年代以后●1980年，在卡内机-梅隆大学召开第一届机器学习国际研讨会；●1986年创刊第一本机器学习杂志Machinelearning。16机器学习现在已经发展到一个新阶段机器学习起源于人工智能对人类学习能力的追求，上一阶段的研究几乎完全局限在人工智能这一领域中（学习本身是目的）而现在，机器学习已经开始进入了计算机科学的不同领域，甚至其他学科，成为一种支持技术、服务技术（学习本身是手段）如果我们想做出重要的贡献，首先需要把握住该领域发展的脉搏。17●机器学习目标有三个，即⑴通用学习算法：这个方向的研究是理论分析和开发用于非实用的学习任务算法。⑵认知模型：这是研究人类学习机制和思维方法。(3)工程目标：这个研究目标就是解决专门的实际问题，并开发完成这些任务的工程系统。⑤机器学习的研究目标18实例学习例子训练实例集合:1.(乌鸦w1，羽毛黑);2.(乌鸦w2，羽毛浅黑);3.(麻雀w3，羽毛灰);4.(鸽子w4，羽毛白);5.(乌鸦w5，羽毛白);6.(乌鸦w6，羽毛黑)；7.(乌鸦w7，羽毛黑);8.(燕子w8，羽毛灰)–根据训练实例集合提出规则(假设）:乌鸦(x)黑（羽毛）¬黑（羽毛）¬乌鸦(x)–归纳：(乌鸦，黑色的羽毛)–可信度：4/5=0.8197.2机械式学习(RoteLearning)机械学习是最简单的机器学习方法。机械学习就是记忆学习，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。机械学习又是最基本的学习过程。任何学习系统都必须记住它们获取的知识。其实质是用存储空间来换取处理时间。20机械学习基本思想可把学习系统的执行部分抽象地看成某个函数，该函数在得到自变量输入值之后，计算并输出函数值。机械学习在存储器中简单地记忆存储对21当需要执行部分就从存储器中把简单地检索出来而不是重新计算它。●这种简单的学习模式如下：机械学习基本思想22例如我们可以在大量病例的基础上归纳总结出治疗的一般规律，形成规则，当遇见一个新病例时，我们就使用规则去处理它，而不必参照以前的众多病例推断解决办法。化简的目的，主要是为了提高工作效率。23机械学习的主要问题存储组织信息环境的稳定性与存储信息的适用性问题存储与计算之间的权衡247.3解释学习Explanation-BasedLearning,简称EBL，是20世纪80年代中兴起的机器学习方法，它是一种演绎学习方法。解释学习是通过运用相关的领域知识及一个训练实例来对某一目标概念进行学习，从而构造解释并产生相应的知识，以便用于指导以后求解类似问题。25解释学习1983年美国Illinois大学的DeJong提出。1986年,Mitchell,Keller和Kedar-Cabelli提出了解释的泛化(Explanation-BasedGeneralization,简称EBG)的统一框架,1986年DeJong和Mooney提出全局取代解释泛化ExplanationGeneralizationusingGlobalSubstitutions,缩写EGGS)方法1987年卡耐基-梅隆大学的Minton和Carbonell提出解释特化(Explanation-BasedSpecialization，简写EBS)学习方法26（1）解释学习的过程利用基于解释的方法对训练实例进行分析与解释，以说明它是目标概念的一个实例。对实例的结构进行概括性解释，建立该训练实例的解释结构以满足所学概念的定义；解释结构的各个叶节点应符合可操作标准，且使这种解释比最初的例子适用于更大的一类例子。从解释结构中识别出训练实例的特性，并从中得到更大一类例子的概括性描述，获取一般控制知识。27EBL的效率选择一条通用规则•太多规则-推理太慢•目标驱动-极大地提高了速度•尽可能的通用可操作性-一个子目标是可操作的，意思是容易解决•可操作性和通用性之间的平衡对EBL学习效率的实验分析28（2）解释学习模型概念描述空间概念空间例子空间D1不可操作的可操作D2C1I1I2I3解释学习的空间描述29例子目标概念：一对物体x,y，SAFE-TO-STACK(x,y)，其中STACK(x,y)NOT(FRAGILE(y))∨LIGHTER(x,y)。训练实例：–ON(OBJ1,OBJ2)–ISA(OBJ1,BOX)–ISA(OBJ2,ENDTABLE)–COLOR(OBJ1,RED)–COLOR(OBJ2,BLUE)–VOLUME(OBJ1,1)–DENSITY(OBJ1,.1)–…30领域知识：–VOLUME(p1,v1)∧DENSITY(p1,d1)→WEIGHT(p1,v1*d1)–WEIGHT(p1,w1)∧WEIGHT(p2,w2)∧LESS(w1,w2)→LIGHTER(p1,p2)–ISA(p1,ENDTABLE)→WEIGHT(p1,5)(default)–LESS(.1,5)–…可操作标准：概念定义必须要用描述实例中的谓词，或者选自领域知识易于评测的谓词。确定：–训练实例的泛化是对目标概念给以充分定义，并且满足可操作性标准。31知识库中的领域知识是把一个物体放置到另一个物体上的安全性标准则：32SAFE-TO-STACK(OBJ1,OBJ2)解释树337.4归纳学习（inductivelearning）归纳学习是研究最广的一种符号学习（symboliclearning）方法，它表示从例子设想出假设的过程。在进行归纳学习时，学习者从所提供的事实或观察到的假设进行归纳推理，获得某个概念。归纳推理是个从部分到全体，从特殊到一般的推理过程。34（1）归纳推理的方法归纳是指从个别到一般，从部分到整体的一类推论行为。归纳推理是应用归纳方法所进行的推理，即从足够多的事例中归纳出一般性的知识，它是一种从个别到一般的推理。在进行归纳时，多数情况下不可能考察全部有关的事例，因而归纳出的结论不能绝对保证它的正确性，只能以某种程度相信它为真，这是归纳推理的一个重要特征。35归纳推理的方法枚举归纳联想归纳类比归纳逆推理归纳36①枚举归纳设a1，a2，…是某类事物Ａ中的具体事物，若已知a1，a2，…an，都有属性P，并且没有发现反例，当n足够大时，就可得出“A中所有事物都有属性P”的结论。这是一种从个别事例归纳出一般性知识的方法，“A中所有事物都有属性P”是通过归纳得到的新知识。37②联想归纳若已知两个事物a与b有n个属性相似或相同，即：a具有属性Pl，b也具有属性Pl；a具有属性P2，b也具有属性P2；……a具有属性Pn，b也具有属性Pn。且发现a具有属性Pn+1，则当n足够大时，可归纳出：b也具有属性Pn+1这一新知识。38③类比归纳设A，B分别是两类事物的集合：A={a1，a2，…}B={b1，b2，…}并设ai与bi总是成对地出现，且当ai有属性P时，bi就有属性Q与之对应，即P（ai）→Q（bi）i=1，2，…则当A与B中有一对新元素出现时（设为A中的，及B中的），若已知有属性P，就可得出有属性Q，即39④逆推理归纳一种由结论成立而推出前提以某种置信度成立的归纳方法。日常生活及科学研究中经常使用这种方法进行归纳推理。一般模式是：(a)若H为真时，则H→E必为真或以置信度cf1成立。(b)观察到E成立或以置信度cf2成立。(c)则H以某种置信度(cf)成立。40（2）归纳学习方法●归纳学习是应用归纳推理进行学习的一类方法，按其有无教师指导可分为示例学习及观察与发现学习。●示例学习●观察与发现学习41示例学习●示例学习（Learningfromexamples）又称为实例学习或从例子中学习，它是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的学习方法。42示例学习学习过程是：首先从示例空间（环境）中选择合适的训练示例，然后经解释归纳出一般性的知识，最后再从示例空间中选择更多的示例对它进行验证，直到得到可实用的知识为止。43示例学习的学习模型44实例学习例子训练实例集合:1.(乌鸦w1，羽毛黑);2.(乌鸦w2，羽毛浅黑);3.(麻雀w3，羽毛灰);4.(鸽子w4，羽毛白);5.(乌鸦w5，羽毛白);6.(乌鸦w6，羽毛黑)；7.(乌鸦w7，羽毛黑);8.(燕子w8，羽毛灰)–根据训练实例集合提出规则(假设）:乌鸦(x)黑（羽毛