\section{Introduction}
\label{sec:intro}
\vspace{-0.5em}

Applied category theory has recently developed software libraries for representing and computing with morphisms in various categories, with a particular focus on (symmetric) monoidal categories and diagrammatic reasoning (e.g. \cite{DeFelice2020,Halter2020,Patterson2021,Patterson2021b}). Categories have also emerged as a common representation for computer programs in different languages \cite{sorensen2006lectures,Elliott2017}.  In parallel, the field has worked to provide categorical semantics and interpretations for a variety of machine learning (ML) and artificial intelligence (AI) building blocks, including neural networks \cite{Fong2019,Fong2019a,Cruttwell2021}, and probabilistic inference \cite{giry1982categorical,Culbertson2014,Cho2019,Fritz2020}.

The intersection of learning and compositional reasoning has challenged the cognitive sciences (AI, ML, cognitive science, etc.) from the beginning. Theoretical arguments suggest that a generally intelligent agent \emph{ought} to reason compositionally \cite{Phillips2010,marcus2018algebraic}, to employ something like computable programs as models of the world \cite{SOLOMONOFF19641}, and to prefer simpler programs to more complex ones \cite{Vitanyi2000}. Evidence from a variety of experiments \cite{Lake2015,Ho2018,Grant2019,Lake2019,Zhou2021} suggests that abductive learning of program-like causal models provides a domain-general foundation for human intelligence.

Most process models of cognition spring from a limited selection of metaphors for how the mind works. For instance, cognitive scientists continue to debate whether the mind builds concepts by means of a ``language of thought'' \cite{Piantadosi2016a,Overlan2017,Romano2018} or convex geometric spaces \cite{gardenfors2004conceptual}. Some cognitive neuroscientists find tentative support for both ``map-like'' and ``sentence-like'' processes in the brain \cite{Frankland2020} while others argue for a more connectionist ``direct fit'' \cite{Hasson2020}. Machine learning scientists tackling the learning and synthesis of task-specific policies or programs tend to employ either Bayesian inference over a context-free grammar of programs, reinforcement learning of neural network policies, or both \cite{Parisotto2017,Valkov2018,Nye2020}.

Category theory readers will notice that program learning tasks, via their context-free grammars, work with the compositional structure of
operads \cite{Hermida1998,Fong2019b}. The connection suggests that categories, too, could provide a setting for learning and inference. This paper thus suggests an additional alternative to the options of neural networks and grammatical programs: a probabilistic generative model (PGM) of morphisms in a free monoidal category. This \emph{free category prior} is parameterized by generating objects and morphisms (to construct the free category) and wiring diagrams (to sample specific morphisms). An experiment shows that the model's software implementation can learn to compose deep generative models to achieve competitive performance in reconstruction evaluation data.

\vspace{-1em}
\paragraph{Outline}
Section~\ref{sec:background} summarizes the categorical background for the rest of the paper: our chosen setting for categorical probability in Section~\ref{subsec:Markov}, and the operad of wiring diagrams for use as specifications in Section~\ref{subsec:wiringoperad}. Section~\ref{sec:categoricalpgm} then defines the necessary categorical machinery for generative modeling, presents the free category prior, and demonstrates its basic properties. Section~\ref{sec:software} describes its software implementation, describes amortized variational inference (Section~\ref{subsec:amortizedinf}), and presents a basic experiment (Section~\ref{subsec:experiments}) showing that fitting the free category model to data yields competitive performance in a generative modeling task. Section~\ref{sec:discussion} discusses extensions and further applications.

\vspace{-1em}
\section{Categorical background}
\label{sec:background}

\subsection{Markov categories}
\label{subsec:Markov}
In this paper we build upon Markov categories, a formalism presented by Fritz~\cite{Fritz2020} following a series of works by Golubtsov~\cite{golubtsov1999axiomatic} and Cho and Jacobs~\cite{Cho2019}.
It allows us to represent fundamental concepts from probability theory (such as conditioning, causality, almost surety, etc.)  in purely categorical terms. 
In particular we work in \textbf{QBS} (i.e., the category of quasi-Borel spaces) by Heunen et al. \cite{Heunen2017}.
In the following we use the notation $\fatsemi$ and $\odot$ throughout for sequential and monoidal composition. 

\begin{definition}[Markov Category]
\label{def:markovcat}
A Markov category \(\mathcal{C}\) is a symmetric monoidal category in which every object \(X \in \mathcal{C}\) is equipped with a commutative comonoid structure given by a comultiplication \(\textbf{copy}_X: X \rightarrow X \odot X\) and a counit \(\textbf{del}_X: X \rightarrow I\).
\end{definition}

Modeling probability theory in a Markov category involves the following steps:
\begin{itemize}
    \item Identify a base Markov category \(\mathcal{C}\) (usually a category of certain type of measurable spaces).
    \item Identify a monad (usually Giry/probability monad) represented by an endofunctor \(\prob{}: \mathcal{C} \rightarrow \mathcal{C}\).
    \item Take the Kleisli category \(Kl(\prob{})\) of the monad \(\prob{}\).
\end{itemize}
Corollary 3.2 in \cite{Fritz2020} says that if \(\prob{}\) is a symmetric monoidal affine monad then the Kleisli category \(Kl(\prob{})\) is again a Markov category. In particular, the Giry monad is symmetric monoidal and affine.

Typically Markov categories consist of certain measurable spaces as objects and Markov kernels as morphisms. In \textbf{QBS}, by contrast, each object consists of a pair of a sample space $X$ and a collection of $X$-valued random variables $M_{X} \subseteq[\mathbb{R} \rightarrow X]$ (which must be closed under certain conditions) and the morphisms are random functions between sample spaces that extend the random variables in the domain to random variables in the codomain. Random variables are thus fundamental, rather than being derived from a $\sigma$-algebra of measurable subsets. They then derive their randomness from probability measures in $\mathbb{R}$, as we will discuss below.



\begin{definition}[Category of quasi-Borel spaces]
\label{def:qbs}
A quasi-Borel space is a set $X$, which we call the \emph{sample space}, together with a set of functions $M_X \subseteq [\mathbb{R} \rightarrow X]$ that
\begin{itemize}
    \item Contains all constant functions: \(\alpha \in M_{X}\) if \(\alpha: \mathbb{R}\rightarrow X\) is constant;
    \item Is closed under pre-composition: \(\alpha \circ f \in M_{X}\) if \(\alpha \in M_X\) and \(f: \mathbb{R}\rightarrow \mathbb{R}\) is measurable; and
    \item Is closed under countable mixtures: with respect to a partition of \(\mathbb{R} \) into a  disjoint union of countably many Borel sets i.e. \(\mathbb{R}=\biguplus_{i \in \mathbb{N}} S_{i}\), and \(\alpha_{1}, \alpha_{2}, \ldots \in M_{X}\) then the mixed random variable \(\beta\) is in \(M_{X}\) where \(\beta(r) = \alpha_i(r)\) for \(r\in S_i\).
\end{itemize}
Morphisms \((X, M_X) \rightarrow (Y, M_Y)\) between quasi-Borel spaces consist of  functions \(f: X\rightarrow Y\) such that \(f\circ \alpha \in M_Y\) for all \(\alpha \in M_X\).

