一種基于MRⅡ算法的三層二值雙向聯想記憶網絡

徐 彥,熊迎軍

(南京農業大學信息科學技術學院，江蘇 南京 210095)

1 引言

聯想記憶是神經網絡一個重要的應用，多種神經網絡如Hopfield網絡、Cellular網絡、混沌神經網絡以及雙向聯想記憶BAM(Bidirectional Associative Memory)網絡等都可以用來實現聯想記憶功能。雙向聯想記憶網絡最初是由Kosko[1]提出的，是一種雙向運行的采用全連接兩層結構的網絡，可以用來存儲、記憶兩組對應的模式。自從BAM網絡被提出之后，很多研究者提出了很多不同的雙向聯想記憶網絡結構或算法[2]，到現在依然不斷有最新的研究成果發表[3]。在文獻[1]中，作者采用Hebbian規則訓練網絡權值存儲模式對，Hebbian學習規則的主要缺點是對非正交的模式對學習能力很差。

文獻[4]提出了BL(Bidirectional Learning)算法訓練BAM網絡。這個算法使用感知機規則訓練網絡的權值。文獻[5]提出了PRLAB(Pseudo-Relaxation Learning Algorithm for BAM)算法，該算法通過迭代的方法，依次將模式對輸入網絡學習調整權值，迭代的初始權值是隨機選取的。文獻[6]將Hebbian規則和PRLAB算法結合起來提出了QLBAM(Quick Learning for BAM)算法。該算法的迭代步驟和PRLAB一樣，所不同的是將用Hebbian規則得到的權值矩陣作為迭代的初始權值，因此其存儲模式的能力不低于PRLAB算法，但是收斂的速度更快。

兩層BAM網絡的存儲能力是由兩層神經元的個數，或者說是由需要存儲的模式對的維數決定的，若模式對過多，網絡會無能為力。另外，以上介紹的學習算法只有當模式之間是正交時訓練的效果才會比較好。以上兩點限制了BAM網絡的存儲能力。一個有效提高BAM網絡存儲能力的方法是擴大網絡的結構，構建三層或多層BAM網絡。但是，網絡層數的增加會導致學習難度的增加。一個可行的方法是采用具有連續型激活函數的神經元，然后用類似BP的算法實現三層網絡的學習[7]。

最初的BAM網絡是一個二值網絡，即存儲模式的元素只有兩個值(-1或1)。輸入輸出只處理二值的神經元以硬極限函數作為激活函數，其結構簡單、運行效率較高。很多實際問題處理過程中只涉及兩個值，解決這類問題時，若采用連續型網絡，會引起輸出結果二值化的誤差和效率的降低，采用二值網絡處理有著固有的優勢。因此，二值神經網絡依然具有較高的研究價值。目前，具有三層結構的二值BAM網絡的研究還很少。

三層二值BAM網絡的難點在于學習。因為神經元采用硬極限函數，所以其無法利用梯度下降以及誤差反向傳播實現三層網絡權值的調整。利用前饋神經網絡的學習算法實現BAM網絡的學習是被研究者多次采用的方法。與三層二值 BAM網絡對應的前饋神經網絡是多層二值前饋網絡，這被研究者稱為Madaline網絡[8]。該網絡目前最成功的學習算法稱為MR II(Madaline Rule Ⅱ)算法[9,10]。實驗表明MR Ⅱ算法具有較強的性能。

為了克服兩層BAM網絡的缺點，同時避免采用連續型網絡處理二值模式所帶來的問題，本文提出一種三層結構的二值BAM網絡TLBBAM(Three-Layer Binary BAM)。通過在傳統的兩層BAM網絡之間加入一個中間層，極大地提高了網絡的存儲容量，同時也提高了網絡存儲小差別與非正交模式的能力。TLBBAM中神經元的激活函數為硬極限函數，采用 MR Ⅱ算法訓練網絡權值存儲模式對，使得網絡的輸入、輸出、運行及權值的訓練等全部采用二值處理。目前，研究者對BAM網絡的研究更多的集中在復雜的連續型BAM網絡的穩定性理論上[11,12]，TLBBAM作為一種新的BAM網絡結構與學習算法可以從另一個重要方面拓展與完善BAM網絡的研究，因此具有較高的理論與實際意義。

2 TLBBAM的結構以及學習算法

