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: Para construction questions

Nathaniel Virgo (Dec 05 2021 at 05:04):

I tried to work through a simple example of the Para construction, but I was surprised to find it didn't seem to work in the way I expected. I want to first check that my understanding is correct, and, if it is, ask whether there could be another version of the Para construction that does work in the way I imagined.

My understanding is that the Para construction lets us consider morphisms in one category that are parametrised by objects in another. In statistics we often want to consider families of probability measures that are parametrised by manifolds, so I figured a simplified version of that would be a nice place to start.

So let $\textbf{Smooth}$ be the category where objects are $\mathbb{R}^n$ and morphisms are smooth maps, with a monoidal product given by the Cartesian product of sets. And let $\textbf{FinStoch}$ be the category where objects are finite sets and morphisms are Markov kernels, a.k.a. conditional probability distributions.

The Para construction starts with an actegory, which is a functor $\bullet\colon \mathscr{M}\times \mathscr{C} \to \mathscr{C}$ (where in this case $\mathscr{M}$ is $\mathbf{Smooth}$ and $\mathscr{C}$ is $\mathbf{FinStoch}$), plus some natural transformations and some equations. Then we define a bicategory where a 1-cell is a parametrised map $\Theta\bullet A \to B$ in $\mathscr{C}$, where $\Theta$ is an object of $\mathscr{M}$ and $A$ and $B$ are objects of $\mathscr{C}$.

If we think informally about a Markov kernel from a finite set $A$ to a finite set $B$, parametrised by $\Theta=\mathbb{R}^n$, then we should expect this to be a map from $\mathbb{R}^n\times A$ to probability distributions over $B$. This is the sort of thing that I initially expected to get out of the Para construction.

However, whatever we define the functor $\bullet$ to be, $\theta\bullet A$ has to be a finite set, and so a map $\Theta\bullet A \to B$ has to be a map from only a finite set to probability distributions over $B$. But $\mathbb{R}^n\times A$ isn't a finite set, so it seems that no matter how we define $\bullet$, we can't do it in such a way that 1-cells of the Para construction correspond to parametrised Markov kernels in the way I was expecting.

If I'd allowed myself to consider Markov kernels between general measurable spaces instead of only finite sets then there would have been no problem, because $\mathbb{R}^n$ can be made into a measurable space in a canonical way, so that a Markov kernel $\Theta\bullet A \to B$ would indeed be a map in $\mathscr{C}$. So it seems that the root of the issue is that in order to produce $\mathscr{M}$-parametrised maps between $\mathscr{C}$-objects via the Para construction, the objects of $\mathscr{C}$ need to be in some sense "big enough" to contain all the information contained in objects of $\mathscr{M}$. (That's obviously a very informal statement, but maybe there is some way to make it more formal.)

My first question is, am I on the right track so far? It seems quite possible that I'm thinking about this in the wrong way, and it would be nice to be corrected if so.

If I'm right about the above, I'm wondering if there might be a different version of the Para construction, which would still produce a bicategory in the same way, but which would also work for examples like this one. It occurs to me that it might work if, instead of a functor $\mathscr{M}\times\mathscr{C}\to\mathscr{C}$, we instead built it on a functor $\mathscr{M}\times\mathscr{C}^\text{op}\times\mathscr{C}\to\textbf{Set}$, or equivalently $M\to \operatorname{Prof}(\mathscr{C},\mathscr{C})$. The idea is that a Markov kernel parametrised by $\Theta=\mathbb{R}^n$ shouldn't be described by a single Markov kernel between finite sets, but rather a whole set of them, one for each point in $\Theta$. Then we would need a bunch of (extra)natural transformations and probably some equations, to describe how these maps should compose. (We might also want to work in an enriched context, so that we would end up with a functor $\mathscr{M}\times\mathscr{C}^\text{op}\times\mathscr{C}\to\mathscr{V}$ instead. In my example we might want $\mathscr{V}$ to be $\mathbf{Meas}$, the category of measurable spaces.)

I could probably work out the details of that with a bit of work, but it seems also like something that might have been done, so I figured I would ask about it here. Does the above make sense, and is there an existing construction along these lines that could be used to build a version of the Para construction that would work in this case?

