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
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):
sampledraws a latent variable from a distributionletcomputes a value from earlier ones without drawingobservescores an observed value under a distribution, which contributes the likelihoodscoreadds an arbitrary log weightmarginalizesums 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.