Inference Compilation and Universal Probabilistic Programming

Tuan Anh Le; Atilim Gunes Baydin; Frank Wood

Source-linked AI summary

Inference Compilation and Universal Probabilistic Programming

Tuan Anh Le, Atilim Gunes Baydin, Frank Wood

arXiv:1610.09900v2Oct 31, 2016cs.AIcs.LGstat.ML

TL;DR

Inference in universal probabilistic programs is flexible but expensive to amortize across repeated observations. The paper compiles each probabilistic program into an adaptive neural proposal network trained on model-generated traces, enabling sequential importance sampling and fast approximate inference. Experiments on mixture models and Captcha solving demonstrate efficient inference, while performance on real Captcha data depends on appropriately specified model priors.

Problem
The paper addresses the problem of amortizing inference for generative models specified by universal probabilistic programs.
Method
The method automatically constructs and trains an adaptive LSTM-based neural architecture from each probabilistic program to parameterize proposal distributions for sequential importance sampling.
Results
The approach successfully trained neural proposals for the studied models and reduced Captcha inference time to < 100 ms, compared with 500 ms to 7.95 s for reported segment-and-classify methods.
Takeaways & Limitations
The framework combines universal probabilistic-program expressiveness for generative modeling with deep-neural-network processing speed for inference.
Takeaways & Limitations
Real-data performance required tuning the Captcha model priors, highlighting risk from model misspecification and the synthetic gap.

Abstract

from arXiv · show

We introduce a method for using deep neural networks to amortize the cost of inference in models from the family induced by universal probabilistic programming languages, establishing a framework that combines the strengths of probabilistic programming and deep learning methods. We call what we do "compilation of inference" because our method transforms a denotational specification of an inference problem in the form of a probabilistic program written in a universal programming language into a trained neural network denoted in a neural network specification language. When at test time this neural network is fed observational data and executed, it performs approximate inference in the original model specified by the probabilistic program. Our training objective and learning procedure are designed to allow the trained neural network to be used as a proposal distribution in a sequential importance sampling inference engine. We illustrate our method on mixture models and Captcha solving and show significant speedups in the efficiency of inference.

1 INTRODUCTION

Universal probabilistic programs support unrestricted generative models, but their flexibility makes inference costly. The paper compiles such inference problems into adaptive neural proposals for sequential importance sampling, combining probabilistic-program expressiveness with neural-network speed.

Universal probabilistic programming languages allow inference in unrestricted models using constructs such as higher-order functions, stochastic recursion, and control flow.
Inference compilation transforms a probabilistic program into a trained neural architecture whose artifact parameterizes proposal distributions during sequential importance sampling.
The paper targets forward inference in universal probabilistic programs because dependency inversion is impossible in this model family.
The adaptive architecture combines an LSTM core with embedding and proposal layers specified by each probabilistic program and reconfigured for execution traces.
The approach is trained offline on model-generated traces, producing varied proposals for explicitly structured models without requiring model-specific dependency inversion.

2 BACKGROUND

Probabilistic programs define generative models through sample and observe statements, and inference seeks the conditional distribution over execution traces. Sequential importance sampling approximates that posterior with weighted proposal traces whose distributions are specified for each address–instance pair.

2.1 Probabilistic Programming: Probabilistic programs use sample and observe statements to define generative models and condition execution traces on observed values.
2.1 Probabilistic Programming: Execution traces record sampled values, statement addresses, and call instances, with trace length and statement order potentially varying across executions.
2.1 Probabilistic Programming: Inference in these models computes an approximation of p(x|y) and its expected values.
2.2 Sequential Importance Sampling: Sequential importance sampling approximates the posterior and expectations using a weighted set of sampled execution traces.
2.2 Sequential Importance Sampling: SIS constructs proposal traces by sampling at each encountered address–instance pair and assigns weights to the resulting traces.

3 APPROACH

Inference compilation adapts proposal distributions for sequential importance sampling by training a neural network specialized to each probabilistic program. The architecture combines a recurrent core with program-specific embeddings and proposal layers, trained from generated execution traces.

