# Understanding of a brain spatial map
based on threshold-free function dendrogramization

Hyekyoung Lee∗
Seoul National University Hospital
Seoul National University
Seoul 03080 Republic of Korea
<EMAIL_ADDRESS>
&Hyejin Kang
Seoul National University Hospital
Seoul National University
Seoul 03080 Republic of Korea
<EMAIL_ADDRESS>
&Youngmin Huh
Seoul National University
Seoul 03080 Republic of Korea
<EMAIL_ADDRESS>
&Hongyoon Choi
Seoul National University Hospital
Seoul National University
Seoul 03080 Republic of Korea
<EMAIL_ADDRESS>
&Dong Soo Lee
Seoul National University Hospital
Seoul National University
Seoul 03080 Republic of Korea
<EMAIL_ADDRESS>
&for the Alzheimer’s Disease Neuroimaging Initiative
Hyekyoung Lee and Dong Soo Lee are corresponding authors. Data used in
preparation of this article were obtained from the Alzheimer’s Disease
Neuroimaging Initiative (ADNI) database (adni.loni.usc.edu). As such, the
investigators within the ADNI contributed to the design and implementation of
ADNI and/or provided data but did not participate in analysis or writing of
this report. A complete listing of ADNI investigators can be found at:
http://adni.loni.usc.edu/wp-
content/uploads/how_to_apply/ADNI_Acknowledgement_List.pdf

###### Abstract

Linear matrix factorizations (LMFs) such as independent component analysis
(ICA), principal component analysis (PCA), and their extensions, have been
widely used for finding relevant spatial maps in brain imaging data. The last
step of an LMF before interpretation is usually to extract the activated brain
regions from the map by thresholding. However, it is difficult to determine an
appropriate threshold level. Thresholding can remove the underlying properties
of spatial maps and their features imposed by the model. In this study, we
propose a threshold-free activated region extraction method which involves
simplifying a brain spatial map to a dendrogram through Morse filtration.
Since a dendrogram is related to the change of clustering structure in Rips
filtration, we first show the relationship between the Rips filtration of a
graph and the Morse filtration of a function. Then, we dendrogramize a spatial
map in order to visualize the activated brain regions and the range of their
importance in a spatial map. The proposed method can be applied to any spatial
maps that a user wants to threshold and interpret. In experiments, we applied
the proposed method to independent component maps (ICMs) obtained from
resting-state fMRI data, and the dominant subnetworks obtained by the PCA of a
correlation-based functional connectivity of FDG PET Alzheimer’s disease
neuroimaging initiative (ADNI) data. We found that dendrogramization can help
to understand a brain spatial map without thresholding.

_Keywords_ Brain spatial map $\cdot$ Dendrogram $\cdot$ Independent component
analysis $\cdot$ Morse filtration $\cdot$ Principal component analysis $\cdot$
Thresholding

Linear matrix factorization (LMF) models such as principal component analysis
(PCA) and independent component analysis (ICA) have been widely used in brain
imaging data analysis (Beckmann et al., 2009; Bijsterbosch et al., 2017;
Correa et al., 2010). An LMF model simply factorizes a brain imaging data
matrix into spatial map and feature matrices, in which features usually
indicate the relationship between a spatial map and a given task, and the
spatial map shows which brain regions are related to the given task. The LMF
model works in a purely data-driven way. However, it can impose a specific
property such as correlation, independence, or sparsity onto spatial maps. A
spatial map obtained using LMF can also be considered as a subnetwork in which
activated brain regions in the map are strongly connected. ICA is a well-known
method with which to extract subnetworks as an independent source forming
resting state functional connectivity (Calhoun and Adalı, 2012). Although LMF
models do not have a high-level of performance, like deep learning, due to
their simplicity and scalability, they have been developed for use in various
research fields of neuroscience for discovering new data, such as a new
imaging biomarker (Beckmann et al., 2009; Marchitelli et al., 2018; de
Cheveigné et al., 2019; Mohammadi-Nejad et al., 2017; Toussaint et al., 2012;
Woo et al., 2017).

Figure 1: (a) A spatial map (Morse function) on a one-dimensional manifold
with 25 points (nodes), $v_{1},v_{2},\dots,v_{25}$ from left to right. The
goal of this study was to extract clusters or activated regions in the map.
(b) Dendrogramization of a spatial map. Dendrogramization is performed by
observing the change of clustering structure during filtration in (e). The
leaf bars, $c_{2},c_{3},c_{1}$ and $c_{5}$ become the activated regions of the
Morse function. (c) Dendrogram smoothing. The more detailed procedure is in
Fig. 2. $c_{2}$ and $c_{3}$ are replaced by $c_{4}.$ (d) Subnetwork
construction. The spatial map is represented by a network in which nodes are
activated regions and edges are determined by the peak value of the activated
regions. (e) Filtration and the change of clustering structure at thresholds,
$0.75,0.7,\dots,0.$ (f) Edge weight matrix with self-similarity of the Morse
function in (a). The Morse filtration of (a) can be thought as the Rips-like
filtration of (f). (g) Barcode of CCs.

A common procedure in most of the studies on LMF models is to threshold a
spatial map for visualization and interpretation. While a general linear model
(GLM) can estimate the voxel- or cluster-level statistical values of spatial
maps based on the hypothesis of a design matrix, LMF cannot be used to
directly estimate the significance value in a map (Nichols, 2012; Smith and
Nichols, 2009). In the early years, statistical inference in ICA was done by
transforming an independent component map (ICM) to a Z-map, under the
assumption that an ICM is normally distributed (Mckeown et al., 1998).
However, since this assumption was not consistent with ICA, Beckmann, et. al.
proposed a new method based on the Gaussianity of residual errors, instead of
that of an ICM (Beckmann and Smith, 2004). They implemented the proposed
method by approximating the histogram of the Z-map of an ICM with a mixture
model in which one of mixtures is considered as background noise, and the
others are considered as the probabilities of activated brain regions
(Beckmann and Smith, 2004). Recently, Poppe, et. al. proposed a method to vary
thresholds from 0 to 1 after normalizing the maximum value of a spatial map to
1, and choosing a threshold that produced desired results (Poppe et al., 2013;
Ma and MacDonald, 2021). However, we need to ask a fundamental question: “is
it possible to threshold a spatial map extracted using an LMF model?" GLM
inference measures how well a spatial map fits into a predetermined
experimental design, and it is possible to select the parts of a spatial map,
called activated regions. However, LMF is a data-driven method that estimates
spatial maps and corresponding features simultaneously. If the parts of a
spatial map obtained by LMF are selected by thresholding, the corresponding
feature vector should be changed, and eventually, they become not a solution
of a given data matrix.

In this paper, we propose a new threshold-free method for the detection of
activated brain regions in a spatial map based on Morse filtration. We express
the change of the clustering structure of a spatial map during Morse
filtration as a tree structure, called a dendrogram (Carlsson and Mémoli,
2010). We call this procedure dendrogramization (Fig. 1). A dendrogram usually
represents the hierarchical clustering structure of a graph in a metric space.
To verify the dendrogramization procedure, we show that the Morse filtration
of a spatial map on a manifold is related to Rips filtration, if self-distance
is allowed (Edelsbrunner and Harer, 2009; Carlsson and Mémoli, 2010). Then, we
define the leaves of the dendrogram of a spatial map as the activated brain
regions of a spatial map. Therefore, by dendrogramizing a spatial map, we can
see not only the activated brain regions of a spatial map, but also their
duration in the map. To further simplify a dendrogram by reducing the number
of leaves, we also propose a dendrogram smoothing method motivated by
persistent homology (Edelsbrunner and Harer, 2009; Carlsson and Mémoli, 2010).
The higher the peak value of the mode is in a spatial map, the more
significant the activated brain region corresponding to the mode is in a
spatial map.

We transform a spatial map to a subnetwork in which nodes are activated brain
regions and edges are determined by the peak values of the regions. The
proposed method can be applied to any spatial map using an LMF model. We
applied the proposed method to ICMs obtained from resting-state functional
connectivity, and dominant spatial maps in a correlation-based functional
connectivity obtained by the PCA of FDG PET Alzheimer’s disease neuroimaging
initiative (ADNI) data. Dendrogramization helped to understand the spatial
maps by visualizing activated brain regions and the range of their importance
in the map, without thresholding.

##  1 Proposed methods

###  1.1 Morse filtration

Suppose that a spatial map $\mbox{\boldmath$s$}\in\mathbb{R}^{p\times 1}$ is
given. This map is a Morse function on a brain manifold, denoted by
$s(\mbox{\boldmath$v$}),$ where $v$ is a voxel in a three-dimensional brain
imaging space (Adler et al., 2010). If a three-dimensional brain imaging space
is assumed to be a grid coordinate with
$v^{\cdot}\in\left\\{1,\cdots,d_{\cdot}\right\\}$ $(\cdot=1,2,3),$ an upper
level set at a nonnegative threshold, $\epsilon_{t}$ is defined by:

$L_{t}(\mbox{\boldmath$s$})=\left\\{\mbox{\boldmath$v$}|\mbox{\boldmath$s$}(\mbox{\boldmath$v$})\geq\epsilon_{t},\mbox{\boldmath$v$}=(v^{1},v^{2},v^{3})\in\mathbb{N}^{d_{1}\times
d_{2}\times d_{3}}\right\\}.$

We define connected components (CCs, or clusters) in $L_{t}$ by the subset of
voxels of which the faces, edges, or corners are touched each other in a
three-dimensional space. The number of adjacent voxels of each voxel is 26.
The number of CCs in $L_{t}(\mbox{\boldmath$s$})$ is denoted by $\beta_{t},$
which is called the zeroth Betti number. The list of CCs in
$L_{t}(\mbox{\boldmath$s$})$ are denoted by
$c_{1}^{t},\dots,c_{\beta_{t}}^{t}\subseteq L_{t},$ which satisfies that
$L_{t}(\mbox{\boldmath$s$})=c_{1}^{t}\cup\dots\cup c_{\beta_{t}}^{t}$ and
$c_{i}^{t}\cap c_{j}^{t}=\emptyset$ for any
$i,j\in\left\\{1,\cdots,\beta_{t}\right\\}.$ Given the sequence of thresholds,
$\epsilon_{1}\geq\epsilon_{2}\geq\cdots\geq\epsilon_{T}\geq 0,$ the sequence
of level sets satisfies the nested property such that
$L_{1}(\mbox{\boldmath$s$})\subseteq
L_{2}(\mbox{\boldmath$s$})\subseteq\dots\subseteq L_{T}(\mbox{\boldmath$s$}).$
The nested sequence of upper level sets is called Morse filtration (Adler et
al., 2010; Edelsbrunner and Harer, 2009). A CC that lasts from $\epsilon_{t}$
to $\epsilon_{t+\tau-1}$ such that $c^{t}\subseteq
c^{t+1}\subseteq\cdots\subseteq c^{t+\tau-1}$ is called persistent CC (PCC).
The thresholds $\epsilon_{t}$ and $\epsilon_{t+\tau-1}$ are called the birth
and death thresholds of the PCC, respectively. Their difference,
$\tau=\epsilon_{t+\tau-1}-\epsilon_{t}$ is defined as the duration of the PCC.

Figure 2: Dendrogram smoothing of Fig. 1 (b) in Example 2.

###  1.2 Hierarchical clustering structure in a Morse function

