Stanford talk: Graphical Models, Distributed Fusion, and Sensor Networks

Alan Willsky
May 15, 2006, 4:15PM

Abstract
In this talk we provide a picture of one groupÞ²s journey through a set of related research topics and lines of inquiry. The point of departure for this talk is our groupÞ²s 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 weÞ²ve 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.