Church: a language for generative models

Abstract

We introduce Church, a universal language for describing stochastic generative processes. Church is based on the Lisp model of lambda calculus, containing a pure Lisp as its deterministic subset. The semantics of Church is defined in terms of evaluation histories and conditional distributions on such histories. Church also includes a novel language construct, the stochastic memoizer, which enables simple description of many complex non-parametric models. We illustrate language features through several examples, including: a generalized Bayes net in which parameters cluster over trials, infinite PCFGs, planning by inference, and various non-parametric clustering models. Finally, we show how to implement query on any Church program, exactly and approximately, using Monte Carlo techniques.

Minor revisions. Fixed errors in author list

Cited by in corpus (103)

• Pyro: Deep Universal Probabilistic Programming
• Automatic Differentiation Variational Inference
• A Bayesian Sampling Approach to Exploration in Reinforcement Learning
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
• Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
• A Convenient Category for Higher-Order Probability Theory
• Scaling Exact Inference for Discrete Probabilistic Programs
• TerpreT: A Probabilistic Programming Language for Program Induction
• Automated Variational Inference in Probabilistic Programming
• Denotational validation of higher-order Bayesian inference
• Approximate Bayesian Image Interpretation using Generative Probabilistic Graphics Programs
• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
• Deep Amortized Inference for Probabilistic Programs
• Programs as Black-Box Explanations
• Measure Transformer Semantics for Bayesian Machine Learning
• Formal verification of higher-order probabilistic programs
• Nonlinear System Identification: Learning while respecting physical models using a sequential Monte Carlo method
• A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
• C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching
• Black-Box Policy Search with Probabilistic Programs
• Monolingual Probabilistic Programming Using Generalized Coroutines
• Particle Gibbs with Ancestor Sampling for Probabilistic Programs
• Accelerating Inference: towards a full Language, Compiler and Hardware stack
• Gibbs Sampling in Open-Universe Stochastic Languages
• Compiling Universal Probabilistic Programming Languages with Efficient Parallel Sequential Monte Carlo Inference
• Swift: Compiled Inference for Probabilistic Programming Languages
• Driving Markov chain Monte Carlo with a dependent random stream
• Traceability of Deep Neural Networks
• Reparameterization Gradient for Non-differentiable Models
• Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
• A Credit Assignment Compiler for Joint Prediction
• Probabilistic Programming Concepts
• Learning Probabilistic Programs
• Paradoxes of Probabilistic Programming
• Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support
• Simplifying Dependent Reductions in the Polyhedral Model
• On the Pitfalls of Nested Monte Carlo
• Distribution Bisimilarity via the Power of Convex Algebras
• Learning Proposals for Probabilistic Programs with Inference Combinators
• Nested Reasoning About Autonomous Agents Using Probabilistic Programs
• Automating Involutive MCMC using Probabilistic and Differentiable Programming
• Probabilistic Neural Programs
• Higher-Order Bayesian Networks, Exactly (Extended version)
• Nesting Probabilistic Programs
• Amortized Rejection Sampling in Universal Probabilistic Programming
• An Application of Computable Distributions to the Semantics of Probabilistic Programs
• Beginner's Luck: A Language for Property-Based Generators
• A Probabilistic Dependent Type System based on Non-Deterministic Beta Reduction
• Deriving Probability Density Functions from Probabilistic Functional Programs
• Cost Analysis of Nondeterministic Probabilistic Programs
• InferSpark: Statistical Inference at Scale
• Bayesian Optimization for Probabilistic Programs
• On the computability of graphons
• Sublinear-Time Approximate MCMC Transitions for Probabilistic Programs
• Compiling Relational Database Schemata into Probabilistic Graphical Models
• Soft Constraints for Inference with Declarative Knowledge
• The Random Conditional Distribution for Higher-Order Probabilistic Inference
• DynamicPPL: Stan-like Speed for Dynamic Probabilistic Models
• Maximum a Posteriori Estimation by Search in Probabilistic Programs
• Unifying AI Algorithms with Probabilistic Programming using Implicitly Defined Representations
• PClean: Bayesian Data Cleaning at Scale with Domain-Specific Probabilistic Programming
• Probabilistic programming for birth-death models of evolution using an alive particle filter with delayed sampling
• Evaluating probabilistic programming languages for simulating quantum correlations
• Efficient Probabilistic Inference in the Quest for Physics Beyond the Standard Model
• Hamiltonian Monte Carlo for Probabilistic Programs with Discontinuities
• Probabilistic Program Abstractions
• Spreadsheet Probabilistic Programming
• Applications of Probabilistic Programming (Master's thesis, 2015)
• Joint Distributions in Probabilistic Semantics
• Herded Gibbs Sampling
• SIMPL: A DSL for Automatic Specialization of Inference Algorithms
• RankPL: A Qualitative Probabilistic Programming Language
• Slice Sampling for Probabilistic Programming
• Metric Reasoning about $\lambda$-Terms: the Affine Case (Long Version)
• Programming with Neural Surrogates of Programs
• Coarse-to-Fine Sequential Monte Carlo for Probabilistic Programs
• Probabilistic Termination by Monadic Affine Sized Typing (Long Version)
• On Higher-Order Probabilistic Subrecursion
• Static Analysis for Probabilistic Programs
• On Open-Universe Causal Reasoning
• A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories
• Encapsulating models and approximate inference programs in probabilistic modules
• From high-level inference algorithms to efficient code
• Contextual Equivalence for a Probabilistic Language with Continuous Random Variables and Recursion
• Towards Verified Stochastic Variational Inference for Probabilistic Programs
• Probabilistic Programs with Stochastic Conditioning
• Doubly Bayesian Optimization
• Meta-Learning an Inference Algorithm for Probabilistic Programs
• Running Probabilistic Programs Backwards
• Effectful Programming in Declarative Languages with an Emphasis on Non-Determinism: Applications and Formal Reasoning
• A Useful Algebraic System of Statistical Models
• Approximations in Probabilistic Programs
• Stochastic Probabilistic Programs
• Stochastically Differentiable Probabilistic Programs
• Whittemore: An embedded domain specific language for causal programming
• Semiring Programming: A Declarative Framework for Generalized Sum Product Problems
• Compositional Inference Metaprogramming with Convergence Guarantees
• Probabilities on Sentences in an Expressive Logic
• Abstractions for AI-Based User Interfaces and Systems
• Probabilistic Safety Programs
• Lazy Factored Inference for Functional Probabilistic Programming
• Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning
• Path Finding under Uncertainty through Probabilistic Inference