During Morse filtration, new voxels are added at every threshold. The new
voxels originally become a new PCC. Some of them merge with other adjacent
PCCs and disappeared without a trace, becoming a new PCC. For convenience, we
omit the process of becoming PCCs in this case, and simply divide the change
of current clustering structure by the new voxels into three cases as follows:

  1. (1)

creating a new CC, if some of them are isolated,

  2. (2)

being connected into the existing CC, if some of them are adjacent to the
existing CC, and

  3. (3)

merging more than two existing CCs into a new CC, if some of the new voxels
are adjacent with the existing CCs.

The clustering structure is changed by cases (1) and (3). In case (2), only
the size of the existing PCC, which is the number of voxels in the PCC, is
expanded, but there is no change in the clustering structure. Case (1) creates
a new PCC. In case (3), the change of PCC structure is slightly different
between traditional persistent homology and hierarchical clustering
dendrograms. For example, suppose that two PCCs, $c_{i}$ and $c_{j},$ are
merged into $c_{k}$ at $\epsilon_{t}.$ In traditional persistent homology, if
$c_{i}$ appears earlier than $c_{j}$ during the filtration, $c_{i}$ continues
($i=k$), and $c_{j}$ disappears. However, in a hierarchical clustering
dendrogram, both $c_{i}$ and $c_{j}$ disappear, and a new PCC $c_{k}$ starts
at $\epsilon_{t}.$ In this study, we will represent the change of connected
structure during Morse filtration by hierarchical clustering dendrograms. The
new PCC is called a parent, and the combined PCCs are called children
(children $\subset$ parent).

###  1.3 Relationship between Morse filtration and Rips filtration

Rips filtration is defined on a metric space with point cloud data and a
distance between points (Carlsson and Mémoli, 2010). If a weighted graph is in
a metric space, the topological change of a given weighted graph during Rips
filtration is related to the single linkage hierarchical clustering structure
of the graph, and it can be expressed as a dendrogram (Carlsson and Mémoli,
2010; Lee et al., 2012). Therefore, if the relationship between Rips
filtration and Morse filtration can be found, it will be clearer whether a
Morse function can be expressed as a dendrogram or not.

If a space in which a Morse function is represented as a grid coordinate, the
space looks like a lattice graph in which voxels are nodes and adjacent voxels
are connected by edges. Suppose that an edge weight (similarity) matrix of a
lattice graph is given by $\mbox{\boldmath$W$}=[w_{ij}]\in\mathbb{R}^{p\times
p},$ where

