AIC Seminar Series
Distributed Inference in Sensor Networks
Mark Paskin  Stanford University  
Date: 20060209 at 16:00
Location: EJ228 (Directions)

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
problemsincluding probabilistic inference, regression, and control
problemscan 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
97node 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 sumproduct
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 sumproduct
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.
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 940253493
SRI International is an independent, nonprofit corporation. Privacy policy
