人工智能ArtificialIntelligenc第五章ppt课件

《人工智能ArtificialIntelligenc第五章ppt课件》由会员分享，可在线阅读，更多相关《人工智能ArtificialIntelligenc第五章ppt课件（110页珍藏版）》请在装配图网上搜索。

1、人工智能人工智能Artificial IntelligenceArtificial Intelligence第五章第五章史忠植史忠植 中国科学院计算技术研究所http:/ Learning2022-8-28史忠植 人工智能：机器学习2内容提要内容提要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 什么是机器学习？学习是使系统在不断

2、重复的工作中对本身能力的增强和改进，使得系统下一次完成同样或类似的任务时比上一次更有效，即通过对人类学习过程和特点的研究，建立学习理论和方法，并应用于机器，以改进机器的行为和性能。1、学习是一个过程。学习是经验积累的过程，这个过程可能很快，也可能很漫长；2、学习是对一个系统而言。这个系统可能是一个计算机系统，或一个人机系统；3、学习能够改变系统的性能。这只说明对系统性能的改进，但是并未限制改进的方法。从人工智能的角度看，机器学习是一门研究使用计算机获取新的知识和技能，提高现有计算机求解问题能力的科学2022-8-28史忠植 人工智能：机器学习3机器学习概述机器学习概述n 为什么要研究机器学习？

3、必要性：理解学习的本质和建立学习系统是AI研究的目标之一现有的大多数AI系统都是演绎的，没有归纳推理，因而不能自动获取和生成知识 可行性：学习的过程是信息处理的过程，这包括直接记忆和经过推理已有工作说明可以实现一定程度的机器学习2022-8-28史忠植 人工智能：机器学习4机器学习概述机器学习概述 机器学习的研究目标和困难研究目标：通用学习算法：理论分析任务和开发用于非实用学习任务的算法 认知模型：研究人的学习的计算模型和实验模型 工程目标：解决专门的实际问题，并开发完成这些任务的工程系统困难：学习系统性能的预测更加困难 获取知识的本质还是猜想。由特定的观察和类比生成的知识不可能证明其正确性。

4、2022-8-28史忠植 人工智能：机器学习5机器学习模型机器学习模型 学习的一种模型环境：外部信息的来源，它将为系统的学习提供有关信息知识库：代表系统已经具有的知识学习环节：系统的学习机构，它通过对环境的感知取得外部信息，然后经分析、综合、类比、归纳等思维过程获得知识，生成新的知识或改进知识库的组织结构。执行环节：基于学习后得到的新的知识库，执行一系列任务，并将运行结果报告学习环节，以完成对新知识库的评价，指导进一步的学习工作,是该模型的核心。环境环境学习环节学习环节知识库知识库执行环节执行环节2022-8-28史忠植 人工智能：机器学习6机器学习发展阶段机器学习发展阶段机器学习的研究大致可

5、以分为三个阶段：n 五六十年代的探索阶段：主要受神经生理学、生理学和生物学的影响，研究主 要侧重于非符号的神经元模型的研究，主要研制通用学习系统，即神经网络或自组织系统。主要成果有：感知机（Perceptron）Friedberg等模拟随机突变和自然选择过程的程序，Hunt等的决策树归纳程序CLS。2022-8-28史忠植 人工智能：机器学习7n 七十年代的发展阶段：由于当时专家系统的蓬勃发展，知识获取成为当务之急，这给机器学习带来了契机，主要侧重于符号学习的研究。机器学习的研究脱离了基于统计的以优化理论为基础的研究方法，提出了基于符号运算为基础的机器学习方法，并产生了许多相关的学习系统，主要

6、系统和算法包括：Winston的积木世界学习系统；Michalski基于逻辑的归纳学习系统AQVAL；Michalski和Chilausky的AQ11；Quinlan的ID3程序 Mitchell的版本空间方法。机器学习发展阶段机器学习发展阶段2022-8-28史忠植 人工智能：机器学习8n 八九十年代至今的鼎盛阶段。理论研究和应用研究也有了新的突破，机器学习的研究进入了全面的、系统化的时期。主要成果有：一方面传统的符号学习的各种方法已日臻完善。Michalski等将AQ11扩充为一个多功能学习系统AQ15，ID3算法中使用了熵，从而使决策树归纳得到了很大的改进。科学发现系统BACON开辟了无

