Զѧ
ACTA AUTOMATICA SINICA
1997ꡡ236ڡVol.23No.61997




һЧѧϰ㷨
ѧ¡ῡ
ժҪһµģ͵Чѧϰ㷨ص㣺(1)ȫ洢ѵģʽѵģʽĿ֮Եǿûƣ(2)Сѵģﵽ(3)(2)Ļϣÿѵģʽоܴ(4)ȫȶ.ļʵ˵ѧϰ㷨㷨иǿĴ洢ݴ.
ؼʡ磬ѵģʽȫ洢ȫȶ.
AN EFFICIENT LEARNING ALGORITHM FOR ASSOCIATIVE
MEMORY NEURAL NETWORK
LIANG XUEBINWU LIDEYU JUN
(Dept.of Computer ScienceFudan University,Shanghai200433)
AbstractA new and efficient learning algorithm of asociative memory neural network is proposed,with the following characteristics:(1)it can store any given training pattern set no matter how much and what correlation among them may be;(2)the smallest domain of attraction of training patterns is maximized;(3)each domain of attraction of training patterns is guaranteed to be as large as possible;(4)the designed associative memory network is globally stable.A large number of computer experimental results confirm that our algorithm possesses more powerful storage ability and more fault-tolerance capability than existing ones.
Key wordsAssociative memory,training pattern set,total storage ability,maximized domain of attraction,global stability.
1
ɷΪԷԷģͣϢϢĹܣܹӲϢʵϢӦĴ洢еļϢ12.Ҫɾѧϰ㷨.
Ѿ˲ٹѧϰ㷨ҪHebbianѧϰ㷨3ݡͶӰѧϰ㷨4ݡGardnerѧϰ㷨5ݡСصѧϰ㷨6ݡHo-Kashyapѧϰ㷨7ݡԪѵģʽȨѧϰ㷨8ݺŻѧϰ㷨9ݵ.ֻŻѧϰ㷨ϸĴ洢ݴ.
ף9ݵ˼룬ļС׼ҪƳĶԳȨӦʹСļģʽﵽ.һչۺһЧѧϰ㷨ص㣺(1)ȫ洢ѵģʽ(2)Сѵģʽﵽ(3)(2)Ļϣÿѵģʽоܴ(4)ȨԽԪΪ1ĶԳƳȫȶģ11.
2ԷģѵʽĻԼ
ģNԪɵķԶϵͳ.״̬v=(v1,,vN)tvi(i=1,2,,N)ʾiԪ״̬ȡֵռ{-1,1}ȨW=(Wij)NN,WijʾӵjԪiԪȨ.ģͿɱΪ1
(1)
vi=(v1,,vN)tʾһʱ̵״̬Ժsgn(x)Ϊx0ʱΪ1x<0ʱΪ-1.
ȨWWij=Wji(i,j=1,2,,N)Wii=0(i=1,2,,N)ȨһԽǵʵԳΪHopfield1.
Mͬѵģʽx1x2,xMxu=(xu1,,xuN)t,u=1,2,,M.ǳΪϵͳ(1)ȶӵȼڶu=1,2,,M
(2)
ף11֤HopfieldĴ洢NκMM>NһMѵģʽǲͬʱHopfieldȶ.
ڵĽǣʹMNMͬѵģʽͬʱΪHopfieldȶӣ»Լ(Fundamental Constraint,FC)ͬѵģʽͬ.Ȼĳͬѵģʽպֻһͬ.HopfieldԷѵģʽȻͬһѵģʽͳì.
Щѵģʽķĳģʽ纺֡͡񡱣ѡ͡.ˣԼ(FC)ӳHopfieldڴ洢ľ.
²ȨԽʵԳΪԷHopfield磬ȨǾзԽԪʵԳΪԷHopfield.ԷHopfieldԴ洢ѵģʽ4ݣʵʹÿѵģʽо.
3ȶӺݴԷ
HopfieldȨHebbianѧϰ׼ȷ
(3)
Hebbianѧϰ׼ҪΪģ繤ԭģ3ݣǴ˹Ĺ׼.ֻܴͨ洢Խѵģʽ.
1.Mͬѵģʽx1,x2,,xMΪϵͳ(1)ȶӵĳǶu=1,2,,M
(4)
2.xu(u{1,2,,M})ϵͳ(1)һģʽxһģʽH(x,xu)ʾxxu֮Hamming.H(x,xu)<Fui/(2Wmi),i{1,2,,N},xһxui.
֤.Ҫ֤xi=xui.õʽһ
(5)
ע⵽(6)
ڡ
(6)ʽá
Ӷʽ(5).֤.
Ϊдͽۼ࣬ҲӰ۵ʵʣĺٶi=1,2,,N,Wij(j=1,2,N)ȫΪ0Wmi=1.FuiֵԽxuĵiݴԾԽǿ.ƵĶҲɲοף612.
 (7)
