Information Retrieval
Definizioni e metodi
Definizioni
• IR tratta problemi di rappresentazione, memorizzazione,
organizzazione e accesso ad informazioni
• Obiettivo: facilitare l’accesso alle informazioni cui un
utente è interessato
• Un testo libero non può direttamente essere usato per
interrogare gli attuali motori di ricerca su Web.
• Una descrizione degli interessi dell’utente va trasformata
in una query, una struttura di dati (usualmente un vettore)
adatta all’elaborazione da parte di un motore di ricerca.
Caratterizzare l’interesse
dell’utente
• Caratterizzare l’interesse di un utente non è facile: “trova
tutte le pagine che contengono informazioni su squadre di
tennis di Università Americane, e che partecipino alle gare
NCAA. Mi interessano solo documenti che riportino anche
la qualifica di queste squadre negli ultimi 3 anni e la email
o telefono del loro allenatore”
• Rosso: irrilevante per la query
• Blu: necessitano una qualche forma di ragionamento
induttivo, es:
MIT is_a Università_Americana
march_2002 january_2000 january_2003
..Tuttavia anche in casi più semplici
c’è il problema del silenzio-rumore
• Esempio: chi ha inventato il web?
• http://www.google.it
Se si cerca sulla base di
parole-chiave le risposte
possono essere molto
diverse
Dati e informazioni: che differenza?
• Data retrieval: trovare oggetti che soddisfino condizioni
chiaramente specificate mediante una espressione
regolare o di algebra relazionale:
FIND person WHERE age>40 AND…OR...
Un errore è segnale di totale fallimento del sistema (la
risposta non esiste)
• Information retrieval: richiede una interpretazione della
richiesta dell’utente. I documenti recuperati non possono
essere classificati tout court come “buoni” o “cattivi”, ma
vanno associati ad una misura di rilevanza rispetto alla
richiesta dell’utente (o meglio: all’interpretazione della
richiesta!)
• La nozione di rilevanza è centrale in IR
Perché IR è importante
– IR aveva una ristretta nicchia di interesse
(bibliotecari ed esperti di informazioni, es.
agenzie di stampa)
– L’avvento del Web ha cambiato radicalmente le
cose
•
•
•
•
Una sorgente di informazioni virtualmente illimitata
Accesso universale ed a basso costo
Non esiste un controllo editoriale centralizzato
Molti nuovi problemi si pongono: IR è vista come
una area chiave per identificare soluzioni
appropriate
Le azioni dell’utente in un sistema di
IR
Retrieval
Database
Browsing
• Una sessione di Retrieval comporta la specifica degli
interessi dell’utente e la sua trasformazione in una query
(usualmente, un insieme di parole chiave o keywords)
• Se l’interesse dell’utente è mal specificato, o è molto vasto,
l’utente può utilizzare una interfaccia interattiva (es.
finestre a scelta multipla), visualizzare alcuni documenti
proposti, seguire hyperlinks a partire da documenti che più
lo interessano, o dettagliare meglio la sua query. Si parla
allora di una sessione di Browsing.
Information retrieval session: digita la query e
ottieni i risultati
Browsing Session: seguendo gli hyperlinks,
esplora i documenti
Pulling vrs pushing
• Retrieval e Browsing vengono classificate
come azioni di pulling: l’utente “tira fuori”
le informazioni richieste
• Alcuni sistemi sono in grado di prendere
iniziative, cioè di sospingere (push)
documenti verso l’utente. Ad esempio,
filtrando notizie periodicamente sulla base
di profili di utente (web assistant,
information filtering and extraction).
Fasi di un processo di IR
• L’utente esprime un interesse
• La query viene “confrontata” con i
documenti dell’archivio
• I documenti ritenuti rilevanti vengono
presentati all’utente
• L’utente può raffinare la sua query, o
navigare a partire dai risultati della ricerca
Problemi legati al processo di
retrieval
• Interessi dell’utente e documenti sono espressi in
linguaggio naturale: perché un programma di IR possa
analizzarli occorre generare una rappresentazione
formale
• Come confrontare una query ed un documento? Occorre un
modello, o schema, di confronto
• Poiché, al contrario di un sistema di interrogazione di basi
dati, il risultato di un confronto non è binario, occorre
definire una misura di “rilevanza” come risultato di un
confronto, e presentare all’utente le risposte in ordine di
rilevanza
Una caratterizzazione formale del
task IR
• Def. Un modello di IR è una quadrupla [D,Q,F,R(qi,dj)]
dove:
– D è un insieme di viste logiche, o rappresentazioni dei
documenti nella collezione
– Q è un insieme di viste logiche, o rappresentazioni dei
bisogni informativi dell’utente , dette query
– F è uno schema per modellare le rappresentazioni dei
documenti, le query, e le inter-relazioni fra query e
documenti
– R(qi,dj)] è una funzione di rilevanza, o ranking R :
QD che definisce un ordine fra i documenti, in
relazione alla query qi
Quanto è corretta la rappresentazione
del documento ?
Quanto è corretta la rappresentazione
della query ??
Quanto sono rilevanti i risultati ?
Quanto
esattamente
corrisponde il
documento alla
query?
Rappresenta
zione query
Query
Rappresentazione Documenti
PROBLEMI
NEI SISTEMI
DI IR
Collezione documenti
Risposta
Architettura di un sistema di IR
• Modulo per il trattamento dei testi (trasformare query e
documenti secondo una rappresentazione formale)
• Document management system: inserimento
cancellazione, aggiornamento dell’archivio di documenti
• Modulo di indicizzazione: puntatori ad elementi atomici
dei documenti, che ne definiscono il contenuto (es. parolechiave)
• Modulo di ricerca: data una query seleziona i documenti
(sulla base del sistema di indici) che sono rilevanti
• Modulo di ranking: ordina le “risposte” sulla base di una
misura di rilevanza
Il processo di retrieval (più in dettaglio)
Testi
Interfaccia
utente
Cerco curricula di personale esperto nella progettazione di siti web
user need
Testi
Operazioni sui testi
Vista logica
user feedback
Operazioni
Personal
sulla query
query
Vista logica
espert progettazion
sit web
Indicizzazi
one
DB Manager
Module
inverted file
(espertconosc)(realizzaz
progettaz)
ricerca
Indici sit web
Doc. recuperati
Documenti
pesati
ranking
Database
dei testi
3 fasi fondamentali
• Operazioni sui testi (query e documenti)
• Generazione di indici (strutture di
puntamento)
• Ricerca e ranking
Operazioni sui testi
• Un sistema di IR genera una rappresentazione più generale
e astratta dei documenti e delle richieste degli utenti
(query) , detta logical view, o rappresentazione.
• Quando la rappresentazione di un documento comprende
l’intero insieme delle parole che lo compongono, si parla
di full text logical view.
• Tuttavia, anche nei moderni computers sono necessarie
alcune operazioni di compressione dell’informazione
• Queste operazioni possono essere finalizzate non solo alla
compressione (es. eliminazione di articoli, congiunzioni.,
lemmatizzazione...) ma anche alla generalizzazione (non
rappresentare termini (ambigui) ma concetti )
Rappresentazione e Indicizzazione dei
documenti
• Nei sistemi di IR ogni documento viene rappresentato
mediante un insieme di parole-chiave o termini indice
• Un termine-indice è una parola ritenuta utile per
rappresentare il contenuto del documento
• In genere, nei sistemi di IR “classici”, gli indici sono
nomi, perché maggiormente indicativi del contenuto
• Tuttavia, nei motori di ricerca vengono considerati tutti i
termini (full text representation)
• Gli indici vengono utilizzati per generare strutture di
puntamento ai documenti della collezione, facilitandone il
recupero a fronte di una query.
Ranking (ordinamento)
• Un ranking è un ordinamento dei documenti
recuperati che dovrebbe riflettere gli
interessi dell’utente
• E’basato su :
– Identificazione di gruppi di termini comuni
– Condivisione di termini pesati
– Probabilità di rilevanza
• La classificazione dei modelli di IR è basata
si diversi criteri di ranking
Documenti
Termini indice
documenti
Operazioni
sui testi
match
Bisogni Informativi
ranking
query
Trattamento dei testi,
strutturazione
e metodi di Ricerca
1. Trattamento dei testi e generazione
della rappresentazione formale
• Si estraggono dal documento le parole ritenute
rilevanti per caratterizzarne il contenuto
• Questo elenco di parole o keywords viene
comunemente rappresentato come un vettore
• Il vettore ha tante dimensioni quanti sono i termini
indice (se V è il vocabolario, n=|V|)
• Se vj(w1,w2..wn) è il vettore estratto dal
documento j, wi indica la presenza o assenza del
termine i nel documento. A seconda del modello di
IR utilizzato, wi è un booleano o un reale.
di=(..,..,…after,..attend,..both,..build,.before, ..center,
college,…computer,.dinner,………..university,..work)
Operazioni sui testi
• La fase di trattamento dei testi ha come scopo individuare
gli elementi caratterizzanti un testo, e generare una
rappresentazione formale (in genere un vettore).
• Il trattamento può essere da molto semplice a molto
complesso:
– Tokenizzazione: identificazione dei singoli elementi
(parole, spazi, punteggiatura..)
– Lemmatizzazione: identificazione della radice dei
termini (vadano  andare)
– Identificazione di stringhe terminologiche (consiglio
di amministrazione) nomi propri (Presidente Giorgio
Napolitano), date e numeri (3-06-08 , 3 giugno 2008..)
– Analisi strutturale (sintassi) e semantica (piano 
pianoforte /progetto/ripiano/piano di edificio..)
Operazioni sui testi
Spaziature,
accenti
Doc.
stopwords
lemmatizzazione
Estrazione indici
Operazioni+
complesse
struttura
Struttura
Full text
(parag, titoli,
tags html XML...)
Nomi propri,
semantica
Termini
indice
1.Identificazione delle keywords o “tokens” rilevanti
2.Definizione di una struttura di memorizzazione
dei documenti efficiente ai fini del recupero
Tokenizzazione
• Un testo va trasformato in una lista di elementi
significativi detti token.
• A volte, la punteggiatura, i numeri, e la differenza
fra maiuscole e minuscole possono essere elementi
significativi. Anche le etichette html (o xml)
possono o meno essere eliminate.
• Generalmente, più superficiale è l’analisi del testo,
più dettagli vengono eliminati.
• L’approccio più semplice –quello usato dai motori
di ricerca- consiste nell’ignorare numeri e
punteggiatura e considerare solo stringhe contigue
di caratteri alfabetici come tokens.
Tokenizzazione di simboli
HTML
• Cosa fare del testo racchiuso nei comandi html che
tipicamente non vengono visualizzati? Alcune di
queste stringhe sono indicative del contenuto del
testo:
– Le parole contenute negli URLs
(www.acquistionline.it)
– Le parole contenute nei “meta testi” delle immagini.
<meta name=“description” content=“gli sfondi di
Vincent Van Gogh per il vostro Desktop”>
• L’approccio più semplice esclude dalla
tokenizzazione tutte le informazioni contenute fra
tag HTML (fra “<“ e “>”).
Tipi di documenti
Documenti
Stringhe di testo
(per le query digitate da tastiera)
Documenti su files
Files Testo
(ASCII files)
Files HTML
(HTML files)
Documenti web:
immagini, audio,
filmati, ma anche
sofware, dati strutturati..
Stopwords
• Tipicamente vengono eliminate parole ad elevata
frequenza in un linguaggio, dette stopwords (es.
parole funzionali, in inglese: “a”, “the”, “in”, “to”;
o pronomi: “I”, “he”, “she”, “it”, ecc.).
• Le Stopwords sono ovviamente dipendenti dalla
lingua. Vector Space Retrieval (VSR) utilizza un
set standard di circa 500 parole inglesi.
• http://bll.epnet.com/help/ehost/Stop_Words.htm
• Le stringhe di stopwords vengono memorizzate in
una hashtable per essere riconosciute in tempo
costante.
Stemming
• Si intende per stemming il processo di riduzione di
un termine al lemma o alla radice, in modo da
riconoscere variazioni morfologiche della stessa
parola.
– “comput-er”,“comput-ational”, “comput-ation”
“compute”
• L’analisi morfologica è specifica di ogni lingua, e
può essere molto complessa (ad esempio in
Italiano ben più che in Inglese)
• I sistemi di stemming più semplici si limitano ad
identificare suffissi e prefissi e ad eliminarli.
Porter Stemmer
• E’ una procedura semplice, che iterativamente riconosce ed
elimina suffissi e prefissi noti senza utilizzare un dizionario
(lemmario).
• Può generare termini che non sono parole di una lingua:
– “computer”, “computational”, “computation” diventano
tutti “comput”
• Vengono unificate parole che in effetti sono diverse (matto e
mattone)
• Non riconosce deviazioni morfologiche (vado e andiamo).
• http://www.mozart-oz.org/mogul/doc/lager/porterstemmer/
Errori del Porter Stemmer
• Errori di “raggruppamento”:
–
–
–
–
organization, organ  organ
police, policy  polic
arm, army  arm
matto, mattone  matt
• Errori di “omissione”:
– cylinder, cylindrical
– create, creation
– Europe, European
•
Operazioni più complesse sui
testi
Analisi morfosintattica
– I have been be
• Analisi dei Nomi Propri, date, espressioni monetarie e numeriche,
terminologia
– Medical Instrument inc
– April 15th, 2003. 15-4-03…
– 5 millions euros
– Consiglio di amministrazione, week end, ..
• Analisi della struttura del testo
– Es: I termini nel titolo o nei paragrafi hanno un peso maggiore, i termini
in grassetto o sottolineati..
• Analisi semantica: associare a parole singole o a porzioni di testo dei concetti
di una ontologia o dizionario semantico (..più avanti nel corso)
is_a
– “L’albergo dispone di piscina..”
swimming_pool
hotel_facility
– “L’albergo si trova a Corvara..”
Val_Badia
Dolomiti ..
is_in
Strumenti per l’analisi
morfosintattica di testi
• Treetagger
• On-line version su:
http://www.cele.nottingham.ac.uk/~ccztk/treetagg
er.php
• Supporta diverse lingue (inglese tedesco italiano..)
• Analisi delle parti del discorso e analisi dei gruppi
sintattici (gruppi nominali, verbali,
preposizionali..)
Sir Timothy John Berners-Lee OM KBE FRS FREng FRSA (born 8 June
1955) is an computer scientist and MIT professor credited with inventing the
World Wide Web. On 25 December 1990 he implemented the first successful
communication between an HTTP client and server via the Internet with the
help of Robert Cailliau and a young student staff at CERN. He was ranked
Joint First alongside Albert Hofmann in The Telegraph’s list of 100 greatest
living geniuses.[2] Berners-Lee is the director of the World Wide Web
Consortium (W3C), which oversees the Web’s continued development, the
founder of the World Wide Web Foundation and he is a senior researcher and
holder of the 3Com Founders Chair at the MIT Computer Science and
Artificial Intelligence Laboratory (CSAIL).
POS tagging & chunking
Sir/NNP Timothy/NNP John/NNP Berners-Lee/NNP OM/NNP KBE/NNP
FRS/NNP FREng/NNP FRSA/NNP (/( born/VBN 8/NNP June/NNP 1955/CD )/)
is/VBZ an/DT computer/NN scientist/NN and/CC MIT/NNP professor/NN
credited/VBN with/IN inventing/VBG the/DT World/NNP Wide/JJ Web/NN ./.
On/IN 25/CD December/NNP 1990/CD he/PRP implemented/VBN the/DT first/JJ
successful/JJ communication/NN between/IN an/DT HTTP/NNP client/NN
and/CC server/NN via/IN the/DT Internet/NNP with/IN the/DT help/NN of/IN
Robert/NNP Cailliau/NNP and/CC a/DT young/JJ student/NN staff/NN at/IN
CERN/NNP ./.
He/PRP was/VBD ranked/VBN Joint/NNP First/JJ alongside/IN Albert/NNP
Hofmann/NNP in/IN The/DT Telegraph's/NNP list/NN of/IN 100/CD greatest/JJS
living/VBG geniuses/NNS ./.
[/( 2/CD ]/) Berners-Lee/NNP is/VBZ the/DT director/NN of/IN the/DT
World/NNP Wide/JJ Web/NNP Consortium/NNP (/( W3C/NNP )/) ,/, which/WDT
oversees/VBZ the/DT Web's/NNP continued/VBD development/NN ,/, the/DT
founder/NN of/IN the/DT World/NNP Wide/JJ Web/NN Foundation/NN and/CC
he/PRP is/VBZ a/DT senior/JJ researcher/NN and/CC holder/NN of/IN the/DT
3Com/NNP Founders/NNPS Chair/NN at/IN the/DT MIT/NNP Computer/NNP
Science/NNP and/CC Artificial/NNP Intelligence/NNP Laboratory/NNP (/(
Terminology (multi-word) extraction
Sir Timothy John Berners-Lee
compu ter scientist
MIT professor
World Wide Web
HTTP client
Robert Cailliau
Joint First
Albert Hofmann
greatest living geniuses
World Wide Web Consortium (W3C)
World Wide Web Foundat ion
senior researcher
3Com Founders C hair
MIT Compu ter Science and Artificial Intelligence
Laboratory (CSAI L)
2. Indicizzazione dei
documenti
• Come identificare i documenti che
contengono le stesse parole della query?
• Una semplice alternativa consiste nello
scandire l’intero testo sequenzialmente
• Una opzione migliore è quella di costruire
strutture di dati chiamate indici per
velocizzare la ricerca
Indicizzazione: come
memorizzare e recuperare i
documenti rappresentati
mediante keywords
• Tecniche di indicizzazione:
– Inverted files
– Array di suffissi
– Signature files
Notazione
• n: il numero di tokens nel testo (tokens: output
del processo tokenizzazione - stopwordsstemming)
• m: lunghezza di un vettore
• V: taglia del vocabolario (quante parole
diverse)
• M: memoria a disposizione
Inverted Files
• Definizione: un inverted file è un meccanismo
orientato alla manipolazione di parole, per
indicizzare una collezione di documenti in modo
da velocizzare il processo di ricerca.
• Struttura di un inverted file:
– Vocabolario: l’insieme di parole diverse nel
testo (NOTA: la taglia di V dipende dalle
operazioni effettuate sui testi)
– Occorrenze: liste che contengono tutte le
informazioni necessarie per ogni parola del
vocabolario (posizione nel testo, frequenza,
documenti nei quali appaiono, ecc.)
Esempio
Posizione dei caratteri
• Testo:
1
6
12 16 18
25
29
36
40
45
54 58
66 70
That house has a garden. The garden has many flowers. The flowers are beautiful
• Inverted file
Vocabolario
beautiful
Occorrenze
70
flowers
45, 58
garden
18, 29
house
6
Le occorrenze identificano la
posizione del termine nel testo
Spazio di memoria
• Lo spazio necessario per memorizzare il
vocabolario non è eccessivo. Secondo la legge
di Heap il vocabolario cresce come O(n), dove
 è una costante compresa fra 0.4 e 0.6 nei casi
reali
• Viceversa, le occorrenze richiedono uno spazio
molto maggiore. Poiché vi è un riferimento per
ogni occorrenza della parola nel testo, lo spazio
necessario è O(n) per ogni riga.
• Per ridurre lo spazio necessario, si può utilizzare
una tecnica detta indirizzamento di blocco
(block addressing)
Indirizzamento di blocco
• Il testo viene suddiviso in blocchi
• Le occorrenze puntano ai blocchi in cui appare la parola
• Vantaggi:
– Il numero dei puntatori di blocco è minore del
numero dei puntatori di posizione
– Tutte le occorrenze di una parola all’interno di uno
stesso blocco hanno un solo puntatore
• Svantaggi:
– Se è richiesta l’identificazione esatta del termine, è
necessario scandire “online” i blocchi di interesse
Esempio
• Testo:
Block 1
Block 2
Block 3
Block 4
That house has a garden. The garden has many flowers. The flowers are beautiful
• Inverted file:
Vocabolario
Occorrenze
beautiful
4
flowers
3
garden
2
house
1
In alcuni modelli IR vengono
memorizzate solo le coppie Dk,tfik
Dj, tfj
Termini indice df
computer
3
D7, 4
database
2
D1, 3
4
D2, 4
1
D5 , 2

science
system
Lista delle Occorrenze
File Indice
dfi = numero di documenti in cui compare il termine ti
tfik = frequenza del termine ti nel documento Dk
Ricerca su inverted indexes
• L’algoritmo di ricerca basato su indici
inversi opera in tre fasi successsive:
– Ricerca nel vocabolario: le parole presenti nella
query vengono ricercate nel vocabolario
– Recupero delle occorrenze: viene estratta la lista
delle occorrenze di tutte le parole incluse nella
query e presenti nel vocabolario
– Manipolazione delle occorrenze: la lista delle
occorrenze viene elaborata, per generare una
risposta alla query
Ricerca su inverted indexes(2)
• La ricerca parte sempre dal vocabolario, che
dovrebbe essere memorizzato separatamente
• I vocabolari vengono memorizzati in
strutture di tipo hashing, tries o B-trees
• Alternativamente, le parole possono essere
memorizzate in ordine alfabetico (si
risparmia in spazio, maggior tempo di
ricerca)
Costruzione del vocabolario
• Il vocabolario viene generato scandendo i testi del
repository
• Vengono effettuate operazioni preliminari sui testi, di
cui abbiamo parlato, al fine di limitare la taglia del
vocabolario (stemming e stop words)
• Ad ogni parola del vocabolario, quale che sia la struttura
dati utilizzata, viene associata la lista delle occorrenze
nei documenti
• Ogni parola incontrata in un testo viene prima cercata
nel vocabolario: se non viene trovata, viene aggiunta al
vocabolario, con una lista inizialmente vuota di
occorrenze.
Costruzione del vocabolario
(2)
• Una volta che si siano esaminati tutti i testi, il
vocabolario viene memorizzato con la lista delle
occorrenze. Vengono generati due files:
– Nel primo file, vengono memorizzate in locazioni
contigue le liste delle occorrenze
– Nel secondo file, il vocabolario è memorizzato in
ordine lessicografico (alfabetico), e viene generato
per ogni parola un puntatore alla sua lista di
occorrenze nel primo file.
• L’intero processo ha un costo O(n) nel caso peggiore. La
ricerca (binaria) ha un costo O(logn)
Memorizzazione del
vocabolario in un trie
1
6
12 16 18
25
29
36
40
45
n. ordine dei
caratteri
54 58
66 70
That house has a garden. The garden has many flowers. The flowers are beautiful
beautiful:70
b
...
flowers:45
f
...
h
g
garden:18,29
has: 12,36
a
o
house: 6
Modelli strutturati del testo
• La ricerca e indicizzazione per parole-chiave
considera il documento come una struttura piatta
• Se cerco “consiglio di amministrazione” potrei
trovare documenti in cui queste parole compaiono
ma non sono correllate
• Inoltre, il peso di una parola è lo stesso sia che la
parola compaia nel testo che, ad es. nel titolo
Modelli strutturati (2)
• Definizioni:
– Match point: la posizione nel testo in cui
occorre una parola o sequenza di parole
– Regione: una porzione contigua di testo
(frase, paragrafo..)
– Nodo: un componente strutturale del testo, ad
esempio un capitolo, una sezione..
NODO
Esempio
MATCH POINT
REGIONE
Abstract—The so-called Semantic Web vision will certainly
benefit from automatic semantic annotation of words in
documents. We present a method, called structural semantic
interconnections (SSI), that creates structural specifications of the
possible senses for each word in a context, and selects the best
hypothesis according to a grammar G, describing relations
between sense specifications. The method has been applied to
different semantic disambiguation problems, like automatic
ontology construction, sense-based query expansion,
disambiguation of words in glossary definitions. Evaluation
experiments have been performed on each disambiguation task, as
well as on standard publicly available word sense disambiguation
test sets.
Proximal Nodes
• Il testo viene rappresentato con una struttura
gerarchica
• Gli indici vengono definiti mediante gerarchie
multiple
• Ogni struttura di indicizzazione è una gerarchia
composta da: capitoli, sezioni, sottosezioni,
paragrafi, linee
• Ognuno di questi componenti è un NODO
• Ad ogni nodo è associata una regione di testo
Proximal Nodes
Capitolo
Sezione
Sottosezione
Paragrafo
consiglio
10
256
48,324
Proximal Nodes
• Ogni nodo può essere contenuto in un altro
nodo
• Due nodi sullo stesso livello non si possono
sovrapporre
• L’informazione fornita dagli inverted
indexes complementa quella degli indici
gerarchici
Proximal Nodes
• E’ possibile fare query del tipo:
(*sec tion)with(( semantic )and (annotation ))
Trova una sezione in cui compaiono le parole semantic e
annotation
• Le query sono espressioni regolari, è
possibile cercare stringhe e far riferimento a
componenti strutturali
Conclusioni sui metodi di
archiviazione-indicizzazione
• Il meccanismo inverted file è il più adeguato nel
caso di archivi testuali statici
• Altrimenti, se la collezione è volatile (ad
esempio il web) la sola opzione è una ricerca
online (Spiders, nel seguito di questo corso).
• In questo caso i metodi di trattamento dei testi
devono essere semplici per garantire rapidità (li
vedremo nella seconda parte: Web information
retrieval)
3. Metodi di Ranking:
Come ordinare i documenti per
“rilevanza” rispetto ad una query
Ranking
• Supponiamo di avere a disposizione una visione
logica, e questa sia data da un insieme di parole-chiave
o keywords.
• Un banale matching di parole chiave fra documenti e
query spesso fornisce risultati modesti, gli utenti sono
insoddisfatti.
• Inoltre, spesso gli utenti non sono in grado di
esprimere i loro interessi mediante un elenco
appropriato di keywords
• Il problema è resto più grave se siamo nell’ambito Web
IR
• Un ranking appropriato dei documenti ha un effetto
notevole sulle prestazioni (vedi i motori di ricerca)
Una tassonomia dei modelli di
ranking
Teoria degli insiemi
Modelli Classici
U
s
e
r
T
a
s
k
Retrieval:
Ad-hoc
Filtering
booleano
vettoriale
probabilistico
Modelli strutturali
Non-Overlapping Lists
Proximal Nodes
Browsing
Browsing
Flat
Structure Guided
Hypertext
Fuzzy
Extended Boolean
Algebrici
Generalized Vector
Lat. Semantic Index
Neural Networks
Probabilistici
Inference Network
Belief Network
Modelli “classici”: concetti base
• Non tutti i termini sono ugualmente importanti per la
rappresentazione di un testo (o query). Nella selezione di
termini indice è importante assegnare un peso di rilevanza
alle varie parole.
• L’importanza di un termine indice è rappresentata da un
valore che ad esso viene associato
• Sia
– ki un termine indice
– dj un documento della collezione
– wij un peso associato a (ki,dj)
• Il peso wij quantifica l’importanza dell’indice ki per
descrivere il contenuto del documento
Modelli “classici”: concetti base (2)
–
–
–
–
–
–
–
ki è un termine indice
dj è un documento
N è il numero totale di documenti in D
K = (k1, k2, …, kt) è l’insieme dei termini indice
t=|K| è la taglia del vocabolario
wij >= 0 è un peso associato con (ki,dj)
wij = 0 indica che un termine non appartiene al
documento
– v(dj) =dj=(w1j, w2j, …, wtj) è un vettore pesato
associato a dj
– gi(dj) = wij è una funzione che restituisce il peso
associato alla coppia (ki,dj)
Modelli basati sulla teoria degli
insiemi: Modello Booleano
• Un modello molto semplice basato sulla set theory
• Le query vengono rappresentate mediante espressioni
booleane
– La semantica è precisa
– Il formalismo è elegante
– q = ka  (kb  kc)
Es: (automobili  (vendita  fabbricazione)
• I termini sono presenti o assenti.
• Dunque, wij  {0,1}
Esempio
• q = ka  (kb  kc)
• Forma normale disgiuntiva (DNF):
ka  kb  ka  k c
• Trasformazione della query in componenti
congiuntivi
qDNF  (1,1,0) (1,1,1) (1,0,0)

qcc
componenti congiuntivi
Modello Booleano
ka
kb
(1,0,0)
(1,1,0)
(1,1,1)
• q = ka  (kb  kc)
1 se q (q q

cc cc DNF )(ki qcc ,gi (d j )gi (qcc )
sim(d j ,q)  
0 altrimenti


kc
sim=1 se esiste almeno un componente congiuntivo della query per il quale il peso
delle relative keywords nel documento è lo stesso del componente congiuntivo.
Esempio
• Query: golf(automobile  abbigliamento)
• qcc1:golf,automobile,abbigliamento (1,1,1)
qcc2:golf,automobile, abbigliamento (1,1,0)
qcc3: golf, automobile, abbigliamento (1,0,0)
• d1:Scheda dettagli tecnici Volkswagen GOLF 2004 automobili
usate a Arezzo:diesel,cambio manuale,..
• d2: Negozio on-line specializzato nella vendita di attrezzatura,
accessori e abbigliamento delle migliori marche per la pratica
del gioco del golf ..
• d3: L'azienda Newmar produce da anni una sua linea di golf in
cachemire e capi di abbigliamento di alta qualità
• Per d1, i pesi delle parole: golf, automobile e abbigliamento
coincidono con qcc2: (1,1,0), invece per d2 e d3 i pesi non
coincidono con nessuna delle qcc della query, perché i pesi delle
tre parole sono, per entrambi i documenti: (1,0,1)
Problemi del modello Booleano
• Il retrieval è basato su criteri di decisione binari, non esiste
la nozione di corrispondenza parziale
• Non viene fornito un ordinamento parziale dei documenti
(non c’è ranking), poiché sim vale 0 o 1!!
• Gli utenti non esperti trovano difficile trasformare le loro
richieste informative in una espressione booleana
• Gli utenti formulano spesso query booleane troppo
semplicistiche (congiunzioni di termini)
• Di conseguenza, le query booleane restituiscono o troppo
pochi (silenzio) o troppi (rumore) documenti
Modello vettoriale
• Definisci:
– wij > 0 ogni volta che ki  dj
– wiq  0 associato alla coppia (ki,q)
– d j= (w1j, w2j, ..., wtj)
q = (w1q, w2q, ..., wtq)
– Ad ogni termine ki è associato un vettore unitario i  1
– I vettori unitari i e j si assumono essere ortonormali
(Cioè si assumono occorrere indipendentemente
l’uno dall’altro nei documenti)
• I t vettori unitari formano una base ortonormale in uno
spazio t-dimensionale
• In questo spazio, query e documenti sono rappresentati
mediante vettori pesati
Lo spazio vettoriale
Lo spazio ha
una
dimensionalità
pari al numero
di termini nel
vocabolario.
t3
d1
d2
t2

t1
Rappresentazione grafica
Esempio:
D1 = 2T1 + 3T2 + 5T3
D2 = 3T1 + 7T2 + T3
Q = 0T1 + 0T2 + 2T3
T3
5
D1 = 2T1+ 3T2 + 5T3
Q = 0T1 + 0T2 + 2T3
2
3
T1
D2 = 3T1 + 7T2 + T3
T2
7
• E’ D1 o D2 + simile a Q?
• Come misurare il grado di
similarità?
Nota: i coefficienti wij qui sono le frequenze dei termini Ti nei documenti
Misura della similarità del coseno
t3
• Si misura il coseno dell’angolo fra due vettori.
• Il prodotto scalare (al numeratore) è normalizzato
con la lunghezza dei vettori.
t
dj  q
CosSim(dj, q) =

dj  q
 ( wi j  wi q)
i 1
t
t
2
2
 w i j   wi q t2
i 1
i 1
1
D1
2
Q
D2
D1 = 2T1 + 3T2 + 5T3 CosSim(D1 , Q) = 10 / (4+9+25)(0+0+4) = 0.81
D2 = 3T1 + 7T2 + 1T3 CosSim(D2 , Q) = 2 / (9+49+1)(0+0+4) = 0.13
Q = 0T1 + 0T2 + 2T3
D1 è 6 volte migliore di D2 usando la misura del coseno.
t1
Similarità nel modello vettoriale
j
dj

q
i
t
dj  q
sim(dj,q) 

dj  q
 wi, j  wi,q
t
i1
t
2
2
 (wi, j )   (wi,q )
i1
i1
 cos 
Pesatura dei termini nel modello
vettoriale
• Una misura del peso di un termine in un
documento deve tenere conto di due fattori :
– Quantificazione del peso che il termine ha nel
freqi, j
documento:
tf (i, j) 
max freqk, j
• Fattore tf (term frequency)
k
– Quanto il termine aiuta a discriminare il documento dj
dagli altri documenti in D
• Fattore idf (inverse document frequency)
Dove: N numero di doc. nella collezione, ni numero N
dei documenti in cui il termine ki appare idfi  log
ni

– wij = tf(i,j) * idf(i)

Pesatura tf- idf
• Il peso di un termine in un documento è
tanto più alto quanto più il termine ricorre
molte volte nel documento, e invece ricorre
poco negli altri documenti della collezione
• Tf viene normalizzato per non penalizzare
documenti corti
• Anche idf viene normalizzato
Peso dei termini nella query
• Salton e Buckley suggeriscono:


0,5 freqi,q 
N

wi,q  0,5 

log
max ( freqk,q ) 


ni


k
Vantaggi e svantaggi del modello vettoriale
• Vantaggi:
– Il peso dei termini migliora la qualità delle risposte
– Poiché possono verificarsi matching parziali fra
documenti e query, è possibile ottenere risposte che
approssimino le richieste dell’utente
– La formula del coseno dell’angolo consente di ordinare
i documenti rispetto al grado di similarità con la query
• Svantaggi:
– Si basa sull’assunzione che i termini siano fra loro
indipendenti. Ma non è provato che questo sia un vero
svantaggio..
Il modello vettoriale:
Esempio I
k2
k1
d2
d4
idf(k1)=log(7/5)=0,146
idf(k2)=log(7/4)=0,243
idf(k3)=log(7/3)=0,367
d7
d6
d5
d3
d1
“coincidenze”
k3
tf
d1
d2
d3
d4
d5
d6
d7
k1
1
1
0
1
1
1
0
k2
0
0
1
0
1
1
1
k3
1
0
1
0
1
0
0
q
1
1
1
q  dj
2
1
2
1
3
2
1
Esempio 1 (continua)
• Calcolo sim(d1,q):
• w1,1=10,145=0,145 w2,1=0 w3,1=0,367
• w1,q= (0,5+0,5 1) 0,145=0,145
w2,q=0,243 w3,q=0,367
sim(d1,q) 
0,145  0,145  0,367  0,367
0,1452
 0,3672

0,1452
 0,2432
 0,3672
 0,85
Il modello vettoriale:
Esempio 2
k2
k1
d7
d6
d2
d4
d5
d1
d3
k3
d1
d2
d3
d4
d5
d6
d7
k1
1
1
0
1
1
1
0
k2
0
0
1
0
1
1
1
k3
1
0
1
0
1
0
0
q
1
2
3
q  dj
4
1
5
1
6
3
2
Il modello vettoriale:
Esempio 3
k2
k1
d7
d6
d2
d4
d5
d1
d3
k3
d1
d2
d3
d4
d5
d6
d7
k1
2
1
0
2
1
1
0
k2
0
0
1
0
2
2
5
k3
1
0
3
0
4
0
0
q
1
2
3
q  dj
5
1
11
2
17
5
10
Extended Boolean Model
• Il modello booleano è semplice ed elegante
• Ma non consente ranking
• Il modello booleano può essere esteso
mediante la nozione di corrispondenza
parziale e di pesatura dei termini
• Combina le caratteristiche del modello
vettoriale con le proprietà dell’algebra
booleana
Extended Boolean Model
• Il modello extended Boolean (introdotto da Salton, Fox, e
Wu, 1983) si basa su una critica di una assunzione-base
dell’algebra booleana
• Sia:
– q = kx  ky o q = kx  ky la query (queri “or” oppure “and”)
– wxj = fxj *
idf(x)
peso associato a [kx,dj]
max(idf(i))
freq ( xij )
– fxj è la frequenza normalizzata di kx in dj f ( xij )  max( freq ( xkj ))
xk d j
–  0 wxj 1
– Inoltre, indichiamo wxj = x and wyj = y
1) OR
• qor = kx  ky; wxj = x and wyj = y
(1,1)
ky
kx.ky
dj+1
y = wyj
dj
distanza
normalizzata
 kx  ky
(0,0)
x = wxj
x e y sono i pesi normalizzati di kx e ky in
dj: dj è tanto più simile a q quanto più il
punto di coord (x,y) è distante da (0,0)
kx
sim(qor,dj) =
x 2  y2
2
• qand = kx  ky; wxj = x e wyj = y
AND
(1,1)
ky
dj+1
y = wyj
(0,0)
dj
x = wxj
kx
2
2
(1

x)

(1

y)
Nel caso di un and, il punto sim(q , d )  1
and j
2
ottimale è 1,1 che corrisponde
a kx  ky
Extended Boolean Model
• Se esistono t termini indice, il modello può
essere esteso ad uno spazio t-dimensionale
• Espressioni and-or es: (k1k2)k3
 

2

2
2
  (1 x1 )  (1  x 2 ) 

2
 ( x3 ) 
1 


2
 


sim(q, d)  

2







