FACULTY RESEARCH GUIDE 1999-00 Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 (412) 268-2565

This file presents the current research interests of the faculty members of the Carnegie Mellon Doctoral Program in Computer Science, along with those of associated faculty of other departments. Each person listed has written his or her own section of the Guide. There has been no attempt to eliminate redundancy by combining descriptions of related work. In addition to the research descriptions, indices at the end of the document list the faculty by interest keywords, and by project names.

The primary purpose of the Guide is to acquaint new and prospective members of our community, especially graduate students, with the on-going research and with the faculty involved. We also use the Guide to inform outside colleagues and visitors, and to direct those looking for persons knowledgeable about any particular topic.

The goal of my research is to understand how people organize knowledge that they acquire from their diverse experiences to produce intelligent behavior. The concern is very much with how it is all put together and this has led to the focus on what are called "unified theories of cognition." A unified theory is a cognitive architecture that can perform in detail a full range of cognitive tasks. Our theory is called ACT-R (Anderson & Lebiere, 1998) and takes the form of a computer simulation which is capable of performing and learning from the same tasks that subjects in our laboratories work at.

ACT-R is also an instance of a hybrid cognitive architecture in that it represents knowledge symbolically as rules and facts but also has a neurally-based activation process that determines which facts and rules get deployed in which situations. We have engaged in extensive analyses of the situations which people have to deal with in order to understand how each of these components should work together to yield adaptive behavior.

Our research has two major branches. First, in the laboratory we are looking at how people learn and solve problems in very well-defined situations. Here we are interested in things like how strategies for problem-solving evolve, how people discover things about a new domain, how they deal with the working memory load imposed by the tasks, and how they get faster at accessing information relevant to task performance. Our subjects all interact with experiment-running computer programs and we try to develop ACT-R simulations that can interact with the same programs, take the same actions, make the same eye movements, and display the same latencies. The emphasis in this research is very much in getting the detail of the simulation to match up with the detail of the behavior.

The other branch of our research involves a much broader focus. We have taken on modeling the cognitive competences that are taught in the domains of mathematics, computer programming, and cognitive psychology. Much of the motivation for this research is to be able to tap into real situations where people learn and solve problems and understand the implications of these domains for the cognitive architecture. We have built larger-grain ACT-R simulations that are capable of solving problems in these domains and have developed computer-based instruction around these cognitive models. Many of these computer-based instructional systems have the cognitive models as a component and attempt to understand student behavior by actually simulating what the student is doing in real time. These are called cognitive tutors and are currently being used to help teach courses in schools around the country. Much of this research has gonebeyond the original goals of understanding human cognition and now is part of a major effort to produce a significant improvement in American mathematics education.

Robot Teams
I am interested in all aspects of the development of effective robot teams. To build effective teams we must address many challenges that are not a concern for single robot systems. Cooperation, diversity, communication, distributed learning and distributed planning are a few examples. Of these, two of the most interesting (and open) issues are robot team diversity and the development of cooperative behavior:

Robot Team Diversity
We have developed a metric of robot team diversity that has been used experimentally in the evaluation of robots performing multirobot tasks (e.g. soccer, foraging and cooperative movement). It was discovered that behavioral diversity is an effective means for providing cooperation in multirobot teams but that the utility of diversity depends on the task. For instance, behavioral diversity seems to be useful in robot soccer teams, but not in foraging teams.

We now have a formal basis from which to investigate a number of important open issues relating to diversity. Why, for instance, is diversity important in some tasks, but not others? How does communication between agents impact the need for diversity? These are some of the issues we will be investigating over the next few years.

Social Potentials for Cooperative Behavior
The potential field approach is a well-known strategy for robot navigation. In this paradigm, repulsive and attractive fields are associated with important objects in the environment (e.g. goal locations or obstacles to avoid). To navigate, the robot computes the value of the vectors corresponding to each relevant field, then combines them (usually by summation) to compute a movement vector based on its current position. The result is emergent navigational behavior reflecting numerous constraints and/or intentions encoded in the robot's task-solving behavior.

We have extended the mechanism to multiple robots so that the potential field impacting a robot's path is shaped by the presence of team or opponent robots. We call these potential functions "social potentials." This approach provides an elegant means for specifying team strategies in tasks like foraging, soccer and cooperative navigation.

While we have found the approach to be quite useful, it has not been analyzed or evaluated formally. The implementations have been ad hoc systems built to address a particular research goal. It would be very useful to explore this topic in more rigor and depth.

One research direction we plan to follow is to examine how and why animals exploit "social potential" behavior. Examples include flocking by geese (presumably for efficiency), fish schooling, ant columns and distribution of predatory animals by scent marking. It is likely that robot teams can benefit from these behaviors in the same ways animals do.

We will also characterize the various forms of social potentials for cooperative behavior. What types/shapes of potential fields for instance, might be useful for multirobot tasks? Can we enumerate or classify these functions? Finally, we will implement and evaluate these functions in practice (in simulation and on multirobot teams).

My main research interest is in the interaction between algorithms and languages, mostly in the context of parallel computing, and has consisted of both theoretical and experimental work. As programming languages become higher level, implementations become more complex, and parallelism becomes pervasive, users are naturally becoming more removed from the hardware and its costs. Rather than trying to bring programmers down to the level of the machine to understand and get good performance, however, I believe that we should be trying to bring languages and cost models up to the level of the programmer. My research therefore centers around questions of how to model costs (e.g. time and space) for very-high level programming constructs (e.g. dynamic parallelism, futures, garbage collection), of how to design systems so these costs have meaning, and of how to make use of these features in effective algorithms design.

My recent work includes work on the PSCICO project with Gary Miller, Bob Harper and Peter Lee. Here we are looking at how to use very-high level programming constructs in geometric and scientific algorithms. We hope this project will give guidance to future language design, and will identify new ways of thinking about algorithm implementation. I also work on applied algorithms, parallel garbage collection, parallel scheduling, efficient parallel algorithms, and continue to work, to some extent, on the NESL programming language, a parallel language that my students and I developed in the early 90s.

My main research interests are in computational learning theory, on-line algorithms, and approximation algorithms. I also am working on applying techniques from graph algorithms to planning problems.

Computational Learning Theory. The goals of computational learning theory are to provide a mathematical understanding of the issues involved in getting machines to learn from experience, as well as to provide new analyzable algorithms. One of the questions I am particularly interested in is: under what conditions can one quickly hone in on the most relevant information in a large feature space? What fundamentally is involved in this task? Some simple versions of this question can be viewed as trying to combine a large number of sources of advice that may be available in a learning setting. Other versions of this question have close relations to cryptography. I am also interested in algorithms for active learning --- learning in settings in which one may actively probe the outside environment to gain additional knowledge --- and methods for fruitfully combining both labeled and unlabeled data in a learning task.

On-line algorithms. On-line algorithms involve repeatedly making decisions knowing only one's past history and without knowledge of future events. For instance, what is a good strategy for deciding when to switch lanes in rush-hour traffic? The Metrical Task System problem is a general on-line problem I have been interested in that (at some level) models a number of settings of this form. Roughly, an algorithm must repeatedly decide whether to continue in its current state or to incur a cost to move to a seemingly better state; but, only at the end, in hindsight, can it tell if it really made the best decisions. There are many important open questions in this area, such as how to make good use of partial prior knowledge, and how to use randomization to beat known deterministic approaches.

Approximation algorithms. Many important problems turn out to be NP-hard, implying that it is unlikely there will be algorithms for them that are both efficient and optimal in the worst case. One approach, then, is to find algorithms that produce approximately-optimal solutions. I am interested in a variety of problems of this sort including traveling salesman-like problems, graph coloring problems, and problems in DNA sequencing. For example, an interesting problem from this perspective is the "trick-or-treater's problem": given a weighted graph (a map of a neighborhood) and an integer k (a candy bag of a certain size), find the shortest route that visits at least k vertices (enough different houses to fill the candy bag). Broadly, the key challenges are to understand the approximability of fundamental problems, as well as to better understand the set of fundamental techniques for achieving good approximation guarantees.

Domain Independent Planning. I have recently become interested in applying techniques from graph algorithms to the setting of domain independent planning. Together with Merrick Furst we have developed the Graphplan planner based on this approach, and I have most recently been exploring the extent to which this method can be applied to probabilistic planning settings.

URL: http://www.cs.cmu.edu/~avrim

Complexity and Real Computation. In 1989, Steve Smale, Mike Shub and I introduced a theory of computation and complexity over an arbitrary ring or field R. In 1997, along with Felipe Cucker, we published a book, Complexity and Real Computation (Springer-Verlag). From our Introduction:

"The classical theory of computation had its origin in the work of logicians -- of Godel, Turing, ... , among others -- in the 1930's. The model of computation developed in the following decades, the Turing machine, has been extraordinarily successful in giving the foundations and framework for theoretical computer science.

"The point of view of this book is that the Turing model (we call it "classical") with it's dependence on 0's and 1's, is fundamentally inadequate for giving such a foundation for modern scientific computation, where most of the algorithms - with origins in Newton, Euler, Gauss, et al. - are real number algorithms."

Our approach applies to the analysis of algorithms over continuous domains as well as the discrete. The classical theory is recovered if we allow the ring R to be Z_2 (the integers mod 2). But now R can also be the real or complex numbers, or any other field. The familiar complexity classes P, NP and fundamental question "does P= NP?" make sense over R and moreover, relate explicitly to fundamental problems in mathematics such as Hilbert's Nullstellensatz. Thus, we are particularly interested in research concerning the complexity of algorithms that solve systems of polynomial equations.

Transfer Principles for Complexity Theory.
A powerful tool of the classical theory is that of reduction: If problem A can be shown to be reducible to problem B, then techniques for solving B can be used to solve A. Classically, A and B are both discrete, i.e. defined over the same domain Z_2. But now we have an additional powerful tool, namely that of transfer:

When there was essentially only one model of computation (i.e. over Z_2), it didn't make sense to transfer complexity results from one domain to another. But now, transfer becomes a real possibility. We can ask: Suppose we can show P=NP over the complex numbers (using all the mathematics that is natural here). Then can we conclude that P=NP over another field such as the algebraic numbers or even over Z_2? (Answer: Yes and essentially yes.)

I am particularly interested in such transfer results and problems that appear in the interface between the discrete and the continuous.

