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.
Paolo Perrone (Jun 04 2020 at 15:13):Hey all,
This is the discussion thread of Sam Staton's talk, "Categorical models of probability with symmetries".
The talk, besides being on Zoom, is livestreamed here: https://youtu.be/eTa7-nW9AE8
Paolo Perrone (Jun 04 2020 at 19:25):Date and time: Friday, 5 Jun, 12h UTC.
Sam Staton (Jun 05 2020 at 11:56):My slides: http://www.cs.ox.ac.uk/people/samuel.staton/2020cps.pdf
Paolo Perrone (Jun 05 2020 at 11:59):We start in 30 seconds!
Oliver Shetler (Jun 05 2020 at 12:40):Hi Sam. I was unaware that graphons are such well studied objects. When you have time, can you point out some introductory resources on graphon theory? Also any results in category theory that you think are especially significant.
Sam Staton (Jun 05 2020 at 13:07):Hi Oliver Shetler. An overview reference I like is https://arxiv.org/pdf/1312.7857.pdf . Another introduction is Tao's blog https://terrytao.wordpress.com/2014/10/12/additive-limits/ which is from a very different perspective.
Graphons have been rediscovered in many different domains by many people over the years. They're considered everywhere from model theory, combinatorics, to data science.
The reference to consistent local graph models in my talk was https://arxiv.org/abs/math/0408173 , although perhaps the ideas go back to the 1970s.
Oliver Shetler (Jun 05 2020 at 13:08):Thank you!
Tobias Fritz (Jun 05 2020 at 14:20):Sam, there was a lot of intriguing content in your talk and this will take time to process, but for now here's one more question. You had mentioned that natural families of functions are deterministic morphisms. What is the general precise statement here, and what definition of deterministic morphism does it use? I guess that it applies in at least every presheaf category, right? Is it your own observation, and is there a reference?
Tobias Fritz (Jun 05 2020 at 14:35):What I mean is that if is a category, then we can consider two kinds of morphisms between presheaves . One is just arbitrary families of functions indexed by the objects of , and the other one is only those families which form natural transformations. What you seem to be saying is that using arbitrary families of functions as morphisms, we get a Markov category in which the natural transformations coincide with the deterministic morphisms. If that's what it is then it's really neat! (And of course I imagine that it well predates the theory of Markov categories.)
Sam Staton (Jun 05 2020 at 14:40):Interesting idea! I hadn't thought of that but it might work!
I mainly meant I would set things up as a Kleisli category or a Freyd category, where there are two given categories, which I was calling deterministic and probabilistic. Perhaps that was a bit unclear.
But there is a simple theorem there, which is that all the _definable_ deterministic programs are interpreted as _natural_ transformations, i.e. the naturality is satisfied by everything definable, which is a kind of invariance property that shows that some nasty non-natural maps (such as <, sin(-)=cos(-)) are not definable.
Tomáš Gonda (Jun 05 2020 at 14:53):That was indeed a very interesting talk and I also need some time to process it fully and relate to what I've been thinking about.
The most immediate question I have related to the combinatorial model of probability, which I think I didn't fully grasp. How should I think of (or interpret) the objects X constructed in this fashion - as families of sets indexed by natural numbers? What does n represent here? Also, just to make sure, X is a functor and FinSet has all functions as morphisms, right?
Peter Arndt (Jun 05 2020 at 14:56):Sam Staton said:
Interesting idea! I hadn't thought of that but it might work!
I mainly meant I would set things up as a Kleisli category or a Freyd category, where there are two given categories, which I was calling deterministic and probabilistic. Perhaps that was a bit unclear.
The non-natural transformations can be described as non-deterministic maps in a monad sense: If we denote by the inclusion of the discrete category with just the objects of , then non-natural transformations are exactly . But by adjointness this is , so non-natural transformations are non-deterministic maps with respect to the "right Kanextension$$\circ$$precomposition with i"-monad.
Is that what you two were thinking ?
Sam Staton (Jun 05 2020 at 15:00):Hi Tomáš Gonda. Yes, that's right. X is a functor and FinSet has all functions as morphisms. n represents the number of urns that have been created, or the number of times "beta" has been used. Naturality under the permutations in FinSet means that the urns are indistinguishable -- you can't look inside them or ask whether one was made before another. Naturality under inclusion maps in FinSet means that you can't ask "how many urns have been made so far".
Sam Staton (Jun 05 2020 at 15:17):Hi Peter Arndt, that's a good idea, and maybe what Tobias was thinking. But I just meant that if we have a monad on a presheaf category, then deterministic expressions would be interpreted as a plain natural transformation and probabilistic expression would be interpreted as a Kleisli natural transformation. And as I wrote to Tomas, the naturality is itself saying an invariance or equivariance property which is already a bit interesting in the deterministic case.
Manuel Bärenz (Jun 05 2020 at 18:20):Hi @Sam Staton , I enjoyed your talk a lot. A functional programmer may wonder: An urn represents a global state. For example in Haskell, this is modelled with a state monad. While probability monads are typically commutative, the state monad isn't, and that's the complication in commuting statements that use the state effect. In your example, that may not be relevant, but I'm wondering whether there is a general theory about how probability interplays with other effects? E.g. is there a theory on how to commute a state monad transformer with a probability monad transformer?
Manuel Bärenz (Jun 05 2020 at 18:33):"Getting a new name" can also be thought as an effect (in Haskell, this monad is usually called "Accum", see http://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Accum.html), as can the memoization function. Is there something going on between effects and probability? (Note that both State and Accum can be represented as polynomial functors (maybe even Lawvere theories, but I'm not sure about that))
Manuel Bärenz (Jun 05 2020 at 18:56):Hah, I should have listened to the questions first :D of course Gordon asked about State. So if noncommutativity is such a problem, we can still look at the Accum monad with a commutative monoid as internal state, or something like that. Your "fresh name" effect is commutative if you disallow inspection of the actual name beyond equality comparison. Memoization is also commutative and even idempotent. So what can we do here?
Manuel Bärenz (Jun 05 2020 at 19:03):Another question. I asked a similar question in Peter's talk, but I'm realising now that it might be relevant to your topic as well. In homotopy type theory, we can express symmetries as groupoid types, or higher inductive types. Does it make sense to use these to express symmetries, and can you extract a good model from that?
Sam Staton (Jun 05 2020 at 21:29):Hi Manuel Bärenz! I agree, this interplay between state and probability is very interesting. To show that Polya's urn behaves in a commutative way is a bit of work because, as you observed it involves state, and state is not usually commutative. From a programming perspective, de Finetti's theorem says that if you have a module for the get/sample interface that uses state but is still commutative, then you can implement it without state, just using probability.
I also agree that name generation and memoization are important examples of state-like behaviour that are commutative. My current conjecture is that they are canonical with this property, in a certain sense. Also, Dario Stein is currently looking at name generation from a probability point of view.
For type theory, it might be interesting but I haven't really thought about it. I know Harry Crane was looking at HOTT + probability at one point. Bas Spitters may also have something to say if he is around.
Paolo Perrone (Jun 05 2020 at 21:30):Hi all! Here is the recording:
https://youtu.be/8Y0b7e4OIUQ
Bas Spitters (Jun 06 2020 at 09:42):Hi @Sam Staton is the internal logic of the Rado topos understood?
Tobias Fritz (Jun 06 2020 at 13:59):@Sam Staton, if you don't mind I'd have a question that's not directly related to your talk (as far as I can see). The nLab states that if the underlying functor of a Freyd category has a right adjoint, then the Freyd category arises as a Kleisli category. Do you know of a reference for that? Or is it folklore, perhaps because it's sufficiently obvious?
Sam Staton (Jun 06 2020 at 20:09):Hi Bas Spitters! The topos is Boolean, and AC fails badly. It is quite like Schanuel topos (nominal sets, FM set theory) in this way, if you've ever looked at that. Also, as I mentioned briefly, if I write for the object of vertices, then the powerobject comprises all definable sets (with finite parameters) in the language of graphs, in the sense of model theory. So that's nice.
Sam Staton (Jun 06 2020 at 20:20):Hi Tobias Fritz, in general, if an identity-on-objects functor has a right adjoint, then it is a Kleisli adjunction. (I remember, as a student, finding it surprisingly hard to find this in a book. Maybe someone knows a nice reference.) For Freyd categories, the literature is mostly focused on _closed_ Freyd categories , which ask that has a right adjoint for all A.
Tobias Fritz (Jun 06 2020 at 21:50):Sam Staton said:
in general, if an identity-on-objects functor has a right adjoint, then it is a Kleisli adjunction.
Wow! That is obvious upon thinking about it, but somehow still quite surprising to me. Thanks!