Together these form the category of Quasi-Borel Spaces and measurable functions between them (\textbf{QBS}), with function composition as composition of morphisms and identity functions as identity morphisms.
\end{definition}





To study probability theory via quasi-Borel spaces, there is a notion of probability measure on them.
\begin{definition}[Probability measure on quasi-Borel space.]
\label{def:probmeas}
A probability measure on a quasi-Borel space \((X, M_X)\) is a pair \((\alpha, \mu)\) where \(\alpha \in M_X\) and \(\mu\) is a probability measure on \(\mathbb{R}\). Here \(\mu\) is a probability measure from the standard measure theory.
\end{definition}
The above definition reflects the usual notion of a probability measure on a measurable space which is induced via pushing-forward through a random variable (a measurable function) from the sample space with a probability measure. Another way of phrasing the notion of probability measure is that with a source of randomness from \(\mathbb{R}\) and a distribution \(\mu\) on \(\mathbb{R}\), we observe the effect of the process \(\alpha \in M_X\) in \(X\). From this notion of probability measure, there is generalized version of Giry monad in \textbf{QBS} which is referred as the probability monad.

\begin{lemma}[Probability monad in \textbf{QBS}, due to Heunen et al.~\cite{Heunen2017}]
\label{lem:probMonad}
The set of all probability measures on a quasi-Borel space naturally forms a quasi-Borel space (see Heunen et al.~\cite{Heunen2017}). The endofunctor \(\prob\) sending a quasi-Borel \(X\) to the space \(\prob{X}\) of probability measures on \(X\) (quotienting out a suitable notion of equivalent measures) gives rise to a commutative monad in \textbf{QBS} with Kleisli composition $\fatsemi_{\prob{}}: \mathbf{QBS}(A, \prob{B}) \times \mathbf{QBS}(B, \prob{C}) \rightarrow \mathbf{QBS}(A, \prob{C})$ and unit natural transformation $\eta: \mathbb{I} \rightarrow \prob{}$ from the identity functor $\mathbb{I}$.
\end{lemma}

\vspace{-1em}
\subsection{Wiring diagram operads and algebras over them}
\label{subsec:wiringoperad}
Rupel and Spivak~\cite{Rupel2013} introduced wiring diagrams as a formal graphical language to represent the structure of composite processes. Despite their geometric presentation, wiring diagrams should be understood as combinatorial entities. Every wiring diagram is a combinatorial scheme of composing blank boxes and directed wires, and Patterson et al.~\cite{Patterson2021} showed that wiring diagrams provide a combinatorial normal form for morphisms in SMCs. This makes wiring diagrams suitable to be represented in a data structure. This paper employs acyclic wiring diagrams as a syntax for specifying morphisms in categories.

Mathematically, wiring diagrams are expressed via the notion of a \textit{symmetric colored operad}. Loosely speaking, a colored operad is a category except that the hom-sets are allowed to go from a one finite set of objects to another finite set of objects. Operads capture algebraic structures in SMCs. We utilize the specific definition of an operad found in Spivak~\cite{Spivak2013}. In short, an operad \(\mathcal{O}\) is encoded by two pieces of data: structure and laws. The structure of \(\mathcal{O}\) consists of a) objects; b) morphisms; c) specified identity morphisms on objects; and d) a composition formula for morphisms. The structure is required to satisfy an identity law and an associativity law. We give a quick overview of the \(\tau\)-typed operad \(\mathcal{W_\tau}\) of acyclic wiring diagrams for the convenience of readers. The full definition can be found in Patterson~\cite{Patterson2021}.

\begin{definition}[Operad of acyclic wiring diagrams]
Let \(\tau\) be a set. A \(\tau\)-typed set is an object in the slice category \(\mathtt{Set}/\tau\). The operad \(\mathcal{W_\tau}\) has the following structure:
\begin{itemize}
    \item \textit{Objects}. An object (\textbf{box}) \(\mathbf{t}\) of \(\mathcal{W_\tau}\) is a pair of \(\tau\)-typed finite sets. Pictorially \(\mathbf{t}=(\mathbf{t}_{-}, \mathbf{t}_{+})\) is a blank box with a finite number of \(\tau\)-typed input and output wires \footnote{The wires are directed from left to right.}.
    \begin{center}
        \scalebox{1.4}{\tikzfig{box}}
    \end{center}

    \item \textit{Morphisms}. A morphism (\textbf{wiring diagram}) \(\Phi\) from a set of indexed boxes \(\mathbf{t}^{1},\ldots,\mathbf{t}^n\) to a box \(\mathbf{v}\) is a span in category \(\mathbf{Bij}_\tau\) which is the category of \(\tau\)-typed finite sets and bijective functions between them. The morphism is denoted as \(\Phi: \mathbf{t}^{1},\ldots,\mathbf{t}^{n} \rightarrow \mathbf{v}\). Pictorially \(\Phi\) is a wiring diagram with \(\mathbf{t}^{1},\ldots,\mathbf{t}^{n}\) as inner boxes and \(\mathbf{v}\) as outer box. More importantly, \(\Phi\) encodes how the wires are connected. Additionally, the indexed boxes \(\mathbf{t}^{1},\ldots,\mathbf{t}^{n}\) must satisfy a \emph{progress condition} which ensures that there is no cycle in a wiring diagram. For example:
    \begin{center}
        \scalebox{0.8}{\tikzfig{wiring1}}
    \end{center}
    \item \textit{Identities}. The identity morphism \(\mathbf{Id_t}\) on box \(\mathbf{t}\) is the identity span associated with \(\mathbf{t}\). Pictorially, it is a wiring diagram with no internal box, i.e., there is only one wire going right through the diagram. \vspace{-0.5cm}
    \begin{center}
        \scalebox{1.4}{\tikzfig{identity}}
    \end{center}
    \item \textit{Composition formula}. Given wiring diagram \(\Psi: \mathbf{s}^{1}, \ldots, \mathbf{s}^{m} \rightarrow \mathbf{t}^{i} \text { and } \Phi: \mathbf{t}^{1}, \ldots, \mathbf{t}^{n} \rightarrow \mathbf{v}\), their \(i\)-th partial composition is denoted as \(\Psi {\fatsemi}_i \Phi\). We follow the notation from Patterson, Spivak and Vagner that \(\fatsemi\) gives composition of morphisms in operad and the order of composition is left to right. 
    The composition is a new wiring diagram:
    \[\Psi {\fatsemi}_i \Phi: \mathbf{t}^{1}, \ldots, \mathbf{t}^{i - 1}, \mathbf{s}^{1}, \ldots, \mathbf{s}^{m}, \mathbf{t}^{i + 1}, \ldots ,\mathbf{t}^{n} \rightarrow \mathbf{v}\]
    The formula says that the composition slots the whole wiring diagram \(\Psi\) into the inner box \(\mathbf{t}^{i}\) in wiring diagram \(\Phi\).
    \begin{center}
        \scalebox{0.7}{\tikzfig{composition}}
    \end{center}

    It can be shown that composition satisfies the progress condition which ensures that the wiring diagram is acyclic.
\end{itemize}
The necessary identity law and associativity law are left to readers to check.
\end{definition}