My main interests concern the mathematical semantics of programming languages. I believe that proper attention to semantic foundations can yield significant benefits in developing techniques for proving properties of programs, in program design, in language design and implementation.

I am particularly interested in developing intensional semantic models, in which one is able to reason both about the correctness and efficiency of programs. This is in contrast to most traditional semantic models, which are extensional and focus on the input-output behavior of programs while abstracting away from computation strategy. I am working mainly on the semantic foundations of parallelism. This work includes the development of axiomatic proof techniques for establishing behavioral properties of parallel systems, design rules for parallel networks that guarantee desirable behavior such as deadlock-freedom, and the design and implementation of programming languages that employ parallelism uniformly and cleanly.

A semantics for a programming language is an assignment of meanings to program terms. For a semantics to be useful it should accurately capture the computational behavior of program terms, at an appropriate level of abstraction.

I believe that major improvements in the formal treatment of program properties can be achieved by paying careful attention to semantics. If we want to reason about a particular behavioral notion (such as partial correctness) we should first define a mathematical model for programs which precisely captures this behavior without being overly complicated. Ideally, we would like a fully abstract semantics: terms should be given the same meaning precisely when the terms would induce identical behavior in all program contexts. The construction of fully abstract models is by no means an easy task, and depends in any case on the underlying notion of behavior.

For modelling and reasoning about certain types of program behavior, such as partial or total correctness, an extensional semantics is satisfactory: the meaning of a program can be chosen to be a (partial) function from initial states to final states, and all details of how the program goes about its computation can be suppressed since all we really need to keep track of is the state transformation that the program induces. However, such a semantics is no use if we want to make comparisons between programs for the same function. In an extensional semantics all sorting programs have the same meaning, whereas we might well want to design a semantics with which we can compare sorting programs with different computation strategies. This motivation leads to a desire for a theory of intensional semantics. In an intensional semantics the meaning of a program is taken to be an algorithm rather than simply a function. An algorithm can be viewed as a function together with a (mathematical representation of a) computation strategy. I have recently developed a category-theoretic approach to the modelling of algorithms, and applied these ideas to the semantics of the lambda calculus. In the resulting semantic model, there is a complete partial order on algorithms and standard operations such as composition, application, and currying are continuous; thus, one may define algorithms recursively and use the standard techniques of denotational semantics (least fixed points) to reason about recursive programs, even at this intensional level. This approach using categories is rather general, and I am exploring several other possible applications.

Semantic principles and insights should be used in the design of new programming languages, to avoid the development of cumbersome languages in which the programmer may have to labor to overcome the syntactic quirks and idiosyncrasies of the programming language in order to express his algorithm as a program. I am particularly interested in designing a language that embodies parallelism uniformly: it ought to be as easy to specify parallel expression evaluation as it is to specify parallel execution of statements, and it ought to be easy to put together the results of parallel activities. The choice of an appropriate set of primitives for such a language should be guided by proper attention to semantic foundations, and I am carrying out research on this topic.

My primary research interest is in formally verifying hardware designs. This interest grew out of earlier work in logic simulation and symbolic circuit analysis. Over the past few years, we have made great progress in formal verification, to the point where industrial hardware designers are making use of our ideas and tools. These tools promise to eliminate the uncertainty that lingers even after extensive evaluation by techniques such as simulation. The recent fiasco with the defective floating point divider in the Intel Pentium has placed formal verification at the forefront in digital hardware research. Industry is showing great interest in our work. Much more research is required in formalizing and generalizing our methodology, as well as in tool development.

During the course of developing hardware verification tools, I have become quite interested in symbolic representations and manipulation of discrete functions. Most tasks performed by a symbolic manipulator require solving NP-hard problems, and hence there are no known algorithms with good guaranteed performance. Instead, this work seeks heuristic methods that give satisfactory performance in practice. Our approach involves representing functions by directed acyclic graphs and applying graph algorithms to perform operations on functions. The results of our work in this area have spread beyond the original application. Our methods are now being applied to such areas as, temporal logic model checking, logic circuit optimization, automated theorem proving, and truth maintenance systems.

In recent years, we have developed techniques that generalize from Boolean functions, representing each bit of data as a separate function, to word-level functions, representing an entire data word as a function. This has lead to a hierarchical methodology for verifying arithmetic circuits such as multipliers and dividers. In fact, Intel has already started using these methods on their floating point units. I also maintain a longstanding interest in parallel computing, particularly in efficient mappings of application programs onto parallel machines. I am particularly interested in applications involve the manipulation of sparse and dynamically changing data structures. Such applications have historically performed poorly on parallel machines, but I believe that the right combination of architecture, programming model, and algorithms could lead to efficient solution techniques.

I am particularly interested in developing techniques to formally verify pipelined microprocessors. Each generation of microprocessor uses increasingly complex mechanisms to maximize performance, but these mechanisms should not affect program behavior. The challenge is to verify that the hardware implements the sequential semantics of the instruction set definition despite the fact that many instructions are executed in parallel. Since the complexity of a microprocessor is in its control logic, we can model the data operations as unintepreted functions operating on symbolic data. We have recently devised techniques that can verify simple, superscalar processors. However, major research breakthroughs are required to handle the complexity of advanced microprocessors.

My research focuses on computational design theory, methods, automation, and practice, emphasizing. the early stages of design. In particular I explore computational representation, generation and optimizing search of the design space. My premise is that computational tools must support a design process modeled by lateral exploration followed by concentrated investigation of one or more good designs. Based on this premise, much of my work has focused on stochastic optimization algorithms as search techniques, and various grammatical representations to model, generate, and move within the design space. The result is a merging between artificial intelligence and operations research, giving a unique approach to addressing the conceptual design problem.

Grammars are able to concisely model large design spaces. In a competitive society, once such a space is created, it must be searched not only to find a feasible solution, but an optimally directed one. Further, solutions obtained from any computer tool are only as good as the model that represented them, namely the set of objectives and constraints. Thus several equally good solutions are desired from which a designer can consider all objectives, including those not articulated in the model, to select the most preferred one. This motivates our shape annealing technique; shape annealing combines shape grammars and simulated annealing for the generation of optimal shape topologies. Based on the initial success of the technique in solving a knapsack-like problem, we have pursued simulated annealing with shape, string, and graph grammars, and probabilistic move sets, for the design of structures, machines, process plans and product layouts. This work bridges the theoretical aspects of form to function reasoning, the general question of topology generation and optimization, and the practical problem of component layout under a variety of constraints.

From the shape annealing/simulated annealing work we have begun to move in new directions, focusing on agent-based design in a changing environment where agents act based on a grammar representation and focusing on the creation of new stochastic optimization techniques with improved properties over simulated annealing. We are also exploring approaches to symbolic optimization for non-monotonic functions by incorporating robustness considerations into the activity analysis method for monotonic symbolic optimization. These efforts help the designer identify regions of the design space in the early stages of design where optimally directed design concepts lie, for further refinement during the later design stages.

My interests span several areas of Artificial Intelligence and Language Technologies. In particular, my current research is focused on machine learning in the context of language processing, including: tracking and detection of new topics and events, extracting key facts from text, corpus-based techniques for machine translation and translingual information retrieval, and content-based text summarization and text mining. I also work on planning, problem-solving, integrated rational-agent architectures, and large-scale data mining.

The following are my current projects; all represent collaborative efforts with graduate students, research staff, and/or faculty colleagues:

The TDT Project (Topic Detection and Tracking) [with Brown, Lafferty, and Yang]
Automated topic-tracking and new-topic detection for textual, audio and video news media, including developing new classifiers trainable with very few positive instances of events or topics to track. Also, unsupervised learning discovery of new topics at different levels of granularity from unlabeled textual data.

The MMR Project (Maximal Marginal Relevance) [with Goldstein]
Combining information novelty with query relevance in Information Retrieval to minimize redundancy. Also, extending MMR for on-demand query-relevant passage extraction document summarization, including producing unifying summaries of topically-related document clusters.

The HPKB Project (High-Performance Knowledge Bases) [with Mitchell]
Extracting knowledge from text (primarily from The Web) in order to build large-scale knowledge-bases on-demand. My part of the project focuses on extraction of entities and relations.

The DIPLOMAT Project [with Frederking, Brown and Hogan]
Multi-engine machine translation for rapid corpus-based development of MT systems among new language pairs. Diplomat includes speech-to-speech MT and well as text-MT. My focus is on generalizing example-based machine translation methods to produce reasonable MT with "minimal" training corpora.

The Multilingual IR Project [with Yang and Brown]
Multiple methods for bridging the language barrier between queries and document collections in IR, including example-based thesauri, translingual pseudo-relevance feedback, generalized vector spaces, and latent semantic indexing.

The KANT Project [with Nyberg and Mitamura]
High-accuracy knowledge-based machine translation in well-defined semantic domains. Unlike other my other text-based projects that are corpus-based and domain independent, KANT is a knowledge-intensive project to optimize performance given semantically delineated domains.

The PRODIGY Project [with Veloso]
PRODIGY is an integrated intelligent system for problem-solving, planning, analogical reasoning and learning that serves as a baseline platform from which to launch various focused machine learning projects. Whereas Veloso carries the bulk of this project, my primary interest is on learning new domains from examples and observation.

My interests are in multimedia interface development and evaluation, digital video libraries, and computer support for situated learning. My current work as part of the Informedia Project leverages from other CMU CS research in image processing, natural language processing, and speech recognition to enable full content search and retrieval from digital video, audio and text libraries.

Given thousands of hours of video and the need to find a relevant ten minute clip, the user should be able to locate the relevant clip without investing hours of viewing time. I contribute to the development of segmentation and abstraction strategies to meet this goal of more efficient information retrieval from multimedia libraries. I also conduct empirical studies evaluating the effects of multimedia abstractions such as filmstrip views and video skims.

The Informedia library system is currently in use at a local high school. I am interested in improving browsing within this system by supplementing the current query interface with information visualization techniques. I am also involved in a follow-up project which will extend the Informedia scope of accessing broadcast quality multimedia materials in a library setting to capturing, integrating and communicating experiences across people, time and space.

My interests span three areas: Programming Systems, Hardware, and Theory. I use the techniques and insights of theoretical computer science to solve problems in programming systems and hardware design that are of practical interest. I have a number of active research projects in these areas that I would be happy to discuss with students. Below are short descriptions of two research projects that I think are particularly exciting.

