Elamur Research⌕
☰
home / papers / 2019 / Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index

Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index

Summary

Standard open-domain QA systems such as DrQA first retrieve a handful of documents and then run a neural reader over them for each new question. This is slow, and the final accuracy is capped by the retriever. Seo et al. propose DenSPI (Dense-Sparse Phrase Index), which removes this two-stage design. Every candidate answer span in English Wikipedia is encoded once, offline, independently of any question. At query time, the question is projected into the same vector space, and the answer is found by (approximate) maximum inner product search.

Each phrase vector has two parts:

  • A dense part, built from BERT-based start and end token vectors plus a coherency scalar, which captures syntactic and semantic context.
  • A sparse part, which captures exact lexical evidence such as term frequencies.

Storing start and end vectors instead of every full span keeps the index compact. On SQuAD-Open, DenSPI matches or beats earlier systems at a fraction of the compute cost. This shows that web-scale QA can run in real time on modest academic hardware.

Key points

  • The index covers up to 60 billion Wikipedia phrases in under 2TB. The whole system can be trained and deployed in about a week on one server with 4 GPUs, 128GB RAM and a 2TB PCIe SSD.
  • On SQuAD-Open, DenSPI achieves 3.8% higher EM than DrQA.
  • Computational cost drops by roughly 6000x in a controlled setting, and end-to-end CPU inference (including disk access) is at least 68x faster.
  • Ablation: removing the sparse vector costs 21.8 F1 points. Lexical signals are crucial for separating entities that are semantically similar but named differently.
  • Restricting the search to a few documents first (a pipeline variant) is faster but less accurate. Qualitatively, DenSPI often finds the same answer in several different documents.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

75 papers of our library cite it (of the 140884 whose bibliographies we read); 9 of them have a page here, 66 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p19-1436

@inproceedings{seo2019real,
  title = {{Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index}},
  author = {Seo, Minjoon and Lee, Jinhyuk and Kwiatkowski, Tom and Parikh, Ankur and Farhadi, Ali and Hajishirzi, Hannaneh},
  booktitle = {Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1436},
  url = {https://doi.org/10.18653/v1/p19-1436}
}

References

34 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alexandr Andoni and Ilya Razenshteyn. 2015. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing. find
  2. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. Semantic parsing on freebase from question-answer pairs. In EMNLP. find
  3. David M Blei, Andrew Y Ng, and Michael I Jordan. 2003. Latent dirichlet allocation. JMLR. find our card
  4. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD. find
  5. Omer Levy, Minjoon Seo, Eunsol Choi, and Luke Zettlemoyer. 2017. Zero-shot relation extraction via reading comprehension. In CoNLL. find
  6. Mike Lewis and Angela Fan. 2019. Generative question answering: Learning to answer the whole question. In ICLR. find
  7. Yankai Lin, Haozhe Ji, Zhiyuan Liu, and Maosong Sun. 2018. Denoising distantly supervised open-domain question answering. In ACL. find
  8. Yury A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI. find our card
  9. Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017. Reading wikipedia to answer open-domain questions. In ACL. find our card
  10. Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. 2016. Key-value memory networks for directly reading documents. arXiv preprint arXiv:1606.03126. find
  11. Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. 2016. Wide & deep learning for recommender systems. In Proceedings of the 1st Workshop on Deep Learning for Recommender Systems. find
  12. Sewon Min, Victor Zhong, Richard Socher, and Caiming Xiong. 2018. Efficient and robust question answering from minimal context over documents. In ACL. find
  13. Jennifer Chu-Carroll, James Fan, BK Boguraev, David Carmel, Dafna Sheinwald, and Chris Welty. 2012. Finding needles in the haystack: Search and candidate generation. IBM Journal of Research and Development. find
  14. Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, and Andrew McCallum. 2019. Multi-step retriever-reader interaction for scalable open-domain question answering. In ICLR. find
  15. Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. 1990. Indexing by latent semantic analysis. Journal of the American society for information science. find
  16. Kyosuke Nishida, Itsumi Saito, Atsushi Otsuka, Hisako Asano, and Junji Tomita. 2018. Retrieve-and-read: Multi-task learning of information retrieval and reading comprehension. In CIKM. find
  17. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In NAACL-HLT. find
  18. John Prager et al. 2007. Open-domain question– answering. Foundations and Trends R in Information Retrieval. find
  19. Jonathan Raiman and John Miller. 2017. Globally normalized reader. In EMNLP. find
  20. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT. find
  21. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016. Squad: 100,000+ questions for machine comprehension of text. In EMNLP. find our card
  22. Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In VLDB. find
  23. Minjoon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. 2017. Bidirectional attention flow for machine comprehension. In ICLR. find our card
  24. Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product quantization for nearest neighbor search. TPAMI. find
  25. Minjoon Seo, Tom Kwiatkowski, Ankur Parikh, Ali Farhadi, and Hannaneh Hajishirzi. 2018. Phrase-indexed question answering: A new challenge for scalable document comprehension. In EMNLP. find
  26. Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017. Billion-scale similarity search with gpus. arXiv preprint arXiv:1702.08734. find our card
  27. Jinhyuk Lee, Seongjun Yun, Hyunjae Kim, Miyoung Ko, and Jaewoo Kang. 2018. Ranking paragraphs for improving answer recall in open-domain question answering. In EMNLP. find
  28. Yelong Shen, Po-Sen Huang, Jianfeng Gao, and Weizhu Chen. 2017. Reasonet: Learning to stop reading in machine comprehension. In KDD. find
  29. Anshumali Shrivastava and Ping Li. 2014. Asymmetric lsh (alsh) for sublinear time maximum inner product search (mips). In NIPS. find
  30. Ellen M Voorhees and Dawn M Tice. 2000. Building a question answering test collection. In SIGIR. find
  31. Shuohang Wang, Mo Yu, Xiaoxiao Guo, Zhiguo Wang, Tim Klinger, Wei Zhang, Shiyu Chang, Gerry Tesauro, Bowen Zhou, and Jing Jiang. 2018a. R 3: Reinforced ranker-reader for open-domain question answering. In AAAI. find
  32. Shuohang Wang, Mo Yu, Jing Jiang, Wei Zhang, Xiaoxiao Guo, Shiyu Chang, Zhiguo Wang, Tim Klinger, Gerald Tesauro, and Murray Campbell. 2018b. Evidence aggregation for answer re-ranking in open-domain question answering. In ICLR. find
  33. Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. 2019. End-to-end open-domain question answering with bertserini. arXiv preprint arXiv:1902.01718. find our card
  34. Yi Yang, Wen-tau Yih, and Christopher Meek. 2015. Wikiqa: A challenge dataset for open-domain question answering. In EMNLP. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/seo-2019-real-time-open-domain-question/