Venture: a higher-order probabilistic programming platform with programmable inference

Vikash Mansinghka; Daniel Selsam; Yura Perov

Source-linked AI summary

Venture: a higher-order probabilistic programming platform with programmable inference

Vikash Mansinghka, Daniel Selsam, Yura Perov

arXiv:1404.0099v1Apr 1, 2014cs.AIcs.PLstat.COstat.ML

TL;DR

Probabilistic programming needs systems that reduce the difficulty of building expressive models while supporting practical inference. Venture addresses this with a higher-order probabilistic language, programmable inference, execution-trace abstractions, and stochastic regeneration, achieving linear rather than quadratic scaling in stated cases while retaining broad inference support.

Problem
Existing probabilistic programming systems make expressive probabilistic models and practical inference difficult to design, implement, and scale.
Method
Venture combines a Turing-complete higher-order modeling language with programmable inference built on the SPI, PETs, scaffolds, and stochastic regeneration.
Results
Venture’s standard MCMC scales linearly with dataset size in cases where previous inference architectures scale quadratically, and supports multiple general-purpose inference strategies.
Takeaways & Limitations
Venture provides a platform spanning expressive probabilistic models, custom inference strategies, likelihood-free procedures, and external inference components.
Takeaways & Limitations
The paper identifies developing a specification language and cost model for controlling automatic inference within runtime and accuracy constraints as an important challenge.

Abstract

from arXiv · show

We describe Venture, an interactive virtual machine for probabilistic programming that aims to be sufficiently expressive, extensible, and efficient for general-purpose use. Like Church, probabilistic models and inference problems in Venture are specified via a Turing-complete, higher-order probabilistic language descended from Lisp. Unlike Church, Venture also provides a compositional language for custom inference strategies built out of scalable exact and approximate techniques. We also describe four key aspects of Venture's implementation that build on ideas from probabilistic graphical models. First, we describe the stochastic procedure interface (SPI) that specifies and encapsulates primitive random variables. The SPI supports custom control flow, higher-order probabilistic procedures, partially exchangeable sequences and ``likelihood-free'' stochastic simulators. It also supports external models that do inference over latent variables hidden from Venture. Second, we describe probabilistic execution traces (PETs), which represent execution histories of Venture programs. PETs capture conditional dependencies, existential dependencies and exchangeable coupling. Third, we describe partitions of execution histories called scaffolds that factor global inference problems into coherent sub-problems. Finally, we describe a family of stochastic regeneration algorithms for efficiently modifying PET fragments contained within scaffolds. Stochastic regeneration linear runtime scaling in cases where many previous approaches scaled quadratically. We show how to use stochastic regeneration and the SPI to implement general-purpose inference strategies such as Metropolis-Hastings, Gibbs sampling, and blocked proposals based on particle Markov chain Monte Carlo and mean-field variational inference techniques.

1. Introduction

Probabilistic programming seeks to reduce the cost of designing and implementing probabilistic models and inference, but existing systems trade expressiveness against efficiency. Venture combines a higher-order probabilistic language with programmable inference and implementation mechanisms intended to support expressive models at improved scale.

Probabilistic modeling and approximate Bayesian inference are powerful across fields, but their models and inference schemes can be difficult and time-consuming to design, analyze, implement, and debug.
Existing probabilistic programming systems commonly restrict expressiveness for efficiency or emphasize expressive models whose specialized inference is difficult to engineer for deployment.
Venture is an interactive, Turing-complete, higher-order platform with languages for probabilistic models, inference problems, and custom inference strategies.
Venture’s stochastic procedure interface supports custom control flow, higher-order procedures, exchangeable sequences, likelihood-free primitives, and external models with hidden latent variables.
Scaffolds factor probabilistic execution traces into coherent local inference problems, while stochastic regeneration modifies relevant trace fragments without visiting conditionally independent choices.
Stochastic regeneration supports single-site and composite Metropolis-Hastings, Gibbs sampling, and blocked proposals combining sequential Monte Carlo and variational techniques.

2. The Venture Language

