人工智能ArtificialIntelligence第五章课件.pptx

1、2022-11-16史忠植 人工智能：机器学习1内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结机器学习概述机器学习概述n 什么是机器学习？学习是使系统在不断重复的工作中对本身能力的增强和改进，使得系统下一次完成同样或类似的任务时比上一次更有效，即通过对人类学习过程和特点的研究，建立学习理论和方法，并应用于机器，以改进机器的行为和性能。1、学

2、习是一个过程。学习是经验积累的过程，这个过程可能很快，也可能很漫长；2、学习是对一个系统而言。这个系统可能是一个计算机系统，或一个人机系统；3、学习能够改变系统的性能。这只说明对系统性能的改进，但是并未限制改进的方法。从人工智能的角度看，机器学习是一门研究使用计算机获取新的知识和技能，提高现有计算机求解问题能力的科学2022-11-16史忠植 人工智能：机器学习2机器学习概述机器学习概述n 为什么要研究机器学习？必要性：理解学习的本质和建立学习系统是AI研究的目标之一现有的大多数AI系统都是演绎的，没有归纳推理，因而不能自动获取和生成知识 可行性：学习的过程是信息处理的过程，这包括直接记忆和经

3、过推理已有工作说明可以实现一定程度的机器学习2022-11-16史忠植 人工智能：机器学习3机器学习概述机器学习概述 机器学习的研究目标和困难研究目标：通用学习算法：理论分析任务和开发用于非实用学习任务的算法 认知模型：研究人的学习的计算模型和实验模型 工程目标：解决专门的实际问题，并开发完成这些任务的工程系统困难：学习系统性能的预测更加困难 获取知识的本质还是猜想。由特定的观察和类比生成的知识不可能证明其正确性。2022-11-16史忠植 人工智能：机器学习4机器学习模型机器学习模型 学习的一种模型环境：外部信息的来源，它将为系统的学习提供有关信息知识库：代表系统已经具有的知识学习环节：系统

4、的学习机构，它通过对环境的感知取得外部信息，然后经分析、综合、类比、归纳等思维过程获得知识，生成新的知识或改进知识库的组织结构。执行环节：基于学习后得到的新的知识库，执行一系列任务，并将运行结果报告学习环节，以完成对新知识库的评价，指导进一步的学习工作,是该模型的核心。环境环境学习环节学习环节知识库知识库执行环节执行环节2022-11-16史忠植 人工智能：机器学习5机器学习发展阶段机器学习发展阶段机器学习的研究大致可以分为三个阶段：n 五六十年代的探索阶段：主要受神经生理学、生理学和生物学的影响，研究主 要侧重于非符号的神经元模型的研究，主要研制通用学习系统，即神经网络或自组织系统。主要成果

5、有：感知机（Perceptron）Friedberg等模拟随机突变和自然选择过程的程序，Hunt等的决策树归纳程序CLS。2022-11-16史忠植 人工智能：机器学习6n 七十年代的发展阶段：由于当时专家系统的蓬勃发展，知识获取成为当务之急，这给机器学习带来了契机，主要侧重于符号学习的研究。机器学习的研究脱离了基于统计的以优化理论为基础的研究方法，提出了基于符号运算为基础的机器学习方法，并产生了许多相关的学习系统，主要系统和算法包括：Winston的积木世界学习系统；Michalski基于逻辑的归纳学习系统AQVAL；Michalski和Chilausky的AQ11；Quinlan的ID3程

6、序 Mitchell的版本空间方法。机器学习发展阶段机器学习发展阶段2022-11-16史忠植 人工智能：机器学习7n 八九十年代至今的鼎盛阶段。理论研究和应用研究也有了新的突破，机器学习的研究进入了全面的、系统化的时期。主要成果有：一方面传统的符号学习的各种方法已日臻完善。Michalski等将AQ11扩充为一个多功能学习系统AQ15，ID3算法中使用了熵，从而使决策树归纳得到了很大的改进。科学发现系统BACON开辟了无导师学习的两个重要研究领域。神经网络学习在消沉了一段时期后又重新蓬勃发展起来了，同时计算机硬件技术的高速发展也为开展大规模和高性能的人工神经网络提供了保障，使得基于神经网络的

