AitF: Collaborative Research: Algorithms for Probabilistic Inference in the Real World

Probabilistic models are the method of choice in large scale machine learning systems for describing complex dependencies in data and performing prediction tasks across diverse fields like computer vision, natural language processing, and computational biology. A fundamental inference problem underlying many of these applications of graphical models is to find the most likely configuration of the probability distribution, called the maximum a posteriori (MAP) assignment. MAP inference problems for graphical models often reduce to well-studied combinatorial optimization problem that are known theoretically to be NP-hard in the worst-case. However, practitioners in areas such as computer vision and machine learning have made significant strides in designing heuristic algorithms to perform real-world inference accurately and efficiently. Reconciling this large gap between theory and practice in probabilistic inference, and designing efficient MAP inference algorithms with provable guarantees is a major challenge in machine learning. This proposal focuses on bridging the gap between theory and practice for probabilistic inference problems in large-scale machine learning systems by: -- Understanding why many real-world instances of MAP inference problems on graphical models are tractable. The goal is to identify structural properties and methods of analysis that differentiate real-world instances from worst-case instances of these NP-hard combinatorial optimization problems, and then design efficient algorithms with provable guarantees that would apply to most instances that come from the real-world. -- Understanding why heuristics like linear programming and other convex relaxations are so successful on real-world instances. The broad goal is to develop a theory that allows us to understand when these relaxations become integral or partially-integral on many real-world instances. -- Developing new scalable algorithms that take advantage of properties exhibited