人工智能：第6章 机器学习

1、第六章 机器学习主要内容机器学习概述归纳学习决策树学习基于实例的学习强化学习小结 6.1.1 学习与机器学习 学习的概念，代表性观点(1)心理学的解释学习是指（人或动物）依靠经验的获得而使行为持久变化的过程。(2)西蒙（Simon,1983） 学习就是系统中的适应性变化，这种变化使系统在重复同样工作或类似工作时，能够做得更好。(3) Tom M. Mitchell（机器学习） 对于某类任务T和性能度P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么，我们称这个计算机程序从经验E中学习。6.1 机器学习概述 6.1.1 机器学习的概念学习的一般性解释学习是对某一个特定目标的知识

2、获取的智能过程，系统的内部表现为获得知识、积累经验、发现规律，外部表现为改进性能、适应环境、实现自我完善。机器学习机器模拟人类的学习活动获取知识和技能的理论和方法改善系统性能6.1 机器学习概述* 1. 具有适当的学习环境指学习系统进行学习时所必需的信息来源。 2. 具有一定的学习能力学习系统应模拟人的学习过程，使系统通过与环境反复多次相互作用，逐步学到有关知识，要使系统在学习过程中通过实践验证、评价所学知识的正确性。 3. 能用所学的知识解决问题学习系统能把学到的信息用于对未来的估计、分类、决策和控制。一个机器学习系统应具有特点*4. 能提高系统的性能 提高系统的性能是学习系统最终目标。通过

3、学习，系统随之增长知识，提高解决问题的能力，使之能完成原来不能完成的任务，或者比原来做得更好。学习系统至少应有环境、知识库、学习环节和执行环节四个基本部分。一种典型的机器学习系统-迪特里奇(Dietterich)学习模型 迪特里奇（Dietterich）学习模型 环境向系统的学习部件提供某些信息， 学习环节对环境提供的信息进行整理、分析归纳或类比，形成知识，放入/修改知识库。 知识库存储经过加工后的信息（即知识）。 执行环节根据知识库完成任务，同时把获得的信息反馈给学习部件。学习环节再利用反馈信息对知识进行评价，进一步改善执行环节的行为。环境学习单元知识库执行单元简单的学习模型 1神经元模型研

4、究阶段神经元模型以及基于该模型的决策论和控制论;机器学习方法通过监督（有教师指导的）学习来实现神经元间连接权的自适应调整，产生线性的模式分类和联想记忆能力。代表性的工作FRosenblaft的感知机（1958年）WSMcCullouch与WPitts的模式拟神经元理论（1943年）6.1.2 机器学习的发展简史*神经元模型*神经网络圆圈代表神经元x1x2x3y2隐含层WiWiy12符号概念获取研究阶段心理学和人类学习的模似占有主导地位，其特点是使用符号而不是数值表示来研究学习问题，其目标是用学习来表达高级知识的符号描述。主要技术是概念获取和各种模式识别系统的应用代表性的工作是温斯顿的基于示例

5、归纳的结构化概念学习系统。3基于知识的各种学习系统研究阶段第三阶段始于70年代中期不再局限于构造概念学习系统和获取上下文知识结合了问题求解中的学习、概念聚类、类比推理及机器发现的工作有关学习方法: 示例学习、示教学习、 观察和发现学习、类比学习、基于解释的学习。工作特点强调应用面向任务的知识和指导学习过程的约束，应用启发式知识于学习任务的生成和选择，包括提出收集数据的方式、选择要获取的概念、控制系统的注意力。4联结学习和符号学习共同发展阶段80年代后期以来，发现了用隐单元来计算和学习非线性函数的方法，克服了早期神经元模型的局限性神经网络的物理实现(计算机硬件)，在声音识别、图像处理等领域，取得

6、了很大成功符号学习杰出的工作有分析学习（特别是解释学习）、遗传算法、决策树归纳等。*发现了用隐单元来计算和学习非线性函数的方法，克服了早期神经元模型的局限性60 75 6910 x1x2x3y2隐含层WiWiy11. 基于学习策略的分类 （1）模拟人脑的机器学习符号学习：模拟人脑的宏观心理级学习过程，以认知心理学原理为基础，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或规则等。符号学习的典型方法有：记忆学习、示例学习、演绎学习、类比学习、解释学习等。神经网络学习（或连接学习）：模拟人脑的微观生理级学习过程，以脑和神经科学原理为基础，以人工神经网络为函数结

