CogSci Summaries home |
Falkenhainer, B., K. D. Forbus, D. Gentner (1990). The Structure
mapping engine: algorithm and examples. Artificial Intelligence (41) pp1-63.
author = "Brian Falkenhainer and Kenneth D. Forbus and Dedre
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, email@example.com
Cite this paper for:
note: page numbers are taken from a preprint version of this paper,
not the one published in AI. Sorry!
- 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.
- 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.
cannot usefully compare Gmaps with different bases and different
- SME is part of a larger learning program called PHINEAS.
Analogy is bringing knowledge of previous experiences to bear on new
situations. Defined this broadly, analogy is a fundamental cognitive
process and is of great interest to cognitive scientists.
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?
This paper describes the Structure-Mapping Engine (SME) which is based
on Gentner's Structure-Mapping Theory of analogy. The theory has been
well supported by human subject experiments. The SME works out many
computational details of the theory and makes some predictions of its
The order of a representation: objects are order 0. The order of a
predicate is 1 plus the maximum order of its arguments. This
conception of order tells how deep the structure is below an item.
How is the mapping made? Isolated object descriptions are discarded
such as red(wagon), which means the wagon is red. Relations between
objects are mapped. High level mappings occur with a systematicity
bias, which means that high order relational similarities are
preferred. Systematicity has been empirically validated with empirical
Kinds of similarity:(these correspond to the different sets of match
rules typically used in SME.)
Structure-mapping has three stages:
- analogy (described above)
- literal similarity (where both relational and object predicates
- mere-appearance (where primarily only the object descriptions
- abstraction mapping (where the entities in the base domain are
variables rather than objects).
SME models the mapping stage.
- access: retrieval of a similar analogue.
- mapping: finding the right coorespondences. Produces a set of
candidate inferences. Match rules determine how this is done.
- evaluation and use: determining the quality of the match.
The Structure-Mapping Engine
SME constructs all possible mappings (each is called a global mapping
or Gmap), each with a score for finding
the best mapping each with candidate inferences. A Gmap is any
consistent set of match hypotheses formed between the target and base
The knowledge is represented with the following constructs:
One of the match rules for literal similarity is: "If the match
hypothesis concerns two facts, then create a match hypothesis between
any corresponding arguments that are both functions or entities."
- entities: objects and contants
They might be communicative and/or may have any number of
arguments. Predicate instances are called facts.
- functions: map entities to entities. E.g. (PRESSURE
piston) maps the piston to a quantity that describes its
- attributes: describes some property of an entity.
- relations: the arguments over relations can be predicates
or entities. Examples of predicates include CAUSE and
- 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.
local match construction: O(Nb * Nt) in theory, O(N) in practice
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)
SME has been applied to the solar-system/atom analogy, heat flow/water
flow (in which temperature and diameter are suggested to be analogous
an a candidate inference), and analogy of stories.
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
A story was the base of the analogy. Two stories were potential
analogues: one with different content but with the same structure, and
one with the same content (names of things, etc) but with the same
structure. It was predicted that the analogical match rules would
prefer the deep analogue and the mere similarity rules would prefer
the surface story.
The hypotheses were supported. These results also match with human
subject data, which show a difference in these stories with respect to
accessability and evaluation of match soundness. (p34).
Comparisons with other work
Holyoak's analogy theory makes a match based on the goal of a problem
solver. The limitations are that it has no notion of soundness, so
the search space explodes. Also, a system should be able to use
analogy for more than problem solving.
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 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. 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
SME should be looked at as one module of a larger cognitive
framework. What SME does is it takes two concepts and finds the best
analogy between them. It makes no claims about retrieval of good
concepts (though the related project MAC/FAC does) or what to do with
the analogy created (though the larger system PHINEAS does). Key to
understanding what SME does and does not do relies on the
understanding that given two concepts one can make multiple mappings
between them. There are many ways to make an analogy between a river
and time, for example, and SME choose among them.
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?
Gentner, D. (1983). Structure-mapping: A theoretical framework for
analogy. Cognitive Science, 7, pp 155-170.
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
AAAI Fall Symposium on Computational Models for Integrating Language
and Vision. 1995.
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!
Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
Last modified: Thu Apr 29 12:41:46 EDT 1999