Probabilistic Retrieval

information retrievalprobabilistic models

Ranking documents by an estimate of how likely they are to be relevant, from the Probability Ranking Principle through the Binary Independence Model and BM25 to inference networks and relevance feedback, with an experiment comparing the models on the Cranfield collection.

Every retrieval system works with uncertainty. A query is a few words standing in for an information need the system cannot observe, and a document's index entry is a lossy summary of what it is about. Whether a given document will satisfy a given user is never known in advance. Probabilistic retrieval makes that uncertainty the starting point. Boolean retrieval asks whether a document matches a query, and the vector space model asks how similar it is. Probabilistic retrieval asks how likely the document is to be relevant, and ranks by the answer.

The theoretical anchor is the Probability Ranking Principle, which shows that ranking by probability of relevance is optimal under stated conditions. The rest of the topic is the problem the principle leaves open: estimating that probability from evidence a system actually has. The Binary Independence Model estimates it from which query terms a document contains and turns the estimate into a sum of term weights. Along the way it explains inverse document frequency as the weight a term deserves when nothing is known about relevance. The 2-Poisson model explains why term frequency should saturate, and Okapi BM25 builds that saturation, together with document length normalization, into a ranking function that has remained a standard baseline for three decades. Bayesian inference networks take a different route, representing the structure of a query, its phrases, alternatives, and weighted concepts, as a network through which evidence is combined.

A thread runs through all of these models. Each one introduces an assumption it knows to be false, such as the independence of terms or the irrelevance of term counts, because the assumption makes the probabilities estimable. Each then succeeds or fails according to whether the assumption distorts the ordering of documents, which is all a ranking needs to get right. The topic ends with an experiment: the comparison article runs Boolean retrieval, TF-IDF, the BIM, and BM25 on the same test collection, showing how much each model's assumptions cost or gain in practice.

Articles

Foundations

Models

  • The Binary Independence Model: documents as sets of terms, the derivation of the retrieval status value, the Robertson–Spärck Jones weight, and how IDF emerges.
  • The 2-Poisson model and eliteness: the model of term frequency behind BM25's saturation curve, tested on real term counts.
  • Okapi BM25: term frequency saturation, document length normalization, the IDF component, and tuning.
  • BM25F: extending BM25 to documents with fields such as title, body, and anchor text, traced on this site's own search index.
  • Bayesian inference networks: retrieval as inference over a network of documents, concepts, and queries, as in the INQUERY system.

Using relevance information

  • Relevance feedback: Rocchio and Ide drawn in two dimensions, re-estimating term weights and expanding queries from documents a user has judged, with results on Cranfield.
  • Pseudo-relevance feedback: assuming the top results are relevant, which queries gain and which lose, and how query drift happens.

In practice

  • Implementing BM25: a tested implementation over an inverted index, accumulators and pruning traced by hand, the effect of $k_1$ and $b$, and the variants that different systems compute under the same name.
  • Comparing ranking models: Boolean retrieval, TF-IDF, the BIM, and BM25 on the Cranfield collection, with precision-recall curves, per-query differences, significance tests, and parameter tuning.
  • The vector space model, whose TF-IDF weighting the BIM explains in probabilistic terms.
  • Language models for retrieval, which rank by the probability of generating the query rather than the probability of relevance.
  • Naive Bayes classification, which relies on the same conditional independence assumption as the BIM.
  • Retrieval evaluation, which supplies the measures used to compare the models.

Course materials

My implementation of the Binary Independence Model for the course is HW04 on GitHub, and it later became the search engine for the Goodreads project.

References

  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 11. Cambridge University Press.
  • Robertson, S., and Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389.
  • Turtle, H., and Croft, W. B. (1991). Evaluation of an inference network-based retrieval model. ACM Transactions on Information Systems, 9(3), 187–222.