Teoria e tecniche della catalogazione e classificazione

Sistemi di recupero dell’informazionericerca4sistemi

Prof.ssa Elisa GrignaniUniversità degli studi di Parma

aa. 2005/2006

2

Abbiamo visto:

• Informazione• Dati/Informazione/Conoscenza/Sapere• Teoria dell’informazione (C. Shannon)

• Ciclo di trasferimento dell’informazione

3

Gerarchia dell’informazione

Wisdom

Knowledge

Information

Data

4

Teoria dell’informazione• Meglio indicata come “Teoria della

comunicazione”• La comunicazione oltrepassa tempo e spazio

Noise

Source DecodingEncoding Destination

Message Message

Channel

StorageSourceDecoding

(Retrieval/Reading)Encoding

(writing/indexing)Destination

Message Message

5

Ciclo di trasferimento dell’informazioneCreation

Utilization Searching

Active

Inactive

Semi-Active

Retention/Mining

Disposition

Discard

Using Creating

AuthoringModifying

OrganizingIndexing

StoringRetrieval

DistributionNetworking

AccessingFiltering

6

Temi principali del corsoCreation

Utilization Searching

Active

Inactive

Semi-Active

Retention/Mining

Disposition

Discard

Using Creating

AuthoringModifying

OrganizingIndexing

StoringRetrieval

DistributionNetworking

AccessingFiltering

7

Oggi

• Sistemi di recupero dell’informazione

8

Information Retrieval (IR)

• L’espressione “information retrieval” è coniata da C. Mooers nel 1952

• Obiettivo dell’IR è di recuperare, all’interno di una collezione, tutti e solo i documenti rilevanti per un particolare utente con una particolare richiesta informativa

• The goal is to search large document collections (millions of documents) to retrieve small subsets relevant to the user’s information need

• Rilevanza è un concetto chiave dell’IR, su cui torneremo

9

Sistemi IR: prime rappresentazioni fisiche

• Pinakes – Biblioteca di Alessandria

• Indici e concordanze della Bibbia (Ugo di San Caro, 1247)

• Indici dei giornali

10

Sistemi IR: rappresentazioni mentali

• Mnemotecnica, palazzi della memoria (Simonide di Ceo)

11

Sistemi IR: rappresentazioni bibliografiche

• Cataloghi di biblioteca

• Bibliografie

12

Visioni di sistemi IR

• Paul Otlet (’30)• Emanuel Goldberg (‘20 – ’40)• H.G. Wells, World Brain: the idea of a

permanent World Encyclopedia, 1937 (Introduzione al XVIII vol. dell’Encyclopedie Francaise)

• Vannevar Bush, As we may think, “Atlantic Monthly”, 1945 - Memex

13

Sistemi IR: storia più recente

– Radici nella “Information Explosion” che segue la II GM– L’espressione “Information Retrieval” è coniata da C.

Mooers nel 1952– A partire dagli anni ‘50, interesse verso sistemi IR

“computer-based”• H.P. Luhn presso IBM (1958)

• Modello probabilistico (Maron & Kuhns 1960)

• Sviluppo del sistema booleano presso Lockheed (‘60)

• Modello vettoriale (Salton presso Cornell U. 1965)

• Metodi di “statistical weighting” (‘70 – ‘80)• Interfacce utenti, applicazioni su larga scala (‘90)

14

Struttura di un sistema IRSearchLine Interest profiles

& QueriesDocuments

& data

Rules of the game =Rules for subject indexing +

