Information Retrieval – 1

Michel Beigbeder

September, 24th 2020

EMSE M. Beigbeder

2020–21

Master DSC 2A

Outline

Introduction

Deﬁnition

Diﬃculties

Data Retrieval vs. Information Retrieval

An example

IR model

Index construction

Intersection

An example of a boolean system

Wishes

Glossary

EMSE M. Beigbeder

2020–21

Master DSC 2A

Information Retrieval (IR)

TO READ: Chapter 1 of http://nlp.stanford.edu/IR-book/

• Quid ?

Information retrieval (IR) is ﬁnding material (usually

documents) of an unstructured nature (usually text) that

satisﬁes an information need from within large collections

(usually stored on computers).

But it also covers:

(cid:73) Routing (and Filtering)

(cid:73) Classiﬁcation/Categorization

(cid:73) Clustering

(cid:73) Information Extraction

(cid:73) Recommendation

(cid:73) Question Answering Systems

EMSE M. Beigbeder

2020–21

Master DSC 2A

Information Extraction (IE)

(cid:73) IE systems extract clear, factual information

Who did what to whom when?

The headquarters of BHP Biliton Limited, and the global

headquarters of the combined BHP Biliton Group, are

located in Melbourne, Australia.

(cid:73) Named Entity Recognition

The decision by the independent MP Andrew Wilkie to

withdraw his support for the minority Labor government

sounded dramatic but it should not further threaten its

stability. When, after the 2010 election, Wilkie, Rob

Oakeshott, Tony Windsor and the Greens agreed to

support Labor, they gave just two guarantees: conﬁdence

and supply.

Person Date Location Organization

EMSE M. Beigbeder

2020–21

Master DSC 2A

Data types in IR

• Unstructured

• Text data (news, reports, mails, etc.)

Nature

Text

Example

A large novel

Size

1 Mb

500 Mb An encyclopedia

100 Gb

20 Tb

A library

Library of Congress

• Non-text data (images, graphics, sounds, videos, etc.)

Nature

Sound

Video

Image

Example

Size

500 Mb A symphony

100 Gb

1 Pb

A movie

Numerized Library of Congress

EMSE M. Beigbeder

2020–21

Master DSC 2A

Data Size

Three scales:

1. Web: billions of documents stored on millions computers

2. enterprise

3. personnal data

EMSE M. Beigbeder

2020–21

Master DSC 2A

Diﬃculties in IR

• Data Size

1980 some hundreds megabytes

1990 ten or so gigabytes

2000 some terabytes

• Unstructured data: semantics are diﬃcult to catch

• All and every domain

• User diversity

• Diﬃcult to know the actual information need

• Distribution and multiplicity of information sources

• Both eﬃciency and eﬀectiveness are concerned

EMSE M. Beigbeder

2020–21

Master DSC 2A

Data Retrieval vs. Information Retrieval

Answer

Model

Query

lan-

Query

guage

Success crite-

ria

record (data)

deterministic

accurate,

ambiguous

artiﬁcial

complete, non

document reference

probabilistic

fuzzy, incomplete, ambigu-

ous

natural

(exactitude) eﬃciency, er-

gonomy, integrability

utility

EMSE M. Beigbeder

2020–21

Master DSC 2A

Example: What is the best SCSI drive for my personal

computer?

Drive databases (one or several catalogs):

constructor

r´ef.

Q13215 Seagate

Seagate

115-6

K13456

Seagate

. . .

provider

R&C

BlueD

R&C

capacity

2.4

3.2

interface

SCSI

price

162

159

197

access time

12.8

News: google.com/best SCSI disk PC

Best SCSI, IDE DVD-ROM drives?

Re: Dels Rodent Problem

Re: Best SCSI drive?

Re: Q: Best NT4 pageﬁle location on HD.

. . .

EMSE M. Beigbeder

2020–21

Master DSC 2A

An example

Find what Shakespeare’s plays that contain the words Brutus and

Caesar but not Calpurnia.

Query:

Brutus & Caesar & !

Calpurnia

Solution with grep and some pre- and post-processings.

But we need:

1. eﬃciency;

2. ﬂexibility;

3. ranking.

EMSE M. Beigbeder

2020–21

Master DSC 2A

Matrix representation

Antony

and

Cleopatra

Antony

Brutus

Caesar

Calpurnia

mercy

worser

. . .

Julius

Caesar

The

Tempest

Hamlet Othello Macbeth

. . .

• Document: Set of keywords

• Document: vector of {0, 1}

EMSE M. Beigbeder

2020–21

Master DSC 2A

Sparse matrix: numerical example

(cid:73) collection (corpus) of one million documents,

(cid:73) each document of size one thousand words,

(cid:73) each word six characters long,

(cid:73) in a vocabulary of half a million terms.

Occupation ratio:

EMSE M. Beigbeder

2020–21

Master DSC 2A

IR model

corpus

texte

indexation

requˆete q

f (q, δi )

@dr (q,1)

@dr (q,2)

@dr (q,3)

mise en correspondance

δ1

δ2

δ3

δn

base d’index

EMSE M. Beigbeder

2020–21

Master DSC 2A

U?An Information Retrieval System (IRS)

• deﬁnition and creation of the corpus

• matching function choice

• query language choice and deﬁnition

• users choice and deﬁnition

(cid:73) knowledge of IRS

