In $1950$, Alan Turing proposed a framework called an imitation game in which the participants are to be classified Human or Machine solely from  natural language interactions. Using mathematics largely developed since Turing – category theory – we investigate a broader class of universal imitation games (UIGs). Choosing a category means defining a collection of objects and a collection of composable arrows between each pair of objects that represent “measurement probes"  for solving UIGs. The theoretical foundation of our paper rests on two celebrated results by Yoneda.  The first, called the Yoneda Lemma, discovered in 1954 – the year of Turing's death – shows that objects in categories can be identified up to isomorphism solely with measurement probes defined by composable arrows. Yoneda embeddings are universal representers of objects in categories. A simple yet general solution to the static UIG problem, where the participants are not changing during the interactions,  is to determine if the Yoneda embeddings are (weakly) isomorphic. A universal property in category theory is defined by an initial or final object. A second foundational result of Yoneda from 1960 defines initial objects called coends and final objects called ends, which yields a categorical “integral calculus" that unifies probabilistic generative models, distance-based kernel, metric and optimal transport models, as well as topological manifold representations. When participants adapt during interactions, we study two special cases: in dynamic UIGs, “learners" imitate “teachers".  We contrast the initial object  framework of passive learning from observation over well-founded sets using inductive inference – extensively studied by Gold, Solomonoff, Valiant, and Vapnik – with the final object framework of coinductive inference over non-well-founded sets and universal coalgebras, which formalizes  learning from active experimentation using causal inference or reinforcement learning. We define a category-theoretic notion of minimum description length or Occam's razor based on final objects in coalgebras.   Finally, we explore evolutionary UIGs, where a society of participants is playing a large-scale imitation game. Participants in evolutionary UIGs can go extinct from “birth-death" evolutionary processes that model how novel technologies or “mutants" disrupt previously stable equilibria.  Given the rapidly rising energy costs of playing imitation games on classical computers, it seems  likely that tomorrow's imitation games may have to played on non-classical computers. We end with a brief discussion of how our categorical framework extends to imitation games on quantum computers.

