机器学习课件

第六章

机器学习7/4/20231第六章机器学习主要内容：机器学习概述归纳学习例如学习基于决策树的归纳学习方法ID3类比学习基于范例的学习解释学习支持向量机7/4/20232学习经典定义：利用经验改善系统自身的性能[T.Mitchell,Book97]随着该领域的开展，主要做智能数据分析典型任务：预测例如：天气预报7/4/20233机器学习〔续〕数据挖掘数据库机器学习数据分析技术数据管理技术7/4/20234美国航空航天局JPL实验室的科学家在?Science?〔2001年9月〕上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的假设干年内将取得稳定而快速的开展重要性生物信息学计算金融学分子生物学行星地质学……工业过程控制机器人……遥感信息处理信息平安机器学习7/4/20235重要性：例子—网络平安入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现……对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络决策树支持向量机k近邻序列分析聚类…………7/4/20236重要性：例子—生物信息学常用技术：神经网络支持向量机隐马尔可夫模型k近邻决策树序列分析聚类…………7/4/20237重要性〔续〕机器学习在过去十年中开展极为迅速，今后会快速稳定地开展、对科学做出更大奉献的领域[E.Mjolsness&D.DesCoste,Science01]人工智能中最活泼、应用潜力最明显的领域〔之一〕[T.G.Dietterich,AIMag97]美国、欧洲各国都投入了大量人力物力大型公司如波音、微软、通用电器等都有研究课题已有一些研究成果进入产品7/4/20238机器学习角色的转变如果我们想做出重要的奉献，首先需要把握住该领域开展的脉搏机器学习现在似乎已经开展到一个新阶段机器学习起源于人工智能对人类学习能力的追求，上一阶段的研究几乎完全局限在人工智能这一领域中〔学习本身是目的〕而现在，机器学习已经开始进入了计算机科学的不同领域，甚至其他学科，成为一种支持技术、效劳技术〔学习本身是手段〕7/4/20239挑战问题(1)：泛化能力共性问题：几乎所有的领域，都希望越准越好提高泛化能力是永远的追求目前泛化能力最强的技术：支持向量机〔SVM〕产生途径：理论->实践集成学习〔ensemblelearning〕产生途径：实践->理论7/4/202310挑战问题(1)：泛化能力〔续〕第一个挑战问题：今后10年能否更“准〞？如果能，会从哪儿来？7/4/202311挑战问题(2)：速度共性问题：几乎所有的领域，都希望越快越好加快速度也是永远的追求“训练速度〞vs.“测试速度训练速度快的往往测试速度慢：k近邻测试速度快的往往训练速度慢：神经网络7/4/202312挑战问题(2)：速度〔续〕第二个挑战问题：今后10年能否更“快〞？能做到“训练快〞、“测试也快〞吗？如果能，如何做？7/4/202313挑战问题(3)：可理解性共性问题：绝大多数领域都希望有“可理解性〞例子：医疗诊断地震预测目前强大的技术几乎都是〔或根本上是〕“黑盒子〞神经网络、支持向量机、集成学习“黑盒子〞能满足需要吗？7/4/202314挑战问题(3)：可理解性〔续〕第三个挑战问题：今后10年能否产生“白盒子〞？是和“黑盒子〞完全不同的东西，还是从“黑盒子〞变出来？7/4/202315挑战问题(4)：数据利用能力传统的机器学习技术—>对有标记数据进行学习“标记〞——>事件所对应的结果共性问题：随着数据收集能力飞速提高、Internet的出现，在大多数领域中都可以很容易地获得大量未标记数据例子：医学图象分析垃圾邮件过滤没有标记的数据是没用的吗？7/4/202316挑战问题(4)：数据利用能力〔续〕共性问题：在绝大多数领域中都会遇到“坏〞数据，有时甚至只有“坏〞数据例子：海军舰队Web“坏〞数据——>大量噪音、属性缺失、不一致、……传统的“坏〞数据处理方式—>“扔掉〞“坏〞数据一点用也没有吗？7/4/202317第四个挑战问题：今后10年能否“数据通吃〞？如何“吃〞？挑战问题(4)：数据利用能力〔续〕7/4/202318挑战问题(5)：代价敏感目前的机器学习技术—>降低错误率“错误〞是没有区别的吗？把“好〞当成“坏〞把“坏〞当成“好〞共性问题：大多数领域中的错误代价都不一样例子：入侵检测癌症诊断一样吗？7/4/202319第五个挑战问题：今后10年能否“趋利避害〞？在到达较低的总错误率的根底上，如何“趋〞、如何“避〞？挑战问题(5)：代价敏感〔续〕7/4/202320挑战问题：……More……在任何一个挑战问题上取得突破性进展，都可能成为对机器学习的重要奉献7/4/2023216.1机器学习概述学习可能只是一个简单的联想过程，给定了特定的输入，就会产生特定的输出。如：狗命令“坐〞行为“坐〞7/4/202322学习的成功是多种多样的：学习识别客户的购置模式以便能检测出信用卡欺诈行为，对客户进行扼要描述以便能对市场推广活动进行定位，对网上内容进行分类并按用户兴趣自动导入数据，贷款申请人的信用打分，燃气涡轮的故障诊断等。7/4/2023236.1.1简单的学习模型

