Elamur Research⌕
☰
home / papers / 1989 / The structure-mapping engine: Algorithm and examples

The structure-mapping engine: Algorithm and examples

Paper · 1989 · Brian Falkenhainer, Kenneth D. Forbus and Dedre Gentner

Summary

The paper presents the Structure-Mapping Engine (SME), a program that computationally models the mapping stage of analogy under Gentner's Structure-mapping theory. In this theory, analogy is driven by shared relational structure, not surface features of objects. A connected system of relations, especially one tied together by higher-order relations such as CAUSE, is preferred over isolated facts (the systematicity principle). SME works as a configurable toolkit. It builds in the requirement that correspondences be one-to-one and structurally consistent. Every other matching constraint comes from user-supplied rules, which propose local correspondences and assign them evidence weights. SME then combines these local pieces into all consistent global interpretations, without backtracking, and scores each one structurally. The authors analyse the algorithm's complexity, demonstrate it on examples from cognitive simulation and machine learning, and compare it with other analogy programs. This matters because it gives psychologists a fast, explicit and adjustable simulator. It also gives AI learning systems an efficient analogy component.

Key points

  • Most steps of the algorithm are polynomial, typically bounded by O(N²). The authors suggest that connectionist-style relaxation could avoid listing every global mapping ("gmap") and bring the whole procedure close to O(N²).
  • The program had been run on more than 40 examples, including the classic water-flow vs. heat-flow analogy.
  • Theory and evaluation are kept separate. Match rules are interchangeable, so researchers can test different evaluation criteria on the same representations, or the same criteria on novice versus expert representations.
  • SME serves as a component of Falkenhainer's PHINEAS, which belongs to the University of Illinois's Automated Physicist Project.
  • The structural evaluation score (SES) is not normalized for domain size, so it cannot compare unrelated analogies. Janice Skorstad is building a programmable evaluator module to address this.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Illinois Urbana-ChampaignUrbana · United States228 works · 74,590 citations🎓University of Illinois SystemUrbana · United States3 works · 1,577 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksPsychology · 1,673 worksExperimental and Cognitive Psychology · 950 works

Cite

