appunti per la lezione

Elaborazione del linguaggio naturale
automi & morfologia
Maria Teresa PAZIENZA
Programma generale





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
Obiettivi dell’NLP
L’ Elaborazione del Linguaggio Naturale (Natural Language Processing, NLP)
ha come obiettivo principale:
 la costruzione di modelli e di strumenti informatici in grado di
eseguire specifici task riguardanti il Linguaggio Naturale, quali:
 Permettere la comunicazione uomo – macchina
 Migliorare la comunicazione uomo – uomo
 Elaborare e manipolare oggetti linguistici a qualunque livello di
granularità
PERCHE’ E’ IMPORTANTE L’ NLP ?
 Sempre maggiore quantità di conoscenza condivisa in testi in
Linguaggio Naturale machine readable (ES: sul Web)
 Necessità di un’interazione più diretta uomo-macchina (ES: agenti
intelligenti)
Intro
Cosa serve ?
CONOSCENZA LINGUISTICA: tutta la conoscenza che ha a che vedere con il
linguaggio (conoscenza relativa a ciò che significhi essere una parola):
Cos’è una parola?
Quali sono le regole per costruire una frase?
Qual è il significato di un sintagma?
MODELLI (teorie): i modelli linguistici hanno lo scopo di catturare la
conoscenza linguistica e rappresentarla in una forma comprensibile per il
computer
ALGORITMI: strumenti per manipolare i modelli e le strutture linguistiche
necessarie per l’analisi e la comprensione del linguaggio (algoritmi per la
gestione di grafi)
Intro
Cosa serve? Modelli
 MODELLI PROCEDURALI:
 Automi a Stati Finiti
 Trasduttori a Stati Finiti
 Markov Models … …
Solitamente un modello procedurale
ha una sua controparte in un modello
dichiarativo (ad es. automi –
grammatiche regolari)
 MODELLI DICHIARATIVI:
 Grammatiche regolari
 Context Free Grammar … …
Un modello può essere più o meno
complesso da un punto di vista
computazionale (ad es. le Context
Free Grammar sono più complesse di
quelle Regolari)
 MODELLI LOGICI:
 Calcolo dei Predicati
 Logica del Primo Ordine … …
Nei diversi modelli possono
generalmente essere integrati elementi
di probabilità (modelli probabilistici)
Cosa devono fare i modelli ? Che analisi devono portare a termine ?
Intro
Livelli di analisi del Linguaggio Naturale
I sistemi di NLP possono operare a diversi livelli di analisi,
ognuno dei quali richiede una specifica conoscenza linguistica .
 FONETICA: studio dei suoni linguistici
 MORFOLOGIA: studio delle componenti significative di una parola
 SINTASSI: studio delle strutture relazionali tra le parole
 SEMANTICA: studio del significato
 PRAGMATICA: studio di come il linguaggio è usato per raggiungere obiettivi
 ANALISI DEL DISCORSO: studio di unità linguistiche complesse
Una architettura per L’NLP può portare a termine uno o più
livelli di analisi, generalmente in cascata
Intro
Livelli di analisi: un esempio
 David : - Apri la saracinesca esterna, Hal.
 Hal : - Mi dispiace David, purtroppo non posso farlo.
 FONETICA: Hal deve essere in grado di analizzare il segnale audio e
ricostruire la giusta sequenza delle parole
 MORFOLOGIA: Hal deve saper rispondere con la giusta flessione: ad
esempio posso e non puoi
 SINTASSI: Hal deve sapere che la saracinesca esterna è un sintagma
nominale complemento oggetto di apri, e che la frase di David è corretta
 SEMANTICA: Hal deve sapere cos’è una saracinesca, e cose vuol dire
aprire qualcosa (in generale ed aprire una saracinesca in particolare)
 PRAGMATICA: Hal deve saper rispondere cortesemente a David
 ANALISI DEL DISCORSO: Hal risponde farlo riferendosi a una frase
del discorso precedente, quindi domina un segmento maggiore della
frase
Intro
Linguaggio Naturale e Linguaggi Formali

Cos’è il Linguaggio Naturale ?
 Strumento di comunicazione tra persone;
 Fatti, idee e conoscenze (sul mondo esterno ed interiore)
 Emozioni
 Ordini
 E’ ambiguo! (“La vecchia porta la sbarra”)