学习系统的根本结构如下图。环境学习知识库执行环境向系统的学习局部提供某些信息，学习局部利用这些信息修改知识库，以增进系统执行局部完成任务的效能，执行局部根据知识库完成任务，同时把获得的信息反响给学习局部。在具体的应用中，环境、知识库和执行局部决定了具体的工作内容，学习局部所需要解决的问题完全由上述三局部确定。7/4/202324影响学习系统设计的最重要的因素是环境向系统提供的信息。知识库里存放的是指导执行局部动作的一般原那么，但环境向学习系统提供的信息却是各种各样的。如果信息的质量比较高，与一般原那么的差异比较小，那么学习局部就比较容易处理。如果向学习系统提供的是杂乱无章的指导执行具体动作的具体信息，那么学习系统需要在获得足够数据之后，删除不必要的细节，进行总结推广，形成指导动作的一般原那么，放入知识库。这样，学习局部的任务就比较繁重，设计起来也较为困难。7/4/202325学习系统所进行的推理并不完全是可靠的，它总结出来的规那么可能正确，也可能不正确，这要通过执行效果加以检验。正确的规那么能使系统的效能提高，应予保存；不正确的规那么应予修改或从数据库中删除。知识库是影响学习系统设计的第二个因素。知识表示有多种形式，如特征向量、一阶逻辑、产生式规那么、语义网络框架等。选择表示方式时要兼顾以下4个方面：7/4/202326(1)表达能力强。例如，如果研究的是一些孤立的木块，那么可选用特征向量表示方式。用(<颜色>，<形状>，<体积>)这种形式的向量表示木块。用一阶逻辑公式描述木块之间的相互关系，如用公式表示一个红色的木块在一个绿色的木块上面。7/4/202327(2)易于推理。如，在推理过程中经常会遇到判别两种表示方式是否等价的问题。在特征向量表示方式中，解决这个问题比较容易；在一阶逻辑表示方式中，解决这个问题要花费较高的计算代价。因为学习系统通常要在大量的描述中查找，很高的计算代价会严重影响查找的范围。因此如果只研究孤立的木块而不考虑相互的位置，那么应该使用特征向量表示。7/4/202328(3)容易修改知识库学习系统的本质要求它不断地修改自己的知识库，当推广得出一般执行规那么后，要加到知识库中去。当发现某些规那么不适用时要将其删除。因此学习系统的知识表示，一般都采用明确、统一的方式，如特征向量、产生式规那么等，以利于知识库的修改。新增加的知识可能与知识库中原有的知识相矛盾，因此有必要对整个知识库作全面调整。删除某一知识也可能使许多其他知识失效，因此需要进一步作全面检查。7/4/202329(4)知识表示易于扩展随着系统学习能力的提高，单一的知识表示己经不能满足需要；一个系统可能同时使用几种知识表示方式。有时还要求系统自己能够构造出新的表示方式，以适应外界信息不断变化的需要。因此要求系统包含如何构造表示方式的元级描述。现在，人们把这种元级知识也看成是知识库的一局部。这种元级知识使学习系统的能力得到极大提高，使其能够学会更加复杂的东西，不断地扩大它的知识领域和执行能力。7/4/202330学习系统不能在全然没有任何知识的情况下凭空获取知识，每一个学习系统都要求具有某些知识以理解环境提供的信息，分析比较，作出假设，检验并修改这些假设。因此，学习系统是对现有知识的扩展和改进。7/4/2023316.1.2什么是机器学习学习是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，比现在做得更好或效率更高。例子：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的人工智能分支。1959年Samuel设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对弈中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力。7/4/202332开展分四阶段：(1)在20世纪50年代中叶到60年代中叶，属于热烈时期。在这个时期，所研究的是“没有知识〞的学习，即“无知〞学习；其研究目标是各类自组织系统和自适应系统；其主要研究方法是不断修改系统的控制参数以改进系统的执行能力，不涉及与具体任务有关的知识。指导本阶段研究的理论根底是早在20世纪40年代就开始研究的神经网络模型。这个阶段的研究导致了“模式识别〞的诞生，同时形成了两种机器学习方法——判别函数法和进化学习。Samuel的下棋程序就是使用判别函数法的典型例子。6.1.3机器学习研究概况7/4/202333(2)在20世纪60年代中叶至70年代中叶，被称为冷静时期。本阶段的研究目标是模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器内部描述。机器能够采用符号来描述概念(符号概念获取)，并提出关于学习概念的各种假设。本阶段的代表性工作神经网络学习机因理论缺陷未能到达预期效果而转入低潮。Winston的结构学习系统和HayesRoth等人的基于逻辑的归纳学习系统。7/4/202334(3)从20世纪70年代中叶至80年代中叶，称为复兴时期。在这个时期，人们从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。机器的学习过程一般都建立在大规模的知识库上，实现知识强化学习。本阶段开始把学习系统与各种应用结合起来，促进了机器学习的开展。在出现第一个专家学习系统之后，例如归约学习系统成为研究的主流，自动知识获取成为机器学习的应用研究目标。1980年，在CMU召开了第一届机器学习国际研讨会。此后，机器归纳学习进入应用。1986年，杂志MachineLearning创刊。7/4/202335(4)机器学习的最新阶段始于1986年。在这一时期，符号学习由“无知〞学习转向有专门领域知识的增长型学习，因而出现了有一定知识背景的分析学习。神经网络中的反向传播算法获得应用。基于生物发育进化论的进化学习系统和遗传算法，因吸取了归纳学习与连接机制学习的长处而受到重视。基于行为主义的强化学习系统因开展新算法和应用连接机制学习遗传算法的新成就而显示出新的生命力。数据挖掘研究的蓬勃开展。7/4/202336它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习的理论根底。结合各种学习方法的多种形式的集成学习系统研究正在兴起。机器学习与人工智能各种根底问题的统一性观点正在形成。各种学习方法的应用范围不断扩大，一局部已形成商品。数据挖掘和知识发现技术在生物医学、金融管理、商业销售等领域得到成功应用。ML进入新阶段表现在：7/4/202337机器学习的研究概况学习过程与推理过程是紧密相连的，机器学习所采用的策略可分为：机械学习示教学习类比学习例如学习学习中所用的推理越多，系统的能力就越强。

机械学习就是记忆。这种学习策略不需要任何推理过程。外界输入知识的表示方式与系统内部的表示方式完全一致，不需要任何处理与转换。7/4/202338虽然机械学习在方法上看来很简单，但由于计算机的存储容量相当大，检索速度又相当快，而且记忆精确、无丝毫误差，所以也能产生人们难以预料的效果。Samuel的下棋程序就是采用了这种机械记忆策略。为了评价棋局的优劣，他给每一个棋局都打了分，对自己有利的分数高，不利的分数低，走棋时尽量选择使自己分数高的棋局。这个程序可记住53000多个棋局及其分值，并能在对弈中不断地修改这些分值以提高自己的水平，这对于人来说是无论如何也办不到的。7/4/202339机械学习示教学习类比学习例如学习

示教学习策略:对于使用示教学习策略的系统来说，外界输入知识的表达方式与内部表达方式不完全一致，系统在接受外部知识时需要一点推理、翻译和转化工作。MYCIN，DENDRAL等专家系统在获取知识上都采用这种学习策略。类比学习系统只能得到完成类似任务的有关知识，因此，学习系统必须能够发现当前任务与任务的相似点，由此制定出完成当前任务的方案，因此，它比上述两种学习策略需要更多的推理。7/4/202340采用例如学习策略的计算机系统，事先完全没有完成任务的任何规律性的信息，所得到的只是一些具体的工作例子及工作经验。系统需要对这些例子及经验进行分析、总结和推广，得到完成任务的一般性规律，并在进一步的工作中验证或修改这些规律，因此需要的推理是几种策略中最多的此外，还有基于解释的学习、强化学习和基于神经网络的学习等。机械学习示教学习类比学习例如学习

