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: event: ACT@UCR

Topic: April 15th: Jules Hedges

Joe Moeller (Apr 10 2020 at 17:33):

Next up in this seminar is @Jules Hedges

Open games: the long road to practical applications

Abstract: I will talk about open games, and the closely related concepts of lenses/optics and open learners. My goal is to report on the successes and failures of an ongoing effort to try to realise the often-claimed benefits of categories and compositionality in actual practice. I will introduce what little theory is needed along the way. Here are some things I plan to talk about:
— Lenses as an abstraction of the chain rule
— Comb diagrams
— Surprising applications of open games: Bayesian inference, value function iteration
— The state of tool support
— Open games in their natural habitat: microeconomics
— Sociological aspects of working with economics

Jules Hedges (Apr 10 2020 at 19:07):

:wave:

John Baez (Apr 10 2020 at 20:23):

Send us your slides, @Jules Hedges!

Jules Hedges (Apr 10 2020 at 20:25):

Oh right. I need to make a couple of changes from my first run. If it's urgent, I'll do it tomorrow

sarahzrf (Apr 11 2020 at 19:07):

:magnifying_glass:

sarahzrf (Apr 11 2020 at 19:07):

optics gang

John Baez (Apr 13 2020 at 19:55):

Here are the slides to Jules Hedges' talk. Don't forget: his talk is on Wednesday April 15th at 5 pm UTC, which is 10 am Pacific Time or 1 pm Eastern Time in the United States. To get to it, go here: https://ucr.zoom.us/j/607160601

$\;$

• Jules Hedges, Open games: the long road to practical applications.

Abstract. I will talk about open games, and the closely related concepts of lenses/optics and open learners. My goal is to report on the successes and failures of an ongoing effort to try to realise the often-claimed benefits of categories and compositionality in actual practice. I will introduce what little theory is needed along the way. Here are some things I plan to talk about:

— Lenses as an abstraction of the chain rule

— Comb diagrams

— Surprising applications of open games: Bayesian inference, value function iteration

— The state of tool support

— Open games in their natural habitat: microeconomics

— Sociological aspects of working with economics

Daniel Geisler (Apr 13 2020 at 20:39):

Howdy @Jules Hedges, I'm looking forward to your talk on open games. You discuss lens and the chain rule. Has your work taken you to Faà di Bruno's formula and it's properties of a Hopf algebra? Faà di Bruno's formula is at the heart of my research. I'm interested in games as the ultimate abstraction of numbers and would love to hear more.

John Baez (Apr 15 2020 at 16:48):

Hi! There's a new, more user-friendly version of Jules' talk slides here:

http://math.ucr.edu/home/baez/mathematical/ACTUCR/Hedges_Open_Games.pdf

Leah Neukirchen (Apr 15 2020 at 16:55):

Is it possible to open the zoom for web browsers?

Dan Frumin (Apr 15 2020 at 16:59):

Leah Neukirchen said:

Is it possible to open the zoom for web browsers?

It works on Chromium, although you have to insist on not wanting to install their app.

Leah Neukirchen (Apr 15 2020 at 17:00):

Dan Frumin said:

Leah Neukirchen said:

Is it possible to open the zoom for web browsers?

It works on Chromium, although you have to insist on not wanting to install their app.

I don't see the direct link from Chromium, and when I edit the URL I get to a login page.

Reid Barton (Apr 15 2020 at 17:00):

Is it still possible? On April 3 I tried to open a zoom meeting in my web browser and I couldn't get it to work even though it had worked for me before then.

Leah Neukirchen (Apr 15 2020 at 17:01):

argh, deny twice works. and then i need a zoom account?

Reid Barton (Apr 15 2020 at 17:01):

Hmm, maybe I just didn't try hard enough.

Leah Neukirchen (Apr 15 2020 at 17:05):

finally

sarahzrf (Apr 15 2020 at 17:11):

optics actually generalize considerably further than even just monoidal categories :)

sarahzrf (Apr 15 2020 at 17:17):

...i think there might be a link between the stuff my talk is about and the kind of optics you want to use, jules

