In questo articolo studieremo alcune tecniche di rappresentazione e indicizzazione dei documenti testuali al fine di poter trattare l‘informazione con tecniche di apprendimento automatico.

Introduzione

Per definire una metodologia per l‘estrazione automatica e semi-automatica di conoscenza a partire da informazione strutturata e non strutturata è necessario studiare approfonditamente tecniche per l‘analisi testuale dei documenti e le modalità  in cui il testo ivi contenuto si relaziona semanticamente con le classi dell‘ontologia di riferimento.

Nel caso in cui le informazioni da analizzare siano di tipo non strutturato, il lavoro di estrazione della conoscenza è maggiormente articolato a causa delle difficoltà  insite nell‘analisi dei documenti scritti in linguaggio naturale. Le informazioni di cui non è possibile riscontrare una specifica struttura ben definita, o senza una caratterizzazione semantica espressa con appositi linguaggi, risultano svantaggiate nel processo di reperimento da parte dell‘utente, poiché il relativo contenuto non sempre risulta facilmente individuabile e confrontabile con le richieste espresse.

 

Rappresentazione e indicizzazione dei documenti testuali

L‘approccio più immediato di tipo word-level (menzionato nel precedente articolo) per rappresentare un testo è quello detto bag-of-words, nel quale le features del documento sono le parole in esso presenti oppure, se questo sarà  oggetto di pre-processing, quelle presenti al termine di questa fase.

Più rigorosamente, dato un documento d, ed applicata su di esso se necessario qualche tecnica di preprocessing, si otterrà  un documento equivalente (ai fini della classificazione) de.

Nel caso la fase di pre-processamento non venisse effettuata, si pone de = d

A questo punto, posto

 

l‘insieme delle n parole distinte presenti nel documento de, la rappresentazione di d secondo l‘approccio bag of words sarà  costituita da un insieme di coppie

 

dove wi è il peso associato alla parola ti.

Una tipica scelta per il valore dei coefficienti wi è quella di porli pari al numero di occorrenze della parola ti nel documento de.

Tale quantità  è detta term frequency di una parola t nel documento d, ed è indicata come TF(t,d).

Quanto detto fino adesso vale nel caso che sia possibile scegliere ex-novo le features; a volte però queste sono scelte in fase di training, d una volta decise, quello che importa è rappresentare il documento sulla base di queste. Anche in questo caso è possibile adottare un approccio di tipo bag-of-words, basta apportare qualche modifica al metodo di base. Più rigorosamente, detto

 

l‘insieme delle features (in questo caso parole) da considerare, un generico documento dj (eventualmente pre-processato) è rappresentato mediante il vettore

 

Nel quale il termine wi,j rappresenta il peso assegnato alla feature (parola) ti nel documento dj, che nell‘approccio bag-of-words equivale al numero di occorrenze con cui compare la parola ti nel documento dj, che in questo caso può anche essere pari a zero.

Un approccio molto simile a quello appena descritto è l‘approccio set-of-words, nel quale un generico documento dj è ancora rappresentato tramite il vettore, ma i termini w{i,j} sono binari, e rappresentano la presenza

 

oppure l‘assenza

 

di almeno una occorrenza della parola ti nel documento dj.

L‘approccio bag of words è immediatamente estendibile al caso sub-word level, basta sostituire in quanto detto in questo paragrafo il concetto di parola con quello di n-gramma. Rappresentare i documenti in questo modo è abbastanza comune, perché sebbene qualche informazione venga persa, rappresentazioni più sofisticate non garantiscono miglioramenti sostanziali, e spesso la loro maggiore complessità  non è compensata da apprezzabili miglioramenti in fase di classificazione. La tesi secondo la quale nessuna rappresentazione del testo è significativamente superiore (ovvero, nel caso TC, aumenta in modo sensibile l‘effectiveness del classificatore) a quella ottenuta selezionando le singole parole dal documento originale, sembra non trovare ancora smentite credibili.

Oltre l‘approccio bag of words (ma non l‘approccio set of words, che è di tipo booleano) è possibile operare altri approcci basati sulla Term Frequency

 

pari al numero di occorrenze della parola ti nel documento dj.

