Carnegie Mellon University
Department of Computer Science

AI Seminar 97/98 Schedule

Time: Tuesday 3:30-4:30pm
Place: Wean Hall 5409

Speakers' Guide | Mailing List | RI Seminar | CNBC Seminar | VASC Seminar | CALD Seminar

Date	Speaker	Affiliation	Topic
Spring 1998
01/27/98	Raj Reddy	Carnegie Mellon University	Information Infrastructure
02/03/98	Yiming Yang	Carnegie Mellon University	Translingual Information Retrieval
02/10/98	Tuomas Sanholm	Washington University	Negotiation among Agents
02/17/98	Craig Boutilier	University of British Columbia	Reinforcement Learning
02/24/98	Herb Simon	Carnegie Mellon University	Cumulative Science
03/10/98	Andy Barto	University of Massachusetts, Amherst	Reinforcement Learning
03/31/98	Murray Campbell	IBM	Deep Blue
04/07/98	Yair Weiss	Massachusetts Institute of Technology	EM and Loopy Belief Propagation
04/14/98	Michael Langer	NEC Research Institute	Illumination Models in Vision
04/21/98	Martha E. Pollack	University of Pittsburgh	Planning in Dynamic Environment
04/28/98	Wesley Chu	University of California, Los Angeles	Image Retrieval
05/13/98 (special date!)	Justin Boyan	Carnegie Mellon University	Learning for Global Optimization
05/19/98	Andrew McCallum	Just Research, Pittsburgh	Text Classification
05/26/98	Donald Peterson	Birmingham University, UK	Matching Relational Data
0?/??/98	David Mumford	Brown University	Pattern Theory
Fall 1997
09/23/97	Rich Caruana	Carnegie Mellon University	Multitask Learning
09/30/97	Manuela M. Veloso	Carnegie Mellon University	Multi Agent System
10/07/97	Andrew Moore	Carnegie Mellon University	Machine Learning
10/14/97	Jack Mostow	Carnegie Mellon University	Project LISTEN
10/21/97	Katia Sycara	Carnegie Mellon University	Intelligent Software Agent
11/04/97	Richard Korf	University of California, Los Angeles	Search and Planning
11/11/97	Raymond Mooney	University of Texas at Austin	Relational Learning
11/18/97	Daphne Koller	Stanford University	Probabilistic Reasoning
11/25/97	Roger Dannenberg	Carnegie Mellon University	Computer Music
12/09/97	Wei-Min Shen	University of Southern California	Dynamic Agents

The AI seminars are open to the public and will be held on most Tuesdays at 3:30pm in Wean Hall, Carnegie Mellon University. Special AI seminars can be arranged for visitors on dates other than Tuesdays. The schedule will be updated daily. To volunteer to give an AI seminar or to nominate an outside speaker, contact Dr. Tai Sing Lee at tai@cs.cmu.edu.

All AI seminars will be posted to both cboards and bboards (cs & robotics). Meanwhile, if you would like to/not to be reminded by email, please subscribe/unsubscribe ai-seminar-announcements mailing list by sending email to Sebastian_Thrun@heaven.learning.cs.cmu.edu. Simply put "Subscribe/Unsubsribe ai-seminar-announcements" in the subject of your message.

01/27/98 - Raj Reddy Carnegie Mellon University

AI and Scalable Information Infrastructure

What are the barriers to creating Scalable Global Information Infrastructure(Web, Internet) that could serve a billion people? Such a goal implies ensuring that networks, communications, and computers are sufficiently scalable, have the performance bandwidth to achieve an information infrastructure that is ubiquitous, secure, easy to use, and accessible to every citizen of the world. Besides systems issues such as ubiquitous connectivity, quality of service guarantees, and performance guarantees, it should also satisfy the attributes that we expect from any intelligent system. To be universally usable such a system should exhibit attributes such as: operate in real-time; exploit vast amounts of knowledge; tolerate errorful, unexpected and possibly unknown input; use symbols and abstractions; communicate using natural language; learn from the environment; and exhibit adaptive goal-oriented behavior. In this talk we will explore the AI research agenda that needs to be undertaken to contribute to this important societal goal.

Raj Reddy is Dean of the School of Computer Science at Carnegie Mellon University and the Herbert A. Simon University Professor of Computer Science and Robotics. From 1960-63, Dr. Reddy worked as an Applied Science Representative for IBM Corp., in Australia. He began his academic career as an Assistant Professor at Stanford in 1966. He joined the Carnegie Mellon faculty as an Associate Professor of Computer Science in 1969. He became a Full Professor in 1973, a University Professor in 1984, and named as the Simon University Professor in 1992. He served as the founding Director of the Robotics Institute from 1979 to 1991 and as the Dean of the School of Computer Science since 1991. Dr. Reddy received a BE degree from the Guindy Engineering College (currently named Anna University) of the University of Madras, India in 1958 and a MTech degree from the University of New South Wales, Australia, in 1960. He received a Ph.D. degree in Computer Science from Stanford University in 1966. Dr. Reddy's research interests include the study of human-computer interaction and artificial intelligence. His current research projects include speech recognition and understanding systems; collaboration on the web; universal digital libraries; and learning on demand. His professional honors include: Fellow of the Institute of Electrical and Electronics Engineers, Fellow of the Acoustical Society of America, Fellow of the American Association for Artificial Intelligence, Member of the National Academy of Engineering and Member of the American Academy of Arts and Sciences. He was president of the American Association for AI from 1987 to 89. He is a recipient of the IBM Research Ralph Gomory Fellow Award in 1991. Dr. Reddy was awarded the Legion of Honor by President Mitterand of France in 1984. He is a recipient of the ACM Turing Award in 1995. He was named a member of President's Information Technology Advisory Committee in 1997.

