Back

Relevance-Based Language Models

Victor LavrenkoW. Bruce Croft

article2001SIGIR1,872 citationsTest of Time Award

Proposes a formal method for estimating relevance-based language models directly from user queries without training data, bridging classical probabilistic retrieval and language modeling to improve ad-hoc search and topic tracking.

Listen

Modern information retrieval systems often struggle to accurately interpret user search queries because queries are brief, ambiguous, and lack explicit labels indicating which documents in a large collection are truly relevant. Traditional probabilistic retrieval frameworks excelled at modeling relevant documents when training data existed, but failed in practice because real-world queries arrive without pre-labeled examples. Conversely, newer language modeling techniques bypass relevance modeling entirely by treating queries as rigid text samples, making standard improvements like query expansion difficult to integrate.

The article demonstrates a formal probabilistic technique to estimate a "relevance model"—the probability distribution of words across relevant documents—using only the user's initial query and no prior training data. It evaluates how effectively this unsupervised relevance model ranks documents in standard retrieval benchmarks and tracks topics in continuous news streams.

To construct this model without training data, the approach estimates the joint probability of vocabulary words co-occurring with query words across the top fifty documents retrieved by an initial search. The authors evaluated two formulation methods across two standard benchmarks: ad-hoc search across more than 164,000 Associated Press news stories using short topic titles, and topic tracking across approximately 63,000 broadcast and newswire stories spanning six months.

The experimental findings demonstrate significant performance gains. First, the conditional sampling approach (Method 2) closely approximated true relevance distributions, achieving lower cross-entropy error than a model built from an actual known relevant document. Second, in standard document retrieval, the relevance model improved average precision over baseline language models by 29.5% on one query set and 10.5% on a second query set, while noticeably improving precision among top-ranked results. Third, in topic tracking tasks without any training stories, the unsupervised relevance model outperformed a supervised system trained on one relevant example and nearly matched the accuracy of a system trained on four relevant examples, achieving a 10% miss rate at a 1% false alarm rate.

These results show that search engines and filtering systems do not require manual training examples or complex parameter tuning to achieve high retrieval accuracy. Because the proposed method replaces short queries with a rich probability distribution over the entire vocabulary, it naturally addresses synonyms and word ambiguity without the instability common to traditional query expansion techniques. This provides a formal, reliable foundation for high-precision retrieval, summarization, and automated topic tracking applications.

Organizations developing search, media monitoring, or intelligence filtering tools should consider adopting query-based relevance models as a robust alternative to standard language modeling baselines. For implementation, teams should prefer the conditional sampling method (Method 2) due to its superior stability across different document universe sizes. Further technical work should explore integrating explicit training examples into the model when available and refining document smoothing techniques to extract additional performance gains.

statistical language modelsrelevance-based language modelsquery expansion techniquead-hoc retrieval task
Lavrenko et al (2001).pdf
Cover for Relevance-Based Language Models

Topics

statistical language models

Keywords

relevance-based language modelsquery expansion techniquead-hoc retrieval tasktopic modelsdocument modelstranslation modeltopic trackingtopic detectionprobabilistic modelsquery generation

Table of Contents

  • 1. INTRODUCTION
  • 2. RELATED WORK
  • 4.3 TDT topic tracking
  • 7. ACKNOWLEDGMENTS
  • 8. REFERENCES

