# SSC: Semantic Scan Context for Large-Scale Place Recognition

Lin Li1, Xin Kong1, Xiangrui Zhao1, Tianxin Huang1 and Yong Liu1,∗ 1Lin Li,
Xin Kong, Xiangrui Zhao, Tianxin Huang and Yong Liu are with the Institute of
Cyber-Systems and Control, Zhejiang University, Hangzhou 310027, P. R. China.
(*Yong Liu is the corresponding author, email: yongliu@iipc.zju.edu.cn).

###### Abstract

Place recognition gives a SLAM system the ability to correct cumulative
errors. Unlike images that contain rich texture features, point clouds are
almost pure geometric information which makes place recognition based on point
clouds challenging. Existing works usually encode low-level features such as
coordinate, normal, reflection intensity, etc., as local or global descriptors
to represent scenes. Besides, they often ignore the translation between point
clouds when matching descriptors. Different from most existing methods, we
explore the use of high-level features, namely semantics, to improve the
descriptor’s representation ability. Also, when matching descriptors, we try
to correct the translation between point clouds to improve accuracy.
Concretely, we propose a novel global descriptor, Semantic Scan Context, which
explores semantic information to represent scenes more effectively. We also
present a two-step global semantic ICP to obtain the 3D pose ($x$, $y$, $yaw$)
used to align the point cloud to improve matching performance. Our experiments
on the KITTI dataset show that our approach outperforms the state-of-the-art
methods with a large margin. Our code is available at:
https://github.com/lilin-hitcrt/SSC.

##  I INTRODUCTION

Simultaneous Localization and Mapping (SLAM) has rapidly developed in recent
decades as critical technologies for autonomous vehicles and robots. Place
recognition represents the ability of robots to recognize previously visited
places, which can build global constraints for the SLAM system to eliminate
the odometry’s cumulative errors and establish a globally consistent map[1].
Place recognition is usually conducted by using images or point clouds. Since
point cloud data is rarely affected by environmental factors such as
illumination and seasonal changes, LiDAR-based methods have received
widespread attention in recent years.

Most existing works on LiDAR-based place recognition are achieved by encoding
the point cloud into global or local descriptors and then matching the
descriptors. They usually use low-level features such as coordinates[2, 3, 4,
5, 6], normal[7], reflection intensity[8, 9, 10, 7], etc. In recent years,
with the development of point cloud deep learning, many LiDAR-based object
detection[11] and semantic segmentation[12, 13] methods have been proposed,
making it possible to obtain semantic information from point clouds. However,
there are still only a few LiDAR-based works trying to use semantic
information[14, 15, 7].

Figure 1: An example of place recognition using semantic scan context. It is a
partial map of the KITTI sequence 08, where the frames 720 and 1500 form a
reverse loop. The lower part of the figure is the semantic scan context
corresponding to the two frames. Since the directions of them are opposite,
the descriptors are quite different, while the aligned one shown in Fig. 2 is
easy to distinguish. Figure 2: The pipeline of our approach. It mainly
consists of two parts: two-step global semantic ICP and Semantic Scan Context.
First, we conduct semantic segmentation on the raw point cloud. Then we use
semantic information to retain representative objects and project them onto
the x-y plane. The two-step global semantic ICP is performed on the projected
cloud to get the 3D pose ($\Delta x,\Delta y,\theta)$. Finally, we use the 3D
pose to align the original clouds and generate global descriptors (Semantic
Scan Context). The similarity score is obtained by matching SSC.

For place recognition, when a robot passes through a place visited before, it
does not mean that the two poses are the same. Instead, the robot may walk
through the original area from any direction, and there may be a small amount
of translation from the original position. Many existing works consider the
robot’s orientation, namely rotation, and realize the invariance of
rotation[14, 3, 4, 10]. They may think that the small translation will not
strongly impact the recognition result and therefore ignore it. However, we
find that simply ignoring the translation for the scan context-based methods
will greatly reduce the similarity of the positive samples, making them
difficult to identify.

In this paper, we propose a novel global descriptor named Semantic Scan
Context (SSC), which explores semantic information to enhance the expressive
power of descriptors. We also propose a two-step global semantic ICP that can
produce reliable results regardless of the pose initialization, to obtain the
3D pose $(x,y,yaw)$ of the point cloud. The pose is then used to align the
point clouds to reduce the influence of rotation and translation on the
similarity of the descriptors. Furthermore, it can also provide good initial
values for 6D ICP algorithms to refine the global pose further. Fig. 1 is a
demonstration of our results. The main contribution is summarized as follows:

  * •

We propose a novel global descriptor for LiDAR-based place recognition, which
exploits semantic information to encode the 3D scenes effectively.

  * •

We propose a two-step global semantic ICP, which doesn’t require any initial
values, to obtain the 3D pose $(x,y,yaw)$ of the point clouds.

  * •

We align point clouds with the obtained 3D poses to eliminate the influence of
rotation and translation error on the similarity of the descriptors, which can
also further benefit the SLAM system as good initial poses.

  * •

Exhaustive experiments on the KITTI odometry dataset show that our approach
achieves state-of-the-art performance both in place recognition and pose
estimation.

##  II RELATED WORK

According to the features used, we can divide the place recognition methods
into three categories: geometry-based, semi-semantic-based, semantic-based.

Geometry-based methods: Spin image [2] establishes a local coordinate system
for each point, then projects the point into the 2D space and counts the
number of points in different areas in the 2D space to form a spin image. ESF
[16] proposes a shape descriptor that combines angle, point-distance, and area
to boost the recognition rate. M2DP [5] projects the point cloud into multiple
2D planes and generates a density signature for each plane’s points. The left
and right singular vectors of those signatures are used as the global
descriptors. Scan context [3, 4] converts the point cloud to polar coordinates
and then divides it into blocks along the azimuth and radial directions.
Lastly, it encodes the z coordinate of the highest point in each block as a 2D
global descriptor. LocNet [6] divides a point cloud into rings, generates a
distance histogram for each ring, and stitches all histograms to form a global
descriptor. Then a siamese network is used to score the similarity between the
descriptors. LiDAR Iris [17] extracts a binary signature image for each point
cloud then uses the Hamming distance of two corresponding binary signature
images as the similarity. Seed [18] segments the point cloud into different
objects and encodes the topological information of the segmented objects into
the global descriptor. The above methods have achieved good results by
encoding low-level geometric structures into descriptors. It can be expected
that integrating more advanced features can further enhance the discriminative
power of descriptors.

Semi-semantic-based methods: Some methods use non-geometric information to
construct descriptors, such as reflection intensity or learning-based features
extracted by neural networks. Such features are related to the object type but
do not clearly indicate the semantic category, so we classify these methods as
semi-semantic based. ISHOT [9] and ISC [10] exploit the intensity information
of the point cloud for place recognition. SegMatch [19] and SegMap [20]
cluster a point cloud into segments. Then they extract features for each
segment and use the kNN algorithm to identify corresponds. PointNetVLAD [21]
combines PointNet [22] and NetVLAD [23] to extract global descriptors from the
3D point clouds end-to-end. $L^{3}$-Net [24] selects key points from the given
point cloud then uses a PointNet to learn local descriptors for each key
point. OREOS [25] projects the 3D point cloud into a 2D range image and
proposes a convolutional neural network to extract the global descriptor. DH3D
[26] designs a siamese network to learn 3D local features from the raw 3D
point clouds, then use an attention mechanism to aggregate these local
features as the global descriptor. LPD-Net [27] proposes the adaptive local
feature extraction module and the graph-based neighborhood aggregation module
to extract local features of the point cloud; then, as the PointNetVLAD, they
use the NetVLAD to generate the global descriptor. MinkLoc3D [28] uses a
sparse voxelized point cloud representation and sparse 3D convolutions to
compute a discriminative 3D point cloud descriptor. SeqSphereVLAD [29]
projects the point cloud onto a spherical view, extracts features on it and
sequences those features to form a descriptor. SpoxelNet [30] voxelized the
point cloud in spherical coordinates and defines the occupancy of each voxel
in ternary values. Then they use a neural network to extract the global
descriptor. The above methods combine more advanced features with geometric
features. However, most of them use neural networks to extract abstract
features, which are more complicated and not well interpretable.

Semantic-based methods: SGPR [14] represents the scene as a semantic graph
then uses a graph similarity network to score the similarity of the graphs.
GOSMatch [15] proposes a new global descriptor that is generated from the
spatial relationship between semantics. It also proposes a coarse-to-fine
strategy to efficiently search loop closures and gives an accurate 6-DOF
initial pose estimation. The two methods represent the scene as a graph and
abstract the object as a node in the graph, which will cause the loss of
features such as the size of each object. OverlapNet [7] designed a deep
neural network that uses different types of information, such as intensity,
normal, and semantics generated from LiDAR scans, to provide overlap and
relative yaw angle estimates between paired 3D scans. However, it is too slow
in preprocessing due to the need to calculating the normal and inferring the
complex network backbone. To use the semantic information more effectively, we
propose our Semantic Scan Context approach.

##  III METHODOLOGY

In this section, we present our semantic scan context approach. Different from
other scan context-based methods that use incomplete semantic information and
ignore small translations between point clouds, we explore to exploit full
semantic information and emphasize that the small translation between point
cloud pairs has a significant influence on the accuracy of recognition.

As shown in Fig. 2, our method consists of two main parts: two-step global
semantic ICP and Semantic Scan Context. The two-step global semantic ICP is
divided into Fast Yaw Angle Calculate and Fast Semantic ICP. First, we define
a point cloud frame as $P=\\{p_{1},p_{2},\cdots,p_{n}\\}$, with each point
$p_{i}=[x_{i},y_{i},z_{i},\eta_{i}]$, $\eta_{i}$ represent the semantic label
of $p_{i}$. Given a pair of point clouds $(P_{1},P_{2})$, we first use our
Fast Yaw Angle Calculate method to get the relative yaw angle $\theta$ between
them. Then we use the Fast Semantic ICP to calculate their relative
translation $(\Delta x,\Delta y)$ in the x-y plane. Through the above two
steps, we get the relative poses $(\Delta x,\Delta y,\theta)$ of the two
frames of point clouds in 3D pose space. In order to eliminate the influence
of rotation (e.g., reverse loop closures) and small translation on
recognition, we use the obtained relative pose to align point cloud $P_{2}$.
We mark the aligned point cloud as $P_{a}$. Finally, we use our global
descriptor – the Semantic Scan Context to describe $(P_{1},P_{a})$ as
$(S_{1},S_{2})$. The similarity score is obtained by comparing $S_{1}$ and
$S_{2}$.

(a) Yaw Aligned

(b) Translation Aligned

Figure 3: An illustration of the two-step global semantic ICP.

###  III-A Global Semantic ICP

It is known that the general ICP algorithm based on local iterative
optimization is susceptible to local minimums [31]. For place recognition, we
usually cannot get a valid initial value, which leads to the failure of the
general ICP algorithm. To solve this, we propose the two-step global semantic
ICP algorithm consisting of Fast Yaw Angle Calculate and Fast Semantic ICP.
Benefited from the use of semantic information, our algorithm does not require
any initial values to get satisfactory results.

Fast Yaw Angle Calculate. For scan context based methods, columns of their
descriptor represent the yaw angle. The pure rotation of the LiDAR in the
horizontal plane will cause the column shift of their descriptor. Scan context
and Intensity Scan Context get the similarity score and the yaw angle at the
same time. Specifically, they calculate similarity (or distance) with all
possible column-shifted descriptors and find the maximum similarity (or
minimum distance). However, there are two main disadvantages. Firstly, it’s
inefficient to compare the whole 2D descriptors by shifting. Secondly, they
still try to get the maximum score for point clouds from different places (not
loop closure). This obviously makes it more prone to false positives. To draw
the above issues, we propose the semantic-based fast yaw angle calculate
method.

Given a point cloud pair $(P_{1},P_{2})$, we select representative objects
such as buildings, tree trunks, and traffic signs based on semantic
information. Then we convert the filtered clouds to polar coordinate in the
x-y plane:

$\displaystyle p_{i}$ $\displaystyle=[r_{i},\varphi_{i},x_{i},y_{i},\eta_{i}]$
(1) $\displaystyle r_{i}$ $\displaystyle=\sqrt{x_{i}^{2}+y_{i}^{2}}$
$\displaystyle\varphi_{i}$ $\displaystyle=arctan(\frac{y_{i}}{x_{i}})$

where $p_{i}$ is the $i^{th}$ point in each converted cloud, $r_{i}$ and
$\varphi_{i}$ represent polar diameter and polar angle, respectively. Each
converted cloud is then segmented to $N_{a}$ sectors by yaw angle. We only
keep the point with the smallest polar diameter in each sector. Finally, we
get two clouds $P_{I1}$ and $P_{I2}$, with $N_{a}$ elements. We sort the
points in $P_{I1}$ and $P_{I2}$ according to the azimuth angle and save their
corresponding polar diameters as vectors $R_{1}$ and $R_{2}$. Similar to the
scan context, the shift of the column vector is related to the yaw angle:

$\displaystyle shift$
$\displaystyle=\mathop{argmin}\limits_{i,i\in[0,N_{a}]}\varPsi(R_{1},R_{2}^{i})$
(2) $\displaystyle\theta$ $\displaystyle=360-\frac{360\times shift}{N_{a}}$

where $R_{2}^{i}$ is $R_{2}$ shifted by $i^{th}$ element and $\varPsi$ is
defined as:

$\varPsi(R_{1},R_{2}^{i})=\left\lVert R_{1}-R_{2}^{i}\right\rVert_{1}$ (3)

Compared with Scan Context and Intensity Scan Context, our method only needs
to compare one-dimensional vectors; therefore, it is more efficient. Moreover,
our method does not obtain the angle via maximizing the score, which is
helpful to identify non-loop-closure point-cloud pairs. Fig. 3 shows the
result of Fast Yaw Angle Calculate.

Figure 4: An example of generating SSC. $\rho$ and $\theta$ represent the
polar diameter and polar angle, respectively. A sector corresponds to a
descriptor column, while a ring corresponds to a row of the descriptor.

Fast Semantic ICP. Though most works ignore translation between point clouds,
ignoring the translation causes considerable declines in our experiments. In
fact, for methods based on scan context, translation will affect both the row
and column of the descriptor. We can’t get the best result just by the column-
shifted descriptor. Therefore, we propose a fast semantic ICP algorithm to
correct the translation between point clouds.

To find the relative translation, we firstly rotate $P_{I2}$ to the same
direction as $P_{I1}$, and the rotated point cloud is $P_{Ia}$, which is
defined as:

$\displaystyle x_{ai}$ $\displaystyle=x_{i}cos(\theta)-y_{i}sin(\theta)$ (4)
$\displaystyle y_{ai}$ $\displaystyle=x_{i}sin(\theta)+y_{i}cos(\theta)$

where $(x_{i},y_{i})$ and $(x_{ai},y_{ai})$ represent the $i^{th}$ point in
$P_{I2}$ and $P_{Ia}$ respectively. Our ICP problem can be defined as:

$\displaystyle(\Delta x,\Delta y)$
$\displaystyle=\mathop{argmin}\limits_{\Delta x,\Delta
y}L=\mathop{argmin}\limits_{\Delta x,\Delta
y}\sum_{i=1}^{N_{a}}\Gamma(\eta_{ai},\eta_{ri})$ (5) $\displaystyle\times$
$\displaystyle\frac{(x_{ai}+\Delta x-x_{ri})^{2}+(y_{ai}+\Delta
y-y_{ri})^{2}}{2}$

where $(x_{ri},y_{ri})$ represents the corresponding point of
$(x_{ai},y_{ai})$, which is the point closest to $(x_{ai},y_{ai})$ in
$P_{I1}$, $\eta_{ai}$ and $\eta_{ri}$ are semantic labels of the points. If
$\eta_{ai}$ is equal to $\eta_{ri}$, then the output of
$\Gamma(\eta_{ai},\eta_{ri})$ is $1$; otherwise, $0$. As our point clouds are
ordered, we can search for the corresponding points near the position where
the yaw angle is consistent with the target point. Specifically, our search
interval for the $i^{th}$ target point is:

$[i+shift-\frac{N_{l}}{2},i+shift+\frac{N_{l}}{2}]$ (6)

where $N_{l}$ is the length of search interval and $shift$ is defined in Eq.
2. After a certain number of iterations, we can get the relative translation
between the input point clouds, shown in Fig. 3.

(a) 00

(b) 02

(c) 05

(d) 06

(e) 07

(f) 08

Figure 5: Precision-Recall curves on KITTI dataset. TABLE I: $F_{1}$ max
scores and Extended Precision on KITTI dataset

Methods | 00 | 02 | 05 | 06 | 07 | 08 | Mean
---|---|---|---|---|---|---|---
SC[3] | 0.750/0.609 | 0.782/0.632 | 0.895/0.797 | 0.968/0.924 | 0.662/0.554 | 0.607/0.569 | 0.777/0.681
ISC[10] | 0.657/0.627 | 0.705/0.613 | 0.771/0.727 | 0.842/0.816 | 0.636/0.638 | 0.408/0.543 | 0.670/0.661
M2DP[5] | 0.708/0.616 | 0.717/0.603 | 0.602/0.611 | 0.787/0.681 | 0.560/0.586 | 0.073/0.500 | 0.575/0.600
LI[17] | 0.668/0.626 | 0.762/0.666 | 0.768/0.747 | 0.913/0.791 | 0.629/0.651 | 0.478/0.562 | 0.703/0.674
PV[21] | 0.779/0.641 | 0.727/0.691 | 0.541/0.536 | 0.852/0.767 | 0.631/0.591 | 0.037/0.500 | 0.595/0.621
ON[7] | 0.869/0.555 | 0.827/0.639 | 0.924/0.796 | 0.930/0.744 | 0.818/0.586 | 0.374/0.500 | 0.790/0.637
SGPR[14] | 0.820/0.500 | 0.751/0.500 | 0.751/0.531 | 0.655/0.500 | 0.868/0.721 | 0.750/0.520 | 0.766/0.545
Ours-RN |  0.939/0.826 |  0.890/0.745 |  0.941/0.900 |  0.986/0.973 |  0.870/0.773 |  0.881/0.732 |  0.918/0.825
Ours-SK |  0.951/0.849 |  0.891/0.748 |  0.951/0.903 |  0.985/0.969 |  0.875/0.805 |  0.940/0.932 |  0.932/0.868

  * •

$F_{1}$ max scores and Extended Precision: $F_{1}$ max scores / Extended
Precision. The best scores are marked in bold and the second best scores are
underlined.

###  III-B Semantic Scan Context

Scan Context and Intensity Scan Context uses the points’ height and reflection
intensity as features, respectively. Their methods essentially take advantage
of the different characteristics of different objects in the scene. However,
height and reflection intensity is only low-level features of the object which
are not representative enough. We explore to use the high-level semantic
features to represent scenes and thus propose the Semantic Scan Context
descriptor.

Descriptor definition. Given a point cloud $P$, we first convert it to the
polar coordinate system as we did in Section III-A. Then, like scan context,
we divide the point cloud into $N_{s}\times N_{r}$ blocks along the azimuthal
and radial directions. Each block is represented by:

$\displaystyle B_{ij}=\\{\eta_{k}|\frac{(i-1)\cdot R_{max}}{N_{r}}\leq
r_{k}<\frac{i\cdot R_{max}}{N_{r}},$ (7) $\displaystyle\frac{(j-1)\cdot
2\pi}{N_{s}}-\pi\leq\varphi_{k}<\frac{j\cdot 2\pi}{N_{s}}-\pi\\}$

where $R_{max}$ is the the maximum effective measurement distance of LiDAR,
$i\in[1,N_{r}]$ and $j\in[1,N_{s}]$. Our descriptor can be defined by:

$S(i,j)=f(B_{ij})=\mathop{argmax}\limits_{\eta\in B_{ij}}E(\eta)$ (8)

$f$ is an encoding function to encode features of $B_{ij}$. Note that if
$B_{ij}=\varnothing,~{}f(B_{ij})=0$. We manually set the priority of different
semantics in function $E$ to show their representativeness. We believe objects
that appear less frequently in the scene are more representative (e.g.,
traffic signs are more representative than roads).

Similarity Scoring. Given aligned clouds $P_{1}$ and $P_{a}$, we can get their
descriptors $S_{1}$ and $S_{2}$ by Eq. 8. Then the similarity score between
them can be calculated by:

$\displaystyle score=\frac{\sum\limits_{1\leq i\leq N_{r}}\sum\limits_{1\leq
j\leq N_{s}}I(S_{1}(i,j)=S_{2}(i,j))}{\sum\limits_{1\leq i\leq
N_{r}}\sum\limits_{1\leq j\leq N_{s}}I(S_{1}(i,j)\neq 0~{}or~{}S_{2}(i,j)\neq
0)}$ (9)

where $I$ is the indicator function, defined by:

$I(x)=\left\\{\begin{aligned} &1&&x~{}is~{}true\\\
&0&&x~{}is~{}false\end{aligned}\right.$ (10)

Fig. 4 shows Semantic Scan Context creation.

(a) Average $F_{1}$ max scores

(b) Average $EP$

Figure 6: Average $F_{1}$ max score and Average Extended Precision
corresponding to different $\alpha$.

##  IV EXPERIMENTS

###  IV-A Experiment Setup

We conduct experiments on the KITTI odometry dataset[32] collected by a
64-ring LiDAR, which contains 11 training sequences (00-10) with ground truth
poses. We choose sequences with loop-closure (00,02,05,06,07,08) for
evaluation and note that sequence 08 has reverse loops while others are in the
same direction. Similar to SGPR[14], we regard the point cloud pair with a
relative distance less (greater) than 3m (20m) as a positive (negative)
sample. Since there are too many negative samples, we only select a part of
the negative samples for evaluation. Specifically, if there are $N_{p}$
positive samples in a sequence, we will randomly select $\alpha\cdot N_{p}$
negative samples. We can adjust the proportion of negative samples by changing
the coefficient $\alpha$.

The ground-truth semantic labels are from the SemanticKITTI dataset[33]. We
also test our method with the semantic segmentation algorithm (RangeNet++
[34]) to prove that our method can be applied to noisy predictions in real
situations. In our experiments, we set
$N_{a}=360,~{}N_{l}=20,~{}N_{s}=360,~{}N_{r}=50$. All experiments are done on
the same system with an Intel i7-9750H @3.00GHz CPU with 16 GB RAM.

###  IV-B Place Recognition Performance

As mentioned in Section IV-A, we use both ground-truth semantic labels (Ours-
SK) and predicted semantic labels (Ours-RN) for testing. We compare our
approach with the state-of-the-art methods, including Scan Context[3] (SC),
Intensity Scan Context[10] (ISC), M2DP[5], LiDAR Iris[17] (LI),
PointNetVLAD[21] (PV), OverlapNet[7] (ON), and SGPR[14]. For SGPR, we use
their pre-trained models trained with the 1-fold strategy. As we cannot
reproduce the results of OverlapNet, we use the pre-trained model provided by
the author. The model is trained on sequences 03-10, so sequences 05, 06, 07,
08 are included in the training set.

Fixed $\alpha$. In this experiment, we set $\alpha$ to 100, which means the
number of negative samples is $100N_{p}$. Fig. 5 shows the precision-recall
curve of each method. Additionally, we also use the maximum $F_{1}$ score and
Extended Precision[35] (EP) shown in Tab. I to analyze the performance. The
$F_{1}$ score is defined as:

$F_{1}=2\times\frac{P\times R}{P+R}$ (11)

where $P$ and $R$ represent the Precision and Recall, respectively; $F_{1}$ is
the harmonic mean of $P$ and $R$. It treats $P$ and $R$ as equally important
and measures the overall performance of classification. The Extended Precision
is defined as:

$EP=\frac{1}{2}(P_{R0}+R_{P100})$ (12)

where $P_{R0}$ is the precision at minimum recall, and $R_{P100}$ is the max
recall at $100\%$ precision. $EP$ is specifically designed metrics for place
recognition algorithms.

As shown in Fig. 5 and Tab. I, Ours-SK surpasses other methods in all
indicators of all sequences with a large margin. Especially in sequence 08,
which has only reverse loops, the performance of other methods drops
significantly while our method still performs well. This indicates that our
method is robust to view angle changes. OverlapNet performs well on most
sequences except 08. We guess this is because it uses the normal of the point
cloud, which will change as the point cloud rotates. Therefore, this method
cannot robustly handle reverse loops. SGPR works well on indicator the $F_{1}$
max score but poorly on the Extended Precision. We find that it gives some
negative samples a huge score, which causes the recall to be almost zero when
the accuracy reaches $100\%$. The result of Ours-RN is slightly worse than
Ours-SK as expected. As the difference is not obvious, it means that our
approach can adapt to semantic segmentation algorithms for actual systems.

Change $\alpha$. In this experiment, we change the value of $\alpha$ to
analyze the influence of the number of negative samples on those algorithms.
Fig. 6 shows the Average $F_{1}$ max score and Average Extended Precision
corresponding to different $\alpha$. It clearly shows that our method performs
better than others no matter how much $\alpha$ is taken. As $\alpha$
increases, the performance of all methods gradually decreases, but our method
is less affected, showing that our method can effectively identify negative
samples. For place recognition, negative samples are generally far more than
positive samples, which is one key reason why our method leads in metrics far
ahead. Moreover, identifying negative samples is significant as false
positives will bring fatal crashes to the SLAM system.

TABLE II: Yaw error on KITTI dataset sequences | SC (deg) | ISC (deg) | ON (deg) | Ours-SK (deg)
---|---|---|---|---
00 | 11.526 | 0.829 | 2.595 | 0.891
02 | 11.301 | 1.343 | 4.911 | 1.142
05 | 18.394 | 0.904 | 3.329 | 0.653
06 | 4.074 | 0.534 | 1.124 | 0.759
07 | 21.862 | 0.684 | 2.233 | 0.512
08 | 49.170 | 3.856 | 68.622 | 1.878
Average | 19.388 | 1.358 | 13.802 | 0.973

###  IV-C Pose Accuracy

As described in Section III-A, our approach can estimate the 3D relative pose
$(\Delta x,\Delta y,\theta)$, while most other methods cannot estimate pose or
can only estimate 1D pose (yaw). We compare our method with Scan Context,
Intensity Scan Context, and Overlap. The ground-truth pose is calculated by:

$\displaystyle T$ $\displaystyle=T_{1}^{-1}T_{2}$ (13) $\displaystyle(\Delta
x,\Delta y,\theta)$
$\displaystyle=(T(1,3),T(2,3),arctan(\frac{T(2,1)}{T(1,1)}))$

where $T_{1}\in SE(3)$ and $T_{2}\in SE(3)$ represent the pose of $P^{1}$ and
$P^{2}$, respectively. Since the pitch and roll angles are hardly changed in
autonomous vehicles, we ignore them.

Tab. II shows the relative yaw error on the KITTI dataset. We can see that our
method outperforms other methods in terms of the average relative yaw error.
Especially in the challenging sequence 08, affected by the reverse loop, most
methods perform poorly, while our method can still accurately estimate the yaw
angle. This again shows that our method can handle the reverse loop well. As
mentioned in Section IV-B, OverlapNet performs poorly due to its inability to
handle reverse loops.

Fig. 7 shows the relative translation error of our approach on the KITTI
dataset. As shown, our method can estimate accurate relative translation,
which is currently not possible with other methods to our knowledge. Thus, our
Fast Yaw Angle Calculate and Fast Semantic ICP approaches can give accurate 3D
pose estimation. This can provide a good initial value for the ICP algorithm
to obtain a 6D pose or directly serve as a global constraint in the SLAM
system.

Figure 7: Translation error. TABLE III: Contribution of individual components Yaw | ICP | Semantic | $F_{1}/EP$ | Decrease
---|---|---|---|---
| $\surd$ | $\surd$ | 0.896/0.820 | 3.6%/4.8%
$\surd$ |  | $\surd$ | 0.757/0.685 | 17.5%/18.3%
$\surd$ | $\surd$ |  | 0.775/0.762 | 15.7%/10.6%
$\surd$ | $\surd$ | $\surd$ | 0.932/0.868 | 0.0%/0.0%

###  IV-D Ablation Study

We design an ablation study to investigate the contribution of each component.
Specifically, we remove or replace a module at a time and then calculate the
$F_{1}$ max scores and Extended Precision. To show the contribution of our
Fast Yaw Angle Calculate method, we replace this module with the method used
in scan context – shift the column of descriptors and calculate the maximum
similarity score while obtaining the yaw angle. Similarly, we replace the
semantic label in the descriptor by maximum $z$ to see semantic contribution.
To evaluate the contribution of our Fast Semantic ICP approach, we directly
set $\Delta x$ and $\Delta y$ to 0. As shown in Tab. III, after removing Yaw,
ICP, and Semantic, the average $F_{1}$ max score decrease by $3.6\%$,
$17.5\%$, $15.7\%$, and the average Extended Precision decrease by $4.8\%$,
$18.3\%$, $10.6\%$. Therefore, the following conclusions can be drawn:

  * •

Compared with other methods, our approach can get a more accurate yaw angle
and translation.

  * •

As we emphasized, the small translation has a significant impact on scan
context-based methods. Simply ignoring the translation will greatly weaken the
performance.

  * •

High-level features, like semantics, can bring considerable improvements in
the scene description.

TABLE IV: Average time cost on KITTI 08

Methods | Size | Description | Retrieval | ICP | Total
---|---|---|---|---|---
SC | $20\times 60$ | 4.825 | 0.158 | - | 4.983
ISC | $20\times 90$ | 3.094 | 0.800 | - | 3.894
Ours | $50\times 360$ | 2.563 | 0.066 | 2.126 | 4.755

  * •

The unit of time in the table is milliseconds.

###  IV-E Efficiency

To evaluate the efficiency, we set $\alpha$ to $1$ and compare the average
time cost of our method with Scan Context and Intensity Scan Context on
sequence 08. As shown in Tab. IV, the total time cost of our approach is
acceptable. As we use the obtained 3D pose to align the point clouds in
advance, we don’t need to shift the column of descriptors during the matching
stage, so our retrieval speed is extremely fast. Our two-step global semantic
ICP only takes 2.126 milliseconds on average. This algorithm is fast due to
the following reasons. Firstly, since we only keep $N_{a}$ (360 taken in our
experiments) points, the computational cost is greatly reduced compared to the
original point cloud (about 120,000 points). Secondly, We divide the algorithm
into two steps, first calculate the yaw angle, and then iteratively calculate
$\Delta x$ and $\Delta y$, which simplifies the algorithm and speeds up the
calculation. Thirdly, when calculating $\Delta x$ and $\Delta y$, we use the
yaw angle to align the input clouds in advance. Therefore we don’t need to
traverse the entire point cloud when looking for the corresponding points.
Instead, we can find them near the corresponding positions, which greatly
reduces the number of searches.

##  V CONCLUSION

In this paper, we propose a novel semantic-based global descriptor for place
recognition. We propose a two-step global semantic ICP to obtain the 3D pose
$(x,y,yaw)$ of the point cloud pair, aligning the point clouds to improve the
descriptor matching accuracy. In addition, it can provide good initial values
for point cloud registration. We achieve leading performance on the KITTI
odometry dataset compared to the state-of-the-art methods.

Our method also has some limitations. Like most place recognition methods, our
method does not consider pitch angle and roll angle. Therefore, our method may
fail in some extreme scenarios.

In the future work, we will try to solve the above problems and further
explore the application of semantic information in LiDAR-based SLAM systems.

## References

  * [1] A. Angeli, D. Filliat, S. Doncieux, and J. Meyer, “Fast and incremental method for loop-closure detection using bags of visual words,” IEEE Transactions on Robotics, vol. 24, no. 5, pp. 1027–1037, 2008.
  * [2] A. E. Johnson and M. Hebert, “Using spin images for efficient object recognition in cluttered 3d scenes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 5, pp. 433–449, 1999.
  * [3] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4802–4809, 2018.
  * [4] G. Kim, B. Park, and A. Kim, “1-day learning, 1-year localization: Long-term lidar localization using scan context image,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1948–1955, 2019.
  * [5] L. He, X. Wang, and H. Zhang, “M2dp: A novel 3d point cloud descriptor and its application in loop closure detection,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 231–237, 2016.
  * [6] H. Yin, L. Tang, X. Ding, Y. Wang, and R. Xiong, “Locnet: Global localization in 3d point clouds for mobile vehicles,” in 2018 IEEE Intelligent Vehicles Symposium (IV), pp. 728–733, 2018.
  * [7] X. Chen, T. Läbe, A. Milioto, T. Röhling, O. Vysotska, A. Haag, J. Behley, and C. Stachniss, “OverlapNet: Loop Closing for LiDAR-based SLAM,” in Proceedings of Robotics: Science and Systems (RSS), 2020.
  * [8] K. P. Cop, P. V. K. Borges, and R. Dubé, “Delight: An efficient descriptor for global localisation using lidar intensities,” in 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 3653–3660, 2018.
  * [9] J. Guo, P. V. K. Borges, C. Park, and A. Gawel, “Local descriptor for robust place recognition using lidar intensity,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1470–1477, 2019.
  * [10] H. Wang, C. Wang, and L. Xie, “Intensity scan context: Coding intensity and geometry relations for loop closure detection,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 2095–2101, 2020\.
  * [11] S. Shi, C. Guo, L. Jiang, Z. Wang, J. Shi, X. Wang, and H. Li, “Pv-rcnn: Point-voxel feature set abstraction for 3d object detection,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
  * [12] X. Zhu, H. Zhou, T. Wang, F. Hong, Y. Ma, W. Li, H. Li, and D. Lin, “Cylindrical and asymmetrical 3d convolution networks for lidar segmentation,” arXiv preprint arXiv:2011.10033, 2020.
  * [13] H. Tang, Z. Liu, S. Zhao, Y. Lin, J. Lin, H. Wang, and S. Han, “Searching efficient 3d architectures with sparse point-voxel convolution,” in European Conference on Computer Vision, 2020.
  * [14] X. Kong, X. Yang, G. Zhai, X. Zhao, X. Zeng, M. Wang, Y. Liu, W. Li, and F. Wen, “Semantic graph based place recognition for 3d point clouds,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 8216–8223, 2020.
  * [15] Y. Zhu, Y. Ma, L. Chen, C. Liu, M. Ye, and L. Li, “Gosmatch: Graph-of-semantics matching for detecting loop closures in 3d lidar data,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5151–5157, 2020.
  * [16] W. Wohlkinger and M. Vincze, “Ensemble of shape functions for 3d object classification,” in 2011 IEEE International Conference on Robotics and Biomimetics, pp. 2987–2992, 2011.
  * [17] Y. Wang, Z. Sun, C. Z. Xu, S. E. Sarma, J. Yang, and H. Kong, “Lidar iris for loop-closure detection,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5769–5775, 2020.
  * [18] Y. Fan, Y. He, and U. X. Tan, “Seed: A segmentation-based egocentric 3d point cloud descriptor for loop closure detection,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5158–5163, 2020.
  * [19] R. Dubé, D. Dugas, E. Stumm, J. Nieto, R. Siegwart, and C. Cadena, “Segmatch: Segment based place recognition in 3d point clouds,” in 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 5266–5272, IEEE, 2017.
  * [20] R. Dubé, A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: Segment-based mapping and localization using data-driven descriptors,” The International Journal of Robotics Research, p. 0278364919863090, 2019.
  * [21] M. A. Uy and G. H. Lee, “Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4470–4479, 2018.
  * [22] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652–660, 2017\.
  * [23] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5297–5307, 2016.
  * [24] W. Lu, Y. Zhou, G. Wan, S. Hou, and S. Song, “L3-net: Towards learning based lidar localization for autonomous driving,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6389–6398, 2019.
  * [25] L. Schaupp, M. Bürki, R. Dubé, R. Siegwart, and C. Cadena, “Oreos: Oriented recognition of 3d point clouds in outdoor scenarios,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3255–3261, 2019.
  * [26] J. Du, R. Wang, and D. Cremers, “Dh3d: Deep hierarchical 3d descriptors for robust large-scale 6dof relocalization,” in European Conference on Computer Vision, pp. 744–762, Springer, 2020.
  * [27] Z. Liu, S. Zhou, C. Suo, P. Yin, W. Chen, H. Wang, H. Li, and Y.-H. Liu, “Lpd-net: 3d point cloud learning for large-scale place recognition and environment analysis,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2831–2840, 2019.
  * [28] J. Komorowski, “Minkloc3d: Point cloud based large-scale place recognition,” in Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 1790–1799, 2021.
  * [29] P. Yin, F. Wang, A. Egorov, J. Hou, J. Zhang, and H. Choset, “Seqspherevlad: Sequence matching enhanced orientation-invariant place recognition,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5024–5029, 2020.
  * [30] M. Y. Chang, S. Yeon, S. Ryu, and D. Lee, “Spoxelnet: Spherical voxel-based deep place recognition for 3d point clouds of crowded indoor spaces,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 8564–8570, 2020.
  * [31] J. Yang, H. Li, D. Campbell, and Y. Jia, “Go-icp: A globally optimal solution to 3d icp point-set registration,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 11, pp. 2241–2254, 2016\.
  * [32] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The kitti dataset,” The International Journal of Robotics Research, vol. 32, no. 11, pp. 1231–1237, 2013.
  * [33] J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “Semantickitti: A dataset for semantic scene understanding of lidar sequences,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 9297–9307, 2019.
  * [34] A. Milioto, I. Vizzo, J. Behley, and C. Stachniss, “RangeNet++: Fast and Accurate LiDAR Semantic Segmentation,” in IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), 2019.
  * [35] B. Ferrarini, M. Waheed, S. Waheed, S. Ehsan, M. J. Milford, and K. D. McDonald-Maier, “Exploring performance bounds of visual place recognition using extended precision,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 1688–1695, 2020.


