AIC Seminar Series
Distributed Inference in Sensor Networks
Mark Paskin  Stanford University  
Date: Thursday, February 9th 2006 at 4:00pm
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 as you will need to sign in by
following instructions by the lobby phone at Building E (or call Wilma
Lenz at 650 859 4904, or Eunice Tseng at 650 859 2799). SRI is
located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the
parking lots off Fourth Street. Detailed directions to SRI, as well as maps,
are available from the Visiting AIC web page.
There are two entrances to SRI International located on Ravenswood Ave.
Please check the Building E entrance signage.
©2018 SRI International 333 Ravenswood Avenue, Menlo Park, CA 940253493
SRI International is an independent, nonprofit corporation. Privacy policy
