Interpreting Dynamical Systems as Bayesian Reasoners

Nathaniel Virgo10000-0001-8598-590X Martin Biehl20000-0002-1670-6855 Simon McGregor3

N. Virgo et al.

$^{1}$Earth-Life Science Institute, Tokyo Institute of Technology, Tokyo 152-8550, Japan

$^{2}$Araya Inc., Tokyo 107-6024, Japan

$^{3}$University of Sussex, Falmer, UK

A central concept in active inference is that the internal states of a physical
system parametrise probability measures over states of the external world. These
can be seen as an agent's beliefs, expressed as a Bayesian prior or posterior. Here we begin
the development of a general theory that would tell us when it is appropriate to
interpret states as representing beliefs in this way. We focus on the case
in which a system can be interpreted as performing either
Bayesian filtering or Bayesian inference. We provide formal definitions of what
it means for such an interpretation to exist, using techniques from category theory.

§ INTRODUCTION

A question of current interest is what does it mean for a physical system to be an agent?

That is, given a physical system that interacts with an environment, when does it make sense to say that the system is learning about its environment or trying to achieve a goal, rather than merely being dynamically coupled to its environment?

Here we confine ourselves to the first of these, in a simple form:
given a physical system that is influenced by its surroundings, under what circumstances can it be said to be performing inference, such that its internal states could be said to contain `knowledge' or `beliefs' about the outside world?

Our approach has something in common with Dennet's intentional stance <cit.>, in that on the one hand we treat the question of whether a system is performing inference as a matter of interpretation, but on the other hand we draw a strong connection between interpretations and the underlying physical dynamics.

We provide a formal notion of interpretation for the particular cases we are interested in (Bayesian filtering and Bayesian inference), such that the question of whether a system can be consistently interpreted in a particular way is mathematically well-defined and has a definite answer.

The question of how to identify agents in physical systems has been addressed in several ways.

Some works focus on whether a system's actions can be seen as pursuing a goal <cit.>, with <cit.> taking an explicitly Dennettian approach.

Others focus more on the question of identifying which part of a system should be identified as the agent <cit.>, or on understanding what the external world looks like from the agent's point of view <cit.>.

Another approach, which we take here, is to regard the system's internal state as parametrising its beliefs.

That is, there is a function mapping the system's physical state to a probability measure that can be seen as a Bayesian prior.

This is a key component of work on the Free Energy Principle (FEP) <cit.> and also of <cit.>, although our approach differs from these in that our model is not derived from the dynamics of the true environment.

The notion that agency is closely related to parametrisation is also central to recent approaches to agency based on category theory <cit.>.

The idea that states of a system parametrise Bayesian probability distributions appears more broadly in the Bayesian brain literature <cit.> and has also arisen in cell biology <cit.>.

Our contribution is to make the concept much more formal, and in so doing, to shed light on the precise relationship between the interpretation level and the underlying physical level.

On a technical level we formulate the problem of Bayesian filtering at an abstract level using the tools of category theory.

This part of the work is inspired by
<cit.>, which formulates the notion of conjugate prior in terms of category theory in a similar way.

Conjugate priors are convenient because they ensure the functional form of the posterior is the same as the posterior, in Bayesian belief updating.

At the same time they can be seen as a special case of Bayesian filtering, as we explain in <ref> and <ref>.

Formulating filtering in this way allows us to clearly distinguish the role of the physical machine from the more semantic level at which we can talk about priors and posteriors.

We then
flip this perspective around, asking, for a given system, whether it can be interpreted as implementing Bayesian filtering, and if so under which model.

In this respect our approach generalises that of <cit.>, who studied the special case of the Dirichlet distribution (which is conjugate prior to a categorical distribution) in the context of interpreting a physical system as performing inference.

One thing our approach makes clear is that a given system may have more than one interpretation, and the “correct” interpretation cannot be determined from the system's dynamics alone.

Another important aspect of our framework is that an interpretation only depends on the system's internal dynamics, and not on the dynamics of the external world.

Because of this, a system's presumed beliefs might not match the true dynamics of the world at all — its beliefs might be consistent but incorrect — and indeed we can construct examples where the world “as the system sees it” has a different causal structure from the world as it really is. (Compare <ref> to <ref>.)

§ DEFINITIONS AND RESULTS

§.§ Technical preliminaries

In the following, we use the concepts of measurable space and Markov kernel.

By measurable space we mean a set equipped with a $\sigma$-algebra, i.e. the kind of thing on which a probability measure can be defined.

An example of a measurable space is a finite set, and a reader who is only interested in the finite case could mentally substitute “finite set” wherever we say “measurable space” and “probability distribution” wherever we say “probability measure.”

Given a measurable space $X$, we write $P(X)$ for the set of all probability measures over $X$.

Given measurable spaces $X$ and $Y$, a Markov kernel is a function $\kappa\colon X\to P(Y)$ that maps elements of $X$ to probability measures over $Y$, with an additional technical requirement that the function $\kappa$ be measurable.

Markov kernels are closely related to conditional probability, but they are different in that a Markov kernel defines a probability measure over $Y$ for every element $X$, regardless of whether any probability distribution has been defined over $X$ or what form such a distribution has.

In the case where $Y$ is a finite set, we write $\kappa(y\mg x)$ for the probability that the kernel $\kappa$ assigns to $y$ when given the input $x$.

We also make use of a graphical notation known as string diagrams, which comes from the literature on category-theoretic probability <cit.>.

This notation provides a convenient way to reason about how Markov kernels relate to one another.

The full technical description of this calculus can be found in <cit.> or <cit.>, but we provide a brief intuitive explanation in <ref>, aimed at readers with no category theory background, along with references to further reading.

§.§ Machines and interpretations

We are concerned with interpreting a physical system as performing inferences of some kind on its inputs.

We therefore begin by defining a notion corresponding to a physical system that can take an input from the outside world, which leads to a change in state, which might be stochastic and might depend on the input.

A machine consists of two measurable spaces, $Y$ (the state space) and $S$ (the input space), together with a Markov kernel $\gamma\colon Y\times S \to P(Y)$ called the update kernel.

The idea is that the machine is in reality only a part of some larger stochastic process.

We might typically think of this broader context as represented by the following causal Bayesian network, although this is not the only possibility.

\begin{equation}
\label{bayesian-network-context}
\raisebox{-0.5\height}{\includegraphics[height=5.5em]{figures/bayesian_network_context.png}}
\end{equation}

Here the variables $X_0,X_1,\dots$ represent the states of the external world at different times, which are hidden from the machine's perspective. $S_0,S_1,\dots$ are the observable “sensor values” that the machine can access, all of which have the same sample space, given by $S$. Similarly, $Y_0,Y_1,\dots$ are the machine's internal state at each time step and each has the sample space $Y$.

We assume that each of the nodes $Y_1,Y_2,\dots$ in this network are associated with the same kernel, $\gamma$.

The nodes $X_0$ and $Y_0$ represent distributions over initial states of the agent and the world.

A common ancestor of these nodes could be added, to represent the possibility that the initial states are correlated.

There is no need for any stationarity assumption in our framework; the initial distribution in <ref> can be arbitrary.

Even though we might think of the machine as existing in a context along these lines, our notion of interpretation does not depend on the machine's external environment at all, but only on the machine's internal dynamics.

That is, on the measurable spaces $Y$ and $S$ and on the update kernel $\gamma$.

This is because, informally speaking, a reasoner may have consistent but wrong beliefs about the external world, and we wish to include this possibility in our framework.

(In particular, a system that reasons correctly in one environment might be placed in a different environment where the same inferences are no longer correct.)

Our notion of interpretation will include a notion of “beliefs” about the external world.

These must be consistent with the machine's internal dynamics and the inputs it receives, but they need not relate in any particular way to any ground truth about the process by which those inputs are generated, since we regard that as something the reasoner has no direct access to.

Because of this we will rarely reason about causal models directly, and instead will express our definitions directly in terms of Markov kernels and the relationships between them.

The string diagram notation, explained <ref>, will be indispensable for this.

We now describe our central concept: an interpretation of a machine.

Here we will present only two kinds of interpretations, Bayesian filtering interpretations and an important special case, Bayesian inference interpretations, but we expect these to fit naturally into a much broader family of concepts.

The most important component of an interpretation is what we term an interpretation map, a function that maps the physical state of a machine to something that we can think of as a belief about some external world.

In the cases we are concerned with in this paper, a “belief” will be a probability measure over some hidden variable.

An interpretation of a machine will be an interpretation map together with some additional data (the model as defined below), such that a consistency equation is obeyed.

For a given machine there may be many possible interpretations.

We use the term reasoner for a machine together with a particular choice of interpretation.

In the case of Bayesian inference interpretations and Bayesian filtering interpretations, in which `beliefs' are probability measures over a hidden variable, the interpretation map is a Markov kernel $\psi_H\colon Y\to P(H)$.

Instead of interpreting this stochastically, we think of it as a function that takes a state $y\in Y$ and returns a probability measure $\psi_H(y)$ (the belief) over $H$.

This is to be thought of as the reasoner's subjective knowledge (a Bayesian prior or posterior) about the hypotheses in $H$.

This kernel plays quite a different role from those associated with the graphical model in <ref>, since its purpose is to map states to beliefs, rather than to model causal influences between random variables.

For an interpretation to be consistent, the reasoner's beliefs must update in the appropriate way when the machine receives new data.

The precise meaning of this will depend on what kind of interpretation we are using.

For the interpretations we describe here it is given by Bayes' rule, in a form that we state precisely below.

In future work we can imagine interpretations based on other principles, such as approximate Bayes (e.g. via the free energy principle).

The idea is that a machine by itself is merely a (possibly stochastic) dynamical process, but if a consistent interpretation exists then it is at least consistent to ascribe a meaning to its states.

It should be noted that, for a given machine, the question of whether it can be consistently interpreted in a particular way is in principle an empirical one, since it depends on the machine's update kernel, which can in principle be measured.

However, in general a given machine might have multiple non-equivalent consistent interpretations, and one cannot distinguish between these empirically by looking only at the system's internal dynamics.
[We leave open the possibility that they could be distinguished by looking at some broader context, e.g. by discovering that a device's designer intended a particular interpretation, or that evolution selected for a particular interpretation.]

Consequently the relationship between interpretations and the empirical, physical world is rather subtle, and one should keep in mind that our notion of “consistent reasoner” unavoidably involves an element of choice in which interpretation to adopt.

§.§ Consistency for Bayesian Interpretations

We begin with the more general case of Bayesian filtering interpretations.

The idea is that a reasoner has a model of the environment's dynamics.

This model is part of the interpretation, and need not match the true environment dynamics.

In the case of filtering, such a model can be described as a Markov kernel $\!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H};
\llabel{-4,-1}{ H};
that is, $\kappa\colon H\to P(H\times S)$.

The idea is that $H$ is the space of possible hidden states of the external world, as modelled by the reasoner.

The kernel $\kappa$ models a step of this hypothetical external world's evolution, during which it both changes to a new state in $H$ and also emits an observable sensor value in $S$.

A Bayesian filtering interpretation of a machine $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};
}$ will then consist of a choice of interpretation map $\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H\!$}{2}
\llabel{0,1}{Y};
\rlabel{4,1}{H};
}$ as described above, together with a choice of model $\!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H};
\llabel{-4,-1}{ H};

The kernel $\kappa$ thus describes a reasoner's beliefs about the next hidden state and the next sensor value, given the current hidden state.

Given the kernels $\psi_H$ and $\kappa$ we can define another kernel, which we also consider to be an interpretation map,

\begin{equation}
\label{filtering-big-interpretation-map}
\pbox{
\stringdiagram{
\llabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2.5,0}{$\psi_{S,H\sprime,H}$}{6};
\wire(2,1.5) -- (5,1.5);
\wire(2,0) -- (5,0);
\wire(2,-1.5) -- (5,-1.5);
\rlabel{5,1.5}{H};
\rlabel{5,0}{H};
\rlabel{5,-1.5}{S};
\,\coloneqq
\stringdiagram{
\ulabel{0.3,0}{H};
\wire(-4,0) -- (2,0);
\llabel{-4,0}{Y};
\stoch{2,0}{$\kappa$}{4};
\stoch{-2,0}{$\psi_H$}{3};
\blackdot{-0.5,0};
\wire[3] (-0.5,0) -- (-0.5,3) -- (4,3);
\wire(2,1) -- (4,1);
\wire(2,-1) -- (4,-1);
\rlabel{4,3}{H};
\rlabel{4,1}{H};
\rlabel{4,-1}{S};
\end{equation}

The kernel $\psi_{H,H',S}$ maps a state of the machine $y\in Y$ to a joint distribution over $S$ and two copies of $H$, which we think of as the reasoner's beliefs about the the next sensor value, the next hidden state, and the current hidden state.

We also define its marginals,

\begin{equation}
\label{filtering-interpretation-SH'}
\pbox{
\stringdiagram{
\llabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2.5,0}{$\psi_{S,H'}$}{4};
\wire(2,0.7) -- (4.7,0.7);
\wire(2,-0.7) -- (4.7,-0.7);
\rlabel{4.7,0.7}{H};
\rlabel{4.7,-0.7}{S};
\,\,\coloneqq
\stringdiagram{
\llabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2.5,0}{$\psi_{S,H\sprime,H}$}{4};
\wire(2,1) -- (4.8,1);
\blackdot{4.8,1}
\wire(2,0) -- (5,0);
\wire(2,-1) -- (5,-1);
\rlabel{5,0}{H};
\rlabel{5,-1}{S};
\,\,=
\stringdiagram{
\ulabel{0.3,0}{H};
\wire(-3,0) -- (2,0);
\llabel{-3,0}{Y};
\stoch{2,0}{$\kappa$}{4};
\stoch{-1.2,0}{$\psi_H$}{3};
\wire(2,1) -- (4,1);
\wire(2,-1) -- (4,-1);
\rlabel{4,1}{H};
\rlabel{4,-1}{S};
\end{equation}

\begin{equation}
\label{filtering-interpretation-S}
\pbox{
\stringdiagram{
\llabel{0.5,0}{Y};
\wire(0.5,0) -- (4.7,0);
\stoch{2.5,0}{$\psi_{S}$}{3};
\rlabel{4.7,0}{S};
\,\,\coloneqq
\stringdiagram{
\llabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2.5,0}{$\psi_{S,H\sprime,H}$}{4};
\wire(2,1) -- (4.8,1);
\blackdot{4.8,1}
\wire(2,0) -- (4.8,0);
\blackdot{4.8,0}
\wire(2,-1) -- (5,-1);
\rlabel{5,-1}{S};
\,\,=
\stringdiagram{
\ulabel{0.3,0}{H};
\wire(-3,0) -- (2,0);
\llabel{-3,0}{Y};
\stoch{2,0}{$\kappa$}{4};
\stoch{-1.2,0}{$\psi_H$}{3};
\wire(2,1) -- (3.75,1);
\blackdot{3.75,1};
\wire(2,-1) -- (4,-1);
% \rlabel{4,1}{H};
\rlabel{4,-1}{S};
\end{equation}

which represent the reasoner's beliefs about the next hidden state and the next input, and about only the next input, respectively.

We can now state the consistency requirement for a Bayesian filtering interpretation.

Given a machine $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};
},$ a consistent Bayesian filtering interpretation of $\gamma$ is given by a measurable space $H$ together with Markov kernels $\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H\!$}{2}
\llabel{0,1}{Y};
\rlabel{4,1}{H};
}$ and $\!\!\stringdiagram{
\wire (0,1)--(2,1);
\wire (2,0)--(4,0);
\wire (2,2)--(4,2);
\stoch{2,1}{$\kappa$}{2.5}
\llabel{0,1}{H};
\rlabel{4,2}{H};
\rlabel{4,0}{S};
}$ that satisfy

\begin{equation}
\label{bayesian-filtering-consistency}
\stringdiagram {
\wire (0,0) -- (11.5,0);
\ulabel{0,0}{Y};
\ulabel{11.5,0}{Y};
\blackdot{1,0};
\wire[3] (1,0) -- (1,3) -- (5,3);
\wire (5,2) -- (11.5,2);
\ulabel{11.5,2}{S};
\stoch{4.5,3}{$\psi_{S,H'}$}{4};
\stoch{9.5,0.25}{$\gamma$}{3};
\blackdot{7.5,2};
\ulabel{8,2}{S};
\wire[1.5] (7.5,2) -- (7.5,0.5) -- (9.5,0.5);
\wire[2] (5,4) -- (11.5,4);
\ulabel{11.5,4}{H};
\,\, =
\pbox{
\stringdiagram {
\wire (2,0) -- (15,0);
\ulabel{2,0}{Y};
\ulabel{15,0}{Y};
\blackdot{3,0};
\wire[2] (3,0) -- (3,2) -- (6,2);
\stoch{5.25,2}{$\psi_{S}$}{3};
\wire (6,2) -- (15,2);
\ulabel{15,2}{S};
\stoch{9,0.25}{$\gamma$}{3};
\blackdot{7,2};
\ulabel{7.4,2}{S};
\wire[1.5] (7,2) -- (7,0.5) -- (9,0.5);
\wire[4] (10.5,0) -- (10.5,4) -- (15,4);
\blackdot{10.5,0};
\ulabel{11.3,0}{Y};
\stoch{13.2,4}{$\psi_{H}$}{3};
\ulabel{15,4}{H};
% \showgrid
%\stringdiagram {
% \wire (0,0) -- (15,0);
% \ulabel{0,0}{Y};
% \ulabel{15,0}{Y};
% \blackdot{1,0};
% \wire[3] (1,0) -- (1,3) -- (5,3);
% \wire (5,2) -- (11.5,2);
% \stoch{4.5,3}{$\psi_{S,H'}$}{4};
% \wire (6,2) -- (15,2);
% \ulabel{15,2}{S};
% \wire[2] (5,4) -- (8,4);
% \ulabel{7.4,4}{H};
% \blackdot{8,4};
% \stoch{9,0.25}{$\gamma$}{3};
% \blackdot{7,2};
% \ulabel{7.4,2}{S};
% \wire[1.5] (7,2) -- (7,0.5) -- (9,0.5);
% \wire[4] (10.5,0) -- (10.5,4) -- (15,4);
% \blackdot{10.5,0};
% \ulabel{11.3,0}{Y};
% \stoch{13.2,4}{$\psi_{H}$}{3};
% \ulabel{15,4}{H};
%% \showgrid
\end{equation}

with $\psi_{S,H'}$ and $\psi_S$ given by <ref>.

The left-hand-side of <ref> can be read as sampling from the reasoner's joint beliefs about the next hidden state and the next input, and then feeding the corresponding value of $S$ into the machine as an input.

The right-hand-side can be read as sampling from the reasoner's belief about its next input, feeding the result in as its next input, and then sampling from its resulting (posterior) belief about what it now sees as the current hidden state.

The equation says that these two procedures must give the same result.

In <ref> we give some further intuition for this definition, by considering the case where $S$, $Y$ and $H$ are finite sets.

An important consequence is that, in the finite case, whether a given interpretation is consistent or not only depends on which states are reachable from which other states under a given input; the actual transition probabilities are irrelevant beyond that.

We expect an analogous statement to hold more generally.

Another important consequence discussed in <ref> is that there is a large class of machines that only admit trivial interpretations.

At least in the finite case, non-trivial interpretations can only exist if some transitions are impossible, in the sense that there is a zero probability of transitioning from $y\in Y$ to $y'\in Y$ under the input $s\in S$.

In <ref> we give a more technical proof, using string diagrams, that at least in the case of deterministic machines, a machine with a consistent Bayesian filtering interpretation can indeed be regarded as performing a Bayesian filtering task.

This can be seen as extending some of the ideas in <cit.> on conjugate priors to the more general case of Bayesian filtering.

An important special case of <ref> is where the model $\kappa$ is such that the hidden state does not change over time.

In this case $H$ can be thought of as an unknown parameter of a statistical model, with the sensor inputs being independent and identically distributed samples from the model.

We call these Bayesian inference interpretations.

Although the following follows from <ref> under this assumption, we write it as a separate definition.

Given a machine $\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};
},$ a consistent Bayesian inference interpretation of $\gamma$ is given by a measurable space $H$ together with Markov kernels $\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H\!$}{2}
\llabel{0,1}{Y};
\rlabel{4,1}{H};
}$ and $\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\phi$}{2}
\llabel{0,1}{H};
\rlabel{4,1}{S};
}$ that satisfy

\begin{equation}
\label{bayesian-inference-consistency}
\stringdiagram {
\wire (0,0) -- (11.5,0);
\ulabel{0,0}{Y};
\ulabel{11.5,0}{Y};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (11.5,2);
\ulabel{11.5,2}{S};
\stoch{3,2}{$\psi_H\!$}{3};
\stoch{6,2}{$\phi$}{3};
\blackdot{4.5,2};
\ddlabel{4.5,2}{H};
\stoch{9.5,0.25}{$\gamma$}{3};
\blackdot{7.5,2};
\ulabel{8,2}{S};
\wire[1.5] (7.5,2) -- (7.5,0.5) -- (9.5,0.5);
\wire[2] (4.5,2) -- (4.5,4) -- (11.5,4);
\ulabel{11.5,4}{H};
% \showgrid
\, = \!
\pbox{
\stringdiagram {
\wire (0,0) -- (15,0);
\ulabel{0,0}{Y};
\ulabel{15,0}{Y};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (15,2);
\ulabel{15,2}{S};
\stoch{3,2}{$\psi_H\!$}{3};
\ulabel{4.25,2}{H};
\stoch{5.5,2}{$\phi$}{3};
\stoch{9,0.25}{$\gamma$}{3};
\blackdot{7,2};
\ulabel{7.5,2}{S};
\wire[1.5] (7,2) -- (7,0.5) -- (9,0.5);
\wire[4] (10.5,0) -- (10.5,4) -- (15,4);
\blackdot{10.5,0};
\ulabel{11.3,0}{Y};
\stoch{13.2,4}{$\psi_H\!$}{3};
\ulabel{15,4}{H};
% \showgrid
\end{equation}

In <ref> we show that this definition is closely related to the notion of a conjugate prior, and in particular to the definition of conjugate prior given by <cit.> in terms of Markov kernels and string diagrams.

Finally, in <ref> we unpack <ref> in more familiar terms, showing that in the discrete case it does indeed correspond to Bayes' theorem as usually understood.

In a Bayesian inference interpretation we interpret the reasoner as
assuming its inputs are i.i.d. samples from some distribution, but this need not mean that they actually are.

Under a consistent Bayesian inference interpretation a reasoner is interpreted as modelling the world as if its causal structure is as follows, where each of the `$S$' nodes is associated with the kernel $\phi$.

