A Discrete Hard EM Approach for Weakly Supervised Question Answering

Introduction

A natural setting in many question answering (QA) tasks is to provide weak supervision to determine how the question should be answered given the evidence text. For example, as seen in Figure 1, TriviaQA answers are entities that can be mentioned multiple times in supporting documents, while DROP answers can be computed by deriving many different equations from numbers in the reference text. Such weak supervision is attractive because it is relatively easy to gather, allowing for large datasets, but complicates learning because there are many different spurious ways to derive the correct answer. It is natural to model such ambiguities with a latent variable during learning, but most prior work on reading comprehension has rather focused on the model architecture and used heuristics to map the weak signal to full supervision (e.g. by selecting the first answer span in TriviaQA (Joshi et al., 2017; Tay et al., 2018; Talmor and Berant, 2019)). Some models are trained with maximum marginal likelihood (MML) (Kadlec et al., 2016; Swayamdipta et al., 2018; Clark and Gardner, 2018; Lee et al., 2019), but it is unclear if it gives a meaningful improvement over the heuristics.

In this paper, we show it is possible to formulate a wide range of weakly supervised QA tasks as discrete latent-variable learning problems. First, we define a solution to be a particular derivation of a model to predict the answer (e.g. a span in the document or an equation to compute the answer). We demonstrate that for many recently introduced tasks, which we group into three categories as given in Table 1, it is relatively easy to precompute a discrete, task-specific set of possible solutions that contains the correct solution along with a modest number of spurious options. The learning challenge is then to determine which solution in the set is the correct one, while estimating a complete QA model.

We model the set of possible solutions as a discrete latent variable, and develop a learning strategy that uses hard-EM-style parameter updates. This algorithm repeatedly (i) predicts the most likely solution according to the current model from the precomputed set, and (ii) updates the model parameters to further encourage its own prediction. Intuitively, these hard updates more strongly enforce our prior beliefs that there is a single correct solution. This method can be applied to any problem that fits our weak supervision assumptions and can be used with any model architecture.

We experiment on six different datasets (Table 1) using strong task-specific model architectures (Devlin et al., 2019; Dua et al., 2019; Hwang et al., 2019). Our learning approach significantly outperforms previous methods which use heuristic supervision and MML updates, including absolute gains of 2–10%, and achives the state-of-the-art on five datasets. It outperforms recent state-of-the-art reward-based semantic parsing algorithms (Liang et al., 2018; Agarwal et al., 2019) by 13% absolute percentage on WikiSQL, strongly suggesting that having a small precomputed set of possible solutions is a key ingredient. Finally, we present a detailed analysis showing that, in practice, the introduction of hard updates encourages models to assign much higher probability to the correct solution.

Related Work

Large-scale reading comprehension (RC) tasks that provide full supervision for answer spans (Rajpurkar et al., 2016) have seen significant progress recently (Seo et al., 2017; Xiong et al., 2018; Yu et al., 2018a; Devlin et al., 2019). More recently, the community has moved towards more challenging tasks such as distantly supervised RC (Joshi et al., 2017), RC with free-form human generated answers (Kočiskỳ et al., 2018) and RC requiring discrete or multi-hop reasoning (Dua et al., 2019; Yang et al., 2018). These tasks introduce new learning challenges since the gold solution that is required to answer the question (e.g. a span or an equation) is not given.

Nevertheless, not much work has been done for this particular learning challenge. Most work on RC focuses on the model architecture and simply chooses the first span or a random span from the document (Joshi et al., 2017; Tay et al., 2018; Talmor and Berant, 2019), rather than modeling this uncertainty as a latent choice. Others maximize the sum of the likelihood of multiple spans (Kadlec et al., 2016; Swayamdipta et al., 2018; Clark and Gardner, 2018; Lee et al., 2019), but it is unclear if it gives a meaningful improvement. In this paper, we highlight the learning challenge and show that our learning method, independent of the model architecture, can give a significant gain. Specifically, we assume that one of mentions are related to the question and others are false positives because (i) this happens for most cases, as the first example in Table 2, and (ii) even in the case where multiple mentions contribute to the answer, there is often a single span which fits the question the best.

