Symposium & PhD Defense Guy Van den Broeck

Speaker:
Guy Van den Broeck, Computer Science Department, KU Leuven, Belgium

Abstract:
Statistical relational models combine aspects of first-order logic and probabilistic graphical models, enabling them to model complex logical and probabilistic interactions between large numbers of objects. This level of expressivity comes at the cost of increased complexity of inference, motivating a new line of research in lifted probabilistic inference. By exploiting symmetries of the relational structure in the model, and reasoning about groups of objects as a whole, lifted algorithms dramatically improve the run time of inference and learning.

The thesis has five main contributions. First, we propose a new method for logical inference, called first-order knowledge compilation. We show that by compiling relational models into a new circuit language, hard inference problems become tractable to solve. Furthermore, we present an algorithm that compiles relational models into our circuit language. Second, we show how to use first-order knowledge compilation for statistical relational models, leading to a new state-of-the-art lifted probabilistic inference algorithm. Third, we develop a formal framework for exact lifted inference, including a definition in terms of its complexity w.r.t. the number of objects in the world. From this follows a first completeness result, showing that the two-variable class of statistical relational models always supports lifted inference. Fourth, we present an algorithm for approximate lifted inference by performing exact lifted inference in a relaxed, approximate model. Statistical relational models are receiving a lot of attention today because of their expressive power for learning. Fifth, we propose to harness the full power of relational representations for that task, by using lifted parameter learning. The techniques presented in this thesis are evaluated empirically on statistical relational models of thousands of interacting objects and millions of random variables.

Speaker:
Stuart Russell, Computer Science Division, University of California, Berkeley, USA and LIP6, University Pierre et Marie Curie, France

Abstract:
The first part of the talk will briefly summarize the historical development and current status of formal languages for open-universe probability models, which allow for uncertain reasoning about unknown objects and events. The second part will focus on an application: global seismic monitoring for the Comprehensive Nuclear-Test-Ban Treaty.

The speaker is supported by, and this talk is given under the auspices of, the Blaise Pascal International Research Chair, funded by l'Etat et la Region d'Ile de France and administered by the Fondation de l'Ecole Normale Superieure.

Speaker:
Adnan Darwiche, Computer Science Department, University of California, Los Angeles, USA

Abstract:
Decision diagrams have played an influential role in computer science and AI over the past few decades, with OBDDs (Ordered Binary Decision Diagrams) as perhaps the most practical and influential example. The practical influence of OBDDs is typically attributed to their canonicity, their efficient support of Boolean combination operations, and the availability of effective heuristics for finding good variable orders (which characterize OBDDs and their size). Over the past few decades, significant efforts have been exerted to generalize OBDDs, with the goal of defining more succinct representations while retaining the attractive properties of OBDDs. On the theoretical side, these efforts have yielded a rich set of decision diagram generalizations. Practially, however, OBDDs remain as the single most used decision diagram in applications. In this talk, I will discuss a recent line of research for generalizing OBDDs based on a new type of Boolean-function decompositions (which generalize the Shannon decomposition underlying OBDDs).

I will discuss in particular the class of Sentential Decision Diagrams (SDDs), which branch on arbitrary sentences instead of variables, and which are characterized by trees instead of total variable orders. SDDs retain the main attractive properties of OBDDs and include OBDDs as a special case. I will discuss recent theoretical and empirical results, and a soon-to-be-released open source package for supporting SDDs, which suggest a potential breakthrough in the quest for producing more practical generalizations of OBDDs.