Break It Down: A Question Understanding Benchmark

Introduction

Recently, increasing work has been devoted to models that can reason and integrate information from multiple parts of an input. This includes reasoning over images Antol et al. (2015); Johnson et al. (2017); Suhr et al. (2019); Hudson and Manning (2019), paragraphs Dua et al. (2019), documents Welbl et al. (2018); Talmor and Berant (2018); Yang et al. (2018), tables Pasupat and Liang (2015) and more. Question answering (QA) is commonly used to test the ability to reason, where a complex natural language question is posed, and is to be answered given a particular context (text, image, etc.). Although questions often share structure across tasks and modalities, understanding the language of complex questions has thus far been dealt within each task in isolation. Consider the questions in Figure 1, all of which express operations such as fact chaining and counting. Additionally, humans can take a complex question and break it down into a sequence of simpler questions even when they are unaware of what or where the answer is. This ability, to compose and decompose questions, lies at the heart of human language Pelletier (1994) and allows us to tackle previously unseen problems. Thus, better question understanding models should improve performance and generalization in tasks that require multi-step reasoning or that do not have access to substantial amounts of data.

In this work we propose question understanding as a standalone language understanding task. We introduce a formalism for representing the meaning of questions that relies on question decomposition, and is agnostic to the information source. Our formalism, Question Decomposition Meaning Representation (QDMR), is inspired by database query languages (SQL; SPARQL), and by semantic parsing Zelle and Mooney (1996); Zettlemoyer and Collins (2005); Clarke et al. (2010), in which questions are given full meaning representations.

We express complex questions via simple (“atomic”) questions that can be executed in sequence to answer the original question. Each atomic question can be mapped into a small set of formal operations, where each operation either selects a set of entities, retrieves information about their attributes, or aggregates information over entities. While this has been formalized in knowledge-base (KB) query languages Chamberlin and Boyce (1974), the same intuition can be applied to other modalities, such as images and text. QDMR abstracts away the context needed to answer the question, allowing in principle to query multiple sources for the same question.

In contrast to semantic parsing, QDMR operations are expressed through natural language, facilitating annotation at scale by non-experts. Figure 1 presents examples of complex questions on three different modalities. The middle box lists the natural language decompositions provided for each question, and the bottom box displays their corresponding formal queries.

QDMR serves as the formalism for creating Break, a question decomposition dataset of 83,978 questions over ten datasets and three modalities. Break is collected via crowdsourcing, with a user interface that allows us to train crowd workers to produce quality decompositions (§3). Validating the quality of annotated structures reveals 97.4% to be correct (§4).

We demonstrate the utility of QDMR in two setups. First, we regard the task of open-domain QA over multi-hop questions from the HotpotQA dataset. Combining QDMR structures in Break with an RC model Min et al. (2019b) improves F1 from 43.3 to 52.4 (§5). Second, we show that decompositions in Break possess high annotation consistency, which indicates that annotators produce high-quality QDMRs (§4.3). In §6 we discuss how these QDMRs can be used as a strong proxy for full logical forms in semantic parsing.

We use Break to train a neural QDMR parser that maps questions into QDMR representations, based on a sequence-to-sequence model with copying Gu et al. (2016). Manual analysis of generated structures reveals an accuracy of 54%, showing that automatic QDMR parsing is possible, though still far from human performance (§7).

Proposing the task of question understanding and introducing the QDMR formalism for representing the meaning of questions (§2)

The Break dataset, which consists of 83,978 examples sampled from 10 datasets over three distinct information sources (§3)

Showing how QDMR can be used to improve open-domain question answering (§5), as well as alleviate the burden of annotating logical forms in semantic parsing (§6)

A QDMR parser based on a sequence-to-sequence model with copying mechanism (§7)

The Break dataset, models and entire codebase are publicly available at: https://allenai.github.io/Break/.

Question Decomposition Formalism

In this section we define the QDMR formalism for domain agnostic question decomposition.

QDMR is primarily inspired by SQL Codd (1970); Chamberlin and Boyce (1974). However, while SQL was designed for relational databases, QDMR also aims to capture the meaning of questions over unstructured sources such as text and images. Thus, our formalism abstracts away from SQL by assuming an underlying “idealized” KB, which contains all entities and relations expressed in the question. This abstraction enables QDMR to be unrestricted to a particular modality, with its operators to be executed also against text and images, while allowing in principle to query multiple modalities for the same question.A system could potentially answer “Name the political parties of the most densely populated country”, by retrieving “the most densely populated country” using a database query, and “the political parties of #1” via an RC model.

Given a question $x$, its QDMR is a sequence of $n$ steps, $\textbf{s}=\langle s^{1},...,s^{n}\rangle$, where each step $s^{i}$ corresponds to a single query operator $f^{i}$ (see Table 1). A step, $s^{i}$ is a sequence of tokens, $s^{i}=(s^{i}_{1},...,s^{i}_{m_{i}})$, where a token $s^{i}_{k}$ is either a word from a predefined lexicon $L_{x}$ (details in §3) or a reference token, referring to the result of a previous step $s^{j}$, where $j<i$. The last step, $s^{n}$ returns the answer to $x$.

Decomposition Graph

QDMR structures can be represented as a directed acyclic graph (DAG), used for evaluating QDMR parsing models (§7.1). Given QDMR, $\textbf{s}=\langle s^{1},...,s^{n}\rangle$, each step $s^{i}$ is a node in the graph, labeled by its sequence of tokens and index $i$. Edges in the graph are induced by reference tokens to previous steps. Node $s^{i}$ is connected by an incoming edge $(s^{j},s^{i})$, if $ref[s^{j}]\in(s^{i}_{1},...,s^{i}_{m_{i}})$. That is, if one of the tokens in $s^{i}$ is a reference to $s_{j}$. Figure 2 displays a sequence of QDMR steps, represented as a DAG.

QDMR Operators

We now formally define each QDMR operator and provide concrete examples in Table 1.

FILTER: Filters a set of objects so that it follows the condition expressed by $w$:

PROJECT: Computes the objects that relate to input entities $S_{e}$ with the relation expressed by $w$,

GROUP: Receives a set of “keys”, $S_{e}$ and a set of corresponding “values”, $S_{o}$. It outputs a set of numbers, each corresponding to a key $e\in S_{e}$. Each number results from applying aggregate, $w_{agg}$ to the subset of values corresponding to $e$.

SUPERLATIVE: Receives entity set $S_{e}$ and number set $S_{n}$. Each number $n\in S_{n}$ is the result of a mapping from an entity $e\in S_{e}$. It returns a subset of $S_{e}$ for which the corresponding number is either highest/lowest as indicated by $w_{sup}$.

COMPARATIVE: Receives entity set $S_{e}$ and number set $S_{n}$. Each $n\in S_{n}$ is the result of a mapping from an $e\in S_{e}$. It returns a subset of $S_{e}$ for which the comparison with $n^{\prime}$, represented by $w_{com}$, holds.

UNION: Denotes the union of object sets: $\mathbf{union}(S^{1}_{o},S^{2}_{o})=S^{1}_{o}\cup S^{2}_{o}$.

DISCARD: Denotes the set difference of two objects sets: $\mathbf{discard}(S^{1}_{o},S^{2}_{o})=S^{1}_{o}\setminus S^{2}_{o}$.

INTERSECTION: Computes the intersection of its entity sets and returns all objects which relate to the entities with the relation expressed by $w$.

SORT: Orders a set of entities according to a corresponding set of numbers. Each number $n_{i}$ is the result of a mapping from entity $e_{i}$.

High-level Decompositions

In QDMR, each step corresponds to a single logical operator. In certain contexts, a less granular decomposition might be desirable, where sub-structures containing multiple operators could be collapsed to a single node. This can be easily achieved in QDMR by merging certain adjacent nodes in its DAG structure. When examining existing RC datasets Yang et al. (2018); Dua et al. (2019), we observed that long spans in the question often match long spans in the text, due to existing practices of generating questions via crowdsourcing. In such cases, decomposing the long spans into multiple steps and having an RC model process each step independently, increases the probability of error. Thus, to promote the usefulness of QDMR for current RC datasets and models, we introduce high-level QDMR, by merging the following operators:

SELECT + PROJECT on named entities: For the question, “What is the birthdate of Jane?” its high-level QDMR would be “return the birthdate of Jane” as opposed to the more granular, “return Jane; return birthdate of #1”.

SELECT + FILTER: Consider the first step of the example in Figure 3. It contains both a SELECT operator (“return actress”) as well as two FILTER conditions (“that played…”, “on the TV sitcom…”).

FILTER + GROUP + COMPARATIVE: Certain high-level FILTER steps contain implicit grouping and comparison operations. E.g., “return yard line scores in the fourth quarter; return #1 that both teams scored from”. Step #2 contains an implicit GROUP of team per yard line and a COMPARATIVE returning the lines where exactly two teams scored.

We provide both granular and high-level QDMRs for a random subset of RC questions (see Table 3). The concrete utility of high-level QDMR to open-domain QA is presented in §5.

Data Collection

Our annotation pipeline for generating Break consisted of three phases. First, we collected complex questions from existing QA benchmarks. Second, we crowdsourced the QDMR annotation of these questions. Finally, we validated worker annotations in order to maintain their quality.

Questions in Break were randomly sampled from ten QA datasets over the following tasks (Table 3):

Semantic Parsing: Mapping natural language utterances into formal queries, to be executed on a target KB Price (1990); Zelle and Mooney (1996); Li and Jagadish (2014); Yu et al. (2018).

Reading Comprehension (RC): Questions that require understanding of a text passage by reasoning over multiple sentences Talmor and Berant (2018); Yang et al. (2018); Dua et al. (2019); Abujabal et al. (2019).

Visual Question Answering (VQA): Questions over images that require both visual and numerical reasoning skills Johnson et al. (2017); Suhr et al. (2019).

All questions collected were composed by human annotators.Except for ComplexWebQuestions (CWQ), where annotators paraphrased automatically generated questions. HotpotQA questions were all sampled from the hard split of the dataset.

QDMR Annotation

A key question is whether it is possible to train non-expert annotators to produce high-quality QDMRs. We designed an annotation interface (Figure 4), where workers are first given explanations and examples on how to identify and phrase each of the operators in Table 1. Then, workers decompose questions into a list of steps, where they are only allowed to use words from a lexicon $L_{x}$, which contains: (a) words appearing in the question (or their automatically computed inflections), (b) words from a small pre-defined list of 66 function word such as, ‘if’, ‘on’, ‘for each’, or (c) reference tokens that refer to the results of a previous step. This ensures that the language used by workers is consistent across examples, while being expressive enough for the decomposition. Our annotation interface presents workers with the question only, so they are agnostic to the original modality of the question. The efficacy of this process is explored in §4.2.

We used Amazon Mechanical Turk to crowdsource QDMR annotation. In each task, workers decomposed a single question, paying them $0.4, which amounts to an average pay of$12 per hour. Overall, we collected 83,978 examples using 64 distinct workers. The dataset was partitioned into train/development/test sets following the partitions in the original datasets. During partition, we made sure that development and test samples do not share the same context.

Worker Validation

To ensure worker quality, we initially published qualification tasks, open to all United States’ workers. The task required workers to carefully review the annotation instructions and decompose 10 example questions. The examples were selected so that each QDMR operation should appear in at least one of their decompositions (Table 1). In total, 64 workers were able to correctly decompose at least 8 examples and were qualified as annotators. To validate worker performance over time, we conducted random validations of annotations. Over 9K annotations were reviewed by experts throughout the annotation process. Only workers that consistently produced correct QDMRs for at least 90% of their tasks were allowed to continue as annotators.

Dataset Analysis

This section examines the properties of collected QDMRs in Break and analyzes their quality.

Overall, Break contains 83,978 decompositions, including 60,150 QDMRs and 23,828 examples with high-level QDMRs, which are exclusive to text modalities. Table 3 shows data is proportionately distributed between questions over structured (DB) and unstructured modalities (text, images).