Hardware and Software Verification.
Logical errors in finite state concurrent systems like sequential circuits and communication protocols are an important problem for computer scientists. They can delay getting a new product on the market or cause the failure of some critical device that is already in use. The most widely used verification method is based on extensive simulation and can easily miss significant errors when the number possible states of the system is very large. Although there has been considerable research on the use of theorem provers, term rewriting systems and proof checkers for verification, these techniques are time consuming and often require a great deal of manual intervention. My group has developed an alternative approach called temporal logic model checking in which specifications are expressed in a propositional temporal logic and an efficient search procedure is used to determine whether or not the specifications are satisfied.

In the fifteen years that have passed since the original algorithm was published, the size of the systems that can be verified by this means has increased dramatically. By developing special programming languages for describing transition systems, it became possible to check examples with several thousand states. This was sufficient to find subtle errors in a number of nontrivial, although relatively small, circuit and protocols designs. Use of boolean decision diagrams (BDDs) led to a major increase in the size of the examples we could handle by this technique. Representing transition relations implicitly using BDDs made it possible to verify examples that would have required 10@^20 states with the original version algorithm. Refinements of the BDD-based techniques have pushed the state count up over 10^100 states. By combining model checking with abstraction, we have been able to check even larger examples. In one case, we were able to verify a pipelined ALU design with 64 registers, each 64 bits wide, and more than 10^1300 reachable states.

Analytica --- A Theorem Prover for Mathematica.
Analytica is an automatic theorem prover for theorems in elementary analysis. The prover runs in the Mathematica environment and is written in Mathematica language. The goal of the project is to use a powerful symbolic computation system to prove theorems that are beyond the scope of previous automatic theorem provers. The theorem prover is also able to guarantee the correctness of certain steps that are made by the symbolic computation system and therefore prevent common errors like division by a expression that could be zero.

Since we wanted to generate proofs that were as similar as possible to proofs constructed by humans, we use a variant of natural deduction to generate proofs. We have demonstrated the power of our theorem prover on several non-trivial examples including the basic properties of the stereographic projection and a series of three lemmas that lead to a proof of Weierstrass's example of a continuous nowhere differentiable function. Each of the lemmas in the latter example is proved completely automatically. In a related project that uses similar techniques, we have managed to prove all of the theorems and examples in Chapter 2 of Ramanujan's Collected Works completely automatically. We believe these examples provide convincing justification for combining powerful symbolic computation techniques with theorem provers.

I am interested in image understanding and computer vision systems, especially in the area of binocular stereo from passively-acquired imagery. I am currently working with Dave McKeown, Chris McGlone and Jefferey Shufelt at the Digital Mapping Laboratory in the investigation of the automated analysis of aerial imagery to support research in computer vision for digital mapping and the creation of databases for virtual world simulation.

Binocular Stereo.
Humans are able to surmise depth in 2-D "monocular" images and to perceive it through the stereoscopic fusion of a pair of images. The process used by the human visual system to achieve this, however, is not well understood. How, then can we produce autonomous systems which are able to extract depth information about, and interact with, their environments? One way is to attempt to emulate some of those processes, which seem to be present in the human visual system, and learn what does and does not work. This approach allows us to attempt automatic visual recognition of objects, and, perhaps in some cases, to gain insight about the operation of the human visual system. The perception of depth from a stereo pair provides both a qualitative and a quantitative measure in depth determination that is not available from a monocular view and produces the ability to detect objects which are difficult to distinguish from the background due to similar image intensities or textures. For my theses work at USC, I developed a Stereo Vision System (SVS) in which I showed methods to integrate primitives derived from area-based and feature-based stereo matching algorithms. I have continued this work at CMU particularly with respect to improvements in stereo matching accuracy and refinement.

Data Fusion.
Stereo data alone is not sufficient to solve the cartographic feature extraction problem. To achieve that goal, we will need to gather together various partial scene abstractions formed by differing methods: stereo, monocular, multi-spectral and others. Relating image derived measurements and features into a consistent and rigorous object-space representation is an important first step in automated fusion. As an example, four aerial images that cover a common area allow twelve different sets of pairwise stereo data to be produced, along with four sets of monocular estimates of building hypotheses. The key issue is finding common robust structure from this noisy and diverse set of information.

Evaluation.
It is not enough to simply point at a set of results and saying Look! I am doing a great job. It is necessary to determine quantitatively, as well as qualitatively, how well an approach is working in order to justify claims of an improvement to that approach. At the same time it is difficult and/or expensive to obtain or generate a complete ground-truth model of a test scene. Therefore I have been working on ways to generate quantitative results with respect to a set of goals. For instance, if the goal is to extract all of the buildings in the scene, then only the buildings need to be explicitly modeled in the ground reference data.

URL: http://www.cs.cmu.edu/~sdc

My interests are in the application of artificial intelligence to education, in particular, the use of cognitive models in computer-based tutoring environments. Our approach is to build tutoring programs around rule-based models of how people perform skills, such as programming. Such a model allows the tutoring program to solve practice exercises along with the student, providing help as needed. My research has focused recently on estimating students' mastery of the knowledge represented in the cognitive model. By integrating learning and performance assumptions with the cognitive rules, we attempt to predict students' test performance, shape practice appropriately and improve the model. I am also interested in related issues in the design of computer-based practice environments, for example the content and timing of help messages and their impact on students' performance.

My research interests are in the design and implementation of advanced programming languages and in applying programming language technology to improve the development, maintenance, and performance of software systems. I am particularly interested in the application of types to the structure and implementation of programming languages.

A current focus of my research is on typed compilation. Compilation using types offers some compelling benefits over conventional, untyped compilation. For example, preserving types through compilation provides additional information that may be used to optimize programs. Type-based optimizations are particularly useful for compiling advanced programming languages, such as ML. Advanced programming languages, provide many features such as first-class functions, automatic memory management, polymorphism and abstraction, that are valuable to programmers but are also hard to implement efficiently. Modern implementation strategies, including type-based optimization, allow advanced languages to be implemented roughly as efficiently as less advanced ones. For instance, the TIL (Typed Intermediate Languages) compiler for ML, one project I work on, uses type-based optimizations to obtain a 3-fold speedup over other ML compilers.

An even more important benefit of typed compilation lies in its application to mobile code security. With the increasing importance of the widely distributed computing (particularly with the World Wide Web), it has become impractical for agents to limit their computing interactions to other agents whom they trust. This leads directly to a need for mechanisms whereby an agent can safely execute untrusted and potentially malicious programs. However, it is important that such mechanisms not substantially sacrifice performance, as is the case with run-time checking mechanisms. Typed compilation gives us a tool for producing certified executables, which can be statically determined to be safe before execution. This certification strategy works by attaching types to mobile code; that code is then type-checked and is run only if type-checking succeeds. If it does succeed, the formal semantics of the type system guarantees that code is safe.

For this to work requires a type system suitable for low-level code, in particular for machine binaries. However, most research into type systems has focused on high-level languages, in part because low-level languages can be uncooperative to type-theoretic analysis. Recently, I and others have been studying typed assembly languages, machine-level programming languages with sound type systems. In a typed assembly language, one can program with direct access to machine resources without sacrificing the safety guarantees provided by typed high-level languages. In practice, however, typed assembly code is typically produces by a typed compiler from high-level source code. My ongoing research into typed assembly languages focuses on enhancing their type systems both to make them more flexible and to strengthen the safety properties they can guarantee.

My work is focused on various aspects of computer music, a field which poses many challenges for computer science. I also direct the Just-In-Time Lecture Consortium, which offers a new technology for low-cost, computer-based training and education.

A central problem in computer music is expressive control, that is, the detailed control of timing, gesture, nuance, and tone quality that is essential to music. This problem has many facets, resulting in a variety of research directions. The Computer Music Project has developed new languages, development tools for real-time systems, synthesis techniques, and music understanding systems. This research is more than intrinsically interesting. It can shed light on related problems in real-time systems, multimedia, human-computer interaction, and artificial intelligence. Moreover, new possibilities of control and interaction in music are changing the very nature of music composition, performance, and aesthetics.

One research example is the the development of new languages for expressing temporal behavior. One of these is Nyquist, a language that provides a single abstraction mechanism for the seemingly different notions of ``note,'' ``instrument,'' and ``musical score.'' Nyquist gives composers an elegant, uniform notation that spans the range from low-level digital signal processing to high-level music composition. At present, Nyquist does not generate sound in real-time, but as processors increase in speed, software for sound synthesis will replace special-purpose hardware synthesizers. Nyquist already provides one of the fastest sound synthesis implementations, and a future version will support real-time synthesis.

Expressive control of musical tones is another topic of research. A violin is expressive because there are many parameters under continuous control by the player, including bow pressure, finger and bow positions, and bow velocity. These give rise to variations in the resulting sound. My colleagues and I have developed a new synthesis technique, spectral interpolation, which allows us to synthesize tones with interesting variations in spectra. Spectral interpolation has been used to accurately synthesize a variety of instruments. In the future, we will use this technique to give composers and performers greater intuitive control over synthesized sound.

Real-time performance systems present interesting problems. I have developed several systems for real-time music understanding that ``listen'' to a live performance and derive some abstract information regarding rhythm, tempo, harmony, etc. The degree of understanding is usually demonstrated by having the system participate in the performance. One example is Computer Accompaniment, in which the computer follows a performance in a score and plays an accompaniment in synchronization with the performer. My computer accompaniment technology appeared in a commercial product in 1994. Another example is a system that listens to an improvisor playing 12-bar blues and plays the part of a rhythm section. Systems that perform both of these tasks have been built here, but this is only the beginning of what is possible. Current work includes more sophisticated systems for listening to improvisations, ensembles, and vocalists.

Education is another interest. Our country spends more for education than for health care, and as with health care, education costs are growing faster than the inflation rate. Computer-based tutoring systems have much to offer, but development costs and lack of expertise have made it difficult to produce good tutoring systems. Work on automating instructional design principles to lower the cost of intelligent tutoring systems led to an even simpler approach, ``Just-In-Time Lectures,'' in which presentations are captured using digital video, synchronized slides, a table-of-contents, and links to the Web. Just-In-Time Lectures have been used to deliver entire courses and by large corporations for training.

