Scalable Inference and Learning for High-Level Probabilistic Models

March 9, 2015
3:00 pm - 4:15 pm
Halligan 102
Host: Soha Hassoun


Probabilistic graphical models are pervasive in AI and machine learning. A recent push, however, is towards more high-level representations of uncertainty, such as probabilistic programs, probabilistic databases, and statistical relational models. This move is akin to going from hardware circuits to a full-fledged programming language, and poses key challenges for inference and learning. For instance, we encounter a fundamental limitation of classical learning algorithms: they make strong independence assumptions about the entities in the data (e.g., images, web pages, patients, etc.). These assumptions fail to hold in a global view of the data, where all entities are related. We also encounter a limitation of existing reasoning algorithms, which fail to scale to large, densely connected graphical models, consisting of millions of interrelated entities.

In this talk, I present my research on efficient algorithms for high-level probabilistic models, called lifted inference and learning algorithms. I begin by introducing the key principles behind exact lifted inference, namely to exploit symmetry and exchangeability in the model. Next, I discuss the strengths and limitations of lifting. Building on results from database theory and counting complexity, I identify classes of tractable models, and classes where high-level reasoning is fundamentally hard. I conclude by showing the practical embodiment of these ideas, in the form of approximate inference and learning algorithms that scale up to big data and big models.


Van den Broeck graduated summa cum laude with a Ph.D. in Computer Science from KU Leuven, Belgium, in 2013. He was a postdoctoral researcher at UCLA and KU Leuven, supported by FWO. His research interests are broadly in machine learning, artificial intelligence, knowledge representation and reasoning, and statistical relational learning. His work was awarded the ECCAI AI Dissertation Award 2014, Scientific Prize IBM Belgium for Informatics 2014, and Alcatel-Lucent Innovation Award 2009. He is the recipient of the best student paper award at ILP 2011 and a best paper honorable mention at AAAI 2014.