人工智能与神经网络(ainn)(钟义信)(北京邮电大学讲义)ainn09

AI&NNNotesChapter9FeedbackNeuralNetworks§9.1BasicConceptsAttractor:astatetowardwhichthesystemevolvesintimestartingfromcertaininitialconditions.Basinofattraction:thesetofinitialconditionswhichinitiatestheevolutionterminatingintheattractor.Fixedpoint:ifanattractorisinaformofauniquepointinstatespace.LimitCycle:ifanattractorconsistsofaperiodicsequenceofstates.HopfieldNetworkanditsBasicAssumptions12nvvv12nTTT12niiin21wwww2112n1wwn21n2n1.1layer,nneurons2.T--Thresholdofneuroni3.w--weightfromjtoi4.v--outputofneuronj5.i--externalinputtothei-thneuronijijiThetotalinputofthei-thneuronisnet=iJ=1jinwv+i-T=WV+i-T,forI=2,…,nijjiiitiiwhereW=wwwii1i2in...V=vvv12nThecompletematrixdescriptionofthelinearportionofthesystemshowninthefigureisgivenbynet=WV+i-twherenet=netnetneti=iii12n12narevectorscontainingactivation,externalinputtoeachneuronandthresholdvector,respectively.t=TTT1n2Wisannnmatrixcontainingnetworkweights:W=www=wwwwwwwwwwww000012nttt12131n21232n31323nn1n2n3w=wijjiw=0iiand§9.2Discrete-TimeHopfieldNetworkAssumingthattheneuron’sactivationfunctionissgn,thetransitionruleofthei-thneuronwouldbe-1,ifnet<0(inhibitedstate)+1,ifnet>0(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,untilitisstabilizedinoneofthe2verticesavailable.Themovementisfromavertextoanadjacentvertexsincetheasynchronousupdatemodeallowsforasingle-componentupdateofann-tuplevectoratatime.Thefinalpositionofvask,isdeterminedbyweights,thresholds,inputs,andtheinitialvectorvaswellastheorderoftransitions.nn0nToevaluatethestabilitypropertyofthedynamicalsystemofinterest,thecomputationalenergyfunctionisdefinedinn-dimensionaloutputspacev.Iftheincrementsofacertainboundedpositive-valuedcomputationalenergyfunctionunderthetransitionrulearefoundtobenon-positive,thenthefunctioncanbecalledaLyapunovfunction,andthesystemwouldbeasymptoticallystable.Thescalar-valuedenergyfunctionforthediscussedsystemisaquadraticform:nE=-1/2VWV-iV+tVtttE=-1/2VWV-iV+tVorE=-1/2wvv-iv+tvi=1nj=1nijiji=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.vjitttThereforewehave(v)=[0…v…0]itThiscanberewrittenasE=-(wv+i-t)vforji,iiijijnj=1orbrieflyE=-netviiNotethatwhennet<0,thenv<0whennet>0,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.Fork>4,nochangesareproducedatthenetworkoutputsincethesystemarrivedatoneofitsstablestates.§9.3Gradient-TypeHopfieldNetworkConsiderthecontinuous-timesingle-layerfeedbacknetworks.Oneofitsmodelisgivenbelow.ccccgggg112233nn123nvvvvwn11nww32iiii123nuuuu123n123nvvvvItconsistsofnneurons,eachmappingitsinputuintotheoutputvthroughtheactivationfunctionf(u).Conductancewconnectstheoutputofthej-thneurontotheinputofthei-thneuron.Itisalsoassumedthatw=wandw=0.TheKCLequationfortheinputnodehavingpotentialucanbeobtainedasiiiijijjiiiii+wv-u(w+g)=Cij=1jinijjij=1jinijiidudtiDefiningG=w+g,C=diag[C,…,C],j=1jiniji1nwethenhaveCdu(t)dt=Wv(t)-Gu(t)+iwherev(t)=f(u(t))ItcanbeshownthatthederivativeofthecomputationalenergyfunctiondE[v(t)]dt=-(c)dudttdvdtItfollowsthusthatthechangeofE,intime,areinthegeneraldirectiontowardlowervaluesoftheenergyfunctioninvspace--thestabilitycondition.n<0=E(v)vi•LetE(v)=-(1/2)vWv–iv+Gf(z)dztttni=1i0Vii-1=…(seep.268-269[1])§9.4FeedbackNetworksforComputationalApplicationsInprinciple,anyoptimizationproblemswhoseobjectivefunctioncanbeexpressedintheformofenergyfunctioncanbesolvedbyfeedbacknetworksconvergence.TaketheTSPProblemasanexample.GivenasetofncitiesA,B,C,…withpairwisedistancesd,d,…trytofindaclosetourwhichvisitseachcityonce,returnstothestartingcityandhasaminimumtotalpathlength.ABACThisisanNP-completeproblem.Tomapthisproblemontothecomputationalnetwork,werequirearepresentationscheme,inwhichthefinallocationofanyindividualcityisspecifiedbytheoutputstatesofasetofnneurons.E.g.,n=5,theneuronalstate(5neurons)shownbelowwouldrepresentatour:2CityOrderABCDE123450100000010100000000100100Inthennsquarerepresentation,thismeansthatinanoutputstatedescribingavalidtourtherecanbeonlyone“1”ineachrowandeachcolumn,allotherentriesbeing“0”.Inthisscheme,thensymbolsvwillbedescribedbydoubleindices,v:xstandsforcityname,jforthepositionofthatcityintour.2iToenabletheNneuronstocomputeasolutiontotheproblem,thenetworkmustbedescribedbyanenergyfunctioninwhichthelowestenergystatecorrespondstothebestpathofthetour.xjAnappropriateformforthisfunctioncanbefoundbyconsideringthehighgainlimit,inwhichallfinalnormaloutputwillbe0or1.Thespaceoverwhichtheenergyfunctionisminimizedinthislimitisthe2cornersoftheN-dimensionalhypercubedefinedbyv=0or1.NiConsiderthosecornersofthisspacewhicharethelocalminima(stablestates)oftheenergyfunctionE=1A2vv+B2vv+C2(v-n)xijixixjxiyxxiyixi2xiwhereA,B,Carepositiveconstants,v{0,1}.i--Thefirsttermis0iffeachcityrowxcontainsnomorethanone“1”.--Thesecondtermis0iffeachpositionintourcolumnicontainsnomorethanone“1”.--Thethirdtermis0ifftherearencitiesof“1”intheentirematrix.Thus,thisenergyfunctionevaluatedonthedomainofthecornersofthehypercubehasminimawithE=0forallstablematriceswithone“1”ineachrowandcolumn.Allotherstateshavehigherenergy.1Hence,includingthesetermsinanenergyfunctiondescribingaTSPnetworkstronglyfavorsstablestateswhichareatleastvalidtourintheTSPproblem.Anotherrequirement,thatEfavorsvalidtoursrepresentingshortpath,isfulfilledbyaddingoneadditionaltermtoE.Thistermcontainsinformationaboutthelengthofthepathcorrespondingtoagiventour,anditsformcanbe1E=D22dv(v+v)xyxixyxiy,i+1y,i-1wheresubscriptsaredefinedmodulon,inordertoexpresseasily“endeffects”suchasthefactthatthen-thcityonatourisadjacentinthetourtobothcity(n-1)andcity1,i.e.,v=v.Withinthedomainofstateswhichcharacterizesavalidtour,Eisnumeric-allyequaltothelengthofthepathforthattour.y,n+jy,j2IfA,B,andCaresufficientlylarge,allthereallylowenergystatesofanetworkdescribedbythisfunctionwillhavetheformofavalidtour.Thetotalenergyofthatstatewillbethelengthofthetour,andthestateswiththeshortestpathwillbethelowestenergystates.Usingtherow/columnneuronlabelingschemedescribedaboveforeachofthetwoindices,theimplicitlydefinedconnectionmatrixisT=-Ad(1-d)“inhibitoryconnectionswithineachrow”-Bd(1-d)“inhibitoryconnectionswitheachcolumn”-C“globalinhibition”-Dd(d+d)“dataterm”xyijijxyxyj,i+1j,i-1xi,yjTheexternalinputareI=2C“excitationbias”xinThe“dataterm”contribution,withD,toTistheinputwhichdescribeswhichTSPproblem(i.e.,wherethecitiesactuallyare)istobesolved.xi,yjThetermswithA,B,CprovidethegeneralconstraintsrequiredforanyTSPproblem.The“dataterm”contributioncontrolswhichoneofthen!setoftheseproperlyconstrainedfinalstatesisactuallychosenasthe“best”path.Theproblemformulatedasshownbelowhasbeensolvednumericallyforthecontinuousactivationfunctionwithl=50,A=B=D=250,andC=100,for10<n<30.Quitesatisfactorysolutionhasbeenfound.ABCDEFGHIJ12345678910Path=D-H-I-F-G-E-A-J-C-B-D§9.5AssociativeMemory(AM)Byproperlyselectingtheweights,itispossibletomakethestablestatesofthenetworkjustbetheones,M,wewanttostore.Underthiscondition,thenetwork’sstateshouldnotchangeifthenetworkisinitiallyinthestateM;whereasifnotinM,itisexpectedthatthenetwork’sstablestateshouldbetheones,inM,closesttotheinitialstate(inthesenseofHammingdistance).TherearetwocategoriesofAM:1)Auto-AM:Ifinputx’=x+v,wherex{x,…,x},thenoutputy=x.aa1Max+vaxa2)Hetero-AM:Ifx’=x+v,wherexy,storedthenoutputy=y.x+vxyyaaaaOneofthetasksishowtofindthesuitableweightssuchthatthenetworkperformafunctionofAM?ThemostfrequentlyusedruleforthispurposeistheOuterProductRule.Assumethat--Considerann-neuronnetwork;--Eachactivitystatex{-1,1};--Hebbeanruleisobserved:w=xx,>0.iijaijaaaaae{1,...,M},Theouterproductruleisasfollows:ForgivenvectorsM={U,…,U},whereU=(x,…,x)write1mktkk1nW=(UU-I)=mk=1kkt0xxxxxx0xxxxxx0mk=11111222nnnn2kkkkkkkkkkkk=xxxx00k=1k=1mmkkkkn11nandthiscanbeimplementedbyfollowingprocedure:(1)SetW=[0](2)Fork=1tom,inputU,dow=w+xxforallconnectedpair(i,j)Checktoseeifitisreasonable:1)SupposethatU,…,Uareorthogonalandm<nkkkijijij1mWU=(UU-I)U+(UU-I)U111t1k=2mkkt1=UUU-IU+(UUU-IU)kkk=2m111111tt=Un-U+(-IU)=U(n-1)-(m-1)U=(n-m)U111111k=2mHenceSgn(WU)=Sgn[(n-m)U]=U111i.e.,Uisexactlyastablestateofthenetwork,andWthusdeterminedisreasonable.ExampleGivenn=3,m=3U=(11-1),U=(-111),U=(1,-11)Thus123tttUU-I=UU-I=UU-I=W=(UU-I)=11t01-110-1-1-1022t33t0-1-1-101-1100-11-10-11-10kktk=130-1-1-10-1-1-10WU=100-2Sgn(WU)=11-1=U111SimilarlyWU=00-2Sgn(WU)=222-111=UWU=0-20Sgn(WU)=1-11=U333Clearly,U,U,andUarestablememories.Thestructureofthenetworkisasbelow:uuu321-1-1-1321uuu123wwwwww121332233121ijw=-1,i,j=1,2,3,ijOr,equivalently,thenetworkisschemedasApplications:a)ClassificationGiveninputU=(111),whetherU{U,U,U}?xx123WU=x-2-2-2Sgn(WU)=-1-1-1UxHenceUdoesnotbelongtotheset{U,U,U}.1x23b)AssociativeMemoryGivenanoisyinputU=(01-1),whatisU?txtxWU=x01-1Sgn(WU)=x11-1=U.1UU.x12)Ingeneral,ifn-dimensionalvectorU,…,Uareorthogonal,n>m,then1mWU=(UU-I)U+(UU-I)Ukkkkkttiimi=1ik=U(UU-IU)+(UUU-IU)kkkkkkttmi=1iiik=Un-U+(m-1)(-IU)=(n-1)U-(m-1)U=(n-m)UkkkkkkSgn(WU)=Sgn[(n-m)U]=U,k=1,2,…,mkkkHence{U}arestablestates.k1)Thenucleusoftheneuralnetworkdesigntaskinmostcasesistofindtheproperweightmatrixofthenetwork.Summarization:2)Theweightmatrixoftheneuralnetworksinthecasesofassociativememorycanbedeterminedbytheouterproductrule.Itisimportanttoknowthat§9.6Self-OrganizingNetworksFeatures:UnsupervisedLearningNofeedbackfromtheenvironmentduringlearning.Thenetworkmustdiscoverforitselfanyrelationshipsofinterestthatmayexistintheinputdata.Theobjectiveinthispartistoexploretheunsupervisedlearningalgorithmsofneuralnetworkssothattheirweightscansensiblyadaptduringtheprocesscalledself-organizing.Networkstrainedinthismodewillnotonlyreacttovaluesofinputsbutalsototheirstatisticalparameters.Theindicatorhavetobecreatedbasedonthehistoryoflearningexperience.Unsupervisedlearningcanonlyimplementedwithredundantinputdata.Redundancyprovideknowledgeaboutstatisticalpropertiesofinputpatterns.UnsupervisedLearningofClustersThelearningisbasedonclusteringofinputdata.Noaprioriknowledgeisassumedtobeavailableregardinganinput’smembershipinaparticularclass.Rather,graduallydetectedcharacteristicsandahistoryoftrainingwillbeusedtoassistthenetworkindefiningclassesandpossibleboundariesbetweenthem.Clusteringisunderstoodtobethegroupingofsimilarobjectsandseparatingofdissimilarones.Thenumberofclassesisassumedknownapriori.Thepatternset{x,x,…,x}issubmittedtotheinputtodeterminedecisionfunctionsrequiredtoidentifypossibleclusters.Sincenoinformationisavailablefromtheteacher,wewillusethesimilarityofincomingpatternsasthecriterionforclustering.Todefineacluster,weneedtoestablishabasisforassigningpatternstothedomainofaparticularcluster.ThemostcommonsimilarityruleistheEuclideandistancebetweentwopatterns||x–x||=[(x–x)(x–x)](9-6-1)tiii1/212NThedistancesbetweenallpairsofpointscanbecomputedByusingeq.(9-6-1).AdistanceTcanthenbechosentodiscriminateclusters.ThevalueTisunderstoodasthemaximumdistancebetweenpatternswithinasinglecluster.Anothersimilarityruleisthecosineoftheanglebetweenxandx:cos=(xx)/||x||·||x||iitiThenetworkclassifiesinputvectorsintooneofthespecifiednumberofpcategoriesaccordingtotheclustersdetectedinthetrainingset{x,x,…,x}.Duringthetraining,dissimilarvectorsarerejectedandonlythemostsimilaroneisacceptedforweightbuilding.ThenetworktobetrainediscalledtheKohonennetwork.Theprocessingofinputdataxfromthetrainingset{x,x,…,x},whichrepresentspclusters,canbeexpressedasy=T[Wx]withdiagonalelementsoftheoperatorTbeingcontinuousactivationfunctionsoperatingcomponentwiseonentriesofVectorWx.12N12nww12ptttW==wwwwwwwwww...............11121n21222np1p2pnyyy1mpxxx12nwwwm1m2mnwpnw11w1nTheweightadjustmentcriterionforthismodeoftrainingistheselectionofwsuchthat||x–w||=min{||x–w||}imii=1,2,…p^^^wherew=w/||w||,I=1,2,…,p^iiiisthenormalizationofallweightvectors.Theindexmdenotesthewinningneuronnumbercorrespondingtothevectorw,whichistheclosestapproximationofthecurrentinputx.^mFeatureMappingwithoutSupervision