#  I Know What You Meant:
Learning Human Objectives by (Under)estimating Their Choice Set

Ananth Jonnavittula and Dylan P. Losey The authors are members of the
Collaborative Robotics Lab (Collab), Dept. of Mechanical Engineering, Virginia
Tech, Blacksburg, VA 24061.
e-mail: {ananth<EMAIL_ADDRESS>
###### Abstract

Assistive robots have the potential to help people perform everyday tasks.
However, these robots first need to learn what it is their user wants them to
do. Teaching assistive robots is hard for inexperienced users, elderly users,
and users living with physical disabilities, since often these individuals are
unable to show the robot their desired behavior. We know that inclusive
learners should give human teachers credit for what they cannot demonstrate.
But today’s robots do the opposite: they assume every user is capable of
providing any demonstration. As a result, these robots learn to mimic the
demonstrated behavior, even when that behavior is not what the human really
meant! Here we propose a different approach to reward learning: robots that
reason about the user’s demonstrations in the context of similar or simpler
alternatives. Unlike prior works — which err towards overestimating the
human’s capabilities — here we err towards underestimating what the human can
input (i.e., their choice set). Our theoretical analysis proves that
underestimating the human’s choice set is risk-averse, with better worst-case
performance than overestimating. We formalize three properties to generate
similar and simpler alternatives. Across simulations and a user study, our
resulting algorithm better extrapolates the human’s objective. See the user
study here: https://youtu.be/RgbH2YULVRo.

##  I Introduction

Figure 1: (Left) User teaches an assistive robot arm to carry coffee upright.
Because of their limitations, this user’s best demonstration unintentionally
tilts the cup. (Middle) When the robot ignores these limitations — and
compares the human’s input to any trajectory — it learns to match the human’s
demonstration and also spill coffee. To make learning more inclusive, we
instead compare the human’s demonstration to simpler and similar trajectories.
(Right) Because these alternatives spill more coffee than the human, the robot
now extrapolates what the user really wanted: keeping the coffee upright.

Imagine that you’re using an assistive robot arm, and you want to teach this
arm to carry a cup of coffee upright. You control the robot’s motion using a
joystick [1, 2, 3]. The robot has many degrees-of-freedom, and — as you
teleoperate the arm to provide your demonstration — you must carefully
orchestrate each joint to keep the coffee upright. It’s possible for a
dexterous, experienced human to teleoperate this task correctly. But you’re
not as skilled with the control interface: because of your limitations the
best you can do is to avoid turning over the cup and spilling all the coffee
(see Fig. 1).

We refer to the set of possible demonstrations that a given human can show the
robot as the human’s choice set [4, 5]. Robots learn what the human wants by
reasoning about the human’s actual demonstrations in the context of this
choice set. For instance, if the human’s demonstrations keep the coffee more
vertical than the alternatives within their choice set, it’s likely that the
human values keeping the coffee upright. Importantly, when we interact with
robots, our choice sets are inherently constrained by our own physical and
cognitive capabilities — and these limitations vary from one person to another
[6, 7, 8]. Take our example: although an expert is able to show a trajectory
with the coffee roughly upright, the best we can do is to keep the cup from
flipping over. Uncertainty over what this choice set is makes it hard for the
robot to learn: did we tilt the coffee because we meant to, or because we were
unable to keep it upright?

Existing work on learning human objectives from demonstrations often ignores
user limitations, and assumes that the human’s choice set includes every
demonstration that is consistent with the robot’s dynamics [9, 10, 11, 12,
13]. This results in robots that learn to match your demonstrated behavior, so
that if all your demonstrations spill some coffee, the robot also learns to
spill. We explore the opposite perspective:

Inclusive robots should assume that the human may have limitations, and can
only show alternative behaviors that are similar to or simpler than their
actual demonstrations.

Returning to our coffee example, now the robot narrows down its estimate of
the human’s choice set to only include the observed human trajectories and
sparse and noisy alternatives. Compared to these alternatives, our actual
demonstrations better keep the cup closer to vertical. Here the robot
extrapolates what we really meant, despite the fact that we spilled coffee in
all our demonstrations (see Fig. 1).

Overall, we make the following contributions:

Underestimating vs. Overestimating Choice Sets. Robots will inevitably get the
human’s choice set wrong. We theoretically compare overestimating the human’s
choice set (i.e., assuming users can provide any demonstration) to
underestimating the human’s choice set (i.e., users can only provide a few
demonstrations). We prove that underestimating is a risk-averse approach with
better worst-case learning.

Generating Choice Sets from Demonstrations. How does the robot get its
estimate of a human’s choice set? Our analysis finds that waiting for human
teachers to demonstrate their choice set is intractable. To address this, we
formalize three properties that robots can leverage to generate trajectories
that are similar to or simpler than the human’s actual choices.

Conducting a User Study. We compare our inclusive approach to state-of-the-art
baselines. Our results suggest that robots which err towards underestimating
the human’s choice set better extrapolate the human’s underlying objective.

##  II Related Work

Application – Assistive Robots. Assistive robots, such as wheelchair-mounted
robot arms, promise to improve the autonomy and independence of users living
with physical disabilities [14]. However, people’s ability to control
assistive robots is often restricted, both by their own physical impairments
and the teleoperation interfaces they leverage [3, 1, 15, 2, 16, 17].
Expecting all users to produce the same demonstrations is unfair [18]. We
therefore develop a personalized approach, where the robot learns from each
user by placing their demonstrations in the context of similar behaviors.

Learning Rewards from Demonstrations. Prior work studies how assistive arms
and other robots can learn from human demonstrations. Inverse reinforcement
learning (IRL) infers what the user wants — i.e., their underlying reward
function — from their demonstrated trajectories. To do this, the robot
searches for the reward function that makes the human’s trajectories appear
roughly optimal [9]. Crucially, today’s methods assume that the human is
optimizing over all possible trajectories; accordingly, when human
demonstrates suboptimal behavior, the robot thinks this behavior is better
than every other option, and learns the reward function that best reproduces
what the human demonstrated [10, 11, 12, 13].

Recent research explores how this learning model misses out on the way humans
actually behave [19, 20, 21]. Most relevant are [4] — where the authors
formalize choice sets in reward learning — and [5] — where the authors
experimentally compare different classes of choice set misspecification. We
also build upon inverse reinforcement learning, but develop a formalism for
generating smaller, constrained choice sets from the human’s demonstrations.

Outperforming Imperfect Demonstrations. Our goal in generating these choice
sets is for robots to learn rewards which better align with what the human
wants than the human’s demonstrations. Other works outperform imperfect and
suboptimal demonstrations by eliciting additional types of human feedback [22,
23, 24, 25, 26]. We do not gather additional feedback; instead, our approach
is most similar to [27, 28, 29]. Here the robot considers noisy perturbations
of the human’s original demonstrations, and extrapolates a reward function
which maximizes the difference between the human’s demonstrations and these
noisy alternatives. Viewed within our formalism, the alternative
demonstrations form the human’s choice set, and leveraging noisy perturbations
becomes one instance of generating this set.

##  III Problem Statement

Let’s return to our motivating example, where we are teleoperating an
assistive robot arm, and want to teach this arm to hold coffee upright. Each
time we guide the robot through the process of picking up, carrying, and
putting down our coffee cup, we show the robot a trajectory
$\xi\in\operatorname{\Xi_{\mathcal{H}}}$. Here $\xi$ is a sequence of robot
state-action pairs, and $\operatorname{\Xi_{\mathcal{H}}}$ is our choice set:
i.e., the set of all trajectories we are capable of showing to the robot. Of
course, the robot does not know what our choice set is — we could be an expert
user, capable of keeping the cup perfectly vertical, or an inexperienced user,
who struggles to keep the cup from flipping over. The robot therefore works
with $\operatorname{\Xi_{\mathcal{R}}}$, an estimate of
$\operatorname{\Xi_{\mathcal{H}}}$.

Over repeated interactions we show the robot $N$ trajectories from our choice
set. Given all of these user demonstrations
$\mathcal{D}=\\{\xi_{1},\xi_{2},\ldots,\xi_{N}\\}$, the robot recovers our
reward function $r_{\theta}(\xi)\rightarrow\mathbb{R}$, i.e., what we want the
robot to optimize for across a trajectory111In our experiments we are
consistent with previous work on inverse reinforcement learning and use
$r_{\theta}(\xi)=\theta\cdot\Phi(\xi)$, where $\Phi(\xi)\in\mathbb{R}^{k}$ are
known features and $\theta\in\mathbb{R}^{k}$ are unknown reward weights [9,
10, 11, 4].. More formally, the robot tries to infer $r_{\theta}$ (what we
value) given $\mathcal{D}$ (the trajectories we have shown) and
$\operatorname{\Xi_{\mathcal{R}}}$ (the trajectories the robot thinks we can
show).

Bayesian Inference. Let belief $b$ denote the robot’s learned probability
distribution over $r_{\theta}$. Applying Bayes’ Theorem:

$b(r_{\theta})=P(r_{\theta}\mid\mathcal{D},\operatorname{\Xi_{\mathcal{R}}})\propto
P(\mathcal{D}\mid r_{\theta},\operatorname{\Xi_{\mathcal{R}}})\cdot
P(r_{\theta})$ (1)

where $P(r_{\theta})$ is the robot’s prior over the human’s reward. Since we
assume the human’s demonstrations are conditionally independent [9, 24],
Equation (1) simplifies to:

$b(r_{\theta})\propto P(r_{\theta})\prod_{\xi\in\mathcal{D}}P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{R}}})$ (2)

The crucial term is $P(\xi\mid r_{\theta},\operatorname{\Xi_{\mathcal{R}}})$,
the likelihood of observing $\xi$ given that the human has reward $r_{\theta}$
and choice set $\operatorname{\Xi_{\mathcal{R}}}$. Within robot learning [11]
and cognitive science [30], this is commonly written using a Boltzmann-
rational model:

$P(\xi\mid r_{\theta},\operatorname{\Xi_{\mathcal{R}}})=\frac{\exp{(\beta\cdot
r_{\theta}(\xi))}}{\sum_{\xi^{\prime}\in\operatorname{\Xi_{\mathcal{R}}}}\exp{(\beta\cdot
r_{\theta}(\xi^{\prime}))}}$ (3)