02/03/98 - Yiming Yang Carnegie Mellon University

Translingual Information Retrieval: Learning from Bilingual Corpora

This talk introduces several new approaches to translingual information retrieval (TIR), based on statistical learning of term equivalences in context from bilingual corpora. Our methods include example-based term translation, TIR versions of pseudo-relevance feedback, the Generalized Vector Space Model, and Latent Semantic Indexing (new implementation). Empirical validation shows that these corpus-based approaches significantly outperform dictionary-based query translation, heretofore the most popular method in the literature.

Yiming Yang is a Senior Research Computer Scientist at the School of Computer Science at Carnegie Mellon University. She received her B.S. degree in Electrical Engineering, and her M.S. and Ph.D. degrees in Computer Science (Kyoto University, Japan). Her research has centered on statistical learning approaches to text categorization, retrieval, clustering, summarization, multimedia and translingual information access, and intelligent search in digital libraries and Internet environment. Dr. Yang received the Academy Prize of Information Processing Society of Japan in 1985, the Best Theoretical Paper Award at the Annual Symposium on Computer Application in Medical Care in 1993 and 1994, and the Distinguished Paper Award at the International Joint Conference of Artificial Intelligence in 1997.

02/10/98 - Tuomas Sandholm Washington University

Negotiation among Computationally Limited Self-Interested Agents

Tuomas Sandholm is Assistant Professor of computer science at Washington University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994 respectively. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has a broad range of research interests including multiagent systems, rational resource-bounded reasoning, electronic commerce, game theory, negotiation, coalition formation, voting, network pricing, machine learning, constraint satisfaction, combinatorial optimization, and scheduling. He has also co-developed two fielded AI systems, and holds the Chief Scientist position at an electronic commerce startup company that he recently co-founded. He has published over 50 technical papers, and has received several academic awards including the NSF CAREER award in 1997.

02/17/98 - Craig Boutilier University of British Columbia

The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems
(joint work with Caroline Claus)

Craig Boutilier is an Associate Professor of Computer Science at the University of British Columbia and is a member of the Laboratory for Computational Intelligence. He received his Ph.D. in 1992 from the University of Toronto. His research interests are in planning and sequential decision making, Markov decision processes and reinforcement learning, probabilistic reasoning, and knowledge representation schemes for actions and preferences. He is an Associate Editor of the international Journal of Artificial Intelligence Research. He is currently on sabbatical leave at the University of Toronto, supported by an Izaak Walton Killam Faculty Research Fellowship.

02/24/98 - Herb Simon Carnegie Mellon University

Brand Names and Cumulative Science

In AI, we typically (and properly) implement our research with large complex systems that employ a collection of interacting mechanisms to achieve their results. Hence, we often think of advances in AI knowledge in terms of the names of such programs: e.g., LT, GPS, EPAM, PRODIGY, Soar, BACON, Act-R --just to mention a few of local origin. However, it can be argued that the real "action" lies largely in the mechanisms embedded in these programs, and in issues about how such mechanisms can be combined effectively.

