Coarse graining via adjoint functors

This is a writeup of some things that I learned and talked about at the first day of the FRA3 workshop, in a group with Adele Dewey Lopez, Sophie Libkind, and Joe Moeller.

We formed this group in order to talk about coarse graining, which I view as the process of “lossily compressing” a model of the world to use smaller descriptions.
I’ve been interested in coarse graining for a long time, because it seems to me that understanding the process of coarse graining is essential to understanding macro-scale models in the world. This is becaue macro-scale models are definitionally coarse grained micro-scale models. For instance, I might describe a beaker using the concentrations of each of the chemicals in the beaker. This is coarse grained from the quantum microscale description of the beaker as some massive wave function. When you coarse grain in this instance, your system moves from being reversible to being irreversible.

I talked a little bit about some of the things that can happen when you coarse grain a system in Moving, Fast and Slow. Specifically, when you approximate a “fast” time scale as happening instantaneously, you get constrained, hybrid dynamical systems.

In the morning discussion, we talked about an example of how coarse graining a deterministic system can produce a non-deterministic system.

We did this via an idea that Adele has been thinking about for a while, which is formalizing the process of an agent observing its world via adjoint functors.

For concreteness, let’s start with an example.

Suppose that the state of the world is described by W Boolean variables, and the state of an agent’s mind is described by P Boolean variables. Assume that we have some function f \colon 2^W \to 2^P which maps a state of the world to a state of the agent’s mind.

For example, we could have W = 4, P = 1, with the interpretation that the world consists of 4 coin flips, and the agent consists of an light that is on or off. The map f sends world states where all of the coins land on the same side (i.e. all heads or all tails) to the light being on, and everything else to the light being off. I.e., the light turns on if and only if we get all heads or all tails.

Then there is a pair of adjoint functors between the powerset \mathcal{P}(2^W) of 2^W and the powerset \mathcal{P}(2^P) of 2^P.

The intuition is that a subset U \subset 2^W represents a “constraint” on the world; the constraint that the state lies within U, and similarly for a subset V \subset 2^P. Then S=\exists f (“sensation”) sends a subset U to S(U) = \{f(x) \mid x \in U\}, which is the set of all states of the agent’s mind which could be induced by an element of U. R=f^* (“realization”) sends a subset V to R(V) = \{ x \in 2^W \mid f(x) \in V\}, the set of all world states which could induce an agent state in V.

The adjointness comes from the fact that for all V \subset 2^P, SR(V) \subset V, and for all U \subset 2^W, U \subset RS(U). SR(V) is the subset of V consisting of the agent states which could actually be induced by anything in the world, and RS(U) is the superset of U consisting of all states that could be “confused with” a state of U by the agent.

Now, we want to talk about dynamical systems. The simplest kind of dynamical system is a discrete, deterministic dynamical system. A discrete, deterministic dynamical system on a state space X is just an “update function” u \colon X \to X. Given a starting state x \in X, the system evolves as x, u(x), u(u(x)), u(u(u(x))) and so on.

Suppose that we have a very simple update function on 2^W for the system of coin flips and a light before. This update just flips the first coin, so u(1xxx) = u(0xxx) and u(1xxx) = u(0xxx). Can we make a dynamical system on 2^P which somehow “tracks” this update function? Well, we know that if the light is currently on, and we flip the first coin, then the light will no longer be on in the next step, because not all the coins will be the same any more. However, if the light is currently off, then it could either be on or off in the next step! So we get an update function u' defined by

u'(\mathtt{on}) = \{\mathtt{off}\}
u'(\mathtt{off}) = \{\mathtt{on}, \mathtt{off}\}

So what was a deterministic dynamical system in the world states becomes a nondeterministic dynamical system in the agent states!

We can abstract this. Suppose that we have an update function u \colon 2^W \to 2^W. Then we can create an nondeterministic update function u' \colon 2^P \to \mathcal{P}(2^P) via u'(y) = (\exists f)(\exists u)(f^*(\{y\})).

However, this fails to be functorial!! Specifally, (u \circ u)' \neq u' \circ u' for our example, because u \circ u is the identity, but u' \circ u' sends both \mathtt{on} and \mathtt{off} to \{\mathtt{on}, \mathtt{off}\}. This says that the single step dynamics of the light bulb aren’t sufficient to predict the future behavior of the light bulb! However, note that the double step dynamics of the lightbulb are, because the two options are either flipping between on and off forever or staying off forever. So we can recover determinism by remembering the history, which we did not need to do in the actual world state. In other words, coarse-graining broke the “Markovness” of the system.

Adele’s setup of adjoint functors for modeling agent and world aren’t just limited to this simplistic description of the world and the agent in terms of Boolean variables, and I’m hoping that applying the same analysis to richer categories will formalize other types of coarse-graining.


Interesting thoughts!

My two cents: checking functoriality on composition of updates is a bit unfair, since you’re really treating those as objects for (-)', so composition is more of a monoidal structure for them. Indeed you have a colax structure, since (u \circ u)' \subseteq u' \circ u'.

Have fun at FRA3!

Ooh, neat!! So more generally, this might be some sort of lax bifunctor.

I think lax monoidal functor is enough?

In general, \rm End, sending a category to its monoidal category of endofunctors, is functorial over \bf Adj, the category whose morphisms are adjunctions. More precisely its a functor \rm End : \bf Adj \to MonCat_{\rm colax}. I think this is more or less what’s happening here.

Well, I mean when you move from just composing endomorphisms to possibly composing more general morphisms, you might expect to see lax bifunctor structure; in this particular example it is just lax monoidal!

1 Like

Oh I see, that’s reasonable I guess!