INFS7410 · Information Retrieval and Web Search · Week 3

Retrieval Models I: Term-based Lexical Models

Simplified Technical English edition. These notes explain relevance models, retrieval models and reranking models. They then explain the term-based lexical models: the Boolean model, coordination level matching, professional Boolean search, TF, IDF, TF-IDF, the vector space model, the probability ranking principle, the Binary Independence Model and BM25. Each scoring formula has a symbol key, a spoken reading, a plain explanation and a worked example. The notes also show 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. It estimates how relevant each document is to a query. It uses a representation of the query, a representation of the document, and a function that measures their relationship. Each search system needs a relevance model. The model decides which documents answer the query and how well they answer it.

1.1 Example: where is UQ located?

A user searches for Where is UQ located. Two candidate web pages exist.

The relevance model gives each page a score. The score shows how well the page matches the query. A score of 1 means highly relevant. A score of 0 means not relevant. Page A can get 0.98. Page B can get 0.03. The system uses these scores to make the ranking.

1.2 Structure: encoder plus scorer

Each relevance model has two components:

  1. The encoder changes the query and the document into representations. Examples are term vectors and embeddings.
  2. The scorer compares the two representations. It gives 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 structure of a relevance model. The encoder makes a representation of the query and of the document. The scorer compares the two representations. Keyword search and neural rankers use this same structure.

1.3 The relevance-model cost table

Two costs measure the complexity of a relevance model: the encoder cost and the scorer cost. The course puts each model in a table with these two axes. Simple models, for example the Boolean model and BM25, have a low cost on both axes. Neural rerankers, for example monoBERT, have a much higher cost. Later weeks explain these rerankers. The table starts empty. The course adds each model to the table when it introduces the 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. All models in this week are in the cell with the lowest cost. The encoding cost is O(|d|). The scoring cost is approximately O(1) for each query–document pair. Later weeks fill the other cells.
Key ideaThe encoding cost is proportional to the document length |d|. The reason is that the index build must process each term in the document. The scoring cost is approximately O(1) for each query–document pair. This statement assumes that an inverted index (Week 1) selects the candidate documents first. The scorer then adds the weights of the terms that the query and the document share. This set of shared terms is small. The cost stays the same when documents and collections become larger. For this reason, term-based models are fast and scalable. Modern search engines still use them.

George E. P. Box said: “All models are wrong, but some are useful” (slide 10). This statement applies to all models in this week. A retrieval model is a simplified version of relevance. A useful model keeps the parts of relevance that are important.

PracticeGive the two components of a relevance model. Explain why a term-based model scores a query–document pair in approximately constant time.
Think about the terms that add to the score. Think about the data structure that finds the candidate documents.
AnswerThe encoder changes the query and the document into representations. The scorer compares them and gives a score. The inverted index gives only documents that contain query terms. The score adds weights only for the terms that the query and the document share. The number of these terms depends on the query length, which is small. It does not depend on the document length or the collection size. The encoding cost is O(|d|), because the index build processes each term of the document one time.

2. Retrieval models versus reranking models

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

This course examines two types of relevance models: the retrieval model and the reranking model.

AspectRetrieval modelReranking model
InputThe full document collectionOnly the top-n results from the retrieval model, usually 10 to 1,000 documents
ScoresEach document in the corpusOnly the selected documents
SpeedMust be fast and scalable. It uses approximations and heuristics.Can be slower and more complex
Typical methodsAn inverted index and lexical matching, for example BM25Deeper features and large machine-learning models, for example monoBERT
FunctionFirst stage: it quickly makes the list of candidates smallerLater stage: it changes the order of the candidates with better relevance estimates

Real systems use a cascade. A fast retrieval model is the first stage. One or more strong reranking models follow it.

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. The fast retrieval model makes a short list of candidates from the large collection. The expensive reranking model changes the order of only that short list.
Key ideaA retrieval model is a type of relevance model. It is fast and efficient. It is usually the first stage of a modern search system. It makes the list of candidates smaller before the reranking stage. The next weeks explain many retrieval models. This week explains the term-based lexical models.
PracticeA system searches 50 million web pages. It must answer each query in less than 100 ms. It must also use a BERT-based model for quality. Where does each model go in the pipeline? Why?
AnswerBM25, or a different lexical retrieval model, goes first. It uses the inverted index to score the full collection quickly. It gives, for example, the top 1,000 documents. The BERT-based model goes second, as a reranking model. It scores only these 1,000 candidates. A BERT-based model is too slow to score 50 million pages for each query. This pipeline is the cascade: a fast, broad stage first, then a slow, precise stage.

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 use the lexical form of the text, that is, the words as they are written. They usually measure relevance through the terms that the query and the document share.

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

The methods in the right column are the text-processing steps from Week 1. These methods make a lexical model more effective.

3.1 Each representation is a sparse vector

