INFS7410 · Information Retrieval and Web Search · Week 3

Retrieval Models I: Term-based Lexical Models

What a relevance model is (an encoder plus a scorer), where fast retrieval models sit next to slower rerankers, and the family of term-based lexical models that score documents by the terms they share with the query: the Boolean model and coordination level matching, professional Boolean search, TF, IDF and TF-IDF, the vector space model, the probability ranking principle, the Binary Independence Model and BM25. Every scoring formula is explained symbol by symbol, read aloud, and worked through with numbers, including how the BM25 parameters k₁, b and k₂ change the score.

1. Relevance models: encoder and scorer

Sources: slides 2–6, 10–11, 13 · Video 1 (Overview of relevance model, retrieval vs. reranking) · Video 2 (Term-based lexical retrieval models) 00:02–02:07

A relevance model is a computational framework that estimates the relevance of documents to a given query, based on representations of the query and the documents and a function that measures their relationship. Every search system needs some way of deciding which documents answer a query and how well they answer it; the relevance model is that mechanism.

1.1 Example: where is UQ located?

A user searches Where is UQ located and two candidate web pages exist:

A relevance model gives each candidate a score that reflects how well it matches the query. If 1 means highly relevant and 0 means irrelevant, Page A might score 0.98 and Page B 0.03. These scores are the basis for ranking.

1.2 Structure: encoder plus scorer

Every relevance model has two components:

  1. An encoder converts the query and the document into representations: term vectors, embeddings, or other forms.
  2. A scorer computes how well the two encoded representations match and outputs the relevance score.
representations Query “Where is UQ located” Encode Query vector [0, 1, 1, 0, 1, …] Document “UQ is … in Brisbane …” Encode Document vector [1, 1, 0, 1, 0, …] Scorer Score 0.98
The general structure of a relevance model: encode the query and the document, then score how well the two representations match. The same structure covers everything from keyword search to neural rankers.

1.3 The relevance-model cost table

Encoder cost and scorer cost are the two main dimensions of complexity in relevance models. Throughout the course, models are compared by placing them in a table with scorer cost on one axis and encoder cost on the other. Simple models such as the Boolean model and BM25 are fast on both axes; neural rerankers (for example monoBERT, covered in later weeks) are far more expensive. The table starts empty and fills up as the course introduces each model.

Scorer cost Encoder cost O(1) O(|d|) Term-based lexical models Boolean · TF · TF-IDF VSM · BIM · BM25 ? ? ? ? ?
The relevance-model cost table. This week's models all sit in the cheapest cell: encoding cost O(|d|) and scoring cost effectively O(1) per query–document pair. Later weeks fill the other cells.
Key ideaEncoding cost is proportional to document length |d|, because every term must be processed when the index is built. Scoring is often described as O(1) per query–document pair, and this assumes an inverted index (Week 1) pre-filters the candidate documents. Scoring then sums weights over only the terms the query and document share, which is a small constant number. The cost stays flat as documents and collections grow, which makes term-based models fast, scalable, and still widely used in modern search engines.

George E. P. Box's remark (slide 10), “All models are wrong, but some are useful”, frames the whole week. Retrieval models are deliberate simplifications of what relevance really is; the useful ones make the simplifications that matter least.

PracticeName the two components of a relevance model, and explain why term-based models can score a query–document pair in roughly constant time.
Think about which terms actually contribute to the score, and what data structure finds the candidate documents.
AnswerThe encoder turns the query and document into representations; the scorer compares them and outputs a score. Scoring is roughly constant time because an inverted index supplies only documents that contain query terms, and the score sums weights over the few terms shared by query and document. That number depends on the query length, which is small, and stays independent of document length and collection size. Encoding costs O(|d|) because each term of the document is processed once at indexing time.

2. Retrieval models versus reranking models

Sources: slides 7–9 · Video 1 (Overview of relevance model, retrieval vs. reranking) 02:48–04:22

Within relevance models, this course focuses on two main categories: retrieval models and reranking models.

AspectRetrieval modelReranking model
Operates onThe entire document collectionOnly the top-n results from the retriever (typically 10–1,000 documents)
ScoresEvery document in the corpusOnly a selected list of documents
Speed requirementMust be fast and scalable; uses approximations and heuristicsCan afford to be slower and much more sophisticated
Typical techniquesInverted index plus lexical matching (for example BM25)Deeper features and heavy machine-learning models (for example monoBERT)
RoleFirst stage: efficiently narrows down the candidatesLater stage: reorders the candidates with refined relevance estimates

In practice, systems use a cascade: a fast first-stage retriever followed by one or more powerful rerankers.

Document collection millions to billions of documents every document is scored Retrieval model (first stage) fast and scalable, for example BM25 with an inverted index top-n candidate list (10–1,000) Reranking model slower and stronger, for example monoBERT reordered list Final ranking
The cascade: a fast retriever narrows a huge collection to a short candidate list, and an expensive reranker reorders only that list.
Key ideaA retrieval model is a specific type of relevance model. It is fast and efficient, and it normally forms the first stage of modern search systems, narrowing down the candidates before deeper analysis and reranking. The next few weeks cover a range of retrieval models in detail; this week covers the term-based lexical ones.
PracticeA system must answer queries over 50 million web pages within 100 ms and wants to use a BERT-based model for quality. Where does each model go in the pipeline, and why?
AnswerBM25 (or another lexical retrieval model) goes first: it scores the whole collection quickly through the inverted index and returns, say, the top 1,000. The BERT-based model goes second as a reranker, scoring only those 1,000 candidates, because running it over 50 million pages per query would take far too long. This is the cascade: cheap and broad first, expensive and precise second.

3. Term-based lexical models

Sources: slides 12–16 · Video 2 (Term-based lexical retrieval models)

Term-based lexical models are some of the oldest and simplest retrieval models. They rely on the lexical form of the text, the actual surface terms, and typically measure relevance by the overlapping terms between queries and documents.

Common lexical modelsTechniques that can be applied
Boolean model · TF (term frequency) · TF-IDF · Vector space model (VSM) · Binary Independence Model (BIM) · BM25Stopword removal · Stemming · Document length normalisation

The techniques in the right-hand column are the text-processing steps from Week 1; coupling them with a lexical model improves its effectiveness.

3.1 Everything is a sparse vector

In practice these models are implemented with an inverted index for efficiency. Conceptually, though, all lexical representations (Boolean, TF, TF-IDF and so on) can be viewed as sparse vectors:

he born what uq where a yes is university in australia how come on brisbane was Q 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 D1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 D2 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 Q ∧ D1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 D1 shares uq and is with Q: score 1. D2 shares no term with Q: score 0.
The Boolean model viewed as vectors. Each column is one vocabulary term; a 1 means the term is present. The query and D1 overlap on uq and is (green columns), so D1 scores 1; D2 overlaps nowhere and scores 0.

3.2 The Boolean overlap score in vector form

With binary vectors, the simplest scorer asks one question: do the query and the document share at least one term?

score(q,d)=1 ⁣[ ∑j=1∣V∣V(q)j∧V(d)j  >  0] \mathrm{score}(q,d) = \mathbb{1}\!\left[\, \sum_{j=1}^{|V|} V(q)_j \wedge V(d)_j \;>\; 0 \right]
Where
q,dq, d
the query and the document being scored
V(q),V(d)V(q), V(d)
binary vectors of qq and dd over the vocabulary: entry jj is 1 if term jj is present, 0 otherwise
j, ∣V∣j,\ |V|
index of a vocabulary term (one vector dimension), and the vocabulary size (number of dimensions)
∧\wedge
logical AND: 1 only when both entries are 1
1[⋅]\mathbb{1}[\cdot]
indicator function: 1 if the condition inside holds, 0 if it fails
Read it aloud The score of document d for query q is one if the sum, over every vocabulary term j, of “term j is in the query AND term j is in the document” is greater than zero, and zero otherwise.
Formula in plain words Line up the two binary vectors, mark every position where both have a 1, and count the marks. Any count above zero means the document shares at least one query term and receives a 1; a count of zero gives a 0. The output is only ever 0 or 1, so adding more shared terms leaves the score unchanged: this is matching, with no grading. The slide writes the same test as sum(V(q) & V(d)) > 0, which is the behaviour of a query whose terms are joined by OR.

Worked example 1The Boolean model viewed as vectors

Assume a fixed token space (all possible terms): [he, born, what, uq, where, a, yes, is, university, in, australia, how, come, on, brisbane, was]. Encode the query and two documents as binary vectors (1 = term present):

TextBinary vector
Q: “Where is UQ”[0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,0]
D1: “UQ is a University in Australia”[0,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0]
D2: “He was born in Brisbane”[1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1]
1
Q ∧ D1 has 1s at uq and is: the sum is 2, which is greater than 0.
2
Q ∧ D2 is all zeros: D2 shares no query term, so the sum is 0.
ResultD1 scores 1 (retrieved) and D2 scores 0 (left out).
Watch outThis vector view is only an illustration. Real Boolean retrieval uses inverted indexes, which are far more efficient at scale.
PracticeEncode D3 = “Where was he born” over the same token space and give its Boolean overlap score for Q = “Where is UQ”.
AnswerD3 = [1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1] (he, born, where, was). It shares where with the query, so the overlap sum is 1 and the score is 1, the same score D1 gets with two shared terms. The overlap score cannot tell a one-term match from a two-term match.

