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: theory: applied category theory

Topic: Causal theories with richer objects - sets not numbers

David Michael Roberts (Dec 20 2023 at 02:34):

In @Brendan Fong 's Masters thesis a causal theory associated to a directed acyclic graph $s,t\colon A\rightrightarrows V$ is a category with set of objects $\mathbb{N}^V$, and with morphisms generated in a way that to start with is not important.

Given the developments in ACT and the general cospan tech, this feels like it is the decategorification of something involving finite sets, or at the least a skeleton of something richer. So, for instance, one can consider the set of objects $\mathbb{N}^V$ as being a decategorification of the category of functors $V\to \mathbf{FinSet}$.

Is this something people have already thought about? I'm thinking about Bayesian networks, or rather the richer structure which is models in $\mathbf{Stoch}$ (measurable spaces and stochastic maps) of a causal theory.

David Michael Roberts (Dec 20 2023 at 04:09):

Hmm, it seems the free gs-monoidal categories of @Tobias Fritz and @Wendong Liang are in the neighbourhood of what I'm thinking of, though they are more general in taking hypergraph input.

David Michael Roberts (Dec 20 2023 at 04:13):

Or, perhaps, the free Markov category on a DAG is what I'm thinking of.

Mike Shulman (Dec 20 2023 at 04:15):

Reminds me of Petri nets.

David Michael Roberts (Dec 20 2023 at 04:16):

Exactly.

David Michael Roberts (Dec 20 2023 at 04:17):

But I'm not sure they are quite it. Maybe they are, though!

Mike Shulman (Dec 20 2023 at 04:26):

I haven't read the whole thesis, but I'm looking at the start of section 4. It looks like it is a "commutative monoidal category" (strict symmetric with identity braidings) like that generated by a Petri net, but I don't think it's exactly that because a Petri net generates a free CMC and here there are equations (the comonoid equations). But it's definitely related, and so it does seem like there should also be a version with nonidentity braidings like that generated by a $\Sigma$-net, if that's what you had in mind (I wouldn't call that exactly a decategorification, though, since it's still a monoidal 1-category).

David Michael Roberts (Dec 20 2023 at 04:30):

If the DAG is the one with a single vertex and no edges, then what I'm thinking of is FinSet^op. I suspect that if you have a discrete DAG with no edges and finite vertex set V, it's (FinSet/V)^op. The trick is to know how to introduce the new morphisms coming from the nontrivial edge structure.

David Michael Roberts (Dec 20 2023 at 04:30):

Maybe what I'm thinking of turns out to be a double category :-)

David Michael Roberts (Dec 20 2023 at 04:36):

You can see the definition of gs-category in Tobias and Wendong's paper https://arxiv.org/abs/2204.02284, it's explicitly a symmetric monoidal category and cocommutative comonoids.

They also remark:

A minor technical difference is that our additional restrictions on the leg of a cospan, in the form of a monogamy condition adopted from [19,20], have not been considered in the literature on categorical network theory so far. Thus our construction is not technically an instance of the structured cospan framework in its present form. [emphasis added]

Ah, and my suspicion about the discrete DAG case is correct, as they confirm in their intro.

Mike Shulman (Dec 20 2023 at 05:15):

Is it the same as a SMC with a [[supply]] of comonoids?

David Michael Roberts (Dec 20 2023 at 05:17):

Check out the second example in sec 4 :-)

David Michael Roberts (Dec 20 2023 at 05:18):

In Friz and Liang's terminology, gs-categories are Markov, minus the requirement the tensor unit is the terminal object

Mike Shulman (Dec 20 2023 at 05:19):

Ok, so since a Markov category is a semicartesian monoidal category with a supply of comonoids, I guess it's right that a gs-category is just an SMC with a supply of comonoids.

Mike Shulman (Dec 20 2023 at 05:22):

So is it a wide subcategory of a structured cospan category?

David Michael Roberts (Dec 20 2023 at 05:23):

However, I don't want, for instance, to have the analogue of $\Delta$ (free monoidal cat with a monoid), where the objects are natural numbers, but the thing that's equivalent to this with actual structured sets.

David Michael Roberts (Dec 20 2023 at 05:23):

