Elaborazione del linguaggio naturale
automi, trasduttori & morfologia
Maria Teresa PAZIENZA
a.a. 2007-08
Programma





Breve introduzione all’NLP

Linguaggi Naturali e Linguaggi Formali

Complessità
Morfologia

Teoria: Morfologia del Linguaggio Naturale

Strumenti: Automi e Trasduttori

Analisi Morfologica: con automi e trasduttori
Part of Speech Tagging

Teoria: Le classi morfologiche

Strumenti a Analisi: modelli a regole e statistici
Sintassi

Teoria: Sintassi del Linguaggio Naturale

Strumenti: CFG

Analisi Sintattica: parsing top-down, bottom-up, Early
Semantica

Lexical Semantics

Sentence Semantics
Info
Sommario
Strumenti per la Morfologia
• Automi a stati finiti (FSA)
•
•
•
•
FSA deterministici
FSA non-deterministici (NFSA)
Introduzione alla Morfologia
FSA e Morfologia: riconoscimento
• Trasduttori a stati finiti (FST)
• Cosa sono
• FST e Morfologia: parsing
FSA: semplice esempio
FSA per riconoscere e generare sequenze di simboli appartenenti al linguaggio (regolare) delle
caprette, descritto dall’espressione regolare: /baa+!/
SIMBOLO
STATO
INIZIALE
STATO
TRANSIZIONE
STATO
FINALE
FSA : il suo comportamento durante la fase di riconoscimento è totalmente
determinato
1. dallo stato in cui si trova e
2. dal simbolo in arrivo.
FSA
FSA non-deterministici (NFSA)
Un automa è detto non-deterministico se ha due archi uguali uscenti dallo
stesso stato.
Quindi:
- Deterministico vuol dire che ad ogni stato può essere presa una sola decisione
- Non-Deterministico vuol dire che ad ogni stato si può scegliere tra più decisioni
Equivalenza tra FSA e NFSA
- Un NFSA può essere sempre convertito in un FSA equivalente (che definisce cioè
lo stesso linguaggio)
- NFSA e FSA hanno quindi lo stesso potere di riconoscimento/generazione
- L’FSA equivalente di un NFSA ha sempre più stati dell’NFSA
NFSA
FSA non-deterministici (NFSA)
Un tipo particolare di non-determinismo è quello causato dalla presenza di εtransizioni (o jump arcs) ovvero da archi/transizioni non legati ad alcun
simbolo ingresso.
ε
Una ε-transizione corrisponde ad un passaggio di stato che non influenza la stringa
in esame:
- in riconoscimento: non viene letto il simbolo corrente della stringa
-in generazione: non viene prodotto alcun simbolo
In questo caso si introduce una forma di non determinismo in quanto non si sa se
seguire la transizione ε oppure l’arco !
NFSA
FSA non-deterministici (NFSA)
Un tipo particolare di non-determinismo è quello causato dalla presenza
di ε-transizioni (o jump arcs) ovvero da archi/transizioni non legati ad
alcun simbolo ingresso.
Possibili soluzioni:
1. Backup: inserire un marker per indicare un punto su cui siamo già
passati
2. Look-ahead: guardare avanti per decidere quale percorso scegliere
3. Parallelismo: in uno stato con più scelte, verificare in parallelo
percorsi alternativi
NFSA
FSA non-deterministici (NFSA)
Algoritmo di backup:
quando si raggiunge un punto con nessuna possibilità di
andare avanti (no input oppure nessuna transizione
legale), ri ritorna al precedente punto di decisione , si
selezione una delle alternative ancora non esplorate, e
si continua da quella fase.
In questo NFSA, per ciascun punto di scelta, bisogna
solo ricordare lo stato in cui ci si trova (nodo) e la
posizione corrispondente sul nastro in input.
La combinazione di stato e posizione del nastro
corrispondente (search-state)
nel suo insieme costituisce lo spazio di ricerca
FSA non-deterministici: ricerca
Riconoscimento: negli stati non-deterministici l’FSA può seguire strade
diverse, ovvero prendere decisioni errate. In tal caso deve essere in grado di:
- Riconoscere la soluzione errata;
- Cercare altre soluzioni prendendo strade diverse;
- Ricordare quali sono le strade diverse
L’automa deve quindi effettuare una ricerca nello spazio delle
soluzioni (state-space search)
Ad ogni bivio (choice point) devono quindi essere memorizzate in una agenda tutte le
coppie di stati alternativi e la posizione nella stringa dopo la transizione δ (search-states)
SEARCH STATES
STATO CORRENTE
q2, [b,a,a,a,a]
q3, [b,a,a,a,a]
q2, [b,a,a,a,a]
NFSA
Ricerca in NFSA: esempio
b
q0
a
q1
a
a
q2
q2
!
q3
\
q4
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Profondità NFSA: esempio
NFSA
Ricerca in Ampiezza NFSA: esempio
NFSA
Ricerca in NFSA: algoritmo di ricerca
NFSA
Ricerca in NFSA: algoritmo di ricerca
L’algoritmo produce in uscita un reject solo quando l’agenda diventa
vuota (quindi non alla fine del nastro in uno stato di nonaccettazione, nè per affermare che il nastro non può avanzare in
un nuovo stato).
Essendo in una situazione di non-determinismo, si indica un errore
in un dato percorso, non un insuccesso totale.
Si rigetta una stringa solo quando tutte le scelte possibili sono state
prese in esame e si è arrivati ad un insuccesso. Lo spazio degli
stati consiste di tutte le coppie possibili (stato, posizione); la
ricerca avverrà navigando attraverso questo spazio cercando una
coppia con stato accept e posizione fine nastro.
Ruolo dell’ordine con cui avviene la ricerca (si possono esaminare
molte situazioni non utili prima di incontrare quella corretta).
(profondità verso ampiezza, stack verso coda)
Sommario
Strumenti per la Morfologia
• Automi a stati finiti (FSA)
•
•
•
•
FSA deterministici
FSA non-deterministici (NFSA)
Introduzione alla Morfologia
FSA e Morfologia: riconoscimento
• Trasduttori a stati finiti (FST)
• Cosa sono
• FST e Morfologia: parsing
Morfologia: definizioni
La morfologia (morphology) è lo studio di come le parole sono costruite
a partire da unità atomiche dette morfemi.
I morfemi (morphemes) sono le più piccole unità linguistiche che
possiedono un significato. Possono essere divisi in due classi:
- Radice (stem) il morfema che dà il significato principale alla parola
- Affisso (affix) particelle apposte alla radice che ne completano il
significato e la funzione grammaticale
ESEMPIO
radice
gatt-o gatt-i
buy-s
affisso
buy - er
Morfologia
Morfologia: definizioni
La morfologia può essere divisa in due parti principali
- Inflectional Morphology: combinazione di una radice con un affisso che risulta
in una parola (forma flessa) della stessa classe (nome, verbo, aggettivo, ecc..)
con una funzione grammaticale specifica
 cat (nome sing) cat-s (nome plur)
 cut (verbo base) cut-ting (verbo progressivo)
- Derivational Morphology: combinazione di una radice con un affisso che
risulta in una parola di una classe diversa. Il significato della nuova parola non
è facilmente prevedibile
 trasporto (nome)  trasport-abile (aggettivo)
 computerize (verbo)  computeriz-ation (nome)
Morfologia
Quante morfologie ?
Ogni linguaggio naturale ha una sua morfologia (affissi, regole, ecc.)
Due classi principali:
- Concatenative morphology: una parola è composta da morfemi
concatenati insieme
 Italiano, Inglese: gatt-o, cat-s, buy-er
- Non-concatenative morphology: le parole sono composte in maniera
complessa
 Ebraico: lamad (radice: lmd; affissi: a-a pass.rem.attivo)
Lingue agglutinanti: le parole sono formate da molti affissi
 Turco: uygarlaştiramadiklarimizdanmişsinizcasina
(“comportarsi come se fossi tra quelli che non possono civilizzare”)
Morfologia
Morfologia inglese
Caratteristiche:
- Concatenative morphology
- Non-agglutinative (al più 4 o 5 affissi)
- Una parola può avere più affissi:
- Prefissi:
- Suffissi:
un-certain
eat-s
- Combinazioni:
un-clear-ly
- Inflectional morphology: semplice, applicata solo a nomi, verbi e aggettivi
- Derivational Morphology: complessa
Morfologia
Inflectional Morphology
NOMI:
Due solo inflessioni:
- Plurale:
- Possessivo:
cat  cat-s
dog  dog’s
thrush thrush-es
children  childrens’
VERBI:
Quattro forme morfologiche:
- stem:
walk
- s form:
walk walk-s
- past form:
walk walked
- ing form:
walk walking
che non seguono le regole morfologiche (Esempio:mouse mice
go goes, going, went). La maggior parte dei nomi e verbi inglesi sono regolari
- Irregolari:
(ca. 250) Parole
- La classe dei verbi regolari è produttiva : una nuova parola della lingua è automaticamente
inclusa nella classe (Esempio: fax  faxes,faxing, faxed )
Morfologia
Derivational Morphology
nominalizzazione (verbo, aggettivo nome)
-ation
computerize
computerization
-ee
appoint
appointee
-er
kill
killer
-ness
fuzzy
fuzziness
nome, verbo aggettivo
-al
Computation
Computational
-able
Embrace
Embraceable
-less
Clue
Clueless
Morfologia
A cosa serve l’analisi morfologica automatica?
- Stemming in Information Retrieval
 Data una parola della query, cercare le pagine che contengano
anche le sue forme flesse
- Spell Checking
 Riconoscere quali forme flesse sono ammissibili in una lingua e
quali no (ad esempio gatt-o e gatt-are)
- Traduzione Automatica
 Ricondurre parole diverse a una stessa radice e quindi alla
stessa traduzione (ad esempio amatore, amare  love)
Morfologia & FSA
Quali strumenti usare ?
- Lessico esteso
 Un lessico (lista di parole) che contiene tutte le parole della lingua in
tutte le forme flesse
 Spreco di spazio e non è produttivo!
- Lessico ridotto + Automi
 La morfologia è generalmente produttiva (gran parte delle parole segue
le regole morfologiche per formare le forme flesse)
 Conviene quindi utilizzare:
 Lessico contenente solo radici e affissi (ed eventualmente irregolarità)
 Implementazione delle regole morfologiche in un dispositivo
 FSA sono semplici dispositivi per implementare tali regole
Morfologia & FSA
Sommario
Strumenti per la Morfologia
• Automi a stati finiti (FSA)
•
•
•
•
FSA deterministici
FSA non-deterministici (NFSA)
Introduzione alla Morfologia
FSA e Morfologia: riconoscimento
• Trasduttori a stati finiti (FST)
• Cosa sono
• FST e Morfologia: parsing
FSA: riconoscimento
Un FSA può essere utilizzato per riconoscere se una parola è
ammissibile in una lingua - Cosa serve?
Lessico: lista di radici ed affissi della lingua (invece di lista di tutte le parole
della lingua – troppo lunga e non esaustiva)

1.
Esempio: [cat,dog,cut,go,…,-s,-ed,-ation,-able,…,un-,dis-]
Regole Morfologiche (morphotactics): le regole di costruzione dei
morfemi che spiegano come classi di morfemi possono seguire altre
classi di morfemi in una parola

Esempio: Plurale inglese: radice + -s
2. Regole Ortografiche: cambiamenti che occorrono in una parola quando
due morfemi si combinano

Esempio: city  cities
Morfologia & FSA
NOMI: regole morfologiche
FSA per modellare l’inflessione plurale per nomi regolari ed irregolari
Come modellare i nomi (regolari ed irregolari) nell’FSA?
Ovvero: Come si può integrare il lessico?
Morfologia & FSA
NOMI: regole morfologiche + lessico
Integrazione del lessico dei nomi regolari ed irregolari
R
E
G
O
L
A
R
I
I
R
R
E
G
O
L
A
R
I
Morfologia & FSA
Sommario
Strumenti per la Morfologia
• Automi a stati finiti (FSA)
•
•
•
•
FSA deterministici
FSA non-deterministici (NFSA)
Introduzione alla Morfologia
FSA e Morfologia: riconoscimento
• Trasduttori a stati finiti (FST)
• Cosa sono
• FST e Morfologia: parsing
Dal Riconoscimento al Parsing
RICONOSCIMENTO : indica se una data parola in input è morfologicamente
corretta oppure no (ad esempio gatti è corretta, gattare è scorretta)
FSA
PARSING/GENERAZIONE :
- parsing: produce un’analisi morfologica della parola in input: data la
parola in input viene restituita la sua struttura
cats cat +N +PL
- generazione: data una struttura morfologica in input, produce una
forma superficiale (parola)
cat +N +PL  cats
FST
FST
Trasduttori a Stati Finiti (FST)
I Trasduttori sono automi a stati finiti con due nastri A e B
Ad es, può leggere da un nastro (ad es. “cats”) e scrivere sull’altro (“cat + N + PL”)
Quattro modalità di utilizzo dell’ FST:
riconoscitore: riceve in input una coppia di stringhe su A e B, e restituisce
accept se essa appartiene al linguaggio delle coppie (una stringa per nastro)
 cats, cat+N+PL  accept
produttore: restituisce coppie di stringhe appartenenti al linguaggio su A e B
 Output: tutte le parole del lessico con la loro struttura
traduttore: riceve in input una stringa su A (o B) e ne restituisce un’altra su B (o
A)
 cats  cat+N+PL (PARSING)
 cat+N+PL  cats (GENERAZIONE)
correlatore: correla set di stringhe in A e B
FST
FST: definizione formale
Un FST è definito dai seguenti parametri:
- Q : un insieme finito di N stati q0….qN
- Σ : un alfabeto finito di simboli complessi. Ogni simbolo complesso è una coppia (uno
per nastro) di simboli i:o appartenenti rispettivamente agli alfabeti I e O (Σ  I x O)
- q0 : lo stato iniziale
- F : un insieme di stati finali FQ
-δ(q,i:o) : funzione di transizione tra stati (relazione da Q x Σ a Q) che restituisce un
nuovo stato a partire da un dato stato e un simbolo complesso in input
ESEMPIO di utilizzo di un FST
:
- riconosce tutte le coppie di stringhe in cui una ha tutte a e l’altra uno
stesso numero di b
- produce stringhe di a su un nastro e stringhe di b sull’altro, con la
stessa lunghezza
- traduce stringhe di a in input in stringhe di b della stessa lunghezza
in output, e viceversa
FST
Trasduttori a Stati Finiti (FST)
Un FSA definisce un linguaggio formale
attraverso la definizione di un insieme di stringhe
– un FSA è isomorfo ai linguaggi regolari
Un FST definisce una relazione tra insiemi di
stringhe – un FST è isomorfo alle relazioni
regolari
Ovvero l’FST esprime il concetto della relazione tra due entità
formalmente definite
Trasduttori a Stati Finiti (FST)
Un FST gode delle proprietà di
Inversione: l’inversione di un transducer T (T -1) cambia
l’input in output - se T correla l’input I all’ouput O, T -1
correla l’input O all’ouput I
Composizione:
se T1 è un transducer da I1 ad O1 ,
e T2 è un transducer da I2 ad O2,
allora T1 ◦T2 correla I1 ad O2
La proprietà di inversione inverte i ruoli di input ed output, facendo passare
il FST da un ruolo ad un altro (da parser a generatore)
La proprietà di composizione permette di porre più transducer in serie ed
ottenere un transducer più complesso
FST: -transizioni
Come gli FSA, anche gli FST possono avere ε-transizioni (o jump arcs)
ESEMPIO
:
:
- riconosce tutte le coppie di stringhe
in cui quella sul primo nastro ha tutte
a e quella sul secondo un numero
doppio di b
- produce le coppie di stringhe …
ε:
- traduce stringhe di a in input in
stringhe di b di lunghezza doppia
Σ = {a:b,:b}
L = {0,abb,aabbbb,aaabbbbbb…}
FST
Sommario
Strumenti per la Morfologia
• Automi a stati finiti (FSA)
•
•
•
•
FSA deterministici
FSA non-deterministici (NFSA)
Introduzione alla Morfologia
FSA e Morfologia: riconoscimento
• Trasduttori a stati finiti (FST)
• Cosa sono
• FST e Morfologia: parsing
FST e morfologia: parsing
OBIETTIVO:
Livello Superficiale
Livello Lessicale
Passare da un livello superficiale ad un livello lessicale e viceversa,
utilizzando un FST in funzione di traduttore:
 cats  cat+N+PL (PARSING)
 cat+N+PL  cats (GENERAZIONE)