4. The Boolean model

Sources: slides 17–18, 22 · Video 3 (Boolean model)

The Boolean model takes its name from its reliance on Boolean logic and set theory to characterise relevance.

4.1 Operators as set operations

Ret(a  AND  b)=Ret(a)∩Ret(b)Ret(a  OR  b)=Ret(a)∪Ret(b)Ret(a  NOT  b)=Ret(a)∖Ret(b) \begin{aligned} \mathrm{Ret}(a \;\mathrm{AND}\; b) &= \mathrm{Ret}(a) \cap \mathrm{Ret}(b) \\ \mathrm{Ret}(a \;\mathrm{OR}\; b) &= \mathrm{Ret}(a) \cup \mathrm{Ret}(b) \\ \mathrm{Ret}(a \;\mathrm{NOT}\; b) &= \mathrm{Ret}(a) \setminus \mathrm{Ret}(b) \end{aligned}
Where
a,ba, b
query terms or sub-expressions
Ret(x)\mathrm{Ret}(x)
the set of documents that satisfy expression xx (for a single term: the documents that contain it, read from its postings list)
∩\cap
intersection: documents in both sets
∪\cup
union: documents in either set
∖\setminus
set difference: documents in the first set with the second set's documents removed
Read it aloud The documents retrieved for “a AND b” are the intersection of those retrieved for a and for b; for “a OR b”, the union of the two sets; for “a NOT b”, the documents retrieved for a minus those retrieved for b.
Formula in plain words Each term selects a set of documents (its postings list from Week 1). AND keeps only documents in both sets, so adding AND clauses can only shrink the result. OR merges the sets, so adding OR clauses can only grow it. NOT removes every document containing the negated term. Because each operation returns a set, a document is simply in or out; nothing says how well it fits.

4.2 Worked examples on a three-document collection

The term–document incidence matrix below records which terms occur in which documents (1 = present; empty cells are 0, left blank for clarity):

Termd1d2d3
a11
jaguar111
is11
an1
animal1
my1
new1
guitar1
big1
cat1
jaguar AND animal jaguar: d1, d2, d3 animal d1 d2 d3 Result: {d1} jaguar NOT cat jaguar: d1, d2, d3 cat d3 d1 d2 Result: {d1, d2}
AND intersects the sets (left: only d1 contains both jaguar and animal). NOT removes the negated set (right: d3 contains cat, so d1 and d2 remain). Green marks the retrieved documents.

Worked example 2q = “jaguar”

1
Retrieve every document that satisfies the expression, that is, every document containing jaguar.
2
The jaguar row has a 1 in all three columns.
Result{d1, d2, d3}

Worked example 3q = “jaguar AND animal”

AND is an intersection operator in set terms.

1
Documents matching jaguar: {d1, d2, d3}.
2
Documents matching animal: {d1}.
3
Intersection: {d1, d2, d3} ∩ {d1} = {d1}.
Result{d1}

Worked example 4q = “jaguar NOT cat”

NOT removes from the retrieved set every document that contains the negated term.

1
Documents matching jaguar: {d1, d2, d3}.
2
Documents matching cat: {d3}.
3
Remove them: {d1, d2, d3} \ {d3} = {d1, d2}.
Result{d1, d2}
PracticeExercise from the lecture: evaluate q = “jaguar AND car” on the same collection.
Work out the set for each term first, then apply the operator.
AnswerDocuments matching jaguar: {d1, d2, d3}. The term car appears in no document, so its set is ∅. Intersection: {d1, d2, d3} ∩ ∅ = ∅. Nothing is retrieved: one unmatched conjunct empties the whole result, which shows how brittle strict Boolean matching is.
PracticeEvaluate q = “jaguar AND (animal OR guitar)”.
Answeranimal OR guitar = {d1} ∪ {d2} = {d1, d2}. Then jaguar AND {d1, d2} = {d1, d2, d3} ∩ {d1, d2} = {d1, d2}. The brackets matter: without them the expression could be read differently.

4.3 Advantages and disadvantages

AdvantagesDisadvantages
Results are predictable and relatively easy to explain.Effectiveness depends entirely on the user writing a good query: it suits expert users with a precise understanding of their needs, the collection, and Boolean logic.
Many features beyond terms can be incorporated, for example conditions on creation date or language.Simple queries (for example one term) usually work poorly.
Very efficient: postings can be stored as a single bit, and many documents are eliminated from the search very quickly.Complex queries are difficult to formulate; UQ researchers work on building high-performing complex queries automatically for professional settings such as medical literature search.
TakeawaysTwo fundamental problems push us beyond the Boolean model. On its own, the Boolean model therefore serves most users poorly, because it cannot cope with the large vocabulary gap between users and collections (the vocabulary mismatch problem from Week 1).
PracticeWhy is the Boolean model efficient, and why does the same property make it hard to use for ordinary searchers?
AnswerIt only needs to know whether each term is present (one bit per posting) and can discard every document that fails a clause immediately, so evaluation is fast set arithmetic. The same all-or-nothing logic means the user must predict the exact words relevant documents use and combine them correctly; a missing synonym or an over-strict AND silently drops relevant documents, and there is no ranking to soften the mistake.

5. Ranking on top of Boolean: coordination level matching

Sources: slides 22–24 · Video 3 (Boolean model) 05:05–05:37

Strategies do exist for adding ranking on top of Boolean logic. The classic one is coordination level matching (CLM).

CLM(Q,D)=∑c ∈ C(Q)1[ D satisfies c ]for every D that satisfies Q \mathrm{CLM}(Q,D) = \sum_{c \,\in\, C(Q)} \mathbb{1}\big[\, D \text{ satisfies } c \,\big] \qquad \text{for every } D \text{ that satisfies } Q
Where
Q,DQ, D
the Boolean query and a document
C(Q)C(Q)
the set of Boolean clauses that make up QQ (for plain keyword queries: the query terms)
cc
one clause (or term) of the query
1[⋅]\mathbb{1}[\cdot]
indicator: 1 if DD satisfies clause cc, otherwise 0
Read it aloud The coordination level of document D for query Q is the sum, over every clause c of Q, of one if D satisfies c and zero otherwise, computed for every document that satisfies Q as a whole.
Formula in plain words First apply the Boolean query as a filter; only documents that satisfy it take part. Then count how many of the query's clauses each surviving document satisfies and sort by that count, highest first. Each extra satisfied clause adds exactly one point, so every clause counts equally, and documents with the same count tie. The filter still applies, so CLM adds an ordering to the Boolean result without adding partial matching.
All documents 1. Filter satisfies Q? others dropped 2. Rank by clauses satisfied 1. Blue doc 1 3 8 16 4 clauses 2. Green doc 5 13 2 clauses both documents satisfy the 18-line query
CLM in two steps: the Boolean query filters the collection, then the survivors are ordered by how many clauses they satisfy (clause numbers shown in the boxes).

Worked example 5Rank two documents that satisfy an 18-clause query

Both documents satisfy the professional Boolean query shown in Section 6 (slide 24).

1
Consider only documents that satisfy the Boolean query: the query must still be satisfied.
2
Count the clauses: the blue document satisfies clauses 1, 3, 8 and 16 (4 clauses); the green document satisfies clauses 5 and 13 (2 clauses).
3
Rank in decreasing order of clauses satisfied.
ResultBlue document first (CLM = 4), green document second (CLM = 2).
PracticeDocuments A and B satisfy a Boolean query Q; A satisfies clauses 2, 7 and 11, B satisfies clauses 1 and 3. Document C satisfies 5 clauses but fails Q overall. Give the CLM ranking.
AnswerA (3 clauses) then B (2 clauses). C is excluded: CLM only reorders documents that satisfy the whole Boolean query, however many individual clauses they match.

6. Boolean search in professional practice

Sources: slides 19–21, 24 · Video 4 (Boolean professional)

The Boolean model may look simple, even naive, yet it is thoroughly used in professional contexts: patent retrieval, legal retrieval, contract retrieval and medical and scientific literature retrieval. A very popular search engine for medical literature is PubMed (advanced search), which primarily uses a Boolean retrieval model with additional advanced features.

Below is a professional Boolean query of the kind written for systematic reviews, similar to the queries in the course project:

1.  (adrenergic* and antagonist*).tw.
2.  (adrenergic* and block$).tw.
3.  (adrenergic* and beta-receptor*).tw.
4.  (beta-adrenergic* and block*).tw.
5.  (beta-blocker* and adrenergic*).tw.
6.  (blockader*.tw. or Propranolol/ or Sotalol/)
7.  or/1-6
8.  Lung Diseases, Obstructive/
9.  exp Pulmonary Disease, Chronic Obstructive/
10. emphysema*.tw.
11. (chronic* adj3 bronchiti*).tw.
12. (obstruct*.tw. adj3 (lung* or airway*).tw.)
13. COPD.tw.
14. COAD.tw.
15. COBD.tw.
16. AECB.tw.
17. or/8-16
18. 7 and 17

Each line is a Boolean clause. The line numbers are convenience labels outside the query itself; lines 7, 17 and 18 use them as shorthand to express how the clauses are assembled.

18: 7 AND 17 7: OR of lines 1–6 17: OR of lines 8–16 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 drug clauses (beta-blockers) disease clauses (COPD)
How the 18 lines assemble: a document must match at least one drug clause (line 7) and at least one disease clause (line 17), which line 18 joins with AND.
OperatorExampleWhat it does
Groupingor/1-6Combines clauses 1–6 with OR (line 18 combines 7 AND 17).
Sub-grouping( … )Brackets group Boolean sub-expressions inside a clause.
Wildcardantagonist*Matches any string that starts with the given prefix.
Explicit stemmingblock$The $ operator performs explicit stemming.
Field restriction.tw.Limits the search to specific index fields (text words: title and abstract), similar to ti in the project queries.
Adjacencyadj3The two terms or expressions must occur within n words of each other; in line 12, obstruct* must appear within 3 words of lung* or airway*.
MeSH headingPropranolol/Matches categorical metadata attached to documents. MeSH is a controlled (fixed) medical vocabulary whose terms are organised hierarchically.
MeSH explosionexp …/Replaces the MeSH term with itself plus all its children in the MeSH hierarchy (line 9).
Exam angleBe ready to name each operator family on slide 21 (wildcard, explicit stemming, grouping, sub-grouping, adjacency, field restriction, MeSH heading, MeSH explosion) and to explain how lines 7, 17 and 18 assemble the clauses.
PracticeWhat must a document contain to satisfy line 18, and how does line 9 differ from line 8?
AnswerLine 18 is 7 and 17: the document must satisfy at least one of lines 1–6 (a beta-blocker clause) and at least one of lines 8–16 (a COPD clause). Line 8 matches documents indexed with exactly the MeSH heading “Lung Diseases, Obstructive”. Line 9 uses exp, so it matches the heading “Pulmonary Disease, Chronic Obstructive” and every narrower heading beneath it in the MeSH hierarchy.

7. Beyond Boolean: the TF model

Sources: slides 25–28 · Video 5 (TF)

The TF (term frequency) model still treats documents and queries as a bag of words: a collection of items with repetitions and without order. The step forward from Boolean is that TF models term frequencies, the count of each term in a document. Boolean query operators are not required, although query languages often still support them.

document d1 (ordered text) A jaguar is an animal … animal … animal drop order, keep counts bag of words for d1 a × 1 jaguar × 1 is × 1 an × 1 animal × 3
A bag of words forgets word order and keeps how often each term occurs; the TF model scores with these counts.

The three example documents now become a term–document count matrix. The documents are d1 = “A jaguar is an animal… animal… animal”, d2 = “My new Jaguar guitar… big…” and d3 = “A jaguar is a big cat… animal…”.

Termd1d2d3
a12
jaguar111
is11
an1
animal31
my1
new1
guitar1
big11
cat1

7.1 Formal definition

score(D,Q)=∑i=1∣Q∣f(qi,D) \mathrm{score}(D,Q) = \sum_{i=1}^{|Q|} f(q_i, D)
Where
D,QD, Q
the document being scored and the query
∣Q∣|Q|
the size of the query (number of query terms)
qiq_i
the ii-th query term
f(qi,D)f(q_i, D)
term frequency: the number of times qiq_i occurs in DD
Read it aloud The score of document D for query Q is the sum, for i from one to the size of the query, of the frequency of query term q-i in D.
Formula in plain words Goal: reward documents that contain the query terms the most. Walk through the query terms (the query's terms only), count each one in the document, and add the counts. Every extra occurrence adds exactly one point, with no ceiling, so a document that repeats a single query term many times can beat a document that contains all query terms at moderate frequency. Every term also counts the same: an occurrence of “a” is worth as much as an occurrence of “jaguar”.

Worked example 6TF scores for q = “jaguar animal”

Score each document as the sum, over the query terms, of that term's count in the document.

Documentf(jaguar, d)f(animal, d)TF scoreRank
d11341
d21013
d31122
score(d1)=f(jaguar,d1)+f(animal,d1)=1+3=4 \mathrm{score}(d_1) = f(\text{jaguar}, d_1) + f(\text{animal}, d_1) = 1 + 3 = 4
ResultRanking: d1 (4) ≻ d3 (2) ≻ d2 (1).
TakeawaysTwo problems with TF motivate the rest of the week.
Common trapThe sum runs over the query terms. Terms that appear in the document and are absent from the query contribute nothing to the score.
PracticeFrom slide 28: compute the TF scores of d1, d2 and d3 for q = “a jaguar” and for q = “a cat”. What goes wrong?
Answer “a jaguar”:d1=1+1=2d2=0+1=1d3=2+1=3“a cat”:d1=1+0=1d2=0d3=2+1=3 \begin{aligned} \text{“a jaguar”:}\quad \text{d1} &= 1 + 1 = 2 \\ \text{d2} &= 0 + 1 = 1 \\ \text{d3} &= 2 + 1 = \mathbf{3} \\ \text{“a cat”:}\quad \text{d1} &= 1 + 0 = 1 \\ \text{d2} &= 0 \\ \text{d3} &= 2 + 1 = \mathbf{3} \end{aligned} In the first query d3 wins mainly because of the stopword “a”, which says nothing about jaguars; for “a cat”, d1 scores above d2 purely through “a”. TF treats every term as equally important.

8. IDF and TF-IDF

Sources: slides 29–33 · Video 6 (IDF, TF-IDF)

8.1 Motivation: terms differ in importance

Different terms have different importance. Stopwords such as “the”, “a” and “who” are rarely useful for judging relevance. Recall Zipf's law from Week 1: a small set of terms occurs extremely often, followed by a long tail of terms that rarely appear. One classical response is a stoplist that removes stopwords entirely (slide 29 shows one running from “a”, “a's”, “able” to “yourselves”, “z”, “zero”). A stoplist has problems:

8.2 Inverse document frequency

This motivates a function that dampens the effect of terms that occur too often in the collection to be meaningful for estimating relevance:

score(D,Q)=∑i=1∣Q∣log⁡N1+ni \mathrm{score}(D,Q) = \sum_{i=1}^{|Q|} \log \frac{N}{1+n_i}
Where
∣Q∣|Q|
number of query terms; ii indexes them
NN
total number of documents in the collection
nin_i
document frequency: the number of documents that contain query term ii
1+ni1+n_i
the +1 keeps the fraction finite when a term occurs in no document
log⁡N1+ni\log \frac{N}{1+n_i}
the idf of term ii, written idf(i)idf(i); any log base works (the plot below uses base 10)
Read it aloud The score of document D for query Q is the sum, over the query terms i, of the log of N divided by one plus n-i.
Formula in plain words For each query term, divide the collection size by (roughly) the number of documents containing the term, then take the log. A rare term (small nin_i) gives a large ratio and a high weight; a term found almost everywhere gives a ratio near 1 and a weight near 0. The log compresses the range, so a term in 10 documents weighs more than one in 1,000, by a margin far smaller than the hundredfold count difference. Growing the collection (larger NN) raises every weight equally and leaves the order of terms unchanged.
3.0 3.5 4.0 4.5 5.0 200 400 600 800 1000 document frequency nᵢ (documents containing the term) idf = log₁₀(N / (1 + nᵢ)) rare terms: high idf common terms: low idf
IDF plotted against document frequency for the Reuters newswire collection (N = 806,791 documents). Rare terms get high IDF and common terms low IDF. The relation is logarithmic: it smooths off quickly, leaving a small head of very-high-IDF rare terms and a long tail of low-IDF common terms.
Watch outRead the IDF-only sum as running over the query terms that D actually contains. If absent terms counted, every document would receive the same score, since idf values are properties of the collection.
Key ideaTF depends only on the document being scored. IDF uses collection-level statistics: for a given term, its IDF is the same for every document.

8.3 Putting things together: TF-IDF

IDF alone is a weak model too, because it ignores how often the term appears in the document. TF and IDF each define term weights, and they are usually used together, multiplied for each query term (written TF × IDF, or tf-idf):

