Lecture 2: Retrieval Models
Background reading: Zhai - Chapter 6 Retrieval_Models
Van Rijsbergen, 1976:
Intellectually it is possible for a human to establish the relevance of a document to a query. For a computer to do this we need to construct a model within which relevance decisions can be quantified. It is interesting to note that most research in information retrieval can be shown to have been concerned with different aspect of such a model (my emphasis)
This refers to the concept of an information retrieval model.
Q: What is an information retrieval model?
All models are wrong; but some are useful (Box, quote). (I'm thinking of an addition: but models that are true are more useful; i.e. are true models usually more useful than false models?)
Each retrieval model makes simplified assumptions. We should make these assumptions explicit and test their validity.
But proving the effectiveness of a model, given its assumptions, is very hard, because we are trying to formalize a complex human activity. In practice, we use experimental setups to validate our chosen approach.
Q: Why is it hard (or even: impossible) to prove the validity of an information retrieval model?
Vector Space Model
Basic assumption: a document is relevant for a query when there is a similarity between query and document.
Imagine an n-dimensional space where:
- Each dimension corresponds to a term from the vocabulary
- Represent documents as vectors consisting of term magnitudes
We need to define:
- What is a concept (or more sloppy, a "term") in the vector space?
- Words, phrases, n-grams?
- In this case: a word.
- Define the vector representation of the documents
- Define a similarity function between a query and a document vector
The vector space model uses a bag-of-words representation:
- No word order
- No markup
- No decompounding
- So no voetbalstadium -> voetbal / stadium -> voet/bal/stadium.
In practice we also do:
- Stop word removal
- Potentially stemming
Q: What's the basic relevance assumption of a Vector Space Model?
Naive VSM
A simple instantiation would be to use a bit-vector representation for a document and query.
The vector is 1 if a word is present, 0 otherwise.
The similarity function can then simply be the dot product of vectors q and d, summing the results. That makes sense: we only have 1 when a term is present in both. So then this is basically a way of counting how many terms occur in both.
An obvious problem of this instantiation is that it does not take word frequencies into account at all.
For "q: Apple Phone", "d2: Apple Phone Apple" and "d3: Phone Samsung Phone Phone Apple Samsung" have the same score.
VSM with TF
A first improvement is therefore to take term frequency into account, and plug that number into the vector instead.
Downsides are known: very sensitive to spam / stopwords / common uninteresting words.
To counter this, arbitrary attempts can be made, e.g. a threshold as a cutoff for frequent terms.
VSM with TF*IDF
We should treat matches on non-frequent terms as more valuable than ones on frequent terms, without disregarding the latter altogether. The natural solution is to correlate a term's matching value with its collection frequency. (Karen Spark Jones, 1972)
$$IDF(w) = log( \frac{M+1}{df(w)})$$
Where M is the total number of documents, and df(w) total number of documents containing w.
A common variant leaves the "+1" out.
Q: Explain the rationale behind the TF.IDF weighing scheme.
Q: Why is a logarithm used in the DF part of the TF.IDF formula?
Case distinction: A) When a word occurs in all documents, we have (M+1)/M -> 1, with log(1)=0. So extremely frequent terms (i.e. with high df) are heavily penalized. B) When a word is extremely rare, df=1, then with M=100.000 we have log(100.000) is 5 (assuming base 10 for simplicity here). If we wouldn't have taken the log here, then we would completely dominate the TF in TF.IDF.
"This makes sense when the term occurs so frequently that it’s unlikely to differentiate two documents’ relevance (since the term is so common)" (Zhai, Ch6. p.101).
Using the log also penalizes very frequent terms most, expressing that frequent terms should have a very low contribution in determining relevance. When it concerns a comparison between infrequent and very infrequent terms, the difference in penalization/reward is smaller, because it's OK here if TF can do its work. A simpler way to say this is: the point is not to heavily promote the most rare words.
Consolidated in TF-IDF scoring
Q: Which type of document representation is used in a Vector Space Model?
Probabilistic Models
Probability Ranking Principle:
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. (Van Rijsbergen, 1979; my emphasis)
Q: What is the difference between the main relevance assumption of a probabilistic model versus a vector space model?
In the VSM one assumes documents are equal length vectors and defines relevance as (vector) similarity. In probabilistic models you instead assume there is a random variable that expresses the relevance of a document for a user, whose probabilities we can estimate based on the data.
Q: What's the main relevance assumption of probabilistic retrieval models?
B25 model
This is a very dominant and useful model. It is a baseline that is in fact hard to beat. So it's often the starting point for development of new methods.
Derived from the Binary Independence Model (BIM).
- Have a binary random variable R {0,1} denote relevance
- We want to estimate P(R=1|d,q), where we have the query.
- Ideally we would have clicking data for each document-query pair, but we don't, so we have to estimate it.
- But we don't estimate the probability directly; instead the model orders by P(R=1|d,q)
- Cf. when sorting on posterior probabilities we don't actually have to compute the posterior; propertional to sorting on likelihood times prior.
The justification of this is probabilistic but not logical: this is not a formal model. It has been validated experimentally though.
$b \in [0,1]$ and $k \in [0, + \infty]$ are hyperparameters that need to be set experimentally. Obviously, they cannot be tuned on a test set, but on a training set/validation set pair.
Also note that the score for a query is the sum of scores for individual query terms.
You'll see that the formula contains both TF and IDF terms, but the TF term is adjusted: we have transferred TF.
Transferred TF
Regular TF has no upper bound, which leads them to dominate other terms.
In terms of information, the information gain between TF=0 and TF=1 is very big, whereas the difference between TF=1000 and TF=1001 is very little. We reflect this in an adjusted TF formula, that has a plateau:
$y=\frac{(k+1)x}{x+k}$.
The specific curve of the formula is now determined by the hyperparamter k. It's flat for k=0, and close to linear (regular TF) for a very large k.
Q: Can you explain the rationale of using the transferred term frequency (e.g. in BM25) instead of regular term frequency? And what role does hyperparameter k play here?
Document Length Normalization
Imagine a document that has all terms in our collection. This imaginary document will always be retrieved independent of the query.
Instead, we want to return documents that are focused on the topic of interest.
The applied trick is that we use the average document length as a pivot: longer documents are penalized whereas shorter documents are rewarded.
Normalizer: $$1-b + b \frac{|d|}{avdl}$$
The hyperparameter b denotes the strength of penalizing/rewarding.
Note that when $|d|=avdl$ we have 1-b+b=1, i.e. no weighing. When $|d|>avdl$, we have normalizer < 1, and else >1.
Note that the first occurrence of b is additive, but the second is multiplicative. So the larger b, the stronger the effect of the document length proportion.
Note that these ideas can also be applied in other vector space models.
In that case we get a "Pivoted length normalization VSM":
Q: Is BM25 a vector space model or a probabilistic model?
The lecture slides list BM25 as a probabilistic model, but can't it not also be seen as a VSM? Answer, Zhai 111:
In this category of models, there are many different variants. The classic prob-abilistic model has led to the BM25 retrieval function, which we discussed in the vector space model section because its form is quite similar to these types of models. (Zhai, 111)
Q: What is the rationale behind using document length normalization (for example in BM25)? And what role does hyperpameter b play?
Q: Can you identify the individual components of the BM25 retrieval model? Can you explain their rationale?
Language modeling: query likelihood
What is a language model?
A language model assigns a probability to a sequence of words drawn from some vocabulary, e.g. this can also be used for sentence completion.
Q: What's the main assumption behind the query likelihood language model?
In query likelihood, our assumption is that this probability of relevance can be approximated by the probability of a query given a document and relevance,p(q|d,R=1). Intuitively, this probability just captures the following probability:if a user likes document d, how likely would the user enter query q in order to retrieve document d? The condition part contains document d and R=1, which can be interpreted as the condition that the user likes document d. (Zhai, 111)
This probability can in theory be estimated through relevance judgements (could be based on clickthrough data or so). E.g. we can estimate this probability as the following frequency:
$$P(R=1|d,q)=\frac{ count(q,d,R=1)}{count(q,d)}$$
But, of course this approach does not work for unseen documents and unseen queries.
In this case, we approximate this probability by another probability, namely $P(q|d, R=1)$. That is, for any given document we ask how likely it is that the user would have typed this query if we assume that the document is relevant. So this is a way of circumventing needing to have relevance judgements for each document.
We essentially ask: "which of these documents is most likely the imaginary relevant document in the user’s mind when the user formulates this query?" (113). The document that assigns the highest likelihood to the query is most likely that imaginary relevant document.
We assume that the user likes the document because we have seen that the user clicked on this document, and we are interested in all these cases when a user liked this particular document and want to see what kind of queries they have used. Note that we have made an interesting assumption here: we assume that a user formulates the query based on an imaginary relevant document. If you just look at this as a conditional probability, it’s not obvious we are making this assumption. (Zhai 113)
Can I write this reasoning as such? We look for the left term $P(R=1|d,q)$, but when we just assume P(d, R=1)=1, then this is proportional to the query likelihood $P(q|d,R=1)$, which then suffices for ranking:
$$P(R=1|d,q) = \frac{ P(q | d, R=1) x P(d, R=1)}$$
The question then is how to compute $P(q|d, R=1)$, which we can factorize in various ways. But the problem still is that in this "ideal" document a query term might not occur, still leading to a zero probability.
Continued at IR-3-Retrieval_Models_II.md
Unigram and Higher Order Language Models.
Full join probability distribution: $P(t1,t2,t3)=P(t1)P(t2|t1)P(t3|t1,t2)P(t4|t1,t2,t3)$
Is often infeasible to compute.
Unigram (independence assumption between words): $P(t1,t2,t3)=P(t1)P(t2)P(t3)$
Bigram (word only dependent on previous word, independent otherwise): $P(t1,t2,t3)=P(t1)P(t2|t1)P(t3|t2)$
So in a bigram we take the directly preceding term as a second term.
An obvious issue is that multiplying probabilities leads to very small numbers that run out of memory. (So just take a log probability i.e. sum of logs)
Q: Name two main high-level types of retrieval model.
Q: What is a language model?
Q: What's the difference between BM25 and a typical language modeling approach?