7、导师学习的两个重要研究领域。神经网络学习在消沉了一段时期后又重新蓬勃发展起来了，同时计算机硬件技术的高速发展也为开展大规模和高性能的人工神经网络提供了保障，使得基于神经网络的连接学习从低谷走出，发展迅猛。其中Rumelhart等人提出的BP模型，提供了一个训练多层网络的实际可行的方法，克服了Perceptron的大部分局限性。机器学习机器学习发展阶段发展阶段2022-8-28史忠植 人工智能：机器学习9 另一方面，机器学习的基础理论的研究越来越引起人们的重视。1984年美国学者Valiant提出了基于概率近似正确性的学习理论（PAC学习），对布尔函数的一些特殊子类的可学习性进行了探讨，将可学习

8、性与计算复杂性联系在一起，并由此派生出了“计算学习理论”（COLT）1995年，Vapnik出版了“统计学习理论”一书。对PAC的研究是一种理论性，存在性的；Vapnik的研究却是构造性的，他将这类研究模型称为支持向量机SVM（Support Vector Machine）。机器学习机器学习发展阶段发展阶段2022-8-28史忠植 人工智能：机器学习10机器学习概述机器学习概述机器学习的研究方法 1、演绎学习：是一种常规的逻辑推理方法。其推理的过程就是从公理出发，经过逻辑变换，推导出结论。2、归纳学习：环境或教师提供一系列正例和反例，通过归纳推理，机器将这些例子进行推广，产生一个或一组一般的概

9、念描述。3、类比学习：利用两个不同领域（目标域和源域）知识的相似性，从源域的知识（包括相似的特征和其他特征）推断出目标域的相应知识的推理方法。4、统计学习：基于数据构建概率统计模型并运用模型对数据进行预测与分析。5、强化学习：又称激励学习，是从环境到行为映射的学习，以使奖励信号函数值最大。6、进化学习：是研究利用自然进化和适应思想的计算系统。2022-8-28史忠植 人工智能：机器学习112022-8-28史忠植 人工智能：机器学习12内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5

10、5.5 强化学习强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结归纳学习归纳学习归纳学习（Inductive Learning）就是从个别到一般，根据某个概念的一系列已知的正例和反例，从中归纳出一个一般的概念描述旨在从大量的经验数据中归纳抽取出一般的判定规则和模式。是机器学习中最核心、最成熟的分支。归纳学习也称为：经验学习：归纳学习依赖于经验数据基于相似性的学习：归纳学习依赖于数据间的相似形归纳的操作：泛化(Generalization)：扩展某假设的语义信息，使其能够包含更多的正例特化(Specializatio

11、n)：泛化的相反操作，用于限制概念描述的应用范围2022-8-28史忠植 人工智能：机器学习13归纳学习归纳学习 归纳学习的分类和研究领域：符号学习 监督学习：实例学习：系统事先将训练例子（经验数据）分类：正、负例子。由于它产生规则，所以也称为概念学习 无监督学习：事先不知道训练例子的分类概念聚类：机器发现 神经网络：本质上是实例学习，为区别起见，称为联结学习学习的计算理论 传统的算法复杂性分析 概率近似正确性学习研究（计算学习理论）2022-8-28史忠植 人工智能：机器学习14实例学习实例学习 基本思想：环境提供给系统一些特殊的实例，这些例子事先由施教者划分为正例和反例。实例学习由此进行归

12、纳推理，产生适用于更大范围的一般性知识，得到一般的规则，它将覆盖所有的正例并排除所有的反例。环境提供给学习环境的例子是低水平的信息，这是在特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作2022-8-28史忠植 人工智能：机器学习15实例学习 例子空间要考虑的问题：示教例子的质量 例子空间的组织和搜索方法 规则空间要考虑的问题 形成知识的归纳推理方法 搜索规则空间的方法 对规则空间的要求例子空间例子空间规则空间规则空间选择例子选择例子解释例子解释例子2022-8-28史忠植 人工智能：机器学习16实例学习实例学习 按规则空间搜索方法分类

13、：数据驱动方法：变型空间方法：采用统一的形式表示规则和例子。改进假设方法：例子和规则的表示不统一。程序根据例子选择一种操作，用该操作修改H中的规则模型驱动方法：产生和测试方法：针对示教例子反复产生和测试假设的规则。利用基于模型的知识产生假设的规则，便于只产生可能合理的假设 方案示例方法：使用规则方案的集合来限制可能合理的规则形式，最符合示教例子的规则被认为是最合理的规则2022-8-28史忠植 人工智能：机器学习17实例学习实例学习 按任务的复杂性划分为：学习单个概念：由系统提供的某个概念的正例和反例，只要求系统归纳出一个概念的描述规则学习多个概念：要求归纳出多个相互独立的概念学习执行多步任务