The "brand names" tend to make difficult the analysis and comparison of these mechanisms or the exchange of knowledge between research groups. One can argue that it has caused and causes an enormous amount of duplication of effort. Physicists did not divide quantum mechanics into the Heisenberg Brand, the Schrodinger Brand,and the Dirac Brand, but analyzed in detail the relations among these and use one or the other according to their computational power in particular situations. When specific "brand name" choices have arisen (wave v. particle theories of light, Ampere's v. Faraday"s theories of electromagnetism, phlogisten v. oxygen theories of production), they used experimental techniques to analyze both similarities and differences and to sort them out.

How can we develop AI theory that goes beyond Brand Names? What techniques do we have for comparing theories (more than staging horse races between them in particular tasks)? How do we trace particular mechanisms and their development through the theories in which they develop? The aim of the talk will not be to provide answers to all of these questions but to stimulate constructive discussion about new forms of research activity that will address them.

Herb Simon

03/10/98 - Andy Barto University of Massachusetts, Amherst

Reinforcement Learning: New Life for Some Old Ideas

Reinforcement learning refers to improving performance through trial-and-error experience. In this talk, I describe some of the surprising things about reinforcement learning that have emerged as it developed from principles of animal learning into a collection of useful methods for difficult dynamic optimization problems. I focus most on the implications of the Monte Carlo nature of reinforcement learning algorithms, which permits their application to stochastic problems without having to make relevant probability distributions explicit. I also discuss recent results showing the surprising importance of the on-policy sampling distribution for the successful use of function approximation methods for this kind of learning.

Andy Bartois Professor of Computer Science, University of Massachusetts, Amherst. B.S. in mathematics, 1970, Ph.D. in Computer Science, 1975, University of Michigan. Core faculty of the Neuroscience and Behavior Program, University of Massachusetts. Member: Society for Neuroscience, INNS. Senior member of the IEEE. Member and Fellow of the American Association for the Advancement of Science. INNS board of governors 1991-95. Member editorial board: Machine Learning, Journal of Artificial Intelligence Research; associate editor, MIT Press series Neural Network Modeling and Connectionism. Professor Barto's research centers on learning in natural and artificial systems, and he has studied learning algorithms for artificial neural networks since 1977, contributing to the development of associative reinforcement learning methods and their application to control problems. Current research centers on neural models of motor learning and reinforcement learning methods for real-time planning and control. He is co-author with R. Sutton of "Reinforcement Learning: An Introduction", MIT Press 1998.

03/31/98 - Murray Campbell IBM

Deep Blue: The IBM Chess Machine

Last year Deep Blue became the first computer to defeat the World Chess Champion in a regulation match, thereby fulfilling a long-standing challenge in computer science. Many factors contributed to Deep Blue's success, including a single-chip chess accelerator, a large-scale parallel system, selective search algorithms and a complex evaluation function. This talk will examine some of these factors and place them in the context of the nearly 50 years of computer chess research. I will also explore some of the many questions about machine and human intelligence that have been prompted by Deep Blue's win. Our current work involves applying some of the lessons learned from the Deep Blue experience to computationally demanding problems in data mining and finance.

Murray Campbell Murray Campbell is a research scientist at the IBM T.J. Watson Research Center. He is a member of the team that developed Deep Blue, the first computer to defeat the World Chess Champion in a regulation match, for which Campbell was awarded the Fredkin prize and the Allen Newell Research Excellence Medal. Deep Blue and its predecessor machines have won many other awards and distinctions, including first computer to defeat a Grandmaster in tournament play, the Fredkin Intermediate Prize for the first Grandmaster-level chess computer and the OMNI Challenge Prize. Campbell received his B.Sc. and M.Sc. from the University of Alberta (1979,1981), and his Ph.D. in Computer Science from Carnegie Mellon University (1987).

04/07/98 - Yair Weiss Massachusetts Institute of Technology

Smoothness in Layers: Motion Analysis, Perceptual Organization and the EM algorithm

Estimating motion in scenes containing multiple moving objects remains a difficult problem in computer vision yet is solved effortlessly by humans. I will briefly review experiments we have conducted to understand this astonishing performance in human vision. The results implicate an early perceptual organization process in which the scene is segmented into motion groups or segments, and smooth motion is assumed within a group. I will then present a new EM based algorithm that analyzes motion based on these principles. Distinguishing features of our algorithm include the automatic estimation of the number of models, the use of static coherence to aid the segmentation and the estimation of a nonparametric smooth motion field for each model. The algorithm's performance will be illustrated on real and synthetic image sequences. Joint work with Ted Adelson.

Loopy belief propagation --- from image understanding to error correcting codes.

Problems involving belief propagation arise in a wide variety of applications including error correcting codes, speech recognition and image processing. For singly connected networks, there exist local update rules that are guaranteed to converge to the optimal beliefs. Recently, however, a number of researchers have empirically demonstrated good performance of these same algorithms on networks with loops. Perhaps the most dramatic instance is the near Shannon limit performance of ``Turbo Codes''. These codes have been described as ``the most exciting and potentially important development in coding theory in many years'' but a theoretical understanding of their performance has yet to be achieved. I will describe analytical results relating the steady state beliefs in a network with a single loop and the true posterior probabilities. This leads to a category of loopy networks for which the MAP estimate obtained by belief propagation can be proven to be optimal (although the beliefs will be incorrect) and to a method by which nodes can use local information in the messages they receive in order to correct the steady state beliefs. I will discuss how to generalize these results to networks with multiple loops, and illustrate the results using examples from image understanding and error correcting codes.

Yair Weiss received his M.Sc in Applied Mathematics from Tel-Aviv University. For the past four years he has been a graduate student with Ted Adelson at the MIT Media Lab and the MIT department of Brain and Cognitive Sciences. His research interests include human and machine vision and probabilistic models. Details and publications are available at: http://www-bcs.mit.edu:/~yweiss

04/14/98 - Michael Langer NEC Research Institute

The Role of Illumination Models in Vision

A common intuition about human vision is that our visual systems are much better at judging certain scene properties such as the shape as material of surfaces than they are at judging other scene properties namely illumination. From a computational perspective, however, this intuition is puzzling since images depend as much on illumination as they do on shape and material. In this talk, I will address two questions that concern the role of illumination models in vision. How can a vision system recover shape from shading information when shading cues depend strongly on the lighting condition ? How might a vision system model different types of lighting conditions ? I will present novel computational models and psychophysical experiments that help us to answer these questions. I will also discuss an ecological role of illumination models namely to make explicit what parts of a scene are visible and why. Joint work with S. Zucker (Yale), J. Stewart (Toronto), and H. Buelthoff (MPI Tuebingen).

Michael Langer completed a B.Sc. in Mathematics from McGill University, an M.Sc. in Computer Science from the University of Toronto, and a Ph.D. in Electical Engineering from McGill University. He main research topic is computational models of vision. Since 1995, he has been a Scientist at the NEC Research Institute in Princeton, NJ.

04/21/98 - Martha E Pollack University of Pittsburgh

Plan Management in Dynamic Environments

Humans are planning creatures: they form plans to achieve their goals, and they make commitments to the execution of those plans. AI research on planning has focused primarily on modeling the first of these capabilities, designing and analyzing algorithms for plan generation. I will argue that the second capability is at least as important for agents that must inhabit dynamic, uncertain environments. When agents commit to future plans, they need to be able to manage those commitments. I will describe the kinds of reasoning tasks that are involved in plan management in dynamic environments, and will survey approaches that have been taken towards developing computational models of plan management, giving emphasis to plan-management strategies that my colleagues and I have been investigating.

Martha E Pollack is Associate Professor of Computer Science and Intelligent Systems at the University of Pittsburgh. She received her A.B. degree (1979) in linguistics from Dartmouth College and her M.S. and Ph.D. degrees (1984, 1986) in Computer and Information Science from the University of Pennsylvania. From 1985 until 1991, she was employed at the Artificial Intelligence Center at SRI International. Pollack is a recipient of the Computers and Thought Award (1991), a National Science Foundation Young Investigator's Award (1992), and is a AAAI Fellow (1996). A member of the editorial board of the Artificial Intelligence Journal and an associate editor of the Journal of Artificial Intelligence Research, Pollack also served as Program Chair for the 15th International Joint Conference on Artificial Intelligence (1997). Her current research interests are interests are in planning and acting in dynamic environments, and in computational models of rationality. Pollack is spending the 1997-1998 academic year on sabbatical at CMU.

04/28/98 - Wesley Chu University of California, Los Angeles

Knowledge-Based Image Retrieval with Spatial and Temporal Constructs

A knowledge-based approach to retrieve medical images by feature and content with spatial and temporal constructs is developed. Selected objects of interest in a medical image (e.g. x-ray, MR image) are segmented, and contours are genrated from these objects. Features (e.g. shape, size, texture) and content (e.g. spatial relationships among objects) are extracted and stored in a feature database. Knowledge about image features can be expressed as a hierarchical structure called a Type Abstraction Hierarchy (TAH) which is user- and context- sensitive. Knowledge-based query processing that provides approximate (e.g similar to, near to, etc) matching of image features and content are developed. Further, a visual query language has been developed that accepts visual iconic input on the screen. User models are introduced to provide default parameter values for specifying query conditions. We have implemented a Knowledge-Based Medical Images Database System (KMeD) using the above mentioned technology at UCLA. The results from this research should be applicable to other multimedia information systems as well.

Wesley W. Chu received his B.S. and M.S. degrees from the University of Michigan, Ann Arbor, in 1960 and 1961, respectively, and his Ph.D. degree in electrical engineering from Stanford University in 1966. He did computer system design at General Electric and IBM, San Jose, California, and research in computer communications and distributed databases at At&T Bell Laboratories, Holmdel, New Jersey, prior to joining UCLA in 1969. He served as a chair of the UCLA Computer Science Department from 1989-1991, and is currently a professor in the department. His current research interests are in the areas of distributed processing, distributed databases, knowledge-based multimedia medical images system, and intelligent information systems. Dr. Chu is also a fellow of IEEE.

05/13/98 (10:00 a.m.) - Justin Boyan Carnegie Mellon University

Learning Evaluation Functions for Global Optimization

In complex sequential decision problems such as scheduling factory production, planning medical treatments, and playing backgammon, optimal decision policies are in general unknown, and it is often difficult, even for human domain experts, to manually encode good decision policies in software. The reinforcement-learning theory of ``value function approximation'' (VFA) offers an alternative: systems can learn effective decision policies autonomously, simply by simulating the task and keeping statistics on which decisions lead to good ultimate performance and which do not. This thesis advances the state of the art in VFA in two ways.

First, it presents three new VFA algorithms, which apply to three different restricted classes of sequential decision problems: Grow-Support for deterministic problems, ROUT for acyclic stochastic problems, and Least-Squares TD($\lambda$) for fixed-policy prediction problems. Each is designed to gain robustness and efficiency over current approaches by exploiting the restricted problem structure to which it applies.

Second, it introduces STAGE, a new search algorithm for general combinatorial optimization tasks. STAGE learns a problem-specific heuristic evaluation function as it searches. The heuristic is trained by supervised linear regression or Least-Squares TD($\lambda$) to predict, from features of states along the search trajectory, how well a fast local search method such as hillclimbing will perform starting from each state. Search proceeds by alternating between two stages: performing the fast search to gather new training data, and following the learned heuristic to reach a promising new start state.

STAGE has produced good results (in some cases, the best results known) on a variety of combinatorial optimization domains, including VLSI channel routing, Bayes net structure-finding, bin-packing, Boolean satisfiability, radiotherapy treatment planning, and geographic cartogram design. This thesis describes the results in detail, analyzes the reasons for and conditions of STAGE's success, and places STAGE in the context of four decades of research in local search and evaluation function learning. It provides strong evidence that reinforcement learning methods can be efficient and effective on large-scale decision problems.

Justin Boyan received his B.S. in mathematics from the University of Chicago in 1991 and, as a Churchill Scholar, his M.Phil. in computer speech and language processing from the University of Cambridge in 1992. At CMU, he belongs to the AUTON project, led by Andrew Moore. His thesis committee consists of Andrew Moore (co-chair), Scott Fahlman (co-chair), Tom Mitchell, and Tom Dietterich (Oregon State). A paper describing his thesis work has been named an Outstanding Paper for the AAAI-98 conference. Besides his research on machine learning, Justin enjoys writing commercial software such as BOYAN Communications, MVP Backgammon, and The Anonymizer. He is currently seeking research positions in industry.

05/19/98 - Andrew McCallum Just Research, Pittsburgh

Two Methods for Improving Text Classification when there is Sparse Training Data

Given the growing volume of online text available through the World Wide Web, Internet news feeds, electronic mail, and digital libraries, the problem of automatically assigning documents to pre-defined topic categories is of great practical significance. The problem poses an interesting challenge for Machine Learning because the number of features (words) is large, and the training data often covers this feature space only sparsely.

In this talk I will describe two methods for increasing the accuracy of statistical text classifiers when training data is sparse.

The first method assumes that the topic categories are organized hierarchically, and uses this hierarchy to improve the classifier's parameter estimates. We adopt a statistical technique called ``shrinkage'' that smoothes parameter estimates of a data-sparse child with its parent in order to obtain more robust estimates.

The second method augments the usual small set of labeled training documents with a large (frequently available and cheaply gathered) pool of unlabeled training documents. We treat these absent class labels as ``hidden variables'' and use Expectation Maximization to fill them in. Expectation Maximization improves the classifier by alternately using the current classifier to guess the hidden variables, and then using the current guesses to advance classifier training.

I will show how both these techniques can increase classification accuracy by 30% on real-world tasks. Both techniques can also be applied to non-textual problems.

Joint work with Kamal Nigam, Tom Mitchell, Sebastian Thrun, Roni Rosenfeld, Andrew Ng (MIT), and Larry Wasserman (CMU Statistics).

Andrew McCallum is a Research Scientist at Just Research (formerly JPRC) and Adjunct Faculty in the Center for Automated Learning and Discovery at CMU. He received his A.B. in Computer Science from Dartmouth College (summa cum laude) in 1989, and then did research in Machine Learning at the Biomedical Information Communication Center of Oregon Health Sciences University in 1990 and 1991. He earned the Ph.D. in Computer Science at the University of Rochester under Dana Ballard in 1995, with a thesis on "Reinforcement Learning with Selective Perception and Hidden State". In 1996 he was a Post-Doctoral Fellow with Sebastian Thrun and Tom Mitchell at CMU, and he is currently a member of Tom Mitchell's World Wide Knowledge Base project. Andrew's main research interests are in machine learning for text, statistical language modeling, and reinforcement learning.

05/26/98 - Donald Peterson Birmingham University, UK

Type Matching in the Graphical Representation of Relations

Relations are often expressed using graphical notations (bar charts, cartesian graphs, pie charts, and so on). I apply the set-theoretic logic of relations to characterise the types of individual relations and notations, and the principles of type-matching between the two. This serves two main purposes: to identify principles for matching a relation to a set of alternative notations in which it is expressible, and to provide a systematic way of characterising the expressive powers of graphical notations.

Donald Peterson BIO. - 1978, MA in Philosophy and Psychology (Edinburgh) - 1985, PhD in Philosophy (University College London) - 1986, MSc in Foundations of Advanced Information Technology (Imperial College London) - 1987-9, Researcher, European Computer-Industry Research Centre, Munich - 1990-present, Lecturer in Cognitive Science, University of Birmingham BOOKS. - 1990, *Wittgenstein's Early Philosophy*, Harvester. - 1993, C. Hookway and D. Peterson eds, *Philosophy asnd Cognitive Science*, Cambridge University Press - 1996, *Forms of Represetnation*, Intellect Press.

0?/??/98 - David Mumford Brown University

The Pattern-theoretic philosophy and applications to Vision

The term "Pattern Theory" was coined by Ulf Grenander to describe an approach to recognizing the structure implicit in all signals generated by the world, such as images and sound. The idea is that stochastic models must be found whose samples contain all the structure and the variability of the natural signals so that Bayesian methods can be effective even in the presence of large amounts of noise, missing data and distractions. Such models are not easy to construct. In this talk, I will review the general philosophy behind this approach, which applies in principle to virtually all aspects of AI, and will then give several recent examples of constructing and applying such stochastic models in vision.

David Mumford

09/23/97 - Rich Caruana Carnegie Mellon University

Multitask Learning - (Ph.D. Thesis Defense)

The world we live in requires us to learn many things. Perhaps it is the similarity of the many tasks we must learn that enables us to learn so much with so little experience. Yet the standard methodology in machine learning is to learn one thing at a time. Large problems are broken into small, reasonably independent sub problems that are learned separately and then recombined. This thesis argues that this kind of modularity can be counterproductive because it ignores a potentially rich source of information available in many real-world problems: the information contained in the training signals of other related tasks.

Multitask Learning is an approach to inductive transfer that improves learning for one task by using the information contained in the training signals of other related tasks. It does this by learning tasks in parallel while using a shared representation; what is learned for each task can help other tasks be learned better. This thesis demonstrates multitask learning with artificial neural nets on nearly a dozen problems. It explains how multitask learning in back prop nets works, presents methods for making it work better, and shows that there are many opportunities for applying multitask learning in real domains. In the thesis we also present an algorithm for multitask learning with case-based methods like k-nearest neighbor and kernel regression, and sketch an algorithm for multitask learning indecision trees. Multitask learning improves generalization performance, can be applied in many different kinds of domains, and can be used with different learning algorithms. In the talk we'll present results of applying multitask learning to problems in image understanding, DNA analysis, and medical decision making. We conjecture there will be many opportunities for its use on real-world problems.

Rich Caruanareceived an undergraduate degree in math and physics, and a master's degree in computer science, from Villanova University. Before coming to Carnegie Mellon, he worked for several years at Philips Research Labs on machine learning, genetic algorithms, and optimization. Rich joined CMU as a CS grad student specializing in machine learning in 1989. His advisors, Tom Mitchell and Herb Simon, are happy to see him finish. So is his wife, Diane. The members of his thesis committee are: Tom Mitchell (chair) Herb Simon (co-advisor) Dean Pomerleau (CS/Robotics, CMU) Tom Dietterich (CS, Oregon State). Rich currently works at Pittsburgh's newest research lab, JPRC (Justsystem Pittsburgh Research Center).

09/30/97 - Manuela M. Veloso Carnegie Mellon University.

Towards Continuous Planning, Execution, and Learning in Multi Agent Systems:
A Team of Robotic Soccer Agents

Problem solving in complex domains necessarily involves multiple agents, dynamic environments, and the need for learning from feedback and previous experience. Robotic soccer is an example of such complex tasks where agents need to collaborate in an adversarial environment to achieve specific objectives. In this talk, I describe the robotic agents and architecture with which we won the small-robot competition at RoboCup-97. The framework consists of an overall wireless communication system of small-size robots, an overhead vision camera for perception, and a centralized controller with role-based algorithms as the robot minds. We designed and built the robots (six), devised the appropriate vision algorithm, and developed and implemented strategic behaviors to allow for and developed and implemented strategic behaviors to allow for effective individual and collaborative problem solving. I will present the general approach that I am pursuing, towards continuous deliberative and reactive planning, execution, and learning in teams of multiple robots in dynamic, real-time, and adversarial environments. There search and development team for our robotic team entry at RoboCup-97 was led by me and included the graduate students Peter Stone and Kwun Han, and the research engineer Sorin Achim, Computer Science, Carnegie Mellon University.

Manuela M. VelosoFinmeccanica Associate Professor of Computer Science Department, Carnegie Mellon University.

10/07/97 - Andrew Moore Carnegie Mellon University

Accelerating Machine Learning Algorithms with Cached Sufficient Statistics
Joint work with Mary Soon Lee

In this talk we introduce new data structures and algorithms that can empirically give a 50-fold to 1000-fold computational speedup for machine learning methods such as Bayes net structure finders, rule learners and feature selectors operating on large datasets. Many machine learning algorithms need to do vast numbers of counting queries (e.g. "How many records have Color=Blue, Nationality=British, Smoker=False, Status=Married, Nose=Big?"). Similarly, many algorithms need to build and test many contingency tables. We provide methods for which, subject to certain assumptions, the costs of these kinds of operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table. We provide a very sparse data structure, the ADTree (all-dimensions tree), to minimize memory use. We provide analytical worst-case memory and construction-cost bounds for this structure for several models of data distribution. We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a)using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves. We show how the ADTree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADTree methods against traditional direct counting approaches. We also discuss the possible uses of ADTrees in other machine learning methods, and discuss the merits of ADTrees in comparison with alternative representations such as kd-trees, R-trees and frequent sets.

