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

Text Categorization per l‘Ontology Mapping

La Text Categorization (nel seguito TC) è l‘attività  di classificare parole del linguaggio in precise categorie che fanno parte di un insieme predefinito di categorie da cui scegliere [1][3].

Per fissare nel tempo l‘evoluzione della TC, nei primi anni Novanta è diventata il maggior settore della disciplina dei sistemi informativi, grazie soprattutto all‘aumentato interesse applicativo e alla possibilità  di avere a disposizione mezzi hardware più potenti.

Attualmente la TC è utilizzata in numerosi contesti, come l‘ordinamento sui documenti indicizzati attraverso un vocabolario predeterminato, per filtrare i documenti, per la generazione automatica di metadati, per evitare l‘ambiguità  delle parole, per popolare cataloghi gerarchici di risorse Web e in generale viene utilizzata in ogni applicazione che richiede un‘organizzazione di documenti o una selezione ed esecuzione controllata su di essi.

Per offrire una soluzione ai problemi di Ontology Mapping, vengono definite allo stato dell‘arte quattro applicazioni di ricerca (definite task). Di seguito vengono descritte brevemente, mostrando quale è l‘input, quale è l‘output e quale problema risolve ogni applicazione [3][4]:

• Topic Detection. Lavora su un insieme di storie. Processandole, quando incontra una storia che tratta un evento non ancora conosciuto allora crea un nuovo topic.
• Topic Tracking. Lavora su un insieme di storie e su dei topic che devono essere monitorati. Processando via via le storie, cerca di classificarle rispetto ai topic, ovvero se la storia tratta un evento relativo a uno dei topic assegnata, questa viene aggiunta a quel topic.
• New Event Detection. Lavora su un insieme di storie. Processandole, quando incontra una storia che tratta un evento non ancora conosciuto o un evento già  conosciuto ma considerato esaurito, allora crea un nuovo topic.
• Link Detection. Lavora su un insieme di storie. Considerando coppie di storie, riconosce se le due storie sono simili, ovvero trattano uno stesso evento oppure no.

Esaminiamo i singoli Task con maggiore attenzione:

Topic Detection

In questo task, viene processato un flusso di storie. Per ognuna viene valutato se l‘evento trattato sia riconducibile a un determinato topic gia conosciuto dal sistema. In caso positivo (ovvero, la storia è on-topic rispetto a un topic conosciuto), la storia viene aggiunta al topic esistente, altrimenti il sistema provvede a crearne uno nuovo. Importante per la buona riuscita del task è che il sistema venga implementato in modo da essere in grado di riconoscere cosa sia concettualmente un topic.
Infatti se sapesse riconoscere solo topic specifici, concreti, nel momento in cui se ne presentasse uno non conosciuto, il sistema non sarebbe in grado di riconoscerlo come tale e tanto meno di poterlo rappresentare. Per quanto riguarda la decisione che il sistema prende rispetto alla storia, questa può non essere presa immediatamente.
Ovvero, non è detto che il sistema processi le storie una alla volta. Infatti questo approccio è ritenuto inefficiente e irrealistico. Invece ciò che spesso accade è che un flusso di storie venga dato in input al sistema e quest‘ultimo può attendere un certo tempo o un certo numero di storie prima di prendere la propria decisione.
Una volta che la decisione è presa, essa è irrevocabile. Il periodo di latenza nel pronunciare il giudizio è definito deferral period ed è stato introdotto per migliorare le performance del sistema. Infatti risulta che più lungo è il periodo e migliore è la decisione. Però il periodo non può essere troppo lungo altrimenti andrebbe a scapito della reattività  del sistema. Il risultato del task sono topic che hanno lo stesso livello di granularità . Al sistema è richiesto di scegliere un certo livello di granularità  per massimizzare le performance relativamente a tutti i topic. Inoltre ogni storia deve essere pertinente al più a un topic. Il sistema in caso giudichi una storia pertinente a più di un topic, questa viene scartata.

Topic Tracking

Applicazione in cui le storie in arrivo vengono processate e eventualmente associate a topic già  conosciuti dal sistema. Un topic è considerato essere conosciuto dal sistema quando esiste almeno una storia on-topic che lo tratti. Quindi per supportare questo task è necessario che almeno un piccolo insieme di storie (definito insieme di training) sia utilizzato per ogni topic che deve essere monitorato dal sistema.
Ovvero, al sistema vengono impostati i topic che devono essere seguiti e per ognuno di essi viene inserito un insieme di storie on-topic (storie di training). In questo modo il sistema ha per ogni topic una certa base da cui partire per poter giudicare le storie che successivamente saranno processate.

New event Detection

