Valutazione delle prstazioni di un sistema di retrieval.
-
Upload
raffaello-negro -
Category
Documents
-
view
213 -
download
1
Transcript of Valutazione delle prstazioni di un sistema di retrieval.
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 precedentemente 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, R o I
5 “traccie” per la gara 2010
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)
• Precision P = tp/(tp + fp)• Recall R = tp/(tp + fn)
Relevant Not Relevant
Retrieved tp (true positive) fp (false positive)
Not Retrieved fn tn
Esempio
- -
+ ++
+ ++
+
++ +
+ +
- -
-
-
- -
-
Rilevanti nella collezione: 12Rilevanti recuperati: 8Recuperati totali: 10
Precision=8/10=0,8Recall=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: 12Irrilevantinella collezione: 9Rilevanti recuperati: 8Irrilevanti 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
• Poiché la frazione di rilevanti è spessissimo minima rispetto agli irrilevanti, classificare tutto come irrilevante dà una accuracy molto alta!!
Search for:
0 matching results found.
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):
• In genere si usa una F- measure bilanciata:– cioè = 1 o = ½
RP
PR
RP
F+
+=
−+= 2
2 )1(1)1(1
1
F1 e altre combinazioni di P e R
Combined Measures
0
20
40
60
80
100
0 20 40 60 80 100
Precision (Recall fixed at 70%)
Minimum
Maximum
Arithmetic
Geometric
Harmonic
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 precision-recall
– 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.
il primo doc èrilevante P=1
il secondo non èrilevante P=0,5
il terzo èrilevante P=0,75
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 Rr
• Pinterp(r)= maxRrP(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