容量約束的自組織增量聯(lián)想記憶模型*

孫　桃，謝振平，王士同，劉　淵江南大學(xué)數(shù)字媒體學(xué)院，江蘇無錫214122

* The National Natural Science Foundation of China under Grant No. 61272210 (國家自然科學(xué)基金); the Natural Science Foundation of Jiangsu Province under Grant Nos. BK20130161, BK2011003 (江蘇省自然科學(xué)基金).

Received 2015-03,Accepted 2015-05.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-05-29, http://www.cnki.net/kcms/detail/11.5602.TP.20150529.1611.003.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0130-12

?

容量約束的自組織增量聯(lián)想記憶模型*

孫桃，謝振平+，王士同，劉淵
江南大學(xué)數(shù)字媒體學(xué)院，江蘇無錫214122

* The National Natural Science Foundation of China under Grant No. 61272210 (國家自然科學(xué)基金); the Natural Science Foundation of Jiangsu Province under Grant Nos. BK20130161, BK2011003 (江蘇省自然科學(xué)基金).

Received 2015-03,Accepted 2015-05.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-05-29, http://www.cnki.net/kcms/detail/11.5602.TP.20150529.1611.003.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0130-12

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：自組織聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)因其并行、容錯及自我學(xué)習(xí)等優(yōu)點而得到廣泛應(yīng)用，但現(xiàn)有主流模型在增量學(xué)習(xí)較大規(guī)模樣本時，網(wǎng)絡(luò)節(jié)點數(shù)可能無限增長，從而給實際應(yīng)用帶來不可承受的內(nèi)存及計算開銷。針對該book=131,ebook=135問題，提出了一種容量約束的自組織增量聯(lián)想記憶模型。以網(wǎng)絡(luò)節(jié)點數(shù)為先決控制參數(shù)，結(jié)合設(shè)計新的節(jié)點間自競爭學(xué)習(xí)策略，新模型可滿足大規(guī)模樣本的增量式學(xué)習(xí)需求，并能以較低的計算容量取得較高的聯(lián)想記憶性能。理論分析表明了新模型的正確性與有效性，實驗分析同時顯示了新模型可有效控制計算容量，提升增量樣本學(xué)習(xí)效率，并獲得較高的聯(lián)想記憶性能，從而能更好地滿足現(xiàn)實應(yīng)用需求。

關(guān)鍵詞：聯(lián)想記憶；容量約束；增量學(xué)習(xí)；自組織；神經(jīng)網(wǎng)絡(luò)

1　引言

聯(lián)想記憶[1]是人腦計算的一個核心功能，為使機器獲得類人智能，研究者設(shè)計了各種可進行機器計算的聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)來對此進行模擬。聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)將對象模式顯式或隱式地存儲至網(wǎng)絡(luò)節(jié)點，并通過示例樣本的學(xué)習(xí)訓(xùn)練，實現(xiàn)對輸入模式聯(lián)想記憶出相應(yīng)的輸出模式。聯(lián)想記憶主要分為自聯(lián)想記憶和異聯(lián)想記憶兩種方式。前者輸出受損或受污染輸入模式的原始模式，后者輸出輸入模式的（因果）相關(guān)模式[2]。人工聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)因其具有較好的抗噪性、分布式信息存儲能力、穩(wěn)定性，并在一定程度上模擬了人類大腦對信息的記憶、識別和聯(lián)想等功能，已大量應(yīng)用于人臉識別[3]、模式識別[4]、圖像和聲音識別、機器人[5]等領(lǐng)域。

自20世紀(jì)80年代開始，聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)逐漸成為機器學(xué)習(xí)的重要研究領(lǐng)域之一。以經(jīng)典的Hopfield網(wǎng)絡(luò)[6]為標(biāo)志，聯(lián)想記憶模型經(jīng)歷了從全連接網(wǎng)絡(luò)到稀疏連接網(wǎng)絡(luò)，從單層單向到多層多向，從自聯(lián)想到異聯(lián)想[7]，從一對一聯(lián)想到一對多甚至多對多聯(lián)想，從二值型到非二值型，從簡單網(wǎng)絡(luò)到復(fù)雜網(wǎng)絡(luò)[8]的發(fā)展。目前已提出的一些聯(lián)想記憶模型有：基于動態(tài)突觸的神經(jīng)網(wǎng)絡(luò)聯(lián)想記憶模型[9]，其在存儲容量上擁有比Hopfield聯(lián)想記憶網(wǎng)絡(luò)更優(yōu)秀的性能；基于模糊學(xué)的神經(jīng)網(wǎng)絡(luò)聯(lián)想記憶模型[10]，其利用模糊運算能夠很好地抵抗噪聲，具有較好的容錯能力；基于自組織的神經(jīng)網(wǎng)絡(luò)聯(lián)想記憶模型[11]，其調(diào)節(jié)神經(jīng)元連接動力學(xué)形成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，使迭代收斂速度較快。

雖然現(xiàn)有聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)性能較早期的模型已有較大提高，但許多受容量效率限制而實用性并不強。此外，大部分聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法主要聚焦于常規(guī)的樣本訓(xùn)練方式，對于增量地學(xué)習(xí)樣本數(shù)據(jù)問題，則涉及較少，難以在大數(shù)據(jù)環(huán)境下演化地提升模型的計算性能。針對容量效率和增量學(xué)習(xí)[12]問題，現(xiàn)有一些方法如有界支持向量機[13]和在線球向量機[14]（online ball vector machine，OBVM）提出了一些解決方法，但此類方法主要針對二分類問題，不適用于復(fù)雜聯(lián)想記憶輸出要求。

針對上述問題，本文提出了一種容量約束的自組織增量聯(lián)想記憶模型（self-organizing incremental associative memory model under capacity constraint，CCGAM）。新模型以控制網(wǎng)絡(luò)節(jié)點數(shù)為手段，通過引入一種新的節(jié)點自競爭學(xué)習(xí)策略，實現(xiàn)模型在大規(guī)模增量可學(xué)習(xí)樣本環(huán)境下的性能演化提升[15]，在獲得較好模型性能的同時保持較低且可控的內(nèi)存及計算要求。這為聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)相關(guān)應(yīng)用及理論研究提供了一種非常有意義的新方法。

2　相關(guān)模型

作為早期Hopfield聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)模型的推廣，Kosko等人[16]提出了一種雙向聯(lián)想記憶模型（bidirectional associative memory，BAM）。BAM是一種兩層非線性反饋神經(jīng)網(wǎng)絡(luò)，可以用較小的相關(guān)矩陣實現(xiàn)有效的異聯(lián)想。但BAM存在的補碼問題和連續(xù)性假設(shè)限制了其存儲容量和糾錯能力，且其僅能處理二值型模式數(shù)據(jù)，實用性仍不強。

Wang等人[17]提出了一種新的模糊形態(tài)學(xué)聯(lián)想記憶模型（fuzzy morphological associative memories，F(xiàn)MAM）。FMAM結(jié)合了形態(tài)學(xué)聯(lián)想記憶[18]（morphological associative memories，MAM）和模糊聯(lián)想記憶[19]（fuzzy associative memories，F(xiàn)AM），用模糊算子(∨，?)和(∧，?)代替FAM中的(∨，∧)算子，并具有較好的可解釋性，其中提供了一種模糊規(guī)則集可完全聯(lián)想回憶的新編碼方法。FMAM的模糊算子能夠有效地抑制樣本噪聲的干擾，在學(xué)習(xí)樣本差異較大，受污染嚴(yán)重的情況下仍可擁有較好的聯(lián)想記憶性能。雖然如此，但FMAM不具備增量學(xué)習(xí)能力，不適合學(xué)習(xí)條件復(fù)雜，學(xué)習(xí)樣本規(guī)模大的情況，也不具有異聯(lián)想功能。

為實現(xiàn)聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)的增量學(xué)習(xí)[20]，F(xiàn)urao等人提出了一種自組織增量神經(jīng)網(wǎng)絡(luò)[21]（self-organizing incremental neural network，SOINN）。SOINN采用無監(jiān)督增量學(xué)習(xí)方法，實現(xiàn)對復(fù)雜分布數(shù)據(jù)的增量在線學(xué)習(xí)，并能夠近似得到輸入數(shù)據(jù)的分布，以自組織聚類方法估計出數(shù)據(jù)的類群數(shù)。進一步，F(xiàn)urao等人[22]在SOINN基礎(chǔ)上提出了一種廣義聯(lián)想記憶模型（general associative memory，GAM）。GAM是一種三層網(wǎng)絡(luò)結(jié)構(gòu)的通用聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)模型，其采用有監(jiān)督學(xué)習(xí)方法，具有較好的廣義性和聯(lián)想記憶性能，同時支持自聯(lián)想和異聯(lián)想記憶輸出。GAM模型結(jié)構(gòu)如圖1所示，包括輸入層、記憶層和聯(lián)想層。輸入層接受輸入模式數(shù)據(jù)以及它們間的關(guān)系；記憶層與輸入層為全連接，將輸入模式數(shù)據(jù)經(jīng)變換后存儲至對應(yīng)的記憶子網(wǎng)中；聯(lián)想層中的每個神經(jīng)節(jié)點與對應(yīng)的記憶子網(wǎng)相關(guān)聯(lián)，并與聯(lián)想層其他節(jié)點間用有向邊表示聯(lián)想計算通路。

Fig.1 Three-layer network structure of GAM圖1　GAM三層網(wǎng)絡(luò)結(jié)構(gòu)

GAM記憶層對樣本進行學(xué)習(xí)時，首先在記憶層中找到對應(yīng)該樣本標(biāo)簽的子網(wǎng)絡(luò)，然后在子網(wǎng)絡(luò)中找到距離要學(xué)習(xí)樣本最近的節(jié)點（冠軍節(jié)點）和次近節(jié)點（亞軍節(jié)點）；隨后計算輸入樣本與冠軍節(jié)點的距離s，并判斷s與冠軍節(jié)點相似性閾值Th之間的大小關(guān)系，若s大于Th，則將該學(xué)習(xí)樣本作為新節(jié)點插入，否則更新冠軍節(jié)點和亞軍節(jié)點的權(quán)值向量，更新規(guī)則如下：

其中，w代表節(jié)點權(quán)值向量；s1為冠軍節(jié)點；s2為亞軍節(jié)點；x為訓(xùn)練樣本；M為節(jié)點被選為冠軍節(jié)點的次數(shù)。冠軍節(jié)點的相似性閾值更新如下：

如果冠軍節(jié)點和亞軍節(jié)點之間沒有連接邊，添加一條邊連接冠軍和亞軍節(jié)點，并將邊年齡(age)設(shè)為0，然后將所有與冠軍節(jié)點相連的邊年齡加1。如果邊的年齡大于預(yù)先定義的agemax，刪除該邊。最后，刪除孤立節(jié)點。

GAM算法實現(xiàn)了多向自由聯(lián)想記憶，可以處理實值型數(shù)據(jù)，能在不破壞全部神經(jīng)元原有連接結(jié)構(gòu)的情況下進行增量學(xué)習(xí)，并可對含噪輸入模式聯(lián)想回憶出真實模式。但GAM對初值過于敏感，且在大規(guī)模樣本學(xué)習(xí)或者增量學(xué)習(xí)時，網(wǎng)絡(luò)節(jié)點數(shù)量不可調(diào)節(jié)，存在無限增長的可能，相應(yīng)的訓(xùn)練及聯(lián)想回憶計算時間復(fù)雜度也會無限增大，這將導(dǎo)致其具有的增量學(xué)習(xí)能力難以發(fā)揮很好的實際作用，不能靈活地應(yīng)對復(fù)雜的現(xiàn)實需求，廣義適用性受到嚴(yán)重限制。

考慮到影響聯(lián)想記憶神經(jīng)網(wǎng)絡(luò)模型計算和學(xué)習(xí)效率的控制參數(shù)為網(wǎng)絡(luò)神經(jīng)元節(jié)點數(shù)，以此為出發(fā)點，文中借鑒文獻[13]的有界控制策略，結(jié)合新設(shè)計的節(jié)點間自競爭學(xué)習(xí)策略，提出了一種容量約束的自組織增量聯(lián)想記憶模型CCGAM。