Intuitively, this model asserts that a rational human picks the trajectory
from their choice set that noisily maximizes their reward, and the
hyperparameter $\beta\geq 0$ captures how close-to-rational the human is.
Substituting this likelihood function into Equation (2), we arrive at the
robot’s learning rule:

$b(r_{\theta})\propto\frac{\exp{(\beta\cdot\sum_{\xi\in\mathcal{D}}r_{\theta}(\xi))}}{\big{(}\sum_{\xi^{\prime}\in\operatorname{\Xi_{\mathcal{R}}}}\exp{(\beta\cdot
r_{\theta}(\xi^{\prime}))}\big{)}^{N}}\cdot P(r_{\theta})$ (4)

Importance of Choice Sets. When the robot misunderstands the human’s choice
set (i.e,
$\operatorname{\Xi_{\mathcal{R}}}\neq\operatorname{\Xi_{\mathcal{H}}}$) this
learning rule may spectacularly fail. Imagine that the robot from Fig. 1 has a
uniform prior over two opposite rewards that optimize for staying upright
($r_{upright}$) or spilling coffee ($r_{spill}$). As an inexperienced user the
best we can do is to spill at least $75\%$ of the coffee, and we demonstrate
this $\xi$ to the robot — hoping the robot will recognize our limitations and
learn $r_{upright}$. However, the robot overestimates our capabilities. Let
$\operatorname{\Xi_{\mathcal{R}}}$ include a full spectrum of trajectories,
from spilling the entire cup to spilling none at all: importantly, our $\xi$
pours more coffee than most of these alternatives in
$\operatorname{\Xi_{\mathcal{R}}}$. Hence, if we apply Equation (4) with this
choice set, for any $\beta>0$ the robot believes $r_{spill}$ is actually what
we wanted to optimize. The robot gets it wrong here because it incorrectly
estimates what trajectories the human can input.

##  IV Theoretical Analysis

The problem is that robots will inevitably get the human’s choice set wrong.
This is especially true in assistive robotics, where physical and control
limitations vary greatly from one user to another [3]. If we are doomed to
mistake $\operatorname{\Xi_{\mathcal{H}}}$, on which side should we err? One
option is to overestimate the choices that the human can make, such that
$\operatorname{\Xi_{\mathcal{R}}}\supseteq\operatorname{\Xi_{\mathcal{H}}}$.
This is traditionally done in inverse reinforcement learning, where
$\operatorname{\Xi_{\mathcal{R}}}$ includes all feasible trajectories [10, 11,
12, 13]. By contrast, our insight is to err towards underestimating the
human’s capabilities, such that
$\operatorname{\Xi_{\mathcal{R}}}\subseteq\operatorname{\Xi_{\mathcal{H}}}$.
In this section we analyze the pros and cons of each approach.

Assumptions. To better understand how the system behaves at the limit, we
assume that the human is perfectly rational, and always inputs the
$\xi\in\operatorname{\Xi_{\mathcal{H}}}$ that maximizes their reward (i.e.,
$\beta\rightarrow\infty$). We further assume that the human’s choice $\xi$ is
an element of $\operatorname{\Xi_{\mathcal{R}}}$: because the robot observes
$\xi$ prior to learning, it is trivial to add $\xi$ to
$\operatorname{\Xi_{\mathcal{R}}}$ if it is not already included. Finally, for
the sake of clarity, we assume that the mapping from trajectories $\xi$ to
rewards $r_{\theta}(\xi)$ is injective.

In practice, putting these assumptions together with Equation (3) implies that
either $P(\xi\mid r_{\theta},\operatorname{\Xi_{\mathcal{R}}})=1$ (if
$\xi\in\operatorname{\Xi_{\mathcal{R}}}$ maximizes $r_{\theta}$) or $P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{R}}})=0$ (if
$\xi\in\operatorname{\Xi_{\mathcal{R}}}$ does not maximize $r_{\theta}$).
These assumptions are purely for analysis, and are removed in our simulations
and user study.

###  IV-A Risk-Sensitivity and Learning

In the context of learning with Equation (4), one definition of risk relates
to confidence. A risk-seeking robot becomes confident in its estimate of
$r_{\theta}$ after just a few demonstrations, while a risk-averse robot
remains uncertain even when many demonstrations are available. We quantify
this confidence as the Shannon entropy over the robot’s belief $b$ [31].

But how confident should the robot actually be? Our point of reference is an
ideal leaner that knows $\operatorname{\Xi_{\mathcal{H}}}$. This is the gold
standard, because if we knew $\operatorname{\Xi_{\mathcal{H}}}$, we’d always
have the right context for learning from the human’s demonstrations. We
therefore define risk as the difference between the robot’s actual entropy and
the gold standard entropy. A risk-seeking robot has less entropy than the gold
standard (indicating it is overly confident in its estimate) while a risk-
averse robot has more entropy than the gold standard (indicating it is being
unnecessarily conservative).

We find that how we estimate the choice set affects risk:

Proposition 1. Robots which overestimate the human’s capabilities are risk-
seeking, while robots which underestimate the human’s choice set are risk-
averse.

Proof. Let $\xi\in\mathcal{D}$ be an observed human demonstration. When the
robot overestimates the human’s capabilities,
$\operatorname{\Xi_{\mathcal{R}}}\supseteq\operatorname{\Xi_{\mathcal{H}}}$.
This increases the denominator of Equation (3), so that $P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{R}}})\leq P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{H}}})$ for all $r$. But from our
assumptions we know that $P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{R}}})$ is either $0$ or $1$. Thus,
$\operatorname{\Xi_{\mathcal{R}}}\supseteq\operatorname{\Xi_{\mathcal{H}}}$
concentrates the robot’s belief $b$ around the same or fewer rewards than if
$\operatorname{\Xi_{\mathcal{R}}}=\operatorname{\Xi_{\mathcal{H}}}$.

Conversely, if the robot underestimates the human’s capabilities,
$\operatorname{\Xi_{\mathcal{R}}}\subseteq\operatorname{\Xi_{\mathcal{H}}}$.
Removing choices decreases the denominator of Equation (3), so that $P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{R}}})\geq P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{H}}})$ for all $r_{\theta}$. Hence,
$\operatorname{\Xi_{\mathcal{R}}}\subseteq\operatorname{\Xi_{\mathcal{H}}}$
distributes the robot’s belief $b$ around the same or more rewards than if
$\operatorname{\Xi_{\mathcal{R}}}=\operatorname{\Xi_{\mathcal{H}}}$. $\square$

To see this in action let’s return to our motivating example, where we input a
trajectory which spills some coffee. If the robot overestimates our
capabilities, the robot becomes confident that we are optimizing for spilling,
since there are better trajectories to choose if we preferred to keep the cup
upright. But a robot that underestimates our capabilities is not as quick to
eliminate other explanations. This robot realizes that the trajectory we have
shown is our best choice if we intend to spill some coffee, as well as our
best choice for spilling no coffee at all. Hence, the risk-averse robot thinks
both of these rewards are still likely.

###  IV-B Worst-Case Learning

Next let’s look at the worst that could happen when we get the human’s choice
set wrong. We’ll think about this error in terms of Equation (4), where the
robot learns the likelihood of each reward. In the best case the robot learns
the human’s true reward $r_{\theta}$, so that $b(r_{\theta})=1$.

The worst-case depends on how we estimate $\operatorname{\Xi_{\mathcal{H}}}$:

Proposition 2. In the worst case, robots that overestimate the human’s
capabilities learn the wrong reward.

Proof. The rational human chooses $\xi\in\operatorname{\Xi_{\mathcal{H}}}$ to
maximize their reward $r_{\theta}$. But
$\operatorname{\Xi_{\mathcal{R}}}\supset\operatorname{\Xi_{\mathcal{H}}}$, and
in $\operatorname{\Xi_{\mathcal{R}}}$ there might be another trajectory
$\xi^{\prime}$ where $r_{\theta}(\xi^{\prime})>r_{\theta}(\xi)$. So the
human’s choice $\xi$ does not maximize reward for $r_{\theta}$; instead,
$\xi\in\operatorname{\Xi_{\mathcal{R}}}$ is the best choice for reward
$r_{\theta}^{\prime}$. Here $b(r_{\theta}^{\prime})=1$ and $b(r_{\theta})=0$.
$\square$

Proposition 3. In the worst case, robots that underestimate the human’s
capabilities learn nothing from demonstrations.

Proof. The rational human chooses $\xi\in\operatorname{\Xi_{\mathcal{H}}}$ to
maximize $r_{\theta}$. But
$\operatorname{\Xi_{\mathcal{R}}}\subset\operatorname{\Xi_{\mathcal{H}}}$ only
contains this single choice, $\operatorname{\Xi_{\mathcal{R}}}=\\{\xi\\}$. So
while $\xi\in\operatorname{\Xi_{\mathcal{R}}}$ is the best choice for reward
$r_{\theta}$, it is also the best choice for all other rewards. Now
${P(\xi\mid r_{\theta},\operatorname{\Xi_{\mathcal{R}}})=1}$ for every reward,
and $b(r_{\theta})=P(r_{\theta})$. $\square$

We can intuitively connect this worst-case performance to our earlier analysis
of risk-sensitivity. Robots that overestimate the human’s capabilities are
risk-seeking, and quickly become overconfident in the reward they have
learned. When these risky robots get it wrong — for instance, thinking we want
to spill the coffee — they commit to their mistakes, resulting in complete
confidence in the wrong reward. Robots that underestimate the human’s choice
set err in the opposite direction. These risk-averse robots play it safe, and
maintain several possible explanations for the human’s behavior. When these
conservative robots are overly cautious — e.g., severely underestimating our
capabilities — they ignore the information our demonstrations actually
contain.

###  IV-C Can We Rely on Human Teachers?

