A search engine built on term matching cannot find a passage that answers a query in other words. The course met that limit several times: as the term independence of the vector space model, whose last article names it the model's central weakness, as the vocabulary mismatch that query expansion works around, and as the stated limits of this site's own search engine. This unit is about the representation that removes the limit at its source. A text becomes a dense vector, a few hundred real numbers with no component tied to any one term, produced by a trained function called an encoder. Texts with related meanings receive nearby vectors, and retrieval becomes a search for the vectors nearest the query's.
The unit follows that idea from words to passages to a working retriever. It starts with vectors for single words, where the whole mechanism can be seen and proved: a shallow network trained to tell observed word pairs from random ones ends up factorizing a matrix of co-occurrence statistics, the same kind of matrix the course factorized in latent semantic indexing. It then fixes the geometry, since "near" has three common meanings that agree only under a condition. With that in place it builds the encoder for whole passages, the loss that trains it, and the dense passage retriever, and then turns to what makes training hard and where one vector per passage fails. The last article is about choosing among encoders.
What the unit assumes
The course's vector space model unit, in particular cosine similarity; the singular value decomposition as latent semantic indexing develops it; and the evaluation measures of retrieval evaluation (nDCG, recall at a cutoff). The articles on encoders assume the transformer as the library's Language Models from Scratch builds it, from self-attention to the full block. Gradients are computed by the chain rule and nothing beyond it.
What is proved, cited and measured
Derived or proved on the page: the gradient of skip-gram with negative sampling and the theorem that its objective is maximized by a shifted pointwise mutual information matrix when every pair is observed and the dimension suffices, and otherwise drives the dot products of unobserved pairs toward $-\infty$; the conditions under which dot product, cosine and Euclidean distance rank alike, and the reductions among the three searches; the contrastive (InfoNCE) loss and its gradient, a Kullback-Leibler bound on the contrastive loss and from it the bound that connects the loss to mutual information; the gradient of the margin mean squared error used in distillation; the dimension bound of Luan and colleagues for single-vector retrieval, proved from a cited concentration inequality, with an exact error law for Gaussian projections and a counting bound on result sets. Cited and not proved: every published measurement of effectiveness, that concentration inequality, the general form of the mutual-information bound, in which the scores may depend on all the candidates, and the other results each article lists as cited in its own account of what it proves.
The experiments use three bodies of text. Word vectors are trained on the Brown corpus, the million-word corpus the library's natural language processing article already counts. Retrieval is run on the Cranfield collection, the course's standard test collection, and on this site's own passages with its 60 judged queries. The passage encoder is one small pretrained model, pinned by revision and run on a laptop processor; the articles that use it give its name and revision. Training a retriever on a large question-answering collection is beyond that machine, so results at that scale are reported from the papers, with the table each number comes from. Seeded experiments follow the site's convention of 30 runs, reported as a median with quartiles.
The unit uses one notation throughout. A query is $q$ and a passage $p$; their vectors are $\vec{q} = E_Q(q)$ and $\vec{p} = E_P(p)$ in $\mathbb{R}^m$, where $E_Q$ and $E_P$ are the query and passage encoders (one symbol $E$ when a single network serves both). The score of a passage for a query is $s(q, p)$, and each article says which measure it is.
Words and geometry
- Word Embeddings: skip-gram with negative sampling (Mikolov et al., 2013) stated and its gradient derived; the theorem of Levy and Goldberg (2014) that the objective is maximized when each dot product equals the pair's pointwise mutual information less the logarithm of the number of negative samples, proved with its conditions; GloVe's objective (Pennington et al., 2014); the objective maximized full-batch from 30 seeds, which is not a run of word2vec, and compared with the explicit factorization on Brown.
- Similarity Measures for Embeddings: dot product, cosine and Euclidean distance; the proof that the three rank alike for every query exactly when all vectors have one length; the reductions that turn maximum inner product search, nearest neighbor search and cosine search into one another; what normalization discards.
Encoders and their training
- Sentence and Passage Encoders: from token vectors to one vector by pooling, why an untuned BERT (Devlin et al., 2019) gives poor sentence vectors, Sentence-BERT's siamese training (Reimers and Gurevych, 2019), and the bi-encoder defined.
- Contrastive Training for Retrieval: the InfoNCE loss derived as a classification among one positive passage and sampled negatives, in-batch negatives and the role of batch size, temperature, the gradient worked on a small batch, and the bound on the loss by a Kullback-Leibler divergence from which the mutual-information bound follows.
- Dense Passage Retrieval: the dense passage retriever of Karpukhin and colleagues (2020) in full, and a dense retriever run on Cranfield and on this site's passages against BM25 and BM25F.
- Hard Negatives and Distillation: why random negatives stop teaching, negatives mined from the index, false negatives, and distilling a cross-encoder into a bi-encoder with the margin mean squared error loss.
Limits and evaluation
- Limits of Single-Vector Retrieval: what one vector cannot hold, with the dimension bound of Luan and colleagues (2021) proved from a cited concentration inequality, results outside the training domain, exact-match failures on this site's queries, and when BM25 wins.
- Evaluating Embedding Models: recall and nDCG for first-stage retrieval, the BEIR (Thakur et al., 2021) and MTEB (Muennighoff et al., 2023) benchmarks and what they measure, variable-length embeddings, and choosing a model for a corpus with a paired comparison.
Finding the nearest vectors quickly among millions is the subject of the next unit, Vector Search. Ranking a short list with a model that reads query and passage together, and combining dense with lexical retrieval, is the unit after it, Neural Ranking and Hybrid Retrieval.
References
- Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT 2019, Volume 1, 4171–4186. record · 4 pages
- Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W. (2020). Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP 2020, 6769–6781. arXiv:2004.04906. record · 10 pages
- Levy, O., and Goldberg, Y. (2014). Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems 27, 2177–2185. record · 3 pages
- Luan, Y., Eisenstein, J., Toutanova, K., and Collins, M. (2021). Sparse, dense, and attentional representations for text retrieval. Transactions of the Association for Computational Linguistics, 9, 329–345. arXiv:2005.00181. record · 2 pages
- Mikolov, T., Sutskever, I., Chen, K., Corrado, G., and Dean, J. (2013). Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems 26, 3111–3119. arXiv:1310.4546. record · 2 pages
- Muennighoff, N., Tazi, N., Magne, L., and Reimers, N. (2023). MTEB: Massive text embedding benchmark. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, 2014–2037. record · 3 pages
- Pennington, J., Socher, R., and Manning, C. D. (2014). GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 1532–1543. record · 5 pages
- Reimers, N., and Gurevych, I. (2019). Sentence-BERT: Sentence embeddings using siamese BERT-networks. In Proceedings of EMNLP-IJCNLP 2019, 3982–3992. record · 2 pages
- Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., and Gurevych, I. (2021). BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track. arXiv:2104.08663. record · 7 pages