sarahzrf (Apr 15 2020 at 17:18):

...well, that link might just be monoidal products :sweat_smile:

sarahzrf (Apr 15 2020 at 17:18):

will think more later

sarahzrf (Apr 15 2020 at 17:30):

question for after the talk: if the morphisms really are games and not strategies, then how does that example work w/ players as morphisms? in what sense is a player's behavior a game rather than a strategy?

Bruno Gavranović (Apr 15 2020 at 17:33):

sarahzrf said:

optics actually generalize considerably further than even just monoidal categories :)

Could you elaborate what you mean by even just monoidal categories? I guess you mean mixed optics?

sarahzrf (Apr 15 2020 at 17:34):

yeah

sarahzrf (Apr 15 2020 at 17:35):

well, i mean, you can formulate optics in terms of a monoidal category's action even if your optics aren't mixed

sarahzrf (Apr 15 2020 at 17:35):

but mixed optics are still more general so they were what i was thinking of

Bryan Bischof (Apr 15 2020 at 17:36):

I'd be curious to hear further explanation of the restriction on care of counterfactuals in machine learning; i think some combination of the words gives me the impression that I misunderstand this claim.

Bruno Gavranović (Apr 15 2020 at 17:36):

Right, got it. Was just curious if there's some other generalization I'm not aware of :)

Dan Frumin (Apr 15 2020 at 17:37):

Is there a small concrete example of a typical game from game theory represented as a (closed) open game?

sarahzrf (Apr 15 2020 at 17:42):

coend optics are equivalent to profunctor optics—i bet the latter is more popular for a reason :)

Bruno Gavranović (Apr 15 2020 at 17:44):

sarahzrf said:

coend optics are equivalent to profunctor optics—i bet the latter is more popular for a reason :)

The reason being "profunctor optics" just sounds incredibly cool

Gershom (Apr 15 2020 at 17:55):

On software to compile/execute string diagrams, there is also (though not graphical) Selinger and Rios' Proto-Quipper-M which can describe morphisms in any symmetric monoidal category: https://arxiv.org/abs/1706.02630 (I don't think its in the public view, but Selinger is happy to provide the current state to researchers interested in it).

Philip Zucker (Apr 15 2020 at 18:23):

Ever taken a look at Nashpy? https://nashpy.readthedocs.io/en/stable/ I'd been kinda eyeing it for a possible backend. It does find equilibria.

Bruno Gavranović (Apr 15 2020 at 18:23):

Now that I'm think about it, the thing that @Jules Hedges mentioned about doing graphical manipulations of rotating the images to get the transpose of the jacobian, pretty sure that holds. Because if we rotate the bottom wire of optics we get an "optic" which has both covariant wires - which correspond exactly to forward mode AD where we don't take the transpose of the jacobian :)

Jules Hedges (Apr 15 2020 at 18:23):

:wave:

sarahzrf (Apr 15 2020 at 18:23):

hey!

Bruno Gavranović (Apr 15 2020 at 18:24):

More information about this transpose/Jacobian business
can be found here: https://arxiv.org/abs/1910.07065 (Example 2.3 and Example 5.3) and https://arxiv.org/abs/1804.00746

Jules Hedges (Apr 15 2020 at 18:24):

This is the point where I need to figure out how to quote-reply

Philip Zucker (Apr 15 2020 at 18:25):

Also here :nerd: http://www.philipzucker.com/reverse-mode-differentiation-is-kind-of-like-a-lens-ii/

Bruno Gavranović (Apr 15 2020 at 18:26):

Jules Hedges said:

This is the point where I need to figure out how to quote-reply

Top-right of my message, hover near the timestamp

sarahzrf (Apr 15 2020 at 18:26):

in the menu from the dropdown arrow to be precise

John Baez (Apr 15 2020 at 18:28):

Yup, click on the downarrow above and to the right of the message you want to reply to.

John Baez (Apr 15 2020 at 18:28):

And get this:

Jules Hedges said:

This is the point where I need to figure out how to quote-reply

John Baez (Apr 15 2020 at 18:28):

