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.
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.
Page A is the Wikipedia article about the University of Queensland. It says that UQ is a public research university, mainly in Brisbane, Queensland. It answers the question. It is highly relevant.
Page B is the Wikipedia article about Australia. It gives general information about Australia. It does not help the user. It is not relevant.
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:
The encoder changes the query and the document into representations. Examples are term vectors and embeddings.
The scorer compares the two representations. It gives the relevance score.
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.
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.
Aspect
Retrieval model
Reranking model
Input
The full document collection
Only the top-n results from the retrieval model, usually 10 to 1,000 documents
Scores
Each document in the corpus
Only the selected documents
Speed
Must be fast and scalable. It uses approximations and heuristics.
Can be slower and more complex
Typical methods
An inverted index and lexical matching, for example BM25
Deeper features and large machine-learning models, for example monoBERT
Function
First stage: it quickly makes the list of candidates smaller
Later 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.
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.
The representations come from the terms of the query and the document. They use features such as term frequency or term presence.
The scores come from the terms that the query and the document have in common.
Common lexical models
Methods that you can add
Boolean model · TF (term frequency) · TF-IDF · Vector space model (VSM) · Binary Independence Model (BIM) · BM25
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.
The length of each vector is the vocabulary size. Each dimension is one unique term of the collection.
Most values are zero. A typical document or query contains only a very small part of all terms.
The non-zero values show the presence, the frequency or the weighted importance of terms.
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)=1j=1∑∣V∣V(q)j∧V(d)j>0
Where
q,d
the query and the document that you score
V(q),V(d)
the binary vectors of q and d. Value j is 1 if term j is present. Otherwise it is 0.
j,∣V∣
the index of a term in the vocabulary (one dimension), and the vocabulary size (the number of dimensions)
∧
logical AND. The result is 1 only if the two values are 1.
1[⋅]
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):
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 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.
The query is a Boolean expression. It joins terms with the operators AND, OR and NOT. Some systems also have more advanced operators, for example proximity.
The system retrieves only the documents that satisfy the Boolean expression.
The model has no term frequency. A term is present or absent. The model also has no scores. The output is a set of documents.
the set of documents that satisfy expression x. For one term, this is the set of documents that contain the term. The postings list of the term gives this set.
∩
intersection: the documents that are in the two sets
∪
union: the documents that are in one or both sets
∖
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.
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 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”
NOTremoves each document that contains the negated term.
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
Advantages
Disadvantages
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.
No partial matching: Boolean logic is strict. A document satisfies the full query, or the system does not retrieve it.
No scores and no ranking: the model cannot show how well a document matches. It gives a set with no order.
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).
A document with n different index terms in common with the query is more relevant than a document with n − 1 terms in common.
The coordination level (“size of overlap”) of a query Q and a document D is the number of terms that they have in common.
For the Boolean model, the coordination level is 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 in Q. For a simple keyword query, these are the query terms.
c
one clause (or term) of the query
1[⋅]
indicator. The result is 1 if D satisfies clause c. 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.
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.
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.
Operator
Example
Function
Grouping
or/1-6
Joins clauses 1–6 with OR. Line 18 joins 7 AND 17.
Sub-grouping
( … )
Brackets put parts of an expression together in one clause.
Wildcard
antagonist*
Matches each string that starts with the given prefix.
Explicit stemming
block$
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.
Adjacency
adj3
The 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 heading
Propranolol/
Matches category metadata of the documents. MeSH is a controlled (fixed) medical vocabulary. Its terms have a hierarchy.
MeSH explosion
exp …/
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.
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…”.
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 that you score, and the query
∣Q∣
the size of the query (the number of query terms)
qi
query term number i
f(qi,D)
term frequency: the number of times that 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
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.
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).
TakeawaysTF has two problems. The other models in this week solve them.
All terms have the same importance. In reality, terms have different importance. Examples are stopwords such as “a”, “the” and “is”. For q = “a jaguar”, d3 gets a higher score than d1, mainly because d3 repeats “a”. This result is wrong. IDF (Section 8) gives each term an importance.
Long documents usually get higher scores. They contain more terms and more repetitions. Later models use the document length to correct this. Examples are BM25 (Section 12) and, later in the course, language models with Dirichlet smoothing.
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”:d1d2d3“a cat”:d1d2d3=1+1=2=0+1=1=2+1=3=1+0=1=0=2+1=3
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:
it is static;
it has only two options: the system keeps a term or removes it;
we want a graded importance for each term.
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∣log1+niN
Where
∣Q∣
the number of query terms.
i
the index of a query term.
N
the 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 no document contains the term
log1+niN
the idf of term i, written 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 ni) 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 N) increases all weights by the same amount. The order of the terms stays the same.
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)
Where
tf(i,D)
the frequency of query term i in document D (the f(qi,D) of Section 7)
idf(i)
the inverse document frequency of term i: log1+niN
∣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.
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.
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
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
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.
Answerlog10101,000,000log10100,0001,000,000=log10(100,000)=5=log10(10)=1
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.
Answeridf(jaguar)idf(a)=log1043≈−0.125=log1033=0
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.
The dimensions are terms. The value of each component is a term weight. A document is Di=(di1,di2,…,dit). The query is Q=(q1,q2,…,qt).
The full collection is a matrix of term weights. The documents are the rows. The terms are the columns.
The match of a document and a query is the similarity of their vectors. The cosine measures this similarity.
the number of terms in the vocabulary (the number of dimensions)
j
the index of a vocabulary term
dj
the weight of term j in document D, for example its tf-idf
qj
the weight of term j in query Q
∑jdjqj
the dot product of the two vectors
∑jdj2,∑jqj2
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
1
The vectors point in the same direction
0
The vectors have nothing in common (they are perpendicular)
−1
The 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.
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), D2=(0.9,0.4,0.2), Q=(1.5,1.0,0).
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).
Advantages
Disadvantages
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?
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, 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).
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)
Where
D
the document (its representation)
R,NR
the classes “relevant” and “non-relevant” (for the current query)
P(R∣D)
the probability that D is relevant, given the content of D
P(NR∣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)P(D∣R)P(R)
Where
P(D∣R)
the probability of a document like D in the set of relevant documents
P(R)
the prior probability of relevance (before you examine 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) adjusts the answer for how common relevance is. The division by P(D) normalises it. The same change applies to P(NR∣D).
Apply Bayes' rule to the two sides of the decision rule. Then change the order of the terms. The P(D) terms cancel. The result is: retrieve D if
likelihood ratioP(D∣NR)P(D∣R)>P(R)P(NR)
Where
P(D∣R),P(D∣NR)
the probability of a document like D in the relevant set, and in the non-relevant set
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)), 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.02, P(D∣NR)=0.004, and P(R)=0.1. Thus P(NR)=0.9.
1
Likelihood ratio:
0.0040.02=5
2
Threshold:
P(R)P(NR)=0.10.9=9
3
Check with the posteriors before normalisation:
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. 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:
The system estimates the probabilities as accurately as possible. If the estimates are different from reality, the ranking can have errors.
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). The reason is that P(R) and P(NR) are the same for all documents. Thus you can ignore them for ranking. The complement gives P(D∣NR). The lecture relates it to 1−P(D∣R). Thus you can sort documents by decreasing P(D∣R). Step 1 is the same in most models. It assumes that terms occur independently of each other:
P(D∣R)=i=1∏tP(di∣R)
Where
t
the number of terms in the vocabulary
di
the feature of document D for term i. In the BIM, it is 1 if the term is present and 0 if it is absent.
P(di∣R)
the probability of that feature value in relevant documents
∏
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). Probabilistic models are different in how they do this. The first model is the Binary Independence Model.
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). The setup of the BIM:
A vector of binary features shows the terms in a document. The value di=1 if term i is present. The value di=0 if it is absent.
pi = the probability that term ioccurs (has the value 1) in a relevant document.
si = the probability that term i occurs in a non-relevant document.
Thus 1−pi is the probability that term i is absent from a relevant document. 1−si is the same probability for a non-relevant document.
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.
the probability that term i occurs in a relevant document, and in a non-relevant document
1−pi,1−si
the probability that term i 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/si. 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). 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−pi1−si⋅∏i:di=11−si1−pi. These two products cancel. Thus the value stays the same:
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=0 product together use all terms:
=depends on Di:di=1∏si(1−pi)pi(1−si)⋅over all termsi∏1−si1−pi
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.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=1logsi(1−pi)pi(1−si). The next subsection explains it.
11.2 The BIM scoring function
score(D)=i:di=1∑logsi(1−pi)pi(1−si)
Where
i:di=1
the terms that are present in document D
pi
the probability that term i occurs in a relevant document
si
the probability that term i occurs in a non-relevant document
1−pipi,1−sisi
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
The query gives our information about relevant documents. Thus assume that pi is non-zero only for query terms. Then you calculate the score only over terms that are in the document and the query.
Assume that pi is constant for all query terms, for example pi=0.5. Then the factor pi/(1−pi) equals 1.
Estimate si from the full collection. Most documents are non-relevant, thus this estimate is good: si=ni/N.
score(D)=i∈Q∩D∑logniN−ni
Where
i∈Q∩D
the terms that are in the query and in the document
N
the total number of documents in the collection
ni
the number of documents that contain term i
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.5 and si=ni/N into the BIM weight. The result is logni/N1−ni/N=logniN−ni. 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=300 documents:
wlincoln=ln300500,000−300=ln(1665.7)≈7.42
2
president occurs in ni=40,000 documents:
wpresident=ln40,000460,000=ln(11.5)≈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
When no relevance information is available, the BIM term weight is very similar to an IDF weight.
The BIM has no TF. The model uses binary features for documents. Thus it has no term frequency. BM25 adds term frequency.
PracticeIn the simplified BIM (pi=0.5, si=ni/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=2N:
log2NN−2N=log1=0
A match with this term does not change the score. With ni>2N, 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:
Term-frequency saturation
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.
the number of query terms, and the index of a query term
R
the number of documents that are judged relevant
ri
the number of judged-relevant documents that contain term i
N,ni
the number of judged documents, and the judged documents that contain term i. Without judgements, these are the collection size and the document frequency.
0.5
a smoothing constant. It keeps all counts positive.
fi
the frequency of term i in the document
qfi
the frequency of term i in the query
k1
the term-frequency saturation parameter, k1>0 (usually 1.2)
k2
the within-query saturation parameter (some authors write k3)
B
the document length normalisation factor
b
the length normalisation parameter, 0≤b≤1 (usually 0.75)
dl,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 fi 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+1. In this factor, B 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 k1 lets repeated occurrences add more score. A larger b gives a larger penalty to long documents.
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.
Parameter
Controls
Usual value
Small value
Large value
k1
Term-frequency saturation
1.2
Saturation is almost immediate. Near k1=0, only presence counts (binary, as in the BIM).
Repeated occurrences continue to add score. When k1→∞, the factor becomes the raw tf.
b
Document length normalisation
0.75
b=0: the length has no effect (B=1)
b=1: full normalisation (B=dl/avdl)
k2
Within-query saturation
often large (the Croft example uses 100)
Repeated query terms saturate quickly
The factor becomes the raw qfi
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 R, and the number of relevant documents that contain term i, ri. 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. N and ni are the counts of the documents that were judged to get R and ri. The 0.5 values are smoothing factors. If no relevance information is available (R=ri=0), N and ni become the collection size and the document frequency. Then the weight becomes:
wiRSJ=logni+0.5N−ni+0.5
Where
wiRSJ
the RSJ weight of query term i without relevance information
N
the number of documents in the collection
ni
the number of documents that contain term i
0.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 k1 controls this:
sat(fi)=k1B+fi(k1+1)fi
Where
fi
the frequency of term i in the document
k1
the saturation parameter, k1>0, usually 1.2
B
the length normalisation factor (equal to 1 for a document of average length)
k1+1
a scale factor. It makes the factor equal to 1 when fi=1 and B=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 fi increases, the fi in the denominator becomes more important. Thus the value increases quickly at first, and then it becomes flat near k1+1. High k1: saturation occurs only at high frequencies. Thus fi continues to add much score. Low k1: more occurrences add less and less, very quickly. At k1=0, the factor is 1 for each fi>0. This is the binary view of the BIM. The usual value is k1=1.2. Then the upper limit is 2.2.
Normalised saturation fi/(k1+fi) against term frequency, for four values of k1. This is the saturation factor divided by its upper limit k1+1, for a document of average length. With a small k1, the curve becomes flat almost immediately. With a large k1, repeated occurrences continue to add score.
12.4 Component 3: document length normalisation
B gives a soft normalisation of the document length. The saturation factor uses B to normalise the term frequency fi:
B=(1−b)+b⋅avdldl,0≤b≤1
Where
B
the length normalisation factor. The saturation denominator multiplies it by k1.
b
the parameter that controls the effect of the length, usually 0.75
dl
the length of the document that you score
avdl
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 wordsB is a mix of 1 (length has no effect) and dl/avdl (the full relative length). b is the weight of the mix. A document with exactly the average length always gets B=1. A longer document gets B>1. This makes the saturation denominator larger, thus each occurrence has less value. A shorter document gets B<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 b lets the system choose between these two cases.
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+qfi(k2+1)qfi
Where
qfi
the number of times that term i occurs in the query
k2
the within-query saturation constant (some authors write k3)
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=1), the factor is exactly 1 for each k2. Thus it has no effect on short queries. A larger k2 lets repeated query terms count almost linearly. A smaller k2 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×avdl. N=500,000. “president” occurs in n1=40,000 documents (a common term). “lincoln” occurs in n2=300 documents (a discriminative term). No relevance information is available. k1=1.2 and b=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):
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
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:
Why does (15, 0) get a lower score than (0, 25)? The term frequency is lower. Also, the IDF-like weight of “president” (2.44) is much lower than the weight of “lincoln” (7.42). The reason is that lincoln is much more discriminative.
Why do more matches of “president” add so little? From (1, 25) to (15, 25), the score increases only from 18.2 to 20.66. “president” has a low IDF. Also, the saturation function decreases the effect of more occurrences.
Why do more matches of “lincoln” add much? From (15, 1) to (15, 25), the score increases from 12.74 to 20.66. Fewer documents contain lincoln. Thus lincoln is more discriminative (high IDF). BM25 multiplies its saturated tf by a large weight.
Worked example 13How k₁ and b change the saturation factor
Illustrative values. This example examines only the saturation factor k1B+f(k1+1)f.
1
Change k1 for a document of average length (B=1). With f=1, the factor is k1+1k1+1=1 for each 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
Change 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 controls only the value of the later occurrences. Ten occurrences have the value of 1.18 to 3.08 first occurrences. b controls how much the same count decreases in long documents and increases in short documents.
PracticeWhat does BM25 become when k1=0? What does it become when b=0 and k1 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=0, the factor is fifi=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=0 (B=1) and k1→∞, k1+fi(k1+1)fi→fi. Thus BM25 becomes ∑tf×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×avdl. D_long has dl=3×avdl. k1=1.2. Which document gets the higher score for “lincoln” at b=0.75? 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 gets the higher score. At b=0, the two documents have B=1. The factor is 5.28.8=1.69 for the two documents. The length has no effect, and the scores are equal.
13. Summary and study checklist
Model
Representation
Scoring idea
Ranking?
Main limitation
Boolean
Binary term presence
Satisfy the Boolean expression (set retrieval)
No (set only)
No partial matching, no ranking. Only expert users write good queries.
+ CLM
Binary
Sort the matching documents by the number of matched clauses or terms
Yes
The document must still satisfy the full Boolean query
TF
Term counts (bag of words)
∑if(qi,D)
Yes
All terms have the same importance. Long documents get an advantage.
IDF
Collection statistics
∑ilog1+niN
Yes
Ignores the frequency in the document
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 the word order.
BIM
Binary features
∑i∈Q∩Dlogsi(1−pi)pi(1−si). This becomes an IDF-like weight.
Yes
No term frequency
BM25
Counts, lengths, optional relevance information
RSJ weight (≈ IDF) × saturated tf × query factor
Yes
It 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.
The main line of this week: two groups of term-based models that join 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). With pi=0.5,si=ni/N, it 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 give its two components. Put term-based models in the cost table. Explain O(|d|) and O(1).
Compare retrieval models and reranking models. Draw the cascade.
Write a query and documents as binary vectors. Calculate the overlap score.
Find the results of Boolean queries with AND, OR and NOT on an incidence matrix. Give the advantages, the disadvantages and the two basic problems of the model.
Sort documents with coordination level matching. Remember that the Boolean query still filters the documents.
Name the operators in a professional (PubMed) Boolean query: wildcard, explicit stemming, grouping, sub-grouping, adjacency, field restriction, MeSH heading and MeSH explosion.
Calculate TF, IDF and TF-IDF scores by hand. Explain why IDF is better than a stoplist.
Calculate a cosine similarity. Explain the function of the denominator.
Use Bayes' rule to get the likelihood-ratio decision rule. Give the PRP and its two assumptions. Name iPRP and qPRP.
Follow the BIM derivation. Show how pi=0.5 and si=ni/N give an IDF-like weight. Explain why the BIM has no tf.
Explain each BM25 component. Predict the change in the score when k1, b, dl or ni change. Explain the president/lincoln example.
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. It gives the derivation from the BIM to BM25 and the president/lincoln example.