Elamur Research
☰
home / papers / 2020 / Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval

Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/2007.00808

Summary

Dense retrieval (DR) represents queries and documents as vectors and matches them with similarity search. When trained end-to-end, though, it often scores lower than sparse lexical baselines such as BM25. The authors analyse SGD convergence through variance reduction and trace the weakness to how training negatives are chosen. Negatives drawn from the local mini-batch are almost always trivially irrelevant. Their losses, and therefore their gradients, shrink toward zero, so gradient variance rises and training converges slowly. The proposed fix is ANCE. It takes hard negatives from the entire corpus by searching an ANN index built with the model that is currently being trained. A separate Inferencer process re-encodes the corpus from recent checkpoints in parallel and swaps in a fresh index, so the negatives keep up with training. The method is tested on web search (TREC 2019 DL Track), OpenQA and a commercial search engine. ANCE uses plain dot-product retrieval and gets close to the accuracy of a BERT-based cascade ranking pipeline while being about 100x more efficient. This makes dense first-stage retrieval a realistic alternative to sparse methods.

Key points

  • Theory: negatives with near-zero loss give near-zero gradients. Both the batch size and the set of informative negatives are tiny compared with the corpus, so a random mini-batch almost never contains useful negatives.
  • Training runs asynchronously in two parts: a Trainer learns from ANN-retrieved negatives, while an Inferencer re-encodes the corpus from checkpoints and refreshes the index. The authors confirm empirically that ANCE negatives produce much larger gradient norms than in-batch ones.
  • In a case study on 43 TREC 2019 DL document-ranking queries, ANCE beats BM25 on 29, loses on 13 and ties on 1.
  • Typical ANCE errors are documents that are related but not exactly relevant, or gaps in domain knowledge, for example reading "active margin" as a finance term instead of a geography term.
  • Code and trained models are released at aka.ms/ance.

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: Other

Cited by

477 papers of our library cite it (of the 140673 whose bibliographies we read); 26 of them have a page here, 451 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2007.00808 · arXiv 2007.00808

@misc{xiong2020approximate,
  title = {{Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval}},
  author = {Xiong, Lee and Xiong, Chenyan and Li, Ye and Tang, Kwok-Fung and Liu, Jialin and Bennett, Paul and Ahmed, Junaid and Overwijk, Arnold},
  year = {2020},
  doi = {10.48550/arxiv.2007.00808},
  eprint = {2007.00808},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2007.00808}
}

