Ricerca on-line con tecniche di Query Expansion

III parte: Hyperspace Analogue to Language per l‘espansione della querydi e

In questo articolo introduciamo l‘Hyperspace Analogue to Language (HAL), una metodologia basata sull‘analisi grammaticale e semantica dei termini e sulla derivazione delle relazioni tra di essi mediante la costruzione di una matrice di co-occorrenza.

Nel precedente articolo abbiamo introdotto il concetto di "vettorializzazione" e i relativi vantaggi indotti da questo tipo di rappresentazione nel contesto delle tecniche di Query Expansion. A tal proposito, in questo articolo, introdurremo una delle metodologie utilizzate in letteratura per la traduzione delle parole nello spazio multidimensionale: Hyperspace Analogue to Language (HAL). In particolare, attraverso questa metodologia viene generata una matrice di prossimità delle parole, ottenuta a partire dall'analisi del corpus dei documenti: tale matrice, detta anche di co-occorrenza, ha una sua validità in quanto si basa sul seguente postulato alla base di HAL: termini dal significato simile occorrono in contesti simili.

Aspetti Teorici

L'Hyperspace Analogue to Language è una metodologia presentata da C. Burgess and K. Lund nel 1995 [1]; essa è incentrata sull'analisi grammaticale e semantica dei termini contenuti nei documenti di training, e sulla derivazione delle relazioni tra di essi mediante la costruzione di una matrice di prossimità.

Il presupposto fondamentale alla base di HAL è il seguente:

"Termini dal significato simile occorrono in contesti simili"

Utilizzando questa affermazione come un postulato, la teoria ha l'ambizioso intento di coniugare dati statistici (come il calcolo della frequenza di occorrenza di ogni termine all'interno di un documento) e elementi semantici (intervenendo sui dati ottenuti per individuare strutture latenti connesse al significato e al contesto dei vari termini collezionati).

Il primo passo dell'Hyperspace Analogue to Language consiste nella costruzione della matrice di contesto di dimensioni NxN (dove n è il numero complessivo di termini incontrati), che contiene i valori calcolati alizzando i documenti per mezzo di una finestra scorrevole di dimensioni fissate.

HAL genera una matrice della co-occorrenza delle parole dall'analisi del corpus dei documenti, limitata ad una sola porzione del testo mediante una finestra scorrevole di dimensioni fissate.
Eseguendo una lettura della matrice selezionando una parola w è possibile associare ad essa tutto il contesto associato a tale termine durante l'analisi del corpus dei documenti. Per ogni vocabolo il significato ad esso associato si presenta sotto forma vettoriale e risulta essere associato al contento in cui è stata individuata durante l'analisi. Quindi come detto in precedenza, i vocaboli che compariranno in contesti simili saranno rappresentati da vettori simili.
Questo presupposto è basato sul principio che composizione di documenti inerenti ad argomenti simili sia effettuata con parole simili.

Ogni parola viene quindi rappresentata da un vettore pesato mediante la co-occorrenza con altre le altre parole del corpus. Il peso rappresenta appunto la forza dell'associazione tra il termine analizzato e quello corrente, tale peso viene ottenuto considerando la lettura dei termini limitata ad una sola porzione del testo o finestra di dimensione n. L'associazione di co-occorrenza tra i termini risulterà maggiore al crescere del peso. Ovviamente tale misura sarà soggetta a rumore, il quale tenderà a crescere all'aumentare del numero di documenti analizzati. Per ovviare a tale problema è possibile ricorrere a tecniche che prevedano l'uso di soglie specifiche o allo scarto di tutte le associazioni che non superano il valore medio. Inoltre ogni elemento di tali vettori rappresenta delle coordinate in uno spazio multidimensionale per la rappresentazione del significato stesso della parola.

Considerando tali coordinate sarà possibile calcolarne la distanza mediante metriche basate sulla distanza stessa.

Mediante la rappresentazione nello spazio di ciascun termine la metodologia HAL risulta in grado di classificare con facilità sostantivi, preposizioni e verbi. Infatti grazie a questa metodologia i vocaboli possono essere analizzati sia in base alle caratteristiche semantiche, sia in base a quelle grammaticali. In particolare possono essere individuate relazioni tra i termini che siano semantiche oppure associative. Tipicamente si definisce relazione associativa una relazione che sia causata dalla co-occorrenza temporale nel contesto, ovvero relazioni episodiche. Generalmente tale differenza dovrebbe essere tenuta in considerazione nel calcolo delle distanze tra i termini, dovrebbe essere assegnato un maggior peso alle relazioni di tipo semantiche. Purtroppo la distinzione tra esse non risulta sempre semplice, infatti possono essere individuate varie combinazioni di tali associazioni: solo semantiche, solo associative e come combinazione tra le due.

La co-occorrenza a livello locale, ottenuta mediante l'impiego della finestra scorrevole, sarà indicativa di relazioni occasionali e debolmente di quelle semantiche. Questa è ottenibile dalla matrice analizzando la co-occorrenza di due singoli termini.Invece la co-occorrenza globale, ottenuta come concatenazione di molte co-occorrenze locali, risulta indicativa della storia d'apprendimento della parola. Tale co-occorrenza costituisce il vettore intero del termine analizzato.

