1
Corso di Laurea Magistrale in Informatica Umanistica
R
ELAZIONE
Sviluppo di un sistema di Relation Classification
per il dominio della Pubblica Amministrazione
Candidato:
Carmela Cinquesanti
Relatore:
prof. Alessandro Lenci
2
Sommario
1. Introduzione ... 3
1.1 Obiettivi del lavoro ... 5
1.2 Contributo ... 7
1.3 Contesto applicativo: il progetto SEMPLICE ... 8
2. Rassegna dello stato dell’arte ... 11
2.1 Named Entity Recognition ... 11
2.2 Relation Detection and Classification ... 17
2.3 Machine Learning ... 27
2.3.1 Weka ... 33
2.3.2 Algoritmi di classificazione ... 35
3. Annotazione semantica delle relazioni ... 43
3.1 Preparazione del corpus di training ... 45
3.1.1 Struttura e dimensione del corpus ... 46
3.1.2 Schema di annotazione ... 49
4. Progettazione del classificatore automatico ... 59
4.1 Selezione ed estrazione di features ... 65
4.2 Esperimenti ... 73
4.2.1 Selezione del modello ... 82
4.2.2 Risultati ... 107
4.2.3 Analisi degli errori ... 111
5. Conclusioni ... 118
6. Appendice ... 121
7. Note bibliografiche ... 127
7.1 Bibliografia ... 127
3
1. Introduzione
La presente discussione costituisce un’esposizione del lavoro realizzato al fine di costruire un classificatore automatico in grado di riconoscere e classificare una serie di relazioni tra Named Entities all’interno di un testo. L’attività svolta si inserisce all’interno del progetto SEMPLICE (Semantic Instruments for Public Administrators and Citizens), relativo all’annotazione semantica di documenti appartenenti al dominio della Pubblica Amministrazione e nato dalla collaborazione di 01S Srl, Seacom srl, Bnova srl ed il dipartimento di Linguistica dell’Università di Pisa.
Tale progetto nasce con l’intento di creare una piattaforma di servizi applicativi per la gestione di documenti e informazioni riguardanti le pubbliche amministrazioni, a causa della necessità di agevolare le comunicazioni tra enti pubblici e privati cittadini. Difatti, la valutazione del gradimento da parte della cittadinanza rappresenta uno strumento fondamentale per la conoscenza dei reali bisogni dei cittadini, per un loro più rapido soddisfacimento e per una comunicazione trasparente delle scelte amministrative.
Per la creazione della piattaforma, ci si è avvalsi di elementi di Text Mining, tecniche di classificazione e sistemi per la costruzione di ontologie, al fine di conferire una struttura organica a un variegato insieme di informazioni non strutturate.
Lo sviluppo del classificatore automatico in grado di riconoscere le relazioni tra entità funge da supporto alla costruzione di un sistema ontologico, costituito dall’insieme di tali entità e dalle relazioni che intercorrono tra di esse. Le finalità della creazione dell’ontologia sono strettamente legate all’organizzazione e alla navigazione della piattaforma di SEMPLICE, in quanto ciò rende possibile una consultazione più immediata ed intuitiva dei contenuti.
La presente relazione documenta in maniera strutturata ed approfondita le varie fasi necessarie allo sviluppo del classificatore automatico, partendo
4
dall’esposizione delle decisioni progettuali alla base del lavoro, passando per la raccolta e l’organizzazione del materiale da impiegare come risorsa di addestramento, fino ad arrivare all’illustrazione degli esperimenti effettuati per la costruzione vera e propria del sistema automatico di classificazione.
La discussione fornisce inoltre una presentazione preliminare dei campi di studio coinvolti nel progetto, ovvero gli ambiti di Named Entity Recognition e di Relation Detection and Classification, ponendoli in relazione con le tecniche di Machine Learning impiegate nella creazione di modelli predittivi sui dati.
Nei paragrafi successivi all’introduzione sono descritti gli obiettivi del lavoro svolto, il contributo della tesi, nonché gli aspetti salienti e le finalità del progetto SEMPLICE, all’interno del quale si inserisce la realizzazione del classificatore automatico di relazioni tra Named Entities. In questa fase viene spiegato come lo sviluppo di uno strumento di classificazione automatica risulti fondamentale per l’annotazione semantica di documenti appartenenti alla Pubblica Amministrazione e per la costruzione di un’ontologia strutturata, in funzione di una consultazione più immediata dei contenuti della piattaforma.
Il capitolo 2 rappresenta una rassegna dello stato dell’arte riguardante le aree tematiche di interesse, ed è rivolto pertanto allo studio delle tecniche di Named Entity Recognition e Relation Detection and Classification. Successivamente, il capitolo illustra gli strumenti di Machine Learning utilizzati per la risoluzione del task, che comprendono procedimenti ed algoritmi per l’applicazione e la valutazione dei modelli predittivi sui dati. Il software di Machine Learning impiegato per le analisi è Weka, mentre gli algoritmi scelti per il confronto delle performance sono quelli di Support Vector Machine e di Naive Bayes. Tali argomenti sono collocati all’interno di un inquadramento generale, in modo tale da fornire alcune conoscenze di base con cui comprendere i processi utilizzati durante l’analisi.
Il capitolo 3 delinea il processo di preparazione del corpus di training da utilizzare in fase di addestramento del classificatore automatico, descrivendo la struttura del corpus con il relativo schema di annotazione ed esponendo il modo in cui è avvenuta l’annotazione manuale delle relazioni semantiche nei testi da utilizzare come corpus di addestramento.
5
Il capitolo 4 si concentra sui processi di selezione ed estrazione di features dai testi annotati, al fine di identificare le relazioni tra Named Entities, soffermandosi successivamente sulla progettazione del sistema automatico. La discussione procede con una descrizione completa ed approfondita degli esperimenti necessari alla costruzione del classificatore, documentandole tre fasi fondamentali del lavoro, ovvero addestramento, validazione e selezione del modello predittivo migliore. In questa parte sono presentati i criteri seguiti e le scelte compiute durante gli esperimenti, per giungere infine alla presentazione dei risultati e a un’analisi critica degli errori.
I capitoli 5, 6 e 7 sono dedicati rispettivamente alle conclusioni, all’appendice (che riporta gli esperimenti in forma integrale) e alla bibliografia.
1.1 Obiettivi del lavoro
L’obiettivo del lavoro documentato nella presente relazione risiede nello sviluppo e nell’implementazione di un sistema di classificazione automatica in grado di riconoscere e classificare una serie di relazioni semantiche tra Named Entities all’interno di un testo.
Le Named Entities sono entità nominali, ovvero entità del mondo reale denotabili con un nome proprio. Tali entità possono essere di vario genere, materiali o immateriali, a seconda del tipo di analisi che si vuole condurre. Solitamente, esse si configurano come persone, luoghi, organizzazioni, ecc., ma poiché dipendono fortemente dal dominio possono assumere anche una connotazione più specifica, come nel caso dei nomi di geni e proteine (Cohen e Demner-Fushman, 2014) o dei nomi dei corsi universitari (McCallum, 2005); inoltre, le entità possono essere legate da vari tipi di relazioni semantiche, quali la meronimia, l’iponimia, l’iperonimia, lo stato in luogo, ecc. Lo scopo del classificatore automatico è quello di individuare alcune delle suddette relazioni, categorizzandole in classi semantiche predefinite di interesse per l’analisi. L’automatizzazione del processo è stata realizzata tramite tecniche di apprendimento automatico, ricorrendo a metodi ed algoritmi appartenenti all’ambito del Machine Learning.
6
L’obiettivo finale del lavoro di estrazione e classificazione automatica delle relazioni è quello di costruire un’ontologia da integrare all’interno della piattaforma di SEMPLICE. In informatica, con il termine ontologia si intende una rappresentazione formale ed esplicita dei concetti di interesse nell’ambito di un determinato dominio, in questo caso la Pubblica Amministrazione. L’utilizzo di ontologie trova nell’intelligenza artificiale un campo di applicazione estremamente fertile, in quanto la rappresentazione della conoscenza tramite ontologie permette di avere una visione completa ed immediata del modo in cui le entità sono organizzate, in base alle relazioni che intercorrono tra di esse. Inoltre, l’uso di un’ontologia consente di facilitare la comunicazione fra diversi sistemi informatici, oltre che favorire una serie di compiti tra cui la classificazione, il ragionamento deduttivo e il problem solving.
Nel caso del progetto SEMPLICE, l’ontologia sarà lo strumento necessario per la definizione dei concetti da rappresentare all’interno della piattaforma. Inoltre, poiché l’ontologia permette di definire anche le relazioni tra i concetti, si potrà ottenere allo stesso modo una struttura esplicita dei legami tra concetti. Lo sviluppo dell’ontologia, a sua volta, costituirà la base per la costruzione di un motore di ricerca semantico, che permetterà all’utente di effettuare ricerche sulla base della semantica delle parole.
La differenza principale tra i motori di ricerca semantici e i motori di ricerca tradizionali risiede nel fatto che generalmente questi ultimi, essendo basati sulla sintassi, effettuano la ricerca a partire dalla parole presenti all’interno del testo, senza preoccuparsi del contesto in cui i termini vengono utilizzati. I motori di ricerca semantici, invece, tentano di avvicinarsi ai meccanismi propri dell’apprendimento umano, provando a definire una mappa concettuale che veicoli il significato di quanto si sta leggendo. Il ricorso alla ricerca basata sulla semantica rappresenta un punto di svolta per la semplificazione della gestione di dati non strutturati, in quanto la possibilità per l’utente di interagire con il sistema tramite un linguaggio simile al parlato consente di ottenere risultati molto più ricchi e precisi, ed elimina la necessità di effettuare le ricerche utilizzando le esatte parole contenute nel documento originale. Questi sono i motivi per cui si cercherà di strutturare i concetti e le relazioni relativi alla Pubblica Amministrazione all’interno di un’ontologia completa e coerente, che fornirà a
7
sua volta una solida base su cui incentrare il lavoro di sviluppo del motore di ricerca semantico, in modo tale da arricchire e perfezionare le funzionalità offerte dal progetto SEMPLICE.
1.2 Contributo
Il contributo fornito dal lavoro svolto riguarda la realizzazione di un sistema di classificazione automatica in grado di riconoscere e classificare una serie di relazioni semantiche tra Named Entities all’interno di testi di dominio amministrativo. Lo scopo del lavoro è quello di integrare ed ampliare le funzionalità della piattaforma sviluppata nell’ambito del progetto SEMPLICE, contribuendo alla realizzazione di un’ontologia che possa fungere da supporto all’implementazione di un motore semantico.
L’intero processo di costruzione del classificatore automatico si è svolto seguendo un percorso incrementale suddiviso in più fasi, in cui ciascun momento ha costituito la base per lo sviluppo della fase successiva, ed è avvenuto sotto la supervisione della dott.ssa Lucia Passaro, che ha guidato il lavoro in qualità di esperto del settore.
La prima fase si è concentrata sull’osservazione del corpus di testi a disposizione e delle Named Entities coinvolte nell’annotazione, al fine di definire con precisione le categorie relazionali di interesse. La scelta è ricaduta sui tipi di relazione rilevanti per la costruzione dell’ontologia della piattaforma di SEMPLICE, cercando di individuare le relazioni più interessanti in cui sono tipicamente coinvolte le entità della Pubblica Amministrazione.
Da questa fase, si è passati alla definizione di uno schema di annotazione da impiegare nel processo di preparazione del corpus di addestramento, cui è seguita l’annotazione manuale delle relazioni semantiche all’interno del corpus. Successivamente sono state definite ed estratte dal testo le features rilevanti per la fase di addestramento, concentrandosi principalmente sull’individuazione di features a livello di parola e ricorrendo ad alcune keywords come spie per il riconoscimento delle relazioni tra entità.
8
A causa della significativa mole di lavoro richiesta per lo svolgimento del progetto, sia la fase di definizione delle relazioni che la fase di annotazione ed estrazione delle features sono state realizzate in collaborazione con la collega Federica Semplici, sviluppando il lavoro in maniera parallela ma in completa condivisione delle informazioni, al fine conferire unità e coerenza all’intero svolgimento del progetto.
Le fasi successive, relative alla costruzione e all’addestramento del classificatore automatico, si sono svolte invece in completa autonomia. Il corpus di addestramento è stato sottoposto al software di apprendimento automatico Weka, e sono stati condotti una serie di esperimenti mediante l’addestramento, la validazione e il confronto di due algoritmi di classificazione, ovvero Support Vector Machine e Naive Bayes. I risultati degli esperimenti hanno portato alla definizione di un procedimento di model selection, volto a determinare il modello predittivo migliore nel task di Relation Detection and Classification, in modo da poter impiegare il sistema nella classificazione automatica delle relazioni semantiche anche su testi mai osservati.
La discussione si conclude con un’analisi degli errori riscontrati durante il processo di classificazione automatica, formulando osservazioni e riflessioni che possano risultare utili per futuri sviluppi o miglioramenti nell’ambito dell’annotazione semantica delle relazioni.
1.3 Contesto applicativo: il progetto SEMPLICE
Il progetto SEMPLICE nasce dalla collaborazione tra vari partner, aventi in comune l’interesse per la creazione di strumenti open source in grado di sfruttare l’innovazione tecnologica nella gestione di Big Data e nei sistemi di Business Intelligence.
I partner coinvolti nello sviluppo di SEMPLICE sono 01S Srl, Seacom srl, Bnova srl ed il dipartimento di Linguistica dell’Università di Pisa.
Il progetto SEMPLICE si propone come soluzione per migliorare la comunicazione tra pubbliche amministrazioni, da un lato, e cittadini e imprese,
9
dall’altro. Lo scopo principale è quello di supportare la Pubblica Amministrazione nella gestione digitale dei processi territoriali, fornendo una piattaforma semplice e intuitiva, dotata delle tecnologie informatiche adatte all’organizzazione della grande mole di informazioni in carico alle pubbliche amministrazioni. Le informazioni cui si fa riferimento possono configurarsi sia come dati custoditi nelle banche dati interne agli enti, sia come open data, ovvero dati liberamente accessibili a tutti. Le informazioni non strutturate che si intende riorganizzare con questo progetto riguardano un enorme corpus documentale composto di vari materiali, quali atti amministrativi, documenti riguardanti i cittadini, delibere e determinazioni. Il corpus comprende, pertanto, tutto ciò che scaturisce dall’attività ordinaria della Pubblica Amministrazione, ed è soggetto ad elaborazioni semantiche che permettono di implementare metodi di ricerca e di pubblicazione molto efficienti ed intuitivi.
L’obiettivo principale del progetto è quello di fornire una piattaforma informatica in grado di offrire due tipi di servizi. Il primo riguarda la possibilità di sfruttare l’analisi semantica per una gestione innovativa del patrimonio documentale, tramite le seguenti funzionalità:
- l’analisi linguistica del testo; - l’estrazione di entità;
- la classificazione automatica di contenuti basata su tassonomie e ontologie;
- la creazione di collegamenti automatici tra contenuti.
Il secondo aspetto rilevante delle funzionalità offerte dalla piattaforma si configura nella possibilità di disporre di un sistema di supporto alla programmazione sistematica degli interventi da parte delle amministrazioni, nonché nella capacità di misurare le performance (rating) della Pubblica Amministrazione. Ciò che si intende realizzare è un’interpretazione approfondita e consapevole dei fenomeni che caratterizzano i rapporti tra enti pubblici e cittadini, in modo tale da utilizzare i dati documentali a disposizione per ideare interventi mirati al soddisfacimento dei bisogni dei cittadini, alla conoscenza del sistema territoriale, oltre che alla semplificazione delle azioni amministrative. Nella definizione di questo quadro concettuale, non manca un’attenzione primaria
10
alla comunicazione trasparente tra ente e cittadino, che trae certamente beneficio da un sistema automatizzato ed open source come quello fornito da SEMPLICE.
11
2. Rassegna dello stato dell’arte
Il presente capitolo espone lo stato dell’arte per quanto riguarda i temi principali affrontati durante lo svolgimento del progetto.
In particolare, si descrive il livello cui sono giunte le conoscenze scientifiche nell’ambito della Named Entity Recognition, della Relation Detection and Classification, evidenziando il modo in cui le tecniche di apprendimento automatico vengono applicate ai task appena citati. Nella discussione è presente un ulteriore approfondimento sul settore del Machine Learning e sul software open source Weka utilizzato per le analisi, oltre che sugli algoritmi di supporto ai modelli predittivi impiegati sui dati, ovvero Support Vector Machine e Naive Bayes.
2.1 Named Entity Recognition
Il riconoscimento di Named Entities rappresenta un task centrale nell’ambito dell’estrazione di informazione da testi non strutturati, e si pone come tassello fondamentale per una serie di operazioni linguistiche più complesse, come il task di Relation Detection and Classification; l’attività di estrazione delle relazioni tra entità nominali non può prescindere infatti dall’individuazione preliminare delle Named Entities, un task conosciuto con il nome di Named Entity
Recognition(NER).
Il compito del Named Entity Recognition è quello di individuare ed estrarre da un testo le Named Entities, ossia entità appartenenti al mondo reale (come persone, luoghi, organizzazioni, prodotti, ecc.) e identificabili con un nome proprio. Tali entità possono avere esistenza fisica o natura astratta, e possono essere viste come istanze di concetti generici (ad es., l’entità nominale “Roma” è un’istanza del concetto “città”).
L’utilizzo del termine “Named Entity” sta ad indicare la volontà di includere nella ricerca soltanto entità designate da nomi propri, che devono essere individuate e categorizzate in classi semantiche di interesse definite a priori (Kripke, 1982). Il
12
risultato della categorizzazione funge da base per una serie di applicazioni, quali la costruzione di ontologie, l’indicizzazione e il recupero di informazioni, le metodologie di Relation Detection, i sistemi di question answering, i processi di traduzione automatica o di text summarization.
Lo studio del NER è stato intrapreso per la prima volta nel 1996 come attività parte del Message Understanding Conference (Grishman et al.,1996), sotto forma di estrazione di informazione strutturata riguardante alcune aziende da testi non strutturati (ad es. articoli di giornale). L’obiettivo dell’analisi era quello di individuare e classificare i nomi propri in base a una serie di categorie semantiche predefinite, suddividendo il task principale in due sottotask: riconoscimento delle entità e loro successiva categorizzazione.
La prima documentazione scientifica relativa al NER risale al 1991, con la presentazione dell’articolo di ricerca di Lisa F. Rau alla Seventh IEEE Conference on Artificial Intelligence Applications (Rau, 1991), in cui il riconoscimento e l’estrazione di entità nominali veniva basato su euristiche e regole scritte manualmente. Da quel momento in poi, gli studi in questo campo si sono sviluppati in maniera dinamica e produttiva grazie a svariati workshop e conferenze sul tema, rendendo il NER un argomento sempre più centrale nell’ambito dell’Information Extraction.
Lo scopo principale del task di NER è pertanto quello di individuare le porzioni di testo che costituiscono le entità nominali, e successivamente classificare il tipo di entità identificata. Il processo di riconoscimento può risultare difficile sia a causa dell’ambiguità della segmentazione, in quanto è necessario stabilire cosa rappresenti un’entità in base ai confini di parola, sia a causa dell’ambiguità legata al tipo di Named Entity: una stessa parola può infatti indicare una persona, un luogo o un edificio (si pensi, ad esempio, agli innumerevoli casi di intitolazioni di strade, piazze o altri luoghi a favore di personaggi celebri).
Le classi semantiche generalmente riconosciute per il task di Named Entity Recognition, secondo le specifiche fornite dal Linguistic Data Consortium, sono sette:
1. Nomi di persona 2. Nomi di organizzazioni
13
3. Entità geo-politiche 4. Nomi di luogo 5. Edifici o strutture
6. Strumenti atti allo spostamento 7. Strumenti fisici
Tuttavia, un task di NER può essere basato su un sottoinsieme di queste classi o anche su altre classi ad hoc, a seconda del dominio cui appartengono i testi e in base anche al genere di informazione richiesta per l’analisi.
Le tecniche di Named Entity Recognition variano in relazione al tipo di approccio che si sceglie di adottare; il primo metodo prevede di affidarsi a sistemi basati sulla scrittura di regole di classificazione, che, pur essendo molto precisi, richiedono costi e tempi di sviluppo piuttosto elevati, in quanto dipendono dall’attività manuale dei linguisti. Una seconda alternativa è, invece, quella di utilizzare sistemi di apprendimento automatico, che vengono addestrati su grandi quantità di documenti annotati e sono in grado di trasformare le informazioni acquisite dai testi in conoscenza utile alla categorizzazione. Anche questo approccio richiede un’attività di tipo manuale, costituita dall’annotazione dei testi per l’addestramento, ma si tratta comunque di una mole di lavoro inferiore rispetto alla scrittura di regole.
Solitamente, i metodi automatici di Named Entity Recognition fanno affidamento su un algoritmo standard, il Sequence Labeling (Jurafsky et al., 2016), che effettua l’assegnamento delle categorie a ogni membro di una sequenza di valori osservati (nel caso del NER, alle parole che costituiscono il testo). Addestrando un
sequence classifier, ovvero un sistema automatico che implementi l’algoritmo di sequence labeling, è possibile individuare sia i confini dell’entità in termini di
token sia il tipo di entità, grazie alle caratteristiche (features) delle parole. I sequence classifier solitamente impiegati per il task di NER sono il Maximum-entropy Markov Model (MEMM) o il Conditional Random Field (CRF).
La preparazione del corpus di training per l’addestramento dei sequence classifier avviene tramite l’annotazione dei dati, che può realizzarsi mediante diversi tipi di tagging: il BIO, l’IO, il BMEWO, ecc.
14
Il formato più comune, scelto anche per il lavoro documentato dalla presente relazione, è il BIO (Inside, Outside, Beginning), in cui il tag B indica che il token si trova all’inizio dell’entità, il tag I indica un token interno all’entità, mentre il tag O indica un token esterno all’entità.
In fig. 1, è illustrato un esempio di IO e BIO tagging:
Figura 1
Dopo aver definito la codifica dei dati di training, un aspetto fondamentale per il riconoscimento automatico di entità nominali risiede nell’individuazione di
features, ovvero attributi o caratteristiche delle parole in grado di fornire dati utili
all’apprendimento. La possibilità di rappresentare una parola tramite un gruppo di features, difatti, permette un certo grado di astrazione dal testo, traducendo il flusso testuale in una serie di valori numerici, nominali o booleani da sottoporre al calcolatore. Per esempio, una feature di tipo numerico può essere la lunghezza in caratteri della parola; un attributo nominale, invece, può configurarsi come il lemma della parola; infine, un attributo booleano può corrispondere, ad esempio, al valore true se la parola è scritta con la lettera maiuscola, false altrimenti.
Le features impiegate nel riconoscimento di Named Entities si suddividono in tre categorie:
15
- le features a livello di parola - le features a livello di corpus
- i gazetteers, ovvero liste di entità note che compaiono nel testo
Le features a livello di parola coinvolgono: tratti legati all’ortografia della parola, come la presenza di maiuscole, caratteri speciali o numeri; aspetti relativi alla punteggiatura (ad es. nel caso degli acronimi); caratteristiche di inizio o fine parola significative per l’identificazione di entità (emblematico il caso dei suffissi “ista” o “ore” per individuare le qualifiche professionali, come “musicista” o “professore”).
Le features a livello di corpus interessano aspetti relativi al contesto in cui è inserita la parola, nonché la sua posizione nel documento e gli eventuali metadati disponibili.
I gazetteers sono liste di parole associate a una determinata classe, che fungono da indizio per la rilevazione di entità interessanti nel testo.
Chiaramente, l’utilità effettiva dei vari tipi di features dipende strettamente dal tipo di risorsa a disposizione, dal genere di comunicazione, dal linguaggio e dal mezzo che veicola i contenuti. Ad esempio, le features che riguardano la forma della parola, e che si basano quindi sulla presenza di lettere maiuscole o sull’ortografia, risultano fondamentali per gli articoli di giornale, mentre si rivelano pressoché inutili per le trascrizioni dal parlato o per materiale proveniente da fonti di scrittura informale, come i blog o i forum. Ciò si verifica anche nel caso di lingue basate su un proprio sistema di caratteri, come il cinese, in cui l’informazione relativa alla presenza di maiuscole o minuscole non è disponibile. Pertanto, bisogna considerare le features elencate semplicemente come un punto di partenza da cui iniziare a modellare la propria analisi in base alle peculiarità della risorsa a disposizione.
Con un corpus di training così configurato, è possibile addestrare un sequence classifier con lo scopo di individuare Named Entities su testi nuovi, valutando successivamente le performance raggiunte dal sistema. Le misure solitamente impiegate per valutare i sistemi di NER sono la precisione, la recall e la F-measure. La precisione denota il rapporto tra il numero di istanze correttamente identificate e il numero totale di istanze identificate; la recall indica il rapporto tra
16
il numero di istanze correttamente identificate e il numero di istanze che avrebbero dovuto essere identificate; la F-measure costituisce una media armonica tra precisione e recall.
Sebbene nel mondo della ricerca ci sia la tendenza a ricorrere a modelli totalmente basati sull’approccio statistico, e dunque sull’apprendimento automatico, nell’ambito commerciale spesso si impiegano modelli ibridi che combinano la scrittura di regole all’apprendimento automatico supervisionato (Chiticariu et al., 2013).
Proprio un approccio ibrido è stato utilizzato per il task di Named Entity Recognition implementato nel progetto “SEMPLICE” (Passaro, 2014), che rappresenta un punto focale nell’attività di sviluppo del progetto di tesi, in quanto l’annotazione semantica delle Named Entities funge da base per l’individuazione delle relazioni tra le entità. Il modello di NER per questo progetto, creato dal Laboratorio di Linguistica Computazionale dell’Università di Pisa, è stato generato a partire dall’ibridazione delle tecniche statistiche con un sistema basato su regole, in quanto non era disponibile un corpus annotato di grandi dimensioni appartenente al dominio amministrativo. Per questa ragione, è sorta la necessità di ampliare l’insieme di entità individuate dal modello statistico, in modo da includere eventuali altre entità di interesse: sono state dunque estratte anche le classi che identificano le espressioni temporali e le espressioni monetarie.
Sono state utilizzate diverse features per l’addestramento del modello; in particolare per le features di parola si è scelto di osservare le due parole precedenti e le due parole successive rispetto alla parola target, in modo da operare su finestre di cinque parole. Sono state coinvolte nell’analisi anche features ortografiche e linguistiche, quali la presenza di lettere maiuscole, la posizione della parola all’interno della frase, il lemma corrispondente e la Part of Speech. A questi attributi si sono inoltre affiancati dei gazetteers, riguardanti per esempio, nel caso delle entità geopolitiche, i nomi di tutti i comuni italiani. Per incrementare le performances del modello, è stata estratta anche la feature che codifica la presenza nel testo di multiwords o termini complessi appartenenti alla terminologia di dominio; quest’ultima è stata estratta tramite EXTra, un software
17
sviluppato contestualmente al progetto e progettato per il riconoscimento di termini complessi a partire da pattern di Part of Speech (Passaro et al., 2016). Il modello di NER ottenuto è stato infine adoperato per l’indicizzazione dei documenti disponibili sulla piattaforma del progetto SEMPLICE, quali ad esempio i documenti dell’Albo Pretorio di Sesto Fiorentino e l’archivio delle delibere della Comunità Montana della Valtiberina Toscana. Il risultato di questa indicizzazione basata su Named Entities è stato reso visibile tramite la realizzazione di pagine HTML contenenti il testo con le entità evidenziate mediante fogli di stile CSS.
In fig. 2, è mostrato un documento di “SEMPLICE” così come appare dopo l’intero processo di analisi. Nel testo è ben visibile il modo in cui sono evidenziate le Named Entities:
Figura 2
2.2 Relation Detection and Classification
Il passo successivo alla classificazione di entità nominali consiste nella capacità del sistema di individuare e classificare le relazioni semantiche che sussistono tra le entità all’interno del testo.
18
Le relazioni tra Named Entities sono rapporti di tipo binario, in quanto intercorrono tra coppie di entità, e possono configurarsi come istanze di rapporti linguistici (quali la meronimia, l’iperonimia, l’iponimia, ecc.) o come realizzazioni di un’azione espressa da complemento (come lo stato in luogo).Tuttavia, come avviene nel caso del task di Named Entity Recognition, anche le relazioni sono soggette al dominio della risorsa a disposizione, dunque per alcuni testi è possibile estrarre relazioni molto specifiche e particolari come, ad esempio, la nozione di rotta aerea o il rapporto tra un trattamento farmacologico e una patologia.
Da un punto di vista informatico, una relazione consiste in un set di tuple che legano gli elementi di uno specifico dominio. Nei sistemi relazionali, la relazione rappresenta un’associazione tra elementi dello stesso dominio, e lo scenario in questione è esattamente quello che si configura nel task di Relation Detection and Classification, in cui gli elementi del dominio corrispondono alle entità presenti nel testo.
Esistono molteplici risorse da cui attingere per ottenere liste di relazioni semantiche tra entità, anche in caso di domini molto diversi tra loro. Ad esempio, il progetto ACE (Automatic Content Extraction), sviluppato dal Linguistic Data Consortium, mette a disposizione un ampio insieme di relazioni, nel cui novero sono presenti relazioni fisiche (di locazione, vicinanza e meronimia), relazioni sociali/personali (di tipo lavorativo o familiare), relazioni tra persone e artefatti, relazioni di affiliazione e relazioni tra persone ed entità geopolitiche (Jurafsky et al., 2016). In fig. 3 sono mostrati alcuni esempi delle relazioni individuate dal progetto ACE:
19
Un caso diverso, in cui le relazioni appartengono a un dominio specifico, può riscontrarsi invece nella risorsa prodotta per UMLS (Unified Medical Language System) dall’US National Library of Medicine (Jurafsky et al., 2016). Questa risorsa contiene un insieme di 54 relazioni intercorrenti tra entità nominali, estratte da testi di dominio medico. Le entità sono raggruppate all’interno di categorie molto ampie, in modo tale da raccogliere in un’unica classe più concetti affini, da mettere in relazione come avviene nei casi in fig. 4:
Figura 4
Anche Wikipedia offre una vasta quantità di relazioni, derivabili dalle infoboxes, ovvero le tabelle associate ad alcune voci dell’enciclopedia (Bollacker et al., 2008). Le informazioni strutturate in forma tabellare possono, infatti, essere estratte e trasformate in relazioni tramite RDF (Resource Description Framework), un metalinguaggio che descrive le relazioni come tuple, in cui il legame tra le due entità si traduce in una struttura del tipo soggetto-predicato-oggetto. Pertanto, dalla pagina di Wikipedia sulla Torre Eiffel, facendo riferimento alla voce “Località” presente nell’infobox, è possibile estrarre la seguente informazione (fig. 5):
Figura 5
Un’ulteriore risorsa in cui reperire relazioni tra entità è WordNet (Fellbaum, 1998), un database semantico in cui le connessioni tra Named Enitities sono
20
espresse sotto forma di un’ontologia composta da synset, ovvero raggruppamenti di parole con significato simile, e dalle relazioni tra synset. WordNet vanta un ampio numero di relazioni semantiche, in cui sono incluse l’iponimia, l’iperonimia, la meronimia, l’implicazione e la coordinazione, una condizione particolare in cui due termini sono correlati se hanno almeno un iperonimo in comune.
La risoluzione del task di Relation Detection and Classification può avvenire seguendo diversi approcci: tramite la scrittura manuale di regole di classificazione o mediante l’apprendimento automatico supervisionato, semi-supervisionato o non supervisionato.
Il primo metodo, che prevede la scrittura manuale di pattern (ovvero schemi che definiscono una stringa di riferimento), venne per la prima volta sviluppato e documentato da Hearst (1992a). Il principio su cui si basa riguarda la capacità dell’essere umano di inferire le relazioni semantiche a partire dalla struttura del testo, impiegando una serie di pattern lessico-sintattici in grado di catturare le relazioni di interesse. Per esempio, data la frase:
“Le acque dolci sono state colonizzate nel tempo da alcune specie di molluschi, come i gasteropodi”
il pattern per individuare la relazione di iponimia è:
NP0, come NP1
Il metodo suggerito da Hearst può fornire risultati ancora più precisi se ai concetti coinvolti nella relazione si sostituiscono delle restrizioni legate ai tipi di entità. Per esempio, se si vuole individuare il ruolo svolto da una persona all’interno di un’organizzazione è possibile impostare la ricerca in questo modo:
“Antonio Guterres, Segretario generale delle Nazioni Unite.”
[PER], [POSITION]delle[ORG]
“Antonio Guterres è stato nominato Segretario generale delle Nazioni Unite”
21
Per chiarire questo concetto, si supponga di voler individuare tutte le organizzazioni che hanno sede in un luogo, e di voler quindi estrarre tutte le relazioni di stato in luogo presenti nel testo. Un possibile pattern in grado di identificare la relazione di stato in luogo è:
/ * ha sede a * /
in cui il carattere * (di tipo wildcard) rappresenta una qualsiasi sequenza di caratteri.
Sebbene un pattern di questo tipo riesca ad individuare molti esempi validi, allo stesso tempo esso può fallire in due modi: trovando esempi non pertinenti o tralasciando dei casi corretti che sottendono un pattern diverso. Alcuni esempi individuati ma non pertinenti potrebbero essere:
- “Tradizionalmente, il festival del cinema ha sede a Venezia” - “La seconda riunione ha sede a distanza di tempo dalla prima”
In questo caso, è possibile indirizzare la ricerca verso un esito più preciso sostituendo il carattere wildcard con la tipologia di Named Entity richiesta. Pertanto, il pattern precedente diventa:
/ [ORG] ha sede a [LOC] /
La seconda questione da risolvere riguarda, invece, la possibilità di scartare alcuni esempi rilevanti, ma che non soddisfano i vincoli espressi dal pattern. Ciò accade quando gli esempi scartati presentano delle leggere variazioni, che non combaciano con gli schemi linguistici di riferimento. Esistono due modi per ovviare a questo problema: il primo consiste nella generalizzazione del pattern, in modo tale da includere nella ricerca anche gli esempi che si discostano dal modello espresso dal pattern. Una scelta di questo tipo rischia comunque di
22
introdurre nuovi errori nella ricerca, recuperando gli esempi non pertinenti che si era tentato di escludere specializzando il pattern in prima istanza.
Il secondo metodo, certamente più efficiente, prevede la creazione di un set di patterns altamente specifici, che possano ampliare la gamma di espressioni legate a una determinata relazione, in modo da coprire quanti più esempi possibile. La generazione dei pattern può avvenire manualmente, ovvero tramite la scrittura, da parte di linguisti specializzati, di nuovi pattern inerenti al dominio, oppure può verificarsi in maniera automatica, grazie al metodo del bootstrapping (Jurafsky et al., 2016). Il bootstrapping è un processo di acquisizione linguistica automatica semi-supervisionata in cui i risultati della prima ricerca, effettuata con un piccolo set di pattern di partenza, sono utilizzati per indurre nuovi pattern.
Supponiamo che dalla prima ricerca effettuata con il pattern / [ORG] ha sede a [LOC] /
emerga che
“L’ONU ha sede a New York”.
A questo punto, è possibile ricercare nel testo nuovi pattern utilizzando le parole “ONU”, “sede” e “NewYork” come keywords in co-occorrenza.
Un’analisi di questo genere può fornire risultati del tipo: - “New York è la sede principale dell’ONU”
- “Il Dipartimento di Informazione Pubblica promuove visite alla sede
dell’ONU di New York”
- “A New York si trova la sede dell’ONU”
Dagli esempi estratti si possono quindi ricavare i seguenti pattern: / [LOC] è la sede principale dell’[ORG] /
/ […] sede dell’[ORG] di [LOC] / / A [LOC] si trova la sede dell’[ORG] /
Con l’ausilio di questi pattern aggiuntivi è possibile ampliare la ricerca, in modo da individuare molte più espressioni inerenti alla relazione che si sta cercando.
23
Il principale vantaggio degli approcci che utilizzano la scrittura manuale di pattern risiede nell’alto grado di precisione dei risultati, oltre che nella possibilità di adattare l’analisi alle peculiarità del dominio. Tuttavia, l’impiego di regole scritte a mano spesso comporta il rischio di tralasciare molti casi che andrebbero recuperati, ma che non possono essere catturati a causa della difficoltà di identificare e formalizzare tutti i possibili pattern.
Negli approcci basati, invece, sull’apprendimento automatico supervisionato l’individuazione e la classificazione delle relazioni avviene seguendo un iter ben preciso. I testi vengono annotati con una serie di relazioni scelte a partire da un set predeterminato, e sono successivamente sottoposti ad un algoritmo di machine learning come corpus di addestramento, al fine di riprodurre le annotazioni su un insieme di nuovi testi. Solitamente, il task viene suddiviso in due sotto-compiti: in una prima fase, il classificatore è addestrato per decidere se una coppia di entità nominali sia coinvolta in una relazione o meno, dunque affronta una decisione di tipo binario. Nella seconda fase avviene il vero e proprio processo di classificazione, in cui il sistema deve etichettare le relazioni precedentemente individuate tra le entità.
Anche nel caso del task di Relation Detection and Classification, analogamente a quanto avviene per la Named Entity Recognition, le features costituiscono un strumento fondamentale per l’identificazione di caratteristiche rilevanti per l’estrazione. Il primo di livello di features cui si ha accesso sono quelle relative alle Named Entities, come ad esempio il tipo di entità, le teste sintattiche o la rappresentazione delle entità con il metodo delle bag of words in cui si tiene conto delle parole che le compongono, ignorandone l’ordine.
Il secondo livello di features si ottiene osservando il testo che circonda le entità, individuando per esempio le parole precedenti e successive in base a una finestra di testo prefissata, o la distanza in termini di token tra le due entità, così come il numero di entità tra le due candidate alla relazione.
Anche la struttura sintattica della frase può rivelarsi un aspetto importante, in quanto la presenza di particolari costruzioni sintattiche o di alcuni costituenti può agevolare l’individuazione delle relazioni. Si tratta di un metodo per l’estrazione di features che dipende da un’accurata operazione di analisi linguistica a priori, e
24
che può essere sostituito da un approccio automatico, lasciando che sia il classificatore a codificare certi aspetti delle strutture sintattiche (ad esempio, i
path degli alberi sintattici) come valori di features, scegliendo poi quelle con
livello informativo più alto.
Un approccio di questo tipo richiede, ovviamente, l’accesso a grandi quantità di testi annotati con cui effettuare l’addestramento; se ciò non è fattibile, come spesso accade nella realtà, esiste la possibilità di estrarre le informazioni tramite dei pattern di espressioni regolari, ovvero modelli di stringhe in grado di combaciare (quindi generare un matching) con segmenti di testo che esprimono le relazioni che si stanno cercando.
L’ultima alternativa alla risoluzione del task di Relation Detection and Classification è quella di utilizzare l’apprendimento automatico non supervisionato. Generalmente, è necessario ricorrere a un metodo non supervisionato quando non si ha a disposizione un corpus di training annotato con cui effettuare l’addestramento del sistema; ciò implica la mancanza anche della lista di relazioni cui fare riferimento in fase di estrazione. Questo genere di task è conosciuto con il nome di Open Information Extraction (Jurafsky et al., 2016) poiché l’estrazione avviene su testo libero, non annotato, e senza la necessità di specificare uno schema di annotazione in partenza. Per questo motivo, le relazioni vengono estratte in maniera automatica sotto forma di semplici stringhe, soggette comunque a limitazioni di tipo sintattico e lessicale. Il vincolo più comune nel processo di identificazione delle stringhe prevede che la sequenza cominci con un verbo. In tal modo, si suppone che le relazioni si esprimano comunemente tramite lo schema
NP VP NP
in cui due costituenti nominali sono legati da una struttura verbale. La parte verbale può comunque includere dei nomi al proprio interno, specialmente nel caso di verbi di supporto (come “fare”, “prendere” o “avere”), che si accompagnano a dei sostantivi per esprimere il senso della relazione, e spesso sono seguiti da preposizioni (“fare scalo a”, “prendere parte a”, “avere sede in”). Pertanto, lo schema finale per individuare ed estrarre le relazioni si configura nel modo seguente:
25
NP V|VNP NP
Questa configurazione prevede che al verbo possa sostituirsi, a seconda dei casi, una struttura composta da verbo, sostantivo e preposizione.
Un sistema che adotta il metodo di Open Information Extraction è ReVerb (Fader et al. 2011), un programma in grado di identificare ed estrarre automaticamente relazioni binarie da frasi in lingua inglese ricavate dal web. Oltre a stabilire vincoli di tipo sintattico sulle stringhe, ReVerb impone anche delle limitazioni lessicali, basate su un dizionario che include soltanto le relazioni che occorrono con più frequenza. La scelta di eliminare le relazioni che si verificano con poche entità diverse fra loro nasce dall’idea che questi casi siano probabilmente esempi non pertinenti. Il sistema dapprima applica l’algoritmo di estrazione delle relazioni su un insieme di 500 milioni di frasi provenienti dal web, ottenendo una lista di tutte le relazioni che compaiono nel testo. Successivamente, le relazioni vengono normalizzate tramite la lemmatizzazione e la rimozione di verbi ausiliari, aggettivi e avverbi, in modo tale da ridurre tutte le strutture marcate ad una forma canonica. Infine, vengono aggiunte al dizionario soltanto le relazioni che occorrono con almeno venti entità differenti. Con questo metodo, il sistema effettua un’operazione di pruning sui dati su base lessicale, scartando le relazioni che si rivelano molto rare e quindi poco probabili.
La comodità principale di un approccio automatico non supervisionato risiede nella capacità di gestire l’estrazione delle relazioni senza dover specificare in anticipo gli elementi da ricercare. Per contro, lo svantaggio più grande consiste nella possibilità di estrarre soltanto alcune forme standard di espressione delle relazioni, rischiando di tralasciare molti casi che prevedono una forma di espressione diversa. Difatti, lo stato dell’arte attuale comprende molti sistemi che estraggono principalmente relazioni basate su forme verbali, e che trascurano le relazioni espresse tramite strutture nominali.
I metodi per la valutazione delle performance dei sistemi automatici di Relation Detection and Classification varia a seconda del tipo di approccio adottato.
In primo metodo, utilizzato in caso di apprendimento supervisionato, prevede di misurare l’abilità del sistema sia nella ricerca che nella classificazione di tutte le relazioni all’interno del testo. La valutazione si compie tramite le misure di recall,
26
precision e F-measure, ottenute confrontando i risultati del sistema con un gold
standard, ovvero un set di testi in cui le relazioni sono annotate a mano. Il task di
Relation Detection si valuta sulla base della capacità del sistema di riconoscere semplicemente le entità coinvolte in una relazione, mentre il task di Relation Classification si valuta considerando l’abilità del sistema nel classificare le relazioni in modo corretto.
La valutazione è invece più complessa per i sistemi semi-supervisionati e non supervisionati, poiché non partono da un set prefissato di relazioni, ma individuano ed estraggono nuove relazioni da grandi collezioni di testi o da documenti tratti dal web. Per questa ragione, non è possibile valutarli su piccoli insiemi di test annotati a mano; l’unica soluzione attuabile è quella di approssimare solamente la misura di precisione, revisionando a mano un campione delle relazioni individuate dal sistema. Solitamente, questo tipo di valutazione si focalizza sulla capacità del sistema di riconoscerei tipi di tuple coinvolte in una relazione. Con questo approccio, interessa solo valutare se il sistema è in grado di capire, per esempio, che l’ONU ha sede a New York, senza considerare quante volte e in quanti modi diversi individua questa relazione nel testo. La valutazione avviene, quindi, con il controllo delle tuple da parte di un team di analisti umani, che calcolala precisione del sistema misurando il rapporto tra il numero di tuple corrette e il totale di tuple estratte dal sistema.
Le tecniche di estrazione fin qui illustrate costituiscono lo stato dell’arte per quanto riguarda l’estrazione di informazione semantica a partire da testi non strutturati. I task in questione si presentano quasi sempre come un problema di individuazione dei contenuti di interesse, cui segue una fase di vera e propria classificazione, e gli approcci da impiegare sono molteplici, a partire dalle tecniche di estrazione manuale fino all’adozione di metodi totalmente automatici. Poiché per lo sviluppo del classificatore automatico da impiegare nel progetto SEMPLICE si è scelto di seguire un approccio automatico supervisionato, la discussione si concentrerà ora sugli aspetti fondamentali nell’ambito del Machine Learning.
27 2.3 Machine Learning
La scelta riguardante gli strumenti da impiegare nello svolgimento del progetto si è orientata verso le tecniche di Machine Learning per gli aspetti relativi allo sviluppo e al perfezionamento del processo di addestramento del classificatore automatico.
Il Machine Learning è un campo che comprende le tecniche che consentono la creazione di programmi in grado di migliorare automaticamente con l’esperienza. Si può affermare che un programma apprende dall’esperienza, rispetto a un determinato task T e a una misura di performance P, se la sua performance in T, valutata tramite P, migliora con l’esperienza (Mitchell, 1997). Esistono moltissimi esempi che mostrano l’utilità dell’applicazione delle tecniche di Machine Learning alla risoluzione di problematiche appartenenti ai diversi ambiti della vita reale e che forniscono una panoramica dei risultati raggiunti nello stato dell’arte: nel corso degli anni, infatti, sono stati sviluppati programmi in grado di riconoscere il parlato (Lee 1989; Waibel 1989), di guidare veicoli (Pomerleau 1989), di predire il tasso di guarigione di pazienti affetti da polmonite (Cooper et al. 1997) e di raggiungere performance di livello agonistico nel gioco del Backgammon (Tesauro 1992, 1995).
Un esempio tipico, frequentemente utilizzato per spiegare i processi di apprendimento automatico, è il problema del gioco della dama (Mitchell, 1997). Si supponga di voler costruire un programma capace di giocare a dama, che dovrà essere in grado di migliorare la propria performance nel gioco tramite l’esperienza: in tal caso, la misura di performance sarà data dalla percentuale di partite vinte dal sistema, mentre l’esperienza può essere creata facendo giocare ripetutamente il programma contro se stesso.
Una volta stabiliti il task, la misura di performance e il modo in cui impostare il processo di acquisizione dell’esperienza, è necessario definire tre passi fondamentali per dare inizio all’apprendimento, ovvero definire il tipo di esperienza di training, il tipo di conoscenza che il sistema dovrà apprendere e il modo in cui rappresentare tale conoscenza.
28
Il primo passo, relativo al tipo di esperienza di training da fornire al programma, riguarda principalmente la scelta del modo in cui impostare l’addestramento, se tramite un feedback diretto o indiretto. Il feedback è il procedimento tramite il quale l’insegnante, ovvero colui che addestra il programma, fornisce le risposte corrette al sistema. In caso di feedback diretto, l’insegnante fornisce la risposta esatta per ogni esempio di training, quindi nel caso del gioco della dama mostra al sistema la mossa corretta da compiere per ogni schermata di gioco. In caso di feedback indiretto, invece, l’insegnante fornisce un’informazione di tipo indiretto, mostrando ad esempio soltanto la sequenza di mosse da effettuare con il risultato finale per ogni partita. È importante evidenziare che in questa circostanza il sistema deve affrontare un ulteriore problema di credit assignment, deve cioè comprendere quali mosse sono effettivamente vincenti per il risultato finale e quali invece compromettono il successo della partita. Proprio per questo motivo, l’apprendimento tramite feedback indiretto risulta tipicamente più complesso rispetto all’apprendimento mediante esempi diretti.
Nell’esempio del gioco della dama si è ipotizzato di avere un insegnante con il compito di fornire il feedback al sistema; in realtà, la sequenza di esempi di training può essere gestita in tre modi diversi: un insegnante fornisce per ogni esempio anche la risposta corretta; il sistema seleziona gli esempi più incerti e chiede all’insegnante quale sia la risposta corretta; il sistema sceglie in autonomia sia gli esempi che le risposte (è questo il caso in cui il programma gioca a dama contro se stesso, selezionando sia le schermate che le mosse da effettuare). Qualsiasi approccio si scelga di seguire per la presentazione degli esempi di training, l’importante è che essi siano sufficientemente rappresentativi degli esempi di test, in modo tale che l’esperienza acquisita dal programma in fase di addestramento possa permettere una corretta gestione anche dei casi mai osservati dal sistema.
Il secondo passo da affrontare in fase di addestramento riguarda la scelta del tipo di conoscenza che il sistema dovrà acquisire, un aspetto traducibile con la definizione di una funzione target. La funzione target f(x) rappresenta la formalizzazione del tipo di conoscenza da veicolare tramite l’apprendimento, ed è solitamente oggetto di una qualche forma di approssimazione, in quanto il modello elaborato dal sistema cercherà di avvicinarsi quanto più possibile alla
29
funzione target, che risulta non nota in fase di training. Difatti, dato un set di esempi di training, dove ogni singolo esempio è rappresentato da un vettore di features x e da un output desiderato y, il compito del sistema è quello di formulare un’ipotesi h(x) in grado di approssimare l’output y, rappresentato dalla relazione
y=f(x). Se l’output è di tipo numerico, l’individuazione del modello si configura
come un task di regressione, mentre se l’output è di tipo categoriale, si configura come un task di classificazione.
Il terzo aspetto da considerare durante l’apprendimento è relativo alla scelta della rappresentazione della funzione target, ovvero del modo in cui descrivere il tipo di conoscenza che verrà appresa dal sistema. Esistono molte alternative per rappresentare la funzione target, per esempio tramite l’uso di set di regole, di funzioni polinomiali o di reti neurali. Tuttavia, un aspetto fondamentale da considerare nella scelta della rappresentazione della funzione target riguarda il livello di espressività che si raggiunge con la rappresentazione, ovvero la capacità di generalizzare a partire da un set di dati di training. Se da un lato si aspira a ricercare una rappresentazione molto espressiva, in grado di approssimare quanto più possibile la funzione target ideale, dall’altro lato una soluzione di questo tipo richiede moltissimi esempi di training da presentare al sistema, al fine di discriminare con precisione tra le diverse ipotesi rappresentate. La soluzione migliore è quella di ricercare un equilibrio tra i vari aspetti della rappresentazione, unendo una buona espressività a una gestione efficiente degli esempi di training. Nell’esempio del gioco della dama, si è scelto di rappresentare la funzione target tramite una combinazione lineare delle seguenti caratteristiche associate alle schermate di gioco:
- x1: il numero di pezzi neri presenti nella schermata
- x2: il numero di pezzi bianchi presenti nella schermata
- x3: il numero di dame nere presenti nella schermata
- x4: il numero di dame bianche presenti nella schermata
- x5: il numero di pezzi neri minacciati dai bianchi
- x6: il numero di pezzi bianchi minacciati dai neri
La rappresentazione della funzione target si configura, pertanto, come la seguente funzione lineare:
30
V(b) = w0 + w1 x1 + w2 x2+ w3 x3+ w4 x4+ w5 x5+ w6 x6
in cui i simboli da w1a w6 sono coefficienti numerici che rappresentano i pesi da associare ai singoli elementi della funzione. I pesi vengono stabiliti dall’algoritmo di apprendimento e determinano l’importanza del contributo di ciascun elemento nella definizione del valore della schermata di gioco. La costante w0 è un peso aggiuntivo che viene applicato al valore schermata nella sua interezza. Il compito dell’algoritmo di apprendimento è pertanto quello di scegliere un set di pesi in grado di minimizzare l’errore quadratico medio tra i valori di training e i valori predetti dal sistema, fornendo un’approssimazione della funzione target quanto più vicina possibile alla funzione ideale.
Per comprendere a fondo cosa avviene nel processo di classificazione automatica supervisionata, bisogna fare riferimento ai meccanismi alla base del concept
learning, ovvero la capacità di acquisire la definizione di una categoria dato un
campione di esempi positivi e negativi (Mitchell, 1997). L’obiettivo di un sistema di concept learning è quello di imparare un concetto osservando un determinato set di esempi, ciascuno composto da un insieme di attributi (o features) e accompagnato dal rispettivo target value che segnala l’appartenenza o meno dell’esempio alla categoria.
Si supponga di voler realizzare l’apprendimento del concetto “Giorni in cui
pratico sport d’acqua”.
In fig. 6 sono mostrati alcuni esempi, con i relativi valori per ogni attributo e con la colonna Target Value, che indica l’appartenenza o meno dell’esempio al concetto.
31
Lo scopo del task è quello di imparare a predire il valore del Target Value per gli esempi mai osservati, basandosi sui valori degli altri attributi. Ciò significa che occorre formulare un’ipotesi che sia coerente con gli esempi di training e che possa quindi fornire una generalizzazione per gli esempi mai osservati.
Un’ipotesi consiste in una serie di vincoli da applicare ai valori degli attributi; il processo di apprendimento prevede una ricerca all’interno dello spazio di tutte le possibili ipotesi, al fine di individuare quella più consistente con gli esempi di training. Nel caso del concetto “Giorni in cui pratico sport d’acqua”, ogni ipotesi consiste in un vettore di sei vincoli, che specificano i valori dei sei attributi. Ciascun attributo può quindi assumere un valore del tipo:
- ?se ogni valore è accettabile - Ø se nessun valore è accettabile
- un valore specifico (ad es. il valore “Caldo” per l’attributo “Temperatura”) Ogni ipotesi h si configura pertanto come un vettore composto dai valori (?, Ø, val. specifico) degli attributi. Se un’istanza x soddisfa tutti i vincoli imposti dall’ipotesi h, allora h classifica x come un esempio positivo(h(x) = 1).
Ad esempio, se si volesse illustrare l’ipotesi per cui i “Giorni in cui pratico sport
d’acqua” sono soltanto quelli molto freddi e umidi, a prescindere dal valore dei
restanti attributi, bisognerebbe rappresentare l’ipotesi con la seguente espressione:
‹?, Freddo, Alta, ?, ?, ?›
L’ipotesi più generica, ovvero quella per cui ogni esempio è considerato positivo, è rappresentata dall’espressione:
‹?, ?, ?, ?, ?, ?›
mentre l’ipotesi più specifica, per cui nessun esempio è considerato positivo, è rappresentata da:
‹Ø, Ø, Ø, Ø, Ø, Ø›
In sostanza, il processo alla base del concept learning intende realizzare l’apprendimento a partire dall’osservazione del set di esempi positivi descritti da una determinata congiunzione di vincoli sugli attributi, ricercando, all’interno dello spazio di tutte le possibili ipotesi, quella che maggiormente si adatta ai dati
32
di training, nella prospettiva di poter operare una generalizzazione su un set di dati mai osservati. Gli elementi a disposizione, in fase iniziale, sono il set di istanze X, su cui si definisce il concetto target C da apprendere; al sistema viene presento un sottoinsieme delle istanze x di X, accompagnate dal valore target C(x), che costituisce il set di training, per cui:
C(x) = 1 indica un esempio positivo
C(x) = 0 indica un esempio negativo.
L’obiettivo del sistema è quello di sfruttare la conoscenza estrapolata dall’osservazione degli esempi di training e dall’analisi dei valori delle varie features per formulare un’ipotesi che coincida con il concetto target C. La ricerca dell’ipotesi migliore avviene all’interno di uno spazio di ipotesi H, solitamente predefinito dall’analista umano in base alle proprie scelte di rappresentazione. In generale, ogni ipotesi h in H rappresenta una funzione booleana definita su X e l’obiettivo del sistema è di trovare un’ipotesi tale che h(x) = c(x) per tutte le istanze x in X, non soltanto per quelle di training.
Sebbene il fine ultimo del concept learning sia quello di trovare l’ipotesi identica al concetto target per tutto il set di istanze X, l’unica informazione disponibile riguarda il valore di C per gli esempi di training; pertanto, è necessario assumere che l’ipotesi migliore per l’intero set di istanze (anche per quelle mai osservate) sia quella che più si adatta agli esempi di training. Si tratta di un’assunzione fondamentale per operare un’approssimazione del concetto target, che si può racchiudere nella definizione di apprendimento induttivo. L’ipotesi dell’apprendimento induttivo afferma che:
“Any hypothesis found to approximate the target function well over a sufficiently
large set of training examples will also approximate the target function well over other unobserved examples”, (Mitchell, 1997).
Gli algoritmi alla base dei task di concept learning operano quindi un’approssimazione della funzione target, basandosi sulla ricerca dell’ipotesi migliore a partire dall’analisi del vettore di features associato a ciascun esempio di training. Tali algoritmi vengono poi impiegati per la costruzione di sistemi di
33
classificazione automatica, solitamente tramite il ricorso a software di Machine Learning che implementano queste metodologie.
Per la costruzione del classificatore da integrare all’interno del progetto SEMPLICE, la scelta è ricaduta sul software open source di apprendimento automatico Weka (“Waikato Environment for Knowledge Analysis”), un programma che permette di applicare metodi di Machine Learning a un set di dati e di analizzarne il risultato. Nel prossimo paragrafo, verranno descritte nel dettaglio le funzionalità offerte dal software, impiegato per questo progetto nella versione 3.8.0.
Per quanto riguarda gli algoritmi per la classificazione dei dati, si è scelto di confrontare e valutare le performance di due modelli distinti, ovvero l’algoritmo di Support Vector Machine e l’algoritmo di Naive Bayes. Nel corso della discussione, verranno presentati il funzionamento e le caratteristiche di entrambi i modelli.
2.3.1 Weka
Weka è un software open source sviluppato per supportare le metodologie di Data Mining e di Machine Learning, scritto in linguaggio Java e distribuito sotto la GNU Public License. Il suo utilizzo, che avviene principalmente in ambito didattico-scientifico, è facilitato da un’interfaccia grafica semplice e intuitiva, che si compone di diverse sezioni operative a seconda del tipo di analisi che si vuole condurre sui dati. Il software offre, infatti, un insieme di strumenti per il pre-processing dei dati, cui si accompagna una vasta scelta di algoritmi di apprendimento e di metodi di valutazione delle performance.
Le sezioni cui l’utente può accedere sono quattro:
- Simple CLI: l’interfaccia gestibile da riga di comando;
- Explorer: l’ambiente grafico in cui avviene l’esplorazione e l’analisi dei dati;
- Experimenter: la sezione in cui è possibile effettuare test statistici tra i vari algoritmi di Data Mining;
34
- Knowledge flow: ambiente che consente di generare una rappresentazione grafica del flusso di analisi, formato da connessioni tra i moduli.
Il formato utilizzato da Weka per la lettura dei dati è l’ARFF (Attribute Relationship File Format), una codifica che rappresenta le istanze come elementi di una tabella in un database relazionale. L’idea alla base di questo formato è quella di considerare il dataset come un insieme di attributi e valori, ovvero tuple legate da una relazione e inserite all’interno di tabelle; all’interno delle tabelle, le istanze sono rappresentate dalle righe e gli attributi dalle colonne. Il formato ARFF è molto simile al formato CSV, e proprio a partire da quest’ultimo è possibile anche effettuare la conversione dei dati direttamente tramite il software. Il workflow sotteso alla costruzione del classificatore per il progetto SEMPLICE prevede che lo script in Python, dopo aver estratto le features necessarie all’analisi, produca un file in formato ARFF, da importare direttamente all’interno di Weka.
Una volta caricato il dataset all’interno dell’ambiente, è possibile effettuare varie operazioni di pre-processing sui dati, estremamente utili nel caso in cui sia necessario filtrare o trasformare i dati per esigenze di analisi. Il pre-processing avviene mediante dei filtri, che consentono operazioni di discretizzazione, normalizzazione o ricampionamento dei dati, ma anche la selezione o la trasformazione di attributi. La funzionalità di selezione degli attributi (o feature
selection) è certamente una delle più rilevanti, in quanto consente di eseguire
degli esperimenti per determinare il subset di features con il più alto livello informativo, vale a dire le caratteristiche maggiormente utili in fase di predizione su dati mai osservati.
L’interfaccia del pre-processing offre, inoltre, la possibilità di visualizzare mediante dei grafici la distribuzione dei dati rispetto ad un particolare attributo. Dopo aver effettuato le eventuali operazioni di pre-processing, il software consente di scegliere un algoritmo di predizione da applicare ai dati, a partire da una nutrita lista di algoritmi che consentono sia operazioni di classificazione che di regressione; in questa fase, è possibile modificare gli iperparametri dell’algoritmo scelto, al fine di stabilire la configurazione migliore, quella cioè che consente un livello di predizione soddisfacente sui dati. Inoltre, l’interfaccia