Semantic Parsing.

Method

In this section, we first formally define our general setup, which we will instantiate for specific tasks in Section 4 and then we describe our learning approach.

Let $x$ be the input of a QA system (e.g. a question and a document) and $y$ be the answer text (e.g. ‘Robert Schumann’ or ‘4’). We define a solution as a particular derivation that a model is supposed to produce for the answer prediction (e.g. a span in the document or an equation to compute the answer, see Table 2). Let $f$ denote a task-specific, deterministic function which maps a solution to the textual form of the answer (e.g. by simply returning the string associated with a particular selected mention or solving an equation to get the final number, see Table 2). Our goal is to learn a model (with parameters $\theta{}$) which takes an input $x$ and outputs a solution $z$ such that $f(z)=y$.

In a fully supervised scenario, a true solution $\bar{z}$ is given, and $\theta$ is estimated based on a collection of ($x,\bar{z}$) pairs. In this work, we focus on a weakly supervised setting in which $\bar{z}$ is not given and we define $Z_{\text{tot}}$ as a finite set of all the possible solutions. In the case that the search space is very large or infinite, we usually can approximate $Z_{\text{tot}}$ with a high coverage in practice. Then, we obtain $Z=\{z\in Z_{\text{tot}}:f(z)=y\}$ by enumerating all $z\in Z_{\text{tot}}$. This results a set of all the possible solutions that lead to the correct answer. We assume it contains one solution that we want to learn to produce, and potentially many other spurious ones. In practice, $Z$ is defined in a task-specific manner, as we will see in Section 4.

2 Learning Method

In a fully-supervised setting where $\bar{z}$ is given, we can learn $\theta$ by optimizing the negative log likelihood of $\bar{z}$ given the input $x$ with respect to $\theta{}$.

In our weak supervision scenario, the model has access to $x$ and $Z=\{z_{1},z_{2},\dots,z_{n}\}$, and the selection of the best solution in $Z$ can be modeled as a latent variable. We can compute the maximum marginal likelihood (MML) estimate, which marginalizes the likelihood of each $z_{i}\in Z$ given the input $x$ with respect to $\theta{}$. Formally,

is used to compute the objective as follows:

However, there are two major problems in the MML objective in our settings. First, MML can be maximized by assigning high probabilities to any subset of $z_{i}\in Z$; whereas in our problems, instances in $Z$ other than one correct $z$ are spurious solutions which the model should ideally assign very low probability. Second, in MML we optimize the sum over probabilities of $Z$ during training but typically predict the maximum probability solution during inference, creating a discrepancy between training and testing.

Task Setup

We apply our approach to three different types of QA tasks: multi-mention reading comprehension, RC with discrete reasoning and a semantic parsing task. In this section, we describe each task in detail: how we define a solution $z$ and pre-compute a set $Z$ based on input $x$ and answer $y$. The statistics of $|Z|$ and examples on each task are shown in Table 1 and Table 2 respectively.

Multi-mention reading comprehension naturally occurs in several QA tasks such as (i) distantly-supervised reading comprehension where a question and answer are collected first before the evidence document is gathered (e.g. TriviaQA), (ii) abstractive reading comprehension which requires a free-form text to answer the question (e.g. NarrativeQA), and (iii) open-domain QA where only question-answer pairs are provided.

Given a question $Q=[q_{1},\dots,q_{l}]$ and a document $D=[d_{1},\dots,d_{L}]$, where $q_{i}$ and $d_{j}$ denote the tokens in the question and document, the output $y$ is an answer text, which is usually mentioned multiple times in the document.

Previous work has dealt with this setting by detecting spans in the document through text matching (Joshi et al., 2017; Clark and Gardner, 2018). Following previous approaches, we define a solution $z$ as a span in the document. We obtain a set of possible solutions $Z=\{z_{1},\dots,z_{n}\}$ by finding exact match or similar mentions of $y$, where $z_{i}=(s_{i},e_{i})$ is a span of text with start and end token indices $s_{i}$ and $e_{i}$. Specifically,