Intuitivamente, tanto più è alto il valore di TF in un documento, tanto più quel termine è rilevante nel documento. Tuttavia, occorre anche tenere in conto il fatto che se una parola compare in quasi tutti i documenti di una collezione non sarà  molto rilevante per la discriminazione in categorie. Occorre quindi introdurre un termine ulteriore, detto Document Frequency

 

ovvero il numero di documenti in cui la parola wi appare almeno una volta. Un alto valore di

 

deve portare alla riduzione dell‘importanza del termine di wi nell‘economia della categorizzazione. Spesso questo si traduce in una riduzione del suo peso. Bisogna inoltre tener presente che i documenti possono avere lunghezza differente, pertanto può essere necessario ricorrere a qualche forma di normalizzazione per poter confrontare l‘importanza dei termini su testi di grandezza diversa.

Detto

 

il vettore con i pesi delle features fi che rappresenta il documento d, alcuni dei più utilizzati approcci di term weighting sono :

• TF weighting, nel quale la term frequency di una feature è semplicemente normalizzata sulla somma delle term frequency di tutte le features, ovvero:

 

 

• TFxIDF weighting, nel quale è tenuta in considerazione anche la frequenza del termine in tutti i documenti che fanno parte del training set. Posto |D| il numero dei documenti della collezione, in questo caso si ha:

 

 

• TFC weighting, ovvero la versione normalizzata rispetto alla lunghezza euclidea dell‘approccio TFxIDF. In questo caso si ha:

 

• LTC weighting, simile all‘approccio TFC, ma per la normalizzazione è utilizzato il logaritmo della frequenza del termine. In questo caso si ha:

 

• Enthropy weighting. Questo approccio si basa su idee proprie della teoria dell‘informazione ed è molto sofisticato. Alcuni studi dimostrano la sua efficacia e la sua maggiore prestazionalità  nei confronti degli altri metodi. In questo caso il peso è dato da:

 

è pari all‘entropia del termine fi, che risulta uguale a -1 se fi è equamente distribuita in tutti i documenti e pari a zero se fi è presente solo in un documento.

Gli approcci basati su term frequency sono indubbiamente i più utilizzati, ma non sono gli unici.

Un approccio alternativo è quello detto bxc weighting, nel quale è posto ad 1 il peso di ogni parola presente nel documento, ed a 0 quello di tutte le altre, ed il vettore risultante è poi normalizzato, ovvero

 

Dove

 

se e solo se il termine fi è presente nel documento d almeno una volta, altrimenti

 

 

Dimensionality Reduction

Posto a

 

il term space, ovvero l‘insieme dei termini atti a rappresentare un documento, è necessario che la sua cardinalità  non sia troppo elevata, e quindi può risultare opportuno usare metodi per ridurla.

Più formalmente, applicare tecniche di dimensionality reduction (DR) sull‘insieme

 

vuol dire ottenere da esso un insieme

 

con m<n, che rappresenterà  il documento. L‘insieme

 

è detto reduced term set.

Il processo di riduzione del numero dei termini porta comunque alla perdita di informazioni, e va quindi effettuato con l‘obiettivo di ottimizzare, secondo qualche criterio, il rapporto tra numero di termini persi ed il danno (in questa sede, “danno” va inteso in senso neutro e non necessariamente negativo, visto che una rappresentazione con meno termini, benchà© porti un minor contenuto informativo, non necessariamente porta a classificazioni peggiori) che la nuova rappresentazione del documento porterebbe alla classificazione.

È possibile distinguere diversi approcci alla dimensionality reduction. Una prima distinzione può operarsi sulla differente modalità  di applicazione, che può essere locale oppure globale.

Nell‘approccio locale si calcola un insieme

 

con

 

per ogni categoria ci.

In altri termini, in questo approccio viene applicata la riduzione del term set categoria per categoria, e perciò per decidere sull‘appartenenza o meno di un documento ad ogni categoria si farà  riferimento alla riduzione corrispondente. Nell‘approccio globale invece si calcola un insieme

 

con

 

che verrà  usato per la classificazione sotto tutte le categorie ci.

Una seconda e più importante distinzione è basata invece sulla natura del term set risultante, che può essere un sottoinsieme del term set originario oppure può contenere termini ottenuti da combinazioni e trasformazioni dei termini originali.

