nLab
Giry monad

Contents

Idea

The Giry monad (Giry 80) is the monad on a category of suitable spaces which sends each suitable space XX to the space of suitable probability measures on XX.

Definition

A useful choice of category of topological spaces suitable for the definition of the Giry monad is the category, PolPol, of Polish spaces, i.e., separable metric spaces for which a complete metric exists.

Write

P:PolPol P \colon Pol \to Pol

for the endofunctor which sends a space, XX, to the space of probability measures on the Borel subsets of XX. P(X)P(X) is equipped with the weakest topology which makes the integration map τ Xfdτ\tau \mapsto \int_{X}f d\tau continuous for any ff, a bounded, continuous, real function on XX.

There is a natural transformation

μ X:P(P(X))P(X) \mu_{X}: P(P(X)) \to P(X)

given by

μ X(M)(A):= P(X)τ(A)M(dτ).. \mu_X (M)(A) := \int_{P(X)} \tau(A) M(d\tau). \,.

This makes the endofunctor PP into a monad, and this is the Giry monad.

Properties

Algebras over the Giry monad

(Doberkat 03) works out the algebras for the Giry monad using the Giry monad defined on PolPol. We want measurable maps between P(X)P(X) and XX, such that the ‘fibres’ are convex and closed, and such that δ x\delta_{x}, the delta distribution on xx, is in the fibre over xx. And there’s another condition which requires a compact subset of P(X)P(X) to be sent to a compact subset of XX.

Now, as ever, P(X)P(X) will support an algebra, μ X:P(P(X))P(X)\mu_{X}: P(P(X)) \to P(X). This is the analogue of a free group being an algebra of the group monad. But just as there are many interesting groups which are not free, we should want to find algebras of Giry’s monad which are not of the μ X\mu_{X} form. Doberkat shows that for such an algebra XX must be connected, and suggests this example

h:P([0,1])τ 0 1tτ(dt)[0,1]. h: P([0, 1]) \ni \tau \mapsto \int_{0}^{1} t \tau (dt) \in [0, 1].

(One author believe that this might be μ {0,1}\mu_{\{0, 1\}}. After all, probability measures on {0,1}\{0, 1\} are just binomial, parameterised by p[0,1]p \in [0, 1].)

The other example he gives has XX a bounded, closed and convex subset of n\mathbb{R}^n, and probability measures being sent to their barycentre.

Doberkat has a longer article on Eilenberg-Moore algebras of the Giry monad as item 5 here. (Unfortunately, the monograph ‘Stochastic Relations: Foundations for Markov Transition Systems’ doesn’t appear to be available.) There are two monads being treated here, one which sends a Polish space to the space of all probability measures, the other to the space of all subprobability measures. The extra structure relating to these monads, is that of a (positive) convex structure. In the case of a convex structure, this intuitively captures the idea that a weighted sum of points in the space has barycentre within the space.

[Sturtz] exploits the close relationship between the tensor product structure of the two categories, measurable spaces and convex spaces, to generalize the fundamental results of Doberkat, to arbitrary measurable spaces, not just Polish spaces. With this generalization, the Giry-algebras are (characterized as) convex spaces.

Voevodsky’s work

Vladimir Voevodsky has also worked on a category theoretic treatment of probability theory, and gave few talks on this at IHES, Miami, in Moscow etc. Voevodsky had in mind applications in mathematical biology?, for example, population genetics:

See Miami Talk abstract

…a categorical study of probability theory where “categorical” is understood in the sense of category theory. Originally, I developed this approach to probability to get a better understanding of the constructions which I had to deal with in population genetics. Later it evolved into something which seems to be also interesting from a purely mathematical point of view. On the elementary level it gives a category which is useful for the work with probabilistic constructions involving complicated combinations of stochastic processes of different types. On a more advanced level, applying in this context the old idea of a functor as a generalized object one gets a better view of the relationship between probability and the theory of (pre-)ordered topological vector spaces.

A talk in Moscow (20 Niv 2008, in Russian) can be viewed here, wmv 223.6 Mb. Abstract:

In early 60-ies Bill Lawvere defined a category whose objects are measurable spaces and morphisms are Markov kernels. I will try to show how this category allows one to think about many of the notions of probability theory in categorical terms and to connect probabilistic objects to objects of other types through various functors.

Panangaden’s monad

Prakash Panangaden in Probabilistic Relations defines the category SRelSRel (stochastic relations) to have as objects sets equipped with a σ\sigma-field. Morphisms are conditional probability densities or stochastic kernels. So, a morphism from (X,Σ X)( X, \Sigma_X) to (Y,Σ Y)( Y, \Sigma_Y) is a function h:X×Σ Y[0,1]h: X \times \Sigma_Y \to [0, 1] such that

  1. BΣ Y.λxX.h(x,B)\forall B \in \Sigma_Y . \lambda x \in X . h(x, B) is a bounded measurable function,
  2. xX.λBΣ Y.h(x,B)\forall x \in X . \lambda B \in \Sigma_Y . h(x, B) is a subprobability measure on Σ Y\Sigma_Y.

If kk is a morphism from YY to ZZ, then khk \cdot h from XX to ZZ is defined as (kh)(x,C)= Yk(y,C)h(x,dy)(k \cdot h)(x, C) = \int_Y k(y, C)h(x, d y).

Panangaden’s definition differs from Giry’s in the second clause where subprobability measures are allowed, rather than ordinary probability measures.

Panangaden emphasises that the mechanism is similar to the way that the category of relations can be constructed from the power set functor. Just as the category of relations is the Kleisli category of the powerset functor over the category of sets Set, SRelSRel is the Kleisli category of the functor over the category of measurable spaces and measurable functions which sends a measurable space, XX, to the measurable space of subprobability measures on XX. This functor gives rise to a monad.

What is gained by the move from probability measures to subprobability measures? One motivation seems to be to model probabilistic processes from XX to a coproduct X+YX + Y. This you can iterate to form a process which looks to see where in YY you eventually end up. This relates to SRelSRel being traced.

There is a monad on MeasureSpacesMeasureSpaces, 1+:MeasMeas1 + -: Meas \to Meas. A probability measure on 1+X1 + X is a subprobability measure on XX. Panangaden’s monad is a composite of Giry’s and 1+1 + -.

References

A categorical approach to probability was developed by Bill Lawvere in an unpublished manuscript in 1962 which already points out the adjunction structure:

W. Lawvere, The category of probabilistic mappings, ms. 12 pages, 1962 (Lawvere Probability 1962)

‘ The key idea … is that random maps between spaces are just maps in a category of convex spaces between “simplices” ‘ (W.Lawvere, catlist remark 25 oct 1998).

The monad made its way into print then with

  • Michèle Giry, A categorical approach to probability theory, Categorical aspects of topology and analysis (Ottawa, Ont., 1980), pp. 68–85, Lecture Notes in Math. 915 Springer 1982.

In the paper, there are allegedly a few minor analytically incorrect points and gaps in proofs, observed by later authors.

According to E. Burroni (2009) the ‘Giry’ monad appears also in

  • O. de la Tullaye, L’intégration considérée comme l’algèbre d’un triple. Rapport de Stage de D.E.A. manuscrit 1971.

K.Sturtz discusses the Giry monad as a codensity monad:

This includes some corrections from an earlier version of the article, The Giry monad as a codensity monad, pointed out in

  • T. Avery, Codensity and the Giry monad , arXiv:1410.4432 (2014). (pdf)

Apart from these papers, there are similar developments in

  • Franck van Breugel, The metric monad for probabilistic nondeterminism, features both the Lawvere/Giry monad and Panangaden’s monad.

  • Ernst-Erich Doberkat, Characterizing the Eilenberg-Moore Algebras for a Monad of Stochastic Relations (pdf)

  • Ernst-Erich Doberkat, Kleisli morphisms and randomized congruences

  • N. N. Cencov, Statistical decisions rules and optimal Inference, Translations of Math. Monographs 53, Amer. Math. Society 1982

(blog comment) Cencov’s “category of statistical decisions” coincides with Giry’s (Lawvere’s) category. I (\leftarrow somebody) have the sense that Cencov discovered this category independently of Lawvere although years later.

There is also relation with work of Jacobs et al.

  • Robert Furber, Bart Jacobs, Towards a categorical account of conditional probability, arxiv/1306.0831

  • B. Jacobs, Probabilities, distribution monads and convex categories , Theoretical Computer Science 412(28) (2011) pp.3323–3336. (preprint)

J. Culbertson and K. Sturtz use the Giry monad in their categorical approach to Bayesian reasoning and inference (both articles contain further references to the categorical approach to probability theory):

  • Jared Culbertson and Kirk Sturtz, A categorical foundation for Bayesian probability, Applied Cat. Struc. 2013 (preprint as arXiv:1205.1488)

  • Jared Culbertson and Kirk Sturtz, Bayesian machine learning via category theory, 2013 (arxiv:1312.1445)

  • Kirk Sturtz?, The Factorization of the Giry monad and convex spaces as an extension of the Kleisi category, arXiv:1601.02593

E. Burroni discusses the Giry monad in:

  • Burroni, Lois distributives. Applications aux automates stochastiques, TAC 22, 2009 pp.199-221 (pdf)

where she derives stochastic automata as algebras for a suitable distributive law on the monoid and Giry monads.

B. Fong has a section on the Giry monad in his paper on Bayesian networks:

  • Fong: Causal Theories - A Categorical Perspective on Bayesian Networks, arXiv1301.6201 (2013) pdf

To do:

Revised on July 26, 2017 02:36:13 by Anonymous (119.42.79.45)