Visual analogy Viewing analogical retrieval and ma

VisualAnalogy:ViewingAnalogicalRetrievalandMappingasConstraintSatisfactionProblemsPatrickW.YanerandAshokK.GoelArtificialIntelligenceLaboratoryCollegeofComputing,GeorgiaInstituteofTechnology,email:fyaner,[e-mail]26,2006AbstractThecoreissueofanalogicalreasoningisthetransferofrelationalknowledgefromasourcecasetoatargetproblem.Visualanalogicalreasoningpertainstoproblemscontainingonlyvisualknowledge.HolyoakandThagardproposedthattheretrievalandmappingtasksofanalogyingeneralcanbeproductivelyviewedasconstraintsatisfactionproblems,andprovidedconnectionistimplementationsoftheirproposal.Inthispaper,wereexaminetheretrievalandmappingtasksofanalogyinthecontextofdiagrammaticcases,representingthespatialstructureofsourceandtargetdiagramsassemanticnetworksinwhichthenodesrepresentspatialelementsandthelinksrepresentspatialrelations.Weuseamethodofcon-straintsatisfactionwithbacktrackingfortheretrievalandmappingtasks,withsub-graphisomorphismoveraparticulardomainlanguageasthesimilaritymeasure.Resultsinthedomainof2Dlinedrawingssuggestthatatleastforthisdomaintheabovemethodisquitepromising.Keywords:analogicalreasoning,visualreasoning,constraintsatisfaction,ana-logicalretrieval,analogicalmapping1IntroductionAnalogicalreasoningreferstotransferofrelationalknowledgefromasource(orbase)casetoatargetproblem.Dependingonthenatureofthetargetandthesource,theknowledgetransferredinananalogymaypertaintodifferentkindsofrelations,forexample,causal,functionalorteleologicalrelations.Invisualanalogy,thepertinentrelationsarespatialrelationsamongvisualelements.Weviewknowledgeofdifferentkindsaslyingonaspectrum,atoneendofwhichisrawsensorydata,suchaspixelsinaphotograph,andattheotherextremeishighlyinterpretedandabstractedknowl-edge,suchasteleologicalknowledge.Visualknowledgeisclosertotheperceptualorthemodalendofthespectrumandcausalknowledgeisclosertotheamodalend.Invisualknowledge,causalitycanbepresentonlyimplicitly.AtthemodalextremeoftheAppliedIntelligence25(1):91-105,2006StorageEvaluationfocusofthissectionRetrievalfocusofoursystemMappingAdaptationTransferandFigure1:Thetasksofanalogy.Thispaperfocusesontheretrievalandmappingtasks,withthefirstpartofthispaperfocusingonretrieval.knowledgespectrum,visualknowledgemaybeexpressedusingdepictiveorpictorialrepresentationssuchasabitmap.Visualknowledgehigherupinthespectrummaybedescriptivelyrepresentedusingsymbolicstructures.Inthispaper,wefocusonvisualanalogicalreasoning,i.e.,reasoningwithcasesthatcontainonlyvisualknowledge,wherevisualknowledgeconsists(only)ofinformationabouthowanentityappears.Analogicaltypicallyinvolvesthetasksofretrievingasourcecasesimilartoagiventargetproblem,mapping(oraligning)thesourceandthetarget,transferringarela-tionalstructurefromthesourceandadaptingittothetarget,evaluatingthecandidatesolutiontothetarget,andstoringthetargetinmemory(seefigure1).HolyoakandThagardproposedthattheretrieval[40]andmapping[23]tasksofanalogyingeneralcanbeproductivelyviewedasconstraintsatisfactionproblems.Theirproposalincor-poratedstructural,semanticandpragmaticconstraintsandusedgraphisomorphismastheprimarysimilaritymeasure.TheirmappingsystemcalledACME,andthecom-plementaryretrievalsystemnamedARCS,providedconnectionistimplementationsoftheirproposal.InACME,nodesareconstructedforeachmaphypothesis(betweenasourceelementandatargetelement),withinhibitoryandexcitatorylinksbetweendifferentnodes,andthenetworkisrununtilitreachesquiescence.OurworkbuildsonHolyoakandThagard’sproposalintwoways.Firstly,wein-vestigatetheirproposalforthespecificcaseofvisualanalogies.Thatis,theanalogiesarebasedonlyvisualknowledgeabouttheappearanceofanentity.Secondly,whilewealsoviewtheretrievalandmappingtasksasconstraintsatisfactionproblems(CSPs),ourmethodforaddressingthetasks(i)organizesthesourcecasesinadiscriminationtree,(ii)uses(general-purpose)heuristicstoguidethesearch,(iii)performsaback-trackingsearch,and(iv)searchesallthesourcecasesatonce.Constraintsatisfactionwithbacktrackingisknowntobefast,andrecentlyhasbeenshowntoaddressreal-worldcomputationallyintractableproblems[2].Ourmethodologyistostartwithsimpleproblemsandincrementallyaddcomplex-itytothem.Thisincrementalnatureofthemethodologyismanifestedinthreeways.Firstly,visualknowledgecanbeofmanyforms,suchasbit-maprepresentations,pho-tos,sketches,oranimations,butourworkdealsspecificallywithdiagrammaticknowl-edgeknowledgeofshapes,theirsizesandlocations,andthespatialrelationshipsbe-tweentheshapes.Secondly,thoughvisualanalogies,likeanalogiesmoregenerally,caninvolvesemanticandpragmaticconstraints,westartwithjustthestructuralcon-straintsimposedbyrequiringsourceandtargettomatchstructures.Thirdly,fromagraph-theoreticperspective,theremaybemorethanonegraphisomorphismmetricformeasuringthesimilaritybetweentwodiagrams,butwebeginwithsubgraphiso-2FeatureVectorNetworkExternalMemoryTargetMatcherNetworkFeatureComparisonWorkingMemoryGeneratorNetworkResultsExtractorFeatureImageFigure2:SystemArchitecture.morphismasourmetric.Ofcourse,sincesubgraphisomorphismisNP-Complete,constraintsatisfactionwithbacktrackingevenwithon