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