\ulabel{5.3,-1}{S};
% \stoch{8.75,1.5}{$(\psi_H{\comp}f)|_S$}{4};
\stoch{8.75,1.5}{$c$}{4};
\rlabel{11,1.5}{H\sprime};
\rlabel{11,-1}{S};
% \showgrid
%  \pbox{
%  \stringdiagram{
% \ulabel{0.2,0}{H};
% \wire(-4,0) -- (2,0);
% \wire[2.25] (-3.2,0) -- (-3.2,2.25) -- (9,2.25);
% \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.5,-1);
% \rlabel{3.8,1}{H\sprime};
% \blackdot{3.5,1};
% \wire[2] (5.5,-1)--(5.5,1)--(9,1);
% \wire (9,1.5) -- (11.5,1.5);
% \blackdot{5.5,-1};
% \ulabel{5,-1}{S};
% \stoch{8.75,1.5}{$(\psi_H{\comp}f)|_S$}{4};
% \rlabel{11.5,1.5}{H\sprime};
% \rlabel{11.5,-1}{S};
%% \showgrid
% }}{.}
\end{equation}

This is an instance of definition 11.4 in <cit.>.

The conditional $c$ is now a kernel of type $\Theta\times S \to P(H')$, depending on both a data point $s\in S$ and a parameter value $\theta\in\Theta$.

The next idea is that if our parametrised distributions are suitably chosen, then for every $s$ and every $\theta$ the conditional over $H'$ will be a member of the family parametrised by $\Theta'$. This amounts to saying that there exists a deterministic function $\gamma\colon \Theta\times S \to \Theta'$ such that
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$c$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ \Theta};
\rlabel{4,1}{ H\sprime};
%\wire (-2.5,1)--(6.5,1);
%\wire[0.5] (-2.5,3)--(-2,3)--(-1,2)--(0,2);
%\llabel{-2.5,3}{ S};
%\llabel{-2.5,1}{ \Theta};
%\rlabel{6.5,1}{ H\sprime};
\stringdiagram{
\wire (0,1)--(9,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}{ \Theta};
\ulabel{3.6,1}{ \Theta\sprime};
\stoch{6.2,1.5}{$\Psi_{H\sprime}$}{2};
\rlabel{9,1}{H\sprime};
The equation then becomes

\begin{equation}
\label{deterministic-heterogeneous-filtering}
\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) -- (8.5,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) -- (13,-1);
\rlabel{3.8,1}{H\sprime};
\blackdot{3.5,1};
\wire (8.5,1.5) -- (13,1.5);
\wire[2.5] (4.5,-1)--(5.5,2.25)--(8.5,2.25);
\blackdot{4.5,-1};
\ulabel{5.3,-1}{S};
\sqbox{7.75,1.5}{$\gamma$}{4};
\stoch{11,1.5}{$\psi_{H\sprime}$}{4};
\rlabel{13,1.5}{H\sprime};
\rlabel{13,-1}{S};
\ulabel{9.25,1.5}{\Theta\sprime}
% \showgrid
\end{equation}

The point is that once the appropriate families of distributions have been chosen such that this equation holds, only the function $\gamma$ needs to be implemented.

I am again considering only talking about deterministic machines. If we don't do that, the following footnote would be a paragraph at this point, and we'd use stochastic updates after that.
Later, in taking a natural science perspective, we will want to consider the case where $\gamma$ is not a function $\Theta\times S \to \Theta'$ but instead a Markov kernel $\Theta\times S \to P(\Theta')$.

That is, $\gamma$ may behave stochastically, choosing a random element of $\Theta'$ that may depend on $s\in S$ and $\theta\in \Theta$.

In this case <ref> must be changed to

\begin{equation}
\label{stochastic-heterogeneous-filtering}
\stringdiagram {
\wire (0,0) -- (11.5,0);
\ulabel{0,0}{\Theta};
\ulabel{11.5,0}{\Theta\sprime};
\blackdot{0.7,0};
\wire[3] (0.7,0) -- (0.7,3) -- (5,3);
\wire (6,2) -- (11.5,2);
\ulabel{11.5,2}{S};
\stoch{2.8,3}{$\psi_H\!$}{3};
\stoch{5.75,3}{$f$}{4};
\ulabel{4.2,3}{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] (5,4) -- (11.5,4);
\ulabel{11.5,4}{H};
% \showgrid
\, = \!
\pbox{
\stringdiagram {
\wire (0,0) -- (15,0);
\ulabel{0,0}{\Theta};
\ulabel{15,0}{\Theta\sprime};
\blackdot{0.7,0};
\wire[3] (0.7,0) -- (0.7,3) -- (5,3);
\wire (6,2) -- (15,2);
\ulabel{15,2}{S};
\stoch{2.8,3}{$\psi_H\!$}{3};
\stoch{5.75,3}{$f$}{4};
\ulabel{4.2,3}{H};
\wire[2] (5,4) -- (8,4);
\ulabel{7.4,4}{H\sprime};
\blackdot{8,4};
\stoch{9,0.25}{$\gamma$}{3};
\blackdot{7.3,2};
\ulabel{7.8,2}{S};
\wire[1.5] (7.3,2) -- (7.3,0.5) -- (9,0.5);
\wire[4] (10.5,0) -- (10.5,4) -- (15,4);
\blackdot{10.5,0};
\ulabel{11.3,0}{\Theta\sprime};
\stoch{13.2,4}{$\psi_{H\sprime}$}{3};
\ulabel{15,4}{H\sprime};
% \showgrid
\end{equation}

This is because if $\gamma$ is stochastic then there may be several different elements of $\Theta'$ that can result from giving passing values $\theta\in\Theta$ and $s\in S$ to $\gamma$.

<Ref> demands that each of these map to a valid conditional distribution over $H'$.

In a typical Bayesian filtering setup, we would demand that $H=H'$, $\Theta=\Theta'$ and $\psi_{H} = \psi_{H'}$.

That is, instead of having one family of distributions over $H$ and another over $H'$ we instead just have one family of distributions and update its parameters in response to data.

This allows the updating process to be iterated over a sequence of inputs.

However, before we consider that case, let us first consider a slightly different kind of iteration.

Suppose that in addition to the kernel
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};
we also have a kernel
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f'$}{2}
\rlabel{0,-3}{ T};
\rlabel{0,-1}{ \,\,H''};
\llabel{-4,-1}{ H'};
which we can interpret as the hidden system undergoing a second transition, changing stochastically to a new state in $H''$ and producing a second observable from a sample space $T$, which might in general be different from $S$.

Correspondingly, we can define a new parameter space $\Theta''$ and a new family of distributions

6,1   H”;
and a new update function
\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}{ T};
\llabel{0,1}{ \Theta'};
\rlabel{4,1}{ \,\,\,\Theta''};
obeying the analog of <ref>.or <ref> if we include stochastic updates.

We can see this either as two separate updates (one in response to an input in $S$ and another in response to an input in $T$), or we can see it as a single update in response to an input $(s,t)\in S\times T$, that is, an input consisting of sequence consisting of $s$ followed by $t$.

This gives us two different ways to write <ref>, and we might hope that these would be equivalent.

Indeed this is the case, and it has the interesting consequence that Bayesian filtering updates form a category.

Although this fact is somewhat technical and we do not use it extensively below, we state it as a proposition:

There is a category $\mathsf{Filt}$ of Bayesian filtering updates, in which
$(i)$ the objects are tuples $\left\langle \Theta, H, \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H$}{2}
\llabel{0,1}{\Theta};
\rlabel{4,1}{H};
consisting of two measurable spaces and a Markov kernel; $(ii)$ a morphism $\left\langle \Theta, H, \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H$}{2}
\llabel{0,1}{\Theta};
\rlabel{4,1}{H};
}\right\rangle \to \left\langle \Theta', H', \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_{H\sprime}$}{2}
\llabel{0,1}{\Theta'};
\rlabel{4,1}{H'};
}\right\rangle$ is an equivalence class of tuples $\left\langle S, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};
}, \!\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}{ \Theta};
\rlabel{4,1}{ \Theta'};
} \right\rangle$
that consist of a measurable space, a stochastic kernel and a deterministic kernel such that <ref> holds; and $(iii)$
given morphisms