Più formalmente, si possono distinguere i due diversi approcci:

 

• Feature Subset Selection, nel quale il term set della nuova rappresentazione è un sottoinsieme del term set originale
• Feature Construction, nel quale gli elementi del term set della nuova rappresentazione sono ottenuti combinando e trasformando quelli del term set originale.

 

Alcune tecniche di DR tramite Feature Subset Selection sono:

 

Stopword Elimination

Se non è stata eseguita in fase di pre-processing, è possibile farlo successivamente. Come detto in precedenza, questa tecnica elimina i termini troppo frequenti, e quindi presumibilmente legati più al linguaggio in cui il documento è scritto che all‘argomento.

 

Document Frequency Tresholding

Questa tecnica tende a rimuovere i termini scarsamente frequenti, basandosi sul principio che se un particolare termine non compare almeno m volte nei documenti di training (oppure alternativamente non compare in almeno m documenti di training) è irrilevante al fine della determinazione dell‘argomento trattato, e viene quindi scartato. Variando il valore di m è possibile ridurre pesantemente le dimensioni del term set. Le parole scartate sono dette low-frequency words.

 

Mutual information

Il tasso d‘informazione mutua misura la riduzione d‘entropia che si ha considerando due variabili casuali Y e W insieme piuttosto che individualmente, ovvero

 

dove la variabile casuale Y indica l‘etichetta assegnata ad un documento e la variabile casuale W descrive se una partiolare parola è presente nel documento. La precedente espressione diventa quindi

 

L‘entropia H(X) misura il numero di bit necessari per codificare X, perciò I(W,Y) è indice dell‘informazione che la parola W porta all‘etichetta Y, indipendentemente dalle altre parole del linguaggio. Per calcolare I(W,Y) le probabilità  necessarie possono essere stimate (è ad esempio possibile usare stime a massima somiglianza) dai documenti di training. I termini con la più alta informazione mutua sono selezionati come features.

 

Metrica “chi quadro”

Anche questa tecnica misura la dipendenza tra un termine W ed un‘etichetta Y. Posto M il numero di documenti di Y (corrispondente alla categoria Ci) che contengono il termine W, Z il numero di documenti di Y che non contengono il termine W, K il numero di documenti delle altre classi che contengono il termine W, J il numero di documenti delle altri classi che non contengono W, ed N il numero totale dei documenti del training set, la metrica

 

relativa al termine W ed alla classe Y è pari a

 

Un termine W sarà  legato all‘etichetta Y soltanto se la metrica

 

risulterà  superiore ad un certo valore.

 

Alcune delle tecniche di feature construction più usate sono invece:

 

Stemming

Accorpare in un unico indexing term più parole accomunate dalla stessa radice morfologica.

L‘assunto alla base di questa tecnica è che i suffissi delle parole, al fine dell‘individuazione dell‘argomento del testo, hanno un‘importanza trascurabile. In conseguenza di questo, si possono accorpare sotto un‘unica parola tutte le parole accomunate dalla stessa radice. Nel caso di articoli in lingua italiana, la presenza di un sostantivo al maschile oppure al femminile porta praticamente la stessa informazione, così pure tutti i verbi, in qualsiasi tempo compaiano, portano la stessa informazione che avrebbe il corrispondente verbo all‘infinito.

 

Latent Semantic Indexing

Questa tecnica produce un mapping dei vettori che rappresentano le features in un sotto-spazio di dimensione minore, applicando una trasformazione ortogonale del sistema di coordinate. I valori delle nuove coordinate corrispondono alle nuove features[1][2].

 

Term Clustering

Questa tecnica cerca di raggruppare dei termini simili semanticamente in cluster, che poi rappresenteranno le nuove features. I cluster sono generati usando algoritmi di learning non supervisionati, e questo richiede che le parole siano descritte usando meta-attributi.

 

Misure di similarità

Molti dei problemi nel machine learning e del procesamento del linguaggio naturale si basano sulla stima delle distanza tra osservazioni differenti [3].

