Prof.ssa Elisa Grignani Università degli studi di Parma aa. 2004/2005

Teoria e tecniche della catalogazione e classificazione

Sistemi di recupero dell’informazionericerca4sistemi

Prof.ssa Elisa GrignaniUniversità degli studi di Parma

aa. 2004/2005

ricerca3sistemi T&T 2004/05 2

Abbiamo visto:

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

• Ciclo di trasferimento dell’informazione


Gerarchia dell’informazione

Wisdom

Knowledge

Information

Data


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


Ciclo di trasferimento dell’informazioneCreation

Utilization Searching

Active

Inactive

Semi-Active

Retention/Mining

Disposition

Discard

Using Creating

AuthoringModifying

OrganizingIndexing

StoringRetrieval

DistributionNetworking

AccessingFiltering


Temi principali del corsoCreation

Utilization Searching

Active

Inactive

Semi-Active

Retention/Mining

Disposition

Discard

Using Creating

AuthoringModifying

OrganizingIndexing

StoringRetrieval

DistributionNetworking

AccessingFiltering


Oggi

• Sistemi di recupero dell’informazione


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


Sistemi IR: prime rappresentazioni fisiche

• Pinakes – Biblioteca di Alessandria

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

• Indici dei giornali


Sistemi IR: rappresentazioni mentali

• Mnemotecnica, palazzi della memoria (Simonide di Ceo)


Sistemi IR: rappresentazioni bibliografiche

• Cataloghi di biblioteca

• Bibliografie


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


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)

ricerca3sistemi T&T 2004/052

Fredric C. Gey

Historical Milestones in IR Research

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

1958 Statistic Language Properties (Luhn)1960 Probabilistic Indexing (Maron & Kuhns)1961 Term association and clustering (Doyle)1965 Vector Space Model (Salton)1968 Query expansion (Roccio, Salton)1972 Statistical Weighting (Sparck-Jones)1975 2-Poisson Model (Harter, Bookstein, Swanson)1976 Relevance Weighting (Robertson, Sparck-Jones)1980 Fuzzy sets (Bookstein)1981 Probability without training (Croft)

ricerca3sistemi T&T 2004/053

Historical Milestones in IR Research (continued)


1983 Linear Regression (Fox)1983 Probabilistic Dependence (Salton, Yu)1985 Generalized Vector Space Model (Wong, Rhagavan)1987 Fuzzy logic and RUBRIC/TOPIC (Tong, et al)1990 Latent Semantic Indexing (Dumais, Deerwester)1991 Polynomial & Logistic Regression (Cooper, Gey, Fuhr)1992 TREC (Harman)1992 Inference networks (Turtle, Croft)1994 Neural networks (Kwok)


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



& QueriesDocuments

& data



Lead-InVocabulary

andIndexing

Language

StorageLine


Documents

Comparison/Matching




Subject)


descriptors

Storage of profiles




ricerca3sistemi T&T 2004/05 2104/07/98 9

Componenti di un sistema IR


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


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.


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


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


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.


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.


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.


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



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

Lunar

Excursion



• 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


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


Sistemi IR - Modello D: booleano• Gatti

• Gatti OR Cani

• Gatti AND Cani

• Gatti NOT Cani

• Gatti AND Cani OR Pulci

• Gatti WITH Siamesi


Logica BooleanaGatti Cani

Pulci


AND

2578

152935

100135140155189190195198

28

15100135155189195

289

1215222850687784

100120128135138141150155188189195

AND =


OR

2578

152935

100135140155189190195198

25789

12152228293550687784

100120128135138141150155188189190195198

289

1215222850687784

100120128135138141150155188189195

OR =


AND NOT

2578

152935

100135140155189190195198

57

152935

140190198

289

1215222850687784

100120128135138141150155188189195

AND NOT =



• Sul sistema booleano, vedere al sito:

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



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

prima del WWW


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


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.


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

Esempi:

• Ricerca Web– Motori e metamotori di ricerca


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


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


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


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


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


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


How Inverted Files are Created

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


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


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


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.


Prossimamente

• IR: concetti di base

• Processo di ricerca e recupero dell’informazione

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


Directories vs. Search EnginesAn IMPORTANT Distinction

• Directories– Hand-selected sites

– Search over the contents of the descriptions of the pages

– Organized in advance into categories

• Search Engines– All pages in all sites

– Search over the contents of the pages themselves

– Organized after the query by relevance rankings or other scores

Prof.ssa Elisa Grignani Università degli studi di Parma aa. 2004/2005

Documents

Transcript of Prof.ssa Elisa Grignani Università degli studi di Parma aa. 2004/2005