(cid:73) kind of information needs

(cid:73) expertise

• document indexation

EMSE M. Beigbeder

2020–21

Master DSC 2A

IRS usage

1. Ask the query (U)

(cid:73) query

(cid:73) query language

(cid:73) interface

2. Build the answer (IRS)

(cid:73) matching function

(cid:73) rank

(cid:73) interface

3. Evaluate the answer (U)

EMSE M. Beigbeder

2020–21

Master DSC 2A

Index construction

1. Collect the text

Friends, Romans, countrymen. So let it be with Caesar. . .

2. Split in tokens

Friends Romans

countrymen So let

it be with

Caesar . . .

3. Linguistic processing, products normalised forms

friend roman countryman so let

caesar . . .

it be with

4. Index construction with its dictionary and its occurrences

EMSE M. Beigbeder

2020–21

Master DSC 2A

Postings lists

Brutus −→ 1

Caesar −→ 1

Calpurnia −→ 35

19 . . .

EMSE M. Beigbeder

2020–21

Master DSC 2A

Vocabulary size – Heaps’ law [1978]

(cid:73) 300 `a 600 000 entries in a dictionary

(cid:73) names of people, of locations, of products, etc.

(cid:73) the vocabulary increases with collection sizes

M = kT b

M: vocabulary size

T : collection size, number of occurrences

b about 0, 5

30 ≤ k ≤ 100

EMSE M. Beigbeder

2020–21

Master DSC 2A

Term distribution – Zipf’s law [1949]

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

(cid:73) (ti ), terms ordered by decreasing cf

d tf (t, d)

cf i α

cf i = ki −1

EMSE M. Beigbeder

2020–21

Master DSC 2A

Preliminary draft (c)(cid:0)2007 Cambridge UP845Indexcompression0123456701234567log10 ranklog10 cf!Figure5.2Zipf’slawforReuters-RCV1.Frequencyisplottedasafunctionoffrequencyrankforthetermsinthecollection.ThelineisthedistributionpredictedbyZipf’slaw(weightedleastsquaresﬁt,interceptis6.95).5.2DictionarycompressionThissectionpresentsaseriesofdictionaryrepresentationsthatachievein-creasinglyhighercompressionratios.ThedictionaryissmallcomparedtothepostingsﬁleassuggestedbyTable5.1.Sowhycompressitifitisrespon-sibleforonlyasmallpercentageoftheoverallspacerequirementsoftheIRsystem?OneofthemaindeterminantsofresponsetimeofanIRsystemisthenum-berofdiskseeksnecessarytoprocessaquery.Ifpartsofthedictionaryareonadisk,thenmanymorediskseeksarenecessaryinqueryevaluation.Thus,themaingoalofcompressingthedictionaryistoﬁtitinmainmemory,oratleastalargeportionofit,inordertosupporthighquerythroughput.Whiledictionariesofverylargecollectionswillﬁtintothememoryofastandarddesktopmachine,thisisnottrueofmanyotherapplicationscenarios.Forex-ample,anenterprisesearchserverforalargecorporationmayhavetoindexIntersection algorithm

Intersect(p1,p2)

answer ← ()

While (p1 (cid:54)= nil and p2 (cid:54)= nil) do

If (docID(p1) = docID(p2)) then

Add(answer , docID(p1))

p1 = next(p1)

p2 = next(p2)

else

If (docID(p1) < docID(p2)) then

p1 = next(p1)

else

p2 = next(p2)

end If

done

return answer

EMSE M. Beigbeder

2020–21

Master DSC 2A

Optimisation

(cid:73) conjunctive case: process the lists by increasing length;

Query:

(Calpurnia & Brutus) & Caesar

(cid:73) conjunction of disjunctions case:

Query:

OR skies) AND (kaleidoscope OR eyes)

(tangerine OR trees) AND (marmalade

(cid:73) conjunctive case: process without copy and with initialisation

to the shortest list.

EMSE M. Beigbeder

2020–21

Master DSC 2A

Westlaw

(cid:73) Information need: Information on the legal theories involved in

preventing the disclosure of trade se-

crets by employees formerly employed by a competing company.

Query: "trade secret" /s disclos!

/s employe!

/s prevent

(cid:73) Information need: Requirements for disabled people to be able

to access a work-place.

Query: disab! /p access!

work-place (employment /3 place)

/s work-site

(cid:73) Information need: Cases about a host’s responsibility for

drunk guests.

Query: host! /p (responsib! liab!)

(intoxicat! drunk!)

/p guest

EMSE M. Beigbeder

2020–21

Master DSC 2A

Wishes

(cid:73) free-text queries

(cid:73) vocabulary tolerance : orthograph mistakes, term choice

(cid:73) compound words, phrases, proximity

(cid:73) weighting (using the occurrence number)

(cid:73) ranking the answers

EMSE M. Beigbeder

2020–21

Master DSC 2A

Lexicon

(cid:73) (document) collection, corpus

(cid:73) document

(cid:73) document retrieval, ad hoc retrieval

(cid:73) information need

(cid:73) query

(cid:73) relevance

(cid:73) precision

(cid:73) recall

(cid:73) index, inverted index, inverted ﬁle

(cid:73) dictionary (data structure)

(cid:73) vocabulary (lexicon)

(cid:73) occurrence, posting

EMSE M. Beigbeder

2020–21

Master DSC 2A