7、连接学习从低谷走出，发展迅猛。其中Rumelhart等人提出的BP模型，提供了一个训练多层网络的实际可行的方法，克服了Perceptron的大部分局限性。机器学习机器学习发展阶段发展阶段2022-11-16史忠植 人工智能：机器学习8 另一方面，机器学习的基础理论的研究越来越引起人们的重视。1984年美国学者Valiant提出了基于概率近似正确性的学习理论（PAC学习），对布尔函数的一些特殊子类的可学习性进行了探讨，将可学习性与计算复杂性联系在一起，并由此派生出了“计算学习理论”（COLT）1995年，Vapnik出版了“统计学习理论”一书。对PAC的研究是一种理论性，存在性的；Vapnik的

8、研究却是构造性的，他将这类研究模型称为支持向量机SVM（Support Vector Machine）。机器学习机器学习发展阶段发展阶段2022-11-16史忠植 人工智能：机器学习9机器学习概述机器学习概述机器学习的研究方法 1、演绎学习：是一种常规的逻辑推理方法。其推理的过程就是从公理出发，经过逻辑变换，推导出结论。2、归纳学习：环境或教师提供一系列正例和反例，通过归纳推理，机器将这些例子进行推广，产生一个或一组一般的概念描述。3、类比学习：利用两个不同领域（目标域和源域）知识的相似性，从源域的知识（包括相似的特征和其他特征）推断出目标域的相应知识的推理方法。4、统计学习：基于数据构建概率

9、统计模型并运用模型对数据进行预测与分析。5、强化学习：又称激励学习，是从环境到行为映射的学习，以使奖励信号函数值最大。6、进化学习：是研究利用自然进化和适应思想的计算系统。2022-11-16史忠植 人工智能：机器学习102022-11-16史忠植 人工智能：机器学习11内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结归纳学习归纳学习归纳学习

10、（Inductive Learning）就是从个别到一般，根据某个概念的一系列已知的正例和反例，从中归纳出一个一般的概念描述旨在从大量的经验数据中归纳抽取出一般的判定规则和模式。是机器学习中最核心、最成熟的分支。归纳学习也称为：经验学习：归纳学习依赖于经验数据基于相似性的学习：归纳学习依赖于数据间的相似形归纳的操作：泛化(Generalization)：扩展某假设的语义信息，使其能够包含更多的正例特化(Specialization)：泛化的相反操作，用于限制概念描述的应用范围2022-11-16史忠植 人工智能：机器学习12归纳学习归纳学习 归纳学习的分类和研究领域：符号学习 监督学习：实例学

11、习：系统事先将训练例子（经验数据）分类：正、负例子。由于它产生规则，所以也称为概念学习 无监督学习：事先不知道训练例子的分类概念聚类：机器发现 神经网络：本质上是实例学习，为区别起见，称为联结学习学习的计算理论 传统的算法复杂性分析 概率近似正确性学习研究（计算学习理论）2022-11-16史忠植 人工智能：机器学习13实例学习实例学习 基本思想：环境提供给系统一些特殊的实例，这些例子事先由施教者划分为正例和反例。实例学习由此进行归纳推理，产生适用于更大范围的一般性知识，得到一般的规则，它将覆盖所有的正例并排除所有的反例。环境提供给学习环境的例子是低水平的信息，这是在特殊情况下执行环节的行为。

12、学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作2022-11-16史忠植 人工智能：机器学习14实例学习 例子空间要考虑的问题：示教例子的质量 例子空间的组织和搜索方法 规则空间要考虑的问题 形成知识的归纳推理方法 搜索规则空间的方法 对规则空间的要求例子空间例子空间规则空间规则空间选择例子选择例子解释例子解释例子2022-11-16史忠植 人工智能：机器学习15实例学习实例学习 按规则空间搜索方法分类：数据驱动方法：变型空间方法：采用统一的形式表示规则和例子。改进假设方法：例子和规则的表示不统一。程序根据例子选择一种操作，用该操作修改H中的规则模型驱动方法：

13、产生和测试方法：针对示教例子反复产生和测试假设的规则。利用基于模型的知识产生假设的规则，便于只产生可能合理的假设 方案示例方法：使用规则方案的集合来限制可能合理的规则形式，最符合示教例子的规则被认为是最合理的规则2022-11-16史忠植 人工智能：机器学习16实例学习实例学习 按任务的复杂性划分为：学习单个概念：由系统提供的某个概念的正例和反例，只要求系统归纳出一个概念的描述规则学习多个概念：要求归纳出多个相互独立的概念学习执行多步任务：执行环节使用一个操作序列去完成任务，即执行环节进行任务规划。因此，归纳出的规则应该是进行任务规划的规则2022-11-16史忠植 人工智能：机器学习17变型

