 NSFPAR ID:
 10425675
 Date Published:
 Journal Name:
 Proceedings of the ACM on Programming Languages
 Volume:
 7
 Issue:
 OOPSLA1
 ISSN:
 24751421
 Page Range / eLocation ID:
 665 to 695
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

A streaming probabilistic program receives a stream of observations and produces a stream of distributions that are conditioned on these observations. Efficient inference is often possible in a streaming context using RaoBlackwellized particle filters (RBPFs), which exactly solve inference problems when possible and fall back on sampling approximations when necessary. While RBPFs can be implemented by hand to provide efficient inference, the goal of streaming probabilistic programming is to automatically generate such efficient inference implementations given input probabilistic programs. In this work, we propose semisymbolic inference, a technique for executing probabilistic programs using a runtime inference system that automatically implements RaoBlackwellized particle filtering. To perform exact and approximate inference together, the semisymbolic inference system manipulates symbolic distributions to perform exact inference when possible and falls back on approximate sampling when necessary. This approach enables the system to implement the same RBPF a developer would write by hand. To ensure this, we identify closed families of distributions – such as linearGaussian and finite discrete models – on which the inference system guarantees exact inference. We have implemented the runtime inference system in the ProbZelus streaming probabilistic programming language. Despite an average 1.6× slowdown compared to the state of the art on existing benchmarks, our evaluation shows that speedups of 3×87× are obtainable on a new set of challenging benchmarks we have designed to exploit closed families.more » « less

For many classic structured prediction problems, probability distributions over the dependent variables can be efficiently computed using widelyknown algorithms and data structures (such as forwardbackward, and its corresponding trellis for exact probability distributions in Markov models). However, we know of no previ ous work studying efficient representations of exact distributions over clusterings. This paper presents definitions and proofs for a dynamicprogramming inference procedure that computes the partition function, the marginal probability of a cluster, and the MAP clustering—all exactly. Rather than the N th Bell number, these exact solutions take time and space proportional to the substantially smaller powerset of N . Indeed, we improve upon the time complexity of the algorithm introduced by Kohonen and Corander [11] for this problem by a factor of N. While still large, this previously unknown result is intellectually interesting in its own right, makes feasible exact inference for important realworld small data applications (such as medicine), and provides a natural stepping stone towards sparsetrellis approximations that enable further scalability (which we also explore). In experi ments, we demonstrate the superiority of our approach over approximate methods in analyzing realworld gene expression data used in cancer treatment.more » « less

Probabilistic programming languages aid developers performing Bayesian inference. These languages provide programming constructs and tools for probabilistic modeling and automated inference. Prior work introduced a probabilistic programming language, ProbZelus, to extend probabilistic programming functionality to unbounded streams of data. This work demonstrated that the delayed sampling inference algorithm could be extended to work in a streaming context. ProbZelus showed that while delayed sampling could be effectively deployed on some programs, depending on the probabilistic model under consideration, delayed sampling is not guaranteed to use a bounded amount of memory over the course of the execution of the program. In this paper, we the present conditions on a probabilistic program’s execution under which delayed sampling will execute in bounded memory. The two conditions are dataflow properties of the core operations of delayed sampling: the m consumed property and the unseparated paths property . A program executes in bounded memory under delayed sampling if, and only if, it satisfies the m consumed and unseparated paths properties. We propose a static analysis that abstracts over these properties to soundly ensure that any program that passes the analysis satisfies these properties, and thus executes in bounded memory under delayed sampling.more » « less

Probabilistic programming languages are valuable because they allow domain experts to express probabilistic models and inference algorithms without worrying about irrelevant details. However, for decades there remained an important and popular class of probabilistic inference algorithms whose efficient implementation required manual lowlevel coding that is tedious and errorprone. They are algorithms whose idiomatic expression requires random array variables that are latent or whose likelihood is conjugate . Although that is how practitioners communicate and compose these algorithms on paper, executing such expressions requires eliminating the latent variables and recognizing the conjugacy by symbolic mathematics. Moreover, matching the performance of handwritten code requires speeding up loops by more than a constant factor. We show how probabilistic programs that directly and concisely express these desired inference algorithms can be compiled while maintaining efficiency. We introduce new transformations that turn highlevel probabilistic programs with arrays into pure loop code. We then make great use of domainspecific invariants and norms to optimize the code, and to specialize and JITcompile the code per execution. The resulting performance is competitive with manual implementations.more » « less

Weighted model counting and integration (WMC/WMI) are natural problems to which we can reduce many probabilistic inference tasks, e.g., in Bayesian networks, Markov networks, and probabilistic programs. Typically, we are given a firstorder formula, where each satisfying assignment is associated with a weighte.g., a probability of occurrenceand our goal is to compute the total weight of the formula. In this paper, we target exact inference techniques for WMI that leverage the power of satisfiability modulo theories (SMT) solvers to decompose a firstorder formula in linear real arithmetic into a set of hyperrectangular regions whose weight is easy to compute. We demonstrate the challenges of hyperrectangular decomposition and present a novel technique that utilizes orthogonal transformations to transform formulas in order to enable efficient inference. Our evaluation demonstrates our technique's ability to improve the time required to achieve exact probability bounds.