# A General Relationship between Optimality Criteria and Connectivity Indices
for Active Graph-SLAM

Julio A. Placed, and José A. Castellanos The authors are with the Instituto de
Investigación en Ingeniería de Aragón (I3A), Universidad de Zaragoza, C/María
de Luna 1, 50018, Zaragoza, Spain e-mail<EMAIL_ADDRESS>
###### Abstract

Quantifying uncertainty is a key stage in active simultaneous localization and
mapping (SLAM), as it allows to identify the most informative actions to
execute. However, dealing with full covariance or even Fisher information
matrices (FIMs) is computationally heavy and easily becomes intractable for
online systems. In this work, we study the paradigm of active graph-SLAM
formulated over SE(n), and propose a general relationship between the FIM of
the system and the Laplacian matrix of the underlying pose-graph. This link
makes possible to use graph connectivity indices as utility functions with
optimality guarantees, since they approximate the well-known optimality
criteria that stem from optimal design theory. Experimental validation
demonstrates that the proposed method leads to equivalent decisions for active
SLAM in a fraction of the time.

##  I Introduction

Autonomous exploration of unknown environments has long attracted the
attention of the robotics community and despite being essential for achieving
high-level autonomy in numerous applications (e.g., search and rescue), it
still remains an open problem. Mainly, it involves planning and navigating
under uncertainty, thus making necessary to have a model of the surrounding
environment.

Simultaneous Localization and Mapping (SLAM) passively deals with the base
problem of incrementally building a map of the environment while at the same
time locating the robot on it. Many approaches have been developed to solve
it, although the interest of this paper particularly lies on (pose) graph-SLAM
methods, that intuitively formulate the problem using a graph representation
where nodes encode the robot poses, and edges encode the constraints between
them. This SLAM variant is built on the idea that the map representation can
be retrieved once the robot states have been properly estimated [1]. After
solving the data association and building the graph, it all comes down to
finding the optimal nodal configuration via maximum likelihood (ML), i.e.,
finding the set of robot poses that minimizes a cost function of the
observations. See [1, 2, 3] and the references there in.

Active SLAM expands the previous problem so as to include the selection of the
actions the robot should execute to build the best model of the environment
possible. This new decision-making problem, erected on active perception [4],
can be formally defined as the control of a robot that is performing SLAM with
the objective of reducing the uncertainty of its location and of the map
representation. Given the probabilistic nature of SLAM, the above involves
reasoning over probabilistic states (i.e., _beliefs_) under uncertainty, a
problem also referred to in the literature as belief space planning (BSP) [5].
Active SLAM has been traditionally divided in three phases for the ease of its
resolution [6]:

  1. i)

the identification of possible locations to explore,

  2. ii)

the evaluation of the utility associated to the actions that would take the
robot from its current position to each of those locations, and

  3. iii)

the selection and execution of the optimal actions.

In the first stage, actions to reach all possible locations should be
evaluated, although easily proves to be intractable due to the dimensionality
of the state and action spaces. In practice, the most common approach is the
identification of the points which lie between the known and unknown regions
of the map, i.e., frontiers. During the second step, the utility of each set
of actions is estimated by quantifying the expected uncertainty in the two
target random variables: the robot location and the map. Uncertainty
quantification can be based either on theory of optimal experimental design
(TOED) [7] or information theory (IT) [8], although it is the former on which
this letter focuses. Either way, these utility functions must find the
equilibrium between exploring new areas and exploiting those previously seen
(i.e., the so called _exploration-exploitation dilemma_). Finally, third phase
consists in executing the set of actions with highest utility.

TOED-based utility functions, or _optimality criteria_ directly map the
expected covariance matrices to the real scalar space through their
eigenvalues. However, the use (i.e., propagation, store and analysis) of these
dense matrices quickly becomes intractable in online active SLAM. For example,
approaches that require computing the determinant of the a posteriori
covariance matrix are $\mathcal{O}(n^{3})$ complex in general, with $n$ the
dimension of the full state. In an effort to lessen the computational load,
most works resort to the sparser Fisher information matrices (FIMs) [9] or use
sparsified representations [10, 11]. Even so, the use of TOED metrics is
costly and thus often disregarded in the literature in favor of fast IT
metrics, e.g., the entropy.

In this work, we demonstrate that the expensive evaluation of optimality
criteria over the expected FIMs during active graph-SLAM can be approximated
by analyzing the topology of the expected pose-graphs. This method requires
way less resources and eases the use of optimality criteria in online methods.
First, we propose a general relationship between the FIM of a graph-SLAM
system and the Laplacian matrix of the underlying pose-graph. This allows to
relate their spectra under certain conditions and, therefore, to establish a
link between optimality criteria and graph connectivity indices.

The rest of the paper is organized as follows. Section II discusses related
work and the contributions of this paper, Section III presents preliminary
contents, Section IV details the theoretical contributions of this paper, and
Section V contains the experimental results. The manuscript is concluded in
Section VI, where future work is also outlined.

##  II Related Work

The idea of the topology of a graph being closely related to its optimality
was already noticed four decades ago, when Cheng [12] realized that a graph
with the maximum number of spanning trees is generally optimal, and thus
related two problems (from graph theory and TOED) that had always been viewed
differently. More recently, Khosoussi et al. [13] observed that certain
classical optimality criteria are closely related to the connectivity of the
underlying pose-graph. In particular, they show the existing relationship
between the number of spanning trees of the pose-graph and the determinant of
the covariance matrix of the SLAM system (traditionally known as
D-optimality), and that between its algebraic connectivity and the
covariance’s maximum eigenvalue; for 2D and assuming constant and isotropic
variance through measurements. In [14], the authors extend the above
relationships to the case in which uncertainty evolves as the trajectory does.
Given block-isotropic Gaussian noise in the measurements, they relate the
determinant of the covariance to the determinants of the Laplacians of two
pose-graphs, each weighted by the decoupled rotational/translational inverse
variance. Chen et al. [15] study graph-SLAM as the synchronization problem
over $\mathbb{R}^{n}\times SO(n)$. They propose an approximation relationship
for the FIM’s trace (T-optimality) and two bounds on its determinant that,
once again, depend on the Laplacians of two weighted pose-graphs. In contrast
to [14], they assume isotropic Langevin noise for orientation and block-
isotropic Gaussian noise for translation.

Fast exploitation of the graph structure was also recently transferred to the
domain of information-theoretic BSP. Kitanov and Indelman [16] prove that the
number of spanning trees is also a good approximation of the posterior entropy
—a reasonable fact since it ultimately depends on the covariance determinant
as classical D-optimality. They also present a relationship between the
graph’s node degree and the Von Neumann entropy. Despite being faster, it
fails to select the optimal actions in some cases (just as T-optimality
would).

Following all the above relationships, instead of maximizing optimality
criteria of the FIM, the optimal set of actions in active SLAM can be found
more efficiently through maximizing graph connectivity indices. Chen et al.
[7] build a 2D multi-robot active SLAM algorithm that achieves uncertainty
minimization and information sharing between agents thanks to the fast
evaluation of the underlying pose-graphs topology.

All the aforementioned works, however, have isolatedly related specific
classic optimality criteria to certain connectivity indices; also for
specific/restrictive SLAM configurations. In this letter, on the basis of
graph theory, differential models, [13] and [17], we derive a general
theoretical relationship between the FIM of a graph-SLAM problem formulated
over the Lie group SE(n), and the Laplacian of the underlying pose-graph. On
top of that, we establish a strong link between the spectrum of both matrices
and relate optimality criteria to graph connectivity indices. Contrarily to
previous works, measurement noises are not restricted to be (block-) isotropic
nor constant, formulation is done over SE(n), and modern optimality criteria
are used. Note that these differences are key for active SLAM applications,
since: (i) covariance is usually non-isotropic (i.e., variances may not be the
same in all directions for rotation/translation and may be cross-correlated)
and varies along exploration, (ii) only differential representations maintain
the monotonicity of the decision making criteria (see [18]), and (iii) the use
of traditional criteria is not suitable for active SLAM111The best known
example is the possibility of a single element driving classical D-optimality
to zero. Also, the size of the FIM grows over time, so comparison of raw
determinants is unfair [19].. We validate the proposed relationships and
analyze time complexity in several 2D and 3D SLAM datasets. On average, our
method requires just $10\%$ of the time traditional computations would, and
error is only $2\%$. Besides, graph-based approximations always maintain same
the trend of optimality criteria over time, which makes their use appropriate
for active SLAM.

##  III Preliminaries

###  III-A Graph-based SLAM

Graph-SLAM methods employ a graph representation to solve the SLAM estimation
problem. Nodes in the graph represent the poses of the variables of interest
(i.e., the robot location and the map points), while edges represent the
sensor measurements. The process of generating constraints between nodes from
the observations is known as data association and is usually bounded to the
most likely topology to restrain complexity. Thus, under the assumption of
observations affected by Gaussian noise, an edge will encode the relative pose
between two nodes and the associated covariance matrix (or FIM). Such
constraints may be related to a sensor measurement (e.g., odometry) or to a
loop closure. The work in this manuscript is particularly focused on pose-
graphs, which flatten the above representation encoding only robot poses in
vertices. These sparser representations can be achieved by marginalizing the
map points in landmark-based representations, or by building a discretized
metric map via scan matching and updating it after a loop closure occurs.

In any case, once the graph is built and the data association problem solved,
the goal is to compute the (Gaussian-approximated) posteriors over the robot
poses. That is, to find the nodal configuration that maximizes the likelihood
of the observations [1]. The following optimization problem may be solved
using, e.g., Gauss-Newton method:

$\displaystyle\boldsymbol{x}^{*}=\arg\min_{\boldsymbol{x}}\boldsymbol{F}(\boldsymbol{x})$
(1)
$\displaystyle\text{s.t.}\quad\boldsymbol{F}(\boldsymbol{x})=\frac{1}{2}\textstyle\sum\limits_{j=1}^{m}\boldsymbol{F}_{j}(\boldsymbol{x})=\displaystyle\frac{1}{2}\textstyle\sum\limits_{j=1}^{m}\boldsymbol{e}_{j}^{T}(\boldsymbol{x})\boldsymbol{\Sigma}_{j}^{-1}\boldsymbol{e}_{j}(\boldsymbol{x})$

where $\boldsymbol{x}$ are the variables of interest (i.e., the robot poses),
$\boldsymbol{F}$ the cost function of the $m$ observations, and
$\boldsymbol{e}_{j}$ and $\boldsymbol{\Sigma}_{j}$ the error to be minimized
and covariance for each measurement.

###  III-B Modern Optimality Criteria in Active SLAM

While performing active SLAM, decision making comes down to computing the
utility that executing a certain set of actions would lead to, i.e., to
quantifying their expected uncertainty. Kiefer [20], on the basis of TOED,
shows that there is a family of mappings that quantify uncertainty, i.e.,
$\|\boldsymbol{\Sigma}\|\to\mathbb{R}$, which are dependent of just one
parameter ($p$):

$\|\boldsymbol{\Sigma}\|_{p}\triangleq\left(\frac{1}{\ell}\text{trace}(\boldsymbol{\Sigma}^{p})\right)^{\frac{1}{p}}$
(2)

where $\ell$ is the dimension of the state vector and
$\boldsymbol{\Sigma}\in\mathbb{R}^{\ell\times\ell}$ the covariance matrix
which measures its uncertainty. The preferred set of actions will be that with
lowest $\|\boldsymbol{\Sigma}\|_{p}$.

Kiefer’s information function may be expressed in terms of the eigenvalues of
$\boldsymbol{\Sigma}$,
$(\lambda_{1},\makebox[10.00002pt][c]{.\hfil.\hfil.},\lambda_{\ell})$, and
particularized for the different values of $p$; yielding four modern
optimality criteria [21]:

  * •

T-optimality criterion ($p=1$): captures the average variance. Its computation
is fast, but a single element may drive the whole metric and thus it may
perform similar to just evaluating the highest eigenvalue [22].

$T{\text{-}}opt\triangleq\frac{1}{\ell}\textstyle\sum\limits_{k=1}^{\ell}\lambda_{k}$
(3)

  * •

D-optimality criterion ($p=0$): captures the volume of the covariance hyper
ellipsoid. Only it captures global uncertainty and holds the monotonicity
property under both absolute and differential representations [18].

$D{\text{-}}opt\triangleq\exp\left(\frac{1}{\ell}\textstyle\sum\limits_{k=1}^{\ell}\log(\lambda_{k})\right)$
(4)

  * •

