Skip to content

Functional probabilistic programming for PyTorch.

quivers is a Python library for typed composition of weighted relations, Markov kernels, and probabilistic programs, with a PyTorch runtime.

object Item : FinSet 100

program regression : Item -> Item [effects=[Sample, Score]]
    sample sigma  <- HalfNormal(scale=1.0)
    sample beta_0 <- Normal(loc=0.0, scale=5.0)
    sample beta_1 <- Normal(loc=0.0, scale=2.0)
    let mu = beta_0 + beta_1 * x
    observe y : Item <- Normal(loc=mu, scale=sigma)
    return y

export regression

The modeling language

QVR is the modeling language of quivers. Programs are written in .qvr files, which the compiler parses, checks, and elaborates to a typed core language, the Quivers Indexed Effect Core (QIEC), before running, fitting, or transpiling them.

The program above is a Bayesian linear regression. Each sample step draws a latent variable from its prior, let computes a value from earlier ones, and observe scores the responses y under the likelihood, with one draw for each element of the finite set Item. The name x is bound nowhere in the program, so the compiler treats it as a data input, a value the program reads and the caller gives at run time. The option [effects=[Sample, Score]] declares the effects the body may perform, and the compiler rejects a body that performs any other.

Syntax, denotation, and implementation

QVR syntax

Probabilistic programs, effects and handlers, indexed families, weighted deduction systems, and tree autoencoders share one typed source language.

Read the language reference

Denotation

Each well-typed phrase denotes a weighted relation between finite sets, a Markov kernel, or a computation with effects.

Open the semantics

Implementation

The compiler elaborates checked QVR to QIEC, runs it in PyTorch, and transpiles it to eleven other probabilistic programming languages.

Inspect the API

What composes

A morphism f : A -> B between finite sets is stored as a PyTorch tensor of shape (|A|, |B|). Its entries are weights combined by the two operations of an Algebra: \(\otimes\) combines the weights along a path, and \(\bigoplus\) combines alternative paths. Composition f >> g contracts the shared axis, so entry \((a, c)\) of the result is \(\bigoplus_b f(a, b) \otimes g(b, c)\). Composition is associative when the two operations form a semiring, in which \(\otimes\) distributes over \(\bigoplus\) (Goodman, 1999). The default Algebra, product with noisy-OR, is not distributive, so regrouping a chain of compositions can change its result.

The compiler checks domains and codomains before any tensor is evaluated: f >> g requires the codomain of f to equal the domain of g. Beyond sequential composition, f @ g runs two morphisms side by side on a pair of inputs, change_base applies an entrywise map or a row normalization to a morphism's weights, and a program's marginalize step sums a discrete latent variable out of the likelihood. Probabilistic programs, weighted deduction systems declared with deduction (for instance a CKY parser), and tree autoencoders declared with signature elaborate to the same core language.

The library also provides:

Architecture

Solid arrows are computation steps, and dotted arrows are interpretation.

flowchart LR
    subgraph AUTHOR["1 · Author"]
        direction TB
        QVR["QVR source<br/><small>programs · effects · handlers</small>"]
        PY["Python API<br/><small>morphisms · algebras · composition</small>"]
    end

    subgraph CHECK["2 · Parse, elaborate, and check"]
        direction TB
        AST["Source AST"] -->|"elaborate + check"| QIEC["Checked QIEC module<br/><small>indexed types · effect rows</small>"]
    end

    subgraph USE["3 · Use the checked program"]
        direction TB
        RUN["Execute + infer<br/><small>SVI · HMC · NUTS</small>"]
        INSPECT["Inspect<br/><small>analysis · diagnostics · LSP</small>"]
        TARGET["Translate<br/><small>11 target languages</small>"]
    end

    subgraph SEM["4 · Denotation"]
        FOUNDATION["Weighted relations · Markov kernels<br/><small>computations with effects</small>"]
    end

    QVR -->|"parse"| AST
    QIEC -->|"run"| RUN
    QIEC -->|"analyze"| INSPECT
    QIEC -->|"lower"| TARGET
    QIEC -. interpret .-> FOUNDATION
    PY -->|"construct"| FOUNDATION

    class QVR,PY qv-input
    class AST,QIEC qv-checked
    class RUN,INSPECT,TARGET qv-output
    class FOUNDATION qv-foundation

Foundations

The denotational semantics interprets each well-typed QVR phrase as a weighted relation, a Markov kernel, or a computation with effects. It draws on enriched category theory (Kelly, 1982), categorical treatments of probability (Giry, 1982; Fritz, 2020), and the monadic semantics of effects (Moggi, 1991). The inference algorithms follow the standard sources for SVI (Hoffman et al., 2013), HMC (Neal, 2011), and NUTS (Hoffman and Gelman, 2014).

Cited sources

Joshua Goodman. Semiring Parsing. Computational Linguistics, 25(4):573–606, 1999. URL: https://aclanthology.org/J99-4004/.

Matthew D. Hoffman and Andrew Gelman. The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo. Journal of Machine Learning Research, 15(47):1593–1623, 2014. URL: https://www.jmlr.org/papers/v15/hoffman14a.html.

G. M. Kelly. Basic Concepts of Enriched Category Theory. Cambridge University Press, 1982. Reprinted in Reprints in Theory and Applications of Categories 10 (2005), 1–136. URL: https://www.tac.mta.ca/tac/reprints/articles/10/tr10abs.html.

Michèle Giry. A Categorical Approach to Probability Theory. In B. Banaschewski, editor, Categorical Aspects of Topology and Analysis, volume 915 of Lecture Notes in Mathematics, pages 68–85. Springer, 1982. URL: https://link.springer.com/chapter/10.1007/BFb0092872, doi:10.1007/BFb0092872.

Tobias Fritz. A Synthetic Approach to Markov Kernels, Conditional Independence and Theorems on Sufficient Statistics. Advances in Mathematics, 370:107239, 2020. URL: https://www.sciencedirect.com/science/article/pii/S0001870820302656, doi:10.1016/j.aim.2020.107239.

Eugenio Moggi. Notions of Computation and Monads. Information and Computation, 93(1):55–92, 1991. URL: https://www.sciencedirect.com/science/article/pii/0890540191900524, doi:10.1016/0890-5401(91)90052-4.

Matthew D. Hoffman, David M. Blei, Chong Wang, and John Paisley. Stochastic Variational Inference. Journal of Machine Learning Research, 14(40):1303–1347, 2013. URL: https://www.jmlr.org/papers/v14/hoffman13a.html.

Radford M. Neal. MCMC Using Hamiltonian Dynamics. In Steve Brooks, Andrew Gelman, Galin L. Jones, and Xiao-Li Meng, editors, Handbook of Markov Chain Monte Carlo, chapter 5, pages 113–162. Chapman and Hall/CRC, 2011. URL: https://doi.org/10.1201/b10905-6, doi:10.1201/b10905-6.