$\left\langle S, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};
}, \!\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}{ \Theta};
\rlabel{4,1}{ \Theta'};
} \right\rangle$

$\left\langle T, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H'};
}, \!\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}{ T};
\llabel{0,1}{ \Theta'};
\rlabel{4,1}{ \Theta''};
} \right\rangle$,

their composition is given by the equivalence class containing the morphism
$\left\langle S\times T,
\!\stringdiagram{
\wire (0,-1)--(-7.5,-1);
\wire[0.5] (0,-2.5)--(-0.5,-2.5)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f'$}{2}
\wire[0.5] (0,-4)--(-3,-4)--(-4,-2)--(-5.5,-2);
\stoch{-5.5,-1.5}{$f$}{2}
\rlabel{0,-2.5}{ S};
\rlabel{0,-4.2}{ T};
\rlabel{0,-0.7}{ \,\,\,H''};
\llabel{-7.5,-1}{ H};
\wire (0,1)--(7.5,1);
\wire[0.5] (0,2.5)--(0.5,2.5)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma$}{2}
\wire[0.5] (0,4)--(3,4)--(4,2)--(5.5,2);
\sqbox{5.5,1.5}{$\gamma$}{2}
\llabel{0,2.5}{ T};
\llabel{0,4.2}{ S};
\llabel{0,0.7}{ \Theta};
\rlabel{7.5,1}{ \,\,\,\Theta''};
\right\rangle$.

The appropriate notion of equivalence is defined in the supplementary information.

Alternatively, $\mathsf{Filt}$ may be viewed as a bicategory, with 2-cells given by a generalisation of sufficient statistics.

The proof and further details are given in the supplementary information.

It is interesting to note that the category $\mathsf{Filt}$ has some similarity to the categories of lenses or optics that have previously been used to model Bayesian updates two of Toby's papers, as well as agents in a game-theoretic or control-theoretic context e.g. Bayesian open games, backprop as functor, towards foundations.

However, it is different in that $\mathsf{Filt}$ lacks the bidirectional quality of lenses and optics.

Its morphisms consist of pairs of morphisms of the underlying category, but both point in the same direction instead of one of them being reversed.

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.

Some steps have been taken in this direction recently cyber kittens, towards foundations, Translating Extensive Form Games to Open Games with Agency.

These works share a common theme with the present work, in that they identify a relationship between agency and parametrisation.

§.§ The category $\mathsf{Filt}$

Here we restate in more detail the definition of the category $\mathsf{Filt}$, in both its category form and its bicategory form.

As in the main paper, we assume we are working in a Markov category $\mathscr{C}$.

We use the term “space” or “measurable space” for objects of $\mathscr{C}$ and “Markov kernel” for morphisms of $\mathscr{C}$.

We start by defining a parametrised family of distributions.

These will be the objects of $\mathsf{Filt}$.

A parametrised family of distributions (or family) $X$ is a choice of measurable spaces $\Theta_{X}$ and $H_{X}$, together with a Markov kernel
\wire (-0.3,1)--(4.5,1);
\stoch{2,1}{$\psi_X$}{2}
\llabel{-0.3,1}{\Theta_X\,\,\,\,};
\rlabel{4.5,1}{\,\,\,\,H_X};

We then define a Bayesian filtering update between two parametrised families.

In the category version of $\mathsf{Filt}$ the morphisms of $\mathsf{Filt}$ will be equivalence classes of filtering updates.

In the bicategory version of $\mathsf{Filt}$, filtering updates will be the 1-cells.

Given parametrised families $X$ and $Y$, a Bayesian filtering update $u$ from $X$ to $Y$ is a choice of measurable space $S_u$, a Markov kernel
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};

temporary, just so I can copy and paste:

There is a category $\mathsf{Filt}$ of Bayesian filtering updates, in which
$(i)$ the objects are tuples $\left\langle \Theta, H, \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H$}{2}
\llabel{0,1}{\Theta};
\rlabel{4,1}{H};
consisting of two measurable spaces and a Markov kernel; $(ii)$ a morphism $\left\langle \Theta, H, \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_H$}{2}
\llabel{0,1}{\Theta};
\rlabel{4,1}{H};
}\right\rangle \to \left\langle \Theta', H', \!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\psi_{H\sprime}$}{2}
\llabel{0,1}{\Theta'};
\rlabel{4,1}{H'};
}\right\rangle$ is an equivalence class of tuples $\left\langle S, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};
}, \!\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}{ \Theta};
\rlabel{4,1}{ \Theta'};
} \right\rangle$
that consist of a measurable space, a stochastic kernel and a deterministic kernel such that <ref> holds; and $(iii)$
given morphisms

$\left\langle S, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H};
}, \!\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}{ \Theta};
\rlabel{4,1}{ \Theta'};
} \right\rangle$

$\left\langle T, \!\stringdiagram{
\wire (0,-1)--(-4,-1);
\wire[0.5] (0,-3)--(-0.5,-3)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f$}{2}
\rlabel{0,-3}{ S};
\rlabel{0,-1}{ H\sprime};
\llabel{-4,-1}{ H'};
}, \!\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}{ T};
\llabel{0,1}{ \Theta'};
\rlabel{4,1}{ \Theta''};
} \right\rangle$,