The Venture language separates modeling, conditioning, inference, and read-out through interactive instructions. Programs construct probabilistic models with ASSUME and OBSERVE, evolve execution traces with INFER, and obtain predictions with PREDICT.

Venture programs combine modeling and inference instructions in interactive sessions that specify a probabilistic model, constraints, and prediction requests.
ASSUME binds simulated model expressions to names, while OBSERVE adds constraints that expressions yield specified literal values.
PREDICT samples an expression from the current execution distribution, which converges toward the distribution conditioned on observations as inference increases.
Its default Markov chain uses random-scan single-site Metropolis-Hastings to resimulate choices conditioned on the remaining trace and accept or reject changes.
INFER incorporates observations and evolves the distribution over execution traces using a user-specified inference strategy.
Venture also provides SAMPLE and FORCE for simulation, initialization, and debugging, plus FORGET for removing OBSERVE or PREDICT instructions.

2.2 Modeling Expressions

Venture modeling expressions define stochastic generative processes and support higher-order, conditional, and dynamically scoped computation. Inference scopes and blocks annotate trace fragments so inference programs can target structured subsets of random choices.

The hypothesis space of a Venture program consists of all executions of its modeling expressions, which define a stochastic generative process.
Venture’s s-expression syntax is called Venchurch, while the desugared JSON parse-tree language is called Venture.
Venture expressions include literals, combinations, quoted expressions, lambda expressions, conditionals, and inference-scope annotations.
The scope include form tags random choices required to simulate an expression with a named scope and block.
Scopes and blocks may be produced by random choices, allowing model variables to control how other choices are allocated for inference.
The default scope contains every random choice, whereas the latents scope contains latent choices hidden from Venture and controls external inference frequency.

2.4 Inference Expressions

Venture inference expressions specify transition operators over selected trace choices, with primitive and compositional forms implemented through stochastic regeneration. They support exact, approximate, and hybrid inference strategies while preserving the conditioned distribution.

Inference expressions evolve the trace distribution, unlike instructions that extend models, add data, or initiate inference using a valid transition operator.
Venture’s primitive transition operators leave the conditioned distribution invariant and act on choices selected by scopes and blocks.
Metropolis-Hastings proposes and accepts or rejects resimulated or custom-kernel values for selected choices.
Rejection sampling produces exact conditioned samples but can be computationally intractable, while particle Gibbs uses conditional sequential Monte Carlo to approximate conditioned proposals.
Mean-field inference performs stochastic-gradient optimization of a partial approximation before making a Metropolis-Hastings proposal.
Cycle and mixture composition rules combine transition operators sequentially or according to mixing weights, enabling standard and novel hybrid strategies.

2.5 Values

Venture values extend Scheme’s scalar and symbolic types with collections, statistical datatypes, and stochastic procedures that support built-in, user-added, and compound probabilistic operations.

Venture includes Scheme-like scalar and symbolic types alongside collections and probability- and statistics-oriented datatypes.
Numbers are floating-point-like scalar values, while atoms are unordered discrete items generated by categorical, Dirichlet, and Pitman-Yor processes.
Symbols represent values such as lambda argument names, ASSUME names, and results of evaluating quote.
Supporting multiple simultaneous particles requires stochastic procedures to clone or emulate cloning their auxiliary state, which may be infeasible for distributed external inference systems.
Collections include vectors and maps with O(1) random access or O(1) amortized random access, respectively.
Stochastic procedures comprise standard-library components and procedures created by lambda or other stochastic procedures.

2.6 Automatic inference versus inference programming

Venture combines automatic access to standard inference algorithms with a compositional language for programming custom inference strategies. The paper presents this as a broader design perspective whose practical sufficiency remains unsettled.

