Un componente NER Multi-language per il TermExtractor

”Sapienza”, Universita di Roma

Facolta di Ingegneria dell’Informazione,Informatica e Statistica

Tesi di Laurea Magistrale in

Informatica (ex. DM270)

Un componente NER Multi-languageper il TermExtractor

Relatore Candidato

Prof. Paola Velardi Sofien Vannutelli

Anno Accademico 2013/2014

Ringraziamenti

”Fatti non foste per viver come bruti, ma per seguir virtute e canoscenza”DANTE (Canto XXVI).

In questa pagina, tutta mia, voglio prendere l’occasione per ringraziare tutte quellepersone che, con il loro aiuto e con il loro impegno, mi hanno aiutato a crescere,maturare e a diventare la persona che sono oggi. Ringrazio quindi: tutti il collegiodei professori e dei ricercatori del Dipartimento di Informatica, in particolare lamia relatrice, la Prof. Paola Velardi, per la sua professionalita, disponibilita edattenta assistenza, il Prof. Panizzi per l’ottimo rapporto d’amicizia creato durantela collaborazione nella preparazione degli eventi ITMeeting e il Prof. GiancarloBongiovanni per la sua bonta e disponibilita infinita; tutto il personale della Di-dattica, in particolare la responsabile, la Dott.ssa Alessandra Fremiotti, per la suagrande professionalita e disponibilita verso tutti gli studenti dei corsi di Informat-ica; e tutto il personale Tecnico ed Amministrativo; tutto il collegio dei professorid’arabo dell’Institut Bourguiba des Langues Vivantes di Tunisi, nessuno e escluso.Ringrazio i miei genitori che mi hanno dato la possibilita di studiare, perche solocon lo studio si puo arrivare a capire davvero l’importanza delle cose. Grazie an-che agli amici, perche la vita non e fatta solo di libri e di famiglia, ma anche dirisate e momenti passati in compagnia, senza pensare ai doveri. E per finire voglioringraziare VIVIANA ARRIGONI, con cui ho stupidamente e tristemente rotto unbellissimo rapporto di amicizia, alla quale va il merito di avermi letto e corretto imiei strafalcioni di questa sezione.

Grazie a tutti.

Contents

1 Introduzione 7

2 Background 102.1 Che cosa e il Natural Language Processing? . . . . . . . . . . . . . 102.2 Il Natural Language Processing e la linguistica . . . . . . . . . . . . 12

2.2.1 Sintassi e semantica . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Contesto e pragmatica . . . . . . . . . . . . . . . . . . . . . 122.2.3 Due punti di vista . . . . . . . . . . . . . . . . . . . . . . . 132.2.4 Task e super-task . . . . . . . . . . . . . . . . . . . . . . . . 142.2.5 Strumenti a disposizione . . . . . . . . . . . . . . . . . . . . 15

2.3 TermExtractor: un estrattore terminologico . . . . . . . . . . . . . 202.4 Caratteristiche della lingua araba . . . . . . . . . . . . . . . . . . . 21

2.4.1 Storia e prospettive correnti . . . . . . . . . . . . . . . . . . 212.4.2 Ortografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.3 Morfologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.4 Generazione delle parole dalla forma base . . . . . . . . . . 242.4.5 Struttura della parola araba . . . . . . . . . . . . . . . . . . 252.4.6 L’ambiguita nella lingua araba . . . . . . . . . . . . . . . . 272.4.7 I nomi propri nella lingua araba . . . . . . . . . . . . . . . . 272.4.8 Struttura . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.9 Sintassi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.4.10 Pecularieta e sfide nella corretta rilevazione e classificazione

dei nomi propri in arabo . . . . . . . . . . . . . . . . . . . . 30

3 Stato dell’arte 323.1 Metodi di apprendimento per i sistemi NER . . . . . . . . . . . . . 33

3.1.1 Apprendimento Supervisionato . . . . . . . . . . . . . . . . 333.1.2 Apprendimento Semi-supervisionato . . . . . . . . . . . . . 343.1.3 Apprendimento Non Supervisionato . . . . . . . . . . . . . . 34

3.2 Stato dell’arte e related work dei sistemi English NER . . . . . . . 36

2

3.3 Stato dell’arte e related work dei sistemi Italian NER . . . . . . . . 393.4 Stato dell’arte e related work dei sistemi Arabic NER . . . . . . . . 42

4 Descrizione del parser LingPipe 444.1 Una breve panoramica . . . . . . . . . . . . . . . . . . . . . . . . . 444.2 Elenco delle risorse e delle lingue disponibili . . . . . . . . . . . . . 464.3 Il diagramma dei componenti . . . . . . . . . . . . . . . . . . . . . 484.4 Named Entity Recognition di LingPipe . . . . . . . . . . . . . . . . 50

4.4.1 Regular Expression-Based Chunker . . . . . . . . . . . . . . 504.4.2 Dictionary-Based Chunker . . . . . . . . . . . . . . . . . . . 514.4.3 Model-Based Chunker . . . . . . . . . . . . . . . . . . . . . 524.4.4 Addestramento del modello per un sistema NER . . . . . . 54

4.5 Part-Of-Speech Tagger di LingPipe . . . . . . . . . . . . . . . . . . 604.5.1 POS tag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.5.2 Addestramento del modello per un sistema POS Tagger . . 614.5.3 Lettura del modello . . . . . . . . . . . . . . . . . . . . . . 634.5.4 Tokenizzazione . . . . . . . . . . . . . . . . . . . . . . . . . 634.5.5 Analisi dei token . . . . . . . . . . . . . . . . . . . . . . . . 634.5.6 Risultato finale . . . . . . . . . . . . . . . . . . . . . . . . . 64

5 Analisi del modulo POS Tagger di LingPipe 655.1 POS Tagger: confronto con il TreeTagger . . . . . . . . . . . . . . . 65

5.1.1 TreeTagger . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.1.2 Che cosa sono i tag-set? . . . . . . . . . . . . . . . . . . . . 685.1.3 L’algoritmo Tag-Set Reduction . . . . . . . . . . . . . . . . 685.1.4 L’applicazione Tag-Set Reduction Computing . . . . . . . . 715.1.5 Applicazione della riduzione del tag-set per il TreeTagger . . 735.1.6 Applicazione della riduzione del tag-set per il POS Tagger

di LingPipe . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.1.7 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6 Architettura del sistema 836.1 La progettazione in UML del sistema . . . . . . . . . . . . . . . . . 83

6.1.1 Glossario di Progetto . . . . . . . . . . . . . . . . . . . . . . 836.1.2 Gli attori . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.1.3 Requisiti del sistema . . . . . . . . . . . . . . . . . . . . . . 846.1.4 Requisiti Funzionali . . . . . . . . . . . . . . . . . . . . . . 856.1.5 Requisiti Non-Funzionali . . . . . . . . . . . . . . . . . . . . 866.1.6 Casi d’Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . 866.1.7 Analisi dei punti funzione . . . . . . . . . . . . . . . . . . . 876.1.8 Diagramma delle Attivita . . . . . . . . . . . . . . . . . . . 90

3

6.1.9 Diagramma dei Componenti . . . . . . . . . . . . . . . . . . 946.1.10 Gestione requisiti non-funzionali . . . . . . . . . . . . . . . 97

6.2 Schema dell’architettura . . . . . . . . . . . . . . . . . . . . . . . . 996.2.1 Estrazione delle frasi . . . . . . . . . . . . . . . . . . . . . . 1016.2.2 Grammar Configuration . . . . . . . . . . . . . . . . . . . . 1016.2.3 Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066.2.4 Merge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.3 Il modulo English NER . . . . . . . . . . . . . . . . . . . . . . . . . 1096.3.1 Differenze del modulo E-NER . . . . . . . . . . . . . . . . . 110

6.4 Il modulo Italian NER . . . . . . . . . . . . . . . . . . . . . . . . . 1116.4.1 Differenze del modulo I-NER . . . . . . . . . . . . . . . . . 113

6.5 Il modulo Arabic NER . . . . . . . . . . . . . . . . . . . . . . . . . 1146.5.1 Differenze del modulo A-NER . . . . . . . . . . . . . . . . . 116

7 Valutazioni 1187.1 Accuratezza, Precision, Recall e F1-Score . . . . . . . . . . . . . . . 1187.2 Valutazione delle prestazioni . . . . . . . . . . . . . . . . . . . . . . 120

7.2.1 Valutazione delle annotazioni con ENAMEX Named Entities 1247.2.2 Valutazione del component di estrazione terminological NER

Multi-language . . . . . . . . . . . . . . . . . . . . . . . . . 1267.3 Riepilogo e conclusioni finalli sulla valutazione . . . . . . . . . . . . 129

8 Applicazioni Future 1318.1 Sistemi Question & Answer . . . . . . . . . . . . . . . . . . . . . . 1318.2 Sistemi per la ricerca di letteratura accademica . . . . . . . . . . . 1338.3 Applicazioni web e-commerce . . . . . . . . . . . . . . . . . . . . . 134

A Apprendimento Automatico 135

B Hidden Markov Models 137

C Espressioni regolari 140

Bibliography 142

4

List of Tables

2.1 Esempi di generazione di forme basi. . . . . . . . . . . . . . . . . . 252.2 Proclitiche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.3 Enclitiche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1 I migliori quattro sistemi sul task Entity Estraction al MUC. . . . . 37

4.1 Lista di Token e di Entity Tag associati in una frase. . . . . . . . . 564.2 Lista di Token e di Entity Tag generati da un modello stocastico

(HMM). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3 Lista di Token e di Entity Tag associati in una frase. . . . . . . . . 594.4 Le sequenze legali con il sistema BIO. . . . . . . . . . . . . . . . . . 594.5 Lista di Token e di Entity Tag associati in una frase. . . . . . . . . 61

5.1 Tabella di Mapping per la riduzione del tag-set di TreeTagger. . . 745.2 Tabella di Mapping per la riduzione del tag-set di TreeTagger (2). 755.3 Tabella di Mapping per la riduzione del tag-set di TreeTagger (3). 765.4 Tabella di Mapping per la riduzione del tag-set di LingPipe. . . . . 775.5 Tabella di Mapping per la riduzione del tag-set di LingPipe (2). . . 785.6 Tabella di Mapping per la riduzione del tag-set di LingPipe (3). . . 795.7 Tabella di Mapping per la riduzione del tag-set di LingPipe (4). . . 805.8 Tabella riassuntiva dei risultati finali. . . . . . . . . . . . . . . . . . 82

6.1 Tabella dei coefficienti. . . . . . . . . . . . . . . . . . . . . . . . . . 886.2 Valori di aggiustamento dei VAF. . . . . . . . . . . . . . . . . . . . 896.3 Tabella riassuntiva per l’applicazione della Capitalizzazione Con-

venzionale, come regola, nella valutazione dei linguaggi. S = sicapitalizzata; N = non capitalizzata; Q = qualche volta. . . . . . . 103

6.4 Elenco delle regole (ambigue e non-ambigue) utilizzate per la con-figurazione della grammatica. . . . . . . . . . . . . . . . . . . . . . 110

6.5 Elenco delle regole, ambigue e non-ambigue, utilizzate per la con-figurazione della grammatica. . . . . . . . . . . . . . . . . . . . . . 113

5

6.6 Elenco delle regole (solo non-ambigue) utilizzate per la configu-razione della grammatica. . . . . . . . . . . . . . . . . . . . . . . . 117

7.1 Risultati della valutazione per la lingua araba. . . . . . . . . . . . . 1267.2 Risultati della valutazione per la lingua italiana. . . . . . . . . . . . 1267.3 Accuratezza raggiunta per la lingua inglese. . . . . . . . . . . . . . 1277.4 Accuratezza raggiunta per la lingua italiana. . . . . . . . . . . . . . 1277.5 Accuratezza raggiunta per la lingua araba. . . . . . . . . . . . . . . 1277.6 Accuratezza totale del component di estrazione terminological NER

Multi-language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6

Chapter 1

Introduzione

I motori di ricerca ”tradizionali” abbinano i documenti basandosi unicamente sulleparole chiave della query dell’utente. Tuttavia esistono degli strumenti in gradodi fornire risultati piu precisi eseguendo l’analisi semantica del testo.

Il Named Entity Recognition (NER) e uno di questi strumenti, che meglio com-prende le tecnologie per l’analisi del testo ed e uno dei pilastri per il trattamento deicontenuti non strutturati; per fare questo, esistono diversi approcci, che possonoessere anche combinati insieme.

Uno di questi strumenti e noto come Named Entity Recognition (NER) e unasotto-area dell’elaborazione del linguaggio naturale.

NER, inoltre, e anche un sub-task dell’Information Extraction1, in quanto ha comeobiettivo quello di estrarre i nomi propri o entita2 proprie (in inglese Named En-tities o NEs) di: persone, organizzazioni, toponimi, espressioni temporali, valorinumerici, nomi di prodotti, nomi di geni, URLs ed indirizzi email, provenienti daun set di testi non strutturati, provenienti da varie fonti (per esempio: pagine web,newsletters, twitter, etc.), si vuole estrarre ed identificare tutte le entita proprieal loro interno. NER e uno dei pilastri per il trattamento dei contenuti non strut-turati, in quanto i nomi propri sono pervasivi nei testi e molto frequenti nelle querydegli utenti. Il problema della NER viene risolto utilizzando diversi approcci, che

1L’Information Extraction e un task particolarmente complesso, che ha come obiettivo quellodi estrarre automaticamente informazioni strutturate da un testo non strutturato. Le infor-mazioni estratte consentono di descrivere il contenuto dei documenti, in quanto l’utente accedeprima all’informazione ed in seguito al documento in cui essa e contenuta.

2In un contesto di questo genere, un’entita e definita come il nome di: una persona, un luogo,un’organizzazione, una dimensione, una data/ora, o di un qualsiasi altro termine, che spiega iltipo di sostantivo.

7

possono essere anche combinati insieme.

Figure 1.1: Schema di un tipico sistema di Information Extraction con i moduliin cascata.

La differenza, tra il testo strutturato ed il testo non strutturato (o di dominioaperto), e che il testo strutturato risiede in uno schema relazionale di una basedi dati, dove a ciascuna colonna gli si associa un attributo e il testo stesso econtenuto in una cella, grazie alla quale esso assume un significato esplicito, peresempio: una colonna numerica intitolata ”prezzo” rappresenta il costo di un certoarticolo; mentre nel testo non strutturato, l’estrazione delle stesse informazionie piu difficile, poiche non esiste alcuna struttura sottostante, tranne quella dellinguaggio stesso (morfologia, grammatica).

L’obiettivo di questa tesi e di arricchire un sistema di estrazione terminological pre-esistente, TermExtractor [21] uno strumento di riconoscimento di Named Entities,per tre lingue: inglese, italiano e arabo. La tesi e articolata come segue:

• Nel Capitolo 2 viene fatta una breve panoramica dell’area dell’Elaborazionedel Linguaggio Naturale, viene descritto il component di estrazione termi-nological TermExtractor, e si descrivono alcune caratteristiche della linguaaraba. Infatti, la parte piu complessa di questo lavoro e stata costruireil component NER per la lingua araba, che presenta particolari elementiche rendono piu difficile utilizzare algoritmi NER comunemente usati per lelingue europee.

• Nel Capitolo 3 viene presentato lo stato dell’arte nell’area della NER, ingenerale e per le tre lingue considerate in questa tesi.

• Nel Capitolo 4 si descrive LingPipe, un toolkit liberamente disponibile perla costruzione di sistemi per l’analisi del linguaggio naturale. LingPipe si erivelato particolarmente versatile per gli obiettivi di questa tesi.

• Nel Capitolo 5 si descrive l’analisi prestazionale del modulo Part-of-SpeechTagger di LingPipe, confrontandolo con il TreeTagger.

• Nel Capitolo 6 e dedicato alla valutazione delle prestazioni.

• Il Capitolo 7 e dedicato ad esporre le conclusion e ad analizzare possibilifuturi sviluppi.

8

• Infine, il Capitolo 8 e dedicato ad esporre e conclusioni e ad analizzare pos-sibili futuri sviluppi.

9

Chapter 2

Background

2.1 Che cosa e il Natural Language Processing?

Un dialogo molto famoso, che si trova sul Web, e tra il programma Elizaed uno dei suoi autori. Eliza e un’invenzione AI del 1960, la quale imp-iega un metodo primitivo di pattern-matching, per rispondere agli utenti,sostenendo, di sorta, una conversazione. L’obiettivo di Eliza era quello diricoprire il ruolo di psicoterapista, cosı che essa poteva sostenere una con-versazione terapeutica con il paziente, anche se nel lungo andare le rispostedi Eliza si potevano deteriore in schiocchezze. Attualmente, ci sono in giroaltri programmi identici ad Eliza, ma questi non hanno migliorie rispettoall’originale, ovvero non implementano dei nuovi trucchi linguistici.

Il termine Natural Language Processing [11, 19] (NLP) e usato per descrivere nor-malmente la funzione di un software o di un componente hardware all’interno diun sistema informatico, che analizza o sintetizza il linguaggio parlato (o scritto).L’epiteto naturale e quindi destinato a fare una distinzione tra il linguaggio umanoe la scrittura dei linguaggi piu formali1 oppure i linguaggi di programmazione2. IlNatural Language Understanding3 (NLU) (in italiano Comprensione del Linguag-gio Naturale) e associato ad un’obiettivo piu ambizioso, ovvero, avere un sistema,all’interno di una macchina, che e in grado comprendere il linguaggio naturale,come se fosse un essere umano.

Questo significa che e possibile programmare una macchina, ad esempio: unamacchina che sia in grado di comprendere il codebyte di Java.

1Come le notazioni matematiche o logiche.2Come il Java, il LISP, il C++, etc.3Il Natural Language Understanding e un sub-topic del Natural Language Processing e si

occupa di far comprendere, ad una macchina, la lettura di un testo scritto in linguaggio naturale.

10

E anche possibile programmare un computer per risolvere molti enigmi matematicie logici, e dimostrare teoremi ed anche venire con nuove congetture, ma l’analisidelle parole e del testo da parte di un calcolatore rimane pieno di problemi, siapure interessanti.

Si potrebbe pensare, che nessuno di questi problemi potrebbero avere un minimodi interesse commerciale, se non fosse per il fatto, che la necessita di informazioni,come oggi, sia cresciuta in modo esponenziale, rispetto agli altri mercati. Esse,ormai, sono disponibili in formato digitale, con libero accesso, una dimostrazioneconcreta ne e il Web. La questione, quindi, non e piu la mancanza di informazioni,ma la mancanza di strumenti per la loro organizzazione ed offrirle al prezzo giustoed al momento giusto. La maggior parte di queste informazioni e ancora espressain un formato testuale, piuttosto che: in immagini, in grafici, in suoni, etc. Moltedi queste risiedono nei database relazionali e sono state estratte dai documenti informato digitale, fogli di calcolo e tabelle.

Ambiguita nel Natural Language Processing

L’ambiguita linguistica e qualche volta una sorgente di umorismo, ma molteparole e frasi hanno molteplici interpretazioni, che passano inosservate. Peresempio, il nome ”bank” assume molti significati nella lingua inglese. Essopuo riferirsi ad un’istituto bancario oppure ad un margine di un fiume. Lepersone raramente confondono questi significati, a causa dei diversi con-testi in cui i token di questa parola occorrono ed il perche della conoscenzareale della parola. Ad esempio, chiunque legga i giornali conosce che, ”theWest Bank of Jordan” non si riferisce ad un istituto bancario, bensı allasponda occidentale della Giordania4, quindi il termine ”bank” e un’istanzadell’ambiguita lessicale. Intere frasi possono essere ambigue rispetto allaloro struttura e quindi anche il loro significato.

4Esso e un territorio senza sbocco al mare sulla riva occidentale del fiume Giordano, nel VicinoOriente.

11

2.2 Il Natural Language Processing e la linguistica

E necessario prima dare alcune brevi definizioni sui concetti della linguistica tradi-zionale[11, 19]. Le sezioni, che seguono, introdurranno alcuni concetti e termi-nologie, che sono il tema comune di discussione in questo campo. La coperturadi queste tematiche e destinata ad essere superficiale, ma non in modo semplicis-tico.

2.2.1 Sintassi e semantica

Chomsky5 fa una netta distinzione tra le frasi, che sono sintatticamente ”anomale”(o ”non lineari”), come ad esempio

’Furiously sleep ideas green colorless.’

e le frasi, che sono grammaticalmente ben formate, ma semanticamente ”anomale”,come ad esempio

’Colorless green ideas sleep furiously.’

Il fatto che si e in grado di ”rompere” le regole del linguaggio, nei due modi com-pletamente diversi visti sopra, e spesso portato come prova per la ”scomponibilita”della sintassi e della semantica nel linguaggio. Un presupposto e che si puo primaanalizzare la struttura sintattica di una frase (senza riferimento al significato) e inseguito di analizzarne la struttura semantica. La separazione di forma e significatoe tipicamente una caratteristica del progetto di notazioni piu formali, come ad es-empio calcoli logici e linguaggi di programmazione. In tali linguaggi, il significatodi una dichiarazione puo essere determinato esclusivamente dalla sua forma. Inaltre parole, la semantica di un linguaggio puo essere cosı definita sulle strutturevalide del linguaggio, senza considerare fattori contestuali o extra-linguistici. Inquesto caso, non si eın quella ”felice” posizione per quanto riguarda i linguagginaturali, dove sono l’ambiguita e la soggettivita a fare le poesie, le parole crociate,e le incomprensioni internazionali possibili.

2.2.2 Contesto e pragmatica

La pragmatica, solitamente, e definita come l’insieme delle regole, che governanol’uso del linguaggio. Dunque se si dice: ”Tu mi devi cinque euro” questo potrebbe

5Avram Noam Chomsky e nato a Philadelphia, il 7 dicembre 1928 ed e un: linguista, filosofoe teorico della comunicazione statunitense.

12

essere piu di una richiesta di pagamento, che un’affermazione di fatto, indipen-dentemente da come viene formulata. Da qui il primato spesso viene accordatoad intenzionare il significato nell’analisi moderna. Per esempio, se digito le parole”elaborazione del linguaggio naturale” nella form di un motore di ricerca, che cosasi desidera cercare? Una definizione? Dei riferimenti a delle letterature sul NLP?Chi sono gli esperti di NLP? Corsi sul NLP? Un motore di ricerca ”intelligente”potrebbe essere in grado di capire questo, osservando le mie domande precedenti.Ciascuna delle precedenti query, potrebbero far restituire al motore di ricerca iseguenti risultati: ”che cosa e il linguaggio naturale”, ”libri di testo su AI” e”Linguistic Computing Laboratory Universita La Sapienza”.

I termini uso e contesto sono inestricabilmente intrecciati. Alcuni contesti in-fluenzano radicalmente l’intenzione, dietro un enunciato. E possibile, quindi, dis-tinguere due approcci generali per NLP, che affrontano questi problemi in modidiversi.

Ci sono stati tentativi di costruire grandi teorie dell’uso del linguaggio, ma senzabuoni risultati, arrivando cosı a sostenere, che per un dato dominio vi e un pat-tern ben specifico, e che e impossibile averne uno in generale. Infatti, riprendendodiversi documenti, come articoli di giornale, rapporti giudiziari, registri pubblici,pubblicita, etc.; essi sono tenuti ad avere pattern diversi in base all’uso del lin-guaggio.

2.2.3 Due punti di vista

Il primo punto di vista e radicato sul tipo di analisi linguistica, il quale e statoaccennato precedentemente. A volte viene caratterizzato come ”simbolico”, perchee costituito in gran parte da regole per la manipolazione di simboli, ovvero daregole grammaticali, che controllano se una frase e ben formata oppure no. Datala forte dipendenza di intelligenza artificiale tradizionale sul calcolo simbolico estato caratterizzato informalmente come Good Old-Fashioned Artificial Intelligence(GOFAI)6[14].

Il secondo punto di vista, che ha guadagnato un’ampia importanza negli anni’90, affonda le sue radici nell’analisi statistica del linguaggio. A volte vengonocaratterizzate come empiriche, perche si tratta di dati linguistici, derivanti darelativi ampi corpora di testi, come i feed news e le pagine web.

6Nel campo della ricerca in intelligenza artificiale, il Good Old-Fashioned Artificial Intelli-gence (GOFAI)[14] descrive il piu antico approccio originale al raggiungimento dell’intelligenzaartificiale, il quale e basato sulla logica e sul problem solving.

13

Il modo di guardare a questa distinzione e puramente metodologica. Il SymbolicNLP tende a lavorare in modo top-down, imponendo pattern grammaticali bennoti. Mentre, l’Empiric NLP tende a lavorare in modo bottom-up, partendo daitesti stessi, cercando dei pattern ed associazioni da modellare, alcuni dei qualipotrebbero non corrispondere a rapporti puramente sintattici o semantici.

Un’altro modo di pensare a questa distinzione e quello di vedere come i due punti divista gestiscono la complessita del NLP, in particolare il problema dell’incertezza,semplificato da fenomeni quali l’ambiguita.

E chiaro che un approccio puramente simbolico deve risolvere l’incertezza, propo-nendo regole aggiuntive, o fattori contestuali, che devono poi essere formalizzatiin qualche modo. Si tratta di una metodologia basata sulla conoscenza, in quantosi basa sul fattore umano per identificare e descrivere le regolarita nel dominio.Mentre, l’approccio empirico e piu quantitativo, in quanto tendera ad associareprobabilita attraverso le analisi alternate di dati e di decidere tra loro con deimetodi statistici.

2.2.4 Task e super-task

Una prima applicazione per il Natural Language Processing (NLP) e il recuperodi documenti tramite i motori di ricerca; il loro ritrovamento viene fatto in base aquanto essi sono rilevanti in base alla query dell’utente. Ovviamente, il recuperodei documenti lo si puo eseguire senza un uso significativo del NLP, infatti alcunimotori di ricerca lo facevano, ma il trend negli anni ’90 e stato verso la crescentesofisticazione nell’indicizzazione, nell’identificazione e nella presentazione dei testipertinenti.

Correlato, ma non identico, e il task document routing, in cui gli elementi di undocument feed sono automaticamente inoltrati ad un utente. Il document routinge a sua volta legato al task document classification. In questo task, si pensa comeassegnare i documenti in classi, di solito in base al loro contenuto. Nel caso piugenerale, un documento potrebbe essere assegnato a piu di una classe e le classipossono essere parte di una struttura piu grande.

E possibile distinguere questa attivita dal task document indexing, dove un pro-gramma assegna automaticamente le parole chiave o le frasi selezionate a un doc-umento.

A volte il focus non e sul trovare il documento giusto, ma sul trovare gli obiettiviinformativi specifici in un documento o in un insieme di documenti. Ad esempio,dato un insieme di articoli finanziari, si potrebbe desiderare di distillare, da ogni