Mike Shulman said:

So is it a wide subcategory of a structured cospan category?

Maybe? What's the intuition here?

David Michael Roberts (Dec 20 2023 at 05:24):

Or just point me at a paper if that's easier

Tobias Fritz (Dec 20 2023 at 06:51):

Mike Shulman said:

Is it the same as a SMC with a [[supply]] of comonoids?

Yes, a gs-monoidal category is a symmetric monoidal category with a supply of commutative comonoids. What we construct in the paper are the free such categories generated by a "monoidal signature", which consists of a set of wires and a set of boxes, such that each box has a list of wires as input and output. This is formally encoded in our Defn 3.1 (which was already used by Bonchi et al for the construction of free SMCs).

Tobias Fritz (Dec 20 2023 at 06:54):

This is very similar to a Petri net. As far as I can tell, the only difference is that in a monoidal signature, the inputs and outputs of a box (transition) are lists rather than multisets of wires (places).

Tobias Fritz (Dec 20 2023 at 06:56):

Morally, Petri nets are arguably the "right" notion of signature for an SMC, since the ordering of input and output wires that Bonchi et al and we have is arbitrary and artificial. But we've settled on the morally inferior option as it simply seemed easier to work with.

Tobias Fritz (Dec 20 2023 at 07:05):

Part of this was anticipated by Brendan's early work on causal theories. However, his notion of "supply of commutative comonoids" did not impose any compatbility with the monoidal structure, while we now understand that the supply of a product $A \otimes B$ should be the product of the supplies on $A$ and $B$. (There may be other differences like what @Mike Shulman says which I don't remember right now.) There also was earlier work on free gs-monoidal categories in special cases going back to the 1996 thesis of Fabio Gadducci, who coined the term "gs-monoidal", but neither Brendan nor us knew about this for a long time as the context was different.

Tobias Fritz (Dec 20 2023 at 07:09):

We decided to go with Gadducci's term "gs-monoidal" in order to advertise his work on this, but currently it seems that people prefer to say "CD category" instead.

Tobias Fritz (Dec 20 2023 at 07:13):

David Michael Roberts said:

Hmm, it seems the free gs-monoidal categories of Tobias Fritz and Wendong Liang are in the neighbourhood of what I'm thinking of, though they are more general in taking hypergraph input.

Right, when you have a DAG you can convert it into a string diagram with commutative comonoid supply as described in Brendan's thesis. Formally that's a certain kind of cospan of hypergraphs as described in our paper, or equivalently a morphism in the free gs-monoidal category generated by the underlying signature. Like this, you get the "unviersal Bayesian network" represented by the DAG.

Tobias Fritz (Dec 20 2023 at 07:14):

But you can just as well start with an arbitrary gs-monoidal string diagram and think of it as representing a causal structure instead of a DAG. That's why we call these "generalized causal models".

Tobias Fritz (Dec 20 2023 at 07:15):

You can also do all of this with "free Markov" instead of "free gs-monoidal", and I can elaborate on the differences here if you want to know about this.

Tobias Fritz (Dec 20 2023 at 07:20):

Mike Shulman said:

So is it a wide subcategory of a structured cospan category?

Yes. If you take all structured cospans, then you get a free hypergraph category. So we needed to restrict to those cospans that represent string diagrams without monoid structure appearing, and that works by imposing additional conditions on the cospans. (And this led to additional complications in the proof of freeness, which eventually made us reprove things from scratch.)

Mike Shulman (Dec 20 2023 at 07:45):

Tobias Fritz said:

Morally, Petri nets are arguably the "right" notion of signature for an SMC, since the ordering of input and output wires that Bonchi et al and we have is arbitrary and artificial. But we've settled on the morally inferior option as it simply seemed easier to work with.

If by a Petri net you mean one with just multisets of states as the inputs and outputs of transitions, then my understanding is that that's the right notion of signature for a commutative monoidal category, but for a general symmetric monoidal category you need to have orderings even if they can be swapped around.

Tobias Fritz (Dec 20 2023 at 07:51):