To avoid this worst-case performance, one option is to rely on the human to
show the robot their choice set. Every time the human teleoperates the robot
along a trajectory $\xi$, they are showing the robot another element of
$\operatorname{\Xi_{\mathcal{H}}}$. A naïve robot may assume that — given
enough time — the human will demonstrate all the trajectories they are capable
of inputting. Using this wait-and-see approach, the robot sets
$\operatorname{\Xi_{\mathcal{R}}}=\mathcal{D}$.

The problem here is that the user isn’t picking $\xi$ to convey their choice
set; instead, the human is inputting trajectories to teach the robot.
Referring back to Equation (3), the human chooses
$\xi\in\operatorname{\Xi_{\mathcal{H}}}$ to noisily maximize their reward $r$.
When users follow this Boltzmann-rational model, passively waiting for the
user to show a diverse set of choices from $\operatorname{\Xi_{\mathcal{H}}}$
becomes prohibitively time consuming:

Proposition 4. If we normalize the rewards over
$\operatorname{\Xi_{\mathcal{H}}}$ between $0$ and $1$, the probability that
the human will show a minimal reward trajectory $\xi$ in $N$ demonstrations is
bounded by:

$P(\xi\in\mathcal{D})\leq
1-\Bigg{[}\frac{|\operatorname{\Xi_{\mathcal{H}}}|-2+\exp{\beta}}{|\operatorname{\Xi_{\mathcal{H}}}|-1+\exp{\beta}}\Bigg{]}^{N}$
(5)

Proof. We seek to maximize Equation (3) when $r_{\theta}(\xi)=0$ and there
exists at least one $\xi^{\prime}$ where $r_{\theta}(\xi^{\prime})=1$. To do
this we minimize the denominator, which occurs when
$r_{\theta}(\xi^{\prime})=1$ only once and $0$ otherwise. Now $P(\xi\mid
r_{\theta},\operatorname{\Xi_{\mathcal{H}}})=1/(\exp{\beta}+|\operatorname{\Xi_{\mathcal{H}}}|-1)$,
and the probability of not picking $\xi$ during the current interaction is
$1-P(\xi\mid r_{\theta},\operatorname{\Xi_{\mathcal{H}}})$. $\square$

Jumping back to the motivating example, let’s say there are
$|\operatorname{\Xi_{\mathcal{H}}}|=2$ different types of trajectories we can
demonstrate: either tilting the mug or completely flipping it over. For a
Boltzmann-rational human teacher with $\beta=5$, even if the robot waits for
$50$ demonstrations, there is at most a $29\%$ likelihood that the human
demonstrates flipping the cup over. Hence, when humans are optimizing for
teaching, we cannot rely on them to convey their choice set to the robot.

##  V Generating the Choice Set

The last section explored how underestimating or overestimating the human’s
choice set affects reward learning — but how does the robot estimate this
choice set in the first place? Although we can’t rely on the human to show us
the entire $\operatorname{\Xi_{\mathcal{H}}}$ (see Proposition 4), we can
still leverage the choices the human makes. To estimate
$\operatorname{\Xi_{\mathcal{H}}}$ from an individual user’s demonstrations,
we apply our insight: $\operatorname{\Xi_{\mathcal{H}}}$ only includes
trajectories that are similar to or simpler than $\mathcal{D}$. Unlike prior
work, this approach errs towards underestimating (i.e.,
$\operatorname{\Xi_{\mathcal{R}}}\subseteq\operatorname{\Xi_{\mathcal{H}}}$),
since we are implicitly assuming that the user’s demonstrations are the limits
of their capabilities.

In what follows we formalize three properties that result in similar and
simpler trajectories. These properties are not meant to be an exhaustive list,
but rather a starting point for generating intuitive and inclusive choice
sets.

Noisy Deformations. When humans teleoperate robots they make minor mistakes:
e.g., unintentionally pressing the joystick up instead of right. We capture
these local perturbations as noisy trajectory deformations. Let $\sigma\sim
p(\cdot)$ be a noise parameter. After sampling $\sigma$, we deform the human
trajectory $\xi\in\mathcal{D}$ to get a similar alternative:
$\xi^{\prime}=f(\xi,\sigma)$. One concrete way to deform the human’s
trajectory is $\xi^{\prime}=\xi+A\sigma$, where $A$ defines the deformation
shape [32]. In practice, this produces alternate trajectories the user could
have input if they made small, stochastic changes to their inputs.

Algorithm 1 Inclusive reward learning from demonstrations

1:Collect human demonstrations:
$\mathcal{D}=\\{\xi_{1},\xi_{2},\ldots,\xi_{N}\\}$

2:Initialize estimate of human’s choice set:
$\operatorname{\Xi_{\mathcal{R}}}=\mathcal{D}$

3:for $\xi\in\mathcal{D}$ do

4: Generate counterfactual $\xi^{\prime}$ from $\xi$

5: Add the resulting trajectory $\xi^{\prime}$ to
$\operatorname{\Xi_{\mathcal{R}}}$

6:end for

7:Update robot’s belief given $\mathcal{D}$ and
$\operatorname{\Xi_{\mathcal{R}}}$:
$P(r_{\theta}\mid\mathcal{D},\operatorname{\Xi_{\mathcal{R}}})\propto\frac{\exp{(\beta\cdot\sum_{\xi\in\mathcal{D}}r_{\theta}(\xi))}}{\big{(}\sum_{\xi^{\prime}\in\operatorname{\Xi_{\mathcal{R}}}}\exp{(\beta\cdot
r_{\theta}(\xi^{\prime}))}\big{)}^{N}}\cdot P(r_{\theta})$

Sparse Inputs. To guide the robot throughout the process of picking up,
carrying, and placing a coffee cup, the user must input a complex sequence of
teleoperation commands. Each of these individual inputs requires user effort
and intention. Hence, we hypothesize that some simpler trajectories are the
result of less user oversight. Let $u$ be a human teleoperation input, let
$U=[u^{1},u^{2},\ldots]$ be the sequence of human inputs, and let
$g(U)\rightarrow\xi^{\prime}$ be the trajectory that results from input
sequence $U$. Formally, this property searches for trajectories that are
similar to $\xi\in\mathcal{D}$ but produced by sparser inputs:

$\xi^{\prime}=g(U^{*}),\quad U^{*}=\text{arg}\min\leavevmode\nobreak\
\|\xi-g(U)\|^{2}+\lambda\cdot\|U\|_{1}^{2}$ (6)

where scalar $\lambda>0$ determines the relative trade-off between trajectory
similarity and input sparsity.

Consistent Inputs. Precisely controlling the robot arm often requires rapidly
changing inputs: e.g., adjusting the position of the cup, then rotating the
cup upright, and then fixing its position again [19]. Instead of expecting the
user to make all of these different commands, we recognize that it is easier
to maintain consistent inputs. Using the same notation from the last property,
we now search for similar trajectories where the user minimizes their changes
in teleoperation input:

$\quad U^{*}=\text{arg}\min\leavevmode\nobreak\
\|\xi-g(U)\|^{2}+\lambda\cdot\sum\|u^{t}-u^{t-1}\|^{2}$ (7)

Solving Equation (7) outputs trajectories $\xi^{\prime}=g(U^{*})$ where the
human inputs are held roughly constant.

Algorithm. The listed properties produce counterfactuals: i.e., what would
have happened if the human was more noisy, more sparse, or more consistent. In
Algorithm 1 we add these trajectories to $\operatorname{\Xi_{\mathcal{R}}}$
before leveraging our learning rule from Equation (4), where
$\operatorname{\Xi_{\mathcal{R}}}$ determines the partition function. Overall,
Algorithm 1 learns from human demonstrations by comparing $\mathcal{D}$ only
to a personalized choice set that we are confident the human is capable of
inputting.

##  VI Simulations

Figure 2: Simulated users with different levels of rationality ($\beta$)
interact in four environments. (Left) The robot’s learned belief in the
human’s true reward. Higher values indicate the robot has learned what the
human really meant. (Right) The robot’s confidence over its learned belief.
Robots with less entropy than Ideal are overconfident in their prediction
(risk-seeking), while robots that have more entropy are overly cautious (risk-
averse).

In this section we apply our learning algorithm across a spectrum of simulated
humans with different levels of rationality ($\beta$). To better relate these
findings to our theoretical results, for now we assume a discrete set of
possible reward functions (we will move to a continuous hypothesis space in
the subsequent user study).

Baselines. We compare Algorithm 1 (Ours) to three baselines. First we consider
a hypothetical world (Ideal) where the robot knows exactly what the human’s
choice set is
($\operatorname{\Xi_{\mathcal{R}}}=\operatorname{\Xi_{\mathcal{H}}}$). Next,
we test Bayesian inverse reinforcement learning (BIRL) where the robot assumes
the human is capable of providing any demonstration [12]. This leads to
$\operatorname{\Xi_{\mathcal{R}}}\supseteq\operatorname{\Xi_{\mathcal{H}}}$.
Finally, we implement a robot that compares human demonstrations to noisy
alternatives (Noise). This method is a modified version of D-REX [27] without
ranking feedback, and can be seen as an instance of our formalism where the
only counterfactuals are noisy deformations.

Figure 3: Human demonstrations and objective results from our user study.
(Top) Example user demonstrations and desired behavior for three different
tasks. In each task the user is faced with a different challenge that prevents
them from inputting their desired behavior. (Bottom) When the robot errs
towards towards underestimating the human’s capabilities (Ours), it
extrapolates what the human really wants from their limited demonstrations.
This results in a more accurate estimate of the human’s true reward and lower
regret across the robot’s learned behavior. Error bars indicate standard error
about the mean.

Environments. We simulate humans with various limitations and test our
algorithm across four learning environments (see Fig. 2). In Lavaworld the
human teleoperates a 2D point mass towards a goal. The human wants to avoid
lava, but has a limited range of visibility around the point mass. In Cartpole
the human tries to keep an inverted pendulum upright, and in Lander the human
lands a craft on the surface of the moon (OpenAI Gym [33]). Within both
Cartpole and Lander we limit how frequently the simulated human can change
their input to mimic the response time of actual users. Finally, in Swarm the
human navigates an obstacle course with three race cars (developed in Pybullet
[34]). All three cars move simultaneously, but we limit the user to only
control one car at a time. For each environment we hand-coded a discrete set
of possible reward functions.