Automatic inference versus inference programming: Single-site Metropolis-Hastings and Gibbs sampling can be invoked with one instruction, while global sequential Monte Carlo and mean-field algorithms are also straightforward to implement.
Automatic inference versus inference programming: Venture treats inference strategies as structured, compositional inference programs operating on model programs, an approach the authors describe as new to Venture.
Automatic inference versus inference programming: Standard inference algorithms can correspond to primitive inference-programming operations or templates that depend on features of the model program.
Automatic inference versus inference programming: A contrasting mainstream view treats inference algorithms as monolithic solvers for problem classes with particular structure.
Automatic inference versus inference programming: Whether monolithic mechanisms suffice in practice or underestimate interactions among inference, modeling, and problem specification remains unresolved.

2.7 Procedural and Declarative Interpretations

Venture programs support both procedural and declarative interpretations. Increasing inference within each instruction makes these interpretations converge toward sequential Bayesian semantics.

Procedural interpretation: A procedural reading treats Venture code as a generative process that samples hypotheses, checks constraints, and invokes specified inference algorithms.
Procedural interpretation: Reordering inference instructions can change runtime and the distribution of outputs under the procedural interpretation.
Declarative interpretation: Declarative readings define meaning through distributions over execution traces, the joint values of PREDICTs, or the interactive program state.
Convergence of interpretations: As inference per INFER instruction increases, the procedural and declarative interpretations coalesce into sequential Bayesian reasoning.
Program semantics: Venture combines sampling operations, constraint-building operations, and inference operations that move distributions toward conditioner-induced conditional distributions.

2.8 Markov chain and sequential Monte Carlo architectures

The current Venture implementation uses one probabilistic execution trace per virtual machine and modifies it with invariant-preserving transition operators. Sequential Monte Carlo architectures with multiple weighted traces are also possible, though they impose cloning requirements and can produce dependent outputs across repeated inference.

Markov chain architecture: Each virtual machine maintains one probabilistic execution trace initialized from ASSUME and OBSERVE instructions and modified during inference by invariant-preserving transitions.
Sequential Monte Carlo architecture: Sequential Monte Carlo architectures can instead use weighted collections of traces and are described as straightforward to implement.
Sequential Monte Carlo architecture: An SMC design would initialize multiple traces, attach observation likelihood weights, read PREDICT values from an active trace, and resample traces with INFER.
Sampling behavior: Separate virtual machines yield independent samples, but repeated inference and prediction within one program generally produces dependent outputs unless rejection sampling is used.

2.9 Examples

Venture examples show how programmable inference supports sequential HMM inference, mixture-model strategies, and probabilistic program synthesis. These examples also illustrate improved scaling through selective resimulation and identify advances needed for larger symbolic programs.

Hidden Markov models: Sequentialized Metropolis-Hastings inference for hidden Markov models scales linearly with sequence length rather than quadratically.Interleaving inference with observations mitigates strong conditional dependencies in the posterior.
Hidden Markov models: Venture composes Metropolis-Hastings, particle Gibbs, and particle filtering operations with user-specified transition counts and particle numbers.Examples include ten hyperparameter MH transitions per five approximate Gibbs transitions using 30 particles, and 30-particle particle Gibbs variants.
Dirichlet process mixtures: For Dirichlet process mixtures of Gaussians, Venture supports separate inference schedules for hyperparameters, component parameters, and cluster assignments.A cycle can apply one hyperparameter transition, five parameter transitions, and five cluster reassignments, with random choices of targets.
Inverse interpretation: Inverse interpretation uses one Venture program to generate expressions and Turing-complete inference to explore expressions satisfying constraints on their evaluated results.Venture can associate program-source portions and induced executions with custom inference strategies, extending beyond rejection sampling and single-site Metropolis-Hastings.
Inverse interpretation: References improve asymptotic scaling by resimulating only execution portions that depend on changed grammar source code.A naive evaluator would not provide this selective resimulation property.
Inverse interpretation: Scaling inverse interpretation to larger symbolic expressions and small programs will require broader system efficiency, inference-operator, and prior-structure advances.The paper specifically mentions Hamiltonian Monte Carlo for continuous parameters and inference-friendly expression priors.

3. Stochastic Procedures

Venture’s stochastic procedure interface encapsulates primitive random behavior while supporting higher-order procedures, exchangeable coupling, likelihood-free simulation, and external latent-variable inference.

