JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 53

CS255 Fundamentals of Information Retrieval

Lecture 7

Probabilistic Retrieval

Krishnendu Ghosh

Department of Computer Science & Engineering

Indian Institute of Information Technology Dharwad

2 of 53

Why Probabilities in IR

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 search uncertainties?

3 of 53

Why Probabilities in IR

User

Information Need

Documents

Document

Representation

Query

Representation

How to match?

Uncertain guess of

whether document has relevant content

Understanding

of user need is

uncertain

4 of 53

Why Probabilities in IR

Classical probabilistic retrieval model

Probability ranking principle, etc.
Binary independence model (≈ Naïve Bayes text cat)
Okapi BM25

Bayesian networks for text retrieval
Language model approach to IR

An important development in 2000s IR

Probabilistic methods are one of the oldest but trending topics
Traditionally: neat ideas, but didn’t win on performance
It seems to be different now

5 of 53

Document Ranking Problem

We have a collection of documents
User issues a query
A list of documents needs to be returned
Ranking method is the core of modern IR systems:
In what order do we present documents to the user?
We want the “best” document to be first, second best second, etc.
Idea: Rank by probability of relevance of the document w.r.t. information need
P(R=1|documenti, query)

6 of 53

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.”

7 of 53

The Probability Ranking Principle (PRP)

Let x represent a document in the collection.

Let R represent relevance of a document w.r.t. given (fixed) query and let R=1 represent relevant and R=0 not relevant.

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

p(R=1), p(R=0) - prior probability of retrieving a relevant or non-relevant document at random

p(x|R=1), p(x|R=0) - probability that if a relevant (not relevant) document is retrieved, it is x.

8 of 53

The Probability Ranking Principle (PRP)

Let C1 be the cost of not retrieving a relevant document and C0 the cost of retrieval of a nonrelevant document. Then the Probability Ranking Principle says that if for a specific document d and for all documents d′ not yet retrieved

C0 · P(R = 0|d) − C1 · P(R = 1|d) ≤ C0 · P(R = 0|d′) − C1 · P(R = 1|d′)

then d is the next document to be retrieved.

9 of 53

Binary Independence Model

First, estimate how each term contributes to relevance

How do other things like term frequency and document length influence your judgments about document relevance?

Not at all in BIM
A more nuanced answer is given by BM25

Combine to find document relevance probability
Order documents by decreasing probability
Theorem: Using the PRP is optimal, in that it minimizes the loss (Bayes risk) under 1/0 loss

Provable if all probabilities correct, etc. [e.g., Ripley 1996]

10 of 53

Binary Independence Model

Queries: binary term incidence vectors
Given query q, for each document d need to compute p(R|q,d) replace with computing p(R|q,x) where x is binary term incidence vector representing d
Interested only in ranking
Will use odds and Bayes’ Rule:

11 of 53

Binary Independence Model

Using Independence Assumption:

Needs estimation

Constant for a given query

12 of 53

Binary Independence Model

Since x_i is either 0 or 1:

Assume, for all terms not occurring in the query (q_i=0)

13 of 53

Binary Independence Model

	document	relevant (R=1)	not relevant (R=0)
term present	x_i = 1	p_i	r_i
term absent	x_i = 0	(1 – p_i)	(1 – r_i)

14 of 53

Binary Independence Model

All matching terms

Non-matching query terms

All matching terms

All query terms

15 of 53

Binary Independence Model

Constant for

each query

Only quantity to be estimated

for rankings

Retrieval Status Value:

16 of 53

Binary Independence Model

All boils down to computing RSV.

The ci are log odds ratios (of contingency table a few slides back)

They function as the term weights in this model

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

17 of 53

Graphical Model for BIM – Bernoulli NB

x_i

Binary

variables

18 of 53

Binary Independence Model

Estimating RSV coefficients in theory

For each term i look at this table of document counts:

Estimates:

19 of 53

Estimation: Key Challenge

If non-relevant documents are approximated by the whole collection, then ri (prob. of occurrence in non-relevant documents for query) is n/N and

Inverse Document Frequency (IDF)

Spärck-Jones (1972)
A key, still-important term weighting concept

