Analogical Problem Solving and Schema Induction


Anti-unification as Approach to Automated Analogical Reasoning and Generalization

Reasoning by analogy is an approach to problem-solving and learning where knowledge aquired in previous problem solving episodes is applied for solving new, similar, problems. More abstract knowledge structures can be derived by generalizing over structurally similar problems, such that with increasing expertise in a domain analogical reasoning can be replaced by applying abstract rules. Especially in complex domains as mathematical proofs or program development, where fully automated general inference methods can only be applied in a very restricted way, analogical reasoning can be a helpful alternative for practical applications. In cognitive science, the ability to analogical reasoning is seen as one of the central characteristics of human intelligence. Numerous cognitive theories and some implemented cognitive models exist. Goal of our research is, to formalize this cognitive models in a unifying apporach. Anti-unification offers a suitable formal backbone, because it allows to solve analogy problems with a method where generalization of common problem structures occurs as a side-effect of inference. Anti-unification modulo equational theories allows to include background knowledge for generating sets of alternative problem representations in a natural way. It is planned to implement this approach and evaluate it in selected domains, such as intelligence test tasks and automatic programming. Description
current: past:
  • Ulrich Wagner

Forschungsförderung 2005:
Effiziente Implementation eines Algorithmus zum Lösen von Proportionalanalogien.
Projekt-Nr. 070121-51

  • Gust, H.; Kühnberger, K.-U.; Schmid, U.: Ontologies as a Cue for the Metaphorical Meaning of Technical Concepts. In Schalley, Andrea C. and Khlentzos, Drew (eds.): Mental States: Evolution, Function, Nature (Vol. I). Amsterdam/Philadelphia: John Benjamins, to appear.
  • Weller, S.; Schmid, U.: Solving proportional analogies by E-generalization. 29th annual German Conference on Artificial Intelligence, Bremen, June 14--19, 2006. [pdf]
  • Weller, S.; Schmid, U.: Analogy by abstraction. ICCM, Trieste, 5-8 April 2006. [pdf]
  • Gust, H.; Kühnberger, K.-U.; Schmid, U.: Metaphors and Heuristic-Driven Theory Projection (HDTP), Theoretical Computer Science, 354 (1), 98--117, 2006.
  • Stephan Weller (bachelor student, cognitive science, Osnabrück): Solving Proportional Analogies with E-Generalization (June 2005) [pdf]
  • Gust, H.; Kühnberger, K.-U.; Schmid, U.: Ontologies as a Cue for the Metaphorical Meaning of Technical Concepts. International Language and Cognition Conference, ILCC 2004 (Univ. of New England, Australia, Sept. 10-12), 2004. [abstract, pdf]
  • Gust, H.; Kühnberger, K.-U.; Schmid, Ute: Anti-unification of axiomatic systems. Work in progress report. Osnabrück: Universtität Osnabrück. 2003. - Interner Bericht. [ps]
  • Gust, H.; Kühnberger, K.-U.; Schmid, Ute: Algebraic Models of Reasoning. In: Gust, H., Kühnberger, K.-U., Rollinger, C., Schmid, U. (Eds.): Proceedings of the Workshop Algebraic Models of Reasoning (KI 2003 Hamburg 14.-18. Sept. 2003). 2003, pp. 5 - 20. [Proceedings, pdf, 61 pages]
  • Gust, H.; Kühnberger, K.-U.; Schmid, U.: Coalgebras and Reasoning, In H. Gust, K.-U. Kühnberger, C. Rollinger and U. Schmid (Eds.), Proceedings of the Workshop "Algebraic Models of Reasoning" (KI 2003 Hamburg 14.-18. Sept. 2003). 2003, pp. 49 - 59.[Proceedings, pdf, 61 pages]
  • Schmid, Ute; Gust, H.; Kühnberger, K.-U.; Burghardt, J.: An Algebraic Framework for Solving Proportional and Predictive Analogies. In: Schmalhofer, F.; Young, R.; Katz, G. (Hrsg.): Proceedings of the European Conference on Cognitive Science (EuroCogSci 2003 Osnabrück 10.-13. September 2003). Mahwah, NJ: Lawrence Erlbaum, 2003, S. 295-300. [pdf, 6 pages]
  • Gust, H.; Kühnberger, K.-U.; Schmid, Ute: Metaphors and Anti-Unification. In: Spoto, F.; Scollo, G.; Nijholt, A. (Hrsg.): Algebraic Methods in Language Processing - AMiLP-3 (AMiLP-3 Verona, Italy 25-27 August 2003). Bd. 21. Twente: University of Twente, 2003, S. 111-123. Bd. TWLT, Nr. 21. [pdf, 13 pages]
  • Gust, H.; Kühnberger, K.-U.; Schmid, Ute: Solving Predictive Analogy Tasks with Anti-Unification. In: Slezak, P. (Hrsg.): Joint International Conference on Cognitive Science (ICCS/ASCS-2003 Sydney, Australia 13 - 17 July 2003). 2003. [pdf, 6 pages]
  • Schmid, U., Burghardt, J., and Wagner, U. (2003). Anti-unification as an approach to analogical reasoning and generalization. (Poster Abstract) Fifth International Conference on Cognitive Modeling, ICCM'03 (April 10 - 12,2003, Bamberg, Germany). [Postscript, 2 pages]
  • Ulrich Wagner (diploma student, computer science, TU Berlin): Combinatorically Restricted Higher Order Anti-Unification -- An Application to Programming by Analogy (April 2002) [Web-Page]