Results.  In Fig. 2 we compute the robot’s belief using Equation (4) and then
evaluate the Shannon entropy of that belief. We find that robots using Ours
extrapolate what the human really wanted from their suboptimal demonstrations.
Across a spectrum of different environments and different types of simulated
users, we also find that robots which overestimate the human’s choice set
(BIRL) are risk-seeking, while robots which underestimate the human’s choice
set (Noise, Ours) are risk-averse.

##  VII User Study

Motivated by the application of assistive robotics we designed a user study
with three manipulation tasks. Participants teleoperated a $7$-DoF robot
(Franka Emika) using a $2$-DoF joystick. Users were unable to fully
demonstrate what they wanted because of challenges and limitations when
controlling the robot (Fig. 3). Here the robot had a continuous space of
rewards $r_{\theta}(\xi)=\theta\cdot\Phi(\xi)$, and our proposed approach
leveraged Algortihm 1 with Metropolis–Hastings sampling to estimate the
human’s true reward weights $\theta\in\mathbb{R}^{k}$.

Experimental Setup. Each participant attempted to demonstrate three
manipulation tasks. In Constraint, users needed to drop-off trash in a waste
bin. The bin was placed behind an obstacle that the robot must rotate around,
but users could only control the end-effector’s position. In Precision, users
needed to carefully stack a marker. This was challenging because noise was
injected into the robot’s motion. Finally, Coupling is our motivational task
from Fig. 1, where users teach the robot to carry coffee upright. Here the
robot’s translation was coupled with its rotation, so that moving the robot
across the table caused the cup to inadvertently tilt.

Independent Variables.  Participants first provided 3-5 teleoperated
demonstrations $\mathcal{D}$ for each task. We then compared what the robot
learned with three different methods: BIRL [12], Noise [27], and Ours
(Algorithm 1). BIRL assumes the human can provide any demonstration, while
Noise and Ours err towards underestimating the human’s capabilities.

Dependent Measures – Objective. We obtained the Error
$\|\theta-\hat{\theta}\|$ between the true reward weights $\theta$ and the
mean of the estimated reward weights $\hat{\theta}$. We also computed Regret:
$r_{\theta}(\xi^{*})-r_{\theta}(\xi_{\mathcal{R}})$. Here $\xi^{*}$ is the
trajectory that maximizes $r_{\theta}$, and $\xi_{\mathcal{R}}$ is the robot’s
learned trajectory which maximizes $r_{\hat{\theta}}$. If the robot learns
what the human really wants, $\xi_{\mathcal{R}}=\xi^{*}$.

Dependent Measures – Subjective. We administered a 7-point Likert scale survey
after showing users what the robot learned (see Fig. 4). Questions were
organized along five scales: how confident users were that the robot Learned
their objective, how Intuitive the robot’s behavior was, whether the robot
Extrapolated from their demonstrations, how trustworthy users thought the
robot was (Deploy), and whether they would use the shown method again
(Prefer).

Participants and Procedure. We recruited $10$ subjects from the Virginia Tech
student body to participate in our study ($4$ female, average age $22\pm 3$
years). All subjects provided informed written consent prior to the
experiment. We used a within-subjects design, where we counterbalanced the
order of learning algorithms.

Hypothesis.  When human teachers face limitations, robots that learn from
similar and simpler alternatives best extract what the human wants, and are
preferred by users.

Results – Objective. Our objective results for each task are displayed in Fig.
3. Lower errors indicate the robot’s reward estimate approaches the true
reward, while lower regret shows that the robot’s resulting behavior matches
the desired trajectory. With BIRL, the robot learned to replicate what the
human demonstrated. But because of their limitations, users were unable to
demonstrate their desired trajectory — and thus BIRL learned suboptimal
behavior.

Under Noise, the robot compared the human’s demonstrations to similar
alternatives (i.e. noisy perturbations). But just considering similar
alternatives was not enough to reveal what the human meant. Ours outperformed
Noise because it reasoned over both similar and simpler trajectories. Equipped
with this choice set, Ours inferred the human’s reward (low error), and output
near optimal trajectories (low regret).

Figure 4: Survey results from our user study. Higher ratings indicate user
agreement. Posthoc comparisons revealed that the differences between our
method and the baselines were statistically significant (p < .01).

Results – Subjective. We report the results of the user survey in Fig. 4. We
received comments such as “Method C (Ours) was by far the best and the only
one I would trust,” which highlight the perceived benefits of our approach.

##  VIII Conclusion

We analyzed the consequences of over- and underestimating the human’s
capabilities when learning rewards from demonstrations. Both our risk-
sensitivity analysis and experimental results suggest that erring towards
underestimating the human’s choice set results in safer and more inclusive
learning. Limitations: we recognize that our properties for generating similar
and simpler alternatives require hyperparameter tuning, which may depend on
the environment.

## References

  * [1] D. P. Losey, K. Srinivasan, A. Mandlekar, A. Garg, and D. Sadigh, “Controlling assistive robots with learned latent actions,” in _IEEE International Conference on Robotics and Automation_ , 2020, pp. 378–384.
  * [2] L. V. Herlant, R. M. Holladay, and S. S. Srinivasa, “Assistive teleoperation of robot arms via automatic time-optimal mode switching,” in _ACM/IEEE International Conference on Human-Robot Interaction_ , 2016, pp. 35–42.
  * [3] B. D. Argall, “Autonomy in rehabilitation robotics: An intersection,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 1, pp. 441–463, 2018.
  * [4] H. J. Jeon, S. Milli, and A. D. Dragan, “Reward-rational (implicit) choice: A unifying formalism for reward learning,” _arXiv preprint arXiv:2002.04833_ , 2020.
  * [5] R. Freedman, R. Shah, and A. Dragan, “Choice set misspecification in reward inference,” in _CEUR Workshop Proceedings_ , 2020.
  * [6] O. Evans, A. Stuhlmüller, and N. D. Goodman, “Learning the preferences of ignorant, inconsistent agents,” in _AAAI_ , 2016.
  * [7] D. Kahneman and A. Tversky, “Prospect theory: An analysis of decision under risk,” in _Handbook of the fundamentals of financial decision making: Part I_. World Scientific, 2013, pp. 99–127.
  * [8] S. Choi, S. Kariv, W. Müller, and D. Silverman, “Who is (more) rational?” _American Economic Review_ , vol. 104, no. 6, pp. 1518–50, 2014.
  * [9] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, and J. Peters, “An algorithmic perspective on imitation learning,” _Foundations and Trends in Robotics_ , vol. 7, no. 1-2, pp. 1–179, 2018.
  * [10] P. Abbeel and A. Y. Ng, “Apprenticeship learning via inverse reinforcement learning,” in _International Conference on Machine Learning_ , 2004.
  * [11] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey, “Maximum entropy inverse reinforcement learning.” in _AAAI_ , vol. 8, 2008, pp. 1433–1438.
  * [12] D. Ramachandran and E. Amir, “Bayesian inverse reinforcement learning.” in _IJCAI_ , vol. 7, 2007, pp. 2586–2591.
  * [13] C. Finn, S. Levine, and P. Abbeel, “Guided cost learning: Deep inverse optimal control via policy optimization,” in _International Conference on Machine Learning_ , 2016, pp. 49–58.
  * [14] D. M. Taylor, _Americans With Disabilities: 2014_. US Census Bureau, 2018.
  * [15] D. Gopinath, M. N. Javaremi, and B. D. Argall, “Customized handling of unintended interface operation in assistive robots,” _arXiv preprint arXiv:2007.02092_ , 2020.
  * [16] R. M. Aronson, T. Santini, T. C. Kübler, E. Kasneci, S. Srinivasa, and H. Admoni, “Eye-hand behavior in human-robot shared manipulation,” in _ACM/IEEE International Conference on Human-Robot Interaction_ , 2018, pp. 4–13.
  * [17] K. Muelling, A. Venkatraman, J.-S. Valois, J. E. Downey, J. Weiss, S. Javdani, M. Hebert, A. B. Schwartz, J. L. Collinger, and J. A. Bagnell, “Autonomy infused teleoperation with application to brain computer interface controlled manipulation,” _Autonomous Robots_ , vol. 41, no. 6, pp. 1401–1422, 2017\.
  * [18] D. P. Losey and M. K. O’Malley, “Enabling robots to infer how end-users teach and learn through human-robot interaction,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1956–1963, 2019.
  * [19] A. Bajcsy, D. P. Losey, M. K. O’Malley, and A. D. Dragan, “Learning from physical human corrections, one feature at a time,” in _ACM/IEEE International Conference on Human-Robot Interaction_ , 2018, pp. 141–149.
  * [20] S. Reddy, A. Dragan, and S. Levine, “Where do you think you’re going?: Inferring beliefs about dynamics from behavior,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 1454–1465.
  * [21] A. Bobu, A. Bajcsy, J. F. Fisac, S. Deglurkar, and A. D. Dragan, “Quantifying hypothesis space misspecification in learning from human–robot demonstrations and physical corrections,” _IEEE Transactions on Robotics_ , vol. 36, no. 3, pp. 835–854, 2020.
  * [22] D. H. Grollman and A. Billard, “Donut as I do: Learning from failed demonstrations,” in _IEEE International Conference on Robotics and Automation_ , 2011, pp. 3804–3809.
  * [23] K. Shiarlis, J. Messias, and S. Whiteson, “Inverse reinforcement learning from failure,” in _International Foundation for Autonomous Agents and Multiagent Systems_ , 2016.
  * [24] E. Bıyık, D. P. Losey, M. Palan, N. C. Landolfi, G. Shevchuk, and D. Sadigh, “Learning reward functions from diverse sources of human feedback: Optimally integrating demonstrations and preferences,” _arXiv preprint arXiv:2006.14091_ , 2020.
  * [25] D. Sadigh, A. D. Dragan, S. Sastry, and S. A. Seshia, “Active preference-based learning of reward functions.” in _Robotics: Science and Systems_ , 2017\.
  * [26] S. Choi, K. Lee, and S. Oh, “Robust learning from demonstrations with mixed qualities using leveraged gaussian processes,” _IEEE Transactions on Robotics_ , vol. 35, no. 3, pp. 564–576, 2019.
  * [27] D. S. Brown, W. Goo, and S. Niekum, “Better-than-demonstrator imitation learning via automatically-ranked demonstrations,” in _Conference on Robot Learning_ , 2020, pp. 330–359.
  * [28] M. Kalakrishnan, P. Pastor, L. Righetti, and S. Schaal, “Learning objective functions for manipulation,” in _IEEE International Conference on Robotics and Automation_ , 2013, pp. 1331–1336.
  * [29] A. Boularias, J. Kober, and J. Peters, “Relative entropy inverse reinforcement learning,” in _International Conference on Artificial Intelligence and Statistics_ , 2011, pp. 182–189.
  * [30] C. L. Baker, R. Saxe, and J. B. Tenenbaum, “Action understanding as inverse planning,” _Cognition_ , vol. 113, no. 3, pp. 329–349, 2009.
  * [31] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. John Wiley & Sons, 2012.
  * [32] D. P. Losey and M. K. O’Malley, “Trajectory deformations from physical human–robot interaction,” _IEEE Transactions on Robotics_ , vol. 34, no. 1, pp. 126–138, 2017.
  * [33] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “OpenAI Gym,” _CoRR_ , vol. abs/1606.01540, 2016.
  * [34] E. Coumans and Y. Bai, “Pybullet, a python module for physics simulation for games, robotics and machine learning,” http://pybullet.org, 2016–2019.


