第07讲 反馈网络反馈网络(Recurrent Network),又称自联想记忆网络,其目的是为了设计一个网络,储存一组平衡点,使得当给网络一组初始值时,网络通过自行运行而最终收敛到这个设计的平衡点上。
1982年,美国加州工学院物理学家霍普菲尔德(J.Hopfield)发表了一篇对人工神经网络研究颇有影响的论文。他提出了一种具有相互联接的反馈型人工神经网络模型,并将“能量函数”的概念引入到对称霍普菲尔德网络的研究中,给出了网络的稳定性判据,并用来进行约束优化问题,如TSP问题的求解,实现A/D转换等。他利用多元霍普菲尔德网络的多吸引子及其吸引域,实现了信息的联想记忆(associative memory)功能。另外霍普菲尔德网络与电子模拟线路之间存在着明显的对应关系,使得该网络易于理解且便于实现。而它所执行的运算在本质上不同于布尔代数运算,对新一代电子神经计算机具有很大的吸引力。
反馈网络能够表现出非线性动力学系统的动态特性。它所具有的主要特性为以下两点:第一、网络系统具有若干个稳定状态。当网络从某一初始状态开始运动,网络系统总可以收敛到某一个稳定的平衡状态;第二,系统稳定的平衡状态可以通过设计网络的权值而被存储到网络中。
如果将反馈网络稳定的平衡状态作为一种记忆,那么当网络由任一初始状态向稳态的转化过程,实质上是一种寻找记忆的过程。网络所具有的稳定平衡点是实现联想记忆的基础。所以对反馈网络的设计和应用必须建立在对其系统所具有的动力学特性理解的基础上,这其中包括网络的稳定性,稳定的平衡状态,以及判定其稳定的能量函数等基本概念。
针对人工神经网络的特点,若按其运行过程的信息流向来分类,则可分为两大类:前向网络和反馈网络。在前面的章节里,主要介绍了前向网络,通过许多具有简单处理能力的神经元的相互组合作用使整个网络具有复杂的非线性逼近能力。在那里,着重分析的是网络的学习规则和训练过程,并研究如何提高网络整体非线性处理能力。在本章中,我们将集中讨论反馈网络,通过网络神经元状态的变迁而最终稳定于平衡状态,得到联想存储或优化计算的结果。在这里,着重关心的是网络的稳定性问题,研究的重点是怎样得到和利用稳定的反馈网络。
反馈式网络有多种,这里主要讨论由霍普菲尔德提出的反馈网络。霍普菲尔德网络是单层对称全反馈网络,根据其激活函数的选取不同,可分为离散型的霍普菲尔德网络(Discrete Hopfield Neural Network,简称DHNN)和连续型的霍普菲尔德网络(Continuous Hopfield Neural Network,简称CHNN)。DHNN的激活函数为二值型的,其输入、输出为{0,1}的反馈网络,主要用于联想记忆。CHNN的激活函数的输入与输出之间的关系为连续可微的单调上升函数,主要用于优化计算。
霍普菲尔德网络已经成功地应用于多种场合,现在仍常有新的应用的报道。具体的应用方向主要集中在以下方面:图像处理、语声处理、信号处理、数据查询、容错计算、模式分类、模式识别等。
7.1 霍普菲尔德网络模型反馈网络的网络结构如图7.1所示。
图7.1 反馈网络结构图该网络为单层全反馈网络,其中的每个神经元的输出都是与其他神经元的输入相连的。所以其输入数目与输出层神经元的数目是相等的,有r=s。
在反馈网络中,如果其激活函数f(·)是一个二值型的硬函数,如图7.2所示,即ai=sgn(ni),i=l,2,… r,则称此网络为离散型反馈网络,如果ai=f(ni)中的f(·)为一个连续单调上升的有界函数,这类网络被称为连续型反馈网络,图7.3中所示为一个具有饱和线性激活函数,它满足连续单调上升的有界函数的条件,常作为连续型的激活函数。
图7.2 DHNN中的激活函数 图7.3 CHNN中的激活函数
7.2 状态轨迹对于一个由r个神经元组成的反馈网络,若将加权输入和n视作网络的状态,则状态矢量N=[n1,n2,…,nr],网络的输出矢量为A=[a1,a2…,as]T。在某一时刻t,分别用N(t)和A(t)来表示各自的矢量。在下一时刻t+1,可得到N(t+1),而N(t+1)又引起A(t+1)的变化,这种反馈演化的过程,使状态矢量N(t)随时间发生变化。在一个r维状态空间上,可以用一条轨迹来描述状态变化情况。从初始值N(t0)出发,N(t0+Δt)→N(t0+2Δt)→…→N(t0+mΔt),这些在空间上的点组成的确定轨迹,是演化过程中所有可能状态的集合,我们称这个状态空间为相空间。图7.4描述了一个三维相空间上三条不同的轨迹,对于DHNN,因为N(t)中每个值只可能为±1,或{0,1},对于确定的权值wij,其轨迹是跳跃的阶梯式,如图中A所示,对于CHNN,因为f(·)是连续的,因而,其轨迹也是连续的。如图中B、C所示。
图7.4 三维空间中的状态轨迹对于不同的连接权值wij和输入Pj(i,j=1,2,… r),反馈网络状态轨迹可能出现以下几种情况。
7.2.1 状态轨迹为稳定点状态轨迹从系统在t0时状态的初值N(t0)开始,经过一定的时间t(t>0)后,到达N(t0+t)。如果N(t0+t+Δt)=N(t0+t),Δt>0,则状态N(t0+t)称为网络的稳定点,或平衡点。由于N(t0+t)不再变化,对于P(t0+t)也达到了稳定值。即反馈网络从任一初始态P(0)开始运动,若存在某一有限时刻t,从t以后的网络状态不再发生变化:P(t+Δt)= P(t),Δt>0,则称该网络是稳定的。处于稳定时的网络状态叫做稳定状态,又称为定吸引子。
对于非线性系统来说,不同的初始值N(t0),可能有不同的轨迹,到达不同的稳定点,这些稳定点,也可以认为是人工神经网络的解。在一个反馈网络中,存在很多稳定点,根据不同情况,这些稳定点可以分为:
1)渐近稳定点:如果在稳定点Ne周围的N(σ)区域内,从任一个初始状态N(t0)出发的每个运动,当t→∞时都收敛于Ne,则称Ne为渐近稳定点。此时,不仅存在一个稳定点Ne,而且存在一个稳定域。有时称此稳定点为吸引子,其对应的稳定域为吸引域;
2)不稳定平衡点Nen:在某些特定的轨迹演化过程中,网络能够到达稳定点Nen,但对于其它方向上的任意一个小的区域N(σ),不管N(σ)取多么小,其轨迹在时间t以后总是偏离Nen;
3)网络的解:如果网络最后稳定到设计人员期望的稳定点,且该稳定点又是渐近稳定点,那么这个点称为网络的解;
4)网络的伪稳定点:网络最终稳定到一个渐近稳定点上,但这个稳定点不是网络设计所要求的解,这个稳定点为伪稳定点。
在一个非线性的反馈网络中,存在着这些不同类型的稳定点,而网络设计的目的是希望网络最终收敛到所要求的稳定点上,并且还要有一定的稳定域。
7.2.2 状态轨迹为极限环如果在某些参数的情况下,状态N(t)的轨迹是一个圆,或一个环,状态N(t)沿着环重复旋转,永不停止,此时的输出A(t)也出现周期变化,即出现振荡,如图7.4中C的轨迹即是极限环出现的情形。对于DHNN,轨迹变化可能在两种状态下来回跳动,其极限环为2。如果在r种状态下循环变化,称其极限环为r。
7.2.3 混沌现象如果状态N(t)的轨迹在某个确定的范围内运动,但既不重复,又不能停下来,状态变化为无穷多个,而轨迹也不能发散到无穷远,这种现象称为混沌(chaos)。在出现混沌的情况下,系统输出变化为无穷多个,并且随时间推移不能趋向稳定,但又不发散。这种现象越来越引起人们的重视,因为在脑电波的测试中已发现这种现象,而在真正的神经网络中存在这种现象,也应在人工神经网络中加以考虑。
7.2.4 状态轨迹发散如果状态N(t)的轨迹随时间一直延伸到无穷远,此时状态发散,系统的输出也发散。在人工神经网络中,由于输入、输出激活函数上一个有界函数,虽然状态N(t)是发散的,但其输出A(t)还是稳定的,而A(t)的稳定反过来又限制了状态的发散。一般非线性人工神经网络中发散现象是不会发生的,除非神经元的输入输出激活函数是线性的。
对于一个由r个神经元组成的反馈系统,它的行为就是由这些状态轨迹的情况来决定的。目前的人工神经网络是利用第一种情况即稳定的专门轨迹来解决某些问题的。如果把系统的稳定点视做一个记忆的话,那么从初始状态朝这个稳定点移动的过程就是寻找该记忆的过程。状态的初始值可以认为是给定的有关该记忆的部分信息,状态N(t)移动的过程,是从部分信息去寻找全部信息,这就是联想记忆的过程。如果把系统的稳定点考虑为一个能量函数的极小点,在状态空间中,从初始状态N(t0)=N(t0+t),最后到达N*。若N*为稳定点,则可以看作是N*把N(t0)吸引了过去,在N(t0)时能量比较大,而吸引到N*时能量已为极小了。根据这个道理,可以把这个能量的极小点作为一个优化目标函数的极小点,把状态变化的过程看成是优化某一个目标函数的过程。因此反馈网络的状态移动的过程实际上是一种计算联想记忆或优化的过程。它的解并不需要真的去计算,只需要去形成一类反馈神经网络,适当地讨论其权重值wij,使其初始输入A(t0)向稳定吸引子状态的移动就可以达到这个目的。
霍普菲尔德网络是利用稳定吸引子来对信息进行储存的,利用从初始状态到稳定吸引子的运行过程来实现对信息的联想存取的。通过对神经元之间的权和阈值的设计,要求单层的反馈网络达到下列目标:
(1)网络系统能够达到稳定收敛即研究系统在什么条件下不会出现振荡和混钝现象。
(2)网络的稳定点一个非线性网络能够有很多个稳定点,对权值的设计,要求其中的某些稳定点是所要求的解。对于用做联想记忆的反馈型网络,希望稳定点就是一个记忆,那么记忆容量就与稳定点的数量有关,希望记忆的量越大,那么,稳定点的数目也越大,但稳定点数目的增加可能会引起吸引域的减小,从而使联想功能减弱。对于用做优化的反馈网络,由于目标函数(即系统中的能量函数)往往要求只有一个全局最小。那么稳定点越多,陷入局部最小的可能性就越大,因而要求系统的稳定点越少越好。
(3)吸引域的设计希望的稳定点有尽可能大的吸引域,而非希望的稳定点的吸引域要尽可能的小。因为状态空间是一个多维空间,状态随时间的变化轨迹可能是多种形状,吸引域就很难用一个明确的解析式来表达,这在设计时要尽可能考虑。
7.3 离散型霍普菲尔德网络
7.3.1 DHNN模型结构在DHNN模型中,每个神经元节点的输出可以有两值状态,-1或1(0或1),其输出类似于MP神经元,可表示为:
在上式中,取b=0,权矩阵中有wij=wji,且取wii=0。即DHNN采用对称联接。因此,其网络结构可以用一个加权元向量图表示。图7.5(a)为一个3节点DHNN结构,其中,每个输入神经元节点除了不与具有相同节点号的输出相连外,与其他节点两两相连。每个输出信号又反馈到相同的输入节点。
由图7.5(a),考虑到DHNN的权值特性wij=wji,网络各节点加权输入和分别为:
由此可得简化后等效的网络结构如图7.5(b)所示。
图7.5 霍普菲尔德网络图对于以符号函数为激活函数的网络,网络的方程可写为:
7.3.2 联想记忆联想记忆功能是DHNN的一个重要应用范围。要想实现联想记忆,反馈网络必须具有两个基本条件:①网络能收敛到稳定的平衡状态,并以其作为样本的记忆信息;②具有回忆能力,能够从某一残缺的信息回忆起所属的完整的记忆信息。
DHNN实现联想记忆的过程分为两个阶段:学习记忆阶段和联想回忆阶段。在学习记忆阶段中,设计者通过某一设计方法确定一组合适的权值,使网络记忆期望的稳定平衡点。而联想回忆阶段则是网络的工作过程。此时,当给定网络某一输入模式,网络能够通过自身的动力学状态演化过程最终达到稳定的平衡点,从而实现自联想或异联想回忆。
反馈网络有两种基本的工作方式:串行异步和并行同步方式。
1)串行异步方式:任意时刻随机地或确定性地选择网络中的一个神经元进行状态更新,而其余神经元的状态保持不变;
2)并行同步方式:任意时刻网络中部分神经元(比如同一层的神经元)的状态同时更新。如果任意时刻网络中全部神经元同时进行状态更新,那么称之为全并行同步方式。
对于s个神经元的反馈网络DHNN有2s个状态的可能性。其输出状态是一个包含-1或1(0或1)的矢量,每一时刻网络将处于某一种状态下。当网络状态的更新变化采用随机异步策略,即随机地选择下一个要更新的神经元,且允许所有神经元具有相同的平均变化概率。在状态更新过程中,包括三种情况:由-1变为1;由1变为-1及状态保持不变。在任一时刻,网络中只有一个神经元被选择进行状态更新或保持,所以异步状态更新的网络从某一初态开始需经过多次更新状态后才可以达到某种稳态。这种更新方式的特点是:实现上容易,每个神经元有自己的状态更新时刻,不需要同步机制;另外,功能上的串行状态更新可以限制网络的输出状态,避免不同稳态等概率的出现;再者,异步状态更新更接近实际的生物神经系统的表现。
7.3.3 DHNN的海布(Hebb)学习规则在DHNN的网络训练过程中,运用的是海布调节规则:当神经元输入与输出节点的状态相同(即同时兴奋或抑制)时,从第j个到第i个神经元之间的连接强度则增强,否则则减弱。海布法则是一种无指导的死记式学习算法。
离散型霍普菲尔德网络的学习目的,是对具有q个不同的输入样本组Pr×q=[P1,P2 …Pq],希望通过调节计算有限的权值矩阵W,使得当每一组输入样本Pk,k=1,2,…,q,作为系统的初始值,经过网络的工作运行后,系统能够收敛到各自输入样本矢量本身。当k=1时,对于第i个神经元,由海布学习规则可得网络权值对输入矢量的学习关系式为:
(7.2)
其中,α>0,i=1,2…,r;j=1,2…,r。在实际学习规则的运用中,一般取α=1或1/r。(7.2)式表明了海布调节规则:神经元输入P与输出A的状态相同(即同时为正或为负)时,从第j个到第i个神经元之间的连接强度wij则增强(即为正),否则wij减弱(为负)。
那么由(7.2)式求出的权值wij是否能够保证ai=pj? 取α=l,我们来验证一下,对于第i个输出节点,有:
因为pi和ai值均取二值{—l,1},所以当其为正值时,即为1;其值为负值时,即为-1。同符号值相乘时,输出必为1。而且由sgn(pi1)可以看出,不一定需要sgn(pi1)的值,只要符号函数sgn(·)中的变量符号与pi1的符号相同,即能保证sgn(·)=pi1。这个符号相同的范围就是一个稳定域。
当k=1时,海布规则能够保证ai1=pi1成立,使网络收敛到自己。现在的问题是:对于同一权矢量W,网络不仅要能够使一组输入状态收敛到其稳态值,而且是要能够同时记忆住多个稳态值,即同一个网络权矢量必须能够记忆住多组输入样本,使其同时收敛到不同对应的稳态值。所以,根据海布规则的权值设计方法,当k由1增加到2,直至q时,则是在原有己设计出的权值的基础上,增加一个新量pjkpik,k=2…,q,所以对网络所有输入样本记忆权值的设计公式为:
(7.3)
式中矢量T为记忆样本,T=P。上式称为推广的学习调节规则。当系数α=1时,称(7.3)式为T的外积和公式。
DHNN的设计目的是使任意输入矢量经过网络循环最终收敛到网络所记忆的某个样本上。
因为霍普菲尔德网络有wij=wji,所以完整的霍普菲尔德网络权值设计公式应当为:
(7.4)
用向量形式表示为:
(7.5)
当α=1时有
(7.6)
其中,I为单位对角矩阵。
由(7.5)和(7.6)式所形成的网络权值矩阵为零对角阵。
采用海布学习规则来设计记忆权值,是因为设计简单,并可以满足wij=wji的对称条件。从而可以保证网络在异步工作时收敛。在同步工作时,网络或收敛或出现极限环为2。在设计网络权值时,与前向网络不同的是令初始权值wij=0,每当一个样本出现时,都在原权值上加上一个修正量,即wij=wij+tjktik,对于第k个样本,当第i个神经元输出与第j个神经元输入同时兴奋或同时抑制时,tjktik>o;当tjktik中一个兴奋一个抑制时,tjktik<0。这就和海布提出的生物神经细胞之间的作用规律相同。
在神经网络工具箱中有关采用海布公式求解网络权矩阵变化的函数为learnh.m和learnhd.m,后者为带有衰减学习速率的函数:
dW=1earnh(P,A,lr);
或 dW=learnhd(W,P,A,lr,dr);
对于简单的情况,lr可以选择1;对于复杂的应用,可取lr=0.1~0.5,dr=lr/3。
7.3.4 影响记忆容量的因素设计DHNN网络的目的,是希望通过所设计的权值矩阵W储存多个期望模式。从海布学习公式的推导过程中可以看出:当网络只记忆一个稳定模式时,该模式肯定被网络准确无误地记忆住,即所设计的W值一定能够满足正比于输入和输出矢量的乘积关系。但当需要记忆的模式增多时,情况则发生了变化,主要表现在下面两点上:
(1)权值移动在网络的学习过程中,网络对记忆样本输入T1,T2…,Tq的权值学习记忆实际上是逐个实现的。即对权值W,有程序:
W=0
for k=l,q
W=W+TkTkT-I
end
由此过程可知:当k=1时,有
此时,网络准确的记住了样本T1,当k=2时,为了记忆样本T2,需要在记忆了样本Tl的权值上加上对样本T2的记忆项T2T2T-I,将权值在原来值的基础上产生了移动。在此情况下,所求出的新的W为:wij= tj1ti1+ tj2ti2,对于样本T1来说,网络的输出为:
此输出有可能不再对所有的s个输出均满足加权输入和与输出符号一致的条件。网络有可能部分地遗忘了以前已记忆住的模式。
另一方面,由于在学习样本T2时,权矩阵W是在已学习了T1的基础上进行修正的。此时,因W起始值不再为零,所以由此调整得出的新的W值,对记忆样本T2来说,也未必对所有的s个输出同时满足符号函数的条件,即难以保证网络对T2的精确的记忆。
随着学习样本数k的增加,权值移动现象将进一步发生,当学习了第q个样本Tq后,权值又在前q—1个样本修正的基础上产生了移动,这也是网络在精确的学习了第一个样本后的第q-1次移动。不难想象,此时的权矩阵W对于P1来说,使每个输出继续能够同时满足符号条件的可能性有多大? 同样,对于其他模式Tk,k=2,…,q-1,也存在着同样的问题。很有可能出现的问题是:网络部分甚至全部地遗忘了先前已学习过的样本。即使对于刚刚进入网络的样本Tq,由于前q-1个样本所形成的记忆权值难以预先保证其可靠性,因而也无法保证修正后所得到的最终权值矩阵5r满足其符号条件。这也就无法保证网络能够记忆住该样本Tq。
从动力学的角度来看,k值较小时,网络的海布学习法则,可以使输入学习样本成为其吸引子。随着k值的增大,不但难以使后来的样本成为网络的吸引子,而且有可能使已记忆住的吸引子的吸引域变小,使原来处于吸引子位置上的样本从吸引子的位置发生移动。对已记忆的样本发生遗忘,这种现象成为“疲劳”。
(2)交叉干扰设网络的权矩阵已经设计完成,网络的输入矢量为P,并希望其成为网络的稳定矢量T=P,按同步更新规则,状态演变方程为:
实际上,上式就是P成为稳定矢量的条件,式中N为神经网络的加权输入和矢量。
设输入矢量P维数为r×q,取α=1/r,因为对于DHNN有Pk∈{-1,1},k=1,2,…,q,所以有pik*pjk=pjk*pjk=1。当网络某个矢量Pl,l∈[1,q],作为网络的输入矢量时,可得网络的加权输入和nil为:
(7.7)
上式右边中第一项为期望记忆的样本,而第二项则是当网络学习多个样本时,在回忆阶段即验证该记忆样本时,所产生的相互干扰,称为交叉干扰项。由sgn函数的符号性质可知,(7.7)式中第一项可使网络产生正确的输出,而第二项可能对第一项造成扰动,网络对于所学习过的某个样本能否正确的回忆,完全取决于(7.7)式中第一项与第二项的符号关系及数值大小。
7.3.5 网络的记忆容量确定从对网络的记忆容量产生影响的权值移动和交叉干扰上看,采用海布学习法则对网络记忆样本的数量是有限制的,通过上面的分析已经很清楚地得知,当交叉干扰项幅值大于正确记忆值时,将产生错误输出,那么,在什么情况下,能够保证记忆住所有样本?答案是有的。当所期望记忆的样本是两两正交时,能够准确得到一个可记忆数量的上限值。
在神经元为二值输出的情况下,即Pj∈{—1,1},当两个r维样本矢量的各个分量中,有r/2是相同的1,有r/2是相反的-1,对于任意一个数l,l∈[1,r],有Pl(Pk)T=0,l≠k;而有Pl(Pl)T=1,l=k的正交特性。下面用外积和公式所得到的权矩阵进行迭代计算,在输入样本Pk,k=1,2…,q中任取一个Pl作为初始输入,求网络的加权输入和Nl:
由上式结果可知,只要满足r>q,则有sgn(Nl)=Pl,保证Pl为网络的稳定解。
但对于一般的非正交的记忆样本,从前面的交叉干扰的分析过程中已经得知,网络不能保证收敛到所希望的记忆样本上。
DHNN用于联想记忆有两个突出的特点:即记忆是分布式的,而联想是动态的。这与人脑的联想记忆实现机理相类似。利用网络稳定的平衡点来存储记忆样本,按照反馈动力学运动规律唤起记忆,显示了DHNN联想记忆实现方法的重要价值。然而,DHNN也存在有其局限性,主要表现在以下几点:①记忆容量的有限性;②伪稳定点的联想与记忆;③当记忆样本较接近时,网络不能始终回忆出正确的记忆等。
另外网络的平衡稳定点并不可以任意设置的,也没有一个通用的方式来事先知道平衡稳定点。换句话说,并没有一个简便的方法来求网络的平衡稳定点。只有靠用一个一个样本去测试寻找。所以真正想利用好霍普菲尔德网络并不是一件容易的事情。
7.3.6DHNN权值设计的其他方法用海布规则设计出的DHNN权值能够保证其网络在异步工作时稳定收敛,尤其在记忆样本是正交的条件下,可以保证每个记忆样本收敛到自己,并有一定范围的吸引域,但对于那些不是正交的记忆样本,用此规则没计出的网络则不一定能收敛到本身。
这里介绍几种其他的权值设计方法以对此不足加以改进,它们都各有自己的特点。
(1) δ学习规则
δ学习规则基本公式为:
即通过计算每个神经元节点的实际激活值A(t),与期望状态T(t)进行比较,若不满足要求,则将二者的误差的一部分作为调整量,若满足要求,则相应的权值保持不变。
(2)伪逆法对于输入样本P=[P1 P2 … Pq],设网络输出可以写成一个与输入样本相对应的矩阵A,输入和输出之间可用一个权矩阵W来映射,即有:W*P=N,A=sgn(N),由此可得:
W=N*P* (7.9)
其中P*为P的伪逆,有P*=(PTP)-1PT,如果样本之间是线性无关的,则PTP满秩,其逆存在,则可求出(7.9)式求权矩阵W来。
用伪逆法求出的权矩阵W,可以保证对所记忆的模式,在输入时仍能够正确收敛到样本自己,在选择A值时,只要满足A矩阵中的每一个元素与W*P矩阵中的每个元素有相同的符号,甚至可以简单地选择A与P具有相同符号的值,即可满足收敛到学习样本的本身。但当记忆样本之间是线性相关的,由海布法所设计出网络存在的问题,伪逆法也解决不了,甚至无法求解,相比之下,由于存在求逆等运算,伪逆法较为繁琐,而海布法则要容易求得多。
(3)正交化的权值设计这一方法的基本思想和出发点是为了满足下面四个要求:
1)保证系统在异步工作时的稳定性,即它的权值是对称的,满足wij=wji,i,j=1,2…,s;
2)保证所有要求记忆的稳定平衡点都能收敛到自己;
3)使伪稳定点的数目尽可能的少;
4)使稳定点的吸引域尽可能的大。
正交化权值计算公式推导如下:
a) 已知有q个需要存储的稳定平衡点T1,T2,…,Tq,T∈Rs,计算s×(q-l)阶矩阵YRs×(q-l):
b)对Y进行奇异值及酋矩阵分解,如存在两个正交矩阵U和V以及一个对角值为Y的奇异值的对角矩阵A,满足:
k维空间为s维空间的子空间,它由k个独立基组织:
k=rank(A)
设{U1 U2 …Uk}为Y的正交基,而{Uk+1 Uk+2 …Us}为s维空间中的补充正交基,下面利用U矩阵来设计权值。
c)定义:
总的联接权值为:
其中τ为大于-1的参数。
d)网络的阈值定义为:
由此可见,网络的权矩阵是由两部分的权矩阵W+和W-相加而成的,每一部分权所采用的都是类似于外积和法得到的,只是用的不是原始要求记忆的样本,而是分解后正交矩阵的分量。这两部分权矩阵均满足对称条件,即有下式成立:
因而Wt中分量也满足对称条件。这就保证了系统在异步时能够收敛并且不会出现极限环。
下面我们来推导记忆样本能够收敛到自己的有效性。
①对于输入样本中的任意目标矢量Ti,i=1,2…,q,因为(Ti-Tq)是Y中的一个矢量,它属于A的秩所定义的k个基空间中的矢量,所以必存在一些系数α1,α2,…αk使
即:
对于U中任意一个Ui,有:
对于样本输入Ti,其网络输出为:
②当选择第q个样本Tq作为输入时,有:
③如果输入一个不是记忆样本的P,则网络输出为:
因为P不是已学习过的记忆样本,P-Tq不是Y中的矢量,则必然有Wr=(P-Tq)≠P-Tq,并且在设计过程中可以通过调节Wτ=W+-τW-中的参数τ的大小,来控制(P-Tq)与Tq的符号,以保证输入矢量P与记忆样本之间存在足够的大小余额,从而使sgn(WτP+Bτ)≠P,使P不能收敛到自身。
利用参数τ的调节可以改变伪稳定点的数目。在串行工作的情况下,伪稳定点数目的减少就意味着每个期望稳定点的稳定域的扩大。对于任意一个不在记忆中的样本P,总可以设计一个τ把P排除在外。
表7.1给出的是一个τ=10,学习记忆5个稳定样本的系统,采用上面的方法进行权的设计,以及在不同的τ时的稳定点数目,同时给出了正交化设计方法与外积和网络权值设计法的比较。
表7.1 不同的τ时的稳定点数目
虽然正交化设计方法的数学设计较为复杂,但与外积和法相比较,所设计出的平衡稳定点能够保证收敛到自己并且有较大的稳定域。更主要的是在MATLAB工具箱中已将此设计方法写进了函数solvehop.m中:
[W,b]=solvehop(T);
用目标矢量给出一组目标平衡点,由函数solvehop.m可以设计出对应反馈网络的权值和偏差,保证网络对给定的目标矢量的输入能收敛到稳定的平衡点。但网络可能也包括其他伪平衡点,这些不希望点的数目通过选择τ值(缺省值为10)已经做了尽可能的限制。
一旦设计好网络,可以用一个或多个输入矢量对其进行测试。这些输入将趋近目标平衡点,最终找到它们的目标矢量。下面给出用正交化方法设计权值的例子。
[例7.1]考虑一个具有两个神经元的霍普菲尔德网络,每个神经元具有两个权值和一个偏差。
图7.7 正交化方法设计的霍普菲尔德网络结构图网络所要存储的目标平衡点为一个列矢量T:
T=[1 -1;
-1 1];
T将被用在设计函数solvehop.m中以求出网络的权值[W,b]=solvehop(T);
solvehop.m函数返回网络的权值与偏差为:
W=[0.6925 -0.4694;
-0.4694 0.6925]
b=1.0e-16*[0.6900; 0.6900]
可以看出其权值是对称的。
下面用目标矢量作为网络输入来测试其是否已被存储到网络中了。取输入为:
Ptest=[1 -1; -1 1]; %输入矢量用来进行测试的函数为simuhop.m;
A=simuhop(Ptest,W,B,3); %计算其网络循环结束后的输出函数右端中的第四个参数3表示网络反复循环的次数。经过3次的运行,如同所希望的那样,网络的结果为目标矢量T。
现在我们想知道所设计的网络对任意输入矢量的收敛结果。我们首先给出六组输入矢量为:
P= [0.5621 0.3577 0.8694 0.0388 -0.9309 0.0594;
-0.9059 0.3586 -0.2330 0.6619 0.8931 0.3423];
在经过25次循环运行后,得到输出为:
如同所看到的第2组及第5组的输入矢量没有能够收敛到目标平衡点上。然而,如果让其运行60次,它们则能够收敛到第2个目标矢量上。
另外,当取其他随机初始值时,在25次循环后均能够收敛到所设计的平衡点上。一般情况下,此网络对任意初始随机值,在运行60次左右均能够收敛到网络所储存的某个平衡点上。
7.4 连续型霍普菲尔德网络霍普菲尔德网络可以推广到输入和输出都取连续数值的情形。这时网络的基本结构不变,状态输出方程形式上也相同。若定义网络中第i个神经元的输入总和为ni,输出状态为ai,则网络的状态转移方程可写为:
其中神经元的激活函数f为S型的函数(或线性饱和函数):
或
图7.8 连续霍普菲尔德网络激活函数
[例7.2]TSP问题。
所谓TSP(Traveling Salesman Problem)问题,即“旅行商问题”是一个十分有名的难以求解的优化问题,其要求很简单:在n个城市的集合中,找出一条经过每个城市各一次,最终回到起点的最短路径。
如果已知城市A,B,C,D,…,之间的距离为dAB,dBC,dCD…;那么总的距离d=dAB+dBC+dCD+…,对于这种动态规化问题,要去求其min(d)的解。因为对于n个城市的全排列共有n种,而TSP并没有限定路径的方向,即为全组合,所以对于固定的城市数n的条件下,其路径总数Sn为Sn=n!/2n (n≥4),例如n=4时,Sn=3,即有三种方式,如图7.9所示。
图7,9 n=4时的TSP路径图
表7,2城市数和对应的旅行方案数由斯特林(Stirlin)公式,路径总数可写为:
若采用穷举搜索法,则需要考虑所有可能的情况,找出所有的路径,再分别对其进行比较,以找出最佳路径,因其计算复杂程度随城市数目的增加呈指数增长,可能达到无法进行的地步。从表7,2中可以看到,当城市数为16时,旅行方案数已超过6×1011种。而每增加一个城市,所增加的方案数为:
这类问题称为完全非确定性多项式问题(Nondeterministic Polynomial Complete,简称NP完全问题)。由于求解最优解的负担太重,通常比较现实的作法是求其次优解。霍普菲尔德网络正是一种合适的方法。因为它可以保证其解向能量函数的最小值方向收敛,但不能确保达到全局最小值点。
采用连续时间的霍普菲尔德网络模型来求解TSP,开辟了一条解决这一问题的新途径。其基本思想是把TSP映射到CHNN上,通过网络状态的动态演化逐步趋向稳态而自动地搜索出优化解。为了便于神经模型的实现,必须首先找到过程的一个合适的表达方法。TSP的解是若干城市的有序排列,任何一个城市在最终路径上的位置可用一个n维的0、1矢量表示,对于所有n个城市,则需要一个n×n维矩阵,例如以5个城市为例,一种可能的排列矩阵为:
其中,行矢量表示城市名,列矢量表示城市中在旅行中排的序号。该矩阵唯一地确定了一条有效的行程路径:
C→A→D→B→E
很明显,为了满足约束条件,该矩阵中每一行以及每一列中只能有一个元素为1,其余元素均为零。这个矩阵称为关联阵。若用dxy表示从城市x到城市y的距离,则上面路径的总长度为:
dxy=dCE+dAD+dDB+dBE
TSP的最优解是求长度dxy为最短的一条有效的路径。为了解决TSP,必须构造这样一个网络:在网络运行时,其能量能不断降低。在运行稳定后,网络输出能代表城市被访问的次序,即构成上述的关联矩阵。网络能量的最小值对应于最佳(或次最佳)的路径距离。所以解决问题的关键,仍然是构造合适的能量函数。
(1)目标函数f(V)
对于一个n城市的TSP,需要n×n节点的CHNN。假设每个神经元的输出记为Vxi,Vyi,行下标x和y表示不同的城市名,列下标i和j表示城市在路径中所处的次序位置,通过Vxi,Vyi取0或1,可以通过关联矩阵确定出不同种的访问路径。用dxy表示两个不同的城市之间的距离,对于选定的任一Vxi,和它相邻的另一个城市y的状态可以有Vy(i+1)和Vy(i-1)。那么,目标函数f(V)可选为:
这里所选择的f(V)表示的是对应于所经过的所有路径长度的总量,其数值为一次有效路径总长度的倍数,当路径为最佳时,f(V)达到最小值,它是输出的函数。
当Vxi=0时,则有:f(V)=0,此输出对f(V)没有贡献;当Vxi=1时,则通过与i相邻位置的城市i+1和i-1的距离,如在关联矩阵中VD3=1,那么,与i=3相邻位上的两个城市分别为VA2和VB4,此时在f(V)中可得到dAD和dDB两个相加的量,依此类推,把推销员走过的全部距离全加起来,即得f(V)。
(2)约束条件g(V)
约束条件要保证关联矩阵的每一行每一列中只有一个值为1,其他值均为零,用三项表示为:
其中:
第一项,当且仅当关联矩阵每一列包含不多于一个1元素时,此项为最小;
第二项,当且仅当关联矩阵每一行包含不多于一个1元素时,此项为最小;
第三项,当且仅当关联矩阵中元素为1的个数为n时,此项为最小。
即g(V)保证满足了所有三项要求,收敛到有效解时其值为0。
(3)总的能量函数E
选择使用高增益放大器,这样能量函数中的积分分项可以忽略不计,求解得网络的联接权值为:
式中:
外部输入偏置电流为:
求解TSP的连接神经网络模型的运动方程可表示为:
式中U0为初始值,非线性函数取近似于S型的双曲正切函数。霍普菲尔德和泰克(Tank)经过实验,认为取初始值为:S=Q=P=500,T=200,RC=1,U0=0.02时,其求解10个城市的TSP得到良好的效果。人们后来发现,用连续霍普菲尔德网络求解像TSP这样约束优化问题时,系统S、Q、P、T的取值对求解过程有很大影响。
7.5 本章小结设计Hopfield网络的目的是用来存储一些平衡点集,当给定初始状态后,该网络最终能在设计点上平衡。该网络是递归的,其输出反馈为网络的输入。在理想状态下,网络的输出恰好是原始的设计点。
Hopfield网络可以作为误差纠正或向量归类网络。从理论上说,Hopfield网络有意义,但实际上很少使用。因为即使是最好的Hopfield网络,也会有伪平衡点,从而导致错误结果。
7.6 作业:
设计一个三元的霍普菲尔德网络,使网络存储的目标平衡点为:
1982年,美国加州工学院物理学家霍普菲尔德(J.Hopfield)发表了一篇对人工神经网络研究颇有影响的论文。他提出了一种具有相互联接的反馈型人工神经网络模型,并将“能量函数”的概念引入到对称霍普菲尔德网络的研究中,给出了网络的稳定性判据,并用来进行约束优化问题,如TSP问题的求解,实现A/D转换等。他利用多元霍普菲尔德网络的多吸引子及其吸引域,实现了信息的联想记忆(associative memory)功能。另外霍普菲尔德网络与电子模拟线路之间存在着明显的对应关系,使得该网络易于理解且便于实现。而它所执行的运算在本质上不同于布尔代数运算,对新一代电子神经计算机具有很大的吸引力。
反馈网络能够表现出非线性动力学系统的动态特性。它所具有的主要特性为以下两点:第一、网络系统具有若干个稳定状态。当网络从某一初始状态开始运动,网络系统总可以收敛到某一个稳定的平衡状态;第二,系统稳定的平衡状态可以通过设计网络的权值而被存储到网络中。
如果将反馈网络稳定的平衡状态作为一种记忆,那么当网络由任一初始状态向稳态的转化过程,实质上是一种寻找记忆的过程。网络所具有的稳定平衡点是实现联想记忆的基础。所以对反馈网络的设计和应用必须建立在对其系统所具有的动力学特性理解的基础上,这其中包括网络的稳定性,稳定的平衡状态,以及判定其稳定的能量函数等基本概念。
针对人工神经网络的特点,若按其运行过程的信息流向来分类,则可分为两大类:前向网络和反馈网络。在前面的章节里,主要介绍了前向网络,通过许多具有简单处理能力的神经元的相互组合作用使整个网络具有复杂的非线性逼近能力。在那里,着重分析的是网络的学习规则和训练过程,并研究如何提高网络整体非线性处理能力。在本章中,我们将集中讨论反馈网络,通过网络神经元状态的变迁而最终稳定于平衡状态,得到联想存储或优化计算的结果。在这里,着重关心的是网络的稳定性问题,研究的重点是怎样得到和利用稳定的反馈网络。
反馈式网络有多种,这里主要讨论由霍普菲尔德提出的反馈网络。霍普菲尔德网络是单层对称全反馈网络,根据其激活函数的选取不同,可分为离散型的霍普菲尔德网络(Discrete Hopfield Neural Network,简称DHNN)和连续型的霍普菲尔德网络(Continuous Hopfield Neural Network,简称CHNN)。DHNN的激活函数为二值型的,其输入、输出为{0,1}的反馈网络,主要用于联想记忆。CHNN的激活函数的输入与输出之间的关系为连续可微的单调上升函数,主要用于优化计算。
霍普菲尔德网络已经成功地应用于多种场合,现在仍常有新的应用的报道。具体的应用方向主要集中在以下方面:图像处理、语声处理、信号处理、数据查询、容错计算、模式分类、模式识别等。
7.1 霍普菲尔德网络模型反馈网络的网络结构如图7.1所示。
图7.1 反馈网络结构图该网络为单层全反馈网络,其中的每个神经元的输出都是与其他神经元的输入相连的。所以其输入数目与输出层神经元的数目是相等的,有r=s。
在反馈网络中,如果其激活函数f(·)是一个二值型的硬函数,如图7.2所示,即ai=sgn(ni),i=l,2,… r,则称此网络为离散型反馈网络,如果ai=f(ni)中的f(·)为一个连续单调上升的有界函数,这类网络被称为连续型反馈网络,图7.3中所示为一个具有饱和线性激活函数,它满足连续单调上升的有界函数的条件,常作为连续型的激活函数。
图7.2 DHNN中的激活函数 图7.3 CHNN中的激活函数
7.2 状态轨迹对于一个由r个神经元组成的反馈网络,若将加权输入和n视作网络的状态,则状态矢量N=[n1,n2,…,nr],网络的输出矢量为A=[a1,a2…,as]T。在某一时刻t,分别用N(t)和A(t)来表示各自的矢量。在下一时刻t+1,可得到N(t+1),而N(t+1)又引起A(t+1)的变化,这种反馈演化的过程,使状态矢量N(t)随时间发生变化。在一个r维状态空间上,可以用一条轨迹来描述状态变化情况。从初始值N(t0)出发,N(t0+Δt)→N(t0+2Δt)→…→N(t0+mΔt),这些在空间上的点组成的确定轨迹,是演化过程中所有可能状态的集合,我们称这个状态空间为相空间。图7.4描述了一个三维相空间上三条不同的轨迹,对于DHNN,因为N(t)中每个值只可能为±1,或{0,1},对于确定的权值wij,其轨迹是跳跃的阶梯式,如图中A所示,对于CHNN,因为f(·)是连续的,因而,其轨迹也是连续的。如图中B、C所示。
图7.4 三维空间中的状态轨迹对于不同的连接权值wij和输入Pj(i,j=1,2,… r),反馈网络状态轨迹可能出现以下几种情况。
7.2.1 状态轨迹为稳定点状态轨迹从系统在t0时状态的初值N(t0)开始,经过一定的时间t(t>0)后,到达N(t0+t)。如果N(t0+t+Δt)=N(t0+t),Δt>0,则状态N(t0+t)称为网络的稳定点,或平衡点。由于N(t0+t)不再变化,对于P(t0+t)也达到了稳定值。即反馈网络从任一初始态P(0)开始运动,若存在某一有限时刻t,从t以后的网络状态不再发生变化:P(t+Δt)= P(t),Δt>0,则称该网络是稳定的。处于稳定时的网络状态叫做稳定状态,又称为定吸引子。
对于非线性系统来说,不同的初始值N(t0),可能有不同的轨迹,到达不同的稳定点,这些稳定点,也可以认为是人工神经网络的解。在一个反馈网络中,存在很多稳定点,根据不同情况,这些稳定点可以分为:
1)渐近稳定点:如果在稳定点Ne周围的N(σ)区域内,从任一个初始状态N(t0)出发的每个运动,当t→∞时都收敛于Ne,则称Ne为渐近稳定点。此时,不仅存在一个稳定点Ne,而且存在一个稳定域。有时称此稳定点为吸引子,其对应的稳定域为吸引域;
2)不稳定平衡点Nen:在某些特定的轨迹演化过程中,网络能够到达稳定点Nen,但对于其它方向上的任意一个小的区域N(σ),不管N(σ)取多么小,其轨迹在时间t以后总是偏离Nen;
3)网络的解:如果网络最后稳定到设计人员期望的稳定点,且该稳定点又是渐近稳定点,那么这个点称为网络的解;
4)网络的伪稳定点:网络最终稳定到一个渐近稳定点上,但这个稳定点不是网络设计所要求的解,这个稳定点为伪稳定点。
在一个非线性的反馈网络中,存在着这些不同类型的稳定点,而网络设计的目的是希望网络最终收敛到所要求的稳定点上,并且还要有一定的稳定域。
7.2.2 状态轨迹为极限环如果在某些参数的情况下,状态N(t)的轨迹是一个圆,或一个环,状态N(t)沿着环重复旋转,永不停止,此时的输出A(t)也出现周期变化,即出现振荡,如图7.4中C的轨迹即是极限环出现的情形。对于DHNN,轨迹变化可能在两种状态下来回跳动,其极限环为2。如果在r种状态下循环变化,称其极限环为r。
7.2.3 混沌现象如果状态N(t)的轨迹在某个确定的范围内运动,但既不重复,又不能停下来,状态变化为无穷多个,而轨迹也不能发散到无穷远,这种现象称为混沌(chaos)。在出现混沌的情况下,系统输出变化为无穷多个,并且随时间推移不能趋向稳定,但又不发散。这种现象越来越引起人们的重视,因为在脑电波的测试中已发现这种现象,而在真正的神经网络中存在这种现象,也应在人工神经网络中加以考虑。
7.2.4 状态轨迹发散如果状态N(t)的轨迹随时间一直延伸到无穷远,此时状态发散,系统的输出也发散。在人工神经网络中,由于输入、输出激活函数上一个有界函数,虽然状态N(t)是发散的,但其输出A(t)还是稳定的,而A(t)的稳定反过来又限制了状态的发散。一般非线性人工神经网络中发散现象是不会发生的,除非神经元的输入输出激活函数是线性的。
对于一个由r个神经元组成的反馈系统,它的行为就是由这些状态轨迹的情况来决定的。目前的人工神经网络是利用第一种情况即稳定的专门轨迹来解决某些问题的。如果把系统的稳定点视做一个记忆的话,那么从初始状态朝这个稳定点移动的过程就是寻找该记忆的过程。状态的初始值可以认为是给定的有关该记忆的部分信息,状态N(t)移动的过程,是从部分信息去寻找全部信息,这就是联想记忆的过程。如果把系统的稳定点考虑为一个能量函数的极小点,在状态空间中,从初始状态N(t0)=N(t0+t),最后到达N*。若N*为稳定点,则可以看作是N*把N(t0)吸引了过去,在N(t0)时能量比较大,而吸引到N*时能量已为极小了。根据这个道理,可以把这个能量的极小点作为一个优化目标函数的极小点,把状态变化的过程看成是优化某一个目标函数的过程。因此反馈网络的状态移动的过程实际上是一种计算联想记忆或优化的过程。它的解并不需要真的去计算,只需要去形成一类反馈神经网络,适当地讨论其权重值wij,使其初始输入A(t0)向稳定吸引子状态的移动就可以达到这个目的。
霍普菲尔德网络是利用稳定吸引子来对信息进行储存的,利用从初始状态到稳定吸引子的运行过程来实现对信息的联想存取的。通过对神经元之间的权和阈值的设计,要求单层的反馈网络达到下列目标:
(1)网络系统能够达到稳定收敛即研究系统在什么条件下不会出现振荡和混钝现象。
(2)网络的稳定点一个非线性网络能够有很多个稳定点,对权值的设计,要求其中的某些稳定点是所要求的解。对于用做联想记忆的反馈型网络,希望稳定点就是一个记忆,那么记忆容量就与稳定点的数量有关,希望记忆的量越大,那么,稳定点的数目也越大,但稳定点数目的增加可能会引起吸引域的减小,从而使联想功能减弱。对于用做优化的反馈网络,由于目标函数(即系统中的能量函数)往往要求只有一个全局最小。那么稳定点越多,陷入局部最小的可能性就越大,因而要求系统的稳定点越少越好。
(3)吸引域的设计希望的稳定点有尽可能大的吸引域,而非希望的稳定点的吸引域要尽可能的小。因为状态空间是一个多维空间,状态随时间的变化轨迹可能是多种形状,吸引域就很难用一个明确的解析式来表达,这在设计时要尽可能考虑。
7.3 离散型霍普菲尔德网络
7.3.1 DHNN模型结构在DHNN模型中,每个神经元节点的输出可以有两值状态,-1或1(0或1),其输出类似于MP神经元,可表示为:
在上式中,取b=0,权矩阵中有wij=wji,且取wii=0。即DHNN采用对称联接。因此,其网络结构可以用一个加权元向量图表示。图7.5(a)为一个3节点DHNN结构,其中,每个输入神经元节点除了不与具有相同节点号的输出相连外,与其他节点两两相连。每个输出信号又反馈到相同的输入节点。
由图7.5(a),考虑到DHNN的权值特性wij=wji,网络各节点加权输入和分别为:
由此可得简化后等效的网络结构如图7.5(b)所示。
图7.5 霍普菲尔德网络图对于以符号函数为激活函数的网络,网络的方程可写为:
7.3.2 联想记忆联想记忆功能是DHNN的一个重要应用范围。要想实现联想记忆,反馈网络必须具有两个基本条件:①网络能收敛到稳定的平衡状态,并以其作为样本的记忆信息;②具有回忆能力,能够从某一残缺的信息回忆起所属的完整的记忆信息。
DHNN实现联想记忆的过程分为两个阶段:学习记忆阶段和联想回忆阶段。在学习记忆阶段中,设计者通过某一设计方法确定一组合适的权值,使网络记忆期望的稳定平衡点。而联想回忆阶段则是网络的工作过程。此时,当给定网络某一输入模式,网络能够通过自身的动力学状态演化过程最终达到稳定的平衡点,从而实现自联想或异联想回忆。
反馈网络有两种基本的工作方式:串行异步和并行同步方式。
1)串行异步方式:任意时刻随机地或确定性地选择网络中的一个神经元进行状态更新,而其余神经元的状态保持不变;
2)并行同步方式:任意时刻网络中部分神经元(比如同一层的神经元)的状态同时更新。如果任意时刻网络中全部神经元同时进行状态更新,那么称之为全并行同步方式。
对于s个神经元的反馈网络DHNN有2s个状态的可能性。其输出状态是一个包含-1或1(0或1)的矢量,每一时刻网络将处于某一种状态下。当网络状态的更新变化采用随机异步策略,即随机地选择下一个要更新的神经元,且允许所有神经元具有相同的平均变化概率。在状态更新过程中,包括三种情况:由-1变为1;由1变为-1及状态保持不变。在任一时刻,网络中只有一个神经元被选择进行状态更新或保持,所以异步状态更新的网络从某一初态开始需经过多次更新状态后才可以达到某种稳态。这种更新方式的特点是:实现上容易,每个神经元有自己的状态更新时刻,不需要同步机制;另外,功能上的串行状态更新可以限制网络的输出状态,避免不同稳态等概率的出现;再者,异步状态更新更接近实际的生物神经系统的表现。
7.3.3 DHNN的海布(Hebb)学习规则在DHNN的网络训练过程中,运用的是海布调节规则:当神经元输入与输出节点的状态相同(即同时兴奋或抑制)时,从第j个到第i个神经元之间的连接强度则增强,否则则减弱。海布法则是一种无指导的死记式学习算法。
离散型霍普菲尔德网络的学习目的,是对具有q个不同的输入样本组Pr×q=[P1,P2 …Pq],希望通过调节计算有限的权值矩阵W,使得当每一组输入样本Pk,k=1,2,…,q,作为系统的初始值,经过网络的工作运行后,系统能够收敛到各自输入样本矢量本身。当k=1时,对于第i个神经元,由海布学习规则可得网络权值对输入矢量的学习关系式为:
(7.2)
其中,α>0,i=1,2…,r;j=1,2…,r。在实际学习规则的运用中,一般取α=1或1/r。(7.2)式表明了海布调节规则:神经元输入P与输出A的状态相同(即同时为正或为负)时,从第j个到第i个神经元之间的连接强度wij则增强(即为正),否则wij减弱(为负)。
那么由(7.2)式求出的权值wij是否能够保证ai=pj? 取α=l,我们来验证一下,对于第i个输出节点,有:
因为pi和ai值均取二值{—l,1},所以当其为正值时,即为1;其值为负值时,即为-1。同符号值相乘时,输出必为1。而且由sgn(pi1)可以看出,不一定需要sgn(pi1)的值,只要符号函数sgn(·)中的变量符号与pi1的符号相同,即能保证sgn(·)=pi1。这个符号相同的范围就是一个稳定域。
当k=1时,海布规则能够保证ai1=pi1成立,使网络收敛到自己。现在的问题是:对于同一权矢量W,网络不仅要能够使一组输入状态收敛到其稳态值,而且是要能够同时记忆住多个稳态值,即同一个网络权矢量必须能够记忆住多组输入样本,使其同时收敛到不同对应的稳态值。所以,根据海布规则的权值设计方法,当k由1增加到2,直至q时,则是在原有己设计出的权值的基础上,增加一个新量pjkpik,k=2…,q,所以对网络所有输入样本记忆权值的设计公式为:
(7.3)
式中矢量T为记忆样本,T=P。上式称为推广的学习调节规则。当系数α=1时,称(7.3)式为T的外积和公式。
DHNN的设计目的是使任意输入矢量经过网络循环最终收敛到网络所记忆的某个样本上。
因为霍普菲尔德网络有wij=wji,所以完整的霍普菲尔德网络权值设计公式应当为:
(7.4)
用向量形式表示为:
(7.5)
当α=1时有
(7.6)
其中,I为单位对角矩阵。
由(7.5)和(7.6)式所形成的网络权值矩阵为零对角阵。
采用海布学习规则来设计记忆权值,是因为设计简单,并可以满足wij=wji的对称条件。从而可以保证网络在异步工作时收敛。在同步工作时,网络或收敛或出现极限环为2。在设计网络权值时,与前向网络不同的是令初始权值wij=0,每当一个样本出现时,都在原权值上加上一个修正量,即wij=wij+tjktik,对于第k个样本,当第i个神经元输出与第j个神经元输入同时兴奋或同时抑制时,tjktik>o;当tjktik中一个兴奋一个抑制时,tjktik<0。这就和海布提出的生物神经细胞之间的作用规律相同。
在神经网络工具箱中有关采用海布公式求解网络权矩阵变化的函数为learnh.m和learnhd.m,后者为带有衰减学习速率的函数:
dW=1earnh(P,A,lr);
或 dW=learnhd(W,P,A,lr,dr);
对于简单的情况,lr可以选择1;对于复杂的应用,可取lr=0.1~0.5,dr=lr/3。
7.3.4 影响记忆容量的因素设计DHNN网络的目的,是希望通过所设计的权值矩阵W储存多个期望模式。从海布学习公式的推导过程中可以看出:当网络只记忆一个稳定模式时,该模式肯定被网络准确无误地记忆住,即所设计的W值一定能够满足正比于输入和输出矢量的乘积关系。但当需要记忆的模式增多时,情况则发生了变化,主要表现在下面两点上:
(1)权值移动在网络的学习过程中,网络对记忆样本输入T1,T2…,Tq的权值学习记忆实际上是逐个实现的。即对权值W,有程序:
W=0
for k=l,q
W=W+TkTkT-I
end
由此过程可知:当k=1时,有
此时,网络准确的记住了样本T1,当k=2时,为了记忆样本T2,需要在记忆了样本Tl的权值上加上对样本T2的记忆项T2T2T-I,将权值在原来值的基础上产生了移动。在此情况下,所求出的新的W为:wij= tj1ti1+ tj2ti2,对于样本T1来说,网络的输出为:
此输出有可能不再对所有的s个输出均满足加权输入和与输出符号一致的条件。网络有可能部分地遗忘了以前已记忆住的模式。
另一方面,由于在学习样本T2时,权矩阵W是在已学习了T1的基础上进行修正的。此时,因W起始值不再为零,所以由此调整得出的新的W值,对记忆样本T2来说,也未必对所有的s个输出同时满足符号函数的条件,即难以保证网络对T2的精确的记忆。
随着学习样本数k的增加,权值移动现象将进一步发生,当学习了第q个样本Tq后,权值又在前q—1个样本修正的基础上产生了移动,这也是网络在精确的学习了第一个样本后的第q-1次移动。不难想象,此时的权矩阵W对于P1来说,使每个输出继续能够同时满足符号条件的可能性有多大? 同样,对于其他模式Tk,k=2,…,q-1,也存在着同样的问题。很有可能出现的问题是:网络部分甚至全部地遗忘了先前已学习过的样本。即使对于刚刚进入网络的样本Tq,由于前q-1个样本所形成的记忆权值难以预先保证其可靠性,因而也无法保证修正后所得到的最终权值矩阵5r满足其符号条件。这也就无法保证网络能够记忆住该样本Tq。
从动力学的角度来看,k值较小时,网络的海布学习法则,可以使输入学习样本成为其吸引子。随着k值的增大,不但难以使后来的样本成为网络的吸引子,而且有可能使已记忆住的吸引子的吸引域变小,使原来处于吸引子位置上的样本从吸引子的位置发生移动。对已记忆的样本发生遗忘,这种现象成为“疲劳”。
(2)交叉干扰设网络的权矩阵已经设计完成,网络的输入矢量为P,并希望其成为网络的稳定矢量T=P,按同步更新规则,状态演变方程为:
实际上,上式就是P成为稳定矢量的条件,式中N为神经网络的加权输入和矢量。
设输入矢量P维数为r×q,取α=1/r,因为对于DHNN有Pk∈{-1,1},k=1,2,…,q,所以有pik*pjk=pjk*pjk=1。当网络某个矢量Pl,l∈[1,q],作为网络的输入矢量时,可得网络的加权输入和nil为:
(7.7)
上式右边中第一项为期望记忆的样本,而第二项则是当网络学习多个样本时,在回忆阶段即验证该记忆样本时,所产生的相互干扰,称为交叉干扰项。由sgn函数的符号性质可知,(7.7)式中第一项可使网络产生正确的输出,而第二项可能对第一项造成扰动,网络对于所学习过的某个样本能否正确的回忆,完全取决于(7.7)式中第一项与第二项的符号关系及数值大小。
7.3.5 网络的记忆容量确定从对网络的记忆容量产生影响的权值移动和交叉干扰上看,采用海布学习法则对网络记忆样本的数量是有限制的,通过上面的分析已经很清楚地得知,当交叉干扰项幅值大于正确记忆值时,将产生错误输出,那么,在什么情况下,能够保证记忆住所有样本?答案是有的。当所期望记忆的样本是两两正交时,能够准确得到一个可记忆数量的上限值。
在神经元为二值输出的情况下,即Pj∈{—1,1},当两个r维样本矢量的各个分量中,有r/2是相同的1,有r/2是相反的-1,对于任意一个数l,l∈[1,r],有Pl(Pk)T=0,l≠k;而有Pl(Pl)T=1,l=k的正交特性。下面用外积和公式所得到的权矩阵进行迭代计算,在输入样本Pk,k=1,2…,q中任取一个Pl作为初始输入,求网络的加权输入和Nl:
由上式结果可知,只要满足r>q,则有sgn(Nl)=Pl,保证Pl为网络的稳定解。
但对于一般的非正交的记忆样本,从前面的交叉干扰的分析过程中已经得知,网络不能保证收敛到所希望的记忆样本上。
DHNN用于联想记忆有两个突出的特点:即记忆是分布式的,而联想是动态的。这与人脑的联想记忆实现机理相类似。利用网络稳定的平衡点来存储记忆样本,按照反馈动力学运动规律唤起记忆,显示了DHNN联想记忆实现方法的重要价值。然而,DHNN也存在有其局限性,主要表现在以下几点:①记忆容量的有限性;②伪稳定点的联想与记忆;③当记忆样本较接近时,网络不能始终回忆出正确的记忆等。
另外网络的平衡稳定点并不可以任意设置的,也没有一个通用的方式来事先知道平衡稳定点。换句话说,并没有一个简便的方法来求网络的平衡稳定点。只有靠用一个一个样本去测试寻找。所以真正想利用好霍普菲尔德网络并不是一件容易的事情。
7.3.6DHNN权值设计的其他方法用海布规则设计出的DHNN权值能够保证其网络在异步工作时稳定收敛,尤其在记忆样本是正交的条件下,可以保证每个记忆样本收敛到自己,并有一定范围的吸引域,但对于那些不是正交的记忆样本,用此规则没计出的网络则不一定能收敛到本身。
这里介绍几种其他的权值设计方法以对此不足加以改进,它们都各有自己的特点。
(1) δ学习规则
δ学习规则基本公式为:
即通过计算每个神经元节点的实际激活值A(t),与期望状态T(t)进行比较,若不满足要求,则将二者的误差的一部分作为调整量,若满足要求,则相应的权值保持不变。
(2)伪逆法对于输入样本P=[P1 P2 … Pq],设网络输出可以写成一个与输入样本相对应的矩阵A,输入和输出之间可用一个权矩阵W来映射,即有:W*P=N,A=sgn(N),由此可得:
W=N*P* (7.9)
其中P*为P的伪逆,有P*=(PTP)-1PT,如果样本之间是线性无关的,则PTP满秩,其逆存在,则可求出(7.9)式求权矩阵W来。
用伪逆法求出的权矩阵W,可以保证对所记忆的模式,在输入时仍能够正确收敛到样本自己,在选择A值时,只要满足A矩阵中的每一个元素与W*P矩阵中的每个元素有相同的符号,甚至可以简单地选择A与P具有相同符号的值,即可满足收敛到学习样本的本身。但当记忆样本之间是线性相关的,由海布法所设计出网络存在的问题,伪逆法也解决不了,甚至无法求解,相比之下,由于存在求逆等运算,伪逆法较为繁琐,而海布法则要容易求得多。
(3)正交化的权值设计这一方法的基本思想和出发点是为了满足下面四个要求:
1)保证系统在异步工作时的稳定性,即它的权值是对称的,满足wij=wji,i,j=1,2…,s;
2)保证所有要求记忆的稳定平衡点都能收敛到自己;
3)使伪稳定点的数目尽可能的少;
4)使稳定点的吸引域尽可能的大。
正交化权值计算公式推导如下:
a) 已知有q个需要存储的稳定平衡点T1,T2,…,Tq,T∈Rs,计算s×(q-l)阶矩阵YRs×(q-l):
b)对Y进行奇异值及酋矩阵分解,如存在两个正交矩阵U和V以及一个对角值为Y的奇异值的对角矩阵A,满足:
k维空间为s维空间的子空间,它由k个独立基组织:
k=rank(A)
设{U1 U2 …Uk}为Y的正交基,而{Uk+1 Uk+2 …Us}为s维空间中的补充正交基,下面利用U矩阵来设计权值。
c)定义:
总的联接权值为:
其中τ为大于-1的参数。
d)网络的阈值定义为:
由此可见,网络的权矩阵是由两部分的权矩阵W+和W-相加而成的,每一部分权所采用的都是类似于外积和法得到的,只是用的不是原始要求记忆的样本,而是分解后正交矩阵的分量。这两部分权矩阵均满足对称条件,即有下式成立:
因而Wt中分量也满足对称条件。这就保证了系统在异步时能够收敛并且不会出现极限环。
下面我们来推导记忆样本能够收敛到自己的有效性。
①对于输入样本中的任意目标矢量Ti,i=1,2…,q,因为(Ti-Tq)是Y中的一个矢量,它属于A的秩所定义的k个基空间中的矢量,所以必存在一些系数α1,α2,…αk使
即:
对于U中任意一个Ui,有:
对于样本输入Ti,其网络输出为:
②当选择第q个样本Tq作为输入时,有:
③如果输入一个不是记忆样本的P,则网络输出为:
因为P不是已学习过的记忆样本,P-Tq不是Y中的矢量,则必然有Wr=(P-Tq)≠P-Tq,并且在设计过程中可以通过调节Wτ=W+-τW-中的参数τ的大小,来控制(P-Tq)与Tq的符号,以保证输入矢量P与记忆样本之间存在足够的大小余额,从而使sgn(WτP+Bτ)≠P,使P不能收敛到自身。
利用参数τ的调节可以改变伪稳定点的数目。在串行工作的情况下,伪稳定点数目的减少就意味着每个期望稳定点的稳定域的扩大。对于任意一个不在记忆中的样本P,总可以设计一个τ把P排除在外。
表7.1给出的是一个τ=10,学习记忆5个稳定样本的系统,采用上面的方法进行权的设计,以及在不同的τ时的稳定点数目,同时给出了正交化设计方法与外积和网络权值设计法的比较。
表7.1 不同的τ时的稳定点数目
虽然正交化设计方法的数学设计较为复杂,但与外积和法相比较,所设计出的平衡稳定点能够保证收敛到自己并且有较大的稳定域。更主要的是在MATLAB工具箱中已将此设计方法写进了函数solvehop.m中:
[W,b]=solvehop(T);
用目标矢量给出一组目标平衡点,由函数solvehop.m可以设计出对应反馈网络的权值和偏差,保证网络对给定的目标矢量的输入能收敛到稳定的平衡点。但网络可能也包括其他伪平衡点,这些不希望点的数目通过选择τ值(缺省值为10)已经做了尽可能的限制。
一旦设计好网络,可以用一个或多个输入矢量对其进行测试。这些输入将趋近目标平衡点,最终找到它们的目标矢量。下面给出用正交化方法设计权值的例子。
[例7.1]考虑一个具有两个神经元的霍普菲尔德网络,每个神经元具有两个权值和一个偏差。
图7.7 正交化方法设计的霍普菲尔德网络结构图网络所要存储的目标平衡点为一个列矢量T:
T=[1 -1;
-1 1];
T将被用在设计函数solvehop.m中以求出网络的权值[W,b]=solvehop(T);
solvehop.m函数返回网络的权值与偏差为:
W=[0.6925 -0.4694;
-0.4694 0.6925]
b=1.0e-16*[0.6900; 0.6900]
可以看出其权值是对称的。
下面用目标矢量作为网络输入来测试其是否已被存储到网络中了。取输入为:
Ptest=[1 -1; -1 1]; %输入矢量用来进行测试的函数为simuhop.m;
A=simuhop(Ptest,W,B,3); %计算其网络循环结束后的输出函数右端中的第四个参数3表示网络反复循环的次数。经过3次的运行,如同所希望的那样,网络的结果为目标矢量T。
现在我们想知道所设计的网络对任意输入矢量的收敛结果。我们首先给出六组输入矢量为:
P= [0.5621 0.3577 0.8694 0.0388 -0.9309 0.0594;
-0.9059 0.3586 -0.2330 0.6619 0.8931 0.3423];
在经过25次循环运行后,得到输出为:
如同所看到的第2组及第5组的输入矢量没有能够收敛到目标平衡点上。然而,如果让其运行60次,它们则能够收敛到第2个目标矢量上。
另外,当取其他随机初始值时,在25次循环后均能够收敛到所设计的平衡点上。一般情况下,此网络对任意初始随机值,在运行60次左右均能够收敛到网络所储存的某个平衡点上。
7.4 连续型霍普菲尔德网络霍普菲尔德网络可以推广到输入和输出都取连续数值的情形。这时网络的基本结构不变,状态输出方程形式上也相同。若定义网络中第i个神经元的输入总和为ni,输出状态为ai,则网络的状态转移方程可写为:
其中神经元的激活函数f为S型的函数(或线性饱和函数):
或
图7.8 连续霍普菲尔德网络激活函数
[例7.2]TSP问题。
所谓TSP(Traveling Salesman Problem)问题,即“旅行商问题”是一个十分有名的难以求解的优化问题,其要求很简单:在n个城市的集合中,找出一条经过每个城市各一次,最终回到起点的最短路径。
如果已知城市A,B,C,D,…,之间的距离为dAB,dBC,dCD…;那么总的距离d=dAB+dBC+dCD+…,对于这种动态规化问题,要去求其min(d)的解。因为对于n个城市的全排列共有n种,而TSP并没有限定路径的方向,即为全组合,所以对于固定的城市数n的条件下,其路径总数Sn为Sn=n!/2n (n≥4),例如n=4时,Sn=3,即有三种方式,如图7.9所示。
图7,9 n=4时的TSP路径图
表7,2城市数和对应的旅行方案数由斯特林(Stirlin)公式,路径总数可写为:
若采用穷举搜索法,则需要考虑所有可能的情况,找出所有的路径,再分别对其进行比较,以找出最佳路径,因其计算复杂程度随城市数目的增加呈指数增长,可能达到无法进行的地步。从表7,2中可以看到,当城市数为16时,旅行方案数已超过6×1011种。而每增加一个城市,所增加的方案数为:
这类问题称为完全非确定性多项式问题(Nondeterministic Polynomial Complete,简称NP完全问题)。由于求解最优解的负担太重,通常比较现实的作法是求其次优解。霍普菲尔德网络正是一种合适的方法。因为它可以保证其解向能量函数的最小值方向收敛,但不能确保达到全局最小值点。
采用连续时间的霍普菲尔德网络模型来求解TSP,开辟了一条解决这一问题的新途径。其基本思想是把TSP映射到CHNN上,通过网络状态的动态演化逐步趋向稳态而自动地搜索出优化解。为了便于神经模型的实现,必须首先找到过程的一个合适的表达方法。TSP的解是若干城市的有序排列,任何一个城市在最终路径上的位置可用一个n维的0、1矢量表示,对于所有n个城市,则需要一个n×n维矩阵,例如以5个城市为例,一种可能的排列矩阵为:
其中,行矢量表示城市名,列矢量表示城市中在旅行中排的序号。该矩阵唯一地确定了一条有效的行程路径:
C→A→D→B→E
很明显,为了满足约束条件,该矩阵中每一行以及每一列中只能有一个元素为1,其余元素均为零。这个矩阵称为关联阵。若用dxy表示从城市x到城市y的距离,则上面路径的总长度为:
dxy=dCE+dAD+dDB+dBE
TSP的最优解是求长度dxy为最短的一条有效的路径。为了解决TSP,必须构造这样一个网络:在网络运行时,其能量能不断降低。在运行稳定后,网络输出能代表城市被访问的次序,即构成上述的关联矩阵。网络能量的最小值对应于最佳(或次最佳)的路径距离。所以解决问题的关键,仍然是构造合适的能量函数。
(1)目标函数f(V)
对于一个n城市的TSP,需要n×n节点的CHNN。假设每个神经元的输出记为Vxi,Vyi,行下标x和y表示不同的城市名,列下标i和j表示城市在路径中所处的次序位置,通过Vxi,Vyi取0或1,可以通过关联矩阵确定出不同种的访问路径。用dxy表示两个不同的城市之间的距离,对于选定的任一Vxi,和它相邻的另一个城市y的状态可以有Vy(i+1)和Vy(i-1)。那么,目标函数f(V)可选为:
这里所选择的f(V)表示的是对应于所经过的所有路径长度的总量,其数值为一次有效路径总长度的倍数,当路径为最佳时,f(V)达到最小值,它是输出的函数。
当Vxi=0时,则有:f(V)=0,此输出对f(V)没有贡献;当Vxi=1时,则通过与i相邻位置的城市i+1和i-1的距离,如在关联矩阵中VD3=1,那么,与i=3相邻位上的两个城市分别为VA2和VB4,此时在f(V)中可得到dAD和dDB两个相加的量,依此类推,把推销员走过的全部距离全加起来,即得f(V)。
(2)约束条件g(V)
约束条件要保证关联矩阵的每一行每一列中只有一个值为1,其他值均为零,用三项表示为:
其中:
第一项,当且仅当关联矩阵每一列包含不多于一个1元素时,此项为最小;
第二项,当且仅当关联矩阵每一行包含不多于一个1元素时,此项为最小;
第三项,当且仅当关联矩阵中元素为1的个数为n时,此项为最小。
即g(V)保证满足了所有三项要求,收敛到有效解时其值为0。
(3)总的能量函数E
选择使用高增益放大器,这样能量函数中的积分分项可以忽略不计,求解得网络的联接权值为:
式中:
外部输入偏置电流为:
求解TSP的连接神经网络模型的运动方程可表示为:
式中U0为初始值,非线性函数取近似于S型的双曲正切函数。霍普菲尔德和泰克(Tank)经过实验,认为取初始值为:S=Q=P=500,T=200,RC=1,U0=0.02时,其求解10个城市的TSP得到良好的效果。人们后来发现,用连续霍普菲尔德网络求解像TSP这样约束优化问题时,系统S、Q、P、T的取值对求解过程有很大影响。
7.5 本章小结设计Hopfield网络的目的是用来存储一些平衡点集,当给定初始状态后,该网络最终能在设计点上平衡。该网络是递归的,其输出反馈为网络的输入。在理想状态下,网络的输出恰好是原始的设计点。
Hopfield网络可以作为误差纠正或向量归类网络。从理论上说,Hopfield网络有意义,但实际上很少使用。因为即使是最好的Hopfield网络,也会有伪平衡点,从而导致错误结果。
7.6 作业:
设计一个三元的霍普菲尔德网络,使网络存储的目标平衡点为: