Applicazione di algoritmi evolutivi ad un etichettatore in parti del discorso basato su HMM

- 1 -
Capitolo 1. L’etichettatura in parti del discorso 
1.1 Descrizione del problema 
Ogni parola di un testo appartiene ad una determinata categoria, o parte del discorso (in inglese 
Part-Of-Speech o POS), che ne stabilisce la funzione grammaticale nell’ambito della frase in cui si 
trova. Ad esempio, un verbo identifica un’azione, un aggettivo assegna una certa qualità, un articolo 
introduce un nome, ecc. 
Storicamente, una prima descrizione delle parti del discorso nel contesto linguistico risale a 
Dionisio Trace di Alessandria (170-90 a.C.), il quale compose una sorta di manuale di grammatica 
per il greco (techn5) dove ne distingueva otto categorie [Jurafsky – Martin, 2000] che sono rimaste 
quasi invariate fino ad oggi. Infatti dalle otto originali ne sono state cambiate due e aggiunta una. 
Ecco l’elenco aggiornato: nome, verbo, pronome, preposizione, avverbio, congiunzione, articolo, 
aggettivo e interiezione. 
 
L’etichettatura in parti del discorso (in inglese POS tagging) è il processo che consiste 
nell’assegnare ad ogni parola di una frase un’etichetta (in inglese tag), che ne identifica la categoria 
di appartenenza. In pratica, il processo può essere visto come la trasformazione di una frase in una 
sequenza di etichette. 
 
Ad esempio, la frase: 
la penna è sopra il tavolo . 
 
può essere etichettata in questo modo: 
la/ART penna/NOME è/VERBO sopra/AVV il/ART tavolo/NOME ./. 
 
Si noti che anche la punteggiatura (“.”) viene etichettata come parte del discorso. 
 
Un etichettatore in parti del discorso (in inglese POS tagger) è un sistema automatizzato che 
realizza il processo appena descritto. 
Per svolgere il proprio compito, l’etichettatore deve avere a disposizione un insieme di etichette (in 
inglese tagset) dal quale scegliere le categorie, e un dizionario (o lessico) che elenca tutte le parole 
riconosciute dal sistema con le relative etichette. Queste due strutture possono venir ricavate da una 
collezione di testi di riferimento già etichettati che prende il nome di corpus. Questi testi sono di 
generi diversi, per far sì che il corpus sia un buon riferimento per i molteplici stili di scrittura della 
lingua. 
Molte applicazioni che sfruttano il POS tagging hanno bisogno di maggiori informazioni sulle 
parole del testo, per cui distinguere solamente nove categorie diventa un po’ restrittivo. Le 
dimensioni degli odierni tagset sono state allargate di molto, includendo, per ogni parte del 
discorso, diversi casi. Ad esempio per la categoria nome si possono distinguere quattro sotto-
categorie, ovvero: nome comune singolare, nome comune plurale, nome proprio singolare e plurale. 
Il corpus Brown per l’inglese, di circa un milione di parole, prevede un tagset di 87 parti del 
discorso ed un lessico formato da circa 40.000 termini 
[http://helmer.aksis.uib.no/icame/brown/bcm.html]. 
 
Nell’ambito delle applicazioni di ricerca linguistica, l’etichettatura in parti del discorso fornisce 
delle utili informazioni sulle parole. Ad esempio, se un vocabolo è stato etichettato come un 
pronome personale (io, tu, egli,…), si può stimare che dopo di esso molto probabilmente segua un 
verbo, mentre dopo un aggettivo possessivo (mio, tuo, suo, …) un nome. Questo può essere utile 
nelle applicazioni di riconoscimento del parlato. 
- 2 -
L’etichettatura può essere usata anche nei sistemi di sintesi del parlato: nei casi di omografia
1
,
infatti, sapere qual è la corretta parte del discorso può indicare l’esatta pronuncia per un vocabolo. 
Ad esempio, la parola “ancora” viene pronunciata àncora quando è un nome, e ancòra quando è un 
avverbio. Così leggiamo sùbito (avverbio) e subìto (verbo), oppure légge (nome) e lègge (verbo), 
ecc…. 
L’etichettatura in parti del discorso può risultare utile in molte altre applicazioni, come ad esempio 
il parsing di frasi, l’information retrieval e la classificazione di testi. 
1.1.1 Il concetto di ambiguità delle parole 
La principale difficoltà del processo di etichettatura è dovuta ai casi di omonimia, cioè al fatto che 
le parole possono assumere più etichette, e per questo vengono dette ambigue. Lo scopo di un 
etichettatore è quindi quello di risolvere tali ambiguità. 
Ad esempio, la parola “presa” può essere etichettata come participio passato del verbo prendere o 
come nome (la presa della corrente elettrica), la parola “uno” può essere un articolo indeterminativo 
o un aggettivo numerale cardinale, ecc…. 
A causa di tale ambiguità, ad ogni parola è associato un insieme di possibili etichette. Questo 
insieme viene spesso riportato nel lessico accanto ad ogni termine, in modo da facilitare il compito 
dell’etichettatore. Il vocabolo “presa” dell’esempio appare nel dizionario con entrambe le possibili 
etichette: 
 
presa NOME, VERBO 
 
Vediamo in che misura si pone il problema dell’ambiguità: De Rose [DeRose, 1988] ha conteggiato 
la percentuale di parole ambigue e non per il corpus Brown. Si veda la Figura 1-1. 
 
35340
89,6%
4100
10,4%
Parole non ambigue
Parole ambigue
Figura 1-1 I risultati di DeRose per il corpus Brown. Su 39.440 parole totali, solo il 10,4% sono ambigue. 
Nell’ambito delle parole ambigue, la maggior parte di esse ha un grado di ambiguità = 2, cioè 
queste parole possono essere etichettate in due modi. Le rimanenti di grado più alto sono in minima 
percentuale, come si vede nella Tabella 1-1. 
 
1
Due parole di dicono omografe quando sono scritte allo stesso modo ma hanno pronuncia e significato diverso. 
- 3 -
Parole ambigue (2-7 etichette) 4.100 parole 
di cui: 
2 etichette
3 etichette
4 etichette
5 etichette
6 etichette
7 etichette
3.760 parole 
264 parole 
61 parole 
12 parole 
2 parole 
1 parola, “still” 
 
91.7 % 
6.4 % 
1.4 % 
0.29 % 
0.04 % 
0.02 % 
Tabella 1-1 Distribuzione delle parole ambigue del corpus Brown in base al grado di ambiguità. 
1.2 Vari approcci all’etichettatura in parti del discorso e stato dell’arte 
Nel paragrafo precedente è stato chiarito che il compito di un etichettatore è quello di risolvere le 
ambiguità delle parole. Ma qual è l’idea alla base dell’algoritmo di risoluzione? Come si stabilisce, 
cioè, la corretta parte del discorso per un vocabolo? 
Un metodo è quello di considerare le informazioni contestuali della parola da etichettare, 
intendendo per contesto la disposizione delle etichette delle parole vicine. 
 
Ad esempio, la parola “telefono” può essere un sostantivo, o la prima persona singolare del verbo 
telefonare al presente. Ed è proprio il contesto che aiuta a risolvere l’ambiguità. 
Si guardino le frasi: 
 
il/ART mio/AGG.POSS telefono/NOME è/COPULA rotto/VERBO 
io/PRON.PERS. telefono/VERBO a/PREP.SEMPLICE mia/AGG.POSS. madre/NOME 
 
Nella prima, un articolo e un aggettivo precedono la parola “telefono”: è naturale pensare che la 
sequenza corretta sia ART, AGG e NOME piuttosto che VERBO; nella seconda, invece il termine è 
preceduto da un pronome personale, suggerendoci di etichettarlo come verbo. 
Codificando varie considerazioni contestuali di questo tipo in un insieme di regole da applicare 
all’etichettatura, si ottiene un tagger basato su regole (o rule-based). Nell’esempio appena citato, 
le regole potrebbero essere del tipo: 
 
se trovi la sequenza di etichette ART, AGG 5 la prossima etichetta è NOME 
se trovi l’etichetta PRON.PERS.   5 la prossima etichetta è VERBO 
 
Greene e Rubin hanno sviluppato un etichettatore basato su regole che riesce ad annotare 
correttamente il 77% delle parole [Greene – Rubin, 1971]. 
Il punto debole di questo approccio sta proprio nella difficile realizzazione manuale del set di regole 
che devono in qualche modo racchiudere le molteplici sfumature di un linguaggio naturale. 
 
Tale debolezza è stata eliminata usando metodi basati su statistica: se si dispone di un corpus già 
annotato, da esso si possono ricavare importanti informazioni probabilistiche che agevolano il 
compito dell’etichettatore. In pratica, il tagger deve prima “apprendere” queste informazioni dal 
corpus, per poi sfruttarle nel processo di risoluzione di ambiguità. Si parlerà, in questo caso, di 
etichettatori ad apprendimento automatico. L’apprendimento avviene tramite un ragionamento di 
tipo induttivo che passa dagli esempi alle regole generali (impara cioè dall’esperienza). 
 
Il più semplice funziona secondo il paradigma “scegli l’etichetta più probabile per questa parola”. 
Si prende cioè il testo pre-etichettato (detto testo di apprendimento o training set) e, per tutte le 
occorrenze della parola da annotare X, si considera quali etichette essa assume e con quale 
probabilità. L’algoritmo di risoluzione quindi non fa altro che scegliere l’etichetta risultata più 
probabile da assegnare a X.
- 4 -
Sorprendentemente, questa strategia riesce ad etichettare correttamente circa il 90% delle parole 
[Manning – Schütze, 2003]. Spesso questo metodo viene utilizzato come baseline per il confronto 
delle prestazioni tra i vari tagger. 
 
Un approccio più complesso è quello basato su trasformazioni di Brill [Brill, 1995]. 
L’etichettatore è del tipo rule-based nel processo di risoluzione di ambiguità, ma le regole stavolta 
non sono scritte a mano: esse vengono apprese automaticamente in base al testo pre-etichettato con 
opportuni calcoli probabilistici. Questo etichettatore riesce ad annotare correttamente circa il 96% 
delle parole
2
.
Un metodo alternativo per utilizzare il contesto consiste nel ricavare direttamente dal testo di 
apprendimento dei valori statistici, ovvero le probabilità di occorrenza di determinate sequenze di 
etichette. Questo approccio è chiamato a “n-grammi”, e si basa sul concetto che la migliore etichetta 
per una parola è determinata dalla probabilità che essa compaia con le precedenti n etichette. 
 
Sfruttando gli n-grammi insieme con la strategia di “prendere l’etichetta più probabile”, si realizza 
un approccio che gode dei vantaggi di entrambi i modelli, noto con il nome di Modello di Markov 
Nascosto (in inglese Hidden Markov Model – HMM). 
Gli etichettatori basati su HMM assegnano ad una determinata parola l’etichetta più probabile per 
essa e per le precedenti n etichette. Viene scelta cioè quella che massimizza la quantità: 
 
Questo tipo di etichettatore riesce ad annotare il maggior numero di parole correttamente (96-97%)
3
rispetto agli altri presentati e sarà quello utilizzato in questo progetto. 
Uno dei maggiori vantaggi di questo tipo di architettura consiste nella possibilità di poter effettuare 
l’apprendimento anche nel caso in cui non si disponga di un corpus pre-etichettato
4
. Si parla, in tal 
caso, di apprendimento senza supervisione. Il processo utilizza l’algoritmo iterativo di Baum-Welch.
Prima di descrivere il funzionamento dell’etichettatore in dettaglio, è necessario introdurre il 
Modello di Markov Nascosto. 
1.3 Il Modello di Markov Nascosto (Hidden Markov Model o HMM) 
Un HMM è un processo doppiamente stocastico in cui il processo stocastico sottostante non è 
osservabile. 
Esso genera una sequenza di T simboli osservabili o emissioni: 

 = (o
1
, o
2
, …, o
T
) o
i
 W, per 1 S i S T
dove W (di dimensione M) è l’insieme finito di tutti i possibili simboli. 
 
Il processo stocastico sottostante è composto da un insieme di N stati “non visibili”: 
 
S = {S
1
, S
2
, …, S
N
}
2
Dall’implementazione fatta da ACOPOST sul Wall Street Journal corpus [http://acopost.sourceforge.net/]. 
3
Sempre da un’implementazione fatta da ACOPOST sul Wall Street Journal corpus [http://acopost.sourceforge.net/]. 
4
Spesso la necessità di avere un corpus di grandi dimensioni e di generi diversi di scrittura può essere costosa. 
P(parola | tag) × P(tag | precedenti n tag) 
“prendi l’etichetta più probabile” n-grammi 
- 5 -
L’HMM assumerà, date le T osservazioni, esattamente T stati. Possiamo identificare questa 
sequenza con: 
X = (X
1
, X
2
, …, X
T
) X
k
 S, per 1 S k S T
L’HMM può essere allora descritto da: 
 
- Un vettore  (dimensione N) di stati iniziali: 

i
= P(S
i
= X
1
) la probabilità di cominciare dallo stato S
i
- Una matrice A (dimensione N×N) di probabilità di transizione: 
a
ij
 = P(S
j
| S
i
) la probabilità di passare dallo stato S
i
a S
j
- Una matrice B (N×M) delle probabilità di osservazione: 
b
jk
 = b
j
(w
k
) = P(w
k
| S
j
) la probabilità di osservare il simbolo w
k
se si è nello stato S
j
Figura 1-2 La rappresentazione grafica di un HMM. Gli stati sono i cerchietti, mentre le emissioni i rettangoli. In 
questo caso l’insieme dei simboli è W = {a,b,c}, mentre l’insieme dei possibili stati è S = {S
1
,S
2
,S
3
,S
4
}. 
Le frecce piene indicano le transizioni di stato, mentre quelle tratteggiate indicano le emissioni, insieme 
alle relative probabilità. Gli stati iniziali sono solamente S
1
e S
2
, con probabilità 
1
= 0.4 e 
2
= 0.6. 
1.3.1 Vincoli di struttura dell’HMM 
Siccome queste strutture hanno come coefficienti valori di probabilità, esse vanno vincolate nel 
seguente modo: 
a. La somma di tutti gli elementi di  deve essere pari a 1, perché la possibilità di cominciare 
da almeno uno stato deve essere un evento certo. 
b. La somma di tutti gli elementi di ciascuna riga di A deve essere pari a 1, perché la possibilità 
di passare da uno stato ad un altro deve essere un evento certo. 
c. La somma di tutti gli elementi di ciascuna riga di B deve essere pari a 1, perché la possibilità 
di leggere almeno un simbolo, trovandosi in un qualsiasi stato, deve essere un evento certo. 
 
S
1
S
2
S
3
S
4
0.5
0.5
0.3 0.2
0.5
1.0
1.0
“a” “b” 
0.5
0.5
“b” 
1.0
“a” 
“b” 
“c” 
0.2
0.1
0.7
“c” 
1.0
start 
0.6
0.4