Real systems use an inverted index for these models, because it is efficient. But you can think of all lexical representations as sparse vectors. This includes Boolean, TF and TF-IDF representations.

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 as vectors. Each column is one term of the vocabulary. A 1 shows that the term is present. The query and D1 share uq and is (green columns). Thus D1 gets the score 1. D2 shares no term with the query. Thus D2 gets the score 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 one or more terms?

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 that you score
V(q),V(d)V(q), V(d)
the binary vectors of qq and dd. Value jj is 1 if term jj is present. Otherwise it is 0.
j, ∣V∣j,\ |V|
the index of a term in the vocabulary (one dimension), and the vocabulary size (the number of dimensions)
∧\wedge
logical AND. The result is 1 only if the two values are 1.
1[⋅]\mathbb{1}[\cdot]
indicator function. The result is 1 if the condition is true. It is 0 if the condition is false.
Read it aloud The score of document d for query q is one if the sum, over each vocabulary term j, of “term j is in the query AND term j is in the document” is more than zero. Otherwise, the score is zero.
Formula in plain words Put the two binary vectors side by side. Mark each position where the two vectors have a 1. Count the marks. If the count is more than zero, the document shares one or more query terms, and the score is 1. If the count is zero, the score is 0. The score is always 0 or 1. More shared terms do not increase the score. Thus this scorer only checks for a match. The slide writes the same test as sum(V(q) & V(d)) > 0. This test is the behaviour of a query that joins its terms with OR.

Worked example 1The Boolean model as vectors

Use a fixed token space (all possible terms): [he, born, what, uq, where, a, yes, is, university, in, australia, how, come, on, brisbane, was]. Write the query and two documents as binary vectors (1 = term is 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 a 1 at uq and at is. The sum is 2. This is more than 0.
2
Q ∧ D2 has only zeros. D2 shares no query term. The sum is 0.
ResultD1 gets the score 1, and the system retrieves it. D2 gets the score 0, and the system does not retrieve it.
Watch outThis vector view is only an illustration. Real Boolean retrieval uses inverted indexes. Inverted indexes are much more efficient for large collections.
PracticeWrite D3 = “Where was he born” as a binary vector over the same token space. 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). D3 shares where with the query. The overlap sum is 1, and the score is 1. D1 shares two terms and also gets the score 1. Thus the overlap score cannot separate 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 gets its name from Boolean logic and set theory. It uses them to define 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 parts of the expression
Ret(x)\mathrm{Ret}(x)
the set of documents that satisfy expression xx. For one term, this is the set of documents that contain the term. The postings list of the term gives this set.
∩\cap
intersection: the documents that are in the two sets
∪\cup
union: the documents that are in one or both sets
∖\setminus
set difference: the documents of the first set, without the documents of the second set
Read it aloud The documents for “a AND b” are the intersection of the documents for a and the documents for b. The documents for “a OR b” are the union of the two sets. The documents for “a NOT b” are the documents for a minus the documents for b.
Formula in plain words Each term selects a set of documents. This set is the postings list of the term (Week 1). AND keeps only the documents that are in the two sets. Thus each AND clause can only make the result smaller. OR joins the sets. Thus each OR clause can only make the result larger. NOT removes each document that contains the negated term. Each operation gives a set. A document is in the set or it is not in the set. The model does not show how well a document matches.

4.2 Worked examples on a collection of three documents

The term–document incidence matrix shows which terms are in which documents. A 1 shows that the term is present. An empty cell is 0.

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 makes the intersection of the sets. On the left, only d1 contains jaguar and animal. NOT removes the negated set. On the right, d3 contains cat, thus d1 and d2 stay. Green shows the retrieved documents.

Worked example 2q = “jaguar”

1
Retrieve each document that satisfies the expression. These are the documents that contain 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.

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

Worked example 4q = “jaguar NOT cat”

NOT removes each document that contains the negated term.

1
Documents that contain jaguar: {d1, d2, d3}.
2
Documents that contain cat: {d3}.
3
Remove these documents: {d1, d2, d3} \ {d3} = {d1, d2}.
Result{d1, d2}
PracticeExercise from the lecture: find the result of q = “jaguar AND car” on the same collection.
First find the set for each term. Then apply the operator.
AnswerDocuments that contain jaguar: {d1, d2, d3}. No document contains car. Thus its set is ∅. Intersection: {d1, d2, d3} ∩ ∅ = ∅. The system retrieves no document. One term with no match makes the full result empty. This shows that strict Boolean matching is brittle.
PracticeFind the result of 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 are important. Without the brackets, a different reading of the expression is possible.

4.3 Advantages and disadvantages

AdvantagesDisadvantages
You can predict the results. The results are easy to explain.The effectiveness depends fully on the user. The user must write a good query. Thus the model is good for expert users. These users know their needs, the collection and Boolean logic well.
You can add many features in addition to terms, for example conditions on the creation date or the language.Simple queries, for example one-term queries, usually give poor results.
It is very efficient. One bit can store a posting. The system removes many documents from the search very quickly.Complex queries are difficult to write. For this reason, UQ researchers develop methods that write good complex queries automatically, for example for medical literature search.
TakeawaysThe Boolean model has two basic problems. For these reasons, the Boolean model alone is not good for most users. It cannot manage the large vocabulary gap between users and collections. Week 1 calls this the vocabulary mismatch problem.
PracticeWhy is the Boolean model efficient? Why does the same property make it difficult for most users?
AnswerThe model needs to know only if each term is present. This needs one bit for each posting. The model removes each document that fails a clause immediately. Thus the evaluation is fast set arithmetic. But the same strict logic has a cost. The user must predict the exact words of the relevant documents and join them correctly. A missing synonym or a too strict AND removes relevant documents. No ranking reduces the effect of this error.