Andrew Moorereceived a Phd in Computer Science from the University of Cambridge in 1991 (thesis topic: Robot Learning). He worked as a post-doc with Chris Atkeson at MIT AI lab for three years before joining CMU as an assistant professor in Robotics/CS in 1993. His research interests include: Autonomous learning systems for manufacturing, efficient algorithms for machine learning and reinforcement learning, finite production scheduling, and machine learning applied to optimization.

10/14/97 - Jack Mostow Carnegie Mellon University

Project LISTEN

Project LISTEN is developing a novel tool to combat illiteracy: an automated reading tutor that displays a story on a computer screen, listens to a child read it aloud, and helps where needed. The tutor provides a combination of reading and listening, in which the child reads wherever possible, and the tutor helps wherever necessary.

Jack MostowDirector, Project LISTEN, Carnegie Mellon University. A.B. cum laude in Applied Mathematics (1974), Harvard University; Ph.D. in Computer Science (1981) and NSF Graduate Fellow, Carnegie Mellon University. Dr. Mostow's research interests in artificial intelligence have included speech, machine learning, and design. After research and faculty positions at Stanford, Information Sciences Institute, and Rutgers, he joined the Carnegie Mellon faculty in 1992 to launch Project LISTEN, which is getting computers to listen to children read aloud, and help them. Dr. Mostow is Co-chair of AAAI98, and has served as an editor of Machine Learning Journal and IEEE Transactions on Software Engineering.

