Week 3: Retrieval Models I (Term-based Lexical Models)Lecture notes3
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.
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:
Page A: the Wikipedia article on the University of Queensland, which states that UQ is a public research university located primarily in Brisbane, Queensland. It answers the question directly, so it is highly relevant.
Page B: the Wikipedia article on Australia. It mentions Australia in general and gives the user nothing useful, so it is not relevant.
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:
An encoder converts the query and the document into representations: term vectors, embeddings, or other forms.
A scorer computes how well the two encoded representations match and outputs the relevance score.
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.
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.
Aspect
Retrieval model
Reranking model
Operates on
The entire document collection
Only the top-n results from the retriever (typically 10–1,000 documents)
Scores
Every document in the corpus
Only a selected list of documents
Speed requirement
Must be fast and scalable; uses approximations and heuristics
Can afford to be slower and much more sophisticated
Typical techniques
Inverted index plus lexical matching (for example BM25)
Deeper features and heavy machine-learning models (for example monoBERT)
Role
First stage: efficiently narrows down the candidates
Later 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.
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.
Representations are built from the raw query and document terms, using features such as term frequency or binary presence.
Scores are based on the terms the query and the document have in common.
Common lexical models
Techniques that can be applied
Boolean model · TF (term frequency) · TF-IDF · Vector space model (VSM) · Binary Independence Model (BIM) · BM25
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:
Each vector has length equal to the vocabulary size; each dimension corresponds to one unique term in the collection.
Most values are zero, because a typical document or query contains only a tiny subset of all possible terms.
The non-zero entries record the presence, frequency, or weighted importance of terms.
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)=1j=1∑∣V∣V(q)j∧V(d)j>0
Where
q,d
the query and the document being scored
V(q),V(d)
binary vectors of q and d over the vocabulary: entry j is 1 if term j is present, 0 otherwise
j,∣V∣
index of a vocabulary term (one vector dimension), and the vocabulary size (number of dimensions)
∧
logical AND: 1 only when both entries are 1
1[⋅]
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):
Text
Binary 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.
The query is a Boolean expression: terms combined with the operators AND, OR and NOT (sometimes more advanced operators too, for example proximity).
Only documents that satisfy the Boolean expression are retrieved.
There is no notion of frequency: a term is either present or absent. There are no scores either, so the output is a set of documents.
the set of documents that satisfy expression x (for a single term: the documents that contain it, read from its postings list)
∩
intersection: documents in both sets
∪
union: documents in either set
∖
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):
Term
d1
d2
d3
a
1
1
jaguar
1
1
1
is
1
1
an
1
animal
1
my
1
new
1
guitar
1
big
1
cat
1
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”
NOTremoves 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
Advantages
Disadvantages
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.
No partial matching: Boolean logic is stringent. A document either fully satisfies the query or is left out entirely.
No scoring and no ranking: the model cannot say how well a document fits; it retrieves an unordered set.
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).
Documents that have n different index terms in common with the query are more relevant than documents with n − 1 different terms in common.
The coordination level (“size of overlap”) between a query Q and a document D is the number of terms they have in common.
Applied to the Boolean model: rank by the number of Boolean clauses of Q that D satisfies.
CLM(Q,D)=c∈C(Q)∑1[D satisfies c]for every D that satisfies Q
Where
Q,D
the Boolean query and a document
C(Q)
the set of Boolean clauses that make up Q (for plain keyword queries: the query terms)
c
one clause (or term) of the query
1[⋅]
indicator: 1 if D satisfies clause c, 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.
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.
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.
Operator
Example
What it does
Grouping
or/1-6
Combines clauses 1–6 with OR (line 18 combines 7 AND 17).
Sub-grouping
( … )
Brackets group Boolean sub-expressions inside a clause.
Wildcard
antagonist*
Matches any string that starts with the given prefix.
Explicit stemming
block$
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.
Adjacency
adj3
The 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 heading
Propranolol/
Matches categorical metadata attached to documents. MeSH is a controlled (fixed) medical vocabulary whose terms are organised hierarchically.
MeSH explosion
exp …/
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.
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…”.
Term
d1
d2
d3
a
1
2
jaguar
1
1
1
is
1
1
an
1
animal
3
1
my
1
new
1
guitar
1
big
1
1
cat
1
7.1 Formal definition
score(D,Q)=i=1∑∣Q∣f(qi,D)
Where
D,Q
the document being scored and the query
∣Q∣
the size of the query (number of query terms)
qi
the i-th query term
f(qi,D)
term frequency: the number of times qi occurs in D
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.
Document
f(jaguar, d)
f(animal, d)
TF score
Rank
d1
1
3
4
1
d2
1
0
1
3
d3
1
1
2
2
score(d1)=f(jaguar,d1)+f(animal,d1)=1+3=4
ResultRanking: d1 (4) ≻ d3 (2) ≻ d2 (1).
TakeawaysTwo problems with TF motivate the rest of the week.
All words have the same importance. In reality they differ: think of stopwords such as “a”, “the” and “is”. For q = “a jaguar”, d3 beats d1 mainly because it repeats “a”, which is clearly wrong. This motivates modelling term importance with IDF (Section 8).
Long documents are more likely to get higher scores, because they contain more terms and more repetitions. Later models (BM25 in Section 12, and language models with Dirichlet smoothing later in the course) use document length to correct this.
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”:d1d2d3“a cat”:d1d2d3=1+1=2=0+1=1=2+1=3=1+0=1=0=2+1=3
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:
it is static;
it is black or white: a term is either kept or removed;
we want graded sensitivity in modelling the importance of a term instead.
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∣log1+niN
Where
∣Q∣
number of query terms; i indexes them
N
total number of documents in the collection
ni
document frequency: the number of documents that contain query term i
1+ni
the +1 keeps the fraction finite when a term occurs in no document
log1+niN
the idf of term i, written 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 ni) 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 N) raises every weight equally and leaves the order of terms unchanged.
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)
Where
tf(i,D)
frequency of query term i in document D (the f(qi,D) of Section 7)
idf(i)
inverse document frequency of term i: log1+niN
∣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.
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.
Term
tf(i, D)
nᵢ
idf=log101+niN
tf × idf
the
10
8,000
log10800110000≈0.097
≈ 0.97
jaguar
3
50
log105110000≈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
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.
Answerlog10101,000,000log10100,0001,000,000=log10(100,000)=5=log10(10)=1
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.
Answeridf(jaguar)idf(a)=log1043≈−0.125=log1033=0
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:
The dimensions are terms; the value of each component is a term weight. A document is Di=(di1,di2,…,dit) and the query is Q=(q1,q2,…,qt).
The whole collection becomes a matrix of term weights, with documents as rows and terms as columns.
“Match of document and query” becomes similarity between the two vectors, computed with the cosine.
number of terms in the vocabulary (the number of dimensions)
j
index of a vocabulary term
dj
weight of term j in document D (for example its tf-idf)
qj
weight of term j in query Q
∑jdjqj
the dot product of the two vectors
∑jdj2,∑jqj2
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
1
Vectors point in the same direction
0
Nothing in common (geometrically: perpendicular)
−1
Same 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.
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), D2=(0.9,0.4,0.2), Q=(1.5,1.0,0).
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).
Advantages
Disadvantages
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?
AnswerDot product∣D∣2∣Q∣2cos=1⋅0+0⋅1+2⋅1=2=1+0+4=5=0+1+1=2=5×22=102≈0.63
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).
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)
Where
D
the document (its representation)
R,NR
the classes “relevant” and “non-relevant” (to the current query)
P(R∣D)
probability that D is relevant, given what D contains
P(NR∣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)P(D∣R)P(R)
Where
P(D∣R)
probability of seeing a document like D among the relevant documents
P(R)
prior probability of relevance (before looking at 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) scales the answer by how common relevance is overall, and dividing by P(D) normalises it. The same rewrite applies to P(NR∣D).
Applying Bayes' rule to both sides of the decision rule and rearranging (the P(D) terms cancel) gives: retrieve D if
likelihood ratioP(D∣NR)P(D∣R)>P(R)P(NR)
Where
P(D∣R),P(D∣NR)
probability of a document like D within the relevant set and within the non-relevant set
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)), 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.02, P(D∣NR)=0.004, and P(R)=0.1, so P(NR)=0.9.
1
Likelihood ratio:
0.0040.02=5
2
Threshold:
P(R)P(NR)=0.10.9=9
3
Cross-check with the unnormalised posteriors:
P(D∣R)P(R)P(D∣NR)P(NR)=0.002=0.0036
5<9⟺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:
Probabilities are estimated as accurately as possible. If the estimates fail to resemble reality, the ranking has room for error.
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), because P(R) and P(NR) are constant across all documents and can be ignored for ranking, and P(D∣NR) is handled through the complement (the lecture relates it to 1−P(D∣R)). So we can rank documents by decreasing P(D∣R). Step 1, common to most models, assumes that terms occur independently of one another:
P(D∣R)=i=1∏tP(di∣R)
Where
t
number of terms in the vocabulary
di
the feature of document D for term i (in the BIM: 1 if present, 0 if absent)
P(di∣R)
probability of that feature value among relevant documents
∏
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); probabilistic models differ exactly in how they do this, starting with the Binary Independence Model.
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). The BIM's setup:
A document is represented by a vector of binary features indicating term occurrence: element di=1 if term i is present and di=0 otherwise.
pi = probability that term ioccurs (has value 1) in a relevant document.
si = probability that term i occurs in a non-relevant document.
So 1−pi is the probability that term i is absent from a relevant document, and 1−si the corresponding probability for a non-relevant document.
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:
probability that term i occurs in a relevant, and in a non-relevant, document
1−pi,1−si
probability that term i 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/si: above 1 when the term is more common in relevant documents, pushing the document up. An absent term multiplies by (1−pi)/(1−si), 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−pi1−si⋅∏i:di=11−si1−pi; the two cancel, so nothing changes:
Regroup. The first two products run over the same terms, so they combine. The last factor in the bracket and the di=0 product together cover all terms:
=depends on Di:di=1∏si(1−pi)pi(1−si)⋅over all termsi∏1−si1−pi
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.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=1logsi(1−pi)pi(1−si), derived in full below.
11.2 The BIM scoring function
score(D)=i:di=1∑logsi(1−pi)pi(1−si)
Where
i:di=1
terms present in document D
pi
probability that term i occurs in a relevant document
si
probability that term i occurs in a non-relevant document
1−pipi,1−sisi
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
The query is our information about relevant documents, so assume pi is non-zero only for query terms: the score is computed only over terms in both the document and the query.
Assume pi is constant for all query terms, say pi=0.5; the pi/(1−pi) factor then equals 1.
Approximate si by the term's distribution in the whole collection, justified because most documents are non-relevant: si=ni/N.
score(D)=i∈Q∩D∑logniN−ni
Where
i∈Q∩D
terms that appear in both the query and the document
N
total number of documents in the collection
ni
number of documents containing term i
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.5 and si=ni/N into the BIM weight leaves logni/N1−ni/N=logniN−ni: 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=300 documents:
wlincoln=ln300500,000−300=ln(1665.7)≈7.42
2
president appears in ni=40,000 documents:
wpresident=ln40,000460,000=ln(11.5)≈2.44
ResultThe rare, discriminative term gets a weight about three times larger (7.42 against 2.44): exactly the IDF behaviour.
Takeaways
In the absence of relevance information, the BIM term weight is very similar to an IDF weight.
TF is absent: documents were assumed to have binary features, so the BIM has no notion of term frequency. BM25 adds it back.
PracticeUnder the simplified BIM (pi=0.5, si=ni/N), what weight does a term receive if it appears in exactly half of the collection? In more than half?
AnswerWith ni=2N:
log2NN−2N=log1=0
So matching it changes nothing. With ni>2N, 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:
Term-frequency saturation
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.
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 fi into a bounded value: the first occurrence adds the most, later ones add less and less, and the value can never exceed k1+1. Inside it, B 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 k1 lets repeated occurrences keep adding score; raising b punishes long documents more.
BM25's anatomy: three factors per query term, multiplied and then summed over the query. Length normalisation acts through the saturation factor.
Parameter
Controls
Typical value
Small value
Large value
k1
Term-frequency saturation
1.2
Saturates almost at once; near k1=0, presence alone counts (binary, like the BIM)
Repeats keep adding; as k1→∞ the factor approaches raw tf
b
Document length normalisation
0.75
b=0: length ignored (B=1)
b=1: full normalisation (B=dl/avdl)
k2
Within-query saturation
often large (Croft's example uses 100)
Repeated query terms saturate quickly
Factor approaches raw qfi
12.2 Component 1: the Robertson–Spärck Jones (RSJ) weight
The RSJ weight uses knowledge about relevance: the number of relevant documents R and the number of relevant documents containing term i, ri. 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. N and ni refer to the documents that were judged to obtain R and ri. The 0.5 terms are smoothing factors. If no relevance information is available (R=ri=0), and N, ni become the collection size and document frequency, the weight simplifies to:
wiRSJ=logni+0.5N−ni+0.5
Where
wiRSJ
the RSJ weight of query term i with no relevance information
N
number of documents in the collection
ni
number of documents containing term i
0.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 k1 controls this:
sat(fi)=k1B+fi(k1+1)fi
Where
fi
frequency of term i in the document
k1
saturation parameter, k1>0, typically 1.2
B
length normalisation factor (equal to 1 for a document of average length)
k1+1
scaling that makes the factor equal 1 when fi=1 and B=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 fi grows, the fi in the denominator catches up with the one in the numerator, so the value climbs quickly at first and then levels off towards k1+1. High k1: saturation happens only at high frequencies, so fi keeps contributing significantly. Low k1: additional occurrences tail off very quickly; at k1=0 the factor is 1 for any fi>0, which is the BIM's binary view. A typical setting is k1=1.2, giving a ceiling of 2.2.
Normalised saturation fi/(k1+fi) (the saturation factor divided by its ceiling k1+1, for a document of average length) against term frequency, for four values of k1. Small k1: the curve flattens almost immediately. Large k1: repeated occurrences keep adding to the score.
12.4 Component 3: document length normalisation
B provides a soft normalisation of document length and is used to normalise the term frequency fi inside the saturation factor:
B=(1−b)+b⋅avdldl,0≤b≤1
Where
B
length normalisation factor, multiplied by k1 in the saturation denominator
b
parameter controlling how much length matters, typically 0.75
dl
length of the document being scored
avdl
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 wordsB is a blend of 1 (ignore length) and dl/avdl (full relative length), with b as the mixing weight. A document of exactly average length always gets B=1. A longer document gets B>1, which enlarges the saturation denominator, so each occurrence is worth less; a shorter one gets B<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 b lets the system lean either way.
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+qfi(k2+1)qfi
Where
qfi
number of times term i occurs in the query
k2
within-query saturation constant (called k3 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=1) the factor is exactly 1 whatever k2 is, so short queries are unaffected. Larger k2 lets repeated query terms count almost linearly; smaller k2 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×avdl; N=500,000; “president” occurs in n1=40,000 documents (common) and “lincoln” in n2=300 (discriminative); no relevance information; k1=1.2, b=0.75; short query, so the within-query factor is 1. Natural log.
1
Length normalisation (the same for every document here):
The full table (each row is a different document):
f(“president”)
f(“lincoln”)
BM25 score
15
25
20.66
15
1
12.74
15
0
5.00
1
25
18.2
0
25
15.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:
Why does (15, 0) score lower than (0, 25)? Lower term frequency, and the IDF-like weight of “president” (2.44) is far lower than that of “lincoln” (7.42), because lincoln is much more discriminative.
Why do more matches of “president” add so little? Going from (1, 25) to (15, 25) only lifts the score from 18.2 to 20.66: “president” has a low IDF, and additional occurrences are dampened by the saturation function.
Why do more matches of “lincoln” add a lot? Going from (15, 1) to (15, 25) lifts the score from 12.74 to 20.66: lincoln occurs in fewer documents, so it is more discriminative (high IDF), and its saturated tf is multiplied by a large weight.
Worked example 13How k₁ and b move the saturation factor
Illustrative values, looking only at the saturation factor k1B+f(k1+1)f.
1
Vary k1 for an average-length document (B=1). With f=1 the factor is k1+1k1+1=1 for every k1. With f=10:
k1=0.2:factork1=1.2:factork1=3:factor=10.212=1.18=11.222=1.96=1340=3.08
2
Vary b for f=3, k1=1.2 and a long document (dl=2×avdl):
b=0:B=1,factorb=0.75:B=1.75,factorb=1:B=2,factor=4.26.6=1.57=2.1+36.6=1.29=2.4+36.6=1.22
3
Short document (dl=0.5×avdl, b=0.75):
B=0.625,factor=0.75+36.6=1.76
Resultk1 only decides how much the later occurrences add (ten occurrences are worth 1.18 to 3.08 first occurrences); b decides how strongly the same count is discounted in long documents and boosted in short ones.
PracticeWhat does BM25 reduce to when k1=0? And when b=0 and k1 grows very large?
Look at the saturation factor in each limit; assume no relevance information and a short query.
AnswerWith k1=0, the factor is fifi=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=0 (B=1) and k1→∞, k1+fi(k1+1)fi→fi, so BM25 approaches ∑tf×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×avdl and D_long has dl=3×avdl. With k1=1.2, which scores higher for “lincoln” at b=0.75, and what changes at b=0?
AnswerAt b=0.75:
D_short:B=0.625,factorD_long:B=2.5,factor=0.75+48.8=1.85=3+48.8=1.26
D_short scores higher. At b=0, both have B=1 and the factor is 5.28.8=1.69 for both: length no longer matters, and they tie.
13. Summary and study checklist
Model
Representation
Scoring idea
Ranking?
Key limitation
Boolean
Binary term presence
Satisfy the Boolean expression (set retrieval)
No (set only)
No partial matching, no ranking; expert-only queries
+ CLM
Binary
Rank satisfying documents by the number of clauses or terms matched
Yes
Still requires full Boolean satisfaction
TF
Term counts (bag of words)
∑if(qi,D)
Yes
All terms equally important; favours long documents
IDF
Collection statistics
∑ilog1+niN
Yes
Ignores within-document frequency
TF-IDF
Weighted counts
∑itf(i,D)⋅idf(i)
Yes
No saturation, no length normalisation
VSM
Vectors of term weights
Cosine similarity
Yes
Term independence; ignores word order
BIM
Binary features
∑i∈Q∩Dlogsi(1−pi)pi(1−si), which becomes an IDF-like weight
Yes
No term frequency
BM25
Counts, lengths, optional relevance information
RSJ weight (≈ IDF) × saturated tf × query factor
Yes
Still 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.
The week's through-line: two families of term-based models that meet in BM25.
13.1 Formula reference card
Model
Scoring function
TF
score(D,Q)=∑i=1∣Q∣f(qi,D)
IDF
score(D,Q)=∑i=1∣Q∣log1+niN
TF-IDF
score(D,Q)=∑i=1∣Q∣tf(i,D)×idf(i)
VSM (cosine)
score(D,Q)=∑jdj2⋅∑jqj2∑jdjqj
BIM
score(D)=∑i:di=1logsi(1−pi)pi(1−si), which with pi=0.5,si=ni/N becomes ∑i∈Q∩DlogniN−ni
BM25
∑i=1∣Q∣log((ni−ri+0.5)/(N−ni−R+ri+0.5)(ri+0.5)/(R−ri+0.5))⋅k1B+fi(k1+1)fi⋅k2+qfi(k2+1)qfi, with B=(1−b)+bavdldl
13.2 Study checklist
Define a relevance model and name its two components; place term-based models in the encoder-cost × scorer-cost table and justify O(|d|) and O(1).
Contrast retrieval and reranking models and sketch the cascade.
Encode a query and documents as binary vectors and apply the overlap score.
Evaluate Boolean queries with AND, OR and NOT on an incidence matrix; list the model's advantages, disadvantages and two fundamental problems.
Rank documents with coordination level matching, remembering that the Boolean query still filters.
Name the operators in a professional (PubMed-style) Boolean query: wildcard, explicit stemming, grouping, sub-grouping, adjacency, field restriction, MeSH heading and explosion.
Compute TF, IDF and TF-IDF scores by hand, and explain why a stoplist is a weaker fix than IDF.
Compute a cosine similarity and explain what the denominator does.
Derive the likelihood-ratio decision rule with Bayes' rule, state the PRP and its two assumptions, and name iPRP and qPRP.
Follow the BIM derivation and show how pi=0.5, si=ni/N yield an IDF-like weight; explain why the BIM has no tf.
Explain each BM25 component and predict how the score moves when k1, b, dl or ni change; reproduce the president/lincoln reasoning.
Robertson, S. E. “The probability ranking principle in IR.” Journal of Documentation 33.4 (1977): 294–304.
Fuhr, N. “A probability ranking principle for interactive information retrieval.” Information Retrieval 11.3 (2008): 251–265.
Zuccon, G., Azzopardi, L. and van Rijsbergen, C. J. “The quantum probability ranking principle for information retrieval.” Conference on the Theory of IR (2009).
Croft, W. B., Metzler, D. and Strohman, T. Search Engines: Information Retrieval in Practice: the derivation from the BIM to BM25 and the president/lincoln example.