3　CCGAM

CCGAM網(wǎng)絡(luò)模型結(jié)構(gòu)仍采用GAM相同的形式（見圖1），在學(xué)習(xí)方法上，首先考慮網(wǎng)絡(luò)神經(jīng)元數(shù)目具有上界約束，以限制網(wǎng)絡(luò)的計算和存儲規(guī)模，然后基于新提出的節(jié)點間自競爭學(xué)習(xí)策略，實現(xiàn)模型參數(shù)的學(xué)習(xí)。節(jié)點間自競爭學(xué)習(xí)策略不僅保證了學(xué)習(xí)結(jié)果的準(zhǔn)確性，同時可有效避免GAM的初值敏感問題。下面分別從CCGAM的學(xué)習(xí)算法、聯(lián)想算法、理論特性等幾個方面展開描述。

3.1CCGAM學(xué)習(xí)算法

CCGAM學(xué)習(xí)算法包括記憶層學(xué)習(xí)算法和聯(lián)想層學(xué)習(xí)算法。在記憶層學(xué)習(xí)算法中，為每個記憶子網(wǎng)絡(luò)節(jié)點規(guī)模設(shè)置上界閾值Nmax。初始學(xué)習(xí)時，將同一標(biāo)簽的前Nmax個樣本作為新節(jié)點添加至相應(yīng)的記憶層子網(wǎng)絡(luò)，這可有效避免GAM的初值敏感問題，強化對新知識的學(xué)習(xí)。在新引入的自競爭學(xué)習(xí)策略中，當(dāng)子網(wǎng)絡(luò)中節(jié)點數(shù)目達(dá)到上限閾值時，以一定概率淘汰對網(wǎng)絡(luò)結(jié)構(gòu)影響最小的節(jié)點，保證網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的穩(wěn)定性。上述學(xué)習(xí)算法能夠?qū)⒚總€子網(wǎng)絡(luò)中節(jié)點數(shù)量控制在節(jié)點規(guī)模上界內(nèi)，滿足大規(guī)模增量樣本的在線學(xué)習(xí)要求，并能有效地提高學(xué)習(xí)效率，避免不可控的內(nèi)存及計算開銷。CCGAM記憶層學(xué)習(xí)算法具體如算法1所示。

算法1 CCGAM記憶層學(xué)習(xí)算法

（1）初始化記憶層：A＝Φ，S＝Φ（A為記憶層節(jié)點集合，S為記憶層子網(wǎng)絡(luò)集合）；

（2）設(shè)定每個模式子網(wǎng)絡(luò)節(jié)點規(guī)模上界閾值Nmax；

（3）輸入x∈RD到記憶層，x屬于類cx（cx為x的標(biāo)簽）；

（4）若記憶層沒有子網(wǎng)絡(luò)cx，則添加cx，S＝S∪{cx}，A＝A∪{}，w＝x，＝1，轉(zhuǎn)步驟（3）；

（6）計算子網(wǎng)絡(luò)cx中節(jié)點數(shù)量Qcx；

（7）若Qcx＜Nmax，則將x作為新節(jié)點插入cx，＝x，＝1，轉(zhuǎn)步驟（3）；

（9）若d1＞d2且r＜1/Ms3，刪除s3，x作為新節(jié)點插入cx中，＝x，＝1，否則，更新ws1，ws1← ws1＋δs1(x?ws1)，其中δs1＝1/Ms1；

（10）如果訓(xùn)練沒有結(jié)束，轉(zhuǎn)步驟（3）。

分析算法1中步驟（6）和（7）可知，CCGAM將前Nmax個樣本全部作為新節(jié)點添加到網(wǎng)絡(luò)，若其中含有兩個噪聲點P1、P2（如圖2所示），則其在后續(xù)樣本學(xué)習(xí)過程時被選中冠軍節(jié)點的概率將較小，最終將由步驟（8）和（9）的自競爭策略淘汰掉。而GAM對于樣本初值過于敏感，在其學(xué)習(xí)前兩個受污染樣本后，添加P1、P2兩個噪聲點到網(wǎng)絡(luò)中，兩點的相似性閾值Th均被更新為P1與P2之間的歐氏距離d。由于后續(xù)樣本點到P1或P2的距離小于Th，導(dǎo)致GAM始終更新P1、P2節(jié)點的權(quán)值，對新知識的學(xué)習(xí)能力較弱。

Fig.2 Initializing samples with noises圖2　初始含噪聲樣本數(shù)據(jù)

CCGAM聯(lián)想層學(xué)習(xí)算法仍采用與GAM相同的算法，以學(xué)習(xí)不同類別輸入輸出模式間的異聯(lián)想關(guān)系，具體見算法2。其中，輸入模式經(jīng)算法1學(xué)習(xí)至記憶層后，在聯(lián)想層建立與記憶層中每個子網(wǎng)絡(luò)一一對應(yīng)的節(jié)點，然后通過在聯(lián)想層節(jié)點間建立有向箭頭表示每個輸入模式間的異聯(lián)想關(guān)系，有向箭頭權(quán)重表示聯(lián)想優(yōu)先級。

算法2 CCGAM聯(lián)想層學(xué)習(xí)算法

（1）初始化聯(lián)想層：B＝Φ，D＝Φ（B為聯(lián)想層節(jié)點集合，D為聯(lián)想層有向邊集合）；

（2）輸入x、y向量，x∈RD，x標(biāo)簽cx，y∈Rm，y標(biāo)簽cy；

（3）用算法1分別將x、y學(xué)習(xí)到記憶層；

（4）若聯(lián)想層中沒有代表cx的節(jié)點b，則插入新節(jié)點b代表cx，B＝B∪，cb＝cx，mb＝0，wb＝x（mb為b引用次數(shù)，wb為b權(quán)值，cb為b名稱）；

（5）否則，更新節(jié)點b的m值，mb←mb＋1，找到記憶層cx中M值最大的節(jié)點i，，更新b權(quán)值；

