《神經(jīng)網(wǎng)絡》課件第9章

9.1

Hopfield神經(jīng)網(wǎng)絡9.2反饋網(wǎng)絡與優(yōu)化計算9.3

Hopfield網(wǎng)絡的MATLAB開發(fā)9.4小結

習題

反饋型神經(jīng)網(wǎng)絡又稱為遞歸網(wǎng)絡或回歸網(wǎng)絡,它是一種反饋動力學系統(tǒng)。反饋網(wǎng)絡與前饋網(wǎng)絡是人工神經(jīng)網(wǎng)絡中兩種最基本的網(wǎng)絡模型。從控制的觀點來看,后者屬于靜態(tài)網(wǎng)絡,前者則屬于動態(tài)網(wǎng)絡。聯(lián)想特性是人工神經(jīng)網(wǎng)絡的一個重要特性,它主要包括兩個方面：聯(lián)想映射與聯(lián)想記憶。在前饋網(wǎng)絡的討論中,我們著重介紹了神經(jīng)網(wǎng)絡中誘人的聯(lián)想映射能力；在反饋網(wǎng)絡的討論中,我們將著重介紹神經(jīng)網(wǎng)絡的另一誘人特性——聯(lián)想記憶能力。人類智能的一個重要特點就是具有很強的聯(lián)想記憶能力。人不僅能識別記憶中的完整模式,而且也能根據(jù)記憶由模式的部分信息進行正確的識別,由部分信息聯(lián)想或恢復到完整的信息,這即所謂的自聯(lián)想。前饋網(wǎng)絡研究的是網(wǎng)絡的輸出與輸入之間的映射關系,通常不考慮它們之間在時間上的延遲關系,其輸出、輸入之間無反饋聯(lián)系,給網(wǎng)絡的分析帶來了許多方便,討論中心是學習算法的收斂速度。對于反饋網(wǎng)絡,由于反饋的存在,使它成為一個復雜的動力學系統(tǒng),需要考慮輸出與輸入之間的延遲關系。反饋網(wǎng)絡的模型雖然較多,但其中典型的是Hopfield神經(jīng)網(wǎng)絡。它是目前研究得較充分并得到廣泛應用的神經(jīng)網(wǎng)絡模型之一。該網(wǎng)絡的變量可以取離散值,也可以取連續(xù)值。因此,Hopfield網(wǎng)絡可分為兩類：離散型與連續(xù)型。我們關心的是網(wǎng)絡的穩(wěn)定性問題,通過無教師的學習,使網(wǎng)絡狀態(tài)經(jīng)過演變最終收斂到某一穩(wěn)定狀態(tài),從而實現(xiàn)聯(lián)想記憶或優(yōu)化計算的功能。9.1

Hopfield神經(jīng)網(wǎng)絡

Hopfield網(wǎng)絡作為一種全連接型的神經(jīng)網(wǎng)絡,曾經(jīng)為人工神經(jīng)網(wǎng)絡的發(fā)展進程開辟了新的研究途徑。它利用與階層型神經(jīng)網(wǎng)絡不同的結構特征和學習方法,模擬生物神經(jīng)網(wǎng)絡的記憶機理,獲得了令人滿意的結果。它是由美國物理學家J.JHopfield于1982年首先提出的,故稱為Hopfield網(wǎng)絡。下面對此網(wǎng)絡進行詳細介紹。9.1.1

Hopfield網(wǎng)絡的結構

Hopfield神經(jīng)網(wǎng)絡是一種單層的反饋型網(wǎng)絡。若網(wǎng)絡變量的取值為二值{-1,+1}(或{0,1}),神經(jīng)元的功能函數(shù)為線性閾值函數(shù),則這樣的網(wǎng)絡稱為離散型Hopfield神經(jīng)網(wǎng)絡,簡稱離散Hopfield網(wǎng)絡。Hopfield網(wǎng)絡的基本結構如圖9-1所示。

圖中N1,N2,…,Nn表示網(wǎng)絡的n個神經(jīng)元,各神經(jīng)元的功能函數(shù)通常均取為相同的符號函數(shù)；

x=(x1,x2,…,xn)T∈{-1,+1}n

為網(wǎng)絡的輸入(向量)；y=(y1,y2,…,yn)T∈{-1,+1}n為網(wǎng)絡的輸出(向量)；V(t)=[v1(t),v2(t),…,vn(t)]T∈{-1,+1}n為網(wǎng)絡在時刻t的狀態(tài)(向量),各狀態(tài)變量vi(t)通常是指神經(jīng)元在時刻t的輸出量,t∈{0,1,2,…}為離散的時間變量。網(wǎng)絡的動態(tài)特性可由下列一組非線性差分方程來描述：(9-1)(9-2)其中：θj為神經(jīng)元的閾值,通常取各神經(jīng)元的閾值相等,且為了分析簡便,往往均取為零(即θ1=θ2=…=θn=0)；sgn(·)為符號函數(shù),其取值為若采用二值{0,1},則式(9-2)應改寫為(9-3)下面的討論均采用二值{+1,-1},所得結論具有普遍性。對于采用二值{0,1}也是有效的，讀者若有興趣可自行類推,這里不再贅述。圖9-1

Hopfield網(wǎng)絡結構示意圖當網(wǎng)絡經(jīng)過學習,建立了連接權矩陣w=(wji)后,網(wǎng)絡就處于待工作狀態(tài)。網(wǎng)絡運行時,通過輸出、輸入間的反饋作用,實現(xiàn)網(wǎng)絡狀態(tài)的演變,直至收斂到穩(wěn)定狀態(tài)為止。若作用在網(wǎng)絡上的輸入為x,網(wǎng)絡各神經(jīng)元就處于一特定的初始狀態(tài),經(jīng)網(wǎng)絡的作用,可以得到一時刻網(wǎng)絡的狀態(tài)(即在這一時刻各神經(jīng)元的輸出)。然后通過反饋作用,可得下一時刻的輸入信號；由這個新的輸入信號經(jīng)過網(wǎng)絡的作用,可得再下一時刻網(wǎng)絡的狀態(tài),反饋至輸入端又可得新的輸入信號,依次反復演變。網(wǎng)絡的狀態(tài)通過反饋作用不斷地如此演變著。如果網(wǎng)絡是穩(wěn)定的,則隨著狀態(tài)演變不斷地進行,網(wǎng)絡狀態(tài)的變化將不斷減少,直至達到穩(wěn)定狀態(tài)。因此,網(wǎng)絡的運行方程為(9-4)若達到t時刻后,網(wǎng)絡狀態(tài)不再改變,則已收斂至穩(wěn)定點,即有：

v(t+1)=v(t)(9-5)這時由輸出端可得網(wǎng)絡的穩(wěn)定輸出：

y=v(t)(9-6)

在網(wǎng)絡的運行過程中,網(wǎng)絡狀態(tài)的演變主要有兩種工作方式。

(1)異步方式。異步方式又稱非同步或串行方式,其特點是：在每個時間節(jié)拍里只對一個神經(jīng)元i進行調整,而其余的神經(jīng)元狀態(tài)保持不變。故異步工作方式的調整算法為(9-7)每次被調整的神經(jīng)元序號i可以按隨機方式選擇,也可以按預定的序列逐個調整。

(2)同步方式。同步方式又稱并行方式,其特點是：在同一時間節(jié)拍里,網(wǎng)絡的所有神經(jīng)元同時進行調整。故同步方式的調整算法為

(9-8)

有時,也可以是一部分神經(jīng)元的狀態(tài)同時進行調整。通常,只要在同一時間節(jié)拍里進行同時調整的神經(jīng)元不止一個,均稱為同步工作方式。9.1.2

Hopfield網(wǎng)絡的穩(wěn)定性

作為一個非線性動力學系統(tǒng),Hopfield網(wǎng)絡的穩(wěn)定性是非常重要的,在任一初始狀態(tài)作用下,網(wǎng)絡可能收斂到穩(wěn)定狀態(tài),也可能收斂到極限環(huán)產(chǎn)生振蕩。若將每一記憶樣本均視為網(wǎng)絡的一個穩(wěn)定狀態(tài),且要具有足夠的穩(wěn)定域,那么從初始狀態(tài)的演變過程和收斂到穩(wěn)定狀態(tài)的過程則是尋找記憶的過程。初始狀態(tài)可認為是給定的部分信息,網(wǎng)絡的演變和收斂到穩(wěn)定狀態(tài)的過程,就是從部分信息找到全部信息實現(xiàn)聯(lián)想記憶的過程。

1.吸引子和吸引域

若網(wǎng)絡從初態(tài)出發(fā),通過反饋,狀態(tài)不斷地演變,至某一刻t到達穩(wěn)定狀態(tài),從此網(wǎng)絡狀態(tài)不隨時間變化而變化,則稱該網(wǎng)絡是穩(wěn)定的。其穩(wěn)定狀態(tài)的表達式為

v(t0+t+Δt)=v(t0+t)

Δt>0(9-9)

若取t0=0,Δt=1,則穩(wěn)定狀態(tài)表達式可變?yōu)?/p>

v(t+1)=v(t)(9-10)或各分量為(9-11)于是有：(9-12)式(9-12)表明,若v(t)為網(wǎng)絡的穩(wěn)定狀態(tài),則其各神經(jīng)元的加權輸入量與輸出量是同號的,因而其乘積大于零。故式(9-12)可作為網(wǎng)絡穩(wěn)定狀態(tài)的條件表達式。

為了簡化分析,通常取閾值θj=0,于是,穩(wěn)定狀態(tài)表達式(9-11)可用向量矩陣簡潔地表示如下：

v(t+1)=sgn(w·v(t))=v(t)(9-13)若輸入模式為網(wǎng)絡的穩(wěn)定狀態(tài),由上式則應有：

網(wǎng)絡的穩(wěn)定狀態(tài)也稱為“吸引子”

(Attractor)或“不動點”(FixedPoint)。我們希望：需要網(wǎng)絡記憶的樣本皆為網(wǎng)絡的穩(wěn)定狀態(tài)；除此之外網(wǎng)絡不應再有別的吸引子,因為這些吸引子是多余的,相應的穩(wěn)定狀態(tài)稱為偽(或虛)穩(wěn)定狀態(tài)。(9-14)為了實現(xiàn)良好的聯(lián)想記憶功能,當網(wǎng)絡輸入受了干擾或為缺損的樣本時,網(wǎng)絡應有能力自動聯(lián)想,由部分信息恢復全部信息,并吸引到樣本向量所對應的吸引子。這就是說,網(wǎng)絡的吸引子應有一定的吸引范圍或稱吸引域,且這種吸引應是強吸引的。設v為網(wǎng)絡的吸引子。所謂強吸引,是指從x開始的每條狀態(tài)演變路徑都可到達v,則稱x強吸引到v,并記作；對于吸引子v的鄰域N(v),若對于所有x∈N(v)都有,則稱N(v)為v的強吸引域。與此相對應,弱吸引是指若存在一條路徑可從x演變到v,則稱x弱吸引到v,并記作；對于吸引子v的鄰域N(v),若對所有x∈N(v)都有,則稱N(v)為v的弱吸引域。

2.漢明距離

為了說明各向量之間的差異程度,需引入某種度量的標準。通常使用信息與編碼理論中廣泛采用的漢明距離dH來作為度量的標準。兩向量v1與v2之間的漢明距離定義為：

dH(v1,v2)=v1與v2中對應元素不相同(即v1i≠v2i)的總個數(shù)

(9-15)

對于元素取二值vi∈{-1,+1},則有：

(9-16)

顯然,若v1=v2則dH(v1,v2)=0；若兩個n維向量各元素均相反,則dH(v1,v2)=n。

3.能量函數(shù)

研究動力學系統(tǒng)的穩(wěn)定性,通常使用“能量函數(shù)”的方法,這是李雅普諾夫穩(wěn)定性第二方法的一種推廣應用。這里借用鐵磁材料哈密頓函數(shù)的形式來定義離散Hopfield網(wǎng)絡的能

量函數(shù)。在鐵磁體中鐵磁分子旋轉只有兩個方向,即可認為自旋Pi∈{-1,+1},在鐵磁材料中哈密頓函數(shù)為其中：鐵磁分子自旋Pi、Pj只有兩個方向{-1,+1}；Jij為第i個鐵磁分子與第j個鐵磁分子之間的作用,Jij=Jji。整個物質相互作用的結果是使哈密頓函數(shù)H達到最小。而離散Hopfield網(wǎng)絡與此很相似，變量也是二值量,相互作用可由連接權wij表示。因此Hopfield就定義網(wǎng)絡的能量函數(shù)為(9-17)(9-18)由于vi,vj∈{-1,+1},wij與θi有界,i,j=1,2,…,n,故能

