A Study of Parallel Self-Organizing Map

quant-ph/9808025v319Oct1998AStudyofParallelSelf-OrganizingMapLiWeigangDepartmentofComputerScience-CICUniversityofBrasilia-UnBC.P4466,CEP:70919-970,Brasilia-DF,BrazilE-mail:[e-mail]-OrganizingMap(Parallel-SOM)isproposedtomodifyKohonen’sSOMinparallelcomputingenvironment.Inthismodel,twoseparatelayersofneuronsareconnectedtogether.Thenumberofneuronsinbothlayersandconnectionsbetweenthemistheproductofthenumberofallelementsofinputsignalsandthenumberofpossibleclassificationofthedata.Withthisstructuretheconventionalrepeatedlearningprocedureismodifiedtolearnjustonce.Theoncelearningmannerismoresimilartohumanlearningandmemorizingactivities.Duringtraining,weightupdatingismanagedthroughasequenceofoperationsamongsometransformationandoperationmatrices.Everyconnectionbetweenneuronsofinput/outputlayersisconsideredasaindependentprocessor.Inthisway,allelementsoftheEuclideandistancematrixandweightmatrixarecalculatedsimultaneously.TheminimumdistanceofeverylineofdistancematrixcanbefoundbyGrover’ssearchalgorithm.Thissynchronizationfeatureimprovestheweightupdatingsequencesignificantly.Withatypicalclassificationexample,theconvergenceresultdemonstratesefficientperformanceofParallel-SOM.Theoreticanalysisandproofsalsoshowsomeimportantpropertiesofproposedmodel.Especially,thepaperprovesthatParallel-SOMhasthesameconvergencepropertyasKohonen’sSOM,butthecomplexityofformerisreducedobviously.Keywords:Artificialneuralnetworks,competitivelearning,parallelcomputing,quantumcomputing,Self-OrganizingMap.1.IntroductionOncesaw,neverforgottenisasentencewhichisusedtodescribeahumansenseandlearningsequence.Forexample,aboyglancedatalovelygirlinaparty.Onhiswayhome,girl'sfaceappearsagainandagainduringhisthinking.Thisisadistinctfeatureofthehumanbrain.Generallyspeaking,thebrainisorganizedinmanyplacesinsuchawaythatdifferentsensoryinputsarerepresentedbytopologicallyorderedcomputationalmaps[Hay94].Inthefieldofartificialneuralnetworks(ANN),thissequenceiscalledpatternreorganization.Theboylearnedthegirl'simagejustonceandrecognizeditlatter.Somekindsofartificialneuralnetworkscansimulatethissequencebyrepeatedlearning.AmongthearchitecturesandalgorithmssuggestedforANN,theSOMhasthespecialpropertyofeffectivelycreatingspatiallyorganizedinternalrepresentations[Koh90].Kohonenattempttoconstructanartificialsystem,SOM,thatcanshowthesamebehaviorasboy'sexperiencethroughvariouslearning.FollowingKohonen'sprincipleoftopographicmapformation,thespatiallocationofanoutputneuroninthetopographicmapcorrespondstoaparticulardomainorfeatureoftheinputdata[Koh90].Inapplication,SOMhasbeenprovedtobeparticularlysuccessfulinvariouspatternrecognitiontasks.AsmentionedbyGrossberg[Gros98],theconventionallearningisintermsofserialprocessingandthissloweddowntheacceptanceofasamplingoperationthatcouldachievetask-dependentselectivityinaparallelprocessingenvironment.So,tosimulateboy'sbehaviorthroughjustonetime'slearning,isstilldifficultforSOM.Inthispaper,aParallelSelf-OrganizingMap-Parallel-SOMisproposedtoshowthesamebehaviorashumanlearningandmemorizingactivities.Willshaw-vonderMalsburg'sSOMisreconstructedinaparallelarchitecture.Thenumberofneuronsinbothinput/outputlayerandconnectionsbetweenthemisequaltotheproductofthenumberofallelements(M)ofinputsignalsandthenumberofpossibleclassification(P)ofthedata.Theweightupdatingismanagedthroughasequenceofoperationsamongsometransformationandoperationmatrices.Sotheconventionalrepeatedtrainingprocedureismodifiedtolearnjustonce.Notethatinparallelprocessingenvironment,thedevelopedweightupdatingalgorithmmakesParallel-SOMtohavethesamecompetitivelearningabilityandconvergencepropertyastheconventionalSOM.SomeotherparallelimplementationsofSOMhavebeendiscussed[Hyo97,Man90,Ope96,Sch97,Wu91].Themannerofthelearningandstructureofmaparedifferentfromtheproposedmodel.Inclassicalcomputing,Parallel-SOMisevenlessefficientthanSOM.Thisisduetotheextracompetitiveoperationsandweighttransformationsofthenewmodel.Ontheotherhand,puttingallinputastheneuronsoflayerisalmostimpossible.Supposetherearesignalsx(x(i)∈x,i=1,2,...M);oneinputneuronandPoutputneuronsareneededbyusingSOM,butMxPinputandoutputneuronsareneededinParallel-SOM.Inquantumcomputing,theuniquecharacteristicsofquantumtheorymaybeusedtorepresentinformationwhenthenumberofneuronsisexponentialcapacity[Ven98b].Usingquantumrepresentationx(i),i=1,...,M,thenumberofneuronsisexponentiallyreducedtoLog2M.WhenM=1000000andP=100,inconventionalcomputing,MxP=100millionsneuronsinbothinputandoutputlayerareneededtoimplementParallel-SOM;inquantumcomputing,just27quantumneuronsareneeded.WiththesynchronizationfeatureofParallel-SOMinquantumcomputing,thecompetitiveoperationsandweighttransformationwillcarryoutsimultaneously.ThismakestheParallel-SOMmoreinterestinginapplications.SinceBeniof[Ben82]andFeynman[Fey82]discoveredthepossibilityofusingquantummechanicalsystemforreasonablecomputingandDeutsch[Deu85]definedthefirstquantumcomputingmodel,thequantumcomputationhavebeendevelopedasainterestingmultidiscipline.Speciallyinrecentyears,theappearances