（6）若聯(lián)想層中沒有代表cy的節(jié)點d，則插入新節(jié)點d代表cy，B＝B∪j5i0abt0b，cd＝cy，md＝0，wd＝y(tǒng)；

（7）否則，找到cy中M值最大的節(jié)點i，i＝，更新d權(quán)值；

（8）設(shè)置cd為b的序號mb的響應(yīng)節(jié)點，RCb[mb]＝cd（RCb為b的響應(yīng)節(jié)點）；

（9）若b、d無有向邊相連，用有向邊將b、d相連，b出發(fā)，d結(jié)束，添加有向邊(b，d)到集合D，D＝D∪{(b，d)}，設(shè)置(b，d)權(quán)值w(b，d)＝1；

（10）否則，更新(b，d)權(quán)值w(b，d)←w(b，d)＋1。

3.2CCGAM聯(lián)想算法

不完全相同于GAM模型，CCGAM聯(lián)想算法采用的自聯(lián)想算法和異聯(lián)想算法分別如算法3和算法4所示。與GAM的自聯(lián)想算法不同，算法3在記憶層中使用輸入模式x對應(yīng)模式子網(wǎng)絡(luò)中節(jié)點間最大距離作為自聯(lián)想輸出有效的置信閾值，以取得更高的自聯(lián)想準(zhǔn)確性。

算法3 CCGAM自聯(lián)想算法

（1）輸入向量x；

（3）計算ck中任兩節(jié)點間的距離最大值smax＝；

（4）若smin大于smax，則自聯(lián)想失敗，否則，輸出自聯(lián)想結(jié)果wk和標(biāo)簽ck。

算法4 CCGAM異聯(lián)想算法

（1）輸入線索向量x；

（2）用算法3找出x在記憶層中所屬的子網(wǎng)絡(luò)cx；

（3）在聯(lián)想層找到代表cx的節(jié)點bx；

（4）按響應(yīng)優(yōu)先級輸出bx所有響應(yīng)節(jié)點。

CCGAM的異聯(lián)想算法與GAM相同，能夠聯(lián)想出輸入線索模式的所有響應(yīng)模式，并根據(jù)響應(yīng)優(yōu)先級輸出。首先由算法3聯(lián)想出線索模式在記憶層中的子網(wǎng)絡(luò)，然后找到該子網(wǎng)絡(luò)在聯(lián)想層中對應(yīng)的節(jié)點，最后按照響應(yīng)優(yōu)先級依次輸出所有的響應(yīng)節(jié)點，實現(xiàn)多對多聯(lián)想。如圖3所示，x1是線索模式類在聯(lián)想層中的代表節(jié)點，其響應(yīng)節(jié)點為x2、x3、x4，算法4將根據(jù)響應(yīng)節(jié)點對應(yīng)的優(yōu)先級w1、w2和w8的大小順序依次輸出響應(yīng)節(jié)點。

Fig.3 Structure of associative layer of CCGAM圖3　CCGAM聯(lián)想層結(jié)構(gòu)模型

3.3CCGAM理論分析

3.3.1學(xué)習(xí)穩(wěn)定性

CCGAM基于對樣本的增量迭代學(xué)習(xí)而得到模型參數(shù)，為保證學(xué)習(xí)的可靠性，通常要求學(xué)習(xí)算法是漸近穩(wěn)定的。對于CCGAM，在網(wǎng)絡(luò)節(jié)點數(shù)達(dá)到上界時，通過自競爭策略更新或者替換某個節(jié)點，經(jīng)分析可知有以下定理成立。

定理1 CCGAM對任一記憶層節(jié)點權(quán)值的迭代更新過程是收斂穩(wěn)定的。

證明設(shè)有n個輸入模式v1，v2，…，vn屬于同一標(biāo)簽cv，CCGAM記憶層與cv對應(yīng)的子網(wǎng)絡(luò)中的節(jié)點數(shù)為m個，對cv中每個模式vi(i＝1，2，…，n)進行學(xué)習(xí)，定義冠軍節(jié)點為，設(shè)某節(jié)點x被 p個模式選中為冠軍節(jié)點，其中p＝(′，，…，)，假設(shè)p足夠大，隨著學(xué)習(xí)次數(shù)增加，則第n次學(xué)習(xí)模式(∈p)，對節(jié)點x的權(quán)值wx更新的遞歸公式為：

節(jié)點x被迭代更新n次的最終權(quán)值為所有學(xué)習(xí)模式的平均值，即CCGAM對任意n個輸入模式的迭代學(xué)習(xí)過程是收斂穩(wěn)定的。學(xué)習(xí)算法針對模型一致的學(xué)習(xí)樣本時，學(xué)習(xí)結(jié)果是統(tǒng)計一致的?！?/p>

3.3.2計算復(fù)雜度

假設(shè)CCGAM神經(jīng)元規(guī)模上界閾值為Nmax，待訓(xùn)練的模式為x，x的標(biāo)簽為cx，s1、s2分別為cx中與x的歐式距離最近的神經(jīng)元節(jié)點和次近的神經(jīng)元節(jié)點，定義：

其中，d1＝‖ws1?x‖，d2＝‖ws2?ws1‖；Ncx是網(wǎng)絡(luò)中對應(yīng)標(biāo)簽cx的神經(jīng)元節(jié)點數(shù)。如果sgn(Ncx)值為1，x直接作為新的神經(jīng)元添加；如果sgn(Ncx)值為0，對s1的權(quán)值進行更新，ws1＝ws1＋?ws1，其中?ws1＝(x?ws1)/Ms1；如果sgn(Ncx)值為?1，找到標(biāo)簽為cx的子網(wǎng)絡(luò)中M值最小的神經(jīng)元節(jié)點并以1 M的概率刪除，再將x作為新的神經(jīng)元添加到cx。由此可知，在CCGAM記憶層，每個子網(wǎng)絡(luò)中神經(jīng)元數(shù)最多為預(yù)先設(shè)定的Nmax。

