程序代写代做代考 AI Bayesian scheme COMP6714: Informa2on Retrieval & Web Search

COMP6714: Informa2on Retrieval & Web Search

Introduc*on to

Informa(on Retrieval

Lecture 9: Probabilis*c Model & Language Model

1

COMP6714: Informa2on Retrieval & Web Search

Recap of the last lecture
§  Improving search results

§  Especially for high recall. E.g., searching for aircra? so it
matches with plane; thermodynamic with heat

§  Op*ons for improving results…
§  Global methods

§  Query expansion
§  Thesauri
§  Automa*c thesaurus genera*on

§  Global indirect relevance feedback
§  Local methods

§  Relevance feedback
§  Pseudo relevance feedback

2

COMP6714: Informa2on Retrieval & Web Search

Probabilis*c relevance feedback
§  Rather than reweigh*ng in a vector space…
§  If user has told us some relevant and some irrelevant
documents, then we can proceed to build a
probabilis*c classifier, such as a Naive Bayes model:
§  P(tk|R) = |Drk| / |Dr|
§  P(tk|NR) = |Dnrk| / |Dnr|

§  tk is a term; Dr is the set of known relevant documents; Drk is the
subset that contain tk; Dnr is the set of known irrelevant
documents; Dnrk is the subset that contain tk.

3

COMP6714: Informa2on Retrieval & Web Search

Why probabili*es in IR?

User
Information Need

Documents
Document

Representation

Query
Representation

How to match?

In traditional IR systems, matching between each document and
query is attempted in a semantically imprecise space of index terms.

Probabilities provide a principled foundation for uncertain reasoning
.
Can we use probabilities to quantify our uncertainties?

Uncertain guess of
whether document
has relevant content

Understanding
of user need is
uncertain

4

COMP6714: Informa2on Retrieval & Web Search

Probabilis*c IR topics

§  Classical probabilis*c retrieval model
§  Probability ranking principle, etc.

§  (Naïve) Bayesian Text Categoriza*on
§  Bayesian networks for text retrieval
§  Language model approach to IR

§  An important emphasis in recent work

§  Probabilis2c methods are one of the oldest but also
one of the currently hoGest topics in IR.
§  Tradi2onally: neat ideas, but they’ve never won on
performance. It may be different now.

5

COMP6714: Informa2on Retrieval & Web Search

The document ranking problem
n We have a collec*on of documents
n User issues a query
n A list of documents needs to be returned
n Ranking method is core of an IR system:

n In what order do we present documents to the user?
n We want the “best” document to be first, second best
second, etc….

n Idea: Rank by probability of relevance of the
document w.r.t. informa(on need
n P(relevant|documenti, query)

6

COMP6714: Informa2on Retrieval & Web Search

Recall a few probability basics
§  For events a and b:
§  Bayes’ Rule

§  Odds:

∑ =
==

=

==∩=

aax
xpxbp

apabp
bp
apabp

bap

apabpbpbap
apabpbpbapbapbap

,
)()|(

)()|(
)(
)()|(

)|(

)()|()()|(
)()|()()|()(),(

)(1
)(

)(
)(

)(
ap
ap

ap
ap

aO
−

==

Posterior

Prior

7

COMP6714: Informa2on Retrieval & Web Search

The Probability Ranking Principle

“If a reference retrieval system’s response to each request is a
ranking of the documents in the collec*on in order of decreasing
probability of relevance to the user who submiged the request,
where the probabili*es are es*mated as accurately as possible on
the basis of whatever data have been made available to the system
for this purpose, the overall effec2veness of the system to its user
will be the best that is obtainable on the basis of those data.”

§  [1960s/1970s] S. Robertson, W.S. Cooper, M.E. Maron;
van Rijsbergen (1979:113); Manning & Schütze (1999:538)

8

COMP6714: Informa2on Retrieval & Web Search

Probability Ranking Principle

Let x be a document in the collection.
Let R represent relevance of a document w.r.t. given (fixed)
query and let NR represent non-relevance.

)(
)()|(

)|(

)(
)()|(

)|(

xp
NRpNRxp

xNRp

xp
RpRxp

xRp

=

=

p(x|R), p(x|NR) – probability that if a relevant (non-relevant)
document is retrieved, it is x.

Need to find p(R|x) – probability that a document x is relevant.

p(R),p(NR) – prior probability
of retrieving a (non) relevant
document

1)|()|( =+ xNRpxRp

R={0,1} vs. NR/R

9

COMP6714: Informa2on Retrieval & Web Search

Probability Ranking Principle (PRP)
§  Simple case: no selec*on costs or other u*lity
concerns that would differen*ally weight errors

§  Bayes’ Op*mal Decision Rule
§  x is relevant iff p(R|x) > p(NR|x)

§  PRP in ac*on: Rank all documents by p(R|x)

§  Theorem:
§  Using the PRP is op*mal, in that it minimizes the loss
(Bayes risk) under 1/0 loss

§  Provable if all probabili*es correct, etc. [e.g., Ripley 1996]

10

COMP6714: Informa2on Retrieval & Web Search

Probability Ranking Principle

§  More complex case: retrieval costs.
§  Let d be a document
§  C – cost of retrieval of relevant document
§  C’ – cost of retrieval of non-relevant document

§  Probability Ranking Principle: if

for all d’ not yet retrieved, then d is the next
document to be retrieved

§  We won’t further consider loss/u(lity from now
on

�

C ⋅ p(R | d) + ′ C ⋅ (1− p(R | d)) ≤ C ⋅ p(R | ′ d ) + ′ C ⋅ (1− p(R | ′ d ))

11

COMP6714: Informa2on Retrieval & Web Search

Probability Ranking Principle
§  How do we compute all those probabili*es?

§  Do not know exact probabili*es, have to use es*mates
§  Binary Independence Retrieval (BIR) – which we
discuss later today – is the simplest model

§  Ques*onable assump*ons
§  “Relevance” of each document is independent of
relevance of other documents.
§  Really, it’s bad to keep on returning duplicates

§  Boolean model of relevance
§  That one has a single step informa*on need

§  Seeing a range of results might let user refine query

12

COMP6714: Informa2on Retrieval & Web Search

Probabilis*c Retrieval Strategy

§  Es*mate how terms contribute to relevance
§  How do things like u, df, and length influence your
judgments about document relevance?
§  One answer is the Okapi formulae (S. Robertson)

§  Combine to find document relevance probability

§  Order documents by decreasing probability

13

COMP6714: Informa2on Retrieval & Web Search

Probabilis*c Ranking

Basic concept:

“For a given query, if we know some documents that are
relevant, terms that occur in those documents should be
given greater weighting in searching for other relevant
documents.

By making assumptions about the distribution of terms
and applying Bayes Theorem, it is possible to derive
weights theoretically.”

Van Rijsbergen

14

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model
§  Tradi*onally used in conjunc*on with PRP
§  “Binary” = Boolean: documents are represented as binary

incidence vectors of terms (cf. lecture 1):
§ 
§  iff term i is present in document x.

§  “Independence”: terms occur in documents independently
§  Different documents can be modeled as same vector

§  Bernoulli Naive Bayes model (cf. text categoriza*on!)

),,( 1 nxxx …
!
=
1=ix

15

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model
§  Queries: binary term incidence vectors
§  Given query q,

§  for each document d need to compute p(R|q,d).
§  replace with compu*ng p(R|q,x) where x is binary term
incidence vector represen*ng d Interested only in ranking

§  Will use odds and Bayes’ Rule:

)|(
),|()|(

)|(
),|()|(

),|(
),|(

),|(

qxp
qNRxpqNRp

qxp
qRxpqRp

xqNRp
xqRp

xqRO
!
!

!
!

!
!

!
==

16

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model

•  Using Independence Assumption:

∏
=

=
n

i i

i

qNRxp
qRxp

qNRxp
qRxp

1 ),|(
),|(

),|(
),|(

!
!

),|(
),|(

)|(
)|(

),|(
),|(

),|(
qNRxp
qRxp

qNRp
qRp

xqNRp
xqRp

xqRO !
!

!
!

!
⋅==

Constant for a
given query Needs estimation

∏
=

⋅=
n

i i

i

qNRxp
qRxp

qROdqRO
1 ),|(

),|(
)|(),|(• So :

17

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model

∏
=

⋅=
n

i i

i

qNRxp
qRxp

qROdqRO
1 ),|(

),|(
)|(),|(

•  Since xi is either 0 or 1:

∏∏
== =

=
⋅

=

=
⋅=

01 ),|0(
),|0(

),|1(
),|1(

)|(),|(
ii x i

i

x i

i

qNRxp
qRxp

qNRxp
qRxp

qROdqRO

•  Let );,|1( qRxpp ii == );,|1( qNRxpr ii ==

•  Assume, for all terms not occurring in the query (qi=0) ii rp =

Then…
This can be
changed (e.g., in
relevance feedback)

18

COMP6714: Informa2on Retrieval & Web Search

All matching terms Non-matching
query terms

Binary Independence Model

All matching terms
All query terms

∏∏

∏∏

===

=
===

−

−
⋅

−

−
⋅=

−

−
⋅⋅=

11

1
01

1
1

)1(
)1(

)|(

1
1

)|(),|(

iii

i
iii

q i

i

qx ii

ii

q
x i

i

qx i

i

r
p

pr
rp

qRO

r
p

r
p

qROxqRO
!

19

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model

Constant for
each query

Only quantity to be estimated
for rankings

∏∏
=== −

−
⋅

−

−
⋅=

11 1
1

)1(
)1(

)|(),|(
iii q i

i

qx ii

ii

r
p

pr
rp

qROxqRO
!

•  Retrieval Status Value:

�

RSV = log
pi(1− ri)
ri(1− pi)xi = qi =1

∏ = log pi(1− ri)
ri(1− pi)xi = qi =1

∑

20

�

= log(odds(pi))− log(odds(ri))( )
xi = qi =1
∑ = logit(pi) − logit(ri)( )

xi = qi =1
∑

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model

•  All boils down to computing RSV.

∑∏
==== −

−
=

−

−
=

11 )1(
)1(

log
)1(
)1(

log
iiii qx ii

ii

qx ii

ii

pr
rp

pr
rp

RSV

∑
==

=
1
;

ii qx
icRSV

�

ci = log
pi(1− ri)
ri(1− pi)

= logit(pi) − logit(ri)

So, how do we compute ci’s from our data ?

21

COMP6714: Informa2on Retrieval & Web Search

Binary Independence Model
•  Estimating RSV coefficients.
•  For each term i look at this table of document counts:

S
s

pi ≈ )(
)(
SN
sn

ri
−

−
≈

)()(
)(

log),,,(
sSnNsn

sSs
sSnNKci

+−−−

−
=≈

•  Estimates:

22

Documents Relevant Non-Relevant Total

Xi = 1

Xi = 0

Total N S

n s n-s
S-s N-n-S+s N-n

N-S

However, these
estimates could
be 0.

COMP6714: Informa2on Retrieval & Web Search

Add ½ Smoothing
•  Add ½ to each of the center four cells.

�

ci ≈ K(N,n,S,s) = log
(s+1 2) (S − s+1 2)

(n − s+1 2) (N − n − S + s+1 2)

23

Documents Relevant Non-Relevant Total

Xi = 1

Xi = 0

Total N+2 S+1

n+1 s+½ n-s+½
S-s+½ N-n-S+s+½ N-n+1

N-S+1

COMP6714: Informa2on Retrieval & Web Search

Example /1

24

§  Query = {x1, x2}
§  O(R=1|D3, q)

Doc Judgment x1 x2 x3
D1 R 1 1 1

D2 R 0 0 1

D3 R 1 0 0

D4 NR 1 0 1

D5 NR 0 1 1

COMP6714: Informa2on Retrieval & Web Search

Example /2

25

§  Es*mate pi and ri

Doc Judgment x1 x2 x3
D1 R 1 1 1

D2 R 0 0 1

D3 R 1 0 0

D4 NR 1 0 1

D5 NR 0 1 1

COMP6714: Informa2on Retrieval & Web Search

Es*ma*on – key challenge
§  If non-relevant documents are approximated by
the whole collec*on, then ri (prob. of occurrence
in non-relevant documents for query) is n/N and
§  log (1– ri)/ri = log (N– n)/n ≈ log N/n = IDF!

§  pi (probability of occurrence in relevant
documents) can be es*mated in various ways:
§  from relevant documents if know some

§  Relevance weigh*ng can be used in feedback loop
§  constant (Cro} and Harper combina*on match – 0.5) –
then just get idf weigh*ng of terms

§  propor*onal to prob. of occurrence in collec*on
§  more accurately, to log of this (Greiff, SIGIR 1998)

26

in fact, u-idf can be deemed as the cross-entropy

COMP6714: Informa2on Retrieval & Web Search

27

Itera*vely es*ma*ng pi
1.  Assume that pi constant over all xi in query

§  pi = 0.5 (even odds) for any given doc
2.  Determine guess of relevant document set:

§  V is fixed size set of highest ranked documents on this
model (note: now a bit like u.idf!)

3.  We need to improve our guesses for pi and ri, so
§  Use distribu*on of xi in docs in V. Let Vi be set of

documents containing xi
§  pi = |Vi| / |V|

§  Assume if not retrieved then not relevant
§  ri = (ni – |Vi|) / (N – |V|)

4.  Go to 2. un*l converges then return ranking

op*onal

COMP6714: Informa2on Retrieval & Web Search

Probabilis*c Relevance Feedback
1.  Guess a preliminary probabilis*c descrip*on of R

and use it to retrieve a first set of documents V, as
above.

2.  Interact with the user to refine the descrip*on:
learn some definite members of R and NR

3.  Rees*mate pi and ri on the basis of these
§  Or can combine new informa*on with original guess (use

Bayesian prior):

4.  Repeat, thus genera*ng a succession of
approxima*ons to R.

κ
κ
+

+
=

||
|| )1()2(
V

pV
p iii

κ is
prior

weight

28

op*onal

COMP6714: Informa2on Retrieval & Web Search

PRP and BIR

§  Ge�ng reasonable approxima*ons of probabili*es
is possible.

§  Requires restric*ve assump*ons:
§  term independence
§  terms not in query don’t affect the outcome
§  boolean representa*on of documents/queries/
relevance

§  document relevance values are independent
§  Some of these assump*ons can be removed
§  Problem: either require par*al relevance informa*on or only can

derive somewhat inferior term weights
29

COMP6714: Informa2on Retrieval & Web Search

Okapi BM25

§  Heuris*cally extend the BIR to include informa*on
of term frequencies, document length, etc.

§  Typically,

30

�

RSVd = log
N
dft

⎛

⎝
⎜

⎞

⎠
⎟

t∈q
∑ ⋅ (k1 +1)tf t ,d

k1 (1− b) + b ⋅
Ld
Lave

⎛

⎝
⎜

⎞

⎠
⎟ + tf t ,d

⋅
(k3 +1)tf t ,q
k3 + tf t,q

idf Normalized term
freq (doc)

Normalized term
freq (query)

�

k1,k3 ∈ [1.2,2.0],b = 0.75

caps the contribu*on of R

COMP6714: Informa2on Retrieval & Web Search

Good and Bad News
§  Standard Vector Space Model

§  Empirical for the most part; success measured by results
§  Few proper*es provable

§  Probabilis*c Model Advantages
§  Based on a firm theore*cal founda*on
§  Theore*cally jus*fied op*mal ranking scheme

§  Disadvantages
§  Making the ini*al guess to get V
§  Binary word-in-doc weights (not using term frequencies)
§  Independence of terms (can be alleviated)
§  Amount of computa*on
§  Has never worked convincingly beger in prac*ce

31

COMP6714: Informa2on Retrieval & Web Search

Resources
S. E. Robertson and K. Spärck Jones. 1976. Relevance Weigh*ng of Search

Terms. Journal of the American Society for Informa2on Sciences 27(3):
129–146.

C. J. van Rijsbergen. 1979. Informa2on Retrieval. 2nd ed. London:
Bugerworths, chapter 6. [Most details of math] hgp://
www.dcs.gla.ac.uk/Keith/Preface.html

N. Fuhr. 1992. Probabilis*c Models in Informa*on Retrieval. The Computer
Journal, 35(3),243–255. [Easiest read, with BNs]

F. Crestani, M. Lalmas, C. J. van Rijsbergen, and I. Campbell. 1998. Is This
Document Relevant? … Probably: A Survey of Probabilis*c Models in
Informa*on Retrieval. ACM Compu2ng Surveys 30(4): 528–552.

hgp://www.acm.org/pubs/cita*ons/journals/surveys/1998-30-4/p528-crestani/

[Adds very ligle material that isn’t in van Rijsbergen or Fuhr ]

32

COMP6714: Informa2on Retrieval & Web Search

Resources
H.R. Turtle and W.B. Cro}. 1990. Inference Networks for Document Retrieval.

Proc. ACM SIGIR: 1-24.
E. Charniak. Bayesian nets without tears. AI Magazine 12(4): 50-63 (1991). hGp://

www.aaai.org/Library/Magazine/Vol12/12-04/vol12-04.html
D. Heckerman. 1995. A Tutorial on Learning with Bayesian Networks. Microso}

