A Selection of Topics for Bachelor-/Master-Theses supervised by Ute Schmid (http://www.inf.uos.de/schmid) Feb., 27, 2003 Topics are in the domains of symbolic AI and cognitive psychology -- most topics address both areas. Most topics can be adjusted in complexity for bachelor or master theses. If a topic is only suitable for bachelor OR master, it is marked as such. I just give very short descriptions of the topics -- for more information, refer to my homepage (current and finished theses, publications, research) or contact me directly. Please note that for some topics given below there are already interested students. Mostly, the topics are broad enough for more than one thesis (with different focus). ========================================================================== (1) Structural Similarity in Analogical Transfer In some psychological experiments, I could show that the ``size of structural overlap'' between a base and a target problem has an impact on transfer success where structural overlap is calculated with a measure of graph distance. The original studies were done in the domain of water jug problems. Follow-up studies should be done in new domains, exploiting a larger range of structural similarities. - Focus: cognitive psychology - Relation to AI: graph metrics - see: Schmid, Wirth & Polkehn (2003). A closer look on structural similarity in analogical transfer. Cognitive Science Quarterly. --------------------------------------------------------------------------- (2) Transfer of Solitaire Experience to the Tower of Hanoi Domain Tower of Hanoi is very well researched in cognitive psychology, AI, and computer science -- but, there are only few studies on Tower of Hanoi isomorphs in the context of analogical problem solving (Simon & Hayes, 1976, Clement & Richard, 1997). Some games of Solitaire can be solved with rules which are structurally very similar to Tower of Hanoi. A study could be conducted where subjects without/with experience in Solitair playing must solve Tower of Hanoi. Hopefully, subjects with Solitair experience should show a significantly better performance. - Focus: cognitive psychology - Relation to AI: formalize the rules of a suitable variant of Solitaire and show the isomorphism - see: literature named in the abstract --------------------------------------------------------------------------- (3) Derivational vs. Transformational Analogy Cognitive models of analogy are typically transformational: Based on a structure mapping of base and target, entities of the base are transferred to the target suuch that the structural relations are preserved. In AI, an alternative, derivational, approach was proposed: For a new (target) problem, a base problem with similar problem solving goals is retrieved and the solution is step-wisely replayed. I have the hypothesis, that humans can use both strategies. Transformational analogy should be applied if there are semantic/pragmatic constraints for mapping of objects, otherwise derivational analogy should be preferred. In a pilot study I could show that for problems with no mapping constrains, subjects use derivational analogy. I am currently working on a follow-up experiment, where base/target pairs with no vs. many mapping constraints are prepared. - Focus: cognitive psychology and cognitive modeling - Relation to AI: derivational analogy - Current cooperation: with Jackie Griego and Peter Gerjets (IWM, Tuebingen) - see: Schmid and Carbonell (1999). Empirical Evidence for Derivational - Analogy. CogSci'99 and KogWiss'99. ==> probably assigned as bachelor thesis --------------------------------------------------------------------------- (4) Learning from Predictive Analogies in the Domain of Physics (as master thesis only) Predictive analogies are the typical example of analogical reasoning: knowledge from one domain is transferred to a new domain to provide for explanations. Predictive analogies are mostly researched in naive physics (heat flow/water flow, Rutherford analogy) and Gentner's SME model is focussed on this kind of analogy. The problem of SME is, that a domain is represented as a graph structure and analogy is performed by a simple object-to-object mapping. Alternatively, I propose ``anti-unification'' as an approach to analogy. Here, mapping is performed via abstraction over the common structure of base and target. This model has several advantagtes: no combinatorial explosion due to sub-graph mapping, guidance of mapping by the common role of objects, generalization learning occurs as a side effect. In addition, Helmar Gust and Kai-Uwe Kuehnberger proposed to get rid of the brittle, representation of domains and allow for inferences and physical experiments to enrich some initial representation. A very interesting experiment, best performed in a high-school in collaboration with a teacher of physics, would be to let high-school students (with no knowledge in physics) solve the heat flow/water flow analogy after the SME model (that is, receive some info about the base domain and transfer it to the target) vs. give them just some basic information and let them experiment. We suppose that the second group will show a much better understanding of both domains and a better rate of transfer. - Focus: cognitive psychology and cognitive modeling - Relation to AI: Anti-unification - Current cooperation: with Helmar Gust and Kai-Uwe Kuehnberger - see: Schmid, Gust, Kuehnberger & Burghardt: An algebraic approach to - proportional and predictive analogies, submitted --------------------------------------------------------------------------- (5) Re-Representation Processes in Solving Proportional Analogies Douglas Hofstadter proposed the Copycat model to solving proportional analogies in string domains, such as `abc : abd == kji : ?'. Although his model is somewhat critisized by cognitive science researchers, most agree that the model has one feature which is crucial to analogical reasoning and which the other analogy models do not cover: the ability to re-represent structures such that a suitable mapping can be obtained. E.g., `abc' might be represented as three letters or as an increasing sequence of three letters. There are some further AI models dealing with this aspect of analogy (PAN, O'Hara, 1992; Indurkhya, 1992) -- but up to now there are no experimental data showing that human reasoners re-represent initial descriptions. - Focus: cognitive psychology and cognitive modeling - Relation to AI: Analogy models with re-description - see diploma thesis by Martin Muehlpfordt, Repraesentationsprozesse beim Analogen Schliessen (1999) --------------------------------------------------------------------------- (6) Implicit Learning of Grammars with Recursive Rules Inductive inference is often studied in the domain of learning artificial grammars. Subjects get presented ``words'' of a language (this can be strings, icons, pseudo-sentences) and later on are presented new words and must decide whether they belong to the learn language or not. Typically, artificial grammars for regular languages are investigated. Even for this most simple formal grammar, results from learning theory show that such languages cannot be learned efficiently from positive examples only. Learning theory assumes that the example words are presented in some arbitrary order. In contrast, in natural settings, a language is not learned by random examples but in a more systematic way. An experiment for learning a regular and a context-free language could be conducted where radom presentation is contrasted with some training regime (based on structural information theory). - Focus: cognitive psychology and cognitive modeling - Relation to AI: grammar inference - Possible cooperation with Jochen Trommer (Learning of morphem grammars) - see: Gold, 1967, Language identification in the limit; Osherson, Stob, Weinstein, 1986, Systems that learn; Poletiek, 2002, Implicit learning of a recursive rule in an artificial grammar --------------------------------------------------------------------------- (7) Learning Spatial Maps from Exploratory Navigation Typically, robots use fixed maps for route planning in navigation tasks. If route/map learning is investigated, it is on a basic level, connecting uninterpreted sensory data with navigation behavior. I am interested in high-level learning of maps from navigation experience. Imagine, that you start to shop in a newly opened supermarket where the goods are ordered in a way completly unknown to you. The first time you search for some goods (say apples, coffee and milk), you store their positions and maybe also goods you passed during search in memory. After a second shopping experience you can integrate both routes into a partial map. As more often you go shopping as more detailled your map becomes. Since typically you do not have absolute coordinates, the main problem in map learning is integrating routes into a single map. The goal is to provide a simulation system together with a variety of algorithms for exploration, map learning and map usage for navigation. - Focus: AI (mainly implementation) - Relation to psychology: experimental data on route and map learning in humans and animals - see: diploma thesis of Karin Boehnke, Gewinnung und Nutzung von Routen- und Ueberblickwissen bei der Navigation (2001) --------------------------------------------------------------------------- (8) Modeling Spatial Inferences Text understanding in a spatial domain is often seen as the construction of a mental model. In an DFG project we developed a first prototype of a program that realizes some of the characteristics claimed for spatial reasoning processes in mental models. Our work is based on homogeneous coordinate systems and transformation matrices. This means that a relation between two objects `A' and `B' is represented by the transformation matrix that maps the coordinate system of `A' onto that `B'} and by constraints on the parameters of the matrix. Objects and relations explicitely given in a text are represented as a graph with objects as nodes and relations as arcs. Inference of a relation between two objects is performed by connecting the relational information along the arcs between these objects. Based on the graph, a visualization of the described scene can be constructed. Because natural language descriptions are underspecified with respect to spatial locations, a ``prototypical'' visualization should be constructed. - Focus: AI/constraint solving (algorithm development and implementation) - Relation to psychology: Theory of Mental Models, preferred models - see: Schmid, U., Wiebrock, S., and Wysotzki, F. (2000). Modelling Spatial Inferences in Text Understanding. In S. O'Nuallain (Ed.), Spatial Cognition (pp. 285-298). Advances in Consciousness, Vol. 26, Amsterdam: John Benjamins. --------------------------------------------------------------------------- (9) Inductive Synthesis of Recursive Program Schemes with Nested Function Calls (as master thesis only) In the context of the system IPAL (http://www.inf.uos.de/schmid/ipal.html) we investigate how finite terms can automatically be generalized into recursive programs. Our current formal framework and implementation does not allow to infer programs with nested function calls. The theoretical framework and the algorithms should be extended accordingly. - Focus: AI/Program Synthesis (formal framework based on term algebras, algorithm development and implementation) - Relation to psychology: inductive learning, grammar learning - see Kitzelmann, E., Schmid, U., Muehlpfordt, M., and Wysotzki, F. (2002). Inductive synthesis of functional programs. In J. Calmet, B. Benhamou, O. Caprotti, L. Henocque, V. Sorge (Eds.), Artificial Intelligence, Automated Reasoning, and Symbolic Computation, Joint International Conference, AISC 2002 and Calculemus 2002 Marseille, France, July 1-5, 2002, pp. 26-37, Springer, LNAI 2385. --------------------------------------------------------------------------- (10) Solving Proportional Analogies with E-Anti-Unification There are some computational approaches for solving proportional analogies (see topic 5). We propose to use anti-unification as a formally sound and powerful approach. Most important re-representations must not be calculated and tested sequentially, but, given an equalition theory, all possible representations can be considered simultaneously. Jochen Burghardt worked out this approach for inductive reasoning intelligence test tasks and we presented an algorithm how anti-unification can be applied to proportional analogy (as a special case of inductive reasoning). The algorithm should be implemented and tested for the string domain examples found in literature. - Focus: AI/cognitive modeling (formal framework based on term algebras, implementation) - Relation to psychology: experiments and models for proportional analogy - see: Schmid, U., Burghardt, J., and Wagner, U. (submitted). Analogy needs abstraction. --------------------------------------------------------------------------- (11) Universal Planning with OBDDs In the context of the system IPAL (http://www.inf.uos.de/schmid/ipal.html) we investigate universal planning. Since universal planning is based on breadth-first search it is not time and especially not space efficient. Ordered binary decision diagrams are a compact way to represent planning states and some planners already use this form of representation. Either DPlan should be extended to deal with OBDD representations or another universal planner should be adapted for the demands of planning in IPAL. - Focus: AI/Planning (planning algorithms and implementation) - Relation to psychology: only indirect via IPAL - see: Schmid, U. and Wysotzki, F. (2000). Applying inductive program synthesis to macro learning. In S. Chien, S. Kambhampati, and C.A. Knoblock (Eds.), Proceedings of the AIPS 2000, Breckenridge, CO, April 2000, (pages 371-378), AAAI Press. --------------------------------------------------------------------------- (12) Memory Organization and Retrieval for Programming by Analogy Programming by analogy can be seen as a special case of problem solving by analogy: A new programming problem is given either by examples or by specification and the (typically recursive) solution is generated by mapping the new problem to an already solved problem and transferring the solution. In the context of the system IPAL (http://www.inf.uos.de/schmid/ipal.html) we learn recursive program schemes. We propose an approach for hierarchical memory organization which is based on the notion of term subsumption. Based on this proposal an algorithm for memory organization and retrieval should be designed, implemented and tested. - Focus: AI/Analogy (subsumption hierarchies, algorithms for memory org. and retrieval) - Relation to psychology: Learning of problem solving schemes - see: Schmid, U. (1997). Programmieren durch analoges Schliessen. Kognitionswissenschaft, Sonderheft "Analoges Schliessen", 6 (3), 127-134. Schmid, U., Sinha, U., and Wysotzki, F. (2001). Program reuse and abstraction by anti-unification. In G. Stumme et al.: Professionelles Wissensmanagement -- Erfahrungen und Visionen (pp. 183-185). Shaker. (German Workshop of Case-Based Reasoning (GWCBR2001) im Rahmen der WM 2001, 15-16 March, Baden-Baden.) --------------------------------------------------------------------------- (13) Planning by Analogy In the context of the system IPAL (http://www.inf.uos.de/schmid/ipal.html), programming by analogy can be used in combination with planning: First, a plan for a small domain (say transporting three objects) is generated, then this plan is trannsformed into a finite term. The finite term is compared with recursive program schemes in memory and a generalized/recursive function which solves more general problems (say transporting n objects) is constructed by analogical transfer. Since planning an plan transformation are costly, it would be more efficient to use analogical transfer directly for the planning domains. Some work in this direction was done by Fox and Long (2000) who proposed how to detect invariants in planning domains. - Focus: AI/Planning/Analogy - Relation to Psychology: only indirect via IPAL - see: M.Fox and D.Long 2000 Utilizing Automatically Inferred Invariants in Graph Construction and Search International Conference on AI Planning and Scheduling, AIPS 2000, Breckenridge, Colorado, USA. and diploma thesis by Bernhard Wolf ==> probably assigned as bachelor thesis --------------------------------------------------------------------------- (14) Learning XSL Transformations from Example Documents We developped a quite powerful method for folding of finite terms into recursion (see topic 9). Folding is used to construct a recursive program based on regularities detected in the finite term (which was constructed from examples). We demonstrated the usefulness of this approach in the domain of planning (learning recursive control-rules) and just started to apply folding to learning XSL Transformations with recursive template applications. We used a genetic programming approach to generate initial transformations which exactly transform a given input XML into the desired ouutput. This initial XSL is input in the folder. Based on our initial results, the approach should be applied to a larger variety of XSL problems and the approach should be modified for more efficiency (genetic programming should be done ``in parallel''). - Focus: AI/programming by demonstration - Relation to Psychology: only indirect (generalization learning, HCI) - see: Schmid, U. and Waltermann, J. (submitted). Automatic Synthesis of XSL-Transformations from Example Documents. --------------------------------------------------------------------------- (15) Learning Strategies for Interactive Games In the context of the system IPAL (http://www.inf.uos.de/schmid/ipal.html) we learn domain-specific control rules from planning. An alternative approach to control-rule learning (called policy or strategy learning) is reinforcement learning (Sutton & Barton, 1998). A student project in the computer science department developped an interactive game (http://sourceforge.net/projects/ugaagga). In the long run it would be interesting, to allow that artificial agents can participate in the game to study the power of different learning algorithms. As a first step, an agent should be constructed who is able to interact with the game and who learns a strategy for a small subset of the game. Because the log-files for the game are available it would also be possible to study human strategy learning and compare it with the artificial agent. - Focus: AI/reinforcement learning - Relation to Psychology: strategy learning - see: A. E. Roth and I. Erev. Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review, 88(4):848--881, 1998. ==> probably assigned as bachelor thesis ===========================================================================