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
Fit a model¶
Install quivers, write a regression in QVR, fit it with variational inference, and read the posterior.
Learn QVR¶
From a first regression through hierarchical models, mixtures, effect handlers, weighted deduction, and transpilation.
Read the semantics¶
The denotation of each well-typed QVR phrase and the conditions under which its laws hold.
Read the source¶
The subpackages of the library, what each provides, and how they depend on one another.
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.
Denotation¶
Each well-typed phrase denotes a weighted relation between finite sets, a Markov kernel, or a computation with effects.
Implementation¶
The compiler elaborates checked QVR to QIEC, runs it in PyTorch, and transpiles it to eleven other probabilistic programming languages.
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:
- Distribution families: more than fifty, discrete and continuous
- Stochastic variational inference (SVI): automatic guides and several objectives
- Hamiltonian Monte Carlo (HMC), with the No-U-Turn Sampler (NUTS) (Hoffman and Gelman, 2014)
- Diagnostics: convergence statistics, posterior predictive checks, and model comparison through ArviZ
- Formulas: mixed-effects regression from R-style formulas
- Static analysis of program structure, including plate diagrams
- Interactive tools: a REPL, a Jupyter kernel, and a language server
- Transpilation to Stan, PyMC, NumPyro, Pyro, Edward2, Turing, Gen, Church, WebPPL, BUGS, and JAGS. A target that cannot express a feature the program uses reports it at the feature's source location.
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.