score(D,Q)=∑i=1∣Q∣tf(i,D)×idf(i) \mathrm{score}(D,Q) = \sum_{i=1}^{|Q|} tf(i, D) \times idf(i)
Where
tf(i,D)tf(i, D)
frequency of query term ii in document DD (the f(qi,D)f(q_i, D) of Section 7)
idf(i)idf(i)
inverse document frequency of term ii: log⁡N1+ni\log \frac{N}{1+n_i}
∣Q∣|Q|
number of query terms
Read it aloud The score of D for Q is the sum, over the query terms i, of the term frequency of i in D times the inverse document frequency of i.
Formula in plain words Each query term contributes “how often it appears here” (tf) scaled by “how rare it is overall” (idf). A term reaches a high tf-idf when it occurs often in this document and in few documents in the collection. Common terms get an idf near zero, so even many occurrences add little: the score tends to filter them out. Terms absent from the document have tf = 0 and drop out automatically. The tf part still grows without limit and ignores document length; BM25 fixes both.
tf(i, D) counted in this document only idf(i) = log N / (1 + nᵢ) same value for every document × term weight high: frequent here, rare elsewhere
Where the statistics come from: tf is a per-document count, idf a per-collection statistic, and their product is the tf-idf weight of the term in that document.

Worked example 7Why TF-IDF fixes TF's blind spot

Illustrative values: collection of N = 10,000 documents; query “the jaguar”. Document D contains “the” 10 times and “jaguar” 3 times. Log base 10.

Termtf(i, D)nᵢidf=log⁡10N1+ni\mathrm{idf} = \log_{10}\frac{N}{1+n_i}tf × idf
the108,000log⁡10100008001≈0.097\log_{10}\frac{10000}{8001} \approx 0.097≈ 0.97
jaguar350log⁡101000051≈2.292\log_{10}\frac{10000}{51} \approx 2.292≈ 6.88
1
Under raw TF, “the” contributes 10 points and “jaguar” only 3, so the stopword dominates.
2
Under TF-IDF, the contribution of “the” collapses to about 0.97 while “jaguar” contributes about 6.88.
score(D)≈0.97+6.88=7.85 \mathrm{score}(D) \approx 0.97 + 6.88 = 7.85
ResultThe discriminative term now dominates the score, as it should. Any log base can be used: changing the base rescales all scores by the same factor and leaves the ranking unchanged.
PracticeIn a collection of N = 1,000,000 documents, compute the idf (base 10) of a term found in 9 documents and of a term found in 99,999 documents.
Answer log⁡101,000,00010=log⁡10(100,000)=5log⁡101,000,000100,000=log⁡10(10)=1 \begin{aligned} \log_{10}\frac{1{,}000{,}000}{10} &= \log_{10}(100{,}000) = \mathbf{5} \\ \log_{10}\frac{1{,}000{,}000}{100{,}000} &= \log_{10}(10) = \mathbf{1} \end{aligned} The second term is about 11,000 times more common, yet its weight is only 5 times smaller: the log compresses the scale.
PracticeCompute idf(jaguar) and idf(a) (base 10) in the three-document jaguar collection. What do you notice?
jaguar is in all 3 documents; a is in d1 and d3.
Answer idf(jaguar)=log⁡1034≈−0.125idf(a)=log⁡1033=0 \begin{aligned} \mathrm{idf}(\text{jaguar}) &= \log_{10}\frac{3}{4} \approx \mathbf{-0.125} \\ \mathrm{idf}(\text{a}) &= \log_{10}\frac{3}{3} = \mathbf{0} \end{aligned} Because of the +1, a term found in every document gets a slightly negative weight. In a tiny collection this is visible; in a realistic collection it only affects terms present in almost every document, which carry no ranking signal anyway.

9. The vector space model

Sources: slides 34–38 · Video 7 (VSM)

The vector space model (VSM) often relies on TF-IDF to compute its term weights. As the name suggests, documents and queries are represented by vectors:

score(D,Q)=cos⁡(D,Q)=∑j=1tdj qj∑j=1tdj2⋅∑j=1tqj2 \mathrm{score}(D,Q) = \cos(D,Q) = \frac{\displaystyle\sum_{j=1}^{t} d_j \, q_j}{\sqrt{\displaystyle\sum_{j=1}^{t} d_j^2 \cdot \sum_{j=1}^{t} q_j^2}}
Where
tt
number of terms in the vocabulary (the number of dimensions)
jj
index of a vocabulary term
djd_j
weight of term jj in document DD (for example its tf-idf)
qjq_j
weight of term jj in query QQ
∑jdjqj\sum_j d_j q_j
the dot product of the two vectors
∑jdj2, ∑jqj2\sqrt{\sum_j d_j^2},\ \sqrt{\sum_j q_j^2}
the lengths (norms) of the document and query vectors
Read it aloud The score of D for Q is the cosine of the angle between them: the sum over all terms j of d-j times q-j, divided by the square root of the sum of the squared document weights times the sum of the squared query weights.
Formula in plain words The numerator multiplies the document weight and the query weight for every term and adds the products, so it grows when the two vectors put weight on the same terms. The denominator divides by the lengths of both vectors, which removes the effect of sheer size: doubling every weight in a document leaves its cosine unchanged, so a long document gains nothing just by being long. What remains is the angle between the vectors: the smaller the angle, the larger the cosine and the higher the rank. Terms with weight 0 in either vector contribute nothing to the numerator, so only shared terms need to be visited.
cos(D, Q)Meaning
1Vectors point in the same direction
0Nothing in common (geometrically: perpendicular)
−1Same components, opposite direction

If vector weights are always positive, as with TF-IDF, the cosine can only lie between 0 and 1. Once the cosine is computed for all documents, they are ranked by decreasing similarity to the query.

Term 3 Term 2 Term 1 Doc1 Doc2 Query θ₁ θ₂
Documents and the query live in the same term space. A smaller angle means a larger cosine: here θ₂ < θ₁, so Doc2 ranks above Doc1.

Worked example 8Cosine similarity from the lecture

Weighted vectors over three terms: D1=(0.5, 0.8, 0.3)D_1 = (0.5,\ 0.8,\ 0.3), D2=(0.9, 0.4, 0.2)D_2 = (0.9,\ 0.4,\ 0.2), Q=(1.5, 1.0, 0)Q = (1.5,\ 1.0,\ 0).

1
Score D1:
cos⁡(D1,Q)=(0.5×1.5)+(0.8×1.0)+(0.3×0)(0.52+0.82+0.32)(1.52+1.02)=1.550.98×3.25≈0.87 \cos(D_1,Q) = \frac{(0.5\times1.5)+(0.8\times1.0)+(0.3\times0)}{\sqrt{(0.5^2+0.8^2+0.3^2)(1.5^2+1.0^2)}} = \frac{1.55}{\sqrt{0.98\times3.25}} \approx 0.87
2
Score D2:
cos⁡(D2,Q)=(0.9×1.5)+(0.4×1.0)+(0.2×0)(0.92+0.42+0.22)(1.52+1.02)=1.751.01×3.25≈0.97 \cos(D_2,Q) = \frac{(0.9\times1.5)+(0.4\times1.0)+(0.2\times0)}{\sqrt{(0.9^2+0.4^2+0.2^2)(1.5^2+1.0^2)}} = \frac{1.75}{\sqrt{1.01\times3.25}} \approx 0.97
3
Rank by decreasing cosine. The third term has query weight 0, so it contributes nothing to either numerator; any term with weight 0 in the query or the document can be skipped in the sums over products, which is what makes VSM efficient over sparse vectors.
ResultD2 (0.97) ≻ D1 (0.87).
AdvantagesDisadvantages
Simple computational framework for ranking, which can be implemented efficiently thanks to the sparse nature of term occurrences.Assumes terms are independent: it ignores the order in which terms appear in documents (like TF and IDF, and like the other models this week).
Any similarity measure and any weighting scheme can be used: TF-IDF (the most common), TF only, IDF only, even BM25 weights.
PracticeCompute cos(D, Q) for D = (1, 0, 2) and Q = (0, 1, 1). Why can the cosine never be negative when weights come from TF-IDF?
Answer Dot product=1⋅0+0⋅1+2⋅1=2∣D∣2=1+0+4=5∣Q∣2=0+1+1=2cos⁡=25×2=210≈0.63 \begin{aligned} \text{Dot product} &= 1\cdot0 + 0\cdot1 + 2\cdot1 = 2 \\ |D|^2 &= 1 + 0 + 4 = 5 \\ |Q|^2 &= 0 + 1 + 1 = 2 \\ \cos &= \frac{2}{\sqrt{5 \times 2}} = \frac{2}{\sqrt{10}} \approx \mathbf{0.63} \end{aligned} With TF-IDF every weight is zero or positive (away from the tiny-collection edge case of Section 8), so every product in the numerator is at least zero and the cosine stays between 0 and 1.

10. Probabilistic models and the probability ranking principle

Sources: slides 39–43 · Video 8 (Probabilistic models, BIM) 00:00–05:57

10.1 Retrieval as classification

Probabilistic retrieval models view retrieval as a classification problem: documents are divided into two classes, Relevant (R) and Non-Relevant (NR).

Document D “The rain in Spain …” Relevant (R) Non-relevant (NR) P(R | D) P(NR | D)
Retrieve D if the probability that it belongs to the relevant class exceeds the probability that it belongs to the non-relevant class.

