Probabilistic graphical models are a powerful modeling framework with numerous applications in machine learning. Unfortunately, from the computational point of view, probabilistic reasoning is generally intractable, as it involves the computation of high-dimensional integrals. In this talk, I will introduce a new computational paradigm where probabilistic reasoning is achieved by solving a small number of instances of a combinatorial optimization problem (MAP inference) closely related to the maximum-likelihood decoding problem. Treating probabilistic inference as an optimization problem is a clear departure from methods based on Monte Carlo sampling or variational inference. The new approach also provides formal probabilistic guarantees on the accuracy of the results. Based on the theory of low-density parity check codes, I will introduce several approaches to solve, approximate, and relax the underlying combinatorial optimization problem, leading to a new family of inference algorithms that outperform traditional variational and sampling methods in a range of domains, in particular those involving combinations of probabilistic and deterministic constraints. This ability to handle deterministic constraints creates new opportunities for including prior knowledge into probabilistic models. As an example, I will discuss a scientific data analysis application in the emerging area of Computational Sustainability where we greatly improved the quality of the results by incorporating prior background knowledge of the physics of the system into the model.
Stefano Ermon is a PhD candidate in Computer Science at Cornell University, working at the Institute for Computational Sustainability (ICS). He has (co-)authored nearly 20 publications, including two Best Student Paper Awards and one Runner-Up Prize. His research spans combinatorial reasoning, probabilistic inference, machine learning, and optimization. Most recently, his focus is on applying these artificial intelligence techniques to problems in Computational Sustainability, ranging from natural resource management to sustainable transportation systems and discovery of new fuel-cell materials.