The n-Category Café

Hi David.
This might be a somewhat silly question, but have people done much work on using the technology of type theory with machine learning? That’s generally where a lot of the uses of categories come in to CS, at least the kind of CS I seem to read about.

Also, I had never heard of information geometry before. The idea of the metric being related to the “amount of information” between two configurations is fun. I’m surprised I haven’t seen it come up more often in quantum mechanics.

On a somewhat related note:

As far as I am aware, Nils Baas (usually mentioned here in relation to his work on classifying spaces of 2-vector bundles) is seriously thinking about applying $n$-category theory – in the context of his framework of hyperstructures – to biology.

I hear that Baas’s talk at Categories in Geometry and Physics will be about this.

There is

N. Baas, C. Emmeche, On Emergence and Explanation

but I have yet to read it. The basic idea seems to be this:

We think that the present framework is quite useful for analysing the nature of emergence - in particular the dependence on observational mechanisms. In order to put this into a more mathematical framework category theory is very useful. We let the systems be represented as objects in a category and the interactions as morphisms. A complex system with interactions is then represented by a diagram. Since the morphisms are represented by arrows, this may be viewed as a process oriented representation.

I like the idea that all forms of generalisation are adjunctions. It makes some kind of sense to me - the idea being that an adjunction gives what is in some sense the ‘best’ way to represent an object in one category using an object in another category. Much of machine learning could loosely be thought of in this way.

I had some ideas about this about the time of my book with Cordier:
Shape Theory: Categorical Methods of Approximation,
in 1989.
There has been a little written about it by myself and others but the problem of incorporating Kernel type constructions is still a hard one as far as I can see.

It may help to look at some of the work recorded in the Dagstuhl seminars on representation of spaces:
http://drops.dagstuhl.de/portals/index.php?semnr=04351
Some of this is fairly standard TCS but the use for instance by formal concept analysis of lattice theoretic stuff is serious artificial intelligence.

Though it’s not machine learning, evolutionary computation, and particularly coevolutionary computation, has several places where category theory could contribute quite a lot. I’ve formulated most of my own ideas about coevolution in terms of preorders, many of which could conceivably and usefully be replaced by categories. Besides that, there are places where I’ve seen what amount to functors and sheaves. I’m sorry about the long comment, but I wanted to give some setup and intuition.

A typical formulation of a coevolutionary algorithm starts with an interactive domain. You can view one of these as a function $p:S\times T\rightarrow R$. When an element of $S$ (candidate solution) interacts with an eleemnt of $T$ (test), it receives a result from the preorder $R$. The order on $R$ allows results to be compared; higher values are better for the candidate solution. Payoff matrices as used in game theory can be written in this way, though there is no need for $R$ to contain numbers. $p$ might encode the outcome of a game of chess, and $p(me,you)$ might be $lose$, where $lose \lt draw \lt win$ (it might be useful to encode why I lost, and make $R$ a full-blown category). Since I brought up chess, I should say that games make up a good fraction of example applications, so I’m going to lapse into using words like “strategy” and “play” when to be more general I should be saying “solution” and “interact.”

One of the most important observations here is that in most games of interest, no single element of $S$ actually suffices as a “solution.” Rather, some mixture (distribution – think Nash equilibrium strategy), bag, or other structure built from elements of $S$ usually works better (I should say that I’m ignoring $T$ for now for simplicity’s sake…but there is a lot to say about it). In rock-paper-scissors, for instance, none of the “primitive” or “atomic” strategies rock, paper, or scissors, is a very good one to play; picking one of them at random with equal probability at each interaction is usually a better strategy. Well, that is just a probability distribution over $S=\{rock,paper,scissors\}$ with all choices equiprobable. The collection of all probability distributions over $S$ is what we’re really searching in this case.