2.1 兩層BAM的結構及QLBAM算法

三層二值BAM網絡以兩層二值BAM網絡為基礎。如圖1所示，初始的兩層BAM網絡由X層和Y層構成。

Figure 1 Two-layer BAM network圖1 兩層BAM網絡

(1)

(2)

其中,λ,ξ為參數。當Y(k)輸入到Y層，若在X層模式輸出錯誤，也需要調整權值和偏置值，其調整規則與式(1)和式(2)完全類似。

2.2 TLBBAM的結構

本文提出的TLBBAM網絡為三層結構，即在傳統兩層BAM網絡的X層和Y層之間加上一個中間層。其結構如圖2所示。其中X層和Y層的功能與兩層BAM網絡一樣，負責模式的輸入與輸出，H層為中間層。

Figure 2 Three-layer Binary BAM圖2 三層二值雙向聯想記憶網絡結構

其中，(W1)N×T為X層和中間層之間的權值矩陣，(W2)T×M為中間層和Y層之間的權值矩陣，θx和θy分別為X層和Y層的偏置，θh為中間層的偏置，N、M、T分別為X層、Y層和中間層的神經元個數，k∈{1,…,K},K為存儲的模式對個數。網絡X層和Y層神經元的個數由所存儲的模式對的維數決定，中間層神經元的個數是一個可以調節的參數，理論上中間層神經元個數越多，網絡的存儲能力越強，可以存儲的模式對越多。

2.3 TLBBAM的學習算法

TLBBAM網絡的學習算法，我們引入二值多層前向網絡Madaline的MR Ⅱ算法[8]。MR Ⅱ算法是一種有監督的學習算法，網絡的訓練過程實際上就是對網絡的權值與偏置值調節的過程。對權值和偏置值的每一次調節，總希望在滿足當前樣本學習的同時，盡量使得本次學習對網絡總體的結構改變最小，這樣就可以讓網絡通過前面樣本學習到的性能得到最大限度的保持。這就是MR Ⅱ算法的理論基礎“最小擾動原則”。

假設有一個三層Madaline網絡。網絡在學習過程中，權值的調整從中間層到輸出層依次進行，一次完整的學習過程稱為一次迭代或一個學習周期。設當前為第k次迭代，按照最小擾動原則選擇網絡某一層的一個神經元翻轉其輸出狀態作為期望輸出計算調整該神經元的權值。此時，以神經元的“信任度”，即該神經元內部此次運行的加權和的絕對值|u|=|W(k)X(k)|作為衡量該神經元權值改變對整個網絡影響程度的指標量，其中W(k)和X(k)分別為神經元的權值和輸入向量。并且規定，當某個神經元的信任度大于某一數值δ時，不對這個神經元的權值進行調整，對于其它的神經元按照信任度從小到大依次選擇進行學習。權值調整后若網絡的最終實際輸出更接近網絡的最終期望輸出，則保留這次翻轉。具體的權值調整公式為:

W(k+1)=

其中，n為當前神經元的輸入維數，η為確保輸出翻轉的常數，d(k)為神經元的期望輸出，L是一個常數。該算法重復上述的過程，直到網絡訓練成功或者達到某一最大訓練迭代次數為止。

TLBBAM借助于MR Ⅱ算法可以成功地將X層、中間層和Y層連接起來實現模式對的訓練存儲。在學習過程中，依次使用需要存儲的K個模式對V={(X(k),Y(k))},k=1,…,K訓練網絡。對于每一對模式(X(k),Y(k))，在網絡的兩個方向上都訓練一次。首先從X層到Y層，將X(k)看成Madaline網絡的輸入，Y(k)看成Madaline網絡的期望輸出，利用MR Ⅱ算法，訓練網絡的權值和偏置值。接著從Y層到X層，將Y(k)看成Madaline網絡的輸入，X(k)看成Madaline網絡的期望輸出，利用MR Ⅱ算法，訓練網絡的權值和偏置值。這樣循環下去，直到網絡成功收斂或者達到某一最大循環迭代次數。本文中學習收斂指的是通過訓練網絡可以成功地存儲并正確回憶所有待存儲模式對。

TLBBAM的學習算法可以表述為：

(1)在訓練的初始階段，隨機選擇一組數作為網絡的初始權值和偏置W1,W2,θx,θy,θh。

