Nlp

How to Build an Open-Domain Question Answering System:

[Updated on 2020-11-12: Added an example of closed-book factual QA using the OpenAI API (beta). A model that can answer any question based on factual knowledge can enable many useful, practical applications, including serving as a chatbot or an AI assistant🤖. In this post, we review several common approaches to building an open-domain question answering system.

2020 · 33 min read · Curated and presented by Arthur Sedek

A model that can answer any fact-based question can unlock many valuable applications. This article examines how to build an Open-Domain Question Answering (ODQA) system under the assumption that we have access to a powerful pretrained language model. It covers both closed-book and open-book approaches.

[Updated on 2020-11-12: add an example on closed-book factual QA using OpenAI API (beta).

A model capable of answering factual questions can enable many practical uses, such as powering a chatbot or an AI assistant🤖. In this post, we review several widely used approaches for building an open-domain question answering system.

Disclaimers given so many papers in the wild:

Assume we have access to a powerful pretrained language model.
We do not cover how to use structured knowledge base (e.g. Freebase, WikiData) here.
We only focus on a single-turn QA instead of a multi-turn conversation style QA.
We mostly focus on QA models that contain neural networks, specially Transformer-based language models.
I admit that I missed a lot of papers with architectures designed specifically for QA tasks between 2017-2019😔

What is Open-Domain Question Answering?

Open-domain Question Answering (ODQA) is a class of language tasks in which a model is asked to produce natural-language answers to factoid questions. Because the correct answer is objective, performance is relatively straightforward to evaluate.

For example,

Question: What did Albert Einstein win the Nobel Prize for?
Answer: The law of the photoelectric effect.

The “open-domain” aspect refers to the absence of provided context for an arbitrarily asked factual question. In the example above, the model receives only the question as input, and no article about “why Einstein didn’t win a Nobel Prize for the theory of relativity” is supplied, even though such an article would likely mention the term “the law of the photoelectric effect.” When both the question and the context are provided, the task is typically referred to as Reading comprehension (RC).

An ODQA model may operate with or without access to an external source of knowledge (e.g. Wikipedia). These two settings are commonly referred to as open-book and closed-book question answering, respectively.

When thinking about different kinds of open-domain questions, I like the classification by Lewis, et al., 2020, ordered from easier to harder:

A model can correctly memorize and return the answer to a question it saw during training.
A model can answer novel test-time questions by selecting an answer from the set of answers observed during training.
A model can answer novel questions whose answers do not appear in the training dataset.

Overview of three frameworks discussed in this post.

Notation

Given a question $x$ and a ground truth answer span $y$, the context passage that contains the true answer is denoted $z \in \mathcal{Z}$, where $\mathcal{Z}$ is an external knowledge corpus. Wikipedia is a common choice for this type of external knowledge source.

Concerns of QA data fine-tuning

Before getting into the details of the models below, it is worth flagging one concern related to fine-tuning on common QA datasets, which appears as a fine-tuning step in several ODQA models. This can be problematic because many public QA datasets exhibit substantial overlap between questions in their training and test sets.

Lewis, et al., (2020) (code) found that 58-71% of test-time answers also appear somewhere in the training sets, and that 28-34% of test-set questions have a near-duplicate paraphrase in their corresponding training sets. In their experiments, multiple models performed noticeably worse when duplicated or paraphrased questions were removed from the training data.

Open-book QA: Retriever-Reader

Given a factoid question, if a language model has no context, or if it is not large enough to memorize relevant context present in its training data, it is unlikely to guess the correct answer. In an open-book exam, students can consult external resources such as notes and books while answering. In the same spirit, an ODQA system can be paired with a rich knowledge base and use it to locate relevant documents that serve as evidence for answers.

The overall process of answering a question can be decomposed into two stages:

Locate relevant context in an external knowledge repository;
Process the retrieved context to extract an answer.

The retriever-reader QA framework combines information retrieval with machine reading comprehension.

This retriever + reader framework was first introduced in DrQA (“Document retriever Question-Answering” by Chen et al., 2017; code). The retriever and reader can be designed and trained independently, or they can be trained jointly end-to-end.

Retriever Model

Two common ways to implement the retriever are: (1) an information retrieval (IR) system based on classic, non-learning TF-IDF features (“classic IR”), or (2) dense text embeddings produced by neural networks (“neural IR”).

Classic IR

DrQA (Chen et al., 2017) uses an efficient, non-learning search engine based on the vector space model. Each query and document is represented as a bag-of-words vector, with each term weighted by TF-IDF (term frequency $\times$ inverse document frequency).

$ \begin{aligned} \text{tf-idf}(t, d, \mathcal{D}) &= \text{tf}(t, d) \times \text{idf}(t, \mathcal{D}) \\ \text{tf}(t, d) &= \log(1 + \text{freq}(t, d)) \\ \text{idf}(t, \mathcal{D}) &= \log \Big( \frac{\vert\mathcal{D}\vert}{\vert d\in\mathcal{D}: t\in d\vert} \Big) \end{aligned} $

Here, $t$ is a unigram or bigram term in a document $d$ from a collection of documents $\mathcal{D}$. $\text{freq}(t, d)$ measures how often a term $t$ occurs in $d$. Note that the term-frequency definition also includes bigram counts. This is reported to be very helpful because bigrams incorporate local word order information. In its implementation, DrQA maps the bigrams of $2^{24}$ bins using unsigned murmur3 hash.

Concretely, DrQA uses Wikipedia as its knowledge source, and this choice has since become a default setting in many ODQA studies. The non-ML document retriever returns the top $k=5$ most relevant Wikipedia articles for a given question.

BERTserini (Yang et al., 2019) combines the open-source Anserini IR toolkit as the retriever with a fine-tuned, pretrained BERT model as the reader. The top $k$ documents ($k=10$) are retrieved using the post-v3.0 branch of Anserini, treating the query as a bag of words. Retrieved text segments are scored using BM25, a classic TF-IDF-based retrieval function. Regarding the impact of retrieval granularity, they report paragraph retrieval > sentence retrieval > article retrieval.

An illustration of BERTserini architecture. (Image source: Yang et al., 2019)

ElasticSearch + BM25 is used by the Multi-passage BERT QA model (Wang et al., 2019). They report that splitting articles into 100-word passages using a sliding window yields 4% improvements, because splitting documents into non-overlapping passages can cause evidence near passage boundaries to lose useful context.

Neural IR

Learning low-dimensional representations of text that are denser than raw term-based vectors has a long history (Deerwester et al., 1990; Yih, et al., 2011). Dense representations can be obtained via matrix decomposition or through neural architectures (e.g. MLP, LSTM, bidirectional LSTM, etc.). When neural networks are involved, such approaches are often categorized as “Neural IR.” Neural IR is a newer category of retrieval methods, but it is not guaranteed to outperform classic IR (Lim, 2018).

After the success of many large-scale general language models, many QA models adopt the following pattern:

$ h_x = E_x(x)\quad h_z = E_z(z)\quad \text{score}(x, z) = h_x^\top h_z $

Compute dense representations of a question $x$ and a context passage $z$ by feeding them into a language model;
Use the dot product between these representations as a retrieval score to rank passages and select the most relevant ones.

ORQA, REALM and DPR all use this type of scoring function for context retrieval, which will be described in detail in a later section on the end-to-end QA model.

An extreme variant, explored in DenSPI (“Dense-Sparse Phrase Index”; Seo et al., 2019), encodes the entire knowledge corpus at the phrase level, then relies solely on the retriever to select the most relevant phrase as the predicted answer. Under this design, the retriever+reader pipeline effectively becomes a retriever-only system. Naturally, the index becomes much larger and the retrieval problem becomes more challenging.

DenSPI proposes a query-agnostic indexable representation of document phrases. Specifically, it encodes query-agnostic representations of Wikipedia text spans offline, then searches for the answer at inference time using nearest-neighbor retrieval. This can substantially reduce inference time because documents do not need to be re-encoded for each new query, which is often required by reader models.

Given a question $x$ and a fixed set of (Wikipedia) documents, $z_1, \dots, z_K$, where each document $z_k$ contains $N_k$ words, $z_k = \langle z_k^{(1)}, \dots, z_k^{(N_k)}\rangle$, an ODQA model defines a scoring function $F$ over each candidate phrase span $z_k^{(i:j)}, 1 \leq i \leq j \leq N_k$, such that the true answer is the phrase with the maximum score: $y = {\arg\max}_{k,i,j} F(x, z_k^{(i:j)})$.

The phrase representation $z_k^{(i:j)}$ combines dense and sparse vectors, $z_k^{(i:j)} = [d_k^{(i:j)}, s_k^{(i:j)}] \in \mathbb{R}^{d^d + d^s}$ (note that $d^d \ll d^s$):

The dense vector $d_k^{(i:j)}$ is effective at encoding local syntactic and semantic cues, as can be learned by a pretrained language model.
The sparse vector $s_k^{(i:j)}$ is better suited for encoding precise lexical information. This sparse vector is a term-frequency-based encoding. DenSPI uses 2-gram term frequency, as in DrQA, producing a highly sparse representation ($d^s \approx 16$M)

The dense vector $d^{(i:j)}$ is further decomposed into three parts, $d^{(i:j)} = [a_i, b_j, c_{ij}] \in \mathbb{R}^{2d^b + 1}$ where $2d^b + 1 = d^d$. All three components are learned from different columns of fine-tuned BERT representations.

A vector $a_i$ encodes the start position for the $i$-th word of the document;
A vector $b_j$ encodes the end position for the $j$-th word of the document;
A scalar $c_{ij}$ measures the coherency between the start and end vectors, helping prevent non-constituent phrases during inference.

For all $(i,j,k)$ tuples satisfying $j-i < J$, the text span embeddings are precomputed and stored in a phrase index. The maximum span length $J$ is a predefined scalar constant.

An illustration of Dense-Sparse Phrase Index (DenSPI) architecture. (Image source: Seo et al., 2019)

At inference time, the question is mapped into the same vector space $x=[d’, s’] \in \mathbb{R}^{d^d + d^s}$. The dense vector $d’$ is taken from the BERT embedding of the special [CLS] symbol. The same BERT model is shared for encoding both questions and phrases. The final answer is predicted by $k^*, i^*, j^* = \arg\max x^\top z_k^{(i:j)}$.

Reader Model

The reader learns to solve reading comprehension: given a question and a context document, it extracts an answer from the document. Here, we focus only on neural network approaches to machine comprehension.

Bi-directional LSTM

The DrQA reader for answer detection (Chen et al., 2017) is a 3-layer bidirectional LSTM with hidden size 128. Each relevant paragraph from retrieved Wikipedia articles is encoded as a sequence of feature vectors, $\{\tilde{\mathbf{z}}_1, \dots, \tilde{\mathbf{z}}_m \}$. Each feature vector $\hat{\mathbf{z}}_i \in \mathbb{R}^{d_z}$ is intended to capture contextual information around a token $z_i$. The feature set includes multiple categories:

Word embeddings: A 300d Glove word embedding trained on 800B Web crawl data, $f_\text{embed} = E_g(z_i)$.
Exact match: Whether a word $z_i$ appears in the question $x$, $f_\text{match} = \mathbb{I}(z_i \in x)$.
Token features: POS (part-of-speech) tagging, NER (named entity recognition), and TF (term-frequency), $f_\text{token}(z_i) = (\text{POS}(z_i), \text{NER}(z_i), \text{TF}(z_i))$.
Aligned question embedding: The attention score $y_{ij}$ is designed to capture inter-sentence matching and similarity between the paragraph token $z_i$ and the question word $x_j$. This feature provides soft alignment between words that are similar but not identical.

$ \begin{aligned} f_\text{align}(z_i) &= \sum_j y_{i,j} E_g(x_j) \\ y_{i,j} &= \frac{\exp(\alpha(E_g(z_i))^\top \alpha(E_g(x_j)) )}{\sum_{j'} \exp(\alpha(E_g(z_i))^\top \alpha(E_g(x_{j'})) ) } \end{aligned} $