7、构模型，以数值数据为输入，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。 （2）直接采用数学方法的机器学习 主要有统计机器学习。6.1.3 机器学习的分类2. 基于推理策略的分类 （1）归纳学习：应用归纳推理进行学习的方法。是从个别到一般的推理。 （2）解释学习：根据任务所在领域的知识和概念，对当前示例进行分析和求解。 （3）神经学习：基于神经网络的学习。BP神经网络，Hopfield网络。 （4）知识发现：从大量数据中识别出有效的，新颖的，潜在有用的，可被理解的模式的高级处理过程。3. 基于学习方式的分类（1）有导师学习（监督

8、学习）：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。如神经学习，分类学习。（2）无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。（3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。4. 基于数据形式的分类（1）结构化学习：以结构化数据为输入，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规则学习。（2）非结构化学习：以非结构化数据为输入，典型的非结构化学习有类比学习、案例学

9、习、解释学习、文本挖掘、图像挖掘、Web挖掘等。 5. 基于学习目标的分类 （1）概念学习： 学习的目标和结果为概念，典型的概念学习有示例学习。 （2）规则学习： 学习的目标和结果为规则，典型的规则学习有决策树学习。 （3）函数学习： 学习的目标和结果为规则，典型的函数学习有神经网络学习。 （4）类别学习： 学习的目标和结果为对象类，典型的类别学习有聚类分析。 （5）贝叶斯网络学习： 学习的目标和结果是贝叶斯网络，又分为结构学习和参数学习。机器学习的应用：文本分类模型自动挖掘和生成以及动态优化 与自然语言处理的结合在专家系统和智能决策系统的应用 语音识别自动驾驶技术学习分类新的天文结构人机对弈