10/21/97 - Katia Sycara Carnegie Mellon University

Next Generation of Agent Technology: Multiagent Systems for Planning, Execution, Coordination and Information Gathering

To date, agent technology primarily consists of solipsistic agents that are used for information gathering and filtering from the Web. The next generation will result in agents that interact as peers and coordinate to perform integrated planning, replanning, execution monitoring and information gathering. Such capabilities are non trivial, given scale, heterogeneity and dynamic nature of the Internet. As agents populate Cyberspace in their many guises and roles, they coordinate and interact in different ways, spanning self-interested, as well as collaborative interactions. Agent coordination should be supported by an agent's internal architecture and agent societal frameworks. In this talk, we report on our work in the RETSINA project (Reusable Environment for Task Structured Intelligent Network Agents). In RETSINA, each agent has a sophisticated achitecture that supports interleaving planning, execution, information gathering and coordination. Multiple agents adaptively form teams "on-demand" by discovring appropriate team mates through middle agents. The RETSINA framework has been utilized for the development of different applications (e.g. the Warren financial portfolio management system, the Thales satellite visibility system).

Katia Sycara is a Senior Research Scientist in the Robotics Institute in the School of Computer Science at Carnegie Mellon University. She is also the Director of the Enterprise Integration Laboratory. She is directing/conducting research and developing technology for integrating organizational decision making. She holds a B.S in Applied Mathematics from Brown University, M.S. in Electrical Engineering from the University of Wisconsin and a Ph.D in Computer Science from the Georgia Institute of Technology. Her research has contributed to the definition of case-based reasoning and the development of computational negotiation models as a means of resolving goal conflicts and inconsistencies in assumptions and viewpoints of heterogeneous agents in distributed problem solving. She has applied her research to concurrent engineering design, crisis action planning and manufacturing scheduling. She has published extensively in these areas. Currently, she is engaged in the development of intelligent agents that interact with their users, other agents and distributed information resources in order to assist their users in the planning and execution of various tasks. In the course of performing their tasks, the agents (1) retrieve, route and integrate information, (2) negotiate to resolve conflicts and (3) learn from their users and other agents. Sycara is Area Editor for AI and Management Science for the journal "Group Decision and Negotiation" and on the editorial board of "IEEE Expert", "AI in Engineering" and "Concurrent Engineering, Research and Applications". She is a member of AAAI, ACM, Cognitive Science Society, IEEE, and the Institute of Management Science (TIMS).