3.1 Objective Function: Inference compilation adapts proposals q_at,it(x_t|x_1:t−1,y) to approximate p(x|y) within sequential importance sampling.The inference procedure remains unchanged except that proposals condition on observations y.
3.1 Objective Function: The objective minimizes the expected KL divergence D_KL(p(x|y) || q(x|y; φ)) over observations, equivalently optimizing expected negative log proposal density.Individual proposals depend on the neural network output η_t parameterized by φ.
3.2 Training Data: Training uses execution traces sampled from an unconstrained program that replaces each observe statement with a sample and ignores its observed value.Minibatches are generated from p(x,y) and streamed to stochastic gradient descent for optimizing φ.
3.3 Neural Network Architecture: The compilation artifact contains a shared RNN core plus program-specific observation embedding and proposal layers, with trained weights specialized to the probabilistic program.The RNN hidden state incorporates temporal dependencies, while proposal layers produce η_t for each address–instance pair.
3.3 Neural Network Architecture: The adaptive architecture handles variable-length traces and changing random-choice structure by creating embedding and proposal layers for encountered address–instance pairs.At each step, the LSTM receives the observation embedding, previous sample embedding, previous sample value, and current address, instance, and proposal-type encodings.
3.3 Neural Network Architecture: During inference, the artifact supplies proposal parameters as address–instance pairs are encountered, while the previous sample is drawn from the preceding proposal.The implementation supports distributed training and GPU-backed inference across multiple machines.

4 EXPERIMENTS

The experiments evaluate inference compilation on an open-universe Gaussian mixture model and Captcha-solving models. Across both applications, learned neural proposals improve inference efficiency and achieve fast, high recognition rates, including on real Captcha images.

4.1 Mixture Models: For mixture models, the neural network uses a convolutional observation embedding to represent cluster-count information and condition subsequent cluster localization.The input is a two-dimensional histogram image of the observed data.
4.1 Mixture Models: Mixture-model training breaks permutation symmetries by sorting clusters, so the proposal receives consistently ordered training examples.The model has K! class-label permutations and N! data-point permutations; sorting makes the nearest cluster to the origin the first proposal target.
4.1 Mixture Models: Inference compilation learned a proposal that made Gaussian-mixture inference dramatically more efficient than sequential Monte Carlo with three fixed clusters.The experiment also considers an unknown number of clusters and uses neural processing to count and localize them.
4.2 Captcha Solving: Captcha models encode domain-specific letter dictionaries, fonts, placement, and renderer noise, while excluding some noise parameters from inference improved robustness on mismatched test data.Displacement fields were instrumental in achieving the reported results.
4.2 Captcha Solving: Under 100 ms per test Captcha was achieved after approximately 16M training traces, compared with 500 ms to 7.95 s for reported segment-and-classify approaches.The comparison concerns test-time inference using the trained compilation artifacts.
4.2 Captcha Solving: 81% and 42% recognition rates were achieved on real Wikipedia and Facebook Captcha datasets, respectively, after initially obtaining rates below 10%.The datasets contained 500 labeled images each, and both rates exceeded the cited 1% threshold for deeming a Captcha scheme broken.

5 DISCUSSION

The discussion frames inference compilation as a framework combining probabilistic-program expressiveness with neural-network inference speed while retaining uncertainty handling. Experiments support posterior approximation, but the neural architecture and generative-model specification still impose important limitations.

5 DISCUSSION: Inference compilation combines universal probabilistic programming for generative modeling with deep neural networks for faster inference.The framework transforms probabilistic-program inference problems into trained neural architectures that parameterize proposal distributions.
5 DISCUSSION: The approach must address fast scalable inference, generative-model interpretability, streamed training data, and correct uncertainty representation.
5 DISCUSSION: The proposed architecture successfully learns nonlinear mappings from observations to approximate posterior parameters for the studied model family.
5 DISCUSSION: The neural architecture is only partly determined by the probabilistic program because an invariant LSTM core connects automatically configured embedding and proposal layers.The authors seek closer correspondence between the neural artifact and the program’s computational graph.
5 DISCUSSION: Domain-specific observation embeddings are hand-selected and trained end-to-end, motivating future automation of potentially pretrained embedding selection.
5 DISCUSSION: Model misspecification remains a risk: Captcha experiments required altered priors, so broad calibrated models are preferred over narrow uncalibrated ones.