14、：执行环节使用一个操作序列去完成任务，即执行环节进行任务规划。因此，归纳出的规则应该是进行任务规划的规则2022-8-28史忠植 人工智能：机器学习18变型空间方法变型空间方法 基本思想：以整个规则空间为初始的假设规则集合H，根据示教例子中的信息，对集合H进行一般化或特殊化处理，逐步缩小集合H，最后使H收敛为只含要求的规则。规则空间中的偏序关系：它是按一般性和特殊性来建立的一种概念之间的关系 排序后的变形空间：最上面：是最一般的 规则(概念)，是没有描述的点，所有的例子都符合这一概念 最下面一行的各点：是示教正例对应的概念，每个点的概念只符合一个正例2022-8-28史忠植 人工智能：机器学习

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

16、共同归纳出的最特殊的结果 如果是反例：从S中去掉覆盖该反例的概念；然后修改G为由新反例和G原有元素共同特殊化为最一般的结果(3)若G=S，且是单元集合，则转(4)，否则转(2)(4)输出H中的概念（即G和S）变型空间方法变型空间方法2022-8-28史忠植 人工智能：机器学习21 变型空间法的缺点(1)抗干扰能力差变形空间法是数据驱动的方法，所有数据驱动的方法都难以处理有干扰的训练例子算法得到的概念应满足每个示教例子的要求，所以一个错误的例子会造成很大的影响(2)无法发现析取概念变型空间方法变型空间方法2022-8-28史忠植 人工智能：机器学习22决策树学习决策树学习决策树 通过把实例从根节

17、点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类 树上每个节点说明了对实例的某个属性的测试 节点的每个后继分支对应于该属性的一个可能值正实例：产生正值决策的实例负实例：产生负值决策的实例决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取2022-8-28史忠植 人工智能：机器学习23决策树学习例子决策树学习例子InstancesNo.of wingsBroken wings Living statusWing area/weight Fly120Alive2.5True221Alive2.5False322Alive2.6

18、False420Alive3.0True520Dead3.2False600Alive0False710Alive0False820Alive3.4True920alive2.0False2022-8-28史忠植 人工智能：机器学习24ID3ID3算法算法1、是利用信息论原理对大量样本的属性进行分析和归纳而产生的。2、决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。3、用信息增益（即信息论中的互信息）来选择属性作为决策树的结点。2022-8-28史忠植 人工智能：机器学习25决策树学习n 熵(entro

19、py)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为：Entropy(S)=-pos log2(pos)neg log2(neg)“pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0n 如果分类器有c个不同的输出，则：Entropy(S)=-ci=1pi log2(pi)pi表示S中属于类i的比例2022-8-28史忠植 人工智能：机器学习26决策树学习决策树学习例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)*

20、log2(3/4)=0.81例3：p1=1 p2=0 H3=-1*log21=02022-8-28史忠植 人工智能：机器学习27决策树学习决策树学习n 实例集合S中属性A的信息增益为：Gain(S,A)=Entropy(S)-（|SV|/|S|）Entropy(Sv)vvalues of A Sv表示S的子集，其属性A的值为V2022-8-28史忠植 人工智能：机器学习28决策树学习决策树学习思路：考察任一个属性，计算其熵值；对这个特定属性，考察根据其不同的属性值分成的若干子集；对任意子集，考察不同的类别，计算其熵值并求和；从所有属性中，选择熵值最小（或增益最大）的属性作为当前决策节点。202

21、2-8-28史忠植 人工智能：机器学习292022-8-28史忠植 人工智能：机器学习30内容提要内容提要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 小结小结31类比学习类比学习类比学习 类比学习（learning by analogy）就是通过类比，即通过对相似事物加以比较所进行的一种学习。其推理过程如下：回忆与联想 选择 建立对应关系转换 P(a)Q(a),