14、空间方法变型空间方法 基本思想：以整个规则空间为初始的假设规则集合H，根据示教例子中的信息，对集合H进行一般化或特殊化处理，逐步缩小集合H，最后使H收敛为只含要求的规则。规则空间中的偏序关系：它是按一般性和特殊性来建立的一种概念之间的关系 排序后的变形空间：最上面：是最一般的 规则(概念)，是没有描述的点，所有的例子都符合这一概念 最下面一行的各点：是示教正例对应的概念，每个点的概念只符合一个正例2022-11-16史忠植 人工智能：机器学习18 假设规则的集合H：H是规则空间的子集H中最一般的元素组成的子集称为G集合H中最特殊的元素组成的子集称为S集合在规则空间中，H是G和S中间的一段。可以

15、用G和S来表示H 变型空间方法：初始：G是最上面一个点，S是最下面的直线（示教正例），H为整个规则空间搜索过程：G下移，S上移，H逐步缩小。结果：H收敛为只含一个要求的概念变型空间方法变型空间方法2022-11-16史忠植 人工智能：机器学习19 消除侯选元素算法(1)正规的初始H集是整个规则空间，这时S包含所有可能的示教正例（最特殊的概念）。(2)接收一个新的示教例子。如果是正例：去掉G中不覆盖新正例的概念，然后修改S为由新正例和S原有的元素共同归纳出的最特殊的结果 如果是反例：从S中去掉覆盖该反例的概念；然后修改G为由新反例和G原有元素共同特殊化为最一般的结果(3)若G=S，且是单元集合，

16、则转(4)，否则转(2)(4)输出H中的概念（即G和S）变型空间方法变型空间方法2022-11-16史忠植 人工智能：机器学习20 变型空间法的缺点(1)抗干扰能力差变形空间法是数据驱动的方法，所有数据驱动的方法都难以处理有干扰的训练例子算法得到的概念应满足每个示教例子的要求，所以一个错误的例子会造成很大的影响(2)无法发现析取概念变型空间方法变型空间方法2022-11-16史忠植 人工智能：机器学习21决策树学习决策树学习决策树 通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类 树上每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值正实

17、例：产生正值决策的实例负实例：产生负值决策的实例决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取2022-11-16史忠植 人工智能：机器学习22决策树学习例子决策树学习例子InstancesNo.of wingsBroken wings Living statusWing area/weight Fly120Alive2.5True221Alive2.5False322Alive2.6False420Alive3.0True520Dead3.2False600Alive0False710Alive0False820Alive3.

18、4True920alive2.0False2022-11-16史忠植 人工智能：机器学习23ID3ID3算法算法1、是利用信息论原理对大量样本的属性进行分析和归纳而产生的。2、决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。3、用信息增益（即信息论中的互信息）来选择属性作为决策树的结点。2022-11-16史忠植 人工智能：机器学习24决策树学习n 熵(entropy)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为：Entropy(S)=-pos log2(pos)neg log2(

19、neg)“pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0n 如果分类器有c个不同的输出，则：Entropy(S)=-ci=1pi log2(pi)pi表示S中属于类i的比例2022-11-16史忠植 人工智能：机器学习25决策树学习决策树学习例1：p1=p2=1/2 H1=-(1/2)*log2(1/2)-(1/2)*log2(1/2)=1例2：p1=1/4 p2=3/4 H2=-(1/4)*log2(1/4)-(3/4)*log2(3/4)=0.81例3：p1=1 p2=0 H3=-1*log21=02022-11-16史忠植 人工智能：机器学习26决策树学习

20、决策树学习n 实例集合S中属性A的信息增益为：Gain(S,A)=Entropy(S)-（|SV|/|S|）Entropy(Sv)vvalues of A Sv表示S的子集，其属性A的值为V2022-11-16史忠植 人工智能：机器学习27决策树学习决策树学习思路：考察任一个属性，计算其熵值；对这个特定属性，考察根据其不同的属性值分成的若干子集；对任意子集，考察不同的类别，计算其熵值并求和；从所有属性中，选择熵值最小（或增益最大）的属性作为当前决策节点。2022-11-16史忠植 人工智能：机器学习282022-11-16史忠植 人工智能：机器学习29内容提要内容提要5.1 5.1 机器学习概