Operad algebras take composition structures in operads and map them to a meaning in some SMC. A $\mathcal{W}_{Ob(\mathcal{C})}$-algebra is an operad functor $H: \mathcal{W}_{Ob(\mathcal{C})} \rightarrow \mathcal{O}_{\mathcal{V}}$, where the latter is the operad underlying \(\mathcal{V}\).

\begin{proposition}[Enriched SMCs have enriched operad algebras]
\label{prop:enopalgebras}
Each \(\mathcal{V}\)-enriched strict SMC \(\mathcal{C}\) has an operad of wiring diagrams \(\mathcal{W}_{Ob(\mathcal{C})}\) and a \(\mathcal{V}\)-enriched algebra \(H: \mathcal{W}_{Ob(\mathcal{C})} \rightarrow \mathcal{O}_{\mathcal{V}}\). This operad provides a ``normal form'' for \(\mathcal{C}\), in the sense that the \(\mathcal{V}\)-enriched SMC arising from the algebra and \(\mathcal{C}\) itself.
\end{proposition}
\begin{proof}
Definition 6.63 in Fong and Spivak~\cite{Fong2019} shows how to construct the operad \(\mathcal{O}_{\mathcal{V}}\) underlying \(\mathcal{V}\). Theorem 5.3 in Patterson~\cite{Patterson2021} then shows how to obtain the algebra \(H: \mathcal{W}_{Ob(\mathcal{C})} \rightarrow \mathcal{O}_{\mathcal{V}}\), substituting \(\mathcal{O}_\mathcal{V}\) for the operad \texttt{Set} and hom-objects for hom-sets.
\end{proof}
We therefore understand the \(\mathcal{V}\)-enriched algebra $H$ as
\begin{itemize}
    \item Sending a box $(\mathbf{t}_{-}, \mathbf{t}_{+}) \in \mathcal{W}_{Ob(\mathcal{C})}$ to the hom-object $\mathcal{C}(\mathbf{t}_{-}, \mathbf{t}_{+}) \in \mathcal{V}$ whose shapes it specifies.
    \item Sending a wiring diagram $\Phi: \mathbf{t}^1 \times \ldots \times \mathbf{t}^n \rightarrow \mathbf{v} $ to the morphism $H(\Phi): \mathcal{C}(\mathbf{t}^{1}_{-}, \mathbf{t}^{1}_{+}) \otimes \ldots \otimes \mathcal{C}(\mathbf{t}^{n}_{-}, \mathbf{t}^{n}_{+}) \rightarrow \mathcal{C}(\mathbf{v}_{-}, \mathbf{v}_{+})$ from the boxes' hom-objects to the whole diagram's hom-object.
\end{itemize}

\vspace{-1em}
\subsection{Free monoidal categories over quivers}
\label{subsec:freecats}
Learning structures of composition will require specifying, a priori, some set of generating objects and morphisms between them. However, a specific structure of possible compositions may have semantics in several concrete categories, depending on the needs of the application. The free category prior therefore defers semantics to specific applications, considering only structure in the generative model itself.

The free category prior requires, as a hyperparameter, a directed multigraph $G=(V, E)$ as a nerve. Each vertex $v \in V$ must have a label $\sigma(v)$ drawn from $\bigcup_{n \in \mathbb{N}} \Sigma^{n}$ (the Kleene closure of a finite symbol-set $\Sigma$), and each label in $\Sigma^1$ must appear on a vertex. A unique label $I \in \Sigma$ is reserved to denote in the graph the vertex underlying the monoidal unit. Each edge has a ``domain'' $\text{dom}(e)$ and a ``codomain'' $\text{cod}(e)$. We write $E(A, B)$ to denote the edge-set between $A, B \in V$, and write (assuming \(\emptyset = E^0 \))
\begin{align*}
    P(A, B) &:= \bigcup_{n\in\mathbb{N}} \{p\in E^{n} : \text{dom}(p_1) = A, \text{cod}(p_n) = B \}
\end{align*}
for the path-set from $A$ to $B$. We impose the following condition on the nerve-graph $G$.

\begin{condition}[All non-unit generating objects have points]
\label{cond:reachability}
Each vertex $v\in V$  with $|\sigma(v)|=1$, $\sigma(v)\neq I$, and a nonzero out-degree must have a path into it from the unit
\begin{align*}
    \forall v\in V. (|\sigma(v)| = 1) \wedge (\text{deg}^{+}(v) > 0) \rightarrow (|P(I, v)| > 0).
\end{align*}
\end{condition}

\begin{definition}[Directed multigraph with monoidal points]
\label{def:monoidalpoints}
Given a directed multigraph $G$ meeting Condition~\ref{cond:reachability}, the quiver $Q = (V_Q, E_Q)$ where
\begin{align*}
    V_Q &= V \cup \{I\} \\
    E_Q &= E \cup \bigcup_{ \{ (\sigma(v_1) \sigma(v_2)) \in V : (I, v_1), (I, v_2) \in E \}} \{(I, \sigma(v_1) \sigma(v_2))\}
\end{align*}
has paths from the unit vertex $I$ to its vertices with labels longer than one symbol. Adding the extra edges to the quiver ensures that any two generating vertices with paths from the unit give rise to a compound vertex with a path from the unit. Note that the original multigraph $G$ may already include a vertex for $I$; this construction simply ensures one is added if it doesn't.
\end{definition}

\begin{definition}[Free monoidal category on a directed multigraph]
\label{def:freecat}
Assume that $Q=(V_Q, E_Q)$ is a quiver constructed via Definition~\ref{def:monoidalpoints}. The free monoidal category $\freeCat{Q}$ (notation due to Gavranovic~\cite{Gavranovic2019}) on that quiver has as objects finite Cartesian products of vertex labels
\begin{align*}
    Ob(\freeCat{Q}) &:= \bigcup_{n \in \mathbb{N}} \{\sigma(v) : v \in V_Q\}^{n}.
\end{align*}
We define the hom-sets for the free monoidal category inductively. For each
\(A, B \in V_Q\) such that \(|\sigma(A)|=1, |\sigma(B)|=1\),
\begin{align*}
  \freeCat{Q}(\sigma(A), \sigma(B)) := P(A, B).  
\end{align*}
For $A, B, C, D \in \freeCat{Q}$, none of which equals $I$,
\begin{align*}
    \freeCat{Q}(\sigma(A) \sigma(C), \sigma(B) \sigma(D)) &:= \{(f, g) : f \in \freeCat{Q}(\sigma(A), \sigma(B)), g \in \freeCat{Q}(\sigma(C), \sigma(D)) \}.
\end{align*}
Finally, for each \(A \in \freeCat{Q}\) we define the identity morphism to be
\begin{align*}
    id_A &= \emptyset \in \freeCat{Q}(A, A).
\end{align*}
The above construction gives the free (Cartesian) monoidal product on paths in a graph, with the monoidal action on objects being concatenation of vertex labels. This category has as morphisms finite tuples of paths between the respect elements of finite tuples of vertices.
\end{definition}

\vspace{-1em}
\section{Probabilistic categorical generative modeling}
\label{sec:categoricalpgm}

