Timezone: »

Probabilistic Inference with Algebraic Constraints: Theoretical Limits and Practical Approximations
Zhe Zeng · Paolo Morettin · Fanqi Yan · Antonio Vergari · Guy Van den Broeck

Thu Dec 10 07:30 AM -- 07:40 AM (PST) @ Orals & Spotlights: Unsupervised/Probabilistic

Weighted model integration (WMI) is a framework to perform advanced probabilistic inference on hybrid domains, i.e., on distributions over mixed continuous-discrete random variables and in presence of complex logical and arithmetic constraints. In this work, we advance the WMI framework on both the theoretical and algorithmic side. First, we exactly trace the boundaries of tractability for WMI inference by proving that to be amenable to exact and efficient inference a WMI problem has to posses a tree-shaped structure with logarithmic diameter. While this result deepens our theoretical understanding of WMI it hinders the practical applicability of exact WMI solvers to real-world problems. To overcome this, we propose the first approximate WMI solver that does not resort to sampling, but performs exact inference on one approximate models. Our solution performs message passing in a relaxed problem structure iteratively to recover certain lost dependencies and, as our experiments suggest, is competitive with other SOTA WMI solvers.

Author Information

Zhe Zeng (University of California, Los Angeles)
Paolo Morettin (University of Trento)
Fanqi Yan (University of California, Los Angeles)

B.S. - Zhejiang University M.S. - University of Chinese Academy of Sciences Visiting Student - University of California, Los Angeles Visiting Student - University Pierre and Marie Curie Exchange Student - University of New South Wales

Antonio Vergari (University of California, Los Angeles)
Guy Van den Broeck (UCLA)

I am an Assistant Professor and Samueli Fellow at UCLA, in the Computer Science Department, where I direct the Statistical and Relational Artificial Intelligence (StarAI) lab. My research interests are in Machine Learning (Statistical Relational Learning, Tractable Learning), Knowledge Representation and Reasoning (Graphical Models, Lifted Probabilistic Inference, Knowledge Compilation), Applications of Probabilistic Reasoning and Learning (Probabilistic Programming, Probabilistic Databases), and Artificial Intelligence in general.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors