Graphical Models, Distributed Fusion, and Sensor Networks
Alan Willsky
SSG, LIDS, MIT
Graphical Models, Distributed Fusion, and Sensor Networks
<> 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 so-called “embedded tree” algorithms for the
efficient and exact solution of a nontrivial class of Gaussian MRFs;
“tree-reparameterization” algorithms which lead to a number of
theoretical results on graphical models; a new recursive cavity
modeling (RCM) algorithm that blends 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 an approach we call
“Nonparametric Belief Propagation” 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.
Problems with this site should be emailed to jonesb@mit.edu