5. Ranking on top of Boolean: coordination level matching

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

Some methods add a ranking to Boolean logic. The classic method 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 in QQ. For a simple keyword query, these are the query terms.
cc
one clause (or term) of the query
1[⋅]\mathbb{1}[\cdot]
indicator. The result is 1 if DD satisfies clause cc. Otherwise it is 0.
Read it aloud The coordination level of document D for query Q is the sum, over each clause c of Q, of one if D satisfies c, and zero otherwise. You calculate it only for each document that satisfies Q.
Formula in plain words First, use the Boolean query as a filter. Only the documents that satisfy the query continue. Then count how many clauses each of these documents satisfies. Sort the documents by this count, from high to low. Each satisfied clause adds exactly one point. Thus all clauses have the same weight. Documents with the same count have the same rank. The filter stays. Thus CLM adds an order to the Boolean result, but it does not add 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 has two steps. First, the Boolean query filters the collection. Then CLM sorts the remaining documents by the number of clauses that they satisfy. The boxes show the clause numbers.

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

The two documents satisfy the professional Boolean query in Section 6 (slide 24).

1
Use only the documents that satisfy the Boolean query. The query must stay 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
Sort the documents by the number of satisfied clauses, from high to low.
ResultThe blue document is first (CLM = 4). The green document is 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 it does not satisfy Q. Give the CLM ranking.
AnswerA is first (3 clauses). B is second (2 clauses). C is not in the ranking. CLM sorts only the documents that satisfy the full Boolean query. The number of single clauses that C matches is not important.

6. Boolean search in professional practice

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

The Boolean model looks simple. But professionals use it a lot. Examples are patent retrieval, legal retrieval, contract retrieval and medical and scientific literature retrieval. PubMed is a very popular search engine for medical literature (advanced search). PubMed mainly uses a Boolean retrieval model with some advanced features.

The query below is a professional Boolean query for a systematic review. It is 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 labels. They are not part of the query. But lines 7, 17 and 18 use the numbers as a short way to join the clauses.

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 join. A document must match one or more drug clauses (line 7) and one or more disease clauses (line 17). Line 18 joins lines 7 and 17 with AND.
OperatorExampleFunction
Groupingor/1-6Joins clauses 1–6 with OR. Line 18 joins 7 AND 17.
Sub-grouping( … )Brackets put parts of an expression together in one clause.
Wildcardantagonist*Matches each string that starts with the given prefix.
Explicit stemmingblock$The $ operator does explicit stemming.
Field restriction.tw.Limits the search to specified index fields (text words: title and abstract). It is similar to ti in the project queries.
Adjacencyadj3The two terms or expressions must be within n words of each other. In line 12, obstruct* must be within 3 words of lung* or airway*.
MeSH headingPropranolol/Matches category metadata of the documents. MeSH is a controlled (fixed) medical vocabulary. Its terms have a hierarchy.
MeSH explosionexp …/Replaces the MeSH term with the term and all its children in the MeSH hierarchy (line 9).
Exam angleKnow the name of each operator type on slide 21: wildcard, explicit stemming, grouping, sub-grouping, adjacency, field restriction, MeSH heading and MeSH explosion. Know how lines 7, 17 and 18 join the clauses.
PracticeWhat must a document contain to satisfy line 18? How is line 9 different from line 8?
AnswerLine 18 is 7 and 17. The document must satisfy one or more of lines 1–6 (a beta-blocker clause) and one or more of lines 8–16 (a COPD clause). Line 8 matches documents with exactly the MeSH heading “Lung Diseases, Obstructive”. Line 9 uses exp. Thus it matches the heading “Pulmonary Disease, Chronic Obstructive” and each narrower heading below it in the MeSH hierarchy.

7. Beyond Boolean: the TF model

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

The TF (term frequency) model also uses a bag of words for documents and queries. A bag of words keeps repeated items, but it has no order. The improvement on the Boolean model is that TF uses term frequencies. A term frequency is the number of times that a term occurs in a document. The TF model does not need Boolean operators. But 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 removes the word order. It keeps the number of times that each term occurs. The TF model uses these counts to score documents.

The three example documents now make 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 that you score, and the query
∣Q∣|Q|
the size of the query (the number of query terms)
qiq_i
query term number ii
f(qi,D)f(q_i, D)
term frequency: the number of times that 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 The goal is to give a high score to the documents that contain the query terms most often. Go through the query terms only. Count each query term in the document. Add the counts. Each occurrence adds exactly one point. There is no upper limit. Thus a document that repeats one query term many times can get a higher score than a document that contains all query terms a moderate number of times. Also, all terms have the same weight. An occurrence of “a” gives the same points as an occurrence of “jaguar”.

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