where $g$ is a string matching function. If the answer is guaranteed to be a span in the document $D$, $g$ is a binary function which returns $1$ if two strings are the same, and otherwise. If the answer is free-form text, we choose $g$ as the ROUGE-L metric (Lin, 2004).

This complicates the learning because the given document contains many spans matching to the text, while most of them are not related to answering the question. As an example shown in Table 2, only the fourth span out of six is relevant to the question.

2 Reading Comprehension with Discrete Reasoning

Some reading comprehension tasks require reasoning in several discrete steps by finding clues from the document and aggregating them. One such example is mathematical reasoning, where the model must pick numbers from a document and compute an answer through arithmetic operations Dua et al. (2019).

In this task, the input is also a question $Q$ and a document $D$, and the output $y$ is given as a numeric value. We define a solution $z$ to be an executable arithmetic equation. Since there is an infinite set of potential equations, we approximate $Z_{\text{tot}}$ as a finite set of arithmetic equations with two numeric values and one operation, following Dua et al. (2019).This approximation covers 93% of the examples in the development set. Specifically,

where $N_{D}$ and $N_{Q}$ are all numeric values appearing in $D$ and $Q$, respectively, and $S$ are a set of predefined special numbers. Then

where $f$ is an execution function of equations.

Figure 1 shows an example $Z$ given a question and a document. We can see that one equation is correct, while the others are false positives which coincidentally lead to the correct answer.

3 SQL Query Generation

To evaluate if our training strategy generalizes to other weak supervision problems, we also study a semantic parsing task where a question and an answer are given but the logical form to execute the answer is not. In particular, we consider a task of answering questions about a given table by generating SQL queries.

The input is a question $Q=[q_{1},\dots,q_{l}]$ and a table header $H=[h_{1},\dots,h_{n_{L}}]$, where $q_{i}$ is a token, $h_{i}$ is a multi-token title of each column, and $n_{L}$ is the number of headers. The supervision is given as the SQL query result $y$, which is always a text string.

We define a solution to be an SQL query. Since the set of potential queries is infinite, we approximate $Z_{\text{tot}}$ as a set of non-nested SQL queries with at most three conditions.This approximation covers 99% of the examples in the development set. Specifically, given $A$ as a set of aggregating operators $\{\text{sum},\text{mean},\text{max},\text{min},\text{count}\}$ and $C$ as a set of possible conditions $\{(h,o,t)~{}\text{s.t. }h\in[1,n_{L}],o\in\{=,<,>\},t\in\text{spans in }Q\}$, we define ${Z}_{\text{tot}}$:

where $f$ is an SQL executor. The third example in Table 2 shows ${Z}$ may contain many spurious SQL querie, e.g. the third query in ${Z}$ coincidentally executes the answer because ‘John Long’ is ranked first among all the guards in alphabetical order.

Experiments

We experiment on a range of question answering tasks with varied model architectures to demonstrate the effectiveness of our approach. Built on top of strong base models, our learning method is able to achieve state-of-the-art on NarrativeQA, TriviaQA-open, NaturalQuestions-open, DROP${}_{\text{num}}$ and WikiSQL.

We experiment on two reading comprehension datasets and two open-domain QA datasets. For reading comprehension, we evaluate on TriviaQA (Wikipedia) (Joshi et al., 2017) and NarrativeQA (summary) (Kočiskỳ et al., 2018).

For open-domain QA, we follow the settings in Lee et al. (2019) and use the QA pairs from TriviaQA-unfiltered (Joshi et al., 2017) and Natural Questions (Kwiatkowski et al., 2019) with short answers and discard the given evidence documents. We refer to these two datasets as TriviaQA-open and NaturalQuestions-open. Following Lee et al. (2019), we treat the dev set as the test set and split the train set into 90/10 for training and development. Datasets and their split can be downloaded from https://bit.ly/2HK1Fqn.

We experiment with three learning methods as follows.

