10
$\begingroup$

Why is there so much interest in the Markov categories which are Kleisli categories for monads corresponding to distributions etc. but not much discussion of the E.M. categories?

For example, the E.M. category of algebras for the finitely supported distribution monad - the so called finitary Giry monad - is really quite intuitive: Fritz' category of convex spaces.

What can you do with the Kleisli category that you can't do with the E.M. category?

$\endgroup$
1
  • 1
    $\begingroup$ Please don't attribute convex spaces to me -- they've been rediscovered many times over, and also treated in categorical terms, before I was apparently the first one to do so in times of the internet. I've described some of the history on p.1/2 here, and there has been additional prior work on variations of it such as superconvex spaces (see kirk sturtz's answer and comments for that). $\endgroup$ Aug 10, 2022 at 10:32

2 Answers 2

7
$\begingroup$

The short answer is that there is nothing that one can't do with the EM category $\mathbf{Meas}^{\mathcal{G}}$ that one can do with the Kleisi category $\mathbf{Meas}_{\mathcal{G}}$ of the Giry monad. But the purpose of Markov categories is the capture certain aspects of probability and statistics which can then be applied to other categories without directly requiring measurable spaces. The axioms for Markov categories do indeed look like they were derived with the Kleisi category in mind because (I presume) the progenitors of that theory believe those are precisely the axioms which are necessary to model the fundamental aspects of probability and statistics. Whether those axioms are the appropriate ones or not is open to debate, but the idea and intent is to abstract the basic axioms much like one does with characterizing Abelian categories for which the axioms are applicable to a wide variety of situations. In that sense the theory is successful drawing much interest (and that is how math research progresses forward).

If one had extracted the axioms based upon the properties of the EM category then the axioms would be quite different. In referring to the EM category care must be exercised because axioms characterizing the EM category are descriptive in nature and not constructive. Those axioms say nothing about the existence of algebras (which are the objects of the EM category) outside the free algebras $(\mathcal{G}(X), \mu_X)$, and the full subcategory of all those objects is precisely the Kleisi category of the $\mathcal{G}$-monad. Proving the existence/non-existence of non free $\mathcal{G}$-algebras is the key aspect in deriving the EM category, and for the general case $\mathbf{Meas}$ we cannot say too much because of pathological spaces. Thus we must temper our ambitions and address the $\mathcal{G}$-algebras for subcategories of $\mathbf{Meas}$ which have nice properties. In practice, the category of standard measurable spaces, $\mathbf{Std}$, covers most measurable spaces which arise in practice. For that case what we do know is that the $\mathcal{G}$-algebras are isomorphic to a subcategory of the category of super convex spaces. The discussion on the page Giry monad discussing the algebras gives some arguments why super convex spaces arise in the analysis of algebras. I must emphasize that that work on $\mathcal{G}$-algebras for $\mathbf{Std}$ is still a work in progress. A list of some known algebras for other nice subcategories of $\mathbf{Meas}$ can be found at probability monads. The reason that the category of super convex spaces, $\mathbf{SCvx}$, is of particular interest is that in attempting to find the algebras for the case $\mathbf{Std}$ there, we find that all other algebras are super convex spaces also.

To answer your question

why aren't EM categories used?

I would say that EM categories have not been used in the past because the algebras for the subcategories of $\mathbf{Meas}$ that we do understand are not practical for applications because they were based upon subcategories using the Borel $\sigma$-algebra of a topological space, e.g., the algebras for Polish Spaces with continuous maps, $\mathbf{Pol}$, or metric spaces with short maps, $\mathbf{Met}$, all require the algebras to have continuous maps. Thus, there are no discrete algebras, e.g., $\epsilon_2: \mathcal{G}(2) \rightarrow 2$ given by $\epsilon_2(p \delta_0 + (1-p) \delta_1)= 0$ for all $p \in (0,1]$ and $=1$ for $p=0$ is a $\mathcal{G}$-algebra in $\mathbf{Std}$, but it is not an algebra in $\mathbf{Pol}$ or $\mathbf{Met}$. Thus those algebras are not practical for applications. That is why the $\mathcal{G}$-algebras for $\mathbf{Std}$ which only requires the $\mathcal{G}$-algebras to be measurable is so important.

Whether the category of $\mathcal{G}$-algebras affects the synthetic approach to probability and statistics is still to be discovered. But Markov categories have attracted the lions share of research effort and the categorical understanding of probability theory has made progress based upon those axioms.

$\endgroup$
5
  • 2
    $\begingroup$ I am wondering (quite sincerely) if the categorical understanding of probability theory has helped one obtain a result in traditional probability theory which is harder to obtain without category theory. $\endgroup$ Aug 9, 2022 at 12:21
  • $\begingroup$ One aspect that it does illuminate which is not so clear cut without the categorical viewpoint is the use of the $\ell_1$-norm or $\ell_2$-norm (over the complex numbers) is really just a choice in how one chooses to define countable affine sums. I believe that realization is due to Pumplun. $\endgroup$ Aug 10, 2022 at 0:35
  • 1
    $\begingroup$ I am not sure if your comment is in response to mine. Actually, I have no idea what point is addressed by your comment. In particular, aren't all norms over the complex numbers equivalent to one another? $\endgroup$ Aug 10, 2022 at 3:20
  • $\begingroup$ I am just making reference to the fact you can employ probability amplitudes, as is done in quantum mechanics, instead of the traditional real-valued probability measures. See section 4 at super convex space. I realize your question was making inference w/r/t/ well-known theorems occuring within traditional probability Theory. Category theory rarely helps in that regard. $\endgroup$ Aug 10, 2022 at 4:38
  • $\begingroup$ @IosifPinelis, I've tried to answer your question in my own answer. $\endgroup$ Aug 10, 2022 at 10:28
7
$\begingroup$

What can you do with the Kleisli category (of a probability monad) that you can't do with the Eilenberg-Moore category?

The first paragraph of kirk sturtz's answer provides a good high-level summary. In this answer, let me provide some of the more detailed motivation for axiomatizing the Kleisli category and why "the progenitors of that theory believe those are precisely the axioms which are necessary to model the fundamental aspects of probability and statistics". Various points come to mind.

  • The most important point: it just works. Within the Markov categories formalism, we have proven purely categorical versions of some classical theorems of probability and statistics. So far, these are:

    Notably, the categorical formulations and proofs do not involve any measure theory (but only category theory). I would not know how to achieve this in a framework based on Eilenberg-Moore categories. What special structure or property does the Eilenberg-Moore category of a probability monad have?

  • To see what special structure the Kleisli category has and how this is relevant to probability theory, consider for example the equation $$p(x,y) = p(x) p(y|x).$$ You can think of this as the definition of the conditional $p(y|x)$. In this equation, note that the $x$ appears twice on the right-hand side. This means that a categorical formulation of this equation must facilitate some sort of "copying" of values, axiomatized as categorical structure. This comes in the form of a distinguished morphism $X \to X \otimes X$ for every object $X$ in the Markov category, which together with the unique morphism $X \to I$ equips $X$ with the structure of a commutative comonoid. It's typically implemented as the usual diagonal $X \to X \times X$ lifted to the Kleisli category.

    Getting to the Eilenberg-Moore category, the problem now is that non-free algebras do typically not allow for such a copying morphism. This is a version of the no-cloning theorem of quantum mechanics, where the relevant technical result is the no-cloning theorem for general probabilistic theories. Therefore, the main feature that the Kleisli category has and the Eilenberg-Moore category lacks are the copying morphisms, and my claim is that this is a crucial piece of structure that is necessary and sufficient (on top of having a semicartesian symmetric monoidal category) for developing a lot of probability and statistics purely abstractly.

    My above notation has been that of discrete probability, but translating this into the categorical formulation results in a definition that applies to measure-theoretic probability just as well and recovers the definition of regular conditional probability there.

  • The non-free algebras of a probability monad correspond intuitively to convex sets that are not simplices. These rarely come up in classical probability theory. The way in which randomness actually does come up is in the form of Markov kernels. And these are exactly the morphisms in the Kleisli category.

    In the rare cases in which non-free algebras are relevant, we can still work with them in the Kleisli category. This is what we've done in the comparison of statistical experiments paper linked above.


Iosif Pinelis asks:

if the categorical understanding of probability theory has helped one obtain a result in traditional probability theory which is harder to obtain without category theory.

That is a great question, but also a high bar for a formalism that is barely a few years old. And it's also subjective to some degree, especially given that the perceived hardness of a proof depends on one's background.

With that being said, I think that our proof of de Finetti's theorem (see above) could qualify as more intuitive and more insightful than previous measure-theoretic ones. I would also claim that our categorical d-separation criterion is significantly simpler than the traditional one.

One hope for the intermediate future is that we'll be able to provide also categorical versions of more recent results, in particular de Finetti theorems for hierarchical exchangeability. It is along these lines that I would expect genuinely new results to appear, i.e. results that have not been developed in a measure-theoretic setting before.

$\endgroup$
3
  • 1
    $\begingroup$ Wow, this is a great (and, frankly, surprising to me) answer to my question. I should consider studying category theory! $\endgroup$ Aug 10, 2022 at 23:58
  • $\begingroup$ The statement the main feature that the Kleisli category has and the Eilenberg-Moore category lacks are the copying morphisms is not true. The EM category of the Giry monad has both the cartesian monoidal and tensor monoidal structures. What is true that the tensor monoidal structure does not permit copying. It seems one would want to use properties of the EM category rather than the Kleisi category because the EM category has very nice properties, as opposed to the Kleisi categoroy which lacks good properties. Regardless, as you clearly note, good progress is being made! $\endgroup$ Aug 11, 2022 at 1:14
  • $\begingroup$ With regard to the statement The way in which randomness actually does come up is in the form of Markov kernels is certainly true. But unfortunately it is true because we (nobody) has ever explained to the scientific community just how to use $\mathcal{G}$-algebras can be used for modeling. We, as a research community, need to show the benefits of the EM category. Within that framework many aspects can be answered which cannot be answered w/o EM. Quotient spaces are critical for applications, and that requires the category of algebras. Both Markov and $\mathcal{G}$-algebras are useful $\endgroup$ Aug 11, 2022 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.