# Kan Extensions in Data Science and Machine Learning

Dan Shiebler<EMAIL_ADDRESS>Kellogg College, University of
OxfordUnited Kingdom

(2022)

###### Abstract.

A common problem in data science is “use this function defined over this small
set to generate predictions over that larger set.” Extrapolation,
interpolation, statistical inference and forecasting all reduce to this
problem. The Kan extension is a powerful tool in category theory that
generalizes this notion. In this work we explore several applications of Kan
extensions to data science. We begin by deriving a simple classification
algorithm as a Kan extension and experimenting with this algorithm on real
data. Next, we use the Kan extension to derive a procedure for learning
clustering algorithms from labels and explore the performance of this
procedure on real data. We then investigate how Kan extensions can be used to
learn a general mapping from datasets of labeled examples to functions and to
approximate a complex function with a simpler one.

Kan Extension, Data Science, Machine Learning, Generalization, Extrapolation

††copyright: none††journalyear: 2022††conference: …; …; …††booktitle: …

##  1\. Introduction

A popular slogan in category theoretic circles, popularized by Saunders Mac
Lane, is: “all concepts are Kan extensions” (Mac Lane, 1971). While Mac Lane
was partially referring to the fundamental way in which many elementary
category theoretic structures (e.g. limits, adjoint functors, initial/terminal
objects) can be formulated as Kan extensions, there are many applied areas
that have Kan extension structure lying beneath the surface as well.

One such area is data science/machine learning. It is quite common in data
science to apply a model constructed from one dataset to another dataset. In
this work we explore this structure through several applications.

Our contributions in this paper are as follows:

  * •

We derive a simple classification algorithm as a Kan extension and demonstrate
experimentally that this algorithm can learn to classify images.

  * •

We use Kan extensions to derive a novel method for learning a clustering
algorithm from labeled data and demonstrate experimentally that this method
can learn to cluster images.

  * •

We explore the structure of meta-supervised learning and use Kan extensions to
derive supervised learning algorithms from sets of labeled datasets and
trained functions.

  * •

We use Kan extensions to characterize the process of approximating a complex
function with a simpler minimum description length (MDL) function.

The code that we use in this paper be found at:

https://anonymous.4open.science/r/Kan_Extensions-4C21/.

###  1.1. Related Work

While many authors have explored how an applied category theoretic perspective
can help exploit structure and invariance in machine learning (Shiebler et
al., 2021), relatively few authors have explored applications of Kan
extensions to data science and machine learning.

That said, some authors have begun to explore Kan extension structure in
topological data analysis. For example, Bubenik et al. (Bubenik et al., 2017)
describe how three mechanisms for interpolating between persistence modules
can be characterized as the left Kan extension, right Kan extension, and
natural map from left to right Kan extension. Similarly, McCleary et. al.
(McCleary and Patel, 2021) use Kan extensions to characterize deformations of
filtrations. Furthermore, Botnan et. al. (Botnan and Lesnick, 2018) use Kan
extensions to generalize stability results from block decomposable persistence
modules to zigzag persistence modules and Curry (Curry, 2013) use Kan
extensions to characterize persistent structures from the perspective of sheaf
theory.

Other authors have explored the application of Kan extensions to databases.
For example, in categorical formulations of relational database theory (Spivak
and Wisnesky, 2015; Schultz and Wisnesky, 2017; Schultz et al., 2016), the
left Kan extension can be used for data migration. Spivak et. al. (Spivak and
Wisnesky, 2020) exploit the characterization of data migrations as Kan
extensions to apply the chase algorithm from relational database theory to the
general computation of the left Kan extension.

Outside of data science, many authors have applied Kan extensions to the study
of programs. For example, Hinze et. al. (Hinze, 2012) use Kan extensions to
express the process of optimizing a program by converting it to a
continuation-passing style. Similarly, Yonofsky (Yanofsky, 2013) uses Kan
extensions to reason about the output of programs expressed in a categorical
programming language. Many authors have also used Kan extensions to reason
about operations on the category of Haskell types and functions (Paterson,
2012).

###  1.2. Background on Kan extensions

In this work we assume readers have a basic familiarity with category theory.
For a detailed introduction to the field check out “Basic Category Theory”
(Leinster, 2016) or “Seven Sketches in Compositionality” (Fong and Spivak,
2019).

Suppose we have three categories $\mathbf{A},\mathbf{B},\mathbf{C}$ and two
functors $G:\mathbf{A}\rightarrow\mathbf{B},K:\mathbf{A}\rightarrow\mathbf{C}$
and we would like to derive the “best” functor
$F:\mathbf{B}\rightarrow\mathbf{C}$. There are two canonical ways that we can
do this:

###### Definition 1.1.

The left Kan extension of $K$ along $G$ is the universal pair of the functor
$Lan_{G}K:\mathbf{B}\rightarrow\mathbf{C}$ and natural transformation
$\mu:K\rightarrow(Lan_{G}K\circ G)$ such that for any pair of a functor
$M:\mathbf{B}\rightarrow\mathbf{C}$ and natural transformation
$\lambda:K\rightarrow(M\circ G)$ there exists a unique natural transformation
$\sigma:Lan_{G}K\rightarrow M$ such that $\lambda=\sigma_{G}\circ\mu$ (where
$\sigma_{G}(a)=\sigma(Ga)$).

###### Definition 1.2.

The right Kan extension of $K$ along $G$ is the universal pair of the functor
$Ran_{G}K:\mathbf{B}\rightarrow\mathbf{C}$ and natural transformation
$\mu:(Ran_{G}K\circ G)\rightarrow K$ such that for any pair of a functor
$M:\mathbf{B}\rightarrow\mathbf{C}$ and natural transformation
$\lambda:(M\circ G)\rightarrow K$ there exists a unique natural transformation
$\sigma:M\rightarrow Ran_{G}K$ such that $\lambda=\mu\circ\sigma_{G}$ (where
$\sigma_{G}(a)=\sigma(Ga)$).

${\mathbf{B}}$${\mathbf{A}}$${\mathbf{C}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

Intuitively, if we treat $G$ as an inclusion of $\mathbf{A}$ into $\mathbf{B}$
then the Kan extensions of $K$ along $G$ act as extrapolations of $K$ from
$\mathbf{A}$ to all of $\mathbf{B}$. If $\mathbf{C}$ is a preorder then the
left and right Kan extensions respectively behave as the least upper bound and
greatest lower bounds of $K$.

For example, suppose we want to interpolate a monotonic function
$K:\mathbb{Z}\rightarrow\mathbb{R}$ to a monotonic function
$F:\mathbb{R}\rightarrow\mathbb{R}$ such that $F\circ G=K$ where
$G:\mathbb{Z}\hookrightarrow\mathbb{R}$ is the inclusion map (morphisms in
$\mathbb{Z},\mathbb{R}$ are $\leq$):

${\mathbb{R}}$${\mathbb{Z}}$${\mathbb{R}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

We have that $Lan_{G}K:\mathbb{R}\rightarrow\mathbb{R}$ is simply $K\circ
floor$ and $Ran_{G}K:\mathbb{R}\rightarrow\mathbb{R}$ is simply $K\circ ceil$,
where $floor,ceil$ are the rounding down and rounding up functions
respectively.

##  2\. Applications of Kan Extensions

To start, recall the definitions of the left and right Kan extensions from
Section 1.2. We will explore four applications of Kan extensions to
generalization in machine learning:

  * •

Section 3: Learn a classifier from a dataset of labeled examples.

  * •

Section 4: Learn a mapping from metric spaces $(X,d_{X})$ to partitions of
$X$.

  * •

Section 5: Learn a mapping from datasets of labeled examples to functions.

  * •

Section 6: Approximate a complex function with a simpler one.

In each of these applications we first define categories
$\mathbf{A},\mathbf{B},\mathbf{C}$ and a functor
$K:\mathbf{A}\rightarrow\mathbf{C}$ such that $\mathbf{A}$ is a subcategory of
$\mathbf{B}$ and $G:\mathbf{A}\hookrightarrow\mathbf{B}$ is the inclusion
functor. Then, we take the left and right Kan extensions $Lan_{G}K,Ran_{G}K$
of $K$ along $G$ and study their behavior. Intuitively, the more restrictive
that $\mathbf{B}$ is (i.e. the more morphisms in $\mathbf{B}$) or the larger
that $\mathbf{A}$ is (and therefore the more information that is stored in
$K$) the more similar $Lan_{G}K,Ran_{G}K$ will be to each other.

##  3\. Classification

We start with a simple application of Kan extensions to supervised learning.
Suppose that $\mathbf{I}$ is a preorder,
$\mathbf{I}^{\prime}\subseteq\mathbf{I}$ is a subposet of $\mathbf{I}$,
$K:\mathbf{I}^{\prime}\rightarrow\\{\text{false},\text{true}\\}$ is a not-
necessarily monotonic mapping, and we would like to learn a monotonic function
$\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}$ that approximates $K$ on
$\mathbf{I}^{\prime}$. That is, $K$ defines a finite training set of points
$S=\\{(x,K(x))\ |\ x\in\mathbf{I}^{\prime}\\}$ from which we wish to learn a
monotonic function $F:\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}$. Of
course, it may not be possible to find a monotonic function that agrees with
$K$ on all the points in $\mathbf{I}^{\prime}$.

${\mathbf{I}}$${\mathbf{I}^{\prime}}$${\\{\text{false},\text{true}\\}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

If we treat $\mathbf{I}^{\prime}$ as discrete category, then $K$ is a functor
and we can solve this problem with the left and right Kan extensions of $K$
along the inclusion functor $G:\mathbf{I}^{\prime}\hookrightarrow\mathbf{I}$.

###### Proposition 3.1.

The left and right Kan extensions of
$K:\mathbf{I}^{\prime}\rightarrow\\{\text{false},\text{true}\\}$ along the
inclusion map $G:\mathbf{I}^{\prime}\hookrightarrow\mathbf{I}$ are
respectively:

$\displaystyle
Lan_{G}K:\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}\qquad
Ran_{G}K:\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}$ $\displaystyle
Lan_{G}K(x)=\begin{cases}\text{true}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq x,K(x^{\prime})=\text{true}\\\
\text{false}&\text{else}\end{cases}$ $\displaystyle
Ran_{G}K(x)=\begin{cases}\text{false}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},K(x^{\prime})=\text{false}\\\ \text{true}&\text{else}\end{cases}$

(Proof in Section 8.1)

In the extreme case that $Ob(\mathbf{I}^{\prime})=\emptyset$, for
$x\in\mathbf{I}$ we have that:

$\displaystyle Lan_{G}K(x)=$ $\displaystyle\begin{cases}\text{true}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq x,K(x^{\prime})=\text{true}\\\
\text{false}&\text{else}\end{cases}=\text{false}$

and:

$\displaystyle Ran_{G}K(x)=$ $\displaystyle\begin{cases}\text{false}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},K(x^{\prime})=\text{false}\\\
\text{true}&\text{else}\end{cases}=\text{true}$

Similarly, in the extreme case that $Ob(\mathbf{I}^{\prime})=Ob(\mathbf{I})$
we have by the functoriality of $K$ that for $x\in\mathbf{I}$ both of the
following hold if and only if $K(x)=\text{true}$.

$\displaystyle\exists x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x,K(x^{\prime})=\text{true}$ $\displaystyle\not\exists
x^{\prime}\in\mathbf{I}^{\prime},x\leq x^{\prime},K(x^{\prime})=\text{false}$

Therefore in this extreme case we have:

$\displaystyle Lan_{G}K(x)=Ran_{G}K(x)=K(x)$

Now suppose that $\mathbf{I}^{\prime}$ contains at least one $x^{\prime}$ such
that $K(x^{\prime})=\text{true}$ and at least one $x^{\prime}$ such that
$K(x^{\prime})=\text{false}$. In this case $Lan_{G}K$ and $Ran_{G}K$ split
$\mathbf{I}$ into three regions: a region where both map all points to false,
a region where both map all points to true, and a disagreement region. Note
that $Ran_{G}K$ has no false positives on $\mathbf{I}^{\prime}$ and $Lan_{G}K$
has no false negatives on $\mathbf{I}^{\prime}$.

For example, suppose $\mathbf{I}=\mathbb{R},\mathbf{I}^{\prime}=\\{1,2,3,4\\}$
and we have:

$\displaystyle K(1)=\text{false}\qquad K(2)=\text{false}$ $\displaystyle
K(3)=\text{true}\qquad K(4)=\text{true}$

Then we have that:

$\displaystyle Lan_{G}K(x)=$ $\displaystyle\begin{cases}\text{true}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq x,K(x^{\prime})=\text{true}\\\
\text{false}&\text{else}\end{cases}=$
$\displaystyle\begin{cases}\text{true}&x\geq 3\\\
\text{false}&\text{else}\end{cases}$

and that:

$\displaystyle Ran_{G}K(x)=$ $\displaystyle\begin{cases}\text{false}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},K(x^{\prime})=\text{false}\\\ \text{true}&\text{else}\end{cases}=$
$\displaystyle\begin{cases}\text{true}&x>2\\\
\text{false}&\text{else}\end{cases}$

In this case the disagreement region for $Lan_{G}K,Ran_{G}K$ is $(2,3)$ and
for any $x\in(2,3)$ we have $Lan_{G}K(x)<Ran_{G}K(x)$.

As another example, suppose
$\mathbf{I}=\mathbb{R},\mathbf{I}^{\prime}=\\{5,6,7,8\\}$ and we have:

$\displaystyle K(5)=\text{false}\qquad K(6)=\text{true}$ $\displaystyle
K(7)=\text{false}\qquad K(8)=\text{true}$

Then we have that:

$\displaystyle Lan_{G}K(x)=$ $\displaystyle\begin{cases}\text{true}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq x,K(x^{\prime})=\text{true}\\\
\text{false}&\text{else}\end{cases}=$
$\displaystyle\begin{cases}\text{true}&x\geq 6\\\
\text{false}&\text{else}\end{cases}$

and that:

$\displaystyle Ran_{G}K(x)=$ $\displaystyle\begin{cases}\text{false}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},K(x^{\prime})=\text{false}\\\ \text{true}&\text{else}\end{cases}=$
$\displaystyle\begin{cases}\text{true}&x>7\\\
\text{false}&\text{else}\end{cases}$

In this case the disagreement region for $Lan_{G}K,Ran_{G}K$ is $[6,7]$ and
for any $x\in[6,7]$ we have $Ran_{G}K(x)<Lan_{G}K(x)$.

While this approach is effective for learning very simple mappings, there are
many choices of $K$ for which $Lan_{G}K$ and $Ran_{G}K$ do not approximate $K$
particularly well on $\mathbf{I}^{\prime}$ and therefore the disagreement
region is large. In such a situation we can use a similar strategy to the one
leveraged by kernel methods (Hofmann et al., 2008) and transform $\mathbf{I}$
to minimize the size of the disagreement region.

That is, we choose a preorder $\mathbf{I}^{*}$ and transformation
$f:\mathbf{I}\rightarrow\mathbf{I}^{*}$ such that the size of the disagreement
region for $Lan_{f\circ G}K\circ f,Ran_{f\circ G}K\circ f$ is minimized.

${\mathbf{I}}$${\mathbf{I}^{*}}$${\mathbf{I}^{\prime}}$${\\{\text{false},\text{true}\\}}$$\scriptstyle{f}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

For example, if $\mathbf{I}^{*}=\mathbb{R}^{a}$ we can choose $f$ to minimize
the following loss:

###### Definition 3.2.

Suppose we have a set $\mathbf{I}^{\prime}\subseteq\mathbf{I}$ and function
$K:\mathbf{I}^{\prime}\rightarrow\\{\text{false},\text{true}\\}$ such that:

$\displaystyle\exists
x^{\prime},x^{\prime\prime}\in\mathbf{I}^{\prime},K(x^{\prime})=\text{true},K(x^{\prime\prime})=\text{false}$

Then the ordering loss $l$ maps a function
$f:\mathbf{I}\rightarrow\mathbb{R}^{a}$ to an approximation of the size of the
disagreement region for $Lan_{f\circ G}K\circ f,Ran_{f\circ G}K\circ f$.
Formally, we define the ordering loss $l$ to be:

$\displaystyle l:(\mathbf{I}\rightarrow\mathbb{R}^{a})\rightarrow\mathbb{R}$
$\displaystyle l(f)=\sum_{i\leq a}\max(0,\ \max\\{f(x)[i]\ |\
x\in\mathbf{I}^{\prime},K(x)=\text{false}\\}-$ $\displaystyle\min\\{f(x)[i]\
|\ x\in\mathbf{I}^{\prime},K(x)=\text{true}\\})$

where $f(x)[i]$ is the $i$th component of the vector
$f(x)[i]\in\mathbb{R}^{a}$.

We can show that minimizing the ordering loss $l$ will also minimize the size
of the disagreement region:

###### Proposition 3.3.

The ordering loss $l$ (Definition 3.2) is non-negative and is only equal to 0
when $\forall x\in\mathbf{I}^{\prime}$ we have:

$\displaystyle K(x)=(Lan_{f\circ G}K\circ f)(x)=(Ran_{f\circ G}K\circ f)(x)$

(Proof in Section 8.2)

It is relatively straightforward to minimize the ordering loss with an
optimizer like subgradient descent (Boyd and Vandenberghe, 2004).111Example
code at https://anonymous.4open.science/r/Kan_Extensions-4C21/.

In Table LABEL:fashionmnistclassification we demonstrate that we can use this
strategy to distinguish between the “T-shirt” (false) and “shirt” (true)
categories in the Fashion MNIST dataset (Xiao et al., 2017). Samples in this
dataset have $784$ features (pixels), so we train a simple linear model
$f:\mathbb{R}^{784}\rightarrow\mathbb{R}^{10}$ with Adam (Kingma and Ba, 2014)
to minimize the ordering loss $l(f)$ over a training set that contains $90\%$
of samples in the dataset. We then evaluate the performance of $Lan_{f\circ
G}K\circ f,Ran_{f\circ G}K\circ f$ over both this training set and a testing
set that contains the remaining $10\%$ of the dataset. We look at two metrics
over both sets.

###### Definition 3.4.

The true positive rate is the percentage of all true samples (shirts) which
the classifier correctly labels as true. This is also known as recall or
sensitivity. The true positive rate is $1.0$ if and only if there are no false
negatives.

###### Definition 3.5.

The true negative rate is the percentage of all false samples (T-shirts) which
the classifier correctly labels as false. This is also known as specificity.
The true negative rate is $1.0$ if and only if there are no false positives.

As we would expect from the definition of Kan extensions, the map $Lan_{f\circ
G}K\circ f$ has no false negatives and $Ran_{f\circ G}K\circ f$ has no false
positives on the training set. The metrics on the testing set are in-line with
our expectations as well: $Lan_{f\circ G}K\circ f$ has a higher true positive
rate and $Ran_{f\circ G}K\circ f$ has a higher true negative rate.

Model |  Dataset |  True Positive Rate |  True Negative Rate
---|---|---|---
Left Kan Classifier | Train | $1.000\ (\pm 0.000)$ | $0.612\ (\pm 0.042)$
Right Kan Classifier | Train | $0.705\ (\pm 0.035)$ | $1.000\ (\pm 0.000)$
Left Kan Classifier | Test | $0.815\ (\pm 0.020)$ | $0.593\ (\pm 0.044)$
Right Kan Classifier | Test | $0.691\ (\pm 0.044)$ | $0.837\ (\pm 0.026)$
Table 1. True positive rate and true negative rate of the left Kan classifier
$Lan_{f\circ G}K\circ f$ and the right Kan classifier $Ran_{f\circ G}K\circ f$
where $f$ is a linear map trained to minimize the ordering loss $l(f)$
(Definition 3.2) on the Fashion-MNIST “T-shirt” vs “shirt” task (Xiao et al.,
2017). We run a bootstrap experiment by repeatedly selecting $9000$ training
samples and $1000$ testing samples, running the training procedure, and
computing true positive rate and true negative rate metrics. Mean and two
standard error confidence bounds from $10$ such bootstrap iterations are
shown.

##  4\. Clustering with Supervision

Clustering algorithms allow us to group points in a dataset together based on
some notion of similarity between them. Formally, we can consider a clustering
algorithm as mapping a metric space $(X,d_{X})$ to a partition of $X$.

In most applications of clustering the points in the metric space $(X,d_{X})$
are grouped together based solely on the distances between the points and the
rules embedded within the clustering algorithm itself. This is an unsupervised
clustering strategy since no labels or supervision influence the algorithm
output. For example, agglomerative clustering algorithms like HDBSCAN (McInnes
and Healy, 2017) and single linkage partition points in $X$ based on graphs
formed from the points (vertices) and distances (edges) in $(X,d_{X})$.

However, there are some circumstances under which we have a few ground truth
examples of pre-clustered training datasets and want to learn an algorithm
that can cluster new data as similarly as possible to these ground truth
examples. We can define the supervised clustering problem as follows. Given a
collection of tuples

$\displaystyle
S=\\{(X_{1},d_{1},P_{1}),(X_{2},d_{2},P_{2}),\cdots,(X_{n},d_{n},P_{n})\\}$

where each $(X_{i},d_{i})$ is a metric space and $P_{i}$ is a partition of
$X_{i}$, we would like to learn a general function $f$ that maps a metric
space $(X,d_{X})$ to a partition $P_{X}$ of $X$ such that for each
$(X_{i},d_{i},P_{i})\in S$ the difference between $f(X_{i},d_{i})$ and $P_{i}$
is small.

We can frame this objective in terms of categories and functors by using the
functorial perspective on clustering algorithms (Culbertson and Sturtz, 2014;
Carlsson and Mémoli, 2013; Shiebler, 2020).

###### Definition 4.1.

In the category $\mathcal{\mathbf{Met}}$ objects are metric spaces and the
morphisms between $(X,d_{X})$ and $(Y,d_{Y})$ are non-expansive maps, or
functions $f:X\rightarrow Y$ such that:

$\displaystyle d_{Y}(f(x_{1}),f(x_{2}))\leq d_{X}(x_{1},x_{2}).$

###### Definition 4.2.

The objects in the category $\mathbf{Part}$ are tuples $(X,\mathcal{P}_{X})$
where $\mathcal{P}_{X}$ is a partition of the set $X$. The morphisms in
$\mathbf{Part}$ between $(X,\mathcal{P}_{X})$ and $(Y,\mathcal{P}_{Y})$ are
refinement-preserving maps, that is functions $f:X\rightarrow Y$ such that for
any $S_{X}\in\mathcal{P}_{X}$, there exists some $S_{Y}\in\mathcal{P}_{Y}$
with $f(S_{X})\subseteq S_{Y}$.

###### Definition 4.3.

Given a subcategory $\mathbf{D}$ of $\mathcal{\mathbf{Met}}$, a
$\mathbf{D}$-clustering functor is a functor
$F:\mathbf{D}\rightarrow\mathbf{Part}$ that is the identity on morphisms and
underlying sets.

That is, a $\mathbf{D}$-clustering functor commutes with the forgetful
functors from $\mathbf{D}$ and $\mathbf{Part}$ into $\mathbf{Set}$. An example
clustering functor is the $\delta$-single linkage clustering functor.

###### Definition 4.4.

The $\delta$-single linkage functor maps a metric space $(X,d_{X})$ to the
partition of $X$ in which the points $x_{1},x_{n}$ are in the same partition
if and only if there exists some sequence of points:

$\displaystyle x_{1},x_{2},...,x_{n-1},x_{n}$

such that for all $(x_{i},x_{i+1})$ in this sequence we have:

$\displaystyle d_{X}(x_{i},x_{i+1})\leq\delta$

In this section we will work with the restrictions of $\mathcal{\mathbf{Met}}$
and $\mathbf{Part}$ to the preorder subcategories in which morphisms are
limited to inclusion maps $\iota(x)=x$.

###### Definition 4.5.

$\mathcal{\mathbf{Met}}_{id}$ is the subcategory of $\mathcal{\mathbf{Met}}$
in which the morphisms between $(X,d_{X})$ and $(Y,d_{Y})$ are limited to
inclusion functions $\iota(x)=x$. $\mathcal{\mathbf{Met}}_{id}$ is a preorder
and we write:

$\displaystyle(X,d_{X})\leq_{\mathcal{\mathbf{Met}}_{id}}(Y,d_{Y})$

to indicate that $X\subseteq Y$ and that $\iota:(X,d_{X})\rightarrow(Y,d_{Y})$
is non-expansive.

Similarly, if $\mathbf{D}$ is a subcategory of $\mathcal{\mathbf{Met}}_{id}$
then we write

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(Y,d_{Y})$

to indicate that the inclusion map $\iota:(X,d_{X})\rightarrow(Y,d_{Y})$ is a
morphism in $\mathbf{D}$.

###### Definition 4.6.

$\mathbf{Part}_{id}$ is the subcategory of $\mathbf{Part}$ in which the
morphisms between $(X,\mathcal{P}_{X})$ and $(Y,\mathcal{P}_{Y})$ are limited
to inclusion functions $\iota(x)=x$. $\mathbf{Part}_{id}$ is a preorder and we
write:

$\displaystyle(X,\mathcal{P}_{X})\leq_{\mathbf{Part}_{id}}(Y,\mathcal{P}_{Y})$

to indicate that $X\subseteq Y$ and that
$\iota:(X,\mathcal{P}_{X})\rightarrow(Y,\mathcal{P}_{Y})$ is refinement-
preserving.

We can now frame our objective in terms of clustering functors. Suppose
$\iota:\mathbf{Part}_{id}\hookrightarrow\mathbf{Part}$ is the inclusion
functor. Then given a subcategory
$\mathbf{D}\subseteq\mathcal{\mathbf{Met}}_{id}$ (Definition 4.5), a discrete
subcategory $\mathbf{T}\subseteq\mathbf{D}$, and a functor
$K:\mathbf{T}\rightarrow\mathbf{Part}_{id}$ such that:

$\displaystyle\iota\circ K:\mathbf{T}\rightarrow\mathbf{Part}$

is a $\mathbf{T}$-clustering functor (Definition 4.3), find the best functor
$F:\mathbf{D}\rightarrow\mathbf{Part}_{id}$ such that:

$\displaystyle\iota\circ F:\mathbf{D}\rightarrow\mathbf{Part}$

is a $\mathbf{D}$-clustering functor and $F\circ G=K$ where
$G:\mathbf{T}\hookrightarrow\mathbf{D}$ is the inclusion functor.