\begin{equation}
\raisebox{-0.5\height}{\includegraphics[height=5.5em]{figures/bayesian-network-iid.png}}
\label{bayesian-network-iid}
\end{equation}

However, the true dynamics of the world could still correspond to the Bayesian network in <ref> or some other causal structure.

The reasoner is simply (interpreted as being) unable to perceive the correlations among its inputs.

In <ref> we present three examples of machines with consistent Bayesian inference interpretations.

The first example is a non-deterministic finite machine with three states.

The consistent Bayesian inference interpretation we provide also involves subjectively impossible observations.

The second example is a countably infinite deterministic machine that counts occurrences of each of two possible observations.

The consistent Bayesian interpretation we provide intuitively considers this machine to be inferring the bias of a coin that is flipped to cause its observations.

It uses the standard conjugate prior to its model as an interpretation map.

The third example is also a countably infinite machine with two possible observations.

However, it only stores the difference between the number of the two possible observations.

Intuitively, instead of considering all possible biases of a coin as the second example the consistent Bayesian interpretation we provide for this machine infers which of two specific biases of a coin is causing its observations.

We also hint at how the second machine can “inherit” this interpretation.

§ DISCUSSION

We see the main contribution of this work as a conceptual one.

The consistency equation involved in <ref>

can be seen either as a constraint on the machines that have a particular interpretation or as a constraint on the interpretations that a particular machine allows.

Every machine has an interpretation with respect to a trivial model (one that has no parameter), but in order to have an interpretation with respect to a non-trivial model, a machine must at least obey the constraints discussed in <ref>.

Similar consistency equations should exist for approximate Bayesian filtering as well as for related inference problems like Bayesian smoothing or prediction.

Even non-Bayesian normative theories about what a system should be representing and how this should change under external influences will probably have associated consistency equations.

Another direction to extend the concept of consistency equations is to take into account a possible influence of the machine's state on the external world.

On the interpretation side this would mean going beyond perception and representation to also include deliberate actions that combine with beliefs and possibly also with goals.

A machine with such an interpretation might deserve the term agent instead of reasoner.

Our work is related to other current efforts to capture the notion of agent using category theory.

These include approaches to Bayesian inference <cit.> and game theory <cit.>.

The idea that agency is related to parametrisation has also arisen in these contexts <cit.>.

These works focus on the notion of a lens and its generalisations.

It is interesting to note that our notions of interpretation seem to be different, and somewhat simpler, in that they lack the bidirectional nature of lenses.

We conjecture that a more lens-like bidirectional structure would be needed if we were to consider Bayesian smoothing rather than Bayesian filtering.

It will be interesting in future work to better understand the relationship between lens-like categories and the concept of interpretation developed in the present work.

§.§ Relation to the Free Energy Principle

Let us now consider the relation to the Free Energy Principle (FEP) which is also referred to as active inference.

The relevant part of FEP is the part called “Bayesian mechanics” <cit.>.

It seems that the ingredients for an interpretation map can be found in this literature:
<cit.> describes a Markov kernel of an appropriate type, as we detail in <ref>.

However, it is not currently clear to us whether the FEP can be formulated in terms of a consistency equation that this kernel obeys.

Presumably, such an equation would be different from our <ref>, because the FEP is concerned with approximate rather than exact inference and deals with continuous time.

One important difference between our approach and current formulations of FEP is that the FEP requires a stationarity assumption on the true dynamics of the agent-environment system.

It seems to us that this is used to derive something that corresponds to a model.

In our approach the reasoner's and the “ground truth” dynamics of the environment are different things, and partly for this reason we need no stationarity assumption.

We see this conceptual separation as an advantage of the consistency equation approach, and we believe that by incorporating these ideas it might be possible to formulate the FEP in a way that would make its assumptions clearer and perhaps even avoid the need for the stationarity assumption.

Although we do not currently know the precise relationship between our work and the FEP at a technical level, we explore it in more detail in <ref>.

§ CATEGORY-THEORETIC PROBABILITY AND STRING DIAGRAMS

In this paper we use some concepts from category-theoretic probability, and in particular we use a notation known as string diagrams.

A full introduction to these topics would be out of scope of the paper, but we include here an informal introduction to the topic.

We do this because, to our knowledge, no concise introduction currently exists that is focused on (classical) probability and does not assume a background in category theory.

We assume that the reader knows the definition of a category, but not much more than that.

<Ref> introduces the basic concepts, mostly in the context of discrete probability.

In <ref> we briefly comment on how this extends to the general case of measure-theoretic probability with very little extra work.

In <ref> we explain how to reason about conditional probabilities and Bayes' theorem within this category-theoretic context.

These sections contain no original material.

Their purpose is to give the reader enough information to be able to read the string diagram equations in the main text and later sections of the appendix without needing to consult a category theory text.

However, they are intended neither as an authoritative technical reference nor as a comprehensive review, and readers should consult the cited references for full details.

§.§ Introduction to String Diagrams and Category-Theoretic Probability

A full technical introduction to the use of string diagrams in probability can be found in <cit.> or the earlier <cit.>, but these works require some knowledge of category theory.

The string diagram notation predates its use in probability and has many other applications.

One could consult <cit.> for tutorial introductions to diagrammatic reasoning in other fields, of various different flavours.

Here we present it somewhat informally and only in the context of probability.

It should be kept in mind that, despite our somewhat informal introduction, string diagrams are formal expressions.

The main difference between them and the more familiar kind of mathematical expression formed from strings of symbols is their two-dimensional syntax.

This makes it easier to express certain concepts. (Particularly those relating to joint distributions, in the case of probability.)

We use the so-called Markov category approach to probability <cit.>.

The main idea here is to express everything in terms of measurable spaces and Markov kernels, whose definitions we outlined in the main text.
[In fact for most of the paper we will work much more abstractly than this. It would be more correct to say “objects in a Markov category” wherever we say “measurable space” and “morphisms in a Markov category” wherever we say “Markov kernel,” since for most of the paper we will reason at the category level, and we will not directly invoke the definition of a measurable space. We have chosen to use the more concrete terms because they express a clear intuition for how these objects and morphisms are intended to be interpreted.]

To explain how the framework works, let us consider the special case where the only measurable spaces we are interested in are finite sets (with their power sets as their $\sigma$-algebras).

If $A$ and $B$ are finite sets then a Markov kernel can be thought of as just a function $f\colon A\to P(B)$, where $P(B)$ is the set of all probability distributions over $B$.

(The set $P(B)$ may be thought of as a $(|B|-1)$-dimensional simplex, consisting of all those vectors in $\mathbb{R}^{|B|}$ whose components are all non-negative and sum to 1.)

Such a function amounts to a $|B|$-by-$|A|$ stochastic matrix, although some care needs to be taken over which rows correspond to which elements of $B$ and which columns to which elements of $A$.

In this finite case, we write $f(b\mg a)$ to denote the probability that the kernel $f$ assigns to the outcome $b\in B$ when given the input $a\in A$.

We use a thick vertical line to indicate a close relationship to conditional probability while also emphasising that the concept is different:
given a kernel $f\colon A\to P(B)$ the quantities $f(b\mg a)$ are always defined, regardless of whether any probability distribution has been defined over $A$, and regardless of whether $a$ has a nonzero probability according to such a distribution.

More common notations include $|$ or $;$ in place of $\mg$.

We also write $f(a)$ for the probability distribution over $B$ that the function $f$ returns when given the input $a$.

We could say that $f(b\mg a)$ is defined as $f(a)(b)$.

Given Markov kernels $f\colon A\to P(B)$ and $g\colon B\to P(C)$, we can compose them to form a new kernel of type $A\to P(C)$.

We write this $f\comp g$.

It is given by

\begin{equation}
\label{finite_kernel_composition}
(f\comp g)(c\mg a) = \sum_{b\in BY} f(b\mg a)\,g(c\mg b).
\end{equation}

In this finite case this is simply matrix multiplication, and we could have denoted it $gf$ instead of $f\comp g$ accordingly.

(Another common notation is $g\circ f$.)

We prefer $f\comp g$ because it puts $f$ and $g$ in the same order that they will appear in string diagrams.

It is straightforward to show that composition is associative, that is

\begin{equation}
\label{associativity-law}
(f\comp g)\comp h = f\comp (g\comp h).
\end{equation}

In addition, for every finite set $A$ there is an identity kernel, which amounts to just the $|A|$-by-$|A|$ identity matrix.

We write this as $\id_A$ and define it by $\id_A(a'\mg a) = \delta_{a,a'}$.

For every Markov kernel $f\colon A\to P(B)$ we have

\begin{equation}
\label{identity-law}
\id_A\comp f = f = f\comp \id_B.
\end{equation}

These two facts mean that there is a category whose objects are finite sets and whose morphisms are Markov kernels between finite sets.

This category is called $\mathsf{FinStoch}$.

Since Markov kernels are morphisms in a category, we will often write $f\colon A \todot B$ instead of $f\colon A\to P(B)$, using the dotted arrow $\todot$ to distinguish morphisms in $\mathsf{FinStoch}$ and related categories from ordinary functions.

(In the main text we continue writing them as functions in order to avoid introducing new notation.)

The composition of Markov kernels can be generalised to the case of measure-theoretic probability, which allows us to reason about continuous probability and more general probability measures using the same kinds of diagram and much of the same reasoning.

We briefly discuss this in more detail in <ref>.

The main difference is that composition becomes integration over measures rather than summation.

Probability measures themselves may be seen as a special case of Markov kernels.

Consider a set with a single element, denoted $\one = \{\star\}$.

(The identity of the element does not matter because all one-element sets are isomorphic to each other.

Category theorists often speak of “the one-element set” for this reason. We use a star to denote the element.)