量函數(shù)E是有界的,即(9-18)如果從任意初態(tài)出發(fā),網(wǎng)絡狀態(tài)的演變都能滿足ΔE≤0,則表明隨著狀態(tài)演變過程的進行,能量函數(shù)E是單調下降的。也就是說,在吸引子的吸引域內,當狀態(tài)離吸引子較遠時,其能量是較大的；隨著狀態(tài)演變過程的進行,狀態(tài)越趨近吸引子,其能量就越小；當能量達到極小點而不再改變(即ΔE=0)時,網(wǎng)絡就處于穩(wěn)定狀態(tài)。

4.穩(wěn)定性結論

結論1

若網(wǎng)絡按異步方式工作,且滿足wij=wji，wii=0,i,j,=1,2,…,n,則從任意初態(tài)出發(fā),Hopfield網(wǎng)絡最終將收斂

到一個穩(wěn)定狀態(tài)。

證明對于離散Hopfield網(wǎng)絡的單個神經(jīng)元j,其狀態(tài)變化可能為(9-20)當網(wǎng)絡工作在異步方式時,每一節(jié)拍只有一個神經(jīng)元(設為i)狀態(tài)發(fā)生變化,而其余神經(jīng)元保持不變。于是可得：

由于網(wǎng)絡對稱,wij=wji,wii=0,故上式可改寫為(9-21)(9-22)因此有：

當neti(t)≥0時,Δvi≥0,則ΔE≤0;

當neti(t)<0時,Δvi≤0,則ΔE≤0。(9-23)

這表明,在任意初態(tài)下均能夠滿足ΔE≤0,因而保證了網(wǎng)絡的穩(wěn)定性。

同理可證得下列結論。結論2

若網(wǎng)絡按異步方式工作,且滿足

wij=wji,wii>0(i,j=1,2,…,n),則網(wǎng)絡是穩(wěn)定的。

結論3若網(wǎng)絡按同步方式工作,且滿足wij=wji，當權矩陣為非負定(w≥0)時,則網(wǎng)絡從任意初態(tài)出發(fā)的演變過程將收斂到穩(wěn)定狀態(tài)；當權矩陣不滿足非負定條件時,則將不能保證同步演變過程的收斂性,可能出現(xiàn)狀態(tài)的周期振蕩,形成權限環(huán)；若權矩陣為負定的,則網(wǎng)絡周期振蕩,出現(xiàn)權限環(huán)。下面舉例說明。圖9-2所示的由兩個神經(jīng)元構成的離散Hopfield網(wǎng)絡,其權矩陣和閾值分別為

假設初始狀態(tài)為，則網(wǎng)絡的狀態(tài)在和

之間來回振蕩。圖9-2同步工作方式的Hopfield網(wǎng)絡9.1.3基本學習規(guī)則

Hopfield網(wǎng)絡的學習采用的是無教師學習。學習的過程相應于形成網(wǎng)絡的連接權矩陣。討論的中心問題在于,如何使網(wǎng)絡對于給定的問題進行學習,建立連接權矩陣,并使網(wǎng)絡具有較強的聯(lián)想記憶能力。假設需要存貯的記憶樣本有x1,x2,…,xp,xi∈{-1,+1}n。

1.Hebb學習規(guī)則

1)對一個模式的學習

為了分析簡便,首先考慮網(wǎng)絡對一個模式的學習。這時需要存貯的記憶樣本只有1個(設為x1),它將成為網(wǎng)絡的穩(wěn)定狀態(tài),并具有最大的吸引域,或者說是具有最大的“糾錯能力”。

將記憶樣本x1輸入到網(wǎng)絡,并作為網(wǎng)絡的初始狀態(tài),經(jīng)過演變,它將成為網(wǎng)絡的穩(wěn)定狀態(tài)。設網(wǎng)絡的連接權矩陣為w,有：或(9-24)由符號函數(shù)的性質可知，式(9-24)等價于下列關系式：(9-25)欲使式(9-25)成立，則連接權應和的乘積成比例。故網(wǎng)絡對記憶樣本的學習關系式為：

其中比例系數(shù)a>0為一常數(shù)。通常取a=1或a=1/n(n為樣本向量的維數(shù))。

式(9-26)的學習關系式是Hebb于20世紀40年代末首先提出的一種神經(jīng)網(wǎng)絡的學習算法,屬于無教師學習,實際上它是一種死記式學習,收斂速度很快。

(9-26)當網(wǎng)絡只有一個輸入模式時,它不僅是網(wǎng)絡的吸引子,而且可以證明網(wǎng)絡的觀察向量為x,它與記憶樣本x1的漢明距離設為,則網(wǎng)絡的輸出為

yj=sgn(netj)

j=1,2,…,n(9-27)

其中：第j個神經(jīng)元的加權輸入為將式(9-26)代入上式可得：

式中因子n-k為與x1中相同的各元素乘積之和,即為；-k為與x1中不同的各元素乘積之和。故式(9-27)可改寫為(9-28)(9-29)為使網(wǎng)絡的輸入觀察向量能收斂到吸引子x1上,根據(jù)穩(wěn)定條件應滿足：

(9-30)

而a＞0,故由上式可導出：

(9-31)

式(9-31)表明,當Hopfield網(wǎng)絡只有一個記憶樣本時,網(wǎng)絡的最大糾錯能力可達n/2漢明距離。這就是說,輸入50%的信息,網(wǎng)絡可聯(lián)想出全部的信息。

2)對多個模式的學習

當網(wǎng)絡需要學習的記憶樣本有p個(x1,x2,…,xp)時,學習的算法仍然是Hebb規(guī)則,它是式(9-26)的推廣,則有：

于是權矩陣為：(9-32)(9-33)可見,當系數(shù)a=1時,根據(jù)Hebb規(guī)則,網(wǎng)絡的連接權矩陣可表示為各學習模式x1,x2,…,xp的外積和。