L‘applicazione di New Event Detection (NED) è dedicata a trovare in un flusso di storie, ordinato cronologicamente, proveniente da sorgenti multiple e in differenti lingue, la prima storia che discute un certo evento. Questo task è sicuramente paragonabile al task di Topic Detection fatta eccezione per l‘output del task. Infatti NED estrae la prima storia di un determinato topic, mentre TD estrae tutte le storie che sono correlate con la prima (o con un certo numero di storie già  appartenenti al topic) Un‘importante osservazione è che un evento per essere definito nuovo non deve essere per forza dovuto alla prima storia in ordine temporale che lo tratta. Bisogna considerare anche la possibilità  che un determinato evento possa esaurirsi e che poi si ripresenti in un istante temporale abbastanza lontano dalla sua precedente manifestazione.

Link Detection Task

Applicazione che determina, fornite due storie, se esse trattano lo stesso topic. Anche in questo caso è fondamentale che il sistema riesca a comprendere il significato di cosa sia un topic e che tale comprensione sia indipendente da topic specifici. Comunque in questo task, il sistema non deve occuparsi esplicitamente di topic. Infatti non deve adoperarsi per inserire storie nei relativi topic e ne preoccuparsi che le storie discutano uno e un solo topic, ma deve solamente verificare la presenza di un collegamento (link) tra esse.

Text Categorization

Esistono diversi metodi di TC sui quali ci soffermeremo nel seguito, che verranno discussi in maniera completamente generale, nel senso che questi metodi non dipendono dalla disponibilità  di risorse con uno scopo preciso che potrebbero non essere utilizzabili o troppo costose da ottenere.
Utilizzare solo conoscenze endogene, cioè estratte solamente da altri documenti, significa classificare un documento basandosi solo sulla sua semantica, e dato che la semantica di un documento è un concetto molto soggettivo, che varia da persona a persona, ne segue che l‘appartenenza di un documento a una particolare categoria non può essere decisa deterministicamente [5].

Classificatore Naive Bayes

Per quanto riguarda la categorizzazione di testi si sono consolidati due classificatori Naive Bayes:

• Il modello a indipendenza binaria
• Il modello multinomiale

Nel modello ad indipendenza binaria un documento è rappresentato come al solito da un vettore di pesi X1, X2,…Xn con

ÂÂ

e da una variabile che ne indica la classe

ÂÂ

con C indice dell‘ultima categoria; è importante notare che in questo modo stiamo tagliando fuori l‘informazione relativa a quante volte sia presente una parola in un documento, ma ci preoccupiamo solo se sia presente. Le parole sono tra loro indipendenti ma sono tutte legate all‘appartenenza ad una delle due classi. Questa situazione può essere rappresentata da un modello di Markov grafico.

 

 

La probabilità  condizionata di un documento data la sua classe è

con pij probabilità  di avere la parola j quando il documento è della classe i

varrà  pij se la parola è presente e 0 altrimenti

1 – pij si può perciò interpretare come la probabilità  che la parola j non sia presente nel documento quando questo appartiene alla classe i.

Quindi pij e 1 – pij contribuiscono entrambi alla probabilità  totale: il primo valuta il contributo che offre la parola j se è presente nel documento, il secondo valuta il contributo della parola j se è assente.
pij può essere stimata in fase di training come:

con

• Ni numero dei documenti nella classe i
• Nij numero dei documenti nella classe i che contengono la parola j

f e fnj sono dei valori introdotti per:

• Supplire alla mancanza di campioni di training: si assume di avere dei dati con una determinata distribuzione (gaussiana, poissoniana, etc.) e si aggiustano f e fnj in accordo a questi campioni ipotetici. Al crescere dei dati di training questi valori tendono a scomparire, possono preciò essere considerati come un tampone.
• Eliminare il problema degli Zero Count, che si verifica quando una certa classe e un certo attributo non occorrono mai all‘interno del training set; questo potrebbe portare ad avere pij = 0, annullando la produttoria.

Scegliamo quindi i valori:

• Si può porre f =1/n con n numero di campioni del training set
• nj può essere il numero di valori che può assumere il j-esimo attributo (anche conosciuta come correzione di Laplace)

Anche Pr(c=i) è un risultato della fase di training ed è calcolato come:

con Ni numero dei documenti nella classe i ed N numero totale dei documenti.

A questo punto avendo a disposizione

ÂÂ

e Pr(c=i) possiamo finalmente classificare un documento (rappresentato dal vettore <x1,x2,…xn>), ovvero capire, per ogni classe i, qual è la probabilità  che vi appartenga

Classificatore tramite albero di decisione

Un classificatore tramite albero di decisione è un albero in cui i nodi interni sono etichettati da termini, i rami uscenti da essi sono etichettati dal test sul peso che il termine ha nell‘insieme di documento presi come esperimento, e le foglie sono etichettate da categorie.

Classificatore tramite regole di decisione

