Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Comb elements in Markov categories

Nathaniel Virgo (Jan 14 2021 at 13:59):

This is a set of questions about two different definitions of "comb" or "optic" like things, which seem to be equivalent in Markov categories. The questions are mostly of the "hey, what's going on here?" variety, i.e. not very specific.

I was recently reading Jacobs, Kissinger and Zanazi's paper Causal Inference by String Diagram Surgery, where they give the following definition of a "2-comb":

image.png

($\mathsf{Stoch}$ here is the category of finite sets and stochastic matrices, but I guess this definition makes sense in any Markov category.)

This is a kind of conditional independence relationship, and it motivates the comb notation,

image.png

This same notation is also used for optics, as introduced by Riley in Categories of Optics. (Riley doesn't use the word "comb" for it, but lots of other people do.)

On the face of it an optic is quite a different thing from what JKZ define, but I think in Markov categories they're equivalent. An optic (at least one way to look at it) is an equivalence class of pairs of morphisms

$$(A_1\xrightarrow{u} B_1\otimes M,\,\, A_2\otimes M\xrightarrow{v}B_2).$$

(I won't state the equivalence relation explicitly.) This is different from a single morphism that obeys an equation. However, if I have such a pair of morphisms then I can form a morphism that obeys JKZ's condition as follows.

image.png

(Sorry for switching orientations.) The equation uses the naturalness of the delete morphism, so we need at least that property of Markov categories for this to work.

The correspondence isn't one-to-one - many pairs of morphisms map to a single morphism in this way - but I think the preimages of this map are exactly the equivalence classes in the definition of an optic. So (I think) in any Markov category there is a 1-1 correspondence between 2-combs as Jacobs et al. define them and optics as Riley defines them. I assume this correspondence is well known - people use the same notation after all - but I was surprised that I hadn't seen it noted anywhere. (Is it noted anywhere?)

Now on to my questions. I assume it isn't a coincidence that these two definitions are equivalent, but it currently seems a bit mysterious to me, even though I could probably prove it fairly easily. Is there some way I can understand, from a nice intuitive, probabilistic point of view, why the definition of an optic should be equivalent to a kind of conditional independence relationship when we specialise to Markov categories?

[edit: I should have tried to prove it before asking the question - it turns out it's not obvious at all and probably needs some extra conditions beyond being a Markov category. The question should really be "under what conditions are they the same?"]

My next question is about "bending wires" and requires some more images, so I'll post it below shortly.

Nathaniel Virgo (Jan 14 2021 at 14:13):

In order to compose 2-combs, JKZ move into the category of finite sets and unnormalised Markov kernels, in which objects have duals, which lets them bend wires around like this:

image.png

This seems in some way related to the "bending wires" in the other common notation for optics. That wire-bending is a notation for a coend rather than dualisation, but I'm wondering if they're related. In the context of a suitable unnormalised Markov category I guess there's no reason you couldn't write a 2-comb like this

image.png

subject to the same equivalence relation as above. Here the arrows, cap and "backwards" morphisms represent dualisation, so this is really just a family of morphisms in an unnormalised Markov category, rather than a notation for profunctors and coends.

I don't think I can make a sharp question out of this - I'm basically just asking if anyone has any nice intuitions about what's really going on here. Coends still seem very abstract and magical to me, whereas Markov kernels and unnormalised Markov kernels seem very straightforward and simple, so if I can clearly understand the relationship between them it would hopefully make a lot of things a lot easier to understand.

Nathaniel Virgo (Jan 14 2021 at 14:17):

(This might be better in #practice: applied ct. Sorry, I wasn't thinking too hard about where to post it.)

John van de Wetering (Jan 14 2021 at 15:24):

I think if you tag @Aleks Kissinger that you might get a nice answer :)

Aleks Kissinger (Jan 14 2021 at 15:54):

hi @Nathaniel Virgo, it's a good question, and one I remember discussing with @Guillaume Boisseau (who has been thinking a lot about optics) about a year ago. The two concepts are closely related. Indeed it is true for any comb in Stoch (or even in the quantum generalisation of Stoch!) can be decomposed into a pair $(f: A_1 \to B_1 \otimes M, g: A_2 \otimes M \to B_2)$.

However, it is not totally clear if it implements the same equivalence relation as the coend imposes, or a stronger one. Namely, two such pairs are considered to define the same comb if they compose to give the same map as you drew in your second diagram. On the other hand, the coend equivalence only says a pair should be considered equivalent if I can find a mediating map $m$ where:

$((1 \otimes m) \circ f, g) \sim (f, g \circ (1 \otimes m))$

This implies that when I plug these two pieces together I'll get the same comb, but the converse seems to be a very special property of a category (which is maybe true in Stoch, but we didn't come up with a proof or counter-example).

Aleks Kissinger (Jan 14 2021 at 16:01):

The classical case of decomposing a comb into two pieces is basically a special case of the product rule for conditional probabilities. The quantum case was (somewhat famously) proved by Eggeling, Schlingemann, and Werner using a nice property of quantum channels called "essential uniqueness of purifications": https://arxiv.org/abs/quant-ph/0104027

You can find both proofs re-done in a categorical style in the appendix (A.2) of mine and Sander Uijlen's causality paper: https://arxiv.org/pdf/1701.04732.pdf

John van de Wetering (Jan 14 2021 at 16:46):

I want to add to this that this proof can be generalized to finite-dimensional C*-algebras by using a modified version of purification that also works for classical systems. This proof isn't written down anywhere but can be pretty easily constructed by putting Sander's proof together with the modified definition of purification. So it is possible to do this proof in an entirely categorical way that restricts to the quantum and classical case.

Jules Hedges (Jan 15 2021 at 14:54):

Nice question! My gut feeling is also that they ought to be the same, so it's interesting if there are counterexamples. If so then it would also be interesting to figure out what conditions you need on a Markov category to make them coincide

Jules Hedges (Jan 15 2021 at 14:56):

For your section question my gut feeling is no, the cap in the optic-orientation diagram should correspond in the comb-orientation diagram to a wire that goes through the "bar" of the comb, but in the forwards direction. It allows you to "bypass" from the input of the first tooth to the output of the second tooth