Valutazione delle prstazioni di
un sistema di retrieval
Misure di valutazione per un
motore di ricerca
• Velocità di indicizzazione
– Numero di documenti/ora
– (In funzione della dimensione media del
documento)
• Velocità di ricerca
– Latenza: funzione della dimensione dell’indice
• Espressività del “query language” (booleano,
parole chiave..)
– Velocità di retrieval per query complesse
Misure di valutazione per un
motore di ricerca
• Tutti i criteri precedenetemente citati sono
misurabili: possiamo quantificare il rapporto
velocità/dimensione, e anche il concetto di
espressività può essere precisato
• La misura più importante è la soddisfazione
dell’utente
– La velocità di risposta è importante per l’utente
– Ma un sistema veloce che fornisca risposte
irrilevanti non può soddisfare l’utente
• Occorre quantificare in qualche modo la
soddisfazione dell’utente
Misure di “soddisfazione”
• Le misure dipendono anche dal tipo di utente
e dagli scopi del sistema di retrieval
• Web engine: se l’utente trova ciò che vuole,
tornerà ad usare il motore di ricerca
– Si può misurare la frequenza di questi “ritorni”
• Un sito di eCommerce : l’utente trova quel
che vuole ed acquista un bene
– Ma in tal modo si misura la soddisfazione
dell’utente, o del sito di eCommerce?
– Misurare il tempo necessario per un acquisto, o la
frazione di utenti che diventano acquirenti?
Misure di soddisfazione
• Impresa
(società/amministrazione/accademia):
Danno peso alla “user productivity”
– Quanto tempo risparmia il mio utente
usando questo sistema?
– Esistono anche altri criteri, come ampiezza
delle informazioni memorizzate, sicurezza
degli accessi, privacy..
Soddisfazione: difficile da
misurare
•
•
•
Il metodo di misura “approssimativo” più
comunemente usato: rilevanza dei risultati
Come misuriamo la rilevanza?
Per una valutazione sperimentale servono 3
elementi:
 Una collezione standard di documenti
 Un set standard di queries
 Una stima binaria della rilevanza o irrilevanza di
ogni coppia query-doc, effettuata da esperti
Valutazione dei sistemi IR
• Il bisogno informativo viene tradotto in una
query
• Ma la rilevanza va misurata con riferimento al
bisogno informativo!
• ES: Bisogno informativo: I'm looking for
information on whether drinking red wine is
more effective at reducing your risk of heart
attacks than white wine.
• Query: drink wine red white heart attack
effective
• Non è così importante la presenza di tutte
queste parole, quanto che si parli di ciò
che l’utente vuole sapere!
Valutazioni standardizzate
(benchmarks) di rilevanza
• TREC - National Institute of Standards and
Testing (NIST trec.nist.gov/ ) ha preparato
per molti anni benchmarks su larga scala, e
“gare” di retrieval con vari “tasks”
• Utilizza le collezioni Reuters (agenzia
stampa) e altri archivi di grandi dimensioni
• Vengono specificati i compiti di retrieval in
modo preciso
• Esperti umani assegnano un indicatore di
rilevanza ad ogni documento per ogni query,
RoI
5 “traccie” per la gara 2008
Altre traccie degli anni passati:
•Question Answering Track
•Spam Track
•Genomics Track
•Cross- language Track
•..
Misure di rilevanza: Precision
e Recall
• Precision: frazione dei documenti recuperati
che sono rilevanti = P(rilevanti|recuperati)
• Recall: frazione dei documenti rilevanti che
vengono recuperati = P(recuperati|rilevanti)
Relevant
Retrieved
Not Retrieved
Not Relevant
tp (true positive) fp (false positive)
fn
tn
• Precision P = tp/(tp + fp)
• Recall
R = tp/(tp + fn)
Esempio
Rilevanti nella collezione: 12
Rilevanti recuperati: 8
Recuperati totali: 10
+
-
+
+
+
+
+
+
+
Precision=8/10=0,8
Recall=8/12=0,66
+
-
-- -
-
+
+
-
-
+
-
Accuracy – una misura
alternativa
• Data una query il sistema di ricerca
classifica i documenti della collezione
come “Rilevanti” o “Irrilevanti”.
• Accuracy del motore di ricerca: la
frazione di questa classificazione che
risulta corretta
Esempio
Rilevanti nella collezione: 12
Irrilevantinella collezione: 9
Rilevanti recuperati: 8
Irrilevanti non recuperati : 7
+
-
+
+
+
+
+
+
+
Accuracy=(tp+tn)/totali
=(8+7)/(12+9)=15/21=0,71
+
-
-- -
-
+
+
-
-
+
-
Perché l’accuracy non basta?
• Come costruire un motore con accuracy
99.9999% con un budget limitato
Search for:
0 matching results found.
• Poiché la frazione di rilevanti è spessissimo minima
rispetto agli irrilevanti, classificare tutto come
irrilevante dà una accuracy molto alta!!
Precision/Recall
• Anche qui c’è il trucco..
• E’ possibile ottenere una recall=1 (ma 0
precision) recuperando tutti i documenti
della collezione!
Difficoltà di utilizzo di
precision/recall
• Si dovrebbe mediare su un ampio numero di
documenti e tipi di query
• E’ necessario il giudizio di esperti umani
– Non affidabile: in genere si impiegano più esperti
(si misura “inter-annotator-agreement”, che
difficilmente è superiore all’80%)
• I giudizi devono essere binari (I o R)
– Ma spesso un giudizio ha una gradazione!!
• Dipendenza dal corpus di documenti
– I risultati spesso non sono trasferibili da un
dominio all’altro
Una misura combinata: F
• La F-measure media fra precision e recall
(media armonica pesata):
(  2  1) PR
F

2
1
1

P

R
  (1   )
P
R
1
• In genere si usa una F- measure bilanciata:
– cioè  = 1 o  = ½
F1 e altre combinazioni di P e
R
Combined Measures
100
80
Minimum
Maximum
60
Arithmetic
40
Geometric
Harmonic
20
0
0
20
40
60
80
Precision (Recall fixed at 70%)
100
Ranked results
• Valutazione dei risultati “pesati” :
– E’ possibile restituire qualsiasi numero k di risultati
(con k prefissato, oppure fissando una “soglia” per
il valore minimo di rank)
– Scegliendo vari valori k per il numero di documenti
restituiti (il che corrisponde a fissare diversi livelli
di recall), si può costruire una curva precisionrecall
– Queste misure sono più utili per i motori di
ricerca, infatti, non conta tanto la precisione e la
recall globale, quanto che i documenti “buoni”
siano presentati nella prima, o prime due, pagine!
Curve Precision-Recall
L’andamento è a dente di sega: se il (k+1)-esimo documento non è rilevante,
la recall sarà la stessa che per i primi k, ma la precisione calerà. Se invece è rilevante,
sia P che R aumentano in valore.
Valutazione: altre misure
• Altre misure
– Precision con recall fissa
• Appropriata per web search: si preferisce avere buoni
risultati nella prima, o prime due, pagine di risultati
– 11-point interpolated average precision
• Si traccia una curva precision-recall e si esegue una
interpolazione nel seguente modo: la precisione
interpolata a livello r è la più alta precisione che si ottiene
per ogni livello di recall Rr
• Pinterp(r)= maxRrP(R )
• La “11-point” è una curva interpolata, per i seguenti 11
valori di k: 0.0, 0.1, 0.2, ..., 1.0
• Si esegue una media artimetica dei valori di precisione
interpolati, su tutte le query del benchmark
Esempio