their composition is given by the equivalence class containing the morphism
$\left\langle S\times T,
\!\stringdiagram{
\wire (0,-1)--(-7.5,-1);
\wire[0.5] (0,-2.5)--(-0.5,-2.5)--(-1,-2)--(-2,-2);
\stoch{-2,-1.5}{$f'$}{2}
\wire[0.5] (0,-4)--(-3,-4)--(-4,-2)--(-5.5,-2);
\stoch{-5.5,-1.5}{$f$}{2}
\rlabel{0,-2.5}{ S};
\rlabel{0,-4.2}{ T};
\rlabel{0,-0.7}{ \,\,\,H''};
\llabel{-7.5,-1}{ H};
\wire (0,1)--(7.5,1);
\wire[0.5] (0,2.5)--(0.5,2.5)--(1,2)--(2,2);
\sqbox{2,1.5}{$\gamma$}{2}
\wire[0.5] (0,4)--(3,4)--(4,2)--(5.5,2);
\sqbox{5.5,1.5}{$\gamma$}{2}
\llabel{0,2.5}{ T};
\llabel{0,4.2}{ S};
\llabel{0,0.7}{ \Theta};
\rlabel{7.5,1}{ \,\,\,\Theta''};
\right\rangle$.

old version of this section. Probably just as good in the end, and the same length, but doesn't introduce $\psi_H$ as a Markov kernel

§.§ Interpretations and reasoners

some or all of this subsection could be moved to intro?

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

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

The idea is that an interpretation is a function that maps the physical state of a machine to some other mathematical object, which can be thought of as a set of possible beliefs about some external world.

In the case of Bayesian interpretations and Bayesian filtering interpretations, this object is the set of probability measures over some hidden variable.

An interpretation will also generally be required to satisfy some kind of consistency requirement.

In the case of Bayesian and Bayesian filtering interpretations, this consistency requirement is given by Bayes' theorem, as we explain below.

As we will show, not every machine can be consistently interpreted in every possible way; the existence of a non-trivial consistent interpretation can put strong constraints on the possible dynamics that a machine can have.

Given a machine $\gamma$ and a consistent interpretation, we will refer to the two together as a reasoner.

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.

Specifically, we can think of each state as corresponding to a probability distribution representing a subjective state of knowledge, and these distributions will update correctly as the machine receives new inputs.

As possible extensions of this idea, one can also imagine weaker kinds of consistency requirement, which might correspond to Jeffrey updating Jeffrey; see also Jacobs, or to approximate Bayes of some form, perhaps based on some form of the free energy principle.

One could also imagine applying these ideas to machines that have outputs as well as inputs, which might allow concepts such as goals, plans and actions to be formalised via the notion of interpretation, in addition to Bayesian beliefs.

However, we leave the development of these notions to future work, and focus here only on interpretations in terms of exact Bayesian inference and filtering.

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 “reasoner” unavoidably involves an element of choice in which interpretation to adopt.

I like the following paragraph but think it's a distraction

In string diagram notation, the update kernel can be written as $\!\!\!\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};
The fact that it is able to take sequences of inputs follows from its type: two copies of $\gamma$ can be composed in a particular way to form $\!\!\!\stringdiagram{
\wire (0,1)--(7.5,1);
\wire[0.5] (0,2.5)--(0.5,2.5)--(1,2)--(2,2);
\stoch{2,1.5}{$\gamma$}{2}
\wire[0.5] (0,4)--(3,4)--(4,2)--(5.5,2);
\stoch{5.5,1.5}{$\gamma$}{2}
\llabel{0,2.5}{ S};
\llabel{0,4.2}{ S};
\llabel{0,0.7}{ Y};
\rlabel{7.5,1}{ Y};
[-1cm]note to self: this is related to the Para construction, e.g. from “towards foundations of categorical cybernetics”, also a similar trick is used in “backprop as functor.” Not sure whether to cite these here as this is obviously way simpler.

This can be read as a kernel that takes a state $y\in Y$ and a sequence of two inputs in $S$, and returns another state in $Y$ stochastically, as a result of feeding the two inputs to the machine in sequence.

This generalises to sequences of any length.

(Some care must be taken over associativity but this can be done in a standard way.)

\begin{equation}
\label{jacobs-equation-b}
\stringdiagram {
\wire (0,0) -- (9,0);
\ulabel{0,0}{Y};
\ulabel{9,0}{H};
\ulabel{3.5,0}{H};
\blackdot{4,0};
\wire[2] (4,0) -- (4,2) -- (9,2);
\ulabel{9,2}{S};
\stoch{2,0}{$\psi$}{3};
\stoch{6.5,2}{$\phi$}{3};
% \showgrid
\, = \!
\pbox{
\stringdiagram {
\wire (0,0) -- (14,0);
\ulabel{0,0}{Y};
\ulabel{14,0}{H};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (14,2);
\ulabel{14,2}{S};
\stoch{3,2}{$\psi$}{3};
\ulabel{4.25,2}{H};
\stoch{5.5,2}{$\phi$}{3};
\sqbox{9,0}{$\gamma$}{3};
\blackdot{7,2};
\ulabel{7.5,2}{S};
\wire[1.5] (7,2) -- (7,0.5) -- (9,0.5);
\ulabel{10.3,0}{Y};
\stoch{11.5,0}{$\psi$}{3};
% \showgrid
\end{equation}

§ TECHNICAL PRELIMINARIES

I bet I can move most of this section to the SI once I've got the rest written.

In order to fill in some of the details sketched above, we introduce some concepts and notation that has been developed in the context of category theory
Fritz, Jacobs, ….

We present here only an informal sketch of the ideas. An introduction to category theory and the string diagram notation can be found in a short but accessible form in Baez and Stay or in a longer text-book format in Seven Sketches.

For a comprehensive technical exposition of their application to probability theory via so-called Markov categories, see Fritz, maybe also the representable Markov cats paper.

The framework has been used previously in a context related to Bayesian updates and the free energy principle Toby.

The central concepts are that of measurable space and of Markov kernel.

A measurable space is a set equipped with a $\sigma$-algebra.

The basic idea is that a measurable space is the kind of thing on which one can define a probability measure, but unlike a probability space it does not have any measure defined on it by default.

Often, but not always, we will take our measurable spaces to be finite sets, in which case we always take their $\sigma$-algebras to be their power sets.

In the supplementary information we give a formal definition of Markov kernels , along with the category-theoretic calculus we use to reason about them, aimed at readers without a category theory background.

However the basic idea is that for measurable spaces $X$ and $Y$, a Markov kernel $\kappa$ with source $X$ and target $Y$ is a function that maps elements of $X$ to probability measures over $Y$ (along with a technical requirement that this function be measurable in a certain sense).

Following Toby we write such a kernel as $\kappa\colon X\todot Y$, using the symbol $\todot$ to distinguish Markov kernels from ordinary functions.

Sometimes we will think of a Markov kernel as being an ordinary deterministic function that takes an element of $X$ and returns a probability distribution over $Y$.

However, we will also sometimes think of it as a stochastic function, which takes an element $x\in X$ and returns a randomly chosen element of $Y$, sampled according to a probability measure that might depend on $x$.

(These two interpretations can be distinguished formally using the machinery of representable Markov cats paper, but we will not make use of that here.)

We write $\kappa(y\mg x)$ to denote the probability that the kernel $\kappa$ assigns to the outcome $y\in Y$ when given the input $x\in X$.

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 $\kappa\colon X\todot Y$ the quantities $\kappa(y\mg x)$ are always defined, regardless of whether any probability distribution has been defined over $X$, and regardless of whether $x$ has a nonzero probability according to such a distribution.

(In fact, with a little care this same notation can be used even in the general measure-theoretic case, where $X$ and $Y$ are not necessarily finite Fritz, section 2.8.

In this case $x$ and $y$ are interpreted as abstract indices rather than elements of $X$ and $Y$.)

two short paragraphs that mention composition and joint distributions, referring to the SI for more details

I'm entering some introductory stuff about string diagrams here, just to try and see if this will work. Nothing in this document yet is final - I'm still unsure of the form the paper will take.

my conclusion: this might have to go in the supplementary material - it could be made a bit shorter but I think most of the points here have to be said in one form or another for it to make sense. Or we just give references and don't explain it.

A measurable space is a set equipped with a $\sigma$-algebra, or formally a tuple $(X,\Sigma)$, where $X$ is a set and $\Sigma\subseteq \mathcal{P}(X)$ is a set of subsets of $X$ that obeys the axioms of a $\sigma$-algebra.

Often, but not always, our measurable spaces will be finite sets, in which case we will always assume $\Sigma=\mathcal{P}(X)$.

Given two measurable spaces $X$ and $Y$, a Markov kernel, which we write $f\colon X\todot Y$, is a measurable function $f\colon X\to P(Y)$, where $P(Y)$ is the space of probability distributions over $Y$, which is itself a measurable space.

We first introduce the framework in the case of finite probability, and then outline how it generalises to a more general measure-theoretic context that includes continuous probability.

We will make use of the more general version later on.

For now, let $X, Y, Z\dots$ represent finite sets. Given a finite set $X$, we write $P(X)$ for the set of all probability distributions over $X$.

In this finite case, $P(X)$ may be thought of as a $(|X|-1)$-dimensional simplex, given by the set of vectors in $\mathbb{R}^{|X|}$ whose components are nonnegative and sum to 1.

Given finite sets $X$ and $Y$, a Markov kernel $f\colon X\todot Y$ is defined as a function $f\colon X\to P(Y)$.

The kernel $f$ can be thought of as a set of probability distributions over $Y$, parametrised by elements of $X$.

Alternatively, it may be thought of as a stochastic function, that is, something that takes an input in the underlying set of $X$ and then produces an output in $Y$, chosen randomly according to a distribution that depends on $X$.

(A formal distinction between these interpretations can be made using the machinery of representable Markov cats, but we will not make use of that here.)

In the finite case $f$ may also be thought of as a stochastic matrix (i.e. one whose entries are nonnegative and whose columns sum to 1), representing a linear map that maps distributions over $X$ to distributions over $Y$.

Following Toby we use the symbol $\todot$ to distinguish Markov kernels from ordinary functions.

We write $f(y\mg x)$ to denote the probability that the kernel $f$ assigns to the outcome $y\in Y$ when given the input $x\in X$.

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 X\todot Y$ the quantities $f(y\mg x)$ are always defined, regardless of whether any probability distribution has been defined over $X$, and regardless of whether $x$ has a nonzero probability according to such a distribution.

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

Given Markov kernels $f\colon X\todot Y$ and $g\colon Y\todot Z$, we can compose them to form a new kernel of type $X\todot Z$, which we write $f\comp g$, given by

\begin{equation}
(f\comp g)(z\mg x) = \sum_{y\in Y} f(x\mg y)\,g(y\mg z),
\end{equation}

which is a discrete version of the Chapman-Kolmogorov equation.

There are two important special cases of Markov kernels that have special notation.

The first is that for every finite set $X$ there is a kernel $\id_X\colon X\to X$ corresponding to the identity matrix, which simply returns

The second important special case is a Markov kernel $p\colon \one \to X$, where $\one = \{\star\}$ is a set with a single element.

(The identity of the element does not matter.)

In this case the kernel $p$ can be defined by choosing a single probability distribution over $X$, which is the kernel's output when given its only possible input.

In fact we think of distributions over $X$ and kernels of type $\one\to X$ as the same thing, and we write $p(x)$ rather than $p(x\mg \star)$.

(Note that the symbol $p$ here refers to the name of the kernel, rather than being a generic symbol for probability.)

We also use a notation called string diagrams for Markov kernels. String diagrams can be applied to a much wider range of mathematical topics than probability

(Baez+Stay is a good overview of some other applications).

Here we present them only in the context of Markov kernels, as used by Cho+Jacobs, Fritz.

We choose to orient our diagrams horizontally and generally write kernels with curved edges.

In general, in our context, every string diagram represents a Markov kernel, which might be built up out of other Markov kernels.

We denote a kernel $f\colon X\todot Y$ by the diagram $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$f$}{2}
\llabel{0,1}{X};
\rlabel{4,1}{Y};

Each wire represents a finite set. Composition via the Chapman-Kolmogorov equation is written as

\begin{equation}
\stringdiagram {
\wire (0,0) -- (4,0);
\stoch{2,0}{$f\comp g$}{3};
\ulabel{0,0}{A};
\ulabel{4,0}{C};
\,=\,
\pbox{\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}

Here each side of the equation represents a Markov kernel and we are asserting that the two kernels are equal.

For this to make sense, the types have to match, meaning that the “dangling wires” on each side of the two diagrams must match.

As a special case, we write a one-element set as no wire, so that a probability distribution over $X$ (that is, a kernel $p\colon \one\to X$) is written simply as $\!\stringdiagram{
\wire (2,1)--(4,1);
\stoch{2,1}{$p$}{2}
\rlabel{4,1}{X};

String diagrams come into their own when we consider joint distributions.

For example, we might want to consider a function $h\colon A\times B\to P(C\times D)$, which we write as a Markov kernel $h\colon A\otimes B\todot C\otimes D$.

Here $A\otimes B$ and $B\otimes C$ represent the spaces of probability distributions over $A\times B$ and $C\times D$.

We write such spaces of joint distributions as pairs of parallel wires, so that the kernel

Two central concepts are measurable spaces and Markov kernels. A measurable space is a set equipped with a $\sigma$-algebra. This is a similar concept to a measure space or a probability space, but without a specified measure defined on it.  Given a measurable space $X$, we write $P(X)$ for the set of all probability measures over $X$. In fact $P(X)$ itself can be made into a measurable space. We will often consider the case where a measurable space is a finite set, in which case we will always assume its associated $\sigma$-algebra is its power set.

Given measurable spaces $X$ and $Y$, a Markov kernel $f\colon X\todot Y$ can be defined as a measurable function $f\colon X\to P(Y)$. That is, $f$ can be thought of as a set of probability distributions over $Y$, parametrised by elements of $X$. Alternatively, it may be thought of as a stochastic function, that is, something that takes an input in the underlying set of $X$ and then produces an output in $Y$, chosen randomly according to a distribution that depends on $X$. Following Toby we use the symbol $\todot$ to distinguish Markov kernels from ordinary functions.

equations for the DE machine version

I am thinking there should be an introduction to Jacobs' version of conjugate priors before this. It would basically note that the update function already looks kind of like a machine, but it would note that there's a couple of issues: first we need the update function to be deterministic otherwise it doesn't work (for the reasons we discussed), and second Jacobs' equation says nothing about what the machine should do in the case of subjectively impossible inputs. The text would explain roughly why that's a problem. So we motivate the definitions below by saying they exist to solve those issues.

Given a measurable space $S$, an $S$-machine is a tuple $(M,\mu)$, consisting of a measurable space $M$, together with a Markov kernel of type $\mu\colon M\otimes S\todot M$. The set $M$ is called the state space of the machine, and $\mu$ is called its update kernel.

We can write the update kernel in string diagrams as $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\mu$}{2}
\llabel{0,3}{ S};
\llabel{0,1}{ M};
\rlabel{4,1}{ M};

Often we will refer to a machine $(M,\mu)$ by its update kernel $\mu$, leaving the state space implicit.

The intuition is that a machine can start in a state $m\in M$ and receive an input $s\in S$, and as a result change its state to some other $m'\in M$.

This next state may be chosen stochastically, and in general will depend on both the previous state and the input.

The process of receiving inputs can be iterated.

For example, the following diagram represents a kernel of type $M\otimes(S\otimes S\otimes S)\todot M$ formed by composing three copies of $\mu$.

It can be thought of as receiving a string of three inputs and outputting the resulting state.
can restructure to remove this diagram if we need to save space

\begin{equation*}
\stringdiagram{
\wire (0,1)--(10,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\mu$}{3}
\wire[1] (0,4) -- (2,4) --(4,2)--(5,2);
\stoch{5,1.5}{$\mu$}{3}
\wire[1] (0,5) -- (4,5) --(7,2)--(8,2);
\stoch{8,1.5}{$\mu$}{3}
\llabel{0,3}{S};
\llabel{0,4}{S};
\llabel{0,5}{S};
\llabel{0,1}{M};
\rlabel{10,1}{ M};
\dlabel{3.5,1}{ M};
\dlabel{6.5,1}{ M};
\end{equation*}

It is worth noting that the notion of a machine plays two roles in our work: sometimes a machine will represent a physical system, whose state space and input space are interpreted physically, with its update function modelling its true physical dynamics.

However, machines will also sometimes play a more abstract role in our definitions, and not every machine we define will necessarily exist as a physical system.

Given an $S$-machine $(M,\mu)$ and a $T$-machine $(N,\nu)$, a map of machines $f\colon \mu\to\nu$ consists of two deterministic kernels, $f_\textnormal{state}\colon M\to N$ and $f_\textnormal{input}\colon S\to T$, such that

\begin{equation}
\stringdiagram{
\wire (-4,1)--(4,1);
\wire (-4,3)--(0,3);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\nu$}{3}
\sqbox{-1.6,0.8}{$f_\textnormal{state}$}{3}
\sqbox{-1.6,3.3}{$f_\textnormal{input}$}{3}
\llabel{-4,3}{S};
\llabel{-4,1}{M};
\dlabel{0.4,1}{N};
\ulabel{0.4,3}{T};
\rlabel{4,1}{N};
\pbox{\stringdiagram{
\wire (0,1)--(7.25,1);
\wire[0.5] (0,3)--(0.5,3)--(1,2)--(2,2);
\stoch{2,1.5}{$\mu$}{3}
\sqbox{5,1.5}{$f_\textnormal{state}$}{3}
\llabel{0,3}{S};
\llabel{0,1}{M};
\dlabel{3.25,1}{M};
\rlabel{7.25,1}{N};
\end{equation}

If both of the functions $f_\text{state}$ and $f_\text{input}$ are surjective we say $f$ is a surjective map of machines.

Similarly, if both of the underlying functions $f_\text{state}$ and $f_\text{input}$ are injective we say $f$ is an injective map of machines.

if needed, we can define “isomorphism,” “isomorphic,” and “identity-on-$S$ map” here as well.

To get an intuition for the concept it is helpful to consider the surjective case first.

In this case, the functions $f_\text{input}$ and $f_\text{state}$ can be seen as coarse-graining the input space and the state space, in such a way that the dynamics are preserved.

That is, coarse-graining the state and input followed by an update of $\nu$ must be the same as first performing an update of $\mu$ and then coarse-graining the state space.

This is a similar concept to so-called lumpability of Markov processes.

The definition also demands that $\nu$ itself be a machine, which is an extra condition not implied by the lumpability condition itself.

(See the paper Martin recommended for an explanation of this point, in relation to Markov processes rather than machines.)
[-2cm]to discuss with Martin: what's the one-sentence way to correctly explain what this definition amounts to, in terms of that paper?

This intuition is probably helpful but can be removed to save space (except for the last sentence of this paragraph)
We can also consider the case of an injective map of machines $f\colon \mu\to \nu$.

In this case we can think of $\mu$ as a kind of “sub-machine” of $\nu$, in that the states in $M$ correspond to a subset of the states in $N$, and similarly $S$ corresponds to a subset of $T$.

The condition in <ref> ensures that these sets embed into $\nu$ in such a way that the dynamics are preserved, meaning in this case that if $\nu$ starts in a state corresponding to a state in $M$, and if it only receives inputs corresponding to inputs in $S$, then it will behave exactly like the machine $\mu$.

In general a map of machines need not be surjective or injective, meaning that some states in $M$ and $S$ may be coarse-grained, while some states in $T$ and $N$ might have no states that map to them.

Martin, feel free to ignore anything below this point - you can write the into however you like, it doesn't have to join up to this.

Although ultimately our goal is to understand agents in a much broader sense, we restrict ourselves here to the following very simple scenario, which is a generalisation of the one considered in Biehl and Kanai.

We consider a physical system that receives a stream of inputs.

The system is modelled as a Markov process that takes inputsis there a standard term for “Markov process that takes inputs”?, meaning that at each time step its next state is determined stochastically as a function of both its previous state and the input received.

The question we ask is, given such a system, can that system be consistently interpreted as performing exact Bayesian inference about some hidden variable?, and if it can, how many such interpretations are possible?

The latter question might at first sound surprising, but we will show in a proposition that if one non-trivial such interpretation exists then so do an infinite set of alternatives.

We will show that the requirement of consistency puts fairly strong constraints on the physical systems that can be interpreted as performing inference.

It should be noted however, that the condition of being able to perform exact inference on arbitrarily long sequences of inputs is quite a restrictive one, and one could certainly consider weaker forms of interpretation.

We focus on exact inference as a kind of case study, in order to elucidate the relationship of mutual constraint between the dynamical properties of a physical system and its interpretations as an agent performing inference.

By an “interpretation,” in this particular restricted case, we mean a function that maps the system's internal state to a space of probability distributions, which we think of as representing the agent's subjective beliefs about some hidden variable $H$.

The hidden variable may or may not in fact correspond to something that exists in the physical world:
we do not demand that the agent's beliefs be true, but only that they be consistent.

I'm removing the original content of the template, but it can be found at the bottom of the .tex file, after the end document command.

After quite a bit of work I was able to fit Simon's equation on a single line — see below. Hopefully future equations will be less work, but at least currently I have to manually position each element of the diagram, so it takes a while to enter them and get them to look nice.

Inline string diagrams are possible but it's not really feasible to convey much information. For example, we can say $\!\!\!\stringdiagram{
\wire (0,1)--(4,1);
\stoch{2,1}{$\iota$}{2}
\llabel{0,1}{M};
\rlabel{4,1}{S};
} = \!\!\!\stringdiagram{
\wire (0,1)--(6,1);
\stoch{1.75,1}{$\psi$}{2}
\stoch{4.25,1}{$\phi$}{2}
\llabel{0,1}{M};
\rlabel{6,1}{S};
but there isn't really even enough space to fit an $H$ label on the intermediate wire, without increasing the height of the equation above the height of a normal line. So probably we won't want to use inline diagrams in this paper. (It works better if you only have dots and wires.)

We require the interpretation map $M\xklto{\psi} H$ and the agent's model  $H\xklto{\phi} S$ to obey the following consistency equation:

\begin{equation}
\stringdiagram {
\wire (0,0) -- (11.5,0);
\ulabel{0,0}{M};
\ulabel{11.5,0}{M};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (11.5,2);
\ulabel{11.5,2}{S};
\stoch{3,2}{$\psi$}{3};
\stoch{6,2}{$\phi$}{3};
\blackdot{4.5,2};
\ddlabel{4.5,2}{H};
\stoch{9.5,0.25}{$\mu$}{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}{M};
\ulabel{15,0}{M};
\blackdot{1,0};
\wire[2] (1,0) -- (1,2) -- (15,2);
\ulabel{15,2}{S};
\stoch{3,2}{$\psi$}{3};
\ulabel{4.25,2}{H};
\stoch{5.5,2}{$\phi$}{3};
\stoch{9,0.25}{$\mu$}{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}{M};
\stoch{13.2,4}{$\psi$}{3};
\ulabel{15,4}{H};
% \showgrid
\end{equation}

This says that …

The following is copied-and-pasted from elsewhere - the notation will need to be changed (the rest to match this, or this to match the rest).

We build on the formal definition of conjugate priors given by Jacobs, which we sketch here, using the language of string diagrams.

In this graphical notation, we write a Markov kernel $f\colon X\todot Y$ as

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

This should be thought of as a function that maps elements $x\in X$ to probability distributions over $Y$.

We can use Markov kernels to model either physical processes (in which case we interpret $X$ as the space of possible inputs and $Y$ as the space of possible outputs) or statistical models, in which case we regard $X$ as the set of possible parameter values and $Y$ as the sample space.

The Markov category framework provides various ways to compose Markov kernels together, either in series (which can be thought of as feeding the output of one process into the input of another), or in parallel, which can be thought of in terms of two processes operating on separate variables independently.

Jacobs' definition of a conjugate prior may be stated within this framework.

Let $q\colon\Theta\todot X$ be a statistical model with parameter space $\Theta$ and sample space $X$.

We say that $q$ admits a conjugate prior if there exists $(i)$ another statistical model $p\colon\Psi\to\Theta$, whose sample space is $\Theta$, and a deterministic function $h\colon \Psi\times X\to \Psi$, such thatThis equation can be made vertically smaller by laying it out in the style of <ref>. Then it will only be 2 units high, not 3.

\begin{equation}
\label{conjugate-prior-def}
\stringdiagram{
\wire(0,0) -- (3.5,0);
\stoch{2,0}{$p$}{3};
\ulabel{0,0}{\Psi};
\rlabel{3.8,0}{\Theta};
\blackdot{3.5,0};
\wire[2.5] (3.5,0) -- (3.5,2.5) -- (7.5,2.5);
\ulabel{7.5,2.5}{X};
\stoch{5.75,2.5}{$q$}{3};
\wire[2.5] (3.5,0) -- (3.5,-2.5) -- (7.5,-2.5);
\ulabel{7.5,-2.5}{\Theta};
\pbox{
\stringdiagram{
\wire(-3,0) -- (3.5,0);
\stoch{-0.3,0}{$p$}{3};
\ulabel{0.9,0}{\Theta};
\stoch{2.1,0}{$q$}{3};
\ulabel{-3,0}{\Psi};
%	\uulabel{-2,0.1}{\Psi};
\blackdot{-2,0};
\wire[2.5] (-2,0) -- (-2,-2.8) -- (5.75,-2.8);
\rlabel{3.8,0}{X};
\blackdot{3.5,0};
\wire[2.5] (3.5,0) -- (3.5,2.5) -- (10,2.5);
\ulabel{10,2.5}{X};
\wire[2.2] (3.5,0) -- (3.5,-2.2) -- (5.75,-2.2);
\wire(5.75,-2.5) -- (10,-2.5);
\sqbox{5.75,-2.5}{$h$}{3};
\ulabel{7,-2.5}{\Psi};
\stoch{8.2,-2.5}{$p$}{3};
\ulabel{10,-2.5}{\Theta};
\end{equation}

The parameters $\psi\in\Psi$ of $p$ are called the hyperparameters.

The function $h$ takes the value of the hyperparameters along with a sample from $X$ and returns the updated value of the hyperparameters.

The equation expressed in string diagrams ensures that the behaviour of these functions is consistent with Bayesian inference.

The model of Biehl and Kanai may be expressed in this framework by interpreting Equation <ref> differently.

We regard $\Psi$ as the agent's physical state and $h$ as the function that updates it according to its observations $X$.

We interpret $q$ as the agent's model of $X$, and $p$ as the interpretation map, sending its internal state to a distribution over model parameters.

Only $\Psi$, $h$ and the observations $X$ are part of the physical system.

The other Markov kernels constitute the interpretation map, with $\Theta$ being a hidden variable in the agent's assumed model.

Seen this way the equation above can be seen as the defining equation for an interpretation map, for an agent that performs exact inference.

§ OLD INTRO

A question of general interest that also plays a central role in the Free Energy Principle (FEP) is which systems are performing Bayesian inference.

More precisely, what are the necessary and sufficient conditions under which it is justified to say that a system performs Bayesian inference.

This question is of general interest by itself because Bayesian inference is in some sense the optimal way to reason about uncertain events cox which makes systems (including biological ones) performing Bayesian inference special bayes in biology.

This question is also of interest as part of the broader question of which systems are intelligent since Bayesian inference plays an important role in current theories of intelligence and rationality.

The Free Energy Principle itself may be seen as a theory of intelligence that relies on Bayesian inference but it is not the only one <cit.>.

We now give some informal motivation for our proposal to answer this question. Readers mainly interested in formal development may skip ahead to refer.

§.§ Bayesian inference

Briefly, Bayesian inference is a prescription for how to update probabilistic beliefs about hypothetical causes of observations in response to such observations.

The set of hypothetical causes is represented by a family of distributions or a (statistical) model which we will informally write as $\phi(s \mg h)$.

Here $h \in H$ are hypotheses or parameters in parameter space $H$ and $s \in S$ are observations in observation space $S$.

Note that the parameterized model is often called the likelihood function and written in the style of a conditional probability $p(s|h)$ and sometimes as $p(s;h)$.

In order to keep the exposition in this introduction accessible we avoid measure theoretic notions and consider probabilistic beliefs as probability mass functions in the discrete case and probability density functions in the continuous case.

When there is no need to distinguish them we will refer to both as probability distributions.

Bayesian inference then takes a probability distribution (the prior belief) over $H$ and an observation $s \in S$ and transforms them into a new probability distribution (the posterior belief) over $H$.

This is a new attempt. Make Bayesian inference about updating probability distributions instead of measures. Then the things that are updated by the well known form of Bayes rule are not necessarily parameterizations. The other way would be to use probability measures and Bayes rule for probability measures, but only really technical people would get that...

Importantly, this transformation (and therefore Bayesian inference) is only well defined if we specify the model $\phi(s \mg h)$ whose parameters the belief ranges over.

A complicating issue is that even if a model is defined, Bayesian inference may not specify a posterior belief for every prior belief.

We will discuss this issue in the technical part refer but in this introduction we only consider the case where every prior is transformed to a unique posterior for every observation.

Next we want to consider what it could mean that a system performs Bayesian inference.

To some degree this depends on what we consider systems to be.

So we discuss this first.

§.§ Systems

For the purpose of this paper a system is a triple $\langle Y,S,\gamma\rangle$ consisting of a state space $Y$, an input space $S$, and transformation $\gamma$ that takes a state and an input and transforms them into a new state.

In this introduction we will assume that $\gamma$ is deterministic but the formal treatment works for stochastic systems as well.

Many examples of such systems are known to exist (in the mathematical sense) because they are formally defined, i.e. state space, input space, and transformation are all given in some formal language (e.g. ZFC set theory).

I am not sure that “ZFC set theory” is really a possible formal language in which all of these things can be unambiguously defined, I am pretty sure in some way it is possible.

For example, let $Y=\{0,1,2\}$, $S=\{0,1\}$, and $\gamma(y,s) \coloneqq y+s \mod 3$.

We assume that there are also parts of the physical world that are systems of this kind.

These are what we refer to as physical systems.

For example the state space may be the possible configurations of a set of degrees of freedom of some physical matter and the input space may be the set of possible configurations of a disjoint set of degrees of freedom.

[There may be other ways in which parts of the physical world forms systems of the kind we study here.]

All degrees of freedom evolve under the laws of physics with the time evolution of the state space degrees of freedom possibly depending on the input degrees of freedom.

The input dependent time evolution of the state space degrees of freedom then induces and thereby defines the transformation of such a physical system.

An important fact about systems in general is that even though two systems may have different state spaces and input spaces (which also means their transformations are different) they can still be isomorphic.

Intuitively this just means that they “behave” in the same way.

This will be explained below refer.

A simple example of a system that is isomorphic to the example above is $Y=\{0,-1,-2\}$, $S=\{0,-1\}$, and $\gamma(y,s) \coloneqq -y-s \mod 3$.

Note that among the formally defined systems there are some that were constructed specifically to model physical systems.

Note also that for some physical systems an isomorphic formal system may, by accident or due to somebodies skill, have already been defined.

With a better idea of what we mean by systems we now discuss which ones should count as performing Bayesian inference.

§.§ Systems that should count as performing Bayesian inference

As mentioned before belief updating according to Bayesian inference is only defined with respect to a model.

This means that the question of whether a system performs Bayesian inference is formulated more precisely as whether there exists a model with respect to which a system is performing Bayesian inference.

One thing we require from the model is that its observation space is equal to the system's input space.

The question is then when a system performs Bayesian inference with respect to a model of its inputs.

Note that it is straightforward to (formally) construct a system that performs Bayesian inference with respect to a model of its inputs.

At the very least it should be justified to say that such a system performs Bayesian inference.

To construct such a system we start by defining a model $\phi(s\mg h)$ together with its parameter space $H$ and observation space $S$.

The input space of the constructed system is defined as the observation space of the model.

We can then construct the space of all probability distributions (beliefs) over parameter space $H$.

[To make sure all posteriors are well defined we only allow beliefs that assign positive probability to all parameters.]

This forms the states space $Y$ of the constructed system.

Any pair $(y,s)$ of state and input is now also a pair of a probability distribution over parameters of a model (a possible prior) and an observation such that we can use Bayes rule to obtain a new probability distribution $\gamma(y,s)$, the posterior.

This completes the construction of a system that performs Bayesian inference.

For example we can choose a model for binary observations $S \coloneqq \{0,1\}$ (or equivalently $\{\text{heads},\text{tails}\}$) the family of probability distributions $\phi(s \mg h)$

\begin{align}
\phi(s \mg h) \coloneqq  h^{\delta_0(s)} (1-h)^{\delta_1(s)}
\end{align}

where $h \in H$ and $H \coloneqq [0,1]$.

This is equivalent to considering $H$ as a set of hypothetical biases that could be causing the outcomes of a coin flip.

For the state space $Y$ we can choose the set of positive probability density functions over $H$.

We can then define the transformation $\gamma(y,s)$ via Bayes rule:

\begin{align}
\gamma(y,s)(h) \coloneqq  \frac{\phi(s \mg h)y(h)}{\int \phi(s \mg \bar{h})y(\bar{h}) d\bar{h}}.
\end{align}

The result of $\gamma(y,s)$ is again a positive probability density function over $H$ and therefore an element of $Y$ for all $(y,s) \in Y\times S$.$\gamma$ isn't a Markov kernel in this case, for that we would need a distribution over $Y$ on the r.h.s. not just an element of $Y$. This could be done using a Dirac delta, but it would be nice to avoid it. Maybe it needs a short note.

However, apart from systems directly constructed to perfrom Bayesian inference there are three other classes of systems that we also consider to be performing Bayesian inference.

* Systems that implement Bayesian inference in a (hyper-) parameter space.

It is well known that certain statistical models have associated parameterized conjugate priors.

In this case Bayesian inference can be, and in practice often is, implemented completely in some parameter space.

This parameter space need not be isomorphic to any space of probability distributions and is often a low dimensional real space $\mathbb{R}^n$.

Maybe point to, or quickly describe an example with conjugate prior here.

Let us explain a bit more how parameterized conjugate priors allow Bayesian inference in parameter space.

The first thing to note is that for some models there are subsets of probability distributions (beliefs) over the model parameters that are closed under Bayesian updates.

This just means that if we start with a prior measure from such a subset then the posterior measure for any observation will always be in this subset again.

Often these subsets of probability distributions can be conveniently parameterized.

A set $C$ of probability distributions is parameterized by a set $D$ (not necessarily containing probability distributions and often some $\mathbb{R}^n$) if there is a bijective function $f:D \to C$.

Note that parameters of beliefs are sometimes called hyperparameters to distinguish them from the model parameters.

Let's assume we have a model that has such a closed subset $C$ of probability distributions over its parameters and is parameterized by some set $D$ of hyperparameters.

Let $f(d) \in C$ denote the probability distribution associated to hyperparameter $d \in D$ and write $f(d)(h)$ for the probability assigned to parameter/hypothesis $h \in H$ by $f(d)$.

If we then pick an arbitrary observation $s \in S$ and hyperparameter $d \in D$ we can take the belief $f(d)$ it parameterized and use Bayes rule to update it with respect to the observation $s$ to get a posterior belief $p \in C$ which is also in $C$ since $C$ is closed:

\begin{align}
\label{eq:hyperbayes}
p(h)=\frac{\phi(s \mg h)f(d)(h)}{\int \phi(s \mg \bar{h})f(d)(\bar{h}) d\bar{h}}.
\end{align}

Since $f$ is bijective we can then use its inverse to find the hyperparameter $d' \coloneqq f^{-1}(p) \in D$ of the posterior.

We can therefore define a function $\alpha(d,s)$ mapping the hyperparameter of any prior belief $f(d) \in C$ and observations $s \in S$ to the hyperparameter $d'$ of the posterior belief $f(d')=p$.

\begin{align}
\alpha(d,s) \coloneqq f^{-1}\left(\frac{\phi(s \mg h)f(d)(h)}{\int \phi(s \mg \bar{h})f(d)(\bar{h}) d\bar{h}}\right).
\end{align}

This is what we mean by implementing Bayesian inference in a (hyper)parameter space.

Note that $\alpha(d,s)$ is then also the transformation of a system whose state space is $D$ and input space is $S$.

Systems of this kind should also be considered as systems performing Bayesian inference.

* Systems where only a part performs Bayesian inference.

For example if one component of the system's state space are parameters whose dynamics implement Bayesian inference with respect to the input but another component of the system does something else. Example?

* Systems that are isomorphic to a system that performs Bayesian inference.

Note that this means that if some formal system performs Bayesian inference and is isomorphic to some physical system then we can also say that the physical system performs Bayesian inference.

The necessary and sufficient condition that we propose to identify systems that perform Bayesian inference is satsified by these three classes of systems.I guess ideally we would also know that it is satisfied by only those classes, but I don't think we can or necessarily need to. Next we give the main idea behind that condition.

§.§ Condition for systems to perform Bayesian inference

We now introduce the main idea behind the proposed formal condition (see refer) under which a system performs Bayesian inference with respect to given model.

This also leads to a condition under which a system performs Bayesian inference in general.

The condition is in form of a consistency requirement or equation that has to be satisfied between the system's transformation and Bayesian belief updating with respect to the model.

Recall that in the case of parameterized conjugate priors there was a bijective function $f$ that mapped hyperparameters to beliefs about the model parameters $H$.

In that case we constructed the transformation of the system that implemented Bayesian inference by using Bayes rule <ref>.

In the case of a given system $\langle Y,S,\gamma\rangle$ we require the existence of a (not necessarily bijective) function, which we call the interpretation map $g$, from system states $y \in Y$ to beliefs $g(y)$ about the model parameters $h \in H$ that is “consistent with Bayes rule”.

This means, the belief $g(\gamma(y,s))$ associated to the new state $\gamma(y,s)$ must be the posterior belief obtained by considering belief $g(y)$ associated to old state $y$ as the prior belief, input $s$ as the observation, $\phi(s \mg h)$ as the model and applying Bayes rule.

More formally, a (deterministic) system $\langle Y,S,\gamma\rangle$, performs Bayesian inference with respect to model $\phi(s \mg h)$ if and only if there exists a function $g$ such that for all $y \in Y,s \in S$:

\begin{align}
g(\gamma(y,s))(h) = \frac{\phi(s \mg h) g(y)(h)}{\int \phi(s \mg \bar{h}) g(y)(\bar{h}) d\bar{h}}
\end{align}

The dynamics of hyperparameters of conjugate priors obey this condition with the interpretation function being the bijective function $f$.

Systems where a only part of the system state is involved in Bayesian inference also satisfy this condition since the interpretation function can just ignore the rest of the system state.

Note that the condition is also satisfied when the state space consists of probability distributions directly and the dynamics of the system are identical to Bayesian inference.

In that case a possible interpretation function is just the identity.

Finally, if two systems are isomorphic and the first of them obeys the condition, the second does so as well.

In this case we can construct the interpretation map of the second system by composing the bijective function that exists between isomorphic systems with the interpretation function of the first system.

To be continued...