Knowls

  1. Knowl 1 — Relevance Model Approximation via Query Co-Occurrence

    model/method

    In the relevance-based language modeling framework, every user information need is assumed to have an underlying generative relevance model RR, representing a probability distribution over the vocabulary. Both the relevant documents and the user query Q=q1extextellipsisqkQ = q_1 ext{ extellipsis } q_k (where each qiq_i is a query term) are treated as random samples generated from RR, although the generative sampling mechanisms for queries and documents may differ.

    In standard ad-hoc retrieval, no training examples or relevance judgments are available to estimate the probability P(w∣R)P(w|R) of observing word ww in relevant documents. In the absence of training data, the relevance model distribution P(w∣R)P(w|R) is approximated by the conditional probability of generating word ww given that the sequence of query words q1extextellipsisqkq_1 ext{ extellipsis } q_k has been observed from the same underlying process:

    P(w∣R)≈P(w∣q1 …qk)=P(w,q1 …qk)P(q1 …qk)P(w|R) \approx P(w|q_1 \text{ \textellipsis } q_k) = \frac{P(w, q_1 \text{ \textellipsis } q_k)}{P(q_1 \text{ \textellipsis } q_k)}

    Here, P(w,q1 …qk)P(w, q_1 \text{ \textellipsis } q_k) is the joint probability of observing word ww together with the query terms, and P(q1 …qk)=∑w′P(w′,q1 …qk)P(q_1 \text{ \textellipsis } q_k) = \sum_{w'} P(w', q_1 \text{ \textellipsis } q_k) ensures the probability distribution sums to 1 over all vocabulary terms.

  2. Knowl 2 — Relevance Model Estimation via Conditional Sampling

    equation

    Under the conditional sampling formulation (Method 2) for relevance models, a word ww is initially chosen according to a prior distribution P(w)P(w). Conditioned on ww, each query term qiq_i (i=1, extellipsis ,ki = 1, \text{ extellipsis }, k) is assumed to be sampled independently through an intermediate unigram distribution MiM_i selected from a finite universe of document language models M\mathcal{M} according to P(Mi∣w)P(M_i|w).

    The resulting joint probability of term ww co-occurring with query q1 …qkq_1 \text{ \textellipsis } q_k is:

    P(w,q1 …qk)=P(w)∏i=1k∑Mi∈MP(Mi∣w)P(qi∣Mi)P(w, q_1 \text{ \textellipsis } q_k) = P(w) \prod_{i=1}^k \sum_{M_i \in \mathcal{M}} P(M_i|w) P(q_i|M_i)

    where the conditional distribution over document models is calculated by Bayes' rule assuming a uniform prior P(Mi)P(M_i):

    P(Mi∣w)=P(w∣Mi)P(Mi)P(w)P(M_i|w) = \frac{P(w|M_i) P(M_i)}{P(w)}

    and the prior probability of word ww is the marginal probability over the universe M\mathcal{M}:

    P(w)=∑M∈MP(w∣M)P(M)P(w) = \sum_{M \in \mathcal{M}} P(w|M) P(M)

    This method enforces conditional independence of query words given ww, allowing each query term qiq_i to originate from a different document model MiM_i associated with ww.

  3. Knowl 3 — Document Ranking via Relevance-to-Non-Relevance Odds Ratio

    model/method

    Following Robertson's Probability Ranking Principle under a word-independence assumption, documents DD (represented as word sequences w∈Dw \in D) are ranked by the odds of being generated by the relevant language model RR versus the non-relevant language model NN:

    P(D∣R)P(D∣N)=∏w∈DP(w∣R)P(w∣N)\frac{P(D|R)}{P(D|N)} = \prod_{w \in D} \frac{P(w|R)}{P(w|N)}

    where:

    • P(w∣R)P(w|R) is the estimated probability of word ww under the query-based relevance model.
    • P(w∣N)P(w|N) is the probability of word ww in the non-relevant class, which is approximated by the collection/background language model P(w∣G)P(w|G) (the collection frequency of ww divided by the total number of tokens in the corpus) because non-relevant documents constitute nearly the entire collection for any specific query.

  4. Knowl 4 — Relevance Model Estimation via i.i.d. Sampling

    equation

    Under the identically and independently distributed (i.i.d.) sampling formulation (Method 1), the vocabulary word ww and all query words q1, extellipsis ,qkq_1, \text{ extellipsis }, q_k are assumed to be drawn independently from the exact same unigram document model MM, which is chosen from a finite universe of unigram distributions M\mathcal{M} with prior probability P(M)P(M).

    The joint probability of observing word ww together with query sequence q1 …qkq_1 \text{ \textellipsis } q_k is given by:

    P(w,q1 …qk)=∑M∈MP(M)P(w∣M)∏i=1kP(qi∣M)P(w, q_1 \text{ \textellipsis } q_k) = \sum_{M \in \mathcal{M}} P(M) P(w|M) \prod_{i=1}^k P(q_i|M)

    This assumes mutual conditional independence among all query words and the candidate word ww given the single selected model MM.

  5. Knowl 5 — Parameter Estimation and Smoothing Protocol for Relevance Models

    experimental setup

    To implement relevance model estimation efficiently and effectively, the universe of unigram models M\mathcal{M} is restricted to the top 50 document models MDM_D retrieved by a baseline language modeling query-likelihood ranking for query Q=q1 …qkQ = q_1 \text{ \textellipsis } q_k.

    Each document language model MDM_D is smoothed via Jelinek-Mercer linear interpolation with a background collection model P(w∣G)P(w|G):

    P(w∣MD)=λtf(w,D)∑vtf(v,D)+(1−λ)P(w∣G)P(w|M_D) = \lambda \frac{tf(w, D)}{\sum_v tf(v, D)} + (1 - \lambda) P(w|G)

    where tf(w,D)tf(w, D) is the raw count of word ww in document DD, P(w∣G)P(w|G) is the corpus relative frequency of ww, and λ\lambda is a fixed smoothing parameter set to λ=0.6\lambda = 0.6 (with stable performance observed for λ∈[0.4,0.8]\lambda \in [0.4, 0.8]). The prior distribution P(M)P(M) over models in M\mathcal{M} is set to uniform (P(M)=1/∣M∣P(M) = 1/|\mathcal{M}|). The resulting estimated relevance probabilities P(w∣R)P(w|R) are smoothed using the same linear interpolation with P(w∣G)P(w|G).

  6. Knowl 6 — TREC Ad-Hoc Retrieval Performance of Relevance Models

    data/table

    The relevance model estimated with conditional sampling (Method 2) was evaluated on the Associated Press (AP) newswire collection (164,000 documents) from TREC volumes 1 and 2 across title queries 101–150 and 151–200. The baseline is a standard unigram language model (LM) ranking documents by query likelihood with linear interpolation smoothing.

    TREC queries 101–150 (title) TREC queries 151–200 (title)
    Metric LM Rel.M %chg LM Rel.M %chg
    Relevant 4805 4805 4933 4933
    Rel. Ret. 2981 3733 +25.23* 3288 3222 -2.01*
    Precision @ 0.00 0.6132 0.6161 +0.5 0.7699 0.7248 -5.9
    Precision @ 0.10 0.4090 0.4686 +14.6 0.5669 0.5913 +4.3
    Precision @ 0.20 0.3267 0.4066 +24.5* 0.4494 0.5201 +15.7*
    Precision @ 0.30 0.2815 0.3562 +26.6* 0.3628 0.4797 +32.2*
    Precision @ 0.40 0.2277 0.3171 +39.3* 0.3239 0.4090 +26.3*
    Precision @ 0.50 0.1922 0.2803 +45.8* 0.2596 0.3258 +25.5*
    Precision @ 0.60 0.1579 0.2393 +51.6* 0.2187 0.2649 +21.1*
    Precision @ 0.70 0.1094 0.1799 +64.5* 0.1772 0.1852 +4.5
    Precision @ 0.80 0.0693 0.1205 +74.0* 0.1436 0.1134 -21.0
    Precision @ 0.90 0.0441 0.0578 +30.8 0.1048 0.0561 -46.5*
    Precision @ 1.00 0.0267 0.0113 -57.7* 0.0319 0.0165 -48.2
    Mean Avg Prec 0.2021 0.2617 +29.50* 0.2878 0.3182 +10.55
    Precision @ 5 0.3840 0.4240 +10.4 0.5400 0.5200 -3.7
    Precision @ 10 0.3760 0.3940 +4.8 0.4880 0.4980 +2.0
    Precision @ 20 0.3260 0.3810 +16.9 0.4430 0.4690 +5.9
    Precision @ 100 0.2104 0.2652 +26.0* 0.2532 0.2832 +11.8
    R-Precision 0.2546 0.2935 +15.27* 0.3212 0.3519 +9.56

    Asterisks indicate statistically significant differences at the 95% confidence level according to a one-sided Wilcoxon test. The relevance model substantially improves mean average precision (+29.5% on queries 101–150 and +10.55% on 151–200) and improves precision across intermediate recall levels.

  7. Knowl 7 — Cross-Entropy Comparison with the True Topic Model

    empirical result

    On the TDT2 dataset (96 topics with exhaustive relevance assessments over approximately 63,000 stories), the relevance model estimated via conditional sampling (Method 2) achieves lower cross-entropy with the true relevance model (constructed directly from all known relevant documents) than the i.i.d. sampling model (Method 1).

    Both estimation methods achieve minimal cross-entropy when the universe size ∣M∣|\mathcal{M}| is around 50 top-ranked documents. Method 2 achieves lower absolute cross-entropy than Method 1 and degrades much more slowly as ∣M∣|\mathcal{M}| increases up to 1,000 documents. Furthermore, the cross-entropy achieved by Method 2 using only the query is strictly lower than the cross-entropy obtained from a model built from a single known relevant document smoothed with corpus background statistics.

  8. Knowl 8 — Unsupervised Topic Tracking Performance in TDT

    empirical result

    On the Topic Detection and Tracking (TDT2) tracking task evaluated via Detection Error Tradeoff (DET) curves (plotting Miss probability vs. False Alarm probability), an unsupervised relevance model constructed solely from 2–3 word topic titles outperforms a supervised TDT tracking system provided with Nt=1N_t = 1 known relevant training story, and performs on par with a supervised tracking system provided with Nt=2N_t = 2 training stories.

    Both the query-based relevance model and the supervised system with Nt=2N_t = 2 achieve approximately a 10% miss rate at a 1% false alarm rate. In contrast, standard query-likelihood language models and language models with heuristic query expansion applied to the topic title perform substantially worse than supervised tracking systems.

Coverage note — None was omitted; all central methodological contributions (formal derivations of Method 1 and Method 2, ranking formulation, estimation details) and experimental evaluations (cross-entropy, TREC ad-hoc retrieval, and TDT tracking) are fully represented.

References

  1. 1.J. Allan, J. Callan, F. Feng, and D. Malin. INQUERY and TREC-8. In D. Harman, editor, Proceedings of the Eighth Text REtrieval Conference (TREC-8), 1999.
  2. 2.J. Allan, R.Papka, and V.Lavrenko. On-line new event detection and tracking. In Proceedings of ACM SIGIR, pp 37-45, 1998.
  3. 3.D. Beeferman, A. Berger, and J. Lafferty. Statistical models for text segmentation. In Machine Learning, vol.34, pages 1–34, 1999.
  4. 4.A. Berger, R. Caruana, D.Cohn, D. Freitag, and V. Mittal. Bridging the lexical chasm: Statistical approaches to answer-finding. In Proceedings of SIGIR, pages 192–199, 2000.
  5. 5.A. Berger and J. Lafferty. Information retrieval as statistical translation. In Proceedings on the 22nd annual international ACM SIGIR conference, pages 222–229, 1999.
  6. 6.A. Berger and V. Mittal. OCELOT: a system for summarizing web pages. In Proceedings of SIGIR, pages 144–151, 2000.
  7. 7.P. Brown, S. D. Pietra, V. D. Pietra, and R. Mercer. The mathematics of statistical machine translation: Parameter estimation. In Computational Linguistics, 19(2), pages 263–311, 1993.
  8. 8.S. F. Chen and J. T. Goodman. An empirical study of smoothing techniques for language modeling. In Proceedings of the 34th Annual Meeting of the ACL, 1996.
  9. 9.C. Cieri, D.Graff, M.Liberman, N.Martey, and S.Strassel. The TDT-2 text and speech corpus. In Proceedings of the DARPA Broadcast News Workshop, pp 57-60, 1999.
  10. 10.D. Hiemstra. Using language models for information retrieval. In PhD Thesis, University of Twente, 2001.
  11. 11.D. Hiemstra and A. de Vries. Relating the new language models of information retrieval to the traditional retrieval models. In CTIT Technical Report TR-CTIT-00-09, 2000.
  12. 12.H. Jin, R. Schwartz, S. Sista, and F. Walls. Topic tracking for radio, TV broadcast and newswire. In Proceedings of DARPA Broadcast News Workshop, pp 199-204, 1999.
  13. 13.A. Martin, G. Doddington, T. Kamm, and M. Ordowski. The DET curve in assessment of detection task performance. In EuroSpeech, pages 1895–1898, 1997.
  14. 14.D. Miller, T. Leek, and R. Schwartz. A hidden markov model information retrieval system. In Proceedings on the 22nd annual international ACM SIGIR conference, pages 214–221, 1999.
  15. 15.J. Ponte. A Language Modeling Approach to Information Retrieval. PhD thesis, Dept. of Computer Science, University of Massachusetts, Amherst, 1998.
  16. 16.J. Ponte and W. B. Croft. A language modeling approach to information retrieval. In Proceedings on the 21st annual international ACM SIGIR conference, pages 275–281, 1998.
  17. 17.S. Robertson and K. S. Jones. Relevance weighting of search terms. In Journal of the American Society for Information Science, vol.27, 1977.
  18. 18.S. Robertson and S. Walker. Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In Proceedings of the 17th annual international ACM SIGIR conference, pages 232–241, 1996.
  19. 19.S. E. Robertson. The Probability Ranking Principle in IR, pages 281–286. Morgan Kaufmann Publishers, Inc., San Francisco, California, 1997.
  20. 20.S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. OKAPI at TREC-3. In D. Harman, editor, Proceedings of the 3rd Text REtrieval Conference (TREC-3), 1996.
  21. 21.F. Song and W. B. Croft. A general language model for information retrieval. In Proceedings on the 22nd annual international ACM SIGIR conference, pages 279–280, 1999.
  22. 22.H. Turtle and W. B. Croft. Efficient probabilistic inference for text retrieval. In Proceedings of RIAO 3, pages 644–651, 1991.
  23. 23.C. J. van Rijsbergen. A theoretical basis for the use of co-occurrence data in information retrieval. Journal of Documentation, 33:106–119, 1977.
  24. 24.J. Xu and W. B. Croft. Improving the effectiveness of informational retrieval with local context analysis. In ACM TOIS, vol. 18, no. 1, pages 79–112, January 2000.
  25. 25.J. Yamron, I. Carp, L. Gillick, S.Lowe, and P. van Mulbregt. Topic tracking in a news stream. In Proceedings of DARPA Broadcast News Workshop, pp 133-136, 1999.
  26. 26.J. Yamron, S. Knecht, and P. van Mulbregt. Dragon’s tracking and detection systems for the TDT2000 evaluation. In Proceedings of Topic Detection and Tracking Workshop, pp 75-80, 2000.

