In probabilistic modelling, joint distributions are often of more interest than their marginals, but the standard composition of stochastic channels is defined by marginalization.
Recently, the notion of `copy-composition' was introduced in order to circumvent this problem and express the chain rule of the relative entropy fibrationally, but while that goal was achieved, copy-composition lacked a satisfactory origin story.
Here, we supply such a story for two standard probabilistic tools: directed and undirected graphical models.
We explain that (directed) Bayesian networks may be understood as “stochastic terms” of product type, in which context copy-composition amounts to a pull-push operation.
Likewise, we show that (undirected) factor graphs compose by copy-composition.
In each case, our construction yields a double fibration of decorated (co)spans.
Along the way, we introduce a useful bifibration of measure kernels, to provide semantics for the notion of stochastic term, which allows us to generalize probabilistic modelling from product to dependent types.

§ INTRODUCTION

Recent work has formalized the “chain rule” of the relative entropy (a.k.a. Kullback-Leibler divergence) as a section of a fibration of statistical games over Bayesian lenses Smithe2023Approximate.
Curiously, however, the base category of this fibration was not a category of stochastic channels (measure kernels), as one might expect, but instead a bicategory of copy-composite channels.
The need for this stemmed from the Chapman-Kolmogorov rule for the composition of kernels, which involves marginalization; and marginalization does not commute with the logarithm defining the relative entropy.
Copy-composition defers this marginalization (indeed, the Chapman-Kolmogorov rule is precisely the marginalization of the intermediate copy), so there is no problem of commutativity, and the chain rule thus obtains.

Although this yields an elegant fibrational structure, copy-composition is not strictly unital, owing to the extra copy produced when copy-composing with the identity.
This means that the base of the fibration is necessarily a bicategory.
Moreover, the construction of this bicategory [2]Smithe2023Approximate was largely ad hoc, based on the similarity to a $\mathbf{CoPara}$ construction [Remark 4]Capucci2022Foundations.
This was despite the evident importance of copy-composition to the statistical problems of interest there: copy-composition constructs joint distributions, which are often of more interest in applications than the composite channels that would yield their marginals.
This can be seen not only via the relative entropy, but also in the context of Bayesian networks, which describe the factorization of a joint distribution according to a graphical structure.
Fong2013Causal studied Bayesian networks from a categorical perspective, making extensive use of comonoid (`copy-discard' Cho2017Disintegration) structure to construct the corresponding joint distributions; see for example the proof of his Theorem 4.5.

In the present submission, we show how copy-composition emerges naturally (but distinctly) from the compositional structure of directed and undirected probabilistic graphical models, thereby replacing the earlier arbitrariness with something structurally meaningful.
In the directed case, the key observation is that a Bayesian network may be understood as a “stochastic term” of some displayed type (which is invariably a product), equipped with a distribution (the `prior') over its context.
Identifying types with bundles and terms with sections, this means understanding the factors of a Bayesian network as stochastic sections; copy-composition then emerges via a pull-push operation.
In the undirected case, one observes that the `factors' of a factor graph are costates[
A state in a monoidal category is a morphism out of the monoidal unit; a costate is a morphism into the monoidal unit.]
in a copy-discard category, and that copy-composition amounts to a kind of gluing.
In both cases, copy-composition appears as the horizontal composition operation of a pseudo double category, thereby extending the earlier bicategorical story.
These double categories[
We take “double category” henceforth to mean pseudo double category, oriented such that composition is strict in the vertical category and weak in the horizontal.]
are in fact double fibrations, following the generalized decorated (co)span construction of Patterson2023Structured: in the directed case, one decorates spans of display maps with sections; in the undirected case, one decorates cospans with factors.

§ DIRECTED MODELS: PULL-PUSH STOCHASTIC SECTIONS

A Bayesian network is a distribution (or measure) on a product space that factorizes into a product of conditional distributions (or measure kernels) that matches the structure of a directed acyclic graph [Definition 3.7]Fong2013Causal.
Interpreting this idea in a category of stochastic channels (such as measure kernels between measurable spaces), [Theorem 4.5]Fong2013Causal showed that any Bayesian network can be written as a state $1\to \otimes_j\,X_j$ that factorizes as the sequential composition of morphisms of the form

\[\scalebox{0.85}{\tikzfig{img/bayes-net-factor-1}}\]