\subsection{Assigning probabilities to morphisms by enrichment in a Markov category}
\label{subsec:homdists}
Definition~\ref{def:freecat} defined the free category over a given quiver, giving a purely syntactic description of compositional structure.
Constructing a probabilistic generative model over such structure will require defining a version of the free category $\freeCat{Q}$ enriched in a Markov category, in our case \textbf{QBS}. This requires first showing that hom-sets in $\freeCat{Q}$ admit the structure of objects in the enriching category.
\begin{lemma}[Hom-sets in free (monoidal) categories admit the structure of quasi-Borel spaces]
\label{lem:randompaths}
Let $G$ be a directed multigraph and $\freeCat{Q}$ its free monoidal category as defined above. Each hom-set $\freeCat{Q}(A, B)$ can admit the structure of a quasi-Borel space.
\end{lemma}
\begin{proof}
An object in \textbf{QBS} is a pair $(X, M_X)$ with $X$ a set and $M_X \subseteq [\mathbb{R} \rightarrow X]$ a set of primitive random variables over that space. For each $A, B \in V$ we already have a hom-set $\freeCat{Q}(A, B)$, and just need to construct a corresponding set of random variables. We take advantage of the countable-discrete nature of the underlying path-set $\freeCat{Q}(A, B)$ to construct the standard discrete $\sigma$-algebra over the set, which we call $\Sigma_{Q(A, B)}$. We then call $M_{B^A}$ the set of measurable functions $\mathbb{R} \rightarrow \freeCat{Q}(A, B)$. We therefore have $(\freeCat{Q}(A, B), M_{B^A})) \in \textbf{QBS}$ as required.
\end{proof}

Defining quasi-Borel spaces with path-sets as their sample spaces enables defining a probabilistically enriched free category. Recall from Lemma~\ref{lem:probMonad}, $\prob{}$ is the probability monad in \textbf{QBS}. Furthermore, we define the enrichment here with a twist: since we require a probabilistic generative model, composition builds up joint distributions, without marginalizing away intermediate spaces.
\begin{definition}[Probabilistic generative free category]
\label{def:pgcat}
The probabilistic generative category $\p{Q}$ is a version of $\freeCat{Q}$ enriched in $\mathbf{QBS}$. We construct it by specifying
\begin{itemize}
    \item Its objects $Ob(\p{Q}) = Ob(\freeCat{Q})$;
    \item For each $(A, B) \in Ob(\p{Q}) \times Ob(\p{Q})$ the hom-object \(\p{Q}(A, B) = \prob{(\freeCat{Q}(A, B), M_{B^A})} \in \mathbf{QBS}\);
    \item For each $A \in Ob(\p{Q})$ the identity element
    \begin{align*}
        id_{A} &: \mathbf{QBS}(I, \prob{(\freeCat{Q}(A, A), M_{A^A})}) \\
        id_{A} &= I \mapsto \eta_{\freeCat{Q}(A, A)}(\mathbf{const}_{\emptyset}: (\freeCat{Q}(A, A), M_{A^A}))
    \end{align*}
    gives a Dirac delta distribution over the empty path in \(\freeCat{Q}(A, A)\);
    \item For each $A, B, C \in Ob(\p{Q})$ a way of composing morphisms, in this case
    \begin{align*}
        \fatsemi_{A,B,C} &: \p{Q}(A, B) \odot \p{Q}(B, C) \rightarrow \p{Q}(A, C) \\
        f \fatsemi_{A,B,C} g &= (f \odot_{\mathbf{QBS}} g) \fatsemi_{\prob{}} (x \odot y \mapsto \eta_{\freeCat{Q}(A, C)}(x \fatsemi_{\freeCat{Q}} y)),
    \end{align*}
    pushes-forward the joint distribution defined by $f$ and $g$ into a distribution over $\freeCat{Q}(A, C)$.
    \item \(\p{Q}\) inherits its monoidal structure from \textbf{QBS}
    \begin{align*}
        \odot_{A, B, C D} &: \p{Q}(A, B) \times \p{Q}(C, D) \rightarrow \p{Q}(A \odot C, B \odot D) \\
        f \odot_{A, B, C, D} g &= (f \odot_{\mathbf{QBS}} g).
    \end{align*}
    The usual probabilistic composition uses a random outcome from one distribution to parameterize another. Here we take their monoidal product, representing their joint distribution.
\end{itemize}
\end{definition}
Above we defined operads $\mathcal{W}_{Ob(\mathcal{C})}$ of wiring diagrams, and algebras over them. Now, having an enriched category $\p{Q}$, we can demonstrate the existence of an enriched operad algebra mapping wiring diagrams $\Phi$ into $\p{Q}$.
\begin{lemma}[Existence of algebras of wiring diagrams over the probabilistic generative free category]
\label{lem:algebras}
We consider the concrete setting where $\mathcal{C}=\p{Q}$, the probabilistic generative free category, with the enriching category being $\mathcal{V}=\mathbf{QBS}$. An operad algebra in this setting has the form
\(H: \mathcal{W}_{Ob(\mathcal{C})} \rightarrow Op(\mathbf{QBS})\), which sends a box $\mathbf{t} = (\mathbf{t}_{-}, \mathbf{t}_{+}) \in \mathcal{W}_{Ob(\mathcal{C})}$ to the quasi-Borel space $\p{Q}(\mathbf{t}_{-}, \mathbf{t}_{+}) \in \mathbf{QBS}$ and the collection of hom-distributions in a wiring diagram $\Phi$ to their joint distribution within the space of distributions over paths from the input and output types of the diagram as a whole.
\end{lemma}
\begin{proof}
Definition~\ref{def:pgcat} (of $\p{Q}$) gives the machinery for forming $\tau$-typed hom-distributions, and joint hom-distributions, in \textbf{QBS}. Since \textbf{QBS} is an SMC and $\p{Q}$ inherits its monoidal structure, $\p{Q}$ supports an operad algebra as an instantiation of Proposition~\ref{prop:enopalgebras} above. This construction requires that the hom-distribution assigned to each box in a wiring diagram be conditionally independent of all others, given the wiring diagram itself.
\vspace{-1em}
\end{proof}

\vspace{-1em}
\subsection{The free category prior over morphisms}
\label{subsec:freecatprior}
Definition~\ref{def:pgcat} demonstrates that free categories \emph{allow} enrichment with joint distributions, and similarly, Lemma~\ref{lem:algebras} demonstrates the existence of operad algebras taking wiring diagrams into joint distributions over morphisms in the free category. These existence proofs alone do not constitute a generative model: that requires a distribution with constructive procedures for sampling and density evaluation. This section will define such procedures and the joint distribution they induce on morphisms.

A probabilistic generative model over some space must generally impose some notion of simplicity, assigning higher prior probability to simpler elements of the space. Free monoidal categories have only two kinds of structure that give rise to complexity: sequential and parallel composition. We hypothesize that path-length and product-width in the underlying quiver may serve as a reasonable inductive bias. Shorter, ``narrower'' paths should have higher probability, but no path should have zero probability.

We thus begin with our quiver $Q$ representing the free category, and a wiring diagram $\Phi$. Each box $\mathbf{t}^{i} \in \text{dom}(\Phi)$ consists of a source and target $\mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+} \in V_Q$. To generate morphisms, we need a policy
\begin{align*}
    \pi(e \mid v, \mathbf{t}_{+}) &: E_Q(v, \cdot) \rightarrow (0, 1]
\end{align*}
that randomly selects edges out of $v$, yielding short paths to the destination $\mathbf{t}_{+}$. This is a stochastic short-paths problem, generalizing the all-destinations shortest-path problem (which has itself inspired a learning problem \cite{Jurgenson2020}) to a setting of probabilistic transitions.

