Skip to content

Concepts

1. An object names the possible values

An object is the type of a value. The finite objects are instances of FinSet, a named finite set whose elements index one axis of a tensor. Continuous objects, such as the real line or the probability simplex, are continuous spaces. A morphism f : A -> B relates each element of its domain A to each element of its codomain B. Between finite sets it is stored as a tensor of shape (|A|, |B|) that holds one weight for each pair.

The examples below use Weather = {dry, rainy}, Route = {walk, bus}, and Arrival = {on_time, late}, with element 0 standing for the first label of each set. Two morphisms give conditional probabilities:

f walk bus
dry 0.8 0.2
rainy 0.3 0.7
g on_time late
walk 0.9 0.1
bus 0.6 0.4

Objects combine. Weather * Route is the Cartesian product, whose elements are pairs, and Weather + Route is the disjoint union, whose elements are tagged values of either set. Both have four elements, and both are written the same way in Python and in QVR. In Python, the one-element set quivers.Unit is the domain of a morphism that takes no varying input. Core types gives the tensor layout of each.

2. Composition eliminates an intermediate value

f >> g composes f : A -> B with g : B -> C into a morphism A -> C by summing out the shared object B. Mathematics writes the same composite as \(g \circ f\). When the weights are probabilities and each row of f and g sums to one, f and g are Markov kernels between finite sets, and f >> g is their composite: the matrix product, which gives the probability of each arrival given the weather with the route summed out.

import torch
from quivers import FinSet, observed
from quivers.core.algebras import MARKOV

Weather = FinSet(name="Weather", cardinality=2)
Route = FinSet(name="Route", cardinality=2)
Arrival = FinSet(name="Arrival", cardinality=2)

f = observed(Weather, Route,
             torch.tensor([[0.8, 0.2], [0.3, 0.7]]), algebra=MARKOV)
g = observed(Route, Arrival,
             torch.tensor([[0.9, 0.1], [0.6, 0.4]]), algebra=MARKOV)
result = (f >> g).tensor
assert torch.allclose(result, torch.tensor([[0.84, 0.16], [0.69, 0.31]]))

observed wraps a fixed tensor as a morphism, and MARKOV selects ordinary multiplication and addition. observed does not check that the rows sum to one. The stochastic interface provides morphisms whose rows are normalized by construction.

3. An algebra chooses how weights combine

Composition computes

\[ (f \mathbin{>>} g)(a, c) = \bigoplus_{b \in B} f(a, b) \otimes g(b, c), \]

where \(a\) is an element of A, \(c\) an element of C, \(\otimes\) the operation that combines the weights along the path through \(b\), and \(\bigoplus\) the operation that combines the paths. An Algebra fixes the two operations. The built-in ones include these:

Algebra \(\otimes\) \(\bigoplus\) Structure and typical use
BOOLEAN AND OR Boolean semiring, for reachability
MARKOV multiplication sum sum-product semiring, for probabilities
TROPICAL addition minimum tropical semiring, for shortest paths
LOG_PROB addition log-sum-exp log semiring, for probabilities in log space
PRODUCT_FUZZY multiplication noisy-OR product t-norm with the probabilistic sum

The first four are semirings, as in semiring parsing (Goodman, 1999; Mohri, 2002). PRODUCT_FUZZY pairs the product t-norm with its dual t-conorm, the probabilistic sum (Klement et al., 2000). Over many arguments the probabilistic sum is the noisy-OR, \(1 - \prod_i (1 - x_i)\), the probability that at least one of several independent causes occurs (Pearl, 1988). The algebra catalog lists every built-in Algebra.

PRODUCT_FUZZY is the default. Composing f and g without algebra=MARKOV gives \(1 - (1 - 0.8 \times 0.1)(1 - 0.2 \times 0.4) = 0.1536\) for late arrival on a dry day, where MARKOV gives \(0.16\). The noisy-OR treats walking and taking the bus as independent causes of lateness, while the sum treats them as exclusive alternatives.

Composition is associative, so that (a >> b) >> c and a >> (b >> c) agree, when the two operations form a semiring, in which \(\otimes\) distributes over \(\bigoplus\). Product does not distribute over the probabilistic sum, so under the default the two groupings can differ:

S = FinSet(name="S", cardinality=2)
a = observed(S, S, torch.tensor([[0.9, 0.5], [0.2, 0.7]]))
b = observed(S, S, torch.tensor([[0.6, 0.8], [0.4, 0.3]]))
c = observed(S, S, torch.tensor([[0.5, 0.1], [0.9, 0.6]]))
left = ((a >> b) >> c).tensor
right = (a >> (b >> c)).tensor
assert not torch.allclose(left, right)

Semirings, t-norms, and change of base states which laws each Algebra satisfies.

4. A probabilistic program describes how data could arise

A QVR program is a generative model: its steps say how the observed values could have been produced (Goodman and Stuhlmüller, 2014). Each step is one of the following (step reference):

  • sample draws a latent variable from a distribution
  • let computes a value from earlier ones without drawing
  • observe scores an observed value under a distribution, which contributes the likelihood
  • score adds an arbitrary log weight
  • marginalize sums a discrete latent variable out of the likelihood by enumerating its values