${\mathbf{D}(\subseteq\mathcal{\mathbf{Met}}_{id})}$${\mathbf{T}(\subseteq\mathbf{D})}$${\mathbf{Part}_{id}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

Intuitively, $Ob(\mathbf{T})$ is the set of unlabelled training samples, $K$
defines the labels on these training samples, and $Ob(\mathbf{D})$ is the set
of testing samples.

We would like to use the Kan extensions of $K$ along $G$ to find this best
clustering functor. However, these Kan extensions are not guaranteed to be
clustering functors.

For example, consider the case in which $\mathbf{T}$ is the discrete category
that contains the single-element metric space as its only object and
$\mathbf{D}$ is the discrete category that contains two objects: the single-
element metric space and $\mathbb{R}$ equipped with the Euclidean distance
metric 222This counterexample due to Sam Staton.

${\\{(\\{*\\},d_{\\{*\\}}),(\mathbb{R},d_{\mathbb{R}})\\}}$${\\{(\\{*\\},d_{\\{*\\}})\\}}$${\mathbf{Part}_{id}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

Since $\mathbf{D}$ is a discrete category, the behavior of $K$ on
$(\\{*\\},d_{\\{*\\}})$ will not affect the behavior of the left and right Kan
extensions of $K$ along $G$ on $(\mathbb{R},d_{\mathbb{R}})$. The left Kan
extension of $K$ along $G$ will always map $(\mathbb{R},d_{\mathbb{R}})$ to
the initial object of $\mathbf{Part}_{id}$ (the empty set). That is, the left
Kan extension does not satisfy the conditions of Definition 4.3 since it does
not act as the identity on the underlying set $\mathbb{R}$. Futhermore, the
right Kan extension of $K$ along $G$ will not exist because
$\mathbf{Part}_{id}$ does not have a terminal object.

In order to solve this problem with Kan extensions we need to add a bit more
structure. Suppose $Ob(\mathbf{D})$ is the discrete category with the same
objects as $\mathbf{D}$ and define the following:

###### Definition 4.7.

The functor $K_{L}:Ob(\mathbf{D})\rightarrow\mathbf{Part}_{id}$ is equal to
$K$ on $\mathbf{T}$ and maps each object $(X,d_{X})$ in
$Ob(\mathbf{D})-Ob(\mathbf{T})$ to $(X,\\{\\{x\\}\ |\ x\in X\\})$.

###### Definition 4.8.

The functor $K_{R}:Ob(\mathbf{D})\rightarrow\mathbf{Part}_{id}$ is equal to
$K$ on $\mathbf{T}$ and maps each object $(X,d_{X})$ in
$Ob(\mathbf{D})-Ob(\mathbf{T})$ to $(X,\\{X\\})$.

Intuitively, $K_{L}$ and $K_{R}$ are extensions of $K$ to all of the objects
in $\mathbf{D}$. For any metric space $(X,d_{X})$ not in $Ob(\mathbf{T})$ the
functor $K_{L}$ maps $(X,d_{X})$ to the finest possible partition of $X$ and
$K_{R}$ maps $(X,d_{X})$ to the coarsest possible partition of $X$.

Suppose we go back to the previous example in which $\mathbf{T}$ is the
discrete category containing only the single-element metric space and
$\mathbf{D}$ is the discrete category containing both the single-element
metric space and $(\mathbb{R},d_{\mathbb{R}})$. Since:

$\displaystyle K_{L}(\mathbb{R},d_{\mathbb{R}})=(\mathbb{R},\\{\\{x\\}\ |\
x\in\mathbb{R}\\})$

the left Kan extension of $K_{L}$ along the inclusion

$\displaystyle G:Ob(\mathbf{D})\hookrightarrow\mathbf{D}$

must map $(\mathbb{R},d_{\mathbb{R}})$ to the
$\leq_{\mathbf{Part}_{id}}$-smallest $(X,\mathcal{P}_{X})$ such that:

$\displaystyle(\mathbb{R},\\{\\{x\\}\ |\
x\in\mathbb{R}\\})\leq_{\mathbf{Part}_{id}}(X,\mathcal{P}_{X})$

which is $(X,\mathcal{P}_{X})=(\mathbb{R},\\{\\{x\\}\ |\ x\in\mathbb{R}\\})$.
Similarly, since:

$\displaystyle K_{R}(\mathbb{R},d_{\mathbb{R}})=(\mathbb{R},\\{\mathbb{R}\\})$

the right Kan extension of $K_{R}$ along the inclusion

$\displaystyle G:Ob(\mathbf{D})\hookrightarrow\mathbf{D}$

must map $(\mathbb{R},d_{\mathbb{R}})$ to the
$\leq_{\mathbf{Part}_{id}}$-largest $(X,\mathcal{P}_{X})$ such that:

$\displaystyle(X,\mathcal{P}_{X})\leq_{\mathbf{Part}_{id}}(\mathbb{R},\\{\mathbb{R}\\})$

which is $(X,\mathcal{P}_{X})=(\mathbb{R},\\{\mathbb{R}\\})$. We can apply the
same logic to the behavior of the Kan extensions on the single-element metric
space as well, so the composition of

$\displaystyle\iota:\mathbf{Part}_{id}\hookrightarrow\mathbf{Part}$

to either Kan extension yields a $\mathbf{D}$-clustering functor.

We can now build on this perspective to construct our optimal clustering
functor extensions of $K$.

###### Proposition 4.9.

Consider the map $Lan_{G}K_{L}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$ that
acts as the identity on morphisms and sends the metric space $(X,d_{X})$ to
the partition of $X$ defined by the transitive closure of the relation $R$
where for $x_{1},x_{2}\in X$ we have $x_{1}Rx_{2}$ if and only if there exists
some metric space $(X^{\prime},d_{X^{\prime}})\in\mathbf{T}$ where:

$\displaystyle(X^{\prime},d_{X^{\prime}})\leq_{\mathbf{D}}(X,d_{X})$

and $x_{1},x_{2}$ are in the same cluster in $K(X^{\prime},d_{X^{\prime}})$.
The map:

$\displaystyle\iota\circ Lan_{G}K_{L}:\mathbf{D}\rightarrow\mathbf{Part}$

is a $\mathbf{D}$-clustering functor. (Proof in Section 8.3)

###### Proposition 4.10.

Consider the map $Ran_{G}K_{R}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$ that
acts as the identity on morphisms and sends the metric space $(X,d_{X})$ to
the partition of $X$ defined by the transitive closure of the relation $R$
where for $x_{1},x_{2}\in X$ we have $x_{1}Rx_{2}$ if and only if there exists
no metric space $(X^{\prime},d_{X^{\prime}})\in\mathbf{T}$ where:

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(X^{\prime},d_{X^{\prime}})$

and $x_{1},x_{2}$ are in different clusters in $K(X^{\prime},d_{X^{\prime}})$.
The map:

$\displaystyle\iota\circ Ran_{G}K_{R}:\mathbf{D}\rightarrow\mathbf{Part}$

is a $\mathbf{D}$-clustering functor. (Proof in Section 8.4)

We can also make the following claim:

###### Proposition 4.11.

Suppose there exists some functor $F:\mathbf{D}\rightarrow\mathbf{Part}_{id}$
such that

$\displaystyle\iota\circ F:\mathbf{D}\rightarrow\mathbf{Part}$

is a $\mathbf{D}$-clustering functor and $F\circ G=K$. Then for
$(X,d_{X})\in\mathbf{T}$ we have that:

$\displaystyle F(X,d_{X})=$ $\displaystyle K(X,d_{X})=$ $\displaystyle
Lan_{G}K_{L}(X,d_{X})=$ $\displaystyle Ran_{G}K_{R}(X,d_{X})$

(Proof in Section 8.5)

We can now put everything together and construct the functors
$Lan_{G}K_{L},Ran_{G}K_{R}$ as Kan extensions.

###### Proposition 4.12.

Suppose there exists some functor $F:\mathbf{D}\rightarrow\mathbf{Part}_{id}$
such that

$\displaystyle\iota\circ F:\mathbf{D}\rightarrow\mathbf{Part}$

is a $\mathbf{D}$-clustering functor and $F\circ G=K$.

Then $Lan_{G}K_{L}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$ (Proposition 4.9)
is the left Kan extension of
$K_{L}:Ob(\mathbf{D})\rightarrow\mathbf{Part}_{id}$ along the inclusion
functor $G:Ob(\mathbf{D})\hookrightarrow\mathbf{D}$.

${\mathbf{D}(\subseteq\mathcal{\mathbf{Met}}_{id})}$${Ob(\mathbf{D})}$${\mathbf{Part}_{id}}$$\scriptstyle{Lan_{G}K_{L}}$$\scriptstyle{G}$$\scriptstyle{K_{L}}$

In addition $Ran_{G}K_{R}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$
(Proposition 4.10) is the right Kan extension of
$K_{R}:Ob(\mathbf{D})\rightarrow\mathbf{Part}_{id}$ along the inclusion
functor $G:Ob(\mathbf{D})\hookrightarrow\mathbf{D}$.

${\mathbf{D}(\subseteq\mathcal{\mathbf{Met}}_{id})}$${Ob(\mathbf{D})}$${\mathbf{Part}_{id}}$$\scriptstyle{Ran_{G}K_{R}}$$\scriptstyle{G}$$\scriptstyle{K_{R}}$

(Proof in Section 8.6)

Note that when $Ob(\mathbf{T})=\emptyset$ we have for any $(X,d_{X})\in
Ob(\mathbf{D})$ that:

$\displaystyle Lan_{G}K_{L}(X,d_{X})=K_{L}(X,d_{X})=(X,\\{\\{x\\}\ |\ x\in
X\\})$ $\displaystyle Ran_{G}K_{R}(X,d_{X})=K_{R}(X,d_{X})=(X,\\{\\{X\\}\\})$

In general for any metric space $(X,d_{X})\in Ob(\mathbf{D})-Ob(\mathbf{T})$
the functors $Lan_{G}K_{L},Ran_{G}K_{R}$ respectively map $(X,d_{X})$ to the
finest (most clusters) and coarsest (fewest clusters) partitions of $X$ such
that for any metric space $(X^{\prime},d_{X^{\prime}})\in\mathbf{T}$ we have:

$\displaystyle
K(X^{\prime},d_{X^{\prime}})=Lan_{G}K_{L}(X^{\prime},d_{X^{\prime}})=Ran_{G}K_{R}(X^{\prime},d_{X^{\prime}})$

and $Lan_{G}K_{L},Ran_{G}K_{R}$ are functors. For example, suppose we have a
metric space $(X,d_{X})$ where $X=\\{x_{1},x_{2},x_{3}\\}$. We can form the
subcategories
$\mathbf{T}\subseteq\mathbf{D}\subseteq\mathcal{\mathbf{Met}}_{id}$ where:

$\displaystyle
Ob(\mathbf{T})=\\{(\\{x_{1},x_{2}\\},d_{X}),(\\{x_{1},x_{3}\\},d_{X}),(\\{x_{2},x_{3}\\},d_{X})\\}$
$\displaystyle
Ob(\mathbf{D})=Ob(\mathbf{T})\cup(\\{x_{1},x_{2},x_{3}\\},d_{X})$

$\mathbf{T}$ is a discrete category and the only non-identity morphisms in
$\mathbf{D}$ are the inclusions
$\\{x_{i},x_{j}\\}\hookrightarrow\\{x_{1},x_{2},x_{3}\\}$. Now define
$K:\mathbf{T}\rightarrow\mathbf{Part}_{id}$ to be the following functor:

$\displaystyle K(\\{x_{1},x_{2}\\},d_{X})=\\{\\{x_{1},x_{2}\\}\\}$
$\displaystyle K(\\{x_{1},x_{3}\\},d_{X})=\\{\\{x_{1}\\},\\{x_{3}\\}\\}$
$\displaystyle K(\\{x_{2},x_{3}\\},d_{X})=\\{\\{x_{2}\\},\\{x_{3}\\}\\}$

In this case we have that:

$\displaystyle
K_{L}(\\{x_{1},x_{2},x_{3}\\},d_{X})=\\{\\{x_{1}\\},\\{x_{2}\\},\\{x_{3}\\}\\}$
$\displaystyle
K_{R}(\\{x_{1},x_{2},x_{3}\\},d_{X})=\\{\\{x_{1},x_{2},x_{3}\\}\\}$

Since the only points that need to be put together are $x_{1},x_{2}$ and there
are no non-identity morphisms out of $\\{x_{1},x_{2},x_{3}\\}$ in
$\mathbf{D}$, we have:

$\displaystyle
Lan_{G}K_{L}(\\{x_{1},x_{2},x_{3}\\},d_{X})=\\{\\{x_{1},x_{2}\\},\\{x_{3}\\}\\}$
$\displaystyle
Ran_{G}K_{R}(\\{x_{1},x_{2},x_{3}\\},d_{X})=\\{\\{x_{1},x_{2},x_{3}\\}\\}$

As another example, suppose $\mathbf{D}$ is $\mathcal{\mathbf{Met}}_{id}$ and
$\mathbf{T}$ is the discrete subcategory of $\mathbf{D}$ whose objects are all
metric spaces with $\leq 2$ elements. Define the following
$\mathbf{T}$-clustering functor:

$\displaystyle
K(\\{x_{1},x_{2}\\},d)=\begin{cases}\\{\\{x_{1},x_{2}\\}\\}&d(x_{1},x_{2})\leq\delta\\\
\\{\\{x_{1}\\},\\{x_{2}\\}\\}&\text{else}\end{cases}$

Now for some metric space $(X,d_{X})$ with $|X|>2$ and points $x_{1},x_{2}\in
X$ we have that $Lan_{G}K_{L}$ maps $x_{1},x_{2}$ to the same cluster if and
only if there exists some chain of points $x_{1},\cdots,x_{2}$ in $X$ where
for each pair of adjacent points $x^{\prime}_{1},x^{\prime}_{2}$ in this chain
and any metric space
$(\\{x^{\prime}_{1},x^{\prime}_{2}\\},d_{X^{\prime}})\in\mathbf{D}$ equipped
with a non-expansive inclusion map:

$\displaystyle\iota:(\\{x^{\prime}_{1},x^{\prime}_{2}\\},d_{X^{\prime}})\hookrightarrow(X,d_{X})$

in $\mathbf{D}$, it must be that the points $x^{\prime}_{1},x^{\prime}_{2}$
are in the same cluster in
$K(\\{x^{\prime}_{1},x^{\prime}_{2}\\},d_{X^{\prime}})$. This is the case if
and only if:

$\displaystyle d_{X}(x^{\prime}_{1},x^{\prime}_{2})\leq\delta$

. Therefore, $Lan_{G}K_{L}$ maps $x_{1},x_{2}$ to the same cluster if and only
if $x_{1},x_{2}$ are in the same connected component of the $\delta$-Vietoris
Rips complex of $(X,d_{X})$. $Lan_{G}K_{L}$ is therefore the $\delta$-single
linkage functor (Definition 4.4).

In contrast, since $|X|>2$ there are no morphisms in $\mathbf{D}$ from
$(X,d_{X})$ to any metric spaces in $\mathbf{T}$. Therefore:

$\displaystyle Ran_{G}K_{R}(X,d_{X})=(X,\\{X\\})$

Figure 1.  Cluster assignments of a $100$ point testing set $X_{te}$ from the
Fashion MNIST dataset (Xiao et al., 2017) shown in UMAP space (McInnes et al.,
2018). Each color corresponds to a unique cluster, and points without clusters
are shown as black squares. We show ground truth clothing categories,
unsupervised $\delta$-single linkage cluster assignments ($\delta$ chosen via
line search), and the $Lan_{G}K_{L},Ran_{G}K_{R}$ supervised cluster
assignments. The $Lan_{G}K_{L},Ran_{G}K_{R}$ algorithms are trained on a
separate $10,000$ point random sample $X_{tr}$ from the Fashion MNIST dataset.

We can use this strategy to learn a clustering algorithm from real-world data.
Recall that the Fashion MNIST dataset (Xiao et al., 2017) contains images of
clothing and the categories that each image falls into. Suppose that we have
two subsets of this dataset: a training set $X_{tr}$ in which images are
grouped by category and a testing set $X_{te}$ of ungrouped images. We can use
UMAP (McInnes et al., 2018) to construct metric spaces $(X_{tr},d_{X_{tr}})$
and $(X_{te},d_{X_{te}})$ from these sets.

Now suppose we would like to group the images in $X_{te}$ as similarly as
possible to the grouping of the images in $X_{tr}$.

For any category $\mathbf{D}^{*}\subseteq\mathcal{\mathbf{Met}}$ with:

$\displaystyle
Ob(\mathbf{D}^{*})=\\{(X_{tr},d_{X_{tr}}),(X_{te},d_{X_{te}})\\}$

we can define subcategories
$\mathbf{T}\subseteq\mathbf{D}\subseteq\mathcal{\mathbf{Met}}_{id}$ and
functor $K:\mathbf{T}\rightarrow\mathbf{Part}_{id}$ as follows:

  1. (1)

Initialize $\mathbf{T}$ to an empty category and $\mathbf{D}$ to be the
discrete category with a single object $\\{(X_{te},d_{X_{te}})\\}$.

  2. (2)

For every morphism

$\displaystyle f:(X_{tr},d_{X_{tr}})\rightarrow(X_{te},d_{X_{te}})$

in $\mathbf{D}^{*}$ and pair $(x_{1},x_{2})\in X_{tr}$ of samples in the same
clothing category, add the object $(\\{f(x_{1}),f(x_{2})\\},d_{X_{te}})$ to
$\mathbf{T}$ and $\mathbf{D}$, add the inclusion morphism:

$\displaystyle\iota:(\\{f(x_{1}),f(x_{2})\\},d_{X_{te}})\hookrightarrow(X_{te},d_{X_{te}})$

to $\mathbf{D}$, and define $K(\\{f(x_{1}),f(x_{2})\\},d_{X_{te}})$ to map
$f(x_{1})$ and $f(x_{2})$ to the same cluster.

  3. (3)

For every morphism

$\displaystyle f:(X_{te},d_{X_{te}})\rightarrow(X_{tr},d_{X_{tr}})$

in $\mathbf{D}^{*}$ define a metric space
$(X^{\prime}_{te},d_{X^{\prime}_{te}})$ where $X_{te}=X^{\prime}_{te}$ and
$d_{X_{te}}=d_{X^{\prime}_{te}}$. Add the object
$(X^{\prime}_{te},d_{X^{\prime}_{te}})$ to $\mathbf{T}$ and $\mathbf{D}$, add
the inclusion map

$\displaystyle\iota:(X_{te},d_{X_{te}})\hookrightarrow(X^{\prime}_{te},d_{X^{\prime}_{te}})$

to $\mathbf{D}$ and define $K(X^{\prime}_{te},d_{X^{\prime}_{te}})$ to be the
partition of $X^{\prime}_{te}$ defined by the preimages of the function
$(h\circ f)$ where $h$ maps each element of $X_{tr}$ to the category of
clothing it belongs to.

We can now use $Lan_{G}K_{L}$ and $Ran_{G}K_{R}$ to partition $X_{te}$. In
Figure 1 we compare the clusterings produced by $Lan_{G}K_{L}$ and
$Ran_{G}K_{R}$ to the ground truth clothing categories. We can compare
clustering performance with the following metric:

###### Definition 4.13.

The Rand score (Rand, 1971; Pedregosa et al., 2011) between the partitions
$\mathcal{P}_{X},\mathcal{P}_{X}^{\prime}$ of the set $X$ is the ratio:

$\displaystyle
RI(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})=\frac{|both(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})|+|neither(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})|}{|X|^{2}}$