20 of 53

Estimation: Key Challenge

pi (probability of occurrence in relevant documents) cannot be approximated as easily
pi can be estimated in various ways:

from relevant documents if you know some

Relevance weighting can be used in a feedback loop

constant (Croft and Harper combination match) – then just get idf weighting of terms (with pi=0.5)

proportional to prob. of occurrence in collection
Greiff (SIGIR 1998) argues for 1/3 + 2/3 dfi/N

21 of 53

Collection vs Document Frequency

Collection frequency of t is the total number of occurrences of t in the collection (incl. multiples)

Document frequency is number of docs t is in

Example:

Which word is a better search term (and should get a higher weight)?

Word	Collection frequency	Document frequency
insurance	10440	3997
try	10422	8760

22 of 53

Probabilistic Relevance Feedback

Guess a preliminary probabilistic description of R=1 documents; use it to retrieve a set of documents
Interact with the user to refine the description: learn some definite members with R = 1 and R = 0
Re-estimate pi and ri on the basis of these

If i appears in Vi within set of documents V: pi = |Vi|/|V|
or, can combine new information with original guess (use Bayesian prior):

Repeat, thus generating a succession of approximations to relevant documents

23 of 53

Probabilistic Relevance Feedback

Assume that pi is constant over all xi in query and ri as before

pi = 0.5 (even odds) for any given doc

Determine guess of relevant document set:

V is fixed size set of highest ranked documents on this model

We need to improve our guesses for pi and ri, so

Use distribution 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|)

Go to 2. until converges then return ranking

24 of 53

PRP and BIM

It is possible to reasonably approximate probabilities

But either require partial relevance information or need to make do with somewhat inferior term weights

Requires restrictive assumptions:

“Relevance” of each document is independent of others

Really, it’s bad to keep on returning duplicates

Term independence
Terms not in query don’t affect the outcome
Boolean representation of documents/queries
Boolean notion of relevance

Some of these assumptions can be removed

25 of 53

Term frequency and the VSM

Right in the first lecture, we said that a page should rank higher if it mentions a word more

Perhaps modulated by things like page length

Why not in BIM? Much of early IR was designed for titles or abstracts, and not for modern full text search
We now want a model with term frequency in it
We’ll mainly look at a probabilistic model (BM25)
First, a quick summary of vector space model

26 of 53

Okapi BM25

BM25 “Best Match 25” (they had a bunch of tries!)

Developed in the context of the Okapi system
Started to be increasingly adopted by other teams during the TREC competitions
It works well

Goal: be sensitive to term frequency and document length while not adding too many parameters

(Robertson and Zaragoza 2009; Spärck Jones et al. 2000)

27 of 53

Generative model for documents

Words are drawn independently from the vocabulary using a multinomial distribution

28 of 53

Generative model for documents

Distribution of term frequencies (tf) follows a binomial distribution – approximated by a Poisson

29 of 53

Poisson distribution

The Poisson distribution models the probability of k, the number of events occurring in a fixed interval of time/space, with known average rate λ ( = cf/T), independent of the last event

Examples

Number of cars arriving at a toll booth per minute
Number of typos on a page

30 of 53

Poisson distribution

If T is large and p is small, we can approximate a binomial distribution with a Poisson where λ = Tp

Mean = Variance = λ = Tp.
Example p = 0.08, T = 20. Chance of 1 occurrence is:
Binomial

Poisson … already close

31 of 53

Poisson Distribution

Assume that term frequencies in a document (tfi) follow a Poisson distribution

“Fixed interval” implies fixed document length … think roughly constant-sized document abstracts

… will fix later

32 of 53

Poisson Distribution

33 of 53

1-Poisson Model Flaw

Is a reasonable fit for “general” words
Is a poor fit for topic-specific words
get higher p(k) than predicted too often

		Documents containing k occurrences of word (λ = 53/650)
Freq	Word	0	1	2	3	4	5	6	7	8	9	10	11	12
53	expected	599	49	2
52	based	600	48	2
53	conditions	604	39	7
55	cathexis	619	22	3	2	1	2	0	1
51	comic	642	3	0	1	0	0	0	0	0	0	1	1	2

