L'analisi frequentistica delle occorrenze, tipica dei modelli di ranking di information retrieval, puo` 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, perche´ entrambe hanno l'obiettivo di assegnare dei pesi di rilevanza alle singole parole di un documento, e sembrano complementari, perche´ si basano su metodologie differenti. Tuttavia finora esse sono progredite in modo separato. L'obiettivo di questa ricercae` di favorire una loro riconciliazione. I contributi principali del lavoro sono tre: (a) estensione del metodo basato sull'interspaziatura mediante analisi di corpora, (b) verifica sperimentale che la pesatura quantisticae` 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 esperimentie` che il metodo quantistico da solo non funziona bene, ma che il metodo combinato consente di migliorare in modo significativo le prestazioni del metodo classico frequentistico. Un ulteriore risultato riguarda le potenzialiat` di applicazione selettiva dei due metodi di pesatura: buone in funzione della lunghezza dei documenti recuperati, modeste rispetto alla dicffiolat` stimata delle interrogazioni. 1
Ordinare i documenti di una collezione per pertinenza a fronte di una richiesta d’utentee` il problema chiave dell’Information Retrieval. Nel corso degli ultimi decenni sono stati ideati numerosi modelli di ranking (vettoriale, probabilistico, basato sulla modellazione del linguaggio, o sullo scostamento dalla casualiat`), che tipicamente assegnano un punteggio o una probabiliat` 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 lavoroe` 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’Universiat` Roma Tre nel luglio 2011. progressi degli ultimi anni peor`, i margini per ulteriori miglioramenti nelle tecniche tradizionali di ranking si sono ridotti: un avanzamento sostanziale ormai saar` difficile che avvenga senza un vero e proprio cambiamento di paradigma.
Parallelamente, nell’ultimo decennio sie` sviluppato un ramo della ricerca riguardante l’estrazione delle parole rilevanti di un testo che prescinde dalla frequenza 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 occorrenze di uno stesso termine. Un ruolo fondamentalee` giocato dalle forze di attrazione e repulsione cui sono soggette le singole occorrenze di un termine. Pui` il terminee` rilevante, maggioree` lattrazione fra sue occorrenze, quindi pui` tali parole si concentrano in aree determinate del documento, generando la formazione di clusters; viceversa, pui` un terminee` comune e poco rilevante, pui` deboli sono queste forze, per cui il termine si distribuisce uniformemente lungo tutto il testo.
Ortun˜o et al. [
Fra queste due aree di ricerca, quella frequentistica e quella quantistica, esiste una forte connessione, perche´ 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 comuniat`, di information retrieval e di fisica dei quanti, senza cercare di analizzare i rispettivi vantaggi e svantaggi o di combinarle per trovare un approccio pui` potente di quelli singoli. Da questa osservazione e` scaturita la nostra ricerca. L’obiettivoe` il tentativo di cominciare a riconciliare questi due approcci.
La prima area di interventoe` 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 capaciat` di discriminazione di un termine. Il secondo tema chee` stato studiatoe` la complementarieat` dei ranking prodotti dalle metriche quantistiche e da quelle frequentistiche (in particolare quelle basate su tf-idf). Innfie, dati gli esiti deludenti dell’applicazione diretta delle metriche quantistiche, con o senza estensione, al ranking dei documenti, abbiamo fatto una serie di esperimenti 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 articoloe` strutturato nel seguente modo. Dopo avere ricapitolato l’approccio quantistico alla pesatura dei termini, coı sc`ome presentato in letteratura, introduciamo la sua estensione basata sulle variazioni di frequenza nel corpus. Successivamente, viene discussa la combinazione di pesatura quantistica estesa e pesatura tradizionale ai fini del ranking, presentando una serie di esperimenti su due collezioni campione. Infine, viene discussa la possibiliat` di un uso selettivo delle due metriche di pesatura guidato da lunghezza dei documenti e difficolat` delle interrogazioni.
occorrenze: σ p Il fenomeno della diversa distribuzione spaziale di parole rilevanti e non rilevanti e` illustrato in Figura 1. I gracfii 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. Coi` accade indipendentemente dal numero di occorrenze, perche´ queste parole hanno nel ranking delle frequenze posizioni differenti. Simmetricamente, le occorrenze di parole non rilevanti, quali the (chee` il termine con maggiore frequenza nel testo), sono equidistribuite.
Da un punto di vista sfiico, nel caso di una parola chiave ogni livello d’energia attrae se stesso. La controparte linguistica di questo comportamentoe` che un termine rilevantee` di solito il soggetto principale in un contesto locale di un documento, percoi` occorre con maggiore frequenza in qualche area del testo e minore in altre, generando il fenomeno di clustering. Invece, nel caso di parole non rilevanti tali livelli d’energia risultano scorrelati, corrispondentemente al fatto che tali parole si distribuiscono attraverso l’intero documento senza caratterizzarne in modo specicfio nessuna parte.
Per quanticfiare questo fenomeno si utilizza il seguente approccio. Ogni occorrenza di un terminee` 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 energiae` 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 μ : (1) (2) (3) (4)
Se la parolae` distribuita in modo casuale (random) lungo il testo, la distribuzione P1, nel limite continuo, saar` una distribuzione Poissoniana:
Se invece il termine respinge se stesso (quindie` distribuito uniformemente
lungo tutto il testo) allora la sua distribuzione P1 saar` pui` piccola di quella di
Poisson per μ < 1. Viceversa, se il termine attrae se stesso, P1 saar` pui` grande
della distribuzione di Poisson per brevi distanze (per un trattamento
probabilistico piu approfondito si rimanda a [
Il calcolo della funzione di distribuzione P1 per tutte le parole di un testoe` molto oneroso dal punto di vista computazionale. Per questo motivo, al posto di P1, viene utilizzata la deviazione standard s: μ =
1 n + 1 · n X (xi+1 − xi) = i=0 xn+1 − x0 n + 1
Denotando con p(x) la frequenza relativa di occorrenza di una data distanza x, la sua funzione di distribuzione integrata P1(x)e:`
P1(x) =
X p(x0 ) x0 <x
P1(μ ) = 1 − exp(− μ ) s =
1 n − 1 · n X ((xi+1 − xi) − μ )2 i=0
Per eliminare la dipendenza dalla frequenza per differenti parole, la deviazione standard viene normalizzata rispetto al corrispondente valore medio delle distanze moltiplicato per √1 − p: dove ne` il numero di occorrenze della parola w all’interno del documento e Ne` il numero totale di parole nel testo. Questa funzionee` molto semplice da calcolare e si dimostra robusta contro le oscillazioni. Le parole con il valore di σ p pui` elevato saranno quelle pui` importanti.
Numerose analisi e modicfihe di σ p sono state proposte. Uno dei lavori piu
importantie` [
I tentativi presenti in letteratura hanno cercato di presentare dei correttivi alla funzione σ p senza peor` abbandonare l’assunzione di base, e cieo` che l’ordinamento dei termini viene costruito soltanto analizzando il particolare testo che si sta considerando. Mentre questa assunzione puo` essere utile in determinate situazioni, sembra ragionevole cercare di estendere l’approccio quantistico utilizzando informazioni aggiuntive sulla importanza dei singoli termini basate sull’analisi di corpora, la disponibiliat` di corpora essendo oggigiorno vasta.
In particolare, noi proponiamo di correggere la metrica originaria con un
fattore che abbia un duplice obiettivo: penalizzare le parole rare, perche´ in collezioni
reali queste spesso costituiscono ”rumore”, e premiare le parole che riescono a
discriminare meglio il testo in osservazione da altri testi, capaciat` questa che
manca completamente nella pesatura quantistica. Il nostro approccio prende lo
spunto da una metrica ben nota in information retrieval, la deviazione standard
delle frequenze dei termini [
1 N D · n X fi(w) i=1
Si noti che NDe` il numero totale di documenti della collezione: vengono considerate quindi anche le frequenze nulle, cieo` i documenti in cui la parola non compare. La deviazione standard delle frequenze sf sara’ data da: sf (w) =
1 N D · n X (fi(w) − μ f )2 i=1
Chiaramente, sf assumear` valori piccoli nel caso in cui la distribuzione di frequenzae` uniforme (con fi circa uguale a μ f ) o il termine appare in pochissimi documenti (essendo la maggior parte degli fi uguali a zero e μ f circa uguale a zero). Viceversa, sf saar` grande quando la distribuzione di frequenza presenta forti variazioni a fronte di una frequenza media apprezzabile. Queste caratteristiche sembrano in grado di compensare i limiti di σ p.
La deviazione standard puo` essere poi normalizzata rispetto al corrispondente valore medio delle frequenze μ f , come visto in precedenza nel caso della pesatura quantistica: vettore delle frequenze fi, freq(w) = f1, ..., fND relativo a una ad una parola w negli ND documenti della collezione., La media delle frequenze μ f e:` (6) (7) (8) (9) σ f = sf μ f
Nel complesso, questo approccio ha l’ulteriore vantaggio che il suo razionalee` analogo a quello impiegato per sviluppare la funzione di pesatura originale σ p. In questo caso i livelli di energia di una parola non corrispondono pui` alla posizione delle sue occorrenze in un testo, benı sa`lle frequenze in ciascun documento della collezione. Pertanto, l’analogia in questo casoe` fra lo spettro di energia dei sistemi di quanti disordinati e l’insieme delle frequenze che una certa parola assume nella collezione.
La funzione di pesatura quantistica estesa σ ∗ , relativa ad una singola parola, e` data dal prodotto di σ p e σ f :
σ ∗ (w) = σ p(w) · σ f (w)
Per farsi un’idea pui` precisa delle caratteristiche dei termini estratti da testi lunghi mediante metriche frequentistiche e quantistiche, nonche´ del loro grado di complementarieat`, abbiamo svolto il seguente esperimento. Come metrica di pesatura frequentistica abbiamo scelto tf-idf, chee` semplice ed ha una valenza paradigmatica in information retrieval, nelle due versioni con e senza stop words (denotate rispettivamente tf-idf e tf-idf*), e come metriche quantistiche σ p e σ ∗ . Abbiamo utilizzato come testo The Bible2 e come corpus di riferimento per
calcolare i valori tf-idf e σ f la collezione TREC WT10g, pre-elaborarata secondo quanto descritto nella Sezione 5.
I risultati sono mostrati in Tabella 1. La metrica tf-idf ha riportato nelle prime posizioni molte stop words arcaiche, poiche´ queste parole, oltre ad avere un valore elevato di tf nel testo originario, hanno conseguito anche un alto valore di idf nella collezione di riferimento (costituita da testi moderni). La metrica tfidf* (cieo` con rimozione di stop words) ha funzionato molto meglio, anche se ha restituito diversi termini generici nelle prime dieci posizioni, quali ad esempio ”son”, ”king”, ”man”, ”land”, ”men”. Le parole estratte da σ p sembrano invece pui´ precise nel descrivere il contenuto della Bibbia, e consentono di identificare molti concetti e nomi propri importanti. Passando a σ ∗ , si nota che le parole diventano ancora pui´ specifiche (anche se non si tratta di termini rari in un testo come la Bibbia) e corrispondono a brani pui´ circoscritti all’interno del libro. Alcuni di questi termini hanno conseguito un alto valore di σ ∗ non solo in virut´ della loro elevata concentrazione nella Bibbia ma anche per l’infrequenza con la quale appaiono nel corpus, secondo quanto gai´ evidenziato nella discussione di tfidf. Nel complesso le parole estratte da σ ∗ sono meno caratterizzanti al livello del testo globale ma hanno sicuramente una maggiore capaciat` di discriminazione (ad esempio rispetto ad altri testi di carattere religioso).
Se poi confrontiamo la somiglianza dei ranking prodotti dalle diverse metriche, ci accorgiamo che metriche frequentistiche e quantistiche restituiscono termini molto differenti. Considerando i primi 100 termini, ci sono 15 termini in comune fra σ p e i due tf-idf, che scendono a due con σ ∗ , precisamente ”jesus” e ”saul”. Inoltre, i pochi termini in comune hanno posizioni molto differenti. Ad esempio, la parola ”jesus”, che usando σ p e σ ∗ compare nella prima posizione, viene invece classicfiata rispettivamente in quarantesima e quindicesima posizione da tf-idf e tf-idf*. Questi risultati indicano chiaramente che i ranking prodotti dai due tipi di ordinamento sono completamente scorrelati, in particolar modo quando si considera σ ∗ invece di σ p, anche se bisogna sottolineare che i nostri esperimenti sono stati effettuati su un testo lungo che non contiene errori. I testi che vengono tipicamente considerati nelle applicazioni di information retrieval sono invece brevi e rumorosi. Nelle prossime sezioni verranno presentati una serie di esperimenti con la seconda tipologia di dati. 4
La metrica σ ∗ puo essere adoperata per fare il ranking di una collezione di documenti rispetto ad una interrogazione q, semplicemente sommando i valori relativi a tutti i termini di q presenti nel documento. Il punteggio σ ∗ (d, q) conferito al generico documento d saar` dato da: σ ∗ (d, q) =
X σ ∗ (w) w∈q
Vista la complementarieat` delle metriche di pesatura quantistica e frequentistica, un approccio naturalee` quello di cercare di integrare le due tecniche. Uno dei modi pui` intuitivie` fare una combinazione lineare dei punteggi assegnati dalle due tecniche a ciascun documento, preceduta da una normalizzazione degli stessi. Lo schema di normalizzazione adoperatoe` stato il seguente: Il punteggio finalee` dato da: weightNORM =
weight − weightMin weightMax − weightMin score = α · scoreBM25 + (1 − α ) · scoreσ ∗ 5
Come collezioni di prova abbiamo utilizzato la WT10g e la Robust, due collezioni sviluppate in ambito TREC. La prima contiene oltre un milione e mezzo di pagine web, la seconda circa 500 mila documenti estratti da varie sorgenti informative. Per WT10g sono state utilizzate le 50 topics 501-550, mentre per la collezione Robust sono state usate 250 queries, le topics 301-450 che sono quelle del track ”ad hoc” delle TREC 6-8, e le topics 601-700 del track ” robust” delle TREC 2003-2004. Su queste collezionie` stata applicata una riduzione dello spazio dei termini, sia per rendere piu` efficiente l’esecuzione degli esperimenti sia per cercare di migliorare l’efficacia attraverso una riduzione del rumore insito nei testi (abbreviazioni, refusi, ecc.). In particolare sono state rimosse le parole contenute in meno di dieci documenti, e quelle che contenevano piu` di tre caratteri consecutivi uguali o che erano lunghe piu` di venti caratteri. Tale procedimento ha portato l’insieme di documenti WT10g ad avere 435.744 invece di 5.167.898 di termini distinti (considerando anche i numeri interi), mentre per la Robust siamo passati da 1.178.484 a 485.326. Per quest’ultima collezione peor` abbiamo notato che per alcune topics c’era soltanto un documento che conteneva i (10) (11) (12) termini corrispondenti; eliminando la restrizione sulla frequenza dei documenti siamo passati a 835.760 termini.
Come sistema di indicizzazione e ricercae` stato utilizzato Lucene, 3 con l’estensione a BM25 fornita da Perez-Iglesias4. Lucenee` stato adoperato sia per calcolare il ranking secondo BM25, sia per fornire i documenti di input (tutti quelli che contenevano almeno una parola dell’interrogazione) alle routine sviluppate per calcolare il ranking secondo σ ∗ e il successivo ranking integrato σ ∗ + BM25. Il valore di α usato negli esperimenti (= 0,8)e` stato determinato utilizzando le topics 451-500, viste come al training set di WT10g.
In Tabella 2 sono riportate le prestazioni dei tre metodi di ranking, cieo` BM25, σ ∗ e la loro combinazione BM25+σ ∗ , su ciascuna delle due collezioni.5 BM25 va molto meglio di σ ∗ , probabilmente a causa del fatto che i documenti rilevanti sono di lunghezza ridotta, ma il metodo combinato ha ottenuto le prestazioni migliori in tutti e due i casi, con un miglioramento piuttosto netto anche rispetto a BM25. La differenza fra le prestazioni del metodo integrato e di BM25 sono statisticamente significative utilizzando il T-Test.
Per esaminare meglio le prestazioni relative dei tre metodi, abbiamo calcolato il valore di MAP sulle singole interrogazioni. In Figura 2 abbiamo graficato i risultati per le interrogazioni di WT10g. In questo caso il metodo combinato migliora in 28 casi e peggiora nei rimanenti 22, rispetto a BM25. I risultati per Robust sono leggermente differenti, perche´ a fronte di un miglioramento medio percentuale piu contenuto, la robustezza rispetto alle singole interrogazioni aumenta: 197 i miglioramenti, 53 i peggioramenti.
Per valutare la robustezza del metodo rispetto al parametro α abbiamo ricalcolato le prestazioni facendo variare il valore di α nell’intervallo fra uno e zero, i due estremi coincidendo rispettivamente con BM25 e σ ∗ . I risultati, mostrati in Tabella 3, suggeriscono chiaramente che il metodoe` sufficientemente robusto, perche´ ce’` un intervallo di valori per i quali le prestazioni si mantengono elevate, e questo comportamentoe` riscontrabile su entrambe le collezioni.
4 http://nlp.uned.es/ jperezi/Lucene-BM25/ 5 Abbiamo fatto una serie di esperimenti per valutare le potenzialiat` per il ranking anche della metrica σ p, sia da sola, sia in combinazione con BM25, sia infine come riordinamento del ranking prodotto da BM25. I risultati peor` sono stati insoddisfacenti.
Finora abbiamo considerato l’ipotesi di combinare la pesatura frequentistica e quantistica in modo sistematico, per ciascuna interrogazione e su tutta la collezione. Poiche peor` pesatura quantistica e frequentistica hanno caratteristiche e requisiti differenti, ci siamo chiesti see` possibile prevedere una utilizzazione selettiva dei due paradigmi di ranking in funzione di determinate caratteristiche dei documenti e dell’interrogazione. La prima variabile che abbiamo consideratoe` stata la lunghezza dei documenti, perche´ il metodo quantistico dovrebbe andare meglio sui testi lunghi. Vogliamo valutare se effettivamente la metrica quantisticae` pui` efficace nel recuperare i documenti lunghi e quella frequentistica i documenti brevi.
A questo scopo abbiamo riportato due gracfii relativi a WT10g, uno per BM25 e uno per σ ∗ , in cui sull’asse x ci sono i valori della lunghezza del documento in numero di parole, mentre sull’asse ye` riportata la percentuale di documenti rilevanti (nei due casi in cui vengano ritrovati o non ritrovati) che hanno meno del corrispondente numero di parole dell’asse x. Ad esempio, il gracfio di sinistra mostra che per i documenti rilevanti di lunghezza < 2000, i ritrovati da BM25 sono l80% del totale dei rilevanti ritrovati e solo il 60% dei rilevanti non ritrovati. Risulta quindi confermato che gli andamenti sono opposti a seconda della metrica che si considera. Questi risultati sono incoraggianti dal punto di vista di un’applicazione selettiva guidata dalla lunghezza dei documenti. Lo sviluppo e la sperimentazione di un metodo di pesatura basato su queste osservazionie` stato lasciato come lavoro futuro.
La seconda variabile per l’applicazione selettiva che abbiamo consideratoe`
stata la difficolat` stimata delle interrogazioni. La speranza era che le metriche
fossero efficaci in modo inverso rispetto a quest’ultima, in particolare che la
pesatura quantistica conseguisse buone prestazioni sulle topics ritenute piu difficili.
Abbiamo utilizzato due noti predittori pre-retrieval: Simpliefid Clarity Score [
In questo lavoro abbiamo cercato di riconciliare la pesatura quantistica delle
parole, basata sull’interspaziatura delle occorrenze e sviluppata prevalentemente
nell’ambito della fisica, e la pesatura frequentistica adottata in information
retrieval. Abbiamo visto che le due tecniche sono essenzialmente complementari
e che la loro combinazione puo` migliorare sia la pesatura quantistica,
incorporando statistiche legate all’analisi di corpus, sia quella frequentistica, per trovare
termini rilevanti che sfuggono ai normali criteri basati su tf-idf. In una serie di
esperimenti preliminari abbiamo dimostrato chee` possibile migliorare il ranking
attraverso una semplice combinazione delle due metriche, anche se le potenzialiat`
di questo approccio sono ancora in gran parte da investigare. Oltre al ranking,
questa tecnica puo` essere utilizzata per migliorare altri classici compiti di
information retrieval nei quali l’individuazione delle parole chiave presenti in uno
o pui` documentie` cruciale ede` stata nfiora affrontata con tecniche
frequentistiche, in particolare la diversicfiazione e il clustering dei risultati [