(2)重復運行下列學習周期，直到收斂或達到某一個最大學習周期數：

對需要存儲的模式對V={(X(k),Y(k))},k=1,…,K，作如下循環，Fork=1 toK

①將X(k)作為輸入，Y(k)作為期望輸出，利用MR Ⅱ算法，在X層到Y層方向上訓練網絡;

②將Y(k)作為輸入，X(k)作為期望輸出，利用MR Ⅱ算法，在Y層到X層方向上訓練網絡;

Nextk

(3)測試以上學習得到的網絡權值和偏置值。

3 實驗

下面我們用幾組實驗來驗證TLBBAM網絡存儲模式的能力。在第一組實驗中我們存儲0～9這10個數字的點陣模式與它們的二進制模式組成的模式對。數字的點陣模式用二值10×8方格表示，黑的方格為-1，白的方格為1。標準的二進制是由0，1表示的數字，在這里我們將0用-1代替。因為10個數字的二進制模式只需要四位二進制數，所以我們用二值1×4方格表示。如圖3所示，上面的10個是數字的點陣模式，下面的10個是二進制模式，兩兩對應組成10個模式對。

Figure 3 Lattice and binary models of numbers圖3 數字的點陣模式和二進制模式

二值1×4方格總共有16個，其中數字模式占去10個，還剩下6個。為了增加學習的難度，在這6個中我們選出4個，和加、減、乘、除這四個運算符的點陣模式組成模式對，并且將剩下的2個和另外2個隨機產生的10×8點陣模式組成模式對，如圖4所示。這樣，需要存儲的模式一共有16對。這里用X(k),k=1,…,16來表示數字和運算符的點陣模式，用Y(k),k=1,…,16來表示數字的二進制以及運算符的四位模式，上標中1～10依次為數字1～9和0，11～14依次代表加、減、乘、除四個運算符，15、16代表隨機模式。

Figure 4 Lattice and four bit binary models of operators and random models圖4 運算符及隨機模式的點陣模式和四位模式

這個例子有如下幾個特點。第一，實驗中的四位模式使用了全部的16個四位二值向量，我們稱之為模式的飽和存儲問題，模式中有的模式之間差別很小，比如數4和5的二進制只相差末尾的1位，在學習結束回憶模式時任何誤差都會導致回憶出的是另一個模式，這需要網絡提供足夠強的模式區分能力；第二，模式對之間不是兩兩正交的;第三，一個模式對中80維向量對應于4維向量，向量維數之間差距很大。這些都增加了學習存儲模式的難度。

首先我們采用傳統兩層二值BAM網絡來學習存儲這16對模式，網絡的X層有10×8=80個神經元，Y層有4個神經元。實驗中我們采用RPLAB和QLBAM算法訓練網絡，每次實驗迭代周期的最大值設置為1 000次。實驗結果表明,兩層結構的BAM網絡在任何實驗設定下都無法將這16對模式全部存儲進網絡。以性能最強的QLBAM算法為例，圖5顯示了經過訓練之后將兩組模式中的前14個分別從兩個方向輸入網絡后得到的對應模式回憶結果。由圖5可知，網絡經過訓練后模式聯想回憶的結果很差，點陣模式除了一個能完美回憶，4個回憶有噪音以外都沒有正確回憶出來，而四位模式只有5個能正確回憶。這說明兩層BAM網絡整體存儲這16對模式的性能很差。

Figure 5 Recall results of TLBBAM for 16 pair models圖5 兩層二值BAM網絡回憶16對模式的結果

在實驗中如果只選擇16對模式中的一部分進行學習，則存儲性能會有所提高。例如，如果只學習7～14這8個模式對，兩層二值BAM網絡采用QLBAM算法可以訓練成功。這也是兩層BAM網絡學習這16對模式存儲結果最好的情況，或者說對于這個例子兩層BAM的存儲性能在此時達到極限。

接下來我們采用本文提出的TLBBAM網絡來學習存儲這16對模式。實驗中X層和Y層的神經元個數和上面的兩層BAM網絡一樣，中間層神經元的個數設置為從10個開始，每次增加兩個，逐漸增加到34個。實驗中MR Ⅱ算法參數選擇如下:δ=6.5,η=0.4,L=3.5；網絡的初始權值和偏置值隨機選擇由1或-1組成的矩陣和向量。每種情形下進行100次實驗，每次實驗的最大迭代周期數設置為500，記錄網絡能成功存儲并回憶所有16對模式的實驗次數以及這些成功實驗中網絡學習所需要的平均周期數。實驗的結果如表1所示。

