Graphical Models, Distributed Fusion, and Sensor Networks

(Beginning of 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 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.
(Conclusion of abstract) 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.