Technical Report MSR-TR-95-06
hGp://www.research.microso?.com/~heckerman/

N. Fuhr. 2000. Probabilis*c Datalog: Implemen*ng Logical Informa*on Retrieval
for Advanced Applica*ons. Journal of the American Society for Informa2on
Science 51(2): 95–110.

R. K. Belew. 2001. Finding Out About: A Cogni2ve Perspec2ve on Search Engine

Technology and the WWW. Cambridge UP 2001.

MIR 2.5.4, 2.8
33

COMP6714: Informa2on Retrieval & Web Search

LANGUAGE MODEL

34

COMP6714: Informa2on Retrieval & Web Search

Today
§  The Language Model Approach to IR

§  Basic query genera*on model
§  Alterna*ve models

35

COMP6714: Informa2on Retrieval & Web Search

Standard Probabilis*c IR

query

d1

d2

dn

…

Information
need

document collection

matching

),|( dQRP

36

COMP6714: Informa2on Retrieval & Web Search

IR based on Language Model (LM)

query

d1

d2

dn

…

Information
need

document collection

generation

)|( dMQP 1d
M

2d
M

…

nd
M§  A common search heuris*c is to use words that you expect to find in matching documents as your

query – why, I saw Sergey Brin advoca*ng that
strategy on late night TV one night in my hotel
room, so it must be good!

§  The LM approach directly exploits that idea!
§  See later slides for a more formal jus*fica*on 37

COMP6714: Informa2on Retrieval & Web Search

Formal Language (Model)

§  Tradi*onal genera*ve model: generates strings
§  Finite state machines or regular grammars, etc.

§  Example:

I wish

I wish
I wish I wish
I wish I wish I wish
I wish I wish I wish I wish
…

38

COMP6714: Informa2on Retrieval & Web Search

Stochas*c Language Models

§  Models probability of genera*ng strings in the
language (commonly all strings over alphabet ∑)

0.2 the

0.1 a

0.01 man

0.01 woman

0.03 said

0.02 likes

… …

the man likes the woman

0.2 0.01 0.02 0.2 0.01

multiply

Model M

P(s | M) = 0.00000008

s:

39

COMP6714: Informa2on Retrieval & Web Search

Stochas*c Language Models

§  Model probability of genera*ng any string

0.2 the

0.01 class

0.0001 sayst

0.0001 pleaseth

0.0001 yon

0.0005 maiden

0.01 woman

Model M1 Model M2

maiden class pleaseth yon the

0.0005 0.01 0.0001 0.0001 0.2
0.01 0.0001 0.02 0.1 0.2

P(s|M2) > P(s|M1)

0.2 the

0.0001 class

0.03 sayst

0.02 pleaseth

0.1 yon

0.01 maiden

0.0001 woman

40

COMP6714: Informa2on Retrieval & Web Search

Stochas*c Language Models

§  A sta*s*cal model for genera*ng text
§  Probability distribu*on over strings in a given language

M

P ( | M ) = P ( | M )

P ( | M, )

P ( | M, )

P ( | M, )
41

COMP6714: Informa2on Retrieval & Web Search

Unigram and higher-order models

§  Unigram Language Models

§  Bigram (generally, n-gram) Language Models

§  Other Language Models
§  Grammar-based models (PCFGs), etc.

§  Probably not the first thing to try in IR

= P ( ) P ( | ) P ( | ) P ( | )

P ( ) P ( ) P ( ) P ( )

P ( )

P ( ) P ( | ) P ( | ) P ( | )

Easy.
Effective!

42

COMP6714: Informa2on Retrieval & Web Search

Using Language Models in IR
§  Treat each document as the basis for a model (e.g.,
unigram sufficient sta*s*cs)

§  Rank document d based on P(d | q)
§  P(d | q) = P(q | d) x P(d) / P(q)

§  P(q) is the same for all documents, so ignore
§  P(d) [the prior] is o}en treated as the same for all d