We construct our stochastic short-paths problem by transforming the original nerve quiver $Q$ into a simple directed bipartite graph $G'=(V', E')$ for
\begin{align*}
   V' &= V_Q \cup E_Q
   &
   E' &= \bigcup_{e \in E_Q} \{ (\text{dom}(e), e), (e, \text{cod}(e))  \}.
\end{align*}
This directed graph has two sets of vertices: one of the generating objects $v \in V_Q$ and another of the generating morphisms $e \in E_Q$. In this graph, generating object vertices only receive edges from generating morphism vertices, and vice-versa, while each generating morphism vertex has only a single exiting edge. No two vertices have multiple edges between them.

\begin{lemma}[Equivalence of free categories under conversion from quiver to directed bipartite graph]
\label{lem:graphequivalence}
The original free category $\freeCat{Q}$ is equivalent to the one generated by taking the directed bipartite graph $G'$, converting it back into a quiver $Q'$ according to the above construction, and generating a free category $\freeCat{Q'}$ from that.
\end{lemma}
\begin{proof}
Representing both graphs via their adjacency matrices will demonstrate equivalence of the graphs, with proofs due to Brualdi~\cite{Brualdi1980} and others as old results. Equivalence of the underlying graphs then produces an equivalence of their free categories.
\end{proof}
We represent $Q$ as $G'$ because the latter supports representing our policy as a transition kernel $\pi \in \mathbf{QBS}(V', V')$. Given the directed adjacency matrix $A' \in \mathbb{R}^{|V'| \times |V'|}$, Estrada and Hatano~\cite{Estrada2008} defined the communicability between $\mathbf{t}^{i}_{-}$ and $\mathbf{t}^{i}_{+}$ as
\begin{align}
    C_{\mathbf{t}^{i}_{-},\mathbf{t}^{i}_{+}} &= \sum_{n=1}^{\infty} \frac{({A'}^{l})_{\mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+}}}{n!} = (e^{A'})_{\mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+}}.
\end{align}
This communicability measure, also known as the matrix exponential, measures the number of paths in the underlying graph, weighted by their length. Its negative logarithm
\begin{align}
\label{eq:quasimetric}
    d(\mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+}) &= -\log (C)_{\mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+}}   
\end{align}
provides a quasimetric\footnote{Lacking symmetry due to directedness of edges.} of ``intuitive distance'' on the graph \cite{baram2018intuitive}. Intuitive distance in a graph penalizes actual path length, while rewarding paths connecting many sources and targets.