I am interested in making robots act purposefully and successfully in a world in which most everything is uncertain. Sensory information is inaccurate or noisy, actions seldom have a precise effect, and objects in the world are often in the wrong location or orientation. Despite such obstacles to purposeful action, there are many tasks that can be accomplished successfully. Humans, animals, and some machines are proof. Providing robots with the ability to operate autonomously and purposefully requires an understanding of how different tasks may be accomplished by different repertoires of actions. Grasping, hitting, and dropping are some actions that are useful in a robot's repertoire. More exotic actions include shaking, twirling, and other actions that randomize an object's state. My current work focuses on two-palm manipulation, in which two arms cooperate to manipulate objects dynamically, that is, without the need for full kinematic constraint. My work is motivated by several desires. First, I would like to program robots more easily than is currently possible. Second, I would like to understand the scope and limitations of autonomous systems, whether biological or artificial. Third, I would like to reduce the complexity of design and planning by codifying the design parameters required to achieve a given level of automation. An underlying goal of my research is to understand the relationship between sensing, action, and prediction. In the past, I have explored various extreme points in this space. With Matt Mason I explored sensorless strategies, for my thesis work I looked at randomized strategies, and most recently I investigated fast-action minimal-sensing strategies. My research draws on tools from geometry, mechanics, planning, and probability.

AI and Machine Learning:
For most of my career I have been exploring the idea that recognition and other essential operations of human intelligence may depend on the use of massively parallel computation rather than clever algorithms and data structures. Instead of using a single processor to look at data sitting passively in memory, we need some kind of active memory in which all of the available knowledge participates in producing a response. My first experiments in this area led to the NETL system, essentially a semantic network with a very simple computing element permanently assigned to each node and link in the network. In recent years, I have become interested in more neuron-like architectures that represent knowledge in a distributed form and that can learn new behaviors from examples.

My students and I have developed several improved learning algorithms for neural networks, including Quickprop, Cascade-Correlation, and several variations on these. Cascade-correlation is very fast, scales up well, and it constructs a network of the appropriate size and shape as it works on a problem. These algorithms are being used in a large number of application projects worldwide.

Most current learning algorithms employ "supervised" learning: the system is trained by showing it a collection of input/output pairs illustrating the desired behavior. However, in many domains, such labeled training data is scarce. I am currently interested in developing better algorithms for "unsupervised" and "partially unsupervised" learning, in which the learning algorithm must discover interesting and useful structure in an unlabeled stream of experiences.

Tools for Software Development.
Most of software engineering is concerned with developing programs that correctly implement a pre-existing specification. I am more interested in tools for "evolutionary" or "incremental" software development, in which the requirements may change over time, and in which the developer doesn't know exactly what he wants until after the software is running. Languages of the Lisp family always have been excellent vehicles for this kind of programming.

I was one of the principal designers of the Common Lisp language, and my CMU Common Lisp group developed a widely used, public-domain implementation of Common Lisp with a very powerful compiler. Later, my "Gwydion" research group worked on the Dylan language and on Sheets, an advanced software development environment for Java. I do not currently have any active research projects in this area, but I still am very much interested in software tools of this kind, and in the future of programming in general.

Just Research.
I am currently on leave of absence from the CMU faculty so that I can head Just Research, a new computer science research center located a few blocks from CMU. This laboratory was established by Justsystem, a large software company based in Tokushima, Japan. Just Research conducts research in many areas, including information retrieval, natural language processing, image processing, and machine learning applied to all of the above. The lab maintains close ties to the CMU community. Many of our Ph.D.-level researchers have adjunct faculty appointments in SCS, and we have employed a number of CMU students in part-time and summer positions.

The first project examines fast methods for approximate matching in multimedia databases. Typical queries are as follows: "in a collection of product photographs, find pro- ducts that look like tennis shoes"; "in a collection of med- ical X-rays, find ones that look like the X-ray of the current patient, and list the corresponding diagnoses". The main idea behind our approach is to extract n features from the objects of interest (typically, with the help of a domain expert), thus mapping each object into a point in n-dimensional feature space. Subsequently, we can use state-of-the-art database techniques (like the 'R-trees') to store and retrieve these n-dimensional points. The philo- sophy of our approach is to provide a the vast majority of irrelevant objects. Allowing some 'false alarms' is accept- able, because they can be easily discarded by a elaborate test, or even by the user. We have already successful sets of features for 2-d color images, 2-d shapes, and 1-d time series (such as stock-price movements). Depending on the domain, we are experimenting with modern signal processing techniques, such as the discrete wavelet transform for sound and images, hidden Markov chains for digitized voice, the discrete cosine transform for stock-price time series.

The second project focuses on data mining. The goal is to discover correlations ('rules') in a collection of records. For example, in a set of patient records with demographic characteristics, symp- toms and diagnoses, we would like to find all the 'interesting' rules (eg., 'patients >50 years old with cholesterol >300 have 10% probability of heart attack'). We are studying traditional clustering methods as well as statistical methods like the 'Singular Value Decomposition' (SVD), to do cluster analysis and rule discovery.

The last project examines algorithms and architectures for fast execution of expensive database operations. We are working on Active Disks for data mining, on striping and placement algorithms for video servers, and on buffering algorithms for database operations.

My main research interests are the theory, design and implementation of high performance information systems. The general theme of my work is to understand and exploit the interplay of applications and new technologies. At various times this work has involved designing parallel algorithms, parallel architectures, custom chips, and specialized compilers. My current activity centers on the architecture and control of high speed networks as infrastructure for communication and for parallel computation. Colleagues and I have recently completed the Credit Net project, which has designed and is in the deployed a 622 megabit-per-second ATM local area network. I am currently working with Peter Steenkiste, Hui Zhang and our students and staff on the Darwin project, which involves the design of algorithms to allocate and control resources in the network, and of interfaces and software to support applications in parallel computing and multiparty, multimedia communication. The overall goal of Darwin is to develop the infrastructure need to provide dynamic electronic service creation and deployment in future networks.

I have broad research interests in computer systems, including operating systems, networking, storage systems, computer architecture, performance evaluation, and distributed systems. I am particularly interested in developing new ways of structuring computer systems (hardware and/or software) to address technology changes and enable new applications. One place where I see an opportunity for large, fundamental changes is in the ongoing shift in importance from conventional computing to I/O and data movement -- we need computer system designs that treat I/O components as first-class entities, allowing them to actively and adaptively cooperate in the completion of useful work.

My students and I are currently pursuing several topics of research:

* design and implementation of extensible I/O software.
* design and implementation of application-level networking.
* construction of high-performance network servers
* implementation and use of application-controlled storage management
* improved general-purpose file system support for small file I/O

My field of interest is software engineering, and specifically the areas of applied formal methods, software architectures, and software development environments. The common thread that links these areas is the problem of controlling the complexity of large software systems by providing a scientific basis for software design.

Applied Formal Methods.
The traditional use of formal (or mathematically-based) methods has been to solve the problem of refinement: given a formal specification of a system, how does one construct an implementation that is correct with respect to that specification. In contrast, my interest in formal methods is in dealing with the inverse problem of abstraction: given a family of existing systems, how does one construct a formal model that characterizes the important commonalities in these systems. When used in this way, formal methods become a tool for extracting reusable software architectures, for clarifying system design, for simplifying the way we think about a class of system, and for building a framework for reuse. Among the important research issues are those of methodology (How should we use formal notations in practice to arrive at system abstractions?), language (What notations, type systems, parameterization mechanisms, etc. are best suited to this use of formal methods?), and reusability (What properties of a formal model best support reusability, evolution, and adaptation?).

Software Architecture.
Successful design of software architecture has always been a major factor in determining the success of a software system. But until recently architectural design has been largely based on ad hoc choice, informal experience, and local expertise. The goal of this research is make this knowledge precise, codified, and available to engineers as a matter of routine engineering. An example of where this has been successfully accomplished is compiler construction: what once took years to develop is now done routinely by undergraduates in a semester course. This is because compiler development is based on a well-defined, formalized software architecture, which defines a set of abstractions that give the software engineer a conceptual grasp of the problem, leads to a focused set of tasks that must be performed to specialize the architecture for a specific compiler (lexical analysis, parsing, flow analysis, etc.), and enables automated support for the compiler construction tools (parser generators, attribute evaluators, etc).

The goal of this research is to demonstrate that similar architectures can be obtained for other classes of software. In particular, the design abstractions obtained through the application of formal methods to the design process (mentioned above) are natural candidates for architectures.

Software Development Environments.
Given a well-defined architecture, it is natural to attempt to support its use with development tools and environments. The ABLE project is currently building a system, called AESOP, for generating environments that support specific classes of architectures -- or architectural styles. Given a description of an architectural style, AESOP produces an open environment for creating software designs in that style, reasoning about properties of those systems, integrating external tools, and graphically visualizing architectural designs. The ABLE project also is developing transformational techniques for specializing general-purpose environments: using these techniques we are able to adapt existing environments so that they support the creation of application-specific programs.

I am interested in computer systems architectures, in particular, memory systems architectures employing prefetching, parallel and video file systems, redundant arrays of disks, high bandwidth networks and workstations and multicomputer operating systems. Towards these goals, I lead the Parallel Data Laboratory (PDL) in the following projects.

Currently, most of our effort is focussed on the Network-Attached Secure Disks (NASD) project. The central goal of NASD is to establish an intelligent storage interface and to develop the distributed and parallel file system technology to exploit it. This new interface features direct communication between clients (possibly cluster servers) and storage devices or subsystems. Direct communication enables cost-effective scalable striped storage, file server offloading and reduced messaging, storage processing and bandwidth proportional to capacity, device-enforced security, and extensible storage intelligence available for application needs (Active Disks). The Lab develops full-function prototype systems and evaluates these against real applications. For example, in the fall of 1998 we are building a 1.25 TB array of 100 NASD (or Active Disk) nodes to be tested with data mining applications (such as association discovery from consumer transactions) and multimedia applications (such as medical image processing and digital library retrieval and viewing). In the spring of 1998, this project branched out to examine the use of intelligent network devices (Active Networks) for storage functions such as caching, redundancy or load balancing. We also participate in a National Storage Industry Consortium (NSIC) industry working group devoted to developing the appropriate interfaces for network-attached storage devices.

