人工智能与神经网络笔记8

AI&NNNotesChapter9FeedbackNeuralNetworks§9.1BasicConceptsAttractor:astatetowardwhichthesystemevolvesintimestartingfromcertaininitialconditions.Basinofattraction:thesetofinitialconditionswhichinitiatestheevolutionterminatingintheattractor.Fixedpoint:ifanattractorisinaformofauniquepointinstatespace.LimitCycle:ifanattractorconsistsofaperiodicsequenceofstates.HopfieldNetworkanditsBasicAssumptions12nvvv12nTTT12niiin21=iJ=1jinwv+i-T=WV+i-T,forI=2,…,nijjiiitiiwhereW==vvv12nThecompletematrixdescriptionofthelinearportionofthesystemshowninthefigureisgivenbynet=WV+i-twherenet=netnetneti=iii12n12narevectorscontainingactivation,externalinputtoeachneuronandthresholdvector,respectively.t=TTT1n2Wisannnmatrixcontainingnetworkweights:W===wijjiw=0iiand§9.2Discrete-TimeHopfieldNetworkAssumingthattheneuron’sactivationfunctionissgn,thetransitionruleofthei-thneuronwouldbe-1,ifnet0(inhibitedstate)+1,ifnet0(excitatorystate)vIf,foragiventime,onlyasingleneuronisallowedtoupdateitsoutputandonlyoneentryinvectorvisallowedtochange,thisisanasynchronousoperation,underwhicheachelementoftheoutputvectorisupdatedseparatelywhiletakingintoaccountthemostrecentvaluesfortheelementsthathavealreadybeenupdatedandremainstable.(*)Basedon(*),theupdateruleofadiscrete-timerecurrentnetwork,foronevalueofiatatime,becomesv=sgn(wv+i-T)forrandomi,i=1,2,…,nandk=0,1,2,...iK+1itkiiwherekdenotestheindexofrecursiveupdate.ThisisreferredasasynchronousstochasticrecursionoftheHopfieldnetwork.Thisupdateprocesswillcontinueuntilallnentriesofvhavebeenupdated.Therecursivecomputationcontinuesuntiltheoutputnodevectorremainsunchangedwithfurtheriterations.Similarly,forsynchronousoperation,wehaveiK+1v=T[Wv+i-t],forallneurons,k=0,1,...K+1kwhereallneuronschangetheiroutputsimultaneously.GeometricalExplanationTheoutputvectorvisoneoftheverticesofthen-dimensionalcube[-1,1]inEspace.Thevectormovesduringrecursionsfromvertextovertex,untilitisstabilizesinoneofthe2verticesavailable.Themovementisfromavertextoanadjacentvertexsincetheasynchronousupdatemodeallowsforasingle-componentupdateofann-tuplevectoratatime.Thefinalpositionofvask,isdeterminedbyweights,thresholds,inputs,andtheinitialvectorvaswellastheorderoftransitions.nn0nToevaluatethestabilitypropertyofthedynamicalsystemofinterest,thecomputationalenergyfunctionisdefinedinn-dimensionaloutputspacev.Iftheincrementsofacertainboundedpositive-valuedcomputationalenergyfunctionunderthetransitionrulearefoundtobenon-positive,thenthefunctioncanbecalledaLyapunovfunction,andthesystemwouldbeasymptoticallystable.Thescalar-valuedenergyfunctionforthediscussedsystemisaquadraticform:nE=-1/2VWV-iV+tVtttorE=-1/2wvv-iv+tvi=1nj=1jinijiji=1i=1niiniiTheenergyfunctioninasynchronousmode.AssumethattheoutputnodeIhasbeenupdatedatthek-thinstantsothatv-v=v.Computingtheenergygradientvector:ik+1kiE=-1/2(W+W)v-i+t=-Wv-i+tvtttttW=WtTheenergyincrementbecomesE=(E)v=(-Wv-i+t)vttttiiiiThisisbecauseonlythei-thoutputisupdated.Thereforewehave(v)=[0…v…0]itThiscanberewrittenasE=-(wv+i-t)vforji,iiijijnj=1orbrieflyE=-netviiNotethatwhennet0,thenv0whennet0,thenv0thus(netv)isalwaysnon-negative.Inotherwords,anycorrespondingenergychangesEarenon-positiveprovidedthatw=w.iiiiiiijjiFurtherwecanshowthatthenon-increasingenergyfunctionhasaminimum.SinceWisindefinitebecauseofitszerodiagonal,thenEhasneitheraminimumnormaximuminunconstrainedoutputspace.However,Eisobviouslyboundedinn-dimensionalspaceconsistingofthe2verticesofn-dimensionalcube,Thus,Ehastoreachitsminimumfinallyundertheupdatealgorithm.nExampleofrecursiveasynchronousupdateofcomputeddigit4:(a)(b)(c)(d)(e)where(a)k=0,(b)k=1,(c)k=2,(d)k=3,(e)k=4.Theinitialmapisadestroyeddigit4with20%ofthepixelsrandomlyreversed.Fork4,nochangesareproducedatthenetworkoutputsincethesystemarrivedatoneofitsstablestates.§9.3Gradient-TypeHopfieldNetworkConsiderthecontinuous-timesingle-layerfeedbacknetworks.Oneofitsmodelisgivenbelow.ccccgggg112233nn123nvvvvwn11nww32iiii123nuuuu123n123nvvvvItconsistsofnneurons,eachmappingitsinputuintotheoutputvthroughtheactivationfunctionf(u).Conductancewconnectstheoutputofthej-thneurontotheinputofthei-thneuron.Itisalsoassumedthatw=wandw=0.TheKCLequationfortheinputnodehavingpotentialucanbeobtainedasiiiijijjiiiii+wv-u(w+g)=Cij=1jjnijjij=1jjnijiidudtiDefiningG=w+g,C=diag[C,…,C],G=diag[G,…,G]j=1jjniji1n1nThenwehaveCdu(t)dt=Wv(t)-Gu(t)+iandv(t)=f(u(t))ItcanbeshownthatdEdt=-(c)dudttdvdtItfollowsthusthatthechangeofE,intime,areinthegeneraldirectiontowardlowervaluesofheenergyfunctioninvspace--thestabilitycondition.n0§9.4FeedbackNetworksforComputationalApplicationsInprinciple,anyoptimizationproblemswhoseobjectivefunctioncanbeexpressedintheformofenergyfunctioncanbesolvedbyfeedbacknetworksconvergence.TaketheTravelingSalesmanProblemasanexample.GivenasetofncitiesA,B,C,…withpairwisedi