Interface capabilities: The stochastic procedure interface extends ordinary random-variable representations to higher-order procedures, coupled applications, likelihood-free simulators, and externally hidden latent variables.These capabilities let primitives participate in dynamic control flow, specialized representations, and custom inference while remaining integrated with Venture.
Primitive stochastic procedures: Primitive stochastic procedures can simulate outputs, report log densities, maintain exchangeable auxiliary state, and provide custom proposal kernels with Metropolis-Hastings contributions.Auxiliary state may track sufficient statistics rather than every sampled value, enabling efficient updates for conjugate or exchangeably coupled models.
Foreign inference interface: The SPI contract preserves coherent inference while allowing external inference systems to manage latent variables that Venture does not represent directly.This interface also permits primitives to dynamically create and destroy hidden latent variables and run custom inference over them.
Simulation requests: A stochastic procedure is defined through request and output PSPs together with a latent-variable simulator that responds to latent simulation requests.Exposed requests provide values Venture must compute, whereas latent requests identify variables simulated internally by the procedure.
Foreign inference interface: Encapsulated latent inference can exploit specialized algorithms such as forwards-filtering backwards-sampling for hidden HMM states.Venture integrates these black-box procedures through an Arbitrary Ergodic Kernel that it may invoke during inference.
Efficiency: Sufficient-statistic tracking lets a primitive support rapid Metropolis-Hastings proposals without visiting every observation node in a large dataset.The paper contrasts this with a naive generic scheme that might inspect all one billion observation nodes for each acceptance-ratio computation.

4. Probabilistic Execution Traces

Probabilistic execution traces represent Venture executions as dependency graphs enriched with auxiliary state and metadata for existential dependence and exchangeable coupling. Their family structure supports dynamic program behavior, while examples connect traces to Bayesian networks, stochastic memoization, and constraint handling.

PET foundations: PETs extend graphical-model representations to Turing-complete, higher-order Venture programs and support recursive construction and destruction during evaluation.They capture dependencies that arise beyond fixed graphical-model structure.
PET structure: A PET contains a directed dependency graph, stochastic-procedure auxiliary state, the Venture program, and metadata for existential dependencies and exchangeable coupling.Node values remain fixed during an execution, while auxiliary state may mutate as samples are incorporated or removed.
Nodes and edges: PETs include constant, lookup, request, and output nodes corresponding to environments, evaluations, symbol resolution, and stochastic-procedure applications.Edges encode lookup, operator, operand, requester, and exposed-simulation-request relationships.
Nodes and edges: PET edges connect lookup targets, operators, operands, request-output pairs, and SP families to the applications that request them.These edges make the execution’s conditional structure explicit for inference operations.
Families and dependence: Trace families are associated with Venture directives or unique exposed requests, and each family’s structure depends on its expression rather than its random choices.Conditional simulation changes graph topology only through which families are present and how existential dependencies select them.
Examples: A coarsened PET preserves the conditional-dependence and independence information of a Bayesian network, with each Venture family corresponding to a network node.The Bayesian-network example illustrates how PET execution histories represent the computation needed to simulate nodes from their parents.
Examples: Stochastic memoization creates overlapping requests because repeated procedure applications may reuse previously sampled values under a Pitman-Yor process.The corresponding PET depicts a typical execution of a stochastically memoized Bernoulli procedure.
Constraint handling: Venture’s constraint mechanism is not a general inversion procedure: finding an execution giving an observed output positive probability is intractable in general.The system instead recursively searches for a constrainable stochastic-procedure application and may re-evaluate the program after failure.

5. Partitioning Traces into Scaffolds for Scalable, Incremental Inference

Venture uses probabilistic execution traces and scaffolds to isolate coherent local inference problems despite conditional, existential, and exchangeable dependencies. Scaffolds identify which nodes may change or disappear, which must be conditioned on, and which can be ignored.