# A Graph-based Imputation Method for Sparse Medical Records

Ramon Viñas,1 Xu Zheng, 2 Jer Hayes 2

###### Abstract

Electronic Medical Records (EHR) are extremely sparse. Only a small proportion
of events (symptoms, diagnoses, and treatments) are observed in the lifetime
of an individual. The high degree of missingness of EHR can be attributed to a
large number of factors, including device failure, privacy concerns, or other
unexpected reasons. Unfortunately, many traditional imputation methods are not
well suited for highly sparse data and scale poorly to high dimensional
datasets. In this paper, we propose a graph-based imputation method that is
both robust to sparsity and to unreliable unmeasured events. Our approach
compares favourably to several standard and state-of-the-art imputation
methods in terms of performance and runtime. Moreover, results indicate that
the model learns to embed different event types in a clinically meaningful
way. Our work can facilitate the diagnosis of novel diseases based on the
clinical history of past events, with the potential to increase our
understanding of the landscape of comorbidities.

## Introduction

Missing data is a pervasive challenge for medical domains that can result in
the reduction of the statistical power of a study and can produce biased
estimates, leading to invalid conclusions (Hyun 2013). Previous research has
demonstrated success in data imputation with both statistical and generative
models based approaches. These traditional data imputation methods include
univariate methods such as mean or median imputation, multi-variate methods
like k-NN imputation (Troyanskaya et al. 2001) and Multivariate Imputation by
Chained Equations (MICE) (Van Buuren and Groothuis-Oudshoorn 2011), and deep
learning methods such as autoencoders (Vincent et al. 2008), GAIN (Yoon,
Jordon, and Schaar 2018), and GRAPE (You et al. 2020).

Although these methods show good performance on traditional datasets, they do
not explicitly deal with the sparsity and imbalance problem that characterises
many medical datasets. From a machine learning perspective, medical data can
potentially be very sparse, e.g. there are over 69,000 International
Classification of Diseases (ICD) diagnosis codes and even a very diseased
patient will only present a minuscule fraction of these codes. Together with
high dimensionality, the sparsity issue often makes it infeasible to apply
traditional data imputation methods on medical datasets.

In recent years, Graph Neural Networks (GNN) have gained increasing attention
for modelling graph-based datasets, including social networks, citation
networks, and molecules. In this paper, we build on GRAPE (You et al. 2020) to
develop a GNN-based imputation method for highly imbalanced medical datasets.
Essentially, GRAPE represents data as a bipartite graph where sample and
feature nodes are connected according to the missingness pattern of the
dataset. Data imputation then corresponds to edge-level prediction for the
missing links. To deal with the highly sparse and unary nature of EHRs (i.e.
missing values represent either unmeasured events or negative outcomes), we
employ a training scheme that balances positive and unmeasured edges in the
graph. We perform experiments on EHRs from a subset of more than 72,000
diabetes patients from the IBM Explorys dataset. Our results show improved
performance with respect to traditional and state-of-the-art methods that do
not explicitly deal with the imbalanced and unary nature of the data. Besides,
we demonstrate that the latent embeddings of medical concepts retrieved from
our model cluster in a clinically meaningful way.

## Method

### Problem definition.

Let ${\bm{X}}\in\\{0,1\\}^{m\times n}$ be a medical dataset with $m$ patients
and $n$ event types (e.g. diagnoses). For each patient $i$ and event type $j$,
the entry $x_{ij}$ is one if event $i$ (e.g. familial Mediterranean fever) has
been observed for patient $j$ and zero otherwise (i.e. unmeasured events with
unknown outcomes). Here we assume that the entries $x_{ij}$ are binary
(unmeasured and measured), but our approach can be extended to account for
more complex variable types (e.g. sequence of event times). Our goal is to
impute the unmeasured values of dataset ${\bm{X}}$.

### Bipartite graph representation.

Following (You et al. 2020), we represent data in a bipartite graph
${\mathcal{G}}=\\{{\mathcal{V}}_{p}\cup{\mathcal{V}}_{e},{\mathcal{E}}\\}$,
where ${\mathcal{V}}_{p}=\\{v^{p}_{1},...,v^{p}_{m}\\}$ is the patient
partition, ${\mathcal{V}}_{e}=\\{v^{e}_{1},...,v^{e}_{n}\\}$ is the event
partition, and
${\mathcal{E}}=\\{(v^{p}_{i},v^{e}_{j})|v^{p}_{i}\in{\mathcal{V}}_{p},v^{e}_{j}\in{\mathcal{V}}_{e},x_{ij}=1\\}$
is the set of edges connecting patients from ${\mathcal{V}}_{p}$ to events
from ${\mathcal{V}}_{e}$ according to the measured entries of the dataset.
This framework also allows attributed edges (e.g. with event times) with
potential edge repetitions (i.e. a certain event can occur several times for
the same patient).

### Model.

We employ a graph neural network to perform link prediction on the bipartite
graph. This procedure can be divided into 3 steps.

First, we initialise node features of the patient ${\mathcal{V}}_{p}$ and
event nodes ${\mathcal{V}}_{e}$. For event nodes, we use $d$-dimensional
learnable embeddings as initial node values. The idea is that these weights,
which will be learnt through gradient descent, should summarise relevant
properties of each event. For patient nodes, we initialise the node features
with the available demographic information (e.g. age and sex) and project them
to the $d$-dimensional space with a multi-layer perceptron. Importantly, this
formulation allows transfer learning between sets of distinct patients.

Second, we perform message passing to compute latent node embeddings. Let
${\mathcal{H}}_{p}=\\{{\bm{h}}^{p}_{1},...,{\bm{h}}^{p}_{m}\\}$ and
${\mathcal{H}}_{e}=\\{{\bm{h}}^{e}_{1},..,{\bm{h}}^{e}_{n}\\}$ be the initial
$k$-dimensional patient and event node embeddings, respectively. Let
${\mathcal{N}}_{p}(i;{\mathcal{E}})=\\{j|(v^{p}_{i},v^{e}_{j})\in{\mathcal{E}}\\}$
and
${\mathcal{N}}_{e}(i;{\mathcal{E}})=\\{j|(v^{p}_{j},v^{e}_{i})\in{\mathcal{E}}\\}$
be the set of neighbours of nodes $v^{p}_{i}$ and $v^{e}_{i}$, respectively.
We compute latent node embeddings
$\hat{{\mathcal{H}}}_{p}=\\{\hat{{\bm{h}}}^{p}_{1},...,\hat{{\bm{h}}}^{p}_{m}\\}$
and
$\hat{{\mathcal{H}}}_{e}=\\{\hat{{\bm{h}}}^{e}_{1},...,\hat{{\bm{h}}}^{e}_{n}\\}$
with separate GraphSAGE layers (Hamilton, Ying, and Leskovec 2018) as follows:

$\begin{split}\hat{{\bm{h}}}^{p}_{i}={\bm{W}}^{p}_{1}{\bm{h}}^{p}_{i}+{\bm{W}}^{p}_{2}\Bigg{(}\frac{1}{|{\mathcal{N}}_{p}(i;{\mathcal{E}})|}\sum_{j\in{\mathcal{N}}_{p}(i)}{\bm{h}}^{e}_{j}\Bigg{)}\\\
\hat{{\bm{h}}}^{e}_{i}={\bm{W}}^{e}_{1}{\bm{h}}^{e}_{i}+{\bm{W}}^{e}_{2}\Bigg{(}\frac{1}{|{\mathcal{N}}_{e}(i,{\mathcal{E}})|}\sum_{j\in{\mathcal{N}}_{e}(i)}{\bm{h}}^{p}_{j}\Bigg{)}\end{split}$
(1)

where ${\bm{W}}^{p}_{1}$, ${\bm{W}}^{p}_{2}$, ${\bm{W}}^{e}_{1}$,
${\bm{W}}^{e}_{2}$ are learnable weights. Optionally, we can stack several
layers interleaving non-linearities.

Finally, unmeasured values are imputed via link prediction. We compute the
probability of an edge between nodes $v^{p}_{i}$ and $v^{e}_{j}$ as
$p(x_{ij}=1)=\text{MLP}(\hat{{\bm{h}}}^{p}_{i},\hat{{\bm{h}}}^{e}_{j})$, where
MLP is a multi-layer perceptron with a sigmoid function as output activation.