$\displaystyle w_{ij}=\left\\{\begin{array}[]{ll}s_{i},&\mbox{if $i=j,$}\\\
\min(s_{i},s_{j}),&\mbox{if $\mbox{\boldmath$v$}_{i}$ and
$\mbox{\boldmath$v$}_{j}$ are adjacent, }\\\
0,&\mbox{otherwise,}\end{array}\right.$ (4)

where $s_{i}=s(\mbox{\boldmath$v$}_{i})$ for $i=1,\dots p.$

######  Theorem 1.

Suppose that a node set, $V=\left\\{v_{1},\dots,v_{p}\right\\}$ and a
nonnegative function $s:V\rightarrow\mathbb{R}^{+}$ are given. A distance
matrix between nodes is defined by
$\mbox{\boldmath$D$}=[d_{ij}]\in\mathbb{R}^{p\times p}$ with

$\displaystyle d_{ij}=\left\\{\begin{array}[]{ll}d_{i}=1/s_{i},&\mbox{if
$i=j,$}\\\ \max(d_{i},d_{j}),&\mbox{if $\mbox{\boldmath$v$}_{i}$ and
$\mbox{\boldmath$v$}_{j}$ are adjacent, }\\\
d_{\max},&\mbox{otherwise,}\end{array}\right.$ (8)

where $d_{\max}$ is a large enough constant. The nodes $v_{1},\dots,v_{p}$
with a distance matrix $D$ are in a partial metric space. (Proof in Appendix
(Bukatin et al., 2009))

In a metric space, every point (node) has a distance of 0 from itself, so the
self-distance of a node is always 0. Therefore, all nodes exist from the
beginning of Rips filtration at threshold 0, and the number of CCs at 0 is the
same as the number of nodes. However, in a partial metric space, a self-
distance is not zero as shown in (8). If we perform Rips-like filtration on a
partial metric space with $V$ and $\mbox{\boldmath$D$},$ different nodes
appear at different thresholds.

######  Theorem 2.

Given a node set $V=\left\\{v_{1},\dots,v_{p}\right\\}$ with a nonnegative
function $\mbox{\boldmath$s$}=[s_{i}=s(v_{i})]\in\mathbb{R}^{p\times 1}$ and a
distance matrix $\mbox{\boldmath$D$}=[d_{ij}]\in\mathbb{R}^{p\times p}$ in
(8), the Morse filtration of $s$ with threshold
$\epsilon_{1}\geq\cdots\geq\epsilon_{T}\geq 0$ is the same as the Rips-like
filtration of $D$ with threshold $1/\epsilon_{1}\leq\cdots\leq
1/\epsilon_{T}\leq d_{max}.$

_Sketch of proof:_ Nodes are added in ascending order of $s_{i}$ in Morse
filtration, and in descending order of $d_{i}$ in Rips-like filtration. Since
$d_{i}=1/s_{i},$ the order of added nodes is the same. If an adjacency matrix
is $\mbox{\boldmath$A$}=[a_{ij}]=(\mbox{\boldmath$D$}>0)$ in (8), $a_{ij}=1$
when two nodes are adjacent on a brain manifold, and $0$ when they are not. If
$v_{i}$ and $v_{j}$ are adjacent, an edge between $v_{i}$ and $v_{j}$ is added
at $\max(d_{i}=1/s_{i},d_{j}=1/s_{j})$ in Rips-like filtration. This is the
same as the moment at which $v_{i}$ and $v_{j}$ appear at $\min(s_{i},s_{j})$
in Morse filtration.

The hierarchical clustering structure of Morse filtration is the same as that
of Rips-like filtration.

###  1.4 Dendrogramization and active mode detection of a spatial map

A dendrogram is a visualization tool of the hierarchy of PCCs in a tree form
on a two-dimensional plane, as shown in Fig. 1 (b). The vertical and
horizontal axes in a dendrogram represent the threshold and the index of the
PCCs, respectively. In a dendrogram, a PCC is represented by a vertical bar,
which starts at the birth threshold and ends at the death threshold. Children
and parents are connected by a horizontal bar. The last bars of the tree,
without any children are called leaves. We consider the leaves of dendrogram
as the modes of a Morse function, and the modes of a Morse function as the
activated brain regions in a spatial map.

######  Example 1.

Fig. 1 (a) shows an example of a 1-dimensional Morse function,
$\mbox{\boldmath$s$},$ with 25 nodes, denoted by $v_{1},\cdots,v_{25}$ from 0
to 12 on the horizontal axis. In this example, a voxel has two neighbors on
the left and right except for voxels at both ends. Morse filtration is
performed for thresholds, $0.75>0.7>\cdots>0,$ and PCCs, $c_{1},\dots,c_{7}$
are found as shown in Fig. 1 (e). A dendrogram in (b) shows the hierarchical
clustering structure of a Morse function $s$ in (a) as well as that of nodes
with an edge weight matrix in (f). Note that the traditional Morse filtration
finds 4 PCCs as shown in the barcode in (g). The leaves of dendrogram in (b),
$c_{2}$, $c_{3}$, $c_{1}$, and $c_{5},$ become the activated regions of the
map such that $c_{2}=\left\\{v_{5},v_{6}\right\\},$
$c_{3}=\left\\{v_{8},v_{9}\right\\},$
$c_{1}=\left\\{v_{13},\cdots,v_{17}\right\\},$ and
$c_{5}=\left\\{v_{19},\cdots,v_{22}\right\\}.$

###  1.5 Dendrogram smoothing

We propose a dendrogram smoothing method to simplify a spatial map by reducing
the number of modes in the map, by restricting the size and duration of a PCC.
First, dendrogram smoothing was performed by deleting PCCs of which size is
smaller than a predefined minimum size. During deletion, if all children are
deleted, their parent PCC absorbs all of those children, and the birth
threshold of the parent PCC is replaced by the maximum birth threshold of all
deleted children. After the deletion, if there is a PCC which has an only
child, the child is deleted, even if they are larger than the minimum size.
The children of the child become the children of the PCC which had the deleted
child. The birth threshold of the PCC, which had the deleted child, is also
replaced by the birth threshold of the deleted child. This procedure is
repeated until the size of all PCCs is larger than the minimum size. The
minimum size of a PCC is determined by the user, and determines the resolution
of a smoothed dendrogram.

Second, dendrogram smoothing was performed by choosing PCCs having longer
duration, under the assumption of persistent homology that the longer the
duration of a PCC, the better the underlying clustering structure of a Morse
function is reflected (Adler et al., 2010; Edelsbrunner and Harer, 2009). We
initialize an original list of all PCCs sorted in descending order of their
duration, and a selected list by an empty set. The PCC with the longest
duration is selected from the original list. Then, we put it on the selected
list by updating its birth threshold by the maximum peak value of voxels in
the PCC, and remove the selected PCC and all of its descendants in the
original list. Again, the PCC with the longest duration is selected from the
original list. If all its children are removed from the original list and are
in the selected list, the PCC is also removed from the original list and put
into the selected list. Otherwise, the PCC is moved to the selected list by
updating its birth threshold by the maximum peak value of its voxels, and
removed from the original list with all of its descendants, as above. This
procedure is repeated until the original list is empty. Finally, we
reconstruct a dendrogram consisting of PCCs in the selected list, and call it
a smoothed dendrogram. We call this procedure dendrogram smoothing. The leaves
of a smoothed dendrogram can be thought as the modes of a smoothed Morse
function, and we consider them to be the activated brain regions of a
simplified brain spatial map.

######  Example 2.

We apply dendrogram smoothing method to Fig. 1 (b). In this example, the
minimum size of a PCC is 0. In Fig. 2 (1), we first sort bars in descending
order of duration. Then, we initialize two lists of PCCs, $list_{original}$
and $list_{selected},$ as shown in (2). In (3), the longest green bar $c_{1}$
is selected, and it moves to $list_{selected}.$ In (4), the longest blue bar
$c_{4}$ is selected, but it has two children, $c_{2}$ and $c_{3}.$ The $c_{2}$
and $c_{3}$ are absorbed to $c_{4}$ by updating the birth threshold of
$c_{4}.$ The $c_{2},$ $c_{3},$ and $c_{4}$ are removed from $list_{original},$
and only $c_{4}$ moves to $list_{selected}.$ In (5), the longest orange bar
$c_{5}$ is selected, and it moves from $list_{original}$ to $list_{selected}.$
In (6) and (7), the next longest blue-green and khaki bars, $c_{6}$ and
$c_{7}$ are selected, respectively. Since their children are not in
$list_{original}$ at the step (6) and (7), it just moves from
$list_{original}$ to $list_{selected}.$ Finally, $list_{original}$ becomes
empty, and the smoothing procedure is finished. The smoothed dendrogram is
shown in Fig. 1 (c). The blue, green, and orange bars become the activated
brain regions of a given spatial map (Morse function) such that
$c_{4}=\left\\{v_{3},\cdots,v_{11}\right\\},$
$c_{1}=\left\\{v_{13},\cdots,v_{17}\right\\},$ and
$c_{5}=\left\\{v_{19},\cdots,v_{22}\right\\}.$

###  1.6 Relationship between a dendrogram and a smoothed dendrogram

Suppose that the hierarchy of PCCs having $v_{i}$ and $v_{j}$ in a dendrogram
is as follows:

$v_{i}\in c_{1}^{i}$$c_{2}^{i}$$\cdots$$c_{l}^{i}$$v_{j}\in
c_{1}^{j}$$c_{2}^{j}$$\cdots$$c_{m}^{j}$$c_{1}^{ij}\ni v_{i},v_{j}$

where $c_{l}^{i}$ and $c_{m}^{j}$ are PCCs having $v_{i}$ and $v_{j},$
respectively, and $c_{1}^{ij}$ are a CC where $v_{i}$ and $v_{j}$ meet for the
first time. We assume that $l\geq m.$ If $c_{1}^{ij}$ has the longest
duration, $c_{1}^{i},\dots,c_{l}^{i}$ and $c_{1}^{j},\dots,c_{m}^{j}$ are
removed by dendrogram smoothing. If we denote the birth threshold of $c$ in a
dendrogram and a smoothed dendrogram by $b_{original}(c)$ and
$b_{smoothed}(c),$ respectively, the birth threshold of $c_{1}^{ij}$ is
updated after dendrogram smoothing by:

$\displaystyle b_{smoothed}(c_{1}^{ij})$ $\displaystyle=$
$\displaystyle\max(b_{original}(c_{1}^{i}),b_{original}(c_{1}^{j})).$

Therefore, the difference between original and smoothed dendrograms is:

$\displaystyle|b_{smoothed}(c_{1}^{ij})-b_{original}(c_{1}^{ij})|$
$\displaystyle=$
$\displaystyle|\max(b_{original}(c_{1}^{i}),b_{original}(c_{1}^{j}))-b_{original}(c_{1}^{ij})|$
$\displaystyle=$
$\displaystyle\max(\tau(c_{1}^{i})+\cdots+\tau(c_{l}^{i}),\tau(c_{1}^{j})+\cdots+\tau(c_{m}^{j}))$
$\displaystyle\leq$ $\displaystyle l\tau(c_{1}^{ij}),$

where $\tau(c)$ is the duration of $c.$

###  1.7 Spatial map estimation by LMF

Given a data matrix $\mbox{\boldmath$X$}\in\mathbb{R}^{n\times p}$ with $n$
participants or time points and $p$ voxels, an LMF model decomposes $X$ into a
spatial map matrix $\mbox{\boldmath$A$}\in\mathbb{R}^{n\times k}$ and a
feature matrix $\mbox{\boldmath$S$}\in\mathbb{R}^{k\times p}$ such that
$\mbox{\boldmath$X$}\approx\mbox{\boldmath$A$}\mbox{\boldmath$S$}$, where $k$
is the predefined number of spatial maps. The column vector of
$\mbox{\boldmath$A$},$ denoted by $\mbox{\boldmath$a$}\in\mathbb{R}^{n\times
1},$ and the row vector of $\mbox{\boldmath$S$},$ denoted by
$\mbox{\boldmath$s$}^{\top}\in\mathbb{R}^{1\times p},$ are a feature and
spatial map, respectively. ICA finds spatial maps that are an independent
source generating $\mbox{\boldmath$X$},$ and PCA finds a spatial map that
consists of maximally covariated brain regions in $\mbox{\boldmath$X$}.$

If the column vector of $X$ is centered with zero mean, PCA can be written in
an optimization problem such as

$\displaystyle\begin{array}[]{lcl}\operatornamewithlimits{\arg\min}_{a,s}\parallel\mbox{\boldmath$X$}-\mbox{\boldmath$a$}\mbox{\boldmath$s$}\parallel^{2}_{2}&\Leftrightarrow&\operatornamewithlimits{\arg\max}_{s}\mbox{\boldmath$s$}\mbox{\boldmath$X$}^{\top}\mbox{\boldmath$X$}\mbox{\boldmath$s$}^{\top}\\\
\mbox{subject to
}\mbox{\boldmath$s$}\mbox{\boldmath$s$}^{\top}=1&&\mbox{subject to
}\mbox{\boldmath$s$}\mbox{\boldmath$s$}^{\top}=1.\end{array}$ (11)

In the right part of (11),
$\mbox{\boldmath$X$}^{\top}\mbox{\boldmath$X$}\in\mathbb{R}^{p\times p}$ is a
covariance matrix of $X$ in standard PCA. However, if the column vector of $X$
is centered and normalized with zero mean and length one,
$\mbox{\boldmath$X$}^{\top}\mbox{\boldmath$X$}$ becomes a correlation matrix,
which is widely used as a representation of functional brain connectivity. If
$X$ is the data matrix of a group, $s$ represents the dominant subnetwork of
the functional connectivity of the group. If $X$ is the data matrix of all
groups, for example, normal controls (NCs), stable mild cognitive impairments
(sMCIs), progressive MCIs (pMCIs), and Alzheimer’s disease (AD) patients, $s$
represents the dominant subnetwork which consists of maximally correlated
brain regions over groups, that is, changes during the Alzheimer’s disease
progression. If the number of voxels, $p,$ is too large to directly compute
$\mbox{\boldmath$X$}^{\top}\mbox{\boldmath$X$},$ we can reduce the
computational complexity by the singular value decomposition of $X$ instead of
the PCA of a correlation matrix. In this way, although we cannot observe a
voxel-level correlation matrix directly, we can find a subnetwork mainly
dominated in a correlation-based functional connectivity by basic LMF method,
PCA.

##  2 Results

###  2.1 Toy example: changing the minimum cluster size

Figure 3: Dendrograms and activated regions of Example 1 with noises. (a)
Morse functions of Example 1 by varying the magnitude of noises,
$0,0.1,\dots,0.6$ from top to bottom. Dendrograms and activated brain regions
of the Morse function on the left with the minimum cluster size (b) 0, (c) 10,
(d) 20, (e) 30, (f) 40, (g) 50, and (h) 60. In each figure, the upper panel
shows a dendrogram and the lower panel shows activated regions corresponding
to the leaves of the above dendrogram. In the lower panel, the horizontal and
vertical axes correspond to the horizontal axis of the above dendrogram and
the horizontal axis of the Morse function in (a), respectively. The color of a
bar in a dendrogram was determined by the average color of points in an
activated region corresponding to the bar.

We first observed the change of smoothed dendrogram by changing the signal-to-
noise ratio and the minimum cluster size. We generated a Morse function
$\mbox{\boldmath$s$}=[s_{i}]$ for $i=1,\dots,241$ by mixing four Gaussian
distributions as follows:

$\displaystyle s_{i}$ $\displaystyle=$ $\displaystyle
1.3{\mathcal{N}}(v_{i};2,0.8)+1.2{\mathcal{N}}(v_{i};4,0.8)$
$\displaystyle+1.2{\mathcal{N}}(v_{i};7,0.6)+0.3{\mathcal{N}}(v_{i};10,0.6)+w\cdot
e,$

where ${\mathcal{N}}(v_{i};\mu,\sigma)$ is a Gaussian distribution of a
variable $v_{i}\in\left\\{0,0.05,\cdots,12\right\\},$ with mean $\mu$ and
standard deviation $\sigma,$ $e$ is Gaussian noise following
${\mathcal{N}}(e;0,1),$ and $w$ is a parameter controlling the magnitude of
noise. The generated Morse function, $\mbox{\boldmath$s$},$ was shown in Fig.
3 (a) for $w=0,0.1,0.2,\cdots,0.6$ from top to bottom. The 241 nodes each had
its own color from blue through green to red. We obtained the dendrogram and
activated regions of each Morse function by varying the minimum size of a
cluster, $0,10,20,\dots,60$ in (b-h).

The first row in (b-h) shows the smoothed dendrograms and the activated
regions of the true Morse function without noise, but with different minimum
sizes. As the minimum size increased, the small clusters, like the red nodes,
disappeared from the dendrogram, as shown in (g,h). Although the noise levels
of the functions were different, the activated regions obtained by the
smoothed dendrograms were somewhat similar to each other at the minimum
cluster size 30 in (e). However, because of the noise, the birth and death
thresholds of the activated regions (clusters) were different from those of
the true dendrogram without noise.

Figure 4: (a) ICMs, (i) DMN and (ii) SN (bottom). (b) Histogram of DMN and SN.
The colored region in a histogram corresponds to voxels in activated brain
regions obtained by (i,ii) the proposed method, (iii,iv) $Z>4,$ and (v,vi)
$Z>6.$ The color is the same as the color of the corresponding activated brain
regions. The gray region represents voxels that were not selected as any
activated brain regions. (c) Dendrograms of (i,ii) DMN and (iii,iv) SN in (a).
The positive and negative parts are on (i,iii) and (ii,iv), respectively.
Activated brain regions are plotted on the corresponding leaf bar. Activated
brain regions that survived $Z>4$ and $Z>6$ are represented by $\ast$ and
$\ast\ast,$ respectively. Detailed brain regions are listed in Table 1.

###  2.2 ICMs of resting-state fMRI

####  2.2.1 Data set and ICA

Resting-state fMRI data was measured from 20 healthy subjects (male = 4;
female = 16, mean age = 26.45 $\pm$ 5.20, mean education year = 15.55 $\pm$
2.77) when they closed their eyes (TR = 3000ms, TE = 30ms, flip angle = 90°,
FOV = 240 $\times$ 240mm, matrix size 128 $\times$ 128, 45 axial slices with
3mm thickness, voxel size = 1.9 $\times$ 1.9 $\times$ 3.0mm3, resulting 180
volumes). The imaging data was preprocessed using Statistical Parametric
Mapping (SPM, www.fil.ion.ucl.ac.uk/spm/) and FMRIB Software Library (FSL,
fsl.fmrib.ox.ac.uk). The preprocessing procedure was as follows: (1)
discarding five volumes, (2) repairing using ArtRepair Software
(https://cibsr.stanford.edu/tools/human-brain-project/artrepair-software.html)
(Mazaika et al., 2005), (3) slice timing and motion artifacts corrections, (4)
co-registeration to anatomical T1 weighted images and normalization to
Montreal Neurological Institute (MNI) space, (5) smoothing and intensity
normalization, (6) wavelet despiking (Patel and Bullmore, 2016), (7)
regressing out of white matter and CSF signals, and six motion parameters, and
(8) bandpass filtering (0.01Hz-0.1Hz). ICA was performed by using Multivariate
Exploratory Linear Decomposition into Independent Components (MELODIC). Among
ICMs, we manually selected a default mode network (DMN) and a salience network
(SN), which are plotted in Fig. 4 (a). We also estimated the threshold values
of $Z>4$ and $Z>6$ in DMN and SN by using the Post-Stats method in MELODIC.

####  2.2.2 Dendrogramization and activated regions

A spatial map, $\mbox{\boldmath$s$},$ usually has positive and negative parts,
denoted by $\mbox{\boldmath$s$}_{+}>0$ and $\mbox{\boldmath$s$}_{-}<0,$
respectively. Therefore, we dendrogramized $\mbox{\boldmath$s$}_{+}>0$ and
$-\mbox{\boldmath$s$}_{-}>0$ separately, and showed the smoothed dendrograms
of the positive and negative parts separately on the left and right of Fig. 4
(c), respectively. We chose a minimum cluster size of 800. The activated brain
regions of the ICMs were plotted on the corresponding bars in a dendrogram.
The color of the voxels was set according to their location in the brain, red
for frontal, green for parietal, blue for temporal, violet for occipital,
green and orange for subcortical, and purple for cerebellar regions. The color
of the brain regions and corresponding bars was determined by averaging the
colors of voxels in the brain region. In the dendrograms, the threshold values
of $Z>4$ (*) and $Z>6$ (**) were plotted as the blue dashed lines.

The detailed names of the activated brain regions in Fig. 4 (c) are given in
Table 1. In the dendrogram in Fig. 4 (c-i), there are three big gaps between
the birth values of the activated brain regions. The first one was between the
fourth and fifth regions (1.38 and 1.04), the second one was between the first
and second regions (1.88 and 1.65), and the third one was between the seventh
and eighth regions (0.93 and 0.70). The second and fourth activated regions
were the left and right ANG, respectively. If the spatial map was thresholded
at $Z>6,$ only the left ANG was detected, and the right ANG was missed by a
narrow margin. In ICM, the negative part was usually rarely considered. In our
DMN, when thresholding the map at the same threshold $Z>4$ in the positive
part, two activated regions, MTG and ITG (blue) and right PCNU (green),
survived (Fig. 4 (c-ii)).

In the dendrogram in Fig. 4 (c-iii), there are also three big gaps between the
third and fourth activated regions (1.07 and 0.74), the first and second
regions (1.29 and 1.08), and the fifth and sixth regions (0.67 and 0.49). If
the threshold level was selected by $Z>6$ (**), the right MFG and SFG would be
missed. The histograms of DMN and SN are plotted in Fig. 4 (b), and they show
the distribution of the activated brain regions selected by the proposed
method, $Z>4,$ and $Z>6$ from top to bottom according to the colored regions.

Figure 5: (a,b) Dominant spatial maps representing the overall changes during
disease progression, and those representing NC, sMCI, pMCI, and AD in voxel-
and ROI-level functional connectivity. Each spatial map is plotted in the top,
right and left lateral, and the right and left medial views from left to
right. The boxplot of the corresponding features for NC, sMCI, pMCI, and AD
are shown on the right. (c,d) Subnetworks (top), dendrograms (bottom, left),
and smoothed dendrograms (bottom, right) of the voxel- and ROI-level dominant
spatial maps of the overall change in (a,b). The positive and negative parts
of a spatial map are dendrogramized on the left and right, respectively. In a
circular subnetwork, activated brain regions corresponding to the leaf bars in
a dendrogram became nodes. If two nodes are within the same positive or
negative parts, they are connected by red, orange, or yellow lines. Otherwise,
they are connected by blue or sky blue lines. The line width and the darkness
of the line color is proportional to the peak values of the connected nodes.

###  2.3 Subnetwork extraction from FDG PET ADNI data

####  2.3.1 Data set

Data used in the preparation of this article were obtained from the
Alzheimer’s Disease Neuroimaging Initiative (ADNI) database
(adni.loni.usc.edu). The ADNI was launched in 2003 as a public-private
partnership, led by Principal Investigator Michael W. Weiner, MD. The primary
goal of ADNI has been to test whether serial magnetic resonance imaging (MRI),
positron emission tomography (PET), other biological markers, and clinical and
neuropsychological assessment can be combined to measure the progression of
mild cognitive impairment (MCI) and early Alzheimer’s disease (AD). The FDG
PET images in the ADNI dataset consisted of 182 NCs, 92 sMCIs, 78 pMCIs, and
138 AD patients (age: $73.7\pm 5.9$, range $56.1\textendash 90.1$). The FDG
PET images were measured from 30 to 60 min, and averaged over all frames. The
images were spatially normalized to MNI space using SPM software (SPM8,
www.fil.ion.ucl.ac.uk/spm). More details are given in (Choi and Jin, 2018).
The dimensions of the brain image data were $79\times 95\times 68.$ We
selected $182,363$ voxels which were labeled by a second version of automated
anatomical labeling atlas (AAL2) (Rolls et al., 2015).

####  2.3.2 Dominant subnetwork of Alzheimer’s disease progression

We obtained the dominant spatial maps of all groups, NC, sMCI, pMCI, and AD by
the PCA of voxel- and ROI-level correlation matrices in (11). The voxel- and
ROI-level dominant spatial maps are plotted in Fig. 5 (a,b). We also estimated
features by projecting the spatial maps to the data matrix of all groups, and
the boxplots of the features were plotted for four groups in (a,b). The
asterisk (*) on the right indicates that the spatial map of overall change in
the first row could significantly discriminate between the four groups
(Kruskal-Wallis test, $p<.005$), and that of NC, sMCI, pMCI, and AD in the
next four rows could significantly discriminate the group from the other
groups (Wilcoxon rank sum test, $p<.005$).

Fig. 5 (c,d) showed the original and smoothed dendrograms, and subnetworks of
the voxel- and ROI-level dominant spatial maps of overall change,
respectively, in the first row in (a,b). We set the minimum cluster size to
400 for dendrogram smoothing. In the voxel-level subnetwork in (c), the
positive part consisted of the ACC, PCNU, ANG, prefrontal region (ROL, SFGmed,
MFG, SFG, IFGtri), and MTG and ITG with caudate (CAU), which are related to
the DMN. The negative part mainly consisted of the cerebellum, hippocampus
(HIP), and motor cortex (postcentral gyrus (PoCG), supplementary motor area
(SMA), PCL), which are related to motor function and memory. In the ROI-level
subnetwork in (d), the positive part was the anterior part of brain including
the prefrontal, temporal, and parietal regions with the ACC and CAU, and the
negative part was the cerebellar and occipital regions with the PoCG. The
positive and negative parts of the subnetworks were negatively correlated, and
decreased and increased with the disease progression, respectively, because
their features decreased over the groups in the first row of Fig. 5 (a,b).

Figure 6: (a,c) Best match between the dominant spatial maps of overall
change, NC, sMCI, pMCI, and AD in Fig. 5 (a,b) and those obtained by 10
repeats of a two-fold cross validation (20 different sets). (b,d) Histograms
of correlation values at the best match. The color, blue, green, yellow, red,
or violet represents the spatial maps of overall change, NC, sMCI, pMCI, and
AD in the 20 sets, respectively. (e) Number of times when features were
significantly distinguished between groups among the 20 sets (corrected
$p<.005$).

####  2.3.3 Reliability

To check the reliability of the dominant spatial maps, corresponding features
and dendrograms, we repeated a two-fold cross validation 10 times, and
obtained 20 different sets for all groups, NC, sMCI, pMCI, and AD. To assess
the reliability of the spatial maps, we estimated the Pearson correlation
between the dominant spatial maps of all groups, NC, sMCI, pMCI, and AD in
Fig. 5 (a,b) and those obtained by the set, and found a best match between
them using the Hungarian algorithm (Papadimitriou and Steiglitz, 1982). In
Fig. 6 (a), in voxel-level analysis, the dominant spatial maps of overall
change, NC, sMCI, pMCI, and AD in Fig. 5 (a) from left to right columns are
always maximally matched to those obtained by the cross validation. However,
in Fig. 6 (c), in ROI-level analysis, they were maximally matched to 80 %
overall, 85 % NC, 80 % sMCI, 65 % pMCI, and 80 % AD spatial maps among 20
different sets. The histograms of the correlation values at the best match are
plotted in (b) and (d). In (b)-NC, the correlation values at the best match
for the 20 sets were not high, with the minimum correlation value 0.27.
However, even the minimum value was significant, because the dimension of the
spatial maps is 182,363. In (d), the correlation values of the 20 sets tended
to be high when they were best matched with the same group (blue for overall
change, green for NC, yellow for sMCI, red for pMCI, and violet for AD).

We counted the number of times that the features of overall change were
significantly distinguished between the four groups, using Kruskal-Wallis
tests, and those of NC, sMCI, pMCI, and AD were significantly distinguished
between the group and the other groups by Wilconxon rank sum tests (Bonferroni
corrected $p<.005$). The results are shown in Fig. 6 (e). Only the features of
overall change showed the 100 % reproducibility of discrimination for the 20
sets at both voxel- and ROI-level. To check the change in the structure of the
original and smoothed dendrograms over the groups, we counted the number of
all PCCs, all leaf bars, all layers, and voxels covered by all activated brain
regions in the voxel-level original and smoothed dendrograms of the 20 sets,
and the results of the group difference are summarized in Table 2.

Table 1: Detailed names of activated brain regions in Fig. 4.

|  |  color |  $s_{max}$ |  regions |  significance
---|---|---|---|---|---
(a) |  1 |  red |  1.88 |  RL: medial part of superior frontal gyrus (SFGmed), superior frontal gyrus (SFG), Rolandic operculum (ROL) |  **
|  2 |  mint |  1.65 |  L: angular gyrus (ANG), supramarginal gyrus (SMG), inferior parietal gyrus (IPG) |  **
|  3 |  yellow-green |  1.49 |  RL: precuneus (PCNU), anterior and middle cingulate cortex (ACC, MCC) |  **
|  4 |  mint |  1.38 |  R: ANG, middle occipital gyrus (MOG), IPG |  *
|  5 |  blue |  1.04 |  R: middle and inferior temporal gyrus (MTG, ITG), and the temporal pole of middle temporal gyrus (MTGp) |  *
|  6 |  red |  0.95 |  L: the orbital part of inferior frontal gyrus (IFGorb) |  *
|  7 |  blue |  0.93 |  L: MTG, ITG, MTGp, insula (INS) |  *
(b) |  1 |  blue |  -0.95 |  L: MTG and ITG |  *
|  2 |  green |  -0.90 |  R: PCNU |  *
(c) |  1 |  red |  1.29 |  RL: ROL, ACC, paracentral lobule (PCL) |  **
|  2 |  gray |  1.08 |  L: INS, SMG, precentral gyrus (PreCG), superior temporal gyrus (STG), the pars triangular of the inferior frontal gyrus (IFGtri), putamen (PUT), |  **
|  3 |  gray |  1.07 |  R: INS, SMG, PreCG, PUT, STG |  **
|  4 |  red |  0.74 |  L: middle frontal gyrus (MFG), SFG, IFGtri |  **
|  5 |  red |  0.67 |  R: MFG and SFG |  *

$s_{max}:$ the maximum peak value in an activated brain region, R: right
hemisphere, L: left hemisphere, **: $Z>6,$ *: $Z>4$

Table 2: Change of the structure of voxel-level original and smoothed dendrograms during Alzheimer’s disease progression (Wilcoxon rank sum test, Boferroni corrected $p<.005$). Original | Positive | Negative
---|---|---
# PCCs | NC$\approx$sMCI$\approx$pMCI$>$AD | NC$\approx$sMCI$\approx$pMCI$>$AD
# leaves | NC$\approx$sMCI$\approx$pMCI$>$AD | NC$\approx$sMCI$\approx$pMCI$>$AD
# layers | NC$\approx$sMCI$\approx$pMCI$\approx$AD | NC$\approx$sMCI$\approx$pMCI$\approx$AD
# voxels | NC$\approx$sMCI$\approx$pMCI$>$AD | NC$\approx$sMCI$>$pMCI$>$AD
Smoothed | Positive | Negative
# PCCs | sMCI$>$NC$>$pMCI$>$AD | sMCI$\approx$NC$>$pMCI$>$AD
# leaves | sMCI$>$NC$>$pMCI$>$AD | sMCI$\approx$NC$>$pMCI$>$AD
# layers | sMCI$>$NC$>$pMCI$>$AD | sMCI$>$NC$>$pMCI$>$AD
# voxels | NC$\approx$sMCI$\approx$pMCI$<$AD | NC$\approx$sMCI$\approx$pMCI$\approx$AD

##  3 Discussion and conclusions

In this study, we developed a threshold-free activated region extraction
method from a brain spatial map by dendrogramizing and smoothing the map. To
verify the proposed method, we also demonstrated the relationship between Rips
filtration and Morse filtration. The proposed method can simplify a Morse
function including a brain spatial map in a three-dimensional space to a
dendrogram in a two-dimensional plane. The dendrogramized spatial map can
visualize activated brain regions as well as the range of their importance in
a spatial map. Therefore, a user can check the shape of a brain spatial map
estimated by his or her own method, and choose a proper threshold by
monitoring the dendrogramized map for interpretation. In Sec. 2.2.2, if the
significance level was appropriately adjusted within the allowable range by
dendrograms, the brain symmetry of DMN and SN could be preserved. We could
also choose the threshold by using the large gaps between activated brain
regions, not only by the significance level. The proposed method can help to
identify the shape of a spatial map in a brain space, rather than in a
histogram or vectorized form of the map. In Table 2, the smoothed dendrogram
of the positive part in AD had a small number of layers and leaf bars, while
there were a large number of voxels in activated brain regions. This finding
might indicate that the function of brain regions in AD was fused and crushed
rather than performing their own functions. Another advantage of the proposed
method is the ability to transform a spatial map (function) to a network, as
shown in Sec. 2.3.2. Since PCA and ICA are multivariate approaches, the
obtained spatial map contains the information about the relationship between
variables (voxels). The proposed method could express this hidden relationship
in a spatial map as a network, as shown in Fig. 5 (c), in which DMN was found
in the positive part, and a network related with motor function and memory was
found in the negative part.

The disadvantage of the proposed method is that it can be affected by the
spatial smoothing of the brain imaging data. When the proposed method was
applied to non-smoothed data, the activated brain regions were like jagged
clusters. Therefore, smoothing is necessary before applying the proposed
dendrogramization. As can be seen in toy example in the Results section, the
duration of the activated regions in the dendrogram was sensitive to the noise
level, while the activated regions themselves were comparatively well
estimated. Therefore, in the future, we need to develop an additional
procedure to correct the duration according to the noise level.

The proposed method can be applied to a statistical map obtained in a
hypothesis-driven way. However, there is a risk of increasing the false
positive rate. We therefore limited the application of the proposed method to
a brain spatial map obtained by a data-driven LMF model in this study.
However, a method to appropriately adjust the cluster size and significance
level could provide a new approach to cluster-based statistics in the future.

## Acknowledgement

Data collection and sharing for this project was funded by the Alzheimer’s
Disease Neuroimaging Initiative (ADNI) (National Institutes of Health Grant
U01 AG024904) and DOD ADNI (Department of Defense award number
W81XWH-12-2-0012). ADNI is funded by the National Institute on Aging, the
National Institute of Biomedical Imaging and Bioengineering, and through
generous contributions from the following: AbbVie, Alzheimer’s Association;
Alzheimer’s Drug Discovery Foundation; Araclon Biotech; BioClinica, Inc.;
Biogen; Bristol-Myers Squibb Company; CereSpir, Inc.; Cogstate; Eisai Inc.;
Elan Pharmaceuticals, Inc.; Eli Lilly and Company; EuroImmun; F. Hoffmann-La
Roche Ltd and its affiliated company Genentech, Inc.; Fujirebio; GE
Healthcare; IXICO Ltd.; Janssen Alzheimer Immunotherapy Research &
Development, LLC.; Johnson & Johnson Pharmaceutical Research & Development
LLC.; Lumosity; Lundbeck; Merck & Co., Inc.; Meso Scale Diagnostics, LLC.;
NeuroRx Research; Neurotrack Technologies; Novartis Pharmaceuticals
Corporation; Pfizer Inc.; Piramal Imaging; Servier; Takeda Pharmaceutical
Company; and Transition Therapeutics. The Canadian Institutes of Health
Research is providing funds to support ADNI clinical sites in Canada. Private
sector contributions are facilitated by the Foundation for the National
Institutes of Health (www.fnih.org). The grantee organization is the Northern
California Institute for Research and Education, and the study is coordinated
by the Alzheimer’s Therapeutic Research Institute at the University of
Southern California. ADNI data are disseminated by the Laboratory for Neuro
Imaging at the University of Southern California. This research was supported
by Basic Science Research Program through the National Research Foundation of
Korea (NRF) funded by the Ministry of Education (2020R1A2C1013853,
2016R1D1A1B03935, 2020R1A2C2011532, and 2017M3C7A1048079).

## Appendix: Proof of theorem 1

  1. 1.

Nonnegativity and small self-distances: $0\leq d_{ii}\leq
d_{ij}=\max(d_{i},d_{j})$

  2. 2.

Indistancy implies equality: if $d_{i}=d_{j}=d_{ij}=\max(d_{i},d_{j}),$ then,
$v_{i}$ and $v_{j}$ are connected as soon as they appear during Morse
filtration. They are the same.

  3. 3.

Symmetry: $d_{ij}=\max(d_{i},d_{j})=d_{ji}.$

  4. 4.

Triangularity: given $v_{i},$ $v_{j},$ and $v_{k},$

    1. (a)

if they all are not adjacent,
$d_{ij}+d_{jk}-d_{j}-d_{ik}=d_{\max}+d_{\max}-d_{j}-d_{\max}>0.$

    2. (b)

if $v_{i}$ and $v_{j}$ are adjacent, but $v_{k}$ is not connected,
$d_{ij}+d_{jk}-d_{j}-d_{ik}=\max(d_{i},d_{j})+d_{\max}-d_{j}-d_{\max}\geq 0.$

    3. (c)

if $v_{j}$ and $v_{k}$ are adjacent, but $v_{i}$ is not connected,
$d_{ij}+d_{jk}-d_{j}-d_{ik}=d_{\max}+\max(d_{j},d_{k})-d_{j}-d_{\max}\geq 0.$

    4. (d)

if $v_{i}$ and $v_{k}$ are adjacent, but $v_{j}$ is not connected,
$d_{ij}+d_{jk}-d_{j}-d_{ik}=d_{\max}+d_{\max}-d_{j}-\max(d_{i},d_{k})\geq 0.$

    5. (e)

if they all are adjacent,
$d_{ij}+d_{jk}-d_{j}-d_{ik}=\max(d_{i},d_{j})+\max(d_{j},d_{k})-d_{j}-\max(d_{i},d_{k})={\mathcal{A}}$.

      1. i.

$d_{i}\geq d_{j}\geq d_{k}:{\mathcal{A}}=d_{i}+d_{j}-d_{j}-d_{i}=0$

      2. ii.

$d_{i}\geq d_{k}\geq d_{j}:{\mathcal{A}}=d_{i}+d_{k}-d_{j}-d_{i}\geq 0$

      3. iii.

$d_{j}\geq d_{i}\geq d_{k}:{\mathcal{A}}=d_{j}+d_{j}-d_{j}-d_{i}\geq 0$

      4. iv.

$d_{j}\geq d_{k}\geq d_{i}:{\mathcal{A}}=d_{j}+d_{j}-d_{j}-d_{k}\geq 0$

      5. v.

$d_{k}\geq d_{i}\geq d_{j}:{\mathcal{A}}=d_{i}+d_{k}-d_{j}-d_{k}\geq 0$

      6. vi.

$d_{k}\geq d_{j}\geq d_{i}:{\mathcal{A}}=d_{j}+d_{k}-d_{j}-d_{k}=0$

Therefore, $d_{ik}\leq d_{ij}+d_{jk}-d_{jj}.$

The given $p$ nodes with distance $D$ satisfies the properties of a partial
metric space.

## References

  * Beckmann et al. [2009] C. F. Beckmann, C. E. Mackay, N. Filippini, and S. M. Smith.  Group comparison of resting-state fMRI data using multi-subject ICA and dual regression.  _NeuroImage_ , 47:S148, 2009.
  * Bijsterbosch et al. [2017] Janine Bijsterbosch, Stephen M. Smith, and Christian F. Beckmann.  _Introduction to Resting State fMRI Functional Connectivity_.  Oxford University Press, 2017.
  * Correa et al. [2010] Nicolle Correa, Tulay Adali, Yi-Ou Li, and Vince Calhoun.  Canonical correlation analysis for data fusion and group inferences.  _IEEE Signal Processing Magazine_ , 27(4):39–50, 2010.
  * Calhoun and Adalı [2012] V. D. Calhoun and T. Adalı.  Multisubject independent component analysis of fMRI: a decade of intrinsic networks, default mode, and neurodiagnostic discovery.  _IEEE Rev Biomed Eng._ , 5:60–73, 2012.
  * Marchitelli et al. [2018] Rocco Marchitelli, Marco Aiello, Arnaud Cachia, Mario Quarantelli, Carlo Cavaliere, Alfredo Postiglione, Gioacchino Tedeschi, Patrizia Montella, Graziella Milan, Marco Salvatore, Elena Salvatore, Jean Claude Baron, and Sabina Pappatà .  Simultaneous resting-state FDG-PET/fMRI in Alzheimer disease: Relationship between glucose metabolism and intrinsic activity.  _NeuroImage_ , 176:246–258, 2018.  ISSN 1053-8119.
  * de Cheveigné et al. [2019] Alain de Cheveigné, Giovanni M. Di Liberto, Dorothée Arzounian, Daniel D.E. Wong, Jens Hjortkjær, Søren Fuglsang, and Lucas C. Parra.  Multiway canonical correlation analysis of brain data.  _NeuroImage_ , 186:728–740, 2019.
  * Mohammadi-Nejad et al. [2017] A. R. Mohammadi-Nejad, G. A. Hossein-Zadeh, and H. Soltanian-Zadeh.  Structured and sparse canonical correlation analysis as a brain-wide multi-modal data fusion approach.  _IEEE Transactions on Medical Imaging_ , 36(7):1438–1448, 2017.
  * Toussaint et al. [2012] P. J. Toussaint, V. Perlbarg, P. Bellec, S. Desarnaud, L. Lacomblez, J. Doyon, M. O. Habert, H. Benali, and for the ADNI.  Resting state FDG-PET functional connectivity as an early biomarker of Alzheimer’s disease using conjoint univariate and independent component analyses.  _NeuroImage_ , 63:936–946, 2012.
  * Woo et al. [2017] Choong-Wan Woo, Luke J Chang, Martin A Lindquist, and Tor D Wager.  Building better biomarkers: brain models in translational neuroimaging.  _Nature Neuroscience_ , 20:365–377, 2017.
  * Nichols [2012] T. E. Nichols.  Multiple testing corrections, nonparametric methods, and random field theory.  _NeuroImage_ , 62:811–815, 2012.
  * Smith and Nichols [2009] S. M. Smith and T. E. Nichols.  Threshold-free cluster enhancement: addressing problems of smoothing, threshold dependence and localisation in cluster inference.  _NeuroImage_ , 44:83–98, 2009.
  * Mckeown et al. [1998] Martin J. Mckeown, Scott Makeig, Greg G. Brown, Tzyy-Ping Jung, Sandra S. Kindermann, Anthony J. Bell, and Terrence J. Sejnowski.  Analysis of fMRI data by blind separation into independent spatial components.  _Hum. Brain Mapp._ , 6:160–188, 1998.
  * Beckmann and Smith [2004] C. F. Beckmann and S. M. Smith.  Probabilistic independent component analysis for functional magnetic resonance imaging.  _IEEE Transactions on Medical Imaging_ , 23(2):137–152, Feb 2004.
  * Poppe et al. [2013] A. B. Poppe, K. Wisner, G. Atluri, K. O. Lim, V. Kumar, and A. W. 3rd. Macdonald.  Toward a neurometric foundation for probabilistic independent component analysis of fMRI data.  _Cogn Affect Behav Neurosci_ , 13(3):641–59, 2013\.
  * Ma and MacDonald [2021] Yizhou Ma and Angus MacDonald.  Impact of ica dimensionality on the test-retest reliability of resting-state functional connectivity.  _Brain Connectivity_ , 0(ja):null, 2021.  PMID: 33926215.
  * Carlsson and Mémoli [2010] G. Carlsson and F. Mémoli.  Characterization, stability and convergence of hierarchical clustering methods.  _J. Mach. Learn. Res._ , 11:1425–1470, 2010.
  * Edelsbrunner and Harer [2009] H. Edelsbrunner and John Harer.  _Computational Topology: An Introduction_.  American Mathematical Society Press, 2009.
  * Adler et al. [2010] R. J. Adler, O. Bobrowski, M. S. Borman, E. Subag, and S. Weinberger.  Persistent homology for random fields and complexes.  _ArXiv e-prints_ , 2010.
  * Lee et al. [2012] H. Lee, M. K. Chung, H. Kang, B. N. Kim, and D. S. Lee.  Persistent brain network homology from the perspective of dendrogram.  _IEEE T. Med. Imaging_ , 31:2267–2277, 2012.
  * Bukatin et al. [2009] Michael Bukatin, Ralph Kopperman, Steve Matthews, and Homeira Pajoohesh.  Partial metric spaces.  _The American Mathematical Monthly_ , 116(8):708–718, 2009.
  * Mazaika et al. [2005] P. K. Mazaika, S. Whitfield, and J. C. Cooper.  Detection and repair of transient artifacts in fMRI data.  In _Human Brain mapping_ , 2005.
  * Patel and Bullmore [2016] A. X. Patel and E. T. Bullmore.  A wavelet-based estimator of the degrees of freedom in denoised fMRI time series for probabilistic testing of functional connectivity and brain graphs.  _Neuroimage_ , 142:14–26, 2016.
  * Choi and Jin [2018] Hongyoon Choi and Kyong Hwan Jin.  Predicting cognitive decline with deep learning of brain metabolism and amyloid imaging.  _Behavioural Brain Research_ , 344:103 – 109, 2018.  ISSN 0166-4328.
  * Rolls et al. [2015] E. T. Rolls, M. Joliot, and N. Tzourio-Mazoyer.  Implementation of a new parcellation of the orbitofrontal cortex in the automated anatomical labeling atlas.  _NeuroImage_ , 122:1–5, 2015.
  * Papadimitriou and Steiglitz [1982] Christos H. Papadimitriou and Kenneth Steiglitz.  _Combinatorial Optimization: Algorithms and Complexity_.  Prentice-Hall, Inc., USA, 1982.  ISBN 0131524623.


# Contextual Dynamic Prompting for Response Generation in Task-oriented Dialog
Systems

Sandesh Swamy
AWS AI Labs
<EMAIL_ADDRESS>&Narges Tabari
AWS AI Labs
<EMAIL_ADDRESS>Chacha Chen
University of Chicago
<EMAIL_ADDRESS>&Rashmi Gangadharaiah
AWS AI Labs
<EMAIL_ADDRESS>Work done during an internship at AWS AI Labs

###### Abstract

Response generation is one of the critical components in task-oriented dialog
systems. Existing studies have shown that large pre-trained language models
can be adapted to this task. The typical paradigm of adapting such extremely
large language models would be by fine-tuning on the downstream tasks which is
not only time-consuming but also involves significant resources and access to
fine-tuning data. Prompting (Schick and Schütze, 2020) has been an alternative
to fine-tuning in many NLP tasks. In our work, we explore the idea of using
prompting for response generation in task-oriented dialog systems.
Specifically, we propose an approach that performs contextual dynamic
prompting where the prompts are learnt from dialog contexts. We aim to distill
useful prompting signals from the dialog context. On experiments with MultiWOZ
2.2 dataset Zang et al. (2020), we show that contextual dynamic prompts
improve response generation in terms of combined score Mehri et al. (2019a) by
3 absolute points, and a massive 20 points when dialog states are
incorporated. Furthermore, human annotation on these conversations found that
agents which incorporate context were preferred over agents with vanilla
prefix-tuning.

##  1 Introduction

With the advent of large language models (LLMs), a vast majority of NLP tasks,
including dialog systems, further fine-tune these LMs for their downstream
tasks. Although these approaches provide substantial improvements over
traditional task-specific models Ham et al. (2020); Hosseini-Asl et al.
(2020); He et al. (2022), it is a time consuming process that also involves
significant use of energy/resources in the form of compute. These approaches
also require tuning and storing parameters for each downstream task.

A more recent line of work, explores “prompting” LLMs to elicit the necessary
knowledge required for the downstream tasks Shin et al. (2020); Gao et al.
(2020); Schick and Schütze (2020); Petroni et al. (2019); Lee et al. (2021);
Zhu et al. (2022). Prompts composed of tokens or short pieces of text
(discrete prompts) inserted at the end of the input examples. These prompts
are typically manually defined based on the specific downstream task. The main
motivation behind these approaches stems from the idea that the large corpora
that these language models are trained on contain relevant information which
is pertinent to the task on hand.

Adapter-tuning was proposed as an alternate approach to fine-tuning. These
methods only train task-specific layers that are inserted within pretrained
LMs. Such a lightweight approach that add about 4% task-specific parameters
has shown to obtain comparable performances to their fine-tuning counterparts
Rebuffi et al. (2017); Houlsby et al. (2019); Lin et al. (2020a).

Drawing inspiration from prompting, prefix-tuning approaches Li and Liang
(2021) were proposed as another alternative to fine-tuning. These approaches
pre-pend a sequence of task-specific continuous vectors (aka prefix-) to the
input. In contrast to prompting, the prefix consists of free parameters that
do not correspond to actual real tokens. Such an approach is more prevalent
since it only optimizes the prefix and does not tune parameters of the entire
LM.

Most of the existing approaches use static prompts, i.e., the same set of
tokens are used as “prompt tokens" regardless of input. However, we believe
that taking context into consideration is critical especially in response
generation since the current response has to fit not only the domain but also
the information being requested in previous turns. For example: In the
MultiWOZ dataset, if a customer asks about train bookings, the agent response
has to restrict itself to that particular domain. To address this problem, we
explore the idea of generating input-dependent or contextual prompts. We want
the prompts to capture and encode different signals for different turns of
dialogs depending on the context, hence, we call our approach dynamic context
prompting. This way, we hope to distill useful signals into the prompts and
provide the model with adequate signals to generate a desired system response.
In this work, we explore the potential of using dialog context within a prefix
tuning approach for the task of response generation in task-oriented dialog
systems (TOD). The contributions of this paper are summarized as:

  * •

we propose a context-dependent prefix-tuning method for dialog response
generation in TOD systems.

  * •

to illustrate the benefits of such an approach, we conduct experiments on the
MultiWOZ dataset. We show that our model significantly outperforms the
original task-dependent design of the prefix-tuning method.

##  2 Related Work

###  2.1 Dialog Generation

With the prevalence of LLMs, the quest for an answer to “how do we effectively
adapt such models for dialog generation?" has been on the forefront of
researchers’ minds in the dialog community. For task-oriented dialogs, fine-
tuning large pre-trained models such as GPT-2 or T5 has made great progress on
benchmarks recently Ham et al. (2020); Hosseini-Asl et al. (2020). Built upon
these advances, more recent line of work investigates the effectiveness of
using multi-task learning Su et al. (2021); Lin et al. (2020b); Yang et al.
(2021), or pre-training the model on external dialog corpora Peng et al.
(2021); Liu et al. (2021). More recently, prompting has been used to address
the sub-task of dialog state tracking Lee et al. (2021); Zhu et al. (2022).
Different from those works, we focus on the task of dialog response
generation.

###  2.2 Prompt-based Learning

As an alternative to the fine-tuning paradigm, prompting involves a sequence
of tokens appended to the input text, which can then induce the model to
engage in a certain behavior suited to the task. Since the release of GPT-2
Radford et al. (2018, 2019); Brown et al. (2020), many prompt-related papers
have emerged. Most of the leading approaches in prompting use task-specific
prompts, ranging from discrete prompts Shin et al. (2020); Gao et al. (2020);
Schick and Schütze (2020); Petroni et al. (2019) to continuous “soft prompts”
Li and Liang (2021); Lester et al. (2021). These methods have a fixed prompt
for each task. However, in dialog systems specifically, the context varies for
every turn. In our work, we aim to design prompts which are context-dependent.

##  3 Problem Statement

Response generation is one of the tasks carried out in dialog systems usually
in addition to dialog state tracking (DST). Given a dialog context (previous
turns between the system and the user) $C=[u_{1},s_{1},...,u_{n-1},s_{n-1}]$
and the current user utterance $u_{n}$, the goal of response generation is to
generate system response $s_{n}$. Note that in the actual task, we generate
delexicalized system responses, given all the groundtruth previous turns as
input, following previous works Hosseini-Asl et al. (2020); Wen et al. (2015).

Techniques mentioned in Ham et al. (2020); Hosseini-Asl et al. (2020) rely on
fully fine-tuning LLMs to carry out this task. In contrast, our approach
builds on the prefix-tuning framework, but incorporates dialog context, $C$,
as an additional signal for the prefix tokens. As a supplement to context $C$,
we added dialog state information $D$ (up to the current turn) to further help
response generation.

##  4 Contextual Dynamic Prompting Framework

###  4.1 Prefix-tuning for Response Generation

Figure 1: The figures above indicate the differences between the vanilla
prefix-tuning approach compared to our approach. In both these variants, only
the prefix tokens are tuned.

Our work is built on top of prefix tuning for generation tasks Li and Liang
(2021), which adds a fixed set of tunable prefix tokens/prompts to the
original input $x$ to obtain a new input, [PREFIX; $x$]. Following the
denotation in (Li and Liang, 2021), we use $P_{\theta}[i,:]$ to denote the
$i_{th}$ prefix. $P_{\theta}[i,:]$ is generated by:

$P_{\theta}[:,:]=MLP_{\theta}(P^{\prime}),$ (1)

where $P^{\prime}$ is a fixed smaller matrix as input to a feedforward neural
network ($MLP_{\theta}$). The training objective of prefix-tuning is same as
fine-tuning, i.e., the following log-likelihood objective:

$\max_{\theta}\log p_{\phi}(y|x),$

where $y$ is the decoder output and $x$ is the input. $\theta$ represents the
trainable parameters in the prefix tuning feedforward neural network and
$\phi$ denotes all other parameters that include the frozen parameters of the
large language model.

For our task of response generation, we concatenate the prefix with the dialog
context and the current user utterance as input [PREFIX;
$u_{1},s_{1},...,u_{n-1},s_{n-1},u_{n}$]. The target output is the system
response $s_{n}$ as seen in Figure 1 (a).

We adopt T5 Raffel et al. (2020) as the pre-trained language model. T5 employs
an encoder-decoder framework which is prevalent in seq2seq tasks Sutskever et
al. (2014); Cho et al. (2014).

###  4.2 Contextual Prefix-tuning

In vanilla prefix-tuning, the parameters of the prefix are fixed after
training for any particular task to be reused. However, a dialog system
involves having multiple turns of conversation between a system and the user.
It is imperative in such systems to dynamically incorporate contextual
information to carry out a meaningful conversation with the user. We explore
how we can distill the dialog context information into the prefix with a
prompt encoder.

Different from the original design, we want to encode additional signals into
the prefix that differs for each input instances. In other words, we want to
generate contextual prefix or contextual dynamic prompts.

Formally, we modify the equation (1) as follows:

$P_{\theta}[:,:]=MLP_{\theta}(encoder(C)),$ (2)

where $C=[u_{1},s_{1},...,u_{n-1},s_{n-1}]$ represents the dialog context. We
first obtain the representation of the dialog context by feeding $C$ into a T5
encoder which is kept frozen as shown in Figure 1 (b). Subsequently, we use
the prompt encoder, i.e., the feedforward neural network, to get the prefix.
The generated prefix $P_{\theta}$ is then concatenated with only the current
user utterance. Instead of concatenating the whole context as the input to the
T5 decoder, we first distill the signal into the prefix tokens. As a
consequence of freezing the T5 encoder which generates the context
representation, we still have the same number of tunable parameters as the
original prefix-tuning framework.

###  4.3 Input-dependent Prefix-tuning with Dialog State

In most task-oriented dialog systems, we also have access to the dialog state
at every turn in addition to dialog context. The dialog state has information
such as requested slots and filled slots at every turn. We provide the dialog
state $D$ in addition to the context $C$ to obtain contextual dynamic prompts.
As a result, we will now modify equation (2) as:

$P_{\theta}[:,:]=MLP_{\theta}(encoder(C;D_{n-1})),$ (3)

we only provide the most recent dialog state $D_{n-1}$ which is an
amalgamation of all previous dialog states $D_{<n-1}$.

| MultiWOZ 2.2
---|---
| BLEU | Inform | Success | Combined Score | Av. len. | #uniq. words | #uniq. 3-grams |
Prefix-Tuning | 19.19 | 54.7 | 48.0 | 70.54 | 13.83 | 245 | 1671 |
Prefix-Tuning (with DS) | 19.36 | 51.8 | 47.0 | 68.76 | 13.08 | 231 | 1626 |
Contextual Dynamic Prompt | 19.16 | 58.1 | 50.5 | 73.46 | 14.16 | 231 | 1532 |
Contextual Dynamic Prompt (with DS) | 17.94 | 77.2 | 68.8 | 90.94 | 14.02 | 282 | 2390 |

Table 1: Performance Comparison. All model performance are based on features
from all modalities. Contextual Dynamic Prompt (with DS) has the best
performance in combined score.

##  5 Experimental Settings

###  5.1 Dataset and Metrics

We evaluate our proposed framework and model on the MultiWOZ 2.2 dataset Zang
et al. (2020); Budzianowski et al. (2018) which is a large-scale, multi-
domain, human-human task-oriented dialog dataset collected via the Wizard-of-
Oz framework where one participant plays the role of the system. It consists
of seven domains including hotel, restaurant, attraction, train, taxi,
hospital, and police, and an additional domain general for acts such as
greeting or goodbye. Due to its multi-domain setting, complex ontology, and
flexible human expressions, developing dialog systems on MultiWOZ is extremely
challenging. The training data contain 8437 dialogs, the dev and test set
contain 1000 dialogs each.

We use four evaluation metrics: BLEU Papineni et al. (2002), Inform, and
Success rates, and combined score. Inform measures whether the system provides
an appropriate entity and Success measures whether the system answers all the
requested attributes. Specifically, the Inform rate relates to attributes that
allow the user to constrain database searches, e.g., restaurant location or
price range (the informational slots) and the Success rate focuses on request-
able slots, that can be asked by the user, e.g., phone number. Both are
calculated on the level of dialogs. The combined score is calculated following
Mehri et al. (2019b) as $BLEU+0.5*(Inform+Success)$. We followed a standard
script 111https://github.com/Tomiinek/MultiWOZ_Evaluation to report different
measures.

###  5.2 Human Evaluation

We chose a 10% subset of the evaluation set (randomly shuffled) conversations
with a total of 728 turns across them and provided annotators with the
responses generated by each of the methods described in section 4. Annotators
were asked to rate each agent on a turn-level and to also pick the agent which
carried out the best conversation. If annotators felt more than one agent did
well, they could choose multiple agents. The agent numbers, when provided to
annotators, were shuffled to avoid bias. Each agent is described as:

  * •

Agent 1: Incorporates only prefix-tuning

  * •

Agent 2: Incorporates prefix-tuning with Dialog State

  * •

Agent 3: Incorporates contextual dynamic prompts

  * •

Agent 4: Incorporates contextual dynamic prompts with Dialog State

When annotating on turn level, from these 728 turns, we saw that the agents
tied on 596 occasions, agent 1 had outright win on 12 occasions, agent 2 on
22, agent 3 on 33 occasions, and agent 4 on 65 occasions. This shows that our
technique of using contextual dynamic prompts for generating responses is
effective (Examples in Appendix B).

Additionally, on the conversation level, we noticed that across 100
conversations, 37 were tied, and agents 3 and 4 were preferred in a total of
53 conversations confirming our hypothesis that incorporating context into
prompts leads to better responses. We request readers to refer to Appendix A
and B for more details about the annotation task.

##  6 Results

As shown in Table 1, contextual dynamic prompting with dialog states obtains a
combined score of 90.94, a 20 point jump from our baseline (prefix-tuning). In
addition, even though we can’t explicitly explain the drop in BLEU, the
massive jumps in both success and inform suggest more transparency and
coherence for the responses generated by the input-dependent prefix-tuning as
these metrics focus on quality of informational and request-able slots in each
turn. When comparing our results with the human annotations, we also see that
Agent 4 \- which uses contextual dynamic prompting - wins 38 conversations
(out of 100). This is majority of wins compared to Agent 1 winning only 3
conversations, and Agent 2 winning 7. This further emphasized that adding
contextual dynamic prompts leads to better quality of responses. We show some
examples from the human annotation task where Agent 4 was chosen as the
winning agent in Tables 2 and 3 below.

Turn num |  User turn |  Agent 1 response |  Agent 2 response |  Agent 3 response |  Agent 4 response
---|---|---|---|---|---
1 |  i am looking for a place to dine. the restaurant should be expensive and should serve chinese food. |  there are [choice] [pricerange] [food] restaurants in town. do you have a preference for area or price range? |  i have [choice] [pricerange] [food] restaurants. do you have a preference for area? |  there are [choice] [pricerange] [food] restaurants. do you have a price range in mind? |  there are [choice] [food] restaurants in the [pricerange] price range. is there a particular area you are interested in?
2 |  not in any specific area please. i need to book a table for 3 at 14:00 on saturday. |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. is there anything else i can help you with? |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. |  i was able to book you at [name] for [bookday] at [booktime]. your reference number is [ref]. is there anything else i can help you with? |  i have made a reservation for you at [name]. the table will be reserved for 15 minutes. the reference number is [ref]. is there anything else i can help you with?
3 |  how about 13:00 then? |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. is there anything else i can help you with? |  ok, i have you booked at [name]. your reference number is [ref]. is there anything else i can help you with?
4 |  what is the reference number for my booking? |  your reference number is [ref]. is there anything else i can help you with? |  the reference number is [ref]. is there anything else i can help you with? |  your reference number is [ref]. is there anything else i can help you with? |  the reference number is [ref].
5 |  no thank you, that is all i needed! |  you’re welcome. have a great day! |  you’re welcome. have a great day! |  you’re welcome. have a great day! |  you’re welcome, have a great day!
Table 2: An example where Agent 4 was picked as the best performing agent in a conversation. Turn num |  User turn |  Agent 1 response |  Agent 2 response |  Agent 3 response |  Agent 4 response
---|---|---|---|---|---
1 |  can you help me find a restaurant that serves african food with a moderate price range please |  there are no [food] restaurants in the [pricerange] price range. would you like to try a different type of food? |  there are no [food] restaurants in the [pricerange] price range. would you like to try a different type of food? |  there are no [food] restaurants in the [pricerange] price range. would you like to try a different type of food? |  [name] is a [food] restaurant in the [area]. would you like to try it?
2 |  yes how about asian food in the same price range? |  there are [choice] [food] restaurants in the [area] and [choice] in the [area]. do you have a preference? |  there are [choice] [food] restaurants in the [pricerange] price range. do you have a preference for area? |  there are [choice] [pricerange] [food] restaurants in the [area]. do you have a price range in mind? |  [name] is a [food] restaurant in the [pricerange] price range.
3 |  will you please book a table for 6 at 13:45 on friday? |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. is there anything else i can help you with? |  booking was successful. the table will be reserved for 15 minutes. reference number is : [ref]. |  i was able to book you at [name] for [bookday] at [booktime]. your reference number is [ref]. is there anything else i can help you with? |  i have made a reservation for [bookpeople] at [booktime] on [bookday] at [booktime]. the table will be reserved for 15 minutes. the reference number is [ref]. is there anything else i can help you with?
4 |  that’s all i needed. thanks a lot for the help! |  you’re welcome. have a great day! |  you’re welcome. have a great day! |  you’re welcome. have a great day! |  you’re welcome. have a great day!
Table 3: An example where Agent 4 was picked as the best performing agent in a
conversation.

##  7 Conclusion

In our work, we proposed an approach that performs contextual dynamic
prompting where prompts are learnt from dialog contexts with the goal of
distilling useful prompting signals. In our experiments, we showed that
contextual dynamic prompts improve response generation in terms of combined
score Mehri et al. (2019a) by 3 points, and by 20 points when dialog states
are incorporated compared to the baseline. Our technique does not expose the
models to additional knowledge sources. Human annotation on these
conversations found that agents which incorporate context into prompts were
preferred over agents with vanilla prefix-tuning.

## Limitations

While our work explores a new technique of contextual dynamic prompts for
response generation, we carried out our experiments on a dataset which is in
the English language. A potential limitation of this work would be the
transfer of our findings on an English dataset to a multi-lingual dataset or a
mono-lingual dataset on a language other than English. We plan to address this
in our future work and also request the help of the research community in
doing so.

## Acknowledgements

We would like to thank the anonymous reviewers for their feedback on this
work. We also thank the AWS Console/UXP2 Science team at AWS AI Labs for
discussions around this work. Lastly, we’d like to thank the human annotators
for their efforts.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Budzianowski et al. (2018) Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Ultes Stefan, Ramadan Osman, and Milica Gašić. 2018.  Multiwoz - a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014\.  On the properties of neural machine translation: Encoder–decoder approaches.  In _Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation_ , pages 103–111, Doha, Qatar. Association for Computational Linguistics.
  * Gao et al. (2020) Tianyu Gao, Adam Fisch, and Danqi Chen. 2020.  Making pre-trained language models better few-shot learners.  _arXiv preprint arXiv:2012.15723_.
  * Ham et al. (2020) Donghoon Ham, Jeong-Gwan Lee, Youngsoo Jang, and Kee-Eung Kim. 2020.  End-to-end neural pipeline for goal-oriented dialogue systems using gpt-2.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 583–592.
  * He et al. (2022) Wanwei He, Yinpei Dai, Yinhe Zheng, Yuchuan Wu, Zheng Cao, Dermot Liu, Peng Jiang, Min Yang, Fei Huang, Luo Si, Jian Sun, and Yongbin Li. 2022.  Galaxy: A generative pre-trained model for task-oriented dialog with semi-supervised learning and explicit policy injection.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(10):10749–10757.
  * Hosseini-Asl et al. (2020) Ehsan Hosseini-Asl, Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher. 2020.  A simple language model for task-oriented dialogue.  _Advances in Neural Information Processing Systems_ , 33:20179–20191.
  * Houlsby et al. (2019) Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019.  Parameter-efficient transfer learning for NLP.  _CoRR_ , abs/1902.00751.
  * Lee et al. (2021) Chia-Hsuan Lee, Hao Cheng, and Mari Ostendorf. 2021.  Dialogue state tracking with a language model using schema-driven prompting.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 4937–4949, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Lester et al. (2021) Brian Lester, Rami Al-Rfou, and Noah Constant. 2021.  The power of scale for parameter-efficient prompt tuning.  _arXiv preprint arXiv:2104.08691_.
  * Li and Liang (2021) Xiang Lisa Li and Percy Liang. 2021.  Prefix-tuning: Optimizing continuous prompts for generation.  _arXiv preprint arXiv:2101.00190_.
  * Lin et al. (2020a) Zhaojiang Lin, Andrea Madotto, and Pascale Fung. 2020a.  Exploring versatile generative language model via parameter-efficient transfer learning.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 441–459, Online. Association for Computational Linguistics.
  * Lin et al. (2020b) Zhaojiang Lin, Andrea Madotto, Genta Indra Winata, and Pascale Fung. 2020b.  Mintl: Minimalist transfer learning for task-oriented dialogue systems.  _arXiv preprint arXiv:2009.12005_.
  * Liu et al. (2021) Qi Liu, Lei Yu, Laura Rimell, and Phil Blunsom. 2021.  Pretraining the noisy channel model for task-oriented dialogue.  _Transactions of the Association for Computational Linguistics_ , 9:657–674.
  * Mehri et al. (2019a) Shikib Mehri, Tejas Srinivasan, and Maxine Eskenazi. 2019a.  Structured fusion networks for dialog.  In _Proceedings of the 20th Annual SIGdial Meeting on Discourse and Dialogue_ , pages 165–177, Stockholm, Sweden. Association for Computational Linguistics.
  * Mehri et al. (2019b) Shikib Mehri, Tejas Srinivasan, and Maxine Eskenazi. 2019b.  Structured fusion networks for dialog.  _arXiv preprint arXiv:1907.10016_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Peng et al. (2021) Baolin Peng, Chunyuan Li, Jinchao Li, Shahin Shayandeh, Lars Liden, and Jianfeng Gao. 2021.  Soloist: Buildingtask bots at scale with transfer learning and machine teaching.  _Transactions of the Association for Computational Linguistics_ , 9:807–824.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel. 2019.  Language models as knowledge bases?  _arXiv preprint arXiv:1909.01066_.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. 2018.  Improving language understanding by generative pre-training.  _https://openai.com/blog/language-unsupervised/_.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1–67.
  * Rebuffi et al. (2017) Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi. 2017.  Learning multiple visual domains with residual adapters.  _CoRR_ , abs/1705.08045.
  * Schick and Schütze (2020) Timo Schick and Hinrich Schütze. 2020.  Exploiting cloze questions for few shot text classification and natural language inference.  _arXiv preprint arXiv:2001.07676_.
  * Shin et al. (2020) Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. 2020.  Autoprompt: Eliciting knowledge from language models with automatically generated prompts.  _arXiv preprint arXiv:2010.15980_.
  * Su et al. (2021) Yixuan Su, Lei Shu, Elman Mansimov, Arshit Gupta, Deng Cai, Yi-An Lai, and Yi Zhang. 2021.  Multi-task pre-training for plug-and-play task-oriented dialogue system.  _arXiv preprint arXiv:2109.14739_.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014.  Sequence to sequence learning with neural networks.  In _Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’14, page 3104–3112, Cambridge, MA, USA. MIT Press.
  * Wen et al. (2015) Tsung-Hsien Wen, Milica Gasic, Nikola Mrksic, Pei-Hao Su, David Vandyke, and Steve Young. 2015.  Semantically conditioned lstm-based natural language generation for spoken dialogue systems.  _arXiv preprint arXiv:1508.01745_.
  * Yang et al. (2021) Yunyi Yang, Yunhao Li, and Xiaojun Quan. 2021.  Ubar: Towards fully end-to-end task-oriented dialog system with gpt-2.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 14230–14238.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  Multiwoz 2.2: A dialogue dataset with additional annotation corrections and state tracking baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI, ACL 2020_ , pages 109–117.
  * Zhu et al. (2022) Qi Zhu, Bing Li, Fei Mi, Xiaoyan Zhu, and Minlie Huang. 2022.  Continual prompt tuning for dialog state tracking.  _arXiv preprint arXiv:2203.06654_.

##  Appendix A Human Evaluation Task

We explored contextual dynamic prompting strategies for the response
generation task using the MultiWOZ 2.2 Budzianowski et al. (2018); Zang et al.
(2020) dataset and noticed that the combined score that we obtained was
significantly better than the baseline prefix-tuning method of response
generation. To understand if the agents which incorporated contextual dynamic
prompts did indeed provide a better conversational experience, we designed a
small human evaluation task to test our hypothesis.

We picked a random subset of 10% of the conversations from the original
MultiWOZ test data to perform this analysis. Once we obtained this random set,
we ran our four model variants as described in Section 4 on the conversations
to obtain system responses for each of them. We then presented the different
agents’ responses to the annotator as shown in Table 4 below. In order to
avoid potential biases, we shuffled the order of the agents between our
annotators i.e., Agent 1 for annotator a would not be Agent 1 for annotator b.
We kept track of which agents corresponded to which of our four methods prior
to distribution of data amongst the annotators.

The annotators were given instructions to read every turn of conversation and
provide a number between 1 and 4 for the agent which they thought performed
the best for that turn. If the annotators found that there was a tie, they
could pick more than one agent as [agent_a, agent_b]. In addition to this
instruction, annotators were asked to read the entire conversation and pick
the agent which performed the best - once again with an option to pick
multiple. Table 5 below shows an example annotation style for a single
conversation spanning 6 turns. There is an annotation at every turn and a
single annotation at the end of the conversation.

We tallied results and re-mapped all agents back to their methods and found
that agents 3 and 4 as mentioned in Section 5.2 were preferred at the
conversation level in a total of 53 of the 100 conversations while agents 1
and 2 were only preferred 10 conversations in the entire set of 100.

Turn num | User turn | Agent 1 response | Agent 2 response | Agent 3 response | Agent 4 response
---|---|---|---|---|---
1 |  |  |  |  |
2 |  |  |  |  |
3 |  |  |  |  |
4 |  |  |  |  |
5 |  |  |  |  |
6 |  |  |  |  |
7 |  |  |  |  |
Table 4: The format which is presented to annotators while performing turn-level and conversation-level annotation. The agents are shuffled between the annotators to avoid biasing them. Turn num | Turn level | Conversation level
---|---|---
1 | 2 |
2 | [3,4] |
3 | 2 |
4 | 3 |
5 | 4 |
6 | [3,4] | 3
Table 5: We asked annotators to provide two levels of annotation for each
conversation - turn level and conversation level. Annotators were allowed to
pick more than agent in case of a tie.

##  Appendix B Examples

In the table below, we provide another examples from the human annotation task
where annotators picked agent 4 as the best performing agent for the
conversation (we performed the re-mapping to fit the agent numbers in Section
5.2). Table 2 shown in the main paper indicates a scenario where Agent 4 was
rightly able to ask the customer about their area of preference for dining,
and also considers a booking time change from the user. Table 6 shows an
example where agent 4 is able to take into consideration all the different
constraints mentioned by the user in terms of slots in the response that it
generates. Table 3 shows an example where the agent 4 is able to correctly
respond to the user request for number of people to reserve the table for -
which none of the other agents captured. All these examples showed that agent
4, which uses contextual dynamic prompts with dialog states was indeed able to
provide smoother responses to the customer input compared to the other agents.

Turn num |  User turn |  Agent 1 response |  Agent 2 response |  Agent 3 response |  Agent 4 response
---|---|---|---|---|---
1 |  i am looking for a train that departs from peterborough and goes to cambridge. |  there are [choice] trains leaving from [departure] to [destination]. what day would you like to travel? |  what day would you like to travel? |  there are [choice] trains leaving [departure] from [departure] to [destination]. what day would you like to travel? |  i have [choice] trains departing from [departure] to [destination]. what day would you like to travel?
2 |  we will be leaving on sunday afternoon. |  [trainid] leaves [departure] at [leaveat] and arrives in [destination] at [arriveby]. would you like me to book that for you? |  i have [choice] trains available. what time would you like to leave? |  [trainid] leaves at [leaveat] and arrives in [destination] at [arriveby]. would you like me to book it for you? |  [trainid] leaves [departure] at [leaveat] and arrives at [destination] at [arriveby]. would that work for you?
3 |  yes, it should leave after 20:15 and leave on monday, not sunday. please give me a price, travel time, and arrival time for any train. |  [trainid] leaves at [leaveat] and arrives in [destination] at [arriveby]. the price is [price]. |  [trainid] leaves at [leaveat] and arrives at [arriveby]. would you like me to book that for you? |  [trainid] leaves at [leaveat] and arrives at [arriveby]. the price is [price]. would you like me to book it for you? |  [trainid] leaves [departure] at [leaveat] and arrives in [destination] at [arriveby]. the cost is [price] and the travel time is [duration].
4 |  yes please. what is the travel time? i’ll also need a hotel in the expensive price range. can you help me with that as well? |  the travel time is [duration]. is there anything else i can help you with? |  the travel time is [duration]. |  the travel time is [duration]. is there anything else i can help you with? |  the travel time is [duration]. is there anything else i can help you with?
5 |  yes, i’d like a 2 star rating and i’ll need it to be in the east side of town. |  i have [choice] [type] in the [area] with [stars] stars. do you have a preference? |  there are [choice] [type] in the [area] that are [stars] stars. do you have a preference? |  there are [choice] [type] in the [area] that are [pricerange] and [pricerange]. do you have a preference? |  [name] is a [stars] star hotel in the [area]. would you like me to book it for you?
6 |  yes, i would like to book it for 3 people starting that same day for 4 nights. |  booking was successful. reference number is : [ref]. is there anything else i can help you with? |  booking was successful. reference number is : [ref]. |  booking was successful, the total fee is [price] payable at the station. reference number is : [ref]. |  booking was successful. the total fee is [price] payable at the station. reference number is : [ref].
7 |  that is all thank you goodbye. |  you’re welcome. have a great day! |  you’re welcome. have a great day. |  you’re welcome. have a great day. |  you’re welcome. have a great day.
Table 6: Another example where Agent 4 was picked as the best performing agent
in a conversation.

##  Appendix C Compute Infrastructure and Experimental settings used

All our experiments were carried out on public AWS p3 GPU instances which are
backed by Tesla V100 GPU cores. All four variants of our models required 18-24
hours to reach convergence on these machines. Learning rates were varied based
on performance of models on the validation split of our dataset.