1、人工神经网络及其应用第5讲Hopfield网络何建华电信系,华中科技大学2003年3月3日1一、反馈网络二、Hopfield网络简介三、DHNN网络四、稳定性与应用五、内容小结内容安排2反馈网络如何通过网络神经元状态的变迁而最终稳定于平衡状态,得到联想存储或优化计算的结果关心网络的稳定性问题研究重点为怎样得到和利用稳定的反馈网络要点31.1 反馈网络简介1.2 网络稳定性一、反馈网络41.1 反馈网络简介反馈网络(Recurrent Network),又称自联想记忆网络 其目的是为了设计一个网络,储存一组平衡点,使得当给网络一组初始值时,网络通过自行运行而最终收敛到这个设计的平衡点上。反馈网络
2、能表现出非线性动力学系统动态特性 网络系统具有若干个稳定状态。当网络从某一初始状态开始运动,网络系统总可以收敛到某一个稳定的平衡状态;系统稳定的平衡状态可以通过设计网络的权值而被存储到网络中51.1 反馈网络简介反馈网络分类 如果激活函数f()是一个二值型的硬函数,即aisgn(ni),il,2,r,则称此网络为离散型反馈网络;如果f()为一个连续单调上升的有界函数,这类网络被称为连续型反馈网络61.2 网络稳定性状态轨迹 设状态矢量N=n1,n2,,nr,网络的输出矢量为Aa1,a2,asT 在一个r维状态空间上,可以用一条轨迹来描述状态变化情况 从初始值N(t0)出发,N(t0+t)N(t
3、0+2t)N(t0+mt),这些在空间上的点组成的确定轨迹,是演化过程中所有可能状态的集合,我们称这个状态空间为相空间71.2 网络稳定性状态轨迹 离散与连续轨迹81.2 网络稳定性状态轨迹分类:对于不同的连接权值wij和输入Pj(i,j=1,2,r),反馈网络可能出现不同性质的状态轨迹 轨迹为稳定点 轨迹为极限环 轨迹为混沌现象 轨迹发散91.2 网络稳定性稳定轨迹 状态轨迹从系统在t0时状态的初值N(t0)开始,经过一定的时间t(t0)后,到达N(t0+t)。如果N(t0+t+t)=N(t0+t),t0,则状态N(t0+t)称为网络的稳定点,或平衡点 反馈网络从任一初始态P(0)开始运动,
4、若存在某一有限时刻t,从t以后的网络状态不再发生变化(P(t+t)=P(t),t0)则称网络是稳定的 处于稳定时的网络状态叫做稳定状态,又称为定吸引子101.2 网络稳定性稳定点分类 在一个反馈网络中,存在很多稳定点 稳定点收敛域 渐近稳定点:在稳定点Ne周围的N()区域内,从任一个初始状态N(t0)出发,当t时都收敛于Ne,则称Ne为渐近稳定点 不稳定平衡点Nen:在某些特定的轨迹演化过程中,网络能够到达稳定点Nen,但对其它方向上任意小的区域N(),不管N()取多么小,其轨迹在时间t以后总是偏离Nen;期望解 网络的解:如果网络最后稳定到设计人员期望的稳定点,且该稳定点又是渐近稳定点,那么
5、这个点称为网络的解;网络的伪稳定点:网络最终稳定到一个渐近稳定点上,但这个稳定点不是网络设计所要求的解111.2 网络稳定性状态轨迹为极限环 在某些参数的情况下,状态N(t)的轨迹是一个圆,或一个环 状态N(t)沿着环重复旋转,永不停止,此时的输出A(t)也出现周期变化(即出现振荡)如果在r种状态下循环变化,称其极限环为r 对于离散反馈网络,轨迹变化可能在两种状态下来回跳动,其极限环为2121.2 网络稳定性状态轨迹为混沌 如果状态N(t)的轨迹在某个确定的范围内运动,但既不重复,又不能停下来 状态变化为无穷多个,而轨迹也不能发散到无穷远,这种现象称为混沌(chaos)出现混沌的情况下,系统输
6、出变化为无穷多个,并且随时间推移不能趋向稳定,但又不发散131.2 网络稳定性状态轨迹发散 状态N(t)的轨迹随时间一直延伸到无穷远。此时状态发散,系统的输出也发散 在人工神经网络中,由于输入、输出激活函数上一个有界函数,虽然状态N(t)是发散的,但其输出A(t)还是稳定的,而A(t)的稳定反过来又限制了状态的发散。一般非线性人工神经网络中发散现象是不会发生的,除非神经元的输入输出激活函数是线性的141.3 网络工作方式目前的反馈神经网络是利用稳定的特定轨迹来解决某些问题 如果视系统的稳定点为一个记忆,则从初始状态朝此稳定点移动的过程即为寻找该记忆的过程 状态的初始值可以认为是给定的有关该记忆
7、的部分信息,状态N(t)移动的过程,是从部分信息去寻找全部信息,这就是联想记忆的过程 将系统的稳定点考虑为一个能量函数的极小点。在状态空间中,从初始状态N(t0)N(t0+t),最后到达N*。若N*为稳定点,则可以看作是N*把N(t0)吸引了过去,在N(t0)时能量比较大,而吸引到N*时能量已为极小了151.3 网络工作方式考虑具体应用,可以将能量的极小点作为一个优化目标函数的极小点,把状态变化的过程看成是优化某一个目标函数的过程因此反馈网络的状态移动的过程实际上是一种计算联想记忆或优化的过程。它的解并不需要真的去计算,只需要形成一类反馈神经网络,适当地设计网络权值wij,使其初始输入A(t0
8、)向稳定吸引子状态移动就可以达到目的161.3 网络工作方式权值设计目标 网络系统能够达到稳定收敛 设计网络的稳定点 设计吸引域 17二、Hopfield网络简介2.1 网络模型2.2 DHNN2.3 CHNN2.4 联想记忆与优化计算182.1 网络模型192.1 网络模型分类 离散Hopfield网络(DHNN)连续Hopfield网络(CHNN)DHNN中的激活函数 CHNN中的激活函数 202.2 DHNNDHNN 取b0,wii0 权矩阵中有wijwji212.2 DHNN DHNN网络结构可以用一个加权元向量图表示222.3 CHNN将霍普菲尔德网络推广到输入和输出都取连续数值的情
9、形网络的基本结构不变,状态输出方程形式上也相同。则网络的状态转移方程可写为232.3 CHNN神经元的激活函数f为S型的函数(或线性饱和函数)242.3 CHNN神经元的激活函数f为S型的函数(或线性饱和函数)252.3 CHNN电路实现 神经元模型(见参见教材)电阻Ri和电容Ci并联,模拟生物神经元输出的时间常数 跨导Tij模拟神经元之间互连的突触特性 运算放大器模拟神经元的非线性特性 ui为第i个神经元的输入,Vi为输出网络模型262.3 CHNN定义系统计算能量定理 推论 系统的稳定平衡点就是能量函数E的极小点,反之亦然272.3 CHNN定理 系统在状态空间中正交稳定平衡点的任意放置可
10、以通过Tij的学习来实现增加存储与消除记忆 如果在已设计的系统中加入一个新的存储,只要修正Tij,新的存储的加入并不改变原有的存储,且与原存储无关282.4 联想记忆与优化计算联想记忆问题 稳定状态已知并且通过学习和设计算法寻求合适的权值矩阵将稳定状态存储到网络中优化计算 权值矩阵W已知,目的为寻找具有最小能量E的稳定状态 主要工作为设计相应的W和能量函数公式29三、DHNN3.1 神经元状态更新方式3.2 网络学习3.3 网络记忆容量3.4 权值设计303.1 状态更新由-1变为1;由1变为-1;状态保持不变串行异步方式 任意时刻随机地或确定性地选择网络中的一个神经元进行状态更新,而其余神经
11、元的状态保持不变 并行同步方式 任意时刻网络中部分神经元(比如同一层的神经元)的状态同时更新。如果任意时刻网络中全部神经元同时进行状态更新,那么称之为全并行同步方式 313.1 状态更新串行异步方式 任一时刻,网络中只有一个神经元被选择进行状态更新或保持,所以异步状态更新的网络从某一初态开始需经过多次更新状态后才可以达到某种稳态。实现上容易,每个神经元有自己的状态更新时刻,不需要同步机制;异步状态更新更接近实际的生物神经系统的表现并行同步方式323.2 网络学习联想记忆 联想记忆功能是DHNN的一个重要应用范围。DHNN用于联想记忆有两个突出的特点,即记忆是分布式的,而联想是动态的 反馈网络实
12、现联想记忆必须具备的两个基本条件 网络能收敛到稳定的平衡状态,并以其作为样本的记忆信息;具有回忆能力,能够从某一残缺的信息回忆起所属的完整的记忆信息学习目的 具有q个不同的输入样本组PrqP1,P2 Pq 通过学习方式调节计算有限的权值矩阵W 以每一组输入样本Pk,k=1,2,q 作为系统的初始值 经过网络工作运行后,系统能收敛到各自输入样本矢量本身333.2 网络学习DHNN中运用海布调节规则 海布法则是一种无指导的死记式学习算法 当神经元输入与输出节点的状态相同(即同时兴奋或抑制)时,从第j个到第i个神经元之间的连接强度则增强,否则减弱当k1时,对于第i个神经元,由海布学习规则可得网络权值
13、对输入矢量的学习关系式为 其中,0,i1,2,r;j=1,2,r。在实际学习规则的运用中,一般取1或1/r343.2 网络学习当k由1增加到2,直至q时,是在原有己设计出的权值的基础上,增加一个新量pjkpik,k2,q对网络所有输入样本记忆权值的设计公式为 其中,0,i1,2,r;j=1,2,r。在实际学习规则的运用中,一般取1或1/r353.2 网络学习向量形式表示1时神经网络工具箱中采用海布公式求解网络权矩阵变化的函数为learnh.m和learnhd.m。后者为带有衰减学习速率的函数 dW1earnh(P,A,lr)dWlearnhd(W,P,A,lr,dr);对于简单的情况,lr可以
14、选择1;对于复杂的应用,可取lr0.10.5,drlr3363.2 网络学习简单验证 q1,l 求出的权值wij是否能够保证aipi?对于第i个输出节点,有373.3 记忆容量设计DHNN网络的目的,是希望通过所设计的权值矩阵W储存多个期望模式当网络只记忆一个稳定模式时,该模式肯定被网络准确无误地记忆住,即所设计的W值一定能够满足正比于输入和输出矢量的乘积关系但当需要记忆的模式增多时,网络记忆可能出现问题 权值移动 交叉干扰383.3 记忆容量权值移动 当k2时,为了记忆样本T2,需要在记忆了样本Tl的权值上加上对样本T2的记忆项T2T2T-I,将权值在原来值的基础上产生了移动 由于在学习样本
15、T2时,权矩阵W是在已学习了T1的基础上进行修正的,W起始值不再为零,所以由此调整得出的新的W值,对记忆样本T2来说,也未必对所有的s个输出同时满足符号函数的条件,即难以保证网络对T2的精确的记忆 随着学习样本数k的增加,权值移动现象将进一步发生,当学习了第q个样本Tq后,权值又在前q-1个样本修正的基础上产生了移动,这也是网络在精确的学习了第一个样本后的第q-1次移动 对已记忆的样本发生遗忘,这种现象被称为“疲劳”393.3 记忆容量交叉干扰 设输入矢量P维数为rq,取=1/r。Pk-1,1,所以pik*pjkpjk*pjk1。当网络某个矢量Pl,l1,q,作为网络的输入矢量时,可得网络的加
16、权输入和nil为 上式右边中第一项为期望记忆的样本,而第二项则是当网络学习多个样本时,在回忆阶段即验证该记忆样本时,所产生的相互干扰,称为交叉干扰项403.3 记忆容量有效容量 从对网络的记忆容量产生影响的权值移动和交叉干扰上看,采用海布学习法则对网络记忆样本的数量是有限制的 通过上面的分析已经很清楚地得知,当交叉干扰项幅值大于正确记忆值时,将产生错误输出在什么情况下,能够保证记忆住所有样本?当所期望记忆的样本是两两正交时,能够准确得到一个可记忆数量的上限值 413.3 记忆容量有效容量的上界 正交特性 神经元为二值输出的情况下,即Pj-1,1,当两个r维样本矢量的各个分量中,有r/2是相同,
17、r/2是相反。对于任意一个数l,l1,r,有Pl(Pk)T0,lk;而有Pl(Pl)Tr,lk 用外积和公式所得到的权矩阵进行迭代计算,在输入样本Pk,k=1,2,q中任取Pl为初始输入,求网络加权输入和Nl 只要满足,rq,则有sgn(Nl)Pl保证Pl为网络的稳定解 423.4 权值设计学习规则:通过计算每个神经元节点的实际激活值A(t),与期望状态T(t)进行比较,若不满足要求,则将二者的误差的一部分作为调整量,若满足要求,则相应的权值保持不变 433.4 权值设计伪逆法 对于输入样本PP1 P2 Pq,设网络输出可以写成一个与输入样本相对应的矩阵A,输入和输出之间可用一个权矩阵W来映射
18、,即有:W*PN,Asgn(N),由此可得WN*P*其中P*为P的伪逆,有P*(PTP)-1PT 如果样本之间是线性无关的,则PTP满秩,其逆存在,则可求出权矩阵W 但当记忆样本之间是线性相关的,由海布法所设计出的网络存在的问题,伪逆法也解决不了,甚至无法求解,相比之下,由于存在求逆等运算,伪逆法较为繁琐,而海布法则要容易求得多443.4 权值设计正交化的权值设计 这一方法的基本思想和出发点 1)保证系统在异步工作时的稳定性;2)保证所有要求记忆的稳定平衡点都能收敛到自己;3)使伪稳定点的数目尽可能的少;4)使稳定点的吸引域尽可能的大。正交化设计方法的数学设计较为复杂,类似于Gram-Schm
19、idt正交化过程与外积和法相比较,所设计出的平衡稳定点能够保证收敛到自己并且有较大的稳定域在MATLAB工具箱中已将此设计方法写进了函数solvehop.m中:W,bsolvehop(T)45四、稳定性与应用3.1 联想存储器特性3.2 稳定平衡点判定3.3 TSP问题求解464.1 联想存储器特性性质 如果X是一个系统的稳定状态,则X也一定是一个稳定状态 如果X1,X2,Xk为系统的稳定状态,Y是它们的线性组合而得到的向量,则Y为稳定状态 对于任意X1,X2,Xk,k=n-1,则总可以找到W,并且rank(W)n),使得X1,X2,Xk是网络的稳定状态474.2 稳定平衡点判定定理(稳定平衡
20、点判定)对于CHNN,Us为一个n维向量。Us为系统的一个稳定平衡点的充分条件如下,484.3 TSP问题求解所谓TSP(Traveling Salesman Problem)问题,即“旅行商问题”是一个十分有名的难以求解的优化问题,其要求很简单:在n个城市的集合中,找出一条经过每个城市各一次,最终回到起点的最短路径问题描述 如果已知城市A,B,C,D,之间的距离为dAB,dBC,dCD;那么总的距离ddAB+dBC+dCD+,对于这种动态规化问题,要去求其min(d)的解对于n个城市的全排列共有n!种,而TSP并没有限定路径的方向,即为全组合,所以对于固定的城市数n的条件下,其路径总数Sn为
21、Snn!2n(n4)在n个城市基础上,每添加一个城市,路径总数要添加n倍49504.3 TSP问题TSP的解是若干城市的有序排列,任何一个城市在最终路径上的位置可用一个n维的0、1矢量表示,对于所有n个城市,则需要一个nn维矩阵。以5个城市为例,一种可能的排列矩阵为514.3 TSP问题若用dxy表示从城市x到城市y的距离,则上面路径的总长度为:dxydCA+dAD+dDB+dBE+dCETSP的最优解是求长度dxy为最短的一条有效的路径 采用连续时间的霍普菲尔德网络模型来求解TSP,开辟了一条解决这一问题的新途径。其基本思想是把TSP映射到CHNN上,通过网络状态的动态演化逐步趋向稳态而自动
22、地搜索出优化解524.3 TSP问题目标函数f(V)约束条件g(V)约束条件要保证关联矩阵的每一行每一列中只有一个值为1,其他值均为零,用三项表示为总的能量函数E534.3 TSP问题选择使用高增益放大器,从而能量函数中的积分分项可以忽略不计。求解得网络的联接权值为式中外部输入偏置电流为544.3 TSP问题求解TSP的连接神经网络模型的运动方程可表示为霍普菲尔德和泰克(Tank)经过实验,认为取初始值为:SQP500,T200,RC1,U00.02时,其求解10个城市的TSP得到良好的效果。人们后来发现,用连续霍普菲尔德网络求解像TSP这样约束优化问题时,系统S、Q、P、T的取值对求解过程有很大影响 55五、内容小结设计Hopfield网络的目的是用来存储一些平衡点集,当给定初始状态后,该网络最终能在设计点上平衡。该网络是递归的,其输出反馈为网络的输入。在理想状态下,网络的输出恰好是原始的设计点网络的分类和模型DHNN的学习、性能与设计反馈网络的稳定性Hopfield网络可以作为误差纠正或向量归类网络。从理论上说,Hopfield网络有意义,但实际上很少使用。因为即使是最好的Hopfield网络,也会有伪平衡点,从而导致错误结果56五、内容小结下次课内容 自组织网络57The EndQuestions&SuggestionsThanks!58