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.