<ul><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>DRAFT! April 15, 2007 Cambridge University Press. Feedback welcome. 181</p><p>12 Language models for informationretrieval</p><p>In the traditional probabilistic approach to IR, the user has an informationneed, and determines a query q which is run against documents d, and wetry to determine the probability of relevance P(R q, d). The original languagemodeling approach bypasses overtly modeling the concept of relevance. Itinstead builds a probabilistic language model Md from each document d, andranks documents based on the probability of the model generating the query:P(q Md).</p><p>A common suggestion to users for coming up with good queries is to thinkof words that would likely appear in a relevant document, and to use thosewords as your query. The language modeling approach to IR directly modelsthat idea: a document is a good match to a query if the document modelis likely to generate the query, which will in turn happen if the documentcontains the query words often.</p><p>What do we mean by a document model generating a query? A traditionalgenerative model of language of the kind familiar from formal language the-GENERATIVE MODELory can be used either to recognize or to generate strings. For example, thefinite automaton shown in Figure 12.1 can generate strings that include theexamples shown. The full set of strings that can be generated is called thelanguage of the automaton.</p><p>If instead each node has a probability distribution over generating differ-ent words, we have a language model. A (stochastic or probabilistic) languageLANGUAGE MODELmodel is a function that puts a probability measure over strings drawn fromsome vocabulary. One simple kind of language model is equivalent to a prob-abilistic finite automaton consisting of just a single node with a single prob-ability distribution of producing different words, as shown in Figure 12.2,coupled with a probability of stopping when in a finish state. Such a modelplaces a probability distribution over any sequence of words. By construc-tion, it also provides a model for generating text according to its distribution.To find the probability of a word sequence, we just multiply the probabilities</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>182 12 Language models for information retrieval</p><p>I wish</p><p>I wishI wish I wishI wish I wish I wishI wish I wish I wish I wish I wish I wish. . .</p><p>*wish I wish</p><p> Figure 12.1 A simple finite automaton and some of the strings in the languagethat it generates. shows the start state of the automaton and a double circle indi-cates a (possible) finishing state.</p><p>the 0.2a 0.1frog 0.01toad 0.01said 0.03likes 0.02that 0.04</p><p> Figure 12.2 A one-state finite automaton that acts as a unigram language modeltogether with a partial specification of the state emission probabilities.</p><p>which it gives to each word in the sequence. For example,</p><p>P(frog said that toad likes frog) = 0.01 0.03 0.04 0.02 0.01(12.1)</p><p>= 0.0000000024</p><p>Here we omit the probability of stopping after frog. An explicit stop proba-bility is needed for the finite automaton to generate and give probabilities tofinite strings, but we will in general omit mention of it, since, if fixed, it doesnot alter the ranking of documents.</p><p>Suppose, now, that we have two language models M1 and M2, shownpartially in Figure 12.3. Each gives a probability estimate to a sequence ofwords, as shown in the example. The language model that gives the higherprobability to the sequence of words is more likely to have generated theword sequence. For the sequence shown, we get:</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>183</p><p>Model M1 Model M2the 0.2 the 0.15a 0.1 a 0.12frog 0.01 frog 0.0002toad 0.01 toad 0.0001said 0.03 said 0.03likes 0.02 likes 0.04that 0.04 that 0.04dog 0.005 dog 0.01cat 0.003 cat 0.015monkey 0.001 monkey 0.002. . . . . . . . . . . .</p><p> Figure 12.3 Partial specification of two unigram language models.</p><p>(12.2) s frog said that toad likes that dogM1 0.01 0.03 0.04 0.01 0.02 0.04 0.005M2 0.0002 0.03 0.04 0.0001 0.04 0.04 0.01</p><p>P(s M1) = 0.00000000000048P(s M2) = 0.000000000000000384</p><p>and we see that P(s M1) &gt; P(s M2).How do people build probabilities over word sequences? We can always</p><p>use the chain rule to decompose the probability of a sequence of events intothe probability of each successive events conditioned on earlier events:</p><p>P(w1w2w3w4) = P(w1)P(w2 w1)P(w3 w1w2)P(w4 w1w2w3)</p><p>The simplest form of language model simply throws away all conditioningcontext, and estimates each word independently. Such a model is called aunigram language model:UNIGRAM LANGUAGE</p><p>MODEL</p><p>Puni(w1w2w3w4) = P(w1)P(w2)P(w3)P(w4)</p><p>Under this model the order of words is irrelevant, and so such models aresometimes called bag of words models as discussed in Chapter 6 (page 90).There are many more complex kinds of language models, such as bigramlanguage models, which condition on the previous word,</p><p>Pbi(w1w2w3w4) = P(w1)P(w2 w1)P(w3 w2)P(w4 w3)</p><p>and even more complex grammar-based language models such as probabilis-tic context-free grammars. However, most language-modeling work in IR</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>184 12 Language models for information retrieval</p><p>has used unigram language models, and IR is probably not the most produc-tive place to try using complex language models, since IR does not directlydepend on the structure of sentences to the extent that other tasks like speechrecognition do. Moreover, since, as we shall see, IR language models are fre-quently estimated from a single document, there is often not enough trainingdata and losses from sparseness outweigh any gains from richer models.</p><p>The fundamental problem in designing language models is that we gen-erally do not know what exactly we should use as the model Md. However,we do generally have a sample of text that is representative of that model.This problem makes a lot of sense in the original, primary uses of languagemodels. For example, in speech recognition, we have a training sample oftext, but we have to expect that in the future, users will use different wordsand in different sequences, which we have never observed before, and so themodel has to generalize beyond the observed data to allow unknown wordsand sequences. This interpretation is not so clear in the IR case, where a doc-ument is finite and usually fixed. However, we pretend that the documentd is only a representative sample of text drawn from a model distribution,we estimate a language model from this sample, use that model to calculatethe probability of observing any word sequence, and finally rank documentsaccording to their probability of generating the query.</p><p>12.1 The Query Likelihood Model</p><p>12.1.1 Using Query Likelihood Language Models in IR</p><p>Language modeling is a quite general formal approach to IR, with many vari-ant realizations. The original and basic method for using language modelsin IR is the query likelihood model. In it, we construct from each document dQUERY LIKELIHOOD</p><p>MODEL in the collection a language model Md. Our goal is to rank documents byP(d q), where the probability of a document is interpreted as the likelihoodthat it is relevant to the query. Using Bayes rule, we have:</p><p>P(d q) = P(q d)P(d)/P(q)</p><p>P(q) is the same for all documents, and so can be ignored. The prior P(d)is often treated as uniform across all d and so it can also be ignored, but wecould implement a genuine prior which could include criteria like author-ity, length, genre, newness, and number of previous people who have readthe document. But, given these simplifications, we return results ranked bysimply P(q d), the probability of the query q given by the language model de-rived from d. The Language Modeling approach thus attempts to model thequery generation process: Documents are ranked by the probability that aquery would be observed as a random sample from the respective documentmodel.</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>12.1 The Query Likelihood Model 185</p><p>The most common way to do this is using the multinomial unigram lan-guage model, which is equivalent to a multinomial Naive Bayes model (page 205),where the documents are the classes, each treated in the estimation as a sep-arate language. Under this model, we have that:</p><p>P(q Md) = wV</p><p>P(w Md)c(w)(12.3)</p><p>Usually a unigram estimate of words is used in IR. There is some work on bi-grams, paralleling the discussion of van Rijsbergen in Chapter 11 (page 176),but it hasnt been found very necessary. While modeling term cooccurrenceshould improve estimates somewhat, IR is different to tasks like speech recog-nition: word order and sentence structure are not very necessary to modelingthe topical content of documents.</p><p>For retrieval based on a probabilistic language model, we treat the gener-ation of queries as a random process. The approach is to</p><p>1. Infer a language model for each document.</p><p>2. Estimate the probability of generating the query according to each of thesemodels.</p><p>3. Rank the documents according to these probabilities.</p><p>The intuition is that the user has a prototype document in mind, and gen-erates a query based on words that appear in this document. Often, usershave a reasonable idea of terms that are likely to occur in documents of in-terest and they will choose query terms that distinguish these documentsfrom others in the collection. Collection statistics are an integral part of thelanguage model, rather than being used heuristically as in many other ap-proaches.</p><p>12.1.2 Estimating the query generation probability</p><p>In this section we describe how to estimate P(q Md). The probability of pro-ducing the query given the language model Md of document d using maxi-mum likelihood estimation (MLE) and given the unigram assumption is:</p><p>P(q Md) = tq</p><p>Pmle(t Md) = tq</p><p>t ft,ddld</p><p>(12.4)</p><p>where Md is the language model of document d, t ft,d is the (raw) term fre-quency of term t in document d, and dld is the number of tokens in documentd.</p><p>The classic problem with such models is one of estimation (the is usedabove to stress that the model is estimated). In particular, some words will</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>186 12 Language models for information retrieval</p><p>not have appeared in the document at all, but are possible words for the in-formation need, which the user may have used in the query. If we estimateP(t Md) = 0 for a term missing from a document d, then we get a strict con-junctive semantics: documents will only give a query non-zero probability ifall of the query terms appear in the document. This may or may not be unde-sirable: it is partly a human-computer interface issue: vector space systemshave generally preferred more lenient matching, though recent web searchdevelopments have tended more in the direction of doing searches with suchconjunctive semantics. But regardless of ones approach here, there is a moregeneral problem of estimation: occurring words are also badly estimated; inparticular, the probability of words occurring once in the document is nor-mally overestimated, since there one occurrence was partly by chance.</p><p>This problem of insufficient data and a zero probability preventing anynon-zero match score for a document can spell disaster. We need to smoothprobabilities: to discount non-zero probabilities and to give some probabil-ity mass to unseen things. Theres a wide space of approaches to smoothingprobability distributions to deal with this problem, such as adding a num-ber (1, 1/2, or a small ) to counts and renormalizing, discounting, Dirichletpriors and interpolation methods. A simple idea that works well in practiceis to use a mixture between the document multinomial and the collectionmultinomial distribution.</p><p>The general approach is that a non-occurring term is possible in a query,but no more likely than would be expected by chance from the whole collec-tion. That is, if t ft,d = 0 then</p><p>P(t Md) c ft/cs</p><p>where c ft is the raw count of the term in the collection, and cs is the raw size(number of tokens) of the entire collection. We can guarantee this by mixingtogether a document-specific model with a whole collection model:</p><p>P(w d) = Pmle(w Md) + (1 )Pmle(w Mc)(12.5)</p><p>where 0 &lt; &lt; 1 and Mc is a language model built from the entire doc-ument collection. This mixes the probability from the document with thegeneral collection frequency of the word. Correctly setting is importantto the good performance of this model. A high value of lambda makes thesearch conjunctive-like suitable for short queries. A low value is moresuitable for long queries. One can tune to optimize performance, includingnot having it be constant but a function of document size.</p><p>So, the general formulation of the basic LM for IR is:</p><p>P(q d) P(d) tq</p><p>((1 )P(t Mc) + P(t Md))</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>12.2 Ponte and Crofts Experiments 187</p><p>The equation represents the probability that the document that the user hadin mind was in fact this one.</p><p>Example 12.1: Suppose the document collection contains two documents:</p><p> d1: Xyz reports a profit but revenue is down</p><p> d2: Qrs narrows quarter loss but revenue decreases further</p><p>The model will be MLE unigram models from the documents and collection,mixed with = 1/2.</p><p>Suppose the query is revenue down. Then:</p><p>P(q d1) = [(1/8 + 2/16)/2] [(1/8 + 1/16)/2](12.6)</p><p>= 1/8 3/32 = 3/256</p><p>P(q d2) = [(1/8 + 2/16)/2] [(0/8 + 1/16)/2]</p><p>= 1/8 1/32 = 1/256</p><p>So, the ranking is d1 &gt; d2.</p><p>12.2 Ponte and Crofts Experiments</p><p>Ponte and Croft (1998) present the first experiments on the language model-ing approach to information retrieval. Their basic approach where each doc-ument defines a language model is the model that we have presented untilnow. However, we have presented an approach where the language modelis a mixture of two multinomials, much as in Miller et al. (1999), Hiemstra(2000) rather than Ponte and Crofts multivariate Bernoulli model. The useof multinomials has been standard in most subsequent work in the LM ap-proach and evidence from text categorization (see Chapter 13) suggests thatit is superior. Ponte and Croft argued strongly for the effectiveness of theterm weights that come from the language modeling approach over tradi-tional tf-idf weights. We present a subset of their results in Figure 12.4 wherethey compare tf-idf to language modeling by evaluating TREC topics 202250 evaluated on TREC disks 2 and 3. The queries are sentence length naturallanguage queries. The language modeling approach yields significantly bet-ter results than their baseline tf-idf based term weighting approach. Andindeed the gains shown here have been extended in subsequent work.</p><p>12.3 Language modeling versus other approaches in IR</p><p>The language modeling approach provides a novel way of looking at theproblem of text retrieval, which links it with a lot of recent work in speech</p></li><li><p>Preliminary draft (c)2007 Cambridge UP</p><p>188 12 Language models for information retrieval</p><p>PrecisionRec. tf-idf LM %chg0.0 0.7439 0.7590 +2.00.1 0.4521 0.4910 +8.60.2 0.3514 0.4045 +15.1 *0.3 0.2761 0.3342 +21.0 *0.4 0.2093 0.2572 +22.9 *0.5 0.1558 0.2061 +32.3 *0.6 0.1024 0.1405 +37..</p></li></ul>