Yes, I do mean with multisets of states (or equivalently arc weights encoding multiplicity). Why can't I take these as a notion of signature for an SMC? I understand that to describe the morphisms of a free SMC, we need to do more work by keeping track of which inputs get matched up with which outputs, but what's wrong with using it as a notion of signature?

Matteo Capucci (he/him) (Dec 20 2023 at 10:25):

The way Kock treats PNs and their executions seems quite relevant here. He explicitly works with 'categorified' markings (though he categorifies the natural to the [[symmetric groupoid]] $\mathbb B$), and then executions of a PN are 'ètale' morphisms of open graphs from DAGs to the PN.
In particular, I'd speculate that if you take a DAG and consider it as a PN, its associated category of processes should be a 'causal theory' of the categorified kind you want.

Tobias Fritz (Dec 20 2023 at 10:38):

Right, that's also what I was thinking of. I didn't mention it since I don't fully understand it, but my feeling is that Joachim's Theorem 7.2 is the "morally correct" notion of free SMC. And it's generated by a Petri net, meaning that the generating morphisms don't come equipped with an ordering of their inputs or outputs. Does this sound sensible?

Tobias Fritz (Dec 20 2023 at 10:41):

BTW there's a dual role played by DAGs here and we need to be careful not to get mixed up. If we start with a DAG in the Bayesian network sense, and translate it into a string diagram as mentioned above, then the nodes becomes wires (objects), and you generally need the comonoid structures in order to do the translation. While for a DAG in the sense of Joachim's paper, I think the nodes become boxes (morphisms), right?

Tobias Fritz (Dec 20 2023 at 10:44):

And I think what we want in the context of causality is the former. For example, take the DAG with three nodes and two edges $A \to B$ and $A \to C$. Here, these nodes represent "variables" that can have values, and these correspond to information flowing along the wires of a string diagram. And the value of $A$ can influence the value of both $B$ and $C$, so we need to copy that value, which is where the comonoid structures come in.

Matteo Capucci (he/him) (Dec 20 2023 at 14:35):

Tobias Fritz said:

BTW there's a dual role played by DAGs here and we need to be careful not to get mixed up. If we start with a DAG in the Bayesian network sense, and translate it into a string diagram as mentioned above, then the nodes becomes wires (objects), and you generally need the comonoid structures in order to do the translation. While for a DAG in the sense of Joachim's paper, I think the nodes become boxes (morphisms), right?

Correct

Tomáš Gonda (Dec 20 2023 at 15:20):

Tobias Fritz said:

And I think what we want in the context of causality is the former. For example, take the DAG with three nodes and two edges $A \to B$ and $A \to C$. Here, these nodes represent "variables" that can have values, and these correspond to information flowing along the wires of a string diagram. And the value of $A$ can influence the value of both $B$ and $C$, so we need to copy that value, which is where the comonoid structures come in.

I wouldn't be so sure about that. For instance, in the context of quantum causal models it seems more fruitful to think of nodes as 'points of intervention' rather than 'variables', not least because variables here cannot be copied of course, while an intervention may have multiple outputs. In the classical case, this point of view is also possible, but I think equivalent to that of nodes in a DAG viewed as variables.

Tobias Fritz (Dec 20 2023 at 15:32):

Fair enough :wink: So how do you translate a DAG into a string diagram in that context? I only know of the two ways described above. You've excluded the gs-monoidal one, and the other one would assign to the DAG with edges $A \to B$ and $A \to C$ the string diagram consisting of a state corresponding to $A$ with two output wires, leading to effects corresponding to $B$ and $C$, respectively. Since this diagram doesn't have any overall output, it can hardly be any sort of causal model? So is there a third kind of translation that is relevant here?

David Michael Roberts (Dec 20 2023 at 22:57):

OK, so to bring it back to my original idea, I can refine it slightly: is there a fairly explicitly identifiable 'concrete' category equivalent to the free Markov category on a DAG? By concrete I mean here that the objects are structured sets (for instance elements of a slice of FinSet), but where the objects can be cospans or what-have-you?

From the above discussion it seems the answer is 'yes', but everyone is having a lot of fun with matters more general than my needs at present :-)

Mike Shulman (Dec 20 2023 at 23:14):

