• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Partition Function Estimation: A Quantitative Study.
Durgesh Agrawal, Yash Pote and Kuldeep S. Meel.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), August 2021.
Probabilistic graphical models have emerged as a powerful modeling tool for several real-world scenarios where one needs to reason under uncertainty. A graphical model's partition function is a central quantity of interest, and its computation is key to several probabilistic reasoning tasks. Given the #P-hardness of computing the partition function, several techniques have been proposed over the years with varying guarantees on the quality of estimates and their runtime behavior. This paper seeks to present a survey of 17 techniques and a rigorous empirical study of their behavior across an extensive set of benchmarks. Our empirical study draws up a surprising observation: exact techniques are as efficient as the approximate ones, and therefore, we conclude with an optimistic view of opportunities for the design of approximate techniques with enhanced scalability. Motivated by the observation of an order of magnitude difference between the Virtual Best Solver and the best performing tool, we envision an exciting line of research focused on the development of portfolio solvers.
@inproceedings{APM21,
title={Partition Function Estimation: A Quantitative Study},
author={Agrawal, Durgesh and Pote, Yash and Meel, Kuldeep S.},
booktitle=IJCAI,
year={2021},
month=aug,
bib2html_rescat={Counting},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={https://arxiv.org/abs/2105.11132},
abstract={
Probabilistic graphical models have emerged as a powerful modeling tool for
several real-world scenarios where one needs to reason under uncertainty. A
graphical model's partition function is a central quantity of interest, and
its computation is key to several probabilistic reasoning tasks. Given the
#P-hardness of computing the partition function, several techniques have
been proposed over the years with varying guarantees on the quality of
estimates and their runtime behavior. This paper seeks to present a survey
of 17 techniques and a rigorous empirical study of their behavior across an
extensive set of benchmarks. Our empirical study draws up a surprising
observation: exact techniques are as efficient as the approximate ones, and
therefore, we conclude with an optimistic view of opportunities for the
design of approximate techniques with enhanced scalability. Motivated by the
observation of an order of magnitude difference between the Virtual Best
Solver and the best performing tool, we envision an exciting line of
research focused on the development of portfolio solvers.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21