where $\alpha$ is a single dense layer with ReLU and $E_g(.)$ is the glove word embedding.

The feature vector sequence for a paragraph of $m$ tokens is passed through the LSTM to produce final paragraph vectors:

$ \begin{aligned} \mathbf{z} = \{\mathbf{z}_1, \dots, \mathbf{z}_m\} &= \text{LSTM}(\{\tilde{\mathbf{z}}_1, \dots, \tilde{\mathbf{z}}_m\}) \\ \text{where } \tilde{\mathbf{z}}_i &= \{f_\text{embed}, f_\text{match}, f_\text{token}, f_\text{align}\} \end{aligned} $

The question is represented as a weighted sum of the embeddings for all question words:

$ \mathbf{x} = \sum_j b_j E(x_j) \quad b_j = \text{softmax}(\mathbf{w}^\top E(x_j)) $

where $\mathbf{w}$ is a learned weight vector.

After constructing feature vectors for the question and all relevant paragraphs, the reader predicts, for each paragraph position, the probability of being the start and end of an answer span, $p_\text{start}(i_s)$ and $p_\text{end}(i_s)$, respectively. Across all paragraphs, the model returns the optimal span as the final answer by maximizing $p_\text{start}(i_s) \times p_\text{end}(i_e) $.

$ \begin{aligned} p_\text{start}(i_s) \propto \exp(\mathbf{z}_{i_s} \mathbf{W}_s \mathbf{x}) \\ p_\text{end}(i_e) \propto \exp(\mathbf{z}_{i_e} \mathbf{W}_e \mathbf{x}) \\ \text{ s.t. } i_s \leq i_e \leq i_s + 15 \end{aligned} $

