Learning Probabilistic Programs

Yura N. Perov, Frank D. Wood

Introduction

Traditional machine learning typically involves fitting parameters to a fixed model or finding deterministic functions. However, many real-world processes are better described as stochastic programs—executable procedures that generate samples from a distribution. This paper addresses the challenge of "learning" these generative models by representing the model itself as program text. By treating program induction as a Bayesian inference problem, the authors demonstrate that machines can automatically generate efficient sampling algorithms directly from data.

Methodology

The authors utilize Anglican, a Turing-complete, higher-order probabilistic programming language (PPL). Anglican's eval function allows the system to treat program code as data, enabling its execution during the inference process.

The learning framework consists of three primary components:

  • Generative Prior over Programs: A grammar-based prior, informed by a corpus of human-written code for common statistical distributions, guides the search toward readable and efficient algorithms.
  • MCMC-ABC (Approximate Bayesian Computation): To navigate the vast, discrete space of possible programs, the system uses ABC to compare summary statistics (mean, variance, skewness, and kurtosis) of samples from candidate programs against the observed data.
  • Hierarchical Modeling: The system learns programs that can take parameters as input (e.g., a Bernoulli sampler with parameter $\theta$), ensuring that the generated code generalizes across different settings rather than overfitting a single dataset.

Experimental Evaluation

The approach was evaluated using synthetic distributions (including Bernoulli, Poisson, Gamma, Beta, and Normal), real-world features from a credit approval dataset, and a collection of existing statistical sampling procedures. These experiments tested the system's ability to discover exact algorithms and to generate samplers for complex, unknown empirical distributions.

Results and Discussion

The results demonstrate a powerful proof-of-concept for automated algorithm discovery. The system successfully inferred exact human-standard code for simple cases like the Bernoulli distribution. For more complex distributions, the generated programs produced samples that closely matched the target statistical profiles.

Grid of distributions generated by inferred probabilistic programs across various test cases.

As illustrated in the grid above, the framework is capable of capturing a wide variety of distribution shapes. This highlights the expressiveness of the "programs as models" paradigm, which allows for representations involving loops, recursion, and complex conditional logic.

Detailed view of a sample distribution produced by an inferred program.

A key innovation presented is "probabilistic program compilation," where the system automatically generates a new, efficient standalone program that samples directly from the posterior of a more complex model. This effectively automates the creation of high-performance inference algorithms.

Conclusion

While the computational cost of searching program space remains a significant hurdle, this work shows that Bayesian program induction is a viable path toward automated programming in the probabilistic domain. Future work will focus on incremental learning, allowing the system to build and reuse a library of learned subroutines to solve increasingly complex problems, much like a human programmer.

Summary updated

Abstract

We develop a technique for generalising from data in which models are samplers represented as program text. We establish encouraging empirical results that suggest that Markov chain Monte Carlo probabilistic programming inference techniques coupled with higher-order probabilistic programming languages are now sufficiently powerful to enable successful inference of this kind in nontrivial domains. We also introduce a new notion of probabilistic program compilation and show how the same machinery might be used in the future to compile probabilistic programs for efficient reusable predictive inference.
BibTeX
@misc{perov2014learning,
  author = {Yura N. Perov and Frank D. Wood},
  title = {{Learning Probabilistic Programs}},
  year = {2014},
  eprint = {1407.2646},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.2646},
}
Figure