22、P(a)P(b)Q(b)Q(a)2022-8-28史忠植 人工智能：机器学习32类比学习主要包括如下四个过程：1.输入一组已知条件和一组未完全确定的条件。2.对两组出入条件寻找其可类比的对应关系。3.根据相似转换的方法，进行映射。4.对类推得到的知识进行校验。类比学习类比学习2022-8-28史忠植 人工智能：机器学习2022-8-28史忠植 人工智能：机器学习33发展简况发展简况 1971年，Kling,R.E.,Stanford Research Institute,发表文章“A Paradigm for Reasoning by Analogy”提出了记忆网模型和案例 检索算法。1981

23、年，Jaime G.Carbonell,Carnegie-Mellon University,发表文章“A Computational 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”，开发了

24、PRODIGY系统。2022-8-28史忠植 人工智能：机器学习34类比的形式定义类比的形式定义ABAB类比问题求解的一般模式2022-8-28史忠植 人工智能：机器学习35转换类比转换类比2022-8-28史忠植 人工智能：机器学习36手段手段-目的分析的问题求解模型目的分析的问题求解模型问题空间：问题空间：1)一组可能的问题组合状态集。2)一个初始状态。3)一个或多个目标状态。4)一组变换规则集5)差别函数6)对可用规则编序的索引函数7)一组全局路径限制8)差别表S-MEAS-MEA算法算法2022-8-28史忠植 人工智能：机器学习371)比较当前状态和目标状态，得出差别2)选择合适的规

25、则，以减少两个状态间的差别3)尽可能应用转换规则，直至完成状态转换。否则保存当前状态，并将MEA算法递归地应用于其它子问题，直到该子问题确认不能满足该规划的前提条件为止。4)当子问题求解后，恢复被保存的当前状态，再继续求解原来的问题2022-8-28史忠植 人工智能：机器学习38类比求解问题的计算模型类比求解问题的计算模型EMEA的T-空间包括：1)转换空间中每个状态是初始问题的潜在解，包括初始状态、最终状态、操作符序列以及路径限制。2)初始状态：O-空间中检索到的相似问题的解序列。3)目标状态：求解新问题的解的规范说明。4)操作符将一个完整的解序列映射到另一个潜在的解序列。5)差别函数：新问

26、题情况下检索解的初始状态、中止状态、路径的约束和应用度之间的差别测度的综合。6)差别表：用来检索T-空间的操作。7)没有路径约束，可用更为复杂的差别函数补偿。8)可用启发式函数作为规则排序。2022-8-28史忠植 人工智能：机器学习39基于案例推理基于案例推理n 人们为了解决一个新问题，先是进行回忆，从记忆中找到一个与新问题相似的案例，然后把该案例 中的有关信息和知识复用到新问题的求解之中。n 在基于案例推理(Case-Based Reasoning,简称CBR)中，把当前所面临的问题或情况称为目标案例(target case)，而把记忆的问题或情况称为源案例(base case)。粗略地说

27、，基于案例 推理就是由目标案例 的提示而获得记忆中的源案例，并由源案例 来指导目标案例 求解的一种策略。2022-8-28史忠植 人工智能：机器学习40 基于案例学习的一般过程基于案例学习的一般过程CBRCBR的过程模型的过程模型 新问题新范例检索保存修正范例解答范例确认解建议解检索建议粗略解调整辩护评批实际评估存储历史范例历史范例范例库2022-8-28史忠植 人工智能：机器学习412022-8-28史忠植 人工智能：机器学习42迁移学习迁移学习迁移学习（transfer learning）的目标是将从一个环境中学到的知识用来帮助新环境中的学习任务。在传统分类学习中，为了保证训练得到的分类模

28、型具有准确性和高可靠性，都有两个基本的假设：用于学习的训练样本与新的测试样本满足独立同分布的条件；必须有足够可利用的训练样本才能学习得到一个好的分类模型。但是，在实际应用中发现要满足这两个条件往往是困难的。迁移学习是运用已有的知识对不同但相关领域问题进行求解。它放宽了传统机器学习中的两个基本假设，目的是迁移已有的知识来解决目标领域中仅有少量有标签样本数据甚至没有的学习问题。2022-8-28史忠植 人工智能：机器学习43内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3 类比学习类比学习5.4 5.4 统计学习统计学习5.5 5.5 强化学习