where $\mathbf{W}_s$ and $\mathbf{W}_e$ are learned parameters.

BERT-universe

After the success of BERT (Devlin et al., 2018), many QA systems implement the machine comprehension component using BERT. Define BERT as a function that takes one or more strings (concatenated by [SEP]) and outputs encoding vectors for the special [CLS] token and for each input token:

$ \text{BERT}(s_1, s_2, \dots) = [\mathbf{h}^\texttt{[CLS]}, \mathbf{h}^{(1)}, \mathbf{h}^{(2)}, \dots] $

where $\mathbf{h}^\texttt{[CLS]}$ is the embedding for the special [CLS] token and $\mathbf{h}^{(i)}$ is the embedding for the $i$-th token.

To apply BERT to reading comprehension, the model learns two additional weights, $\mathbf{W}_s$ and $\mathbf{W}_e$, and $\text{softmax}(\mathbf{h}^{(i)}\mathbf{W}_s)$ and $\text{softmax}(\mathbf{h}^{(i)}\mathbf{W}_e)$ define probability distributions over the start and end positions of the predicted span for each token.

BERTserini (Yang et al., 2019) uses a pretrained BERT model as the reader. Their experiments indicate that fine-tuning pretrained BERT on SQuAD is sufficient to achieve high accuracy for answer span identification.

How BERT is used to solve question-answering tasks. (Image source: Devlin et al., 2018)

The main difference between the BERTserini reader and the original BERT QA setup is that, to enable comparison and aggregation across segments, it removes the final softmax layer over candidate answer spans. The pretrained BERT model is fine-tuned on the SQuAD training set. All reader inputs are padded to 384 tokens, and the learning rate is 3e-5.

When ranking extracted answer spans, the retriever score (BM25) is combined with the reader score (probability of a token being the start position $\times$ probability of that token being the end position) using linear interpolation.

In the original BERT, the start and end distributions are normalized independently within each passage. In contrast, Multi-passage BERT (Wang et al., 2019) normalizes answer scores across all retrieved passages for a question globally. Specifically, multi-passage BERT removes the final per-passage normalization layer in BERT for QA (as in BERTserini) and then applies a global softmax across all word positions in all passages. This global normalization makes the reader more stable when pinpointing answers from many passages.

Multi-passage BERT also adds an independent passage ranker, implemented as another BERT model. The rank score for $(x, z)$ is computed using a softmax over the representation vectors of the first [CLS] token. The passage ranker yields an additional 2% improvement. A similar idea, re-ranking passages using BERT, is also discussed in Nogueira & Cho, 2019.

Interestingly, Wang et al., 2019 reports that explicit inter-sentence matching is not critical for RC tasks with BERT (see the original paper for the experimental design). One possible explanation is that BERT’s multi-head self-attention layers already encode inter-sentence matching.

End-to-end Joint Training