Figure 1: Distribution of per-event recalls and specificities (y-axis) by
event frequencies (x-axis), computed from the graph-based model trained under
two undersampling schemes. Version 1 (red): the number of events in the
invisible and negative sets match (i.e.
$|{\mathcal{E}}_{\text{inv}}|=|{\mathcal{E}}_{\text{neg}}|$). Version 2 (blue,
ours): the event and patient frequencies are additionally preserved (i.e.
$|{\mathcal{N}}_{p}(i;{\mathcal{E}}_{\text{neg}})|=|{\mathcal{N}}_{p}(i;{\mathcal{E}}_{\text{inv}})|$
and
$|{\mathcal{N}}_{e}(j;{\mathcal{E}}_{\text{neg}})|=|{\mathcal{N}}_{e}(j;{\mathcal{E}}_{\text{inv}})|$
for any patient $i$ and event type $j$). Version 1 (red) introduces a sampling
bias – common events are rarely imputed as negative, while rare events are
rarely imputed as active.

### Optimisation.

To deal with the highly unbalanced data, we employ a training scheme that
balances positive and unmeasured edges. At each training iteration, we sample
three sets of edges:

  * •

Invisible edges. The set ${\mathcal{E}}_{\text{inv}}$ contains $k$ positive
edges from ${\mathcal{E}}$ that are unseen to the model, where $k$ is a
hyperparameter. The goal is to correctly predict the presence of these edges
via link prediction.

  * •

Visible edges. The set ${\mathcal{E}}_{\text{vis}}$ contains the remaining
$|{\mathcal{E}}|-k$ positive edges that are seen during message passing. The
visible and invisible subsets are disjoint and
${\mathcal{E}}={\mathcal{E}}_{\text{vis}}\cup{\mathcal{E}}_{\text{inv}}$.

  * •

Negative edges. The set ${\mathcal{E}}_{\text{neg}}$ contains $k$ edges that
do not belong to ${\mathcal{E}}$. The goal of the model is to correctly
predict the absence of these edges. Importantly, the cardinalities of
${\mathcal{E}}_{\text{neg}}$ and ${\mathcal{E}}_{\text{inv}}$ match. Moreover,
the set ${\mathcal{E}}_{\text{neg}}$ preserves the patients and event
frequencies, i.e.
$|{\mathcal{N}}_{p}(i;{\mathcal{E}}_{\text{neg}})|=|{\mathcal{N}}_{p}(i;{\mathcal{E}}_{\text{inv}})|$
and
$|{\mathcal{N}}_{e}(j;{\mathcal{E}}_{\text{neg}})|=|{\mathcal{N}}_{e}(j;{\mathcal{E}}_{\text{inv}})|$
for any patient $i$ and event type $j$. This effectively balances the model’s
exposure to positive and unmeasured edges for each patient and event type,
preventing any sampling biases (see Figure 1).

We then optimise model’s parameters via gradient descent by minimising the
binary cross-entropy:

$\begin{split}{\mathcal{L}}({\mathcal{E}}_{\text{inv}},{\mathcal{E}}_{\text{neg}})=&-\frac{1}{2k}\sum_{(v^{p}_{i},v^{e}_{j})\in{\mathcal{E}}_{\text{inv}}}\log
p(x_{ij}=1)\\\
&-\frac{1}{2k}\sum_{(v^{p}_{i},v^{e}_{j})\in{\mathcal{E}}_{\text{neg}}}\log
p(x_{ij}=0)\end{split}$ (2)

## Results

### Evaluation metrics.

Medical records are extremely sparse – only a very small proportion of events
(e.g. symptoms, diagnoses, treatments) are observed during the lifetime of an
individual. At the same time, we cannot always be certain that unobserved
events have not occurred because in practise we can only measure a small
fraction of them (e.g., it is unfeasible to test someone for all known
diseases) – this is precisely why we want to impute missing values.
Conversely, observed events have happened in reality with high confidence
(e.g. chemotherapy for lung cancer). In this paper, we evaluate the imputation
performance with sensitivity, specificity, and balanced accuracy. In contrast
to accuracy (uninformative in sparse scenarios) and precision (sensitive to
unreliable false positives), the proposed metrics are both robust to sparsity
and to unreliable unmeasured events.

### Dataset.

Patients with diabetes are sampled from the the IBM Explorys database. We
create a bipartite graph of patients and events using diagnoses-related
events. We filter out events that appear in less than $0.1\%$ of the records,
resulting in 3284 unique events. We split patients into disjoint train
($70\%$) and test ($30\%$) sets, yielding 72801 and 30334 unique train and
test patients, respectively. For the test patients, we mask out $30\%$ of the
observed values and use them to evaluate the performance of all the models. We
leverage the age and sex of the patients as demographic information provided
as input to the models. When represented as a matrix, the dataset is highly
sparse, with 98.3% of zero entries.

### Baseline models.

We compare our model to several baseline methods, including k-NN imputation
(Troyanskaya et al. 2001), Generative Adversarial Imputation Networks (GAIN)
(Yoon, Jordon, and Schaar 2018) and Denoising Autoencoders (DAE) (Vincent et
al. 2008). As these baseline models can only handle tabular data, we represent
patient records as a binary matrix where rows correspond to patients and
columns to unique diagnosis codes. In this matrix, entry $(i,j)$ is one if the
$j$-th diagnosis has been observed for patient $i$-th and zero otherwise.

The denoising autoencoder (DAE) and generative adversarial imputation networks
(GAIN) are both optimised via the reconstruction error on the observed values
(plus an adversarial term for the missing values for GAIN). Because the
dataset is highly imbalanced, both models are by default biased towards the
majority class, i.e. zero for each feature. Additionally, GAIN cannot readily
deal with the unary nature of the data – missing positive values cannot be
distinguished from actual zeros (i.e. events with negative outcome) and they
both form the mask vector. To address these issues, we adopt an undersampling
mechanism that closely mimicks the training scheme of the GNN model. At each
training iteration, we randomly sample $k$ negative values (i.e. unmeasured
events), where $k$ is the total number of positive values, and treat them as
observable. The remaining entries are masked out (and form the mask vector for
GAIN) and the methods are optimised by minimising their respective loss
functions.

### Hyperparameters.

We use node embeddings of dimension $d=95$. We initialise them with the right
singular vectors of the train dataset computed via singular value
decomposition (SVD). This yields higher validation scores according to our
experiments. The graph neural network architecture consists of 3 GraphSAGE
layers with node embeddings of dimension $d=95$ and rectified linear unit
(ReLU) activations. The final multi-layer perceptron comprises 1 hidden layer
with 32 units followed by ReLU. We optimise the model with the Adam optimiser
(Kingma and Ba 2014) and a learning rate of $0.0066$. At each training
iteration, we randomly sample the invisible ${\mathcal{E}}_{\text{inv}}$ set
of edges from a binomial distribution $B(1,p)$ with probability $p=0.2$, that
is, on average $20\%$ of the total number of training edges are masked out.
The set ${\mathcal{E}}_{\text{neg}}$ of unmeasured edges is then sampled as
described in the optimisation section, preserving the cardinality of
${\mathcal{E}}_{\text{inv}}$. We implement the model in Pytorch (Paszke et al.
2019) and Pytorch Geometric (Fey and Lenssen 2019).

Figure 2: Low-dimensional representation of the latent event embeddings. Each
point corresponds to a different event type (e.g. malnutrition-related
diabetes mellitus). We use spectral clustering to cluster events into 10
clusters and analyse their composition in Figure 3. Overall, we find that the
model is able to identify clusters of clinically-related events.  Figure 3:
Composition of low-dimensional event clusters. We inspect the event-type
composition of clusters identified via spectral clustering on the latent event
embeddings of our imputation model (see Figure 2). We observe high cluster
purity, that is, several clusters consist mostly of events of the same type.
For example, 65% of events in cluster 0 are mental and behavioural related
disorders, while most events in clusters 4 and 6 are related to pregnancy and
childbirth. Other clusters are more heterogeneous and understanding their
semantics would possibly require a finer-grained analysis.

### Results.

Table 1 shows the test imputation scores. We compute the sensitivity,
specificity, and balanced accuracy for each event type and report the mean
standard deviation of these metrics. Importantly, conventional imputation
methods such as k-NN imputation do not have any built-in mechanisms to deal
with the inherent characteristics of medical records (i.e. sparsity and
unreliability of unmeasured events) and model calibration is therefore
unclear. For these methods, we analyse their performance under two different
thresholds, namely a $0.5$ cutoff (i.e. for patient $i$, event $j$ is imputed
as measured if $p(x_{ij}=1)>0.5$) and the per-event-type frequencies of
measured values in the train set (i.e. for patient $i$, event $j$ is imputed
as measured if $p(x_{ij}=1)>\frac{1}{m}\sum_{i=1}^{m}x_{ij}$, where $m$ is the
number of train patients). Despite the data sparsity, the GNN-based method
attains highly balanced predictions (sensitivity$=0.78\pm 0.12$,
specificity$=0.79\pm 0.09$) with the default $0.5$ cutoff, outperforming other
baselines by a large margin in terms of balanced accuracy (arithmetic mean of
sensitivity and specificity). We attribute this to the training scheme, which
effectively balances the model’s exposure to positive and unmeasured edges for
each event type, yielding a well-calibrated model (see Figure 1 for a
comparison with a random undersampling method). The proposed approach is also
highly scalable and significantly faster than traditional methods.

Table 1: Imputation results. We report the mean and standard deviation of the
per-event-type evaluation metric for different cutoff values. For the
threshold _Avg._ , we use the per-event-type frequencies of observed values in
the train set as cutoffs. The best scores are highlighted in bold.

Method | Cutoff | Sensitivity | Specificity | Balanced Acc. | Runtime
---|---|---|---|---|---
10-NN | $0.5$ | $0.08\pm 0.20$ | $\mathbf{0.98\pm 0.10}$ | $0.53\pm 0.07$ | $43.29$h
Avg. | $\underline{0.63\pm 0.29}$ | $0.63\pm 0.26$ | $\underline{0.63\pm 0.09}$
DAE | $0.5$ | $0.36\pm 0.34$ | $\underline{0.87\pm 0.24}$ | $0.62\pm 0.11$ | $0.25$h
Avg. | $\mathbf{0.98\pm 0.08}$ | $0.09\pm 0.18$ | $0.54\pm 0.08$
GAIN | $0.5$ | $0.36\pm 0.29$ | $0.83\pm 0.25$ | $0.59\pm 0.11$ | $0.25$h
Avg. | $0.45\pm 0.31$ | $0.73\pm 0.29$ | $0.59\pm 0.11$
Ours | $0.5$ | $0.78\pm 0.12$ | $0.79\pm 0.09$ | $\mathbf{0.79\pm 0.09}$ |  $1.09$h