7/4/202341归纳学习归纳学习人类智能的重要表达；机器学习的核心技术之一；从提供的例如中抽象出结论的知识获取过程。依据：具体的例如；目标：一般性推论；能解释例如；预见新事实。例如一般性推论新的事实归纳演绎7/4/2023421.归纳学习的模式和规那么一般的归纳推理结论只是保假的。从相同的实例集合中，可以提出不同的理论来解释它，应按某一标准选取最好的作为学习结果。人类知识的增长主要得益于归纳学习方法。虽然归纳得出的新知识不像演绎推理结论那样可靠，但存在很强的可证伪性，对于认识的开展和完善具有重要的启发意义。归纳学习(inductionlearning)是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为例如学习和观察与发现学习。前者属于有师学习，后者属于无师学习。7/4/202343(1)归纳学习的模式给定：①观察陈述F，用以表示有关某些对象、状态、过程等的特定知识；②假定的初始归纳断言(可能为空)；③背景知识，用于定义有关观察陈述、候选归纳断言以及任何相关问题领域知识、假设和约束，其中包括能够刻画所求归纳断言的性质的优先准那么。求：归纳断言H，能重言蕴涵或弱蕴涵观察陈述，并满足背景知识。7/4/202344假设H永真蕴涵事实F，说明F是H的逻辑推理，那么有：H∣>F(读作H特殊化为F)或F∣<H(读作F一般化为H)这里，从H推导到F是演绎推理，因此是保真的；而从事实F推导出假设H是归纳推理，因此不是保真的，而是保假的。7/4/202345归纳学习系统的模型如下图。实验规划过程通过对实例空间的搜索完成实例选择，并将这些选中的活泼实例提交给解释过程。解释过程对实例加以适当转换，把活泼实例变换为规那么空间中的特定概念，以引导规那么空间的搜索。归纳学习系统模型

实例空间规则空间规划过程解释过程7/4/202346(2)归纳概括规那么归纳推理过程中，要引用如下归纳规那么：选择性概括规那么构造性概括规那么令D1,D2分别为归纳前后的知识描述，那么归纳是D1=>D2。如果D2中所有描述根本单元(如谓词子句的谓词)都是D1中的，只是对D1中根本单元有所取舍，或改变连接关系，那么就是选择性概括。如果D2中有新的描述根本单元(如反映D1各单元间的某种关系的新单元)，那么就称之为构造性概括。7/4/2023472.归纳学习方法(1)例如学习例如学习(learningfromexamples)，它是通过环境中假设干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。外部环境提供的是一组例子(正例和反例)，它们是一组特殊的知识，每一个例子表达了仅适用于该例子的知识。例如学习就是要从这些特殊知识中归纳出适用于更大范围的一般性知识，以覆盖所有的正例并排除所有反例。如，如果用一批动物作为例如，并且告诉学习系统哪一个动物是“马〞，哪一个动物不是。当例如足够多时，学习系统就能概括出关于“马〞的概念模型，使自己能够识别马，并且能将马与其他动物区别开来。归纳学习的方法7/4/202348(2)观察发现学习观察发现学习(learningfromobservationanddiscovery)，其目标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习分为概念聚类机器发现前者用于对事例进行聚类，形成概念描述；后者用于发现规律，产生定律或规那么。1〕概念聚类——根本思想是把事例按照一定的方式和准那么分组，如划分为不同的类或不同的层次等，使不同的组代表不同的概念，并且对每一个组进行特征概括，得到一个概念的语义符号描述。如，对如下事例：7/4/202349喜鹊、麻雀、布谷鸟、乌鸦、鸡、鸭、鹅……可根据它们是否家养分为如下两类：鸟={喜鹊，麻雀，布谷鸟，乌鸦……}家禽={鸡，鸭，鹅，…}这里，“鸟〞和“家禽〞就是由分类得到的新概念，而且根据相应动物的特征还可得知：“鸟有羽毛、有翅膀、会飞、会叫、野生〞“家禽有羽毛、有翅膀、不会飞、会叫、家养〞如果把它们的共同特性抽取出来，就可进一步形成“鸟类〞的概念。7/4/2023502〕机器发现机器发现是指从观察事例或经验数据中归纳出规律或规那么的学习方法。可分为：经验发现知识发现前者是指从经验数据中发现规律和定律，后者是指从已观察的事例中发现新的知识。7/4/202351例如学习和ID3教学目的：掌握例如学习的根本策略；理解构造决策树法ID3；主要内容：例如学习的根本概念3种例如学习策略：①逐步泛化的学习策略；②逐步特化的学习策略；③双向学习策略；基于决策树的归纳学习方法ID37/4/202352教学要求：掌握主要内容：理解例子空间和假设空间的概念及其关系；理解泛化和特化的概念以及与搜索的关系；掌握例如学习的三种根本策略。例如学习7/4/202353例如学习任务：从一系列例如出发：正例；反例；生成一个反映这些例如本质的定义〔概念描述〕：覆盖所有的正例，而不包含任何反例；可用来指导对新例子的分类识别；例如概念描述解描述例如学习7/4/2023541、概念描述的搜索和获取例子空间和假设空间例子空间：所有可能的正例、反例构成的空间；假设空间〔概念空间〕：所有可能的假设〔概念描述〕构成的空间；假设空间中每一假设都对应于例子空间中一个子集子集中的例子均是该假设的例子；假设空间例子空间假设A假设B例子1例子n...例如学习7/4/2023551、概念描述的搜索和获取假设的泛化和特化：D1对应例子集是D2对应例子集的子集；D2比D1泛化；D1比D2特化；假设空间中假设间的泛化关系：反对称：

D2比D1泛化、且D1比D2泛化，那么D1=D2；可传递：D3比D2泛化、且D2比D1泛化，那么D3比D1泛化；假设空间假设D1假设D2例子空间D2例子集D1例子集假设空间假设D1假设D2例如学习7/4/2023561、概念描述的搜索和获取例1：病态细胞的分类识别〔找到病态细胞的概念〕每个细胞由2个细胞体组成；每个细胞体具有3个属性──胞核数(1-2)，尾巴数(1-2)及染色状〔浅或深〕；细胞P1,P2,P3有病状X；N1,N2是正常细胞；P1+P2+N1-P3+N2-例如学习7/4/2023571、概念描述的搜索和获取例1：病态细胞的分类识别细胞体——3元组〔核数、尾数、染色状〕；细胞——2个细胞体3元组组成的集合；细胞P1表示为{(2,2,深)(1,1,浅)}例子空间由P1,P2,P3,N1,N2组成；P1,P2,P3为正例；N1,N2为反例；P1+P2+N1-P3+N2-学习任务从例子空间中归纳出有病状X的细胞概念描述

例如学习7/4/2023581、概念描述的搜索和获取例1：病态细胞的分类识别假设空间表示为假设的集合；假设不必给每个特性〔属性〕都指明应取值：假设a：{(2,?,?)(?,1,深)}，表示：如果：细胞中一个细胞体有2个胞核；另一个有1个尾巴，且染色是深的；那么：该细胞有病症X。“?〞指相应的属性对病细胞的判断是无关紧要；a例如学习7/4/2023591、概念描述的搜索和获取例1：病态细胞的分类识别假设空间表示为假设的集合；假设不必给每个特性〔属性〕都指明应取值：假设a：{(2,?,?)(?,1,深)}假设b：{(2,?,?)(?,?,深)}覆盖更多的例子ab特

化泛

化假设b比假设a泛化假设a比假设b特化例如学习7/4/202360完全的假设空间底层假设⑴最特化〔具体〕的概念描述；⑵所有特性都给定特性值；⑶对应于例子空间中的一个例子；顶层假设⑴最泛化的概念描述；⑵不指定任何具体的特性值；⑶表示为{(???)，(???)}；特化范化例如学习7/4/2023611、概念描述的搜索和获取例如学习的过程〔T.Mitchell,1982〕：在假设空间中搜索的过程。学习过程中假设空间可以动态扩展；假设空间假设D1假设D2例子空间D2例子集D1例子集获取、修正指导、预测例如学习7/4/2023621、概念描述的搜索和获取假设空间中的搜索方法①特化搜索从最泛化的假设〔概念描述〕出发；每次取用一个新的例子，产生一些特化的描述；直到产生出足够特化的解描述；②泛化搜索从最特化的假设〔例子空间中的一个正例〕开始；每次取用一个新的例子，产生一些泛化的描述；直到产生出足够泛化的解描述。例如学习7/4/2023631、概念描述的搜索和获取假设空间中的搜索方法①特化搜索②泛化搜索大多数例如学习方法都采用这二种方法或这二个方法的结合。任何的例如学习的过程都可以看成假设空间中的搜索过程，不同的搜索方式对应于不同的学习策略：①逐步泛化的学习策略——自底向上的泛化搜索；②逐步特化的学习策略——自顶向下的特化搜索；③双向学习策略——双向搜索。例如学习7/4/2023642、逐步泛化的学习策略采用宽度优先、自底向上的泛化搜索方式；根本策略：⑴从第一个正例出发，作为初始假设；⑵遇见正例就泛化某些假设以保证假设的完全描述性〔覆盖所有正例〕；⑶遇见反例那么删去某些假设以保证假设的一致描述性〔不覆盖所有反例〕；直至得到一个既完全又一致的解描述(假设)为止；解描述作为学习系统获得的新知识，满足给定例子集的概念定义。例如学习7/4/2023652、逐步泛化的学习策略采用宽度优先、自底向上的泛化搜索方式：⑴将正例P1作为初始假设H1初始假设H1是最特化的假设；只覆盖了一个正例P1；P1+P2+N1-P3+N2-宽度优先自底向上例如学习7/4/2023662、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑵取出下一个正例P2由于初始假设H1不能覆盖P2；建立比H1泛化的假设,使之能同时覆盖H1和P2；初始假设H1P2+相同特性(2,?,?)相同特性(1,?,?)假设H2相同特性(?,1,浅)相同特性(?,2,深)假设H3例如学习7/4/2023672、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑵取出下一个正例P2正例P2指导系统生成泛化的假设H2和H3；采用“最低限度的泛化〞的原那么新的假设刚好覆盖现有的“假设/例子〞，如，H2和H3刚好覆盖H1/P2；初始假设H1P2+假设H2假设H3例如学习7/4/2023682、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑶取出下一个反例N1反例用来删除过于泛化的假设；假设H2覆盖了反例N1；假设H2是过于泛化的假设，应该剪去；初始假设H1假设H2假设H3反例N1-细胞体1(2,?,?)细胞体2(1,?,?)例如学习7/4/2023692、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑷取出下一个正例P3由于假设H3不能覆盖P3；建立比H3泛化的假设,使之能同时覆盖H3和P3；初始假设H1假设H3P3+相同特性(?,2,?)相同特性(?,1,?)假设H4例如学习7/4/2023702、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑷取出下一个正例P3由于假设H3不能覆盖P3；建立比H3泛化的假设,使之能同时覆盖H3和P3初始假设H1假设H3P3+相同特性(?,?,浅)相同特性(?,?,深)假设H4假设H5例如学习7/4/2023712、逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：⑸取出下一个反例N2反例用来删除过于泛化的假设；假设H4覆盖了反例N2；假设H4是过于泛化的假设，应该剪去；假设H5不覆盖反例N1，N2。细胞体1(?,2,?)细胞体2(?,1,?)初始假设H1假设H3假设H4假设H5N2-反例N1-例如学习7/4/202372P1+P2+N1-P3+N2-初始假设H1假设H2假设H3例如学习7/4/202373P1+P2+N1-P3+N2-假设H5假设H3假设H4初始假设H1假设H5足够泛化的解描述例如学习7/4/2023742、逐步泛化的学习策略符号说明：H：当前的假设集，初始值为{第一个观察的正例}；N：已观察到的反例集，初始值为空集{}；i：观察的下一个例子；算法描述：IFi是正例THEN{⑴对每一个不覆盖i的假设h∈H,用能覆盖i和h〔假设/例子〕，且泛化程度又最低的假设〔可以有多个〕代替h；⑵移去H中能覆盖已往观察到的反例n∈N的假设(以保证一致性)；}ELSE//i是反例{⑴把i参加到反例集N；⑵移去H中能覆盖i的假设；}例如学习7/4/2023751、概念描述的搜索和获取例如学习的过程〔T.Mitchell,1982〕：在假设空间中搜索的过程。假设空间中的搜索方法①泛化搜索从最特化的假设〔例子空间中的一个正例〕开始；每次取用一个新的例子，产生一些泛化的描述；直到产生出足够泛化的解描述。②特化搜索从最泛化的假设〔概念描述〕出发；每次取用一个新的例子，产生一些特化的描述；直到产生出足够特化的解描述；例如学习7/4/2023763、逐步特化的学习策略“泛化策略〞：采用宽度优先、自底向上的搜索方式；“特化策略〞：采用宽度优先、自顶向下的搜索方式；【相同点】新例子的参加会导致新假设的增加和已存在假设的删除；P1+N1-N2-P2+例如学习7/4/2023773、逐步特化的学习策略正例和反例所起的作用与泛化策略相反：反例——生成一些特化假设；*采用保守的原那么——最低限度的特化：-新的假设在覆盖已有正例的同时只是刚好能排斥反例；正例——剪裁过于特化的假设。7/4/2023783、逐步特化的学习策略采用宽度优先、自顶向下的搜索方式；⑴最泛化的假设H1={(?,?,?),(?,?,?)}细胞简化成2个细胞体,不附有任何的属性；⑵取出第一个正例P1H1正确地覆盖了正例P1，不必修改；正例P1将放入正例集，备用；初始假设H1P1+例如学习7/4/2023793、逐步特化的学习策略采用宽度优先、自顶向下的搜索方式；⑶取出下一个反例N1初始假设H1过于泛化,覆盖了这个反例N1；假设H1必须特化，至少得到特化假设H2、H3；假设H2、H3排斥反例N1；系统是依靠反例来生成一些特化假设；“最低限度的特化〞保守的原那么：特化的假设在覆盖已有正例的同时只是刚好能排斥反例。N1-初始假设H1假设H2假设H3P1+覆盖正例P1例如学习7/4/2023803、逐步特化的学习策略采用宽度优先、自顶向下的搜索方式；⑷取出下一个反例N2假设H2、H3过于泛化,覆盖了这个反例N2；假设H2、H3必须特化；初始假设H1假设H2假设H3P1+-N2假设H4假设H5例如学习7/4/2023813、逐步特化的学习策略采用宽度优先、自顶向下的搜索方式；⑸取出下一个正例P2正例P2排斥了假设H4；初始假设H1假设H2假设H3假设H4假设H5P2+假设H5是最后得到的概念描述——解描述例如学习7/4/2023823、逐步特化的学习策略符号说明：H：当前的假设集，初始值为{最泛化的假设}；P：已观察到的正例集，初始值为空集{}；i：观察的下一个例子；算法描述：IFi是反例THEN{⑴对每一个覆盖i的假设h∈H,用可被h覆盖但排斥i，且特化程度最低的假设代替h；⑵移去H中不覆盖已往观察到的正例p∈P的假设；}ELSE//i是正例{⑴把i参加到正例集P；⑵移去H中所有不覆盖i的假设；}例如学习7/4/202383泛化策略：采用自底向上的搜索假设空间的方式；从第一个正例表示的最特化的假设开始；系统依靠正例生成泛化的假设；反例用来剪裁过于泛化的假设；解描述——泛化程度最低；特化策略：采用自顶向下的搜索假设空间的方式；从最泛化的假设开始；系统依靠反例生成特化的假设；正例用来剪裁过于特化的假设；解描述——特化程度最低；如果给出充分多的例子,那么二者的结果就可能会是相同的概念描述。