“I propose to consider the question, `Can machines think'?" – Alan Turing, Mind, Volume LIX, Issue 236, October 1950, Pages 433–460.

§ OVERVIEW OF THE PAPER

Alan Turing proposed imitation games as a way to pose the problem of whether machines could think.

§.§ Turing's imitation game

The field of artificial intelligence (AI) has existed for about 7 decades, if we define its origin as beginning with Turing's famous paper [Turing, 1950].  To answer the question “Can machines think?", Turing suggested it was necessary first to define the words “machine" and “think". He proposed an imitation game, as shown in Figure <ref>, as a concrete way to frame the problem.  Quoting from Turing's paper:

The new form of the problem can be described in terms of a game which we call the ‘imitation game’.

It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart from the other two.

The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either ‘X is A and Y is B’ or ‘X is B and Y is A’.

Turing proposes replacing one of the human participants with a machine, thereby framing the original question of whether machines can think by the more concrete version of being able to tell from interactions whether one is conversing with a human or a machine:

We now ask the question, ‘What will happen when a machine takes the part of A in this game?’ Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, ‘Can machines think?’

The imitation game, or what is now more popularly called the Turing Test, has become the mainstay of the field of AI for the ensuing seven decades since Turing wrote his original paper, prompting an immense amount of attention that would be impossible to survey within this paper. The study of imitation games is no longer an academic pursuit: the recent success of generative AI  is already being felt in terms of its economic  impact around the world. Millions of humans are now playing imitation games with generative AI systems, and there is an alarming increase in the use of “deepfakes" for nefarious purposes.  In response, a growing number of software tools are being released that attempt to solve limited classes of imitation games, such as gptzero. [gptzero can be accessed at https://gptzero.me.] We seek to develop a framework for UIGs that applies both to the current generation of generative AI systems being developed on classical computers that are “Turing's machine" models, as well as the next generation of quantum computers that build on more exotic forms of interaction in braided categories [Coecke and Kissinger, 2017].

Two recent articles are noteworthy. The first article by Bernardo Goncalves [Gonçalves, 2024] presents a fascinating historical reconstruction of Turing's test from archival sources. The second article by Terry Sejnowski [Sejnowski, 2023] proposes an interesting alternative called a “Reverse Turing Test" based on the recent successes in building large language models (LLMs), which has resulted in possibly the largest ever “natural" experiment conducted on imitation games with literally millions of humans conversing with chatbots like Open AI's chatGPT. The literature on applications of LLMs is already beyond comprehension, and a review would be impossible here. [Adesso, 2023] explores how LLMs can shape scientific discovery in the coming decades. [Jacques, 2023] examines how the teaching of basic computer science will have to be revised in light of the new capabilities of LLMs.

§.§ Universal Imitation Games

In Turing's imitation game, the identity of a participant is determined by a series of questions and answers (the specific questions above are from Turing's original paper [Turing, 1950].  We model interactions as ${\cal C}(-, x): {\cal C}^{op} \rightarrow {\cal D}$ and ${\cal C}(x, -): {\cal C} \rightarrow {\cal D}$ as contravariant and covariant functors, respectively,  from a category ${\cal C}$ into another category ${\cal D}$ (such as Sets or any other enriched category). Two key results by Yoneda provide the theoretical foundation for our paper. The Yoneda Lemma shows objects can be defined purely in terms of these contravariant and covariant functors. In addition, Yoneda investigated bivalent functors $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$ that combine both contravariant and covariant actions, and proposed a categorical “integral calculus" over coends and ends, which reveal deep similarities between generative probabilistic models, distance-based models, kernel methods, optimal transport and topological representations.

Based largely on mathematics developed since Turing – in particular, category theory [MacLane, 1971] – we investigate a broader class of universal imitation games (UIGs) that captures many other forms of interactions. Category theory is exceptionally well-suited to the study of imitation games as it constitutes a “universal" language  for defining interactions: choosing a category means defining a collection of objects and a collection of composable arrows between each pair of objects that represent “measurement probes"  for solving UIGs.
Figure <ref> illustrates our approach to modeling (universal) imitation games, where interactions define contravariant functors ${\cal C}(-,x)$ or covariant functors ${\cal C}(x, -)$, and the solution to an imitation game corresponds to (weak) isomorphism in a category ${\cal C}$. The Python package DisCoPy [de Felice et al., 2021] is a software implementation for computing with string diagrams in category theory, and could be used to implement some of the ideas in this paper. [Categories for language are described in https://docs.discopy.org/en/main/notebooks/21-05-03-tallcat.html.] [Toumi, 2022] has a detailed description of natural language processing on quantum computers.  We will discuss UIGs over quantum computers at the end of the paper in Section <ref>.

The theoretical foundation of our paper rests on two fundamental insights developed by Yoneda (see Figure <ref>).   The celebrated Yoneda Lemma [MacLane, 1971] asserts that objects in a category ${\cal C}$ can be defined purely in terms of their interactions with other objects. This interaction is modeled by contravariant or covariant functors:

\[ {\cal C}(-, x): {\cal C}^{op} \rightarrow {\bf Sets},  \ \ \  {\cal C}(x, -): {\cal C} \rightarrow {\bf Sets} \]

The Yoneda embedding $x \rightarrow {\cal C}(-, x)$ is sometimes denoted as $\yo(x)$ for the Japanese Hiragana symbol for yo, serves as a universal representer, and generalizes many other similar ideas in machine learning, such as representers $K(-, x)$ in kernel methods [Schölkopf and Smola, 2002] and representers of causal information [Mahadevan, 2023]. There are many variants of the Yoneda Lemma, including versions that map the functors ${\cal C}(-, x)$ and ${\cal C}(x, -)$ into an enriched category. In particular, [Bradley et al., 2022] contains an extended discussion of the use of an enriched Yoneda Lemma to model natural language interactions that result from using a large language model.

The second major insight from Yoneda [Yoneda, 1960] is based on a powerful concept of the coend and end of a bifunctor $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$ that combines both a contravariant and a covariant action.  It can be shown that many approaches to solving imitation games, such as building a probabilistic generative model of participants, or using distances in some metric space, correspond to initial or terminal objects in a category of wedges, defined by objects that represent bifunctors, and the arrows are dinatural transformations. These initial or terminal objects correspond to coends and ends. For example, dimensionality reduction methods such as UMAP [McInnes et al., 2018] are based mapping a dataset (say of interactions with a participant) into a topological space, which can be shown to define a coend object. Dually, building a probabilistic generative model of a participant essentially defines an end object, as probabilities can be shown to be codensity monads [Avery, 2016] that are in fact defined by ends. In summary, coends represent geometric ways to solve UIGs, whereas ends represent probabilistic approaches. Bifunctors $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D} $ can be used to construct universal representers of distance functions in generalized metric spaces leading to a “metric Yoneda Lemma" [Bonsangue et al., 1998].

The theoretical foundation of our approach to universal imitation games is based on two celebrated results of Yoneda. The first (top row) shows that Yoneda embeddings $\yo(x) = C(-, x)$ are universal representers of objects in a category. The second (middle row) is based on Yoneda's categorical “integral calculus" using coends and ends that unify diverse approaches to solving imitation games studied in AI over the past six decades. The bottom row shows that universal properties defined by initial and final objects provide a unified way to characterize approaches to dynamic UIGs using passive learning (inductive inference) as well as active learning (causal inference and reinforcement learning).

A classification of universal imitation games based on the characteristics of the participants and the framework employed to discriminate among them.

Figure <ref> depicts a classification of universal imitation games (UIGs) that will be the primary focus of our paper. In Turing's original model, discussed above, the participants were assumed to be static, that is, they were not adapting during the course of the interactions. In the case that participants are static, we can try to distinguish between them using a large variety of methods, ranging from distance-based methods like kernel methods [Schölkopf and Smola, 2002] or  optimal transport [Villani, 2003], or density-based  methods such as constructing a generative model. The fundamental ideas developed by Yoneda, in particular Yoneda embeddings $\yo(x) = {\cal C}(-, x)$ and (co)ends play a major role in our paper. For example, [Avery, 2016] showed that the set of probability distributions on a set can be defined as a codensity monad, which is mathematically equivalent to an end of a bifunctor defined over a functor $G: {\cal B} \hookrightarrow \mbox{Meas}$, where ${\cal B}$ is a category  consisting of all convergent sequences $[0,1]$ with affine maps, and $\mbox{Meas}$ is the category of all measurable spaces. Probabilities are essentially final objects, and in contrast, topological embeddings of the type produced by dimensionality reduction methods like UMAP [McInnes et al., 2018] correspond to coends. Another theme of our paper is that we model generative models categorically as universal coalgebras [Jacobs, 2016, Rutten, 2000, Sokolova, 2011].

When participants adapt during interactions, we study two special cases: in dynamic UIGs, “learners" imitate “teachers".  We contrast the initial object  framework of passive learning from observation over well-founded sets using inductive inference – extensively studied by Gold, Solomonoff, Valiant, and Vapnik – with the final object framework of coinductive inference over non-well-founded sets and universal coalgebras, which formalizes  learning from active experimentation using causal inference or reinforcement learning. We define a category-theoretic notion of minimum description length or Occam's razor based on final objects in coalgebras.

In the study of dynamic UIGs, we contrast the approach of inductive inference, which we associate with initial algebras over well-founded sets, with the framework of coinductive inference, which relates to final coalgebras over non-well-founded sets. Algebras can be defined as mappings $F(X) \rightarrow X$, for some functor $F$ on a category ${\cal C}$ (e.g., of Sets), where $X$ is some object in ${\cal C}$, whereas coalgebras go in the opposite direction $X \rightarrow F(X)$.

Figure <ref> illustrates our study of dynamic UIGs, where “learner" participants are trying to imitate the behavior of “teacher" participants. We contrast two approaches, representing initial and final objects in a category of coalgebras. Induction corresponds to initial algebras over a category defined by the ${\cal P}$ powerset functor over sets. In contrast, coinduction corresponds to final coalgebras. Formally,  inductive inference studied by Gold [Gold, 1967], Solomonoff [Solomonoff, 1964], Valiant [Valiant, 1984], and Vapnik [Vapnik, 1999] corresponds to mathematical induction defined by initial objects over algebras.  We contrast inductive inference with coinductive inference in universal coalgebras [Aczel, 1988, Rutten, 2000], which formally corresponds to final objects. Reinforcement learning algorithms, such as TD-learning [Sutton and Barto, 1998], are typically analyzed as stochastic approximation methods [Robbins and Monro, 1951, Borkar, 2008]. In our paper, we model RL in terms of the metric coinduction framework [Kozen and Ruozzi, 2009] over a coalgebra. The Markov decision process (MDP) model, and its innumerable variants, are all easily modeled as probabilistic coalgebras [Sokolova, 2011], and the process of TD-learning is essentially a stochastic coinduction inference step towards determining the final coalgebra. This perspective differs considerably from the standard stochastic approximation perspective used to analyze RL algorithms thus far [Bertsekas, 2022, Bertsekas, 2019]. The fundamental idea underlying dynamic programming (DP) and reinforcement learning (RL) methds is the Bellman optimality principle, which essentially states that the restriction of any shortest path to a segment must again produce a shortest path, otherwise we can produce a shorter overall path by switching to a shorter segment. This principle is just a special case of the general principle of sheaves, which we discuss in Section <ref>. To the best of our knowledge, the relationship between the Bellman optimality equation and the theory of sheaves [MacLane and leke Moerdijk, 1994] has not been made before, and represents one of many such examples of the deep insights that come from  category-theoretic perspective. Also, by understanding that RL is essentially based on the discovery of final coalgebras in a category of coalgebras, it is possible to explore the vast repertoire of probabilistic coalgebras that have been studied by [Sokolova, 2011] and others, which may yield many new RL approaches.

Finally, we explore evolutionary UIGs, where a society of participants is playing a large-scale imitation game. Participants in evolutionary UIGs can go extinct from “birth-death" evolutionary processes that model how novel technologies or “mutants" disrupt previously stable equilibria.  In the case when the participants are evolving, we introduce the framework of game theory as developed by von Neumann and Morgenstern [von Neumann and Morgenstern, 1947] and Nash [Nash, 1951], combined with the use ideas from Darwin's model of evolution by natural selection. We propose category-theoretic formulations of evolutionary game theory [Lieberman et al., 2005].

Figure <ref> illustrates a sample of interactions between an evaluator and a participant, with the questions and replies taken from Turing's original paper [Turing, 1950]. The essence of our paper is to model such interactions by morphisms into and out of an object in a category [MacLane, 1971]. A number of previous studies have explored how natural language can be modeled in terms of objects and morphisms of a category [Asudeh and Giorgolo, 2020, Bradley et al., 2021, Coecke, 2020]. At the outset, it is important to clarify that we are proposing a significantly broader vision of imitation games, which we refer to as universal imitation games. More specifically, we are not constraining ourselves to interactions that are purely focused on text, but we include other forms of interaction, including causal experimentation [Imbens and Rubin, 2015, Pearl, 2009], use of machine learning methods more broadly, including distance-based kernel methods [Schölkopf and Smola, 2002], statistical methods [Tibshirani et al., 2010], information theoretic methods [Cover and Thomas, 2006], inductive inference [Gold, 1967, Solomonoff, 1964], and universal coalgebraic methods that rely on coinduction [Jacobs, 2016, Rutten, 2000]. In short, the aim of our framework is to explore the full gamut of approaches available to determine the identity of abstract objects in a category, with a primary goal being its application in AI. To clarify this point further, we view the problem of deciding if a particular image was created by a human or a diffusion based generative AI system [Song and Ermon, 2019]  as an example of an imitation game,  or deciding if a particular computer program was written by a human or an AI copilot.

One significant strength of category theory is that it can reveal surprising similarities between algebraic structures that superficially look very different, such as metric spaces and partially ordered sets (see Table <ref>). 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.

UIGs can be “played" in many different categories.
C      Hom$_{\cal C}$ 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      $\geq$      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

We view imitation games as fundamental to much of the research in AI in many areas. For example, an autonomous car that is traversing the streets of a busy city like San Francisco is engaged in playing an imitation game at many levels. It has to decide the identity of unknown objects that appear in its perceptual field: is the perceived object a pedestrian or another car?  It has to determine its current “state", which could be a complex function of its past observations. Many approaches to modeling state have been studied in the literature, including diversity based representations in automata based on tests [Rivest and Schapire, 1994], extensions of diversity automata to stochastic sequential models such as partially observable Markov decision processes [Singh et al., 2004], coalgebraic notions of state [Jacobs, 2016], as well as causal experimentation methods [Imbens and Rubin, 2015]. One can view the problem of “black box identification" as containing within it much of the complexity of AI. For example, conversational models involve determining what someone else knows or is thinking about, which involves formal models of knowledge such as modal logic [Halpern, 2016].

We build on the extensive literature on object isomorphisms in category theory, the bulk of which was developed after Turing's death in 1954, to formulate universal properties of imitation games, building on the rich mathematical literature on category theory [MacLane, 1971, Riehl, 2017, Richter, 2020, Lurie, 2009]. As we do not assume the prospective reader to have a background in category theory, we have sought to provide a condensed but detailed overview of those parts of category theory that are relevant to formulating UIGs. 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.

We expand on Turing's concept and analyze a broader class of  universal imitation games (UIGs) using mathematics – principally category theory [MacLane, 1971, Riehl, 2017, Richter, 2020, Lurie, 2009] – that was largely developed after Turing. Category theory gives an exceptional set of  “measuring tools" for imitation games. 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 for solving imitation games, 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.

We classify UIGs into three types: static UIGs, which is closest to Turing's original formulation, but based  on (weak) isomorphism and homotopy; dynamic UIGs, where one participant – the “learner" – is seeking to “imitate" the other participant – a “teacher" – where we contrast the initial object framework of theoretical machine learning defined by  inductive inference first studied by Gold and Solomonoff in the 1960s with the dynamical systems final object framework of coinductive inference developed by Aczel and Rutten since the 1980s; and finally evolutionary UIGs, which models a network economy of participants and we analyze the possibility that a new “mutant" can cause the entire economy to imitate it by being better fit. Evolutionary imitation games model both the spread of diseases through a population or the spread of new ideas or technologies that promise investors a better return. We give a category-theoretic model of evolutionary game theory, combining Darwin's model of evolution by natural selection with the framework of games and economic behavior pioneered by von Neumann, Morgenstern, and Nash.

Abstractly, the problem of solving imitation games can be viewed as comparing two potentially infinitely long strings of tokens that represent the communication from and to the participants. At a high level, our approach builds on the notion of object isomorphism in category theory. We formulate the question of imitation games as deciding if two objects are isomorphic:

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 = $ id$_X$, and $f$ is right invertible using a morphism $h$ where $f \circ h = $ id$_Y$.

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 Vect$_k$ 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.

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

Let ${\cal C}$ be a category. We say a morphism $f: C \rightarrow D$ is a retract of another morphism $f': C \rightarrow D$ if it is a retract of $f'$ 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'$ of ${\cal C}$, if $f$ is a retract of $f'$, and $f'$  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. Thus, in the framework of universal imitation games, as we will show in detail later, there are many choices of categories and each one provides some set of measurement tools. Application areas, like natural language processing or computer vision or robotics, may dictate which set of measurement tools is most appropriate. It is, however, possible to state results that hold regardless of what  measurement tools are used (such as the Yoneda Lemma), and we will review the most important of these results for imitation games.

To motivate why homotopy might be useful, a number of recent generative AI systems based on neural or state-space sequence models [Gu et al., 2023, Vaswani et al., 2017] enable the summarization of long documents, which can be viewed as compression of a sequence of tokens. In what sense can we determine if the compressed sequence and the original sequence denote the same object? Homotopy provides an answer.

A richer model of interaction is provided by simplicial sets [May, 1992], which is a graded set $S_n, \ n \geq 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]:

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}$.

These definitions illustrate how category theory can be useful in defining general ways to formulate the problem of imitation games. We now illustrate how category theory is useful in defining generative models that capture much of the work in generative AI, including sequence models.

We expand significantly on Turing's model of imitation games, which limited itself to static games, to include dynamic imitation games where one participant is a “teacher" and the other is a “learner", as well as evolutionary imitation games, where there is an entire economy of participants that are competing to maximize individual fitness values.

Our core theoretical framework is based defining participants in a UIG as functors that act on categories,  collections of objects that interact through arrows or morphisms. To solve Turing's imitation game, we need to decide if the infinite stream of tokens (e.g., words in a natural language) from two participants in an imitation game (possibly one or both being humans or machines) are “indistinguishable" from each other. Category theory asks whether two objects are isomorphic, not whether they are equal. Accordingly, our formulation of UIGs is based on determining whether two UIG objects are isomorphic, not whether they are equal as Turing originally phrased it. In addition, we can bring to bear the notion of homotopy in category theory [Richter, 2020, Quillen, 1967] and ask if the two participants in a static UIG are homotopic.

Static UIGs: Given a potentially infinite stream of (multimedia) tokens from and to two participants in an imitation game (see Figure <ref>),  modeled abstractly as objects $A$ and $B$ in some category ${\cal C}$,  are these two objects (weakly) isomorphic?

In the second type of UIG that we study, it is known that the two participants are in fact different initially from each other. The goal of dynamic UIGs is to determine if asymptotically, the two participants are indistinguishable. This second model captures the process by which generative AI systems are being developed today to pass imitation games, using large language models (LLMs) [Vaswani et al., 2017] or through building generative models by diffusion [Song and Ermon, 2019]. An LLM at the beginning outputs random tokens, but over a long process of training on potentially trillions of tokens from datasets like Common Crawl, they appear capable in principle of passing a Turing test.

Dynamic UIGs: This formulation differs from  Turing's original conception, in that the two participants are known to be different initially, but the question is to determine if asymptotically, the two participants become indistinguishable. That is, given a potentially infinite stream of tokens from the two participants in a dynamic UIG, modeled again as objects $A$ and $B$ in some category ${\cal C}$, do these objects become isomorphic in the limit? We can intuitively think of participant $A$ as a “teacher" and participant $B$ as the “learner" in a dynamic UIG.

Our formulation of dynamic UIGs relates closely to the original theoretical model of inductive inference or language identification in the limit studied by Gold [Gold, 1967] and Solomonoff [Solomonoff, 1964], and subsequently refined by many others, incuding Valiant [Valiant, 1984] and Vapnik [Vapnik, 1999]. We use the mathematics of non-well-founded sets [Aczel, 1988] and universal coalgebras [Jacobs, 2016, Rutten, 2000] to define a relation called bisimulation to address this problem. We then illustrate how our formulation of dynamic UIGs gives rise to a new framework called coinductive inference for machine learning (ML), and contrast it to the 60-year-old framework of inductive inference proposed by Gold and Solomonoff.

Finally, we explore a third formulation of UIGs termed evolutionary UIGs, combining the principle of evolution by natural selection pioneered by Darwin with the framework of games and economic behavior pioneered by von Neumann and Morgenstern, Nash, and subsequently developed by many others over the past 70 years [Maschler et al., 2013]. Fundamentally, humans and all other biological organisms on Earth evolved by natural selection, and as the recent Covid-19 pandemic has illustrated, the evolutionary game is one that is indeed a game of the survival of the fittest.

Evolutionary UIGs: The third formulation differs from the previous two, in that there is a network economy of participants, each of which has a certain fitness to an environment, and the goal is to understand if a particular mutant can cause the entire economy to “imitate" it.  Evolutionary UIGs model the spread of diseases through societies, or the spread of new ideas and technologies that promise investors a better return.  The problem of evolutionary UIGs is to determine if the economy find an equilibrium point.

Evolutionary UIGs integrates  the framework of evolutionary dynamics [Lieberman et al., 2005], and non-cooperative games pioneered by Nash [Nash, 1951]. In particular, we focus on identifying fundamental differences between adaptation by incremental processing of experience, as in dynamic UIGs, with the process of random mutation by natural selection, where global changes occur to disrupt an equilibrium. We investigate several models of UIGs, from Valiant's evolvability [Valiant, 2009], to birth-death stochastic processes [Novak, 2006]. We give a detailed introduction to variational inequalities (VIs) [Facchinei and Pang, 2003], which generalize game theory and optimization and illustrate it with an example of playing a generative AI network economy game. We describe a metric coinduction stochastic approximation method for solving VIs [Alfredo N. Iusem, 2018, Wang and Bertsekas, 2015], and outline how to extend such methods to evolutionary UIGs.

The length of this paper is largely due to its tutorial nature, beginning in the next section with a detailed overview of category theory for the reader who may be new to this topic. In Section <ref>, besides giving a detailed introduction to category theory, we also define several examples of static UIGs. We turn to describe dynamic UIGs in Section <ref>. Finally, in Section <ref>, we define evolutionary UIGs.

§ STATIC UNIVERSAL IMITATION GAMES: AN INTRODUCTION TO CATEGORIES AND FUNCTORS

In this  section, we introduce category theory more formally, and illustrate how it is useful in modeling universal imitation games (UIGs). As noted above, UIGs fundamentally involve determining answering the question Human or Machine?, in the original model that Turing proposed [Turing, 1950]. We propose to generalize this notion in the remainder of this paper, fundamentally starting with our use of category theory, a field of mathematics that has largely developed since Turing. We turn the question posed by Turing into a question of deciding if two objects in a category are (weakly) isomorphic. Thus, in reading this somewhat long section summarizing a lot of work in category theory over the past seven decades, it is useful to keep in mind that at the heart of what we are trying to do is to decide if two participants in a UIG are in some abstract sense “similar" using the various tools provided by category theory. Different categories allow us to “play" the imitation game in various ways, and this chapter is intended to whet the reader's appetite for the enormous variety of possible ways in which this question can be posed.

Categories are comprised of objects, which can be arbitrarily complex, which gives it an unmatched power of abstraction in virtually all of mathematics [MacLane, 1971, Riehl, 2017, Richter, 2020].  Categories are compositional structures, and can be built out of smaller category-like objects. Objects in a category interact with each other through arrows or morphisms. One of the most remarkable results in category theory – the Yoneda Lemma – shows that objects in a category can be defined by their interactions. This result forms the underlying motif throughout the rest of this paper, as it relates closely to the problem posed by UIGs. Another central principle in category theory is the notion of a universal property: a property is defined to be universal if it represents an initial or final object in a category. There is a unique arrow from the initial object in a category to every other object. Analogously, there is a unique morphism from every object in the category into the final object. These two special cases illustrate the theme of the Yoneda Lemma of characterizing every object from its interactions. We introduce universal constructions through colimits and limits, pullbacks, equalizers and co-equalizers, which give a rich and flexible way of integrating over objects to find common properties. Functors map one category to another, mapping not just objects, but also the morphisms in a category. Many of the generative models we define in this paper will correspond to functors over some category.

Category theory [MacLane, 1971, Riehl, 2017, MacLane and leke Moerdijk, 1994] differs substantially from earlier formulations of AI in terms of causal inference, logic, probability theory, neural networks, statistics, or optimization, all of which essentially can be shown to define special types of categories (e.g., causal models are endofunctors in the category of preorders, probabilities are defined as endofunctors over the category of measurable spaces, optimization methods represent endofunctors over the category of vector spaces, etc). As we will see in the remainder of the paper, many of the theoretical models used in AI can be described in the language of category theory, which provides an unmatched power of abstraction in all of mathematics. It is also singularly suited to modeling computation, and has been extensively explored in other areas of computer science [Jacobs, 2016].

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. An underlying motif that runs through this entire paper is to view AI and ML systems as functors acting on categories.

§.§ Categories and Functors

Table <ref> gives a few examples from a myriad of ways in which categories can be defined for formulating UIGs, including approaches based on information theory [Baez et al., 2011], statistical methods based on a decomposable probability distribution [Pearl, 2009], causal methods based on experimentation to test a difference between the participants [Pearl, 2009, Imbens and Rubin, 2015], reinforcement learning methods that are based on modeling the participants as a stochastic dynamical system [Sutton and Barto, 1998],  formal models of knowledge [Fagin et al., 1995], universal coalgebraic methods of modeling dynamical systems [Jacobs, 2016, Rutten, 2000], and last but not least, generative AI models based on large language models (LLMs) [Vaswani et al., 2017] and diffusion models [Song and Ermon, 2019].

Category        Characterization     UIG Application
Topological spaces       Continuous functions     Analyze document summarization
Measurable spaces          Probability monads      Statistical model of participants
Coalgebras         $X \rightarrow F(X)$, $F$ is a functor over sets      Generative AI models
Simplicial sets     $[n] = (0, 1, \ldots, n)$ as objects     Evolutionary UIGs
Wedges     Dinatural transformations between $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$     Generalized metric spaces
Coends     $\int^D {\cal C}(D, D)$ models topological embeddings     Manifold representations
Ends     $\int_D {\cal C}(D, D)$ models integration over measures     Categorical probability
Categories can be defined in a myriad of ways for formulating UIGs. We illustrate a few possibilities here.

Category theory is based fundamentally on defining universal properties [Riehl, 2017], which can be defined as the initial or final object in some category. To take a simple example, the Cartesian product of two sets can be defined as the set of ordered pairs, which tells us what it is, but not what it is good for, or why it is special in some way. Alternatively, we can define the Cartesian product of two sets as an object in the category Sets that has the unique property that every function onto those sets must decompose uniquely as a composition of a function into the Cartesian product object, and then a projection component onto each component set. Furthermore, among all such objects that share this property, the Cartesian product is the final object. In sum, we seek such universal properties that define solutions to imitation games.

We propose a categorical calculus for formulating universal imitation games (UIGs),  building on a $70$-year rich legacy of research in AI, mathematics, and computer science. Principally, our framework builds on ideas in category theory that were principally developed since Turing tragically died in 1954 [MacLane, 1971, MacLane and leke Moerdijk, 1994, Riehl, 2017, Richter, 2020]. That very year, Saunders Maclane, a distinguished American mathematician, met with a young Japanese mathematician, Nobuo Yoneda, in the Gare du Nord train station in Paris. That possibly chance encounter led to the development of a profound series of mathematical ideas that revolve around a central core question: can objects can be identified by their interactions with other objects?. The relevance of this question to UIGs is clear, if we abstractly model the participants in a UIG as objects in some category. In a nutshell, our categorical calculus for UIGs posits that two participants in a UIG are indistinguishable if they are isomorphic. One cardinal principle of category theory is to never ask if two objects are equal, only if they are equivalent under a pair of invertible mappings. This categorical perspective succinctly summarizes our formulation of UIGs.

Maclane published a classic textbook on category theory [MacLane, 1971], where he introduced the mathematical world to the Yoneda Lemma.  Our categorical calculus for UIGs builds on the Yoneda Lemma, as well as many ideas that have been developed since, both in category theory [Loregian, 2021, Richter, 2020, Lurie, 2009], as well as in theoretical computer science on universal coalgebras [Jacobs, 2016, Rutten, 2000], and the axiomatic foundations of non-well-founded sets [Aczel, 1988]. In 1958, Daniel Kan introduced the concept of adjoint functors, denoted $F \vdash G$, where the functors $F$ and $G$ map between two categories ${\cal C}$ and ${\cal D}$ in opposite directions [Kan, 1958]. The fundamental principle here was to note that the collection of interactions between two objects $A$ and $B$ in a category ${\cal C}$, denoted variously as ${\bf Hom}_{{\cal C}}(A, B)$, or more simply as ${\cal C}(A, B)$ was contravariant in the first argument, but covariant in the second argument. It appeared to differ from a tensor product $\otimes$ functor that produced a new object $A \otimes B$, and was covariant in both arguments. As it turned out, both the ${\bf Hom}$ functor and the tensor product functor $\otimes$ were not independent, but formally adjoints of each other. Adjoint functors gives us a further refinement of our categorical calculus for UIGs, since we can now construct functors that map between two apparently dissimilar categories, which may indeed be comparable, such as the category of conditional independence models, modeled as separoids [Dawid, 2001], and the category of causal models, modeled by an algebraic structure, such as a directed acyclic graph (DAG) [Pearl, 2009]. This relationship was explored previously in [Mahadevan, 2023] In the context of UIGs, two objects in the category of separoids are only statistically distinguishable, whereas two objects in the causal category of DAG models are causally distinct. By suitably enriching the Hom functor, we can model a rich variety of structures that capture properties of the interactions between two objects $A$ and $B$.

Kan also introduced Kan extensions in his paper on adjoint functors, which provide us deeper insight into the study of dynamic UIGs, where initially one participant is a “teacher" and the other is a “learner" that are distinguishable initially, but may become indistinguishable in the limit. [Gold, 1967] proposed the theoretical framework of identification in the limit, motivated by the remarkable ability of human children in acquiring natural language from hearing spoken text.  [Solomonoff, 1964] proposed inductive inference as a model for our ability to generalize from examples. Gold's framework was subsequently elaborated by [Valiant, 1984] and  [Vapnik, 1999], based on introducing a probabilistic perspective, as well as introducing the need for efficient estimation with a polynomial number of samples or time.  Abstractly, the problem of inductive inference or identification in the limit can be viewed as extrapolating a function from samples of the function. Given a function $f: C \rightarrow D$ that is defined on some subset $C \subset M$ that we want to extend to the entire set $M$, there are no obvious canonical solutions to this problem as it is inherently ill-defined. Much of the work in machine learning over the past six decades has explored various formulations of this function induction problem, usually introducing some regularization principle such as Occam's Razor, or prefer the simplest hypothesis [Belkin et al., 2006], or using some intrinsic measure of the complexity of an object, such as algorithmic information theory [Chaitin, 2002] based on the shortest program that can generate an object (also referred to as Kolmogorov complexity). In contrast, if instead, we assume that we are extending a functor $F: C \rightarrow D$ from some subcategory $C$ of a larger category $M$, there are two canonical and “universal" solutions to the functor extension problem given by Kan extensions. Thus, the Kan extension gives us a powerful set of tools to formulate dynamic UIGs.

Yoneda [Yoneda, 1960] developed another remarkable idea in 1960 based on defining the end of a bifunctor $F: C^{op} \times C \rightarrow D$ that, like the Hom functor above, is contravariant in the first argument, but covariant in the second argument. The end of a bifunctor $F: C^{op} \times C \rightarrow D$ refers to an object $\mbox{end}(P) \in {\cal D}$ that represents the terminal object in a category of wedges defined by dinatural transformations between bifunctors $F,G: C^{op} \times C \rightarrow {\cal D}$. A dual notion is the coend, which represents the initial object. The significance of the end and the coend of a bifunctor to this paper is that they capture universal properties of many AI and ML approaches. In particular, the end can be shown to define  the universal property of probability distributions on a space [Avery, 2016] in terms of the codensity monad, which is defined as the right Kan extension of a functor against itself. Analogously, the coend can be shown to define the topological realization functor of a (fuzzy) simplicial set, which has been the basis for a widely used manifold learning method called UMAP [McInnes et al., 2018]. A detailed discussion of the calculus of coends is given in [Loregian, 2021].

Finally, we build on the framework of non-well-founded sets [Aczel, 1988] and universal coalgebras [Jacobs, 2016, Rutten, 2000] in modeling UIGs. Here, we have a collection of participants that are neither static, nor are they dynamic, but rather they evolve by interacting with each other in a non-cooperative game [Maschler et al., 2013]. von Neumann and Morgenstern [von Neumann and Morgenstern, 1947], and subsequently Nash [Nash, 1951],  developed non-cooperative games as a model of economic behavior, which has had a persuasive influence on the development of AI, computer science, and of course, economics. It has also had profound significance in biology in the study of evolutionary games. Our framework builds on the theory of network economics [Nagurney, 1999], where the participants in an evolutionary UIG are interacting on a graph. The economic activity that occurs in a network economy classifies the participants as producers, such as vendors of generative AI products, transporters who control the network infrastructure over which data is transmitted, and finally consumers who constitute the demand market that must choose between a producer and a transporter. Each participant in an evolutionary UIG is seeking to maximize a selfish goal, and the formulation of evolutionary UIGs is based on determining if the network economy, formulated as a category of coalgebras, has a final coalgebra [Rutten, 2000].

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

Comparison of notions from set theory and category theory.

Category theory is a compositional model of a system in terms of objects and their interactions.

Figure <ref> compares the basic notions in set theory vs. category theory. Figure <ref> 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 \leq 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.

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}$.

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.

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

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

* An  arrow  $F(f): F X \rightarrow F Y$ 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_{F X}$ and $(F f) (F g) = F(g \circ f)$ for any composable arrows $f: X \rightarrow Y, g: Y \rightarrow Z$.

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}$.

One of the motifs that underlies much of the application of category theory to AI and ML in this paper is to model problems in terms of functors. Figure <ref> illustrates the use of functoriality in designing an algorithm for clustering points in a finite metric space based on pairwise distances, one of the most common ways to preprocess data in ML and statistics. Treating clustering as a functor implies the resulting algorithm should behave appropriately under suitable modifications of the input space. Here, we can define clustering formally as a functor $F$ that maps the input category of finite metric spaces FinMet defined by $(X, d)$, where $X$ is a finite set of points in $\mathbb{R}^n$ and $d:X \times X \rightarrow [0, \infty]$ is a (generalized) finite metric space, and the output category Part is the set of all partitions $X$ into subsets $X_i$ such that $\cup_i X_i = X$.

One of the most traditional problems in statistics and ML is clustering by constructing a partition of a finite metric space by grouping points together based on their pairwise distances. Treating clustering as a functor implies designing an algorithm that behaves functorially: if the distances were scaled by some factor, the clustering should not change.

One can impose three criteria on a clustering algorithm, which seem entirely natural, and yet, as Kleinberg [Kleinberg, 2002] showed, no standard clustering algorithm satisfies all these conditions:

* Scale invariance: If the distance metric $d$ is increased or decreased by $c \cdot d$, where $c$ is a scalar real number, the output clustering should not change. In terms of Figure <ref>, if the points in each cluster became closer together or further apart proportionally, the clustering should remain the same.

* Completeness: For any given partition of the space $X$, there should exist some distance function $d$ such that the clustering algorithm when given that distance function should return the desired partition.

* Monotonicity: If the  distance between points within each cluster in Figure <ref> were decreased, and the distances between points in different clusters were increased, the clustering should not change either.

Remarkably, it turns out that no clustering algorithm exists that satisfies all these three basic conditions. Yet, as Carlsson  and Memoli showed [Carlsson and Memoli, 2010], treating clustering as a functor makes it possible to define a modified clustering problem in terms of creating persistent clusters that overcomes Kleinberg's impossibility result. This simple but deep example reveals the power of functorial design, and gives a concrete illustration of the importance of categorical thinking in AI and ML.

§.§ Natural Transformations and Universal Arrows

Given any two functors $F: C \rightarrow D$ and $G: C \rightarrow D$ between the same pair of categories, we can define a mapping between $F$ and $G$ that is referred to as a natural transformation. These are defined through a collection of mappings, one for each object $c$ of $C$, thereby defining a morphism in $D$ for each object in $C$.

Given categories $C$ and $D$, and functors $F, G: C \rightarrow D$, a natural transformation $\alpha: F \Rightarrow G$ is defined by the following data:

* an arrow $\alpha_c: Fc \rightarrow Gc$ in $D$ for each object $c \in C$, which together define the components of the natural transformation.

* For each morphism $f: c \rightarrow c'$, the following commutative diagram holds true:

\[\begin{tikzcd}
Fc &&& Gc \\
\\
{Fc'} &&& {Gc'}
\arrow["{\alpha_c}", from=1-1, to=1-4]
\arrow["Ff"', from=1-1, to=3-1]
\arrow["{\alpha_{c'}}"', from=3-1, to=3-4]
\arrow["Gf", from=1-4, to=3-4]
\end{tikzcd}\]

A natural isomorphism is a natural transformation $\alpha: F \Rightarrow G$ in which every component $\alpha_c$ is an isomorphism.

We will see many examples of natural transformations in this paper, but we will use one example here to illustrate its versatility.
Figure <ref> shows that we can model causal models as functors mapping from an input category of algebraic structures, whose objects represent structural descriptions of the causal model, into an output category of probabilistic representations, whose objects specify the semantics of the causal model.

Causal models capture directional relationships between entities. A causal model can be viewed as a functor that maps a category of algebraic structures, whose objects are directed acyclic graph (DAG) models as shown here, or integer-valued multisets shown here as a lattice, into a category of probabilistic representations, each of whose objects can be viewed as a structured probability distribution.

This process of going from a category to its underlying directed graph  embodies a fundamental universal construction in category theory, called the universal arrow. It lies at the heart of many useful results, principally the Yoneda lemma that shows how object identity itself emerges from the structure of morphisms that lead into (or out of) it.

Given a functor $S: D \rightarrow C$ between two categories, and an object $c$ of category $C$, a universal arrow from $c$ to $S$ is a pair $\langle r, u \rangle$, where $r$ is an object of $D$ and $u: c \rightarrow Sr$ is an arrow of $C$, such that the following universal property holds true:

* For every pair $\langle d, f \rangle$ with $d$ an object of $D$ and $f: c \rightarrow Sd$ an arrow of $C$, there is a unique arrow $f': r \rightarrow d$ of $D$ with $S f' \circ u = f$.

If $D$ is a category and $H: D \rightarrow$ Set is a set-valued functor, a universal element associated with the functor $H$ is a pair $\langle r, e \rangle$ consisting of an object $r \in D$ and an element $e \in H r$ such that for every pair $\langle d, x \rangle$ with $x \in H d$, there is a unique arrow $f: r \rightarrow d$ of $D$ such

Let $E$ be an equivalence relation on a set $S$, and consider the quotient set $S/E$ of equivalence classes, where $p: S \rightarrow S/E$ sends each element $s \in S$ into its corresponding equivalence class. The set of equivalence classes $S/E$ has the property that any function $f: S \rightarrow X$ that respects the equivalence relation can be written as $f s = f s'$ whenever $s \sim_E s'$, that is, $f = f' \circ p$, where the unique function $f': S/E \rightarrow X$. Thus, $\langle S/E, p \rangle$ is a universal element for the functor $H$.

Figure <ref> illustrates the concept of universal arrows through the connection between categories and graphs. For every (directed) graph $G$, there is a universal arrow from $G$ to the “forgetful” functor $U$ mapping the category Cat of all categories to Graph, the category of all (directed) graphs, where for any category $C$, its associated graph is defined by $U(C)$. Intuitively, this forgetful functor “throws” away all categorical information, obliterating for example the distinction between the primitive morphisms $f$ and $g$ vs. their compositions $g \circ f$, both of which are simply viewed as edges in the graph $U(C)$.  To understand this functor,  consider a directed graph $U(C)$ defined from a category $C$, forgetting the rule for composition. That is, from the category $C$, which associates to each pair of composable arrows $f$ and $g$, the composed arrow $g \circ f$, we derive the underlying graph $U(C)$ simply by forgetting which edges correspond to elementary arrows, such as $f$ or $g$, and which are composites. For example, consider a partial order as the category ${\cal C}$, and then define  $U({\cal C} )$ as the directed graph that results from the transitive closure of the partial ordering.

The universal arrow from a graph $G$ to the forgetful functor $U$  is defined as a pair $\langle C, u: G \rightarrow U(C) \rangle$, where $u$ is a “universal”  graph homomorphism. This arrow possesses the following universal property: for every other pair $\langle D, v: G \rightarrow H \rangle$, where $D$ is a category, and $v$ is an arbitrary graph homomorphism, there is a functor  $f': C \rightarrow D$, which is an arrow in the category Cat of all categories, such that every graph homomorphism $\phi: G \rightarrow H$ uniquely factors through the universal graph homomorphism $u: G \rightarrow U(C)$  as the solution to the equation $\phi = U(f') \circ u$, where $U(f'): U(C) \rightarrow H$ (that is, $H = U(D)$).  Namely, the dotted arrow defines a graph homomorphism $U(f')$ that makes the triangle diagram “commute”, and the associated “extension” problem of finding this new graph homomorphism $U(f')$ is solved by “lifting” the associated category arrow $f': C \rightarrow D$. This property of universal arrows, as we show in the paper, provide the conceptual underpinnings of universal properties in many applications in AI and ML, as we will see throughout this paper.

The concept of universal arrows is illustrated through the connection between directed graphs, and their associated “free" categories. In this example, the forgetful functor $U$ between Cat, the category of all categories, and Graph, the category of all (directed) graphs, maps any category into its underlying graph, forgetting which arrows are primitive and which are compositional.  The universal arrow from a graph $G$ to the forgetful functor $U$  is defined as a pair $\langle C, u: G \rightarrow U(C) \rangle$, where $u$ is a “universal”  graph homomorphism. The universal arrow property asserts that every graph homomorphism $\phi: G \rightarrow H$ uniquely factors through the universal graph homomorphism $u: G \rightarrow U(C)$, where $U(C)$ is the graph induced  by category $C$ defining the universal arrow property. In other words, the associated extension problem of “completing” the triangle of graph homomorphisms in the category of Graph can be uniquely solved by “lifting” the associated category arrow $h: C \rightarrow D$.

§.§ Yoneda lemma and the Universality of Diagrams

The Yoneda Lemma  is one of the most celebrated results in category theory, and it provides a concrete example of the power of categorical thinking. Stated in simple terms, it states the mathematical objects are determined (up to isomorphism) by the interactions they make with other objects in a category. We will show the surprising results of applying this lemma to problems involving computing distances between objects in a metric space, reasoning about causal inference, and many other problems of importance in AI and ML. An analogy from particle physics proposed by Theo Johnson-Freyd might help give insight into this remarkable result: “You work at a particle accelerator. You want to understand some particle. All you can do is throw other particles at it and see what happens. If you understand how your mystery particle responds to all possible test particles at all possible test energies, then you know everything there is to know about your mystery particle". The Yoneda Lemma states that the set of all morphisms into an object $d$ in a category ${\cal C}$, denoted as Hom$_{\cal C}(-,d)$ and called the contravariant functor (or presheaf),  is sufficient to define $d$ up to isomorphism. The category of all presheaves forms a category of functors, and is denoted $\hat{{\cal C}} = $ Set$^{{\cal C}^{op}}$.We will briefly describe two concrete applications of this lemma to two important areas in AI and ML in this section: reasoning about causality and reasoning about distances. The Yoneda lemma plays a crucial role in this paper because it defines the concept of a universal representation in category theory. We first show that associated with universal arrows is the corresponding induced isomorphisms between Hom sets of morphisms in categories. This universal property then leads to the Yoneda lemma.

Given any functor $S: D \rightarrow C$, the universal arrow $\langle r, u: c \rightarrow Sr \rangle$ implies a bijection exists between the Hom sets

\[ \mbox{{\bf Hom}}_{D}(r, d) \simeq \mbox{{\bf Hom}}_{C}(c, Sd) \]

A special case of this natural transformation that transforms the identity morphism 1$_r$ leads us to the Yoneda lemma.

D(r,r) dD(r, f') rϕ_r
C(c, Sr) []dC(c, S f')

D(r,d)  []r[]ϕ_d
C(c, Sd)

As the two paths shown here must be equal in a commutative diagram, we get the property that a bijection between the Hom sets holds precisely when $\langle r, u: c \rightarrow Sr \rangle$ is a universal arrow from $c$ to $S$. Note that for the case when the categories $C$ and $D$ are small, meaning their Hom collection of arrows forms a set, the induced functor Hom$_C(c, S - )$ to Set is isomorphic to the functor Hom$_D(r, -)$. This type of isomorphism defines a universal representation, and is at the heart of the causal reproducing property (CRP) defined below.

Yoneda lemma: For any functor $F: C \rightarrow {\bf Set}$, whose domain category $C$ is “locally small" (meaning that the collection of morphisms between each pair of objects forms a set), any object $c$ in $C$, there is a bijection

\[ \mbox{Hom}(C(c, -), F) \simeq Fc \]

that defines a natural transformation $\alpha: C(c, -) \Rightarrow F$ to the element $\alpha_c(1_c) \in Fc$. This correspondence is natural in both $c$ and $F$.

There is of course a dual form of the Yoneda Lemma in terms of the contravariant functor $C(-, c)$ as well using the natural transformation $C(-, c) \Rightarrow F$. A very useful way to interpret the Yoneda Lemma is through the notion of universal representability through a covariant or contravariant functor.

A universal representation of an object $c \in C$ in a category $C$ is defined as a contravariant functor $F$ together with a functorial representation $C(-, c) \simeq F$ or by a covariant functor $F$ together with a representation $C(c, -) \simeq F$. The collection of morphisms $C(-, c)$ into an object $c$ is called the presheaf, and from the Yoneda Lemma, forms a universal representation of the object.

Later in this Section, we will see how the Yoneda Lemma gives us a novel perspective on causal inference, as well as distance metrics that are at the core of many applications in AI and ML. For causal inference, any causal influence on a variable $c$ in a causal model defined as an object in a category must be transmitted through its presheaf. The collection of all such causal influences in effect defines the object itself, giving a more rigorous way to substantiate an observation by the philosopher Plato made more than two millennia ago that

Everything that becomes or changes must do so owing to some cause; for nothing can come to be without a cause [Plato, 1971]

Another useful concept was introduced by the mathematician Grothendieck, who made many important contributions to category theory.

The category of elements $\int F$ of a covariant functor $F: C \rightarrow \mbox{{\bf Set}}$ is defined as

* a collection of objects  $(c, x)$ where $c \in C$ and $x \in Fc$

* a collection of morphisms $(c, x) \rightarrow (c', x')$ for every morphism $f: c \rightarrow c'$ such that $F f(x) = x'$.

The category of elements $\int F$ of a contravariant functor $F: C^{op} \rightarrow \mbox{{\bf Set}}$ is defined as

* a collection of objects  $(c, x)$ where $c \in C$ and $x \in Fc$

* a collection of morphisms $(c, x) \rightarrow (c', x')$ for every morphism $f: c \rightarrow c'$ such that $F f(x') = x$.

There is a natural “forgetful" functor $\pi: \int F \rightarrow C$ that maps the pairs of objects $(c, x) \in \int F$ to $c \in C$ and maps morphisms $(c, x) \rightarrow (c', x') \in \int F$ to $f: c \rightarrow c' \in C$. Below we will show that the category of elements $\int F$ can be defined through a universal construction as the pullback in the diagram of categories.

A key distinguishing feature of category theory is the use of diagrammatic reasoning. However, diagrams are also viewed more abstractly as functors mapping from some indexing category to the actual category. Diagrams are useful in understanding universal constructions, such as limits and colimits of diagrams. To make this somewhat abstract definition concrete, let us look at some simpler examples of universal properties, including co-products and quotients (which in set theory correspond to disjoint unions). Coproducts refer to the universal property of abstracting a group of elements into a larger one.

Before we formally the concept of limit and colimits, we consider some examples.  These notions generalize the more familiar notions of Cartesian products and disjoint unions in the category of Sets, the notion of meets and joins in the category Preord of preorders, as well as the  least upper bounds and greatest lower bounds in lattices, and many other concrete examples from mathematics.

If  we consider a small  “discrete” category ${\cal D}$ whose only morphisms are identity arrows, then the colimit of a functor ${\cal F}: {\cal D} \rightarrow {\cal C}$ is the categorical coproduct of ${\cal F}(D)$ for $D$, an object of category D, is denoted as

\[ \mbox{Colimit}_{\cal D} F = \bigsqcup_D {\cal F}(D) \]

In the special case when the category C is the category Sets, then the colimit of this functor is simply the disjoint union of all the sets $F(D)$ that are mapped from objects $D \in {\cal D}$.

Dual to the notion of colimit of a functor is the notion of limit. Once again, if we consider a small  “discrete” category ${\cal D}$ whose only morphisms are identity arrows, then the limit of a functor ${\cal F}: {\cal D} \rightarrow {\cal C}$ is the categorical product of ${\cal F}(D)$ for $D$, an object of category D, is denoted as

\[ \mbox{limit}_{\cal D} F = \prod_D {\cal F}(D) \]

In the special case when the category C is the category Sets, then the limit of this functor is simply the Cartesian product of all the sets $F(D)$ that are mapped from objects $D \in {\cal D}$.

Category theory relies extensively on universal constructions, which satisfy a universal property. One of the central building blocks is the identification of universal properties through formal diagrams.  Before introducing these definitions in their most abstract form, it greatly helps to see some simple examples.

We can illustrate the limits and colimits in diagrams using pullback and pushforward mappings.

Z[r, "p"] [d, "q"]
X [d, "f"] [ddr, bend left, "h"]

Y [r, "g"] [drr, bend right, "i"]    X ⊔Y [dr, "r"]

An example of a universal construction is given by the above commutative diagram, where the coproduct object $X \sqcup Y$ uniquely factorizes any mapping $h: X \rightarrow R$, such that any mapping $i: Y \rightarrow R$, so that $h = r \circ f$, and furthermore $i = r \circ g$. Co-products are themselves special cases of the more general notion of co-limits. Figure <ref>  illustrates the fundamental property of a pullback, which along with pushforward, is one of the core ideas in category theory. The pullback square with the objects $U,X, Y$ and $Z$ implies that the composite mappings $g \circ f'$ must equal $g' \circ f$. In this example, the morphisms $f$ and $g$ represent a pullback pair, as they share a common co-domain $Z$. The pair of morphisms $f', g'$ emanating from $U$ define a cone, because the pullback square “commutes” appropriately. Thus, the pullback of the pair of morphisms $f, g$ with the common co-domain $Z$ is the pair of morphisms $f', g'$ with common domain $U$. Furthermore, to satisfy the universal property, given another pair of morphisms $x, y$ with common domain $T$, there must exist another morphism $k: T \rightarrow U$ that “factorizes” $x, y$ appropriately, so that the composite morphisms $f' \ k = y$ and $g' \ k = x$. Here, $T$ and $U$ are referred to as cones, where $U$ is the limit of the set of all cones “above” $Z$. If we reverse arrow directions appropriately, we get the corresponding notion of pushforward. So, in this example, the pair of morphisms $f', g'$ that share a common domain represent a pushforward pair.
As Figure <ref>, for any set-valued functor $\delta: S \rightarrow$ Sets, the Grothendieck category of elements $\int \delta$ can be shown to be a pullback in the diagram of categories. Here, ${\bf Set}_*$ is the category of pointed sets, and $\pi$ is a projection that sends a pointed set $(X, x \in X)$ to its

[drr, bend left, "x"]
[ddr, bend right, "y"]
[dr, dotted, "k" description]

U[r, "g'"] [d, "f'"]
X [d, "f"]

Y [r, "g"]    Z

[drr, bend left, "x"]
[ddr, bend right, "y"]
[dr, dotted, "k" description]

∫δ[r, "δ'"] [d, "π_δ"]
Set_* [d, "π"]

S [r, "δ"]     Set

Universal Property of pullback mappings. (Right) The Grothendieck category of elements $\int \delta$ of any set-valued functor $\delta: S \rightarrow$ Set can be described as a pullback in the diagram of categories. Here, Set$_*$ is the category of pointed sets $(X, x \in X)$, and $\pi$ is the “forgetful" functor that sends a pointed set $(X, x \in X)$ into the underlying set $X$.

We can now proceed to define limits and colimits more generally. We define a diagram $F$ of shape $J$ in a category $C$ formally as a functor $F: J \rightarrow C$. We want to define the somewhat abstract concepts of limits and colimits, which will play a central role in this paper in identifying properties of AI and ML techniques.  A convenient way to introduce these concepts is through the use of universal cones that are over and under a diagram.

For any object $c \in C$ and any category $J$, the constant functor $c: J \rightarrow C$ maps every object $j$ of $J$ to $c$ and every morphism $f$ in $J$ to the identity morphisms $1_c$. We can define a constant functor embedding as the collection of constant functors $\Delta: C \rightarrow C^J$ that send each object $c$ in $C$ to the constant functor at $c$ and each morphism $f: c \rightarrow c'$ to the constant natural transformation, that is, the natural transformation whose every component is defined to be the morphism $f$.

A cone over a diagram $F: J \rightarrow C$ with the summit or apex $c \in C$ is a natural transformation $\lambda: c \Rightarrow F$ whose domain is the constant functor at $c$. The components $(\lambda_j: c \rightarrow Fj)_{j \in J}$ of the natural transformation can be viewed as its legs. Dually, a cone under $F$ with nadir $c$ is a natural transformation $\lambda: F \Rightarrow c$ whose legs are the components $(\lambda_j: F_j \rightarrow c)_{j \in J}$.

\[\begin{tikzcd}
&& c &&&& Fj &&&& Fk \\
\\
{F j} &&&& Fk &&&& c
\arrow["{\lambda_j}", from=1-3, to=3-1]
\arrow["{\lambda_k}"', from=1-3, to=3-5]
\arrow["{F f}", from=3-1, to=3-5]
\arrow["Ff", from=1-7, to=1-11]
\arrow["{\lambda_j}"', from=1-7, to=3-9]
\arrow["{\lambda_k}", from=1-11, to=3-9]
\end{tikzcd}\]

Cones under a diagram are referred to usually as cocones. Using the concept of cones and cocones, we can now formally define the concept of limits and colimits more precisely.

For any diagram $F: J \rightarrow C$, there is a functor

\[ \mbox{Cone}(-, F): C^{op} \rightarrow \mbox{{\bf Set}} \]

which sends $c \in C$ to the set of cones over $F$ with apex $c$. Using the Yoneda Lemma, a limit of $F$ is defined as an object $\lim F \in C$ together with a natural transformation $\lambda: \lim F \rightarrow F$, which can be called the universal cone defining the natural isomorphism

\[ C(-, \lim F) \simeq \mbox{Cone}(-, F) \]

Dually, for colimits, we can define a functor

\[ \mbox{Cone}(F, -): C \rightarrow \mbox{{\bf Set}} \]

that maps object $c \in C$ to the set of cones under $F$ with nadir $c$. A colimit of $F$ is a representation for $\mbox{Cone}(F, -)$. Once again, using the Yoneda Lemma, a colimit is defined by an object $\mbox{Colim} F \in C$ together with a natural transformation $\lambda: F \rightarrow \mbox{colim} F$, which defines the colimit cone as the natural isomorphism

\[ C(\mbox{colim} F, -) \simeq \mbox{Cone}(F, -) \]

Limit and colimits of diagrams over arbitrary categories can often be reduced to the case of their corresponding diagram properties over sets. One important stepping stone is to understand how functors interact with limits and colimits.

For any class of diagrams $K: J \rightarrow C$, a functor $F: C \rightarrow D$

* preserves limits if for any diagram $K: J \rightarrow C$ and limit cone over $K$, the image of the cone defines a limit cone over the composite diagram $F K: J \rightarrow D$.

* reflects limits if for any cone over a diagram $K: J \rightarrow C$ whose image upon applying $F$ is a limit cone for the diagram $F K: J \rightarrow D$ is a limit cone over $K$

* creates limits if whenever $FK : J \rightarrow D$ has a limit in $D$, there is some limit cone over $F K$ that can be lifted to a limit cone over $K$ and moreoever $F$ reflects the limits in the class of diagrams.

To interpret these abstract definitions, it helps to concretize them in terms of a specific universal construction, like the pullback defined above $c' \rightarrow c \leftarrow c''$ in $C$. Specifically, for pullbacks:

* A functor $F$ preserves pullbacks if whenever $p$ is the pullback of  $c' \rightarrow c \leftarrow c''$ in $C$, it follows that $Fp$ is the pullback of  $Fc' \rightarrow Fc \leftarrow Fc''$ in $D$.

* A functor $F$ reflects  pullbacks  if  $p$ is the pullback of  $c' \rightarrow c \leftarrow c''$ in $C$ whenever $Fp$ is the pullback of  $Fc' \rightarrow Fc \leftarrow Fc''$ in $D$.

* A functor $F$ creates pullbacks if there exists some $p$ that is the pullback of  $c' \rightarrow c \leftarrow c''$ in $C$ whenever there exists a $d$ such  that $d$ is the pullback of  $Fc' \rightarrow Fc \leftarrow Fc''$ in $F$.

§.§ Universality of Diagrams

In the category Sets, we know that every object (i.e., a set) $X$ can be expressed as a coproduct (i.e., disjoint union)  of its elements $X \simeq \sqcup_{x \in X} \{ x \}$, where $x \in X$. Note that we can view each element $x \in X$ as a morphism $x: \{ * \} \rightarrow X$ from the one-point set to $X$. The categorical generalization of this result is called the density theorem in the theory of sheaves. First, we define the key concept of a comma category.

Let $F: {\cal D} \rightarrow {\cal C}$ be a functor from category ${\cal D}$ to ${\cal C}$. The comma category $F \downarrow {\cal C}$ is one whose objects are pairs $(D, f)$, where $D \in {\cal D}$ is an object of ${\cal D}$ and $f \in$ Hom$_{\cal C}(F(D), C)$, where $C$ is an object of ${\cal C}$. Morphisms in the comma category $F \downarrow {\cal C}$ from $(D, f)$ to $(D', f')$, where $g: D \rightarrow D'$, such that $f' \circ F(g) = f$. We can depict this structure through the following commutative diagram:

[column sep=small]
F(D) dl[near start]F(g) drf

F(D')rrf'                                C

We first introduce the concept of a dense functor:

Let D be a small category, C be an arbitrary category, and $F: {\cal D} \rightarrow {\cal D}$ be a functor. The functor $F$ is dense if for all objects $C$ of ${\cal C}$, the natural transformation

\[ \psi^C_F: F \circ U \rightarrow \Delta_C, \ \ (\psi^C_F)_{({\cal D}, f)} = f\]

is universal in the sense that it induces an isomorphism $\mbox{Colimit}_{F \downarrow C} F \circ U \simeq C$. Here, $U: F \downarrow C \rightarrow {\cal D}$ is the projection functor from the comma category $F \downarrow {\cal C}$, defined by $U(D, f) = D$.

A fundamental consequence of the category of elements is that every object in the functor category of presheaves, namely contravariant functors from a category into the category of sets, is the colimit of a diagram of representable objects, via the Yoneda lemma. Notice this is a generalized form of the density notion from the category Sets.

Universality of Diagrams: In the functor category of presheaves Set$^{{\cal C}^{op}}$, every object $P$ is the colimit of a diagram of representable objects, in a canonical way.

§.§ Lifting Problems

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.

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

A df rμ
X []dp

B  []r[]ν

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 df rμ
X []dp

B [ur,dashed, "h"] []r[]ν

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 df rμ
X []dp

B [ur,dashed, "h"] []r[]ν

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

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.

∅df rμ
X []dp

{ ∙} [ur,dashed, "h"] []r[]ν

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.

{∙, ∙} df rμ
X []dp

{ ∙} [ur,dashed, "h"]  []r[]ν

§.§ Adjoint Functors

Adjoint functors naturally arise in a number of contexts, among the most important being between “free" and “forgetful" functors. Let us consider a canonical example that  is of prime significance in many applications in AI and ML.

Adjoint functors provide an elegant characterization of the relationship between the category of statistical models and that of causal models. Statistical models can be viewed as the result of applying a “forgetful" functor to a causal model that drops the directional structure in a causal model, whereas causal models can be viewed as “words" in a “free" algebra that results from the left adjoint functor to the forgetful functor.

Figure <ref> provides a high level overview of the relationship between a category of statistical models and a category of causal models that can be seen as being related by a pair of adjoint “forgetful-free" functors. A statistical model can be abstractly viewed in terms of its conditional independence properties. More concretely, the category of separoids, defined in Section 2, consists of objects called separoids $(S, \leq)$, which are semilattices with a preordering $\leq$ where the elements $x, y, z \in S$ denote entities  in a statistical model. We define a ternary relation $(\bullet \perp \bullet | \bullet) \subseteq S \times S \times S$, where $(x \perp y | z)$ is interpreted as the statement $x$ is conditionally independent of $y$ given $z$ to denote a relationship between triples that captures abstractly the property that occurs in many applications in AI and ML. For example, in statistical ML, a sufficient statistic $T(X)$ of some dataset $X$, treated as a random variable, is defined to be any function for which the conditional independence relationship $(X \perp  \theta| T(X))$, where $\theta \in \mathbb{R}^k$ denotes the parameter vector of some statistical model $P(X)$ that defines the true distribution of the data. Similarly, in causal inference, $(x \perp y | z)  \Rightarrow p(x, y, z) = p(x | z) p(y | z)$ denotes a statement about the probabilistic conditional independence of $x$ and $y$ given $z$. In causal inference, the goal is to recover a partial order defined as a directed acyclic graph (DAG) that ascribes causality among a set of random variables from a dataset specifying a sample of their joint distribution. It is well known that without non-random interventions, causality cannot be inferred uniquely, since because of Bayes rule, there is no way to distinguish causal models such as $x \rightarrow y \rightarrow z$ from the reverse relationship $z \rightarrow y \rightarrow x$. In both these models, $x \perp z | y$ and because of Bayes inversion, one model can be recovered from the other. We can define a “free-forgetful" pair of adjoint functors between the category of conditional independence relationships, as defined by separoid objects, and the category of causal models parameterized by DAG models.

We first review some basic material relating to adjunctions defined by adjoint functors, before proceeding to describe the theory of monads, as the two are intimately related. Our presentation of adjunctions and monads is based on Riehl's excellent textbook on category theory [Riehl, 2017] to which the reader is referred to for a more detailed explanation.
Adjunctions are defined by an opposing pair of functors $F: C \leftrightarrow D: G$ that can be defined more precisely as follows.

An adjunction consists of a pair of functors $F: C \rightarrow D$ and $G: D \rightarrow C$, where $F$ is often referred to left adjoint and  $G$ is referred to as the right adjoint, that result in the following isomorphism relationship holding between their following sets of homomorphisms in categories $C$ and $D$:

\[ D(Fc, d) \simeq C(c, Gd) \]

We can express the isomorphism condition more explicitly in the form of the following commutative diagram:

D(Fc, d) [r, "≃"] [d, "k_*"]
C(c, Gd) [d, "Gk_*" ]

D(Fc, d') [r,  "≃"]
C(c, Gd')

Here, $k: d \rightarrow d'$ is any morphism in $D$, and $k_*$ denotes the “pullback" of $k$ with the mapping $f: Fc \rightarrow d$ to yield the composite mapping $k \circ f$. The adjunction condition holds that the transpose of this composite mapping is equal to the composite mapping $g: c \rightarrow Gd$ with $G k: Gd \rightarrow G d'$. We can express this dually as well, as follows:

D(Fc, d) [r, "≃"] [d, "Fh^*"]
C(c, Gd) [d, "h^*" ]

D(Fc', d) [r,  "≃"]
C(c', Gd')

where now $h: c' \rightarrow c$ is a morphism in $C$, and $h^*$ denote the “pushforward" of $h$. Once again, the adjunction condition is a statement that the transpose of the composite mapping $f \circ Fh: F c' \rightarrow d$ is identical to the composite of the mappings $h: c \rightarrow c'$ with $f: c \rightarrow Gd$.

It is common to denote adjoint functors in this turnstile notation, indicating that $F: C \rightarrow D$ is left adjoint to $G: D \rightarrow C$, or more simply as $F \vdash G$.

\[
\begin{tikzcd}
\mathcal{D}\arrow[r, shift left=.75ex, "G"{name=G}] & \mathcal{C}\arrow[l, shift left=.75ex, "F"{name=F}]
\arrow[phantom, from=F, to=G, "\dashv" rotate=90].
\end{tikzcd}
\]

We can use the concept of universal arrows introduced in Section 2 to give more insight into adjoint functors. The adjunction condition for a pair of adjoint functors $F \vdash G$

\[ D(Fc, d) \simeq C(c, Gd) \]

implies that for any object $c \in C$, the object $Fc \in D$ represents the functor $C(c, G -): D \rightarrow {\bf Set}$. Recall from the Yoneda Lemma that the natural isomorphism $D(Fc, -) \simeq C(c, G-)$ is determined by an element of $C(c,GFc)$, which can be viewed as the transpose of $1_{Fc}$. Denoting such elements as $\eta_c$, they can be assembled jointly into the natural transformation $\eta: 1_C \rightarrow GF$. Below we will see that this forms one of the conditions for an endofunctor to define a monad.

The unit $\eta: 1_C \rightarrow GF$ is a natural transformation defined by an adjunction $F \vdash G$, whose component $\eta_c: c \rightarrow GF c$ is defined to be the transpose of the identity morphism $1_{Fc}$.

Proof: We need to show that for every $f: c \rightarrow c'$, the following diagram commutes, which follows from the definition of adjunction and the isomorphism condition that it imposes, as well as the obvious commutativity of the second transposed diagram below the first one.

c [r, "η_c"] [d, "f"]
GF c[d, "GF f" ]

c' [r,  "η_c'"]
GF c'

Fc [r, "1_Fc"] [d, "Ff"]
Fc [d, "F f" ]

Fc' [r,  "1_Fc'"]

The dual of the above theorem leads to the second major component  of an adjunction.

The counit $\epsilon: FG \Rightarrow 1_D$ is a natural transformation defined by an adjunction $F \vdash G$, whose components $\epsilon_c: F G d \rightarrow d$ at $d$ is  defined to be the transpose of the identity morphism $1_{Gd}$.

Adjoint functors interact with universal constructions, such as limits and colimits, in ways that turn out to be important for a variety of applications in AI and ML. We state the main results here, but refer the reader to [Riehl, 2017] for detailed proofs. Before getting to the general case, it is illustrative to see the interaction of limits and colimits with adjoint functors for preorders. Recall from above that separoids are defined by a preorder $(S, \leq)$ on a join lattice of elements from a set $S$. Given two separoids $(S, \leq_S)$ and $(T, \leq_T)$, we can define the functors $F: S \rightarrow T$ and $G: T \rightarrow S$ to be order-preserving functions such that

\[ Fa \leq_T b \ \ \ \mbox{if and only if} \ \ \ a \leq_S Gb \]

Such an adjunction between preorders is often called a Galois connection.  For preorders, the limit is defined by the meet of the preorder, and the colimit is defined by the join of the preorder. We can now state a useful result. For a fuller discussion of preorders and their applications from a category theory perspective, see [Fong and Spivak, 2018].

Right adjoints preserve meets in a preorder: Let $f: P \rightarrow Q$ be left adjoint to $g: Q \rightarrow P$, where $P, Q$ are both preorders, and $f$ and $g$ are monotone order-preserving functions. For any subset $A \subseteq Q$, let $g(A) = \{ g(a) | a \in Q \}$. If $A$ has a meet $\bigwedge A \in Q$, then $g(A)$ has a meet $\wedge g(A) \in P$, and we can see that $g(\wedge A) \simeq \bigwedge g(A) $, that is, right adjoints preserve meets. Similarly, left adjoints preserve meets, so that if $A \subset P$ such that $\bigvee A \in P$ then $f(A)$ has a join $\vee f(A) \in Q$ and we can set $f(\vee A) \simeq \bigvee f(A)$, so that left adjoints preserve joins.

Proof: The proof is not difficult in this special case of the category being defined as a preorder. If $f: P \rightarrow Q$ and $g: Q \rightarrow P$ are monotone adjoint maps on preorders $P, Q$, and $A \subset Q$ is any subset such that its meet is $m = \wedge A$. Since $g$ is monotone, $g(m) \leq g(a), \ \forall a \in A$, hence it follows that $g(m) \leq g(A)$. To show that $g(m$ is the greatest lower bound, if we take any other lower bound $b \leq g(a), \ \forall a \in A$, then we want to show that $b \leq g(m)$. Since $f$ and $g$ are adjoint, for every $p \in  P, q \in Q$, we have

\[ p \leq g(f(p)) \ \ \ \mbox{and} \ \ \ f(g(q)) \leq q \]

Hence, $f(b) \leq a$ for all $a \in A$, which implies $f(b)$ is  a lower bound for $A$ on $Q$. Since the meet $m$ is the greatest lower bound, we have $f(b) \leq m$. Using the Galois connection, we see that $b \leq g(m)$, and hence showing that $g(m)$ is the greatest lower bound as required. An analogous proof follows to show that left adjoints preserve joins. $\qed$

We can now state the more general cases for any pair of adjoint functors, as follows.

A category ${\cal C}$ admits all limits of diagrams indexed by a small category ${\cal J}$ if and only if the constant functor $\Delta: {\cal C} \rightarrow {\cal C}^{{\cal J}}$ admits a right adjoint, and admits all colimits of ${\cal J}$-indexed diagrams if and only if $\Delta$ admits a left adjoint.

By way of explanation, the constant functor $c: J \rightarrow C$ sends every object of $J$ to $c$ and every morphism of $J$ to the identity morphism  $1_c$. Here, the constant functor $\Delta$ sends every object $c$ of $C$ to the constant diagram $\Delta c$, namely the functor that maps each object $i$ of $J$ to the object $c$ and each morphism of $J$ to the identity $1_c$. The theorem follows from the definition of the universal properties of colimits and limits. Given any object $c \in C$, and any diagram (functor) $F \in {\cal C}^{{\cal J}}$, the set of morphisms ${\cal C}^{{\cal J}}(\Delta c, F)$ corresponds to the set of natural transformations from the constant ${\cal J}$-diagram at $c$ to the diagram $F$. These natural transformations precisely correspond to the cones over $F$ with summit $c$ in the definition given earlier in Section 2. It follows that there is an object $\lim F \in {\cal C}$ together with an isomorphism

\[ {\cal C}^{{\cal J}}(\Delta c, F) \simeq {\cal C}(c, \lim F) \]

We can now state the more general result that we showed above for the special case of adjoint functors on preorders.

Right adjoints preserve limits, whereas left adjoints preserve colimits.

§.§ Ends, Coends, and Kan Extensions

Perhaps the most canonical category for formulating UIGs is the category of wedges, which are defined by a collection of objects comprised of bifunctors $F: {\cal C}^{op} \times C \rightarrow {\cal D}$, and a collection of arrows between each pair of bifunctors $F, G$ called a dinatural transformation (as an abbreviation for diagonal natural transformation). We will see below that the initial and terminal objects in the category of wedges correspond to a beatiful idea first articulated by Yoneda called the coend or end [Yoneda, 1960]. [Loregian, 2021] has an excellent treatment of coend calculus, which we will use below.

Given a pair of bifunctors $F, G: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$, a dinatural transformation is defined as follows:

\[\begin{tikzcd}
&& {F(c',c)} \\
{F(c,c)} &&&& {F(c',c')} \\
\\
{G(c,c)} &&&& {G(c',c')} \\
&& {G(c,c')}
\arrow["{F(f,c)}", from=1-3, to=2-1]
\arrow["{F(c',f)}"', from=1-3, to=2-5]
\arrow[dashed, from=2-1, to=4-1]
\arrow[dashed, from=2-5, to=4-5]
\arrow["{G(c,f)}", from=4-1, to=5-3]
\arrow["{G(f,c)}"', from=4-5, to=5-3]
\end{tikzcd}\]

As [Loregian, 2021] observes, just as a natural transformation interpolates between two regular functors $F$ and $G$ by filling in the gap between their action on a morphism $Ff$ and $Fg$ on the codomain category, a dinatural transformation “fills in the gap" between the top of the hexagon above and the bottom of the hexagon.

We can define a constant bifunctor $\Delta_d: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$ by the object it maps everything to, namely the input pair of objects $(c, c') \rightarrow d$ are both mapped to the object $d \in {\cal D}$, and the two input morphisms $(f, f') \rightarrow {\bf 1}_d$ are both mapped to the identity morphism on $d$. We can now define wedges and cowedges.

A wedge for a bifunctor $F: {\cal C}^{op} \times {\cal C} \Rightarrow {\cal D}$ is a dinatural transformation $\Delta_d \rightarrow F$ from the constant functor on the object $d \in {\cal D}$ to $F$. Dually, we can define a cowedge for a bifunctor $F$ by the dinatural transformation $P \Rightarrow \Delta_d$.

We can now define a category of wedges, each of whose objects are wedges, and for arrows, we choose arrows in the co-domain category that makes the diagram below commute.

Given a fixed bifunctor $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$, we define the category of wedges ${\cal W}(F)$ where each object is a wedge $\Delta_d \Rightarrow F$ and given a pair of wedges $\Delta_d \Rightarrow F$ and $\Delta_d' \Rightarrow F$, we choose an arrow $f: d \rightarrow d'$ that makes the following diagram commute:

\[\begin{tikzcd}
d &&&& {d'} \\
\\
&& {F(c,c)}
\arrow["f", from=1-1, to=1-5]
\arrow["{\alpha_{cc}}"', from=1-1, to=3-3]
\arrow["{\alpha'_{cc}}", from=1-5, to=3-3]
\end{tikzcd}\]

Analogously, we can define a category of cowedges where each object is defined as a cowedge $F \Rightarrow \Delta_d$.

With these definitions in place, we can once again define the universal property in terms of initial and terminal objects. In the category of wedges and cowedges, these have special significance for formulating and solving UIGs, as we will see in the next section.

Given a bifunctor $F: {\cal C}^{op} \times {\cal C} \rightarrow {\cal D}$, the end of $F$ consists of a terminal wedge $\omega: \underline{{\bf end}}(F) \Rightarrow F$. The object $\underline{{\bf end}}(F) \in D$ is itself called the end. Dually, the coend of $F$ is the initial object in the category of cowedges $F \Rightarrow \underline{{\bf coend}}(F)$, where the object $\underline{{\bf coend}}(F) \in {\cal D}$ is itself called the coend of $F$.

Remarkably, probabilities can be formally shown to define ends of a category [Avery, 2016], and topological embeddings of datasets, as implemented in popular dimensionality reduction methods like UMAP [McInnes et al., 2018], correspond to coends [MacLane, 1971].  These connections suggest the canonical importance of the category of wedges and cowedges in formulating and solving UIGs. First, we introduce another universal construction, the Kan extension, which turns out to be the basis of every other concept in category theory.

§.§ Extending Functors rather than Functions: Kan Extensions

Often, in machine learning, we are given samples of a function defined on some subset $f: A \rightarrow B$ and we want to extend the function over a larger set $A \subset M$, but there is no obvious or canonical extension of functions. This ill-defined nature of machine learning has prompted a large variety of solutions, such as regularization or Occam's razor (prefer the simplest function). In contrast, if we are given a functor $F: A \rightarrow B$, and we want to extend the functor to a larger category $M$, there are only two canonical solutions that present themselves. These are referred to as the Kan extensions. There is a close connection between the notions of ends and coends and Kan extensions [Loregian, 2021], as well as to the categorical foundation of probability [Avery, 2016].

A left Kan extension of a functor ${\cal F}: {\cal C} \rightarrow {\cal E}$ along another functor ${\cal K}: {\cal C} \rightarrow {\cal D}$, is a functor $\mbox{Lan}_{\cal K} {\cal F}: {\cal D} \rightarrow {\cal E}$ with a natural transformation $\eta: F \Rightarrow \mbox{Lan}_F \circ K$ such that for any other such pair $(G: {\cal D} \rightarrow {\cal E}, \gamma: F \Rightarrow G K)$, $\gamma$ factors uniquely through $\eta$. In other words, there is a unique natural transformation $\alpha: \mbox{Lan}_F \Rightarrow G$.

[row sep=huge, column sep=huge]

𝒞 [dr, "𝒦"'name=F]
[rr, "ℱ", ""name=H, below]        ℰ

|[alias=D]| 𝒟 [ur, swap, dashed,

[Rightarrow, from=H, to=D, "η",shorten >=1em,shorten <=1em]

A right Kan extension of a functor ${\cal F}: {\cal C} \rightarrow {\cal E}$ along another functor ${\cal K}: {\cal C} \rightarrow {\cal D}$, is a functor $\eta: \mbox{Ran}_F \circ K \rightarrow F$  with a natural transformation $\eta: \mbox{Lan}_F \circ K \Rightarrow {\cal F}$ such that for any other such pair $(G: {\cal D} \rightarrow {\cal E}, \gamma: G K \Rightarrow F)$, $\gamma$ factors uniquely through $\eta$. In other words, there is a unique natural transformation $\alpha: G \Rightarrow \mbox{Ran}_F$.

[row sep=huge, column sep=huge]

𝒞 [dr, "𝒦"'name=F]
[rr, "ℱ", ""name=H, below]        ℰ

|[alias=D]| 𝒟 [ur, swap, dashed,

[Rightarrow, to=H, from=D, "η",shorten >=1em,shorten <=1em]

§.§ Monads and Categorical Probability

Now, we turn to defining monads more formally, and relate them to adjoint functors. Categorically speaking, probabilities are essentially  monads [Avery, 2016, Giry, 1982]. Like the case with coalgebras, which we discussed extensively in previous Sections, monads also are defined by an endofunctor on a category, but one that has some special properties. These additional properties make monads possess algebraic structure, which leads to many interesting properties. Monads provide a categorical foundation for probability, based on the property that the set of all distributions on a measurable space is itself a measurable space [Avery, 2016].  The well-known Giry monad [Giry, 1982] been also shown to arise as the codensity monad  of a forgetful functor from the category of convex sets with affine maps to the category of measurable spaces [Avery, 2016]. Our goal in this paper is to apply monads to shed light into causal inference.   We first review the basic definitions of monads, and then discuss monad algebras, which provide ways of characterizing categories.

Consider the pair of adjoint free and forgetful functors between graphs and categories. Here, the domain category is Cat, the category of all categories whose objects are categories and whose morphisms are functors. The co-domain category is the category Graph of all graphs, whose objects are directed graphs, and whose morphisms are graph homomorphisms. Here, a monad $T = U \circ F$ is induced by composing the “free" functor $F$ that maps a graph into its associated “free" category, and the “forgetful" functor $U$ that maps a category into its associated graph. The monad $T$  in effect takes a directed graph $G$ and computes its transitive closure $G_{tc}$. More precisely,  for every (directed) graph $G$, there is a universal arrow from $G$ to the “forgetful" functor $U$ mapping the category Cat of all categories to Graph, the category of all (directed) graphs, where for any category $C$, its associated graph is defined by $U(C)$.

To understand this functor, simply consider a directed graph $U(C)$ as a category $C$ forgetting the rule for composition. That is, from the category $C$, which associates to each pair of composable arrows $f$ and $g$, the composed arrow $g \circ f$, we derive the underlying graph $U(G)$ simply by forgetting which edges correspond to elementary functions, such as $f$ or $g$, and which are composites. The universal arrow from a graph $G$ to the forgetful functor $U$  is defined as a pair $\langle G, u: G \rightarrow U(C) \rangle$, where $u$ is a a graph homomorphism. This arrow possesses the following universal property: for every other pair $\langle D, v: G \rightarrow H \rangle$, where $D$ is a category, and $v$ is an arbitrary graph homomorphism, there is a functor  $f': C \rightarrow D$, which is an arrow in the category Cat of all categories, such that every graph homomorphism $\phi: G \rightarrow H$ uniquely factors through the universal graph homomorphism $u: G \rightarrow U(C)$  as the solution to the equation $\phi = U(f') \circ u$, where $U(f'): U(C) \rightarrow H$ (that is, $H = U(D)$).  Namely, the dotted arrow defines a graph homomorphism $U(f')$ that makes the triangle diagram “commute", and the associated “extension" problem of finding this new graph homomorphism $U(f')$ is solved by “lifting" the associated category arrow $f': C \rightarrow D$. In causal inference using graph-based models, the transitive closure graph is quite important in a number of situations. It can be the initial target of a causal discovery algorithm that uses conditional independence oracles. It is also common in graph-based causal inference [Pearl, 2009] to model causal effects through a directed acyclic graph (DAG) $G$, which specifies its algebraic structure, and through a set of probability distributions on $G$ that specifies its semantics $P(G)$. Often, reasoning about causality in a DAG requires examining paths that lead from some vertex $x$, representing a causal variable, to some other vertex $y$. The process of constructing the transitive closure of a DAG provides a simple example of a causal monad.

A monad on a category $C$ consists of

* An endofunctor $T: C \rightarrow C$

* A unit natural transformation $\eta: 1_C \Rightarrow T$

* A multiplication natural transformation $\mu: T^2 \rightarrow T$

such that the following commutative diagram in the category $C^C$ commutes (notice the arrows in this diagram are natural transformations as each object in the diagram is a functor).

\[\begin{tikzcd}
{T^3} &&&& {T^2} \\
\\
\\
{T^2} &&&& T
\arrow["{T \mu}", from=1-1, to=1-5]
\arrow["{\mu T}"', from=1-1, to=4-1]
\arrow["\mu"', from=4-1, to=4-5]
\arrow["\mu", from=1-5, to=4-5]
\end{tikzcd}\]

\[\begin{tikzcd}
T &&& {T^2} &&& T \\
\\
\\
&&& T
\arrow["{T \eta}"', from=1-7, to=1-4]
\arrow["\mu", from=1-4, to=4-4]
\arrow["{\eta T}", from=1-1, to=1-4]
\arrow["{1_T}"', from=1-1, to=4-4]
\arrow["{1_T}"', from=1-7, to=4-4]
\end{tikzcd}\]

It is useful to think of monads as the “shadow" cast by an adjunction on the category corresponding to the co-domain of the right adjoint $G$. Consider the following pair of adjoint functors $F \vdash G$.

\[
\begin{tikzcd}
\mathcal{C}\arrow[r, shift left=.75ex, "F"{name=F}] & \mathcal{D}\arrow[l, shift left=.75ex, "G"{name=G}]
\arrow[phantom, from=F, to=G, "\dashv" rotate=270].
\end{tikzcd}  \ \ \ \ \eta: 1_C \Rightarrow UF, \ \ \ \epsilon: FU \Rightarrow 1_D
\]

In the language of ML, if we treat category $C$ as representing “labeled training data" where we have full information, and category $D$ as representing a new domain for which we have no labels, what can we conclude about category $D$ from the information we have from the adjunction? The endofunctor $UF$ on $C$ is of course available to us, as is the natural transformation $\eta: 1_C \Rightarrow UF$. The map $\epsilon_A: FG A \rightarrow A$ for any object $A \in D$ is an endofunctor on $D$, about which we have no information. However, the augmented natural transformation $U \epsilon F A: G F G F A \rightarrow G F A$ can be studied in category $C$. From this data, what can we conclude about the objects in category $D$? In response to the natural question of whether every monad can be defined by a pair of adjoint functors, two solutions arose that came about from two different pairs of adjoint functors. These are referred to as the Eilenberg-Moore category and the Kleisli category [MacLane, 1971].

§.§ Codensity Monads and Probability

A striking recent finding is that categorical probability structures, such as Giry monads, are in essence codensity monads that result from extending a certain functor along itself [Avery, 2016].

A codensity monad $T^{\cal F}$ of a functor ${\cal F}$ is the right Kan extension of ${\cal F}$ along itself (if it exists). The codensity monad inherits the university property from the Kan extension.

[row sep=huge, column sep=huge]

𝒞 [dr, "ℱ"'name=F]
[rr, "ℱ", ""name=H, below]        ℰ

|[alias=D]| ℰ [ur, swap, dashed,

[Rightarrow, to=H, from=D, "η",shorten >=1em,shorten <=1em]

Codensity monads can also be written using Yoneda's abstract integral calculus as ends:

\[ T^{\cal F} e = \int_{c \in C} [{\cal E}(e, {\cal F}c), {\cal F}c]\]

Here, the notation $[A, m]$, where $A$ is any set, and $m$ is any object of a category ${\cal M}$, denotes the product in ${\cal M}$ of $A$ copies of $m$.

A convex set $c$ is a convex subset of a real vector space, where for all $x, y \in c$, and for all $r \in [0,1]$, the convex combination $r x + (1 - r) y \in c$. An affine map $h: c \rightarrow c'$ is a function such that $h(x +_r y) = h(x) +_r h(y)$ where $x +_r y = r x + (1 - r) y, r \in [0,1]$.

To define categorical probability as codensity monads, we need to  define forgetful functors from the category ${\cal C}'$ of compact convex subsets of $\mathbb{R}{^n}$ with affine maps to the category ${\bf Meas}$ of measurable spaces and measurable functions. In addition, let ${\cal D}'$ be the category ${\cal C}'$ with the object $d_0$ adjoined, where $d_0$ is the convex set of convergent sequences in the unit interval $I = [0,1]$.

The ${\cal C}'$ be the category of compact convex subsets of $\mathbb{R}^n$ for varying $n$ with affine maps between them, and let ${\cal D}'$ be the same with the object $d_0$ adjoined. Then, the codensity monads of the forgetful functors $U': {\cal C}' \rightarrow {\bf Meas}$ and $V': {\cal D}' \rightarrow {\bf Meas}$ are the finitely additive Giry monad and the Giry monad respectively.

The well-known Giry monad [Giry, 1982] defines probabilities in both the discrete case and the continuous case (over Polish spaces) in terms of endofunctor on the category of measurable spaces ${\bf Meas}$.

§.§ Sheaves and Topoi

In this section, we define an important categorical structure defined by sheaves and topoi [MacLane and leke Moerdijk, 1994].  Yoneda embeddings $\yo(x): {\cal C}^{op} \rightarrow {\bf Sets}$ define (pre)sheaves, which satisfy a number of crucial properties that make it remarkably similar to the category of Sets. The sheaf condition plays an important role in many applications of machine learning, from dimensionality reduction [McInnes et al., 2018] to causal inference [Mahadevan, 2023]. [MacLane and leke Moerdijk, 1994] provides an excellent overview of sheaves and topoi, and how remarkably they unify much of mathematics, from geometry to logic and topology. We will give only the briefest of overviews here, and apply in the main ideas to the study of UIGs.

Two applications of sheaf theory in AI: (top) minimizing travel costs in weighted graphs satisfies the sheaf principle, one example of which is the Bellman optimality principle in dynamic programming [Bertsekas, 2005] and reinforcement learning [Bertsekas, 2019, Sutton and Barto, 1998] (bottom): Approximating a function over a topological space must satisfy the sheaf condition.

Figure <ref> gives two concrete examples of sheaves. In a minimum cost transportation problem, say using optimal transport [Villani, 2003] or reinforcement learning [Sutton and Barto, 1998], any optimal solution has the property that any restriction of the solution must also be optimal. In RL, this sheaf principle is codified by the Bellman equation, and leads to the fundamental principle of dynamic programming [Bertsekas, 2005]. Consider routing candy bars from San Francisco to New York city. If the cheapest way to route candy bars is through Chicago, then the restriction of the overall route to the (sub) route from Chicago to New York City must also be optimal, otherwise it is possible to find a shortest overall route by switching to a lower cost route. Similarly, in function approximation with real-valued functions $F: {\cal C} \rightarrow \mathbb{R}$, where ${\cal C}$ is the category of topological spaces, the (sub)functions $F(A), F(B)$ and $F(C)$ restricted to the open sets $A$, $B$ and $C$ must agree on the values they map the elements in the intersections $A \cap B$, $A \cap C$, $A \cap B \cap C$ and so on. Similarly, in causal inference, any probability distribution that is defined over a causal model must satisfy the sheaf condition in that any restriction of the causal model to a submodel must be consistent, so that two causal submodels that overlap in their domains must agree on the common elements.

Sheaves can be defined over arbitrary categories, and we introduce the main idea by focusing on the category of sheaves over Sets.

A sheaf of sets $F$ on a topological space $X$ is a functor $F: {\cal O}^{op} \rightarrow {\bf Sets} $ such that each open covering $U = \bigcup_i U_i, i \in I$ of an open set $O$ of $X$ yields an equalizer diagram

\[
\xymatrix{
\begin{tikzcd}
\prod_i FU_i \ar[r,shift left=.75ex,"p"]
\ar[r,shift right=.75ex,swap,"q"]
\prod_{i,} F(U_i \cap U_j)
\end{tikzcd}
\]

The above definition succinctly captures what Figure <ref> shows for the example of approximating functions: the value of each subfunction must be consistent over the shared elements in the intersection of each open set.

The category $\mbox{Sh}(X)$ of sheaves over a space $X$ is a full subcategory of the functor category ${\bf Sets}^{{\cal O}(X)^{op}}$.

§.§ Grothendieck Topologies

We can generalize the notion of sheaves to arbitrary categories using the Yoneda embedding $\yo(x) = {\cal C}(-, x)$. We explain this generalization in the context of a more abstract topology on categories called the Grothendieck topology defined by sieves. A sieve can be viewed as a subobject $S \subseteq \yo(x)$ in the presheaf ${\bf Sets}^{{\cal C}^{op}}$, but we can define it more elegantly as a family of morphisms in ${\cal C}$, all with codomain $x$ such that

\[ f \in S \Longrightarrow f \circ g \in S \]

Figure <ref> illustrates the idea of sieves. A simple way to think of a sieve is as a right ideal. We can define that more formally as follows:

If $S$ is a sieve on $x$, and $h: D \rightarrow x$ is any arrow in category ${\cal C}$, then

\[ h^* = \{g \ | \ \mbox{cod}(g) = D, hg \in S \}\]

Sieves are subobjects of of $\yo(x)$ Yoneda embeddings of a category ${\cal C}$, which generalizes the concept of sheaves over sets in Figure <ref>.

A Grothendieck topology on a category ${\cal C}$ is a function $J$ which assigns to each object $x$  of ${\cal C}$ a collection $J(x)$ of sieves on $x$ such that

* the maximum sieve $t_x = \{ f | \mbox{cod}(f) = x \}$ is in $J(x) $.

* If $S \in J(x)$  then $h^*(S) \in J(D)$ for any arrow $h: D \rightarrow x$.

* If $S \in J(x)$ and $R$ is any sieve on $x$, such that $h^*(R) \in J(D)$ for all $h: D \rightarrow x$, then $R \in J(C)$.

We can now define categories with a given Grothendieck topology as sites.

A site is defined as a pair $({\cal C}, J)$ consisting of a small category ${\cal C}$ and a Grothendieck topology $J$ on ${\cal C}$.

An intuitive way to interpret a site is as a generalization of the notion of a topology on a space $X$, which is defined as a set $X$ together with a collection of open sets ${\cal O}(X)$. The sieves on a category play the role of “open sets".

§.§ Exponential Objects and Cartesian Closed Categories

To define a topos, we need to understand the category of Sets a bit more. Clearly, the single point set $\{ \bullet \}$ is a terminal object for Sets, and the binary product of two sets $A \times B$ can always be defined. Furthermore, given two sets $A$ and $B$, we can define $B^A$ as the exponential object representing the set of all functions $f: A \rightarrow B$. We can define exponential objects in any category more generally as follows.

Given any category ${\cal C}$ with products, for a fixed object $x$ in ${\cal C}$, we can define the functor

\[ x \times - :  \rightarrow {\cal C}\]

If this functor has a right adjoint, which can be denoted as

\[ (-)^x: {\cal C} \rightarrow {\cal C} \]

then we say $x$ is an exponentiable object of ${\cal C}$.

A category ${\cal C}$ is Cartesian closed if it has finite products (which is equivalent to saying it has a terminal object and binary products) and if all objects in ${\cal C}$ are exponentiable.

A result that is of foundational importance to this paper is that the category defined by Yoneda embeddings is Cartesian closed.

For any small category ${\cal C}$, the functor category ${\bf Sets}^{{\cal C}^{op}}$ is Cartesian closed

For a detailed proof, the reader is referred to [MacLane and leke Moerdijk, 1994]. A further result of significance is the density theorem, which can be seen as the generalization of the simple result that any set $S$ can be defined as the union of single point sets $\bigcup_{x \in S} \{ x \}$.

In a functor category ${\bf Sets}^{{\cal C}^{op}}$, any object $x$ is the colimit of a diagram of representable objects in a canonical way.

Recall that an object is representable if it is isomorphic to a Yoneda embedding $\yo(x)$. This result has numerous applications to AI and ML, among them to causal inference [Mahadevan, 2023] and universal decision models [Mahadevan, 2021].

§.§ Subobject Classifiers

A topos builds on the property of subobject classifiers in Sets. Given any subset $S \subset X$, we can define $S$ as the monic arrow $S \hookrightarrow X$ defined by the inclusion of $S$ in $X$, or as the characteristic function $\phi_S$ that is equal to $1$ for all elements $x \in X$ that belong to $S$, and takes the value $0$ otherwise. We can define the set ${\bf 2} = \{0, 1 \}$ and treat true as the inclusion $\{1 \}$ in ${\bf 2}$. The characteristic function $\phi_S$ can then be defined as the pullback of true along $\phi_S$.

\[\begin{tikzcd}
S &&& {{\bf 1}} \\
\\
X &&& {{\bf 2}}
\arrow["m", tail, from=1-1, to=3-1]
\arrow[from=1-1, to=1-4]
\arrow["{{\bf true}}"{description}, tail, from=1-4, to=3-4]
\arrow["{\phi_S}"{description}, dashed, from=3-1, to=3-4]
\end{tikzcd}\]

We can now define subobject classifiers in a category ${\cal C}$ as follows.

In a category ${\cal C}$ with finite limits, a subobject classifier is a monic arrow ${\bf true}: {\bf 1} \rightarrow \Omega$, such that to every other monic arrow $S \hookrightarrow X$ in ${\cal C}$, there is a unique arrow $\phi$ that forms the following pullback square:

\[\begin{tikzcd}
S &&& {{\bf 1}} \\
\\
X &&& \Omega
\arrow["m", tail, from=1-1, to=3-1]
\arrow[from=1-1, to=1-4]
\arrow["{{\bf true}}"{description}, tail, from=1-4, to=3-4]
\arrow["{\phi}"{description}, dashed, from=3-1, to=3-4]
\end{tikzcd}\]

This definition can be rephrased as saying that the subobject functor is representable. In other words, a subobject of an object $x$ in a category ${\cal C}$ is an equivalence class of monic arrows $m: S \hookrightarrow  x$.

[MacLane and leke Moerdijk, 1994] provide many examples of subobject classifiers.  [Vigna, 2003] gives a detailed description of the topos of graphs.

§.§ Heyting Algebras

A truly remarkable finding is that the logic of topoi is not classical Boolean logic, but intuitionistic logic defined by Heyting algebras.

A Heyting algebra is a poset with all finite products and coproducts, which is Cartesian closed. That is, a Heyting algebra is a lattice with ${\bf 0}$ and ${\bf 1}$ which has to each pair of elements $x$ and $y$ an exponential $y^x$. The exponential is written $x \Rightarrow y$, and defined as the adjunction

\[ z \leq (x \Rightarrow y) \ \ \mbox{if and only if} \ \ z \wedge x \leq y\]

Alternatively, $x \Rightarrow y$ is a least upper bound for all those elements $z$ with $z \wedge x \leq y$. Therefore, for the particular case of $y$, we get that $y \leq (x \Rightarrow y)$. In the figure below, the arrows show the partial ordering relationship. As a concrete example, for a topological space $X$ the set of open setx ${\cal O}(X)$ is a Heyting algebra. The binary intersections and unions of open sets yield open sets. The empty set $\emptyset$ represents ${\bf 0}$ and the complete set $X$ represents ${\bf 1}$. Given any two open sets $U$ and $V$, the exponential object $U \Rightarrow W$ is defined as the union $\bigcup_i W_i$ of all open sets $W_i$ for which $W \cap U \subset V$.

\[\begin{tikzcd}
&&& {x \Rightarrow y} \\
x && y \\
& {x \wedge y}
\arrow[from=3-2, to=2-3]
\arrow[from=2-3, to=1-4]
\arrow[from=3-2, to=2-1]
\end{tikzcd}\]

Note that in a Boolean algebra, we define implication as the relationship

\[ (x \Rightarrow y) \equiv \neg x \vee y \]

This property, which is sometimes referred to as the “law of the excluded middle" (because if $x = y$, then this translates to $\neg x \vee x = {\bf true}$), does not hold in a Heyting algebra. For example, on a real line $\mathbb{R}$, if we define the open sets by the open intervals $(a, b), a, b \in \mathbb{R}$, the complement of an open set need not be open.

We can now state what is a truly remarkable result about the subobjects of a (pre)sheaf.

For any functor category $\hat{C} = {\bf Sets}^{{\cal C}^{op}}$ of a small category ${\cal C}$, the partially ordered set $\mbox{Sub}_{\hat{C}}(x)$ of subobjects of $x$, for any object $x$ of $\hat{C}$ is a Heyting algebra.

This result has deep implications for a lot of applications in AI and ML that are based modeling presheaves, including causal inference and decision making. It implies that the proper logic to employ in these settings is intuitionistic logic, not classical logic as is often used in AI [Pearl, 2009, Fagin et al., 1995, Halpern, 2016].

Finally, we can now define the category of topoi.