The distribution of QDMR operators is presented in Table 4, detailing the prevalence of each query operatorRegarding the three merged operators of high-level QDMRs (§2), the first two operators are treated as SELECT, while the third is considered a FILTER. (we automatically compute this distribution, as explained in §4.3). SELECT and PROJECT are the most common operators. Additionally, at least 10% of QDMRs contain operators such as GROUP and COMPARATIVE which entail complex reasoning, in contrast to high-level QDMRs, where such operations are rare. This distinction sheds light on the reasoning types required for answering RC datasets (high-level QDMR) compared to more structured tasks (QDMR).

Table 5 details the distribution of QDMR sequence length. Most decompositions in QDMR include 3-6 steps, while high-level QDMRs are much shorter, as a single SELECT often finds an entity described by a long noun phrase (see §2).

2 Quality Analysis

We describe the process of estimating the correctness of collected QDMR annotations. Similar to previous works Yu et al. (2018); Kwiatkowski et al. (2019) we use expert judgements, where the experts had prepared the guidelines for the annotation task. Given a question and its annotated QDMR, $(q,\textbf{s})$ the expert determines the correctness of s using one of the following categories:

Correct ($\mathcal{C}$): If s constitutes a list of QDMR operations that lead to correctly answering $q$.

Granular ($\mathcal{C_{G}}$): If s is correct and none of its operators can be further decomposed.For high-level QDMRs, the merged operators (§2) are considered to be fully decomposed.

Incorrect ($\mathcal{I}$): If s is in neither $\mathcal{C}$ nor $\mathcal{C_{G}}$.

Examples of these expert judgements are shown in Figure 5. To estimate expert judgement of correctness, we manually reviewed a random sample of 500 QDMRs from Break. We classified 93.8% of the samples in $\mathcal{C_{G}}$ and another 3.6% in $\mathcal{C}$. Thus, 97.4% of the samples constitute a correct decomposition of the original question. Workers have somewhat struggled with decomposing superlatives (e.g., “biggest sphere”), as evident from the first question in Figure 5. Collected QDMRs displayed similar estimates of $\mathcal{C}$, $\mathcal{C_{G}}$ and $\mathcal{I}$, regardless of their modality (DB, text or image).

3 Annotation Consistency

As QDMR is expressed using natural language, it introduces variability into its annotations. We wish to validate the consistency of collected QDMRs, i.e., whether we can correctly infer the formal QDMR operator ($f^{i}$) and its arguments from each step ($s^{i}$). To infer these formal representations, we developed an algorithm that goes over the QDMR structure step-by-step, and for each step $s^{i}$, uses a set of predefined templates to identify $f^{i}$ and its arguments, expressed in $s^{i}$. This results in an execution graph (Figure 2), where the execution result of a parent node serves as input to its child. Figure 1 presents three QDMR decompositions along with the formal graphs output by our algorithm (lower box). Each node lists its operator (e.g., GROUP), its constant input listed in brackets (e.g., count) and its dynamic input which are the execution results of its parent nodes.

Overall, 99.5% of QDMRs had all their steps mapped into pseudo-logical forms by our algorithm. To evaluate the correctness of the mapping algorithm, we randomly sampled 350 logical forms, and examined the structure of the formulas, assuming that words copied from the question correspond to entities and relations in an idealized KB (see §2). Of this sample, 99.4% of its examples had all of their steps, $s^{i}$, correctly mapped to the corresponding $f^{i}$. Overall, 93.1% of the examples were of fully accurate logical forms, with errors being due to QDMRs that were either incorrect or not fully decomposed ($\mathcal{I}$, $\mathcal{C}$ in §4.2). Thus, a rule-based algorithm can map more than 93% of the annotations into a correct formal representation. This shows our annotators produced consistent and high-quality QDMRs. Moreover, it suggests that non-experts can annotate questions with pseudo-logical forms, which can be used as a cheap intermediate representation for semantic parsers Yih et al. (2016), further discussed in §6.

QDMR for Open-domain QA

A natural setup for QDMR is in answering complex questions that require multiple reasoning steps. We compare models that exploit question decompositions to baselines that do not. We use the open-domain QA (“full-wiki") setting of the HotpotQA dataset Yang et al. (2018): Given a question, the QA model retrieves the relevant Wikipedia paragraphs and answers the question using these paragraphs.

We compare BreakRC, a model that utilizes question decomposition to BERTQA, a standard QA model, based on BERT Devlin et al. (2019), and present Combined, an approach that enjoys the benefits of both models.

Algorithm 1 describes the BreakRC model which uses high-level QDMR structures for answering open-domain multi-hop questions. We assume access to an IR model and an RC model, and denote by $\textsc{Answer}(\cdot)$ a function that takes a question as input, runs the IR model to obtain paragraphs, and then feeds those paragraphs as context for an RC model that returns a distribution over answers.

Given an input QDMR, $\textbf{s}=\langle s^{1},...,s^{n}\rangle$, iterate over s step-by-step and perform the following. First, we extract the operation (line 4) and the previous steps referenced by $s^{i}$ (line 5) . Then, we compute the answer to $s^{i}$ conditioned on the extracted operator. For SELECT steps, we simply run the $\textsc{Answer}(\cdot)$ function. For PROJECT steps, we substitute the reference to the previous step in $s^{i}$ with its already computed answer, and then run $\textsc{Answer}(\cdot)$. For FILTER steps,INTERSECTION steps are handled in a manner similar to FILTER, but we omit the exact description for brevity. we use a simple rule to extract a “normalized question”, $\hat{s}^{i}$ from $s^{i}$ and get an intermediate answer $ans_{\text{tmp}}$ with $\textsc{Answer}(\hat{s}^{i})$. We then “intersect” $ans_{\text{tmp}}$ with the referenced answer by multiplying the probabilities provided by the RC model and normalizing. For COMPARISON steps, we compare, with a discrete operation, the numbers returned by the referenced steps. The final answer is the highest probability answer of step $s^{n}$.

As our IR model we use bigram TF-IDF, proposed by Chen et al. (2017). Since the RC model is run on single-hop questions, we use the BERT-based RC model from Min et al. (2019b), trained solely on SQuAD Rajpurkar et al. (2016).

BERTQA Baseline

As BreakRC exploits question decompositions, we compare it with a model that does not. BERTQA receives as input the original natural language question, $x$. It uses the same IR model as BreakRC to retrieve paragraphs for $x$. For a fair comparison, we set its number of retrieved paragraphs such that it is identical to BreakRC (namely, 10 paragraphs for each QDMR step that involves IR). Similar to BreakRC, retrieved paragraphs are fed to a pretrained BERT-based RC model Min et al. (2019b) to answer $x$. In contrast to BreakRC, that is trained on SQuAD, BERTQA is trained on the target dataset (HotpotQA), giving it an advantage over BreakRC.

A Combined Approach

Last, we present an approach that combines the strengths of BreakRC and BERTQA. In this approach, we use the QDMR decomposition to improve retrieval only. Given a question $x$ and its QDMR s, we run BreakRC on s, but in addition to storing answers, we also store all the paragraphs retrieved by the IR model. We then run BERTQA on the question $x$ and the top-10 paragraphs retrieved by BreakRC, sorted by their IR ranking. This approach resembles that of Qi et al. (2019).

The advantage of Combined is that we do not need to develop an answering procedure for each QDMR operator separately, which involves different discrete operations such as comparison and intersection. Instead, we use BreakRC to retrieve contexts, and an end-to-end approach to learn how to answer the question directly. This can often handle operators not implemented in BreakRC, like BOOLEAN and UNION.

Dataset

To evaluate our models, we use all 2,765 QDMR annotated examples of the HotpotQA development set found in Break. PROJECT and COMPARISON type questions account for 48% and 7% of examples respectively.

2 Results

Table 6 shows model performance on HotpotQA. We report EM and F1 using the official HotpotQA evaluation script. IR, measures the percentage of examples in which the IR model successfully retrieved both of the “gold paragraphs” necessary for answering the multi-hop question. To assess the potential utility of QDMR, we report results for $\textsc{BreakRC}^{\textsc{G}}$, which uses gold QDMRs, and $\textsc{BreakRC}^{\textsc{P}}$, which uses QDMRs predicted by a Copynet parser (§7.2).

Retrieving paragraphs with decomposed questions substantially improves the IR metric from 46.3 to 59.2 ($\textsc{BreakRC}^{\textsc{G}}$), or 52.5 ($\textsc{BreakRC}^{\textsc{P}}$). This leads to substantial gains in EM and F1 for $\textsc{Combined}^{\textsc{G}}$ (43.3 to 52.4) and $\textsc{Combined}^{\textsc{P}}$ (43.3 to 49.3). The EM and F1 of $\textsc{BreakRC}^{\textsc{G}}$ are only slightly higher than BERTQA since BreakRC does not handle certain operators, such as BOOLEAN steps (9.4% of the examples).

The majority of questions in HotpotQA combine SELECT operations with either PROJECT (also called “bridge” questions), COMPARISON, or FILTER. PROJECT and COMPARISON questions (Figure 6) were shown to be less susceptible to reasoning shortcuts, i.e. they necessitate multi-step reasoning Chen and Durrett (2019); Jiang and Bansal (2019); Min et al. (2019a). In Table 7 we report BreakRC results on these question types, where it notably outperforms BERTQA.

In BreakRC, multiple IR queries are issued, one at each step. To examine whether these multiple queries were the cause for performance gains, we built IR-NP: A model that issues multiple IR queries, one for each noun phrase in the question. Similar to Combined, the question and union of retrieved paragraphs are given as input to BERTQA. We observe that Combined substantially outperforms IR-NP, indicating that the structure of QDMR, rather than multiple IR queries, has led to improved performance.Issuing an IR query over each “content word” in the question, instead of each noun phrase, led to poor results.

To test whether QDMR is better than a simple rule-based decomposition algorithm, we developed a model that decomposes a question by applying a set of predefined rules over the dependency tree of the question (full details in §7.2). Combined and BreakRC were compared to $\textsc{Combined}^{\textsc{R}}$ and $\textsc{BreakRC}^{\textsc{R}}$ which use the rule-based decompositions. We observe that QDMR lead to substantially higher performance when compared to the rule-based decompositions.

QDMR for Semantic Parsing

As QDMR structures can be easily annotated at scale, a natural question is how far are they from fully executable queries (known to be expensive to annotate). As shown in §4.3, QDMRs can be mapped to pseudo-logical forms with high precision (93.1%) by extracting formal operators and arguments from their steps. The pseudo-logical form differs from an executable query in the lack of grounding of its arguments (entities and relations) in KB constants. This stems from the design of QDMR as a domain-agnostic meaning representation (§2). QDMR abstracts away from a concrete KB schema by assuming an underlying “idealized” KB, which contains all of its arguments.

Thus, QDMR can be viewed as an intermediate representation between a natural language question and an executable query. Such intermediate representations have already been discussed in prior work on semantic parsing. Kwiatkowski et al. (2013) and Choi et al. (2015) used underspecified logical forms as an intermediate representation. Guo et al. (2019) proposed a two-stage approach, separating between learning an intermediate text-to-SQL representation and the actual mapping to schema items. Works in the database community have particularly targeted the mapping of intermediate query representations into DB grounded queries, using schema mapping and join path inference Androutsopoulos et al. (1995); Li et al. (2014); Baik et al. (2019). We argue that QDMR can be used as an easy-to-annotate representation in such semantic parsers, bridging between natural language and full logical forms.

QDMR Parsing

We now present evaluation metrics and models for mapping questions into QDMR structures.

Given a question $x$ we wish to map it to its QDMR steps, $\textbf{s}=\langle s^{1},...,s^{n}\rangle$. One can frame this as a sequence-to-sequence problem where $x$ is mapped to a string representing its decomposition. We add a special separating token $\langle\text{SEP}\rangle$, and define the target string to be $s^{1}_{1},...,s^{1}_{m_{1}},\langle\text{SEP}\rangle,s^{2}_{1},...,s^{2}_{m_{2}},\langle\text{SEP}\rangle,...,s^{n}_{m_{n}}$, where $m_{1},...,m_{n}$ are the number of tokens in each decomposition step.

1 Evaluation Metrics

We wish to assess the quality of a predicted QDMR, $\hat{\textbf{s}}$ to a gold standard, s. Figure 7 lists various properties by which question decompositions may differ, such as granularity (e.g., steps 1-3 of decomposition 1 are merged into the first step of decomposition 2), ordering (e.g., the last two steps are swapped) and wording (e.g., using “from” instead of “on”). While such differences do not affect the overall semantics, the second decomposition can be further decomposed. To measure such variations, we introduce two types of evaluation metrics. Sequence-based metrics treat the decomposition as a sequence of tokens, applying standard text generation metrics. As such metrics ignore the QDMR graph structure, we also employ graph-based metrics that compare the predicted graph $G_{\hat{\textbf{s}}}$ to the gold QDMR graph $G_{\textbf{s}}$ (see §2).

Sequence-based scores, where higher values are better, are denoted by $\Uparrow$. Graph-based scores, where lower values are better, are denoted by $\Downarrow$.

Exact Match $\Uparrow$: Measures exact match between s and $\hat{\textbf{s}}$, either 0 or 1.

SARI $\Uparrow$ Xu et al. (2016): SARI is commonly used in tasks such as text simplification. Given s, we consider the sets of added, deleted, and kept n-grams when mapping the question $x$ to s. We compute these three sets for both s and $\hat{\textbf{s}}$ using the standard of up to 4-grams, then average (a) the F1 for added n-grams between s and $\hat{\textbf{s}}$, (b) the F1 for kept n-grams, and (c) the precision for the deleted n-grams.

Graph Edit Distance (GED) $\Downarrow$: A graph edit path is a sequence of node and edge edit operations (addition, deletion, and substitution), where each operation has a predefined cost. GED computes the minimal-cost graph edit path required for transitioning from $G_{\textbf{s}}$ to $G_{\hat{\textbf{s}}}$ (and vice versa), normalized by $\max(|G_{\textbf{s}}|,|G_{\hat{\textbf{s}}}|)$. Operation costs are $1$ for insertion and deletion of nodes and edges. The substitution cost of two nodes $u,v$ is set to be $1-\textit{Align}(u,v)$, where $\textit{Align}(u,v)$ is the ratio of aligned tokens between these steps.

GED+ $\Downarrow$: Comparing the QDMR graphs in Figure 8, we consider the splitting and merging of graph nodes. We implement GED+, a variant of GED with additional operations to merge (split) a set of nodes (node), based on the A* algorithm Hart et al. (1968).Due to its exponential worst-case complexity, we compute GED+ only for graphs with up to 5 nodes, covering 75.2% of the examples in the development set of Break.

2 QDMR Parsing Models

We present models for QDMR parsing, built over AllenNLP Gardner et al. (2017).

Copy: A model that copies the input question $x$, without introducing any modifications.

RuleBased: We defined 12 decomposition rules, to be applied over the dependency tree of the question, augmented with coreference relations. A rule is a regular expression over the question dependency tree, which invokes a decomposition operation when matched (Table 8). E.g., the rule for relative clauses (relcl) breaks the question at the relative pronoun “that”, while adding a reference to the preceding part of the sentence. A full decomposition is obtained by recursively applying the rules until no rule is matched.

Seq2Seq: A sequence-to-sequence neural model with a 5-layer LSTM encoder and attention at decoding time.

S2SDynamic: Seq2Seq with a dynamic output vocabulary restricted to the closed set of tokens $L_{x}$ available to crowd-workers (see §3).

Copynet: Seq2Seq with an added copy mechanism that allows copying tokens from the input sequence Gu et al. (2016).

3 Results

Table 9 presents model performance on Break. Neural models outperform the RuleBased baseline and perform reasonably well, with Copynet obtaining the best scores across all metrics. This can be attributed to most of the tokens in a QDMR parse being copied from the original question.

To judge the quality of predicted QDMRs we sampled 100 predictions of Copynet (Table 10) half of them being high-level QDMRs. For standard QDMR, 24% of the sampled predictions were an exact match, with an additional 30% being fully decomposed and semantically equivalent to the gold decompositions. E.g., in the first row of Table 10, the gold decomposition first discards the number of cylinders, then counts the remaining objects. Instead, Copynet opted to count both groups, then subtract the number of cylinders from the number of objects. This illustrates how different QDMRs may be equivalent.

For high-level examples (from RC datasets), as questions are often less structured, they require a deeper semantic understating from the decomposition model. Only 8% of the predictions were an exact match, with an additional 46% being semantically equivalent to the gold. The remaining 46% were of erroneous predictions (see Table 10).

Related Work

Recent work on QA through question decomposition has focused mostly on single modalities Gupta and Lewis (2018); Guo et al. (2019); Min et al. (2019b). QA using neural modular networks has been suggested for both KBs and images by Andreas et al. (2016) and Hu et al. (2017). Question decomposition over text was proposed by Talmor and Berant (2018), however over a much more limited set of questions than in Break. Iyyer et al. (2017) have also decomposed questions to create a “sequential question answering” task. Their annotators viewed a web table and performed actions over it to retrieve the cells that constituted the answer. Conversely, we provided annotators only with the question, as QDMR is agnostic to the original context.

An opposite annotation cycle to ours was presented in Cheng et al. (2018). The authors generate sequences of simple questions which crowd-workers paraphrase into a compositional question. Questions in Break are composed by humans, and are then decomposed to QDMR.

Semantic formalism annotation

Labeling corpora with a semantic formalism has often been reserved for expert annotators Dahl et al. (1994); Zelle and Mooney (1996); Abend and Rappoport (2013); Yu et al. (2018). Recent work has focused on cheaply eliciting quality annotations from non-experts through crowdsourcing He et al. (2016); Iyer et al. (2017); Michael et al. (2018). FitzGerald et al. (2018) facilitated non-expert annotation by introducing a formalism expressed in natural language for semantic-role-labeling. This mirrors QDMR, as both are expressed in natural language.

Relation to other formalisms

QDMR is related to Dependency-based Compositional Semantics Liang et al. (2013), as both focus on question representations. However, QDMR is designed to facilitate annotations, while DCS is centered on paralleling syntax. Domain-independent intermediate representations for semantic parsers were proposed by Kwiatkowski et al. (2013) and Reddy et al. (2016). As there is no consensus on the ideal meaning representation for semantic parsing, representations are often chosen based on the particular execution setup: SQL is used for relational databases Yu et al. (2018), SPARQL for graph KBs Yih et al. (2016), while other ad-hoc languages are used based on the task at hand. We frame QDMR as an easy-to-annotate formalism that can be potentially converted to other representations, depending on the task. Last, AMR Banarescu et al. (2013) is a meaning representation for sentences. Instead of representing general language, QDMR represents questions, which are important for QA systems, and for probing models for reasoning.

Conclusion

In this paper, we presented a formalism for question understanding. We have shown it is possible to train crowd-workers to produce such representations with high quality at scale, and created Break, a benchmark for question decomposition with over 83K decompositions of questions from 10 datasets and 3 modalities (DB, images, text). We presented the utility of QDMR for both open-domain question answering and semantic parsing, and constructed a QDMR parser with reasonable performance. QDMR proposes a promising direction for modeling question understanding, which we believe will be useful for multiple tasks in which reasoning is probed through questions.

Acknowledgments

This work was completed in partial fulfillment for the PhD of Tomer Wolfson. This research was partially supported by The Israel Science Foundation grants 942/16 and 978/17, The Yandex Initiative for Machine Learning and the European Research Council (ERC) under the European Union Horizons 2020 research and innovation programme (grant ERC DELPHI 802800).

References