Matteo Capucci (he/him) (Dec 05 2021 at 09:52):

Hey! What you're describing has been studied by @Toby Smithe as the 'Proxy' construction

Matteo Capucci (he/him) (Dec 05 2021 at 09:53):

The two constructions are equivalent in some sense, but Para parametrises internally while Proxy does it externally

Matteo Capucci (he/him) (Dec 05 2021 at 09:53):

I think the most complete reference for the construction at the moment are the slides of my CT21 talk about these two constructions

Matteo Capucci (he/him) (Dec 05 2021 at 09:54):

You can find them on my website under 'Work'

Nathaniel Virgo (Dec 05 2021 at 10:19):

Great, thanks!

Is a video of the talk available anywhere? (The slides look very clear, but it would be great to watch the talk if it's possible.)

Matteo Capucci (he/him) (Dec 05 2021 at 10:26):

Uh, that's a good question, I think the videos are expected to become public around Christmas (don't ask me why)

Matteo Capucci (he/him) (Dec 05 2021 at 10:27):

Anyway in my talk I didn't really manage to talk about Proxy, alas

Matteo Capucci (he/him) (Dec 05 2021 at 10:27):

I can send you some notes in the next days, they're eventually gonna come out as a paper anyway

Nathaniel Virgo (Dec 05 2021 at 10:32):

That would be great!

Nathaniel Virgo (Dec 09 2021 at 07:53):

By the way, I have another Para construction question, maybe a bit more basic than my previous one. Basically I'd like to know whether there are any nice practical examples where the actegory structure doesn't arise from a monoidal functor.

To elaborate on what I mean: in my original post above I tried to parametrise morphisms of $\mathbf{FinStoch}$ by smooth maps, and it didn't work. However, it would have worked if instead of $\mathbf{FinStoch}$ I'd used $\operatorname{Kl} D$, the Kleisli category of the distribution monad. In that case I can define a monoidal functor $I\colon\mathbf{Smooth}\to \operatorname{Kl} D$ that embeds $\mathbf{Smooth}$ into $\operatorname{Kl} D$ by mapping to their underlying sets, and maps morphisms of $\mathbf{Smooth}$ to their underlying functions, seen as deterministic Markov kernels. I can then define

$${-}\bullet{=} \,\,=\,\, I({-})\otimes {=}.$$

I think $I$ being monoidal should give me all the natural transformations I need to make that into an actegory.

My question is just whether there are nice examples of the Para construction where the functor $\bullet \colon \mathcal{M}\times \mathcal{C}\to\mathcal{C}$ doesn't arise from a monoidal functor in this way, either because $\mathcal{C}$ doesn't have a nice monoidal structure or just because $\bullet$ doesn't factor through a monoidal functor $I\colon \mathcal{M}\to\mathcal{C}$ in this way.

Matteo Capucci (he/him) (Dec 10 2021 at 22:52):

We have a result that any actegory which obeys some basic compatibility between the action and the monoidal product on the category being acted upon arises from a strong monoidal functor as you observe. So if you want examples where this is not true get any action which doesn't satisfy the axiom $m\bullet (x \otimes y) \cong (m \bullet x) \otimes y$

Matteo Capucci (he/him) (Dec 10 2021 at 22:54):

In particular you need the above condition to make Para monoidal itself (you get a monoidal bicategory)

Matteo Capucci (he/him) (Dec 10 2021 at 22:54):