Our informed prefetching and caching research (TIP) proactively tailors file system resource management to the needs of I/O-intensive applications. With applications disclosing access patterns, TIP increases I/O concurrency to exploit the full parallelism of disk arrays, fetching further ahead on congested disks as needed. Our implementation is based on an extensible cost-benefit resource allocator and encapsulates within each module bidding for resources all policy related to that module's allocation strategy. Hints, the key to TIP's dramatic reduction in elapsed time (approximately linear in the number of disks for many I/O-intensive applications), can be automatically generated by runtime and compilation means. Both techniques are currently being explored; speculative pre-execution of runtime code stalled waiting for I/O generates probable future reads and compile time loop unrolling predicts a superset of future virtual memory page-ins.

Our Scalable I/O collaboration (SIO) , with Caltech, Rice, Princeton, Arizona, Washington, Argonne, Illinios and others, is focussed on defining and demonstrating extensions to the traditional UNIX file system programmer's interface to portably support high-performance, parallel applications. PDL researchers are implementing the SIO parallel file system API in a cluster of workstations environment employing network-attached secure disks. Designed to operate outside of client operating system kernels while providing dynamically configurable failure tolerance, our parallel file system will fully exploit the features of NASD devices.

The Lab's original and most well-documented project, redundant disk arrays (RAID) , is largely complete. In its heyday we worked on RAID architectures for improved performance in the presence of failures and architectures for reducing the failure-free penalty for maintaining redundant information. More recently, the RAID project developed and published a rapid prototyping framework for RAID systems. This executable framework, RAIDframe, enables us to treat RAID architectures as simple graphical programs amenable to automatic error recovery and rapid modification. RAIDframe efforts persist as local and remote colleagues port and extend RAIDframe.

The Lab is equipped with a few hundred disk drives in various arrays and standalone configurations. About 50 Digital Equipment Alpha workstations with 133 to 500 MHz processors form the basis of the Lab's computing. To these we have recently added 64 300 MHz Pentium II workstations. Networking is provided with a 52-port OC3 ATM switch, a collection of 24-port 100Mbps Ethernet switches and am 8-port 1.28 Gbps Myrinet switch.

The Lab is advised and supported by a consortium of companies including Hewlett-Packard, Intel, Compaq, 3Com, Seagate, Quantum, Clariion, Symbios Logic, StorageTek and Wind River. Representatives of these sponsors visit CMU for at least three days per year to participate in the Lab's annual retreat and workshop, typically in the late fall at an off-campus conference facility nearby CMU.

My research area is computer architecture and compilers. Currently my interest is focused on novel ways to use the hundreds of millions to billions of transistors that will be available to processor designers in the near future. In particular, I am interested in how user programs written in high-level languages can be compiled directly into hardware, yielding order of magnitude speedups.

The key architectural feature that enables huge speedups is the reconfigurable fabric (similar in concept to today's FPGAs), which can be configured to any hardware circuit. The reconfigurable fabric is then integrated with a simple super-scalar processor core, resulting in a high-powered general-purpose processor. The compiler for such a system partitions a program into sections that are executed either on the core or on the reconfigurable fabric. It synthesizes communication and synchronization code and also creates the hardware configurations.

The research is proceeding on four fronts: (1) the development of techniques for compiling high-level languages to reconfigurable fabrics, (2) the design of Tiger, a TIghtly coupled General-purpose processor with a Reconfigurable fabric, (3) The design and implementation of PipeRench, a compiler-friendly computation-based reconfigurable fabric, and (4) the creation of a benchmark suite workload 2000.

The compilation technology we are developing allows users to program Tiger processors in high-level languages without requiring them to understand the actual implementation details of the reconfigurable fabric or the processor/fabric interface. We have already completed our first version of a compiler that creates configurations for fabrics from a text-based dataflow intermediate language (DIL). We are now investigating techniques to turn C programs into executables for Tiger machines. Among other things, we are investigating how to automatically partition a C program between the general-purpose core and the reconfigurable fabric, how to create hardware pipelines from C code, how to retime circuits to reduce register pressure, and how to speed up place-and-route without compromising efficiency.

As part of this research effort I am collaborating on the design of a new reconfigurable fabric called PipeRench. PipeRench is the first FPGA-like device that virtualizes the physical array allowing designs larger than the physical device to run efficiently. Furthermore, unlike previous FPGAs, PipeRench is oriented toward the implementation of data paths instead of random logic. We expect to fabricate PipeRench in late 1998. Currently, using our DIL compiler, we have implemented many kernels on PipeRench and have, at least initially, validated our assumption that PipeRench's compiler-friendly design enables our goal of compiling high-level languages automatically to the fabric.

My other areas of interest are parallel object-oriented languages and fine-grained parallelism.

Areas: (I have included all areas, including the ones I am currently listed under in this list. Also note that reconfigurable computing new areas)

My research interests center on how to build (design, program, implement) systems. "Systems" in this context refers to a software system executing on some hardware platform. One of the challenges in system design is to develop good abstractions and tools (both for the software and hardware side) to simplify the task of building the system. Therefore, my research includes the building of tools (often compilers) to support system development.

I'm involved in two projects: one (Fx) focusses on the mapping of programs onto parallel and distributed systems; the other (cmcc -- for CMU's C Compiler) investigates the construction of an optimizing C compiler.

Together with other researchers (both inside the School of Computer Science and in other departments), I work on developing applications, usage models, abstractions, and programming tools for scalable computers. This class of platforms includes networked workstation clusters (or "networks of workstations", although these networks in practice include a lot more than workstations) as well as parallel systems. The core of our effort is the Fx compiler, which maps application programs written in a dialect of High Performance Fortran (HPF) onto a variety of systems. The Fx compiler system has been (re)targeted at the Cray T3D, the Intel Paragon and iWarp, and the Nectar Gigabit Testbed. Efforts to target new ATM-based networks like CreditNet are under way. The Fx compiler provides a unique framework to explore issues in parallel computing, ranging from applications to computer architecture. For example our input language allows the user to pass hints about the alignment and distribution of data objects (i.e., how the elements of an array are to be placed relative to other arrays and relative to other elements of the same array). These directives guide the compiler when mapping applications with access patterns that are too hard for a compiler to analyze.

HPF and its dialects form one class of languages that can be used for the programming, and HPF has demonstrated some success for the programming of "regular" problems. (A problem is called "regular" when the distribution of data can be described with a few parameters, like the block size and stride.) However, there exist a number of applications (often referred to a "irregular") that are beyond the capabilities of current compilers for HPF. That it, is is either hard or impossible to efficiently map these code onto parallel or distributed systems. The Archimedes project attempts to support such applications, and the Archimedes and Fx compilers share the communication back-end. To address the needs of these applications, however, it is necessary to consider all aspects of the execution environment, including the runtime system. Therefore, one of our current projects investigates the interface between compilers, applications, and the memory and synchronization models provided by the runtime system.