We further study the behaviour of our model by inspecting the latent event
embeddings obtained after message passing. We employ UMAP (McInnes, Healy, and
Melville 2018) to project these embeddings into a 2-dimensional space and
further apply spectral clustering ($N$=10 clusters) to cluster events (see
Figure 2). Figure 3 depicts their event type composition. Cluster 0 mostly
consists of mental and behavioural related disorders (65%). Events in cluster
2 involve injuries and poisoning (69%) and external causes of morbidity and
mortality (31%). Cluster 3 is composed exclusively by diseases of the ear and
mastoid process. Clusters 4 and 6 are both related to pregnancy, childbirth,
and the puerperium. The majority of events in cluster 5 are diseases of the
skin and the subcutaneous tissue (55%), while most events in cluster 9 are
diseases of the genitourinary system. The remaining clusters are more
heterogeneous and understanding their semantics would possibly require a
finer-grained analysis (e.g. cluster 1 consists of events related to contact
with health services, 23%, and diseases of the digestive system, 21%, among
others). Overall, this analysis shows that the model is grouping clinically-
related event types in the latent space, with high cluster purity.

## Conclusion

In this paper, we have studied the problem of imputing missing data in medical
records. These datasets are highly sparse and unmeasured events are unreliable
(i.e. the fact that a specific event has not been observed for a certain
patient does not entail that it has not occurred in reality). Unfortunately,
traditional imputation methods are not well suited for this scenario. To
address this challenge, we have proposed a graph-based deep learning model
that is both scalable and effective at imputing missing values in sparse
regimes. The proposed model is easy to use and well-calibrated by default.
Furthermore, our approach compares favourably to existing methods in terms of
performance and runtime. This work can facilitate the diagnosis of new events
and shed light into the landscape of comorbidities.

## References

  * Fey and Lenssen (2019) Fey, M.; and Lenssen, J. E. 2019.  Fast Graph Representation Learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_.
  * Hamilton, Ying, and Leskovec (2018) Hamilton, W. L.; Ying, R.; and Leskovec, J. 2018.  Inductive Representation Learning on Large Graphs.
  * Hyun (2013) Hyun, K. 2013.  The prevention and handling of the missing data.  _Korean J Anesthesiol_ 64(5): 402–406.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ .
  * McInnes, Healy, and Melville (2018) McInnes, L.; Healy, J.; and Melville, J. 2018.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ .
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32_ , 8024–8035. Curran Associates, Inc.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Troyanskaya et al. (2001) Troyanskaya, O.; Cantor, M.; Sherlock, G.; Brown, P.; Hastie, T.; Tibshirani, R.; Botstein, D.; and Altman, R. B. 2001.  Missing value estimation methods for DNA microarrays.  _Bioinformatics_ 17(6): 520–525.
  * Van Buuren and Groothuis-Oudshoorn (2011) Van Buuren, S.; and Groothuis-Oudshoorn, K. 2011.  mice: Multivariate imputation by chained equations in R.  _Journal of statistical software_ 45: 1–67.
  * Vincent et al. (2008) Vincent, P.; Larochelle, H.; Bengio, Y.; and Manzagol, P.-A. 2008.  Extracting and composing robust features with denoising autoencoders.  In _Proceedings of the 25th international conference on Machine learning_ , 1096–1103.
  * Yoon, Jordon, and Schaar (2018) Yoon, J.; Jordon, J.; and Schaar, M. 2018.  Gain: Missing data imputation using generative adversarial nets.  In _International Conference on Machine Learning_ , 5689–5698. PMLR.
  * You et al. (2020) You, J.; Ma, X.; Ding, D.; Kochenderfer, M.; and Leskovec, J. 2020.  Handling Missing Data with Graph Representation Learning.  _NeurIPS_ .


# Representations Matter: Embedding Modes of Large Language Models using
Dynamic Mode Decomposition

Mohamed Akrout
University of Manitoba, AIP Labs
<EMAIL_ADDRESS>

###### Abstract

Existing large language models (LLMs) are known for generating “hallucinated”
content, namely a fabricated text of plausibly looking, yet unfounded, facts.
To identify when these hallucination scenarios occur, we examine the
properties of the generated text in the embedding space. Specifically, we draw
inspiration from the dynamic mode decomposition (DMD) tool in analyzing the
pattern evolution of text embeddings across sentences. We empirically
demonstrate how the spectrum of sentence embeddings over paragraphs is
constantly low-rank for the generated text, unlike that of the ground-truth
text. Importantly, we find that evaluation cases having LLM hallucinations
correspond to ground-truth embedding patterns with a higher number of modes
being poorly approximated by the few modes associated with LLM embedding
patterns. In analogy to near-field electromagnetic evanescent waves, the
embedding DMD eigenmodes of the generated text with hallucinations vanishes
quickly across sentences as opposed to those of the ground-truth text. This
suggests that the hallucinations result from both the generation techniques
and the underlying representation.

##  1 Introduction

Language Language Models (LLMs) have emerged as impressive tools capable of
generating coherent and contextually relevant answers. These models, trained
on vast amounts of data, demonstrated abilities that include understanding
language, providing custom and comprehensive answers, and generating creative
content. However, LLMs also tend to generate nonsensical or unfaithful content
[1]. This phenomenon, referred to as hallucinations, is one of the crucial
challenges that hinder the success and performance of LLMs.

Various research endeavors have begun proposing ways to overcome
hallucinations in different text-generation tasks such as summarization,
question-answering, and translation [1]. A plethora of tools have been
introduced to detect hallucinated content. As one example, fact-verification
consists of assessing the truthfulness of the LLM output using evidence
retrieved from an external knowledge base [2]. Other approaches have focused
on hallucination detection methods for black-box LLMs (i.e., models accessible
only through an API) since, in the absence of information about the internal
state of the LLM (e.g., embeddings, token probability, or entropy), it is not
possible to use uncertainty metrics to detect hallucinations. A self-
evaluation approach was proposed where the LLM is asked to answer if its
generated answer is true [3]. Alternatively, the LLM can be used to sample
different responses, and hallucinations are detected when there is information
inconsistency between the different samples [4]. Using this self-checking
approach, it was concluded that the hallucination problem is not inherently
one of training or representation but is rather one of generation, given that
LLMs contain enough information to reduce the hallucination rate.

Here, we call into question this conclusion by observing the embedding
properties of the generated text that highlight the importance of the learned
representations by LLMs. Our observations do not offer a complete answer about
the importance level of representations in generating hallucinations. However,
it does aim to balance research discussions and reintroduce questions about
representations back to the fold. In this work, we assume that we have access
to a black-box LLM and that no external knowledge base is available.

To emphasize the importance of learned representations by LLMs, we resort to
the dynamic mode decomposition (DMD) [5] method to find the modes of both
generated and ground-truth texts (e.g. Wikipedia). While the standard goal of
DMD is extracting key spatiotemporal features of high-dimensional systems, in
this work, we employ DMD to obtain the embedding properties over sentences. We
do this by substituting the time and system state dimensions with the sentence
and embedding dimensions, respectively. It is important to highlight that DMD
approximates the modes of the so-called Koopman operator [5]. While the
Koopman operator is linear and infinite-dimensional, it does not linearize the
system dynamics and represents the flow of the dynamical system on measurement
functions as an infinite-dimensional operator [6]. For this reason, the
application of DMD in the text embedding space accounts for the non-linear
behavior of the embedding dimensions as they evolve through sentences.

##  2 Dynamic mode decomposition

###  2.1 Background

Consider a non-linear dynamical system whose state
$\bm{x}_{t}\in\mathbb{R}^{N}$ at time $t$ is governed by

$\frac{\textrm{d}\bm{x}_{t}}{\textrm{d}t}=\bm{f}\left(\bm{x}_{t},t\right),$
(1)

where $\bm{f}(\cdot)$ represents the dynamics. For many applications (e.g.,
fluid dynamics, structural vibrations, neuroscience), the dynamics $\bm{f}$ is
difficult to approximate, or simply unknown, and only state measurements
$\\{\bm{x}_{t}\\}_{t=1}^{T}$ are available. In this case, the DMD method takes
the equation-free perspective by approximating (1) by its discrete-time
version sampled every $\Delta t$ in time as

$\bm{x}_{t+1}=\bm{A}\,\bm{x}_{t},$ (2)

where $\bm{A}$ refers to the dynamics matrix. The DMD algorithm was devised to
collect state measurements from a dynamical system at regularly spaced time
intervals by defining the two matrices:

$\bm{X}=\left[\begin{array}[]{cccc}\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\\\
\bm{x}_{1}&\bm{x}_{2}&\ldots&\bm{x}_{T-1}\\\
\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\end{array}\right],~{}\textrm{and}~{}~{}\bm{X}^{\prime}=\left[\begin{array}[]{cccc}\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\\\
\bm{x}_{2}&\bm{x}_{3}&\ldots&\bm{x}_{T}\\\
\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\end{array}\right].$
(3)

Then, DMD finds the optimal local linear approximation of the non-linear
dynamical system by satisfying the approximation

$\bm{X}^{\prime}\approx\bm{A}\,\bm{X}.$ (4)

Here, the DMD modes (also called dynamic modes) are the eigenvectors of
$\bm{A}$, and each DMD mode corresponds to a particular eigenvalue of
$\bm{A}$. The DMD eigenvalues provide information about the temporal behavior
of the spatial structure described by the corresponding eigenvectors.

###  2.2 From time dynamics to sentence-wise dynamics

The DMD was originally designed to collect data measurements across different
time instants. However, the time dimension in the mathematical derivation of
DMD is a dummy dimension, and one can substitute it with another variable
depending on the analysis at hand. For NLP use cases, the matrices
$\bm{X}\in\mathbb{R}^{N\times P}$ and $\bm{X}^{\prime}\in\mathbb{R}^{N\times
P}$ can be constructed from a paragraph composed of $P$ sentences with each
sentence having a text embedding state $\bm{x}_{p}\in\mathbb{R}^{N}$ as shown
in Figure 1.