設(shè)一個集群的訓(xùn)練模式總數(shù)為M（M無限大），當(dāng)網(wǎng)絡(luò)中每增加一個神經(jīng)元，訓(xùn)練一個樣本模式所需增加的時間開銷為τ。對于CCGAM，訓(xùn)練前Nmax個模式時，網(wǎng)絡(luò)神經(jīng)元數(shù)是線性增加的，空間復(fù)雜度為O(n)，所需訓(xùn)練時間開銷關(guān)于訓(xùn)練樣本數(shù)呈二次函數(shù)增長；訓(xùn)練超過Nmax個模式時，由于網(wǎng)絡(luò)中神經(jīng)元規(guī)模已達(dá)到上界且不再增加，空間復(fù)雜度為O(1)，訓(xùn)練時間關(guān)于訓(xùn)練樣本數(shù)呈線性增加。對于GAM，每個訓(xùn)練樣本是否作為新的神經(jīng)元添加到網(wǎng)絡(luò)中且有一定的隨機性。假設(shè)GAM將每個訓(xùn)練模式作為新神經(jīng)元添加的概率為ρ(ρ＜1)，空間復(fù)雜度為O(n)，訓(xùn)練時間關(guān)于訓(xùn)練樣本數(shù)始終呈二次函數(shù)增長。CCGAM( T1)和GAM( T2)的訓(xùn)練時間隨著訓(xùn)練樣本模式數(shù)n的變化函數(shù)整理如下：

GAM、CCGAM訓(xùn)練時間關(guān)于訓(xùn)練模式規(guī)模的變化趨勢如圖4所示（其中a＝Nmax，γ＝ρ）。從圖中可知，對于單個學(xué)習(xí)樣本，其序號數(shù)等于a時，CCGAM的學(xué)習(xí)時間復(fù)雜度為O(n2)，當(dāng)序號數(shù)大于a時，學(xué)習(xí)時間復(fù)雜度為O(n)；而GAM的學(xué)習(xí)時間復(fù)雜度始終為O(n2)。當(dāng)學(xué)習(xí)樣本較大時，新學(xué)習(xí)一個樣本所需的計算時間，GAM要遠(yuǎn)大于CCGAM。

Fig.4 Training time on different sample number for GAM and CCGAM圖4　GAM與CCGAM訓(xùn)練時間關(guān)于訓(xùn)練模式數(shù)的變化關(guān)系

4　實驗研究

本文分別基于字母識別、性別判別和煙霧檢測問題對CCGAM的實際性能進行分析。實驗計算配置如下：內(nèi)存4.00 GB，CPU為Intel@CoreTMi5-3470，主頻3.20 GHz，操作系統(tǒng)為64位，程序開發(fā)環(huán)境為C++平臺、OpenCV和Boost程序庫。

Fig.5 Binary letters images圖5　二進制字母圖像

4.1字母識別

本實驗主要測試分析CCGAM模型的計算有效性、學(xué)習(xí)效率和聯(lián)想記憶性能。字母識別對象如圖5所示，有26個大寫字母和26個小寫字母，每個字母是一個7×7像素構(gòu)成的二值圖像，圖像是由黑點（-1）和白點（1）構(gòu)成，每個字母屬于一個類，共52個模式類。

本部分實驗中，首先對比分析GAM和CCGAM的學(xué)習(xí)效率和計算有效性。從每個原始字母圖像49個像素點中隨機選取10個點添加噪聲，將其原像素值更改為其相反值，如圖6所示，并分別重復(fù)100，150，…，1 000次，共生成19組含噪訓(xùn)練樣本作為訓(xùn)練集數(shù)據(jù)。針對上述19組訓(xùn)練集Di(i＝1，2，…，19)，分別使用GAM和CCGAM進行19次訓(xùn)練，訓(xùn)練完后對兩者進行一次增量學(xué)習(xí)，其中Nmax取值為10。圖7分別給出了CCGAM和GAM模型的子網(wǎng)節(jié)點數(shù)、訓(xùn)練時間及增量學(xué)習(xí)時間隨學(xué)習(xí)次數(shù)的變化關(guān)系圖。

Fig.6 Noise patterns generated from an original pattern圖6　對原始模式隨機加噪生成噪聲模式

圖7（a）是CCGAM和GAM在訓(xùn)練樣本逐漸增加的情況下，每個類在記憶層中產(chǎn)生的節(jié)點數(shù)。由于GAM每個類訓(xùn)練后記憶層產(chǎn)生的節(jié)點數(shù)并不一樣，實驗中統(tǒng)計的節(jié)點數(shù)是52個類的平均節(jié)點數(shù)。從圖中可以得出，CCGAM每個子網(wǎng)絡(luò)中節(jié)點數(shù)始終控制在10，而GAM隨著訓(xùn)練樣本的增加，節(jié)點數(shù)也逐漸增加，圖像中顯示GAM的節(jié)點數(shù)與訓(xùn)練樣本大致呈線性增加關(guān)系。

圖7（b）是在訓(xùn)練樣本增加的情況下，CCGAM 和GAM對每個類的訓(xùn)練時間變化趨勢曲線。由于CCGAM控制了網(wǎng)絡(luò)節(jié)點數(shù)增長，隨著訓(xùn)練樣本的增加，CCGAM的訓(xùn)練時間關(guān)于訓(xùn)練樣本數(shù)呈線性增長，訓(xùn)練時間復(fù)雜度為O(n)。而GAM的網(wǎng)絡(luò)節(jié)點數(shù)隨著訓(xùn)練樣本增加而不斷增加，其訓(xùn)練時間關(guān)于訓(xùn)練樣本數(shù)呈二次函數(shù)增加，復(fù)雜度為O(n2)。同時也證明了3.3節(jié)中關(guān)于兩者時間復(fù)雜度的理論分析。