Kock's "whole-grain Petri nets" don't have what I would call "multisets" of states as inputs and outputs; they have families of states. You don't need an ordering per se, but you need some way of telling apart the "multiple occurrences" of a single state.

Mike Shulman (Dec 20 2023 at 23:16):

@John Baez, @Fabrizio Genovese, @Jade Master, and I wrote a paper called Categories of nets trying to clarify the relationship between different kinds of Petri net and the monoidal categories they generate, and introducing something called a $\Sigma$-net that's a bit more general than Kock's whole-grain Petri nets but can still generate a free SMC.

John Baez (Dec 20 2023 at 23:32):

Yes, and we discuss how Kock's work is related to ours. We were attempting to lay to rest the surprisingly subtle question "which kinds of things like Petri nets generate which kinds of monoidal categories", by studying some of the most important answers and putting them all into a big diagram.

Bradley Saul (Dec 21 2023 at 00:50):

(deleted)

David Michael Roberts (Dec 21 2023 at 00:59):

I think this conversation is getting away from me... :-)

Mike Shulman (Dec 21 2023 at 02:08):

Sorry.

David Michael Roberts (Dec 21 2023 at 02:15):

I don't begrudge people having the discussion at all :-) Just that it's not particularly helping with what I need at present.

Mike Shulman (Dec 21 2023 at 02:43):

Maybe we should move it into another topic.

David Michael Roberts (Dec 21 2023 at 02:55):

And perhaps I should have put it in learning: questions ! :-D

David Michael Roberts (Dec 21 2023 at 05:01):

Hmm, it seems @Wendong Liang's thesis talks about something useful https://www.uibk.ac.at/mathematik/algebra/teaching/m1these_wendong_liang.pdf

David Michael Roberts (Dec 21 2023 at 05:02):

Particularly Definition 2.14 and Theorem 2.16

Tobias Fritz (Dec 21 2023 at 06:54):

Right! All of that is also in the paper, in slightly different form.

David Michael Roberts (Dec 21 2023 at 06:59):

I see it now, it's just that it was explicitly stated in more concrete terms in the thesis. I want to unwind it even further to very concrete data.

Tobias Fritz (Dec 21 2023 at 07:02):

David Michael Roberts said:

OK, so to bring it back to my original idea, I can refine it slightly: is there a fairly explicitly identifiable 'concrete' category equivalent to the free Markov category on a DAG? By concrete I mean here that the objects are structured sets (for instance elements of a slice of FinSet), but where the objects can be cospans or what-have-you?

Assuming that you meant that the morphisms can be (iso classes of) cospans, then the free gs-monoidal (free CD category) on a DAG is concrete in that sense. For the free Markov category It's a bit more subtle: to get that, we need to quotient by the equational equations making the monoidal unit terminal:
image.png

Tobias Fritz (Dec 21 2023 at 07:04):

This quotient is nice at least insofar as every equivalence class has a minimal representative: you simply apply the above equation from left to right as many times as you can and you end up with a normal form (Section 6 of the paper). The annoying thing is that the composition of two normal forms is not necessarily a normal form again.

Tobias Fritz (Dec 21 2023 at 07:05):

I'd love to see a more concrete description than this, as that could be very useful in Bayesian network theory and causal inference. We do work with the cospan formalism quite a bit, but it's rather clunky and difficult to understand, so having something simpler would help us a lot. At the same time, I have some doubts about this being possible, since the cospans seem to encode the combinatorial structure of a string diagram rather accurately.

Tobias Fritz (Dec 21 2023 at 08:00):

BTW I'd be curious to know what got you interested in this @David Michael Roberts, if you don't mind sharing.

David Michael Roberts (Dec 21 2023 at 09:02):

I'm learning about graphical models, and trying to understand them from the modern, CT viewpoint. :-)

David Michael Roberts (Dec 21 2023 at 09:04):

I guess that the universal property of the free Markov category, though, is that if you have an appropriate model of the free gs-monoidal category on a DAG in a Markov category (like a variant of Stoch or similar), then there should be an essentially unique model of the free Markov category, right?

Tobias Fritz (Dec 21 2023 at 09:10):

Yep, that's exactly right!