Efficient Search-Based Weighted Model Integration

Zhe Zeng, Guy Van den Broeck
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:175-185, 2020.

Abstract

Weighted model integration (WMI) extends Weighted model counting (WMC) to the integration of functions over mixed discrete-continuous domains. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programming. Yet, state-of-the-art tools for WMI are limited in terms of performance and ignore the independence structure that is crucial to improving efficiency. To address this limitation, we propose an efficient model integration algorithm for theories with tree primal graphs. We exploit the sparse graph structure by using search to performing integration. Our algorithm greatly improves the computational efficiency on such problems and exploits context-specific independence between variables. Experimental results show dramatic speedups compared to existing WMI solvers on problems with tree-shaped dependencies.

Cite this Paper


BibTeX
@InProceedings{pmlr-v115-zeng20a, title = {Efficient Search-Based Weighted Model Integration}, author = {Zeng, Zhe and Van den Broeck, Guy}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {175--185}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/zeng20a/zeng20a.pdf}, url = {https://proceedings.mlr.press/v115/zeng20a.html}, abstract = {Weighted model integration (WMI) extends Weighted model counting (WMC) to the integration of functions over mixed discrete-continuous domains. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programming. Yet, state-of-the-art tools for WMI are limited in terms of performance and ignore the independence structure that is crucial to improving efficiency. To address this limitation, we propose an efficient model integration algorithm for theories with tree primal graphs. We exploit the sparse graph structure by using search to performing integration. Our algorithm greatly improves the computational efficiency on such problems and exploits context-specific independence between variables. Experimental results show dramatic speedups compared to existing WMI solvers on problems with tree-shaped dependencies.} }
Endnote
%0 Conference Paper %T Efficient Search-Based Weighted Model Integration %A Zhe Zeng %A Guy Van den Broeck %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-zeng20a %I PMLR %P 175--185 %U https://proceedings.mlr.press/v115/zeng20a.html %V 115 %X Weighted model integration (WMI) extends Weighted model counting (WMC) to the integration of functions over mixed discrete-continuous domains. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programming. Yet, state-of-the-art tools for WMI are limited in terms of performance and ignore the independence structure that is crucial to improving efficiency. To address this limitation, we propose an efficient model integration algorithm for theories with tree primal graphs. We exploit the sparse graph structure by using search to performing integration. Our algorithm greatly improves the computational efficiency on such problems and exploits context-specific independence between variables. Experimental results show dramatic speedups compared to existing WMI solvers on problems with tree-shaped dependencies.
APA
Zeng, Z. & Van den Broeck, G.. (2020). Efficient Search-Based Weighted Model Integration. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:175-185 Available from https://proceedings.mlr.press/v115/zeng20a.html.

Related Material