AIC Seminar Series

Many inference problems that arise in sensor networks require the computation of a global conclusion that is consistent with local information known to each node. A large class of these problems--including probabilistic inference, regression, and control problems--can be solved by message passing on a data structure called a "junction tree". In this talk, I will describe a distributed architecture for solving these problems that is robust to unreliable communication and node failures. In this architecture, the nodes of the sensor network assemble themselves into a junction tree and exchange messages between neighbors to solve the inference problem efficiently and exactly. A key part of the architecture is a distributed algorithm for optimizing the choice of junction tree to minimize the communication and computation required by inference. I will present experimental results from a prototype implementation on a 97-node Mica2 mote sensor network, as well as simulation results for three applications: distributed sensor calibration, optimal control, and sensor field modeling. These experiments demonstrate that the distributed architecture can solve many important inference problems exactly, efficiently, and robustly. If time permits, I will delve a little deeper into the challenges of solving probabilistic inference problems robustly in distributed systems. In our distributed inference architecture, the natural algorithm to solve probabilistic inference problems is the sum-product algorithm. Unfortunately, this algorithm can yield very poor estimates in settings where communication is lossy and nodes can fail. This is because the nodes' beliefs before the algorithm converges can be arbitrarily different from the correct posteriors. I will present a new message passing algorithm for probabilistic inference which provides several crucial guarantees that the standard sum-product algorithm does not. Not only does it converge to the correct posteriors, but it is also guaranteed to yield a principled approximation at any point before convergence. In addition, the computational complexity of the message passing updates depends only upon the model, and is independent of the network topology of the distributed system. (Joint work with Carlos Guestrin and Jim McFadden)

Mark Paskin is a Postdoctoral Researcher in the Artificial Intelligence Laboratory at Stanford University. His research interests focus on machine learning--particularly probabilistic reasoning--and its applications in robotics, sensor networks, computer vision, and other areas. He obtained his Ph.D. in 2004 from the University of California, Berkeley, under the supervision of Stuart Russell.

Please arrive at least 10 minutes early in order to sign in and be escorted to the conference room. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the visitors lot in front of Building E, and should follow the instructions by the lobby phone to be escorted to the meeting room. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page.

©2013 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy