UC Irvine

Probabilistic graphical models such as Markov random fields, Bayesian networks and decision networks (a.k.a. influence diagrams) provide powerful frameworks for representing and exploiting dependence structures in complex systems. However, making predictions or decisions using graphical models involve challenging computational problems of optimization and/or estimation in high dimensional spaces. These include combinatorial optimization tasks such as maximum a posteriori (MAP), which finds the most likely configuration, or marginalization tasks that calculate the normalization constants or marginal probabilities. Even more challenging tasks require a hybrid of both: marginal MAP tasks find the optimal MAP prediction while marginalizing over missing information or latent variables, while decision-making problems search for optimal policies over decisions in single- or multi-agent systems, in order to maximize expected utility in uncertain environments.

All these problems are generally NP-hard, creating a need for efficient approximations. The last two decades have witnessed significant progress on traditional optimization and marginalization problems, especially via the development of variational message passing algorithms. However, there has been less progress on the more challenging marginal MAP and decision-making problems.

This thesis presents a unified variational representation for all these problems. Based on our framework, we derive a class of efficient algorithms that combines the advantages of several existing algorithms, resulting in improved performance on traditional marginalization and optimization tasks. More importantly, our framework allows us to easily extend most or all existing variational algorithms to hybrid inference and decision-making tasks, and significantly improves our ability to solve these difficult problems. In particular, we propose a spectrum of efficient belief propagation style algorithms with "message passing" forms, which are simple, fast and amenable to parallel or distributed computation. We also propose a set of convergent algorithms based on proximal point methods, which have the nice form of transforming the hybrid inference problem into a sequence of standard marginalization problems. We show that our algorithms significantly outperform existing approaches in terms of both empirical performance and theoretical properties.