(I'm assuming M is symmetric here, otherwise things get a bit more delicate)

Matteo Capucci (he/him) (Dec 10 2021 at 22:59):

I guess an example could be a distributive category (monoidal tensor distributing over coproducts): the self left action of the tensor doesn't satisfy the above wrt to the monoidal structure of coproducts

Matteo Capucci (he/him) (Dec 10 2021 at 23:00):

Like (Set, 1, x) acting on (Set, 0, +)

Matteo Capucci (he/him) (Dec 10 2021 at 23:02):

BTW I promised you notes but I realized the ones I have atm are worse than the slides I pointed at, especially regarding proxy. So if you have any questions after consulting them let me know. Hopefully the paper will be out around February..?

Nathaniel Virgo (Dec 11 2021 at 06:14):

Thank you for that, and no worries about the notes, I'll look forward to the paper.

By the way, here's what I think is kind of a neat way to think about the string diagrams for Para. In the slides you mentioned that formalising those diagrams is still to be done, so maybe this could be helpful.

The coherence axioms for an actegory are basically the same as for a monoidal category (why does no-one ever write them down?), so there should be a string diagram language for actegories that looks like this:

image.png

Each object is of the form $M_1 \otimes \dots \otimes M_n \bullet C$ for $M_1, \dots, M_n \in \mathcal{M}_0$, $C\in\mathcal{C}_0$. The coherence axioms mean there's no ambiguity in omitting the brackets (up to isomorphism), so we can draw them as parallel wires. There's always exactly one $\mathcal{C}$ wire but a varying number of $\mathcal{M}$ wires because of the monoidal structure on $\mathcal{M}$. The diagram as a whole expresses a morphism in $\mathcal{C}$.

Then having defined this graphical calculus for actegories we can express the Para construction in terms of it: 1-cells are given by pairs

image.png

with composition law

image.png

and 2-cells as $\mathcal{M}$-morphisms

image.png

This looks the same as the diagrams you draw for the Para construction, except that the blue parametrising wires are horizontal, in parallel with the black ones instead of perpendicular to them. But I think you can convert between the two just by "shearing" the diagrams, turning vertical lines into diagonal ones or vice versa.

Of course this doesn't add anything new beyond the diagrams you already draw for the Para construction, I just thought it's a neat way to think about where they come from, and maybe it suggests a way to formalise them, by formalising the graphical calculus for actegories first.

Nathaniel Virgo (Dec 11 2021 at 06:54):

On another note: it sort of seems as if Proxy is less general than the thing I was hypothesising about in my original post. From the definition on slide 20, it looks like you can only parametrise objects of $\mathcal{C}$ by objects of $\mathcal{V}$, which $\mathcal{C}$ is enriched in. This probably would work for the example in my OP, because I think you can regard $\mathbf{FinStoch}$ as enriched in $\mathbf{Smooth}$, but it wouldn't be too hard to change the example so that that wouldn't work.

e.g. take $\mathbf{CountableStoch}$, where objects are countable sets, in place of $\mathbf{FinStoch}$, while keeping $\mathbf{Smooth}$ as I defined it, with the objects being finite-dimensional vector spaces. I think $\mathbf{CountableStoch}$ is not enriched in $\mathbf{Smooth}$. It makes sense to consider Markov kernels between countable sets that are parametrised by finite-dimensional manifolds, but if my understanding is correct I think neither Para nor Proxy can be used to construct them.

But on the other hand I'm not sure - the definition on slide 20 makes sense to me, but it will take me some work to unpack the examples, mostly because I've never worked through the definition of changing the base of enrichment.

If this issue is real I wonder if it's fixable. It feels like there should be a common generalisation of Para and Proxy where these examples do work. Perhaps that would be something new.

Nathaniel Virgo (Dec 11 2021 at 07:11):

Thinking out loud, I guess if you had a monoidal functor $I\colon \mathcal{M}\to\mathcal{V}$ that can be thought of as embedding the parametrising category $\mathcal{M}$ into $\mathcal{V}$, then maybe you could form something like the Proxy construction except that

$$\mathsf{Proxy}_I(\mathcal{C})(X,Y) = \sum_{M:\mathcal{M}} \mathcal{V}(I(M),\mathcal{C}(X,Y)).$$

If that works out I think it would work for the example in my previous post, if we let $\mathcal{V}=\mathbf{Set}$ (or Meas etc). Maybe that's what I was looking for.

Matteo Capucci (he/him) (Dec 11 2021 at 12:51):

Re: the diagrams, that looks very plausible, it's also the way I think about it when I want to try to be 'formal'. Also when you can actually draw string diagrams for $C$ you want to be in the situation I described above, which implies the action is actually just a monoidal functor into $C$. What I want to say is that then $m \bullet x$ is really a tensor in the usual sense, so already captured by string diagrams with functorial boxes. Neat!

There at least two others contenders for the formalisation of the diagrams

1. One is to make Para into a double category whose horizontal morphisms are parametrised morphisms, vertical morphisms are morphisms in C and squares are reparametrisations (hence morphisms in $M$). You should be able to tile string diagrams the way we draw them with these squares. You can also have corner structures (which I think are hidden in your proposal? I don't know if this is a feature or a bug) which are given by particular adjunctions to the functor $M \to C$ emboding an action. Then I guess one falls back to this https://arxiv.org/abs/1612.02762
2. The other one is to embed this diagrams in Tamb, as described here https://arxiv.org/abs/2002.11480. They would look a lot like your diagrams, since objects of $M$ and $C$ get mixed by the action, which gives suitable Tambara modules. Keep in mind these are string diagrams for bicategories, hence regions between wires are 'coloured' by the domain and codomain of the Tambara modules the wires represent. The advantage of this approach is that we get to decompose diagrams of optics automatically, and the story fits together without much fanfare. It's almost too trivial!

Matteo Capucci (he/him) (Dec 11 2021 at 12:53):

Re: the generality of Proxy. One can see Proxy as a Para construction by freely completing a given enriched category with V-tensors (e.g. for Set-enriched cats, this is the coproduct completion). Then the V-tensor is just another action and $Para \cong Proxy$.
Then you can get what you propose by first doing the above and then pulling back the V-tensor along $I$.

Jules Hedges (Dec 11 2021 at 19:18):

We (at Strathclyde) draw string diagrams in $\mathbf{Para}_{\mathcal M} (\mathcal C)$ where the string diagrams in $\mathcal M$ are at right angles to the (necessarily linear if it's just a category) "string diagrams" in $\mathcal C$. That causes the correct composition law to appear by magic: when you put things in $\mathcal C$ in sequence, you "automatically" take a tensor product in $\mathcal M$ by putting the wires in parallel. My strong gut feeling is that this choice is "canonical" in some topological sense

Nathaniel Virgo (Dec 12 2021 at 00:34):

If it can be made into a double category then drawing the $\mathcal{M}$ wires perpendicular to the $\mathcal{C}$ ones seems like it should be canonical when viewing it that way. I guess it's a double category with a single object? (This makes sense to me when $\mathcal{C}$ is monoidal and the action is a monoidal functor, but it seems a bit weird when $\mathcal{C}$ is just a category, because you need to have at most one $\mathcal{C}$ wire going from left to right in any given diagram.)

Matteo Capucci (he/him) (Dec 12 2021 at 12:43):

How would you make it into a double category with a single object?

Matteo Capucci (he/him) (Dec 12 2021 at 12:52):

Given a monoidal $\mathcal M$-biactegory $\mathcal C$ (meaning it has both a left and right action which 'agree' up to coherent isomorphism, and moreover they agree with a monoidal product on $\mathcal C$ -- this is the categorification of a bimodule algebra over a ring, in a sense), I know I can make it into a double (bi)category where $\mathbb B \mathcal M$ is the horizontal (bi)category, $\mathbb B \mathcal C$ is the vertical (bi)category and a square delimited by $(M, X, N, Y)$ are biparametrised morphisms $M \bullet X \to Y \bullet N$.

Then Para 'is' the vertical slice over $I = I$ and Copara 'is' the vertical coslice under $I=I$. I put 'is' in scary quotes bc the slices give you doubly indexed categories, not bicategories. I stop working it out after I stated this proposition and the fact horizontal composition, so it's a bit muddy from here.

Nathaniel Virgo (Dec 13 2021 at 12:33):

I was sort of guessing about it being a double category with a single object. We want to draw diagrams where there are vertical and horizontal lines, but the spaces between them are all white, so a single object would make sense.

Here's what I was imagining - I've no idea if it really works or if so what conditions are needed to make it all coherent. It seems to make more sense if we consider biparametrised maps, so that morphisms can have outputs in $\mathcal{M}$ as well as inputs in $\mathcal{M}$. Then, at least intuitively, we should be able to define a double category with a single object, where vertical morphisms (which I draw as horizontal lines) are objects of $\mathcal{C}$, horizontal morphisms (which I draw as vertical lines) are objects of $\mathcal{M}$. Vertical composition is the monoidal product in $\mathcal{C}$, horizontal composition is the monoidal product in $\mathcal{M}$, and a square is a biparametrised map. If that all works nicely, then Jaz Myers' graphical notation for double categories should give us diagrams that look like this:

image.png

The places where wires cross are biparametrised maps that are identities for both categories.

If we want to only consider parametrised morphisms rather than biparametrised ones then (assuming this works) we could do it by restricting ourselves to squares that represent morphisms whose output in $\mathcal{M}$ is the unit object, plus the "wire crossing" squares and anything that can be formed by composing the above. Then we would get diagrams exactly like the ones you guys draw. But it's a bid odd for the squares to be generated by two distinct sets of things, so maybe a double category isn't actually quite the right structure here, at least for this particular construction.

Nathaniel Virgo (Dec 13 2021 at 22:51):

There is a construction that's quite similar to the above, where you take any monoidal category and form a double category with one object, where the horizontal and vertical morphisms are both objects of the original category and squares are maps $A\otimes X \to B\otimes Y$. I can't remember what it's called though.

edit: I found it, it's called the [[quintet construction]]. It works for 2-categories and not just monoidal categories, but in the case of a monoidal category the double category will only have one object. The quintet construction seems quite relevant in the case you described earlier, where $\bullet$ "really is" a tensor.

Matteo Capucci (he/him) (Dec 14 2021 at 10:42):

Nathaniel Virgo said:

I was sort of guessing about it being a double category with a single object. We want to draw diagrams where there are vertical and horizontal lines, but the spaces between them are all white, so a single object would make sense.

Here's what I was imagining - I've no idea if it really works or if so what conditions are needed to make it all coherent. It seems to make more sense if we consider biparametrised maps, so that morphisms can have outputs in $\mathcal{M}$ as well as inputs in $\mathcal{M}$. Then, at least intuitively, we should be able to define a double category with a single object, where vertical morphisms (which I draw as horizontal lines) are objects of $\mathcal{C}$, horizontal morphisms (which I draw as vertical lines) are objects of $\mathcal{M}$. Vertical composition is the monoidal product in $\mathcal{C}$, horizontal composition is the monoidal product in $\mathcal{M}$, and a square is a biparametrised map. If that all works nicely, then Jaz Myers' graphical notation for double categories should give us diagrams that look like this:

image.png

The places where wires cross are biparametrised maps that are identities for both categories.

If we want to only consider parametrised morphisms rather than biparametrised ones then (assuming this works) we could do it by restricting ourselves to squares that represent morphisms whose output in $\mathcal{M}$ is the unit object, plus the "wire crossing" squares and anything that can be formed by composing the above. Then we would get diagrams exactly like the ones you guys draw. But it's a bid odd for the squares to be generated by two distinct sets of things, so maybe a double category isn't actually quite the right structure here, at least for this particular construction.

It seems we are describing the same double category!

Matteo Capucci (he/him) (Dec 14 2021 at 10:42):

Nathaniel Virgo said:

edit: I found it, it's called the [[quintet construction]]. It works for 2-categories and not just monoidal categories, but in the case of a monoidal category the double category will only have one object. The quintet construction seems quite relevant in the case you described earlier, where $\bullet$ "really is" a tensor.

YES! Amazing

Chad Nester (Dec 14 2021 at 13:07):

fwiw the "crossing squares" you describe are related to the concept of a monoidal double category. They are present in the free cornering (proarrow equipment) on a symmetric monoidal category. https://www.ioc.ee/~cneste/files/nester-2021-the-structure-of-concurrent-process-histories.pdf

Nathaniel Virgo (Dec 14 2021 at 13:33):

What does a monoidal double category with a single object work out to be? I'm wondering if that might be just the structure that's needed in order for the wires to be "not in the same plane" and thus able to cross over each other like that. (Or is that already exactly what you meant?)

Chad Nester (Dec 14 2021 at 13:36):

I think that's right.

Chad Nester (Dec 14 2021 at 13:38):

I suspect having the "crossing squares" exist and satisfy the obvious "sliding" equations is exactly what it means to be a monoidal double category, but haven't bothered to work out both directions yet (one of them is in that paper).

Chad Nester (Dec 14 2021 at 13:39):

To clarify: a monoidal strict double category with a single object

Nathaniel Virgo (Dec 14 2021 at 13:45):

Is a wire crossing over another wire different from crossing under it? I'm wondering if you can have knots, like this:

image.png

If that can happen then maybe a symmetry could be added to get rid of them for things like the Para diagrams where the difference isn't needed.

Chad Nester (Dec 14 2021 at 14:14):

In my work the crossings are flat. I imagine you could construct examples of the other thing though.

Matteo Capucci (he/him) (Dec 17 2021 at 09:41):

should crossings corresponds to maps $m \bullet x \to x \bullet m$? i.e. mixing left and right actions

Nathaniel Virgo (Dec 18 2021 at 04:55):

I think so. At least, that's how I was thinking about it in my original vague thought about the quintet construction.

I think of the quintet construction as doing the "shear transformation" on string diagrams that I mentioned earlier, turning a string diagram like this

image.png

into one like this.

image.png

Now if we have all the nice conditions that make $\bullet$ into a tensor then presumably we'd end up with string diagrams that look like this

image.png

Here I've drawn coparametrised maps as morphisms $m\times x \to y\times n$ rather than $m\times x \to n\times y$ so that blue wires can always move diagonally downwards from the top left to the bottom right. If we used something like the quintet construction to "pull the blue wires vertical" we'd end up with this

image.png

(I say "something like" the quintet construction because we need to make sure it's always the blue wires that end up vertical and the black ones horizontal, which presumably needs a bit of extra bookkeeping on top of what the quintet construction already does.)

In the first of those diagrams the wire crossings are morphisms $m\bullet x \to x\bullet m$ as you say, so that's what they should correspond to in the double category version as well, assuming all this handwaving can be cashed out.

I'm not really sure how this fits with the monoidal double category idea - I don't yet clearly see how they relate.

I guess though that if we only have structure maps $m\bullet x \to x\bullet m$ and not $x\bullet m \to m\bullet x$ then maybe we can say there's only one kind of crossing and then hopefully you can't get knots. It might make sense to only have that one kind of map, because of the requirement that the blue wires always move diagonally downwards. (But again this is all just vague conjecture based on intuition about how the diagrams should look - I haven't worked any of it out formally.)

Matteo Capucci (he/him) (Dec 19 2021 at 11:48):

Mmh that transformation from string diagrams in Tamb to string diagrams in the quintet of $\bullet$(1) is really intriguing... As you say, there's something going on with book-keeping, but I think the most important takeaway is that they're the same diagrams since the transformation is purely topological.
This makes me conjecture this transformation is actually an embedding of the quintet of $\bullet$ into Tamb...

(1) I'm using 'quintet of $\bullet$' to denote the quintet construction applied to bipara. There's a bit to say about the data of this: the data is really that of a $\mathcal M$-biactegory, where 'bi' denotes a pair of a left and right compatible actions (you have a rebracketing structure iso $m \bullet (x \bullet n) \to (m \bullet x) \bullet n$, which is actually a [[distributive law]] between $m \bullet -$ and $- \bullet n$). I see you probably already figured this out. As a further aside, this is also the setting where it's most natural to talk about tensor products of actegories, hence of monoidal actegories. Therefore the monoidal structure @Chad Nester is talking about is easily put there (and needs to be there in most practical applications).

Matteo Capucci (he/him) (Dec 19 2021 at 11:51):

Nathaniel Virgo said:

I guess though that if we only have structure maps $m\bullet x \to x\bullet m$ and not $x\bullet m \to m\bullet x$ then maybe we can say there's only one kind of crossing and then hopefully you can't get knots. It might make sense to only have that one kind of map, because of the requirement that the blue wires always move diagonally downwards. (But again this is all just vague conjecture based on intuition about how the diagrams should look - I haven't worked any of it out formally.)

Indeed! When I talk about structure morphisms nowadays, I always assume they're invertible because that makes life so much easier, but they don't need to!