Per questo sono state sviluppate un gran numero di funzioni che permettono di stimare la similarità  tra oggetti per differenti tipi di dato; tali funzioni varieranno ovviamente in maniera anche considerevole nel loro livello di espressività , nelle proprietà  matematiche e nelle assunzioni che possono essere effettuate.

Molta della letteratura sulle funzioni di similarità  ha come dominio applicativo il calcolo di similarità  tra stringhe; ciò è dovuto al ruolo trasversale e decisivo che le stringhe rivestono in contesti anche molto distanti. In questa prima sezione vediamo le tecniche classiche che vengono utilizzate per il calcolo di funzioni di similarità  tra stringhe.

Il problema della similarità  tra stringhe può essere approcciato da due differenti punti di vista tra loro complementari tramite il calcolo di una funzione di similarità  o una funzione distanza:

 

• Una funzione distanza mappa una coppia di stringhe s e t ad un numero reale r, dove un numero più piccolo di r indica una maggiore similarità  tra s e t.
• Una funzione di similarità  è analoga alla funzione di distanza ma in questo caso un maggior valore di r indica un maggiore indice di similarità .

Per pensare di procedere al calcolo tanto di una funzione di similarità  che di distanza tra stringhe è necessario poter individuare in maniera quantitativa il concetto di distanza e di similarità , ossia deve essere possibile misurare tali concetti attraverso l‘utilizzo di una metrica opportuna.

Una semplice misura di distanza è quella di considerare tutti i simboli diversi come fossero equidistanti e tutti quelli che coincidono invece a distanza nulla. Una tale metrica potrebbe essere identificata da una funzione del tipo

dist(a,b) = 1 se a?b

dist(a,b) = 0 se a=b

Tale funzione prende il nome di distanza di Hamming.

Come esempio si pensi di calcolare la distanza tra due stringhe ACGTA e ACTA; il calcolo di tale distanza dipende in realtà  da come le due stringhe vengono allineate. Infatti si suppongano i 3 possibili casi :

ACGTA

ACTA

In questo caso primo la distanza di Hamming è pari a 0+0+1+1+1

 

ACGTA

 ACTA

In questo secondo caso la distanza di Hamming è pari a 1+1+1+0+0

 

ACGTA

AC TA

In questo caso la distanza di Hamming è pari a 0+0+?+0+0

Nei primi due casi la distanza di Hamming corrisponde comunque a 3 mentre nel terzo caso tale distanza corrisponde al costo che si assegna all‘inserimento di un gap nella seconda stringa.

È necessario pertanto definire in maniera almeno informale il concetto di allineamento come l‘appaiamento dei simboli di una sequenza con quelli dell‘altra oppure con il simbolo ‘-‘ (gap).

Le tecniche classiche per il calcolo delle funzioni di similarità  tra stringhe possono essere in realtà  suddivise in due macro-categorie in base al punto di vista che esse hanno rispetto alle stringhe che trattano; si dividono pertanto in tecniche sequence-based e tecniche token-based.

 

• Sequence-based: le stringhe vengono viste come una sequenza continua di caratteri
• Token-based: le stringhe vengono viste come un insieme non ordinato di token

 

Conclusioni

In questo articolo abbiamo definito teoricamente alcune tecniche di indicizzazione e rappresentazione del testo. Nel prossimo articolo definiremo una metodologia per l‘estrazione automatica e semi-automatica di conoscenza a partire da informazione strutturata e non strutturata utilizzando le tecniche per l‘analisi testuale dei documenti analizzate.

 

Riferimenti

[1] Claudio Biancalana – Alessandro Micarelli, “Text Categorization in non-Linear semantic space”. In “Proceedings of the 10th Conference of the Italian Association for Artificial Intelligence (AI*IA 2007)”, Rome 2007, Lecture notes in Computer Science – Springer Verlag.

[2] A. Micarelli – F. Gasparetti – C. Biancalana, “Intelligent Search on the Internet”. In O. Stock, M. Schaerf (eds.), “Reasoning, Action and Interaction in AI Theories and Systems”. LNAI Festschrift Volume 4155 of the Lecture Notes in Computer Science series, Springer, Berlin, 2006.

[3] Fabrizio Sebastiani (2002). “Machine learning in automated text categorization”. ACM Computing Surveys, Vol. 34, No. 1, pp 1-47, March 2002.