For each document, add the counts of the query terms 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).
TakeawaysTF has two problems. The other models in this week solve them.
Common trapThe sum goes over the query terms. A term that is in the document but not in the query adds nothing to the score.
PracticeFrom slide 28: calculate the TF scores of d1, d2 and d3 for q = “a jaguar” and for q = “a cat”. What is the problem?
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} For the first query, d3 is first mainly because of the stopword “a”. This word gives no information about jaguars. For “a cat”, d1 gets a higher score than d2 only because of “a”. TF gives the same importance to each term.

8. IDF and TF-IDF

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

8.1 Motivation: terms have different importance

Terms have different importance. Stopwords such as “the”, “a” and “who” rarely help to find relevance. Remember Zipf's law from Week 1. A small set of terms occurs very often. A long tail of terms occurs rarely. A classic solution is a stoplist. A stoplist removes all stopwords. Slide 29 shows a stoplist from “a”, “a's”, “able” to “yourselves”, “z”, “zero”. A stoplist has problems:

8.2 Inverse document frequency

Thus we need a function that reduces the effect of terms that occur in too many documents. These terms do not help to estimate 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|
the number of query terms.
ii
the index of a query term.
NN
the 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 no document contains the term
log⁡N1+ni\log \frac{N}{1+n_i}
the idf of term ii, written idf(i)idf(i). You can use each log base. 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 (approximately) the number of documents that contain the term. Then calculate the log. A rare term (small nin_i) gives a large ratio and a high weight. A term that is in almost all documents gives a ratio near 1 and a weight near 0. The log makes the range smaller. A term in 10 documents has a higher weight than a term in 1,000 documents. But the difference in weight is much smaller than the difference in counts. A larger collection (larger NN) increases all weights by the same amount. The order of the terms stays the same.
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 against document frequency for the Reuters newswire collection (N = 806,791 documents). Rare terms get a high IDF. Common terms get a low IDF. The relation is logarithmic. The curve becomes flat quickly. A small group of rare terms has a very high IDF. A long tail of common terms has a low IDF.
Watch outFor the IDF-only sum, use only the query terms that D contains. The idf of a term is a property of the collection. If absent terms also count, each document gets the same score.
Key ideaTF depends only on the document that you score. IDF uses statistics of the full collection. Thus the IDF of a term is the same for each document.

8.3 TF and IDF together: TF-IDF

IDF alone is also a weak model. It does not use the number of times that the term occurs in the document. TF and IDF each give term weights. Usually you use them together: you multiply them for each query term. The name is 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)
the frequency of query term ii in document DD (the f(qi,D)f(q_i, D) of Section 7)
idf(i)idf(i)
the inverse document frequency of term ii: log⁡N1+ni\log \frac{N}{1+n_i}
∣Q∣|Q|
the 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 adds “how often it occurs in this document” (tf) multiplied by “how rare it is in the collection” (idf). A term gets a high tf-idf when it occurs often in this document and in few documents of the collection. A common term has an idf near zero. Thus many occurrences of a common term add little. The score removes most of the effect of common terms. A term that is absent from the document has tf = 0, and it adds nothing. The tf part has no upper limit, and it ignores the document length. BM25 solves these two problems.
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
The sources of the statistics. tf is a count in one document. idf is a statistic of the collection. Their product is the tf-idf weight of the term in that document.

Worked example 7How TF-IDF solves the TF problem

Illustrative values: the collection has N = 10,000 documents. The query is “the jaguar”. Document D contains “the” 10 times and “jaguar” 3 times. The log base is 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
With TF only, “the” adds 10 points and “jaguar” adds 3 points. The stopword has the largest effect.
2
With TF-IDF, “the” adds approximately 0.97. “jaguar” adds approximately 6.88.
score(D)≈0.97+6.88=7.85 \mathrm{score}(D) \approx 0.97 + 6.88 = 7.85
ResultNow the discriminative term has the largest effect on the score. This is correct. You can use each log base. A different base multiplies all scores by the same factor. The ranking stays the same.
PracticeA collection has N = 1,000,000 documents. Calculate the idf (base 10) of a term in 9 documents and of a term 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 approximately 11,000 times more common. But its weight is only 5 times smaller. The log makes the scale smaller.
PracticeCalculate idf(jaguar) and idf(a) (base 10) in the collection of three jaguar documents. What do you see?
All 3 documents contain jaguar. d1 and d3 contain a.
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 in all documents gets a small negative weight. You can see this in a very small collection. In a real collection, it has an effect only on terms in almost all documents. These terms do not help the ranking.

9. The vector space model

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

The vector space model (VSM) often uses TF-IDF to calculate its term weights. The model shows documents and queries as 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
the number of terms in the vocabulary (the number of dimensions)
jj
the index of a vocabulary term
djd_j
the weight of term jj in document DD, for example its tf-idf
qjq_j
the 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 vector and the query vector
Read it aloud The score of D for Q is the cosine of the angle between them. It is 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 each term, and adds the products. It increases when the two vectors put weight on the same terms. The denominator divides by the lengths of the two vectors. This removes the effect of size. If you multiply all weights of a document by 2, its cosine stays the same. Thus a long document gets no advantage only because it is long. The remaining value is the angle between the vectors. A smaller angle gives a larger cosine and a higher rank. A term with weight 0 in one of the two vectors adds nothing to the numerator. Thus the calculation needs only the shared terms.
cos(D, Q)Meaning
1The vectors point in the same direction
0The vectors have nothing in common (they are perpendicular)
−1The vectors have the same components, but opposite directions

