第5章机器学习课件

第5章 机器学习2024/7/51人工智能第5章 机器学习2023/8/131人工智能 学习能力是人类智能的根本特征。人类通过学习来提高和改进自己的能力。学习的基本机制是把一种情况下成功的表现行为转移到另一种类似的新情况中。人的认识能力和智慧才能就是在毕生的学习中逐步形成、发展和完善。任何自然的智能系统都具备学习的能力。机器学习是继专家系统之后人工智能应用的又一重要研究领域。本章主要介绍机器学习的有关知识及其主要的几种学习方法。2024/7/52人工智能 学习能力是人类智能的根本特征。人类通过学习来提高5.1 机器学习概述机器学习概述5.2 机械学习机械学习5.3 归纳学习归纳学习5.4 类比学习类比学习5.5 解释学习解释学习5.6 强化学习强化学习5.7 知识发现知识发现本章主要内容：2024/7/53人工智能5.1 机器学习概述本章主要内容：2023/8/133人工5.1 机器学习概述n什么是学习？什么是学习？学习是人类具有的一种重要智能行为，但究竟什么是学习，长期以来却众说纷纭。n关于“学习”这一概念的主要观点：q学习是系统改进其性能的过程。这是西蒙的观点。n西蒙的观点：学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。q学习是获取知识的过程。这是从事专家系统研究的人们的观点。q学习是技能的获取。这是心理学家的观点。q学习是事物规律的发现过程。2024/7/54人工智能5.1 机器学习概述什么是学习？2023/8/134人工 基本的学习形式有基本的学习形式有2 2种：种：（1）知识获取和技能求精。）知识获取和技能求精。例如，我们说某人学过物理。我们的意思是，此人已经掌握了有关物理学的基本概念，并且理解其含义，同时还懂得这些概念之间以及它们与物理世界之间的关系。一般地，知识获取可看作学习新的符号信息，而这些符号信息是以有效方式与应用这种信息的能力相适应的。（2）第二类学习形式是通过实践逐步改进机制和认知技能。）第二类学习形式是通过实践逐步改进机制和认知技能。学习的很多过程都是由改进所学的技能组成。这些技能包括意识的或者机制的协调，而这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。例如骑自行车或弹钢琴等等。知识获取的本质可能是一个自觉的过程，其结果产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复实践来实现的。人类的学习一般表现为这两种活动的结合。2024/7/55人工智能 基本的学习形式有2种：2023/8/135人工智能5.1.1 5.1.1 机器学习的定义机器学习的定义 至今，还没有统一的“机器学习”定义，而且也很难给出一个公认的和准确的定义。一般认为机器学习是研究如何使用机器来模拟人类学习活动的一门学科。更为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。u 最早的具有学习能力的程序：最早的具有学习能力的程序：1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。2024/7/56人工智能5.1.1 机器学习的定义 至今，还没有统一5.1.2 5.1.2 机器学习的发展史机器学习的发展史 机器学习的发展过程大体上可分为机器学习的发展过程大体上可分为4个时期：个时期：1、第一阶段是在50年代中叶到60年代中叶，属于热烈时期。在这个时期，所研究的是“没有知识”的学习，即“无知”学习；其研究目标是各类自组织系统和自适应系统；指导本阶段研究的理论基础是早在40年代就开始研究的神经网络模型。在这个时期，我国研制了数字识别学习机。2、第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。本阶段的研究目标是模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器内部描述。这个时期正是我国“史无前例”的十年，对机器学习的研究不可能取得实质进展。2024/7/57人工智能5.1.2 机器学习的发展史 机器学习的发展过程大体5.1.2 5.1.2 机器学习的发展史（机器学习的发展史（2 2）3、第三阶段从70年代中叶至80年代中叶，称为复兴时期。在这个时期，人们从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。u1980年,在美国召开了第一届国际机器学习研讨会;1984年,机器学习杂志问世。u我国于1987年召开了第一届全国机器学习研讨会;1989年成立了以中国科技大学蔡庆生教授为理事长的理事会。4、机器学习的最新阶段始于1986年。一方面，由于神经网络研究的重新兴起，另一方面，对实验研究和应用研究得到前所未有的重视。我国的机器学习研究开始进入稳步发展和逐渐繁荣的新时期。2024/7/58人工智能5.1.2 机器学习的发展史（2）3、第三阶段从70年代中叶机器学习、知识发现与数据挖掘机器学习、知识发现与数据挖掘 知识发现(Knowledge Discovering in Database)与数据挖掘(Data Mining)是人工智能、机器学习(Machine Learning)与数据库技术相结合的产物。KDD一词是在1989年于美国底特律市召开的第一届KDD国际学术会议上正式形成的。2019年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于数据库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传开来。数据挖掘和知识发现的研究已形成热潮，并在生物医学、金融管理、商业销售等领域得到成功应用，给机器学习注入新的活力。2024/7/59人工智能机器学习、知识发现与数据挖掘 知识发现(Knowledge 5.1.3 5.1.3 机器学习系统的基本结构机器学习系统的基本结构环境是指系统外部信息的来源，它可以是系统的工作对象，也可以包括工作对象和外界条件。学习单元处理环境提供的信息，相当于各种学习算法。学习单元利用环境提供的信息，并与执行单元的反馈信息进行比较，获取相关知识，对知识库进行修改。知识库用于存放由学习环节所得到的知识。知识库中知识的表示方法可以是：谓词、产生式、特征向量、神经网络等。执行单元处理系统所面临的现实问题，即应用知识库中的知识求解问题。机器学习系统的基本结构如图机器学习系统的基本结构如图2024/7/510人工智能5.1.3 机器学习系统的基本结构环境是指系统外部信息的来源影响学习系统设计的重要因素影响学习系统设计的重要因素(1)影响学习系统设计的最重要的因素是环境向系统提供的信息。更具体地说是信息的质量。(2)知识库是影响学习系统设计的第二个因素。知识的表示有多种形式，在选择时要兼顾以下4个方面：表达能力强。所选择的表示方式能很容易地表达有关的知识。易于推理。为了使学习系统的计算代价比较低，希望知识表示方式能使推理较为容易。容易修改知识库。学习系统的本质要求它不断地修改自己的知识库，当推广得出一般执行规则后，要加到知识库中。知识表示易于扩展。每一个学习系统都要求具有某些知识理解环境提供的信息，分析比较，做出假设，检验并修改这些假设。因此，更确切地说，学习系统是对现有知识的扩展和改进。2024/7/511人工智能影响学习系统设计的重要因素(1)影响学习系统设计的最重要的5.1.4 5.1.4 机器学习的分类机器学习的分类u按学习方法分类（温斯顿在1977年提出的分类方法）机械式学习：机械学习就是记忆。指导式学习：采用示教式学习策略，也称为示教学习。示例学习：通过工作例子学习。类比学习：应用类似任务的知识求解当前问题。解释学习：根据领域知识对当前实例分析和求解。u按学习的综合属性分类（综合考虑知识表示、推理方法、应用领域等多种因素）：归纳学习：从个体的特征归纳出它们的共性 分析学习：从领域理论出发演绎出更有效的规则。连接学习：人工神经网络学习 遗传学习：模拟自然界遗传与变异机制2024/7/512人工智能5.1.4 机器学习的分类按学习方法分类（温斯顿在1977年5.2 机械学习机械学习的模式机械学习的模式机械学习是最简单的机器学习方法。机械学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。机械学习又是最基本的学习过程。任何学习系统都必须记住它们获取的知识。在机械学习系统中，知识的获取是以较为稳定和直接的方式进行的，不需要系统进行过多的加工。(X1,X2,Xn)(Y1,Y2,Yn)f(X1,X2,Xn),(Y1,Y2,Yn)存储2024/7/513人工智能5.2 机械学习机械学习的模式(X1,X2,Xn)(Y数据化简数据化简 Lenat,Hayes Roth，和Klahr等人于1979年关于机械学习提出一种有趣的观点。他们指出，可以把机械学习看成是数据化简分级中的第一级。数据化简与计算机语言编译类似；其目的是把原始信息变成可执行的信息。在机械学习中我们只记忆计算的输入输出，忽略了计算过程，这样就把计算问题化简成存取问题。2024/7/514人工智能数据化简 Lenat,Hayes Roth，机械学习的主要问题机械学习的主要问题 对于机械学习，需要注意3个重要的问题：存储组织，稳定性和存储与计算之间的权衡。（1）存储组织信息：采用适当的存储方式，使检索速度尽可能地快，是机械学习中的重要问题。（2）环境的稳定性与存储信息的适用性问题：机械学习系统必须保证所保存的信息适应于外界环境变化的需要，这也就是所谓的信息适用性问题。（3）存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率。2024/7/515人工智能机械学习的主要问题 对于机械学习，需要注意3个5.3 归纳学习 归纳学习是目前研究得最多的学习方法，其学习目的是为了获得新的概念、构造新的规则或发现新的理论。这种方法对领域理论没有要求，甚至可以没有领域理论，但其需要大量的训练例子，而且归纳性能受到描述语言、概念类型、信噪比、实例空间分布、归纳模式等的影响。（1）归纳归纳（induction）是人类拓展认识能力的重要方法，是一种从个别到一般的，从部分到整体的推理行为。（2）归纳推理归纳推理是应用归纳方法，从足够多的具体事例中归纳出一般性知识，提取事物的一般规律；它是一种从个别到一般的推理。（3）归纳学习归纳学习（induction learning）是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察与发现学习。前者属于有师学习，后者属于无师学习。2024/7/516人工智能5.3 归纳学习 归纳学习是目前研究得最多的学5.3.1 5.3.1 归纳学习的模式和规则归纳学习的模式和规则归纳学习的模式归纳学习的模式给定：(1)观察陈述（事实）F，用以表示有关某些对象、状态、过程等的特定知识；(2)假定的初始归纳断言（可能为空），是关于目标的泛化项或泛化描述。(3)背景知识，用于定义有关观察陈述、候选归纳断言以及任何相关问题领域知识、假设和约束，其中包括能够刻画所求归纳断言的性质的优先准则。(4)求：归纳断言（假设）H，能重言蕴涵或弱蕴涵观察陈述，并满足背景知识。2024/7/517人工智能5.3.1 归纳学习的模式和规则归纳学习的模式给定：2023 假设H永真蕴涵事实F，说明F是H的逻辑推理，则有：H|F（读作H特殊化为F）或 F|CTXK(2)放松条件：一个事例的原因可能不止一条，当出现新的原因时，应该把新的原因包含进去。CTX1K=(CTX1CTX2)K 2024/7/519人工智能归纳概括规则 设CTX表示任一描述，K表示结论，(3)沿概念树上溯：设L是一结构性描述项，S代表所有条件中的L值在概念分层树上最近的共同祖先，则：(4)形成闭合区域：设L是一个具有显性关系的描述项，a,b是它的特殊值，则：(5)将常量转化成变量：2024/7/520人工智能(3)沿概念树上溯：(4)形成闭合区域：(5)将常量转5.3.2 5.3.2 归纳学习方法归纳学习方法1、示例学习、示例学习 示例学习（learning from examples）又称为实例学习，它是通过环境中若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。在这种学习方法中，外部环境提供的是一组例子（正例和反例），示例学习就是要从这些特殊知识中归纳出适用于更大范围的一般性知识，以覆盖所有的正例并排除所有反例。2、观察发现学习、观察发现学习 观察发现学习又称为描述性概括，其目标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习可分为观察学习与机器发现两种。前者用于对事例进行聚类，形成概念描述；后者用于发现规律，产生定律或规则。2024/7/521人工智能5.3.2 归纳学习方法1、示例学习2023/8/13215.3.3 5.3.3 归纳学习示例归纳学习示例-决策树学习决策树学习 决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法。在这种方法中学习到的函数被表示为一颗决策树。学习得到的决策树也能再被表示为多个if-then规则，以提高可读性。决策树学习方法对噪声数据有很好的健壮性且能够学习析取表达式。决策树学习算法有很多，比如ID3、C4.5、ASSISTANT等等。这些决策树学习方法搜索一个完整表示的假设空间，从而避免了受限假设空间的不足。决策树学习的归纳偏置是优先选择较小的树。2024/7/522人工智能5.3.3 归纳学习示例-决策树学习 决策树学决策树表示法决策树表示法n决策树通过把实例从根节点排列(sort)到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性(attribute)的测试，并且该节点的每一个后继分枝对应于该属性的一个可能值。n分类实例的方法是从这颗树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后这个过程再以新节点为根的子树上重复。例子：在一个水果的分类问题中，采用的特征向量为：颜色,尺寸,形状,味道，其中：颜色取值为红,绿,黄，尺寸取值为大,中,小，味道取值为甜,酸，形状取值为圆,细。样本集：一批水果，知道其特征向量及类别问 题：一个新的水果，观测到了其特征向量，将其分类2024/7/523人工智能决策树表示法决策树通过把实例从根节点排列(sort)到某个叶2024/7/524人工智能2023/8/1324人工智能 通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction)。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。上述例子可对应如下析取式：(color=greensize=big)(color=greensize=medium)(color=greensize=small)(color=yellowshape=roundsize=big)(color=yellowshape=roundsize=small)(color=yellowshape=thin)(color=redsize=medium)(color=redsize=smalltaste=sweet)(color=redsize=smalltaste=sour)2024/7/525人工智能 通常决策树代表实例属性值约束的合取(conju决策树的适用问题决策树的适用问题n决策树学习适合解决具有以下特征的问题q实例是由“属性-值”对表示的：实例是用一系列固定的属性和它们的值来描述的。q目标函数具有离散的输出值：决策树给每个实例赋予一个布尔型的分类。决策树方法很容易扩展到学习有两个以上输出值的函数。q可能需要析取的描述：决策树很自然地代表了析取表达式。q训练数据可以包含错误：决策树学习对错误有很好的健壮性，无论是训练样例所属的分类错误，还是描述这些样例的属性值错误。q训练数据可以包含缺少属性值的实例：决策树甚至可以再有未知属性值的训练样例中使用。2024/7/526人工智能决策树的适用问题决策树学习适合解决具有以下特征的问题2023决策树学习的常见问题决策树学习的常见问题n确定决策树增长的深度，避免过度拟合；n处理连续值的属性；n选择一个适当的属性筛选度量标准；n处理属性值不完整的训练数据；n处理不同代价的属性；n提高计算效率。2024/7/527人工智能决策树学习的常见问题确定决策树增长的深度，避免过度拟合；20ID3算法算法n大多数已开发的决策树学习算法是一种核心算法（CLS算法）的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法(Quinlan 1986)和后继的C4.5(Quinlan 1993)的基础。nID3是一种自顶向下增长树的贪婪算法，在每个节点选取能最好分类样例的属性。继续这个过程指导这棵树能完美分类训练样例，或所有的属性都已被使用过。n构造过程是从“哪一个属性将在树的根节点被测试”这个问题开始。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根节点的测试。然后为根节点属性的每个可能值产生一个分枝，并把训练样例排列到适当的分枝（也就是，样例的该属性值对应的分枝）之下。然后重复整个过程，用每个分枝节点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。2024/7/528人工智能ID3算法大多数已开发的决策树学习算法是一种核心算法（CLS决策树的构建决策树的构建n已知训练样本集，构造决策树需要解决以下几个问题（考虑Binary Decision Trees）：（1）最佳提问的选择：应该先对哪一个属性提出问题？应该按什么样的顺序提出问题？每一个问题都是一个YES/NO问题。（2）叶结点的确定：什么时候可以结束提问，并判定模式的类别？（3）决策树修剪：如果决策树过大，应该如何修剪决策树，以保证其泛化能力？2024/7/529人工智能决策树的构建已知训练样本集，构造决策树需要解决以下几个问题（最佳提问的选择（最佳提问的选择（1）（1）决策树中的每一个结点（叶结点除外）对应于一个提问。每一个叶结点给出最终的分类。决策树的构建从根结点开始。（2）根结点的构建：根结点对应于训练样本集D。通过选择针对某一属性的一个问题进行提问，可以根据对该问题的回答，将训练样本集D分类两个部分：Dy及Dn（其中，Dy为回答YES的样本，Dn为回答NO的样本），并建立与之相对应的两个子结点。我们希望选择一个这样问题进行提问：使得Dy及Dn尽可能纯净。（3）中间结点的构造：对于每一个中间结点（结点N），都有一个与之对应的子集DN。同样，根据结点N的提问，可以将DN进一步划分为两个部分DNy及DNn（其中，DNy为回答YES的样本，DNn为回答NO的样本），并得到与之相对应的两个子结点。我们希望根据结点N提出的问题，能够使DNy及DNn尽可能纯净。2024/7/530人工智能最佳提问的选择（1）（1）决策树中的每一个结点（叶结点除外）最佳提问的选择（最佳提问的选择（2）（4）当如上得到的某一个子结点足够纯净时，就可以确定该结点为叶结点，并给出其类别。（5）当决策树中的每一条路径都对应于一个叶结点时，学习过程结束，决策树构建完毕。（6）根据上述准则（纯净度准则）构建决策树，可以保证决策树的复杂度较小（结点数量少、深度小）。（7）在对训练集分类能力相近的条件下，复杂度小的决策树（分类器）优于复杂度大的决策树（分类器）。复杂度小的分类器通常具有较好的泛化能力。这一原则称为Occams razor。2024/7/531人工智能最佳提问的选择（2）（4）当如上得到的某一个子结点足够纯净时最佳提问的选择（最佳提问的选择（3）（8）结点n非纯净度的定义 其中，i(n)为结点n的非纯净度，Nn 为结点n对应的样本的数量，Njn为结点n中属于j的样本的数量，C为类别的个数。2024/7/532人工智能最佳提问的选择（3）（8）结点n非纯净度的定义 最佳提问的选择（最佳提问的选择（4）其中，ny为结点n的YES子结点，nn 为NO子结点，Nny为YES子结点对应的样本的数量，Nnn为NO子结点对应的样本的数量。结点n的最佳选择问题：使i(n)取得最大值。（9）结点n最佳问题的选择：对于结点n，通过提出并回答某个问题，可以得到如下的纯净度的提高（不纯净度的降低）：2024/7/533人工智能最佳提问的选择（4）其中，ny为结点n的YE最佳提问的选择（最佳提问的选择（5）（10）结点n最佳问题的选择范围：需要枚举出所有可以提出的问题，从中选出有效的问题，并在这些有效的问题中选择一个最佳的问题。由于特征的数量是有限的，每个特征的可能取值也是有限的，所以所有可能提出的问题是可以枚举的。所提问题通常限制为针对某个特征提出的简单问题，问题的形式如前面的二叉数所示。2024/7/534人工智能最佳提问的选择（5）（10）结点n最佳问题的选择范围：202叶结点的确定问题叶结点的确定问题 决策树结点划分的原则是使其子结点尽可能纯净（指两个子结点的平均纯净度最高）。对于任意一个结点n，可以出现以下三种情况：（1）结点n中的样本属于同一类，即结点n绝对纯净。此时结点n不可进一步划分。（2）结点n中的样本不属于同一类，但是不存在任何一个划分（即提出一个问题并根据该问题对结点n的样本进行划分）可以使其子结点的平均纯净度高于结点n。此时结点n不可进一步划分。（3）可以提出一个问题对结点n进行划分，从而使结点n的子结点具有更高的纯净度。此时结点n可以进一步划分。2024/7/535人工智能叶结点的确定问题 决策树结点划分的原则是使其子结点尽可能叶结点的确定问题叶结点的确定问题n问题：在构建决策树的过程中，确定叶节点的一个策略是：对于每一个可以进一步划分的结点都进行划分，直到得到一个不可划分的子结点，并将该子结点定为叶结点。这样构造的决策树，其叶结点均为不可再进一步划分的结点。这种叶结点的确定方法是否可行？n答案：决策树是根据训练样本的集合构成的。该集合中的样本是随机的。不同的随机实验会得到不同的样本集合。因此，该集合并不能完全描述样本(即特征向量)真实分布。当叶结点按上述方法确定时，所得决策树虽然对训练样本集合给出了最优的分类，但是却背离了样本的真实分布，因此削弱了对未来新样本的分类能力。这一现象称为过度拟合(指决策数对训练样本过度拟合，从而背离了样本的真实分布)。2024/7/536人工智能叶结点的确定问题问题：在构建决策树的过程中，确定叶节点的一个叶结点确定的基本思路叶结点确定的基本思路（1）并不绝追求对训练样本的正确划分。并不绝对追求叶结点的纯净度。绝对追求叶结点的纯净度导致过度拟合。此时决策树的复杂度偏高。（2）要适度保证叶结点的纯净度，适度保证对训练样本的正确分类能力。叶结点的不纯净度过高，对训练样本的正确分类能力过低称为欠学习（此时，决策树不能够充分提取样本集合中蕴涵的有关样本真实分布的信息。欠学习同样不能保证对未来新样本的正确分类能力）。此时决策树的复杂度偏低。（3）因此，在决策树的构建过程中，需要在过度拟合与欠学习之间寻求合理的平衡，即寻求复杂度适中的决策树。具体方法为：在结点还可以进一步划分的时候，可根据预先设定的准则停止对其划分，并将其设置为叶结点。2024/7/537人工智能叶结点确定的基本思路（1）并不绝追求对训练样本的正确划分。并确定叶结点的基本方法（确定叶结点的基本方法（1）方法1：采用测试集的方法。将样本集合分为训练集与测试集。根据训练集构建决策树，决策树中的结点逐层展开。每展开一层子结点，并将其设为叶结点，就得到一棵决策树，然后采用测试集对所得决策树的分类性能进行统计。重复上述过程，可以得到决策树在测试集上的学习曲线。根据学习曲线，选择在测试集上性能最佳的决策树为最终的决策树。方法2：在决策树开始训练以前，首先设定一个阈值A。在决策树的训练过程中，对于任意一个结点n，如果该结点的最优划分（即最优问题对该结点的样本集合所作的划分）所导致的纯净度的提高小于A，则将该结点定为叶结点。采用该方法不需要将样本集合分为训练集及测试集。决策树直接采用全体样本集合构建。2024/7/538人工智能确定叶结点的基本方法（1）方法1：采用测试集的方法。将样本集确定叶结点的基本方法（确定叶结点的基本方法（2）方法3：在决策树开始训练以前，首先设定一个阈值A。在决策树的训练过程中，对于任意一个结点n，如果Nn/NA，则确定结点n为叶结点。其中，Nn为结点n对应的样本的数量，N 为全体样本的数量。采用该方法同样不需要将样本集合分为训练集及测试集。决策树直接采用全体样本集合构建。方法4：采用如下的性能准则函数：其中size 代表决策树的复杂度，i(n)为结点n 的非纯净度。该准则函数表达出了过度拟合与欠学习之间的相互关系。决策树的优化准则为：使该准则函数取得最小值。2024/7/539人工智能确定叶结点的基本方法（2）方法3：在决策树开始训练以前，首先决策树修剪（决策树修剪（1）决策树的修剪是决策树学习的另外一种有效的方法。其基本思路是，首先使决策树得到充分生长，然后再通过修剪降低决策树的复杂度，从而保证决策树的泛化能力。具体方法如下：（1）决策树的构建：在决策树的构建过程中，对于每一个可以进一步划分的结点都进行划分，直到得到一个不可进一步划分的子结点，并将该子结点定为叶结点。这样构造的决策树，其叶结点均为不可再进一步划分的结点。2024/7/540人工智能决策树修剪（1）决策树的修剪是决策树学习决策树修剪（决策树修剪（2）（2）在上述决策树构建完毕后，从叶结点一层开始，考察兄弟叶结点是否可以合并。如果可以合并，则对这些兄弟结点进行合并，并将其父结点设为叶结点。在对所有可以合并的兄弟叶结点进行合并后，可以形成一棵新的决策树。对于新形成的决策树，可以重复上述兄弟结点的合并过程，直到最后得到一棵决策树，其中任意两个兄弟叶结点都不再满足合并的条件。这棵决策树，就是我们最终选择的决策树。2024/7/541人工智能决策树修剪（2）（2）在上述决策树构建完毕后，从叶结点一层开决策树修剪（决策树修剪（3）（3）兄弟叶结点合并的条件为 其中，ny及nn为兄弟叶结点，n为其父结点。Nn 为父结点中样本的数量，Nny及Nnn 为两个子结点中样本的数量。上述合并条件中，i(n)代表了由于合并所导致的不纯净度的损失。A为阈值，在修剪过程开始前预先设定。叶结点的类别叶结点的类别 设分类问题为C类的分类问题。对于叶结点n，如果在该结点对应的样本中，属于第 i 类的样本数量最多，则判该叶结点为第i类。2024/7/542人工智能决策树修剪（3）（3）兄弟叶结点合并的条件为 讨论讨论（1）根据决策树可以得出若干条规则。一条从根结点到叶结点的路途对应于一条IF-THEN规则。其中，路径的非叶结点部分构成了规则的条件部分（IF部分），叶结点给出了规则的结论（THEN部分）。例子：IF COLOR=RED AND SIZE=MEDIUM THEN IT IS AN APPLE 用途：知识的获取。（2）决策树方法同样可用于连续取值的特征量。当特征向量空间为欧氏空间时，同样可以采用决策树方法来构造分类器。当然，一般情况下在欧氏空间中通常采用神经网络来构造分类器。2024/7/543人工智能讨论（1）根据决策树可以得出若干条规则。一条从根结点到叶结点5.4 类比学习 类比(analogy)是一种很有用的和有效的推理方法，它能够清晰简洁地描述对象间的相似性；也是人类认识世界的一种重要方法。类比学习(learning by analogy)就是通过类比，即通过相似事物加以比较所进行的一种学习。例如，当人们遇到一个新问题需要进行处理，但又不具备处理这个问题的知识时，通常采用的办法就是回忆一下过去处理过的类似问题，找出一个与目前情况最接近的处理方法来处理当前问题。2024/7/544人工智能5.4 类比学习 类比(analogy)是一种5.4.1 5.4.1 类比推理和类比学习类比推理和类比学习类比推理类比推理 类比推理是由新情况与已知情况在某些方面的相似来推出它们在其它相关方面的相似。显然，类比推理是在两个相似域之间进行的：类比推理的目的是从源域中选出与当前问题最近似的问题及其求解方法以求解决当前的问题，或者建立起目标域中已有命题间的联系，形成新知识。类比推理过程如下：(1)(1)回忆与联想回忆与联想遇到新情况或新问题时，首先通过回忆与联想在S中找出与当前情况相似的情况，这些情况是过去已经处理过的，有现成的解决方法及相关的知识。2024/7/545人工智能5.4.1 类比推理和类比学习类比推理 类比推 (2)选择选择从找出的相似情况中选出与当前情况最相似的情况及其有关知识。(3)建立对应映射建立对应映射在S与T的相似情况之间建立相似元素的对应关系，并建立起相应的映射。(4)转换转换在上一步建立的映射下，把S中的有关知识引到T中来，从而建立起求解当前问题的方法或者学习到关于T的新知识。2024/7/546人工智能 (2)选择2023/8/1346人工智能类比学习类比学习 类比学习是基于类比推理的。类比学习的过程主要分为两步：首先归纳找出源问题和目标问题的公共性质，然后再演绎推出从源问题到目标问题的映射，得出目标问题的新的性质。所以类比学习既有归纳过程，又有演绎过程。类比学习的主要过程可描述如下：(1)输入一组已知条件（已解决问题）和一组未完全确定的条件（新问题）。(2)对输入的两组条件，根据其描述，按某种相似性的定义寻找两者可类比的对应关系。(3)按相似变换的方法，将已有问题的概念、特性、方法、关系等映射到新问题上，以获得待求解新问题所需的新知识。(4)对类推得到的新问题的知识进行校验。验证正确的知识存入知识库中，而暂时还无法验证的知识只能作为参考性知识，置于数据库中。2024/7/547人工智能类比学习 类比学习是基于类比推理的。类比学习的5.4.2 5.4.2 基于范例的学习基于范例的学习 范例（case）：“范例是一段带有上下文信息的知识，该知识表达了推理机在达到其目标的过程中能起关键作用的经验”。具体来说，一个范例应具有如下特性：范例表示了与某个上下文有关的具体知识，这种知识具有可操作性。范例可以是各式各样的，可有不同的形状和粒度，可涵盖或大或小的时间片，可带有问题的解答或动作执行后的效应。范例记录了有用的经验，这种经验能帮助推理机在未来更容易地达到目标，或提醒推理机失败发生的可能性有多大等等。2024/7/548人工智能5.4.2 基于范例的学习 范例（case）：“基于范例的推理基于范例的推理 人们为了解决一个新问题，先是进行回忆，从记忆中找到一个与新问题相似的范例，然后把该范例中的有关信息和知识复用到新问题的求解之中。这种推理就是基于范例的推理(Case-Based Reasoning,CBR)，也简称为范例推理。在基于范例推理中，把当前所面临的问题或情况称为目标范例(target case)，而把记忆的问题或情况称为源范例(base case)。粗略地说，基于范例推理就是由目标范例的提示而获得记忆中的源范例，并由源范例来指导目标范例求解的一种策略。2024/7/549人工智能基于范例的推理 人们为了解决一个新问题，先是进行范例推理基本流程范例推理基本流程提出解决方案确认解决方案以前案例新案例学过的案例取回案例新案例解决的案例修改案例 一般知识提取使用修改保留问题2024/7/550人工智能范例推理基本流程提出解决方案确认解决方案以前案例新案例学过的基于范例推理中知识表示是以范例为基础，范例的获取比规则获取要容易，大大简化知识获取。对过去的求解结果进行复用，而不是再次从头推导，可以提高对新问题的求解效率。过去求解成功或失败的经历可以指导当前求解时该怎样走向成功或避开失败，这样可以改善求解的质量。对于那些目前没有或根本不存在的问题，可以通过计算推导来解决的问题。如在法律中的判例，基于范例推理能很好发挥作用。范例推理的特点范例推理的特点2024/7/551人工智能基于范例推理中知识表示是以范例为基础，范例的获取比规则获取要基于范例的学习基于范例的学习 基于范例的推理系统经过不断的积累经验（案例），同时合适地对其进行索引，系统的推理效率和问题求解能力会随之增加。因此在CBR中，学习的主要任务是对案例库的丰富和优化。在CBR中，大多数学习是通过如下两种方式体现的：一个是新范例的积累，推理系统的范例对问题的覆盖越多，其功能越强；另一个是设计覆盖了成功事例也覆盖了失败事例的推理要比只设计成功情况的推理系统要好，索引的重新赋值，调节索引可使得范例能在更合适的时机被回忆。2024/7/552人工智能基于范例的学习 基于范例的推理系统经过不断的积累基于范例学习的一般过程基于范例学习的一般过程新问题 新范例检索历史范例范例库复用保存修正范例修正解答范例 确认解建议解2024/7/553人工智能基于范例学习的一般过程新问题 新范例检索历史范例范例库复用保范例的内容范例的内容(1)问问题题或或情情景景描描述述：是对要求解的问题或要理解的情景的描述，一般要包括这些内容：当范例发生时推理器的目标，完成该目标所要涉及的任务，周围世界或环境与可能解决方案相关的所有特征。(2)解解决决方方案案：是问题如何在一特定情形下得到解决。它可能是对问题的简单解答，也可能是得出解答的推导过程。(3)结结果果：记录了实施解决方案后的结果情况，是失败还是成功。有了结果内容，CBR在给出建议解时有能给出曾经成功地工作的范例，同时也能利用失败的范例来避免可能会发生的问题。当对问题还缺乏足够的了解时，通过在范例的表示上加上结果部分能取得较好的效果。2024/7/554人工智能范例的内容(1)问题或情景描述：是对要求解的问题或要理解的范例的索引范例的索引建立范例索引有三个原则：索引与具体领域有关。数据库中的索引是通用的，目的仅仅是追求索引能对数据集合进行平衡的划分从而使得检索速度最快；而范例索引则要考虑是否有利于将来的范例检索，它决定了针对某个具体的问题哪些范例被复用；索引应该有一定的抽象或泛化程度，这样才能灵活处理以后可能遇到的各种情景，太具体则不能满足更多的情况；索引应该有一定的具体性，这样才能在以后被容易地识别出来，太抽象则各个范例之间的差别将被消除。2024/7/555人工智能范例的索引建立范例索引有三个原则：2023/8/1355人范例学习的主要问题（范例学习的主要问题（1 1）(1)范例表示范例表示：基于范例推理方法的效率和范例表示紧密相关。范例表示涉及这样几个问题:选择什么信息存放在一个范例中；如何选择合适的范例内容描述结构；范例库如何组织和索引。对于那些数量达到成千上万、而且十分复杂的范例,组织和索引问题尤其重要。(2)分析模型分析模型：分析模型用于分析目标范例，从中识别和抽取检索源范例库的信息。(3)范例检索范例检索：利用检索信息从源范例库中检索并选择潜在可用的源范例。这步非常关键。一般讲，范例匹配不是精确的，只能是部分匹配或近似匹配。因此，它要求有一个相似度的评价标准。该标准定义得好，会使得检索出的范例十分有用，否则将会严重影响后面的过程。2024/7/556人工智能范例学习的主要问题（1）(1)范例表示：基于范例推理范例学习的主要问题（范例学习的主要问题（2 2）(4)类比映射类比映射:寻找目标范例同源范例之间的对应关系。(5)类比转换类比转换:转换源范例中同目标范例相关的信息，以便应用于目标范例的求解过程中。把检索到的源范例的解答复用于新问题或新范例之中需要解决的问题分别是：源范例与目标范例间有何不同之处；源范例中的哪些部分可以用于目标范例。需要根据它们之间的不同对复用的求解方案进行调整。(6)解释过程解释过程:对把转换过的源范例的求解方案应用到目标范例时所出现的失败做出解释，给出失败的因果分析报告。有时对成功也同样做出解释。基于解释的索引也是一种重要的方法。(7)范例修补范例修补:有些类似于类比转换，区别在于修补过程的输入是解方案和一个失败报告，而且也许还包含一个解释，然后修改这个解以排除失败的因素。2024/7/557人工智能范例学习的主要问题（2）(4)类比映射:寻找目标范例学习的主要问题（范例学习的主要问题（3 3）(8)类比验证类比验证:验证目标范例和源范例进行类比的有效性。(9)范例保存范例保存:新问题得到了解决，则形成了一个可能用于将来情形与之相似的问题。这时有必要把它加入到范例库中。这是学习也是知识获取。此过程涉及选取哪些信息保留，以及如何把新范例有机集成到范例库中。修改和精化源范例库,其中包括泛化和抽象等过程。在决定选取范例的哪些信息进行保留时，一般要考虑以下几点：和问题有关的特征描述；问题的求解结果；以及解答为什么成功或失败的原因及解释。把新范例加入到范例库中，需要对它建立有效的索引，这样以后才能对之作出有效的回忆。为此，可能要对范例库的索引内容甚至结构进行调整，如改变索引的强度或特征权值。2024/7/558人工智能范例学习的主要问题（3）(8)类比验证:验证目标5.5 解释学习基于解释的学习：一种从单个观察中抽象出通用规则的方法目标是下次可以快速地解决类似的问题通过保存结果和避免从零开始解决问题来提高速度更进一步EBL从观察到规则 解释学习(Explanation-Based Learning,简称EBL)是一种分析学习方法，在领域知识指导下,通过对单个问题求解实例的分析,构造出求解过程的因果解释结构,并获取控制知识,以便用于指导以后求解类似问题。2024/7/559人工智能5.5 解释学习基于解释的学习：解释学习(解释学习过程和算法 解释学习一般包括下列3个步骤：(1)利用基于解释的方法对训练例子进行分析与解释。(2)对例子的结构进行概括性解释。(3)从解释结构中识别出训练例子的特性，获取一般控制知识。1986年米切尔（Mitchell）等人为基于解释的学习提出了一个统一的算法EBG，该算法建立了基于解释的概括过程，并运用知识的逻辑表示和演绎推理进行问题求解。下图表示EBG问题。2024/7/560人工智能解释学习过程和算法 解释学习一般包括下列3个步骤：2023/EBG求解问题的形式描述:给定：(1)目标概念描述TC；(2)训练实例TE；(3)领域知识DT；(4)操作准则OC。求解：训练实例的一般化概括，使之满足：(1)目标概念的充分概括描述TC；(2)操作准则OC。图 EBG问题 2024/7/561人工智能 EBG求解问题的形式描述:图 EBG问题 20235.6 强化学习 强化学习(reinforcement learning-RL，又称再励学习，评价学习)在智能控制机器人及分析预测等领域有许多应用。在传统的机器学习分类中没有提及到过强化学习。而在连接主义学习中，把学习算法分为非监督学习(unsupervised learning)、监督学习(supervised learning)和强化学习三种。所谓强化学习就是智能系统从环境到行为映射的学习，以使奖励信号(强化信号)函数值最大。强化学习不同于连接主义学习中的监督学习，主要表现在教师信号上，强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价(通常为标量信号)，而不是告诉强化学习系统如何去产生正确的动作。2024/7/562人工智能5.6 强化学习 强化学习(reinforcem强化学习通常包括两个方面的含义：一方面是将强化学习作为一类问题；另一方面是指解决这类问题的一种技术。如果将强化学习作为一类问题，目前的学习技术大致可分成两类：其一是搜索智能系统的行为空间，以发现系统最优的行为。典型的技术如遗传算法等搜索技术；另一类是采用统计技术和动态规划方法来估计在某一环境状态下的行为的效用函数值，从而通过行为效用函数来确定最优行为。我们特指这种学习技术为强化学习技术。2024/7/563人工智能强化学习通常包括两个方面的含义：如果将强化强化学习的产生与发展 u强化思想最先来源于心理学的研究。1911年Thorndike提出了效果律（Law of Effect）：一定情景下让动物感到舒服的行为，就会与此情景增强联系（强化），当此情景再现时，动物的这种行为也更易再现；相反，让动物感觉不舒服的行为，会减弱与情景的联系，此情景再现时，此行为将很难再现。换个说法，哪种行为会“记住”，会与刺激建立联系，取决于行为产生的效果。u动物的试错学习，包含两个含义：选择和联系，对应计算上的搜索和记忆。所以，1954年，Minsky在他的博士论文中实现了计算上的试错学习。同年，Farley和Clark也在计算上对它进行了研究。强化学习一词最早出现于科技文献是1961年Minsky 的论文“Steps Toward Artificial Intelligence”，此后开始广泛使用。1969年，Minsky因在人工智能方面的贡献而获得计算机图灵奖。2024/7/564人工智能强化学习的产生与发展 强化思想最先来源于心理学的研究。191强化学习的发展过程可粗略分为两个阶段：n强化学习的形成阶段（50 年代60年代）Minsky首次提出“强化”和“强化学习”这些术语；Samuel的下棋程序采用类似值迭代、瞬时差分和Q 学习的训练机制，来学习用线性函数表示的值函数；Saridis 把强化控制系统的控制器看成一个随机自动机，首次系统提出了采用强化学习来解决随机控制系统的学习控制问题。n强化学习的发展阶段（70 年代 ）1972年，Klopf把试错学习和时序差分结合在一起。1978年开始，Sutton、Barto、Moore等对这两者结合开始进行深入研究。1989年Watkins提出了Q-学习，也把强化学习的三条主线扭在了一起。1992年，Tesauro用强化学习成功了应用到西洋双陆棋中，称为TD-Gammon。2024/7/565人工智能强化学习的发展过程可粗略分为两个阶段：强化学习的形成阶段（5.6.1 5.6.1 强化学习的原理强化学习的原理 强化学习把学习看作试探过程，基本过程如图所示。在强化学习中，Agent 选择一个动作作用于环境，环境接收该动作后发生变化，同时产生一个强化信号（奖或罚）反馈给Agent，Agent 再根据强化信号和环境的当前状态再选择下一个动作，选择的原则是使受到正的报酬的概率增大。选择的动作不仅影响立即强化值而且还影响下一时刻的状态及最终强化值。强化学习的目的就是寻找一个最优策。1、强化学习的结构 Agent环境状态s奖赏r动作a2024/7/566人工智能5.6.1 强化学习的原理 强化学习把学习看作试 强化学习模型由以下部分组成：2、强化学习模型 一个离散的状态集S=s0,s1,s2,sn；动作集A=a0,a1,a2,an；一个强化值集r R；agent 和环境交互的状态动作序列(si,ai)ri，表示agent 在状态si 下执行动作ai 获得的立即奖赏值ri。agent 执行一个动作除了获得立即奖赏信号外，还有从后续状态动作映射的延迟奖赏。agent 获得的总奖赏值为:其中0,1 为折扣因子。Agent 的任务就是学习控制策略:S A，能够最大化期望奖赏值的总和。2024/7/567人工智能 强化学习模型由以下部分组成：2、强化学习模型 一个离散的状 强化学习技术的基本原理是：如果系统某个动作导致环境正的奖赏，那么系统以后产生这个动作的趋势便会加强。反之系统产生这个动作的趋势便减弱。这和生理学中的条件反射原理是接近的。如果假定环境是马尔可夫型的，则顺序型强化学习问题可以通过马氏决策过程（Markov Decision Process，MDP）建模。下面首先给出马氏决策过程的形式化定义。马氏决策过程马氏决策过程 由四元组定义。包含一个环境状态集S，系统行为集合A，奖赏函数R：SA 和状态转移函数P：SAPD(S)。记R(s,a,s)为系统在状态s采用a动作使环境状态转移到s获得的瞬时奖赏值，简记为Rass；记P(s,a,s)为系统在状态s采用a动作使环境状态转移到s的概率，简记为Pass。2024/7/568人工智能 强化学习技术的基本原理是：如果系统某个动作导致 马氏决策过程的本质是：当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。因此在已知状态转移概率函数P和奖赏函数R的环境模型知识下，可以采用动态规划技术求解最优策略。而强化学习着重研究在P函数和R函数未知的情况下，系统如何学习最优行为策略。由于模型中P函数和R函数未知，系统只能够依赖于每次试错所获得的瞬时奖赏来选择策略。但由于在选择行为策略过程中，要考虑到环境模型的不确定性和目标的长远性，因此在策略和瞬时奖赏之间构造值函数（即状态的效用函数），用于策略的选择。2024/7/569人工智能 马氏决策过程的本质是：当前状态向下一状态转移的 首先通过下式构造一个返回函数Rt，用于反映系统在某个策略指导下的一次学习循环中，从st状态往后所获得的所有奖赏的累计折扣和。由于环境是不确定的，系统在某个策略指导下的每一次学习循环中所得到的Rt有可能是不同的。因此在s状态下的值函数要考虑不同学习循环中所有返回函数的数学期望。因此在策略下，系统在s状态下的值函数由下式定义，其反映了如果系统遵循策略，所能获得的期望的累计奖赏折扣和。2024/7/570人工智能 首先通过下式构造一个返回函数Rt，用于反映系统在某 根据Bellman最优策略公式，在最优策略*下，系统在s状态下的值函数定义为：所以，强化学习的任务就是求解所以，强化学习的任务就是求解*。由于强化学习中，P函数和R函数未知，系统无法直接求解上面的值函数。因而实际中常采用逼近的方法进行值函数的估计，其中最主要的方法之一是Monte Carlo采样。2024/7/571人工智能 根据Bellman最优策略公式，在最优策略*下5.6.2 5.6.2 强化学习算法强化学习算法 到目前为止，研究者们提出了很多强化学习算法，近年来对强化学习算法的研究已由算法本身逐渐转向研究经典算法在各种复杂环境中的应用，较有影响的强化学习算法有TD 算法，Q 学习算法，Sarsa算法，Dyan 算法，R 学习算法，H 学习等，还有一些改进算法，如滞后更新多步Q-学习算法等。2024/7/572人工智能5.6.2 强化学习算法 到目前为止，研究者们1、蒙特卡罗算法 蒙特卡罗算法(Monte Carlo method,MC)通过评估值函数来发现最优策略，且不需要环境的全部信息，它只需要经验知识。如部分有关状态序列、动作行为集以及同环境交互产生的奖赏值的信息。MC算法基于平均化取样回报来解决强化学习问题，它将解决的问题分解成幕(episode)。当环境状态为终止状态时，将得到积累回报赋予开始状态s 的值函数V。从s 出发到终止状态t 的过程中，s 可能不止出现一次。对s 的值函数的更新有两种方法：(1)first visit MC 将回报赋予第一次访问的s；(2)every visit MC 将每次访问s 到t 的回报平均后赋予s。2024/7/573人工智能1、蒙特卡罗算法 蒙特卡罗算法(Monte MC算法中，值函数更新规则为：其中，Rt 为t 时刻的奖赏值，为步长参数。控制过程采用贪心搜索策略。TTTTTTTTTTTTTTTTTTTT2024/7/574人工智能MC算法中，值函数更新规则为：其中，Rt 为2、瞬时差分学习算法(TD算法)TD(Temporal Differences)算法是一种增量式学习算法，它不用建立环境的动态信息模型，也不必等到最终输出结果产生之后再修改以往学到的经验,而是直接从交互经验中学习，在学习过程中逐步修改。最简单的算法为一步TD 算法，即TD(0)算法，是一种自适应的策略迭代算法。所谓一步TD 算法，是指Agent 获得的瞬时报酬值仅回退一步，也就是说只是修改了相邻状态的估计值。TD(0)算法如式：与MC算法相比，上式中用回报的估计值rt+1+V(st+1)代替了实际回报值Rt。2024/7/575人工智能2、瞬