Running a program forward draws each variable after the variables it depends on, which is ancestral sampling (Koller and Friedman, 2009). Fitting it approximates the posterior over the latent variables given the observed values, by variational inference or by Markov chain Monte Carlo. The quickstart fits a regression, and Your first model works through the same model in detail.

5. A distribution is more than one sample

A morphism between continuous spaces is a conditional distribution family, such as ConditionalNormal, which assigns a distribution over its codomain to each input. It offers two different operations. rsample draws values, with gradients through the draw by the reparameterization trick where the family allows it (Kingma and Welling, 2014). log_prob evaluates the log probability mass or log density of a given value.

The two operations behave differently under composition. rsample on f >> g draws an intermediate value from f and then a value from g. log_prob sums out a discrete intermediate exactly. For a continuous random intermediate it does not compute the marginal density, which would require an integral. It scores the composite along a reference path instead, which agrees with the marginal density when the intermediate is deterministic. Continuous spaces gives the interface, and Implementation correspondence and limits states what each operation computes.

6. Monads and handlers describe how computations continue

A monad is an interface for sequencing computations that produce values in some context, here a distribution over values (Moggi, 1991; Wadler, 1992). Its return wraps a value as a computation, and its bind runs a computation and passes each possible result to the next step. The steps of a program are sequenced by bind. Kleisli composition is the composition of functions that return computations. For the Giry monad, which sends a space to the probability distributions on it, those functions are the Markov kernels (Giry, 1982). The library also implements these interfaces in Python (monads, categorical structures).

An effect is an operation a computation requests, such as drawing a sample, and a handler answers the request (Plotkin and Pretnar, 2009; Bauer and Pretnar, 2015). One handler may draw a fresh value for a sampling request, another may return an observed value, and a third may replay a value recorded earlier. The handler receives the continuation, the rest of the computation waiting for the value. QVR declares effects and handlers directly (Effects and handlers), and the effects guide gives the Python interface.

7. Reading the notation and finding the next explanation

Notation or term Meaning Defined in
\(f : A \to B\) A morphism with domain \(A\) and codomain \(B\) Morphisms
\(\mathcal V\) The weights of an Algebra, with its operations \(\otimes\) and \(\bigoplus\) Setting
\(\mathcal C(A, B)\), hom-set The morphisms from \(A\) to \(B\) in a category \(\mathcal C\) Categorical structures
Functor A map between categories that preserves identities and composition Functors
Natural transformation A family of morphisms between two functors that commutes with every morphism Categorical structures
\(\llbracket e \rrbracket_\rho\), denotation The meaning of expression \(e\) when its free names take the values that the environment \(\rho\) gives Setting
\(\Gamma \vdash e : \tau\), typing judgment Under the typing context \(\Gamma\), expression \(e\) has type \(\tau\) Typing
Effect row The effects a computation may still perform Effects and handlers
Guide The family of distributions that variational inference fits to the posterior SVI
Plate Conditionally independent draws, one for each element of an object Probabilistic Programs

Cited sources

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

Mehryar Mohri. Semiring Frameworks and Algorithms for Shortest-Distance Problems. Journal of Automata, Languages and Combinatorics, 7(3):321–350, 2002. doi:10.25596/jalc-2002-321.

Erich Peter Klement, Radko Mesiar, and Endre Pap. Triangular Norms. Trends in Logic. Springer, 2000. doi:10.1007/978-94-015-9540-7.

Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988. doi:10.1016/C2009-0-27609-4.

Noah D. Goodman and Andreas Stuhlmüller. The Design and Implementation of Probabilistic Programming Languages. Author-published electronic textbook, 2014. URL: https://dippl.org.

Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. ISBN 9780262013192. URL: https://mitpress.mit.edu/9780262013192/probabilistic-graphical-models/.

Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In International Conference on Learning Representations. 2014. Accepted conference paper; manuscript available as arXiv:1312.6114. URL: https://arxiv.org/abs/1312.6114, doi:10.48550/arXiv.1312.6114.

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.

Philip Wadler. The Essence of Functional Programming. In Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1–14. ACM, 1992. URL: https://doi.org/10.1145/143165.143169, doi:10.1145/143165.143169.

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.

Gordon Plotkin and Matija Pretnar. Handlers of Algebraic Effects. In Programming Languages and Systems, volume 5502 of Lecture Notes in Computer Science, 80–94. Springer, 2009. URL: https://link.springer.com/chapter/10.1007/978-3-642-00590-9_7, doi:10.1007/978-3-642-00590-9_7.

Andrej Bauer and Matija Pretnar. Programming with Algebraic Effects and Handlers. Journal of Logical and Algebraic Methods in Programming, 84(1):108–123, 2015. URL: https://www.sciencedirect.com/science/article/pii/S2352220814000194, doi:10.1016/j.jlamp.2014.02.001.