Programs and inference

A Bayesian model can be expressed as a program that makes random choices and observes data. Inference asks which execution histories are supported by those observations. For runnable examples, see Probabilistic programming in BAli-Phy.

Distributions over execution histories

A model program draws random variables from their prior distributions. The sequence of random choices in an execution is its trace. Given the input data and those choices, the course of that execution is determined.

Random choices can affect control flow: an execution may take a different branch, recurse further, or create a different number of random variables. The program thus defines a distribution over execution histories, whose structures may differ.

Independent executions draw different parameter values. For example:

BAli-Phy is a universal probabilistic programming language, supporting random control flow and changing collections of random variables. A fixed graphical model provides a useful special case: values change, but the organization of random variables and their dependencies remains fixed.

The term probabilistic programming language is also used more broadly for systems with fixed parameter spaces. Here, the distinction is whether the structure of the probabilistic computation can itself change during inference. Greater expressiveness does not guarantee faster inference; restrictions can enable particularly efficient methods.

For a discussion of universal probabilistic programming in evolutionary biology, see Ronquist et al. (2021).

Conditioning on observations

The program's random choices contribute prior terms. Calls to observe contribute the likelihood of the data. Together they define the posterior over traces:

posterior density ∝ prior density × likelihood

Inference samples traces from this posterior distribution, rather than simply drawing from the prior. A basic approximation would draw many independent prior traces and weight each by its likelihood. This can be inefficient when only a small fraction of prior draws explain the data well.

MCMC over traces

BAli-Phy uses Markov chain Monte Carlo to explore the posterior. A Metropolis–Hastings update involves:

1. Proposing a modified trace by changing random choices.
2. Evaluating the consequences for the program and its probability terms.
3. Accepting or rejecting the proposal using the posterior and proposal probabilities.

A change can alter both values and structure. For example, changing a tree can change which ancestor a descendant depends on. The inference machinery handles these changes while the model program describes the distributions and observations.

Models can also register specialized MCMC moves, as the codon example does. Separating model specification from the inference machinery does not prevent tailoring proposals to a particular model.

Efficient execution in BAli-Phy

Rerunning the entire model program for every proposal would repeat many unchanged computations. BAli-Phy instead tracks dependencies during execution. When a random variable changes, it recomputes affected results and reuses unaffected work.

Model programs use Haskell, evaluated by BAli-Phy's runtime, which is implemented mainly in C++. The runtime records dependencies between computations, including those arising through function calls and control flow. This execution graph can change as different random choices lead to different computations.

The graph therefore serves a different purpose from a fixed graphical model: it tracks the current computation so that updates can be evaluated efficiently. Haskell's functional evaluation supports this design, but dependency tracking is work performed by BAli-Phy's implementation.

Continue with the model-program examples.