where:

$\displaystyle both(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})=$
$\displaystyle\\{x_{i},x_{j}\ |\ \exists
s_{X}\in\mathcal{P}_{X},x_{i},x_{j}\in s_{X}\wedge\exists
s^{\prime}_{X}\in\mathcal{P}_{X}^{\prime},x_{i},x_{j}\in s^{\prime}_{X}\\}$
$\displaystyle neither(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})=$
$\displaystyle\\{x_{i},x_{j}\ |\ \not\exists
s_{X}\in\mathcal{P}_{X},x_{i},x_{j}\in s_{X}\wedge\not\exists
s^{\prime}_{X}\in\mathcal{P}_{X}^{\prime},x_{i},x_{j}\in s^{\prime}_{X}\\}$

The value of the Rand score is heavily dependent on the number of clusters,
which can make it difficult to interpret. Therefore, in practice we usually
work with a chance-adjusted variant of the Rand score that is close to $0$ for
a random partition and is exactly $1$ for identical partitions.

###### Definition 4.14.

Suppose $\mathbf{P}^{2}_{X}$ is the set of all pairs of partitions of the set
$X$ and $\mu_{\mathbf{P}^{2}_{X}}$ is the uniform distribution over
$\mathbf{P}^{2}_{X}$. Then the adjusted Rand score (Hubert and Arabie, 1985;
Pedregosa et al., 2011) between the partitions
$\mathcal{P}_{X},\mathcal{P}_{X}^{\prime}$ of the set $X$ is the ratio:

$\displaystyle
ARI(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})=\frac{RI(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})-E_{\mu_{\mathbf{P}^{2}_{X}}}[RI]}{\max_{\mathbf{P}^{2}_{X}}(RI)-E_{\mu_{\mathbf{P}^{2}_{X}}}[RI]}$

where $RI(\mathcal{P}_{X},\mathcal{P}_{X}^{\prime})$ is the Rand score between
the partitions $\mathcal{P}_{X},\mathcal{P}_{X}^{\prime}$ (Definition 4.13).

As a baseline we compute the $\delta$-single linkage clustering algorithm
(Definition 4.4) with $\delta$ chosen via line search to maximize the adjusted
Rand score (Definition 4.14) with the ground truth labels. As expected, we see
that $Lan_{G}K_{L}$ produces a finer clustering (more clusters) than does
$Ran_{G}K_{R}$ and that the clusterings produced by $Lan_{G}K_{L}$ and
$Ran_{G}K_{R}$ are better than the clustering produced by single linkage in
the sense of adjusted Rand score with ground truth.

##  5\. Meta-Supervised Learning

Suppose $I$ is a set and $O$ is a partial order. A supervised learning
algorithm maps a labeled dataset (set of pairs of points in $I\times O$) to a
function $f:I\rightarrow O$. For example, both $Lan_{G}K$ and $Ran_{G}K$ from
Section 3 are supervised learning algorithms.

In this Section we use Kan extensions to derive supervised learning algorithms
from pairs of datasets and functions. Our construction combines elements of
Section 3’s point-level algorithms and Section 4’s dataset-level functoriality
constraints.

Suppose we have a finite partial order $S_{f}\subseteq(I\rightarrow O)$ of
functions where for $f,f^{\prime}\in S_{f}$ we have $f\leq f^{\prime}$ when
$\forall x\in I,f(x)\leq f^{\prime}(x)$.

###### Proposition 5.1.

For any subset $S^{*}_{f}\subseteq S_{f}$ the upper antichain of $S^{*}_{f}$
is the set:

$\displaystyle\\{f\ |\ f\in S^{*}_{f},\ \not\exists f^{*}\in
S^{*}_{f},f<f^{*}\\}\\}$

The upper antichain of $S^{*}_{f}$ is an antichain in $S^{*}_{f}$, and for any
function $f\in S^{*}_{f}$ there exists some function $f^{*}$ in the upper
antichain of $S^{*}_{f}$ such that $f\leq f^{*}$. (Proof in Section 8.7)

Intuitively the upper antichain of $S^{*}_{f}$ is the collection of all
functions $f\in S^{*}_{f}$ that are not strictly upper bounded by any other
function in $S^{*}_{f}$. The upper antichain of an empty set is of course
itself an empty set.

###### Definition 5.2.

We can form the following categories:

  1. $\mathbf{D_{C}}$

: The objects in $\mathbf{D_{C}}$ are $\leq$-antichains of functions
$X_{f}\subseteq S_{f}$. $\mathbf{D_{C}}$ is a preorder in which $X_{f}\leq
X^{\prime}_{f}$ if for $f\in X_{f}$ there must exist some $f^{\prime}\in
X^{\prime}_{f}$ where $f\leq f^{\prime}$.

  2. $\mathbf{D_{B}}$

: The objects in $\mathbf{D_{B}}$ are labeled datasets, or sets of pairs
$U=\\{(x,y)\ |\ x\in I,y\in O\\}$. $\mathbf{D_{B}}$ is a preorder such that
$U\leq U^{\prime}$ when for all $(x,y^{\prime})\in U^{\prime}$ there exists
$(x,y)\in U$ where $y\leq y^{\prime}$.

  3. $\mathbf{D_{A}}$

: A subcategory of $\mathbf{D_{B}}$ such that if $U\leq
U^{\prime}\in\mathbf{D_{B}}$ then $U\leq U^{\prime}\in\mathbf{D_{A}}$.

###### Proposition 5.3.

$\mathbf{D_{B}}$ and $\mathbf{D_{C}}$ are preorder catgories. (Proof in
Section 8.8)

Intuitively, $\mathbf{D_{A}}$ is a collection of labeled training datasets and
$\mathbf{D_{B}}$ is a collection of labeled testing datasets. We can define a
functor that maps each training dataset to all of the trained models that
agree with that dataset.

###### Proposition 5.4.

The map $K:\mathbf{D_{A}}\rightarrow\mathbf{D_{C}}$ that acts as the identity
on morphisms and maps the object $U\in\mathbf{D_{A}}$ to the upper antichain
of the following set:

$\displaystyle S_{K}(U)=\\{f\ |\ f\in S_{f},\forall(x,y)\in U,f(x)\leq y\\}$

is a functor. (Proof in Section 8.9)

Now define $G:\mathbf{D_{A}}\hookrightarrow\mathbf{D_{B}}$ to be the inclusion
functor. A functor $F:\mathbf{D_{B}}\rightarrow\mathbf{D_{C}}$ such that
$F\circ G$ commutes with $K$ will then be a mapping from the testing datasets
in $\mathbf{D_{B}}$ to collections of trained models.

