Information Retrieval
Sistemi Informativi Multimediali
I sistemi di Information retrieval
I sistemi di Information Retrieval supportano la rappresentazione,
la memorizzazione, l'organizzazione e il reperimento di
informazioni non strutturate in archivi di grandi dimensioni, sulla
base di criteri di classificazione e ricerca non esatti, basati
sull'identificazione del contenuto informativo attraverso un
utilizzo controllato del linguaggio naturale
!
!
Augusto Celentano
Università Ca’ Foscari Venezia
!
!
!
!
ricerche bibliografiche
ricerca documentaria
consultazione di archivi giuridici e normativi
catalogazione di oggetti eterogenei
archiviazione di documenti in prosa
analisi letteraria e linguistica
© Augusto Celentano
Sistemi Informativi Multimediali - 2
Le funzionalità di ricerca
Documenti e Information Retrieval
Ricerca mirata in funzione del contenuto (querying)
Un documento è una qualsiasi collezione di informazioni
rintracciabile in base alla descrizione del suo contenuto
!
!
!
!
!
classificazione argomentale
strutturazione del contenuto
indicizzazione
dizionari dei sinonimi
lemmatizzazione
!
!
!
!
I sistemi commerciali operano prevalentemente sul testo,
identificando le altre informazioni attraverso didascalie e note
Ricerca esplorativa (browsing)
!
!
!
!
testo in prosa
dati numerici e tabelle
immagini e disegni
suoni e voci
navigazione
approssimazioni successive
storia e orientamento
ricerca incrementale
I sistemi che operano sul contenuto di immagini, disegni
geometrici e sequenze video ne esplorano la struttura e le
proprietà visive
Video e audio richiedono algoritmi di pattern matching che si
estendono nel tempo e presentano un elevato grado di incertezza
© Augusto Celentano
Sistemi Informativi Multimediali - 3
© Augusto Celentano
Sistemi Informativi Multimediali - 4
Architettura funzionale di un sistema di IR
Un database di esempio (1)
Un sistema di IR non opera direttamente sui documenti
Alcuni titoli dai quotidiani (mercoledì 5 marzo 2003)
!
!
!
i documenti sono rappresentati dall’insieme di termini che lo identificano
le interrogazioni esprimono condizioni sui termini attraverso cui si
vogliono ricercare i documenti
la ricerca avviene quindi su surrogati dei documenti stessi, e la qualità
del risultato dipende dall’accuratezza dei surrogati
Determinazione della similarità tra
la richiesta e i documenti
Interrogazioni
Rappresentazione
Formulazione
della richiesta
Documenti
Indicizzazione
dei documenti
© Augusto Celentano
Sistemi Informativi Multimediali - 5
Doc n.
Testo
1
Cinque nomi negli appunti dei due BR
2
3
Il Presidente RAI all’opposizione
Bimbi stanchi e distratti? Perché dormono troppo poco
4
5
Finanziate le imprese, non le lotte di potere
FIAT: agenzia declassa il debito, perdite in Borsa
6
7
RAI: Pera e Casini offrono la presidenza all’Ulivo: si fanno i nomi di
Petruccioli e Del Turco
Baudo travolto dalle tre donne del suo Festival
8
9
Le borse: è l’accessorio che non deve mancare mai
Un giorno di digiuno contro la guerra
10
Il Presidente Bush lancia un ultimatum: “Settantadue ore poi l’attacco”
© Augusto Celentano
Sistemi Informativi Multimediali - 6
Un database di esempio (2)
Un database di esempio (3)
A ogni documento possono essere associati i termini che ne
descrivono il contenuto
Un’assegnazione più accurata considera termini polisemici e
sinonimi e pesi probabilistici
documento 1
termine
nome
1
presidente
2
rai
1
borsa
guerra
lotta
attacco
© Augusto Celentano
3
4
5
6
7
8
9
1
1
1
10
1
1
1
documento 1
termine
nome
1
presidente
rai
borsa (1)
guerra
1
1
lotta
1
1
Sistemi Informativi Multimediali - 7
attacco
borsa (2)
© Augusto Celentano
2
3
4
5
1
1
6
7
1
1
1
0.7
8
9
10
1
1
0.2
1
1
0.5
0.2
0.7
0.7
1
1
Sistemi Informativi Multimediali - 8
Formulazione delle interrogazioni
Lo spazio dei documenti in archivio
A seguito di una interrogazione, il sistema segnala il numero di
documenti ritrovati.
Alcuni documenti contengono l’informazione desiderata (sono
rilevanti), altri no
!
l'utente può riformulare, specializzare o generalizzare l’interrogazione
fino a che il numero di documenti ritrovati appare soddisfacente
Alcuni documenti saranno ritrovati come risultato
dell’interrogazione, altri no
L'esame dei documenti si avvale di due funzionalità
!
!
ranking: i documenti sono presentati all'utente in ordine decrescente di
rilevanza, secondo i pesi assegnati ai termini
browsing: i documenti sono raggruppati in classi di somiglianza,
permettendo all'utente di "sfogliarli" secondo un ordine logico
ritrovati ma non rilevanti (RitNRil)
ritrovati e rilevanti (RitRil)
ritrovati
non ritrovati
rilevanti
non ritrovati ma rilevanti (NRitRil)
© Augusto Celentano
Sistemi Informativi Multimediali - 9
non rilevanti
non ritrovati e non rilevanti (NRitNRil)
© Augusto Celentano
Sistemi Informativi Multimediali - 10
Indici di valutazione di un sistema di IR (1)
Indici di valutazione di un sistema di IR (2)
Scopo di un sistema di IR è quello di accedere efficientemente a
tutti e soli i documenti rilevanti per un dato problema
Ma richiamo e precisione non sono indipendenti
!
Si introducono due indici di valutazione
!
!
!
richiamo = RitRil / (RitRil + NRitRil)
valuta la capacità di trovare i documenti rilevanti
Si può esaminare come varia la precisione al variare del richiamo
!
!
!
se il sistema restituisce tutti i documenti ha un richiamo del 100%
non è significativo, la precisione dipende da quanti documenti non
rilevanti ci sono nell’intera collezione (solitamente NRil >> Ril)
generalmente la precisione è alta se il richiamo è basso, poi decresce
precisione = RitRil / (RitRil + RitNRil)
valuta la capacità di rigettare i documenti non rilevanti
Si osserva sperimentalmente che la precisione è più importante,
valori soddisfacenti sono
!
!
richiamo = 20%
precisione = 80%
© Augusto Celentano
Sistemi Informativi Multimediali - 11
© Augusto Celentano
Sistemi Informativi Multimediali - 12
Indici di valutazione di un sistema di IR (3)
Relazione tra richiamo e precisione (1)
Normalmente i risultati di un’interrogazione sono presentati
secondo un ordine di rilevanza
A fronte di un’interrogazione il sistema restituisce insieme
ordinato di documenti
!
!
!
alcuni documenti soddisfano l’interrogaizone meglio di altri (dipende dal
modello)
alcuni documenti “pesano” più di altri (dipende dal modello, dai termini
indice e dai documenti)
i documenti elencati per primi “dovrebbero” essere i più soddisfacenti e i
più simili all’interrogazione
© Augusto Celentano
Sistemi Informativi Multimediali - 13
!
Rit = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }
I documenti rilevanti della collezione sono
!
!
Ril = { 1, 2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 15, a, b }
richiamo = 12/14
© Augusto Celentano
Sistemi Informativi Multimediali - 14
Relazione tra richiamo e precisione (2)
Relazione tra richiamo e precisione (2)
Se i risultati sono presentati in modo ordinato la precisione varia
nel tempo
Se i risultati sono presentati in modo ordinato la precisione varia
nel tempo
!
!
Rit = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }
Ril = { 1, 2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 15, a, b }
!
!
Rit = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }
Ril = { 1, 2, 3, 4, 5, 6, 7, 10, 11, 13, 14, 15, a, b }
p
p
p = 0,07
r=1
r
© Augusto Celentano
p = 0,8
r = 0,86
r
Sistemi Informativi Multimediali - 15
© Augusto Celentano
Sistemi Informativi Multimediali - 16
Modello booleano di ricerca
Un database di esempio (1)
Ricerche con operatori booleani (AND, OR, NOT)
!
Doc n. Testo
sono valutate eseguendo operazioni booleane sugli insiemi di documenti
che corrispondono ai singoli termini dell'indice
Ricerche per adiacenza e posizione (ADJ, AFTER, BEFORE)
!
richiedono una prima valutazione booleana (AND) e successivamente
l'accesso al testo dei documenti trovati per verificare la posizione dei
termini, o l'arricchimento degli indici con informazioni posizionali
Indicazioni di rilevanza e frequenza dei termini
!
richiedono l'arricchimento degli indici e il calcolo della rilevanza dei
documenti
© Augusto Celentano
Sistemi Informativi Multimediali - 17
Un database di esempio (2)
termine
1
nome
1
2
3
4
5
6
1
1
rai
1
1
lotta
attacco
© Augusto Celentano
2
Il Presidente RAI all’opposizione
3
Bimbi stanchi e distratti? Perché dormono troppo poco
4
Finanziate le imprese, non le lotte di potere
5
FIAT: agenzia declassa il debito, perdite in Borsa
6
7
RAI: Pera e Casini offrono la presidenza all’Ulivo: si fanno i nomi di
Petruccioli e Del Turco
Baudo travolto dalle tre donne del suo Festival
8
Le borse: è l’accessorio che non deve mancare mai
9
Un giorno di digiuno contro la guerra
10
Il Presidente Bush lancia un ultimatum: “Settantadue ore poi
l’attacco”
Sistemi Informativi Multimediali - 18
Interrogazioni booleane
presidente
1
guerra
Cinque nomi negli appunti dei due BR
© Augusto Celentano
7
8
9
10
“nome” and “presidente” ->
!
1
borsa
1
1
“nome” or “presidente” ->
!
!
!
1
!
1
RAI: Pera e Casini offrono la presidenza all’Ulivo: si fanno i nomi di
Petruccioli e Del Turco
Cinque nomi negli appunti dei due BR
Il Presidente RAI all’opposizione
RAI: Pera e Casini offrono la presidenza all’Ulivo: si fanno i nomi di
Petruccioli e Del Turco
Il Presidente Bush lancia un ultimatum: “Settantadue ore poi l’attacco”
“nome” not “presidente” ->
1
!
Cinque nomi negli appunti dei due BR
1
Sistemi Informativi Multimediali - 19
© Augusto Celentano
Sistemi Informativi Multimediali - 20
Modello vettoriale di ricerca
Indicizzazione dei documenti
Una collezione di documenti è una matrice le cui righe sono i
documenti, le cui colonne sono i termini, e il cui generico
elemento Xij è una misura della rilevanza del termine j-esimo nel
documento i-esimo
L'identificazione e il reperimento delle informazioni dipende
dal grado di coincidenza tra le richieste e i testi dei documenti
!
!
!
i documenti sono punti in uno spazio n-dimensionale, le coordinate sono
i pesi dei termini
anche una interrogazione è un punto nello stesso spazio
la ricerca avviene in base a
una misura di distanza o di
D1
correlazione
Termine3
E' necessario caratterizzare le informazioni per mezzo di brevi
descrizioni convenzionali dette profili, utilizzate come surrogati
delle richieste e dei documenti
La costruzione dei surrogati dei documenti attraverso la
classificazione dei termini utilizzati si chiama indicizzazione, e
può essere manuale o automatica
Query
Come calcolare la rilevanza di
un termine?
!
!
oggettiva (autore, titolo, …)
non oggettiva (contenuto)
!
con vocabolario specifico
con vocabolario esaustivo
!
!
con termini singoli
con termini nel contesto
D2
D3
!
Termine1
!
Termine2
© Augusto Celentano
Sistemi Informativi Multimediali - 21
!
profonda
superficiale
© Augusto Celentano
Sistemi Informativi Multimediali - 22
Indicizzazione dei documenti
Indicatori di frequenza dei termini
La scelta dei termini da utilizzare negli indici dei documenti si
basa su
Le ricorrenze dei termini nei documenti possono essere utilizzate
per calcolare le somiglianze, es:
!
!
rilevanza, per l'identificazione di un documento
peso, per la discriminazione di documenti simili
!
!
i documenti 1 e 2 hanno la stessa distribuzione dei termini -> simili
i documenti 2 e 4 hanno distribuzioni molto diverse -> dissimili
La frequenza di uso delle parole è legata alla loro importanza per
l'identificazione del contenuto
!
!
le parole importanti ricorrono più frequentemente
le parole troppo frequenti sono parole comuni o termini generici
© Augusto Celentano
Sistemi Informativi Multimediali - 23
© Augusto Celentano
Sistemi Informativi Multimediali - 24
Legge di Zipf
Distribuzione di importanza delle parole
Ordinando per frequenza decrescente l'insieme di parole di un
testo si verifica che frequenza * rango = costante
Le parole più frequenti sono articoli, preposizioni, congiunzioni,
etc., o parole comuni prive di significato specifico
Poche parole sono molto frequenti
Le parole meno frequenti non sono significative per esprimere il
contenuto di un documento
!
!
!
2 parole -> 10%
6 parole -> 20%
50 parole -> 50%
Il significato è espresso
dalle parole che ricorrono
nel documento più di quanto
non ricorrano nell’intera
collezione di documenti
Molte parole sono rare
Principio del “minimo sforzo”
!
si tende a minimizzare lo sforzo di
trovare parole nuove per esprimere
concetti ricorrenti
© Augusto Celentano
Sistemi Informativi Multimediali - 25
© Augusto Celentano
Sistemi Informativi Multimediali - 26
Indicatori di rilevanza dei termini
Misure di distanza e di correlazione
Un approccio comune per l’identificazione della rilevanza dei
termini è chiamato tf*idf: term frequency * inverse document
frequency
La “somiglianza” tra due vettori che rappresentano i pesi dei
termini che descrivono due documenti (un documento e la query)
può essere calcolata in termini di distanza o di correlazione
!
!
tf : più un termine compare in un documento, più è importante per
descrivere quel documento
idf: più sono i documenti in cui appare un termine, meno quel termine è
importante (per discriminarli)
A
B
Il peso di un termine k in un documento i è wik = tfik * idfk
!
!
tfik = numero di occorrenze del termine tk nel documento i
idfk = inverso della frequenza del termine tk nella collezione dei
documenti = log(N/nk ) dove N è il numero di documenti della collezione
e nk il numero di documenti che contengono il termine tk
© Augusto Celentano
Sistemi Informativi Multimediali - 27
© Augusto Celentano
Sistemi Informativi Multimediali - 28
Modello probabilistico di ricerca
Probabilità di rilevanza (1)
I modelli probabilistici misurano le prestazioni di un sistema di IR
in termini di efficacia verso l'utente
D = { 10.000 documenti }
query = { t }
Dt = { 2.000 documenti }
R = { 20 documenti }
Rt = { 2 documenti }
!
!
!
i documenti vengono giudicati, rispetto alla query, in base alla loro
rilevanza per l’utente, misurata in termini probabilistici
se la probabilità che un documento ritrovato (indicizzato dai termini della
query) sia rilevante è maggiore della probabilità che non lo sia, allora il
documento viene
restituito, altrimenti no
le probabilità definiscono un
Documento D
ordinamento tra i documenti
Problema: possiamo
calcolare le probabilità?
P(q->D|D in R)
P(q ->D|D in NR)
Documenti
rilevanti
Documenti
non rilevanti
7980
18
1998
Dt
2
R
P ( R | d ! Dt) = 2/2000 = 0,0010
P ( R | d " Dt ) = 18/8.000 = 0,0022
E’ più probabile che i documenti rilevanti non contengano il
termine t !!!
(il termine t è rilevante?)
© Augusto Celentano
Sistemi Informativi Multimediali - 29
© Augusto Celentano
Probabilità di rilevanza (2)
Probability Ranking Principle
Dt = il documento è indicizzato dal termine t (0,1)
Formula di Bayes
ril = il documento è rilevante (0,1)
P(a|b) P(b) = P(a # b) = P(b|a) P(a)
P(b|a)p(a)
P(a|b) =
P(b)
!
!
!
!
nt = # documenti indicizzati da t
rt = # documenti rilevanti indicizzati da t
R = # documenti rilevanti
N = # documenti della collezione
P(Dt|ril) = rt/R
P(Dt|~ril) = (nt-rt) / (N-R)
7980
Dt
2
R
P(~Dt|ril) = (R -rt)/R
Documenti
non rilevanti
P(ril), P(~ril) = probabilità a priori di trovare un documenti rilevante o
non rilevante = R/N, (N-R/N)
se P(ril|Dt) > P(~ril|Dt) allora Dt è rilevante, altrimenti Dt non è
rilevante
non conosciamo R
ci interessa la probabilità P(ril|Dt)
© Augusto Celentano
P(~ril|Dt)
P(ril|Dt) = P(Dt|ril)P(ril) / P(Dt)
!
Problemi
!
P(ril|Dt)
P(~ril|Dt) = P(Dt|~ril)P(~ril) / P(Dt)
P(~Dt|~ril) = (N-nt-R+rt) / (N-R)
!
Documento D
Documenti
rilevanti
18
1998
Sistemi Informativi Multimediali - 30
Sistemi Informativi Multimediali - 31
© Augusto Celentano
Sistemi Informativi Multimediali - 32
Probability Ranking Principle (2)
Utilizzo di text signature
P(ril|Dt) = P(Dt|ril)P(ril) / P(Dt)
Per rendere più efficiente l'esame del testo dei documenti si
ricorre a codifiche compatte e uniformi (text signature), generate
con tecniche di hash e memorizzate insieme al documento
P(~ril|Dt) = P(Dt|~ril)P(~ril) / P(Dt)
!
Purtroppo non è possibile calcolare queste probabilità:
!
P(ril|Dt) = (rt/R)(R/N) / (nt/N) = rt/nt
Non conosciamo rt!!! (per restituire i documenti rilevanti
dobbiamo conoscere quali documenti sono rilevanti!!!)
!
!
!
Le ricerche basate sulla corrispondenza dei termini sono eseguite
confrontando i codici della richiesta con quelli del documento
!
possiamo calcolarli incrementalmente sulla base di risposte parziali
valutate dall’utente
relevance feedback
© Augusto Celentano
Sistemi Informativi Multimediali - 33
la presenza di un termine è segnalata da un bit
la stringa di bit viene sottoposta ad una codifica hash che ne riduce la
lunghezza
la non univocità delle signature può introdurre false corrispondenze
(false drop), che devono essere eliminate con un confronto successivo sul
testo originale
© Augusto Celentano
Sistemi Informativi Multimediali - 34
Relevance feedback (1)
Relevance feedback (2)
L’interrogazione migliore è quella che contiene i termini dei
documenti rilevanti e esclude quelli dei documenti non rilevanti
L'efficienza della ricerca può essere migliorata se le interrogazioni
sono modificate per tener conto di alcuni documenti sicuramente
rilevanti o sicuramente non rilevanti
!
!
!
CR = insieme dei documenti rilevanti nella collezione
Di, Dj = descrittori di documenti (vettori di termini)
Qopt = query “ottima”
!
!
!
l'utente integra l’interrogazione con l’indicazione dei documenti di cui è
nota a priori la presenza e la rilevanza
l'utente indica i documenti rilevanti (R) e quelli non rilevanti (NR)
ottenuti dalla risposta
il sistema può specializzare l’interrogazione sulla base di queste
indicazioni
Ma CR non è noto a priori!
© Augusto Celentano
Sistemi Informativi Multimediali - 35
© Augusto Celentano
Sistemi Informativi Multimediali - 36
Tecniche di relevance feedback (1)
Tecniche di relevance feedback (2)
Salton, 1989
Salton, 1989
© Augusto Celentano
Sistemi Informativi Multimediali - 37
Tecniche di relevance feedback (3)
© Augusto Celentano
Sistemi Informativi Multimediali - 38
Il processo di indicizzazione (1)
Il processo di indicizzazione può basarsi su operazioni sintattiche,
e quindi essere parzialmente automatizzato
!
!
!
!
!
!
eliminazione delle parole inutili (stop word)
rimozione di prefissi, suffissi, riduzione alla radice (stemming)
riunione di radici equivalenti (sinonimi, thesauri)
assegnazione dei pesi di importanza
eliminazione dei termini fuori soglia
inserimento dei termini rimasti nell'indice
Per classificare i termini utilizzati in un certo ambito si utilizza un
thesaurus che definisce classi di equivalenza e relazioni tra le
parole chiave di accesso agli indici
!
Salton, 1989
!
!
!
© Augusto Celentano
Sistemi Informativi Multimediali - 39
sinonimi
grafie differenti
legami di significato
generalizzazioni e specializzazioni
© Augusto Celentano
Sistemi Informativi Multimediali - 40
Il processo di indicizzazione (2)
Il processo di indicizzazione (3)
Testo originale
Documents
text
Experiments with Indexing Methods.
The analysis of 25 indexing algorithms has not produced consistent retrieval
performance. The best indexing technique for retrieving documents is not
known.
documents
assign document IDs
document
numbers
and *field
numbers
break into words
words
stoplist
non-stoplist
words
*Indicates
optional
operation
Segmentazione e rimozione delle parole inutili
experiments indexing methods analysis indexing algorithms produced
consistent retrieval performance best indexing technique retrieving
documents known
stemming*
stemmed
words
Riduzione alla radice
term weighting*
terms with
weights
© Augusto Celentano
Index database
Sistemi Informativi Multimediali - 41
experiment index method analys index algorithm produc consistent retriev
perform best index techni (retriev) document known
Il risultato è un insieme (multi-insieme) di termini
© Augusto Celentano
Sistemi Informativi Multimediali - 42
Indicizzazione nei sistemi di IR
Profili di utente
Nei sistemi di text
retrieval si utilizzano
strutture di
indicizzazione basate
su indici invertiti
associati alle parole
chiave
In ambienti stabili e definiti la conoscenza di chi effettua la
ricerca di informazioni può integrare e specializzare le richieste
Es. STAIRS
Il contenuto dei profili di utente è variabile nel tempo, richiede
una gestione dinamica e non è adatto a ambienti generici e a
utenti occasionali
!
!
!
!
!
Il modello vettoriale
introduce il concetto
di descrittore
multidimensionale
!
!
tipi di documenti richiesti più frequentemente
risultati delle analisi di rilevanza precedenti
conoscenza sul contesto applicativo o operativo
conoscenza sul livello di competenza e sugli scopi
dell'utente
Si possono introdurre profili dinamici basati sulla evoluzione
della sessione di lavoro
distanza
correlazione
Salton 1989
© Augusto Celentano
Sistemi Informativi Multimediali - 43
© Augusto Celentano
Sistemi Informativi Multimediali - 44
Requisiti di utente per i sistemi evoluti di IR
Modelli di sistemi evoluti di IR
I requisiti per un sistema “efficace” di IR dal punto di vista
dell’utente non devono limitarsi agli aspetti tecnici
!
!
!
!
!
!
le interrogazioni devono essere espresse nel linguaggio dell’utente usando
il suo vocabolario di concetti
deve essere possibile esprimere interrogazioni parziali e/o incerte
il numero di documenti proposti come risposta deve essere adeguato alle
esigenze dell’utente
deve essere disponibile una spiegazione comprensibile del motivo per cui
un documento è stato incluso nella risposta
l’utente deve poter riformulare la propria interrogazione in funzione
delle risposte del sistema
deve essere possibile condividere tra più utenti interrogazioni e i loro
significati (ontologie)
© Augusto Celentano
Sistemi Informativi Multimediali - 45
© Augusto Celentano
Sistemi Informativi Multimediali - 46
RUBRIC: un sistema di IR con regole di conoscenza (1)
RUBRIC: un sistema di IR con regole di conoscenza (2)
Esprime la conoscenza attraverso regole che descrivono i concetti
presenti in un certo dominio applicativo
team | event => World_Series
St._Louis_Cardinals | Milwaukee_Brewers => team
"Cardinals" = St._Louis_Cardinals (0.7)
Cardinal_full_name => St._Louis_Cardinals (0.9)
saint & "Louis" & "Cardinals" => Cardinals_full_name
"St." => saint (0.9)
"Saint" => saint
"Brewers" => Milwaukee_Brewers (0.5)
"Milwaukee Brewers" => Milwaukee_Brewers (0.9)
"World Series" => event
baseball_championship => event (0.9)
baseball & championship => baseball_championship
"ball" => baseball (0.5)
"baseball" => baseball
"championship" => championship (0.7)
!
!
!
!
!
termini
termini composti e frammenti di frase
relazioni tra termini (es. sinonimie)
relazioni tra termini e concetti
derivazione di concetti da altri concetti
Le regole specificano anche il grado di confidenza con cui un
concetto si riconosce nel modo di formularlo a parole
!
!
“baseball” --> baseball
“ball” --> baseball (0,5)
© Augusto Celentano
(da parola a concetto)
(come sopra, ma con un grado di confidenza
minore)
Sistemi Informativi Multimediali - 47
© Augusto Celentano
Sistemi Informativi Multimediali - 48
Rubric: valutazione del significato dei termini (1)
Rubric: valutazione del significato dei termini (2)
team | event => World_Series
team | event => World_Series
St._Louis_Cardinals | Milwaukee_Brewers => team
St._Louis_Cardinals | Milwaukee_Brewers => team
"Cardinals" = St._Louis_Cardinals (0.7)
"Cardinals" = St._Louis_Cardinals (0.7)
Cardinal_full_name
Cardinal_full_name
=> St._Louis_Cardinals (0.9)
saint & "Louis" & "Cardinals"
=> Cardinals_full_name
"St." => saint (0.9)
"Saint" => saint
"Brewers" => Milwaukee_Brewers (0.5)
=> Cardinals_full_name
c
c = a & b (x)
w(c) = w(a) * w(b) * x
event (.63)
"Saint" => saint
b
"Brewers" => Milwaukee_Brewers (0.5)
"World Series" (0) baseball_championship (.7)
"Milwaukee Brewers"
=> Milwaukee_Brewers (0.9)
=> Milwaukee_Brewers (0.9)
"World Series" => event
baseball & championship
team (0)
"St." => saint (0.9)
&
a
"Milwaukee Brewers"
baseball_championship => event (0.9)
World_Series (.63)
=> St._Louis_Cardinals (0.9)
Composizione di concetti
saint & "Louis" & "Cardinals"
"World Series" => event
c
c = a | b (x)
w(c) = max(w(a),w(b)) * x
=> baseball_championship
baseball_championship => event (0.9)
|
a
b
"ball" => baseball (0.5)
"baseball" => baseball
"baseball" => baseball
© Augusto Celentano
(RUBRIC, 1985)
Sistemi Informativi Multimediali - 49
"ball" (1) "baseball" (1) "championship" (1)
(RUBRIC, 1985)
"championship" => championship (0.7)
© Augusto Celentano
Sistemi Informativi Multimediali - 50
RUBRIC: regole e modificatori
Tecniche di inferenza logica
Le regole normalmente associano termini a concetti “per
aggregazione”
Database
!
!
!
!
!
E’ possibile specificare regole che “confutano” associazioni
precedenti
championship (.7)
=> baseball_championship
"ball" => baseball (0.5)
"championship" => championship (0.7)
baseball (1)
baseball & championship
!
!
!
!
about(d1,c2).
about(d1,c12).
about(d2,c3).
about(d2,c27).
about(d3,c12).
about(d4,c45).
part-of(d4,d1).
nn(d2,d3).
synonym(c2,c27).
Regole
!
!
!
about(D,Cx) :- about(D,Cy),
synonym(Cx,Cy).
about(Dx,C) :- about(Dy,C),
nn(Dx,Dy).
about(Dx,C) :- about(Dy,C),
part-of(Dy,Dx).
Query
!
?- about(X,c2), about(X,c12),
about(X,c45).
Risposta
!
!
© Augusto Celentano
Sistemi Informativi Multimediali - 51
© Augusto Celentano
d1 (attraverso d4)
d2, d3 non contengono c45
Sistemi Informativi Multimediali - 52
IR multimediale: problemi (1)
IR multimediale: problemi (2)
La ricerca di informazioni multimediali è più complessa della
information retrieval su documenti di testo
Gli oggetti multimediali sono rappresentati da insiemi di
caratteristiche
!
!
!
!
l’informazione è contenuta in dati appartenenti a classi diverse per
codifica e presentazione
un sistema di retrieval deve valutare una query riferendosi a classi
diverse di dati contemporaneamente
le condizioni espresse nella query possono appartenere (in genere
appartengono) ad un dominio di rappresentazione diverso dai dati
ricercati
i dati multimediali hanno un contenuto informativo molto ricco ma parte
della informazione non è esplicita e può essere estratta solo analizzando
un contesto più ampio
!
colore, texture, forma, struttura
Ogni caratteristica è un vettore di componenti
!
!
es., istogramma dei colori, parametri di texture, coefficienti di Fourier
le caratteristiche possono avere più rappresentazioni (es., spazi di colore)
Un oggetto multimediale è quindi descritto da un (multi-)vettore in
uno spazio di caratteristiche
!
!
!
alta dimensionalità
intervalli di valori differenti per ogni dimensione
normalizzazione
Le caratteristiche non sono equivalenti
!
!
© Augusto Celentano
Sistemi Informativi Multimediali - 53
IR multimediale: problemi (3)
sono legate alla percezione umana
la somiglianza può riguardare solo alcune
caratteristiche e non altre
© Augusto Celentano
Sistemi Informativi Multimediali - 54
Esempio: ricerca di immagini per somiglianza (1)
I termini in un documento di testo sono considerati indipendenti
!
!
il modello vector space assume che la distribuzione dei punti nello spazio
sia in linea di principio omogenea
le funzioni di somiglianza si basano su questa assunzione
Ma le caratteristiche di un oggetto multimediale NON sono
indipendenti
!
!
es., autocorrelazione dei colori o correlazione colore/texture
negativo, ma per fortuna il problema è soprattutto teorico
“La maledizione dimensionale” (dimensionality curse)
!
!
!
quando le dimensioni di uno spazio crescono, la distanza tra i punti tende
a livellarsi (non è discriminante)
i punti tendono ad accumularsi verso la superficie di un’ipersfera che
delimita il campo di valori delle caratteristiche
la distanza tra due punti qualunque è variabili all’interno di un intervallo
piccolo (= tutti i punti sono vicini tra loro)
© Augusto Celentano
Sistemi Informativi Multimediali - 55
(QBIC, 1995)
© Augusto Celentano
Sistemi Informativi Multimediali - 56
Esempio: ricerca di immagini per somiglianza (2)
Esempio: ricerca di immagini per somiglianza (3)
(Del Bimbo 1999)
© Augusto Celentano
Sistemi Informativi Multimediali - 57
Ricerca di informazioni multimediali continue
Nell’ambito dei media continui, la ricerca di informazioni si può
appoggiare a proprietà visuali misurabili che derivano da proprietà
o variazioni di contenuto
!
!
!
identificazione dei movimenti nell’immagine
identificazione dei cambiamenti nell’immagine
identificazione di configurazioni ripetitive
luminosità
zoom
© Augusto Celentano
panoramica
fotogrammi
Sistemi Informativi Multimediali - 59
© Augusto Celentano
Sistemi Informativi Multimediali - 58