Citation

MLA
Lavrenko, V., and W. B. Croft. “Relevance-Based Language Models”. ACM SIGIR Forum, vol. 51, no. 2, 2017, pp. 260–67, https://doi.org/10.1145/3130348.3130376.
APA
Lavrenko, V., & Croft, W. B. (2017). Relevance-Based Language Models. ACM SIGIR Forum, 51(2), 260–267. https://doi.org/10.1145/3130348.3130376
Chicago
Lavrenko, V., and W. B. Croft. 2017. “Relevance-Based Language Models”. ACM SIGIR Forum 51 (2): 260–67. https://doi.org/10.1145/3130348.3130376.
Harvard
Lavrenko, V. and Croft, W.B. (2017) “Relevance-Based Language Models”, ACM SIGIR Forum, 51(2), pp. 260–267. Available at: https://doi.org/10.1145/3130348.3130376.
Vancouver
1. Lavrenko V, Croft WB (2017) Relevance-Based Language Models. ACM SIGIR Forum 51:260–267

BibTeX

@article{Lavrenko_2017, title={Relevance-Based Language Models}, volume={51}, ISSN={0163-5840}, url={http://dx.doi.org/10.1145/3130348.3130376}, DOI={10.1145/3130348.3130376}, number={2}, journal={ACM SIGIR Forum}, publisher={Association for Computing Machinery (ACM)}, author={Lavrenko, Victor and Croft, W. Bruce}, year={2017}, month=Aug, pages={260–267} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF