An Introduction to Probabilistic Programming

Jan-Willem van de Meent; Brooks Paige; Hongseok Yang; Frank Wood

Source-linked AI summary

An Introduction to Probabilistic Programming

Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, Frank Wood

arXiv:1809.10756v2Sep 27, 2018stat.MLcs.AIcs.LGcs.PL

TL;DR

The book addresses how probabilistic programs can represent generative models and support conditioning and inference across increasingly expressive programming languages. It develops language and inference foundations from first-order and higher-order systems through differentiable programming, including neural and gradient-based methods.

Problem
Probabilistic programming requires both probabilistic inference and programming-language techniques to represent models and compute posteriors for arbitrary program executions.
Method
The book develops probabilistic programming from model-based reasoning and conditioning through first-order and higher-order languages, inference algorithms, automatic differentiation, and neural parameterizations.
Results
The book provides foundations for using existing probabilistic programming systems and for designing and implementing future systems across first-order, higher-order, and differentiable settings.
Takeaways & Limitations
Probabilistic programming connects program representations of generative models with statistical inference algorithms for conditioning on program outputs.
Takeaways & Limitations
Most of the book assumes the probabilistic program is fixed, while learning parts or all of the generative model is discussed later through variational autoencoders.

Abstract

from arXiv · show

This book is a graduate-level introduction to probabilistic programming. It not only provides a thorough background for anyone wishing to use a probabilistic programming system, but also introduces the techniques needed to design and build these systems. It is aimed at people who have an undergraduate-level understanding of either or, ideally, both probabilistic machine learning and programming languages. We start with a discussion of model-based reasoning and explain why conditioning is a foundational computation central to the fields of probabilistic machine learning and artificial intelligence. We then introduce a first-order probabilistic programming language (PPL) whose programs correspond to graphical models with a known, finite, set of random variables. In the context of this PPL we introduce fundamental inference algorithms and describe how they can be implemented. We then turn to higher-order probabilistic programming languages. Programs in such languages can define models with dynamic computation graphs, which may not instantiate the same set of random variables in each execution. Inference requires methods that generate samples by repeatedly evaluating the program. Foundational algorithms for this kind of language are discussed in the context of an interface between program executions and an inference controller. Finally we consider the intersection of probabilistic and differentiable programming. We begin with a discussion of automatic differentiation, and how it can be used to implement efficient inference methods based on Hamiltonian Monte Carlo. We then discuss gradient-based maximum likelihood estimation in programs that are parameterized using neural networks, how to amortize inference using by learning neural approximations to the program posterior, and how language features impact the design of deep probabilistic programming systems.

Notation

The notation defines expressions and programs for first-order and higher-order probabilistic languages, alongside maps, graphical models, variables, factors, and probability densities.

Probabilistic languages: FOPPL expressions combine constants, variables, binding, conditionals, procedures, primitive functions, sampling, and observations.
Target language: A deterministic target-language expression supports constants, variables, conditionals, and primitive-function application without sampling or observation constructs.
Sets, lists, maps, and expressions: Constants are organized as sets or lists, and maps associate variables with constants while supporting replacement and key-domain operations.
Graphical models: A directed graphical model specifies variable nodes, observed and unobserved subsets, directed parent-child edges, probability expressions, and observed values.
Graphical models: A factor graph represents variable nodes, factor nodes, undirected variable-factor edges, and factor potentials as target-language expressions.
Probabilistic quantities: The joint density p(Y, X), prior p(X), likelihood p(Y | X), and posterior p(X | Y) distinguish the principal distributions over observed and unobserved variables.
Probabilistic quantities: A trace records values for an instantiated set of variables, and evaluating p(X) at that trace gives the corresponding joint probability density.

Introduction

Probabilistic programming combines programming-language tools for denoting probabilistic models with inference algorithms that characterize conditional distributions. This book develops the foundations, implementation strategies, and applications needed to use and build such systems.

Motivation: Probabilistic programming addresses machine reasoning by supporting probabilistic modeling and inference alongside optimization-based approaches such as deep learning.The introduction frames probabilistic machine learning as requiring inference, while deep learning typically relies on gradient-based optimization.
Motivation: Automated inference lowers the cost of iterating Bayesian model designs, enabling better models to be developed in less time.Traditional analyses often required implementing a model-specific inference algorithm for each iteration.
Scope: The book covers probabilistic programming from model denotation and language design through evaluator implementation and inference algorithms.It is intended both to help readers adopt existing systems and to provide a foundation for future language designers and implementers.
Conditioning: Bayesian inference is generally difficult because conditioning requires integrating over latent-variable spaces, which can be exponential in examples such as Captcha interpretation.The book therefore emphasizes sampling-based characterizations of conditional distributions, since exact density evaluation and sampling are not generally possible.
Conditioning: Conditioning characterizes posterior distributions over random choices that could have produced an observed program output.Probabilistic programming uses programming languages to denote generative models and statistical inference algorithms to compute their conditional distributions.
Expressive Models: Probabilistic programming supports expressive models, including program synthesis through inference that inverts a generative model and conditions on observed behavior.The modeling language can be more compact and readable than mathematical notation while accommodating programs that users write in expressive languages.

A Probabilistic Language Without Recursion

FOPPL is a first-order Lisp-based probabilistic language whose finite, statically determined computation graphs support compilation to graphical models. Its restricted syntax omits recursion and I/O, while retaining expressive coverage of graphical models, BUGS programs, and fixed-graph neural networks.

FOPPL programs describe distributions over finitely many random variables and can be compiled into corresponding graphical models.Its computation graphs can be completely determined and unrolled at compile time.
The language is a Clojure-based Lisp variant with recursive grammar rules for expressions and programs, including functions, conditionals, bindings, and primitive operations.Programs consist of an expression optionally preceded by function declarations.
The sample form creates an unobserved random variable by sampling from a distribution-valued expression, while observe conditions on a supplied value.These two forms provide FOPPL's probabilistic operations.
Despite its small grammar and lack of input/output, FOPPL can express any graphical model and supports compilation of BUGS programs and fixed-computation-graph neural networks.Examples include multilayer perceptrons, convolutional networks, and fixed-length recurrent networks.
First-order restrictions disallow potentially non-halting computations and recursive calls, yielding a finite compilation-time bound on computation steps.Function-call restrictions can be enforced through scoping and preprocessing.
FOPPL includes vector and map data structures in addition to standard Lisp-like constants, variables, let forms, conditionals, and applications.The grammar also distinguishes user-defined and primitive procedure applications.

Graph-Based Inference

FOPPL programs are translated into finite graphical models through a compilation relation that also produces a deterministic expression representing the program's return value. Graph vertices encode random variables, arcs encode dependencies, and observed nodes carry values and control-flow predicates.

FOPPL programs specify probabilistic models over finitely many random variables that can be translated into graphical models for inference.The translation enables adapting graphical-model inference algorithms to probabilistic programs.
The compilation relation maps a source expression, procedure environment, and flow-control predicate to a graphical model G and deterministic expression E.E describes the original expression's return value using random variables in G.
Graphical-model vertices represent random variables, arcs represent dependencies, and observed variables include values plus predicates indicating whether their observe expressions are active.

Definition of a Graphical Model

A graphical model is formally represented as a tuple containing random-variable vertices, dependency arcs, probability maps, and observed values. A simple FOPPL mixture program illustrates how compilation exposes the posterior inference problem.

A graphical model G is a tuple (V, A, P, Y) containing vertices, directed dependency arcs, probability expressions, and a partial map of observed values.
In the example program, a Bernoulli sample z selects between Gaussian means −1.0 and 1.0 before observing y = 0.5.
The example defines the joint distribution p(y = 0.5, z), with inference focused on characterizing the posterior p(z | y).The corresponding graphical model and deterministic link functions are shown in Figure 3.1.
For the example graph, V contains z and y, while A contains the single conditional-dependence edge (z, y).The probability map assigns Bernoulli and normal mass or density functions to the variables.

Assigning Symbols to Variable Nodes

Compilation assigns graphical-model vertices unique symbols corresponding to random-variable addresses. This is straightforward for simple programs but requires care when procedures evaluate the same sample and observe expressions multiple times.

A graphical-model node generally corresponds to each evaluated sample or observe expression, but program-variable names need not uniquely identify those nodes.
In the procedure example, each sample expression inside norm-gamma is evaluated twice, making the mapping from program variables to random variables less direct.
The compilation rules assign every graph vertex a newly generated unique symbol, while tutorial examples name sample and observe returns for readability.
Unique vertex labels serve as random-variable addresses needed for correct and generic inference algorithms.The book later develops explicit addressing for programs whose control-flow paths cannot be fully explored at compile time.

if-expressions in Graphical Models

The placement and evaluation strategy of if-expressions determines how probabilistic programs map to graphical models. Lazy evaluation preserves branch-specific execution but creates support and normalization challenges, whereas eager evaluation gives a conventional mixture structure but mishandles conditional observations.

Program structure: Moving the if-expression outside a sample adds an explicit sample node while preserving the distribution on return values.The rewritten program has four nodes rather than three, but both programs induce the same distribution on z.
Evaluation strategy: Lazy evaluation samples only the selected branch, while eager evaluation samples both branches before returning the predicate-selected value.For Program 3.5, lazy evaluation resembles the two-sample formulation, whereas eager evaluation is equivalent to the explicit four-node formulation.
Lazy-evaluation support: Lazy evaluation with probability-one densities for unevaluated branches produces improper priors and a divergent marginal-likelihood integral.The problem arises because the assumed support includes variables from branches that were not evaluated.
Lazy-evaluation support: A branch-union support can assign nil to variables in unevaluated branches, but nested conditionals make the resulting support definitions complicated.The support is represented as a union in which exactly one branch variable is real and the other is nil.
Evaluation strategy: Eager evaluation yields the standard mixture joint density by incorporating both branch samples into the joint distribution.The resulting factors are p(y|µ0, µ1, z)p(z)p(µ0)p(µ1), with branch parameters sampled regardless of z.
Conditional observations: Conditional observe expressions favor lazy evaluation because eager evaluation would incorporate observations from both branches and produce counter-intuitive results.This motivates special treatment of observes when choosing an evaluation strategy.

Support-Related Subtleties

FOPPL permits distributions with potentially infinite support and distributions whose support or type depends on sampled control flow. These cases do not necessarily create unbounded random-variable graphs, but they require care in reasoning and inference.

Stochastic support and type: Stochastic control flow can make a distribution’s support and type depend on a sampled value.Program 3.8 selects between a Normal and Gamma distribution, so the sampled distribution itself changes with control flow.
Infinite support: A sampled Poisson value may define a discrete distribution with potentially infinite support without inducing an unbounded number of random variables.The sampled value cannot be used as a loop bound, so the program remains non-problematic in this respect.

Translation rules

The translation rules recursively compile FOPPL expressions into graphical models and deterministic target expressions. Sample and observe forms add graph variables and factors, while control-flow predicates govern which observations contribute.

Recursive translation: The recursive translation handles constants, variables, lets, conditionals, procedure calls, samples, and observes by translating their sub-expressions.Let expressions substitute the translated binding before translating the body, while deterministic constructs otherwise preserve the graph structure.
Graph construction: The graphical-model combination operator assumes disjoint vertices, ensured because translation generates fresh vertices for each network.This makes model merging well-defined during recursive translation.
Graph construction: The rules prioritize readability over efficiency, potentially evaluating the same translated expression once for each occurrence of a substituted variable.Deterministic graph nodes could avoid these duplicate computations, but that optimization is omitted.
Conditionals: Translating an if-expression combines the three submodels and conjoins the predicate or its negation with each branch.The predicate controls whether branch-specific observe statements are active on the current sample path.
Sample and observe: A sample translation creates a fresh variable, links it to free random variables in the distribution expression, and records its probability mass or density.Translation fails with bottom when the sampled expression does not denote a distribution.
Sample and observe: An observe translation creates a fresh observed variable, records its observed value, and gates its score by the control-flow predicate.The observed expression must be fully deterministic, requiring free-vars(E2) = ∅.
Factor-graph representation: The compiled undirected representation introduces deterministic variable nodes for primitive operations, supporting subsequent inference procedures.Examples include nodes for subtraction and comparisons.

Inference with Evaluators

Evaluation-based inference avoids requiring a dependency graph before execution, making it suitable for programs with dynamic or potentially unbounded support. Importance sampling uses executable proposals and unnormalized weights, also yielding a marginal-likelihood estimate.

Dynamic support: Dynamic-support models cannot have their conditional-dependency graphs constructed before inference because the number of random variables may be unknown at compile time.Object tracking is an example where object count and duration in view can vary.
Dynamic support: Dynamic support can be approximated with bounded static variables and on/off indicators, or handled by dynamically instantiating variables during inference.Evaluation-based strategies generate values by repeatedly running the program.
Evaluation-based inference: Evaluation-based methods build dependency structure at run time or avoid constructing it explicitly, allowing application to models with potentially unbounded random variables.This contrasts with compilation-based methods, which require a graph representation before execution.
Evaluation semantics: Lazy evaluation is necessary for conditional observes, while sample expressions permit either lazy or eager evaluation in the discussed setting.The distinction follows from observes changing the posterior distribution on the program output.
Evaluation semantics: Recursive stochastic programs can defeat eager compilation because evaluating both branches may trigger infinite recursion.The recursive geometric sampler uses a sampled Bernoulli outcome to continue or terminate recursion.
Importance sampling: Importance sampling approximates posterior expectations with weighted samples from an easy-to-sample proposal distribution rather than directly sampling the posterior.The proposal must cover every region having nonzero posterior probability.
Importance sampling: Unnormalized joint probabilities replace unavailable posterior-to-proposal ratios, and their average provides an estimate of the marginal likelihood usable for Bayesian model comparison.This requires evaluating p(Y, Xl) for samples Xl drawn from q(X).

3. Return the weighted set of return values r(Xl)

Likelihood weighting evaluates a probabilistic program repeatedly, sampling from prior distributions and accumulating observation log probabilities as inference-state side effects. It returns weighted program outputs without requiring an explicit dependency graph.

The evaluator recursively handles constants, variables, let bindings, conditionals, procedure calls, and primitive calls.Let forms extend the local environment, and conditionals evaluate only the selected branch.
Procedure calls evaluate arguments first, then evaluate the procedure body in an environment extended with the corresponding parameter bindings.Primitive calls instead apply the language implementation’s function to evaluated arguments.
Sample expressions draw prior values, while observe expressions add the observed value’s log probability to the inference state.The evaluator returns the observed value after updating σ(log W).
Likelihood weighting repeatedly evaluates a FOPPL program and returns each execution’s return value together with its final log weight.Executions start with log W = 0.
The implementation does not track the number of sample or observe statements or maintain an explicit conditional-dependency graph.It samples and accumulates log probabilities only when those forms are encountered during execution.

Aside 1: Relationship between Evaluation and Inference Rules

The translation rules provide an implementation recipe: recursively translate each subexpression, then combine the translated results according to the expression form.

For a primitive call, translation recursively processes every argument and returns each argument’s graph-expression pair.
The translated argument graphs are combined, and the resulting expressions are assembled into a target-language primitive call.

4. Return the pair G, E

Inference rules define translation compositionally, mirroring big-step programming-language semantics: each expression is determined from its subexpressions and yields a graph-expression pair.

Inference rules for translation can be implemented as recursive translate operations specialized to each expression type.
Big-step semantics defines an expression’s value from the values of its subexpressions, and the same pattern defines evaluation-based likelihood weighting.
The likelihood-weighting inference rules are presented as big-step semantics for the evaluator.

Aside 2: Side Effects and Referential Transparency

Adding sample and observe makes the language impure: sampling changes returned values, while observing preserves its returned value but updates inference state. Evaluation-based MCMC reuses this execution-and-side-effect strategy for proposals and acceptance ratios.

Side Effects and Referential Transparency: Without sample and observe, FOPPL expressions are pure and referentially transparent because each expression always evaluates to the same value.
Side Effects and Referential Transparency: Sample expressions are referentially opaque because repeated evaluations can return different values.
Side Effects and Referential Transparency: Observe expressions return their observed value but increment σ(log W), so replacing them with that value would erase likelihood accumulation.
Evaluation-based MCMC: Evaluation-based Metropolis-Hastings reruns the program to generate proposals conditioned on previous sample values and computes the acceptance ratio as a side effect.
Evaluation-based MCMC: Independent proposals from the prior simplify acceptance to a likelihood ratio that reuses likelihood weighting’s computed log weight.
Evaluation-based MCMC: Single-site Metropolis-Hastings changes one variable, reuses other values when possible, and resamples variables absent from the new execution trace.

