UCLA

Distributions on integers are ubiquitous in probabilistic modeling but remain challenging for many of today’s probabilistic programming languages (PPLs), restricting their use as modeling tools. The core challenge comes from the nature of these distributions: many of today’s PPL inference strategies rely on enumeration, sampling, or differentiation in order to scale, which fail for the high-dimensional complex discrete distributions involving integers. Our insight is that there is structure in arithmetic that these approaches are not using. We present a binary encoding strategy for discrete distributions that exploits the rich logical structure of integer operations like summation and comparison. We leverage this structured encoding through knowledge compilation to perform exact probabilistic inference, and show that this approach scales to much larger integer distributions with arithmetic. Finally, we demonstrate an application of these scalable integers in representing the continuous Beta distribution, with potential application in Bayesian parameter learning.