Epidemiological Modeling With Structured Cospans

19 October, 2020

This is a wonderful development! Micah Halter and Evan Patterson have taken my work on structured cospans with Kenny Courser and open Petri nets with Jade Master, together with Joachim Kock’s whole-grain Petri nets, and turned them into a practical software tool!

Then they used that to build a tool for ‘compositional’ modeling of the spread of infectious disease. By ‘compositional’, I mean that they make it easy to build more complex models by sticking together smaller, simpler models.

Even better, they’ve illustrated the use of this tool by rebuilding part of the model that the UK has been using to make policy decisions about COVID19.

All this software was written in the programming language Julia.

I had expected structured cospans to be useful in programming and modeling, but I didn’t expect it to happen so fast!

For details, read this great article:

• Micah Halter and Evan Patterson, Compositional epidemiological modeling using structured cospans, 17 October 2020.

Abstract. The field of applied category theory (ACT) aims to put the compositionality inherent to scientific and engineering processes on a firm mathematical footing. In this post, we show how the mathematics of ACT can be operationalized to build complex epidemiological models in a compositional way. In the first two sections, we review the idea of structured cospans, a formalism for turning closed systems into open ones, and we illustrate its use in Catlab through the simple example of open graphs. Finally, we put this machinery to work in the setting of Petri nets and epidemiological models. We construct a portion of the COEXIST model for the COVID-19 pandemic and we simulate the resulting ODEs.

You can see related articles by James Fairbanks, Owen Lynch and Evan Patterson here:

AlgebraicJulia Blog.

Also try these videos:

• James Fairbanks, AlgebraicJulia: Applied category theory in Julia, 29 July 2020.

• Evan Patterson, Realizing applied category theory in Julia, 16 January 2020.

I’m biased, but I think this is really cool cutting-edge stuff. If you want to do work along these lines let me know here and I’ll get Patterson to take a look.

Here’s part of a network created using their software:


Open Petri Nets and Their Categories of Processes

14 October, 2020

My student Jade Master will be talking about her work on open Petri nets at the online category theory seminar at UNAM on Wednesday October 21st at 18:00 UTC (11 am Pacific Time):

Open Petri Nets and Their Categories of Processes

Abstract. In this talk we will discuss Petri nets from a categorical perspective. A Petri net freely generates a symmetric monoidal category whose morphisms represent its executions. We will discuss how to make Petri nets ‘open’—i.e., equip them with input and output boundaries where resources can flow in and out. Open Petri nets freely generate open symmetric monoidal categories: symmetric monoidal categories which can be glued together along a shared boundary. The mapping from open Petri nets to their open symmetric monoidal categories is functorial and this gives a compositional framework for reasoning about the executions of Petri nets.

You can see the talk live, or later recorded, here:

You can read more about this work here:

• John Baez and Jade Master, Open Petri nets.

• Jade Master, Generalized Petri nets.

You can see Jade’s slides for a related talk here:

Open Petri nets

Abstract. The reachability semantics for Petri nets can be studied using open Petri nets. For us an ‘open’ Petri net is one with certain places designated as inputs and outputs via a cospan of sets. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Open Petri nets can be treated as morphisms of a category \mathsf{Open}(\mathsf{Petri}), which becomes symmetric monoidal under disjoint union. However, since the composite of open Petri nets is defined only up to isomorphism, it is better to treat them as morphisms of a symmetric monoidal double category \mathbb{O}\mathbf{pen}(\mathsf{Petri}). Various choices of semantics for open Petri nets can be described using symmetric monoidal double functors out of \mathbb{O}\mathbf{pen}(\mathsf{Petri}). Here we describe the reachability semantics, which assigns to each open Petri net the relation saying which markings of the outputs can be obtained from a given marking of the inputs via a sequence of transitions. We show this semantics gives a symmetric monoidal lax double functor from \mathbb{O}\mathbf{pen}(\mathsf{Petri}) to the double category of relations. A key step in the proof is to treat Petri nets as presentations of symmetric monoidal categories; for this we use the work of Meseguer, Montanari, Sassone and others.


