第五章霍普菲尔德(Hopfield)神经网络.ppt

1、第五章霍普菲尔德（Hopfield）神经网络,前面介绍的网络模型属于前向NN，从学习的角度看，具有较强的学习能力，结构简单，易于编程。从系统角度看，属于静态的非线性映射，通过简单的非线性处理单元的复合映射可获得复杂的非线性处理能力。但他们因此缺乏反馈，所以并不是强有力的动力学系统。 联想特性是ANN的一个重要特性，主要包括联想映射和联想记忆。前馈网络具有诱人的联想映射能力，而不具备联想记忆能力。在反馈NN中，我们将着重介绍NN的联想记忆和优化计算的能力。,5.1 概述,联想记忆是指当网络输入某个矢量后，网络经过反馈演化，从网络输出端得到另一个矢量，这样输出矢量就称作网络从初始输入矢量联想得到的

2、一个稳定记忆，即网络的一个平衡点。 优化计算是指当某一问题存在多种解法时，可以设计一个目标函数，然后寻求满足这一目标函数的最优解法。例如，在很多情况下可以把能量函数作为目标函数，得到的最优解法需要使能量函数达到极小点，即能量函数的稳定平衡点。 总之，反馈网络的设计思想就是在初始输入下，使网络经过反馈计算最后到达稳定状态，这时的输出即是用户需要的平衡点。,1982年,美国加州工学院J.Hopfield提出了可用作联想存储器和优化计算的反馈网络,这个网络称为Hopfield神经网络(HNN)模型,也称Hopfield模型.并用它成功地探讨了旅行商问题(TSP)的求解方法。,HNN是一种循环NN,从

3、输出到输入有反馈连接. HNN有离散型和连续型两种.,Hopfield模型属于反馈型神经网络，从计算的角度上讲，它具有很强的计算能力。这样的系统着重关心的是系统的稳定性问题。稳定性是这类具有联想记忆功能神经网络模型的核心，学习记忆的过程就是系统向稳定状态发展的过程。Hopfield网络可用于解决联想记忆和约束优化问题的求解。,反馈网络(Recurrent Network),又称自联 想记忆网络,如下图所示:,反馈网络的目的是为了设计一个网络，储存一 组平衡点，使得当给网络一组初始值时，网络通过 自行运行而最终收敛到这个设计的平衡点上。 反馈网络能够表现出非线性动力学系统的动态 特性。它所具有的

4、主要特性为以下两点： 第一、网络系统具有若干个稳定状态。当网络从某一初始状态开始运动，网络系统总可以收敛到某一个稳定的平衡状态； 第二、系统稳定的平衡状态可以通过设计网络的权值而被存储到网络中。,由于HNN为动力学系统,且其平衡态关系到信息的存储与联想记忆,其平衡态与稳定性是非常关键的问题。 反馈网络根据信号的时间域的性质的分类为 如果激活函数f()是一个二值型的阶跃函数,则称此网络为离散型反馈网络,主要用于联想记忆; 如果f()为一个连续单调上升的有界函数,这类网络被称为连续型反馈网络,主要用于优化计算。,反馈NN由于其输出端有反馈到其输入端,所以,HNN在输入的激励下,会产生不断的状态变化

5、. 当有输入之后,可以求取出HNN的输出,这个输出反馈到输入从而产生新的输出,这个反馈过程一直进行下去. 如果HNN是一个能稳定的网络,则这个反馈与迭代的计算过程所产生的变化越来越小,一旦到达了稳定平衡状态,那么HNN就会输出一个稳定的恒值. 对于HNN来说,关键是在于确定它在稳定条件下的权系数. 应该指出,反馈网络有稳定的,也有不稳定的. 对于HNN来说,还存在如何判别它是稳定网络,亦或是不稳定的问题.而判别依据是什么,也是需要确定的.,反馈网络与前向网络的区别 结构不同 前向神经网络：没有反馈环节。 反馈神经网络：一个动态系统，存在稳定性问题。（关键问题） 模型不同 前向网络：从输入到输出

6、的映射关系，不考虑延时。 反馈网络：考虑延时，是一个动态系统，模型是动态方程（微分方程）。,网络的演变过程不同 前向网络：通过学习得到连接权然后完成指定任务。 反馈网络：(优化计算时)首先确定w（不是通过学习而来的，而是通过目标函数用解析算法得到的），设定网络的初始状态，然后系统运动，若稳定，则最后达到一个稳定状态，对应的输出就是优化问题的解。,学习方法不同 前向网络：误差修正算法（BP算法）。 反向网络：海布(Hebb)算法(用于联想、分类的时候),应用范围不同 前向网络：只能用于联想映射及其分类。 反馈网络：同时也可以用于联想记忆和约束优化问题的求解。,对于如HNN类似的反馈网络,研究的重

