《Hopfield网络》PPT课件.ppt

第五章 霍普菲尔德（Hopfield） 神经网络,1985年，J.J.Hopfield和D.W.Tank建立了相互连接型的神经网络模型，简称HNN(Hopfield Neural Network)，并用它成功地探讨了旅行商问题(TSP)的求解方法。前几章介绍的神经网络模型属于前向神经网络，从学习的观点上看，它们是强有力的学习系统，结构简单，易于编程。从系统的观点看，它们属于一种静态的非线性映射，通过简单非线性处理单元的复合映射可获得复杂的非线性处理能力，但它们因缺乏反馈，所以并不是一个强有力的动力学系统。 Hopfield模型属于反馈型神经网络，从计算的角度上讲，它具有很强的计算能力。这样的系统着重关心的是系统的稳定性问题。稳定性是这类具有联想记忆功能神经网络模型的核心，学习记忆的过程就是系统向稳定状态发展的过程。Hopfield网络可用于解决联想记忆和约束优化问题的求解。,反馈型神经网络作为非线性动力学系统，可表现出丰富多样的动态特性，如稳定性、极限环、奇怪吸引子(混沌)等。这些特性是神经网络引起研究人员极大兴趣的原因之一。研究表明，由简单非线性神经元互连而成的反馈动力学神经网络系统具有两个重要特征： 1. 系统有若干个稳定状态，如果从某一个初始状态开始运动，系统总可以进入其中某一个稳定状态； 2. 系统的稳定状态可以通过改变各个神经元间的连接权值而得到。 Hopfield神经网络设计与应用的关键是对其动力学特性的正确理解：网络的稳定性是其重要性质，而能量函数是判定网络稳定性的基本概念。,网络结构形式,Hopfield网络是单层对称全反馈网络，根据激励函数选取的不同，可分为离散型和连续性两种（ DHNN,CHNN）。 DHNN：作用函数为函数，主要用于联想记忆。 CHNN：作用函数为S型函数，主要用于优化计算,非线性系统状态演变的形式,在Hopfield网络中，由于反馈的存在，其加权 输入和ui，i=1n为网络状态，网络的输出为y1yn， 则u,y的变化过程为一个非线性动力学系统。可用非线性差（微）分方程来描述。一般有如下的几种状态演变形式： （1）渐进稳定 （2）极限环 （3）混沌现象 （4）状态轨迹发散,网络结构及I/O关系,对于以符号函数为激励函数的网络，网络的方程可 写为： 图2.8.2,离散型 Hopfield神经网络,Hopfield网络为对称网络，wij=wji。当wii0时为无自反馈型，反之为全自反馈型,两种工作方式,（1）串行工作方式 在某一时刻只有一个神经元改变状态，而其它神经元的输出不变。这一变化的神经元可以按照随机的方式或预定的顺序来选择。 （2）并行工作方式 在某一时刻有N个神经元改变状态，而其它的神经元的输出不变。变化的这一组神经元可以按照随机方式或某种规则来选择。当N=n时，称为全并行方式。,DHNN的稳定工作点,DHNN的状态变换,从Hopfield网络的模型定义中可以看到对于n节点的HNN有2n个可能的状态，即网络状态可以用一个包含0和1的矢量表示 每一个时刻整个网络处于一个状态，状态的变化采用随机异步更新方式，即随机地选择下一个要更新的神经元，且允许所有神经元具有相同的平均变化概率。 节点状态更新包括三种情况：由0变为1、由1变为0和状态保持不变。 按照单元异步更新工作方式，某一时刻网络中只有一个节点被选择进行状态更新，当该节点状态变化时，网络状态就以一概率转移到另一状态；当该节点状态保持时，网络状态更新的结果保持前一时刻的状态。,DHNN的状态变换,通常网络从某一初始状态开始经过多次更新后才可能达到某一稳态。使用异步状态更新策略有以下优点： （1）算法实现容易，每个神经元节点有自己的状态更新时刻不需要同步机制； （2）以串行方式更新网络的状态可以限制网络的输出状态，避免不同稳态以等概率出现。 一旦给出HNN的权值和神经元的阈值，网络的状态转移序列就确定了。,DHNN的状态变换,例 计算如图所示3节点HNN的状态转移关系。 该网络的参数为： 现在以初态(可任意选定)v1v2v3(000)为例，以异步方式运行网络，考察各个节点的状态转移情况。现在考虑每个节点v1v2v3以等概率(13)被选择。假定首先选择节点v1，则节点状态为： 网络状态由(000)变化到(100)，转移概率为I3 假定首先选择节点v2，则节点状态为：,DHNN的状态变换,网络状态由(000)变化到(000)(也可以称为网络状态保持不变)，转移概率为13。 假定首先选择节点v3，则节点状态为： 网络状态由(000)变化到(000)，转移概率为13。 从上面网络的运行看出，网络状态(000)不会转移到(010)和(001)，而以13的概率转移到(100)，以23的概率保持不变 同理，可以计算出其他状态之间 的转移关系如图所示。图中标出了 状态保持不变的转移概率，其余未 标注的均为13。,DHNN的状态变换,从这个例子，可以看出两个显著的特征： (1)状态(110)是一个满足前面定义的稳定状态。 (2)从任意初始状态开始，网络经过有限次状态更新后，都将到达该稳定状态。 Hopfield网络是一类反馈动力学系统，稳定性是这类系统的重要特性。对于这类模型，有如下稳定性判据： 当网络工作在串行方式下时，若W为对称阵，且其对角元素非负，则其能量函数单调下降，网络总能收敛到一个稳定点。,DHNN的能量函数,上例的状态转移关系有这样的规律：任意一个状态要么在同一“高度”变化，要么从上向下转移。 Hopfield网络模型是一个多输入、多输出、带阈值的二态非线性动力学系统。在满足一定的参数条件下，能量函数在网络运行过程中是不断降低、最后趋于稳定平衡状态的。 这种以能量函数作为网络计算的求解工具，被称为计算能量函数。Hopfield网络状态变化分析的核心是对每个网络的状态定义一个能量E，任意一个神经元节点状态发生变化时，能量值都将减小。 假设第i个神经元节点状态vi的变化量记为vi相应的能量变化量记为Ei。所谓能量Ei随状态变化而减小意味着Ei总是负值。 考察两种情况： (1)当状态vi由0变为1时， vi 0。 (2)当状态vi由1变为0时， vi 0。,DHNN的能量函数,按照能量变化量为负的思路，可将能量的变化量Ei表示为 故节点i的能量可定义为：,显然E是对所有的Ei按照某种方式求和而得到，即式中出现的12因子。其原因在于离散Hopfield网络模型中，wij=wji，如直接计算E，将会对Ei中的每一项计算两次。如上例中对于3个节点的网络，其节点能量为：,DHNN的能量函数,DHNN的能量函数,由上面给出E定义，显然有： （1）在离散Hopfield模型状态更新过程中，能量函数E随状态变化而严格单调递减。 （2）离散Hopfield模型的稳定状态与能量函数E在状态空间的局部极小点是一一对应的。 上例中各状态的能量为,DHNN的能量函数,显然，状态v1v2v3(110)处的能量最小。下图右边的数值变化说明了能量单调下降的对应状态。从任意初态开始，网络沿能量减小(包括同一级能量)方向更新状态，最终能达到对应能量极小的稳态。,DHNN的能量函数,例：运行图所示4节点模型，并计算其各状态的能量。 任意给定一个初始状态为： v(0)1,0,1,0，先计算E(0)得 E(0)1.0 第一轮迭代： v1(1)sgn(2.8-6.3)=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,DHNN的能量函数,因此，v0,1,1,1是网络的一个稳定状态。实际上此例中有4个神经元其可能的状态有16个，为便于验算，将其各状态的能量列表如下：,显然，网络稳定状态下的能量为最小值-14。 网络能量极小状态即为网络的一个稳定平衡状态。能量极小点的存在为信息的分布式存储记忆、优化计算提供了基础。如果将记忆的样本信息存贮于不同的能量极小点，当输入某一模式时，网络就能“联想记忆”与其相关的存储样本，实现联想记忆。,DHNN能量极小点的设计,只有当网络的能量极小点可被选择和设定时，网络所具有的能力才能发挥作用。 能量极小点的分布是由网络的连接权值和阈值所决定的。因此设计能量极小点的核心就是如何获取一组合适的参数值。 有两种方法供选择： (1)根据求解问题的要求直接设计出所需要的连接枚值 (2)通过提供的附加机制来训练网络，使其自动调整连接权值，产生期望的能量极小点。 前者为静态学习方法，对于一个具体应用而言，权矩阵为定常矩阵、如TSP求解等。后者为动态学习方法，如联想记忆等。,DHNN能量极小点的设计,例 以3节点Hopfield网络为例，假定要求设计的能量极小点为状态v1v2v3(010)和v1v2v3(111)，且网络参数(权值、阂值)的取值范围为-1,1试确定满足条件的网络参数。 记v1v2v3(010)为状态A，v1v2v3(111)为状态B 对于状态A，节点激励函数必须满足下列不等式： 对于状态B，节点激励函数必须满足下列不等式：,DHNN能量极小点的设计,用上面的不等式组，可以求解出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能量极小点的设计,DHNN能量极小点的设计,按照上述方法在设计能量极小点时，网络的权值和网值可在某个允许区间内取值。因而所选择的一组参数虽然满足了能量极小点设计的要求，但同时也可能产生设计所不期望的能量极小点。 比如，如果选择的权值和阈值为： w12-0.5， w130.5， w230.4； 1-0.1， 2-0.2， 30.4， 可以验证，这组值也满足(a)一(f)不等式组，但是这组参数构成的Hopfield网络有三个能量极小点，包括期望的(010)和(111)以及(100)。,DHNN能量极小点的设计,DHNN的学习和联想记忆,Hopfield网络可用于联想记忆。当它用于计算时，其权矩阵给定为W，目的是寻找具有最小能量E的网络稳定状态；而作为记忆的学习时稳定状态是给定的，通过网络的学习求合适的权矩阵W(对称阵)。一旦学习完成后，以计算的方式进行联想。 前面设计能量极小点是根据问题的要求用手工计算得到一组网络的参数。而网络的学习是通过一定的学习算法，自动地得到所需要的参数。对于Hopfield网络，可以采用Hebb学习规则和误差型学习算法。,DHNN的学习和联想记忆,用 DHNN实现联想记忆需要考虑两个重要的问题： 怎样按记忆确定网络的W和； 网络给定之后如何分析它的记忆容量。下面将分别讨论： 1、权值的设计方法 2、记忆容量分析 3、权值修正的其它方法,权值的设计方法,权值设计的方法有外积法、伪逆法、正交设计法等。 外积法（Hebb学习规则）：是一种比较简单，在一定条件下行之有效的方法。,按上述规则求出权矩阵后，网络已经将模式存入网络的连接权中。在联想过程中，先给出一个原始模式，使网络处于某种初始状态下，用网络方程动态运行，最后达到一个稳定状态。如果此稳定状态对应于网络已存储的某个模式，则称模式是由模式联想起来的。,例 对于一个4神经元的网络，取阈值为0。给定两个模式存贮于网络之中 m1： V(1)v1,v2,v3,v41,1,1,1 m2： V(2)v1,v2,v3,v4-1,-1,-1,-1 计算可得权矩阵：,给出用于联想的原始模式： mA ： V(A)1,1,-1,1 运行网络得到稳定状态V(1)1,1,1,1，这个稳定状态正好是网络已记忆的模式m1 由此可以认为A是由模式mA联想起来的。 如联想模式为： mB ： V(B)-1,-1,-1,1 则得到另一稳定状态:V(2)-1,-1,-1,-1，即模式m2,例 设计DHNN，并考察其联想性能。 说明所设计的网络没有准确的记忆所有期望的模式。 因此，Hopfield网络用于联想记忆受其记忆容量和样本差异制约。当记忆的模式较少且模式之间的差异较大，则联想结果正确；而当需记忆的模式较多就容易引起混淆，网络到达的稳定状态往往不是已记忆的模式。此外当需记忆的模式之间较为相近时网络就不能辨别出正确的模式，甚至连自身都会联想错，即使用已记忆的模式作为联想模式(自联想)，也可能出错。,记忆容量分析,当网络只记忆一个稳定的模式时，该模式肯定被网络准确无误的记忆住。但当所要记忆的模式增加时，情况则发生了变化，主要表现在下列两点上： 1、权值移动 2、交叉干扰,权值移动,在网络的学习过程中，网络对权值的记忆实际上是逐个实现的。即对权值W，有程序: 当网络准确的记忆X1时，为了记忆X2,需要在记忆样本X1的权值上加上对样本X2的记忆项X2 X2T-I，将权值在原来值的基础上产生了移动。这样网络有可能部分地遗忘了以前已记忆的模式。,从动力学的角度来看，k值较小时，网络Hebb学习规则可以使输入学习样本成为其吸引子。随着k值的增加，不但难以使后来的样本成为网络的吸引子，而且有可能使以记忆住的吸引子的吸引域变小，使原来处于吸引子位置上的样本从吸引子的位置移动。对一记忆的样本发生遗忘，这种现象称为“疲劳”。,交叉干扰,网络在学习多个样本后，在回忆阶段，即验证该记忆样本时所产生的干扰，称为交叉干扰。 对外积型设计而言，如果输入样本是彼此正交的，n个神经元的网络其记忆容量的上界为n。但是在大多数情况下，学习样本不可能是正交的，因而网络的记忆容量要比n小得多，一般为(0.130.15)n。,权值修正的其它方法,1、学习规则 2、伪逆法 3、正交化权值设计,学习规则,学习规则基本公式是： 即通过计算该神经元节点的实际激励值A(t)，与期望状态T(t)进行比较，若不满足要求，将两者的误差的一部分作为调整量，若满足要求，则相应的权值保持不变。,伪逆法,用伪逆法求出的权W可以保证在自己输入时仍能收敛到样本自己。如果N与输入X完全相同，则W也可以是对称的，因而满足稳定工作的条件。其实只要满足Y矩阵中每一个元与WX矩阵中的每个元有相同的符号就可以满足收敛到本身。,正交化权值设计,这一方法是由Li和Mechel提出来的，其出发点为： (1)要保证系统在异步工作时的稳定性，则它的权是对称的 (2 )要保证所有的要求的记忆样本都能收敛到自己，不会出现错误的其他收敛值 (3)要求伪稳定点的数目尽可能地少。 (4)要求稳定点吸引域尽可能地大。 其状态转换公式为,其连接矩阵可以构造如下：,L表示模式向量为L对。,BAM是一个双层回归联想存贮器，是Hopfield网络的扩展， 也是内容编址存贮器，但各单元可以有自反馈。,双向联想存贮器（BAM）,为了构造Y层到X层的权值矩阵，将W取成WT即可。,BAM是双向的，输入和输出取决于转播方向。,BAM数学上处理如下：,netY 是Y 层总输入，各单元的输入：,在X层：,netX 是X 层总输入，各单元的输入：,举例：,连续Hopfield网络,CHNN是在DHNN的基础上提出的，它的原理 和DHNN相似。由于CHNN是以模拟量作为网络的 输入输出量，各神经元采用并行方式工作，所以 它在信息处理的并行性、联想性、实时性、分布 存储、协同性等方面比DHNN更接近于生物神经 网络。 1、网络模型 2、CHNN方程的解及稳定性分析 3、关于Hopfield能量函数的几点说明 4、关于CHNN的几点结论,CHNN的网络模型,对于神经元，放大器的I/O关系可用如下的方程来描述：,CHNN的网络模型,对I/O方程变形得：,该动态方程描述了神经元i的输出和其内部状态ui之间的关系。 CHNN实质上是连续的非线性动力学系统，由一组非线性微分方程来描述。 当给定初始状态，通过求解非线性微分方程组即可求得网络状态的运动轨迹。 若系统是稳定的，则它最终可收敛到一个稳定状态。 若用模拟电路的硬件来实现该模型，则这个求解非线性微分方程的过程将由该电路自动完成，其求解速度非常快。 CHNN有如下一些特性： (1)系统在运行过程中，其能量函数将会逐渐减小到某一极小状态。 (2)系统的极小状态一般不止一个，存在有限个平衡点 (3)CHNN可以用模拟电路实现。电路中的放大器和电阻电容等器件的电气特性在物理上对生物神经网络的某些特征有较好的模拟。,CHNN方程的解及稳定性分析,对于CHNN来说，关心的同样是稳定性问题。在所有影响电路系统稳定的参数中，一个比较特殊的参数值是放大器的放大倍数。当放大器的放大倍数足够大时，网络由连续性转化成离散型，状态与输出之间的关系表现了建立函数的形状，而正是激励函数代表了一个网络的特点，所以着重分析不同激励函数关系对系统的稳定性的影响。,当激励函数为线性函数时,对于非线性系统进行稳定性分析，方法之一就是在系统的平衡点附近对系统进行线性化处理。也可以基于网络的能量函数。下面介绍Hopfield能量函数法。,此定理表明，随着时间的演化，网络的状态总是朝能量减少的方向运动，网络的平衡点就是E的极小点。,关于Hopfield能量函数的 几点说明,当对反馈网络应用能量函数后，从任一初始状态开始，因为在每次迭代后都能满足E0，所以网络的能量将会越来越小，最后趋于稳定点E=0。 Hopfield能量函数的物理意义是：在那些渐进稳定点的吸引域内，离吸引点越远的状态，所具有的能量越大，由于能量函数的单调下降特性，保证状态的运动方向能从远离吸引点处，不断地趋于吸引点，直到达到稳定点。,几点说明： 1 能量函数为反馈网络的重要概念。根据能量函数可以方便的判断系统的稳定性； 2 Hopfield选择的能量函数，只是保证系统稳定和渐进稳定的充分条件，而不是必要条件，其能量函数也不是唯一的。,关于CHNN的几点结论,1）具有良好的收敛性； 2）具有有限个平衡点； 3）如果平衡点是稳定的，那么它也一定是渐进稳定的； 4）渐进稳定平衡点为其能量函数的局部极小点； 5）能将任意一组希望存储的正交化矢量综合为网络的渐进平衡点； 6）网络的存储信息表现为神经元之间互连的分布式动态存储； 7）网络以大规模、非线性、连续时间并行方式处理信息，其计算时间就是网络趋于平衡点的时间。,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，其余为0，列的大小表示对某城市访问的次序。同样每一行也只有一个元素为1，其余为0。通过这样的PM，可唯一地确定一条旅行路线。 对于n个城市的TSP，存在n!个输出状态。然而一个旅行只是描述一条访问城市的路线。对于访问n个城市，这是一个n个城市沿闭合路径排列的问题，它共有n!/n=(n-1)!种方案。如果将沿同一闭合路径但方向相反的两个方案合算为一种方案，n个城市的TSP共有n!2n条城市旅行路线。显然，TSP的计算时间随城市数目n呈指数增长。,约束条件和最优条件,矩阵的每个元素对应于神经网络中的每个神经元，则这个问题可用n2=52=25个神经元组成的Hopfield网络来求解。 问题的约束条件和最优条件如下： （1) 一个城市只能被访问一次=换位矩阵每行只有一个“1”。 （2）一次只能访问一个城市=换拉矩阵每列只有一个“1”。 （3）总共有n个城市=换位矩阵元素之和为n。 (4）求巡回路径最短=网络能量函数的最小值对应于TSP的最短路径。,用vij表示换位矩阵第i行、第j列的元素，显然只能取1或0。同时vij也是网络神经元的状态。 结论: 构成最短路径的换位矩阵一定是形成网络能量函数极小点的网络状态。,对于用HNN来求解TSP问题，就是要恰当地构造一个能量函数，使得HNN网络中的n个神经元能够求得问题的解，并使其能量处于最低状态。为此，构造能量函数需考虑以下两个问题； (1)能量函数要具有适合于PM的稳定状态(约束条件)。 (2)能量函数要有利于表达在TSP所有合法旅行路线中最短路线的解(目标函数)。,网络能量函数的构成,第（,4,）项为优化目标