Scaling Integer Arithmetic in Probabilistic Programs

• URL: http://arxiv.org/abs/2307.13837v1
• Date: Tue, 25 Jul 2023 22:21:07 GMT
• Title: Scaling Integer Arithmetic in Probabilistic Programs
• Authors: William X. Cao, Poorva Garg, Ryan Tjoa, Steven Holtzen, Todd Millstein, Guy Van den Broeck
• Abstract summary: We present a binary encoding strategy for discrete distributions that exploits the rich logical structure of integer operations. We show that this approach scales to much larger integer distributions with arithmetic.
• Score: 21.26857534769979
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributions on integers are ubiquitous in probabilistic modeling but remain challenging for many of today's probabilistic programming languages (PPLs). The core challenge comes from discrete structure: many of today's PPL inference strategies rely on enumeration, sampling, or differentiation in order to scale, which fail for 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 with knowledge compilation to perform exact probabilistic inference, and show that this approach scales to much larger integer distributions with arithmetic.

Related papers

• Probabilistic Answer Set Programming with Discrete and Continuous Random Variables [0.18416014644193066]
  Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with probabilistic facts that represent uncertain information. We propose Hybrid Probabilistic Answer Set Programming (HPASP) We discuss, implement, and assess the performance of two exact algorithms based on projected answer set enumeration and knowledge compilation.
  arXiv  Detail & Related papers  (2024-09-30T13:24:42Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization.
  arXiv  Detail & Related papers  (2023-09-01T18:02:04Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Parallel Sampling for Efficient High-dimensional Bayesian Network Structure Learning [6.85316573653194]
  This paper describes an approximate algorithm that performs parallel sampling on Candidate Parent Sets (CPSs) The modified algorithm, which we call Parallel Sampling MINOBS (PS-MINOBS), constructs the graph by sampling CPSs for each variable.
  arXiv  Detail & Related papers  (2022-02-19T22:35:59Z)
• Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors [1.8130068086063333]
  Stragglers and other failures can severely impact the overall completion time. Recent works in coded computing provide a novel strategy to mitigate stragglers with coded tasks. We show that this strict definition does not directly optimize the probability of failure.
  arXiv  Detail & Related papers  (2022-02-07T19:20:00Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm [0.0]
  purge-and-merge algorithm is designed to nudge a malleable graph structure towards a tree structure by selectively merging factors. This approach is evaluated on a number of constraint-satisfaction puzzles such as Sudoku, Fill-a-pix, and Kakuro. Although these tasks were limited to the binary logic of CSP, we believe it holds promise for extension to general PGM inference.
  arXiv  Detail & Related papers  (2021-09-30T21:20:52Z)
• pRSL: Interpretable Multi-label Stacking by Learning Probabilistic Rules [0.0]
  We present the probabilistic rule stacking (pRSL) which uses probabilistic propositional logic rules and belief propagation to combine the predictions of several underlying classifiers. We derive algorithms for exact and approximate inference and learning, and show that pRSL reaches state-of-the-art performance on various benchmark datasets.
  arXiv  Detail & Related papers  (2021-05-28T14:06:21Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• A General Method for Robust Learning from Batches [56.59844655107251]
  We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. We derive the first robust computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.
  arXiv  Detail & Related papers  (2020-02-25T18:53:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.