Falkenhainer, B., K. D. Forbus, D. Gentner (1990). The Structure mapping engine: algorithm and examples. Artificial Intelligence (41) pp1-63.

@Article{Falkenhainer90b,
  author =       "Brian Falkenhainer and Kenneth D. Forbus and Dedre
                 Gentner",
  title =        "The Structure-Mapping Engine: Algorithm and Examples",
  journal =      "Artificial Intelligence",
  volume =       "41",
  pages =        "1--63",
  year =         "1990",
}

Author of the summary: Jim Davies, 1999, jim@jimdavies.org

Cite this paper for:

• system: Structure-Mapping Engine
• system: SME
• SME is flexible and efficient enough to be of interest to AI as well as for cognitive modelers.
• SME has been applied to over 40 examples of analogy.
• systematicity
• global match: a set of pairwise matches between the facts and entities of two Dgroups.
• Dgroups: description groups. A collection of entities and facts about them.
• candidate inferences: a set of new facts which the comparison suggests holds in the target Dgroup.
• An analogy in between two Dgroups.
• Emap: a map between primitive entities.
• SME cannot usefully compare Gmaps with different bases and different targets.
• SME is part of a larger learning program called PHINEAS.

motivation

How does analogy work? Does all analogy use the same functions? How do you determine the quality of an analogue? How many ways can you sensible find analogies between two things?

goals

Structure-Mapping Theory

Kinds of similarity:(these correspond to the different sets of match rules typically used in SME.)

• analogy (described above)
• literal similarity (where both relational and object predicates are mapped)
• mere-appearance (where primarily only the object descriptions are mapped.)
• abstraction mapping (where the entities in the base domain are variables rather than objects).

1. access: retrieval of a similar analogue.
2. mapping: finding the right coorespondences. Produces a set of candidate inferences. Match rules determine how this is done.
3. evaluation and use: determining the quality of the match.

The Structure-Mapping Engine

The knowledge is represented with the following constructs:

• entities: objects and contants
• predicates:
  • functions: map entities to entities. E.g. (PRESSURE piston) maps the piston to a quantity that describes its pressure.
  • attributes: describes some property of an entity.
  • relations: the arguments over relations can be predicates or entities. Examples of predicates include CAUSE and GREATER-THAN.
  They might be communicative and/or may have any number of arguments. Predicate instances are called facts.
• description group (Dgroup): Like a frame. A collection of entities and facts about them. An analogy in between two Dgroups. A doorknob mechanism might be an example of a Dgroup.

With the exception of functions, predicates must match identically.

For two facts to match, all of their descendants must match perfectly (for the literal similarity case). The structural evaluation score is based on the rules and also uses a belief maintainance system that takes weights of mappings into consideration. The evidence for a Gmap is the sum of the evidence for its match hypotheses. (p22) No normalization is done, because normalizing doing so prevents one from comparing Gmaps with different base domains. You still cannot usefully compare Gmaps with different bases and different targets.

An Emap is a map between primitive entities.

Algorithm complexity

conflict calculation: between O(N) and O(N^2)

Emaps and NoGood set: O(# match rules)

Gmap merge: O(# partial matches)

finding candidate inferences: O(N^3)

score computation: O(# match rules)

Examples

some hypotheses of SME: That symantic relational overlap determines the inferential soundness of the match and that the surface similarity determines the accessability. Psychological studies supported both. (p32)

Experiment

Results

Comparisons with other work

Winston's matcher does a heuristic search for a single best match. SME produces fewer entity pairings.

Kline's RELAX system focuses on matching relations rather than entities. This program is able to match items with very different syntax, but does not prune the search very well.

Some inductive generalization programs address the partial matching problem. It may appear that many to one mappings are necessary, but the SME view is that though this may happen in artistic methphor, it does not happen with explanatory, predictive analogies. Multiple mappings may sometimes be useful, we suggest multiple analogies between the same base and target.

main claims and contributions of paper

SME has been applied to over 40 examples of analogy. It posits there are 3 distinct ways to map. These may (in part) coorespond to developmental changes in analogical strategy. Different kinds of analogy can be reproduced with these methods.

scope of work and limitations

One limitation I see is that in spite of the empirical evidence for structure mapping, the theory doesn't fit at all with spreading activation theories (and experiments?) of memory. Since what the objects actually are does not affect analogy (except in mere appearance matching), where do the robust priming effects we can see come from? Why are they seperate?

Related Information

Forbus, K. D., Ferguson, R. W., & Gentner, D. (1994). Incremental Structure Mapping. Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society.

Ferguson, R. W., and K.D. Forbus. Understanding illustrations of physical laws by integrating differences in visual and textual representations.

AAAI Fall Symposium on Computational Models for Integrating Language and Vision. 1995.

http://www.qrg.ils.nwu.edu/ideas/smeidea.htm A webpage on structure mapping.

Summary author's notes:

• page numbers are taken from a preprint version of this paper, not the one published in AI. Sorry!