If all weights are positive, as with TF-IDF, the cosine is between 0 and 1. After you calculate the cosine for all documents, sort the documents by decreasing similarity to the query.

Term 3 Term 2 Term 1 Doc1 Doc2 Query θ₁ θ₂
The documents and the query are in the same term space. A smaller angle gives a larger cosine. Here θ₂ < θ₁. Thus Doc2 has a higher rank than Doc1.

Worked example 8Cosine similarity from the lecture

The weighted vectors have 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
Sort by decreasing cosine. The third term has query weight 0. Thus it adds nothing to the two numerators. You can ignore each term with weight 0 in the query or the document in the sums of products. For this reason, VSM is efficient with sparse vectors.
ResultD2 (0.97) ≻ D1 (0.87).
AdvantagesDisadvantages
It is a simple framework for ranking. The sparse term data makes an efficient implementation possible.It assumes that terms are independent. It ignores the order of the terms in documents. TF, IDF and the other models in this week have the same assumption.
You can use each similarity measure and each weighting scheme: TF-IDF (the most common), TF only, IDF only, or BM25 weights.
PracticeCalculate cos(D, Q) for D = (1, 0, 2) and Q = (0, 1, 1). Why is the cosine never negative with TF-IDF weights?
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, each weight is zero or positive (except the small-collection case of Section 8). Thus each product in the numerator is zero or more, and the cosine is 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 use a classification view of retrieval. They put documents 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 D is in the relevant class is more than the probability that D is in 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” (for the current query)
P(R∣D)P(R \mid D)
the probability that D is relevant, given the content of D
P(NR∣D)P(NR \mid D)
the probability that D is non-relevant, given the content of D
Read it aloud Retrieve D if the probability of relevance given D is more than the probability of non-relevance given D.
Formula in plain words This rule is a classifier with two classes. Put D in the class with the higher probability. The two probabilities add up to 1. Thus the rule is the same as “retrieve D if P(R | D) > 0.5”. You cannot calculate these probabilities directly. For this reason, the next step uses Bayes' rule.

Remember Bayes' rule. It changes the form of 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)
the probability of a document like D in the set of relevant documents
P(R)P(R)
the prior probability of relevance (before you examine D)
P(D)P(D)
the 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 changes a question that you cannot answer directly (“is this document relevant?”) into a question that you can estimate from examples (“how probable is a document like this in the relevant set?”). The prior P(R)P(R) adjusts the answer for how common relevance is. The division by P(D)P(D) normalises it. The same change applies to P(NR∣D)P(NR \mid D).

Apply Bayes' rule to the two sides of the decision rule. Then change the order of the terms. The P(D)P(D) terms cancel. The result is: 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)
the probability of a document like D in the relevant set, and in the non-relevant set
P(R), P(NR)P(R),\ P(NR)
the prior probabilities of relevance and of non-relevance
Read it aloud Retrieve D if the likelihood ratio, P of D given R over P of D given NR, is more than P of NR over P of R.
Formula in plain words The left side is the likelihood ratio. It shows how much more typical D is of relevant documents than of non-relevant documents. It is the only part that depends on the document. The right side is a fixed threshold from the priors. When relevant documents are rare (small P(R)P(R)), the threshold is high. Then a document must be very similar to relevant documents before the system retrieves it. For ranking, only the likelihood ratio is important. Sort the documents by this ratio to get the order.

Worked example 9Use 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. Thus 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
Check with the posteriors before normalisation: 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. But relevance is very rare. Thus D is more probably non-relevant, and the rule says: do not retrieve D. In a ranking, D is still above each 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)

A mathematical proof shows that the PRP gives the best possible ranking. But the proof needs some assumptions:

  1. The system estimates the probabilities as accurately as possible. If the estimates are different from reality, the ranking can have errors.
  2. The relevance of each document is independent (this assumption is implicit). The relevance of one document has no relation to the relevance of other documents. The model assumes that the user examines each document alone. It also assumes that the user forgets all information from the search. For example, the PRP can put many copies of the same document one after the other. But the copies give no new information to the user. In reality, this assumption is often false.

Other principles exist for cases where the assumptions are false: iPRP (Fuhr, 2008) for interactive IR, and qPRP (Zuccon, Azzopardi and van Rijsbergen, 2009) for dependent document relevance. The “overall effectiveness” in the PRP is measured with the evaluation measures of Week 2.

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

The estimation problem becomes an estimate of P(D∣R)P(D \mid R). The reason is that P(R)P(R) and P(NR)P(NR) are the same for all documents. Thus you can ignore them for ranking. The complement gives P(D∣NR)P(D \mid NR). The lecture relates it to 1−P(D∣R)1 - P(D \mid R). Thus you can sort documents by decreasing P(D∣R)P(D \mid R). Step 1 is the same in most models. It assumes that terms occur independently of each other:

P(D∣R)=∏i=1tP(di∣R) P(D \mid R) = \prod_{i=1}^{t} P(d_i \mid R)
Where
tt
the number of terms in the vocabulary
did_i
the feature of document DD for term ii. In the BIM, it is 1 if the term is present and 0 if it is absent.
P(di∣R)P(d_i \mid R)
the probability of that feature value in relevant documents
∏\prod
the product over all terms
Read it aloud The probability of D given R is the product, over each term i from one to t, of the probability of d-i given R.
Formula in plain words Independence changes one difficult probability (of a full document) into many easy probabilities (of single terms). You multiply the probabilities of the single terms. The cost is that the model ignores word order and co-occurrence. TF and VSM make the same simplification. The next question is how to estimate each P(di∣R)P(d_i \mid R). Probabilistic models are different in how they do this. The first model is 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. It starts with a classification decision and ends with an estimation problem for each term. The BIM and BM25 solve this problem.
PracticeGive the two assumptions of the PRP. Give an example result list that satisfies the PRP but is bad for the user.
Answer(1) The system estimates the probabilities of relevance as accurately as possible. (2) The relevance of each document is independent of the other documents. Example: the top five results are five copies (or near copies) of the same relevant page. This list satisfies the PRP, because each copy has the same high probability of relevance. But after the first copy, the user gets no new information. qPRP is a proposal for this type 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 setup of the BIM:

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 of the BIM for each term: present or absent, in relevant or non-relevant documents.

11.1 The likelihood ratio in the BIM

With independence and binary features, the likelihood ratio has two parts. The first part is a product over the terms in the document. The second part is a product over the terms that are absent from the document.

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 that are present in DD
i: di=0i:\,d_i=0
all vocabulary terms that are absent from DD
pi, sip_i,\ s_i
the probability that term ii occurs in a relevant document, and in a non-relevant document
1−pi, 1−si1-p_i,\ 1-s_i
the probability that term ii is absent from a relevant document, 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 Each term in the vocabulary gives a vote. A present term multiplies the ratio by pi/sip_i/s_i. This value is more than 1 when the term is more common in relevant documents. Then the document moves up. An absent term multiplies the ratio by (1−pi)/(1−si)(1-p_i)/(1-s_i). This is the vote for absence. The ratio of the document is the product of all votes. For this reason, the model needs the independence assumption.

Worked example 10From the likelihood ratio to the BIM score

The derivation has three steps (slides 45–48). It starts from the product above.

1
Add 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}. These two products cancel. Thus the value stays the same:
=∏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
Put the products in new groups. The first two products use the same terms. Thus you can join them. The last factor in the brackets and the di=0d_i = 0 product together use 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
Remove the constant and use logs. The second product uses all terms of the collection. Thus it is the same for each document, and you can ignore it for ranking. The remaining product multiplies probabilities (numbers in [0, 1]). The result becomes very small quickly, for example 0.1×0.1=0.010.1 \times 0.1 = 0.01. Computers cannot show very small decimal numbers accurately (floating-point underflow). The log changes 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)}. The next subsection explains it.

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
the terms that are present in document DD
pip_i
the probability that term ii occurs in a relevant document
sis_i
the 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 that the term occurs in the relevant set and in the non-relevant set. The fraction is the ratio of these odds.
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 weight is the log of (the odds of the term in relevant documents) divided by (the odds of the term in non-relevant documents). A term that is much more probable in relevant documents adds a large positive weight. A term with the same probability in the two sets adds log 1 = 0. A term that is more typical of non-relevant documents decreases the score. Absent terms add nothing. The model has no term frequency. A present term counts one time.

11.3 Make the score 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
the terms that are in the query and in the document
NN
the total number of documents in the collection
nin_i
the number of documents that contain term ii
Read it aloud The score of D is the sum, over terms in the query and the document, of the log of N minus n-i over n-i.
Formula in plain words Put pi=0.5p_i = 0.5 and si=ni/Ns_i = n_i/N into the BIM weight. The result is log⁡1−ni/Nni/N=log⁡N−nini\log\frac{1-n_i/N}{n_i/N} = \log\frac{N-n_i}{n_i}. This is the number of documents without the term divided by the number of documents with the term. Rare terms get large weights. Common terms get small weights. This is the same behaviour as IDF. A term in more than half of the collection gets a negative weight. Each matched term counts one time, independent of its frequency.

Worked example 11BIM term weights for president and lincoln

The collection has N = 500,000 documents. This is the collection of the BM25 example in Section 12. The log is the natural log.

1
lincoln occurs 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 occurs 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 that is approximately three times larger (7.42 against 2.44). This is the same behaviour as IDF.
Takeaways
PracticeIn the simplified BIM (pi=0.5p_i = 0.5, si=ni/Ns_i = n_i/N), what weight does a term get if it is in exactly half of the collection? What weight does it get if it is 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 A match with this term does not change the score. With ni>N2n_i > \frac{N}{2}, the fraction is less than 1, and the weight is negative. A match with a very common term decreases the score a little. The RSJ weight of BM25, with its 0.5 smoothing, has the same behaviour.

12. BM25

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

