对Hopfield神经网络的直接数学分析_英文_.pdf

军 10 期 19 92年10月 电子学报 人 C T AE L ECT R ON IC人SIN IC人 V ol 2 0 O et 饨10 1092 AS r aigh 于 o rwa rd M a t卜 ema ie a lA na l ysis 于 or 卜 e H op 于iel dN eura l N etwork 对H叩f i e l d神经网络的直接数学分析 食 Xi angsu n Z ha ng H ong 芬 e ng Li Xi ao do ng W a ng In stitute o fAp plied M athematies Chin e seA e adem 丫 of Seie n e e B eijing 100080 二 Abs七 r et In steadofu singstatistiealnatu re teehniqu es whieh a re in n e ural s n a o etwo rkanalysis u nderstandingof straightforward m athematiealanalysis 15de veloped this PoPular P压Per t0 proPe rties ofthe H opfieldn etwo rk whe nit15 Us ed stored a C AM By Promote in troduc ing aeon e ePtofn on一rthogon al deg re e d ofa 户一et n 一binary thenetwork 1 e the m aximumn um be rofstablestored Patte rns 15 p atte r n s theeapaeityof n d l in the w o rstease andthestability deg re e 无 a qu antityde seribing ther adiu sof 15 Po sitivelyProPo rtio nalto n一P一 P一 1 J a nd in ve rs elyProPortio nalto 户 e o nverge n ee ba sin Con eePtsofa sso eiative Pat tern andspuriou s patte r n a reeo nsidered Abo utspu rio u s patte r n s w e ha ve Pr o ved 李 that l in m c C一 S gn 急 a P a re pu riou patte r n s w he re a 任f l 一 l 拼 K ywo rds H opfieldn etwork Capa eity A sso eiative patte r n s Spu riou s pattern s 提典 本文不是使用一般常用 的统计技术 而是直接采用数学方法对神经网络进行分析 以便对Ho Pf i e l d网用作C人M时的性质有更进一步的了解 通过引进p个 n 维存储模式之间的非正交 度d的概念 给出了网络的容t 即德定的存储向t的最大数目 在最坏的情形下是 n d d l 而描述收敛盆半径的t 稳定度护 则正比于 n一P一 户一l d且反比于p 本文考察了相 关 式和伪 式的二关于伪模式 证明了在某种条件下s s n 急 恤 伪模 式 其 中 f l 一 11 拌二1 户 关健词 H opfield网 容是 相关模式 伪模式 岁 1 I ntro du et io n Inm any e autho rs oPinio ns a ss o eiativ e storageandr e e allof info rm T 五e a s s oeiativ e m emory m odelore o nt ent一addre s sable z n emory CAM w as Pr oPo ed byKoho n e n A nderso n 幻 N aka no A m a ri Ja nd m a nyothers Itha s e n j oyed 名r e atpoPula rity sine e H opfield drew the 名n alog yto Physie al spinsystem s m emory ation by a s so eiation w ith othe r info rmatio n M anuse riptr e e eiv ed Feb 1992 aeeepted M a丫 1092 T hi r e se a reb 15 su p po rtedby the N atio n al N atu re Seien CeFOu ndatiQn 二章祥荪 李宏峰 王晓东 中国科学院应用数学 研究所 北京100080 第 1 0 期 章祥荪等 对Ho Pf ie l d神经网络的直接数学分析 1l 套 15 the simplestap plie ationof eo lle ctive e omPutatio nonan e u raln etwork but as yet ago odthe oretiealunde rsta nding fo ritsbeha vior ha sn ot bee n reached In thisPaPerwe us estr aightforwa rd m athematieala n alysis in stead ofpoPula rstatistiealnatu re m ethod to dise uss the eaPa eityofthe H opfieldnet w orkandothe rrelated Problems TheHoPfield networke o nsistsof Pa irw ise e on n比tedneurons T hei一th ne u ro n ea n bein o n eoftwostates y 一 1 or l 二 l then define the statee olumnveeto r y to be an一dime nsio nal binaryve eto r who se i一th e omPon e nte o rresPonds tothe state ofthe i一th neu ro n Let 势 1 be thestr e ngth ofthe syn aptie eonn e etio n from n e uro n 1 to n e u ron i 协11 妙川势 0 In this pa卜 er w esimPlifythe m odel bysetting theth re sholdvoltageofe v eryn e uro n to be zero Iti r ea so nable whe n the n etwork 15 u s ed as C AM but15 note ssentialto m athemati ealanalysis Let W be annxnze ro一diago n alsym m etrie m atrix w hos e e ntriesa r e the妙11 defined abo v eand w be itsi一th row T he n the n etworkstarts in a n initial stateand r u ns with the follow ingdyn a m ie equatio n s Wh enthe H opfieldn etwo rk 10 u s edas CAM letyl 一 be a P一et ofn一dim e nsion al binarye olumnveeto rs w hieh a re to be stor ed W ealsoe all these v e etorsthe m emoriesorPatterns W e form a nnxn m atrix W 君二 一1 3 for e a eh patte r ny召 wherel de no te sthe nxn ide ntitvm atrix a ndthes upe rs e ript T de n otes tran sPo s etoarowveeto r N ow fo r the setof 户pattern s 1 一 w eean defin ethe H oPfieldeon n e etio n m atrix in 2 a s 二 上 自w 上自 一之2 n 邵一玉 n 翻一l 4 o r m ore Pre eis ely I D I二土自 兮片 5 像 协 一l 0 Equ atio n 2 andasynehro n ous r U nIn i笋i both Proeedu res as a nonlin e a r m aPPing synehron ou s be viewed n 一dime n si o nal b in a rysPaee S interesting Problem tO from itself the n the fir st 15 to finditsfix edPoint orstab le patte rn in thesPae esatisfying sgn w r 宁 sgn w W ee a n putthisprob lem 6 in the follow 一 1 sgn W t 艺 手 1 n 1 尹 几 n g 准 l sgn W 2 whe r e thesgn fun etio n oPerate son the v ee to r W y e ompo ne ntwis ea nd 15 the de s e rete tim e inte rval 0 1 In thispaP e r we s etsgn 0 1 The e x aetnatureof thisproeess 15 va ryinga e e ording to w hethe r ana synehro nou supdate Pro e edure orasyn ehron o u s pro e edu r e 15being used In syneh ronou sProe edure eaehofthe n eurons51 m ulta n eouslyevaluate sandupdate s its state ae e o rding to equatio n 2 In a synehr onous Proeedu re thee omPo n e ntsofthee u rrent veeto r y t a reuPdatedoneata time ae c ording to l toProduee anewstateveetor ingdiffe rent w ay given 户pa tte r n s l find a eonneetion m atrix W m akin g th e s epatte rn sto be stableu nde rthe m aPping sgn W This15 aetu all丫a pr oblem con ce rn ed in the CAMle a rning r ulee o n stru etio n Aw el l一knownobservatio n 15 thatif I a re m utu allyorthogo nal the nyl s atisfy 6 Aw e ak definitio n for the eaPaeityof the H oPfieldn etwork 15 De干i nition l田 T he eapaeity 户 15 the m a x im um n um b er of fix ed Points orstablestored patte r ns then etworke a n ha v eby appropriatelye on strueting its e on ne Ction m atrix In this se n se it15known thattheea P aeity 15户 2几by anum be rof inte r e sting l2电 子 学报 1992年 butd iffe rentm etho ds 一1 1J Som eauthors ha ve ehos e na m o r ee omPle xe o n n e etion m atr ix tban W in 4 to r e aeh thema ximum ea Pa eity su ehas spe etra l sehemes explo r ed byV enkate shand Psaltis 0 and D em bo 1 1 a s follow s W Y Y Y 一IY 7 w he r ey 1 In the e a seon e ha s W 忍 l 户 a s long a s J 5 ar e lin ea rlyindePende nt Butm o st PaPe rs e o n sider the eaPaeity ofthe H oPfieldnetwo rk in te rmsofa m od ified versionof definitio n l that15 find the m aximumnum be r of fix ed Points a H oPfield network w ith aspe eifiede o n n eetion m atrix e a n have In theea s eof 4 or 5 the observ ation m entionedabo v e the adva ntage of m utu allyorthogon alstored patte r n s tosa tisty equation 6 plays ave ry importa nt role in the r e 吕ea reh for e aPa eity Se v e r al a uthors 1 1一盈 ha ve a rgu ed thatif 15 m u eh l a rge r than P and 君 5 aree五os e nra ndom ly p re e isely the e ompon e ntsof 召ar e deter min ed random ly a nd indePe nde n tl y tobe eq u t r 一 W th r ob b t 合 the the r e 15 a highprobability thatthe 5 will be n e a rlyorthogo nal and fu rther a high pr obability thatthe 君 5satisfyequ atio n 6 But asPointedout bythe authorsof 12 theweak eaPaeity definitio n15 n otv eryu s e ful be eau s eitm e ans that thenetwork 15 m er elyable to reme垃ber thethings w hieh ar estored but a sanass o eiativ e m emo ry w e wa ntsomee r ror一e o rreetingo r Pull一in ProPe rty In ot her w ords the storedPatter ns a s fix ed Points orattraetorsofthe m apPing n e ed tohave a ba sin ofattraetion with non z e r orad ius in te rms ofthe H am mingdist anee H e r e the H am mingdistan e e oftwo Pa tte r n s15the num be rofbits in thesetwoPat ter nsw hieh do n ot m ateh Thenw e ha ve thefollowins strong definitionfo rtheeapa eityofthe H opfiel dn etwork D e于 ini 七io n2 The eaPa eity p of a H oPfield network w ith sPe eified W 15 the m ax im umnum be r ofstored Pat te r nsthat h av e d esir ed basins of attr a etio n Be side s a bove e apa eity definition s w hieh are imPo rtan t fo rdise u s sio n ofn etwork s e apa eity thea utho rsof 12 also d ise u ssed eo n ve rgenee beha vio rsof an input unde r the n etwo rk dyn am ie s T heyindie atedthat the r e areat Iea stthr e e Possibilities ofeo nve rgen e e in the a syn ehron ouseas e w hieh c o rr e sP ondtothr e e definition softhe ba sin ofat traetio n Firstly if a n input ve etor fallsinto the ba sin ofattraetionofastored Pattern the n itsi一th eompo n e nt w ill be ehangedto the eo rr esPo ndinge omPon e ntvalueof the stored Pat te rn afteron eupdate by l W e eallthis kind of basin ofattraetiona n i们 m ediatee on v e rge n e e ba sin oron e一tepeo n ve rgen e e ba sin In the e aseofsynehro nou s Proe edu re w ith thisbasin definitio n thein Putgo e sto thestor ed patter n in o n e teP Se e o nd ly fo ra n inPutfall ingin a ba sin of attr aetion ittake s m o r e than o n esteP both in thesynehrono usa ndasyn ehr o n ou s Pro eedure to 90 to the stored Patte r n The thirdon e 15m or es oPhistieated w e wil l n ot m ention ithe rebe ea u s e itha s n oeo n e e r n with o ur dis e u ssio n B ased on the def initio n ofthe ba sinof attraetion the a uthor s of 12 Pr e se ntedthe follow ingm ainr esults l Cho o sesto r ed Pattern s atra ndom Ifd efinitio n 215 u seda nd let r be the ra diu s ofthe b asin ofattraetio n a ndthe first tyPe ba sin ofattraetio n 15de sir ed the n fo r suffieiently la rg en dePe nd ento nr 食 李 岁 12 Zr In 公甲二一 汁妞l一 下 4 刀 1 In刀 8 2 Choo se sto red patte r n s at random If these eond type ba sin ofattra etio n 15de sir ed an dd efintio n 215 u s ed the n 第 1 0 期章祥荪等 对Ho Pf ie ld神经网络的直接数学分析 13 tio n Ifa setof PPattern s 1 v e n its non 一orthoso n al degre e a r e 91 15defin edas The se are f d 二卜l 无 l 汽 Pa cityan alysis 广 命 inte re sting fo r the 9 r e s ults in thee a H opfieldn etwork d m a x 止 k But stillthey he ayily让epend o n the as sump tio n s ofPatte rn吞 orthogon alitya ndsuffieie n tly la rge s ealeofthen etwo rk It15 obvia u s thatin m o staPPl ieatio ns thestor ed Pat te r n s a r enotn e e e ssa rily m utu allyorthngo n aland the n etworkse ale 15 also lim ited In thisPaPer in steadofusingstatistie alnature m ethod whieh15 PoPula rin n eur alnet orkan alysisshown in 6 a nd 12 w eusestraightforwa rd m athematieala n alysis to studyasiv e n H O Pfiel d n etwork given siz e and giv enpatte r ns Inl the c aPaeityofthen etwork in terms of definit io n 1 a nd 215d is eu ssed In皿 the eone ePts ofa ss o eiative Patte r ns a ndsPuriou s Pat te rnsa r e introdu e ed whieh ha vebe ene盆PI or ed in 12一15 and w e ha vePro v ed thatin me pe 二 一g n 么 a 一 pur iou spa tte r n s wher e a 任 1 一 1 拼二1 一 P Fin a lly eonelusiona nd dise u ssio nare pre sentedin w Let 几denotethe H am m ing 正尹人 11 distan ee 科 oftwo patte n s 月an d 介 then 21吐了 d m ax 七 二 l 几 2 By the orem this definitio n l 无 1 p 忍笋朴 12 w e hav e aeaPaeity in te rmsofthe m odifiedve r sio nof definition1 The o rem Giv e n 1 夕户 a n d W in 4 o r 5 if 户一l d 一一二 二一一 戈 二 于 一犷 13 the n Ping yl 2 y a re fix ed Points ofthe m ap Pr o o于 Fo r a ny l l 令 W 艺 二 上习 I 勺 几 I 今I 户 户 艺 y竿 梦 y 脚一I 二上川 砚 李习 梦习 矛娜 刀梦斗 w he re a nd her eafter w e den ote 习 兹 习 as 艺 气 l 习 I for short Sin e e 1 1 Cap a eli t yan a lysi s 芬 o ra 9iv en H op 荟ield netwo rk 上艺 n口勺止 习 梦 J布 梦 川 粤习 梦 n 即勺 艺衅川 气l 衅 C o n sidera H oPfieldn etwo rk with ne u ro nsru n ning in the asyn ehrono u sPro e ed ur eorsynehron ousPr oe edur e Fo r a give n setofPattern s 少1 thee on ne etio n m atri笼 15 shown in 4 o r 5 G e nerally 1 p arenotn ee e ssa ry to bem utually orthogo n al T oestimate the deg r eeofas et of binaryv e etors wegive the follow ingde finition D e子 initio n 3 Fo r giv enPatterns 夕考 an d 夕几 二 告 恩 恩 生 一1 一 几 师 t the n w e ha ve E D then etwork Q o f notieing 13 sgn w e C o ro a ry w ith siz e The eaPaeity n i e thema ximum ofstablesto r ed Patterns at le ast n um be rP lS 理竺1 L IJ 二 属 l 10 五 5their quantitv n on一o rthogon al degre e w hieh to m e a suretheirorthogon al ISa t ela For giving some in sights into the eo n d itio n 13 somee x amPlesare Iistedin the fol lowins tab le N otie ethate ondition 13 gu ar anteesP Patternsto be stable in the w or stea s e In fa et theProofoftheorem 115 a w orstcas e l4 电子学报 19 92牟 P 洛 1125102 050100 二 5 U 且 n 万 2 U nl 月 曰n 口 d 二 吸OU 工才弓曰月吧 了 通 吸 扭0 二 O 一月 吧 g U O 100 600 1000 10000 50 2 50 500 6000 83 16 7 333 3 3 3 3 17 84 1 67 16 67 O a nalysis 0on eeanexPe et thatinPraetiee the r ewill be a Iittlela rg ernum be r 户tha n that11吕tedin abo v e tab le In aPPlie atio n fo r e x amPle ifw en e ed ehoo s e ome lette rs fr om26Englishlette rs to bePatte rn 吕 of ag ive n size HoPfield net w o rk w eea neomPote JI 介 fo r e v ery Pair of lette r s the n cho oseas ubsetof lette r s w 主th a s m u eh Iette r s a s Possible a nda吕 small d as Po s sibleto u s e the n etwo rk effeetively I n the followingdis e ussion w eu s e B g 卜 x 户 to den otethe im m ediate orone ste P c onverge nee ba sin that15 刀 f x 任S sgn w x 14 the fol lowing theor emgiv e s asuffeient e onditio n fo r avectorx belo ng to B勿 T he o r e m 2 If 13 15 satisfied 仓 必 then N x 任S x 习l x 口勺I P cB g 1 e N 刀 15 asubset eon v e rge nee ba sinB勿 de se riPtive to be cheeke d of the o n e 15 SteP W 01台 e alle d the re sidualeaPa eity of the n etwork w hen 户Patte rn sa re giv e n T hisdefinitio neomes from anobse rva tionthatthe Ia rg e rofther e sidualeaPa eity R the m oreextra Patter ns thateould be ad ded in the n etwork o r the large rof the c o nv e rge ne e ba sin r ad iu sof the existing to re dPatte rn s T oexplain this obse rvation m athematieal ly w e give the follow ingdefini tion al ldtheo t em D e 于ini七io n 6 The stability deg ree 无 of a Hopfield n etwork a s CAM w ith aset ofgive n Pat te r n s i defin ed a S 声 目了 e习 昌 匕 了 奋 bu t N 刀 15m ore uP Pro o于 Fir stlyw e hav e 三N by onlyn otieing 习 户 户一1 d 户上 艺l Pro o书 T o do the estimation w e the definitio nof 无 as follow s n 即勺l 梦 x P 一Px 口勺心 dify 无 之0 if夕l二一l the n 脚 whe r e n In 且 m ax 人 B gN g N 刀 15defin ed that for in 15 x 任B 一 刀 n otieing 笋 I g F r x 第 1 0 期章祥荪等 对Ho Pf i e l d神经网络的 接数学分析 l5 d 2无 hen e e if 介一2无 户一l J 2气 户 then x 习I 刀 x l p 口 1 e x 任N g N owrewrite 20 w e have 20 Pro o子 omitted F公 om the defin atio n of d w eeansee 几 一户一 P一l d 2 户 二一星 2户 tbat it15 a m e a su reme ntofthenon 一o rthogo n ality deg ree betw e e n a ndothe r P一l sto r ed Patterns 50 theorem 4 tellsus that the m a ximumradiusof B 15 r elated to 及 1 e the一 a r e J 15 the 一 e s th 凡宁 15 a ndviee ve r sa then 左 口in 翻 皿 m a义 无 B y g N 二 曰口 In U 二 1 In 臼 1 m二 会 圈 刹 Q E D Theo rem3giv e s o nea n ideahow to esti mate in thewo rst e a s e the radiusofthe O ne一stePe onve rgene e basinw he n户Patte rn a re determ ined W e hav edi吕 eus sed the e on eePtofstab ilitydegr e e now w e willgivem orean aly 515o n the m ax im umr ad iu sofon e一stePeo n vergen ee basin ofsinglePattern F ir st w e ha v e the followingdefination D e 子 in a七 io n 7 T hem ax im um ra diu s o f one 一ste P eonvergenee ba sin B y l 15defin ed as 斤宁 m ax 左 刀 任刀 刀 l二 1 户 About this defin atio n w eean first ha ve the follow ing re sult Lem m a 1 Sup po se y l a reaset ofstored Patte rn s the n forVI二1 P w e ha v e左 分 n 2 Pr o o于 Om itr ed Letd l l P 一 l 艺 J u From the 龟冷 lemm aabove w ee a n oren getthefol low ingthe 1 A s soeia七ive pat七 e rnsa ndspurious Pa七 tern s A simplea n alysis in 16 shows that if a H oPfieldn etwo rksto reso nlyone Pat te rn沙 o n e stor ed pa tern m odel tbe n一9 15 a15 0 a fix ed point C an w ee all 一 a sPu r io uo pattern 户If thete rm spu rious Patter n 15 u s ed it give s on ean idea thatthe n et w ork m ake sa mistake toeo nvergetoa w r o ng Pattern It15inte re sting to think that an e ur alnetwo rk 15 somew hat intell i ge nt a a hum an brain the n w he n it r ee og nize sa PhotograPh Pat tern it shouldals o r e eognize in some deg r e e the negativ eof the Photogr aph The onestored Patte r n m odel the n n atu rallyremem be r 一g o 一刀 15 notasPu riou s Patte r n bu ta nassoeiativ e Patte rn w hieh15 a ssoeiativelyr emembered byPatte r n 刀 1t15w ell known fo r the H oPfieldn et w o rk tbatifit remem ber s patte rns 万 t 刀 the n it e anals ore eogniz e s 一 1 一 一 From the o rem 1 tothe o rem 3 w e ha v e seenthat the eo nd itio n 13 plays ave ry imPo rra ntrole togu a r a ntee the network ele arlyremem be ring patte rns刀1 一 a nd their negative s Infaet ifw er ewrite l犷 s d 1 n 一 1 p一l 21 Or 尹 T卜 eo rem a r e the stor ed 4 S uppose 1 户一l Y 2 一 5 0 w e have sgn W 二 宁 v i 1 n A nd it 5 e a sy to see thatwe ea nalso Pro ve sgn W 一y 一y宁 v i x n 50 a nd一少 a r e fix edpoin tsofthen et wo rk Q E D From the for功e r lemm a w e w ill e a sily get T he o re m 5 Suppose 1 2 尸a rea g ro u p o fpatte rn s 歹 拜 a 抖 whe r ea 任 l 一l 1 户 京 侄 L et J l n 一 l 卫 J t de note d 二 口 勺耳 名 歹梦 d d二 V 拌 无 1 户 拌特七 av 忍I IO 蚕 r川 h n 一 乡 n 一 fiX ed V 了 2 Let l 2 n 言 I n n 一 1 艺了 de n ote 才 脚勺七 r e a Points ofthen etwo rk Pro o于 V l n W 习 了气t 学 梦 才 了 石 Y 凡二1 p 料斗左 a nd w e hav 忍l 含 l L 一 才 n 一 妙 h二 一 么 二S 自 a 上艺 nl勺l 习 y了y罗 臼一压丹 属 青急 寺急 寺急 习衅对 脚一扭三 y 兮艺 梦 I 勺口 习 t l fl习二 一 1 L布勺臼了勺IJ nL 杯二 习 d t一 几勺邵 罗 李 n 一 l a re fix edpoints of the n etwork Pr o o于 If o nl丫 w enote that and 一 气 二1 Pgiv e thesamee ontributio n to the weishtm atrix w eeanu se 一 一 ins te ad ofthe 拼 一th patte rn and w e wil lg et thes ame w eight m atrix In othe r w ords w e getthe samen etwork bya rbitra rilyeha nging the s主gn softhe p attern s H e ne e ifw er egard 夕 夕 2 astheo rigin al patte r ns the Pro ofPro ee s s of this the or em wil lbe the s amea softhe lem m a 汀 曰L 艺 y r 日飞 nL J芯习 少 习 J d 介勺口 门 一 弄 Jn儿 pp 习 梦 习 y梦 乍 鑫补 弃 一 自 介 口 一I I V t Q E D Co ne u sio n a nd dis e u s sio n In ste adofu singstatistie alnatu re m e 今 一 l J一 一 l 一 刀 thod field 甲7 e a n alys e the ProPe rtie s ofthe H oP n etwork su ehas it eaPa eity eonv er 习片 口一l 一七 nL 茹二l 习 夕梦艺d 几勺即 石 ge n e e a ss o eiativ ea nd usingstr aightforwa rd sPu rio u sPatte rn s by an alysis Or W OtstCase 第 1 0 期 章祥荪等 对Ho Pf i el d 神经网络的直接数学分析 l7 a n alysis It seems to u sthatsu eh kind of analvtie alte ehnique 15 effe etiv e an d the n 15 as uPPleme ntto thetradition al teehniques s e e 6 In thisPaPerwe hav e given suffieie nt e ond itio n s se e the orem 1 a ndeond ition 13 with whieh the to r ed Patte r n swil lbe re e a 1ledby the n etwork D u ring the dise u s sio n somen eweon e ePt sucha sthenon 一orthog o nal degr eeofasetofPatte r ns 人 一n e ighbou r ho odin one一stePeonve rge n e e ba sin w e r e introdu eed theyw illbe useful in Praetie al aPPlie ation s It15inte resting that if then etworkre m ebers 1 it noto nlyautomarieal ly o r assoeiatively r emem be r s 一 一 but also Pr obably r emem berssome lin ea r eom bin ation 一I ike ofthesto r edPa