Colloquium

Probability distributions defined by graphs arise in a variety of fields, including statistical signal and image processing, sensor networks, machine learning, and comunication theory. Graphical models provide a principled framework in which to combine local constraints so as to construct a global model. Important practical problems in applications of graphical models include computing marginal distributions or modes, and the log partition function. Although these problems can be solved efficiently in tree-structured models, these same tasks are intractable for general large-scale graphs with cycles.

In recent years, local message-passing algorithms (i.e., belief propagation, max-product) have been widely used to compute approximate solutions in graphs with cycles. We describe a class of reweighted message-passing algorithms, and demonstrate how they can be understood as methods for solving graph-structured optimization problems. These modified algorithms have advantages over standard methods, including unique fixed points and guaranteed upper bounds (reweighted belief propagation), and performance guarantees (reweighted mix-product). We discuss applications of graphical models and message-passing to statistical image processing and error-control coding, as well as directions for future research.

There is precisely one complete language processing system to date: the human brain. Though there is debate on how much built-in bias human learners might have, we definitely acquire language in a primarily unsupervised fashion. On the other hand, computational approaches to language processing are almost exclusively supervised, relying on hand-labeled corpora for training. This reliance is largely due to repeated failures of unsupervised approaches. In particular, the problem of learning syntax (grammar) from completely unannotated text has received a great deal of attention for well over a decade, with little in the way of positive results.

We argue that previous methods for this task have generally failed because of the representations they used. Overly complex models are easily distracted by non-syntactic correlations (such as topical associations), while overly simple models aren't rich enough to capture important first-order properties of language (such as directionality, adjanency, and valence). We describe several syntactic representations which are designed to capture the basic character of natural language syntax as directly as possible.

With these representations, high-quality parses can be learned from surprisingly little text, with no labeled examples and no language-specific biases. Our results are the first to show above-baseline performance in unsupervised parsing, and far exceed the baseline (in multiple languages).These specific grammar learning methods are useful since parsed corpora exist for only a small number of languages. More generally, most high-level NLP tasks, such as machine translation and question-answering, lack richly annotated corpora, making unsupervised methods extremely appealing even for common languages like English.

The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASes to have conflicting policies that can lead to routing instability.

This talk proposes a set of guidelines for an AS to follow in setting its routing policies, without requiring coordination with other ASes. Our approach exploits the Internet's hierarchical structure and the commercial relationships between ASes to impose a partial order on the set of routes to each destination. The guidelines conform to conventional traffic-engineering practices of ISPs, and provide each AS with significant flexibility in selecting its local policies. Furthermore, the guidelines ensure route convergence even under changes in the topology and routing policies. Drawing on a formal model of BGP, we prove that following our proposed policy guidelines guarantees route convergence. We also describe how our methodology can be applied to new types of relationships between ASes, how to verify the hierarchical AS relationships, and how to realize our policy guidelines. Our approach has significant practical value since it preserves the ability of each AS to apply complex local policies without divulging its BGP configurations to others. The end of the talk briefly summarizes follow-up studies that have built on this work.

The work described in this talk draws on the papers http://www.research.att.com/~jrex/papers/ton01-stable.pdf http://www.research.att.com/~jrex/papers/infocom01.ps

In recent years, researchers have invested significant effort in multi-robot systems. Robot soccer, as a pioneering multi-robot task, has offered a challenging research testbed. In robot soccer, a team of robots faces an uncertain and dynamic environment including an opponent team.

We have researched in robot soccer, developing single-robot and multi-robot perception, cognition, and action algorithms. To form an effective team, individual robots need to be skilled. We have developed novel object-recognition, localization, and behavior-based algorithms to provide these skills. To achieve a reliable team of robots, we have contributed team coordination strategies, methods for representing and adapting team plans in response to a dynamic world, and multiagent learning. In this talk, I will present our contributions to this complex adversarial multi-robot task, focused in particular on our teams of small wheeled robots and of four-legged Sony AIBO robots.

Based on our research results, I will introduce an overarching hypothesis on a set of principles for effective robot autonomy in the physical world. I will conclude by presenting how my research goals in fit into the broad fields of artificial intelligence and robotics.

We study the problem of finding a shortest path between two vertices in a directed graph. This is an important problem with many applications, including that of computing driving directions, our motivating one. We allow preprocessing the graph using a linear (in the graph size) amount of extra space to store additional information. This information helps us to answer shortest paths queries quickly. Our main contribution is a new distance lower-bounding technique hat, combined with heuristic search (aka A* search), gives surprisingly good results for important classes of graphs. The this technique is based on landmarks and triangle inequality. We also study several bidirectional variants of heuristic search,including new variants. Computational experiments show that on some graph classes,in particular road networks, these algorithms work very well. This talk is aimed at a general Computer Science audience. Joint work with Chris Harrelson