BM25 is a popular and effective probabilistic ranking model. It comes from the Binary Independence Model. The textbook by Croft, Metzler and Strohman shows the derivation from the BIM to BM25. BM25 extends the tf-idf idea (in its general form, without relevance information). It has two main differences:

  1. Term-frequency saturation
  2. Document length normalisation

There is a third difference. The most general form of BM25 can also use relevance information (judged documents). But this information is rarely available. Experiments show that BM25 is reliable and robust. It gives good results without tuning in most situations. It is the default ranking model in many open-source search libraries, for example Lucene and Elasticsearch. Thus it is also the default in Pyserini, which the pracs use. Web search engines use BM25 as one of their important features.

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
the number of query terms, and the index of a query term
RR
the number of documents that are judged relevant
rir_i
the number of judged-relevant documents that contain term ii
N, niN,\ n_i
the number of judged documents, and the judged documents that contain term ii. Without judgements, these are the collection size and the document frequency.
0.50.5
a smoothing constant. It keeps all counts positive.
fif_i
the frequency of term ii in the document
qfiqf_i
the frequency of term ii in the query
k1k_1
the term-frequency saturation parameter, k1>0k_1 > 0 (usually 1.2)
k2k_2
the within-query saturation parameter (some authors write k3k_3)
BB
the document length normalisation factor
bb
the length normalisation parameter, 0≤b≤10 \le b \le 1 (usually 0.75)
dl, avdldl,\ avdl
the length of the document, and the 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 first factor is the Robertson–Spärck Jones weight of term i. The second is k-one plus one times f-i, over k-one times B plus f-i. The third is 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 factors. The RSJ weight shows how strongly the term indicates relevance. Without judgements, it shows how rare the term is: it is an IDF. The saturation factor changes the count fif_i into a value with an upper limit. The first occurrence adds the most. Each next occurrence adds less. The value is never more than k1+1k_1 + 1. In this factor, BB increases the denominator for documents that are longer than average. Thus the same count has less value in a long document. The within-query factor applies the same saturation to terms that repeat in the query. For a usual short query, it equals 1. A larger k1k_1 lets repeated occurrences add more score. A larger bb gives a larger penalty to long documents.
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
The parts of BM25. For each query term, BM25 multiplies three factors. It then adds the results for all query terms. The length normalisation has its effect through the saturation factor.
ParameterControlsUsual valueSmall valueLarge value
k1k_1Term-frequency saturation1.2Saturation is almost immediate. Near k1=0k_1 = 0, only presence counts (binary, as in the BIM).Repeated occurrences continue to add score. When k1→∞k_1 \to \infty, the factor becomes the raw tf.
bbDocument length normalisation0.75b=0b = 0: the length has no effect (B=1B = 1)b=1b = 1: full normalisation (B=dl/avdlB = dl/avdl)
k2k_2Within-query saturationoften large (the Croft example uses 100)Repeated query terms saturate quicklyThe factor becomes the raw qfiqf_i

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

The RSJ weight uses relevance information. This information is the number of relevant documents RR, and the number of relevant documents that contain term ii, rir_i. The top of the ratio compares the relevant documents with the term and the relevant documents without the term. The bottom makes the same comparison for the judged non-relevant documents. NN and nin_i are the counts of the documents that were judged to get RR and rir_i. The 0.5 values are smoothing factors. If no relevance information is available (R=ri=0R = r_i = 0), NN and nin_i become the collection size and the document frequency. Then the weight becomes:

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 without relevance information
NN
the number of documents in the collection
nin_i
the number of documents that contain term ii
0.50.5
smoothing. It prevents division by zero and the 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 the two counts. It divides the documents without the term by the documents with the term. It is an approximation of the classical IDF. A rarer term gets a larger weight. A term in more than half of the collection gets a negative weight. When relevance judgements exist, the full form increases the weight of terms that occur often in the judged-relevant documents.

12.3 Component 2: term-frequency saturation

The occurrences of a term cannot add more than a saturation point to the document score. 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
the frequency of term ii in the document
k1k_1
the saturation parameter, k1>0k_1 > 0, usually 1.2
BB
the length normalisation factor (equal to 1 for a document of average length)
k1+1k_1 + 1
a scale factor. It makes the factor equal to 1 when fi=1f_i = 1 and B=1B = 1. It is also the upper limit.
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 When fif_i increases, the fif_i in the denominator becomes more important. Thus the value increases quickly at first, and then it becomes flat near k1+1k_1 + 1. High k1k_1: saturation occurs only at high frequencies. Thus fif_i continues to add much score. Low k1k_1: more occurrences add less and less, very quickly. At k1=0k_1 = 0, the factor is 1 for each fi>0f_i > 0. This is the binary view of the BIM. The usual value is k1=1.2k_1 = 1.2. Then the upper limit is 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) against term frequency, for four values of k1k_1. This is the saturation factor divided by its upper limit k1+1k_1 + 1, for a document of average length. With a small k1k_1, the curve becomes flat almost immediately. With a large k1k_1, repeated occurrences continue to add score.

12.4 Component 3: document length normalisation

BB gives a soft normalisation of the document length. The saturation factor uses BB to normalise the term frequency fif_i:

B=(1−b)+b⋅dlavdl,0≤b≤1 B = (1-b) + b\cdot\frac{dl}{avdl}, \qquad 0 \le b \le 1
Where
BB
the length normalisation factor. The saturation denominator multiplies it by k1k_1.
bb
the parameter that controls the effect of the length, usually 0.75
dldl
the length of the document that you score
avdlavdl
the 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 mix of 1 (length has no effect) and dl/avdldl/avdl (the full relative length). bb is the weight of the mix. A document with exactly the average length always gets B=1B = 1. A longer document gets B>1B > 1. This makes the saturation denominator larger, thus each occurrence has less value. A shorter document gets B<1B < 1, thus each occurrence has more value. b = 1: full normalisation. b = 0: no normalisation. The usual value is b = 0.75. Why is the length important? An author writes a document that is longer or shorter than average for a reason. One reason is verbosity: the author adds too many words. Then shorter documents are better. A different reason is scope: for example, a user who writes an essay needs many details. Then longer documents are better. The parameter bb lets the system choose between these two cases.
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 average, equal to average, and longer than average. Long documents get the largest decrease for repeated occurrences.

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
the number of times that term ii occurs in the query
k2k_2
the within-query saturation constant (some authors write k3k_3)
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 This factor gives weight to query terms by their frequency in the query. It has the same saturation shape as the document factor. It is useful only for longer queries, where a term can repeat. For a term that occurs one time (qfi=1qf_i = 1), the factor is exactly 1 for each k2k_2. Thus it has no effect on short queries. A larger k2k_2 lets repeated query terms count almost linearly. A smaller k2k_2 makes them saturate quickly. Experiments show that this component is not important. Real systems often treat repeated query terms as different terms.

12.6 Worked examples

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

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

1
Length normalisation (the same for each document in this example):
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 (similar to IDF):
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
Calculate the full score of one document 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
ResultThese are the scores from the lecture. A new calculation with the values above gives 20.63, 12.74, 5.00, 18.17 and 15.62. The small differences come from the rounding of the weights.
Exam angleThe lecture asks three questions about this table:

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

Illustrative values. This example examines only the saturation factor (k1+1)fk1B+f\frac{(k_1+1)f}{k_1B+f}.

1
Change k1k_1 for a document of average length (B=1B = 1). With f=1f = 1, the factor is k1+1k1+1=1\frac{k_1+1}{k_1+1} = 1 for each 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
Change 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 controls only the value of the later occurrences. Ten occurrences have the value of 1.18 to 3.08 first occurrences. bb controls how much the same count decreases in long documents and increases in short documents.
PracticeWhat does BM25 become when k1=0k_1 = 0? What does it become when b=0b = 0 and k1k_1 is very large?
Examine the saturation factor in each case. Assume that no relevance information is available and that the query is short.
AnswerWith k1=0k_1 = 0, the factor is fifi=1\frac{f_i}{f_i} = 1 for each matched term. Thus BM25 becomes the sum of the RSJ weights of the matched terms. This is the BIM with an IDF-like weight and 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. Thus BM25 becomes ∑tf×RSJ\sum tf \times \text{RSJ}. This is almost TF-IDF, with a tf that has no limit and no length normalisation. The usual settings are between these two cases.
PracticeTwo documents each contain “lincoln” 4 times. D_short has dl=0.5×avdldl = 0.5 \times avdl. D_long has dl=3×avdldl = 3 \times avdl. k1=1.2k_1 = 1.2. Which document gets the higher score for “lincoln” at b=0.75b = 0.75? 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 gets the higher score. At b=0b = 0, the two documents have B=1B = 1. The factor is 8.85.2=1.69\frac{8.8}{5.2} = 1.69 for the two documents. The length has no effect, and the scores are equal.

13. Summary and study checklist

ModelRepresentationScoring ideaRanking?Main limitation
BooleanBinary term presenceSatisfy the Boolean expression (set retrieval)No (set only)No partial matching, no ranking. Only expert users write good queries.
+ CLMBinarySort the matching documents by the number of matched clauses or termsYesThe document must still satisfy the full Boolean query
TFTerm counts (bag of words)∑if(qi,D)\sum_i f(q_i,D)YesAll terms have the same importance. Long documents get an advantage.
IDFCollection statistics∑ilog⁡N1+ni\sum_i \log\frac{N}{1+n_i}YesIgnores the frequency in the document
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 the 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)}. This becomes an IDF-like weight.YesNo term frequency
BM25Counts, lengths, optional relevance informationRSJ weight (≈ IDF) × saturated tf × query factorYesIt is still lexical: no semantics, term independence
TakeawaysEach model solves the main problem of the model before it. Boolean (no ranking) → TF (adds frequency) → TF-IDF (adds term importance) → VSM (a general geometric ranking framework) → BIM (a probabilistic basis, the PRP) → BM25 (adds tf saturation and document length normalisation to the probabilistic framework). All these models are term-based lexical models. Their encoding cost is low (O(|d|)). Their scoring cost is low (O(1) for each pair with an inverted index). All of them 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 main line of this week: two groups of term-based models that join 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)}. With pi=0.5, si=ni/Np_i=0.5,\ s_i=n_i/N, it 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.

VideoLengthSection
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