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 bag of words

Dato l'insieme delle n parole distinte presenti nel documento d, la rappresentazione di d secondo l'approccio bag of words sarà costituita da un insieme di coppie (ti, wi) 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 d. 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, e 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 F = {t1, t2, ..., tn} l'insieme delle features (in questo caso parole) da considerare, un generico documento dj (eventualmente pre-processato) è rappresentato mediante il vettore:

dj = (w1,j, w2,j, ..., wn,j)

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 wi,j sono binari, e rappresentano la presenza (wi,j = 1) oppure l'assenza (wi,j = 0) 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.

Term weighting

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 TF(ti, dj) 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 DF(ti) ovvero il numero di documenti in cui la parola wi appare almeno una volta. Un alto valore di DF(ti) deve portare alla riduzione dell'importanza del termine 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 d = (w1, w2, ..., wn) 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
  • 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, il peso è calcolato come TF(ti,d) × log(|D|/DF(ti))
  • TFC weighting: ovvero la versione normalizzata rispetto alla lunghezza euclidea dell'approccio TFxIDF
  • LTC weighting: simile all'approccio TFC, ma per la normalizzazione è utilizzato il logaritmo della frequenza del termine
  • Entropy 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. L'entropia del termine fi 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. Il valore wi = 1 se e solo se il termine fi è presente nel documento d almeno una volta, altrimenti wi = 0.

Dimensionality Reduction

Posto T = {t1, t2, ..., tn} 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 T vuol dire ottenere da esso un insieme T' = {t'1, t'2, ..., t'm} con m < n, che rappresenterà il documento. L'insieme T' è 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 T'i con |T'i| < |T| 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 T' con |T'| < |T| 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

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 Thresholding

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 I(W,Y) = H(Y) - H(Y|W) dove la variabile casuale Y indica l'etichetta assegnata ad un documento e la variabile casuale W descrive se una particolare parola è presente nel documento.

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 altre classi che non contengono W, ed N il numero totale dei documenti del training set, la metrica χ²(W,Y) relativa al termine W ed alla classe Y è calcolata secondo la formula standard del chi quadro. Un termine W sarà legato all'etichetta Y soltanto se la metrica χ²(W,Y) risulterà superiore ad un certo valore.

Alcune tecniche di feature construction

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.

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 processamento del linguaggio naturale si basano sulla stima della distanza tra osservazioni differenti. 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.

Distanza di Hamming

Una semplice misura di distanza è quella di considerare tutti i simboli diversi come fossero equidistanti e tutti quelli che coincidono invece a distanza nulla. 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:

Caso 1: ACGTA vs ACTA - la distanza di Hamming è pari a 0+0+1+1+1 = 3

Caso 2: ACGTA vs ACTA (allineamento diverso) - la distanza di Hamming è pari a 1+1+1+0+0 = 3

Caso 3: ACGTA vs AC-TA (con gap) - 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.