Hopfield网络

第五章霍普菲尔德（Hopfield）神经网络1985年，J.J.Hopfield和D.W.Tank建立了相互连接型的神经网络模型，简称HNN(HopfieldNeuralNetwork)，并用它成功地探讨了旅行商问题(TSP)的求解方法。前几章介绍的神经网络模型属于前向神经网络，从学习的观点上看，它们是强有力的学习系统，结构简单，易于编程。从系统的观点看，它们属于一种静态的非线性映射，通过简单非线性处理单元的复合映射可获得复杂的非线性处理能力，但它们因缺乏反馈，所以并不是一个强有力的动力学系统。Hopfield模型属于反馈型神经网络，从计算的角度上讲，它具有很强的计算能力。这样的系统着重关心的是系统的稳定性问题。稳定性是这类具有联想记忆功能神经网络模型的核心，学习记忆的过程就是系统向稳定状态发展的过程。Hopfield网络可用于解决联想记忆和约束优化问题的求解。反馈型神经网络作为非线性动力学系统，可表现出丰富多样的动态特性，如稳定性、极限环、奇怪吸引子(混沌)等。这些特性是神经网络引起研究人员极大兴趣的原因之一。研究表明，由简单非线性神经元互连而成的反馈动力学神经网络系统具有两个重要特征：1.系统有若干个稳定状态，如果从某一个初始状态开始运动，系统总可以进入其中某一个稳定状态；2.系统的稳定状态可以通过改变各个神经元间的连接权值而得到。Hopfield神经网络设计与应用的关键是对其动力学特性的正确理解：网络的稳定性是其重要性质，而能量函数是判定网络稳定性的基本概念。网络结构形式Hopfield网络是单层对称全反馈网络，根据激励函数选取的不同，可分为离散型和连续性两种（DHNN,CHNN）。DHNN：作用函数为δ函数，主要用于联想记忆。CHNN：作用函数为S型函数，主要用于优化计算非线性系统状态演变的形式在Hopfield网络中，由于反馈的存在，其加权输入和ui，i=1~n为网络状态，网络的输出为y1~yn，则u,y的变化过程为一个非线性动力学系统。可用非线性差（微）分方程来描述。一般有如下的几种状态演变形式：（1）渐进稳定（2）极限环（3）混沌现象（4）状态轨迹发散网络结构及I/O关系对于以符号函数为激励函数的网络，网络的方程可写为：图2.8.2nitutxtxwtuiinjijiji,,2,1)1(sgn)1()1(1离散型Hopfield神经网络Hopfield网络为对称网络，wij=wji。当wii＝0时为无自反馈型，反之为全自反馈型两种工作方式（1）串行工作方式在某一时刻只有一个神经元改变状态，而其它神经元的输出不变。这一变化的神经元可以按照随机的方式或预定的顺序来选择。（2）并行工作方式在某一时刻有N个神经元改变状态，而其它的神经元的输出不变。变化的这一组神经元可以按照随机方式或某种规则来选择。当N=n时，称为全并行方式。DHNN的稳定工作点1(1)()sgn(())niiijiijXtXtwxtDHNN的状态变换•从Hopfield网络的模型定义中可以看到对于n节点的HNN有2n个可能的状态，即网络状态可以用一个包含0和1的矢量表示•每一个时刻整个网络处于一个状态，状态的变化采用随机异步更新方式，即随机地选择下一个要更新的神经元，且允许所有神经元具有相同的平均变化概率。•节点状态更新包括三种情况：由0变为1、由1变为0和状态保持不变。•按照单元异步更新工作方式，某一时刻网络中只有一个节点被选择进行状态更新，当该节点状态变化时，网络状态就以一概率转移到另一状态；当该节点状态保持时，网络状态更新的结果保持前一时刻的状态。DHNN的状态变换•通常网络从某一初始状态开始经过多次更新后才可能达到某一稳态。使用异步状态更新策略有以下优点：（1）算法实现容易，每个神经元节点有自己的状态更新时刻．不需要同步机制；（2）以串行方式更新网络的状态可以限制网络的输出状态，避免不同稳态以等概率出现。一旦给出HNN的权值和神经元的阈值，网络的状态转移序列就确定了。DHNN的状态变换例计算如图所示3节点HNN的状态转移关系。该网络的参数为：现在以初态(可任意选定)v1v2v3＝(000)为例，以异步方式运行网络，考察各个节点的状态转移情况。现在考虑每个节点v1v2v3以等概率(1／3)被选择。假定首先选择节点v1，则节点状态为：网络状态由(000)变化到(100)，转移概率为I／3假定首先选择节点v2，则节点状态为：1221133123321231235,0,331111sgn()sgn(001020(5))sgn(5)1jjjvwv2sgn(10(3)00)sgn(3)0vDHNN的状态变换3sgn(20(3)03)sgn(3)0v网络状态由(000)变化到(000)(也可以称为网络状态保持不变)，转移概率为1／3。假定首先选择节点v3，则节点状态为：网络状态由(000)变化到(000)，转移概率为1／3。从上面网络的运行看出，网络状态(000)不会转移到(010)和(001)，而以1／3的概率转移到(100)，以2／3的概率保持不变同理，可以计算出其他状态之间的转移关系如图所示。图中标出了状态保持不变的转移概率，其余未标注的均为1／3。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的能量可定义为：1()niijjiijEwvv1111()12niijjiijjinnnijijiiijijiEwvvEwvvv显然E是对所有的Ei按照某种方式求和而得到，即式中出现的1／2因子。其原因在于离散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)=0v2(1)＝sgn(3.4+4.7-(-4.3))=sgn(12.4)=1v3(1)＝sgn(2.8-(-2.5))=sgn(5.3)=1v4(1)＝sgn(-3.1-5.9-(-9.6))=sgn(0.6)=1E(1)＝-14.0v1(2)＝sgn(3.4+2.8-3.1-6.3)=sgn(-3.2)=0v2(2)＝sgn(4.7-1.2-(-4.3))=sgn(7.8)=1v3(2)＝sgn(4.7-5.9-(-2.5))=sgn(1.3)=1v4(2)＝sgn(-1.2-5.9-(-9.6))=sgn(2.5)=1E(2)＝-14.0DHNN的能量函数因此，v＝{0,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，节点激励函数必须满足下列不等式：1212233()0()0()0awbcw121311223223133()0()0()0dwwewwfwwDHNN能量极小点的设计用上面的不等式组，可以求解出6个未知量的允许取值范围。假设取w12＝0.5，则：由(a)式，0.5＜θ1＜1，取θ1＝0.7由(d)式，0.2＜w13＜1，取W13＝0.4由(b)式，-1＜θ2＜0，取θ2＝-0.2由(e)式，-0.7＜w23＜1，取w23＝0.1由(c)式，0.1＜θ3＜1，取θ3＝0.4；θ3也满足(f)式。于是，确定了一组权值和阈值：w12＝0.5，w13＝0.4，w23＝0.1θ1＝0.7，θ2＝-0.2，θ3＝0.4可以验证，利用这组参数构成的Hopfield网络对于任何起始状态，始终都将达到所期望的稳态A和稳态BDHNN能量极小点的设计DHNN能量极小点的设计按照上述方法在设计能量极小点时，网络的权值和网值可在某个允许区间内取值。因而所选择的一组参数虽然满足了能量极小点设计的要求，但同时也可能产生设计所不期望的能量极小点。比如，如果选择的权值和阈值为：w12＝-0.5，w13＝0.5，w23＝0.4；θ1＝-0.1，θ2＝-0.2，θ3＝0.4，可以验证，这组值也满足(a)一(f)不等式组，但是这组参数构成的Hopfield网络有三个能量极小点，包括期望的(010)和(111)以及(100)。DHNN能量极小点的设计DHNN的学习和联想记忆Hopfield网络可用于联想记忆。当它用于计算时，其权矩阵给定为W，目的是寻找具有最小能量E的网络稳定状态；而作为记忆的学习时稳定状态是给定的，通过网络的学习求合适的权矩阵W(对称阵)。一旦学习完成后，以计算的方式进行联想。前面设计能量极小点是根据问题的要求用手工计算得到一