[title=Index,columns=3] noclearpage

# GAIA: Categorical Foundations of Generative AI††thanks: This is a
preliminary draft of a forthcoming book. This draft may contain errors or
omissions, and will be periodically updated.

Sridhar Mahadevan
Adobe Research and University of Massachusetts, Amherst
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we explore the categorical foundations of generative AI.
Specifically, we investigate a Generative AI Architecture (GAIA) that lies
beyond backpropagation, the longstanding algorithmic workhorse of deep
learning. Backpropagation is at its core a compositional framework for
(un)supervised learning: it can be conceptualized as a sequence of modules,
where each module updates its parameters based on information it receives from
downstream modules, and in turn, transmits information back to upstream
modules to guide their updates. GAIA is based on a fundamentally different
hierarchical model. Modules in GAIA are organized into a simplicial complex.
Each $n$-simplicial complex acts like a manager of a business unit: it
receives updates from its superiors and transmits information back to its
$n+1$ subsimplicial complexes that are its subordinates. To ensure this
simplicial generative AI organization behaves coherently, GAIA builds on the
mathematics of the higher-order category theory of simplicial sets and
objects. Computations in GAIA, from query answering to foundation model
building, are posed in terms of lifting diagrams over simplicial objects. The
problem of machine learning in GAIA is modeled as “horn" extensions of
simplicial sets: each sub-simplicial complex tries to update its parameters in
such a way that a lifting diagram is solved. Traditional approaches used in
generative AI using backpropagation can be used to solve “inner" horn
extension problems, but addressing “outer horn" extensions requires a more
elaborate framework.

At the top level, GAIA uses the simplicial category of ordinal numbers with
objects defined as $[n],n\geqslant 0$ and arrows defined as weakly order-
preserving mappings $f:[n]\rightarrow[m]$, where $f(i)\leqslant
f(j),i\leqslant j$. This top-level structure can be viewed as a combinatorial
“factory" for constructing, manipulating, and destructing complex objects that
can be built out of modular components defined over categories. The second
layer of GAIA defines the building blocks of generative AI models as universal
coalgebras over categories that can be defined using current generative AI
approaches, including Transformers that define a category of permutation-
equivariant functions on vector spaces, structured state-space models that
define a category over linear dynamical systems, or image diffusion models
that define a probabilistic coalgebra over ordinary differential equations.
The third layer in GAIA is a category of elements over a (relational) database
that defines the data over which foundation models are built. GAIA formulates
the machine learning problem of building foundation models as extending
functors over categories, rather than interpolating functions on sets or
spaces, which yields canonical solutions called left and right Kan extensions.
GAIA uses the metric Yoneda Lemma to construct universal representers of
objects in non-symmetric generalized metric spaces. GAIA uses a categorical
integral calculus of (co)ends to define two families of generative AI systems.
GAIA models based on coends correspond to topological generative AI systems,
whereas GAIA systems based on ends correspond to probabilistic generative AI
systems.

_K_ eywords Generative AI $\cdot$ Foundation Models $\cdot$ Higher-Order
Category Theory $\cdot$ Machine Learning

###### Contents

  1. 1 Overview of the Paper
    1. 1.1 Roadmap to the Paper
  2. 2 Backpropagation as a Functor: Compositional Learning
    1. 2.1 Category of Supervised Learning
    2. 2.2 Backpropagation as a Functor
  3. 3 Backpropagation as an Endofunctor: Generative AI using Universal Coalgebras
    1. 3.1 Non-Well-Founded Sets and Universal Coalgebras
    2. 3.2 Backpropagation as a Coalgebra
    3. 3.3 Zeroth-Order Deep Learning using Stochastic Approximation
    4. 3.4 Lambek’s Theorem and Final Coalgebras: Analyzing the Convergence of Generative AI Algorithms
    5. 3.5 Metric Coinduction for Generative AI
  4. 4 Layer 1 of GAIA: Simplicial Sets for Generative AI
    1. 4.1 Simplicial Sets and Objects
    2. 4.2 Hierarchical Learning in GAIA by solving Lifting Problems
    3. 4.3 Simplicial Subsets and Horns in GAIA
    4. 4.4 Higher-Order Categories
  5. 5 Layer 2 of GAIA: Generative AI using Simplicial Categories
    1. 5.1 Categories as Building Blocks of GAIA
    2. 5.2 A Categorical Theory of Transformer Models
    3. 5.3 Constructing Simplicial Transformers from Transformer Categories
  6. 6 Layer 3 of GAIA: Universal Properties and the Category of Elements
    1. 6.1 Natural Transformations and Universal Arrows
    2. 6.2 Yoneda Lemma
    3. 6.3 Universal Arrows and Elements
    4. 6.4 The Category of Elements
    5. 6.5 Lifting Problems in Generative AI
    6. 6.6 Kan Extension
    7. 6.7 The Metric Yoneda Lemma
    8. 6.8 Adjoint Functors
  7. 7 The Coend and End of GAIA: Integral Calculus for Generative AI
    1. 7.1 Ends and Coends
    2. 7.2 Sheaves and Topoi in GAIA
    3. 7.3 Topological Embedding of Simplicial Sets
    4. 7.4 The Geometric Transformer Model
    5. 7.5 The End of GAIA: Monads and Categorical Probability
  8. 8 Homotopy and Classifying Spaces of Generative AI Models
    1. 8.1 Homotopy in Categories
    2. 8.2 The Category of Fractions: Localizing Invertible Morphisms in a Generative AI Category
    3. 8.3 Homotopy of Simplicial Generative AI Objects
    4. 8.4 The Singular Homology of a Generative AI Model
  9. 9 Summary and Future Work

##  1 Overview of the Paper

Figure 1: We propose a hierarchical Generative AI Architecture (GAIA) using
higher-order category theory.

Generative AI has become a dominant paradigm for building intelligent systems
in the last few years, ranging from large language models developed with the
widely used Transformer model Vaswani et al. (2017), or more recently with the
structured state space sequence models Gu et al. (2022); Yin et al. (2023),
and with the growing use of image diffusion algorithms Song and Ermon (2019);
Yin et al. (2023). We can broadly define the problem of generative AI as the
construction, maintenance, and deployment of foundation models Bommasani et
al. (2022), a storehouse of human knowledge that provides the basic
infrastructure for AI across some set of applications. A fundamental question,
therefore, to investigate is to study the mathematical basis for foundation
models. We propose a mathematical framework for a Generative AI Architecture
(GAIA) (see Figure 1) based on the hypothesis that category theory MacLane
(1971); Riehl (2017); Lurie (2009) provides a universal mathematical language
for foundation models. In particular, GAIA is based on simplicial learning,
which is intended to generalize compositional learning frameworks based on
well-established machine learning algorithms, such as backpropagation Bengio
(2009). Category theory has been called a “Rosetta Stone" Baez and Stay
(2010), as it provides a universal language for defining interactions among
objects in all of mathematics, physics, computer science, and mathematical
logic. Category theory has recently seen increasing use in machine learning,
including dimensionality reduction McInnes et al. (2018) and clustering
Carlsson and Memoli (2010). One unique aspect of defining machine learning as
extending functors in a category, in contrast to the well-established previous
approach of extending functions over sets or spaces Wagstaff et al. (2022), is
that there are two canonical solutions that emerge – the left and right Kan
extensions MacLane (1971) – whereas there is no corresponding canonical
solution to the problem of learning functions over sets.

Figure 2: Traditional Generative AI models, such as Transformers, are based on
a compositional sequential model. GAIA is based on a simplicial model, where
each “face" of the $n$-simplicial complex defines a generative model. Figure
3: GAIA is based on a hierarchical framework, where each $n$-simplicial
complex acts as a business unit in a company: each $n$-simplex updates its
parameters based on data it receives from its superiors, and it transmits
guidelines for its $n+1$ sub-simplicial complexes to help them with their
updates. The mathematics for this hierarchical framework is based on higher-
order category theory of simplicial sets and objects.

Current generative AI systems are built on the longstanding algorithmic
workhorse of backpropagation Bengio (2009). Backpropagation is fundamentally a
compositional sequential framework, where each module updates its parameters
based on information it gets from its downstream modules, and in turn,
transmits information back to upstream modules. Fong et al. (2019) propose a
categorical framework for backpropagation, which we review in Section 2. In
this paper, we will generalize this category-theoretic formalization of neural
networks in several ways. As Figure 2 illustrates, unlike traditional
generative AI models, such as those developed with sequence models like
Transformers or structured state space sequence models, is not sequential, but
rather simplicial. Each “face" of the $n$-simplex defines a “local"
Transformer model (or indeed, any type of machine learning model), which are
then “stitched" together into the whole structure using the mathematics of
higher-order category theory of simplicial objects and sets May (1992).

