RI: Medium: Approximation Algorithms for Probabilistic Graphical Models with Constraints

University Of California-Irvine, Irvine CA

Investigators

Abstract

The goal of this project is to create the next generation of approximate inference techniques and algorithms for probabilistic graphical models. Probabilistic graphical models are employed throughout science and engineering to solve difficult problems, including automated reasoning and decision making, computational biology and genetics, computer vision, data mining, and social network analysis. However, these real-world problems are now of such considerable size that most existing techniques are uneven in their performance in that they typically work well on some problems and not others, and often require sets of choices and customizations that must be made with little guidance or automation. This project brings together separate but complementary streams of research to develop new algorithms to manage models containing mixtures of probabilistic and deterministic relations and mixtures of graph-based and context-sensitive relationships. This project aims to advance the state of the art of probabilistic reasoning in the presence of deterministic constraints by developing new approximate inference techniques for graphical models, for instance, by exploiting the rich structure of graphical models that is largely neglected by most sampling techniques. This project aims to create improved frameworks for probabilistic graphical models by improving both sampling and message-passing algorithms for approximate inference and developing hybrid approaches that exploit the advantages of each. The frameworks will be used to provide automated guidance for selecting parameters to optimize the inherent tradeoffs between complexity and accuracy as well as provide meaningful bounds on results and accuracy. This project will use the fruits of its research to improve education, both at the undergraduate and graduate level, for instance by developing a new undergraduate course in graphical models, and by posting course materials online. In addition, the project will post open source code on the web.