在實際應用中往往取wii=0,因為不帶自環(huán)的Hopfield網(wǎng)絡的穩(wěn)定性易于保證。對于這種不帶自環(huán)的網(wǎng)絡,式(9-32)和式（9-33)可改寫為(9-34)和

學習過程一旦結束,連接權矩陣就形成,網(wǎng)絡便可進入工作狀態(tài)。輸入觀察向量(或未知向量)x,則網(wǎng)絡進行狀態(tài)演變,直至收斂到穩(wěn)定狀態(tài)。這時網(wǎng)絡的穩(wěn)定輸出就是聯(lián)想的結果。(9-35)

2.多個記憶模式間的相互干擾

如果網(wǎng)絡只記憶一個模式,則該模式肯定是網(wǎng)絡的不動點,且具有最大的糾錯能力,可達n/2漢明距離。但當記憶的模式增多時,各個模式間的相互影響不可避免地存在,這主要表

現(xiàn)為以下幾種方式。

1)權值移動

根據(jù)Hebb學習規(guī)則,網(wǎng)絡對輸入模式x1,x2,…,xp的學習記憶是逐個實現(xiàn)的。比如,對無自環(huán)網(wǎng)絡的權矩陣,其學習記憶過程為

w←0

for

k=1,2,…,p,w←w+[axk(axk)T-I]

當k=1時,網(wǎng)絡能準確地記住模式x1；當k=2時,為了記憶模式x2,連接權值需要在原有基礎上移動。這樣,對模式x1式(9-25)可能不再對所有j∈{1,2,…,n}都成立，可能會部分遺忘以前的記憶；對模式x2,由于權矩陣w已學習了x1,其起始值不再是零,因而條件(9-25)也未必對所有的j∈{1,2,…,n}都成立,這就是說,難以保證網(wǎng)絡對x2一定能準確地記憶。余可類推。從動力學觀點來看,當k較小時,經(jīng)學習可使輸入模式成為網(wǎng)絡的吸引子；然而隨著k增大,可能不僅難以使后來的模式成為吸引子,而且將原來吸引子的吸引域變小,甚至使原處于吸引子的模式發(fā)生移動或淡忘。對于一定規(guī)模的網(wǎng)絡(即節(jié)點數(shù)n一定時),存在能學習記憶的模式數(shù)上限pmax,這時網(wǎng)絡不但無力記憶以后輸入的模式,而且對以前的記憶也將逐漸淡忘。產(chǎn)生這種網(wǎng)絡“疲勞”的原因就在于交叉干擾。

2)交叉干擾

設網(wǎng)絡的權矩陣已經(jīng)建立,若輸入向量為x,希望它成為網(wǎng)絡的吸引子,其條件為

x=sgn(wx)

(9-36)

其中網(wǎng)絡的加權輸入：(9-37)設輸入；令，

由于，于是得：(9-38)由式(9-37)可得網(wǎng)絡的加權輸入為：(9-39)分析式(9-39)可以看到：當網(wǎng)絡學習記憶多個模式時,根據(jù)符號函數(shù)的性質可知，式(9-39)右邊的第一項能使網(wǎng)絡建立與xl相應的吸引子；而其右邊的第二項是表示學習其它模式時所產(chǎn)生的對第一項的干擾,故稱為交叉干擾項。因此,網(wǎng)絡對于學習模式集合中某一模式能否正確地記憶與聯(lián)想,完全取決于式(9-39)右邊第一項與第二項的大小及其符號關系。9.1.4

Hopfield網(wǎng)絡的聯(lián)想特性

綜上分析可以看到,Hopfield網(wǎng)絡是利用穩(wěn)定狀態(tài)來對信息進行記憶的,利用從初態(tài)到穩(wěn)定狀態(tài)的演變過程來實現(xiàn)對信息的聯(lián)想。下面討論Hopfield網(wǎng)絡的主要聯(lián)想特性

1.記憶樣本與穩(wěn)定狀態(tài)方面

結論1設網(wǎng)絡各神經(jīng)元的閾值為零,若模式x為網(wǎng)絡的

穩(wěn)定狀態(tài),則-x也是網(wǎng)絡的穩(wěn)定狀態(tài)。證明若x為穩(wěn)定狀態(tài),則有：

x=sgn(wx)

(9-40)

若對換網(wǎng)絡輸入-x,則網(wǎng)絡的狀態(tài)演變?yōu)?/p>

sgn[w(-x)]=sgn(-wx)=-sgn(wx)=-x

(9-41)因此-x也為網(wǎng)絡的穩(wěn)定狀態(tài)。結論2對于無自環(huán)網(wǎng)絡,若有兩個模式x1和x2,dN(x1,x2)=1,則x1和x2不可能同時成為網(wǎng)絡的穩(wěn)定狀態(tài)。

證明

dN(x1,x2)=1,這表明x1和x2只有一個元素不同。不妨假定它們的第一個元素不同,即,而其余的元素均相同,即,i=2,3,…,n。若x1為穩(wěn)定狀態(tài),則網(wǎng)絡第一個神經(jīng)元的輸出應為

對網(wǎng)絡輸入x2,若x2也為穩(wěn)定狀態(tài),則第一個神經(jīng)元的輸出應為

(9-42)(9-43)式(9-42)和式(9-43)的右端相同。于是可導出其左端也應相等,即。這與假定條件矛盾。故x1和x2不可能同時成為網(wǎng)絡的穩(wěn)定狀態(tài)。結論3若dN(x1,x2)=n-1,則模式x1和x2也不可能同時成為網(wǎng)絡的穩(wěn)定狀態(tài)。

證明證明過程參考結論2。

對于離散Hopfield網(wǎng)絡,我們的目的是企圖使所有的記憶樣本都能成為網(wǎng)絡的穩(wěn)定狀態(tài)。除此之外,網(wǎng)絡再沒有別的穩(wěn)定狀態(tài)。但從上述討論中可以看到：①并不是任意的輸入

模式都可以同時成為網(wǎng)絡的吸引子,它們必須是互不相似且差異較大的,結論1~3是記憶樣本欲成為網(wǎng)絡吸引子必須滿足的必要條件。②在網(wǎng)絡中存在一些非記憶樣本的多余穩(wěn)定狀態(tài)

,通常稱之為偽(或虛)穩(wěn)定狀態(tài)。因此,在實際應用上應注意這種情況的存在,同時為了得到良好的聯(lián)想特性,從初態(tài)演變到穩(wěn)定狀態(tài)應當是強吸引的。

