the entire sequence, which is useful for many downstream tasks. Technically,
the prediction of the output words requires adding an MLM head on top of the
encoder output:

$\displaystyle
P_{r}(x|\mathbf{h}_{i})=\mathrm{softmax}(\mathbf{W}\cdot\mathbf{h}_{i})=\frac{\exp(\mathbf{W}_{i}\mathbf{h}_{i})}{\sum_{x_{t}\in\mathcal{V}}\exp(\mathbf{W}_{t}\mathbf{h}_{t})}.$

This classification layer multiplies the output vectors $\mathbf{h}_{i}$ by a
projection matrix $\mathbf{W}$, transforms them into the vocabulary dimension
$|\mathcal{V}|$, and calculates the probability of each word in the vocabulary
with softmax as

Figure 3.4: Pre-training BERT with Masked Language Modeling [Devlin et al.,,
2018].

Figure 3.4 shows an example of pre-training BERT using MLM. Since no manual
label is required, BERT can be trained on large amounts of raw text corpora.
For example, the BERT base model, a 12-layer Transformer with 110 million
parameters, is pre-trained on the Wikipedia and Google Book Corpora which
amount to 16 GB words [Devlin et al.,, 2018]. Recent results show that
training a larger PLM on a larger dataset significantly improve model’s
performance, especially in few-shot or zero-shot settings where there is few
or zero task labels in the downstream task [Liu et al., 2019c, ; Raffel et
al.,, 2019; Brown et al.,, 2020; Roberts et al.,, 2020; Schick and Schütze,,
2020].

While the root reason why PLMs are so effective remains an open research
topic, a recent study shows that BERT does capture linguistic information,
representing the steps of the traditional NLP pipeline (e.g., POS tagging,
parsing, NER, semantic roles, then coreference) in an interpretable and
localizable way [Tenney et al.,, 2019].

###### Fine-Tuning for Downstream Tasks.

A PLM can be adapted to downstream tasks by continually fine-tuning the
parameters of the PLM and an added task-specific head using task labels, e.g.,
relevance labels in document search. Depending on the formulation of the
target downstream task, we use different types of task-specific heads, and
process training data accordingly. Figure 3.5 presents three commonly used
formulations of downstream tasks for fine-tuning PLMs.

Figure 3.5: Three formulations of downstream tasks: single prediction (Left),
pair prediction (Middle) and dual-encoding matching (Right).

The first formulation is Single Prediction, as illustrated in Figure 3.5
(Left). It is often used to predict a label for a single text sequence. Take
the text classification task as an example. The probability that text $X$ is
labeled as class $y$ (i.e., the positive or negative sentiment) is predicted
by a logistic regression with softmax:

$\displaystyle P_{r}(y|X)=\text{softmax}(\mathbf{W}\cdot\mathbf{x}),$ (3.6)

where $\mathbf{x}$ is the contextual vector of $X$ (i.e., the contextual
vector of the [CLS] token), and $\mathbf{W}$ is the task-specific parameter
matrix. Note that we can make prediction using the contextual vectors of other
token, rather than [CLS], in the input. For example, we might want to predict
the POS tag of a word or a text span in extractive OA tasks.

The second formulation is Pair Prediction, as illustrated in Figure 3.5
(Middle). It is used to predict a label for a pair (or a set) of text
sequences. An example is to predict the relevance label of a query-document
pair. This can be achieved by feeding the concatenation of query string
$X_{1}$, a [SEP] token, and document string $X_{2}$ to the model, and the
relevance label $y$ is predicted using a logistic regression layer with
softmax:

$\displaystyle
P_{r}(y|X_{1},X_{2})=\text{softmax}(\mathbf{W}\cdot\mathbf{x}),$ (3.7)

where $\mathbf{x}$ is the contextual representation of the concatenated input
sequence (i.e., the contextual vector of the [CLS] token), and $\mathbf{W}$ is
the task-specific parameter matrix. In neural IR, this pair prediction task is
sometimes denoted as BERT${}_{\text{CAT}}$ or Transformer${}_{\text{CAT}}$.

The third formulation is Dual-Encoding Matching, as illustrated in Figure 3.5
(Right). This is often used in text similarity or matching tasks. For example,
in document search we might want to compute the relevance score Rel(.) between
query $X_{1}$ and each candidate document $X_{2}$ as

$\displaystyle\text{Rel}(X_{1},X_{2})=\text{sim}(\mathbf{x}_{1},\mathbf{x}_{2};\theta),$
(3.8)

where $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are the contextual representations
of $X_{1}$ and $X_{2}$, generated by the two encoders (dual-encoding),
respectively, and sim(.) is a similarity function which can be implemented
using cosine similarity or a model parameterized by $\theta$. Compared to the
pair prediction formulation, dual-encoding is more often used for document
retrieval where runtime efficiency is important. Dual-encoding allows
documents and queries to be encoded separately so that we can _pre-encode_ all
documents and the IR system only needs to encode an input query on the fly for
retrieval. Dual-encoding is widely used for dense retrieval [Huang et al.,,
2013; Lee et al., 2019a, ; Karpukhin et al.,, 2020; Xiong et al.,, 2021],
which will be discussed in later sections. This formulation is also referred
to as the representation-based model, dual-encoder, siamese-encoder, weak
interaction model, deep structured similarity model etc.

The PLM fune-training follows the standard supervised learning procedure,
where the parameters of the PLM and its added task-specific head are optimized
w.r.t. the task loss, e.g., cross entropy for prediction, rank loss in
relevance ranking, and NCE loss in dense retrieval.

###  3.4 System Architecture

Figure 3.6:  A general architecture of conversational document search systems.

A typical architecture of conversational search systems is illustrated in
Figure 3.6. It consists of a subset of the components of the CIR architecture
in Figure 1.4. Following the task setting described in Section 3.1,
conversational search is performed as follows. A user issues a series of
conversational queries $\\{Q_{1},...,Q_{N}\\}$ for a topic $\mathcal{T}$,
where each query $Q$ is part of the conversational trajectory and its answer
depends on not only $Q$ but its dialog history $\mathcal{H}$ which includes
all its previous queries and their system responses. The system returns for
each query $Q$ a list of documents $\\{D_{1},...,D_{M}\\}$, ranked by their
relevance scores with respect to $Q$. The search is conducted using three
components: contextual query understanding, document retrieval, and document
ranking. The result generation module will be described in Chapters 4 and 5.

###### Contextual Query Understanding.

Since ellipsis phenomena are frequently encountered in conversational search,
understanding a conversational query $Q$ relies on its context. Contextual
query understanding conceptually acts as a query rewriter, which uses
conversational context $\mathcal{H}$ to rewrite $Q\in\mathcal{T}$ to a de-
contextualized query $\hat{Q}$ for document retrieval. The rewriter can be
implemented as a separate module using query expansion methods or neural
rewriting models (Section 3.5), or as part of the conversational dense
retrieval module (Section 3.8).

###### Document Retrieval.