We therefore parameterize the policy in log-space $\log \pi(e \mid v; \mathbf{t}_{+}, Q)$, for global hyperparameters $Q$ and $\mathbf{t}_{+} \in V_Q$, with global random variables
\begin{itemize}
    \item $\mathbf{w} \sim \mathcal{N}(\Vec{0}, \Vec{1}) \in \mathbb{R}^{|V'|}$: a vector of single-step ``preferences'' over objects and morphisms sampled from a standard Gaussian prior;
    \item $\beta \sim \gamma(1, 1) \in \mathbb{R}_{+}$: a positive inverse-temperature specifying the ``confidence'' of the policy, sampled from a Gamma prior;
\end{itemize}
and the local random variable $v \in V_Q$. $v$ is a ``present location'' in the graph $G'$, obtained autoregressively. The policy is then written in terms of its surprisal as
\begin{align}
\label{eq:policy}
    -\log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q) &\propto -\frac{1}{\beta} \log \left(C + (A')\text{diag}(\mathbf{w}) \right)_{\text{cod}(e), \mathbf{t}_{+}},
\end{align}
and we have the following theorem relating the policy to the global structure of the quiver $Q$.
\begin{theorem}[The intuitive distance lower-bounds expected policy surprisal]
\label{thm:distancebound}
Under the prior distributions on the global random variables, the expected unnormalized surprisal of the policy (Equation~\ref{eq:policy}) is at least the intuitive distance (Equation~\ref{eq:quasimetric})
\begin{align*}
    d(\text{cod}(e), \mathbf{t}_{+}) &\leq \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        -\log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }.
\end{align*}
\end{theorem}
\begin{proof}
We begin by expanding the definition of the expectation
\begin{align*}
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        -\log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }
    &=
    \expect{\mathbf{w} \sim \mathcal{N}}{
        \expect{
            \beta \sim \gamma(1, 1)
        }{
            -\frac{1}{\beta} \log \left(C + (A')\text{diag}(\mathbf{w}) \right)_{\text{cod}(e), \mathbf{t}_{+}}
        }
    }
\end{align*}
and recognizing that our Gamma prior has a mean of 1. Substituting the inner expectation away and cancelling, we have
\begin{align*}
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        \log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }
    &=
    \expect{\mathbf{w} \sim \mathcal{N}}{
        \log \left(C + (A')\text{diag}(\mathbf{w}) \right)_{\text{cod}(e), \mathbf{t}_{+}}
    }.
\end{align*}
Jensen's inequality for log-expectations says an expected-log lower bounds a log-expectation
\begin{align*}
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        \log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }
    &\leq
    \log \left(\expect{\mathbf{w} \sim \mathcal{N}}{
        C + (A')\text{diag}(\mathbf{w})
    } \right)_{\text{cod}(e), \mathbf{t}_{+}} \\
    &\leq 
    \log \left(
        C + \expect{\mathbf{w} \sim \mathcal{N}}{(A')\text{diag}(\mathbf{w})}
    \right)_{\text{cod}(e), \mathbf{t}_{+}},
\end{align*}
and we can now substitute in the standard normal's mean
\begin{align*}
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        \log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }
    &\leq
    \log \left(
        C + (A')\text{diag}(\Vec{0})
    \right)_{\text{cod}(e), \mathbf{t}_{+}} \\
    &\leq
    \log \left(
        C
    \right)_{\text{cod}(e), \mathbf{t}_{+}} \\
    -\log \left(
        C
    \right)_{\text{cod}(e), \mathbf{t}_{+}}
    &\leq
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        -\log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    } \\
    d(\text{cod}(e), \mathbf{t}_{+})
    &\leq
    \expect{
        \mathbf{w} \sim \mathcal{N},
        \beta \sim \gamma(1, 1)
    }{
        -\log \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q)
    }.
\end{align*}
\vspace{-1em}
\end{proof}
The policy's parametric form thus normalizes to
\begin{align}
\label{eq:normedpolicy}
    \pi(e \mid v, \mathbf{w}, \beta; \mathbf{t}_{+}, Q) &= \text{softmin}\left(
        -\frac{1}{\beta} \log(C + (A')\text{diag}(\mathbf{w}))_{\cdot, \mathbf{t}_{+}}
    \right)_{\text{cod}(e)}.
\end{align}
Theorem~\ref{thm:distancebound} demonstrates that Equation~\ref{eq:normedpolicy} assigns ``energy'' to finite edge-sets proportionately to a stochastic upper bound on their intuitive distance, scales the energies according to its ``confidence'' $\beta$, and employs soft minimization to assign probabilities to edges. When arrival to $v=\mathbf{t}_{+}$ samples a path $f= (e_1, \ldots, e_L): \mathbf{t}_{-} \rightarrow \mathbf{t}_{+}$ of length $L$, it has probability
\begin{align}
\label{eq:pmorphism}
    \mathbb{P}(f \mid \mathbf{w}, \beta; \mathbf{t}_{-}, \mathbf{t}_{+}, Q) &= \pi(e_1 \mid \mathbf{t}_{-}, \mathbf{w}, \beta; \mathbf{t}_{+}, Q) \prod_{l=2}^{L} \pi(e_l \mid \text{cod}(e_{l-1}), \mathbf{w}, \beta; \mathbf{t}_{+}, Q).
\vspace{-1em}
\end{align}
Equation~\ref{eq:pmorphism} relies on the explicit quiver representation $Q$, and so can only ``connect'' generator objects $\mathbf{t}_{-}, \mathbf{t}_{+} \in V_Q$ to define a hom-distribution $\p{Q}(\mathbf{t}_{-}, \mathbf{t}_{+})$. However, the second term defining $E_Q$ in Definition~\ref{def:monoidalpoints} defines a series of edges in $Q$ mapping $I \rightarrow \p{Q}(\mathbf{t}^{1}_{+} \odot \mathbf{t}^{2}_{+})$. These edges represent ``points'' in the product object, and their semantic content is to recursively invoke the free category prior to generate \(f: I \rightarrow \mathbf{t}^{1}_{+}\), \(g: I \rightarrow \mathbf{t}^{2}_{+}\), and then finally combine them into \(f \odot g: I \rightarrow \mathbf{t}^{1}_{+} \odot \mathbf{t}^{2}_{+}\).

We employ ``macro expansion'' rather than split and simplify boxes in wiring diagrams because some applications may supply their own generating morphisms into product objects. Our approach here simply supplies points in product objects when the component objects support points.

\vspace{-1em}
\subsection{The complete generative model over wiring diagrams}
\label{subsec:joint}
In summary, given a quiver $Q$ and a wiring diagram $\Phi: \mathbf{t}^{1} \times \ldots \times \mathbf{t}^{n} \rightarrow \mathbf{v}$, the sampling process for generating a morphism $f \sim \p{Q}$ fitting $\Phi$ proceeds as
\begin{align*}
    \beta &\sim \gamma(1, 1) \\
    \mathbf{w} &\sim \mathcal{N}(0, 1) \\
    \forall i \in [1..n]. f_{i} &\sim \mathbb{P}(\mathbf{f}_{i} \mid \mathbf{w}, \beta; \mathbf{t}^{i}_{-}, \mathbf{t}^{i}_{+}, Q).
\end{align*}
This procedure induces a joint distribution over all latent variables
\begin{align}
    \label{eq:generative}
    p(f, \mathbf{w}, \beta; \Phi, Q) &= p(\beta) p(\mathbf{w}) \prod_{\textbf{t} \in \Phi} \mathbb{P}(f_{\textbf{t}} \mid \mathbf{w}, \beta; \textbf{t}, Q).
\end{align}
Finally, in order to learn morphisms, an application must supply both a concrete semantic functor $F: \freeCat{Q} \rightarrow \mathcal{C}$ into an arbitrary SMC $\mathcal{C}$ and a likelihood $p(x \mid F(f))$ relating morphisms to data.
\begin{theorem}[Bayesian learning with free category priors]
Assuming that the semantic category $\mathcal{C}$ supports enrichment in \textbf{QBS} via joint distributions, the free category prior indeed acts as a prior. Sampling a morphism $f \sim p(f; \Phi, Q)$ from the prior, assigning semantics $F(f)$ to that morphism, and evaluating a likelihood $p(x \mid F(f))$ relating those semantics to data induces a joint density and Bayesian inverse.
\end{theorem}
\begin{proof}
We can ``lift'' the semantics $F: \freeCat{Q} \rightarrow \mathcal{C}$ into a functor $\prob{F}: \p{Q} \rightarrow \mathbf{QBS}-\mathcal{C}$ by defining the action on morphisms
\begin{align*}
    \prob{F}(\cdot) &: \p{Q}(A, B) \rightarrow \mathbf{QBS}-\mathcal{C}(F(A), F(B)) \\
    \prob{F}(p) &= p \fatsemi_{\prob{}} (f \mapsto \eta_{F(B)}(F(f))),
\end{align*}
to push-forward \(\p{Q}(A, B)\) via $F(f)$. The semantics and likelihood then define a joint density
\begin{align}
    \label{eq:genjoint}
    p(x, f, \mathbf{w}, \beta; \Phi, Q) &= p(x \mid F(f)) p(f, \mathbf{w}, \beta; \Phi, Q)
\end{align}
with a Bayesian inversion
\begin{align}
\label{eq:bayesinverse}
    p(f, \mathbf{w}, \beta \mid x; \Phi, Q) &= \frac{
        p(x, f, \mathbf{w}, \beta; \Phi, Q)
    }{
        p(x; \Phi, Q)
    }.
\end{align}
\end{proof}
Section~\ref{sec:software} will discuss the software implementation of the free category prior, and an experiment in which a concrete quiver $Q$ is assigned specific semantics and likelihood to perform learning.

\vspace{-1em}
\section{Machine learning with the free category prior}
\label{sec:software}

For machine learning applications, we provide a software implementation of the free category prior. We call it \href{https://github.com/neu-pml/discopyro}{Discopyro}; it is available as a Python library on top of the Discopy~\cite{DeFelice2020} library for computing with morphisms in monoidal categories and the Pyro~\cite{bingham2019pyro} probabilistic programming language. The Discopyro implementation takes the directed multigraph $G$ as a hyperparameter; constructs its corresponding $Q$, $\freeCat{Q}$, and $\p{Q}$; and uses those to conditionally sample morphisms for application-specific wiring diagrams $\Phi$. The Discopyro software supports implicitly associating each edge (generating morphism) $e \in E_Q$ with an instance of \texttt{discopy.monoidal.Diagram}, representing an arbitrary SMC \(\mathcal{C}\) via Discopy.  The user can also apply a Discopy \texttt{Functor} defining the semantics \(F: \freeCat{Q} \rightarrow \mathcal{C}\) to interpret morphisms into the chosen category.

\vspace{-1em}
\subsection{Implementing the sampling process}
\label{subsec:sampling}

To specify wiring diagrams in Python, we have added wiring diagrams to a \href{https://github.com/neu-pml/discopy}{fork of Discopy}. Our implementation is fairly naive and just consists of \texttt{Box}, \texttt{Id} wires, and \texttt{Sequential} and \texttt{Parallel} composites, all subclasses of a \texttt{wiring.Diagram} base class. These come equipped with a \texttt{collapse()} method which implements the canonical catamorphism on the algebraic data type of wiring diagrams. We then implement wiring-diagram algebras for sampling from the $\p{Q}$ representation via F-algebras on wiring diagrams. Python pseudocode describing Discopyro's implementation will denote sequential (categorical) and parallel (monoidal product) compositions by their Discopy operators \texttt{>>} and \texttt{@}.

We represent the free category prior defined in Section~\ref{subsec:freecatprior} as a program that samples from the model in the Pyro~\cite{bingham2019pyro} probabilistic programming language. We give the name \texttt{path\_through} to the sample procedure defined above, and give pseudocode for its implementation in Listing~\ref{alg:path-between}.

\begin{listing*}[h]
    \begin{minted}[escapeinside=||,mathescape=true]{python}
    def path_through(self, wbox, energies, temperature):
        loc = wbox.dom
        f = |$id_A$|
        while loc != wbox.cod:
            logits = [energies[a, wbox.cod] for a in self.out_arrows(loc)]
            idx = pyro.sample(Categorical(logits=logits / temperature))
            arrow = self.out_arrows(loc)[idx]
            if not isinstance(arrow, Box):
                wiring = [wiring.Box(|$I$|, ob)] for ob in arrow.dest.objects]
                wiring = reduce(|$\lambda$| x, y: x @ y, wiring, wiring.Id(|$I$|))
                arrow = self.sample_morphism(wiring, energies)
            f = f >> arrow # Composition of morphisms
            loc = arrow.cod
        return f
    \end{minted}
    \caption{Generative model for short paths from $A$ to $B$ in the nerve $Q$.}
    \label{alg:path-between}
    \vspace{-1em}
\end{listing*}

Listing~\ref{alg:sample-morphism} then extends the short-paths procedure from individual boxes to whole wiring diagrams, implementing the operad algebra of Lemma~\ref{lem:algebras}. Since probability distributions are once again represented by random samplers and wiring diagrams by combinatorial data structures, the algebra over wiring diagrams is written as an $F$-algebra over the wiring diagrams themselves.

\begin{listing*}[h]
    \begin{minted}[escapeinside=||,mathescape=true]{python}
    def __sampler_falg__(self, f, energies, temp):
        if isinstance(f, Id):
            return ar_factory.id(f.dom)
        if isinstance(f, Box):
            return self.path_through(f, energies, temp)
        if isinstance(f, Sequential):
            return reduce(|$\lambda$| f, g: f >> g, arrows)
        if isinstance(f, Parallel):
            return reduce(|$\lambda$| x, y: x @ y, factors, ar_factory.id(Ty()))
    
    def sample_morphism(self, wdiagram, energies, temperature):
        falg = |$\lambda$| f: self.__sampler_falg__(f, energies, temperature)
        return wdiagram.collapse(falg)
    \end{minted}
    \caption{The operad functor mapping wiring diagrams to morphisms in $\freeCat{Q}$}
    \label{alg:sample-morphism}
    \vspace{-1em}
\end{listing*}

\vspace{-1em}
\subsection{Amortized inference with the free category prior}
\label{subsec:amortizedinf}
Learning morphisms from data via a likelihood requires approximately estimating the marginal likelihood $p(x; \Phi, Q)$ and thereby approximating the Bayesian inversion (Equation~\ref{eq:bayesinverse}). Discopyro provides amortized variational inference over its own random variables via neural proposals, whose parameters we label $\phi$, for the ``confidence'' $\beta \sim q_\phi(\beta \mid x)$ and the edge ``preferences'' $\mathbf{w} \sim q_\phi(\mathbf{w} \mid x)$.

The samples from these proposal distributions then parameterize a proposal, identical to the generative model, over $f_\theta \sim \mathbb{P}(f_\theta \mid \mathbf{w}, \beta; \Phi, Q)$. This gives us a complete proposal for the latent variables induced by the free category prior itself, 
\begin{align*}
    q_\phi(f_\theta, \mathbf{w}, \beta \mid x; \Phi, Q) &= \mathbb{P}(f_\theta \mid \mathbf{w}, \beta; \Phi, Q) q_\phi(\beta \mid x) q_\phi(\mathbf{w} \mid x).
\end{align*}

Finally, if an application programmer wants to make use of Discopyro's amortized inference functionality, they must supply a proposal $q_\phi(F(f_\theta) \mid f_\theta, x)$ which approximates the posterior distribution over the morphism's semantics $F(f_\theta)$. This final piece induces a joint proposal density
\begin{align}
    \label{eq:jointproposal}
    q_\phi(F(f_\theta), f_\theta, \mathbf{w}, \beta \mid x; \Phi, Q) &= q_\phi(F(f_\theta) \mid f_\theta, x) q_\phi(f_\theta, \mathbf{w}, \beta \mid x; \Phi, Q),
\end{align}
on the parameters $\mathbf{w}$ and $\beta$, the string diagram structure $f_\theta$ (with internal parameters $\theta$) compatible with the wiring diagram $\Phi$, and the semantics $F(f)$. Maximizing the ELBO (Equation~\ref{eq:elbo})
\begin{align*}
    \mathcal{L}(\theta, \phi) &= \expect{q_\phi}{\log \frac{p_\theta(x, F(f_\theta), f_\theta, \mathbf{w}, \beta; \Phi, G)}{q_\phi(F(f_\theta), f_\theta, \mathbf{w}, \beta \mid x)}}
\end{align*}
by stochastic gradient ascent adjusts the proposal to approximate the true posterior distribution (a process called variational Bayesian inference \cite{Blei2016}). Appendices \ref{app:importanceweighting} and \ref{app:elbo} derive and justify this objective function.

\subsection{Experiment: representing Omniglot with deep generative models}
\label{subsec:experiments}

\begin{table}[t]
    \centering
    \begin{tabular}{c|c|c|c|c}
        \toprule
        Model & Image Size & Learns Structure & log-$\Hat{Z}$ & log-$\Hat{Z}$/dim \\
        \hline 
        Sequential Attention & 28x28 & \ding{55} & -95.5 & -0.1218 \\
        Variational Homoencoder (PixelCNN) & 28x28 & \ding{55} & -61.2 & -0.0780 \\
        Graph VAE & 28x28 & \ding{51} & -104.6 & -0.1334 \\
        Generative Neurosymbolic & 105x105 & \ding{51} & -383.2 & -0.0348 \\
        Free Category DGM (ours) & 28x28 & \ding{51} & -11.6 & \textbf{-0.0148} \\
        \bottomrule
    \end{tabular}
    \caption{Average log model evidence on the Omniglot evaluation set across deep generative models}
    \label{tab:loglikelihoods}
    \vspace{-1em}
\end{table}

As a demonstrative experiment, we constructed a graphical nerve $G$ whose edges (generating morphisms) implemented probabilistic programs in Pyro by inheriting from \texttt{discopy.cartesian.Box}. We trained the resulting free category model on the Omniglot challenge dataset for few-shot learning \cite{Lake2019b}.

Internally, the edges implemented functions consisting of neural building blocks (ie: neural networks elements with probabilistic sampling) for deep generate models. Each generating morphism consisted not only of a domain, codomain, and function but also of a trace-type for its random sampling. Lew et al.~\cite{Lew2020} gave semantics in \textbf{QBS} to traced probabilistic programs  with a monoidal structure over traces\footnote{Note that $\tau$ here refers to trace types, not to wire types in a wiring diagram.}
\begin{align*}
    \fatsemi_{\prob{}_{\tau}} &: \mathbf{QBS}(A, \prob{(B \times \tau)}) \times \mathbf{QBS}(B, \prob{(C \times \tau)}) \rightarrow \mathbf{QBS}(A, \prob{(C \times \tau)}).
\end{align*}
This additional monoidal structure induces an appropriately ``traced''\footnote{In the sense of program execution, not traced categories.} probability monad and Kleisli category, which we call $\prob{\mathbf{QBS}}_{\tau}$ as a subcategory of \textbf{QBS}. The implied semantics functor and likelihood function apply the monadic multiplier of $\mathbb{P}$ in \textbf{QBS} to yield only a single-level probability endofunctor. Our experiment assumes data $x \in \mathbb{R}^{28 \times 28}$, and that morphisms therefore induce the joint likelihood
\begin{align*}
    p_\theta(x \mid z, f) &= \mathcal{N}(\mu{_\theta}(z, f), \tau I) \\
    p(x \mid F(f)) &= p_\theta(x \mid z, f) p_\theta(z \mid f)  
\end{align*}
and semantics proposal over the random variable $x$
\begin{align*}
    q_\phi(F(f) \mid f, x) &= q_\phi(z \mid f^{\dagger}_{\phi}, x).
\end{align*}

The random variable $z$ denotes unobserved random variables occurring in the randomness trace when running $f_\theta$ on data $x$. $f^{\dagger}_{\phi}$ is the result of an endofunctor $F_q: \prob{\mathbf{QBS}}_\tau \rightarrow \prob{\mathbf{QBS}}_\tau$ with action on objects
\begin{align*}
    F_q(A) &= \begin{cases}
        \mathbb{R}^D & \text{if } A=\mathbb{R}^D \\
        A \odot A & \text{otherwise},
    \end{cases}
\end{align*}
and action $F_q(f_\theta) : \prob{\mathbf{QBS}}_{\tau}(A, B) \rightarrow \prob{\mathbf{QBS}}_{\tau}(F_q(B), F_q(A))$ on morphisms $f_\theta: \prob{\mathbf{QBS}}_{\tau}(A, B)$ is $F_q(f_\theta) = f^{\dagger}_{\phi}$. Each $f^\dagger_\phi$ is represented by a neural network with parameters $\phi$. The inference functor ``doubles'' objects in order to produce, for each piece of data and each latent variable, two parameters $\mu, \sigma$ for a Gaussian proposal with the appropriate trace-type.

\begin{figure}[t]
    \centering
    \begin{subfigure}{0.45\columnwidth}
        \centering
        \includegraphics[width=\textwidth]{figures/omniglotrecons.pdf}
        \caption{Characters from the Omniglot evaluation set (above) and our model's reconstructions (below)}
        \label{subfig:reconstructions}
    \end{subfigure}
    \hfill
    \begin{subfigure}{0.45\columnwidth}
        \centering
        \includegraphics[width=\textwidth]{figures/omniglotstringdiagram.pdf}
        \caption{An example string diagram drawn from the approximate posterior of the free category model.}
        \label{subfig:omniglotdiagram}
    \end{subfigure}
    \caption{Reconstructions (left) generated by inference in the diagrammatic generative model (right) on handwritten characters in the Omniglot evaluation set. The string diagram shows a model that generates a glimpse, decodes it into an image canvas via a variational ladder decoder, and then performs a simpler process to generate another glimpse and insert it into the canvas.}
    \label{fig:omniglotresults}
    \vspace{-1em}
\end{figure}

Table~\ref{tab:loglikelihoods} compares the free category prior's performance to other structured generative models (described in Appendix~\ref{app:competing}). We report the estimated log model evidence (estimated as described in Appendix~\ref{app:importanceweighting}). Our free category prior over deep generatives models achieves the best log-evidence per data dimension. Figure~\ref{fig:omniglotresults} shows samples from the trained model's posterior distribution, including reconstruction of evaluation data (Figure~\ref{subfig:reconstructions}) and the morphism sampled for that data (Figure~\ref{subfig:omniglotdiagram}).

\section{Discussion}
\label{sec:discussion}

This paper described a probabilistic generative model over free categories. Section~\ref{sec:categoricalpgm} gave a novel categorical description of distributions over morphisms, by enriching in \textbf{QBS} with joint distributions and push-forwards. It then showed how to sample morphisms from \textbf{QBS}-enriched free monoidal categories via a stochastic short-paths policy. Section~\ref{sec:software} described the software implementation of the free category prior as Discopyro, showing that enriching in a Markov category can also be understood as randomly sampling the computational representations of morphisms in an SMC. It then showed that amortized variational inference in Discopyro achieved competitive log-likelihood in generative modeling of the Omniglot dataset. This section discusses potential future work.

\paragraph{Future improvements to the free category prior}
The underlying quiver $Q$ could be expanded stochastically by randomly choosing and applying commuting diagrams (such as functors, universal constructions, etc.). In the infinite limit, such expansions would give a $Q$ encoding the ``true'' category given by the original graph and the commuting diagrams: a (nonparametric) probability model $\mathbb{P}(Q)$ over the category. This would provide a nonparametric category model as an alternative to nonparametric grammar (i.e.~operad) models~\cite{johnson2006adaptor}. Stochastic memoization~\cite{roy2008stochastic} would enable sampling from that model, with Russian Roulette methods \cite{Xu2019} providing gradient estimates of Equation~\ref{eq:elbo}.

We defined the free category prior in terms of Estrada and Hatano's~\cite{Estrada2008} communicability quasimetric. Boyd et al.~\cite{Boyd2021} recently published a proper metric on quivers and their Markov chains, which might provide a more interpretable foundation for our stochastic short-paths algorithm. Stochastically generalizing shortest-path algorithms may improve the tractability of credit-assignment in policy learning. We plan to explore a subgoal decomposition (e.g.~such as Jurgenson's\cite{Jurgenson2020}) of path-sampling.

\paragraph{Future improvements to the Discopyro implementation}
Discopyro employs amortized variational inference to model the posterior distribution over morphisms. The inference functor mentioned in Section~\ref{subsec:amortizedinf} was defined ad-hoc, meeting only the requirements for constructing faithful inverses \cite{Webb2018} for string diagrams. We used \textbf{QBS} as a semantic category for our learned probabilistic programs, and it is not yet known whether \textbf{QBS} and \textbf{QBS} have all the conditionals necessary to encode Bayesian inversion as a dagger functor. Conjecture~\ref{con:QBSbayes} hypothesizes explicitly that an inference construction similar to ours could approximate Bayesian inversions (in the sense of Cho and Jacobs~\cite{Cho2019}), rather than just a proposal.
\begin{conjecture}[Approximate Bayesian inversions in $\prob{\mathbf{QBS}}$]
\label{con:QBSbayes}
Consider an inference functor $F^{\dagger}$ whose action on objects is identity, with action on morphisms similar to $F_q$ above. Such a functor is a dagger endofunctor $F^{\dagger}: \prob{\mathbf{QBS}} \rightarrow \prob{\mathbf{QBS}}$ sending objects to themselves and morphisms $f: \mathbf{QBS}(A, \prob{B})$ to (approximate) Bayesian inversions $f^\dagger: \mathbf{QBS}(B, \prob{A})$.
\end{conjecture}

\paragraph{Conclusion}
In our experiment the free category prior learned compositional structures from real data. Future applications could include learning program-like representations, a long-term goal for artificial intelligence \cite{Chollet2019,Lake2019b,Nie2020}, or ``cognitive maps'' for spatial navigation \cite{Master2021} in cognitive science \cite{Momennejad2020}.

\nocite{*}
\bibliographystyle{eptcs}
