# Path-Integral Formula for Computing Koopman Eigenfunctions

Shankar A. Deka∗, Sriram S.K.S. Narayanan∗ and Umesh Vaidya * These authors
contributed equally to this paper.UV will like to acknowledge the financial
support from NSF grant 1932458. Shankar A. Deka is with the Decision and
Control Systems division in the Dept. of Electrical Engr. and Computer
Science, KTH Royal Institute of Technology, Sweden. Email<EMAIL_ADDRESS>Sriram
S.K.S Narayanan and Umesh Vaidya are with the Dept. of Mechanical Engr.,
Clemson University, Clemson SC. Email<EMAIL_ADDRESS>
###### Abstract

The paper is about the computation of the principal spectrum of the Koopman
operator (i.e., eigenvalues and eigenfunctions). The principal eigenfunctions
of the Koopman operator are the ones with the corresponding eigenvalues equal
to the eigenvalues of the linearization of the nonlinear system at an
equilibrium point. The main contribution of this paper is to provide a novel
approach for computing the principal eigenfunctions using a path-integral
formula. Furthermore, we provide conditions based on the stability property of
the dynamical system and the eigenvalues of the linearization towards
computing the principal eigenfunction using the path-integral formula.
Further, we provide a Deep Neural Network framework that utilizes our proposed
path-integral approach for eigenfunction computation in high-dimension
systems. Finally, we present simulation results for the computation of
principal eigenfunction and demonstrate their application for determining the
stable and unstable manifolds and constructing the Lyapunov function.

##  I Introduction

The Koopman operator theory is emerging as a powerful tool for the analysis
and synthesis of nonlinear systems [1, 2, 3, 4, 5, 6, 7]. The linear lifting
of a nonlinear system provided by the Koopman operator in the space of
functions is successfully exploited for control design [8, 9], prediction [10,
11], and uncertainty propagation [12, 13] in a dynamical system. However, the
spectral properties, i.e., the eigenvalues and eigenfunctions, of the Koopman
operator still need to be explored, especially for control [14, 9].

In this paper, we are specifically interested in identifying the principal
eigenfunctions of the Koopman operator. The principal eigenfunctions are
associated with the eigenvalues of the linearization of the nonlinear system
at an equilibrium point. The principal eigenfunctions provide a powerful tool
for analyzing and synthesizing controllers for nonlinear systems. These
eigenfunctions can be used as a change of coordinates for the linear
representation of a nonlinear system over a large region of the state space
[15, 1]. The extent of validity of these eigenfunctions determines the size of
the domain over which the linear representation is valid. For example, in a
system with a stable equilibrium point, these eigenfunctions are well defined
in the domain of attraction of the equilibrium point. The zero-level curves of
the eigenfunction are used to identify the stable and unstable manifolds of
the dynamical system. More recently, the connection between the principal
eigenfunctions of the Koopman operator and the solution of the Hamilton Jacobi
equation has been established [9]. This connection provides a systematic
approach for formulating and solving various control problems, including
optimal control, robust control, and input-output gain analysis of a nonlinear
system [16]. For all these reasons, it becomes imperative to develop
systematic and robust computational methods for determining the principal
spectrum of the Koopman operator. In [17], Taylor and Bernstein’s polynomials
were used to approximate the eigenfunctions. To reduce the computation cost
for high dimensional systems, [18] proposed to decompose the system as a set
of interconnected systems and exploit its sparsity structure. A convex
formulation to approximate the principal eigenfunctions is provided in [19].
However, these methods cannot be easily extended to a general high-dimensional
system.

The main contribution of this paper is to provide a novel approach for the
computation of the principal eigenfunctions of the Koopman operator. The
approach relies on decomposing principal eigenfunctions into linear and purely
nonlinear parts. The linear part of the eigenfunction is obtained as the left
eigenvector of the linearization of system dynamics at the equilibrium point.
The nonlinear part is shown to satisfy a linear partial differential equation
(PDE). The solution of this linear PDE is obtained using a path-integral
formulation. In particular, the value of the eigenfunction at any given point
${\mathbf{x}}_{0}$, is obtained by integrating a known function along the
system trajectory forward in time with ${\mathbf{x}}_{0}$ as the initial
state. We provide conditions based on the stability properties of the system
for the path-integral formula to work. The path-integral approach does not
involve a choice of basis function, making it attractive for complex systems.
Furthermore, we present a DNN framework to approximate the solution of the PDE
for high-dimensional systems. Finally, we demonstrate the application of the
developed framework for the computation of stable/unstable manifolds and the
construction of Lyapunov functions.

##  II Preliminaries and Notations

Consider the continuous-time dynamical system

$\displaystyle\dot{\mathbf{x}}={\mathbf{f}}({\mathbf{x}}),\;\;\;{\mathbf{x}}\in{\mathbf{X}}\subset{\mathbb{R}}^{n}.$
(1)

The following assumption is made on the vector field in the rest of the paper.

######  Assumption 1.

We assume that the vector field ${\mathbf{f}}({\mathbf{x}})$ is at least
${\cal C}^{2}({\mathbf{X}})$ (twice continuously differentiable) and
${\mathbf{x}}=0$ is a hyperbolic equilibrium point of the system, i.e.,
${\mathbf{A}}:=\frac{\partial{\mathbf{f}}}{\partial{\mathbf{x}}}(0)$ has no
eigenvalues on the imaginary axis.

######  Definition 1 (Koopman Operator).

Let ${\mathbf{s}}_{t}({\mathbf{x}})$ be the solution of the dynamical system
(1) at time $t$ starting from the initial condition ${\mathbf{x}}$. The
Koopman operator $\mathbb{U}_{t}:{\cal L}_{\infty}({\mathbf{X}})\to{\cal
L}_{\infty}({\mathbf{X}})$ associated with the dynamical system (1) is defined
as

$\displaystyle[\mathbb{U}_{t}\psi]({\mathbf{x}})=\psi({\mathbf{s}}_{t}({\mathbf{x}})),$
(2)

where $\psi$ (commonly referred to as an observable function) is defined on
${\cal L}_{\infty}({\mathbf{X}})$, which is the space of essentially bounded
functions on ${\mathbf{X}}$. The infinitesimal generator ${\cal K}_{\bf f}$
for the Koopman operator is given by

$\displaystyle\lim_{t\to
0}\frac{(\mathbb{U}_{t}-I)\psi}{t}=\frac{\partial\psi}{\partial{\mathbf{x}}}{\bf
f}({\mathbf{x}})=:{\cal K}_{\bf f}\psi,\;\;t\geq 0.$ (3)

######  Definition 2 (Eigenvalues and Eigenfunctions).

A function $\phi({\mathbf{x}})\in{\cal C}^{1}({\mathbf{X}})$ is said to be an
eigenfunction of the Koopman operator associated with eigenvalue $\lambda$ if

$\displaystyle[{\mathbb{U}}_{t}\phi]({\mathbf{x}})=e^{\lambda
t}\phi({\mathbf{x}}),\;\;{\color[rgb]{0,0,0}t\geq 0}.$ (4)

Using the Koopman generator, equation (4) can be written as

$\displaystyle{\color[rgb]{0,0,0}{\cal K}_{\bf
f}\phi=}\frac{\partial\phi}{\partial{\mathbf{x}}}{\bf
f}({\mathbf{x}})=\lambda\phi({\mathbf{x}}).$ (5)

Notice that equations (4) and (5) provide a “global” definition of Koopman
spectrum in the sense that it holds for all $t\in[0,\infty)$ and all
$x\in{\mathbf{X}}$. However, the spectrum can be defined over finite time or
over a subset of the state space and is of interest to us in this paper.
Furthermore, in this paper, we are also interested in computing the spectrum
associated with the eigenvalues of the linearization of the nonlinear system
at an equilibrium point.

######  Definition 3 (Open Eigenfunction [1]).

Let $\phi:{\bm{\mathcal{C}}}\to{\mathbb{C}}$, where
${\bm{\mathcal{C}}}\subset{\mathbf{X}}$ is not an invariant set. Let
${\mathbf{x}}\in{\bm{\mathcal{C}}}$, and
$\tau\in(\tau^{-}({\mathbf{x}}),\tau^{+}({\mathbf{x}}))=I_{\mathbf{x}}$, a
connected open interval such that
${\mathbf{s}}_{\tau}({\mathbf{x}})\in{\bm{\mathcal{C}}}$ for all $\tau\in
I_{\mathbf{x}}$. If

$[{\mathbb{U}}_{\tau}\phi]({\mathbf{x}})=\phi({\mathbf{s}}_{\tau}({\mathbf{x}}))=e^{\lambda\tau}\phi({\mathbf{x}})\;\;\;\;\forall\tau\in
I_{\mathbf{x}},$

then $\phi$ is called an open eigenfunction of the Koopman operator family
${\mathbf{U}}_{t}$, for $t\in{\mathbb{R}}$ with eigenvalue $\lambda$.

If ${\bm{\mathcal{C}}}$ is a proper invariant subset of ${\mathbf{X}}$ in
which case $I_{\mathbf{x}}={\mathbb{R}}$ for every
${\mathbf{x}}\in{\bm{\mathcal{C}}}$, then $\phi$ is called a subdomain
eigenfunction. If ${\bm{\mathcal{C}}}={\mathbf{X}}$, then $\phi$ will be an
ordinary eigenfunction associated with eigenvalue $\lambda$ as defined in (4).
When ${\bm{\mathcal{C}}}$ is open, the open eigenfunctions as defined above
can be extended from ${\bm{\mathcal{C}}}$ to a larger set which is the
backward-reachable from the closure of ${\bm{\mathcal{C}}}$, based on the
construction procedure outlined in [1, Definition 5.2, Lemma 5.1]. Following
Assumption 1, let ${\cal D}$ be the domain of attraction of the equilibrium
point at the origin. Our interest is in computing the Koopman eigenfunctions
which are defined over this domain ${\cal D}$. Furthermore, these
eigenfunctions are associated with the eigenvalues of the dynamic matrix
${\mathbf{A}}$ of the linearized system around the equilibrium
${\mathbf{x}}=0$. These principal eigenfunctions are connected to the
diffeomorphism as established in the famous Hartman Grobman theorem, which
transforms the nonlinear system into a linear system in a small neighborhood
around the equilibrium point [20, 15]. In fact, these eigenfunctions can be
essentially viewed as the extension of the Hartman Grobman diffeomorphism from
the local neighborhood around the origin to the entire domain of attraction
${\cal D}$ [1, Theorem 5.6].

##  III Main Results

Following Assumption 1, we can write the system dynamics (1) as

$\displaystyle\dot{\mathbf{x}}={\mathbf{f}}({\mathbf{x}})={\mathbf{A}}{\mathbf{x}}+{\mathbf{f}}_{n}({\mathbf{x}}),$
(6)

where
${\mathbf{A}}{\mathbf{x}}:=\frac{\partial{\mathbf{f}}}{\partial{\mathbf{x}}}(0){\mathbf{x}}$
is the linear part and
${\mathbf{f}}_{n}({\mathbf{x}}):={\mathbf{f}}({\mathbf{x}})-{\mathbf{A}}{\mathbf{x}}$
is the purely nonlinear part of the vector field ${\mathbf{f}}({\mathbf{x}})$.
Let $\lambda$ be an eigenvalue of the linearization, i.e., ${\mathbf{A}}$, and
let $\varphi_{\lambda}({\mathbf{x}})$ be the eigenfunction associated with the
eigenvalue $\lambda$ (such eigenfunctions are called principal
eigenfunctions). Similar to the system decomposition into linear and nonlinear
parts, the principal eigenfunction, $\varphi_{\lambda}({\mathbf{x}})$, also
admits a decomposition into linear and nonlinear terms as follows:

$\displaystyle\varphi_{\lambda}({\mathbf{x}})={\mathbf{w}}_{\lambda}^{\top}{\mathbf{x}}+h_{\lambda}({\mathbf{x}}),$
(7)

where ${\mathbf{w}}^{\top}{\mathbf{x}}$ is the linear part and
$h_{\lambda}({\mathbf{x}})$ is the purely nonlinear term and hence satisfies
$\frac{\partial h}{\partial{\mathbf{x}}}(0)=0$. Substituting (7) in equation
(5) and comparing terms, we obtain