So yeah, I was being a bit silly about inverses vs. transposes.

John Baez (Apr 15 2020 at 18:29):

If you have a smooth map f: X -> Y and a tangent vector v to some point x of X, you map it forward via $df : T_x X \to T_{f(x)} Y$.

John Baez (Apr 15 2020 at 18:30):

Let's say $f(x) = y$, so we get $df : T_x X \to T_y Y$.

John Baez (Apr 15 2020 at 18:30):

But then the adjoint of this map, which is a transpose when you write it out using matrices, gives

$(df)^* : (T_y Y)^* \to (T_x X)^*$

Jules Hedges (Apr 15 2020 at 18:31):

sarahzrf said:

question for after the talk: if the morphisms really are games and not strategies, then how does that example work w/ players as morphisms? in what sense is a player's behavior a game rather than a strategy?

So this is one of the things I had to skip for time. Here's the simplest example. A player who chooses an $X$ given no observation is modelled as a particular open game $\mathcal P : (1, 1) \to (X, \mathbb R)$. The index set of strategy profiles is defined to be $\Sigma_\mathcal P = \mathcal D (X)$ where $\mathcal D$ is probability distributions, ie. the set of mixed strategies the player can use to make their choice. It turns out that $\hom_{Optic} ((1, 1), (X, \mathbb R)) \cong X$, so we take the indexing map $\Sigma_\mathcal P \to \hom_{Optic} ((1, 1), (X, \mathbb R))$ to be just that. The other thing we need to supply is the best response function. It turns out that in this simple case the set of contexts (the 3 toothed combs) simplifies to $X \to \mathbb R$, the coend vanishes. So the remaining piece of information we need to define $\mathcal P$ is the best response function $\Sigma \times (X \to \mathbb R) \to 2^\Sigma$. We define it by $(\sigma, k) \mapsto \arg\max \mathbb E k = \{ x \in X \mid \mathbb E [k (x)] \geq \mathbb E [k (x')] \forall x' \}$

Bruno Gavranović (Apr 15 2020 at 18:32):

John Baez said:

But then the adjoint of this map, which is a transpose when you write it out using matrices, gives

$(df)^* : (T_y Y)^* \to (T_x X)^*$

I always wondered why is this called the "adjoint" and is there any sense in which adjoint functors play a role :)

John Baez (Apr 15 2020 at 18:33):

I could say a lot about that. Basically it's a decategorified version of an adjoint functor.

John Baez (Apr 15 2020 at 18:34):

Adjoint functors:

hom(LX, Y) $\cong$ hom(X,RY)

Adjoint linear maps:

$F^*(f)(x) = f(F(x))$

John Baez (Apr 15 2020 at 18:35):

Same pattern, but now both sides are numbers instead of sets!

John Baez (Apr 15 2020 at 18:35):

I'll stop here, since Jules just said something that's more relevant to open games.

Jules Hedges (Apr 15 2020 at 18:36):

Dan Frumin said:

Is there a small concrete example of a typical game from game theory represented as a (closed) open game?

On the string diagrams side, there is the example of a 2 player imperfect information game on p11 of the slides (http://math.ucr.edu/home/baez/mathematical/ACTUCR/Hedges_Open_Games.pdf). On the semantics side, it turns out that an open game $(1, 1) \to (1, 1)$ is defined by 2 things: (1) a set $\Sigma$, and (2) an endo-relation on $\Sigma$. All of the other stuff vanishes. This is precisely the best response relation of your game. So say for example you wanted to model the prisoner's dilemma, you would end up with $\Sigma = \{ C, D \} \times \{ C, D \}$, and the endo-relation on $\Sigma$ that relates everything to $(D, D)$ (which is the dominant strategy in prisoner's dilemma)

Valeria de Paiva (Apr 15 2020 at 18:36):

John Baez said:

So yeah, I was being a bit silly about inverses vs. transposes.

well, from my perspective from Logic, not silly at all. it's the big difference between Chu and Dialectica constructions, in Dialectica we do "true inverses" i.e we transpose and negate the proposition, while Chu simply transposes.

Jules Hedges (Apr 15 2020 at 18:38):

Now it turns out that closed open games really throw away too much information for some practical purposes, although you can get a long way by winging it if you don't mind a bit of weirdness. For example if you do things naively, the prisoner's dilemma as an open game turns out to be equal to a 1-player game with 4 strategies and 1 dominant strategy

Jules Hedges (Apr 15 2020 at 18:39):

But that's a technical problem that can be fixed in a relatively straightforward way. I present the simplest possible version of open games that still suffers from problems like that, because it's hard enough to explain already

Jules Hedges (Apr 15 2020 at 18:41):

Gershom said:

On software to compile/execute string diagrams, there is also (though not graphical) Selinger and Rios' Proto-Quipper-M which can describe morphisms in any symmetric monoidal category: https://arxiv.org/abs/1706.02630 (I don't think its in the public view, but Selinger is happy to provide the current state to researchers interested in it).