Then a Markov kernel $p\colon \one\todot A$ is a function $p\colon \one\to P(A)$, which takes an element of $\one$ and returns a probability measure over $A$.

Since there is only one element of $\one$ this means that the kernel $p$ only defines a single probability measure over $A$.

We therefore think of Markov kernels $\one\todot A$ and probability measures over $A$ as essentially the same thing.

We now begin to introduce the string diagram notation.

A Markov kernel $f\colon A\todot B$ will be denoted

\begin{equation}
\pbox{
\stringdiagram {
\wire (0,0) -- (4,0);
\stoch{2,0}{$f$}{3};
\ulabel{0,0}{A};
\ulabel{4,0}{B};
\end{equation}

This expression means much the same thing as the notation $f\colon A \todot B$.

It is just a formal symbol denoting the kernel $f$, annotated with type information.

The composition of kernels $f\colon A\todot B$ and $g\colon B\todot C$ is written

\begin{equation}
\label{composition-string-diagram}
\pbox{
\stringdiagram {
\wire (0,0) -- (4,0);
\stoch{2,0}{$f\comp g$}{3};
\ulabel{0,0}{A};
\ulabel{4,0}{C};
\quad=\quad
\stringdiagram {
\wire (0,0) -- (7,0);
\stoch{2,0}{$f$}{3};
\ulabel{0,0}{A};
\ulabel{3.5,0}{B};
\stoch{5,0}{$g$}{3};
\ulabel{7,0}{C};
\end{equation}

The left and right hand side of this equation are just two different ways to write the composite kernel $f\comp g$, as defined by <ref> or its measure-theoretic generalisation.

In reading a diagram like the right-hand side of <ref> we find it helpful to imagine an element of $A$ travelling along the wire from the left.

As it passes through the kernel $f$ it is stochastically transformed into an element of $B$, in a way that might depend on its original value.

It then travels further to the right and is stochastically transformed by $g$ into an element of $C$.

<Ref> can be seen as describing this process.

In string diagrams a special notation is used for identity kernels (or identity morphisms more generally): an identity kernel $\id_A$ is drawn simply as a wire with no box on it,

\begin{equation}
\pbox{
\stringdiagram {
\wire (0,0) -- (4,0);
\ulabel{0,0}{A};
\end{equation}

For any Markov kernel $f\colon A\todot B$ the identity law <ref> can then be written

\begin{equation}
\begin{aligned}
\stringdiagram {
\wire (0,0) -- (4,0);
\stoch{2,0}{$f$}{3};
\ulabel{0,0}{A};
\ulabel{4,0}{B};
& \quad=\quad \stringdiagram {
\wire (-2,0) -- (4,0);
\stoch{2,0}{$f$}{3};
\ulabel{-2,0}{A};
\ulabel{4,0}{B};
} \\[1em]
\pbox{\stringdiagram {
\wire (0,0) -- (6,0);
\stoch{2,0}{$f$}{3};
\ulabel{0,0}{A};
\ulabel{6,0}{B};
\end{aligned}
\end{equation}

This allows us to think of the wires as stretchy: we can extend and contract them at will.

We will think of the wires as continuously deformable, rather than extending and contracting in discrete units.

This is justified by the formal theory of string diagrams.

(One may informally think of the wire itself as an infinite chain of identity kernels, all composed together.)

This ability to continuously deform diagrams turns out to be an extremely powerful and useful idea.

Another special notation is used for one-element sets[or in a more general context, the unit object of a monoidal category]:
they are drawn as no wire at all.

For this reason a probability measure over $A$, that is, a kernel $p\colon \one\todot A$, is drawn as

\begin{equation}
\pbox{
\stringdiagram {
\wire (2,0) -- (4,0);
\stoch{2,0}{$p$}{3};
\ulabel{4,0}{A};
\end{equation}

(Morphisms of this kind are sometimes known as “states,” and they are often drawn as a triangle rather than a box, though here we draw them in the same style as other morphisms.)

It is worth noting that the kernels $p$ and $f$ above can be composed, yielding

\begin{equation}
\pbox{
\stringdiagram {
\wire (2,0) -- (4,0);
\stoch{2,0}{$p\comp f$}{3};
\ulabel{4,0}{B};
\quad=\quad
\stringdiagram {
\wire (2,0) -- (7,0);
\stoch{2,0}{$p$}{3};
\ulabel{3.5,0}{A};
\stoch{5,0}{$f$}{3};
\ulabel{7,0}{B};
\end{equation}

Because of this, although the kernel $f\colon A\todot B$ is defined as a function $f\colon A\to P(B)$ mapping elements of $A$ to probability distributions over $B$, we can instead choose to see it as mapping probability measures over $A$ to probability measures over $B$.

In the finite case, if we think of finite probability distributions as normalised and nonnegative vectors in $\mathbb{R}^{n}$, then $f$ can be seen as a linear map with the property that it maps points in one simplex to points in another.

(This justifies thinking of it as a stochastic matrix.)

The string diagram notation becomes useful when we start thinking about joint distributions.

We do this by drawing wires in parallel.

As an example, we can consider a Markov kernel defined by a function $h\colon A\times B \to P(C\times D)$.

This function takes two arguments, an element of $A$ and an element of $B$, and it returns a joint probability distribution over $C$ and $D$.

In string diagrams we write this as

\begin{equation}
\pbox{
\stringdiagram {
\wire (0,0) -- (4,0);
\wire (0,2) -- (4,2);
\stoch{2,1}{$h$}{4};
\ulabel{0,2}{B};
\ulabel{0,0}{A};
\ulabel{4,2}{D};
\ulabel{4,0}{C};
\end{equation}

In symbols, we write $h\colon A\otimes B \todot C\otimes D$.

An object like $A\otimes B$, drawn as two parallel wires, can either be thought of as the measurable space $A\times B$ (which is the Cartesian product of sets in the finite case), or as the space of probability measures over $A\times B$.

The symbol $\otimes$ is referred to as a monoidal product.

There is some inherent ambiguity in this notation.

If we draw three parallel wires,
\stringdiagram{
\wire (0,0) -- (3,0);
\wire (0,1.6) -- (3,1.6);
\wire (0,3.2) -- (3,3.2);
\llabel{0,0}{A};
\llabel{0,1.6}{B};
\llabel{0,3.2}{C};
it could either mean $(A\otimes B)\otimes C$ or $A\otimes (B\otimes C)$.

In the finite case, these correspond to the sets $(A\times B)\times C$ and $A\times (B\times C)$.

These are different sets, since one is composed of pairs $((a,b),c)$ and the other of pairs $(a,(b,c))$.

This ambiguity is not important in practice, however, and the formal machinery of monoidal categories allows us to use string diagrams without worrying about it.

We do not give a formal treatment of this here.

(A concise summary can be found in <cit.>.)

Instead we simply remark that when we draw three parallel wires we think of joint distributions over $A$, $B$ and $C$, and the precise distinction between $P(A\times (B\times C))$ and $P((A\times B)\times C)$ will not be important to us.

In a similar vein, the spaces $A$ and $A\otimes \one$ are different, but the difference is not important to us, and in fact they are written the same way in string diagrams.

This is because we draw $\one$ as an invisible wire.

This also allows us to write

\begin{equation}
\pbox{
\stringdiagram{
\wire (0,0) -- (4,0);
\wire (0,1) -- (4,1);
\llabel{0,-0.1}{A};
\llabel{0,1.1}{B};
\quad=\quad
\stringdiagram{
\wire (0,0) -- (4,0);
\wire (0,2.5) -- (4,2.5);
\llabel{0,0}{A};
\llabel{0,2.5}{B};
\quad=\quad
\stringdiagram{
\wire (0,0) -- (2,-1) -- (4,0);
\wire (0,1) -- (1,1) -- (3,2) -- (4,2);
\llabel{0,-0.1}{A};
\llabel{0,1.1}{B};
\end{equation}

That is, string diagrams are stretchy in the vertical direction as well as the horizontal one.

We can bend the wires, as long as we don't deform them so much that they point backwards, from right to left.

This also allows to write things like

\begin{equation}
\stringdiagram{
\wire (0,1) -- (2,1);
\ulabel{0,1}{$A$};

\wire (2,2) -- (4,2);
\ulabel{4,2}{$C$};

\wire (2,0) -- (4,0);
\ulabel{4,0}{$B$};

\stoch{2,1}{$f$}{4};
\end{equation}

for a kernel $f\colon A\todot B\otimes C$.

We can also draw morphisms (i.e. Markov kernels) in parallel with each other, for example,

\begin{equation}
\pbox{
\stringdiagram {
\wire (0,0) -- (4,0);
\wire (0,3) -- (4,3);
\stoch{2,0}{$f$}{3};
\stoch{2,3}{$g$}{3};
\ulabel{0,3}{C};
\ulabel{0,0}{A};
\ulabel{4,3}{D};
\ulabel{4,0}{B};
\end{equation}

We write this in symbols as $f\otimes g$, which is a morphism of type $A\otimes C \todot B\otimes D$.

In the finite case, it is given by

\begin{equation}
(f\otimes g)(b,d\mg a,c) = f(b\mg a) \, g(d\mg c).
\end{equation}

The probabilities $f(b\mg c)$ and $g(d\mg c)$ are multiplied together because the two Markov kernels are operating in parallel.

One can imagine an element of $A$ entering from the bottom left and being stochastically transformed by $f$ into an element of $B$, while in parallel, and independently, an element of $C$ enters from the top left and is stochastically transformed by $g$ into an element of $D$.

In general, in the finite case, $f\otimes g$ is given by the tensor product of the stochastic matrices that represent $f$ and $g$.

(This might give some intuition for the symbol $\otimes$.)

We can cross wires over each other.

(In category theory terms, the categories we are concerned with are symmetric monoidal categories.)

The diagram

\begin{equation}
\stringdiagram{
\wire (0,0) -- (1,0) -- (3,2) -- (4,2);
\wire (0,2) -- (1,2) -- (3,0) -- (4,0);
\llabel{0,0}{A};
\llabel{0,2}{B};
\rlabel{4,0}{B};
\rlabel{4,2}{A};
\end{equation}

can be seen as a Markov kernel $A\otimes B\todot B\otimes A$.

In the finite case it is defined by

\begin{equation}
\operatorname{swap}_{A,B}(b',a'\mg a,b) = \delta_{a,a'}\delta_{b,b'}.
\end{equation}

We have a number of equations that are standard in monoidal category theory, and allow us to freely slide boxes along wires and bend wires to cross over each other.

These can either be shown directly from the definitions above or (perhaps more usefully) deduced from the definition of a symmetric monoidal category.

Three such equations are as follows.

More details can be found in the references cited above.

\begin{align}
\stringdiagram{
\wire (0,0) -- (1,0) -- (3,2) -- (5,2) -- (7,0) -- (8,0);
\wire (0,2) -- (1,2) -- (3,0) -- (5,0) -- (7,2) -- (8,2);
\llabel{0,0}{A};
\llabel{0,2}{B};
\rlabel{8,0}{A};
\rlabel{8,2}{B};
\quad&=\quad
\stringdiagram{
\wire (0,0) -- (8,0);
\wire (0,2) -- (8,2);
\llabel{0,0}{A};
\llabel{0,2}{B};
\rlabel{8,0}{A};
\rlabel{8,2}{B};
\\[1em]
\stringdiagram {
\wire (0,0) -- (8,0);
\wire (0,2) -- (8,2);
\stoch{2.25,0}{$f$}{3};
\stoch{5.75,2}{$g$}{3};
\llabel{0,2}{C};
\llabel{0,0}{A};
\rlabel{8,2}{D};
\rlabel{8,0}{B};
\quad&=\quad
\stringdiagram {
\wire (0,0) -- (8,0);
\wire (0,2) -- (8,2);
\stoch{5.75,0}{$f$}{3};
\stoch{2.25,2}{$g$}{3};
\llabel{0,2}{C};
\llabel{0,0}{A};
\rlabel{8,2}{D};
\rlabel{8,0}{B};
\\[1em]
\stringdiagram {
\wire (0,2) -- (5,2) -- (7,0) -- (8,0);
\wire (0,0) -- (5,0) -- (7,2) -- (8,2);
\stoch{2.25,0}{$f$}{3};
\llabel{0,2}{C};
\llabel{0,0}{A};
\rlabel{8,2}{B};
\rlabel{8,0}{C};
\quad&=\quad
\stringdiagram {
\wire (0,0) -- (1,0) -- (3,2) -- (8,2);
\wire (0,2) -- (1,2) -- (3,0) -- (8,0);
\stoch{5.75,2}{$f$}{3};
\llabel{0,2}{C};
\llabel{0,0}{A};
\rlabel{8,2}{B};
\rlabel{8,0}{C};
\end{align}

So far, everything we have said about string diagrams applies to any symmetric monoidal category.

However, there are two additional things we can add that take us much closer to probability theory.

These are the ability to copy and to delete.

These operations, and their special properties, do not necessarily exist in other contexts, such as quantum mechanics.

This is a central point of <cit.>.

We will stick to the context of classical probability, however, so copying and deletion will always be possible in this paper.

We cover deletion first.

For every measurable space $A$ there is a unique kernel of type $A\to \one$, which we call $\del_A$.

In the finite case it is given by $\del_A(\star\mg a) = 1$ for all $a\in A$.

We can think of this as a $1\times |A|$ matrix (i.e. a row vector) whose entries are all 1.

This is the only possible $1\times |A|$ stochastic matrix.

In string diagrams we write such a deletion kernel as a black dot:

\begin{equation}
\pbox{
\stringdiagram{
\wire (0,0) -- (2,0);
\blackdot{2,0};
\llabel{0,0}{A};
\end{equation}

There is one such morphism for every measurable space, but we denote them all with the same kind of black dot.

These black dots have the property that

\begin{equation}
\label{naturality-of-delete}
\pbox{
\stringdiagram{
\wire (0,0) -- (4.5,0);
\stoch{2,0}{$f$}{3};
\ulabel{3.5,0}{B};
\blackdot{4.5,0};
\ulabel{0,0}{A};
\,\,=
\stringdiagram{
\wire (0,0) -- (2,0);
\blackdot{2,0};
\ulabel{0,0}{A};
\end{equation}

for every Markov kernel $f$. This says that if we take some input $A$, perform some stochastic operation $f$ on it and then delete the result, this is the same as simply deleting the input.[In category theory terms, this means that the set of all delete kernels collectively forms a natural transformation. (Specifically, it is a natural transformation from the identity functor to the functor that sends all objects to $\one$ and all morphisms to $\id_\one$.) For this reason this property of delete kernels is called “naturality.”]

The second special operation is copying.

For every measurable space $A$ there is a kernel $\cpy_A\colon A\to A\otimes A$, which we will describe shortly.

We write this also as a black dot, but this time with two output wires rather than one.

\begin{equation}
\pbox{
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (4,1);
\wire[1] (2,0) -- (2,-1) -- (4,-1);
\blackdot{2,0};
\llabel{0,0}{A};
\rlabel{4,1}{A};
\rlabel{4,-1}{A};
\end{equation}

Informally, this kernel takes an outcome $a\in A$ and copies it, producing a pair $(a,a)$ of identical values.

It's important to note that it copies values rather than distributions.

Its output does not consist of two independent and identically distributed elements of $A$ but rather two perfectly correlated elements of $A$ that always have the same value.

In the discrete case the copy map is defined as

\begin{equation}
\cpy_A(a'',a'\mg a) =
\begin{cases}
1 & \text{if $a''=a'=a$} \\
0 & \text{otherwise.}
\end{cases}
\end{equation}

In addition to <ref>, the copy and delete maps obey the following properties <cit.>:

\begin{equation}
\label{coassociativity}
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (4,1);
\wire[1] (2,0) -- (2,-1) -- (6,-1);
\blackdot{2,0};
\llabel{0,0}{A};
\blackdot{4,1};
\wire[1] (4,1) -- (4,0) -- (6,0);
\wire[1] (4,1) -- (4,2) -- (6,2);
\rlabel{6,-1}{A};
\rlabel{6,0}{A};
\rlabel{6,2}{A};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (6,1);
\wire[1] (2,0) -- (2,-1) -- (4,-1);
\blackdot{2,0};
\llabel{0,0}{A};
\blackdot{4,-1};
\wire[1] (4,-1) -- (4,0) -- (6,0);
\wire[1] (4,-1) -- (4,-2) -- (6,-2);
\rlabel{6,1}{A};
\rlabel{6,0}{A};
\rlabel{6,-2}{A};
\end{equation}

\begin{equation}
\label{cancellation}
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (3.5,1);
\wire[1] (2,0) -- (2,-1) -- (4,-1);
\blackdot{2,0};
\blackdot{3.5,1};
\llabel{0,0}{A};
\rlabel{4,-1}{A};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (4,0);
\llabel{0,0}{A};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,-1) -- (3.5,-1);
\wire[1] (2,0) -- (2,1) -- (4,1);
\blackdot{2,0};
\blackdot{3.5,-1};
\llabel{0,0}{A};
\rlabel{4,1}{A};
\end{equation}

\begin{equation}
\label{cocommutativity}
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (3,1);
\wire[0.75] (3,1) -- (3.5,1) -- (4.5,-1)--(5,-1);
\wire[1] (2,0) -- (2,-1) -- (3,-1);
\wire[0.75] (3,-1) -- (3.5,-1) -- (4.5,1)--(5,1);
\blackdot{2,0};
\llabel{0,0}{A};
\rlabel{5.3,1}{A};
\rlabel{5.3,-1}{A};
% \showgrid
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1] (2,0) -- (2,1) -- (4,1);
\wire[1] (2,0) -- (2,-1) -- (4,-1);
\blackdot{2,0};
\llabel{0,0}{A};
\rlabel{4,1}{A};
\rlabel{4,-1}{A};
\end{equation}

\begin{equation}
\label{delete-compatibility}
\stringdiagram{
\wire (0,0) -- (2,0);
\blackdot{2,0};
\llabel{0,0}{A\otimes B\quad\quad\,};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\blackdot{2,0};
\llabel{0,0}{A};
\wire (0,2) -- (2,2);
\blackdot{2,2};
\llabel{0,2}{B};
\end{equation}

\begin{equation}
\label{copy-compatibility}
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1.5] (2,0) -- (2,1.5) -- (4,1.5);
\wire[1.5] (2,0) -- (2,-1.5) -- (4,-1.5);
\blackdot{2,0};
\llabel{0,0}{A\otimes B\quad\quad\,};
\rlabel{4,1.5}{\quad\quad\,A\otimes B};
\rlabel{4,-1.5}{\quad\quad\,A\otimes B};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1.5] (2,0) -- (2.5,2) -- (4,2);
\wire[1.5] (2,0) -- (2.5,-2) -- (4,-2);
\blackdot{2,0};
\llabel{0,0}{A};
\rlabel{4,2}{A};
\rlabel{4,-2}{A};
\wire (0,1.5) -- (2,1.5);
\wire[1.5] (2,1.5) -- (2.5,3.5) -- (4,3.5);
\wire[1.5] (2,1.5) -- (2.5,-0.5) -- (4,-0.5);
\blackdot{2,1.5};
\llabel{0,1.5}{B};
\rlabel{4,3.5}{B};
\rlabel{4,-0.5}{B};
\end{equation}

<Ref> says that if we make multiple copies of something it doesn't matter which order we make them in.

<Ref> says that if we copy something and then delete one of the copies, that is the same as doing nothing to it.

<Ref> says that if we copy something and then swap the copies it makes no difference.

(Because the two copies are the same as each other.)

<Ref> are more technical.

They say that if we have elements of $A$ and $B$ we can delete or copy them as a single element of $A\otimes B$ or separately, as elements of $A$ and $B$, and these should give the same result.

These equations can be derived from the definitions we have given for the finite case.

They may also be derived in various more general measure-theoretic contexts <cit.>.

However, the approach of <cit.> is instead to treat them as axioms: any symmetric monoidal category with copy and delete maps that obey <ref> is called a Markov category.

One can do a surprising amount of reasoning about probability theory using these axioms alone, although there are also Markov categories that do not directly resemble the category of measurable spaces and Markov kernels that we have described.

There are various additional axioms that can to be added as well, which then allow more specific results to be proven.

(See <cit.> for the details.)

An important thing to note about the copy operator is that, in general,

\begin{equation}
\pbox{
\stringdiagram{
\wire (-2,0) -- (2,0);
\wire[1.5] (2,0) -- (2,1.5) -- (4,1.5);
\wire[1.5] (2,0) -- (2,-1.5) -- (4,-1.5);
\blackdot{2,0};
\ulabel{1.6,0}{B}
\llabel{-2,0}{A};
\stoch{0,0}{$f$}{3};
\rlabel{4,1.5}{B};
\rlabel{4,-1.5}{B};
\quad\ne\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1.5] (2,0) -- (2,1.5) -- (6,1.5);
\wire[1.5] (2,0) -- (2,-1.5) -- (6,-1.5);
\blackdot{2,0};
\ulabel{1.6,0}{A}
\llabel{0,0}{A};
\stoch{4.2,1.5}{$f$}{3};
\stoch{4.2,-1.5}{$f$}{3};
\rlabel{6,1.5}{B};
\rlabel{6,-1.5}{B};
\end{equation}

That is, copying the output of a kernel $f$ is not the same as copying its input and then applying two copies of the kernel to it.

Intuitively, this is because $f$ might be stochastic.

If we copy the output we end up with two perfectly correlated copies, whereas if we copy the input then the stochastic variations will be independent.

However, if the kernel is deterministic then copying its input is indeed the same as copying its output.

In fact, in the Markov category framework this is the definition of a deterministic Markov kernel: we say a kernel $h\colon A \to B$ is deterministic if

\begin{equation}
\label{determinism}
\pbox{
\stringdiagram{
\wire (-2,0) -- (2,0);
\wire[1.5] (2,0) -- (2,1.5) -- (4,1.5);
\wire[1.5] (2,0) -- (2,-1.5) -- (4,-1.5);
\blackdot{2,0};
\ulabel{1.6,0}{B}
\llabel{-2,0}{A};
\sqbox{0,0}{$h$}{3};
\rlabel{4,1.5}{B};
\rlabel{4,-1.5}{B};
\quad=\,\,\,
\stringdiagram{
\wire (0,0) -- (2,0);
\wire[1.5] (2,0) -- (2,1.5) -- (6,1.5);
\wire[1.5] (2,0) -- (2,-1.5) -- (6,-1.5);
\blackdot{2,0};
\ulabel{1.6,0}{A}
\llabel{0,0}{A};
\sqbox{4.2,1.5}{$h$}{3};
\sqbox{4.2,-1.5}{$h$}{3};
\rlabel{6,1.5}{B};
\rlabel{6,-1.5}{B};
\end{equation}

In this paper we use square boxes for kernels that are known to be deterministic, and boxes with rounded edges for general, possibly-stochastic kernels.

In the main text, we write Markov kernels as functions $f\colon A\to P(B)$, and we write deterministic kernels as functions $f\colon A\to B$.

To be more precise, a deterministic kernel should really also be considered as a function $f\colon A\to P(B)$, such that <ref> is obeyed.

However, if we assume we are working in a category called $\mathsf{BorelStoch}$ (which is a common assumption in category-theoretic probability) then <ref> implies that $f$ always returns a delta measure <cit.>, and in this case there is not much harm in treating a deterministic kernel $f$ as a function $f\colon A\to B$.

§.§ The extension to measure theory

Above we described the category $\mathsf{FinStoch}$ and introduced string diagrams mostly in that context.

Here we briefly describe how this generalises to the measure-theoretic case, which is needed in order to think about continuous probability.

In the measure-theoretic case the objects ($X$, $Y$, etc.) are any measurable spaces rather than only finite sets.

Markov kernels are still functions $f\colon X\to P(Y)$, but now $P(Y)$ is the set of all probability measures on the measurable space $Y$.

(That is, $P(Y)$ is the set of all functions from the $\sigma$-algebra associated with $Y$ to $[0,1]$, such that Kolmogorov's axioms are obeyed.)

$P(Y)$ can itself be made into a measurable space in a standard way, and the function $f$ must obey an additional restriction that it be a measurable function.

(This means that the preimage of every element of $P(Y)$ must be a member of the $\sigma$-algebra associated with $X$.)

In this case $f(x)$ is a probability measure rather than a probability distribution, and composition is given by integration rather than summation.

(See <cit.> for the details.)

This gives rise to a category called $\mathsf{Stoch}$, whose objects are all measurable spaces and whose morphisms are all Markov kernels.

(This category is also known as the Kleisli category of the Giry monad, for reasons we do not discuss here.)

Unfortunately the category $\mathsf{Stoch}$ does not have all of the properties that one might want it to have. (See <ref> below.)

Because of this a common approach is to work in a category called $\mathsf{BorelStoch}$ (also discussed in <cit.>), in which the objects are a subset of measurable spaces called standard Borel spaces, and the morphisms are all Markov kernels between standard Borel spaces.

Standard Borel spaces include many kinds of measurable space that one would be likely to use in practice, and in particular they include both finite sets and $\mathbb{R}^{n}$ with its usual $\sigma$-algebra.

In the present paper, the properties of $\mathsf{BorelStoch}$ are used in two ways.

Firstly, in $\mathsf{BorelStoch}$ we can always use conditionals, as explained in the next section.

as a notational convenience we treat deterministic kernels and measurable functions as interchangeable, which makes sense in $\mathsf{BorelStoch}$ but doesn't hold in the more general case of $\mathsf{Stoch}$.

§.§ Conditionals and Bayes' theorem

Conditional probabilities and Bayes' theorem play central roles in the theory of inference. Here we briefly discuss how they look in string diagrams.

Given a joint distribution $\!\!\stringdiagram{
\wire (0,0) -- (2,0);
\wire (0,2) -- (2,2);
\stoch{0,1}{$q$}{2.5};
\rlabel{2,0}{A};
\rlabel{2,2}{B};
we may want to split it up into a product of a marginal and a conditional, which in traditional notation, in the discrete case, would be written $p(a,b) = p(a)\, p(b\,|\, a)$.

The category-theoretic approach, as set out in <cit.>, is slightly different. We write the following, which is called a disintegration of $q$.
(The term “disintegration” is used because it is the opposite of integration.)

\begin{equation}
\label{conditional-definition-unparametrised}
\stringdiagram{
\stoch{2,0}{$q$}{4};
\wire(2,1) -- (4.5,1);
\wire(2,-1) -- (4.5,-1);
\rlabel{4.5,1}{B};
\rlabel{4.5,-1}{A};
%  \uulabel{4,1}{\phantom{H\sprime}}; % to line it up vertically with the rhs
\,\, =
\pbox{
\stringdiagram{
\stoch{2,0}{$q$}{4};
\wire(2,1) -- (4,1);
\wire(2,-1) -- (10,-1);
\uulabel{4,1}{B};
\blackdot{4,1};
\wire[2] (5.5,-1)--(5.5,1)--(10,1);
\blackdot{5.5,-1};
\ulabel{5,-1}{A};
\stoch{8,1}{$c$}{3};
\rlabel{10,1}{B};
\rlabel{10,-1}{A};
% \showgrid
\end{equation}

Here, $\!\!\stringdiagram{
\wire (0,0) -- (2,0);
\wire (0,2) -- (1.7,2);
\stoch{0,1}{$q$}{2.5};
\rlabel{2,0}{A};
\blackdot{1.7,2}
is the marginal of $A$ according to the joint distribution $q$.

In the finite case it can be written $\sum_{b\in B} q(a,b)$.

The kernel  $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$c$}{2}
\llabel{0,1}{A};
\rlabel{4,1}{B};
is called a conditional of $p$.

It is defined by <ref>, which in the finite case can be written

\begin{equation}
\label{conditional-discrete}
q(a,b) = \left(\sum_{b'\in B} q(a,b')\right) c(b\mg a).
\end{equation}

This is closely analogous to the identity $p(a,b) = p(a)\, p(b\,|\, a)$.

The difference is that $p(b\,|\,a)$ is defined as $p(a,b)/p(a)$, and is only defined when $p(a)>0$.

On the other hand, in <ref>, if $\left(\sum_{b'\in B} q(a,b')\right) = 0$ for some $a\in A$ then $q(a,b)$ must be $0$ for all $b\in B$, and consequently the equation puts no constraint on $c(b\mg a)$ in this case.

This means that instead of being undefined in this case, the conditional $c$ is not uniquely defined: there may be many different kernels $c$ that satisfy the equation.

This carries over to the general measure-theoretic case as well.

If we are in the category $\mathsf{BorelStoch}$ then for any joint distribution $\!\!\stringdiagram{
\wire (0,0) -- (2,0);
\wire (0,2) -- (2,2);
\stoch{0,1}{$q$}{2.5};
\rlabel{2,0}{A};
\rlabel{2,2}{B};
$ there exists at least one conditional $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$c$}{2}
\llabel{0,1}{A};
\rlabel{4,1}{B};
that satisfies <ref>, but there might be many.

(In the case of $\mathsf{Stoch}$ conditionals may fail to exist at all, see <cit.>.)

We may also want to disintegrate a joint distribution that is a function of some parameter, e.g. $\!\!\stringdiagram{
\wire (-2,1) -- (0,1);
\wire (0,0) -- (2,0);
\wire (0,2) -- (2,2);
\stoch{0,1}{$q$}{2.5};
\rlabel{2,0}{A};
\rlabel{2,2}{B};
\llabel{-2,1}{Z};

In this case <ref> becomes

\begin{equation}
\label{conditional-definition}
\stringdiagram{
\stoch{2,0}{$q$}{4};
\wire (-1,0) -- (2,0);
\wire(2,1) -- (4.5,1);
\wire(2,-1) -- (4.5,-1);
\rlabel{4.5,1}{B};
\rlabel{4.5,-1}{A};
\llabel{-1,0}{Z};
%  \uulabel{4,1}{\phantom{H\sprime}}; % to line it up vertically with the rhs
\,\, =
\pbox{
\stringdiagram{
\wire[2.25] (-1,0) -- (-1,2.25) -- (7.5,2.25);
\stoch{2,0}{$q$}{4};
\wire (-2,0) -- (2,0);
\blackdot{-1,0};
\wire(2,1) -- (4,1);
\wire(2,-1) -- (10,-1);
\rlabel{4.3,1}{B};
\blackdot{4,1};
\wire[2] (5.5,-1)--(5.5,1)--(8,1);
\wire (8,1.6) -- (10,1.6);
\blackdot{5.5,-1};
\ulabel{5,-1}{A};
\stoch{8,1.6}{$c$}{3};
\rlabel{10,1.6}{B};
\rlabel{10,-1}{A};
\llabel{-2,0}{Z};
% \showgrid
\end{equation}

Conceptually this is very similar.

We want the disintegration to hold for every parameter value $z\in Z$, and we define the conditional to be a function of $z$ as well as of $a\in A$.

In the discrete case, <ref> is analogous to the identity $p(a,b\,|\, z) = p(a\,|\, z)\,p(b\,|\, a,z)$.

Bayes' theorem is closely related to conditional probability and can be expressed in a similar way.

Given a prior $\!\!\stringdiagram{
\wire (2,1)--(4,1);
\stoch{2,1}{$q$}{2}
\rlabel{4,1}{A};
and a kernel
\wire (0,1)--(4,1);
\stoch{2,1}{$f$}{2}
\llabel{0,1}{A};
\rlabel{4,1}{B};
we can define a Bayesian inverse of $f$ with respect to $q$, which is a kernel $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$f^{\dagger}$}{2}
\llabel{0,1}{B};
\rlabel{4,1}{A};
such that

\begin{equation}
\label{bayesian-inverse-unparametrised}
\pbox{
\stringdiagram{
\wire(1,0) -- (3,0);
\stoch{1,0}{$q$}{3};
\rlabel{3.8,0}{A};
\blackdot{3,0};
\wire[1.5] (3,0) -- (3,1.5) -- (7.5,1.5);
\ulabel{7.5,1.5}{B};
\stoch{5.75,1.5}{$f$}{3};
\wire[1.5] (3,0) -- (3,-1.5) -- (7.5,-1.5);
\ulabel{7.5,-1.5}{A};
\,\,=
\stringdiagram{
\wire(-1.5,0) -- (3,0);
\stoch{-1.5,0}{$q$}{3};
\ulabel{0,0}{A};
\stoch{1.5,0}{$f$}{3};
\rlabel{3.8,0}{B};
\blackdot{3,0};
\wire[1.5] (3,0) -- (3,1.5) -- (7.5,1.5);
\stoch{5.75,-1.5}{$f^{\dagger}$}{3};
\wire[1.5] (3,0) -- (3,-1.5) -- (7.5,-1.5);
\ulabel{7.5,1.5}{B};
\ulabel{7.5,-1.5}{A};
\end{equation}

The Bayesian inverse $f^{\dagger}$ depends on the prior $q$ as well as on the kernel $f$.

If we had chosen a different distribution in place of $q$, the Bayesian inverse $f^{\dagger}$ would be different.

As with conditionals, Bayesian inverses are not necessarily unique, and for a given $f$ and $q$ there may be many kernels $f^{\dagger}$ that satisfy <ref>.

(In fact, Bayesian inverses can be seen as a special case of conditionals.)

We may also consider the case where the prior takes a parameter, e.g. $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$q$}{2}
\llabel{0,1}{Z};
\rlabel{4,1}{A};

In this case a Bayesian inverse in general also needs to depend on the parameter, which gives us the following more general definition:

\begin{equation}
\label{bayesian-inverse}
\pbox{
\stringdiagram{
\wire(-1,0) -- (3,0);
\stoch{1,0}{$q$}{3};
\rlabel{3.8,0}{A};
\blackdot{3,0};
\wire[1.5] (3,0) -- (3,1.5) -- (7.5,1.5);
\ulabel{7.5,1.5}{B};
\stoch{5.75,1.5}{$f$}{3};
\wire[1.5] (3,0) -- (3,-1.5) -- (7.5,-1.5);
\ulabel{7.5,-1.5}{A};
\llabel{-1,0}{Z};
\,\,=
\stringdiagram{
\wire(-4,0) -- (3,0);
\blackdot{-3,0};
\wire[2] (-3,0) -- (-3,-2) -- (5.75,-2);
\stoch{-1.5,0}{$q$}{3};
\ulabel{0,0}{A};
\stoch{1.5,0}{$f$}{3};
\rlabel{3.8,0}{B};
\blackdot{3,0};
\wire[1.5] (3,0) -- (3,1.5) -- (7.5,1.5);
\stoch{5.75,-1.5}{$f^{\dagger}$}{3};
\wire[1.5] (3,0) -- (3,-1.5) -- (7.5,-1.5);
\ulabel{7.5,1.5}{B};
\ulabel{7.5,-1.5}{A};
\llabel{-4,0}{Z};
\end{equation}

The references <cit.> contain much more detail about Bayes' theorem in this form.

§ MORE DETAILS ABOUT BAYESIAN INTERPRETATIONS

§.§ Unpacking Bayesian filtering interpretations

In this section we give some more intuition for <ref> and then note some consequences of it.

The section deals mostly with the case where $S$, $Y$ and $H$ are discrete sets, meaning that we can reason in terms of probability distributions rather than measure theory.

In this case <ref> can be written in a form that makes the relationship to Bayes' theorem more clear.

We define a notion of subjectively impossible input, which is a value of $S$ that the reasoner believes with certainty will not occur as its next input.

(This does not imply that the input actually is impossible according to the true dynamics of the environment.)

We show that <ref> puts no constraints on the reasoner's posterior after receiving a subjectively impossible input.

We also show that the possible interpretations of a machine only depend on which states can transition to which other states given which inputs, and not on the probabilities of such transitions.

In addition, we show that some machines admit no non-trivial interpretations at all.

In order to unpack <ref> a little more, let us consider the case where $S$, $Y$ and $H$ are discrete.

Before starting we note that in the finite case, the definition of $\psi_S$, <ref>, can be written as

\begin{equation}
\psi_S(s\mg y) = \sum_{h\in H}\psi_{S,H'}(s,h\mg y).
\end{equation}

In this case, <ref> can be written in symbols as

\begin{equation}
\psi_{S,H'}(h,s\mg y) \gamma(y'\mg y,s) = \psi_S(s\mg y) \gamma(y'\mg y,s) \psi_H(h\mg y'),
\end{equation}

for all $s\in S, h,\in H, y,y'\in Y$.

We can cancel $\gamma(y'\mg y,s)$ from both sides on the assumption that it is positive, yielding

\begin{equation}
\label{filtering_intuitive_version}
\gamma(y'\mg y,s)>0 \,\implies\,   \psi_{S,H'}(h,s\mg y)  = \psi_S(s\mg y) \psi_H(h\mg y').
\end{equation}

The condition $\gamma(y'\mg y,s)>0$ means that $y'\in Y$ is a possible next state when the machine starts in state $y\in Y$ and receives the input $s\in S$.

(There may be many possible next states in this situation because the machine may be stochastic.)

Let us then suppose that the machine starts in state $y$, receives an input $s$, and transitions to state $y'$.

Let $h$ be an arbitrary element of $H$.

The number $\psi_{S,H'}(h,s\mg y)\in [0,1]$ can then be seen as the reasoner's prior probability that the next state is $h$ and the next input is $s$.

In more traditional notation we might write this as $P(H'=h, S=s)$, where we leave the state of the underlying machine implicit.

(Here we do not attempt to formalise this in terms of random variables, but simply treat it as a kind of notational shorthand for $\psi_{S,H'}(h,s\mg y)$.)

We may then regard $\psi_S(s\mg y)$ as the reasoner's prior probability that the next input is $s$, i.e. $P(S=s) = \sum_{h\in H} P(H=h,S=s)$.

However, since $\psi_H(h\mg y')$ is conditioned on $y'$ rather than $y$, we instead regard it as the reasoner's posterior probability that $H'=h$.

(We refer to $H'$ rather than $H$ here because after it receives an input its previous “next” hidden state becomes its current hidden state.)

$\psi_H(h\mg y')$ therefore corresponds to what we might write as $P(H'=h \mid S=s)$.

With this informal shorthand notation <ref> then says

\begin{equation}
\label{traditional-bayes-filtering}
P(H'=h, S=s) = P(S=s)\, P(H'=h \mid S=s),
\end{equation}

which has the same appearance as a familiar identity from elementary probability theory.

It corresponds to a single step of Bayesian filtering, which we spell out in more detail in <ref>.

This shorthand notation gives some intuition for why <ref> has the particular form it does, but it leaves the dependence on the state of the underlying machine implicit, and in so doing it obscures an important and subtle point.

In a more traditional context, $P(H'=h \mid S=s)$ is defined by

\begin{equation}
P(H'=h \mid S=s) = P(H'=h, S=s)/P(S=s)
\end{equation}

and has no value when $P(S=s)=0$.

However, in our case $P(H'=h \mid S=s)$ is a shorthand for $\psi_H(h\mg y')$, which is defined even when $\psi_S(s\mg y) = 0$.

In the case where $P(S=s)>0$, <ref> in the form of <ref> demands that $P(H'=h \mid S=s)$ is indeed equal to $P(H'=h, S=s)/P(S=s)$.

More precisely, if $\psi_S(s\mg y) > 0$ then we must have $\psi_H(h\mg y') =  \psi_{S,H'}(h,s\mg y)/\psi_S(s\mg y)$.

However, if $\psi_S(s\mg y) = 0$ then <ref> puts no constraints on $\psi_{S,H'}(h,s\mg y)$ at all, or indeed on $\psi_H(h\mg y)$.

In the case where $S$ is a discrete set (even if $Y$ and $H$ are not discrete), we say that $s\in S$ is a subjectively impossible input for a given state $y\in Y$ if $\psi_S(s\mg y) = 0$.

The point is that the reasoner believes, with certainty, that it will not receive the input $s$ as its next input.

The reasoning above says that in this situation, any posterior over $H$ is acceptable, because Bayes' rule doesn't specify what the posterior should be.

We find this somewhat analogous to the fact that in logic one can deduce any proposition from a contradiction.

<Ref> indeed permits any posterior in the case of a subjectively impossible input.

In fact, it even allows the posterior to be chosen stochastically in this case.

This is in a sense the minimal possible assumption we could make.

However, one could imagine addressing the issue in a different way by changing the framework, thus introducing a subtly different notion of interpretation than the one we have presented here.

One possibility would be to allow partial interpretations, where $\psi_H$ becomes a partial function, meaning that not every state of the machine needs to have an interpretation at all.

This would allow the posterior to be undefined in the case of a subjectively impossible input, rather than merely arbitrarily defined.

Another possibility would be to strengthen <ref> with additional conditions, forcing the posterior to be meaningful even after a subjectively impossible input.

We suspect that such an approach can lead to an interesting way to formalise improper priors, which are also about having meaningful posteriors in the case of `impossible' inputs, but we leave investigation of this to future work.

We note one other important consequence of the above reasoning, in the discrete case.

When we express <ref> in the form of <ref>, we see that it only depends on whether a transition from $y$ to $y'$ is possible given an input $s$, and not on the probability of such a transition.

Thus, for Bayesian filtering interpretations (and hence also for Bayesian inference interpretations), the only property of a machine that matters is which states can be reached from which other states (in a single step) under a given input.

(Strictly speaking this only makes sense in the discrete case, but we expect an analogous statement to this to hold more generally.)

Finally we note another consequence: <ref> implies that if $\gamma(y'\mg y,s)>0$ for every $y,y',s$, then

\begin{equation}
%  \psi_{S,H'}(h,s\mg y)  = \left(\sum_{h'\in H} \psi_{S,H'}(h',s\mg y)\right) \psi_H(h\mg y'),
\psi_{S,H'}(h,s\mg y)  = \psi_S(s\mg y) \psi_H(h\mg y'),
\end{equation}

for all $y,y'\in Y, s\in S, h\in H$.

Note that for any given $y\in Y$ there must exist some $s\in S$ such that $\psi_S(s\mg y)>0$.

It follows that $\psi_H(h\mg y')$ must be independent of $y'$ in this case.

In other words, if a machine is such that $\gamma(y'\mg y,s)>0$ for all $y,y',s$ then it only admits trivial interpretation maps, in which the beliefs are the same for every state.

Therefore the existence of any non-trivial Bayesian filtering interpretation implies a fairly strong constraint on a discrete machine's dynamics, namely that some of its transition probabilities are zero.

§.§ More on Bayesian filtering

In this section we show that <ref> does indeed correspond to Bayesian filtering, at least in the case of a deterministic machine.

Our proof of this is inspired by <cit.>, which proves an analogous fact about conjugate priors.

The proof we give uses string diagram reasoning, which means that it holds even in the most general measure-theoretic context; we do not need to assume that the sets involved are discrete.

Since we restrict ourselves to only deterministic machines in this section, we will note a couple of things about deterministic machines before we talk about Bayesian filtering.

We first note that the condition for a machine $\gamma$ to be deterministic is

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.7\textwidth]{equation_figures/determinism-applied-to-gamma.png}.
\end{equation}

This comes from the defining equation for deterministic morphisms, <ref>, and also the axiom (<ref>), noting that $\gamma$ is a kernel with input $S\otimes Y$ and output $Y$.

Next we prove the following proposition, which is useful for reasoning about Bayesian filtering interpretations of deterministic machines.

Suppose $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};
}$ is a deterministic machine, and let $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H\!$}{2}
\llabel{0,1}{Y};
\rlabel{4,1}{H};
}$ and $\!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H};
\llabel{-4,-1}{ H};
}$ be arbitrary Markov kernels.

Then $\psi_H$ and $\kappa$ form a consistent Bayesian filtering interpretation of $\gamma$ (i.e. <ref> is satisfied) if and only if

\begin{equation}
\label{deterministic-machine-condition}
\raisebox{-0.5\height}{
\includegraphics[width=0.7\textwidth]{equation_figures/deterministic-machine-condition.png},
\end{equation}

with $\psi_{S,H'}$ and $\psi_S$ as defined in <ref>.

To see that <ref> implies <ref> we marginalise <ref>:

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.8\textwidth]{equation_figures/deterministic-machine-marginal.png}.
\end{equation}

This implies <ref> by the rules for Markov categories, specifically <ref>.

For the other direction we assume <ref> holds and calculate

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.5\textwidth]{equation_figures/deterministic-filtering-condition-proof.png}.
\end{equation}

The first step substitutes in the right-hand side of <ref>, the second rearranges using the rules of Markov categories, and the third uses the determinism condition.

This proves that <ref> holds.

We now consider what a Bayesian filtering task involves.

The idea is that the reasoner has a model of a hidden Markov process, given by the kernel $\!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H};
\llabel{-4,-1}{ H};

As described in the main text, this kernel can be thought of as a process that simultaneously transforms the hidden state, stochastically, into a new value and emits a visible “sensor value.”

Given a kernel of this type, we can iterate it to produce sequences of values in $S$.

For example, we can write

\begin{equation}
\pbox{
\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa^{3}$}{3}
\rlabel{0,-1}{H};
\rlabel{0,-3}{\,\,S^{3}};
\llabel{-4,-1}{ H};
\,=\,
\stringdiagram{
\wire (0,-1)--(-10,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{3}
\wire[1] (-0,-4) -- (-2,-4) --(-4,-2)--(-5,-2);
\stoch{-5,-1.5}{$\kappa$}{3}
\wire[1] (0,-5) -- (-4,-5) --(-7,-2)--(-8,-2);
\stoch{-8,-1.5}{$\kappa$}{3}
\rlabel{0,-3}{S};
\rlabel{0,-4}{S};
\rlabel{0,-5}{S};
\rlabel{0,-1}{H};
\llabel{-10,-1}{ H};
\ulabel{-3.5,-1}{ H};
\ulabel{-6.5,-1}{ H};
\end{equation}

where $S^{3}$ means $S\otimes S\otimes S$ and $\kappa^{n}$ is notation for iterating the kernel $n$ times.

A kernel of this kind, thought of as an infinitely iterated process, is sometimes called a “coalgebra,” since it is a special case of a more general concept of that name. (e.g. <cit.> takes a coalgebraic approach to de Finetti's theorem.)

For filtering we are interested in inferring the final hidden state of a system, given a finite sequence of visible states.

In order to reason about this, we define the following kernel:

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.6\textwidth]{equation_figures/sequence-interpretation.png}.
\end{equation}

This can be seen as an interpretation map, mapping the state of a reasoner to its beliefs about its next $n$ inputs, $S^{n} = (S_1, \dots, S_n)$, along with the final value of the hidden state, $H_n$.

These take the form of a joint distribution between $S^{n}$ and $H_n$.

This joint distribution is formed from the reasoner's initial prior over the initial hidden state $H_1$ (given by the kernel $\psi_H$) and the model $\kappa$, which is iterated $n$ times.

We define this because in filtering we wish to make a probabilistic inference of the final hidden state, $H_n$, given the sequence of visible states $S^{n}$.

To infer $H_n$ given $S^{n}$ we seek a disintegration of $\psi_{S^{n},H_n}$.

(See <ref> in <ref>.)

Specifically, we seek a kernel $\psi_{H_n\mid S^{n}}\colon S^{n}\otimes Y \to P(H)$ such that

\begin{equation}
\label{filtering-disintegration}
\raisebox{-0.5\height}{
\includegraphics[width=0.75\textwidth]{equation_figures/filtering-disintegration.png}.
\end{equation}

The kernel $\psi_{H_n\mid S^{n}}$ takes in a sequence $S^{n}$ of observations and returns the reasoner's conditional beliefs about $H_n$, given the sequence $S_n$.

It is also a function of the reasoner's initial beliefs $y\in Y$.

In fact such a kernel can be constructed iteratively in a natural way, if we assume that $\psi_H$ and $\kappa$ form a consistent Bayesian filtering interpretation.

To do this, we first define the iteration of $\gamma$, in a similar way to the iteration of $\kappa$:

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.75\textwidth]{equation_figures/iterating-gamma.png},
\end{equation}

where there are $n$ copies of $\gamma$ on the right-hand side. We can then state the following result, which shows that consistent Bayesian filtering interpretations can indeed be seen as performing Bayesian filtering, in the discrete case.

The kernel $
\stringdiagram{
\wire (-0.3,1)--(9,1);
\wire[0.5] (-0.3,3)--(0.5,3)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma^{n}$}{2};
\llabel{-0.3,3}{S^{n}\,};
\llabel{-0.3,1}{ Y\,\,\,};
\ulabel{4,1}{ Y};
\stoch{6.2,1.5}{$\psi_{H}$}{2};
\rlabel{9,1}{H};
$ is a conditional of $\psi_{S^{n},H_n}$, satisfying <ref>, in that

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.85\textwidth]{equation_figures/filtering-string-condition.png}.
\end{equation}

We begin by defining the kernel

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.6\textwidth]{equation_figures/psibar-definition.png}.
\end{equation}

We also define its iteration, $(\bar\psi_S)^{n}\colon Y\to Y\otimes S^{n} $, analogously to $\kappa^{n}$ and $\gamma^{n}$.

We note that the consistency equation for Bayesian filtering interpretations, <ref>, can be written in terms of $\kappa$ and $\bar\psi_S$, as

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.8\textwidth]{equation_figures/consistency-in-terms-of-barpsi.png}.
\end{equation}

We then calculate

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.8\textwidth]{equation_figures/filtering-proof-part-1.png},
\end{equation}

where the last step is by applying the other steps inductively.

We can then apply a second inductive argument in “the other direction” using <ref>, as follows:

\begin{equation}
\raisebox{-0.5\height}{
\includegraphics[width=0.7\textwidth]{equation_figures/filtering-proof-part-2.png},
\end{equation}

where the last step is again by applying the other steps inductively.

We have proved that
\stringdiagram{
\wire (-0.3,1)--(9,1);
\wire[0.5] (-0.3,3)--(0.5,3)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma^{n}$}{2};
\llabel{-0.3,3}{S^{n}\,};
\llabel{-0.3,1}{ Y\,\,\,};
\ulabel{4,1}{ Y};
\stoch{6.2,1.5}{$\psi_{H}$}{2};
\rlabel{9,1}{H};
$ is a conditional of $\psi_{S^{n},H_n}$.

The kernel $
\stringdiagram{
\wire (-0.3,1)--(9,1);
\wire[0.5] (-0.3,3)--(0.5,3)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma^{n}$}{2};
\llabel{-0.3,3}{S^{n}\,};
\llabel{-0.3,1}{ Y\,\,\,};
\ulabel{4,1}{ Y};
\stoch{6.2,1.5}{$\psi_{H}$}{2};
\rlabel{9,1}{H};
can be thought of as giving the reasoner's beliefs about $H$ after receiving a given sequence $S^{n}$ of inputs, starting from a given initial state $y\in Y$.

The result shows that these beliefs are consistent with the agent's prior $\psi_H(y)$ and the model $\kappa$, in the sense that the agent's final posterior beliefs about $H$ are a conditional of its initial joint beliefs about the sequence $S^{n}$ and the final hidden state.

We conclude that a deterministic machine with a consistent Bayesian filtering interpretation can indeed be seen as performing a Bayesian filtering task.

We expect this to be true in the general case of stochastic machines as well.

§.§ Bayesian inference interpretations and conjugate priors

In the main text we noted that Bayesian inference corresponds to a special case of Bayesian filtering.

By “Bayesian inference” here we mean the case where the reasoner is interpreted as assuming its inputs are i.i.d. samples from some known distribution with an unknown parameter space $H$, which we also call the hypothesis space.

The difference between inference and filtering is that we interpret the reasoner as believing that the value of $H$ is unknown but fixed.

That is, the reasoner assumes that $H$ doesn't change over time.

This corresponds to a special case of filtering in which  $\!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$\kappa$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H};
\llabel{-4,-1}{ H};
} =
\!\stringdiagram{
\wire (0,0) -- (5,0);
\wire[2] (1,0) -- (1,-2) -- (5,-2);
\blackdot{1,0};
\stoch{3,-2}{$\phi$}{2};
\rlabel{5,-2}{ S};
\rlabel{5, 0}{ H};
\llabel{0, 0}{ H};
for some kernel $\phi$ that we also call the model.

While $\kappa$ can be seen as a model of the environment's dynamics, $\phi$ has more of the character of a statistical model.

It is a model of how the agent's sensor values depend on the unknown value of the hidden parameter $H$.

However, we do not put any constraints on the hypothesis space $H$ or the model $\phi$.

In particular, we do not assume that $\phi$ is an injective function $H\to P(S)$, and we allow the case where $H$ is a finite set.

In the case of inference rather than filtering, the kernels  $\psi_S$ and $\psi_{S,H'}$  from <ref> can be written

\begin{equation}
\label{psi-s-inference}
\pbox{\stringdiagram {
\wire (0,0) -- (3,0);
\stoch{1.5,0}{$\psi_{S}$}{3};
\ulabel{0,0}{Y};
\ulabel{3,0}{S};
\,=
\stringdiagram {
\wire (0,0) -- (5.5,0);
\stoch{1.5,0}{$\psi_H\!$}{3};
\ulabel{0,0}{Y};
\ulabel{2.8,0}{H};
\stoch{4,0}{$\phi$}{3};
\ulabel{5.5,0}{S};
\end{equation}

\begin{equation}
\label{psi-sh-inference}
\pbox{
\stringdiagram{
\ulabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2,0}{$\psi_{S,H}\!$}{5};
\wire(2,1.25) -- (4,1.25);
\wire(2,-1.25) -- (4,-1.25);
\ulabel{4,1.25}{H};
\ulabel{4,-1.25}{S};
\,=
\stringdiagram{
\wire(0.5,0) -- (3.5,0);
\stoch{2,0}{$\psi_H\!$}{3};
\ulabel{0.5,0}{Y};
\rlabel{3.8,0}{H};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (7,1.5);
\ulabel{7,1.5}{H};
\stoch{5.5,-1.5}{$\phi$}{3};
\wire[1.5] (3.5,0) -- (3.5,-1.5) -- (7,-1.5);
\ulabel{7,-1.5}{S};
\end{equation}

We write $\psi_{S,H}$ instead of $\psi_{S,H'}$ because in the i.i.d. inference case there is only one hidden variable, that is, $H'=H$.

Thus, the joint distribution $\psi_{S,H}(y)$ can be seen as the reasoner's joint belief about its next input and the hidden variable $H$, when its underlying machine is in state $y$.

The consistency equation for Bayesian inference,
<ref>, then follows by substituting these for $\psi_{S,H'}$ and $\psi_S$ in <ref>, the consistency equation for Bayesian filtering interpretations.

As with Bayesian filtering interpretations, it is useful to consider the case in which the underlying machine is deterministic (but not necessarily discrete).

In <ref> we gave a simpler version of the consistency equation for Bayesian filtering interpretations, which is equivalent to <ref> in the case of a deterministic machine.

In the inference case we can substitute <ref> into this simplified consistency equation (<ref>) to obtain

\begin{equation}
\label{jacobs-equation}
\stringdiagram{
\wire(0,0) -- (3.5,0);
\stoch{2,0}{$\psi_H\!$}{3};
\ulabel{0,0}{Y};
\rlabel{3.8,0}{H};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (7.5,1.5);
\ulabel{7.5,1.5}{S};
\stoch{5.75,1.5}{$\phi$}{3};
\wire[1.5] (3.5,0) -- (3.5,-1.5) -- (7.5,-1.5);
\ulabel{7.5,-1.5}{H};
\pbox{
\stringdiagram{
\wire(-3,0) -- (3.5,0);
\stoch{-0.3,0}{$\psi_H\!$}{3};
\ulabel{0.9,0}{H};
\stoch{2.1,0}{$\phi$}{3};
\ulabel{-3,0}{Y};
\blackdot{-2,0};
\wire[1.5] (-2,0) -- (-2,-1.8) -- (5.75,-1.8);
\rlabel{3.8,0}{S};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (10,1.5);
\ulabel{10,1.5}{S};
\wire[1.2] (3.5,0) -- (3.5,-1.2) -- (5.75,-1.2);
\wire(5.75,-1.5) -- (10,-1.5);
\sqbox{5.75,-1.5}{$\gamma$}{3};
\ulabel{7,-1.5}{Y};
\stoch{8.2,-1.5}{$\psi_H\!$}{3};
\ulabel{10,-1.5}{H};
\end{equation}

This is exactly the equation given by <cit.> as a definition of a conjugate prior.

Both sides of <ref> express a joint distribution between $S$ and $H$, as a function of $Y$.

In the context of conjugate priors, $\phi$ is considered to be a family of distributions, with parameters $H$.

Our interpretation map $\psi_H$ corresponds to another family of distributions, which is a conjugate prior to $\phi$.

The machine state $Y$ corresponds to the so-called hyperparameters, i.e. the parameters of $\psi_H$.

This shift in perspective makes sense.

In a computational context, conjugate priors are often useful precisely because they offer a way to perform inference without needing to directly calculate Bayesian inverses at run-time.

Instead, the implementation only needs to keep track of the hyperparameters and update them in response to data.

This update takes place according to a deterministic function, whose form depends on the family $\phi$ and its conjugate prior $\psi_H$.

This updating of the hyperparameters is the role played by $\gamma$: it takes in a data point in $S$ along with the current value of the hyperparameters, and returns the updated hyperparameters.

<Ref> asserts that this must done in such a way that the new value of $Y$ does indeed correspond to the correct Bayesian posterior, when mapped to a distribution over $H$ by the kernel $\psi_H$.

We note that it is somewhat nontrivial to find a pair of kernels $\psi_H$, $\phi$ and a function $\gamma$ such that <ref> is obeyed.

However, many such examples are known.

(Although it is not an authoritative source, a useful list can be found online <cit.>, which explicitly gives both kernels and the update function for each example.)

Any example of a conjugate prior can be seen as a deterministic machine together with a consistent Bayesian inference interpretation.

In addition, in <ref> we give a number of examples of a different flavour, in that in our examples $H$ is either a finite or a countable set.

§.§ Unpacking Bayesian inference interpretations

We now unpack <ref> by converting <ref> into more familiar terms in the case where all the spaces are discrete sets, as we did for filtering interpretations in <ref>.

In the case where $Y$, $H$ and $S$ are finite sets, <ref> can be written as

\begin{equation}
\label{bayesian-consistency-kernels}
\psi_H(h\mg y)\, \phi(s\mg h)\, \gamma(y'\mg s,m) = \psi_S(s\mg y)\, \gamma(y'\mg s,y)\, \psi_H(h\mg y'), \\
\end{equation}

or equivalently,

\begin{equation}
\label{bayes-in-kernels}
\gamma(y'\mg s,y)>0\quad\implies\quad \psi_H(h\mg y)\, \phi(s\mg h) = \psi_S(s\mg y)\, \psi_H(h\mg y'),
\end{equation}

since we can cancel $\gamma(y'\mg s,y)$ if we assume it is positive.

For $\gamma(y'\mg s,y)$ to be positive means that it is possible for the machine to transition from state $y\in Y$ to state $y'\in Y$ after receiving the input $s\in S$.

We can now give an intuitive interpretation to the terms in this equation.

If the machine starts in state $y$, receives input $s$, and transitions to state $y'$ as a result, then we can regard $\psi_H(h\mg y)$ as the reasoner's prior beliefs about the hypothesis $h$,  $\psi_S(s\mg y)$ as its prior beliefs about the input $s$, and $\psi_H(h\mg y')$ as the reasoner's posterior belief about the hypothesis $h$. <Ref> can then be compared, term by term, to the much more familiar equation

\begin{equation}
p(h)\,p(s\mid h) = p(s)\, p(h\mid s).
\end{equation}

Here we have written $p(s\mid h)$ in place of $\phi(s\mg h)$ and $p(h\mid s)$ in place of $\psi_H(h\mg y')$ in order to emphasise the similarity to Bayes' theorem in a more familiar form.

Our definition, in the form of <ref> or <ref>, differs from this in that it explicitly takes account of the machine's state, and $\phi$ and $\psi_H$ are defined by Markov kernels rather than conditional probabilities.

We note that, as in the case of filtering (<ref>), our definition of a consistent Bayesian inference interpretation allows the posterior to be arbitrary in the case of subjectively impossible inputs, i.e. those $s\in S$ for which $\sum_{h\in H}\psi_H(h\mg y)\phi(s\mg h) = 0$ for a given state $y\in Y$.

Given such an input the reasoner may update its posterior to anything at all.

As with filtering, we regard this as the minimal assumption we could have made, but we can imagine several other choices that one could make instead.

These include allowing the posterior to be undefined in such cases; requiring it to be undefined; requiring it to obey some additional consistency equation such that the posterior would make sense even on subjectively impossible inputs; or requiring $\phi$ and $\psi_H$ to be such that subjectively impossible inputs do not exist.

We would consider these to be subtly different kinds of interpretation, and we leave their further investigation to future work.

§ DETAILS OF EXAMPLES

§.§ An Interpretation Of A Non-Deterministic Finite Machine

We here present a non-deterministic finite machine with internal state space $Y = \{ y_0, y_1, y_2 \}$ and sensory input space $S = \{ s_1, s_2 \}$.

Transitions for a three-state machine. Deterministic transitions are depicted using bold arrows, and non-deterministic transitions using regular arrows. The precise probability values for non-deterministic transitions are not shown, since we only need to know that they are non-zero.

One Bayesian interpretation of this machine, for a hidden state space $H = \{ h_1, h_2 \}$, is as follows (where $\delta$ is the Kronecker delta):

ϕ(s_i h_j)    = δ_ij

ψ(h_i y_j)    =

δ_ij  if  j ∈{ 1, 2 }

0.5  if  j = 0.

Under this interpretation, the model $\phi$ ascribed to the machine is that sensory inputs transparently reflect the hidden state.

The machine, in internal state $y_0$, is taken to be uncertain about the hidden state; in state $y_i \in \{ y_1, y_2 \}$ it is taken to be certain that the hidden state is $h_i$.

The dynamics of the machine match this interpretation: it transitions deterministically to $y_i$ when receiving input $s_i$, unless $s_i$ is “subjectively impossible” ($s_2$ at $m_1$, and $s_1$ at $m_2$).

Behaviour on subjectively impossible inputs is not constrained by the consistency equation, so this is a consistent Bayesian interpretation.

§.§ Machine counting occurrences of different observations

We now consider a countably infinite deterministic machine $(Y_0,S,\gamma_0)$.

Let $Y_0=\mathbb{N}^+\times \mathbb{N}^+$ ($\mathbb{N}^+$ excludes $0$) and the input space be $S = \{ +1, -1 \}$.

The machine deterministically computes the function $f_0: (Y_0 \times S) \to Y_0$, in the sense that $\gamma_0(f_0(y, s) \mg y, s) = 1$.

Essentially, it keeps distinct count of how many $+1$ and $-1$ inputs it has received. Formally:

f_0((i, j), s)    =

(i+1, j)  if  s = +1

(i, j+1)  if  s = -1

One consistent Bayesian interpretation $(\psi_0,\phi_0)$ for machine $\gamma_0$ uses hypothesis space $H_0 = [0, 1]$ and model:

ϕ_0(s h) = h^δ_-1(s)(1-h)^δ_+1(s)

\begin{align}
\delta_{u}(v):=\begin{cases}
1 \text{ if } u = v \\
0 \text{ else.}
\end{cases}
\end{align}

This model is known as the categorical distribution for two outcomes (or just the Bernoulli distribution).

The machine states were deliberately chosen to be the hyperparameters of a possible interpretation map $\psi_0:Y_0 \to H_0$ which is known as the Dirichlet distribution (and in this special case also as Beta-distribution):

ψ_0(h (i,j)) = 1/B(i,j) h^i-1 (1-h)^j-1

where $B(i,j)$ is the Beta function.

This interpretation map (the Dirichlet distribution) is the conjugate priors for categorical distributions.

This implies that $(\psi_0,\phi)$ form a consistent Bayesian inference interpretation, as explained in <ref>.

§.§ Machine tracking differences between the number of occurrences of different observations

We now consider another countably infinite deterministic machine $(Y_1,S,\gamma_1)$ which has the same input space as the machine in <ref>.

Let $Y_1=\mathbb{Z}$ and the input space again be $S = \{ +1, -1 \}$.

The machine $\gamma_0$ deterministically computes a function $f_1: (Y_1 \times S) \to Y_1$, in the sense that $\gamma_1(f_1(y, s) \mg y, s) = 1$.

Machine $\gamma_1$ only counts how many more $+1$ inputs it has received than $-1$ inputs. Formally:

f_1(k, s)    = k+s.

One consistent Bayesian interpretation $(\psi_1,\phi_1)$ for machine $\gamma_1$ uses hypothesis space $H_1 = \{ h_{+1}, h_{-1} \}$ and model:

ϕ(s h_i) =

0.75  if  i = s

0.25  otherwise.

The interpretation map $\psi_1:Y_1 \to H_1$ is

ψ_1(h_+1 k) = 1/2(1 + 0.75^k 0.25^-k)

ψ_1(h_-1 k) = 1/2(1 + 0.75^-k 0.25^k)

It is relatively easy to verify that $(\psi_1,\phi_1)$ is a consistent Bayesian interpretation with $\gamma_1$'s dynamics.

As a teaser for future work we may note the following.

Since machine $\gamma_0$ of <ref> stores the individual counts for $s_0$ and $s_1$ inputs, it also implicitly keeps track of the difference between those counts; $\gamma_1$ only keeps track of this difference.

Consequently, we can define a deterministic kernel $g:Y_0 \to P(Y_1)$ that maps any state $(i, j) \in Y_0$ of $\gamma_0$ to $g(i,j) \coloneqq \delta_{i-j}$ which is a probability measure over the state space of $\gamma_1$.

It turns out that for this map, for any $k' \in Y_1,s \in S$ and $(i,j) \in Y_0$ we have

\begin{align}
\label{eq:example_machine_map}
(\gamma_0\comp g)(k' \mg (i,j),s)=\sum_k \gamma_1(k' \mg k,s) g(k \mg(i,j)).
\end{align}

This implies that we can construct an interpretation of machine $\gamma_0$ from the interpretation $(\psi_1,\phi_1)$ of $\gamma_1$.

For this we precompose the interpretation map $\psi_1$ for $\gamma_1$ with the machine map $g$ to get a consistent Bayesian inference interpretation $(g \comp \psi_1,\phi_1)$ for $\gamma_0$.

In future work we intend to further develop the theory of how a consistent interpretation of one deterministic machine can be “pulled back” to other machines that are related in a similar way to <ref>.

§ DETAILS ON THE RELATION TO THE FEP

We here try to identify the structures in the FEP that are analogous to the notions of machine $\gamma$, model $\kappa$, and interpretation map $\psi_H$.

This suggests that, at least in some treatments of FEP, there is an implicit concept that is close to what we have called a reasoner.

We will call this putative concept the FEP reasoner.

Large parts of the FEP literature do not explicitly deal with FEP reasoners but are sometimes presented as based on them (e.g. in <cit.>).

The parts that construct the FEP reasoner are those called “Bayesian mechanics” and are still evolving.

A standard reference is <cit.> but this is known to contain some issues <cit.>.

The most recent version can be found in <cit.>.

Understanding precisely the relationship between the concepts of our Bayesian and the FEP reasoner is future work.

The following are preliminary observations.

§.§ Machine

We first identify the structure in the FEP setup that is most closely related to a machine and is also said to appear to perform Bayesian inference.

Unfortunately, the latest iteration of the conditions under which there exists an FEP reasoner, which is <cit.>, does not make this particular structure as explicit as the previous version <cit.>.

We will therefore identify this structure in the older version.

A corresponding structure should also exist in the newer version and we will hint at how it may differ.

The FEP setup in <cit.> consists of four sets of variables $\eta \in E,s \in S,a \in A,\mu \in M$ called external, sensory, active, and internal states with $E,S,A,M$ finite dimensional real vector spaces.

These variables obey the stochastic differential equations

η̇   =f_η(η,s,a) + ω_η

ṡ   =f_s(η,s,a) + ω_s

ȧ   =f_a(s,a,μ) + ω_a

μ̇   =f_μ(s,a,μ) + ω_μ

where $\omega_\eta,\omega_s,\omega_a,\omega_\mu$ are independent Gaussian noise terms.

The FEP goes beyond the scope of a reasoner and formulates a concept of agent.

The concept of an agent should, as part of its interpretation, make it possible to talk about deliberate actions.

In the FEP deliberate actions are associated to the active states $a$.

At the same time, the internal states are only involved in inference (or filtering) and the special case where there are no active states seems to be within the scope of the FEP.

This should still leave us with a FEP reasoner and make it more comparable to our Bayesian reasoner.

We therefore consider the special case where there are no active states such that we get:

η̇   =f_η(η,s) + ω_η

ṡ   =f_s(η,s) + ω_s

μ̇   =f_μ(s,μ) + ω_μ.

This looks like a continuous time version of the Bayesian network in <ref> and has the somewhat significant feature that all influences from the external states $\eta$ are mediated by the sensory states $s$.

This suggests that it is possible to see the sensory states $s \in S$ as inputs to a machine state $\mu \in M$ with the external states $\eta \in E$ “hidden behind” the sensory states.

The internal states $\mu \in M$ are supposed to appear to infer the external states.

So the state space $Y$ of the machine of the FEP reasoner should be identified with $M$.

Going by their name and their role in the earlier dynamics of <ref> it seems reasonable to identify the sensory state space $S$ with the input state space (also $S$ in our notation) of the machine.

This brings us to the machine's kernel $\gamma$.

Our formalism does not deal with continuous-time kernels at the moment so we only make some informal comments here.

Note that none of the following statements should be considered as proven.

Since all variables together form a (time-homogeneous) Markov process, we can choose times $t,t+\tau$ with $\tau>0$ and write the conditional probability density (assuming things are well behaved enough) at a state $(\eta',s',\mu')$ at $t+\tau$ given a state $(\eta,s,\mu)$ at time $t$ as $p(\eta',s',\mu',t+\tau\mid \eta,s,\mu,t)$ (this notation is taken from <cit.>).

We can then marginalise out $\eta'$ and $s'$ to get $p(\mu',t+\tau\mid \eta,s,\mu,t)$ which looks a bit closer to a machine kernel but still depends also on $\eta$.

We cannot just drop $\eta$ from this expression even if we assume <ref> holds since within a time interval $[t,t+\tau]$ with $\tau >0$ the influence from $\eta$ would propagate through the intermediate values of the sensory states to $\mu'$.

Instead we here condition on all those intermediate values of the sensory state between $t$ and $t+\tau$.

Write $s[t:t+\tau]$ for a part of the trajectory of the sensory state between $t$ and $t+\tau$ that starts in $s$.

Then, assuming <ref> we should get:

\begin{align}
p(\mu',t+\tau \mid \eta,s[t:t+\tau],\mu,t)=p(\mu',t+\tau\mid s[t:t+\tau],\mu,t).
\end{align}

In order to make this look even more like a kernel we may take the limit as $\tau \to 0$ and so we write

\begin{align}
\gamma(\mu'\mid  \mu,s):= \lim_{\tau \to 0} p(\mu',t+\tau\mid s[t:t+\tau],\mu,t)
\end{align}

which is just a notation for an expression that hopefully provides sufficient intuition for our purposes.

What is important is that within the system <ref> there should be a (continuous-time) machine describing the dynamics of the internal states in response to sensory states.

In <cit.> the structure of <ref> and thus <ref> is no longer assumed.

This means all variables can directly influence each other and the sensory states no longer play a special role.

However, the sensory (and usually the active states) are still special due to an additional assumption.

The larger process has to have a stationary distribution $p(\eta,s,a,\mu)$ that factorises according to

\begin{align}
\label{eq:mblanket}
\end{align}

which is referred to as a Markov blanket.

With this assumption only, one can no longer assume that the sensory states $s[t:t+\tau]$ can “shield” those states from direct influence by external states, which makes it more difficult to compare the dynamics to our setup.

A solution may be to use
a continuous-time version of the approach in <cit.>.

Below we ignore this issue and assume that we have the structure of <ref>.

§.§ Model

For a reasoner we also need a model and an interpretation map.

As already mentioned the FEP assumes that the system in <ref> has a stationary distribution $p(\eta,s,\mu)$.

One purpose of this assumption seems to be the definition of what we call the model.

In the language of the FEP literature the stationary distribution defines the generative model.

Here, generative model refers to a joint probability distribution over causes (parameters/hidden variables) and observed variables.

In <cit.> the generative model is defined to be $p(\eta,s,\mu)$ with $\eta$ as the hidden variables and observed variables $(s,\mu)$.

We are not sure why $\mu$ is also seen as an observed variable and not only $s$.

This could mean that the machine state $\mu$ itself is also modelled by an FEP reasoner.

However, this would need further investigation that we leave for future work.

So we resort to a previous version where only the marginalised stationary distribution $p(\eta,s)$ was considered as the generative model (<cit.>,<cit.>).

In that case the hidden variable space $H$ in our notation should be identified with the external state space $E$ and the model (in our sense) is a conditional distribution induced by the stationary distribution:

\begin{align}
\phi(s\mid \eta) \coloneqq p(s\mid\eta).
\end{align}

Note that, this choice of a model by itself does not immediately tell us whether the FEP reasoner does filtering or just inference in the sense of <ref>.

A model like $\phi(s\mg \eta)$ can be part of a filtering kernel $\kappa$ as well.

In both cases we also need an interpretation map.

§.§ Interpretation map

For the interpretation map $\psi_H$ we need a kernel of type $M \to P(E)$.

Indeed, a kernel that has the right type can be identified in the FEP literature.

This kernel is denoted $q_\mu(\eta)$ and we will identify $\psi_H(\eta \mg \mu)=q_\mu(\eta)$.

The kernel's definition, however, relies on another assumption of the FEP, namely the existence of a “synchronisation map” $\sigma:M \to E$.

To construct $\sigma$ let us first define two other functions $g_M:S \to M$ and $g_E:S \to E$ via

f_M(s)    𝔼_p(μ|s)[μ]

f_E(s)    𝔼_p(η|s)[η]

and then set

\begin{align}
\sigma(\mu) \coloneqq f_E(f_M^{-1}(\mu))
\end{align}

which is assumed to be well defined.

For details on when this exists in the linear case see <cit.>.

With this we can define $q_\mu(\eta)$ and in turn the interpretation map $\psi_H$.

This maps an internal state $\mu$ to the Gaussian distribution with mean value equal to $\sigma(\mu)$:

\begin{align}
\label{eq:FEPinterpretationmap}
\psi(\eta \mg \mu) \coloneqq q_{\mu}(\eta) \coloneqq \mathcal{N}(\eta; \sigma(\mu),\Sigma(\mu))
\end{align}

where the variance $\Sigma(\mu)$ is defined as the variance of the best Gaussian approximation to the model $p(s|\eta=\sigma(\mu))$ when the external state is equal to $\sigma(\mu)$ <cit.>.

Note that in <cit.> the whole stationary distribution is assumed as Gaussian and so $p(\eta|\mu)$ in the corresponding equation in that publication (i.e. Eq.3.3) is also a Gaussian.

In conclusion, the necessary ingredients for something like a Bayesian reasoner seem to be present in the FEP literature.

One thing that is special about the FEP reasoner is that its model $\kappa$ and interpretation map $\psi_H$ are derived from features of the process that the machine is embedded in.

We do not know whether there is an appropriate notion of consistency equation that the FEP reasoner obeys.

Presumably, instead of the equation for exact inference that we have presented, such an equation would express the idea that the FEP reasoner performs approximate inference in the form of free energy minimisation.

Other differences are that the FEP takes place in continuous time, and perhaps more significantly, that it deals with deliberate actions as well as inference.

However, it is not inconceivable that these could be expressed in the form of a consistency equation.

In the current formulations of the FEP, the interpretation is derived from the properties of the `true' environment, such as the stationary distribution, or the synchronisation map $\sigma$.

In our consistency equation approach, this need not be the case, since a reasoner's beliefs only need to be consistent and need not be correct.

This means in particular that no stationarity assumption is needed.

Nonetheless, perhaps an important idea behind the FEP is that the model that most closely corresponds to the true environment can be considered the best one.

A consistency equation approach would still be helpful, in order to systematically explore whether and how interpretations should relate to the larger process in which the machine is embedded.

§ ———————————————————————————

§.§ Every machine has a trivial consistent Bayesian interpretation

As stated in the main text  a trivial interpretation is as an interpretation $(\psi,\phi)$ in which the interpretation map $\psi$ maps every state $y \in Y$ to the same belief $\psi_0$ over parameters $H$.

To show that every machine  has a trivial consistent Bayesian interpretation $(\psi,\phi)$ we choose a constant model $\phi:H \to P(S)$ that

is a constant function,
i.e. for all $h_1,h_2 \in H$ we have $\phi(h_1)=\phi(h_2)$.

(Note that this is an equality between probability measures over $H$.)

To make the interpretation $(\psi,\phi)$ trivial we pick any probability measure over $H$ as the constant value $\psi_0 \in P(H)$ of the interpretation map $\psi:S \to P(H)$.

Indeed we find that it obeys <ref>.refer to the right equation, maybe plug in the constant interpretation map and model?

Intuitively, since all hypotheses explain the observation in the same way any prior belief remains unchanged by a Bayesian update.

Thus, a constant interpretation map $\psi$ together with a constant model $\phi$ is a consistent Bayesian interpretation.

Since constant models exist for all input and hypothesis spaces and constant interpretation maps exist for all hypothesis and state spaces all machines have trivial consistent Bayesian interpretations.

Next comment is a simpler way of stating the above

Let $\psi_0\in P(H)$ be any probability measure over $H$, and let $\phi_0\in P(S)$ be any probability measure over $S$.

Then define $\psi(y) = \psi_0$ for all $y\in Y$ and $\phi(h) = \phi_0$ for all $s\in S$.

We find that this obeys the consistency requirements [refer to correct equation]

However, “we find that” is not a proof. A proof is actually needed here I think.

§.§ A machine whose consistent Bayesian interpretations are trivial

We will now show that there exist a machine for which all consistent Bayesian interpretations are trivial[This does not, of course, prohibit them from possessing an interpretation in terms of implementing approximate Bayesian inference.].

Consider a finite machine (i.e. $Y$ and $S$ are finite sets) $\gamma$ in which the following holds:

\begin{align}
\forall y, y' \in Y, s \in S: \quad \gamma(y' \mg y, s) > 0
\end{align}

This machine has the property that any state $y$ might transition to any other state $y'$ on any input $s$.

We claim that every consistent Bayesian interpretation (whose space of hypotheses $H$ need not be finite) of such a machine must have a constant interpretation map i.e. $\psi(y_0) = \psi(y_1)$ for all $y_0, y_1 \in Y$.

Here is a proof sketch.

Write $y \xmapsto{s} y'$ to denote that $y$ can transition to $y'$ upon receiving the subjectively possible input $s$, i.e. $\gamma(y' \mg y, s) > 0$ and $(\psi\comp \phi)(s \mg y) > 0$.

We have that $y_0 \xmapsto{s} y_1$ and $y_0 \xmapsto{s} y_2$ together imply that $\psi(y_1) = \psi(y_2)$, since $s$ is subjectively possible at $y$, and therefore both $y_1$ and $y_2$ must encode the same well-defined posterior distribution.

There must be at least one subjectively possible $s$ at any given $y$.

By construction of $\gamma$, for this $y$ and $s$, and for arbitrary $y_0, y_1 \in M$, we have that $y \xmapsto{s} y_0$ and $y \xmapsto{s} y_1$.

Hence we have that $\psi(y_0) = \psi(y_1)$ for all $y_0, y_1$. QED.

§.§ Machines with non-trivial consistent Bayesian interpretation with respect to all models

not finished

For IID filtering, which is equivalent to exact Bayesian inference, a distinct count of every input is a sufficient statistic for every model (because permutation of the input sequence makes no difference for IID inference).

It follows that machine $\gamma_1$ supports (up to relabelling of states) every consistent exact Bayesian interpretation that could be assigned to any machine whose input space is binary[For the filtering case, a machine which stores its entire sensory history is similarly `universal'.].

However, the same is not true of $\gamma_0$, which `forgets' permutation-insensitive information about its input history.

Hence, $\gamma_1$ supports interpretations that $\gamma_0$ does not (even up to relabelling of states).

[ TO-DO: GIVE AN EXAMPLE? ]

THE REST OF THIS SECTION TO BE DELETED

might delete this section, not sure it's needed now

To introduce the notion of a consistency equation it is helpful to begin with the case of conjugate priors mentioned above .

In this case we require the machine's update kernel to be deterministic, so that it can be regarded as simply a (measurable) function $\gamma\colon Y\times S \to Y$.

We choose to write deterministic functions without the curved edge, so that a deterministic update function $\gamma$ is written $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};

To introduce the notion of a consistency equation it is helpful to begin with the notion of a conjugate prior.

The usual setting for thinking about conjugate priors is that we have a parametrised family of distributions over some space $X$, which can be thought of as a Markov kernel $\phi\colon \Theta\to P(X)$, where $\Theta$ is the space of possible parameter values.

If we have a prior over $\Theta$ then, given a sample $x\in X$, we can calculate the posterior over $\Theta$ using Bayes' rule.

The notion of a conjugate prior involves a family of distributions or statistical model, which we write as a kernel $\phi\colon H\todot S$.

Here $H$ is the space of parameters of the family, which we may also think of as a hidden variable that we wish to interpret the machine as reasoning about.

For each $h\in H$ the model $\phi$ defines a probability measure over the space of possible observations $S$, which justifies the name “family of distributions.”

We then also ask that the machine's state space $Y$ parametrises a set of distributions over $H$.

We therefore introduce another kernel $\psi_H\colon Y\todot H$, which we also think of as defining a set of distributions over $H$, parametrised by $Y$.

In the context of Bayesian statistics, the intended meaning of $\psi_H$ is that it is a conjugate prior for $\phi$, and $Y$ are its parameters (often called hyperparameters, to distinguish them from $H$).

In order to be a conjugate prior for $\phi$, the kernel $\psi_H$ must have a special property, which can be stated informally as follows:
suppose we start with a prior over $H$ that lies in the family defined by $\psi_H$.

Then if we condition on some data $s\in S$, then our posterior will also be in the family defined by $\psi_H$.

This implies that in practice we only need to update the hyperparameters $Y$ when receiving a new data point.

This will be the role played by $\gamma$: it takes in a data point in $S$ along with the current value of the hyperparameters, and returns the updated hyperparameters.

This must be done in such a way that the new value of $Y$ does indeed correspond to the correct Bayesian posterior, when mapped to a distribution over $H$ by the kernel $\psi_H$.

This requirement has been expressed formally in string diagrams by Jacobs Jacobs, eq. 16, which we repeat here using our conventions:

\begin{equation}
% \label{jacobs-equation}
\stringdiagram{
\wire(0,0) -- (3.5,0);
\stoch{2,0}{$\psi_H\!$}{3};
\ulabel{0,0}{Y};
\rlabel{3.8,0}{H};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (7.5,1.5);
\ulabel{7.5,1.5}{S};
\stoch{5.75,1.5}{$\phi$}{3};
\wire[1.5] (3.5,0) -- (3.5,-1.5) -- (7.5,-1.5);
\ulabel{7.5,-1.5}{H};
\pbox{
\stringdiagram{
\wire(-3,0) -- (3.5,0);
\stoch{-0.3,0}{$\psi_H\!$}{3};
\ulabel{0.9,0}{H};
\stoch{2.1,0}{$\phi$}{3};
\ulabel{-3,0}{Y};
\blackdot{-2,0};
\wire[1.5] (-2,0) -- (-2,-1.8) -- (5.75,-1.8);
\rlabel{3.8,0}{S};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (10,1.5);
\ulabel{10,1.5}{S};
\wire[1.2] (3.5,0) -- (3.5,-1.2) -- (5.75,-1.2);
\wire(5.75,-1.5) -- (10,-1.5);
\sqbox{5.75,-1.5}{$\gamma$}{3};
\ulabel{7,-1.5}{Y};
\stoch{8.2,-1.5}{$\psi_H\!$}{3};
\ulabel{10,-1.5}{H};
\end{equation}

Both sides of this equation express a joint distribution between $S$ and $H$, as a function of $Y$.

If we regard $\gamma$ as the update kernel for a deterministic physical machine, then any pair of kernels $(\psi_H,\phi)$ satisfying <ref> may be considered a consistent Bayesian interpretation.

Before explaining this in more detail, we first state a more general definition of Bayesian interpretation, which allows $\gamma$ to be stochastic.

We give the formal definition first and then unpack it in more familiar terms.

Given a machine $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\gamma$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ Y};
\rlabel{4,1}{ Y};
},$ a consistent Bayesian interpretation of $\gamma$ is given by a measurable space $H$ together with Markov kernels $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H\!$}{2}
\llabel{0,1}{Y};
\rlabel{4,1}{H};
}$ and $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\phi$}{2}
\llabel{0,1}{H};
\rlabel{4,1}{S};
}$ that satisfy

\begin{equation}
\label{bayesian-consistency}
\stringdiagram {
\wire (0,0) -- (11.5,0);
\ulabel{0,0}{Y};
\ulabel{11.5,0}{Y};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (11.5,2);
\ulabel{11.5,2}{S};
\stoch{3,2}{$\psi_H\!$}{3};
\stoch{6,2}{$\phi$}{3};
\blackdot{4.5,2};
\ddlabel{4.5,2}{H};
\stoch{9.5,0.25}{$\gamma$}{3};
\blackdot{7.5,2};
\ulabel{8,2}{S};
\wire[1.5] (7.5,2) -- (7.5,0.5) -- (9.5,0.5);
\wire[2] (4.5,2) -- (4.5,4) -- (11.5,4);
\ulabel{11.5,4}{H};
% \showgrid
\, = \!
\pbox{
\stringdiagram {
\wire (0,0) -- (15,0);
\ulabel{0,0}{Y};
\ulabel{15,0}{Y};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (15,2);
\ulabel{15,2}{S};
\stoch{3,2}{$\psi_H\!$}{3};
\ulabel{4.25,2}{H};
\stoch{5.5,2}{$\phi$}{3};
\stoch{9,0.25}{$\gamma$}{3};
\blackdot{7,2};
\ulabel{7.5,2}{S};
\wire[1.5] (7,2) -- (7,0.5) -- (9,0.5);
\wire[4] (10.5,0) -- (10.5,4) -- (15,4);
\blackdot{10.5,0};
\ulabel{11.3,0}{Y};
\stoch{13.2,4}{$\psi_H\!$}{3};
\ulabel{15,4}{H};
% \showgrid
\end{equation}

We also define the following two Markov kernels, which are convenient for reasoning about Bayesian reasoners.

\begin{equation}
\stringdiagram {
\wire (0,0) -- (3,0);
\stoch{1.5,0}{$\psi_{S}$}{3};
\ulabel{0,0}{Y};
\ulabel{3,0}{S};
\coloneqq \!\!
\pbox{\stringdiagram {
\wire (0,0) -- (5.5,0);
\stoch{1.5,0}{$\psi_H\!$}{3};
\ulabel{0,0}{Y};
\ulabel{2.8,0}{H};
\stoch{4,0}{$\phi$}{3};
\ulabel{5.5,0}{S};
\quad\quad\,\,
\stringdiagram{
\ulabel{0,0}{Y};
\wire(0,0) -- (2,0);
\stoch{2,0}{$\psi_{H\times S}\!$}{5};
\wire(2,1.25) -- (4,1.25);
\wire(2,-1.25) -- (4,-1.25);
\ulabel{4,1.25}{S};
\ulabel{4,-1.25}{H};
\coloneqq\!\!
\pbox{
\stringdiagram{
\wire(0.5,0) -- (3.5,0);
\stoch{2,0}{$\psi_H\!$}{3};
\ulabel{0.5,0}{Y};
\rlabel{3.8,0}{H};
\blackdot{3.5,0};
\wire[1.5] (3.5,0) -- (3.5,1.5) -- (7,1.5);
\ulabel{7,1.5}{S};
\stoch{5.5,1.5}{$\phi$}{3};
\wire[1.5] (3.5,0) -- (3.5,-1.5) -- (7,-1.5);
\ulabel{7,-1.5}{H};
\end{equation}

That is, $\psi_{S}$ is given by $\psi_S(s\mg y) = \sum_{h\in H}\psi_H(h\mg y)\phi(s\mg h)$, and $\psi_{H\times S}$ is given by $\psi_{H\times S}(h,s\mg y) = \psi_H(h\mg y)\phi(s\mg h)$.

We call the kernels $\psi_H$, $\psi_S$ and $\psi_{H\times S}$ interpretation maps.

Each of them maps the state of the machine to a distribution over some measurable space, which we think of as the agent's beliefs about a particular quantity, parametrised by its state.

In particular, $\psi_H$ maps the machine's state to the reasoner's current beliefs over the set of hypotheses $H$, while $\psi_S$ maps the machine's state to its beliefs about its next input.

The idea is that the kernel $\gamma$, along with the state spaces $M$ and the input space $S$, are properties of a physical system that can, in principle, be measured, whereas the interpretation maps and the model $\phi$ form what we term an interpretation.

The idea is that an interpretation is a “meaning” that can optionally be assigned to the system's dynamics, as long as <ref> is satisfied.

The model and the interpretation maps are not determined by the physics, but neither are they completely independent of it, because whether a given interpretation is consistent depends both on the interpretation and on the system's dynamics.

We use the term reasoner for a machine $\gamma$ together with a choice of interpretation.

This could be numbered as a proposition, but I think this informal statement flows better.
A consequence of <ref> is that, at least in the discrete case, the only thing that really matters about the probabilities $\gamma(y' \mg y,s)$ is whether they are zero or not.

That is, it matters which states are possible successors of the current state for a given input, but beyond that the probability of transitioning to any given successor state is irrelevant to the consistency of the interpretation.

This is because <ref> is concerned with exact Bayesian inference, which implies that the posterior must update deterministically.

(But see link section for an additional subtlety.)[-1cm]here I refer to subjectively impossible inputs, which should be explained below.

§ ROUGH DRAFTS AND DELETED TEXT

§ REWRITING - THIS IS EXPERIMENTAL

I got an itch to write up the Filt thing in some form. I feel that this construction is what the mathematicians (Toby, Jules etc.) are most likely to cite us for, and I don't want to leave it out. If this works it might replace quite a lot of my text below this section.

There are two ways we might approach the relationship between Bayesian inference and its physical implementation.

We call these the design perspective and the natural science perspective.

From the design perspective, we start with the inference procedure we wish to perform, and then ask how it can be implemented, for example in software, or by building a physical device.

From this perspective we can choose the properties we want the implementation to have.

In contrast, in the natural science perspective we are given a physical system of some kind, and we wish to determine what kind of inference it might be performing.

This is the inverse of the design perspective in a sense, and in general it presents a different set of challenges.could say more here

Although our main interest is in a natural science perspective, we will begin our discussion from the design perspective, outlining a generalised version of the Bayesian filtering problem and a natural way to solve it. write outline/intro when done

Let $H$ be a space of hypotheses, and suppose that for each outcome $h\in H$ we have a joint distribution over $H'$ and $S$, where $H'$ is some other (in general different) hypothesis space, and $S$ is a space of observable “sensor values.”

This situation can arise, for example, if $H$ is the space of possible hidden states of some system at a particular time, and $H'$ is the space of states of the same system at a later time.

(For now we do not impose the constraint that the two hypothesis spaces are the same, although later we will be concerned with the special case in which they are.)

The idea is that the system transitions stochastically from a state $h\in H$ to a state $h'\in H'$, and during this process it is possible to make an observation $s\in S$, which might depend on $h$ and might be co-distributed with $h'$.

If we have a prior over $H$ then we can calculate a joint distribution over $H'$ and $S$, which is given by $p(h',s) = \sum_{h\in H}p(h)p(h',s\mid h)$ in the discrete case.

Having observed a visible state $s\in S$ we may then calculate the conditional $p(h'\mid s) = p(h',s)/p(s)$, assuming $p(s)>0$.

This simple calculation is the basis of Bayesian filtering.

In the string diagram notation (explained in the supplementary material ), this calculation is written

\begin{equation}
\label{unparametrised-filtering-step}
\stringdiagram{
\ulabel{0.2,0}{H};
\wire(-1.5,0) -- (2,0);
\stoch{2,0}{$f$}{4};
\stoch{-1.5,0}{$q$}{3};
\wire(2,1) -- (4.5,1);
\wire(2,-1) -- (4.5,-1);
\rlabel{4.5,1}{H\sprime};
\rlabel{4.5,-1}{S};
%  \uulabel{4,1}{\phantom{H\sprime}}; % to line it up vertically with the rhs
\pbox{
\stringdiagram{
\ulabel{0.2,0}{H};
\wire(-1.5,0) -- (2,0);
\stoch{2,0}{$f$}{4};
\stoch{-1.5,0}{$q$}{3};
\wire(2,1) -- (4,1);
\wire(2,-1) -- (10,-1);
\uulabel{4,1}{H\sprime};
\blackdot{4,1};
\wire[2] (5.5,-1)--(5.5,1)--(10,1);
\blackdot{5.5,-1};
\ulabel{5,-1}{S};
\stoch{8,1}{$c$}{3};
\rlabel{10,1}{H\sprime};
\rlabel{10,-1}{S};
% \showgrid
\end{equation}

The left-hand side expresses the joint distribution between $H'$ and $S$ in terms of the prior over $H$, which we call $q$, and the kernel representing the joint distribution between $H'$ and $S$ as a function of $H$, which we have denoted $f$.

The right-hand side expresses a disintegration of the joint distribution into a marginal and a conditional, which we write $c$.

(Disintegrations were first written in this form by Cho+Jacobs.)

The kernel $c$ is the conditional, which takes an element $s\in S$ and returns the conditional distribution over $H'$ given $S=s$.

The marginal over $S$ is formed by deleting $H'$.

The equation says that multiplying the marginal by the corresponding conditional distribution must reproduce the joint distribution.

If the equation holds, then $c$ is a conditional distribution.

In general, such a conditional kernel always existsmake sure we mention BorelStoch before this! but might not be uniquely defined.

In the discrete case this is because the probability of $s$ might be zero according to the joint distribution $q\comp f$, in which case the equation puts no constraints on the output of $c$.

Informally, since Bayes' rule doesn't specify a posterior in this case, it is allowed to be anything.

This fact is explored in <cit.> and will be important for us later.

Now suppose, from a design perspective, that we want to implement an inference of this kind.

Generally, unless $H$ and $H'$ are small finite sets, it will not be practical to store the prior $q$ or the posterior $c(s)$
numerically as probability distributions.

Instead, typically, one wishes to use parametrised distributions, and only store the parameters.

Let us then choose two parameter spaces $\Theta$ and $\Theta'$ and two Markov kernels Θψ_HH and Θ ψ_H H, which we think of as parametrised families of distributions over $H$ and $H'$.

Our prior $q$ will then be replaced by the distribution $\psi_H(\theta)$ for some $\theta\in\Theta$.

Since a conditional distribution depends on the prior, <ref> becomes

\begin{equation}
\stringdiagram{
\ulabel{0.2,0}{H};
\wire(-3.5,0) -- (2,0);
\llabel{-3.5,0}{\Theta};
\stoch{2,0}{$f$}{4};
\stoch{-1.5,0}{$\psi_H$}{3};
\wire(2,1) -- (4.5,1);
\wire(2,-1) -- (4.5,-1);
\rlabel{4.5,1}{H\sprime};
\rlabel{4.5,-1}{S};
\pbox{
\stringdiagram{
\ulabel{0.2,0}{H};
\wire(-4,0) -- (2,0);
\wire[2.25] (-3.2,0) -- (-3.2,2.25) -- (4.5,2.25);
\wire[0.5] (4.5,2.25) -- (5,2.25) -- (6,1) -- (9,1);
\blackdot{-3.2,0};
\llabel{-4,0}{\Theta};
\stoch{2,0}{$f$}{4};
\stoch{-1.5,0}{$\psi_H$}{3};
\wire(2,1) -- (3.5,1);
\wire(2,-1) -- (11,-1);
\rlabel{3.8,1}{H\sprime};
\blackdot{3.5,1};
\wire (9,1.5) -- (11,1.5);
\wire[2.5] (4.5,-1)--(5.5,2.25)--(9,2.25);
\blackdot{4.5,-1};