Metodi per il ritrovamento dell'informazione

Precision and Recall

La precisione indica quanti documenti rilevanti sono stati trovati tra tutti i documenti ritrovati. È l'abilità di ritrovare i documenti top-ranked che sono più rilevanti. -> valuto la correttezza del sistema. Per precisione si intende il rapporto tra il numero di documenti rilevanti ritrovati e il numero di documenti ritrovati.

Il richiamo indica quanti documenti rilevanti sono stati trovati tra tutti i documenti rilevanti nella collezione. -> valuto la completezza del sistema. Per richiamo si intende il rapporto tra il numero di documenti rilevanti ritrovati e il numero di documenti rilevanti all'interno della collezione.

La precisione è la frazione di documenti ritrovati che sono rilevanti. Dal punto di vista probabilistico precisione = P(relevant | retrieved). È la capacità di recuperare documenti top-ranked più rilevanti.

Il recall è la frazione dei documenti rilevanti che riesco a ritrovare. Dal punto di vista probabilistico recall = P(retrieved | relevant). È la capacità di ritrovare tutti i documenti rilevanti.

punto di vista probabilistico richiamo = P(retrieved | relevant). È l'abilità del sistema di trovare (tutti) i documenti rilevanti nel corpus. Empiricamente quando il recall è alto la precisione si abbassa.

ACCURATEZZA -> la frazione (TP + TN) / (TP + FP + TN + FN) su tutta la collezione. L'accuratezza è la capacità del sistema di recuperare i TP e i TN. A noi nella valutazione non interessa. L'accuratezza è una valutazione comunemente usata per misurare il lavoro di classificazione dell'apprendimento automatico.

Osservazioni: qual è il richiamo di una query se recuperi tutti i documenti della collezione? Si può ottenere un elevato richiamo (ma bassa precisione) dal ritrovamento di tutti i documenti per tutte le query.

Il recall è una funzione non decrescente del numero dei documenti ritrovati. Perché se io aumento il numero dei documenti ritrovati posso succedere due cose: - Il doc è rilevante,

Il recall di un sistema di ritrovamento rappresenta una misura migliore della bontà di un sistema di ritrovamento rispetto a una media aritmetica. La media armonica, infatti, tende ad essere bassa quando almeno uno dei due valori è basso. Si chiama F1 perché è la generalizzazione di una misura standard: F β. Il valore β controlla il trade-off:

• β=1 stesso peso di precisione e richiamo
• β>1 richiamo pesa di più
• β<1 la precisione pesa di più
• β=0 (F equivale solo alla precisione)

La precisione e il richiamo non sono in grado di valutare la bontà del ranking. Il grafico di precision-recall per una query non ha molto senso. È necessario guardare una media su un insieme di domande, ma c'è un problema: i calcoli di precision-recall posizionano alcuni punti sul grafico. Come si determina un valore (interpolato) tra i punti? Per avere un grafico standard posso interpolare il valore di

precisione ad un valore dirichiamo standard: VALUTAZIONE: PRECISION@k

È la precisione dei primi k risultati del ranking (di solito k = 10 o 20). Può essere definita come il numero dei documenti rilevanti ritrovati / k.

Vantaggi:

• È appropriato per le ricerche sul web, le persone vogliono buoni risultati
• È utile per stimare il valore di cutoff K

Svantaggi:

• Non fa una distinzione tra diversi ranking con lo stesso numero di documenti rilevanti
• Fa una media sbagliata e ha un parametro k arbitrario
• La scelta di k può essere fuorviante, influenzando i risultati e l'affidabilità della valutazione

QUALI SONO LE METRICHE CHE NON SONO IN GRADO DI CALCOLARE LA BONTÀ DEL RANKING? PRECISIONE, RICHIAMO, F1. LA CURVA DI PRECISION RECALL È IN GRADO DI CALCOLARE LA BONTÀ DEL RANKING. LA PRECISION@K POTREBBE CALCOLARLO MA POICHÉ DERIVA DALLA PRECISIONE EREDITA GLI STESSI PROBLEMI

Curva di precision-recall: è una modalità grafica con

AVERAGE PRECISION