10.2 The decision rule and Bayes' rule

Decision rule: retrieve document D if

P(R∣D)>P(NR∣D) P(R \mid D) > P(NR \mid D)
Where
DD
the document (its representation)
R, NRR,\ NR
the classes “relevant” and “non-relevant” (to the current query)
P(R∣D)P(R \mid D)
probability that D is relevant, given what D contains
P(NR∣D)P(NR \mid D)
probability that D is non-relevant, given what D contains
Read it aloud Retrieve D if the probability of relevance given D is greater than the probability of non-relevance given D.
Formula in plain words This is a two-class classifier: put D in whichever class is more probable. Since the two probabilities add up to 1, the rule is the same as “retrieve D if P(R | D) > 0.5”. Neither probability can be read off directly, which is why the next step rewrites them with Bayes' rule.

Recall Bayes' rule, which rewrites a conditional probability:

P(R∣D)=P(D∣R) P(R)P(D) P(R \mid D) = \frac{P(D \mid R)\,P(R)}{P(D)}
Where
P(D∣R)P(D \mid R)
probability of seeing a document like D among the relevant documents
P(R)P(R)
prior probability of relevance (before looking at D)
P(D)P(D)
prior probability of the document D
Read it aloud The probability of R given D equals the probability of D given R, times the probability of R, divided by the probability of D.
Formula in plain words Bayes' rule turns a question we cannot answer directly (“is this document relevant?”) into one we can estimate from examples (“how likely is a relevant document to look like this?”). The prior P(R)P(R) scales the answer by how common relevance is overall, and dividing by P(D)P(D) normalises it. The same rewrite applies to P(NR∣D)P(NR \mid D).

Applying Bayes' rule to both sides of the decision rule and rearranging (the P(D)P(D) terms cancel) gives: retrieve D if

P(D∣R)P(D∣NR)⏟likelihood ratio  >  P(NR)P(R) \underbrace{\frac{P(D \mid R)}{P(D \mid NR)}}_{\text{likelihood ratio}} \;>\; \frac{P(NR)}{P(R)}
Where
P(D∣R), P(D∣NR)P(D \mid R),\ P(D \mid NR)
probability of a document like D within the relevant set and within the non-relevant set
P(R), P(NR)P(R),\ P(NR)
prior probabilities of relevance and non-relevance
Read it aloud Retrieve D if the likelihood ratio, P of D given R over P of D given NR, is greater than P of NR over P of R.
Formula in plain words The left side, the likelihood ratio, asks how much more typical D is of relevant documents than of non-relevant ones; it is the only part that depends on the document. The right side is a fixed threshold set by the priors: when relevant documents are rare (small P(R)P(R)), the threshold is high and a document must look strongly “relevant-like” to be retrieved. For ranking, only the likelihood ratio matters: sorting documents by it gives the order.

Worked example 9Applying the decision rule

Illustrative values: P(D∣R)=0.02P(D \mid R) = 0.02, P(D∣NR)=0.004P(D \mid NR) = 0.004, and P(R)=0.1P(R) = 0.1, so P(NR)=0.9P(NR) = 0.9.

1
Likelihood ratio: 0.020.004=5 \frac{0.02}{0.004} = 5
2
Threshold: P(NR)P(R)=0.90.1=9 \frac{P(NR)}{P(R)} = \frac{0.9}{0.1} = 9
3
Cross-check with the unnormalised posteriors: P(D∣R)P(R)=0.002P(D∣NR)P(NR)=0.0036 \begin{aligned} P(D \mid R)P(R) &= 0.002 \\ P(D \mid NR)P(NR) &= 0.0036 \end{aligned}
5<9⟺0.002<0.0036 5 < 9 \quad\Longleftrightarrow\quad 0.002 < 0.0036
ResultD is five times more typical of relevant documents, yet relevance is so rare that D is still more likely non-relevant: the rule says do not retrieve. In a ranking, D would still be placed above any document with a smaller likelihood ratio.

10.3 The probability ranking principle (PRP)

“If a reference retrieval system's response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.” (Robertson, 1977)

The PRP has been mathematically proven to give the best possible ranking, but only under assumptions:

  1. Probabilities are estimated as accurately as possible. If the estimates fail to resemble reality, the ranking has room for error.
  2. Independent document relevance (implicit): the relevance of one document is unrelated to the relevance of any other. The user is assumed to examine documents in isolation, forgetting anything learned during the search. For example, the PRP would happily rank several copies of the same document one after another, even though the user gains nothing from the copies. This assumption often fails in reality.

Alternative principles exist for when the assumptions fail: iPRP (Fuhr, 2008) for interactive IR, and qPRP (Zuccon, Azzopardi and van Rijsbergen, 2009) for dependent document relevance. “Overall effectiveness” here means the evaluation measures of Week 2.

10.4 The core problem: estimating P(D | R)

Estimation boils down to P(D∣R)P(D \mid R), because P(R)P(R) and P(NR)P(NR) are constant across all documents and can be ignored for ranking, and P(D∣NR)P(D \mid NR) is handled through the complement (the lecture relates it to 1−P(D∣R)1 - P(D \mid R)). So we can rank documents by decreasing P(D∣R)P(D \mid R). Step 1, common to most models, assumes that terms occur independently of one another:

P(D∣R)=∏i=1tP(di∣R) P(D \mid R) = \prod_{i=1}^{t} P(d_i \mid R)
Where
tt
number of terms in the vocabulary
did_i
the feature of document DD for term ii (in the BIM: 1 if present, 0 if absent)
P(di∣R)P(d_i \mid R)
probability of that feature value among relevant documents
∏\prod
product over all terms
Read it aloud The probability of D given R is the product, over every term i from one to t, of the probability of d-i given R.
Formula in plain words Independence lets one hard probability (of a whole document) be built from many easy ones (of single terms): multiply the per-term probabilities. The price is that word order and co-occurrence are ignored, the same simplification as TF and VSM. The open question becomes how to estimate each P(di∣R)P(d_i \mid R); probabilistic models differ exactly in how they do this, starting with the Binary Independence Model.
1 Decision rule retrieve D if P(R | D) > P(NR | D) 2 Bayes' rule on both sides likelihood ratio P(D | R) / P(D | NR) > P(NR) / P(R) 3 Drop what is the same for every document priors are constant: rank by P(D | R) 4 Assume term independence P(D | R) = product over terms of P(dᵢ | R) 5 Estimate P(dᵢ | R) binary features: BIM (Section 11); add tf and length: BM25 (Section 12)
The probabilistic line of reasoning: from a classification decision to a per-term estimation problem, which the BIM and BM25 then solve.
PracticeState the two assumptions behind the PRP's optimality and give a search result list that satisfies the PRP but serves the user badly.
Answer(1) Probabilities of relevance are estimated as accurately as possible; (2) each document's relevance is independent of the others. A list whose top five results are five copies (or near-duplicates) of the same relevant page satisfies the PRP, since each copy has the same high probability of relevance, yet after the first copy the user learns nothing new. qPRP was proposed for exactly this kind of dependence.

11. The Binary Independence Model

Sources: slides 44–49 · Video 8 (Probabilistic models, BIM) 05:24–11:37

Step 2 is to estimate P(di∣R)P(d_i \mid R). The BIM's setup:

term i in document D? Relevant (R) Non-relevant (NR) present: dᵢ = 1 pᵢ occurs in a relevant doc sᵢ occurs in a non-relevant doc absent: dᵢ = 0 1 − pᵢ missing in a relevant doc 1 − sᵢ missing in a non-relevant doc each column adds up to 1; the BIM needs pᵢ and sᵢ for every term
The four probabilities the BIM works with for each term: presence or absence, in relevant or non-relevant documents.

11.1 The likelihood ratio under the BIM

With independence and binary features, the likelihood ratio becomes a product over the terms present in the document times a product over the terms absent from it:

P(D∣R)P(D∣NR)=∏i: di=1pisi  ⋅  ∏i: di=01−pi1−si \frac{P(D \mid R)}{P(D \mid NR)} = \prod_{i:\,d_i=1} \frac{p_i}{s_i} \;\cdot\; \prod_{i:\,d_i=0} \frac{1-p_i}{1-s_i}
Where
i: di=1i:\,d_i=1
all terms present in DD
i: di=0i:\,d_i=0
all vocabulary terms absent from DD
pi, sip_i,\ s_i
probability that term ii occurs in a relevant, and in a non-relevant, document
1−pi, 1−si1-p_i,\ 1-s_i
probability that term ii is absent from a relevant, and from a non-relevant, document
Read it aloud The likelihood ratio equals the product, over terms present in D, of p-i over s-i, times the product, over terms absent from D, of one minus p-i over one minus s-i.
Formula in plain words Every term in the vocabulary casts a vote. A present term multiplies the ratio by pi/sip_i/s_i: above 1 when the term is more common in relevant documents, pushing the document up. An absent term multiplies by (1−pi)/(1−si)(1-p_i)/(1-s_i), the matching vote for absence. The document's overall ratio is the product of all these votes, which is why independence was needed.

