# Verifiable Learned Behaviors via Motion Primitive Composition:
Applications to Scooping of Granular Media

Andrew Benton, Eugen Solowjow, Prithvi Akella1 1All authors are with Siemens
Corporation {andrew.benton, prithvi.akella<EMAIL_ADDRESS>
###### Abstract

A robotic behavior model that can reliably generate behaviors from natural
language inputs in real time would substantially expedite the adoption of
industrial robots due to enhanced system flexibility. To facilitate these
efforts, we construct a framework in which learned behaviors, created by a
natural language abstractor, are verifiable by construction. Leveraging recent
advancements in motion primitives and probabilistic verification, we construct
a natural-language behavior abstractor that generates behaviors by
synthesizing a directed graph over the provided motion primitives. If these
component motion primitives are constructed according to the criteria we
specify, the resulting behaviors are probabilistically verifiable. We
demonstrate this verifiable behavior generation capacity in both simulation on
an exploration task and on hardware with a robot scooping granular media.

##  I Introduction

In recent years, learning from human demonstrations has proven tremendously
successful at imitating intricate, human-like motion on robotic systems [1, 2,
3]. This has allowed for improvements in robotic grasping [4, 5, 6], assembly
[3, 7, 8], and even robotic surgery [9, 10, 11]. However, these methods often
require prohibitive amounts of precisely labeled data [12]. Additionally,
these learned behaviors are typically not transferrable to tasks that are
similar but not identical, prompting further research into task-transferrable
learning [13, 14, 15]. However, works in this vein exhibit similar, if not
heightened, requirements on the amount of data available to the learning
procedure.

Despite these challenges, more comprehensive learned models that incorporate
streams of multimodal data have shown tremendous success at learning
generalized, intricate behaviors. For example, the recently developed Palm-E
model has successfully translated natural language user commands to control
policies for a $6$-DOF arm, realizing the intended tasks even when they were
not explicitly learned [16]. Building on the success of Palm-E and other
foundational robotic models [17, 18, 19], recent work also aims to codify
effective design principles for these models [20].

Figure 1: A graphical representation of our natural-language-based behavior
generalizer and verification scheme. By ensuring that the language model only
composes behaviors as a directed graphical abstraction over the provided
motion primitives, we show that any such generated behavior has an associated
certificate list that we can exploit to verify the learned behavior’s ability
to realize the user’s desired task.

Conceptually, however, both the Palm-E model and the other learning paradigms
mentioned prior hinge on a notion of composing generalized behavior from a
finite set of learned behaviors. Prior work in controls and robotics has shown
that generalizing from this initial behavior set, termed motion primitives in
the existing literature, yields robust, and more importantly, verifiable
generalized behavior provided the primitives and subsequent behaviors are
constructed with care [21, 22, 23]. Consequently, inspired by the previous
attempts at codifying design principles for these learned models [20], we
posit that by leveraging these prior works in motion primitives and black-box
risk-aware verification, we can synthesize verifiable learned behaviors over a
provided set of carefully constructed motion primitives.

Our Contribution: Leveraging recent work in risk-aware verification [24, 25],
we take steps towards constructing a framework for verifying learned,
generalized behaviors composed from a set of motion primitives. Specifically,
if the input/output spaces of the motion primitives satisfy certain conditions
that permit its verifiability, and the behavior is constructed as a directed
graph over these primitives, then the resulting behavior is similarly
verifiable. We showcase this verifiability in both simulation and on hardware,
focusing on exploration and reconnaissance for the former and a granular media
scooping task for the latter.

Structure: We review black-box risk-aware verification and motion primitives
in Section II before formally stating the problem under study in Section II-C.
Section III details our behavior generation scheme and states our main
contribution regarding the verifiability of the resulting generated behaviors.
Finally, Section IV showcases our behavior generation scheme developing an
exploratory behavior - Section IV-A \- and a scooping motion for granular
media - Section IV-B. Both behaviors are also verified in the same sections
according to the provided verification scheme.

##  II Terminology and Formal Problem Statement

###  II-A Black-Box Risk-Aware Verification

The information in this section is adapted from [24, 25]. Black-box risk-aware
verification assumes the existence of a discrete-time controlled system of the
following form, with system state $x\in\mathcal{X}$, control input
$u\in\mathcal{U}$, environment state $d\in\mathcal{D}$ and potentially unknown
dynamics $f$:

$x_{k+1}=f(x_{k},u_{k},d),~{}\forall~{}k=0,1,2,\dots.$ (1)

As verification measures the robustness of a controlled system’s ability to
realize a behavior of interest, work in this vein assumes the existence of a
feedback controller $U:\mathcal{X}\times\mathcal{D}\to\mathcal{U}$. The
system’s evolution when steered by this controller $U$ will be denoted as
$\Sigma$ \- a function mapping an initial system and environment state to the
system state evolution as prescribed by (1), i.e.
$\Sigma(x_{0},d)=\\{x_{0},x_{1},\dots,x_{K}\\}\in\mathcal{X}^{K}$ for some
$K>0$. Finally, a robustness measure $\rho$ maps this state evolution
$\Sigma(x_{0},d)$ and environment state $d$ to the reals, i.e.
$\rho:\mathcal{X}^{K}\times\mathcal{D}\to\mathbb{R}$. For context, these
robustness measures can be those coming from temporal logic [26] or the
minimum value of a control barrier function over a time horizon [27] among
other methods. A positive outcome of this robustness measure indicates that
the corresponding state evolution realized the desired behavior, i.e.
$\rho(\Sigma(x_{0},d),d)\geq 0$ implies the state evolution $\Sigma(x_{0},d)$
realized the behavior of interest.

Black-box risk-aware verification employs this robustness measure to provide a
probabilistic statement on the system’s ability to realize the desired
behavior for all permissible initial conditions and environment states. This
will formally be expressed in the following theorem:

######  Theorem 1.

Let $\\{r^{i}=\rho(\Sigma(x_{0}^{i},d^{i}),d^{i})\\}_{i=1}^{N}$ be a set of
$N$ robustness evaluations of trajectories whose initial conditions and
environments $(x_{0}^{i},d^{i})$ were sampled via $\pi$ over
$\mathcal{X}\times\mathcal{D}$, and let
$r^{*}=\min\\{r_{1},r_{2},\dots,r_{N}\\}$. Then, both the probability of
sampling an initial condition and environment evolution pair whose robustness
is lower bounded by $r^{*}$ and the confidence in the associated probability
is only a function of the number of samples $N$ and a scalar
$\epsilon\in[0,1]$, i.e.

$\operatorname{\mathbb{P}}^{N}_{\pi}\left[\operatorname{\mathbb{P}}_{\pi}[\rho(\Sigma(x_{0},d),d)\geq
r^{*}]\geq 1-\epsilon\right]\geq 1-(1-\epsilon)^{N}.$ (2)

###  II-B Motion Primitives

Motion primitives are a well-studied field in the controls and robotics
literature, though we will provide a slight variant on existing definitions to
align with our notation.

######  Definition 1.

A Motion Primitive is $4$-tuple $\mathcal{P}=(\Xi,A,U,R)$ with the following
definitions for the tuple:

  * $(\Xi)$

The complete set of parameters for this primitive, i.e.
$\Xi\subseteq\mathbb{R}^{p}$ for an appropriate dimension $p\geq 0$.

  * $(A)$

A function taking a system and environment state $(x,d)$ as per (1) and
outputting the subset of valid parameters $P$ for this pair, i.e.
$A(x,d)=P\subseteq\Xi$.

  * $(U)$

The parameterized controller for this primitive, mapping states, environments,
and the parameter to inputs, i.e.
$U:\mathcal{X}\times\mathcal{D}\times\Xi\to\mathcal{U}$.

  * $(R)$

A parameterized function outputting the subset of the state space the system
will occupy upon completion of the primitive, i.e. for $\xi\in\Xi$ and with
environment state $d$, $R(\xi,d)=X_{f}\subseteq\mathcal{X}$.

As an example consistent with the simulations to follow then, consider the
system as per (1) to be a single-integrator system on the plane required to
navigate in a finite-sized grid. A feasible motion primitive $\mathcal{P}$
would be moving the system to an adjacent cell. For simplicity’s sake, assume
there are no obstacles, and as such, the environment state space
$\mathcal{D}=\varnothing$. Then, the complete set of parameters $\Xi$ would be
the labels for all the cells in this grid, the accepting function $A$ outputs
all adjacent cells to the cell containing the current system state $x$, $U$
could be a proportional controller sending the system to the appropriate grid,
and $R$ would output the subset of the state space encompassed by the cell to
which the system was required to move.

###  II-C Problem Statement

Our goal is to develop a framework by which behaviors learned over these
primitives can be verified. As such, we define a behavior $B$ as a directed
graph of primitives, with edges from a primitive $\mathcal{P}$ indicating the
primitive $\mathcal{P}^{\prime}$ to be run upon completion of $\mathcal{P}$.
For examples of such behaviors, see the sketch provided in Figure 1 and the
resulting behavior for our simulation example in Figure 3. The formal
definition of these behaviors will follow.

######  Definition 2.

A behavior $B$ is a directed graph defined as a $4$-tuple, i.e. $B=(N,E,S,T)$
with the following definitions:

  * $(N)$

The finite set of nodes for the graph, where each node is a primitive as per
Definition 1, i.e.
$N=\\{\mathcal{P}_{1},\mathcal{P}_{2},\dots,\mathcal{P}_{|N|}\\}$.

  * $(E)$

The set of directed edges connecting nodes in the graph. Each edge identifies
a method to choose parameters for the successive primitive. If multiple edges
emanate from a node, then a method exists such that at runtime, only one edge
is chosen.

  * $(S)$

A start function taking as input the system and environment state $(x,d)$ as
per (1) and outputting both the starting primitive and its parameter, i.e.
$S(x,d)=(\xi,\mathcal{P})$ where $\mathcal{P}\in N$ and $\xi\in
A_{\mathcal{P}}(x,d)$.

  * $(T)$

The set of terminal nodes, i.e. $T\subseteq N$.

Our goals are twofold. First, determine whether we can verify the behaviors
generated by Algorithm 1, and second, if the behaviors are verifiable,
determine a framework by which we can verify any behavior generated by this
method. Phrased formally, the problem statement will follow.

######  Problem 1.

Determine if the behaviors generated by Algorithm 1 are verifiable, and if
they are verifiable, determine a method to verify any such generated behavior.

Algorithm 1 Natural Language-based Behavior Generalizer

A set of primitives as per Definition 1 and their descriptions
$\mathbb{D}=\\{(\mathcal{P}_{i},$ description of primitive $i)\\}_{i=1}^{M}$,
a list of existing behaviors $\mathbb{B}=\\{B_{1},B_{2},\dots\\}$ with
behaviors $B$ as per Definition 2, and a natural language abstractor $A$
taking as input a string $s$ defining a desired behavior, a string $I$
defining any useful, non-primitive information available for behavior
generation, and the primitive list $\mathbb{D}$ and outputting behaviors $B$.

while True do

$c\leftarrow$ desired behavior $B$

if $c\not\in\mathbb{B}$ then

$s\leftarrow$ description of desired behavior

$I\leftarrow$ helpful non-primitive information

$\mathbb{B}\leftarrow\mathbb{B}\bigcup A(s,I)$

end if

end while

##  III Verifying Learned Behaviors

We will provide a solution to both aspects of Problem 1 simultaneously, by
constructing the framework for verifying any behavior as per Definition 2. To
construct this framework, we first note that there exist two outcomes to
executing any behavior from any initial system and environment state - it
either terminates successfully or it does not. In the event it terminates
successfully, we can record the set of all primitives run over the course of
the behavior, their corresponding parameters, and the system states upon
termination of the corresponding primitive, i.e.
$\mathbb{D}=\\{(\xi_{1},\mathcal{P}_{1},x^{f}_{1}),(\xi_{2},\mathcal{P}_{2},x^{f}_{2}),\dots\\}$.
If the behavior fails due to reasons such as an intermediary controller
failure or an error in the behavior’s graph construction leading to a runtime
error, we can record the failure.

This permits us to construct a robustness measure for a verification scheme
aligned with the method described in Section II-A. First, for each pair in the
dataset $\mathbb{D}$ generated by running the behavior, we can define a
certificate function checking whether the terminal state laid in the terminal
set prescribed by the primitive, parameter, and environment:

$C\left(\xi,\mathcal{P},x^{f},d\right)=x^{f}\in R_{\mathcal{P}}(\xi,d).$ (3)

Here, we note that we are implicitly associating boolean outcomes with $\pm
1$. The robustness measure $\rho$ would check the validity of each of these
certificates over the run of a behavior and output $1$ if all certificates
were satisfied and $-1$ if the system failed or any certificate was not
satisfied. Specifically then, let $(x_{0},d)$ be the initial system and
environment state, let $\Sigma$ be the trajectory function as described in
Section II-A, and let $\mathbb{D}$ be the dataset of tuples collected over the
course of a successfully run behavior. Then the robustness measure

$\rho_{B}(\Sigma(x_{0},d),d)=\begin{cases}\min\limits_{\gamma\in\mathbb{D}}~{}C(\gamma,d)&\mbox{if~{}behavior~{}finished},\\\
-1&\mbox{else}.\end{cases}$ (4)

Here, we have abbreviated the tuples in $\mathbb{D}$ with the variable
$\gamma$ to ease notation. That being said, the robustness measure $\rho_{B}$
in (4) evaluates to a positive number if and only if the behavior successfully
terminated and all component primitives exhibited their component desired
behaviors.

Figure 2: Examples of the environments considered for the example in Section
IV-A. The blue circle represents the agent, the blue square represents the
agent’s starting cell, the green squares are goals, the black squares are
obstacles, and the gold region is the region explored by the learned behavior.

Using the robustness measure in (4), we can verify any behavior as per
Definition 2. To ease the formal exposition of the results, we will first
denote via $\mathcal{B}$ the subset of the system and environment state spaces
that have a valid starting point for the behavior $B$ to be verified. This is
to ensure that in the verification procedure to follow, we do not sample and
evaluate the behavior’s performance from initial conditions and environment
states that disallow the behavior from the start. Formally then,

$\mathcal{B}=\\{(x,d)\in\mathcal{X}\times\mathcal{D}~{}|~{}S_{B}(x,d)\neq\varnothing\\}.$
(5)

With these definitions we have the following theorem identifying a framework
to verify behaviors, though to simplify exposition, we will express the
assumptions separately:

######  Assumption 1.

Let $\\{r^{i}=\rho_{B}(\Sigma(x^{i}_{0},d^{i}),d^{i})\\}_{i=1}^{N}$ be the
behavioral robustness of $N$ attempts at executing behavior $B$ from uniformly
sampled initial conditions and states $(x_{0},d)$ over the allowable space
$\mathcal{B}$ as per (5) with robustness measure $\rho$ as per (4), and let
$r^{*}=\min_{i}r^{i}$.

######  Theorem 2.

Let Assumption 1 hold. If $r^{*}=1$, then $\forall~{}\epsilon\in[0,1]$, the
behavior $B$ will execute successfully for at least $100(1-\epsilon)\%$ of the
initial condition and environment pairs in $\mathcal{B}$ and the confidence in
this statement is $1-(1-\epsilon)^{N}$.

Proof: As Assumption 1 satisfies the conditions for Theorem 1, we can employ
the same theorem and get the following result $\forall~{}\epsilon\in[0,1]$ and
substituting $r^{*}=1$:

$\displaystyle\mathbb{C}1$
$\displaystyle\triangleq\operatorname{\mathbb{P}}_{\operatorname{\mathrm{U}}[\mathcal{B}]}[\rho_{B}(\Sigma(x_{0},d),d)\geq
1]\geq 1-\epsilon,$ (6) $\displaystyle\mathbb{C}2$
$\displaystyle\triangleq\operatorname{\mathbb{P}}^{N}_{\operatorname{\mathrm{U}}[\mathcal{B}]}[\mathbb{C}1]\geq
1-(1-\epsilon)^{N}.$

Here, $\operatorname{\mathrm{U}}[\mathcal{B}]$ denotes the uniform
distribution over $\mathcal{B}$. We will analyze $\mathbb{C}1$ first. Note
that in order for $\rho_{B}(\Sigma(x_{0},d),d)\geq 1$, all certificate
functions over the dataset $\mathbb{D}$ generated by running behavior $B$ must
evaluate to $1$ \- a consequence of equations (4) and (3). As a result,

$\rho_{B}(\Sigma(x_{0},d),d)=1\iff\begin{gathered}\mathrm{The~{}behavior~{}executes}\\\
\mathrm{successfully.}\end{gathered}$ (7)

Therefore, we can define a subset of the feasible joint state space,
corresponding to initial conditions and environment states where from and in
the behavior executes successfully:

$\mathbb{V}=\\{(x,d)\in\mathcal{B}~{}|~{}\rho(\Sigma(x,d),d)=1\\}.$ (8)

Similarly, we can define a volume fraction function over the allowable joint
state space:

$\mathcal{V}(Q)=\frac{\int_{Q}1ds}{\int_{\mathcal{B}}1ds}.$ (9)

Finally, since the uniform distribution assigns probabilistic weight to a
subset of events equivalent to their volume fraction in the sample space,
$\mathbb{C}1$ resolves to the following:

$\mathbb{C}1\equiv\mathcal{V}(\mathbb{V})\geq 1-\epsilon.$ (10)

Substituting this equivalency in $\mathbb{C}2$ completes the proof.
$\mathbin{{\rule{5.38193pt}{5.38193pt}}}$

###  III-A Extending to Non-Deterministic Behaviors

In the prior sections, we only considered deterministic system evolution and
behavior graph resolution. However, it may be the case that either the system
evolves or the behavior graph resolves non-deterministically. Our proposed
verification framework should account for this non-determinism, and this
section details how the prior procedure extends to this case. We will
formalize this non-determinism directly in the context of verification.
Specifically, we assume that we have a distribution by which we can draw
robustness evaluations of system trajectories, i.e.

$\rho(\Sigma(x_{0},d),d)~{}\mathrm{is~{}sampled~{}from~{}}\pi_{V}$ (11)

Note that this accounts for both cases where the initial system and
environment states are potentially sampled randomly via a distribution
$\pi_{X}$ over the allowable space $\mathcal{B}$ as per (5) and the ensuing
trajectories $\Sigma(x_{0},d)$ are also randomly sampled from some unknown
trajectory-level distribution $\pi_{S}$, arising from the aforementioned non-
deterministic system evolution or behavior graph resolution.

As a result, we can follow the same verification method as in Theorem 1,
though we cannot identify trajectories via initial conditions as we did in
Assumption 1. The following assumption and corollary expresses this notion
formally:

######  Assumption 2.

Let $\rho_{B}$ be the robustness measure for the behavior $B$ as per equation
(4), let $\\{r^{i}=\rho_{B}(\Sigma(x^{i}_{0},d^{i}),d^{i})\\}_{i=1}^{N}$ be
the robustnesses of $N$ trajectories sampled via the (unknown) distribution
$\pi_{V}$, and let $r^{*}=\min_{i}r^{i}$.

######  Corollary 1.

Let Assumption 2 hold. If $r^{*}=1$, then $\forall~{}\epsilon\in[0,1]$, the
non-deterministic system $\Sigma$ successfully executes the behavior $B$ with
minimum probability $1-\epsilon$ and confidence $1-(1-\epsilon)^{N}$, i.e.:

$\operatorname{\mathbb{P}}^{N}_{\pi_{V}}\left[\operatorname{\mathbb{P}}_{\pi_{V}}[\rho(\Sigma(x_{0},d),d)\geq
r^{*}]\geq 1-\epsilon\right]\geq 1-(1-\epsilon)^{N}.$ (12)

Proof: This is a direct result of Theorem 1.
$\mathbin{{\rule{5.38193pt}{5.38193pt}}}$

##  IV Demonstrations

###  IV-A Exploratory Behavior Generation

To illustrate the verifiability of behaviors generated via Algorithm 1, this
section will detail our efforts at using a natural language abstractor built
on ChatGPT to construct an exploratory behavior.

System and Environment Description: To that end, the simulations to follow
feature an agent idealized as a single integrator system on the plane and
navigating within a $10\times 10$ grid with obstacles and a few goals. The
system state $x$ is its planar position and its labels for each of the cells,
i.e. $x\in[-5,5]^{2}\times\\{$empty, obstacle, unexplored,
goal$\\}^{100}\triangleq\mathcal{X}$. The environment, i.e. obstacle and goal
cells, is the subset of the overall label space where there exist $30$
obstacles and $3$ goals with no overlaps, i.e. $\mathcal{D}\subset$
$\\{$empty, obstacle, goal$\\}^{100}$. The system dynamics as per (1) are
known in this case, with single-integrator dynamics for the planar dimension
and label updates when specifically provided by a controller - otherwise,
labels remain constant.

Motion Primitives: The system has two primitives upon which the natural-
language behavior generalizer can build behaviors. Their descriptions will
follow:

  * $\mathcal{P}^{s}_{1}:$

A label update function that updates the labels in the state $x$ to match the
labels of the cells immediately surrounding the agent, i.e. if the agent were
in cell $(2,3)$ the function updates the labels of cells
$\\{(2,3),(3,3),(1,3),(2,4),(2,2)\\}$.

    * $\Xi:$

The set of all cells, i.e. $\Xi=\\{0,1,2,\dots,9\\}^{2}$.

    * $A:$

A function outputting the cell the system currently occupies, i.e. if the
system’s planar position were $[-4.5,-3.5]$, the only valid parameter is cell
$(0,1)$.

    * $U:$

Updates the state to reflect the environment labels of all adjacent cells.

    * $R:$

A function outputting the portion of the state space where the labels for the
agent’s current and adjacent cells align with those of the environment. All
other cell labels are unconstrained, i.e. if the agent’s current and adjacent
cells were all empty, then $R(\xi,d)$ would output the subset of the state
space containing label vectors whose elements for those cells all read “empty”
with no constraints on other elements.

  * $\mathcal{P}^{s}_{2}:$

A navigation function that steers the agent to a desired cell while avoiding
obstacles.

    * $\Xi:$

The set of all cells, i.e. $\Xi=\\{0,1,2,\dots,9\\}^{2}$.

    * $A:$

A function outputting the portion of the parameter space where the cell is
reachable by the agent in the provided environment.

    * $U:$

A Markov-Decision-based planner tracked by a PD controller that steers the
agent to the desired cell while avoiding obstacles.

    * $R:$

Outputs the portion of the planar state space encompassed by the desired cell,
i.e. if the agent could reach cell $(2,2)$, then $R(\xi=(2,2),d)=[-2,-1]^{2}$.

Algorithm Information: We desired an exploratory behavior whereby the system
searches the grid for a goal and after identifying a goal, oscillates back and
forth between the goal and its starting location at least $5$ times. As useful
information for the task-following algorithm, the inputted information -
string $I$ in Algorithm 1 \- indicated that the language model could use the
following functions when determining edges in the outputted behavior graph:

  * $\mathcal{E}^{s}_{1}:$

A function that outputs as a list, all the cells that have been explored by
the agent thus far, i.e. all cells that have a label other than “unexplored”
in the current state.

  * $\mathcal{E}^{s}_{2}:$

A function that outputs as a list all cells immediately adjacent to the
agent’s currently occupied cell.

  * $\mathcal{E}^{s}_{3}:$

A function that determines whether a goal has been found and outputs the
corresponding cell.

Figure 3: Depiction of the directed behavior graph generated by Algorithm 1
for the example detailed in Section IV-A. The first behavior’s graph is
highlighted in green, the second behavior incorporates the first and the extra
information is the unhighlighted part of the graph. Figure 4: Depiction of the
learned scooping behavior. In this case, the motion was coded previously, but
contingent on the arm’s ability to sense the cups in its environment. As such,
the LLM interface only asked for the end-user to provide that initial
positioning (1) wherein the arm had a high likelihood of sending both cups.
Then the LLM behavior first moves to the desired sensing position (2), calls
the scooping primitive as seen in (3)-(4), and returns to the instructed
sensing position in (5) in case any of the cups shifted during the procedure.
Then the process repeats.

Behavior 1: For the first step, we asked the algorithm to devise a behavior
that explored the grid until it identified a goal. Specifically, the inputted
behavior string $s$ was as follows: “Please construct a function that performs
the following tasks in sequence. First, it searches over all explored cells
that are not obstacles to find the explored cell with the highest number of
unexplored neighbors. Let’s call this identified cell, cell A. Second, it
sends the agent to cell A and identifies the labels of all adjacent cells.
Three, it repeats steps one and two until a goal has been found, at which
point, it stops.” The part of the graph highlighted in green in Figure 3 shows
the generated behavior graph. As part of this generation procedure, it used
two of the provided functions $\mathcal{E}^{s}_{1},\mathcal{E}^{s}_{2}$ to
construct the edge decision function $\mathcal{E}^{s}_{4}$ whose description
will follow:

  * $\mathcal{E}^{s}_{4}:$

A function that searches over all explored cells - the list of explored cells
is provided by $\mathcal{E}^{s}_{1}$ \- and assigns to each cell the number of
its adjacent cells that are unexplored - the list of adjacent cells is
provided by $\mathcal{E}^{s}_{2}$. Reports the first cell in the list with the
maximum number of unexplored neighbors.

Behavior 2: We wanted to build on the prior behavior for the latter half of
our goal, and as such, informed the LLM of the existence of this prior
behavior in the list of existing behaviors denoted as $\mathbb{B}$ in
Algorithm 1. Then, as the user, we requested the following from the LLM:
“Please construct a function that performs the following tasks in sequence.
First, it finds a goal. Second, it moves between the goal and its starting
location 5 times.” The behavior graph for this second behavior is the
unhighlighted graph in Figure 3.

Verification Procedure and Remarks: As Behavior $2$ utilized Behavior $1$,
verifying both amounts to verifying the former. Following the results of
Theorem 2, we recorded a data set $\mathbb{D}$ of parameters, primitives, and
terminal states while running the second behavior. The certificates per
equation (3) amount to checking that updated labels matched their true labels
after running primitive $\mathcal{P}^{s}_{1}$ and checking that the system
occupied the desired cell after running primitive $\mathcal{P}^{s}_{2}$. The
allowable joint state space $\mathcal{B}$ as per (5) was the portion of the
joint space where the system starts in a state $x$ such that at least one goal
is reachable in the corresponding environment $d$. Finally, the verification
procedure uniformly randomly sampled state pairs $(x,d)\in\mathcal{B}$ and
checked the corresponding certificates for each run of the behavior.

After running the second behavior from $100$ randomly sampled initial state
pairs, the behavior terminated successfully every time. As such, by Theorem 2
we expect that the second behavior will run successfully for $95\%$ of
possible state pairs and we are $99.4\%$ confident in this statement - we
generated these numbers by substituting $\epsilon=0.05$ and $N=100$ for
Theorem 2. To validate these statements, we ran the second behavior in $2000$
more sampled environments, and it terminated successfully every time. If we
were incorrect in our prior statement that the behavior would run successfully
for at least $95\%$ of feasible state pairs $(x,d)\in\mathcal{B}$, then we
would have been effectively guaranteed to identify such a failure over the
$2000$ subsequent runs. As we did not, we are confident in our corresponding
statement. Furthermore, while the synthesized behaviors seem rudimentary, they
suffice to indicate that our behavior synthesis scheme produces effective and
verifiable behaviors.

###  IV-B Scooping of Granular Media

Our second demonstration focusing on granular media scooping illustrates the
framework’s utility in helping end-users set up repetitive, verifiable tasks.

System and Environment Description: The scooping problem consists of picking
up material from a donor container and depositing it into a receiver container
using a UR5e $6$-DOF robot arm with a wrist-mounted RealSense depth camera.
While a rudimentary scooping motion has been programmed apriori, it does not
know the environment in which it will be performing this motion - similar to
the situation when a pre-programmed robot has to be initialized for specific
use. The robot’s state $x\in\mathbb{R}^{6}$ is the full pose of the end-
effector, the control input $u$ corresponds to joint rotations, and the
environment $d$ corresponds to the locations and orientations of the donor and
receiver containers and the level and distribution of sand in the donor
container.

Motion Primitives: In this case, the system only has one primitive, the
scooping primitive, described as follows:

  * $\mathcal{P}^{r}:$

A primitive performing a scooping motion from a donor container to a receiver
container.

    * $\Xi:$

The space of feasible end-effector poses where a parameter $\xi\in\Xi$ denotes
the pose in which the robot will sense all objects in the environment to start
the scooping motion.

    * $A:$

A function outputting the space of end-effector poses from which all
containers are in view of the onboard vision system.

    * $U:$

A controller that performs the scooping motion.

    * $R:$

A function that outputs a ball around the provided parameter within which the
end-effector’s pose will lie upon the termination of the scooping motion.

That being said, the acceptance function $A$ is implicitly defined and
impossible to know apriori. Here, we intend for the algorithm to assist the
end-user in selecting a parameter $\xi$ whose validity, i.e. existence in
$A(x,d)~{}\forall~{}(x,d)\in\mathcal{X}\times\mathcal{D}$, can be checked
through the ensuing verification procedure.

Algorithm Information: To assist the user in picking such a parameter $\xi$,
the algorithm was provided an information string $I$ describing a helper
function $\mathcal{E}^{r}_{1}$ that translated and rotated the end-effector a
desired amount. This string also included several examples of natural language
translations to inputs for this function $\mathcal{E}^{r}_{1}$. Additionally,
the string included another function $\mathcal{E}^{r}_{2}$ that saved the end-
effector pose for future reference, and the LLM was told to call this function
if the user deemed the current end-effector pose satisfactory.

Behavior Generation and Verification: The task-model repeatedly queried the
user for end-effector translations and rotations and as to whether or not the
user deemed the current pose sufficient for sensing any placement of
containers. As such, there was no singular behavior prompt $s$. However, as
the resulting behavior repetitively executes the scooping primitive with the
user-provided sensing pose parameter $\xi$, this behavior can be verified by
the results of Corollary 1. To do so, before every scooping motion, we placed
the containers at a computer-generated randomly chosen distance from a pre-
determined set-point. As we are manually placing containers at the pre-
determined locations, there will be noise affecting this placement, though we
assume this noise is independent for successive placements. We will denote
this distribution of container placements via $\pi$. As there is no need to
sample over initial robot states - the system always starts and ends at the
parameterized sensing pose $\xi$ every iteration - we can draw independent
environments - container placements - via our distribution $\pi$ and record
the robot’s ability to perform its scooping motion in each placement. Doing so
for $59$ sampled environments with successful trials each time indicates
according to Corollary 1 that if we continued to sample environments and test
the system accordingly, the system would succeed at least $95\%$ of the time
and we are at least $95\%$ confident in that statement.

##  V Conclusion

We propose a framework by which a natural language abstractor can synthesize
verifiable behaviors as a directed graph over provided motion primitives. To
showcase the increased flexibility and verifiability of the synthesized
behaviors, we instructed the task-following model to construct an exploratory
behavior for a simulated planar agent and a scooping behavior for a robotic
arm. In both cases, the generated behavior was verifiable via the
aforementioned method, and we were able to validate our probabilistic
verification statements in simulation.

## References

  * [1] C. G. Atkeson and S. Schaal, “Robot learning from demonstration,” in _ICML_ , vol. 97. Citeseer, 1997, pp. 12–20.
  * [2] H. Ravichandar, A. S. Polydoros, S. Chernova, and A. Billard, “Recent advances in robot learning from demonstration,” _Annual review of control, robotics, and autonomous systems_ , vol. 3, pp. 297–330, 2020.
  * [3] Z. Zhu and H. Hu, “Robot learning from demonstration in robotic assembly: A survey,” _Robotics_ , vol. 7, no. 2, p. 17, 2018.
  * [4] Y. Lin, S. Ren, M. Clevenger, and Y. Sun, “Learning grasping force from demonstration,” in _2012 IEEE International Conference on Robotics and Automation_. IEEE, 2012, pp. 1526–1531.
  * [5] P. Pastor, H. Hoffmann, T. Asfour, and S. Schaal, “Learning and generalization of motor skills by learning from demonstration,” in _2009 IEEE International Conference on Robotics and Automation_. IEEE, 2009, pp. 763–768.
  * [6] E. Misimi, A. Olofsson, A. Eilertsen, E. R. Øye, and J. R. Mathiassen, “Robotic handling of compliant food objects by robust learning from demonstration,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 6972–6979.
  * [7] O. M. Manyar, Z. McNulty, S. Nikolaidis, and S. K. Gupta, “Inverse reinforcement learning framework for transferring task sequencing policies from humans to robots in manufacturing applications,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 849–856.
  * [8] Y. Wang, R. Xiong, L. Shen, K. Sun, J. Zhang, and L. Qi, “Towards learning from demonstration system for parts assembly: A graph based representation for knowledge,” in _The 4th Annual IEEE International Conference on Cyber Technology in Automation, Control and Intelligent_. IEEE, 2014, pp. 174–179.
  * [9] B. Keller, M. Draelos, K. Zhou, R. Qian, A. N. Kuo, G. Konidaris, K. Hauser, and J. A. Izatt, “Optical coherence tomography-guided robotic ophthalmic microsurgery via reinforcement learning from demonstration,” _IEEE Transactions on Robotics_ , vol. 36, no. 4, pp. 1207–1218, 2020.
  * [10] T. Osa, K. Harada, N. Sugita, and M. Mitsuishi, “Trajectory planning under different initial conditions for surgical task automation by learning from demonstration,” in _2014 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 6507–6513.
  * [11] J. W. Kim, C. He, M. Urias, P. Gehlbach, G. D. Hager, I. Iordachita, and M. Kobilarov, “Autonomously navigating a surgical tool inside the eye by learning from demonstration,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 7351–7357.
  * [12] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” _ACM Comput. Surv._ , vol. 50, no. 2, apr 2017. [Online]. Available: https://doi.org/10.1145/3054912
  * [13] C. Chao, M. Cakmak, and A. L. Thomaz, “Towards grounding concepts for transfer in goal learning from demonstration,” in _2011 IEEE International Conference on Development and Learning (ICDL)_ , vol. 2. IEEE, 2011, pp. 1–6.
  * [14] K. Hausman, Y. Chebotar, S. Schaal, G. Sukhatme, and J. J. Lim, “Multi-modal imitation learning from unstructured demonstrations using generative adversarial nets,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [15] C. Finn, T. Yu, T. Zhang, P. Abbeel, and S. Levine, “One-shot visual imitation learning via meta-learning,” in _Conference on robot learning_. PMLR, 2017, pp. 357–368.
  * [16] D. Driess, F. Xia, M. S. Sajjadi, C. Lynch, A. Chowdhery, B. Ichter, A. Wahid, J. Tompson, Q. Vuong, T. Yu, _et al._ , “Palm-e: An embodied multimodal language model,” _arXiv preprint arXiv:2303.03378_ , 2023.
  * [17] Y. Cui, S. Niekum, A. Gupta, V. Kumar, and A. Rajeswaran, “Can foundation models perform zero-shot task specification for robot manipulation?” in _Learning for Dynamics and Control Conference_. PMLR, 2022, pp. 893–905.
  * [18] D. Shah, A. Sridhar, N. Dashora, K. Stachowicz, K. Black, N. Hirose, and S. Levine, “Vint: A large-scale, multi-task visual navigation backbone with cross-robot generalization,” in _7th Annual Conference on Robot Learning_ , 2023.
  * [19] R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill, _et al._ , “On the opportunities and risks of foundation models,” _arXiv preprint arXiv:2108.07258_ , 2021.
  * [20] S. Vemprala, R. Bonatti, A. Bucker, and A. Kapoor, “Chatgpt for robotics: Design principles and model abilities,” _Microsoft Auton. Syst. Robot. Res_ , vol. 2, p. 20, 2023.
  * [21] F. Stulp, E. Theodorou, M. Kalakrishnan, P. Pastor, L. Righetti, and S. Schaal, “Learning motion primitive goals for robust manipulation,” in _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2011, pp. 325–331.
  * [22] W. Ubellacker and A. D. Ames, “Robust locomotion on legged robots through planning on motion primitive graphs,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 12 142–12 148.
  * [23] P. Akella, W. Ubellacker, and A. D. Ames, “Probabilistic guarantees for nonlinear safety-critical optimal control,” _arXiv preprint arXiv:2303.06258_ , 2023.
  * [24] P. Akella, A. Dixit, M. Ahmadi, J. W. Burdick, and A. D. Ames, “Sample-based bounds for coherent risk measures: Applications to policy synthesis and verification,” _arXiv preprint arXiv:2204.09833_ , 2022.
  * [25] P. Akella, M. Ahmadi, and A. D. Ames, “A scenario approach to risk-aware safety-critical system verification,” _arXiv preprint arXiv:2203.02595_ , 2022.
  * [26] A. Donzé and O. Maler, “Robust satisfaction of temporal logic over real-valued signals,” in _International Conference on Formal Modeling and Analysis of Timed Systems_. Springer, 2010, pp. 92–106.
  * [27] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 8, pp. 3861–3876, 2016.


11footnotetext: P. Godau and P. Kalinowski contributed equally to this
paper.11institutetext: Division of Intelligent Medical Systems (IMSY), German
Cancer Research Center (DKFZ), Heidelberg, Germany 11email:
<EMAIL_ADDRESS>22institutetext: National Center for Tumor
Diseases (NCT), NCT Heidelberg, a partnership between DKFZ and university
medical center Heidelberg 33institutetext: Faculty of Mathematics and Computer
Science, Heidelberg University, Germany 44institutetext: HIDSS4Health -
Helmholtz Information and Data Science School for Health,
Karlsruhe/Heidelberg, Germany 55institutetext: Helmholtz Imaging, German
Cancer Research Center (DKFZ), Germany 66institutetext: Instituto de Ciencias
de la Computación, UBA-CONICET, Argentina 77institutetext: Interactive Machine
Learning Group, German Cancer Research Center (DKFZ), Germany 88institutetext:
Medical Faculty, Heidelberg University, Germany

# Deployment of Image Analysis Algorithms
under Prevalence Shifts

Patrick Godau 11223344⋆⋆ Piotr Kalinowski 1144⋆⋆ Evangelia Christodoulou 11
Annika Reinke 113355 Minu Tizabi 1155 Luciana Ferrer 66 Paul Jäger 5577 Lena
Maier-Hein 1122335588

###### Abstract

Domain gaps are among the most relevant roadblocks in the clinical translation
of machine learning (ML)-based solutions for medical image analysis. While
current research focuses on new training paradigms and network architectures,
little attention is given to the specific effect of prevalence shifts on an
algorithm deployed in practice. Such discrepancies between class frequencies
in the data used for a method’s development/validation and that in its
deployment environment(s) are of great importance, for example in the context
of artificial intelligence (AI) democratization, as disease prevalences may
vary widely across time and location. Our contribution is twofold. First, we
empirically demonstrate the potentially severe consequences of missing
prevalence handling by analyzing (i) the extent of miscalibration, (ii) the
deviation of the decision threshold from the optimum, and (iii) the ability of
validation metrics to reflect neural network performance on the deployment
population as a function of the discrepancy between development and deployment
prevalence. Second, we propose a workflow for prevalence-aware image
classification that uses estimated deployment prevalences to adjust a trained
classifier to a new environment, without requiring additional annotated
deployment data. Comprehensive experiments based on a diverse set of 30
medical classification tasks showcase the benefit of the proposed workflow in
generating better classifier decisions and more reliable performance estimates
compared to current practice.

###### Keywords:

Prevalence shift Medical image classification Generalization Domain Gap.

##  1 Introduction

Figure 1: Summary of contributions. (a) Based on a dataset comprising 30
medical image classification tasks, we show that prevalence shifts between
development data and deployment data engender various problems. (b) Our
workflow for prevalence-aware medical image classification addresses all of
these issues.

Machine learning (ML) has begun revolutionizing many fields of imaging
research and practice. The field of medical image analysis, however, suffers
from a substantial translational gap that sees a large number of
methodological developments fail to reach (clinical) practice and thus stay
short of generating (patient) benefit. A major roadblock are dataset shifts,
situations in which the distributions of data used for algorithm
development/validation and its deployment, differ due to exogenous factors
such as dissimilar cohorts or differences in the acquisition process [8, 40].
In the following, we focus on prevalence shifts, which are highly relevant in
the context of global artificial intelligence (AI) [37]. Common causes for
prevalence shifts include sample selection bias and variations in
environmental factors like season or geography [8, 11, 40]. According to prior
work [11] as well as our own analyses, prevalence handling is especially
crucial in the following steps related to model deployment:

Model re-calibration: After a prevalence shift models need to be re-
calibrated. This has important implications on the decisions made based on
predicted class scores (see next point). Note in this context that deep neural
networks tend not to be calibrated after training in the first place [15].

Decision rule: A decision rule is a strategy transforming continuous predicted
class scores into a single classification decision. Simply using the argmax
operator ignores the theoretical boundary conditions derived from Bayes
theory. Importantly, argmax relies on the predicted class scores to be
calibrated and is thus highly sensitive to prevalence shifts [13].
Furthermore, it only yields the optimal decision for specific metrics.
Analogously, tuned decision rules may not be invariant to prevalence shifts.

Performance assessment: Class frequencies observed in one test set are in
general not representative of those encountered in practice. This implies that
the scores for widely used prevalence-dependent metrics, such as Accuracy, F1
Score, and Matthews Correlation Coefficient (MCC), would substantially differ
when assessed under the prevalence shift towards clinical practice [27].

This importance, however, is not reflected in common image analysis practice.
Through a literature analysis, we found that out of a total of 53 research
works published between 01/2020 and beginning of 03/2023 that used any of the
data included in our study, only one explicitly mentioned re-calibration.
Regarding the most frequently implemented decision rules, roughly three
quarters of publications did not report any strategy, which we strongly assume
to imply use of the default argmax operator. Moreover, both our analysis and
previous work show Accuracy and F1 Score to be among the most frequently used
metrics for assessing classification performance in comparative medical image
analysis [26, 27], indicating that severe performance deviations under
potential prevalence shifts are a widespread threat.

Striving to bridge the translational gap in AI-based medical imaging research
caused by prevalence shifts, our work provides two main contributions: First,
we demonstrate the potential consequences of ignoring prevalence shifts on a
diverse set of medical classification tasks. Second, we assemble a
comprehensive workflow for image classification, which is robust to prevalence
shifts. As a key advantage, our proposal requires only an estimate of the
expected prevalences rather than annotated deployment data and can be applied
to any given black box model.

Figure 2: Medical image classification tasks used in this study. The number of
samples (red) and classes (green) ranges from 1,200 to 121,583 and two to
eight, respectively. The imbalance ratio (blue) varies between 1 and 10.9.

##  2 Methods

###  2.1 Workflow for prevalence-aware image classification

Our workflow combines existing components of validation in a novel manner. As
illustrated in Fig. 1, it leverages estimated deployment prevalences to adjust
an already trained model to a new environment. We use the following
terminology.

Fundamentals: We define a dataset $D:=\\{(x_{i},y_{i})|1\leq i\leq N\\}$ by a
set of $N$ images $x_{i}\in X$ and labels $y_{i}\in Y$ with
$Y=\\{1,\ldots,C\\}$. $P_{D}$ is a $C$-dimensional vector called the
prevalences of $D$, where $P_{D}(k):=|\\{(x_{i},y_{i})\in D|y_{i}=k\\}|/N$ is
the prevalence of class $k\in Y$. The fraction
$\max_{k}\\{P_{D}(k)\\}/\min_{k}\\{P_{D}(k)\\}$ is named the imbalance ratio
(IR) of $D$.

Re-calibration: We refer to the output of a model
$\varphi:X\rightarrow\mathbb{R}^{C}$ before applying the softmax activation as
$\varphi(x)$. It can be re-calibrated by applying a transformation $f$. Taking
the softmax of $\varphi(x)$ (no re-calibration) or of $f(\varphi(x))$, we
obtain predicted class scores $s_{x}$. The probably most popular re-
calibration approach is referred to as “temperature scaling” [15] and requires
only a single parameter $t\in\mathbb{R}$ to be estimated:
$f_{\mathrm{temp}}(\varphi(x))=\varphi(x)/t$. The transformation parameter(s)
is/are learned with minimization of the cross-entropy loss.

Decision rule: A decision rule $d$ is a deterministic algorithm that maps
predicted class scores $s_{x}$ to a final prediction $d(s_{x})\in Y$. The most
widely used decision rule is the argmax operator, although various
alternatives exist [27].

To overcome problems caused by prevalence shifts, we propose the following
workflow (Fig. 1b)

Step 1: Estimate the deployment prevalences: The first step is to estimate the
prevalences in the deployment data $D_{dep}$, e.g., based on medical records,
epidemiological research, or a data-driven approach [23, 32]. The workflow
requires an underlying anticausal connection of image and label, i.e., a label
$y$ causes the image $x$ (e.g., presence of a disease has a visual effect)[8,
11], to be verified at this point.

Step 2: Perform prevalence-aware re-calibration: Given an external factor that
varies $P_{D}$ between development calibration and deployment datasets
$D_{cal}$ and $D_{dep}$ from, we can assume the likelihoods $P(x|y=k)$ to stay
identical for an anticausal problem, ignoring potential manifestation and
acquisition shifts during deployment [8]. Under mild assumptions [23, 41],
weight adaptation in the loss function optimally solves the prevalence shift
for a classifier. In the presence of prevalence shifts, we therefore argue for
adaptation of weights in the cross-entropy loss
$\sum_{i}-w(y_{i})\log(s_{i}(y_{i}))$ according to the expected prevalences;
more precisely, for class $k$ we use the weight
$w(k)=P_{D_{dep}}(k)/P_{D_{cal}}(k)$ during the learning of the transformation
parameters [11, 34, 41]. Furthermore, since temperature scaling’s single
parameter $t$ is incapable of correcting the shift produced by a mismatch in
prevalences, we add a bias term $b\in\mathbb{R}^{C}$ to be estimated alongside
$t$ as suggested by [2, 6, 29]. We refer to this re-calibration approach as
“affine scaling”: $f_{\mathrm{aff}}(\varphi(x))=\varphi(x)/t+b$.

Step 3: Configure validation metric with deployment prevalences: Prevalence-
dependent metrics, such as Accuracy, MCC, or the F1 Score, are widely used in
image analysis due to their many advantages [27]. However, they reflect a
model’s performance only with respect to the specific, currently given
prevalence. This problem can be overcome with the metric Expected Cost (EC)
[13]. In its most general form, we can express EC as
$\mathrm{EC}=\sum_{k}P_{D}(k)\sum_{j}c_{kj}R_{kj}$, where $c_{kj}$ refers to
the “costs” we assign to the decision of classifying a sample of class $k$ as
$j$ and $R_{kj}$ is the fraction of all samples with reference class $k$ that
have been predicted as $j$. Note that the standard 0-1 costs ($c_{kk}=0$ for
all $k$ and $c_{kj}=1$ for $k\neq j$) reduces to EC being 1 minus Accuracy. To
use EC as a robust estimator of performance, we propose replacing the
prevalences $P_{D}(k)$ with those previously estimated in step 1 [13].

Step 4: Set prevalence-aware decision rule: Most counting metrics [27] require
some tuning of the decision rule during model development, as the argmax
operator is generally not the optimal option. This tuning relies on data from
the development phase and the resulting decision rule is likely dependent on
development prevalences and does not generalize (see Sec. 3). On the other
hand, EC, as long as the predicted class scores are calibrated, yields the
optimal decision rule $\mathrm{argmin}_{k}\sum_{j}c_{jk}s_{x}(j)$ [3, 16]. For
standard 0-1 costs, this simplifies to the argmax operator.

Step 5: External validation: The proposed steps for prevalence-aware image
classification have strong theoretical guarantees, but additional validation
on the actual data of the new environment is indispensable for monitoring
[33].

###  2.2 Experimental design

The purpose of our experiments was twofold: (1) to quantify the effect of
ignoring prevalence shifts when validating and deploying models and (2) to
show the value of the proposed workflow. The code for our experiments is
available at https://github.com/IMSY-DKFZ/prevalence-shifts.

####  2.2.1 Medical image classification tasks

To gather a wide range of image classification tasks for our study, we
identified medical image analysis tasks that are publicly available and
provide at least 1000 samples. This resulted in 30 tasks covering the
modalities laparoscopy [22, 38], gastroscopy/colonoscopy [5, 30], magnetic
resonance imaging (MRI)[4, 9], X-ray [1, 18, 20, 31], fundus photography [24],
capsule endoscopy[35], and microscopy [14] (Fig. 2). We split each task as
follows: 30% of the data – referred to as “deployment test set” $D_{dep}$ –
was used as a hold-out split to sample subsets $D_{dep}(r)$ representing a
deployment scenario with IR r. The remaining data set made up the “development
data“, comprising the “development test set” $D_{test}$ (10%; class-balanced)
, the “training set” (50%) and the “validation set” (10%; also used for
calibration).

####  2.2.2 Experiments

For all experiments, the same neural network models served as the basis. To
mimic a prevalence shift, we sub-sampled datasets $D_{dep}(r)$ from the
deployment test sets $D_{dep}$ according to IRs $r\in[1,10]$ with a step size
of $0.5$. The experiments were performed with the popular prevalence-dependent
metrics Accuracy, MCC, and F1 Score, as the well as EC with 0-1 costs. For our
empirical analyses, we trained neural networks (specifications: see Tab.
LABEL:tab:models Suppl.) for all 30 classification tasks introduced in Sec.
2.2.1. In the interest of better reproducibility and interpretability, we
focused on a homogeneous workflow (e.g., by fixing hyperparameters across
tasks) rather than aiming to achieve the best possible Accuracy for each
individual task. The following three experiments were performed. (1) To assess
the effects of prevalence shifts on model calibration, we measured
miscalibration on the deployment test set $D_{dep}(r)$ as a function of the
increasing IR r for five scenarios: no re-calibration, temperature scaling,
and affine scaling (the latter two with and without weight adaptation).
Furthermore, (2) to assess the effects of prevalence shifts on the decision
rule, for the 24 binary tasks, we computed – with and without re-calibration
and for varying IR r – the differences between the metric scores on
$D_{dep}(r)$ corresponding to an optimal decision rule and two other decision
rules: argmax and a cutoff that was tuned on $D_{test}$. Lastly, (3) to assess
the effects of prevalence shifts on the generalizability of validation
results, we measured the absolute difference between the metric scores
obtained on the development test data $D_{test}$ and those obtained on the
deployment test data $D_{dep}(r)$ with varying IR r. The scores were computed
for the argmax decision rule for both non-re-calibrated and re-calibrated
predicted class scores. To account for potential uncertainty in estimating
deployment prevalences, we repeated all experiments with slight perturbation
of the true prevalences. To this end, we drew the prevalence for each class
from a normal distribution with a mean equal to the real class prevalence and
fixed standard deviation (std). We then set a minimal score of 0.01 for each
class and normalized the resulting distribution.

##  3 Results

Figure 3: Effect of prevalence shifts on the calibration. The class-wise
calibration error (CWCE) generally increases with an increasing prevalence
shift from development (balanced) to deployment test set. Left: Mean (line)
and standard deviation (shaded area) obtained from n = 30 medical
classification tasks. Right: CWCE values for all tasks at imbalance ratio 10.
Figure 4: Effect of prevalence shifts on the decision rule. The difference
between the actual metric score and the optimal metric score (optimal decision
rule) is shown as a function of the imbalance ratio for non-re-calibrated
(left) and re-calibrated (right) models for two decision rule strategies:
argmax (top) and threshold optimization on the development test set (bottom).
Mean (lines) and standard deviation (transparent area) obtained from n=24
binary tasks.

Effects of prevalence shifts on model calibration In general, the calibration
error increases with an increasing discrepancy between the class prevalences
in the development and the deployment setting (Fig. 3). The results clearly
demonstrate that a simple accuracy-preserving temperature scaling-based method
is not sufficient under prevalence shifts. Only our proposed method, which
combines an affine transformation with a prevalence-driven weight adjustment,
consistently features good calibration performance. This also holds true when
perturbing the deployment prevalences, as demonstrated in Fig.
LABEL:fig:sup:calibration_perturb (Suppl.). For the inspected range (up to
r=10), miscalibration can be kept constantly close to 0. Note that CWCE is a
biased estimator of the canonical calibration error [27], which is why we
additionally report the Brier Score (BS) as an overall performance measure
(Fig. LABEL:fig:sup:calibration_metrics Suppl.).

Effects of prevalence shifts on the decision rule Fig. 4 supports our
proposal: An argmax-based decision informed by calibrated predicted class
scores (top right) and assessed with the Expected Cost (EC) metric (identical
to the blue Accuracy line in this case) yields optimal results irrespective of
prevalence shifts. In fact, this approach substantially increases the quality
of the decisions when compared to a baseline without re-calibration, as
indicated by an average relative decrease of EC by 25%. This holds true in a
similar fashion for perturbed versions of the re-calibration (Fig.
LABEL:fig:sup:threshold Suppl.). The results further show that argmax is not
the best decision rule for F1 Score and MCC (Fig. 4 top). Importantly,
decision rules optimized on a development dataset do not generalize to unseen
data under prevalence shifts (Fig. 4 bottom).

Effects of prevalence shifts on the generalizability of validation results As
shown in Fig. 5, large deviations from the metric score obtained on the
development test data of up to 0.41/0.18 (Accuracy), 0.35/0.46 (F1 Score), and
0.27/0.32 (MCC), can be observed for the re-calibrated/non-re-calibrated case.
In contrast, the proposed variation of Expected Cost (EC) enables a reliable
estimation of performance irrespective of prevalence shifts, even when the
prevalences are not known exactly (Fig. LABEL:fig:sup:assessment Suppl.). The
same holds naturally true for the prevalence-independent metrics Balanced
Accuracy (BA) and Area under the Receiver Operating Curve (AUROC) (Fig.
LABEL:fig:sup:assessment Suppl.).

Figure 5: Effect of prevalence shifts on the generalizability of validation
results. The absolute difference of the metric score computed on the
deployment data to that computed on the development test set is shown as a
function of the imbalance ratio (IR) for non-re-calibrated (top) and re-
calibrated (bottom) models. The dot- and boxplots show the results for all
n=30 tasks at a fixed IR of 10.

##  4 Discussion

Important findings, some of which are experimental confirmations of theory,
are:

  1. 1.

Prevalence shifts lead to miscalibration. A weight-adjusted affine re-
calibration based on estimated deployment prevalences compensates for this
effect.

  2. 2.

Argmax should not be used indiscriminately as a decision rule. For the metric
EC and specializations thereof (e.g., Accuracy), optimal decison rules may be
derived from theory, provided that the predicted class scores are calibrated.
This derived rule may coincide with argmax, but for other common metrics (F1
Score, MCC) argmax does not lead to optimal results.

  3. 3.

An optimal decision rule, tuned on a development dataset, does not generalize
to datasets with different prevalences. Prevalence-aware setting of the
decision rule requires data-driven adjustment or selection of a metric with a
Bayes theory-driven optimal decision rule.

  4. 4.

Common prevalence-dependent metrics, such as MCC and F1 Score, do not give
robust estimations of performance under prevalence shifts. EC, with adjusted
prevalences, can be used in these scenarios.

These findings have been confirmed by repeated experiments using multiple
random seeds for dataset splitting and model training. Overall, we present
strong evidence that the so far uncommon metric EC offers key advantages over
established metrics. Due to its strong theoretical foundation and flexibility
in configuration it should, from our perspective, evolve to a default metric
in image classification. Note in this context that while our study clearly
demonstrates the advantages of prevalence-independent metrics, prevalence-
dependent metrics can be much better suited to reflect the clinical interest
[27].

In conclusion, our results clearly demonstrate that ignoring potential
prevalence shifts may lead to suboptimal decisions and poor performance
assessment. In contrast to prior work [25], our proposed workflow solely
requires an estimation of the deployment prevalences – and no actual
deployment data or model modification. It is thus ideally suited for
widespread adoption as a common practice in prevalence-aware image
classification.

####  4.0.1 Acknowledgements

This project has been funded by (i) the German Federal Ministry of Health
under the reference number 2520DAT0P1 as part of the pAItient (Protected
Artificial Intelligence Innovation Environment for Patient Oriented Digital
Health Solutions for developing, testing and evidence based evaluation of
clinical value) project, (ii) HELMHOLTZ IMAGING, a platform of the Helmholtz
Information & Data Science Incubator and (iii) the Helmholtz Association under
the joint research school “HIDSS4Health – Helmholtz Information and Data
Science School for Health” (iv) state funds approved by the State Parliament
of Baden-Württemberg for the Innovation Campus Health + Life Science Alliance
Heidelberg Mannheim.

## References

  * [1] Covid19 x-ray classification dataset on kaggle. https://www.kaggle.com/ahemateja19bec1025/covid-xray-dataset, accessed: 2022-01-13
  * [2] Alexandari, A.M., et al.: Maximum likelihood with bias-corrected calibration is hard-to-beat at label shift adaptation. In: International Conference on Machine Learning (2020)
  * [3] Bishop, C.M.: Pattern recognition and machine learning (information science and statistics) (2006)
  * [4] Bohaju, J.: Brain tumor (2020). https://doi.org/10.34740/KAGGLE/DSV/1370629
  * [5] Borgli, H., et al.: Hyper-kvasir: A comprehensive multi-class image and video dataset for gastrointestinal endoscopy (Dec 2019). https://doi.org/10.31219/osf.io/mkzcq
  * [6] Brummer, N., et al.: On calibration of language recognition scores. 2006 IEEE Odyssey - The Speaker and Language Recognition Workshop pp. 1–8 (2006)
  * [7] Buslaev, A., et al.: Albumentations: Fast and flexible image augmentations. Information 11(2) (2020). https://doi.org/10.3390/info11020125
  * [8] de Castro, D.C., et al.: Causality matters in medical imaging. Nature Communications 11 (2019)
  * [9] Cheng, J.: brain tumor dataset (Apr 2017). https://doi.org/10.6084/m9.figshare.1512427.v5
  * [10] Deng, J., et al.: Imagenet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition (2009)
  * [11] Dockes, J., et al.: Preventing dataset shift from breaking machine-learning biomarkers. GigaScience 10 (2021)
  * [12] Falcon, W., et al.: PyTorch Lightning (Mar 2019). https://doi.org/10.5281/zenodo.3828935, https://github.com/Lightning-AI/lightning
  * [13] Ferrer, L.: Analysis and comparison of classification metrics. ArXiv abs/2209.05355 (2022)
  * [14] Ghamsarian, N., et al.: Relevance-based compression of cataract surgery videos using convolutional neural networks (Oct 2020). https://doi.org/10.1145/3394171.3413658
  * [15] Guo, C., et al.: On calibration of modern neural networks. In: Proceedings of the 34th International Conference on Machine Learning - Volume 70. p. 1321–1330. ICML’17, JMLR.org (2017)
  * [16] Hastie, T.J., et al.: The elements of statistical learning (2001)
  * [17] He, K., et al.: Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2016)
  * [18] Irvin, J., et al.: Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison (2019)
  * [19] Johnson, J.M., et al.: Survey on deep learning with class imbalance. Journal of Big Data 6, 1–54 (2019)
  * [20] Kermany, D.S., et al.: Identifying medical diagnoses and treatable diseases by image-based deep learning. Cell 172(5), 1122–1131.e9 (2018). https://doi.org/10.1016/j.cell.2018.02.010
  * [21] Kingma, D.P., et al.: Adam: A method for stochastic optimization. CoRR abs/1412.6980 (2015)
  * [22] Leibetseder, A., et al.: Lapgyn4: a dataset for 4 automatic content analysis problems in the domain of laparoscopic gynecology. In: Proceedings of the 9th ACM Multimedia Systems Conference, MMSys 2018, Amsterdam, The Netherlands, June 12-15, 2018. pp. 357–362. ACM (2018). https://doi.org/10.1145/3204949.3208127
  * [23] Lipton, Z.C., et al.: Detecting and correcting for label shift with black box predictors. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018\. Proceedings of Machine Learning Research, vol. 80, pp. 3128–3136. PMLR (2018), http://proceedings.mlr.press/v80/lipton18a.html
  * [24] Liu, R., et al.: Deepdrid: Diabetic retinopathy—grading and image quality estimation challenge. Patterns p. 100512 (2022). https://doi.org/https://doi.org/10.1016/j.patter.2022.100512
  * [25] Ma, W., et al.: Test-time adaptation with calibration of medical image classification nets for label distribution shift. In: Medical Image Computing and Computer Assisted Intervention – MICCAI 2022: 25th International Conference, Singapore, September 18–22, 2022, Proceedings, Part III. p. 313–323. Springer-Verlag, Berlin, Heidelberg (2022), https://doi.org/10.1007/978-3-031-16437-8_30
  * [26] Maier-Hein, L., et al.: Why rankings of biomedical image analysis competitions should be interpreted with care. Nature Communications 9 (2018)
  * [27] Maier-Hein, L., et al.: Metrics reloaded: Pitfalls and recommendations for image analysis validation. ArXiv abs/2206.01653 (2022)
  * [28] Paszke, A., et al.: PyTorch: An Imperative Style, High-Performance Deep Learning Library. In: Advances in Neural Information Processing Systems 32. pp. 8024–8035. Curran Associates, Inc. (2019)
  * [29] Platt, J.: Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods (1999)
  * [30] Pogorelov, K., et al.: Nerthus: A bowel preparation quality video dataset. In: Proceedings of the 8th ACM on Multimedia Systems Conference. pp. 170–174. MMSys’17, ACM, New York, NY, USA (2017). https://doi.org/10.1145/3083187.3083216
  * [31] Rajpurkar, P., et al.: MURA dataset: Towards radiologist-level abnormality detection in musculoskeletal radiographs. In: Medical Imaging with Deep Learning (2018), https://openreview.net/forum?id=r1Q98pjiG
  * [32] Saerens, M., et al.: Adjusting the outputs of a classifier to new a priori probabilities: A simple procedure. Neural Computation 14, 21–41 (2002)
  * [33] Saria, S., et al.: Tutorial: Safe and reliable machine learning. ArXiv abs/1904.07204 (2019)
  * [34] Shimodaira, H.: Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference 90, 227–244 (2000)
  * [35] Smedsrud, P.H., et al.: Kvasir-Capsule, a video capsule endoscopy dataset. Scientific Data 8(1), 142 (2021). https://doi.org/10.1038/s41597-021-00920-z
  * [36] Smith, L.N.: Cyclical learning rates for training neural networks. 2017 IEEE Winter Conference on Applications of Computer Vision (WACV) pp. 464–472 (2015)
  * [37] Subbaswamy, A., et al.: From development to deployment: dataset shift, causality, and shift-stable models in health ai. Biostatistics (2019)
  * [38] Twinanda, A.P., et al.: Endonet: A deep architecture for recognition tasks on laparoscopic videos. IEEE Transactions on Medical Imaging 36, 86–97 (2017)
  * [39] Wightman, R.: Pytorch image models. https://github.com/rwightman/pytorch-image-models (2019). https://doi.org/10.5281/zenodo.4414861
  * [40] Zhang, A., et al.: Shifting machine learning for healthcare from development to deployment and from models to data. Nature Biomedical Engineering 6, 1330 – 1345 (2022)
  * [41] Zhang, K., et al.: Domain adaptation under target and conditional shift. In: International Conference on Machine Learning (2013)