21、述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结30类比学习类比学习类比学习 类比学习（learning by analogy）就是通过类比，即通过对相似事物加以比较所进行的一种学习。其推理过程如下：回忆与联想 选择 建立对应关系转换 P(a)Q(a),P(a)P(b)Q(b)Q(a)2022-11-16史忠植 人工智能：机器学习31类比学习主要包括如下四个过程：1.输入一组已知条件

22、和一组未完全确定的条件。2.对两组出入条件寻找其可类比的对应关系。3.根据相似转换的方法，进行映射。4.对类推得到的知识进行校验。类比学习类比学习2022-11-16史忠植 人工智能：机器学习2022-11-16史忠植 人工智能：机器学习32发展简况发展简况 1971年，Kling,R.E.,Stanford Research Institute,发表文章“A Paradigm for Reasoning by Analogy”提出了记忆网模型和案例 检索算法。1981年，Jaime G.Carbonell,Carnegie-Mellon University,发表文章“A Computati

23、onal Model of Analogical Problem Solving”，提出了转换类比 1983年，Jaime G.Carbonell,发表文章“Derivational Analogy and its role in Problem Solving”,提出了 派生类比 1991年，Jaime G.Carbonell等，发表文章“PRODIGY:An Integrated Architecture for Planning and Learning”，开发了PRODIGY系统。2022-11-16史忠植 人工智能：机器学习33类比的形式定义类比的形式定义ABAB类比问题求解的一般模

24、式2022-11-16史忠植 人工智能：机器学习34转换类比转换类比2022-11-16史忠植 人工智能：机器学习35手段手段-目的分析的问题求解模型目的分析的问题求解模型问题空间：问题空间：1)一组可能的问题组合状态集。2)一个初始状态。3)一个或多个目标状态。4)一组变换规则集5)差别函数6)对可用规则编序的索引函数7)一组全局路径限制8)差别表S-MEAS-MEA算法算法2022-11-16史忠植 人工智能：机器学习361)比较当前状态和目标状态，得出差别2)选择合适的规则，以减少两个状态间的差别3)尽可能应用转换规则，直至完成状态转换。否则保存当前状态，并将MEA算法递归地应用于其它子

25、问题，直到该子问题确认不能满足该规划的前提条件为止。4)当子问题求解后，恢复被保存的当前状态，再继续求解原来的问题2022-11-16史忠植 人工智能：机器学习37类比求解问题的计算模型类比求解问题的计算模型EMEA的T-空间包括：1)转换空间中每个状态是初始问题的潜在解，包括初始状态、最终状态、操作符序列以及路径限制。2)初始状态：O-空间中检索到的相似问题的解序列。3)目标状态：求解新问题的解的规范说明。4)操作符将一个完整的解序列映射到另一个潜在的解序列。5)差别函数：新问题情况下检索解的初始状态、中止状态、路径的约束和应用度之间的差别测度的综合。6)差别表：用来检索T-空间的操作。7)

26、没有路径约束，可用更为复杂的差别函数补偿。8)可用启发式函数作为规则排序。2022-11-16史忠植 人工智能：机器学习38基于案例推理基于案例推理n 人们为了解决一个新问题，先是进行回忆，从记忆中找到一个与新问题相似的案例，然后把该案例 中的有关信息和知识复用到新问题的求解之中。n 在基于案例推理(Case-Based Reasoning,简称CBR)中，把当前所面临的问题或情况称为目标案例(target case)，而把记忆的问题或情况称为源案例(base case)。粗略地说，基于案例 推理就是由目标案例 的提示而获得记忆中的源案例，并由源案例 来指导目标案例 求解的一种策略。2022-

27、11-16史忠植 人工智能：机器学习39 基于案例学习的一般过程基于案例学习的一般过程CBRCBR的过程模型的过程模型 新问题新范例检索保存修正范例解答范例确认解建议解检索建议粗略解调整辩护评批实际评估存储历史范例历史范例范例库2022-11-16史忠植 人工智能：机器学习402022-11-16史忠植 人工智能：机器学习41迁移学习迁移学习迁移学习（transfer learning）的目标是将从一个环境中学到的知识用来帮助新环境中的学习任务。在传统分类学习中，为了保证训练得到的分类模型具有准确性和高可靠性，都有两个基本的假设：用于学习的训练样本与新的测试样本满足独立同分布的条件；必须有足够