${\mathbf{D_{B}}}$${\mathbf{D_{A}}}$${\mathbf{D_{C}}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

We can take the left and right Kan extensions of $K$ along the inclusion
functor $G:\mathbf{D_{A}}\hookrightarrow\mathbf{D_{B}}$ to find the optimal
such mapping.

###### Proposition 5.5.

The map $Lan_{G}K$ that acts as the identity on morphisms and maps the object
$U\in\mathbf{D_{B}}$ to the upper antichain of the following set:

$\displaystyle S_{L}(U)=\bigcup_{\\{U^{\prime}\ |\
U^{\prime}\in\mathbf{D_{A}},U^{\prime}\leq U\\}}\ K(U^{\prime})$

is the left Kan extension of $K$ along $G$.

Next, the map $Ran_{G}K$ that acts as the identity on morphisms and maps the
object $U\in\mathbf{D_{B}}$ to the upper antichain of the following set:

$\displaystyle S_{R}(U)=$ $\displaystyle\\{f\ |\ f\in S_{f},\ \forall
U^{\prime}\in\\{U^{\prime}\ |\ U^{\prime}\in\mathbf{D_{A}},U\leq
U^{\prime}\\},$ $\displaystyle\exists f^{\prime}\in K(U^{\prime}),\ f\leq
f^{\prime}\\}$

is the right Kan extension of $K$ along $G$. (Proof in Section 8.10)

Intuitively the functions in $Ran_{G}K(U)$ and $Lan_{G}K(U)$ are as large as
possible subject to constraints imposed by the selection of sets in
$Ob(\mathbf{D_{A}})$. The functions in $Lan_{G}K(U)$ are subject to a
membership constraint and grow smaller when we remove objects from
$Ob(\mathbf{D_{A}})$. The functions in $Ran_{G}K(U)$ are subject to an upper
boundedness-constraint and grow larger when we remove objects from
$Ob(\mathbf{D_{A}})$.

Consider the extreme case where $Ob(\mathbf{D_{A}})=\emptyset$. For any
$U\in\mathbf{D_{B}}$ we have that:

$\displaystyle S_{L}(U)=\bigcup_{\\{U^{\prime}\ |\
U^{\prime}\in\emptyset,\cdots\\}}\ K(U^{\prime})=\emptyset$ $\displaystyle
S_{R}(U)=\\{f\ |\ f\in S_{f},\ \forall U^{\prime}\in\emptyset,\
\cdots\\}=S_{f}$

so $Lan_{G}K(U)$ is empty and $Ran_{G}K(U)$ is the upper antichain of $S_{f}$.

Now consider the extreme case where $Ob(\mathbf{D_{A}})=Ob(\mathbf{D_{B}})$.
For any $U\in\mathbf{D_{B}}$ and $f\in K(U)$ the functoriality of $K$ implies
that:

$\displaystyle\forall U^{\prime}\in\\{U^{\prime}\ |\
U^{\prime}\in\mathbf{D_{A}},U\leq U^{\prime}\\},\ \exists f^{\prime}\in
K(U^{\prime}),\ f\leq f^{\prime}$

and therefore $f\in S_{R}(U)$. This implies $K(U)\leq Ran_{G}K(U)$. Similarly,
for any $f\in Lan_{G}K(U)$ it must be that:

$\displaystyle\exists U^{\prime}\in\mathbf{D_{A}},\ U^{\prime}\leq U,\ f\in
K(U^{\prime})$

which by the functoriality of $K$ implies that

$\displaystyle\exists f^{*}\in K(U),f\leq f^{*}$

and therefore $Lan_{G}K(U)\leq K(U)$. Therefore in this extreme case we have:

$\displaystyle Ran_{G}K(U)=Lan_{G}K(U)=K(U)$

Let’s now consider a more concrete example. Suppose $I=\mathbb{R}_{\geq
0}^{2},O=\\{\text{false},\text{true}\\}$, and $S_{f}$ is the finite set of
linear classifiers $l:\mathbb{R}_{\geq
0}^{2}\rightarrow\\{\text{false},\text{true}\\}$ that can be expressed as:

$\displaystyle l_{a,b}(x_{1},x_{2})=\begin{cases}\text{true}&x_{2}\leq
a*x_{1}+b\\\ \text{false}&\text{else}\end{cases}$

where $a,b$ are integers in $(-100,100)$. Intuitively:

  * •

The classifiers in $Lan_{G}K(U)$ are selected to be the classifiers that
predict true as often as possible among the set of all classifiers that have
no false positives on some $U^{\prime}\in\mathbf{D_{A}}$ where $U^{\prime}\leq
U$.

  * •

The classifiers in $Ran_{G}K(U)$ are constructed to predict true as often as
possible subject to a constraint imposed by the selection of sets in
$\mathbf{D_{A}}$. For every set $U^{\prime}\in\mathbf{D_{A}}$ where $U\leq
U^{\prime}$ it must be that each classifier in $Ran_{G}K(U)$ is upper bounded
at each point in $I$ by some classifier in $S_{f}$ with no false positives on
$U^{\prime}$.

We can give a concrete example to demonstrate this. Suppose that:

$\displaystyle
Ob(\mathbf{D_{A}})=\\{\\{((1,3),\text{false})\\},\\{((4,4),\text{false})\\},$
$\displaystyle\qquad\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\}\\}\\}$
$\displaystyle
Ob(\mathbf{D_{B}})=Ob(\mathbf{D_{A}})\cup\\{\\{((1,3),\text{false}),((4,4),\text{false})\\}\\}$

We can visualize $\mathbf{D_{B}}$ as follows:

${\\{((4,4),\text{false})\\}}$${\\{((1,3),\text{false})\\}}$${\\{((1,3),\text{false}),((4,4),\text{false})\\}}$${\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\}}$$\scriptstyle{\leq}$$\scriptstyle{\leq}$$\scriptstyle{\leq}$

We can see the following:

  * •

$l_{(1,1)}\in K(\\{((1,3),\text{false})\\})$ since:

$\displaystyle l_{(1,1)}(1,3)=\begin{cases}\text{true}&3\leq 1*1+1\\\
\text{false}&\text{else}\end{cases}=\text{false}$

but we have that:

$\displaystyle l_{(1,2)}(1,3)=\begin{cases}\text{true}&3\leq 1*1+2\\\
\text{false}&\text{else}\end{cases}=\text{true}$ $\displaystyle
l_{(2,1)}(1,3)=\begin{cases}\text{true}&3\leq 2*1+1\\\
\text{false}&\text{else}\end{cases}=\text{true}$

  * •

$l_{(0,2)}\in K(\\{((1,3),\text{false})\\})$ since:

$\displaystyle l_{(0,2)}(1,3)=\begin{cases}\text{true}&3\leq 0*1+2\\\
\text{false}&\text{else}\end{cases}=\text{false}$

but we have that:

$\displaystyle l_{(0,3)}(1,3)=\begin{cases}\text{true}&3\leq 0*1+3\\\
\text{false}&\text{else}\end{cases}=\text{true}$ $\displaystyle
l_{(1,2)}(1,3)=\begin{cases}\text{true}&3\leq 1*1+2\\\
\text{false}&\text{else}\end{cases}=\text{true}$

  * •

$l_{(0,3)}\in K(\\{((4,4),\text{false})\\})$ since:

$\displaystyle l_{(0,3)}(4,4)=\begin{cases}\text{true}&4\leq 0*4+3\\\
\text{false}&\text{else}\end{cases}=\text{false}$

but we have that:

$\displaystyle l_{(1,3)}(4,4)=\begin{cases}\text{true}&4\leq 1*4+3\\\
\text{false}&\text{else}\end{cases}=\text{true}$ $\displaystyle
l_{(0,4)}(4,4)=\begin{cases}\text{true}&4\leq 0*4+4\\\
\text{false}&\text{else}\end{cases}=\text{true}$

  * •

$l_{(0,1)}\in
K(\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\})$
since:

$\displaystyle l_{(0,1)}(2,2)=\begin{cases}\text{true}&2\leq 0*2+1\\\
\text{false}&\text{else}\end{cases}=\text{false}$ $\displaystyle
l_{(0,1)}(1,3)=\begin{cases}\text{true}&3\leq 0*1+1\\\
\text{false}&\text{else}\end{cases}=\text{false}$ $\displaystyle
l_{(0,1)}(4,4)=\begin{cases}\text{true}&4\leq 0*4+1\\\
\text{false}&\text{else}\end{cases}=\text{false}$

but we have that:

$\displaystyle l_{(1,1)}(4,4)=\begin{cases}\text{true}&4\leq 1*4+1\\\
\text{false}&\text{else}\end{cases}=\text{true}$ $\displaystyle
l_{(0,2)}(2,2)=\begin{cases}\text{true}&2\leq 0*2+2\\\
\text{false}&\text{else}\end{cases}=\text{true}$

By the definition of $Lan_{G}K$ we have that:

$\displaystyle Lan_{G}K(\\{((1,3),\text{false}),((4,4),\text{false})\\})$

must contain $l_{(0,1)}$ since we have that:

$\displaystyle l_{(0,1)}\in
K(\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\})$

but:

$\displaystyle l_{(0,2)}\not\in
K(\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\})$

and:

$\displaystyle l_{(1,1)}\not\in
K(\\{((2,2),\text{false}),((1,3),\text{false}),((4,4),\text{false})\\})$

Similarly, by the definition of $Ran_{G}K$ we have that:

$\displaystyle Ran_{G}K(\\{((1,3),\text{false}),((4,4),\text{false})\\})$

must contain $l_{(0,2)}$ since we have that:

$\displaystyle l_{(0,2)}\leq l_{(0,3)}\qquad l_{(0,2)}\leq l_{(0,2)}$

but that there is no $l_{(a,b)}$ such that $l_{(0,2)}<l_{(a,b)}$ that is in
both $K(\\{((4,4),\text{false})\\})$ and $K(\\{((1,3),\text{false})\\})$
since:

$\displaystyle l_{(1,2)}\not\in K(\\{((4,4),\text{false})\\})\qquad
l_{(0,3)}\not\in K(\\{((1,3),\text{false})\\})$

Figure 2.  The decision boundaries defined by $l_{(1,1)}$, $l_{(0,3)}$, and
$l_{(0,1)}$.

##  6\. Function Approximation

In many learning applications there may be multiple functions in a class that
fit a particular set of data similarly well. In such a situation Occam’s Razor
suggests that we are best off choosing the simplest such function. For
example, we can choose the function with the smallest Kolmogorov complexity,
also known as the minimum description length (MDL) function (Rissanen, 1978).
In this Section we will explore how we can use Kan extensions to find the MDL
function that fits a dataset.

Suppose $I$ is a set, $O$ is a partial order, and $S$ is a finite subset of
$I$. We can define the following preorder:

###### Definition 6.1.

Define the preorder $\leq_{S}$ on $(I\rightarrow O)$ such that
$f_{1}\leq_{S}f_{2}$ if and only if $\forall x\in S,f_{1}(x)\leq f_{2}(x)$. If
$f_{1}\leq_{S}f_{2},f_{2}\not\leq_{S}f_{1}$ then write $f_{1}<_{S}f_{2}$ and
if $f_{1}\leq_{S}f_{2}\leq_{S}f_{1}$ then write $f_{1}=_{S}f_{2}$.

Now suppose also that $C_{\leq_{c}}$ is some finite subset of the space of all
functions $(I\rightarrow O)$ equipped with a total order $\leq_{c}$ such that
$f_{1}\leq_{c}f_{2}$ whenever the Kolmogorov complexity of $f_{1}$ is no
larger than that of $f_{2}$. Note that functions with the same Kolmogorov
complexity may be ordered arbitrarily in $C_{\leq_{c}}$.

###### Proposition 6.2.

Given a set of functions $S_{f}\subseteq C_{\leq_{c}}$ we can define a subset
$S_{f_{c}}\subseteq S_{f}$, which we call the minimum Kolmogorov subset of
$S_{f}$, such that for any function $f\in S_{f}$ the set $S_{f_{c}}$ contains
exactly one function $f_{c}$ where $f=_{S}f_{c}$. This function $f_{c}$
satisfies $f_{c}\leq_{c}f$. (Proof in Section 8.11)

We can use these constructions to define the following categories:

###### Definition 6.3.

Given the sets of functions $S^{1}_{f}\subseteq S^{2}_{f}\subseteq
C_{\leq_{c}}$ define $S^{1}_{f_{c}}$ to be the minimum Kolmogorov subset of
$S^{1}_{f}$. We can construct the categories
$\mathbf{F_{A}},\mathbf{F_{B}},\mathbf{F_{C}}$ as follows.

  * •

The set of objects in the discrete category $\mathbf{F_{A}}$ is
$S^{1}_{f_{c}}$.

  * •

The set of objects in $\mathbf{F_{B}}$ is $S^{2}_{f}$. $\mathbf{F_{B}}$ is a
preorder with morphisms $\leq_{S}$.

  * •

$\mathbf{F_{C}}$ is the subcategory of $\mathbf{F_{B}}$ in which objects are
functions in $S^{1}_{f_{c}}$ and morphisms are $\leq_{S}$.

Intuitively a functor $\mathbf{F_{B}}\rightarrow\mathbf{F_{C}}$ acts as a
choice of a minimum Kolmogorov complexity function in $S^{1}_{f_{c}}$ for each
function in $S^{2}_{f}$. For example, if $S^{1}_{f}$ contains all linear
functions and $S^{2}_{f}$ is the class of all polynomials then we can view a
functor $\mathbf{F_{B}}\rightarrow\mathbf{F_{C}}$ as selecting a linear
approximation for each polynomial in $S^{2}_{f}$.

###### Proposition 6.4.

For some function $g\in S^{2}_{f}$ define its minimal $S$-overapproximation to
be the function $h\in S^{1}_{f_{c}}$ where $g\leq_{S}h$ and $\forall
h^{\prime}\in S^{1}_{f_{c}}$ where $g\leq_{S}h^{\prime}$ we have
$h\leq_{S}h^{\prime}$. If this function exists it is unique.

###### Proof.

Suppose $h_{1},h_{2}$ are both minimal $S$-overapproximations of $g$. Then
$h_{1}\leq_{S}h_{2}$ and $h_{2}\leq_{S}h_{1}$ which by the definition of
$S^{1}_{f_{c}}$ implies that $h_{1}=h_{2}$. ∎

###### Proposition 6.5.

For some function $g\in S^{2}_{f}$ define its maximal $S$-underapproximation
to be the function $h\in S^{1}_{f_{c}}$ where $h\leq_{S}g$ and $\forall
h^{\prime}\in S^{1}_{f_{c}}$ where $h^{\prime}\leq_{S}g$ we have
$h^{\prime}\leq_{S}h$. If this function exists it is unique.

###### Proof.