Oh, that's an interesting idea, I never thought of trying to misuse that. I should bring it up in the #practice: software stream

Jules Hedges (Apr 15 2020 at 18:42):

Philip Zucker said:

Ever taken a look at Nashpy? https://nashpy.readthedocs.io/en/stable/ I'd been kinda eyeing it for a possible backend. It does find equilibria.

It's very, very restricted at the moment. The standard tool for computing equilibria is Gambit, which I think is for Matlab. Even that can only do mixed Nash equilibrium. To my knowledge there is no tool in existence for computing Bayesian Nash equilibria of extensive form games, which is my usual favourite setting to think about game theory

Philip Zucker (Apr 15 2020 at 18:44):

Huh. Never heard of that. Interesting.

Jules Hedges (Apr 15 2020 at 18:44):

Was there a conclusion to the Prakash vs Bruno saga?

Jules Hedges (Apr 15 2020 at 18:45):

My usual strategy for anything to do with machine learning is to ask Bruno, so I'm a bit alarmed at the possibility that he got something wrong :sweat_smile:

Bruno Gavranović (Apr 15 2020 at 18:45):

Jules Hedges said:

Was there a conclusion to the Prakash vs Bruno saga?

To my understanding, we were in agreement about it not being the inverse

Jules Hedges (Apr 15 2020 at 18:45):

Ah, ok

Philip Zucker (Apr 15 2020 at 18:47):

A side comment: An intriguing but possibly meaningless connection to your comb diagrams is that they are graphically reminiscent of a class of Feynman diagrams called rainbow diagrams (for which I am having difficulty finding a good reference).

Philip Zucker (Apr 15 2020 at 18:47):

As I recall they were an important class of diagrams for scattering of electrons in random potentials.

John Baez (Apr 15 2020 at 18:48):

Hmm, I should know about rainbow diagrams... I've heard of 'em.... but I don't know 'em.

Philip Zucker (Apr 15 2020 at 18:48):

Probably important in other contexts of physics as well

Joachim Kock (Apr 15 2020 at 18:48):

You can think of the forward part of a lens map as a morphism of base spaces $B \to C$, and the backward map as a map from the pullback of a bundle over $C$ to a bundle over $B$.

If we just stay in the category of sets and let 'bundle' mean 'trivial bundle', like $F\times B \to B$ and $G \times C \to C$, then this configuration is a base map $f: B \to C$ and a bundle map from $f^*(G \times C)$ to $F\times B$. But $f^*(G \times C)=G\times B$ because the bundle is trivial, and to be a bundle map over $B$ means compatibility with the projections to $B$, so to give this vertical map is to give a map $G\times B \to F$. So this is precisely a lens map.

I learned this from David Spivak.

The picture is the same for general bundles in $\mathbf{Set}$. These are arbitrary maps $E\to B$ (instead of the trivial case $F\times B\to B$). Each such bundle represents a polynomial functor $X \mapsto \sum_{b\in B} X^{E_b}$. The same notion of backward bundle map is very useful for these general bundles: they represent precisely the natural transformations between polynomial functors.

Philip Zucker (Apr 15 2020 at 18:49):

Again, I'm having a problem finding a good reference. Maybe I have the name wrong

Philip Zucker (Apr 15 2020 at 18:49):

I learned about them in a mesoscopic physics class.

Philip Zucker (Apr 15 2020 at 18:49):

many moons ago

Jules Hedges (Apr 15 2020 at 18:49):

Yes, I learned the same thing from David too :slight_smile:

Jules Hedges (Apr 15 2020 at 18:51):

This is one of the things I would have talked about if I'd done a theory talk about lenses

Bruno Gavranović (Apr 15 2020 at 18:51):

I learned this from Jules who learned it from David, so I guess that's one more :grinning:

Joachim Kock (Apr 15 2020 at 18:52):

The 'chain rule' is then a general feature of pullbacks. It does not seem to be anything anything specific to cotangent bundles or derivatives.

Jules Hedges (Apr 15 2020 at 18:52):

I think of the category of bundle morphisms as being like a completion of the category of lenses. The category of lenses is missing a bunch of limits and colimits, but bundles is complete and cocomplete and it agrees with the existing co/limits that are already in Lens. So if I'm working with lenses and I need some co/limit that isn't there, I go to bundles instead

Jules Hedges (Apr 15 2020 at 18:53):

Joachim Kock said:

The 'chain rule' is then a general feature of pullbacks. It does not seem to be anything anything specific to cotangent bundles or derivatives.

Yes... hence my comment that it briefly looked like computer scientists had reinvented a trivial case of bundle morphisms

Bruno Gavranović (Apr 15 2020 at 18:53):

Question: how do dependent lenses and optics work together? As far as I understand, optics only allow us to talk about non-dependent generalizations of lenses...

Jules Hedges (Apr 15 2020 at 18:54):

Bruno Gavranovic said:

Question: how do dependent lenses and optics work together? As far as I understand, optics only allow us to talk about non-dependent generalizations of lenses...

You beat me to it! This is a hard sounding question I like to ask people. Bundle morphisms and optics are 2 different generalisations of lenses, what is a common generalisation of them? This would have some applications in game theory, and possibly in programming too, and I bet the category theory would be really interesting

Jules Hedges (Apr 15 2020 at 18:55):

Fun fact: the category of bundle morphisms was also completely reinvented in computer science by another name, the category of containers. There were a bunch of papers about it, I think in the 90s

Jules Hedges (Apr 15 2020 at 18:56):

In any case I don't know any reference for these bundle morphisms, David told me it's just folklore. It's probably in SGA, but I'm too lazy to read it in French

Bruno Gavranović (Apr 15 2020 at 18:57):

Jules Hedges said:

You beat me to it! This is a hard sounding question I like to ask people. Bundle morphisms and optics are 2 different generalisations of lenses, what is a common generalisation of them? This would have some applications in game theory, and possibly in programming too, and I bet the category theory would be really interesting

Here at Strathclyde dependent lenses keep popping up frequently and the main thing stopping me from using them is that I don't have as nice intuitions about them as I do about optics. Optics have this nice graphical language and they're basically sets of top/bottom maps with a shared state between them

Jules Hedges (Apr 15 2020 at 18:59):

I believe surface diagrams like the one in my slides can be used to denote bundle morphisms. There's a bunch of work to do to make sure, but I sometimes work with them anyway. I also sometimes squash it into a string diagram and hope for the best, not sure I'd do that in polite company though

Jules Hedges (Apr 15 2020 at 19:00):

Specifically, I think you want to take your 3 dimensions to be composition, monoidal product and coproduct

Jules Hedges (Apr 15 2020 at 19:02):

If you have 2 different string diagrams in Lens, you can take their coproduct in Bund and that should be the 2 string diagrams side by side in parallel sheets

Jules Hedges (Apr 15 2020 at 19:02):

Course that's for generalising string diagrams for optics, which didn't appear in my slides. I have no idea what happens to comb diagrams

Bruno Gavranović (Apr 15 2020 at 19:03):

Jules Hedges said:

If you have 2 different string diagrams in Lens, you can take their coproduct in Bund and that should be the 2 string diagrams side by side in parallel sheets