Figure 1: The construction of the embedding matrix of a paragraph using a word
embedding model.

By doing so, the induced DMD eigenmodes and eigenvalues convey information
about the sentence-wise dynamics of the text embedding instead of the standard
time dynamics of the state measurement.

##  3 Experiments

We evaluate the text embedding properties of both generated text and ground-
truth text using GPT-3 (text-davinci-003) on individuals from the Wikibio
dataset [7]. Specifically, we use a sub-dataset of Wikibio from [4] containing
238 articles from the top 20% of articles by length. This importantly ensures
the mitigation of more obscure concepts being incorporated. It is a sub-
dataset of the first paragraph (along with tabular information) of Wikipedia
biographies111https://huggingface.co/datasets/potsawee/wiki_bio_gpt3_hallucination,
and the GPT-3 output was generated in [4] using the prompt “This is a
Wikipedia passage about {concept}”. Moreover, each sentence of each data
sample generated by GPT-3 was classified into one of three annotation
categories:

  * •

major inaccurate when the sentence is unrelated to the topic and hence is a
hallucination sample,

  * •

minor inaccurate when the sentence is related to the topic but contains non-
factual information,

  * •

accurate when the sentence describes factual information.

###  3.1 Data processing

For each data sample, we map both the ground-truth Wiki and the GPT-3
generated paragraphs to a 384-dimensional embedding vector space using the
HuggingFace sentence embeddings API of the sentence-transformers model all-
MiniLM-L6-v2222https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2.
To obtain a single label for each paragraph, if all sentence annotations
agree, we use the paragraph label. However, if annotations differ from one
sentence to another, we use the most frequent annotation as the paragraph
label. If multiple annotations have the same occurrence frequency, we use the
worse-case label as the paragraph label. For example, the sentence annotation
list {minor inaccurate, minor inaccurate, major inaccurate, major inaccurate}
is mapped to the paragraph annotation {major inaccurate}.

We start by stacking all the sentences’ embeddings of each paragraph into an
embedding matrix. Then, we plot in Figure 2 the average spectrum of data
samples associated with each of the three annotation categories. There, it is
seen that the rank of the Wiki embedding is higher than that of the GPT-3
generated embedding. This means that the number of linearly independent
embedding vectors over sentences is higher for Wiki text than for GPT-3
generated text.

Figure 2: The average spectrum of the Wiki and GPT-3 text embedding matrices
$\bm{X}$ associated with major inaccurate, minor inaccurate, and accurate data
samples.

Moreover, it is interesting to note that the higher hallucination of GPT-3
(e.g., major inaccurately generated samples) is associated with a higher rank
of the ground-truth Wiki embeddings. This is opposed to the rank of the GPT-3
embeddings which has a smaller rank for hallucinated and partially
hallucinated, or non-hallucinated samples.

###  3.2 DMD analysis

We use the PyDMD package [8] to examine the modes and dynamics of the text
embeddings. We also use the optimal rank method in [9] to approximate the
best-fit matrix $\bm{A}$ in (4).333This can be done by letting the parameter
svd_rank=0 in the constructor of the DMD class..

Figures 3 and 4 depict the DMD eigenvalues of the modes associated with Wiki
and GPT-3 text, respectively, for paragraphs with the three annotations
described in Section 3.1. First, it is observed that all the eigenvalues in
the complex plane are inside the unit circle. This suggests that the embedding
eigenmodes describe transient embedding responses decreasing across sentences.

We also note how a significant number of the eigenvalues of the Wiki text
associated with hallucinated samples in Figure 3a are complex. This is to be
opposed to the eigenvalues of $i)$ Wiki text having minor inaccuracies or
being accurate (cf. Figures 3b and 3c), and $ii)$ those of the generated GPT-3
text in 4 independently of its accuracy.

(a) Wiki, major inaccurate.

(b) Wiki, minor inaccurate.

(c) Wiki, accurate.

Figure 3: DMD eigenmodes of the text embedding of the wiki text for (a) major
inaccurate samples, (b) minor inaccurate samples, and (c) accurate samples.

(a) GPT-3, major inaccurate.

(b) GPT-3, minor inaccurate.

(c) GPT-3, accurate.

Figure 4: DMD eigenmodes of the text embedding of the GPT-3 generated text for
(a) major inaccurate samples, (b) minor inaccurate samples, and (c) accurate
samples.

Unlike the discrete Fourier transform (DFT) whose eigenvalues are roots of
unity, the DMD eigenvalues are characterized by both a frequency and a
magnitude, which together correspond to a complex frequency. The latter
characterizes important physical properties (e.g., periodicity, oscillation,
damping) in real-world dynamical systems [10]. In loose analogical reference
to electromagnetics (EM), one would compare embedding modes vanishing over
sentences to EM waves radiated in space. The embedding modes associated with
complex eigenvalues correspond to far-field propagation modes, while the real-
valued eigenvalues are associated with near-field ones (e.g., evanescent
waves) which vanish rapidly in space.

By contrasting Figures 3a and 4a, it is seen that generated samples with
hallucinations correspond to generated embeddings with a few modes propagating
across sentences as opposed to the Wiki embeddings, where many more embeddings
survive across sentences. In other words, hallucinations occur when a few
embedding modes generated by GPT-3 are approximating a larger set of embedding
modes of the Wiki text. Confirmingly, little to no hallucinations are observed
when the Wiki text’s embeddings have only a few modes. In such scenarios, this
suggests that the “few mode embedding nature” of the GPT-3 generation does not
hallucinate and approximates well the embedding modes of the ground truth.
Reverting back to the prior EM analogy, approximating the higher numbers of
modes in the near-field with the lower numbers of modes in the far-field is
called “electromagnetic inversion”, which looks conceptually similar to the
phenomenon of hallucinations in the embedding space. We summarize the analogy
between the hallucination with LLMs and the EM wave theory in Table 1.

Table 1: The analogy between the electromagnetic modes and the DMD text embedding modes for scenarios with or without hallucination. |  | Terminology
---|---|---
| Electromagnetics | NLP
hallucination | radiation source | fact
evanescent modes | DMD modes of the ground-truth text embedding
far-field modes | DMD modes of the LLM text embedding
inversion | hallucination
no hallucination | radiation source | fact
far-field modes | DMD modes of LLM/ground-truth text embedding

Finally, we plot the dynamics of all the embedding modes for both Wiki and
GPT-3 generated text in Figures 5 and 6.

(a) Wiki, major inaccurate.

(b) Wiki, minor inaccurate.

(c) Wiki, accurate.

Figure 5: DMD mode dynamics of the text embedding of the wiki text for (a)
major inaccurate samples, (b) minor inaccurate samples, and (c) accurate
samples.

(a) GPT-3, major inaccurate.

(b) GPT-3, minor inaccurate.

(c) GPT-3, accurate.

Figure 6: DMD mode dynamics of the text embedding of the GPT-3 generated text
for (a) major inaccurate samples, (b) minor inaccurate samples, and (c)
accurate samples.

There, we observe the decreasing behavior of the modes for accurate and minor
inaccurate samples, confirming why all the eigenvalues were inside the unit
circle. For major inaccurate samples, some modes’ dynamics are consistently
present across sentences as they slowly decrease, and appear to be constant.
It is worth noting how the number of these gradually decreasing modes is much
higher for the embeddings of the Wiki test. This confirms how the fewer non-
vanishing embedding modes of the GPT-3 text can be a good approximation of
those of the Wiki text only when the latter itself has a few modes as well.

##  4 Conclusion & future work

This work sought to find a connection in the embedding space between the
dynamic mode decomposition modes of the GPT-3 generated text and those of its
ground-truth Wiki text. We empirically found that hallucination occurs when
the embedding modes of the Wiki text have a significant number of modes that
cannot be well approximated by those of the GPT-3 text. One limitation of this
work is that it does not revisit the prompting of the annotated dataset of
Wikibio from [4]. Questions about the prompting strategies are important to
answer in future studies as they uncover new properties of the text
embeddings. Further tests can be conducted on other datasets after annotating
them to confirm those findings on multiple contexts, prompts, and generated
text.

## References

  * [1] Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung.  Survey of hallucination in natural language generation.  ACM Computing Surveys, 55(12):1–38, 2023.
  * [2] Zhijiang Guo, Michael Schlichtkrull, and Andreas Vlachos.  A Survey on Automated Fact-Checking.  Transactions of the Association for Computational Linguistics, 10:178–206, 2022.
  * [3] Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, et al.  Language models (mostly) know what they know.  arXiv preprint arXiv:2207.05221, 2022.
  * [4] Potsawee Manakul, Adian Liusie, and Mark JF Gales.  Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models.  arXiv preprint arXiv:2303.08896, 2023.
  * [5] J Nathan Kutz, Steven L Brunton, Bingni W Brunton, and Joshua L Proctor.  Dynamic mode decomposition: data-driven modeling of complex systems.  SIAM, 2016.
  * [6] Clarence W Rowley, Igor Mezić, Shervin Bagheri, Philipp Schlatter, and Dan S Henningson.  Spectral analysis of nonlinear flows.  Journal of fluid mechanics, 641:115–127, 2009.
  * [7] Rémi Lebret, David Grangier, and Michael Auli.  Neural text generation from structured data with application to the biography domain.  arXiv preprint arXiv:1603.07771, 2016.
  * [8] Nicola Demo, Marco Tezzele, and Gianluigi Rozza.  Pydmd: Python dynamic mode decomposition.  Journal of Open Source Software, 3(22):530, 2018.
  * [9] Matan Gavish and David L. Donoho.  The optimal hard threshold for singular values is $4/\sqrt{3}$.  IEEE Trans. Inf. Theory, 60(8):5040–5053, 2014.
  * [10] Tim Krake, Stefan Reinhardt, Marcel Hlawatsch, Bernd Eberhardt, and Daniel Weiskopf.  Visualization and selection of dynamic mode decomposition components for unsteady flow.  Visual Informatics, 5(3):15–27, 2021.