This thesis investigates computational properties of decomposable probability models, which can be represented in terms of marginals over subsets of variables. We show that decomposable representations have significant locality structure that can be exploited to yield effective solutions to two important problems.

The first problem is filtering in dynamic Bayesian networks, which is typically intractable because the belief state collapses to a representation with no independence structure. We present a novel technique for filtering, called thin junction tree filtering (TJTF), that approximates the belief state by a decomposable model. By exploiting locality in the belief state representation, TJTF can automatically and efficiently identify the weakest dependencies in the belief state and prune them to control the complexity of filtering. We apply TJTF to simultaneous localization and mapping, a fundamental problem in mobile robotics, and obtain a solution that performs comparably with exact methods but with substantially better time and space complexity.

The second problem is distributed inference, where the nodes of a network collaborate to solve an inference problem. We present a robust architecture for distributed inference in which the nodes assemble themselves into a junction tree and solve the inference problem by message passing. In settings with unreliable communication and node failures, traditional message passing algorithms can fail because nodes cannot access the complete probability model. We present a new message passing algorithm that exploits the locality of decomposable representations to guarantee that each node can make inferences using whatever parts of the model are available. The algorithm is exact at convergence, and when parts of the model are inaccessible, its estimate is an informative approximation to the true posterior. The approach is demonstrated on the problem of automatic sensor calibration in wireless sensor networks.

Chapter 1: Introduction

Chapter 2: Decomposable models and junction trees

This chapter presents an introduction to decomposable models and junction trees, which graphically characterize the structure of decomposable models. We emphasize those properties of decomposable models that make them especially useful representations for dynamic and distributed probabilistic inference.

Chapter 3: Thin junction tree filters (TJTF)

In this chapter we examine the general problem of filtering in dynamic Bayesian networks. We discuss the Boyen-Koller algorithm for approximate filtering in DBNs, and we identify the need for adaptive approximation. We show how decomposable models can form the basis of approximate filtering techniques that automatically and adaptively choose good approximations based upon the model and observations.

Chapter 4: TJTF for simultaneous localization and mapping

This chapter describes the application of TJTF to the simultaneous localization and mapping (SLAM) problem. We cast the SLAM problem as a DBN filtering problem and show why adaptive approximation is necessary for good performance. We present a thin junction tree filter for SLAM with linear time and space complexity, and we also present a novel approximation technique, called adaptive flow passing, that can yield a constant time filter operation.

Chapter 5: A robust architecture for distributed inference

In this chapter we turn to the second problem, distributed inference. We present an architecture for distributed inference that can solve a wide variety of inference problems, including probabilistic inference, regression, and control problems. In this architecture, the nodes of the network assemble themselves into a junction tree and then use asynchronous message passing to solve the inference problem efficiently and exactly. We also present an efficient distributed algorithm for optimizing the choice of junction tree so that the communication and computational cost of inference can be minimized. The architecture is designed to be robust to the failure situations that arise in real-world settings, such as unreliable communication and node failures.

Chapter 6: Robust probabilistic inference in distributed systems

Current message passing algorithms for probabilistic inference can yield arbitrarily bad posterior estimates before they converge; this makes them unsuited for inference in distributed systems where communication is unreliable and nodes can fail. In this chapter, we present a new message passing algorithm that is based upon a decomposable representation of the model; not only does it converge to the correct posteriors, but it also yields an informative approximation at any point before convergence. In addition, the computational complexity of the algorithm depends only upon the model; it is independent of the network topology of the distributed system. The approach is demonstrated on the problem of automatic sensor calibration in wireless sensor networks.

Chapter 7: Conclusions

Chapters 3 and 4 are based upon the following papers:

Mark A. Paskin (2003). Thin Junction Tree Filters for Simultaneous Localization and Mapping. In G. Gottlob and T. Walsh eds., Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), pp. 1157–1164. San Francisco, CA: Morgan Kaufmann.

Mark A. Paskin (2002). Thin Junction Tree Filters for Simultaneous Localization and Mapping. Technical Report UCB/CSD-02-1198, University of California, Berkeley. Revised February 4, 2003.

Mark A. Paskin and Carlos E. Guestrin (2004). A robust architecture for distributed inference. Intel Research Technical Report IRB-TR-03-039.

Mark A. Paskin and Carlos E. Guestrin (2004). Robust Probabilistic Inference in Distributed Systems. To appear in Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI-04).