The cmcc compiler is a compact, optimizing C compiler, implemented in C++. This compiler serves as a testbed for research into compiler construction; current topics of interest include code generation, instruction scheduling, register allocation, debugging of optimized code, as well as code optimization to reduce code space and program execution time. In addition, cmcc is a platform to explore code reuse and software construction. A compiler offers ample opportunities for code reuse, and the compiler includes a number of (application) frameworks, including frameworks for global data flow analysis, local instruction scheduling, and register allocation. These frameworks simplify the program structure (and are one of the reasons for cmcc's compactness). They also allow a fair comparison between different approaches (e.g., to register allocation), since different register allocators share the base tools (like building the interference graphs). Finally, a building a framework indicates that we are able to unify a number of so far disparate approaches and thereby expresses our improved understanding of the problem domain.

In summary, my research area includes the programming aspects of current and future systems. This research area can be loosely described by the overlap of compilers, operating systems, and computer architecture.

I am interested in the performance analysis and design of computer systems, particularly distributed systems. I work on finding analytical models which capture the important characteristics of a computer system and allow me to redesign the system to improve its performance.

I believe that many fundamental conventional wisdoms on which we base system designs are not well understood and sometimes false, leading to inferior designs. My research challenges these age-old beliefs. Here are just a few examples:

• Thousands of "load balancing" heuristics do exactly that -- they aim to balance the load among the existing hosts. But who said that's neccessarily a good thing?

• Migration policies for networks of workstations and distributed servers direct jobs to the host with least load. That seems good from the job's perspective, but is it best for the system overall?

• Given a choice between a single machine with power p , or n identical machines each with power p/n, which would you choose?

• Migrating active jobs is generally considered too expensive. Killing jobs midway through execution and restarting them from scratch later is even worse! Says who?

• Ever notice that the "proven best" scheduling policies like SRPT (shortest-remaining-processing-time-first) are never used in practice? There's a fear that the big jobs will starve. Is this true?

Application areas I currently work in include: Web servers, distributed Web servers, distributed supercomputing servers, networks of workstations, and communication networks.

My principal research interest is in the application of type theory to building and reasoning about programs. The focus of my work is the Fox Project, which I lead with Peter Lee and Frank Pfenning, and the PSciCo Project, which I lead with Guy Blelloch, Peter Lee, and Gary Miller. The Fox Project is concerned with the design, implementation, and application of advanced programming languages. The fundamental thesis of the project is that type theory is critically important for the implementation of robust, maintainable, and efficient software systems. The PSciCo Project is concerned with the application of advanced programming languages to the implementation of sophisticated algorithms for scientific computing.

Type theory provides a unifying conceptual framework for programming language design, specification, and implementation. As a design tool type theory provides a clean framework for organizing programming language constructs. A type consists of a collection of values together with a collection of primitive operations on those values. Familiar notions such as trees or lists may be viewed as values of recursive type; the operations permit traversal of these structures. Procedures may be viewed as values of function type, with operations to create procedures and to apply them to arguments. Abstract data structures such as dictionaries may be seen as values of existential type, with operations to create a data structure and to use a data structure without revealing its implementation details. In fact a programming language may be defined by giving an interpretation of its constructs in type theory. For example, modularity mechanisms might be rendered as uses of existential type, together with a notion of subtyping to admit code reuse and generic operations. A significant advantage of the type-theoretic viewpoint is that it has direct implications for compiler writers. My work on the TIL compiler demonstrates the importance of typed intermediate languages for building compilers that generate efficient machine code. The stages of the TIL compiler are defined as type-directed translations that transform both a program and its type. This allows the compiler to take advantage of type information at compile-, link-, and run-time. The TIL ML compiler generates code that is three times faster and uses half the space of other competing compilers.

Types are also a useful tool for prototyping programming languages and proving properties of programs. My work with Frank Pfenning on the LF logical framework is concerned with the development of a "logic workbench" that allows one to implement formal systems such as type systems for programming languages or logics for reasoning about programs. The LF language is a simple, yet expressive, type theory in which one may describe the abstract syntax and deductive apparatus of a formal logical system. The Elf programming language may be used to build proof checkers and theorem provers for a logic specified in LF. In a recent case study Elf was used to define a small assembly language for network packet filters and to define a logic for stating and proving memory invariants of programs written in this language. The program, together with the LF representation of its proof, form a "self-certified" binary that may be safely installed in an operating system kernel without fear of violating the kernel's memory. Elf has also been used to prototype experimental languages, and to study the properties of logical systems such as Girard's linear logic.

URL: http://www.cs.cmu.edu/~rwh
Fox Project: http://foxnet.cs.cmu.edu
Logical Frameworks: http://www.cs.cmu.edu/afs/cs/user/fp/www/lfs.html

My research interests revolve around the integration of text, image video and audio analysis. In the Informedia Project we have built the News-on-Demand application, which is an instantiation of the Informedia Digital Video Library idea, based completely on automatic methods for processing television and radio news. Through the combination of the strengths of speech recognition, natural language processing, information retrieval and interface design, the system is able to overcome some of the shortfalls inherent in each of the component technologies.

My goal is to utilize large corpora of "found data", that is data that is already available through the Internet or other readily accessible open sources, to improve speech and natural language processing by exploiting advantages across different modalities. It has become clear in recent years that large volumes of text, image, video and audio can be easily stored and made available for research and applications. However, most of these text, image, video and audio sources were not produced with computer processing in mind. My intention is to design and build intelligent, understanding programs that help process data from these sources and make the data useful for other applications. This data can be used to improve speech recognition, image understanding, natural language processing, machine learning as well as information retrieval. The challenge is to find the right data, process it into suitable form for training, learning or re-use and build mechanisms that can successfully utilize this data.

Speech and multimedia technology is about to make a major impact on our daily interaction with computers. What is needed at this point are clear demonstrations of the advantages of integrated speech and multimedia interfaces.

My interests are centered in computer graphics but include related fields such as image processing, computer vision, and scientific computing. I enjoy working with a variety of issues, including mathematical, computational, user-interface, and artistic concerns. A broad summary of my research goals is: the development of algorithms and software tools to facilitate the creation and manipulation of pictures and other multidimensional data. Some applications which motivate much of my work are: computer animation for movies, computer aided design, and scientific visualization for education, science, and engineering. Some of my recent research is in the area of image synthesis, also known as rendering. Realistic image synthesis, the generation of images of mathematically-described three-dimensional scenes that are indistinguishable from reality, is a very challenging goal.

One of the fundamental computational challenges of realistic image synthesis is the simulation of global illumination, the interreflection of light in a 3-D scene. I am currently investigating radiosity methods for doing such simulations, in which a surface is subdivided using a mesh and a large system of equations is solved to compute the brightness of each triangle in the mesh. Our current research involves better methods for meshing that take occlusion into account, wavelet techniques for solving the equations efficiently, and fast methods for generating shadows. Future work will generalize these methods to work well on curved and shiny surfaces.

Another area of my research is surface modeling: their interactive design, their representation, and their efficient display. Prof. Andy Witkin and I developed a particle-based technique that allows very general, interactive design of implicit surfaces. Our repelling particle technique has also been generalized to create a flexible 2-D mesh generator useful for surface meshing in computer graphics and other applications in scientific computing. To speed up the display of complex geometric models, I am currently developing new multiresolution modeling techniques that represent objects at multiple levels of detail. When an object is viewed from up close, a detailed model is drawn; but when viewed from the distance, a coarse approximation is drawn. How do we make multiresolution models quick, accurate, and seamless? Multiresolution techniques have applications in flight simulators, video games, computer aided design, geographic information systems, and cartography. A graduate student and I have recently developed some fast algorithms for simplifying terrain data and more general 3-D objects that generate quite accurate approximations.

This is a summary of my current research, but my interests are not limited to these topics.

My research interests lie in the area of user interface software and technology. I am interested in creating tools and software infrastructure which make it possible to produce high quality user interfaces quickly and economically. This work includes the creation of innovative new interaction techniques for 2D and 3D interaction, development of advanced user interface toolkits, work in the use of constraint systems for user interface implementation, and higher level user interface specification tools.

I am also interested in using new media (such and audio and video) and new interaction modalities (such as pen-based interaction) to create new ways in which people can interact with computers. In this area I am currently working on new techniques for hybrid paper electronic interfaces. This work attempts to expand the usefulness of physical paper as an interaction medium by adding electronic capabilities to it such as searching, hyperlinking, and dynamic content. Finally, I am also working on new techniques for using audio and video communications to support awareness in distributed work groups.

My primary research interest is in creating engineering models of human performance to be used in the design of human-computer interaction. Such models seek to optimize several criteria that distinguish them from traditional cognitive models: the ability to make zero-parameter predictions, the ability to be taught to and be used by computer systems designers, coverage of total tasks, and approximation.

Engineering models must be able to make predictions in the absence of a working, or even simulated, system because the predictions are needed early in the design process, where they can be used to shape the specifications of the system. Any parameters used to make the predictions must be set during the development of the modeling technique, not when the technique is being applied to a new situation. This does not mean that parameters have to be fixed constants for every situation, only that they must be determinable a priori. Tables of parameters covering a wide range of tasks can be used to estimate values for a new situation and these are created from research done in the development of the modeling technique. Such graphs or tables build in basic psychology so that computer designers can use the models effectively.

The target users of HCI engineering models are computer system designers, not usually trained psychologists or human factors experts. Thus, the designer cannot be counted on to bring psychological expertise to the task and the basic psychology must be built into the models. Tables of parameter estimates have already been given as an example of building in this expertise. In addition, the procedures must be clearly defined and representative examples must be presented to allow the techniques to be taught. This does not mean that the procedures have to be as structured as recipes in a cook book. However, there must be guidelines and rules about what to do in many representative situations so that a style of analysis can be developed that leads to good predictions.

The activities people perform when interacting with computers are quite varied. These include reading, searching for information on the CRT screen, processing information relevant to task goals, forming plans, typing, pointing, learning, making and recovering from errors, and a myriad of other activities that overlap and interact with each other. Engineering models must do more than focus on each activity in isolation, they must allow prediction of the overlap and interaction between activities. Coverage of total tasks is the most difficult criteria for engineering models to satisfy.

Engineering models of human performance must produce useful predictions at different levels of approximation. Some design situations require gross predictions of performance, e.g., selecting a word processor based on how long it will take to complete some benchmark tasks. Other design situations require much finer grained analyses, e.g. predicting where a combat pilot's visual attention is directed at every moment during a tactical maneuver so the effects of a new visual display can be assessed. Engineering models meet different design needs by providing approximations to the mechanisms that produce behavior. Models of mechanisms and processes allow operations to be grouped, averaged over, or ignored, as appropriate to the design situation.

One engineering model of human performance has been developed over the last decade, GOMS, which forms the basis for my continuing work. GOMS stands for Goals, Operators, Methods, and Selection rules, which are the components of the user's knowledge and task requirements necessary to predict user performance. GOMS has received a decade of academic interest and laboratory research, and has been demonstrated to be a valuable real-world evaluation and design tool for task-specific workstations (e.g., workstations for telephone operators). A current GOMS project models the behavior of architects using complex CAD systems to increase their productivity. I am currently working within the Soar cognitive architecture to extend GOMS and produce more complete engineering models. The current focus of this work is in modeling rapid interaction with the environment. One current project investigates how expert programmers interleave planning and coding and use the information displayed by their programming environment to structure their work. Another project investigates the mechanisms for problem solving and learning in the externally-driven, fast-paced domain of video games. A third models learning in an air-traffic controller task. My secondary research interest is in understanding the usefulness and usability of predictive HCI assessment techniques other than engineering models. I have an ongoing project to apply other techniques (e.g., Heuristic Evaluation, Cognitive Walkthrough, User Action Notation, Claims Analysis) to the design of complex systems (e.g., programming environments, multi-media authoring tools) to determine what types of usability problems these techniques can identify, how much effort it is to learn and use them, to what types of systems and at what stage of development they can best be applied, and how their results compare to empirical methods.

My research interests lie in the areas of network protocols, operating systems, and distributed systems, particularly in the interactions between these areas. Most of my current research is in the area of adaptive protocols for wireless and mobile networking, and I am currently leading the Monarch Project at CMU in this area.

Wireless networks have fundamentally different properties than typical wired networks, including higher error rates, lower bandwidths, nonuniform transmission characteristics, increased usage costs, increased susceptibility to interference and eavesdropping, and higher variability of performance. Similarly, mobile hosts behave differently and have fundamentally different limitations than stationary hosts. For example, mobile hosts generally operate on limited battery power and may move and change their point of connection to the network at any time. These differences in network and host properties produce many new challenges for network protocols.

Our research in the Monarch Project is addressing these challenges through the development of new networking protocols and protocol interfaces to allow a level of wireless and mobile networking support substantially beyond what is possible with traditional protocols. Our goal is to create an integrated set of protocols that allow mobile computers, and the applications running on them and communicating with them, to seamlessly make the most efficient use of the best available network connections at any time. For example, each time a mobile host changes its location, the routing protocols must adapt in order to continue to route packets to the mobile host. In addition, different wireless networking products or services, intended for example for local-area, metropolitan-area, and wide-area use, must make different tradeoffs in factors such as bandwidth, latency, error rate, and usage cost, providing different levels of quality of network connection to the mobile host. With each change in mobile host location, the routing decisions should take these differences into account, and higher-layer protocols and applications on the mobile host and on other hosts communicating with the mobile host should be able to adapt to the characteristics of the mobile host's new network connection.

The Monarch Project covers areas ranging roughly from portions of the ISO Data Link layer (layer 2) through the Presentation layer (layer 6). Our research approach consists of four themes:

• Protocol design and implementation of new protocols for wireless and mobile networking, or improvements to existing protocols to better support this goal. We have developed new protocols for mobile internetwork routing (Mobile IPv4 and Mobile IPv6) and wireless mobile ad hoc networking (DSR), and are also actively working on other protocol areas.
• Performance measurement and simulation of the protocols we develop, to better understand and improve their behavior and to improve their design. We have been very active in the implementation of the protocols we develop, and have also developed a very detailed, realistic wireless and mobile network simulator that we are using in evaluating our work.
• Usage-based evaluation of these protocols, to analyze how the protocols behave in actual operational usage. For example, we have deployed Mobile IP home agents and foreign agents on four major subnets on campus and hope to enlarge our user community to better evaluate the protocol under real usage.
• Active contribution to Internet standards through the IETF, the principal protocol standards development organization for the Internet. Active participation in the IETF (Internet Engineering Task Force) provides a unique opportunity to transfer the results of our research into the Internet community, and we have been very successful at this in our work.

The Monarch Project is named in reference to the migratory behavior of the monarch butterfly. Each autumn, millions of monarch butterflies migrate from central and eastern United States and Canada to overwintering roosts in central Mexico; with the coming of spring, the monarch population again migrates northward. The name Monarch can also be considered as an acronym for Mobile Networking Architectures. Our work is currently funded by NSF, DARPA, the AT&T Foundation, and Caterpillar Inc., and we have also previously received funding from Bellcore, the Carnegie Mellon Information Networking Institute, and AEG Transportation Systems.

My research interests are in the areas of computer vision, visual and multi-media technology, and robotics. Common themes that my students and I emphasize in performing research are the formulation of sound theories which use the physical, geometrical, and semantic properties involved in perceptual and control processes in order to create intelligent machines, and the demonstration of the working systems based on these theories. My current projects include basic research and system development in computer vision (motion, stereo and object recognition), recognition of facial expressions, virtual(ized) reality, content-based video and image retrieval, VLSI-based computational sensors, medical robotics, and an autonomous helicopter.

Computer vision.
Within the Image Understanding (IU) project, my students and I are conducting basic research in interpretation and sensing for computer vision. My major thrust is the "science of computer vision." Traditionally, many computer vision algorithms were derived heuristically either by introspection or biological analogy. In contrast, my approach to vision is to transform the physical, geometrical, optical and statistical processes, which underlie vision, into mathematical and computational models. This approach results in algorithms that are far more powerful and revealing than traditional ad hoc methods based solely on heuristic knowledge. With this approach we have developed a new class of algorithms for color, stereo, motion, and texture.

The two most successful examples of this approach are the factorization method and the multi-baseline stereo method. The factorization method is for robust recovering shape and motion from an image sequence. Based on this theory we have been developing a system for "modeling by video taping"; a user takes a video tape of a scene or an object by either moving a camera or moving the object, and then from the video a three-dimensional model of the scene or the object is created. The multi-baseline stereo method, the second example, is a new stereo theory that uses multi-image fusion for creating a dense depth map of a natural scene. Based on this theory, a video-rate stereo machine has been developed, which can produce a 200x200 depth image at 30 frames/sec, aligned with an intensity image; in other words, a real 3D camera!!

Currently, we are working on a rapidly trainable object recognition method, a system for modeling-by-video-taping, and a multi-camera 3D object copying/reconstruction method.

Visual media technology for human-computer interaction.
A combination of computer vision and computer graphics technology presents an opportunity for a new exciting visual media. We have been developing a new visual medium, named "virtualized reality." In the existing visual medium, the view of the scene is determined at the transcription time, independent of the viewer. In contrast, the virtualized reality delays the selection of the viewing angle till view time, using techniques from computer vision and computer graphics. The visual event is captured using many cameras that cover the action from all sides. The 3D structure of the event, aligned with the pixels of the image, is computed for a few selected directions using the multi-baseline stereo technique. Triangulation and texture mapping enable the placement of a soft-camera to reconstruct the event from any new viewpoint. The viewer, wearing a stereo-viewing system, can freely move about in the world and observe it from a viewpoint chosen dynamically at view time. We have built a 3D Virtualized Studio using a hemispherical dome, 5 meters in diameter, currently with 51 cameras attached at its nodes. There are many applications of virtualized reality. Virtualized reality starts with a real world, rather than creating an artificial model of it. So, training can become safer, more real and more effective. A surgery, recorded in a virtualized reality studio, could be revisited by medical students repeatedly, viewing it from positions of their choice.

Or, an entirely new generation of entertainment media can be developed - "Let's watch NBA in the court": basketball enthusiasts could watch a game from inside the court, from a referee's point of view, or even from the "ball's eye" point of view.

Also, I am interested in and currently working on vision techniques for recognizing facial expression, gaze, and hand-finger gestures. Such techniques will provide natural non-intrusive means for human-computer interface by replacing current clumsy mechanical devices, such as datagloves.

Computational Sensor.
While significant advancements have been made over the last 30 years of computer vision research, the consistent paradigm has been that a "camera" sees the world and a computer "algorithm" recognizes the object. I have been undertaking a project with Dr. Vladimir Brajovic that breaks away from this traditional paradigm by integrating sensing and processing into a single VLSI chip a computational sensor. The first successful example was an ultra fast range sensor which can produce approximately 1000 frames of range images per second an improvement of two orders of magnitude over the state of the art. A few new sensors are being developed including a sorting sensor chip, a 2D salient feature detector (2D winner-take-all circuits), and others.

Medical Robotics and Computer Assisted Surgery.
The emerging field of Medical Robotics and Computer Assisted Surgery strives to develop smart tools to perform medical procedures better than either a physician or machine could alone. Robotic and computer-based systems are now being applied in specialties that range from neurosurgery and laparoscopy to opthalmology and family practice. Robots are able to perform precise and repeatable tasks that would be impossible for any human. The physician provides these systems with the decision making skills and adaptable dexterity that are well beyond current technology. The potential combination of robots and physicians has created a new worldwide interest in the area of medical robotics. We have developed a new computer assisted surgical systems for total hip replacement. The work is based on biomechanics-based surgical simulations and less invasive and more accurate vision-based techniques for determining the position of the patient anatomy during a robot surgery. The developed system, HipNav, has been already test-used in clinical setting.

Vision-based Autonomous Helicopter.
An unmanned helicopter can take maximum advantage of the high maneuverability of helicopters in dangerous support tasks, such as search and rescue, and fire fighting, since it does not place a human pilot in danger. The CMU Vision-Guided Helicopter Project (with Dr. Omead Amidi) has been developing the basic technologies for an unmanned autonomous helicopter including robust control methods, vision algorithms for real-time object detection and tracking, integration of GPS, motion sensors, vision output for robust positioning, and high-speed real-time hardware. After having tested various control algorithms and real-time vision algorithms using an electric helicopter on an indoor teststand, we have developed a computer controlled helicopter (4 m long), which carries two CCD cameras, GPS, gyros and accelerometers together with a multiprocessor computing system. Autonomous outdoor free flight has been demonstrated with such capabilities as following pre-scribed trajectory, detecting an object, and tracking or picking it from the air.

Toward this goal, I create "cognitive models", computer simulations of student thinking and learning, that are used to guide the design of educational materials, practices and technologies. These cognitive models provide the basis for an approach to educational technology called "Cognitive Tutors" in which we create rich problem solving environments for students to work in and provide just-in-time learning assistance much like a good human tutor does. I have developed Cognitive Tutors for mathematics and science and have tested them in the laboratory and the classroom. In a whole-year classroom study with our Algebra Cognitive Tutor, I have shown that students in our experimental classrooms outperformed students in control classes by 50-100% on targeted real world problem solving skills and by 10-25% on standardized tests.

My research has contributed new principles and techniques for the design of educational software and has produced basic cognitive science research results on the nature of mathematical thinking and learning. I am currently a codirector of the Pittsburgh Advanced Cognitive Tutor (PACT) Center and am managing teams of cognitive scientists, programmers, and teachers to create integrated learning solutions that include text materials, teacher training and Cognitive Tutors. I am a co-founder and board member of Carnegie Learning Inc., a new company that is marketing these technology-enhanced learning solutions to schools and colleges across the country.

I have broad interests in the design and social impact of computing and have conducted research on office automation and employment quality, technology and home-based employment, the communication needs of collaborating scientists, the design of information technology for small-group intellectual work, and the impact of national information networks on organizations and families.

My research in an area examines in detail the challenges groups currently have in performing social tasks, designs new technology to meet some of these challenges, and evaluates the usefulness of the new technology. This cycle of needs assessment, technological design, and evaluation has both scholarly and applied products. For example, research on scientific communication treats scientists as prototypical of collaborating work teams and examined the problems they must solve to accomplish their work and the technologies that might aid them. Other empirical work examined the process by which executive teams engaged in a semester-long business simulation develop shared mental models and the effects of these models on their success. Together this research has contributed both to contemporary theories of team performance and to the design and demonstration of experimental information system for informal interaction, for collaborative writing, and for collaborative awareness.

I am also conducting research on the role that nationwide computer networks, like Minitel in France or the Internet in the United States, have on the interrelationships among firms and on the dynamics of the family. These networks increase the efficiency with which firms can search for or exchange information with each other, but they also shift the type of information that can easily exchanged, from personal to quantitative. The research examines how these shifts in the cost and quality of communication may influence interfirm loyalties and market relationships. At the level of the family, the research examines how easy access to remote and personalized information sources and communication partners changes family's dependence on local resources, among other topics.

Language Technologies.
One of the most challenging, fascinating, and applicable areas of research in human language technologies is the design of computational models of language as a statistical source. Suppose that we were to play a game where I read to you from the The New York Times and periodically ask you to guess the identity of the next word. The entropy of the Times is the average number of yes-or-no questions that you need to ask---if you're as clever as you can be---to determine the identity of the word. The goal of language modeling is to develop computer programs that play this game well. The notion of entropy provides a mathematical foundation on which to build solutions to this problem. We have recently used language models as the basis for a new approach to unsupervised clustering of documents and words; such clustering algorithms are important for a wide variety of tasks in information retrieval, natural language and speech processing.

Statistical Learning Algorithms.
Many of the tasks that we work on in language technologies use machine learning algorithms to extract patterns from historical data to predict future behavior. An example is our work on text segmentation in which we build an exponential model to extract relevant features of the surrounding text to determine where to place story boundaries. There are fascinating connections between these techniques and "boosting" algorithms in machine learning, as well as more classical regression techniques in statistics. We are working to develop the links between these different areas, and to formulate them in terms of a general computational framework for statistical inference.

Coding and Information Theory.
Algorithms on graphical structures play a central role in both communications technology and formal verification. We have recently established a close correspondence between trellises, which are widely used in the construction and decoding of error-correcting codes, and binary decision diagrams, which have found widespread use in computer-aided design and formal verification of digital circuits. Based on this bridge, we are working to transfer ideas between these previously disparate fields. The fundamental problem that confronts both uses of graphical methods is the same: devise techniques to combat the exponential blowup in the size of the graph. In addition to coding and verification, we are also investigating applications of the underlying ideas to such areas as database search.

My research is in the design and implementation of advanced programming languages. I am especially interested in approaches based on principles from formal semantics and type theory, with a particular emphasis on applications in operating systems and networks. Much of my work is centered around the Standard ML programming language (SML) and its theoretical underpinnings. SML provides many advanced features, including first-class functions and continuations, polymorphic types with automatic type inference, garbage collection, and a powerful system for specifying parameterized modules. Jointly with Robert Harper, I work on the Fox Project, which is using SML to implement high-speed network communication protocols. Not surprisingly, we get great benefits from the expressive power, type safety, and support for modularity and composability provided by SML. As a result, our networking system is extremely reliable and easy to reconfigure for special-purpose applications. (You can try out our web server written in SML. This is also a good way to get more information about the Fox Project.)

Using SML directly for systems programming is just the tip of an iceberg, however. What is actually more significant than the language itself is the theoretical foundation that has been developed for the language. This theory has the potential for applications beyond the realm of the SML language itself. The main areas for my focus are the following:

Proof-Carrying Code.
One problem that is becoming more important in distributed and web computing is how one agent (the code consumer) can be assured of safety when it executes code supplied by another agent (the code producer). Instead of using expensive run-time mechanisms such as separate address spaces or dynamic fault checks, Proof-Carrying Code (PCC) requires that the code producer to supply a proof that the code is safe. The proofs are written in a special language (without any use of cryptography) so that the code consumer can know with total confidence that the code is safe. To date, the concept and some limited demonstrations of PCC have been developed, but much more work needs to be done in order to make it fully practical.

Program Analysis and Transformation.
The ML language has a well-defined formal semantics, which forms an excellent basis for developing static analyses and optimizations. However, some of the advanced features of the language, such as higher-order functions, make it hard to get precise information from a static analysis. My students and I have been working in the general mathematical framework of Abstract Interpretation to overcome these problems.

Run-Time Code Generation.
There are many situations, especially in systems such as network protocols, where information that would be useful for compiler optimization becomes available only at run time, but once available, it remains relatively static. In such cases, it is often profitable to delay some optimization and code generation until run time. I have been working on using techniques from partial evaluation to achieve very fast and effective run-time optimization and generation of ML programs, so as to exploit these kinds of situations. For example, using a prototype system, we can demonstrate an interpreter for Berkeley Packet Filters written in ML. Our system achieves a 40% reduction in per-packet latency over the Berkeley C implementation. The unifying theme of all of these research problems is the exploitation of the underlying semantics of the programming language. It is my strong belief that this will be one of the keys to new approaches to software development.

My research involves the application of computational, modeling and electrophysiological techniques to study the neural basis of visual perception and recognition. The current effort of my laboratory is focused on the following scientific issues in the areas of computational neuroscience and computational vision.

The first issue concerns with feedback and hierarchical computation in the visual system. The classical paradigm for vision, as delineated by Marr, is that vision is accomplished by a series of feedforward computations in the visual hierarchy. The experimental findings from my laboratory show that global contextual information can modify the computation in early visual areas, presumably mediated by the massive recurrent feedback from the higher level cortices to the earlier ones. What is the functional role of this feedback? What are the advantages of the concurrent and interactive computation across the visual hierarchy? To address these questions, we are constructing and testing computational models and realistic neural circuits in conjunction with recording from neurons across the visual hierarchy while the monkeys are observing stimulus patterns of different complexity.

The second issue concerns with the dynamic and active aspects of vision. Much of the vision research has focused on the analysis of patterns in static situations by the visual system or by computer. Vision in reality is an active and dynamic process. Our eyes move constantly, purposefully scanning the environment to construct a coherent internal representation of the scene based on the retinal data, which is precise only in the fovea. How are these bits and pieces of retinal information assembled and integrated over time to form a seemingly coherent picture of the world? How and where are these scene elements represented in the brain? To address these questions, we are conducting human psychophysical experiments to examine information transfer across saccadic eye movements, formulating and testing computational models for scene integration, recording from neurons when monkeys are actively scanning and searching in the visual environment.

The third issue concerns with neural plasticity and learning. The brain is an adaptive system. Even after development, the neural circuits remain plastic and exhibit changes with learning. Currently, we are implanting electrode arrays of 100 electrodes into the monkeys' neocortex to record from the same neurons in the visual system over long periods of time (months) during which the monkeys will be trained to perform new perceptual grouping and perceptual discrimination tasks. The experiments are inspired by unsupervised and reinforcement learning models, but we hope to infer from the neurophysiological data the neural algorithms underlying the development, formation and maintenance of neural circuits in the visual hierarchy.

The fourth issue concerns with the structure of neural code For the last thirty years, the average firing rate of the neurons has been considered to be the most reliable measure of neural information. We are analyzing single and multi-electrode data to examine the possible existence of precise temporal spike pattern hidden in the neural spike trains that may encode higher order structures using various pattern analysis, machine learning and statistical techniques.

By elucidating the neural code, representations and algorithms underlying biological computation and learning, we hope not only to gain a better understanding of the mind and the brain, but also to discover new and more powerful ways to build learning systems and robots.

My research focuses on computational approaches to understanding cognition, especially the human language capability and its relationship to human and machine learning. My approach includes both the creation of fine-grained computational models of language processing and the creation of environments for augmenting and facilitating human-computer language interactions. Past research includes the creation of an adaptive natural language interface (CHAMP) that learned the idiosyncratic grammars of different individuals. Together with students, I subsequently developed two systems within the Soar architecture. EFH-Soar was a project that studied the efficacy of education in microworld environments through modeling and empirical testing. NL-Soar, my main focus during the past seven years, is a comprehensive cognitive model of adult language comprehension and production, integrating language, learning, problem-solving and action in a unified framework. Most recently I have refocused my research toward developing a computer-based environment for remediating language in language-disordered children -- work that builds directly on my previous experience with adaptive interfaces, human language modeling, and education in microworlds.

Unlike other software intervention, Simone Says is designed to be a speech-based, interactive environment intended initially for young, non-mute children with autistic spectrum disorders. It creates opportunities for meaningful, verbal language practice across a wide range of linguistic tasks in a simple social world. Tasks cover vocabulary, basic syntax, semantics and pragmatics, joint attention, conversational turn taking, and simple conversational repair. The system's design combines sound clinical practice with the engaging features found in off-the-shelf early learning software, including child-centered control, animation and sound, and readily-available help in the form of animated character guides. It is the child who decides which object(s) to talk about from those visually available and what to make the object(s) do. However, in all instances only referentially meaningful utterances produce an animation, with modeling available if the child cannot produce one. When a language concept is first introduced, the child is unlikely to give a meaningful response to the visual image. In this circumstance, using Simone Says is like a linguistic game of Simon Says: Simone models, the child repeats. As the child's language grows, however, using the system becomes more like verbally clicking on visual hot spots: meaningful speech produces meaningful action on demand. From the child's perspective, increasing proficiency is rewarded by increasing control. Creating Simone Says requires a number of advanced technologies. A primary requirement is a speaker-independent, continuous speech recognition system (such as SPHINX-II) with an acoustic model that can be adapted to young children's voices. Simone Says also requires a method for dynamically tracking the child's language development (such as the one in CHAMP) in order to construct the next target example and provide a constrained language model to the recognizer. Finally, the system must have a method for translating the linguistic description of the next example into a visual image and animation that can dynamically accommodate variation along dimensions such as color, size, number of objects, participation of animated characters, and substitution of objects from the same semantic class. The off-the-shelf animation authoring environment Director seems to be adequate to the task. Each of the components is understood well enough to make an initial implementation of Simone Says feasible. The main contribution clearly lies in bringing all these independently-developed technologies together into a coherent, engaging, and pedagogically effective real-time environment.

I am interested the computational principles underlying the ability of the brain to represent and process of complex, real-world patterns. To understand how we perform such tasks as speech or object recognition, we must not only tackle the question of how to code sensory information, but also how this code is processed to represent more abstract properties of the stimulus. For example, what are the basic computations underlying the formation of perceptual invariances such as the ability to recognize words independent of speaker or objects independent of orientation? Research in my lab works toward these goals by developing and applying principles of information representation and processing.

Computational Principles of Sensory Coding.
Part of my work focuses on the issue of sensory coding: How should natural images or sounds be encoded? One approach that my research has developed is the application of probabilistic models to learn codes that are efficient in an information theoretic sense. Given a particular sensory environment, this top-down computational approach makes predictions about the properties of neural codes at the population level. When this approach is applied to natural images, the resulting representation very closely matches the receptive field properties of visual cortex cells. This framework also demonstrates that the model system encodes natural images more efficiently than many common Fourier or wavelet-based coding schemes. Because the theory based on general probabilistic models of a high dimensional data space, it can be applied to a variety of sensory patterns including static and dynamic visual images as well as patterns from different acoustic environments. A recent extention of this theoretical framework to the temporal domain led to a theory for how continuous time-varying signals can be optimally represented by a population of spiking neurons.

Higher-Order Representation and Inference.
A second aim of my work is to develop algorithms for learning hierarchical representations. These are important because they can extract successively more abstract properties of the sensory patterns and may provide insight into how the brain carries out more complex aspects of perception that subserve object recognition. One result of this work has been a computational explanation for the role of feedback, which is ubiquitous in the brain, but poorly understood. The long term goal of this research is to develop abstract neural architectures and learning algorithms that help elucidate the details of the higher-level processes that allow the brain to perceive and process natural stimuli under a wide range of conditions. These include the computational principles underlying the representation and learning of perceptual invariances and attentional processes such as auditory and visual scene segmentation.

Image and Signal Processing.
As we better understand ways in which