Cos’è un Linguaggio Formale ?
Dato un insieme di simboli  detto alfabeto, un linguaggio formale è un
sottoinsieme di tutte le possibili concatenazioni dei simboli:
L  *
Un linguaggio formale non è ambiguo (una concatenazione di simboli ha una
interpretazione univoca) ed esprime le sue regole in maniera canonica
Un elaboratore può riconoscere e generare solo Linguaggi Formali,
attraverso l’utilizzo di modelli e algoritmi
Intro
Linguaggi Formali
ESEMPIO
={a,b}
*={a,b,aa,ab,ba,bb,aa,baba,baaab,….}
L={ba,baa,baaa,baaaa,….}
Come definire il linguaggio L senza enumerare tutte le stringhe?
 Modello procedurale: automi, regole formali …
 Modello dichiarativo: grammatiche
Intro
Linguaggi Formali e grammatiche
 Una grammatica può essere informalmente intesa come un insieme di
regole per interpretare/generare un linguaggio formale
 iniziando da un simbolo iniziale
 applicando regole che indichino come rimpiazzare alcune sequenze
di simboli con altre combinazioni di simboli (derivazioni)
ESEMPIO
L={ba,baa,baaa,baaaa,…….}
S  Aa
Ab
A  Aa
Intro
Linguaggi Formali e grammatiche
 Una grammatica può essere informalmente intesa come un insieme di
regole per interpretare/generare un linguaggio formale
 iniziando da un simbolo iniziale
 applicando regole che indichino come rimpiazzare alcune sequenze
di simboli con altre combinazioni di simboli (derivazioni)
Formalmente:
Una grammatica è una quadrupla (N, ,S, P) dove:
– N è l’alfabeto dei simboli non-terminali
–  è l’alfabeto dei simboli terminali
– S è elemento di N detto simbolo iniziale
– P è un insieme finito di produzioni, ovvero:
• se V è definito come N  Σ , allora le produzioni di P hanno la
forma , dove V+ V*
Intro
Linguaggi Formali e grammatiche
Un linguaggio formale è un insieme di stringhe
Un linguaggio formale non è un linguaggio naturale, ma può
essere usato per modellare parte di un linguaggio
naturale
Un linguaggio formale può essere più o meno complesso,
ed essere quindi computazionalmente più o meno
esigente.
Intro
Linguaggi Formali: complessità
La gerarchia di Chomsky è un tentativo di ordinare le grammatiche che
generano i linguaggi in base alla loro complessità
+
COMPLESSITA’
-
GERARCHIA DI CHOMSKY
Type 0 Grammars - Unrestricted
  , || 1 and || 1.
Type 1 Grammars - Context-Sensitive
  , || 1 and || 1 and || ||
Type 2 Grammars - Context-Free
  , || = 1 and || 1
Type 3 Grammars - Regular
• left-linear regular grammar: (or )
• right-linear regular grammar: (or )
+
POTERE
GENERATIVO
-
Intro
Linguaggi Formali: complessità
 Le grammatiche sono modelli dichiarativi
 I corrispondenti modelli procedurali sono:
• Type 0 Grammars - Unrestricted
Turing Machine
• Type 1 Grammars - ContextSensitive
Turing Machine
• Type 2 Grammars - Context-Free
Push-down automaton
• Type 3 Grammars - Regular
Finite State Automaton (FSA)
Intro
Linguaggi Formali: complessità
DOMANDA:
Il Linguaggio Naturale può essere rappresentato attraverso un Linguaggio
Formale ?
Se si, un Linguaggio Formale di quale complessità ?
Quanto è complesso il Linguaggio Naturale ?
Intro
Linguaggi Formali e Linguaggio Naturale
 … dipende da quale linguaggio naturale ….
 un livello alto nella gerarchia vuol dire che il linguaggio naturale è
strutturalmente complesso (Tipo 0)
 ITALIANO
 In generale, sembrerebbe “catturabile” da una Grammatica Regolare (Tipo 3)
 ECCEZIONE: costrutti “center-embedded”. Ad esempio:
“Moggi, Giraudo e Bettega erano
rispettivamente DG, amministratore
delegato e vicepresidente della Juventus”
ha struttura an bn
 Sembrerebbe quindi un linguaggio più complesso, ovvero Context-Free (Tipo 2)
 E’ più complesso? No, perché sembra non avere costrutti del tipo anbncn
Intro
Linguaggi Formali e Linguaggio Naturale
 L’italiano è quindi un linguaggio mediamente complesso (Tipo 2)
 E gli altri linguaggi naturali ?
 Inglese:
Context-Free
Tipo 2
 Olandese:
Context-Sensitive
Tipo 1
(Huybregt,1976)
presenta costrutti “cross-serial”. Ad esempio:
“dat Jan Marie Pieter Arabisch laat zien schrijven”
(*THAT JAN MARIE PIETER ARABIC LET SEE WRITE)
‘that Jan let Marie see Pieter write Arabic’
Intro
Linguaggi Formali e Linguaggio Naturale
La sintassi italiana e quella inglese sembrano essere Context-Free
 La morfologia, invece, sembra essere ancora più semplice: può essere infatti
rappresentata da grammatiche Regolari
QUINDI, NEL CORSO VEDREMO:
MORFOLOGIA

Automi a Stati Finiti (FSA)
SINTASSI

Grammatiche Context-Free (CFG) Tipo 2
Tipo 3
Intro
Morfologia
La morfologia è lo studio di come le parole sono costruite a partire da
unità atomiche dette morfemi.
I morfemi sono le più piccole unità linguistiche che possiedono un
significato. Ne esistono due classi:
- Radice  il morfema che dà il significato principale alla parola
- Affisso  il morfema che dà significato aggiuntivo alla parola
ESEMPIO
radice
gatt–o gatt–i
acquist-o acquist-are
affisso
Morfologia
Analisi Morfologica: Automi a Stati Finiti
Strumenti per l’analisi morfologica :
- Automi a Stati Finiti (FSA)
 Riconoscimento
- Finite State Transducers (FST)
 Parsing
RICONOSCIMENTO : indica se una data parola in input è morfologicamente
corretta o no (ad esempio gatti è corretta, gattare è scorretta)
PARSING : produce un’analisi morfologica della parola in input (ad esempio
gatti  gatto N PL)
Sia FSA che FST sono di tipo 3 nella gerarchia di Chomsky: l’analisi
morfologica può essere quindi portata a termine con strumenti
relativamente poco complessi
Morfologia
Analisi Morfologica: qualche esempio
Un analizzatore morfologico completo dovrebbe essere in grado di
riconoscere la classe (nomi, verbi, ecc.) delle parole e la loro
morfologia:
house
house+N+SG
houses
house+N+PL
went
go+V+PastTense+123SP
play
play+V+Pres+non3SG
played
played+A+VPap
miaow
miaow+Onomatop
Morfologia
Espressioni regolari

Espressione regolare: notazione algebrica per descrivere un insieme di stringhe

Una Espressione Regolare descrive un FSA

Un FSA implementa un’espressione regolare
Le espressioni regolari sono un (meta)linguaggio per specificare “stringhe di
caratteri” (per una ricerca sul web per es., così come per una qualunque
applicazione di information retrieval, per sistemi di word processing, calcolo
della frequenza di termini in corpora, etc.).
La ricerca di una espressione regolare identifica un pattern specifico che si vuole
ricercare ed un corpus di testi all’interno del quale effettuare la ricerca. Come
risultato si ottengono - tutti quei testi che contengono quel pattern -.
Una espressione regolare è una formula in un linguaggio speciale (notazione
algebrica) usato per specificare semplici classi di stringhe. Una stringa è una
sequenza di simboli (caratteri alfanumerici – anche lo spazio viene
considerato un carattere)
Espressioni regolari
Espressione regolare: notazione algebrica per descrivere un insieme di
stringhe
Operatori base:

*

zero o più occorrenze del carattere precedente (ciò che è
racchiuso tra [ ] ) (Kleene *)

+

una o più occorrenze del carattere precedente (ciò che è
racchiuso tra [ ] ) (Kleene +)



?

zero o una occorrenze del carattere precedente (ciò che è
racchiuso tra [ ] )
[a|A]  disgiunzione di simboli
[a-A]  range di simboli
Esempi:

a*
si deriva che L={e,a,aa,aaa,…}

[ab]+ si deriva che L={a,b,aa,bb,ab,ba,…}

