Information Retrieval – 2

be?

11

Number of tokens:

Number of types (without case folding):

Number of types (with case folding):

Number of lemmas (linguistics):

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

9

Lemmatization

(cid:73) Lemmatisation (or lemmatization) in linguistics, is the process

of grouping together the different inflected forms of a word so

they can be analysed as a single item. [Collins English

Dictionary]

(cid:73) e.g.

(cid:73) am, are, is → be

(cid:73) car, cars, car’s, cars’ → car

(cid:73) Lies on linguistic analysis

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

10

Stemming

(cid:73) Stemming is the process for reducing inflected (or sometimes

derived) words to their stem, base or root form.

(cid:73) In IR Stemming does not try to be linguistically correct

(cid:73) Porter’s Algorithm [1980] (cf.

http://www.tartarus.org/~martin/PorterStemmer/

(cid:73) Often used in English

(cid:73) Rule based

(cid:73) Five successive steps of reduction

(cid:73) Sample rules in one step

Example

caresses → caress

ponies → poni

caress → caress

cats → cat

Rule

sses → ss

ies → i

ss → ss

s →

Only the rule that allows to match the longest suffix is applied.

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

11

Stemming result examples

(cid:73) Sample text: Such an analysis can reveal features that are not easily

visible from the variations in the individual genes and can lead to a

picture of expression that is more biologically transparent and

accessible to interpretation

(cid:73) Lovins stemmer [1968]: such an analys can reve featur that ar not

eas vis from th vari in th individu gen and can lead to a pictur of

expres that is mor biolog transpar and acces to interpres

(cid:73) Porter stemmer [1980]: such an analysi can reveal featur that ar not

easili visibl from the variat in the individu gene and can lead to a

pictur of express that is more biolog transpar and access to interpret

(cid:73) Paice stemmer [1990]: such an analys can rev feat that are not easy

vis from the vary in the individ gen and can lead to a pict of express

that is mor biolog transp and access to interpret

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

12

Sorted Based Indexing (SBI)

IndexBySort(tokenStream)

outputFile = NewFile()

tab = NewTab()

While (tokenStream not empty) do

(token, docid) = next(tokenStream)

term = Normalize(token)

tab[tokenid] = (term, docid)

Increment tokenid

done

SortPairs(tab)

Write(tab, outputFile)

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

13

List Memory Indexing (LMI)

IndexByPostingsLists(tokenStream)

outputFile = NewFile()

dict = NewDict()

While (tokenStream not empty) do

(token, docid) = next(tokenStream)

term = Normalize(token)

If (term (cid:54)∈ dict) then

postingsList = AddToDictionary(dict, term(token))

else

postingsList = GetPostingsList(dict, term(token))

end If

AddToPostingsList(postingsList, docID(token))

done

Write(dict, postingsList, outputFile)

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

14

Block Sorted-Based Indexing (BSBI)

BSBIndexConstruction()

n = 0

While (documents) do

n = n + 1

block = ParseNextBlock()

BSBI-Invert(block)

WriteBlockToDisk(block, fn)

done

MergeBlocks(f1, . . . , fn ; fmerged)

Cf. Introduction to Information Retrieval, Chapter 4, Manning, Raghavan and Sch¨utze

[2008]

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

15

Single Pass in Memory Indexing (SPMI)

SPIMI-Invert(tokenStream)

outputFile = NewFile()

dict = NewDict()

While (free memory available) do

token = next(tokenStream)

If (term(token) (cid:54)∈ dict) then

postingsList = AddToDictionary(dict, term(token))

else

postingsList = GetPostingsList(dict, term(token))

end If

If (full(postingsList)) then

postingsList = DoublePostingsList(dict, term(token))

end If

AddToPostingsList(postingsList, docID(token))

done

sortedTerms = SortTerms(dict)

WriteBlockToDisk(sortedTerms, dict, outputFile)

Cf. Introduction to Information Retrieval, Chapter 4, Manning, Raghavan and Sch¨utze

[2008]

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

16

Dictionaries

Cf. http://en.wikipedia.org/wiki/Associative_array

pair x = (k, v ), key: k, value: v

Definition: Search(S,k), Insert(S,x), Delete(S,x)

Implementation

Search

Insert Delete

Search

Insert Delete

Worst case

Mean case

List

Sorted array

BST

AVL

Hash Table

(cid:73) BST: Binary search tree

(cid:73) AVL tree: Adelson-Velskii and Landis’ tree

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

17

Statistics on two collections

number of documents

N

Lave mean number of tokens per doc.

M

number of uniq terms

mean number of char. per token

Reuters-RCV1

806 791

222

391 523

INEX/Wikipedia

2 666 190

528

17 661 801

including spaces and punctuation

excluding spaces and punctuation

mean number of char. per uniq term

tokens

T

6.04

4.5

7.5

179 158 204

x.x

x.x

x.x

1 407 654 767

Reuters-RCV1 about 1 Gb of text, 800 000 documents

no filtering

without numbers

with case folding

30 stop words

150 stop words

with stemming

uniq terms

nb.

484 494

473 723

391 523

391 493

391 373

322 383

∆%

%T

−2

−17

−0

−0

−17

−2

−19

−19

−19

−33

non zero tf

∆%

nb.

109 971 179

100 680 242

96 969 056

83 390 443

67 001 847

63 812 300

−8

−3

−14

−30

−4

%T

−8

−12

−24

−39

−42

nb.

197 879 290

179 158 204

179 158 204

121 857 825

94 516 599

94 516 599

tokens

∆%

%T

−9

−0

−31

−47

−0

−9

−9

−38

−52

−52

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

18

Postings Lists Compression

Reuters-RCV1 1 Gb of text, 800 000 documents

(cid:73) 800 000 documents

(cid:73) 200 words per document

(cid:73) 6 characters per word

(cid:73) 100 000 000 non-zero tf

(cid:73) Collection Size: 800 000×200×6 bytes

(cid:73) Document Identifier: 20 bits

(cid:73) Postings Lists Size: 100 000 000×20/8 bytes

Encoding deltas between document identifiers

e.g. List:

becomes:

12

6

with a variable number (integer) of bytes

. . .

. . .

13

1

25

12

6

3

3

3

200 703

?

200 705

2

200 709

4

. . .

. . .

(cid:73) Most Significant Bit of a byte is a continuation bit, set to 1 for the last

byte of the encoding;

(cid:73) the low significant bits encode a part of the binary representation of the

number.

Decreasing of more than 50% with Reuters-RCV1

EMSE M. Beigbeder

Master DSC 2A

2017–18

IR

19

Ranking –. . . Scoring

Goal: Return documents with an order which fosters the most

(probably) useful/relevant to the user

(cid:73) ⇒ compute a score (for instance in [0, 1]) for each document

d for each query q

(cid:73) based on the frequency matrix (tf (t, d))

(cid:73) Doc: John is quicker than Mary.

(cid:73) Doc: Mary is quicker than John.

(cid:73) bag of words model, BOW

(cid:73) RSV (d, q) = (cid:80)

q tf (t, d)

t

∈

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

20

Weighting

(cid:73) RSV (d, q) = (cid:80)

t∈q tf (t, d)

Query: ides of march

Preponderance of term “of”

. . .

. . .

23

3

3

3

55

0

9

0

ides

of

march

. . .

Weight terms according to their importance

(cid:73) Discounting common terms

(cid:73) collection frequency (cf (t) = (cid:80)

(cid:73) document frequency (df (t) = (cid:80)

cf

10422

10440

try

insurance

df

8760

3997

e.g.

d tf (t, d))

d positive(tf (t, d)))

(cid:73) inverse document frequency : idf (t) = log( N

df (t) )

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

21

Vector Model

(cid:73) Weight of term t in document d:

w (t, d) = tf (t, d) × idf (t)

(cid:73) A document is represented by a vector

(cid:73) RSV (d, q) = (cid:80)

t

q w (t, d)

∈

∈

1

Two documents can be compared by the scalar product of their

vector (or their cosine)

(cid:73) Sim(d, d (cid:48)) = (cid:80)

T w (t, d) · w (t, d (cid:48))

t

or

cos(d, d (cid:48)) =

d

d (cid:48)

||

|| ||

||

(cid:80)

t

∈

T w (t, d) · w (t, d (cid:48))

A document and a query can be compared by the scalar product of

their vector (or their cosine)

(cid:73) RSV (d, q) = (cid:80)

t

q w (t, d) · w (t, q)

or

RSV (d, q) = cos(d, q) =

∈

1

d

||

q

||

|| ||

(cid:80)

t

∈

q w (t, d) · w (t, q)

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

22

tf Variants

(cid:73) Discounting tf

(cid:73) Usual choices:

tfl(t, d) =

(cid:26) 0

1 + log(tf (t, d))

si tf (t, d) = 0

sinon

(cid:73) tf Normalization:

tfn(t, d) = a + (1 − a)

tf (t, d)

maxt(cid:48) tf (t(cid:48), d)

(cid:73) Vector normalization: euclidean norm

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

23

tf · idf generalization

w (t, d) = F (tf ) × G (df )/L(d)

where F is an increasing function

G is a decreasing function

L is a measure of the document length

(cid:73) Choosing some tf : increasing function of the frequency of one

term in one document.

(cid:73) Choosing some measure of term inmportance (idf )

(cid:73) Choosing some normalization

(cid:73) For the document AND for the query

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

24

Different tf functions in smart and. . . other tools

To be applied to non zero tf .

C function

tfwt binary

tfwt max

tfwt aug

tfwt square

tfwt log

smart

b**

n**

m**

a**

s**

l**

frac

Singhal

tf (t,d)

maxt(cid:48) tf (t(cid:48),d)+0.00001

tf (t,d)

2 + 1

maxt(cid:48) tf (t(cid:48),d)+0.00001

definition

tfb(t, d) = 1

tfn(t, d) = tf (t, d)

tfm(t, d) =

tfa(t, d) = 1

tfs(t, d) = tf (t, d)2

tfl(t, d)

tff (t, d) = tf (t,d)

tfL(t, d) =

2

= 1 + log tf (t, d)

tf (t,d)+K (d)

1+log tf (t,d)

(cid:80)

t(cid:48) tf (t(cid:48),d)

t(cid:48) positivetf (t(cid:48),d)

(cid:80)

1+log

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

25

Different idf functions in smart

smart C function

definition

i

n

t

mg

f

p

mg

s

idfwt idf

idfwt freq

idfwt prob

idfwt s idf

idfn(t) = 1

idfi(t) = log |

D

|df (t)

D

|df (t) )