In the fall of 2001, a series of biowarfare attacks were sent through the U.S. mail as letters containing a powder form of the anthrax bacterium, Bacillus Anthracis. Subsequent to these attacks, our group was asked to conduct a rapid sequencing project to decode the genome of the strain used in the attacks. We compared this sequence to a second, reference anthrax genome, which we were sequencing simultaneously. I will discuss the difficult challenges posed by trying to compare two imcomplete genome sequences, for which the sequencing error rate is relatively high, and for which the assembly of the genome data may contain mistakes. Using a combination of computational and statistical methods, our group identified 60 novel, high-quality genetic markers distinguishing the attack strain from other strains (1). We also concluded that, in order to facilitate future comparisons at this level of detail, genome sequencing centers need to release not only genome sequences but also detailed information about the accuracy of every nucleotide in those sequences, and about the genome assembly itself.

I will discus the difficult challenges posed by trying to compare two imcomplete genome sequences, for which the sequencing error rate is relatively high,and for which the assembly of the genome data may contain mistakes. Using a combination of computational and statistical methods, our group identified 60 novel, high-quality genetic markers distinguishing the attack strain from other strains (1). We also concluded that, in order to facilitate future comparisons at this level of detail, genome sequencing centers need to release not only genome sequences but also detailed information about the accuracy of every nucleotide in those sequences, and about the genome assembly itself.

If time permits, I will discuss a new project to sample and sequence the genomes of 10,000 or more isolates of the human influenze A virus, in order to anticipate and help prevent future flu pandemics.

The Human Computer Interaction community recognized long ago that it should play a role in the design, implementation and evaluation of technology for users with cognitive disabilities. While there are some significant challenges to working with users who have cognitive disabilities, there has never been a more opportune time to embrace those challenges. Advances in computer technology, including the prevalence of low-cost handheld multimedia devices, combined with the increasing likelihood that individuals with acquired cognitive disabilities where computer-literate prior to acquiring the disability, suggest new opportunites for assistive technology to support these individuals in their daily activities.

The Aphasia Project is an exciting new multi-disciplinary research project operating out of the University of British Columbia and Princeton University. Our goal is to investigate how technology can be designed to support individuals with aphasia in their daily life. Aphasia is a cognitive disorder, usually acquired as a result of a stroke, brain tumor, or other brain injury, that result in an impairment of langage, affecting the production and/or comprehension of speech and/or written language. Most individuals with aphasia retain their comprehension of visual images, suggesting that multimedia technology may plan a role in an assistive solution.

This talk will explore a number of research challenges in the design of assistive technology for individuals with aphasia. Key challenges include achieving effective design and evaluation for a user population with extremely high degree of variance, and creating appropriate multi- disciplinary teams to carry out the research. We will describe our initial approaches to dealing with these challenges and some early research findings.

I will present an overview of a project to capture and use digital models of museum artifacts for the purposes of education and public information. I will begin by describing the original design of a 3D scanning system now in use in Cairoâs Egyptian Museum. The system captures both the geometry and surface color and detail of museum artifacts. I will report on the experience using the system and present samples of how the processed 3D data will be used on a web site designed to communicate Egyptian culture. One of the greatest problems that we have faced in the project is the need to have edits on complex 3D objects specified by non-technical end-users such as historians. I will present a new approach we are exploring in which we convert the problem of editing a 3D object of arbitrary size and surface properties to a problem of editing a 2D image. We allow the user to specify small edits in both geometry and surface properties from any view and at any resolution they find convenient, regardless of the interactive rendering capability of their computer. We believe a purely image-based approach to 3D editing offers the potential to make graphics tools available to a wider population of end-users.

Since the 1950s, computers have become ever more widely used to perform mathematical proofs. Mathematicians have used them for proofs (such as of the famous four-colour theorem) that are too extensive to conduct by hand. Automated proving is a fundamental technique of "artificial intelligence," and also central to debates about the very possibility of such intelligence. Computer scientists use automated theorem provers to verify the design of software critical to human safety or to national security, and "model checking" programs are now an important part of computer hardware design.

After reviewing briefly the history of these developments, the talk will explain why they are of interest to the sociology of scientific knowledge: they suggest the emergence of a set of "cultures of proving" different from those of ordinary mathematics. Clashes between cultures of automated proving and those of ordinary mathematics, and the first litigation centering on the meaning of mathematical "proof," will be examined. The talk will also discuss areas of tension within automated proving and outline a case in which the priorities of national security can be seen in the very construction of an automated theorem prover.

A couple of years ago a new paradigm, based on the quantum adiabatic theorem, was introduced for the design of quantum algorithms for solving optimization problems. In this talk, I will present recent results showing that for certain objective functions, the quantum adiabatic algorithm tunnels through local optima, thus performing exponentially faster than classical local search algorithms. I will also discuss limits on the power of this new paradigm, as well as its relationship to simulated annealing, a classical heuristic for algorithm design.