人工智能 第5章 机器学习

1、第5章 机器学习,2020/6/28,人工智能,2,学习能力是人类智能的根本特征。人类通过学习来提高和改进自己的能力。学习的基本机制是把一种情况下成功的表现行为转移到另一种类似的新情况中。人的认识能力和智慧才能就是在毕生的学习中逐步形成、发展和完善。任何自然的智能系统都具备学习的能力。 机器学习是继专家系统之后人工智能应用的又一重要研究领域。本章主要介绍机器学习的有关知识及其主要的几种学习方法。,2020/6/28,人工智能,3,5.1 机器学习概述 5.2 机械学习 5.3 归纳学习 5.4 类比学习 5.5 解释学习 5.6 强化学习 5.7 知识发现,本章主要内容：,2020/6/28,

2、人工智能,4,5.1 机器学习概述,什么是学习？ 学习是人类具有的一种重要智能行为，但究竟什么是学习，长期以来却众说纷纭。 关于“学习”这一概念的主要观点： 学习是系统改进其性能的过程。这是西蒙的观点。 西蒙的观点：学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。 学习是获取知识的过程。这是从事专家系统研究的人们的观点。 学习是技能的获取。这是心理学家的观点。 学习是事物规律的发现过程。,2020/6/28,人工智能,5,基本的学习形式有2种： （1）知识获取和技能求精。 例如，我们说某人学过物理。我们的意思是，此人

3、已经掌握了有关物理学的基本概念，并且理解其含义，同时还懂得这些概念之间以及它们与物理世界之间的关系。 一般地，知识获取可看作学习新的符号信息，而这些符号信息是以有效方式与应用这种信息的能力相适应的。 （2）第二类学习形式是通过实践逐步改进机制和认知技能。 学习的很多过程都是由改进所学的技能组成。这些技能包括意识的或者机制的协调，而这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。例如骑自行车或弹钢琴等等。 知识获取的本质可能是一个自觉的过程，其结果产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复实践来实现的。人类的学习一般表现为这两种活动的结合。,2020/6/28,人

4、工智能,6,5.1.1 机器学习的定义,至今，还没有统一的“机器学习”定义，而且也很难给出一个公认的和准确的定义。 一般认为机器学习是研究如何使用机器来模拟人类学习活动的一门学科。 更为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。 最早的具有学习能力的程序： 1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。,2020/6/28,人工智能,7,5.1.2 机器学习的发展史,机器学习的发展过程大体上可

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

6、至80年代中叶，称为复兴时期。 在这个时期，人们从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。 1980年,在美国召开了第一届国际机器学习研讨会;1984年,机器学习杂志问世。 我国于1987年召开了第一届全国机器学习研讨会;1989年成立了以中国科技大学蔡庆生教授为理事长的理事会。 4、机器学习的最新阶段始于1986年。 一方面，由于神经网络研究的重新兴起，另一方面，对实验研究和应用研究得到前所未有的重视。我国的机器学习研究开始进入稳步发展和逐渐繁荣的新时期。,2020/6/28,人工智能,9,机器学习、知识发现与数据挖掘,知识发现(Knowledge Discover

7、ing in Database)与数据挖掘(Data Mining)是人工智能、机器学习 (Machine Learning)与数据库技术相结合的产物。 KDD一词是在1989年于美国底特律市召开的第一届KDD国际学术会议上正式形成的。 1995年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于数据库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传开来。 数据挖掘和知识发现的研究已形成热潮，并在生物医学、金融管理、商业销售等领域得到成功应用，给机器学习注入新的活力。,2020/6/28,人工智能,10,5.1.3 机器学习系统的基本结构,环境是指系统外部信息的来源，它可以是系统的工

8、作对象，也可以包括工作对象和外界条件。 学习单元处理环境提供的信息，相当于各种学习算法。学习单元利用环境提供的信息，并与执行单元的反馈信息进行比较，获取相关知识，对知识库进行修改。 知识库用于存放由学习环节所得到的知识。知识库中知识的表示方法可以是：谓词、产生式、特征向量、神经网络等。 执行单元处理系统所面临的现实问题，即应用知识库中的知识求解问题。,机器学习系统的基本结构如图,2020/6/28,人工智能,11,影响学习系统设计的重要因素,(1) 影响学习系统设计的最重要的因素是环境向系统提供的信息。更具体地说是信息的质量。 (2) 知识库是影响学习系统设计的第二个因素。 知识的表示有多种形