Empirical Investigation of Analogical Strategies in Human Problem Solvers

Typically, analogical reasoning is described as a transformational process, where the structure of a known base problem is mapped onto the (partial) structure of a new target problem. Giving the mapping result, the base structure is transferred in the target domain by replacing objects in the base by corresponing objects in the target. In the AI research of the eighties, derivational analogy was proposed as an alternative strategy by Carbonell: A target problem is solved by a replay of the (reinstantiated) solution process of the base problem. Up to now next to no empirical evidence is given that human problem solvers can employ not only transformational but also derivational problem solving strategies. In two empirical studies we could show that given specific problem characteristics one or the other stratey is triggered. Based on this preliminary evidence we plan to conduct further studies investigating the conditions under which transformational or derivational analogy is triggered. We plan to implement a simulation model which realizes both strategies. Description
current: past: Collaborators
  • Gerjets, P.; Scheiter, K.; Kleinbeck, S.; Schmid, Ute: Learning from transformational and derivational worked-out examples. In: Gray, W. D.; Schunn, C. D. (Hrsg.): Proceedings of the 24th Annual Conference of the Cognitive Science Society (24th Conference of the Cognitive Science Society George Mason University, Washington, D.C. August 7-11th). Mahwah, NJ: Erlbaum, 2002, S. 1004. (Member abstract). [pdf, 1 page]
  • Kleinbeck, S.; Gerjets, P.; Scheiter, K.; Schmid, Ute: Impact of different example formats on solving isomorphic and novel problems (Summary). In: EARLI'01 (Hrsg.): Proceedings of the 9th European Conference for Research on Learning and Instruction (9th European Conference for Research on Learning and Instruction Schweiz, Fribourg, 28.8.-1.9. 2001). 2001. [pdf, 1 page]
  • Kleinbeck, S.; Gerjets, P.; Scheiter, K.; Schmid, Ute: Einfluss derivationaler und transformationaler Beispielformate auf Beispielnutzung und Problemlöseleistung. In: Zimmer, A. et al. (Hrsg.): Proceedings der 43. Tagung experimentell arbeitender Psychologen (TeaP, Regensburg, 9.- 11.4. 2001). 2001. [pdf, 9 pages]
  • Schmid, U. and Carbonell, J. (1999). Empirical Evidence for Derivational Analogy (Poster Abstract). In M. Hahn and S. C. Stoness (Eds.), Proceedings of the 21st Annual Conference of the Cognitive Science Society (August 19-21, 1999; Simon Fraser University, Vancouver, British Columbia), p. 814, Lawrence Erlbaum. [Abstract (PS)] [Long Version (PS)] [Poster (A1, postscript)]
  • Schmid, U. and Carbonell, J. (1999). Empirical Evidence for Derivational Analogy. In I. Wachsmuth and B. Jung (Eds.), Proc. der 4. Fachtagung der Gesellschaft f. Kognitionswissenschaft (28.9. - 1.10.99, Bielefeld), pages 116-121. infix. [Postscript]
  • Sven-Eric Schelhorn (bachelor student, cognitive science, Osnabrück): Empirical Evidence for the Use of Derivational Strategies in Analogical Problem Solving (December 2003) [pdf, 93 pages]


Empirical Demonstration of Re-representation of Problem Structures During Analogy Making

Analogy making is a creative and flexible cognitive process. The way in which the structure of a problem (or concept) is represented determines the outcome of the analogy and often the initial preferred representation of a problem needs to be changed to find a suitable mapping to an old problem (known concept). For example, the natural number "4" might be represented as "4", "2+2", "2^2" and so on. Our research is concerned with the empirical study of what triggers re-representation in human problem solvers and of integrating re- representation in a natural way in automated analogy systems. Description
current: past:
  • Martin Mühlpfordt
  • Julia Jira
  • Julia Jira (bachelor student, cognitive science, Osnabrück): Re-Representation Processes in Analogical Reasoning (June 2004)
  • Computing Analogies. In: M. Lovett, C. Schunn, C. Lebiere, and P. Munro (Eds.) Proceedings of the 6th International Conference on Cognitive Modeling (ICCM-2004). Mahwah, NJ: Lawrence Erlbaum. pp. 350-351. [abstract, pdf ]