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 18 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.
翻译:概率图形模型已成为若干现实情景的强大模型工具,其中人们在不确定的情况下需要理性。图形模型的分区功能是一个核心利益,其计算是若干概率推理任务的关键。鉴于计算分区函数的#P-硬性,多年来提出了几种技术,对估计质量及其运行时间行为有不同的保证。本文件试图对18种技术进行调查,并严格地对一系列广泛的基准中的行为进行实证研究。我们的经验研究得出了一个令人惊讶的观察:精确技术与近似技术一样有效,因此,我们最后乐观地看待设计近似技术的机会,提高可伸缩性。由于观测到虚拟最佳溶剂与最佳操作工具之间的数量差异,我们设想了以开发组合解决器为重点的令人振奋的研究线。