1.xu(u{1,2,,M})ϵͳ(1)һģʽxһģʽ.H(x,xu)<Fu/2һxu.
1֪Fu/2Ǽģʽxu뾶һ½.
4С׼ѧϰ㷨
衡(8)
F/2Сļģʽİ뾶һ½.
ѧϣС׼ɱʾΪԼ΢Ż

(9)
arg maxԼWij=Wji,ңWij1;i,j=1,2,,N.
(9)ʽеWij(i>j;i,j=1,2,,N)仯WjiԼ΢Ż⺬N(N+1)/2ɱWijarg maxԼǣWij1.ˣԼ΢Ż(9)ȼԹ滮⣺
(P)max(z),(10)
Լ
(C1)Fuiz,i=1,2,,N;u=1,2,,M;(11)
(C2)Wij1,ij;i,j=1,2,,N.(12)
Թ滮(10)(12)õη.ڵηԽϸӣرNMȽϴʱ.ΪˣĽЧļ򵥷.
ֶ(9)ʽ
(13)
еڶȺFuiֻWij(j=1,2,,N)йصʵͷֱʾԼ(C2)(C3)ֵ(C3)Ϊ
(C3)Wij1,j=1,2,,N.(14)
min(a+b)min(a)+min(b)(abǱ)(13)ʽ
(15)
֪ԼŻ
(16)
Ľ
(17)
ɲʽ(15)֪(17)ʽǲ΢Ż(9)ʽһŽ.
HopfieldȨ(17)ʽȷùͳΪѧϰ㷨.ص㣺
1)Դ洢ѵģʽҾһݴ13ݣ
2)ԼŻ㷨ĳֵ
3)ƳȨֵΪ-101رǣԽȨԪȫΪ1Ӳʵֺ͹ѧʵ.
fԹ滮(10)(12)Ľ.Թ滮(10)(12)ȼԼ
(C4)Wij1(i<j;i,j=1,2,,N)(18)
Բʽ顡Fuif(i=1,2,,N;u=1,2,,M); (19)
ԼԲʽ(19)ø֪㷨14.
ѵģʽѧϰx1,x2,xM,,x1,x2,,xM,,һѭѧϰ.֪㷨ѭ˳ѵģʽxu(u{1,2,,M})Ұй޸Ȩi=1,2,,N
(20)
t㷨q>0Wijĵֵѡ.
ΪʹÿѵģʽһСڸ֪㷨(20)Լ(C4).ͬʱѧϰ㷨(17)ĽΪȨĵֵֻԳֵΪ0ķǶԽȨԪؽŻ.ڴ˻ϣʹÿѵģʽо.
ĵԼ֪Żѧϰ㷨ܽ£
(1)ʼ.Wij(0)(i<j;i,j=1,2,,N)ɿѧϰ㷨(17)ȷf(0)=1,ѡȡѧϰq1ͦ2
(2)ѧϰ.ѭѧϰx1,x2,xM,,x1,x2,,xM,,ܵѵģʽxu(u{1,2,,M}i=1,2,,Nʽ޸Wij(t)(i<j;j=1,2,,N)
(21)
к(x)Ϊx>1ʱΪ1x<-1ʱΪ-1Ϊx.ÿһѭ{x1,x2,,xM}ͳΪһΣ
(3)ж.㷨(21)Fuif(i=1,2,,N;u=1,2,,M)ʱĵСڦ1f=f+1ת(2)㷨(21)1ԲWij㷨(21)ʽ֮ǰֵת4
(4)ÿѵģʽ.fu=f,u=1,2,,M.ѭѧϰx1,x2,xM,,x1,x2,,xMܵѵģʽxu,u{1,2,,M}i=1,2,,Nʽ޸Wij(t)(i<j;j=1,2,,N)
(22)
ÿһѭ{x1,x2,xM}ͳΪһ.
ÿһΣҵСڦ2ʱu=1,2,,M¹fuFuifu(i=1,2,,N)Fuifu-1(uu,u=1,2,,M;i=1,2,,N),fu=fu+1ҵ´0ʼز(4)
㷨(22)ʽڵ2fu(u=1,2,,M)Wij㷨(22)ʽ֮ǰֵ㷨.
5ʵ
ʵȡq=1/N1=2=40.
(23)
Fmax,FminFaveͳ͹۵Hopfieldѧϰ㷨ݴ.Fmax,FminFaveԽ˵㷨ݴԽǿ.
һʵѵģʽǺ֡ѡ͡ȡͼ1ʾ.ÿѧϰ㷨Լѵģʽ.Hebbianѧϰף9ݵŻѧϰ㷨ܴ洢ѵģʽ.Ϊ͡ѡԼ͡ȡHammingΪ1.ʵHebbianѧϰ3ѵģʽ뵽ģʽ.1ǿѧϰ㷨ͱŻѧϰ㷨ݴȽ.ɱ1֪ѧϰ㷨ͱŻѧϰ㷨ڴ£ͬݴ.

ͼ1ʵ1ѵģʽ
1㷨ݴȽ
FmaxFminFave
ѧϰ㷨98.001.0096.06
Żѧϰ㷨98.001.0096.06

ڶʵѵģʽӢĸAHͼ2ʾ8ѵģʽ{A}{A,B},{A,B,C},{A,B,C,D},{A,B,C,D,E},{A,B,C,D,E,F},{A,B,C,D,E,F,G}{A,B,C,D,E,F,G,H}ֱñŻѧϰ㷨ף9ݵŻѧϰ㷨ѧϰ.2Żѧϰ㷨ݴȽϣMʾ8ѵģʽֱģʽ.ɱ12Ľ֪Żѧϰ㷨ף9ݵŻѧϰ㷨иǿݴͬʱ˵ѧϰ㷨ĽΪ㷨ĳֵɴߵ㷨ݴ.

ͼ2ʵ2ѵģʽ
2Żѧϰ㷨ݴȽ
M12345678
Fmax()10057.0049.7840.4736.0636.2833.6230.38
Fmax(ף9)9942.5634.6314.7014.8314.8314.4117.88
Fmax(㷨)10057.0042.0038.0033.0033.0031.0027.00
Fmin()10043.0033.3414.0814.1913.8311.0812.02
Fmin(ף9)9942.0032.0313.0413.0811.0010.0110.01
Fmin(㷨)10043.0015.001.001.001.001.001.00
Fave()10050.9840.5125.7822.2221.8419.6317.66
Fave(ף9)9942.3232.7713.7513.8111.8610.9411.00
Fave(㷨)10050.9829.2622.5815.3814.1212.029.56

߼飺ѧ19971»񸴵ѧרҵʿѧλ.ִ¼оڹѷ30ƪ.
¡ѧѧϵڣʿʦ.¼Ӿͼѧоѷ100ƪಿ.
ᡡѧѧϵоҪѧϰӾͼ.
ߵλѧѧϵϺ200433
ο
1ݡHopfield J J.Neural networks and physical systems with emergent collective computational abilitie,In:Proc.Natl.Acad.Sci.,U.S.A.,1982,79(4):25542558.
2ݡMichel A N,Farrell J A.Associative memories via atrificial neural networks.IEEE Control Syst. Mag.,1990,10(4):617.
3ݡHebbian D O.The organization of behavior.New York:Wiley,1949.
4ݡPersonnaz L,Guyon I,Dreyfus G.Collective computational properties of neural networks:new learning mechanisms.Phys.Rev.A,1986,34(5):42174228.
5ݡGardner E.The space of interactions in neural network models.J.Phys.A:Math.Gen.,1988,21:257270.
6ݡKrauth W,Mezard M.Learning Algorithms with Optimal Stability in Neural Networks.J.Phys.A:Math.Gen.,1987,20:745752.
7ݡHassoun M H,Youssef A M.High performance recording algorithm for hopfeild model associative memories.Optical Eng.,1989,28(1):4654.
8ݡWang T,Zhuang X H,Xing X L.A neuron-weighted algorithm and its hardware implementation in associative memories.IEEE Trans.Computer,1993,42(5):636640.
9ݡWang T.Learning of Hopfield associative memory by global minimization.Int.J.Pattern Recog.Artif.Intell.,1993,7(3):559567.
10ݡAtiya A,Abu-Mostafa Y S.An analog feedback associative memory.IEEE Trans.Neural Networks,1993,(4):117126.
11ݡGoles E.Fogelman F,Pellegrin D.Decreasing energy functions as a tool for studying threshold networks.Discrete Appl.Math.,1985,12:261277.
12ݡAbbott L F,Kepler T B.Optimal learning in neural netwrok memories.J.Phys.A:Math.Gen.,1989,22:711717.
13ݡѧ.ۺȡ׼.ͨѧ199516(2)16.
14ݡTou J T,Gonzalez R C.Pattern recognition principles.Massachusetts:Addison-Wesley,1977.165168.
ոڡ1994-12-25