So while most algorithms move through elements of $S$ (and $T$), what we really seek is an element of some structure built from $S$. The structures, like mixtures, are almost always free structures built from $S$. They’re often called configurations, so we might as well write $CS$ for configurations built from $S$ and recognize $C$ as a functor (it’s not completely clear to me whether $C$ should be covariant or contravariant, but in examples it seems the most natural thing to do is treat it as contravariant; there are usually restrictions or “degeneracies” which make more sense than inclusions/emebeddings/…). Calling it “free” suggests an adjoint, and indeed there’s often a forgetful functor lying around too.

The state of an algorithm at time $t$ is usually a pair of subsets $S_t\subset S$ and $T_t\subset T$ (in fact, “populations” in coevolutionary algorithms are usually multisets/bags or distributions, so think of $S_t$ and $T_t$ as supports for simplicity). As noted above, we draw potential solutions from some structure of configurations $CS$. However, what we actually have on hand when the algorithm is running isn’t all of $S$, but $S_t$. Thus, the structures actually available at time $t$ are those in $CS_t$, so that if we stopped the algorithm and asked it for the best thing it had found, it’d have to give us its best guess from $CS_t$. It’s as if we know about rock and paper but haven’t discovered scissors yet. From the local perspective afforded by the state $\{rock,paper\}$, paper would seem like the best strategy to play, even though from our global perspective (which the algorithm does not have) we know this is not the case. This local/global distinction smells like a sheaf to me, though I’ve never been able to formulate this as a sheaf in a useful way. But the important question is: are there generic statements which can be made about whether a particular algorithm, when progressing from $S_t$ to $S_{t+1}$ to … is getting “closer to” or creating a better and better approximation to the best solution in $CS$ (where its guess are are drawn from $CS_t$, $CS_{t+1}$, …)?

One more word, about $T$. Currying $p$ leads to a function $\lambda_S:T\rightarrow R^S$ via which we recognize that elements of $T$ name functions $S\rightarrow R$ (which is interesting to think about: you, as a chess player, act as a function from the set of other chess players to the preorder $\{lose\lt draw\lt win\}$!). Each $t\in T$ induces a preorder on $S$ therefore by pullback of the order on $R$ through $t$-as-function. Any subset $T^'\subset T$ can be thought of as inducing an order on $S$ (in a variety of ways…) by “integrating” these individual orders from the $t\in T^'$. Is there some natural way to turn that information into an order (or some other sense of direction) on $CS_t$? Can that then be used to identify potential solutions from $CS_t$ which have some hope of being good approximations for the best we could find in $CS$?

Well well,

I have thought the idea in 2008 August and read several books how n-category theory and it’s relatives can be transfered into a machine learning model or/and help a machine learning approach in explaining several cognitive processes which machine can not do. N-Cat is very applicable to layered based generative models. However, the problem is efficiency.

Regarding the comments on using type theory in machine learning, the following may be of interest: http://www.cs.cmu.edu/~fp/papers/popl05.pdf. The authors mention the Giry/Lawvere monad.

An explicit attempt to apply category theory to machine learning is
http://www.adjoint-functors.net/Wojtowicz_Fusion2009pp.pdf.

Mmmmmm…
Stumbling upon this thread due to the recent comment by Ralph Wojtowicz elicits the weird feeling that category theory is “a solution in search of problems”.

there are so many different “educated guesses” about what the next good stepping stone in artificial reasoning/machine learning

My uneducated guess is that the current main stumbling block is in going from the informal to the formal, not only fuzziness but vagueness must be resolved.
Perhaps there is something to find in machine learning about feature extraction, synthesizing the hypothesis space from scratch (well… the raw data actually).
There is no lack of math crunching ready to fire once “the problem is well defined”, it’s the murky part which is still missing not the “high maths”.

A few years on, the field has come quite a way!

Here’s a current preprint:

• Bruno Gavranović, Paul Lessard, Andrew Dudzik, Tamara von Glehn, João G. M. Araújo, Petar Veličković, Categorical Deep Learning: An Algebraic Theory of Architectures, (arXiv:2402.15332)