【例9-1】Hopfield網(wǎng)絡n=3,m=3,三個記憶樣本為x1=(1,1,-1)T,x2=(1,1,-1)T,x3=(1,1,-1)T。

解根據(jù)Hebb學習規(guī)則,取a=1,于是可得網(wǎng)絡的連接權矩陣為

可以驗證：

sgn(wx1)=x1,

sgn(wx2)=x2

即模式x1和x2均為網(wǎng)絡的穩(wěn)定狀態(tài)。而dH(x3,x2)=1,由結論2可知,既然x2為穩(wěn)定狀態(tài),那么,模式x3不可能成為網(wǎng)絡的穩(wěn)定狀態(tài)。當輸入模式x3時,網(wǎng)絡的輸出為網(wǎng)絡具有較好的聯(lián)想記憶能力。例如當輸入觀察向量x=(-1,1,-1)時,網(wǎng)絡的輸出為

因為?？梢?未知的觀察向量x是按漢明距離最小的意義下,收斂于網(wǎng)絡的吸引子x1；也就是說受了干擾的不完全信息,在Hopfield網(wǎng)絡的聯(lián)想作用下,使信息得到了恢復。

2.網(wǎng)絡容量方面

結論4設p個模式向量x1,x2,…,xp,當0<a<1/2時：

an≤dH(xi,xj)≤(1-a)ni≠j

(9-44)

若下列條件成立：

(9-45)

則當網(wǎng)絡的節(jié)點數(shù)n足夠大時,x1,x2,…,xp為網(wǎng)絡的穩(wěn)定狀態(tài)。證明設，于是有：

(xi)Txj=(xi與xj中相同元素之乘積和)-(xi與xj中不同元素

之乘積和)

=(n-dij)-dij=n-2dij

即

|(xi)Txj|=|n-2dij|≤n-2an=(1-2a)n(9-46)

由Hebb學習規(guī)則,取a=1,則有：

(9-47)

設輸入向量x=xl,l∈{1,2,…,p},于是：

上式右邊第二項為交叉干擾項,現(xiàn)估計其大小。考慮到式(9-47),該干擾項為n維列向量,其第i個元素的大小為

(9-48)(9-49)分析式(9-49)可以看到：如果交叉干擾項的符號與第一項相反,則當干擾項第i個元素的絕對值大于第一項對應元素的值時,由符號函數(shù)性質可知,這將造成網(wǎng)絡輸出的第i位出錯

。因此,為了使模式xl成為網(wǎng)絡的穩(wěn)定狀態(tài),其條件是式(9-49)

的第一項起主導作用,即：

(n-p)>(p-1)(1-2α)n

或(9-50)當n足夠大時,上式可化簡為

這就是說,當p滿足條件式(9-51)時,則對于p個模式向量,有：

即它們均為網(wǎng)絡的穩(wěn)定狀態(tài)。

結論4表明：模式向量一般來說不一定都能成為網(wǎng)絡的吸引子,但當滿足一定的條件時,則可同時成為網(wǎng)絡的穩(wěn)定狀態(tài)。(9-51)(9-52)結論5當α=1/2時,則結論4中的p個模式向量x1,x2,…,xp為正交向量,且它們都是網(wǎng)絡的穩(wěn)定狀態(tài)。

證明當α=1/2時,由結論1可知：

因為各模式向量是正交的,所以有：

(xi)Txj=0

i≠j

而由式(9-48)可得,當網(wǎng)絡輸入模式向量xl時,對應的交叉干擾項：

因此,對所有模式向量xl,l∈{1,2,…,p}均滿足式(9-52),

即各模式向量均為網(wǎng)絡的吸引子。

結論6當模式向量為正交向量時,網(wǎng)絡可穩(wěn)定存貯的模式數(shù)等于網(wǎng)絡的神經(jīng)元數(shù),皆為n。

證明若網(wǎng)絡的神經(jīng)元數(shù)為n,通常稱該網(wǎng)絡為n維的,相應地,網(wǎng)絡的輸入狀態(tài)和輸出也均為n維向量。對于n維向量空間,其最大正交向量子集中量的個數(shù)為n。于是由結論5令p=n,則得證。綜上述分析可以看到,網(wǎng)絡可存貯的記憶樣本數(shù)的上限,即網(wǎng)絡的容量問題,是一重要且相當復雜的研究課題。它不僅取決于網(wǎng)絡的結構和算法,而且也取決于被存貯的模式向量。因此,很難得到一般的結論,只能給出一些基本的特點。當存貯的模式為正交向量時,網(wǎng)絡容量最大,可為網(wǎng)絡的維數(shù),即pmax=n。然而,要求存貯的模式向量為正交的,很難實現(xiàn)。有關網(wǎng)絡的容量問題,有待進一步研究。9.2反饋網(wǎng)絡與優(yōu)化計算

Hopfield網(wǎng)絡是一單層的反饋型網(wǎng)絡,網(wǎng)絡的基本結構在前面已做了介紹。連續(xù)Hopfield網(wǎng)絡與以上介紹的離散Hopfield網(wǎng)絡相比較,主要的不同點有：①連續(xù)Hopfield網(wǎng)絡神經(jīng)元的功能函數(shù)采用的不是符號函數(shù),而是連續(xù)可微單調非減的S型函數(shù)；②網(wǎng)絡的輸入狀態(tài)和輸出變量的取值,不是離散的二值量,而是在一定范圍內變化的連續(xù)量。因而連續(xù)Hopfield網(wǎng)絡的狀態(tài)演變不再是異步方式或同步方式,而是連續(xù)的方式,即網(wǎng)絡的所有神經(jīng)元均連續(xù)地隨時間t并行地更新。對于網(wǎng)絡的單個神經(jīng)元(設為第i個神經(jīng)元)而言,其輸入的累加值為

(9-53)式中,vj為網(wǎng)絡的第j個神經(jīng)元的輸出；Ii為作用在第i個神經(jīng)元的外部刺激或該神經(jīng)元的閾值“-θi”。第i個神經(jīng)元的狀態(tài)ui與輸入累加值之間的關系,可用下列狀態(tài)方程表示：

上式中為該神經(jīng)元動態(tài)特性的時間常數(shù)。于是該神經(jīng)元的輸出為：