例如学习7/4/2023844、双向学习策略结合“泛化策略〞和“特化策略〞,同时从2个方向搜索假设空间。版本空间法(VersionSpace〕假设集S——泛化搜索的假设空间；遇见一个新的正例时，如未被Ｓ集包含，那么在该集中进行泛化搜索；假设集G——特化搜索的假设空间；一个新的反例产生时，如被Ｇ集包含，那么在该集中进行特化搜索;例如学习7/4/202385完全的假设空间假设集SS不能覆盖新的正例i那么在S中进行泛化搜索假设集GG能覆盖新的反例i，那么在G中进行特化搜索特化搜索范化搜索当S、G合一时，双向学习结束例如学习7/4/2023864、双向学习策略结合“泛化策略〞和“特化策略〞,同时从2个方向搜索假设空间。版本空间法(VersionSpace〕假设集S——泛化搜索的假设空间；期望获取的最终解描述下界；假设集G——特化搜索的假设空间；期望获取的最终解描述上界；例如学习7/4/2023874、双向学习策略版本空间法(VersionSpace〕优点：⑴系统不必保存正例〔特化策略〕和反例〔泛化策略〕：S蕴涵了已取用的所有正例，删除G中过于特化的假设；G蕴涵了对所有已取用反例的排斥，删除S中过于泛化的假设。⑵系统知道何时推理任务完成；当S、G合一时，双向学习结束；“泛化〞和“特化〞策略只能搜索完所有例如；例如学习7/4/202388输入第一个正例P

初始化S={P}初始化G={最泛化的假设}例如i没有考察例如i为正例保存G中覆盖i的假设S中不覆盖i的假设泛化，并且泛化的假设能被G所蕴涵删除S中蕴涵其他假设的假设是保存S中不覆盖i的假设G中覆盖i的假设特化，并且特化的假设能蕴涵S中相应假设删除G中被其他假设蕴涵的假设否版本空间法(VersionSpace〕蕴涵其他假设的假设泛化程度并非最低的假设〔最低泛化的原那么〕被其他假设蕴涵的假设特化程度并非最低的假设〔最低特化的原那么〕7/4/202389P1+P2+N1-P3+N2-S1G1输入第一个正例P1

7/4/202390P2+S1G1正例P2

保存G中覆盖i的假设S中不覆盖i的假设泛化，并且泛化的假设能被G所蕴涵删除S中蕴涵其他假设的假设S2G27/4/202391反例N1

S2G2N1保存S中不覆盖i的假设G中覆盖i的假设特化，并且特化的假设能蕴涵S中相应假设删除G中可以被其他假设蕴含的假设G3S3S3和G3中的假设构成了满足正、反例的概念描述进一步的“泛化〞、“特化〞搜索只能在S3和G3之间进行例如足够多时，S3和G3就会合而为一7/4/2023926.3基于决策树的归纳学习方法教学要求：理解主要内容：掌握决策树的概念；理解决策树的构造方法。7/4/202393决策树学习——归纳学习方法的一个变种；任务：从大的已经分类的例子集，归纳分类概念；例子表示为一组“属性-值〞；每一个例子用相同的一组属性来表示；每一个属性又有自身的属性值集；6.3基于决策树的归纳学习方法7/4/202394编号属性分类天气温度湿度风况1晴热大无N2晴热大有N3多云热大无P4雨中大无P5雨冷正常无P6雨冷正常有N7多云冷正常有P8晴中大无N9晴冷正常无P10雨中正常无P11晴中正常有P12多云中大有P13多云热正常无P14雨中大有N7/4/202395决策树学习——归纳学习方法的一个变种；任务：从大的已经分类的例子集，归纳分类概念；例子表示为一组“属性-值〞；每一个例子用相同的一组属性来表示；每一个属性又有自身的属性值集；ID3算法，昆兰〔，1986〕；输入：⑴描述类别例子的列表；⑵例子由预先定义的“属性-值〞对来表示；结果：决策树——可以正确地区分所有给定例子的类别；数学根底使用信息论指导决策树构造，提高决策树的工作效率6.3基于决策树的归纳学习方法7/4/202396决策树学习——归纳学习方法的一个变种；预先定义一组属性及其可取值：高度{高，矮}；发色{黑色,红色，金色}；眼睛{兰色，棕色}；人分为两类：“＋〞“－〞高度发色眼睛类别

─────────────────

矮黑色兰色－

高黑色兰色－

矮金色兰色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色兰色＋

高红色兰色＋6.3基于决策树的归纳学习方法7/4/202397决策树学习——归纳学习方法的一个变种；选取“发色〞为树的根节点：3个属性值——3个对象子集发色黑色红色金色｛矮、黑色、蓝色:－｝｛高、黑色、蓝色:－｝｛高、黑色、棕色:－｝｛高、红色、蓝色:＋｝｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝6.3基于决策树的归纳学习方法7/4/202398决策树学习——归纳学习方法的一个变种；按属性“眼睛〞划分“金色〞分支：2个属性值——2个对象子集发色黑色红色金色｛矮、黑色、蓝色:－｝｛高、黑色、蓝色:－｝｛高、黑色、棕色:－｝｛高、红色、蓝色:＋｝｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝｛矮、金色、蓝色:＋｝｛高、金色、蓝色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝眼睛蓝色棕色二级决策树

所有叶节点的对象子集只含同一类对象6.3基于决策树的归纳学习方法7/4/202399决策树学习——归纳学习方法的一个变种；发色黑色红色金色｛矮、黑色、蓝色:－｝｛高、黑色、蓝色:－｝｛高、黑色、棕色:－｝｛高、红色、蓝色:＋｝｛矮、金色、蓝色:＋｝｛高、金色、蓝色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝眼睛蓝色棕色二级决策树

非叶节点对应一个需测试的属性

每个分叉就是该属性可能的取值

叶节点指示同类例子的集合

6.3基于决策树的归纳学习方法7/4/2023100决策树学习——归纳学习方法的一个变种；发色黑色红色金色｛矮、黑色、蓝色:－｝｛高、黑色、蓝色:－｝｛高、黑色、棕色:－｝｛高、红色、蓝色:＋｝｛矮、金色、蓝色:＋｝｛高、金色、蓝色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝二级决策树生成

＋＋－－眼睛棕色蓝色6.3基于决策树的归纳学习方法叶节点指示同类例子的集合

可以用相应的类别名〔本例中的“+〞和“-〞〕取代各叶节点7/4/2023101决策树学习——归纳学习方法的一个变种；发色黑色红色金色｛高、金色、蓝色｝对象所属类的判别＋＋－－眼睛棕色蓝色只测试了两个属性＋6.3基于决策树的归纳学习方法7/4/2023102决策树学习——归纳学习方法的一个变种；预先定义一组属性及其可取值：高度{高，矮}；发色{黑色,红色，金色}；眼睛{兰色，棕色}；人分为两类：“＋〞“－〞高度发色眼睛类别

─────────────────

矮黑色兰色－

高黑色兰色－

矮金色兰色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色兰色＋

高红色兰色＋6.3基于决策树的归纳学习方法高度眼睛头发7/4/2023103决策树学习——归纳学习方法的一个变种；高度高矮＋－－眼睛棕色蓝色头发黑色红色金色＋眼睛棕色蓝色－头发－黑色红色＋｛高、金色、蓝色｝对象所属类的判别测试了3个属性＋6.3基于决策树的归纳学习方法7/4/20231046.3基于决策树的归纳学习方法面临的问题：如何选择属性，使生成的决策树最小的？ID3算法采用了香农〔Shannon〕信息论：目标：使分类时平均的测试次数最小；给定的例子集C：M(C)：从C判别一个对象的类属所要求的总的期望信息量；人分类问题：M(C)=-P+log2P+-P-log2P-“+〞类消息的概率P+；“-〞类消息的概率P-；对于上述例子，C集有８个例子，3个为“+〞，5为"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits概率近似地表示为相对频率P+=3/8高度发色眼睛类别

─────────────────

矮黑色兰色－

高黑色兰色－

矮金色兰色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色兰色＋

高红色兰色＋7/4/2023105A为构造C的决策树时下一个可能选取的属性；{A1,A2,..,An}为属性A的值且是互斥的；属性A将集合C划分为假设n个子集合；{C1，C2，...，Cn}M(Ci)是子集Ci判别一个对象的类属所要求的总的期望信息量；B(C,A)：属性A构造决策树后需要的期望信息量：∑(集合C中A值为Ai的概率P(Ai))*M(Ci)属性AA1A2AnC1C2CnM(C1)M(C2)M(Cn)P(A1)P(A2)P(An)6.3基于决策树的归纳学习方法7/4/2023106决策树学习——归纳学习方法的一个变种；M(C)＝∑(-Pilog2Pi)C判别一个对象的类属所要求的总的期望信息量；M(Ci)Ci判别一个对象的类属所要求的总的期望信息量；B(C,A)＝∑(C中A值为Ai的概率P(Ai))*M(Ci)

C按属性A构造决策树后需要的期望信息量；M(C)-B(C,A)越大说明测试这个属性A所能传递的信息量越大；判别的速度也就越快；选择M(C)-B(C,A)最大的属性A生成决策树；6.3基于决策树的归纳学习方法7/4/20231076.3基于决策树的归纳学习方法面临的问题：如何选择属性，使生成的决策树最小的？ID3算法采用了香农〔Shannon〕信息论：目标：使分类时平均的测试次数最小；给定的例子集C：M(C)：从C判别一个对象的类属所要求的总的期望信息量；人分类问题：M(C)=-P+log2P+-P-log2P-“+〞类消息的概率P+；“-〞类消息的概率P-；对于上述例子，C集有８个例子，3个为“+〞，5为"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits概率近似地表示为相对频率P+=3/8高度发色眼睛类别

─────────────────

矮黑色兰色－

高黑色兰色－

矮金色兰色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色兰色＋

高红色兰色＋7/4/20231086.3基于决策树的归纳学习方法决策树学习——归纳学习方法的一个变种；选取“高度〞为树的根节点：2个属性值——2个对象子集高度高矮{高，金，棕：－}{高，红，蓝：＋}{高，黑，蓝：－}{高，金，蓝：＋}{高，黑，棕：－}

｛矮、金、蓝:＋｝｛矮、黑、棕:－｝｛矮、金、棕:－｝“高〞的分支的所需期望信息量为：M(C高)

-〔2/5〕log2〔2/5〕-〔3/5〕log2〔3/5〕=0.971bitsP+

=2/5P-=3/5“矮〞的分支的所需期望信息量为：M(C矮)

-〔1/3〕log2〔1/3〕-〔2/3〕log2〔2/3〕=0.918bitsP+

=1/3P-

=2/3C以属性“高度〞作划分后进一步判别所需的期望信息量为：

B(C,“高度〞)=5/8×M(C高)+3/8×M(C矮)=0.951P(高)

=5/8P(矮)

=3/8M(C高)M(C矮)7/4/20231096.2.2决策树构造法以属性“高度〞作划分后进一步判别所需的期望信息量为：

B(C,"高度")=5/8×0.971+3/8×0.918=0.951bits测试这属性“高度〞传递的信息为：

M(C)-B(C,"高度")=0.954-0.951=0.003bits对于上述例子，C集有８个例子，3个为“+〞，5为"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits属性“头发〞作为根节点构造决策树7/4/2023110发色黑色红色金色｛矮、黑色、蓝色:－｝｛高、黑色、蓝色:－｝｛高、黑色、棕色:－｝｛高、红色、蓝色:＋｝｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝-1×log21

=0-1×log21

=0以属性“头发〞作划分后进一步判别所需的期望信息量为：

B(C,“头发〞)=3/8×0+1/8×0+4/8×1=0.5bits-1/2×log21/2

-1/2×log21/2

=1测试这属性“头发〞传递的信息为：

M(C)-B(C,"头发")=0.954-0.5=0.454bits6.3基于决策树的归纳学习方法M(C黑)M(C红)M(C金)P(黑)

=3/8P(红)

=1/8P(黑)

=4/8M(C黑)=0M(C红)=0M(C金)=17/4/2023111决策树构造法测试这属性“高度〞传递的信息为：

M(C)-B(C,"高度")=0.954-0.951=0.003bits测试这属性“头发〞传递的信息为：

M(C)-B(C,"头发")=0.954-0.5=0.454bits测试这属性“眼睛〞传递的信息为：

M(C)-B(C,"眼睛")=0.347bits对于上述例子，C集有８个例子，3个为“+〞，5为"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits高度发色眼睛类别

─────────────────

矮黑色兰色－

高黑色兰色－

矮金色兰色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色兰色＋

高红色兰色＋7/4/2023112决策树学习——归纳学习方法的一个变种；发色黑色红色金色＋－6.3基于决策树的归纳学习方法｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝7/4/2023113｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝C1集有4个例子，2个为“+〞，2为“-〞，那么

M(C1)=-〔2/4〕log2〔2/4〕-〔2/4〕log2〔2/4〕=1bits＋－眼睛棕色蓝色-1×log21

=0-1×log21

=0M(C蓝)=0M(C棕)=0P(蓝)

=1/2P(棕)

=1/2以属性“眼睛〞作划分后进一步判别所需的期望信息量为：

B(C1,“眼睛〞)=1/2×0+1/2×0=0bits测试这属性“眼睛〞传递的信息为：

M(C1)-B(C1,“眼睛")=1-0=1bits7/4/2023114｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝C1集有4个例子，2个为“+〞，2为“-〞，那么

M(C1)=-〔2/4〕log2〔2/4〕-〔2/4〕log2〔2/4〕=1bits高度矮高-1/2×log21/2-1/2×log21/2

=1M(C矮)=1M(C高)=1以属性“高度〞作划分后进一步判别所需的期望信息量为：

B(C1,“高度〞)=1/2×1+1/2×1=1bits｛矮、金色、蓝色:＋｝｛矮、金色、棕色:－｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝-1/2×log21/2-1/2×log21/2

=1P(矮)

=1/2P(高)

=1/2测试这属性“高度〞传递的信息为：

M(C1)-B(C1,“高度")=1-1=0bits7/4/2023115｛矮、金色、蓝色:＋｝｛高、金色、棕色:－｝｛高、金色、蓝色:＋｝｛矮、金色、棕色:－｝决策树学习——归纳学习方法的一个变种；发色黑色红色金色＋＋－－眼睛棕色蓝色6.3基于决策树的归纳学习方法测试这属性“高度〞传递的信息为：

M(C1)-B(C1,“高度")=1-1=0bits测试这属性“眼睛〞传递的信息为：

M(C1)-B(C1,“眼睛")=1-0=1bits7/4/2023116编号属性分类天气温度湿度风况1晴热大无N2晴热大有N3多云热大无P4雨中大无P5雨冷正常无P6雨冷正常有N7多云冷正常有P8晴中大无N9晴冷正常无P10雨中正常无P11晴中正常有P12多云中大有P13多云热正常无P14雨中大有N作业：构造天气状况的决策树要求：只要求写出按不同状况的根节点值的算式，不要求计算结果7/4/20231176.4类比学习类比学习(learningbyanalogy)就是通过类比，即通过对相似事物加以比较所进行的一种学习。

许多创造和发现就是通过类比学习获得的。如，卢瑟福将原子结构和太阳系进行类比，发现了原子结构；水管中的水压计算公式和电路中电压计算公式相似等等。7/4/20231181.类比推理和类比学习形式类比推理是由新情况与情况在某些方面的相似来推出它们在其他相关方面的相似。类比推理是在两个相似域之间进行的：一个是已经认识的域，它包括过去曾经解决过且与当前问题类似的问题以及相关知识，称为源域，记为S；另一个是当前尚未完全认识的域，它是待解决的新问题，称为目标域，记为T；类比推理的目的是从S中选出与当前问题最近似的问题及其求解方法以求解决当前的问题，或者建立起目标域中已有命题间的联系，形成新知识。7/4/2023119设用S1与T1分别表示S与T中的某一情况，且S1与T1相似；再假设S2与S1相关，那么由类比推理可推出T中的T2，且T2与S2相似。其推理过程如下：(1)回忆与联想当遇到新情况或新问题时，首先通过回忆与联想在S中找出与当前情况相似的情况，这些情况是过去已经处理过的，有现成的解决方法及相关的知识。找出的相似情况可能不只一个，可依其相似度从高至低进行排序。7/4/2023120(2)选择从找出的相似情况中选出与当前情况最相似的情况及其有关知识。在选择时，相似度越高越好，这有利于提高推理的可靠性。(3)建立对应关系在S与T的相似情况之间建立相似元素的对应关系，并建立起相应的映射。(4)转换在上一步建立的映射下，把S中的有关知识引到T中来，从而建立起求解当前问题的方法或者学习到关于T的新知识。7/4/2023121在以上每一步中都有一些具体的问题需要解决。下面对类比学习的形式加以说明：设有两个具有相同或相似性质的论域：源域S和目标域T，S中的元素a和T中的元素b具有相似的性质P，即P(a)≌P(b)，a还具有性质Q，即Q(a)。根据类比，b也具有性质Q。即：P(a)∧Q(a),P(a)├Q(b)其中，符号├表示类比推理。7/4/2023122类比学习采用类比推理，步骤：(1)找出源域与目标域的相似性质P，找出源域中另一个性质Q和性质P对元素a的关系：P(a)→Q(a)。(2)在源域中推广P和Q的关系为一般关系，即对于所有的变量x来说，存在P(x)→Q(x)。(3)从源域和目标域映射关系，得到目标域的新性质，即对于目标域的所有变量x来说，存在P(x)→Q(x)。(4)利用假言推理：P(b),P(x)→Q(x)├Q(b)最后得出b具有性质Ｑ。7/4/2023123从上述步骤可见，类比学习实际上是演绎学习和归纳学习的组合。步骤(2)是一个归纳过程，即从个别现象推断出一般规律；而步骤(4)那么是一个演绎过程，即从一般规律找出个别现象。7/4/20231242.类比学习过程与研究类型类比学习包括：(1)输入一组条件(已解决问题)和一组未完全确定的条件(新问题)。(2)对输入的两组条件，根据其描述，按某种相似性的定义寻找两者可类比的对应关系。(3)根据相似变换的方法，将已有问题的概念、特性、方法、关系等映射到新问题上，以获得待求解新问题所需的新知识。(4)对类推得到的新问题的知识进行校验。验证正确的知识存入知识库中，而暂时还无法验证的知识只能作为参考性知识，置于数据库中。7/4/2023125类比学习的研究分两类：(1)问题求解型。当求解一个新问题时，总是首先回忆一下以前是否求解过类似的问题，假设是，那么可以此为根据，通过对先前的求解过程加以适当修改，使之满足新问题的解。(2)预测推定型。它又分为两种方式。一种是传统的类比法，用来推断一个不完全确定的事物可能还具有的其他属性。设X，Y为两个事物，Pi属性(i=l，2，….，n)，那么有以下关系：另一种是因果关系型的类比，其根本问题是：因果关系S1:A→B，给定事物Ａ与Ａ’相似，那么可能有与B相似的事物B’满足因果关系：A’→B’。7/4/2023126进行类比的关键是相似性判断，而其前提是配对，两者结合起来就是匹配。实现匹配有多种形式，常用的有以下几种：(1)等价匹配：要求两个匹配对象之间具有完全相同的特性数据；(2)选择匹配：在匹配对象中选择重要特性进行匹配；(3)规那么匹配：假设两个规那么的结论局部匹配，且其前提局部也匹配，那么两规那么匹配；(4)启发式匹配：根据一定背景知识，对对象的特征进行提取，然后通过一般化操作使两个对象在更高、更抽象的层次上相同。7/4/20231276.5基于范例的推理基于范例的推理〔case-basedreasoning，CBR〕同人类的日常推理活动十分接近，它来自于人类的认知心理活动。不同于传统的基于知识系统，CBR系统所信赖的知识主要是系统所存储的相关领域中以前解决问题的具体记录。7/4/20231281.CBR系统的特点罗杰·沙克〔RogerSchank〕是CBR研究的开创者，沙克〔Schank〕指出，CBR方法研究的原始动机，主要来源于对人类推理活动中“回忆〞的重要地位的认识传统的基于知识系统〔主要指知识表示采用产生式规那么或框架架或语义网络的专家系统，ES〕存在一定的困难，如：知识获取的瓶颈问题知识库维护的困难推理链不能太长固定的求解范围7/4/2023129CBR方法在以下方面对基于规那么的系统做出了改进：以下讨论都假定非CBR知识系统的知识表示都采用产生式规那么。1.知识获取2.知识库维护3.解决问题的范围4.解质量5.求解过程7/4/20231302.CBR系统的体系结构一个CBR推理和学习过程可以分解为下面四个步骤：step1.从案例库中检索出与新案例最相似的案例或案例集；step2.把step1获得的案例〔或案例集〕中的信息和知识复用到新问题上；step3.修正所建议的解答；step4.把该次获得的经验保存起来，以备将来来使用。7/4/2023131CBR的学习方法基于范例的推理通过下面几种方法来完成它的大局部学习：新范例的积累。保存成功的和失败的新范例。建立、修改和撤消指向范例的索引路径，完善索引机制。归纳学习。7/4/2023132CBR方法的实现一般包含下面几个主要步聚：案例表示，索引和存储，检索，适应修改，评估和学习等。(1)案例表示基于案例的推理系统利用案例记录以前的问题求解的情况，应该包括与问题的解答有关的一切重要信息。从问题求解角度来看，案例应包含对问题整体情况的描述，还应包含对问题的解或解决方法的描述。所以案例可被表成一个有序对：<问题描述，解描述>。

7/4/2023133〔2〕索引案例库的索引〔indexing〕的目标是提供一种案例库的搜索机制，使得在将来的检索中能够快速找出符合需要的案例或案例集。一个案例的索引就是这个案例的重要关键字的集合，这些关键字可以将这个案例同其他案例区分开来。索引问题的主要任务包括：选择什么类型的索引、如何定义索引词汇表、如何构建索引的搜索空间等。7/4/2023134(3)案例检索检索任务开始于一个描述待求问题的新案例，利用案例库索引机制，根据相似性度量方法，在某种相似性程度阈值下，从案例库中找出一组与新案例匹配较好的旧案例，并从中选择出一个最正确的案例。检索任务的子任务包括：特性鉴别〔indentifyfeature〕，初始匹配〔initiallymatch〕，搜(search)和选择(select)。7/4/2023135(4)相似性度量相似性度量〔similaritymeasure〕在CBR系统中十分重要，适宜的度量方法可以迅速、准确地找到所需要的案例。CBR系统的相似性度量方法主要使用基于距离〔基于计算〕的方法，考虑到具体应用环境的特点扩展了的相似性度量方法和最近邻法〔NNh,thenearestneighbormethod〕。7/4/2023136(5)适应性修改适应性修改可以被简单地理解为把解决文案的一局部用其他的内容替换，或者修改整个解决方案。适应性修改可以有几种形式苛以直接向解决方案中插入一些新内容，也呆以从解决方案中删除一些内容，可以替换解决方案的某一局部内容，也可以将某一局部内容改造。但是，要使CBR系统得到足够的适应性修改知识(Adaptationknowledge)是一件十分困难的任务。7/4/2023137科洛德〔Kolodner〕提出了十种适应性修改的方法。.重新例化.参数调整.局部搜索询问/查询记忆.特殊化搜索.基于案例的替换.常识转化.模型制导的修改补.特定目的的修改和修补.推导重放上述的1至6属替换方法，7和8属于转化方法7/4/2023138(6)评估和学习评估任务需要在现实环境中应用该案例解答的结果，可以通过询问专家或在现实世界中具体执行任务来实现。这通常是CBR系统外部的一个步骤。根据应用的类型，评估结果可能需要一段时间。当某案例的评估结果没有得出时，该案例应标记为未评估案例。学习过程把新案例中有意义的局部保存到系统的知识库中。它包括从案例中选择哪种信息进行保存，以什么形式保存，为新案例建立哪些索引，如何建立这些索引，如何存储新案例等等。7/4/20231394.结论基于案例的推理是人工智能领域中较新出现的一种重要的基于知识的问题求解和学习方法。作为一种基于经验的问题求解技术，基于案例的推理〔CBR〕可以理解为修改旧的解决方案满足新的需要；使用旧案例解释新情况、评价新方案、构造新问题的解答。学习是CBR推理行为的副产品，它获得过去的经验并在以后的推理中能够回忆起来，这样它的推理能力和效率都能得到提高。基于案例的推理系统的推理质量取决它具有的经验，即在那些旧经验的根底上理解新情况的能力、修改的能力、以及评价和改错的能力。基于案例的推理程序的主要过程是案例存储、检索、修改及审查。7/4/20231406.6解释学习归纳学习基于训练数据中的规律来泛化：分析一组正例的共性，鉴别与反例的差异；概念描述：概括所有正例〔完全性〕；排除任何反例〔一致性〕；基于相似性的学习：依据——训练数据的相似性；⑴问题域背景知识约束作用有限；⑵大量正、反例增加归纳学习过程的计算复杂度；数据密集型学习方法7/4/20231416.6解释学习基于解释的学习〔Explanation-BasedLearning〕20世纪80年代中期兴起的新型机器学习方法；根本方法：⑴应用领域知识建立对1个训练实例的解释；⑵训练实例的解释泛化为目标概念不是泛化训练实例主要内容：6.6.2基于解释的泛化Explanation-BasedGeneralization，EBG；Mitchelletal.1986；基于解释的学习〔EBL〕的典型方法；逆向演绎推理7/4/20231426.6.2基于解释的泛化〔EBG〕EBG