The retriever and reader can be trained jointly. This section covers R^3, ORQA, REALM and DPR. These methods share several design patterns, including BERT-based dense retrieval vectors and objectives that maximize the marginal likelihood of recovering the true answer.

In the R^3 (“Reinforced Ranker-Reader”; Wang, et al., 2017) QA system, the retriever and reader are trained jointly via reinforcement learning. (To keep terminology consistent across papers discussed in this section, the “ranker” model in the original R^3 paper is referred to as the “retriever” model here.) Both components are variants of Match-LSTM, which uses an attention mechanism to compute word-level similarities between passage and question sequences.

How does the Match-LSTM module work? Given a question $\mathbf{X}$ containing $d_x$ words and a passage $\mathbf{Z}$ containing $d_z$ words, both are represented using fixed Glove word embeddings:

$ \begin{aligned} \mathbf{H}^x &= \text{BiLSTM}(\mathbf{X}) \in \mathbb{R}^{l \times d_x} \\ \mathbf{H}^z &= \text{BiLSTM}(\mathbf{Z}) \in \mathbb{R}^{l \times d_z} \\ \mathbf{G} &= \text{softmax}((\mathbf{W}^g \mathbf{H}^x + \mathbf{b}^g \otimes \mathbf{e}_{d_x})^\top \mathbf{H}^z) \in \mathbb{R}^{d_x \times d_z} & \text{; an attention matrix}\\ \bar{\mathbf{H}}^x &= \mathbf{H}^x \mathbf{G} \in \mathbb{R}^{l \times d_z} \\ \mathbf{M} &= \text{ReLU} \Big( \mathbf{W}^m \begin{bmatrix} \mathbf{H}^z \\ \bar{\mathbf{H}}^x \\ \mathbf{H}^z \odot \bar{\mathbf{H}}^x \\ \mathbf{H}^z - \bar{\mathbf{H}}^x \end{bmatrix} \Big) \in \mathbb{R}^{2l \times d_z} \\ \mathbf{H}^m &= \text{BiLSTM}(M) \in \mathbb{R}^{l \times d_z} \end{aligned} $

where $l$ is the hidden dimension of the bidirectional LSTM module. $\mathbf{W}^g \in \mathbb{R}^{l\times l}$, $\mathbf{b}^g \in \mathbb{R}^l$, and $\mathbf{W}^m \in \mathbb{R}^{2l \times 4l}$ are learned parameters. The operator $\otimes \mathbf{e}_{d_x}$ denotes the outer product that repeats the column vector $\mathbf{b}^g$ $d_x$ times.

The retriever and reader share the same Match-LSTM module, but use separate prediction heads in the final layer, producing $\mathbf{H}^\text{rank}$ and $\mathbf{H}^\text{reader}$.

The overview of R^3 (reinforced ranker-reader) architecture. Both components share the same Match-LSTM module. (Image source: Wang, et al., 2017)

The retriever applies max-pooling over each passage and then aggregates the result to output the probability that each passage entails the answer.

$ \begin{aligned} \mathbf{u}_i &= \text{max-pooling}(\mathbf{H}^\text{rank}_i) \in \mathbb{R}^l \\ \mathbf{C} &= \text{tanh}(\mathbf{W}^c[\mathbf{u}_1;\dots;\mathbf{u}_N] + \mathbf{b}^c \otimes \mathbf{e}_N) \in \mathbb{R}^{l \times n} \\ \gamma &= \text{softmax}(\mathbf{w}^c \mathbf{C}) \in \mathbb{R}^n \end{aligned} $

Finally, the retriever is treated as a policy that outputs an action to sample a passage according to the predicted $\gamma$:

$ \pi(z \vert x; \theta^\gamma) = \gamma_z $

The reader predicts the answer span start position $\beta^s$ and end position $\beta^e$. The two positions are computed in the same way, but with independent parameters. Across all passages involved, there are $V$ words in total.

$ \begin{aligned} \mathbf{H}^\text{read} &= [\mathbf{H}^\text{read}_\tau; \mathbf{H}^\text{read}_{\text{neg}_1}; \dots; \mathbf{H}^\text{read}_{\text{neg}_n}] \\ \mathbf{F}^s &= \text{tanh}(\mathbf{W}^s \mathbf{H}^\text{read} + \mathbf{b}^s \otimes \mathbf{e}_V) \quad \beta^s = \text{softmax}(\mathbf{w}^s \mathbf{F}^s) \in \mathbb{R}^V \\ \mathbf{F}^e &= \text{tanh}(\mathbf{W}^e \mathbf{H}^\text{read} + \mathbf{b}^e \otimes \mathbf{e}_V) \quad \beta^e = \text{softmax}(\mathbf{w}^e \mathbf{F}^e) \in \mathbb{R}^V \\ L(y \vert z, x) &= -\log(\beta^s_{y_z^s})-\log(\beta^e_{y_z^e}) \end{aligned} $

where $y$ is the ground-truth answer and the passage $z$ is sampled by the retriever. $\beta^s_{y_z^s}$ and $\beta^s_{y_z^e}$ are the probabilities that $y$ is the start and end position, respectively, within passage $z$.

The end-to-end training objective for the R^3 QA system is to minimize the negative log-likelihood of obtaining the correct answer $y$ given a question $x$:

$ \begin{aligned} \mathcal{J}(\theta) &= -\mathbb{E}_{z\sim\pi(.\vert x)} [L(y \vert z, x)] \\ \nabla \mathcal{J}(\theta) &= - \nabla_\theta \sum_z \pi(z \vert x) L(y \vert z, x) \\ &= - \sum_z \big( L(y \vert z, x) \nabla_\theta\pi(z \vert x) + \pi(z \vert x) \nabla_\theta L(y \vert z, x) \big) \\ &= - \mathbb{E}_{z\sim\pi(.\vert x)} \big( \color{red}{L(y \vert z, x)\nabla_\theta\log\pi(z \vert x)} + \nabla_\theta L(y \vert z, x) \big) \\ &\approx - \mathbb{E}_{z\sim\pi(.\vert x)} \big( \underbrace{\color{red}{R(y \vert z, x)\nabla_\theta\log\pi(z \vert x)}}_\text{REINFORCE} + \nabla_\theta L(y \vert z, x) \big) \end{aligned} $

During training, given a passage $z$ sampled by the retriever, the reader is optimized with gradient descent, while the retriever is optimized via REINFORCE using $L(y \vert z, x)$ as the reward signal. However, $L(y \vert z, x)$ is unbounded and can introduce substantial variance. To reduce this issue, the paper replaces the reward with a customized scoring function that compares the ground-truth $y$ with the answer extracted by the reader $\hat{y}$:

$ R(y, \hat{y} \vert z) = \begin{cases} 2 & \text{if } y = \hat{y}\\ f1(y, \hat{y}) & \text{if } y \cap \hat{y} = \varnothing \\ -1 & \text{otherwise} \end{cases} $

The workflow of R^3 training process. (Image source: acl2020-openqa-tutorial/slides/part4)

ORQA (“Open-Retrieval Question-Answering”; Lee et al., 2019) jointly learns a retriever-and-reader QA model by optimizing the marginal log-likelihood of producing correct answers under supervision. It does not rely on an explicit “black-box” IR system. Instead, it is designed to retrieve text from an open corpus directly. During training, ORQA does not require ground-truth context passages (that is, reading comprehension datasets), and instead uses only (question, answer) string pairs. Both the retriever and the reader are built on BERT, but they do not share parameters.

An illustration of the retriever component in ORQA. (Image source: replotted based on one slide in acl2020-openqa-tutorial/slides/part5)

Evidence blocks are ranked by a retrieval score defined as the inner product between BERT embedding vectors for the [CLS] token of the question $x$ and the evidence block $z$. Note that the question encoder and the context encoder are independent.

$ \begin{aligned} h_x &= \mathbf{W}_x \text{BERT}_x(x)^{\mathtt{[CLS]}} \\ h_z &= \mathbf{W}_z \text{BERT}_z(z)^{\mathtt{[CLS]}} \\ S_\text{retr}(z, x) &= h_x^\top h_z \end{aligned} $

The retriever is pretrained with the Inverse Cloze Task (ICT), which aims to predict the context given a sentence, the reverse of the standard Cloze Task. The ICT objective maximizes the retrieval score for the correct context $z$ given a randomly selected sentence $x$:

$ L_\text{ICT} = p_\text{early}(z \vert x) = \frac{\exp(S_\text{retr}(z, x))}{\sum_{z'\in\text{BATCH}(\mathcal{Z})} \exp(S_\text{retr}(z', x))} $

where $\text{BATCH}(\mathcal{Z})$ denotes the set of evidence blocks from the same batch, used as sampled negatives.

After this pretraining stage, the BERT retriever is expected to produce representations that are sufficiently effective for evidence retrieval. For answer extraction, only the question encoder needs fine-tuning. Put differently, the evidence block encoder (that is, $\mathbf{W}_z$ and $\text{BERT}_z$) is kept fixed, so all evidence block encodings can be precomputed, with support for fast Maximum Inner Product Search (MIPS).

An illustration of the reader component in ORQA. (Image source: acl2020-openqa-tutorial/slides/part5)

The reader follows the same design used in the original BERT RC experiments. It is trained in a supervised fashion: the evidence block encoder parameters remain fixed, while all other parameters are fine-tuned. Given a question $x$ and a gold answer string $y$, the reader loss includes two components:

$ \mathcal{L}(x, y) = \mathcal{L}_\text{early}(x, y) + \mathcal{L}_\text{full}(x, y) $

(1) Identify all correct text spans within the top $k$ evidence blocks, and optimize the marginal likelihood over a text span $s$ that matches the true answer $y$:

$ \begin{aligned} h_s &= \text{BERT}_R(x, y)^{(\text{START}(s))} \\ h_e &= \text{BERT}_R(x, y)^{(\text{END}(s))} \\ S_\text{read}(z, s, x) &= \text{MLP}([h_s; h_e]) \\ p(z, s \vert x) &= \frac{\exp(S_\text{read}(z, s, x))}{\sum_{z'\in\text{TOP}(k)} \sum_{s'\in z'} \exp(S_\text{read}(z', s', x))} \\ L_\text{full}(x, y) &= - \log \sum_{\substack{z \in \text{TOP}(k)\\ s \in z}} \sum_{y=\text{TEXT}(s)} p(z, s \vert x) \end{aligned} $

where $y=\text{TEXT}(s)$ indicates whether the answer $y$ matches the text span $s$. $\text{TOP}(k)$ denotes the top $k$ retrieved blocks according to $S_\text{retr}(z, x)$. The paper sets $k=5$.

(2) Early in training, when the retriever is still weak, none of the top $k$ blocks may contain the answer. To mitigate overly sparse learning signals, ORQA uses a larger pool of $c$ evidence blocks to drive more aggressive learning. The paper uses $c=5000$.

$ L_\text{early}(x, y) = -\log \sum_{\substack{z\in \text{TOP}(c)\\y\in\text{TEXT}(z)}} p_\text{early}(z\vert x) = -\log \sum_{\substack{z\in \text{TOP}(c)\\y\in\text{TEXT}(z)}} \frac{\exp(S_\text{retr}(z, x)}{\sum_{z'\in\text{TOP}(c)} \exp(S_\text{retr}(z', x)} $

The ORQA paper also discusses several issues with the SQuAD dataset:

" The notable drop between development and test accuracy for SQuAD is a reflection of an artifact in the dataset,its 100k questions are derived from only 536 documents. Therefore, good retrieval targets are highly correlated between training examples, violating the IID assumption, and making it unsuitable for learned retrieval. We strongly suggest that those who are interested in end-to-end open-domain QA models no longer train and evaluate with SQuAD for this reason."

REALM (“Retrieval-Augmented Language Model pre-training”; Guu et al., 2020) likewise trains a retriever and reader jointly by optimizing the marginal likelihood of producing the correct answer:

$ p(y \vert x) = \sum_{z \in \mathcal{Z}} \underbrace{p(y \vert x, z)}_\text{reader} \underbrace{p(z \vert x)}_\text{retriever} \approx \sum_{z \in \text{TOP}_k(\mathcal{Z})} p(y \vert x, z) p(z \vert x) $

REALM is first unsupervised pre-trained with salient spans masking and then fine-tuned with QA data. (Image source: Guu et al., 2020).

REALM computes two probabilities, $p(z \vert x)$ and $p(y \vert x, z)$, as in ORQA. However, rather than using ICT in ORQA’s form, REALM improves the unsupervised pretraining stage through several design changes that lead to better retrieval. REALM pretrains on Wikipedia or the CC-News corpus.

Use salient span masking. The method identifies named entities and dates, selects one of these “salient spans,” and masks it. Salient span masking is a special case of MLM and performs well for QA.
Add an empty null document, because not every question requires a context document.
Avoid trivial retrieval: the retrieved context document should not be the same as the selected sentence that contains the masked span.
Apply the same ICT loss as in ORQA to encourage learning when retrieval quality is still poor in the early stages of training.

“Among all systems, the most direct comparison with REALM is ORQA (Lee et al., 2019), where the fine-tuning setup, hyperparameters and training data are identical. The improvement of REALM over ORQA is purely due to better pre-training methods.” , from REALM paper.

Both unsupervised pretraining and supervised fine-tuning optimize the same log-likelihood $\log p(y \vert x)$. Because the retriever’s evidence-document encoder parameters are updated during training, the MIPS index changes over time. REALM refreshes the index asynchronously using the updated encoder parameters every several hundred training steps.

Balachandran, et al. (2021) found that REALM is substantially undertrained, and that REALM++ improves EM accuracy by 3-5% by scaling training up via a larger batch size and by retrieving more documents for the reader to process.

DPR (“Dense Passage Retriever”; Karpukhin et al., 2020, code) argues that ICT pretraining can be computationally too expensive, and that ORQA’s context encoder may be suboptimal because it is not fine-tuned on question-answer pairs. DPR addresses both concerns by training only a dense dual-encoder retrieval architecture from a small number of supervised Q/A pairs, without any pretraining.

As in earlier work, DPR uses the dot product (L2 distance or cosine similarity also works) between BERT representations as the retrieval score. The dual-encoder is trained with the NLL of the positive passage, which effectively matches the same formulation as ICT loss in ORQA. Note that both approaches treat other passages in the same batch as negatives, a technique known as in-batch negative sampling. The key difference is that DPR relies on supervised QA data, whereas ORQA learns on an unsupervised corpus using ICT. At inference time, DPR uses FAISS for fast MIPS.

DPR reports comparison experiments across several types of negatives:

Random: a randomly selected passage from the corpus.
BM25: top passages returned by BM25 that do not contain the answer but match most question tokens.
In-batch negative sampling (“gold”): positive passages paired with other questions that occur in the training set.

DPR finds the best results when using gold passages from the same mini-batch together with one hard negative passage that has a high BM25 score. To further improve retrieval, DPR also explores linearly combining a BM25 score and a dense embedding retrieval score as a new ranking function.

Open-book QA: Retriever-Generator

Relative to retriever-reader methods, retriever-generator systems also use two stages, but the second stage generates free-form text to answer the question, rather than extracting a start and end position from a retrieved passage. Some papers also describe this setup as generative question answering.

The retriever + generator QA framework combines a document retrieval system with a general language model.

As illustrated above, a pretrained LM can store substantial knowledge in its parameters. However, such models do not readily allow memory modification or expansion, do not provide transparent explanations for their predictions, and can generate non-existent illusion.

Petroni et al. (2020) investigates how retrieved, relevant context improves answer quality for a generative language model. The authors report the following findings:

Adding relevant context to queries substantially improves a pretrained LM on unsupervised machine reading capabilities.
An off-the-shelf IR system is sufficient for BERT to match the performance of a supervised ODQA baseline.
BERT’s NSP pre-training strategy is an effective unsupervised mechanism for handling noisy and irrelevant context.

They pair BERT with several types of context, including adversarial (unrelated context), retrieved (via BM25), and generative (produced by an autoregressive language model with 1.4N parameters trained on CC-NEWS). The model is robust to adversarial context, but only when the question and context are provided as two segments (for example, separated by [SEP]). One hypothesis connects this behavior to the NSP task: “BERT might learn to not condition across segments for masked token prediction if the NSP score is low, thereby implicitly detecting irrelevant and noisy contexts.”

RAG (“Retrieval-Augmented Generation”; Lewis et al., 2020) combines parametric memory (a pretrained language model) with non-parametric memory (an external knowledge index) for language generation. RAG can be fine-tuned for any seq2seq task, jointly learning both the retriever and the sequence generator. The authors report that unconstrained generation outperforms earlier extractive approaches.

RAG includes a retriever model $p_\eta(z \vert x)$ and a generator model $p_\theta(y_i \vert x, z, y_{1:i-1})$:

The retriever takes input sequence $x$ and retrieves text passages $z$, implemented as a DPR retriever. $\log p_\eta(z \vert x) \propto E_z(z)^\top E_x(x)$.
The generator uses $z$ as additional context when generating the target sequence $y$, simply concatenating the context and the question.

RAG has two variants, depending on whether it uses the same retrieved documents across the full sequence or different documents for each token generation:

$ \begin{aligned} p_\text{RAG-seq}(y \vert x) &= \sum_{z \in \text{TOP}_k(p_\eta(.\vert x))} p_\eta(z \vert x) \prod_i^N p_\theta(y_i \vert x, z, y_{1:i-1}) \\ p_\text{RAG-token}(y \vert x) &= \prod_i^N \sum_{z \in \text{TOP}_k(p_\eta(.\vert x))} p_\eta(z_i\vert x) p_\theta(y_i \vert x, z_i, y_{1:i-1}) \end{aligned} $

The retriever and generator are trained jointly in RAG by minimizing the NLL loss, $\mathcal{L}_\text{RAG} = \sum_j -\log p(y_j \vert x_j)$. Fine-tuning the passage encoder $E_z(.)$ is expensive because it requires re-indexing documents for fast MIPS. RAG does not find fine-tuning $E_z(.)$ necessary (as in ORQA), and updates only the query encoder and the generator.

An illustration of retrieval-augmented generation (RAG) architecture. (Image source: Lewis et al., 2020)

At decoding and test time, RAG-token can be evaluated via a beam search. RAG-seq cannot be decomposed into per-token likelihoods, so it runs beam search for each candidate document $z$ and selects the one with the best $p_\theta(y_i \vert x, z, y_{1:i-1})$.

The Fusion-in-Decoder method proposed by Izacard & Grave (2020) is also built on a pretrained T5. It resembles RAG, but differs in how it incorporates context into the decoder.

Retrieve the top $k$ related passages, each 100 words long, using BM25 or DPR.
Concatenate each retrieved passage and its title with the question, using special tokens such as question:, title:, and context: to mark the distinctions among content types.
Process each retrieved passage independently, and combine them later in the decoder. Independent encoding enables parallel computation. On the other hand, joint processing can encourage stronger aggregation across multiple evidence sources. This aggregation component is absent in extractive approaches.

Note that the pretrained LM is fine-tuned independently for each dataset.

Closed-book QA: Generative Language Model

Large language models are pretrained on large collections of unsupervised text. With sufficient parameters, they can memorize some factual knowledge in their weights. This makes it possible to perform question answering without explicit context, similar to a closed-book exam. In this setting, pretrained language models generate free text answers, without explicit reading comprehension.

The amount of computation used for training big language models of different sizes is getting big. (Image source: Brown et al., 2020).

Roberts et al. (2020) evaluates the practical utility of a language model by fine-tuning a pretrained model to answer questions without access to external context or knowledge. Specifically, they fine-tune the T5 language model (with the same architecture as the original Transformer) to answer questions without providing any additional information or context. This setup forces the language model to answer using “knowledge” internalized during pretraining.

T5 is first pre-trained with salient span masking and then fine-tuned for each QA dataset to produce answers in free text. (Image source: Roberts et al. 2020)

The original T5 models were pretrained on a multi-task mixture that included an unsupervised “masked language modeling” (MLM) tasks on the C4 (“Colossal Clean Crawled Corpus”) dataset, and were also fine-tuned jointly on supervised translation, summarization, classification, and reading comprehension tasks. Roberts, et al. (2020) took a pretrained T5 model and continued pretraining with salient span masking over Wikipedia, which was found to substantially improve ODQA performance. They then fine-tuned the model independently for each QA dataset.

With a pretrained T5 language model + continue pre-training with salient spans masking + fine-tuning for each QA dataset,

It can achieve competitive results in open-domain question answering without access to external knowledge.
Larger models deliver better performance. For example, a T5 with 11B parameters can match the performance of DPR with 3 BERT-base models, each with 330M parameters.

Notably, fine-tuning is not always required. GPT3 (Brown et al., 2020) is evaluated on closed-book question answering without any gradient updates or fine-tuning. In this evaluation, few-shot, one-shot, and zero-shot refer only to the number of demonstrations provided in the input context:

“few-shot learning”: GPT3 is given as many demonstrations as will fit in the model’s context window (typically 10 to 100).
“one-shot learning”: exactly one demonstration is provided.
“zero-shot learning”: no demonstrations are provided, and only a natural-language instruction is given.

Performance increases with model size. On TriviaQA, GPT3 evaluation with demonstrations can match or exceed the performance of state-of-the-art fine-tuned baselines.

GPT3's performance on TriviaQA grows smoothly with the model size. More demonstrations lead to better performance. (Image source: Brown et al., 2020).

Check out this cool example in OpenAI API playground viewer. The model can answer factal questions with short responses, and it avoids fabricating information when it does not know the answer. I added the last two questions and asked the model to reply with A:. The API is still in beta, so you may need to apply to join the wait list.

Q: Who is Batman?
A: Batman is a fictional comic book character.
##
Q: What is torsalplexity?
A: ?
##
Q: What is Devz9?
A: ?
##
Q: Who is George Lucas?
A: George Lucas is American film director and producer famous for creating Star Wars.
##
Q: What is the capital of California?
A: Sacramento.
##
Q: What orbits the Earth?
A: The Moon.
##
Q: Who is Fred Rickerson?
A: ?
##
Q: What is an atom?
A: An atom is a tiny particle that makes up everything.
##
Q: Who is Alvan Muntz?
A: ?
##
Q: What is Kozar-09?
A: ?
##
Q: How many moons does Mars have?
A: Two, Phobos and Deimos.
##
Q: What is COVID-19?
A: ?
##
Q: What is H1N1?
A: H1N1 is a strain of influenza.

Fast Maximum Inner Product Search (MIPS)

MIPS (maximum inner product search) is a key building block in many open-domain question answering models. In retriever-plus-reader or retriever-plus-generator frameworks, a large number of passages from the knowledge source are encoded and stored in memory. A retrieval model then queries this memory to find the top relevant passages, namely those with the maximum inner product with the question embedding.

Fast MIPS is required because the number of precomputed passage representations can be enormous. Several approaches can deliver fast MIPS at runtime, including asymmetric LSH, data-dependent hashing, and FAISS.

Language Model Pre-training

As discussed above, two pretraining tasks are particularly beneficial for QA.

Inverse Cloze Task (proposed by ORQA): The goal of Cloze Task is to predict masked-out text from its context. In contrast, the Inverse Cloze Task (ICT) predicts the context given a sentence. In QA settings, a random sentence can serve as a pseudo-question, and its surrounding context can serve as pseudo-evidence.
Salient Spans Masking (proposed by REALM): Salient span masking is a specialized form of the MLM task used in language model training. First, salient spans are identified using a tagger for named entities and a regular expression for dates. Next, one detected salient span is selected and masked. The learning objective is to predict the masked salient span.

Summary

Model	Retriever	Reader / Generator	Pre-training / Fine-tuning	End2end
DrQA	TF-IDF	Bi-directional LSTM	–	No
BERTserini	Aserini + BM25	BERT without softmax layer	Fine-tune with SQuAD	No
Multi-passage BERT	ElasticSearch + BM25	Multi-passage BERT + Passage ranker		No
R^3	Classic IR + Match-LSTM	Match-LSTM		Yes
ORQA	Dot product of BERT embeddings	BERT-RC	Inverse cloze task	Yes
REALM	Dot product of BERT embeddings	BERT-RC	Salient span masking	Yes
DPR	Dot product of BERT embeddings	BERT-RC	supervised training with QA pairs	Yes
DenSPI	Classic + Neural IR	–		Yes
T5 + SSM	–	T5	SSM on CommonCrawl data + Fine-tuning on QA data	Yes
GPT3	–	GPT3	NSP on CommonCrawl data	Yes
RAG	DPR retriever	BART		Yes
Fusion-in-Decoder	BM25 / DPR retriever	Tranformer		No

A comparison of performance of several QA models on common QA datasets. On TriviaQA, two columns of results are reported, on the open domain test set (left) and on the hidden test set (right). (Image source: Izacard & Grave, 2020).

Citation

Cited as:

Weng, Lilian. (Oct 2020). How to build an open-domain question answering system? Lil’Log. https://lilianweng.github.io/posts/2020-10-29-odqa/.

@article{weng2020odqa,
  title   = "How to Build an Open-Domain Question Answering System?",
  author  = "Weng, Lilian",
  journal = "lilianweng.github.io",
  year    = "2020",
  month   = "Oct"
  url     = "https://lilianweng.github.io/posts/2020-10-29-odqa/"
}

Appendix: QA Datasets

SQuAD 2.0: the Stanford question answering dataset.
RACE: a reading comprehension dataset compiled from English examinations written for middle school and high school students.
TREC QA: the TREC QA collections.
MS MARCO: a QA dataset that includes 100,000 real Bing questions paired with a human-generated answer.
CuratedTREC: based on benchmarks from the TREC QA tasks, curated by Baudis & Sedivy (2015).
Google Natural Questions: includes real user questions submitted to Google Search, along with answers identified in Wikipedia by annotators.
WebQuestions: created for knowledge-base QA, with answers restricted to Freebase entities.
WikiQA: uses Bing query logs as the source of questions; each question is then linked to a Wikipedia page that may contain the answer.
WikiMovies: includes movie-related questions derived from the OMDb and MovieLens databases, where questions can be answered using Wikipedia pages.
WikiReading: focuses on predicting textual values from the structured knowledge base Wikidata by reading the text of the corresponding Wikipedia articles.
TriviaQA: a reading comprehension dataset with 95K question-answer pairs authored by trivia enthusiasts, with multiple evidence documents independently collected for each question.
Jeopardy! Questions: includes more than 200,000 Jeopardy! questions.
DeepMind Q&A Dataset: question-answer pairs derived from CNN and Daily Mail articles.
bAbi: a comprehensive collection of datasets for text understanding released by Facebook.
FEVER: intended for fact extraction and verification.
SearchQA: question-answer pairs were crawled from from J! Archive, then augmented with text snippets from Google.
Quasar-T: a collection of open-domain trivia questions and answers gathered from various internet sources.
Quiz bowl: contains data from a trivia competition known as quiz bowl.
AmbigNQ: ambiguous questions selected from the NQ-OPEN dataset.
QA-Overlap: a collection of overlapped answers and questions between the training and test sets for Natural Questions, TriviaQA, and WebQuestions.