Worked example 10From the likelihood ratio to the BIM score

A derivation in three moves (slides 45–48), starting from the product above.

1
Insert a factor equal to 1. Multiply the first product by ∏i:di=11−si1−pi⋅∏i:di=11−pi1−si\prod_{i:d_i=1}\frac{1-s_i}{1-p_i}\cdot\prod_{i:d_i=1}\frac{1-p_i}{1-s_i}; the two cancel, so nothing changes:
=∏i:di=1pisi⋅(∏i:di=11−si1−pi⋅∏i:di=11−pi1−si)⋅∏i:di=01−pi1−si = \prod_{i:d_i=1}\frac{p_i}{s_i}\cdot\Big(\prod_{i:d_i=1}\frac{1-s_i}{1-p_i}\cdot\prod_{i:d_i=1}\frac{1-p_i}{1-s_i}\Big)\cdot\prod_{i:d_i=0}\frac{1-p_i}{1-s_i}
2
Regroup. The first two products run over the same terms, so they combine. The last factor in the bracket and the di=0d_i = 0 product together cover all terms:
=∏i:di=1pi(1−si)si(1−pi)⏟depends on D  ⋅  ∏i1−pi1−si⏟over all terms = \underbrace{\prod_{i:d_i=1}\frac{p_i(1-s_i)}{s_i(1-p_i)}}_{\text{depends on } D}\;\cdot\;\underbrace{\prod_{i}\frac{1-p_i}{1-s_i}}_{\text{over all terms}}
3
Drop the constant and take logs. The second product covers every term in the collection, so it is identical for every document and can be ignored for ranking. The remaining product multiplies probabilities (numbers in [0, 1]), and the result quickly becomes tiny (for example 0.1×0.1=0.010.1 \times 0.1 = 0.01); computers cannot represent very small decimals accurately (floating-point underflow). Taking logs turns the product into a sum.
ResultThe BIM scoring function: score(D)=∑i:di=1log⁡pi(1−si)si(1−pi)\mathrm{score}(D) = \sum_{i:d_i=1}\log\frac{p_i(1-s_i)}{s_i(1-p_i)}, derived in full below.

11.2 The BIM scoring function

score(D)=∑i: di=1log⁡pi (1−si)si (1−pi) \mathrm{score}(D) = \sum_{i:\,d_i=1} \log \frac{p_i\,(1-s_i)}{s_i\,(1-p_i)}
Where
i: di=1i:\,d_i=1
terms present in document DD
pip_i
probability that term ii occurs in a relevant document
sis_i
probability that term ii occurs in a non-relevant document
pi1−pi, si1−si\frac{p_i}{1-p_i},\ \frac{s_i}{1-s_i}
the odds of the term occurring in the relevant and in the non-relevant set; the fraction is their ratio
Read it aloud The score of D is the sum, over terms present in D, of the log of p-i times one minus s-i, divided by s-i times one minus p-i.
Formula in plain words Each present term adds a weight: the log of (its odds in relevant documents) divided by (its odds in non-relevant documents). A term that is much more likely in relevant documents adds a large positive weight; a term equally likely in both adds log 1 = 0; a term more typical of non-relevant documents subtracts. Absent terms add nothing, and there is no term frequency: presence counts once.

11.3 Making it computable

score(D)=∑i ∈ Q∩Dlog⁡N−nini \mathrm{score}(D) = \sum_{i \,\in\, Q \cap D} \log \frac{N - n_i}{n_i}
Where
i∈Q∩Di \in Q \cap D
terms that appear in both the query and the document
NN
total number of documents in the collection
nin_i
number of documents containing term ii
Read it aloud The score of D is the sum, over terms in both the query and the document, of the log of N minus n-i over n-i.
Formula in plain words Substituting pi=0.5p_i = 0.5 and si=ni/Ns_i = n_i/N into the BIM weight leaves log⁡1−ni/Nni/N=log⁡N−nini\log\frac{1-n_i/N}{n_i/N} = \log\frac{N-n_i}{n_i}: the number of documents without the term divided by the number with it. Rare terms get large weights and common terms small ones, exactly the IDF behaviour, and a term in more than half the collection gets a negative weight. Each matched term counts once, however often it occurs.

Worked example 11BIM term weights for president and lincoln

Collection of N = 500,000 documents (the collection used in the BM25 example of Section 12); natural log.

1
lincoln appears in ni=300n_i = 300 documents:
wlincoln=ln⁡500,000−300300=ln⁡(1665.7)≈7.42 w_{\text{lincoln}} = \ln\frac{500{,}000-300}{300} = \ln(1665.7) \approx 7.42
2
president appears in ni=40,000n_i = 40{,}000 documents:
wpresident=ln⁡460,00040,000=ln⁡(11.5)≈2.44 w_{\text{president}} = \ln\frac{460{,}000}{40{,}000} = \ln(11.5) \approx 2.44
ResultThe rare, discriminative term gets a weight about three times larger (7.42 against 2.44): exactly the IDF behaviour.
Takeaways
PracticeUnder the simplified BIM (pi=0.5p_i = 0.5, si=ni/Ns_i = n_i/N), what weight does a term receive if it appears in exactly half of the collection? In more than half?
AnswerWith ni=N2n_i = \frac{N}{2}: log⁡N−N2N2=log⁡1=0 \log\frac{N - \frac{N}{2}}{\frac{N}{2}} = \log 1 = 0 So matching it changes nothing. With ni>N2n_i > \frac{N}{2}, the fraction drops below 1 and the weight becomes negative: matching a very common term lowers the score slightly. The 0.5 smoothing in BM25's RSJ weight behaves the same way.

12. BM25

Sources: slides 50–59 · Video 9 (BM25)

BM25 is a popular and effective probabilistic ranking model based on the Binary Independence Model (the derivation from BIM to BM25 is in the Croft, Metzler and Strohman textbook). It expands the tf-idf idea, in its most general form without relevance information, with two main differences:

  1. Term-frequency saturation
  2. Document length normalisation

A third difference: in its most general form BM25 can also incorporate prior relevance information (judged documents), although this is rarely available. BM25 has been shown empirically to be a reliable and robust model that works well out of the box in most situations. It is the default ranking model in many open-source search libraries (Lucene, Elasticsearch, and therefore Pyserini in the pracs) and is one of the key features used by web search engines.

12.1 The full formula