7、点为: 如何通过网络神经元状态的变迁而最终稳定于平衡状态,得到联想存储或优化计算的结果 网络的稳定性问题 怎样设计和利用稳定的反馈网络 网络系统能够达到稳定收敛 网络的稳定点 吸引域的设计,网络结构形式,Hopfield网络是单层对称全反馈网络，根据激励函数选取的不同，可分为离散型和连续性两种（ DHNN,CHNN）。 DHNN：作用函数为函数，主要用于联想记忆。 CHNN：作用函数为S型函数，主要用于优化计算,非线性系统状态演变的形式,在Hopfield网络中，由于反馈的存在，其加权 输入和ui，i=1n为网络状态，网络的输出为y1yn， 则u,y的变化过程为一个非线性动力学系统。可用非线性

8、差（微）分方程来描述。一般有如下的几种状态演变形式： （1）渐进稳定 （2）极限环 （3）混沌现象 （4）状态轨迹发散,网络结构及I/O关系,对于以符号函数为激励函数的网络，网络的方程可 写为： 图2.8.2,离散型 Hopfield神经网络,Hopfield网络为对称网络，wij=wji。当wii0时为无自反馈型，反之为全自反馈型,5.2 离散Hopfield网络,Hopfield最早提出的网络是神经元的输出为0-1二值的NN,所以,也称离散的HNN (简称为DHNN). 下面分别讨论DHNN的 结构 动力学稳定性(网络收敛性) 联想存储中的应用 记忆容量问题,在DHNN网络中,神经元所输出

9、的离散值1和0分别表示神经元处于兴奋和抑制状态. 各神经元通过赋有权重的连接来互联. 下面,首先考虑由三个神经元组成的DHNN,其结构如图1所示.,5.2.1离散Hopfield网络的结构,在图中,第0层仅仅是作为网络的输入,它不是实际神经元,所以无计算功能; 而第一层是实际神经元,故而执行对输入信息和权系数乘积求累加和,并由非线性函数f处理后产生输出信息. f是一个简单的阈值函效,如果 神经元的输入信息的综合大于阈值,那么,神经元的输出就取值为1; 小于阈值,则神经元的输出就取值为0. 对于二值神经元,它的计算公式如下,其中xj为外部输入,并且有 yj=1,当ujj时 yj=0,当ujj时,

10、对于DHNN,其网络状态是输出神经元信息的集合. 对于一个输出层是n个神经元的网络,则其t时刻的状态为一个n维向量: y(t)=y1(t),y2(t),.,yn(t) 因为yi(t)可以取值为1或0,故n维向量y(t),即网络状态,有2n种状态. 每一个时刻整个网络处于一个状态，状态的变化采用随机异步更新方式，即随机地选择下一个要更新的神经元，且允许所有神经元具有相同的平均变化概率。 节点状态更新包括三种情况：由0变为1、由1变为0和状态保持不变。按照单元异步更新工作方式，某一时刻网络中只有一个节点被选择进行状态更新，当该节点状态变化时，网络状态就以一概率转移到另一状态；当该节点状态保持时，网

11、络状态更新的结果保持前一时刻的状态。,对于3个神经元的DHNN,它的输出层就是3位二进制数.每一个3位二进制数就是一种网络状态,从而共有8个网络状态,如图2中所示.,在图中,立方体的每一个顶角表示一种网络状态.,同理,对于n个神经元的输出层,它有2n个网络状态,也和一个n维超立方体的顶角相对应. 如果HNN是一个稳定网络,那么在网络的输入端加入一个输入向量,则网络的状态会产生变化,也就是从超立方体的一个顶角转移向另一个顶角,并且最终稳定于某顶角.,对于一个由n个神经元组成的DHNN,则有nn权系数矩阵w=wij|i=1,2,.,n; j=1,2,.,n,同时,有n维阈值向量=1,2,.,n.

12、一般而言,w和可以确定一个唯一的DHNN. 对于图1所示的三神经元组成的HNN,也可以用图3所示的图形表示,这两个图形的意义是一样的.,考虑DHNN的节点状态,用yj(t)表示第j个神经元,即节点j在时刻t的状态,则节点的下一个时刻t+1的状态可以求出如下:,对图3所示的DHNN网络 当wi,j在i=j时等于0,则说明一个神经元的输出并不会反馈到它自己的输入. 这时,DHNN称为无自反馈网络. 当wi,j在i=j时不等于0,则说明个神经元的输出会反馈到它自己的输入. 这时,DHNN称为有自反馈的网络. DHNN有二种不同的工作方式: 串行(异步)方式和 并行(同步)方式. 下面分别加以介绍.,

13、(1) 串行(异步)方式 在时刻t时,只有某一个神经元j的状态产生变化,而其它n-1个神经元的状态不变这时称串行工作方式.并且有,在不考虑外部输入时,则有,(2) 并行(同步)方式 在任一时刻t,所有的神经元的状态都产生了变化,则称并行工作方式.并且有,在不考虑外部输入时,则有,通常网络从某一初始状态开始经过多次更新后才可能达到某一稳态。使用异步状态更新策略有以下优点： （1）算法实现容易，每个神经元节点有自己的状态更新时刻不需要同步机制； （2）以串行方式更新网络的状态可以限制网络的输出状态，避免不同稳态以等概率出现。 一旦给出HNN的权值和神经元的阈值，网络的状态转移序列就确定了。,例1：