$\displaystyle{\mathbf{w}}_{\lambda}^{\top}{\mathbf{A}}=\lambda{\mathbf{w}}_{\lambda}^{\top},$
(8)

i.e., ${\mathbf{w}}_{\lambda}$ is the left eigenvector of ${\mathbf{A}}$ with
eigenvalue $\lambda$. Similarly, the nonlinear part,
$h_{\lambda}({\mathbf{x}})$, of the eigenfunction satisfies the following
linear partial differential equation (PDE)

$\displaystyle\frac{\partial
h_{\lambda}}{\partial{\mathbf{x}}}{\mathbf{f}}({\mathbf{x}})-\lambda
h_{\lambda}({\mathbf{x}})+{\mathbf{w}}_{\lambda}^{\top}{\mathbf{f}}_{n}({\mathbf{x}})=0.$
(9)

The main results of this section on the computation of principal
eigenfunctions of the Koopman operator present an approach for solving
equation (9). We present two different approaches for the computation of the
nonlinear part of the principal eigenfunctions. Our first approach relies on
the path-integral formula for the computation of principal eigenfunctions. Our
second approach relies on the use of a Deep Neural Network for solving the
linear PDE (9).

###  III-A Path-Integral Approach for Computation

Our first results on the path-integral approach for eigenfunction computation
provide a solution formula for the linear PDE (9) using the method of
characteristics.

######  Theorem 1.

The solution formula for the first order linear PDE (9) can be written as

$\displaystyle h_{\lambda}({\mathbf{x}})=e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))+\int_{0}^{t}e^{-\lambda
t}{\mathbf{w}}^{\top}_{\lambda}{\mathbf{f}}_{n}({\mathbf{s}}_{\tau}({\mathbf{x}}))d\tau,$
(10)

where ${\mathbf{s}}_{t}({\mathbf{x}})$ is the solution of the system (6).

###### Proof.

The PDE (9) can be written as

$\displaystyle\frac{dh_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))}{dt}-\lambda
h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))+{\mathbf{w}}^{\top}_{\lambda}{\mathbf{f}}_{n}({\mathbf{s}}_{t}({\mathbf{x}}))=0.$
(11)

Multiplying throughout by $e^{-\lambda t}$, we obtain

$\frac{d(e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}})))}{dt}+e^{-\lambda
t}{\mathbf{w}}^{\top}_{\lambda}{\mathbf{f}}_{n}({\mathbf{s}}_{t}({\mathbf{x}}))=0.$

Next, we integrate the above from $0$ to $t$, thus obtaining

$\displaystyle e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))-h_{\lambda}({\mathbf{x}})+\int_{0}^{t}e^{-\lambda\tau}h_{\lambda}({\mathbf{s}}_{\tau}({\mathbf{x}}))d\tau=0,$
$\displaystyle\implies h_{\lambda}({\mathbf{x}})=e^{-\lambda
t}h_{\lambda}(s_{t}({\mathbf{x}}))+\int_{0}^{t}e^{-\lambda\tau}{\mathbf{w}}^{\top}{\mathbf{f}}_{n}(s_{\tau}({\mathbf{x}}))d\tau.$

This completes our proof. ∎

Our first main result establishes conditions under which the solution of the
PDE (9) is nonlinear.

######  Theorem 2.

For the dynamical system (6) that satisfies Assumption 1, let the origin be an
asymptotically stable equilibrium point with the domain of attraction ${\cal
D}$ and let ${\mathbf{A}}$ be Hurwitz. Furthermore, all the eigenvalues of the
${\mathbf{A}}$ satisfy

$\displaystyle-{\rm Re}(\lambda)+2{\rm Re}(\lambda_{max})<0,$ (12)

where $\lambda_{max}$ is the eigenvalue closest to the $j\omega$ axis and in
the left half plane. Let $h_{\lambda}$ be the solution of PDE (9) as given in
(10). Then,

$\displaystyle\lim_{t\to\infty}e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))=0,\;\;\;\forall{\mathbf{x}}\in{\cal
D}$ (13)

if $h_{\lambda}({\mathbf{x}})$ is purely nonlinear function of ${\mathbf{x}}$
i.e., $\frac{\partial h_{\lambda}}{\partial{\mathbf{x}}}(0)=0$.

###### Proof.

We show that if $h_{\lambda}$ is nonlinear then (13) is true. Since
$h_{\lambda}$ is purely nonlinear, $\nabla_{x}h_{\lambda}(0)=0$ and by
construction $h_{\lambda}(0)=0$. Next, we show that for every $\varepsilon>0$,
there exists $c_{\varepsilon}>0$ such that

$\|h_{\lambda}({\mathbf{x}})\|\leq c_{\varepsilon}\|{\mathbf{x}}\|^{2}$

for all $\|{\mathbf{x}}\|\leq\varepsilon$. By applying the mean value theorem
inside $\|{\mathbf{x}}\|\leq\varepsilon$, we have

$\displaystyle
h_{\lambda}({\mathbf{x}})=h_{\lambda}(0)+\nabla_{\mathbf{x}}h_{\lambda}(0){\mathbf{x}}+{\mathbf{x}}^{T}\nabla_{\mathbf{x}}^{2}h_{\lambda}({\mathbf{z}}){\mathbf{x}}$
$\displaystyle\implies\|h_{\lambda}({\mathbf{x}})\|\leq\|\nabla_{\mathbf{x}}^{2}h_{\lambda}({\mathbf{z}})\|\cdot\|{\mathbf{x}}\|^{2}$

for some point ${\mathbf{z}}$ on the line segment joining $0$ and
${\mathbf{x}}$. Since $h_{\lambda}$ is smooth over the compact domain
$\|{\mathbf{x}}\|\leq\varepsilon$, we can define a constant
$c_{\varepsilon}:=\sup_{\|{\mathbf{x}}\|\leq\varepsilon}\|\nabla_{\mathbf{x}}^{2}h_{\lambda}({\mathbf{x}})\|$,
and obtain the uniform bound $\|h_{\lambda}({\mathbf{x}})\|\leq
c_{\varepsilon}\|{\mathbf{x}}\|^{2}$ in the region
$\|{\mathbf{x}}\|\leq\varepsilon$, where
$c_{\varepsilon}:=\left(\sum_{i}c_{\varepsilon,i}^{2}\right)^{\frac{1}{2}}$.
Now for $\|{\mathbf{x}}\|\leq\varepsilon$, there exists, by Hartman Grobman
theorem, a near identity change of coordinates with inverse in the small
neighborhood around the origin, say of size $\|{\mathbf{x}}\|\leq\epsilon$, of
the form

${\mathbf{z}}={\mathbf{x}}+{\mathbf{d}}({\mathbf{x}})={\mathbf{D}}({\mathbf{x}})\iff{\mathbf{x}}={\mathbf{D}}^{-1}({\mathbf{z}})={\mathbf{z}}+\bar{\mathbf{d}}({\mathbf{z}}),$
(14)

with ${\mathbf{d}}({\mathbf{x}})$ and $\bar{\mathbf{d}}({\mathbf{z}})$ purely
nonlinear such that the nonlinear system is transformed into linear system
i.e.,
$\dot{\mathbf{x}}={\mathbf{A}}{\mathbf{x}}+{\mathbf{f}}_{n}({\mathbf{x}})\implies\dot{\mathbf{z}}={\mathbf{A}}{\mathbf{z}}$
and hence

${\mathbf{s}}_{t}({\mathbf{x}})={\mathbf{D}}^{-1}(e^{{\mathbf{A}}t}{\mathbf{D}}({\mathbf{x}}))\implies{\mathbf{s}}_{t}({\mathbf{x}})={\mathbf{D}}^{-1}(e^{{\mathbf{A}}t}({\mathbf{x}}+{\mathbf{d}}({\mathbf{x}})))$
$=e^{{\mathbf{A}}t}{\mathbf{x}}+e^{{\mathbf{A}}t}{\mathbf{d}}({\mathbf{x}})+\bar{\mathbf{d}}(e^{{\mathbf{A}}t}{\mathbf{x}}+e^{{\mathbf{A}}t}{\mathbf{d}}({\mathbf{x}})).$

In the above, we have used (14) for ${\mathbf{D}}^{-1}$. Since
$\bar{\mathbf{d}}({\mathbf{z}})$ is purely nonlinear, for
$\|{\mathbf{x}}\|\leq\epsilon$, we can get using mean value theorem

$\|\bar{\mathbf{d}}({\mathbf{z}})\|\leq
c_{\bar{d}}\|{\mathbf{z}}\|^{2},\;\;\;\;\|{\mathbf{d}}({\mathbf{x}})\|\leq
c_{d}\|{\mathbf{x}}\|^{2}.$

Using the above inequality, Cauchy Schwartz inequality, and the fact that
$\|{\mathbf{x}}\|\leq\epsilon$, we obtain

$\|{\mathbf{s}}_{t}({\mathbf{x}})\|\leq c_{1}e^{{\rm
Re}(\lambda_{max}t)}\implies\|{\mathbf{s}}_{t}({\mathbf{x}})\|^{2}\leq
c_{1}^{2}e^{{\rm Re}(2\lambda_{max}t)}$

for some constant $c_{1}$ that depends on $\epsilon,c_{d}$, and $\bar{c}_{d}$.
Now

$\|h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))\|\leq
c_{\varepsilon}\|{\mathbf{s}}_{t}({\mathbf{x}})\|^{2}\leq c_{2}e^{{\rm
Re}(2\lambda_{max}t)},$

where $c_{2}=c_{\varepsilon}c_{1}^{2}$. Then, the limit in equation (13)
follows by noting that

$\|e^{-\lambda t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))\|\leq
c_{2}e^{\left(-{\rm Re}(\lambda)+2{\rm Re}(\lambda_{max})\right)t}.$

∎

Using the results of the above theorem we have the following results for the
computation of Koopman eigenfunctions under the stability assumption on the
system dynamics.

######  Theorem 3.

Consider the dynamical system (6) with origin asymptotically stable and with
the domain of attraction ${\cal D}$. Let the eigenvalue $\lambda$ of matrix
${\mathbf{A}}$ satisfy condition (12). Then the principal eigenfunction,
$\phi_{\lambda}$, corresponding to eigenvalue $\lambda$, is well defined in
the domain ${\cal D}$ and is given by following path-integral formula:

$\displaystyle\phi_{\lambda}({\mathbf{x}})={\mathbf{w}}_{\lambda}^{\top}{\mathbf{x}}+\int_{0}^{\infty}e^{-\lambda
t}{\mathbf{w}}_{\lambda}^{\top}{\mathbf{f}}_{n}({\mathbf{s}}_{t}({\mathbf{x}}))dt$
(15)

where ${\mathbf{w}}_{\lambda}$ satisfies
${\mathbf{w}}_{\lambda}^{\top}{\mathbf{A}}=\lambda{\mathbf{w}}_{\lambda}^{\top}$.

###### Proof.

The eigenfunction corresponding to eigenvalue $\lambda$ admits a decomposition
into linear and nonlinear parts as given in Eqs. (7) and (8). Since
$h_{\lambda}$ is assumed to be nonlinear, the results of Theorem 2 applies and
hence $\lim_{t\to\infty}e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))=0$ for all ${\mathbf{x}}\in{\cal
D}$. The result then follows by applying Theorem 1 on the solution formula of
linear PDE. ∎

######  Remark 1.

The eigenfunctions $\phi_{\lambda_{i}}$ for $i=1,\ldots,n$ can be used as
diffeomorphism for the linearization of nonlinear system valid within the
domain of attraction ${\cal D}$. In [15, 1], the authors propose an approach
for the construction of such diffeomorphism valid within the domain of
attraction based on the extension of the Hartman Grobman diffeomorphism, which
is known to exist in a small neighborhood of the origin.

The results of Theorem 3 can be extended to compute the Koopman spectrum for
the system with linearization having all its eigenvalues in the right half
plane by time reversing the vector field. We have the following Corollary in
this direction.

######  Corollary 1.

