The Vector Space Model

information retrievalvector space modelrankingTF-IDF

Ranked retrieval by representing documents and queries as weighted term vectors and scoring documents by their similarity to the query. Zones and weighted zone scoring, TF-IDF, cosine similarity, efficient scoring with an inverted index, weighting variants, and document-to-document similarity.

The Boolean model answers a query with a set: a document matches or it does not. The vector space model answers with a ranking. Every document receives a score expressing how well it matches the query, and documents are returned in order of that score. The searcher no longer has to tune a query until the result set is a manageable size. A long list is no problem, because the best matches come first, and a document that matches only part of the query can still appear, ranked below those that match more.

The model rests on one representational idea. A document is a vector with one dimension for every term in the vocabulary, and its value in each dimension is a weight saying how important that term is to the document. A query is a vector in the same space. Documents are ranked by how similar their vectors are to the query's, measured by the angle between them. Two questions follow, and the rest of the topic answers them. How should the weights be chosen? The usual answer is TF-IDF, which rewards terms that occur often in a document and rarely in the collection. And how can similarity be computed for millions of documents in a fraction of a second? The answer is to accumulate scores from the inverted index, touching only documents that share a term with the query.

The articles share one running example: four short documents (a car-insurance headline, a car review, an auto-insurance page that never says car, and a page about car loans) and the query best car insurance. TF-IDF weighting builds its count matrix and weights, cosine similarity normalizes and scores it, with a demo for editing the documents and weighting schemes, the variants score it under eight schemes, computing vector scores traces both evaluation orders on its postings, finding similar documents compares its documents with each other, and the limits applies relevance feedback to it. Following one example through shows what each refinement changes.

Gerard Salton and his colleagues developed the model in the SMART system over the 1960s and 1970s (see the history). Its weighting ideas remain in use. The term frequency and inverse document frequency components of TF-IDF reappear, in refined form, in BM25, and the geometry of vectors and angles reappears in the dense embeddings of neural retrieval.

Articles

Before vectors

  • Zones and weighted zone scoring: metadata fields and parametric search, zone indexes, scoring by which parts of a document match, and learning the zone weights from relevance judgments.

The model

  • TF-IDF weighting: term frequency and the bag-of-words view, inverse document frequency, and their product as a term weight.
  • Cosine similarity: documents and queries as vectors, why angle beats distance, length normalization, and worked comparisons.
  • Computing vector scores: scoring with postings lists and accumulators, precomputed document lengths, and selecting the top results with a heap.

Refinements

  • Variants of TF-IDF weighting: sublinear term frequency, maximum term frequency normalization, the SMART notation for weighting schemes, and pivoted length normalization.
  • Finding similar documents: comparing every pair of documents in a collection, why it is quadratic, sparse-matrix and inverted-index methods, and benchmarks from my course assignment.
  • Strengths and limits of the vector space model: the independence assumption, vocabulary mismatch, Rocchio relevance feedback, and the model's descendants.
  • Term statistics explains the distributions of term frequency and document frequency that TF-IDF builds on.
  • Evaluation measures whether one ranking is better than another, which is needed to compare weighting schemes.
  • Probabilistic retrieval derives a weighting similar to TF-IDF from the probability of relevance.

Course materials

My document similarity system for the course is HW03 on GitHub. It finds the most similar pairs of documents in a collection under three weighting schemes, with standard, parallel, and sparse-matrix implementations.

References

  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 6–7. Cambridge University Press.
  • Salton, G., Wong, A., and Yang, C. S. (1975). A vector space model for automatic indexing. Communications of the ACM, 18(11), 613–620.
  • Salton, G., and Buckley, C. (1988). Term-weighting approaches in automatic text retrieval. Information Processing and Management, 24(5), 513–523.