Teoria e tecniche della
catalogazione e classificazione
Sistemi di recupero dell’informazione
ricerca4sistemi
Prof.ssa Elisa Grignani
Università degli studi di Parma
aa. 2004/2005
Abbiamo visto:
•
•
•
•
Informazione
Dati/Informazione/Conoscenza/Sapere
Teoria dell’informazione (C. Shannon)
Ciclo di trasferimento dell’informazione
ricerca3sistemi
T&T 2004/05
2
Gerarchia dell’informazione
Wisdom
Knowledge
Information
Data
ricerca3sistemi
T&T 2004/05
3
Teoria dell’informazione
• Meglio indicata come “Teoria della
comunicazione”
• La comunicazione oltrepassa tempo e spazio
Message
Source
Message
Encoding
Decoding
Destination
Channel
Noise
Message
Source
ricerca3sistemi
Message
Encoding
(writing/indexing)
Storage
T&T 2004/05
Decoding
(Retrieval/Reading)
Destination
4
Ciclo di trasferimento dell’informazione
Creation
Active
Authoring
Modifying
Using
Creating
Retention/
Mining
Organizing
Indexing
Accessing
Filtering
Storing
Retrieval
Semi-Active
Discard
Distribution
Networking
Utilization Disposition
Searching
Inactive
ricerca3sistemi
T&T 2004/05
5
Temi principali del corso
Creation
Active
Authoring
Modifying
Using
Creating
Retention/
Mining
Organizing
Indexing
Accessing
Filtering
Storing
Retrieval
Semi-Active
Discard
Distribution
Networking
Utilization Disposition
Searching
Inactive
ricerca3sistemi
T&T 2004/05
6
Oggi
• Sistemi di recupero dell’informazione
ricerca3sistemi
T&T 2004/05
7
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
ricerca3sistemi
T&T 2004/05
8
Sistemi IR: prime rappresentazioni fisiche
• Pinakes – Biblioteca di Alessandria
• Indici e concordanze della Bibbia (Ugo di San Caro, 1247)
• Indici dei giornali
ricerca3sistemi
T&T 2004/05
9
Sistemi IR: rappresentazioni mentali
• Mnemotecnica, palazzi della memoria
(Simonide di Ceo)
ricerca3sistemi
T&T 2004/05
10
Sistemi IR: rappresentazioni bibliografiche
• Cataloghi di biblioteca
• Bibliografie
ricerca3sistemi
T&T 2004/05
11
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
ricerca3sistemi
T&T 2004/05
12
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”
•
•
•
•
•
•
ricerca3sistemi
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)
T&T 2004/05
13
Historical Milestones in IR Research
1958
1960
1961
1965
1968
1972
1975
1976
1980
1981
Statistic Language Properties (Luhn)
Probabilistic Indexing (Maron & Kuhns)
Term association and clustering (Doyle)
Vector Space Model (Salton)
Query expansion (Roccio, Salton)
Statistical Weighting (Sparck-Jones)
2-Poisson Model (Harter, Bookstein, Swanson)
Relevance Weighting (Robertson, Sparck-Jones)
Fuzzy sets (Bookstein)
Probability without training (Croft)
UC DATA: Data Archive & Technical Assistance
University of California, Berkeley
ricerca3sistemi
Fredric C. Gey
T&T 2004/05
2
Historical Milestones in IR Research (continued)
1983
1983
1985
1987
1990
1991
1992
1992
1994
Linear Regression (Fox)
Probabilistic Dependence (Salton, Yu)
Generalized Vector Space Model (Wong, Rhagavan)
Fuzzy logic and RUBRIC/TOPIC (Tong, et al)
Latent Semantic Indexing (Dumais, Deerwester)
Polynomial & Logistic Regression (Cooper, Gey, Fuhr)
TREC (Harman)
Inference networks (Turtle, Croft)
Neural networks (Kwok)
UC DATA: Data Archive & Technical Assistance
University of California, Berkeley
ricerca3sistemi
Fredric C. Gey
T&T 2004/05
3
Struttura di un sistema IR
Search
Line
Interest profiles
& Queries
Formulating query in
terms of
descriptors
Information Storage and Retrieval System
Rules of the game =
Rules for subject indexing +
Thesaurus (which consists of
Lead-In
Vocabulary
and
Indexing
Language
Storage of
profiles
Store1: Profiles/
Search requests
Storage
Line
Documents
& data
Indexing
(Descriptive and
Subject)
Storage of
Documents
Comparison/
Matching
Store2: Document
representations
Adapted from Soergel, p. 19
ricerca3sistemi
Potentially
Relevant
Documents
T&T 2004/05
16
Struttura di un sistema IR
Search
Line
Interest profiles
& Queries
Formulating query in
terms of
descriptors
Information Storage and Retrieval System
Rules of the game =
Rules for subject indexing +
Thesaurus (which consists of
Lead-In
Vocabulary
and
Indexing
Language
Storage of
profiles
Store1: Profiles/
Search requests
Storage
Line
Documents
& data
Indexing
(Descriptive and
Subject)
Storage of
Documents
Comparison/
Matching
Store2: Document
representations
Adapted from Soergel, p. 19
ricerca3sistemi
Potentially
Relevant
Documents
T&T 2004/05
17
Struttura di un sistema IR
Search
Line
Interest profiles
& Queries
Formulating query in
terms of
descriptors
Information Storage and Retrieval System
Rules of the game =
Rules for subject indexing +
Thesaurus (which consists of
Lead-In
Vocabulary
and
Indexing
Language
Storage of
profiles
Store1: Profiles/
Search requests
Storage
Line
Documents
& data
Indexing
(Descriptive and
Subject)
Storage of
Documents
Comparison/
Matching
Store2: Document
representations
Adapted from Soergel, p. 19
ricerca3sistemi
Potentially
Relevant
Documents
T&T 2004/05
18
Struttura di un sistema IR
Search
Line
Interest profiles
& Queries
Formulating query in
terms of
descriptors
Information Storage and Retrieval System
Rules of the game =
Rules for subject indexing +
Thesaurus (which consists of
Lead-In
Vocabulary
and
Indexing
Language
Storage of
profiles
Store1: Profiles/
Search requests
Storage
Line
Documents
& data
Indexing
(Descriptive and
Subject)
Storage of
Documents
Comparison/
Matching
Store2: Document
representations
Adapted from Soergel, p. 19
ricerca3sistemi
Potentially
Relevant
Documents
T&T 2004/05
19
Struttura di un sistema IR
Search
Line
Interest profiles
& Queries
Formulating query in
terms of
descriptors
Information Storage and Retrieval System
Rules of the game =
Rules for subject indexing +
Thesaurus (which consists of
Lead-In
Vocabulary
and
Indexing
Language
Storage of
profiles
Store1: Profiles/
Search requests
Storage
Line
Documents
& data
Indexing
(Descriptive and
Subject)
Storage of
Documents
Comparison/
Matching
Store2: Document
representations
Adapted from Soergel, p. 19
ricerca3sistemi
Potentially
Relevant
Documents
T&T 2004/05
20
Componenti di un sistema IR
Documents
Authoritative
Indexing Rules
Index Records
and
Document Surrogates
Indexing
Process
severe information loss
Query
Specificatio
n
Process
List of Documents
Relevant to User’s
Information Need
User’s
Information
Need
Query
UC DATA: Data Archive & Technical Assistance
University of California, Berkeley
04/07/98
ricerca3sistemi
Retrieval
Process
Retrieval
Rules
Fredric C. Gey
T&T 2004/05
9
21
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.
ricerca3sistemi
T&T 2004/05
22
Sistemi IR - Modello A: registro / inventario /
topografico
1.
2.
3.
4.
chiavi di accesso: UN SOLO DESCRITTORE PER
OGNI DOCUMENTO
domande: UN SOLO DESCRITTORE IN OGNI
DOMANDA
indicatori di valore informativo: 0 (IL DOC. NON HA
VALORE INFORMATIVO) / 1 (IL DOC. HA VALORE
INFORMATIVO)
regola di recupero: AL DOC. VIENE ATTRIBUITO
VALORE INFORMATIVO SE IL DESCRITTORE
DELLA DOMANDA E’ UGUALE A QUELLO
ASSEGNATO COME CHIAVE D’ACCESSO
ricerca3sistemi
T&T 2004/05
23
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
...
ricerca3sistemi
T&T 2004/05
24
Sistemi IR - Modello B: catalogo
1.
2.
3.
4.
chiavi di accesso: PIU’ DI UN DESCRITTORE PUO’
ESSERE ASSEGNATO A OGNI DOCUMENTO
COME CHIAVE D’ACCESSO
domande: COME NEL MODELLO A
indicatori di valore informativo: COME NEL
MODELLO A
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.
ricerca3sistemi
T&T 2004/05
25
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.
ricerca3sistemi
T&T 2004/05
26
Sistemi IR - Modello C: booleano
limitato all’operatore AND
1.
2.
3.
4.
chiavi di accesso: COME NEL MODELLO B
domande: OGNI DOMANDA PUO’ CONTENERE
PIU’ DI UN DESCRITTORE
indicatori di valore informativo: COME NEI MODELLI
A, B
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.
ricerca3sistemi
T&T 2004/05
27
Sistemi IR - Modello C: esempi
• Schede UNITERM (metà anni ’40)
LUNAR
110 181
430 241
820 761
901
ricerca3sistemi
EXCURSION
90 241
52
130 281
92
640
122
870
342
12
42
602
982
73
113
233
44
74
134
194
15
85
95
165
63
83
93
46
76
136
34
44
104
25
66
75
86
115 146
12457
7
28
17
78
37 118
127 198
377 288
407
T&T 2004/05
39
79
109
179
17
57
97
157
207
43821
58
49
88 119
158 139
178 199
248 269
298
28
Sistemi IR - Modello C: esempi
• Schede “Peek-a-Boo” (1948)
Excursion
Lunar
ricerca3sistemi
T&T 2004/05
29
Sistemi IR - Modello C: esempi
• Schede “edge-notched” (Mooers, 1951)
Document 34
Document 1
Title: lksd ksdj sjd Lunar
Title: lksd ksdj sjd sjsjfkl
Document
Author: Smith, J.
Author:
Smith, 200
J.
Title:lksf
Xksd
Lunar
sjd sjsjfkl Abstract: lksf uejm jshy
Abstract:
uejm
jshy
Author:
Jones,
ksd jh uyw hhy jha jsyhe
ksd jh
uyw hhy
jha R.
jsyhe
Abstract: Lunar uejm jshy
ksd jh uyw hhy jha jsyhe
ricerca3sistemi
T&T 2004/05
30
Sistemi IR - Modello D: booleano
1.
2.
3.
4.
chiavi di accesso: COME NEI MODELLI B, C
domande: COME NEL MODELLO C; I DESCRITTORI
UTILIZZABILI NELLE DOMANDE POSSONO
ESSERE ASSOCIATI TRA LORO UTILIZZANDO
GLI OPERATORI AND, OR, NOT
indicatori di valore informativo: COME NEI MODELLI
A, B, C
regola di recupero: AL DOC. VIENE ATTRIBUITO
VALORE INFORMATIVO SECONDO LA LOGICA
COMBINATORIA BOOLEANA
ricerca3sistemi
T&T 2004/05
31
Sistemi IR - Modello D: booleano
• Gatti
• Gatti OR Cani
• Gatti AND Cani
• Gatti NOT Cani
• Gatti AND Cani OR Pulci
• Gatti WITH Siamesi
ricerca3sistemi
T&T 2004/05
32
Logica Booleana
Gatti
Cani
Pulci
ricerca3sistemi
T&T 2004/05
33
AND
2
5
7
8
15
29
35
100
135
140
155
189
190
195
198
ricerca3sistemi
AND
2
8
9
12
15
22
28
50
68
77
84
100
120
128
135
138
141
150
155
188
189
195
T&T 2004/05
=
2
8
15
100
135
155
189
195
34
OR
2
5
7
8
15
29
35
100
135
140
155
189
190
195
198
ricerca3sistemi
OR
2
8
9
12
15
22
28
50
68
77
84
100
120
128
135
138
141
150
155
188
189
195
T&T 2004/05
=
2
5
7
8
9
12
15
22
28
29
35
50
68
77
84
100
120
128
135
138
141
150
155
188
189
190
195
198
35
AND NOT
2
5
7
8
15
29
35
100
135
140
155
189
190
195
198
ricerca3sistemi
AND NOT
2
8
9
12
15
22
28
50
68
77
84
100
120
128
135
138
141
150
155
188
189
195
T&T 2004/05
=
5
7
15
29
35
140
190
198
36
Sistemi IR - Modello D: booleano
• Sul sistema booleano, vedere al sito:
<http://www.lib.berkeley.edu/TeachingLib/Guides
/Internet/Boolean.pdf>
ricerca3sistemi
T&T 2004/05
37
Sistemi IR - Modello D: booleano
Esempi:
•
•
In biblioteca: OPAC
Database; dominante nei sistemi commerciali
prima del WWW
ricerca3sistemi
T&T 2004/05
38
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
ricerca3sistemi
T&T 2004/05
39
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.
ricerca3sistemi
T&T 2004/05
40
Sistemi IR - Modelli E -: vettoriale,
“Statistical Weighting”, probabilistico ...
Esempi:
• Ricerca Web
– Motori e metamotori di ricerca
ricerca3sistemi
T&T 2004/05
41
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”.
ricerca3sistemi
T&T 2004/05
42
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
ricerca3sistemi
T&T 2004/05
43
Inverted Indexes
An Inverted File is a file “inverted” so that
rows become columns and columns
become rows
docs
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
ricerca3sistemi
t1
1
1
0
1
1
1
0
0
0
0
t2
0
0
1
0
1
1
1
1
0
1
t3
1
0
1
0
1
0
0
0
1
1
Terms D1
t1
t2
t3
D2
1
0
1
T&T 2004/05
D3
1
0
0
D4
0
1
1
D5
1
0
0
D6
1
1
1
…
D7
1
1
0
0
1
0
44
How Are Inverted Files Created
• Documents are parsed to extract tokens.
These are saved with the Document ID.
Doc 1
Doc 2
Now is the time
for all good men
to come to the aid
of their country
It was a dark and
stormy night in
the country
manor. The time
was past midnight
ricerca3sistemi
T&T 2004/05
Term
now
is
the
time
for
all
good
men
to
come
to
the
aid
of
their
country
it
was
a
dark
and
stormy
night
in
the
country
manor
the
time
was
past
midnight
Doc #
45
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
How Inverted
Files are Created
• After all documents
have been parsed the
inverted file is sorted
alphabetically.
ricerca3sistemi
T&T 2004/05
Term
now
is
the
time
for
all
good
men
to
come
to
the
aid
of
their
country
it
was
a
dark
and
stormy
night
in
the
country
manor
the
time
was
past
midnight
Doc #
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
the
the
their
time
time
to
to
was
was
Doc #
46
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
1
2
2
1
1
2
1
1
2
2
How Inverted
Files are Created
• Multiple term entries
for a single document
are merged.
• Within-document term
frequency information
is compiled.
ricerca3sistemi
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
the
the
their
time
time
to
to
was
was
T&T 2004/05
Doc #
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
1
2
2
1
1
2
1
1
2
2
Term
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
their
time
time
to
was
Doc #
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
47
How Inverted Files are Created
• Then the file can be split into
– A Dictionary file
and
– A Postings file
ricerca3sistemi
T&T 2004/05
48
How Inverted Files are Created
Term
Doc #
a
aid
all
and
come
country
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
the
their
time
time
to
ricerca3sistemi
was
Dictionary
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
Term
a
aid
all
and
come
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
their
time
to
was
N docs
Doc #
Tot Freq
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
1
T&T 2004/05
Postings
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
2
2
2
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
49
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
ricerca3sistemi
T&T 2004/05
50
How Inverted Files are Used
Dictionary
Term
a
aid
all
and
come
country
dark
for
good
in
is
it
manor
men
midnight
night
now
of
past
stormy
the
their
time
to
was
N docs
ricerca3sistemi
Doc #
Tot Freq
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
1
Postings
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
2
2
2
Freq
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
1
1
2
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
2
2
T&T 2004/05
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.
51
Prossimamente
• IR: concetti di base
• Processo di ricerca e recupero
dell’informazione
• Dalla prossima settimana vedremo alcuni
esempi di sistemi IR modelli D, E
ricerca3sistemi
T&T 2004/05
52
Directories vs. Search Engines
An IMPORTANT Distinction
• Directories
• Search Engines
– Hand-selected sites
– Search over the
contents of the
descriptions of the
pages
– Organized in advance
into categories
ricerca3sistemi
– All pages in all sites
– Search over the
contents of the pages
themselves
– Organized after the
query by relevance
rankings or other
scores
T&T 2004/05
53