Consider the dynamical system (6) satisfying Assumption 1. Let the matrix
${\mathbf{A}}$ for the linearization of system dynamics have all its
eigenvalues in the strict right half plane with eigenvalue, $\lambda$,
satisfying the condition

$\displaystyle{\rm Re}(\lambda)-2{\rm Re}(\lambda_{max})<0.$ (16)

The principal eigenfunction, $\phi_{\lambda}$, with eigenvalue $\lambda$, are
well defined in the domain $\bar{\cal
D}:=\\{{\mathbf{x}}\in{\mathbf{X}}:\lim_{t\to\infty}{\mathbf{s}}_{-t}({\mathbf{x}})=0\\}$
and is given by the following formula

$\displaystyle\phi_{\lambda}({\mathbf{x}})={\mathbf{w}}_{\lambda}^{\top}{\mathbf{x}}+\int_{0}^{\infty}e^{\lambda
t}{\mathbf{w}}_{\lambda}^{\top}{\mathbf{f}}({\mathbf{s}}_{-t}({\mathbf{x}}))dt,$
(17)

where ${\mathbf{w}}_{\lambda}$ satisfies
${\mathbf{w}}_{\lambda}^{\top}{\mathbf{A}}=\lambda{\mathbf{w}}_{\lambda}^{\top}$.

Theorem 3 and Corollary 1 provide an approach for computing the Koopman
principal eigenfunctions for the cases when the equilibrium point is stable
and anti-stable. It is important to emphasize that the results of Theorem 3
and Corollary 1 rely on the sufficient condition that can be verified for the
computation of principal eigenfunction. The following theorem for principal
eigenfunction computation applies to a system with a saddle-type equilibrium
point.

######  Theorem 4.

Consider the dynamical system (6) satisfying Assumption 1 with $\lambda$ as an
eigenvalue of ${\mathbf{A}}$ such that ${\rm Re}(\lambda)>0$. Assume that
$h_{\lambda}({\mathbf{x}})$, the nonlinear part of the principal eigenfunction
corresponding to eigenvalue $\lambda$ satisfy

$\displaystyle\lim_{t\to\infty}|h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))|\leq
M$ (18)

for some constant $M$ and for all ${\mathbf{x}}$ in some set
${\mathbf{X}}_{1}\subseteq{\mathbf{X}}$. Then the eigenfunction corresponding
to eigenvalue $\lambda$ can be computed using the following path-integral
formula for all ${\mathbf{x}}\in{\mathbf{X}}_{1}:$

$\displaystyle\phi_{\lambda}({\mathbf{x}})={\mathbf{w}}_{\lambda}^{\top}{\mathbf{x}}+\int_{0}^{\infty}e^{-\lambda
t}{\mathbf{w}}_{\lambda}^{\top}{\mathbf{f}}({\mathbf{s}}_{t}({\mathbf{x}}))dt.$
(19)

###### Proof.

The condition (18) combined with the fact that ${\rm Re}(\lambda)>0$ ensure
that $\lim_{t\to\infty}e^{-\lambda
t}h_{\lambda}({\mathbf{s}}_{t}({\mathbf{x}}))=0$. The expression (19) then
follows from (7) and the PDE solution (10) by taking $t\rightarrow 0.$ ∎

Note that the main issue with applying the results from the above Theorem is
that the condition (18) cannot be easily verified. For a system with saddle-
type equilibrium point, computation of eigenfunctions corresponding to
eigenvalues with negative real part can be similarly done by applying the
results of Theorem 4 for the time-reversed vector field. We would like to
emphasize that in applications such as optimal control, it is of interest to
compute only part of eigenfunctions corresponding to unstable eigenvalues [9]

###  III-B Deep Neural Network for Principal Eigenfunction

Deep learning techniques have been successfully applied in literature towards
computation of the Koopman operator and its associated eigenfunctions [21,
22]. In all of these prior works, the main approach is to parameterize the
eigenfunctions (or nonlinear ‘lifting’ functions in other cases) using
autoencoders and then utilizing sampled trajectory data to compute the loss
function for training.

Let
$\mathcal{P}=\left\\{({\mathbf{x}}_{i},\mathbf{y}_{i})\right\\}_{i\in\mathcal{I}}$
be a set of points along system trajectories sampled at a uniform time
interval $\tau$, that is,

${\mathbf{y}}_{i}={\mathbf{s}}_{\tau}({\mathbf{x}}_{i}),\;i\in\mathcal{I}.$

Then, the DNN parameterized vector of eigenfunctions or lifting functions
$\psi_{\theta}$ is typically learned by minimizing the loss

$\min_{K,\theta,\omega}\left[\begin{array}[]{c}\underset{({\mathbf{x}},{\mathbf{y}})\sim\mathcal{D}}{\mathbb{E}}\big{[}\|\psi_{\theta}({\mathbf{y}})-K\psi_{\theta}({\mathbf{x}})\|\big{]}\;+\\\
\underset{x\sim{\mathbf{X}}}{\mathbb{E}}\big{[}\|{\mathbf{x}}-\eta_{\omega}\big{(}\psi_{\theta}({\mathbf{x}})\big{)}\|\big{]}\end{array}\right],$
(20)

where $\mathbb{E}[\cdot]$ denotes the expected value with respect to the data
distribution specified. The function $\eta_{\omega}$ is a decoder network
parameterized by $\omega$, which maps points from the lifted Koopman space
back to the original state-space and $K$ is the finite-dimensional
approximation of the Koopman operator. The second term in the equation above
is the auto-encoder loss and is needed to ensure that the DNN does not learn a
trivial solution $\psi_{\theta}\equiv 0$. In place of the first term, it is
also common to use Koopman PDE (2) in the loss function, wherein one penalizes
the violation in the PDE satisfaction. In the case where the DNN parameterizes
the lifting function, one needs to indirectly extract the eigenfunctions using
the learned $K$ matrix and $\psi_{\theta}$.

Our approach using path-integral can be used to learn the principal Koopman
eigenfunctions in a more direct fashion, using the equation (7) to create a
labeled training dataset
$\mathcal{D}^{\prime}=\left\\{({\mathbf{x}}_{i},\phi_{\lambda}({\mathbf{x}}_{i}))\right\\}_{i\in\mathcal{I}}$,
thus leading to the following supervised learning problem:

$\min_{\theta}\underset{({\mathbf{x}},{\mathbf{z}})\sim\mathcal{D}^{\prime}}{\mathbb{E}}\left[\|{\mathbf{z}}-{\mathbf{w}}^{\top}{\mathbf{x}}-\hat{h}_{\theta}({\mathbf{x}})\|\right],$
(21)

where $\theta$ parameterizes the nonlinear part of the principal eigenfunction
using the DNN $\hat{h}_{\theta}$. Additionally, one can introduce the
following secondary term in the loss function for regularization:

$\underset{{\mathbf{x}}\in
X}{\mathbb{E}}\left[\Big{\|}\frac{\partial\hat{h}_{\theta}}{\partial{\mathbf{x}}}{\mathbf{f}}({\mathbf{x}})-\lambda\hat{h}_{\theta}({\mathbf{x}})+{\mathbf{w}}^{\top}{\mathbf{f}}_{n}({\mathbf{x}})\Big{\|}\right].$
(22)

This ensures that the network does not overfit to the dataset
$\mathcal{D}^{\prime}$. Note that this secondary term (22) is much cheaper to
evaluate compared to the loss term in (21) due to offline computations
involved in the generation of labeled dataset $\mathcal{D}^{\prime}$.
Moreover, since PDE (9) does not admit a trivial solution (unlike PDE (2)), we
do not need an additional auto-encoder loss term like in equation (20).

##  IV Simulation Results

Analytical Example 1: Consider the dynamics of a one-dimensional system given
by

$\displaystyle\dot{x}=\alpha(x-x^{3}).$

The principal eigenfunctions for this system can be computed analytically as
$\phi(x)=\frac{x}{\sqrt{1-x^{2}}}$. Note that $\phi(x)$ is well-defined within
the domain $x\in(-1,1)$. For $\alpha=-1$, the system has a stable equilibrium
point at the origin (with eigenvalue $\lambda=-1$). Although $\phi(x)$ blows
up as $x\xrightarrow{}(-1,1)$, since ${\mathbf{s}}_{t}(x)\xrightarrow{}0$,
condition in Eq. (13) is satisfied. The corresponding eigenfunction can be
estimated using Theorem 3 as shown in Fig. 1a. For $\alpha=1$, the origin is
unstable, and hence the results of Theorem 3 do not apply. But the results of
Corollary 1 apply, and the estimated eigenfunction using Eq. (17) matches
perfectly with the analytical solution.

Figure 1: Analytical example 1: (a) eigenfunction corresponding to stable
eigenvalue estimated using Theorem 3 (b)  eigenfunction corresponding to
unstable eigenvalue estimated using Corollary 1.

Analytical Example 2: Consider the dynamics of a two-dimensional system given
by

$\displaystyle\dot{x}_{1}=-2\lambda_{2}x_{2}(x_{1}^{2}-x_{2}-2x_{1}x_{2}^{2}+x_{2}^{4})$
$\displaystyle+\lambda_{1}(x_{1}+4x_{1}^{2}x_{2}-x_{2}^{2}-8x_{1}x_{2}^{3}+4x_{2}^{5})$
$\displaystyle\dot{x}_{2}=2\lambda_{1}(x_{1}-x_{2}^{2})^{2}-\lambda_{2}(x_{1}^{2}x_{2}-2x_{1}x_{2}^{2}+x_{2}^{4})$

where $\lambda_{1},\lambda_{2}$ are the eigenvalues of the system when
linearized about the origin [23]. For this system, the eigenfunctions can be
computed analytically as $\phi_{\lambda_{1}}(x)=x_{1}-x_{2}^{2}$ and
$\phi_{\lambda_{2}}(x)=-x_{1}^{2}+x_{2}+2x_{1}x_{2}^{2}-x_{2}^{4}$. We pick
the eigenvalues $\lambda_{1}=-1$ and $\lambda_{2}=3$ such that the system has
a saddle equilibrium at the origin. The analytical eigenfunction corresponding
to $\lambda_{2}=3$ is shown in Fig. 2a. The  eigenfunction corresponding to
the unstable eigenvalues can be estimated accurately using Theorem 4 as shown
in Figure 2b.

Figure 2: Analytical Example 2 with saddle equilibrium point: Eigenfunction
corresponding to ${\rm Re}(\lambda)>0$. (a) analytical (b) estimated using
Theorem 3.

Duffing Oscillator: The Duffing oscillator dynamics is

$\displaystyle\dot{{x}}_{1}={x}_{2},\;\;\;\;\dot{{x}}_{2}={x}_{1}-\delta{x}_{2}-{x}_{1}^{3}$

For eigenfunction computation, we use $\delta=0.5$. The equilibrium point at
the origin is a saddle point. Fig. 3a shows the  eigenfunction corresponding
to the unstable eigenvalue obtained for the equilibrium point at the origin
after $t=20$ s using Theorem 4. Since the eigenfunctions remain bounded,
equation (13) is satisfied. The stable manifold (shown in yellow in Fig. 3b)
is obtained as the zero-level set of this eigenfunction. The magnitude of the
(complex) eigenfunction corresponding to the stable eigenvalue obtained after
$t=20s$ for the equilibrium point at [1,0] is shown in Fig. 3c.

The Lyapunov function verifying the stability of the equilibrium dynamics is
constructed as
$V({\mathbf{x}})=\Phi^{\top}({\mathbf{x}}){\mathbf{P}}\Phi({\mathbf{x}})$,
where ${\mathbf{P}}$ is a positive matrix obtained as the solution of the
following Lyapunov equation $\Lambda^{\top}{\mathbf{P}}+{\mathbf{P}}\Lambda<0$
[17]. The Lyapunov function for this system is shown in Fig. 3d.

Figure 3: Duffing Oscillator: (a) eigenfunction (real) for $\lambda=0.78$ at
the (0,0); (b) zero level set representing the stable manifold; (c) magnitude
of the eigenfunction (complex) for $\lambda=-0.25\pm 1.39j$ at $(1,0)$; (d)
Lyapunov function obtained from (c)