9、式，在选择时要兼顾以下4个方面：,表达能力强。所选择的表示方式能很容易地表达有关的知识。 易于推理。为了使学习系统的计算代价比较低，希望知识表示方式能使推理较为容易。 容易修改知识库。学习系统的本质要求它不断地修改自己的知识库，当推广得出一般执行规则后，要加到知识库中。 知识表示易于扩展。每一个学习系统都要求具有某些知识理解环境提供的信息，分析比较，做出假设，检验并修改这些假设。因此，更确切地说，学习系统是对现有知识的扩展和改进。,2020/6/28,人工智能,12,5.1.4 机器学习的分类,按学习方法分类（温斯顿在1977年提出的分类方法） 机械式学习：机械学习就是记忆。 指导式学习：采用

10、示教式学习策略，也称为示教学习。 示例学习：通过工作例子学习。 类比学习：应用类似任务的知识求解当前问题。 解释学习：根据领域知识对当前实例分析和求解。 按学习的综合属性分类（综合考虑知识表示、推理方法、应用领域等多种因素）： 归纳学习：从个体的特征归纳出它们的共性 分析学习：从领域理论出发演绎出更有效的规则。 连接学习：人工神经网络学习 遗传学习：模拟自然界遗传与变异机制,2020/6/28,人工智能,13,5.2 机械学习,机械学习的模式 机械学习是最简单的机器学习方法。机械学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。机械学习又是最基本的学习过程。任何学习系统

11、都必须记住它们获取的知识。在机械学习系统中，知识的获取是以较为稳定和直接的方式进行的，不需要系统进行过多的加工。,2020/6/28,人工智能,14,数据化简,Lenat,Hayes Roth，和Klahr等人于1979年关于机械学习提出一种有趣的观点。他们指出，可以把机械学习看成是数据化简分级中的第一级。数据化简与计算机语言编译类似；其目的是把原始信息变成可执行的信息。在机械学习中我们只记忆计算的输入输出，忽略了计算过程，这样就把计算问题化简成存取问题。,2020/6/28,人工智能,15,机械学习的主要问题,对于机械学习，需要注意3个重要的问题：存储组织，稳定性和存储与计算之间的权衡。 （

12、1）存储组织信息：采用适当的存储方式，使检索速度尽可能地快，是机械学习中的重要问题。 （2）环境的稳定性与存储信息的适用性问题：机械学习系统必须保证所保存的信息适应于外界环境变化的需要，这也就是所谓的信息适用性问题。 （3）存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率。,2020/6/28,人工智能,16,5.3 归纳学习,归纳学习是目前研究得最多的学习方法，其学习目的是为了获得新的概念、构造新的规则或发现新的理论。这种方法对领域理论没有要求，甚至可以没有领域理论，但其需要大量的训练例子，而且归纳性能受到描述语言、概念类型、信噪比、实例空间分布、 归纳模式等的影响。

13、 （1）归纳（induction）是人类拓展认识能力的重要方法，是一种从个别到一般的，从部分到整体的推理行为。 （2）归纳推理是应用归纳方法，从足够多的具体事例中归纳出一般性知识，提取事物的一般规律；它是一种从个别到一般的推理。 （3）归纳学习（induction learning）是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察与发现学习。前者属于有师学习，后者属于无师学习。,2020/6/28,人工智能,17,5.3.1 归纳学习的模式和规则,归纳学习的模式,给定： 观察陈述（事实）F，用以表示有关某些对象、状态、过程等的特定知识； 假定的初始归纳断言（

14、可能为空），是关于目标的泛化项或泛化描述。 背景知识，用于定义有关观察陈述、候选归纳断言以及任何相关问题领域知识、假设和约束，其中包括能够刻画所求归纳断言的性质的优先准则。 求：归纳断言（假设）H，能重言蕴涵或弱蕴涵观察陈述，并满足背景知识。,2020/6/28,人工智能,18,假设H永真蕴涵事实F，说明F是H的逻辑推理，则有： H | F （读作H特殊化为F） 或 F | CTXK,(2) 放松条件： 一个事例的原因可能不止一条，当出现新的原因时，应该把新的原因包含进去。 CTX1K = (CTX1CTX2)K,2020/6/28,人工智能,20,(3) 沿概念树上溯： 设L是一结构性描述项