Un classificatore per categorie, costruito con regole di apprendimento induttive, consiste in una regola DNF, che è una regola condizionale con una premessa posta in forma normale disgiuntiva (DNF, Disjunctinve Normal Form) nella quale i letterali presenti denotano la presenza o l‘assenza della parola nel documento in esame, mentre la clausola in testa denota la decisione di classificare il documento sotto una certa categoria.

Metodi on-line

I metodi on-line costruiscono un classificatore subito dopo aver esaminato il primo documento di apprendimento, ridefinendolo successivamente ogni qual volta vengano esaminati nuovi documenti. Risulta vantaggioso nel caso in cui i documenti non siano tutti disponibili all‘inizio, o quando il significato delle categorie potrebbe cambiare nel tempo, come ad esempio nei filtri adattativi.

Il metodo Rocchio

Il metodo Rocchio è usato per classificazioni induttive lineari in modo descrittivo. Si basa su un adattamento per la TC della formula di Rocchio per rilevare feedback nel modello spazio-vettore, ed è forse il solo metodo TC originato dalla tradizione IR, anzichà© da quella del ML. Il metodo calcola un classificatore per ogni categoria ci tramite questa formula

dove wkj è il peso del termine tk nel documento

In questa formula “beta” e “gamma” sono parametri di controllo che permettono l‘impostazione della relativa importanza dei documenti positivi e negativi.

Classificatore basato su esempi

Il classificatore basato su esempi non costruisce una rappresentazione esplicita di una certa categoria, ma conta sulle etichette delle categorie assegnate ai documenti di apprendimento, in modo simile ad un documento di testo. Questo metodo è chiamato lazy learning (“apprendimento pigro”), perché si rimanda la decisione su come generalizzare oltre i dati di apprendimento, fino a che non ci si imbatte in una nuova query.
La rappresentazione che si usa è quella dell‘algoritmo k-NN (dove k sta per il numero di vicini prossimi). Per decidere a quale categoria appartenga un determinato documento, l‘algoritmo confronta se i k documenti di apprendimento più simili al documento preso in esame, siano già  all‘interno di quella categoria; se la risposta è positiva per la maggior parte di essi, viene presa una decisione positiva, altrimenti viene dato un risultato negativo. Attualmente l‘algoritmo si basa sui pesi, inseriti in base alla similarità  tra il documento preso in esame e il documento di test; la classificazione con questo algoritmo si basa sulla seguente formula:

dove Trk(dj) è l‘insieme di k documenti dz che massimizzano RSV(dj,dz) e

RSV(dj,dz) rappresenta alcune misurazioni o alcune relazioni semantiche esistenti tra il documento di test dj e il documento di apprendimento dz; ogni funzione di confronto deve essere o probabilistica o basata su vettori.
Questo metodo è adatto per la TC incentrata sui documenti, perché classificare i documenti di addestramento attraverso la somiglianza con i documenti di test può essere fatta una sola volta per tutte le categorie. Nella TC incentrata sulle categorie, devono essere catalogate le classifiche per ogni documento di test, che risulta ovviamente mal costruito.

Costruire classificatori con Support Vector Machine (SVM)

Il metodo SVM consiste nel trovare una superficie che separi gli esempi di apprendimento positivi da quelli negativi con il maggiore margine di spazio affinchà© la proprietà  di separazione sia invariante, rispettando lo spazio per una possibile transazione.

Classificatore committees

Il classificatore committees si basa sull‘idea che, dato un‘attività  che richiede un‘esperienza approfondita per realizzarla, k esperti potrebbero essere migliori che uno solo, se i loro giudizi individuali sono appropriatamente combinati. Nella TC, l‘idea è quella di applicare k differenti classificatori sulla stessa attività  per decidere se il documento dj appartenga alla categoria ci, e poi mettere insieme i loro risultati in modo appropriato.

Altri metodi

Benchà© nelle sessioni precedenti si sia cercato di dare una veduta generale più completa possibile della letteratura TC, è impossibile dare una visione esaustiva. Alcuni approcci di apprendimento adottati, onestamente non ricadono in una delle classi di algoritmi precedenti, o per qualche motivo sono rimasti tentativi isolati. Tra questi i più importanti sono quelli basati sulla rete di deduzione bayesiana, algoritmi genetici e modellazione con massima entropia.

Conclusioni

In questo ultimo articolo della serie abbiamo esplorato alcune metodologie per la classificazione per l‘ontology mapping. In prima battuta ci siamo occupati dei task per il topic tracking e infine abbiamo esposto alcune tecniche statistiche e vettoriali per l‘apprendimento ed il riconoscimento automatico.

Riferimenti

[1] Claudio Biancalana – Alessandro Micarelli “Text Categorization with Modified LSI”, Technical Report RT-DIA-90-2004, Università  degli Studi Roma Tre, September 2004.

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

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

[4] Uschold M. – Gruninger M, “Ontologies: Principles, Methods and Applications”, Knowledge Engineering Review; Volume 11 Number 2, 1996

[5] 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.