Huh, that's intriguing. I'll have to think about this for a while...

Joachim Kock (Apr 15 2020 at 19:10):

Jules Hedges said:

Fun fact: the category of bundle morphisms was also completely reinvented in computer science by another name, the category of containers. There were a bunch of papers about it, I think in the 90s

Not quite that old :-) The container stuff started in 2003. There was a precursor thing called shapely functors (Jay and Cockett) from the 1990s, but they only considered cartesian morphisms. From the viewpoint of polynomial functors, these are the natural transformations that are cartesian; from the viewpoint of bundles they are those where the backward map is invertible. The basic theory of polynomial functors and some more history can by found in [Gambino-Kock, Polynomial functors and polynomial monads]

Eduardo Ochs (Apr 15 2020 at 19:17):

Bruno Gavranovic said:

John Baez said:

But then the adjoint of this map, which is a transpose when you write it out using matrices, gives

$(df)^* : (T_y Y)^* \to (T_x X)^*$

I always wondered why is this called the "adjoint" and is there any sense in which adjoint functors play a role :)

Take a look at p.330 here: http://www.ams.org/publicoutreach/math-history/hmath1-maclane25.pdf

Bruno Gavranović (Apr 15 2020 at 19:18):

Eduardo Ochs said:

Bruno Gavranovic said:

John Baez said:

But then the adjoint of this map, which is a transpose when you write it out using matrices, gives

$(df)^* : (T_y Y)^* \to (T_x X)^*$

I always wondered why is this called the "adjoint" and is there any sense in which adjoint functors play a role :)

Take a look at p.330 here: http://www.ams.org/publicoutreach/math-history/hmath1-maclane25.pdf

Great, thanks!

sarahzrf (Apr 15 2020 at 20:15):

@Jules Hedges so the link i mentioned beforehand passes thru this https://www.youtube.com/watch?v=Y0OURiQAzek

sarahzrf (Apr 15 2020 at 20:16):

i would have to really sit down and look at what your optics are doing to have any clue whether there's an actual coincidence or if it's just using some of the same tech, but

sarahzrf (Apr 15 2020 at 20:17):

i wonder if maybe some of the relationships i want to express using optics, when you tweak the kind of "separation logic" i'm working in to be something like the above, are akin to the things your optics are expressing

sarahzrf (Apr 15 2020 at 20:52):

okay ive tried staring at it a bit and im now thinking maybe the answer is that no they are not particularly related :T

Ryan Killea (Apr 15 2020 at 22:30):

I was really hoping that I could tune in for the talk, but missed the stream due to a conflict - I'm assuming that it will end up at the ACT youtube channel? One thing I was particularly interested in was the line "Current working hypothesis: open games are a better setting to do machine learning anyway" (on the open learner slide), particularly in relation to VI.

John Baez (Apr 15 2020 at 22:36):

Yes, I will try to put up the video, as always for this series.

John Baez (Apr 16 2020 at 00:23):

Here is the video for Jules' talk:

https://youtu.be/Kwflmrd2AfM

Ryan Killea (Apr 16 2020 at 00:30):

Not sure if this is a reply to your comment specifically (@John Baez because I'm new to Zulip ), but thank you very much! I really appreciate the work that has been going into this series of talks (on a very interesting set of subjects, I might add)

John Baez (Apr 16 2020 at 00:31):

I'm glad you're enjoying these talks! Next week: @Mike Shulman!

Alexander Kurz (Apr 23 2020 at 03:48):

Oh, Jules, I missed your talk ... I have to get used to not getting reminders via email ...

Jules Hedges (Apr 23 2020 at 11:06):

Hi!! My video is here: https://www.youtube.com/watch?v=Kwflmrd2AfM

John Baez (Apr 23 2020 at 18:18):

All talks at the ACT@UCR seminar are recorded and available here, along with links to slides and/or relevant papers, a schedule of forthcoming talks, etc:

https://johncarlosbaez.wordpress.com/2020/03/24/actucr-seminar/

This page has a link to our YouTube channel as well as links to videos of individual talks.