15、，S代表所有条件中的L值在概念分层树上最近的共同祖先，则：,(4) 形成闭合区域： 设L是一个具有显性关系的描述项，a,b是它的特殊值，则：,(5) 将常量转化成变量：,2020/6/28,人工智能,21,5.3.2 归纳学习方法,1、示例学习 示例学习（learning from examples）又称为实例学习，它是通过环境中若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。在这种学习方法中，外部环境提供的是一组例子（正例和反例），示例学习就是要从这些特殊知识中归纳出适用于更大范围的一般性知识，以覆盖所有的正例并排除所有反例。 2、观察发现学习 观察发现学习又称为描述性概括，其目

16、标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习可分为观察学习与机器发现两种。前者用于对事例进行聚类，形成概念描述；后者用于发现规律，产生定律或规则。,2020/6/28,人工智能,22,5.3.3 归纳学习示例-决策树学习,决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法。在这种方法中学习到的函数被表示为一颗决策树。学习得到的决策树也能再被表示为多个if-then规则，以提高可读性。 决策树学习方法对噪声数据有很好的健壮性且能够学习析取表达式。决策树学习算法有很多，比如ID3、C4.5、ASSISTANT等等。这些决策树学习方法搜索一个完整

17、表示的假设空间，从而避免了受限假设空间的不足。决策树学习的归纳偏置是优先选择较小的树。,2020/6/28,人工智能,23,决策树表示法,决策树通过把实例从根节点排列(sort)到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性(attribute)的测试，并且该节点的每一个后继分枝对应于该属性的一个可能值。 分类实例的方法是从这颗树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后这个过程再以新节点为根的子树上重复。,例子：在一个水果的分类问题中，采用的特征向量为：颜色,尺寸,形状,味道，其中：颜色取值为红,绿,

18、黄，尺寸取值为大,中,小，味道取值为甜,酸，形状取值为圆,细。 样本集：一批水果，知道其特征向量及类别 问 题：一个新的水果，观测到了其特征向量，将其分类,2020/6/28,人工智能,24,2020/6/28,人工智能,25,通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。 上述例子可对应如下析取式： (color=greensize=big) (color=greensize=medium) (color=greensize=small) (color=yellowsh

19、ape=roundsize=big) (color=yellowshape=roundsize=small) (color=yellowshape=thin) (color=redsize=medium) (color=redsize=smalltaste=sweet) (color=redsize=smalltaste=sour),2020/6/28,人工智能,26,决策树的适用问题,决策树学习适合解决具有以下特征的问题 实例是由“属性-值”对表示的：实例是用一系列固定的属性和它们的值来描述的。 目标函数具有离散的输出值：决策树给每个实例赋予一个布尔型的分类。决策树方法很容易扩展到学习有两个

20、以上输出值的函数。 可能需要析取的描述：决策树很自然地代表了析取表达式。 训练数据可以包含错误：决策树学习对错误有很好的健壮性，无论是训练样例所属的分类错误，还是描述这些样例的属性值错误。 训练数据可以包含缺少属性值的实例：决策树甚至可以再有未知属性值的训练样例中使用。,2020/6/28,人工智能,27,决策树学习的常见问题,确定决策树增长的深度，避免过度拟合； 处理连续值的属性； 选择一个适当的属性筛选度量标准； 处理属性值不完整的训练数据； 处理不同代价的属性； 提高计算效率。,2020/6/28,人工智能,28,ID3算法,大多数已开发的决策树学习算法是一种核心算法（CLS算法）的变体

21、。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法(Quinlan 1986)和后继的C4.5(Quinlan 1993)的基础。 ID3是一种自顶向下增长树的贪婪算法，在每个节点选取能最好分类样例的属性。继续这个过程指导这棵树能完美分类训练样例，或所有的属性都已被使用过。 构造过程是从“哪一个属性将在树的根节点被测试”这个问题开始。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根节点的测试。然后为根节点属性的每个可能值产生一个分枝，并把训练样例排列到适当的分枝（也就是，样例的该属性值对应的分枝）之下。然后重复整个过