where $\mathrm{pa}(i)$ denotes the set of parents of the vertex $i$, and where $j<i$ iff there is no directed path from $i$ to $j$ (Fong calls this the `ancestral' order on the vertices).

Each factor $X_i\mid \mathrm{pa}(i)$ only appears in the composite diagram as precomposed by a copier applied to its parents, and tensored with the identities of its grandparents.
Interpreting the analogous string diagram

\[\scalebox{0.85}{\tikzfig{img/graph-f}}\]

in $\Set$, we see that it corresponds to the graph of the function $f:X\to Y$, which is a section of the product projection $X\times Y\to X$; in other words, a term of $X\times Y$ over the context $X$.
Moreover, `tensoring' this diagram with extra objects $W$ corresponds to pulling back the section along the projection $W\times X\to X$; in other words, extending the context by $W$.
Thus, whereas Fong2013Causal constructed the preceding diagram by hand, with the right categorical setting we will be able to interpret it as resulting from standard type-theoretic operations.
Our first task will therefore be to establish a bifibration of measure kernels in which these operations may be interpreted.
Then, we will construct a double category whose horizontal composition implements these operations (and thus copy-composition) via `pull-push' in the bifibration.

§.§ A bifibration of measure kernels

The classic categorical semantics for dependent type theory is in fibrations Jacobs1999Categorical,nLabauthors2024Categorical: the base category is interpreted as a category of `contexts'; the fibre over an object interprets the types in the corresponding context; elements in a fibre interpret terms; and pullback (base change) interprets substitution.
The classic example is the codomain fibration of a finitely complete category, in which bundles `display' types, and their sections are corresponding terms.
The category $\Meas$ of measurable spaces and measurable functions between them is a finitely complete category, and so this story may be told there.
But measurable functions are still deterministic; they are not kernels.
However, we may replace the functions in the fibres by kernels and still obtain a fibration, which is the purpose of this section.
In fact, we will obtain a bifibration.
We begin by making the notion of kernel more precise.

Suppose $X$ and $Y$ are measurable spaces; we write $\Sigma_X$ and $\Sigma_Y$ for their $\sigma$-algebra structures.
A (measure) kernel $k:X\kto Y$ is a function $k:X\times\Sigma_Y\to[0,\infty]$ that is measurable in its first argument and a measure in its second; i.e. such that $k(-,B):X\to[0,\infty]$ is measurable for all $B\in\Sigma_Y$ and $k(x,-):\Sigma_Y\to[0,\infty]$ is a (positive) measure for all $x\in X$.

General kernels are too ill-behaved to yield a well-defined category[
They may not satisfy a “Fubini theorem”, meaning that repeated integrals do not commute: consequently, Chapman-Kolmogorov composition (introduced below) would not be associative.],
but for the purposes of sec:fg, we will want more than just probability kernels (those that measure $1$ on the whole codomain).
Staton2017Commutative showed that s-finite kernels (countable sums of finite kernels) are expressive enough for statistical modelling while also yielding a well-defined category, and it is these that we shall employ.

Suppose $k_1,\dots,k_n,\dots$ is a countable sequence of kernels $X\kto Y$.
Then there is a kernel $\sum_i k_i:X\kto Y$ given by their sum,
$ \left( {\textstyle\sum_i} k_i \right)(x,B) := \sum_i k_i(x,B) $.

Suppose $k:X\kto Y$ is a kernel. Then:

* $k$ is finite if there is some $r<\infty$ such that, for all $x\in X$, $k(x,Y) < r$;

* $k$ is s-finite if there is a countable sequence of finite kernels $k_1,\dots$ such that $k = \sum_i k_i$.

[Theorem 4]Staton2017Commutative tells us that s-finite kernels satisfy Fubini's theorem and thus yield a well-defined category.
Composition of kernels $X\kto Y$ and $Y\kto Z$ is by Chapman-Kolmogorov; that is, by integrating over $Y$.

The objects of $\sfKrn$ are measurable spaces.
Morphisms from $X$ to $Y$ are s-finite kernels $X\kto Y$.
Given kernels $X\xkto{g}Y\xkto{h}Z$, their composite $h\circ g:X\kto Z$ is defined by

$$ h\circ g : (x,C) \mapsto \int_{y:Y} g(x,\d y)\, h(y, C) $$

for $x\in X$ and $C\in \Sigma_Z$.
The identity kernel $\id_X:X\kto X$ is given by Dirac delta: $\id_X(x,-) := \delta_x(-)$.
Equivalently, let $[x\in A]$ denote the indicator function

$$ [x\in A] = \begin{cases} 1 & \text{if $x\in A$;} \\ 0 & \text{otherwise.} \end{cases} $$

Then $\id_X(x,A) = [x\in A]$.

We will use $\sfKrn$ to define a bifibration $\Ka$ over $\Meas$, such that the objects of each fibre $\Ka_B$ will be (deterministic, measurable) functions into $B$, and the morphisms $(E,\pi)\kto(E',\pi')$ in $\Ka_B$ will be kernels $E\kto E'$ “fibrewise over $B$”.
To form this idea into a precise definition, we need to be able to compose (or push forward) a kernel with (or along) a deterministic function.

Suppose $f:Y\to Z$ is a measurable function.
Then there is a kernel $\delta_f:Y\kto Z$ defined by $\delta_f(y,C) = [f(y)\in C]$.
This yields a functor $\delta_{(-)} : \Meas\to\sfKrn$.

Let $B$ be a measurable space; we define a corresponding category $\Ka_B$.
Its objects are pairs $(E,p)$ of a measurable space $E$ and a measurable function $p:E\to B$.
A morphism $k:(E,p)\to(E',p')$ is a kernel $k:E\kto E'$ such that $\delta_{p'}\circ k = \delta_p$; we call these morphisms kernels over $B$.
Composition of morphisms is given by the composition of the corresponding kernels; identities are given by identity kernels.
(It is easy to see that this yields a well-defined category.)

To see that the morphisms of $\Ka_B$ really are kernels fibrewise over $B$, let us introduce some notation.

[Fibre notation]
Suppose $p:E\to B$ is a function and $b:J\to B$ is a generalized element of $B$ (another function).
The fibre of $p$ over $b$ is given by the pullback of $p$ along $b$:

\[\begin{tikzcd}[cramped,sep=scriptsize]
{p[b]} & E \\
J & B
\arrow["{\pi_E}", from=1-1, to=1-2]
\arrow["p", from=1-2, to=2-2]
\arrow["b"', from=2-1, to=2-2]
\arrow["{b^*p}"', from=1-1, to=2-1]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-1, to=2-2]
\end{tikzcd}\]

We denote the fibre by $p[b]\xto{b^*p}J$.

Suppose $k:(E,p)\kto(E,p')$ is a kernel over $B$, and $b:J\to B$ is a generalized element of $B$.
Then $k$ restricts to a kernel $k[b]:p[b]\kto p'[b]$.

Let $\pi_E:p[b]\to E$ be the projection as in the preceding pullback square; and let $\pi_{E'}:p'[b]\to E'$ be likewise for $p'$.
Then we have a kernel $k[b]:p[b]\times\Sigma_{p'[b]}\to[0,\infty]$ by setting $k[b](e_b,U_b) := k\bigl(\pi_E(e_b),\pi_{E'}(U_b)\bigr)$, where $\pi_{E'}(U_b)$ denotes the image of $U_b$ under $\pi_{E'}$.

It will be very useful to extend this fibrewise-restriction to composite kernels; fortunately, it commutes with composition.
For the proof, see sec:krn-proofs.

$(k\circ h)[b] = k[b]\circ h[b]$, whenever $k\circ h$ exists.

It is moreover easy to check that fibrewise restriction preserves identity kernels, which, together with the preceding proposition, means that it is functorial.
In particular, given $b:J\to B$ in $\Meas$, fibrewise restriction yields a reindexing functor $\Delta_b:\Ka_B\to\Ka_J$.

Suppose $b:J\to B$ in $\Meas$.
Then we have a functor $\Delta_b:\Ka_B\to\Ka_J$ as follows.
On objects, $\Delta_b$ acts to map $E\xto{p}B$ to $p[b]\xto{b^*p}J$.
On morphisms, it maps $k$ to $k[b]$.

Together with the substitution functors $\Delta$, the mapping $\Ka:B\mapsto\Ka_B$ defines a pseudo functor $\Meas\op\to\Cat$.
Pseudo functoriality follows from the (pseudo) functoriality of pullback and the functoriality of composition.
Applying the Grothendieck construction to this indexed category yields a fibration $\int\Ka\to\Meas$.

It remains to exhibit left adjoints to the substitution functors $\Delta_b$.

Suppose $f:C\to B$ is a morphism in $\Meas$.
Then there is a functor $\Sigma_f:\Ka_C\to\Ka_B$ defined on objects $E\xto{p}C$ by post-composition, $\Sigma_f(p) := E\xto{p}C\xto{f}B$ and on kernels as the identity.

Note that, fibrewise, we have $\Sigma_f(p)[b] \cong p[f^*b]$.
Since $f^*$ is pullback in $\Meas$ and $\Delta$ is defined by pullback, this is the first sign of the adjointness of $\Sigma$ and $\Delta$.
See sec:krn-proofs for the proof of the proposition:

Suppose $f:B\to C$ in $\Meas$.
Then $\Sigma_f$ is left adjoint to $\Delta_f$.

Thus $\Ka$ yields a bifibration.
But this is not all we need: for copy-composition to be well-defined via pull-push, we need the functors $\Sigma$ and $\Delta$ to satisfy the Beck-Chevalley condition.
This result follows because the self-indexing of $\Meas$ satisfies Beck-Chevalley; but an explicit proof may be found in sec:krn-proofs.

Suppose we have a pullback square in $\Meas$ of the form

\[\begin{tikzcd}[sep=small]
& P \\
E && F \\
& B
\arrow["\pi"', from=1-2, to=2-1]
\arrow["\rho", from=1-2, to=2-3]
\arrow["p"', from=2-1, to=3-2]
\arrow["q", from=2-3, to=3-2]
\arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-45}, draw=none, from=1-2, to=3-2]
\end{tikzcd} \; .\]

Then there is a natural isomorphism $\Sigma_\rho\,\Delta_\pi \, \cong \, \Delta_q\,\Sigma_p$.

In fact, the bifibration $\int\Ka$ has more structure than we have space to explore in the present study: each fibre has a tensor product that makes it into a monoidal fibration; each fibre additionally has biproducts (and, with an inconsequential modification, a zero object); and thus the subcategory of probability kernels in each fibre is a commutative effectus Cho2015Introduction.
Moreover, these structures interact nicely with the base change functors.
We leave the exposition of all this to future work.

§.§ Decorating spans with sections

Our task now is to define a categorical structure in which morphisms include graphs (in the functional sense) and compose by copy-composition.
That is, given the `graphs' of $f:X\to Y$ and $g:Y\to Z$ in some underlying monoidal category, we wish to be able to compose them to yield

\[\scalebox{0.85}{\tikzfig{img/graph-gf}} \; .\]

This composite is a section of the composite projection $X\times Y\times Z\to X\times Y\to X$.
In turn, we may observe that this projection is the left leg of the composite span

\[\begin{tikzcd}[cramped,sep=scriptsize]
&& {X\times Y\times Z} \\
& {X\times Y} && {Y\times Z} \\
X && Y && Z
\arrow["{\pi^{XY}_X}"', from=2-2, to=3-1]
\arrow["{\pi^{XY}_Y}", from=2-2, to=3-3]
\arrow["{\pi^{YZ}_Y}"', from=2-4, to=3-3]
\arrow[from=1-3, to=2-2]
\arrow[from=1-3, to=2-4]
\arrow["{\pi^{YZ}_Z}", from=2-4, to=3-5]
\arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-45}, draw=none, from=1-3, to=3-3]
\end{tikzcd}\]

and that the graphs of $f$ and $g$ are sections of the left legs of the constituent spans, respectively.
Thus, if we can interpret $\mathsf{graph}(f)$ and $\mathsf{graph}(g)$ bifibrationally, we could write their composite (depicted above) as
The operation $\Sigma_{\pi^{XY}_X}\,\Delta_{\pi^{XY}_Y}$ is known as a “pull-push” operation Schreiber2014Quantization, because one first pulls back along $\pi^{XY}_Y$ and then pushes forward along $\pi^{XY}_X$.

When $f$ and $g$ are morphisms in a finitely complete category, we can immediately make sense of this pull-push composition in the codomain fibration.
Likewise, when they are s-finite kernels, we can interpret this story in $\Ka$, and this is the situation that allows us to construct Bayesian networks and recover the chain rule of the relative entropy.
Nonetheless, all we require is a bifibration satisfying Beck-Chevalley (and a section of it).
The idea is then to decorate spans in the base of the bifibration with sections of the left leg, and then to compose them by pullback on the spans and pull-push on the decorations.
Thus we have a “decorated span” construction, in the sense of Fong2015Decorated and Patterson2023Structured.

Patterson2023Structured observed that adding compositional decorations to categorical constructions often signals a Grothendieck fibration.
Since spans (and cospans) collect into double categories, the decorated (co)span construction can be reconceived as a double Grothendieck construction, giving an extra dimension of composition to that originally proposed by Fong2015Decorated, and newly allowing the decorations to depend on whole (co)spans (rather than merely their apices), a freedom we will need.
Following [Theorem 3.51]Cruttwell2022Double, the double Grothendieck construction produces a double fibration from an indexed double category, i.e. a lax double pseudo functor whose codomain is the double 2-category $\SSpan(\Cat)$ of spans of categories; see [§3.1]Patterson2023Structured for a summary.

A lax double pseudo functor $F:\Bbb{C}\to\Bbb{D}$ consists of a pair of pseudo functors $F_0:\Bbb{C}_0\to\Bbb{D}_0$ (from the vertical category of $\Bbb{C}$ to that of $\Bbb{D}$) and $F_1:\Bbb{C}_1\to\Bbb{D}_1$ (from the horizontal category of $\Bbb{C}$ to that of $\Bbb{D}$), along with pseudo natural transformations $\mu$ and $\eta$ witnessing the compatibility of $F_1$ and $F_0$ with the double category structures of $\Bbb{C}$ and $\Bbb{D}$, as in the diagrams

\[
\begin{tikzcd}
{\Bbb{C}_1\times_{\Bbb{C}_0}\Bbb{C}_1} && {\Bbb{C}_1} \\
\\
{\Bbb{D}_1\times_{\Bbb{D}_0}\Bbb{D}_1} && {\Bbb{D}_1}
\arrow["{\diamond_{\Bbb{C}}}", from=1-1, to=1-3]
\arrow["{F_1\times F_1}"', from=1-1, to=3-1]
\arrow["{\diamond_{\Bbb{D}}}"', from=3-1, to=3-3]
\arrow["{F_1}", from=1-3, to=3-3]
\arrow["\mu", shorten <=19pt, shorten >=19pt, Rightarrow, from=3-1, to=1-3]
\end{tikzcd}
\qquad\qquad
\begin{tikzcd}
{\Bbb{C}_0} && {\Bbb{C}_1} \\
\\
{\Bbb{D}_0} && {\Bbb{D}_1}
\arrow["{I_{\Bbb{C}}}", from=1-1, to=1-3]
\arrow["{I_{\Bbb{D}}}", from=3-1, to=3-3]
\arrow["{F_0}"', from=1-1, to=3-1]
\arrow["{F_1}", from=1-3, to=3-3]
\arrow["\eta", shorten <=17pt, shorten >=17pt, Rightarrow, from=3-1, to=1-3]
\end{tikzcd}
\]

such that four standard coherence axioms [Def. 3.12]Cruttwell2022Double are satisfied.
($\diamond$ denotes the `external' (2-cell) composition of a double category structure and $I$ its unit, so that, in the context of indexed double categories, $\mu$ implements the indexed external composition, and $\eta$ implements its unit.)

An indexed double category is a lax double pseudo functor with codomain $\SSpan(\Cat)$.

Suppose now that $\Ea\xto{\pi}\Ba$ is a bifibration satisfying Beck-Chevalley, equipped with a section $\iota:\Ba\to\Ea$, where $\Ba$ has all pullbacks; we will continue to write $\Ea_B$ for the fibre over $B:\Ba$, and $\Sigma\dashv\Delta$ for the base change functors, and assume that $\Delta$ preserves $\iota$.
Our model for $\Ea$ will be either $\int\Ka$ or the codomain fibration of a finitely complete category; and for $\iota$ the mapping $B\mapsto\bigl(\id_B:B\to B\bigr)$, so that morphisms out of $\iota$ are understood as sections (and thus models for terms).
We will construct an indexed double category $S:\SSpan(\Ba)_{pb}\op\to\SSpan(\Cat)$, where $\SSpan(\Ba)_{pb}$ is the sub-double category of $\SSpan(\Ba)$ whose 2-cells are Cartesian morphisms of spans (a restriction necessary for morphisms of decorations to be well-defined), and the $\op$ is taken vertically.

The vertical category of $\SSpan(\Ba)_{pb}$ is $\Ba$, and the vertical 2-category of $\SSpan(\Cat)$ is $\Cat$; but the vertical decorations will be trivial: $S_0$ is simply the constant functor on the terminal category $\mathbf{1}$.

There is a simplification in the horizontal direction, too.
The horizontal category of $\SSpan(\Ba)_{pb}$ is $\Ba^{\{\bullet\leftarrow\bullet\to\bullet\}}_{pb}$, the category of diagrams in $\Ba$ of shape $\bullet\leftarrow\bullet\to\bullet$, with morphisms restricted to those natural transformations that are Cartesian (i.e., constituting pullback squares).
$S_1$ must map a span $m=\bigl(A\xleftarrow{a}E\xto{b}B\bigr)$ in $\Ba$ to a span $\mathbf{1}\leftarrow S_1(m)\to\mathbf{1}$ of categories.
Because $\mathbf{1}$ is terminal in $\Cat$, the legs of the latter span are accordingly determined.
There is a further simplification: $S_1(m)$ will be a discrete category (a set).
Indeed, we define $S_1(m)$ to be the set of sections of the left leg of $m$ in $\Ea$.
That is, $S_1(m) := \Ea_A(\iota A, \Sigma_a\,\iota E)$.

Given a morphism $f:m\to m'$ in $\SSpan(\Ba)_{pb}$ as in the diagram

\[\begin{tikzcd}[sep=scriptsize]
A & E & B \\
{A'} & {E'} & {B'}
\arrow["a"', from=1-2, to=1-1]
\arrow["{f_l}"', from=1-1, to=2-1]
\arrow["{a'}"', from=2-2, to=2-1]
\arrow[from=1-2, to=2-2]
\arrow["\llcorner"{anchor=center, pos=0.125}, draw=none, from=1-2, to=2-1]
\arrow["b", from=1-2, to=1-3]
\arrow["{b'}", from=2-2, to=2-3]
\arrow["{f_r}", from=1-3, to=2-3]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-2, to=2-3]
\end{tikzcd} \; ,\]

$S_1(f)$ must be a function $\Ea_{A'}(\iota A', \Sigma_{a'}\,\iota E')\to\Ea_A(\iota A, \Sigma_a\,\iota E)$, which we take to be given by $\Delta_{f_l}$.
This is well defined because $\Delta_{f_l}\,\iota A' = \iota_A$ ex hypothesi, $\Delta_{f_l}\,\Sigma_{a'}\,\iota E' \cong \Sigma_a\,\Delta_f\,\iota E'$ by Beck-Chevalley, and $\Delta_f\,\iota E' = \iota E$ ex hypothesi.
Moreover, since $\Delta_{f_l}$ is functorial, so is $S_1(f)$.

The copy-composition of sections is implemented by the transformation $\mu$, whose component at a pair of composable spans $m=\bigl(A\xleftarrow{a}E\xto{b}B\bigr)$ and $n=\bigl(B\xleftarrow{b'}F\xto{c}C\bigr)$ must be a function $\mu_{m,n}:S_1(m)\times S_1(n) \to S_1(n\diamond m)$, which we take to be defined by pull-push.
That is, $\mu_{m,n}(\sigma,\tau) := \Sigma_a\,\Delta_b(\tau)\circ\sigma$.
Associativity of $\mu$ follows by Beck-Chevalley; the explicit proof is in Appendix <ref>.
The unit $\eta$ is defined over each identity span $E=E=E$ by the function $\eta_E:\mathbf{1}\to\Ea_E(\iota E,\iota E)$ determined by the identity on $\iota_E$.
Note that this makes pull-push copy-composition strictly unital, unlike in Smithe2023Approximate.

Applying the double Grothendieck construction [Theorem 3.51]Cruttwell2022Double to $S$ yields a double category $\Sbb$, doubly fibred over $\SSpan(\Ba)_{pb}$, which has the following structure:

* The objects of $\Sbb$ are the objects of $\Ba$.

* A vertical 1-cell is a morphism of $\Ba$, and vertical composition is as in $\Ba$.

* A horizontal 1-cell $A\nrightarrow B$ is a quadruple $(E,a,b,\sigma)$ where $\bigl(A\xleftarrow{a}E\xto{b}B\bigr)$ is a span with $\sigma$ being a section of the left leg in $\Ea_A$; i.e., $\sigma \in \Ea_A(\iota A,\Sigma_a\,\iota E)$.

* A 2 cell from $(E,a,b,\sigma):A\nrightarrow B$ to $(E',a',b',\sigma'):A'\nrightarrow B'$ is a Cartesian morphism of spans $(f_l,f,f_r):\bigl(A\xleftarrow{a}E\xto{b}B\bigr)\Rightarrow\bigl(A'\xleftarrow{a'}E'\xto{b'}B'\bigr)$ such that $\sigma = \Delta_{f_l}\,\sigma'$.

* Horizontal composition is by pullback on the spans (and their morphisms) and by pull-push on the sections, as described above.

That is to say, we have the following theorem (given the details in Appendix <ref>).

Given a bifibration $\Ea\to\Ba$ over a finitely complete base, satisfying Beck-Chevalley, and equipped with a section $\iota:\Ba\to\Ea$ preserved by pullback, the foregoing data define a pseudo double category $\Sbb$ doubly fibred over $\SSpan(\Ba)_{pb}$.

By instantiating $\Sbb$ in $\int\Ka$, we can formally recover the factors of a Bayesian network described by Fong2013Causal and introduced at the beginning of this section.
There is a lax embedding of $\sfKrn$ horizontally into $\Sbb$ (so instantiated), which maps a kernel to its graph.
Let $\sigma$ denote the image of the kernel $X_i\mid\mathrm{pa}(i)$ under this embedding, which has the effect of precomposing it with copiers.
Then, to tensor with the identity wires $\otimes_{j\notin\mathrm{pa}(i)}\,X_j$, we can pull $\sigma$ back along the projection $\prod_{j<i}\,X_j \to \prod_{j\in\mathrm{pa}(i)}\,X_j$, as in the diagram

\[\begin{tikzcd}[cramped,row sep=small]
{\prod_{j<i}\,X_j} & {\prod_{j\leq i}\,X_j} & {\prod_{j\leq i}\,X_j} \\
\\
{\prod_{j\in\mathrm{pa}(i)}\,X_j} & {\prod_{j\in\mathrm{pa}(i)}X_j\times X_i} & {X_i}
\arrow[from=1-2, to=1-1]
\arrow[from=3-2, to=3-1]
\arrow[from=3-2, to=3-3]
\arrow[Rightarrow, no head, from=1-2, to=1-3]
\arrow[from=1-3, to=3-3]
\arrow[from=1-1, to=3-1]
\arrow[from=1-2, to=3-2]
\arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-90}, draw=none, from=1-2, to=3-1]
\arrow["{\sigma_{\leq i}}", curve={height=-12pt}, dashed, from=1-1, to=1-2]
\arrow["\sigma", curve={height=-12pt}, dashed, from=3-1, to=3-2]
\end{tikzcd} \; .\]

The upper decorated span is the horizontal morphism corresponding to Fong's factor.
Finally, note that whereas traditional statistical modelling is restricted to sections of product types (as above), using $\Ka$ and $\Sbb$ means we can build probabilistic models involving general dependent types.

§ UNDIRECTED MODELS: OPEN FACTOR GRAPHS

\[\scalebox{0.8}{\tikzfig{img/factor-graph-2}}\]

A factor graph, in the style of [§2.1.3]Wainwright2007Graphical.

The preceding section explained how copy-composition is central to Bayesian networks: directed probabilistic graphical models.
In this section, we shall see that it is also central to the construction of undirected models known as factor graphs Dauwels2007Variational,Wainwright2007Graphical.
A factor graph is a graphical representation of the factorization of a function, which is often but not necessarily interpreted as the density of a probability distribution.
Thus Figure <ref> represents a function $f$ of the form

$$f(a,b,c,d,e) = f_0(a,b)\, f_1(a,c)\, f_2(b,c,d)\, f_3(d,e)\, f_4(e)\, f_5(d)$$

where the variables have the types $a:A,b:B,c:C,d:D$.
Note that we could see $f$ as composed of `factors' $f_i$; it is this composition that we explore here.

Typically, the factors of a factor graph are functions into some object of scalars; for example, we might interpret $f_2$ (above) to have the type $B\times C\times D \to \Rb_+$, for some spaces $B,C,D$.
Should these spaces be $\mathbb{R}_+$-modules, then we might suppose $f_2$ to be a linear functional or covector on their product.
$\Rb_+$-modules form a category $\Mod_{\Rb_+}$ which is equipped with a tensor product $\otimes$, whose unit is the 1-dimensional space of scalars $\Rb_+$, often denoted $I$.
Covectors on $X$ then correspond to costates, morphisms $X\to I$.
This suggests that we may internalize the notion of factor in a monoidal category $(\Ca,\otimes,I)$ simply as the costates in $\Ca$.

This first step towards an abstract treatment should be taken with care, as any semicartesian monoidal category, such as $\Set$ or any Markov category (in the sense of Fritz2019synthetic), will only have trivial costates, the monoidal unit there being by definition terminal.
The composition of factors then proceeds by copy-composition; notice for example the duplication of the variable $b:B$ in the expression for $f$ above, or in the following string-diagrammatic representation of its $f_0,f_2$ factor:

\[\scalebox{0.8}{\tikzfig{img/factor-composition-1}}\]

This suggests that an appropriate categorical setting for factor graphs is that of copy-discard categories[
A copy-discard category is a monoidal category in which every object is equipped with a comonoid structure (with respect to the ambient monoidal structure) Cho2017Disintegration.
A Markov category is a semicartesian copy-discard category Fritz2019synthetic.
Precisely because of the existence of non-trivial costates, copy-discard categories often end up being more useful in modelling practice than Markov categories, despite the utility of the latter for synthetic probability theory.], of which $\sfKrn$ (or any fibre of $\Ka$) is an example.

Because factor graphs are a form of undirected graphical model, it is natural to expect them to fit into the framework of undirected wiring diagrams
Spivak2013Operad [Chapter 7]Yau2018Operads.
Undirected wiring diagrams are algebras for an operad of cospans Fong2019Hypergraph, and one way to obtain such algebras is through the decorated cospans construction, originally due to Fong2015Decorated.
(But note that the decorated spans of the previous section are not undirected in the same way, because the decorations there are asymmetric.)
The main result of this section is to show that `open' factor graphs may be obtained and composed precisely through the double-categorical generalization of this construction due to Patterson2023Structured.

Fong2019Hypergraph show that cospan-algebras are equivalent to hypergraph categories, in which each morphism has the form of a hypergraph.
Consequently, this is also the case for factor graphs.

The remainder of this section is dedicated to constructing a double category indexed by cospans, i.e. a double pseudo functor $F$, and instantiating its double Grothendieck construction, the double category $\FG$.
The domain of $F$ is the double category of cospans of finite sets, whose vertical category $\CCospan(\FinSet)_0$ is simply $\FinSet$, and whose horizontal category $\CCospan(\FinSet)_1$ is the category of diagrams in $\FinSet$ of shape $\bullet\to\bullet\leftarrow\bullet$, i.e. the functor category $\FinSet^{\{\bullet\to\bullet\leftarrow\bullet\}}$.
The codomain of $F$ is $\SSpan(\Cat)$, whose vertical 2-category is $\Cat$, and whose horizontal 2-category is $\Cat^{\{\bullet\leftarrow\bullet\to\bullet\}}$.

Henceforth, we will assume an ambient copy-discard category $(\Ca,I,\otimes)$.
Because finite sets are not ordered and we plan to define factors over accordingly indexed monoidal products, we must additionally assume that the monoidal structure $(I,\otimes)$ on $\Ca$ is symmetric.

There will be fewer simplifications involved in the definition of $F$ (versus $S$), and so we split the construction into four subsections.

§.§ Vertical decoration: factors' interfaces

The pseudo functor $F_0:\FinSet\to\Cat$ assigns categories of decorations to finite sets.
For us, these decorations will be the exposed interfaces of factors, given by a discrete diagram in $\Ca$: a functor $\disc X\to\Ca$, for some finite set $X$, where $\disc X$ is the discrete category on $X$.
However, were we just to define $F_0X$ to be the functor category $\Cat(\disc X, \Ca)$, we would run into problems later with the composition of 2-cells.
This is because vertical morphisms — decorated by morphisms in the image of $F_0$ — may be used to transform the interface types, but the composition of factors proceeds by copying.
For this to be compatible with morphisms of interfaces, we must restrict the latter to be comonoid homomorphisms, which (in probabilistic contexts) we can often understand as deterministic functions.

Therefore, on objects $X:\FinSet$, let $F_0X$ be the functor category $\Cat(\disc X, \Comon(\Ca,I,\otimes))$ where $\Comon(\Ca,I,\otimes)$ denotes the (wide) monoidal subcategory of $\Ca$ whose morphisms are the comonoid homomorphisms.
Note that, because the objects $\chi$ of $F_0X$ are functors on a discrete category, a morphism $\varphi:\chi\to\chi'$ (hence a natural transformation) is simply given by an $X$-indexed family of comonoid homomorphisms $\varphi_x:\chi(x)\to\chi'(x)$ in $\Ca$.

Given a morphism $f:X\to Y$ in $\FinSet$, we let $F_0$ return a functor $F_0X\to F_0Y$ which we denote by $f_*$ and define as follows.
If $\chi$ is an object of $F_0X$ then we define $f_*\chi$ by the mapping $y\mapsto\otimes_{x:f^{-1}(y)}\chi(x)$ (for $y:Y$).
Then, if $\varphi:\chi\to\chi'$ is a morphism of $F_0X$, we define each $y$-component $(f_*\varphi)_y$ of $f_*\varphi$ to be $\otimes_{x:f^{-1}(y)}\varphi_x$.
Note that this definition yields components of the correct type

$$(f_*\varphi)_y : (f_*\chi)(y) = \otimes_{x:f^{-1}(y)}\chi(x) \xrightarrow{\otimes_{x:f^{-1}(y)}\varphi_x} \otimes_{x:f^{-1}(y)}\chi'(x) = (f_*\chi')(y) \; .$$

Naturality is trivially satisfied, because $\chi$ and $\chi'$ are discrete functors, and the functoriality of the reindexing $f_*$ follows from the functoriality of $\otimes$.
Likewise, the pseudofunctoriality of $F_0$ itself follows from the functoriality of inverse images and the functoriality and symmetry of $\otimes$, so that $\otimes_{y:g^{-1}(z)} \otimes_{x:f^{-1}(y)} \cong \otimes_{x:(g\circ f)^{-1}(z)}$.

§.§ Horizontal decoration: `open' factors

The pseudo functor $F_1 : \FinSet^{\{\bullet\to\bullet\leftarrow\bullet\}} \to \Cat^{\{\bullet\leftarrow\bullet\to\bullet\}}$ assigns spans of categories to cospans of finite sets, compatibly with $F_0$.
We interpret a cospan $A\xrightarrow{a} X\xleftarrow{b} B$ as follows.
The apex set $X$ will be decorated with two kinds of data: first, a category of interfaces suited to factors in $\Ca$; and second, for each suitable interface, a category of factors on that interface (compatibly with morphisms of interfaces).
The legs of the cospan $a$ and $b$ will be used to expose those parts of the interface which are open to composition, and in this way the objects $A$ and $B$ will be decorated by $F_0A$ and $F_0B$ respectively; this is one of the indexed-double-categorical coherence axioms (`well-definition').

Thus, given a cospan $m=\bigl(A\xrightarrow{a} X\xleftarrow{b} B\bigr)$, we let $F_1$ return a span of categories $F_0A \xleftarrow{\pi_a} \int\underline{F_1}m \xrightarrow{\pi_b} F_0B$.
The apex category $\int\underline{F_1}m$ has for objects pairs $(\chi,f)$ where $\chi:\disc X\to\Ca$ is an interface and $f:\chi^\otimes\to I$ is a factor on that interface.
$\chi^\otimes$ denotes the monoidal product $\otimes_{x:X}\,\chi(x)$ in $\Ca$.
The morphisms of $\int\underline{F_1}m$ are factorizations of factors through transformations of interfaces; that is to say, a morphism $(\chi,f)\to(\chi',f')$ in $\int\underline{F_1}m$ is a morphism of interfaces $\varphi:\chi\to\chi'$ such that $f = \varphi^* f'$, where $\varphi^*$ denotes precomposition by $\varphi^\otimes := \otimes_{x:X}\,\varphi_x$.
The functors $\pi_a$ and $\pi_b$ forget the factors and project out those parts of the interfaces over $X$ that are exposed by $a$ and $b$ respectively.
($\int\underline{F_1}m$ and the functors $\pi_a,\pi_b$ are in fact obtained through universal constructions — a limit and a Grothendieck construction — as we explain in Appendix <ref>.
Universality then yields the functorial action of $F_1$ on morphisms of cospans.)

§.§ Factor composition

The functors $F_0$ and $F_1$ describe how to attach factors to interfaces, and how these interfaces (and the factors on them) may be transformed by morphisms in $\Ca$.
But they do not tell us about the operation at the heart of the open factor graph construction: the horizontal (copy-)composition of factors, or the horizontal composition of their morphisms.
These operations are formalized by the external composition structure $(\mu,\eta)$ with which we now equip $F$.

Let us begin with $\mu$, a pseudo natural transformation whose component $\mu_{m,n}$ at a pair of composable cospans $m=\bigl(A\xrightarrow{a}X\xleftarrow{b}B\bigr)$ and $n=\bigl(B\xrightarrow{b'}Y\xleftarrow{c}C\bigr)$ must be a functor $\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n\to\int\underline{F_1}(n\diamond m)$.
Given factors $(\chi,f),(\gamma,g)$ in its domain, $\mu_{m,n}$ must return an interface over $X+_BY$ and a factor on that interface.
The former is given by the copairing $[\chi,\gamma]_B$ of $\chi$ and $\gamma$ over $B$, while the latter is given by copy-composition.
For each $j:X+_BY$, copying induces a morphism

$$\delta_{\chi,\gamma}^j:[\chi,\gamma]_B(j) \to \bigotimes_{i:[\iota^X_B,\iota^Y_B]^{-1}(j)}\, [\chi,\gamma](i)$$

in $\Ca$ which is unique up to coassociativity.
We then define $\delta_{\chi,\gamma} := \otimes_{j:X+_BY}\;\delta_{\chi,\gamma}^j$, which has the type $[\chi,\gamma]_B^\otimes \to [\chi,\gamma]^\otimes$.
We can compose $f\otimes g$ after this higher-arity copier to yield a factor on the interface $[\chi,\gamma]_B$.
Thus $\mu_{m,n}\bigl((\chi,f),(\gamma,g)\bigr) := \bigl([\chi,\gamma]_B,(f\otimes g)\circ\delta_{\chi,\gamma}\bigr)$.
(For a more detailed construction and proof that this yields a pseudo natural transformation, see Appendix <ref>.)

To see $\mu$ in action, suppose $A$ has $l$-many elements, $C$ has $n$-many elements, and the coupled interface $B$ has $m$-many elements, with $B_1$ shared once between $f$ and $g$ but $B_m$ shared an arbitrary number of times.
Then $\mu\bigl((\chi,f),(\gamma,g)\bigr)$ yields the factor

\[\scalebox{0.8}{\tikzfig{img/factor-composition-2}} \; .\]

The naturality of $\mu_{m,n}$ means that if we were to have $f'$ and $g'$ defined by transforming the interface $B$ along $\beta$ like so

\[\scalebox{0.8}{
\tikzfig{img/factor-comp-naturality-f}
\quad and \quad
\tikzfig{img/factor-comp-naturality-g}

then copy-composing $f'$ and $g'$ along $B'$ yields the same as copy-composing $f$ and $g$ along $B$ and then transforming the $B$ interface of the result accordingly:

\[\scalebox{0.8}{\tikzfig{img/factor-comp-naturality-1}}\]

However, this only works for `determinsitic' transformations $\beta$: although the rules of open factor graphs do allow us to transform factors using arbitrary morphisms, we can only pull these transformations `outside' the composites when the transformations are comonoid homomorphisms.

It remains to define the unit $\eta$, a pseudo natural transformation whose component $\eta_X$ at each finite set $X$ is given by a functor $\eta_X : F_0X \to \int\underline{F_1}(\id_X)$.
We define $\eta_X$ using the counits of the comonoid structures on the interfaces on $X$.
That is to say, $\eta_X$ maps an interface $\chi:\disc X \to \Comon(\Ca)$ to the pair $(\chi, \epsilon_\chi)$, where here $\epsilon_\chi$ denotes the canonical discarding map $\chi^\otimes \to I$.
The functorial action of $\eta_X$ is obtained from the fact that all morphisms in $F_0X$ are comonoid homomorphisms, so if $\varphi$ is a morphism $\chi \to \chi'$ then $\epsilon_\chi = \varphi^*\epsilon_{\chi'}$.
Pseudo naturality of $\eta$ obtains likewise, and its unitality with respect to $\mu$ follows from the counitality of the comonoid counits.

§.§ Putting it all together

We have defined a double pseudo functor $F:\CCospan(\FinSet)\to\SSpan(\Cat)$, from which we obtain a double category of open factor graphs $\FG$, doubly opfibred over $\CCospan(\FinSet)$, by applying the double Grothendieck construction.
This gives $\FG$ the following structure:

* Its objects (0-cells) are pairs $(A,\alpha)$ where $A$ is a finite set and $\alpha$ is an object of $F_0A$ — i.e., an interface in $\Ca$ on $A$.

* A vertical 1-cell $(A,\alpha)\to(A',\alpha')$ is a pair $(f,\varphi)$ of a map $f:A\to A'$ and a deterministic transformation of interfaces $\varphi:f_*\alpha\to\alpha'$ — where $f_* = F_0(f)$ so that $\varphi$ is a morphism in $F_0A'$.

* A horizontal 1-cell $(A,\alpha)\nrightarrow(B,\beta)$ is a quintuple $(X,a,b,\chi,p)$ where $\bigl(A\xrightarrow{a}X\xleftarrow{b}B\bigr)$ is a cospan of finite sets, $\chi$ is an interface on $X$, and $p$ is a factor on $\chi$ — i.e., $(\chi,p)$ is an object of $\int\underline{F_1}(X,a,b)$ — such that $\pi_a(\chi,p) = \alpha$ and $\pi_b(\chi,p) = \beta$.

* A 2-cell as in the diagram

[cramped,column sep=small,row sep=tiny]
(A,α)        (B,β)

(A',α')        (B',β')
["(X,a,b,χ,p)", ""marking, from=1-1, to=1-3]
["(X',a',b',χ',p')"', ""marking, from=3-1, to=3-3]
["(f^l,φ^l)"', from=1-1, to=3-1]
["(f^r,φ^r)", from=1-3, to=3-3]

is a pair $(f,\varphi)$ where $f:X\to X'$ is a map of finite sets and $\varphi$ is a transformation of interfaces $f_*\chi\to\chi'$, such that $f_* p = \varphi^* p'$, $\pi_{a'}(\varphi) = \varphi^l$, $\pi_{b'}(\varphi) = \varphi^r$ (with $\varphi^l$ and $\varphi^r$ deterministic), and such that $(f,f^l,f^r)$ constitutes a morphism of cospans, meaning that $a'\circ f^l = f\circ a$ and $b'\circ f^r = f\circ b$.

* Vertical 1-cells $(f,\varphi):(A,\alpha)\to(A',\alpha')$ and $(f',\varphi'):(A',\varphi')\to(A'',\varphi'')$ compose to yield $(f'\circ f, \varphi'\circ f'_*\varphi):(A,\alpha)\to(A'',\alpha'')$; the vertical composition of 2-cells is similar.
The vertical identity 1-cell on $(A,\alpha)$ is the pair $(\id_A,\id_\alpha)$ of identity morphisms $\id_A:A\to A$ and $\id_\alpha:\alpha\to\alpha$.
We denote vertical composition by $\circ$.

* Finally, horizontal 1-cells (and 2-cells, horizontally) compose by cospan- and copy-composition, as described in sec:copy-comp.
Horizontal identities are given by the external unit $\eta$.
We denote horizontal composition by $\diamond$.

All told, this (plus the details in Appendix <ref>) yields the following theorem.

Given a symmetric monoidal copy discard category $(\Ca,I,\otimes)$, the foregoing data define a pseudo double category $\FG$ doubly opfibred over $\CCospan(\FinSet)$.

Since each of the elements of the construction of $\FG$ are functorial, we expect the construction itself to be functorial, so that a functor $\Ca\to\Ca'$ yields a double functor $\FG_{\Ca}\to\FG_{\Ca'}$.
But we have not established this, and leave it to future work.

In other future work, we hope to make use of $\FG$ to study the compositionality of inference on factor graphs, and to study the formal relationships between directed and undirected models.

§.§ On a graphical calculus

We motivated the construction of $\FG$ with the graphic Figure <ref>.
Decorated cospan categories as originally formulated inherit a graphical calculus from their status as hypergraph categories or undirected wiring diagram algebras.
Lacking a formal theory of double operads and their graphical calculi, we do not have a similarly formal graphical calculus for $\FG$; still, we expect that its horizontal bicategory (appropriately quotiented) would fit the undirected wiring diagram pattern, at the cost of the transformations of interfaces.
Inspired by this, and in an attempt not to pay that cost, in Appendix <ref> we (informally) propose a graphical calculus that matches and extends the non-compositional depictions in the statistics literature.

§ REFERENCES

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Cambridge, UK

Open Publishing Association

abstractWe propose a categorical framework for processes which interact bidirectionally with both an environment and a 'controller'. Examples include open learners, in which the controller is an optimiser such as gradient descent, and an approach to compositional game theory closely related to open games, in which the controller is a composite of game-theoretic agents. We believe that 'cybernetic' is an appropriate name for the processes that can be described in this framework.
booktitleElectronic Proceedings in Theoretical Computer Science
eventtitleApplied Category Theory 2021
titleTowards Foundations of Categorical Cybernetics

abstractThe notions of disintegration and Bayesian inversion are fundamental in conditional probability theory. They produce channels, as conditional probabilities, from a joint state, or from an already given channel (in opposite direction). These notions exist in the literature, in concrete situations, but are presented here in abstract graphical formulations. The resulting abstract descriptions are used for proving basic results in conditional probability theory. The existence of disintegration and Bayesian inversion is discussed for discrete probability, and also for measure-theoretic probability — via standard Borel spaces and via likelihoods. Finally, the usefulness of disintegration and Bayesian inversion is illustrated in several examples.
journaltitleMath. Struct. Comp. Sci. 29 (2019) 938-971
titleDisintegration and Bayesian Inversion via String Diagrams

abstractEffectus theory is a new branch of categorical logic that aims to capture the essentials of quantum logic, with probabilistic and Boolean logic as special cases. Predicates in effectus theory are not subobjects having a Heyting algebra structure, like in topos theory, but `characteristic' functions, forming effect algebras. Such effect algebras are algebraic models of quantitative logic, in which double negation holds. Effects in quantum theory and fuzzy predicates in probability theory form examples of effect algebras. This text is an account of the basics of effectus theory. It includes the fundamental duality between states and effects, with the associated Born rule for validity of an effect (predicate) in a particular state. A basic result says that effectuses can be described equivalently in both `total' and `partial' form. So-called `commutative' and `Boolean' effectuses are distinguished, for probabilistic and classical models. It is shown how these Boolean effectuses are essentially extensive categories. A large part of the theory is devoted to the logical notions of comprehension and quotient, which are described abstractly as right adjoint to truth, and as left adjoint to falisity, respectively. It is illustrated how comprehension and quotients are closely related to measurement. The paper closes with a section on `non-commutative' effectus theory, where the appropriate formalisation is not entirely clear yet.
titleAn Introduction to Effectus Theory

abstractThis is the second part of a three-part overview, in which we derive the category-theoretic backbone of quantum theory from a process ontology, treating quantum theory as a theory of systems, processes and their interactions. In this part we focus on classical-quantum interaction. Classical and quantum systems are treated as distinct types, of which the respective behavioural properties are specified in terms of processes and their compositions. In particular, classicality is witnessed by 'spiders' which fuse together whenever they connect. We define mixedness and show that pure processes are extremal in the space of all processes, and we define entanglement and show that quantum theory indeed exhibits entanglement. We discuss the classification of tripartite qubit entanglement and show that both the GHZ-state and the W-state come from spider-like families of processes, which differ only in how they behave when they are connected by two or more wires. We define measurements and provide fully-comprehensive descriptions of several quantum protocols involving classical data flow. Finally, we give a notion of 'genuine quantumness', from which special processes called 'phase spiders' arise, and get a first glimpse of quantum non-locality.
titleCategorical Quantum Mechanics II: Classical-Quantum Interaction

abstractThis paper defines double fibrations (fibrations of double categories) and describes their key examples and properties. In particular, it shows how double fibrations relate to existing fibrational notions such as monoidal fibrations and discrete double fibrations, proves a representation theorem for double fibrations, and shows how double fibrations are a type of internal fibration.
titleDouble Fibrations
ematics - Category Theory

booktitle2007 IEEE International Symposium on Information Theory
eventtitle2007 IEEE International Symposium on Information Theory
titleOn Variational Message Passing on Factor Graphs

University of Oxford

abstractIn this dissertation we develop a new formal graphical framework for causal reasoning. Starting with a review of monoidal categories and their associated graphical languages, we then revisit probability theory from a categorical perspective and introduce Bayesian networks, an existing structure for describing causal relationships. Motivated by these, we propose a new algebraic structure, which we term a causal theory. These take the form of a symmetric monoidal category, with the objects representing variables and morphisms ways of deducing information about one variable from another. A major advantage of reasoning with these structures is that the resulting graphical representations of morphisms match well with intuitions for flows of information between these variables. These categories can then be modelled in other categories, providing concrete interpretations for the variables and morphisms. In particular, we shall see that models in the category of measurable spaces and stochastic maps provide a slight generalisation of Bayesian networks, and naturally form a category themselves. We conclude with a discussion of this category, classifying the morphisms and discussing some basic universal constructions. ERRATA: (i) Pages 41-42: Objects of a causal theory are words, not collections, in V, and we include swaps as generating morphisms, subject to the identities defining a symmetric monoidal category. (ii) Page 46: A causal model is a strong symmetric monoidal functor.
titleCausal Theories: A Categorical Perspective on Bayesian Networks
year2013-01-26, 2013

journaltitleTheory and Applications of Categories
titleDecorated Cospans

abstractHypergraph categories have been rediscovered at least five times, under various names, including well-supported compact closed categories, dgs-monoidal categories, and dungeon categories. Perhaps the reason they keep being reinvented is two-fold: there are many applications—including to automata, databases, circuits, linear relations, graph rewriting, and belief propagation—and yet the standard definition is so involved and ornate as to be difficult to find in the literature. Indeed, a hypergraph category is, roughly speaking, a "symmetric monoidal category in which each object is equipped with the structure of a special commutative Frobenius monoid, satisfying certain coherence conditions". Fortunately, this description can be simplified a great deal: a hypergraph category is simply a "cospan-algebra". The goal of this paper is to remove the scare-quotes and make the previous statement precise. We prove two main theorems. First is a coherence theorem for hypergraph categories, which says that every hypergraph category is equivalent to an objectwise-free hypergraph category. Second, we prove that the category of objectwise-free hypergraph categories is equivalent to the category of cospan-algebras.
journaltitleJournal of Pure and Applied Algebra
shortjournalJournal of Pure and Applied Algebra
titleHypergraph Categories

abstractWe develop Markov categories as a framework for synthetic probability and statistics, following work of Golubtsov as well as Cho and Jacobs. This means that we treat the following concepts in purely abstract categorical terms: conditioning and disintegration; various versions of conditional independence and its standard properties; conditional products; almost surely; sufficient statistics; as well as versions of theorems on sufficient statistics due to Fisher-Neyman, Basu, and Bahadur. Besides the conceptual clarity offered by our categorical setup, its main advantage is that it provides a uniform treatment of various types of probability theory, including discrete probability theory, measure-theoretic probability with general measurable spaces, Gaussian probability, Markov processes of either of these kinds, and many others.
journaltitleAdvances in Mathematics
titleA Synthetic Approach to Markov Kernels, Conditional Independence and Theorems on Sufficient Statistics
18D10,62A01,68Q55,act2022,act24,cs.LO,dphil,math.CT,math.PR,math.ST,Primary: 60A05,Secondary: 62B05,stat.TH

North-Holland Publishing Co., Amsterdam

seriesStudies in Logic and the Foundations of Mathematics
titleCategorical Logic and Type Theory

abstractThe Free Energy Principle (FEP) is a theoretical framework for describing how (intelligent) systems self-organise into coherent, stable structures by minimising a free energy functional. Active Inference (AIF) is a corollary of the FEP that specifically details how systems that are able to plan for the future (agents) function by minimising particular free energy functionals that incorporate information seeking components. This paper is the first in a series of two where we derive a synthetic version of AIF on free form factor graphs. The present paper focuses on deriving a local version of the free energy functionals used for AIF. This enables us to construct a version of AIF which applies to arbitrary graphical models and interfaces with prior work on message passing algorithms. The resulting messages are derived in our companion paper. We also identify a gap in the graphical notation used for factor graphs. While factor graphs are great at expressing a generative model, they have so far been unable to specify the full optimisation problem including constraints. To solve this problem we develop Constrained Forney-style Factor Graph (CFFG) notation which permits a fully graphical description of variational inference objectives. We then proceed to show how CFFG's can be used to reconstruct prior algorithms for AIF as well as derive new ones. The latter is demonstrated by deriving an algorithm that permits direct policy inference for AIF agents, circumventing a long standing scaling issue that has so far hindered the application of AIF in industrial settings. We demonstrate our algorithm on the classic T-maze task and show that it reproduces the information seeking behaviour that is a hallmark feature of AIF.
shorttitleRealising Synthetic Active Inference Agents, Part I
titleRealising Synthetic Active Inference Agents, Part I: Epistemic Objectives and Graphical Specification Language
ine Learning

abstractWe lift the standard equivalence between fibrations and indexed categories to an equivalence between monoidal fibrations and monoidal indexed categories, namely weak monoidal pseudofunctors to the 2-category of categories. In doing so, we investigate the relation between this `global' monoidal structure where the total category is monoidal and the fibration strictly preserves the structure, and a `fibrewise' one where the fibres are monoidal and the reindexing functors strongly preserve the structure, first hinted by Shulman. In particular, when the domain is cocartesian monoidal, lax monoidal structures on the functor to the 2-category of categories correspond to lifts of the functor to the 2-category of monoidal categories. Finally, we give examples where this correspondence appears, spanning from the fundamental and family fibrations to network models and systems.
journaltitleTheory and Applications of Categories
titleMonoidal Grothendieck Construction
family=nLab authors,

titleCategorical Semantics of Dependent Type Theory

abstractStructured and decorated cospans are broadly applicable frameworks for building bicategories or double categories of open systems. In this paper, we revisit their theory using central concepts about double categories. We show that, under mild hypotheses, double categories of structured cospans are cocartesian (have finite double-categorical coproducts) and are equipments. The proofs are simple as they utilize appropriate double-categorical universal properties. Maps between double categories of structured cospans are studied from the same perspective. We then give a new construction of the double category of decorated cospans using the recently introduced double Grothendieck construction. Besides its conceptual value, this reconstruction leads to a natural generalization of decorated cospans, which we illustrate through an example motivated by statistical theories and other theories of processes.
titleStructured and Decorated Cospans from the Viewpoint of Double Category Theory
ematics - Category Theory

abstractIn the foundational logical framework of homotopy-type theory we discuss a natural formalization of secondary integral transforms in stable geometric homotopy theory. We observe that this yields a process of non-perturbative cohomological quantization of local pre-quantum field theory; and show that quantum anomaly cancellation amounts to realizing this as the boundary of a field theory that is given by genuine (primary) integral transforms, hence by linear polynomial functors. Recalling that traditional linear logic has semantics in symmetric monoidal categories and serves to formalize quantum mechanics, what we consider is its refinement to linear homotopy-type theory with semantics in stable infinity-categories of bundles of stable homotopy types (generalized cohomology theories) formalizing Lagrangian quantum field theory, following Nuiten and closely related to recent work by Haugseng and Hopkins-Lurie. For the reader interested in technical problems of quantization we provide non-perturbative quantization of Poisson manifolds and of the superstring; and find insight into quantum anomaly cancellation, the holographic principle and motivic structures in quantization. For the reader inclined to the interpretation of quantum mechanics we exhibit quantum superposition and interference as existential quantification in linear homotopy-type theory. For the reader inclined to foundations we provide a refinement of the proposal by Lawvere for a formal foundation of physics, lifted from classical continuum mechanics to local Lagrangian quantum gauge field theory.
titleQuantization via Linear Homotopy Types

abstractWiring diagrams, as seen in digital circuits, can be nested hierarchically and thus have an aspect of self-similarity. We show that wiring diagrams form the morphisms of an operad $\mcT$, capturing this self-similarity. We discuss the algebra $\Rel$ of mathematical relations on $\mcT$, and in so doing use wiring diagrams as a graphical language with which to structure queries on relational databases. We give the example of circuit diagrams as a special case. We move on to show how plug-and-play devices and also recursion can be formulated in the operadic framework as well. Throughout we include many examples and figures.
eprintclasscs, math
shorttitleThe Operad of Wiring Diagrams
titleThe Operad of Wiring Diagrams: Formalizing a Graphical Language for Databases, Recursion, and Plug-and-Play Circuits
il,E.1,F.4.1,G.2.2,G.4,H.2.1,H.2.3,H.5,Mathematics - Category Theory,Mathematics - Logic

College Park, MD

Open Publishing Association

abstractWe characterize a number of well known systems of approximate inference as loss models: lax sections of 2-fibrations of statistical games, constructed by attaching internally-defined loss functions to Bayesian lenses. Our examples include the relative entropy, which constitutes a strict section, and whose chain rule is formalized by the horizontal composition of the 2-fibration. In order to capture this compositional structure, we first introduce the notion of `copy-composition', alongside corresponding bicategories through which the composition of copy-discard categories factorizes. These bicategories are a variant of the $\mathbf{Copara}$ construction, and so we additionally introduce coparameterized Bayesian lenses, proving that coparameterized Bayesian updates compose optically, as in the non-coparameterized case.
booktitleElectronic Proceedings in Theoretical Computer Science
eprintclassmath, stat
eventtitleApplied Category Theory 2023
titleApproximate Inference via Fibrations of Statistical Games
ematics - Category Theory,Mathematics - Statistics Theory

Springer Berlin Heidelberg

abstractWe show that a measure-based denotational semantics for probabilistic programming is commutative. The idea underlying probabilistic programming languages (Anglican, Church, Hakaru, etc.) is that programs express statistical models as a combination of prior distributions and likelihood of observations. The product of prior and likelihood is an unnormalized posterior distribution, and the inference problem is to find the normalizing constant. One common semantic perspective is thus that a probabilistic program is understood as an unnormalized posterior measure, in the sense of measure theory, and the normalizing constant is the measure of the entire semantic domain. A programming language is said to be commutative if only data flow is meaningful; control flow is irrelevant, and expressions can be re-ordered. It has been unclear whether probabilistic programs are commutative because it is well-known that Fubini-Tonelli theorems for reordering integration fail in general. We show that probabilistic programs are in fact commutative, by characterizing the measures/kernels that arise from programs as ‘s-finite’, i.e. sums of finite measures/kernels. The result is of theoretical interest, but also of practical interest, because program transformations based on commutativity help with symbolic inference and can improve the efficiency of simulation.
booktitleProgramming Languages and Systems
titleCommutative Semantics for Probabilistic Programming

Now Publishers

abstractThe formalism of probabilistic graphical models provides a unifying framework for capturing complex dependencies among random variables, and building large-scale multivariate statistical models. Graphical models have become a focus of research in many statistical, computational and mathematical fields, including bioinformatics, communication theory, statistical physics, combinatorial optimization, signal and image processing, information retrieval and statistical machine learning. Many problems that arise in specific instances — including the key problems of computing marginals and modes of probability distributions — are best studied in the general setting. Working with exponential family representations, and exploiting the conjugate duality between the cumulant function and the entropy for exponential families, we develop general variational representations of the problems of computing likelihoods, marginal probabilities and most probable configurations. We describe how a wide variety of algorithms — among them sum-product, cluster variational methods, expectation-propagation, mean field methods, max-product and linear programming relaxation, as well as conic programming relaxations — can all be understood in terms of exact or approximate forms of these variational representations. The variational approach provides a complementary alternative to Markov chain Monte Carlo as a general source of approximation methods for inference in large-scale statistical models.
journaltitleFoundations and Trends® in Machine Learning
shortjournalFoundations and Trends® in Machine Learning
titleGraphical Models, Exponential Families, and Variational Inference

Springer International Publishing

abstractThis monograph is a comprehensive study of the combinatorial structure of various operads of wiring diagrams and undirected wiring diagrams. Our first main objective is to prove a finite presentation theorem for each operad of wiring diagrams, describing each one in terms of just a few operadic generators and a small number of generating relations. For example, the operad of wiring diagrams has 8 generators and 28 generating relations, while the operad of undirected wiring diagrams has 6 generators and 17 generating relations. Our second main objective is to prove a corresponding finite presentation theorem for algebras over each operad of wiring diagrams. As applications we provide finite presentations for the propagator algebra, the algebra of discrete systems, the algebra of open dynamical systems, and the (typed) relational algebra. We also provide a partial verification of Spivak's conjecture regarding the quotient-freeness of the relational algebra. Our third main objective is to construct explicit operad maps among the several operads of wiring diagrams. In particular, there is a surjective operad map from the operad of all wiring diagrams, including delay nodes, to the operad of undirected wiring diagrams. This monograph is intended for graduate students, mathematicians, scientists, and engineers interested in operads and wiring diagrams. Assuming no prior knowledge of categories, operads, and wiring diagrams, this monograph is self-contained and can be used as a supplement in a graduate course and for independent study. There are over 100 graphical illustrations and a chapter with a list of problems.
isbn978-3-319-95000-6 978-3-319-95001-3
seriesLecture Notes in Mathematics
titleOperads of Wiring Diagrams
08A70,08A70 18B20 18D50 68Q05 37C60,18B20,18D50,37C60,68Q05,act24,dphil,math.CT,math.DS,Mathematics - Category Theory,Mathematics - Dynamical Systems

§ DIRECTED MODELS

§.§ Kernels bifibration

Suppose $(E,p)\xkto{h}(F,q)\xkto{k}(G,r)$ over $B$.
Then, by the definitions of fibrewise restriction and of kernel composition,

$$ (k\circ h)[b] : (x_b, V_b) \mapsto \int_{y:F} k\bigl(y, \pi_G(V_b)\bigr) \, h\bigl(\pi_E(x_b), \d y\bigr) \; . $$

Now, by the condition on kernels over $B$, the measure $h\bigl(\pi_E(x_b),-\bigr)$ is only supported over $b$, so we can write the integral as

$$ \int_{y_b:q[b]} k\bigl(\pi_F(y_b), \pi_G(V_b)\bigr) \, h\bigl(\pi_E(x_b), \pi_F(\d y)\bigr) \; . $$

But, again by their definition, this is equal to

$$ \int_{y_b:q[b]} k[b](y_b, V_b) \, h[b](x_b, \d y_b) $$

and hence to $(k[b]\circ h[b])(x_b, V_b)$.
So $(k\circ h)[b] = k[b]\circ h[b]$.

Suppose $k:X\kto Y$ is a kernel and $f:Y\to Z$ is a measurable function.
Then the pushforward of $k$ along $f$, sometimes denoted $f_*k$, is the kernel $X\kto Z$ defined by the composite $\delta_f\circ k$ in $\sfKrn$.
Note that this composite satisfies $(\delta_f\circ k)(x,C) = k\bigl(x,f^{-1}(C)\bigr)$ where $f^{-1}(C)$ is the preimage of $C$ through $f$.

We need to exhibit an isomorphism

\[\begin{tikzcd}
{\mathcal{K}_B(p,\Delta_fq)} && {\mathcal{K}_C(\Sigma_fp,q)}
\arrow["{(-)^\flat}"{description}, curve={height=-12pt}, from=1-1, to=1-3]
\arrow["{(-)^\sharp}"{description}, curve={height=-12pt}, from=1-3, to=1-1]
\end{tikzcd}\]

natural in $p$ and $q$.

Suppose then that we have $\beta:p\kto\Delta_fq$ in $\Ka_B$ and $\gamma:\Sigma_fp\kto q$ in $\Ka_C$ as in the following diagrams:

\[\begin{tikzcd}[column sep=small]
E &&&& {f^*F} &&& E &&&& F \\
&&&&&&&& B \\
&& B &&&&&&& C
\arrow["p"', from=1-1, to=3-3]
\arrow["\beta", squiggly, from=1-1, to=1-5]
\arrow["{f^*q}", from=1-5, to=3-3]
\arrow["p"', from=1-8, to=2-9]
\arrow["f"', from=2-9, to=3-10]
\arrow["q", from=1-12, to=3-10]
\arrow["\gamma", squiggly, from=1-8, to=1-12]
\end{tikzcd}\]

Define $\beta^\flat:\Sigma_fp\kto q$ by the kernel

$$ E\times\Sigma_F\to[0,\infty] : (x,V) \mapsto \beta\bigl(x,\pi_F^{-1}(V)\bigr) $$

where $\pi_F^{-1}(V)$ is the preimage of $V$ through the projection $\pi_F:f^*F\to F$ out of the pullback $f^*F$.

Dually, define $\gamma^\sharp:p\kto\Delta_fq$ by the kernel

$$ E\times\Sigma_{f^*F}\to[0,\infty] : (x,U) \mapsto \gamma\bigl(x,\pi_F(U)\bigr) \; . $$

Our first task is to check that these yield well-defined morphisms: that $\beta^\flat$ and $\gamma^\sharp$ satisfy the triangle conditions in $\Ka_C$ and $\Ka_B$ respectively, that $\delta_q\circ\beta^\flat = \delta_{f\circ p}$ and $\delta_{f^*q}\circ\gamma^\sharp = \delta_p$.
For the former, we have the following chain of equalities:

\begin{align*}
\bigl(\delta_q\circ\beta^\flat\bigr)(x,V)
&=  \beta^\flat\bigl(x,q^{-1}(V)\bigr) & & \text{by pushforward (Def. \ref{def:pshfwd})} \\
&=  \beta\bigl(x, \pi_F^{-1}q^{-1}(V)\bigr) & & \text{by definition of $\flat$} \\
&=  \beta\bigl(x, (f^*q)^{-1}f^{-1}(V)\bigr) & & \text{by pullback of $q$ along $f$} \\
&=  (\delta_{f^*q}\circ\beta)\bigl(x,f^{-1}(V)\bigr) & & \text{by pushforward} \\
&=  \bigl[p(x) \in f^{-1}(V)\bigr] & & \text{since $\delta_p = \delta_{f^*q}\circ\beta$ in $\Ka_B$} \\
&=  [(f\circ p)(x)\in V] & & \text{by preimage} \\
&=  \delta_{f\circ p}(x, V) & & \text{by definition of $\delta$}
\end{align*}

Similarly, for the latter, we have the following:

\begin{align*}
\bigl(\delta_{f^*q}\circ\gamma^\sharp\bigr)(x,U)
&= \gamma^\sharp\bigl(x, (f^*q)^{-1}(U)\bigr) && \text{by pushforward} \\
&= \gamma\bigl(x, \pi_F((f^*q)^{-1}(U))\bigr) && \text{by definition of $\sharp$} \\
&= \gamma\bigl(x, q^{-1}(f(U))\bigr) && \text{by pullback of $q$ along $f$} \\
&= (\delta_q\circ\gamma)\bigl(x, q^{-1}(f(U))\bigr) && \text{by pushforward} \\
&= \bigl[p(x) \in f^{-1}\bigl(f(U)\bigr)\bigr] && \text{since $\delta_{f\circ p}= \delta_q\circ\gamma$ in $\Ka_C$} \\
&= \bigl[p(x) \in U\bigl] && \text{by preimage} \\
&= \delta_p(x,U) && \text{by definition of $\delta$}
\end{align*}

This establishes that $\beta^\flat$ and $\gamma^\sharp$ are well-defined morphisms in their respective fibre categories.
That the maps $(-)^\flat$ and $(-)^\sharp$ constitute an isomorphism of hom sets is immediate from the fact that images and preimages are mutually inverse: $\pi_F^{-1}(\pi_F(U)) = U$ and $\pi_F(\pi_F^{-1}(V)) = V$.

It therefore only remains to demonstrate naturality.
Since $(-)^\flat$ and $(-)^\sharp$ are mutually inverse, we need only demonstrate naturality for one; we choose $(-)^\sharp$.
This means showing that the following square commutes for all kernels $\varphi,\psi$ of appropriate type:

\[\begin{tikzcd}
{\mathcal{K}_C(\Sigma_fp,q)} && {\mathcal{K}_B(p,\Delta_fq)} \\
\\
{\mathcal{K}_C(\Sigma_fo,r)} && {\mathcal{K}_B(o,\Delta_fr)}
\arrow["{(-)^\sharp_{p,q}}", from=1-1, to=1-3]
\arrow["{(-)^\sharp_{o,r}}", from=3-1, to=3-3]
\arrow["{\mathcal{K}_C(\Sigma_f\varphi,\psi)}"', from=1-1, to=3-1]
\arrow["{\mathcal{K}_B(\varphi,\Delta_f\psi)}", from=1-3, to=3-3]
\end{tikzcd}\]

Since the hom functors $\Ka_C$ and $\Ka_B$ act by pre- and post-composition, this requires establishing that

$$ o\xkto{\varphi}p\xkto{\gamma^\sharp}\Delta_f\,q\xkto{\Delta_f\,\psi}\Delta_f\,r
= \left( \Sigma_f\,o\xkto{\Sigma_f\,\varphi}\Sigma_f\,p\xkto{\gamma}q\xkto{\psi}r \right)^{\sharp} \; . $$

We noted above that $\Sigma_f\,p [b] \cong p[f^*b]$; likewise, we have $\Delta_f\,q[b] \cong q[f\circ b]$, since the pasting of two pullback squares is again a pullback square:

\[\begin{tikzcd}
{(\Delta_f\,q)[b]\cong q[f\circ b]} & {f^*F} & F \\
J & B & C
\arrow["f", from=2-2, to=2-3]
\arrow["b", from=2-1, to=2-2]
\arrow["{(f\circ b)^*q}"', from=1-1, to=2-1]
\arrow["{f^*q}"', from=1-2, to=2-2]
\arrow["{\pi_F}", from=1-2, to=1-3]
\arrow["q", from=1-3, to=2-3]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-2, to=2-3]
\arrow["{\pi_{f^*F}}", from=1-1, to=1-2]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-1, to=2-2]
\end{tikzcd}\]

Thus, working fibrewise, we have

$$ \gamma^\sharp[b](x,U) = \gamma^\sharp\bigl(\pi_E(x),\pi_{f^*F}(U)\bigr) = \gamma\bigl(\pi_E(x),(\pi_F\circ\pi_{f^*F})(U)\bigr) = \gamma[f\circ b](x, U) $$

i.e. $\gamma^\sharp_b = \gamma[f\circ b]$, and so

\begin{align*}
&= (\psi\circ\gamma\circ\Sigma_f\,\varphi)[f\circ b](w,V) \\
&\qquad\qquad\quad\text{(since $\gamma^\sharp[b] = \gamma[f\circ b]$)}\\
&= \int_{y:q[f\circ b]} \psi[f\circ b](y,V) \, \int_{x:\Sigma_f\,p[f\circ b]} \gamma[f\circ b](x,\d y) \, \left(\Sigma_f\,\varphi\right)[f\circ b](w,\d x) \\
&\qquad\qquad\quad\text{(by fibrewise composition)} \\
&= \int_{y:q[f\circ b]} \psi[f\circ b](y,V) \, \int_{x:p[b]} \gamma[f\circ b](x,\d y)\, \varphi[b](w,\d x) \\
&\qquad\qquad\quad\text{(since $\Sigma_f\,p[f\circ b] \cong p[f^*(f\circ b)] \cong p[b]$)} \\
&= \int_{y:q[f\circ b]} \psi[f\circ b](y,V) \, \int_{x:p[b]} \gamma^\sharp[b](x,\d y)\, \varphi[b](w,\d x) \\
&\qquad\qquad\quad\text{(since $\gamma^\sharp[b] = \gamma[f\circ b]$)}\\
&= \int_{y:\Delta_f\,q[b]} (\Delta_f\,\psi)[b](y,V) \, \int_{x:p[b]} \gamma^\sharp[b](x,\d y)\, \varphi[b](w,\d x) \\
&\qquad\qquad\quad\text{(since $q[f\circ b]\cong\Delta_f\,q[b]$)} \\
&= (\Delta_f\,\psi\circ\gamma^\sharp\circ\varphi)[b](w,V) \\
&\qquad\qquad\quad\text{(by fibrewise composition).}
\end{align*}

This establishes that $\Sigma_f \dashv \Delta_f$.

The functor $\Sigma_\rho\,\Delta_\pi : \Ka_E\to\Ka_F$ sends $X\xto{\alpha}E$ to $\pi^*X\xto{\Delta_\pi\,\alpha}P\xto{\rho}F$; fibrewise, by adjointness, we have $\Sigma_\rho\,\Delta_\pi(\alpha)[i] \cong \alpha[\pi\circ\rho^*i]$ and, on morphisms $f$, we have $\Sigma_\rho\,\Delta_\pi(f)[i] = f[\pi\circ\rho^*i]$.
On the other side, the functor $\Delta_q\,\Sigma_p$ sends $\alpha$ to $q^*X\xto{\Delta_q\,\alpha}q^*E\xto{\Delta_q\,p}F$; fibrewise, we have $\Delta_q\,\Sigma_p(\alpha)[i] \cong \alpha[p^*(q\circ i)]$ on objects and $\Delta_q\,\Sigma_p(f)[i] = f[p^*(q\circ i)]$ on morphisms.
It therefore suffices to show that $p^*(q\circ i) = \pi\circ\rho^*i$ in $\Meas$.
This follows from the universal property of the pullback, which implies that the pasting of two pullback squares is again a pullback square:

\[\begin{tikzcd}
\bullet & P & E \\
I & F & B
\arrow["i"', from=2-1, to=2-2]
\arrow["q"', from=2-2, to=2-3]
\arrow["p", from=1-3, to=2-3]
\arrow["\pi", from=1-2, to=1-3]
\arrow["\rho"', from=1-2, to=2-2]
\arrow[from=1-1, to=2-1]
\arrow["{\rho^*i}", from=1-1, to=1-2]
\arrow["{p^*(q\circ i)}", curve={height=-18pt}, from=1-1, to=1-3]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-1, to=2-2]
\arrow["\lrcorner"{anchor=center, pos=0.125}, draw=none, from=1-2, to=2-3]
\end{tikzcd}\]

The outer and inner squares are thus both pullbacks of $p$ along $q\circ i$, and hence we must have $p^*(q\circ i) = \pi\circ\rho^*i$.
This yields an isomorphism $\Sigma_\rho\,\Delta_\pi(\alpha) \cong \Delta_q\,\Sigma_p(\alpha)$ rather than an equality because universal constructions are only unique up to natural isomorphism; and thus the naturality of this isomorphism follows similarly from universality.

§.§ Pull-push sections

Much of the structure is simplified, owing to the trivial vertical decorations and the decoration of the apices by sets.
Thus, for example, each component $\mu_{m,n}$ or $\eta_E$ of the pseudo natural transformations $\mu$ or $\eta$ is only a function (discrete functor).
In the main text, the functoriality of $S_0$ and $S_1$ is justified.
So here we will only justify the (pseudo) naturality of $\mu$ and $\eta$ and their (pseudo) associativity and unitality.

Suppose then that $f:m\to m'$ and $g:n\to n'$ are horizontally composable morphisms of spans (i.e., such that $g_l=f_r$) from $m=\bigl(A\xleftarrow{a}E\xto{b}B\bigr)$ and $n=\bigl(B\xleftarrow{\bar{b}}F\xto{c}C\bigr)$ to $m'=\bigl(A'\xleftarrow{a'}E'\xto{b'}B'\bigr)$ and $n'=\bigl(B'\xleftarrow{\bar{b}'}F\xto{c'}C'\bigr)$.
To validate the pseudo naturality of $\mu$ is to confirm the commutativity of the square

\[\begin{tikzcd}[cramped,sep=small]
{S_1(m')\times S_1(n')} && {S_1(n'\diamond m')} \\
\\
{S_1(m)\times S_1(n)} && {S_1(n\diamond m)}
\arrow["{\mu_{m',n'}}", from=1-1, to=1-3]
\arrow["{S_1(f)\times S_1(g)}"', from=1-1, to=3-1]
\arrow["{S_1(g\diamond f)}", from=1-3, to=3-3]
\arrow["{\mu_{m,n}}"', from=3-1, to=3-3]
\end{tikzcd} \; .\]

up to natural isomorphism.
The top-right composite evaluates to

\begin{align*}
S_1(g\diamond f)\bigl(\Sigma_{a'}\,\Delta_{b'}(\tau')\circ\sigma'\bigr)
&= \Delta_{f_l}\bigl(\Sigma_{a'}\,\Delta_{b'}(\tau')\circ\sigma'\bigr) & \text{(by definition)} \\
&= \Delta_{f_l}\,\Sigma_{a'}\,\Delta_{b'}(\tau') \circ \Delta_{f_l}(\sigma') & \text{(by functoriality)}
\end{align*}

while the left-bottom composite evaluates to

\begin{align*}
\Sigma_a\,\Delta_b\bigl(S_1(g)(\tau')\bigr)\circ S_1(f)(\sigma') &= \Sigma_a\,\Delta_b\,\Delta_{g_l}(\tau')\circ \Delta_{f_l}(\sigma') & \text{(by definition}) \\
&= \Sigma_a\,\Delta_f\,\Delta_{b'}(\tau')\circ \Delta_{f_l}(\sigma') & \text{(since $g_l\circ b = b'\circ f$)} \\
&\cong \Delta_{f_l}\,\Sigma_{a'}\,\Delta_{b'}(\tau')\circ \Delta_{f_l}(\sigma') & \text{(by Beck-Chevalley)}
\end{align*}

and so $S_1(g\diamond f)\circ\mu_{m',n'} \cong \mu_{m,n}\circ\bigl(S_1(f)\times S_1(g)\bigr)$ as required.

Validating the pseudo naturality of $\eta$ means, for any $f:E\to F$ in $\Ba$, validating that $\eta_F \cong S_1(f)\circ \eta_E$, i.e., $\eta_F \cong \Delta_f\,\eta_E$.
Since $\eta_E$ is the identity on $\iota E$ and $\Delta_f$ is a functor, it must preserve identities.
So in fact $\eta$ is strictly natural (just as pull-push copy-composition is strictly unital, as we confirm below).

To validate pseudo associativity, suppose $m$ and $n$ are spans as before and $o=\bigl(C\xleftarrow{\bar{c}}G\xto{d}D\bigr)$.
We need to show that $\mu_{n\diamond m,o}\bigl(\mu_{m,n}(\sigma,\tau),\rho\bigr) \cong \mu_{m,o\diamond n}\bigl(\sigma,\mu_{n,o}(\tau,\rho)\bigr)$ for all appropriately typed sections $\sigma,\tau,\rho$.
This obtains as follows:

\begin{align*}
\mu_{n\diamond m,o}\bigl(\mu_{m,n}(\sigma,\tau),\rho\bigr)
&= \mu_{n\diamond m,o}\bigl(\Sigma_a\,\Delta_b(\tau)\circ\sigma,\rho\bigr) & \text{(by definition)} \\
&= \Sigma_a\,\Sigma_{\pi_E}\,\Delta_{\pi_F}\,\Delta_c(\rho) \circ \Sigma_a\,\Delta_b(\tau)\circ\sigma & \text{(by definition)} \\
&\cong \Sigma_a\,\Delta_b\,\Sigma_{\bar{b}}\,\Delta_c(\rho) \circ \Sigma_a\,\Delta_b(\tau) \circ \sigma & \text{(by Beck-Chevalley)} \\
&= \Sigma_a\,\Delta_b\bigl(\Sigma_{\bar{b}}\,\Delta_c(\rho) \circ \tau\bigr) \circ \sigma & \text{(by functoriality)} \\
&= \mu_{m,o\diamond n}\bigl(\sigma, \Sigma_{\bar{b}}\,\Delta_c(\rho)\circ\tau\bigr) & \text{(by definition)} \\
&= \mu_{m,o\diamond n}\bigl(\sigma,\mu_{n,o}(\tau,\rho)\bigr) & \text{(by definition)}
\end{align*}

where $\pi_E$ and $\pi_F$ are the projections out of the pullback of $\bar{b}$ along $b$.

Finally, strict unitality demands that $\mu_{\id_B,n}(\eta_B,\tau) = \tau$ and $\mu_{m,\id_B}(\sigma,\eta_B) = \sigma$.
We have

$$ \mu_{\id_B,n}(\eta_B,\tau) = \Sigma_{\id_B}\,\Delta_{\id_B}(\tau)\circ\eta_B = \tau\circ\id_{\iota_B} = \tau $$

$$ \mu_{m,\id_B}(\sigma,\eta_B) = \Sigma_a\,\Delta_b(\eta_B)\circ\sigma = \Sigma_a\,\Delta_b(\id_{\iota_B})\circ\sigma = \Sigma_a(\id_{\iota_E})\circ\sigma = \id_{\Sigma_a\,\iota_E}\circ\sigma = \sigma $$

as required.

§ FACTOR GRAPHS

§.§ Constructing the horizontal decorations

The apex decoration has a peculiar form, with one category of decorating data (the interfaces) further decorated by a family of others (the factors).
This is because the apex decorations are themselves obtained by a Grothendieck construction, defined functorially for each finite set.
The first step in this construction is to define the interface categories.
Since we have the cospans determining which parts of the interfaces are exposed for factor composition, there may now be some parts which remain `latent', and transformations of these parts are not constrained to be comonoid homomorphisms.
That is, we can allow the transformations of the latent parts of the interfaces to be arbitrary morphisms in $\Ca$, as long as the exposed parts remain constrained as before[
It is this part of the construction that means we cannot use Fong's original decorated cospans: here, the decoration on the apex necessarily depends on the legs, in order that we have comonoid homomorphisms in the right places.].

This line of thought formalizes as follows.
Given a cospan $m:\bigl(A\xrightarrow{a} X\xleftarrow{b} B\bigr)$, we first define an enlarged version of $F_0X$, not totally restricted to comonoid homomorphisms.
We denote this enlargement by $\tilde{F_0}m$ and construct it as the following limit of categories, so that we do still have comonoid homomorphisms over the legs:

\[\begin{tikzcd}
{\mathbf{Cat}\bigl(\mathsf{disc}\,A,\mathbf{Comon}(\mathcal{C})\bigr)} && {\tilde{F_0}m} && {\mathbf{Cat}\bigl(\mathsf{disc}\,B,\mathbf{Comon}(\mathcal{C})\bigr)} \\
\\
{\mathbf{Cat}(\mathsf{disc}\,A,\mathcal{C})} && {\mathbf{Cat}(\mathsf{disc}\,X,\mathcal{C})} && {\mathbf{Cat}(\mathsf{disc}\,B,\mathcal{C})}
\arrow["{\mathbf{Cat}(\mathsf{disc}\,a,\mathcal{C})}", from=3-3, to=3-1]
\arrow["{\mathbf{Cat}(\mathsf{disc}\,b,\mathcal{C})}"', from=3-3, to=3-5]
\arrow[hook, from=1-1, to=3-1]
\arrow[hook, from=1-5, to=3-5]
\arrow[dashed, from=1-3, to=1-1]
\arrow[dashed, from=1-3, to=3-3]
\arrow[dashed, from=1-3, to=1-5]
\end{tikzcd}\]

Note that, because the left and right vertical functors in this diagram are embeddings, so is the induced functor $\tilde{F_0}m\to\Cat(\disc X,\Ca)$.
We can therefore understand $\tilde{F_0}m$ as the wide subcategory of $\Cat(\disc X,\Ca)$ whose morphisms are those $X$-indexed families of morphisms of $\Ca$ whose $A$- and $B$-components are comonoid homomorphisms.

The next step is to decorate $\tilde{F_0}m$ with factors.
Since $\Ca$ is a category, factors on an interface $\chi:\disc X\to\Ca$ form a set $\Ca(\chi^\otimes,I)$.
We thus define a presheaf $\underline{F_1}m:\tilde{F_0}m\op\to\Set$ as follows.
On objects (interfaces) $\chi$, we define $\underline{F_1}m(\chi)$ to be $\Ca(\chi^\otimes,I)$.
On morphisms of interfaces $\varphi:\chi\to\chi'$, we set $\underline{F_1}m(\varphi):\underline{F_1}m(\chi')\to\underline{F_1}m(\chi)$ to be the precomposition functor $\Ca(\varphi^\otimes,I):\Ca({\chi'}^\otimes,I)\to\Ca(\chi^\otimes,I)$ and denote it by $\varphi^*$.
This yields a well-defined presheaf by the functoriality of $\otimes$ and of precomposition.
The apex decoration returned by $F_1$ on $m$ is then given by the 1-categorical Grothendieck construction of $\underline{F_1}m$ (its category of elements), denoted $\int\underline{F_1}m$, whose objects and morphisms are as described in the main text.

This tells us how to decorate the apices of cospans — but, given the cospan $m$, $F_1$ needs to return a whole span of categories $F_0A \xleftarrow{\pi_a} \int\underline{F_1}m \xrightarrow{\pi_b} F_0B$.
We obtain the legs of this span through the universal properties of the construction of $\int\underline{F_1}m$.
First, because $\int\underline{F_1}m$ is obtained by a Grothendieck construction, it is equipped with a projection functor $\pi_m : \int\underline{F_1}m \to \tilde{F_0}m$ which acts by `forgetting' the factors; i.e. $\pi_m(\chi,f) = \chi$.
Next, the construction of $\tilde{F_0}m$ as a limit means that it is equipped with canonical projection functors to $F_0A$ and $F_0B$:

\[\begin{tikzcd}
{F_0A=\mathbf{Cat}\bigl(\mathsf{disc}\,A,\mathbf{Comon}(\mathcal{C})\bigr)} & {\tilde{F_0}m} & {\mathbf{Cat}\bigl(\mathsf{disc}\,B,\mathbf{Comon}(\mathcal{C})\bigr)=F_0B}
\arrow[dashed, from=1-2, to=1-3]
\arrow[dashed, from=1-2, to=1-1]
\end{tikzcd}\]

Therefore, we obtain the requisite span of categories
$F_1m := \bigl(F_0A \xleftarrow{\pi_a} \int\underline{F_1}m \xrightarrow{\pi_b} F_0B\bigr)$
as the composition of this span of limit projections with $\pi_m$:

\[\begin{tikzcd}
&& {\displaystyle\int\underline{F_1}m} \\
\\
{F_0A} && {\tilde{F_0}m} && {F_0B}
\arrow[dashed, from=3-3, to=3-5]
\arrow[dashed, from=3-3, to=3-1]
\arrow["{\pi_m}", from=1-3, to=3-3]
\arrow["{\pi_a}"', curve={height=18pt}, from=1-3, to=3-1]
\arrow["{\pi_b}", curve={height=-18pt}, from=1-3, to=3-5]
\end{tikzcd}\]

We now need to define the action of $F_1$ on morphisms of cospans.
Suppose that $m' := \bigl(A'\xleftarrow{a'}X'\xrightarrow{B'}\bigr)$ is another cospan.
A morphism $\phi:m\to m'$ is a triple $(\phi_l,\phi,\phi_r)$ of maps of finite sets making the following diagram commute:

\[\begin{tikzcd}
A && X && B \\
\\
{A'} && {X'} && {B'}
\arrow["a", from=1-1, to=1-3]
\arrow["{a'}"', from=3-1, to=3-3]
\arrow["{\phi_l}"', from=1-1, to=3-1]
\arrow["\phi", from=1-3, to=3-3]
\arrow["b"', from=1-5, to=1-3]
\arrow["{\phi_r}", from=1-5, to=3-5]
\arrow["{b'}", from=3-5, to=3-3]
\end{tikzcd}\]

We know from the treatment above that $F_0$ is functorial, and this yields the action of $F_1$ on the left and right components $\phi_l$ and $\phi_r$.
Moreover, the construction of $\int\underline{F_1}m$ is functorial: first, the construction of $\tilde{F_0}m$ is functorial in $m$, by the functoriality of taking limits.
Likewise, the Grothendieck construction is functorial, yielding a functor $\int\underline{F_1} : \FinSet^{\{\bullet\to\bullet\leftarrow\bullet\}} \to \Cat$.
The following diagram then commutes by construction:

\[\begin{tikzcd}
{F_0A} && {\displaystyle\int\underline{F_1}m} && {F_0B} \\
\\
{F_0A'} && {\displaystyle\int\underline{F_1}m'} && {F_0B'}
\arrow["{\pi_a}"', from=1-3, to=1-1]
\arrow["{\pi_{a'}}", from=3-3, to=3-1]
\arrow["{F_0\phi_l}"', from=1-1, to=3-1]
\arrow["{\int\underline{F_1}\phi}", from=1-3, to=3-3]
\arrow["{\pi_b}", from=1-3, to=1-5]
\arrow["{F_0\phi_r}", from=1-5, to=3-5]
\arrow["{\pi_{b'}}"', from=3-3, to=3-5]
\end{tikzcd}\]

Consequently, we define the action of $F_1$ on the morphism of cospans $\phi$ to return the morphism of spans $F_1\phi$ whose components are $(F_0\phi_l,\int\underline{F_1}\phi,F_0\phi_r)$, and we see that this action is functorial by construction.

§.§ The horizontal composition

$\mu$ must be a pseudo natural transformation filling the following diagram:

\[\begin{tikzcd}
{\mathbf{FinSet}^{\{\bullet\to\bullet\leftarrow\bullet\}}\times_{\mathbf{FinSet}}\mathbf{FinSet}^{\{\bullet\to\bullet\leftarrow\bullet\}}} && {\mathbf{FinSet}^{\{\bullet\to\bullet\leftarrow\bullet\}}} \\
\\
{\mathbf{Cat}^{\{\bullet\leftarrow\bullet\to\bullet\}}\times_{\mathbf{Cat}}\mathbf{Cat}^{\{\bullet\leftarrow\bullet\to\bullet\}}} && {\mathbf{Cat}^{\{\bullet\leftarrow\bullet\to\bullet\}}}
\arrow["{\diamond_{\Bbb{C}\mathbf{ospan}(\mathbf{FinSet})}}", from=1-1, to=1-3]
\arrow["{F_1\times F_1}"', from=1-1, to=3-1]
\arrow["{\diamond_{\Bbb{S}\mathbf{pan}(\mathbf{Cat})}}"', from=3-1, to=3-3]
\arrow["{F_1}", from=1-3, to=3-3]
\arrow["\mu", shorten <=35pt, shorten >=35pt, Rightarrow, from=3-1, to=1-3]
\end{tikzcd}\]

The external composition $\diamond_{\CCospan(\FinSet)}$ acts on composable cospans by pushout, taking $m:\bigl(A\xrightarrow{a}X\xleftarrow{b}B\bigr)$ and $n:\bigl(B\xrightarrow{b'}Y\xleftarrow{c}C\bigr)$ to the outer cospan in the pushout diagram

\[\begin{tikzcd}
&& {X+_BY} \\
& X && Y \\
A && B && C
\arrow["a", from=3-1, to=2-2]
\arrow["b"', from=3-3, to=2-2]
\arrow["{b'}", from=3-3, to=2-4]
\arrow["c"', from=3-5, to=2-4]
\arrow["{\iota_X}", from=2-2, to=1-3]
\arrow["{\iota_Y}"', from=2-4, to=1-3]
\end{tikzcd} \; .\]

(Psuedo functoriality of $\diamond_{\CCospan(\FinSet)}$ follows from the universal properties of colimits.)
The composite pseudo functor along the top and right of the above diagram therefore acts on $m$ and $n$ to yield the span of categories

$$F_0A \xleftarrow{\pi_{\iota_X\circ a}} \int\underline{F_1}(n\diamond m) \xrightarrow{\pi_{\iota_Y\circ c}} F_0C \; .$$

Dually, $\diamond_{\SSpan(\Cat)}$ acts on composable spans by pullback, so that the composite pseudo functor along the left and bottom of the diagram acts to yield the outer span in the following diagram:

\[\begin{tikzcd}
&& {\displaystyle\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n} \\
& {\displaystyle\int\underline{F_1}m} && {\displaystyle\int\underline{F_1}n} \\
{F_0A} && {F_0B} && {F_0C}
\arrow["{\pi_m}"', from=1-3, to=2-2]
\arrow["{\pi_n}", from=1-3, to=2-4]
\arrow["{\pi_b}", from=2-2, to=3-3]
\arrow["{\pi_{b'}}"', from=2-4, to=3-3]
\arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-45}, draw=none, from=1-3, to=3-3]
\arrow["{\pi_a}"', from=2-2, to=3-1]
\arrow["{\pi_c}", from=2-4, to=3-5]
\end{tikzcd}\]

Note that, here and throughout this section, $\pi_m$ and $\pi_n$ are the projections out of the pullback, rather than the Grothendieck fibrations of the previous section.

In both cases, the feet of the span are $F_0A$ and $F_0C$ on the left and right respectively; this must be the case for $F$ to be a well-defined double functor.
Consequently, the component of $\mu$ at $(m,n)$, denoted $\mu_{m,n}$, must be a functor $\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n\to\int\underline{F_1}(n\diamond m)$ making this diagram commute:

\[\begin{tikzcd}
&& {\displaystyle\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n} \\
& {\displaystyle\int\underline{F_1}m} && {\displaystyle\int\underline{F_1}n} \\
{F_0A} &&&& {F_0C} \\
&& {\displaystyle\int\underline{F_1}(n\diamond m)}
\arrow["{\pi_n}", from=1-3, to=2-4]
\arrow["{\pi_c}", from=2-4, to=3-5]
\arrow["{\pi_m}"', from=1-3, to=2-2]
\arrow["{\pi_a}"', from=2-2, to=3-1]
\arrow["{\mu_{m,n}}", from=1-3, to=4-3]
\arrow["{\pi_{\iota_X\circ a}}", curve={height=-12pt}, from=4-3, to=3-1]
\arrow["{\pi_{\iota_Y\circ c}}"', curve={height=12pt}, from=4-3, to=3-5]
\end{tikzcd}\]

This means that $\mu_{m,n}$ takes a pair of factors over $X$ and $Y$, that are composable by agreeing over $B$, and returns a composite factor over $X+_BY$, all while preserving the exposed interfaces over $A$ and $C$.
We define $\mu_{m,n}$ to act by copy-composition, as follows.

First, notice that both $\int\underline{F_1}(n\diamond m)$ and $\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n$ are (discrete) fibrations; the former over $\tilde{F_0}(n\diamond m)$ by definition and the latter over $\tilde{F_0}m\times_{F_0B}\tilde{F_0}n$, by the universal property of the pullback:

\[\begin{tikzcd}
& {\displaystyle\int\underline{F_1}m\times_{F_0B}\int\underline{F_1}n} \\
{\displaystyle\int\underline{F_1}m} && {\displaystyle\int\underline{F_1}n} \\
& {\tilde{F_0}m\times_{F_0B}\tilde{F_0}n} \\
{\tilde{F_0}m} && {\tilde{F_0}n} \\
& {F_0B}
\arrow[from=3-2, to=4-1]
\arrow[from=3-2, to=4-3]
\arrow[from=4-1, to=5-2]
\arrow[from=4-3, to=5-2]
\arrow["{\pi_m}"', from=2-1, to=4-1]
\arrow["{\pi_n}", from=2-3, to=4-3]
\arrow[from=1-2, to=2-1]
\arrow[from=1-2, to=2-3]
\arrow[dashed, from=1-2, to=3-2]
\arrow["\lrcorner"{anchor=center, pos=0.125, rotate=-45}, draw=none, from=3-2, to=5-2]
\end{tikzcd}\]

$\mu_{m,n}$ should therefore correspond to a morphism of fibrations.
By the Grothendieck construction [p.7]Moeller2018Monoidal, such a morphism is equivalent to a pair $(\mu^0_{m,n},\mu^1_{m,n})$ of a functor and a natural transformation as in the following diagram:

\[\begin{tikzcd}
{\bigl(\tilde{F_0}m\times_{F_0B}\tilde{F_0}n\bigr)^{\,\mathrm{op}}} && {\tilde{F_0}(n\diamond m)^{\,\mathrm{op}}} \\
\\
& {\mathbf{Set}}
\arrow["{\mu^{0\;\mathrm{op}}_{m,n}}", from=1-1, to=1-3]
\arrow[""{name=0, anchor=center, inner sep=0}, "{\bigl(\underline{F_1}m, \underline{F_1}n\bigr)}"', from=1-1, to=3-2]
\arrow[""{name=1, anchor=center, inner sep=0}, "{\underline{F_1}(n\diamond m)}", from=1-3, to=3-2]
\arrow["{\mu^1_{m,n}}", shorten <=11pt, shorten >=11pt, Rightarrow, from=0, to=1]
\end{tikzcd}\]

To define the functor $\mu^0_{m,n}: \tilde{F_0}m \times_{F_0B} \tilde{F_0}n \to \tilde{F_0}(n\diamond m)$, note that the objects in its domain are pairs $(\chi,\gamma)$ of functors $\chi:\disc X\to\Ca$ and $\gamma:\disc Y\to\Ca$ that agree on $B$.
By the universal properties of the coproduct $X+Y$ and the pushout $X+_BY$, there must be copairings $[\chi,\gamma]:\disc(X+Y)\to\Ca$ and $[\chi,\gamma]_B:\disc(X+_BY)\to\Ca$ making the following diagram commute; in particular, $[\chi,\gamma]$ must factor through $[\chi,\gamma]_B$:

\[\begin{tikzcd}
&& {\mathsf{disc}\,B} \\
\\
{\mathsf{disc}\,X} && {\mathsf{disc}\,(X+Y)} && {\mathsf{disc}\,Y} \\
\\
&& {\mathsf{disc}\,(X+_BY)} \\
\\
&& {\mathcal{C}}
\arrow["\chi"', curve={height=18pt}, from=3-1, to=7-3]
\arrow["\gamma", curve={height=-18pt}, from=3-5, to=7-3]
\arrow["{\mathsf{disc}\,b}"', curve={height=12pt}, from=1-3, to=3-1]
\arrow["{\mathsf{disc}\,b'}", curve={height=-12pt}, from=1-3, to=3-5]
\arrow["{\iota^X_B}"{description}, from=3-1, to=5-3]
\arrow["{\iota^Y_B}"{description}, from=3-5, to=5-3]
\arrow["{[\chi,\gamma]_B}"{description}, dashed, from=5-3, to=7-3]
\arrow["{\iota^X}", from=3-1, to=3-3]
\arrow["{\iota^Y}"', from=3-5, to=3-3]
\arrow["{[\iota^X_B,\iota^Y_B]}"{description}, dashed, from=3-3, to=5-3]
\end{tikzcd}\]

Since the image of $(\chi,\gamma)$ under $\mu^0_{m,n}$ must be a functor $\disc(X+_BY)\to\Ca$, we make the universal definition $\mu^0_{m,n}(\chi,\gamma) := [\chi,\gamma]_B$.
Functoriality follows from the functoriality of colimits.

The corresponding component of $\mu^1_{m,n}$ must then be a function

$$ \mu^1_{m,n}(\chi,\gamma) : \Ca(\chi^\otimes,I) \times \Ca(\gamma^\otimes,I) \to \Ca([\chi,\gamma]_B^\otimes,I) \; .$$

Note that $[\chi,\gamma]^\otimes \cong \chi^\otimes \otimes \gamma^\otimes$.
We can thus factor $\mu^1_{m,n}$ as

$$ \Ca(\chi^\otimes,I) \times \Ca(\gamma^\otimes,I) \xrightarrow{\otimes} \Ca(\chi^\otimes\otimes\gamma^\otimes,I) \xrightarrow{\sim} \Ca([\chi,\gamma]^\otimes,I) \to \Ca([\chi,\gamma]_B^\otimes,I)$$

so that, by Yoneda, we seek a morphism $\delta_{\chi,\gamma}:[\chi,\gamma]_B^\otimes \to [\chi,\gamma]^\otimes$ in $\Ca$.

It is here that copying finally enters.
For each $j:X+_BY$, copying induces a morphism

$$\delta_{\chi,\gamma}^j:[\chi,\gamma]_B(j) \to \bigotimes_{i:[\iota^X_B,\iota^Y_B]^{-1}(j)}\, [\chi,\gamma](i)$$

in $\Ca$ which is unique up to coassociativity.
Note that the codomain of this morphism is, by the pullback constraint, the monoidal product of $[\iota^X_B,\iota^Y_B]^{-1}(j)$-many copies of the same object $[\chi,\gamma]_B(j)$ so that this copying is well-defined; and when $j$ is not in the image of $B$, then this product is only unary, so that in this case, $\delta^j_{\chi,\gamma}$ is the corresonding identity morphism.

$$\bigotimes_{j:X+_BY} \delta_{\chi,\gamma}^j : \bigotimes_{j:X+_BY} [\chi,\gamma]_B(j) \to \bigotimes_{j:X+_BY} \bigotimes_{i:[\iota^X_B,\iota^Y_B]^{-1}(j)} [\chi,\gamma](i)$$

has the requisite type, since $\otimes_{j:X+_BY}\, [\chi,\gamma]_B(j) = [\chi,\gamma]_B^\otimes$ and

$$\bigotimes_{j:X+_BY} \bigotimes_{i:[\iota^X_B,\iota^Y_B]^{-1}(j)} [\chi,\gamma](i) = \bigotimes_{i:X+Y} [\chi,\gamma](i) = [\chi,\gamma]^\otimes$$

both by definition.
Hence we define $\delta_{\chi,\gamma} := \otimes_{j:X+_BY}\;\delta_{\chi,\gamma}^j$.

We need to verify that $\delta_{\chi,\gamma}$ is natural in $\chi$ and $\gamma$.
Since identity morphisms are always natural, we only need to check the case that $[\iota^X_B,\iota^Y_B]^{-1}(j)$ has more than one element — and this in turn only obtains for $j$ in the image of $B$.
By construction, morphisms of interfaces on those components are necessarily comonoid homomorphisms, and these are the morphisms for which $\delta^j_{\chi,\gamma}$ is natural.
Therefore, $\delta_{\chi,\gamma}$ is always natural in $\chi$ and $\gamma$, and since every factor of $\mu^1_{m,n}$ is accordingly natural, so is $\mu^1_{m,n}$ itself, as required.

This means that $(\mu^0_{m,n},\mu^1_{m,n})$ constitutes a well-defined morphism of indexed sets, thereby inducing a well-defined morphism $\mu_{m,n}$ of discrete fibrations.
Thus, given factors $(\chi,f)$ and $(\gamma,g)$ that agree over $B$, the external composition $\mu_{m,n}$ acts to return $\bigl([\chi,\gamma]_B,(f\otimes g)\circ\delta_{\chi,\gamma}\bigr)$.

We also need to define the unit $\eta$, a pseudo natural transformation as in the following diagram:

\[\begin{tikzcd}
{\mathbf{FinSet}} && {\mathbf{FinSet}^{\{\bullet\rightarrow\bullet\leftarrow\bullet\}}} \\
\\
{\mathbf{Cat}} && {\mathbf{Cat}^{\{\bullet\leftarrow\bullet\rightarrow\bullet\}}}
\arrow["{\mathsf{id}_{\mathbb{C}\mathbf{ospan}(\mathbf{FinSet})}}", from=1-1, to=1-3]
\arrow["{\mathsf{id}_{\mathbb{S}\mathbf{pan}(\mathbf{Cat})}}", from=3-1, to=3-3]
\arrow["{F_0}"', from=1-1, to=3-1]
\arrow["{F_1}", from=1-3, to=3-3]
\arrow["\eta", shorten <=15pt, shorten >=15pt, Rightarrow, from=3-1, to=1-3]
\end{tikzcd}\]

The component $\eta_X$ at each finite set $X$ is determined by a functor $\eta_X : F_0X \to \int\underline{F_1}(\id_X)$ as in the diagram

\[\begin{tikzcd}[cramped,sep=small]
{F_0X} && {F_0X} && {F_0X} \\
\\
{F_0X} && {\displaystyle\int\underline{F_1}(\mathsf{id}_X)} && {F_0X}
\arrow["{\pi_X}"', from=3-3, to=3-1]
\arrow["{\pi_X}", from=3-3, to=3-5]
\arrow[Rightarrow, no head, from=1-1, to=3-1]
\arrow[Rightarrow, no head, from=1-5, to=3-5]
\arrow[Rightarrow, no head, from=1-3, to=1-1]
\arrow[Rightarrow, no head, from=1-3, to=1-5]
\arrow["{\eta_X}"{description}, from=1-3, to=3-3]
\end{tikzcd}\]

where $\id_X$ denotes the identity cospan $X=X=X$ on $X$.
Note that because $\int\underline{F_1}(\mathsf{id}_X)$ is defined over the identity span, $\tilde{F_0}(\id_X) \cong F_0X$, and so $\pi_X$ simply forgets the factor decorations.
Moreover, this means that all components of morphisms of interfaces in $\tilde{F_0}(\id_X)$ are comonoid homomorphisms in $\Ca$.

We define $\eta_X$ using the counits of the comonoid structures on the interfaces on $X$.
That is to say, $\eta_X$ maps an interface $\chi:\disc X \to \Comon(\Ca)$ to the pair $(\chi, \epsilon_\chi)$, where here $\epsilon_\chi$ denotes the canonical discarding map $\chi^\otimes \to I$.
The functoriality of $\eta_X$ follows from the fact that all morphisms in $F_0X$ are comonoid homomorphisms, so if $\varphi$ is a morphism $\chi \to \chi'$ then $\epsilon_\chi = \varphi^*\epsilon_{\chi'}$.
Pseudo naturality of $\eta$ obtains likewise, and its unitality with respect to $\mu$ follows from the counitality of the comonoid counits.

At this final point, we should also validate the remaining laws that a lax double functor should satisfy: in particular, the associativity of $\mu$.
However, we shall at this point simply assert that associativity follows from the associativity of $\otimes$, the coassociativity of the relevant comonoid structures, and the universal properties of the (co)limits involved in the constructions, leaving a detailed examination of this claim to future exposition.

§.§ Graphical calculus

The relationship between decorated cospans and undirected wiring diagram algebras indicates that factor graphs should be understood as composing `operadically' (multicategorically): that is to say, by nesting; thus, within each factor of a factor graph may be hiding a whole other factor graph.
This formalizes the situation sometimes encountered in the literature — e.g. [Fig.20]Koudahl2023Realising — in which a collection of factors is grouped into a composite factor, sometimes depicted by drawing an extra box around the collection.

To hew more closely to existing undirected wiring diagrams, as well as the standard string diagrams for monoidal categories, we will adopt a syntax in which factors are depicted with circular boxes, exposed variables by emanating wires, and transformation morphisms by rectangular boxes.
We will depict comonoid homomorphisms as `diamond' shaped boxes, both to indicate that they commute with horizontal composition $\diamond$ and also to suggest that they can pierce through the bubble enclosing a factor; this means we will attach wires to their corners.
Conversely, we will depict arbitrary morphisms with standard rectangular boxes, attaching wires to their sides.

\[\scalebox{0.8}{\tikzfig{img/fg-eg-1}}\]

A composite factor $f'$.

Figure <ref> shows a simple example of a composite factor $f'$, constituted by another factor $f$ with three exposed variables, two of which are composed with transformations, one deterministic ($\varphi$) and one not ($\psi$).
Thinking statistically, we can interpret exposed variables (dangling wires) as representing observed random variables.
We can draw a bubble around the whole of Figure <ref> to obtain a new factor with three unobserved variables; nonetheless these variables are observable, which we depict by terminating them with a black dot.
As a horizontal 1-cell in $\FG$, the resulting factor has the type $f_0:0\nrightarrow 0$, where $0$ denotes the empty set.

\[\scalebox{0.8}{\tikzfig{img/fg-eg-2}}\]

The drawing of the bubble represents a 2-cell $f_0\Rightarrow f'$.
We can think of this 2-cell, being directed from $f_0$ to $f'$, as "reaching into $f_0$", pulling observable wires out to expose them as the wires of $f'$.

We can compose $f$ with some factor $g$ (with a compatible interface), repurposing the black dot — or spider, in the terminology of Coecke2016Categorical — to represent the locus of composition:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-3}}\]

(In this way, we can think of a one-legged spider, representing an observable variable, as a locus of potential composition.)

We can reach inside $g\diamond f'$ to expose the internal wire:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-4}}\]

And this gives us another way to understand the deterministic morphisms: as those that can slide past spiders, multiplying on the way into factors.
For example, suppose have another composite factor $h'$ involving $\varphi$, such as this:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-5}}\]

Then we could compose along $\varphi$ with $f'$ to obtain $h'\diamond f'$:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-6}}\]

Notice that here we have made use of the ability (but not necessity!) of copy-composition to couple multiple variables together.

If again we expose the composed variable, we can pull $\varphi$ outside, too:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-7}}\]

Notice that, by using spiders, there would be no ambiguity if we omitted the outer bubble: observed variables are those that are not terminated in a one-legged spider; and deterministic transformations “push forward” from exposed variables to multiply through spiders in the direction of their target factors.

We can use non-deterministic morphisms to render observable variables unobservable, by `marginalizing' them out.
For instance, here we have marginalized out one of the observed variables of $h'$ by transforming it with a state $\nu$:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-8}}\]

Here, we have used the standard string-diagrammatic representation of a state in $\Ca$.

Finally, let us depict the factor graph of Figure <ref> in this language:

\[\scalebox{0.8}{\tikzfig{img/fg-eg-9}}\]

Note how similar this depiction is to the non-compositional form of Figure <ref>: the major change is the replacement of `variable' nodes with (labelled) two-legged spiders, making the distinction between observed and observable variables.
Beyond this distinction, the syntax of $\FG$ tells us precisely what kinds of compositions are allowed — including supplying notions of transformation of factors.