CS255 Fundamentals of Information Retrieval
Lecture 8 Language Modeling for IR
Krishnendu Ghosh
Department of Computer Science & Engineering
Indian Institute of Information Technology Dharwad
Language Models
Language Models
A language model is a function that puts a probability measure over strings drawn from some vocabulary. That is, for a language model M over an alphabet S:
Language Models
Language Models
One simple kind of language model is equivalent to a probabilistic finite automaton consisting of just a single node with a single probability distribution over producing different terms, so that ∑ t∈V P(t) = 1
Language Models
Language Models: Types
P(t1t2t3t4) = P(t1)P(t2|t1)P(t3|t1t2)P(t4|t1t2t3)
The simplest form of language model simply throws away all conditioning context, and estimates each term independently. Such a model is called a unigram language model:
Puni(t1t2t3t4) = P(t1)P(t2)P(t3)P(t4)
There are many more complex kinds of language models, such as bigram language models, which condition on the previous term
Pbi(t1t2t3t4) = P(t1)P(t2|t1)P(t3|t2)P(t4|t3)
Language Models
The original and basic method for using language models in IR is the query likelihood model. In it, we construct from each document d in the collection a language model Md. Our goal is to rank documents by P(d|q), where the probability of a document is interpreted as the likelihood that it is relevant to the query.
P(d|q) = P(q|d)P(d)/P(q)
P(q) is the same for all documents, and so can be ignored.
The prior probability of a document P(d) is often treated as uniform across all d and so it can also be ignored.
Language Models
Kq is the multinomial coefficient for the query q
Language Models
For retrieval based on a language model (henceforth LM), we treat the generation of queries as a random process. The approach is to:
The intuition of the basic model is that the user has a prototype document in mind, and generates a query based on words that appear in this document.
Language Models
where Md is the language model of document d, tft,d is the (raw) term frequency of term t in document d, and Ld is the number of tokens in document d.
Language Models
The general approach is that a non-occurring term should be possible in a query, but its probability should be somewhat close to but no more likely than would be expected by chance from the whole collection. That is, if tft,d = 0 then
P (t|Md) ≤ cft/T
where cft is the raw count of the term in the collection, and T is the raw size (number of tokens) of the entire collection.
Language Models
A simple idea that works well in practice is to use a mixture between a document-specific multinomial distribution and a multinomial distribution estimated from the entire collection:
where 0 < λ < 1 and Mc is a language model built from the entire document collection.
This mixes the probability from the document with the general collection frequency of the word. Such a model is referred to as a linear interpolation language model.
Language Models
An alternative is to use a language model built from the whole collection as a prior distribution in a Bayesian updating process:
Language Models
To summarize, the retrieval ranking for a query q under the basic LM for IR we have been considering is given by:
This equation captures the probability that the document that the user had in mind was in fact d.
Language Models
Three ways of developing the language modeling approach:
(a) query likelihood, (b) document likelihood, and (c) model comparison:
Extended Language Models
Rather than looking at the probability of a document language model Md generating the query, you can look at the probability of a query language model Mq generating the document.
The main reason that doing things in this direction and creating a document likelihood model is less appealing is that there is much less text available to estimate a language model based on the query text, and so the model will be worse estimated, and will have to depend more on being smoothed with some other language model.
Extended Language Models
Rather than directly generating in either direction, we can make a language model from both the document and query, and then ask how different these two language models are from each other.
For instance, one way to model the risk of returning a document d as relevant to a query q is to use the Kullback-Leibler (KL) divergence between their respective language models:
Extended Language Models
A translation model lets you generate query words not in a document by translation to alternate terms with similar meaning. This also provides a basis for performing cross-language IR. We assume that the translation model can be represented by a conditional probability distribution T(·|·) between vocabulary terms. The form of the translation query generation model is then:
The term P(v|Md) is the basic document language model, and the term T(t|v) performs translation. This model is clearly more computationally intensive and we need to build a translation model.
Thank You