Figure 6 An experimental result of TLBBAM learning 16 pair models圖6 TLBBAM學習存儲16對模式的一次實驗結果

神經元個數成功次數學習周期神經元個數成功次數學習周期107136249988123310226998014609928100821673953010078189392321007820978734100732299 88

從表1可以看到，隨著中間層神經元個數的逐漸增加，學習成功的次數也隨之增加。在中間層只有10個神經元時，只有大約7%的實驗可以成功存儲這16對模式；當中間層神經元個數超過26個，每一次實驗都可以成功地將16對模式存儲進網絡，即此時成功率為100%。因此，兩層二值BAM無法成功存儲16個模式對，采用TLBBAM網絡可以成功存儲并正確回憶。實驗的結果說明，TLBBAM網絡相比較兩層BAM網絡在模式記憶與區分能力上有了極大的提高，可以有效解決飽和模式存儲問題。觀察表1中的學習周期可知，隨著中間層神經元個數的增加，學習周期數呈現逐漸下降的趨勢，這說明增加中間層神經元個數可以提高網絡的學習效率。

圖6顯示了當中間層神經元個數為10時某一次沒有成功的實驗在訓練結束后前14個模式對的回憶結果。此時，數字與運算符的點陣模式有2個回憶錯誤，有1個回憶時出現噪音，其余全部正確；而四位模式中只有2個回憶錯誤，總體錯誤率較低。對比圖5可知，雖然在這次實驗中訓練沒有收斂，但是模式回憶的結果也明顯好于兩層BAM網絡。

下面考察TLBBAM網絡的存儲容量，訓練網絡存儲6×5的隨機模式對。圖7顯示了五對隨機產生的6×5模式。實驗先采用兩層BAM網絡結合QLBAM算法，網絡的X層和Y層各有30個神經元，QLBAM的兩個訓練參數設置為λ=1.5,ξ=0.05。實驗中存儲的模式對個數從30個開始逐步增加，每種情況進行50次實驗，每次實驗學習的最大迭代周期數設置為1 000。實驗結果顯示，QLBAM算法可以使兩層BAM網絡最多成功存儲39對隨機模式，此時訓練成功平均需要115個迭代周期。

Figure 7 Five pairs 6×5 models generated randomly圖7 隨機生成的5對6×5模式

接著，我們采用TLBBAM網絡來存儲6×5的隨機模式對，實驗中我們從兩層BAM網絡能夠存儲的39個模式對開始，逐步增加存儲的模式對個數，這個例子中MR Ⅱ算法參數選擇如下:δ=7,η=1,L=3.5。實驗結果如表2所示，表中第一列為模式對個數，第二列為50次實驗均能成功存儲模式對需要的最少的中間層神經元個數，第三列為學習需要的平均迭代周期數。

Table 2 Experimental results of TLBBAM learning 6×5 random model pairs

由表2可知，當存儲的模式對個數為39個時，TLBBAM網絡需要29個中間層神經元就可以成功存儲所有模式對，此時需要的學習周期數平均為133，略多于QLBAM算法的。當存儲的模式對個數不斷增加，兩層BAM網絡已經不能成功存儲所有模式，但是TLBBAM網絡只要相應地增加中間層神經元個數就可以將所有模式對存儲進網絡。例如，當模式對個數為100時，中間層神經元個數增加到132個即可，此時網絡的存儲容量大概是兩層BAM網絡存儲容量的2.5倍。由此可知，相比較兩層BAM網絡，TLBBAM網絡極大地提高了存儲容量。另外，理論上只要繼續增加中間層神經元個數，網絡中能夠存儲的模式對個數就會繼續增加。由表2的第三列可知，伴隨著存儲容量的增加，TLBBAM網絡需要的學習周期數也會增加。