Suppose $h_{1},h_{2}$ are both maximal $S$-underapproximations of $g$. Then
$h_{2}\leq_{S}h_{1}$ and $h_{1}\leq_{S}h_{2}$ which by the definition of
$S^{1}_{f_{c}}$ implies that $h_{1}=h_{2}$. ∎

###### Proposition 6.6.

Suppose that for some $g\in S^{2}_{f}$ there exists some $h\in S^{1}_{f_{c}}$
such that $h(x)=_{S}g(x)$. Then $h$ will be both the minimal
$S$-overapproximation and the maximal $S$-underapproximation of $g$.

###### Proof.

To start, note that $h$ must satisfy $g\leq_{S}h$ and for any $h^{\prime}\in
S^{1}_{f_{c}}$ we have $h=_{S}g\leq_{S}h^{\prime}$ so $h$ is the minimal
$S$-overapproximation of $g$. Next, note that $h$ must satisfy $h\leq_{S}g$
and for any $h^{\prime}\in S^{1}_{f_{c}}$ we have $h^{\prime}\leq_{S}g=_{S}h$
so $h$ is also the maximal $S$-underapproximation of $g$. ∎

We can now show the following:

###### Proposition 6.7.

Define both $K:\mathbf{F_{A}}\hookrightarrow\mathbf{F_{C}}$ and
$G:\mathbf{F_{A}}\hookrightarrow\mathbf{F_{B}}$ to be inclusion functors.
Then:

  * •

Suppose that for any function $g\in S^{2}_{f}$ there exists a minimal
$S$-overapproximation (Proposition 6.4) $h$ of $g$. Then the left Kan
extension of $K$ along $G$ is the functor $Lan_{G}K$ that acts as the identity
on morphisms and maps $g$ to $h$.

  * •

Suppose that for any function $g\in S^{2}_{f}$ there exists a maximal
$S$-underapproximation (Proposition 6.5) $h$ of $g$. Then the right Kan
extension of $K$ along $G$ is the functor $Ran_{G}K$ that acts as the identity
on morphisms and maps $g$ to $h$.

(Proof in Section 8.12)

${\mathbf{F_{B}}}$${\mathbf{F_{A}}}$${\mathbf{F_{C}}}$$\scriptstyle{F}$$\scriptstyle{G}$$\scriptstyle{K}$

Intuitively, the Kan extensions of the inclusion functor
$K:\mathbf{F_{A}}\rightarrow\mathbf{F_{C}}$ along the inclusion functor
$G:\mathbf{F_{A}}\rightarrow\mathbf{F_{B}}$ map a function $g\in S^{2}_{f}$ to
its best $S^{1}_{f}$-approximations over the points in $S$.

For example, suppose $I=O=\mathbb{R}$, $g$ is a polynomial, $S^{1}_{f}$ is the
set of lines defined by all pairs of points in $S$ and
$S^{2}_{f}=S^{1}_{f}\cup g$. $Lan_{G}K$ and $Ran_{G}K$ may or may not exist
depending on the choice of $S$ and $g$. In Figure 3 we give an example $S,g$
in which $Lan_{G}K$ exists and $Ran_{G}K$ does not (left) and an example $S,g$
in which $Ran_{G}K$ exists and $Lan_{G}K$ does not (right).

Figure 3.  Left and right Kan extensions of
$K:\mathbf{F_{A}}\hookrightarrow\mathbf{F_{C}}$ along
$G:\mathbf{F_{A}}\hookrightarrow\mathbf{F_{B}}$ for two example sets $S$ and
polynomials $g$ where $S^{1}_{f}$ is the class of lines and
$S^{2}_{f}=S^{1}_{f}\cup g$.

As another example, suppose $I=O=\mathbb{R}$, $S^{1}_{f}$ is a subset of all
polynomials of degree $|S|-1$ and $S^{2}_{f}$ is a subset of all functions
$\mathbb{R}\rightarrow\mathbb{R}$. Since there always exists a unique $n-1$
degree polynomial through $n$ unique points, for any $S$ there exists some
$S^{1}_{f}$ so that both $Lan_{G}K$ and $Ran_{G}K$ exist and map $g\in
S^{2}_{f}$ to the unique $|S|-1$ degree polynomial that passes through the
points $\\{(x,g(x))\ |\ x\in S\\}$.

As another example, consider the classification case in which
$I=\mathbb{R}^{a},O=\\{\text{false},\text{true}\\}$, $S^{1}_{f}$ is a subset
of all neural networks with a single hidden layer and $S^{2}_{f}$ is a subset
of all functions $\mathbb{R}^{n}\rightarrow\\{\text{false},\text{true}\\}$.
For any $S$ it is possible to select $S^{1}_{f}$ so that for any $g\in
S^{2}_{f}$ the function $Lan_{G}K(g)$ is the smallest (minimum Kolmogorov
complexity) single hidden layer neural network
$f:\mathbb{R}^{a}\rightarrow\\{\text{false},\text{true}\\}$ in $S^{1}_{f}$
such that $\forall x\in S,f(x)=g(x)$.

##  7\. Discussion

The category theoretic perspective on generalization that we introduce in this
paper is fundamentally different from the traditional data science
perspective. Intuitively, the traditional data science perspective is mean and
percentile-focused whereas the category theoretic perspective is min and max-
focused. That is, traditional data science algorithms may have objectives like
“minimize total errors” while the category theoretic algorithms we discuss in
this work have objectives like “minimize false positives subject to no false
negatives on some set.” As a result, algorithms built from the category
theoretic perspective may behave more predictably, but can also be more
sensitive to noise.

## References

  * (1)
  * Botnan and Lesnick (2018) Magnus Botnan and Michael Lesnick. 2018.  Algebraic stability of zigzag persistence modules.  _Algebraic & Geometric Topology_ 18, 6 (Oct 2018), 3133–3204.  https://doi.org/10.2140/agt.2018.18.3133
  * Boyd and Vandenberghe (2004) Stephen Boyd and Lieven Vandenberghe. 2004.  _Convex Optimization_.  Cambridge University Press.  http://www.amazon.com/exec/obidos/redirect?tag=citeulike-20&path=ASIN/0521833787
  * Bubenik et al. (2017) Peter Bubenik, Vin de Silva, and Vidit Nanda. 2017\.  Higher Interpolation and Extension for Persistence Modules.  _SIAM Journal on Applied Algebra and Geometry_ 1, 1 (Jan 2017), 272–284.  https://doi.org/10.1137/16m1100472
  * Carlsson and Mémoli (2013) Gunnar Carlsson and Facundo Mémoli. 2013.  Classifying clustering schemes.  _Foundations of Computational Mathematics_ 13, 2 (2013), 221–252.
  * Culbertson and Sturtz (2014) Jared Culbertson and Kirk Sturtz. 2014.  A categorical foundation for Bayesian probability.  _Applied Categorical Structures_ 22, 4 (2014), 647–662.  https://doi.org/10.1007/s10485-013-9324-9.
  * Curry (2013) Justin M. Curry. 2013\.  Sheaves, Cosheaves and Applications.  https://doi.org/10.1.1.363.2881
  * Fong and Spivak (2019) Brendan Fong and David I. Spivak. 2019.  _An Invitation to Applied Category Theory: Seven Sketches in Compositionality_.  Cambridge University Press.  https://doi.org/10.1017/9781108668804
  * Hinze (2012) Ralf Hinze. 2012\.  Kan Extensions for Program Optimisation Or: Art and Dan Explain an Old Trick. In _Mathematics of Program Construction - 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012. Proceedings_ _(Lecture Notes in Computer Science, Vol. 7342)_ , Jeremy Gibbons and Pablo Nogueira (Eds.). Springer, 324–362.  https://doi.org/10.1007/978-3-642-31113-0_16
  * Hofmann et al. (2008) Thomas Hofmann, Bernhard Schölkopf, and Alexander J Smola. 2008\.  Kernel methods in machine learning.  _The annals of statistics_ 36, 3 (2008), 1171–1220.
  * Hubert and Arabie (1985) Lawrence Hubert and Phipps Arabie. 1985.  Comparing partitions.  _Journal of classification_ 2, 1 (1985), 193–218.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Leinster (2016) Tom Leinster. 2016\.  _Basic Category Theory_.  Cambridge University Press.
  * Mac Lane (1971) Saunders Mac Lane. 1971\.  _Categories for the Working Mathematician_.  New York.
  * McCleary and Patel (2021) Alexander McCleary and Amit Patel. 2021.  Edit Distance and Persistence Diagrams Over Lattices.  arXiv:2010.07337 [math.AT]
  * McInnes and Healy (2017) Leland McInnes and John Healy. 2017.  Accelerated hierarchical density clustering.  _arXiv preprint arXiv:1705.07321_ (2017).
  * McInnes et al. (2018) Leland McInnes, John Healy, and James Melville. 2018\.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ (2018).
  * Paterson (2012) Ross Paterson. 2012\.  Constructing applicative functors. In _International Conference on Mathematics of Program Construction_. Springer, 300–323.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Rand (1971) William M Rand. 1971\.  Objective criteria for the evaluation of clustering methods.  _Journal of the American Statistical Association_ 66, 336 (1971), 846–850.
  * Rissanen (1978) J. Rissanen. 1978\.  Modeling by shortest data description.  _Automatica_ 14, 5 (1978), 465–471.  https://doi.org/10.1016/0005-1098(78)90005-5
  * Schultz et al. (2016) Patrick Schultz, David I Spivak, and Ryan Wisnesky. 2016\.  Algebraic model management: A survey. In _International Workshop on Algebraic Development Techniques_. Springer, 56–69.
  * Schultz and Wisnesky (2017) Patrick Schultz and Ryan Wisnesky. 2017.  Algebraic Data Integration.  arXiv:1503.03571 [cs.DB]
  * Shiebler (2020) Dan Shiebler. 2020\.  Functorial Clustering via Simplicial Complexes.  _NeurIPS Workshop on Topological Data Analysis in ML_ (2020).
  * Shiebler et al. (2021) Dan Shiebler, Bruno Gavranovic, and Paul W. Wilson. 2021\.  Category Theory in Machine Learning.  _CoRR_ abs/2106.07032 (2021).  arXiv:2106.07032 https://arxiv.org/abs/2106.07032
  * Spivak and Wisnesky (2015) David I. Spivak and Ryan Wisnesky. 2015.  Relational Foundations For Functorial Data Migration.  arXiv:1212.5303 [cs.DB]
  * Spivak and Wisnesky (2020) David I Spivak and Ryan Wisnesky. 2020.  Fast Left-Kan extensions using the chase.  _Preprint. Available at www. categoricaldata. net_ (2020).
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017.  Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ (2017).
  * Yanofsky (2013) Noson S. Yanofsky. 2013\.  Kolmogorov Complexity of Categories.  arXiv:1306.2675 [math.CT]

##  8\. Appendix

###  8.1. Proof of Proposition 3.1

###### Proof.

We first need to show that $Lan_{G}K,Ran_{G}K$ are functors. For any
$x_{1}\leq x_{2}\in\mathbf{I}$ suppose that $Lan_{G}K(x_{1})=\text{true}$.
Then $\exists x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x_{1},K(x^{\prime})=\text{true}$. By transitivity we have $x^{\prime}\leq
x_{2}$, so:

$\displaystyle Lan_{G}K(x_{2})=$
$\displaystyle\begin{cases}\text{true}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x_{2},K(x^{\prime})=\text{true}\\\ \text{false}&\text{else}\end{cases}=$ true

and $Lan_{G}K$ is therefore a functor.

Next, for any $x_{1}\leq x_{2}\in\mathbf{I}$ suppose that
$Ran_{G}K(x_{2})=\text{false}$. Then $\exists
x^{\prime}\in\mathbf{I}^{\prime},x_{2}\leq
x^{\prime},K(x^{\prime})=\text{false}$. By transitivity we have $x_{1}\leq
x^{\prime}$, so:

$\displaystyle Ran_{G}K(x_{1})=$
$\displaystyle\begin{cases}\text{false}&\exists
x^{\prime}\in\mathbf{I}^{\prime},x_{1}\leq
x^{\prime},K(x^{\prime})=\text{false}\\\ \text{true}&\text{else}\end{cases}=$
false

and $Ran_{G}K$ is therefore a functor.

Next we will show that $Lan_{G}K$ is the left Kan extension of $K$ along $G$.
If for some $x^{\prime}\in\mathbf{I}^{\prime}$ we have that
$K(x^{\prime})=\text{true}$ then:

$\displaystyle Lan_{G}K(x^{\prime})=$
$\displaystyle\begin{cases}\text{true}&\exists
x^{\prime\prime}\in\mathbf{I}^{\prime},x^{\prime\prime}\leq
x^{\prime},K(x^{\prime\prime})=\text{true}\\\
\text{false}&\text{else}\end{cases}=$ true