altri esempi sul libro….
Le espressioni regolari sono case sensitive
La stringa di caratteri tra parentesi specifica una disgiunzione di caratteri da trovare
Automi a Stati Finiti (FSA)
Un automa a stati finti è un automa in grado di riconoscere o di generare
una sequenza di simboli (stringa) di un alfabeto.
Formalmente: Un FSA è un grafo orientato i cui nodi sono detti stati e i cui archi
sono detti transizioni
Caratteristiche principali:
- molto efficienti (tipo 3 nella ger. di Chomsky)
- facili da implementare
ESPRESSIONI REGOLARI
- Ogni FSA implementa una espressione regolare
- Ogni espressione regolare descrive un FSA
- Ogni FSA descrive un linguaggio regolare
FSA
LINGUAGGI
REGOLARI
Utilizzi principali in linguistica:
- Riconoscimento morfologico
- Fonetica
- Text-to-Speech
FSA: semplice esempio
FSA per riconoscere e generare sequenze di simboli appartenenti al linguaggio (regolare) delle
caprette inglesi, descritto dall’espressione regolare: /baa+!/. In figura un automa che
modella tale espressione regolare.
SIMBOLO
STATO
INIZIALE
STATO
TRANSIZIONE
STATO
FINALE
FSA come riconoscitore: riconosce/accetta tutte le stringhe in input
del tipo baa! , baaa! , baaaa!, … …qualunque altra stringa viene
rigettata (reject).
FSA come generatore: genera tutte le stringhe del tipo baa! , baaa!,
baaaa!, … …
FSA
FSA: definizione formale
Un FSA è definito dai seguenti 5 parametri:
- Q : un insieme finito di N stati q0….qN
- Σ : un alfabeto finito di simboli
- q0 : lo stato iniziale
- F : un insieme di stati finali FQ
-δ(q,i) : relazione di transizione tra stati che restituisce un nuovo stato a
partire da un dato stato e un simbolo in input; δ è una relazione da Qx Σ a Q
Un FSA può essere anche rappresentato
attraverso una state-transition table
FSA
FSA e linguaggi formali
L’insieme delle stringhe riconosciute (o generate) da un FSA definiscono un
linguaggio formale.
LINGUAGGIO FORMALE (L): insieme di stringhe composte da
simboli appartenenti a un insieme finito di simboli Σ detto alfabeto
- L’insieme delle stringhe riconosciute da un FSA costituisce il linguaggio
accettato dall’automa
- L’insieme delle stringhe generate da un FSA costituisce il linguaggio
generato dall’automa
- Per un FSA, il linguaggio generato e quello accettato corrispondono
ESEMPIO
Σ = {a,b,!}
L = {baa!,baaa!,baaaa!,….}
FSA
FSA e linguaggi regolari
Un FSA (o un’espressione regolare) può definire un sottoinsieme particolare
dei linguaggi formali, i linguaggi regolari
LINGUAGGIO REGOLARE (L):
Dato un alfabeto :
– L’insieme vuoto  è un linguaggio regolare
– a    e, {a} è un linguaggio regolare
– Se L1 e L2 sono linguaggi regolari, allora lo sono anche:
• L1 · L2 = {xy|x  L1,y  L2}, concatenazione di L1 & L2
• L1  L2, unione di of L1 e L2
• L1*, la Kleene closure (o ripetizione) di L1
FSA
FSA e linguaggi regolari
LIMITI: I linguaggi regolari hanno un basso potere generativo (tipo 3)
-
Ad esempio, dato l’alfabeto Σ={a,b}, nessun FSA può generare
stringhe del tipo anbn (a fronte della definizione slide precedente)
Gli FSA modellano quindi bene fenomeni linguistici semplici come:
- Morfologia
- Fonetica
-
Gli FSA non possono modellare fenomeni linguistici complessi come:
- Sintassi
ESEMPIO (english)
The cat likes tuna fish
L = xn yn-1 likes tuna fish.
The cat the dog chased likes tuna fish
The cat the dog the rat bit chased likes tuna fish
The cat the dog the rat the elephant admired bit chased likes tuna fish
FSA
FSA come riconoscitori
SCOPO: Data una stringa in input verificare se essa appartiene al
linguaggio formale definito dall’automa.
ALGORITMO DI RICONOSCIMENTO
indice  inizio stringa in input
Stato-corrente  q0
WHILE (input)
IF vuota(trans-table[stato-corrente,stringa[indice]])
return reject
ELSE
stato-corrente trans-table[stato-corrente,stringa[indice]]
indice  indice +1
IF (stato-corrente è stato finale)
return accept
ELSE
return reject (non esiste alcuna transizione legale per una
data combinazione di stato ed input)
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: 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
Automi a Stati Finiti deterministici o non
deterministici (DFSA, NFSA)
Negli automi non deterministici (NFSA) possono esistere
degli stati che prevedono più di una possibile transizione
per passare ad uno stesso stato, ovvero esistono dei
punti in cui bisogna prendere una decisione.
Gli automi DFSA, invece, sono automi il cui comportamento
durante la fase di riconoscimento è totalmente
determinato dallo stato in cui si trova e dal simbolo con
cui si è giunti a quello stato.
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), si 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)
Argomenti trattati in questa lezione
•
•
•
•
•
•
Analisi del linguaggio naturale: tipologia, livelli
Linguaggi formali (grammatiche, complessità)
FSA, FST, espressioni regolari
DFSA, NFSA
ε-transizioni (o jump arcs)
state-space search
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.