29、强化学习5.6 5.6 进化计算进化计算5.7 5.7 群体智能群体智能5.8 5.8 知识发现知识发现5.9 5.9 小结小结2022-8-28史忠植 人工智能：机器学习44统计学习统计学习 统计方法是从事物的外在数量上的表现去推断该事物可统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。能的规律性。科学规律性的东西一般总是隐藏得比较深，科学规律性的东西一般总是隐藏得比较深，最初总是从其数量表现上通过统计分析看出一些线索，最初总是从其数量表现上通过统计分析看出一些线索，然后提出一定的假说或学说，作进一步深入的理论研究。然后提出一定的假说或学说，作进一步深入的理论研究。当理论研究当理

30、论研究 提出一定的结论时，往往还需要在实践中加提出一定的结论时，往往还需要在实践中加以验证。就是说，观测一些自然现象或专门安排的实验以验证。就是说，观测一些自然现象或专门安排的实验所得资料，是否与理论相符、在多大的程度上相符、偏所得资料，是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题，都需要用统计分析的方离可能是朝哪个方向等等问题，都需要用统计分析的方法处理。法处理。列联表及列联表分析列联表及列联表分析 研究两个属性变量之间是否有联系 研究步骤：通过问卷调查或统计资料获得属性 变量的信息 整理问卷或统计资料获得列联表数据 通过统计假设检验两个属性变量是 否具有独立性2022-

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

