Efficient Symbolic Integration for Probabilistic Inference

Samuel Kolb, Martin Mladenov, Scott Sanner, Vaishak Belle, Kristian Kersting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Weighted model integration (WMI) extends weighted model counting (WMC) to the integration of functions over mixed discrete-continuous probability spaces. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programs. Yet, state-of-the-art tools for WMI are generally limited either by the range of amenable theories, or in terms of performance. To address both limitations, we propose the use of extended algebraic decision diagrams (XADDs) as a compilation language for WMI. Aside from tackling typical WMI problems, XADDs also enable partial WMI yielding parametrized solutions. To overcome the main roadblock of XADDs – the computational cost of integration – we formulate a novel and powerful exact symbolic dynamic programming (SDP) algorithm that seamlessly handles Boolean, integer-valued and real variables, and is able to effectively cache partial computations, unlike its predecessor. Our empirical results demonstrate that these contributions can lead to significant computational reduction over existing probabilistic inference algorithms.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Place of PublicationFreiburg, Germany
PublisherIJCAI Inc
Number of pages7
ISBN (Electronic)978-0-9992411-2-7
Publication statusPublished - 19 Jul 2018
Event27th International Joint Conference on Artificial Intelligence: IJCAI 2018 - Stockholmsmässan, Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018


Conference27th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2018
Internet address


Dive into the research topics of 'Efficient Symbolic Integration for Probabilistic Inference'. Together they form a unique fingerprint.

Cite this