3.2 CoNLL 2003 e Preprocessing
3.2.1 CoNLL
Il CoNLL4 `e un convegno annuale organizzato dal SIGNLL5 un sottogruppo
del ACL6. Dal 1999, ogni anno CoNLL ha incluso uno shared task in cui
vengono offerti dagli organizzatori dati di training e di test per poter con- correre a una competizione su uno dei task dell’elaborazione del linguaggio naturale, in queste competizioni viene permesso ai sistemi che partecipano di essere valutati e comparati in modo sistematico, e quindi di capire in maniera abbastanza oggettiva quali sono le migliori tecniche per gli specifici task.
3.2.2
Corpus CoNLL 2003
Nel 2003 la competizione organizzata dal CoNLL ha avuto come interes- se il Language Independent Named entity Recognition. Le entit`a su cui si concentra la competizione sono quattro:
• persone(PER)
4
L’acronimo per CoNLL sta per Conference on Natural Language Learning
5
Special Interest Group on Natural Language Learning
6
Association for Computational Linguistics
Token Term POS Lemma Label t - 2 EU NNP eu I-ORG t - 1 rejects VBZ rejects O t German JJ german I-MISC t + 1 call NN call O
t + 2 to TO to O
t + 3 boycott VB boycott O t + 4 British JJ british I-MISC t + 5 lamb NN lamb O
Tabella 3.1: Esempio di rappresentazione dei token con incluse le feature della finestra statica e dinamica del token t sottolineate
• organizzazioni(ORG)
• luoghi(LOC)
• nomi di entit`a miste(MISC) (entit`a che non appartengono a nessuno dei primi tre tipi)
Ai partecipanti sono stati dati corpus training e test, in lingua inglese e tedesca, con l’obiettivo di sviluppare un sistema di named entity recognition con una parte di apprendimento automatico. Per ogni linguaggio sono stati forniti 4 file, uno di training, uno di sviluppo, uno di test e uno non annotato, il corpus in lingua inglese `e stato preso dal corpus di notizie Reuters7 che
comprende gli articoli tra l’Agosto 1996 e Agosto 1997. I corpora di training e di sviluppo sono composti da articoli datati Agosto 1996, invece il corpus di test `e composto da articoli del Dicembre 1996.
Articoli Frasi Token Training set 946 14,987 203,621 Development set 216 3,466 51,362 Test set 231 3,684 46,435
Tabella 3.2: Numero di articoli frasi e token per ogni file
LOC MISC ORG PER Training set 7140 3438 6321 6600 Development set 1837 922 1341 1842 Test set 1668 702 1661 1617
Tabella 3.3: Numero di named entity per ogni file
7
I set annotati sono stati preprocessati con un tokenizer, un part of speech tagger e un chunker, sono stati quindi suddivisi in token e sono state aggiunte le informazioni su part of spech e chunk. I tag delle entit`a sono stati annotati a mano dagli esperti dell’Universit`a di Anversa. Come gi`a detto oltre ai tre classici tipi di entit`a, ne `e stata aggiunta un’altra MISC, che sta a indicare tutti le espressioni che non appartengono ai tipi ORG PER o LOC, per esempio aggettivi come Italians o eventi come 1000 Lake Rally.
Ogni file del corpus contiene una parola per linea, una riga vuota rappre- senta la fine di una frase, alla fine di ogni riga c’`e un tag che indica se la parola fa parte di una entit`a oppure no, il tag indica anche il tipo di entit`a. Un esempio di struttura della frase del corpus originale `e mostrato nell’esempio 3.4.
U.N. NNP I-NP I-ORG official NN I-NP O Ekeus NNP I-NP I-PER heads VBZ I-VP O for IN I-PP O Baghdad NNP I-NP I-LOC
. . O O
Tabella 3.4: Esempio frase nel corpus originale
Ogni riga contiene 4 campi: il token, il tag part of speech, il tag chunk, il tag named entity. I tag named entity sono etichettati seguendo lo schema detto IOB. Lo schema IOB, `e uno standard per la rappresentazione dei dati in questo tipo di task. Nell’ IOB le parole etichettate con O sono al di fuori di qualsiasi named entity, quelle etichettate con I-XXX(Inside) sono parole all’interno di un named entity di tipo XXX. Ogni volta che due named entity dello stesso tipo XXX sono immediatamente successive, la prima parola della seconda entit`a avr`a come tag B-XXX(Begin), per mostrare che da quella
parola comincia un’altra entit`a. Si assume anche che i named entity non siano ricorsivi o sovrapposti, e quando un’entit`a `e all’interno di un’altra soltanto l’entit`a esterna `e annotata.
CDU NNP B-NP I-ORG / SYM nil I-ORG CSU NNP B-NP I-ORG SPD NNP I-NP B-ORG FDP NNP I-NP B-ORG Greens NNP I-NP B-ORG PDS NNP I-NP B-ORG
Tabella 3.5: Esempio di modello IOB
Nell’esempio 3.5 si nota che l’entit`a CDU /CSU `e la prima entit`a leggendo dall’alto verso il basso, di tipo ORG che si trova nella frase. Le entit`a suc- cessive sono tutte di tipo ORG ma tutte distinte, hanno quindi come prefisso di etichetta B, che appunto sta a indicare che ogni token, in questo caso, `e un’entit`a a se stante.
3.2.3
Preprocessing
I data set utilizzati nello shared task CoNLL 2003, sono stati ulteriormente processati con TagPro per aggiungere altre informazioni a ogni parola. Tag- Pro `e un sistema per il POS-tagging basato su SVM, fa parte di TextPro una suite completa per l’elaborazione del linguaggio naturale[7]. TagPro estende le informazioni con altri campi: la parola normalizzata in minuscolo, prefis- si, suffissi e caratteristiche ortografiche come capitalization e hyphenation. Queste offrono maggiori feature all’algoritmo SVM, rendendolo pi`u efficace. Dopo il preprocessing di TagPro la struttura del corpus sar`a come quella in 3.6
CDU cdu c cd cdu nil u du cdu nil U N NNP B-NP I-ORG
/ / / nil nil nil / nil nil nil N W SYM nil I-ORG
CSU csu c cs csu nil u su csu nil U N NNP B-NP I-ORG
SPD spd s sp spd nil d pd spd nil U N NNP I-NP B-ORG
FDP fdp f fd fdp nil p dp fdp nil U N NNP I-NP B-ORG
Greens greens g gr gre gree s ns ens eens C N NNP I-NP B-ORG
PDS pds p pd pds nil s ds pds nil U N NNP I-NP B-ORG
Strategie di active learning per
estrazione dell’informazione
In questo lavoro abbiamo considerato come unit`a di scelta le frasi, le pi`u piccole unit`a che anche decontestualizzate non perdono valore informativo, a differenza dei token, che presi uno per volta non hanno nessun particolare significato. In un task come il NER infatti non si pu`o prendere come unit`a solamente il token privo di ogni contesto. Una named entity pu`o essere costituita da pi`u token; prendiamo per esempio il token States che, da solo non appartiene a nessuna classe; se per`o viene inserita in un contesto pu`o essere un token che fa parte di una named entity di tipo LOC: United States of America. Da questo fatto non possiamo di sicuro scegliere come unit`a informativa il token dato che andrebbero perse tutte quelle named entity composte da pi`u token. Oltretutto il fatto di avere un contesto ampio diversi token ci permette di associare una finestra di feature a ogni singolo token (vedi Sezione 3.1.2). Un’unit`a di scelta pi`u ampia di una frase creerebbe dei contesti inconsistenti, dato che potrebbero esserci unit`a composte da pi`u frasi, che porterebbero a degli errori di classificazione.
Si dovranno adottare quindi delle funzioni che partendo dai punteggi asse- gnati dal classificatore a ogni token, restituiscano punteggi relativi alle frasi. Abbiamo definito una funzione σ(s) → R che data una frase s, restituisce un
valore reale di rilevanza di s rispetto al processo di active learning. Queste frasi saranno poi ordinate dalle nostre politiche. Negli esperimenti effettuati abbiamo comparato diverse strategie σ per fare il ranking delle frasi.
4.1
Dimensioni
Le strategie sono state definite basandosi su varie dimensioni, ispirandoci in tal modo al lavoro di Esuli Sebastiani sull’active learning nella multi-label text classification [3].
Per rendere chiaro il concetto di dimensioni dobbiamo introdurre due insiemi:
T = {LOC, P ER, ORG, MISC} (4.1) e
L = T + {O} (4.2)
. Gli elementi dell’insieme T sono le etichette che devono essere assegnate alle named entity secondo gli obiettivi del task CoNLL 2003 [9]. L’insieme L contiene tutti gli elementi di T con in pi`u l’etichetta O (che significa nessun tag), che sar`a assegnata dal classificatore a tutti quei token che non sono classificati con gli elementi dell’insieme T .
4.1.1
La dimensione Evidence
La prima dimensione su cui abbiamo basato la definizione delle politiche di active learning `e la dimensione evidence. La dimensione evidence `e stret- tamente legata alla confidenza che ha il classificatore nell’etichettare un token.
Una potenziale scelta `e quella di usare come evidence, il valore di confi- denza con il quale i token vengono classificati. L’intuizione che sta dietro a questa scelta `e che, avendo un basso valore di confidenza su di un token, il classificatore ha un’alta incertezza riguardo alla sua classe di appartenenza.
Aggiungendo il token con bassa confidenza al training set si aiuta il classifica- tore a risolvere un caso “difficile”. Chiameremo questa scelta Min Confidence (in simboli MC). La confidenza di un token `e definita dalla funzione:
tokenScore(t) = maxx∈L(x(t)) (4.3)
dove t rappresenta i token che compongono il testo su cui fare il ranking, e x(t) rappresenta la funzione che, dato un token, restituisce un punteggio associato alla label x; per esempio; LOC(′′
UK′′
) = 0, 83879.
Una scelta alternativa `e usare come evidence il valore di score con il quale i token vengono classificati, qui l’intuizione `e che pi`u alto `e lo score e con maggiore sicurezza il token sar`a un esempio positivo (pi`u il valore assoluto dello score `e alto, pi`u il classificatore ha un’alta confidenza rispetto al token, e quindi `e un esempio positivo, pi`u il valore assoluto dello score si avvicina a zero, pi`u il classificatore ha una bassa confidenza rispetto al token, e quindi `e un esempio negativo), che nei task di apprendimento supervisionato `e molto pi`u utile di un esempio negativo. Chiameremo questa scelta Max Score (MS). Lo score di un token `e definito dalla funzione:
tagScore(t) = maxx∈T(x(t)) (4.4)
dove t rappresenta i token, e x(t) rappresenta la funzione che, dato un token, restituisce un punteggio associato al tag x.
Come gi`a detto, il nostro obiettivo `e di effettuare il ranking delle frasi. In una frase non esiste soltanto un valore, sia questo confidenza o score, ma m singoli valori, uno per ogni token. Come utilizzare questi m valori `e lo scopo della dimensione class (discussa nel Capitolo 4.1.2) la quale ci dice qual `e “il” valore rappresentativo di una frase.
4.1.2
La dimensione Class
La dimension “class” ha a che fare con il fatto che qualsiasi valore si scelga di usare come dimensione “evidence”, sia questo confidenza o score, ci sono
m diversi valori per ogni frase s. La dimensione class rappresenta le politi- che su come scegliere un valore combinando i m valori che otteniamo dalla dimensione evidence.
Se la nostra scelta `e MC, possiamo scegliere di prendere il minimo valore di confidenza dei token per assegnarlo alla frase come valore rappresentativo, e poi ordinare le frasi in maniera crescente, in accordo con la dimensione “evidence”. Questo significa avere:
σ = min(mintj∈Si(tokenScore(tj)) (4.5)
(dove Si sono le frasi che compongono l’unlabelled set appena classificato),
questa politica `e chiamata Min Min Confidence (MMC).
Se invece scegliamo MS, possiamo scegliere di prendere il massimo valore di score dei token per assegnarlo alla frase, e poi ordinare le frasi in ma- niera decrescente, in accordo con la dimensione “evidence”, la strategia che otteniamo `e
σ = max(maxtj∈Si(tagScore(tj)) (4.6)
cio`e la politica Max Max Score (MMS). Lo scopo di queste due politiche `e quello di far concentrare l’annotatore manuale su frasi che hanno dei token che vengono considerati casi estremi. Queste due scelte vengono chiamate MIN/MAX(M).
Un’altra scelta alternativa `e fare la media tra i valori di confidenza o di score, ottenendo due strategie distinte, la prima
σ = min(averagetj∈Si(tokenScore(tj)) (4.7)
detta Min Average Confidence (MAC), e la seconda
σ = max(averagetj∈Si(tagScore(tj)) (4.8)
chiamata Max Average Score, (MAS). Questa politica `e intesa a forzare l’annotatore a etichettare i token di quelle frasi che hanno una buona media di casi interessanti. Chiamiamo questa scelta Average (A).
4.1.3
Round Robin
Le strategie esposte finora effettuano una scelta abbastanza ineguale sui tag che si hanno a disposizione. In pratica `e possibile che le strategie prendano delle frasi che migliorano il classificatore sul riconoscimento di alcuni tag, lasciando invariato o peggiorando il riconoscimento sul resto dei tag. La strategia che andiamo a illustrare considerando le politiche gi`a esposte, crea un ranking per ogni tag, quindi 4 rank, che saranno poi uniti per creare un rank globale. Questo `e ottenuto:
1. prendendo per ogni o ∈ T i token “migliori”, in accordo con la scelta MS della dimensione evidence.
2. facendo per ogni o ∈ T il ranking delle frasi secondo il criterio della dimensione class.
3. inserendo nel ranking globale le k migliori frasi di ogni o ∈ T .
Come si pu`o vedere la dimensione class viene utilizzata diversamente dalle politiche round robin, prendendo MS come dimensione “evidence” (l’unica possibile). Per ogni frase si hanno 4 valori di score, uno per ogni oj ∈ T . Al
solito, ogni valore sar`a assegnato in accordo alla scelta fatta sulla dimensione “class”: Average o Max. Round Robin Max Average Score (RRMAS) `e dato da:
σo = max(averagetj∈Si(tokenScoreo(tj))∀o ∈ T (4.9)
dove tokenScoreo(tj) `e il valore dello score del tag o del token tj.
Round Robin Max Max Score (RRMMS) `e dato da:
σo= max(maxtj∈Si(tokenScoreo(tj))∀o ∈ T (4.10)
La dimensione “round robin” `e compatibile soltanto con le politiche MMS e MAS in quanto lo score `e una misura globale, cio`e per affermare che un token ha uno score basso tutti gli score devono essere bassi, mentre uno score alto per un singolo tag `e comunque rilevante indipendentemente dal valore
degli altri. Non ha senso parlare di “round robin” sulle strategie MMC e MAC dato che l’insieme che sta alla base delle due strategie contiene anche O che non `e un tag.
Nella Tabella 4.1 sono riassunte le strategie sperimentate.
MMC Min Min Confidence MAC Min Average Confidence MMS Min Min Score
MAS Min Average Score
RRMMS Round Robin Min Min Score RRMAS Round Robin Min Average Score
Tabella 4.1: Riassunto politiche basate su dimensioni
4.2
Esperimenti
4.2.1
Protocollo utilizzato
In questo lavoro abbiamo utilizzato il seguente protocollo sperimentale, ba- sato su tre parametri interi α, β e γ. α rappresenta il numero di esempi di training da cui l’algoritmo parte, β sta a indicare il numero di iterazioni che il learner deve compiere, e γ sta a indicare il numero di token che vanno in- seriti nel training set. Ovviamente questi token sono tradotti in frasi, questo `e stato fatto per avere training set della stessa dimensione, e non favorire politiche banali che prediligono frasi molto lunghe. Sia Ω il nostro corpus, diviso in un training set T r e un test set T e e sia σ una strategia di active learning.
2. impostare un training set corrente T rt con l’insieme delle prime α frasi
di T r; impostare l’unlabelled set corrente Ut ← T r/T rt;
3. For t = 1,...,β ripetere i seguenti passi:
(a) Generare un classificatore ˆΦt dal training set corrente T r t
(b) Valutare l’efficacia di ˆΦt su T e
(c) Classificare Ut con ˆΦt
(d) Fare il ranking delle frasi in Ut in accordo con la strategia σ
(e) Sia r(Ut, γ) l’insieme dei γ elementi di Ut top-ranked; impostare
T rt+1 ← T rt∪r(Ut, γ); impostare Ut+1 ← Ut/r(Ut, γ)
E’ importante notare che lo Step 3.b ha il solo scopo di collezionare risultati per fini sperimentali (ad esempio per i grafici e le tabelle della Sezione 4.5), dato che viene utilizzato il test set questi risultati non sono accessibili in nessun modo all’algoritmo. Il protocollo sopra simula l’attivit`a di un anno- tatore umano che all’inizio del processo ha disponibile un training set T r0
che consiste in α esempi (frasi) e un “unlabelled set” U0 che consiste in |T r|
− α esempi non etichettati. L’annotatore genera un classificatore ˆΦ0 da T r
0,
lo usa per classificare le parole in U0 e chiede all’agente di active learning
il ranking delle frasi di U0, poi manualmente l’annotatore umano (oracolo)
etichetta le prime γ, viene generato un classificatore ˆΦ1 con il training set in-
grandito che comprende T r0 e γ nuovi esempi etichettati, viene cos`ı ripetuto
il processo β volte. Si pu`o notare che il criterio di arresto utilizzato e quello fixed sul limite di esempi che l’annotatore pu`o etichettare. Infatti dopo che aver etichettato per β volte γ token, l’oracolo si ferma e non ne etichetta altri.
Negli esperimenti che abbiamo condotto abbiamo impostato i valori in questo modo: α = 110 corrispondente a circa 2000 token, β = 20 e γ = 200. Abbiamo assunto che questi parametri siano realistici, dato che simulano la situazione in cui:
• inizialmente ci sono soltanto 110 frasi di training (questo `e ragionevole dato che in molte applicazioni in cui sono disponibili pi`u esempi di trai- ning, gli annotatori umani possono pensare che valga la pena annotarne di pi`u)
• ogni volta che un annotatore umano etichetta le frasi che corrispondono a 200 token, l’annotatore vuole aggiornare il sistema (`e ragionevole dato che l’annotatore vuole vedere se gli ultimi esempi aggiunti al training set hanno migliorato l’accuratezza del classificatore (questo pu`o essere fatto tramite lo Step 3.b)).
4.2.2
Baseline
Come strategia baseline per la valutazione dei risultati `e stata utilizzata la politica random, che consiste nello scegliere frasi non etichettate in maniera casuale, e aggiungerle una volta etichettate al training set. In pratica questa politica simula il comportamento di un annotatore umano che prende esempi non etichettati, e li etichetta senza avere un preciso ordine.
4.3
Metodi di valutazione
Per valutare i nostri esperimenti usiamo 3 diversi modelli di valutazione (exact match, token model, token & blank model) che appartengono a due classi di metodi di valutazione:
• La prima (annotation-based ), `e basata considerando una testo annotato come un singolo elemento. Per annotazione si intende l’associazione di una certa etichetta a pi`u parole che appartengono a una determinata classe, per esempio ORG potrebbe essere un’annotazione per Governo Italiano. La valutazione `e basta sulla comparazione dei match tra due insiemi di annotazioni, quelle ottenute dal classificatore e quelle effettive del corpus utilizzato per la valutazione.
• La seconda (token-based ), `e basata sul considerare ogni token come un singolo elemento. La valutazione `e effettuata misurando l’accuratezza della classificazione usando misure standard di information retrieval, come precision, recall e F1.
4.3.1
Misure annotation-based
Le misure di valutazione annotation-based considerano un testo annotato come un unico elemento. La valutazione `e eseguita comparando i match tra due insiemi, uno con le classificazioni corrette GX = {g1, ..., gn}, l’altro con
la classificazione eseguita dal nostro sistema, PX = {g1, ..., gn}, per ogni tipo
di etichetta X1. Si pu`o notare che P pu`o contenere un numero arbitrario
di elementi, che non `e detto sia uguale al numero di elementi inclusi in G. Inoltre, le annotazioni in P possono riferirsi a qualsiasi porzione di testo nel documento annotato, senza nessuna relazione con G. Una conseguenza di questo fatto `e che `e impossibile stabilire una relazione uno a uno tra elementi di G e P .
Nell’estrazione dell’informazione un approccio tipico `e quello di definire un predicato del tipo match(g, p) → {true, f alse}, che determina se due elementi, p ∈ P e g ∈ G, hanno un match, e usare questo predicato per calcolare una versione approssimata delle misure di precision (π), recall (ρ), e F1. π(G, P ) = |{p|p ∈ P ∧ ∃g ∈ G : match(g, p)}| |P | (4.11) ρ(G, P ) = |{g|g ∈ G ∧ ∃p ∈ P : match(g, p)}| |G| (4.12) F1(G, P ) = 2π(G, P )ρ(G, P ) π(G, P ) + ρ(G, P ) (4.13) Il predicato match `e definito in vari metodi:
overlap: matchoverlap(g, p) = T rue se e solo se due annotazioni si sovrappongono;
1
head: matchhead(g, p) = T rue se e solo se due annotazioni iniziano dalla stessa
posizione nel testo;
exact: matchexact(g, p) = T rue se e solo se due annotazioni iniziano e finiscono
nella stessa posizione nel testo;
Ad esempio, dati un annotazione ottimale e i tre predicati visti sopra: g = “from the [LOCNational Rifle Association]LOC gun lobby”2
p1 = “from the National Rifle [LOCAssociation]LOC gun lobby”
p2 = “from the [LOCNational Rifle]LOC Association gun lobby”
p3 = “from the [LOCNational Rifle Association]LOC gun lobby”
il predicato matchoverlap(g, pi) `e vero per ogni frase pi, il predicato
matchhead(g, pi) `e vero per le frasi p2 e p3, mentre matchexact(g, pi) `e vero
solo per la frase p3.
Sfortunatamente questo tipo di predicati hanno qualche inconveniente. Il predicato overlap tende a sovrastimare le performance di un sistema che ten- de a produrre frasi etichettate molto lunghe. Dall’altro lato i predicati head e exact sono troppo severi nella loro valutazione, dato che trattano i match approssimati come completamente errati. Ad esempio rispetto alla frase an- notata g, “from [LOCthe National Rifle Association]LOC gun lobby”,
viene considerata da entrambi i predicati come un errore nonostante abbia una piccola differenza.
Questi due predicati non prendono in considerazione il grado di overlap tra due frasi annotate, per esempio, due frasi annotate lunghe entrambe 10 parole e che hanno un overlap di una sola parola, avranno lo stesso significato di due frasi annotate di 10 parole che hanno un overlap di 9 parole.
Infine con usando delle misure annotation-based, non `e possibile calcolare una tabella di contingenza vista la mancanza del concetto di veri negativi.