idfI (t) = log(1 + |

idff (t) = 1

df (t)

idfp(t) = log |

D

df (t)

|−

df (t)

idfP(t) = log(1 +

D

+1

df (t) )2

|

idfs(t) = (log |

maxd,t(cid:48) f (t(cid:48),d)

df (t)

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

)

26

Vector normalization

Vector −→w1 is obtained with the tf and idf functions. The vector −→w1

is normalized into vector −→w2.

smart C function

definition

w2(t, d) = w1(t, d)

w1(t,d)

normwt cos w2(t, d) =

t(cid:48) w 2

normwt sum w2(t, d) = w1(t,d)

√

(cid:80)

(cid:80)

1 (t(cid:48),d)

**n

**c

**s

**u

Singhal

t(cid:48) w1(t(cid:48),d)

(cid:80)

(slope

w1(t,d)

t(cid:48) positivetf (t(cid:48),d)+(1

slope)

·

pivot)

−

w2(t, d) =

·

Weighting schemes

xyz-x’y’z’, xyz for documents, x’y’z’ for queries.

Weighting examples: bnn-bnn mnc-btn lnu-ltc Lnu-Ltu

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

27

Algorithm

CosineScore(q)

float Scores[N] = 0

Initialize Lengths[N]

For each term t of the query do

Compute w (t, q) = F (cid:48)(tf (t, q)) × G (cid:48)(df (t))

Load the postings list for term t

For each pair (d, tf (t, d)) in the list do

Add F (tf (t, d)) × G (df (t)) × w (t, q) to Scores[d]

end For

end For

Load array Lengths

For each document d do

Divide Scores[d] by Lengths[d]

end For

Return the top K components of Scores

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

28

Matching model

Extract from the Stein et al.’s presentation at TIR 09

http://www.uni-weimar.de/medien/webis/research/workshopseries/tir-09/talks/

stein09-talk-collection-relative-representations-a-unifying-view-to-retrieval-models.pdf

EMSE M. Beigbeder

2017–18

Master DSC 2A

IR

29

RetrievalModels• Empirical modelsBOW 1975Boolean <1960FuzzySet 1983GVSM 1985LSI 1990SuffixTree 1998DivRand 2002ESA 2007CL-ESA 2008Genre 1994WebGenre 2004• Probabilistic models1960 BII1976 BIR1991 Inquery1996 Beliefnet1994 BestMatch1974 2-Poisson• Language models1999 pLSI1998 LM2000 MixtUnig2003 LDAFeature space [T] terms [C] concepts [S] special RSV foundation [!] sim. ["] relevance [#] generation Collection [$] open [%] closed Ext. knowledge [!] user feedback [+] collection[T ! $][T ! $][T ! $][T ! %][C ! %][S ! %][T ! %][C ! $ +][C ! $ +][S ! %][S ! %][T " % !][T " % !][T " %][T " %][T " % !][T " % !] [C # %][T # %][C # %][C # %]1960197020102000199019802005 12Stein@TIR[∧]31.08.09