Computational modeling of analogy and similarity Praveen Paritosh CogSci 207 Fall 2004 Overview Examples Structure mapping theory Simulating matching SME Simulating generalizations SEQL An analogy Abusive husband H wife W H treates W badly H terriorises W convinces everyone out there to hurt her and only he can save her When W goes out H watches closely to protect her H alienates W from all her friends who try to warn her But W doesnt quit cant be alone until a replacement lined up In due course another guy G comes along Hmm why does W still stick with H W is intrigued but not sure W s been scared hurt and cant help but see some of H in G H didnt look all that abusive when we started dating right For W to pick G he must prove himself to be a far superior choice not slightly maybe better Analogical reasoning in action To make prediction use some similar event To argue for the prediction focus on aspects that heighten similarity The more similar the event the more likely the prediction To argue against the prediction focus on aspects that decrease similarity Not just any differences will do Differences that are key to the prediction matter Structure Mapping Theory Gentner 1983 Analogy involves correspondences between structured descriptions candidate inferences fill in missing structure in target Constraints Identicality Match identical relations attributes functions Map non identical functions when suggested by higher order matches 1 1 mappings Each item can be matched with at most one other Systematicity Prefer mappings involving systems of relations esp including higher order relations Also provides account of similarity metaphor Growing body of evidence that same processes are used in perception problem solving conceptual change Representation assumptions in structure mapping Attributes are unary predicates representing category membership Bartender George Equivalently isa George Bartender Relations describe connections between more than one thing worksAt George CineArts6 Logically equivalent not same as psychologically equivalent or computationally equivalent Order of an item in a description indicates height in nested structure Order entitties 0 Order expression 1 max order arguments Higher order statement in this sense has deeper nesting Contrast with higher order in logic meaning predicates can be used as terms Why Tiered identicality is important Analogy and similarity are not pure graph isomorphism Content matters Postulating identical relations is a strong semantic constraint preferredPreyType Cats Mice preferredPreyType ConArtist NaiveInvestors typicalMaterialType AutomobileBody Metal Identicality goes a long way but sometimes want to weaken it slightly preferredFoodType ItalianPeople PastaDish Why non identical functions can match Functions are ways of specifying terms Psychologically often correspond to dimensions or parts of some kind e g temperature water8 pressure oil9 e g MilitaryFn Country18 ImmuneSystemFn Animal6 Don t want to propose all possible function matches Avoid combinatorial explosions Allow only if suggested by larger relational structure Supports cross dimensional comparisons Why 1 1 is important Suppose we had Titanic Enron Captain of Titanic Ken Lay Iceberg Ponzi scheme Passengers Investors Lookouts Whistle blowers Then Lookouts warn captain but are ignored Whistleblowers warn Ken Lay but are ignored But if we also have Lookouts Ken Lay Lookouts warn captain but are ignored Ken Lay warns Ken Lay but is ignored Why parallel connectivity is important Consider implies and LeakingFluidDevice BrakeCylinder2 partOf BrakeCylinder2 Car54 DangerousDevice Car54 implies EjectsFlames BattleBot12 DangerousDevice BattleBot12 What does BrakeCylinder2 go with Best one can do in these cases is rerepresent implies reason for being dangerous But that operation lies outside the matcher for tractability Unwise to embed exponential processes in inner loop Why systematicity is important Systems with higher order relations structurally well justified arguments semantically Higher systematicity matching structures more likely to lead to stronger candidate inferences Example implies applicable Theory8 Context12 implies and fact1 fact2 conclusion factA factB versus factA factB applicable Theory8 Context60 SME Structure Mapping Engine Base Inputs propositional descriptions w incremental updates Output one or two mappings SME Target Operates in polynomial time by exploiting graph labels greedy algorithms Mappings correspondences structural evaluation candidate inferences Local parallel processing first Construct local match hypotheses connecting identical predicates functions and entities needed for structural consistency Parallel processing of structural relationships Prune match hypotheses that violate structural consistency Mark structurally inconsistent combinations Start structural evaluation via trickle down local method of enforcing systematicity Identify Kernel mappings Maximal locally consistent combinations of match hypotheses Provides intermediate level representation for start of serial processing Construct global mappings Use greedy merge method Construct candidate inferences from leftover base structure Generate until less than dropoff of max up to n mappings Complexity of the SME Algorithm 1 Local Match construction O n2 worst case 2 Structural consistency local evaluation O n worst case 3 Kernel construction O n worst case 4 Structural evaluation O n 5 Merge O k worst case Adding incrementality does not affect these bounds SME consistent with psychological findings Systematicity and structural consistency influence interpretation of analogies Clement Gentner 1991 Structural consistency influences inference in analogical reasoning Clement Gentner 1991 Keane 1996 Spellman Holyoak 1992 1996 Markman 1997 Structural consistency influences inference in category based induction Lassaline 1996 Wu Gentner 1998 Systematicity influences inference in analogical reasoning and category based induction Clement Gentner 1991 Wu Gentner 1998 Ordinary similarity comparisons utilize structural alignment and mapping Gentner 1989 Gentner Markman 1995 1997 Markman Gentner 1993 in press Medin Goldstone Gentner 1993 Similarity based retrieval is surface driven but similarity based reasoning is structurally driven Gentner Rattermann Forbus 1993 Holyoak Koh 1987 Ross 1989 Some SME psychological predictions Online processing of similarity and analogy is influenced both by object richness