Estensione dei metodi di ranking mediante analisi dell’interspaziatura fra occorrenze Maria C. Daniele, Claudio Carpineto, and Andrea Bernardini Fondazione Ugo Bordoni, Rome, Italy mariac.daniele@gmail.com, carpinet@fub.it, aberna@fub.it Abstract. L’analisi frequentistica delle occorrenze, tipica dei modelli di ranking di information retrieval, può essere integrata con l’analisi della spaziatura fra le occorrenze di una singola parola, mutuata dallo studio dei livelli di energia dei sistemi statistici di quanti disordinati. Queste due aree di ricerca sono fortemente interrelate, perché entrambe hanno l’obiettivo di assegnare dei pesi di rilevanza alle singole parole di un documento, e sembrano complementari, perché si basano su metodolo- gie differenti. Tuttavia finora esse sono progredite in modo separato. L’obiettivo di questa ricerca è di favorire una loro riconciliazione. I con- tributi principali del lavoro sono tre: (a) estensione del metodo basato sull’interspaziatura mediante analisi di corpora, (b) verifica sperimen- tale che la pesatura quantistica è scorrelata da quella frequentistica, (c) studio della combinazione ottimale dei pesi quantistici e frequentistici ai fini del miglioramento delle prestazioni del ranking. Il risultato principale dei nostri esperimenti è che il metodo quantistico da solo non funziona bene, ma che il metodo combinato consente di migliorare in modo sig- nificativo le prestazioni del metodo classico frequentistico. Un ulteriore risultato riguarda le potenzialità di applicazione selettiva dei due metodi di pesatura: buone in funzione della lunghezza dei documenti recuperati, modeste rispetto alla difficoltà stimata delle interrogazioni.1 1 Introduzione Ordinare i documenti di una collezione per pertinenza a fronte di una richi- esta d’utente è il problema chiave dell’Information Retrieval. Nel corso degli ultimi decenni sono stati ideati numerosi modelli di ranking (vettoriale, prob- abilistico, basato sulla modellazione del linguaggio, o sullo scostamento dalla casualità), che tipicamente assegnano un punteggio o una probabilità a ciascun documento basandosi su una valutazione dell’importanza che i singoli termini dell’interrogazione rivestono nei documenti che li contiene. Le grandezze sulle quali si basano la maggior parte di questi modelli dipendono dalle frequenze con le quali i termini compaiono nei singoli documenti e nell’intera collezione. Coi 1 Questo lavoro è basato sulla tesi di laurea magistrale in ingegneria informatica di Maria Daniele ”Sperimentazione di tecniche d’Information Retrieval basate sulla Fisica dei Quanti”, svolta presso la Fondazione Ugo Bordoni e discussa all’Università Roma Tre nel luglio 2011. progressi degli ultimi anni però, i margini per ulteriori miglioramenti nelle tec- niche tradizionali di ranking si sono ridotti: un avanzamento sostanziale ormai sarà difficile che avvenga senza un vero e proprio cambiamento di paradigma. Parallelamente, nell’ultimo decennio si è sviluppato un ramo della ricerca riguardante l’estrazione delle parole rilevanti di un testo che prescinde dalla fre- quenza delle parole. Tale approccio, nato da studi sui livelli di energia dei sistemi statistici di quanti disordinati, si basa sull’analisi dell’interspaziatura fra le oc- correnze di uno stesso termine. Un ruolo fondamentale è giocato dalle forze di attrazione e repulsione cui sono soggette le singole occorrenze di un termine. Più il termine è rilevante, maggiore è lattrazione fra sue occorrenze, quindi più tali parole si concentrano in aree determinate del documento, generando la for- mazione di clusters; viceversa, più un termine è comune e poco rilevante, più deboli sono queste forze, per cui il termine si distribuisce uniformemente lungo tutto il testo. Ortuño et al. [6] sono stati i primi a mostrare che in un testo la distribuzione spaziale di una parola rilevante è molto diversa da quella corrispondente a una non rilevante, postulando un’analogia tra il linguaggio naturale e il linguaggio del DNA. In seguito, ci sono state altre proposte derivate da quella pioneristica di Ortuño et al., ad esempio [9], [5], e [1]. In [9] vengono accertate alcune limitazioni dell’indice di pesatura ideato da Ortuño et al. sulle quali ritorneremo in seguito. Una caratteristica importante di tutte queste tecniche quantistiche è che non serve una collezione esterna da analizzare: esse si basano esclusivamente sul contenuto dei singoli documenti. Fra queste due aree di ricerca, quella frequentistica e quella quantistica, es- iste una forte connessione, perché entrambe puntano ad assegnare un peso di rilevanza ai singoli termini di un documento. Tuttavia, esse sono state portate avanti in modo esclusivo nelle due comunità, di information retrieval e di fisica dei quanti, senza cercare di analizzare i rispettivi vantaggi e svantaggi o di combina- rle per trovare un approccio più potente di quelli singoli. Da questa osservazione è scaturita la nostra ricerca. L’obiettivo è il tentativo di cominciare a riconciliare questi due approcci. La prima area di intervento è stata l’estensione della pesatura quantistica con statistiche estratte da un corpus (considerando in particolare le variazioni della frequenza di ciascun termine rispetto all’insieme dei documenti), ai fini di premiare la capacità di discriminazione di un termine. Il secondo tema che è stato studiato è la complementarietà dei ranking prodotti dalle metriche quan- tistiche e da quelle frequentistiche (in particolare quelle basate su tf-idf). Infine, dati gli esiti deludenti dell’applicazione diretta delle metriche quantistiche, con o senza estensione, al ranking dei documenti, abbiamo fatto una serie di esper- imenti per valutare l’efficacia di una combinazione dei due metodi. I risultati sono stati incoraggianti, con prestazioni migliori di quelle ottenibili con i metodi convenzionali di information retrieval (in particolare BM25). Il seguito di questo articolo è strutturato nel seguente modo. Dopo avere ri- capitolato l’approccio quantistico alla pesatura dei termini, cosı̀ come presentato in letteratura, introduciamo la sua estensione basata sulle variazioni di frequenza Fig. 1. Analisi spettrale e rank dei termini istinct, life, natural e the, estratte dal testo di Charles Darwin The Origin of Species” [6]. nel corpus. Successivamente, viene discussa la combinazione di pesatura quan- tistica estesa e pesatura tradizionale ai fini del ranking, presentando una serie di esperimenti su due collezioni campione. Infine, viene discussa la possibilità di un uso selettivo delle due metriche di pesatura guidato da lunghezza dei documenti e difficoltà delle interrogazioni. 2 Pesatura delle parole basata su interspaziatura fra occorrenze: σp Il fenomeno della diversa distribuzione spaziale di parole rilevanti e non rilevanti è illustrato in Figura 1. I grafici sono relativi al testo The Origin of Species di Charles Darwin. Le occorrenze di parole rilevanti, come istinct, natural, e life, hanno distribuzione non omogenea e tendono a unirsi (fenomeno d’attrazione) formando dei clusters. Ciò accade indipendentemente dal numero di occorrenze, perché queste parole hanno nel ranking delle frequenze posizioni differenti. Sim- metricamente, le occorrenze di parole non rilevanti, quali the (che è il termine con maggiore frequenza nel testo), sono equidistribuite. Da un punto di vista fisico, nel caso di una parola chiave ogni livello d’energia attrae se stesso. La controparte linguistica di questo comportamento è che un termine rilevante è di solito il soggetto principale in un contesto locale di un doc- umento, perciò occorre con maggiore frequenza in qualche area del testo e minore in altre, generando il fenomeno di clustering. Invece, nel caso di parole non ril- evanti tali livelli d’energia risultano scorrelati, corrispondentemente al fatto che tali parole si distribuiscono attraverso l’intero documento senza caratterizzarne in modo specifico nessuna parte. Per quantificare questo fenomeno si utilizza il seguente approccio. Ogni oc- correnza di un termine è considerata come un livello di energia che si trova all’interno di uno spettro energetico formato da tutte le occorrenze della data parola nel testo che si sta analizzando. Ogni valore del livello di energia è dato semplicemente dalla posizione che il termine ha nel documento. In pratica, per una data parola w, si estraggono le posizioni corrispondenti, creando il vettore x(w) = x1 ,..., xn (ogni xi corrisponde ad un livello di energia). Ad esempio, nella frase ”a great scientist must be a good teacher and a good researcher”, per la parola ”a” si estrae il vettore di posizioni x(a) =1,6,10. Si considera, poi, il vettore delle distanze di , dist(w) = d1 ,...,dn , con di = xi+1 - xi , tra le occorrenze consecutive della parola w e si calcola la corrispondente media delle distanze µ: n 1 X xn+1 − x0 µ = · (xi+1 − xi ) = (1) n + 1 i=0 n+1 Denotando con p(x) la frequenza relativa di occorrenza di una data distanza x, la sua funzione di distribuzione integrata P1 (x) è: X 0 P1 (x) = p(x ) (2) x0