vi=f(ui)(9-54)(9-55)通常神經(jīng)元的功能函數(shù)f(·)為S型函數(shù)。由于Hopfield網(wǎng)絡是一動態(tài)網(wǎng)絡,因此網(wǎng)絡的穩(wěn)定性分析是需要關注的主要問題。

Hopfield網(wǎng)絡已經(jīng)有很多成功的應用,現(xiàn)在還在不斷地發(fā)展。這種網(wǎng)絡的應用形式主要有聯(lián)想記憶和優(yōu)化計算兩種,而其具體的應用領域有圖像、語音和信號處理、模式分類和識別、知識處理、控制、容錯計算、數(shù)據(jù)查詢等。這里介紹在優(yōu)化計算中遇到的一些基本概念和方法。9.2.1

Hopfield網(wǎng)絡的電路模型與動態(tài)方程

根據(jù)Hopfield網(wǎng)絡的結構(如圖9-1所示),利用模擬電子線路,建立反饋型人工神經(jīng)網(wǎng)絡的電路模型,如圖9-3所示。圖9-3連續(xù)Hopfield網(wǎng)絡電路模型連續(xù)Hopfield網(wǎng)絡模擬電路主要由以下部分構成：

(1)運算放大器用來模擬神經(jīng)元的非線性功能函數(shù)。通常,神經(jīng)元的功能函數(shù)采用的是連續(xù)可微單調非減的Sigmoid函數(shù)。

(2)運算放大器輸入端的電阻Ri與電容Ci的并聯(lián)電路用來模擬神經(jīng)元動態(tài)特性的時間常數(shù)。

(3)連接電導wij建立了由vj產(chǎn)生第i個運算放大器輸入電流之間的聯(lián)系,用它來模擬生物神經(jīng)元的突觸作用。在圖中反饋線與輸入線的交叉處,以小圓圈示意表示wij,也可以改用電阻Rij表示,

如圖9-4所示。圖9-4第i個神經(jīng)元的模擬電路圖

(4)外加偏置電流Ii用來模擬神經(jīng)元的閾值“-θi”或外部的刺激。

單個神經(jīng)元的模擬電路如圖9-4所示。根據(jù)電路的克希荷夫定律可列寫單個神經(jīng)元的方程如下：

經(jīng)整理后可得：(9-56)式中,

假定網(wǎng)絡共有n個神經(jīng)元,各神經(jīng)元模擬電路的參數(shù)相同,且取令，由式(9-53)則可得描述圖9-3所示的連續(xù)Hopfield網(wǎng)絡的非線性動態(tài)方程為(9-57)或寫成向量矩陣的形式式中，w為n×n的加權陣。9.2.2

Hopfield網(wǎng)絡的能量函數(shù)與穩(wěn)定性

由網(wǎng)絡的動態(tài)方程式(9-56)可以看到,給定一組初值后可求出該方程的解,若其解為一組確定值,則表明網(wǎng)絡狀態(tài)演變的最終結果將達到一個穩(wěn)定的狀態(tài)。如果能設計出w和I,使網(wǎng)絡的穩(wěn)定狀態(tài)與要求的解一致,網(wǎng)絡就可完成優(yōu)化計算之功能。網(wǎng)絡的穩(wěn)定性分析是一重要但又困難的問題,尚待進一步研究。目前應用較廣的是Hopfield提出的利用李雅普諾夫第二方法來研究網(wǎng)絡的穩(wěn)定性。他所提出的能量函數(shù)(即通常所謂的Hopfield能量函數(shù))具有明確的物理意義,是建立在能量基礎之上的。它的離散形式就是在鐵磁材料中鐵磁分子自旋的一種哈密頓能量。

1.Hopfield能量函數(shù)的定義

Hopfield為連續(xù)Hopfield網(wǎng)絡建立的能量函數(shù)為

或改寫成向量矩陣形式：

其中,(9-58)(9-59)將式(9-58)與上一節(jié)離散Hopfield網(wǎng)絡的能量函數(shù)表達式相比較可知,它們的差別只是連續(xù)Hopfield網(wǎng)絡的能量函數(shù)式(9-58)增加了一個積分項。該積分項表示運算放大器輸入ui對輸出vi曲線包圍之面積,具有能量的量綱。由于運放的放大系數(shù)通常較大,積分項的值較小,往往可忽略不計。于是式(9-59)可化簡為

可見,此能量函數(shù)為具有能量量綱的“二次型”函數(shù)。

2.網(wǎng)絡的穩(wěn)定性

通常vi∈[-1,1],能量函數(shù)E是一可正可負但有界的函數(shù)。利用李雅普諾夫穩(wěn)定性第二方法,可以證明網(wǎng)絡的穩(wěn)定性具有下列結論。

穩(wěn)定性定理對于連續(xù)Hopfield網(wǎng)絡,若網(wǎng)絡對稱wij,Ci>

0,且神經(jīng)元的功能函數(shù)f(·)為連續(xù)單調遞增函數(shù),則有：且上式等號成立的充要條件為對一切i∈{1,2,…,n},有：證明由式(9-58)可得：

而故由于Ci>0,f-1(·)為連續(xù)單調遞增函數(shù),故可得：

且可知,若,則對一切i(i=1,2,…,n),均成立,反之亦然。

該定理表明：若連續(xù)Hopfield網(wǎng)絡是對稱的,則網(wǎng)絡的狀態(tài)演變總是朝著能量減小的方向運動,而且網(wǎng)絡的穩(wěn)定平衡點就是能量函數(shù)的極小值點。

上述定理只提出了網(wǎng)絡穩(wěn)定性的充分條件但并非必要的,而且能量函數(shù)也不是唯一的。

3.Hopfield能量函數(shù)的基本性質

上已指出,Hopfield能量函數(shù)可正可負,但是有界的。它與李雅普諾夫函數(shù)的差別在于：李雅普諾夫函數(shù)為正定的,而Hopfield能量函數(shù)(簡稱E函數(shù))可以是負的,是有界的,但E(0)不一定為零。因此,Hopfield函數(shù)是一廣義的李雅普諾夫函數(shù)。只有當E函數(shù)滿足E(V)>0,E(0)=0條件時,Hopfield能量函數(shù)才是李雅普諾夫函數(shù),這時才可完全應用李雅普諾夫穩(wěn)定性定理來分析網(wǎng)絡的穩(wěn)定性。9.2.3