28、可利用的训练样本才能学习得到一个好的分类模型。但是，在实际应用中发现要满足这两个条件往往是困难的。迁移学习是运用已有的知识对不同但相关领域问题进行求解。它放宽了传统机器学习中的两个基本假设，目的是迁移已有的知识来解决目标领域中仅有少量有标签样本数据甚至没有的学习问题。2022-11-16史忠植 人工智能：机器学习42内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5

29、.9 5.9 小结小结2022-11-16史忠植 人工智能：机器学习43统计学习统计学习 统计方法是从事物的外在数量上的表现去推断该事物可统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。能的规律性。科学规律性的东西一般总是隐藏得比较深，科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的假说或学说，作进一步深入的理论研究。然后提出一定的假说或学说，作进一步深入的理论研究。当理论研究当理论研究 提出一定的结论时，往往还需要在实践中加提出一定的结论时，往往还需要在实践中加以验证。就是说，观测

30、一些自然现象或专门安排的实验以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。法处理。列联表及列联表分析列联表及列联表分析 研究两个属性变量之间是否有联系 研究步骤：通过问卷调查或统计资料获得属性 变量的信息 整理问卷或统计资料获得列联表数据 通过统计假设检验两个属性变量是 否具有独立性2022-11-16史忠植 人工智能：机器学习44 逻辑回归逻辑回归基本理论和方基本理论和方法法 研究某一事件发生

31、的概率P=P(y=1)与若干因素之间的关系 qqxxp 110在在0和和1之间之间任意范围之间的数量任意范围之间的数量若干个状态的标量若干个状态的标量2022-11-16史忠植 人工智能：机器学习45逻辑回归逻辑回归模型模型 人们通常把p的某个函数f(p)假设为变量的函数形式，取 称之为logit函数，也叫逻辑变换。因此，逻辑变换是取列联表中优势的对数。当概率在0-1取值时，Logit可以取任意实数，避免了线性概率模型的结构缺陷。()()lnln1()1xpf pxp2022-11-16史忠植 人工智能：机器学习46逻辑变换逻辑变换 logistic变换 Logistic回归模型 ),(1ln

32、 ppqqxxpp 1101ln优势比优势比2022-11-16史忠植 人工智能：机器学习47概率概率p p的预测的预测 P与多因素之间的关系预测qqqqxxxxeep 1101101)(11011qqxxep qqxxpp 1101ln2022-11-16史忠植 人工智能：机器学习48P P与单因素之间的关系图与单因素之间的关系图px1xxeep10101 01 最可能成功范围最可能成功范围最不可能成功范围最不可能成功范围2022-11-16史忠植 人工智能：机器学习49回归系数的含义回归系数的含义 优势比(Odds Ratio)事件发生与不发生的概率比 优势比与单变量系数之间的关系 qqx

33、xeppOR 1101),(),1,(2121qiqixxxxORexxxxORi 优势比减小优势比减小优势比增加优势比增加00ii 2022-11-16史忠植 人工智能：机器学习50支持向量机支持向量机 支持向量机（support vector machine:SVM）是一种二类分类方法，它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。2022-11-16史忠植 人工智能：机器学习51统计学习问题统计学习问

34、题 学习问题的表示学习的目的就是，在联合概率分布函数F(x,y)未知、所有可用的信息都包含在训练集中的情况下，寻找函数f(x,w0)，使它（在函数类f(x,w)，(w W）上最小化风险泛函 模式别别问题),(),(,()(yxdFwxfyLwRw)f(x,y1w)f(x,y ,0),(,(，若若wxfyL2022-11-16史忠植 人工智能：机器学习52经验风险最小化原则经验风险最小化原则(ERM)(ERM)最小化经验风险(训练样本错误率)NiiiempwxfdLnwR1),(,(1)(用ERM准则代替期望风险最小化并没有经过充分的理论论证，只是直观上合理的想当然做法 这种思想却在多年的机器学

35、习方法研究中占据了主要地位。人们多年来将大部分注意力集中到如何更好地最小化经验风险上。而实际上，即使可以假定当n趋向于无穷大时经验风险也不一定趋近于期望风险，在很多问题中的样本数目也离无穷大相去甚远，如神经网络。2022-11-16史忠植 人工智能：机器学习53学习机器实际风险的界学习机器实际风险的界 学习机器实际风险的界其中n样本数量，h是VC维，是递减函数 两种方法：神经网络:保持置信范围固定（通过选择一个适当构造的机器）并最小化经验风险。支持向量机(SVM):保持经验风险固定（比如等于零）并最小化置信范围。)()()(hnwRwRemp2022-11-16史忠植 人工智能：机器学习54结

36、构风险最小化原则结构风险最小化原则 函数集 Fk=F(x,w);wWk,k=1,2,n F1 F2 Fn VC维：h1h2hn 在使保证风险（风险的上界）最小的子集中选择使经验风险最小的函数2022-11-16史忠植 人工智能：机器学习552022-11-16史忠植 人工智能：机器学习56 Sn S*经验风险经验风险Empirical risk置信范围置信范围Confidence interval风险界限风险界限Bound on the riskh1h*hnhS1S*Sn结构风险最小化归纳原则结构风险最小化归纳原则(SRM)(SRM)最大间隔分类器最大间隔分类器 不但能将两类正确分开，而且使分

37、类间隔最大。hmin(R2A2,N)+1H1 H2 H 2/|w|2022-11-16史忠植 人工智能：机器学习572022-11-16史忠植 人工智能：机器学习58考虑2维空间中极端直线之间的间隔情况2222121-1bbDwwwDw 221222Dwww求出两条极端直线的距离：如何计算分划间隔如何计算分划间隔？特征空间与核函数特征空间与核函数 Mercer定理：要保证L2(C)下的对称函数 能以正的系数展开成(即 描述了在某个特征空间中的一个积)，其中紧集 ，充分必要条件是，对使得 的所有 ,条件 成立。RCCK:1,kkkkvuavuKvuK,0g 0,dudvvgugvuK duug2

38、NRC 2022-11-16史忠植 人工智能：机器学习59特征空间与核函数特征空间与核函数nMercer核多项式核高斯径向基函数核Sigmoid核（只在部分参数值情况下才满足核函数的定义）2022-11-16史忠植 人工智能：机器学习602022-11-16史忠植 人工智能：机器学习61提升方法提升方法 弱学习机（weak learner):对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨 强学习机（strong learner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert)根据CNN,ABC,CBS以往的预

39、测表现及实际天气情况作出综合准确的天气预测 弱学习机 强学习机 Boosting2022-11-16史忠植 人工智能：机器学习62提升方法提升方法 过程:在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重Set of weightedinstances Classifier Ct train classifier adjust weights2022-11-16史忠植 人工智能：机器学习63提升流程提升流程(loop1)(loop1)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设X1?1:-1 弱假设弱假设2022-11-16史忠植 人

40、工智能：机器学习64提升流程提升流程(loop2)(loop2)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Y3?1:-1 弱假设弱假设2022-11-16史忠植 人工智能：机器学习65提升流程提升流程(loop3)(loop3)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Z7?1:-1弱假设弱假设2022-11-16史忠植 人工智能：机器学习66内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5

41、.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结强化学习强化学习 人类（通常）从与外界环境的交互中学习。但是，动作的反馈并不总是立即的和直接的。例如，经常需要比较长时间才能充分知道我们的动作所得出的结果。在强化学习中，学习系统根据从环境中反馈的信号的状态（奖励/惩罚），调整系统的参数。强化学习由于其方法的通用性，对学习背景知识要求较少，以及适用于复杂、动态的环境等特点，在近年，引起了许多研究者的注意，成为机器学习的主要的方式之一。强化学习一般比较困难，主要是因为学习系统并不知道哪个动作是正确的，也不知

42、道哪个奖惩赋予哪个动作。2022-11-16史忠植 人工智能：机器学习67强化学习强化学习强化学习由四部分组成：策略，报酬函数r，值映射V和环境的模型。策略：定义在任何给定时刻学习系统的选择和动作的方法。这样，策略可以通过一组产生式规则或者一个简单的查找表来表示。报酬函数r：定义了在时刻t问题的状态/目标关系。它把每个动作，或更精细的每个状态-响应对，映射为一个报酬量，以指出那个状态完成目标的愿望的大小。赋值函数V：是环境中每个状态的一个属性，它指出对从这个状态继续下去的动作系统可以期望的报酬。报酬函数度量状态-响应对的立即的期望值，而赋值函数指出环境中一个状态的长期的期望值。模型：是抓住环境

43、行为的方面的一个机制。模型让我们在没有实际试验它们的情况下估计未来可能的动作。2022-11-16史忠植 人工智能：机器学习682022-11-16史忠植 人工智能：机器学习69强化学习模型强化学习模型i:input 输入 r:reward 奖励s:state 状态 a:action 动作状态 sisi+1ri+1奖励 ri动作动作 aia0a1a2s0s1s2s32022-11-16史忠植 人工智能：机器学习70学习自动机学习自动机在强化学习方法中，学习自动机是最普通的方法。这种系统的学习机制包括两个模块：学习自动机和环境。学习过程是根据环境产生的刺激开始的。自动机根据所接收到的刺激，对环境

44、做出反应，环境接收到该反应对其做出评估，并向自动机提供新的刺激。学习系统根据自动机上次的反应和当前的输入自动地调整其参数。2022-11-16史忠植 人工智能：机器学习71自适应动态程序设计自适应动态程序设计在自适应动态程序设计中，状态i的效用值U(i)可以用下式计算：其中，R(i)是在状态i时的奖励，Mij是从状态i到状态j的概率。jijjUMiRiU)()()(2022-11-16史忠植 人工智能：机器学习72Q-Q-学习学习在Q学习中，Q是状态-动作对到学习到的值的一个函数。对所有的状态和动作：Q:(state x action)value 对Q学习中的一步：),(),(MAX),()1

45、(),(11tttatttttasQasQrcasQcasQ (10.15)其中c和都1，rt+1是状态st+1的奖励。2022-11-16史忠植 人工智能：机器学习73内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结2022-11-16史忠植 人工智能：机器学习74进化计算进化计算进化计算(evolutionary computation)

46、是研究利用自然进化和适应思想的计算系统。达尔文进化论是一种稳健的搜索和优化机制，对计算机科学，特别是对人工智能的发展产生了很大的影响。大多数生物体是通过自然选择和有性生殖进行进化。自然选择决定了群体中哪些个体能够生存和繁殖，有性生殖保证了后代基因中的混合和重组。自然选择的法则是适应者生存，不适应者被淘汰,简言之为优生劣汰。生物进化的基本条件生物进化的基本条件生物进化过程的发生需要四个基本条件：1）存在有多个生物个体组成的种群；2）生物个体之间存在着差异，或群体具有多样性；3）生物能够自我繁殖；4）不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。2022-11-16史

47、忠植 人工智能：机器学习752022-11-16史忠植 人工智能：机器学习76遗传算法与自然进化的比较遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构2022-11-16史忠植 人工智能：机器学习77达尔文进化算法达尔文进化算法1)建立原始种体。2)通过突变建立子孙。3)选择：4)返回到步骤(1)。11sgs 111ZsxxsgsZsxx)(max)(1xQxQi2022-11-16史忠植 人工智能：机器学习78遗传算法遗传算法遗传算法先将搜索

48、结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。2022-11-16史忠植 人工智能：机器学习79基本遗传算法基本遗传算法1.随机产生一个由固定长度字符串组成的初始群体;2.对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：1)计算群体中的每个个体字符串的适应值;2)应用下述三种操作(至少前两种)来产生新的群体:复制:把现有的个体字符串复制到新的群体中。杂交:通

49、过遗传重组随机选择两个现有的子字符串,产生新的字符串。变异:将现有字符串中某一位的字符随机变异。3.把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可以是问题的解(或近似解)。2022-11-16史忠植 人工智能：机器学习80基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？12022-11-16史忠植 人工智能：机器学习81概率地选择遗传操作根据适应值选择一个个体完成交叉i:=i+1i:=i+1复制个体p(r)选择（接上页）基于适应值选择两个个体把新的两个

50、孩子加到群体中p(c)交叉变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中12022-11-16史忠植 人工智能：机器学习82 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下:(1)定义的问题是寻找n维的实数向量x,它使函数(2)双亲向量的初始群体从每维可行范围内随机选择。(3)子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。(4)根据最小误差选择向量为下一代新的双亲。(5)向量的标准偏差保持不变,或者没有可用的计算方法,那么处理结束。RRxFn:)(2022-11-16史忠植 人工智能：机器学习83 进化规