14、计算如图5所示3节点DHNN的状态转移关系。考虑到DHNN的权值特性wijwji，可简化为图6右边的等价图。,图6 一个3节点的DHNN结构图,DHNN的状态变换,该网络的参数为： 现在以初态(可任意选定)v1v2v3(000)为例，以异步方式运行网络，考察各个节点的状态转移情况。现在考虑每个节点v1v2v3以等概率(13)被选择。假定首先选择节点v1，则节点状态为： 网络状态由(000)变化到(100)，转移概率为I3 假定首先选择节点v2，则节点状态为：,DHNN的状态变换,网络状态由(000)变化到(000)(也可以称为网络状态保持不变)，转移概率为13。 假定首先选择节点v3，则节点状

15、态为： 网络状态由(000)变化到(000)，转移概率为13。 从上面网络的运行看出，网络状态(000)不会转移到(010)和(001)，而以13的概率转移到(100)，以23的概率保持不变 同理，可以计算出其他状态之间 的转移关系如图所示。图中标出了 状态保持不变的转移概率，其余未 标注的均为13。,DHNN的状态变换,从这个例子，可以看出两个显著的特征： (1)状态(110)是一个满足前面定义的稳定状态。 (2)从任意初始状态开始，网络经过有限次状态更新后，都将到达该稳定状态。 Hopfield网络是一类反馈动力学系统，稳定性是这类系统的重要特性。对于这类模型，有如下稳定性判据： 当网络工

16、作在串行方式下时，若W为对称阵，且其对角元素非负，则其能量函数单调下降，网络总能收敛到一个稳定点。,5.2.2 DHNN的动力学稳定性,由于HNN为一非线性动力学系统,因此在其状态的演变过程中,存在一个动力学稳定性问题. 对于动力学系统来说,稳定性是一个重要的性能指标,也可以说是第一重要的性能指标. 对于DHNN, 在串行方式下的DHNN稳定性称之为串行稳定性. 同理,在并行方式的稳定性称之为并行稳定性. 在NN稳定时,其状态称稳定状态. 类似于研究动力学系统稳定性的Lyapunov稳定性分析方法,下面讨论HNN的动力学稳定性问题.,定义 对于DHNN,其状态为y(t): y(t)=y1(t)

17、,y2(t),.,yn(t) 如果,经有限时刻t,对于任何t0,有: y(t+t)=y(t) 则称网络是稳定的. 吸引子：若y(t)是网络的稳定状态，则称y(t)是网络的稳定吸引子。 吸引域：能够稳定在吸引子y(t)的所有初始状态y(0)的集合，称为吸引子y(t)的吸引域。,DHNN的能量函数,上例的状态转移关系有这样的规律：任意一个状态要么在同一“高度”变化，要么从上向下转移。 Hopfield网络模型是一个多输入、多输出、带阈值的二态非线性动力学系统。在满足一定的参数条件下，能量函数在网络运行过程中是不断降低、最后趋于稳定平衡状态的。 这种以能量函数作为网络计算的求解工具，被称为计算能量函

18、数。Hopfield网络状态变化分析的核心是对每个网络的状态定义一个能量E，任意一个神经元节点状态发生变化时，能量值都将减小。 假设第i个神经元节点状态vi的变化量记为vi相应的能量变化量记为Ei。所谓能量Ei随状态变化而减小意味着Ei总是负值。 考察两种情况： (1)当状态vi由0变为1时， vi 0。 (2)当状态vi由1变为0时， vi 0。,按照能量变化量为负的思路，可将能量的变化量Ei表示为 故节点i的能量可定义为：,显然E是对所有的Ei按照某种方式求和而得到，即式中出现的12因子。其原因在于离散Hopfield网络模型中，wij=wji，如直接计算E，将会对Ei中的每一项计算两次。

19、如上例中对于3个节点的网络，其节点能量为：,由上面给出E定义，显然有： （1）在离散Hopfield模型状态更新过程中，能量函数E随状态变化而严格单调递减。 （2）离散Hopfield模型的稳定状态与能量函数E在状态空间的局部极小点是一一对应的。,从DHNN可以看出: 它是一种多输入,含有阈值的二值非线性动力系统. 在动力系统中,平衡稳定状态可以理解为系统的某种形式的能量函数在系统运动过程中,其能量值不断减小,最后处于最小值. 因此,对HNN可引入一个Lyapunov函数,即所谓能量函数:,即有,对HNN的能量函数有几点说明: 当对反馈网络应用能量函数后,从任一初始状态开始,因为在每次迭代后都