Figure 4 illustrates a crucial conceptual perspective that forms the basis for
the design of GAIA. A generative model is, first and foremost, an algebraic
structure of some kind. It may be a sequence, a directed graph, or as in our
case, a simplicial complex. This specification is akin to specifying the
“skeleton" of the generative AI model. To give the skeleton some “flesh and
blood", it is necessary to map it into a parameter space (e.g., Euclidean
space), through a suitable functor. The actual process of building a
foundation model occurs through implementing a learning method, such as
backpropagation, which Fong et al. (2019) model as a functor that maps from
the space of parameters into the category of learners. A crucial difference in
our approach is that we model backpropagation not just as a functor, but
rather as an endofunctor on the category of parameters, as it must eventually
result in a new set of parameters (see Figure 5. This important difference in
our approach makes it possible to apply the rich theory of universal
coalgebras over endofunctors Jacobs (2016); Rutten (2000) to analyze
generative AI methods. We describe in detail in Section 2 one specific
instantiation of this general perspective proposed by Fong et al. (2019). In
their case, the algebraic structure is a symmetric monoidal category that
defines the skeleton. Their parameter space is Euclidean space, and their
category of learners is defined by compositional learning using
backpropagation. In GAIA, we make a more sophisticated framework, where the
algebraic structure is a simplicial set or category, the parameter space may
be a sheaf in a topos MacLane and leke Moerdijk (1994), and the category of
learners is defined as horn extensions in a simplicial set.

Figure 4: Crucial to the GAIA framework is understanding the separation
between the algebraic structure of a generative AI model, and the parameter
space over which the model is defined, and how specific machine learning
algorithms such as backpropagation can be viewed as functors. Fong et al.
(2019) defined backpropagation as a functor as shown from the category Param
of parameters to the category Learn of machine learners. Crucially, GAIA
models backpropagation as an endofunctor from the category Param back to
itself, because every morphism in Learn must result in an update of the
parameters of the network, thus resulting in a new object in Param. Thus, in
this paper, we “close the loop", opening the rich theory of universal
coalgebras defined by endofunctors Jacobs (2016); Rutten (2000) to analyze
generative AI methods, such as backpropagation.

Figure 5: Left: In the categorical framework for deep learning proposed by
Fong et al. (2019), a learner is a morphism in the category Learn that acts
sequentially on its input $A$ to produce an output $B$, updating its
parameters $P$, and sending back a request $A$ to an upstream module that
represents “backpropagation". In GAIA, we view backpropagation as a coalgebra
Rutten (2000), defined by an endofunctor on the category of parameters, so
that each step of backpropagation is modeled as a dynamical system that maps
some parameter object into a new parameter object.

GAIA is based on a hierarchical organization, much like the business units in
a company. An $n$-simplex defines a collection of $n+1$ sub-simplicial sets
(or object), and each $n$-simplex computes some function based on a set of
parameters, which it updates based on information it receives from its
superiors. It then transmits guidelines to its $n+1$ subordinate sub-
simplicial sets on how to update their parameters. We use the simplicial
category $\Delta$ at the top layer of GAIA to define not just sequences of
morphisms, each representing a layer of a generative AI network, but
simplicial complexes of them. One way to understand the connection between
categories and simplicial sets is through the nerve functor that maps
sequences of morphisms – for example, each representing a Transformer block or
a diffusion image generation step – into a simplicial set. The $n$-simplices
are defined by sequences of composable morphisms of length $n$. It can be
shown that the nerve functor is a full and faithful functor that fully
captures the category structure as a simplicial set Lurie (2009). However, the
left adjoint of the nerve functor is a “lossy" inverse, in that it only
preserves structure for $n$-simplices, where $n\leqslant 2$. GAIA defines
generative AI over $n$-simplicial complexes that allow more complex
interactions among them than that which can be modeled by compositional
learning frameworks, such as backpropagation. Simplicial sets are defined as a
graded set $S_{n},n\geqslant 0$, where $S_{0}$ represents “objects", $S_{1}$
represent morphisms (as in Fong et al. (2019)), $S_{2}$ define triangles of
composable morphisms that have to be filled in different ways, and constitute
“inner" and “outer" horn extension problems Lurie (2009). In summary, GAIA
generalizes the category-theoretic framework for deep learning in Fong et al.
(2019) to a higher-order category of simplicial sets and objects. Figure 6
illustrates the simplicial generative AI vision underlying GAIA.

Figure 6: GAIA is based on a simplicial framework, where each generative AI
method is modeled as a morphism that maps between two objects. In the simplest
case of compositional learning, a $1$-simplex is defined as an “edge", where
its beginning and ending “vertices" represent data that flows into and out of
a generative AI model, such as a Transformer, or a structured state space
sequence model, or a diffusion process. Backpropagation can be used to solve
compositional learning problems over such sequences of “edge" building blocks.
GAIA generalizes this paradigm to define “higher-order" simplicial objects
where the interfaces between simplices can be more elaborate. Each $n$-simplex
is comprised of a family of $n-1$ subsimplicial objects, each of which can be
“glued" together to form the $n$-simplex.

Backpropagation can solve a wide range of generative AI problems defined as
supervised learning problems, where the task is to infer an unknown function
$f:A\rightarrow C$ from samples $(a,f(a))$, where $f$ is constructed as a
sequential composition of building block unknown functions that represent
intermediate targets such as $f\simeq g\circ h$, and $h:A\rightarrow B$, and
$g:B\rightarrow C$. Such problems are modeled in GAIA as “inner horn"
extensions of simplicial objects. GAIA is able to formulate “outer horn"
extension problems, such as inferring unknown functions $f:B\rightarrow C$
from samples of unknown functions $g:A\rightarrow B$ and $h:A\rightarrow C$,
or infer unknown functions $f:A\rightarrow B$ given samples of unknown
functions $g:A\rightarrow C$ and $h:B\rightarrow C$, which lie outside the
scope of sequential compositional methods like backpropagation. One example of
a setting where both inner and outer horn extensions are solvable are in Kan
complexes.

We can define the class of “horn extensions" of simplicial complexes, where
each morphism might represent a generative AI morphism (such as in the
category Learn considered by Fong et al. (2019)), which is essentially all the
ways of composing $1$-dimensional simplices to form a $2$-dimensional
simplicial object. Each simplicial subset of an $n$-simplex induces a a horn
$\Lambda^{n}_{k}$, where $0\leqslant k\leqslant n$. Intuitively, a horn
$\Lambda^{n}_{k}$ is a subset of a simplicial object that results from
removing the interior of the $n$-simplex and the face opposite the $k$th
vertex. Consider the three horns defined below. The dashed arrow
$\dashrightarrow$ indicates edges of the $2$-simplex $\Delta^{2}$ not
contained in the horns.

${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$

The inner horn $\Lambda^{2}_{1}$ is the middle diagram above, and admits an
easy solution to the “horn filling” problem of composing the simplicial
subsets. In defining a compositional category for neural networks and
supervised learning, Fong et al. (2019) only consider “inner horn" extension
problems defined as how to compose two morphism in the category Learn. In
other words, if $f:A\rightarrow B$ and $g:B\rightarrow C$ are two functions to
be learned from a database of samples, their framework works out the updates
to the composition $g\circ f:A\rightarrow C$.

The two outer horns on either end pose a more difficult challenge. For
example, filling the outer horn $\Lambda^{2}_{0}$ when the morphism between
$\\{0\\}$ and $\\{1\\}$ is $f$ and that between $\\{0\\}$ and $\\{2\\}$ is the
identity ${\bf 1}$ is tantamount to finding the left inverse of $f$ up to
homotopy. Dually, in this case, filling the outer horn $\Lambda^{2}_{2}$ is
tantamount to finding the right inverse of $f$ up to homotopy. A considerable
elaboration of the theoretical machinery in category theory is required to
describe the various solutions proposed, which led to different ways of
defining higher-order category theory Boardman and Vogt (1973); Joyal (2002);
Lurie (2009).

As examples, consider a large language model (LLM) that is trained to output
programs based on textual inputs. For example, given data corresponding to
possible textual descriptions of programs and actual code, a GitHub Copilot
can generate programs from textual inputs. An outer horn problem for this case
would be to infer an unknown function between two generated sample programs
from their textual prompts as inputs. Similarly, for a generative AI program
that produces images by diffusion from textual inputs, the outer horn problem
might correspond to learning an unknown function between two generated images.

If we assume that the simplicial complex is a Kan complex Kan (1958), all horn
extensions can be solved, which intuitively can be understood as implying that
the outer horn extension problems can be turned into inner horn extensions.
So, for example, we can solve the outer horn problem defined by the first
diagram on the left above by assuming that the morphism $f:[0]\rightarrow[1]$
has an inverse $f^{-1}:[1]\rightarrow[0]$, and hence turn the outer horn into
an inner horn problem. Similarly, for the outer horn problem on the right hand
side of the above diagram, we can assume that morphism $f:[0]\rightarrow[2]$
has an inverse $f^{-1}:[2]\rightarrow[0]$ that converts it back into an inner
horn extension problem.

Note that neural networks that are trained through backpropagation are
inherently directional: there is a well-defined notion of an input and an
output over which forward and backwards propagation occurs. In essence, what
outer horn extension problems imply is that if there exists a solution to a
problem of inferring an unknown function $f:A\rightarrow B$ from samples
$(a,f(a))\in A\times B$, does that imply a solution to the problem of
inferring an inverse function $f^{-1}:B\rightarrow A$? Lastly, it must be
noted that horn extensions can be more complex than the simple $2$-simplex
case described above. In general, in a lifting diagram, defined below, we are
asking if a solution exists to an arbitrary lifting problem in a certain
category?

We define the update process through lifting diagrams from algebraic topology
Gavrilovich (2017) as a unifying framework, from answering queries to building
foundation models. A lifting diagram defines constraints between different
paths that lead from one category to another. They have been used to formulate
queries in relational databases Spivak (2013). In our previous work, we used
lifting diagrams to define queries for causal inference Mahadevan (2023).
Lifting problems define ways of decomposing structures into simpler pieces,
and putting them back together again, and thus play a central role in GAIA
(see Figure 7.

Figure 7: Lifting diagrams were originally studied in algebraic topology
Gavrilovich (2017), and provide a concise way to define diverse computational
problems in GAIA. A map $p:E\rightarrow B$ is called a fibration if and only
if for any maps $h$ and $g$ that make this diagram “commute", there exists a
diagonal map $h^{\prime}$ that makes the whole diagram commute. Fibrations
have been used to formalize SQL queries in relational databases Spivak (2013)
and causal inference Mahadevan (2023), and are central to homotopy theory in
higher-order category theory. Many universal approximability results in deep
learning Yarotsky (2018); Wagstaff et al. (2022); Yun et al. (2020) can be
phrased in terms of lifting diagrams.

######  Definition 1.

Let ${\cal C}$ be a category. A lifting problem in ${\cal C}$ is a commutative
diagram $\sigma$ in ${\cal C}$.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{\nu}$

To understand the meaning of such a diagram for generative AI, let us consider
the setting where every edge in the above commutative diagram represents an
instance of a Transformer module that maps a object $x\in\mathbb{R}^{d\times
n}$ into another using a permutation-equivariant mapping. Yun et al. (2020)
show that Transformers compute permutation-equivariant functions and are
nonetheless universal approximators in the space of all continuous functions
on $\mathbb{R}^{d\times n}$ due to their reliance on absolute positional
encoding Vaswani et al. (2017) to overcome the limitations imposed by
permutation equivariance. Permutation-equivariant functions are defined as
$f:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{d\times n}$ such that
$f(XP)=f(X)P$ for any $X\in\mathbb{R}^{d\times n}$ where $P$ is a permutation
matrix. It is straightforward to define a category of Transformer models,
where the objects are vectors $X\in\mathbb{R}^{d\times n}$ and the arrows are
permutation-invariant mappings. Similarly, diffusion models used in image
generation Song and Ermon (2019) can be viewed as a category of stochastic
dynamical systems that can be viewed as probabilistic coalgebras Sokolova
(2011). Rutten (2000) and Jacobs (2016) show that a wide class of dynamical
systems used in computer science can be expressed as categories of universal
coalgebras. With this context, asking for solutions to lifting problems is
posing a question on the representational adequacy of a framework for
generative AI.

######  Definition 2.

Let ${\cal C}$ be a category. A solution to a lifting problem in ${\cal C}$ is
a morphism $h:B\rightarrow X$ in ${\cal C}$ satisfying $p\circ h=\nu$ and
$h\circ f=\mu$ as indicated in the diagram below.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{h}$$\scriptstyle{\nu}$

Although lifting diagrams have been proposed for deep learning architectures
recently Papillon et al. (2023), it is important to stress that the notion of
simplicial complex used in this paper, as well as other notions used in
computer graphics is fundamentally different from our paper. In our case,
simplicial complexes are directional, since each edge is defined by a
directional arrow, not an undirected arrow. The edges correspond to morphisms,
and indeed, a basic question that we will ask is under what circumstances can
directional morphisms be inverted. This question is fundamental to solving
extension problems, and in really nice settings like Kan complexes, all
morphisms can be inverted since all inner and outer horn extension problems
have solutions.

Figure 8: We propose two families of GAIA models in this paper (see Section 7
for details), based on coends and ends Loregian (2021). In this diagram, the
bifunctor $F\in\mbox{Cat}({\cal C}^{op}\times{\cal C},{\cal D})$ acts both
contravariantly and covariantly on objects in the category ${\cal C}$. Coend
and end objects correspond to objects in the category ${\cal D}$. Coend GAIA
models are based on topological realizations of the simplicial model, whereas
end GAIA models are based on probabilistic generative models.

In the literature on higher-order category theory Joyal (2002); Lurie (2009,
2022) and homotopy theory Gabriel et al. (1967); Richter (2020); Quillen
(1967), lifting diagrams were used to define structures such as Kan complexes
that possess nice extension properties. For example, for any given topological
space $X$, there is a functor that defines a simplicial set
$\mbox{Sing}_{\bullet}(X)$ defined by all continuous functions from the
topological simplex $\Delta_{n}$ into the space $X$. The simplicial set
$\mbox{Sing}_{\bullet}(X)$ is a Kan complex because all “horn extensions" of
simplicial subsets can be solved. In practical terms, this property explains
the success of dimensionality reduction methods like UMAP McInnes et al.
(2018), which constructs functors from simplicial sets that represent data
into topological spaces. The topological realization of simplicial sets
computed by UMAP is an example of a coend, a unifying “integral calculus"
proposed originally by Yoneda Yoneda (1960). Loregian (2021) gives a detailed
description of the integral calculus of (co)ends, which provides a unifying
way to design an entire spectrum of generative AI systems, where systems based
on ends leads to probabilistic generative models like Transformers, whereas
models based on coends lead to topologically based generative AI systems that
have not been explored in the literature.

In this paper, we use the framework of lifting diagrams to both formulate
queries as shown in Figure 1, but also to define the problem of building
foundation models from data. In particular, we build on the framework of
simplicial sets and objects, where we pose lifting diagram queries as solving
“horn extension" problems Lurie (2009). Formally, we pose the problem of
learning in a generative AI system in terms of properties such as Kan
complexes May (1992), which are ideal categories to solve lifting problems
since there is a unique solution to all extension problems (inner and outer
horn extensions). As a concrete example, every topological space can be mapped
into a simplicial set using the singular functor, which was used in the UMAP
McInnes et al. (2018) dimensionality reduction method, which can be shown to
form a Kan complex.

Beginning at the top layer, GAIA uses the simplicial category of ordinal
numbers May (1992) as a way to build, manipulate, and destroy compositional
structures. The category of ordinal numbers $\Delta$ includes a collection of
objects indexed by the ordinals $[n],n\geqslant 0$, where $[n]=(0,1,\ldots,n)$
under the natural ordering $<$. The morphisms of $\Delta$ are order-preserving
functions $f:[n]\rightarrow[m]$ where $f(i)\leqslant f(j),i\leqslant
j,i,j\in[n]$. The category $\Delta$ has provided the basis for a combinatorial
approach to topology and also serves as the basis for higher-order category
theory Joyal (2002); Lurie (2009); Gabriel et al. (1967). This category “comes
to life" when it is functorially mapped to some other category, such as Sets,
when the resulting structure is called a simplicial set. The contravariant
functor $X:\Delta^{op}\rightarrow{\bf Sets}$ is defined by viewing $X([0])$ as
a set of “objects", $X[1])$ as a set of “arrows" representing pairwise
interactions among the objects, and in general, $X([n])$ – which is often
simply written as $X_{n}$ and consists of a set of $n$-simplices – defines
interactions of order $n$ among the objects. Simplicial sets generalize
directed graphs, partial orders, sequences, and in fact, regular categories
MacLane (1971) as well. There are constructor and destructor morphisms that
map from $X([n])$ to $X([n+1])$ and $X([n])$ to $X(n-1])$, which are usually
denoted as degeneracy and face operators.

The second layer of GAIA defines a category of generative AI models, which can
be composed of any of the standard technologies used to build generative
models, including finite and probabilistic automata, context-free grammars,
structured state-space sequence models Gu et al. (2022) or Transformer models
Vaswani et al. (2017), or cellular automata Vollmar (2006); Wolfram (2002). We
assume that each of these models defines a category whose objects and arrows
can be composed and otherwise manipulated by the simplicial category $\Delta$.

The third layer of GAIA defines the category of (relational) databases out of
which the category of foundation models is build (e.g., such as by using one
of the standard generative AI methods, such as self-attention Vaswani et al.
(2017) or structured state-space sequence models Gu et al. (2022)). Spivak and
Kent (2012) has shown that categories provide a foundation for defining
relational databases, and that many common operations in databases can be
defined in terms of lifting diagrams in topology Gavrilovich (2017). In
particular, a fundamental premise of GAIA is that machine learning is defined
as the extension of functors on categories, not functions on sets Wagstaff et
al. (2022). The fundamental reason to view machine learning as extending
functors is that there are two canonical solutions to the problem of extending
functors, defined as left and right Kan extensions Kan (1958). In contrast,
there is no obvious or natural solution to the problem of extending functions
on sets, which has prompted an enormous literature in the field of machine
learning over many decades, and also in fields like information theory Chaitin
(2002); Cover and Thomas (2006). Lifting diagrams provide an elegant and
general framework to pose the problem of generalization for generative AI,
based not just on individual units of experience, but by providing a
theoretically sound way to do generalization over arbitrary relational
structures. Much of the work in machine learning has focused on the ability to
generalize propositional representations, which also includes most of the work
in statistics. To generalize over first-order relational structures requires
bringing in some powerful tools from algebraic topology and higher-order
category theory, in particular the ability to do horn filling of simplicial
horns Lurie (2009).

###  1.1 Roadmap to the Paper

Given the length of this paper, a roadmap to its organization will be helpful
to the reader. Keep in mind that this paper is a condensed version of a
forthcoming book, which is designed to provide a detailed tutorial level
introduction to category theory, in addition to illustrating its application
to generative AI. With that mind, Section 2 begins us off with a detailed look
at a category theory of deep learning, building on the work of Fong et al.
(2019). The crucial idea of separating the algebraic structure of a generative
AI model from its parameterization, which in turn is independent of the
structure of a learning framework is crucial to our framework as well,
although GAIA differs in many ways from the approach proposed in Fong et al.
(2019).

Section 3 gives our alternative view of backpropagation as an endofunctor, in
particular a universal coalgebra of the form $X\rightarrow F(X)$, where the
endofunctor $F$ maps objects $X$ in a category ${\cal C}$ back to the same
category. Universal coalgebras Jacobs (2016); Rutten (2000) provide a rich
language for specifying dynamical systems, and they have also been extended to
describe probabilistic generative models, such as Markov chains Sokolova
(2011), Markov decision processes Feys et al. (2018) and a wealth of
programming-related abstractions Jacobs (2016).

Section 4 defines the simplicial layer of GAIA, which acts like a
“combinatorial factory" that can assemble together pieces of generative AI
models. The heart of the GAIA framework is that the simplicial category allows
a hierarchical framework for generative AI, which we believe goes beyond the
purely sequential framework thus far studied in the literature. We illustrate
how hierarchical learning works in GAIA in terms of lifting problems in
simplicial sets. Section 5 defines particular categories for generative AI,
including the popular Transformer architecture as permutation equivariant
functions over Euclidean spaces. Section 6 defines universal properties and
the Yoneda Lemma, which are used to define universal parameterizations of
generative AI models. In particular, we show that non-symmetric generalized
metric spaces can be studied with the metric Yoneda Lemma, which has
applications in constructing non-symmetric attention models for natural
language.

Section 7 defines an abstract integral calculus for generative AI, based on
Yoneda’s pioneering work Yoneda (1960). Loregian (2021) gives a detailed
textbook level account of (co)end calculus. We define two classes of
generative AI models, those based on coends and ends. We show that coend GAIA
models lead to topological realizations, whereas GAIA models based on ends
lead to probabilistic generative AI models. We also introduce sheaves and
topoi as alternative parameterizations of generative AI models, which arise
from the Yoneda Lemma, and can give additional structure over simply using
Euclidean spaces. Section 8 finally defines abstract notions of equivalence in
category theory for comparing two generative AI models. When can we say, for
example, that a summarized document produced by a generative AI copilot is
actually faithful to the original document on which it was based? Homotopy
theory provides some answers to these questions, which have only been studied
empirically in the literature. We introduce the notion of a classifying space
for generative AI models, and define their homotopy colimits.

The paper covers a great deal of abstract mathematics, but we have attempted
to provide a range of concrete examples of its application to the problem of
generative AI. Many more examples can be given, but would significantly
increase the length of an already really long paper! Ultimately, as we
conclude at the end, the real proof of the utility of GAIA will come from its
actual implementation as a working system, but we view that as a multi-year
research problem. There are many open problems that are remaining to be worked
out, and we discuss a few of them in the paper at various places.

##  2 Backpropagation as a Functor: Compositional Learning

Our principal goal in this section to review the categorical framework for
deep learning proposed in Fong et al. (2019), which models backpropagation as
a functor. In the next section, we will argue that backpropagation should be
viewed instead as an endufunctor on the category Param, which defines the
space over which generative AI model are defined.

We first give a high-level introduction to generative AI, building on the
framework of category theory (see Figure 9). Category theory is intrinsically
a framework for compositional structures, which generative AI exemplifies as
well. Excellent textbook length treatments are readily available and should be
consulted for further background MacLane (1971); MacLane and leke Moerdijk
(1994); Riehl (2017); Richter (2020). We summarize salient concepts from
category theory as and when needed. We define several types of categories in
this section, beginning with a category for supervised learning, and then
other categories that represent machine learning algorithms, including the
traditional backpropagation algorithm, and zeroth-order optimization, as well
as categories for specific deep learning architectures, such as Transformers,
structured state space sequence models, and diffusion models. We then
introduce some key ideas from category theory, including the fundamental
Yoneda Lemma that shows all objects in a category can be characterized in
terms of their interactions.

Figure 9: Categories are defined by collection of arbitrary objects that
interact through morphisms (also called arrows). Functors map objects from one
category into another, but also map the arrows of the domain category into
corresponding arrows in the co-domain category. We define generative AI
systems and learning algorithms as categories in GAIA.

###  2.1 Category of Supervised Learning

Fong et al. (2019) give an elegant characterization of the well-known
backpropagation algorithm that serves as the “workhorse" of deep learning as a
functor over symmetric monoidal categories. In such categories, objects can be
“multiplied": for example, sets form a symmetric monoidal category as the
Cartesian product of two sets defines a multiplication operator. A detailed
set of coherence axioms are defined for monoidal categories (see MacLane
(1971) for details), which we will not go through, but they ensure that
multiplication is associative, as well as that there are identity operators
such that $I\otimes A\simeq A$ for all objects $A$, where $I$ is the identity
object.

Figure 10: A learner in the symmetric monoidal category Learn is defined as a
morphism. Later in Section 3, we will see how to define learners as coalgebras
instead.

######  Definition 3.

Fong et al. (2019) The symmetric monoidal category Learn is defined as a
collection of objects that define sets, and a collection of an equivalence
class of learners. Each learner is defined by the following $4$-tuple (see
Figure 10).

  * •

A parameter space $P$

  * •

An implementation function $I:P\times A\rightarrow B$

  * •

An update function $U:P\times A\times B\rightarrow P$

  * •

A request function $r:P\times A\times B\rightarrow A$

Note that it is the request function that allows learners to be composed, as
each request function transmits information back upstream to earlier learners
what output they could have produced that would be more “desirable". This
algebraic characterization of the backpropagation algorithm clarifies its
essentially compositional nature

Two learners $(P,I,U,R)$ and $(P^{\prime},I^{\prime},U^{\prime},r^{\prime})$
are equivalent if there is a bijection $f:P\rightarrow P^{\prime}$ such that
the following identities hold for each $p\in P,a\in A$ and $b\in B$.

  * •

$I^{\prime}(f(p),a)=I(p,a)$.

  * •

$U^{\prime}(f(p),a,b)=f(U(p,a,b))$.

  * •

$r^{\prime}(f(p),a,b)=r(p,a,b)$

Typically, in generative AI trained with neural networks, the parameter space
$P=\mathbb{R}^{N}$ where the neural network has $N$ parameters. The
implementation function $I$ represents the “feedforward" component, and the
request function represents the “backpropagation" component. The update
function represents the change in parameters as a result of processing a
training example $(a,f(a))\in A\times B$. The main contribution of Fong et al.
(2019) is in showing that supervised learning can be defined as a
compositional category under the sequential composition of morphisms defining
individual building blocks of learners.

Figure 11: Sequential and parallel composition of two learners in the
symmetric monoidal category Learn.

Fong et al. (2019) show that each learner can be combined in sequentially and
in parallel (see Figure 11), both formally using the operations of composition
$\circ$ and tensor product $\otimes$ in the symmetric monoidal category Learn,
and equivalently in terms of string diagrams. For clarity, let us write out
the compositional rule for a pair of learners

$A\xrightarrow[]{(P,I,U,r)}B\xrightarrow[]{(Q,J,V,s)}C$

The composite learner $A\rightarrow C$ is defined as $(P\times Q,I\cdot
J,U\cdot V,r\cdot s)$, where the composite implementation function is

$(I\cdot J)(p,q,a)\coloneqq J(q,I(p,a))$

and the composite update function is

$U\cdot V(p,q,a,c)\coloneqq\left(U(p,a,s(q,I(p,a),c)\right),V(q,I(p,a),c)$

and the composite request function is

$(r\cdot s)(p,q,a,c)\coloneqq r(p,a,s(q,I(p,a),c)).$

###  2.2 Backpropagation as a Functor

We can define the backpropagation procedure as a functor that maps from the
category Para to the category Learn. Functors can be viewed as a
generalization of the notion of morphisms across algebraic structures, such as
groups, vector spaces, and graphs. Functors do more than functions: they not
only map objects to objects, but like graph homomorphisms, they need to also
map each morphism in the domain category to a corresponding morphism in the
co-domain category. Functors come in two varieties, as defined below. The
Yoneda Lemma, in its most basic form, asserts that any set-valued functor
$F:{\cal C}\rightarrow{\bf Sets}$ can be universally represented by a
representable functor ${\cal C}(-,x):{\cal C}^{op}\rightarrow{\bf Sets}$.

######  Definition 4.

A covariant functor $F:{\cal C}\rightarrow{\cal D}$ from category ${\cal C}$
to category ${\cal D}$, and defined as the following:

  * •

An object $FX$ (also written as $F(X)$) of the category ${\cal D}$ for each
object $X$ in category ${\cal C}$.

  * •

An arrow $F(f):FX\rightarrow FY$ in category ${\cal D}$ for every arrow
$f:X\rightarrow Y$ in category ${\cal C}$.

  * •

The preservation of identity and composition: $F\ id_{X}=id_{FX}$ and
$(Ff)(Fg)=F(g\circ f)$ for any composable arrows $f:X\rightarrow
Y,g:Y\rightarrow Z$.

######  Definition 5.

A contravariant functor $F:{\cal C}\rightarrow{\cal D}$ from category ${\cal
C}$ to category ${\cal D}$ is defined exactly like the covariant functor,
except all the arrows are reversed.

The functoriality axioms dictate how functors have to be behave:

  * •

For any composable pair $f,g$ in category $C$, $Fg\cdot Ff=F(g\cdot f)$.

  * •

For each object $c$ in $C$, $F(1_{c})=1_{Fc}$.

Note that the category Learn is ambivalent as to what particular learning
method is used. To define a particular learning method, such as
backpropagation, we can define a category whose objects define the parameters
of the particular learning method, and then another category for the learning
method itself. We can define a functor from the category NNet to the category
Learn that factors through the category Param. Later in the next section, we
show how to generlize this construction to simplicial sets.

${NNet}$${Learn}$${Param}$$\scriptstyle{F}$$\scriptstyle{L_{\epsilon,e}}$

######  Definition 6.

Fong et al. (2019) The category Param defines a strict symmetric monoidal
category whose objects are Euclidean spaces, and whose morphisms
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ are equivalence classes of
differential parameterized functions. In particular, $(P,I)$ defines a
Euclidean space $P$ and $I:P\times A\rightarrow B$ defines a differentiable
parameterized function $A\rightarrow B$. Two such pairs
$(P,I),(P^{\prime},I^{\prime})$ are considered equivalent if there is a
differentiable bijection $f:P\rightarrow P^{\prime}$ such that for all $p\in
P$, and $a\in A$, we have that $I^{\prime}(f^{\prime}(p),a)=I(p,a)$. The
composition of $(P,I):\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ and
$(Q,J):\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is given as

$(P\times Q,I\cdot J)\ \ \ \mbox{where}\ \ \ (I\cdot J)(p,q,a)=J(q,I(p,a))$

The monoidal product of objects $\mathbb{R}^{n}$ and $\mathbb{R}^{m}$ is the
object $\mathbb{R}^{n+m}$, whereas the monoidal product of morphisms
$(P,I):\mathbb{R}^{m}\rightarrow\mathbb{R}^{m}$ and
$(Q,J):\mathbb{R}^{l}\rightarrow\mathbb{R}^{k}$ is given as $(P\times
Q,I\parallel J)$, where

$(I\parallel J)(p,q,a,c)=\left(I(p,a),J(q,c)\right)$

Symmetric monoidal categories can also be braided. In this case, the braiding
$\mathbb{R}^{m}\parallel\mathbb{R}^{m}\rightarrow\mathbb{R}^{m}\parallel\mathbb{R}^{n}$
is given as $(\mathbb{R}^{0},\sigma)$ where $\sigma(a,b)=(b,a)$.

The backpropagation algorithm can itself be defined as a functor over
symmetric monoidal categories

$L_{\epsilon,e}:{\tt Param}\rightarrow{\tt Learn}$

where $\epsilon>0$ is a real number defining the learning rate for
backpropagation, and $e(x,y):\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$
is a differentiable error function such that $\frac{\partial e}{\partial
x}(x_{0},-)$ is invertible for each $x_{0}\in\mathbb{R}$. This functor
essentially defines an update procedure for each parameter in a compositional
learner. In other words, the functor $L_{\epsilon,e}$ defined by
backpropagation sends each parameterized function $I:P\times A\rightarrow B$
to the learner $(P,I,U_{I},r_{I})$

$U_{I}(p,a,b)\coloneqq p-\epsilon\nabla_{p}E_{I}(p,a,b)$

$r_{I}(p,a,b)\coloneqq f_{a}(\nabla_{a}E_{I}(p,a,b))$

where $E_{I}(p,a,b)\coloneqq\sum_{j}e(I_{j}(p,a),b_{j})$ and $f_{a}$ is a
component-wise application of the inverse to $\frac{\partial e}{\partial
x}(a_{i},-)$ for each $i$.

Note that we can easily define functors that define other ways of doing
parameterized updates, such as a stochastic approximation method Robbins and
Monro (1951) that updates each parameter using only the (noisy) value of the
function at the current value of the parameter, and uses a gradual decay of
the learning parameters to “simulate" the process of taking gradients. These
sort of stochastic approximation updates are now called “zeroth-order"
optimization in the deep learning literature.

##  3 Backpropagation as an Endofunctor: Generative AI using Universal
Coalgebras

Our categorical framework for generative AI differs in crucial ways from the
analysis in Fong et al. (2019) that defined backpropagation as a functor, but
not an endofunctor. In their framework, which we reviewed in the previous
section, backpropagation was modeled as a functor from the category Param to
the cateory Learn, but that masks the simple fact that the goal of learning is
to produce a new set of parameters (i.e., construct a new object in Param).
Once you complete that loop, backpropagation becomes an endofunctor. This
property allows bringing in the rich framework of universal coalgebras Jacobs
(2016); Rutten (2000) to analyze a whole family of endofunctors for generative
AI.

As the ultimate goal of backpropagation at each step is to produce a new
parameter, i.e. a new object in Param, we argue that our endofunctor
characterization provides a rich source of insight into the analysis of
generative AI methods. Accordingly, we review below the theory of universal
coalgebras, and then show more formally how to model backpropagation and other
similiar generative AI methods as coalgebras.

###  3.1 Non-Well-Founded Sets and Universal Coalgebras

Figure 12: Generative models define an infinite stream of tokens. Solving an
‘imitation game" Turing (1950) that involves comparing two infinite data
streams involves the process of deciding if two non-well-founded sets are
categorically bisimulations of each otherAczel (1988); Rutten (2000).

To begin with, we present an elegant formalism for defining generative AI
models as universal coalgebras Rutten (2000), and non-well-founded sets Aczel
(1988). Figure 12 illustrates the main idea. We define the two participants in
an imitation game as universal coalgebras (or non-well-founded sets) and ask
if there is a bisimulation relationship between them. This characterization
covers a wide range of probabilistic models, including Markov chains and
Markov decision processes Sutton and Barto (1998), and automata-theoretic
models, as well as generative AI models Gu et al. (2023).

Generative AI has become popular recently due to the successes of neural and
structured-state space sequence models Gu et al. (2022); Vaswani et al. (2017)
and text-to-image diffusion models Song and Ermon (2019). The underlying
paradigm of building generative models has a long history in computer science
and AI, and it is useful to begin with the simplest models that have been
studied for several decades, such as deterministic finite state machines,
Markov chains, and context-free grammars. We use category theory to build
generative AI models and analyze them, which is one of the unique and novel
aspects of this paper. To explain briefly, we represent a generative model in
terms of universal coalgebras Rutten (2000) generated by an endofunctor $F$
acting on a category $C$. Coalgebras provide an elegant way to model dynamical
systems, and capture the notion of state Jacobs (2016) in ways that provide
new insight into the design of AI and ML systems. Perhaps the simplest and in
some ways, the most general, type of generative AI model that is representable
as a coalgebra is the powerset functor

$F:S\Rightarrow{\cal P}(S)$

where $S$ is any set (finite or not), and ${\cal P}(S)$ is the set of all
subsets of $S$, that is:

${\cal P}(S)=\\{A|A\subseteq S\\}$

Notice in the specification of the powerset functor coalgebra, the same term
$S$ appears on both sides of the equation. That is a hallmark of coalgebras,
and it is what distinguishes coalgebras from algebras. Coalgebras generate
search spaces, whereas algebras compact search spaces and summarize them. This
admittedly simple structure nonetheless is extremely versatile and enables
modeling a remarkably rich and diverse set of generative AI models, including
the ones listed in Figure 13. To explain briefly, we can model a context-free
grammar as a mapping from a set $S$ that includes all the vertices in the
context-free grammar graph shown in Figure 13 to the powerset of the set $S$.
More specifically, if $S=N\cup T$ is defined as the non-terminals $N$ as well
as the terminal symbols (the actual words) $T$, any context-free grammar rule
can be represented in terms of a power set functor. We will explain how this
approach can be refined later in this Section, and in much more detail in
later sections of the paper. To motivate further why category theory provides
an elegant way to model generative AI systems, we look at some actual examples
of generative AI systems to see why they can be modeled as functors.

Figure 13: In this paper, generative AI models, from the earliest models
studied in computer science such as deterministic finite state automata and
context-free grammars, to models in statistics and information theory like
Markov chains, and lastly, sequence models can be represented as universal
coalgebras.

To compare say two large language models, we need to compare two potentially
infinite data streams of tokens (e.g., words, or in general, other forms of
communication represented digitally by bits). Many problems in AI and ML
involve reasoning about circular phenomena. These include reasoning about
common knowledge Barwise and Moss (1996); Fagin et al. (1995) such as social
conventions, dealing with infinite data structures such as lists or trees in
computer science, and causal inference in systems with feedback where part of
the input comes from the output of the system. In all these situations, there
is an intrinsic problem of having to deal with infinite sets that are
recursive and violate a standard axiom called well-foundedness in set theory.
First, we explain some of the motivations for including non-well-founded sets
in AI and ML, and then proceed to define the standard ZFC axiomatization of
set theory and how to modify it to allow circular sets. We build on the
pioneering work of Peter Aczel on the anti-foundation-axiom in modeling non-
well-founded sets Aczel (1988), which has elaborated previously in other books
as well Barwise and Moss (1996); Jacobs (2016), although we believe this paper
is perhaps one of the first to focus on the application of non-well-founded
sets and universal coalgebras to problems in AI and ML at a broad level.

Figure 14: Three representations of infinite data streams: non-well-founded
set $x=\\{x\\}$: accessible pointed graphs (AGPs), non-well-founded sets
specified by systems of equations, and universal coalgebras. We can view these
as generative models of the recursive set $\\{\\{\\{\ldots\\}\\}\\}$.

Figure 14 illustrates three ways to represent an infinite object, as a
directed graph, a (non-well-founded) set or as a system of equations. We begin
with perhaps the simplest approach introduced by Peter Aczel called accessible
pointed graphs (APGs) (see Figure 14), but also include the category-theoretic
approach of using universal coalgebras Rutten (2000), as well as systems of
equations Barwise and Moss (1996).

We now turn to describing coalgebras, a much less familiar construct that will
play a central role in the proposed ML framework of coinductive inference.
Coalgebras capture hidden state, and enable modeling infinite data streams.
Recall that in the previous Section, we explored non-well-founded sets, such
as the set $\Omega=\\{\Omega\\}$, which gives rise to a circularly defined
object. As another example, consider the infinite data stream comprised of a
sequence of objects, indexed by the natural numbers:

$X=(X_{0},X_{1},\ldots,X_{n},\ldots)$

We can define this infinite data stream as a coalgebra, comprised of an
accessor function head that returns the head of the list, and a destructor
function that gives the tail of the list, as we will show in detail below.

To take another example, consider a deterministic finite state machine model
defined as the tuple $M=(X,A,\delta)$, where $X$ is the set of possible states
that the machine might be in, $A$ is a set of input symbols that cause the
machine to transition from one state to another, and $\delta:X\times
A\rightarrow X$ specifies the transition function. To give a coalgebraic
definition of a finite state machine, we note that we can define a functor
$F:X\rightarrow{\cal P}(A\times X)$ that maps any given state $x\in X$ to the
subset of possible future states $y$ that the machine might transition to for
any given input symbol $a\in A$.

We can now formally define $F$-coalgebras analogous to the definition of
$F$-algebras given above.

######  Definition 7.

Let $F:{\cal C}\rightarrow{\cal C}$ be an endofunctor on the category ${\cal
C}$. An $F$-coalgebra is defined as a pair $(A,\alpha)$ comprised of an object
$A$ and an arrow $\alpha:A\rightarrow F(A)$.

The fundamental difference between an algebra and a coalgebra is that the
structure map is reversed! This might seem to be a minor distinction, but it
makes a tremendous difference in the power of coalgebras to model state and
capture dynamical systems. Let us use this definition to capture infinite data
streams, as follows.

${\bf Str}:{\bf Set}\rightarrow{\bf Set},\ \ \ \ \ \ {\bf
Str}(X)=\mathbb{N}\times X$

Here, Str is defined as a functor on the category Set, which generates a
sequence of elements. Let $N^{\omega}$ denote the set of all infinite data
streams comprised of natural numbers:

$N^{\omega}=\\{\sigma|\sigma:\mathbb{N}\rightarrow\mathbb{N}\\}$

To define the accessor function head and destructor function tail alluded to
above, we proceed as follows:

$\displaystyle{\bf head}$ $\displaystyle:$
$\displaystyle\mathbb{N}^{\omega}\rightarrow\mathbb{N}\ \ \ \ \ \ \ {\bf
tail}:\mathbb{N}^{\omega}\rightarrow\mathbb{N}^{\omega}$ (1)
$\displaystyle{\bf head}(\sigma)$ $\displaystyle=$ $\displaystyle\sigma(0)\ \
\ \ \ \ \ {\bf tail}(\sigma)=(\sigma(1),\sigma(2),\ldots)$ (2)

Another standard example that is often used to illustrate coalgebras, and
provides a foundation for many AI and ML applications, is that of a labelled
transition system.

######  Definition 8.

A labelled transition system (LTS) $(S,\rightarrow_{S},A)$ is defined by a set
$S$ of states, a transition relation $\rightarrow_{S}\subseteq S\times A\times
S$, and a set $A$ of labels (or equivalently, “inputs" or “actions"). We can
define the transition from state $s$ to $s^{\prime}$ under input $a$ by the
transition diagram $s\xrightarrow[]{a}s^{\prime}$, which is equivalent to
writing $\langle s,a,s^{\prime}\rangle\in\rightarrow_{S}$. The ${\cal
F}$-coalgebra for an LTS is defined by the functor

${\cal F}(X)={\cal P}(A\times X)=\\{V|V\subseteq A\times X\\}$

Just as before, we can also define a category of $F$-coalgebras over any
category ${\cal C}$, where each object is a coalgebra, and the morphism
between two coalgebras is defined as follows, where $f:A\rightarrow B$ is any
morphism in the category ${\cal C}$.

######  Definition 9.

Let $F:{\cal C}\rightarrow{\cal C}$ be an endofunctor. A homomorphism of
$F$-coalgebras $(A,\alpha)$ and $(B,\beta)$ is an arrow $f:A\rightarrow B$ in
the category ${\cal C}$ such that the following diagram commutes:

${A}$${B}$${F(A)}$${F(B)}$$\scriptstyle{f}$$\scriptstyle{\alpha}$$\scriptstyle{\beta}$$\scriptstyle{F(f)}$

For example, consider two labelled transition systems $(S,A,\rightarrow_{S})$
and $(T,A,\rightarrow_{T})$ over the same input set $A$, which are defined by
the coalgebras $(S,\alpha_{S})$ and $(T,\alpha_{T})$, respectively. An
$F$-homomorphism $f:(S,\alpha_{S})\rightarrow(T,\alpha_{T})$ is a function
$f:S\rightarrow T$ such that $F(f)\circ\alpha_{S}=\alpha_{T}\circ f$.
Intuitively, the meaning of a homomorphism between two labeled transition
systems means that:

  * •

For all $s^{\prime}\in S$, for any transition
$s\xrightarrow[]{a}_{S}s^{\prime}$ in the first system $(S,\alpha_{S})$, there
must be a corresponding transition in the second system
$f(s)\xrightarrow[]{a}_{T}f(s;)$ in the second system.

  * •

Conversely, for all $t\in T$, for any transition
$t\xrightarrow[]{a}_{T}t^{\prime}$ in the second system, there exists two
states $s,s^{\prime}\in S$ such that $f(s)=t,f(t)=t^{\prime}$ such that
$s\xrightarrow[]{a}_{S}s^{\prime}$ in the first system.

If we have an $F$-homomorphism $f:S\rightarrow T$ with an inverse
$f^{-1}:T\rightarrow S$ that is also a $F$-homomorphism, then the two systems
$S\simeq T$ are isomorphic. If the mapping $f$ is injective, we have a
monomorphism. Finally, if the mapping $f$ is a surjection, we have an
epimorphism.

The analog of congruence in universal algebras is bisimulation in universal
coalgebras. Intuitively, bisimulation allows us to construct a more “abstract"
representation of a dynamical system that is still faithful to the original
system. We will explore many applications of the concept of bisimulation to AI
and ML systems in this paper. We introduce the concept in its general setting
first, and then in the next section, we will delve into concrete examples of
bisimulations.

######  Definition 10.

Let $(S,\alpha_{S})$ and $(T,\alpha_{T})$ be two systems specified as
coalgebras acting on the same category ${\cal C}$. Formally, a
$F$-bisimulation for coalgebras defined on a set-valued functor $F:{\bf
Set}\rightarrow{\bf Set}$ is a relation $R\subset S\times T$ of the Cartesian
product of $S$ and $T$ is a mapping $\alpha_{R}:R\rightarrow F(R)$ such that
the projections of $R$ to $S$ and $T$ form valid $F$-homomorphisms.

${R}$${S}$${F(R)}$${F(S)}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\alpha_{R}}$$\scriptstyle{\alpha_{S}}$$\scriptstyle{F(\pi_{1})}$

${R}$${T}$${F(R)}$${F(T)}$$\scriptstyle{\pi_{2}}$$\scriptstyle{\alpha_{R}}$$\scriptstyle{\alpha_{T}}$$\scriptstyle{F(\pi_{2})}$

Here, $\pi_{1}$ and $\pi_{2}$ are projections of the relation $R$ onto $S$ and
$T$, respectively. Note the relationships in the two commutative diagrams
should hold simultaneously, so that we get

$\displaystyle F(\pi_{1})\circ\alpha_{R}$ $\displaystyle=$
$\displaystyle\alpha_{S}\circ\pi_{1}$ $\displaystyle
F(\pi_{2})\circ\alpha_{R}$ $\displaystyle=$
$\displaystyle\alpha_{T}\circ\pi_{2}$

Intuitively, these properties imply that we can “run" the joint system $R$ for
one step, and then project onto the component systems, which gives us the same
effect as if we first project the joint system onto each component system, and
then run the component systems. More concretely, for two labeled transition
systems that were considered above as an example of an $F$-homomorphism, an
$F$-bisimulation between $(S,\alpha_{S})$ and $(T,\alpha_{T})$ means that
there exists a relation $R\subset S\times T$ that satisfies for all $\langle
s,t\rangle\in R$

  * •

For all $s^{\prime}\in S$, for any transition
$s\xrightarrow[]{a}_{S}s^{\prime}$ in the first system $(S,\alpha_{S})$, there
must be a corresponding transition in the second system
$f(s)\xrightarrow[]{a}_{T}f(s;)$ in the second system, so that $\langle
s^{\prime},t^{\prime}\rangle\in R$

  * •

Conversely, for all $t\in T$, for any transition
$t\xrightarrow[]{a}_{T}t^{\prime}$ in the second system, there exists two
states $s,s^{\prime}\in S$ such that $f(s)=t,f(t)=t^{\prime}$ such that
$s\xrightarrow[]{a}_{S}s^{\prime}$ in the first system, and $\langle
s^{\prime},t^{\prime}\rangle\in R$.

A simple example of a bisimulation of two coalgebras is shown in Figure 15.

Figure 15: A bisimulation among two coalgebras.

There are a number of basic properties about bisimulations, which we will not
prove, but are useful to summarize here:

  * •

If $(R,\alpha_{R})$ is a bisimulation between systems $S$ and $T$, the inverse
$R^{-1}$ of $R$ is a bisimulation between systems $T$ and $S$.

  * •

Two homomorphisms $f:T\rightarrow S$ and $g:T\rightarrow U$ with a common
domain $T$ define a span. The image of the span $\langle
f,g\rangle(T)=\\{\langle f(t),g(t)\rangle|t\in T\\}$ of $f$ and $g$ is also a
bisimulation between $S$ and $U$.

  * •

The composition $R\circ Q$ of two bisimulations $R\subseteq S\times T$ and
$Q\subseteq T\times U$ is a bisimulation between $S$ and $U$.

  * •

The union $\cup_{k}R_{k}$ of a family of bisimulations between $S$ and $T$ is
also a bisimulation.

  * •

The set of all bisimulations between systems $S$ and $T$ is a complete
lattice, with least upper bounds and greatest lower bounds given by:

$\bigvee_{k}R_{k}=\bigcup_{k}R_{k}$

$\bigwedge_{K}R_{k}=\bigcup\\{R|R\ \mbox{is a bisimulation between}S\
\mbox{and}\ T\ \mbox{and}\ R\subseteq\cap_{k}R_{k}\\}$

  * •

The kernel $K(f)=\\{\langle s,s^{\prime}\rangle|f(s)=f(s^{\prime})\\}$ of a
homomorphism $f:S\rightarrow T$ is a bisimulation equivalence.

###  3.2 Backpropagation as a Coalgebra

Finally, we return to the original goal of this section, which is to argue
that any generative AI machine learning method can be usefully modeled not
just as a functor, but rather as an endofunctor that maps an object in a
category Param of parameters into a new object as a result of doing a machine
learning step, such as a gradient update. We can now formally define
backpropagation as a coalgebra over the caetgory Param as follows.

Recall that the category Param defines a strict symmetric monoidal category
whose objects are Euclidean spaces, and whose morphisms
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ are equivalence classes of
differential parameterized functions. To see why the backpropagation algorithm
can be defined as an endofunctor over the symmetric monoidal category Param,
recall from the previous section that backpropagation was viewed as a functor
from the cateory Param to the cateogry Learn.

$L_{\epsilon,e}:{\tt Param}\rightarrow{\tt Learn}$

where $\epsilon>0$ is a real number defining the learning rate for
backpropagation, and $e(x,y):\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$
is a differentiable error function such that $\frac{\partial e}{\partial
x}(x_{0},-)$ is invertible for each $x_{0}\in\mathbb{R}$. This functor
essentially defines an update procedure for each parameter in a compositional
learner. In other words, the functor $L_{\epsilon,e}$ defined by
backpropagation sends each parameterized function $I:P\times A\rightarrow B$
to the learner $(P,I,U_{I},r_{I})$

$U_{I}(p,a,b)\coloneqq p-\epsilon\nabla_{p}E_{I}(p,a,b)$

$r_{I}(p,a,b)\coloneqq f_{a}(\nabla_{a}E_{I}(p,a,b))$

where $E_{I}(p,a,b)\coloneqq\sum_{j}e(I_{j}(p,a),b_{j})$ and $f_{a}$ is a
component-wise application of the inverse to $\frac{\partial e}{\partial
x}(a_{i},-)$ for each $i$.

But a simpler and we argue more elegant characterization of backpropagation is
to view it as a coalgebra or dynamical system defined by an endofunctor on
Param. Here, we view the inputs $A$ and outputs $B$ as the input “symbols" and
output produced by a dynamical system. The actual process of updating the
parameters need not be defined as “gradient descent", but it can involve any
other functor (as we saw earlier, it could involve a stochastic approximation
method Borkar (2008)). Our revised definition of backpropagation as an
endofunctor follows. Note that this definition is generic, and applies to
virtually any approach to building foundation models that updates each object
to a new object in the category Param as a result of processing a data
instance.

######  Definition 11.

Backpropagation defines an $F_{B}$-coalgebra over the symmetric monoidal
category Param, specified by an endofunctor $X\rightarrow F_{B}(X)$ defined as

$F_{B}(X)=A\times B\times X$

Note that in this definition, the endofunctor $F_{B}$ takes an object $X$ of
Param, which is a set of network weights of a generative AI model, and
produces a new set of weights, where $A$ is the “input" symbol of the
dynamical system and $B$ is the output symbol.

###  3.3 Zeroth-Order Deep Learning using Stochastic Approximation

To illustrate how the broader coalgebraic definition of backpropagation is
more useful than the previous definition in Fong et al. (2019), we describe a
class of generative AI methods based on adapting stochastic approximation
Robbins and Monro (1951) to deep learning, which are popularly referred to
zeroth-order optimization Liu et al. (2009) (see Figure 16). A vast range of
stochastic approximation methods have been explored in the literature (e.g.,
see Borkar (2008); Kushner and Yin (2003)). For example, in random directions
stochastic approximation, each parameter is adjusted in a random direction by
sampling from distribution, such as a multivariate normal, or a uniform
distribution. Any of these zeroth-order stochastic approximation algorithms
can itself be defined as a functor over symmetric monoidal categories

$L^{0}_{\epsilon}:{\tt Param}\rightarrow{\tt Learn}$

where $\epsilon>0$ is a real number defining a learning rate parameter that is
gradually decayed. Notice now that the error of the approximation with respect
to the target plays no role in the update process itself. backpropagation, and
$e(x,y):\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$ is a differentiable
error function such that $\frac{\partial e}{\partial x}(x_{0},-)$ is
invertible for each $x_{0}\in\mathbb{R}$. The functor $L^{0}_{\epsilon}$
defined by zeroth-order optimization sends each parameterized function
$I:P\times A\rightarrow B$ to the learner $(P,I,U^{0}_{I},r^{0}_{I})$

$U^{0}_{I}(p,a,b)\coloneqq p-\epsilon I(p,a,b)$

Here, the $1$-point gradient estimate is approximated by the (noisy) sampled
value, averaged over multiple steps using a decaying learning rate as required
by the convergence theorems of stochastic approximation Robbins and Monro
(1951); Kushner and Yin (2003). The advantages of zeroth-order stochastic
approximation methods are that it avoids computing gradients over a very large
number of parameters (which for state of the art generative AI models can be
in the billions or trillions of parameters), and it potentially helps avoid
local minima by stochastically moving around in a very high-dimensional space.
The disadvantage is that it can be significantly slower than gradient-based
methods for well-behaved (convex) functions.

Figure 16: Zeroth-order optimization methods for generative AI are based on
stochastic approximation, and average noisy values of the function to
approximate gradient steps. Such methods define probabilistic coalgebras
Sokolova (2011).

We can easily extend our previous definition of backpropagation as a coalgebra
to capture zeroth-order optimization methods which act like stochastic
dynamical systems, where there is a distribution of possible “next" states
that is produced as a result of doing stochastic approximation updates.

######  Definition 12.

Stochastic Backpropagation defines an $F_{\mbox{SGD}}$-coalgebra over the
symmetric monoidal category Param, specified by an endofunctor $X\rightarrow
F_{\mbox{SGD}}B(X)$ defined as

$F_{\mbox{SGD}}(X)=A\times B\times{\cal D}(X)$

where $F_{\mbox{SGD}}$ defines the variant of backpropagation defined by
stochastic gradient descent, and ${\cal D}$ is the distribution functor over
$X$ that defines a distribution over possible objects $X$ in Param. There is a
vast literature on stochastic coalgebras that can be defined in terms of such
distribution functors. Sokolova (2011) contains an excellent review of this
literature.

###  3.4 Lambek’s Theorem and Final Coalgebras: Analyzing the Convergence of
Generative AI Algorithms

Another advantage modeling backpropagation as a coalgebra defined by an
endofunctor is that it provides an elegant way to analyze the problem of
convergence of the algorithm to some (local) minimum solution. We explain the
general principle of using final coalgebras as a generalization of (greatest)
fixed points in this section. Later in Section 6, when we introduce the metric
Yoneda Lemma, we will show how to use the metric coinduction property to
analyze convergence of backpropagation.

Let us illustrate the concept of final coalgebras defined by a functor that
represents a monotone function over the category defined by a preorder
$(S,\leqslant)$, where $S$ is a set and $\leqslant$ is a relation that is
reflexive and transitive. That is, $a\leqslant a,\forall a\in S$, and if
$a\leqslant b$, and $b\leqslant c$, for $a,b,c\in S$, then $a\leqslant c$.
Note that we can consider $(S,\leqslant)$ as a category, where the objects are
defined as the elements of $S$ and if $a\leqslant b$, then there is a unique
arrow $a\rightarrow b$.

Let us define a functor $F$ on a preordered set $(S,\leqslant)$ as any
monotone mapping $F:S\rightarrow S$, so that if $a\leqslant b$, then
$F(a)\leqslant F(b)$. Now, we can define an $F$-algebra as any pre-fixed point
$x\in S$ such that $F(x)\leqslant x$. Similarly, we can define any post-fixed
point to be any $x\in S$ such that $x\leqslant F(x)$. Finally, we can define
the final $F$-coalgebra to be the greatest post-fixed point $x\leqslant F(x)$,
and analogously, the initial $F$-algebra to be the least pre-fixed point of
$F$.

In this section, we give a detailed overview of the concept of final
coalgebras in the category of coalgebras parameterized by some endofunctor
$F$. This fundamental notion plays a central role in the application of
universal coalgebras to model a diverse range of AI and ML systems. Final
coalgebras generalize the concept of (greatest) fixed points in many areas of
application in AI, including causal inference, game theory and network
economics, optimization, and reinforcement learning among others. The final
coalgebra, simply put, is just the final object in the category of coalgebras.
From the universal property of final objects, it follows that for any other
object in the category, there must be a unique morphism to the final object.
This simple property has significant consequences in applications of the
coalgebraic formalism to AI and ML, as we will see throughout this paper.

An $F$-system $(P,\pi)$ is termed final if for another $F$-system
$(S,\alpha_{S})$, there exists a unique homomorphism
$f_{S}:(S,\alpha_{S})\rightarrow(P,\pi)$. That is, $(P,\pi)$ is the terminal
object in the category of coalgebras $Set_{F}$ defined by some set-valued
endofunctor $F$. Since the terminal object in a category is unique up to
isomorphism, any two final systems must be isomorphic.

######  Definition 13.

An $F$-coalgebra $(A,\alpha)$ is a fixed point for $F$, written as $A\simeq
F(A)$ if $\alpha$ is an isomorphism between $A$ and $F(A)$. That is, not only
does there exist an arrow $A\rightarrow F(A)$ by virtue of the coalgebra
$\alpha$, but there also exists its inverse $\alpha^{-1}:F(A)\rightarrow A$
such that

$\alpha\circ\alpha^{-1}=\mbox{{\bf id}}_{F(A)}\ \ \mbox{and}\ \
\alpha^{-1}\circ\alpha=\mbox{{\bf id}}_{A}$

The following lemma was shown by Lambek, and implies that the transition
structure of a final coalgebra is an isomorphism.

######  Theorem 1.

Lambek: A final $F$-coalgebra is a fixed point of the endofunctor $F$.

Proof: The proof is worth including in this paper, as it provides a classic
example of the power of diagram chasing. Let $(A,\alpha)$ be a final
$F$-coalgebra. Since $(F(A),F(\alpha)$ is also an $F$-coalgebra, there exists
a unique morphism $f:F(A)\rightarrow A$ such that the following diagram
commutes:

${F(A)}$${A}$${F(F(A))}$${F(A)}$$\scriptstyle{f}$$\scriptstyle{F(\alpha)}$$\scriptstyle{\alpha}$$\scriptstyle{F(f)}$

However, by the property of finality, the only arrow from $(A,\alpha)$ into
itself is the identity. We know the following diagram also commutes, by virtue
of the definition of coalgebra homomorphism:

${A}$${F(A)}$${F(A)}$${F(F(A))}$$\scriptstyle{\alpha}$$\scriptstyle{\alpha}$$\scriptstyle{\alpha}$$\scriptstyle{F(\alpha)}$

Combining the above two diagrams, it clearly follows that $f\circ\alpha$ is
the identity on object $A$, and it also follows that $F(\alpha)\circ F(f)$ is
the identity on $F(A)$. Therefore, it follows that:

$\alpha\circ f=F(f)\circ F(\alpha)=F(f\circ\alpha)=F(\mbox{{\bf
id}}_{A})=\mbox{{\bf id}}_{F(A)}\qed$

By reversing all the arrows in the above two commutative diagrams, we get the
easy duality that the initial object in an $F$-algebra is also a fixed point.

######  Theorem 2.

Dual to Lambek: The initial $F$-algebra $(A,\alpha)$, where
$\alpha:F(A)\rightarrow A$, in the category of $F$-algebras is a fixed point
of $F$.

The proof of the duality follows in the same way, based on the universal
property that there is a unique morphism from the initial object in a category
to any other object.

Lambek’s lemma has many implications, one of which is that final coalgebras
generalize the concept of a (greatest) fixed point, which can be applied to
analyze the convergence of generative AI methods, such as backpropagation.
Generally speaking, in optimization, we are looking to find a solution $x\in
X$ in some space $X$ that minimizes a smooth real-valued function
$f:X\rightarrow\mathbb{R}$. Since $f$ is smooth, a natural algorithm is to
find its minimum by computing the gradient $\nabla f$ over the space $X$. The
function achieves its minimum if $\nabla f=0$, which can be written down as a
fixed point equation.

###  3.5 Metric Coinduction for Generative AI

To make the somewhat abstract discussion of final coalgebras above a bit more
concrete, we now briefly describe the concept of metric coinduction Kozen and
Ruozzi (2009), which is a special case of the general principle of coinduction
Aczel (1988); Rutten (2000). The basic idea is simple to describe, and is
based on viewing algorithms as forming contraction mappings in a metric space.
The novelty here for many readers is understanding how this well-studied
notion of contractive mappings is related to coinduction and coalgebras. One
way to analyze the convergence of iterative methods like backproapgation is to
see if they can be shown to form contraction mappings in a metric space.

Consider a complete metric space $(V,d)$ where $d:V\times V\rightarrow(0,1)$
is a symmetric distance function that satisfies the triangle inequality, and
all Cauchy sequences in $V$ converge (We will see later that the property of
completeness itself follows from the Yoneda Lemma!). A function
$H:V\rightarrow V$ is contractive if there exists $0\leqslant c<1$ such that
for all $u,v\in V$,

$d(H(u),H(v))\leqslant c\cdot d(u,v)$

In effect, applying the algorithm represented by the continuous mapping $H$
causes the distances between $u$ and $v$ to shrink, and repeated application
eventually guarantees convergence to a fixed point. The novelty here is to
interpret the fixed point as a final coalgebra. We will later see that the
concept of a (greatest) fixed point is generalized by the concept of final
coalgebras.

######  Definition 14.

Metric Coinduction Principle Kozen and Ruozzi (2009): If $\phi$ is a closed
nonempty subset of a complete metric space $V$, and if $H$ is an eventually
contractive map on $V$ that preserves $\phi$, then the unique fixed point
$u^{*}$ of $H$ is in $\phi$. In other words, we can write:

$\displaystyle\exists u\phi(u),\ \ \ \forall\phi(u)$
$\displaystyle\Rightarrow$ $\displaystyle\phi(H(u))$
$\displaystyle\phi(u^{*})$

It should not be surprising to those familiar with contraction mapping style
arguments that a large number of applications in AI and ML, including game
theory, reinforcement learning and stochastic approximation involve proofs of
convergence that exploit properties of contraction mappings. What might be
less familiar is how to think of this in terms of the concept of coinductive
inference. To explain this perspective briefly, let us introduce the relevant
category theoretic terminology.

Let us define a category $C$ whose objects are nonempty closed subsets of $V$,
and whose arrows are reverse set inclusions. That is, there is a unique arrow
$\phi_{1}\rightarrow\phi_{2}$ if $\phi_{1}\supseteq\phi_{2}$. Then, we can
define an endofunctor $\bar{H}$ as the closure mapping
${\bar{H}}(\phi)=\mbox{cl}(H(\phi))$, where cl denotes the closure in the
metric topology of $V$. Note that $\bar{H}$ is an endofunctor on $C$ because
$\bar{H}(\phi_{1})\supseteq\bar{H}(\phi_{2})$ whenever
$\phi_{1}\supseteq\phi_{2}$.

######  Definition 15.

An $\bar{H}$-coalgebra is defined as the pair
$(\phi,\phi\supseteq\bar{H}(\phi))$ (or equivalently, we can write
$\phi\subseteq H(\phi)$. The final coalgebra is the isomorphism
$u^{*}\simeq\bar{H}(u^{*})$ where $u^{*}$ is the unique fixed point of the
mapping $H$. The metric coinduction rule can be restated more formally in this
case as:

$\phi\supseteq H(\phi)\ \ \Rightarrow\ \ \phi\supseteq H(u^{*})$

This result has deep significance, as we will see later, and provides an
elegant way to prove contraction style arguments in very general settings. In
particular, it can be applied to analyze the convergence of machine learning
methods for GAIA models to see if they can be shown to convergence in a
(generalized) metric space. We will postpone the details of this analysis to a
subsequent paper

##  4 Layer 1 of GAIA: Simplicial Sets for Generative AI

Figure 17: (A) GAIA is based on a hierarchical simplicial sets and objects.
The base simplicial set $X_{0}$ is a set of entities that can be mapped to
computational entities in generative AI, such as a tokens in a large language
model, or images in a diffusion based system. The set $X_{1}$ defines a
collection of morphisms between pairs of objects in $X_{0}$, where each
morphism could define a deep learning module as explained in Section 2. (B)
The first two sets $X_{0}$ and $X_{1}$ essentially define what is possible
with today’s compositionally based generative AI system using backpropagation,
where learning is conceived of as an entirely sequential process. (C) $X_{2}$
and higher-level simplicial sets constitute the novel core of GAIA: here,
groups of sub-simplicial objects act like business units with a common
objective. Each $n$-simplex has $n+1$ sub-simplicial complexes, and
information is transmitted hierarchically in GAIA from superior simplicial
sets to subordinate simplicial sets using lifting diagrams. (D) Solving “outer
horn" extension problems is more challenging for methods like deep learning
with backpropagation, than solving “inner horn" extensions.

Unlike earlier generative AI architectures, GAIA uses the paradigm of
simplicial sets and objects as the basic building blocks for generative AI
(see Figure 3). We can still cast much of the earlier work described above in
terms of GAIA, but this flexibility gives us the power to also formulate
generative AI approaches that lie beyond the scope of compositional learning
methods, such as backpropagation. As we illustrated in Figure 6, GAIA puts
together building blocks of generative AI methods as $n$-simplices of a
simplicial set. In the simplest setting, these combine compositionally in the
way that Fong et al. (2019) defined for the category Learn that we discussed
in detail in the previous section. It is possible to take the category Learn
and embed it in the category of simplicial sets using the nerve functor Lurie
(2022), which is a full and faithful embedding of the category as a simplicial
set. Each $n$-simplex is then defined by $n$-length sequences of a generative
AI system, like a Transformer building block that computes a permutation-
equivariant map. But the left adjoint of the nerve functor that maps back from
the simplicial set category is a “lossy" functor that does not generate a full
and faithful embedding, which shows why simplicial learning is more powerful
in principle than compositional learning.

The first layer of GAIA is based on the simplicial category $\Delta$, which
serves as a “combinatorial factory" for piecing together building blocks of
generative AI systems into larger units, and for decomposing complex systems
into their component subsystems. The category $\Delta$ is defined over ordinal
numbers $[n],n\geqslant 0$, but really “comes to life" when it is plugged into
some concrete category, such as the ones described in the previous section
like Learn or Para. For example, if the parameters of a learning method are
defined over a category of Sets, then a contravariant functor from $\Delta$
into sets is called a simplicial set May (1992). We can also define functors
from $\Delta$ into some category of generative AI models, like Transformers
Vaswani et al. (2017) or structured state space sequence (S4) models Gu et al.
(2022) or diffusion models Song and Ermon (2019).

###  4.1 Simplicial Sets and Objects

As shown in Figure 17, a simplicial set can be viewed as a collection of sets,
or a graded set, $S_{n},n\geqslant 0$, where $S_{0}$ defines the primitive
objects (which can be elements of the category Param defined in the previous
section), $S_{1}$ represents a collection of “edge" objects (which can be
viewed as Learners as defined in the previous section), $S_{2}$ represents
simplices of three objects interacting, and in general, $S_{n}$ defines a
collection of objects that represents interactions of order $n$. These higher-
level simplicial sets act like “business units" in a company: they have a
hierarchical structure, receive inputs and outputs from higher-level superiors
and lower-level subordinates, and adjust their internal parameters. These
$n$-simplicial sets are related to each other by degeneracy operators that map
$S_{n}$ into $S_{n+1}$ or face operators that map $S_{n}$ into $S_{n-1}$.
Figure 6 shows an example of a $3$-simplex. Note how in Figure 3, the
simplicial set $X_{3}$ sends “back" information to $X_{2}$ through four face
operators. These exactly correspond to the four subsimplices of each object in
$X_{3}$, as illustrated in Figure 3, because each $3$-simplex has four faces.
The crux of the GAIA framework is to treat each such simplex as a building
block of a generative AI system.

Simplicial sets are higher-dimensional generalizations of directed graphs,
partially ordered sets, as well as regular categories themselves. Importantly,
simplicial sets and simplicial objects form a foundation for higher-order
category theory. Simplicial objects have long been a foundation for algebraic
topology, and more recently in higher-order category theory. The category
$\Delta$ has non-empty ordinals $[n]=\\{0,1,\ldots,n]$ as objects, and order-
preserving maps $[m]\rightarrow[n]$ as arrows. An important property in
$\Delta$ is that any many-to-many mapping is decomposable as a composition of
an injective and a surjective mapping, each of which is decomposable into a
sequence of elementary injections $\delta_{i}:[n]\rightarrow[n+1]$, called
coface mappings, which omits $i\in[n]$, and a sequence of elementary
surjections $\sigma_{i}:[n]\rightarrow[n-1]$, called co-degeneracy mappings,
which repeats $i\in[n]$. The fundamental simplex $\Delta([n])$ is the presheaf
of all morphisms into $[n]$, that is, the representable functor
$\Delta(-,[n])$. The Yoneda Lemma assures us that an $n$-simplex $x\in X_{n}$
can be identified with the corresponding map $\Delta[n]\rightarrow X$. Every
morphism $f:[n]\rightarrow[m]$ in $\Delta$ is functorially mapped to the map
$\Delta[m]\rightarrow\Delta[n]$ in ${\cal S}$.

Any morphism in the category $\Delta$ can be defined as a sequence of co-
degeneracy and co-face operators, where the co-face operator
$\delta_{i}:[n-1]\rightarrow[n],0\leqslant i\leqslant n$ is defined as:

$\delta_{i}(j)=\left\\{\begin{array}[]{ll}j,&\mbox{for }\ 0\leqslant
j\leqslant i-1\\\ j+1&\mbox{for }\ i\leqslant j\leqslant
n-1\end{array}\right.$

Analogously, the co-degeneracy operator $\sigma_{j}:[n+1]\rightarrow[n]$ is
defined as

$\sigma_{j}(k)=\left\\{\begin{array}[]{ll}j,&\mbox{for }\ 0\leqslant
k\leqslant j\\\ k-1&\mbox{for }\ j<k\leqslant n+1\end{array}\right.$

Note that under the contravariant mappings, co-face mappings turn into face
mappings, and co-degeneracy mappings turn into degeneracy mappings. That is,
for any simplicial object (or set) $X_{n}$, we have $X(\delta_{i})\coloneqq
d_{i}:X_{n}\rightarrow X_{n-1}$, and likewise, $X(\sigma_{j})\coloneqq
s_{j}:X_{n-1}\rightarrow X_{n}$.

The compositions of these arrows define certain well-known properties May
(1992); Richter (2020):

$\displaystyle\delta_{j}\circ\delta_{i}$ $\displaystyle=$
$\displaystyle\delta_{i}\circ\delta_{j-1},\ \ i<j$
$\displaystyle\sigma_{j}\circ\sigma_{i}$ $\displaystyle=$
$\displaystyle\sigma_{i}\circ\sigma_{j+1},\ \ i\leqslant j$
$\displaystyle\sigma_{j}\circ\delta_{i}(j)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\sigma_{i}\circ\sigma_{j+1},&\mbox{for
}\ i<j\\\ 1_{[n]}&\mbox{for }\ i=j,j+1\\\
\sigma_{i-1}\circ\sigma_{j},\mbox{for}\ i>j+1\end{array}\right.$

######  Example 1.

The “vertices” of a simplicial object ${\cal C}_{n}$ are the objects in ${\cal
C}$, and the “edges” of ${\cal C}$ are its arrows $f:X\rightarrow Y$, where
$X$ and $Y$ are objects in ${\cal C}$. Given any such arrow, the degeneracy
operators $d_{0}f=Y$ and $d_{1}f=X$ recover the source and target of each
arrow. Also, given an object $X$ of category ${\cal C}$, we can regard the
face operator $s_{0}X$ as its identity morphism ${\bf 1}_{X}:X\rightarrow X$.

######  Example 2.

Given a category ${\cal C}$, we can identify an $n$-simplex $\sigma$ of a
simplicial set ${\cal C}_{n}$ with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

the face operator $d_{0}$ applied to $\sigma$ yields the sequence

$d_{0}\sigma=C_{1}\xrightarrow[]{f_{2}}C_{2}\xrightarrow[]{f_{3}}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{0}$ is “deleted” along with the morphism $f_{0}$ leaving
it.

######  Example 3.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
${\cal C}_{n}$, the face operator $d_{n}$ applied to $\sigma$ yields the
sequence

$d_{n}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n-1}}C_{n-1}$

where the object $C_{n}$ is “deleted” along with the morphism $f_{n}$ entering
it. Note this face operator can be viewed as analogous to interventions on
leaf nodes in a causal DAG model.

######  Example 4.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
${\cal C}_{n}$ the face operator $d_{i},0<i<n$ applied to $\sigma$ yields the
sequence

$d_{i}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots
C_{i-1}\xrightarrow[]{f_{i+1}\circ
f_{i}}C_{i+1}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{i}$ is “deleted” and the morphisms $f_{i}$ is composed
with morphism $f_{i+1}$. Note that this process can be abstractly viewed as
intervening on object $C_{i}$ by choosing a specific value for it (which
essentially “freezes” the morphism $f_{i}$ entering object $C_{i}$ to a
constant value).

######  Example 5.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
${\cal C}_{n}$, the degeneracy operator $s_{i},0\leqslant i\leqslant n$
applied to $\sigma$ yields the sequence

$s_{i}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots
C_{i}\xrightarrow[]{{\bf
1}_{C_{i}}}C_{i}\xrightarrow[]{f_{i+1}}C_{i+1}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{i}$ is “repeated” by inserting its identity morphism
${\bf 1}_{C_{i}}$.

######  Definition 16.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
${\cal C}_{n}$, $\sigma$ is a degenerate simplex if some $f_{i}$ in $\sigma$
is an identity morphism, in which case $C_{i}$ and $C_{i+1}$ are equal.

###  4.2 Hierarchical Learning in GAIA by solving Lifting Problems

As we mentioned earlier, a crucial difference between GAIA and earlier
generative AI architectures is that it is based on a hierarchical model of
simplicial learning, rather than the standard compositional learning framework
described in Section 2. To understand how such a structure will work, we need
to define some key ideas from higher-order category theory below, but before
we do that, we want to build up some intuition as to how this process will
work at a more informal level. Figure 18 illustrates the idea using the same
figure we showed earlier as Figure 3, but here, we will use it to illustrate
the simplicial learning concept.

Figure 18: Example of a “small business unit" in GAIA defined as a $3$-simplex
that maintains its set of internal parameters, and updates them based on
information it receives from its superiors and subordinates.

To understand how simplicial learning works, let us consider as an example the
$3$-simplex shown in Figure 18. We generalize the earlier compositional model
defined in Section 4, where in the category Learn (see Figure 10), each
learner was a morphism in the symmetric monoidal category. In that model, each
learner morphism transmits information downstream to its successors and
upstream to its predecessors, but there is no hierarchical structure. Here, in
Figure 18, the simplicial structure defines a hierarchy of learners, so that
each learner is not just a morphism anymore, but a $n$-simplex that maintains
its internal set of parameters that it then updates based on the information
from its superiors and subordinates. To define this more carefully, we can
construct a functor that maps the algebraic structure of a simplicial set
$\Delta$ into a suitable parameter space (e.g., a symmetric monoidal category
like vector spaces), whereby each $n$-simplex now becomes defined as a
contravariant functor $\Delta^{op}\rightarrow{\bf Vect}$.

We can in fact use exactly the same updates defined earlier in Section 4,
following Fong et al. (2019), with the crucial difference being that the
updates must be consistent across the hierarchical structure of the simplicial
complex. So, each $n$-simplex is updated based on data from its subordinate
$n-1$ sub-simplicial complexes and its superior $n+1$-simplicial complexes,
but these need to be made consistent with each other. To solve this problem
requires some additional machinery from higher-order category theory, which we
now introduce below.

Lifting problems provide elegant ways to define solutions to computational
problems in category theory regarding the existence of mappings. We will use
these lifting diagrams later in this paper. For example, the notion of
injective and surjective functions, the notion of separation in topology, and
many other basic constructs can be formulated as solutions to lifting
problems. Lifting problems define ways of decomposing structures into simpler
pieces, and putting them back together again.

######  Definition 17.

Let ${\cal C}$ be a category. A lifting problem in ${\cal C}$ is a commutative
diagram $\sigma$ in ${\cal C}$.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{\nu}$

######  Definition 18.

Let ${\cal C}$ be a category. A solution to a lifting problem in ${\cal C}$ is
a morphism $h:B\rightarrow X$ in ${\cal C}$ satisfying $p\circ h=\nu$ and
$h\circ f=\mu$ as indicated in the diagram below.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{h}$$\scriptstyle{\nu}$

######  Definition 19.

Let ${\cal C}$ be a category. If we are given two morphisms $f:A\rightarrow B$
and $p:X\rightarrow Y$ in ${\cal C}$, we say that $f$ has the left lifting
property with respect to $p$, or that p has the right lifting property with
respect to f if for every pair of morphisms $\mu:A\rightarrow X$ and
$\nu:B\rightarrow Y$ satisfying the equations $p\circ\mu=\nu\circ f$, the
associated lifting problem indicated in the diagram below.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{h}$$\scriptstyle{\nu}$

admits a solution given by the map $h:B\rightarrow X$ satisfying $p\circ
h=\nu$ and $h\circ f=\mu$.

Gavrilovich (2017) shows that a remarkable number of properties in mathematics
can be defined as lifting problems. Spivak (2013) showed that query answering
in languages like SQL in relational databases can be formalized as lifting
problems. Mahadevan (2023) showed that causal inference could be posed in
terms of lifting problems. At its heart, a lifting problem defines a
constrained search over a space of parameters, and it is that property that
makes it so useful in generative AI because in effect, methods like
backpropagation can be viewed as solving lifting problems. As a simple example
to build intuition, here is a way any surjective (onto) function as a solution
to a lifting problem.

######  Example 6.

Given the paradigmatic non-surjective morphism
$f:\emptyset\rightarrow\\{\bullet\\}$, any morphism p that has the right
lifting property with respect to f is a surjective mapping. .

${\emptyset}$${X}$${\\{\bullet\\}}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{h}$$\scriptstyle{\nu}$

Similarly, here is another lifting problem whose solution defines an $1-1$
injective function.

######  Example 7.

Given the paradigmatic non-injective morphism
$f:\\{\bullet,\bullet\\}\rightarrow\\{\bullet\\}$, any morphism p that has the
right lifting property with respect to f is an injective mapping. .

${\\{\bullet,\bullet\\}}$${X}$${\\{\bullet\\}}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{p}$$\scriptstyle{h}$$\scriptstyle{\nu}$

###  4.3 Simplicial Subsets and Horns in GAIA

To explain how lifting problems can be used for generative AI in GAIA, we need
to define lifting problems over $n$-simplicial complexes. The basic idea, as
illustrated in Figure 18, is that we construct a solution to a lifting problem
by asking if a particular sub-simplicial complex can be “extended" into the
whole complex. This extension process is essentially what methods like
backpropagation are doing, and universal approximation results for
Transformers Yun et al. (2020) are in effect saying that a solution to a
lifting problem exists for a particular class of simplicial complexes defined
as $n$-length sequences of Transformer models.

We first describe more complex ways of extracting parts of categorical
structures using simplicial subsets and horns. These structures will play a
key role in defining suitable lifting problems.

######  Definition 20.

The standard simplex $\Delta^{n}$ is the simplicial set defined by the
construction

$([m]\in\Delta)\mapsto{\bf Hom}_{\Delta}([m],[n])$

By convention, $\Delta^{-1}\coloneqq\emptyset$. The standard $0$-simplex
$\Delta^{0}$ maps each $[n]\in\Delta^{op}$ to the single element set
$\\{\bullet\\}$.

######  Definition 21.

Let $S_{\bullet}$ denote a simplicial set. If for every integer $n\geqslant
0$, we are given a subset $T_{n}\subseteq S_{n}$, such that the face and
degeneracy maps

$d_{i}:S_{n}\rightarrow S_{n-1}\ \ \ \ s_{i}:S_{n}\rightarrow S_{n+1}$

applied to $T_{n}$ result in

$d_{i}:T_{n}\rightarrow T_{n-1}\ \ \ \ s_{i}:T_{n}\rightarrow T_{n+1}$

then the collection $\\{T_{n}\\}_{n\geqslant 0}$ defines a simplicial subset
$T_{\bullet}\subseteq S_{\bullet}$

######  Definition 22.

The boundary is a simplicial set $(\partial\Delta^{n}):\Delta^{op}\rightarrow$
Set defined as

$(\partial\Delta^{n})([m])=\\{\alpha\in{\bf Hom}_{\Delta}([m],[n]):\alpha\
\mbox{is not surjective}\\}$

Note that the boundary $\partial\Delta^{n}$ is a simplicial subset of the
standard $n$-simplex $\Delta^{n}$.

######  Definition 23.

The Horn $\Lambda^{n}_{i}:\Delta^{op}\rightarrow$ Set is defined as

$(\Lambda^{n}_{i})([m])=\\{\alpha\in{\bf
Hom}_{\Delta}([m],[n]):[n]\not\subseteq\alpha([m])\cup\\{i\\}\\}$

Intuitively, the Horn $\Lambda^{n}_{i}$ can be viewed as the simplicial subset
that results from removing the interior of the $n$-simplex $\Delta^{n}$
together with the face opposite its $i$th vertex.

Consider the problem of composing $1$-dimensional simplices to form a
$2$-dimensional simplicial object. Each simplicial subset of an $n$-simplex
induces a a horn $\Lambda^{n}_{k}$, where $0\leqslant k\leqslant n$.
Intuitively, a horn is a subset of a simplicial object that results from
removing the interior of the $n$-simplex and the face opposite the $i$th
vertex. Consider the three horns defined below. The dashed arrow
$\dashrightarrow$ indicates edges of the $2$-simplex $\Delta^{2}$ not
contained in the horns.

${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$

The inner horn $\Lambda^{2}_{1}$ is the middle diagram above, and admits an
easy solution to the “horn filling” problem of composing the simplicial
subsets. The two outer horns on either end pose a more difficult challenge.
For example, filling the outer horn $\Lambda^{2}_{0}$ when the morphism
between $\\{0\\}$ and $\\{1\\}$ is $f$ and that between $\\{0\\}$ and
$\\{2\\}$ is the identity ${\bf 1}$ is tantamount to finding the left inverse
of $f$ up to homotopy. Dually, in this case, filling the outer horn
$\Lambda^{2}_{2}$ is tantamount to finding the right inverse of $f$ up to
homotopy. A considerable elaboration of the theoretical machinery in category
theory is required to describe the various solutions proposed, which led to
different ways of defining higher-order category theory Boardman and Vogt
(1973); Joyal (2002); Lurie (2009).

###  4.4 Higher-Order Categories

We now formally introduce higher-order categories, building on the framework
proposed in a number of formalisms. We briefly summarize various approaches to
the horn filling problem in higher-order category theory.

######  Definition 24.

Let $f:X\rightarrow S$ be a morphism of simplicial sets. We say $f$ is a Kan
fibration if, for each $n>0$, and each $0\leqslant i\leqslant n$, every
lifting problem.

${\Lambda^{n}_{i}}$${X}$${\Delta^{n}}$${S}$$\scriptstyle{\sigma_{0}}$$\scriptstyle{f}$$\scriptstyle{\sigma}$$\scriptstyle{\bar{\sigma}}$

admits a solution. More precisely, for every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow X$ and every $n$-simplex
$\bar{\sigma}:\Delta^{n}\rightarrow S$ extending $f\circ\sigma_{0}$, we can
extend $\sigma_{0}$ to an $n$-simplex $\sigma:\Delta^{n}\rightarrow X$
satisfying $f\circ\sigma=\bar{\sigma}$.

######  Example 8.

Given a simplicial set $X$, then a projection map $X\rightarrow\Delta^{0}$
that is a Kan fibration is called a Kan complex.

######  Example 9.

Any isomorphism between simplicial sets is a Kan fibration.

######  Example 10.

The collection of Kan fibrations is closed under retracts.

######  Definition 25.

Lurie (2009) An $\infty$-category is a simplicial object $S_{\bullet}$ which
satisfies the following condition:

  * •

For $0<i<n$, every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{\bullet}$ can be extended to a map
$\sigma:\Delta^{n}\rightarrow S_{i}$.

This definition emerges out of a common generalization of two other conditions
on a simplicial set $S_{i}$:

  1. 1.

Property K: For $n>0$ and $0\leqslant i\leqslant n$, every map of simplicial
sets $\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{\bullet}$ can be extended to a
map $\sigma:\Delta^{n}\rightarrow S_{i}$.

  2. 2.

Property C: for $0<1<n$, every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{i}$ can be extended uniquely to a
map $\sigma:\Delta^{n}\rightarrow S_{i}$.

Simplicial objects that satisfy property K were defined above to be Kan
complexes. Simplicial objects that satisfy property C above can be identified
with the nerve of a category, which yields a full and faithful embedding of a
category in the category of sets. definition 25 generalizes both of these
definitions, and was called a quasicategory in Joyal (2002) and weak Kan
complexes in Boardman and Vogt (1973) when ${\cal C}$ is a category.

##  5 Layer 2 of GAIA: Generative AI using Simplicial Categories

The second layer of GAIA is based on defining generative models as universal
coalgebras over some base category, including the standard mathematical
categories (Sets, measurable spaces Meas, topoogical spaces Top or Vector
spaces Vect). Existing approaches to generative AI, such as Transformers
Vaswani et al. (2017), structured state-space models Gu et al. (2022), or
image diffusion models Song and Ermon (2019) can all be defined as
(stochastic) coalgebras over one of the base categories. We first introduce
some basic categorical structures, and then define the category of universal
coalgebras over these. to define generative AI systems as coalgebras.

###  5.1 Categories as Building Blocks of GAIA

GAIA is built on the hypothesis that category theory provides a universal
language for encoding foundation models. We define a few salient aspects of
category theory in this section, including showing how it can reveal
surprising similarities between algebraic structures that superficially look
very different, such as metric spaces and partially ordered sets (see Table
1). A key principle that is often exploited is to explicitly represent the
structure in the collection of morphisms between two objects. That is, for
some category C, the Hom${}_{\cal C}(a,b)$ between objects $a$ and $b$ might
itself have some additional structure beyond that of merely being a collection
or a set. For example, in the category of vector spaces, the set of morphisms
(linear transformations) between two vector spaces $U$ and $V$ is itself a
vector space. So-called V-enriched categories signify cases when the Hom
values are specified in some structure V. Examples include metric spaces,
where the Hom values are non-negative real numbers representing distances, and
partially ordered sets (posets) where the Hom values are Boolean.

Table 1: Categories are defined as collections of objects and arrows between them. C |  HomC values | Composition and | Domain | Domain for
---|---|---|---|---
|  | and identity law | for composition | for identity laws
General category | Sets | Functions | Cartesian product | One element set
Metric spaces | Non-negative numbers | $\geqslant$ | sum | zero
Posets | Truth values | Entailment | Conjunction | true
V-enriched | objects | morphisms | tensor product | unit object for
category | in V | in V | in V | tensor product in V
$F:{\cal C}^{op}\times C\rightarrow D$ | Bivalent functors | Dinatural transformations | Probabilities, distances | Unit object
Coends, ends |  |  | topological embeddings |

The aim of category theory is to build a “unified field theory" of mathematics
based on a simple model of objects that interact with each other, analogous to
directed graph representations. In graphs, vertices represent arbitrary
entities, and the edges denote some form of (directional) interaction. In
categories, there is no restriction on how many edges exist between any two
objects. In a locally small category, there is assumed to be a “set’s worth"
of edges, meaning that it could still be infinite! In addition, small
categories are assumed to contain a set’s worth of objects (again, which might
not be finite). The framework is compositional, in that categories can be
formed out of objects, arrows that define the interaction between objects, or
functors that define the interactions between categories. This
compositionality gives us a rich generative space of models that will be
invaluable in modeling UIGs.

Category theory gives an exceptional set of “measuring tools" for modeling
Transformers and other generative models in AI. Choosing a category means
selecting a collection of objects and a collection of composable arrows by
which each pair of objects interact. This choice of objects and arrows defines
the measurement apparatus that is used in formulating and solving an imitation
game. A key result called the Yoneda Lemma shows that objects can be
identified up to isomorphism solely by their interactions with other objects.
Category theory also embodies the principle of universality: a property is
universal if it defines an initial or final object in a category. Many
approaches in generative AI, such as probabilistic generative models or
distance metrics, can be abstractly characterized as initial or final objects
in a category of wedges, where the objects are bifunctors and the arrows are
dinatural transformations. Loregian (2021) has an excellent treatment of the
calculus of coends, which we will discuss in detail later in the paper. At a
high level, the notion of object isomorphism in category theory is defined as
follows.

######  Definition 26.

Two objects $X$ and $Y$ in a category ${\cal C}$ are deemed isomorphic, or
$X\cong Y$ if and only if there is an invertible morphism $f:X\rightarrow Y$,
namely $f$ is both left invertible using a morphism $g:Y\rightarrow X$ so that
$g\circ f=$ idX, and $f$ is right invertible using a morphism $h$ where
$f\circ h=$ idY.

Category theory provides a rich language to describe how objects interact,
including notions like braiding that plays a key role in quantum computing
Coecke et al. (2016). The notion of isomorphism can be significantly weakened
to include notions like homotopy. This notion of homotopy generalizes the
notion of homotopy in topology, which defines why an object like a coffee cup
is topologically homotopic to a doughnut (they have the same number of
“holes”). In the category Sets, two finite sets are considered isomorphic if
they have the same number of elements, as it is then trivial to define an
invertible pair of morphisms between them. In the category Vectk of vector
spaces over some field $k$, two objects (vector spaces) are isomorphic if
there is a set of invertible linear transformations between them. As we will
see below, the passage from a set to the “free” vector space generated by
elements of the set is another manifestation of the universal arrow property.
In the category of topological spaces Top, two objects are isomorphic if there
is a pair of continuous functions that makes them homeomorphic May and Ponto
(2012). A more refined category is hTop, the category defined by topological
spaces where the arrows are now given by homotopy classes of continuous
functions.

######  Definition 27.

Let $C$ and $C^{\prime}$ be a pair of objects in a category ${\cal C}$. We say
$C$ is a retract of $C^{\prime}$ if there exists maps $i:C\rightarrow
C^{\prime}$ and $r:C^{\prime}\rightarrow C$ such that $r\circ
i=\mbox{id}_{\cal C}$.

######  Definition 28.

Let ${\cal C}$ be a category. We say a morphism $f:C\rightarrow D$ is a
retract of another morphism $f^{\prime}:C\rightarrow D$ if it is a retract of
$f^{\prime}$ when viewed as an object of the functor category Hom$([1],{\cal
C})$. A collection of morphisms $T$ of ${\cal C}$ is closed under retracts if
for every pair of morphisms $f,f^{\prime}$ of ${\cal C}$, if $f$ is a retract
of $f^{\prime}$, and $f^{\prime}$ is in $T$, then $f$ is also in $T$.

The point of these examples is to illustrate that choosing a category, which
means choosing a collection of objects and arrows, is like defining a
measurement system for deciding if two objects are isomorphic. A richer model
of interaction is provided by simplicial sets May (1992), which is a graded
set $S_{n},\ n\geqslant 0$, where $S_{0}$ represents a set of non-interacting
objects, $S_{1}$ represents a set of pairwise interactions, $S_{2}$ represents
a set of three-way interactions, and so on. We can map any category into a
simplicial set by constructing sequences of length $n$ of composable
morphisms. For example, we can model sequences of words in a language as
composable morphisms, thereby constructing a simplicial set representation of
language-based interactions in an imitation game. Then, the corresponding
notion of homotopy between simplicial sets is defined as Richter (2020):

######  Definition 29.

Let X and Y be simplicial sets, and suppose we are given a pair of morphisms
$f_{0},f_{1}:X\rightarrow Y$. A homotopy from $f_{0}$ to $f_{1}$ is a morphism
$h:\Delta^{1}\times X\rightarrow Y$ satisfying $f_{0}=h|_{{0}\times X}$ and
$f_{1}=h_{1\times X}$.

Set theory | Category theory
---|---
set | object
subset | subobject
truth values $\\{0,1\\}$ | subobject classifier $\Omega$
power set $P(A)=2^{A}$ | power object $P(A)=\Omega^{A}$
bijection | isomorphims
injection | monic arrow
surjection | epic arrow
singleton set $\\{*\\}$ | terminal object ${\bf 1}$
empty set $\emptyset$ | initial object ${\bf 0}$
elements of a set $X$ | morphism $f:{\bf 1}\rightarrow X$
- | functors, natural transformations
- | limits, colimits, adjunctions
Figure 19: Comparison of notions from set theory and category theory. Figure
20: Category theory is a compositional model of a system in terms of objects
and their interactions.

Figure 19 compares the basic notions in set theory vs. category theory. Figure
20 illustrates a simple category of 3 objects: $A$, $B$, and $C$ that interact
through the morphisms $f:A\rightarrow B$, $g:B\rightarrow C$, and
$h:A\rightarrow C$. Categories involve a fundamental notion of composition:
the morphism $h:A\rightarrow C$ can be defined as the composition $g\circ f$
of the morphisms from $f$ and $g$. What the objects and morphisms represent is
arbitrary, and like the canonical directed graph model, this abstractness
gives category theory – like graph theory – a universal quality in terms of
applicability to a wide range of problems. While categories and graphs and
intimately related, in a category, there is no assumption of finiteness in
terms of the cardinality of objects or morphisms. A category is defined to be
small or locally small if there is a set’s worth of objects and between any
two objects, a set’s worth of morphisms, but of course, a set need not be
finite. As a simple example, the set of integers $\mathbb{Z}$ defines a
category, where each integer $z$ is an object and there is a morphism
$f:a\rightarrow b$ between integers $a$ and $b$ if $a\leqslant b$. This
example serves to immediately clarify an important point: a category is only
defined if both the objects and morphisms are defined. The category of
integers $\mathbb{Z}$ may be defined in many ways, depending on what the
morphisms represent.

Briefly, a category is a collection of objects, and a collection of morphisms
between pairs of objects, which are closed under composition, satisfy
associativity, and include an identity morphism for every object. For example,
sets form a category under the standard morphism of functions. Groups,
modules, topological spaces and vector spaces all form categories in their own
right, with suitable morphisms (e.g, for groups, we use group homomorphisms,
and for vector spaces, we use linear transformations).

A simple way to understand the definition of a category is to view it as a
“generalized" graph, where there is no limitation on the number of vertices,
or the number of edges between any given pair of vertices. Each vertex defines
an object in a category, and each edge is associated with a morphism. The
underlying graph induces a “free” category where we consider all possible
paths between pairs of vertices (including self-loops) as the set of morphisms
between them. In the reverse direction, given a category, we can define a
“forgetful” functor that extracts the underlying graph from the category,
forgetting the composition rule.

######  Definition 30.

A graph ${\cal G}$ (sometimes referred to as a quiver) is a labeled directed
multi-graph defined by a set $O$ of objects, a set $A$ of arrows, along with
two morphisms $s:A\rightarrow O$ and $t:A\rightarrow O$ that specify the
domain and co-domain of each arrow. In this graph, we define the set of
composable pairs of arrows by the set

$A\times_{O}A=\\{\langle g,f\rangle|\ g,f\in A,\ \ s(g)=t(f)\\}$

A category ${\cal C}$ is a graph ${\cal G}$ with two additional functions:
${\bf id}:$ $O\rightarrow A$, mapping each object $c\in C$ to an arrow ${\bf
id}_{c}$ and $\circ:A\times_{O}A\rightarrow A$, mapping each pair of
composable morphisms $\langle f,g\rangle$ to their composition $g\circ f$.

It is worth emphasizing that no assumption is made here of the finiteness of a
graph, either in terms of its associated objects (vertices) or arrows (edges).
Indeed, it is entirely reasonable to define categories whose graphs contain an
infinite number of edges. A simple example is the group $\mathbb{Z}$ of
integers under addition, which can be represented as a single object, denoted
$\\{\bullet\\}$ and an infinite number of morphisms
$f:\bullet\rightarrow\bullet$, each of which represents an integer, where
composition of morphisms is defined by addition. In this example, all
morphisms are invertible. In a general category with more than one object, a
groupoid defines a category all of whose morphisms are invertible. A central
principle in category theory is to avoid the use of equality, which is
pervasive in mathematics, in favor of a more general notion of isomorphism or
weaker versions of it. Many examples of categories can be given that are
relevant to specific problems in AI and ML. Some examples of categories of
common mathematical structures are illustrated below.

  * •

Set: The canonical example of a category is Set, which has as its objects,
sets, and morphisms are functions from one set to another. The Set category
will play a central role in our framework, as it is fundamental to the
universal representation constructed by Yoneda embeddings.

  * •

Top: The category Top has topological spaces as its objects, and continuous
functions as its morphisms. Recall that a topological space $(X,\Xi)$ consists
of a set $X$, and a collection of subsets $\Xi$ of $X$ closed under finite
intersection and arbitrary unions.

  * •

Group: The category Group has groups as its objects, and group homomorphisms
as its morphisms.

  * •

Graph: The category Graph has graphs (undirected) as its objects, and graph
morphisms (mapping vertices to vertices, preserving adjacency properties) as
its morphisms. The category DirGraph has directed graphs as its objects, and
the morphisms must now preserve adjacency as defined by a directed edge.

  * •

Poset: The category Poset has partially ordered sets as its objects and order-
preserving functions as its morphisms.

  * •

Meas: The category Meas has measurable spaces as its objects and measurable
functions as its morphisms. Recall that a measurable space $(\Omega,{\cal B})$
is defined by a set $\Omega$ and an associated $\sigma$-field of subsets B
that is closed under complementation, and arbitrary unions and intersections,
where the empty set $\emptyset\in{\cal B}$.

###  5.2 A Categorical Theory of Transformer Models

To illustrate the power of the simplicial sets and objects framework, we want
to briefly explain how we can use it to define a novel hierarchical framework
for generative AI, where each morphism $[m]\rightarrow[n]$ can be mapped into
a Transformer module Vaswani et al. (2017). It is straightforward to extend
our discussion below to other building blocks of generative AI systems,
including structured state space sequence models Gu et al. (2022) or image
diffusion models Song and Ermon (2019). As with all generative AI systems, the
fundamental structure of a Transformer model is that it is a compositional
structure made up of modular components, each of which computes a permutation-
equivariant function over the vector space $\mathbb{R}^{d\times n}$ of
$n$-length sequences of tokens, each embedded in a space of dimension $d$. We
can define a commutative diagram showing the permutation equivariant property
as shown below.

To begin with, following Fong et al. (2019), we can generically define a
neural network layer of type $(n_{1},n_{2})$ as a subset
$C\subseteq[n_{1}]\times[n_{2}]$ where $n_{1},n_{2}\in\mathbb{N}$ are natural
numbers, and $[n]=\\{1,\ldots,n\\}$. Notice how these can be viewed as the
objects of a simplicial category $\Delta$. These numbers $n_{1}$ and $n_{2}$
serve to define the number of inputs and outputs of each layer, $C$ is a set
of connections, and $(i,j)\in C$ means that node $i$ is connected to node $j$
in the network diagram. It is straightforward, but perhaps tedious, to define
activation functions $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ for each layer,
but essentially each network layer defines a parameterized function
$I:\mathbb{R}^{|C|+n_{2}}\times\mathbb{R}^{n_{1}}\rightarrow\mathbb{R}^{n_{2}}$,
where the $\mathbb{R}^{|}C|$ define the edge weights of each network edge and
the $\mathbb{R}^{n_{2}}$ factor encodes individual unit biases. We can
specialize these to Transformer models, in particular, noting that the
Transfomer models compute specialized types of permutation-equivariant
functions as defined by the commutative diagram below.

${X}$${Y}$${Z}$${XP}$${YP}$${ZP}$$\scriptstyle{f}$$\scriptstyle{P}$$\scriptstyle{P}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{g}$$\scriptstyle{P}$

In the above commutative diagram, vertices are objects, and arrows are
morphisms that define the action of a Transformer block. Here,
$X\in\mathbb{R}^{d\times n}$ is a $n$-length sequence of tokens of
dimensionality $d$. $P$ is a permutation matrix. The function $f$ computed by
a Transformer block is such that $f(XP)=f(X)P$. This property is defined in
the above diagram by setting $Y=f(X)P$, which can be computed in two ways,
either first by permuting the input by the matrix $P$, and then applying $f$,
or by

Let us understand the permutation equivariant property of the Transformer
model in a bit more detail. Our notation for the Transformer model is based on
Yun et al. (2020), although there are countless variations in the literature
that we do not discuss further. These can be adapted into our categorical
framework fairly straightforwardly based on the approach outlined below.
Transformer models are inherently compositional, which makes them particularly
convenient to model using category theory.

######  Definition 31.

Yun et al. (2020); Vaswani et al. (2017) A Transformer block is a sequence-to-
sequence function mapping $\mathbb{R}^{d\times
n}\rightarrow\mathbb{R}^{d\times n}$. There are generally two layers: a self-
attention layer Vaswani et al. (2017) and a token-wise feedforward layer. We
assume tokens are embedded in a space of dimension $d$. Specifically, we model
the inputs $X\in\mathbb{R}^{d\times n}$ to a Transformer block as $n$-length
sequences of tokens in $d$ dimensions, where each block computes the following
function defined as $t^{h,m,r}:\mathbb{R}^{d\times n}:\mathbb{R}^{d\times n}$:

$\displaystyle\mbox{Attn}(X)$ $\displaystyle=$ $\displaystyle
X+\sum_{i=1}^{h}W^{i}_{O}W^{i}_{V}X\cdot\sigma[W^{i}_{K}X)^{T}W^{i}_{Q}X]$
$\displaystyle\mbox{FF}(X)$ $\displaystyle=$
$\displaystyle\mbox{Attn}(X)+W_{2}\cdot\mbox{ReLU}(W_{1}\cdot\mbox{Attn}(X)+b_{1}{\bf
1}^{T}_{n},$

where $W^{i}_{O}\in\mathbb{R}^{d\times n}$,
$W^{i}_{K},W^{i}_{Q},W^{i}_{Q}\in\mathbb{R}^{d\times n}$,
$W_{2}\in\mathbb{R}^{d\times r}$, $W_{1}\in\mathbb{R}^{r\times d}$, and
$b_{1}\in\mathbb{R}^{r}$. The output of a Transformer block is $FF(X)$.
Following convention, the number of “heads" is $h$, and each “head" size $m$
are the principal parameters of the attention layer, and the size of the
“hidden" feed-forward layer is $r$.

Transformer models take as input objects $X\in\mathbb{R}^{d\times n}$
representing $n$-length sequences of tokens in $d$ dimensions, and act as
morphisms that represent permutation equivariant functions
$f:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{d\times n}$ such that
$f(XP)=f(X)P$ for any permutation matrix. Yun et al. (2020) show that the
actual function computed by the Transformer model defined above is a
permutation equivariant mapping.

Categories are compositional structures, which can be built out of smaller
objects. Concretely, we define a category of transformers ${\cal C}_{T}$ where
the objects are vectors $x\in\mathbb{R}^{d\times n}$ representing sequences of
$d$-dimensional tokens of length $n$, and the composable arrows are
permutation-invariant functions ${\cal T}^{h,m,r}$ comprised of a composition
of transformer blocks $t^{h,m,r}$ of $h$ heads of size $m$ each, and a
feedforward layer of $r$ hidden nodes. Objects in a category interact with
each other through arrows or morphisms. In the category ${\cal C}_{T}$ of
Transformer models, the morphisms are the equivariant maps $f$ by which one
Transformer model block can be composed with another.

######  Definition 32.

The category ${\cal C}_{T}$ of Transformer models is defined as follows:

  * •

The objects Obj(C) are defined as vectors $X\in\mathbb{R}^{d\times n}$
denoting $n$-length sequences of tokens of dimension $d$.

  * •

The arrows or morphisms of the category ${\cal C}_{T}$ are defined as a family
of sequence-to-sequence functions and defined as:

$T^{h,m,r}\coloneqq\\{f:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{d\times
n}\ |\ \mbox{where}\ f(XP)=XP,\ \mbox{for some permutation matrix}\ P\\}$

###  5.3 Constructing Simplicial Transformers from Transformer Categories

We now show how we can define a novel hierarchical theory of simplicial
Transformers, first by embedding the category of Transformers into a
simplicial set by computing the nerve of a functor that maps ${\cal C}_{T}$
into the simplicial set $S^{T}_{\bullet}$. The nerve of a category ${\cal C}$
enables embedding ${\cal C}$ into the category of simplicial objects, which is
a fully faithful embedding Lurie (2009); Richter (2020).

######  Definition 33.

Let ${\cal F}:{\cal C}\rightarrow{\cal D}$ be a functor from category ${\cal
C}$ to category ${\cal D}$. If for all arrows $f$ the mapping $f\rightarrow
Ff$

  * •

injective, then the functor ${\cal F}$ is defined to be faithful.

  * •

surjective, then the functor ${\cal F}$ is defined to be full.

  * •

bijective, then the functor ${\cal F}$ is defined to be fully faithful.

######  Definition 34.

The nerve of a category ${\cal C}$ is the set of composable morphisms of
length $n$, for $n\geqslant 1$. Let $N_{n}({\cal C})$ denote the set of
sequences of composable morphisms of length $n$.

$\\{C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}\
|\ C_{i}\ \mbox{is an object in}\ {\cal C},f_{i}\ \mbox{is a morphism in}\
{\cal C}\\}$

The set of $n$-tuples of composable arrows in C, denoted by $N_{n}({\cal C})$,
can be viewed as a functor from the simplicial object $[n]$ to ${\cal C}$.
Note that any nondecreasing map $\alpha:[m]\rightarrow[n]$ determines a map of
sets $N_{m}({\cal C})\rightarrow N_{n}({\cal C})$. The nerve of a category C
is the simplicial set $N_{\bullet}:\Delta\rightarrow N_{n}({\cal C})$, which
maps the ordinal number object $[n]$ to the set $N_{n}({\cal C})$.

The importance of the nerve of a category comes from a key result Lurie
(2022); Richter (2020), showing it defines a full and faithful embedding of a
category:

######  Theorem 3.

The nerve functor $N_{\bullet}:$ Cat $\rightarrow$ Set is fully faithful. More
specifically, there is a bijection $\theta$ defined as:

$\theta:{\bf Cat}({\cal C},{\cal C^{\prime}})\rightarrow{\bf
Set}_{\Delta}(N_{\bullet}({\cal C}),N_{\bullet}({\cal C^{\prime}})$

Unfortunately, the left adjoint to the nerve functor is not a full and
faithful encoding of a simplicial set back into a suitable category. Note that
a functor $G$ from a simplicial object $X$ to a category ${\cal C}$ can be
lossy. For example, we can define the objects of ${\cal C}$ to be the elements
of $X_{0}$, and the morphisms of ${\cal C}$ as the elements $f\in X_{1}$,
where $f:a\rightarrow b$, and $d_{0}f=a$, and $d_{1}f=b$, and $s_{0}a,a\in X$
as defining the identity morphisms ${\bf 1}_{a}$. Composition in this case can
be defined as the free algebra defined over elements of $X_{1}$, subject to
the constraints given by elements of $X_{2}$. For example, if $x\in X_{2}$, we
can impose the requirement that $d_{1}x=d_{0}x\circ d_{2}x$. Such a definition
of the left adjoint would be quite lossy because it only preserves the
structure of the simplicial object $X$ up to the $2$-simplices. The right
adjoint from a category to its associated simplicial object, in contrast,
constructs a full and faithful embedding of a category into a simplicial set.
In particular, the nerve of a category is such a right adjoint.

##  6 Layer 3 of GAIA: Universal Properties and the Category of Elements

A central and unifying principle in GAIA is that every pair of categorical
layers is synchronized by a functor, along with a universal arrow. In this
section, we introduce some additional ideas from category theory, including
the fundamental Yoneda Lemma MacLane (1971) that states that all objects in a
(generative AI) category can be defined in terms of their interactions. To
understand the significance of this powerful lemma, keep in mind that it
applies to any (small) category. In particular, we defined in Section 5 the
category of Transformer models as equivariant functions over Euclidean spaces.
What the Yoneda Lemma implies here is that any Transformer model building
block can be defined (upto isomorphism) purely in terms of the interactions it
makes with other Transformer building blocks. This somewhat strange
parameterization provides deep insight into how objects in categories behave.
In a concrete sense, Transformer models are based on defining words by their
context in sentences, and an enriched form of the Yoneda Lemma can be directly
applied to model the statistical representations of words learned by
Transformers Bradley et al. (2022).

The bottom layer of GAIA is a (Grothendieck) category of elements Riehl (2017)
that essentially “grounds" out the universal coalgebras at layer 2 of GAIA in