A-optimality criterion ($p=-1$): captures the harmonic mean variance, being
thus sensitive to smallest eigenvalues —in contrast to $T\text{-}opt$ which
just neglects them— and insensitive to extremely large ones.

$A{\text{-}}opt\triangleq\left(\frac{1}{\ell}\textstyle\sum\limits_{k=1}^{\ell}\lambda_{k}^{-1}\right)^{-1}$
(5)

  * •

$E$-optimality criterion ($p\to\pm\infty$): approximates the uncertainty using
a single eigenvalue. Despite its computation is fast, this criterion tends to
be too optimistic by underestimating the covariance (for the case of the
minimum eigenvalue).

$\displaystyle E{\text{-}}opt\triangleq\min(\lambda_{k}:k=1,...,\ell)$ (6)
$\displaystyle\tilde{E}{\text{-}}opt\triangleq\max(\lambda_{k}:k=1,...,\ell)$
(7)

###  III-C Graph Theory

A strict undirected graph is defined by the ordered pair of sets
${\mathcal{G}}\triangleq(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{\boldsymbol{v}_{0},...,\boldsymbol{v}_{n}\\}$ is the set of
vertices and
${\mathcal{E}=\\{\boldsymbol{e}_{1},...,\boldsymbol{e}_{m}\\}\subset\\{\
\\{\boldsymbol{v}_{i},\boldsymbol{v}_{k}\\}\ |\
\boldsymbol{v}_{i},\boldsymbol{v}_{k}\in\mathcal{V},\boldsymbol{v}_{i}\neq\boldsymbol{v}_{k}\\}}$
the set of edges. Their dimensions will be $|\mathcal{V}|=n$ and
$|\mathcal{E}|=m$. The adjacency matrix of the graph,
$\textbf{A}\in\\{0,1\\}^{n\times n}$, indicate whether pairs of vertices are
connected or not. Each element $a_{ik}$ will be $1$ if the pair
$(\boldsymbol{v}_{i},\boldsymbol{v}_{k})$ is connected and $0$ otherwise. Note
that the diagonal will be zero. The incidence matrix, $\boldsymbol{Q}$, shows
the connections between vertices and edges and can be defined as a
concatenation of $m$ column vectors, each of them associated to an edge:

$\boldsymbol{Q}=[\boldsymbol{q}_{1},\boldsymbol{q}_{2},\makebox[10.00002pt][c]{.\hfil.\hfil.},\boldsymbol{q}_{m}]\in\\{-1,0,1\\}^{n\times
m}$ (8)

The column block associated to the edge
$\boldsymbol{e}_{ik}\equiv\boldsymbol{e}_{j}$, that connects
$\boldsymbol{v}_{i}$ and $\boldsymbol{v}_{k}$, will be denoted as
$\boldsymbol{q}_{j}$. All elements of $\boldsymbol{q}_{j}$ will be zero except
those associated to the vertices incident upon $\boldsymbol{e}_{j}$ (i.e., the
$i$-th and $k$-th) which will be $[q_{j}]_{i}=-[q_{j}]_{k}=1$. The Laplacian
matrix of ${\mathcal{G}}$ is a matrix representation of the whole graph, and
may be read as a particular case of the discrete Laplace operator. It can be
expressed in terms of $\boldsymbol{Q}$ as:

$\boldsymbol{L}\triangleq\boldsymbol{Q}\boldsymbol{Q}^{T}=\boldsymbol{q}_{1}\boldsymbol{q}_{1}^{T}+\boldsymbol{q}_{2}\boldsymbol{q}_{2}^{T}+...+\boldsymbol{q}_{m}\boldsymbol{q}_{m}^{T}\in\mathbb{Z}^{n\times
n}$ (9)

Or, more compactly, as:

$\boldsymbol{L}\triangleq\textstyle\sum\limits_{j=1}^{m}\boldsymbol{E}_{j}=\textstyle\sum\limits_{j=1}^{m}\boldsymbol{q}_{j}\boldsymbol{q}_{j}^{T}$
(10)

where each generator $\boldsymbol{E}_{j}\in\\{-1,0,1\\}^{n\times n}$
represents the connection between the pair
$(\boldsymbol{v}_{i},\boldsymbol{v}_{k})$ through the edge
$\boldsymbol{e}_{j}$. An element of the matrix diagonal will be $1$ if it is
associated to the vertices, i.e., $[E_{j}]_{i,i}$ and $[E_{j}]_{k,k}$; and $0$
otherwise. Off-diagonal elements will be $-1$ if the nodes are related, i.e.,
$[E_{j}]_{ik}$ and $[E_{j}]_{k,i}$; and $0$ otherwise.

For a weighted graph ${\mathcal{G}}_{\gamma}$ in which
$\tilde{\boldsymbol{e}}_{j}\triangleq(\boldsymbol{v}_{i},\boldsymbol{v}_{k},\gamma_{ik})$
with $\gamma_{j}\equiv\gamma_{ik}\in\mathbb{R}$, generalization is straight-
forward. The weighted Laplacian will be now given by:

$\boldsymbol{L}_{\gamma}\triangleq\sum_{j=1}^{m}\boldsymbol{E}_{j}\gamma_{j}=\left\\{\begin{array}[]{ll}-\gamma_{ik}&\text{if}\
i\neq k,a_{ik}=1\\\ 0&\text{if}\ i\neq k,a_{ik}=0\\\
\textstyle\sum_{q=1}^{n}\gamma_{iq}&\text{if}\ i=k\end{array}\right.$ (11)

Note that (11) yields to (10) when $\gamma_{j}=1\ \forall j$. Also,
$\boldsymbol{L}_{\gamma}$ is positive semi-definite and singular, since
$\boldsymbol{L}_{\gamma}\boldsymbol{1}^{T}=\boldsymbol{0}^{T}$.

###  III-D Spectral Graph Theory

Most important graph connectivity indices come from the analysis of the
Laplacian spectrum, since it reflects how a graph is connected. Consider
$\boldsymbol{\mu}=(\mu_{1},\mu_{2},\makebox[10.00002pt][c]{.\hfil.\hfil.},\mu_{n})$
the ordered set of eigenvalues of $\boldsymbol{L}$ and
$\boldsymbol{\tilde{\mu}}=(\tilde{\mu}_{1},\tilde{\mu}_{2},\makebox[10.00002pt][c]{.\hfil.\hfil.},\tilde{\mu}_{n})$
that of $\boldsymbol{L}_{\gamma}$; both ranked in increasing order. In
connected graphs, the Laplacian matrix has one zero eigenvalue with unit
eigenvector, i.e., $\mu_{1}=\tilde{\mu}_{1}=0$.

The simplest metric broadly studied in the literature is the sum of the
Laplacian eigenvalues [23, 24]. The sum of all non-zero eigenvalues is known
to be given by:

$\displaystyle
S=\textstyle\sum\limits_{k=2}^{n}\mu_{k}=\text{tr}(\boldsymbol{L})=\sum_{k}l_{kk}=2m$
(12)

being $l_{kk}$ the diagonal elements of $\boldsymbol{L}$. Since the traces of
$\boldsymbol{L}$ and $\boldsymbol{L}_{\gamma}$ are proportional, as shown
hereafter, the previous metric can be easily generalized for a weighted graph.

$\displaystyle\text{tr}(\boldsymbol{L}_{\gamma})=\textstyle\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}\gamma_{j}l_{kk}=\frac{1}{n}\sum\limits_{j=1}^{n}\gamma_{j}\sum\limits_{k=1}^{n}l_{kk}$
$\displaystyle\propto\text{tr}(\boldsymbol{L})$ (13)

A second important index is the number of spanning trees, $t({\mathcal{G}})$,
i.e., the number of sub-graphs that are also trees with minimum number of
edges and which set of vertices equals that of the original graph. This index
provides a measure for the global reliability of a network. Following
Kirchhoff’s matrix-tree theorem (MTT), it is given by the determinant of the
reduced Laplacian matrix (after anchoring an arbitrary vertex), which equals
to any cofactor of $\boldsymbol{L}$:

$t({\mathcal{G}})\triangleq\det(\boldsymbol{L}_{reduced})=\text{cof}(\boldsymbol{L})=\frac{1}{n}\textstyle\prod\limits_{k=2}^{n}\mu_{k}$
(14)

The weighted MTT allows to compute the weighted number of spanning trees as:

$t({\mathcal{G}}_{\gamma})\triangleq\text{cof}(\boldsymbol{L}_{\gamma})=\frac{1}{n}\textstyle\prod\limits_{k=2}^{n}\tilde{\mu}_{k}$
(15)

The second smallest eigenvalue of the Laplacian is also a crucial index of a
graph, since its value reflects whether it is disconnected [25]. It is known
as the algebraic connectivity and is greater than zero only for connected
graphs:

$\alpha({\mathcal{G}})\triangleq\min(\mu_{k}:k=2,\makebox[10.00002pt][c]{.\hfil.\hfil.},n)=\mu_{2}$
(16)

Its generalization for weighted graphs is straight-forward.

Finally, the Kirchhoff index, $K({\mathcal{G}})$, measures the resistance
between each pair of vertices under the assumption that edges are unit
resistors, and is defined by [26]:

$K({\mathcal{G}})\triangleq n\textstyle\sum\limits_{k=2}^{n}\mu_{k}^{-1}$ (17)

##  IV Linking the Fisher Information Matrix and the Graph Laplacian

Consider a typical SLAM pose-graph in which nodes encode robot poses and edges
the relative transformation between node pairs and its uncertainty, usually in
the form of a FIM. The robot pose and its uncertainty can be defined with Lie
groups using the special Euclidean group $SE(n^{\prime})$. As in differential
representations, the real location of the robot w.r.t. a global frame ($w$),
denoted as $\boldsymbol{T}_{wi}$, will be defined by a large noise-free value
which contains the estimated location, and a small perturbation that encodes
the estimation error:

$\boldsymbol{T}_{wi}=\bar{\boldsymbol{T}}_{wi}\exp{\left({\boldsymbol{d}_{i}}^{\wedge}\right)}$
(18)

where $\bar{\boldsymbol{T}}_{wi}\in SE(n^{\prime})$ is a large mean
transformation, and $\boldsymbol{d}_{i}\in\mathbb{R}^{\ell}$ is a random
vector normally distributed and defined by its mean $\bar{\boldsymbol{d}}_{i}$
and covariance
${\boldsymbol{\Sigma}_{i}=\mathbb{E}[(\boldsymbol{d}_{i}-\bar{\boldsymbol{d}}_{i})(\boldsymbol{d}_{i}-\bar{\boldsymbol{d}}_{i})^{T}]}$;
expressed in its own frame. The hat operator $(\cdot)^{\wedge}$ defines the
mapping from the real vector space to that of the Lie algebra [27].
Alternatively, the perturbation may be expressed in the global frame, just
like in differential representations [28], in which case the exponential map
will precede the estimate:

$\boldsymbol{T}_{wi}=\exp{\left({\boldsymbol{d}_{wi}}^{\wedge}\right)}\
\bar{\boldsymbol{T}}_{wi}$ (19)

As mentioned previously, the $j$-th edge in the pose-graph will encode a
single measurement that represents the relative pose change between the pair
$(\boldsymbol{v}_{i},\boldsymbol{v}_{k})$. This transformation can be simply
expressed as:

$\boldsymbol{T}_{ik}=\boldsymbol{T}_{wi}^{-1}\
\boldsymbol{T}_{wk}=\exp{\left({\boldsymbol{d}_{ik}}^{\wedge}\right)}\bar{\boldsymbol{T}}_{ik}$
(20)

assuming that measurements are Gaussian on $SE(n^{\prime})$, i.e.,
$\boldsymbol{d}_{ik}\sim\mathcal{N}(0,\boldsymbol{\Sigma}_{ik}^{\prime})$ with
$\boldsymbol{\Sigma}_{j}^{\prime}\equiv\boldsymbol{\Sigma}_{ik}^{\prime}\in\mathbb{R}^{\ell\times\ell}$
the measurement covariance matrix. Note $\boldsymbol{d}_{ik}$ will be
referenced to the $i$-th frame, as the mean transformation is perturbed on the
left.

The error term of each measurement can be defined from (20) as the difference
between that single measurement, $\bar{\boldsymbol{T}}_{ik}$, and the optimal
estimate, $\boldsymbol{T}_{ik}$:

$\boldsymbol{e}_{j}(\boldsymbol{x})\equiv\boldsymbol{e}_{ik}(\boldsymbol{x})=\ln\left(\boldsymbol{T}_{wi}^{-1}\boldsymbol{T}_{wk}{\bar{\boldsymbol{T}}_{ik}}^{-1}\right)^{\vee}$
(21)

with
$\boldsymbol{x}=\left(\boldsymbol{T}_{w1},\makebox[10.00002pt][c]{.\hfil.\hfil.},\boldsymbol{T}_{wn}\right)$
the variables of interest, and $(\cdot)^{\vee}$ the inverse of the hat
operator. Inserting (19) into the above,

$\boldsymbol{e}_{j}(\boldsymbol{x})=\ln\left(\bar{\boldsymbol{T}}_{wi}^{-1}\exp\left(-{\boldsymbol{d}_{wi}}^{\wedge}\right)\exp\left({\boldsymbol{d}_{wk}}^{\wedge}\right)\bar{\boldsymbol{T}}_{wk}{\bar{\boldsymbol{T}}_{ik}}^{-1}\right)^{\vee}$
(22)

and using now the adjoint (see, e.g., [27]) to transform vectors from the
tangent space around one element to that of another, and the definition
$\exp{(Ad_{\boldsymbol{A}}\boldsymbol{B})}\triangleq\boldsymbol{A}\exp{(\boldsymbol{B})}\boldsymbol{A}^{-1}$,
the term inside the logarithm in (22) becomes:

$\displaystyle\exp\left(-Ad_{\boldsymbol{T}_{wi}^{-1}}{\boldsymbol{d}_{wi}}^{\wedge}\right)\exp\left(Ad_{\boldsymbol{T}_{wi}^{-1}}{\boldsymbol{d}_{wk}}^{\wedge}\right)\exp\left({\boldsymbol{e}}_{j}(\bar{\boldsymbol{x}}){}^{\wedge}\right)$
(23)

with
$\boldsymbol{e}_{j}(\bar{\boldsymbol{x}})=\ln(\bar{\boldsymbol{T}}_{wi}^{-1}\bar{\boldsymbol{T}}_{wk}{\bar{\boldsymbol{T}}_{ik}}^{-1})^{\vee}$
and
$(\bar{\boldsymbol{T}}_{wi}^{-1}\bar{\boldsymbol{T}}_{wk}{\bar{\boldsymbol{T}}_{ik}}^{-1})$
small.

Finally, using the first-order approximation [29] of the Baker-Campbell-
Haussdorf formula for the product of exponential maps, the linearized error
can be expressed as:

$\boldsymbol{e}_{j}(\boldsymbol{x})\approx
Ad_{\boldsymbol{T}_{wi}^{-1}}({\boldsymbol{d}_{wk}}-{\boldsymbol{d}_{wi}})+{\boldsymbol{e}}_{j}(\bar{\boldsymbol{x}})$
(24)

Or, equivalently, in matrix form,

$\boldsymbol{e}_{j}(\boldsymbol{x})\approx\boldsymbol{e}_{j}(\bar{\boldsymbol{x}})-Ad_{\boldsymbol{T}_{wi}^{-1}}\begin{bmatrix}\boldsymbol{\mathbb{I}}_{\ell}&-\boldsymbol{\mathbb{I}}_{\ell}\end{bmatrix}\delta\boldsymbol{x}_{j}$
(25)

with $\delta\boldsymbol{x}_{j}=[\boldsymbol{d}_{wi}\ \boldsymbol{d}_{wk}]^{T}$
and $\boldsymbol{\mathbb{I}}_{\ell}$ the identity matrix of size $\ell$.

Inserting the error function into (1) and generalizing
$\delta\boldsymbol{x}_{j}$ to $\delta\boldsymbol{x}=\left[\boldsymbol{d}_{w1}\
\makebox[10.00002pt][c]{.\hfil.\hfil.}\ \boldsymbol{d}_{wn}\right]^{T}$ to
account for all measurements, the ML (quadratic) cost function will be:

$\displaystyle\boldsymbol{F}(\boldsymbol{x})$
$\displaystyle\approx\boldsymbol{F}(\bar{\boldsymbol{x}})-\textstyle\sum_{j}\boldsymbol{e}_{j}(\bar{\boldsymbol{x}})^{T}{\boldsymbol{\Sigma}_{j}^{\prime}}^{-1}Ad_{\boldsymbol{T}_{wi}^{-1}}\boldsymbol{\mathcal{I}}_{j}\delta\boldsymbol{x}$
$\displaystyle\quad+\frac{1}{2}\textstyle\sum_{j}\delta\boldsymbol{x}^{T}{\boldsymbol{\mathcal{I}}_{j}}^{T}Ad_{\boldsymbol{T}_{wi}^{-1}}^{T}{\boldsymbol{\Sigma}_{j}^{\prime}}^{-1}Ad_{\boldsymbol{T}_{wi}^{-1}}\boldsymbol{\mathcal{I}}_{j}\delta\boldsymbol{x}$
(26)
$\displaystyle=\boldsymbol{F}(\bar{\boldsymbol{x}})-\boldsymbol{Z}\delta\boldsymbol{x}+\frac{1}{2}\delta\boldsymbol{x}^{T}\boldsymbol{Y}\delta\boldsymbol{x}$
(27)

with $\boldsymbol{\mathcal{I}}_{j}$ the $1\text{-by-}n$ selection block
matrix, populated with zero blocks everywhere but in the $i$-th and $k$-th
columns, where
$[\boldsymbol{\mathcal{I}}_{j}]_{1,i}=-[\boldsymbol{\mathcal{I}}_{j}]_{1,k}=\boldsymbol{\mathbb{I}}_{\ell}$.

The Fisher information matrix —or Hessian— of the entire system can be
directly extracted from (IV) and expressed as:

$\boldsymbol{Y}=\textstyle\sum\limits_{j=1}^{m}\boldsymbol{Y}_{j}=\textstyle\sum\limits_{j=1}^{m}{\boldsymbol{\mathcal{I}}_{j}}^{T}{\boldsymbol{\Sigma}_{j}}^{-1}\boldsymbol{\mathcal{I}}_{j}$
(28)

with
${\boldsymbol{\Sigma}_{j}}^{-1}=Ad_{\boldsymbol{T}_{wi}^{-1}}^{T}{\boldsymbol{\Sigma}_{j}^{\prime}}^{-1}Ad_{\boldsymbol{T}_{wi}^{-1}}$
the inverse covariance matrix of the relative movement, expressed in $w$.
Since we kept the perturbations $\delta\boldsymbol{x}$ in the global frame
from (25) on, the need arises to express their covariance in that frame as
well. This formulation over Lie groups is analogous to the differential one
(see, e.g., [1]), but embedding the equivalent measurement Jacobian in the
covariance rather than in $\boldsymbol{\mathcal{I}}_{j}$.

((a)) Example graph.

((b)) $\boldsymbol{Y}_{1}$ (odometry edge).

((c)) $\boldsymbol{Y}_{10}$ (loop closure).

((d)) Full FIM, $\boldsymbol{Y}$.

((e)) Graph Laplacian, $\boldsymbol{L}$.

Figure 1: Example of two of the generators $\boldsymbol{Y}_{j}$, and
$\boldsymbol{Y}$ for an example 2D pose-graph with $n=m=10$ that contains one
loop closure. Also, the graph Laplacian. Non-zero matrix elements are depicted
with black dots.

At this point, we can leverage graph theory and write
${\boldsymbol{\mathcal{I}}_{j}}=\boldsymbol{q}_{j}^{T}\otimes\boldsymbol{\mathbb{I}}_{\ell}$,
where $\otimes$ denotes the Kronecker product and $\boldsymbol{q}_{j}$ is the
column vector that identifies the vertices incident upon the $j$-th edge (see
Section III-C). Then, using the transpose and mixed-product properties of the
Kronecker product, the full FIM can be expressed in terms of the pose-graph
topology,

$\therefore\boldsymbol{Y}=\textstyle\sum\limits_{j=1}^{m}\boldsymbol{Y}_{j}=\sum\limits_{j=1}^{m}\boldsymbol{E}_{j}\otimes\boldsymbol{\Sigma}_{j}^{-1}$
(29)

where the generator $\boldsymbol{Y}_{j}\in\mathbb{R}^{n\ell\times n\ell}$ is
the information matrix of the entire system associated to the $j$-th edge; and
$\boldsymbol{E}_{j}=\boldsymbol{q}_{j}\boldsymbol{q}_{j}^{T}$ are the
Laplacian generators, see (10).

The left- and right-multiplication of the covariance matrices of the
measurements by ${\boldsymbol{\mathcal{I}}_{j}}$ confers $\boldsymbol{Y}$ a
very special block-sparsity pattern that, in fact, conveys that of the
Laplacian of the underlying pose-graph. Figure 1 contains a pose-graph toy
example, for which the information matrix, two of their generators and its
Laplacian are shown. Sub-figures 1(d) and 1(e) illustrate the similarity
between the block-sparsity patterns of $\boldsymbol{Y}$ and the Laplacian
matrix, $\boldsymbol{L}$.

Two special cases of equality (29) arise, in which it is possible to directly
link the full information matrix to the (weighted) Laplacian rather than to
its generators. The first one corresponds to the situation of constant
uncertainty through measurements (i.e., a constant covariance matrix or FIM,
$\bar{\boldsymbol{\Phi}}$, for all $j$); a common assumption in related
literature [13], although unrealistic except for some exploratory
trajectories. Under this hypothesis, by leveraging the associative property of
the Kronecker product, (29) becomes:

$\displaystyle\boldsymbol{Y}=\textstyle\sum\limits_{j=1}^{m}\boldsymbol{E}_{j}\otimes\bar{\boldsymbol{\Phi}}=\boldsymbol{L}\otimes\bar{\boldsymbol{\Phi}}\qquad\text{if
}\boldsymbol{\Phi}_{j}=\bar{\boldsymbol{\Phi}}\ \forall j$ (30)

The second case considers variable uncertainty along exploration. Since any
positive semi-definite matrix can be considered trivially upper-bounded by a
diagonal matrix with its largest eigenvalue as diagonal terms, it holds:

$\boldsymbol{\Sigma}_{j}\succeq\lambda^{j}_{1}\
\boldsymbol{\mathbb{I}}_{\ell}\ \ \Leftrightarrow\ \
\boldsymbol{\Phi}_{j}\preceq\rho^{j}_{\ell}\
\boldsymbol{\mathbb{I}}_{\ell}=(\lambda^{j}_{1})^{-1}\
\boldsymbol{\mathbb{I}}_{\ell}$ (31)

with
$(\lambda^{j}_{1},\makebox[10.00002pt][c]{.\hfil.\hfil.},\lambda^{j}_{\ell})$
the ordered set of eigenvalues of $\boldsymbol{\Sigma}_{j}$ and
$(\rho^{j}_{1},\makebox[10.00002pt][c]{.\hfil.\hfil.},\rho^{j}_{\ell})$ that
of the FIM $\boldsymbol{\Phi}_{j}={\boldsymbol{\Sigma}_{j}}^{-1}$; ranked in
increasing order. Using the previous bound, (7) and the associative property
of the Kronecker product, (29) now becomes:

$\displaystyle\boldsymbol{Y}$
$\displaystyle\preceq\textstyle\sum\limits_{j=1}^{m}\left(\|\boldsymbol{\Phi}_{j}\|_{\infty}\
\boldsymbol{E}_{j}\right)\otimes\boldsymbol{\mathbb{I}}_{\ell}$
$\displaystyle=\boldsymbol{L}_{\gamma}\otimes\boldsymbol{\mathbb{I}}_{\ell}\ \
\ \text{if }\boldsymbol{\Phi}_{j}\preceq\ \|\boldsymbol{\Phi}_{j}\|_{\infty}\
\boldsymbol{\mathbb{I}}_{\ell}\ \forall j$ (32)

where $\boldsymbol{L}_{\gamma}$ is the Laplacian of the pose-graph in which
each edge is weighted with $\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{\infty}$. As
with the weighted Laplacian, (32) yields to (30) for the case that
$\gamma_{j}=1\ \forall j$.

###  IV-A On the Spectra

Consider now
$(\bar{\rho}_{1},\makebox[10.00002pt][c]{.\hfil.\hfil.},\bar{\rho}_{\ell})$ to
be the ordered set of eigenvalues of $\bar{\boldsymbol{\Phi}}$, and
$(0=\mu_{1},\mu_{2},\makebox[10.00002pt][c]{.\hfil.\hfil.},\mu_{n})$ that of
the Laplacian matrix $\boldsymbol{L}$, again ranked in increasing order.
According to the spectral properties of the Kronecker product:

$\text{eig}\left(\boldsymbol{L}\otimes\bar{\boldsymbol{\Phi}}\right)=\mu_{k}\
\bar{\rho}_{b},\ \
\begin{array}[]{ll}k=1,\makebox[10.00002pt][c]{.\hfil.\hfil.},n\\\
b=1,\makebox[10.00002pt][c]{.\hfil.\hfil.},\ell\end{array}$ (33)

Thus, under the assumption of constant uncertainty, optimality criteria
applied to $\boldsymbol{Y}$ can be obtained by applying it separately to the
reduced Laplacian (i.e., after removing its zero eigenvalue) and
$\bar{\boldsymbol{\Phi}}$. For the different $p$-values, it will be:

$\displaystyle\|\boldsymbol{Y}\|_{p}$
$\displaystyle=\left\\{\begin{array}[]{lrr}\|\boldsymbol{L}\|_{p}\
\|\bar{\boldsymbol{\Phi}}\|_{p}&\text{if}&0<|p|<\infty\\\
\|\boldsymbol{L}\|_{p}\ \|\bar{\boldsymbol{\Phi}}\|_{p}\
\|\bar{\boldsymbol{\Phi}}\|_{p}^{-\frac{1}{n}}&\text{if}&p=0\end{array}\right.$
(36)

Leading to the following proportionality relationship,

$\therefore\|\boldsymbol{Y}\|_{p}\propto\|\boldsymbol{L}\|_{p}\quad\forall p$
(37)

The above equation allows to shift the traditional approach of applying
optimality criteria to $\boldsymbol{Y}$, to a new strategy where they are
applied to $\boldsymbol{L}$. Given that new optimality criteria will be
functionals of the reduced Laplacian eigenvalues, the spectral graph theory
presented in Section III-D can be leveraged. Hence, under the assumption that
every measurement has the same covariance, optimality criteria of
$\boldsymbol{Y}$ (or $\boldsymbol{\Sigma}$) can be expressed in terms of the
pose-graph structure as:

$\displaystyle T{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle=A{\text{-}}opt(\boldsymbol{\Sigma})^{-1}$ $\displaystyle\propto
T{\text{-}}opt(\boldsymbol{L})$ $\displaystyle=\bar{d}$ (38) $\displaystyle
D{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle=D{\text{-}}opt(\boldsymbol{\Sigma})^{-1}$ $\displaystyle\propto
D{\text{-}}opt(\boldsymbol{L})$ $\displaystyle=\left(n\
t({\mathcal{G}})\right)^{\frac{1}{n}}$ (39) $\displaystyle
A{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle=T{\text{-}}opt(\boldsymbol{\Sigma})^{-1}$ $\displaystyle\propto
A{\text{-}}opt(\boldsymbol{L})$ $\displaystyle=n^{2}\ K({\mathcal{G}})^{-1}$
(40) $\displaystyle E{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle=\tilde{E}{\text{-}}opt(\boldsymbol{\Sigma})^{-1}$
$\displaystyle\propto E{\text{-}}opt(\boldsymbol{L})$
$\displaystyle=\alpha({\mathcal{G}})$ (41)

where $n$ is the number of nodes and $\bar{d}\triangleq 2m/n$ the average
degree of the pose-graph. Note that (39) is consistent with [13] for the
particular case they studied in which $\ell=\\{2,3\\}$ and $D{\text{-}}opt$ is
defined in a traditional way [30].

On the other hand, using Weyl’s monotonicity theorem [31], the following
inequality is satisfied for the case of variable uncertainty, as expressed in
(32):

$\therefore\|\boldsymbol{Y}\|_{p}\leq\|\boldsymbol{L}_{\gamma}\|_{p}\ \
\text{if}\ \gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{\infty}\ \forall p$ (42)

Thus, we are first weighting the graph edges individually with
$\tilde{E}\text{-}opt$ and then computing the desired optimality criteria of
the graph. The bound in (31) and the fact that $\tilde{E}\text{-}opt\geq
T\text{-}opt\geq D\text{-}opt\geq A\text{-}opt\geq E\text{-}opt$ makes (42)
hold for all $p$. If we consider isotropic noise, the bound in (31) turns into
equality and so does (42). However, for non-isotropic (nor diagonal)
covariance matrices, (42) represents an extremely conservative bound for
criteria other than the one used as weight. Interestingly, for $p=\infty$ the
bound particularizes to
$\tilde{E}{\text{-}}opt(\boldsymbol{Y})\lesssim\tilde{E}{\text{-}}opt(\boldsymbol{L}_{\gamma})$
because (i) the highest eigenvalue is weakly affected by off-diagonal elements
and (ii) absolute values of the off-diagonal terms in SLAM FIMs are generally
smaller than those on the main diagonal.

Instead of the loose upper-bound that (42) offers in general, an approximation
relationship can be obtained by following the strategy of weighting the pose-
graph with the same optimality criterion to be estimated:

$\therefore\|\boldsymbol{Y}\|_{p}\approx\|\boldsymbol{L}_{\gamma}\|_{p}\ \
\text{if}\ \gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{p}\ \forall p$ (43)

The goodness of approximation, in general, will depend on: (i) the number of
off-diagonal elements in both $\boldsymbol{\Phi}_{j}$ (cross-correlations) and
$\boldsymbol{Y}$ (loop closures); (ii) the values of the off-diagonal terms in
$\boldsymbol{\Phi}_{j}$, relative to those in the main diagonal; and (iii) how
every criterion accounts for them. Regarding the latter, equality will emerge
for $T\text{-}opt$ as it neglects off-diagonal terms, and
$E\text{-}opt(\boldsymbol{L}_{\gamma})$ will represent a lower-bound, unlike
$\tilde{E}{\text{-}}opt(\boldsymbol{L}_{\gamma})$, although more affected by
off-diagonal terms. Finally, particularizing (43) for the different
$p$-values,

$\displaystyle\tilde{E}{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle\lesssim\tilde{E}{\text{-}}opt(\boldsymbol{L}_{\gamma})$ (44)
$\displaystyle T{\text{-}}opt(\boldsymbol{Y})$
$\displaystyle=T{\text{-}}opt(\boldsymbol{L}_{\gamma})=\bar{d}\ \bar{\gamma}$
(45) $\displaystyle D{\text{-}}opt(\boldsymbol{Y})$ $\displaystyle\approx
D{\text{-}}opt(\boldsymbol{L}_{\gamma})=\left(n\
t({\mathcal{G}}_{\gamma})\right)^{\frac{1}{n}}$ (46) $\displaystyle
E{\text{-}}opt(\boldsymbol{Y})$ $\displaystyle\gtrsim
E{\text{-}}opt(\boldsymbol{L}_{\gamma})=\alpha({\mathcal{G}}_{\gamma})$ (47)

where ${\mathcal{G}}_{\gamma}$ now denotes the pose-graph weighted with the
same criterion to be computed, $\bar{\gamma}$ its average weight and
$\boldsymbol{L}_{\gamma}$ its weighted Laplacian. $A{\text{-}}opt$ was not
presented since the complexity of the weighted Kirchhoff index makes its use
worthless. Also, computation of the Laplacian determinant to evaluate the
number of spanning trees quickly becomes intractable for large graphs, as well
as it generates low precision for small values. The logarithmic determinant
avoids under/overflow and allows to compute (46) efficiently via:

$D{\text{-}}opt(\boldsymbol{Y})\approx n^{\frac{1}{n}}\
\exp{\left\\{\log(t({\mathcal{G}}_{\gamma}))/n\right\\}}$ (48)

##  V Experimental Validation

In this section, we conduct several experiments to prove the theoretical
relationships in (38)-(41) and (44)-(47) hold. Pose-graph datasets from [32]
and [33], which are publicly available, have been used for 2D and 3D
experiments, respectively. To compare traditional and graph-based approaches,
we simulate the construction of the pose-graph as if the robot were performing
active SLAM. That is, at each time step, a new node and its corresponding
constraints are added to the graph and optimality criteria is computed using
both $\mathbf{Y}$ and $\mathbf{L}$. Experiments have been performed on an
Intel Core i9 CPU.

###  V-A Constant Uncertainty Case

First, we used a reduced trajectory of the FRH 2D dataset that contains the
path before the first loop closure occurs (purely exploratory). We assigned to
every edge the same following FIM, which is non-isotropic and in which the
translational variances are correlated:

$\displaystyle\boldsymbol{\Phi}_{j}=\bar{\boldsymbol{\Phi}}$
$\displaystyle=\scalebox{0.9}{$\begin{pmatrix}11.11&-3&0\\\ -3&6.25&0\\\
0&0&250\end{pmatrix}$ }\ \forall j$ (49)

Figure 2(a) shows the computed $T\text{-},D\text{-},A\text{-}$ and
$E\text{-}opt$ using the estimation-theoretic (blue) and graphical (red)
facets of the problem. All curves overlap, proving that the relationships in
(38)-(41) hold and, moreover, that the proportionality constants derived in
(36) are consistent —although they are not necessary for active SLAM. Time
consumed per step by both approaches appears in Figure 2(b), clearly showing
the advantage of computing
$\|\boldsymbol{L}\|_{p}\|\bar{\boldsymbol{\Phi}}\|_{p}$ (red) over
$\|\boldsymbol{Y}\|_{p}$ (blue) as the size of the pose-graph grows. Studying
computational complexity, optimality criteria on $\boldsymbol{L}$ requires
$\mathcal{O}(n^{3})+\mathcal{O}(\ell^{3})$ while on $\boldsymbol{Y}$ requires
$\mathcal{O}(\ell^{3}n^{3})$, omitting lower order terms and being
$\mathcal{O}(\cdot)$ a lower-bound. Also, as the FIM dimension grows, building
$\mathbf{Y}$ requires way far more resources than creating ${\mathcal{G}}$.

((a)) Optimality criteria.

((b)) Time ($s$).

Figure 2: Optimality criteria of the full FIM (blue) and the Laplacian (red),
and the time required per step to compute them in the reduced FRH sequence
with constant uncertainty.

###  V-B Variable Uncertainty Case

((a)) FRH, $\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{\infty}$.

((b)) FRH, $\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{p}$.

((c)) MIT, $\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{p}$.

((d)) INTEL, $\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{p}$.

Figure 3: Optimality criteria of the full FIM (blue) and the Laplacian (red)
weighted with $\|\boldsymbol{\Phi}_{j}\|_{\infty}$ (a), and
$\|\boldsymbol{\Phi}_{j}\|_{p}$ (b-d).

Consider now the case in which edges’ FIMs are no longer constant. According
to (42), one first needs to construct a graph weighted with
$\gamma_{j}=\|\boldsymbol{\Phi}_{j}\|_{\infty}$. In this case, the whole
trajectory and the original FIMs contained in FRH dataset have been used
(which sparsity structure is similar to (49)). Figure 3(a) contains the
resulting $\tilde{E}\text{-},T\text{-},D\text{-}$ and $E\text{-}opt$ for the
full information matrix (blue) and the weighted Laplacian (red). The selected
bound indeed limits $\|\boldsymbol{Y}\|_{p}\ \forall p$, though it is an
extremely conservative one for $p$ other than $\infty$, for which (44) holds
during the entire sequence.

Figure 3(b) shows the results in the same dataset using the approximation in
(43) instead. Blue and red curves are now much closer to each other;
overlapping for T-opt, and also during certain parts of the trajectory for the
other criteria. Besides, the trend of the two curves is the same (i.e., either
both increase or decrease); a property that holds in all studied datasets and
key for active SLAM —otherwise we could be wrongly detecting an information
gain/loss. Further experiments have been carried out using the MIT, Intel, and
3D Garage datasets; to prove the proposed relationships hold and that are not
dependent on the dimension of the estimation vector. Analogous results to
those seen in FRH dataset have been obtained, and they are presented in
Figures 3(c), 3(d) and 4(a), respectively. Figure 4(b) shows the time
difference in the 3D dataset. Behavior is equivalent to Figure 2(b), although
now appears in a log-linear plot and the difference grows up to $10^{2}s$ in
the end of the sequence.

((a)) Optimality criteria.

((b)) Time ($s$).

Figure 4: Optimality criteria of the full FIM (blue) and the Laplacian (red) in the Garage dataset. Also, the time required per step to compute them. Dataset |  | Approximation Error | Time (min)
---|---|---|---
n | m | d |  $\boldsymbol{\Delta}\tilde{\textbf{E}}$-opt |  $\boldsymbol{\Delta}$T-opt |  $\boldsymbol{\Delta}$D-opt |  $\boldsymbol{\Delta}\textbf{E}$-opt | t($\|\boldsymbol{Y}\|_{p}$) | t($\|\boldsymbol{L}_{\gamma}\|_{p}$) |  $\boldsymbol{\Delta}$t
MIT | 807 | 827 | 2.1 | 2.76% |  $\sim$0% | 0.16% | 3.53% | 13.75 | 1.96 | 85.7%
FR079 | 989 | 1217 | 2.4 | 0.43% |  $\sim$0% | 7.15% | 5.33% | 26.50 | 3.07 | 88.4%
CSAIL | 1045 | 1171 | 2.2 | 0.11% |  $\sim$0% | 1.68% | 1.05% | 33.90 | 2.73 | 91.9%
INTEL | 1227 | 1481 | 2.4 |  $\sim$0% |  $\sim$0% | 5.85% | 7.19% | 63.29 | 7.46 | 88.2%
FRH | 1316 | 1485 | 2.2 |  $\sim$0% |  $\sim$0% | 0.76% | 0.49% | 121.77 | 5.42 | 95.6%
MH01 (monocular) | 376 | 544 | 2.9 |  $\sim$0% |  $\sim$0% | 0.74% | 1.49% | 4.22 | 0.56 | 86.6%
V101 (monocular) | 264 | 415 | 3.1 |  $\sim$0% |  $\sim$0% | 0.13% | 3.27% | 1.01 | 0.14 | 84.9%
V101-103 (stereo-multi) | 322 | 369 | 2.3 |  $\sim$0% |  $\sim$0% | 0.40% | 3.65% | 2.21 | 0.30 | 86.1%
V201 (stereo-inertial) | 337 | 598 | 3.5 |  $\sim$0% |  $\sim$0% | 0.79% | 0.05% | 2.65 | 0.16 | 94.0%
Garage | 1661 | 2615 | 3.1 | 0.01% |  $\sim$0% | 6.21% | 7.55% | 1549.9 | 11.70 | 99.2%
Mean | - | - | - | 0.34% |  $\sim$0% | 2.38% | 3.36% | - | - | 90.1%
TABLE I: Percentage error (median) in estimation of optimality criteria using
the graph Laplacian instead of the full FIM. Also, the accumulated time
required to compute both approaches (in minutes) and the time reduction
achieved.

Since it is hard to visually capture the exact difference between the curves
presented given their similarity, Table I contains the median percentage
errors when using our approximations instead of the expensive computations
over $\boldsymbol{Y}$. It contains the results for all the previously
mentioned datasets, but also for FR079 and CSAIL (2D). Furthermore, we
analyzed some EuRoC sequences [34], extracting their pose-graphs with ORB-
SLAM3 [35]. Quantitative results denote that differences between computing
$\|\boldsymbol{L}_{\gamma}\|_{p}$ and $\|\boldsymbol{Y}\|_{p}$ following (43)
are indeed very low, and even indistinguishable in some cases. $T\text{-}opt$
was perfectly computed in all cases, showing numerical errors only and proving
equality in (45) holds. Error in the case of $\tilde{E}\text{-}opt$ is akin
($0.3\%$ on average and being nearly zero in most datasets) since it is
insensitive to elements outside the main diagonal when they are lower than
those on it. However, for MIT, FR079 and CSAIL the error is not negligible. We
attribute it to certain isolated measurements in these datasets with FIMs
several orders of magnitude larger than the rest, and with extremely high off-
diagonal elements (also orders of magnitude); perhaps due to incorrect
behaviors of the SLAM algorithm. In any case, when these measurements are
corrected, or when we use a modern SLAM system as in the EuRoC sequences, the
errors drop to zero. Besides, the upper-bound in (44) is satisfied whenever
the error is non-zero. Unlike the above two, the smallest eigenvalue is much
more sensitive to off-diagonal terms (both cross-correlations and loop
closures), even when they are small. The estimation error of $E\text{-}opt$ is
the highest ($3.4\%$), also due to the numerical complexity of precisely
computing the smallest eigenvalue of high-dimensional matrices. $D\text{-}opt$
subtly inherits the same behavior since it takes into account all eigenvalues,
showing an average approximation error of $2.4\%$. Nevertheless, in most cases
it remained below $0.8\%$. A deeper analysis on the eigenvalue variation
demonstrates that $\Delta\tilde{E}\text{-}opt$, $\Delta D\text{-}opt$ and
$\Delta E\text{-}opt$ increase slightly as the amount of loop closures does.
When the edge FIMs become denser and their off-diagonal terms dominate,
particularly $\Delta E\text{-}opt$ is affected.

Also, Table I contains the total time required to compute modern optimality
criteria with both approaches and the reduction achieved using the Laplacian.
These computations require, in one case: building the full FIM and computing
its optimality criteria; and in the other case: building 4 different weighted
graphs (one for each criterion), analyzing their connectivity and computing
optimality criteria equivalences. To make a fair comparison, both methods are
evaluated under the same conditions, and eigenvalue computations leverage fast
decomposition techniques. On average, computing optimality criteria of the
weighted Laplacian required just $10\%$ of the time that traditional
calculations over the FIM did.

##  VI Conclusions

In this paper, we have shown that quantifying uncertainty in active graph-SLAM
formulated over $SE(n)$ can be efficiently done by analyzing the topology of
the underlying pose-graph. We have proposed and validated relationships
between modern optimality criteria and graph connectivity indices; showing
that equivalent results can be obtained in a fraction of the time. On average,
approximations with $2\%$ error can be computed in just $10\%$ of the time.
Regardless of the estimation error, the same trend is always maintained,
proving that minimum uncertainty (i.e., optimal) actions can be found by
exploiting the graphical structure of the problem.

As future work, we aim to use the proposed method to perform online (multi-
robot) active visual SLAM. Also, the use of full graphs instead of only pose-
graphs is to be studied.

## Acknowledgments

This work was partially supported by MINECO project PID2019‐108398GB‐I00 and
DGA_FSE T45_20R.

## References

  * [1] G. Grisetti, R. Kummerle, C. Stachniss, and W. Burgard, “A tutorial on graph-based SLAM,” _IEEE Intelligent Transportation Systems Magazine_ , vol. 2, no. 4, pp. 31–43, 2010.
  * [2] H. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping: Part I,” _IEEE Robotics & Automation Magazine_, vol. 13, no. 2, pp. 99–110, 2006.
  * [3] C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. Reid, and J. J. Leonard, “Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age,” _IEEE Trans. on Robotics_ , vol. 32, no. 6, pp. 1309–1332, 2016.
  * [4] R. Bajcsy, “Active perception,” _Proc. of the IEEE_ , vol. 76, no. 8, pp. 966–1005, 1988.
  * [5] R. Platt Jr, R. Tedrake, L. Kaelbling, and T. Lozano-Perez, “Belief space planning assuming maximum likelihood observations,” in _Robotics: Science and Systems (RSS)_ , 2010.
  * [6] A. A. Makarenko, S. B. Williams, F. Bourgault, and H. F. Durrant-Whyte, “An experiment in integrated exploration,” in _IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , vol. 1, 2002, pp. 534–539.
  * [7] Y. Chen, S. Huang, and R. Fitch, “Active SLAM for mobile robots with area coverage and obstacle avoidance,” _IEEE/ASME Trans. on Mechatronics_ , 2020\.
  * [8] C. Stachniss, G. Grisetti, and W. Burgard, “Information gain-based exploration using rao-blackwellized particle filters.” in _Robotics: Science and Systems (RSS)_ , vol. 2, 2005, pp. 65–72.
  * [9] V. Indelman, L. Carlone, and F. Dellaert, “Planning in the continuous domain: A generalized belief space approach for autonomous navigation in unknown environments,” _The Int. J. of Robotics Research_ , vol. 34, no. 7, pp. 849–882, 2015.
  * [10] H. Carrillo, P. Dames, V. Kumar, and J. A. Castellanos, “Autonomous robotic exploration using a utility function based on Rényi’s general theory of entropy,” _Aut. Robots_ , vol. 42, no. 2, pp. 235–256, 2018.
  * [11] K. Elimelech and V. Indelman, “Simplified decision making in the belief space using belief sparsification,” _The Int. J. of Robotics Research_ , vol. 41, no. 5, pp. 470–496, 2022.
  * [12] C.-S. Cheng, “Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory,” _J. of Combinatorial Theory_ , vol. 31, no. 2, pp. 240–248, 1981.
  * [13] K. Khosoussi, S. Huang, and G. Dissanayake, “Novel insights into the impact of graph structure on SLAM,” in _IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , 2014, pp. 2707–2714.
  * [14] K. Khosoussi, M. Giamou, G. S. Sukhatme, S. Huang, G. Dissanayake, and J. P. How, “Reliable graphs for SLAM,” _The Int. J. of Robotics Research_ , vol. 38, no. 2-3, pp. 260–298, 2019.
  * [15] Y. Chen, S. Huang, L. Zhao, and G. Dissanayake, “Cramér–Rao bounds and optimal design metrics for pose-graph SLAM,” _IEEE Trans. on Robotics_ , vol. 37, no. 2, pp. 627–641, 2021.
  * [16] A. Kitanov and V. Indelman, “Topological information-theoretic belief space planning with optimality guarantees,” _arXiv preprint arXiv:1903.00927_ , 2019.
  * [17] J. A. Placed and J. A. Castellanos, “Fast autonomous robotic exploration using the underlying graph structure,” in _IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , 2021, pp. 6649–6656.
  * [18] M. L. Rodríguez-Arévalo, J. Neira, and J. A. Castellanos, “On the importance of uncertainty representation in active SLAM,” _IEEE Trans. on Robotics_ , vol. 34, no. 3, pp. 829–834, 2018.
  * [19] L. Mihaylova, T. Lefebvre, H. Bruyninckx, K. Gadeyne, and J. De Schutter, “A comparison of decision making criteria and optimization methods for active robotic sensing,” in _Int. Conf. on Numerical Methods and Applications_ , 2002, pp. 316–324.
  * [20] J. Kiefer, “General equivalence theory for optimum designs (approximate theory),” _The Annals of Statistics_ , pp. 849–879, 1974.
  * [21] F. Pukelsheim, _Optimal design of experiments_. SIAM, 2006.
  * [22] H. Carrillo, I. Reid, and J. A. Castellanos, “On the comparison of uncertainty criteria for active SLAM,” in _IEEE Int. Conf. on Robotics and Automation (ICRA)_ , 2012, pp. 2080–2087.
  * [23] B. Zhou, “On sum of powers of the Laplacian eigenvalues of graphs,” _Linear Algebra and its App._ , vol. 429, no. 8-9, pp. 2239–2246, 2008.
  * [24] H. A. Ganie, A. M. Alghamdi, and S. Pirzada, “On the sum of the laplacian eigenvalues of a graph and Brouwer’s conjecture,” _Linear Algebra and its App._ , vol. 501, pp. 376–389, 2016.
  * [25] N. M. M. De Abreu, “Old and new results on algebraic connectivity of graphs,” _Linear Algebra and its App._ , vol. 423, pp. 53–73, 2007.
  * [26] H. Chen and F. Zhang, “Resistance distance and the normalized Laplacian spectrum,” _Discrete Applied Mathematics_ , vol. 155, no. 5, pp. 654–661, 2007.
  * [27] J. Sola, J. Deray, and D. Atchuthan, “A micro Lie theory for state estimation in robotics,” _arXiv preprint arXiv:1812.01537_ , 2018.
  * [28] T. D. Barfoot and P. T. Furgale, “Associating uncertainty with three-dimensional poses for use in estimation problems,” _IEEE Trans. on Robotics_ , vol. 30, no. 3, pp. 679–693, 2014.
  * [29] M. Brossard, S. Bonnabel, and J.-P. Condomines, “Unscented Kalman filtering on Lie groups,” in _IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , 2017, pp. 2485–2491.
  * [30] A. Wald, “On the efficient design of statistical investigations,” _The Annals of Mathematical Statistics_ , vol. 14, no. 2, pp. 134–140, 1943.
  * [31] I. Gohberg and M. G. Kreĭn, _Introduction to the Theory of Linear Nonselfadjoint Operators_ , 1978, vol. 18.
  * [32] L. Carlone, R. Aragues, J. A. Castellanos, and B. Bona, “A fast and accurate approximation for planar pose graph optimization,” _The Int. J. of Robotics Research_ , vol. 33, no. 7, pp. 965–987, 2014.
  * [33] L. Carlone, R. Tron, K. Daniilidis, and F. Dellaert, “Initialization techniques for 3D SLAM: a survey on rotation estimation and its use in pose graph optimization,” in _IEEE Int. Conf. on Robotics and Automation (ICRA)_ , 2015, pp. 4597–4604.
  * [34] M. Burri, J. Nikolic, P. Gohl, T. Schneider, J. Rehder, S. Omari, M. W. Achtelik, and R. Siegwart, “The EuRoC micro aerial vehicle datasets,” _The Int. J. of Robotics Research_ , vol. 35, no. 10, pp. 1157–1163, 2016\.
  * [35] C. Campos, R. Elvira, J. J. G. Rodríguez, J. M. Montiel, and J. D. Tardós, “ORB-SLAM3: An accurate open-source library for visual, visual–inertial, and multimap SLAM,” _IEEE Trans. on Robotics_ , 2021\.


#  Towards a parallel corpus of Portuguese and the Bantu language Emakhuwa of
Mozambique

Felermino D. M. A. Ali1, Andrew Caines2, Jaimito L. A. Malavi1
1Department of Computer Engineering, Lurio University, Mozambique
2 Computer Laboratory, University of Cambridge, United Kingdom
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Major advancement in the performance of machine translation models has been
made possible in part thanks to the availability of large-scale parallel
corpora. But for most languages in the world, the existence of such corpora is
rare. Emakhuwa, a language spoken in Mozambique, is like most African
languages low-resource in NLP terms. It lacks both computational and
linguistic resources and, to the best of our knowledge, few parallel corpora
including Emakhuwa already exist. In this paper we describe the creation of
the Emakhuwa-Portuguese parallel corpus, which is a collection of texts from
the Jehovah’s Witness website and a variety of other sources including the
African Story Book website, the Universal Declaration of Human Rights and
Mozambican legal documents. The dataset contains 47,415 sentence pairs,
amounting to 699,976 word tokens of Emakhuwa and 877,595 word tokens in
Portuguese. After normalization processes which remain to be completed, the
corpus will be made freely available for research use.

##  1 Introduction

Machine translation (MT) is the process by which computational models are
trained to transform a source language text into a target language text, and
is a technology which in recent years has seen great improvements in
performance thanks to the development of MT with neural networks (NMT)
Kalchbrenner and Blunsom (2013); Sutskever et al. (2014); Bahdanau et al.
(2015). NMT typically depends on supervised machine learning from large
parallel corpora of texts in the source and target language pair. The creation
of such corpora usually depends on extrinsic motivation for the existence of
abundant parallel text: for instance, government activity in multilingual
settings such as the European and Canadian Parliaments. In the context of NMT,
this fact has led to a dichotomous situation of high and low-resource language
pairings. For the academic community, English-German or English-French are
prototypical high-resource translation pairs whereas most other language pairs
are low-resource in comparison.

We present a corpus for a low-resource language pair: Portuguese and Emakhuwa
(alternatively, ‘Makhuwa’ or ‘Makua’), the official and the most widely spoken
languages of Mozambique, respectively. Emakhuwa is spoken in all the provinces
of northern Mozambique, namely Niassa, Cabo Delgado and Nampula and also in
Zambezia in central northern Mozambique. It is estimated that approximately
25% of the country’s population of 30 million people make use of the language
on a daily basis as an alternative to Portuguese de Paula and Duarte (2016).
Emakhuwa is also spoken in some of the neighbouring countries to the north of
Mozambique – namely, Tanzania and Malawi Ngunga (2012) but speaker populations
in these countries are relatively small.

There are 8 variants of Emakhuwa Ngunga and Faquir (2012): Elomwe (ISO-639
code: ngl), Esankaci, Esaaka (ISO-639 code: xsq), Echirima (ISO-639 code:
mhm), Emarevoni (ISO-639 code: xmc), Emeeto (ISO-639 code: mgh), Enahara and
Central (ISO-639 code: vmw). The variants are distributed across different
districts of northern and central Mozambique (see Figure 1) and differ
slightly in terms of accents and lexicon.

Figure 1: Geographic distribution of Emakhuwa variants in Mozambique Ngunga
and Faquir (2012).

Like many languages spoken on the African continent, Emakhuwa has limited
resources for computational linguistics compared with English, French,
Portuguese, and so on. Thus we are collecting a dataset for MT in which
Portuguese texts are paired with Emakhuwa translations. The 47,415 sentence
pairs we have collected contain 699,976 word tokens of Emakhuwa and 877,595
word tokens in Portuguese. The corpus will be made available for research use
when final normalization and data collection has been
completed111placeholder.com. In addition we will seek out new data sources and
continue to expand the corpus.

##  2 Related Work

In general, African languages have been relatively little explored by the NLP
research community. However, lately this scenario seems to be improving as
more data are being made available for research use, including translation
work. OPUS Tiedemann (2012), the 1000Langs corpus crawled from Bible corpora
Asgari and Schütze (2017), and the JW300 project Agić and Vulić (2019) are
examples of this trend, as they made available parallel corpora of over 300
languages including Emakhuwa-Portuguese. The Crúbadán
Project222http://crubadan.org/languages/vmw also used Jehovah’s Witness
resources to create a corpus of Emakhuwa. However, the corpus is monolingual
and relatively small with around 44,071 tokens extracted from 4 documents.

The Masakhane project works mainly on low-resource MT for African languages,
and is an excellent source of African language parallel corpora Nekoto et al.
(2020). Currently, they have a growing online community of researchers who
collaborate, contribute and share advancements in NLP for African languages.
They have an open repository 333https://github.com/masakhane-io/masakhane-mt
for sharing data as well as code and tools for building and facilitating NLP
research in African languages. Nevertheless, the Emakhuwa language has not
been explored yet by the community.

Source |  Portuguese |  Emakhuwa |  English
---|---|---|---
JW |  depois, eu percebi que essa tinha sido a decisão certa. |  nuuvira okathi kihoona wira vaari vooloka othaama. |  After that, I realized that it was the right choice
Centro Catequético Paulo VI |  vivo aquilo em que acredito ? |  vekekhai kinnettela seiyo sinà minaka ? |  Do I live on what I believe?
African Story Book |  Certo homem tinha dois filhos |  Mulopwana mmosa aahikhalana an’awe anli. |  A man had two sons
Declaration of Human Rights |  todos os seres humanos nascem livres e iguais em dignidade e em direitos . dotados de razão e de consciência , devem agir uns para com os outros em espírito de fraternidade . |  atthu othene aniyaria oolikana ni owilamula moota ontthunaya okhala , variyari v edignidade ni edireito . akhalanne esaria ni otthokelela , ahaana akhalasaka othene saya vamurettele . |  the law needs to be known by the whole community, because from the knowledge of the law we can defend and safeguard our rights.
Land Law of Mozambique |  nas áreas rurais , as comunidades locais participam : |  mulaponi mwa imatta , ikomunidade sa elapo yeyo sokhalana mpantta : |  in rural areas, local communities participate:
Table 1:  Examples from the Portuguese-Emakhuwa parallel corpus, with English
translation.

##  3 Data

The dataset contains Portuguese-Emakhuwa parallel sentences, collected from
crawling the Jehovah’s Witness (JW) website444https://www.jw.org and the
African Story Book website555https://www.africanstorybook.org. The African
Story Book contains 17 short stories in Emakhuwa with Portuguese translations.
The Jehovah’s Witness website contains The Watchtower—Study Edition magazine
as well as The Watchtower and Awaque! from 2016 to 2021. Also, contains 27
books of the New Testament Bible.

The corpus also contains text from various institutional sources. These were
digitized by performing optical character recognition (OCR) on a set of PDF
files from Centro Catequético Paulo VI (Paul VI Catechetical Centre), the
Universal Declaration of Human Rights, and Mozambican Land Law. The majority
of texts come from the Centro Catequético Paulo VI which has published a
series of three catechism books: _Yesu Mopoli Ahu – Jesus Nosso Salvador_
(‘Jesus Our Saviour’). These books, besides being religious, also touch upon a
wide range of topics.

The dataset contains texts written in the central Emakhuwa variant only,
because this variant has relatively more resources than others. The sentences
come from 125 pair documents in total, and amount to 699,976 word tokens of
Emakhuwa. Table 1 shows examples from the dataset, with Portuguese and
Emakhuwa parallel sentences and English glosses.

Processing of the OCR obtained from these documents involved the removal of
some inconsistencies. For instance, the letter “ì” was wrongly recognized as
“T”, and the letter “á” was recognized as “6”, to give just two examples of
OCR errors. Processing also involved dividing longer sentences into shorter
and concise sentences as well as discarding sentences wrongly recognized. Then
followed the alignment of Portuguese and Emakhuwa sentences which has been
manually carried out. More processing needs to be done, as it transpires that
spelling standards vary between the data sources. As an example, there are
some lexical conflicts in the corpus, particularly regarding the use of the
letters “j” and “c” along with the suffix or infix “erya”. JW texts tend to
use the letter “cerya”, while others use “jerya”. So for example the English
word “begin” would be written as “opacerya” in JW texts, whereas in others
resources it would be written as “opajerya”. Another example is the English
word “kiss”: its translation to Emakhuwa in the African Story Book is
“epeeco”, whereas in other resources is translated as “epexo”.

Source |  Lang |  Sentences |  Tokens
---|---|---|---
JW |  PT |  42,840 |  798,371
|  VMW |  |  638,365
CCA |  PT |  4067 |  73,221
|  VMW |  |  56,724
ASB |  PT |  294 |  2746
|  VMW |  |  1945
LL |  PT |  128 |  1656
|  VMW |  |  1832
HR |  PT |  86 |  1601
|  VMW |  |  1110
Total |  PT |  47,415 |  877,595
|  VMW |  |  699,976
Table 2:  Dataset counts where: JW = Jehovah’s Witness, CCA = Centro
Catequético Paulo VI, ASB = African Book Story, LL = Land Law of Mozambique,
HR = Universal Declaration of Human Rights; PT = Portuguese, VMW = Emakhuwa.

Word borrowing is another issue to take into account, since Emakhuwa takes
many words from Portuguese, but without a consensus on spelling conventions.
As an example, take the word “bible” which in Portuguese is ”bíblia”. In
Emakhuwa it is sometimes written as “biblia” and at other times written as
“biibiliya”. This inconsistency also exists within Emakhuwa language resources
itself, as the alphabet and spelling standards went through several revisions
– the latest in 2012 Ngunga and Faquir (2012). Therefore, some future
processing is necessary to normalize the word standards in the dataset. The
corpus will be available for research use, and updates may be obtained from
our project website666placeholder.com. Table 2 summarizes the corpus in terms
of sentences and the number of tokens coming from each data source.

##  4 Baseline translation model

We train an initial NMT model with the default OpenNMT
configuration777https://github.com/OpenNMT/OpenNMT-
py/blob/master/docs/source/quickstart.md, which consists of a 2-layer LSTM
with 500 hidden units on both the encoder and decoder Klein et al. (2017).
Sentences from the corpus are randomly assigned to training and test sets at a
ratio of 9:1. These data splits will be released with the corpus so that
others may compare the performance of their models against this one. We
evaluate with BLEU Papineni et al. (2002) as shown in Table 3. This presents a
baseline level of performance to improve upon in future work.

Target |
---|---
Source |  Portuguese |  Emakhuwa
Portuguese |  - |  12.42
Emakhuwa |  13.09 |  -
Table 3:  BLEU scores for Emakhuwa-Portuguese and Portuguese-Emakhuwa NMT
models.

##  5 Conclusion

In this paper we describe the creation of a new parallel corpus of Emakhuwa
and Portuguese. The preparation of the corpus is on-going as the texts require
more processing and normalization, but it will be made freely available for
research use, most probably for machine translation. Currently, the dataset is
made up of mostly religious and legal content but in future our objective is
to diversify the range of sources and topics covered. This is important in
order that Portuguese-Emakhuwa translation models work well across various
domains.

## Acknowledgements

The authors wish to acknowledge the Centro Catequético Paulo VI for allowing
to use their materials for research purpose. The second author is supported by
Research England via the University of Cambridge Global Challenges Research
Fund. He wishes to thank Paula Buttery, Tanya Hall, Carol Nightingale & Sara
Serradas Duarte for their help and guidance.

## References

  * Agić and Vulić (2019) Željko Agić and Ivan Vulić. 2019.  JW300: A wide-coverage parallel corpus for low-resource languages.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3204–3210, Florence, Italy. Association for Computational Linguistics.
  * Asgari and Schütze (2017) Ehsaneddin Asgari and Hinrich Schütze. 2017.  Past, present, future: A computational investigation of the typology of tense in 1000 languages.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _Proceedings of the International Conference on Learning Representations (ICLR)_.
  * Kalchbrenner and Blunsom (2013) Nal Kalchbrenner and Phil Blunsom. 2013.  Recurrent continuous translation models.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush. 2017\.  OpenNMT: Open-source toolkit for neural machine translation.  In _Proceedings of ACL 2017, System Demonstrations_.
  * Nekoto et al. (2020) Wilhelmina Nekoto, Vukosi Marivate, Tshinondiwa Matsila, Timi Fasubaa, Taiwo Fagbohungbe, Solomon Oluwole Akinola, Shamsuddeen Muhammad, Salomon Kabongo Kabenamualu, Salomey Osei, Freshia Sackey, Rubungo Andre Niyongabo, Ricky Macharm, Perez Ogayo, Orevaoghene Ahia, Musie Meressa Berhe, Mofetoluwa Adeyemi, Masabata Mokgesi-Selinga, Lawrence Okegbemi, Laura Martinus, Kolawole Tajudeen, Kevin Degila, Kelechi Ogueji, Kathleen Siminyu, Julia Kreutzer, Jason Webster, Jamiil Toure Ali, Jade Abbott, Iroro Orife, Ignatius Ezeani, Idris Abdulkadir Dangana, Herman Kamper, Hady Elsahar, Goodness Duru, Ghollah Kioko, Murhabazi Espoir, Elan van Biljon, Daniel Whitenack, Christopher Onyefuluchi, Chris Chinenye Emezue, Bonaventure F. P. Dossou, Blessing Sibanda, Blessing Bassey, Ayodele Olabiyi, Arshath Ramkilowan, Alp Öktem, Adewale Akinfaderin, and Abdallah Bashir. 2020.  Participatory research for low-resourced machine translation: A case study in African languages.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_.
  * Ngunga (2012) Armindo Ngunga. 2012.  Interferências de línguas moçambicanas em português falado em moçambique.  _Revista Científica Da Universidade Eduardo Mondlane, Série: Letras e Ciências Sociais_ , 1:7–20.
  * Ngunga and Faquir (2012) Armindo Ngunga and Osvaldo Faquir. 2012.  _Padronização da Ortografia de Línguas Moçambicanas: Relatório do III Seminário. Colecção As Nossas Línguas III_.  Maputo: CEA.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_.
  * de Paula and Duarte (2016) Ronaldo Rodrigues de Paula and Fábio Bonfim Duarte. 2016.  Diversidade linguística em moçambique.  In _Kadila: culturas e ambientes – Diálogos Brasil-Angola_. São Paulo: Bluche.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014.  Sequence to sequence learning with neural networks.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems (NeurIPS)_.
  * Tiedemann (2012) Jörg Tiedemann. 2012.  Parallel data, tools and interfaces in opus.  In _Proceedings of the Eight International Conference on Language Resources and Evaluation (LREC’12)_.


# Unsupervised Domain Adaptation for Segmentation with Black-box Source Model

Xiaofeng Liu  Gordon Center for Medical Imaging, Massachusetts General
Hospital and Harvard Medical School, Boston, MA, USA  Chaehwa Yoo  Gordon
Center for Medical Imaging, Massachusetts General Hospital and Harvard Medical
School, Boston, MA, USA  Dept. of Electronic and Electrical Engineering and
Graduate Program in Smart Factory, Ewha Womans University, Seoul, South Korea
Fangxu Xing  Gordon Center for Medical Imaging, Massachusetts General Hospital
and Harvard Medical School, Boston, MA, USA  C.-C. Jay Kuo  Dept. of
Electrical and Computer Engineering, University of Southern California, Los
Angeles, CA, USA  Georges El Fakhri  Gordon Center for Medical Imaging,
Massachusetts General Hospital and Harvard Medical School, Boston, MA, USA
Je-Won Kang  Gordon Center for Medical Imaging, Massachusetts General Hospital
and Harvard Medical School, Boston, MA, USA  Dept. of Electronic and
Electrical Engineering and Graduate Program in Smart Factory, Ewha Womans
University, Seoul, South Korea  Jonghye Woo  Gordon Center for Medical
Imaging, Massachusetts General Hospital and Harvard Medical School, Boston,
MA, USA

###### Abstract

Unsupervised domain adaptation (UDA) has been widely used to transfer
knowledge from a labeled source domain to an unlabeled target domain to
counter the difficulty of labeling in a new domain. The training of
conventional solutions usually relies on the existence of both source and
target domain data. However, privacy of the large-scale and well-labeled data
in the source domain and trained model parameters can become the major concern
of cross center/domain collaborations. In this work, to address this, we
propose a practical solution to UDA for segmentation with a black-box
segmentation model trained in the source domain only, rather than original
source data or a white-box source model. Specifically, we resort to a
knowledge distillation scheme with exponential mixup decay (EMD) to gradually
learn target-specific representations. In addition, unsupervised entropy
minimization is further applied to regularization of the target domain
confidence. We evaluated our framework on the BraTS 2018 database, achieving
performance on par with white-box source model adaptation approaches.

###### keywords:

Unsupervised domain adaptation, Black-box source model, Brain MR image
segmentation.

##  1 Introduction

Accurate tumor segmentation is an important prerequisite for early diagnosis
and treatment planning, which has been substantially improved with advances in
deep learning approaches. The performance of a pre-trained model, however, can
be severely degraded, when a source distribution differs from a target
distribution. For example, tumors with different grades are likely to yield
different distributions, which hampers the application of a single
segmentation model in segmenting tumors of varying degrees of severity and
growth [1]. In addition, it is costly to annotate high-quality labeled data in
the new target domain. Unsupervised domain adaptation (UDA) has been proposed
to address the problem of domain shift [2]. In UDA, a segmentation model is
typically trained using both source and target data, but only the source data
are labeled.

Although UDA offers a promising solution to the problem of domain shift, due
to the concerns over leakage of sensitive information contained in the patient
data, it is often challenging to access source data, when deploying the
developed model in the target domain [3]. To address this, Liu et al. proposed
a source-free or source-relaxed UDA (i.e., white-box domain adaptation) for
segmentation [3]. In that work, an off-the-shelf segmentation model was
adapted to a target domain via a pre-trained model in a source domain, by
transferring its batch normalization statistics. Recently, a deep inversion
technique [4], however, has shown that original training data can be recovered
from knowledge used during white-box domain adaptation, which may leak
confidential information [5]. Accordingly, this work aims to address the
limitation, by developing a black-box domain adaptation approach that further
restricts the use of knowledge from a source segmentation model.

To our knowledge, this is the first attempt at achieving UDA for a deep
segmentation network using black-box domain adaptation. The black-box setting
provides a more effective way to protect privacy, compared with white-box
domain adaptation approaches [3] or conventional UDA approaches [6]. Recently,
Zhang et al. [5] proposed to use the black-box UDA for classification, with
the class-wise noise rate estimation and category-wise sampling. However, that
work is not applicable to the segmentation task to carry out pixel-wise
classification. In previous works, segmentation based on the black-box domain
adaptation was largely ignored, although it could be used in a more realistic
and challenging scenario.

##  2 Related work

Unsupervised domain adaptation [2, 7, 8, 9] has been an important technology
to address the difficulties such as domain shift and costly labeling in the
new domains. Conventional approaches utilized both source and target domain
data for training [10, 1, 11, 12, 13]. Recently, source-free UDA [14, 15, 16]
has been proposed to only use the pre-trained model rather than co-training
the network with source and target domain data. A recent study [17] explored
the shared or domain-specific batch-normalization statistics to achieve domain
alignment. We note that domain generalization [18], a closely related but
different task, assumes that there are no target domain data in its training.

In this work, we target to tackle a more restrictive scenario, in which we
only use a black-box pre-trained model, and do not rely on the network
parameters. As stated above, a deep inversion technique [4], has shown that
original training data can be recovered from knowledge during white-box domain
adaptation [5]. A contemporary work [5] proposed to adapt a black-box
classification model to a target domain without both source domain data and
the model structure. That work proposed iterative learning with noisy labels,
which regarded the black-box predictions as noisy labels. To the best of our
knowledge, black-box UDA for segmentation has not been investigated. The
semantic segmentation [19, 20, 21, 22, 23, 24] makes pixel-wise classification
and provides more explainable results for the subsequent decision making
process.

##  3 METHOD

In the black-box UDA segmentation task, we have a network $f_{s}$ trained with
the labeled source domain sample $\\{x_{s},y_{s}\\}$, where $f_{s}$ is fixed
and accessed only through a nontransparent API at the adaptation stage. At the
adaptation stage, we only have access to the black-box $f_{s}$ and the
unlabeled target domain sample $\\{x_{t}\\}$ to train a target domain network
$f_{t}$ to achieve a good segmentation performance in the target domain. In
this work, we propose a practical solution to the black-box UDA for
segmentation with a noise-aware knowledge distillation scheme using pseudo
label with exponential mixup decay (EMD). The framework is shown in Fig. 1.

Following the knowledge distillation [4], the well-trained source model can
act as a teacher to provide its pixel-wise softmax histogram prediction of
each image. The target domain model is trained to imitate the source model.
The consistency of their prediction can be enforced with the Kullback–Leibler
(KL) divergence between their pixel-wise softmax histogram distributions.
However, due to the domain shift, the prediction of $f_{s}$ can be noisy.
Accordingly, we resort to a self-training scheme [1] to construct the pseudo
label for target domain training. Specifically, to achieve the gradual
translation to the target domain, we mix up the source and target domain
predictions, i.e., $f_{s}(x_{t})$ and $f_{t}(x_{t})$, and adjust their ratio
for the pseudo label $y_{t}^{\prime}$ with EMD:

$\displaystyle{y_{t}^{\prime}}_{n}=\lambda
f_{s}(x_{t})_{n}+(1-\lambda)f_{t}(x_{t})_{n},$ (1)

where $n$ indexes the pixel, and $f_{s}(x_{t})_{n}$ and $f_{t}(x_{t})_{n}$ are
the histogram distributions of the softmax output of the $n$-th pixel of the
predictions $f_{s}(x_{t})$ and $f_{t}(x_{t})$, respectively.
$\lambda=\lambda^{0}\text{exp}(-I)$ is a target adaptation momentum parameter
with an exponential decay w.r.t. the iteration $I$. $\lambda^{0}$ is the
initial weight of $f_{s}(x_{t})$, which is empirically set to 1. The loss
knowledge distillation with the EMD pseudo label can be formulated as:

$\displaystyle\mathcal{L}_{KL}=\frac{1}{H_{0}\times
W_{0}}\sum_{n}^{H_{0}\times
W_{0}}\mathcal{D}_{KL}(f_{t}(x_{t})_{n}||{y_{t}^{\prime}}_{n}),$ (2)

where $H_{0}$ and $W_{0}$ are the height and width of the image. Therefore,
the weight of $\lambda$ can be smoothly decreased along with the training, and
$f_{t}$ gradually represents the target data.

Figure 1: Illustration of our black-box UDA framework using knowledge
distillation with EMD pseudo label and unsupervised entropy minimization.

In addition, an unsupervised training scheme, e.g., entropy minimization [25],
can be added on top of our framework. For implementation, the entropy for
pixel segmentation can be formulated as an averaged entropy of the pixel-wise
softmax prediction, given by

$\displaystyle\mathcal{L}_{Ent}=\frac{1}{H_{0}\times
W_{0}}\sum_{n}^{H_{0}\times
W_{0}}\\{{f_{t}(x_{t})_{n}\text{log}f_{t}(x_{t})_{n}}\\}.$ (3)

Minimizing $\mathcal{L}_{Ent}$ leads to the output $f_{t}(x_{t})_{n}$ close to
a one-hot distribution, i.e., confident prediction.

In summary, our training objective can be formulated as

$\displaystyle\mathcal{L}={L}_{KL}+\alpha\mathcal{L}_{Ent},$ (4)

where $\alpha$ is used to balance between the knowledge distillation with the
EMD pseudo label and entropy minimization. We note that a trivial solution to
entropy minimization is that all unlabeled target data could have the same
one-hot encoding [25]. Thus, in order to stabilize the training, we linearly
change the hyper-parameter $\alpha$ from 5 to 0.

##  4 RESULTS

We evaluated our approach on the BraTS2018 database, comprising a total of 210
high-grade glioma (HGG) subjects and a total of 75 low-grade glioma (LGG)
subjects. [26]. Each subject has T1-weighted (T1), T1-contrast enhanced
(T1ce), T2-weighted (T2), and T2 Fluid Attenuated Inversion Recovery (FLAIR)
Magnetic Resonance Imaging (MRI) volumes with voxel-wise labels for the
enhancing tumor (EnhT), the peritumoral edema (ED), and the necrotic and non-
enhancing tumor core (CoreT). We denote the sum of EnhT, ED, and CoreT as the
whole tumor. More information about the database can be found in [26].
Training was performed on four NVIDIA TITAN Xp GPUs with the PyTorch deep
learning toolbox [27], which took about 5 hours.

Following the previous white-box source free UDA [3] and UDA with source data
[28], we used HGG subjects as the source domain and the LGG subjects as the
target domain, which have different size and position distributions [28]. We
trained $f_{s}$ using the prior work [3], and did not have access to its
network parameters at the adaptation stage. For simplicity, we used the same
2D U-Net backbone for $f_{s}$ and $f_{t}$ as in [28]. Specifically, we used
U-Net [29] as our segmentation network with 15 layers, batch normalization,
and dropout. The network was trained using Adam as an optimizer with
$\beta_{1}=0.9$ and $\beta_{2}=0.99$.

The slices of four modalities were concatenated as a 4-channel input with the
spatial size of 128$\times$128\. The training of adaptation used the LGG
training set. The evaluation was implemented in the LGG testing set. For
evaluation, we adopted the two metrics, including Dice similarity coefficient
(DSC) and Hausdorff distance (HD) metrics [30].

Figure 2: Comparison with the other UDA methods, and an ablation study of
entropy minimization for HGG to LGG UDA. We use white, dark gray, and gray to
indicate the CoreT, EnhT and ED, respectively. OSUDA [3] with the white-box
source model for UDA training is regarded as an “upper bound.”

We used BBUDA to denote our black-box UDA framework, and BBUDA-Ent indicates
the ablation study without entropy minimization. An illustration of the
segmentation results is shown in Fig. 2. We can see that the predictions of
our proposed BBUDA are better than the no adaptation model. The better
performance of BBUDA over BBUDA-Ent demonstrates the effectiveness of our
entropy minimization.

The quantitative evaluation results are shown in Table 1. Our proposed BBUDA
achieved the state-of-the-art performance for the black-box source-free UDA
segmentation, approaching performance of the white-box OSUDA [16, 3] with the
source model parameters, which can be considered an “upper-bound.” We note
that the label ratio consistency assumption in CRUDA [16] does not hold for
this HGG to LGG transfer task, which thus led to an inferior performance.

Table 1: Comparison of HGG to LGG black-box UDA with the four-channel input
for our four-class segmentation, i.e., whole tumor, enhanced tumor, core
tumor, and background. OSUDA [3] with the white-box source model for UDA
training is regarded as an “upper bound.”

Method | Source | Dice Score [%] $\uparrow$ | Hausdorff Distance [mm] $\downarrow$
---|---|---|---
model | WholeT | EnhT | CoreT | WholeT | EnhT | CoreT
Source only [3] | no UDA | 79.29 | 30.09 | 44.11 | 38.7 | 46.1 | 40.2
BBUDA | black-box | 82.21 | 31.33 | 46.64 | 28.6 | 26.4 | 28.1
BBUDA-Ent | black-box | 81.84 | 31.26 | 45.75 | 29.4 | 27.5 | 29.0
CRUDA [16] | white-box | 79.85 | 31.05 | 43.92 | 31.7 | 29.5 | 30.2
OSUDA [3] | white-box | 83.62 | 32.15 | 46.88 | 27.2 | 23.4 | 26.3

In addition to the HGG to LGG setting, we also proposed to adapt from LGG to
HGG. Similar to the HGG to LGG task, there was also the domain gap w.r.t.
tumor types and the label proportion of each class. The results are shown in
Table 2. Our proposed BBUDA achieved superior segmentation performance
consistently.

##  5 CONCLUSION

In this work, we tackled the problem of black-box UDA for segmentation under a
realistic and meaningful scenario, and proposed a practical and efficient
knowledge distillation scheme with EMD pseudo label. Specifically, we were
able to smoothly transfer the segmentation in the source domain to the target
domain with EMD to construct the pseudo label. In addition, unsupervised
entropy minimization was added on top of our model to further boost the
performance. Experimental results, carried out with the HGG to LGG adaptation
task, showed that our proposed BBUDA outperformed the source model, by a large
margin, and importantly, the DSC and HD metrics were comparable to the white-
box UDA approaches. In this work, we only investigated the adaptation between
HGG and LGG data, while the model can be general for any segmentation UDA
tasks. In addition, more advanced knowledge distillation and unsupervised
learning methods can be added on to further boost the performance, which is
subject to our future work.

Table 2: Comparison of LGG to HGG black-box UDA with the four-channel input
for our four-class segmentation, i.e., whole tumor, enhanced tumor, core
tumor, and background. OSUDA [3] with the white-box source model for UDA
training is regarded as an “upper bound.”

Method | Source | Dice Score [%] $\uparrow$ | Hausdorff Distance [mm] $\downarrow$
---|---|---|---
model | WholeT | EnhT | CoreT | WholeT | EnhT | CoreT
Source only [3] | no UDA | 81.45 | 34.36 | 40.30 | 36.7 | 41.6 | 37.2
BBUDA | black-box | 85.47 | 39.56 | 45.18 | 26.7 | 33.8 | 29.6
BBUDA-Ent | black-box | 84.92 | 38.64 | 44.73 | 27.1 | 34.6 | 31.3
CRUDA [16] | white-box | 87.62 | 40.17 | 49.65 | 23.9 | 22.7 | 23.9
OSUDA [3] | white-box | 89.75 | 44.21 | 50.34 | 22.2 | 19.3 | 21.6

###### Acknowledgements.

This work is partially supported by NIH R01DC018511 and P41EB022544.

## References

  * [1] Liu, X., Xing, F., Stone, M., Zhuo, J., Reese, T., Prince, J. L., El Fakhri, G., and Woo, J., “Generative self-training for cross-domain unsupervised tagged-to-cine mri synthesis,” in [International Conference on Medical Image Computing and Computer-Assisted Intervention ], 138–148, Springer (2021).
  * [2] Liu, X., Liu, X., Hu, B., Ji, W., Xing, F., Lu, J., You, J., Kuo, C.-C. J., Fakhri, G. E., and Woo, J., “Subtype-aware unsupervised domain adaptation for medical diagnosis,” AAAI (2021).
  * [3] Liu, X., Xing, F., Yang, C., El Fakhri, G., and Woo, J., “Adapting off-the-shelf source segmenter for target medical image segmentation,” in [International Conference on Medical Image Computing and Computer-Assisted Intervention ], 549–559, Springer (2021).
  * [4] Yin, H., Molchanov, P., Alvarez, J. M., Li, Z., Mallya, A., Hoiem, D., Jha, N. K., and Kautz, J., “Dreaming to distill: Data-free knowledge transfer via deepinversion,” in [Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition ], 8715–8724 (2020).
  * [5] Zhang, H., Zhang, Y., Jia, K., and Zhang, L., “Unsupervised domain adaptation of black-box source models,” arXiv preprint arXiv:2101.02839 (2021).
  * [6] Zou, Y., Yu, Z., Liu, X., Kumar, B., and Wang, J., “Confidence regularized self-training,” in [Proceedings of the IEEE/CVF International Conference on Computer Vision ], 5982–5991 (2019).
  * [7] Liu, X., Hu, B., Liu, X., Lu, J., You, J., and Kong, L., “Energy-constrained self-training for unsupervised domain adaptation,” in [2020 25th International Conference on Pattern Recognition (ICPR) ], 7515–7520, IEEE (2021).
  * [8] He, G., Liu, X., Fan, F., and You, J., “Classification-aware semi-supervised domain adaptation,” in [Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops ], 964–965 (2020).
  * [9] He, G., Liu, X., Fan, F., and You, J., “Image2audio: Facilitating semi-supervised audio emotion recognition with facial expression image,” in [Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops ], 912–913 (2020).
  * [10] Liu, X., Guo, Z., Li, S., Xing, F., You, J., Kuo, C.-C. J., El Fakhri, G., and Woo, J., “Adversarial unsupervised domain adaptation with conditional and label shift: Infer, align and iterate,” in [Proceedings of the IEEE/CVF International Conference on Computer Vision ], 10367–10376 (2021).
  * [11] Liu, X., Li, S., Ge, Y., Ye, P., You, J., and Lu, J., “Recursively conditional gaussian for ordinal unsupervised domain adaptation,” in [Proceedings of the IEEE/CVF International Conference on Computer Vision ], 764–773 (2021).
  * [12] Liu, X., Xing, F., Prince, J. L., Carass, A., Stone, M., El Fakhri, G., and Woo, J., “Dual-cycle constrained bijective vae-gan for tagged-to-cine magnetic resonance image synthesis,” in [2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI) ], 1448–1452, IEEE (2021).
  * [13] Liu, X., Xing, F., El Fakhri, G., and Woo, J., “A unified conditional disentanglement framework for multimodal brain mr image translation,” in [2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI) ], 10–14, IEEE (2021).
  * [14] Wang, D., Shelhamer, E., Liu, S., Olshausen, B., and Darrell, T., “Fully test-time adaptation by entropy minimization,” arXiv preprint arXiv:2006.10726 (2020).
  * [15] Liang, J., Hu, D., and Feng, J., “Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation,” in [International Conference on Machine Learning ], 6028–6039, PMLR (2020).
  * [16] Bateson, M., Kervadec, H., Dolz, J., Lombaert, H., and Ayed, I. B., “Source-relaxed domain adaptation for image segmentation,” in [International Conference on Medical Image Computing and Computer-Assisted Intervention ], 490–499, Springer (2020).
  * [17] Liu, X., Xing, F., El Fakhri, G., and Woo, J., “Adapting off-the-shelf source segmenter for target medical image segmentation,” in [MICCAI ], (2021).
  * [18] Liu, X., Hu, B., Jin, L., Han, X., Xing, F., Ouyang, J., Lu, J., Fakhri, G. E., and Woo, J., “Domain generalization under conditional and label shifts via variational bayesian inference,” IJCAI (2021).
  * [19] Liu, X., Han, Y., Bai, S., Ge, Y., Wang, T., Han, X., Li, S., You, J., and Lu, J., “Importance-aware semantic segmentation in self-driving with discrete wasserstein training,” in [Proceedings of the AAAI Conference on Artificial Intelligence ], 34(07), 11629–11636 (2020).
  * [20] Liu, X., Ji, W., You, J., Fakhri, G. E., and Woo, J., “Severity-aware semantic segmentation with reinforced wasserstein training,” in [Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition ], 12566–12575 (2020).
  * [21] Liu, X., Lu, Y., Liu, X., Bai, S., Li, S., and You, J., “Wasserstein loss with alternative reinforcement learning for severity-aware semantic segmentation,” IEEE Transactions on Intelligent Transportation Systems (2020).
  * [22] Liu, X., Xing, F., Gaggin, H. K., Wang, W., Kuo, C.-C. J., Fakhri, G. E., and Woo, J., “Segmentation of cardiac structures via successive subspace learning with saab transform from cine mri,” arXiv preprint arXiv:2107.10718 (2021).
  * [23] Wang, J., Liu, X., Wang, F., Zheng, L., Gao, F., Zhang, H., Zhang, X., Xie, W., and Wang, B., “Automated interpretation of congenital heart disease from multi-view echocardiograms,” Medical Image Analysis 69, 101942 (2021).
  * [24] Liu, X., Zhang, Y., Liu, X., Bai, S., Li, S., and You, J., “Reinforced wasserstein training for severity-aware semantic segmentation in autonomous driving,” arXiv preprint arXiv:2008.04751 (2020).
  * [25] Grandvalet, Y. and Bengio, Y., “Semi-supervised learning by entropy minimization,” in [NIPS ], (2005).
  * [26] Menze, B. H., Jakab, A., Bauer, S., Kalpathy-Cramer, J., Farahani, K., Kirby, J., Burren, Y., Porz, N., Slotboom, J., Wiest, R., et al., “The multimodal brain tumor image segmentation benchmark (BRATS),” IEEE transactions on medical imaging 34(10), 1993–2024 (2014).
  * [27] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A., “Automatic differentiation in pytorch,” (2017).
  * [28] Shanis, Z., Gerber, S., Gao, M., and Enquobahrie, A., “Intramodality domain adaptation using self ensembling and adversarial training,” in [Domain Adaptation and Representation Transfer and Medical Image Learning with Less Labels and Imperfect Data ], 28–36, Springer (2019).
  * [29] Ronneberger, O., Fischer, P., and Brox, T., “U-net: Convolutional networks for biomedical image segmentation,” in [International Conference on Medical image computing and computer-assisted intervention ], 234–241, Springer (2015).
  * [30] Zou, D., Zhu, Q., and Yan, P., “Unsupervised domain adaptation with dualscheme fusion network for medical image segmentation,” in [IJCAI ], 3291–3298 (2020).