20、能满足E0,所以网络的能量将会越来越小. 由于能量函数存在下界,因此其最后趋于稳定点E=0. Hopfield能量函数的物理意义是: 在那些渐进稳定点的吸引域内,离吸引点越远的状态,所具有的能量越大. 由于能量函数的单调下降特性,保证状态的运动方向能从远离吸引点处,不断地趋于吸引点,直到达到稳定点.,能量函数是反馈网络中的重要概念.根据能量函数可以方便的判断系统的稳定性; Hopfield选择的能量函数,只是保证系统稳定和渐进稳定的充分条件,而不是必要条件,其能量函数也不是唯一的. 在状态更新过程中，包括三种情况：由0变为1；由1变为0及状态保持不变。,类似于研究动力学系统稳定性的Lyapun

21、ov稳定性理论,上述DHNN的稳定性可由分析上述定义的Lyapunov函数E的变化规律而揭示. 因此,由神经元j的状态变化量yj(t)所引起的的能量变化量Ej为:,若所讨论的HNN是对称网络,即有wi,j=wj,i,i,j=1,2,.,n,则有,则 yj(t+1)=fuj(t)-j 式(3)则可记为: Ej(t)=-uj(t)+jyj(t) (3A) 下面分别对 串行异步方式和 并行同步方式, 证明对称二值型HNN是稳定的.,如果,令,A.串行异步方式 对串行异步和对称权值型的HNN,基于式(3A) Ej(t)=-uj(t)+jyj(t) (3A) 考虑如下两种情况: 如果ujj,即神经元j的

22、输入综合大于阈值,则从二值神经元的计算公式知道: yj的值保持为1,或者从0变到1. 这说明yj的变化yj只能是0或正值.这时很明显有Ej: Ej0 这说明HNN神经元的能量减少或不变.,如果ujj,即神经元j的输入综合小于阈值,则知yj的值保持为0,或者从1变到0,而yj小于等于零.这时则有Ej: Ej0 这也说明HNN神经元的能量减少. 上面两点说明了DHNN在权系数矩阵W的对角线元素为0,而且W矩阵元素对称时,串行异步方式的DHNN是稳定的.,B. 并行同步方式 由上述对串行异步和对称权值型的DHNN的稳定性分析过程知,单个神经元的状态变化引起的Lyapunov函数的变化量 Ej(t)0

23、 因此, 并行同步且权值对称的DHNN的所有神经元引起的 Lyapunov函数的变化量为:,故上面两点说明了DHNN在权系数矩阵W的对角线元素为0, 而且W矩阵元素对称时,并行同步方式的DHNN是稳定的.,基于上述分析,Coben和Grossberg在1983年给出了关于HNN稳定的充分条件,他们指出: 如果权系数矩阵W是一个对称矩阵,并且,对角线元素为0.则这个网络是稳定的. 即是说在权系数矩阵W中,若 i=j时, Wij=0 ij时,Wij=Wji 则HNN是稳定的. 应该指出: 这只是HNN稳定的充分条件,而不是必要条件. 在实际中有很多稳定的HNN,但是它们并不满足权系数矩阵w是对称矩

24、阵这一条件.,由上面的分析可知: 无自反馈的权系数对称HNN是稳定. 它如图4所示.,例2：计算例1中3节点模型的个状态的能量。 首先选择状态y1y2y3=（011），此时，网络的能量为： 再选择状态y1y2y3=（110），同理，网络的能量为：,其余状态能量如表2所示：,显然，状态y1y2y3=（110）处的能量最小。从任意状态开始，网络沿能量减小（包括同一级能量）方向更新状态，最终能达到对应能量极小的稳态。,例：运行图所示4节点模型，并计算其各状态的能量。 任意给定一个初始状态为： v(0)1,0,1,0，先计算E(0)得 E(0)1.0 第一轮迭代： v1(1)sgn(2.8-6.3)=