Hopfield網(wǎng)絡的優(yōu)化計算

應用連續(xù)Hopfield網(wǎng)絡解決優(yōu)化計算問題,其大致過程可歸納如下。

(1)首先對具體的優(yōu)化問題選擇適當?shù)谋硎痉椒?使網(wǎng)絡的輸出與優(yōu)化問題的解相對應。

(2)根據(jù)特定的優(yōu)化問題,構造網(wǎng)絡的能量函數(shù),使其最小值對應問題的最優(yōu)解。

(3)將所得能量函數(shù)與Hopfield能量函數(shù)的規(guī)范表達式(9-58)相比較,則可導出網(wǎng)絡的結構參數(shù)：神經(jīng)元之間的聯(lián)接電導wij和偏流Ii。

(4)根據(jù)網(wǎng)絡的結構參數(shù)構造Hopfield網(wǎng)絡,讓其運行,則網(wǎng)絡穩(wěn)定時的輸出就對應優(yōu)化問題的解。Hopfield網(wǎng)絡的實現(xiàn)方法可以有兩種：硬件實現(xiàn)或計算機仿真。在仿真時,由網(wǎng)絡的結構參數(shù)可確定網(wǎng)絡的數(shù)學模型式(9-56),然后在計算機上仿真,即可得到問題的滿意解答。

下面以A/D變換器和人工智能的典型問題——TSP問題為例,具體說明用人工神經(jīng)網(wǎng)絡解決優(yōu)化計算問題的基本原理和大致過程。

【例9-2】A/D變換器問題。

用神經(jīng)網(wǎng)絡實現(xiàn)A/D變換器,與傳統(tǒng)的A/D變換器電路相比較,具有結構簡單、可提高工作速度等優(yōu)點。下面以4位A/D變換器為例說明它的工作原理,圖9-5所示為Tank與Hopfield給出的神經(jīng)網(wǎng)絡A/D變換器的電路原理示意圖。圖9-5人工神經(jīng)網(wǎng)絡A/D變換器的電路原理示意圖圖中為了實現(xiàn)4位A/D變換之功能,用4個運算放大器模擬神經(jīng)元構成Hopfield網(wǎng)絡,將轉換的模擬量以及參考電源-U從右上端輸入,各反饋線與運放輸入線之交叉處以小圓圈表示相應的電導值wij,而運放的輸出即給出A/D變換后的4位數(shù)字量。首先建立網(wǎng)絡的能量函數(shù)。A/D變換可作為一優(yōu)化問題來處理,要求變換的精度最高,或要求模擬量x與變換后輸出的數(shù)字量之差最小?，F(xiàn)取最優(yōu)性條件為方差最小,即取目標函數(shù)為

式中：vi(i=0,1,2,3)為各運放輸出的數(shù)字量,vi∈{0,1}；2i表示數(shù)字量vi的二進制位數(shù)。顯然J(v)≥0。(9-60)一般來說,運算放大器的輸出vi為0~1之間變化的模擬量,為了確保電路輸出的有效性,使vi為最靠近0或1的數(shù)字量,于是取約束條件為(9-61)由約束條件可知：僅當輸出為數(shù)字量vi∈{0,1}時,g(v)=0；否則,當vi為非數(shù)字量(即vi為0與1之間的任意實數(shù))時,g(v)>0。式中系數(shù)的設置是為了保證網(wǎng)絡無自反饋,即wii=0。

由于運放的放大系數(shù)較大,故式(9-58)的積分項較小,往往可略去不計。于是將式(9-60)與式(9-61)相加,并去除與變量vi無關的量(即常數(shù)項x2/2),則可建立網(wǎng)絡的能量函數(shù)為(9-62)將上式與Hopfield能量函數(shù)的規(guī)范表達式相比較,則可求得網(wǎng)絡的結構參數(shù)為(式中負號利用運放的反相輸出來實現(xiàn))具體參數(shù)值如圖9-5中小圓圈旁所示。

【例9-3】旅行商問題(TravelingSalemanProblem,TSP)。

TSP問題是指有一商人要巡回n個城市,從某城市出發(fā),要求尋找一條最優(yōu)的路徑,使其距離最短。TSP問題是一典型的人工智能難題,其算法的復雜性屬于NP(NondeterministicPol

ynomial)難題,沒有確定的算法能夠在多項式界時間內得到問題的解。對于該問題,若采用窮舉搜索算法,隨著城市數(shù)n的增加,算法的復雜性是難以接受的。

設n個城市為C1,C2,…,Cn,一條有效的路徑可視為這n個城市的某種排列Ci1,Ci2,…,Cin,其中i1,i2,…,in為自然序列

1,2,…,n的一種排列。ik=j表示在該條路徑中的城市Ci被訪問的順序為第k個。n個城市的全排列有n!種。但TSP問題不限定路徑的起點和路徑的方向,于是排列Ci1,Ci2,…,Cin和逆序

Cin,Cin-1,…,Ci1以及其所有的循環(huán)移動所構成的排列(如Ci2

Ci3CinCi1,CinCi1,Ci3Ci4…CinCi2等)均應視為同一條路徑。因此,n個城市的TSP路徑總數(shù)為由斯特林(Stirlin)

公式,上式可改寫為

表9-1表示路徑數(shù)與城市數(shù)的關系?？梢?路徑總數(shù)隨著城市數(shù)按指數(shù)律增長。當城市數(shù)很多時,窮舉搜索算法實際上是不可行的。

(9-63)表9-1

TPS的可能路徑數(shù)

應用神經(jīng)網(wǎng)絡方法,可將TSP作為一優(yōu)化問題來處理。