We use uncased version of BERT${}_{\text{base}}$. For all datasets, we split documents into a set of segments up to 300 tokens because BERT limits the size of the input. We use batch size of $20$ for two reading comprehension tasks and $192$ for two open-domain QA tasks. Following Clark and Gardner (2018), we filter a subset of segments in TriviaQA through TF-IDF similarity between a segment and a question to maintain a reasonable length. For open-domain QA tasks, we retrieve 50 Wikipedia articles through TF-IDF (Chen et al., 2017) and further run BM25 (Robertson et al., 2009) to retrieve 20 (for train) or 80 (for development and test) paragraphs. We try 10, 20, 40 and 80 paragraphs on the development set to choose the number of paragraphs to use on the test set.

Results.

Table 3 compares the results of baselines, our method and the state-of-the-art on four datasets.For NarrativeQA, we compare with models trained on NarrativeQA only. For open-domain QA, we only compare with models using pipeline approach. First of all, we observe that First-Only is a strong baseline across all the datasets. We hypothesize that this is due to the bias in the dataset that answers are likely to appear earlier in the paragraph. Second, while MML achieves comparable result to the First-Only baseline, our learning method outperforms others by $2+$ F1/ROUGE-L/EM consistently on all datasets. Lastly, our method achieves the new state-of-the-art on NarrativeQA, TriviaQA-open and NaturalQuestions-open, and is comparable to the state-of-the-art on TriviaQA, despite our aggressive truncation of documents.

2 Reading Comprehension with Discrete Reasoning

We experiment on a subset of DROP (Dua et al., 2019) with numeric answers (67% of the entire dataset) focusing on mathematical reasoning. We refer to this subset as DROP${}_{\text{num}}$. The current state-of-the-art model is an augmented version of QANet Yu et al. (2018a) which selects two numeric values from the document or the question and performs addition or subtraction to get the answer. The equation to derive the answer is not given, and Dua et al. (2019) adopted the MML objective.

We truncate the document to be up to 400 words. We use the batch size of $14$ and $10$ for QANet and BERT, respectively.

Results.

Table 3 shows the results on DROP${}_{\text{num}}$. Our training strategy outperforms the First-Only baseline and MML by a large margin, consistently across two base models. In particular, with BERT, we achieve an absolute gain of 10%.

3 SQL Query Generation

Finally, we experiment on the weakly-supervised setting of WikiSQL (Zhong et al., 2017), in which only the question & answer pair is used and the SQL query $(z)$ is treated as a latent variable.

We compare with both traditional and recently-developed reward-based algorithms for weak supervision, including beam-based MML (MML which keeps a beam during training), conventional hard EMThis method differs from ours in that it does not have a precomputed set, and uses a beam of candidate predictions to execute for each update., REINFORCE (Williams, 1992), iterative ML (Liang et al., 2017; Abolafia et al., 2018) and a family of MAPO (Memory-augmented policy optimization) (Liang et al., 2018; Agarwal et al., 2019). For a fair comparison, we only consider single models without execution-guided decoding.

We adopt the same set of hyperparameters as in Hwang et al. (2019), except that we change the batch size to 10 and truncate the input to be up to 180 words.

Results.

Table 4 shows that our training method significantly outperforms all the weakly-supervised learning algorithms, including 10% gain over the previous state of the art. These results indicate that precomputing a solution set and training a model through hard updates play a significant role to the performance. Given that our method does not require SQL executions at training time (unlike MAPO), it provides a simpler, more effective and time-efficient strategy. Comparing to previous models with full supervision, our results are still on par and outperform most of the published results.

Analysis

In this section, we will conduct thorough analyses and ablation studies, to better understand how our model learns to find a solution from a precomputed set of possible solutions. We also provide more examples and analyses in Appendix C.

Figure 2 shows a breakdown of the model accuracy with respect to the size of a solution set ($|Z|$) at test time. We observe that the model with our training method outperforms the model with MML objective consistently across different values of $|Z|$. The gap between MML and our method is marginal when $|Z|=0$ or $1$, and gradually increases as $|Z|$ grows.

Varying the size of solution set at training.

To see how our learning method works with respect to the size of a solution set ($|Z|$) of the training data, particularly with large $|Z|$, we take 5 subsets of the training set on WikiSQL with $|Z|=3,10,30,100,300$. We train a model with those subsets and evaluate it on the original development set, both with our training method and MML objective. Figure 3 shows statistics of each subset and results. We observe that (i) our learning method outperforms MML consistently over different values of $|Z|$, and (ii) the gain is particularly large when $|Z|>3$.

Model predictions over training.

We analyze the top 1 prediction and the likelihood of $z\in Z$ assigned by the model on DROP${}_{\text{num}}$ with different number of training iterations (steps from 1k to 32k). Table 5 shows one example on DROP${}_{\text{num}}$ with the answer text ‘4’, along with the model’s top 1 prediction and a subset of $Z$. We observe that the model first begins by assigning a small, uniform probability distribution to $Z$, but gradually learns to favor the true solution. The model sometimes gives the wrong prediction—for example, at $t=16$k, and changes its prediction from the true solution to the wrong solution, ‘37-36’—but again changes its prediction to be a true solution afterward. In addition, its intermediate wrong solution, ‘37-36’ indicates the model was confused with distinguishing the longest field goal of Rob Bironas (40 vs. 37), which is an understandable mistake.

We also compare the predictions from the model with our method to those from the model with MML, which is shown in Appendix C.

Quality of the predicted solution.

We analyze if the model outputs the correct solution, since the solution executing the correct answer could be spurious. First, on NarrativeQA and DROP${}_{\text{num}}$, we manually analyze 50 samples from the development set and find that 98% and 92% of correct cases produce the correct solution respectively. Next, on WikiSQL, we compare the predictions from the model to the annotated SQL queries on the development set. This is possible because gold SQL queries are available in the dataset for the full supervision. Out of 8,421 examples, 7,110 predictions execute the correct answers. Among those, 88.5% of the predictions are exactly same as the annotated queries. Others are the cases where (i) both queries are correct, (ii) the model prediction is correct but the annotated query is incorrect, and (iii) the annotated query is correct and the model prediction is spurious. We show a full analysis in Appendix C.

Robustness to the noise in |𝒁|𝒁\bm{|Z|}.

Sometimes noise arises during the construction of $|Z|$, such as $|Z|$ constructed based on ROUGE-L for NarrativeQA. To explore the effect of noise in $Z$, we experiment with more noisy solution set by picking all the spans with scores that is equal to or larger than the 5th highest. The new construction method increases $|Z|$ from 4.3 to 7.1 on NarrativeQA. The result by MML objective drops significantly (56.07$\rightarrow{}$51.14) while the result by ours drops marginally (58.77$\rightarrow{}$57.97), suggesting that MML suffers more with a noisier $Z$ while ours is more robust.

Conclusion

In this paper, we demonstrated that, for many QA tasks which only provide the answer text as supervision, it is possible to precompute a discrete set of possible solutions that contains one correct option. Then, we introduced a discrete latent variable learning algorithm which iterates a procedure of predicting the most likely solution in the precomputed set and further increasing the likelihood of that solution. We showed that this approach significantly outperforms previous approaches on six QA tasks including reading comprehension, open-domain QA, discrete reasoning task and semantic parsing, achieving absolute gains of 2–10% and setting the new state-of-the-art on five well-studied datasets.

This research was supported by ONR (N00014-18-1-2826, N00014-17-S-B001), DARPA N66001-19-2-403, NSF (IIS-1616112, IIS-1252835, IIS-1562364), ARO (W911NF-16-1-0121), an Allen Distinguished Investigator Award, Samsung GRO and gifts from Allen Institute for AI, Google and Amazon.

The authors would like to thank the anonymous reviewers, Eunsol Choi, Christopher Clark, Victor Zhong and UW NLP members for their valuable feedback.

References

Appendix A Model details

The following paragraphs describe (i) BERT extractive model used for multi-mention RC (Section 5.1) and (ii) BERT sequence tagging model for discrete reasoning task (Section 5.2), respectively. For QANet for discrete reasoning and the model for SQL generation (Section 5.3), we use the open-sourced code of the original implementationhttps://github.com/allenai/allennlp/blob/master/allennlp/models/reading_comprehension/naqanet.py and https://github.com/naver/sqlova of Dua et al. (2019) and Hwang et al. (2019) and do not make any modification except the objective function, so we refer to original papers.