Two Link Robotic Arm: Consider the following Euler-Lagrange dynamics
representing a 2-link manipulator:

${\mathbf{M}}({\mathbf{q}})\ddot{{\mathbf{q}}}+\mathbf{C}({\mathbf{q}},\dot{{\mathbf{q}}})\dot{{\mathbf{q}}}+{\mathbf{G}}({\mathbf{q}})={\mathbf{B}}\dot{{\mathbf{q}}}$
(23)

where ${\mathbf{q}}\in\mathbb{R}^{2}$ represents the generalized coordinates
of the manipulator. Specifically, we take

${\mathbf{M}}({\mathbf{q}})=\left[\begin{array}[]{cc}2\cos(q_{2})+8.33&\cos(q_{2})+0.33\\\
\cos(q_{2})+0.33&0.33\end{array}\right]$
$\mathbf{C}({\mathbf{q}},\dot{{\mathbf{q}}})=\left[\begin{array}[]{cc}-2\dot{q}_{2}\sin(q_{2})&-\dot{q}_{2}\sin(q_{2})\\\
\dot{q}_{1}\sin(q_{2})&0\end{array}\right]$
${\mathbf{G}}({\mathbf{q}})=\left[\begin{array}[]{c}50\sin(q_{1})+5\sin(q_{1}+q_{2})\\\
5\sin(q_{1}+q_{2})\end{array}\right]$

and ${\mathbf{B}}=diag[5.5,\quad 0.001]$, where $diag$ represents a diagonal
matrix. We take the $4$-dimensional state to be
${\mathbf{x}}=[q_{1},q_{2},\dot{q}_{1},\dot{q}_{2}]$, and rewrite the dynamics
(23) in standard form as $\dot{{\mathbf{x}}}=\mathbf{f}({\mathbf{x}}).$ The
linearized system about the stable equilibrium ${\mathbf{x}}=0$ has complex
eigenvalues $\lambda_{1,2}=-0.23\pm 2.29j$ and $\lambda_{3,4}=-0.32\pm 5.32j$,
thus leading to complex eigenfunctions. We pick a domain
$[-\frac{\pi}{12},\frac{\pi}{12}]^{4}$ over which we compute the path
integrals and create a dataset $\mathcal{D}^{\prime}$ as described in
Subsection III-B. This dataset, along with the sum of losses (21) and (22), is
then used to train a multi-layer perceptron network (MLP) with a sinusoidal
activation function. The MLP has 3 hidden layers, each with 128 neurons. The
input layer is of size 4, and the output layer has a size 2, corresponding to
the real and imaginary parts of the eigenfunction being learned. Fig. 4 shows
the magnitude and phase of the complex eigenfunction along the system
trajectory starting at random initial conditions within the domain. It can be
seen that the magnitude of the eigenfunction goes to zero along the stable
trajectory.

Figure 4: Magnitude of the eigenfunction corresponding to stable eigenvalue
$\lambda=-0.23\pm 2.29j$ along the trajectories of the system starting from
random initial conditions

##  V Conclusions

We provide a novel approach for the computation of principal eigenfunctions of
the Koopman operator based on the path-integral formula. Furthermore, the
path-integral formula is used to formulate the DNN-based approach for
computing the eigenfunctions. Simulation results show that the path-integral-
based approach accurately approximates the principal eigenfunctions of systems
with complex dynamics. We demonstrate the applications of eigenfunctions for
the computation of stable/unstable manifolds and the Lyapunov function.
Simulation results involving analytical examples, duffing oscillator, and two
links robotic arm are presented to show the efficacy of the developed
framework. Future research will focus on a data-driven approach for the
computation of principal eigenfunctions and its extension to discrete-time
dynamical systems.

## References

  * [1] I. Mezić, “Spectrum of the Koopman operator, spectral expansions in functional spaces, and state-space geometry,” _Journal of Nonlinear Science_ , vol. 30, no. 5, pp. 2091–2145, 2020.
  * [2] B. Huang, X. Ma, and U. Vaidya, “Data-driven nonlinear stabilization using koopman operator,” in _The Koopman Operator in Systems and Control_. Springer, 2020, pp. 313–334.
  * [3] ——, “Optimal quadratic regulation of nonlinear system using koopman operator,” in _2019, American Control Conference_. IEEE, 2019.
  * [4] B. Huang and U. Vaidya, “A convex approach to data-driven optimal control via perron-frobenius and koopman operators,” _IEEE Transactions on Automatic Control_ , 2022.
  * [5] M. Korda and I. Mezić, “On convergence of extended dynamic mode decomposition to the Koopman operator,” _Journal of Nonlinear Science_ , vol. 28, no. 2, pp. 687–710, 2018.
  * [6] J. Moyalan, H. Choi, Y. Chen, and U. Vaidya, “Data-driven optimal control via linear transfer operators: A convex approach,” _Automatica_ , vol. 150, p. 110841, 2023.
  * [7] S. Sinha, U. Vaidya, and E. Yeung, “On computation of koopman operator from sparse data,” in _2019 American Control Conference (ACC)_. IEEE, 2019, pp. 5519–5524.
  * [8] M. Korda and I. Mezić, “Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control,” _Automatica_ , vol. 93, pp. 149–160, 2018.
  * [9] U. Vaidya, “Spectral analysis of Koopman operator and nonlinear optimal control,” _IEEE Control and Decision Conference._ , 2022.
  * [10] E. Kaiser, J. N. Kutz, and S. L. Brunton, “Sparse identification of nonlinear dynamics for model predictive control in the low-data limit,” _Proceedings of the Royal Society A_ , vol. 474, no. 2219, p. 20180335, 2018\.
  * [11] S. L. Brunton, B. W. Brunton, J. L. Proctor, and J. N. Kutz, “Koopman invariant subspaces and finite linear representations of nonlinear dynamical systems for control,” _PloS one_ , vol. 11, no. 2, p. e0150171, 2016.
  * [12] A. R. R. Matavalam, U. Vaidya, and V. Ajjarapu, “Data-driven approach for uncertainty propagation and reachability analysis in dynamical systems,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 3393–3398.
  * [13] S. Sinha, U. Vaidya, and R. Rajaram, “Operator theoretic framework for optimal placement of sensors and actuators for control of nonequilibrium dynamics,” _Journal of Mathematical Analysis and Applications_ , vol. 440, no. 2, pp. 750–772, 2016.
  * [14] M. Korda and I. Mezic, “Optimal construction of koopman eigenfunctions for prediction and control,” _IEEE Transactions on Automatic Control_ , 2020\.
  * [15] Y. Lan and I. Mezić, “Linearization in the large of nonlinear systems and Koopman operator spectrum,” _Physica D: Nonlinear Phenomena_ , vol. 242, no. 1, pp. 42–53, 2013.
  * [16] S. Sutavani, B. Umathe, and V. Umesh, “Small gain theorem and l2 gain computation in large using koopman spectrum,” _American Control Conference_ , 2023.
  * [17] A. Mauroy and I. Mezić, “Global stability analysis using the eigenfunctions of the koopman operator,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 11, pp. 3356–3369, 2016.
  * [18] C. Schlosser and M. Korda, “Sparsity structures for koopman and perron–frobenius operators,” _SIAM Journal on Applied Dynamical Systems_ , vol. 21, no. 3, pp. 2187–2214, 2022.
  * [19] B. Umathe, D. Tellez-Castro, and U. Vaidya, “Reachability analysis using spectrum of koopman operator,” _IEEE Control Systems Letters_ , vol. 7, pp. 595–600, 2022.
  * [20] V. I. Arnold, _Geometrical methods in the theory of ordinary differential equations_. Springer Science & Business Media, 2012, vol. 250.
  * [21] B. Lusch, J. N. Kutz, and S. L. Brunton, “Deep learning for universal linear embeddings of nonlinear dynamics,” _Nature communications_ , vol. 9, no. 1, pp. 1–10, 2018.
  * [22] C. Folkestad, D. Pastor, I. Mezic, R. Mohr, M. Fonoberova, and J. Burdick, “Extended dynamic mode decomposition with learned koopman eigenfunctions for prediction and control,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 3906–3913.
  * [23] E. M. Bollt, Q. Li, F. Dietrich, and I. Kevrekidis, “On matching, and even rectifying, dynamical systems through koopman operator eigenfunctions,” _SIAM Journal on Applied Dynamical Systems_ , vol. 17, no. 2, pp. 1925–1960, 2018.


# QED: A Framework and Dataset for Explanations in Question Answering

Matthew Lamm1 , Jennimaria Palomaki2, Chris Alberti2,
Daniel Andor2, Eunsol Choi3 , Livio Baldini Soares2, Michael Collins2