Talvolta concetti possono essere espressi mediante la composizione di due parole, ad esempio come "space program". Anche in questo caso il modello Hyperspace Analogue to Language fornisce un valido supporto per l'analisi di tale concetto. Questo può essere rappresentato mediante la generazione di un vettore come combinazione dei vettori dei termini che lo compongono.
Un approccio molto semplice è la somma di tali vettori, metodologie più complicate prevedono euristiche basate sul peso associato ai vocaboli.

Cosa avviene "in pratica"

L'aggiornamento della matrice c può avvenire in modi diversi a seconda della politica scelta per il calcolo della prossimità.

Ad esempio è possibile procedere nel modo seguente:
1. si sceglie un documento di training d (l'algoritmo itera sull'intera collezione considerata);
2. una volta scelta la dimensione M della finestra scorrevole, si procede al calcolo delle prossimità tra coppie di termini. La finestra fd viene fatta scorrere all'interno del documento, e per ogni coppia formata da t (il termine successivo all'ultimo incluso nella finestra) e tx (un generico termine occorrente almeno una volta al suo interno) si calcola:


dove con occ_tx,i indichiamo l'i-esima occorrenza di tx in fd;

 

3. la matrice di contesto viene aggiornata con ogni valore calcolato:

 


Per chiarire il procedimento descritto ricorriamo a un esempio pratico. Utilizziamo una finestra di ampiezza M=4 per analizzare la seguente frase:


(i pedici servono per distinguere le diverse occorrenze dello stesso termine). Nella prima iterazione la finestra comprende solo il primo termine the1. Pertanto l'unico valore calcolabile è


che assume un valore elevato poiche' la distanza d(the1, table1) tra i due termini è pari a 0. Nelle iterazioni successive alla prima, vengono calcolati i valori riportati nella tabella 1.

Tabella 1 - Calcolo dei valori di prossmità

La matrice di contesto corrispondente è invece riportata nella tabella 2: si noti la somma dei valori relativi alle due occorrenze del termine table.

Tabella 2 - Matrice di contesto

Una volta calcolata la matrice, si nota come ogni termine t possa essere rappresentato dalla somma dei due vettori relativi: il vettore riga (che illustra quali termini sono più spesso seguiti da t) e il vettore colonna (relativo invece ai termini preceduti da t).

Detto HALt il vettore così ottenuto relativo al generico termine t, il calcolo della relazione probabilistica tra un termine t2 e t avviene nel modo seguente:


La matrice di contesto propria dell'approccio Hyperspace Analogue to Language è d'altronde caratterizzata da un'espressività tale da favorire l'ideazione di nuovi modi per trarne informazioni utili ai fini della Query Expansion. L'utilizzo dei dati raccolti dipende a questo punto dal diverso approccio adoperato nella fase successiva all'aggiornamento della matrice.

Conclusioni

Tra le principali metodologie presenti in letteratura per la personalizzazione della ricerca figura la Query Expansion, ovvero l'intervento attivo sui termini di ricerca immessi dall'utente con l'aggiunta di altri termini rilevanti e caratterizzanti, prima di effettuare la ricerca vera e propria. In questo modo si tenta di ovviare all'incompletezza delle queries immesse dagli utenti e, al tempo stesso, si rende più specifica la ricerca, portando a una selezione precisa dei documenti rilevanti.
Per effettuare l'espansione della query è necessario costruire un modello dell'utente che contenga informazioni sugli interessi dello stesso, sotto forma di termini da utilizzare per l'espansione.
L'approccio analizzato in questo ultimo articolo della serie è l'Hypertext Analogue to Language: nella delineazione del modello utente assumono rilevanza particolare tutti i termini che occorrono più spesso nelle pagine visitate precedentemente.

Riferimenti

[1] C. Burgess, K. Lund, "Hyperspace analogue to language (hal): A general model of semantic representation", in "Proceedings of the annual meeting of the Psychonomic Society", 1995.

 

Condividi

Pubblicato nel numero
128 aprile 2008
Francesco Saverio Profiti ha conseguito la laurea in Ingegneria Informatica presso l‘Università degli Studi Roma Tre nel 2003. Durante la sua carriera lavorativa si è occupato, prima da programmatore, poi da analista e infine da architetto di applicazioni di classe enterprise sia in ambiente Java EE sia in ambiente .NET.…
Claudio Biancalana è dottorando in Ingegneria Informatica presso il Dipartimento di Informatica e Automazione dell‘Università degli Studi Roma Tre. L‘attività di ricerca scientifica svolta finora ha riguardato l‘Intelligenza Artificiale e la Categorizzazione Automatica di Testi (ATC, Automated Text Categorization). Dal 2003 collabora attivamente presso il laboratorio di Intelligenza Artificiale dell‘Università…
Articoli nella stessa serie
Ti potrebbe interessare anche