10、：深蓝，阿尔法狗6.1.4 机器学习的应用与研究目标：研究目标有三个： (1)人类学习过程的认知模型研究人类学习机理的认知模型。(2)通用学习算法通过对人类学习过程的研究，探索各种可能的学习方法，建立起具体应用领域的通用学习算法。(3)构造面向任务的专用学习系统。研究智能系统的建造，解决专门的实际问题。主要内容机器学习概述归纳学习决策树学习基于实例的学习强化学习小结归纳学习 归纳学习(概念学习、经验学习）是符号学习中研究的最为广泛的一种方法。 给定关于某个概念的一系列已知的正例与反例，其任务是从中归纳出一个一般的概念描述。 归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是泛

11、化和特化。 泛化用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。 特化是泛化的相反的操作，用于限制概念描述的应用范围。 6.2.1 归纳学习的基本概念归纳学习指在从大量的经验数据中归纳抽取出一般的判定规则和模式，是从特殊情况推导出一般规则的学习方法。归纳学习的目标是形成合理的能解释已知事实和预见新事实的一般性结论。归纳学习由于依赖于经验数据，因此又称为经验学习，也称为基于相似性的学习。归纳学习的双空间模型如图所示。1.归纳学习的双空间模型*示教者给实例空间提供一些初始示教例子，程序对示教例子进行解释（由于示教例子的形式往往不同于规则形式）再利用被解释的示教例子搜索规则空间

12、。 一般不能一次就从规则空间中搜索到要求的规则，还要找一些新的示教例子，这个过程是选择例子。此过程如此循环，直到搜索到要求的规则。麻雀从地上飞到树枝上鸟会飞鸽子从窗台飞到树上鸟会走归纳学习根据有无导师分成示例学习和观察与发现学习。归纳学习按学习的概念划分为单概念学习和多概念学习两类。概念指用某种描述语言表示的谓词，当应用于概念的正实例时，谓词为真，应用于负实例时为假。从而概念谓词将实例空间划分为正、反两个子集。2.归纳学习方法的分类*基于内容的图像检索正例反例* 按例子的来源分类 例子来源于教师的示例学习 例子来源于学习者本身的示例学习 知道自己的状态，但不清楚所要获取的概念。 例子来源于学习

13、者以外的外部环境的示例学习 按例子的类型分类（哪种好？） 仅利用正例的示例学习 这种学习方法会使推出的概念的外延扩大化。 利用正例和反例的示例学习 这是典型方式，它用正例用来产生概念，用反例来防止概念外延的扩大。 *陈佩斯 孟飞 乐嘉典型的单概念学习系统包括基于数据驱动的变型空间法，ID3方法，基于模型驱动的Induce算法。典型的多概念学习方法和系统有AQ11、DENDRAL和AM程序等。多概念学习任务可以划分成多个单概念学习任务来完成。多概念学习与单概念学习的差别在于多概念学习方法必须解决概念之间的冲突问题。归纳学习方法的分类主要内容机器学习概述归纳学习决策树学习基于实例的学习强化学习小结

14、决策树学习 决策树学习是离散函数的一种树型表示，表示能力强，可以表示任意的离散函数，是一种重要的归纳学习方法。 决策树是实现分治策略的数据结构，通过把实例从根节点排列到某个叶子节点来分类实例，可用于分类和回归。 决策树一个属性节点的输出分枝和该节点的所有可能的检验结果相对应 决策树学习过程实际上是一个构造决策树的过程。当学习完成后，就可以利用这棵决策树对未知事物进行分类决策树决策树是一种依托决策而建立起来的一种树。在机器学习中，决策树是一种预测模型，代表的是一种对象属性与对象值之间的一种映射关系.每一个节点代表某个对象，树中的每一个分叉路径代表某个可能的属性值，而每一个叶子节点则对应从根节点到

15、该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出，如果有多个输出，可以分别建立独立的决策树以处理不同的输出。* 两个输出属性X和Y的样本分类决策树 所有属性值X1和Y=B的样本属于类2 值X1的样本都属于类1。 对于树中的非叶节点， 可以沿着分枝继续分 区样本ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。信息熵在信息增益中，重要性的衡量标准就是看特征

16、能够为分类系统带来多少信息，带来的信息越多，该特征越重要。熵,最早起源于物理学，用来度量一个热力学系统的无序程度。在信息学里面，熵是对不确定性的度量。1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。信息熵假设X是一个取值个数有限的离散随机变量，概率分布为P(X=Xi)=pi,i=1,2,.,n则随机变量X的熵定义为意思是一个变量的变化情况可能越多，那么它携带的信息量就越大。对于分类系统来说，类别C是变量，它的取值是C1,C2,Cn，每一个类别出现的概率分别是P

17、(C1),P(C2),P(Cn).条件熵是收信者在收到信息后对信息源不确定性的度量。条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：它表示收信者收到Y后对X不确定性的估计。 信息增益信息增益是针对一个一个特征而言的，就是看一个特征，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验嫡H(D)与特征A给定条件下D的经验条件嫡H(D|A)之差6.3.3基本的决策树算法ID

18、3ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程*ID3算法的学习过程首先以整个例子集作为决策树的根节点S，并计算S关于每个属性的期望熵（即条件熵）；然后选择能使S的期望熵为最小的一个属性对根节点进行分裂，得到根节点的一层子节点；接着再用同样的方法对这些子节点进行分裂，直至所有叶节点的熵值都下降为0为止。得到一棵与训练例子集对应的熵为0的决策树，该树中每一条从根节点到叶节点的路径，都代表了一个分类过程，即

19、决策过程。*节点优先选择哪个属性值的原理根据的假设：决策树的复杂度和所给属性值表达的信息量是密切相关的。采用信息论方法：对样本分类时，节点应选的分类属性是给出最高信息增益的属性，即信息熵最小化的属性。*2C4.5算法（分类属性扩展到数字）C4.5算法最重要的部分是由一组训练样本生成一个初始决策树的过程。该算法生成一个决策树形式的分类器，决策树节点具有两种类型的结构：一个叶节点，表示一个类，一个决策点，它指定要在单个属性值上进行的检验，对检验的每个可能输出有一个分枝和子树。*从该树的根节点开始，移动样本直至达叶节点。在每个非叶节点处，确定属性检验结果，选择子树。例如，图6-7a中的决策树的分类模

20、型问题，待分类的样本如图6-7b所示，然后，该算法将生成一条通过节点A，C，F（叶节点）的路径直到得出最终分类决策，即类2为止。决策树用来对一个新样本进行分类* 图6-7 基于决策树模型的一个新样本的分类银行贷款不贷没欠款贷现考虑鸟是否能飞的实例，InstancesNo. of WingsBroken WingsLiving statusarea/weightFly120alive2.5T221alive2.5F322alive2.6F420alive3.0T520dead3.2F600alive0F710alive0F820alive3.4T920alive2.0F对于上表给出的例子,选取整

21、个训练集为训练窗口,有3个正实例,6个负实例,采用记号3+,6-表示总的样本数据。则S的熵为计算属性Living Status的信息增益，该属性为值域为(alive, dead),则 S=3+,6-, Salive=3+,5-, Sdead=0+,1- 先计算Entropy(Salive), Entropy(Sdead)如下:ID3算法-最佳分类属性-例子分析ID3算法-最佳分类属性-例子分析所以,living status的信息增益为ID3算法-最佳分类属性-例子分析同样可计算其他属性的信息增益，然后根据最小熵原理，选取信息量最大的属性作为决策树的根节点属性。NoNoNoNoYesNoNo2

22、10210alivedead2.52.5No. of WingsBroken WingsStatusArea/weight图6.8 鸟飞的决策树 ID3算法的优点：分类和测试速度快，特别适用于大数据库的分类问题。ID3算法的缺点： 第一：决策树的知识表示没有规则易于理解。 第二：两颗决策树比较是否等价问题是子图匹配问题，是NP完全的。 第三：不能处理未知属性值的情况。 第四：对噪声问题没有好的处理办法。ID3算法-最佳分类属性-优缺点主要内容机器学习概述归纳学习(变型空间和候选消除算法)决策树学习基于实例的学习强化学习小结 采用保存实例本身的方法来表达从实例集里提取出的知识，并将类未知的新实例

23、与现有的类已知的实例联系起来进行操作。 直接在样本上工作，不需要建立规则。 基于实例的学习方法包括最近邻法、局部加权回归法、基于范例的推理法等等。 基于实例的学习只是简单地把训练样例存储起来，没有提取训练数据的模型，称为消极学习法Lazy。基于实例的学习6.4.1 K-近邻算法 基于实例的机器学习方法把实例表示为n维欧式空间Rn中的实数点，使用欧氏距离函数，把任意的实例x表示为这样的特征向量：，那么两个实例xi和xj之间的距离定义为d(xi,xj),则 d(xi,xj)=算法6.4 逼近离散值函数f: RnV的k-近邻算法：训练算法：将每个训练样例加入到列表 training_examples

24、分类算法： （1）给定一个要分类的查询实例xq （2）在training_examples中选出最靠近xq 的k个实例，并用x1.xk表示 （3）返回 离散的k-近邻算法作简单修改后可用于逼近连续值的目标函数。即计算k个最接近样例的平均值，而不是计算其中的最普遍的值，为逼近f：RnR，计算式如下： 6.4.2 距离加权最近邻法 对k-近邻算法的一个改进是对k个近邻的贡献加权，越近的距离赋予越大的权值，比如：也可以用类似的方式对实值目标函数进行距离加权 6.4.3 基于范例的学习 解决一个新问题：回忆，找到一个范例，复用到新问题中。 基于范例推理：把当前所面临的问题或情况称为目标范例，把记忆的问

25、题或情况称为源范例，由目标范例的提示而获得记忆中的源范例，并由源范例来指导目标范例求解的一种策略. 1.范例的获取比规则获取要容易，大大简化了知识获取。 2.对过去的求解结果的复用，不再从头推导，提高问题的求解效率。 3.过去求解成功或失败的经历指导当前求解，改善了求解的质量。 适用于目前没有或根本不存在可以通过计算推导来解决的问题，基于范例推理能很好发挥作用。1.基于范例推理的一般过程（1）联想记忆（2）类比映射（3）获得求解方案（4）评价图6.9 基于范例推理的结构在基于范例的学习中要解决的主要问题有 (1) 范例表示 (2) 分析模型 (3) 范例检索 (4) 类比映射 (5) 类比转换

26、 (6) 解释过程 (7) 范例修补 (8) 类比验证(9) 范例保存 2.范例的表示 一个记忆网便是以语义记忆单元（SMU）为结点，以语义记忆单元间的各种关系为连接建立起来的网络。 SMU = SMU_NAME slot Constraint slots Taxonomy slots Causality slots Similarity slots Partonomy slots Case slots Theory slots 3范例组织 (1)范例内容 问题或情景描述。包括：推理器的目标，任务，周围世界或环境与可能解决方案相关的所有特征。解决方案的内容是问题如何在一特定情形下得到解决。它可

27、能是对问题的简单解答，也可能是得出解答的推导过程。结果。记录了实施解决方案后的结果情况，是失败还是成功。用于给出建议解。(2)范例索引 建立范例索引有三个原则：索引与具体领域有关。范例索引则要考虑是否有利于将来的范例检索，它决定了针对某个具体的问题哪些范例被复用；索引应该有一定的抽象或泛化程度。能灵活处理以后可能遇到的各种情景。索引应该有一定的具体性。能在以后被容易地识别出来，太抽象则各个范例之间的差别将被消除。4范例的检索范例检索从范例库中找到一个或多个与当前问题最相似的范例；知识库不是以前专家系统中的规则库，它是由领域专家以前解决过的一些问题组成。范例库中的每一个范例包括以前问题的一般描述

28、即情景和解法。一个新范例并入范例库时，同时也建立了关于这个范例的主要特征的索引。当接受了一个求解新问题的要求后，CBR利用相似度知识和特征索引从范例库中找出与当前问题相关的最佳范例。范例检索通过三个子过程，即特征辩识、初步匹配，最佳选定来实现。5范例的复用(1)替换法 替换法是把旧解中的相关值，做相应替换而形成新解。有重新例化、参数调整、局部搜索、查询、特定搜索、基于范例的替换等。(2)转换法 常识转换法（common-sense transformation）是使用明白易懂的常识性启发式从旧解中替换、删除或增加某些组成部分。模型制导修补法（model-guided repair）是另一种转换

29、法，它是通过因果模型来指导如何转换。故障诊断中就经常使用这种方法。 5范例的复用(3)特定目标驱动法通过评价近似解，修正特定目标驱动的启发式知识。 (4)派生重演使用过去的推导来推导出新解。同基于范例替换相比，派生重演使用的则是一种基于范例的修正手段。主要内容机器学习概述归纳学习(变型空间和候选消除算法)决策树学习基于实例的学习强化学习小结强化学习(再励学习，评价学习)是一种重要的机器学习方法。分为三种类型：非监督学习、监督学习和强化学习强化学习：从环境到行为映射的学习，目的是使奖励信号(强化信号)函数值最大。不同于监督学习的教师信号，强化学习中由环境提供的强化信号是对产生动作的好坏作一种评价

30、，而不是告诉强化学习系统如何去产生正确的动作。外部环境提供的信息很少，RLS必须靠自身的经历进行学习。通过这种方式，RLS在行动-评价的环境中获得知识，改进行动方案以适应环境强化学习RLS强化学习要解决的问题：主体怎样通过学习选择能达到其目标的最优动作。当主体在其环境中做出每个动作，施教者提供奖励或惩罚信息，以表示结果状态的正确与否。例如，在进行棋类对弈时，施教者可在游戏胜利时给出正回报，在游戏失败时给出负回报，其他时候给出零回报。主体的任务是从这个非直接的有延迟的回报中学习，以便后续动作产生最大的累积回报。强化学习RLS6.5.1 强化学习模型si+1ri+1报酬ri主体环境状态si行动ai 图6.10 强化学习模型 Agent状态回报动作 环 境a0a2a1s1s0s2r1r0r2目标：学习选择动作使下式最大化 r0 + r1 + 2r2 + 其中01Agent 的任务是学习一个控制策略 ：S A 它使这些回报的和的期望值最大。6.5.2 马尔可夫决策过程主体可感知到其环境的不同状态集合S，可执行的动作集合A。在每个离散时间步t，主体感知