11/04/97 - Richard Korf University of California, Los Angeles

Finding Optimal Solutions to Rubik's Cube Using Pattern Databases

We have found the first optimal solutions to random instances of Rubik's Cube. The median optimal solution length appears to be 18 moves. The algorithm used is iterative-deepening-A* (IDA*), with a lower-bound heuristic function based on large memory-based lookup tables, or "pattern databases" (Culberson and Schaeffer 1996). These tables store the exact number of moves required to solve various sub goals of the problem, in this case subsets of the individual movable cubies. The overall performance of the program obeys a relation in which the product of the time and space used equals the size of the state space. Thus, the speed of the program increases linearly with the amount of memory available. In addition, we present the first analysis of A* and IDA* that allows us to accurately predict the running times of the algorithms using a real heuristic on a real problem. Contrary to conventional wisdom, this analysis suggests that the effect of heuristic functions is to reduce the effective depth of search, rather than the effective branching factor.

Richard Korf is a professor of computer science at the University of California, Los Angeles. He received his B.S. from M.I.T. in 1977, and his M.S. and Ph.D. from Carnegie Mellon University in 1980 and 1983, respectively, all in computer science. From 1983 to 1985, he served as Herbert M. Singer Assistant Professor of Computer Science at Columbia University. His research is in the areas of problem solving, planning, and heuristic search in artificial intelligence. He is the author of "Learning to Solve Problems by Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial boards of the Journal of Applied Intelligence, the Journal of Artificial Intelligence Research, and Artificial Intelligence, and on the Executive Council of AAAI. Dr. Korf is the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young Investigator Award, the first UCLA Computer Science Department Distinguished Teaching Award in 1989, and the UCLA Engineering School First Annual Student's Choice Award for Excellence in Teaching in 1996. He was elected a Fellow of the American Association for Artificial Intelligence in 1994.