14

articolo, chi ha comprato un certo quantitativo di BTP7. Normalmente questo el’estrazione di informazioni e fornisce un modo per generare dei valori, che al-trimenti rimarrebbero sepolti all’interno di una raccolta di documenti. Almenoalcune forme di documenti di riepilogo possono essere considerati come un tipospeciale di estrazione di informazioni, in cui un programma tenta di estrarre leinformazioni salienti da uno o piu documenti e presentarle come surrogato in undocumento.

Questi compiti, combinati insieme in un certo modo, possono formare un ”super-task”; ad esempio, un programma potrebbe selezionare i documenti da un feed inbase al loro contenuto, ordinarli in categorie e quindi estrarre alcuni pezzi prove-nienti da ciascun documento di interesse.

2.2.5 Strumenti a disposizione

L’analisi linguistica del testo procede tipicamente in modo stratificato. I documentisono suddivisi in paragrafi, i paragrafi in frasi e le frasi in singole parole. Le parolein una frase vengono analizzate (sottoposte ad analisi grammaticale) per poi esserecontrassegnate con un’etichetta. Di solito, i parser si basano sui: delimitatori difrase, tokenizer, stemmer e Part-of-Speech Tagger (POS Tagger). Non tutte leapplicazioni richiedono una suite completa di tali strumenti. Per esempio, tutti imotori di ricerca svolgono la suddivisione in token dei documenti, ma non tuttieseguono il part of speech (in italiano le parti del discorso).

Alcuni di questi strumenti, che si andra a vedere nelle sezioni successive, sono: idelimitatori di frase, i tokenizer, gli stemmer, i Part-of-Speech Tagger, i sintagminominali, i riconoscitori di nomi, i parser e le grammatiche.

Delimitatori di frase e tokenizer

Rilevare i bordi di una frase con precisione non e un task semplice, in quanto isegni di punteggiatura, che segnano la fine di una frase, sono spesso ambigui. Peresempio, il periodo puo denotare: un punto decimale, un’abbreviazione, la finedi una frase o un’abbreviazione alla fine di una frase. Allo stesso modo, le frasiiniziano con una lettera maiuscola, ma non tutte le parole in maiuscolo inizianouna frase, anche se seguono un periodo.

7Il Buono del Tesoro Poliennale (BTP) rappresenta un certificato di debito emesso dallo Statoitaliano, con scadenza superiore all’anno solare.

15

A volte, i rivelatori di frase hanno bisogno di un’aiuto da parte dei tokenizer perdisambiguare i caratteri di punteggiatura. I tokenizer (noti anche come gli anal-izzatori lessicali o ”segmentatori” di parole) segmentano un flusso di caratteri inunita significative, detti token. A prima vista, un tokenizzazione appare piuttostosemplice, in quanto un token puo essere preso come una sequenza di caratteriseparati da spazi bianchi8. Ad esempio, questa fase puo essere fatta tramite unAutomatic Sentence Chunking, il quale analizza un corpus di frasi, costituite da:punti, punti esclamativi e punti interrogativi, e estraendo una frase per volta,facendo attenzione, in questo modo, a non ”nascondere” le entita proprie. Questoapproccio cosı semplice puo essere adatto per alcune applicazioni, ma puo portarea delle imprecisioni.

Gli strumenti per la tokenizzazione di solito si basano su:

i. regole,

ii. automi a stati finiti,

iii. modelli stocastici

iv. e modelli lessici per identificare le abbreviazioni o le parole multi-token.

Stemming e Part-Of-Speech Tagger

Nel suo complesso, l’analisi di un testo[4, 5] non puo procedere senza quella lessi-cale, e quindi e necessario in primo luogo identificare le forme radicali delle occor-renze di una parola e di determinare la parte del discorso. Nel gergo linguistico, glistemmer sono analizzatori morfologici, che associano varianti dello stesso terminecon una forma radicale. La radice puo essere pensata come la forma, che dovrebbenormalmente essere trovata come una voce in un dizionario.

Ci sono due tipi di analizzatori morfologici: Morfologia flessiva e Morfologiaderivazionale.

• Morfologia flessiva esprime relazioni sintattiche tra le parole di una stessaparte del discorso, mentre la morfologia derivazionale esprime relazioni lessi-cali tra le parole che possono essere diverse parti del discorso.

• Morfologia derivazionale esprime la creazione di nuove parole da quelle vec-chie e tenta di mettere in relazione parole diverse attraverso la radice incomune.

8Il formato CoNLL rimuove gli spazi vuoti, consentendo di utilizzare un semplice tokenizerbasato sugli spazi. L’interruzione, fatta in questo modo, della frase sugli spazi e sulla pun-teggiatura potrebbe funzionare bene.

16

Gli analizzatori morfologici fanno largo uso sia di regole e sia di dizionari. Illessico tipicamente riguarda tutte le forme di una parola alla sua forma radice.Queste regole e lessici possono essere efficacemente codificati utilizzando macchinea stati finiti e supportano la segmentazione della parola, ma limitandosi soltantoai termini composti.

Il Part-Of-Speech Tagger si appoggia fondamentalmente su tokenizer e su delim-itatori di frase, effettuando l’operazione di associazione della parte del discorso aciascuna parola in una frase, dove i token vengono etichettati con etichette sin-tattiche, ovvero esso decide se una data parola e un: sostantivo, verbo, aggettivo,etc.

Nell’esempio che segue ci sono due frasi, in inglese, con dei tag associati, in cui epresente un’ambiguita.

’Visiting/ADJ aunts/N-Pl can/AUX be/V-inf-be a/DET-Indef nui-sance/ N-Sg.’

’Visiting/V-Prog aunts/N-Pl can/AUX be/V-inf-be a/DET-Indef nui-sance/ N-Sg.’

Nella prima frase, il termine ’visiting’ e un aggettivo che modifica il soggetto’aunts’, mentre nella seconda frase, ’visiting’ e un gerundio che prende ’aunts’come un oggetto.

Tuttavia, come illustra l’esempio sopra, a ciascun parola puo essere assegnato piudi un POS tag e per questo il ruolo del Part-Of-Speech Tagger e di scegliere quellocorretto.

Ci sono due approcci principali per implementare un Part-Of-Speech Tagger : basatosu regole e stocastico.

Nel primo caso, si prova ad applicare delle conoscenze linguistiche per escluderetutte le sequenze di tag, che sono sintatticamente non corrette; infatti questo puoessere fatto attraverso delle regole contestuali, oppure su informazioni morfologicheper aiutare il processo di disambiguazione.

Nel secondo caso, ci si basa sui data training e si comprendono gli approcci, chesi basano su informazioni di frequenza o di probabilita nel disambiguare le asseg-nazioni dei tag. I tagger stocastici piu semplici disambiguano le parole, basandosiesclusivamente sulla probabilita, che una certa parola si verifica con un particolaretag. Questa probabilita viene calcolata da un training set, in cui le parole ed i tagsono stati gia abbinati manualmente da un linguista esperto.

Nota: i tagger piu complessi possono usare modelli stocastici molto

17

piu avanzati, come gli Hidden Markov Models (HMM) (vedere Appen-dice A), oppure il Maximum Entropy (ME).

Sintagmi nominali e riconoscitori di entita proprie

Spesso c’e bisogno di andare oltre ad un semplice Part-Of-Speech Tagger, ad esem-pio, si supponga che si voglia costruire un sistema che estrae notizie di bussiness daun determinato documento, oppure la necessita di indentificare le persone, i nomidi aziende e loro relazioni. Sapere che una data parola e un nome proprio, potrebbeessere utile (e.g. ”Beppe”), pero utilizzando sotanto il Part-Of-Speech Tagger nonaiuta a riconoscere i nomi propri e i cognomi (e.g. ”Beppe Grillo”).

Per questo compito, i sintagmi nominali9[26] possono essere di grande aiuto, inquanto essi in genere svolgono un processo di parser piu superficiale rispetto, in-vece, ad altri parser che svolgono un processo piu di profondita, che sono staticitati precedentemente. Questi parser (parziali) hanno come obiettivo quello diindividuare i principali elementi costitutivi, come i sintagmi nominali o ”gruppinominali”10.

Gli estrattori di sintagmi nominali possono essere di due tipi: simbolici11 o statis-tici.

