第七章机器学习课件.ppt

第七章 机器学习,7.1 机器学习的定义、研究意义与发展历史 7.2 机器学习的主要策略与基本结构7.3 7.7 几种常用的学习方法7.8 知识发现7.9 小结,7.1 机器学习的定义和发展历史,学习 学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。（人工智能大师西蒙的观点）,学习的主要表现：,1.获得新知识2.从感性认识发展到理性认识3.通过反复实践,对学习的4种理解：1.学习是一个系统改进其自身性能的任何过程。2.学习是获取明显知识的过程3.学习是技巧的获取4.学习是理论、假说的形成过程,学习的一般模式,7.1.1 机器学习的定义机器学习的定义 顾名思义,机器学习是研究如何使用机器来模拟人类学习活动的一门学科。 稍为严格的提法是：机器学习是一门研究机器获取新知识和新技 能,并识别现有知识的学问。,7.1.2机器学习的发展史,机器学习的发展分为4个时期第一阶段是在50年代中叶到60年代中叶，属于热烈时期。第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。第三阶段从70年代中叶至80年代中叶，称为复兴时期。机器学习的最新阶段始于1986年 。,机器学习进入新阶段的表现机器学习已成为新的边缘学科并在高校形成课程。综合各种学习方法 机器学习与人工智能问题的统一性观点正在形成。各种学习方法的应用范围不断扩大。数据挖掘和知识发现的研究已形成热潮 。与机器学习有关的学术活动空前活跃 。,2. 机器学习的分类 目前常用的分类方法：,机械式学习指导式学习示例学习类比学习解释学习,基于演绎的学习基于归纳的学习,归纳学习分析学习连接学习遗传算法,(1) 按学习方法分类,(2) 按推理方式分类,(3) 按综合属性分类,7. 2 机器学习的主要策略和基本结构,7.2.1 机器学习的主要策略 按照学习中使用推理的多少，机器学习所采用的策略大体上可分为4种机械学习、通过传授学习、类比学习和通过事例学习。机械学习传授学习策略类比学习系统通过事例学习策略,7.2.2 机器学习系统的基本结构 1.学习系统的基本结构,根据西蒙的学习定义，可建立起上图所示的简单学习模型。环境向系统的学习部分提供信息；学习利用信息修改知识库，以增进系统执行部分完成任务的效能；知识库存放指导执行部分动作的一般原则；执行根据知识库完成任务，并把所获信息反馈学习部分。,2.影响学习系统设计的要素影响学习系统设计的最重要因素是环境向系统提供的信息，或者更具体地说是信息的质量。 知识库是影响学习系统设计的第二个因素。知识的表示有特征向量、一阶逻辑语句、产生式规则、语义网络和框架等多种形式。,7.3 机械学习1.机械学习模式 机器学习是最简单的学习方法，也是一种最基本的学习过程。 机器学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。,可把机械学习系统的执行部分抽象地看成某个函数，机械学习在存储器中简单地记忆存储对(X1,X2,Xn),(Y1,Y2,Yp)。当需要f(X1,X2,Xn)时,执行部分就从存储器中把(Y1,Y2,Yp)简单地检索出来而不是重新计算它。这种简单的学习模式如下：,Lenat，Hayes-Roth，和Klahr等人于1979年关于机械学习提出一种有趣的观点，见图7.2。, 机械学习就是记忆； 学习元所做的工作仅仅是存储新的知识； 需要时检索出来即可。 例如： 某个计算的输入是：( x1 , x2 , , xn ) ， 计算后输出是：( y1 , y2 , , yn ), 如果经评价后得知该结果正确，则把联想对: ( x1 , x2 , , xn ), ( y1 , y2 , , yn ) 存入知识库，当以后需要做同样的计算时，只要从知识库中检索出来即可，而不需要重新计算了。 (2) 利弊 机械式学习实质上是用存储空间来换取处理时间，虽然节省了计算时间，但却多占了存储空间。当因学习而积累的知识逐渐增多时，占用的空间就会越来越大，检索的效率也就随之下降。,2.机械学习的主要问题存储组织信息：要采用适当的存储方式，使检索速度尽可能地快。环境的稳定性与存储信息的适用性问题： 机械学习系统必须保证所保存的信息适应于外界环境变化的需要。存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率。,7.4 归纳学习,归纳学习（induction learning）是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察与发现学习。环境提供的信息是关于实际例子的输入与输出描述； 输入数据、输出结果规定了一个特殊的知识原则(特殊知识); 学习元从这些特殊知识中假设和归纳出一般性知识。7.4.1 归纳学习的模式和规则 归纳学习的模式,归纳学习包括示例学习和观察发现学习。1.归纳推理（1）归纳推理是应用归纳方法所进行的推理，即从足够多的事例中归纳出一般性的知识，它是一种从个别到一般的推理。常用的归纳推理方法有： 枚举归纳 联想归纳 类比归纳,. 枚举归纳 设a1, a2, 是某类事物 A 中的具体事物，若已知 a1, a2, , an 都有属性 P ,并且没有发生反例，当 n 足够大时，就可得出“ A 中所有事物都有属性 P ” 的结论。 这是一种从个别事例归纳出一般性知识的方法， “ A 中所有事物都有属性 P ” 是通过归纳得到的新知识。 例如：设有如下已知事例： 张三是足球运动员，他的体格健壮。 李四是足球运动员，他的体格健壮。 赵十是足球运动员，他的体格健壮。 当事例足够多时，就可归纳出一个一般性知识： 凡是足球运动员，他的体格一定健壮。 考虑到可能会出现反例，可给这条知识增加一个可信度： 凡是足球运动员，他的体格一定健壮 （0.95）。,. 联想归纳 若已知两个事物 a 与 b 有 n 个属性相同或相似 ，即： a 具有属性 P1 ，b也有属性 P1 a 具有属性 P2 ，b也有属性 P2 。 a 具有属性 Pn ，b也有属性 Pn 并且还发现， a 具有属性 Pn+1 ，则当 n 足够大时，可归纳出： b 也有属性 Pn+1 这一新知识。 例如：通过观察发现，两个孪生兄弟都有相同的身高、体重、相貌， 都喜欢唱歌、跳舞，且喜欢吃相同的食物，而且发现其中一人喜欢画山水画，虽然我们没有看到另一个也喜欢画山水画，但我们很容易联想到另一个“也喜欢画山水画”，这就是联想归纳。 由于联想归纳是一种主观不充分置信推理，因而经归纳得出的结论 可能会有错误。,2 归纳概括规则,取消部分条件放松条件,沿概念树上溯 S为所有条件中的L值在概念分层树上最近的共同祖先，这是一种从个别推论总体的方法。,形成闭合区域 L为具有线性关系的描述项，a,b是其特殊值。S表示a,b范围内的值。,将常量转化成变量 这种规则仅从事例中提取各个描述项之间的某种相互关系，而忽略其他关系信息。,3 示例学习（Learning by Examples） 示例学习是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。示例学习又称为实例学习。是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法。 在这种学习方法中，外部环境（教师）提供的是一组例子（正例和反例），这些例子实际上是一组特殊的知识，每一个例子表达了仅适用于该例子的知识，示例学习就是要从这些特殊知识中归纳出适合于更大范围的一般性知识。,例如：我们用一批动物作为示例，并且告诉学习系统哪一个动物是“马”，哪一个动物不是，当示例足够多时，学习系统就能概括 出关于“马”的概念模型，使自己能识别“马”。这一学习过程就是示例学习。 例如： 假设示例空间存放有如下的三个示例：示例1：（0，2，7） 示例2：（6，-1，10） 示例3：（-1，-5，-16） 这是三个三维向量，表示空间中的三个点。现要求求出过这三个点的曲线。 对于这一问题可采用通常的曲线拟合技术，归纳出规则:（x,y,2x+3y+1）即z=2x+3y+1,. 示例学习的学习模型 其学习过程是： 首先从示例空间（环境）中选择合适的训练示例，然后经过 解释归纳出一般性的知识，最后再从示例空间中选择更多的示例对它进行验证，直到得到可实用的知识为止。 . 常用的归纳算法 强化/弱化算法： 用于归纳产生式规则：学习元的输出为规则； 强化指使规则前提取值范围加大：扩大范围； 弱化指使规则前提取值范围变小：缩小范围；,找一个规则模式,用实例匹配,判断规则前提范围大？,弱化前提,强化前提,获取一般性规则,Stop,判断规则前提范围小？,Y,Y,N,N,4.观察与发现学习 观察与发现学习分为观察学习与机器发现两种。前者用于对事例进行概念聚类，形成概念描述；后者用于发现规律，产生定律或规则。,(1) 概念聚类 把事例按一定的方式和准则进行分组，使不同的组代表不同的概念，并且对每一个组进行特征概括，得到一个概念的语义符号描述。例如，用K次平均算法实现概念聚类。,(2) 机器发现经验发现从经验数据中发现规律和定律；知识发现从观察的事例中发现新的知识。,7.5 类比学习,7.5.1 类比推理和类比学习方式 类比学习（learning by analogy）就是通过类比，即通过对相似事物加以比较所进行的一种学习 。 类比推理是由新情况（T）与已知情况（S）在某些方面的相似，来推出它们在其他相关方面的相似。 其推理过程如下 ：回忆与联想- 选择 - 建立对应关系-转换,1.类比推理过程(1) 回忆与联想 通过回忆与联想，在S中找出与当前情况相似的情况，这些情况是过去已经处理过的，有现成的解决方法及相关的知识。(2) 选择 从找出的相似情况中选出与当前情况最相似的情况及其有关知识，以便提高推理的可靠性。(3) 建立对应关系 在S与T的相似情况之间建立相似元素的对应关系，并建立起相应的映射。(4) 转换 根据映射，把S中的有关知识引到T中来，从而建立起求解当前问题的方法或者学习到关于T的新知识。,类比学习： 指在几个对象（实体）间检测相似性； 根据一方对象（实体）所具有的事实和知识，推出相似对象所具有的事实与知识； 环境提供相关领域知识（与当前所学习的问题间有相似性）; 学习元找出相似性并得出相似准则/知识。 2 类比推理 类比学习的基础是类比推理。 所谓类比推理是指： 由新情况与记忆中的已知情况在某些方面相似，从而推出它们在其它方面也相似。,类比推理是在两个相似域之间进行的： 一个是已经认识的域，它包括过去曾经解决过且与当前待解决问题类似的问题以及相关知识，称为源域，记做 S； 另一个是当前尚未完全认识的域，它是遇到的新问题，称为目标域，记做 T； 类比推理的目的是： 从 S 中选出与当前问题最近似的问题及其求解方法来求解当前问题，或者建立起目标域中已有命题间的联系，形成新知识。,3. 通过类比推理实现学习的步骤(1) 找出源域与目标域的相似性质P，找出源域中另一个性质Q和性质P对元素a的关系：P(a)Q(a)。(2) 在源域中推广P和Q的关系为一般关系，即对于所有变量x来说，存在P(x)Q(x)。(3) 从源域和目标域映射关系，得到目标域的新性质，即对于目标域的所有变量x来说，存在P(x)Q(x)。(4) 利用假言推理：P(b)，P(x)Q(x) Q(b)，最后得出b具有性质Q。（符号表示类比推理）,类比学习实际上是演绎学习和归纳学习的组合。步骤(2)是一个归纳过程，即从个别现象推断出一般规律；而步骤(4)则是一个演绎过程，即从一般规律找出个别现象。例 学生做习题时，往往在例题和习题之间进行对比，以发现相似之处，然后利用这种相似关系解决习题中的问题。,7.5.2 类比学习过程与研究类型,类比学习主要包括如下四个过程：输入一组已知条件和一组未完全确定的条件 。对两组出入条件寻找其可类比的对应关系。根据相似转换的方法，进行映射。对类推得到的知识进行校验。,类比学习的研究可分为两大类： (1) 问题求解型的类比学习 (2) 预测推定型的类比学习。它又分为两种方式： 一是传统的类比法 另一是因果关系型的类比,7.6 解释学习,7.6.1 解释学习过程和算法 1986年米切尔（Mitchell）等人为基于解释的学习提出了一个统一的算法EBG：,解释学习根据任务所在领域知识和正在学习的概念知识，对当前实例进行分析和求解，得出一个表征求解过程的因果解释树，以获取新的知识。解释学习步骤 利用基于解释的方法对训练实例进行分析与解释，以说明它是目标概念的一个实例。 对实例的结构进行概括性解释，建立该训练实例的一个解释结构以满足所学概念的定义；解释结构的各个叶结点应符合可操作性准则，且使这种解释比最初的例子适用于更大的一类例子。 从解释结构中识别出训练实例的特性，并从中得到更大一类例子的概括性描述，获取一般控制知识。,EBG求解问题的形式可描述于下:,给定：(1) 目标概念描述TC；(2) 训练实例TE；(3) 领域知识DT；(4) 操作准则OC。求解：训练实例的一般化概括，使之满足：(1) 目标概念的充分概括描述TC；(2) 操作准则OC。,7.7 神经学习7.7.1 基于反向传播网络的学习 反向传播（back-propagation,BP）算法是一种计算单个权值变化引起网络性能变化值的较为简单的方法。BP算法过程包含从输出节点开始，反向地向第一隐含层传播由总误差引起的权值修正。,神经网络的组成与特性1.生理神经元结构与功能(1) 生理神经元的结构,2.人工神经元组成与数学描述 人工神经元是根据生物神经网络研究成果，用数学加以抽象和简化，在计算机上模拟生物神经元。(1) 人工神经元（ANN）组成,wji xi,x2 wj2,x1 wj1, -1,f( ),.,(2) ANN的数学描述 令来自其它处理单元(神经元)i的信息为xi，它们与本处理单元的互相作用强度为wi，i=0,1,，n-1，处理单元的内部阈值为。那么本神经元的输入如左式所示 ，处理单元的输出如右式所示：,(2) ANN的数学描述 f称为激励函数或作用函数。它决定节点的输出。该输出为1或0取决于其输入之和大于或小于内部阈值。其中图(c)表示sigmoid函数。,若f( )取为sigmoid函数，则ANN如下图所示：(为了表达方便起见，将内部阈值部分与输入部分统一表示）,若取 w0= w1 = 101，则12，则,w1 x1,x0 w0, -1,f( ),o,7.7.1 基于BP网络（反向传播网络）的学习,1.BP网络的结构 BP网络由一个输入层，一个输出层，以及若干隐层组成。每一层神经元的状态只影响下一层神经元。 还可对每个神经元设置阈值。,例2 设有如下BP神经网络，输入为逻辑值。隐层神经元及输出层神经元的激励函数与例1同。问该神经网络能实现何逻辑功能？,2.BP网络的基本原理,通过一组样例，对网络进行训练，以得到一组符合条件的网络权值。每一样例包括输入向量，及其对应的期望输出(实际输出)向量。 输入信息经各隐层逐层处理后，传至输出层。这一过程称为前向传播。 如果在输出层得不到期望输出，则把误差沿原连接路径返回，并通过修改各层神经元的权值，使误差信号最小。这一过程称为反向传播 。,3.BP网络的学习算法,1）初始化所有的网络权值为小的随机值2）在遇到终止条件前#做以下工作：（1）前向传播。对于每个训练样例（X为输入向量，T为期望输出向量 ），把输入沿前向传播。,（1）前向传播, ANN激励函数的输入(以下简称节点输入) ANN的输出(以下简称节点输出),（1）前向传播,上标表示神经网络的层次序号（ =1,2,M），M层为输出层；当 =1时， 表示整个神经网络的第k个输入值； 表示第 层的神经元个数；单下标表示某层次中的神经元的序号； 表示第 -1层神经元k，到第 层神经元i的权值。,3.BP网络的学习算法,1）初始化所有的网络权值为小的随机值2）在遇到终止条件前做以下工作：（1）前向传播。对于每个训练样例，把输入沿前向传播。 (2) 误差沿网络反向传播。,(2)反向传播, 对输出层的第k个单元，计算其误差项：tk 表示整个神经网络的第k个输出单元的期望输出。,(2)反向传播,对于第 （ M）层的单元h，计算其误差项: 表示上一层单元数。 表示第 层第h单元，到 +1层第k单元的权值。,(2)反向传播,对于第 （ M）层的单元h，计算其误差项: 表示上一层各单元误差 ，以及这些单元与本单元之间权值 的乘积之总和。,3.BP网络的学习算法,1）初始化所有的网络权值为小的随机值2）在遇到终止条件前做以下工作：（1）前向传播。对于每个训练样例，把输入沿前向传播。 (2)误差沿网络反向传播。 (3) 更新权值,(3) 更新权值,是一个正的常数，称为学习速率。,4. BP网络学习算法举例,例3 右图为由sigmoid神经元构成的BP神经网络（设每个神经元的阈值均为0），所标数值为初始权值。当输入矢量为（1，1） 时，期望输出为1，如果学习速率取为0.1，请写出用BP学习算法一次迭代后的权值，要求写出过程。,(1) 前向传播第0层（输入层）：,(1)前向传播,第1层（隐层）：,(1)前向传播,第2层（输出层）：,(2) 反向传播,第2层（输出层）：,(2) 反向传播,第1层（隐层）：,(2) 反向传播,第0层（输入层）：,(3) 更新权值,反向传播和权值更新前后的BP神经网络对比：,-0.0433,0.2071,0.0498,0.1006,0.2506,0.1498,x0,x1,o,5. BP网络学习算法的关键和有待解决的问题1）最终的权值应是各个样例训练结果的某种统计值 例如，设有样例(k=1,2,n)，则其权值可通过下式给出：,2）训练的终止条件(1)权值更新迭代的次数达到设定值时 该设定值应适当，否则将达不到训练目的，或因对于样例的过度拟合而造成对于其它实例泛化精度的降低。,(2)在训练样例上的误差降到设定的允许误差时 训练样例d的误差可以通过对网络中所有输出单元的求和得到：(3)在分离的验证样例集合上的误差符合某个标准时。 与(2)不同的是，这种方法使用训练样例以外的样例来求得误差，并视该误差是否达到某个标准来确定训练是否可以终止。,3）对网络进行训练的样例的数量 样例数量要适当。太少则缺乏代表性，太多则带来训练开销等问题。,4）学习速率 学习速率太小则降低训练效率，太大则可能陷入局部最小而达不到全局最小。5）隐层的层数和每一隐层中单元数目的确定6）平台效应（在训练过程中的某一阶段，输出误差下降不明显）,例4 写出下图所示BP神经网络中隐层右单元的激励函数输入项，误差项，以及该单元与输出层右单元之间权值的修正式。,隐层右单元的激励函数输入项：,隐层右单元的误差项：,该单元与输出层右单元之间权值的修正式：,7.7.2 基于Hopfield网络的学习 反馈神经网络，它是一种动态反馈系统，比前馈网络具有更强的计算能力。 Hopfield网络是一种具有正反相输出的带反馈人工神经元。,7.8 知识发现7.8.1 知识发现的发展和定义知识发现的产生和发展 知识发现最早是于1989年8月在第11届国际人工智能联合会议的专题讨论会上提出。知识发现的定义 数据库中的知识发现是从大量数 据中辨识出有效的、新颖的、潜在有用的、并可被理解的 模式的高级处理过程 。,7.8.2 知识发现的处理过程,1. 数据选择。根据用户的需求从数据库中提取与KDD相关的数据。,2. 数据预处理。主要是对上述数据进行再加工，检查数据的完整性及数据的一致性，对丢失的数据利用统计方法进行填补，形成发掘数据库。,3. 数据变换。即从发掘数据库里选择数据,4.数据挖掘。根据用户要求，确定KDD的目标是发现何种类型的知识。,5. 知识评价。这一过程主要用于对所获得的规则进行价值评定，以决定所得的规则是否存入基础知识库。,7.8.3 知识发现的方法,1.统计方法：统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。,2. 机器学习方法,3. 神经计算方法,4.可视化方法 ：可视化（visualization）就是把数据、信息和知识转化为可视的表示形式的过程。,7.8.4 知识发现的应用,知识发现已在许多领域得到应用。现在，知识发现已在银行业、保险业、零售业、医疗保健、工程和制造业、科学研究、卫星观察和娱乐业等行业和部门得到成功应用，为人们的科学决策提供很大帮助。,7.9 小结,本章只对机器学习作个入门介绍。 机器学习在过去十多年中获得较大发展。今后机器学习将在理论概念、计算机理、综合技术和推广应用等方面开展新的研究。其中，对结构模型、计算理论、算法和混合学习的开发尤为重要。在这些方面，有许多事要做，有许多新问题需要人们去解决。,