References

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

  1. Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint arXiv:1511.06481, 2015. — [arXiv:1511.06481](https://arxiv.org/abs/1511.06481) find
  2. Payal Bajaj, Daniel Campos, Nick Craswell, Li Deng, Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, et al. Ms marco: A human generated machine reading comprehension dataset. arXiv preprint arXiv:1611.09268, 2016. find our card
  3. Wei-Cheng Chang, Felix X Yu, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. Pre-training tasks for embedding-based large-scale retrieval. arXiv preprint arXiv:2002.03932, 2020. — [arXiv:2002.03932](https://arxiv.org/abs/2002.03932) find
  4. Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading wikipedia to answer open-oomain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pp. 1870–1879, 2017. find
  5. Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05709, 2020a. find our card
  6. Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297, 2020b. — [arXiv:2003.04297](https://arxiv.org/abs/2003.04297) find
  7. Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M. Voorhees. Overview of the trec 2019 deep learning track. In Text REtrieval Conference (TREC). find our card
  8. W Bruce Croft, Donald Metzler, and Trevor Strohman. Search engines: information retrieval in practice, volume 520. Addison-Wesley Reading, 2010. find
  9. Zhuyun Dai and Jamie Callan. Context-aware sentence/passage term importance estimation for first stage retrieval. arXiv preprint arXiv:1910.10687, 2019a. — [arXiv:1910.10687](https://arxiv.org/abs/1910.10687) find
  10. Zhuyun Dai and Jamie Callan. Deeper text understanding for ir with contextual neural language modeling. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 985–988, 2019b. find
  11. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-XL: attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2978–2988, 2019. find
  12. Fartash Faghri, David J Fleet, Jamie Ryan Kiros, and Sanja Fidler. Vse++: Improving visual-semantic embeddings with hard negatives. arXiv preprint arXiv:1707.05612, 2017. — [arXiv:1707.05612](https://arxiv.org/abs/1707.05612) find
  13. Luyu Gao, Zhuyun Dai, and Jamie Callan. Understanding bert rankers under distillation. In Proceedings of the 2020 ACM SIGIR on International Conference on Theory of Information Retrieval, pp. 149–152, 2020a. find
  14. Luyu Gao, Zhuyun Dai, Zhen Fan, and Jamie Callan. Complementing lexical retrieval with semantic residual embedding. arXiv preprint arXiv:2004.13969, 2020b. — [arXiv:2004.13969](https://arxiv.org/abs/2004.13969) find
  15. Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. A deep relevance matching model for ad-hoc retrieval. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 55–64, 2016. find
  16. Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. arXiv preprint arXiv:1908.10396, 2020. — [arXiv:1908.10396](https://arxiv.org/abs/1908.10396) find
  17. Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: a new estimation principle for unnormalized statistical models. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pp. 297–304, 2010. find
  18. Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. Realm: retrieval-augmented language model pre-training. arXiv preprint arXiv:2002.08909, 2020. find
  19. Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. arXiv preprint arXiv:1911.05722, 2019. find our card
  20. Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang. Embedding-based retrieval in facebook search. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2553–2561, 2… find
  21. Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. Poly-encoders: architectures and pre-training strategies for fast and accurate multi-sentence scoring. In International Conference on Learning Representations, 2020. find
  22. Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 2019. find our card
  23. Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate importance sampling. In Advances in Neural Information Processing Systems, pp. 7265–7275, 2018. find
  24. Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: a large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pp. 1601–1611, 2017. find our card
  25. Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04906, 2020. find our card
  26. Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. arXiv preprint arXiv:1803.00942, 2018. — [arXiv:1803.00942](https://arxiv.org/abs/1803.00942) find
  27. Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. arXiv preprint arXiv:1911.00172, 2019. find
  28. Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert. arXiv preprint arXiv:2004.12832, 2020. find our card
  29. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:4… find our card
  30. Victor Lavrenko and W Bruce Croft. Relevance-based language models. In Association for Computing Machinery (ACM) Special Interest Group on Information Retrieval (SIGIR) Forum, volume 51, pp. 260–267. ACM New York, NY, USA, 2017. find
  31. Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 6086–6096, 2019. find our card
  32. Mike Lewis, Marjan Ghazvininejad, Gargi Ghosh, Armen Aghajanyan, Sida Wang, and Luke Zettlemoyer. Pre-training via paraphrasing. arXiv preprint arXiv:2006.15020, 2020a. find
  33. Patrick Lewis, Ethan Perez, Aleksandara Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmented generation for knowledge-intensive nlp tasks. arXiv preprint arXiv:2005.11401, 2020b. find
  34. Tie-Yan Liu. Learning to rank for information retrieval. Foundations and trends in information retrieval, 3(3): 225–331, 2009. find
  35. Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: a robustly optimized BERT pretraining approach. arXiv preprint arXiv:1907.11692, 2019. find
  36. Yi Luan, Jacob Eisenstein, Kristina Toutanove, and Michael Collins. Sparse, dense, and attentional representations for text retrieval. arXiv preprint arXiv:2005.00181, 2020. find our card
  37. Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(Nov):2579–2605, 2008. find
  38. Sean MacAvaney, Franco Maria Nardini, Raffaele Perego, Nicola Tonellotto, Nazli Goharian, and Ophir Frieder. Efficient document re-ranking for transformers by precomputing term representations. arXiv preprint arXiv:2004.14255, 2020. — [arXiv:2004.14255](https://arxiv.org/abs/2004.14255) find
  39. Bhaskar Mitra, Nick Craswell, et al. An introduction to neural information retrieval. Foundations and Trends® in Information Retrieval, 13(1):1–126, 2018. find
  40. Marius Mosbach, Maksym Andriushchenko, and Dietrich Klakow. On the stability of fine-tuning bert: Misconceptions, explanations, and strong baselines. arXiv preprint arXiv:2006.04884, 2020. find
  41. Rodrigo Nogueira and Kyunghyun Cho. Passage Re-ranking with BERT. arXiv preprint arXiv:1901.04085, 2019. find our card
  42. Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho. Document expansion by query prediction. arXiv preprint arXiv:1904.08375, 2019. find our card
  43. Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018. find our card
  44. Yifan Qiao, Chenyan Xiong, Zhenghao Liu, and Zhiyuan Liu. Understanding the behaviors of bert in ranking. arXiv preprint arXiv:1904.07531, 2019. — [arXiv:1904.07531](https://arxiv.org/abs/1904.07531) find
  45. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383–2392, 2016. find our card
  46. Adam Roberts, Colin Raffel, and Noam Shazeer. How much knowledge can you pack into the parameters of a language model? arXiv preprint arXiv:2002.08910, 2020. find
  47. James Thorne, Andreas Vlachos, Oana Cocarascu, Christos Christodoulopoulos, and Arpit Mittal. The fact extraction and verification (FEVER) shared task. In Proceedings of the 1st Workshop on Fact Extraction and VERification (FEVER), pp. 1–9, 2018. find
  48. Ellen M Voorhees. Variations in relevance judgments and the measurement of retrieval effectiveness. Information Processing & Management, 36(5):697–716, 2000. find
  49. Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: a multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07461, 2018. find our card
  50. Zhirong Wu, Yuanjun Xiong, Stella Yu, and Dahua Lin. Unsupervised feature learning via non-parametric instance-level discrimination. arXiv preprint arXiv:1805.01978, 2018. — [arXiv:1805.01978](https://arxiv.org/abs/1805.01978) find
  51. Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. End-to-end neural ad-hoc ranking with kernel pooling. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 55–64, 2017. find
  52. Wenhan Xiong, Xiang Lorraine Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oğuz. Answering complex open-domain questions with multi-hop dense retrieval. arXiv preprint arXiv:2009.12756, 2020. — [arXiv:2009.12756](https://arxiv.org/abs/2009.12756) find
  53. Ming Yan, Chenliang Li, Chen Wu, Bin Bi, Wei Wang, Jiangnan Xia, and Luo Si. Idst at trec 2019 deep learning track: Deep cascade ranking with generation-based document expansion and pre-trained language modeling. In Text REtrieval Conference. find
  54. Chen Zhao, Chenyan Xiong, Corby Rosset, Xia Song, Paul Bennett, and Saurabh Tiwary. Transformer-xh: multi-evidence reasoning with extra hop attention. In International Conference on Learning Representations, 2020. find
  55. Zhi Zheng, Kai Hui, Ben He, Xianpei Han, Le Sun, and Andrew Yates. Bert-qe: Contextualized query expansion for document re-ranking. arXiv preprint arXiv:2009.07258, 2020. find
  56. Table 6: Coverage of TREC 2019 DL Track labels on Dense Retrieval methods. Overlap with BM25 is calculated on top 100 retrieved documents. find
  57. TREC DL Passage Hole@10 Overlap w. BM25 5.9% 100% 25.8% 11.9% 20.2% 16.4% 14.8% 17.4% - - Method BM25 BM25 Neg BM25 + Rand Neg ANCE (FirstP) ANCE (MaxP) Recall@1K 0.685 0.569 0.662 0.661 - find