Identifying a short list of relevant documents of query $Q$ (or its de-
contextualized form $\hat{Q}$) from a large document collection $\mathcal{D}$
is computationally expensive. For efficiency, a coarse-to-fine search strategy
is widely adopted where the overall search process is divided into two phases,
document _retrieval_ and _ranking_ , either of which may consist of multiple
steps to perform coarse-to-fine document retrieval or (re-)ranking,
respectively. Conceptually, document retrieval needs to examine each
$D\in\mathcal{D}$ its relevance to $Q$. Since a brute-force method is
prohibitively expensive, it is necessary to construct an index of
$\mathcal{D}$ for efficient retrieval. For example, sparse retrieval methods
(Section 3.6) often use the (weighted) inverted index to help find the top-$K$
relevant documents efficiently, as that in ad hoc search [Croft et al.,,
2010]. Dense retrieval methods (Section 3.7, on the other hand, have to resort
to efficient similarity search methods [Aumüller et al.,, 2017; Johnson et
al.,, 2017; Li et al.,, 2020] to find relevant documents in a continuous
vector space.

###### Document Ranking.

Given top-$K$ candidate documents retrieved from $\mathcal{D}$, where
$K\ll|\mathcal{D}|$, we can afford to use sophisticated ranking models, such
as Transformer-based PLMs, to (re-)rank these documents to return a short list
of the most relevant documents to the user.

The rest of this chapter describes the models and methods recently developed
for the aforementioned three components.

###  3.5 Contextual Query Understanding

The contextual query understanding (CQU) task is to reformulate a
conversational query $Q$, given its conversational context $\mathcal{H}$, to a
de-contextualized query $\hat{Q}$ that can be used alone (without
$\mathcal{H}$) for document retrieval. So, $\hat{Q}$ is also called a
_standalone_ query.

This section presents three types of CQU methods based on heuristic query
expansion, machine learning based query expansion, and neural query rewriting.
All the methods we describe below are developed on the early TREC CAsT
datasets, where turns in a conversational search session depend only on
previous queries but not system responses, as shown in the examples in Table
3.1. Thus, the conversational context of a query at the $i$-th dialog turn
$Q_{i}$ contains only previous conversational queries,
$\mathcal{H}_{i}=\\{Q_{1},…,Q_{i-1}\\}$.

####  3.5.1 Heuristic Query Expansion Methods

Conversational query expansion methods [e.g., Lin et al., 2020b, ; Yang et
al.,, 2019; Voskarides et al.,, 2020] generate a standalone query
$\hat{Q}_{i}$ for a conversational query $Q_{i}$ by adding to $Q_{i}$ a set of
query terms $\mathcal{S}$. The expansion terms are often selected from its
dialog history $\mathcal{H}_{i}$ to optimize the retrieval result of
$\hat{Q}_{i}$ as

$\displaystyle\mathcal{S}^{*}$
$\displaystyle=\text{argmax}_{\mathcal{S}\subseteq\mathcal{H}_{i}}\text{Accuracy}(Q_{i}\cup\mathcal{S}),$
(3.9)

where $\text{Accuracy}(Q_{i}\cup\mathcal{S})$ denotes the quality (accuracy)
of the ad hoc retrieval results using the standalone query, which is $Q_{i}$
expanded with terms in $\mathcal{S}$.

Similar to query expansion in ad hoc search [Croft et al.,, 2010], it is
difficult, or often impossible, to directly optimize Equation 3.9. The
document search system, which is used to estimate
$\text{Accuracy}(Q_{i}\cup\mathcal{S})$, is in general not differentiable.
Thus, many approaches have been developed to obtain $\mathcal{S}^{*}$
approximately using either heuristics or machine learning methods.

As an example of heuristic query expansion methods of CQU, we describe the
Historical Query Expansion (HQE) method proposed by Lin et al., 2020b . HQE is
a very simple and effective method, leading to one of the top-performing
systems in TREC CAsT 2019 [Yang et al.,, 2019]. HQE was developed on the TREC
CAsT dataset, taking advantage of two characteristics of conversational
queries observed from the dataset.

  1. 1.

Main topic and subtopic: A conversational session is centered around a main
topic, and the turns in the session dive deeper into subtopics, each of which
only lasts a few turns. For example, in Table 3.1 (a), the main topic of the
session is “acid reflux”, Turns 3, 4 and 5 discuss the subtopics of “OTC”,
“PPI”, and “treatment”, respectively, while Turns 5 to 8 are related to
“treatments”.

  2. 2.

Degree of ambiguity: The conversational queries can be labeled by degree of
ambiguity of three categories. The first category includes queries with clear
intent, which can be directly used as standalone queries, such as Turn 1 in
Table 3.1 (a). The second contains those starting a subtopic (e.g., Turns 3, 4
and 5). The third contains ambiguous queries that continue a subtopic (e.g.,
Turns 6, 7, and 8).

HQE performs CQU in three steps. For each search query $Q$ in a dialog
session, (1) the main topic and subtopic keywords are extracted from $Q$; (2)
the ambiguity of $Q$ is measured; and (3) a standalone query $\hat{Q}$ is
formed by expanding $Q$ with the main topic and subtopic keywords extracted
from its dialog history $\mathcal{H}$. These steps are performed using a
keyword extractor and a query performance predictor.

###### Keyword Extractor (KE).

KE computes the importance score of each query term $q$ with respect to the
query (or topic) it occurs. Lin et al., 2020b  propose to approximate the
importance score $R(q)$ using the retrieval score (e.g., BM25) of $q$’s
highest-scoring document as

$\displaystyle R(q)$ $\displaystyle=\max_{D\in\mathcal{D}}\text{BM25}(q,D).$
(3.10)

The intuition behind this design is that the importance of a word can be
judged from those documents that are (potentially) highly relevant to it. That
is, if a word is representative of its relevant documents, it is likely a
keyword of the topics of these documents [Lin et al., 2020b, ].

###### Query Performance Predictor (QPP).

QPP measures a query’s ambiguity. Assuming that the degree of query ambiguity
is closely related to its ambiguity with respect to the collection of
documents being searched. Following the design of KE, the ambiguity of a query
$Q$ is scored as the retrieval score (e.g., BM25) of the query’s highest-
scoring document as

$\displaystyle\text{QPP}(Q)$
$\displaystyle=\max_{D\in\mathcal{D}}\text{BM25}(Q,D).$ (3.11)

The higher the QPP score, the less ambiguous $Q$ is.

With KE and QPP defined above, HQE works in three steps:

  1. 1.

For each query $Q=\\{q_{1},...,q_{N}\\}$ in a conversation session, HQE
extracts topic (subtopic) keywords from $Q$ if $R(q)>R_{\text{topic}}$
($R(q)>R_{\text{sub}}$), where $R_{\text{topic}}$ ($R_{\text{sub}}$) is a
hyperparameter, and collects them in the keyword set
$\mathcal{S}_{\text{topic}}$ ($\mathcal{S}_{\text{sub}}$).

  2. 2.

QPP measures the ambiguity of each query $Q$, and labels it as ambiguous if
$\text{QPP}(Q)<\eta$, where $\eta$ is a hyperparameter.

  3. 3.

For all queries $Q_{i}$ in the session, except the first turn $Q_{1}$, HQE
first rewrites $Q_{i}$ by concatenating it with the topic keyword set
$\mathcal{S}_{\text{topic}}$ collected from its history $\mathcal{H}_{i}$.
Moreover, if $Q_{i}$ is ambiguous, HQE further adds the subtopic keywords
$\mathcal{S}_{\text{sub}}$ from the previous $M$ turns, where $M$ is a
hyperparameter, assuming that subtopic keywords only last $M$ turns. The
heuristic is based on the assumption that the first query in a session is
always well-specified and that following queries belong to the second or the
ambiguous category.

Although HQE performs well in TREC CAsT 2019, it is not clear whether the
modeling assumptions, based on the characteristics of the CAsT training data,
are generalizable to real-world conversational search settings. In the next
section, we describe another category of query expansion methods that more
heavily utilize machine learning techniques.

####  3.5.2 Machine Learning Based Query Expansion Methods

Machine learning based query expansion methods tackle CQU of Equation 3.9 by
defining a binary term classification problem: for each term appearing in
dialog history $q\in\mathcal{H}_{i}$, decide whether to add it to the current
query $Q_{i}$. That is, $\mathcal{S}^{*}$ consists of all the terms selected
by a binary term classifier learned from training data [e.g., Voskarides et
al.,, 2020; Cao et al.,, 2008; Xiong and Callan,, 2015].

In what follows, we describe in detail the method of Query Resolution by Term
Classification (QuReTeC) [Voskarides et al.,, 2020] as an example. QuReTeC is
composed of two parts: a BERT-based binary classifier to predict whether to
add a term to the current query, and a distant supervision method of
constructing term-level labels to train the classifier.

Figure 3.7: (Left) The QuReTec model architecture. (Right) An example input
sequence and gold standard term labels (1: relevant, 0: non-relevant) for
QuReTeC, where the labels of <CLS>, <SEP> and the current turn terms are
masked out. Figure credit: Voskarides et al., [2020]

##### Term Classification.

QuReTeC uses a BERT-based classifier, as shown in Figure 3.7 (Left), which is
composed of three components: an input sequence, a BERT encoder, and a term
classification layer.

  1. 1.

The _input sequence_ consists of all the terms in dialog history
$\mathcal{H}_{i}$ and the current turn $Q_{i}$. A [CLS] token is added to the
beginning of the sequence, and a [SEP] token is added between the terms in
$\mathcal{H}_{i}$ and the terms in $Q_{i}$. Figure 3.7 (Right) shows an
example input sequence and the gold standard term labels.

  2. 2.

The _BERT encoder_ first represents the input terms with WordPiece embeddings
using a 30K vocabulary, and then applies multiple Transformer layers to output
a contextual representation (encoding vector) for each term.

  3. 3.

The _term classification layer_ , which consists of a dropout layer, a linear
layer and a sigmoid function, is applied on top of the contextual
representation of the first sub-token of each term to output a scalar for each
term, indicating how likely the term should be added to $\mathcal{S}^{*}$.

##### Generating Distance Supervision.

To train QuReTeC using the standard binary cross entropy loss, we need a
dataset containing a gold binary label for each $q\in\mathcal{H}_{i}$. Since
such labels are in general not available, we have to resort to distant
supervision methods [Mintz et al.,, 2009] to derive these labels from
document-level relevance labels, which are widely available, based on how a
term influences the document retrieval accuracy with respect to a query when
the term is used to expand the query [Cao et al.,, 2008].

Specifically for QuReTeC, given a query $Q_{i}$ and its labeled relevant
document set $\mathcal{D}^{+}$, each term in its dialog history
$q\in\mathcal{H}_{i}$ is labeled as position if $q$ appears in
$\mathcal{D}^{+}$ but not in $Q_{i}$.

Although the above procedure is noisy and can result in adding terms to
$Q_{i}$ that are non-relevant, or adding too few relevant terms $Q_{i}$,
Voskarides et al., [2020] report good performance on the TREC CAsT 2019
dataset, where the majority of expansion terms in the oracle manual de-
contextualized queries (see the example in Table 3.2) are indeed from the
previous query turns. However, it remains to be validated whether the
observation and good performance hold on other conversational search
benchmarks or in real-world scenarios.

####  3.5.3 Neural Query Rewriting

The query rewriting approach to CQU uses a neural natural language generation
(NLG) model to generate standalone query $\hat{Q}_{i}$, using the
conversational query $Q_{i}$ and its dialog history $\mathcal{H}_{i}$. In the
TREC CAsT setting, we have $\mathcal{H}_{i}=\\{Q_{1},...,Q_{i-1}\\}$. Thus,
the approach can be written as

$\displaystyle\\{Q_{1},...,Q_{i-1}\\},Q_{i}\xrightarrow{\text{NLG}(\theta)}\hat{Q}_{i},$
(3.12)

where the query rewriter $\text{NLG}(\theta)$ is often implemented using a
Transformer-based auto-regressive language model, parameterized by $\theta$.
For example, Vakulenko et al., [2021] propose to use a fine-tuned GPT-2 model
[Radford et al.,, 2019] for query rewriting as

$\displaystyle\hat{Q}_{i}$ $\displaystyle=\text{GPT-2}(\texttt{[CLS]}\circ
Q_{1}\circ\texttt{[SEP]}\circ
Q_{2};\texttt{[SEP]}....\texttt{[SEP]}Q_{i}\circ\texttt{[GO]}),$ (3.13)

where $\circ$ is the concatenation operator, the input sequence starts with a
[CLS] token and ends with a [GO] token, and the output standalone query
$\hat{Q}_{i}$ is generated token by token using a beam search decoder or a
greedy decoder.

Fine-tuning a pre-trained GPT-2 model for query rewriting requires large
amounts of gold query rewrites $\hat{Q}^{*}$ as training data. However, the
TREC CAsT datasets consists of only a few hundred manually generated query
rewrites, raising a concern that such a small amount of training data is
likely to lead to overfitting when used to fine-tune deep neural networks like
GPT-2. A common approach is to use the crowd sourced query rewrites in CANARD
[Elgohary et al.,, 2019] as additional training data. It has been reported
that the neural query writer based on fine-tuned GPT-2 is simple and
effective. It leads to one of the best performers in TREC CAsT 2019 [Dalton et
al.,, 2020] and later becomes a standard solution adopted by many participants
in TREC CAsT 2020 [Dalton et al.,, 2021]. The neural query rewriter is also
easy to be combined with other conversational query understanding methods
[e.g., Lin et al., 2020b, ] to achieve better IR results.

However, in real-world IR scenarios, large amounts of gold query writes are
not available. In what follows, we describe a method of training the neural
query rewriter in a few-shot learning setting.

##### Training Data Generation via Rules and Self-Supervised Learning

Yu et al., [2020] propose two methods, based on rules and self-supervised
learning, respectively, to generate weak-supervision data using large amounts
of ad hoc search sessions to fine-tune GPT-2 for conversational query
rewriting. Compared to conversational search session, ad hoc search sessions
are more available in large quantities as ad hoc search is more mature and the
applications are more widely deployed. As illustrated in Figure 3.8, ad hoc
search sessions can be viewed as pseudo target query rewrites
$\mathcal{\hat{H}}=\\{\hat{Q}_{1},...,\hat{Q}_{n}\\}$, and they can be
converted to conversation-like sessions
$\mathcal{{H}}=\\{{Q}_{1},...,{Q}_{n}\\}$ using a _query simplifier_. Then,
$(\mathcal{\hat{H}},\mathcal{H})$ pairs can serve as weak supervision to
approximate gold query rewrites for fine-tuning GPT-2 for query rewriting. The
query simplifier can be implemented using rule-based or machine learning
approaches.

Figure 3.8: A conversational search session (Left) and an ad hoc search
session (Right), adapted from Yu et al., [2020]

.

The rule-based approach uses two simple rules to mimic two ellipsis phenomena
in conversations, omission and coreference, to simplify query $\hat{Q}_{i}$
given its session context $\mathcal{\hat{H}}_{i}$ as follows:

  * •

Omission: A noun phrase is omitted if it occurs after a preposition and
appears in previous queries;

  * •

Coreference: previously appeared singular and plural noun phrases are
respectively replaced with pronouns.

The machine learning approach fine-tunes a pre-trained GPT-2 model for query
simplification using a handful manual query rewrites. The model works
similarly to the neural query rewriter of Equation 3.13, but generates $Q$
from $\hat{Q}$’s.

$\displaystyle{Q}_{i}$
$\displaystyle=\text{GPT-2}(\texttt{[CLS]}\circ\hat{Q}_{1}\circ\texttt{[SEP]}\circ\hat{Q}_{2}\circ\texttt{[SEP]}....\texttt{[SEP]}\hat{Q}_{i}\circ\texttt{[GO]}),$
(3.14)

The query simplifier can then be applied to the ad hoc search sessions (e.g.,
MS MARCO) to generate more conversation-like sessions. Yu et al., [2020] find
that it is easier to train a query simplifier (Equation 3.14) that learns to
omit information from an ad hoc query using session context than to train a
query rewriter (Equation 3.13) that learns to recover the omitted information.
Empirically, the weak-supervision data generated using the machine learning
approach significantly boosts the performance of the GPT-2 based query
rewriter on the TREC CAsT benchmarks.

###  3.6 Sparse Document Retrieval

The de-contextualized query produced by the CQU module (Section 3.5) can be
used as a standalone query to retrieve documents using any ad hoc retrieval
system. Depending on how queries (and documents) are represented, retrieval
systems can be grouped into two categories: _sparse retrieval_ systems that
use sparse vectors to represent queries (and documents), and _dense retrieval_
systems that use dense vector representations. Sparse retrieval is described
in this section, and dense retrieval the next section.

To retrieve a set of documents that are relevant to query $Q$ from document
collection $\mathcal{D}$, a sparse retrieval system first represents $Q$ and
each $D\in\mathcal{D}$ using sparse vectors, computes the relevance score
between query vector $\mathbf{q}$ and each document vector $\mathbf{d}$, and
then selects top-$K$ most relevant documents.

The most commonly used query and document vectors are based on bag-of-words
(BOW) representations,

$\displaystyle\mathbf{q}$ $\displaystyle=\\{(x,w)|\forall x\in Q\\}$ (3.15)
$\displaystyle\mathbf{d}$ $\displaystyle=\\{(x,w)|\forall x\in D\\},$ (3.16)

where $\mathbf{q}$ are $\mathbf{d}$ are high-dimensional sparse vectors, where
each dimension corresponds to a term $x$ in a pre-defined vocabulary, and the
term weight $w$ is none-zero only if the term appears in the query or
document. The term weight can be binary, term frequency counts, or machine
learned [Croft et al.,, 2010].

Then, the query-document relevance score can be computed using a retrieval
function, and top-$K$ relevant documents are returned. One of the most popular
retrieval functions is BM25 [Robertson and Zaragoza,, 2009]:

$\displaystyle\text{BM25}(Q,D)$ $\displaystyle=\sum_{x\in
Q}\text{TF}(x,Q)\text{IDF}(x,\mathcal{D})\cdot\frac{\text{TF}(x,D)\cdot(k_{1}+1)}{\text{TF}(x,D)+k_{1}\cdot(1-b+b\cdot\frac{|D|}{L})},$
(3.17)

where $k_{1}$ and $b$ are hyperparameters, and the function scores a query-
document pair using three sets of sufficient statistics:

  1. 1.

Term Frequency (TF) is the frequency of a term appearing in the query
$\text{TF}(x,Q)$ and the document $\text{TF}(x,D)$. The higher the TF, the
more important the term is.

  2. 2.

Invert Document Frequency (IDF) is the inverse of the fraction of documents in
$\mathcal{D}$ containing this term $\text{IDF}(x,\mathcal{D})$. The higher the
IDF, the more informative the term is.

  3. 3.

The ratio of the document length $|D|$ and the average document length $L$ in
$\mathcal{D}$ is used to normalize the TF-IDF score so that short documents
will score better than long documents given they both have the same number of
term matches.

BM25 is originally derived from the Binary Independence Model [Robertson and
Jones,, 1976], which assumes that terms are mutually independent so that the
relevance score of a query-document pair is a weighted combination of the
matching score of each query term with respect to the document. This allows
efficient document retrieval using data structures such as inverted index.
BM25 is also sometimes referred to as a _family_ of BOW scoring functions with
slightly different components and parameters. The function of Equation 3.17 is
one of the most prominent instantiations. We refer the readers to Croft et
al., [2010] for a comprehensive review of sparse retrieval and indexing
methods.

###  3.7 Dense Document Retrieval

Sparse retrieval methods are based on lexical matching. Although simple and
computationally efficient, lexical matching can be inaccurate due to the fact
that a concept is often expressed using different vocabularies and language
styles in documents and queries. For example, semantically similar words
(e.g., “automobile’ and “vehicle”) are not viewed as a match by BM25. In
addition, sparse retrieval functions, such as BM25, are not trainable, and
thus cannot leverage large amounts of search logs to improve retrieval
performance.

Dense retrieval methods can effectively address these issues. The use of dense
vector representations for retrieval has a long history since Latent Semantic
Analysis [Deerwester et al.,, 1990]. Recently, dense retrieval methods that
are based on deep learning models trained on labeled query-document pairs have
become popular [e.g., Huang et al.,, 2013; Shen et al.,, 2014; Karpukhin et
al.,, 2020]. This section describes the dual-encoder architecture which is
widely used for neural dense retrieval models (Section 3.7.1), how dense
retrieval models are applied efficiently to retrieve relevant documents over a
large document collection using approximate nearest neighbor search (Section
3.7.2), and the way dense retrieval models are trained using search logs
(Section 3.7.3).

####  3.7.1 The Dual-Encoder Architecture

Figure 3.9: The dual-encoder architecture of neural dense retrieval models.

The dual-encoder architecture of neural dense retrieval models [Huang et al.,,
2013; Shen et al.,, 2014; Karpukhin et al.,, 2020] is shown in Figure 3.9.

Dense retrieval works by using two neural encoders (e.g., a pair of fine-tuned
BERT models, as shown in Figure 3.5 (Right)). One, called document encoder
$\text{Enc}_{D}(;\theta_{D})$ parameterized by $\theta_{D}$, encodes document
$D$ into a dense vector $\mathbf{d}$. The other, called query encoder
$\text{Enc}_{Q}$, encodes query $Q$ into a dense vector $\mathbf{q}$. Using a
BERT encoder as an example, the input is the text sequence of $Q$ (or $D$),
appending the [CLS] token in the beginning of the input sequence, and the
output vector of [CLS] produced by BERT can be used as a dense vector
representation of $Q$ (or $D$).

Then, the relevance score of $D$ given $Q$ can be computed as similarity
between the two dense vectors,

$\displaystyle\text{Rel}(Q,D;\theta)$
$\displaystyle=\text{sim}(\mathbf{q},\mathbf{d})$ (3.18)
$\displaystyle=\text{sim}(\text{Enc}_{Q}(Q;\theta_{Q}),\text{Enc}_{D}(D;\theta_{D})),$

where the similarity function can be implemented using dot product, L2
distance, cosine similarity, etc.

During training, we feed query-document pairs into the model, and the model
parameters $\theta=\\{\theta_{Q},\theta_{D}\\}$ are optimized to maximize the
relevance score between a query and its relevant documents, as to be detailed
in Section 3.7.3.

At indexing time, all documents in the collection $\mathcal{D}$ need to be
encoded into dense vectors using $\text{Enc}_{D}$. The vectors are then stored
and indexed.

At runtime, only the input query needs to be encoded into $\mathbf{q}$ on the
fly using $\text{Enc}_{Q}$. Next, $\mathbf{q}$ is compared against the already
indexed document vectors, and top-$K$ most relevant documents, estimated using
Equation 3.18, are returned as the retrieval result.

Unlike sparser retrieval where efficient retrieval can be achieved using
inverted index, a dense retrieval process, which requires computing the
relevance score of the input query vector against every document vector
$\mathbf{d}\in\mathcal{D}$, could be prohibitively expensive for a large
document collection. Thus, efficient dense retrieval relies on specific
designs of indexing strategies, similarity search algorithms, and large-scale
computer infrastructures.

####  3.7.2 Approximate Nearest Neighbor Search

Formally, the nearest neighbor similarity search problem is defined as
follows. Given query vector $\mathbf{q}$ and the collection of $N$ document
vectors $\mathcal{D}=\\{\mathbf{d}_{1},...,\mathbf{d}_{N}\\}$, we search the
$K$ nearest neighbors of $\mathbf{q}$ in terms of a similarity (or distance)
function as

$\displaystyle
K\text{-argmax}_{\mathbf{d}\in\mathcal{D}}\text{sim}(\mathbf{q},\mathbf{d}).$
(3.19)

Approximate nearest neighbor (ANN) search relaxes the guarantee of exactness
for efficiency by vector compression and by only searching a subset of
$\mathcal{D}$ for each query. Searching a larger subset increases both
accuracy and latency. We review some commonly used ANN methods, following
closely the descriptions in Li et al., [2020]; Johnson et al., [2017].

###### Vector Compression.

The first source of approximation comes from compressed vectors. The most
popular vector compression methods includes binary codes [Gong et al.,, 2012;
He et al.,, 2013], and vector quantization methods [Jegou et al.,, 2010;
Paulevé et al.,, 2010]. These methods have the desirable property that
searching neighbors does not require reconstructing the vectors. For example,
in a vector quantization method, a vector is first reduced by principal
component analysis dimension reduction and then is subsequently quantized.
Although the process introduces similarity approximation error, it often
results in orders of magnitude of compression, significantly improving
efficiency in vector storage and similarity calculation.

Figure 3.10: Two state-of-the-art ANN indexing methods: the IVF index (Left)
and the (three-layer) HNSW index (Right). Figure credit: Li et al., [2020]

.

###### ANN Indices.

The second source of approximation comes from ANN indices that restrict the
distance evaluations to a subset of document vectors. Two state-of-the-art
methods are inverted file index (e.g., IVF [31]) and graph-based indexing
(e.g., HNSW [41]). As illustrated in Figure 3.10 (Left), the IVF index groups
document vectors into different clusters. When building the index, a list of
cluster centroids is learned via K-means clustering, and each document vector
is assigned to the cluster with the closest centroid. During searching, the
index first computes the similarity between the query and all cluster
centroids, then evaluates the document vectors belonging to the top-$p$
nearest clusters. A larger $p$ increases both accuracy (good) and search
latency (bad). Hierarchical Navigable Small World Graphs (HNSW) is a graph-
based indexing approach. As illustrated in Figure 3.10 (Right), HSNW includes
multiple layers of proximity graphs. The top layer contains a single node and
the base layer all document vectors. Each intermediate layer contains a subset
of document vectors covered by the next lower layer. During indexing, document
vectors are inserted one by one into multiple layers from the base layer up to
a certain layer determined by an exponentially decaying probability
distribution. At each insertion, the newly-inserted vector is connected to at
most a fixed number of nearest nodes previously inserted to the same graph to
create an approximate KNN-graph. In addition, nodes from different clusters
are selected to be connected to improve the global graph connectivity. At
runtime, given query $\mathbf{q}$, beam search is performed at each layer,
starting from the top layer, to identify nearest neighbor of $\mathbf{q}$
among the top-$p$ best candidate nodes in a coarse-to-fine manner. Like in
IVF, a larger $p$ increases accuracy and search latency.

###### When to Stop Search.

While state-of-the-art ANN approaches use fixed configurations that apply the
same termination condition (the size of subset to search) for all queries, Li
et al., [2020] point out that the number of dense vectors that need to be
searched to find top-$K$ nearest neighbors varies widely among queries, and
that the intermediate search result (after a certain amount of search steps)
provides important information for estimating how much more search should be
performed. To achieve a better trade-off between latency and accuracy, they
propose an approach that adaptively determines search termination conditions
for individual queries. A set of gradient boosting decision tree classifiers
are trained to predict when to stop searching. Applying these classifiers
achieves the same accuracy with much less total amount of search compared to
the fixed configurations.

###### Open-Source ANN libraries.

There are several open-source libraries that provide implementations for ANN
search. The most popular one is perhaps FAISS [Johnson et al.,, 2017]. It
contains algorithms that search in sets of vectors of any size, up to the ones
that possibly do not fit in RAM. FAISS is written in C++ with complete
wrappers for Python/numpy. Some of the most useful algorithms are implemented
on the GPU.

####  3.7.3 Model Training

Let $\theta=\\{\theta_{Q},\theta_{D}\\}$ be the parameters of the neural dense
retrieval model of Equation 3.18. $\theta$ is learned to identify the most
effective query and document representations for document retrieval. Consider
a query $Q$ and two candidate documents $D^{+}$ and $D^{-}$, where $D^{+}$ is
more relevant than $D^{1}$ to $Q$. Let $\text{Rel}(Q,D;\theta)$, as defined in
Equation 3.18, be the relevance score of $D$ given $Q$. We want to maximize
$\Delta=\text{Rel}(Q,D^{+};\theta)-\text{Rel}(Q,D^{-};\theta)$. We do so by
minimizing a smooth pair-wise rank loss [Huang et al.,, 2013] defined as

$\displaystyle\mathcal{L}(\Delta;\theta)$
$\displaystyle=\log(1+\exp(-\gamma\Delta)),$ (3.20)

where $\gamma$ is a scaling factor, or more commonly the margin-based loss
[Liu et al.,, 2009] defined as

$\displaystyle\mathcal{L}(\Delta;\theta)$
$\displaystyle=[\lambda-\Delta]_{+},$ (3.21)

where $[x]_{+}:=\max(0,x)$, and $\lambda$ is the margin hyperparameter.

The quality of the trained model depends on the quality and quantity of the
training data. One common approach is to collect weak relevance labels in
large quantities from search click logs. For example, Huang et al., [2013]
treat all the documents that have been clicked more than 5 times by users for
query $Q$ as its relevant (positive) documents $D^{+}$, and randomly sample a
set of documents from the document collection $\mathcal{D}$ as irrelevant
(negative) documents $D^{-}$. However, such randomly sampled $D^{-}$’s are
often so irrelevant to $Q$ (i.e., resulting in $\Delta\gg 0$ in Equations 3.20
and 3.21) that they do not provide useful information for model training
[Karpukhin et al.,, 2020]. Xiong et al., [2021] provides a theoretical
analysis on the impact of negative sampling for dense retrieval model training
using the variance reduction and negative sampling framework [Alain et al.,,
2015; Katharopoulos and Fleuret,, 2018]. The analysis shows that randomly
sampling negatives from $\mathcal{D}$ is unlikely an effective importance
sampling strategy and often yields inefficient learning or slow convergence.

One remedy to the problem is to sample _challenging_ negative documents that
have high ranking scores assigned by a sparse ranking model such as BM25
[Karpukhin et al.,, 2020; Ding et al.,, 2020]. The drawback of this approach
is that the training signals provided by the sparse model helps improve the
performance of the target dense retrieval model by forcing it to _mimic_ the
sparse model. Thus, the trained dense model is unlikely to suppress or
compensate the sparse model [Luan et al.,, 2020].

To address this drawback, Xiong et al., [2021] propose a self-training method
where the negative documents are sampled by the dense retrieval model being
optimized. Since the dense retrieval model is updated in each mini-batch, the
self-training follows an asynchronous iterative process [Guu et al.,, 2020],
where a set of GPUs are reserved to recalculate the dense vectors for the
documents in $\mathcal{D}$ using the document encoder trained in the last
iteration, and then update the ANN indices for negative sampling.

###  3.8 Conversational Dense Document Retrieval

The document retrieval modules, described in the last two sections, take as
input a standalone query $\hat{Q}$, which is rewritten from a conversational
query $Q$ given its dialog history $\mathcal{H}$ by the CQU module (Section
3.5). This _pipeline_ approach is appealing because we can re-use well-
developed ad hoc document retrieval models for conversational search. But the
drawback of this approach is that the CQU module cannot be optimized directly
for retrieval performance, e.g., using labeled query-document pairs, because
query rewriting is a discrete step which makes the gradient-based training
algorithms not applicable. Moreover, developing the CQU module independently
of the retrieval module requires gold query rewrites, which are much more
difficult to collect in large amounts than labeled query-document pairs which
can be obtained from search click logs.

This section describes conversational dense retrieval (ConvDR) models which
take conversational query $Q$ and its dialog history $\mathcal{H}$ as input,
and retrieve top-$K$ relevant documents without using a separate CQU module.
This _integrated_ approach is motivated by the fact that dense retrieval
models search relevant documents using a dense vector query, which can encode
both the query and its conversational context.

Qu et al., [2020] propose one of the first ConvDR models by extending the
dual-encoder-based dense retrieval model of Equation 3.18. Formally, at the
$i$-th turn, the ConvDR model retrieves top-$K$ relevant documents via

$\displaystyle
K\text{-argmax}_{\mathbf{d}\in\mathcal{D}}\text{sim}(\mathbf{q},\mathbf{d})$
(3.22)

where

$\displaystyle\mathbf{q}$
$\displaystyle=\text{Enc}_{\hat{Q}}(Q_{i},\mathcal{H}_{i};\theta_{\hat{Q}})$
(3.23) $\displaystyle\mathbf{d}$ $\displaystyle=\text{Enc}_{D}(D,\theta_{D}),$
(3.24)

Note that the query encoder encodes both $Q_{i}$ and $\mathcal{H}_{i}$ to
$\mathbf{q}$, taking the roles of both CQU and the ad hoc query encoder of
Equation 3.18. Therefore, the ConvDR model can be trained end-to-end to
directly optimize document retrieval performance on query-context-document
$(\\{Q,\mathcal{H}\\},D)$ pairs in the same way the ad hoc dense retrieval
model is trained, as described in Section 3.7.3.

Qu et al., [2020] show that with sufficient training data (i.e., query-
context-answer pairs), ConvDR significantly outperforms the pipeline approach
on the open-retrieval conversational QA (OR-QuAC) task.

However, unlike the case of ad hoc search where labeled query-document pairs
can be extracted from search click logs, conversational search logs are not
available in large quantities because conversational search engines have not
been widely deployed. Next, we will describe a method of training ConvDR
models in a few-shot learning setting.

####  3.8.1 ConvDR Model Trainining

Yu et al., 2021a  propose a few-shot learning method to train a ConvDR model
using the teacher-student knowledge distillation framework [Hinton et al.,,
2015], where the query encoder of ConvDR (student) learns to produce the
output of the query encoder of a well-trained ad hoc dense retrieval model
(teacher). Specifically, the method assumes that we have

  1. 1.

A few hundred gold query rewrites, $(\\{Q,\mathcal{H}\\},\hat{Q})$, where
$\hat{Q}$ is the standalone query, manually rewritten based on search query
$Q$ and its conversational context $\mathcal{H}$, as in the CANARD dataset
[Elgohary et al.,, 2019];

  2. 2.

A few labeled query-context-document pairs, $(\\{Q,\mathcal{H}\\},D^{+})$ (or
$(\\{Q,\mathcal{H}\\},D^{-})$), where $D^{+}$ (or $D^{-}$) is labeled as
relevant (irrelevant) to $Q$ and its conversational context $\mathcal{H}$; and

  3. 3.

A well-trained ad hoc dense retrieval model, e.g., ANCE [Xiong et al.,, 2021],
which uses the dual-encoder architecture.

The ANCE document encoder is used directly as the document encoder of ConvDR.
The query encoder of ConvDR, as in Equation 3.23, is trained using multi-task
learning, where the parameters $\theta_{\hat{Q}}$ are optimized by minimizing
a combination of two loss functions, one for each tasks.

$\displaystyle\mathcal{L}(\theta_{\hat{Q}})=\mathcal{L}_{\text{KD}}(\theta_{\hat{Q}})+\mathcal{L}_{\text{rank}}(\theta_{\hat{Q}})$
(3.25)

$\mathcal{L}_{\text{KD}}$ is the loss of the knowledge distillation (KD) task,
where $\text{Enc}_{\hat{Q}}$ (student) tries to mimic the ANCE query encoder
$\text{Enc}_{Q}^{\text{ANCE}}$ (teacher) as much as possible. The underlying
assumption is that since the information need behind the standalone query
$\hat{Q}$ is identical to that of the conversational query $Q$ in its dialog
context $\mathcal{H}$, their dense representations should be the same. This
can be achieved by minimizing the mean square error (MSE) between the produced
query representations. On a single training sample
$(\\{Q,\mathcal{H}\\},\hat{Q})$, $\mathcal{L}_{\text{KD}}$ is defined as

$\displaystyle\mathcal{L}_{\text{KD}}(\theta_{\hat{Q}}):=\text{MSE}\left(\text{Enc}_{\hat{Q}}(Q,\mathcal{H};\theta_{\hat{Q}}),\text{Enc}_{Q}^{\text{ANCE}}(\hat{Q})\right)$
(3.26)

The second task is the pair-wise ranking task as described in Section 3.7.3.
$\mathcal{L}_{\text{rank}}(\theta_{\hat{Q}})$ is the loss defined in Equation
3.20 or 3.21.

###  3.9 Document Ranking

As the retrieval module retrieves only a few hundred candidate documents from
a large document collection, the document ranking step can afford to use more
sophisticated models than those used for document retrieval to (re-)rank the
retrieved candidates.

A common approach to document ranking is to learn a ranking model
$f(Q,D;\theta)$, parameterized by $\theta$ and trained using relevance labels,
to score each retrieved candidate document $D$ with respect to input query
$Q$. The ranking model can be a feature-based statistical classifier such as
SVM [Joachims,, 2002] and Boosted Tree [Wu et al.,, 2010], or a neural network
model [Mitra et al.,, 2018]. Recently, ranking models based on pre-trained
language models (PLMs) have achieved SOTA on many IR benchmarks, and have
become the new standard solution to document ranking [Lin et al., 2020a, ]. In
what follows, we present a BERT-based document ranker as an example.

Nogueira and Cho, [2019] cast document ranking as a _pair prediction_ task
that predicts a document to be relevant or not for an input query, and fine-
tune a pre-trained BERT model using the pair prediction formulation, as
illustrated in Figure 3.5 (Middle). Specifically, we feed the concatenation of
query $Q$, a [SEP] token, and document $D$ to the ranker, and the relevance
label $y\in\\{1,0\\}$ is predicted using a logistic regression layer with
softmax as

$\displaystyle P_{r}(y|Q,D)=\text{softmax}(\mathbf{W}\cdot\mathbf{x}),$ (3.27)

where $\mathbf{x}$ is the contextual representation of the concatenated input
sequence (i.e., the contextual vector of the [CLS] token, produced by BERT),
and $\mathbf{W}$ is the parameter matrix of the logistic regression layer.

Note that while the BERT-based ranker uses the pair prediction formulation for
fine-tuning, the PLM-based dense retrievers described in Sections 3.7 and 3.8
use the dual-encoding formulation, as illustrated in Figure 3.5 (Right). The
different design choices are due to the efficient-effectiveness trade-off in
different settings.

The pair prediction formulation allows the model to explicitly capture the
term-level matches between $Q$ and $D$, as its self-attention mechanism of
BERT is applied on all pairs of query and document terms. The dual-encoder
model, however, has to compress all information of $Q$ or $D$ to two dense
vectors, respectively, and performs query-document matching at the document
(or query) level, which is coarser than the term-level matching. Mitra et al.,
[2018]; Xiong et al., [2017] report that the ranking models based on term-
level matching are more effective than the models based on document-level
matching for IR.

Although pair prediction models are widely used for document ranking due to
their effectiveness, they are not feasible for dense retrieval which requires
to score all the documents in a large document collection. Dual-encoder
models, on the other hand, are widely used for document retrieval due to their
efficiency. They allow all documents to be pre-encoded so that only the input
query needs to be encoded on the fly. Then the relevance scores can be
computed efficiently e.g., using dot product, and the retrieval is support by
efficient ANN algorithms.

##  Chapter 4 Query-Focused Multi-Document Summarization

Query-focused multi-document summarization (QMDS) aims at producing a concise
and fluent summary of a set of documents that are returned by the document
search module in response to a specific input query. QMDS is one of the key
components of the result generation module of a CIR system, as illustrated in
Figure 1.4.

Compared to classical automatic text summarization tasks (e.g., single-
document or multi-document summarization) which have been comprehensively
studied for decades [Mani and Maybury,, 1999], dating back to Luhn’s work at
IBM in the 1950’s [Luhn,, 1958], QMDS had received much less attention. Only
in the last 5 to 6 years, have we observed growing interests in QMDS research
driven by various CIR and conversational recommendation applications that are
being deployed on the devices with no or small screens (e.g., voice search and
mobile search) where a concise answer to a query is more desirable than a
traditional SERP.

This chapter is organized as follows. Section 4.1 introduces the QMDS task and
reviews public QMDS datasets. Section4.2 presents an overview of text
summarization methods, including extractive and abstractive methods, with or
without using neural network models. Extractive methods produce a summary by
concatenating sentences or paragraphs selected from the source documents.
Abstractive methods generate a concise summary that captures salient
information of the source documents. Section 4.3 describes neural approaches
to QMDS, based on extractive and abstractive neural models, respectively.
Section 4.4 discusses how we evaluate the factuality of the summaries
generated by abstractive summarizers.

###  4.1 Task and Datasets

Aiming to create a short summary from a set of documents that answers a
specific query [Dang,, 2005], QMDS is becoming imperative in various CIR and
recommendation scenarios (e.g., voice assistant and mobile search) where the
search result needs to be presented as a concise summary such that a user can
easily judge whether it contains the information she is looking for without
going over the long list of returned items, and decides what to do next, e.g.,
fetching the answer and closing the search session, issuing a more specific
query, or switching to a related topic. Unlike classical text summarization
which summarizes important information in the sources document(s), QMDS
generates a summary that highlights only the query-focused aspect of the
source documents, as illustrated by the example in Figure 4.1.

Figure 4.1: A QMDS sample from the QMDS-IR dataset [Pasunuru et al.,, 2021],
illustrating how a query-focused summary (gold summary) of a set of retrieved
documents help a user to answer her input query without going over the
individual documents. Figure Credit: Pasunuru et al., [2021].

Formally, the QMDS task in the context of CIR is defined as follows. Given
input query $Q$, dialog history $\mathcal{H}$, and a set of $N$ documents
$\mathcal{D}=\\{D_{1},...,D_{N}\\}$ retrieved by a conversational search
module based on $Q$ and $\mathcal{H}$, a QMDS model needs to generate a
summary $Y$ of $\mathcal{D}$ that answers $Q$.

A series of text summarization tasks have been evaluated in the Document
Understanding Conference (DUC). The _main_ and _update_ tasks evaluated in DUC
2007 111https://duc.nist.gov/duc2007/tasks.html#pilot, for example, are
conceptually identical to QMDS as defined above. The main task is, given query
$Q$ and a set of 25 relevant documents $\mathcal{D}$, to generate a 250-word
summary $Y$ of the documents that answers $Q$. The update task, in addition,
takes into account conversational context $\mathcal{H}$ when generating the
summary. The task is to produce short (100 words) multi-document update
summarizes $Y$ of newswire articles $\mathcal{D}$, regarding a given DUC topic
$Q$, under the assumption that the user has already read a set of earlier
articles included in $\mathcal{H}$. The purpose of each updated summary is to
inform the user of new information about the topic.

For a typical conversational search session, the main task corresponds to
summarizing the search result with respect to the first query whereas the
update task corresponds to summarizing the search results with respect to
follow-up queries.

To perform the evaluation, DUC organizers provides for each task a small test
set that is manually generated (e.g., 40 queries for the main task and 10
queries for the update task). The lack of large-scale high-quality dataset has
been the biggest hurdle to be overcome to advance the QMDS research.

Although it is challenging to collect QMDS data in large quantities e.g., by
mining Web search session logs, researchers have proposed various approaches
to generating _simulated_ QMDS datasets by leveraging existing document
collections and Web search APIs [e.g., Liu et al., 2018b, ; Pasunuru et al.,,
2021; Kulkarni et al.,, 2020, 2021; Zhao et al.,, 2021]. Below, we review, as
examples, three such datasets that are publicly available.

###### WikiSum.

This dataset consists of approximately 2.2 M $(Q,\mathcal{D},Y)$ triples [Liu
et al., 2018b, ], and is developed based on a subset of English Wikipedia
articles. The authors view Wikipedia as a collection of summaries on various
topics or queries given by their title, e.g., “Canada” or “Artificial
Intelligence”, and the source documents to be summarized can be viewed as all
reputable documents on the Web or books. Thus, each $(Q,\mathcal{D},Y)$ in
WikiSum is constructed using a Wikipedia article as follows. $Q$ is the title
of the article, $\mathcal{D}$ is a collection of non-Wikipedia reference
documents, and $Y$ is the first section, or lead, of the Wikipedia article,
conditioned on reference text. WikiSum has been used in several QMAD studies.
Although WikiSum is a simulated QMAS dataset and the results on WikiSum have
to be taken with a grain of salt since neither the queries nor the summaries
are natural [Pasunuru et al.,, 2021], the dataset is among the most widely
used ones for QMAS research.

###### QMDS-CNN.

This dataset consists of approximately 312K $(Q,\mathcal{D},Y)$ triples
[Pasunuru et al.,, 2021], and is developed using the CNN / Daily Mail (DM)
dataset which is commonly used for single-document summarization [Hermann et
al.,, 2015]. Each $(Q,\mathcal{D},Y)$ triple is generated from a news article.
$Q$ is the title of the article, $Y$ is the single-document summary of the
article provided in the original CNN/DM dataset. $\mathcal{D}$ consists of
documents generated using two methods. First, each news article is chunked
into around 20 small paragraphs, and each paragraph is treated as
$D\in\mathcal{D}$ if it is part of the news article. Second, a BM25 search
engine is used to retrieve for each query (or title) top-4 paragraphs from all
the paragraphs that do not belong to the news article. The authors argue that
QMDS-CNN is a better dataset for QMDS research than WikiSum because (1)
summaries are of high-quality because they are manually generated, and are
query-focused since they reflect the title; and (2) each summary contains
information from multiple documents by design. The only main downsize is that
the queries are not real but simulated by titles. The simulation might not be
desirable since titles are generated by the authors who also create the
documents while queries are issued by users who have no idea about the
documents.

###### QMDS-IR

This dataset consists of queries issued by real search engine users, thus
addressing the problem of WikiSum and QMDS-CNN. The dataset consists of 102K
$(Q,\mathcal{D},Y)$ triples, and each is constructed as follows [Pasunuru et
al.,, 2021]. First, queries that have natural language answers returned and
clicked by users are randomly sampled from Bing search logs in the United
States. Second, for each query $Q$, we collect its top-10 ranked documents
returned by the Bing search engine. The Bing QA system also generates for each
returned document an answer passage. Third, one document is randomly picked
among the top-10 documents, and its answer passage is used as summary $Y$, and
the rest 9 documents form $\mathcal{D}$. The QMDS task on this dataset is to
recover the query-focused answer passage using the other 9 documents retrieved
by the search engine. To the best of our knowledge, the task defined on QMDS-
IR is by far the closest approximation to the QMDS scenario in CIR. A sample
of $(Q,\mathcal{D},Y)$ from this dataset is shown in Figure 4.1.

###  4.2 An Overview of Text Summarization Methods

Radev et al., [2002] define a summary as “a text that is produced from one or
more texts, that conveys important information in the original text(s), and
that is no longer than half of the original text(s) and usually, significantly
less than that.” Text summarization is the task of producing a concise and
fluent summary while preserving key information content and overall meaning of
the original documents. It has been applied in a wide range of applications,
taking different forms. For example, QMAD is a special form of the task where
search engines generate summaries (or snippets) as the preview of the
documents retrieved to answer a specific user query [Gao et al., 2020c, ].

In general, there are two approaches to text summarization: _extraction_ and
_abstraction_. Extractive summarization methods produce summaries by choosing
a subset of the sentences in the original document(s). This contrasts with
abstractive summarization methods, where the information in the text is
rephrased.

####  4.2.1 Extractive Summarizers

The extractive approach has been dominating the field due to its simplicity
and effectiveness. In a recent survey, Allahyari et al., [2017] point out that
most extractive summarizers take three steps to generate a summary: sentence
representation, scoring and selection.

##### Sentence Representation

Each sentence in $\mathcal{D}$ is represented as a feature vector. A classical
approach is to use the BOW (Bag-Of-Words) representation, where each element
in the vector corresponds to a topic word in a pre-defined vocabulary, and the
value of the element is the weight of the topic word assigned using a scoring
model, such as TF-IDF, BM25, log-likelihood ratio, and so on. The feature
vector can be enriched by incorporating indicative information such as
sentence length and position in the document. In neural approaches, the
feature vector is produced using sentence encoders implemented using various
neural network models. For example, Cheng and Lapata, [2016] employ a
recurrent neural network (RNN) or a convolutional neural network (CNN) to
encode the words in a sentence to obtain a vector representation of the
sentence. Liu and Lapata, 2019b  utilize pre-trained language models (e.g.,
BERT) to encode sentences. A recent survey on this topic is Gao et al., 2020c
.

##### Sentence Scoring

Each sentence is assigned an importance score, indicating how well the
sentence represents the main idea of the original documents. This can be
achieved by first encoding the document(s) using a vector, and then computing
the cosine similarity between the sentence vector and the document vector as
the importance score. Document encoding can be achieved by either aggregating
the vectors of all the sentences in the document, or simply treating the
document as a long sentence and applying the same sentence encoder. More
advanced methods also take into account inter-sentence dependencies and the
discourse structure of documents [Erkan and Radev,, 2004], and introduce
machine learning methods to estimate the scores on training data. We will
present an example in detail in the next section.

##### Summary Sentence Selection

The summarizer needs to select a subset of sentences to form the summary,
subject to a pre-set length limit. A naïve method uses a greedy algorithm to
select top-$K$ most important sentences. But this might lead to high
redundancy, i.e., a set of important but similar sentences is selected.

A better strategy is to consider both the importance and novelty of a
sentence. A classic implementation of the strategy is the MMR (maximal
marginal relevance) method [Carbonell and Goldstein,, 1998]. At each
iteration, MMR selects one sentence from $\mathcal{D}$ and includes it in the
summary $Y$ until a length limit is reached. The selected sentence $S_{i}$ is
the most important one among the remaining sentences and it has the least
content overlap with the current summary. As in Equation 4.1 below,
$\mathrm{sim1}(S_{i},\mathcal{D})$ measures the similarity of the sentence
$S_{i}$ to the documents, indicating the sentence importance. $\max_{S_{j}\in
Y}\mathrm{sim2}(S_{i},S_{j})$ measures the maximum similarity of the sentence
$S_{i}$ to each of the summary sentences, acting as a proxy of redundancy.
$\lambda$ is a balancing factor.

$\mathrm{MMR}\triangleq\arg\max_{S_{i}\in\mathcal{D}\backslash
Y}\left[\lambda\mathrm{sim1}(S_{i},\mathcal{D})-(1-\lambda)\max_{S_{j}\in
Y}\mathrm{sim2}(S_{i},S_{j})\right]$ (4.1)

####  4.2.2 Abstractive Summarizers

Compared to the extractive approach where a summary is constructed using
extracted sentences, abstractive summarizers paraphrase the idea of the
original documents in a new form, and have a potential to generate more
concise and coherent summaries. However, developing effective abstractive
summarizers is harder since we have to deal with problems, like semantic
representation, inference and natural language generation, which are
considered more challenging than sentence extraction. Therefore, early
abstractive methods underperform extractive methods, and often rely on an
extractive pre-processor to produce the abstract of text [Berg-Kirkpatrick et
al.,, 2011; Knight and Marcu,, 2000].

Recently, the abstractive approach is getting more attentions in the research
community by applying modern neural language models, such as feed-forward
language models (FFLMs) [e.g., Rush et al.,, 2015], recurrent neural networks
(RNNs) [e.g., Nallapati et al.,, 2016; Chopra et al.,, 2016] and Transformers
[e.g., Liu et al., 2018b, ; Liu and Lapata, 2019a, ], to generate summaries
conditioned on source documents.

##### FFLMs

Rush et al., [2015] present the first widely used neural abstractive
summarizer. The summarizer utilizes a beam search algorithm to generate a
summary word-by-word based on an attend-based feed-forward neural language
model as

$\displaystyle P_{r}(y_{i+1}|\mathbf{Y}_{C},\mathcal{D};\theta)$
$\displaystyle\propto\exp{(\mathbf{Vh}+\mathbf{W}\cdot\text{Enc}(\mathbf{Y}_{C},\mathcal{D}))},$
(4.2) $\displaystyle\mathbf{h}$
$\displaystyle=\tanh\left(\mathbf{U}[\mathbf{E}\mathbf{y}_{i-C_{1}},...,\mathbf{E}\mathbf{y}_{i}]\right),$

where $y_{i+1}$ is next summary word to be predicted, $\mathcal{D}$ is the set
of the source documents, $\mathbf{Y}_{C}\triangleq\mathbf{y}_{[i-C+1,...,i]}$
is a sequence of indicator vectors that represent the $C$ generated summary
words immediately before $y_{i+1}$.

The model is parameterized as a standard feed-forward neural network language
model [Bengio et al.,, 2003] with an additional contextual encoder Enc. The
model parameters are $\theta=(\mathbf{E},\mathbf{U},\mathbf{V},\mathbf{W})$
where $\mathbf{E}\in\mathbb{R}^{D\times V}$ is a word embedding matrix,
$\mathbf{U}\in\mathbb{R}^{(CD)\times H}$, $\mathbf{V}\in\mathbb{R}^{V\times
H}$, $\mathbf{W}\in\mathbb{R}^{V\times H}$ are weight matrices, $4\times D$ is
the size of the word embeddings, and $\mathbf{h}$ is a hidden layer of size
$H$. The contextual encoder Enc returns a vector of size $H$ representing
$(\mathbf{Y}_{C},\mathcal{D})$. Enc can be implemented using any sentence
encoders developed for extractive summarizers as described in Section 4.2.1.
Rush et al., [2015] shows that an attention-based encoder works the best.

##### RNNs

Nallapati et al., [2016] and Chopra et al., [2016] have independently
developed the first set of neural abstractive summarizers implemented using
attentional encoder-decoder RNNs (or sequence-to-sequence models), which are
originally developed for machine translation [Bahdanau et al.,, 2015;
Sutskever et al.,, 2014]. In these summarizers, a RNN decoder generates a
summary of input $\mathcal{D}$ which is encoded by an attention-based encoder
to ensure that the decoder focuses on the appropriate input words at each step
of generation:

$P_{r}(Y|\mathcal{D})=\prod_{i=1}^{N}P_{r}(y_{i}|y_{1},...,y_{i-1},\mathcal{D};\theta).$
(4.3)

Nallapati et al., [2016] propose three novel modeling techniques to address
the unique challenges of text summarization. First, a feature-rich encoder is
developed to identify key concepts and entities that are crucial to capture
the main idea and content of the source documents. As illustrated in Figure
4.2 (Left), in addition to word embeddings, the encoder captures rich
linguistic features, including parts-of-speech (POS) tags, named-entity (NE)
tags, and TF and IDF statistics of words.

The second is the use of a switching generator-pointer decoder to allow the
summarizer to generate OOV words, such as named entities that are unseen in
training data. As illustrated in Figure 4.2 (Middle), the decoder is equipped
with a switch that decides between using the generator (G) or a point (P) for
each summary word to be generated. If the switch is on, the word is in the
vocabulary and can be produced by the generator as usual. Otherwise, the
decoder generates a pointer to a word-position in the source documents, and
the word at that position is copied into the summary.

Third, a hierarchical attention mechanism is utilized to identify both
keywords and key sentences in source documents that are important to generate
the summary. As illustrated in Figure 4.2 (Right), the attention mechanism
operates at the word level and sentence level, and the word-level attention
scores are re-weighted by the corresponding sentence-level attention scores,
implying that the importance of a word increases if it also occurs in an
important sentence.

Combining all these techniques, Nallapati et al., [2016] show that the
encoder-decoder RNNs significantly outperform the model of Rush et al., [2015]
on the DUC benchmark.

Figure 4.2: Three RNN models for abstractive summarization [Nallapati et al.,,
2016]. (Left) A feature-rich encoder captures rich linguistic features of
source documents, including parts-of-speech (POS) tags, named-entity (NE)
tags, and TF and IDF statistics of words. (Middle) A switching generator-
pointer decoder can generates OOV words, such as named entities that are
unseen in training data. When the switch shows ‘G’, the traditional generator
is used to produce a word, and when it shows ‘P’, the pointer network is
activated to copy the word from one of the source document positions. (Right)
A hierarchical encoder with hierarchical attention identifies both keywords
and key sentences in source documents that are important to generate the
summary. The attention weights at the word level, represented by the dashed
arrows are re-weighted by the corresponding sentence level attention weights,
represented by the dotted arrows.

##### Transformers

Liu et al., 2018b ; Liu and Lapata, 2019a  propose an abstractive multi-
document summarizer, which also uses the encoder-decoder architecture, but
based on a multi-layer Transformer model [Vaswani et al.,, 2017]. The
effectiveness of the summarizer is validated empirically on the WikiSum
dataset.

As illustrated in Figure 4.3 (Left), the summarizer consists of four
components: the document embedding layer, local Transformer layer, global
transformer layer, and decoder.

###### Document Embedding Layer.

Each token in each document is mapped to a vector. Unlike RNNs, Transformer
does not retain sequence information of input, thus a position embedding
vector is needed for each word in input. For multi-document summarization,
each token has two positions, the rank of the document the token occurs and
the position of the token in the document.

###### Local Transformer Layer.

The vanilla Transformer layer [Vaswani et al.,, 2017] is used to encode
contextual information for tokens within each document.

###### Global Transformer Layer.

This layer encodes the inter-document context information. As shown in Figure
4.3 (Right), first, a multi-head pooling operation is applied to each
paragraph (or document). Different heads encode paragraphs with different
attention weights. Then, for each head, an inter-paragraph attention mechanism
is applied to collect for each paragraph its dependencies on other paragraphs
by self-attention, generating an inter-document context vector. Finally, these
context vectors are concatenated, linearly transformed, added to the vector of
each token, and fed to a feed-forward layer, updating the representation of
each token with global information.

###### Decoder.

A vanilla Transformer is utilized to generate a summary token by token while
attending to the source input. Beam search and a length penalty are used in
the decoding process to generate fluent and short summaries.

Figure 4.3: A hierarchical Transformer for abstractive multi-document
summarization [Liu and Lapata, 2019a, ]. (Left) The summarizer consists of
four components: the document embedding layer, local Transformer layer, global
transformer layer, and decoder. Figure credit: Pasunuru et al., [2021].
(Right) A global transformer layer. Different colors indicate different heads
in multi-head pooling and inter-paragraph attention. Figure credit: Liu and
Lapata, 2019a .

There are many other works on abstractive summarization. We name a few here.
Abstractive summarizers are known to generate fluent summaries but be weak in
retaining the main idea of source documents. Therefore, many researchers try
to introduce a content selection mechanism so that the summary is generated
conditioned on only the most important content selected. Zhou et al., [2017]
extend the sequence-to-sequence framework with a selective mechanism that
allows the decoder to generate a summary based on a selective portion of the
source documents that is the most important to retain the main idea.
Similarly, Chen and Bansal, [2018] propose an abstractive summarizer that
first selects salient sentences and then rewrites them abstractively (via
compression and paraphrasing) to generate a concise summary. Gehrmann et al.,
[2018] propose a data-efficient content selector to over-select phrases in a
source document that should be part of the summary. The selector is used in a
bottom-up attention step to constrain the model to using only the most likely
phrases.

See et al., [2017] propose a hybrid pointer-generator network that can copy
words from the source text via pointing, which aids accurate reproduction of
information, while retaining the ability to produce novel words through the
generator. This work is a significant extension to Nallapati et al., [2016]
shown in Figure 4.2 (Middle) since the mixture of copy mechanism and the
language model is used to generate all summary words, not just the OOV words.

Celikyilmaz et al., [2018] present deep communicating agents, which use an
encoder-decoder architecture, to address the challenges of representing a long
text (e.g., a concatenation of multiple documents) for abstractive
summarization. The task of encoding a long text is divided across multiple
collaborating encoders (agents), each encoding a subsection of the input text.
These encoders are connected to a single decoder, trained end-to-end using
reinforcement learning to generate a focused and coherent summary.

###  4.3 QMDS Methods

QMDS methods can be grouped into two categories, extractive and abstractive
methods, which are the extensions of extractive and abstractive text
summarizers, respectively, as described in Section 4.2.

####  4.3.1 Extractive Methods

Extractive QMDS methods extend the extractive approach described in Section
4.2.1. Most of these methods also take three steps to generate a summary:
sentence representation, scoring and selection. The main difference is that in
each step the input query $Q$, in addition to source document set
$\mathcal{D}$, is also considered.

##### Sentence Representation

We can simply treat query $Q$ as a document, and then use the same methods of
Section 4.2.1 to represent each sentence, including the sentences in $Q$, as a
feature vector.

##### Sentence Scoring

The importance of each sentence $S$ in $\mathcal{D}$ depends on how relevant
$S$ is to query $Q$, $\text{sim1}(S,Q)$ and how well $S$ represents the main
idea of $\mathcal{D}$, $\mathrm{sim2}(S,\mathcal{D})$ as

$\mathrm{sim}(S,(Q,\mathcal{D}))\triangleq\mu\mathrm{sim1}(S,Q)+(1-\mu)\mathrm{sim2}(S,\mathcal{D})$
(4.4)

where $\mu\in(0,1)$ controls the extent to which query relevance information
influences sentence importance.

To take into account the inter-sentence dependencies and the discourse
structure of documents, many extractive summarizers [e.g. Wan,, 2008; Xu and
Lapata,, 2020] use the well-known LexRank algorithm [Erkan and Radev,, 2004]
to compute sentence importance based on the concept of eigenvector centrality
in a graph representation of sentences. LexRank builds for $\mathcal{D}$ a
graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where nodes $\mathcal{V}$ are
sentences in $\mathcal{D}$, $\mathcal{E}$ are undirected edges and are
weighted according to matrix $\mathbf{E}$, where each element
$\mathbf{E}_{i,j}$ is the transition probability from vertex $i$ to $j$.
Similar to Equation 4.4, $\mathbf{E}_{i,j}$ needs to take into account both
the inter-sentence similarity and the relevance to $Q$, and can be computed as

$\displaystyle\mathbf{E}_{i,j}=\mu P_{r}(S_{i},Q)+(1-\mu)P_{r}(S_{i},S_{j})$
(4.5) $\displaystyle P_{r}(S_{i},Q)\propto\mathrm{sim1}(S_{i},Q)$
$\displaystyle P_{r}(S_{i},S_{j})\propto\mathrm{sim2}(S_{i},S_{j}).$

The importance of each node is computed using random walk on $\mathcal{G}$.
Specifically, a Markov chain is run with $\mathcal{E}$ on $\mathcal{G}$ until
it converges to stationary distribution

$\mathbf{p}=\mathbf{E}^{\top}\mathbf{p},$ (4.6)

where each element of eigenvector $\mathbf{p}$ denotes the importance of a
sentence.

##### Summary Sentence Selection

The summary can be constructed by selecting sentences from $\mathcal{D}$ based
on their importance and novelty scores, similar to the MMR method of Equation
4.1, where for QMDS $\mathrm{sim1}(.)$ is replaced by
$\mathrm{sim}(S,(Q,\mathcal{D}))$ of Equation 4.4 or the elements of
$\mathbf{p}$ in Equation 4.6.

##### Coarse-to-Fine QMDS

Unlike traditional text summarization tasks where $\mathcal{D}$ is pre-
selected, in QMDS the size and number of source documents in $\mathcal{D}$ can
be very large, depending on the retrieval result of an input query. Therefore,
encoding all sentences in $\mathcal{D}$ to generate a summary can be so
computationally expensive as to lead to a noticeable delay in system
responses, thus hurting the user experience of human-machine interactions
during conversational information retrieval.

Xu and Lapata, [2020] propose a coarse-to-fine QMDS modeling framework to
address the challenge. As shown in Figure 4.4(b), the approach employs
progressively more accurate modules for estimating whether a sentence is
relevant to a query (relevance estimator), likely to contain answers to the
query (evidence estimator), and should be included in the summary (centrality
estimator). The authors argue that compared to classic methods where all
sentences are encoded and scored simultaneously (Figure 4.4(a)), the coarse-
to-fine approach is more efficient, especially for highly interactive CIR
scenarios, since at each step the model processes a decreasing number of
sentences and the computational cost does not increase with the size of the
original input $\mathcal{D}$.

Another advantage of this approach is that the modules (i.e., estimators) can
be independently developed by leveraging training data if available. For
example, estimating the relationship between the query and the candidate
sentences can be formulated as an extractive QA task (to be described in
Section 5.1), which aims to detect the answer span for a query from a set of
pre-selected sentences [Yao et al.,, 2013; Yang et al.,, 2015] or text
passages [Rajpurkar et al.,, 2018; Nguyen et al.,, 2016]. Thus, the evidence
estimator can be trained by leveraging distant supervision signals from
existing QA datasets, including WikiQA [Yang et al.,, 2015], TrecQA [Yao et
al.,, 2013] and SQuAD 2.0 [Rajpurkar et al.,, 2018].

Figure 4.4: Classic (a) and coarse-to-fine modeling framework for QMDS [Xu and
Lapata,, 2020]. The classic methods score all sentences in source documents
simultaneously. The coarse-to-fine approach employs progressively more
accurate modules for estimating whether a sentence is relevant to a query
(relevance estimator), likely to contain answers to the query (evidence
estimator), and should included in the summary (centrality estimator). The
blue circles indicate a coarse-to-fine estimation process from source
documents to final summaries where modules gradually discard sentences. Figure
credit: Xu and Lapata, [2020].

####  4.3.2 Abstractive Methods

Abstractive QMDS methods are the extensions of the abstractive summarizers
described in Section 4.2.2 to address two challenges of QMDS: how to
efficiently encode document set $\mathcal{D}$, and how to incorporate query
$Q$ for summary generation.

Since the amount of text in $\mathcal{D}$ can be very large as discussed
earlier, it is infeasible to train an end-to-end abstractive model given the
memory constraints of current hardware and latency constraints of interactive
CIR scenarios. Therefore, a two-stage approach is often used. As illustrated
in Figure 4.5, in the first stage, a subset of $\mathcal{D}$ is coarsely
selected using an extractive summarizer, such as the ones described in Section
4.3.1; and in the second stage, an abstractive summarizer (e.g., based on
encoder-decoder models) generates the target summary conditioning on the
extraction (e.g., the $L^{\prime}$-best paragraphs). This two-stage process
simulates how humans summarize multiple long documents: first highlight
pertinent information, and then conditionally generate the summary based on
the highlights.

Figure 4.5: The two-stage method of query-focused multi-document
summarization. $L$ source paragraphs (documents) are first ranked and the
$L^{\prime}$-best ones serve as input to an abstractive summarizer (i.e., an
encoder-decoder model) which generates the target summary. Figure credit: Liu
and Lapata, 2019a .

A simple method of incorporating $Q$ for summary generation is to append $Q$
to the top-ranked document before sending it to the encoder of an abstractive
summarizer, such as the hierarchical Transformer-based summarizer illustrated
in Figure 4.3, which is referred to as _baseline summarizer_ below. However,
some recent studies show that it is beneficial to treat $Q$ differently from
$D\in\mathcal{D}$.

As an example, we describe the HEROSumm (HiErarchical queRy focused Order-
aware multi-document) model [Pasunuru et al.,, 2021] which extends the
baseline summarizer [Liu and Lapata, 2019a, ]. Like the baseline summarizer,
HEROSumm uses a encoder-decoder architecture based on a hierarchical
Transformer model. HEROSumm differs from the baseline in that the former
introduces two new components in its encoder modules to incorporate $Q$ for
summary generation: a query encoder, and a document ordering component that
ranks documents in $\mathcal{D}$ based on their relevance to $Q$. The encoder
of HEROSumm is illustrated in Figure 4.6. HEROSumm consists of the following
components.

Figure 4.6: The HEROSumm encoder [Pasunuru et al.,, 2021], which extends of
the encoder of the baseline summarizer [Liu and Lapata, 2019a, ] by
introducing two components to incorporate query for summary generation: a
query Transformer layer for query encoding and a document ordering component
for ranking documents based on their relevance to query. Figure credit:
Pasunuru et al., [2021].

###### Document Embedding Layer.

Each token in each document is mapped to a vector. Compared to the baseline
summarizer, the only difference is that the position embedding vector of each
word encodes only the position of the token in the document while the rank of
the document is randomly assigned and will be updated by the document ordering
component.

###### Document Ordering Component.

The self-attention mechanism is used to compute the relevance (attention)
score $R_{i}$ between query and each document $D_{i}\in\mathcal{D}$,
indicating how much information in $D_{i}$ needs to be take into account when
generating the summary. $R$ is encoded in the position embedding vector as

$\displaystyle\mathrm{PE}_{D_{i},2j}$
$\displaystyle=\sin{(R_{i}/1000^{2j/d_{model}})}$ (4.7)
$\displaystyle\mathrm{PE}_{D_{i},2j+1}$
$\displaystyle=\cos{(R_{i}/1000^{2j/d_{model}})}$

where $\mathrm{PE}(D_{i},2j)$ is the $i$-th dimensional position embedding of
$D_{i}$, and $d_{model}$ is the size of model’s hidden layers. The position
encoding is inserted in the last layer of the HEROSumm encoder, as illustrated
in Figure 4.6.

###### Local Transformer Layer.

Like the baseline summarizer, the vanilla Transformer layer [Vaswani et al.,,
2017] is used to encode intra-document contextual information for tokens
within each document.

###### Global Transformer Layer.

Like the baseline summarizer, this layer encodes the inter-document contextual
information, as illustrated in Figure 4.3 (Right).

###### Query Transformer Layer.

This layer sits between the local and global Transformer layers, as
illustrated in Figure 4.6 (with an enlarged view provided on the right of the
figure). It encodes two query-context vectors. One captures dependencies
between the input query and tokens within each document. The other captures
dependencies between the query and each document (or paragraph) in
$\mathcal{D}$. Finally, these query-context vectors, together with the intra-
and intern-document context vectors, are fed to the decoder to generate a
summary.

###### Decoder.

The decoder of HEROSumm uses a standard decoder Transformer [Vaswani et al.,,
2017], as that in the baseline summarizer. There are studies of improving the
decoder using the idea of MMR to avoid generating repeated phrases and
increase the query-relevance and diversity of summaries. For example, Nema et
al., [2017] propose a neural-based Seq2Seq framework which ensures that
context vectors in attention mechanism are orthogonal to each other.
Specifically, to alleviate the problem of repeating phrases in the summary,
successive context vectors are treated as a sequence and a modified LSTM cell
is used to compute the new state at each decoding time step. In decoding
steps, the attention mechanism is used to focus on different portions of the
query at different time steps.

###  4.4 Factuality Metrics for Summarization Evaluation

Automatic evaluation of summarizers, especially the abstractive summarizers,
is challenging [Kryściński et al.,, 2019]. A common approach is to collect for
each test case multiple human generated summaries as references, then measure
the $N$-gram overlap between the machine-generated summaries and the
references using metrics such as ROUGE [Lin,, 2004]. However, this approach
fails to evaluate the factuality of machine-generated summaries. According to
Kryściński et al., [2019], 30% of summaries generated by abstractive
summarizers contain factual inconsistencies, caused by distorted or fabricated
facts about the source documents, as illustrated by the example in Figure 4.7.

Figure 4.7: Example of a factually incorrect summary generated by an
abstractive summarizer. (Top) Source document. (Bottom) Model-generated
summary. Figure credit: Kryściński et al., [2019].

Developing factuality metrics for evaluating abstractive summarizers and other
text generation models becomes an increasingly important topic. Recently
proposed factuality metrics can be grouped into two categories, based on proxy
evaluation tasks and extracted facts, respectively.

The first category uses proxy evaluation tasks, such as question answering
(QA), and a masked token prediction cloze task. Given $(\mathcal{D},Y)$ where
$Y$ is a model-generated summary of $\mathcal{D}$, the QA-based metrics assign
a quality score to $Y$ by measuring how accurate, in terms of
precision/recall/F-score, a QA system can answer questions generated from
$\mathcal{D}$ based on $Y$, or vice versa. For example, the SummaQA metric
[Scialom et al.,, 2019] answers questions derived from $\mathcal{D}$ based on
$Y$, whereas the FEQA metric [Durmus et al.,, 2020] answers questions from $Y$
based on $\mathcal{D}$. The cloze-based metrics assign the quality of a
summarizer by measuring the performance boost gained by a pre-trained language
model with access to its generated summaries while performing the token
prediction task on the source documents [Vasilyev et al.,, 2020]. As
illustrated by the two examples in Figure 4.8, the BLANC-help metric (Left) is
defined by the difference in accuracy of two reconstructions of masked tokens:
with summary versus filler concatenated in front of the sentence with masked
tokens, where the model input is a summary (or filler) and sentence with
masked (grey) tokens, and the output is the unmasked tokens. The BLANC-tune
metric (Right) is defined by the difference in accuracy of two reconstructions
of masked tokens: with model tuned on the summary versus with the original
model, where both models are given the same input consisting of a sentence and
its masked (grey) tokens, and each model outputs the unmasked tokens.

Figure 4.8: Two cloze-based metrics for evaluating the factuality of model-
generated summaries [Vasilyev et al.,, 2020]. (Left) BLANC-help is defined by
the difference in accuracy of two reconstructions of masked tokens: with
summary vs. filler concatenated in front of the sentence with masked tokens.
The model input is a summary (or filler) + sentence with masked (grey) tokens.
The output is the unmasked tokens. (Right) BLANC-tune is defined by the
difference in accuracy of two reconstructions of masked tokens: with model
tuned on the summary vs. with the original model. Both models are given the
same input: a sentence with masked (grey) tokens. Each model outputs the
unmasked tokens. Figure credit: Vasilyev et al., [2020].

The second category extracts facts from the source documents or the reference
summaries, and compute how much a machine-generated summary contains
consistent facts. For example, Zhang, [2019] proposes to adopt information
extraction tools, such as OpenIE, to extract two sets of facts from a machine-
generated summary and its references, respectively, and check the consistency
of the two sets by computing their semantic relevance score, precision, recall
and F1-score. In Chang et al., [2021], salient keywords (facts) are extracted
manually from the source documents as a by-product of generating the reference
answers. The factuality of a machine-generated answer is scored by recall,
i.e., how many salient keywords are contained in the generated answer.

Despite these efforts, evaluating the quality of machine-generated text
remains an open research topic. A recent comparative study of factuality
evaluation metrics is Gabriel et al., [2020]. A recent survey of evaluation
methods of natural language generation systems is Celikyilmaz et al., [2020].

##  Chapter 5 Conversational Machine Comprehension

This chapter discusses neural approaches to conversational machine
comprehension (CMC). A CMC module, which is often referred to as _reader_ ,
generates a direct answer to a user query based on query-relevant documents
retrieved by the document search module (Chapter 3). It is a component of the
result generation module of a CIR system, as shown in Figure 1.4

Equipped with CMC, a CIR system can be used as a conversational open-domain
question answering (QA) system. Compared to a (conversational) document search
system, a QA system is much easier to use in mobile devices in that they
provide concise, direct answers to user queries, as opposed to be a list of
document links. To simplify the terminology, a QA engine and a machine
comprehension module (or a reader) are exchangeable terms in this chapter.

This chapter starts with an introduction to the CMC task (Section 5.1). Using
the CoQA [Reddy et al.,, 2019] and QuAC [Choi et al.,, 2018] benchmarks as
examples, we discuss the dialog features, such as topic shift, drill down,
clarification, which the CMC module needs to handle. Then, we describe two
categories of machine comprehension models, known as _extractive_ and
_generative_ readers, originally developed for sing-turn QA tasks. While
extractive readers (Section 5.2) select a text span in the retrieved documents
as the answer to the user query, generative readers (Section 5.3) can generate
answer strings which might not be contained in the retrieved documents. These
two types of readers can be combined to produce better QA results (Section
5.4). We then examine approaches to extending these readers to use
conversational context for CMC (Section 5.5).

###  5.1 Task and Datasets

Machine comprehension (MC) tasks defined in the research community can be
categorized along two dimensions. Depending on how the answers are produced,
MC tasks can be (1) _extractive_ , where answer is a text span in the given
documents (or passages), such as the SQuAD task (Figure 5.1 (Left)) [Rajpurkar
et al.,, 2016], and (2) _abstractive_ , where the answer is free-form and
needs to be synthesized from the given passages, such as the MS MARCO
benchmark (Figure 5.1 (Left)) [Nguyen et al.,, 2016]. Depending on whether
conversational context is used, MC tasks can be _single-turn_ , such as SQuAD
and MS MARCO, or _conversational_ , such as CoQA and QuAC (Figure 5.2).

Figure 5.1: The examples from two types of MC task. (Left) An extractive QA
example in the SQuAD dataset, adapted from Rajpurkar et al., [2016]. Each of
the answers is a text span in the passage. (Right) An abstractive QA example
in the MS MARCO dataset, adapted from Nguyen et al., [2016]. The answer, if
there is one, is synthesized from the given passages. Figure 5.2: The examples
from two conversational QA datasets. (Left) A QA dialogue example in the QuAC
dataset. The student, who does not see the passage (section text), asks
questions. The teacher provides answers in the form of text spans and dialogue
acts. These acts include (1) whether the student should $\hookrightarrow$,
could $\bar{\hookrightarrow}$, or should not $\not\hookrightarrow$ ask a
follow-up; (2) affirmation (Yes / No), and, when appropriate, (3) No answer.
Figure credit: Choi et al., [2018]. (Right) A QA dialogue example in the CoQA
dataset. Each dialogue turn contains a question ($\text{Q}_{i}$), an answer
($\text{A}_{i}$) and a rationale ($\text{R}_{i}$) that supports the answer.
Figure credit: Reddy et al., [2018].

Without loss of generality, the CMC task is defined as follows. Given an input
question $Q$, a set of passages $\mathcal{P}$ (which are retrieved by the
document search module with respect to $Q$ in CIR), and dialog history
$\mathcal{H}$, the CMC reader needs to produce the answer $A$ to $Q$.

Figure 5.2 (Left) shows an information seeking QA dialog in the QuAC dataset.
The conversation is student-driven and centered around a short evidence
passage. The student, who does not see the passage, asks questions. The
teacher provides answers in the form of text spans and dialog acts. These acts
include

  * •

Whether the student should, could, or should not ask a follow-up question,

  * •

Yes/No affirmation, and when appropriate,

  * •

No answer.

Figure 5.2 (Right) shows an example conversational QA session in CoQA. It is a
conversation between two humans who are reading a passage. One is acting as a
questioner and the other an answerer. Answering every question, except the
first one, depends on the dialog history. For example, “she” in Q2 refers to
the entity “Jessica” in A1. To ensure the naturalness of answers in a
conversation, the answers are not restricted to text spans in the given
passage (as in an extractive QA task) but are free-form text. For evaluation,
the dataset provides for each answer a text span from the passage as a
rationale to the answer. For instance, the answer to Q4 (how many) is “Three”
which is not a text span while its rationale spans across multiple sentences.

For both datasets, the main evaluation metric is macro-average F1 score of
word overlap between the prediction and the references, after removing
stopwords.

Yatskar, [2018] studies the dialog behaviors and abstractive behaviors of the
CoQA and QuAC datasets, and summarizes the unique challenges that CMC models
need to handle. There are five dialog behaviors:

  1. 1.

Topic Shift: A question about something discussed in the dialog history (e.g.,
“Q: how does he try to take over?… Q: where do they live?”).

  2. 2.

Drill Down: A request for more information about a topic being discussed
(e.g., “A: the Sherpas call Mount Everest Chomolungma. Q: is Mt. Everest a
holy site for them?”).

  3. 3.

Topic Return: Asking about a topic again after it had been shifted away from.

  4. 4.

Clarification: Reformulating a question that had previously been asked.

  5. 5.

Definition: Asking what is meant by a term.

Yatstar finds that although the topic shift and drill down behaviors are well
represented in both datasets, neither dataset has a significant number of
returns to previous topics, clarifications, or definitional interactions.
Therefore, the community needs a more representative CMC dataset.

Yatakar also observes that abstractive answers are necessary for the following
cases in the two datasets.

  1. 1.

Yes/No: Questions whose answers are “yes” or “no”.

  2. 2.

Coref: Co-reference is added to previously mentioned entities in either
context or question (e.g., “Q: how was France’s economy in the late 2000’s? A:
it entered the recession.”)

  3. 3.

Count: Counting how many entities of some type were mentioned.

  4. 4.

Fluency: Adding a preposition, changing the form of a word, or merging two
non-contiguous spans (e.g., “Q: how did he get away? A: _by_ foot.”)

Beside Yes/No questions, QuAC contains no other abstractive phenomena while
CoQA contains only a small number of predominately insertions, often at the
beginning of an extracted answer span, for co-reference or other fluency
improvements. Therefore, state-of-the-art extractive readers can be trivially
adapted to both tasks, as we will detail later. Therefore, the community needs
a more representative abstractive QA dataset.

In addition to CoQA and QuAC, we list below four related public benchmarks
that provide complementary features regarding dialog and abstractive
behaviors.

###### QBLink [Elgohary et al.,, 2018].

QBLink is a dataset for sequential question answering where the questioner
asks multiple related questions about the same concept one-by-one. After each
question, the answerer provides an answer before the next question is asked.
The dataset is designed to evaluate the ability of question-answering systems
to leverage the additional context in the form of a history of previously
asked questions and answers. The dataset consists of 18,644 sequences (56,000
question-answer pairs). Each sequence starts with a lead-in that defines the
topic of the questions, followed up three questions and answers.

###### Qulac [Aliannejadi et al.,, 2019].

This is the first dataset dedicated for clarifying questions in an IR setting.
The dataset is built on top of the TREC Web Track 2009-2012 dataset and
consists of 10K QA pairs for 198 topics with 762 facets. Each topic is coupled
with a facet. Thus, the same question would receive a different answer based
on user’s information need (facet).

###### Natural Questions (NQ) [Kwiatkowski et al.,, 2019].

Although NQ is a single-turn QA dataset, it is the among the most popular
large-scale datasets for developing any end-to-end open-domain QA system which
consists of the document search module and the machine comprehension module.

###### TriviaQA [Joshi et al.,, 2017].

Like NQ, TriviaQA is a single-turn QA dataset widely used for developing open-
domain QA systems. It contains trivia question-answer pairs that were scraped
from the web. Different from NQ, the questions in TriviaQA are written with
known answers in mind. TriviaQA is known to be challenging because it contains
complex and compositional questions which require cross-sentence reasoning to
find answers.

###  5.2 Extractive Readers

This section describes neural machine comprehension readers for single-turn
extractive MC. The next two sections describe how these readers are extended
to abstractive MC and conversational MC, respectively.

Extractive MC can be cast as a classification problem. Given a question
$Q=\\{q_{1},...,q_{I}\\}$ and a (set of) passage(s) $P=\\{p_{1},...,p_{J}\\}$,
the reader needs to classify each passage word as start, end, or outside of
the answer span, and pick the most probable span as the answer.

A typical architecture of neural MC models for single-turn extractive MC
consists of two modules. The first is a question-passage encoder. The output
of the encoder is a sequence of integrated context vectors, each for one
passage word, encoding information of its word embedding, passage context and
question context. The second module is an answer predictor. It takes the
integrated context vectors as input, predicts for each word its probabilities
of being the start or the end of the answer span, respectively, and picks the
most probable span.

Early extractive readers commonly use sequence models (such as Recurrent
Neural Networks) with attention for their encoders. After the Transformer
[Vaswani et al.,, 2017] is proposed and widely used to develop pre-trained
language models (such as BERT [Devlin et al.,, 2018]), the extractive readers
that use pre-trained Transformer models as encoders become state of the art.
In what follows, we use two examples to illustrate how these extractive
readers are implemented. The first is the Bi-Directional Attention Flow
(BiDAF) model [Seo et al.,, 2016], which is one of the most popular baseline
readers that use sequence models as encoders. The second is the state-of-the-
art extractive reader based on BERT [Devlin et al.,, 2018].

####  5.2.1 BiDAF

BiDAF first encodes the input question $Q$ and passage $P$ into a set of
integrated context vectors $\mathbf{M}$ using three components (i.e., lexicon
embedding, context encoding, and question-passage integrated encoding), and
then predicts the answer span based on $\mathbf{M}$, as illustrated in Figure
5.3.

Figure 5.3: The Bi-Directional Attention Flow model for extractive QA, adapted
from Seo et al., [2016].

###### Lexicon Embedding.

This component extracts information from a question of length $I$,
$Q=\\{q_{1},...,q_{I}\\}$, and a passage of length $J$,
$P=\\{p_{1},...,p_{J}\\}$, at the word level and normalizes for lexical
variants. It typically maps each word to a dense vector using a pre-trained
word embedding model, such as word2vec [Mikolov et al.,, 2013] or GloVe
[Pennington et al.,, 2014], such that semantically similar words are mapped to
the vectors that are close to each other in neural space. Word embedding can
be enhanced by concatenating each word embedding vector with other linguistic
embeddings such as those derived from Part-Of-Speech (POS) tags, and named
entities etc. To tackle the out-of-vocabulary problem, character-level word
representations or sub-word representations are used, such as CharCNN [Kim et
al.,, 2016], FastText [Bojanowski et al.,, 2017], Byte-Pair Encoding (BPE)
[Sennrich et al.,, 2016] and WordPiece [Wu et al.,, 2016]. Given $Q$ and $P$,
the word embeddings for the tokens in $Q$ is a matrix
$\mathbf{E}^{Q}\in\mathbb{R}^{d\times I}$ and tokens in $P$ is
$\mathbf{E}^{P}\in\mathbb{R}^{d\times J}$, where $d$ is the dimension of the
word embedding vectors.

###### Context Encoding.

This component uses contextual cues from surrounding words to refine the word
embeddings. As a result, the same word maps to different vectors in a neural
space depending on its context, such as “bank” in “bank of a river” vs. “bank
of American”. Context encoding is typically achieved by using Recurrent Neural
Networks (RNNs). As shown in Figure 5.3, BiDAF uses two Long Short-Term Memory
(LSTM) networks in both directions (i.e., left-to-right and right-to-left),
respectively, and concatenate the outputs of the two LSTMs to obtain a matrix
$\mathbf{C}^{Q}\in\mathbb{R}^{2d\times I}$ as the contextual representation of
$Q$, and a matrix $\mathbf{C}^{P}\in\mathbb{R}^{2d\times J}$ as the contextual
representation of $P$.

###### Question-Passage Integrated Encoding.

This component couples the question and passage vectors and produces the
integrated contextual matrix $\mathbf{M}$, which consists of a set of
question-aware feature vectors, one for each passage word, over which the
answer span is predicted. The integration is achieved by summarizing
information from both $\mathbf{C}^{Q}$ and $\mathbf{C}^{P}$ via the
_attention_ process as follows:

  1. 1.

Compute an attention score, which signifies relevance of question words to
each passage word:
$s_{ij}=\text{sim}(\mathbf{c}_{i}^{Q},\mathbf{c}_{j}^{P};\theta_{s})\in\mathbb{R}$
for each $\mathbf{c}_{i}^{Q}$ in $\mathbf{C}^{Q}$, where
$\text{sim}(;{\theta_{s}})$ is the similarity function e.g., a bilinear model,
parameterized by $\theta_{s}$.

  2. 2.

Compute the normalized attention weights through softmax:
$\alpha_{ij}=\exp{(s_{ij})}/\sum_{k}\exp{(s_{kj})}$.

  3. 3.

Summarize information for each passage word via
$\mathbf{\hat{c}}_{j}^{P}=\sum_{i}\alpha_{ij}\mathbf{c}_{i}^{Q}$ to obtain a
matrix $\mathbf{\hat{C}}_{P}\in\mathbb{R}^{2d\times J}$ as the question-aware
representation of $P$.

BiDAF computes attentions in two directions: from passage to question
$\mathbf{\hat{C}}^{Q}$ as well as from question to passage
$\mathbf{\hat{C}}^{P}$. Then, BiDAF generates $\mathbf{M}$ by first
concatenating three matrices $\mathbf{C}^{P}$, $\mathbf{\hat{C}}^{P}$ and
$\mathbf{\hat{C}}^{Q}$, and then using a bidirectional LSTM to encode for each
word its contextual information with respect to the passage and question.

###### Answer Span Prediction.

The probability distribution of the start index over the entire passage is
obtained by a logistic regression with softmax:

$P_{r}^{(start)}(j)=\text{softmax}(\mathbf{W}^{(start)}\mathbf{M}_{:j}),$
(5.1)

where $\mathbf{M}_{:j}$ is the $j$-th column vector (corresponding to the
$j$-th passage word), $\mathbf{W}^{(start)}$ is the parameter matrix.
Similarly, the probability distribution of the end index over the entire
passage is computed as

$P_{r}^{(end)}(j)=\text{softmax}(\mathbf{W}^{(end)}\mathbf{M}_{:j}).$ (5.2)

The probability of an answer span $(i,j)$ is

$P_{r}^{span}(i,j)=P_{r}^{start}(i)P_{r}^{end}(j).$ (5.3)

###### Training.

The training loss is defined as the sum of the negative log probabilities of
the true start and end indices by the predicted distributions, averaged over
all training samples:

$\mathcal{L}(\theta)=-\frac{1}{|\mathcal{D}|}\sum_{n=1}^{|\mathcal{D}|}\left(\log\left({P_{r}^{(start)}}(y^{(start)}_{n})\right)+\log\left({P_{r}^{(end)}}(y^{(end)}_{n})\right)\right),$
(5.4)

where $\theta$ is the set of trainable model parameters, $\mathcal{D}$ is the
training set, $y^{(start)}_{n}$ and $y^{(end)}_{n}$ are the true start and end
of the answer span of the $n$-th training sample, respectively.

####  5.2.2 BERT-Based Readers

Most of the state-of-the-art extractive readers use a Transformer-based pre-
trained language model, such as BERT [Devlin et al.,, 2018] and its variants
like RoBERTa [Liu et al., 2019c, ] and DeBERTa [He et al.,, 2020], as the
encoder.

Figure 5.4: The BERT-based reader for extractive MC, adapted from Devlin et
al., [2018].

As illustrated in Figure 5.4, a BERT-based reader takes the word embeddings
(or, more preciously, sub-word embeddings such as WordPiece) of the
concatenated question-passage sequence as input, and uses the build-in
attention mechanism of the Transformer to compute for every word in question
and passage an attention score to encode the influence each word has on
another. In the output of the encoder, each word in passage is represented
using an integrated contextual vector that incorporates contextual information
from other passage words and question words. These integrated contextual
vectors are then fed into a logistic regression layer with softmax for answer
span prediction as Equations 5.1 to 5.3.

The build-in attention mechanism of the Transformer is described in detail in
Section 3.3 and Figure 3.2, following Vaswani et al., [2017].

###### Training.

BERT-based readers are trained in two stages. In the first stage, the BERT
encoder is pre-trained on large amounts of raw text data by predicting masked
words conditioned on their context. The learning is self-supervised and does
not need any labels. Hugging Face111https://huggingface.co maintains a rich
repository of pre-trained language models (PLMs), including the BERT models
and their variants, which are developed for various NLP tasks. However, these
PLMs are trained on general-domain text corpora (e.g., Web). If the target
domain is dramatically different from general domain, we might consider
adapting a general-domain PLM using in-domain data by continual pre-training
the PLM. For domains with abundant unlabeled text, such as biomedicine, pre-
training domain-specific language models from scratch might also be a good
choice [Gu et al.,, 2020]. In the second stage, the answer span predictor is
added on top of the BERT encoder, following the single or pair prediction
formulation as illustrated in Figure 3.5, and both the encoder and the answer
predictor are fine-tuned using the MC training data.

###  5.3 Generative Readers

While an extractive reader extracts contiguous spans from the retrieved
passages as the answer, generative readers sequentially decode the answer
string which might not be contained in the retrieved passages. A typical
generative reader is implemented as a sequence-to-sequence model that
generates answer $A$ conditioned on retrieved a (set of) passage(s) $P$ and
question $Q$.

We describe the Fusion-In-Decoder (FID) model [Izacard and Grave,, 2020] as an
example. FID is developed for open-domain QA, and is based on a pre-trained
sequence-to-sequence model, T5 [Raffel et al.,, 2019]. As illustrated in
Figure 5.5, given question $Q$ and a set of $N$ retrieved passages
$\mathcal{P}=\\{P_{1},...,P_{N}\\}$, the encoder, which is similar to what is
described in Section 5.2, encodes each $(Q,P_{n})$ pair independently, and
produces an integrated contextual vector representation for each token,
$\mathbf{m}^{n}_{j}$ for the $j$-th token of the $n$-th pair. The decoder then
performs attention over the concatenation of the representations of all the
retrieved passages, and generate the answer string.

Figure 5.5: The Fusion-In-Decoder (FID) model. Figure credit: Izacard and
Grave, [2020]

Let $\\{Q,\mathcal{P}\\}$ denote the input of the question and all retrieved
passage, and $A=\\{a_{1},...,a_{K}\\}$ the answer string consisting of $K$
tokens. The generative reader is trained to minimize a sequence-to-sequence
loss for a given $(\\{Q,\mathcal{P}\\},A)$,

$\mathcal{L}(\\{Q,\mathcal{P}\\},A;\theta)=-\sum_{k}^{K}\log
P_{r}(a_{k}|\\{Q,\mathcal{P}\\},a_{1:k-1};\theta),$ (5.5)

where $\theta$ is the model parameter. During inference, a greedy decoding can
be used to produce the answer.

FID differs from other generative readers [e.g., Min et al.,, 2020; Lewis et
al.,, 2020] in that it processes passages independently in the encoder but
jointly in the decoder. As pointed out by Izacard and Grave, [2020], the
computational cost of FID grows linearly with the number of passages, instead
of quadratically since the encoder of FID only performs self-attention over
one context at a time. On the other hand, conditioning on all passage
encodings jointly allows the decoder to effectively aggregate evidence from
multiple passages.

###  5.4 Hybrid Readers

Since extractive and generative readers adopt different answer inference
strategies, a hybrid extractive-generative reader can be a better option for
open-domain QA. Cheng et al., [2021] show that answers produced by those two
types of reader are complementary to each other. Thus, they propose a simple
ensemble approach, known as UnitedQA, for combining the predictions from
extractive and generative readers. Denote the predicted answer strings from
$M$ extractive and $N$ generative readers as $A^{E}_{1},...,A^{E}_{M}$ and
$A^{G}_{1},...,A^{G}_{N}$, respectively. The hybrid prediction $A^{*}$ is
obtained by

$\displaystyle
A^{*}=\arg\max_{A\in\mathcal{A}}\tau\sum_{m=1}^{M}\mathbbm{1}(A,A^{E}_{m})+\delta\sum_{n=1}^{N}\mathbbm{1}(A,A^{G}_{n}),$
(5.6)

where $\mathcal{A}$ is the set of all predicted strings,
$\mathbbm{1}(A,A^{\prime})$ is an indicator function and $\tau=0.6$,
$\delta=0.4$. UnitedQA sets new state-of-the-art on two representative open-
domain QA benchmarks, NaturalQuestions and TriviaQA, when the paper is
published.

###  5.5 Conversational Machine Comprehension Readers

The Conversational Machine Comprehension (CMC) readers that we discuss in this
section are developed on the CoQA and QuQA datasets. A recent literature
review of CMC readers is Gupta et al., [2020].

Since some important dialog features, such as topic return, clarification,
definition, are not well-represented in the two datasets, as discussed in
Section 5.1, these CMC readers are designed primarily to answer the input
(current) question based on the given passage and dialog history, but not to
take other types of system actions such as recommending a new topic or asking
clarifying questions. Thus, these CMC readers do not use a dialog policy for
system action selection. In Chapter 6, we will describe how a conversational
knowledge base QA module learns a dialog policy to select system actions.

Specifically, the CMC task on the CoQA and QuQA datasets is defined as
follows. Given a passage $P$ and dialog history
$\mathcal{H}=\\{H_{1},...,H_{N-1}\\}$ where each dialog turn is a question-
answer pair: $H_{n}=(Q_{n},A_{n})$, the CMC reader needs to generate answer
$A_{N}$ to input question $Q_{N}$.

Compared to the single-turn readers described in Sections 5.2 and 5.3, CMC
readers need to make use of dialog history $\mathcal{H}$, in addition to $P$,
to answer the input question. Dialog history is useful because the answer to
$Q_{N}$ often depends on the previous answers and questions in the same dialog
session, as demonstrated in the dialog behaviors of drill down and topic
return, and because ellipsis phenomena are frequently encountered in dialog
sessions (e.g., in Figure 5.2 (Right), ”she” in Q2 refers to ”Jessica” in A1).

CMC readers extend single-turn readers by adding a history selection module to
select a subset of $\mathcal{H}$ that are useful to answer the input question,
and by extending the encoding module to encode not only the passage and input
question, but also the (selected) dialog history. The answer module (i.e., the
answer predictor of an extractive reader, or the answer decoder of a
generative reader) remains the same.

####  5.5.1 History Selection

There are two reasons for selecting a subset of history rather than using the
whole history for CMC. The first is due to computational cost. A dialog
history can be arbitrarily long. Encoding a long history is computationally
expensive. For example, many Transformer-based readers (such as BERT-based
readers) take a word sequence up to 512 tokens as input. The second reason is
that not all dialog turns in the history are useful for answering the input
question. As the topics of conversation are likely to shift, it is more
desirable to base the answer to be generated on the relevant subset of the
history.

Many CMC readers use heuristics to select dialog history. Ju et al., [2019];
Choi et al., [2018]; Yatskar, [2018] simply truncate the history to retain the
$M$ immediate turns based on a pre-defined length limit. Zhu et al., [2018];
Ohsugi et al., [2019] use the last two turns based on their empirical study
which shows that including more turns does not improve performance.

The history attention mechanism (HAM) [Qu et al.,, 2019] is among a very few
methods that take a model-based approach to selecting history on-the-fly based
on the input question. HAM is motivated by the observation that previous
dialog turns in a dialog session are of different importance for answering the
input question, and the importance does not necessarily depend on their
relative position. As illustrated in the example in Figure 5.6, while Q2, Q4,
Q5 and Q6 are closely related to their immediate previous turns, Q7 is related
to a remote question Q1, and Q3 does not follow Q2 but shifts to a new topic.
The HAM module computes for each turn in dialog history a weight based on how
useful it is for answering the input question. Then, the history used for
generating the answer to the input question is represented as a weighted sum
of the vector representations of previous dialog turns.

Figure 5.6: An example of a conversational question answering session from
QuAC [Choi et al.,, 2018]. Q2, Q4, Q5 and Q6 are closely related to their
immediate previous turns. Q7 is related to a remote question Q1. Q3 does not
follow Q2 but shifts to a new topic. Figure credit: Qu et al., [2019]

####  5.5.2 History Encoding

The methods of encoding history for CMC can be grouped into two categories.
The first category of methods simply append the selected history to the input
question, thus converting the CMC problem into a single-turn MC problem [e.g.,
Ju et al.,, 2019; Zhu et al.,, 2018]. There are some variants where history is
first encoded into feature vectors before being appended. For example, Choi et
al., [2018] augment BiDAF to encode dialog context from previous $M$ QA pairs
as follows. First, the input question embedding is extended by appending a
feature vector that encodes dialog turn number. Then, the passage embedding is
extended by appending a feature vector that encodes the locations of the
previous answer spans.

The second category uses the FLOW-based approach [e.g., Huang et al.,, 2018;
Yeh and Chen,, 2019; Chen et al., 2019b, ]. The FLOW mechanism is proposed to
incorporate intermediate representations generated during the process of
answering previous questions. Compared to the approaches that simply append
previous QA pairs to the input question as input, FLOW integrates the latent
semantics of dialog history more deeply. The first FLOW-based CMC reader,
called FlowQA [Huang et al.,, 2018], achieves state of the art on CoQA and
QuAC when it is published.

FLOW is designed to capture how a dialog flows, which can be illustrated using
the example in Figure 5.7. As the conversation progresses, the topic being
discussed changes over time. The answer to the same question varies depending
on the current topic. For example, the answer to the question “what did he
feel” is “lonely” when the topic being discussed is the author’s father’s
funeral. But the answer becomes “we saved each other” when the dialog flows to
a different topic regarding five years after the death of the author’s father.
Thus, modeling how a dialog flows is crucial to the performance of a CMC
reader.

Figure 5.7: An illustration of the conversation flow. As the current topic
changes over time, the answer to the same question changes accordingly. Figure
credit: Huang et al., [2018]

Huang et al., [2018] define FLOW as a sequence of latent topic representations
computed based on question-passage context. Take the BiDAF model as an
example, such topic representations are the integrated contextual vectors of
dialog turns. A naïve implementation of FLOW is to read the context in order
and process the dialog turns sequentially, then pass the output hidden vectors
from each integration layer during the $(M-1)$-th dialog turn to the
corresponding integration layer for $Q_{M}$. This process is highly
nonparallel. Thus, training a CMC reader on large amounts of training dialogs
can be prohibitively expensive.

Huang et al., [2018] propose the Integration Flow (IF) mechanism to improve
the training efficiency. As illustrated in Figure 5.8 (Left), an IF layer
performs reasoning in parallel for each question, and then refines the
reasoning results across different dialog turns. Given the input question and
previous questions, each represented using their integrated contextual
vectors, the IF layer generates a history-aware integrated contextual vector
for each passage word using a LSTM. So, the entire integrated contextual
vectors for answering previous questions can be used to answer the input
question. As illustrated in Figure 5.8 (Right), FlowQA employs multiple IF
layers on top of contextual encoding, inter-weaved with attention (first on
question, then on context itself), to generate the history-aware integrated
contextual vectors. The answer is predicted on the integrated context vectors.

Figure 5.8: The integration flow (IF) mechanism and the architecture of
FlowQA. (Left) The IF layer performs reasoning in parallel for each question.
(Right) FlowQA employs multiple IF layers on top of the context encoding,
inter-weaved with attention (first on question, then on context itself), to
generate the history-aware integrated contextual vectors. Figure credit: Huang
et al., [2018]

There have been extensions of FlowQA, achieving even better results. We
present two examples below. FlowDelta [Yeh and Chen,, 2019] explicitly models
the information gain through the dialog flow in order to allow the CMC reader
to focus on more informative cues, as illustrated in Figure 5.9.

Figure 5.9: Illustration of the flow information gain modeled by the FlowDelta
mechanism. Figure credit: Yeh and Chen, [2019].

Chen et al., 2019b  argue that FlowQA is not quite natural since it does not
mimic how humans perform reasoning. Using IF layers, FlowQA first processes
sequentially in passage, in parallel of question turns and then processes
sequentially in question turns, in parallel of passage words. However, humans
typically do not first perform reasoning in parallel for each question, and
then refine the reasoning results across different turns. Doing so is sub-
optimal because the results of previous reasoning processes are not
incorporated into the current reasoning process. Therefore, Chen et al., 2019b
propose an improved FLOW-based CMC reader, GraphFLOW, that captures dialog
flow using a graph neural network. GraphFlow dynamically constructs a
question-specific context graph from passage text at each turn, then models
the temporal dependencies in the sequence of context graphs.

The FLOW mechanism is originally proposed for sequence-model-based readers. It
also inspires the development of several BERT-based CMC readers that use the
integrated context vectors of dialog history for answer prediction. Ohsugi et
al., [2019] use BERT to encode for each question and answer a contextual
representation (i.e., a sequence of vectors) conditioned on the passage. As
illustrated in Figure 5.10, given a history consisting of $K$ QA pairs and the
input question, there are $2K+1$ resultant contextual representations. Then, a
bidirectional RNN model runs over the concatenation of the these vector
sequences for answer span prediction.

Figure 5.10: A CMC reader that uses BERT to encode dialog history. Figure
credit: Ohsugi et al., [2019].

Qu et al., [2019] propose a BERT-based CMC reader that uses HAM to select and
encode dialog history context in three steps. In the first step, each dialog
turn in dialog history, together with the passage and the input question, is
encoded into a context vector using BERT. For example, we can construct for
each dialog turn an instance sequence, which is a concatenation of the token
[CLS], dialog turn $H$, input query $Q$ and passage $P$. We feed the instance
into BERT, and take the output representation of [CLS] as the integrated
contextual vector of the instance, denoted by $\mathbf{h}$. Let
$\mathbf{h}_{k}(k=1,...,K)$ be the integrated contextual vector of the
instance constructed using dialog turn $H_{k}$. Note that the instance for
$H_{K}$ is simply the input question $Q$. In the second step, a single-layer
feed-forward network is used to compute the weight of each dialog turn with
respect to the input question as

$\alpha_{k}=\text{softmax}(\mathbf{W}\cdot\mathbf{h}_{k}),$ (5.7)

where $\mathbf{W}$ is the projection matrix. In the third step, dialog history
is incorporated into the input-question-passage integrated contextual vector
$\mathbf{h}_{K}$ via history attention to form the history-aware integrated
contextual vector $\hat{\mathbf{h}}_{K}$ as

$\hat{\mathbf{h}}_{k}=\sum_{k=1...K}\alpha_{k}\mathbf{h}_{k}.$ (5.8)

The answer span is predicted on $\hat{\mathbf{h}}_{K}$.

##  Chapter 6 Conversational QA over Knowledge Bases

Techniques and methods developed for Conversational Question Answering over
Knowledge Bases (C-KBQA) are fundamental to the knowledge base search module
of a CIR system, as shown in Figure 1.4. Unlike the machine comprehension
module (Chapter 5), which has to rely on the documents retrieved by the
document search module to generate answers, the knowledge base search module
can be used as a standalone system, known as a C-KBQA system, which generates
the answer to an input query by reasoning over its knowledge base. Many task-
oriented dialog systems are implemented as instances of a C-KBQA system [Gao
et al.,, 2019]. These systems consist of many dialog components that have
counterparts in a CIR system as in Figure 1.4, such as contextual query
understanding, dialog policy, dialog state tracker, clarifying question
generation, and response generation.

This chapter describes C-KBQA as a special case of CIR, where the answers to
input queries are generated not from a collection of indexed documents, but
from a (set of) structured knowledge base(s). Section 6.1 introduces the
C-KBQA task, and describes the forms of knowledge bases and public benchmarks.
Section 6.2 gives an overview of the architecture of a typical C-KBQA system
that is based on semantic parsing. The next four sections (Sections 6.3, 6.4,
6.5, and 6.6) describe each of the four main modules of a semantic-parser-
based C-KBQA system, respectively, including a semantic parser, a dialog state
tracker, a dialog policy, and a response generator. Section 6.7 discusses a
unitary (non-modular) C-KBQA system that is based on a Transformer-based
language model which unifies the C-KBQA modules and can generate answers
grounded in input queries, dialog states and knowledge.

###  6.1 Knowledge Bases and Questions

Many C-KBQA systems are developed as a natural language interface to access
their knowledge bases (KBs), which are typically implemented as relational
databases or knowledge graphs.

A relational database (DB) is also known as an entity-centric KB. It stores a
list of entities, each associated with a set of properties. Figure 6.1 (Left)
shows a table in a relational database that contains a list of characters who
appear in the comics Legion of Super Heroes (entities), and for each character
a set of properties such as first-appeared, home-world, powers.

Figure 6.1: A semantic-parsing-based question answering system over a
relational database. (Left) A sub-table of the relational database related to
the comics Legion of Super Heroes Post-Infinite Crisis. (Right) A question,
its semantic parse, and the answer. Figures adapted from Iyyer et al., [2017]

A knowledge graph (KG) consists of a collection of subject-relation-object
triples $(s,r,o)$ where $s,o\in\mathcal{E}$ are entities and $r\in\mathcal{R}$
is a relation (or predicate). The “knowledge graph” is named after its
graphical representation, i.e., the entities are nodes and the relations are
the directed edges that link the nodes. Figure 6.2 (Left) shows a small sub-
graph of Freebase [Bollacker et al.,, 2008] related to the TV show Family Guy.
Nodes include some names, dates and special Compound Value Type (CVT)
entities.111CVT is not a real-world entity, but is used to collect multiple
fields of an event or a special relationship. A directed edge describes the
relation between two entities, labeled by a relation.

Figure 6.2: A semantic-parsing-based question answering system over a
knowledge graph. (Left) A sub-graph of Freebase related to the TV show Family
Guy. (Right) A question, its logical form in $\lambda$-calculus and query
graph, and the answer. Figures adapted from Yih et al., [2015].

The primary difference between KGs and relational DBs is that the former work
with paths while the latter work with sets. In a KG, the relations are stored
at the individual record level, while in a relational DB the structure is
defined at a higher level (i.e., the table schema). This has important
ramifications. First, a relational DB is much faster than a KG when operating
on large numbers of records. In a KG, each record needs to be examined
individually against an input question to determine the structure of the data
in order to locate the sub-graph in which answer nodes reside, as illustrated
in Figure 6.2 (Right). In a relational DB, the schema of each table is pre-
defined. Thus, an input question can be readily parsed to a SQL-like query
based on the pre-defined schema, which is then executed on the DB to retrieve
answer records, as illustrated in Figure 6.1 (Right). Second, relational DBs
use less storage space, because it is not necessary to store all those
relationships for each record or entity.

Due to these differences, KGs and relational DBs are applied in different
settings. KGs are mainly used to store Web-scale open-domain KBs, such as
Freebase [Bollacker et al.,, 2008] and DBPedia [Auer et al.,, 2007], where
there are many variations in relations (or predicates) among entities, and
users can issue complex questions which need to be parsed to map to different
paths in the knowledge graph to retrieve the answer nodes. Relational DBs, on
the other hand, are widely used to store task-specific KBs where the
attributes of entities can be pre-defined. For example, the KBs of many task-
oriented dialog systems, such as the ones designed for movie ticket booking or
table reservation in a restaurant, are stored using relational DBs.

The QA sessions in Figures 6.1 and 6.2 are _single-turn_. But it is not
reasonable to assume that users can always compose in one shot a complicated,
compositional natural language question that can uniquely identify the answer
in the KB. As discussed in Section 1.2, many information seeking tasks, such
as exploratory search, require an intensive human-machine interaction over a
long-term iterative sensemaking process. Thus, a multi-turn C-KBQA system is
more desirable because they allow users to query a KB interactively without
composing complicated questions. For example, Iyyer et al., [2017] show that
users rarely issue complicated questions like

“Which super heroes came from earth and first appeared after 2009?”

as in Figure 6.1 (Right). Instead, the same intent is more naturally expressed
through a sequence of simpler questions as:

  1. 1.

“Who are the super heroes?”

  2. 2.

“Which of them come from earth?”

  3. 3.

“Of those, who appears after 2009?”

Figure 6.3: A sample conversational QA session from the CSQA dataset Saha et
al., [2018].

Saha et al., [2018] present a dataset that consists of 200K QA sessions for
the task of Complex Sequence Question Answering (CSQA). Figure 6.3 shows a
sample conversational QA session from the dataset. The session contains a
sequence of questions. Some are simple questions that can be answered from a
single subject-relation-object triple in the knowledge graph, such as the