BM25(D,Q)=∑i=1∣Q∣log⁡ ⁣((ri+0.5)/(R−ri+0.5)(ni−ri+0.5)/(N−ni−R+ri+0.5))⏟1. RSJ weight⋅(k1+1) fik1B+fi⏟2. saturation⋅(k2+1) qfik2+qfi⏟3. within-query \mathrm{BM25}(D,Q) = \sum_{i=1}^{|Q|} \underbrace{\log\!\left(\frac{(r_i+0.5)/(R-r_i+0.5)}{(n_i-r_i+0.5)/(N-n_i-R+r_i+0.5)}\right)}_{\text{1. RSJ weight}} \cdot \underbrace{\frac{(k_1+1)\,f_i}{k_1 B + f_i}}_{\text{2. saturation}} \cdot \underbrace{\frac{(k_2+1)\,qf_i}{k_2+qf_i}}_{\text{3. within-query}} B=(1−b)+b⋅dlavdl B = (1-b) + b\cdot\frac{dl}{avdl}
Where
∣Q∣|Q|, ii
number of query terms, and the index of a query term
RR
number of documents judged relevant
rir_i
number of judged-relevant documents that contain term ii
N, niN,\ n_i
number of judged documents, and judged documents containing term ii; with no judgements, the collection size and the document frequency
0.50.5
smoothing constant that keeps every count positive
fif_i
frequency of term ii in the document
qfiqf_i
frequency of term ii in the query
k1k_1
term-frequency saturation parameter, k1>0k_1 > 0 (typically 1.2)
k2k_2
within-query saturation parameter (sometimes written k3k_3)
BB
document length normalisation factor
bb
length-normalisation parameter, 0≤b≤10 \le b \le 1 (typically 0.75)
dl, avdldl,\ avdl
length of the document, and average document length in the collection
Read it aloud The BM25 score of D for Q is the sum, over the query terms i, of three factors multiplied together: the Robertson–Spärck Jones weight of term i; k-one plus one times f-i, over k-one times B plus f-i; and k-two plus one times q-f-i, over k-two plus q-f-i. B equals one minus b, plus b times the document length over the average document length.
Formula in plain words For each query term, BM25 multiplies three things. The RSJ weight says how strongly the term signals relevance (without judgements, how rare it is: an IDF). The saturation factor turns the raw count fif_i into a bounded value: the first occurrence adds the most, later ones add less and less, and the value can never exceed k1+1k_1 + 1. Inside it, BB inflates the denominator for longer-than-average documents, so the same count is worth less in a long document. The within-query factor does the same saturation for terms repeated in the query, and equals 1 for ordinary short queries. Raising k1k_1 lets repeated occurrences keep adding score; raising bb punishes long documents more.
BM25(D, Q) = Σ over query terms i of 1. RSJ weight how rare term i is ≈ idf with no relevance judgements × 2. TF saturation (k₁ + 1) fᵢ / (k₁B + fᵢ) k₁ sets how fast repeats level off × 3. Within-query (k₂ + 1) qfᵢ / (k₂ + qfᵢ) equals 1 when qfᵢ = 1 B scales k₁ in the denominator Length normalisation B B = (1 − b) + b · dl / avdl b = 0: off · b = 1: full
BM25's anatomy: three factors per query term, multiplied and then summed over the query. Length normalisation acts through the saturation factor.
ParameterControlsTypical valueSmall valueLarge value
k1k_1Term-frequency saturation1.2Saturates almost at once; near k1=0k_1 = 0, presence alone counts (binary, like the BIM)Repeats keep adding; as k1→∞k_1 \to \infty the factor approaches raw tf
bbDocument length normalisation0.75b=0b = 0: length ignored (B=1B = 1)b=1b = 1: full normalisation (B=dl/avdlB = dl/avdl)
k2k_2Within-query saturationoften large (Croft's example uses 100)Repeated query terms saturate quicklyFactor approaches raw qfiqf_i

12.2 Component 1: the Robertson–Spärck Jones (RSJ) weight

The RSJ weight uses knowledge about relevance: the number of relevant documents RR and the number of relevant documents containing term ii, rir_i. The top of the ratio is the smoothed ratio of relevant documents that contain the term to relevant documents that lack it; the bottom is the same ratio among the judged non-relevant documents. NN and nin_i refer to the documents that were judged to obtain RR and rir_i. The 0.5 terms are smoothing factors. If no relevance information is available (R=ri=0R = r_i = 0), and NN, nin_i become the collection size and document frequency, the weight simplifies to:

wiRSJ=log⁡N−ni+0.5ni+0.5 w_i^{\mathrm{RSJ}} = \log \frac{N - n_i + 0.5}{n_i + 0.5}
Where
wiRSJw_i^{\mathrm{RSJ}}
the RSJ weight of query term ii with no relevance information
NN
number of documents in the collection
nin_i
number of documents containing term ii
0.50.5
smoothing that avoids division by zero and log of zero
Read it aloud The RSJ weight of term i is the log of N minus n-i plus a half, over n-i plus a half.
Formula in plain words This is the simplified BIM weight of Section 11 with 0.5 added to both counts: documents without the term over documents with it. It is an approximation of the classical IDF. The rarer the term, the larger the weight; a term in more than half the collection gets a negative weight. When relevance judgements do exist, the full form raises the weight of terms that occur often in the judged-relevant documents.

12.3 Component 2: term-frequency saturation

The contribution of a term's occurrences to the document score cannot exceed a saturation point. The parameter k1k_1 controls this:

sat(fi)=(k1+1) fik1B+fi \mathrm{sat}(f_i) = \frac{(k_1+1)\,f_i}{k_1 B + f_i}
Where
fif_i
frequency of term ii in the document
k1k_1
saturation parameter, k1>0k_1 > 0, typically 1.2
BB
length normalisation factor (equal to 1 for a document of average length)
k1+1k_1 + 1
scaling that makes the factor equal 1 when fi=1f_i = 1 and B=1B = 1; it is also the upper bound
Read it aloud The saturated frequency of term i is k-one plus one, times f-i, divided by k-one times B plus f-i.
Formula in plain words As fif_i grows, the fif_i in the denominator catches up with the one in the numerator, so the value climbs quickly at first and then levels off towards k1+1k_1 + 1. High k1k_1: saturation happens only at high frequencies, so fif_i keeps contributing significantly. Low k1k_1: additional occurrences tail off very quickly; at k1=0k_1 = 0 the factor is 1 for any fi>0f_i > 0, which is the BIM's binary view. A typical setting is k1=1.2k_1 = 1.2, giving a ceiling of 2.2.
0.2 0.4 0.6 0.8 1.0 0 2 4 6 8 10 k₁ = 0.2 k₁ = 1 k₁ = 3 k₁ = 10 term frequency fᵢ fᵢ / (k₁ + fᵢ)
Normalised saturation fi/(k1+fi)f_i/(k_1+f_i) (the saturation factor divided by its ceiling k1+1k_1 + 1, for a document of average length) against term frequency, for four values of k1k_1. Small k1k_1: the curve flattens almost immediately. Large k1k_1: repeated occurrences keep adding to the score.

12.4 Component 3: document length normalisation

BB provides a soft normalisation of document length and is used to normalise the term frequency fif_i inside the saturation factor:

B=(1−b)+b⋅dlavdl,0≤b≤1 B = (1-b) + b\cdot\frac{dl}{avdl}, \qquad 0 \le b \le 1
Where
BB
length normalisation factor, multiplied by k1k_1 in the saturation denominator
bb
parameter controlling how much length matters, typically 0.75
dldl
length of the document being scored
avdlavdl
average document length in the collection
Read it aloud B equals one minus b, plus b times the document length divided by the average document length.
Formula in plain words BB is a blend of 1 (ignore length) and dl/avdldl/avdl (full relative length), with bb as the mixing weight. A document of exactly average length always gets B=1B = 1. A longer document gets B>1B > 1, which enlarges the saturation denominator, so each occurrence is worth less; a shorter one gets B<1B < 1 and each occurrence is worth more. b = 1: full normalisation; b = 0: no normalisation; typical b = 0.75. Why care about length? An author writes a longer or shorter document than average for a reason: verbosity (padding, so prefer shorter documents) or scope (a user writing an essay wants breadth and detail, so prefer longer documents). The parameter bb lets the system lean either way.
0.5 1.0 1.5 2.0 0 2 4 6 8 10 upper bound k₁ + 1 = 2.2 dl = 0.1 × avdl (short) dl = avdl dl = 10 × avdl (long) term frequency fᵢ (k₁ + 1) fᵢ / (k₁B + fᵢ)
The full saturation factor (k₁ = 1.2, b = 0.75) for documents shorter than, equal to, and longer than average. Repeated occurrences in long documents are discounted the most.

12.5 Component 4: the within-query factor

qsat(qfi)=(k2+1) qfik2+qfi \mathrm{qsat}(qf_i) = \frac{(k_2+1)\,qf_i}{k_2 + qf_i}
Where
qfiqf_i
number of times term ii occurs in the query
k2k_2
within-query saturation constant (called k3k_3 by some authors)
Read it aloud The within-query factor is k-two plus one, times q-f-i, divided by k-two plus q-f-i.
Formula in plain words It weights query terms by how often they appear in the query, with the same saturating shape as the document factor, and it is useful only for longer queries where a term may repeat. For a term that appears once (qfi=1qf_i = 1) the factor is exactly 1 whatever k2k_2 is, so short queries are unaffected. Larger k2k_2 lets repeated query terms count almost linearly; smaller k2k_2 saturates them quickly. Experiments suggest this component is not important: in practice, multiple occurrences of a term in a query are often simply treated as different terms.

12.6 Worked examples

Worked example 12The effect of term frequency in BM25 (from the lecture)

Setup (slides 54–56): query “president lincoln”; every document has length dl=0.9×avdldl = 0.9 \times avdl; N=500,000N = 500{,}000; “president” occurs in n1=40,000n_1 = 40{,}000 documents (common) and “lincoln” in n2=300n_2 = 300 (discriminative); no relevance information; k1=1.2k_1 = 1.2, b=0.75b = 0.75; short query, so the within-query factor is 1. Natural log.

1
Length normalisation (the same for every document here):
B=(1−0.75)+0.75×0.9=0.25+0.675=0.925k1B=1.2×0.925=1.11 \begin{aligned} B &= (1-0.75) + 0.75\times0.9 = 0.25 + 0.675 = 0.925 \\ k_1 B &= 1.2\times0.925 = 1.11 \end{aligned}
2
RSJ weights (IDF-like):
wpresident=ln⁡500000−40000+0.540000+0.5=ln⁡(11.50)≈2.44wlincoln=ln⁡500000−300+0.5300+0.5=ln⁡(1663)≈7.42 \begin{aligned} w_{\text{president}} &= \ln\frac{500000-40000+0.5}{40000+0.5} = \ln(11.50) \approx 2.44 \\ w_{\text{lincoln}} &= \ln\frac{500000-300+0.5}{300+0.5} = \ln(1663) \approx 7.42 \end{aligned}
3
Score one document fully with fpresident=15f_{\text{president}} = 15 and flincoln=25f_{\text{lincoln}} = 25:
score(D)=2.44⋅2.2×151.11+15+7.42⋅2.2×251.11+25=2.44⋅2.048+7.42⋅2.107≈5.00+15.63=20.6 \begin{aligned} \mathrm{score}(D) &= 2.44\cdot\frac{2.2\times15}{1.11+15} + 7.42\cdot\frac{2.2\times25}{1.11+25} \\ &= 2.44\cdot 2.048 + 7.42\cdot 2.107 \\ &\approx 5.00 + 15.63 \\ &= 20.6 \end{aligned}
4
The full table (each row is a different document):
f(“president”)f(“lincoln”)BM25 score
152520.66
15112.74
1505.00
12518.2
02515.66
ResultScores as reported in the lecture. Recomputing with the values above gives 20.63, 12.74, 5.00, 18.17 and 15.62, identical up to rounding of the intermediate weights.
Exam angleThree questions from the lecture about this table:

Worked example 13How k₁ and b move the saturation factor

Illustrative values, looking only at the saturation factor (k1+1)fk1B+f\frac{(k_1+1)f}{k_1B+f}.

1
Vary k1k_1 for an average-length document (B=1B = 1). With f=1f = 1 the factor is k1+1k1+1=1\frac{k_1+1}{k_1+1} = 1 for every k1k_1. With f=10f = 10: k1=0.2:factor=1210.2=1.18k1=1.2:factor=2211.2=1.96k1=3:factor=4013=3.08 \begin{aligned} k_1 = 0.2\text{:}\quad \text{factor} &= \frac{12}{10.2} = 1.18 \\ k_1 = 1.2\text{:}\quad \text{factor} &= \frac{22}{11.2} = 1.96 \\ k_1 = 3\text{:}\quad \text{factor} &= \frac{40}{13} = 3.08 \end{aligned}
2
Vary bb for f=3f = 3, k1=1.2k_1 = 1.2 and a long document (dl=2×avdldl = 2 \times avdl): b=0:B=1,factor=6.64.2=1.57b=0.75:B=1.75,factor=6.62.1+3=1.29b=1:B=2,factor=6.62.4+3=1.22 \begin{aligned} b = 0\text{:}\quad B = 1,\quad \text{factor} &= \frac{6.6}{4.2} = 1.57 \\ b = 0.75\text{:}\quad B = 1.75,\quad \text{factor} &= \frac{6.6}{2.1 + 3} = 1.29 \\ b = 1\text{:}\quad B = 2,\quad \text{factor} &= \frac{6.6}{2.4 + 3} = 1.22 \end{aligned}
3
Short document (dl=0.5×avdldl = 0.5 \times avdl, b=0.75b = 0.75): B=0.625,factor=6.60.75+3=1.76 B = 0.625,\quad \text{factor} = \frac{6.6}{0.75 + 3} = 1.76
Resultk1k_1 only decides how much the later occurrences add (ten occurrences are worth 1.18 to 3.08 first occurrences); bb decides how strongly the same count is discounted in long documents and boosted in short ones.
PracticeWhat does BM25 reduce to when k1=0k_1 = 0? And when b=0b = 0 and k1k_1 grows very large?
Look at the saturation factor in each limit; assume no relevance information and a short query.
AnswerWith k1=0k_1 = 0, the factor is fifi=1\frac{f_i}{f_i} = 1 for every matched term, so BM25 becomes the sum of RSJ weights over matched terms: the BIM with an IDF-like weight, no tf. With b=0b = 0 (B=1B = 1) and k1→∞k_1 \to \infty, (k1+1)fik1+fi→fi\frac{(k_1+1)f_i}{k_1+f_i} \to f_i, so BM25 approaches ∑tf×RSJ\sum tf \times \text{RSJ}: essentially TF-IDF, with unbounded tf and no length normalisation. The typical settings sit between these extremes.
PracticeTwo documents each contain “lincoln” 4 times; D_short has dl=0.5×avdldl = 0.5 \times avdl and D_long has dl=3×avdldl = 3 \times avdl. With k1=1.2k_1 = 1.2, which scores higher for “lincoln” at b=0.75b = 0.75, and what changes at b=0b = 0?
AnswerAt b=0.75b = 0.75: D_short:B=0.625,factor=8.80.75+4=1.85D_long:B=2.5,factor=8.83+4=1.26 \begin{aligned} \text{D\_short:}\quad B = 0.625,\quad \text{factor} &= \frac{8.8}{0.75 + 4} = 1.85 \\ \text{D\_long:}\quad B = 2.5,\quad \text{factor} &= \frac{8.8}{3 + 4} = 1.26 \end{aligned} D_short scores higher. At b=0b = 0, both have B=1B = 1 and the factor is 8.85.2=1.69\frac{8.8}{5.2} = 1.69 for both: length no longer matters, and they tie.

13. Summary and study checklist

ModelRepresentationScoring ideaRanking?Key limitation
BooleanBinary term presenceSatisfy the Boolean expression (set retrieval)No (set only)No partial matching, no ranking; expert-only queries
+ CLMBinaryRank satisfying documents by the number of clauses or terms matchedYesStill requires full Boolean satisfaction
TFTerm counts (bag of words)∑if(qi,D)\sum_i f(q_i,D)YesAll terms equally important; favours long documents
IDFCollection statistics∑ilog⁡N1+ni\sum_i \log\frac{N}{1+n_i}YesIgnores within-document frequency
TF-IDFWeighted counts∑itf(i,D)⋅idf(i)\sum_i tf(i,D)\cdot idf(i)YesNo saturation, no length normalisation
VSMVectors of term weightsCosine similarityYesTerm independence; ignores word order
BIMBinary features∑i∈Q∩Dlog⁡pi(1−si)si(1−pi)\sum_{i\in Q\cap D}\log\frac{p_i(1-s_i)}{s_i(1-p_i)}, which becomes an IDF-like weightYesNo term frequency
BM25Counts, lengths, optional relevance informationRSJ weight (≈ IDF) × saturated tf × query factorYesStill lexical: no semantics, term independence
TakeawaysEach model fixes the main weakness of the one before: Boolean (no ranking) → TF (adds frequency) → TF-IDF (adds term importance) → VSM (a general geometric ranking framework) → BIM (a principled probabilistic foundation, the PRP) → BM25 (adds tf saturation and document length normalisation to the probabilistic framework). All of them are term-based lexical models: cheap to encode (O(|d|)), cheap to score (O(1) per pair with an inverted index), and all assume term independence.
counting and vector models Boolean sets CLM + ranking TF + counts TF-IDF + term rarity VSM + cosine probabilistic models PRP rank by P(R | D) BIM binary, idf-like weight BM25 + saturation, length extends the tf-idf idea
The week's through-line: two families of term-based models that meet in BM25.

13.1 Formula reference card

ModelScoring function
TFscore(D,Q)=∑i=1∣Q∣f(qi,D)\mathrm{score}(D,Q)=\sum_{i=1}^{|Q|} f(q_i,D)
IDFscore(D,Q)=∑i=1∣Q∣log⁡N1+ni\mathrm{score}(D,Q)=\sum_{i=1}^{|Q|} \log\frac{N}{1+n_i}
TF-IDFscore(D,Q)=∑i=1∣Q∣tf(i,D)×idf(i)\mathrm{score}(D,Q)=\sum_{i=1}^{|Q|} tf(i,D)\times idf(i)
VSM (cosine)score(D,Q)=∑jdjqj∑jdj2⋅∑jqj2\mathrm{score}(D,Q)=\frac{\sum_j d_j q_j}{\sqrt{\sum_j d_j^2\cdot\sum_j q_j^2}}
BIMscore(D)=∑i:di=1log⁡pi(1−si)si(1−pi)\mathrm{score}(D)=\sum_{i:d_i=1}\log\frac{p_i(1-s_i)}{s_i(1-p_i)}, which with pi=0.5, si=ni/Np_i=0.5,\ s_i=n_i/N becomes ∑i∈Q∩Dlog⁡N−nini\sum_{i\in Q\cap D}\log\frac{N-n_i}{n_i}
BM25∑i=1∣Q∣log⁡((ri+0.5)/(R−ri+0.5)(ni−ri+0.5)/(N−ni−R+ri+0.5))⋅(k1+1)fik1B+fi⋅(k2+1)qfik2+qfi\sum_{i=1}^{|Q|}\log\big(\frac{(r_i+0.5)/(R-r_i+0.5)}{(n_i-r_i+0.5)/(N-n_i-R+r_i+0.5)}\big)\cdot\frac{(k_1+1)f_i}{k_1B+f_i}\cdot\frac{(k_2+1)qf_i}{k_2+qf_i}, with B=(1−b)+bdlavdlB=(1-b)+b\frac{dl}{avdl}

13.2 Study checklist

14. Video index

Playlist: IR Week 3.

VideoLengthCovered in
1. Overview of relevance model, retrieval vs. reranking4:22Sections 1–2
2. Term-based lexical retrieval models5:25Sections 1, 3
3. Boolean model5:37Sections 4–5
4. Boolean professional3:12Section 6
5. TF3:19Section 7
6. IDF, TF-IDF3:43Section 8
7. VSM3:42Section 9
8. Probabilistic models, BIM11:37Sections 10–11
9. BM259:03Section 12

15. References