1Department of Linguistics, Stanford University
2Google Research
3Department of Computer Science, The University of Texas at Austin
<EMAIL_ADDRESS>{jpalomaki, chrisalberti, danielandor, liviobs,
<EMAIL_ADDRESS><EMAIL_ADDRESS>Work done during internship at
Google. Work done at Google.

###### Abstract

A question answering system that in addition to providing an answer provides
an explanation of the reasoning that leads to that answer has potential
advantages in terms of debuggability, extensibility and trust. To this end, we
propose QED, a linguistically informed, extensible framework for explanations
in question answering. A QED explanation specifies the relationship between a
question and answer according to formal semantic notions such as referential
equality, sentencehood, and entailment. We describe and publicly release an
expert-annotated dataset of QED explanations built upon a subset of the Google
Natural Questions dataset, and report baseline models on two tasks – post-hoc
explanation generation given an answer, and joint question answering and
explanation generation. In the joint setting, a promising result suggests that
training on a relatively small amount of QED data can improve question
answering. In addition to describing the formal, language-theoretic
motivations for the QED approach, we describe a large user study showing that
the presence of QED explanations significantly improves the ability of
untrained raters to spot errors made by a strong neural QA baseline.

##  1 Introduction

Question: who wrote the film howl’s moving castle?
Passage: Howl’s Moving Castle is a 2004 Japanese animated fantasy film written
and directed by Hayao Miyazaki. It is based on the novel of the same name,
which was written by Diana Wynne Jones. The film was produced by Toshio
Suzuki.
Answer: Hayao Miyazaki

(1) Sentence Selection
Howl’s Moving Castle is a 2004 Japanese animated fantasy film written and
directed by Hayao Miyazaki.
(2) Referential Equality
the film howl’s moving castle = Howl’s Moving Castle
(3) Entailment
X is a 2004 Japanese animated fantasy film written and directed by
ANSWER.$\mkern 2.0mu\vdash$ ANSWER wrote X.

Figure 1: QED explanations decompose the question-passage relationship in
terms of referential equality and predicate entailment.

Question Answering (QA) systems can enable efficient access to the vast amount
of information that exists as text (Rajpurkar et al., 2016; Kwiatkowski et
al., 2019; Clark et al., 2019; Reddy et al., 2019, i.a.). Modern neural
systems have made tremendous progress in QA accuracy in recent years Devlin et
al. (2019). However, they generally give no explanation or justification of
how they arrive at an answer to a question. Models that in addition to
providing an answer can explain their reasoning may have significant benefits
pertaining to trust and debuggability Doshi-Velez and Kim (2017); Ehsan et al.
(2019).

Critical questions then, are what constitutes an explanation in question
answering, and how can we enable models to provide such explanations. In an
effort to make progress on these questions, in this paper we make the
following contributions: (1) we introduce QED111QED stands for the Latin “quod
erat demonstrandum” or “that which was to be shown”., a linguistically
grounded definition of QA explanations; and (2) we describe a corpus of QED
annotations based on the Natural Questions Kwiatkowski et al. (2019). The QED
corpus has been released publicly.222https://github.com/google-research-
datasets/QED.

Figure 1 shows a QED example. Given a question and a passage, QED represents
an explanation as a combination of discrete, human-interpretable steps: (1)
identification of a sentence implying an answer to the question, (2)
identification of noun phrases in both the question and answering sentence
that refer to the same thing, and (3) confirmation that the predicate in the
sentence entails the predicate in the question once referential equalities are
abstracted away.

This choice of explanation makes use of core semantic relations—referential
equality and entailment—and thus has well-understood formal properties. (See
Section 2 for further discussion.) In addition, we found that this way of
decomposing explanations has high coverage (77% on the Natural Questions
corpus333Instances with annotated short answers, omitting table passages.).
Since QED decomposes the QA process into distinct subproblems, we also believe
that it should enable research directions aimed at extending or improving upon
extant QA systems.

In what follows, after contextualizing the present work in the broader
discussion on explainability, we present a formal definition of QED
explanations. We then describe the dataset of QED annotations (7638/1353
train/dev examples), including discussion of the distribution of linguistic
phenomena exhibited in the data. We move to propose four potential tasks, of
varying complexity, related to the QED framework, and use the QED annotations
to train and evaluate baseline models on two of these. Additionally, we
describe a rater study which shows how the presence of QED explanations can
help users identify errors made by an automated QA system.

##  2 Motivation: The Need for Explanations in Question Answering

We take as our departure point the following passage from Ehsan et al. (2018)
concerning explainable AI:

> Explainability is important in situations where human operators work
> alongside autonomous and semi-autonomous systems because it can help build
> rapport, confidence, and understanding between the agent and its operator.
> In the event that an autonomous system fails to complete a task or completes
> it in an unexpected way, explanations help the human collaborator understand
> the circumstances that led to the behavior, which also allows the operator
> to make an informed decision on how to address the behavior.

This quote refers to AI and ML systems in general, but is highly relevant to
QA systems. Explanations can help users understand and trust a QA system, and
can help them to work in tandem with a QA system to fulfill their information
needs. Explanations can also help system builders to understand and debug QA
systems, and also to extend them.

QED makes a particular choice about the form of explanations for QA. In
particular, it decomposes the question-answer relationship according to known
semantic and syntactic categories – sentence, reference (and referential
equality), predicate, and entailment. The explanations provided in QED are
discrete structured objects, as opposed, for example, to “heat map"-style
explanations (attention distributions, or other real-valued, word-level
feature importance measures) Jacovi and Goldberg (2020).

One major goal in developing QED is to define models which provide faithful
explanations; that is, explanations that in some sense truly reflect the
underlying computation or reasoning performed by a question-answering model.
(See Section 7 for more discussion.) Another major goal, which is closely
related to faithfulness, is to develop models that have a sound basis in
concepts from cognitive science and linguistics, and are thus closer to human
reasoning. For example reference, a core component of QED, is fundamental to
semantics and cognition Russell (1905); Clark and Marshall (1981); Tomasello
et al. (2007).

##  3 Annotation Definition

We now describe the form of QED annotations. Section 3.1 gives an overview of
the annotation process. Section 3.2 then gives a formal definition, which is
extended in Section 3.3.

###  3.1 An Overview of the Approach

We will use the following example to illustrate the approach:

Question: how many seats in university of michigan stadium Passage: Michigan
Stadium, nicknamed “The Big House”, is the football stadium for the University
of Michigan in Ann Arbor, Michigan. It is the largest stadium in the United
States and the second largest stadium in the world. Its official capacity is
107,601.

The annotator is presented with a question/passage pair. Annotation then
proceeds in the following four steps:

##### (1) Single Sentence Selection.

The annotator identifies a single sentence in the passage that entails an
answer to the question assuming that coreference and bridging anaphora (see
Section 3.3) have been resolved in the sentence.444If it is not possible to
find a sentence that satisfies these properties—typically because the answer
requires inference beyond coreference/bridging that involves multiple
sentences—the annotator marks the example as not possible. See Section 4.

In the above example, the following sentence entails an answer to the
question, and would be selected by the annotator:

> Its official capacity is 107,601.

This follows because given the passage context, “Its” refers to the same thing
as the NP “university of michigan stadium” in the question, and the predicate
in the sentence, “X’s official capacity is 107,601”, entails the predicate in
the question “how many seats in X”.

##### (2) Answer Selection.

The annotator highlights a short answer span (or spans) in the answer
sentence. In the above example the annotator would mark the following (answer
shown with [=A…]):

> Its official capacity is [=A 107,601].

In addition if the answer appears in the sentence in the form of a pronoun,
bridged reference or underspecified NP, the annotator resolves the underlying
coreference within the passage (see Section 3.3 for more discussion).

##### (3) Identification of Question-Sentence Noun Phrase Equalities.

The annotator marks referentially equivalent noun phrases, or noun phrases
that refer to the same thing, in the question and the answer sentence. This
includes reference not only to individuals and other proper nouns, but also to
generic concepts.

In our example the annotator would mark the following two noun-phrases (marked
with the [=1 …] annotations) as referentially equivalent:

how many seats in [=1 university of michigan stadium]
---
[=1 Its] official capacity is [=A 107,601]

##### (4) Extraction of an Entailment Pattern.

As a final, automatic step, an entailment pattern can be extracted from the
annotated example by abstracting over referentially equivalent noun phrases,
and the answer. In the above example the entailment pattern would be as
follows:

> how many seats in X
>
> X’s official capacity is ANSWER

###  3.2 A Formal Definition

An annotator is presented with a question $q$ that consists of $m$ tokens
$q_{1}\ldots q_{m}$, along with a passage $c$ consisting of $n$ tokens
$c_{1}\ldots c_{n}$.

The QED annotation is a triple $\langle s,e,a\rangle$ where:

  * •

$s$ is a sentence within the context $c$. Specifically $s$ is a pair
${s_{0}},{s_{1}}$ indicating that the sentence spans words $c_{{s_{0}}}\ldots
c_{{s_{1}}}$ inclusive.

  * •

$e$ is a sequence of $0$ or more “referential equality annotations”,
$e_{1}\ldots e_{|e|}$. Each member of $e$ specifies that some noun phrase
within the question refers to the same item in the world as some noun phrase
within the sentence $s$.

  * •

$a$ is one or more answer annotations $a_{1}\ldots a_{|a|}$.

We now describe the form of the $e$ and $a$ annotations. As a preliminary
step, given the paragraph $c$ and sentence $s$, we use ${\cal S}$ to refer to
the set of all phrases within $s$. Our initial definition of ${\cal S}$ is

${\cal S}=\\{(i,j):{s_{0}}\leq i\leq j\leq{s_{1}}\\}$

We also define the set of question phrases ${\cal Q}$ and passage phrases
${\cal C}$ to be

$\displaystyle{\cal Q}$ $\displaystyle=$ $\displaystyle\\{(i,j):1\leq i\leq
j\leq m\\}$ $\displaystyle{\cal C}$ $\displaystyle=$
$\displaystyle\\{(i,j):1\leq i\leq j\leq n\\}$

We can then give the following definitions:

###### Definition 1

Each referential equality annotation $e_{k}$ for $k=1\ldots|e|$ is a pair
$(\phi_{k},\pi_{k})\in{\cal Q}\times{\cal S}$, specifying that the phrase
$\phi_{k}$ in the query refers to the same thing in the world as the phrase
$\pi_{k}$ within $s$.

###### Definition 2

Each answer annotation $a_{k}$ for $k=1\ldots|a|$ is a pair
$(\pi_{k},\xi_{k})\in{\cal S}\times{\cal C}$ specifying that the answer is
given by phrase $\pi_{k}$, and the full string corresponding to $\pi_{k}$
after coreference is resolved is the phrase $\xi_{k}$. If no coreference
resolution is required then $\pi_{k}=\xi_{k}$.

To illustrate the treatment of coreference resolution within answers, consider
the following:

Question: who won wimbledon in 2019 Passage: Simona Halep is a female tennis
player. She won Wimbledon in 2019.

In this case the single sentence She won Wimbledon in 2019 would be selected
by the annotator in step 1, as once coreference is resolved, this entails the
answer to the question. The QED annotation would be as follows

who won [=1 wimbledon] in [=2 2019]

[=A She] won [=1 Wimbledon] in [=2 2019]

However, the answer "She" is not sufficient, as it involves an unresolved
anaphor. Because of this, the annotator would mark the fact that "She" refers
to "Simona Halep" earlier in the passage. In this case the answer is a pair
$(\pi,\xi)$ where $\pi$ corresponds to "She" within the sentence, and $\xi$
corresponds to the earlier phrase "Simona Halep".

###  3.3 Extending Annotations to Include Bridging

Bridging anaphora Clark (1975) are frequently encountered in the QA passages
in our data, and in Wikipedia more broadly. This section describes an
extension to include annotations of bridging anaphora. Consider the following:

Question: who won america’s got talent season 11 Passage: The 11th season of
America’s Got Talent, an American talent show competition, began broadcasting
in the United States during 2016. Grace VanderWaal was announced as the winner
on September 14, 2016.

It is clear from context surrounding the sentence "Grace VanderWaal was
announced as the winner on September 14, 2016" that the noun phrase "the
winner" refers to "the winner of America’s Got Talent Season 11", and hence
the sentence provides an answer to the question. It is helpful to imagine that
there is an implicit prepositional phrase "of America’s Got Talent Season 11"
modifying "the winner".

Another motivating example is the following:

Question: who sang the national anthem at the first game of 2017 world series
Passage: Game 1 of the 2017 World Series: The ceremonial first pitch was
thrown out by members of former Dodger Jackie Robinson’s family, including his
widow Rachel. The game marked the 45th anniversary of Robinson’s death. Keith
Williams Jr., a gospel singer, performed “The Star-Spangled Banner”, the
national anthem.

In this case it is clear that the sentence "Keith Williams Jr., a gospel
singer, performed “The Star-Spangled Banner”, the national anthem" is
referring to a performance at Game 1 of the 2017 World Series, and hence that
this sentence provides an answer to the question. In some sense there is an
implicit prepositional phrase "at the first game of 2017 world series"
modifying the entire sentence.

Recall that the set of phrases within the sentence $s$ was previously defined
as ${\cal S}=\\{(i,j):{s_{0}}\leq i\leq j\leq{s_{1}}\\}$. We extend QED by
redefining ${\cal S}$ to include implicit phrases introduced in the form of
implicit prepositional phrases, as in the "winner [of …]" and "[at the first
game …]" examples above. The modified definition of ${\cal S}$ includes all
phrases of the following form: (1) Any pair $(i,j)$ such that ${s_{0}}\leq
i\leq j\leq{s_{1}}$ indicating the subsequence of words $c_{i}\ldots c_{j}$
within the sentence. (2) Any triple $(i,j,p)$ such that ${s_{0}}\leq i\leq
j\leq{s_{1}}$ and $p$ is a preposition, indicating the implicit noun phrase in
the sentence that modifies the phrase $c_{i}\ldots c_{j}$ through the
preposition $p$. (3) Any pair $(\hbox{NULL},p)$ such that $p$ is a
preposition, indicating the implicit noun phrase modifying the entire sentence
$c_{s_{0}}\ldots c_{s_{1}}$ through the preposition $p$.

##  4 QED Annotations for the Natural Questions

We now describe QED annotations over the Natural Questions (NQ) dataset
Kwiatkowski et al. (2019). We first describe the annotation process; then
describe agreement statistics; finally we describe statistics of types of
referential expression.

Question: where did they film and then there were none
Wikipedia page: And_Then_There_Were_None
Passage: Filming began in July 2015. Cornwall was used for many of the harbour
and beach scenes, including Holywell Bay, Kynance Cove, and Mullion Cove.
Harefield House in Hillingdon, outside London, served as the location for the
island mansion. Production designer Sophie Beccher decorated the house in the
style of 1930s designers like Syrie Maugham and Elsie de Wolfe. The below
stairs and kitchen scenes were shot at Wrotham Park in Hertfordshire. Railway
scenes were filmed at the South Devon Railway between Totnes and
Buckfastleigh.

Figure 2: An example outside of QED’s current scope, since multiple passage
sentences contribute an answer.

We focus on questions in the NQ corpus that have both a passage and short
answer marked by the NQ annotator. We exclude examples where the passage is a
table. A QED annotator was presented with a question/paragraph pair. In a
first step they determine whether: (1) there is a valid short answer within
the paragraph (note that they can overrule the original NQ judgment), and
there is a valid QED explanation for that answer; (2) there is a valid short
answer within the paragraph, but there is no valid QED explanation for that
answer. (See Figure 2 for a representative example in this category, in which
multiple sentences are required to justify an answer, thus violating the
single-sentence assumption of QED); (3) there is no valid short answer within
the passage (hence the original NQ annotation is judged to be an error). 10%
of all examples fell into category (3). Of the remaining 90% of examples which
contained a correct short answer, 77% fell into category (1), and 23% fell
into category (2).

Three QED annotators555Three of the authors of this paper. annotated 7638
training examples (5154/1702/782 in categories 1/2/3 respectively), and 1353
dev examples (1019/183/151 in categories 1/2/3).

###  4.1 Agreement Statistics

Each of the three annotators marked a common set of 100 examples drawn from
the development set. Average accuracy of classification of instances was
73.9.%666One annotator was more conservative interpreting the single sentence
assumption. Pairwise accuracy breakdown was thus 81.2/72.3/68.1%. Given the
high number of “debatable” instances reported in the Natural Questions paper,
this divergence is however unsurprising. Average pairwise F1 on mention
identification/mention alignment, conditioned on both annotators labeling
instances as amenable to QED, was 88.4 and 84.1 respectively.

| Referential Link Count
---|---
| 0 | 1 | 2 | 3
Instances | 54 | 649 | 294 | 6
Table 1: Referential link count frequency distribution in a random sample of
1000 instances.

###  4.2 Types of Referential Expressions

Pronominal reference
---
Question: how many blocks in the great pyramid of giza1
Wikipedia page: Great_Pyramid_of_Giza
Passage: Based on these estimates, building the pyramid in 20 years would
involve installing approximately 800 tonnes of stone every day. Additionally,
since  it1 consists of an estimated  2.3 million${}_{\textsc{a}}$ blocks,
completing the building in 20 years would involve moving an average of more
than 12 of the blocks into place each hour, day and night. The first precision
measurements of the pyramid were made by Egyptologist Sir Flinders Petrie in
1880–82 and published as The Pyramids and Temples of Gizeh. Almost all reports
are based on his measurements[…]
Inexact match
Question: where does the term sixes and sevens1 originate
Wikipedia page: At_sixes_and_sevens
Passage: An ancient dispute between the Merchant Taylors and Skinners livery
companies${}_{\textsc{a}}$ is the probable origin of the phrase1 . The two
trade associations, both founded in the same year (1327), argued over sixth
place in the order of precedence. In 1484, after more than a century and a
half of bickering, the Lord Mayor of London Sir Robert Billesden ruled that at
the feast of Corpus Christi, the companies would swap between sixth and
seventh place and feast in each other’s halls[…]
Answer bridging/coref
Question: what is whitney houston’s mother1 ’s name
Wikipedia page: Cissy_Houston
Passage: Emily “Cissy” Houston${}_{\textsc{a}}$ (née Drinkard; born September
30, 1933) is an American soul and gospel singer. After a successful career
singing backup for such artists as Dionne Warwick, Elvis Presley and Aretha
Franklin, Houston embarked on a solo career, winning two Grammy Awards for her
work. Houston is the mother of singer Whitney Houston1 , grandmother of
Whitney’s daughter, Bobbi Kristina Brown, aunt of singers Dionne and Dee Dee
Warwick, and a cousin of opera singer Leontyne Price.
Entity bridging
Question: who sang the national anthem1 at the first game of 2017 world
series2
Wikipedia page: 2017_World_Series
Passage: Game 1: The ceremonial first pitch was thrown out by members of
former Dodger Jackie Robinson’s family, including his widow Rachel. The game
marked the 45th anniversary of Robinson’s death, and the 2017 season was the
70th anniversary of his breaking of the baseball color line. [$\dots$]2 Keith
Williams Jr.${}_{\textsc{a}}$ , a gospel singer, performed  “The Star-Spangled
Banner", the national anthem1 .
Generic reference
Question: what is the function of a paints binder1
Wikipedia page: Paint
Passage: The binder1 is the film-forming${}_{\textsc{a}}$ component of paint.
It is the only component that is always present among all the various types of
formulations. Many binders are too thick to be applied and must be thinned.
The type of thinner, if present, varies with the binder.
Figure 3:  Examples from the QED dataset, grouped according to different types of referential equalities. Question Expression |  Passage Expression
---|---
how i.met your mother |  the CBS television sitcom How I Met Your Mother
the most wins in the nfl |  most wins
mantis |  Mantis
the nashville sound |  Countrypolitan - a smoother sound typified through the use of lush string arrangements with a real orchestra and often, background vocals provided by a choir
a permit driver |  a driver operating with a learner ’s permit
god’s not dead a light in the darkness |  it
the current president of un general assembly |  the United Nations General Assembly President of its 72nd session beginning in September 2017
the new maze runner movie |  Runner : The Death Cure
a box lacrosse team |  a team
Figure 4: Referential equalities from the QED corpus.

Qu. Ps. | P | N | A | G | Pn | B | M | T
---|---|---|---|---|---|---|---|---
Proper | 44 | 0 | 16 | 0 | 9 | 4 | 0 | 73
Def. | 4 | 6 | 4 | 0 | 0 | 1 | 1 | 16
(Non-Ana) |  |  |  |  |  |  |  |
Def. | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 2
(Ana) |  |  |  |  |  |  |  |
Generic | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 6
Pronoun | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Bridge | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
Misc | 2 | 0 | 0 | 0 | 0 | 0 | 1 | 3
Total | 50 | 7 | 21 | 6 | 9 | 5 | 2 | 100

Figure 5: Counts for 100 randomly drawn referential equality annotations from
the QED corpus, subcategorized by expression type in the question (Qu.) and
passage (Ps.). P/N/A/G/Pn/B/M refer to Proper/Def(non-
ana)/Def(ana)/Generic/Pronoun/Bridge/Misc.

The referential equality annotations are a major component of QED. Figure 3
shows some full QED examples from the corpus, and Figure 4 shows some example
equalities from the corpus. In this section, in an effort to gain insight
about the types of phenomena present, we describe statistics on types of
referential equalities. We subcategorize referring expressions into the
following types:777For formal discussion, see Carlson (1977); Krifka (2003);
Abbott (2004); Mikkelsen (2011) among others.

##### Proper Names

Examples are “How I met your Mother” or “the cbs television sitcom how i met
your mother”.

##### Non-Anaphoric Definite NPs

These are expressions such as “the president of the United States” or “the
next Maze Runner film”. The majority involve one or more common nouns (e.g.,
"president", "film") together with a proper name, thereby defining a new
entity that is in some sense a "derivative" of the underlying proper name.

##### Anaphoric Definite NPs

These are definite NPs, most often from within the passage rather than the
question, that require context to be interpreted. Examples are "the series"
referring to an earlier mention of "the Vampire Diaries" within the passage,
or "the winner" referring to "the winner of America’s got Talent Season 11".

##### Generics

Examples are "a dead zone" in the question "what causes a dead zone in the
ocean", or "Dead zones" in the passage sentence "Dead zones are low-oxygen
areas caused by …".

##### Pronouns

Examples are it, they, he, she.

##### Bridging

Referential expressions in the passage sentence that use bridging (see Section
3.3).

##### Miscellaneous

All referential expressions not included in the categories above.

Table 1 shows the frequency distribution of per-instance referential equality
counts. Figure 5 shows an analysis of 100 referential equality annotations
from QED, with a breakdown by type of referring expression in the question and
passage. Proper names, non-anaphoric definites, and generics dominate
expression types in the question (73, 16, and 6 examples respectively).
Expressions in the sentence are more diverse, with a much greater proportion
of anaphoric definites, pronouns, and bridging examples (21, 9, and 5 cases
respectively).

Finally, as an indication of the difficulty of the referential equality task,
we note that in only 12% of all referential equalities in the 100 examples in
Figure 5 is there an exact string match (after lower-casing of both question
and passage) between the question and passage referential expression.

##  5 Tasks and Baseline Results

We release the QED dataset with the intention to spur research into QED-based
tasks and models. In this section, we introduce four potential modeling tasks
using the data and describe baseline approaches and results for the first two
tasks.

###  5.1 Four Tasks

Each QED example is a $(q,d,c,a,e)$ tuple where $q$ is a question from the NQ
corpus, $d$ is a Wikipedia page, $c$ is a long answer (typically a paragraph)
within $d$, $a$ is a short answer within $c$, and $e$ is a QED explanation. We
use ${\cal E}$ to refer to set of evaluation examples (either the development
or test set).

Such data could potentially be used in many different ways. We highlight the
following four tasks, in order of increasing complexity:

##### Task 1

Given a $(q,d,c,a)$ 4-tuple, make a prediction $\hat{e}=f(q,d,c,a)$ where $f$
is a function that maps a $(q,d,c,a)$ tuple to an explanation. We might for
example define $f(q,d,c,a)=\arg\max_{e}p(e|q,d,c,a;\theta)$ under some model
$p(\ldots)$. The evaluation measure is then

$\frac{1}{|{\cal E}|}\sum_{(q,d,c,a,e)\in{\cal E}}l_{1}(e,f(q,d,c,a))$

where $l_{1}(e,\hat{e})$ is a per-example evaluation measure indicating how
close $\hat{e}$ is to $e$.

##### Task 2

Given a $(q,d,c)$ triple, predict $(\hat{a},\hat{e})=f(q,d,c)$, where $f$ is a
function that maps a $(q,d,c)$ pair to a short-answer/explanation triple. We
might for example define $f(q,d,c)=\arg\max_{a,e}p(a,e|q,d,c;\theta)$ under
some model $p(\ldots)$. The evaluation measure is $\sum_{(q,d,c,a,e)\in{\cal
E}}l_{2}((a,e),f(q,d,c))$ where $l_{2}$ is some per-example measure.

##### Task 3

Given a $(q,d)$ pair, predict $(\hat{c},\hat{a},\hat{e})=f(q,d)$, where $f$ is
a function that maps a $(q,d)$ pair to a long-answer/short-answer/explanation
triple. We might for example define
$f(q,d)=\arg\max_{c,a,e}p(c,a,e|q,d;\theta)$ under some model $p(\ldots)$. The
evaluation measure is $\sum_{(q,d,c,a,e)\in{\cal E}}l_{3}((c,a,e),f(q,d))$
where $l_{3}$ is some per-example measure.

##### Task 4

As in Task 3, given a $(q,d)$ pair, predict
$(\hat{c},\hat{a},\hat{e})=f(q,d)$. One part of the evaluation is the same as
in Task 3. But in addition, we require the explanations generated by
$f(\ldots)$ to be faithful with respect to the reasoning process of the
underlying model. This will require an evaluation measure for faithfulness,
which is an open question beyond the scope of this paper.

Accurate models for Tasks 1, 2, and 3 even if they do not generate faithful
explanations (Task 4), may still have considerable utility. However, faithful
models have several desirable characteristics (see Section 7); we view them as
a major avenue for future work.

In the remainder of this section we describe results for baseline models on
Tasks 1 and 2. The intention here is to establish baseline results as a
reference point for future work on QED models and to get an idea of
tractability of recovery of QED annotations.

###  5.2 A Baseline Model for Task 1

Our baseline model for Task 1 is an extension of the recently proposed
coreference resolution model of Joshi et al. (2019) and Lee et al. (2017). We
present two variations on the model, the first trained on coreference data
alone, the second trained on coreference data with fine-tuning on QED
annotations

####  5.2.1 The Coreference Resolution Model

We give a brief recap of the approach of Joshi et al. (2019) and Lee et al.
(2017). Given some document $d$ and a candidate mention $x$, corresponding to
a span within $d$, define ${\cal Y}(x)$ to be the set of potential antecedents
for $x$. Each antecedent is either a span in the document with start-point
before $x$ in the document, or $\epsilon$ signifying that $x$ does not have an
antecedent. We can then define a distribution over the antecedent spans ${\cal
Y}(x)$ as $p(y|x,D)=\frac{e^{s(x,y)}}{\sum_{y^{\prime}\in{\cal
Y}(x)}e^{s(x,y^{\prime})}}$ where

$\displaystyle s(x,y)$ $\displaystyle=\left\\{\begin{array}[]{ll}0&\mbox{ if
$y=\epsilon$};\\\ s_{m}(x)+s_{m}(y)+s_{c}(x,y)&\mbox{o.t.}\end{array}\right.$
$\displaystyle s_{m}(x)$ $\displaystyle=\texttt{FFNN}_{m}({g_{x}})$
$\displaystyle s_{c}(x,y)$ $\displaystyle=\texttt{FFNN}_{c}({g_{x}},{g_{y}})$

where $g_{x}$ and $g_{y}$ are span representations obtained by concatenating
the SpanBERT representation of the first and last token in each mention span.
The scoring functions $s_{m}$ and $s_{c}$ represent mention and joint span
match scores respectively.

Lee et al. (2017) describe a method for training the model based on log-
likelihood, and a beam search method that uses the scores $s_{m}(\ldots)$ to
filter mentions and antecedents. The final output from the model is a hard
clustering of the potential mentions into coreference clusters.

####  5.2.2 The Model Applied to Task 1

Assume an example contains a question $q$ of $m$ tokens $q_{1}\ldots q_{m}$
and a passage $c$ consisting of $n$ tokens $c_{1}\ldots c_{n}$. We denote the
title of the Wikipedia page separately as the sequence $t$ of $k$ tokens
$t_{1}\ldots t_{k}$. The model considers the concatenation of these token
sequences,

${\small\texttt{[CLS]}t_{1}\ldots t_{k}\texttt{[S1]}q_{1}\ldots
q_{m}\texttt{[S2]}c_{1}\ldots c_{n}\texttt{[SEP]},}$

as an input document.888We simply use [S1] = ”.” and [S2] = ”?” as separators.
The model is tasked with predicting the referential equality annotations
$e=e_{1}\ldots e_{k}$ in the QED annotation. We do assume that the NQ short
answer is also an input to the model, used to restrict the position of
referential equality annotations in the passage; we describe this restriction
below.

QED referential equality annotations are of two types: (1) coreferential links
between noun phrases in the question and in the passage, and (2) coreferential
links between a noun phrase in the question and an implicit argument in the
passage. We observe that many implicit arguments link to the title of the
passage, so we model the latter annotation type as a coreferential link
between the question mention and the title span $t_{1}\ldots t_{k}$. In the
untrained baseline, we restrict $s_{m}$ to only score mentions in the sentence
containing the answer. In both models we restrict $s_{c}$ to only score
coreferential links between the query and the passage or between the query and
the title (all other values for $s_{m}$ or $s_{c}$ are set to $-\infty$).

We finally post-process the cluster outputs as follows: for each cluster we
output the first cluster mention in the question paired with the first cluster
mention in the passages. If there is no cluster mention in the passage, then
we output the question mention paired with an implicit argument.

For the untrained baseline, we did not use expert annotated QED data but
instead used the CoNLL OntoNotes coreference dataset Pradhan et al. (2012) to
train the pretrained SpanBERT model. For the fine-tuned baseline, we further
trained the model with the training portion of QED data converted into
coreference format. We used SpanBERT “large”, with a maximum span width of 16
tokens, a top span ratio of 0.2, 30 max antecedents per mention. In fine-
tuning, we used an initial learning rate of $3\cdot 10^{-4}$ and trained for 3
epochs on the QED training set.

| Mention | Mention
---|---|---
| Identification | Alignment
| P | R | F1 | P | R | F1
zero-shot | 59.0 | 35.6 | 44.4 | 47.7 | 28.8 | 35.9
fine-tuned | 76.8 | 68.8 | 72.6 | 68.4 | 61.3 | 64.6

Table 2: SpanBERT model performance for Task 1: recovering QED annotations
when the correct answer is given.

We evaluate both mention identification (the identification of individual
referential expressions in the question and passage) and referential equality
detection (the identification of pairs of referential expressions). We compute
precision, recall, and F1 measure in both cases. Evaluation results are
reported in Table 2. The table shows results for both the zero-shot model,
trained on coreference data alone, and a fine-tuned model, which is fine-tuned
on QED annotations.999Official evaluation code will be released with the
dataset.

###  5.3 A Baseline Model for Task 2

Our baseline model for Task 2 is a straightforward extension of the baseline
model for Task 1. We build a model of the form

$\displaystyle p(a,e|q,d,c;\theta)$ $\displaystyle=$ $\displaystyle
p^{(1)}(a|q,d,c;\theta^{(1)})p^{(2)}(e|a,q,d,c;\theta^{(2)})$

where $p^{(1)}$ is an existing QA model (similar to Alberti et al. (2019)),
and $p^{(2)}$ is the baseline model for Task 1. Thus we simply compose an
existing question-answering model with an answer agnostic model that recovers
explanations.

The answer scoring component of the model computes answer candidate
representations $g_{z}$ in the same way as the Task 1 baseline computes
mention representations. The score of an answer $z$ is then computed as

$\displaystyle s_{a}(z)$ $\displaystyle=\texttt{FFNN}_{a}({g_{z}}).$

Mention representations are shared between $p^{(1)}$ and $p^{(2)}$, so the
only new parameters belong to a single hidden layer feed-forward net
$\texttt{FFNN}_{a}$ that computes the answer score for each mention. No
further dependence is introduced between the answer and explanation
predictions. We train $p^{(1)}$ and $p^{(2)}$ in a multitask fashion, by
minimizig the weighted sum of the question answering and coreference cross
entropy losses. Our best results are obtained with a weight of 5 on the
coreference loss and 2 epochs of training. The best answer accuracy and QED F1
are obtained for different base learning rates of $2\cdot 10^{-5}$ and $5\cdot
10^{-5}$ respectively.

####  5.3.1 Results

| Mention | Mention | Answer
---|---|---|---
| Identification | Alignment | Accuracy
| P | R | F1 | P | R | F1 |
QED-only | 74.1 | 63.8 | 68.6 | 63.6 | 54.9 | 58.9 | -
QA-only | - | - | - | - | - | - | 73.4
QA+QED | 77.5 | 64.6 | 70.5 | 68.6 | 57.3 | 62.4 | 74.5

Table 3: SpanBERT model performance for Task 2: recovering answer and QED
annotations given a passage that is known to contain the answer.

In Table 3 we report results for Task 2 for three separate variations of the
approach described in the previous section. QED-only fine-tunes $p^{(2)}$ on
the QED training set only. QA-only fine-tunes $p^{(1)}$ on all the paragraphs
of the NQ dataset that contain a short answer. QA+QED fine-tunes both
$p^{(1)}$ and $p^{(2)}$ on all NQ and QED data. We obtain the encouraging
result that both QA and QED metrics improve significantly in the final
multitask setting, despite the fact that the QED training data (5154 examples)
amounts to only 6% of the data available for QA (91632 examples).

##  6 Rater Study

A system which makes use of QED explanations to answer a question is one which
decomposes its reasoning process into human-interpretable chunks. We
hypothesize that exposing QED explanations should improve a user’s ability to
spot errors made by an automated QA system. To this end, we evaluate QED
explanations using a rater study.

###  6.1 Task Setup

Given a question, passage, and a candidate answer span, raters were tasked
with assessing whether the candidate answer was correct or incorrect, and
indicating the confidence of their assessment.

We obtained the data for the study by taking a random set of 50 correct
answers and 50 incorrect guesses from the NQ baseline model on the Natural
Questions dev set. So as to ensure that the task was sufficiently challenging,
correct instances were the _gold_ answer spans on question/passage pairs where
the model produced a false negative.101010That is, where an answer existed in
the passage, but the model was not confident about it. Incorrect instances
were false positive guesses from the model.

A total of 354 raters, all of whom are US-residents and native English
speakers, were divided into three disjoint pools to perform the task in three
distinct test settings: The None group of raters (n=121) was presented with a
question, passage, and a highlighted answer span. The Sentence group (n=117)
was provided with additional highlighting of the sentence containing the
answer, with no distinction made between referential equalities and
predicates. The QED group (n=116) was provided with additional highlighting to
indicate referential equalities between spans in the question and spans in the
passage. On average, a given rater provided judgments for 41 questions.

In each case, raters were told that highlighting was the output of “an
automated question answering system” that was incorrect “about half of the
time.” Where explanations were present, they were manually imputed to simulate
the inferences of a hypothetical model that used a QED-style reasoning
process. Additionally, raters were told that the system made use of the
highlighted information to produce its candidate answers.

###  6.2 Results

| Accuracy | F1
---|---|---
| All | Corr | Incorr/Pred/Ref | Incorr
None | 67.5 | 90.4 | 44.3/43.9/44.7 | 57.6
Sentence | 69.7 | 92.4 | 47.1/46.1/48.0 | 60.9
QED | 70.2 | 90.6 |  49.7/48.2/51.0 | 62.5
Table 4: Rater study results. Corr and Incorr are accuracies of raters in each
group on correct and incorrect instances respectively, with incorrect
instances further broken into Pred(icate) and Ref(erence) model errors. F1 is
on the task of identifying incorrect instances. Figure 6: Sorted, per-question
evaluation accuracies from different rater study settings, with 95% binomial
confidence intervals. Left three plots correspond to trials with incorrect
answers highlighted; right three plots to trials with correct answers
highlighted. Dashed red lines correspond to the average accuracy for each
setting, identical to the numbers in Table 4.

Average rater accuracies for each test setting are presented in Table 4. We
see that, in aggregate, QED explanations improved accuracy on the task over
and above the other test settings, and gave the most improvement on the
identification of answers that were incorrect. These improvements translate to
incorrect answers resulting from both predicate and reference model errors.

Somewhat surprisingly, highlighting just the sentence containing the answer
improved accuracy more than including referential equality highlighting on
instances that were correct. This is likely because raters’ propensity to mark
instances correct decreases as the complexity of explanations increases, from
None (73.1%) to Sentence (72.6%) to QED (70.5%).

Also clear from Table 4 is that rater accuracy is much lower on incorrect
instances. Even though raters were told that the answers presented were
incorrect half of the time, they marked the model guess as correct roughly 71%
of the time.111111While this confirmation bias presents an interesting
challenge for future work, it is not a shortcoming of our results: Raters were
not trained to do well on the task, as we aimed to approximate how users
interact with automated QA systems.

Figure 6 provides another perspective on the disparity in judgments on
correct/incorrect instances summarized in Table 4. The instances receiving the
highest accuracy in the incorrect pool are harder for raters on average than
most of the correct instances, and the lowest accuracy on incorrect instances
is far lower than that of any of the correct instances. The wide distribution
of accuracies on incorrect instances ($\sigma$$\approx$0.50) seen in Figure 6
was also reflected in the rater pool ($\sigma$$\approx$0.45). The challenging
nature of incorrect instances speaks to the promise of improvements from QED
explanations.

###  6.3 Effectiveness of explanations

How statistically significant are the results reported in Table 4? The 14,115
test instances were spread across 354 raters and 100 questions. To control for
the correlations induced by the rater and question groups, we fit a
generalized linear mixed model (GLMM) using the rstanarm R package Goodrich et
al. (2020). We used the formula $\texttt{a}\,\mathtt{\sim}\,\texttt{c * e +
(1|r) + (1|q)},$ where a is whether or not the rater accurately marked the
instance; c is whether the instance was Correct or Incorrect; e is the
explanation test setting of None, Sentence, or QED; r is the rater id; and q
is the question id. This formula specifies a regression of the log-odds of the
rater accuracy on the fixed effects of instance correctness (c) and
explanation setting (e), while allowing for random effects in the raters (r)
and questions (q). Ultimately we are interested in the magnitude and
statistical properties of e under the various test settings.

Parameter | Coefficient (SD)
---|---
(Intercept) | -0.31 (0.15)
\+ Incorrect+Sentence | 0.15 (0.11)
\+ Incorrect+QED | 0.25 (0.11)
\+ Correct+None | 2.94 (0.21)
\+ Correct+Sentence | 3.04 (0.13)
\+ Correct+QED | 2.69 (0.13)
Table 5: Generalized linear mixed model fixed effect coefficients, showing
mean and standard deviation of 10k MCMC samples. The Intercept corresponds to
the Incorrect+None setting.

Table 5 shows the fixed effect coefficient and standard deviations for each
setting. The presence of QED explanations in the Incorrect setting increased
the log-odds of rater accuracy by 0.25, with a posterior predictive p-value of
0.015 that this effect is greater than zero. The comparable effect for
Sentence explanations was 0.15, with a posterior predictive p-value of 0.08.
The rater and question random effects had standard deviations of 0.63 and 0.90
respectively, reflecting again the high variance of questions shown in Figure
6.

As we saw earlier, the effects of explanations in the Correct setting was
reversed: the Sentence explanations caused a small, statistically
insignificant increase in log-odds, while QED explanations caused a
statistically significant drop in log-odds.

##  7 Discussion

###  7.1 QED and strong explainability

It is an open question as to what constitutes a good explanation Lipton
(2001). A major inflection point in the discussion is the notion of
faithfulness Ross et al. (2017); Lipton (2016). We say a model’s explanations
are faithful when there is a causal relationship between an explanation and a
prediction. That is, when an explanation changes, the outputs change
accordingly. When this is not true, we say a model generates rationales, which
have the appearance of justifying its outputs, but without causal guarantees
Ehsan et al. (2018).

While the models described in Section 5 fall into the latter category, we
believe QED is a promising framework for strongly explainable QA. This is due
in large part to its commitment to the cognitive reality of reference and
entailment. We can say, definitively, that in order for a sentence to answer a
question about a thing, its meaning must involve that thing in a very
particular sense. Posed counterfactually, when you break referential equality,
you break answerhood, and the same argument follows for predicate entailment.
Unlike other intelligent behavior that may permit of post-hoc rationalization
at best Ehsan et al. (2019), certain forms of high-level linguistic reasoning
are in fact amenable to strong explanation.

###  7.2 Potential Extensions to the QED Framework

QED exists in between relatively unstructured explanation forms on the one
hand, such as attention distributions Wiegreffe and Pinter (2019); Jain and
Wallace (2019); Mohankumar et al. (2020) or sequential outputs Camburu et al.
(2018, 2019); Narang et al. (2020); Kumar and Talukdar (2020) and more
elaborate, discrete semantic representations that can in theory be applied to
explainable QA Abzianidze et al. (2017); Wolfson et al. (2020).

The version of QED presented here is a broad coverage, yet limited
instantiation of a framework, in which explanations are semantic relations
whose substructures are defined in terms of formally motivated linguistic
categories. However, in keeping with its modularity, we can extend QED to
account for these by looking to semantic relations beyond referential equality
and predicate entailment, such as set-membership noun phrase Hearst (1992) and
interclausal Miltsakaki et al. (2004); Lamm et al. (2018); Tandon et al.
(2019) relations.

###  7.3 Future uses of QED representations

Our hope is that QED representations may be useful in a variety of extensions
to extant QA systems. Some examples are as follows:

##### Ambiguous Questions.

Consider again the question in Figure 1, "who wrote the film howl’s moving
castle". Now consider the question "who wrote howl’s moving castle". In this
case there are two possible answers, depending on whether the author of the
question is referring to the film or novel. It would be natural for a system
to provide two possible answers (see, e.g. Min et al., 2020), with two
possible QED explanations highlighting the differing assumptions underlying
each answer. Such referential ambiguities are common, and the centrality of
referential equality in QED annotations should mean that they are useful in
this scenario.

##### Complex Referential Equalities.

Consider the question "meaning of whiskey in the jar by metallica". The
Wikipedia page for "Whiskey in the Jar" says the following:

Passage: "Whiskey in the Jar" is an Irish traditional song set in the southern
mountains of Ireland. The song, about a rapparee (highwayman) who is betrayed
by his wife or lover, is one of the most widely performed traditional Irish
songs and has been recorded by numerous artists since the 1950s.

A good answer could be that the song is "about a rapparee $\ldots$ who is
betrayed by his wife or lover", assuming that the Metallica song is a variant
of the Irish traditional song. Thus the validity of this answer hinges on a
complex referential equality, between the Metallica version and the original.
Examples that require this type of complex referential reasoning are quite
common, and the centrality of reference in QED should be relevant.

##  8 Conclusions

We have described QED, a framework for explanations in question answering, and
we have introduced a corpus of QED annotations. The framework is grounded in
referential equality, and entailment. In addition we have described baseline
models for two QED-based tasks, and a rater study utilizing QED annotations.

Future work should consider the development of models that provide faithful
explanations based on QED; extensions of QED, for example to handle multi-
sentence inference or referential phenomena going beyond equality; and
applications of QED, for example to sentences with multiple potential answers,
to questions that are vague or underspecified, or to referential equalities
that require significant inference to be justified.

## References

  * Abbott (2004) Barbara Abbott. 2004.  Definiteness and indefiniteness.  _The handbook of pragmatics_ , 122.
  * Abzianidze et al. (2017) Lasha Abzianidze, Johannes Bjerva, Kilian Evang, Hessel Haagsma, Rik Van Noord, Pierre Ludmann, Duc-Duy Nguyen, and Johan Bos. 2017.  The parallel meaning bank: Towards a multilingual corpus of translations annotated with compositional meaning representations.  _arXiv preprint arXiv:1702.03964_.
  * Alberti et al. (2019) Chris Alberti, Kenton Lee, and Michael Collins. 2019.  A bert baseline for the natural questions.  _arXiv preprint arXiv:1901.08634_.
  * Camburu et al. (2018) Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom. 2018\.  e-snli: Natural language inference with natural language explanations.  In _Advances in Neural Information Processing Systems_ , pages 9539–9549.
  * Camburu et al. (2019) Oana-Maria Camburu, Brendan Shillingford, Pasquale Minervini, Thomas Lukasiewicz, and Phil Blunsom. 2019.  Make up your mind! adversarial generation of inconsistent natural language explanations.
  * Carlson (1977) Greg N Carlson. 1977.  A unified analysis of the english bare plural.  _Linguistics and philosophy_ , 1(3):413–457.
  * Clark et al. (2019) Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. 2019.  Boolq: Exploring the surprising difficulty of natural yes/no questions.  _arXiv preprint arXiv:1905.10044_.
  * Clark (1975) Herbert H Clark. 1975.  Bridging.  In _Theoretical issues in natural language processing_.
  * Clark and Marshall (1981) Herbert H Clark and Catherine R Marshall. 1981.  Definite knowledge and mutual knowledge.  _Elements of Discourse Understanding_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _ArXiv_ , abs/1810.04805.
  * Doshi-Velez and Kim (2017) Finale Doshi-Velez and Been Kim. 2017.  Towards a rigorous science of interpretable machine learning.  _arXiv preprint arXiv:1702.08608_.
  * Ehsan et al. (2018) Upol Ehsan, Brent Harrison, Larry Chan, and Mark O Riedl. 2018.  Rationalization: A neural machine translation approach to generating natural language explanations.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 81–87.
  * Ehsan et al. (2019) Upol Ehsan, Pradyumna Tambwekar, Larry Chan, Brent Harrison, and Mark O Riedl. 2019\.  Automated rationale generation: a technique for explainable ai and its effects on human perceptions.  In _Proceedings of the 24th International Conference on Intelligent User Interfaces_ , pages 263–274. ACM.
  * Goodrich et al. (2020) Ben Goodrich, Jonah Gabry, Imad Ali, and Sam Brilleman. 2020.  rstanarm: Bayesian applied regression modeling via Stan. R package version 2.19.3.
  * Hearst (1992) Marti A Hearst. 1992.  Automatic acquisition of hyponyms from large text corpora.  In _Proceedings of the 14th conference on Computational linguistics-Volume 2_ , pages 539–545. Association for Computational Linguistics.
  * Jacovi and Goldberg (2020) Alon Jacovi and Yoav Goldberg. 2020.  Towards faithfully interpretable nlp systems: How should we define and evaluate faithfulness?  _arXiv preprint arXiv:2004.03685_.
  * Jain and Wallace (2019) Sarthak Jain and Byron C Wallace. 2019.  Attention is not explanation.  _arXiv preprint arXiv:1902.10186_.
  * Joshi et al. (2019) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. 2019.  Spanbert: Improving pre-training by representing and predicting spans.  _Transactions of the Association for Computational Linguistics_ , 8:64–77.
  * Krifka (2003) Manfred Krifka. 2003.  Bare nps: kind-referring, indefinites, both, or neither?  In _Semantics and linguistic theory_ , volume 13, pages 180–203.
  * Kumar and Talukdar (2020) Sawan Kumar and Partha Talukdar. 2020.  Nile : Natural language inference with faithful natural language explanations.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming-Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019.  Natural questions: a benchmark for question answering research.  _Transactions of the Association of Computational Linguistics_.
  * Lamm et al. (2018) Matthew Lamm, Arun Tejasvi Chaganty, Christopher D Manning, Dan Jurafsky, and Percy Liang. 2018.  Textual analogy parsing: Identifying what’s shared and what’s compared among analogous facts.  _EMNLP_.
  * Lee et al. (2017) Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017.  End-to-end neural coreference resolution.  In _EMNLP_.
  * Lipton (2001) Peter Lipton. 2001.  What good is an explanation?  In _Explanation_ , pages 43–59. Springer.
  * Lipton (2016) Zachary C Lipton. 2016.  The mythos of model interpretability.  _arXiv preprint arXiv:1606.03490_.
  * Mikkelsen (2011) Line Mikkelsen. 2011.  Copular clauses.  In Claudia Maienborn, Klaus von Heusinger, and Paul Portner, editors, _Semantics: An International Handbook of Natural Language Meaning_ , volume 2, pages 1805–1829. Mouton De Gruyter, Berlin.
  * Miltsakaki et al. (2004) Eleni Miltsakaki, Rashmi Prasad, Aravind K Joshi, and Bonnie L Webber. 2004.  The penn discourse treebank.  In _LREC_.
  * Min et al. (2020) Sewon Min, Julian Michael, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2020.  Ambigqa: Answering ambiguous open-domain questions.
  * Mohankumar et al. (2020) Akash Kumar Mohankumar, Preksha Nema, Sharan Narasimhan, Mitesh M. Khapra, Balaji Vasan Srinivasan, and Balaraman Ravindran. 2020.  Towards transparent and explainable attention models.
  * Narang et al. (2020) Sharan Narang, Colin Raffel, Katherine Lee, Adam Roberts, Noah Fiedel, and Karishma Malkan. 2020.  Wt5?! training text-to-text models to explain their predictions.
  * Pradhan et al. (2012) Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012.  Conll-2012 shared task: Modeling multilingual unrestricted coreference in ontonotes.  In _EMNLP-CoNLL Shared Task_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_.
  * Reddy et al. (2019) Siva Reddy, Danqi Chen, and Christopher D. Manning. 2019.  Coqa: A conversational question answering challenge.  _Transactions of the Association for Computational Linguistics_ , 7:249–266.
  * Ross et al. (2017) Andrew Slavin Ross, Michael C Hughes, and Finale Doshi-Velez. 2017.  Right for the right reasons: Training differentiable models by constraining their explanations.  _arXiv preprint arXiv:1703.03717_.
  * Russell (1905) Bertrand Russell. 1905.  On denoting.  _Mind_ , 14(56):479–493.
  * Tandon et al. (2019) Niket Tandon, Bhavana Dalvi, Keisuke Sakaguchi, Peter Clark, and Antoine Bosselut. 2019.  Wiqa: A dataset for “what if…” reasoning over procedural text.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6078–6087.
  * Tomasello et al. (2007) Michael Tomasello, Malinda Carpenter, and Ulf Liszkowski. 2007.  A new look at infant pointing.  _Child development_ , 78(3):705–722.
  * Wiegreffe and Pinter (2019) Sarah Wiegreffe and Yuval Pinter. 2019.  Attention is not not explanation.  _arXiv preprint arXiv:1908.04626_.
  * Wolfson et al. (2020) Tomer Wolfson, Mor Geva, Ankit Gupta, Matt Gardner, Yoav Goldberg, Daniel Deutch, and Jonathan Berant. 2020.  Break it down: A question understanding benchmark.  _Transactions of the Association for Computational Linguistics_ , 8:183–198.