2019

On the Possibilities and Limitations of Multi-hop Reasoning Under Linguistic Imperfections

Khashabi, Daniel, Azer, Erfan Sadeqi, Khot, Tushar et al.

Understand

Systems for language understanding have become remarkably strong at overcoming linguistic imperfections in tasks involving phrase matching or simple reasoning.

Yet, their accuracy drops dramatically as the number of reasoning steps increases.
We present the first formal framework to study such empirical observations.
It allows one to quantify the amount and effect of ambiguity, redundancy, incompleteness, and inaccuracy that the use of language introduces when representing a hidden conceptual space.

Built on

Random graphs
Edgar N Gilbert. 1959 · 1959
Earlier work this paper cites.
On the evolution of random graphs
Paul Erdos and Alfréd Rényi. 1960 · 1960
Earlier work this paper cites.
Programs with common sense
John McCarthy. 1963 · 1963
Earlier work this paper cites.
Semantic memory
M Ross Quillan. 1966 · 1966
Earlier work this paper cites.
Six degrees of separation
Stanley Milgram. 1967 · 1967
Earlier work this paper cites.
Mental models in cognitive science
Philip Nicholas Johnson-Laird. 1980 · 1980
Earlier work this paper cites.
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
J Pearl. 1988 · 1988
Earlier work this paper cites.
The symbol grounding problem
Stevan Harnad. 1990 · 1990
Earlier work this paper cites.
Wordnet: a lexical database for english
George Miller. 1995 · 1995
Earlier work this paper cites.
The average distances in random graphs with given expected degrees
Fan Chung and Linyuan Lu. 2002 · 2002
Earlier work this paper cites.
Mapping dependencies trees: An application to question answering
Vasin Punyakanok, Dan Roth, and Scott Yih. 2004 · 2004
Earlier work this paper cites.
Solving the symbol grounding problem: a critical review of fifteen years of research
Mariarosaria Taddeo and Luciano Floridi. 2005 · 2005
Earlier work this paper cites.

Similar

Wikify!: linking documents to encyclopedic knowledge
Rada Mihalcea and Andras Csomai. 2007 · 2007
Cited alongside, same era.
Freebase: A collaboratively created graph database for structuring human knowledge
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008 · 2008
Cited alongside, same era.
Introduction to algorithms
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009 · 2009
Cited alongside, same era.
Local and global algorithms for disambiguation to Wikipedia
Lev Ratinov, Dan Roth, Doug Downey, and Mike Anderson. 2011 · 2011
Cited alongside, same era.
Combinatory categorial grammar
Mark Steedman and Jason Baldridge. 2011 · 2011
Cited alongside, same era.
Efficient estimation of word representations in vector space
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013 · 2013
Cited alongside, same era.
Reasoning with neural tensor networks for knowledge base completion
Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. 2013 · 2013
Cited alongside, same era.
Naturalli: Natural logic inference for common sense reasoning
Gabor Angeli and Christopher D. Manning. 2014 · 2014
Cited alongside, same era.
Higher-order lexical semantic models for non-factoid answer reranking
Daniel Fried, Peter Jansen, Gustave Hahn-Powell, Mihai Surdeanu, and Peter Clark. 2015 · 2015
Cited alongside, same era.
Observed versus latent features for knowledge base and text inference
Kristina Toutanova and Danqi Chen. 2015 · 2015
Cited alongside, same era.
What’s in an explanation? characterizing knowledge and inference requirements for elementary science exams
Peter Jansen, Niranjan Balasubramanian, Mihai Surdeanu, and Peter Clark. 2016 · 2016
Cited alongside, same era.
A study of automatically acquiring explanatory inference patterns from corpora of explanations: Lessons from elementary science exams
Peter A Jansen. 2016 · 2016
Cited alongside, same era.

Then

Question answering via integer programming over semi-structured knowledge
Daniel Khashabi, Tushar Khot, Ashish Sabharwal, Peter Clark, Oren Etzioni, and Dan Roth. 2016 · 2016
Later among the works it cites.
Framing qa as building and ranking intersentence answer justifications
Peter Jansen, Rebecca Sharp, Mihai Surdeanu, and Peter Clark. 2017 · 2017
Later among the works it cites.
Answering complex questions using open information extraction
Tushar Khot, Ashish Sabharwal, and Peter Clark. 2017 · 2017
Later among the works it cites.
Universal semantic parsing
Siva Reddy, Oscar Täckström, Slav Petrov, Mark Steedman, and Mirella Lapata. 2017 · 2017
Later among the works it cites.
WorldTree: A corpus of explanation graphs for elementary science questions supporting multi-hop inference
Peter A. Jansen, Elizabeth Wainwright, Steven Marmorstein, and Clayton T. Morrison. 2018 · 2018
Later among the works it cites.
Multi-hop knowledge graph reasoning with reward shaping
Xi Victoria Lin, Richard Socher, and Caiming Xiong. 2018 · 2018
Later among the works it cites.
Can a suit of armor conduct electricity? a new dataset for open book question answering
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. 2018 · 2018
Later among the works it cites.
Deep contextualized word representations
Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke S. Zettlemoyer. 2018 · 2018
Later among the works it cites.
HotpotQA: A dataset for diverse, explainable multi-hop question answering
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018 · 2018
Later among the works it cites.
BERT: Pre-training of deep bidirectional transformers for language understanding
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019 · 2019
Closest in time.
Spectral distributions of adjacency and laplacian matrices of random graphs
Xue Ding, Tiefeng Jiang, et al. 2010 · 2086
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…