Probabilistic execution traces represent conditional dependencies, existential dependencies, and exchangeable coupling in Turing-complete probabilistic programs.
A scaffold partitions a trace into nodes that may change, nodes that may disappear, absorbing nodes, parents, and nodes never needing visitation.
The partition avoids invalid proposals caused by deterministic dependencies, branch changes, or likelihood-free procedures whose densities cannot be evaluated directly.
Scaffolds define executions reachable by resimulation while preserving a common conditioning set, enabling high-dimensional global inference to decompose into overlapping lower-dimensional subproblems.
Venture constructs scaffolds by walking downstream from principal nodes to absorbable stochastic procedures, then recursively identifying and removing the brush.

6. Stochastic Regeneration Algorithms for Scaffolds

Stochastic regeneration coherently detaches and rebuilds PET fragments within a scaffold, preserving the information needed for inference and restoration. Its runtime depends on the affected fragment rather than the entire trace.

Stochastic regeneration modifies a trace using a valid scaffold and supports parameterized implementations of many stochastic inference strategies.
Runtime scales with scaffold and brush size rather than total PET size when constituent simulation and density evaluation are constant.
Detach stores scaffold-fragment choices in an omegaDB, while regeneration reconstructs the PET by restoring or resimulating nodes in parent-before-child order.
Detach and regeneration use opposite traversal orders so partially exchangeable procedures receive absorbing-node probabilities consistent with the proposed trace.
Regeneration tracks weights while extracting, detaching, attaching, and incorporating nodes, including recursive handling of parents, requests, and exchangeable stochastic-procedure parents.

7. General-purpose Inference Strategies via Stochastic Regeneration

Venture uses stochastic regeneration as a common substrate for invariant inference operators over probabilistic execution traces. This supports compositional Metropolis-Hastings, Gibbs, particle-based, and variational strategies with scalable local updates.

Venture implements inference strategies as PET transition operators that preserve the posterior distribution while constraining modifications to a scaffold.
Exchangeable procedure probabilities are invariant to complete-trace traversal order, but probabilities of arbitrary trace fragments may depend on ordering.
Auxiliary-variable constructions justify state-dependent random kernel selection and enable compositional analysis of customized Metropolis-Hastings operators.
O(N) runtime supports an inference sweep of N single-site Metropolis-Hastings transitions on sparse PETs, versus O(N^2) for transformational compilers.
Stochastic regeneration can learn local variational approximations using Monte Carlo gradient estimates and wrap the resulting proposal in Metropolis-Hastings.

8. Particle-based Inference: Enumerative Gibbs and Particle Markov chain Monte Carlo

Venture uses particle-based constructions to build flexible inference operators over execution traces, including Gibbs-style, Metropolis-Hastings, and particle MCMC schemes.

Particle-based inference: Particle-based inference represents alternative trace states as weighted particles and provides common machinery for handling dependent random choices.The same framework supports Gibbs sampling, particle Markov chain Monte Carlo, and related techniques.
Implementation tradeoffs: Particle methods support both in-place mutation and simultaneous particle representations, enabling time-space tradeoffs and parallel particle evolution.The simultaneous representation is needed to recover asymptotic scaling competitive with custom sequential Monte Carlo techniques.
State-dependent mixtures: Venture can combine stochastic kernel selection with base kernels while preserving detailed balance under a symmetry condition.The selected kernel must be reachable in both directions with nonzero probability, and each component kernel must satisfy detailed balance.
State-dependent mixtures: MixMH selects a kernel from a state-dependent sampler and applies an acceptance factor that accounts for the reverse-state selection probability.The construction defines λ_i(ρ →ξ) = α_i(ρ →ξ)P_f(f(ξ) = i).
Particle operators: The MHn operator generates a multiset of weighted particles from a seed kernel and then samples from that multiset.This pattern is treated as a reusable composition in the inference language.
Particle MCMC: PGibbs approximates blocked Gibbs sampling over arbitrary scaffolds, while cycles and mixtures with other kernels recover particle MCMC schemes and novel algorithms.Conditional SMC can also generate particle sets by propagating through grouped scaffold regions.

9. Conditional Independence and Parallelizing Transitions

Venture analyzes execution-trace dependencies to identify when transitions can be simulated in parallel, despite dynamic read and write sets in probabilistic programs.