Morfologia & FST
FST e morfologia: parsing
OBIETTIVO:
c:c
a:a
t:t
N:ε
PL:s
Passare da un livello superficiale ad un livello lessicale e viceversa,
utilizzando un FST in funzione di traduttore:
 cats  cat+N+PL (PARSING)
 cat+N+PL  cats (GENERAZIONE)
Morfologia & FST
Analisi morfologica a due stadi
Dal livello superficiale al livello lessicale (PARSING)
Sono necessari due stadi (  due trasduttori)
1.
IDENTIFICAZIONE DEI MORFEMI: Data la parola in input sul nastro A, il
trasduttore la divide su B nei morfemi costituenti (radice + affissi)
2.
IDENTIFICAZIONE DELLA STRUTTURA: Dati i morfemi costituenti sul
nastro A, il trasduttore identifica la categoria della radice e il significato
degli affissi
Livello Superficiale
Livello Intermedio
Livello Lessicale
P
A
R
S
I
N
G
Morfologia & FST
Stadio 1: Identificazione dei morfemi
ESEMPIO: nomi singolari/plurali
Obiettivo

Rappresentare con un FST le regole ortografiche della lingua per i nomi
regolari e irregolari

Input: cats
Output: cat+s
Regola e-insertion
cats  cat+s
foxes fox+s
+
kisses  kiss+s
s:s
s:s, z:z, x:x
s:s, z:z, x:x
+
s:s
Morfologia & FST
Stadio 1: non è così facile …
Problemi

Il trasduttore gestisce solo la regola della e-insertion, e non
altri casi:

Regola y-replacement: berries  berry +s

Regola raddoppio consonanti: beg  begging

Ecc. ecc.
(berrie +s)

Bisogna quindi implementare più regole ortografiche, nello
stesso trasduttore, o in trasduttori paralleli!

Ambiguità locale: foxes produce due forme di cui solo la
prima è corretta: fox+s , foxe+s, foxes.
Morfologia & FST
Stadio 2: Identificazione della struttura
ESEMPIO: nomi singolari/plurali
Obiettivo

Rappresentare con un FST le regole morfologiche della lingua per i nomi
regolari e irregolari

Input: cat+s, mouse, mice
Output: cat N PL, mouse N SG, mouse N PL
reg:reg
irr_sing:irr_sing
irr_plur:irr_sing
Bisogna aggiungere il lessico !
Morfologia & FST
Stadio 2: Identificazione della struttura
ESEMPIO: nomi singolari/plurali
Stadio 1+2: Combinare lessico e regole
E’ possibile combinare i due stadi mettendo in cascata (serie) i due trasduttori:
l’output dell’uno sarà l’input dell’altro (bottom-up parsing, top-down
generazione)
Livello Lessicale
Livello Intermedio
in serie o in
parallelo
Livello Superficiale
Oppure, è possibile fondere i due trasduttori, attraverso un’operazione di
intersezione
Morfologia & FST
Vantaggi e problemi
Vantaggi degli FST

Computazionalmente efficienti

Semplici

Doppio uso: parsing e riconocimento

Qual’è la morfologia di foxes ?
foxes fox+N+PL

Qual è il plurale di fox ?
Fox+N+PL  foxes
Problemi

Laborioso costruire e codificare un trasduttore per gestire ogni regola ed
eccezione:


Soluzione: Tool automatici di traduzione regolaFST
Ambiguità globale: kisses può essere sia verbo che nome

kisses kiss+N+PL kisseskiss+V+3SG

Per disambiguare sono necessarie risorse esterne (non morfologiche), ad
esempio il contesto sintattico
Morfologia & FST
Argomenti trattati in questa lezione
•
•
•
•
DFSA, NFSA
ε-transizioni (o jump arcs)
state-space search
Morfologia (derivazionale/inflezionale,
concatenativa/non-concatenativa, FSA e
riconoscimento, FST e loro proprietà)
Elaborazione del linguaggio naturale
Le presentazioni sugli argomenti di elaborazione del linguaggio
naturale fanno in alcuni passi riferimento ad alcune presentazioni
dei colleghi prof. Fabio Massimo Zanzotto e dottor Marco
Pennacchiotti, oltre che ad alcune parti del libro: Speech and
Language Processing, Prentice Hall, 2000, autori D.Jurafsky, J.
H. Martin.