11/11/97 - Raymond Mooney University of Texas at Austin

Relational Learning for Natural Language Parsing and Information Extraction

We are exploring the application of relational learning methods, such as inductive logic programming, to the construction of natural language processing systems. We have developed a system, CHILL, for learning a deterministic parser from a corpus of parsed sentences. CHILL can construct complete natural-language interfaces that translate database queries directly into executable logical form. It has been tested on English queries for a small database on U.S. geography, answering queries more accurately than a previous hand-built system. It has also recently been tested on Spanish, Turkish, and Japanese queries for the same database, and English queries about jobs posted to the newsgroup misc.jobs.offered and queries about restaurants in the California Bay Area. We are also developing a system for inducing pattern-match rules for extracting information from natural-language texts. This system has obtained promising initial results on extracting information from postings to misc.jobs.offered in order to assemble a database of available jobs. Our overall goal is to combine these techniques to automate the development of natural language systems that can answer queries about information available in a body of texts, such as newsgroup postings or web pages.

Abstract for Pitt Seminar at noon Mon Nov 10 (for completeness)

Theory Refinement for Student Modeling: An Application of Machine Learning to Intelligent Tutoring

Theory refinement systems developed in machine learning automatically modify a knowledge base to render it consistent with a set of classified training examples. We illustrate a novel application of these techniques to the problem of constructing a student model for an intelligent tutoring system (ITS). Our approach is implemented in an ITS authoring system called Assert which uses theory refinement to introduce errors into an initially correct knowledge base so that it models incorrect student behavior. The efficacy of the approach has been demonstrated by evaluating a tutor developed with Assert with 75 students tested on a classification task covering concepts from an introductory course on the C++ programming language. The system produced reasonably accurate models and students who received feedback based on these models performed significantly better on a post test than students who received simple reteaching.

Raymond Mooney

11/18/97 - Daphne Koller Stanford University

Probabilistic Reasoning: Scaling Up

Any application where an intelligent agent interacts with the real world must deal with the problem of uncertainty. Probability theory gives us a principled and coherent methodology for reasoning under uncertainty. In recent years, Bayesian networks have emerged as the dominant technology for making probabilistic reasoning a practical tool. Bayesian networks achieve effective knowledge representation and inference capabilities by utilizing a structural property that appears in many domains: the fact that, typically, each attribute is directly affected only by very few others. Bayesian networks have been used with great success in a wide variety of medium-scale applications. However, certain fundamental limitations on the expressive power of Bayesian networks renders them inadequate for handling large and complex domains. In the talk, I describe these limitations and discuss a new approach for scaling up probabilistic reasoning.