Cite as Brian Falkenhainer, Kenneth D. Forbus and Dedre Gentner. 1989. The structure-mapping engine: Algorithm and examples. Artificial Intelligence.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{falkenhainer1989structure,
  title = {{The structure-mapping engine: Algorithm and examples}},
  author = {Brian Falkenhainer, Kenneth D. Forbus and Dedre Gentner},
  booktitle = {Artificial Intelligence},
  year = {1989},
  doi = {10.1016/0004-3702(89)90077-5},
  url = {https://doi.org/10.1016/0004-3702(89)90077-5}
}

References

74 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Allen, D ., Steinberg, S . and Stabile, L . Recent developments in Butterfly Lisp . Proceedings of AAAI-87, Seattle, 1987. find
  2. Anderson, J ., The Architecture of Cognition, Harvard University Press, Cambridge, Mass, 1983. find
  3. Buckley, S ., Sun up to sun down, McGraw-Hill Company, New York, 1979. find
  4. Bundy, A ., The computer modelling of mathematical reasoning, Academic Press, 1983 find
  5. Burstein, M ., Concept formation by incremental analogical reasoning and debugging, in : Proceedings of the Second International Workshop on Machine Learning, University of Illinois, Monticello, Illinois, June, 1983 . A revised version appears in Machine Learning : An Artificial Intelligence Approac… find
  6. Carbonell, J .G ., Learning by Analogy : Formulating and generalizing plans from past experience, in : Machine Learning: An Artificial Intelligence Approach, R .S . Michalski, J .G. Carbonell, and T .M . Mitchell (Eds .), Morgan Kaufman, 1983 . find
  7. Carbonell, J .G ., Derivational analogy in problem solving and knowledge acquisition, in : Proceedings of the Second International Machine Learning Workshop, University of Illinois, Monticello, Illinois, June, 1983 . A revised version appears in Machine Learning : An Artificial Approach Vol . II, R… find
  8. Chi, M .T .H ., R . Glaser, E . Reese, Expertise in problem solving . In R . Sternberg (Ed .), Advances in the psychology of human intelligence (Vol . 1) . Hillsdale, N .J ., Erlbaum, 1982.
  9. Clement, J . Analogy generation in scientific problem solving . Proceedings of the third annual meeting of the Cognitive Science Society, 1981. find
  10. Clement, J . Analogical reasoning patterns in expert problem solving . Proceedings of the fourth annual meeting of the Cognitive Science Society, 1982. find
  11. Collins, A .M ., & Gentner, D . How people construct mental models . In D . Holland and N . Quinn (Eds .) Cultural models in language and thought . Cambridge, England : Cambridge University, 1987. find
  12. DeJong, G . Generalizations based on explanations . Proceedings of the Seventh International Joint Conference on Artificial Intelligence, August, 1981 find
  13. DeJong, G ., and Mooney, R . Explanation-based Learning : An alternative view . Machine Learning, Volume 1, No . 2, 1986 — Explanation-based learning: An alternative view
  14. Diettrich, T ., & Michalski, R .S ., Inductive learning of structural descriptions : evaluation criteria and comparative review of selected methods, Artificial Intelligence 16, 257-294, 1981. find
  15. Falkenhainer, B ., Towards a general-purpose belief maintenance system, in : J .F . Lem-mer (Ed .), Uncertainty in Artificial Intelligence, Volume II, 1987 . Also Technical Report, UIUCDCS-R-87-1717, Department of Computer Science, University of Illinois, 1987. find
  16. Falkenhainer, B ., An examination of the third stage in the analogy process : Verification-Based Analogical Learning, Technical Report UIUCDCS-R-86-1302, Department of Computer Science, University of Illinois, October, 1986 . A summary appears in Proceedings of the Tenth International Joint Conferen… find
  17. Falkenhainer, B ., Scientific theory formation through analogical inference, Proceedings of the Fourth International Machine Learning Workshop, Irvine, CA, June, 1987. find
  18. Falkenhainer, B ., The SME user's manual, Technical Report UIUCDCS-R-88-1421, Department of Computer Science, University of Illinois, 1988. find
  19. Falkenhainer, B ., Learning from Physical Analogies : An adaptive approach to understanding physical observations, Ph .D . Thesis, University of Illinois, (in preparation). find
  20. Falkenhainer, B ., K .D . Forbus, D . Gentner, The Structure-Mapping Engine, Proceedings of the Fifth National Conference on Artificial Intelligence, August, 1986. find
  21. Forbus, K .D ., " Qualitative Reasoning about Physical Processes " , Proceedings of the Seventh International Joint Conference on Artificial Intelligence, August, 1981 . find
  22. Forbus, K .D ., Qualitative Process Theory, Artificial Intelligence 24, 1984. find
  23. Forbus, K .D ., Qualitative Process Theory, Technical Report No . 789, MIT Artificial Intelligence Laboratory, July, 1984. find
  24. Forbus, K . Interpreting measurements of physical systems, in : Proceedings of the Fifth National Conference on Artificial Intelligence, August, 1986. find
  25. Forbus, K . The Qualitative Process Engine, Technical Report UIUCDCS-R-86-1288, Department of Computer Science, University of Illinois, December, 1986. find
  26. Forbus, K .D . and D . Gentner, Learning Physical Domains : Towards a theoretical framework, In Proceedings of the Second International Machine Learning Workshop, University of Illinois, Monticello, Illinois, June, 1983 . A revised version appears in Machine Learning : An Artificial Approach Vol. II… find
  27. Gentner, D ., The structure of analogical models in science, BBN Tech . Report No . 4451, Cambridge, MA ., Bolt Beranek and Newman Inc ., 1980. find
  28. Gentner, D ., Are scientific analogies metaphors?, in : Miall, D ., Metaphor : Problems and Perspectives, Harvester Press, Ltd ., Brighton, England, 1982. find
  29. Gentner, D ., Structure-mapping : A theoretical framework for analogy, Cognitive Science 7(2), 1983. — Structure-mapping: A theoretical framework for analogy
  30. Gentner, D ., Mechanisms of analogy . To appear in S . Vosniadou and A . Ortony, (Eds .), Similarity and analogical reasoning . Presented in June, 1986. find
  31. Gentner, D ., Analogical inference and analogical access, in A . Preiditis (Ed .), Analogica : Proceedings of the First Workshop on Analogical Reasoning, London, Pitman Publishing Co ., 1988 Presented in December, 1986. find
  32. Gentner, D ., & D .R . Gentner, Flowing waters or teeming crowds : Mental models of electricity, In D . Gentner & A .L . Stevens, (Eds .), Mental Models, Erlbaum Associates, Hillsdale, N .J ., 1983. find
  33. Gentner, D ., & R . Landers, Analogical reminding : A good match is hard to find . In Proceedings of the International Conference on Systems, Man and Cybernetics . Tucson, Arizona, 1985. find
  34. Gentner, D . Metaphor as structure-mapping : The relational shift . Child Development, 59, 47-59, 1988. find
  35. Gentner, D ., & C . Toupin, Systematicity and Surface Similarity in the Development of Analogy, Cognitive Science, 1986. find
  36. Gentner, D ., Falkenhainer, B ., & Skorstad, J . Metaphor : The good, the bad and the ugly. Proceedings of the Third Conference on Theoretical Issues in Natural Language Processing, Las Cruces, New Mexico, January, 1987 . find
  37. Ginsberg, M .L ., Non-Monotonic reasoning using Dempster ' s rule, Proceedings of the Fourth National Conference on Artificial Intelligence, August, 1984. find
  38. Greiner, R ., Learning by understanding analogies, Artificial Intelligence 35 (1), 81-125, 1988. find
  39. Hall, R . Computational approaches to analogical reasoning : A comparative analysis . To appear in Artificial Intelligence. find
  40. Hayes-Roth, F ., McDermott, J . An interference matching technique for inducing abstractions, Communications of the ACM, 21(5), May, 1978. find
  41. Hofstadter, D .R ., The Copycat project : An experiment in nondeterministic and creative analogies . M .I .T . A .I . Laboratory memo 755 . Cambridge, Mass : M .I .T ., 1984. find
  42. Hogge, J . Compiling plan operators from domains expressed in qualitative process theory, Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, WA, July, 1987. find
  43. Holland, J .H ., Holyoak, K .J ., Nisbett, R .E ., & Thagard, P ., Induction : Processes of inference, learning, and discovery, 1987. find
  44. Holyoak, K .J . The pragmatics of analogical transfer . In G .H . Bower (Ed .), The psychology of learning and motivation . Vol. I. New York : Academic Press, 1984. find
  45. Holyoak, K .J ., E .N . Juin, D .O . Gillman (in press) . Development of analogical problem-solving skill . Child Development. find
  46. Indurkhya, B ., "Constrained Semantic Transference : A formal theory of metaphors," Technical Report 85/008, Boston University, Department of Computer Science, October, 1985. find
  47. Kedar-Cabelli, S ., Purpose-Directed Analogy. Proceedings of the Seventh Annual Conference of the Cognitive Science Society, Irvine, CA, 1985. find
  48. Kedar-Cabelli, S . T . (in press) . Analogy : From a unified perspective . To appear in D . H. Heiman (Ed .), Analogical reasoning : Perspectives of artificial intelligence, cognitive science, and philosophy . Dordrecht, Nolland : D . Reidel Publishing Company. find
  49. Kline, P .J ., "Computing the similarity of structured objects by means of a heuristic search for correspondences", Ph .D . Thesis, Department of Psychology, University of Michigan, 1983. find
  50. Larkin, J .H . Problem representations in physics . In D . Gentner & A .L . Stevens (Eds .) Mental Models. Hillsdale, N .J ., Lawrence Erlbaum Associates, 1983. find
  51. Michalski, R .S ., " Pattern recognition as rule-guided inductive inference " IEEE Transactions on Pattern Analysis and Machine Intelligence 2(4), pp . 349-361, 1980. find
  52. Plotkin, G .D ., Building in equational theories, in : Michie, D . (Eds .), John Wiley & Sons, 1972. find
  53. Prade, H ., "A synthetic view of approximate reasoning techniques," Proceedings of the Eighth International Joint Conference on Artificial Intelligence, 1983 . Machine Intelligence 7, Meltzer, B . & find
  54. Raulefs, P ., Siekmann J ., Szabo, P ., & Unvericht, E ., A short survey on the state of the art in matching and unification problems, ACM SIGSAM Bulletin 13(2), 14-20, May, 1979. find
  55. Rajamoney, S ., DeJong, G ., and Faltings, B . Towards a model of conceptual knowledge acquisition through directed experimentation . Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, CA, August, 1985. find
  56. Rattermann, M .J ., and Gentner, D . Analogy and Similarity : Determinants of accessibility and inferential soundness, Proceedings of the Cognitive Science Society, July, 1987. find
  57. Reed, S .K ., A Structure-mapping model for word problems . Journal of Experimental Psychology : Learning, Memory, and Cognition, 13(1), 124-139, 1987. find
  58. Ross, B .H ., Remindings and their effects in learning a cognitive skill, Cognitive Psychology, 16, 371-416, 1984. find
  59. Rumelhart, D .E ., & Norman, D .A ., Analogical processes in learning . In J .R . Anderson (Ed .), Cognitive skills and their acquisition, Hillsdale, N .J ., Erlbaum, 1981. find
  60. Shafer, G ., A mathematical theory of evidence, Princeton University Press, Princeton, New Jersey, 1976. find
  61. Shavlik, J .W . Learning about momentum conservation . Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, CA, August, 1985 find
  62. Stickel, M . A complete unification algorithm for associative-commutative functions, in : Proceedings of IJCAI-75, Tbilisi, Georgia, USSR, 71-76, 1975. find
  63. Tversky, A . Representation of structure in similarity data : Problems and prospects . Psychometrika 39, 373-421, 1974. find
  64. Skorstad, J ., A structural approach to abstraction processes during concept learning, Master's Thesis, 1988. find
  65. Skorstad, J ., Falkenhainer, B ., Gentner, D ., Analogical Processing : A simulation and empirical corroboration, in : Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, WA, August, 1987. find
  66. Van Lehn, K . & J .S . Brown, Planning nets : A representation for formalizing analogies and semantic models of procedural skills . In R .E . Snow, P.A . Federico & W .E . Montague (Eds .), Aptitude, learning and instruction : Cognitive process analyses. Hillsdale, N .J . Erlbaum, 1980. find
  67. Van Lehn, K ., "Felicity conditions for human skill acquisition : Validating an AI-based theory," Xerox Palo Alto Research Center Technical Report CIS-21, 1983. find
  68. Vere, S ., "Induction of concepts in the predicate calculus", Proceedings of the Fourth International Joint Conference on Artificial Intelligence, 1975. find
  69. Vere, S ., "Inductive learning of relational productions", In Waterman & Hayes-Roth (Eds .), Pattern-Directed Inference Systems, 1978 . find
  70. Vosniadou, S ., On the development of metaphoric competence . University of Illinois: Manuscript submitted for publication, 1985. find
  71. Waltz, D .L . & Pollack, J .B ., Massively Parallel Parsing : A strongly interactive model of natural language interpretation, Cognitive Science 9, 51-74, 1985. find
  72. Winston, P.H ., Learning structural descriptions from examples, Ph .D . thesis, Report AI-TR-231, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, 1970. find
  73. Winston, P .H ., Learning and Reasoning by Analogy, Communications of the ACM, 23(12), 1980.
  74. Winston, P .H ., Learning new principles from precedents and exercises, Artificial Intelligence, 19, 321-350, 1982 . find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/falkenhainer-1989-structure-mapping-engine-algorithm-examples/