Probabilistic graphical models such as Markov random fields, Bayesian networks, and decision networks (a.k.a. influence diagrams) provide one of the most powerful frameworks for representing and exploiting dependence structures of high dimensional variables. The last two decades have witnessed significant improvements in basic inference tasks on graphical models, including combinatorial optimization and marginalization (e.g., computing data likelihoods or probabilities of evidence), particularly based on variational inference algorithms. However, modern machine learning applications increasingly require more challenging inference tasks, such as robust combinatorial optimization with missing information or latent variables, stochastic programming and decision making in single or muti-agent systems. These problems are notoriously challenging: they require both optimizing over large numbers of decision variables and averaging over random variables, in either simultaneous or sequential environments.  

In this talk, I present a unified variational representation for all of these problems, providing a broad and powerful framework for deriving new classes of efficient exact or approximate algorithms. In particular, I describe a class of  "message-passing" style algorithms that are simple, fast and nicely amenable to parallel or distributed computation. We show that our algorithms significantly outperform earlier algorithms both in terms of empirical results and theoretical guarantees.   

Qiang Liu is a Ph.D. candidate in the Bren School of Information and Computer Science at UC Irvine. His research focuses on machine learning and probabilistic graphical models, with applications to areas such as crowdsourcing, computational biology and sensor networks. He received a Microsoft Research Fellowship in 2011, and a notable paper award at the 2011 AI and Statistics conference.