進一步，仍基于字母識別問題測試分析CCGAM的異聯(lián)想能力。實驗中將大寫字母圖像作為線索模式，對應(yīng)的小寫字母圖像作為響應(yīng)模式，如A→a，B→b，…，Z→z，以這樣的模式對形式輸入網(wǎng)絡(luò)進行訓(xùn)練，并通過調(diào)整Nmax值比較不同節(jié)點數(shù)限定下的CCGAM異聯(lián)想學(xué)習(xí)性能。采取前述相似加噪方法對每個原始模式加噪生成每個類包含500個不同噪聲模式的數(shù)據(jù)集作為訓(xùn)練集D，同樣方法生成另一組只含線索模式的數(shù)據(jù)集作為測試集T。實驗中，固定訓(xùn)練集D，Nmax分別取值10，15，20，…，60，用算法2對CCGAM進行11組訓(xùn)練，每次訓(xùn)練完用算法4對測試集T進行測試，統(tǒng)計異聯(lián)想性能。由于GAM不能控制調(diào)節(jié)網(wǎng)絡(luò)中節(jié)點數(shù)，本實驗僅用訓(xùn)練集D和測試集T對GAM進行一次實驗，用式（1）計算GAM的平均節(jié)點數(shù)，實驗結(jié)果如表1所示。

Fig.7 Performance comparison of GAM and CCGAM圖7　GAM與CCGAM的性能對比

表1中的實驗結(jié)果表明，對于CCGAM，在網(wǎng)絡(luò)節(jié)點數(shù)限定較小時，增加網(wǎng)絡(luò)節(jié)點數(shù)，可以提高聯(lián)想準(zhǔn)確率，但當(dāng)節(jié)點數(shù)達(dá)到某一上界后，準(zhǔn)確率趨于穩(wěn)定。這一實驗結(jié)果表明，為取得實用有效的性能，記憶子網(wǎng)節(jié)點數(shù)僅需控制在某個問題相關(guān)的上界范圍內(nèi)，并不需要無限增大。對比表1中GAM與CCGAM性能可以發(fā)現(xiàn)，兩者在相近的子網(wǎng)節(jié)點數(shù)時，所取得的性能相當(dāng)，這也表明CCGAM的學(xué)習(xí)算法是有效且可靠的。

4.2性別判別

為了測試分析CCGAM在復(fù)雜實值型數(shù)據(jù)集中的性能，本實驗選用美國CTTP發(fā)起的人臉識別技術(shù)工程（FERET）所采集的通用人臉庫作為數(shù)據(jù)集，包括414張不同男性臉部圖像和309張不同女性臉部圖像。所有圖像均為80×80像素的標(biāo)準(zhǔn)TIF格式灰度圖，圖像人物包含不同的表情、姿態(tài)、種族和年齡，如圖8、圖9所示。

Table 1 Recalling performance obtained by GAM and CCGAM表1　GAM與CCGAM聯(lián)想記憶測試結(jié)果對比

Fig.8 Some female facial images圖8　部分女性臉部圖像

Fig.9 Some male facial images圖9　部分男性臉部圖像

首先，從數(shù)據(jù)集中隨機選取200張男性圖像和200張女性圖像作為訓(xùn)練集，剩余323張圖像作為測試集，用算法1訓(xùn)練，算法3進行測試，計算Nmax在不同取值下CCGAM的自聯(lián)想準(zhǔn)確率；然后再重新隨機抽取訓(xùn)練集和測試集，對應(yīng)每個Nmax值共進行n＝20次，用式（2）計算每個Nmax值對應(yīng)n次隨機抽取樣本的自聯(lián)想準(zhǔn)確率ratei(i＝1，2，…，n)；最后用式（3）統(tǒng)計每個Nmax值對應(yīng)的CCGAM平均聯(lián)想準(zhǔn)確率avg_rate。CCGAM在Nmax值分別取5，10，15，…，100時的平均聯(lián)想準(zhǔn)確率如圖10所示。

Fig.10 Accuracy changes with different nodes number on CCGAM圖10　CCGAM準(zhǔn)確率隨節(jié)點數(shù)的變化曲線

由圖10可以看出，Nmax值在0～20范圍內(nèi)時，CCGAM自聯(lián)想準(zhǔn)確率隨著Nmax值增加而提高較快；在20～50范圍內(nèi)時，CCGAM自聯(lián)想準(zhǔn)確率提高逐漸減緩；而當(dāng)Nmax值超過50時，CCGAM自聯(lián)想準(zhǔn)確率趨于穩(wěn)定。

為了進一步比較CCGAM的性能，表2給出了3種分類算法包括SVM[17]、OBVM[13]和GAM算法的實驗結(jié)果。實驗中，CCGAM節(jié)點數(shù)固定為50，在保持實驗條件不變的情況下，統(tǒng)計另外3種算法的各項性能指標(biāo)，包括節(jié)點數(shù)/支撐向量數(shù)（Ns/SVs）、訓(xùn)練時間（T）、一次增量學(xué)習(xí)時間（I）和準(zhǔn)確率（Accuracy），其中Accuracy是由式（3）計算20次實驗結(jié)果的均值。另外統(tǒng)計了準(zhǔn)確率方差，用來衡量準(zhǔn)確率的穩(wěn)定性。具體實驗結(jié)果如表2所示，加粗部分為每類結(jié)果的最優(yōu)值。

Table 2 Performance of CCGAM and other methods in gender recognition表2　CCGAM和其他方法在性別識別實驗中性能比較

由表2可以看出，和其他方法相比，CCGAM的網(wǎng)絡(luò)節(jié)點數(shù)、訓(xùn)練時間和增量學(xué)習(xí)時間均具有優(yōu)勢，其聯(lián)想準(zhǔn)確率稍低于SVM，但高于另外兩種方法。

4.3煙霧檢測