22、程，用每个分枝节点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。,2020/6/28,人工智能,29,决策树的构建,已知训练样本集，构造决策树需要解决以下几个问题（考虑Binary Decision Trees）： （1）最佳提问的选择：应该先对哪一个属性提出问题？应该按什么样的顺序提出问题？ 每一个问题都是一个YES/NO问题。 （2）叶结点的确定：什么时候可以结束提问，并判定模式的类别？ （3）决策树修剪：如果决策树过大，应该如何修剪决策树，以保证其泛化能力？,2020/6/28,人工智能,30,最佳提问的选择（1）,（1

23、）决策树中的每一个结点（叶结点除外）对应于一个提问。每一个叶结点给出最终的分类。决策树的构建从根结点开始。 （2）根结点的构建：根结点对应于训练样本集D。通过选择针对某一属性的一个问题进行提问，可以根据对该问题的回答，将训练样本集D分类两个部分：Dy及Dn （其中， Dy为回答YES的样本， Dn为回答NO的样本） ，并建立与之相对应的两个子结点。我们希望选择一个这样问题进行提问：使得Dy及Dn尽可能纯净。 （3）中间结点的构造：对于每一个中间结点（结点N），都有一个与之对应的子集DN。同样，根据结点N的提问，可以将DN进一步划分为两个部分DNy及DNn（其中， DNy为回答YES的样本， D

24、Nn为回答NO的样本），并得到与之相对应的两个子结点。我们希望根据结点N提出的问题，能够使DNy及DNn尽可能纯净。,2020/6/28,人工智能,31,最佳提问的选择（2）,（4）当如上得到的某一个子结点足够纯净时，就可以确定该结点为叶结点，并给出其类别。 （5）当决策树中的每一条路径都对应于一个叶结点时，学习过程结束，决策树构建完毕。 （6）根据上述准则（纯净度准则）构建决策树，可以保证决策树的复杂度较小（结点数量少、深度小）。 （7）在对训练集分类能力相近的条件下，复杂度小的决策树（分类器）优于复杂度大的决策树（分类器）。复杂度小的分类器通常具有较好的泛化能力。这一原则称为Occams

25、razor。,2020/6/28,人工智能,32,最佳提问的选择（3）,（8）结点n非纯净度的定义,其中，i(n)为结点n的非纯净度，Nn 为结点n对应的样本的数量，Njn为结点n中属于j的样本的数量，C为类别的个数。,2020/6/28,人工智能,33,最佳提问的选择（4）,其中，ny为结点n的YES子结点，nn 为NO子结点，Nny为YES子结点对应的样本的数量，Nnn为NO子结点对应的样本的数量。 结点n的最佳选择问题：使i(n)取得最大值。,（9）结点n最佳问题的选择： 对于结点n，通过提出并回答某个问题，可以得到如下的纯净度的提高（不纯净度的降低）：,2020/6/28,人工智能,3

26、4,最佳提问的选择（5）,（10）结点n最佳问题的选择范围： 需要枚举出所有可以提出的问题，从中选出有效的问题，并在这些有效的问题中选择一个最佳的问题。 由于特征的数量是有限的，每个特征的可能取值也是有限的，所以所有可能提出的问题是可以枚举的。 所提问题通常限制为针对某个特征提出的简单问题，问题的形式如前面的二叉数所示。,2020/6/28,人工智能,35,叶结点的确定问题,决策树结点划分的原则是使其子结点尽可能纯净（指两个子结点的平均纯净度最高）。对于任意一个结点n，可以出现以下三种情况： （1）结点n中的样本属于同一类，即结点n绝对纯净。此时结点n不可进一步划分。 （2）结点n中的样本不属

