Cranfield query 185 asks for experimental studies on panel flutter. BM25 ranks the abstracts for it by estimating, term by term, how much each occurrence says about relevance. A searcher who types those four words is usually doing something simpler: guessing words that a good abstract would contain. Can a ranking be built directly on that guess, by asking which abstract would be most likely to produce the query as a sample of its own text?
The language modeling approach to retrieval does this. A language model is a probability distribution over strings of words. The approach estimates one model from each document, then ranks documents by the probability that the document's model generates the query. Ponte and Croft (1998) presented the first experiments with it (Manning, Raghavan, and Schütze, 2008, §12.2.3). Manning, Raghavan and Schütze (2008, chapter 12) give it a chapter of its own, after the vector space model and the probabilistic relevance models of this unit. Later articles on query expansion build on the definitions given here.
Here is the route. First we define a unigram language model and the query likelihood model, and work the textbook's two-document example. Then we see why the unsmoothed model fails, and how two smoothing methods repair it. Next we derive the rank-equivalent form of the score, which shows that smoothing supplies the IDF-like weighting and length normalization that the other models build in by hand. Finally we score query 185, measure the model on all of Cranfield, and place it beside the Binary Independence Model and BM25. The article assumes the probability primer of this unit.
A document as a source of words
Think of each document as a bag from which words are drawn at random, with replacement. Abstract 856, one of the nine relevant to query 185, has 172 tokens after stop words are removed and the rest stemmed, and 16 of them are panel. Drawing one token at random from it gives panel with probability $16/172 \approx 0.093$. A unigram language model is exactly this: a probability $P(t \mid M_d)$ for each term $t$ of the vocabulary, summing to 1, where $M_d$ names the model estimated from document $d$. "Unigram" means each word is drawn independently of the words before it, so the probability of a sequence is the product of the probabilities of its words.
Under that independence assumption, word order does not matter, and the model is a multinomial distribution over the bag of words (Manning, Raghavan, and Schütze, 2008, §12.1.3). The textbook notes that, for unigram models, the name "language model" is partly historical. Richer models condition each word on the previous one or two, but most language modeling work in retrieval has used unigram models (§12.1.2), and they are used throughout this article.
The simplest estimate is the maximum likelihood estimate (MLE): the term's relative frequency in the document,
$$\hat P_{\mathrm{mle}}(t \mid M_d) = \frac{\mathit{tf}_{t,d}}{L_d},$$
where $\mathit{tf}_{t,d}$ is the number of times $t$ occurs in $d$ and $L_d$ is the number of tokens in $d$.
The query likelihood model
The goal of a ranking is to order documents by how likely each is to be what the searcher wants. The textbook frames this as ranking by $P(d \mid q)$ and applies Bayes' rule (§12.2.1):
$$P(d \mid q) = \frac{P(q \mid d)\, P(d)}{P(q)}.$$
The denominator $P(q)$ is the same for every document and can be dropped. The prior $P(d)$ could encode evidence that a document is generally useful, such as its authority or recency. With a uniform prior it drops out too, and documents are ranked by $P(q \mid d)$, the probability of the query under the document's model. This is the query likelihood model. With a unigram model, the query's probability is a product over its tokens:
$$P(q \mid M_d) = \prod_{t \in q} P(t \mid M_d).$$
A query term that appears twice contributes its probability twice. The multinomial coefficient, which counts the orders in which the query's words could have been drawn, is the same for every document and is ignored.
Ponte and Croft's original model was slightly different: it treated each vocabulary term as present or absent in the query, in the manner of the Bernoulli event model. The multinomial version, used by Miller, Leek and Schwartz (1999) among others, became standard in later work (Manning, Raghavan, and Schütze, 2008, §12.2.3). The textbook also points out a connection with this site's classification unit. The multinomial query likelihood model is a multinomial Naive Bayes model in which every document is its own class.
The textbook's example
Manning, Raghavan and Schütze (2008, Example 12.3) use two one-line documents:
- $d_1$: Xyzzy reports a profit but revenue is down
- $d_2$: Quorus narrows quarter loss but revenue decreases further
Each has 8 tokens, so the collection has 16. The query is revenue down. By maximum likelihood, $P(\textit{revenue} \mid M_{d_1}) = 1/8$ and $P(\textit{down} \mid M_{d_1}) = 1/8$, so $P(q \mid M_{d_1}) = 1/64$.
Check your understanding. What does the maximum likelihood model give $d_2$?
Zero. The word down does not occur in $d_2$, so $P(\textit{down} \mid M_{d_2}) = 0$, and one zero factor makes the whole product zero. The document is about revenue decreasing, which a reader would count as relevant to revenue down, and the model rules it out entirely.
Why the unsmoothed model fails
Under the maximum likelihood estimate, any document missing any query term receives probability zero. Query likelihood then becomes a conjunctive query: only documents containing every query term are ranked at all. That is Boolean AND with a ranking of the survivors.
Query 185 shows the effect on a real collection. After processing, its terms are experiment, studi, panel and flutter. Only 2 of the 1,400 abstracts contain all four. Both are relevant, so they occupy ranks 1 and 2, and the other seven relevant abstracts are not retrieved; average precision is $(1 + 1)/9 = 0.222$. Over all 225 Cranfield queries, the unsmoothed model returns nothing for 216, and its mean average precision (MAP) is 0.010. Those are the figures for Boolean AND in comparing ranking models, as they must be.
The zeros are only the visible part of the problem. A word that occurs once in a document has a maximum likelihood probability well above what a second sample of text on the same subject would show; it occurred partly by chance. The textbook makes a stronger point: smoothing "actually implements major parts of the term weighting component" (§12.2.2). The derivation below shows how.
Smoothing with the collection
The repair is to borrow probability from the collection as a whole. The collection model $M_c$ is the relative frequency of each term across all documents:
$$P(t \mid M_c) = \frac{\mathit{cf}_t}{T},$$
where $\mathit{cf}_t$ is the collection frequency of $t$ (its total number of occurrences) and $T$ is the total number of tokens. A term absent from a document should then have a small probability, no larger than its frequency in the collection would suggest.
Jelinek-Mercer smoothing mixes the two models with a fixed weight $\lambda$ between 0 and 1 (Manning, Raghavan, and Schütze, 2008, eq. 12.10):
$$P(t \mid d) = \lambda\, \hat P_{\mathrm{mle}}(t \mid M_d) + (1 - \lambda)\, P(t \mid M_c).$$
Here $\lambda$ is the weight on the document, as in the textbook. Zhai and Lafferty (2001) write the same mixture with $\lambda$ on the collection, so their $\lambda$ is our $1 - \lambda$. A smaller document weight means more smoothing.
Dirichlet smoothing treats the collection model as a prior and the document's counts as evidence (Manning, Raghavan, and Schütze, 2008, eq. 12.11; Zhai and Lafferty, 2001):
$$P(t \mid d) = \frac{\mathit{tf}_{t,d} + \mu\, P(t \mid M_c)}{L_d + \mu}.$$
The parameter $\mu > 0$ acts as a number of imaginary tokens, distributed in proportion to the collection model and added to the document before its relative frequencies are taken. It is the same idea as the add-one smoothing of Naive Bayes, with a nonuniform prior. The probability primer derives that kind of estimate from a Beta prior; the Dirichlet distribution is the Beta's generalization to many outcomes.
The two methods are closer than they look. Rewriting the Dirichlet estimate,
$$\frac{\mathit{tf}_{t,d} + \mu P(t \mid M_c)}{L_d + \mu} = \frac{L_d}{L_d + \mu} \cdot \frac{\mathit{tf}_{t,d}}{L_d} + \frac{\mu}{L_d + \mu} \cdot P(t \mid M_c),$$
which is Jelinek-Mercer with a document weight $\lambda_d = L_d/(L_d + \mu)$ that depends on the document's length. A long document has more evidence of its own and is smoothed less.
Check your understanding. Rework the textbook example with Jelinek-Mercer and $\lambda = 1/2$. Then predict the result for Dirichlet smoothing with $\mu = 8$.
With $\lambda = 1/2$, revenue has collection probability $2/16$ and down has $1/16$. For $d_1$, $P(\textit{revenue}) = (1/8 + 2/16)/2 = 1/8$ and $P(\textit{down}) = (1/8 + 1/16)/2 = 3/32$, so $P(q \mid d_1) = 3/256$. For $d_2$, $P(\textit{revenue}) = 1/8$ and $P(\textit{down}) = (0 + 1/16)/2 = 1/32$, so $P(q \mid d_2) = 1/256$. These are the textbook's numbers. Dirichlet smoothing with $\mu = 8$ gives exactly the same values, because both documents have $L_d = 8$ and so $\lambda_d = 8/16 = 1/2$. The document $d_2$ now has a nonzero probability, ranked below $d_1$, which contains both words.
What smoothing does to the score
Here is the idea in one sentence: once the score is rewritten as a sum over the query terms a document actually contains, the collection probability appears in the denominator of each term's weight, which acts like an inverse document frequency, and the smoothing parameter leaves behind a per-document factor that acts like length normalization. Zhai and Lafferty (2001, §2) give the general form. Here it is worked for Dirichlet smoothing.
The formal version. Take logs, so the product becomes a sum, and split the query terms by whether the document contains them. For a term with $\mathit{tf}_{t,d} = 0$, the Dirichlet estimate is $\alpha_d P(t \mid M_c)$, with $\alpha_d = \mu/(L_d + \mu)$. So
$$\log P(q \mid d) = \sum_{t \in q,\ \mathit{tf}_{t,d} > 0} \log P(t \mid d) \;+ \sum_{t \in q,\ \mathit{tf}_{t,d} = 0} \log \big(\alpha_d P(t \mid M_c)\big).$$
The second sum runs over the terms the document lacks, which is awkward to compute. Add and subtract $\log(\alpha_d P(t \mid M_c))$ for the matched terms, so that the second sum covers every query term:
$$\log P(q \mid d) = \sum_{t \in q,\ \mathit{tf}_{t,d} > 0} \log \frac{P(t \mid d)}{\alpha_d P(t \mid M_c)} \;+\; n \log \alpha_d \;+\; \sum_{t \in q} \log P(t \mid M_c),$$
where $n$ is the number of query tokens. The last sum is the same for every document, so it can be dropped without changing the ranking. In the first sum, the ratio simplifies:
$$\frac{(\mathit{tf}_{t,d} + \mu P(t \mid M_c))/(L_d + \mu)}{\mu P(t \mid M_c)/(L_d + \mu)} = 1 + \frac{\mathit{tf}_{t,d}}{\mu\, P(t \mid M_c)}.$$
The rank-equivalent score is therefore
$$\mathrm{score}(q, d) = \sum_{t \in q,\ \mathit{tf}_{t,d} > 0} \log\!\left(1 + \frac{\mathit{tf}_{t,d}}{\mu\, P(t \mid M_c)}\right) + n \log \frac{\mu}{L_d + \mu}.$$
Three familiar components can be read off it:
- Term frequency. Each matched term's contribution grows with $\mathit{tf}_{t,d}$, logarithmically.
- An IDF-like weight. The contribution is larger when $P(t \mid M_c)$ is small, so rare terms count for more. Zhai and Lafferty note that the collection model as a reference distribution "has turned out to play a role very similar to the well-known IDF." It is computed from collection frequency rather than document frequency.
- Length normalization. The last term is negative and grows in magnitude with $L_d$. A long document pays a larger penalty, which offsets the higher counts its length gives it.
The same steps for Jelinek-Mercer give a contribution of $\log\big(1 + \lambda\, \mathit{tf}_{t,d} / ((1 - \lambda) L_d\, P(t \mid M_c))\big)$ for each matched term. There, $\alpha_d = 1 - \lambda$ is the same for every document, so the $n \log \alpha_d$ term drops out of the ranking, and length normalization comes only from the division by $L_d$ inside each contribution.
The rewritten form also makes the model efficient: only documents that contain at least one query term need to be scored, as with an inverted index and BM25. As a check on the algebra, for abstract 858 and query 185 with $\mu = 2000$, the full log probability is $-21.870$. The rank-equivalent score is $2.718$, and the dropped constant $\sum_t \log P(t \mid M_c)$ is $-24.588$. They add up to $-21.870$, as they should.
Query 185 by hand
The Cranfield collection, processed as in the rest of this unit, has 156,309 tokens. The collection model for the four query terms:
| Term | Collection frequency | $P(t \mid M_c)$ | Document frequency |
|---|---|---|---|
| experiment | 515 | 0.003295 | 339 |
| studi | 373 | 0.002386 | 240 |
| panel | 231 | 0.001478 | 45 |
| flutter | 282 | 0.001804 | 56 |
With $\mu = 2000$, a single occurrence of flutter contributes $\log(1 + 1/(2000 \times 0.001804)) = 0.245$, and a single occurrence of experiment contributes 0.141. The rarer term counts for more, as the derivation predicted.
Take abstract 856, with 172 tokens. It contains experiment 4 times, studi 5, panel 16 and flutter 11. For experiment, $\mu P(t \mid M_c) = 2000 \times 0.003295 = 6.590$, and the contribution is $\log(1 + 4/6.590) = \log 1.607 = 0.474$. The four contributions are 0.474, 0.717, 1.858 and 1.398. The length term is $4 \log(2000/2172) = -0.330$. The score is $4.118$, the highest in the collection.
The top 10 under Dirichlet smoothing with $\mu = 2000$, with each document's rank under BM25 ($k_1 = 1.2$, $b = 0.75$). Values are rounded to three decimals, so a row may not add exactly; R marks the relevant abstracts.
| Rank | Abstract | Length | tf (exp., studi, panel, flutter) | Matched-term sum | Length term | Score | BM25 rank |
|---|---|---|---|---|---|---|---|
| 1 | 856 R | 172 | 4, 5, 16, 11 | 4.447 | −0.330 | 4.118 | 1 |
| 2 | 857 R | 175 | 3, 2, 16, 7 | 3.661 | −0.336 | 3.326 | 2 |
| 3 | 766 R | 192 | 4, 0, 14, 10 | 3.548 | −0.367 | 3.182 | 3 |
| 4 | 859 R | 195 | 0, 0, 16, 9 | 3.109 | −0.372 | 2.737 | 9 |
| 5 | 858 R | 149 | 3, 0, 11, 7 | 3.005 | −0.287 | 2.718 | 5 |
| 6 | 658 | 166 | 1, 0, 13, 6 | 2.806 | −0.319 | 2.488 | 7 |
| 7 | 948 | 142 | 0, 0, 11, 7 | 2.630 | −0.274 | 2.356 | 11 |
| 8 | 390 | 90 | 0, 2, 5, 5 | 2.210 | −0.176 | 2.034 | 4 |
| 9 | 391 | 91 | 0, 0, 6, 7 | 2.187 | −0.178 | 2.009 | 10 |
| 10 | 1008 R | 58 | 1, 0, 6, 4 | 1.996 | −0.114 | 1.882 | 6 |
The two models agree on the top three and on most of the top ten. Their disagreements follow one pattern.
Check your understanding. Abstract 859 contains neither experiment nor studi, yet it rises from rank 9 under BM25 to rank 4. Abstract 390 contains three of the four terms and falls from 4 to 8. What property of the two scoring functions explains both moves?
Repetition. Abstract 859 uses panel 16 times, and abstract 390 uses it 5 times. Under query likelihood with $\mu = 2000$, panel contributes 0.990 at 5 occurrences and 1.858 at 16, a ratio of 1.88. BM25's term frequency factor, for a document of average length, is 1.774 at 5 occurrences and 2.047 at 16, a ratio of 1.15. BM25 saturates: after a few occurrences, more add little. Query likelihood grows with the logarithm of the count and keeps rewarding repetition. Here that helped, since 859 is relevant, and BM25's extra credit to 390 for a third matching term went to a nonrelevant abstract. Over the whole ranking the two effects nearly cancel: average precision is 0.785 for query likelihood and 0.784 for BM25.
An experiment on Cranfield
Query 185 is one query. The experiment below runs query likelihood on all 225 Cranfield queries, with the setup of comparing ranking models: the same tokenization, stop list and stemmer, the top 1,000 documents per query, and documents that contain at least one query term. It sweeps the Dirichlet prior $\mu$ from 50 to 10,000 and the Jelinek-Mercer document weight $\lambda$ from 0.1 to 0.9.
The results, rounded to three decimals:
| Model | MAP | P@10 | nDCG@10 |
|---|---|---|---|
| BM25 ($k_1 = 1.2$, $b = 0.75$) | 0.307 | 0.234 | 0.368 |
| Dirichlet, $\mu = 300$ | 0.284 | 0.220 | 0.351 |
| Dirichlet, $\mu = 2000$ | 0.266 | 0.200 | 0.320 |
| Jelinek-Mercer, $\lambda = 0.3$ | 0.284 | 0.215 | 0.347 |
| Jelinek-Mercer, $\lambda = 0.5$ | 0.281 | 0.218 | 0.347 |
| Unsmoothed (maximum likelihood) | 0.010 |
Several observations follow.
- Smoothing is not optional. Without it, the model returns nothing for 216 queries. With any of the settings tried, its MAP lies between the BIM's 0.220 and TF-IDF's 0.294.
- The best $\mu$ is far below 2000. Zhai and Lafferty (2004) found the optimal prior on TREC collections to have "a wide range (500–10000)" and to be "usually around 2,000". On Cranfield the best values are 200 and 300, with MAP falling steadily as $\mu$ grows beyond 500 (0.266 at 2000, 0.235 at 10,000). One plausible reason is document length. $\mu$ is measured in tokens, and a Cranfield abstract averages about 112 tokens after processing. Zhai and Lafferty's collections were full news and web documents, mostly far longer. With $\mu = 2000$, an average abstract gets a document weight $\lambda_d$ of about $112/2112 \approx 0.05$, so its own counts barely register.
- Verbose queries want heavy smoothing in Jelinek-Mercer. Zhai and Lafferty found the best Jelinek-Mercer setting to depend on query type: a collection weight of about 0.1 for short title queries, and about 0.7 for long verbose ones. Cranfield's queries are full sentences, such as "what similarity laws must be obeyed when constructing aeroelastic models of heated high speed aircraft". The best document weights here are 0.2 and 0.3, which is a collection weight of 0.7 to 0.8, in line with their finding for verbose queries.
- Query likelihood trails BM25 on Cranfield. Even the best settings, chosen on the very queries they are reported on, reach 0.284 against BM25's 0.307 with default settings, and also fall short of TF-IDF's 0.294. With $\mu = 2000$, query likelihood is worse than BM25 on 159 queries and better on 59 (paired randomization test, $p < 0.001$).
To choose settings fairly, the queries were split as in comparing ranking models into 112 development and 113 test queries. The development queries chose $\mu = 200$ and $\lambda = 0.2$. On the test queries both reached a MAP of 0.284, against 0.297 for BM25 with default settings ($p = 0.045$ for the Dirichlet run). The gap is smaller than on the full set, but it does not close.
Is the language modeling approach worse than BM25?
It would be easy to read the last row as a verdict on the model. That reading goes too far. The textbook reports that recent work had shown the approach to be very effective, beating TF-IDF and BM25 weights, while adding that there was perhaps still insufficient evidence of an advantage large enough to justify replacing a well-tuned vector space system (Manning, Raghavan, and Schütze, 2008, §12.3). Ponte and Croft (1998) reported an 11-point average precision of 0.2233 against 0.1868 for the INQUERY TF-IDF baseline on TREC topics 202 to 250, as summarized in the textbook's Figure 12.4.
Cranfield is one small collection of short abstracts with long, sentence-like queries, and it differs from those collections in ways the comparison is sensitive to. Query 185 points to one candidate explanation, the absence of saturation, which helps some queries and hurts others. Another is the IDF-like component: query likelihood weighs terms by collection frequency, and BM25 by document frequency. This experiment does not separate those effects. What it does show is that the ranking produced by a principled model still depends on estimation choices, here the amount and form of smoothing, as much as on the principle.
Relevance, revisited
The Probability Ranking Principle ranks by the probability of relevance, and the Binary Independence Model estimates that probability from a model of relevant and nonrelevant documents. Query likelihood mentions no relevance variable at all. A common misreading follows: that the language modeling approach abandons relevance and ranks by something unrelated to it.
The textbook calls the absence of an explicit relevance variable the main apparent difference from the BIM, and adds that "this may not be the correct way to think about things" (§12.3). Lafferty and Zhai (2003) argue that a unified account can be given of the probabilistic semantics underlying both approaches (Manning, Raghavan, and Schütze, 2008, §12.5). The textbook also notes that reversing the direction, generating the document from a model of the query, leads with appropriate modeling choices to the BIM (§12.4). The textbook's justification for the model is a story about relevance: the searcher imagines a document that would satisfy the need and draws query words from it. Ranking by $P(q \mid d)$ then ranks documents by how plausibly each is the one the searcher had in mind.
The lack of an explicit relevance variable has a practical cost all the same. The BIM re-estimates its weights directly from judged documents, as in relevance feedback. Query likelihood has nothing comparable to re-estimate, so the textbook lists relevance feedback as hard to integrate into the basic model (§12.3).
Extensions
The extensions of the basic model add what the unigram query likelihood model leaves out (Manning, Raghavan, and Schütze, 2008, §12.4):
- Comparing models. Lafferty and Zhai (2001) estimate a language model for the query as well as for the document, and rank by the Kullback–Leibler divergence between the two models. With a query model estimated from the query alone, this ranks documents exactly as query likelihood does. Its value is that the query model can be improved, for example from feedback documents.
- Relevance models. Lavrenko and Croft (2001) estimate a model of the relevant documents' language from the top-ranked documents, and use it in place of the query's own words. This brings pseudo-relevance feedback into the framework, and its RM3 variant is worked on Cranfield in query expansion.
- Translation models. Berger and Lafferty (1999) let a document generate a query word it does not contain through a translation probability from a word it does contain, such as decreases to down. This addresses vocabulary mismatch inside the model.
- Structured queries. Metzler and Croft (2004) estimated the beliefs of the inference network model from smoothed language models, keeping INQUERY's query operators. The combined model was implemented in the Indri search engine (Croft, Metzler, and Strohman, 2010, §7.4).
The name can mislead a modern reader. "Language model" now usually means a large neural network that predicts the next word from a long context. The models of this article are counts and their ratios, estimated from a single document, with one parameter. They share the name and the central idea, a probability distribution over text, but little else.
What we have learned
A document can be treated as a sample from a language model, and documents ranked by the probability that their models generate the query. Without smoothing, that probability is zero for any document missing a query term, and the model collapses into Boolean AND: on Cranfield it returned nothing for 216 of 225 queries. With smoothing, the score becomes a sum over matched terms of a weight that grows with term frequency and falls with collection frequency, plus a length penalty. That is TF-IDF and length normalization, derived rather than assumed. On query 185 it matched BM25 almost exactly. Over all of Cranfield the best smoothing gave a MAP of 0.284, below BM25's 0.307, and the best $\mu$ was far smaller than the value recommended for longer documents.
Every model so far ranks documents for the query the searcher typed. When a searcher marks some results as relevant, how can those judgments become a better query? Relevance feedback takes up that question.
References
- Berger, A., and Lafferty, J. (1999). Information retrieval as statistical translation. In Proceedings of SIGIR 1999, 222–229. record
- Croft, W. B., Metzler, D., and Strohman, T. (2010). Search Engines: Information Retrieval in Practice, section 7.4. Addison-Wesley. record · 11 pages
- Lafferty, J., and Zhai, C. (2001). Document language models, query models, and risk minimization for information retrieval. In Proceedings of SIGIR 2001, 111–119. record
- Lafferty, J., and Zhai, C. (2003). Probabilistic relevance models based on document and query generation. In W. B. Croft and J. Lafferty (Eds.), Language Modeling for Information Retrieval, 1–10. Kluwer Academic Publishers. record
- Lavrenko, V., and Croft, W. B. (2001). Relevance-based language models. In Proceedings of SIGIR 2001, 120–127. record · 3 pages
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 12. Cambridge University Press. record · 83 pages
- Metzler, D., and Croft, W. B. (2004). Combining the language model and inference network approaches to retrieval. Information Processing and Management, 40(5), 735–750. record · 2 pages
- Miller, D. R. H., Leek, T., and Schwartz, R. M. (1999). A hidden Markov model information retrieval system. In Proceedings of SIGIR 1999, 214–221. record
- Ponte, J. M., and Croft, W. B. (1998). A language modeling approach to information retrieval. In Proceedings of SIGIR 1998, 275–281. record · 2 pages
- Zhai, C., and Lafferty, J. (2001). A study of smoothing methods for language models applied to ad hoc information retrieval. In Proceedings of SIGIR 2001, 334–342. record
- Zhai, C., and Lafferty, J. (2004). A study of smoothing methods for language models applied to information retrieval. ACM Transactions on Information Systems, 22(2), 179–214. record