Network Models

7 October, 2020

Good news: my student Joe Moeller will be taking a job at NIST, the National Institute of Standards and Technology! He’ll be working with Spencer Breiner and Eswaran Subrahmanian on categories in engineering and system design.

Joe Moeller will be talking about his work on ‘network models’ at the online category theory seminar at UNAM on Wednesday October 14th at 18:00 UTC (11 am Pacific Time):

Network Models

Abstract. Networks can be combined in various ways, such as overlaying one on top of another or setting two side by side. We introduce `network models’ to encode these ways of combining networks. Different network models describe different kinds of networks. We show that each network model gives rise to an operad, whose operations are ways of assembling a network of the given kind from smaller parts. Such operads, and their algebras, can serve as tools for designing networks. Technically, a network model is a lax symmetric monoidal functor from the free symmetric monoidal category on some set to Cat, and the construction of the corresponding operad proceeds via a symmetric monoidal version of the Grothendieck construction.

You can watch the talk here:

You can read more about network models here:

Complex adaptive system design (part 6).

and here’s the original paper:

• John Baez, John Foley, Blake Pollard and Joseph Moeller, Network models, Theory and Applications of Categories 35 (2020), 700–744.


Open Systems: A Double Categorical Perspective (Part 2)

16 September, 2020

Back to Kenny Courser’s thesis:

• Kenny Courser, Open Systems: A Double Categorical Perspective, Ph.D. thesis, U. C. Riverside, 2020.

One thing Kenny does here is explain the flaws in a well-known framework for studying open systems: decorated cospans. Decorated cospans were developed by my student Brendan Fong. Since I was Brendan’s advisor at the time, a hefty helping of blame for not noticing the problems belongs to me! But luckily, Kenny doesn’t just point out the problems: he shows how to fix them. As a result, everything we’ve done with decorated cospans can be saved.

The main theorem on decorated cospans is correct; it’s just less useful than we’d hoped! The idea is to cook up a category where the morphisms are open systems. The objects of this category could be something simple like sets, but morphisms from X to Y could be something more interesting, like ‘open graphs’:

Here X and Y are mapped into a third set in the middle, but this set in the middle is the set of nodes of a graph. We say the set in the middle has been ‘decorated’ with the structure of a graph.

Here’s how the original theory of decorated cospans seeks to make this precise.

Fong’s Theorem. Suppose C is a category with finite colimits, and make C into a symmetric monoidal category with its coproduct as the tensor product. Suppose F\colon (C,+) \to (\mathrm{Set},\times) is a lax symmetric monoidal functor. Define an F-decorated cospan to be a cospan

in C together with an element of F(N). Then there is a symmetric monoidal category with

• objects of C as objects,
• isomorphism classes of F-decorated cospans as morphisms.

I won’t go into many details, but let me say how to compose two decorated spans, and also how this ‘isomorphism class’ business works.

Given two decorated cospans we compose their underlying cospans in the usual way, via pushout:

We get a cospan from X to Z. To decorate this we need an element of F(M +_Y N). So, we take the decorations we have on the cospans being composed, which together give an element of F(N) \times F(M), and apply this composite map:

F(N) \times F(M)  \longrightarrow F(N+M) \longrightarrow F(N+_Y M)

Here the first map, called the laxator, comes from the fact that F is a lax monoidal functor, while the second comes from applying F to the canonical map N+M \to N+_Y M.

Since composing cospans involves a pushout, which is defined via a universal property, the composite is only well-defined up to isomorphism. So, to get an actual category, we take isomorphism classes of decorated cospans as our morphisms.

Here an isomorphism of cospans is a commuting diagram like this:

where h is an isomorphism. If the first cospan here has a decoration d \in F(N) and the second has a decoration d' \in F(N'), then we have an isomorphism of decorated cospans if F(h)(d) = d'.

So, that’s the idea. The theorem is true, and it works fine for some applications—but not so well for others, like the example of open graphs!

Why not? Well, let’s look at this example in more detail. Given a finite set N, let’s define a graph on N to be a finite set E together with two functions s, t \colon E \to N. We call N the set of nodes, E the set of edges, and the functions s and t map each edge to its source and target, respectively. So, a graph on N is a way of choosing a graph whose set of nodes is N.

We can try to apply the above theorem taking

C = \mathrm{FinSet}

and letting

F \colon \mathrm{FinSet} \to \mathrm{Set}

be the functor sending each finite set N to the set of all graphs on N.

The first problem, which Brendan and I noticed right away, is that there’s not really a set of graphs on N. There’s a proper class! E ranges over all possible finite sets, and there’s not a set of all finite sets.

This should have set alarm bells ringing right away. But we used a standard dodge. In fact there are two. One is to replace \mathrm{FinSet} with an equivalent small category, and define a graph just as before but taking N and E to be objects in this equivalent category. Another is to invoke the axiom of universes. Either way, we get a set of graphs on each N.

Then Fong’s theorem applies, and we get a decorated cospan category with:

• ‘finite sets’ as objects,
• isomorphism classes of open graphs as morphisms.

Here I’m putting ‘finite sets’ in quotes because of the trickery I just mentioned, but it’s really not a big deal so I’ll stop now. An open graph has a finite set N of nodes, a finite set E of edges, maps s,t \colon E \to N saying the source and target of each edge, and two maps f \colon X \to N and g \colon Y \to N.

These last two maps are what make it an open graph going from X to Y:

Isomorphism classes of open graphs from X to Y are the morphisms from X to Y in our decorated cospan category.

But later, Kenny and I noticed a second problem. The concept of ‘isomorphic decorated cospan’ doesn’t behave well in this example: the concept of isomorphism is too narrowly defined!

Suppose you and I have isomorphic decorated cospans:

In the example at hand, this means you have a graph on the finite set N and I have a graph on the finite set N'. Call yours d \in F(N) and mine d' \in F(N').

We also have a bijection h \colon N \to N' such that

F(h)(d) = d'

What does this mean? I haven’t specified the functor F in detail so you’ll have to take my word for it, but it should be believable. It means that my graph is exactly like yours except that we replace the nodes of your graph, which are elements of N, by the elements of N' that they correspond to. But this means the edges of my graph must be exactly the same as the edges of yours. It’s not good enough for our graphs to have isomorphic sets of edges: they need to be equal!.

For a more precise account of this, with pictures, read the introduction to Chapter 3 of Kenny’s thesis.

So, our decorated cospan category has ‘too many morphisms’. Two open graphs will necessarily define different morphisms if they have different sets of edges.

This set Kenny and I to work on a new formalism, structured cospans, that avoids this problem. Later Kenny and Christina Vasilakopoulou also figured out a way to fix the decorated cospan formalism. Kenny’s thesis explains all this, and also how structured cospans are related to the ‘new, improved’ decorated cospans.

But then something else happened! Christina Vasilakopoulou was a postdoc at U.C. Riverside while all this was going on. She and my grad student Joe Moeller wrote a paper on something called the monoidal Grothendieck construction, which plays a key role in relating structured cospans to the new decorated cospans. But the anonymous referee of their paper pointed out another problem with the old decorated cospans!

Briefly, the problem is that the functor

F \colon (\mathrm{FinSet},+) \to (\mathrm{Set},\times)

that sends each N to the set of graphs having N as their set of vertices cannot be made lax monoidal in the desired way. To make F lax monoidal, we must pick a natural transformation called the laxator:

\phi_{N,M} \colon F(N) \times F(M) \to F(N+M)

I used this map earlier when explaining how to compose decorated cospans.

The idea seems straightforward enough: given a graph on N and a graph on M we get a graph on their disjoint union N+M. This is true, and there is a natural transformation \phi_{N,M} that does this.

But the definition of lax monoidal functor demands that the laxator make a certain hexagon commute! And it does not!

I won’t draw this hexagon here; you can see it at the link or in the intro to Chapter 3 of Kenny’s thesis, where he explains this problem. The problem arises because when we have three sets of edges, say E,E',E'', we typically have

(E + E') + E'' \ne E + (E' + E'')

There is a sneaky way to get around this problem, which he also explains: define graphs using a category equivalent to \mathrm{FinSet} where + is strictly associative, not just up to isomorphism!

This is good enough to make F lax monoidal. But Kenny noticed yet another problem: F is still not lax symmetric monoidal. If you try to show it is, you wind up needing two graphs to be equal: one with E+E' as its set of edges, and another with E'+E as its set of edges. These aren’t equal! And at this point it seems we hit a dead end. While there’s a category equivalent to \mathrm{FinSet} where + is strictly associative, there’s no such category where + is also strictly commutative.

In the end, by going through all these contortions, we can use a watered-down version of Fong’s theorem to get a category with open graphs as morphisms, and we can make it monoidal—but not symmetric monoidal.

It’s clear that something bad is going on here. We are not following the tao of mathematics. We keep wanting things to be equal, that should only be isomorphic. The problem is that we’re treating a graph on a set as extra structure on that set, when it’s actually extra stuff.

Structured cospans, and the new decorated cospans, are the solution! For example, the new decorated cospans let us use a category of graphs with a given set of nodes, instead of a mere set. Now F(N) is a category rather than a set. This category lets us talk about isomorphic graphs with the same set of vertices, and all our problems evaporate.


Part 1: an overview of Courser’s thesis and related papers.

Part 2: problems with decorated cospans.


Open Systems: A Double Categorical Perspective (Part 1)

15 August, 2020

My student Kenny Courser’s thesis has hit the arXiv:

• Kenny Courser, Open Systems: A Double Categorical Perspective, Ph.D. thesis, U. C. Riverside, 2020.

He’s been the driving force behind a lot of work on open systems and networks at U. C. Riverside. By the way, he’s looking for a job, so if you think you know a position that’s good for someone who can teach all kinds of math and also strong on applied category theory, give him or me a shout.

But let me describe his thesis.

His thesis is big! It lays out a general approach to open systems—systems that can interact with their environment. In this approach, you can attach open systems in series to form larger open systems, so they act like morphisms in a category:

But you can also study 2-morphisms between open systems. These describe ways to include a little system in a bigger one, or simplify a big complicated system down to smaller one:

To handle all this, Courser uses ‘double categories’, which he explains.

His formalism also lets you set two open systems side by side ‘in parallel’ and get a new open system:

To handle this, he uses ‘symmetric monoidal double categories’. He explains what these are, and how to get them. And he illustrates his setup with examples:

open Petri nets
open electrical circuits
open chemical reaction networks
open Markov processes

At a more technical level, Courser explains the problems with Brendan Fong’s and my work on decorated cospans and shows how to fix in not just one but two ways: using structured cospans, and using a new improved version of decorated cospans. He also shows that these two approaches are equivalent under fairly general conditions.

His thesis unifies a number of papers:

• Kenny Courser, A bicategory of decorated cospans, Theory and Applications of Categories 32 (2017), 995–1027.

• John Baez and Kenny Courser, Coarse-graining open Markov processes, Theory and Applications of Categories 33 (2018), 1223–1268. (Blog article here.)

• John Baez and Kenny Courser, Structured cospans. (Blog article here.)

• John Baez, Kenny Courser and Christina Vasilakopoulou, Structured versus decorated cospans.

The last, still being written, introduces the new improved decorated cospans and proves their equivalence to structured cospans under some conditions. For now you’ll have to read Kenny’s thesis to see how this works!

Next time I’ll explain the problems with the original decorated cospan formalism. Another nice thing about Kenny’s thesis is that it goes over a bunch of papers that were afflicted by these problems, and shows how to fix them.


Part 1: an overview of Courser’s thesis and related papers.

Part 2: problems with decorated cospans.


Linear Logic and Petri Nets

28 July, 2020

Wow! Elena Di Lavore and Xiaoyan Li explained how to make a category of Petri nets that’s a model of linear logic! I consider myself a sort of expert on Petri nets, but I didn’t know this stuff:

• Elena Di Lavore and Xiaoyan Li, Linear logic flavoured composition of Petri nets, The n-Category Café, 27 July 2020.

It has great pictures, too. Let me summarize a tiny bit.

A Petri net is a very simple thing. Here’s a Petri net that shows how healthy white blood cells (H), individual viruses (V) and infected white blood cells (I) interact when someone gets AIDS:

The yellow boxes are different kinds of things, called species; the aqua boxes are processes, called transitions.

There are different ways to form categories using Petri nets. Jade Master and I have focused on two:

1) How to turn a Petri net into a category where the morphisms say what the Petri net can do.

2) How to make a category with ‘open’ Petri nets as morphisms. Composing these lets you build big Petri nets from smaller pieces.

open_petri_2

Di Lavore and Li instead explain:

3) How to make a category with elementary Petri nets as objects: a morphism from one elementary Petri net to another turns each transition of the first into a transition of the second.

An elementary Petri net is one where each transition uses each species at most once as an input and at most once as an output:

nets

The category they get has lots of interesting structure! Like products, shown here:

product

In fact it has products, coproducts, two other monoidal structures, and exponentials—all fitting together in a wonderful way, as described by intuitionistic linear logic! To prove this, the key is to use Valeria de Paiva’s work on “Dialectica categories”. They explain how.

This is not original research: Elena Di Lavore and Xiaoyan Li wrote this blog article for the ACT2020 Adjoint School, and they’re explaining Carolyn Brown and Doug Gurr’s paper “A categorical linear framework for Petri nets”.

It’s worth comparing this paper:

• Uffe Engberg and Glynn Winskel, Petri nets as models of linear logic, in Colloquium on Trees in Algebra and Programming, Springer, Berlin, 1990, pp. 147–161.

Engberg and Winskel get a model of linear logic—or to be precise, a ‘commutative quantale’—by taking the category you get from a single Petri net as in item 1) and massaging it a bit. I explained it here:

• John Baez, Quantales from Petri nets, Azimuth, 6 October 2019.


A Localic Approach to Dependency, Conflict, and Concurrency

28 April, 2020

In the fifth talk of the ACT@UCR seminar, Gershom Bazerman told how to use locales to study the semantics of dependency, conflict, and concurrency.

Afterwards we discussed his talk at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2029th.3A.20Gershom.20Bazerman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video here, or watch the video here:

• Gershom Bazerman, A localic approach to the semantics of dependency, conflict, and concurrency.

Abstract. Petri nets have been of interest to applied category theory for some time. Back in the 1980s, one approach to their semantics was given by algebraic gadgets called “event structures.” We use classical techniques from order theory to study event structures without conflict restrictions (which we term “dependency structures with choice”) by their associated “traces”, which let us establish a one-to-one correspondence between DSCs and a certain class of locales. These locales have an internal logic of reachability, which can be equipped with “versioning” modalities that let us abstract away certain unnecessary detail from an underlying DSC. With this in hand we can give a general notion of what it means to “solve a dependency problem” and combinatorial results bounding the complexity of this. Time permitting, I will sketch work-in-progress which hopes to equip these locales with a notion of conflict, letting us capture the full semantics of general event structures in the form of homological data, thus providing one avenue to the topological semantics of concurrent systems. This is joint work with Raymond Puzio.


The Monoidal Grothendieck Construction

24 April, 2020

My student Joe Moeller gave a talk at the MIT Categories Seminar today! People discussed his talk at the Category Theory Community Server, and if you join that you can see the discussion here:

https://categorytheory.zulipchat.com/#narrow/stream/229457-MIT-Categories.20Seminar/topic/April.2023.20-.20Joe.20Moeller’s.20talk

You can see his slides here, and watch a video of his talk here:

The monoidal Grothendieck construction

Abstract. The Grothendieck construction gives an equivalence between fibrations and indexed categories. We will begin with a review of the classical story. We will then lift this correspondence to two monoidal variants, a global version and a fibre-wise version. Under certain conditions these are equivalent, so one can transfer fibre-wise monoidal structures to the total category. We will give some examples demonstrating the utility of this construction in applied category theory and categorical algebra.

The talk is based on this paper:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

This, in turn, had its roots in our work on network models, a setup for the compositional design of networked systems:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models.


Star-Autonomous Envelopes

21 April, 2020

Shulman_slide

In the fourth talk of the ACT@UCR seminar, Michael Shulman told us how to create nice string diagams for any closed symmetric monoidal category.

Mike had to teach right after his talk, but he rejoined us for discussions later at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2022nd.3A.20Michael.20Shulman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video of his talk here, or watch the video here:

• April 22, Michael Shulman, Star-autonomous envelopes.

Abstract. Symmetric monoidal categories with duals, a.k.a. compact monoidal categories, have a pleasing string diagram calculus. In particular, any compact monoidal category is closed with [A,B] = (A* ⊗ B), and the transpose of A ⊗ B → C to A → [B,C] is represented by simply bending a string. Unfortunately, a closed symmetric monoidal category cannot even be embedded fully-faithfully into a compact one unless it is traced; and while string diagram calculi for closed monoidal categories have been proposed, they are more complicated, e.g. with “clasps” and “bubbles”. In this talk we obtain a string diagram calculus for closed symmetric monoidal categories that looks almost like the compact case, by fully embedding any such category in a star-autonomous one (via a functor that preserves the closed structure) and using the known string diagram calculus for star-autonomous categories. No knowledge of star-autonomous categories will be assumed.

His talk is based on this paper:

• Michael Shulman, Star-autonomous envelopes.

This subject is especially interesting to me since Mike Stay and I introduced string diagrams for closed monoidal categories in a somewhat ad hoc way in our Rosetta Stone paper—but the resulting diagrams required clasps and bubbles:


beta_reduction

This is the string diagram for beta reduction in the cartesian closed category coming from the lambda calculus.


Structured Cospans and Petri Nets

6 April, 2020

\;

This talk on structured cospans and Petri nets is the second of a two-part series, but it should be understandable on its own. The first part is on structured cospans and double categories.

I gave this second talk at the MIT Categories Seminar. People discussed the talk at the Category Theory Community Server.

You can see the slides here and watch a video here:

Structured cospans and Petri nets

Abstract. “Structured cospans” are a general way to study networks with inputs and outputs. Here we illustrate this using a type of network popular in theoretical computer science: Petri nets. An “open” Petri net is one with certain places designated as inputs and outputs. We can compose open Petri nets by gluing the outputs of one to the inputs of another. Using the formalism of structured cospans, open Petri nets can be treated as morphisms of a symmetric monoidal category—or better, a symmetric monoidal double category. We explain two forms of semantics for open Petri nets using symmetric monoidal double functors out of this double category. The first, an operational semantics, gives for each open Petri net a category whose morphisms are the processes that this net can carry out. The second, a “reachability” semantics, simply says what these processes can accomplish. This is joint work with Kenny Courser and Jade Master.

The talk is based on these papers:

• John Baez and Kenny Courser, Structured cospans.

• John Baez and Jade Master, Open Petri nets.

• Jade Master, Generalized Petri nets.

I’ve blogged about open Petri nets before, and these articles might be a good way to start learning about them:

Part 1: the double category of open Petri nets.

Part 2: the reachability semantics for open Petri nets.

Part 3: the free symmetric monoidal category on a Petri net.