27、于同一类，但是不存在任何一个划分（即提出一个问题并根据该问题对结点n的样本进行划分）可以使其子结点的平均纯净度高于结点n。此时结点n不可进一步划分。 （3）可以提出一个问题对结点n进行划分，从而使结点n的子结点具有更高的纯净度。此时结点n可以进一步划分。,2020/6/28,人工智能,36,叶结点的确定问题,问题：在构建决策树的过程中，确定叶节点的一个策略是：对于每一个可以进一步划分的结点都进行划分，直到得到一个不可划分的子结点，并将该子结点定为叶结点。这样构造的决策树，其叶结点均为不可再进一步划分的结点。这种叶结点的确定方法是否可行？ 答案：决策树是根据训练样本的集合构成的。该集合中的样本是

28、随机的。不同的随机实验会得到不同的样本集合。因此，该集合并不能完全描述样本(即特征向量)真实分布。当叶结点按上述方法确定时，所得决策树虽然对训练样本集合给出了最优的分类，但是却背离了样本的真实分布，因此削弱了对未来新样本的分类能力。这一现象称为过度拟合(指决策数对训练样本过度拟合，从而背离了样本的真实分布)。,2020/6/28,人工智能,37,叶结点确定的基本思路,（1）并不绝追求对训练样本的正确划分。并不绝对追求叶结点的纯净度。绝对追求叶结点的纯净度导致过度拟合。此时决策树的复杂度偏高。 （2）要适度保证叶结点的纯净度，适度保证对训练样本的正确分类能力。叶结点的不纯净度过高，对训练样本的正

29、确分类能力过低称为欠学习（此时，决策树不能够充分提取样本集合中蕴涵的有关样本真实分布的信息。欠学习同样不能保证对未来新样本的正确分类能力）。此时决策树的复杂度偏低。 （3）因此，在决策树的构建过程中，需要在过度拟合与欠学习之间寻求合理的平衡，即寻求复杂度适中的决策树。具体方法为：在结点还可以进一步划分的时候，可根据预先设定的准则停止对其划分，并将其设置为叶结点。,2020/6/28,人工智能,38,确定叶结点的基本方法（1）,方法1：采用测试集的方法。将样本集合分为训练集与测试集。根据训练集构建决策树，决策树中的结点逐层展开。每展开一层子结点，并将其设为叶结点，就得到一棵决策树，然后采用测试集

30、对所得决策树的分类性能进行统计。重复上述过程，可以得到决策树在测试集上的学习曲线。根据学习曲线，选择在测试集上性能最佳的决策树为最终的决策树。 方法2：在决策树开始训练以前，首先设定一个阈值A。在决策树的训练过程中，对于任意一个结点n，如果该结点的最优划分（即最优问题对该结点的样本集合所作的划分）所导致的纯净度的提高小于A，则将该结点定为叶结点。采用该方法不需要将样本集合分为训练集及测试集。决策树直接采用全体样本集合构建。,2020/6/28,人工智能,39,确定叶结点的基本方法（2）,方法3：在决策树开始训练以前，首先设定一个阈值A。在决策树的训练过程中，对于任意一个结点n，如果Nn/N B

31、1B2Bn 其中，A i、Bj是数据库中的数据项。数据项之间的关联规则就是根据一个事务中某些项的出现，可推导出另一些项在同一事务中也出现。挖掘关联规则的问题描述如下: 令I= i1, i2, , im 是所有项目（数据项）集，D是全体事务的集合（数据库），事务T 是I 的一个子集T I ，每个事务由唯一的标志TID标识。 对数据项集X I ，称T 包含X 当且仅当X T 对任一项集X I ，在事务集D中的支持度定义为X在该事务集中出现的相对频度，即：,2020/6/28,人工智能,96,关联规则具有形式： X=Y 这里X I , Y I ，且XY =, X 称为规则的条件, Y 称为规则的结果。其意义是：一个事务中某些项的出现, 可推导出另一些项在同一事务中也出现。 一条规则X=Y的支持度定义为：在集合D 中同时包含X 和Y 的事务数量与D中的总事务量之比，即：,一条规则X=Y的可信度定义为：在集合D 中，包含X 的事务中有多大可能性也包含Y。即：,2020/6/28,人工智能,97,规则的可信度表示规则的强度，规则的支持度表示规则出现的频度。可信度和支持度均大于给定阈值的规则称为强规则, 而数据挖掘的主要兴趣就是对强规则的挖掘。 关联规则挖掘问题可分解为以下两个步骤:,(1) 找出事务数据库D中所有大于给定阈值的项目集，称之为大数据