Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-Specific Language

Matthew D. Hoffman, Matthew J. Johnson, Dustin Tran

Abstract

Deriving conditional and marginal distributions using conjugacy relationships can be time consuming and error prone. In this paper, we propose a strategy for automating such derivations. Unlike previous systems which focus on relationships between pairs of random variables, our system (which we call Autoconj) operates directly on Python functions that compute log-joint distribution functions. Autoconj provides support for conjugacy-exploiting algorithms in any Python embedded PPL. This paves the way for accelerating development of novel inference algorithms and structure-exploiting modeling strategies.

Introduction

In Bayesian statistics, calculating the "complete conditional distribution" of a variable—how it behaves when all other variables are fixed—is a fundamental task. When a model exhibits conjugacy, these calculations simplify into straightforward algebraic exercises. However, for complex models, manual derivation is tedious, time-consuming, and prone to errors.

While existing tools like BUGS or JAGS automate these derivations, they require models to be written in restrictive Domain-Specific Languages (DSLs) that often lack integration with the broader Python ecosystem. Autoconj addresses this by automatically identifying and exploiting conjugacy directly from standard Python/NumPy code, offering the automation of specialized tools with the flexibility of general-purpose programming.

Methods

Autoconj operates through a three-stage pipeline designed to transform raw Python code into structured mathematical representations:

  1. Tracing: The system takes a standard Python function computing a log-joint density and traces its execution to create a Directed Acyclic Graph (DAG) of mathematical primitives.
  2. Canonicalization: This core stage uses a symbolic rewrite system to transform the DAG into a "canonical form." Specifically, it expresses the log-joint as a sum of np.einsum (Einstein summation) operations. This format serves as a universal representation for multilinear polynomials defining exponential family distributions.
  3. Recognition and Extraction: The canonical patterns are matched against a library of known distributions (e.g., Normal, Gamma, Dirichlet). Automatic differentiation is then used to extract the "natural parameters" required for inference.
Figure 1: Tracing Python code into a canonical DAG representation.

Because Autoconj outputs standard Python functions, the resulting inference steps can be easily ported to different backends, such as TensorFlow, to leverage GPU acceleration.

Key Results

The effectiveness of Autoconj was evaluated across several classic probabilistic models, including Gaussian Mixture Models (GMM), Bayesian Factor Analysis, and Linear-Gaussian State-Space Models.

  • Hardware Acceleration: By translating derived inference steps into TensorFlow, Autoconj achieved an order-of-magnitude speedup on GPUs compared to single-core CPUs (e.g., 4.3s vs 62.9s for GMM iterations).
  • Superior Convergence: In Factor Analysis experiments, Coordinate Ascent Variational Inference (CAVI) derived by Autoconj converged significantly faster and more accurately than "black-box" methods like ADVI, which fail to exploit underlying model structure.
Figure 2: Convergence comparison between Autoconj-derived algorithms and black-box methods.

Discussion and Limitations

Autoconj treats conjugacy as a low-level algebraic property of the log-joint density rather than just a relationship between specific prior-likelihood pairs. By utilizing einsum as a "Swiss Army knife" for structural interactions, the system makes complex statistical structures transparent to the computer. Its "hermetic" design ensures that derived samplers can be immediately integrated with standard Python libraries like SciPy or Matplotlib.

However, some limitations remain. Autoconj's reliance on tracing makes it difficult to handle Python control flow (like if/else statements) that depends on random variable values. Additionally, the system is currently limited to a fixed library of recognized distributions. Future work aims to automate higher-level patterns, such as recursion logic for state-space models, through more sophisticated program analysis.

Summary updated

Abstract

Deriving conditional and marginal distributions using conjugacy relationships can be time consuming and error prone. In this paper, we propose a strategy for automating such derivations. Unlike previous systems which focus on relationships between pairs of random variables, our system (which we call Autoconj) operates directly on Python functions that compute log-joint distribution functions. Autoconj provides support for conjugacy-exploiting algorithms in any Python embedded PPL. This paves the way for accelerating development of novel inference algorithms and structure-exploiting modeling strategies.
BibTeX
@inproceedings{hoffman2018autoconj,
  author = {Matthew D. Hoffman and Matthew J. Johnson and Dustin Tran},
  title = {{Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-Specific Language}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HyVztvbu-B},
}
Figure