Calcolo la media delle precisioni dei documenti rilevanti ritrovati. (è l'area sotto la curva del grafico di precision recall). Prende in considerazione la posizione (il valore di rank) dei documenti. È una metrica molto utile per stimare la performance di un algoritmo di ranking: più l'area è maggiore, tanto più l'algoritmo è performante. È la media dei valori di Precision nelle posizioni in cui viene recuperato ciascun documento. Dove m è il numero dei documenti rilevanti per quella query!

AP è in grado di calcolare la bontà del ranking perché la bontà del ranking dipende dall'area sotto la curva. AP è applicata su singole query. Per più query -> MAP

MEAN AVERAGE PRECISION: è la media aritmetica dell'average precision su un set di query. Dove n è il numero

Il problema è che il valore di MAP calcolato su due sistemi di ritrovamento diversi potrebbe dare valori uguali, per questo si utilizza GMAP: GEOMETRIC MEAN AVERAGE PRECISION, che tiene conto degli incrementi di piccoli valori che hanno un forte impatto sul valore finale. È ideale per testare i sistemi su query difficili, ad esempio query in cui vengono recuperati pochi documenti pertinenti.

Un'altra variante della precisione è R-PRECISION, che rappresenta la precisione alla r-esima posizione del rank, dove R è il numero totale di documenti rilevanti per la query. La R-precision è utile per osservare il comportamento di un algoritmo per query singole. La R-precision potrebbe essere mediata su tutte le query. Quello che si fa è "tagliare" la lista dei documenti al numero di documenti rilevanti per la query.

Ultima metrica: MRR (MEAN RECIPROCAL RANK), si utilizza quando vogliamo...

Figuriamoci con una scala di giudizio. La metrica che andremo a costruire si chiama DISCOUTED CUMULATED GAIN (DCG) che combina gradi di rilevanza effettivi. Quando esaminiamo il risultato di una query, si possono fare due osservazioni fondamentali:

1. Documenti di grande rilevanza sono più utili di documenti marginalmente rilevanti
2. Minore è la posizione in classifica di un documento rilevante, meno è utile per l'utente, poiché è meno probabile che venga esaminato

Per concretizzare il primo principio quello che facciamo è assegnare un giudizio numerico (es: da 0 a 3).

Per modellare il secondo principio: creiamo un GAIN VECTOR inserendo il peso di rilevanza. Il gain vector è un vettore in cui sono presenti, in ordine di posizione, i gradi di rilevanza dei documenti. I gradi presenti in questo vettore li posso sommare per stabilire l'utilità del sistema. -> Posso ricavare il CUMULATED GAIN -> non è altro che il

Il cumulo dei gain delle varie posizioni del ranking.

Esempio: consideriamo i top 15 documenti ritrovati per q1 e q2, il gain vector è:

G1=(1, 0, 1, 0, 0, 3, 0, 0, 0, 2, 0, 0, 0, 0, 3)

G2=(0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3)

Il cumulated gain vector per q1 e q2:

CG1=(1, 1, 2, 2, 2, 5, 5, 5, 5, 7, 7, 7, 7, 7, 10)

CG2=(0, 0, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 6)

Il Cumulated gain lo possiamo definire in maniera ricorsiva:

Dove CGj[i] si riferisce al cumulated gain alla i-esima posizione del ranking per la query qj.

Ora cerchiamo di modellare il secondo principio della metrica, cioè cerco di abbattere l'importanza del peso in base alla posizione (un doc che vale 3 e si trova all'ultima posizione.) -> utilizzo un fattore di sconto (DISCOUNT FACTOR) che riduce l'impatto del gain. Un semplice calcolo del DISCOUNT FACTOR è il logaritmo in base 2 della posizione.

Per produrre una curva di CG e DCG su un set di query, facciamo una media di tutte le query. Dato

Un set di Nq query, la media CG[i] e DCG[i] su tutte le query:

Si preferisce il DCG rispetto al CG, perché il DCG tiene conto della posizione tramite l'utilizzo di un fattore di sconto D. In particolare CG, tiene conto unicamente degli elementi rilevanti ritrovati, mentre il DCG tiene conto degli elementi rilevanti ritrovati ma tiene conto anche della posizione in cui questi si trovano, maggiore sarà la posizione, maggiore sarà lo sconto e di conseguenza incideranno sul valore finale in modo minore.

Il DCG è una metrica molto utile per la valutazione di sistemi di ritrovamento che utilizzano delle misure di rilevanza graduate e non binarie, cioè sistemi in cui è possibile fornire un punteggio di rilevanza ai documenti in modo che si possano distinguere documenti più rilevanti da documenti meno rilevanti. Dato un ranking R, si definisce il vettore gain G, come il vettore ch