34 of 53

Eliteness (“aboutness”)

Model term frequencies using eliteness
What is eliteness?

Hidden variable for each document-term pair, denoted as Ei for term i
Represents aboutness: a term is elite in a document if, in some sense, the document is about the concept denoted by the term
Eliteness is binary
Term occurrences depend only on eliteness…
… but eliteness depends on relevance

35 of 53

Elite terms

Text from the Wikipedia page on the NFL draft showing elite terms

The National Football League Draft is an annual event in which the National Football League (NFL) teams select eligible college football players. It serves as the league’s most common source of player recruitment. The basic design of the draft is that each team is given a position in the draft order in reverse order relative to its record …

36 of 53

Graphical model with eliteness

tf_i

Frequencies (not binary)

E_i

Binary variables

37 of 53

Retrieval Status Value

Similar to the BIM derivation, we have

where

and using eliteness, we have:

38 of 53

2-Poisson Model

The problems with the 1-Poisson model suggests fitting two Poisson distributions

In the “2-Poisson model”, the distribution is different depending on whether the term is elite or not

where π is probability that document is elite for term

but, unfortunately, we don’t know π, λ, μ

39 of 53

Parametric Plotting of RSV

40 of 53

Qualitative properties

increases monotonically with tfi

… but asymptotically approaches a maximum value as [not true for simple scaling of tf]

… with the asymptotic limit being

Weight of eliteness

41 of 53

Approximating the saturation function

Estimating parameters for the 2-Poisson model is not easy

… So approximate it with a simple parametric curve that has the same qualitative properties

42 of 53

Saturation Function

For high values of k1, increments in tfi continue to contribute significantly to the score
Contributions tail off quickly for low values of k1

43 of 53

“Early” versions of BM25

Version 1: using the saturation function

Version 2: BIM simplification to IDF

(k1+1) factor doesn’t change ranking, but makes
term score 1 when tfi = 1
Similar to tf-idf, but term scores are bounded

44 of 53

Document length normalization

Longer documents are likely to have larger tfi values

Why might documents be longer?

Verbosity: suggests observed tfi too high
Larger scope: suggests observed tfi may be right

A real document collection probably has both effects … so should apply some kind of partial normalization

45 of 53

Document length normalization

Document length:

avdl: Average document length over collection
Length normalization component

b = 1 full document length normalization
b = 0 no document length normalization

46 of 53

Document length normalization

47 of 53

Okapi BM25

Normalize tf using document length

BM25 ranking function

48 of 53

Okapi BM25

k1 controls term frequency scaling
k1 = 0 is binary model; k1 large is raw term frequency
b controls document length normalization
b = 0 is no length normalization; b = 1 is relative frequency (fully scale by document length)
Typically, k1 is set around 1.2–2 and b around 0.75
IIR sec. 11.4.3 discusses incorporating query term weighting and (pseudo) relevance feedback

49 of 53

Why is BM25 better than VSM tf-idf?

Suppose your query is [machine learning]
Suppose you have 2 documents with term counts:

doc1: learning 1024; machine 1
doc2: learning 16; machine 8

tf-idf: log2 tf * log2 (N/df)

doc1: 11 * 7 + 1 * 10 = 87
doc2: 5 * 7 + 4 * 10 = 75

BM25: k1 = 2

doc1: 7 * 3 + 10 * 1 = 31
doc2: 7 * 2.67 + 10 * 2.4 = 42.7

50 of 53

Ranking with features

Textual features
Zones: Title, author, abstract, body, anchors, …
Proximity
…

Non-textual features
File type
File age
Page rank
…

51 of 53

Ranking with zones

Straightforward idea:

Apply your favorite ranking function (BM25) to each zone separately
Combine zone scores using a weighted linear combination

But that seems to imply that the eliteness properties of different zones are different and independent of each other

…which seems unreasonable

52 of 53

Ranking with zones

Alternate idea

Assume eliteness is a term/document property shared across zones
… but the relationship between eliteness and term frequencies are zone-dependent

e.g., denser use of elite topic words in title

Consequence

First combine evidence across zones for each term
Then combine evidence across terms

53 of 53

Thank You