I Named Entity Recognizers o NER (vedere Sezione 3.1 ) (in italiano Riconoscitoridi Entita Proprie, identificano i nomi propri in uno o piu documenti e possonoanche classificare questi nomi propri sul fatto, che designano: le persone, i luoghi,le aziende, le organizzazioni e simili. Diversamente dagli estrattori di sintagminominali, essi scelgono di trascurare le parti del discorso e di lavorare direttamentecon i token e le loro proprieta, come ad esempio la Capitalizzazione Convenzionale.Come per i Part-of-Speech Tagger, essi possono contare sia su regole scritte a manoe sia sulla costruzione di modelli stocastici (HMM). Tuttavia, la maggior parte deiNER, attualmente disponibili (tipo quelli commerciali) sono rule-based.

Parser e grammatiche

Il parsing viene eseguito rispetto ad una grammatica, in pratica da un insieme di re-gole, che dicono quali combinazioni delle parti del discorso generano correttamenteuna frase ed una struttura sintattica. L’analisi semantica richiede l’identificazione

9Il sintagma nominale[26] e un tipo di sintagma il cui elemento principale e un nome.10I gruppi nominali sono sintagmi nominali parziali.11Di solito, in questo caso, si definiscono le regole per cio che costituiscono una frase, utilizzando

un’euristica relativamente semplice.

18

di diversi tipi di parole o di frasi, ovvero il riconoscimento di una parola o di unafrase come un nome proprio ed anche l’identificazione del ruolo che essi hanno nellafrase, cioe se soggetto o oggetto.

Ciascuna semantica differisce l’una dall’altra in base alle feature, che esse hanno,cioe, una parola oppure un sintagma nominale puo riferirsi a qualcosa di animatoo inanimato, ad una societa, ad un’organizzazione, ad un luogo geografico, ad unadata oppure ad una somma di denaro.

Identificare sintagmi nominali e un compito importante e non banale. Per questo,l’ingegneria linguistica e molto impegnata nello scrivere regole grammaticali ef-ficaci. Nonostante siano state scritte vaste grammatiche di uso generale per lalingua inglese, nessuna di queste e riuscita ad ottenere una copertura del 100% ditutti i costrutti, che si possono incontrare nei testi casuali, come ad esempio gliarticoli di notizie.

Ci sono pero delle risorse basate su corpus, dove i ricercatori e gli sviluppatoripossono attingere. Ad esempio, il progetto Penn Treebank, presso l’Universitadella Pennsylvania, ha come obiettivo quello di annotare i documenti, da insiemidi testi esistenti, in base alla loro struttura linguistica.

In pratica, questo progetto inserisce i POS tag nei documenti e produce un ”parserscheletrico”, che attesta la struttura sintattica grezza di una frase, per poi generareuna ”banca” di alberi linguistici.

La struttura sintattica, spesso, viene annotata utilizzando le parentesi per produrredegli elenchi incorporati.

Un esempio possibile e questo che segue:

(SS: (SN: (D: Il) (S: cane)) (SV: (V: mangia) (SN: (D: l’) (S: osso)))

Figure 2.1: Struttura della frase rappresentata come un albero.

19

2.3 TermExtractor: un estrattore terminologico

L’estrattore terminologico TermExtractor [21] e una web application, altamenteperformante, sviluppata da ricercatori del Dipartimento di Informatica, per es-trarre automaticamente dai documenti disponibili di un dato dominio, della ter-minologia condivisa da una web community.

L’applicazione ha un’architettura a pipeline, composta da 6 fasi principali, comemostrato in Figure 2.2, che sono:

1. Impostare le opzioni del sistema: in questa fase l’utente puo impostare di-verse opzioni o accettare l’impostazione predefinita;

2. Caricamento dei documenti: gli utenti possono caricare i documenti in piuformati, uno per uno oppure un archivio compresso;

3. Conversione dei documenti: i documenti vengono convertiti in formato testo,le euristiche vengono usate nel correggere gli errori di conversione (special-mente dai documenti originati da file in formato PDF);

4. Estrazion dei termini: in questa fase la terminologia viene estratta e filtrata;

5. Validazione della terminologia: in questa fase un partner oppure un team dipartner validano la terminologia;

6. Salvataggio/Scaricamento della terminologia: in questa fase la terminologiaviene salvata oppure scaricata in formato testo, XML o Excel.

Figure 2.2: Struttura della frase rappresentata come un albero.

20

2.4 Caratteristiche della lingua araba

In questa sezione si discute brevemente sui preliminari essenziali, che copronouna panoramica generale della lingua araba[3] e si enfatizzano gli aspetti, checoncernano la visibilita di questo lavoro legato alla parte sull’Arabic NER, ovveroil riconoscimento delle entita proprie per la lingua araba. Di seguito si introduconoconcetti sulla lingua araba, come la storia, l’ortografia, la morfologia, la struttura,etc.

2.4.1 Storia e prospettive correnti

Il termine lingua Semitica, secondo (Lipinski 2001), e stato introdotto nel 1781dallo storico tedesco AL Schloezer, per mezzo dei figli di Sem (Shem), con unalunga storia di oltre di 4500 anni. Questa famiglia e parte della famiglia afro-asiatica e la sua prima forma scritta e stata introdotta nel terzo millennio a.C.. Lelingue semitiche sono state le prime ad ottenere una forma scritta, con la scritturaAkkadian iniziata nella meta del terzo millennio a.C.. Attualmente, la linguaSemitica piu parlata e l’arabo, seguita dall’aramaico e dall’ebraico.

Versteegh (2001) ha proposto un certo numero di identificazioni di caratteris-tiche per le lingue di famiglia Semitica. Secondo lo studio, una lingua Semiticadovrebbe avere un sistema di root-pattern morfologico, la presenza di consonantienfatiche/gutturali, un sistema di verbi con prefisso e suffisso di coniugazione, cosıcome un gran numero di corrispondeze lessicali. Se una lingua e classificata comeSemitica, essa deve esibire la presenza di tutte queste caratteristiche.

Oggi, l’arabo e la lingua madre di oltre 317 milioni di persone nei paesi arabi.Secondo le stime delle Nazioni Unite (UN), nel 2015, ci saranno nei paesi arabi,quasi 395 milioni di abitanti (fonte UN Development Programme 2009 ). Inoltre,l’arabo e la lingua liturgica religiosa di oltre 1.5 miliardi di musulmani in tutto ilmondo, si tratta di una delle lingue ufficiali delle Nazioni Unite ed e classificatasesta in termini di importanza.

Il lavoro fatto da Weber (1997), sulle prime dieci lingue influenti, la lingua arabasi e classificata quinta. Questa classifica, si basa sulle seguenti misure di punteg-gio:

1. Il potere economico dei paesi che utilizzano la lingua.

2. Il numero delle principali aree di attivita umana in cui la lingua e importante.

3. Il numero e la popolazione dei paesi che utilizzano la lingua.

21

4. Prestigio socio-letterario della lingua.

Anche se lo studio e vecchio, in quanto copre il periodo 1980-1990, Weber ritieneche la sua scoperta non ha bisogno di essere aggiornata, per come la popolazionemondiale e cresciuta relativamente. Secondo la internet monitoring agency12, iltasso di crescita degli utenti del W3 e stato del 445% tra il 2000 e il 2010. Il MedioOriente ha segnato la secona rete con il piu alto tasso di crescita degli utenti nellostesso periodo, circa il 1825%. Assumendo che la maggior parte di questi utentisono di lingua araba, il contenuto web in lingua araba subira un forte incrementonel futuro, per questo si richiede un serio sforzo, per affrontare la necessita di averestrumenti NLP e risorse per l’arabo.

2.4.2 Ortografia

Simile alla propria famiglia Semitica (aramaico e ebraico), l’arabo[3] si scrive dadestra verso sinistra. Essa dispone di 28 lettere, nelle forme di base, tra cui trevocali lunghe. Le forme non basiche sono lettere generate da una combinazione didue lettere. Inoltre, include, come segni diacritici, cinque principali vocali brevi(non inclusi in alfabeto) e un totale di 13 combinazioni di vocali brevi. Le vocalilunghe e le vocali brevi sono correlati in un senso, che una vocale lunga e una doppiavocale corta. Questi segni diacritici sono utilizzati principalmente per la pronunciaesatta di consonanti, che a sua volta aiutano a chiarire l’esatta interpretazione. Essisono posti sopra o sotto le lettere. Tale processo e descritto come vocalizzazionee il testo potrebbe essere: pienamente, parzialmente o mai vocalizzato a secondodella forma scritta (Buckwalter 2004).

Le lettere della lingua araba hanno una caratteristica corsiva, questo significa cheuna lettera puo assumere una forma diversa in base alla sua posizione in unaparola, che sono la posizione: iniziale, mediana, finale, o isolata. Solo tre letterenon sono interessate da questa funzione. Inoltre, sei lettere dell’alfabeto hannosolo due forme possibili, perche solo lettere precedenti possono collegarsi a loro equeste sei lettere non possono essere collegate alle lettere che seguono (Abdelali2004).

Una delle caratteristiche principali del testo in arabo e l’assenza di Capitalizazione,il che significa, che non presenta differenze ortografiche in termini di casi d’uso.Un’altra caratteristica e che c’e poca punteggiatura, anche se recentemente, questae stata introdotta.

La Kashida [ � � �] e un carattere speciale per allungare una lettera. Per esempio

12www.internetworldstats.com.

22

allungando la lettera [h, H, h] nella parola [YÒm×, mHmd, Mohammad] produce lanuova forma [ ]. E utilizzato sia per rispettare i vincoli di calligrafia o per lagiustificazione del testo (Elyaakoubi e Lazrek 2005).

2.4.3 Morfologia

L’arabo[3] ha un sistema morfologico complesso, che lo rende altamente flessivo,con la presenza di prefissazioni, suffissazioni, processi flessionali e derivazionali.Sebbene ha un sistema complesso, esso e fortemente strutturato (Kiraz 2002).In aggiunta all’apposizione13[26], ha la caratteristica di attaccamento clitico alleradici. L’arabo ha anche un sistema morfologico ricco, in cui le parole sono es-plicitamente contrassegnate per causa, genere, numero, determinatezza, modo,persona, diatesi, tempo ed altre caratteristiche morfologiche (Maamouri et al.2006).

Esistono due classi di parole generiche: aperta (sostantivo14 e verbo) e chiusa.

La classe dei sostantivi in arabo e ulteriormente suddivisa in derivati basati sull’originedella parola, come segue:

• Sostantivi derivati da verbi.

• Sostantivi derivati da altri sostantivi.

• Sostantivi derivati da particelle15.

• Primitive16 (cioe sostantivi che non derivano da altre categorie).

Le caratteristiche morfologiche di un sostantivo in arabo ed i loro possibili valorisono i seguenti:

• Numero: singolare, duale, plurale, collettivo.

• Sesso: maschile, femminile, neutro.

13L’apposizione[26] (dal latino appositio, ”aggiunta”) e una nozione della grammaticatradizionale che indica un’unita sintattica (composta di una sola parola o da un sintagma nomi-nale o preposizionale) riferita ad un nome con cui stia in relazione di coreferenza.

14I sostantivi in arabo sono un nome o un’unita lessicale (la quale descrive una persona, unacosa o un’idea).

15Per particelle si intendono: le preposizioni, gli avverbi, le congiunzioni, le particelle inter-rogative, l’eccezioni, le interiezioni, le negazioni e le subordinazioni; queste, poi, possono essereracchiuse in una classe, detta classe delle particelle, la quale comprende tutte quelle parole, cheappartengono alla classe delle parole generiche chiuse.

16Tale categoria, inoltre, comprende quello che sarebbe stato classificato come participi,pronomi, pronomi relativi, pronomi dimostrativi, pronomi interrogativi e numeri.

23

• Determinatezza: definito, indefinito.

• Causa: nominativo, accusativo, genitivo.

L’inventario dei verbi, per la lingua araba, e scarso rispetto ad esempio all’inventariodei verbi di lingua inglese. La carenza di verbi e causata dalla mancanza di unaprecisa significazione o di flusso del tempo come nell’inglese. Le caratteristichemorfologiche per un verbo in arabo ed i possibili valori sono i seguenti:

• Aspetto: perfettivo (passato), imperfettivo (presente), imperativo (futuro).

• Diatesi: attivo, passivo.

• Tempo: passato, presente, futuro.

• Modo17[26]: indicativo, congiuntivo, imperativo.

2.4.4 Generazione delle parole dalla forma base

La derivazione morfologica dell’arabo[3] e basata sul principio delle radici e deipattern per generare la classe aperta. Una radice (detta radicale) e una sequenzadi consonanti, comunemente da tre letterali (Beesley 2001).

Vi e un insieme finito di radici e si dice, che i sostantivi ed i verbi sono derivati daun insieme chiuso di circa 10.000 radici (Al-Fedaghi e Al-Anzi 1989), ed il numerodi parole possibili sono stimate essere circa 6× 1010 (Attia 2000).

Un pattern e un insieme di trasformazioni, che vengono applicate ad una radice diconsonanti inserendo vocali tra esse. Le vocali possono essere vocali lunghe, macomunemente sono le vocali brevi (segni diacritici) (Beesley 2001). Ad esempio,dato una radice con tre letterali CCC (C rappresenta la consonante) un patternfrequente e CvCvCv (v rappresenta la vocale), le consonanti sono fisse mentre levocali possono cambiare. Per ogni combinazione di v, un nuovo pattern e prodottodal pattern principale e quindi un nuovo tema18[26] e derivato da questo modello.Dunque, da una singola radice si possono generare centinaia parole nella forma disostantivi o di verbi (Ahmed, 2005).

17Il modo[26] e una delle tre principali categorie grammaticali che compongono il sistema diconiugazione verbale.

18Il tema[26] e la parte della parola, che resta togliendo la desinenza e che permette l’immediatainserzione degli elementi di flessione (talvolta coincide con la radice): tema nominale, verbale,quello che resta togliendo ad una parola, rispettivamente, la desinenza nominale o la desinenzaverbale.

24

Data la radice araba [I.�J», ktb, nozione di scrittura] (una radice a tre letterali),

si potrebbe generare, ad esempio, la forma passata sostituendo le v con le vocalimelodiche (a-a), ”katab”. Questa caratteristica della morfologia araba e descrittacome morfologia non concatenativa o non lineare. Tre esempi di generazione ditemi sono riportati in Table 2.1.

Table 2.1: Esempi di generazione di forme basi.

Radice/CCC Traslitterazione Melodia/a-a Traslazione Melodia/u-i Traslazione

I.�J» ktb katab ha scritto kutib scrivere

�PX drs daras appreso duris imparare

©Ôg.

jmE jamaE raccolto jumiE raccogliere

Le radici arabe vengono classificate in base al numero delle loro consonanti in:due letterali, tre letterali, quattro letterali e cinque letterali. Da uno studio fattoda Elkateb et al. (2006), si afferma che 85% delle parole arabe sono derivate daradici a tre letterali. Ci sono 15 pattern a tre letterali, di cui almeno nove sonodi uso comune e quattro pattern a quattro letterali sono molto piu rari. Tuttiquesti pattern subiscono alcuni cambiamenti di tema rispetto alle vocali (Violettaet al., 2000). Le vocali sono normalmente aggiunte alla radice del modello per treletterali CvCvCv e per quattro letterali CvCCvC.

I temi generati dalla stessa radice, sono semanticamente correlati e, d’altra parte,ne deriva che seguono lo stesso modello per presentare lo stesso stile.

2.4.5 Struttura della parola araba

Di seguito vengono mostrate le varie forme di parole presenti nella lingua araba[3]:

• Proclitiche[26], parole, di solito monosillabi, che, non avendo accento au-tonomo, si appoggiano prosodicamente alla parola seguente, detta ospite,formando con essa un’unita accentuale, a volte anche a livello di frase. Iverbi possono avere solo una proclitica, mentre i sostantivi possono avernepiu di due. Le possibili proclitiche vengono listate in Table 2.2 con la lorofunzione.

25

Table 2.2: Proclitiche.

Morfema Traslitterazione Funzione

+ð w+ e

+�¯ f+ in ordine a

+�Ë l+ in ordine a

+�K. b+ per

+�Ë+ð w+l+ e +(in ordine a, per)

+�K.+ð w+b+ e +(in, a, per)

+�Ë+�¯ f+l in ordine a +(per)

+�K.+�¯ f+b in ordine a +(in ordine a, per)

• Prefissi,

• Tema,

• Suffissi,

• Enclitiche, morfemi che occorrono alla fine di una parola e rappresentanoi pronomi possessivi elencati in Table 2.3. La loro funzione e differente,secondo la classe della parola a cui essi attribuiscono.

Table 2.3: Enclitiche.

Morfema Traslitterazione Funzione (verbo) Funzione (sostantivo)

ø+ +y - mio

¼+ +k tu (singolare) tuo

AÒ»+ +kma tu (duale) tuo

Õ»+ +km tu (plurale maschile) tuo

á»+ +kn tu (plurale femminile) tuo

è+ +h egli suo

Aë+ +hA ella sua

AÒë+ +hma loro (duale) loro

Ñë+ +hm tu (plurale maschile) loro

áë+ +hn tu (plurale femminile) loro

26

2.4.6 L’ambiguita nella lingua araba

La perdita dei segni diacritici interni, come ad esempio le vocali brevi o la shadda,porta a diversi tipi di ambiguita nei testi in lingua araba[3], sia dal punto di vistastrutturale e sia dal punto di vista lessicale, perche diversi segni diacritici rappre-sentano differenti significati. Questi possono essere risolti solo dalle informazionicontestuali e di una adeguata conoscenza della lingua. A parte l’ambiguita a causadi segni diacritici mancanti, la lingua araba, come molte altre lingue, affronta ilproblema di ambiguita tra due o piu entita proprie.

2.4.7 I nomi propri nella lingua araba

La caratteristica piu significativa dei nomi propri arabi[3] e l’assenza di qualsiasicaratteristica ortografica speciale per distinguerle dalle altre categorie di parole.A differenza dell’inglese e di altre lingue con caratteri latini, l’arabo non ha infor-mazioni di questo tipo.

L’implicazione di questa caratteristica e altamente significativo a causa del fattoche i nomi piu adatti sono nelle forme di verbi, aggettivi o sostantivi comuni.Questo rende l’estrazione corretta del sostantivo in arabo strettamente vincolato,e fortemente influenzata da, passaggi pre-elaborati prima di eseguire il task diestrazione del sostantivo stessso. Questo task e piu sensibile a errori di livelli dianalisi precedenti alla corretta estrazione del sostantivo rispetto all’inglese.

In questa sezione si spiega come si formano in arabo i sostantivi per le tre tipologie(PERS, LOC e ORG).

2.4.8 Struttura

Nomi di persone

In termini di struttura del nome di persona, la piu piccola componente di un nomedi persona araba[3] potrebbe essere classificato come (1) un componente di base chepotrebbe essere un nome semplice o composto e (2) da affissi. Gli affissi vengonoutilizzati con lo scopo di generare un numero di istanze di nome.

Dunque, cio significa che il nome base della persona e preceduto opzionalmente da

27

uno o due suffissi, come [�Ë @, Al, il] (ad esempio ”AlMohammad”) o [ñK.

@, bw, padre

di] (ad esempio padre di Mohammad) e seguiti da opzionalmente da un suffisso,come l’aggettivo indicativo ”y”, che si attacca alla fine del nome. I cognomi inarabo, possono derivare secondo: la professione, il nome della tribu di nascita dellapersona, oppure il luogo di residenza o di nascita.

Nomi di luoghi o di organizzazioni

I nomi delle organizzazioni nella lingua araba[3] comunemente iniziano con un

prefisso seguito da uno o piu sintagmi nominali connesi con la congiunzione [ð,w, e] e seguito opzionalmente da un altro sintagma nominale connesso con una

congiunzione di coordinamento [ �Ë, l, per]. I sintagmi nominali potrebbero essereun singolo o un nome composto opzionalmente seguito da uno o piu aggettivi. Ilnome principale nel sintagma nominale potrebbe essere un nome comune o pro-prio (persona o luogo). Il prefisso dell’organizzazione potrebbe essere un articolo

determinativo [È@, Al, il] per produrre una forma definita.

A differenza dei nomi delle organizzazioni, i nomi dei luoghi sono relativamentesemplici, ma non quando essi sono detti dopo le persone. Iniziano con una po-sizione dei prefissi, ad esempio, la parola ”citta”, seguito da un nome proprio. Lamaggior parte dei prefissi sono in forma femminile. Tuttavia, diversamente delleorganizzazioni, i luoghi non vanno, dal punto di vista morfologico, d’accordo coni sostantivi che seguono.

Molti nomi propri in arabo vengono generati nello stesso modo di unaqualsiasi altra parola presente nella lingua araba utlizzando il sistema delpattern-root morfologico. Infatti, secondo un esperimento fatto Alkharashi(2009), ha concluso che i nomi di persona sono per lo piu generati da radiciarabe, allo stesso modo di qualsiasi altra categorie di parole. E stato scop-erto, che solo 16 pattern Arabi contribuiscono alla produzione di oltre il50% dei nomi di persona nella lingua araba. La radice Hind da sola haprodotto 146 nomi. I nomi propri non possono avere le proclitiche, allafine della parola, ad essi connessi e le enclitiche potevano essere attaccatesolo al token capo del nome proprio. Inoltre, alcune categorie grammaticali

28

non possono far parte del nome proprio, come: i verbi, i pronomi relativi opersonali. Secondo la sezione precedente, i nomi di persona hanno patterninterni quali connettori (o prefissi Kunia) e connettori di nome; mentre, inomi di luoghi e di organizzazione hanno la presenza di prefissi.

2.4.9 Sintassi

Dato che gli aggettivi seguono i sostantivi in arabo[3], l’individuazione dei contorniin un nome di organizzazione frase e problematico. La ragione e che i nomi diorganizzazione sono di solito sintagmi nominali e possono essere seguiti da aggettiviche non possono essere facilmente identificati come parte del nome o non, e quindi illimite che termina lo possono perdere. A volte gli aggettivi che seguono modificanoil prefisso e, a volte il sostantivo principale.

Anche se i ”designatori” di nomi vengono utilizzati all’inizio dei nomi di organiz-zazione e di luogo, che sono di grande aiuto nel riconoscerli, spesso accade chenon sempre risolvono il problema, in quanto questi trigger sono nomi comuni chepotrebbero essere utilizzati in qualsiasi altro contesto; dato che innesca titoli chesono normalmente sostantivi e che possono essere seguiti da una serie di aggettivi,i quali causerebbero la separazione ulteriore del trigger dal nome, con dipendenzemolto piu lunghe.

L’annessione viene usato in arabo per formare nomi composti per indicare la pos-sessivita e data l’ampia diffusione dei nomi in arabi nella forma di sostantivi, i nomicompleti potrebbero essere una serie di nomi semplici. La mancanza di un indica-tore possessivo in arabo come ”of” e ”’s” nella lingua inglese rende una qualsiasisequenza di sostantivi ambigui con un potenziale nome completo. Per esempio, ilseguente nome senza un connettore e nessun titolo e troppo ambiguo per rilevarlo,

infatti [Yê¯ QÔ«, Emr Fhd] potrebbe essere interpretato come ”l’eta di Fhd” oppure

come un nome di una persona ”Emr Fhd”.

29

2.4.10 Pecularieta e sfide nella corretta rilevazione e classificazione deinomi propri in arabo

Il rilevamento dei nomi propri in arabo[3], in generale, e molto piu difficile che ininglese a causa delle caratteristiche citate sopra. Tuttavia, le sfide non nasconosolo dalla natura delle entita proprie, ma in realta dai livelli di analisi fatti prima.La sfida piu interessante e l’ambiguita presente nelle entita proprie. Pero, i segnidiacritici in parte risolvono il problema, come alcuni segni ambigui sono esatti segnidiacritici, indipendentemente dal fatto che essi rappresentano un nome proprio oqualsiasi altra categoria.

Siccome, la lingua araba e una lingua altamente flessiva[31, 33, 3], cioe una parolaaraba puo essere visto come la seguente composizione:

Word = prefix(es) + lemma+ suffix(es)

Entrambi i prefissi e suffissi (vedere Sezione 2.4.5 ) sono autorizzati ad essere com-binazioni, e quindi una parola puo avere zero o piu affissi. Dal punto di vistastatistico, questa caratteristica flessiva della lingua araba rende i testi in arabo,rispetto ai testi scritti in altre lingue che sono mesno complesse morfologicamente,piu sparsi, e, quindi, la maggior parte dei task, per l’Arabic Natural LanguageProcessing, sono piu difficili e piu impegnativi.

Figure 2.3: Un banale esempio di una parola araba composta[31, 33].

Nella letteratura si trovano due possibili soluzioni[31, 33] per superare questo osta-colo, con lo scopo di ridurre la sparsita dei dati nei testi arabi. La prima soluzione eil Light stemming, che consiste nell’omettere tutti i prefissi e suffissi, che sono statiaggiunti al lemma per ottenere il significato necessario. Questa soluzione e con-veniente per task quali l’Information Retrieval e il Question&Answering (vedereSezione 7.1 ), perche le preposizioni, gli articoli e le congiunzioni sono consideraticome parole di arresto e non vengono presi in considerazione per decidere se un

30

documento e rilevante per una query oppure no, ma e meno conveniente per i taskNLP come il NER. La seconda soluzione e Word segmentation, che consiste nelseparare i diversi componenti di una parola da uno spazio; questa tecnica e ingrado di diminuire la scarsita di dati senza provocare perdita di informazioni con-testuali. Pertanto, questa soluzione e la piu adeguata ai task NLP, che richiedonodi mantenere ai diversi morfemi di parole come il Word Sense Disambiguation,NER, etc.

31

Chapter 3

Stato dell’arte

Il Named Entity Recognition (NER) e il problema della disambiguazione sonostati indirizzati in differenti campi di ricerca come: NLP, Web mining e SemanticWeb communities. Tutte queste si accordano sulla definizione di Named Entity,definizione coniata da Gaishman et al. come un’unita di informazione descrittadal nome proprio di: una persona, un’organizzazione, un luogo, un marchio, unprodotto, un’espressione numerica (includendo il tempo), la data, la moneta e lapercentuale numerica; tutte queste entita possono essere presenti in uno o piutesti.

L’identificazione di questi riferimenti legati a queste entita, nei testi non strut-turati, e stato riconosciuto come un importante sub-task dell’Information Extrac-tion (IE). Tale sub-task e essenziale ed e stato assegnato al ramo dell’elaborazionedel linguaggio naturale o Natural Language Processing (NLP).

Molti lavori si basano su euristiche e definizioni di pattern (modelli) per riconoscere,ad esempio, nomi propri di societa nei testi. I dati di addestramento e definito daun set di scelte euristiche. L’idea e quella di riconoscere e classificare attraversodelle regole distinte le feature associate, con esempi positivi e negativi.

Un differente approccio avviene con l’introduzione della tecnica Supervised Learn-ing (SL). Con gli approcci Semi-Supervised Learning (SSL) e Unsupervised Learn-ing (UL), si pensa di risolvere questo problema sfruttando un piccolo set inizialedi dati annotati da ”istruire” e da mostrare al sistema; oppure risolvendolo con ilclustering.

Lasciando i recenti metodi sull’uso di DBpedia, Freebase e YAGO, il SemanticWeb community ha introdotto la mappa delle entita proprie, per relazionare i fattimostrati da queste antologie di grana fine.

32

La disambiguita e una delle chiavi di sfida in questo scenario ed e fondata sulfatto che i termini presi in zone del testo ”isolate” sono naturalmente ambigui.Quindi, un testo contenente il termine London puo riferirsi alla citta London dellostato del Minesota, USA; tutto dipende dal contesto che sta attorno al termineLondon. Similmente: persone, organizzazioni e societa possono avere nomi e nick-name multipli. Questi metodi generalmente provano a trovare nell’intorno deltermine, qualche ”punto”, per contestualizzare la sua ambiguita ed a raffinarla, sepossibile.

3.1 Metodi di apprendimento per i sistemi NER

I primi studi fatti sui sistemi NER, si sono basati sulla gestione delle regole, orainvece si preferisce utilizzare i seguenti metodi di apprendimento per i sistemiNER[10], (vedere Appendice A) come:

• Apprendimento Supervisionato (Supervised Learning (SL)),

• Apprendimento Semi-supervisionato (SemiSupervised Learning (SSL)) e

• Apprendimento Non Supervisionato (Unsupervised Learning (UL)).

3.1.1 Apprendimento Supervisionato

L’idea del Apprendimento Supervisionato[10, 13] e quella di studiare le caratter-istiche delle entita proprie, con esempi positivi e negativi, su un insieme grandedi documenti (annotati manualmente) e di progettare le regole per catturare leistanze di un certo tipo, utilizzando tecniche che includono:

• Hidden Markov Models (HMM),

• Decision Trees,

• Maximun Entropy Models (ME),

• Support Vector Machine (SVM) e

• Conditional Random Fields (CRF).

Il metodo basato sull’Apprendimento Supervisionato consiste nell’etichettare leparole presenti in un corpus, dove essi vengono annotati come entita nelle fasi dipre-addestramento del corpus stesso; le perfomance del sistema dipendono oltre alcorpus, anche dalla ”robustezza” del vocabolario.

33

Le sfide con l’approccio basato sull’Apprendimento Supervisionato non sono moltoaffidabili, per via delle risorse a disposizione e del costo proibitivo per gli ”esempi”creati.

3.1.2 Apprendimento Semi-supervisionato

La tecnica principale, utilizzata nell’Apprendimento Semi-supervisionato[10], echiamata ”bootstrapping” e richiede un piccolo grado di supervisione, come uninsieme di semi, per iniziare con il processo di apprendimento; dopodiche si ap-plica il processo di estrazione e di riconoscimento per trovare dei nuovi oggetti (inquesto caso di entita proprie).

La prima tecnica basata sull’Apprendimento Semi-supervisionato e stata fatta,implementando le lexical features1, attraverso le espressioni regolari, per gener-are delle liste iniziali (seeds) ed attraverso delle regole fisse per il controllo lessi-cale.

Un secondo approccio utilizzato e una variante del ”mutual bootstrapping”; essousa le relazioni sintattiche, come soggetto-oggetto, per scoprire con piu accuratezzale evidenze contestuali attorno alle entita, sfruttando l’output generato da unsistema POS Tagger.

3.1.3 Apprendimento Non Supervisionato

Un tipico approccio basato sull’Apprendimento Non Supervisionato[10, 17] e ilclustering2, questo crea dei gruppi in base alla similarita contestuale, ovviamenteesistono altri metodi di Apprendimento Non Supervisionato.

Ad esempio, l’utilizzo di WordNet, come supporto nella ricerca all’interno dellalista delle parole, che co-occorrono piu frequentemente nel testo, oppure utilizzandodei pattern lessicali per il calcolo statistico su un grande corpus di elementi.

In molti sistemi NER, che utilizzano il metodo non supervisionato, applicano ilclustering. Questa tecnica, in passato, e stata usata da molti ricercatori (Miller

1Il significato in italiano sta per ”caratteristiche lessicali” di un linguaggio. Per conoscerea priori, quali sono le lexical features, utilizzate in un linguaggio, ci sono due sorgenti dove epossibile acquisire queste informazioni e sono: gli spunti semantici e sintattici.

2Il clustering o cluster analisys e un insieme di tecniche per l’analisi multivariata dei dati conil compito di selezionare e di raggruppare gli elementi omogenei in un data set. Tali teniche sibasano su misure relative alla somiglianza tra gli elementi, calcolandone la distanza reciproca (adesempio la distanza euclidea) e quindi se, un dato elemento appartiene o meno ad un insieme,dipende da quanto lo stesso elemento, preso in esame, e distante dall’insieme stesso.

34

et al., 2004; Lhang, 2005; Koo et al., 2008; Ratiov & Roth, 2009; Huang e Yates,2009).

35

3.2 Stato dell’arte e related work dei sistemi English NER

Lo stato dell’arte dei sistemi English NER[10] ha inizio negli anni ’90, dove e statointrodotto il concetto di NER, nel Message Understanding Conference (MUC).Tutte le conferenze sono state finanziate dal Defense Advanced Research ProjectAgency (DARPA), per incoraggiare lo sviluppo di metodi nuovi e migliori perl’Information Extraction, cercando di estrarre informazioni ben precise e ben strut-turate all’interno di testi non strutturati.

Per poter partecipare al MUC, ciascun team doveva progettare e realizzare unsistema in grado di svolgere il compito scelto e di essere in grado di avere, lapropria performance, valutata rispetto agli altri team concorrenti.

Questa iniziativa e stata estremamente fruttuosa per una serie di ragioni[10].

• L’enfasi di avere un sistema reale in esecuzione, evitando la normale tendenzadei ricercatori a concentrare i loro occhi su orrizzonti lontani.

• La fornitura di materiali uniformi, per i dati di addestramento e di valu-tazione, incoraggiano una valutazione rigorosa mediante un insieme di met-riche concordate.

• L’introduzione di un elemento competitivo, che coinvolge un feedback diretto,ha reso l’esercizio piu interessante, rispetto alla normale conferenza tecnica.

Tra i partecipanti al MUC ci sono state sia universita, come, ad esempio, le uni-versita di Edinburgh, di Kyoto e del Massachusetts (MIT), e sia privati.

Le prime due conferenze fatte nel 1987 e 1989, si sono occupate nell’analisi dimessaggi durante delle operazioni navali. Il MUC-3 (1993) ed il MUC-4 (1994) sisono concentrati sull’estrazione di eventi, in particolare ricercando, negli articoli digiornale, dettagli sugli attacchi terroristici. Per il MUC-3, il punteggio ottenuto dalmiglior sistema e stato circa il 50% per la Recall ed il 60% per la Precision.

Al MUC-5 (1993), sono state introdotte piu task orientati al business, come adesempio trovare annunci di joint venture.

Alla sesta conferenza (MUC-6), il task per il Named Entity Recognition fu suddivisoin tre sub-task: ENAMEX (nomi di persone, nomi di luoghi e nomi di organiz-zazioni), TIMEX (data e ora di espressione), e NUMEX (per importi monetari epercentuali). Il miglior sistema ha ottenuto un punteggio circa del 75% per la Re-call e circa del 75% per la Precision. Gran parte dei sistemi NER hanno utilizzatol’approccio rule-based fino alla meta degli anni ’90, e tutt’ora viene utilizzata. Madalla sesta conferenza in poi, gli sviluppatori hanno incominciato a progettare esviluppare sistemi basati sulle tecniche dell’apprendimento automatico.

36

Ad oggi, i sistemi NER sviluppati (in varie lingue) si sono evoluti attorno aquesti tre sub-task.

Nel 1998, il MUC-7 ha dimostrato, che l’estrazione di entita da articoli di giornali,per la lingua inglese, era piu o meno un problema risolto. I migliori sistemi,progettati per il MUC-7, hanno segnato dei valori di F1-Score pari al 93.39%,a fronte di una performance umana stimata di F1-Score circa del 97.60% e del96.95%. Attualmente lo stato dell’arte dei sistemi NER, per la lingua inglese, erimasto fermo al MUC-7.

In Table 3.1 si mostrano i migliori quattro sistemi, per ciascuna conferenza di valu-tazione NER, in base ai diversi parametri di valutazione, per ciascun evento.

Table 3.1: I migliori quattro sistemi sul task Entity Estraction al MUC.

Partecipante Sistema Approccio MUC Rank F1-Score Riferimenti

SRA NameTag Regole 6 1 96.42 Krupka 1995,

7 2 91.60 Krupka et Hausm.

1998

SRI FASTUS Regole 6 2 94.00 Appelt et al. 1995

BBN Identifier Stocastico 6 1 93.65 Bikel et al. 1997,

7 2 90.44 Bikel et al. 1999

U.Edinburg LTG Ibrido 7 1 93.39 Mikheev et al.

1998

Le restanti lingue

Una buona parte del lavoro di ricerca NER e dedicato allo studio della lingua in-glese, ma una percentuale, forse maggiore, riguarda l’indipendenza del linguaggioe i problemi del multi-language. Questo lavoro e stato avviato dalle conferenzeMUC, le quali hanno dato una spinta per la progettazione e realizzazione di NERin altre lingue. Infatti, nel 1996, e stata avviata una conferenza correlata al MUC,denominata Multilingual Entity Task (MET-1) per valutare l’estrazione di infor-mazioni su testi in lingue diverse dall’inglese, soffermandosi solo sullo spagnolo,cinese e giapponese; mentre, l’anno successivo, il MET-2 si e soffermato solamentesull’estrazioni di entita per il cinese ed il giapponese.

Le conferenze sul NER sono iniziate con il MUC, per poi essere continuate con ishared task nel Conference on Natural Language Learning (CoNNL), sofferman-dosi oltre alla lingua inglese, anche nelle restanti lingue. Infatti, nel CONLL-2003

37

viene studiato il tedesco. Allo stesso modo, lo spagnolo e l’olandese sono forte-mente rappresentati, entrambi potenziati da un importante convegno dedicato: ilCONLL-2002. Il cinese viene studiato rilasciando un’abbondante letteratura (adesempio, L. J. Wang et al. Del 1992, H.-H. Chen & Lee 1996, S. Yu et al. 1998);stesso discorso vale per il francese (G. Petasis et al. 2001 Poibeau 2003), per ilgreco (S. Boutsis et al. 2000) e per l’italiano (W. Black et al. del 1998, A. Cuc-chiarelli & Velardi 2001); infine, l’arabo (F. Huang 2005) ha iniziato a riceveremolta attenzione a progetti su larga scala come il Global Autonomous LanguageExploitation (GALE)3.

3http://projects.ldc.upenn.edu/gale/.

38

3.3 Stato dell’arte e related work dei sistemi Italian NER

I sistemi per il trattamento automatico della lingua italiana, vengono affrontatiin EVALITA. EVALITA e un’iniziativa dedicata alla valutazione del Natural Lan-guage Processing e degli strumenti vocali per la lingua italiana.

L’obiettivo generale di EVALITA4 e quello di promuovere lo sviluppo di tecnologielinguistiche per la lingua italiana, di definire ed estendere l’attuale stato dell’artenel ”parsing” della lingua italiana, favorendo l’applicazione di modelli esistenti efornendo un quadro di riferimento condiviso, in cui i sistemi e i diversi approccipossono essere valutati in modo coerente. Infatti, i dati di sviluppo sono in variformati e il compito e composto di attivita secondarie, con una valutazione quan-titativa di diversi tipi di uscite, annotando anche funzioni diverse.

Nella prima edizione[8], del 2007, l’attenzione si e concentrata principalmente sulleapplicazioni per la lingua italiana, con vari approcci di analisi, ad esempio basato suregole e stocastico, e paradigmi, ad esempio constituency-based e dependency-based.L’obiettivo, infatti, era di contribuire, con riferimento all’italiano, per l’indaginesulle cause della irriproducibilita dei risultati di analisi noti in letteratura su linguediverse dall’Inglese, come per il ceco, il tedesco, il cinese, l’italiano, e su altri Tree-Banks Penn. Gli stessi dati di sviluppo, estratti dal Turin University Treebank5,ci sono stati per la distribuzione, sia con il TUT nativo (dependency-based) e siasul TUT Penn (constituency-based), ed il compito e stato articolato in due binariparalleli, rispettivamente sul constituency-based e sul dependency-based.

La valutazione, in EVALITA 2007, si e basata sull’Italian Content AnnotationBank (I-CAB). L’I-CAB e un corpus composto da 525 notizie tratte dal quo-tidiano locale ”L’Adige”, per un totale di circa 180.000 parole. E annotato coninformazioni semantiche a diversi livelli:

• espressioni temporali,

• entita (persone, organizzazioni, luoghi, e entita geo-politiche)

• e le relazioni tra le entita (ad esempio, la relazione di affiliazione collegamentodi una persona di una organizzazione).

L’annotazione di I-CAB e realizzato in collaborazione con CELCT. Finora si sono

4Ad esempio, esiste un task, denominato News People Search Task [24] (o NePS Task), chesi propone di valutare attraverso i documenti la risoluzione di coreferenza di entita propriedi persone indicate nella cronaca italiana. In esso vengono coinvolti due aspetti problematici:l’ambiguita (persone diverse che hanno lo stesso nome) e le variazioni di nome (nomi diversipossono riferirsi alla stessa persona).

5http://www.di.unito.it/∼tutreeb.

39

completati i primi due livelli di annotazione, cioe le espressioni e le entita tem-porali. L’I-CAB sta diventando un punto di riferimento per le varie informazioniautomatiche per le attivita di estrazione, in quanto segue una politica di riuti-lizzo dei linguaggi di markup gia disponibili. In particolare, esso adotta gli schemidi annotazione sviluppati per l’ACE Entity Detection e per i task: Time Expres-sions Recognition e Normalization; seguendo le linee guida ACE-LDC per l’Inglese,dove gran parte dello sforzo e stato nell’adattamento alle specifiche caratteristichemorfo-sintattiche della lingua italiana.

Il miglior sistema per il NER dell’italiano e stato il sistema EntityPro, il quale sibasa sui Support Vector Machine ed e stato addestrato considerando sia featurestatiche e sia feature dinamiche. Il sistema ha ottenuto una misura F1-Score di82.14% e la valutazione e stata fatta sulla base di una corrispondenza esatta.

La seconda edizione[9], del 2009, e diventata la campagna di valutazione di riferi-mento sia del Natural Language Processing e sia delle tecnologie vocali per l’italiano.Quest’ultimo, per la prima volta, e stato la principale novita di EVALITA 2009, inquanto e stata organizzata una iniziativa per esso, grazie, sopratutto, al sostegnodel’Italian Association of Speech Science (AISV). Come seconda novita rilevante,lo stesso evento ha iniziato una collaborazione con Passage6.

Per quanto riguarda il task sul Entity Recognition, esso e stato suddiviso in due sub-task: Named Entity Recognition (NER) e Local Entity Detection and Recognition(LEDR). Come nella precedente edizione, per il primo sub-task, la valutazione estata fatta sull’I-CAB, in cui le entita sono state annotate nel formato OBI, o BIO(vedere Sezione 4.3.3 ) ed e stato utilizzato lo stesso data.

I punteggi vanno dal 82.00% al 61.03%, e quattro sistemi (su sette) hanno ottenutoun punteggio sopra al 79% (considerando la loro migliore conduzione). I quattrosistemi con il miglior punteggio, infatti, hanno ottenuto punteggi molto vicini intermini di F1-Score: il sistema con il miglior punteggio (FBK ZanoliPianta) ha ot-tenuto il 82% (Precision 84.07% e Recall 80.02%); il secondo (UniGen Gesmundo)81.46% (Precision 86.06% e Recall 77.33%); il terzo (UniTN-FBK-RGB) 81.09%(Precisione 83.20% e Recall 79.08%); infine il quarto (UniTN Nguyen) 79.77%(Precision 83.05% e Recall 78.86%). Se i risultati vengono comparati in terminidi Precision e di Recall, si nota, che tutti i sistemi hanno ottenuto dei valori altiper la Precision rispetto alla Recall, dopo l’esecuzione del task.

L’ultima edizione[30], del 2011, di valutazione del Natural Language Processing edelle tecnologie vocali per l’italiano, supportato dal gruppo di lavoro NLP dell’AI*IA(Associazione Italiana per l’Intelligenza Artificiale/Italian Association for Artifi-

6Passage e una campagna di valutazione di analisi per il francese, la quale mira a condividerele metodologie con analoghe iniziative a livello europeo.

40

cial Intelligence) e dall’AISV (Associazione Italiana di Scienze della Voce/ItalianAssociation of Speech Science). La novita introdotta da questa edizione e che iltask e stato basato sulle notizie dei telegiornali. Esse sono state gentilmente messea disposizione dalla televisione RTTR, un’emitettente locale.

L’annotazione dei dati e basata sullo standard di ACE-LDC, per Entity RecognitionTask e Normalization Task, ed e stata adattata alla lingua italiana e limitata alriconoscimento delle entita proprie.

La novita principale introdotta per l’edizione 2011 sta nel fatto, che il task e basatosulla trasmissione di notizie ed e consistito in due sub-task7:

• completo: esibizione dei partecipanti sia nel sub-task per la trascrizione au-tomatica e sia nel sub-task Named Entity Recognition;

• o solo NER: esibizione dei partecipanti nel Named Entity Recognition sfrut-tando la trascrizione automatica fornita dagli organizzatori.

Il task sul riconoscimento delle entita proprie ha avuto quattro partecipanti, tuttisolo per il sub-task NER, i quali hanno presentato un totale di nove esecuzioni davalutare ufficialmente. Uno dei partecipanti ha presentato quattro esecuzioni (duein modalita ”chiusa” e due in modalita ”aperta”), un altro tre esecuzioni (duein modalita ”chiusa” e una in modalita ”aperta”) e due hanno presentato solouna esecuzione in modalita ”chiusa”, per un totale di nove esecuzioni da valutareufficialmente.

Nota: Per la modalita ”chiusa” si intende solamente quei dati distribuitidagli organizzatori e senza risorse aggiuntive8. Mentre per la modalita”aperta” si intende tutte quelle risorse aggiuntive a quelle distribuite dagliorganizzatori.

I risultati F1-Score, ottenuti dai sistemi partecipanti nella valutazione ufficiale,vanno dal 63.56% al 52.15% nella modalita ”aperta” e dal 60.98% al 42.42% nellamodalita ”chiusa”, i quali mostrano, che vi e spazio per miglioramenti in questotask. Soltanto il sistema con il miglior punteggio, cioe FBK Alam, ha conseguitodei risultati discreti in termini di F1-Score (63.56% in modalita ”aperta” e 60.98%-60.67% in modalita ”chiusa”). Altri due sistemi hanno ottenuti dei punteggi moltostretti: FBK Chowdhury ha ottenuto dei risultati leggermente superiori rispettoUniPi SimiDeiRossi in modalita ”chiusa” (57.02% e 56.61% rispettivamente), manon ha partecipato alla modalita ”aperta” dove UniPi SimiDeiRossi ha ottenutoun punteggio di 58.19%.

7Per entrambi i sub-task si sono utilizzati gli stessi dati di addestramento.8Per risorse aggiuntive si intende: gazetteer, dizionari di entita proprie, ontologie, Wikipedia

e framework per NLP (come TextPro, GATE, OpenNLP, etc).

41

3.4 Stato dell’arte e related work dei sistemi Arabic NER

Per quanto riguarda la lingua araba, ci sono stati pochi sforzi sui sistemi Ara-bic NER[18]. Questo e dovuto alla mancanza di risorse di entita proprie perl’arabo, dalla limitata quantita di progressi compiuti in generale nel NLP araboe, sopratutto, per l’assenza di iniziative dedicate alla valutazione del NLP e deglistrumenti vocali per la lingua araba.

Il primo sistema NER per la lingua araba e stato sviluppatto da Maloney e Niv(1998) e si chiama TAGARAB, questo riconoscitore di entita proprie integra dentrodi se un motore per il riconoscimento di pattern, con l’analisi morfologica. Il ruolodell’analizzatore morfologico e quello di decidere dove un nome finisce e dove iniziail contesto del ”non nome”; tale decisione dipende sulle parti del discorso dellaparola araba e/o dalla sua inflessione. Le prestazioni combinate ottenute per laPrecision, la Recall e F1-Score sono 92.35%, 84.8% e 88.325%.

Abuleil (2004) ha presentato una tecnica per estrarre nomi propri da un testo,costruendo una base di dati di nomi con la loro classificazione che puo esseresfruttata nei sistemi Question & Answer 9. L’accuratezza del sistema e stata cal-colata in termini di Precision e sono: 90.4% per PERS, 93% per LOC e 92.3% perORG.

Sami, Moreno e Guiraro (2005) hanno usato un corpora parallelo (spagnolo-arabo)ed un tagger di entita proprie in spagnolo per etichettare i nomi in un corpus arabo.Ovvero per ogni coppia di frasi, spagnolo-arabo, allineate insieme. Essi usano unsemplice schema di mappatura per traslitterare tutte le parole nelle frasi in araboe far ritornare quei abbinamenti con l’entita proprie nelle frasi in spagnolo conle entita proprie nelle frasi in arabo. Il loro approcccio e applicabile solo quandosi dispone di un corpus parallelo. Essi hanno ottenuto, con il loro sistema, unaPrecision (90%) ed una Recall (97.5%), rispettivamante alti.

Zitouni, Sorensen, Luo e Florian (2005) hanno adottato l’approccio basato su mod-ello per la rilevazione e il riconoscimento delle entita proprie. Inoltre nello stessoambito, una citazione puo essere sia un nome, sia un nominale oppure un pronom-inale. In questo ambito, la definizione di entita viene estesa e ridefinita in questomodo: un entita e un aggregato di tutte le citazioni, di qualsiasi livello, che fannoa loro volta riferimento ad una entita concettuale. Le operazioni di addestramentoe di valutazione del sistema sono stati fatti sui dati del Automatic Content Ex-

9I sistemi di Question & Answer (QA) (vedere Sezione ), si pongono come approccio alter-nativo ai tradizionali sistemi di Information Retrieval (IR) e di Information Extraction (IE),in quanto la differenza sta nella query, perche essa viene analizzata per cercare di capire il suosignificato e per supportare l’estrazione dell’informazione cercata.

42

traction (ACE) del 2003 e una parte del 2004, in lingua araba. L’obiettivo dellavalutazione e stata fatta per investigare sull’utilita di derivare le feature in n-gramnella rilevazione di citazioni da parte del sistema. Lo stemming n-gram featuresha dato un interessante miglioramento in termini di Precision (64.4%), di Recall(55.7%) e di F1-Score (59.7%).

Benajiba e Rosso hanno sviluppato un sistema, chiamato ANER 2.0 System (2007),il quale usa l’approccio statistico che sfrutta i modelli probablistici: Maximun En-tropy (ME) e Conditional Random Fields (CRF). Essi hanno usato un corpusdi loro proprieta, chiamato ANERCorp, per effettuare l’addestramento e la valu-tazione del modello CRF. L’ANERCorpus e composto da un corpus di addestra-mento e da un corpus di valutazione in modo ad hoc per il NER task. I risultaticombinati, ottenuti nell’esecuzione del task, su tutte le feature in termini di Preci-sion, Recall, e F1-Score sono stati rispettivamente: 86.9%, 72.77% e 79.21%.

Di recente, Khaled Shaalan e Hafsa Raza, hanno sviluppato un loro sistema, NERA(Named Entity Recogniton for Arabic) (2009), il quale usa l’approccio basato suregole, utilizzando tecniche linguistiche basate sulle regole grammaticali della lin-gua araba. Questo approccio e motivato dalle caratteristiche e dalle pecularietadella lingua. Il sistema NERA prova ad estrarre e a riconoscere le entita pro-prie utilizzando degli Arabic script creati ad-hoc. I risultati combinati, ottenutinell’esecuzione del task, su tutte le feature, in termini di Precision, Recall, e F1-Score sono stati rispettivamente: 91.68%, 90.82% e 92.255%.

43

Chapter 4

Descrizione del parser LingPipe

4.1 Una breve panoramica

Il parser LingPipe[5], come e stato accennato, e un insieme di strumenti perl’elaborazione di testo utilizzando la linguistica computazionale ed e scritto inter-amente in Java.

Le potenziali operazioni eseguibili da LingPipe sono:

• Riconoscere i nomi di persone, organizzazioni o luoghi in un documento.

• Classificare automaticamente i risultati della ricerca Twitter in categorie.

• Suggerire correzioni alla query (Forse cercavi. . . ).

L’architettura di LingPipe e:

• Efficiente.

• Scalabile.

• Riutilizzabile.

• Robusta.

Inoltre, LingPipe fornisce un insieme di strumenti per l’Information Extractioned il Data Mining, tra cui:

• il tracciamento delle entita proprie (esempio persone o proteine);

• permette di collegare le entita proprie nelle entry di una base di dati;

44

• classificare il testo per tipo di lingua, codifica dei caratteri, generi, argomentio sentimenti;

• fare la correzione dello spelling rispetto ad un insieme di testi;

• clustering di documenti da argomenti impliciti e scoprire le tendenze signi-ficative nel tempo.

Il parser LingPipe implementa la maggior parte dei Document Analisys. Infatti,in input puo avere file di tipo: XML, HTML e testo normale, mentre in output puoessere configurato per restituire file di tipo XML, oltre al file di tipo testo. Tuttigli input/ouput di tipo XML vengono gestiti attraverso i SAX filter1, permettendocosı di combinare catene di handler per una completa elaborazione XML (Entities,DTD validation, character set, etc).

1I SAX filter hanno lo stesso pattern come gli stream filter di Java (java.io.InputStramFilter).

45

4.2 Elenco delle risorse e delle lingue disponibili

In generale, le risorse[5, 6] che vengono messe a disposizione, sono:

• API e unit test in codice sorgente Java.

• Modelli multi-lingual, multi-domain e multi-genre.

• N-best output con stime statistiche di confidenza.

• Addestramento on-line (learn-a-little, tag-a-little).

• Modelli thread-safe e decodificatori per il Concurrent-Read Exclusive-Write(CREW).

• Character encoding-sensitive I/O.

Inoltre, per LingPipe, esistono altri tipi di risorse e strumenti a disposizione, comedizionari2, regole, Part-Of-Speech Tagger e Phrase Chunker.

L’approccio di base di LingPipe e la portabilita su piu lingue. Tutto cio che si devecambiare e il rilevamento della frase e della tokenizzazione. Sono stati costruiticon successo dei NER per l’inglese, lo spagnolo, l’olandese, il tedesco, il francese,l’hindi, il cinese e l’arabo.

La rete, in aggiunta, mette a disposizione gazetteer per piu lingue, come:

• inglese,

• francese,

• italiano,

• spagnolo,

• arabo,

• cinese e

• tedesco.

2Per i dizionari LingPipe usa direttamente i gazetteer per la loro creazione, perche, grazie acodesti, e possibile addestrare le categorie.

46

I POS Tagger, in formato corpora e CoNNL, supportati dalla rete per LingPipe

sono:

• cinese mandarino (piu fonti),

• tedesco (piu fonti),

• inglese (piu fonti),

• spagnolo,

• arabo,

• cecoslovacco allineato con l’inglese,

• greco,

• coreano e

• portoghese.

47

4.3 Il diagramma dei componenti

Nell’Ingegneria del Software, un diagramma dei componenti (o component dia-gram), e un diagramma che ha come scopo, quello di rappresentare la strutturainterna dell’intero software modellato, secondo i termini delle sue componenti prin-cipali e delle relazioni fra di esse.

In questa sezione vengono mostrati due diagrammi[5, 19, 4] dei componenti delparser di LingPipe: il primo diagramma schematizza e non scende nei dettaglidei singoli package, mentre il secondo diagramma mostra le classi di maggioreimportanza del parser di LingPipe.

La Figure 4.1 mostra soltanto i package del parser, con le eventuali relazioni traessi, che sono: corpus, tokenizer, suffixarray, symbol lm (language model), classifye tag (tagging).

Figure 4.1: Diagramma dei componenti relativo ai package del parser di LingPipe.

48

La Figure 4.2 mostra le classi, con le eventuali relazioni, dell’intero parser, conciascuna classe appartenente al proprio package.

Figure 4.2: Diagramma dei componenti relativo alle classi del parser di LingPipe.

49

4.4 Named Entity Recognition di LingPipe

Il parser LinPipe, per estrarre[5] le entita proprie, utilizza i chunker, per ogni tipodi approccio. Come e stato accennato nella Sezione LingPipe: il parser adottato,esso fornisce: per l’approccio basato su regole il Regular Expression-Based Chun-ker ; per l’approccio basato su modello stocastico (HMM) il Model-Based Chun-ker ; e per l’approccio basato su dizionario il Dictionary-Based Chunker, che a suavolta e suddiviso in due tipologie: Exact Dictionary-Based Chunker e ApproximateDictionary-Based Chunker.

Ovviamente, l’intero processo di estrazione delle entita proprie e identico per tuttie tre gli approcci. Esso e suddiviso nei seguenti passi:

1. Creazione di un chunker.

2. Applicazione del metodo chunk〈. . .〉 tramite il chunker creato, per prendereun chunking.

3. Inizializzazione di un iterator dal chunkSet del chunking.

4. Scorrimento del set di chunk tramite l’oggetto iterator.

a. Per ogni chunk, ritorna un’entita propria e il suo tipo associato.

Riepilogando, viene prima creato un chunker ed il metodo chunk〈. . .〉 del chunkere utilizzato per prendere un chunking. La maggior parte del tempo di elaborazioneviene speso nel passo 2 per creare il chunking. Il ciclo scansiona un elenco ordinatodi chunk memorizzati in una lista collegata e per ogni chunk ritorna un’entitapropria assieme al tipo (PERS, ORG, LOC e MISC). Il tipo di chunker e l’unicadifferenza nei tre approcci, che si andranno a descrivere di seguito.

4.4.1 Regular Expression-Based Chunker

Il Regular Expression-Based Chunker e particolarmente semplice se e possibilescrivere un’espressione regolare (vedere Appendice C ), che cattura l’entita propriaprevista dal pattern (modello).

Infatti, il primo passo consiste nello scrivere un’espressione regolare, che cor-risponde a tutti e solo a quelle entita proprie, che si vogliono riconoscere. Un esem-pio potrebbe essere quello di trovare gli indirizzi email ben formato. Fondamental-mente, le espressioni regolari sono l’unica parte sostanziale dell’implementazione.

50

4.4.2 Dictionary-Based Chunker

L’utilizzo di un dizionario nella ricerca delle entita proprie, talvolta, e sufficienteper trovare tutti le entita proprie, presenti nel testo, con un dizionario. Ad esem-pio, un nome come ”50 Cent” o un nome del prodotto simile a ”Galaxy SamsungS4” puo rivelarsi molto difficile da trovare in un testo, utilizzando solo riconosc-itori stocastici o solo riconoscitori basati su regole. Talvolta un dizionario puoessere utilizzato in combinazione con un sistema di riconoscimento statistico permigliorare la Recall per i nomi ”difficili”. I nomi tendono ad essere difficili se sonofacilmente confondibili con i numeri o con le parole comuni.

Un’altra strategia che puo essere utilizzata, sia per eseguire un riconoscimentostatistico di un’organizzazione inserita in un corpus e quindi utilizzare l’uscitaper costruire un dizionario, che puo essere utilizzato per ri-annotare frammenti dicorpus, che possono essere stati persi nel primo passaggio.

Il Dictionary-Based Chunker usa un dizionario3 per identificare le entita proprieall’interno di una stringa. Un dizionario, in LingPipe, e fatto da una lista di entry,ciascuna delle quali consiste di una terna formata da: stringa (entita propria), tipo(PERS, ORG, LOC e MISC) e punteggio.

Spesso, per la costruzione dei dizionari si utilizzano i gazetteer di entita proprie(persone, organizzazione e luoghi).

Exact Dictionary-Based Chunker

Nell’Exact Dictionary-Based Chunker, di LingPipe, si e utilizzato l’approccio piusemplice nel fare un’espressione regolare disgiuntiva o una ricerca su sottostringhe,tale che da far convergere rapidamente la ricerca all’interno dei dizionari, an-che di modeste dimensioni. Per questo, LingPipe fornisce un’implementazionedell’algoritmo di Aho-Corasick4[2]. La bellezza di questo algoritmo sta nel trovaretutto tramite gli abbinamenti su un dizionazio in tempo lineare, indipendentementedal numero di ”disabbinamenti” o dalla dimensione del dizionario.

Nell’Exact Dictionary-Based Chunker, al costruttore gli vengono forniti: un diziona-

3Il tipo di struttura utilizzato per i dizionari e il MapDictionary.4L’algoritmo di Aho-Corasick[2] e un algoritmo per la ricerca di stringhe (o di string matching)

inventato da Alfred V. Aho e Margaret J. Corasick. Esso e un tipo di algoritmo basato sudictionary-matching, il quale effettua la ricerca degli elementi in un’insieme finito di stringhe(ovvero il dizionario) con un testo in input; esso abbina tutti pattern simultaneamente. Lacomplessite dell’algoritmo e lineare nella lunghezza del pattern, piu la lunghezza del testo cercatoe piu il numero di abbinamenti in output.

51

rio, un tokenizer factory e due flag. Il dizionario, oltre ad essere popolato con unaentry alla volta, puo essere caricato da una versione, precedentemente salvato, daun file5. Il tokenizer factory usa il metodo IndoEuropeanTokenizer per creare itoken dal testo, che poi vengono usati nella ricerca all’interno del dizionario, perfare l’abbinamento delle singole entry.

Approximate Dictionary-Based Chunker

Nell’Approximate Dictionary-Based Chunker, di LingPipe, si implementa sempreun chunker basato su dizionario, il quale pero esegue una ricerca per approssi-mazione. La ricerca, per l’identificazione dei chunk, si basa su di un abbinamentofuzzy, la quale viene valutata utilizzando una funzione per il calcolo della dis-tanza. Il dizionario dell’Approximate Dictionary-Based Chunker viene popolatonello stesso modo del dizionario dell’Exact Dictionary-Based Chunker. Esso, in-fatti, non si limita a cercare corrispondenze esatte, bensı restituisce un’istanza ditipo WeightedEditDistance, che e il grado di similitudine tra un chunk ed un entrydel dizionario.

4.4.3 Model-Based Chunker

Implementare un NER utilizzando l’approccio statistico e relativamente semplicese esiste un modello addestrato precedentemente. LingPipe attualmente disponedi tre generici ed addestrabili chunker di tipo stocastico, in particolare di tipoHidden Markov Models (HMM), che possono essere utilizzati per il riconoscimentodi entita proprie.

CharLmHmmChunker

Il CharLmHmmChunker impiega un estimatore basato su modello stocastico (HMM)e un tokenizer factory per fare l’addestramento di un chunker. L’estimatore usatoe un’oggetto della classe AbstractHmmEstimator per la stima del modello sot-tostante. Esso usa un tokenizer factory per ”spezzare” i chunk in sequenze ditoken e tag.

Per l’addestramento del modello, questa classe implementa l’interfeccia ObjectHa-ndler〈Chunking〉, che puo essere utilizzato per fornire le istanze di addestramento.Le istanze di addestramento vengono fornite attraverso un chunk handler nel modo

5In questo modo non e necessario crearlo ripetendo la procedura entry per entry.

52

consueto. Per il tag handler, esse richiedono lo standard BIO tagging scheme (permaggiori dettagli, vedere Sezione 4.4.4 ) in cui il primo token in un chunk di tipoX e etichettato con B X (BEGIN), tutti i token successivi nello stesso chunksono etichettati con I X (INSIDE) ed i token che non stanno nel chunk vengonoetichettati con O. Inoltre, questo chunker puo essere addestrato con le entriesdel dizionario tramite un’opportuno metodo, dove chiamandolo si addestrano leprobabilita di emissione, per i relativi tag, determinati dalla suddivisione in tokendella sequenza di caratteri (dopo la conversione al sottostante tag schema definitonella classe HmmChunker).

Questo chunker e basato sulla codifica di chunking all’interno del problema dietichettatura (e un contesto leggermente piu ricco e piu sensibile della codificastandard I/O). Allora, un model character language gestisce la codifica, per ognitag (o stato) nel modello, e un modello di transizione bi-gram con probabilitamassima. Questo chunker esegue: il First-Best output, il N-Best output e ilConfidence output.

Riassumendo, questo parser e il piu semplice anche se ha un chunker meno ac-curato, ma in compenso ha una buona Recall per il emphConfidence output epossiede delle stime abbastanza affidabili e se e abilitata la funzione di caching,esso e molto veloce .

CharLmRescoringChunker

Il CharLmRescoringChunker estende la classe AbstractCharLmRescoringChunkere fornisce un chunker, di tipo long-distance character language model-based, cheopera con il rescoring dell’uscita, avendo un chunker di tipo character languagemodel. Il modello esegue il rescoring sui chunker sottostanti. Essi sono un’istanzadella classe CharLmHmmChunker, i quali vengono configurati fornendo al costrut-ture le seguenti specifiche: il tokenizer factory, la lunghezza del n-gram, il numerodi caratteri ed il rapporto di interpolazione. Il modello di rescoring utilizzato daquesto chunker si basa su un character language model delimitato per ogni tipodi chunk, processando ulteriormente il testo non presente nei chunk con il char-acter language model. L’addestramento viene fatto nel modo usuale, attraversouna chiamate al metodo per il chunk handler, il quale, a sua volta, implemental’interfaccia ObjectHandler〈Chunking〉, permettendo cosı il suo addestramentotramite dei chunking di esempi.

Questo chunker possiede un’ottima Precision, ma e il piu lento fra tutti i chunker6.Esso usa un CharLmHmmChunker (si veda il punto precedente) per generare le

6Questo accade sopratutto quando effettua due volte il calcolo dei punteggi sulle N-Best List.

53

ipotesi, che poi ricalcola utilizzando la distanza maggiore dei modelli di tipo lan-guage character. Esso tende ad approssimare la confidenza stimata attraverso leN-Best List, la quale pero viene attenuata dal modello.

TokenShapeChunker

Il TokenShapeChunker utilizza il TokenShapeDecode per il named-entity e il tok-enizer factory per implementare un entity detection, attraverso l’interfaccia Chunk.Un chunker named-entity viene costruito partendo da un tokenizer factory e da undecoder. Il tokenizer factory crea i token, i quali poi vengono inviati al decoder; itipi di chunk identificati sono derivati dai tipi di named-entity trovati. I token egli spazi bianchi restituiti dal tokenizzatore vengono concatenati per formare, neltesto sottostante, una ”slice” (fetta) di chunk, restituiti dallo stessi chunker. Cosıun tokenizer, simile al Stop List tokenizer o al Porter stemmer tokenizer, creerauna ”slice” di carattere, il quale non si abbinera all’input. Inoltre, e possibile uti-lizzare un filtro whitespace-normalizing tokenizer, come ad esempio per produrreun testo normalizzato per la base di chunk.

Questo chunker funziona con un modello generativo, per prevedere congiuntamenteil token successivo ed il tag succesivo, i quali sono basati dal token precedentee dal tag precedente. Le parole sconosciute o rare sono sostituite tramite unaclassificazione Morphologically-Based (basati su un’istanza di TokenCategorizer).Per utilizzare un chunker (ovvero per l’addestramento del modello) di questo tipo,bisogna utilizzare la classe TrainTokenShapeChunker.

Riassumendo, questo chunker e molto veloce, ma dispone solo del First-Best Outpute le sue prestazioni, normalmente, sono a meta strada tra CharLmRescoringChun-ker e CharLmHmmChunker.

4.4.4 Addestramento del modello per un sistema NER

Come e stato accennato, il NER ha come compito quello di etichettare una datasequenza di parole, in cui si assegna un fissato tag per ogni parola appartenentealla frase in ingresso. Per poter fare l’addestramento del modello, indiferentementedalla lingua su cui si voglia costruire il proprio riconoscitore delle entita proprie,si utilizza, per lo schema di codifica, il sistema BIO (o sistema OBI ). Con il tagB X (Begin) si rappresenta la prima parola di un’entita propria di tipo X, peresempio, al posto della X, PERS (Person) o LOC (Location). Il tag I X (Inside)indica che una parola e parte di un’entita propria, ma non e la prima parola. Il

54

tag O (Outside) e utilizzato per tutte le parole, che non sono delle entita proprie(un esempio e in Table 4.1 con una frase etichettata).

Figure 4.3: Addestramento e valutazione di un modello stocastico (HMM) perNER.

Il chunker basato su modello e tra i piu complessi rispetto ai due chunker prece-denti; in questo approccio, il chunking con il miglior valore viene restituito dalchunker pre-compilato, che e stato letto da un file7, il quale contiene un EN-TITY MODEL.

Per la fase di addestramento del modello, bisogna quindi avvalersi dei dati diaddestramento, che devono contenere un ampio numero di token etichettati. Peresempio, si consideri la frase ”Mr. Smith goes to Washington.” mostrata in Table4.1, la quale mostra la lista di token e degli entity tag associati alla frase.

7Questo file contiene un modello, il quale e stato creato da un’addestramento precedente, sudei dati di addestramento.

55

Table 4.1: Lista di Token e di Entity Tag associati in una frase.

Token tag

Mr. B PERSSmith I PERSgoes Oto O

Washington B LOC. O

Ogni tag e costituito da un prefisso e un suffiso che indica il tag del corrente, delprecedente o del seguente token.

E possibile costruire un modello, da un insieme di dati di addestramento, peretichettare i token con gli entity tag. Il modello continua a tracciare il numero ditransizioni da un tag all’altro ed il numero di occorrenze di una parola dato untag.

Ora, si prenda in considerazione la frase precedente, la quale e composta da settetoken (vedere la tabella precedente). Si e in grado di impostare gli entity tag perla data frase da una tabella di 6 righe e 9 colonne. In Table 4.2 si mostra soloalcune delle nove colonne per brevita, dove ogni colonna rappresenta un entity tag ;essa contiene i token e gli entity tag generati da un modello.

Table 4.2: Lista di Token e di Entity Tag generati da un modello stocastico(HMM).

Token B LOC · · · B PERS I PERS O

Mr. XSmith Xgoesto

Washington X. X

I valori della prima riga sono calcolati dal prodotto della probabilita diiniziare in una colonna con tag x e la probabilita della parola ”Mr”, pre-sente nel modello, per l’entity tag x. Le rimanenti righe della tabella, fattaun’eccezione per l’ultima riga, sono calcolate dal prodotto della probabilitadi transizione, dall’entity tag x all’entity tag y, con la probabilita del token,presente nel modello, per il dato entity tag. Infine, l’ultima riga nella tabellae il prodotto della probabilita di finire con un entity tag x e la probabilita

56

del carattere ”.”, presente nel modello, per il tag x.

Nel caso dell’esempio, l’insieme dei tag per i sette token della frase sono estrattedalla tabella, iniziando dall’ultimo token e lavorando all’indietro fino ad arrivareal primo token. Per ciascun token si calcola l’entity tag con la piu alta probabilitautilizzando la tabella (o matrice) delle probabilita presente in Table 4.2.

L’output di questo algoritmo non puo essere utilizzato direttamente, in quanto sene occupa la classe HmmChunk, che ne gestisce la loro decodifica per i vari entitytag (PERS, LOC, ORG e MISC), che vengono restituiti nel chunk.

In LingPipe e possibile effettuare l’addestramento di un corpus e la cross-validation;inoltre, e possibile, sia con un chunker di tipo stocastico o sia con un chunker ditipo stocastico con rescoring, utilizzare dei dizionari8 durante la fase di trainingdelle categorie. Esso, quindi, permette di costruire dei proprio modelli da utilizzareall’interno dei sistemi NER, che applicano l’approccio statistico.

Funzioni di LingPipe per l’addestramento del modello

Per fare cio e necessario, che le posizioni vengano ”alimentate” attraverso il metodotrainDictionary〈. . .〉. Questo metodo non e astratto ed e disponibile sia per untradizionale chunker di tipo stocastico, attraverso la funzione CharLmHmmChun-ker〈. . .〉, e sia per un chunker di tipo stocastico con rescoring, attraverso la funzioneCharLmRescoringChunker〈. . .〉.

Invece, per l’addestramento del modello, che sfrutta i dizionari, e necessario uti-lizzare il metodo trainDictionary〈. . .〉, cosicche nella fase di addestramento, laPrecision del modello aumenti. Questo metodo non e astratto ed e disponibile siaper il tradizionale chunker di tipo stocastico (chunk.CharLmHmmChunker) e siaper la versione rescoring (chunk.CharLmRescoringChunker).

Core Business Intelligence

Il Core Business Intelligence, ovvero colui che si occupa della gran parte del lavorodi parsing del corpus annotato manualmente, e la classe BioTagChunkCodec9, laquale si occupa sia del parsing, sia del chunking e sia della convalida del parsing.La classe BioTagChunkCodec implementa un chunk per taggare sulla base delloschema di codifica, ad esempio il sistema BIO (o sistema OBI ), assieme ad unospecifico factory tokenizer.

8In questo caso, i dizionari vengono utilizzati come gazetteer.9Questa classe e thread-safe.

57

Lo schema di codifica/decodifica del sistema BIO

La base del sistema BIO e quella di ”spezzare” il chunk, di tipo stocastico, in unasuccessione di token. Il primo token di tipo X in a chunk e etichettato con B X,e le sottosequenze di token in un chunk di tipo X sono etichettati con I X. Tuttigli altri chunk sono etichettati con il tag O.

Si consideri, per esempio, la seguente stringa in input:

John Jones Mary and Mr . J . J . Jones ran to Washington .0123456789012345678901234567890123456789012365678901230 1 2 3 4 5

e la suddivisione in blocchi con questa data stringa:

( 0 , 1 0 ) :PERS, ( 1 1 , 1 5 ) :PERS, ( 2 4 , 3 5 ) :PERS, ( 4 3 , 1 3 ) :LOC

L’indicizzazione viene fatta sia sul primo e sia sull’ultimo carattere, inoltre, si notache le due entita proprie (che sono due nomi di persona) ”John Jonus” e ”Mary”,sono due chunk seperati di tipo PERS ; mentre il blocco per ”Washington” appareprima della fine del periodo ed e un entita propria di tipo LOC.

Nel caso in cui si ha un tokenizzatore, che ”spezza” gli spazi e la punteggiatura, iltoken inizia a partire dal + e continua attraverso i segni −.

John Jones Mary and Mr . J . J . Jones run to Washington .+−−− +−−−− +−−− +−− +−+ ++ ++ +−−−− +−− +− +−−−−−−−−−+

In Table 4.3 i token si trovano nella colonna di destra, mentre nella colonna disinistra si trovano i tag utilizzati dalla schema di codifica/decodifica del sistemaBIO, utilizzati da LingPipe.

Nota: in ciascun blocco si possono avere un qualsiasi numero ditoken.

Vi e un singolo tag O con solo il prefisso di default; per il tag B X ed il tag I Xhanno entrambi il prefisso predefinito, mentre il suffisso e diverso per tutti i tipidi X chunk10.

10Con il simbolo X si intende, ad esempio: PERS, ORG, MISC, DATE, etc.

58


Token Tag

John B PERSJones I PERSMaby B PERSand OMr. B PERSJ. I PERSJ. I PERS

Jones I PERSran Oto O

Washington B LOC. O

Le sequenze di tag legali

Le sequenze dei tag legali sono descritte in Table 4.4, in cui la prima colonnariporta schematicamente i tag e la seconda colonna mostra i tag che li seguono,con le variabili che vanno su tutti i tipi di chunk:

Table 4.4: Le sequenze legali con il sistema BIO.

Tag Successivi tag legali

O O, B XB X O, I X, B YI X O, I X, B Y

Nota: il tentativo di codificare etichette, con sequenze di tag illegali,comportera al sollevamento di una eccezione.

59

4.5 Part-Of-Speech Tagger di LingPipe

Il Part-of-Speech Tagging11 (POS Tagging) e un task complesso del NLP e consistenell’assegnazione automatica di un Part-of-Speech tag (POS tag) a ciascuna parolain un testo. Sfortunatamente, la stessa parola puo essere taggata con differentiPOS tag, per questo il POS Tagging e un task per la disambiguazione. Infatti,egli assegna l’etichetta ad una parola in un testo (corpo) in corrispondenza ad unaparticolare parte del discorso, basandosi sia sulla sua definizione, cosı come il suocontesto, cioe in rapporto con le parole adiacenti e collegate in una frase o in unparagrafo.

Quindi, per fare questo tipo di ricoscimento e necessario avere un modello stocas-tico, in particolare un Hidden Markov Models (HMM), il quale e stato preceden-temente addestrato su una sequenza di frasi precedentemente etichettate, e poisalvato su file. Con il modello, si puo effettuare l’operazione di associazione deiPOS tag [4, 5, 19] ai token, durante il processo di POS Tagging.

4.5.1 POS tag

Un POS Tagger assegna il tag piu probabile a ciascun token del testo utilizzandoil modello. Il numero standard dei POS tag sono otto. Essi sono: aggettivi,avverbi, congiunzioni, articoli determinativi, nomi, preposizioni e verbi, i qualivengono usati per trovare riferimenti ai nomi propri, alle frasi e identificare eventinel testo. Questo numero e sufficiente per quei task, che hanno bisogno solo diidentificare i nomi o gli aggettivi senza ogni ulteriore qualificazione. I tag set usatiper identificare le parti del discorso a un livello piu dettagliato possono avere 100o piu tag, che descrivono con maggior dettaglio una parte del discorso.

11Nel corpus linguistico, il Part-of-Speech Tagging viene chiamato anche grammatical taggingo word-category disambiguation.

60

4.5.2 Addestramento del modello per un sistema POS Tagger

Per la fase di addestramento del modello, bisogna avvalersi di un grande insiemedi frasi etichettate similmente alla frase mostrata in Table 4.4. Queste frasi cos-tituiscono il modello che viene utilizzato per predire i tag delle parole presentinell’insieme di validazione.


Token tag

The atwartime nnprotocol nnof in

September np12 cd. .

In un linguaggio dinamico, il lessico e la sintassi cambiano nel tempo e percio ilmodello addestrato su tale linguaggio, non sara piu ben performante. Il modellomemorizza le stime di probabilita di transizioni di stato e lo stato data una certaparola.

Figure 4.4: Addestramento del modello stocastico (HMM) per POS Tagger.

61

Il problema del POS Tagging puo essere essere indicato come l’identificazione delpiu probabile tag t1,n data la parola w1,n da una frase di lunghezza n. Si nota,che il modello statistico (HMM) trova la sequenza dei tag piu simili per le parolapresenti nell’intera frase.

In questo modo e possibile applicare la regola di Bayes per definire il problemacome

arg maxt1,n

p(t1,n|w1,n) = arg maxt1,n

p(w1,n|t1,n)× p(t1,n) (4.1)

= arg maxt1,n

n∏i=1

p(w1,n|t1,n)× p(t1,n)

La prima parte dell’espressione (4.1) a destra dell’uguale rappresenta l’informazionelessicale, che data la probabilita di una parola w1,n di essere vista con il tag t1,n,mentre la seconda parte dell’espressione (4.1), sempre a destra dell’uguale, esprimela probabilita del tag t1,n. La parte destra dell’espressione (4.1) puo essere estesausando la regola di chain per calcolare la probabilita, che una data parola w1,n siadipendente solo su un tag e non su una sequenza di tag. Il massimo del prodottodi queste due probabilita da il tag piu probabile, che avrebbe generato la parolaosservata. Il numero delle possibili combinazioni di sequenze di tag di lunghezza ne grande e ci vorrebbe tempo per trovare la migliore di tutte queste possibilita. Perquesto, si fa qualche ipotesi per semplificare il calcolo. Si assume, che le parolesiano condizionalmente indipendenti l’uno dall’altro in un tag e un tag dipendesolo dal tag precedente.

Sulla base di questi presupposti, si puo stimare la probabilita di una data parolaw dato un tag t come il rapporto del numero di volte che la parola w e stato vistocon il tag t e il numero di occorrenze del tag t.

p(w|t) =Count(w, t)

Count(t)(4.2)

La probabilita di sequenze di tag viene calcolata dal rapporto tra il numero divolte che un tag tj seguito dal tag ti per il numero di volte che il tag ti e statovisto.

p(tj|ti) =Count(ti, tj)

Count(ti)(4.2)

62

Normalmente, viene aggiunto uno a tutti i conteggi per gestire i casi di paroleinvisibili in entrambe le stime di probabilita. Questa operazione (aggiungendouno a tutti i conteggi) e chiamato Laplace smoothing e distribuisce uniformementequalche probabilita a tutte le parole non viste.

4.5.3 Lettura del modello

Per la lettura del modello e la costruzione del decoder, si richiede soltanto: lamanipolazione del flusso dei dati, assieme al casting e al wrapping degli stessi.

Esso viene caricato leggendo il file che lo contiene, il quale e posizionato in unacartella prestabilita, per poi passarlo all’oggetto com.aliasi.hmm.HiddenMarko-vModel istanziato; una volta terminata la fase di caricamento del modello si chiudel’oggetto ObjectInputStream; e per finire, si istanzia l’oggetto decoder, al quale gliviene passato come parametro l’oggetto com.aliasi.hmm.Hidden-MarkovModel delmodello appena caricato.

4.5.4 Tokenizzazione

Il codice per eseguire la decodifica e molto semplice; in primo luogo, l’input ar-riva sotto forma di righe di testo e si ha quindi bisogno di scomporlo in singolichunk.

Questo lo si fa con la creazione di un oggetto tokenizzatore, che permette di definireun token come la piu lunga sequenza contigua non vuota di simboli alfabetici (\pL),cifre (\d), trattini (\) ed apostrofi (′); ma anche di singoli caratteri diversi daglispazi (\S).

4.5.5 Analisi dei token

Per effettuare l’analisi dei token[4, 5], e necessario avere una funzione che leggeda una cartella uno/piu file, con all’interno uno/piu documento/i ed un modellostatistico (HMM) addestrato, in questo caso, per poi eseguirci, sopra al/i docu-mento/i, l’operazione di Part-of-Speech Tagger.

63

4.5.6 Risultato finale

Il risultato finale, che viene prodotto dal processo di POS Tagging sul testo ininput, e una lista di token assieme ai loro associati POS tag.

Questo processo in LingPipe viene fatto prendendo i singoli token, elaborati prece-dentemente, per poi taggarli ciascuno singolarmente.

Il modello utilizzato per l’etichettatura dei POS tag, non fa altro che creare leipotesi di probabilita in base alle posizioni dei token all’inizio o alla fine dellasingola frase.

Si consideri, per esempio, la seguente stringa in input:

Time f l i e s l i k e s an arrow . This i s a second sentence .

Il risultato che si ottiene dal processo di POS Tagging e il seguente:

Time/nnf l i e s /vbzl i k e s / csan/ atarrow/nn. / .This /dti s /beza/ atsecond /odsentence /nn. / .

64

Chapter 5

Analisi del modulo POS Tagger diLingPipe

Si e effettuato l’analisi prestazionale del modulo POS Tagger di LingPipe ed even-tualmente si e pensato anche di sostituirlo con quello gia, il TreeTagger, presentenell’estrattore terminologico TermExtractor, nel caso si fossero ottenuti risultatisoddisfacenti.

5.1 POS Tagger: confronto con il TreeTagger

5.1.1 TreeTagger

Il TreeTagger [25] e un software Open Source, sviluppato da Helmut Schmid pressol’Universita di Stoccarda, che consente di analizzare un testo ed ottenere il Part-of-Speech[11] e la lemmatizzazione delle singole parole.

Due sono i vantaggi derivanti dalla lemmatizzazione e dall’etichetattura del testo.

Il primo vantaggio (derivante dalla lemmatizzazione) e quello dell’ottimizzazionedelle basi di dati. Infatti in esse, saranno presenti solamente i lemmi ai qualiverranno ricondotte le forme presenti nel testo. I verbi saranno presenti nella basedi dati coniugati all’infinito e non in tutte le possibili forme in cui possono essereconiugati; i sostantivi saranno presenti al singolare; aggettivi ed avverbi in inglesenon avrebbero teoricamente bisogno di essere lemmatizzati poiche indeclinabili.Cio comporta un notevole snellimento della base di dati e quindi un minore spazio

65

di memoria occupato da esso, ed un aumento non indifferente della velocita diprocesso del software e di conseguenza dell’analisi.

Il secondo vantaggio (derivante dall’etichetattura) consiste nel fatto che i softwarerealizzati potranno effettuare ricerche nella base di dati soltanto su parole apparte-nenti a determinate categorie grammaticali riducendo sensibilmente il numero diquery da effettuare ed aumentando di conseguenza le prestazioni del software. Sipotrebbe per esempio voler analizzare solo i nomi o solo gli avverbi. L’etichettaturapermette inoltre di dividere i lemmi presenti nella base di dati in tabelle diversesecondo la categoria grammaticale.

Il TreeTagger[6] utilizza dei parametri di lingua, i quali vengono forniti diretta-mente dal suo sito, per il suo utilizzo con testi in inglese, francese, tedesco, italiano,spagnolo, russo, bulgaro e olandese. I parametri per altre lingue sono disponibilida siti collegati alla pagina web TreeTagger. Per una lingua per la quale non es-istono parametri, e necessario annotare a mano alcuni data-tag, e quindi eseguireun programma di training (fornito con il TreeTagger) per creare i parametri.

Per fare dei test comparativi tra TreeTagger e POS Tagger di LingPipe[19, 4]si e utilizzato il wrapper Java per il TreeTagger, sviluppato da Richard Eckartde Castilho. Il TreeTagger4Java1 e stato scritto con particolare attenzione allaindipendenza della piattaforma ed e facile da integrare nelle applicazioni, e scrittoin Java ed e per questo portabile su tutti i sistemi operativi, come: OS X, UbuntuLinux e Windows.

TT4J

Nel TT4J, la classe principale e TreeTaggerWrapper. Esso genera e mantieneun processo TreeTagger per ogni istanza di questa classe. Il processo associatotermina se il TT4J termina, oppure il processo viene riavviato automaticamente,se il modello subisce delle modifiche; altrimenti il processo resta in esecuzione(background), permettendo cosı di risparmiare del tempo.

1Per semplicita, d’ora in avanti, lo si abbrevia a TT4J.

66

Il processo rimane inattivo quando non viene utilizzato, consumando solo un podi memoria, fatta eccezione della CPU, che non viene impegnata.

Durante l’analisi, due thread sono utilizzati per comunicare con il TreeTagger.Un thread scrive il token al processo TreeTagger, mentre l’altro thread riceve itoken analizzati.

Gli utenti all’interno del TT4J, includono un tokenizer, in quanto lo stesso nondispone la funzione di tokenizzazione, questo perche ci sono delle librerie, che losvolgono in maniera ottima. Per esempio, un buon tokenizzatore in lingua inglesee presente nel parser della Stanford.

Per poter utilizzare il TT4J[4, 6] si e implementato una piccola applicazione, chelegge da una cartella uno o piu file, con uno o piu testi, ed un modello adde-strato per la lingua inglese, il quale viene utlizzato sul/sui testo/i per fare il POSTagging.

Per effettuare facilmente l’operazione di tokenizzazione, perche il TreeTagger nonoffre metodi per fare questa operazione, e stato integrato nell’applicazione la classePennTreebankTokenizerFactory2 di LingPipe e si implementa il metodo, che effet-tua la tokenizzazione del testo.

Essa permette di effettuare l’operazione di tokenizzazione secondo lo standardPenn Treebank ; il metodo per tokenizer prende un array di stringhe, l’indice diinizione e di fine. Per ricevere il token analizzato, si e dovuto impostare un To-kenHandler personalizzato con il metodo SetHandler〈. . .〉.

2Nella classe PennTreebankTokenizerFactory si definisce l’espressione regolare.

67

5.1.2 Che cosa sono i tag-set?

Il tag-set e un insieme di etichette, dove ciascuna di esse descrive il significato(semantico o grammaticale) di un lessema a cui viene associato il tag. Esistonovarie tipologie di tag-set che vengono utilizzati; in questo particolare caso di stu-dio, sono stati usati il Brown Corpus Tag-Set ed il TreeTagger Tag-Set, anche sequest’ultimo si ispira al Penn TreeBank Project, ma il suo tag-set e leggermentediverso e piu grande3 del Penn TreeBank Project [25].

5.1.3 L’algoritmo Tag-Set Reduction

Come si e accennato, per fare il confronto tra i due sistemi e stato necessario”ridurre” i singoli token etichettati secondo le regole del Brown Corpus Tag-Set edel TreeTagger Tag-Set con i tag del Penn TreeBank Project [25].

Una tecnica trovata in rete, per la riduzione di un qualsiasi tag-set, e quella pro-posta da Thosten Brants[29]4, dell’Universita di Saarlandes, il quale propone unmodo per creare un tag-set ridotto da un tag-set originario tale che le categorie, conuna distribuzione di frequenza molto simile in un corpus, siano combinate senzaperdere informazioni fornite dall’insieme dei tag originari. Questo viene fatto uti-lizzando un algoritmo di clustering, per distribuire, con una certa probabilita, i tagoriginari nelle classi, dove ciascuna di queste classi rappresenta il tag ridotto. Iltesto in input sara privo di ambiguita con il nuovo tagset ridotto, facendo in modoche il tag originario sia ancora identificabile univocamente da quello nuovo.

3Il TreeTagger Tag-Set contiene 58 tag.4La proposta messa a disposizione da Thosten Brants e stata introdotta e valutata durante

un esperimento.

68

L’algoritmo proposto, denominato Tag-Set Reduction, prende spunto proprio daquesta tecnica, ma al posto di utilizzare la tecnica di clustering, si e optato inveceper il metodo basato su regole, sotto forma di espressioni regolari, le quali associanoal tag originario in input, il nuovo tag ridotto; questa operazione puo essere vistacome funzione di riduzione sul tag-set originario (vedere Figure 4.4).

Figure 5.1: Funzione di riduzione del tag-set dell’algoritmo Tag-Set Reduction.

La funzione dell’algoritmo fRed non fa altro, che prendere in input un tag-set orig-inario di partenza ed un’insieme formato da coppie di (tag-set di riduzione, regoladi riduzione), e trasforma tale tag-set originario nel nuovo tag-set ridotto.

Formalmente la funzione viene definita in questo modo

fRed : TagSetOrig ×RegExpr → TagSetRed,

assicurando l’unicita dell’operazione di riduzione, in quanto le espressioni regolarinon vanno in conflitto tra di loro, evitando cosı di andare a trasformare (o sosti-tuire) tag precedentemente trasformati (o sostituiti). Infatti una volta applicatala regola corretta al tag originario si ottiene l’equivalente tag ridotto.

69

Di seguito, viene mostrato sia lo pseudo-codice dell’algoritmo.

prec.c.: 〈tagRed, rule〉 ∈ RuleSet,〈tag〉 ∈ TagSetOrig;

post.c.: TagSetRed;

function Tag-SetReduction(RuleSet, TagSetOrig)TagSetRed := {0};for 〈tag〉 ∈ TagSetOrig do

for 〈rule, tagRed〉 ∈ RuleSet doif matches(tag, rule) then

TagSetRed := TagSetRed ∪ 〈tagRed〉;break;

end ifend for

end forreturn TagSetRed;

end function

La complessita computazionale e

O(|m| × |n| × |k|),

dove:

m e il numero dei tag da ridurre;

n e il numero dei tag di riduzione;

k e il tempo che impiega la regola a controllare, sotto forma di espressioneregolare, se il tag in analisi e riducibile o non riducibile.

Ovviamente esiste un’altra soluzione, che permette di abbassare tale costo com-putazionale andando ad utilizzare la hash table5[28], come struttura dati per lamemorizzazione delle regole, in quanto in base alla grandezza dell’array in cuiavviene la ricerca e la memorizzazione delle informazioni, si ha una tabella dellacomplessita computazionale del tempo necessario alla ricerca stessa. Percio conun maggiore spazio disponibile, corrispondera un minor tempo necessario nel casopeggiore.

5La hash table[28] e una struttura dati usata per mettere in corrispondenza una data chiavecon un dato valore. Viene usata per l’implementazione di strutture dati astratte associative comeMap o Set.

70

5.1.4 L’applicazione Tag-Set Reduction Computing

Per l’esecuzione dell’esperimento si dovuto fare, oltre alla progettazione, l’implemen-tazione dell’algoritmo Tag-Set Reduction insieme all’applicazione Tag-Set Reduc-tion Computing, che lo incorpora (mostrata in Figure 4.5). Entrambi sono statiscritti nel linguaggio di programmazione Java.

L’applicazione Tag-Set Reduction Computing, prende in input tre file: il primo filecontiene le coppie formate da (tag-set di riduzione, regola di riduzione), il secondofile contiene i tag-set originali da ridurre, ed il terzo file contiene i token. In output,esso restituisce un file contenente la ricostruzione della stringa con i token associatiai tag ridotti dall’algoritmo.

La GUI dell’applicazione e composta in questo modo:

i. una text area per la visualizzazione dei messaggi riguardanti:

a. il caricamento del file formato dalle coppie (tag-set di riduzione, regoladi riduzione),

b. il caricamento del file con i tag-set originari da ridurre,

c. il caricamento del file dei token,

d. il calcolo della riduzione dei tag-set,

e. il caricamento dei token,

f. la ricostruzione della stringa con i token associati ai nuovi tag ridotti,

g. gli errori sollevati dall’applicazione.

ii. un menu per:

a. settare il path del file formato dalle coppie (tag-set di riduzione, regoladi riduzione),

b. settare il path del file coni tag-set originali,

c. settare il path del file con i token.

71

Il Tag-Set Reduction Computing e un’applicazione multithreading, questo perchele applicazioni che utilizzano il multithread sono piu reattive nei confronti degliinput degli utenti in quanto l’interfaccia utente (la GUI o la linea di comando)rimane attiva, mentre le attivita che richiedono un uso intensivo del processorevengono eseguite su thread diversi. Inoltre, il multithread si rivela utile anche perla creazione di applicazioni scalabili, poiche consente di aggiungere thread manmano che aumenta il carico di lavoro.

Le funzioni dell’applicazione hanno associato un thread per la propria esecuzione;la parte logica e la parte dell’interfaccia grafica dell’utente (GUI) hanno entrambedue thread associati per il loro funzionamento. Nella fase di avvio un thread sioccupa di inizializzare e visualizzare la GUI, mentre un’altro thread si occupa dieseguire il kernel dell’applicazione (la logica), in quanto si vuole evitare inutiliattese, come il blocco della GUI e le operazioni che vengono eseguite in modoconcorrente.

Figure 5.2: GUI dell’applicazione Tag-Set Reduction Computing.

72

5.1.5 Applicazione della riduzione del tag-set per il TreeTagger

Il test e stato effettuato su un set di documenti, scritto in lingua inglese, presi dalsito web CoNLL-2009 Shared Task, in particolare a questo link:

http://ufal.mff.cuni.cz/conll2009-st/trial-data.html.

Figure 5.3: GUI dell’applicazione Tag-Set Reduction Computing in esecuzione peril TreeTagger.

73

Tabella di Mapping per il TreeTagger

In Table 4.6 vengono mostrate le regole di associazione al tag in lettura e le regoledi riduzione al tag ridotto.

Table 5.1: Tabella di Mapping per la riduzione del tag-set di TreeTagger.

Tabella di Mapping

Tag in lettura Regola di riduzione Tag ridotto

SENT (SENT |?|!) .? ′′ ′′

! ′′ ′′

− (−| : |@|+ |ˆ|\|/| =) HY PH: ” ”@ ′′ ′′

+ ′′ ′′

ˆ ′′ ′′

\ ′′ ′′

/ ′′ ′′

= ′′ ′′

( (() () ()) ), (, ) ,−− (−−) :DT (DT ) DTCC (CC) CCCD (CD) CDEX (EX) EXFW (FW ) FWIN (IN) INJJ (JJ) JJJJR (JJR) JJRJJS (JJS) JJSLS (LS) LSMD (MD) MDNN (NN) NNNNP (NNP ) NNPNNS (NNS) NNSNPS (NNPS) NNPS

74

Table 5.2: Tabella di Mapping per la riduzione del tag-set di TreeTagger (2).

Tabella di Mapping (cont.)


PDT (PDT ) PDTPOS (POS) POSPP (PRP ) PRPPP$ (PRP$) PRP$RB (RB) RBRBR (RBR) RBRRBS (RBS) RBSRP (RP ) RPUH (UH) UHV B (V B|V D|V H|V V ) V BV D ′′ ′′

V H ′′ ′′

V V ′′ ′′

V BD (V BD|V V D|V HD|V V D) V BDV V D ′′ ′′

V HD ′′ ′′

V V D ′′ ′′

V BG (V BG|V DG|V HG|V V G) V BGV V D ′′ ′′

V HD ′′ ′′

V V D ′′ ′′

V BN (V BN |V DN |V HN |V V N) V BNVDN ′′ ′′

V HN ′′ ′′

V V N ′′ ′′

V BP (V BP |V DP |V HP |V V P ) V BPV DP ′′ ′′

V HP ′′ ′′

V V P ′′ ′′

75

Table 5.3: Tabella di Mapping per la riduzione del tag-set di TreeTagger (3).



V BZ (V BZ|V DZ|V HZ|V V Z) V BZV DZ ′′ ′′

V HZ ′′ ′′

V V Z ′′ ′′

WDT (WDT ) WDTWP (WP ) WPWP$ (WP$) WP$WRB (WRB) WRB

5.1.6 Applicazione della riduzione del tag-set per il POS Tagger diLingPipe

Lo stessa procedura e stata eseguita per il POS Tagger di LingPipe. In questocaso abbiamo ottenuto piu tipologie di risultati.

Figure 5.4: L’applicazione Tag-Set Reduction Computing in esecuzione per ilLingPipe.

76

Tabella di Mapping per LingPipe

In Table 4.7 vengono mostrate le regole di associazione al tag in lettura e le regoledi riduzione al tag ridotto.

Table 5.4: Tabella di Mapping per la riduzione del tag-set di LingPipe.

Tabella di Mapping


? ((?|.|!|; | :) .. ′′ ′′

! ′′ ′′

; ′′ ′′

: ′′ ′′

− (−| : |@|+ |ˆ|\|/| =) HY PH@ ′′ ′′

+ ′′ ′′

ˆ ′′ ′′

| ′′ ′′

= ′′ ′′

/ ′′ ′′

′′ ′′

( (() () ()) ), (, ) ,−− (−−) −−abl (abl|abn|abx|ap$|at| DT

ap|dt|dt$|dti|dts|dtx)abn ” ”abx ” ”ap ” ”ap$ ” ”at ” ”ap ” ”dt ” ”dt$ ” ”dti ” ”dts ” ”

77



Tag in lettura Regole di riduzione Tag ridotto

pp$ (pp$|pn$|pp$$|prp$) PRP$pn$ ′′ ′′

pp$$ ′′ ′′

prp$ ′′ ′′

rb (rb|rn| ∗ |abl|abn|abx|nr) RBrn ′′ ′′

∗ ′′ ′′

abl ′′ ′′

abn ′′ ′′

abx ′′ ′′

nr ′′ ′′

rbr (rbr) RBRrbs (rbs|ql|qlp) RBTql ′′ ′′

qlp ′′ ′′

rp (rp) RPuh (uh) UHvb (vb|be|do|hv) V Bbe ′′ ′′

do ′′ ′′

hv ′′ ′′

vbd (vbd|bed|bedz|hvd) V BDbed ′′ ′′

bedz ′′ ′′

hvd ′′ ′′

vbg (vbg|hvg|beg) V BGhvg ′′ ′′

beg ′′ ′′

vbn (vbn|ben|dod|hvn) V BNben ′′ ′′

dod ′′ ′′

hvn ′′ ′′

79



Tag in lettura Regole di riduzione Tag ridotto

vbp (vbp|bem|ber) V BPbem ′′ ′′

ber ′′ ′′

vbz (vbz|bez|doz) V BZbez ′′ ′′

doz ′′ ′′

wdt (wdt) WDTwpo (wpo|wps) WPwps ” ”wp$ (wp$) WP$wrb (wrb|wql) WRBwql ” ”

5.1.7 Conclusioni

Per confrontare i due sistemi (TreeTagger e POS Tagger di LingPipe), si e fattouso di un modello di verita, messo a disposizione dalla Thirteenth Conference onComputational Natural Language Learning (CoNLL 2009).

I risultati restituiti dal TreeTagger e dal POS Tagger di LingPipe non sonoequivalenti, anche se si e utilizzato l’algoritmo di riduzione, dalle regole del BrownCorpus Tag-Set alle regole del Penn TreeBank Project. La stessa operazione diriduzione e stata fatta anche per le regole del sistema TreeTagge, dopodiche e statopossibile applicare l’algoritmo di validazione con il modello di verita.

Per fare la validazione, l’algoritmo prende in input il file con i valori restituiti dalsingolo sistema (TreeTagger o dal POS Tagger di LingPipe) e il file con il modellodi verita del CoNLL2009. Si confronta ciascun valore presente nella lista dei valoriprodotti dal dal singolo sistema, con ciascun valore del modello di verita; se sonouguali, allora, si incrementa il numero di tag ”presi” e si selezionano i successividue valori, uno dalla lista dei valori prodotti dal dal singolo sistema e l’altro dalmodello di verita, facendo nuovamente il confronto; iterando fino ad avere lettitutti i valori della lista dei valori prodotti dal singolo sistema e confrontati tutticon i valori del modello di verita. Terminata la fase di conteggio dei tag ”presi”,si calcola la Precision, la Recall e la F1-Score.

80

Il calcolo della Precision, della Recall e del F1-Score

Come e stato affermato prima, per valutare[20] entrambi i sistemi (TreeTagger ePOS Tagger di LingPipe), l’operazione di valutazione viene fatta confrontando ivalori prodotti dal singolo sistema, con i valori del modello di verita valido, creatoappositamente da un linguista esperto.

Per fare questo tipo di operazione si utilizzano la Precision, la Recall e la F1-Score(vedere Sezione 6.1 e Sezione 6.2 ), che sono tre comuni classificazioni statistiche,utilizzate in diversi ambiti, come per esempio l’Information Retrieval.

La Precision puo essere vista come una misura di esattezza o di fedelta o di cor-rettezza, mentre la Recall e una misura di completezza. Durante l’attivita diclassificazione, i termini true-positives, true-negatives, false-positives efalse-negatives fanno il confronto dei risultati del classificatore con un testtramite un giudizio esterno (o modello di verita). I termini positivi e negativi siriferiscono alla previsione del classificatore (a volte conosciuto come l’aspettativa),e le condizioni di vero e falso si riferiscono al fatto che la previsione corrisponde algiudizio esterno (noto anche come l’osservazione).

La Precision (P) e la Recall (R), in questo contesto, sono definiti come

P =tag–presi

num–word–tag

e

R =tag–presi

num–tot–tag.

Si ha, che num-word-tag e numero di parole per cui si e scelto un tag, mentrenum-tot-tag e il numero totale delle parole da etichettare.

Siccome entrambi i sistemi, POS Tagger di LingPipe e il TreeTagger, scelgonosempre un tag per ogni parola, si ha la Precision e la Recall uguali.

Infine, si ha la F1-Score (chiamata anche F-Score o F-Measure), che e la misuradell’accura-tezza di un test, la quale considera sia la Precision e sia la Recall diun test per calcolare il punteggio.

Nella Table 4.10 si mostrano i risultati finali ottenuti, dove il numero di token presidal POS Tagger di LingPipe e di parecchio inferiore al numero dei token presidal TreeTagger, differendone di 31; stesso discorso vale per quanto riguarda: laPrecision, la Recall e F1-Score, dove il TreeTagger e notevolmente avanti rispettoal POS Tagger di LingPipe.

81

Table 5.8: Tabella riassuntiva dei risultati finali.

Risultati Finali

- TreeTagger POS Tagger di LingPipe

Tag presi 215 su 219 185 su 219Precision ≈ 99% ≈ 84%

Recall ≈ 99% ≈ 84%F1-Score ≈ 99% ≈ 84%

In conclusione, si puo dire che ci sono delle differenze tra i due sistemi. La primadifferenza sta sicuramente nel processo di tokenizzazione, in quanto e stato utiliz-zato lo standard Penn Treebank Tokenization; la seconda riguarda con molta prob-abilita al corpus utilizzato per costruire il modello del POS Tagger di LingPipe, inquanto i testi utilizzati per l’addestramento sono stati etichettati con il Brown Cor-pus Tag-Set. Tuttavia, anche se e stato implementato un’algoritmo di riduzionedal tag-set originario al tag-set ridotto per aggirare questo problema, i risultatinon sono stati buoni e la differenza che separa i due sistemi e di ben 14 puntipercentuale.

82

Chapter 6

Architettura del sistema

6.1 La progettazione in UML del sistema

L’obiettivo del sistema e quello di riconoscere (in arabo, in inglese e in italiano) leseguenti categorie di entita proprie:

• PERS,

• LOC,

• ORG e

• MISC.

6.1.1 Glossario di Progetto

• API : insieme di procedure disponibili al programmatore.

• NER: sistema che estrae e riconose l’entita proprie da un testo non strut-turato.

• Utente: persona abilitata ad accedere al sistema a qualsiasi titolo o scopo.

• Sistema: insieme di elementi interconnessi tra di loro o con l’ambiente esternotramite reciproche relazioni.

• Regole: insieme di norme prestabilite, espresse sotto la forma di espressioniregolari.

83

• Modello: rappresentazione di un oggetto, che corrisponde alla cosa modellataper il fatto di riprodurne alcune caratteristiche o comportamenti fondamen-tali, espresso sotto la forma di un modello statistico, per esempio un HiddenMarkov Models (HMM).

• Entita proprie o (NEs): identificano chiaramente un elemento da un insiemedi altri elementi, che hanno caratteristiche simili.

6.1.2 Gli attori

I ruoli considerati per gli attori sono:

• Ruolo Utente: e un utente abilitato ad accedere ed ad utilizzare il sistema.

• Ruolo LingPipe: e un sistema che fornisce le API per la linguistica com-putazionale.

• Ruolo Lucene: e un sistema che fornisce le API per il reperimento ed iltrattamento delle informazioni.

• Ruolo JXL: e una libreria per leggere, scrivere e modificare dinamicamentefogli di calcolo Excel.

Figure 6.1: Diagramma degli attori.

6.1.3 Requisiti del sistema

L’analisi dei requisiti rappresenta una delle prime fasi nel ciclo di vita di unprodotto software, lo scopo generale dell’analisi e stabilire che cosa il sistema in

84

questione deve fare. In questo caso il progetto si sviluppera tramite UML. E im-portante e indispensabile a questo punto definire i requisiti funzionali e quello nonfunzionali.

6.1.4 Requisiti Funzionali

ID Descrizione Priorita

RF01 Selezione lingua da parte dell’utente Indispensabile

RF02 Acquisizione di uno o piu testi inseriti dall’utente Indispensabile

RF03 Estrazione delle singole frasi nel/i testo/i Indispensabile

RF04 Estrazione e riconoscimento delle entita proprie (ambigue Indispensabile

e non ambigue) attraverso delle regole

RF05 Riconoscimento delle entita proprie ambigue applicando Indispensabile

un modello stocastico (HMM)

RF06 Applicazione di un filtro per eliminare il rumore presente Indispensabile

(tramite operazioni di stemming e di normalizzazione)

nelle entita proprie

RF07 Eliminazione delle entita proprie doppione e fusione delle Indispensabile

entita proprie riconosciuti

RF08 Salvataggio delle entita proprie in un file Excel Indispensabile

Divisione in sotto-requisiti fuzionali

In base ai requisiti di sistema, precedentemente elencati, e possibile suddividere ilquarto requisito funzionale (RF04), in tre sotto-requisiti:

ID Descrizione Priorita

RF04:01 Si provvede alla preparazione del data set training un Indispensabile

set di notizie prese dall’ANSA con gli opportuni tag

OBI o all’acquisizione di un corpus gia annotato

RF04:02 Si provvede all’addestramento (o all’acquisizione) del Indispensabile

modello del NER, con gli opportuni test di valutazione

RF04:03 Costruzione delle regole, espresse tramite espressioni Indispensabile

regolari

85

Requisiti di prestazione

ID Descrizione

RNF-PRE01 Sistema con quad-core processor da 2 Ghz in su e 8 Gbytes di RAM

RNF-PRE02 Sistema operativo basato su kernel Linux/Unix e Windows Server

RNF-PRE03 Java VM versione 6 o superiore

6.1.5 Requisiti Non-Funzionali

6.1.6 Casi d’Uso

Il diagramma dei Casi d’Uso e il risultato dell’attivita di ingegneria dei requisitied e composto da tre componenti:

• attori : i ruoli assunti da soggetti tramite il sistema.

• casi d’uso: quello che gli attori possono fare con il sistema.

• relazioni : rapporti tra attori e casi d’uso.

Figure 6.2: Diagramma dei Casi d’Uso.

86

6.1.7 Analisi dei punti funzione

La metrica dei punti funzione permette una valutazione funzionale del sistema apartire dalle prime fasi dello sviluppo software, indipendentemente dalle tecnologiehardware/software utilizzate.

Le linee guida del calcolo Function Points (FP) sono oggi standardizzate dall’orga-nismo Internazionale Function Point User Group (IFPUG) e tale misura coinvolgedue aree di valutazione:

• Unadjusted Function Point (UFP): riflette le funzionalita fornite all’utentedell’applicazione.

• Value Adjustement Factor (VAF): valorizza la complessita delle funzionalitagenerali fornite all’utente.

Come passo preliminare e necessario distinguere e classificare le funzionalita fornitedall’utente (e da lui visibili) all’interno di 5 categorie (function types), a loro voltaraggrupabili in due macro aree: funzioni dati e funzioni transazionali.

#In #Out #Query #Ext In #File

RF01 Selezione lingua 1 1 0 1 0

RF02 Acquisizione testo/testi 2 1 0 0 1

RF03 Estrazione frasi dal testo 2 3 0 0 1

RF04 Estrazione e riconoscimento 2 3 0 0 3

delle entita proprie (ambigue

e non ambigue) tramite rego-

le

RF05 Riconoscimento delle entita 2 3 0 0 2

proprie ambigui tramite

modello stocastico (HMM)

RF06 Applicazione Filtro alle 3 3 0 0 1

entita proprie disambiguate

RF07 Eliminazione e fusione 3 3 0 0 1

delle entita proprie doppione

RF08 Salvataggio delle entita 1 1 0 0 1

proprie in un file Excel

La difficolta di realizzazione dei casi d’uso e stata pesata con un coefficientederivante dalla Table 5.1.

A questo punto, supponendo di avere n componenti, il conteggio e totalmente

87

Table 6.1: Tabella dei coefficienti.

Tipologia Valore Min Max

Facile (Valore 1) 1 0 4

Medio (Valore 2) 2 5 7

Difficile (Valore 2) 3 8 20

definito dalla formala seguente:

UFP =n∑

i=1

peso(function(Typei, compli)).

In questo caso particolare si e ottenuto i seguenti risultati:

#In #Out #Query #Ext In #File #Somma #Diffic. #Parz.

RF01 1 1 0 1 0 3 1 3

RF02 2 1 0 0 1 4 1 4

RF03 2 3 0 0 1 6 3 18

RF04 2 3 0 0 3 8 3 24

RF05 2 3 0 0 2 7 3 21

RF06 3 3 0 0 1 7 3 21

RF07 2 3 0 0 1 6 3 18

RF08 1 1 0 0 1 3 2 6

Totale 115

Value Adjustment Factor (VAF)

Una volta determinato il valore dell’UFP, si deve ”raffinare” il conteggio con un fat-tore correttivo, che valorizzi la complessita della funzionalita fornite dall’utente.

Il calcolo del VAF ottenuto, consente di correggere il valore dell’UFP di un 35% edi giungere al calcolo finale dei punti funzione attraverso la seguente formula:

FP = UFP × V AF

Il VAF e determinato in base a 14 caratteristiche del sistema, dette General SystemCharacteristic (GSC), utilizzando al fine di valutare la complessita generale delsistema basandosi su una scala a 6 valori:

0 = non prensene o di nessuna influenza

88

1 = influenza secondaria o poco significante

2 = influenza moderata

3 = influenza media

4 = influenza significante

5 = influenza forte generalizzata

Sommando i singoli valori assegnati alle varie GSC e applicando la seguente formulasi calcola il VAF:

Table 6.2: Valori di aggiustamento dei VAF.

Fi Domanda Peso

1 Il sistema richiede salvataggi e recuperi affidabili? 1

2 Si richiedono comunicazioni di dati? 5

3 Ci sono funzioni di elaborazione distribuita? 0

4 Le prestazioni sono un fattore critico? 5

5 Il sistema funzionera in un ambiente operativo esistente, utilizzato 5

a fondo?

6 Il sistema richiede inserimenti di dati in linea? 4

7 L’inserimento di dati in linea richiede che la transizione si articoli 5

in piu schemi o piu operazioni?

8 I file principali sono aggiornati in linea? 4

9 I dati d’ingresso o di uscita, i file e le interrogazioni sono complessi? 5

10 L’elaborazone interna e complessa? 5

11 Il codice e stato progettato per essere riusabile? 5

12 La progettazione comprende anche conversioni ed installazioni? 1

13 Il sistema e stato progettato per essere installato in piu organizzazioni? 2

14 L’applicazione e stata progettata per facilitare le modifiche e per essere 5

di semplice uso da parte dell’utente finale?

Calcolo dei Function Point (FP):

FP = 115× [0.65 + (0.01× 52)] = 115× 1.17 = 134.55

89

6.1.8 Diagramma delle Attivita

Il diagramma delle attivita (o Activity Diagram) descrive le attivita da svolgere perrealizzare una data funzionalita e puo essere utilizzato durante la progettazione delsoftware per dettagliare un determinato algoritmo. Di seguito vengono mostrati iseguenti diagrammi delle attivita.

i. Diagramma delle attivita del componente principale (vedi Figure 5.3).

Figure 6.3: Diagramma delle attivita del componente principale.

90

ii. Diagramma delle attivita del modulo English NER (vedi Figure 5.4).

Figure 6.4: Diagramma delle attivita del modulo English NER.

91

iii. Diagramma delle attivita del modulo Italian NER (vedi Figure 5.5).

Figure 6.5: Diagramma delle attivita del modulo Italian NER.

92

iv. Diagramma delle attivita del modulo Arabic NER (vedi Figure 5.6).

Figure 6.6: Diagramma delle attivita del modulo Arabic NER.

93

6.1.9 Diagramma dei Componenti

La Figure 5.7 illustra il diagramma dei componenti principale dell’applicazione,senza scendere nei dettagli dei singoli package dell’applicazione. Esso contiene leJRE System Library, il Package NER Multi-language, il Package Arabic NER, ilPackage English NER, il Package Italian NER e le Referenced Libraries.

Figure 6.7: Diagramma dei componenti relativo alle classi del progetto.

94

La Figure 5.8 illustra il diagramma dei componenti del Package NER Multi-language, ovvero il Core Bussiness dell’applicazione. Esso contiene le, in det-taglio, le classi, i metodi e le variabili presenti in esso, assieme alle relazioni fra diesse.

Figure 6.8: Diagramma dei componenti relativo alle classi del Package NER Multi-language.

95

La Figure 5.9 illustra il diagramma dei componenti del Package English-NER. Essocontiene le, in dettaglio, le classi, i metodi e le variabili presenti in esso, assiemealle relazioni fra di esse.

Figure 6.9: Diagramma dei Componenti relativo alle classi del Package English-NER.

La Figure 5.10 illustra il diagramma dei componenti del Package Italian-NER. Essocontiene le, in dettaglio, le classi, i metodi e le variabili presenti in esso, assiemealle relazioni fra di esse.

Figure 6.10: Diagramma dei Componenti relativo alle classi del Package Italian-NER.

96

La Figure 5.11 illustra il diagramma dei componenti del Package Arabic-NER.Esso contiene in dettaglio: le classi, i metodi e le variabili presenti in esso, assiemealle relazioni fra di esse.

Figure 6.11: Diagramma dei Componenti relativo alle classi del Package Arabic-NER.

6.1.10 Gestione requisiti non-funzionali

Il sistema non possiede nessuna architettura di tipo client/server, server appli-cation o desktop application, in quanto esso e un componente, che deve essereinserito all’interno dell’estrattore terminologico TermExtractor (una web applica-tion), percio la sua architettura deve essere uguale all’estrattore terminologicoTermExtractor e deve essere eseguibile sul Server.

Requisiti non-funzionali lato Server

Il componente deve permettere di avere piu connessioni simultanee, le quali nonhanno bisogno di fare operazioni di lettura/scriittura sul server, ad eccezione delfile con i risultati prodotti dal componente stesso. Infine, il componente non habisogno di memorizzare nessun file o archivio.

97

La configurazione hardware consigliata e la seguente:

• Processore Intel CPU i7 4.00Ghz con 8MB di cache di secondo livello.

• Ram 16GB DDR3.

• Hard Disk da 500MB ciascuno ad alta velocita e connessi in Raid 2.

• Interfaccia Ethernet a 1Gbit.

• Sistema Operativo Linux.

• Java versione 6 o superiore.

98

6.2 Schema dell’architettura

Il sistema, progettato ed implementato, e un component, che deve essere inseritoall’interno dell’estrattore terminologico TermExtractor, mantenendo e rispettando,a sua volta, il work-flow dello sistema principale; esso aggiunge la funzione diestrazione e riconoscimento delle entita proprie provenienti da uno o piu testi datiin input, scritti nelle seguenti lingue:

• inglese,

• italiana,

• araba;

ed infine salvandoli sul file in formato Excel.

Come descritto in precendenza, per poter mantenere il work-flow del sistema prin-cipale, il component possiede l’architettura a pipeline. A sua volta, esso contieneall’interno tre moduli, che eseguono lo stesso compito, ma con delle leggere dif-ferenze di funzionalita, le quali verrano poi spiegate, con maggiori dettagli.

Il sistema funziona in questo modo: in input prende il tipo della lingua scelta, daparte dell’utente, e il testo, il quale contiene le news nella lingua selezionata. Inbase alla lingua scelta si attiva il modulo NER per quella lingua, con l’istanziazionedi un thread per la gestione dello stesso. L’output, che restituisce il sistema, ecostituito da una lista, salvata su file Excel, di entita proprie etichettate con il tagspecifico (PERS, LOC, ORG e MISC).

La sua architettura, in generale, puo essere sintetizzato con lo schema in Figure5.12, detta Macro del sistema NER, con la quale si mostra l’architettura dell’interocomponent di estrazione terminological NER Multi-Language (English NER, Ital-ian NER e Arabic NER).

99

Figure 6.12: Schema dell’architettura Macro del sistema NER Multi-Language.

Il discorso vale per i singoli moduli NER, i quali possegono l’architettura a pipeline(anche se tutti e tre i moduli NER differiscono in alcune funzioni). Essi seguonoessezialmente quattro step, che sono:

• Sentence Extraction,

• Grammar Configuration,

• Filter,

• Merge.

Tutti e quattro gli step saranno ampiamenti descritti nelle sezioni successive.

100

6.2.1 Estrazione delle frasi

La prima fase, quella di Sentence Extraction[5], non e uguale per tutti e tre imoduli NER.

Il component, prima di iniziare ad estrarre e a riconoscere le entita proprie, applicala funzione per estrarre le frasi da un testo, dove nel caso del modulo Arabic NER,si utilizzano le regole per il loro riconoscimento, mentre nel caso del modulo EnglishNER e Italian NER, si utilizza un modello euristico1, ovvero , ovvero un statisticallanguage model, sempre per il loro riconoscimento. In entrambi i casi, tale compitoviene eseguito leggendo un testo in input ed estraendo la frase, quando incontraun ”confine” della frase. Un esempio potrebbe essere, nel caso della lingua inglese:il punto (”.”), il punto esclamativo (”!”), ed il punto esclamativo (”?”), che sonotipicamente i caratteri di delimitazione (o di ”confine”) di una frase, analogamenteal carattere di spazio che separa i token.

Figure 6.13: Schema per l’estrazione della frase da un testo tramite un modelloeuristico.

Il risultato che si ottiente da questa operazione e una lista di frasi, le quali sono piuche sufficienti per comprendere il contenuto oppure per estrarre le entita propriepresenti in ciascuna frase del testo stesso.

6.2.2 Grammar Configuration

Nella fase per la Grammar Configuration sono state costruite due tipologie di classiper le regole e differiscono nei tre moduli NER. Tali classi sono:

- Classi delle regole non-ambigue.

- Classi delle regole ambigue.

La prima classe contiene tutte le regole non-ambigue, per l’estrazione e l’identificazionedelle entita proprie, le quali vengono associate univocamente allo specifico tag

1Tale modello euristico e lo stesso, che viene utilizzato per trovare i token in un testo.

101

(PERS, LOC, ORG e MISC). Il principio della non-ambiguita si basa esclusiva-mente sulle trigger word all’iterno della regola. Il compito della trigger word equello di far attivare la regola, ovvero il processo di estrazione e riconoscimentodelle entita proprie legate alla stessa, nel caso in cui, all’interno del testo in input,si riscontri la presenza di una o piu trigger word. Un esempio di regola non-ambigua, che si puo citare e quella per le entita proprie di tipo PERS, dove siha come prefisso la sigla (Mr.|Mrs.|Miss.) prima del nome e/o cognome dellapersona.

Mentre, la seconda classe contiene tutte le regole ambigue, per l’estrazione el’identificazione delle entita proprie, i quali non hanno nessuna associazione uni-voca, per questo bisogna applicare un algoritmo di disambiguazione che analizzail contesto delle probabili entita proprie estratte e le associa univocamente, con iltag specifico (PERS, LOC, ORG e MISC). In questo caso, le regole ambigue, chesono state prese in considerazione sono quelle, che si basano sulla CapitalizzazioneConvenzionale[15] delle parole.

Capitalizzazione Convenzionale

Nei sistemi ortografici europei, questo caso di distinzione dell’alfabeto e fatto inbase ai contesti, e come viene mostrato secondo la Table 5.3. Come eccezione alcriterio di confidenza adottato, si prova a ”filtrare” le parole capitalizzate estrattee riconosciute come entita proprie, ma che in verita non lo sono.

Nell’inizio frase, se una parola inizia una frase o segue la punteggiatura, essa ecapitalizzata e puo essere considerata dal sistema come un’entita propria, oppureessa viene trovata sulla lista delle parole comunemente frequenti. Ciascuna lingua,in questo caso l’italiano e l’inglese, contiene tutte le parole non capitalizzate piucomunemente frequenti, chiamate anche Stop Word.

Sia nella lingua inglese e sia nella lingua italiana, i nomi comuni non sono capitaliz-zati, presentando per il criterio adottato una sfida, infatti nomi come euro, dollaronon vengono identificati come nomi di persona, ma bensı vengono identificati comenomi comuni.

I titoli personali (come Dr., Prof., etc) nella lingua inglese sono convenzionalmentecapitalizzati, mentre nella lingua italiana non sempre sia usa questa convenzione,in quanto non e obbligatorio. I titoli spesso o sempre appaiono immediatementeprima del nome della persona.

Gli acronimi, sia nella lingua inglese e sia nella lingua italiana, sono convenzional-mente capitalizzate, anche se possono degradere le perfomance nella fase di es-

102

trazione ed identificazione.

Nella lingua inglese le entita di forma aggettivale, come la nazionalita o come lareligione (per esempio le parole American e Islamic) sono capitalizzate e entrambe,secondo il CoNLL e BBN vengono identificate come di tipo MISC. Mentre nellalingua italiana, a differenza della lingua inglese, le forme aggettivali non sonocapitalizzate, come la nazionalita o come la religione (per esempio le parole italianae cattolica), invece, la forma nominale della nazionalita e capitalizzata.

Table 6.3: Tabella riassuntiva per l’applicazione della Capitalizzazione Conven-zionale, come regola, nella valutazione dei linguaggi. S = si capitalizzata; N = noncapitalizzata; Q = qualche volta.

Capitalizzata? Inglese ItalianoPiu entita Y YInizio frase Y YNomi comuni N NTitoli personali Y QAcronimi Y YEntita aggettivali Y N

Disambiguazione delle entita proprie

Per effettuare la disambiguazione delle entita proprie, estratte con le regole am-bigue, si e deciso di applicare l’approccio basato su modello stocastico (HMM), inquesto modo si e potuto disambiguarli ed associargli un unico tag e ben specifico.L’utilizzo di questo approccio necessita di un modello, per questo motivo e statonecessario implementare un’applicazione, che addestri il modello e testi a livello diperfomance il modello.

X-NERVal

Per l’addestramento del modello si e progettato ed implementato un’applicazione,detta X-NERVal (mostrata in Figure 5.14), la quale e stata scritta nel linguag-gio di programmazione Java, per poi utilizzarlo, come parser, LingPipe. Taleapplicazione restituisce in output:

• Un determinato numero di modelli (sotto forma di file binario), dove il nu-mero dei modelli viene specificato in input, in base al numero di folds, concui i dati di addestramento vengono divisi.

103

• Le perfomance2 della validazione dell’addestramento fatti su ciascun modello.

• Le perfomance totali ottenuti da tutti i modelli.

L’applicazione stessa possiede una GUI, suddivisa in:

• una text area per la visualizzazione dei messaggi riguardanti:

– i file letti da input,

– i valori dei parametri inseriti,

– i token ed i tag letti,

– i tipi di tag trovati,

– il numero di token e di frasi letti,

– i valori di Precision, Recalll e F1-Score per ciascun modello e di tutti imodelli combinati,

– gli errori sollevati dall’applicazione.

• una text field per l’inserimento del numero di fold da parte dell’utente,

• una text field per l’inserimento della lunghezza n-gram da parte dell’utente,

• una text field per l’inserimento del numero chars,

• una text field per l’inserimento del rapporto di interpolazione in formatodecimale,

• una text field per l’inserimento del valore (true/false) per l’utilizzo didizionari,

• una text field per l’inserimento del valore (true/false) per l’inclusione dientita di tipo MISC,

• un menu per:

– settare il path del corpus,

– settare il path dei gazetteer (LOC, ORG e PERS).

2Per perfomance si intende i valori di Recall, di Precision e di F1-Score.

104

Figure 6.14: GUI per l’addestramento e la cross-validation del modello.

X-NERVal e implementato in multithreading, ciascuna funzione ha associato unthread per la propria esecuzione. La parte logica e la parte GUI hanno entrambedue thread associati per il funzionamento. Nella fase di avvio dell’applicazione unthread si occupa di inizializzare e visualizzare la GUI, mentre un’altro thread sioccupa di eseguire il kernel dell’applicazione (la logica); in questo modo si evitanoattese inutili (o il blocco della GUI) e le operazioni stesse possono essere eseguitein modo concorrente.

Come mostra l’immagine l’applicazione, attraverso la sua GUI, prende in input iseguenti parametri3:

• N-Gram: si intende la lunghezza degli n-gram (sequenza contigua di n ele-menti di una data sequenza di testo o discorso).

• Num-Chars : e il numero totale di caratteri unici.

3Tali parametri sono inizialmente configurati con dei valori di default.

105

• Interpolation-Ratio: e il rapporto di interpolazione lingua-modello.

• Number-of-Analyses-Rescored : e il numero di chunking sottostanti rivalutati.

• Including-MISC-Entity-Type: si includono le entita di tipo MISC.

• Use-Dictionary : si utilizza uno o piu dizionari nella fase di training delmodello (vero o falso).

• Directory-Corpus : il percorso fisico del corpus per il training del modello.

• Directory-Gazetteer : il percorso fisico dei gazetter per il training del modello.

• Number-Folds : il numero di fold, dove ciascun fold e associato ad un modello.

L’applicazione e molto semplice, in quanto i passi, che effettua sono:

1. Lettura dei parametri descritti sopra e del corpus assieme ai gazetteer, seabilitato.

2. Caricamento del corpus ed identificazione dei tipi delle entita proprie.

3. Verifica se la sequenza dei tag associati ai token e legale.

4. Assemblamento delle frasi dai token letti.

5. Addestramento di uno o piu modelli applicando il metodo CharLmRescor-ingChunker (vedere Sezione 4.3.3 ).

6. Salvataggio dei modelli appena addestrati in file binari.

7. Calcolo delle perfomance per ciascun modello e delle perfomance totali pertutti i modelli.

6.2.3 Filter

Nella fase Filter, si applicano dei filtri a quelle entita proprie estratte dalle regoleambigue oppure senza ricorrere ad esse analizzando l’intera frase, e poi disam-biguarle tramite modello. Tale funzione e composta da 2 step principali, comemostrato in Figure 5.10, che sono:

1. Eliminazione del rumore attorno alle entita proprie.

2. Eliminazione delle eventuali Stop Word presenti nelle entita proprie.

106

Figure 6.15: Schema generale degli step della funzione Filter.

Nota: inizialmente nella fase Filter, essa prevedeva 3 step principali; lostep eliminato e quello di Normalizzazione e stemming delle entita propriein quanto non migliorava le perfomance finali del A-NER e in alcuni casi lestesse peggioravano.

Figure 6.16: Schema generale (vecchio) degli step della funzione Filter.

Il primo step e uguale per tutti e tre i moduli, in quanto si va ad eliminare ilrumore attorno alle entita proprie (all’inizio ed alla fine), come la punteggiaturaed i caratteri speciali presenti in esse, attraverso delle regole costruite ad hoc perciascun modulo NER.

Infine, il secondo step e uguale per tutti e tre i moduli, in quanto si vanno ad elim-inare (o ”filtrare”) le eventuali Stop Word, presenti all’interno delle entita proprie.Esse sono quelle parole che, per la loro alta frequenza in una lingua, sono di solitoritenute poco significative nei sistemi di Information Retrieval e nei sistemi diInformation Extraction. Alcuni esempi di Stop Word sono la punteggiatura, icaratteri speciali, le preposizioni, le congiunzioni, gli avverbi, etc. Esse risiedonoin un file su formato di testo semplice e sono differenti per ciascun modulo NER.Queste vengono caricate ogni qual volta, che si esegue il task di estrazione e ri-conoscimento delle entita proprie, da un insieme di documenti.

6.2.4 Merge

Una volta terminata la fase Filter, si procede nell’eliminazione delle entita propriedoppione, in quanto le stesse entita proprie possono essere estratte e riconosciutesia dalle regole ambigue e sia dalle regole non-ambigue. Per quest’ultima oper-azione, si applica un proprio algoritmo di sub-string searching, che controlla seesistono entita proprie trovate con le regole ambigue, che sono doppioni; se si ver-fica la condizione, allora le entita proprie vengono cancellate, altrimenti no. Unacosa fondamentale dell’algoritmo, e che assegna una maggiore importanza alle en-tita proprie trovate con le regole non-ambigue, rispetto alle entita proprie trovate

107

con le regole ambigue, in quanto i primi sono piu affidabili e veritiere rispetto aisecondi.

Dopodiche, si passa allo step successivo, ovvero la fusione delle entita proprieestratte e riconosciute, con le regole non-ambigue e con le regole ambigue, le qualipoi vengono tutte salvati su un file Excel assieme al loro tag specifico (PERS,LOC, ORG e MISC).

108

6.3 Il modulo English NER

Per la progettazione ed implementazione del modulo English NER[5] (E-NER),non si e fatto uso di un corpus in Inglese, in quanto si e trovato sul sito web diLingPipe un modello addestrato, usando le news, riguardanti la cronaca inglese emondiale.

In detttaglio, con lo schema in Figure 5.15, si mostra l’architettura sintetizzata delmodulo E-NER, la quale viene chiamata Micro del sistema NER.

Figure 6.17: Schema dell’architettura Micro del sistema NER Multi-Language (E-NER).

109

6.3.1 Differenze del modulo E-NER

Per il riconoscimento del ”confine” della frase all’interno di un testo viene utilizzatoun modello euristico, ovvero un statistical language model. Tale modello euristiconon e stato necessario addestrarlo, in quanto il sito web di LingPipe, ne metteuno a disposizione gratuitamente on-line.

Per il riconoscimento delle entita proprie con i tag PERS, LOC, ORG e MISCsono state costruite entrambe le due tipologie di classi di regole (vedere Table 5.3)e per la disambiguazione delle entita ambigue si e utilizzato un modello, il quale escaricato gratuitamente dal sito web di LingPipe[5].

Table 6.4: Elenco delle regole (ambigue e non-ambigue) utilizzate per la configu-razione della grammatica.

Regole non-ambigue Regole ambigue

email parole con le iniziali maiuscolenumeri interinumeri percentualinumeri telefonicidataora in formato CET e AM/PMpersoneorganizzazioni

Le operazioni che vengono svolte, durante la fase Filter, nel caso del modulo E-NER, sono l’eleminazione del rumore attorno alle entita proprie ed eventuali StopWord.

110

6.4 Il modulo Italian NER

Per la progettazione ed implementazione del modulo Italian NER (I-NER), si efatto uso di un corpus in italiano (annotato dal sottoscritto), perche non c’eranessun sito, che mettesse a disposizione tale risorsa gratuitamente. La costruzionedi questo corpus e stata fatta raccogliendo, dai principali siti italiani di notizie, lenotizie riguardanti la politica, la finanza, l’attualita e lo sport. Esso contiene circa70K token contrassegnati in formato CoNLL per:

• la persona,

• la localita,

• l’organizzazione ed

• i vari tipi di entita.

I dati sono stati raccolti da una varieta di fonti:

Fonte Rapporto in %

http://www.ansa.it/ 44.8%http://www.primopiano.it 25.5%

http://it.msn.com/ 6.6%http://www.portalsport.it/ 5.4%

http://www.adn.it/ 5.4%http://affariitaliani.libero.it/ 1.9%Altri newspapers e magazines 12.3%

Le prime entry del file sono le seguenti:

Bernanke B − PERSha Ofatto Osaltare Oil Otappo Osui Otitoli B −MISCdi I −MISCStato I −MISC: Oi OBtp B −MISCai O

111

livelli Opost-elettorale O. ODa Oquando Ola OFederal B −ORGReserve I −ORG...

Con lo schema in Figure 5.16, si mostra l’architettura sintetizzata del moduloI-NER, la quale viene chiamata Micro del sistema NER.

Figure 6.18: Schema dell’architettura Micro del sistema NER Multi-Language (I-NER).

112

6.4.1 Differenze del modulo I-NER

Per il riconoscimento del ”confine” della frase all’interno di un testo viene utilizzatoun modello euristico, ovvero un statistical language model. Tale modello euristiconon e stato necessario costruirlo, in quanto il sito web di LingPipe, ne mette unoa disposizione gratuitamente on-line.

Lo stesso discorso vale per questo modulo, dove per il riconoscimento delle entitaproprie con i tag PERS, LOC, ORG e MISC sono state costruite entrambe le duetipologie di classi di regole (vedere Table 5.5) e per la disambiguazione delle entitaambigue si e utilizzato un modello stocastico (HMM), il quale e stato opportuna-mente addestrato sul proprio corpus, attraverso l’applicazione X-NERVal, la qualee stata dettagliatamente descritta precedentemente.

Table 6.5: Elenco delle regole, ambigue e non-ambigue, utilizzate per la configu-razione della grammatica.

Regole non-ambigue Regole ambigue

email parole con le iniziali maiuscolenumeri interinumeri percentualinumeri telefonicidataora in formato CET e AM/PMpersoneorganizzazioni

Le operazioni che vengono svolte durante la fase Filter, nel caso del modulo I-NER,sono:

• l’eliminazione del rumore attorno alle entita proprie

• e l’eliminazione di eventuali Stop Word riconosciute come entita proprie.

113

6.5 Il modulo Arabic NER

Per la progettazione ed implementazione del modulo Arabic NER (A-NER), si efatto uso di un corpus in arabo (ANERCorpus[32]) disponibilie on-line4 gratuita-mente, contenente circa 150K token contrassegnati in formato CoNLL per:

• la persona,

• la localita,

• l’organizzazione ed

• i vari tipi di entita.

Sempre on-line, oltre al corpus, sono disponibili altre risorse; tra cui un insiemedi gazetteer in arabo (ANERGazet[32]). In esso vi e una raccolta di tre tipi digazetteer:

• sedi (continenti, paesi, citta, etc),

• persone (nomi di persone) ed

• organizzazioni (societa, squadre di calcio, etc).

I dati sono stati raccolti da una varieta di fonti:

Fonte Rapporto in %

http://www.aljazeera.net/ 34.8%http://www.raya.com/ 15.5%

http://ar.wikipedia.org/ 6.6%http://www.alalam.ma/ 5.4%

http://www.ahram.eg.org/ 5.4%http://www.alittihad.ae/ 3.5%

http://www.bbc.co.uk/arabic/ 3.5%http://arabic.cnn.com/ 2.8%

http://www.addustour.com/ 2.8%http://kassioun.org/ 1.9%

Altri newspapers e magazines 17.8%

Le prime entry del file sono le seguente5:

B − LOC �HPñ

®º

K @Q

¯

O X)

4Dal sito http://www1.ccls.columbia.edu/∼ybenajiba/downloads.htm.5Le parole arabe sono tipicamente scritte da destra verso sinistra.

114

O H.

O ( @

O áÊ« @

B −ORG XAm��' @

I −ORG �é«A

J�

I −ORG �H@PAJ�Ë@

O ú

¯

B − LOC AJK AÖÏ

@

. . .

I dizionari (noti anche come gazetteer) sono solo liste di nomi propri. Nell’esempioche segue, le prime entry del dizionario sono:

====

(ASIA) AJ�@

====

àXP@

àXPB@

****

àñÊj. «

àAÔ«

YK. P@

A�JÓQË@

½K. ñ�

�Ë@

��Qk.

ZA�P P

. . .

Con lo schema in Figure 5.17, si mostra l’architettura sintetizzata del moduloA-NER, la quale viene chiamata Micro del sistema NER.

115

Figure 6.19: Schema dell’architettura Micro del sistema NER Multi-Language (A-NER[6]).

6.5.1 Differenze del modulo A-NER

Le regole costruite per l’estrazione delle frasi effettuano un processo basato sulriconoscimento del ”confine” di una frase, le quale possono essere identificate at-traverso la presenza di punteggiatura, come: il punto di fine frase (”.”), il puntoesclamativo (”!”) ed il punto interrogativo (”?”), e il carattere di new line (”n”).

Le regole costruite per la configurazione della grammatica non sono per il riconosci-mento delle entita proprie con i tag PERS, LOC e ORG, ma soltanto per il ri-conoscimento di entita proprie con il tag MISC (vedere in Table 5.6).

116

Table 6.6: Elenco delle regole (solo non-ambigue) utilizzate per la configurazionedella grammatica.

Regole non-ambigue

emailnumeri interinumeri percentualinumeri telefonicidataora in formato CET e AM/PM

Per il riconoscimento delle entita proprie con i tag PERS, LOC, ORG (e ancheMISC) e stato utilizzato il modello sull’intera frase in input. Per l’addestramento ela validazione del modello si e utilizzata l’applicazione X-NERVal, la quale e statadettagliatamente descritta precedentemente, ma non si e fatto uso dei gazetteer(dizionari), durante la sua fase di addestramento, perche la Precision non aumen-tava.

Le operazioni che vengono svolte durante la fase Filter, nel caso del modulo A-NER, sono l’eliminazione del rumore attorno alle entita proprie e l’eliminazione dieventuali Stop Word riconosciute come entita proprie.

117

Chapter 7

Valutazioni

7.1 Accuratezza, Precision, Recall e F1-Score

La valutazione di un sistema NER viene direttamente fatta in base al confrontocon un modello di verita ed i risultati forniti dallo stesso sistema.

I risultati possono essere formulati con le seguenti quantita:

- Classe predetta

- Positivo Negativo

Classe Positivo TP (true positives) FN (false negatives)

reale Negativo FP (false positives) TN (true negatives)

TP (true-positives): elementi etichettati correttamente come appartenenti allaclasse positiva.

FP (false-positives): elementi etichettati erroneamente come appartenenti allaclasse positiva.

FN (false-negatives): elementi etichettati erroneamente come appartenenti allaclasse negativa.

TN (true-negatives): elementi etichettati correttamente come appartenenti allaclasse negativa.

Di norma, i parametri utilizzati in questo ambito sono tre: Precision, Recall eF1-Score.

Definizione. La Recall e la percentuale di istanze realmente positiveclassificate come positive, P = TP

(TP+FN) , ed e una misura di completezza.

118

Definizione. La Precision e la percentuale di predizioni positive cor-rette, P = TP

(TP+FP ) , ed e una misura di correttezza.

Definizione. Nella statistica F1-Score (F-Measure o F-score) e usatocome misura per l’accuratezza di un test.

F1-Score prende in considerazione sia la Precision e sia la Recall. L’indice puoessere visto come la media pesata tra Precision e Recall, e ha connotazione positivaquando tende a 1 e connotazione negativa quando tende a 0, oppue essa puo essereinterpretata come la media pesata della Precision e della Recall, dove un F1-Scoreraggiunge il suo punteggio migliore a 1 ed il suo punteggio peggiore a 0.

F1-Score e definito come

F11 = 2 · (PR ·RC)

(PR +RC).

Un’ulteriore misura e l’Accurattezza.

Definizione. L’Accuratezza e la percentuale di istanze sia positivesia negative classificate correttamente, P = (TP+TN)

(TP+TN+FP+FN).

1Definizione abbreviata di F1-Score.

119

7.2 Valutazione delle prestazioni

I criteri di valutazione delle prestazioni utilizzati per questo progetto, per unalettura analitica dei risultati ottenuti, sono stati fatti prendendo come spuntoquelli di Shaalan & Raza[18]. Questi sono:

• Eccellente = 90-100%.

• Buona = 80-89%.

• Discreto = 75-79%.

• Sufficiente = 65-74%.

• Scarso ≤ 64%.

Per i risultati ottenuti dal component di estrazione terminological NER Multi-language bisogna fare una distinguinzione in base alla lingua, ovvero inglese, ital-iano ed arabo.

Nei paragrafi che seguono, vengono mostrati alcuni esempi di esecuzione per cias-cuno dei tre moduli (E-NER, I-NER e A-NER), all’interno del component di es-trazione terminological NER Multi-language.

120

Esempio di esecuzione del modulo A-NER

The Prime Minister stunned Nick Clegg and Ed Miliband by telling them in aphone call this morning that it was time to bring months of talks to a head. MrCameron will table proposals on Monday for a Royal Charter to set up a new bodyto monitor a beefed up regulator. Newspapers would face fines of up to 1 millionand be forced to print prominent apologies by the regulator. However, with Labourand the Liberal Democrats arguing for a tougher system to be embedded in law,Mr Cameron does not appear to have the votes in the Commons to win his way.Cristina Fernandez de Kirchner made the comments last night as Argentinianscelebrated the surprise election of Cardinal Jorge Mario Bergoglio, the 76-year-old Archbishop of Buenos Aires, to succeed the retired Benedict XVI. The Timesrevealed last night that Lord Ahmed of Rotherham. The UK bank bond issues fallsharply. Why Intel Corporation (INTC) deserves to be bought, now. The AppleInc. (AAPL), Advanced Micro Devices, Inc. (AMD).

Figure 7.1: Output prodotto dal modulo E-NER sul testo in input sopra.

121

Esempio di esecuzione del modulo I-NER

Fri Mar 29 11:44:00 CET 2013 Inflazione: a marzo frena a 1,7% Istat, sestorallentamento, effetto decelerazione carburanti (ANSA) - ROMA, 29 MAR - Amarzo l’inflazione rallenta ancora, con la crescita dei prezzi al consumo fermaall’1,7%, dall’1,9% di febbraio. Si tratta della sesta frenata consecutiva, dovutasoprattutto alla decelerazione annua dei carburanti. Lo rileva l’Istat, si tratta deltasso piu’ basso da novembre 2010. Su base mensile il rialzo e’ dello 0,3%. Amarzo i prezzi dei prodotti acquistati con piu frequenza rincarano del 2% su baseannua, un tasso superiore all’inflazione (1,7%), in frenata rispetto a febbraio. FriMar 29 11:39:00 CET 2013 Fisco: Befera,11 mld rimborsi Iva imprese Letteraa direttori regionali per accelerare liquidazioni (ANSA) - ROMA, 29 MAR - Nel2013 l’Agenzia delle Entrate punta a erogare alle imprese rimborsi Iva in contofiscale ”per un ammontare complessivo di 11 miliardi”. Cosı il direttore AttilioBefera in una lettera, in cui invita i direttori regionali ”a dedicare ogni risorsautile alla liquidazione dei rimborsi nei prossimi 4 mesi”. ”Il volume dei crediti neiconfronti della p.a. e i lunghi tempi di pagamento, rischiano di compromettere -dice - livelli occupazionali e sono un ostacolo alla crescita”.

Figure 7.2: Output prodotto dal modulo I-NER sul testo in input sopra.

122

Esempio di esecuzione del modulo A-NER

H. AJ. K.áK

Q�j.®�K YªK. , úÎ

�J�¯ ñ

�®�Ë øX

@ AÜØ

��

��ÓYK. 86

�è QÖÏ @ ú

k ø

PAj

�JK @ Q�j.

®�K

¬Yî

�D�@

PA�� B@ð áKQk. AêÖÏ @

��k.

à@

àñ¢

��A

K ÈA

�¯ I. Êg ú

¯ð .

�éÖÞ�AªËAK.

áKYË@ á»P Q®

m×ð úÎ�Ó

éÊ

g@YÓ ©JÔg. úÎ«

�é

�PAªÖÏ @

�èQ¢J� I.

�®« , ø

Qº�ªË@

©

JÓ PA¢Ó É

g@X

�èXAJ

�®Ë @ ú

æJ.Ó Qm.

¯

¼XPð�éKBð

àA¾� áÓ

�HA

JÖÏ @ Ñ

¢

J�

��k.

©

KAJË A

®Ê

g

�éJk. PA

jÊË @QK

Pð ,à@ñKA

�K. . . . é

�KAK. @ñK. ð

�éJ»

Q�Ó B@

�é�A

mÌ'@

�H@ñ

�®Ë@ H. Aj�

�AK.

á�J. Ë A¢Ó�

I�. �Ë@ ÉK. A¿ ú

¯

�èQëA

¢Ó

àA

�J�

�A

ª

¯ AK.

�éK. Q¢

�ÖÏ @

�é£Qå

��.

�éJ

KA

Jm.Ì'@

�HA

�®J

�®j

�JË @

�èP@X@

��

KP ÈA

�¯ñ.J. K

Yª

�JË @

�é�PAÒÖß. AêË

�HAÓAî

�E@ YªK.

�éKBñË@ áÓ

àAÖÏQ�. Ë @ Q

�®ÖÏ

�èQ��Ó @ñÒ

¢

�

�éKBñË@

àA¾� áÓ �

m�

��

é KAÖ

�ßC

�Kð ú

�æ

KAÓ

á�K. hð@Q��K AÓ

à@

ÉK. A¿

ÑîE @

àðY

�®�JªK

á�JÊjÖÏ @àA¾�Ë@ áÓ

�éª�

��

��C£A

K.

àñJ. Ë A¢� Ñî

E @ úÍ@

@Q�

��Ó , ÐñJË @

.�éJ»

Q�Ó B@

�H@ñ

�®Ë@ øYË

àð Qj.

�Jm×

Figure 7.3: Output prodotto dal modulo A-NER sul testo in input sopra.

123

7.2.1 Valutazione delle annotazioni con ENAMEX Named Entities

Attraverso la gestione dei parametri di input elencati nella Sezione 5.2.2 e possibilequantificare la qualita del modello, prodotto durante la fase di addestramento.Dal momento, che la complessita del modello e un parametro importante datal’intensita computazionale (sia in fase di creazione, che in fase operativa) puo esserebuona pratica eseguire un ciclo di valutazione piu volte variando, per esempio, ilnumero di fold prima di iniziare la fase di addestramento (e di valutazione), inmodo da poter facilmente individuare il modello, che ha ottenuto il punteggio piualto.

Infatti, per questo scopo l’applicazione X-NERVal e sia dotata di una interfacciagrafica, per il monitoraggio dei risultati (mostrata in Figure 6.2) e contestualmenteil/i modello/i viene/vengono salvato/i su file, e sia dotata, nella parte in bassodell’interfaccia, di un piccolo pannello per l’aggiustamento dei parametri, i qualisono stati accennati nella Sezione 6.2.2.

Per ogni ciclo di addestramento-valutazione vengono mostrati, per ciascuna delle4 tipologie (PERS, ORG, LOC e MISC), gli indici di Precision, di Recall e diF1-Score; ed infine la combinazione dei valori degli indici per tutte le 4 tipologie,permettendo cosı una visione migliore dei risultati ottenuti.

124

Figure 7.4: Istantanea dell’applicazione X-NERVal durante le fasi di addestra-mento e di cross-validation (valutazione).

Sia in Table 7.1 e sia in Table 7.2 sono riportati gli indici di Precision, di Recalle di F1-Score relativi all’iterazione con il punteggio miglior, che hanno prodotto imodelli, poi utilizzati nei moduli I-NER e A-NER, per il component di estrazioneterminological NER Multi-language.

Le perfomance migliori ottenute, sono state eseguite su una configurazione da 4-fold di cross-validation ed utilizzando, come sistema di annotazione, quella basatasul sistema BIO, il quale e stato ampliamente descritto nella Sezione 4.3.3. Inciascuna fold si sono utilizzate una parte dei dati di addestramento, provenienti davarie fonti di notizie (vedere Sezione 6.4, per la lingua italiana, e vedere Sezione6.5, per la lingua inglese); mentre la parte restante dei dati di addestramento,vengono utilizzati per la valutazione.

Inoltre, dalle due tabelle, si puo vedere che i modelli basati sul character-gramlanguage offrono dei buoni risultati sfruttando come tipo di annottazione quellobasato sul sistema BIO. L’utilita dei character-based-grams sono stati dimostratianche altrove (Wilbur et al., 1999; Vasserman, 2004; Townsend et al., 2005). Come

125

e stato descritto precedentemnte nella Sezione 4.3.3, essi usano un modello stocas-tico (HMM), il quale e particolarmente adatto, in quanto permette il token-internalfeatures, per essere poi combinato con il contesto del token.[22]

Table 7.1: Risultati della valutazione per la lingua araba.

LOC 0, 799 0, 826 0, 812PERS 0, 741 0, 756 0, 748ORG 0, 672 0, 528 0, 600MISC 0, 691 0, 648 0, 669

Combinate 0, 747 0, 722 0, 734

Table 7.2: Risultati della valutazione per la lingua italiana.

LOC 0, 900 0, 829 0, 863PERS 0, 671 0, 815 0, 736ORG 0, 784 0, 753 0, 768MISC 0, 815 0, 843 0, 829

Combinate 0, 786 0, 799 0, 792

7.2.2 Valutazione del component di estrazione terminological NERMulti-language

Il modo in cui Precision e Recall vengono tipicamente calcolati (vedere ancheSezione 7.1 ) e quello di misurare le entita l’una contro l’altra. In questo ambito,la Precision e la Recall, vengono calcolati in base alla prima definizione sui cri-teri di corrispondenza. Ad esempio: devono essere in una corrispondenza esatta(exact match)? C’e una sovrapposizione della corrispondenza con tutti (Any Over-lap)? Le intenzioni sono quelle di soddisfare alcuni dei criteri appena citati. Inquesto ambito, per tutte e tre le lingue, si e preso in considerazione il criteriodella corrispondenza esatta (exact match), dove: il true-positive rappresenta lecorrispondenze esatte, il false-positive rappresenta le corrispondenza non esatte edil false-negative rappresenta le entita non estratte (e non riconosciute).

Nella Table 7.3 si mostra l’accuratezza raggiunta per la lingua inglese, ottenendodelle prestazioni complessive Buone, cosı descritte nella Sezione 7.3.

Nella Table 7.4 si mostra l’accuratezza raggiunta per la lingua italiana, ottenendodelle prestazioni complessive Buone, sempre descritte nella Sezione 7.3.

126

Infine, nella Table 7.4 si mostra l’accuratezza raggiunta per la lingua araba, ot-tenendo delle prestazioni complessive Sufficienti, sempre descritte nella Sezione7.3.

Table 7.3: Accuratezza raggiunta per la lingua inglese.

LOC 0, 875 0, 834 0, 854PERS 0, 857 0, 875 0, 866ORG 0, 834 0, 875 0, 854MISC 0, 834 0, 834 0, 834

Combinate 0, 827 0, 857 0, 842

Table 7.4: Accuratezza raggiunta per la lingua italiana.

LOC 0, 855 0, 845 0, 850PERS 0, 680 0, 815 0, 740MISC 0, 780 0, 830 0, 800ORG 0, 820 0, 830 0, 825

Combinate 0, 784 0, 830 0, 800

Table 7.5: Accuratezza raggiunta per la lingua araba.

LOC 0, 790 0, 820 0, 800PERS 0, 740 0, 750 0, 750ORG 0, 670 0, 525 0, 590MISC 0, 690 0, 645 0, 660

Combinate 0, 723 0, 685 0, 700

127

Mettendo insieme le prestazioni dei tre moduli NER (E-NER, I-NER e A-NER),si ottiene la Table 7.6, la quale riassume l’accuratezza totale in termini di Preci-sion e di Recall del component di estrazione terminological NER Multi-language,raggiungendo cosı delle prestazioni complessive piu che soddisfacenti.

Table 7.6: Accuratezza totale del component di estrazione terminological NERMulti-language.

- Precision Recall F1E-NER 0, 827 0, 857 0, 842I-NER 0, 784 0, 830 0, 800A-NER 0, 723 0, 685 0, 700

Totale 0, 778 0, 791 0, 781

128

7.3 Riepilogo e conclusioni finalli sulla valutazione

La valutazione e stata fatta per:

• il processo di addestramento dei modelli stocastici (HMM) per la lingua ita-liana e per la lingua araba,

• le prestazioni dei tre moduli (E-NER, I-NER e A-NER) e

• le prestazioni del componente NER Multi-language.

Nella valutazione del processo di addestramento dei modelli per la lingua ital-iana e per la lingua italiana e consistita nel trovare la configurazione ottimale deiparametri di input a disposizione, tali per cui l’accuratezza del modello soddisfii requisiti del componente NER Multi-language. Le valutazioni per entrambi imodelli, hanno dimostrato come l’impostazione dei parametri di input sia in gradodi migliorare la qualita del risultato, ma sopratutto quello, che assume il ruolocardine, e la qualita del corpus (i dati di addestramento) impiegato nel processostesso. Nel corso delle varie iterazioni si e cercato di introdurre delle migliorieper aumentare l’accuratezza dei modelli e la qualita del testo ottenuto. In baseai criteri minimi di accettazione introdotti all’inizio di questo capitolo, entrambii risultati di valutazione ottenuti, sono piu che soddisfacenti, in quanto quello delmodello per la lingua araba sono piu che sufficienti e che quello del modello per lalingua italiana sono buoni.

La seconda valutazione, interessa le prestazioni del componente NER Multi-langua-ge in base ai dati di ingresso, forniti dall’utente, ovvero non e piu l’algoritmo divalutazione a determinare la misura di prestazione del processo. In questo caso, pervalutare i tre moduli NER, presenti nel componente NER Multi-language, vengonoutilizzati dei modelli di verita, con i quali si mettono a confronto gli NEs presentiin essi, con le entita proprie estratti ed identificati dai tre moduli NER. In questamisura, pero, vengono a manifestarsi due problemi, che si possono manifestare neivari test, ovvero:

• dal momento che non vi e una scelta a priori sui dati in ingresso, questipossono avere caratteristiche molto distanti da quelle dei dati che sono statiutilizzati durante l’addestramento;

• il modo con cui e stato costruito l’insieme di addestramento e di valutazione,incide sulle prestazioni generali: i dati sono il frutto di una raccolta manualee di etichettatura manuale di un operatore umano, di articoli di news prove-nienti da diverse fonti, pertanto questo insieme non e detto che possa averecaratteristiche ottimali, in quanto la raccolta e l’etichettatura e a discrezionedello stesso operatore umano.

129

Errori frequenti nell’estrazione delle entita proprie

L’estrazione delle entita proprie e tuttora un problema piu difficile del POS Tag-ging. La ragione di questa affermazione sta nel fatto che le entita proprie possonoestendersi su piu token. Per esempio, l’uso della congiunzione nella singola entitapropria ”Cable e Wireless” non deve essere trattato come un separatore per le dueentita proprie, ”Cable” e ”Wireless”, mentre il ”pezzo” di testo ”IBM e Google”dovrebbe generare due entita proprie separate. Altre strutture di entita propriecomplesse includono preposizioni come ”di”, ”delle”, ”del”, etc.. La frase ”Agenziadelle Entrate” e una singola entita propria, mentre ”Francesco da Roma” dovrebberestituire due entita proprie separate. Un entita propria di tipo PERS come, adesempio, ”Professor Calculus” puo essere inizialmente espresso con il titolo onori-fico di professore all’inizio di una frase. Una citazione senza titolo per la stessaentita propria, puo rendere la questione piu difficile con un sistema di estrazioneper disambiguare l’uso della parola ”Calculus”.

Le parole capitalizzate[15, 19] sono piu propense a rappresentare le entita proprie,ma spesso non possono rappresentare una persona, un luogo, o un’organizzazione.Essi possono essere trovati nel titolo di un articolo o rappresentano un terminefinanziario, medico, o giuridico che non e incluso nel lessico del NER. Un NERpuo anche essere indotto a soggetti, che interpretano ”Policlinico Umberto I” comeun’entita propria di persona in base all’uso del titolo onorifico.

Altri errori simili includono la creazione delle entita proprie di luoghi come ”NewYork Times” o ”Chicago Board of Trade”, infatti molti di questi errori possonoessere risolti utilizzando un gazetteer o un gazetteer geografico per gestire tutte leentita proprie conosciute.

Nota: spesso puo accadere che non si riesca a risolvere piu citazionidella stessa persona (co-riferimento), come ”John Smith”, ”J. Smith”o ”John S.” in un’unica entita propria.

130

Chapter 8

Applicazioni Future

Le applicazioni future (alcune di queste sono state sviluppate), che fanno uso dientita proprie estratte da un testo, possono usare la semantica, senza una completaanalisi del testo o una conoscenza significante. Alcune di queste applicazioni, chene fanno uso, includono: i sistemi Question & Answer, l’organizzazione dei recordsanitari, la ricerca di letteratura accademica e l’applicazioni web e-commerce.

8.1 Sistemi Question & Answer

Un tradizionale motore di ricerca non puo essere utilizzato in questo ambito, inquanto non si puo utilizzare un sistema che si basa semplicemente sull’abbinamentodelle parole chiave della ”domanda”, posta dall’utente, e dal testo presente nei solidocumenti. Cio significa che la ”risposta” del sistema puo avvenire solo tramite laricerca delle entita e non per parole chiave.

Per esempio, un analista dell’intelligence, ad esempio della CIA, potrebbe essereinteressato nel trovare i posti di tutti gli incidenti mortali (o violenti) avvenutiin un periodo di sei mesi attorno a Kabul, citta dell’Afghanistan. Con un sis-tema tradizionale sarebbe molto difficile per l’utente generare una precisa query diricerca per trovare la ”risposta” a questa ”domanda”. Le query per le basi di datisono molto piu precise di un motore di ricerca tradizionale, poiche le parole chiaveutilizzate nella ricerca devono corrispondere con il testo, per un particolare attrib-uto. Percio si e in grado di generare una precisa query per la base di dati sulla”domanda” precedente, con un intervallo di data, longitudine e latitudine, assiemead un elenco di parole chiave per episodi di violenza, come attentati o disordini.Il NER ha come obiettivo quello della compilazione dello schema relazionale, della

131

base di dati, con specifici segmenti di testo provenienti da un testo non strutturatodi notizie (vedere Figure 6.1).

Figure 8.1: Schema generale di un sistema Question & Answer.

Si estrae l’elenco dei luoghi ed il timestamp dagli articoli insieme a un elenco diparole chiave e di sinonimi. L’elenco dei luoghi e ulteriormente differenziato invalori di longitudine e di latitudine. L’elenco delle parole chiave e dei sinonimisono indicizzati utilizzando un motore di ricerca come Lucene.

La questione viene tradotta in una o piu query per la base di dati e in una solaquery per il motore di ricerca. I risultati di una ricerca delle tabelle della base didati restituira una serie di articoli di A, che menzionano gli indirizzi vicino a Kabulnell’intervallo di date specificate. La query per il motore di ricerca restituira unaserie di articoli B, che includono le parole chiave come ”bombardamenti” nel testo.L’intersezione dei due insiemdi di risultati, A e B, dovrebbe restituire gli articoliche hanno piu probabilita di essere rilevanti per la ”domanda”.

132

8.2 Sistemi per la ricerca di letteratura accademica

Gli articoli accademici sono in genere pubblicati in un formato standard, con i metadati nell’intestazione dell’articolo, per descrivere: il titolo, gli autori, gli indirizzie-mail, le organizzazioni, le date e gli abstract.

Per questo si potrebbe popolare uno schema relazionale di una base di dati, ren-dendo molto piu facile la ricerca di un insieme di articoli. Purtroppo, il testoestratto dagli articoli non contiene demarcazioni, per separare i diversi tipi dimeta-dati e percio bisognerebbe avere dei modelli per estrarre il titolo, gli autori,e gli altri campi di intestazione.

133

8.3 Applicazioni web e-commerce

Il testo proveniente dalle pagine web di un sito e-commerce contengono una listadi prodotti, caratteristiche dei prodotti e costi dei prodotti. Ancora, vi sono indi-cazioni di quando la descrizione di un prodotto termina ed inizia un altro prodotto.Una prima soluzione potrebbe essere quella di costruire un’espressione regolaresulla base di un testo o un pattern HTML nella pagina web. Questa soluzione none affidabile, poiche sia il formato e sia il pattern, contenuto in una pagina Web,possono modificare l’espressione regolare rendendola inutilizzabile. Infatti, non sipuo generare manualmente un’espressione regolare per gestire tutti i casi possibili,perche risulterebbe essere difficile e non e facilmente verificabile.

134

Appendix A

Apprendimento Automatico

L’Apprendimento Automatico[7] (o Machine Learning) e quella disciplina che sioccupa di produrre algoritmi, che attraverso l’esperienza incrementano le loroprestazioni in maniera automatica. La disciplina deriva dalla preesistente mod-ellizzazione statistica dei dati, che costituisce il punto cardine del processo diautomatizzazione con cui il modello stesso viene creato.

Un aspetto fondamentale dell’Apprendimento Automatico e la scelta del mod-ello e il suo corretto dimensionamento, con lo scopo di approssimare al megliola funzione obiettivo senza incappare nell’overfitting1 (sovra-dimensionamento) onell’underfitting2 (sotto-dimensionamento). Sia il sovra-dimensionamento e sia ilsotto-dimensionamento implicano che il modello non e in grado di generalizzarecorrettamente, ossia di fornire risposte corrette a fronte di input diversi da quelliforniti in fase di addestramento.

Nota: per misuare la capacita di generalizzazione e possibile dividere idati a disposizione in due set: il primo set (quello piu grande) detto insiemedi addestramento, serve per la fase di apprendimento, mentre il secondoset (quello piu piccolo, dove la sua dimensione deve essere almeno del 10%,rispetto all’insieme di partenza) serve per la validazione, ed e detto appuntoinsieme di validazione.

Per evitare che il modello inizi ad apprendere anche il rumore dei dati, si applica latecnica dell’early stopping, che ha come obiettivo di fermare l’addestramento primache si verifichi questo problema. Tenendo traccia delle due funzioni d’errore si ha

1Si ha un overfitting, durante la fase di apprendimento, quando un modello statistico si adattaai dati osservati.

2Si ha un underfitting, durante la fase di addestramento, quando il modello non e abbastanzaricco di parametri per poter approssimare correttamente la funzione obiettivo.

135

che l’errore sull’insieme di addestramento e una funzione monotona decrescente,mentre l’errore sull’insieme di validazione ha una funzione con andamento decres-cente fino a raggiungere un punto di minimo, per poi crescere nuovamente (vedifigura A.1). Per questo, l’addestramento deve essere fermato in concomitanza conil punto di minimo.

Figure A.1: Early stopping : funzione di errore.

La scelta dei dati e un’altro aspetto che puo limitare la qualita del modelloi: setra i dati di addestramento e i dati di validazione esiste una forte correlazione siincappa in una sovrastima della capacita predittiva. Per questo, l’insieme dei datideve essere il piu eterogeneo possibile. Comunque deve essere sottolineato che glialgoritmi di apprendimento hanno ottime capacita nell’estrarre le caratteristicheessenziali e nell’isolare le caratteristiche occasionali, suscettibili di errore.

Tipi di learning

L’apprendimento[7] si basa sul principio di sfruttare l’esperienza per migliorare laqualita dei risultati futuri.

• Apprendimento Supervisionato: si forniscono gli ingressi e le corrispondentiuscite desiderate.

• Apprendimento per Rinforzo: si fornisce una valutazione della qualita delrisultato, senza tuttavia indicare la soluzione corretta.

• Apprendimento Non Supervisionato: vengono forniti solo esempi non anno-tati e deve essere il sistema a definire le categorie in cui i dati sono ripartiti.

• Apprendimento Parzialmente Supervisionato o Apprendimento Semi-supervisionato:una parte dei dati non presenta etichettatura.

136

Appendix B

Hidden Markov Models

Un Hidden Markov Model1[1, 23] (HMM) e una catena di Markov i cui stati nonsono osservabili direttamente.

Per chiarire meglio i concetti, si puo ricorrere ad un esempio, che riguarda uninsieme di contenitori di vetro pieni di palline colorate. Si suppone di avere in unastanza N grandi contenitori riempiti di palline di vari colori, dove ogni contenitoreha, al suo interno, un certo numero di palline di ciascun colore, ed i colori possibilisono Σ e nella stanza e presente anche un folletto, il quale sceglie un recipienteiniziale secondo un qualche criterio arbitrario, estrae una pallina da esso annotan-done il colore, dopodiche la rimette al suo posto. Infine la sequenza ricomincia conla scelta di un altro contenitore. Nella stanza accanto si trovano degli osservatori ead essi il folletto comunica soltanto la sequenza dei colori estratti. Tali osservatoripossono modellare il complessivo processo come un HMM, dove gli stati verrannorappresentati dal numero di contenitori ed ogni contenitore e caratterizzato dadeterminate probabilita per l’uscita di ciascun colore.

Supponendo che il sistema, che si sta delineando, goda della proprieta di Markov,secondo cui la probabilita che esso si trovi, in un certo stato, al tempo t dipendesoltanto dallo stato all’istante t–1, ma non da quelli degli istanti precedenti.

Esprimendolo matematicamente:

P (xt = sj|xt–1 = si, xt = sk, . . . , x0 = sm) = P (xt = sj|xt–1 = si).

Supponendo anche che le transizioni siano regolate da un insieme di probabilita,

1Un HMM e particolarmente noto per la loro applicazione come: il riconoscimento di patterntemporale, il riconoscimento dei gesti, la ricostruzione di segnali, il POS Tagging il riconoscimentodella parola, la lettura ottica dei caratteri, il riconoscimento vocale, etc.

137

indipendenti dal tempo, dette appunto probabilita di transizione:

P (xt = sj|xt–1 = si) = ai,j

per ogni t,1 ≤ i, j ≤ N.

Poiche le ai,j sono probabilita, devono soddisfare i seguenti vincoli:

1. ai,j ≤ 0, per ogni i, j;

2.∑N

j=1 ai,j = 1, per ogni i.

Figure B.1: Un Hidden Markov Model.

Il modello considerato produce, infine, un’uscita osservabile ad ogni istante ditempo.

Un modello si dice osservabile se, attraverso le uscita, si conosce con esattezza lasequenza di stati che il sistema ha percorso. Mentre, si dice che un modello non eosservabile nel caso in cui il valore di uscita non sia lo stato.

Per indicare una generica uscita si utilizza vk e per indicare la probabilita che ilmodello abbia quell’uscita si utlizza bi(k), trovandosi nello stato i, ossia l’uscita vke condizionato dallo stato i. In un modello siffatto, gli unici segnali osservabili sonole uscite vk e la sequenza degli stati che il sistema attraversa rimane nascosta, anchese, in generale, non e dato sapere da quali e quanti stati sia composto il modello.Per questo motivo si parla di HMM, perche, appunto, si fa riferimento alla nonosservabilita della sequenza degli stati.

138

Tornando ai modelli markoviani, e opportuno caratterizzare, in maniera formal-mente piu rigorosa, le loro componenti, ovvero un HMM e un modello stocasticocomposto da:

i. la catena ha un insieme di stati S = 〈s1, s2, s3, . . . , sN〉;

ii. Σ diversi simboli, dove Σ = 〈σ1, σ2, σ3, . . . , σK〉, uno per ogni differente uscitaosservabile;

iii. l’insieme A = 〈ai,j〉 delle probabilita di transizione fra stati;

iv. l’insieme B = 〈bj(k)〉 delle probabilita di emissione delle uscite osservabilinei vari stati;

v. la distribuzione di probabilita dello stato iniziale π0, dove π0 = P (x1 =si), 1 ≤ i ≤ n.

Una volta che sono stati scelti i due parametri S e Σ, il modello HMM2 M ecompletamete specificato dalla terna A, B e π0.

Un HMM puo essere usato come un generatore per produrre una sequenza diosservazioni:

O = 〈O1, O2, . . . , OT 〉

dove ogni osservazione Ot e un simbolo di Σ e T e il numero di osservazioni dellasequenza. La sequenza O (detta anche evoluzione temporale del modello) vienegenerata con il seguente procedimento:

(1) Si sceglie uno stato iniziale si in accordo con l’insieme delle proprieta inizialiπ0.

(2) Si pone t = 1, dove t e l’indice temporale;.

(3) Si sceglie Ot = vk secondo la distribuzione di probabilita bi(k).

(4) Si transita in un nuovo stato trovando l’elemento ai,j nella matrice di tran-sizione A.

(5) Settare t = t + 1. Se t ≤ T si ritorna al passo (3), altrimenti si esce dallaprocedura.

Tale procedura puo essere usata come un generatore di osservazioni, ma anche comeun modello per capire come una data sequenza di osservazioni e stata generata daun HMM appropriato.

2Un generico HMM si trova indicato, in letteratura, con il simbolo γ〈A,B, π0〉, o, piu sem-plicemente γ.

139

Appendix C

Espressioni regolari

Le espressioni regolari[12, 16, 27] vengono utilizzate per trovare delle corrispon-denze nelle stringhe (o frasi). Quindi se si vuole cercare una sottostringa ”abc”all’interno delle stringhe, esse devono contenere esattamente queste lettere nellastessa sequenza, affinche venga trovato il riscontro.

Molti sviluppatori hanno familiarita con queste espressioni per il pattern-matching,come ad esempio UNIX grep, linguaggi di programmazione come il Perl, e glistrumenti per l’analisi lessicale per i compilatori dei linguaggi di programmazione,come lex.

Piu formalmente, nell’Informatica Teorica, una espressione regolare (in inglese lesue forme abbreviate sono regexp, regex o RE) e una sequenza di simboli (quindiuna stringa) che identifica un insieme di stringhe. In generale, le esperssioni re-golari sono usate per specificare o definire linguaggi regolari, tuttavia permet-tono di definire anche linguaggi non regolari. I linguaggi regolari sono i linguaggigenerati da grammatiche di tipo 3 (nella gerarchia di Chomsky) e riconosciutida automi (deterministici, semi-deterministici e non-deterministici) a stati finiti.Tuttavia, le espressioni regolari esprimono un formalismo generico, attraverso deimatching pattern. Tale formalismo, non e specifico ad un particolare strumentoo linguaggio di programmazione. Una espressione regolare rappresenta un’insiemeregolare di parole in termini di tre semplici operazioni: adiacenza, ripetizione ealternazione.

Una simile espressione regolare a(b|c)∗a rappresenta un linguaggio infinito L =aa, aba, aca, abba, abca, acba, acca, . . .. L’espressione regolare (b|c) sta a significare”scegliere b o c”, mentre con il simbolo ” ∗ ” (star o chiusura di Kleene) significa”zero o piu volte” e l’adiacenza di due simboli ha il suo significato usuale.

140

Gli operatori delle espressioni regolari

Come e stato detto precedentemente, le espressioni regolari[12, 16, 27] denotanolinguaggi regolari. Data una sequenza su un qualsiasi alfabeto finito Σ = 〈a1, a2,-. . . , an〉, gli operatori delle espressioni regolari possono essere definiti nel seguentemodo.

1. Se ai ∈ A, per 1 ≤ i ≤ n, allora ai e una espressione regolare.

2. Se L e M sono espressioni regolari, allora lo e (LM), dove (LM) rappre-senta l’insieme delle stringhe, che si possono formare prendendo una qualsiasistringa in L e concatenandola con qualsiasi stringa in M .

3. Se L,M, . . . , T sono espressioni regolari, allora lo e (L|M | . . . |T ), dove (L|M |−. . . |T ) rappresenta l’unione delle espressioni regolari L,M, . . . , T .

4. Se L e una espressione regolare, allora lo e anche L∗, dove L∗ rappresental’insieme delle stringhe che possono essere formate prendendo un numeroqualsiasi di stringhe da L, eventualmente con ripetizioni.

5. Solo le espressioni formate applicando le regole 1−4 sono espressioni regolari.

Nota: si assume per convenienza, che la stringa vuota e definitacome una espressione regolare ed e denotata da ε.

141

Bibliography

[1] Bilmes Jeff A. What HMMs Can Do. IEICE TRANS. INF. & SYST., E89–D,2006.

[2] Alfred V. Aho and Margaret J. Corasick. Efficient string matching: An aidto bibliographic search. Communications of the ACM, 18(6):333–340, June1975.

[3] Shabib AlGahtani. Arabic Named Entity Recognition: A Corpus-BasedStudy, 2012.

[4] Breck Baldwin Bob Carpenter. Text Analysis with LingPipe 4. LingPipePublishing - New York, 2011.

[5] Breck Baldwin Bob Carpenter. LingPipe Web Site. URL: alias-i.com/lingpipe/index.html, 2004.

[6] Breck Baldwin Bob Carpenter, Mitzi Morris. Text Processing with Java 6.LingPipe Publishing - New York, 2011.

[7] Alessandro Francois Camerada. Classificazione di contenuti generati dagliutenti come soluzione al problema del sovraccarico informativo del Web, 2010- 2011.

[8] Alessandro Mazzei e Vincenzo Lombardo Cristina Bosco. Evalita ParsingTask: an analysis of the first parsing system contest for Italian.

[9] Alessandro Mazzei Vincenzo Lombardo Felice Dell’Orletta Alessandro LenciCristina Bosco, Simonetta Montemagni. Evalita ’09 Parsing Task: comparingdependency parsers and treebanks.

[10] Satoshi Sekine David Nadeau. A Survey of named entity recognition andclassification. National Research Council Canada/New York University.

142

[11] Daniel Jurafsky e James H. Martin. Speech and Language Processing - AnIntroduction to Natural Language Processing, Computational Linguistics andSpeech Recognition. Prentice Hall.

[12] By Jeffrey E. F. Friedl. Mastering Regular Expressions. O’Reilly.

[13] Giuseppe Rizzo, Raphael Troncy, Sebastian Hellmann. NERD Meets NIF:Lifting NLP Extraction Results to the Linked Data Cloud. LDOW2012.

[14] John Haugeland. Artificial Intelligence: The Very Idea. Cambridge, Mass:MIT Press.

[15] Will Radford Tara Murphy James R. Curran Joel Northman, Nicky Ringland.Learning multilingual named entity recognition from Wikipedia. ArtificialIntelligence, 194(1):151–175, Mar. 2012.

[16] Jeffrey D. Ullman John E. Hopcroft, Rajeev Motwani. Automi, Linguaggi eCalcolabilita - Terza Edizione. Pearson - Addison Wesley.

[17] Joseph Turian, Lev Ratinov, Yoshua Bengio. Word Representations: A Simpleand General Method for Semi-Supervised Learning. ACL ’10 Proceedings ofthe 48th Annual Meeting of the Association for Computational Linguistics.

[18] Khaled Shaalan, Hafsa Raza. NERA: Named Entity Recognition for Arabic.Journal of the American Society for Information Science and Technology,60:1652–1663, 2009.

[19] Manu Konchady. Building Search Applications Lucene, LingPipe, and Gate.Mustru Publishing.

[20] Beata Megyesi. Brill’s Rule-Based Part of Speech Tagger for Hungarian.

[21] Paola Velardi, Francesco Slano. TermExtractor: a Web Application to Learnthe Common Terminology of Groups and Research Communities. ConferenceTIA-2007.

[22] Simone Teufel Peter Corbett, Colin Batchelor. Annotation of ChemicalNamed Entities. BioNLP 2007: Biological, translational, and clinical lan-guage processing, 57–64:27–31, June ACL 2007.

[23] L.R. Rabiner. A tutorial on HMM and selected applications in speech recog-nition. In Proc. IEEE, 77(2):257–286, Feb. 1989.

[24] Emanuele Pianta e Claudio Giuliano Roberto Zanoli. Named Entity Recogni-tion through Redundancy Driven Classifiers. Poster and Workshop Proceed-ings of the 11th Conference of the Italian Association for Artificial Intelli-gence.

143

[25] Beatrice Santorini. Part-of-Speech Tagging Guidelines for Penn TreebankProject.

[26] Raffaele Simone. Fondamenti di linguistica. 2008.

[27] Michael Sipser. Introduction to the Theory of Computation - Second Edition,International Edition. Thomson Course Techonology.

[28] Ronald L. Rivest Thomas H. Cormen, Charles E. Leiserson. Introduzione aglialgoritmi. Jackson Libri, 2003.

[29] Thorsten Brants. Tagset Reduction Without Information Loss. Proceedingsof the 33rd Annual Meeting of the Association for Computational Linguistics,Cambridge, MA (1995).

[30] Manuela Speranza e Rachele Sprugnoli Valentina Bartalesi Lenzi. EVALITA2011: Description and Results of the Named Entity Recognition on Tran-scribed Broadcast News Task. Poster and Workshop Proceedings of the 12thConference of the Italian Association for Artificial Intelligence.

[31] Paolo Rosso Yassine Benajiba. ANERsys 2.0: Conquering the NER Taskfor the Arabic Language by Combining the Maximun Entropy with POS-tagInformation. 3rd Indian Conference on Artificial Intelligence (IICAI-07).

[32] Paolo Rosso Yassine Benajiba. ANERsys: An Arabic Named Entity Recogni-tion System Based on Maximum Entropy. CICLing ’07 Proceedings of the 8thInternational Conference on Computational Linguistics and Intelligent TextProcessing.

[33] Paolo Rosso Yassine Benajiba. Arabic Named Entity Recognition using Con-ditional Random Fields. HLT and NLP within the Arabic world 2008.

144

Un componente NER Multi-language per il TermExtractor

Science

Transcript of Un componente NER Multi-language per il TermExtractor