Dopo aver visto le basi delle tecniche di Query Expansion, in questo secondo articolo ci occuperemo delle metodologie di analisi e di correlazione tra i termini del corpus dei documenti e quelli delle query, alla cui base vi è il concetto di “vettorializzazione”
La “vettorializzazione” è la rappresentazione dei vocaboli come vettori in uno spazio n-dimensionale. Il vantaggio di questo tipo di rappresentazione sta nel fatto che la correlazione tra vocaboli si esprime in termini di proprietà geometriche dei vettori. In particolare verranno introdotte le principali tecniche di Global Analysis, così denominate perch� prendono in esame relazioni tra vocaboli delle query e del corpus dei documenti considerando il corpus dei documenti nella sua interezza, e Local Analysis, così denominate perch� prendono in esame relazioni tra vocaboli della query e del corpus dei documenti considerando i soli documenti meglio classificati del corpus.
Introduzione
In molte metodologie di Query Expansion il significato dei vocaboli e la composizione dei documenti di testo del corpus vengono rappresentati in forma vettoriale da valori caratterizzanti i termini ad essi associati. Mediante la trasformazione vettoriale del significato dei termini risulterà possibile riferirsi a ciascun vocabolo come a un punto nello spazio multidimensionale. Essendo il vettore cosi definito, apparirà evidente che due termini simili saranno rappresentati da due vettori molto simili tra loro. Il grado di tale somiglianza potrà essere calcolato avvalendosi delle proprietà geometriche dei vettori.
In letteratura, esistono molti framework per traduzione delle parole nello spazio multidimensionale, tra questi Latent Semantic Analysis (LSA) e Hyperspace Analogue to Language (HAL)[1]. Nel processo di traduzione viene mantenuto il presupposto che vocaboli dal significato simile occorrono in un contesto simile. In molte tecniche, come in quella approfondita qui, viene usata una matrice per mantenere l’associazione tra il contesto e il termine stesso mediante la loro co-occorrenza statistica. Grazie a tale rappresentazione matriciale, con semplici tecniche algebriche relative alle matrici, risulta possibile rilevare le relazioni dirette o indirette tra i termini ed il loro contesto. Una di queste tecniche è denominata Singular Value Decomposition (SVD). Questa posiziona i termini in uno spazio altamente dimensionale a k dimensioni, con k parametrizzabile, dove contesti simili sono rappresentati da regioni simili nello spazio.
L’informazione contenuta all’interno di una query deve essere estratta dalla domanda stessa e collocata nel modello più opportuno. L’elemento che rende possibile tale differenziazione consiste nella forma in cui si presenta l’informazione stessa all’interno della query stessa.
Preferenze dell’utente indirette
Spesso le query formulate dagli utenti espongono in modo indiretto delle loro preferenze. Questo assume che il ricevente conosca le preferenze del suo interlocutore oppure che sappia interpretarle. Le preferenze possono differenziarsi in personali, temporali o spaziali. In base alla loro tipologia dovranno essere associate al modello opportuno. Le preferenze personali a loro volta possono essere generali o specifiche del dominio, per aggiungere tali preferenze dovrà essere usato il modello d’utente. Le preferenze spaziali e temporali risultano specificare l’informazione in maniera indiretta e relativa al contesto in cui viene espressa; ad esempio “Indicami il Ristorante più vicino”. Solo se comparirà nella frase un riferimento assoluto, ad esempio un luogo, la preferenza sarà indicata in maniera diretta. In questo caso i modelli da impiegare per contenere l’informazione sono quello spaziale e quello temporale.
Informazioni mancanti
Vengono definite mancanti le informazioni che risultano essere obbligatorie per l’analisi esaustiva della query in un particolare sistema, se presupposte possono essere aggiunte dal sistema (ad esempio il luogo di partenza di un volo al momento della prenotazione). Queste informazioni per poter essere identificate devono essere note e soprattutto richieste dal sistema stesso. Identificate tali informazioni, esse vengono aggiunte al modello d’utente per indicarne la sua preferenza.
Preferenze d’utente a breve termine
Questo tipo di preferenza può essere memorizzata nel modello d’utente come parte del profilo d’utente e può variare nel tempo. Al momento della valutazione della query tali conoscenze temporanee possono essere unite alla query originaria per completare la richiesta dell’utente.
Preferenze d’utente a lungo termine
Allo stesso modo il modello d’utente può contenere informazioni riguardanti un contesto più ampio di quello della semplice query. Tuttavia queste conoscenze possono essere usate per l’espansione in aggiunta alle preferenze dell’utente relative alla domanda in esame.
A supporto di tali metodologie di analisi dei termini, sono state sviluppate altre tecniche per l’analisi dell’occorrenza dei termini in relazione alla struttura del corpus di documenti ricercati. Queste tecniche prendono il nome di global analysis e local analysis. La prima fornisce un’analisi dell’occorrenza delle parole e delle loro relazioni considerando il corpus dei documenti per intero: le informazioni ottenute da tale analisi potranno essere impiegate per l’espansione di qualsiasi query. La local analisys limita l’analisi ai soli k documenti del ranking, ovvero i documenti classificati meglio e di conseguenza ritenuti rilevanti, ricavando informazione necessaria alla rivalutazione del peso e dell’espansione delle query analizzate.
Global Analisys
Tecniche molto note di global analysis includono Term Clustering, Phrase-finder, Latent Semantic Indexing e Similarity Thesaurus [2] [3].
Term Clustering
L’idea che risiede alla base dell’analisi globale è la nozione del contesto globale dei concetti, il quale viene adottato come metro di misura nella determinazione del grado di similitudine tra i concetti. Una prima definizione del problema definisce le parole come concetti e il contesto di una parola come tutte le parole che co-occorrono nel documento con tale termine. Mediante questa tecnica la global analysis è impiegata esclusivamente come metodologia d’espansione della query senza andare a modificare la struttura originale delle parole del documento.
Una variante di questo approccio prevede il raggruppamento dei termini in gruppi (Term Clustering) per determinare il contesto per l’analisi dei documenti. Bisogna ricordare che il Term Clustering individua i gruppi di somiglianza mediante l’utilizzo di una matrice simmetrica e successivamente opera l’espansione semplicemente aggiungendo i cluster ai termini in esame.
Phrasefinder
Un’altra definizione del problema è presentata nell’ambito della tecnica Phrasefinder (dizionario dei termini usato nel sistema INQUERY). Il concetto viene qui definito come gruppo di sostantivi, mentre il contesto come la finestra di dimensione fissa nel’intorno del concetto stesso. Quest’ultima tipicamente fissata alla dimensione da una a tre frasi.
Analizziamo meglio questa tecnica. Se consideriamo ogni concetto come gruppo di sostantivi risulta possibile associare ciascun concetto a pseudo-documenti correlati con l’informazione espressa dal concetto in esame. Questi documenti saranno quindi composti da concetti, ovvero da parole che occorrono in ogni finestra associata al concetto esaminato nel corpus di documenti.
Per poter eseguire l’espansione della query, al posto dell’usuale lista di nomi di documenti o termini viene adottata una lista ordinata dei concetti di frase, ottenuta a seguito dell’interrogazione del database dei concetti mediante l’uso del sistema INQUERY. Liste ordinate mediante ranking sono ottenibili mediante associazione di pesi, misura di importanza assunta, ai termini per determinare la classificazione dei concetti e in maniera simile per determinare la classificazione dei documenti. Per l’espansione vera e propria dei termini vengono considerati solo gli elementi posizionati in cima alla classifica ordinata appena considerata. Solo gli elementi considerati e selezionati saranno aggiunti a quelli preesistenti nella query di partenza. Il numero di termini selezionati varierà in base ad una soglia di selezione specificata dall’utente: se questa verrà posta ad un valore k verranno selezionati solamente i primi k concetti della lista (quelli ritenuti più significativi).
Latent Semantic Indexing
Altra tecnica molto impiegata nella Global Analysis è denominata Latent Semantic Indexing. Questa tecnica permette di colmare il problema che si presenta nel collegare le informazioni specifi�cate dell’utente con la sintassi della forme di frasi. Per poter permettere ciò, questa tecnica deriva in modo statistico i concetti invece delle singole parole per costruire un ranking di pertinenza in base alle informazioni dell’utente. LSI assume e prova a estrarre la struttura sottostante o nascosta nell’uso della parola, la quale risulta parzialmente oscurata dall’ampio uso di termini semanticamente simili nella lingua quotidiana. Solitamente questa tecnica viene applicata al livello del documento nella sua forma complessiva e talvolta, ma più raramente, viene impiegata per stilare un ranking delle forme di frase in relazione all’informazione richiesta.
Per poter applicare la tecnica LSI occorre trasformare il dominio di partenza nella “latent semantic dimension space”, tutte le informazioni e le forme di frase dovranno essere rappresentate in tale contesto. Nel latent space potrebbe essere attribuito un elevato grado di similitudine semantica a query e forme di frase apparentemente totalmente dissimili poich� tra esse potrebbe non presentarsi alcun termine in comune. In tale spazio l’intero corpus dei documenti sarà rappresentato sotto forma di matrice cosi composta: le righe rappresentanti le parole e le colonne le forme di frase. Tradotto tutto il corpus, viene applicata la tecnica matematica Single Value Decomposition (SVD) per decomporre tale matrice nel prodotto di tre differenti matrici. SVD è un metodo matematico per permettere la rotazione degli assi nello spazio n-dimensionale: ad esempio è possibile far ruotare il primo asse lungo la direzione della variazione di dati maggiore, far ruotare il secondo asse verso la seconda variazione di dati più grande e così via. Quindi mantenendo le dimensioni, risulta possibile mantenere una rappresentazione dei punti, rappresentanti i dati, pur mantenendo una piccola deviazione tra la loro rappresentazione nello spazio.
A questo punto le forme di frase ridotte sono rappresentate nel nuovo vettore della query, possono quindi essere classificate secondo la loro similitudine con le informazioni richieste.
Similarity thesaurus
Un Similitarity thesaurus consiste in una matrice delle somiglianze di coppie di termini. Tale dizionario dei sinonimi basato sulla somiglianza si basa sulla maniera in cui sono indicizzati i documenti all’interno della collezione.
La matrice in cui esso viene rappresentato può essere costruita in maniera automatica usando un metodo di retrieval con i ruoli dei documenti e dei termini inter scambiati: i termini rappresentano gli oggetti reperibili e i documenti l’indice delle parole dei termini.
Il vantaggio maggiore apportato dalla tecnica della Global Analysis è facilmente riscontrabile nell’analisi delle prestazioni ottenute dai sistemi che implementano questa tecnica. L’analisi globale assicura mediamente buoni miglioramenti nel reperimento delle informazioni richieste dalle query dell’utente. Inoltre viene migliorato anche il dizionario delle risorse, ovvero dei nomi dei documenti. Bisogna notare come quest’ultimo potrebbe essere esportato facilmente e usato per un servizio di browsing basato su un altro tipo di concetti.
Lo svantaggio maggiore di questa tecnica è reperibile in termini di occupazione di spazio sul disco e in termini di tempo d’esecuzione per effettuare l’analisi generale del contesto e costruire adeguatamente il database di ricerca, il quale dovrà contenere tutti i concetti utili ai fini delle ricerche. Infine bisogna anche notare che nonostante miglioramenti nell’ottenimento delle informazioni richieste, le query potrebbero risultare fortemente degradate dal processo d’espansione a causa dell’innumerevole numero di termini aggiunti.
Local Analisys
Le metodologie di analisi locale prendono la denominazione “local” a causa della loro origine, riscontrabile nella tecnica del feedback locale. Nel seguito verranno approfondite varie metodologie sviluppatesi a partire dall’idea originaria presentata nell’anno 1977.
Complessivamente le metodologie di Local Analysis, a differenza della Global Analysis, basano il meccanimo della query expansion sulle informazioni reperite dall’analisi parziale dei documenti riscontrati dalla ricerca. In particolare l’analisi si limita solamente ai soli documenti inizialmente reperiti senza espandere ulteriormente la ricerca.
In letteratura possono essere individuate principalmente quattro tecniche di analisi locale[2] [3].
- Relevance Feedback
- Pseudo-Relevance Feedback
- Local Feedback
- Local Context Analysis
Queste tecniche saranno approfondite a seguire.
Relevance Feedback
Metodologia di Local Analysis molto nota nel campo della Query Expansion. Mediante essa risulta possibile ottenere importanti informazioni di feedback da parte dell’utente per migliorare i risultati di ricerca escludendo documenti non rilevanti e mettendo in risalto quelli desiderati. Queste informazioni saranno raccolte in base al giudizio (selezione o meno del testo) espresso dall’utente in base alla pertinenza ritenuta per i documenti reperiti dal sistema di ricerca. Successivamente queste saranno impiegate nel processo di espansione della query. Tipicamente l’espansione della Query avviene individuando ed estraendo i termini candidati direttamente dagli scritti recuperati dalla ricerca dell’utente.
Questa tecnica permette di ottenere risultati proporzionali alla bontà delle informazioni di feedback fornite dall’utente. Se queste risultano essere sufficienti e corrette, allora i risultati ottenuti potranno essere molto buoni, altrimenti rischia di fornirne di non soddisfacenti. Purtroppo bisogna sottolineare che nel mondo reale solitamente gli utenti sono poco propensi a fornire informazioni di feedback, di conseguenza risulta difficile poter ottenere risultati molto soddisfacenti da un’applicazione realmente interagente con gli utenti.
Pseudo-Relevance Feedback
Variante alla tecnica Relevance Feedback, come suggerisce il nome, per sopperire alla mancanza di giudizi di feedback sufficienti e pertinenti da parte dell’utente. Questa tecnica si propone di colmare il gap informativo per il quale una buona ricerca scaturiva in una di poco significato. In questo contesto la tecnica pseudo-relevance feedback o blind feedback è molto utilizzata.
La metodologia pseudo-relevace feedback approssima la tecnica relevace feedback semplicemente assumendo come rilevanti un certo numero n di documenti posizionati nei primi n posti della classificata ordinata secondo ranking decrescente. Proprio da questi n documenti saranno estratti i termini utili per l’espansione della query, che sarà sottoposta ad un secondo ciclo di ricerca.
Local Feedback
Come la precedente tecnica, la metodologia Local Feedback individua la sua sorgente di informazione nei documenti classificati meglio nell’ambito della ricerca eseguita. I documenti verranno prima classificati secondo un ranking ordinato dei punteggi di pertinenza e successivamente verranno presi in considerazione solamente quelli ritenuti di maggior rilievo ai fini della ricerca.
Le informazioni così ottenute saranno utili ai fini della generazione automatica di un dizionario dei termini. Quest’ultimo viene costruito estraendo i termini solamente dai documenti considerati, suddividendoli in gruppi di somiglianza e considerandoli infine come quasi-sinonimi. In alcuni studi di ricerca, l’informazione derivata dai documenti classificati meglio viene impiegata nella rivalutazione della probabilità d’occorrenza dei termini in un insieme di pertinenza di una query. Tale rivalutazione avviene pesando i termini della query che risulteranno essere modificati, ma allo stesso tempo non verranno aggiunti nuovi termini. Esperimenti così condotti hanno prodotto effettivi miglioramenti, anche se limitati sulla base di una piccola collezione di test.
Una versione semplificata di questa tecnica consiste nel prendere in considerazione solamente termini che siano comuni e che compaiano all’interno dei documenti classificati in cima al ranking di pertinenza, precedentemente ottenuto. I termini cosi ottenuti verranno quindi aggiunti alla query sotto esame.
Da un’analisi delle prestazioni di questa versione semplificata appare evidente la forte infi‚uenza della proporzione dei documenti presi in esame, rispetto l’intero corpus, ai fini del reperimento delle informazioni. Inoltre è stato constatato un peggioramento nei risultati di ricerca qualora i termini impiegati per l’espansione della query dovessero provenire in maggioranza da documenti ritenuti non pertinenti alla ricerca in esame.
È stato riscontrato come la tecnica del Local Feedback risulti molto efficiente nel processo d’espansione basato sui documenti maggiormente importanti (classificati molto in alto) all’interno della classificazione ad essi associata. Inoltre, pur risultando più lento a run-time di altre tecniche, non richiede alcuna costruzione di dizionari di parole su cui basare i successivi passi. D’altra parte bisogna annoverare l’overhead apportato da tale tecnica in termini di ricerche extra e accessi a informazione connessa con quella dei documenti. Se quest’ultima dovesse essere salvata in qualche supporto fisico, implicherebbe ulteriore overhead in termini di spazio; tuttavia è doveroso sottolineare come tale overhead debba essere considerato significativamente inferiore a quello ottenuto dall’accesso a un database dei concetti. Un’altro svantaggio molto importante, e assolutamente da non sottovalutare, consiste nel comportamento ancora poco chiaro del sistema, che implementi questa metodologia, qualora impieghi per l’espansione termini derivanti da documenti ritenuti poco rilevanti ai fini della ricerca.
Local Context Analysis
La metodologia Local Context Analysis è una nuova tecnica di analisi locale che combina l’analisi globale con quella locale. Nell’ambito di tale tecnica i gruppi di sostantivi sono definiti concetti e questi ultimi vengono selezionati in base dei valori di co-occorrenza espressi in relazione alle parole chiave della query di ricerca. Approfondendo il metodo d’espansione, i concetti vengono selezionati in maniera simile a quanto avveniva nel caso del Local Feedback: vengono selezionati analizzando il testo dei documenti che sono stati classificati meglio nella fase di classificazione. Bisogna precisare che la Local Context Analysis fa uso solamente dei passaggi migliori, ovvero quelli più significati, invece di usare l’intero documento come nel caso del Local Feedback.
Il processo d’espansione della query di ricerca usato nell’ambito della Local Context Analysis può essere suddivido in varie fasi:
- Reperimento degli n passaggi meglio classificati mediante l’uso di un sistema di Information Retrieval. Si definisce passaggio di un documento un area di testo di dimensioni predefinite, potrebbe essere impostata una dimensione k per definire una finestra di validità per considerare una porzione di testo valida come passaggio. Ad esempio impostando tale valore a 210 parole un passaggio sarà definito da una porzione di testo composto da 210 termini. In questa metodologia sono preferiti i passaggi all’intero documento principalmente per ridurre l’overhead che potrebbe scaturire dall’analisi del documento se questo dovesse risultare molto lungo e riguardante più argomenti. In questo caso la co-occorrenza stessa risulterebbe compromessa, infatti non può essere assicurato che il significato di un termine venga mantenuto sempre lo stesso e comunque associato al medesimo argomento. Inoltre usando solo porzioni di testo apparirà evidente la semplicità nell’eliminare le parti irrilevanti di ciascun documento: queste otterranno posizioni molto basse nella lista ordinata causandone di conseguenza lo scarto.
- Estrazione e classificazione dei concetti (gruppi di sostantivi) dagli n passaggi di testo classificati meglio al passaggio precendente.
- Infine aggiungere gli m termini maggiormente informativi alla query d’esame.
Conclusioni
In questo secondo articolo della serie abbiamo analizzato nel dettaglio alcune tecniche algoritmiche per l’estrazione dei termini per la Query Expansion.
È stato fornito un quadro complessivo sulla ricerca della Query Expansion approfondendo ciò che concerne la modalità automatica di espansione. Sono quindi state analizzata le tecniche di analisi locale e globale dei documenti del corpus della collezione fornendo un quadro generale sulle varie metodologie d’analisi.
Riferimenti
[1] Claudio Biancalana – Antonello Lapolla – Alessandro Micarelli, “Query Expansion with Matrix Correlation Techniques: a Systematic Approach” in Proceedings of the 4th International Conference on Web Information Systems and Technologies, Funchal, Madeira – Portugal, 4-7 May, 2008.
[2] Jinxi Xu – W. Bruce Croft, “Query Expansion Using Local and Global Document Analysis”, Center fo Intelligent Information Retrieval, Computer Science Department, University of Massachusetts, Amherst.
[3] Yonggang Qiu, H.P. Frei, “Concept Based Query Expansion”