Thesaurus (which consists of

Lead-InVocabulary

andIndexing

Language

StorageLine

Potentially Relevant

Documents

Comparison/Matching

Store1: Profiles/Search requests

Store2: Documentrepresentations

Indexing (Descriptive and

Subject)

Formulating query in terms of

descriptors

Storage of profiles

Storage of Documents

Information Storage and Retrieval System

Adapted from Soergel, p. 19

15

Struttura di un sistema IRSearchLine Interest profiles

& QueriesDocuments

& data

Rules of the game =Rules for subject indexing +

Thesaurus (which consists of

Lead-InVocabulary

andIndexing

Language

StorageLine

Potentially Relevant

Documents

Comparison/Matching

Store1: Profiles/Search requests

Store2: Documentrepresentations

Indexing (Descriptive and

Subject)

Formulating query in terms of

descriptors

Storage of profiles

Storage of Documents

Information Storage and Retrieval System

Adapted from Soergel, p. 19

16

Struttura di un sistema IRSearchLine Interest profiles

& QueriesDocuments

& data

Rules of the game =Rules for subject indexing +

Thesaurus (which consists of

Lead-InVocabulary

andIndexing

Language

StorageLine

Potentially Relevant

Documents

Comparison/Matching

Store1: Profiles/Search requests

Store2: Documentrepresentations

Indexing (Descriptive and

Subject)

Formulating query in terms of

descriptors

Storage of profiles

Storage of Documents

Information Storage and Retrieval System

Adapted from Soergel, p. 19

17

Struttura di un sistema IRSearchLine Interest profiles

& QueriesDocuments

& data

Rules of the game =Rules for subject indexing +

Thesaurus (which consists of

Lead-InVocabulary

andIndexing

Language

StorageLine

Potentially Relevant

Documents

Comparison/Matching

Store1: Profiles/Search requests

Store2: Documentrepresentations

Indexing (Descriptive and

Subject)

Formulating query in terms of

descriptors

Storage of profiles

Storage of Documents

Information Storage and Retrieval System

Adapted from Soergel, p. 19

18

Struttura di un sistema IRSearchLine Interest profiles

& QueriesDocuments

& data

Rules of the game =Rules for subject indexing +

Thesaurus (which consists of

Lead-InVocabulary

andIndexing

Language

StorageLine

Potentially Relevant

Documents

Comparison/Matching

Store1: Profiles/Search requests

Store2: Documentrepresentations

Indexing (Descriptive and

Subject)

Formulating query in terms of

descriptors

Storage of profiles

Storage of Documents

Information Storage and Retrieval System

Adapted from Soergel, p. 19

1904/07/98 9

Componenti di un sistema IR

UC DATA: Data Archive & Technical AssistanceUniversity of California, Berkeley Fredric C. Gey

Documents

AuthoritativeIndexing Rules

Indexing Process

Index Records andDocument Surrogates

Retrieval Process

Retrieval Rules

User’s Information Need

severe information loss

QuerySpecification Process

Query

List of DocumentsRelevant to User’sInformation Need

20

Sistemi IR: struttura (Cooper - Maron, 1985)

1. l’insieme delle possibili chiavi di accesso assegnate ai documenti;

2. l’insieme delle domande formulabili dagli utenti;

3. l’insieme degli indicatori di valore informativo da assegnare ai documenti;

4. una regola di recupero.

21

Sistemi IR - Modello A: registro / inventario /

topografico

1. chiavi di accesso: UN SOLO DESCRITTORE PER OGNI DOCUMENTO

2. domande: UN SOLO DESCRITTORE IN OGNI DOMANDA

3. indicatori di valore informativo: 0 (IL DOC. NON HA VALORE INFORMATIVO) / 1 (IL DOC. HA VALORE INFORMATIVO)

4. regola di recupero: AL DOC. VIENE ATTRIBUITO VALORE INFORMATIVO SE IL DESCRITTORE DELLA DOMANDA E’ UGUALE A QUELLO ASSEGNATO COME CHIAVE D’ACCESSO

22

Sistemi IR - Modello A: registro / inventario /

topografico

Esempi:• In biblioteca (ma anche altrove): inventario

patrimoniale, registro topografico • Registro di classe • Elenco telefonico ?• “Modifica / Trova” quando usate Word• ...

23

Sistemi IR - Modello B: catalogo

1. chiavi di accesso: PIU’ DI UN DESCRITTORE PUO’ ESSERE ASSEGNATO A OGNI DOCUMENTO COME CHIAVE D’ACCESSO

2. domande: COME NEL MODELLO A

3. indicatori di valore informativo: COME NEL MODELLO A

4. regola di recupero: AL DOC. VIENE ATTRIBUITO VALORE INFORMATIVO SE IL DESCRITTORE DELLA DOMANDA E’ UGUALE A UNO DI QUELLI ASSEGNATI COME CHIAVI D’ACCESSO AL DOC.

24

Sistemi IR – Pre-coordinati

I sistemi IR modelli A-B sono pre-coordinati: l’indicizzatore per rappresentare il contenuto dei documenti costruisce stringhe di ricerca, che l’utente in fase di ricerca deve ripercorrere nello stesso ordine con cui sono state formulate.

25

Sistemi IR - Modello C: booleano limitato all’operatore AND

1. chiavi di accesso: COME NEL MODELLO B2. domande: OGNI DOMANDA PUO’ CONTENERE

PIU’ DI UN DESCRITTORE3. indicatori di valore informativo: COME NEI MODELLI

A, B4. regola di recupero: AL DOC. VIENE ATTRIBUITO

VALORE INFORMATIVO SE TUTTI I DESCRITTORI CONTENUTI NELLA DOMANDA SONO UGUALI A QUELLI ASSEGNATI COME CHIAVI D’ACCESSO AL DOC.

26

Sistemi IR - Modello C: esempi

• Schede UNITERM (metà anni ’40)

EXCURSION 43821 90 241 52 63 34 25 66 17 58 49130 281 92 83 44 75 86 57 88 119640 122 93 104 115 146 97 158 139870 342 157 178 199 207 248 269 298

LUNAR 12457110 181 12 73 44 15 46 7 28 39430 241 42 113 74 85 76 17 78 79820 761 602 233 134 95 136 37 118 109 901 982 194 165 127 198 179 377 288 407

27

Sistemi IR - Modello C: esempi

• Schede “Peek-a-Boo” (1948)

Lunar

Excursion

28

Sistemi IR - Modello C: esempi

• Schede “edge-notched” (Mooers, 1951)

Document 1 Title: lksd ksdj sjd sjsjfkl Author: Smith, J. Abstract: lksf uejm jshy ksd jh uyw hhy jha jsyhe

Document 200 Title: Xksd Lunar sjd sjsjfkl Author: Jones, R. Abstract: Lunar uejm jshy ksd jh uyw hhy jha jsyhe

Document 34 Title: lksd ksdj sjd Lunar Author: Smith, J. Abstract: lksf uejm jshy ksd jh uyw hhy jha jsyhe

29

Sistemi IR - Modello D: booleano

1. chiavi di accesso: COME NEI MODELLI B, C

2. domande: COME NEL MODELLO C; I DESCRITTORI UTILIZZABILI NELLE DOMANDE POSSONO ESSERE ASSOCIATI TRA LORO UTILIZZANDO GLI OPERATORI AND, OR, NOT

3. indicatori di valore informativo: COME NEI MODELLI A, B, C

4. regola di recupero: AL DOC. VIENE ATTRIBUITO VALORE INFORMATIVO SECONDO LA LOGICA COMBINATORIA BOOLEANA

30

Sistemi IR - Modello D: booleano• Gatti

• Gatti OR Cani

• Gatti AND Cani

• Gatti NOT Cani

• Gatti AND Cani OR Pulci

• Gatti WITH Siamesi

31

Logica BooleanaGatti Cani

Pulci

32

AND

2578

152935

100135140155189190195198

28

15100135155189195

289

1215222850687784

100120128135138141150155188189195

AND =

33

OR

2578

152935

100135140155189190195198

25789

12152228293550687784

100120128135138141150155188189190195198

289

1215222850687784

100120128135138141150155188189195

OR =

34

AND NOT

2578

152935

100135140155189190195198

57

152935

140190198

289

1215222850687784

100120128135138141150155188189195

AND NOT =

35

Sistemi IR - Modello D: booleano

• Sul sistema booleano, vedere al sito:

<http://www.lib.berkeley.edu/TeachingLib/Guides/Internet/Boolean.pdf>

36

Sistemi IR - Modello D: booleano

Esempi: • In biblioteca: OPAC• Database; dominante nei sistemi commerciali

prima del WWW

37

Sistemi IR - Modelli E -: vettoriale, “statistical weighting”, probabilistico ...

• chiavi di accesso: COME NEI MODELLI B, C, D

• domande: COME NEI MODELLI D, E; E’ POSSIBILE “FILTRARE” LE DOMANDE

• indicatori di valore informativo: GLI INDICATORI DI VALORE INFORMATIVO SONO TUTTI I NUMERI REALI (il documento può avere maggiore o minore valore informativo in funzione di una domanda)

• regola di recupero:AL DOC. VIENE ATTRIBUITO UN INDICATORE DI VALORE (che ne determina la priorità di recupero) CALCOLATO SECONDO ALGORITMI diversi secondo i diversi sistemi

38

RANKING RESULTS

• The order in which search results appear. Each search tool uses its own unique algorithm. Most use "fuzzy and" combined with factors such as how often your terms occur in documents, whether they occur together as a phrase, and whether they are in title or how near the top of the text. Popularity is another ranking system.

39

Sistemi IR - Modelli E -: vettoriale, “Statistical Weighting”, probabilistico ...

Esempi:

• Ricerca Web– Motori e metamotori di ricerca

40

Sistemi IR – Post-coordinati

I sistemi IR modelli C-E sono post-coordinati: l’utente combina tra loro i diversi pezzi (gettoni) di informazione per descrivere doc. che potrebbero essere considerati rilevanti.

I sistemi post-coordinati utilizzano gli “inverted file”.

41

Inverted File• Inverted Files• This is the primary data structure for text indexes• Basic steps:

– Make a “dictionary” of all the tokens in the collection

– For each token, list all the docs it occurs in.

– Do a few things to reduce redundancy in the data structure

42

Inverted IndexesAn Inverted File is a file “inverted” so that

rows become columns and columns become rows

docs t1 t2 t3D1 1 0 1D2 1 0 0D3 0 1 1D4 1 0 0D5 1 1 1D6 1 1 0D7 0 1 0D8 0 1 0D9 0 0 1

D10 0 1 1

Terms D1 D2 D3 D4 D5 D6 D7 …

t1 1 1 0 1 1 1 0t2 0 0 1 0 1 1 1t3 1 0 1 0 1 0 0

43

How Are Inverted Files Created• Documents are parsed to extract tokens.

These are saved with the Document ID.

Now is the timefor all good men

to come to the aidof their country

Doc 1

It was a dark andstormy night in

the country manor. The time was past midnight

Doc 2

Term Doc #now 1is 1the 1time 1for 1all 1good 1men 1to 1come 1to 1the 1aid 1of 1their 1country 1it 2was 2a 2dark 2and 2stormy 2night 2in 2the 2country 2manor 2the 2time 2was 2past 2midnight 2

44

How Inverted Files are Created

• After all documents have been parsed the inverted file is sorted alphabetically.

Term Doc #a 2aid 1all 1and 2come 1country 1country 2dark 2for 1good 1in 2is 1it 2manor 2men 1midnight 2night 2now 1of 1past 2stormy 2the 1the 1the 2the 2their 1time 1time 2to 1to 1was 2was 2

Term Doc #now 1is 1the 1time 1for 1all 1good 1men 1to 1come 1to 1the 1aid 1of 1their 1country 1it 2was 2a 2dark 2and 2stormy 2night 2in 2the 2country 2manor 2the 2time 2was 2past 2midnight 2

45

How InvertedFiles are Created

• Multiple term entries for a single document are merged.

• Within-document term frequency information is compiled.

Term Doc # Freqa 2 1aid 1 1all 1 1and 2 1come 1 1country 1 1country 2 1dark 2 1for 1 1good 1 1in 2 1is 1 1it 2 1manor 2 1men 1 1midnight 2 1night 2 1now 1 1of 1 1past 2 1stormy 2 1the 1 2the 2 2their 1 1time 1 1time 2 1to 1 2was 2 2

Term Doc #a 2aid 1all 1and 2come 1country 1country 2dark 2for 1good 1in 2is 1it 2manor 2men 1midnight 2night 2now 1of 1past 2stormy 2the 1the 1the 2the 2their 1time 1time 2to 1to 1was 2was 2

46

How Inverted Files are Created

• Then the file can be split into – A Dictionary file and – A Postings file

47

How Inverted Files are CreatedDictionary PostingsTerm Doc # Freq

a 2 1aid 1 1all 1 1and 2 1come 1 1country 1 1country 2 1dark 2 1for 1 1good 1 1in 2 1is 1 1it 2 1manor 2 1men 1 1midnight 2 1night 2 1now 1 1of 1 1past 2 1stormy 2 1the 1 2the 2 2their 1 1time 1 1time 2 1to 1 2was 2 2

Doc # Freq2 11 11 12 11 11 12 12 11 11 12 11 12 12 11 12 12 11 11 12 12 11 22 21 11 12 11 22 2

Term N docs Tot Freqa 1 1aid 1 1all 1 1and 1 1come 1 1country 2 2dark 1 1for 1 1good 1 1in 1 1is 1 1it 1 1manor 1 1men 1 1midnight 1 1night 1 1now 1 1of 1 1past 1 1stormy 1 1the 2 4their 1 1time 2 2to 1 2was 1 2

48

Inverted indexes• Permit fast search for individual terms• For each term, you get a list consisting of:

– document ID – frequency of term in doc (optional) – position of term in doc (optional)

• These lists can be used to solve Boolean queries:• country -> d1, d2• manor -> d2• country AND manor -> d2

• Also used for statistical ranking algorithms

49

How Inverted Files are Used

Dictionary PostingsDoc # Freq

2 11 11 12 11 11 12 12 11 11 12 11 12 12 11 12 12 11 11 12 12 11 22 21 11 12 11 22 2

Term N docs Tot Freqa 1 1aid 1 1all 1 1and 1 1come 1 1country 2 2dark 1 1for 1 1good 1 1in 1 1is 1 1it 1 1manor 1 1men 1 1midnight 1 1night 1 1now 1 1of 1 1past 1 1stormy 1 1the 2 4their 1 1time 2 2to 1 2was 1 2

Query on “time” AND “dark”

2 docs with “time” in dictionary ->IDs 1 and 2 from posting file

1 doc with “dark” in dictionary ->ID 2 from posting file

Therefore, only doc 2 satisfied the query.

50

Prossimamente

• IR: concetti di base

• Processo di ricerca e recupero dell’informazione

• Dalla prossima settimana vedremo alcuni esempi di sistemi IR modelli D, E