Max H. Garzon - 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.

The Tutoring Research Group at the University of Memphis has developed a computer tutor (called AutoTutor) that simulates the discourse patterns and pedagogical strategies of unaccomplished human tutors. The typical tutor in a school system is unaccomplished in the sense that the tutor has had no training in tutoring strategies and has only introductory-to-intermediate knowledge about the topic. The development of AutoTutor was funded by an NSF grant (SBR 9720314, in the Learning and Intelligent Systems program). The discourse patterns and pedagogical strategies in AutoTutor were based on a previous project that dissected 100 hours of naturalistic tutoring sessions.

AutoTutor is currently targeted for college students in introductory computer literacy courses, who learn the fundamentals of hardware, operating systems, and the Internet. Instead of merely being an information delivery system, AutoTutor serves as a discourse prosthesis or collaborative scaffold that assists the student in actively constructing knowledge. AutoTutor presents questions and problems from a curriculum script, attempts to comprehend learner contributions that are entered by keyboard, answers student questions, formulates dialog moves that are sensitive to the learner's contributions (such as short feedback, pumps, prompts, assertions, corrections, and hints), and delivers the dialog moves with a talking head. The talking head displays emotions, produces synthesized speech with discourse-sensitive intonation, and points to entities on graphical displays. AutoTutor has seven modules: a curriculum
script, language extraction, speech act classification, latent semantic analysis (a statistical representation of domain knowledge), topic selection, dialog management, and a talking head. Evaluations of AutoTutor have shown that the tutoring system improves learning with an effect size that is comparable to typical human tutors in school systems, but not as high as accomplished human tutors and intelligent tutoring systems. The dialog moves of AutoTutor blend in the discourse context very smoothly because students cannot distinguish whether a speech act was generated by AutoTutor or a human tutor.

The proposed research will substantially expand the capabilities of AutoTutor by designing the discourse to handle more sophisticated tutoring mechanisms. These mechanisms should further enhance the active construction of knowledge. One enhancement is to get the student to articulate more knowledge, with more formal, symbolic, and precise specification; if the student doesn't say it, it is not considered covered by AutoTutor. Another enhancement is to set up the dialog so that it guides the user in manipulating a 3-dimensional microworld of a physical system; the student attempts to simulate a new state in the physical system by manipulating parameters, inputs, and formulae. The proposed research will develop AutoTutor in the domains of both computer literacy and Newtonian physics, so we will have some foundation for evaluating the generality of AutoTutor's mechanisms. AutoTutor has been designed to be generic, rather than domain-specific; an authoring tool will be developed that makes it easy for instructors to prepare new material on new topics. After the new versions of AutoTutor are completed, we will evaluate its effectiveness on learning gains, conversational smoothness, and pedagogical quality. During the course of achieving these engineering and educational objectives, the proposed project will
conduct basic research in cognitive psychology, discourse processes, computer science, and
computational linguistics. This research cuts across quadrant 2 (behavioral, cognitive, affective, and social aspects of human learning) and quadrant 3 (SMET learning in formal and informal educational settings).