對于BAM網絡，針對學習算法的收斂性、網絡存儲容量以及算法學習效率的理論分析[13]是研究者普遍會討論的內容。但是，TLBBAM有著自身的特點，首先，由于TLBBAM采用MR Ⅱ算法，而MR Ⅱ算法的一個顯著特點就是不斷地嘗試翻轉神經元的輸出，這種試驗性導致缺乏對其收斂性進行系統分析的理論基礎。但是，這并不影響MR Ⅱ成為一種十分有效的學習算法。對于網絡的存儲容量，因為中間層神經元的個數不同，整個網絡的存儲容量也會不同，結合MR Ⅱ算法的特點導致TLBBAM網絡的存儲容量的理論分析會比較復雜，本文對此暫不考慮。但是，TLBBAM網絡的存儲容量具有很高的靈活性，通過增加中間層神經元個數就可以增加其容量，并且提高學習的成功率。

4 結束語

針對傳統兩層BAM存儲能力不足的缺點，同時避免采用連續型神經元帶來的問題，本文提出了一種三層二值BAM網絡TLBBAM。該網絡中的神經元使用硬極限函數作為激活函數，在處理二值問題時具有更高的效率和精度。TLBBAM網絡通過增加中間層的方式在結構上擴展了傳統的BAM網絡，在學習方法上將MR Ⅱ算法應用于BAM網絡首次實現了多層二值BAM網絡的學習。實驗表明，TLBBAM網絡的模式存儲和區分能力比傳統兩層BAM網絡有極大的提高。今后的研究中我們將繼續深入探討TLBBAM網絡的性質，如存儲能力的分析、對帶噪音模式的抗干擾能力以及網絡參數的選擇等等。

[1] Kosko B.Bidirectional associative memories[J].IEEE Transactions on Systems,Man and Cybernetics,1988,18(1):49-60.

[2] Maria E A-M,Cornelio Y M,Marco A A-M.Bidirectional associative memories:Different approaches[J].ACM Computing Surveys,2013,45(2):1-30.

[3] Sakthivel R,Vadivel P,Mathiyalagan K.Design of state estimator for bidirectional associative memory neural networks with leakage delays[J].Information Sciences,2015,296:263-274.

[4] Leung C S. Optimum learning for bidirectional associative memory in the sense of capacity[J].IEEE Transactions on Systems,Man and Cybernetics,1994,24(5):791-796.

[5] Oh H,Kothari S C.Adaptation of the relaxation method for learning in bidirectional associative memory[J].IEEE Transactions on Neural Networks,1994,5(4):576-583.

[6] Hattori M,Hagiwara M,Nakagawa M.New results of quick learning for bidirectional associative memory having high capacity[C]∥Proc of IEEE International Conference on Neural Networks,1994:1080-1085.

[7] Roukhe A,Fares A,Bouzid A.Multilayer neural network of adaptive bidirectional associative memories[J].Comptes Rendus de l’Acad′emie des Sciences-Series IIB-Mechanics-Physics-Astronomy,1999,327(7):691-699.

[8] Zhang W.MADALINE neural network with truncated momentum for LTV MIMO system identification[C]∥Chinese Control and Decision Conference,2012:23-25.

[9] Winter R,Widrow B.Madaline rule ii:A training algorithm for neural networks[C]∥Proc of IEEE International Conference on Neural Networks,1988:401-408.

[10] Sheng Xin-xin, Yan Wei-qiong, Wang Bing-hui.An improved learning algorithm for madaline network [J].Computer Technology and Development,2006,16(6):224-226.(in Chinese)

[11] Wang Fen,Wu Huai-yu.Existence and stability of periodic solution for BAM neural networks [J].Computer Engineering and Applications,2010,46(24):15-18.(in Chinese)

[12] Gao Ming.Stability of impulsive BAM neural networks with time-varying delays [J].Mathematica Applicata,2012,25(1):160-166.(in Chinese)

[13] Kabashima Y,Tanaka T,Kakiya S.Capacity analysis of bidirectional associative memory[C]∥Proc of International Conference on Neural Information Processing,2000:779-784.

附中文參考文獻：

[10] 盛新新,顏偉瓊,王炳輝.Madaline網絡學習算法改進[J].計算機技術與發展,2006,16(6):224-226.

[11] 王芬,吳懷宇.BAM神經網絡周期解的存在性與穩定性[J].計算機工程與應用,2010,46(24):15-18.

[12] 高明.變時滯脈沖BAM神經網絡的穩定性[J].應用數學,2012,25(1):160-166.