2016

Question Answering via Integer Programming over Semi-Structured Knowledge

Khashabi, Daniel, Khot, Tushar, Sabharwal, Ashish et al.

Understand

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.

Built on

Representations of knowledge in a program for solving physics problems
G. Novak · 1977
Earlier work this paper cites.
Word association norms, mutual information and lexicography
K. W. Church and P. Hanks · 1989
Earlier work this paper cites.
Wordnet: a lexical database for english
G. Miller · 1995
Earlier work this paper cites.
Data integration using similarity joins and a word-based information representation language
W. W. Cohen · 2000
Earlier work this paper cites.
Scaling question answering to the web
C. C. T. Kwok, O. Etzioni, and D. S. Weld · 2001
Earlier work this paper cites.
An analysis of the AskMSR question-answering system
E. Brill, S. Dumais, and M. Banko · 2002
Earlier work this paper cites.
A linear programming formulation for global inference in natural language tasks
D. Roth and W. Yih · 2004
Earlier work this paper cites.
Markov logic networks
M. Richardson and P. Domingos · 2006
Earlier work this paper cites.
Open information extraction from the web
M. Banko, M. J. Cafarella, S. Soderland, M. Broadhead, and O. Etzioni · 2007
Earlier work this paper cites.
A probabilistic graphical model for joint answer ranking in question answering
J. Ko, E. Nyberg, and L. Si · 2007
Earlier work this paper cites.
The sixth pascal recognizing textual entailment challenge
L. Bentivogli, P. Clark, I. Dagan, and D. Giampiccolo · 2008
Earlier work this paper cites.
Freebase: a collaboratively created graph database for structuring human knowledge
K. D. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor · 2008
Earlier work this paper cites.

Similar

SCIP: solving constraint integer programs
T. Achterberg · 2009
Cited alongside, same era.
Natural Language Inference
B. MacCartney · 2009
Cited alongside, same era.
Global learning of focused entailment graphs
J. Berant, I. Dagan, and J. Goldberger · 2010
Cited alongside, same era.
Toward an architecture for never-ending language learning
A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. H. Jr., and T. M. Mitchell · 2010
Cited alongside, same era.
Discriminative learning over constrained latent representations
M.-W. Chang, D. Goldwasser, D. Roth, and V. Srikumar · 2010
Cited alongside, same era.
Recognizing textual entailment: Rational, evaluation and approaches–erratum
I. Dagan, B. Dolan, B. Magnini, and D. Roth · 2010
Cited alongside, same era.
Building Watson: An overview of the DeepQA project
D. Ferrucci, E. Brown, J. Chu-Carroll, J. Fan, D. Gondek, A. A. Kalyanpur, A. Lally, J. W. Murdock, E. Nyberg, J. Prager, et al · 2010
Cited alongside, same era.
Project Halo update - progress toward digital Aristotle
D. Gunning, V. Chaudhri, P. Clark, K. Barker, J. Chaw, and M. Greaves · 2010
Cited alongside, same era.
Learning from natural instructions
D. Goldwasser and D. Roth · 2011
Cited alongside, same era.
A joint model for extended semantic role labeling
V. Srikumar and D. Roth · 2011
Cited alongside, same era.
Statistical methods for psychology
D. Howell · 2012
Cited alongside, same era.
Recognizing textual entailment: Models and applications
I. Dagan, D. Roth, M. Sammons, and F. M. Zanzotto · 2013
Cited alongside, same era.

Then

Distributional semantics beyond words: Supervised learning of analogy and paraphrase
P. D. Turney · 2013
Later among the works it cites.
NaturalLI: Natural logic inference for common sense reasoning
G. Angeli and C. D. Manning · 2014
Later among the works it cites.
Automatic construction of inference-supporting knowledge bases
P. Clark, N. Balasubramanian, S. Bhakthavatsalam, K. Humphreys, J. Kinkead, A. Sabharwal, and O. Tafjord · 2014
Later among the works it cites.
Open question answering over curated and extracted knowledge bases
A. Fader, L. Zettlemoyer, and O. Etzioni · 2014
Later among the works it cites.
Information extraction over structured data: Question answering with Freebase
X. Yao and B. Van Durme · 2014
Later among the works it cites.
Semantic parsing for single-relation question answering
W. Yih, X. He, and C. Meek · 2014
Later among the works it cites.
Natural language question answering over RDF: a graph data driven approach
L. Zou, R. Huang, H. Wang, J. X. Yu, W. He, and D. Zhao · 2014
Later among the works it cites.
Elementary school science and math tests as a driver for AI: take the Aristo challenge!
P. Clark · 2015
Later among the works it cites.
Exploring Markov logic networks for question answering
T. Khot, N. Balasubramanian, E. Gribkoff, A. Sabharwal, P. Clark, and O. Etzioni · 2015
Later among the works it cites.
Combining retrieval, statistics, and inference to answer elementary science questions
P. Clark, O. Etzioni, T. Khot, A. Sabharwal, O. Tafjord, P. Turney, and D. Khashabi · 2016
Closest in time.
IKE - an interactive tool for knowledge extraction
B. Dalvi, S. Bhakthavatsalam, and P. Clark · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…