All implementations are done in Pytorch (Paszke et al., 2017). For BERT, we modify the open-sourced implementation in PyTorchhttps://github.com/huggingface/pytorch-pretrained-BERT and use the uncased version of BERT${}_{\text{base}}$.

The model architecture is closed to that of Min et al. (2019) and Alberti et al. (2019), where the model operates independently on each paragraph, and selects the best matching paragraph and its associated answer span.

The input is a question $Q$ and a set of paragraphs $\{P_{1},\dots,P_{N}\}$, and the desired output is a span from one of paragraphs. Since our goal is to compute a probability of a specific span, $z$, let’s say $z$ is $s$-th through $e$-th word in $k$-th paragraph.

The model receives a question $Q$ and a single paragraph $P_{i}$ in parallel. Then, $S_{i}=Q:{\tt[SEP]}:P$, a list of $m+n_{i}+1$ words, where : indicates a concatenation, ${\tt[SEP]}$ is a special token, $m$ is the length of $Q$, and $n_{i}$ is the length of $P_{i}$. This $S_{i}$ is fed into BERT:

where $h$ is the hidden dimension of BERT. Then,

Finally, the probability of $z$, $s$-th through $e$-th word in $i$-th paragraph, is obtained by:

where $p^{d}$ denotes $d$-th element of the vector $p$.

Sequence Tagging model for discrete reasoning

The basic idea of the model is closed to that of Dua et al. (2019). The input is a question $Q$ and a paragraph $P$. Our goal is to compute a probability of an equation, $z=(o_{1},n_{1},o_{2},n_{2})$, where $o_{1},o_{2}\in\{+,-,*0.01\}$ and $n_{1},n_{2}\in N_{P}\cup N_{Q}\cup S$, $N_{P}$ and $N_{Q}$ are all numeric values appearing in $P$ and $Q$, and $S$ are a set of predefined special numbers.$S=\{1,2,3,4,5,7,10,12,100,1000\}$.

First, BERT encodings of the question and the paragraph is obtained via

where : indicates a concatenation, ${\tt[SEP]}$ is a special token, $m$ is the length of $Q$, $n$ is the length of $P$, and $h$ is the hidden dimension of BERT. Then,

Appendix B Annealing

Appendix C Examples

To see if the prediction from the model is the correct solution to derive the answer, we analyze outputs from the model.

Table 7 shows one example from TriviaQA where the answer text (Montgomery) is mentioned in the paragraph multiple times. Predictions from the model with our training method and that with MML objective are shown in the red text and the blue text, respectively. The span predicted by the model with our method actually answers to the question, while other spans with the answer text is not related to the question.

DROPnumnum\bm{{}_{\text{num}}}.

Table 8 shows predictions from the model with our method and that with MML objective over training procedure. We observe that the model with our method learns to assign a high probability to the best solution (‘34-24’), while the model with MML objective fails to do so. Another notable observation is that the model with our method assign sparse distribution of likelihood over $Z$, compared to the model with MML objective. We quantitatively define sparsity as

(Hurley and Rickard, 2009) and show that the model with our method gives higher sparsity than the model with MML (59 vs. 36 with $\epsilon=10^{-3}$, 54 vs. 17 with $\epsilon=10^{-4}$ on DROP).

WikiSQL.

WikiSQL provides the annotated SQL queries, makes it easy to compare the predictions from the model to the annotated queries. Out of 8421 examples from the development set, 7110 predictions execute the correct answers. Among those, 6296 predictions are exactly same as the annotated queries. For cases where the predictions execute the correct answers but are not exactly same as the groundtruth queries, we show four examples in Table 9. In the first example, both the annotated query and the prediction are correct, because the selected column does not matter for counting. Similarly in the second example, both queries are correct because Capital (exonym) and Capital (endonym) both indicate the capital city. In the third example, the prediction makes more sense than the annotated query because the question does not imply anything about min. In the last example, the annotated query makes more sense than the prediction because the prediction misses Ship Type = battleship. We conjecture that the model might learn to ignore some information in the question if the table header implies the table is specific about that information, hence does not need to condition on that information.