Appears in collection : French Spring School in Theoretical Computer Science / École de Printemps d'Informatique Théorique

This is a course on the “assembly language” of probabilistic programming languages: the nuts and bolts of low-level algorithms for efficiently implementing exact probabilistic inference in the discrete finite-support setting. Probabilistic inference is extremely computationally hard: inference is #P-hard even for very restricted probabilistic programming languages. Due to this hardness, inference walks a fine line: one must carefully carve out classes of tractable problem instances and design algorithms to exploit whatever tractable footholds one can find. First, we will study classical approaches to exact inference: variable elimination and the join-tree algorithm. Next, we will study knowledge compilation, including binary decision diagrams, sentential decision diagrams, and top-down and bottom-up compilation. Third, we will study pragmatics, and discuss how we should benchmark, evaluate, and design probabilistic reasoning algorithms to support users.