Trace dependencies: PETs expose conditional independence relationships that can support program analyses and justify parallelized kernel composition operators.These relationships also reveal parallelism distinct from particle-level parallelism.
Trace dependencies: Unlike a Bayesian-network Markov blanket, a scaffold factors trace log density but does not by itself permit parallel transition simulation.Venture therefore formulates a separate locality notion for PET transitions.
Dynamic dependencies: Dynamic PET dependencies complicate parallelization because future parents and mutable stochastic-procedure auxiliary states are unknown before simulation.The relevant parent and state sets depend on the proposed regenerated trace.
Parallel transitions: Two temporally overlapping proposals can be simulated simultaneously when neither proposal reads a node whose value differs across the other proposal’s traces.This condition prevents the transitions from clashing.
Parallel transitions: Probabilistic programmers can schedule transitions simultaneously when the proposals satisfy the non-clashing condition, and speculative parallel simulation may also be useful in some cases.Approximate transitions can serve as proposals for later serial transitions when dependency clashes are limited or ignored.
Open issues: Predicting parallelizable transitions in advance may require static analysis or language and stochastic-procedure hints about dependency composition.The paper identifies evaluating these approaches as future work.

10. Related Work

Venture is positioned relative to probabilistic programming systems by combining broad language expressiveness with compositional inference and multiple exact and approximate techniques.

Church-like systems: Earlier Church-like systems used ad hoc scope control or program-analysis techniques, but some retained quadratic scaling, runtime overhead, or constraints on generality.These approaches also differed in absolute efficiency and runtime predictability.
Related systems: BLOG represents dependencies whose existence depends on other variable values through infinite contingent Bayesian networks.The paper presents BLOG as a relevant open-universe probabilistic programming system.
Related systems: Venture is a stand-alone virtual machine, whereas Figaro is an embedded Scala library whose models are represented as Scala data objects.IBAL has a similar stochastic-choice interface but inference restrictions analogous to Infer.NET.
Inference techniques: Venture’s hybrid inference primitives generalize earlier proposals for global mean-field inference and particle Gibbs in probabilistic programs.Those earlier approaches used repeated program resimulation for stochastic optimization or conditional sequential Monte Carlo.
Venture’s position: The authors identify Venture as the first platform, to their knowledge, with a compositional inference language containing multiple computationally universal primitives.They also describe support for higher-order probabilistic procedures and integration of Markov chain, sequential Monte Carlo, and variational inference techniques.

11. Discussion

Venture combines expressive probabilistic modeling with programmable inference, while the authors identify substantial open questions about coverage, performance, language expressiveness, and the scope of automation.

Contributions: Venture combines a stochastic procedure interface, probabilistic execution traces, scaffolds, and stochastic regeneration to support programmable inference.These components support higher-order, likelihood-free, exchangeably coupled, and externally inferred procedures while decomposing inference into subproblems.
Open limitations: The coverage of Venture across models, inference strategies, and end-to-end problems remains to be carefully assessed.The authors also question whether its current inference strategies suffice across Bayesian data analysis, large-scale machine learning, and real-time robotics.
Open limitations: Venture’s performance surface and the principles for comparing accuracy, scaling, memory, and runtime remain largely uncharacterized.The authors call for rigorous empirical assessments and mathematically rigorous cost models before comparative benchmarking.
Inference programming: The inference programming language lacks iteration, reusable procedural abstraction, dynamic expression evaluation, and compound implementations of inference primitives.The authors propose restoring fuller Lisp expressiveness and extending the language to capture interactions between modeling and approximate inference.
Future directions: Future extensions include reusable inference procedures, probabilistic programs that optimize inference, and specifications spanning automatic to highly customized inference.The paper identifies suitable specification languages and cost models as important challenges for controlling automatic inference.
Conclusion: The authors do not know whether one probabilistic language can attain Lisp, Java, or Python’s flexibility, extensibility, and efficiency amid inference complexity.They nevertheless position Venture as a step toward a computationally universal platform suitable for general-purpose use across several fields.