Source-linked AI summary
The Web as a Knowledge-base for Answering Complex Questions
Alon Talmor, Jonathan Berant
TL;DR
Complex question answering requires reasoning across evidence that reading-comprehension systems and knowledge-base semantic parsers do not fully address. The paper decomposes complex questions into simple web-search questions, composes their answers, and evaluates this framework with a new dataset and model. Question decomposition improves precision@1 from 20.8 to 27.5 on ComplexWebQuestions.
Problem
Complex QA requires reasoning across multiple sources, while reading comprehension struggles with reasoning and semantic parsing depends on manually curated knowledge-bases.
Method
The paper decomposes complex questions into simple questions answered through web search and reading comprehension, then composes the retrieved answers using a learned computation procedure.
Results
Question decomposition improved precision@1 from 20.8 to 27.5 on ComplexWebQuestions.
Takeaways & Limitations
The framework provides broad, compositional QA without assuming the answer information is stored in a knowledge-base or already retrieved documents.
Takeaways & Limitations
Automatically generated queries make the dataset’s question distribution artificial from a semantic perspective.
Abstract
from arXiv · showhide
Answering complex questions is a time-consuming activity for humans that requires reasoning and integration of information. Recent work on reading comprehension made headway in answering simple questions, but tackling complex questions is still an ongoing research challenge. Conversely, semantic parsers have been successful at handling compositionality, but only when the information resides in a target knowledge-base. In this paper, we present a novel framework for answering broad and complex questions, assuming answering simple questions is possible using a search engine and a reading comprehension model. We propose to decompose complex questions into a sequence of simple questions, and compute the final answer from the sequence of answers. To illustrate the viability of our approach, we create a new dataset of complex questions, ComplexWebQuestions, and present a model that decomposes questions and interacts with the web to compute an answer. We empirically demonstrate that question decomposition improves performance from 20.8 precision@1 to 27.5 precision@1 on this new dataset.
1 Introduction
Complex QA requires reasoning across multiple sources, beyond the local-context focus of reading comprehension and the knowledge-base dependence of semantic parsing. The paper proposes decomposing complex questions into simple web-search questions and reports improved performance on a new dataset.
- Motivation: Complex questions require reasoning over multiple pieces of evidence and searching across multiple sources.This makes answering broad-domain questions onerous for humans.
- Motivation: Reading-comprehension models handle local contexts well but struggle with reasoning, while relevant documents may be difficult to retrieve for complex questions.Reading comprehension assumes that documents containing the answer are already available.
- Motivation: Semantic parsers support compositional reasoning but depend on manually curated knowledge-bases, limiting their coverage and applicability.The paper instead targets broad questions without assuming information resides in a knowledge-base.
- Approach: The proposed framework decomposes complex questions into simple questions, submits them to a search engine and QA model, and computes a final answer from their answers.The framework can use symbolic operations such as union and intersection after gathering answers.
- Dataset: 34,689 question-answer pairs were created for ComplexWebQuestions using automatically generated complex queries and human-generated natural-language questions.The dataset includes complex questions built from phenomena such as composition, conjunctions, superlatives, and comparatives.
- Results: Question decomposition improved precision@1 from 20.8 to 27.5 on ComplexWebQuestions.Humans reached 63.0 precision@1 under a limited time budget.
- Contributions: The paper contributes a decomposition framework, a sequence-to-sequence model, and the ComplexWebQuestions dataset.The released dataset contains questions, answers, web snippets, and SPARQL queries.
2 Problem Formulation
The model learns to transform a complex question into a computation tree whose functions decompose the question and compose answers from a black-box simple-question QA system. Tree denotations are computed recursively over string leaves and function-labeled inner nodes.
- Model objective: The model maps a question and black-box SIMPQA model to a computation tree that decomposes the question and computes its answer.It is trained from question-computation-tree pairs.
- Computation trees: A computation tree has string-labeled leaves and function-labeled inner nodes whose arguments are child subtrees.The denotation of each node is computed recursively by applying its function to the denotations of its children.
- Computation trees: The framework permits paraphrasing leaf strings when that improves interaction with the simple-question QA model.For example, a leaf may use “cities” instead of the question’s “city”.
- Simple-question QA: SIMPQA submits a simple question to a search engine and applies a reading-comprehension model to retrieved web snippets.In this work, the reading-comprehension model is pretrained separately and treated as a black box.
- Formal language: The expressivity of the QA model is determined by the functions available in the formal language.The language includes SIMPQA and compositional operations such as COMP and CONJ.
3 Formal Language
The formal language represents question answering with functions over strings and sets, supporting composition, conjunction, and arithmetic while treating some web-based logical constructions differently. Superlatives, comparatives, and negation remain constrained by search-engine assumptions and open-world information.
- The language includes functions that take strings or sets and return strings, sets of strings, or sets of numbers.
- COMP replaces a variable in a string with each answer and returns the union of the resulting SIMPQA answers.This implements composition from previously computed values.
- CONJ takes two sets and returns their intersection, with a shorthand that applies SIMPQA before intersecting string inputs.
- ADD adds two singleton sets of numbers, although mathematical operations were not required in the dataset.
- Superlative and comparative questions are handled directly by SIMPQA, assuming the construction is mentioned verbatim in a web document.The framework does not compose these operations over extracted entity-value pairs.
- Negation is difficult with a search engine because the open-world setup lacks a closed set over which to perform subtraction; future table and KB interfaces target this gap.
4 Dataset
COMPLEXWEBQUESTIONS is designed to evaluate question decomposition using broad, complex questions generated from Freebase queries and paraphrased into natural language. The dataset includes diverse compositional phenomena, substantial paraphrasing, and evidence that decomposition requires copying, adding, and deleting words.
- 4.1 Dataset collection: 34,689 examples were produced by extending WEBQUESTIONSSP queries with composition, conjunction, superlative, and comparative phenomena, then paraphrasing them into natural language.The examples include answers, web snippets, and SPARQL queries, although the models ignore the queries.
- 4.1 Dataset collection: The automatically generated question distribution is artificial from a semantic perspective, limiting how naturally the dataset represents complex questions.The authors identify this artificial distribution as a drawback of their data-generation method.
- 4.2 Dataset analysis: MG questions averaged 16 words versus 13.18 for NL questions, while NL questions had 14,282 unique tokens versus 9,489 in MG questions.The measurements indicate shorter natural-language questions with richer vocabulary than the machine-generated versions.
- 4.2 Dataset analysis: 44.7% of conjunction questions and 13.2% of composition questions exhibited word reordering between machine-generated and natural-language questions.The authors estimate reordering with a token-similarity matrix using lemma matches or thresholded GloVe cosine similarity.
- 4.2 Dataset analysis: 54% of analyzed examples used synonyms, while 27% omitted words and 22% substantially reordered words during paraphrasing.The analysis manually examined 100 development examples and also identified word-ordering, modifier, and other paraphrase phenomena.
- 4.2 Dataset analysis: 53% of analyzed cases required copying a natural-language word into multiple decomposed questions, 39% required additions, and 28% required deletions.These findings show that decomposition involves more than simply splitting the original question.
5 Model and Learning
The model represents limited computation trees as token sequences and learns to decompose questions using automatically generated noisy supervision. It combines pointer-network decoding with a score-based choice between decomposition and direct answering.
- Representation: The model restricts computation trees to at most one compositional operation, represented as a sequence of tokens.The supported representations include direct answering, composition, and conjunction, with limited copying and no rephrasing.
- Supervision: Noisy programs generated from SPARQL queries and machine-generated questions provide supervision without requiring the model to use SPARQL at inference.A rule-based alignment procedure approximates split points in natural-language questions.
- Decoding: The model translates questions into representations z = z1 z2 z3, where z1 is COMP or CONJ and z2, z3 are integer indices.These indices point to locations in the input question used to specify decomposition operations.
- Decoding: An augmented pointer network appends COMP and CONJ tokens to each question so one network can decode operation labels and input positions.The pointer-network design is motivated by representations that point to indices in the input.
- Inference: The system returns the highest-scoring answer from decomposed and direct-answering strategies because direct SIMPQA can sometimes perform better.The decision uses answer scores from both strategies, with future work aiming to handle logical functions uniformly.
6 Experiments
Experiments test whether decomposition improves complex-question answering across datasets and reading-comprehension models. Decomposition improves performance over direct answering, while remaining errors include retrieval, matching, ambiguity, and annotation problems.
- Evaluation: Evaluation measures precision@1 as whether the highest-scoring answer string-matches a correct answer.Answers are sets, but 70% of questions have a single answer and the average answer-set size is 2.3.
- COMPLEXWEBQUESTIONS: 27.5 p@1 with question decomposition exceeds 20.8 p@1 for SIMPQA without decomposition on COMPLEXWEBQUESTIONS.SPLITQAORACLE reaches 33.7 p@1 when decomposition decisions are made with perfect hindsight.
- COMPLEXWEBQUESTIONS: SPLITRCQA outperforms RCQA by 3.4 points, showing decomposition benefits a second reading-comprehension model.The result supports the value of decomposition for retrieving documents from which an RC model extracts answers.
- Strategy selection: In 86% of cases where either decomposition or direct answering works, SPLITQA chooses the correct strategy.The model decomposes 61% of questions, and in 71% of answerable cases only one strategy produces a correct answer.
- Decomposition prediction: The pointer network exactly matches the heuristic output sequence 60.9% of the time and reaches 77.1% accuracy allowing one-word errors.Token-level accuracy is 83.0%, increasing to 89.7% with one-word errors allowed.
7 Related work
The work connects semantic parsing, reading comprehension, retrieval, and prior decomposition approaches while differing in its use of the entire web without assuming documents or a curated knowledge base.
- Retrieval and semantic parsing: Unlike semantic-parsing approaches operating against Freebase or other structured resources, this work proposes decomposition while interacting with a search engine over the entire web.The paper emphasizes finding information without assuming that documents are given.
- Black-box QA: The paper notes that black-box QA systems complicate differentiability and reproducibility because such systems can change over time.Despite this challenge, the paper presents black-box QA setups as a holistic view of question answering.
- Prior decomposition: Earlier decomposition work used crowdsourced gold decompositions and web tables, whereas this paper avoids that supervision and uses a search engine.The comparison distinguishes the paper’s training assumptions and information source from prior work.
8 Conclusion
The paper introduces a web-based framework, model, and dataset for complex question answering. It argues that the released resource can support research on compositionality and holistic QA, while identifying broader information sources as future work.
- Conclusion: The proposed framework answers complex questions through question decomposition and interaction with the web.The framework is designed for broad and compositional question answering.
- Conclusion: The released COMPLEXWEBQUESTIONS dataset includes questions, SPARQL programs, answers, and web snippets harvested by the model.The authors expect it to serve QA and semantic-parsing communities.
- Future work: Future work will train directly from weak supervision and extract information from web tables and knowledge bases in addition to the web.The current framework therefore does not yet cover those structured information sources in its extraction process.
Dataset
The dataset is built by generating complex SPARQL queries from simple ones, converting them into natural-language questions, and collecting AMT paraphrases. It contains examples spanning multiple compositionality types and exhibits substantial linguistic variation.
- Query generation: Complex queries are generated from WEBQUESTIONSSP queries using conjunctions, superlatives, comparatives, and compositions.The generation process constructs queries with denotations constrained to nonempty strict subsets for several types and handles entity replacement for compositions.
- Natural-language generation: 503 manually annotated templates map 377 unique KB predicates to natural-language expressions for different compositionality types.The templates make machine-generated questions understandable to AMT workers before paraphrasing.
- Natural-language generation: AMT workers paraphrase template-based questions, with templates connecting generated terms and seed questions according to the compositionality type.Examples include coordinating phrases such as “and is” for conjunction questions.
- Dataset analysis: 22% of COMPLEXWEBQUESTIONS begin with a word other than a wh-word, unlike almost all questions in WEBQUESTIONSSP.This distribution is presented as evidence of substantial paraphrasing from the original questions.
Generating noisy supervision
The authors create noisy supervision for question decomposition by estimating how AMT workers reorder words and selecting split points that best match known machine-generated boundaries.
- Re-ordering detection: A heuristic estimates the amount of global word re-ordering performed by AMT workers and uses it to create noisy supervision.The heuristic is designed to account for differences between machine-generated and natural-language questions.
- Re-ordering detection: The final split point and whether re-ordering occurred are determined by comparing two values and choosing the higher one.This comparison provides the decision rule for the supervision heuristic.
- Split-point estimation: For compositional questions, the system returns two split points marking the beginning and end of the phrase sent to the QA model.The selected points maximize an objective based on known split points in the machine-generated question.
- Split-point estimation: A similarity heat map compares machine-generated and natural-language questions, showing known and approximated split points alongside candidate split-point scores.The figure visualizes how candidate boundaries are evaluated against the known boundary.