Stanley P. Franklin - US grants

In this REU site project, six students will work on problems arising in graph theory and its application to computer science. Research involving five themes will be open to the students. They are: Ramsey-minimal graphs for matching; Menger path systems; efficient graph labelings and embeddings; frequency of an induced subgraph and automata networks. All students will be provided with the necessary background, insuring that the proposed problems in these areas will be within the reach of undergraduates. The study of Ramsey-minimal graphs relates to coloring of graphs in two colors in ways that cannot be achieved by any subgraphs and the number of possible such decompositions. Menger path systems analyze graphs in which the number of paths which connect each pair of vertices is given, while graph labeling is concerned with symplectic embeddings or representations of graphs in possibly larger graphs in Euclidean spaces. Automata networks are models of computer networks used in the analysis of parallel algorithms and parallel processing systems which have particular application to neural networks, associative memories and learning.

The existence of a universal neural network, AMNIAC, developed by the principal investigators for theoretical reasons, raises the possibility of implementing a general purpose neurocomputer, i.e., one which may be "programmed" to behave like any other neural network. Such general purpose neurocomputers will run different neural networks on the same hardware like our serial computers run programs today. A general purpose neurocomputer should include capabilities beyond those of a universal neural network. Most important among these are efficient massive storage, rapid retrieval, learning, and sophisticated input/output. The goal of this project is to simulate AMNIAC on a massively parallel computer. This simulation will allow the design of adequate massive storage, learning and input/output capabilities. It will also allow benchmarks to provide reliable estimates of the feasibility and efficiency of an actual general purpose neurocomputer.

This project is being funded through the Learning and Intelligent Systems (LIS) Initiative. The long-term practical objective of the research is to develop a fully automated computer tutor. The tutor would be able to (a) extract meaning from the contributions that the student types into a keyboard and (b) formulate dialog contributions with pedagogical value and conversational appropriateness. The tutor's discourse moves include: pumping, prompting, hinting, questioning, answering, summarizing, splicing in correct information, providing immediate feedback, and rewording student contributions. The dialog contributions of the tutor would be in different formats and media: printed text, synthesized speech, simulated facial movements, graphic displays, and animation. Such an achievement will require an interdisciplinary integration of theory and empirical research from the fields of cognitive psychology, discourse processing, computational linguistics, artificial intelligence, human-computer interaction, and education. The tutoring topics will be in the domains of computer literacy and introductory medicine. Previous attempts to develop a fully automated tutor have been seriously challenged by some technical and theoretical barriers. These include (a) the problem of interpreting natural language when it is not well-formed semantically and grammatically, (b) the problem of world knowledge being immense, open-ended and incomplete, and (c) the lack of research on human tutorial dialog. Recent advances have dramatically reduced these barriers, so it is time to revisit the mission of developing an automated tutor. According to the recent research on human tutoring, a key feature of effective tutoring lies in generating discourse contributions that assist learners in actively constructing explanations, elaborations, and mental models of the material. The proposed research will advance scientific understanding of how a tutor can manage a smooth, polite dialog that promotes deep learning of the material.

This research investigates emotions during the process of learning and reasoning while college students interact with complex learning environments. College students learn about introductory computer literacy or conceptual physics on the web by an intelligent tutoring system, called AutoTutor. AutoTutor helps learners construct explanations that answer difficult questions by interacting with them in natural language and by helping them use simulation environments. AutoTutor has an animated conversational agent and a dialog management facility that attempts to comprehend the learner's contributions and to respond with appropriate dialog moves (short feedback, pumps, hints, prompts for information, assertions, answers to student questions, suggestions for actions, summaries). The emotions of the learner are monitored during this learning process by integrating state-of-the-art affect sensing technology with AutoTutor. Confusion, frustration, boredom, interest, excitement, and other learner emotions are classified on the basis of facial actions, body posture, pressure on the mouse, speech acts in dialog, mastery of the material, and the timing of interactions. One strand of research develops the affect-sensing technologies and tests their validity in classifying the learner emotions. A second line of research investigates whether learning gains and learner impressions are influenced by dialog moves of AutoTutor that are constrained by the learner's emotional state.

This research will advance education and natural language dialog technologies through a system that promotes deep learning of material in a fashion that is sensitive to the learners' emotions. A learning environment that monitors learner emotions is likely to be more motivating and personally relevant to the learner.