Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)
Graphical Models, Distributed Fusion, and Sensor Networks
Alan Willsky
May 15, 2006, 4:15PM
TCSeq 200
http://graphics.stanford.edu/ba-colloquium/
Abstract
In this talk we provide a picture of one groups journey through a set
of related research topics and lines of inquiry. The point of
departure for this talk is our groups work on multiresolution models
defined on trees. We provide a brief overview of the nature of the
results from that research, and then turn to work that weve pursued
fueled by the limitations of models defined on trees rather than on
more general graphs. Markov models defined on graphs with loops is a
very rich and active field, finding applications in a surprisingly
wide array of disciplines, and challenging theoreticians and algorithm
developers to devise methods that are both computationally tractable
and high-performance. We provide a picture of some of our
contributions in this area, all of which build (in one way or another)
on our work on models defined on trees but that also make explicit
contact with the rich class of so-called "message-passing"
algorithms (such as the celebrated Belief Propagation" (BP)
algorithm) for graphical models. Among the contributions we will
mention are recursive cavity modeling (RCM) algorithms that blend
tree-based estimation with ideas in information geometry to lead to
algorithms that allow scalable solution of very large estimation
problems; the concept of "walk-sums" for graphical models and
the new theoretical results they admit for belief propagation; and
Nonparametric Belief Propagation, an approach that involves a
nontrivial extension of the idea of particle filtering to
message-passing algorithms.
We also describe our growing investigation of distributed fusion
algorithms for sensor networks, in which there is a natural graph
associated with network connectivity, as well as possibly two other
graphs: one, relating the variables that are sensed and those that are
to be estimated and a second relating the sources of information to
the desired "sinks" (i.e., to nodes with responsibility for
certain actions). We are still early in this investigation, but we
describe several results including some on what we call
"message-censoring" in which a sensor decides not to send a BP
message, in which empirical studies motivated a theoretical
investigation into the propagation of messaging errors in BP, a study
that has also produced the as-yet tightest results for BP convergence.
We also describe our results on efficient communication of messages
and the tradeoff between communication load and performance and on
sensor resource management in which we take into account not just the
power cost of taking a measurement and communicating a message but
also of dynamically "handing off" responsibility for estimation
from one node to another. Further, in some initial work on the
rapprochement of message-passing algorithms and decentralized
detection, we describe the fact that an important component of sensor
network activity is "self-organization" and describe, for a
simple scenario, how the solution to a team-decision problem can (a)
be solved via a message-passing algorithm; and (b) leads to what can
be thought of as a network protocol coupling the physical and
application layers.
About the Speaker
Dr. Willsky has held visiting positions at Imperial College, London,
L'Universite de Paris-Sud, and the Institut de Recherche en
Informatique et Systemes Aleatoires (IRISA) in Rennes,
France. Dr. Willsky has given a number of plenary and keynote lectures
at major scientific meetings. He is the author of the research
monograph Digital Signal Processing and Control and Estimation Theory
and is co-author of the undergraduate text Signals and Systems. He
has published more than 180 journal publications and 300 conference
papers. In 1975 he received the Donald P. Eckman Award from the
American Automatic Control Council. He was awarded the 1979 Alfred
Noble Prize by the ASCE and the 1980 Browder J. Thompson Memorial
Prize Award by the IEEE for a paper excerpted from his monograph, and
he recently received the 2004 Donald G. Fink Award from the IEEE.
Dr. Willsky and his students, colleagues and postdoctoral associates
have received a variety of Best Paper Awards at various conferences,
most recently including the 2001 IEEE Conference on Computer Vision
and Pattern Recognition, the 2002 Symposium on Uncertainty in
Artificial Intelligence, the 2003 Spring Meeting of the American
Geophysical Union, the 2004 International Conference on Information
Processing in Sensor Networks, the 2004 Neural Information Processing
Symposium, and Fusion 2005. In addition, in October 2005, Dr. Willsky
was presented with a Doctorat Honoris Causa from Universite de Rennes
in 2005 in connection with the 30th anniversary of the establishment
of IRISA.
Dr. Willsky is the leader of MIT's Stochastic Systems Group
(http://ssg.mit.edu). Prof. Willsky's research has focused on both
theoretical and applied problems in statistical signal and image
processing. His early work on methods for failure detection in
dynamic systems is still widely cited and used in practice, and his
more recent research on multiresolution methods for large-scale data
fusion and assimilation has found application in fields including
target tracking, object recognition, fusion of nontraditional data
sources, oil exploration, oceanographic remote sensing, and
groundwater hydrology. Dr. Willsky's present research interests are
in problems involving multidimensional and multiresolution estimation
and imaging, inference algorithms for graphical and relational models,
statistical image and signal processing, data fusion and estimation
for complex systems, image reconstruction, and computer vision.
Contact: bac-coordinators@cs.stanford.edu
Back to the Colloquium Page