32、工智能：机器学习47逻辑变换逻辑变换 logistic变换 Logistic回归模型 ),(1ln ppqqxxpp 1101ln优势比优势比2022-8-28史忠植 人工智能：机器学习48概率概率p p的预测的预测 P与多因素之间的关系预测qqqqxxxxeep 1101101)(11011qqxxep qqxxpp 1101ln2022-8-28史忠植 人工智能：机器学习49P P与单因素之间的关系图与单因素之间的关系图px1xxeep10101 01 最可能成功范围最可能成功范围最不可能成功范围最不可能成功范围2022-8-28史忠植 人工智能：机器学习50回归系数的含义回归系数的含义

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

34、他机器学习问题中。2022-8-28史忠植 人工智能：机器学习52统计学习问题统计学习问题 学习问题的表示学习的目的就是，在联合概率分布函数F(x,y)未知、所有可用的信息都包含在训练集中的情况下，寻找函数f(x,w0)，使它（在函数类f(x,w)，(w W）上最小化风险泛函 模式别别问题),(),(,()(yxdFwxfyLwRw)f(x,y1w)f(x,y ,0),(,(，若若wxfyL2022-8-28史忠植 人工智能：机器学习53经验风险最小化原则经验风险最小化原则(ERM)(ERM)最小化经验风险(训练样本错误率)NiiiempwxfdLnwR1),(,(1)(用ERM准则代替期望风

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

36、。)()()(hnwRwRemp2022-8-28史忠植 人工智能：机器学习55结构风险最小化原则结构风险最小化原则 函数集 Fk=F(x,w);wWk,k=1,2,n F1 F2 Fn VC维：h1h2hn 在使保证风险（风险的上界）最小的子集中选择使经验风险最小的函数2022-8-28史忠植 人工智能：机器学习562022-8-28史忠植 人工智能：机器学习57 Sn S*经验风险经验风险Empirical risk置信范围置信范围Confidence interval风险界限风险界限Bound on the riskh1h*hnhS1S*Sn结构风险最小化归纳原则结构风险最小化归纳原则(

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

38、,kkkkvuavuKvuK,0g 0,dudvvgugvuK duug2NRC 2022-8-28史忠植 人工智能：机器学习60特征空间与核函数特征空间与核函数nMercer核多项式核高斯径向基函数核Sigmoid核（只在部分参数值情况下才满足核函数的定义）2022-8-28史忠植 人工智能：机器学习612022-8-28史忠植 人工智能：机器学习62提升方法提升方法 弱学习机（weak learner):对一定分布的训练样本给出假设（仅仅强于随机猜测）根据有云猜测可能会下雨 强学习机（strong learner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almos

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

40、的假设X1?1:-1 弱假设弱假设2022-8-28史忠植 人工智能：机器学习65提升流程提升流程(loop2)(loop2)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Y3?1:-1 弱假设弱假设2022-8-28史忠植 人工智能：机器学习66提升流程提升流程(loop3)(loop3)强学习机弱学习机原始训练集原始训练集加权后的训练集加权后的训练集加权后的假设加权后的假设Z7?1:-1弱假设弱假设2022-8-28史忠植 人工智能：机器学习67内容提要内容提要5.1 5.1 机器学习概述机器学习概述5.2 5.2 归纳学习归纳学习5.3 5.3

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

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

43、值函数指出环境中一个状态的长期的期望值。模型：是抓住环境行为的方面的一个机制。模型让我们在没有实际试验它们的情况下估计未来可能的动作。2022-8-28史忠植 人工智能：机器学习692022-8-28史忠植 人工智能：机器学习70强化学习模型强化学习模型i:input 输入 r:reward 奖励s:state 状态 a:action 动作状态 sisi+1ri+1奖励 ri动作动作 aia0a1a2s0s1s2s32022-8-28史忠植 人工智能：机器学习71学习自动机学习自动机在强化学习方法中，学习自动机是最普通的方法。这种系统的学习机制包括两个模块：学习自动机和环境。学习过程是根据环境

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

45、对Q学习中的一步：),(),(MAX),()1(),(11tttatttttasQasQrcasQcasQ (10.15)其中c和都1，rt+1是状态st+1的奖励。2022-8-28史忠植 人工智能：机器学习74内容提要内容提要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-8-28史忠植 人工智能：机器学习75进化计算进化计算进化计算(evol

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

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

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

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

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

51、能：机器学习84 进化规划进化规划 进化规划(evolutionary programming，又译为进化程序设计)的过程,可理解为从所有可能的计算机程序形成的空间中,搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。2022-8-28史忠植 人工智能：机器学习85进化规划步骤1.产生出初始群体,它由关于问题(计算机程序)的函数随机组合而成。2.迭代完成下述子步骤，直至满足选种标准为止:1)执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值2)应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操

52、作作用于该计算机程序个体。把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序,创造出新的计算机程序个体。3.在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。2022-8-28史忠植 人工智能：机器学习86进化计算进化计算进化计算(evolutionary computation)是研究利用自然进化和适应思想的计算系统。达尔文进化论是一种稳健的搜索和优化机制，对计算机科学，特别是对人工智能的发展产生了很大的影响。大多数生物体是通过自然选择和有性生殖进行进化。自然选择决定了群体中哪些个体能够生存和繁殖，有性生殖保证了后代基因中的混合和重

53、组。自然选择的法则是适应者生存，不适应者被淘汰,简言之为优生劣汰。2022-8-28史忠植 人工智能：机器学习87内容提要内容提要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-8-28史忠植 人工智能：机器学习88群体智能群体智能n 指无智能的个体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为复杂问题求解提供了基础。n

54、特点 分布式：能够适应当前网络环境下的工作状态;鲁棒性：没有中心的控制与数据，个体的故障不影响整个问题的求解;扩充性：个体的增加，系统的通信开销增加小;简单性：个体简单，实现也比较简单。n提出蚁群系统提出蚁群系统 1992年，意大利学者M.Dorigo在其博士论文中提出蚁群系统（Ant System）。近年来，M.Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术蚁群优化（ant colony optimization,ACO）。2022-8-28史忠植 人工智能：机器学习89 蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到

55、C点。蚁巢蚁巢食物食物2022-8-28史忠植 人工智能：机器学习90 最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）蚁巢蚁巢食物食物2022-8-28史忠植 人工智能：机器学习912022-8-28史忠植 人工智能：机器学习92蚁群算法模型蚁群算法模型211)(fkkpp22fkfpd 基本模型0)(0/1)(0)(/1)(1iiiiofkofofkkofPdkofkofofkofPpiiii/1)(0/1)(0)(10)(1l简化模型简化模型n由由James KenneyJames Kenney（社会心理学博士）和（社会心理学博士）和Russ Russ EberhartEberha

56、rt（电子工程学博士，（电子工程学博士，http:/www.engr.iupui.edu/eberhart/http:/www.engr.iupui.edu/eberhart/）于）于19951995年提出粒子群算法（年提出粒子群算法（Particle Particle Swarm OptimizationSwarm Optimization,PSO,PSO）n源于对鸟群捕食行为的研究，是基于迭代的源于对鸟群捕食行为的研究，是基于迭代的方法方法n简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少粒子群优化粒子群优化2022-8-28史忠植 人工智能：机器学习93n鸟群：假

57、设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。nPSO算法 每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。粒子群优化粒子群优化2022-8-28史忠植 人工智能：机器学习94n粒子速度和位置的更新 假设在D维搜索空间中，有m个粒子；其中第i个粒子的位置为矢量 其飞翔速度也是一个矢量，记为 第i个粒子搜索到的最优位置为 整个粒子群搜索到的最优位置为 第i个粒子的位置和速度更新为：Ddmivxxxprandcxprandcwvvkidkidkidkidg

58、bestkididkidkid,2,1 ;,2,1 )()()()(11211),(21iDiiipppp),(21gbestDgbestgbestgbestpppp),(21iDiiixxxx),(21iDiiivvvv粒子群优化算法粒子群优化算法2022-8-28史忠植 人工智能：机器学习95n粒子速度和位置的更新 其中，w称为惯性权重，c1和c2为两个正常数，称 为加速因子。将 vidk 限制在一个最大速 度 vmax 内。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211xkvkppg

59、bestxk+1vk+1kkk+1k+1粒子群优化算法粒子群优化算法2022-8-28史忠植 人工智能：机器学习96n粒子速度和位置的更新 Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid,2,1 ;,2,1 )()()()(11211“惯性部分”，对自身运动状态的信任“认知部分”，对微粒本身的思考，即来源于自己经验的部分“社会部分”，微粒间的信息共享，来源于群体中的其它优秀微粒的经验粒子群优化算法粒子群优化算法2022-8-28史忠植 人工智能：机器学习97StartInitialize particles with random po

60、sition and velocity vectors.For each particles position(xi)evaluate fitnessIf fitness(xi)better than fitness(p)then p=xiLoop until all particles exhaustSet best of ps as gBestUpdate particles velocity and positionLoop until max iterStop:giving gBest,optimal solution.粒子群优化算法流程粒子群优化算法流程2022-8-28史忠植 人工

61、智能：机器学习982022-8-28史忠植 人工智能：机器学习99内容提要内容提要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-8-28史忠植 人工智能：机器学习100 数据库知识发现数据库知识发现 目前,大数据知识发现(Knowledge Discovery from Datasets KDD)的研究非常活跃，极为应用广泛。该术语于1989年出

62、现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”2022-8-28史忠植 人工智能：机器学习101 不同的术语名称不同的术语名称 知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。知识发现:人工智能和机器学习界。数据挖掘(data mining):统计界、数据分析、数据库和管理信息系统界q知识抽取(information extraction)、q信息发现(information discovery)、q智能数据分析(intelligent data analysis)、q探索式数据分析(explor

63、atory data analysis)q信息收获(information harvesting)q数据考古(data archeology)2022-8-28史忠植 人工智能：机器学习102 知识发现步骤知识发现步骤2022-8-28史忠植 人工智能：机器学习103知识发现的主要任务知识发现的主要任务 数据总结：对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。分类：根据分类模型对数据集合分类。分类属于监督学习，一般需要有一个训练样本数据集作为输入。聚类：根据数据的不同特征，将其划分为不同的类。无监

64、督学习2022-8-28史忠植 人工智能：机器学习104知识发现的主要任务知识发现的主要任务 相关性分析：发现特征之间或数据之间的相互依赖关系关联规则 偏差分析：基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。建模：构造描述一种活动或状态的数学模型 2022-8-28史忠植 人工智能：机器学习105知识发现的方法知识发现的方法 统计方法：传统方法：回归分析、判别分析、聚类分析、探索性分析 模糊集(fuzzy set)Zadeh 1965 支持向量机(Support Vector Machine)Vapnik 90年代初 粗糙集(Rough Se

65、t)Pawlak 80年代初2022-8-28史忠植 人工智能：机器学习106知识发现的方法知识发现的方法 机器学习：规则归纳：AQ算法 决策树：ID3、C4.5 范例推理:CBR 遗传算法:GA 贝叶斯信念网络2022-8-28史忠植 人工智能：机器学习107知识发现的方法知识发现的方法 神经计算：神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。常用的模型：Hopfield网 多层感知机 自组织特征映射 反传网络 可视化：2022-8-28史忠植 人工智能：机器学习108知识发现的技术难点 动态变化的数据 噪声 数据不完整 冗余信息 数据稀疏 超大数据量109小结小结 n 机器学习是研究如何使计算机具有学习能力的一个研究领域，其最终目标是要使计算机能像人一样进行学习，并且能通过学习获取知识和技能，不断改善性能，实现自我完善。n 本章介绍了主要的机器学习方法：归纳学习、类比学习、统计学习、强化学习、进化计算、群体智能等方法。最后概述了知识发现。2022-8-28史忠植 人工智能：机器学习2022-8-28史忠植 人工智能：机器学习110 Thank You人工智能 http:/