25、sgn (-3.5)=0 v2(1) sgn(3.4+4.7-(-4.3)=sgn (12.4)= 1 v3(1) sgn(2.8-(-2.5)=sgn (5.3)= 1 v4(1) sgn(-3.1-5.9-(-9.6)=sgn (0.6)= 1 E(1)-14.0 v1(2)sgn(3.4+2.8-3.1-6.3)=sgn (-3.2)=0 v2(2) sgn(4.7-1.2-(-4.3)=sgn (7.8)= 1 v3(2) sgn(4.7-5.9-(-2.5)=sgn (1.3)= 1 v4(2) sgn(-1.2-5.9-(-9.6)=sgn (2.5)= 1 E(2)-14.0,D

26、HNN的能量函数,因此，v0,1,1,1是网络的一个稳定状态。实际上此例中有4个神经元其可能的状态有16个，为便于验算，将其各状态的能量列表如下：,显然，网络稳定状态下的能量为最小值-14。 网络能量极小状态即为网络的一个稳定平衡状态。能量极小点的存在为信息的分布式存储记忆、优化计算提供了基础。如果将记忆的样本信息存贮于不同的能量极小点，当输入某一模式时，网络就能“联想记忆”与其相关的存储样本，实现联想记忆。,DHNN能量极小点的设计,只有当网络的能量极小点可被选择和设定时，网络所具有的能力才能发挥作用。 能量极小点的分布是由网络的连接权值和阈值所决定的。因此设计能量极小点的核心就是如何获取一

27、组合适的参数值。 有两种方法供选择： (1)根据求解问题的要求直接设计出所需要的连接枚值 (2)通过提供的附加机制来训练网络，使其自动调整连接权值，产生期望的能量极小点。 前者为静态学习方法，对于一个具体应用而言，权矩阵为定常矩阵、如TSP求解等。后者为动态学习方法，如联想记忆等。,例 以3节点Hopfield网络为例，假定要求设计的能量极小点为状态v1v2v3(010)和v1v2v3(111)，且网络参数(权值、阂值)的取值范围为-1,1试确定满足条件的网络参数。 记v1v2v3(010)为状态A，v1v2v3(111)为状态B 对于状态A，节点激励函数必须满足下列不等式： 对于状态B，节点

28、激励函数必须满足下列不等式：,用上面的不等式组，可以求解出6个未知量的允许取值范围。 假设取w120.5，则： 由(a)式，0.511，取10.7 由(d)式，0.2w13 1，取W130.4 由(b)式，-120，取2-0.2 由(e)式，-0.7w231，取w230.1 由(c)式，0.13 1，取30.4；3也满足(f)式。 于是，确定了一组权值和阈值： w120.5，w130.4，w230.1 10.7，2-0.2，30.4 可以验证，利用这组参数构成的Hopfield网络对于任何起始状态，始终都将达到所期望的稳态A和稳态B,DHNN能量极小点的设计,5.2.3 HNN的联想记忆,所谓

29、联想可以理解为从一种事物联系到与其相关的事物的过程. 日常生活中,从一种事物出发,人们会非常自然地联想到与该事物密切相关或有因果关系的种种事务. 两种联想形式 自联想(Auto-association) : 由某种代表事物(或该事物的主要特征,或部分主要特征)联想到其所标示的实际事物。 从英文字头“Newt”联想到“Newton”。 听到歌曲的一部分可以联想起整个曲子。,异联想(他联想)(Hetero -association) : 由一种事物(或该事物的主要特征,或部分主要特征)联想到与其密切相关的另一事物。 从质能关系式E=mc2联想到其发明者爱因斯坦。 看到某人的名字会联想起他的相貌和特

30、点。 人脑从一种事物得到对应事物的两种途径 按时间顺序对相关事物进行思考 可通过时间表来回忆某一阶段所做的工作. 通过事物本质特征的对比来确定事物的属性 由提示信息或局部信息对事物进行回忆或确认.,HNN的一个功能是可用于联想记忆,也即是联想存储器.这是人类的智能特点之一. 人类的所谓“触景生情”就是见到一些类同过去接触的景物,容易产生对过去情景的回昧和思忆. 对于HNN,用它作联想记忆时,首先通过一个学习训练过程确定网络中的权系数,使所记忆的信息在网络的n维超立方体的某一个顶角的能量最小. 当网络的权系数确定之后,只要向网络给出输入向量,这个向量可能是局部数据. 即不完全或部分不正确的数据,

31、但是网络仍然产生所记忆的信息的完整输出.,1984年Hopfield提出一种用n维HNN作联想存储器的结构. HNN联想存储器的主要思想为: 根据欲存储的信息的表示形式和维数,设计相应的HNN结构 将欲存储的信息设计为HNN的动力学过程的已知的渐近稳定平衡点 通过学习和设计算法寻求合适的权值矩阵将稳定状态存储到网络中,在HNN联想存储器中,权系数的赋值规则Hebb规则,即为存储向量的外积存储规则,其原理如下: 设有m个样本存储向量X1,X2,Xm,其中 Xi=Xi1,Xi2,.,Xi,n 把这m个样本向量存储入HNN中,则在网络中第i,j两个节点 之间权系数的值为(权值学习规则):,其中k为样

32、本向量Xk的下标,k=1,2,m; i,j分别是样本向量Xk的第i,j分量Xk,i,Xk,j的下标.,如果把系统的稳定点视做一个记忆的话，那么从初始状态朝这个稳定点移动的过程就是寻找该记忆的过程。,用 DHNN实现联想记忆需要考虑两个重要的问题： 怎样按记忆确定网络的W和； 网络给定之后如何分析它的记忆容量。下面将分别讨论： 1、权值的设计方法 2、记忆容量分析 3、权值修正的其它方法,权值的设计方法,权值设计的方法有外积法、伪逆法、正交设计法等。 外积法（Hebb学习规则）：是一种比较简单，在一定条件下行之有效的方法。,按上述规则求出权矩阵后，网络已经将模式存入网络的连接权中。在联想过程中，

33、先给出一个原始模式，使网络处于某种初始状态下，用网络方程动态运行，最后达到一个稳定状态。如果此稳定状态对应于网络已存储的某个模式，则称模式是由模式联想起来的。,记忆容量问题,设计DHNN网络的目的,是希望通过所设计的权值矩阵W储存多个期望模式. 因此,在DHNN用于联想记忆问题,记忆容量问题是一个必须回答的基本问题. 当网络只记忆一个稳定模式时,该模式肯定被网络准确无误地记忆住,即所设计的W值一定能够满足正比于输入和输出矢量的乘积关系. 但当需要记忆的模式增多时,网络记忆可能出现问题.,按照Hebb规则求出权矩阵后，可以认为已有M个模式存入网络的连接权中。在联想过程中，先给出原始模式m0，使网

34、络处于某种初始状态下，用网络方程动态运行，最后到达一个稳定状态。如果此稳定状态对应于已存储的M个模式中的某个模式mk,则称模式mk是由模式m0联想起来的。在这里举例说明。 例3.对于一个4神经元的网络，取阈值为0。给定两个模式存储于网络中： m1:Y(1)=y1,y2,y3,y4=1,1,1,1, m2:Y(2)=y1,y2,y3,y4=-1,-1,-1,-1.,按照Hebb规则 可求得权矩阵：,给出用于联想的原始模式： mA:Y=y1,y2,y3,y4=1,1,-1,1, 运用网络方程：,得到： Y(1)=1,1,1,1, 再次运行，得到 Y(2)=1,1,1,1。 这时网络已处于稳定状态：

35、Y=1,1,1,1。而这个稳定状态正好是网络已记忆的模式m1，由此可以认为m1是由模式mA联想起来的。,若给出用于联想的原始模式为： mB:Y=y1,y2,y3,y4=-1,-1,-1,1, 则得到另一稳定状态 Y=-1,-1,-1,-1 即模式m2。,再看一例。 例4.存储如下记忆模式：若给出用于联想的原始模式为： m1:Y(1)=y1,y2,y3,y4=-1,1,1,1, m2:Y(2)=y1,y2,y3,y4=-1,-1,1,1, m3:Y(3)=y1,y2,y3,y4=-1,1,1,-1. 则其权矩阵为：,给出联想模式： m3:Y(3)=y1,y2,y3,y4=-1,1,1,-1. 但

36、网络运行稳定在模式 m1:Y(1)=-1,1,1,1 而不是其自身模式m3。,因此，DHNN用于记忆联想时，是受其记忆容量和样本差异制约的。当记忆模式较少，且模式之间的差异较大，则联想的结果就比较正确；而当需记忆的模式较多，容易引起混淆时，网络到达的稳定状态往往不是已记忆的模式；再者，当需记忆的模式之间较为相近时，网络就不能辨别出正确的模式，甚至连自身都会搞错，即使用已记忆的模式作为联想模式（自联想），也可能出错，如例4。,当网络只记忆一个稳定的模式时，该模式肯定被网络准确无误的记忆住。但当所要记忆的模式增加时，情况则发生了变化，主要表现在下列两点上： 1、权值移动 2、交叉干扰,当网络用于联

37、想记忆时，就涉及到网络的记忆容量问题。对此不做专门讨论，仅给出一些研究结果。,权值移动,在网络的学习过程中，网络对权值的记忆实际上是逐个实现的。即对权值W，有程序: 当网络准确的记忆X1时，为了记忆X2,需要在记忆样本X1的权值上加上对样本X2的记忆项X2 X2T-I，将权值在原来值的基础上产生了移动。这样网络有可能部分地遗忘了以前已记忆的模式。,从动力学的角度来看，k值较小时，网络Hebb学习规则可以使输入学习样本成为其吸引子。随着k值的增加，不但难以使后来的样本成为网络的吸引子，而且有可能使以记忆住的吸引子的吸引域变小，使原来处于吸引子位置上的样本从吸引子的位置移动。对一记忆的样本发生遗忘

38、，这种现象称为“疲劳”。,交叉干扰,网络在学习多个样本后，在回忆阶段，即验证该记忆样本时所产生的干扰，称为交叉干扰。 对外积型设计而言，如果输入样本是彼此正交的，n个神经元的网络其记忆容量的上界为n。但是在大多数情况下，学习样本不可能是正交的，因而网络的记忆容量要比n小得多，一般为(0.130.15)n。,权值修正的其它方法,1、学习规则 2、伪逆法 3、正交化权值设计,学习规则,学习规则基本公式是： 即通过计算该神经元节点的实际激励值A(t)，与期望状态T(t)进行比较，若不满足要求，将两者的误差的一部分作为调整量，若满足要求，则相应的权值保持不变。,伪逆法,用伪逆法求出的权W可以保证在自己

39、输入时仍能收敛到样本自己。如果N与输入X完全相同，则W也可以是对称的，因而满足稳定工作的条件。其实只要满足Y矩阵中每一个元与WX矩阵中的每个元有相同的符号就可以满足收敛到本身。,正交化权值设计,这一方法是由Li和Mechel提出来的，其出发点为： (1)要保证系统在异步工作时的稳定性，则它的权是对称的 (2 )要保证所有的要求的记忆样本都能收敛到自己，不会出现错误的其他收敛值 (3)要求伪稳定点的数目尽可能地少。 (4)要求稳定点吸引域尽可能地大。 其状态转换公式为,Hopfield网络解决TSP问题,（1）TSP（Traveling Saleman Problem)问题描述：对于有n个城市的

40、集合，找出一条最短的经过每个城市各一次（仅一次）且回到出发地的路径。 （2）简单数学分析：n个城市间存在n!/(2n)条可能路径，路径总数随n按指数规律增长，对于较大的n，先找出所有可能的路径，然后再对其进行比较以得到最短路径的方法难以在计算机上以较短的时间得到答案。 （3）神经网络方法：先把问题转化成适合于神经网络处理的形式。用n*n个神经元构成网络，用神经元的状态来表示某一个城市在某一条有效路径中的位置。,dxy城市X与城市Y之间的距离； yxi城市X的第i个神经元的状态： 1 城市X在第i个被访问 yxi= 0 城市X不在第i个被访问 wxi,yj城市X的第i个神经元到城市Y的第j个神经

41、元的连接权。,Hopfield网络解决TSP问题,例如：四个城市X、Y、Z、W。下表输出状态矩阵可唯一地确定对所有城市的访问次序。,Hopfield网络解决TSP问题,为了解决TSP问题，必须构成这样的网络：在网络运行时，计算能量降低。网络稳定后其输出状态代表城市被访问的次序，即构成上表所示的换位阵。网络能量的极小点对应于最佳（或较佳）路径的形成，此时由输出换位阵能得到较佳路径。 解决问题最关键的一步，是构成合适的能量函数。,Hopfield网络解决TSP问题,网络的能量函数,其中A0为常数。E1保证当输出状态矩阵的每一行不多于一个1时，即所有的城市最多只被访问一次时取得极小值0。,路径的有效

42、性。 为保证输出构成换位阵，因此有行约束条件,网络的能量函数,其中B0为常数。E2保证当输出状态矩阵的每一列不多于一个1时，即当每次最多只访问一个城市时取得极小值0。,同理可构成列约束条件,网络的能量函数,其中C0为常数。E3当保证当输出状态矩阵中1的个数为n时，即且仅当所有的n个城市一共被访问n次时才取得最小值0。,接着构成全局约束条件,以上三式之和达到最小时，能保证网络输出状态矩阵构成换位阵。,网络的能量函数,其中D0为常数。E4表实际数值就是一次有效路径总长度的倍数。若路径为最佳的，则E4达到最小点，若路径为较佳的，则E4达到极小点。,路径的合理性,网络的能量函数,至此，可构成Hopfi

43、eld网络求解TSP问题的能量函数为：,Hopfield网络解决TSP问题,连接矩阵 wxi,yj= -Axy(1-ij) Bij(1-xy) C dxy(j，i+1+j，i-1) 1如果i=j ij= 0如果ij,根据Hopfield网络求解TSP问题的能量函数，可反推出神经网络的结构，即神经元之间的连接权值。,Hopfield模型应用实例8皇后问题,问题描述 8皇后问题是：给定一个标准的棋盘和8个皇后，要求正确地放置8个皇后，使得没有任何一个皇后可以攻击到另外的一个皇后。这里我们将用Hopfield模型求解这一问题。,Hopfield模型应用实例8皇后问题,能量函数的定义 定义 , 。表示

44、处于位置( i , j )的方块。有：,Hopfield模型应用实例8皇后问题,能量函数的定义 考察下式： 该式表明当每行只有一个皇后时，该式可以取得最小值0，否则该式的值将大于0。,Hopfield模型应用实例8皇后问题,能量函数的定义 考察下式： 该式表明当每列只有一个皇后时，该式可以取得最小值0，否则该式的值将大于0。,Hopfield模型应用实例8皇后问题,能量函数的定义 每条对角线只有一个皇后时，该式取最小值。,Hopfield模型应用实例8皇后问题,能量函数的定义 每条对角线只有一个皇后时，该式取最小值。,Hopfield模型应用实例8皇后问题,能量函数的定义 显然，H取得最小值时

45、，可以得到最优解。,其连接矩阵可以构造如下：,L表示模式向量为L对。,BAM是一个双层回归联想存贮器，是Hopfield网络的扩展， 也是内容编址存贮器，但各单元可以有自反馈。,双向联想存贮器（BAM）,为了构造Y层到X层的权值矩阵，将W取成WT即可。,BAM是双向的，输入和输出取决于转播方向。,BAM数学上处理如下：,netY 是Y 层总输入，各单元的输入：,在X层：,netX 是X 层总输入，各单元的输入：,举例：,连续Hopfield网络,CHNN是在DHNN的基础上提出的，它的原理 和DHNN相似。由于CHNN是以模拟量作为网络的 输入输出量，各神经元采用并行方式工作，所以 它在信息处

46、理的并行性、联想性、实时性、分布 存储、协同性等方面比DHNN更接近于生物神经 网络。 1、网络模型 2、CHNN方程的解及稳定性分析 3、关于Hopfield能量函数的几点说明 4、关于CHNN的几点结论,CHNN的网络模型,对于神经元，放大器的I/O关系可用如下的方程来描述：,CHNN的网络模型,对I/O方程变形得：,该动态方程描述了神经元i的输出和其内部状态ui之间的关系。 CHNN实质上是连续的非线性动力学系统，由一组非线性微分方程来描述。 当给定初始状态，通过求解非线性微分方程组即可求得网络状态的运动轨迹。 若系统是稳定的，则它最终可收敛到一个稳定状态。 若用模拟电路的硬件来实现该模

47、型，则这个求解非线性微分方程的过程将由该电路自动完成，其求解速度非常快。 CHNN有如下一些特性： (1)系统在运行过程中，其能量函数将会逐渐减小到某一极小状态。 (2)系统的极小状态一般不止一个，存在有限个平衡点 (3)CHNN可以用模拟电路实现。电路中的放大器和电阻电容等器件的电气特性在物理上对生物神经网络的某些特征有较好的模拟。,CHNN方程的解及稳定性分析,对于CHNN来说，关心的同样是稳定性问题。在所有影响电路系统稳定的参数中，一个比较特殊的参数值是放大器的放大倍数。当放大器的放大倍数足够大时，网络由连续性转化成离散型，状态与输出之间的关系表现了建立函数的形状，而正是激励函数代表了一

48、个网络的特点，所以着重分析不同激励函数关系对系统的稳定性的影响。,当激励函数为线性函数时,对于非线性系统进行稳定性分析，方法之一就是在系统的平衡点附近对系统进行线性化处理。也可以基于网络的能量函数。下面介绍Hopfield能量函数法。,此定理表明，随着时间的演化，网络的状态总是朝能量减少的方向运动，网络的平衡点就是E的极小点。,关于Hopfield能量函数的几点说明,当对反馈网络应用能量函数后，从任一初始状态开始，因为在每次迭代后都能满足E0，所以网络的能量将会越来越小，最后趋于稳定点E=0。 Hopfield能量函数的物理意义是：在那些渐进稳定点的吸引域内，离吸引点越远的状态，所具有的能量越

49、大，由于能量函数的单调下降特性，保证状态的运动方向能从远离吸引点处，不断地趋于吸引点，直到达到稳定点。,几点说明： 1 能量函数为反馈网络的重要概念。根据能量函数可以方便的判断系统的稳定性； 2 Hopfield选择的能量函数，只是保证系统稳定和渐进稳定的充分条件，而不是必要条件，其能量函数也不是唯一的。,关于CHNN的几点结论,1）具有良好的收敛性； 2）具有有限个平衡点； 3）如果平衡点是稳定的，那么它也一定是渐进稳定的； 4）渐进稳定平衡点为其能量函数的局部极小点； 5）能将任意一组希望存储的正交化矢量综合为网络的渐进平衡点； 6）网络的存储信息表现为神经元之间互连的分布式动态存储； 7

50、）网络以大规模、非线性、连续时间并行方式处理信息，其计算时间就是网络趋于平衡点的时间。,Hopfield网络在组合优化中的应用,组合优化问题，就是在给定约束条件下，求出使目标函数极小（或极大）的变量组合问题。 将Hopfield网络应用于求解组合优化问题，就是把目标函数转化为网络的能量函数，把问题的变量对应于网络的状态。这样当网络的能量函数收敛于极小值时，问题的最优解也随之求出。,旅行商问题，简称TSP（Traveling Salesman Problem）。问题的提法是：设有N个城市， ,记为： ,用dij表示ci和cj之间的距离， dij0,(i,j=1,2,n) 。 有一旅行商从某一城市出发，访问各城市一次且仅一次后再回到原出发城市。要求找出一条最短的巡回路线。,N=5 TSP Probelm,n=5，并用字母A、B、C、D、E、分别代表这5个城市。当任选一条路径如B-D-E-A-C,，则其总路径长度可表示为 第一步就是将问题映射到一个神经网络。假定每个神经元的放大器有很高的放大倍数，神经元的输出限制在二值0和1上，则映射问题可以用一个换位矩阵（PM, Permutation Matrix）来进行，换位矩阵可如下图所示。,换位矩阵,对于n个城市需用由n2个神经元构成的n x n阶PM来表示旅行路线。在该换位矩阵中每一列只有一个元素为1，其余