Question Answering via Integer Programming over Semi-Structured Knowledge

By Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, Dan Roth. 2016

100 citations recorded by the source corpus.

Answering science questions posed in natural language is an important AI challenge. Answering such questions often requires non-trivial inference and knowledge that goes beyond factoid retrieval. Yet, most systems for this task are based on relatively shallow Information Retrieval (IR) and statistical correlation techniques operating on large unstructured corpora. We propose a structured inference system for this task, formulated as an Integer Linear Program (ILP), that answers natural language questions using a semi-structured knowledge base derived from text, including questions requiring multi-step inference and a combination of multiple facts. On a dataset of real, unseen science questions, our system significantly outperforms (+14%) the best previous attempt at structured reasoning for this task, which used Markov Logic Networks (MLNs). It also improves upon a previous ILP formulation by 17.7%. When combined with unstructured inference methods, the ILP system significantly boosts overall performance (+10%). Finally, we show our approach is substantially more robust to a simple answer perturbation compared to statistical correlation methods.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering (2018, background): “TableILP (Khashabi et al., 2016) is an Integer Linear Programming (ILP) based reasoning sys-tem designed for science questions.”
Looking Beyond the Surface: A Challenge Set for Reading Comprehension over Multiple Sentences (2018, background): “For example, Khashabi et al. (2016) showed that adversarial per-”
Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge (2018, background): “TableILP (Khashabi et al., 2016), which performs matching and reasoning using a semi-structured knowledge base of science knowledge, expressed in tables.”
RACE: Large-scale ReAding Comprehension Dataset From Examinations (2017, methodology): “…created by (Richardson et al., 2013) (containing 500 passages and 2000 questions) and several others (Peñas et al., 2014; Rodrigo et al., 2015; Khashabi et al., 2016; Shibuki et al., 2014), the usefulness of those datasets is significantly restricted due to their small sizes, especially not…”
QASC: A Dataset for Question Answering via Sentence Composition (2019, methodology): “These relations were deﬁned based on previous analyses on science datasets (Clark et al. 2014; Jansen et al. 2016; Khashabi et al. 2016).”
SciTaiL: A Textual Entailment Dataset from Science Question Answering (2018, background): “Consequently, most systems attempt to stitch together multiple rules (Khot et al. 2015), table rows (Khashabi et al. 2016), or Open IE tuples (Khot, Sabharwal, and Clark 2017) to produce an answer.”
Crowdsourcing Multiple Choice Science Questions (2017, background): “Probabilistic reasoning approaches include Markov logic networks (Khot et al., 2015) and an integer linear program-based model that assembles proof chains over structured knowledge (Khashabi et al., 2016).”
Answering Complex Questions Using Open Information Extraction (2017, methodology): “…KB, state-of-the-art systems for this task either rely on shallow reasoning with large text corpora (Clark et al., 2016; Cheng et al., 2016) or deeper, structured reasoning with a small amount of automatically acquired (Khot et al., 2015) or manually curated (Khashabi et al., 2016) knowledge.”
WorldTree: A Corpus of Explanation Graphs for Elementary Science Questions supporting Multi-hop Inference (2018, methodology): “Following Khashabi et al. (2016), we make use of a speciﬁc form of table representation that includes “ﬁller” columns that allow each row to be directly read off as a stand-alone natural language sentence, and serve as input to any model.”
Learning What is Essential in Questions (2017, methodology): “A state-of-the-art optimization based QA system called TableILP (Khashabi et al., 2016), which performs reasoning by aligning the question to semi-structured knowledge, aligns only the word ‘animals’ when answering this question.”
Question Answering as Global Reasoning Over Semantic Abstractions (2018, methodology): “This formalism may be viewed as a generalization of systems that reason over tables of knowledge (Cohen 2000; Khashabi et al. 2016): instead of operating over table rows (which are akin to labeled sequence graphs or predicate-argument graphs), we operate over a much richer class of semantic graphs.”
Mapping to Declarative Knowledge for Word Problem Solving (2017, background): “Finally, we note that there has been some work in the context of Question Answering on perturbing questions or answers as a way to test or assure the robustness of the approach or lack of (Khashabi et al., 2016; Jia and Liang, 2017).”
From 'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project (2019, methodology): “Early work was dominated by information retrieval, statistical, and automated rule extraction and reasoning methods (Clark et al., 2014, 2016; Khashabi et al., 2016; Khot et al., 2017; Khashabi et al., 2018).”
KG^2: Learning to Reason Science Exam Questions with Contextual Knowledge Graph Embeddings (2018, methodology): “TableILP: This method [Khashabi et al., 2016] performs table-based reasoning, which is formulated as an Integer Linear Program (ILP).”
What’s in an Explanation? Characterizing Knowledge and Inference Requirements for Elementary Science Exams (2016, background): “passing performance) on one test set (Khashabi et al., 2016).”
ElimiNet: A Model for Eliminating Options for Reading Comprehension with Multiple Choice Questions (2018, unknown): “Some other datasets such as MCTest [Richard-son et al. , 2013], AI2 [Khashabi et al. , 2016] and RACE contain RC with multiple choice questions (RC-MCQ) where the task is to select the right answer.”
Explainable Natural Language Reasoning via Conceptual Unification (2020, methodology): “Recent approaches adopt global and local semantic constraints to guide the generation of plausible multi-hop explanations (Khashabi et al., 2018; Jansen et al., 2017; Khashabi et al., 2016).”
Automated Historical Fact-Checking by Passage Retrieval, Word Statistics, and Virtual Question-Answering (2017, background): “In a series of recent papers, elementary science questions are used as a benchmark of AI systems (Khot et al., 2015; Jansen et al., 2016; Clark et al., 2016; Khashabi et al., 2016).”
Quick and (not so) Dirty: Unsupervised Selection of Justification Sentences for Multi-hop Question Answering (2019, methodology): “The third category of methods utilize IR techniques to retrieve justifications from both unstructured (Yadav et al., 2019) and structured (Khashabi et al., 2016) KBs.”