Addressing Transformation

The addressing transformation assigns unique identifiers to every sample and observe expression, enabling inference algorithms to refer to stochastic choices consistently.

Address generation: Unique addresses let inference associate each sample or observe expression with a corresponding variable.This supports the formal definition of single-site Metropolis-Hastings proposals.
Address generation: The transformation replaces each sample expression with an addressed form containing a newly created variable.Observe expressions receive analogous addresses through the same source-code transformation.
Transformation procedure: The transformation accepts function definitions and an expression, returning a transformed expression with addresses inserted into stochastic expressions.The resulting expression remains suitable for subsequent inference processing.
Transformation procedure: The addressed expressions provide the cases needed by the proposal evaluator for sample and observe operations.The evaluator is presented as Algorithm 7 for single-site proposals.

Evaluating Proposals

Proposal evaluation reuses cached values where possible, resamples selected sites, and computes probabilities needed by Metropolis-Hastings and sequential Monte Carlo.

Metropolis-Hastings: During proposal evaluation, cached values are reused for non-proposal sample sites, while the selected site is resampled.Sample and observe expressions also contribute their log probabilities to the inference state.
Metropolis-Hastings: Single-site Metropolis-Hastings initializes a state by evaluating the program, then repeatedly selects a current sample site and reruns the program to construct a proposal.The proposed state is accepted or rejected according to the Metropolis-Hastings ratio.
Sequential Monte Carlo: Likelihood weighting is simple and general but inefficient when many random variables must jointly produce a high-weight sample.It guesses from the prior and checks the result using the observe probabilities.
Sequential Monte Carlo: Sequential Monte Carlo converts high-dimensional sampling into a sequence of lower-dimensional sampling problems using weighted particles and resampling.Resampling favors particles with higher weights, especially when successive density weights are strongly correlated.
Sequential Monte Carlo: SMC for FOPPL programs uses truncated programs separated by ordered breakpoints that must occur in every execution.Bootstrapped proposals sample new variables from the prior and assign incremental weights from newly evaluated observes.
Sequential Monte Carlo: The bootstrapped SMC evaluator reuses previously sampled variables, samples new variables from the prior, accumulates log likelihood, and halts at a designated observe breakpoint.The proposal mechanism returns particle values and their accumulated log likelihood for each generation.

A Probabilistic Language With Recursion

Higher-order probabilistic languages support recursion and therefore unbounded random-variable cardinality, requiring evaluation-based inference and interfaces that separate execution from inference.

A Probabilistic Language With Recursion: HOPPLs support higher-order procedures and general recursion, allowing programs to denote models with an unbounded number of random variables.This removes the finite-variable restriction of first-order probabilistic languages.
A Probabilistic Language With Recursion: Because infinite graphical models cannot be represented on finite-capacity computers, HOPPL inference evaluates only a finite portion of a program at a time.Evaluation-based inference remains applicable despite unbounded model structure.
A Probabilistic Language With Recursion: Stochastic recursion can generate infinitely many random variables and may produce computations that never terminate.The geometric sampler illustrates this behavior because each recursive stage samples again.
Execution and inference: Inference can be formulated as non-standard scheduling of HOPPL programs, treating sample and observe as the stochastic operations with side effects.Most other program operations are deterministic and referentially transparent.
Execution and inference: Addressing and continuation-passing transformations preserve HOPPL output while enabling unique runtime addresses and language-agnostic inference controllers.The transformed code can still use an existing compiler, and addresses are determined by call stacks.
Static addressing: Static addressing provides a middle ground between FOPPL and HOPPL programming by retaining higher-order functions while making variable identifiers explicit.This simplifies inference because the set of variables need not vary across executions.
Differentiable programming: Reverse-mode automatic differentiation computes correct derivatives by propagating pathwise derivatives backward through a graph built during a forward pass.The method sums derivatives along unique paths from output to input.