An Introduction to Probabilistic Programming

I like this passage: In this and the next two chapters of this introduction we will present the key ideas of probabilistic programming using a carefully designed first-order probabilistic programming language (FOPPL). The FOPPL includes most common features of programming languages, such as conditional statements (e.g. if), primitive operations (e.g. +,-, etc.), and user-defined functions. The restrictions that we impose are that functions must be first order, which is to say that functions cannot accept other functions as arguments, and that they cannot be recursive. These two restrictions result in a language where models describe distributions over a finite number of random variables. In terms of expressivity, this places the FOPPL on even footing with many existing languages and libraries for automating inference in graphical models with finite graphs.

This gives a nice picture of what's happening. At the same time, does this mean that in the end, you're basically operating on a single distribution with only a few canned global transformations?

I think, and this is WAY outside my area, is that Hamiltonian Monte Carlo (a Markov chain monte carlo method) is used. Beyond that and I'm lost.

Probabilistic programming can be done via MCMC approaches, but you can also infer the necessary quantities by using variational inference (which approximates the distribution described by your program with something that's simpler and easier to estimate).

Basically probabilistic programming is a way of describing a distribution, and then MCMC is one way of inferring the quantities in that distribution.

Probabilistic programming uses computer science techniques to do automated statistical modeling. For example, imagine I have a coin, and I want to discover if it is biased, i.e. if it lands on heads more often than tails. In a probabilistic programming framework, I can express my model as a simple Bernoulli model, `x ~ Bernoulli(p)`, and then automatically estimate the bias parameter `p` given some data (do "inference").

You can easily do this calculation by hand or in Python, but this does not generalize to more complex real-world scenarios. For complex probabilistic models, we must rely on numerical approximations. MCMC is just one algorithm for doing this approximate inference. Another popular technique is called variational inference [2]. Another commenter mentioned HMC [3], which is just a specific instance of MCMC.

[1] https://mc-stan.org/

[2] https://arxiv.org/abs/1601.00670

[3] https://arxiv.org/abs/1206.1901

I'd argue that probabilistic programming is a language or framework of programming that lets you easily build and then fit probabilistic models to estimate or predict things of interest.

If you're taking a Bayesian approach to statistical modelling and inference, then they're probably a fairly good tool to consider. With the Bayesian approach you're trying to compute some posterior probability distribution that summarises your prior information (this might capture domain knowledge, information from related studies) and information from observations.

There are different ways to compute a posterior distribution. In very simple or contrived cases you might be able to manually grind out an answer analytically with pen and paper and lots of algebra and integrals. But that isn't very efficient or scalable. Also, nice algebraic structure is very easily broken by small perturbations to the problem statement -- need to add a weird bit onto the model to capture some real world behaviour? Good chance that ruins your algebraic structure and previous analytic "attack".

MCMC can be used to estimate the integrals you need when computing a posterior distribution. MCMC isn't the only way to estimate or approximate these calculations -- e.g. another approach is variational inference where a bunch of approximations are introduced to replace the original calculation with an approximation that is easier to compute -- this likely introduces bias into the results but can give you something that can then be solved analytically or semi analytically (e.g. approximate everything as Gaussian distributions and a lot of integration collapses to efficiently computable algebraic identities).

Some probabilistic programming platforms like Stan let you define your probabilistic model and parameters and decouple it from the computational backend used to estimate the posterior distribution. E.g. in Stan you can switch the computational backend between MCMC (https://mc-stan.org/docs/2_18/stan-users-guide/sampling-diff...) and ADVI (auto-differentiation variational inference).

MCMC has practical problems in that it is only guaranteed to give you the correct (unbiased) estimate asymptotically, in the limit if you run it for an infinite amount of time. If you're trying to approximate the integral of a function that is very multi-modal -- where it would be difficult for a global optimisation algorithm to locate the global optima -- then MCMC will likely also struggle to produce a good estimate. MCMC is difficult to parallelise effectively as the algorithm is inherently like an iterative local search procedure -- the next state in the chain is some mutation of the previous state. You can run n MCMC chains in parallel from n different initial configurations, but it's not obvious that you'll get a better estimate from n short chains vs a single long chain -- the longer a chain runs, the more chance it has of being able to discover and explore higher probability (more realistic, more plausible) configurations of the parameter space.

MCMC isn't only used for probabilistic programming, you can apply it for other things. E.g. it gets used in material science to study statistical properties of molecular dynamics simulations etc.