Abstractions as morphisms between (co)algebras

2shminux

New Comment

Here is a couple of my somewhat related comments from awhile back: https://www.lesswrong.com/posts/NFMPftEhagCcHcmQJ/on-the-role-of-abstraction-in-mathematics-and-the-natural?commentId=GRp8PKJd64Tm5DhtA

https://www.lesswrong.com/posts/wuJpYLcMEBz4kcgAn/what-is-abstraction-1?commentId=qxnTe3TAYs2ZqzAQL

I wish I had the background to formalize them the way you have in your post.

In general, I get the importance of keeping in mind the relevant commutative diagram (often more than one) for whatever mapping you are working on, but it is not clear to me that you can get anything actionable out of them. Still, I do think that even if all your examples are in Set, CT is a good framework for thinking about them, without going down the abstraction levels.

In a previous post, I suggested we should think of abstractions/ontologies as maps that make a certain commutative diagram commute:

The downward arrows are the abstraction, which throws away some information about the world state while keeping other parts. The horizontal arrow at the top is time evolution. The diagram says that there should be a way to "mirror" the time evolution inside the high-level model (that's the dashed arrow at the bottom). Commutativity of this diagram means that we can either do time evolution in the actual world and then abstract, or first abstract and then do time evolution in the model. If this doesn't make sense, the original post has more details and examples.

It turns out that this idea is very, very far from new.

^{[1]}I'll hopefully write a post on some related literature soon, but here I want to discuss one connection in particular: category theory, and more specifically (co)algebras of endofunctors. Using coalgebras for abstractions is an idea from bisimulations in computer science. See nlab if you just want a quick version. This post essentially just adds lots of examples and some reframing—the computer science discussions I've seen tend to be heavily focused on the special case of abstractions of transition systems.## Motivation

There are two main things the (co)algebra framework will give us:

I'll briefly elaborate on why the description in my earlier post was a bit vague. I had another example of the commutative diagram above with a somewhat different flavor:

The abstraction M maps from real numbers to a representation using 11 decimal digits (the details don't matter here). The horizontal arrow isn't time evolution of a physical system in this example, instead it's addition of real numbers. The commutative diagram essentially says we should also be able to add within our decimal approximation.

A key difference is that in the time evolution example, the horizontal arrow was an

endomorphism, i.e. it mapped from the set of possible states to itself, with a type signature like X→X. Addition doesnothave this type signature, it's a map R×R→R. This means we can't use the same function for both downward arrows. Intuitively, it's pretty clear that it makes sense to use M×M on the left side, i.e. apply the abstraction to each input independently. But what's the general principle that tells us how the two downward arrows should be related? And what kinds of horizontal arrows can we use besides time evolution and addition? That's what this post gives one potential answer to.## (Co)algebras

I'll assume you know what categories and functors are, and just focus on slightly less well-known concepts. If you don't know category theory, the next section with examples could still be interesting to get a sense of what kinds of things can be described in this abstractions framework.

First, an

endofunctoris simply a functor F:C→C from a category C to itself. All of my examples are going to be for C=Set since that already gives us plenty. Some examples of endofunctors we'll use:An

algebraof an endofunctor F is a morphism α:F(X)→X for some specific object X (i.e. a set in our examples). Acoalgebrais the same thing in the other direction, α:X→F(X). Some examples:setof other elements. One interpretation of this is a binary relation: for each x∈X, we specify all the x′∈X with x∼x′.As you can see, both the time evolution example and the binary operation example have a horizontal arrow that can be understood as a (co)algebra. In general, I think

anyalgebra or coalgebra ofanyendofunctor can be used as a horizontal arrow. The choice of functor and (co)algebra is going to describe which "task" we care about: prediction of next time steps, addition of numbers, etc.Given a horizontal arrow, i.e. a (co)algebra, we can think of abstractions as

morphismsfrom this (co)algebra to another one. A morphism from an algebra α:F(X)→X to β:F(Y)→Y is defined as a map f:X→Y such that this diagram commutes:In our context, the morphism f is the abstraction, with X the low-level/detailed system and Y the high-level model. β is the representation of the

task/operationα within the high-level model (the dashed arrow in the diagrams above).This is a generalization of the addition diagram above: there, F(X)=X×X and F(f)=f×f. Note how this answers the question of what the relation between downward arrows should be: we choose the abstraction f and then get the other arrow by applying the functor F, which is part of the specification of the horizontal arrow.

Coalgebras work analogously, except we choose the downward arrow on the left side and then translate it to the right using the functor:

This shows how (co)algebras are

one possibleformalization of these commutative diagrams. I don't see any strong a priori justification of why they are the correct formalism. The main reason this approach seems interesting to me is that lots of examples work out: abstractions I had thought about before seeing this formalism fit in nicely, and if I plug in endofunctors I hadn't thought about before, I often get good examples of abstractions out. This is what we'll look at next.## Examples

I'll now quickly go through some examples of different endofunctors and how to interpret them in the context of abstractions. These are going to be pretty informal but hopefully still clear (otherwise let me know and I'll be happy to give a more detailed version in the comments).

transition system: for any state x, the image α(x) under the coalgebra tells us thepossible next states. If we interpret morphisms from this coalgebra to another one as abstractions, then the commutative diagram tells us that our abstraction should contain all the necessary information to "run a transition system forward" within the abstraction: given the current abstracted state, we need to be able to compute the possible next abstracted states.probability distributionover next abstracted states.labeledtransition systems. We can use a similar trick for the stochastification functor to get a probabilistic version: map each set X to the set of conditional distributions X|A on the set. This gives us a simple notion of what "good abstractions" are for an agent that can take actions in a stochastic environment. (This is certainly not a complete definition of "goodness" though, it doesn't take goals into account.)quotientsof that group.upwardsbecause the functor is contravariant. What the diagram says is that the abstraction A′ of A needs to contain all the necessary information such that the correct abstracted output A′ can be selected forany"loss function" A→B. This is a reasonable notion for good abstractions of ageneral-purpose optimizer. As one example, consider gradient descent: it's most naturally defined on real numbers, but implemented in practice using floating point numbers. It's crucial that gradient descent is able to (approximately) select the floating point approximation of the direction of steepest descent, based on the floating point approximations of the (arbitrary) loss function. This is what makes floating-point-gradient-descent a good abstraction of actual gradient descent.## Some potential problems with this formalism

inducedby (co)algebra morphisms.I don't view any of these as decisive issues. Possible objections that I think could be a bigger deal:

everycommutative diagram of the "right-down = down-right" kind is best thought of as an abstraction!)^{^}Thanks to Generallyer for pointing out related work in causality; there are many other examples as well.