Making deep learning perform real algorithms with Category Theory (Andrew Dudzik, Petar Velichkovich, Taco Cohen, Bruno Gavranović, Paul Lessard)
Machine Learning Street Talk (MLST)Episode Description
Summary
This episode explores how large language models (LLMs) struggle with basic algorithmic reasoning like addition and physics, despite their vast knowledge. The discussion introduces Category Theory as a potential unifying framework for deep learning, moving beyond geometric deep learning's reliance on invertible symmetries. The hosts and guests argue that Category Theory could provide a principled foundation for designing neural network architectures, enabling intrinsic algorithmic capabilities and a better understanding of computational structure.
Chapters
Topics
People
Key Concepts (24)
References (3)
Transcript (36 segments)
Language models cannot do addition. Not really. I keep seeing claims that they can and every time I see this claim I go again to ChatGPT and so on and check and they can't.
And, what they can do is learn patterns which work a lot of the time but you can always trip them up by doing something like okay so if you ask ChatGPT what is a bunch of eights plus a bunch of ones with a two at the end? It will get the correct answer because it will recognize the trick. It'll say, ah, that's just one and a bunch of zeros.
It'll know that you're trying to trick it. But if now you change one of the eights to a seven, now it has to actually know what it's doing. It has to actually sort of walk up, hit the seven, and stop sort of propagating zeros and it simply fails.
It, it either chokes and makes up some nonsense or it says it's one with a bunch of zeros anyway.
that humans learn. And so, like, really teasing apart on a very basic level, like Newton's laws of motion, has it encapsulated it, whether that's VEO or Genie? Have these models encapsulated the physics of that a 100% accurately?
And right now, they're not.
when you just casually look at them. They're not accurate enough yet to rely on, for say, robotics. Just because we can achieve some level of moving the needle by hooking up a really potent tool to a language model doesn't mean that we shouldn't think about what would the next generation of these models look like and how can we make them intrinsically better.
Because even if you have the best tool in the world, that is not going to save you if you cannot predict the right inputs for that tool. Even some of the current frontier models, they will, as you probably know, perform hundreds of billions of multiplications just to produce a single token of output, yet they cannot reliably multiply even relatively small numbers together without failing. Right?
what we are training these systems to do and how we're building them and what we might want to use them for downstream, especially if we're doing reasoning or if we're doing science. But it seems like, let's say, an LLM, if you teach it properly, you can just teach it to do, let's say, addition up to some failure of its memory. Just like with humans, we might forget a digit or we forget to carry over or so, you know, we do the algorithm wrong sometimes with some probability.
Up to that, it can learn this procedure of adding a long digit numbers. You know, is it neural? Is it symbolic?
It's doing something, some algorithm, something symbolic perhaps, but it's doing that with its neural machinery. And the neural machinery also allows it to, well, of all, absorb tons and tons of world knowledge and deal with the vagueness of concepts, right? The fact that things don't exactly want to fit your good old fashioned AI symbolic theory most of the time.
We've all played with MCP servers. We know that we can hook tools up to these things. Why not just call a calculator?
What Andrew argues that tool use isn't enough. Right? We still need to be thinking about the actual architecture underneath.
It still matters.
Internalizing things, I think, has a chance to be a lot more stable. The relationship between neural nets and tools is somewhat complicated. I think you can do a lot with it, you can do a lot of interesting search, but there are a few disadvantages.
One is you may have to call the model a bunch of times because it may get an answer, but it may not be the answer it was expecting, so it might have to rethink things and go back. Like, imagine a situation where you had some complex reasoning problem where along the way you had to do a series of little additions. You just had to sort of okay so then this and then this and then oh how many of these are there okay and then how many of these and so on.
It could be quite complicated to kind of keep calling out to a tool and then going back and then calling out to a tool and then going back. And you know it seems like there are big efficiency gains if you're able to equip the model itself to just do certain kinds of basic computation or reasoning internally.
what I've done together with the team. Already in that very first episode that we did together with geometric deep learning, there was a hint of discussion about how geometric deep learning might not necessarily be enough. It will require us potentially to broaden our lens on what we mean by geometric deep learning.
And this is something we're already very actively thinking about. I think one of our co authors, Taco Cohen, actually thought much more deeply about this. Like, I hinted at the fact that groups, are the bread and butter of geometric deep learning, might not be enough for fitting the concept of aligning the computation, which is my personal motivation.
Right? So for those who are not familiar, geometric deep learning fundamentally builds itself on the concept of constructing neural networks in a way that is what we call equivariant to symmetry transformations. So what this means in a nutshell is if I transform my input in some way, I should get predictable outputs with my neural network if that transformation is something that I find to be irrelevant.
One standard example is translations of images. So if I have a picture of a cat and I decide to shift it by a certain number of pixels, it is still a picture of a cat. That hasn't changed.
I've just changed the way I'm looking at that cat. So I would like to build my model to be what we call translation equivariant, such that when I do apply such a shift, I will still get the same output that this is indeed a cat. In a similar manner, graph machine learning, which is an area that I'm personally really passionate about, deals with extracting useful representations of graph structured data like molecules.
But graphs have this inherent property that there's many different ways you can show them to the model. And typically, you have to present them using some kind of, say, adjacency matrix of nodes by nodes. But what happens if I decide to permute the order in which I show you those nodes?
So I permute the matrixes rows and columns accordingly. This is still the same graph. I would still want to get exactly the same outputs on that graph.
Right? So I can build into my models this notion of permutation equivariance, which guarantees that even if I permute my nodes, I'm still going to get predictable outputs and basically identical outputs up to permutation for those permuted graphs. And this is a really important property because it reduces almost exponentially, basically, the amount of data you need to fit a system like that to a satisfactory amount of behavior.
And it should come as no surprise that transformers, at their heart, are permutation equivariant models. Once you've put token embeddings, position embeddings into tokens, you can permute them all you want. You'll get exactly the same response.
If you wanted to learn that kind of symmetry with a simple MLP of tokens, that would have taken you exponentially more data than the trillions that we currently use to train these models, so likely a data you wouldn't be able to find. We looked at geometric deep learning from a a group symmetry point of view, which is a very nice way to describe spatial regularities and spatial symmetries, but it's not necessarily the best way to talk about say invariance of generic computation, which you would find in algorithms, right? It's like I have input that satisfies certain preconditions.
I want to say something about once I push it through this function, it should satisfy certain post conditions. This is not the kind of thing we can very easily express using the language of group theory.
it is something that perhaps we could express more nicely using the language of category theory. I do think that some very high level priors are probably a good idea and perhaps even necessary. In my PhD, I worked a lot on building knowledge about symmetries into neural networks.
And I think for many problems, you know, knowledge about symmetries is something that, first of all, gives you a lot of bang for the buck. We know from physics already and now from empirical results in machine learning that building these things into neural networks or putting a constraint on your physical theory based on symmetries gives you a lot of information, or it really restricts the space of hypotheses. And at the same time, it doesn't bias your model if indeed your problem has this symmetry.
So I think that's the kind of thing we should be looking for. This kind of very high level abstract prior, not trying to encode, you know, coming back to the example I gave just now, the fact that light switches make lights go on, that we can figure out from data, from reading text on the internet at scale, from trial and error learning in an interactive environment. Perhaps the fact that there's space like three d space and that your two d images are a projection of that, maybe that that is a useful prior.
Category theory is very much in the eye of the beholder.
I think in the first instance for me, theory categories are a very mundane thing from pure mathematics where I come from and category theory means you know when you study categories for their own sake but everybody uses categories. The question is what exactly are they? And I really come from algebra and a lot of my motivation comes from studying algebra.
And one way you can think about categories is algebra with colors. So, you know, we can imagine sort of typical algebra. So for example, let's say we're multiplying square matrices.
I can sort of think of each square matrix as a little magnet and I just sort of hook them up together and they just stick and you kind of get a bigger and bigger magnet and everything makes sense. But now suppose I had special magnets that had colors on each side and I could only connect them if the colors were the same. That sounds a bit weird but it's exactly what happens with non square matrices.
When we multiply two matrices we have to follow a rule that they are not allowed to be multiplied unless the numbers match up. If I have an m by n matrix and I want to multiply on the left with an l by m matrix I can do that because the m's are the same but otherwise I can't. There's a kind of color violation.
So the point is a situation where we want to be able to compose things to hook them up together, but we can't always do it. That's basically what categories are designed to cover and I think the matrix example illustrates they're not so mysterious.
into account. I think the the the this geometric deep learning blueprint that we described there can be generalized. Yeah.
Category theory made a lot of things click for me. Or I'm hoping, let's say, that it will allow us to generalize this methodology of geometric deep learning and equivariance to not just reason about symmetries, but far more general kinds of structures and structure preserving maps.
Could it help there in the sense that, you know, we imbue the models with these geometrical priors and we think these high resolution priors describe the physical world that we're in. Could this category thinking allow us to somehow bring all of those together in some new way? Well, you can certainly see how they're all instances of the same thing.
they start coming back everywhere. And what's very nice about the category theoretic way of thinking is that it's extremely systematic and it tends to guide you in the right direction because while the examples I've given you already show that, right? This notion of equivariance, that's something that someone thinking about groups and group representation and so on will come up with and find to be a very useful concept for mathematical reasoning, but it falls out automatically if you already know category theory and you just define the categories of relevance here, your group as a category, for example, then you just follow the definitions.
You say, okay, so what is a functor from my category to the category of sets, for example? Okay, it's mapping like this. That gives you the definition of a group representation.
And then you look at what is a natural transformation between such functors. You've write out the definition, find, okay, it's an equivariant map in this case. And so it tends to produce meaningful definitions that domain experts like in a mathematical domain will have independently come up with very often.
And so it's for lazy people who don't wanna, or uncreative people, you know, you don't have to be clever. You just have to follow the rules and be very systematic and outcome these very natural definitions and a kind of mathematics that just works very nicely. Everything fits together just like with Lego pieces or something, They always fit exactly.
mathematical structures that have nice properties. There's a historical analogy worth keeping in mind. Before the periodic table, before we understood protons and electrons, practitioners of alchemy made real advances but without a principled foundation.
Deep learning today may be in a similar position: we have powerful empirical results, but we lack the fundamental theory that would let us derive new architectures rather than just stumbling upon them. Categorical deep learning is an attempt to find that periodic table for neural networks.
Deep learning, despite its remarkable success, is a field permeated by ad hoc design choices. Neural network architectures have all these knobs and tweaks that we can't formally justify just yet. There is no unifying framework for deep learning.
There is no unifying framework that would explain the probabilistic perspective, the neuroscience perspective, and merely just the gradient based iterative updating perspective. In fact, in the future, we might look at deep learning very differently. And our claim is that category theory will become the unifying deep learning framework.
But you seem to be making the argument that the interpolative function space of neural networks can model algorithms more closely to real world problems, potentially finding more efficient and pragmatic solutions than those classically proposed by computer scientists.
because you have no easy way of saying, for example, in theoretical computer science, if you want to compose two algorithms, you're working with them in a very abstract space, which means that, you know, you can easily reason about stitching the output of one to the input of another, whereas you cannot make that easy of a claim about latent spaces of two neural networks. Right?
Geometric deep learning is powerful, but it assumes all transformations are invertible. What happens when computation destroys information?
Strictly speaking, I wasn't planning to talk about any of that stuff at the time. It was very much work in progress and just kind of trapped in my head as a collection of possible ideas, but not something I remotely knew how to execute on. Right?
But I was very passionate about algorithmic reasoning at the time as well. I still am. And I still believe that, like, building machine learning models that are capable to align to classical computation is going to be really, really important to address the shortcomings that are not so easily plugged by just gathering a better dataset.
Like fundamentally, some of these things are likely to be restricted to not be able to easily generalize outside of the distribution you've trained them on, and especially for reasoning problems that is the case. When you think about all of the big scientific advances that were done with large language models, for example, up to this date, I would argue most of the ones I'm personally familiar with are a result of a careful combination of a large language model and an algorithmic procedure in the background, which actually makes sure to give it robustness properties. So think about things like fun search, like alpha code, like alpha geometry.
All of these systems have discovered new knowledge in computer science, in competitive programming, in even geometry problems at the IMO. But in all cases, you've hooked up a language model to either a genetic algorithm, or some clustering mechanism, or a tier improver, which all have very nice correctness guarantees, which then, you know, if you can run this model for sufficiently many times to kind of correct itself using the algorithm, you can end up with really nice solutions. The problem with geometric deep learning is that, as I said, it talks about symmetries.
So permutations or circular shifts, those are generally things that have very specific and rigid behaviors. And typically, one of the things we assume about symmetries is that they are invertible. So basically, that whenever I permute nodes, I can always permute them back.
I haven't lost any information. And usually with images, when we do shifts, we actually pad the image with zeros to make sure that no image data is lost and things like that. So basically, it always assumes that it's still the same input.
We haven't lost any information. Now why is this a problem for me, who is really interested in aligning models to classical algorithmic computation? Well, as any computer scientist will know, many programs you write will delete some of the data or destroy some of the data.
So that is no longer a symmetry. You cannot invert it. Maybe one simple example is other than just the, you know, naive example of I'm gonna take a list and delete half of its elements for no reason.
Let's start with, you know, path finding. So we talk a lot about algorithms like Dijkstra or Bellman Ford inside a computer science curriculum. In short, those are algorithms that starting with a directed weighted graph predict what are the shortest paths lengths inside that graph.
Right? Now the thing is, there are many, many different graphs with different weights that are going to have exactly the same shortest paths and potentially even the same shortest path lengths. However, those graphs are different.
And once you've applied the transformations of Dijkstra's algorithm or Bellman Ford algorithm, you'll have lost the information that is contained about the graph in the final output of that algorithm, right? Because many different graphs will be compressed to exactly the same output, right? So this is not an operation I can describe using asymmetry.
And then this journey gradually, like it took me a while to realize how we can be formal about this, how can we try to put some theory on this, and even now down the line, how can we build some practical models using this? And I was fortunate enough to to start chatting with Andrew, who is my colleague at DeepMind, who has a category theory background. And he's been thinking himself about some of these problems in the past.
So it was a great match because together with him, it was a long way, but we managed to gradually relax the constraints of what a group is giving us. We first looked at removing the invertibility part, which led us to monoids, and then we derived some interesting theory and asynchrony invariance in models using monoids. And now we're also looking into removing the second constraint of groups, is the requirement that every single computation must compose with every other piece of computation.
As you might also know in computer science, you cannot always do that. You must make the output of your first function match the input type of the second one. Otherwise, they can't compose.
So this now leads us to categories, and, well, that's what led us now to categorical deep learning. Things like intentionality and planning and system two and reasoning and stuff like that, I think you're placing the assumption that there's something standard about that. Yeah, exactly.
I mean, and to some extent there is, because for a lot of these algorithms we have even proofs that they will arrive at optimal solutions if you give them enough time and put them in the right context. And I actually think it's gonna, it should be a synergy, right? Because as you said, with modern large scale deep learning systems, we actually stand the chance to map really complicated, noisy, real world scenarios into a space where those algorithms might become applicable.
Right? Now the main argument that maybe we are trying to make in some part here is that asking the model to both do that translation and robustly invoke the algorithm is likely a bit too much to ask because, among other things, you've said fixed computational budget. That's already one recipe for failure as inputs get larger because, as you know, for example, multiplication, as I mentioned, is an algorithm which is a is a problem for which we don't really have a super efficient algorithm yet.
The best known one is n log n, and that one relies on, like, complicated number theoretic constructions, let's say. So most people know just the n squared quadratic algorithm for multiplication. So the amount of resources that you need to reliably multiply two numbers will grow, and sometimes super linearly, based on the size of those two numbers.
And currently, our systems can cope with that implicitly if you add things like chain of thought, which gives the model more thinking time and so on. But fundamentally, all of those things are patches that might help for a particular class of problems, but then fail somewhere else just because of the nature of how complicated the entire space of computational problems is. Right?
So basically, I believe in a future where the neural network will deal with the understanding of the world, with the translation of what's happening in the world into some abstract space, which might just be high dimensional embeddings, by the way, that's also plausible. And then there will be some component that we have baked into the system either through priors or through very careful losses or even through combining systems with tools, which has already proved really, really useful that will actually then execute that computation in a way that we can reason about it. And I should stress, by the way, what I mean by reasoning is not 100% accuracy on every single inputs.
I find that humans can reason, and humans are not a 100% accurate on every single input you give to them. Right? As as you can see, if you ask me to multiply two numbers that are, like, 50 digits long, I will definitely make some failures if you ask me to do that.
But, you know, the point is that, like, what I would like is that system understands the amount of effort that needs to go into doing some kind of computation, and maybe at least to give me some either an estimate of how likely it is to make mistakes, or some notion even some notion of, I'm sorry, the problem you've asked me to do is too computationally large for my capabilities. I would like to just back off and not answer. Right?
Currently, systems are not trained to do that. They're trained to always try to give you an answer. Right?
Which is very different to to that. So, basically, I'm fine with making mistakes, but I would really like some awareness of when mistakes might happen and how big they will be, which when you apply algorithms, you often have that. So you can have correctness guarantees as well as, you know, convergence guarantees and things like that.
But you're probably thinking, why do we need to use such abstract mathematics in the first place?
can actually help us see what actually matters.
the notion of structuralist mathematics and then the best known example of structure structuralist mathematics category theory, I would like to begin with the distinction between analytic mathematics and synthetic mathematics. And the usual two examples that are given for this is the geometry of Descartes versus the geometry of Euclid. For Descartes, lines are solution sets to equations, whereas for Euclid, lines are precisely that, which is stretched out between two points.
What's the essential distinction here? In analytic mathematics, stuff is made of stuff. Right?
There's always some question of, okay, I have to have some common foundation from which everything is built, and all of my lemmas, theorems, etcetera, everything eventually boils down to a computation in that more basic substance. On the other hand, in synthetic mathematics, it's like, I don't need to goat I don't need to know what, like, the inside of a line is. That doesn't matter.
The point is, I only abstract what are the principles by which I can make inference on lines and their relationships to each other. Right? The point is you get rid of everything that is inaccessible to your logic.
Right? So you get rid of all of this stuff that you might call detail, but it's not even detail. It's noise.
It because it doesn't have any content for that which you can know. Right? And so therefore, it's completely irrelevant.
So synthetic mathematics gets rid of all of that and focuses just on how you can produce more knowledge. Right? And so then to explain at least what I mean by a structuralist mathematics, I want a synthetic mathematics of structure.
Right? What is structure? You know, in the context of machine learning, we've got lots of notion.
Everyone says structure. Right? The best known and best studied example of that structure is group actions.
Right? All of geometric deep learning is about group actions. But that's only one that's like one pinprick in the vault.
Right? That's just like one thing. Right?
There are lots of other things, say, that come from theoretical computer science, the notion of thing things being lists or, you know, things being trees, all of these other various, like, algebraic structures. So you want, like, a single, you know, language in which all of these various kinds of structure can be described elegantly. This is exactly why we appeal to category theory.
In the simplest possible terms, what do you mean by two category?
Right, right. So if we talk about a category as a collection of things and relationships between them, these relationships are encoded as something we call morphisms. These are like generalized functions.
These are just arrows, we draw them as arrows. Before we go any further, let's ground what weight tying actually means.
Imagine an RNN processing a sentence word by word and at every time step it uses the same neural network cell the same weights to process each word. That is wait time, multiple parts of a computation to share identical parameters. In traditional machine learning we do just this, right?
We code it up, but there's no formal theory explaining when this is valid or what structure it preserves. I know it sounds abstract, it just means that we can prove when weight tying is correct and derive new architectures where weight tying is guaranteed to preserve the structure that we actually care about.
so these are a set in a category, there's a set of morphisms. But now if you take the ethos of category theory and not just have a set of things, but we try to relate that set with some ways between them, if you look at this set of morphisms between two objects now, if we add the notion or start describing the ways these morphisms could be related, the properties they need to satisfy, which is also some kind of composition, then we get, start getting at the notion of a two category, which is objects, morphisms, but two morphisms as ways of relating them.
Category theory talks about these relationships between objects, know, as morphisms, but what about relationships between the morphisms?
Right, right. So these are these that we call two morphisms or two cells, and these are the things we use to model some aspects of neural networks that we deem are important. We shouldn't just think of them as categories, they're not just maps, but they have this high we can think of them certainly like this, but that does not encode a lot of the interesting things we want to have about them.
And this is, I think the idea of higher categories where you start modeling something with purely categories and you realize, well, all along I have been forgetting about this other important thing. So you start putting more stuff into your theory while still trying to make it consistent. And the particular way we encode these higher morphisms or what we use them for, I think the most important thing is weight sharing.
So we got a comprehensive theory of how to do weight sharing in a way that's not particularly tied to smooth spaces, know, spaces that can, it's one that works for manifolds, it's also one that works that we have now used, know, me and my collaborators in my PhD that we have used to connect to game theory where we talk about economic agents that have some strategies and if we want two agents to operate with the same strategy we do weight sharing there.
the kind of thing you're studying built in. You could presumably just go to the third order and to the fourth order. I mean, with self attention transformers, they model these two tuples, is like first order relationship.
You could have third order, fourth order, and so on.
enough, or should we go deeper than that? Well, depending on who you ask, you will get very opinionated answers, but generally, you know, when I started learning category theory, I was like, well, I'm never gonna go to two categories, that seems complicated. Now I say I'm never gonna go higher than two categories because that seems too complicated, but people do three categories, infinity categories, and you can really start building up these relationships higher and higher and get this really comprehensive theory that becomes a very different beast in some ways.
There is a school of thought that our brain works in this way. So we think using the symbols and these categories and so on, and then there's the notion of the universe is a certain way, and we understand the universe with that kind of interface. So it's almost like the driver for this is here's an interface, here's how we think, here's how the universe works, let's program computers in that way.
a big question. What happens with these things is that when we start adding more levels, more is different. And that's the thing we start seeing in higher categories.
When we add different kinds of relationships and morphism you start seeing these things that can be perhaps most aptly described as emergent effects, right, because if you have two things and you want to study their behavior as a composite, well you can either study their behavior individually and look at the joint behavior or you can compose the systems and look at the behavior of the composite. And what we often found is these are not the same. In many compositional cases these are isomorphic but often there's a map going one way but not the other.
So you have to track, you start to track since this isn't an equality anymore, you have to start tracking this higher cell, but now this itself might be a part of another system that gives rise to this plethora and levels and levels of emergent effects. So that's one of the problems with higher category theory is that it's just so hard for us with our complexity of minds to do this. So it's certainly an open question of what is the best substrate, how to encode these things and people have done a lot of work in programming language theory of encoding not just data structures and algorithms but type theories that these algorithms are hosted in, in some categorical way.
think that there is no reductionism. But even with basic weak emergence, the analytical shortcut between the theories at different scales are computationally intractable.
emergent organization as well as what's going on underneath. So this is one of the goals that you could say is one of the goals of category theory is to find some fundamental abstractions that give rise to these very simple principles. Often when you look at some systems or some phenomena, it's very complicated, but if you're lucky enough and you can set up the good foundations, it's always, oh, wait.
It was very simple all along, looked at it the wrong way. So I don't know what where this could go but we're certainly striving to make things as compositional as they could be and in many of these fields where we have plenty of experimental evidence and lack of good theories, category theory has a very good vantage point and just a lot of practical benefit of let's stop and see what's the good vantage point here. Does two morphisms allow us to think about weight tying?
Absolutely. So if we think about a parametric morphism, it's a map from A to B with a parametric B, we often want to change the parameter space. We often want to say do the weight tying, which you know in practice means we start from a smaller weight space and copy the waves in particular.
So a two morphism in the two category of parametric functions is a reparameterization. So it's a map between two parametric morphisms that is somehow coherent. There are some diagrams that have to be satisfied, but essentially they encode that one is obtained by pre composing some form of weight tying, but it doesn't have to be just copying, right?
That's the thing we're finding out. It can be arbitrary relationships between the weights. So one the things that these two cells and two morphisms allow us is to see this algebraic structure encoded as relationships between the weights.
And then that goes again into what category three is about, it's about finding relationships between objects and this, absolutely.
So here's the key connection to programming. In functional languages we define data types like lists recursively. A list is either empty or it's an element followed by another list.
Categorically, this is an algebra for an endofunctor. The structure map of the algebra packages together all of the constructors of the data type, and the homomorphism from this algebra is exactly what programmers call a fold: a function that consumes the list by recursively applying some operation. So the framework is describing the very structure of recursive computation.
When you write code you encounter syntax errors, you don't so much encounter semantics errors. So the syntax is really quite grounded in the things that you're actually typing in when you're writing something whether it's an ordinary algorithm, whether it's a network architecture, etc. The semantics is much more about like how can programs behave and you know one example of this for we have something like list types.
So lists are defined by a type constructor. Given a type T, you have another type, list of T. So what are the semantics of lists?
Well the semantics of lists are really things that are foldable, sort of foldable types. So like, numbers with addition, they're a sort of foldable type. If I have a list of numbers, I can just add them to sort of remove the list.
And now these these foldable types mathematicians have a very different name for them, monoids, which are a more general kind of group. But in any case, like that's sort of the semantics of lists. And before I say something about syntax let me say that our paper is really mostly exploring things from the semantic angle.
Why is this? It's because two different syntaxes can describe the same thing very easily. You know we could have an arithmetic theory where we have addition and we also have negation or we could instead have subtraction.
And you can describe the same things in those two different languages but the languages really are different. They give you the same semantics but the syntaxes are different. And so when doing mathematical analysis, when proving theorems, it's often really beneficial to work from a semantic point of view.
But it's worth really emphasizing that if you want to compare this work to some other work that's done on equivariance and so on, that work is often being done from a syntactic angle. So let's pause to state the central claim of categorical deep learning.
The proposal is basically that a neural network layer should be viewed as a homomorphism between two algebras for the same endofunctor. The endofunctor describes the kind of computation a network needs to respect, be it a group action, a list fold, or an automaton transition. And the algebras describe how that computation transforms the specific data.
The homomorphism is then a function that maps between these two data representations, while preserving the computational structure. When this homomorphism is a group action, you recover geometric deep learning, but the framework itself is far more general.
So what is the syntax, for example, of the action of a group? It's really you kind of say well I want to just think I have like one kind of thing and then each group element takes that thing and makes it sort of sends it back to itself. So I have sort of a single type and then each group action does something to that type.
So I might have some points in the plane and my group might be rotations and reflections that move those points around, but I'm still in the plane. But it turns out that this one sorted syntax isn't enough to even capture basic type constructors in computer science. So for example lists, you cannot deal with the syntax of lists using just a single sort.
You need a multi sorted syntax. So the way that you can do this is to say well think of we have sort of zero tuples, one tuples, two tuples, etc. And then given k tuple I might be able to make some other kind of tuple, an l tuple, by taking elements of my k tuple and making them into some lists, L lists, right?
So that's a syntax in the same way that group elements were a syntax. And it does have compositionality. If I have a way of packing things from a tuple into a bunch of lists then I can pack those lists into other tuples of lists.
But it's clear that this is first of all many sorted and then also differs from the group case because all of this is highly non invertible. There's, you can't sort of by packing things more and more and more into lists eventually undo the lists, right? You just get more lists.
But we basically construct a model for the syntax. And in the case of groups, a model in sets means a set acted on by the group. While for example, a model in vector spaces would mean a vector representation of the group.
Whereas in the case of the syntax for lists, you just get what I was calling before foldable types or monoids. Things that are able to perform these syntactic operations in the expected way. Like there's just something where the mathematical reasoning just works better if you expand your universe of objects a little bit, even if you only care about the original objects.
So this is a lesson that mathematicians have learned many times and it's sort of why a lot of people will prefer to work on the semantic side, at least in the first instance. It turns out that there's something very very basic in mathematics that we all learned in elementary school that has sort of been overlooked in the design of GNNs and that's the notion of a carry. So what exactly is a carry?
Well suppose that I am able to implement a device, a number wheel, that can do arithmetic modulo 10. So zero through nine on it. And now I want to build a kind of composite wheel that can do arithmetic modulo 100.
So what do I need to do? I need sort of this little mechanism that when it when the wheel goes from nine to zero it turns the next wheel by one. And this is very simple, it's extremely at odds with the way that GNNs have been conceived of in the past.
Because in the past, generally you send the whole state, but there's no information in the state. The information is only in the change of the state. But it's even worse than that.
Even if you sent the change in the state that's not enough information because if I went from nine to zero is it because I added one? Is it because I added 11? Is it because I subtracted nine?
It turns out that it's quite subtle to get this kind of thing to work in the presence of gradient descent. So it somehow is a very fundamental aspect of how we assemble more complicated computational operations from simpler ones. I mean one of the first things that you do if you're describing a CPU is you have to describe an adder.
This is already something that we're struggling to do in GNN terms. It turns out that this behavior is easy to get when you do discrete mathematics and very complicated to get when you do continuous mathematics. You can easily give this number wheel example everybody understands it because they know how to do addition but getting it to happen in a way such that everything is continuous turns out to be really interesting.
The simplest examples of this phenomenon don't occur until you're dealing with three-dimensional manifolds, so you would need to be thinking about things in four dimensional space. And the simplest example that we know of is the so called Hopf vibration. This is a situation where, you can decompose a three-dimensional sphere, so that's a sphere in four dimensions.
You can project it onto a two dimensional sphere so that all of the pre images are one dimensional spheres or circles. And the three-dimensional sphere is very different from the product of the one and two dimensional spheres, just the same way that Z mod 100 is very different from the product of Z mod 10 with Z mod 10.
in neural networks. So their claim is quite straightforward at the end of the day. Deep learning has two languages, constraints and implementation.
And we lack a single framework that cleanly links them together. Categorical deep learning produces the bridge, right, using a universal algebra in a two category of parametric maps. It recovers geometric deep learning as a special case while naturally expressing things like recursion, weight tying, and noninvertible computation.
Now if you want the formal story, go and read their paper. The link is in the description, especially the sections on para weight tying and recovering geometric deep learning. Cool.
Thanks for watching.
Shared via Hopper