Our new approach is based on an analogy between probabilistic modeling languages and programming languages. When viewed in this light, Bayesian networks are analogous to logical circuits, clearly a far from optimal language for large scale applications. We show how various fundamental ideas from programming languages --- particularly function calls, encapsulation, and object-oriented programming --- can be imported into the framework of probabilistic modeling. The resulting language maintains the clean and coherent probabilistic semantics of Bayesian networks, while providing much greater expressivity. In particular, our framework allows us to deal with domains containing many objects; it also supports the representation of relations between objects, of hierarchically structured domains where objects can contain other objects, of classes of objects, and more. We also show that the additional structure encoded in these domain models can be exploited for inference. This property allows us to guarantee performance scalability even for very large domain models. Finally, I discuss the connection between our representation language and more traditional knowledge representation languages, and show that our framework bridges the long-standing gap between the two main knowledge representation formalisms: Bayesian networks and frame-based logical representation.

This talk covers joint work with Avi Pfeffer.

Daphne Koller received her PhD from Stanford University in 1994. After a two-year postdoc at Berkeley, she returned to Stanford, where she is now an Assistant Professor in the Computer Science Department. She has a broad range of interests spanning artificial intelligence, economics, and theoretical computer science. Her main research interest is in creating large-scale systems that reason and act under uncertainty. The theme underlying her work is the integration of ideas from decision theory and economics into these systems. This task raises the need for compact and natural knowledge representation schemes and for efficient inference and learning algorithms that utilize these schemes. Daphne Koller is the author of over 45 refereed publications, which have appeared in AI, theoretical computer science, and economics venues. She is on the editorial board of the Journal of Artificial Intelligence Research. She was awarded the Arthur L. Samuel Award for her PhD thesis work and the Sloan Foundation Faculty Fellowship in 1996.

11/25/97 - Roger Dannenberg Carnegie Mellon University

Recent Work in Music Understanding

Although music is commonly thought to be purely subjective, I will argue that music has many elements that can be "understood" in objective, measureable terms. Computers are an ideal way to study the objective aspects of music, and progress with computers challenges the notion of subjectivity altogether. This talk will focus on two specific recent investigations. In one, a computer learns, from labeled training examples, to differentiate improvisational styles. We built a system that can differentiate among 4 styles with better than 98% accuracy after listening for only 5 seconds. In another study, a computer synchronizes an accompaniment with a live vocalist using a set of new representations derived from probability theory. These studies were made jointly with Belinda Thom, David Watson, and Lorin Grubb.

Roger Dannenberg

12/09/97 - Wei-Min Shen University of Southern California

Return of The Jedi -- with Integrated Robots for Soccer Competition

Middle-sized robot soccer competition provides an excellent opportunity for AI, robotics, and vision research. In particular, the dog-sized robot players must perform real-time visual recognition, navigate in a dynamic field, track moving objects, collaborate with teammates, and hit a FIFA size-4 ball in the correct direction. All these tasks demand "integrated robots" that are autonomous (on-board sensing, thinking, and acting as living creatures), efficient (functioning under time and resource constraints), cooperative (collaborating with each other to accomplish tasks that are beyond individual's capabilities), and intelligent (reasoning and planing actions and perhaps learning from experience). Building such robots may require techniques that are different from those employed in separate research disciplines.

This talk describes our experience in building these soccer robots and highlights problems (and maybe some solutions) that are unique to integrated agents in general. These problems include skill composition, semantics for robot programming, and hierarchy of intelligent activities. Our robots share the same general architecture and basic hardware, but they have integrated abilities to play different roles (goal-keeper, defender or forward) and utilize different strategies in their behavior. Our philosophy in building these robots is to use the least possible sophistication to make them as robust as possible. In the 1997 RoboCup competition, these integrated robots played well and our "Dreamteam" won the world championship in the middle-sized robot league.

Wei-Min Shen is a senior research scientist at Information Sciences Institute and a research assistant professor of computer science at University of Southern California. He received his M.S. and Ph.D. from Carnegie Mellon University in 1986 and 1989, respectively, both in computer science. From 1989 to 1994, he served as a member of technical staff and then later a senior member of technical staff at the Microelectronic and Computer Technology Corporation. His research is in the areas of machine learning and discovery, intelligent information integration, data mining, and autonomous agents and robots. He is the author of "Autonomous Learning from the Environment" (Computer Science Press, 1994). He serves on the editorial boards of the Journal of Intelligent Data Analysis, the program committee of International Conference on Data Mining and Knowledge Discovery from Databases, and the executive boards of the International Robot Soccer Federation. Dr. Shen is the recipient of a 1996 AAAI Robotics Competition Second-Place Award, a 1997 World RoboCup Championship Award, and an Meritorious Service Award at USC/ISI in 1997. He is currently working the projects of Adapteam, DataCrystal, Dreamteam, and SIMS.

Webpage maintained by Stella X. Yu

Carnegie Mellon University Department of Computer Science

AI Seminar 97/98 Schedule

Speakers' Guide | Mailing List | RI Seminar | CNBC Seminar | VASC Seminar | CALD Seminar

Carnegie Mellon University
Department of Computer Science