Information Retrieval – 1

Michel Beigbeder

September, 24th 2020

Outline

Introduction

Definition Difficulties Data Retrieval vs. Information Retrieval An example IR model Index construction Intersection An example of a boolean system Wishes Glossary

Information Retrieval (IR)

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

• Quid ? Information retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers).

But it also covers:

Routing (and Filtering)
Classification/Categorization
Clustering
Information Extraction
Recommendation
Question Answering Systems

Information Extraction (IE)

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.

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: confidence and supply.

Person Date Location Organization

Data types in IR

• Unstructured

• Text data (news, reports, mails, etc.) Nature Size Example Text 1 Mb A large novel 500 Mb An encyclopedia 100 Gb A library 20 Tb Library of Congress

• Non-text data (images, graphics, sounds, videos, etc.) Nature Size Example Sound 500 Mb A symphony Video 100 Gb A movie Image 1 Pb Numerized Library of Congress

Data Size

Three scales:

Web: billions of documents stored on millions computers
enterprise
personnal data

Difficulties in IR

• Data Size

1980 some hundreds megabytes 1990 ten or so gigabytes 2000 some terabytes

• Unstructured data: semantics are difficult to catch

• All and every domain

• User diversity

• Difficult to know the actual information need

• Distribution and multiplicity of information sources

• Both efficiency and effectiveness are concerned

Data Retrieval vs. Information Retrieval

DR IR Answer record (data) document reference Model deterministic probabilistic Query accurate, complete, non fuzzy, incomplete, ambiguambiguous ous Query lan- artificial natural guage

Success crite- (exactitude) efficiency, er- utility ria gonomy, integrability

Example: What is the best SCSI drive for my personal computer?

Drive databases (one or several catalogs): r´ef. constructor provider capacity interface price access ti Q13215 Seagate R&C 2.4 SCSI 162 12 115-6 Seagate BlueD 2.4 SCSI 159 12 K13456 Seagate R&C 3.2 SCSI 197 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 pagefile location on HD. . . .

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:

efficiency;
flexibility;
ranking.

Matrix representation

Antony Julius The Hamlet Othello Macbeth . . . and Caesar Tempest Cleopatra Antony 1 1 0 0 0 1 Brutus 1 1 0 1 0 0 Caesar 1 1 0 1 1 1 Calpurnia 0 1 0 0 0 0 mercy 1 0 1 1 1 1 worser 1 0 1 1 1 0 . . .

• Document: Set of keywords

• Document: vector of { 0 , 1 }

Sparse matrix: numerical example

collection (corpus) of one million documents,
each document of size one thousand words,
each word six characters long,
in a vocabulary of half a million terms.

Occupation ratio:

IR model

indexation

requˆete q

@ dr ( q, 1) f ( q, δi ) @@ ddrr (( qq,, 2)3)

mise en correspondance base d’index

An Information Retrieval System (IRS)

• definition and creation of the corpus

• matching function choice

• query language choice and definition

• users choice and definition

 - knowledge of IRS

 - kind of information needs

 - expertise

• document indexation

IRS usage

Ask the query (U)
- query
- query language
- interface
Build the answer (IRS)
- matching function
- rank
- interface
Evaluate the answer (U)

Index construction

Collect the text Friends, Romans, countrymen. So let it be with Caesar. . .
Split in tokens Friends Romans countrymen So let it be with

Caesar . . .

Col1	ic proces
	roman
caesar	caesar

Index construction with its dictionary and its occurrences

Postings lists

1	Col2	6	11	Col5	21	Col7	33	Col9	35	Col11	36	Col13	41	42	Col16	Col17	Col18	Col19
1	1	2	3	4	4	7	7	10	10	11	11	19	19	19	40	40	41	43
→	35	35	35	35	35	35	35	35	35	35	35	35	35	35	35	35	35	35

Vocabulary size – Heaps’ law [1978]

300 `a 600 000 entries in a dictionary
names of people, of locations, of products, etc.
the vocabulary increases with collection sizes

M = kT

M : vocabulary size T : collection size, number of occurrences b about 0 , 5 30 ≤ k ≤ 100

Term distribution – Zipf’s law [1949]

collection frequency, cf ( t ) = [ ] d [ (] [,][ d] [)]
( ti ), terms ordered by decreasing cf

1 cf i α ou cf i = ki [−] [1]

0 1 2 3 4 5 6 7

log10 rank

Intersection algorithm

Intersect( p 1, p 2) answer ← () While ( p 1 = nil and p 2 = nil) do

If ( docID ( p 1) = docID ( p 2)) then

Add( answer , docID ( p 1)) p 1 = next ( p 1) p 2 = next ( p 2)

else

If ( docID ( p 1) < docID ( p 2)) then

p 1 = next ( p 1) else

p 2 = next ( p 2) end If end If done return answer

Optimisation

conjunctive case: process the lists by increasing length;

Query: (Calpurnia & Brutus) & Caesar

conjunction of disjunctions case:

Query: (tangerine OR trees) AND (marmalade

 OR skies) AND (kaleidoscope OR eyes)

conjunctive case: process without copy and with initialisation to the shortest list.

Westlaw

Information need: Information on the legal theories involved in preventing the disclosure of trade secrets by employees formerly employed by a competing company.

Query: "trade secret" /s disclos! /s prevent

 /s employe!

Information need: Requirements for disabled people to be able to access a work-place.

Query: disab! /p access! /s work-site

 work-place (employment /3 place)

Information need: Cases about a host’s responsibility for drunk guests.

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

 (intoxicat! drunk!) /p guest

Wishes

free-text queries
vocabulary tolerance : orthograph mistakes, term choice
compound words, phrases, proximity
weighting (using the occurrence number)
ranking the answers

Lexicon

(document) collection, corpus
document
document retrieval, ad hoc retrieval
information need
query
relevance
precision
recall
index, inverted index, inverted file
dictionary (data structure)
vocabulary ( lexicon )
occurrence, posting

Chapitre 1: Introduction à la POO