3.4 Implementazione del motore di ricerca
3.4.2 Funzionamento di 4IR
Posto di avere a disposizione una collezione sperimentale ed di aver effettuato l’o- perazione di indicizzazione, l’algoritmo prevede che in ingresso sia fornita una stringa rappresentante l’esigenza informativa da soddisfare. Nell’implementazione attuale, 4IR è stato progettato per leggere le interrogazioni da un file di testo e procedere con il reperimento; un parametro da fornire in ingresso riguarda quindi il percorso in cui trovare il file di testo ed estrarne le informazioni. Un’altra indicazione che è necessa- rio fornire affinché il motore possa funzionare è il percorso dove si trova l’indice della collezione; senza questo dato, infatti, non sarebbe possibile reperire alcun documento. Non rimane quindi che specificare percorso e nome del file di output dove verranno stampati i risultati del reperimento.
25 3.4 Implementazione del motore di ricerca
Settate queste variabili, 4IR procede con il calcolo del numero di campioni N, della frequenza fi associata ad ogni termine dell’interrogazione e del loro peso IDF.
A questo punto si ottiene il vettore su cui calcolare la DFT e si procede al calcolo di quest’ultima; infine, ottenuto il modulo della trasformata discreta di Fourier si hanno a disposizione tutti i valori dello spettro che, se sommati, portano ad avere la potenza associata all’interrogazione di input. Si procede quindi con la fase di filtraggio e quella di ranking ottenendo così, in risposta all’esigenza informativa, la lista ordinata per rilevanza dei documenti con relativa potenza associata. I dati, vengono formattati nel formato richiesto dal software Trec_eval 2 e memorizzati nel file di output indicato
dall’utente.
2
CAPITOLO
QUATTRO
ESPERIMENTI
Posto ora di aver implementato il modello LSPR come descritto nel capitolo 3, risulta di notevole interesse avere un’indicazione sulle performance e utilizzare tali indicazioni per confrontare 4IR con un altro o con un’altra versione di se stesso: si deve quindi eseguire la valutazione del modello di IR. In questa fase vengono utilizzate alcune misure, descritte in dettaglio nella sezione 4.1, che servono per avere degli indici di riferimento, relativi alle caratteristiche del modello che si vogliono testare. Un altro elemento importante che entra in gioco nella fase di test è la collezione sperimentale, trattata nella sezione 4.2 che fornisce l’insieme di documenti, interrogazioni e giudizi di rilevanza sui documenti della collezione da utilizzare per la valutazione del sistema. In questa tesi il confronto è stato effettuato tra il modello LSPR sviluppato e il modello probabilistico BM25 considerato lo stato dell’arte in letteratura. I test sono quindi stati svolti per verificare l’ipotesi che il modello LSPR implementato da 4IR dimostrasse prestazioni confrontabili con quelle di BM25; se questo fosse stato confermato, infatti, si sarebbe potuto pensare di investire maggiormente in LSPR per arrivare ad utilizzarlo in contesti come i motori di ricerca per il WWW o nelle reti P2P.
4.1
Misure
E’ necessario stabilire alcune misure da utilizzare come indicatori che riflettano l’effi- cacia e l’efficienza di un sistema di IR; queste misure devono essere necessariamente di tipo quantitativo per poter operare un confronto. Si ricorda che per efficacia si intende la quantità di documenti rilevanti che sono stati reperiti mentre con efficienza ci si riferisce alle risorse computazionali utilizzate e alle funzionalità dell’interfaccia tra l’utente e il sistema. Richiamo e precisione sono le misure d’efficacia di riferimento; chiamando P la precisione, R il richiamo, A il numero di documenti rilevanti ad un’esi-
genza informativa e B il numero di documenti reperiti in risposta ad un’interrogazione, possiamo definire precisione e richiamo come segue:
P =|A ∩ B|
|B| R=
|A ∩ B|
|A| (4.1)
Dalla formula 4.1 si evince che il richiamo si riferisce al numero di documenti rilevanti reperiti tra quelli rilevanti ad un’interrogazione mentre la precisione riguarda la proporzione di documenti rilevanti tra quelli reperiti. Un’altra cosa che è possibile constatare è la relazione inversa che lega P e R; infatti per aumentare il richiamo è necessario reperire una maggiore quantità di documenti e, di conseguenza, ridurre la precisione a meno che ogni documento in più reperito sia rilevante. L’utilizzo dei soli indicatori di richiamo e precisione per valutare un sistema di IR può portare a dei problemi di calcolo; per citare degli esempi, P non è calcolabile qualora nessun documento venga reperito dal sistema così come R non è calcolabile se non è noto il numero di documenti rilevanti ad una certa interrogazione.
Figura 4.1: Calcolo della precisione per due diverse liste di risultati
Una delle misure di efficacia utilizzate durante i test per valutare il motore è il MAP (Mean Average Precision); prima di definirla è necessario introdurre un’altra misura, AP (Average Precision). Quest’ultima è la media dei valori di precisione calcolati ad ogni documento rilevante tra quelli restituiti in risposta ad un’interrogazione; MAP è quindi la media delle precisioni medie non interpolate. Per meglio chiarire come viene calcolato il MAP, si prenda in considerazione la figura 4.1 che riporta i primi 6 documenti reperiti in risposta ad un’interrogazione per due diverse configurazioni di un sistema e con il valore di precisione calcolato ad ogni documento; in questa illustrazione i documenti evidenziati in neretto sono quelli rilevanti. Nell’esempio di figura 4.1 il calcolo di AP per le due configurazioni risulta essere rispettivamente:
1 3· 1 2 + 2 3+ 1 2 =5 9 1 4 · 1 + 1 +3 5 + 2 3 = 49 60 mentre il MAP risulta:
1 2 · 5 9 + 49 60 = 247 360
29 4.1 Misure
Altri indici di efficacia che si sono affermati nell’ambito della valutazione di un sistema di IR sono il CG (Cumulative Gain), ossia il guadagno cumulato medio sul numero di documenti trovati. L’idea alla base di CG sta nel fatto che, scorrendo una lista di risultati ordinata per rilevanza decrescente, ogni volta che si incontra un documento rilevante si accumula un guadagno pari al grado di rilevanza del documento stesso; se al posto della posizione in cui si trova un documento se ne considera il logaritmo in base 2, si ottiene il Discounted Cumulative Gain (DCG). Quanto detto è formalizzato nelle due espressioni seguenti dove i indica la posizione nella lista e ri è
il grado di rilevanza del documento in posizione i: CG= ri
i DCG=
ri
log2i
(4.2) Se i documenti reperiti in risposta ad un’interrogazione vengono ordinati per grado di rilevanza decrescente, si ottiene il valore di DCG ideale, che può essere utilizzato per normalizzare DCG e ottenere la misura chiamata NDCG (Normalized Discounted Cumulative Gain):
N DCG= DCG
DCG∗ DCG
∗= max(DCG) (4.3)
Durante i test di valutazione dei modelli, per valutarne l’efficacia, si è preso in considerazione: MAP, NDGC, la precisione e il NDCG dopo i primi 10 documenti reperiti; questo è stato fatto per avere un’indicazione sulla capacità del modello di posizionare ai primi posti i documenti maggiormente rilevanti.
Trec_Eval
Per poter effettuare la valutazione di diversi sistemi di IR e far in modo che le misure calcolate fossero le stesse per tutti i motori testati, è stato introdotto uno strumento software chiamato Trec_eval. Era necessario, infatti, poter avere una visione standar- dizzata dei risultati ottenuti da un motore di ricerca su una collezione sperimentale; per raggiungere questo obiettivo bisognava sviluppare un programma che consentisse di analizzare i risultati ottenuti dai vari sistemi di IR in modo da poterli confronta- re e avere un’indicazione su quale, tra quelli in esame, avesse le migliori prestazioni. Trec_eval nasce proprio per far fronte a questa esigenza ed è lo strumento che viene utilizzato per valutare un sistema di IR. 1
Il software, per funzionare, ha bisogno di ricevere in input la lista dei primi k documenti (dove k viene scelto da chi effettua la valutazione) reperiti dal motore di ricerca per ciascuno dei topic presenti nella collezione di test e un file contenente i giudizi di rilevanza per i topic considerati. Il file relativo ai giudizi di rilevanza è
1
solitamente chiamato qrels.txt ed è disponibile all’indirizzo web di TREC 2mentre il
file contenente la lista dei primi k documenti reperiti ad ogni topic deve essere prodotto dallo sperimentatore e dovrà avere necessariamente la seguente formattazione:
n_topic O Id_doc rank sim STANDARD
dove i vari campi vanno così interpretati: • n_topic: numero del topic in esame
• O: campo costante, non deve essere modificato
• Id_doc: identificativo TREC del documento reperito dal sistema in risposta al topic n_topic
• rank: posizione che occupa il documento Id_doc nella lista di documenti in risposta al topic n_topic
• sim: valore (float) di similarità fra documento e topic; sim è supposta essere maggiore per i documenti reperiti prima
• STANDARD: campo costante, non deve essere modificato
Una volta che si ha a disposizione il file con i giudizi di rilevanza per ogni topic e che il file con i risultati della valutazione del modello, appositamente formattato, è stato prodotto, è possibile procedere con la fase di valutazione del motore di ricerca. Un esempio di esecuzione del programma Trec_eval è visualizzabile in figura 4.2; per maggiori dettagli sul funzionamento di Trec_eval e sulle varie misure che esso è in grado di fornire si rimanda a [Grossman, 2005]. Durante i test, come già spiegato nella sezione 4.1 le misure di efficacia che sono state considerate sono MAP, NDGC, precisione e NDCG dopo i primi 10 documenti reperiti.
Figura 4.2: Esempio di utilizzo del software trec_eval
2
Il file qrels.txt per la collezione “trec 2001 web trac ad hoc topics” usata nei test è disponibile all’URL http://trec.nist.gov/data/t10.web.html
31 4.2 Collezione sperimentale
4.2
Collezione sperimentale
Uno dei requisiti di base della fase di valutazione è che i risultati ottenuti con diverse configurazioni possano essere confrontati tra loro. Per permettere questo confronto e assicurare che gli esperimenti fatti siano ripetibili è necessario che sia la collezione che le interrogazioni siano le stesse per tutte le configurazioni testate. Inoltre, dato che il calcolo di tutte le misure di efficacia prevede la conoscenza del numero di documenti rilevanti, se questi sono ignoti non è possibile avere indicazioni sulle performance del motore. Per affrontare questi problemi è stato introdotto il concetto di collezione sperimentale (test collection): un insieme di documenti, interrogazioni e giudizi di rilevanza espressi per alcuni documenti reperiti in risposta ad un’esigenza informativa; in questo modo, avendo a disposizione i giudizi di rilevanza per i documenti reperiti a fronte di un’interrogazione, e di conseguenza anche il numero di documenti rilevanti, il calcolo delle misure di efficacia può essere fatto senza problemi.
L’utilizzo di collezioni sperimentali è una pratica comune in IR e nel corso degli anni sono state create diverse collezioni di test che si differenziano soprattutto per la quantità di documenti e interrogazioni presenti e per l’argomento trattato nei docu- menti della collezione. La fase di valutazione consiste in pratica, avendo una collezione sperimentale e un motore di ricerca, nel sottoporre un’esigenza informativa al sistema sviluppato e ottenere quindi una lista di documenti reperiti in risposta all’interrogazio- ne; a questo punto si andranno a confrontare i documenti rilevanti e i rispettivi giudizi di rilevanza con i documenti reperiti dal motore. Più un motore riesce a reperire e posizionare nei primi posti i documenti rilevanti all’esigenza informativa, più il motore è performante.
A livello internazionale, sono diverse le iniziative di valutazione che vengono con- dotte; fra queste vale la pena citare TREC (Text REtrieval Conference), una serie di workshop organizzati dal National Institute of TEchnology (NIST)3 con lo scopo
di definire un modello da utilizzare per la valutazione su grandi moli di documenti, soprattutto di tipo testuale, dei metodi dell’IR. Nel corso degli anni, le collezioni di test prodotte sono cambiate per riflettere i cambiamenti nel comportamento e nelle esigenze di ricerca degli utenti. Per ogni collezione sperimentale prodotta nell’ambito di TREC, sono disponibili delle esigenze informative da soddisfare denominate topic contenenti tre campi principali delimitati da appositi tag. Un esempio di un topic TREC è visibile in figura 4.3 dove si nota la presenza del campo title, supposto essere un’interrogazione di lunghezza ridotta, che rispecchia la tipica esigenza informativa di un utente che opera nel web. Il campo description, invece, non è altro che una versione più lunga dell’interrogazione contenuta in title, fornendo in questo modo un dettaglio
3
maggiore sull’esigenza informativa. Infine, troviamo il campo narrative che descrive i criteri e i requisiti che un documento deve soddisfare affiché possa essere ritenuto rilevante all’esigenza informativa in questione; queste informazioni sono utilizzate da chi dovrà stabilire quali sono e con che grado i documenti rilevanti all’interrogazione.
Collezione Dimensione Numero di
documenti
Numero di in- terrogazioni
CACM 2.2 Mb 3204 64
trec 2001 web trac ad hoc topics 10 Gb 1692096 50
Tabella 4.1: Alcune collezioni sperimentali sviluppate nell’ambito TREC
Figura 4.3: Esempio di un topic TREC
Durante la fase di test di 4IR è stata utilizzata la collezione sperimentale “TREC 2001 web trac ad hoc topics” che fa parte della collezione di test WT10g e conta 1.692.096 documenti e 50 interrogazioni; nella tabella 4.1 sono riportati maggiori dettagli sulla collezione usata per i test ed è presentato un raffronto con un’altra collezione sperimentale, denominata CACM contenente 3.204 documenti e utilizzata in [Costa, 2009] per i test su LSPR. Si è deciso di utilizzare una collezione con quasi 1,7 milioni di documenti proprio perchè, come spiegato in 1.2, lo scopo dei test era quello di verificare se l’efficacia del modello LSPR riscontrata durante la valutazione su un piccolo insieme di documenti, fosse confermata anche quando il modello operava in una collezione più vasta.
33 4.3 Metodologia sperimentale
4.3
Metodologia sperimentale
Quello che si è cercato di fare nella fase di test è stato un confronto fra le prestazioni del modello LSPR e quelle di BM25. Oltre ad un semplice raffronto numerico relativo agli indici di efficacia dei due modelli, è stato fatto anche un test statistico di significatività per vedere se le differenze riscontrate durante la valutazione fossero significative da un punto di vista statistico o dovessero invece essere considerate solo frutto della naturale variabilità dei dati.
In sostanza, scelta una misura di efficacia, ad esempio AP, e ottenuti i valori di AP per tutti i 50 topic della collezione sperimentale e per entrambi i modelli testati, è stato effettuato un test di Student per dati appaiati. L’utilizzo di questo test è stato dettato dal fatto che, disponendo di misure ripetute sulle stesse unità statistiche (i topic), esiste un’associazione tra i valori ottenuti con BM25 e quelli ottenuti con LSPR. In figura 4.4 è riportato il diagramma di dispersione dei valori di AP per LSPR e BM25: l’associazione fra i due modelli appare evidente. Non è possibile
Figura 4.4: Diagramma a dispersione dei valori di AP per LSPR e BM25 quindi utilizzare un test di Student a due campioni ma è necessario applicare il test di Student per dati appaiati che contempla la presenza di un’effetto del topic sui valori di AP ottenuti. I dettagli statistici sull’analisi di significatività sono riportati nella sezione 4.4.3, dove verrà dimostrato che il problema di verificare la differenza di AP nei due campioni sarà affrontato utilizzando un test di Student ad un campione. E’ importante
ricordare che un’assunzione su cui si basa il test vede la normalità dei dati del campione analizzato; è possibile dimostrare tuttavia che il test e le procedure rimangono valide anche se la distribuzione all’interno dei due gruppi non è normale purché la numerosità campionaria sia “sufficientemente grande”. Una semplice regola per stabilire quando una numerosità campionaria può essere ritenuta “sufficientemente grande” suggerisce che i dati presenti nel campione devono essere in numero maggiore o uguale a trenta se la distribuzione dei dati è, almeno approssimativamente, simmetrica. Esistono tuttavia casi in cui, nonostante l’abbondanza delle unità statistiche a disposizione, l’assunzione di normalità per i dati è piuttosto forzata. Nel caso in esame, prima di effettuare il test di Student ad un campione si è effettuata un’analisi esplorativa dei dati indagando anche sull’ipotesi di normalità mediante un procedimento grafico (normal probability plot) e uno analitico (test di normalità di Shapiro-Wilk). Tutti i risultati e i dettagli procedurali sono presentati nella sezione 4.4.3. Inoltre, per potersi svincolare il più possibile da ipotesi sulla distribuzione dei dati, è stato effettuato anche l’equivalente del test di Student per dati appaiati nell’ambito non parametrico, il test di Wilcoxon. Durante la fase di valutazione di LSPR si è proceduto in due direzioni: dapprima è stato effettuato un test considerando come esigenza informativa il testo riportato nel campo title di ogni topic, poi lo stesso test è stato fatto prendendo in considerazione il contenuto di description. Il motivo di questa scelta è che si voleva avere un’idea di come variassero le prestazioni dei modelli BM25 e LSPR passando da un’interrogazione con un numero ristretto di termini (title) ad un’altra più lunga e dettagliata (description). Un’altra prova fatta ha visto l’utilizzo di diversi insiemi di termini da considerare stop word, e quindi da rimuovere, nella fase di analisi dell’interrogazione. Sia per il campo title che per description, infatti, è stata fatta una prima valutazione di BM25 e LSPR considerando come “rumore” un insieme ristretto di termini predefiniti in Lucene; in seconda battuta, invece, è stato ripetuto lo stesso test impostando come stop word tutti i termini portatori di scarso contenuto informativo, raccolti in un file. Il motivo di questa prova è che si voleva analizzare, nei modelli considerati, come variavano le misure di efficacia inserendo o meno alcune stop word nell’esigenza informativa..
Nel seguito verranno presentati i dettagli relativi al settaggio dei parametri di BM25 e LSPR.
4.3.1
Baseline BM25
Partendo dalla formula mediante la quale si ottiene il peso di un termine in un documento nel modello BM25:
wBM25i = T F k1 (1 − b) + bavdldl + T F · log (ri+ 0.5)(|C| − R + ri+ 0.5) (ni− ri+ 0.5)(R − ri+ 0.5) (4.4)
35 4.4 Risultati sperimentali
i valori di T F , N, ni, dl, avdl risultano noti mentre rimangono da settare i pa-
rametri R,ri,b e k1. Come già spigato in 2.3, qualora, come in questo caso, non sia
disponibile alcun indizio sulla rilevanza dei documenti, è sufficiente settare il valore di R e ri a 0. Resta quindi da definire il valore delle costanti b e k1; ricordando i vincoli
0.5 ≤ b ≤ 0.8 e 1.2 ≤ k1 ≤ 2 si è scelto di porre b = 0.8 e k1 = 2. La formula finale
BM25 per calcolare il peso di un termine nel documento risulta quindi essere: wiBM25= T F 2 0.2 + 0.8avdldl + T F · log ((|C| + 0.5) (ni+ 0.5) (4.5)
4.3.2
LSPR
Per quanto riguarda l’algoritmo LSPR, è necessario fornire indicazioni sulla scelta di alcuni parametri del modello. Innanzitutto, nella formula 3.3 si è impostato il valore della frequenza F pari a 2; il motivo di questa scelta è che si vuole garantire l’effetto di dispersione spettrale. Un’altra scelta che è stata fatta, nella 3.2, è stata quella di porre Ai pari al peso IDF del temine i nell’interrogazione; questo è stato
fatto perché, da prove effettuate, con l’utilizzo dello schema di pesatura IDF si è ottenuta l’efficacia migliore. Infine, nella fase di filtraggio, l’ampiezza del filtro è ottenuta moltiplicando una quantità fissa chiamata selettività per il peso del termine nel documento e arrotondando il risultato all’intero più vicino. Si è deciso di impostare il valore di selettività pari a 40; questa scelta è stata fatta perché si è visto che per valori maggiori o minori il MAP diminuisce, come se questo rappresentasse un punto di massimo di una qualche funzione che lega MAP a selettività. Il peso del termine nel documento è stato invece calcolato utilizzando il sistema di pesatura BM25, applicando la formula 4.5.
4.4
Risultati sperimentali
Vengono ora presentati i risultati ottenuti dalla valutazione del modello LSPR e dal suo confronto con la baseline BM25. Una precisazione da fare riguarda il fatto che i risultati esposti sono stati ottenuti rimuovendo dall’interrogazione tutte le stop word più comuni. Infatti, da prove effettuate, si è visto che quando nell’esigenza informati- va sono presenti alcuni termini “rumore” l’efficacia del modello diminuisce; da qui, la necessità di rimuovere tutte le stop word dall’interrogazione nella fase di analisi. Biso- gna evidenziare però, come tale scelta abbia portato ad alcuni problemi in un topic, per la precisione il numero 531; esso, presentando nel campo title una stringa forma- ta esclusivamente da stop word, porta l’algoritmo LSPR ad eliminare tutti i termini dell’interrogazione durante la fase di analisi. Solo nel caso del test su title, quindi, il