進一步選取煙霧檢測問題[23-24]作為實驗對象，評估CCGAM在實際問題上的應(yīng)用性能。煙霧特征具有很強的非線性特征，為更好地辨識煙霧與非煙霧，分類器通常需要對大量的不同場景特征數(shù)據(jù)進行學(xué)習(xí)。文獻[23-24]針對視頻煙霧檢測問題進行研究，提出了新的快速煙霧特征提取方法。此處同樣采用文獻[24]的視頻煙霧圖像特征提取方法。其中對任一分析區(qū)域塊，提取4個基本的煙霧飄動性特征量，再計算WT時間窗內(nèi)的均值和方差作為附加特征量，形成12維的煙霧特征。實驗數(shù)據(jù)集包含真實煙霧（正例）和非煙霧（反例）的特征數(shù)據(jù)共357 006個（正例221 191個，反例135 815個）。首先設(shè)置不同CCGAM節(jié)點規(guī)模上界閾值Nmax，分析其對識別性能的影響。實驗中，分別取Nmax＝200，400，…，2 000，共10組，每次對數(shù)據(jù)集隨機抽取80%共285 605個特征數(shù)據(jù)作為訓(xùn)練集Di，20%作為測試集Ti，用式（2）計算聯(lián)想準(zhǔn)確率（Accuracy），并統(tǒng)計對應(yīng)的訓(xùn)練時間（T）和增量學(xué)習(xí)時間（I），實驗結(jié)果如表3所示。從表3中可知，隨著Nmax增加，CCGAM的訓(xùn)練時間T和增量學(xué)習(xí)時間I均會增加，而聯(lián)想準(zhǔn)確率當(dāng)Nmax在200～ 1 600范圍內(nèi)時會提高，超過1 600后基本保持穩(wěn)定。

Table 3 Smoke detection performance with different Nmax表3　Nmax對煙霧檢測的性能影響

進一步，將CCGAM節(jié)點數(shù)設(shè)為1 600，與SVM、OBVM和GAM的煙霧檢測性能進行對比。其中對4種算法的網(wǎng)絡(luò)節(jié)點數(shù)/支撐向量數(shù)（Ns/SVs）、訓(xùn)練時間（T）、增量學(xué)習(xí)時間（I）和聯(lián)想準(zhǔn)確率（Accuracy）進行了統(tǒng)計，T和I反映了算法的計算效率，實驗結(jié)果見表4，對最優(yōu)結(jié)果作加粗顯示。分析可知，和其他3種方法相比，CCGAM僅需最少的節(jié)點數(shù)和最小的訓(xùn)練時間、增量學(xué)習(xí)時間，獲得了與其他3種方法相當(dāng)?shù)穆?lián)想性能。

Table 4 Smoke detection performance of CCGAM and other methods表4　CCGAM和其他方法的煙霧檢測性能對比

綜合表3、表4可知，CCGAM能夠較好地適用于大規(guī)模增量樣本學(xué)習(xí)，且可以根據(jù)應(yīng)用問題自身特點調(diào)整Nmax，使得模型在保持較高性能的前提下僅需較低的計算資源。綜合地，相比現(xiàn)有的支持增量學(xué)習(xí)的通用計算模型，CCGAM具有較明顯的計算效率優(yōu)勢，并保持較高的模型性能。

5　結(jié)論與展望

為適應(yīng)大數(shù)據(jù)學(xué)習(xí)要求，聯(lián)想記憶算法不僅要求有較高的聯(lián)想準(zhǔn)確率，而且要求有較高的計算效率。本文提出了一種容量約束的自組織增量聯(lián)想記憶模型（CCGAM），針對大規(guī)?？蓪W(xué)習(xí)樣本，新模型能夠在網(wǎng)絡(luò)神經(jīng)元數(shù)量可控的方式下實現(xiàn)增量學(xué)習(xí)，極大地提高了樣本模式的學(xué)習(xí)效率。CCGAM可避免GAM存儲容量過大和初值敏感問題，并能取得較高的聯(lián)想性能。實驗結(jié)果表明，將節(jié)點數(shù)控制在較小范圍后，新模型仍能得到較好的聯(lián)想準(zhǔn)確率，而其在計算效率和內(nèi)存開銷上明顯優(yōu)于GAM和其他傳統(tǒng)算法，這為聯(lián)想記憶在大數(shù)據(jù)學(xué)習(xí)背景下的應(yīng)用提供了一種新的解決方法。

雖然如此，文中所研究的聯(lián)想記憶模型沒有涉及模式特征學(xué)習(xí)問題，而是直接基于原始模式數(shù)據(jù)或已提取的特征數(shù)據(jù)作為輸入模式，這在一定程度上限制了新模型的廣泛適用性，這也將是下一階段的重要研究方向。

References:

[1] Michel A N, Farrell J A. Associative memories via artificial neural networks[J]. IEEE Control Systems Magazine, 1990, 10(3): 6-17.

[2] Haykin S. Neural networks[M]. Beijing: Tsinghua University Press, 2001.

[3] Wu Xiaojun, Zhang Yuanyuan, Wang Shitong, et al. Improved fuzzy neural network and its application to face recognition[J]. Micronano Electronic Technology, 2007, 44(7): 465-469.

[4] Ozturk M C, Principe J C.An associative memory readout for ESNs with applications to dynamical pattern recognition[J]. Neural Networks, 2007, 20(3): 377-390.

[5] Itoh K, Miwa H, Takanobu H, et al. Application of neural network to humanoid robots—development of co-associative memory model[J]. Neural Networks, 2005, 18(5): 666-673.

[6] Hopfield J J. Neural networks and physical systems with emergent collective computational abilities[J]. Proceedings of the National Academy of Sciences, 1982, 79(8): 2554-2558.

[7] Azuela J H S. A bidirectional hetero-associative memory for true-color patterns[J]. Neural Processing Letters, 2008, 28(3): 131-153.

[8] Zhou Zhihua, Chen Shifu. Neural network ensemble[J]. Chinese Journal of Computers, 2002, 25(1): 1-8.

[9] Namarvar H H, Liaw J S, Berger TW.Anew dynamic synapse neural network for speech recognition[C]//Proceedings of the 2001 International Joint Conference on Neural Networks, Washington, USA, Jul 15-19, 2001. Piscataway, USA: IEEE, 2001, 4: 2985-2990.

[10] Chung F, Lee T. On fuzzy associative memory with multiplerule storage capacity[J]. IEEE Transactions on Fuzzy Systems, 1996, 4(3): 375-384.

[11] Carpenter G A, Grossberg S. A massively parallel architecture for a self-organizing neural pattern recognition machine[J]. Computer Vision, Graphics, and Image Processing, 1987, 37(1): 54-115.

[12] Yu Cui, Zhang Rui, Huang Yaochun, et al. High-dimensional kNN joins with incremental updates[J]. Geoinformatica, 2010, 14(1): 55-82.

[13] Zhao Peilin, Wang Jialei, Wu Pengcheng, et al. Fast bounded online gradient descent algorithms for scalable kernel-based online learning[J]. arXiv: 1206.4633, 2012.

[14] Yang Haifeng, Liu Yuan, Xie Zhenping, et al. Efficiently training ball vector machine in online way[J]. Journal of Computer Research and Development, 2013, 50(9): 1836-1842.

[15] Mininno E, Neri F, Cupertino F, et al. Compact differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 32-54.

[16] Kosko B. Bidirectional associative memories[J]. IEEE Transactions on Systems, Man and Cybernetics, 1988, 18(1): 49-60. [17] Wang Min, Wang Shitong, Wu Xiaojun. Initial results on fuzzy morphological associative memories[J]. Chinese Journal of Electronics, 2003, 31(5): 690-693.

[18] Ritter G X, Sussner P, Diza-de-Leon J L. Morphological associative memories[J]. IEEE Transactions on Neural Networks, 1998, 9(2): 281-293.

[19] Wilamowski B M. Neural networks and fuzzy systems[J]. Mechatronics Handbook, 2002, 33(1): 32-26.

[20] Forster K, Monteleone S, Calatroni A, et al. Incremental kNN classifier exploiting correct-error teacher for activity recognition[C]//Proceedings of the 9th International Conference on Machine Learning and Applications, Washington, USA, Dec 12-14, 2010. Piscataway, USA: IEEE, 2010: 445-450.

[21] Furao S, Hasegawa O. An incremental network for on-line unsupervised classification and topology learning[J]. Neural Networks, 2006, 19(1): 90-106.

[22] Shen Furao, Ouyang Qiubao, Kasai W, et al. A general associative memory based on self-organizing incremental neural network[J]. Neurocomputing, 2013, 104: 57-71.

[23] Wang Tao, Liu Yuan, Xie Zhenping. Flutter analysis based video smoke detection[J]. Journal of Electronics and Information Technology, 2011, 33(5): 1024-1029.

[24] Xie Zhenping, Wang Tao, Liu Yuan, et al. A fast video smoke detection algorithm by analyzing fluttering[J]. Microelectronics and Computer, 2011, 28(10): 209-214.

附中文參考文獻：

[3]吳小俊,張媛媛,王士同,等.改進的模糊神經(jīng)網(wǎng)絡(luò)及其在人臉識別中的應(yīng)用[J].微納電子技術(shù), 2007, 44(7): 465-469.

[8]周志華,陳世福.神經(jīng)網(wǎng)絡(luò)集成[J].計算機學(xué)報, 2002, 25(1): 1-8.

[14]楊海峰,劉淵,謝振平,等.球向量機的快速在線學(xué)習(xí)[J].計算機研究與發(fā)展, 2013, 50(9): 1836-1842.

[17]王敏,王士同,吳小俊.新模糊形態(tài)學(xué)聯(lián)想記憶網(wǎng)絡(luò)的初步研究[J].電子學(xué)報, 2003, 31(5): 690-693.

[23]王濤,劉淵,謝振平.一種基于飄動性分析的視頻煙霧檢測新方法[J].電子與信息學(xué)報, 2011, 33(5): 1024-1029.

[24]謝振平,王濤,劉淵,等.一種飄動性分析的視頻煙霧快速檢測新算法[J].微電子學(xué)與計算機, 2011, 28(10): 209-214.

SUN Tao was born in 1991. He is an M.S. candidate at School of Digital Media, Jiangnan University. His research interests include machine learning and computer vision.

孫桃（1991—），男，安徽全椒人，江南大學(xué)數(shù)字媒體學(xué)院碩士研究生，主要研究領(lǐng)域為機器學(xué)習(xí)，計算機視覺。

XIE Zhenping was born in 1979. He received the Ph.D. degree in light industry information technology and engineering from Jiangnan University in 2008. Now he is an associate professor at Jiangnan University. His research interests include machine learning and cognitive computing.

謝振平（1979—），男，江蘇常州人，2008年于江南大學(xué)輕工業(yè)信息技術(shù)與工程專業(yè)獲得博士學(xué)位，現(xiàn)為江南大學(xué)副教授，主要研究領(lǐng)域為機器學(xué)習(xí)，認(rèn)知計算。

WANG Shitong was born in 1964. He is a professor at School of Digital Media, Jiangnan University. His research interests include artificial intelligence, pattern recognition and bioinformatics.

王士同（1964—），男，江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域為人工智能，模式識別，生物信息。

LIU Yuan was born in 1967. He is a professor at School of Digital Media, Jiangnan University. His research interests include network security and digital media.

劉淵（1967—），男，江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域為網(wǎng)絡(luò)安全，數(shù)字媒體。

Self-Organizing Incremental Associative Memory Model under Capacity Constraint*

SUN Tao, XIE Zhenping+, WANG Shitong, LIU Yuan
School of Digital Media, Jiangnan University, Wuxi, Jiangsu 214122, China
+ Corresponding author: E-mail: xiezhenping@hotmail.com

SUN Tao, XIE Zhenping, WANG Shitong, et al. Self-organizing incremental associative memory model under capacity constraint. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：130-141.

Abstract:Due to the advantages of self-organizing neural network like parallelism, fault freedom and self-learning, it has been widely used all over the place. However, in traditional associative memory neural networks, the number of network nodes will unlimitedly grow when they incrementally learning more and more samples, which inevitably leads to an unaffordable overhead of computation and storage. To solve this problem, this paper proposes a self-organizing incremental associative memory model under capacity constraint. By limiting the number of network nodes and introducing a self-competition strategy between network nodes, new model is capable of incrementally learning large-scale samples and can gain equivalent associative memory performance only requiring lower computing demand. The reasonability of model is proved by theoretical analysis. Moreover, the experimental results demonstrate that new model can effectively control computing consumption, improve the efficiency of incrementally learning new samples, and obtain comparative associative memory performance, which may preferably satisfy the demands of many practical applications.

Key words:associative memory; capacity constraint; incremental learning; self-organizing; neural network

文獻標(biāo)志碼：A

中圖分類號：TP18

doi:10.3778/j.issn.1673-9418.1505007