Probabilistic circuits (PCs) are a powerful modeling framework for representing tractable probability distributions over combinatorial spaces. In machine learning and probabilistic programming, one is often interested in understanding whether the distributions learned using PCs are close to the desired distribution. Thus, given two probabilistic circuits, a fundamental problem of interest is to determine whether their distributions are close to each other. The primary contribution of this paper is a closeness test for PCs with respect to the total variation distance metric. Our algorithm utilizes two common PC queries, counting and sampling. In particular, we provide a poly-time probabilistic algorithm to check the closeness of two PCs when the PCs support tractable approximate counting and sampling. We demonstrate the practical efficiency of our algorithmic framework via a detailed experimental evaluation of a prototype implementation against a set of 475 PC benchmarks. We find that our test correctly decides the closeness of all 475 PCs within 3600 seconds.
翻译:概率电路(PCs)是代表组合空间的可移动概率分布的强大模型框架。 在机器学习和概率编程中,人们往往有兴趣了解使用PCs所学的分布是否接近预期分布。因此,考虑到两种概率电路,一个根本的问题就是确定它们之间的分布是否接近。本文的主要贡献是对PCs的近距离测量。我们的算法使用两种共同的PC查询、计数和取样方法。特别是,我们提供一种多时概率算法,以检查两种PCs在支持可移植计算和取样时的近距离。我们通过对一组475个人计算机基准的原型实施进行详细的实验性评估,来证明我们的算法框架的实际效率。我们发现我们的测试正确地决定了所有475个人计算机在3600秒内的近距离。