so we can conclude that $K\leq(Lan_{G}K\circ G)$. Now consider any other
functor $M_{L}:\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}$ such that
$\forall x^{\prime}\in\mathbf{I}^{\prime},K(x^{\prime})\leq
M_{L}(x^{\prime})$. We must show that $\forall x\in\mathbf{I},Lan_{G}K(x)\leq
M_{L}(x)$. For some $x\in\mathbf{I}$ suppose $M_{L}(x)=\text{false}$. Then
since $M_{L}$ is a functor it must be that $\forall
x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x,M_{L}(x^{\prime})=\text{false}$. Since $K\leq(M_{L}\circ G)$ it must be that
$\forall x^{\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x,K(x^{\prime})=\text{false}$. Therefore $Lan_{G}K(x)=\text{false}$.

Next we will show that $Ran_{G}K$ is the right Kan extension of $K$ along $G$.
If for some $x^{\prime}\in\mathbf{I}^{\prime}$ we have that
$K(x^{\prime})=\text{false}$ then:

$\displaystyle Ran_{G}K(x^{\prime})=$
$\displaystyle\begin{cases}\text{false}&\exists
x^{\prime\prime}\in\mathbf{I}^{\prime},x^{\prime}\leq
x^{\prime\prime},K(x^{\prime\prime})=\text{false}\\\
\text{true}&\text{else}\end{cases}=$ false

so we can conclude that $(Ran_{G}K\circ G)\leq K$. Now consider any other
functor $M_{R}:\mathbf{I}\rightarrow\\{\text{false},\text{true}\\}$ such that
$\forall x^{\prime}\in\mathbf{I}^{\prime},M_{R}(x^{\prime})\leq
K(x^{\prime})$. We must show that $\forall x\in\mathbf{I},M_{R}(x)\leq
Ran_{G}K(x)$. For some $x\in\mathbf{I}$ suppose $M_{R}(x)=\text{true}$. Then
since $M_{R}$ is a functor it must be that $\forall
x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},M_{R}(x^{\prime})=\text{true}$. Since $(M_{R}\circ G)\leq K$ it
must be that $\forall x^{\prime}\in\mathbf{I}^{\prime},x\leq
x^{\prime},K(x^{\prime})=\text{true}$. Therefore $Ran_{G}K(x)=\text{true}$. ∎

###  8.2. Proof of Proposition 3.3

###### Proof.

First note that $l$ must be non-negative since each term can be expressed as
$\max(0,\\_)$. Next, suppose that $l(f)=0$. Then it must be that for any
$x_{0},x_{1}\in\mathbf{I}^{\prime}$ such that
$K(x_{0})=\text{false},K(x_{1})=\text{true}$ we have that $f(x_{0})\leq
f(x_{1})$. As a result, for any $x\in\mathbf{I}^{\prime}$ there can only exist
some $x^{\prime}\in\mathbf{I}^{\prime}$ where $f(x)\leq
f(x^{\prime}),K(x^{\prime})=\text{false}$ when $K(x)=\text{false}$. Similarly,
there can only exist some $x^{\prime}\in\mathbf{I}^{\prime}$ where
$f(x^{\prime})\leq f(x),K(x^{\prime})=\text{true}$ when $K(x)=\text{true}$.
Therefore:

$\displaystyle K(x)=(Lan_{f\circ G}K\circ f)(x)=(Ran_{f\circ G}K\circ f)(x)$

∎

###  8.3. Proof of Proposition 4.9

###### Proof.

$Lan_{G}K_{L}$ trivially acts as the identity on morphisms and underlying sets
and preserves composition and identity so we simply need to show that when:

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(Y,d_{Y})$

then

$\displaystyle
Lan_{G}K_{L}(X,d_{X})\leq_{\mathbf{Part}_{id}}Lan_{G}K_{L}(Y,d_{Y})$

Suppose there exists some $x,x^{*}\in X$ in the same cluster in
$Lan_{G}K_{L}(X,d_{X})$. Then by the definition of $Lan_{G}K_{L}$ there must
exist some sequence

$\displaystyle(X_{1},d_{X_{1}}),(X_{2},d_{X_{2}}),\cdots,(X_{n},d_{X_{n}})\in\mathbf{T}$

where $x\in X_{1},x^{*}\in X_{n}$ and each:

$\displaystyle(X_{i},d_{X_{i}})\leq_{\mathbf{D}}(X,d_{X})$

as well as some sequence

$\displaystyle x_{1},x_{2},\cdots,x_{n-1},\ \text{such that}\ x_{i}\in
X_{i},x_{i}\in X_{i+1}$

where the pair $(x,x_{1})$ is in the same cluster in $K(X_{1},d_{X_{1}})$, the
pair $(x_{n-1},x^{*})$ is in the same cluster in $K(X_{n},d_{X_{n}})$, and for
each $1<i<n$ the pair $(x_{i-1},x_{i})$ is in the same cluster in
$K(X_{i},d_{X_{i}})$. Since it must be that each:

$\displaystyle(X_{i},d_{X_{i}})\leq_{\mathbf{D}}(Y,d_{Y})$

as well then by the definition of $Lan_{G}K_{L}$ it must be that $x,x^{*}$ are
in the same cluster in $Lan_{G}K_{L}(Y,d_{Y})$. ∎

###  8.4. Proof of Proposition 4.10

###### Proof.

$Ran_{G}K_{R}$ trivially acts as the identity on morphisms and underlying sets
and preserves composition and identity so we simply need to show that when:

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(Y,d_{Y})$

then:

$\displaystyle
Ran_{G}K_{R}(X,d_{X})\leq_{\mathbf{Part}_{id}}Ran_{G}K_{R}(Y,d_{Y})$

Suppose the points $x,x^{*}\in X$ are in the same cluster in
$Ran_{G}K_{R}(X,d_{X})$. Then by the definition of $Ran_{G}K_{R}$ there cannot
be any $(X^{\prime},d_{X^{\prime}})$ in $\mathbf{T}$ such that:

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(X^{\prime},d_{X^{\prime}})$

and $x,x^{*}$ are in different clusters in
$Ran_{G}K_{R}(X^{\prime},d_{X^{\prime}})$. By transitivity this implies that
there cannot be any $(X^{\prime\prime},d_{X^{\prime\prime}})$ in $\mathbf{T}$
such that:

$\displaystyle(Y,d_{Y})\leq_{\mathbf{D}}(X^{\prime\prime},d_{X^{\prime\prime}})$

and $x,x^{*}$ are in different clusters in
$Ran_{G}K_{R}(X^{\prime\prime},d_{X^{\prime\prime}})$. By the definition of
$Ran_{G}K_{R}$ the points $x,x^{*}$ must therefore be in the same cluster in
$Ran_{G}K_{R}(Y,d_{Y})$. ∎

###  8.5. Proof of Proposition 4.11

###### Proof.

Since each of:

$\displaystyle\iota\circ F:\mathbf{D}\rightarrow\mathbf{Part}$
$\displaystyle\iota\circ Ran_{G}K_{R}:\mathbf{D}\rightarrow\mathbf{Part}$
$\displaystyle\iota\circ Lan_{G}K_{L}:\mathbf{D}\rightarrow\mathbf{Part}$

are $\mathbf{D}$-clustering functors we simply need to prove that all three
functors generate the same partition of $X$ for any input
$(X,d_{X})\in\mathbf{T}$.

Consider some $(X,d_{X})\in\mathbf{T}$ and two points $x,x^{*}\in X$. Suppose
$x,x^{*}$ are in different clusters in

$\displaystyle K(X,d_{X})=F(X,d_{X})$

. Then since $F$ is a $\mathbf{D}$-clustering functor it must be that for any
sequence

$\displaystyle(X_{1},d_{X_{1}}),(X_{2},d_{X_{2}}),\cdots,(X_{n},d_{X_{n}})\in\mathbf{T}$

where $x\in X_{1},x^{*}\in X_{n}$ and each:

$\displaystyle(X_{i},d_{X_{i}})\leq_{\mathbf{D}}(X,d_{X})$

and any sequence

$\displaystyle x_{1},x_{2},\cdots,x_{n-1},\ \text{such that}\ x_{i}\in
X_{i},x_{i}\in X_{i+1}$

one of the following must be true:

  * •

The pair $(x,x_{1})$ are in different clusters in $F(X_{1},d_{X_{1}})$

  * •

The pair $(x_{n-1},x^{*})$ are in different clusters in $F(X_{n},d_{X_{n}})$

  * •

For some $1<i<n$ the pair $(x_{i-1},x_{i})$ are in different clusters in
$F(X_{i},d_{X_{i}})$

This implies that in $Lan_{G}K_{L}(X,d_{X})$ the points $x,x^{*}$ must be in
different clusters. Similarly, since $(X,d_{X})\leq_{\mathbf{D}}(X,d_{X})$, by
Proposition 4.10 it must be that $x,x^{*}$ are in different clusters in
$Ran_{G}K_{R}(X,d_{X})$.

Now suppose $x,x^{*}$ are in the same cluster in

$\displaystyle K(X,d_{X})=F(X,d_{X})$

. Since $(X,d_{X})\leq_{\mathbf{D}}(X,d_{X})$, by Proposition 4.9 it must be
that $x,x^{*}$ are in the same cluster in $Lan_{G}K_{L}(X,d_{X})$. Similarly,
since $F$ is a $\mathbf{D}$-clustering functor there cannot exist any metric
space $(X^{\prime},d_{X^{\prime}})\in\mathbf{T}$ where:

$\displaystyle(X,d_{X})\leq_{\mathbf{D}}(X^{\prime},d_{X^{\prime}})$

and $x,x^{*}$ are in different clusters in

$\displaystyle K(X^{\prime},d_{X^{\prime}})=F(X^{\prime},d_{X^{\prime}})$

. Therefore $x,x^{*}$ are in the same cluster in $Ran_{G}K_{R}(X,d_{X})$. ∎

###  8.6. Proof of Proposition 4.12

###### Proof.

To start, note that Proposition 4.11 implies that for any
$(X,d_{X})\in\mathbf{T}$ we have:

$\displaystyle Lan_{G}K_{L}(X,d_{X})=K(X,d_{X})=Ran_{G}K_{R}(X,d_{X})$

By the definition of $K_{L},K_{R}$ we can therefore conclude that for any
$(X,d_{X})\in\mathbf{D}$ we have:

$\displaystyle K_{L}(X,d_{X})\leq_{\mathbf{Part}_{id}}Lan_{G}K_{L}(X,d_{X})$
$\displaystyle Ran_{G}K_{R}(X,d_{X})\leq_{\mathbf{Part}_{id}}K_{R}(X,d_{X})$

Next, consider any functor $M_{L}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$
such that for all $(X,d_{X})\in\mathbf{D}$ we have:

$\displaystyle K_{L}(X,d_{X})\leq_{\mathbf{Part}_{id}}(M_{L}\circ G)(X,d_{X})$

We must show that for any $(X,d_{X})\in\mathbf{D}$ we have:

$\displaystyle Lan_{G}K_{L}(X,d_{X})\leq_{\mathbf{Part}_{id}}M_{L}(X,d_{X})$

To start, note that for any $x,x^{*}\in X$ that are in the same cluster in
$Lan_{G}K_{L}(X,d_{X})$ by the definition of $Lan_{G}K_{L}$ there must exist
some sequence:

$\displaystyle(X_{1},d_{X_{1}}),(X_{2},d_{X_{2}}),\cdots,(X_{n},d_{X_{n}})\in\mathbf{T}$

where $x\in X_{1},x^{*}\in X_{n}$ and each:

$\displaystyle(X_{i},d_{X_{i}})\leq_{\mathbf{D}}(X,d_{X})$

as well as some sequence

$\displaystyle x_{1},x_{2},\cdots,x_{n-1},\ \text{such that}\ x_{i}\in
X_{i},x_{i}\in X_{i+1}$

where the pair $(x,x_{1})$ is in the same cluster in $K_{L}(X_{1},d_{X_{1}})$,
the pair $(x_{n-1},x^{*})$ is in the same cluster in $K_{L}(X_{n},d_{X_{n}})$,
and for each $1<i<n$ the pair $(x_{i-1},x_{i})$ is in the same cluster in
$K_{L}(X_{i},d_{X_{i}})$. Now since for each $(X_{i},d_{X_{i}})$ in this
sequence we have that:

$\displaystyle
K_{L}(X_{i},d_{X_{i}})\leq_{\mathbf{Part}_{id}}M_{L}(X_{i},d_{X_{i}})$

it must be that the pair $(x,x_{1})$ is in the same cluster in
$M_{L}(X_{1},d_{X_{1}})$, the pair $(x_{n-1},x^{*})$ is in the same cluster in
$M_{L}(X_{n},d_{X_{n}})$, and for each $1<i<n$ the pair $(x_{i-1},x_{i})$ is
in the same cluster in $M_{L}(X_{i},d_{X_{i}})$.

Since $M_{L}$ is a functor it must therefore be that the pair $x,x^{*}$ is in
the same cluster in $M_{L}(X,d_{X})$ and therefore:

$\displaystyle Lan_{G}K_{L}(X,d_{X})\leq_{\mathbf{Part}_{id}}M_{L}(X,d_{X})$

.

Next, consider any functor $M_{R}:\mathbf{D}\rightarrow\mathbf{Part}_{id}$
such that for all $(X,d_{X})$ in $\mathbf{D}$:

$\displaystyle(M_{R}\circ G)(X,d_{X})\leq_{\mathbf{Part}_{id}}K_{R}(X,d_{X})$

We must show that for any $(X,d_{X})$ in $\mathbf{D}$ we have:

$\displaystyle M_{R}(X,d_{X})\leq_{\mathbf{Part}_{id}}Ran_{G}K_{R}(X,d_{X})$

To start, note that for any $x,x^{*}\in X$ such that $x,x^{*}$ are not in the
same cluster in $Ran_{G}K_{R}(X,d_{X})$ by the definition of $Ran_{G}K_{R}$
there must exist some:

$\displaystyle(X^{\prime},d_{X^{\prime}})\in
Ob(\mathbf{D}),(X,d_{X})\leq_{\mathbf{D}}(X^{\prime},d_{X^{\prime}})$

where $x,x^{*}$ are not in the same cluster in
$K_{R}(X^{\prime},d_{X^{\prime}})$. Now since:

$\displaystyle
M_{R}(X^{\prime},d_{X^{\prime}})\leq_{\mathbf{Part}_{id}}K_{R}(X^{\prime},d_{X^{\prime}})$

it must be that $x,x^{*}$ are not in the same cluster in
$M_{R}(X^{\prime},d_{X^{\prime}})$. Since $M_{R}$ is a functor we have:

$\displaystyle
M_{R}(X,d_{X})\leq_{\mathbf{Part}_{id}}M_{R}(X^{\prime},d_{X^{\prime}})$

so $x,x^{*}$ are also not in the same cluster in $M_{R}(X,d_{X})$ and
therefore:

$\displaystyle M_{R}(X,d_{X})\leq_{\mathbf{Part}_{id}}Ran_{G}K_{R}(X,d_{X})$

. ∎

###  8.7. Proof of Proposition 5.1

###### Proof.

Suppose $f_{1},f_{2}$ are in the upper antichain of $S^{*}_{f}\subseteq S_{f}$
and $f_{1}\leq f_{2}$. Then since

$\displaystyle\not\exists f^{*}_{1}\in S^{*}_{f},f_{1}<f^{*}_{1}$

it must be that $f_{1}=f_{2}$ and we can conclude that the upper antichain is
an antichain.

Next, for any function $f\in S^{*}_{f}$ consider the set $\\{f^{*}\in
S^{*}_{f},f<f^{*}\\}$. Since $S_{f}$ is finite this set must have finite size.
If this set is empty then $f$ is in the upper antichain of $S^{*}_{f}$. If
this set has size $n$ then for any $f^{*}$ in this set the set $\\{f^{**}\in
S^{*}_{f},f^{*}<f^{**}\\}$ must have size strictly smaller than $n$. We can
therefore conclude by induction that the upper antichain of $S^{*}_{f}$
contains at least one function $f^{*}$ where $f\leq f^{*}$. ∎

###  8.8. Proof of Proposition 5.3

###### Proof.

$\mathbf{D_{C}}$
We trivially have $X_{f}\leq X_{f}$ in $\mathbf{D_{C}}$. To see that $\leq$ is
transitive in $\mathbf{D_{C}}$ simply note that if $X_{f_{1}}\leq X_{f_{2}}$
and $X_{f_{2}}\leq X_{f_{3}}$ then for $f_{1}\in X_{f_{1}}$ there must exist
$f_{2}\in X_{f_{2}},f_{1}\leq f_{2}$, which implies that there must exist
$f_{3}\in X_{f_{3}},f_{1}\leq f_{2}\leq f_{3}$.

$\mathbf{D_{B}}$
We trivially have $U\leq U$ in $\mathbf{D_{B}}$. To see that $\leq$ is
transitive in $\mathbf{D_{B}}$ simply note that if $U_{1}\leq U_{2}$ and
$U_{2}\leq U_{3}$ in $\mathbf{D_{B}}$ then for $(x,y_{3})\in U_{3}$ there must
exist $(x,y_{2})\in U_{2},y_{2}\leq y_{3}$ which implies that there must exist
$(x,y_{1})\in U_{1},y_{1}\leq y_{2}\leq y_{3}$. ∎

###  8.9. Proof of Proposition 5.4

###### Proof.

To start, note that $K$ maps objects in $\mathbf{D_{A}}$ to objects in
$\mathbf{D_{C}}$ since the upper antichain of $S_{K}(U)$ must be an antichain
in $S_{f}$ by Proposition 5.1.

Next, we need to show that if $U\leq U^{\prime}$ then $K(U)\leq
K(U^{\prime})$. For any $x,y^{\prime}\in U^{\prime}$ it must be that there
exists $(x,y)\in U$ where $y\leq y^{\prime}$, so if $f\in K(U)$ then by the
definition of $K$ we have $f(x)\leq y\leq y^{\prime}$. Therefore $f\in
S_{K}(U^{\prime})$, so by Proposition 5.1 $K(U^{\prime})$ contains
$f^{\prime}$ where $f\leq f^{\prime}$. Therefore $K(U)\leq K(U^{\prime})$. ∎

###  8.10. Proof of Proposition 5.5

###### Proof.

We first need to show that $Lan_{G}K$ is a functor. Note that $Lan_{G}K$ maps
objects in $\mathbf{D_{B}}$ to objects in $\mathbf{D_{C}}$ since the upper
antichain of $S_{L}(U)$ must be an antichain in $S_{f}$.

Next, suppose $U_{1}\leq U_{2}$ and that $f\in Lan_{G}K(U_{1})$. Consider the
set of all $U^{\prime}\in\mathbf{D_{A}}$ where $U^{\prime}\leq U_{1}$. Since
$U_{1}\leq U_{2}$ this is a subset of the set of all
$U^{\prime}\in\mathbf{D_{A}}$ where $U^{\prime}\leq U_{2}$. Since
$S_{L}(U_{1})$ is defined to be a union of the elements in the set we have
that $S_{L}(U_{1})\subseteq S_{L}(U_{2})$. Since $f\in Lan_{G}K(U_{1})$
implies that $f\in S_{L}(U_{1})$ this implies that $f\in S_{L}(U_{2})$ as
well. Proposition 5.1 then implies that there must exist $f^{\prime}\in
Lan_{G}K(U_{2})$ where $f\leq f^{\prime}$ and therefore $Lan_{G}K(U_{1})\leq
Lan_{G}K(U_{2})$.

Next, we will show that $Lan_{G}K$ is the left Kan extension of $K$ along $G$.

  * •

Consider some $U\in\mathbf{D_{A}}$ and $f\in K(U)$. Since $U\leq U$ we have by
the definition of $S_{L}$ that $f\in S_{L}(U)$. Proposition 5.1 then implies
that $\exists f^{\prime}\in Lan_{G}K(U)$ such that $f\leq f^{\prime}$. This
implies that $K\leq Lan_{G}K\circ G$.

  * •

Now consider any functor $M_{L}:\mathbf{D_{B}}\rightarrow\mathbf{D_{C}}$ such
that $K\leq(M_{L}\circ G)$. We must show that $Lan_{G}K\leq M_{L}$. For some
$U\in\mathbf{D_{B}}$ suppose $f\in Lan_{G}K(U)$. By the definition of $S_{L}$
there must exist some $U^{\prime}\in\mathbf{D_{A}}$ where $U^{\prime}\leq U$
such that $f\in K(U^{\prime})$. Since $K(U^{\prime})\leq M_{L}(U^{\prime})$
there must exist some $f^{\prime}\in M_{L}(U^{\prime})$ where $f\leq
f^{\prime}$. Since $M_{L}$ is a functor we have $M_{L}(U^{\prime})\leq
M_{L}(U)$ which implies that there must exist some $f^{*}\in M_{R}(U)$ where
$f\leq f^{\prime}\leq f^{*}$. Therefore $Lan_{G}K\leq M_{L}$.

Next, we need to show that $Ran_{G}K$ is a functor. Note that $Ran_{G}K$ maps
objects in $\mathbf{D_{B}}$ to objects in $\mathbf{D_{C}}$ since the upper
antichain of $S_{R}(U)$ must be an antichain in $S_{f}$. Next, suppose
$U_{1}\leq U_{2}$ and that $f\in Ran_{G}K(U_{1})$. Consider the set of all
$U^{\prime}\in\mathbf{D_{A}}$ where $U_{2}\leq U^{\prime}$. Since $U_{1}\leq
U_{2}$ this is a subset of the set of all $U^{\prime}\in\mathbf{D_{A}}$ where
$U_{1}\leq U^{\prime}$. Therefore by the definition of $S_{R}$ we have that
$S_{R}(U_{1})\subseteq S_{R}(U_{2})$. Since $f\in Ran_{G}K(U_{1})$ implies
that $f\in S_{R}(U_{1})$ this implies that $f\in S_{R}(U_{2})$ as well.
Proposition 5.1 then implies that there must exist $f^{\prime}\in
Ran_{G}K(U_{2})$ where $f\leq f^{\prime}$ and therefore $Ran_{G}K(U_{1})\leq
Ran_{G}K(U_{2})$.

Next, we will show that $Ran_{G}K$ is the right Kan extension of $K$ along
$G$.

  * •

For $U\in\mathbf{D_{A}}$ since $U\leq U$ we have that when $f\in S_{R}(U)$ we
have by the definition of $S_{R}$ that $\exists f^{\prime}\in K(U)$ such that
$f\leq f^{\prime}$. Since $Ran_{G}K(U)$ is a subset of $S_{R}(U)$ this implies
that $Ran_{G}K\circ G\leq K$.

  * •

Now consider any functor $M_{R}:\mathbf{D_{B}}\rightarrow\mathbf{D_{C}}$ such
that $(M_{R}\circ G)\leq K$. We must show that $M_{R}\leq Ran_{G}K$. For some
$U\in\mathbf{D_{B}}$ suppose $f\in M_{R}(U)$. Since $M_{R}$ is a functor it
must be that for all $U^{\prime}\in\mathbf{D_{A}}$ where $U\leq U^{\prime}$ we
have that $M_{R}(U)\leq M_{R}(U^{\prime})$ and therefore $\exists
f^{\prime}_{M_{R}}\in M_{R}(U^{\prime}),f\leq f^{\prime}_{M_{R}}$. Since
$(M_{R}\circ G)\leq K$ this implies that for all $U^{\prime}\in\mathbf{D_{A}}$
where $U\leq U^{\prime}$ we have that $\exists f^{\prime}_{K}\in
K(U^{\prime}),f\leq f^{\prime}_{M_{R}}\leq f^{\prime}_{K}$. By the definition
of $S_{R}$ this implies that $f\in S_{R}(U)$. Proposition 5.1 therefore
implies that there exists $f^{\prime}_{R}\in Ran_{G}K(U)$ such that $f\leq
f^{\prime}_{R}$, and therefore $M_{R}(U)\leq Ran_{G}K(U)$.

∎

###  8.11. Proof of Proposition 6.2

###### Proof.

For any function $f\in S_{f}$ there must exist some
$f_{c}=\min_{\leq_{c}}\\{f^{\prime}\ |\ f^{\prime}\in
S_{f},f^{\prime}=_{S}f\\}$ since $\\{f^{\prime}\ |\ f^{\prime}\in
S_{f},f^{\prime}=_{S}f\\}$ is a nonempty finite total $\leq_{c}$-order.
Therefore we can define a map that sends each $f\in S_{f}$ to $f_{c}$. Define
$S_{f_{c}}$ to be the image of this map.

Since this map will send all $f\in S_{f}$ in the same $=_{S}$ equivalence
class to the same function in that $=_{S}$ equivalence class, $S_{f_{c}}$
contains exactly one function $f_{c}$ where $f=_{S}f_{c}$. This function
$f_{c}$ satisfies $f_{c}\leq_{c}f$. ∎

###  8.12. Proof of Proposition 6.7

###### Proof.

We first show that $Lan_{G}K$ is a functor when it exists. Since
$\mathbf{F_{B}},\mathbf{F_{C}}$ are preorders we simply need to show that when
$f_{1}\leq_{S}f_{2}$ then $Lan_{G}K(f_{1})\leq_{S}Lan_{G}K(f_{2})$. Since
$f_{2}\leq_{S}Lan_{G}K(f_{2})$ by the definition of the minimal
$S$-overapproximation of $f_{2}$ we have that $f_{1}\leq_{S}Lan_{G}K(f_{2})$.
Then $Lan_{G}K(f_{1})\leq_{S}Lan_{G}K(f_{2})$ by the definition of the minimal
$S$-overapproximation of $f_{1}$.

We next show that $Ran_{G}K$ is a functor when it exists. Since
$\mathbf{F_{B}},\mathbf{F_{C}}$ are preorders we simply need to show that when
$f_{1}\leq_{S}f_{2}$ then $Ran_{G}K(f_{1})\leq_{S}Ran_{G}K(f_{2})$. Since
$Ran_{G}K(f_{1})\leq_{S}f_{1}$ by the definition of the maximal
$S$-underapproximation of $f_{1}$ we have that $Ran_{G}K(f_{1})\leq_{S}f_{2}$.
Then $Ran_{G}K(f_{1})\leq_{S}Ran_{G}K(f_{2})$ by the definition of the maximal
$S$-underapproximation of $f_{2}$.

Next, we will show that $Lan_{G}K$ and $Ran_{G}K$ are respectively the left
and right Kan extensions when they exist. First, by Proposition 6.6 if $f\in
S^{1}_{f_{c}}$ then $f$ must be both the minimal $S$-overapproximation and
maximal $S$-underapproximation of $f$. Therefore we have:

$\displaystyle K(f)=Lan_{G}K(f)=Ran_{G}K(f)$

Next, consider any functor $M_{L}:\mathbf{F_{B}}\rightarrow\mathbf{F_{C}}$
such that $\forall f\in S^{1}_{f_{c}},K(f)\leq_{S}M_{L}(f)$. Since
$f=_{S}K(f)$ this implies $f\leq_{S}M_{L}(f)$ so by the definition of the
minimal $S$-overapproximation $Lan_{G}K(f)\leq_{S}M_{L}(f)$.

Next, consider any functor $M_{R}:\mathbf{F_{B}}\rightarrow\mathbf{F_{C}}$
such that $\forall f\in S^{1}_{f_{c}},M_{R}(f)\leq_{S}K(f)$. Since
$K(f)=_{S}f$ this implies $M_{R}(f)\leq_{S}f$ so by the definition of the
maximal $S$-underapproximation $M_{R}(f)\leq Ran_{G}K(f)$. ∎