ch4机器学习.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,机器学习,概述,1.,机器学习的基本概念：,按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。,2.,机器学习的定义,机器学习是研究如何使用机器来模拟人类学习活动的一门学科。稍为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别现有知识的学问。,机器能否象人类一样能具有学习能力呢？,1959,年美国的塞缪尔,(Samuel),设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。,4,年后，这个程序战胜了设计者本人。又过了,3,年，这个程序战胜了美国一个保持,8,年之久的常胜不败的冠军。这个程序向人们展示了机器学习的能力，提出了许多令人深思的社会问题与哲学问题。,机器学习,概述,机器学习的任务,获得对于输入的数据进行分类的能力。,获得解决问题，行为计划和行为控制等的能力。,机器学习,概述,实现的困难：,预测难：学习后知识库发生了什么变化，系统功能的变化的预测。,归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。,机器目前很难观察什么重要、什么有意义。,机器学习,概述,发展历史,50,年代中期,60,年代中期（热烈时期）,学习的统计计算模型,自组织、自适应方法,模式识别的产生,(,指纹、掌心、头骨骼等,),，至今还在沿用,60,年代中期,70,年代中期（冷清时期）,Winston,积木世界学习系统,Michalski,大豆病诊断规则程序,概念学习过程，高级知识的符号描述,70,年代中期,80,年代中期（复兴时期）,多个概念的学习，多种学习策略,机器学习与各种应用结合起来,80,年：,CMU,召开了第一次机器学习研讨会,86,年：,Machine Learning,创刊,机器学习的最新阶段始于,1986,年。,第六章 机器学习,概述,决策树学习,神经网络学习,决策树学习,决策树,(Decision Tree),一种描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。,决策树学习,（概述）,决策树学习是以实例为基础的归纳学习。,从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。,概念分类学习算法：来源于,Hunt,Marin,和,Stone,于,1966,年研制的,CLS,学习系统，用于学习单个概念。,1979,年,J.R.Quinlan,给出,ID3,算法，并在,1983,年和,1986,年对,ID3,进行了总结和简化，使其成为决策树学习算法的典型。,Schlimmer,和,Fisher,于,1986,年对,ID3,进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到,ID4,算法。,1988,年，,Utgoff,在,ID4,基础上提出了,ID5,学习算法，进一步提高了效率。,1993,年，,Quinlan,进一步发展了,ID3,算法，改进成,C4.5,算法。,另一类决策树算法为,CART,，与,C4.5,不同的是，,CART,的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例,决策树学习,（概述）,1,建立决策树，利用训练样本生成决策树模型。,开始，数据都在根节点,递归的进行数据分片,2,使用决策树,对未知数据进行分类,按照决策树上采用的分割属性逐层往下，直到一个叶子节点,判定树分类算法,output,训练集,决策树,input,决策树学习,（决策树）,根结点,个子大,可能是松鼠,可能是老鼠,可能是大象,在水里,会吱吱叫,鼻子长,脖子长,个子小,不会吱吱叫,鼻子短,脖子短,可能是长颈鹿,在陆地上,可能是犀牛,可能是河马,决策树学习,（决策树）,判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“,IFTHEN”,规则来实现。,IF“,个子大”,THEN,IF“,脖子短”,THEN,IF“,鼻子长”,THEN,可能是大象,形式化表示成,决策树学习,（决策树）,构造一棵决策树要解决四个问题：,收集待分类的数据，这些数据的所有属性应该是完全标注的。,设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。,分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。,设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：,决策树学习,（应用）,根据病情对病人分类,根据起因对故障分类,根据付款信用情况对贷款申请者分类,这些都是将输入样本分类成可能离散集,分类问题,决策树学习,（学习）,Shannon,信息熵,自信息量,设信源,X,发出,a,i,的概率,p(a,i,),，在收到符号,a,i,之前，收信者对,a,i,的不确定性定义为,a,i,的自信息量,I(a,i,),。,I(a,i,)=-logp(a,i,),。,信息熵,自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为：,其中，,r,为信源,X,发出的所有可能的符号类型。信息熵反应了信源每发出一个符号所提供的平均信息量。,决策树学习,（学习）,Shannon,信息熵,条件熵,设信源为,X,，收信者收到信息,Y,，用条件熵,H(X|Y),来描述收信者在收到,Y,后对,X,的不确定性估计。设,X,的符号,a,i,，,Y,的符号,b,j,，,p(a,i,|b,j,),为当,Y,为,b,j,时，,X,为,a,i,的概率，则有：,平均互信息量,用平均互信息量来表示信号,Y,所能提供的关于,X,的信息量的大小，用,I(X,Y),表示：,ID3,算法,设学习的实例集为,其中,S,i,为学习实例，,T,实例集大小。对于有指导的学习，任一个,S,i,具有明确标定的类别 ，向量表示该实例的特性，即,S,i,的信息为，如果一个观测值具有属性则应该划归为类，应该有下面的规则总结出来,信息增益度度量,任意样本分类的期望信息：,I(s,1,s,2,s,m,)=,P,i,log,2,(p,i,),（,i=1,m,）,S,是,s,个数据样本的集合。类别属性具有,m,个不同值,C,i,。,s,i,是类,C,i,中的样本数。,p,i,是任意样本属于,C,i,的概率，并用,s,i,/s,估计。,由非类别属性,A,划分为子集的熵：,E(A)=(s,1j,+s,mj,)/s*,I,(s,1j,，,，,s,mj,),非类别属性,A,具有,v,个不同值,a,1,，,a,2,，,，,a,v,。利用,A,将,S,划分为,v,个子集,S,1,，,S,2,，,，,S,v,；,其中,S,j,包含,S,中在,A,上具有值,a,j,的样本。,S,ij,是子集,S,j,中类,C,i,的样本数。,信息增益：,Gain(A)=,I,(s1,s2,sm),E(A),ID3,的基本思想,构造决策树，决策树的每个节点对应一个非类别属性，每条边对应该属性的每个可能值。以信息熵的下降速度作为选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性。,天气,温度,湿度,风况,运动,晴,85,85,无,不适合,晴,80,90,有,不适合,多云,83,78,无,适合,有雨,70,96,无,适合,有雨,68,80,无,适合,有雨,65,70,有,不适合,多云,64,65,有,适合,晴,72,95,无,不适合,晴,69,70,无,适合,有雨,75,80,无,适合,晴,75,70,有,适合,多云,72,90,有,适合,多云,81,75,无,适合,有雨,71,80,有,不适合,使用信息增益进行属性选择,类,C,1,运动“适合”，,类,C,2,对运动“不适合”,I(s1,s2)=I(9,5)=0.940,计算属性天气的熵,:,决策树,天气,?,overcast,湿度,?,风况,?,75,无,有,天晴,有雨,不适合,不适合,不适合,适合,适合,多云,第六章 机器学习,概述,决策树学习,神经网络学习,人工神经元网络,概述,基本原理,前馈型人工神经元网络,神经网络的应用,参考书：,人工神经网络教程,北京邮电大学出版社，韩力群,概述,什么叫人工神经网络,采用物理可实现的系统来模仿人脑神经细胞的结构和功能的系统。,为什么要研究神经网络,用计算机代替人的脑力劳动。,计算机速度为纳秒级，人脑细胞反应时间是毫秒级。而计算机不如人。,长期以来人类的梦想，机器既能超越人的计算能力，又有类似于人的识别、分析、联想等能力。,概述,发展史,1890,年，美国生物学家,W.James,出版了,Physiology,（生理学）一书。首次阐明了有关人脑结构及其功能，以及相关学习、联想、记忆的基本规律。指出：人脑中当两个基本处理单元同时活动，或两个单元靠得比较近时，一个单元的兴奋会传到另一个单元。而且一个单元的活动程度与他周围的活动数目和活动密度成正比。,概述,发展史,1943,年,McCulloch,（心理学家）和,Pitts,（数理逻辑学家）发表文章，提出,M-P,模型。描述了一个简单的人工神经元模型的活动是服从二值（兴奋和抑制）变化的。总结了神经元的基本生理特性，提出了神经元的数学描述和网络的结构方法。,标志神经计算时代的开始,概述,发展史,MP,模型的意义：,M-P,模型能完成一定的逻辑运算,第一个采用集体并行计算结构来描述人工神经元和网络工作。,为进一步的研究提供了依据,（可以完成布尔逻辑计算）,概述,发展史,1949,年,Donala U.Hebb,（心理学家）论著,The Organization of Behavior,（行为自组织）,，提出突触联系强度可变的假设，认为学习的过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。,赫布规则,多用于自组织网络的学习。即：若两个神经元输出兴奋，则它们之间的连接权加强，反之减少。,W,ji,(t+1)=w,ji,(t)+x,i,(t)x,j,(t),概述,发展史,赫布规则意义,（提出了变化的概念）,提出了一个神经网络里信息是储藏在突触连接的权中的概念,连接权的学习律是正比于两个被连接神经细胞的活动状态值的乘积,假设权是对称的,细胞的互相连接的结构是他们权的改变创造出来的,概述,发展史,1957,年,Frank Rosenblatt,定义了一个神经网络结构，称为感知器,(Perceptron),。,意义：第一次把神经网络研究从纯理论的探讨推向工程实现，在,IBM704,计算机上进行了模拟，证明了该模型有能力通过调整权的学习达到正确分类的结果。掀起了神经网络研究高潮。,概述,发展史,1969M.Minsky,和,S.Papert,发表了,Perceptrons,的论著，指出感知器仅能解决一阶谓词逻辑，只能做线性划分。对于非线性或其他分类会遇到很大困难。一个简单的,XOR,问题的例子就证明了这一点。,神经网络研究一度达到低潮。原因还有：计算机不够发达、,VLSI,还没出现、而人工智能和专家系统正处于发展高潮。,概述 发展史,七十年代,据说全球只有几十个人在研究，但还是成功的。如：日本,Fukusima,的,Neocognitron,；芬兰,Kohonen,的自组织神经网络；,Stephen Crossberg,的共振自适应理论,ART,网络等。,概述,发展史,1982,年,John J.,Hopfield,（物理学家）提出了全联接网络，离散的神经网络模型。,全新的具有完整理论基础的神经网络模型。基本思想是对于一个给定的神经网络，对于一个能量函数，这个能量函数是正比于每一个神经元的活动值和神经元之间的联接权。而活动值的改变算法是向能量函数减少的方向进行，一直达到一个极小值为止。证明了网络可达到稳定的离散和连续两种情况。年后,AT&T,等做出了半导体芯片。,神经网络复兴时期开始。,概述,发展史,1986,年美国的一个平行计算研究小组提出了前项反馈神经网络的,Back Propagation,（,BP,）学习算法。成为当今应用最广泛的方法之一。该方法克服了感知器非线性不可分类问题，给神经网络研究带来了新的希望。,概述,发展史,1987,年在美国召开了第一届世界神经网络大会,1000,人参加。,IJCNN,等大会,Neural Computing,IEEE Neural Network,等期刊,概述,符号主义与神经网络,共同之处：研究怎样使用计算机来模仿人脑工作过程。学习,实践,再学习,再实践。,不同之处：,符号主义研究人脑的推理、学习、思考、规划等思维活动，解决需人类专家才能处理的复杂问题。,神经网络企图阐明人脑结构及其功能，以及一些相关学习、联想记忆的基本规则（联想、概括、并行搜索、学习和灵活性）,概述,基本原理,神经元模型,基本原理神经元模型,神经元,每一个细胞处于两种状态。突触联接有强度。多输入单输出。实质上传播的是脉冲信号，信号的强弱与脉冲频率成正比。,基本原理,神经元模型,特性函数：,神经细胞的输出对输入的反映。,(,a),x,f,(,x,),1,0,神经元中的某些特性（激励）函数,(a),二值函数,(b)S,形函数,(c),分段函数,(,c),x,f,(,x,),1,(,b),f,(,x,),x,1,0,基本原理,网络结构,人脑神经网络：,人脑中约有亿个神经细胞，根据,Stubbz,的估计这些细胞被安排在约个主要模块内，每个模块上有上百个神经网络，每个网络约有万个神经细胞。,基本原理,网络模型,前馈网络：每层只与前层相联接,基本原理,网络模型,输入输出有反馈的前馈网络：输出层上存在一个反馈回路，将信号反馈到输入层。而网络本身还是前馈型的,基本原理,网络模型,前馈内层互联网络：外部看还是一个前向网络，内部有很多自组织网络在层内互联着。,基本原理,网络模型,反馈型全互联网络：所有计算单元之间都有联接。如：,Hopfield,网络,基本原理,基本属性,基本属性：,非线性,非局域性,非定常性,非凸性,基本原理,优缺点,评价,优点：,并行性；分布存储；容错性；学习能力,缺点：,不适合高精度计算；学习问题没有根本解决，慢；目前没有完整的设计方法，经验参数太多。,前馈型神经网,概述,最初称之为感知器。应用最广泛的一种人工神经网络模型，最要原因是有,BP,学习方法。,前馈网络结构是分层的，信息只能从下一层单元传递到相应的上一层单元。上层单元与下层所有单元相联接。特性函数可以是线性阈值的。,前馈型神经网,单层感知器,前馈型神经网,基本原理，结构简单。很少在实际应用中出现。采用阶跃函数作为特性函数。,输出,y,i,等于,：,(1),其中,前馈型神经网,单层感知器,分类方法：,如果输入,x,有,k,个样本，,x,p,p=1,2,k,x,R,n,当将这些样本分别输入到单输出的感知器中，在一定的和下，输出有两种可能,+1,或,-1,。,举个例子：银行贷款：什么情况下可以，什么情况下不可以,分为条件,x,1,x,2,x,3,x,k,，过去有很多贷款实例。形成一个表：,0,x,1,x,2,x,3,x,k,贷款,1,0101010101,1,2,1100101010,0,。,1,+,+,+,+,+,+,+,+,X,1,X,2,二维输入感知器及其在状态空间中的划分,简单感知器引入的学习算法称之为误差学习算法：,误差型学习规则：,(1),选择一组初始权值,w,i,(0),。,(2),计算某一输入模式对应的实际输出与期,望输出的误差,(3),如果,小于给定值，返回,2,，否则继续。,(4),更新权值,(,阈值可视为输入恒为,1,的一个权值,),：,w,i,（,t+1,）,w,i,（,t+1,）,-w,i,（,t,）,dy(t)x,i,。,式中,为在区间,(0,，,1),上的一个常数，称为学习步长，它的取值与训练速度和,w,收敛的稳定性有关；,d,、,y,为神经元的期望输出和实际输出；,x,i,为神经元的第,i,个输入。,(5),返回,(2),，重复，直到对所有训练样本模式，网络输出均能满足要求。,简单的分类例题,(XOR),其中,a,b,是输入单元，,c,d,是隐单元，,e,是输出单元。单元的激活值规定取,1,或,0,，每个单元的输出函数都取为等价函数，即,a=o,。单元的,net,值是所有输入的加权和：,net=,w,o,。单元的激活函数采用阈值函数，阈值为,0.01,。即当单元的,net,值大于,0.01,时该单元的激活值取,1,，否则取,0,。,d,b,c,a,e,+1,+1,+1,+1,-1,-1,输入 输出 阈值,(0 0)0,=,0.01,(0 1)1,(1 0)1,(1 1)0,=,0.01,=,0.01,=,0.01,简单的分类计算,1.,输入为,(0,0),时，,o,a,=o,b,=0,net,c,=o,a,w,ca+,o,b,w,cb,=0,1,+,0,(-,1,)=0,net,d,=o,a,w,da+,o,b,w,db,=0,(-,1,),+,0,1,=0,因为,net,c,0.01,，,net,c,0.01,，所以,a,c,=0,，,a,d,=0,得到,o,c,=0,o,d,=0,。所以,net,e,=o,c,w,ec+,o,d,w,ed,=0,1+,0,1,=0,因为,net,e,0.01,所以,o,e,=a,e,=0,即当输入为,(0,0),时，网络的输出为,0,。,d,b,c,a,e,+1,+1,+1,+1,-1,-1,=,0.01,=,0.01,=,0.01,简单的分类计算,2.,网络输入为,(0,1),时，,o,a,=0,o,b,=1,net,c,=o,a,w,ca+,o,b,w,cb,=0,1,+1,(-,1,)=-1,net,d,=o,a,w,da+,o,b,w,db,=0,(-,1,),+1,1,=1,因为,net,c,0.01,所以,o,c,=a,c,=0,o,d,=a,d,=1,。得,net,e,=o,c,w,ec+,o,d,w,ed,=0,1+1,1,=10.01,o,e,=a,e,=1,即当输入为,(0,1),时，网络的输出为,1,。,d,b,c,a,e,+1,+1,+1,+1,-1,-1,=,0.01,=,0.01,=,0.01,例题总结,同样当网络输入为,(1,0),时，网络的输出为,1,。,当网络输入为,(1,1),时，网络的输出为,0,。,因此，神经网络完成了一个影射，起到了函数的作用。由于其中的机理不清楚，也称“黑箱”。,d,b,c,a,e,+1,+1,+1,+1,-1,-1,=,0.01,=,0.01,=,0.01,“黑箱”或函数,F,输入,(0 0),(0 1),(1 0),(1 1),输出,0,1,1,0,前馈型神经网,多层感知器,多层感知器的输入输出关系与单层感知器完全相同。前一层的输出是下一层的输入。也被称为,BP,网络。,反向传播,(BP),网络的基本结构,主要有以下特点：,1.,至少有一层隐单元；,2.,增加隐藏层的层数和隐藏层神经元个数不一定总能够提高网络精度和表达能力。,BP,网一般都选用三层网络。,3.,单元的激活函数是它总输入的非递减可微函数，实际应用中常选取,S,型函数，如,Logsigmoid,或,Tansigmoid,函数,4.,包括两个过程：,i),正向的计算传播；,ii),逆向的误差传播过程。,d,b,c,a,e,w,v,v,d,b,c,a,g,w,u,f,e,网络的拓扑结构,x,0,y,0,输出层,隐藏层,输入层,x,1,y,1,Y,m-1,X,n-1,W,1,W,logSigmoid,函数基本形式及图形,0,1,BP,网络的学习,其根本思想是：,i),建立描述网络实际输出与目标输出的差值,ii),找到使,E,最小的一个权重集合,iii)E,中,y,l,是权值,w,ij,的函数,所以,E,也是权值,w,ij,的函数。为使,E,最小，需选取,E,曲面上一个梯度下降最快的方向修改,w,ij,。,即：权值的改变量与,E,的负导数成比例,w,ij,=-,(,E/,w,ij,),BP,网络权重学习算法的最一般形式,E,中的权重分为两种，连接到隐单元的和到输出单元的。因而从,w,ij,=-(,E/,w,ij,),中导出的权值计算就有两种,:,i),对于输出单元的连接权,ii),对于隐单元的连接权,程序结构分析。,网络初始设定：随机权重,W,、随机阈值,B,、学习率、网络误差,E,、隐结点个数等。,初始设定,前向计算,误差传播,权值修改,网络训练是建立网络模型的核心内容，是一个循环体，分为前向计算、误差逆向传播、权值修改等。然后根据初始设定的误差决定是否停止训练。,样本检验,参数存储,训练结束后，继续使用检验样本对网络进行适应性验证。,当考证网络具备所要求的性能后，将网络涉及的各种参数存储，以备建立实际系统。,例：保定市的降水模型,通过对降水过程的总结，建立保定降水的简单预报模型：,1,、东高西低：高空天气形势应该具备东部是高压或高压脊，西部有低压或低压槽，保定位于南或西南气流里，简称东高西低；,2,、垂直运动条件：降水时一定存在低层要有水平辐合，高层水平辐散，有上升运动；,3,、水汽条件：具备充足的水汽和水汽输送；,4,、能量条件：处于一定强度的锋区内和一定的层结条件；这些条件定性分析比较简单，和降水没有确定的定量关系，预报员凭预报经验作预报，很难客观化。人工神经网络应用是使这一经验预报方法客观化的好方法。,因子的具体选取,依据降水的主要条件，从我国,T213,数值预报产品中选取反映保定降水条件的物理量。共从,36,小时预报中选出,10,个网格点要素，分别是：湿度条件：,850HPA,的相对湿度、水汽通量；垂直速度条件：,850,的散度、,200,的散度、,700,的垂直速度、降水量、,700,的涡度；（以上为,116E,、,39N,网点的值）东高西低条件：,110E,、,120E,、,39N,两点,850,的高度差；锋区和能量条件：,116E,、,35N,、,45N,两点,850,的温度差、,TS,。,BP,神经网络的建立,采用三层,BP,人工神经网络模式，输入层为,10,个神经元，对应,10,个预报因子。输出层为,3,个神经元，对应降水的大中小三个降水量级。中间层一般取输入层和输出层数的平均，这里取,7,个神经元。如图,1,所示，,X,为输入层，,H,为隐含层，,Y,为预报输出层。,图,1,网 络 训 练,1,、预报因子,01,化：,Xi=(Xmax-Xi)/(Xmax-Xmin),2,、在训练以前我们取,01,之间的随机数为连接权重系数,Uil,、,Wlt,和阀值,Rl,、,Sj,赋初值。由于训练开始时误差常常较大，它们将在以后的训练学习过程中自动逐步调节,3,、,02,年，我台从,3,月到,11,月接收,T213,数值预报产品齐全的共有,159,天，用前,109,天的资料作为网络训练样本,训练结果,经过两万多次的训练，总体预报误差达到了,4.0,以下。终止训练后。这,109,天中共有降水日,27,天，其中小雨,20,天，中雨,6,天，大雨以上降水一次。训练结束时,27,天降水全部报出，量级也全部正确，只是空报两次小雨过程，历史拟合率达到,27/29=93%,。,试报结果,在试报的,50,天中共有降水,8,次，其中大雨,2,次，漏一次，一次报中雨。中雨,3,次，报对,2,次，漏一次。,3,次小雨，一次报中雨，漏,2,次。另空报,2,次小雨，定性准确率,4/10=40%,。,