§  But we could use criteria like authority, length, genre
§  P(q | d) is the probability of q given d’s model

§  Very general formal approach

43

COMP6714: Informa2on Retrieval & Web Search

The fundamental problem of LMs
§  Usually we don’t know the model M

§  But have a sample of text representa*ve of that model

§  Es*mate a language model from a sample
§  Then compute the observa*on probability

P ( | M ( ) )

M
doc query

44

COMP6714: Informa2on Retrieval & Web Search

Language Models for IR
§  Language Modeling Approaches

§  Agempt to model query genera(on process
§  Documents are ranked by the probability that a query
would be observed as a random sample from the
respec(ve document model

§  Mul*nomial approach

45

COMP6714: Informa2on Retrieval & Web Search

Retrieval based on probabilis*c LM

§  Treat the genera*on of queries as a random process.
§  Approach

§  Infer a language model for each document.
§  Es*mate the probability of genera*ng the query according
to each of these models.

§  Rank the documents according to these probabili*es.
§  Usually a unigram es*mate of words is used

§  Some work on bigrams, paralleling van Rijsbergen

46

COMP6714: Informa2on Retrieval & Web Search

Retrieval based on probabilis*c LM

§  Intui*on
§  Users …

§  Have a reasonable idea of terms that are likely to occur in
documents of interest.

§  They will choose query terms that dis*nguish these documents
from others in the collec*on.

§  Collec*on sta*s*cs …
§  Are integral parts of the language model.
§  Are not used heuris*cally as in many other approaches.

§  In theory. In prac*ce, there’s usually some wiggle room for
empirically set parameters

47

COMP6714: Informa2on Retrieval & Web Search

Query genera*on probability (1)
§  Ranking formula

§  The probability of producing the query given the language model of
document d using MLE is:

∏

∏

∈

∈

=

=

Qt d

dt

Qt
dmld

dl
tf

MtpMQp

),(

)|(ˆ)|(ˆ

Unigram assumption:
Given a particular language model, the
query terms occur independently

),( dttf

ddl

: language model of document d

: raw tf of term t in document d

: total number of tokens in document d

dM

)|()(
)|()(),(

dMQpdp
dQpdpdQp

≈

=

48

COMP6714: Informa2on Retrieval & Web Search

Insufficient data
§  Zero probability

§  May not wish to assign a probability of zero to a document
that is missing one or more of the query terms [gives
conjunc*on seman*cs]

§  General approach
§  A non-occurring term is possible, but no more likely than
would be expected by chance in the collec*on.

§  If ,

0)|( =dMtp

0),( =dttf

cs

cs
cf

Mtp td =)|(

tcf : raw count of term t in the collection
: raw collection size(total number of tokens in the collection)

49

COMP6714: Informa2on Retrieval & Web Search

Insufficient data
§  Zero probabili*es spell disaster

§  We need to smooth probabili*es
§  Discount nonzero probabili*es
§  Give some probability mass to unseen things

§  There’s a wide space of approaches to smoothing
probability distribu*ons to deal with this problem,
such as adding 1, ½ or ℇ to counts, Dirichlet priors,
discoun*ng, and interpola*on
§  [See FSNLP ch. 6 or CS224N if you want more]

§  A simple idea that works well in prac*ce is to use a
mixture between the document mul*nomial and the
collec*on mul*nomial distribu*on

50

COMP6714: Informa2on Retrieval & Web Search

Mixture model
§  Jelinek-Mercer method

§  P(w|d) = λPmle(w|Md) + (1 – λ)Pmle(w|Mc)
§  Mixes the probability from the document with the
general collec*on frequency of the word.

§  Correctly se�ng λ is very important
§  A high value of lambda makes the search
“conjunc*ve-like” – suitable for short queries

§  A low value is more suitable for long queries
§  Can tune λ to op*mize performance

§  Perhaps make it dependent on document size (cf. Dirichlet
prior or Wigen-Bell smoothing) 51

COMP6714: Informa2on Retrieval & Web Search

Basic mixture model summary
§  General formula*on of the LM for IR

§  The user has a document in mind, and generates the query
from this document.

§  The equa*on represents the probability that the
document that the user had in mind was in fact this one.

∏
∈

+−=
Qt

dMtptpdpdQp ))|()()1(()(),( λλ

collection/background language model

individual-document model

52

COMP6714: Informa2on Retrieval & Web Search

Rela*onship to idf
fqi,D=0 è query word that
does not occur in the doc

Add contribu*ons
from i:fqi,D>0

Becomes a
constant | Q, C

propor*onal to the u, inversely
propor*onal to the cf

Note here (i.e., [CMS09]) λ is
mul*plied to the background
model.

53

COMP6714: Informa2on Retrieval & Web Search

Example
§  Document collec*on (2 documents)

§  d1: Xerox reports a profit but revenue is down
§  d2: Lucent narrows quarter loss but revenue decreases
further

§  Model: MLE unigram from documents; λ = ½
§  Query: revenue down

§  P(Q|d1) = [(1/8 + 2/16)/2] x [(1/8 + 1/16)/2]
= 1/8 x 3/32 = 3/256
§  P(Q|d2) = [(1/8 + 2/16)/2] x [(0 + 1/16)/2]
= 1/8 x 1/32 = 1/256

§  Ranking: d1 > d2 54

COMP6714: Informa2on Retrieval & Web Search

Ponte and Cro} Experiments
§  Data

§  TREC topics 202-250 on TREC disks 2 and 3
§  Natural language queries consis*ng of one sentence each

§  TREC topics 51-100 on TREC disk 3 using the concept fields
§  Lists of good terms

Number: 054

Domain: International Economics