(1)將TSP問題轉化為適于神經(jīng)網(wǎng)絡處理的形式。對于n個城市的TSP問題,可使用n×n個神經(jīng)元,用神經(jīng)元的狀態(tài)表示某一城市在某條路徑中被訪問的順序。神經(jīng)元xi的狀態(tài)用vxi表示,其中第一個下標表示城市名,第二個下標i∈{1,2,…,n}表示途經(jīng)的順序。vxi=1表示城市x在路徑中是第i個被訪問的；vxi=0表示城市x在路徑中是第i個位置上沒有被訪問的。這樣就可用一個n×n關聯(lián)矩陣來描述n個城市的TSP問題。一條有效路徑對應的關聯(lián)矩陣是每行有且只有一個元素為1,其余的均為0,這表明每個城市均被訪問,且只被訪問一次；在每一列中只有一個元素為1,其余均為0,這表明每次只訪問一個城市。表9-2為5個城市的一條有效路徑的關聯(lián)矩陣,由關聯(lián)矩陣可以得到,訪問城市的順序為C3C1C5C2C4C3,相應的路徑總長度d=d31+d15+d52+d24+d43。表9-2

5城市TSP問題一條有效路徑的關聯(lián)矩陣

(2)根據(jù)TSP優(yōu)化問題,構造網(wǎng)絡的能量函數(shù)。TSP問題是一最優(yōu)路徑問題,其最優(yōu)性條件為路徑最短。于是,可取目標函數(shù)(9-64)式中dxy表示x、y兩個不同城市之間的距離。若vxi=0,則表明該神經(jīng)元對J(v)無影響；若vxi=1,表示城市x在路徑中是在第i個位置上被訪問的,那么尋找與i相鄰順序的被訪問城市,并將這些城市間的距離加起來。以表9-2為例,取,于是可找到與其相鄰的城市為C3和C5,即,

相應地將城市C3和C5與城市C1的距離和

相加。因此,式(9-64)表示將商人走過的路程累加起來,但式中每個距離都計算兩次,故系數(shù)“1/2”是為消去重復計算而設置的。為了確保路徑的有效性,使網(wǎng)絡的輸出矩陣為一關聯(lián)矩陣,取優(yōu)化問題的約束條件為

式中等號右邊的第一項為列約束條件,保證每次只訪問一個城市,滿足此條件時,該項的值為零；第二項為行約束條件,保證每個城市只能訪問一次；第三項為全局約束條件,確保vxi=1的總數(shù)為n。因此,當路徑有效時,g(v)=0。(9-63)構造網(wǎng)絡的能量函數(shù)為(9-66)

(3)確定網(wǎng)絡的結構參數(shù),則網(wǎng)絡的穩(wěn)態(tài)輸出就對應TSP問題的最優(yōu)解。將式(9-66)與Hopfield能量函數(shù)的規(guī)范表達式

相比較,并考慮到系數(shù)B只影響同一列各神經(jīng)元之間的連接電導值,C只影響同一行各神經(jīng)元之間的連接電導值,D與全部的連接電導值都有關,而A只涉及路徑順序的相鄰項。于是可得網(wǎng)絡的結構參數(shù)為其中根據(jù)參數(shù)值構造網(wǎng)絡并讓其運行,則網(wǎng)絡穩(wěn)定時能量函數(shù)E達到極小值。這時網(wǎng)絡的穩(wěn)態(tài)輸出就對應TSP問題的最優(yōu)解。若采用計算機仿真的方法來實現(xiàn),考慮到神經(jīng)元的功能函數(shù)不一定有硬限幅特性,需在E函數(shù)表達式中增加f-1(vi)函數(shù)的積分項。于是可導出網(wǎng)絡的數(shù)學模型為這是n×n個神經(jīng)元動態(tài)方程的一般表達式。聯(lián)立求解這組n×n個非線性一階微分方程組,則可得到TSP問題的最優(yōu)解。

必須指出,起始狀態(tài)選擇的不同,所得結果可能會不一樣。這說明用神經(jīng)網(wǎng)絡解決優(yōu)化計算問題,所得答案并不能保證是最優(yōu)的,但它們是相當接近最優(yōu)的滿意解。9.3

Hopfield網(wǎng)絡的MATLAB開發(fā)

MATLAB為設計Hopfield網(wǎng)絡提供了強有力的工具函數(shù),本節(jié)將對這些函數(shù)的功能、調用格式以及使用方法進行詳細的介紹。

1.網(wǎng)絡函數(shù)(newhop)

功能：設計一個Hopfield神經(jīng)網(wǎng)絡。

指令格式：net=newhop(T)

參數(shù)意義：T為目標向量(元素的值為1或-1)。

Hopfield神經(jīng)網(wǎng)絡經(jīng)常被用于模式的聯(lián)想記憶。Hopfield神經(jīng)網(wǎng)絡僅有一層,其輸入用netsum函數(shù),權函數(shù)用dotprod函數(shù),傳遞函數(shù)用satlins函數(shù)。層中的神經(jīng)元有來自它自身的連接權和閾值。

【例9-4】設計一個Hopfield神經(jīng)網(wǎng)絡,具有兩個三維的穩(wěn)定點(本例M文件見光盤中的FLch9eg1)。

創(chuàng)建該網(wǎng)絡：

net=newhop(T)

下面檢驗該網(wǎng)絡是否穩(wěn)定在這兩個點上。由于Hopfield神經(jīng)網(wǎng)絡沒有輸入項,所以sim()函數(shù)的第二個參數(shù)等于2。程序如下：

Ai=T；

[Y,Pf,Af]=sim(net,2,{},Ai)；

Y

%打印神經(jīng)網(wǎng)絡輸出Y

程序運行結果如下：再通過其它的初始條件Ai來檢驗該網(wǎng)絡的性能。程序如下：

Ai={[-0.9;-0.8;0.7]}；

[Y,Pf,Af]=sim(net,{15},{},Ai)；

Y{1}

%打印網(wǎng)絡輸出

程序運行結果如下：

ans=[JB(]-1-1

1[JB)]

從以上仿真結果可以看出,Ai與設計的第一個初始條件比較接近,所以它使網(wǎng)絡收斂到第一個穩(wěn)定點。2.傳遞函數(shù)(satlins)

功能：對稱飽和線性傳遞函數(shù)。

指令格式：A=satlins(N)

inf=satlins(code)

參數(shù)意義：N為輸入向量。

對稱飽和線性傳遞函數(shù)從網(wǎng)絡的輸入計算一層的輸出。Satlins函數(shù)的算法為：

(1)當N<-1時,satlins(N)＝-1；

(2)當-1≤N≤1時,satlins(N)＝N；

(3)當N>1時,satlins(N)＝1。

satlins(code)返回如下信息：

(1)deriv,返回導數(shù)函數(shù)名稱；

(2)name,