Natural Language Processing
Parte 3: Sintassi e grammatica
chunking e costituenti
2
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Sintassi
•  La sintassi fornisce le regole con cui le parole sono organizzate in
una frase a livello dei seguenti elementi
▫  Costituenti – la sintassi di basa su regole i cui token sono in genere
gruppi di parole (chunks) che a livello sintattico sono viste come unità
  es. la parte nominale - noun phrase – che comprende gruppi costituiti da
sostantivi, articoli, aggettivi (the big house, a red and large carpet, …)
▫  Relazioni grammaticali – rappresentano la formalizzazione della
struttura di una frase come legame fra SOGGETTI e OGGETTI
  es. [he]/SUBJECT took [the big hammer]/OBJECT
▫  Sottocategorizzazioni e relazioni di dipendenza – sono regole che
esprimono vincoli sulle relazioni fra parole e gruppi frasali
  es. volere può reggere un infinito o avere un complemento oggetto (voglio
camminare, voglio una pizza) mentre trovare può avere solo un complemento
oggetto (ho trovato un amico)
3
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Costituenti e chunking
•  In genere più parole sono raggruppate a formare un costitutente o
chunk che ha una specifica funzione
▫  Una tipologia di costituente, es. una parte nominale (noun phrase NP),
può comparire solo in certi contesti, es. NP prima del verbo
  [il volo da Parigi] arriva in ritardo
  [l’auto nuova di Filippo] è parcheggiata…
▫  Altre tipologie di costituenti possono avere più possibilità di costruzione
(preposta, postposta)
  [Il 17 giugno] farò l’ultima lezione/Farò l’ultima lezione [il 17 giugno]
▫  In ogni caso le parole che compogono il chunk sono sempre organizzate
in un gruppo unico
▫  I chunk possono essere modellati con grammatiche Context Free
4
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Grammatiche CF e chunk
•  Le regole seguenti possono descrivere (parzialmente) la struttura di una
noun phrase (NP)
NP → Det Nominal
Det → a | the
NP → ProperNoun
Nominal → Noun | Noun Nominal Noun → flight | plane | arrival
▫  Una parte delle regole è di fatto il lessico che associa ad ogni parola il
simbolo terminale della PoS corrispondente
•  Una verb phrase (VP) consiste di un verbo eventualmente seguito da una
serie di altri chunk come una NP o prepositional phrase (PP)
VP → Verb
mangio
VP → Verb NP
mangio una pizza
VP → Verb NP PP
mangio una pizza con la forchetta
VP → Verb PP mangio con la forchetta 5
Marco Maggini
Chunks –
Tecnologie per l'elaborazione del
linguaggio
PP e frasi
•  Una parte preposizionale (PP) è un gruppo di parole generalmente
introdotto da una preposizione
PP → Preposition NP
con la forchetta bianca di plastica
▫  Le PP possono essere anche molto complesse
•  Un modello semplice per la frase completa (che rappresenta lo
scopo S del linguaggio) è
S → NP VP
[S[NPIl mio amico] [Vpmangia la forchetta bianca di plastica]]
6
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Costruzioni a livello di frase
•  Ci sono molte strutture possibili per le frasi e per l’Inglese le 4
principali sono
▫  dichiarative
S → NP VP
The plane will land in the afternoon
▫  imperative
S → VP
List all the flights to New York
▫  domande si/no
S → Aux NP VP
Will the plane arrive on time?
▫  domande chi/cosa (wh-subject-question/wh-non-subject-question)
S → Wh-NP VP
Which flights depart at night?
S → Wh-NP Aux NP VP Which flights does UA have from NYC?
7
Marco Maggini
NP: Noun Phrase -
Tecnologie per l'elaborazione del
linguaggio
1
•  Una NP ha un sostantivo principale (head) a cui si possono
aggiungere dei modificatori prima (prenominale) o dopo
(postnominal)
▫  In genere una NP inizia con un determinatore (a, the, this, any,..) ma può
anche essere omesso se il sostantivo head è plurale (es. UA flights are
based in..) ed è omesso se è un sostantivo non contabile (es. water is a
public resource)
▫  Possono essere presenti dei pre-determinatori (all the passengers)
▫  Fra il determinatore e il sostantivo principale possono esserci varie classi
di parole (post-determinatori)
  numeri cardinali (the two flights) o ordinali (the first flight) e quantificatori
(many flights)
  aggettivi raggruppabili in una parte aggettivale (AP – Adjective phrase) che
oltre all’aggettivo può includere un avverbio (very expensive)
8
Marco Maggini
NP: Noun Phrase -
Tecnologie per l'elaborazione del
linguaggio
2
•  Considerando le parti prenominali (opzionali) si può definire un modello
semplificato della NP
NP → (Det) (Card) (Ord) (Quant) (AP) Nominal
•  Il sostantivo principale (head) può essere seguito da modificatori
postnominali
▫  Parti preposizionali (PP)
Nominal → Nominal PP (PP) (PP)
flights from Rome to NYC by UA
▫  Forme con gerundio – la parte nominale è seguita da una forma verbale
costruita col gerundio
Nominal → Nominal GerundVP
GerundVP → GerundV NP | GerundV PP
| GerundV | GerundV NP PP
flights arriving from NYC
9
Marco Maggini
NP: Noun Phrase -
Tecnologie per l'elaborazione del
linguaggio
3
▫  Forme verbali non finite – la parte nominale è seguita da una forma
verbale costruita con infinito o participio passato
  es. the flights arrived last night, the aircraft used by this flight
▫  Proposizioni relative – spesso iniziano con un pronome relativo (that,
who,..) che funge da soggetto della frase relativa
Nominal → Nominal RelClause
flights that arrive at night
RelClause → (who|that) VP
  Un caso un po’ più complesso sono le relative in cui il pronome relativo ha la
funzione di oggetto o complemento (es. the steward, whom I asked the question
to, the flight that I got on)
▫  I modificatori postnominali possono poi essere combinati
  Is there a flight to NYC departing from Washington at night?
10
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Frasi coordinate
•  Le parti nominali e altre unità possono essere coordinate con le
congiunzioni (and, or, but,..)
▫  es.
NP → NP and NP
the pilots and the crew
•  Si possono coordinare anche parti verbali e proposizioni intere
VP → VP and VP
the flights departing from NYC and arriving in San Diego
S → S and S
I will fly to Denver and then I will drive to Aspen
11
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Accordo di genere/persona
•  E’ possibile modificare la grammatica per tener in conto delle regole
di accordo di persona/genere
▫  Un modo diretto è quello di espandere la grammatica esplicitando la
stessa regola per tutti i casi di accordo
  es. domande in Inglese non terza persona/terza persona singolare
S → 3sgAux 3sgNP VP
S → Aux NP VP
S → Non3sgAux Non3sgNP VP
3sgAux → does | has | can …
Non3sgAux → do | have | can …
▫  Di fatto si moltiplica il numero di regole per le possibili forme che
richiedono accordo
  Il problema può essere affrontato in altro modo, ad esempio aggiungendo delle
feature ai simboli terminali
12
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Verb Phrase & Sottocategorie -
1
•  Non tutti i verbi sono compatibili con tutte le strutture/complementi
possibili
•  Una distinzione classica è fra verbi transitivi e intransitivi, ma nei modelli di
grammatica più recenti si arriva fino a circa 100 sottocategorie
  La distinzione è basata sui complementi che possono essere retti dal verbo
(subcategorization frame). Un verbo può anche essere usato con costruzioni
corrispondenti a frame diversi
Frame
Verb

sleep, walk
NP
find, take
NP NP
PPfrom PPto
show, give
fly, go
Example
I walk
I take a taxi
I showed him my documents
I went from NYC to Boston
NP PPwith
help, load
He helped me with my baggage
VPto
want, need
I need to leave
VPstem
can, would
I can wait
S
mean, say
I say I will not go home
13
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Verb Phrase & Sottocategorie -
2
•  Le costruzioni specifiche di ogni sottocategoria possono essere espresse
tramite regole grammaticali ad hoc
Verb-with-no-complement → walk | sleep |…
VP → Verb-with-no-complement
Verb-with-NP-complement → find | leave | ..
VP → Verb-with-NP-complement NP
Verb-with-S-Complement → think | say | …
VP → Verb-with-S-complement S
….
…..
•  Questo approccio ha lo svantaggio di richiedere la scrittura ad hoc per ogni
costruzione possibile aumentando di molto il numero di regole
•  Una soluzione più efficiente prevede l’uso di feature per i simboli terminali
•  La necessità di suddividere le parole in sottocagorie basate sulle possibili
costruzioni si può applicare anche a sostantivi, aggettivi e preposizioni
14
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
CF parsing per NLP
•  Le grammatiche necessarie per modellare la costruzione di frasi in
NLP possono avere caratteristiche che rendono difficile l’analisi
▫  Ricorsione a sinistra
  E’ un problema se si utilizza un analizzatore ricorsivo discendente
  Si può eliminare ma la grammatica equivalente risultante può modellare la
struttura sintattica in modo non naturale
▫  Ambiguità
  L’ambiguità strutturale si ha quando esiste più di un albero di analisi per la
stessa frase
  L’ambiguità di collegamento (attachment ambiguity) si ha quando una parte
può essere inserito nell’albero di analisi in più punti
  L’ambiguità di coordinamento (coordination ambiguity) si ha quando ci sono
più elementi uniti con congiunzioni coordinate (and)
15
Marco Maggini
Ambiguità in NLP -
Tecnologie per l'elaborazione del
linguaggio
collegamento
S
VP
NP
PP
PP
NP
Nominal
NP
Nominal
Det Noun
il poliziotto
Nominal
Verb Prep Det
sparò
a
il
Noun
ladro
Prep Det
con
la
Noun
pistola
S
L’ambiguità di collegamento
non può essere risolta a
livello sintattico ma solo a
livello semantico/pragmatico
VP
PP
NP
Nominal
Det Noun
il poliziotto
NP
PP
NP
Nominal
Nominal
Verb Prep Det
sparò
a
il
Noun
ladro
Prep Det
con
la
Noun
pistola
16
Marco Maggini
Ambiguità in NLP -
Tecnologie per l'elaborazione del
linguaggio
esempi
Ambiguità di collegamento
I saw the Grand Canyon flying to New York
Si può risolvere a livello semantico…
.. il Grand Canyon non vola!!
Ambiguità di coordinamento
the bad boys and girls
sono possibili due ragguppamenti
[the [bad boys] and [girls]]
[the [bad [boys and girls]]]
•  Spesso la disambiguazione per scegliere uno solo fra i diversi alberi di
analisi può essere effettuata solo con conoscenza statistica/semantica
▫  I parser che non utilizzano un disambiguatore devono produrre tutti i possibili
alberi di analisi
▫  Produrre tutti gli alberi di analisi può essere costoso
17
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
L’algoritmo di Earley (1970)
•  Le grammatiche CF usate in NLP in genere non appartengono a
sottocategorie per cui è possibile costruire parser efficienti (es. LL(k)
o LR(k))
▫  Le grammatiche per NLP sono in genere ambigue e richiedono la
costruzione di tutti i possibili alberi di analisi per una frase
▫  L’ algoritmo di Earley utilizza la programmazione dinamica per rendere
efficiente la fase di analisi mantenendo in memoria i sottoalberi parziali
relativi ai componenti della frase
  E’ un parser parallelo di tipo top-down che elimina la soluzione ripetitiva dei
sottoproblemi generati durante la ricerca con backtracking in modo da ridurre
la complessità
  Nel caso peggiore l’algoritmo ha una complessità O(N3) dove N è il numero di
parole della frase
  L’algoritmo esegue una singola scansione da sinistra a destra (left-to-right) e
riempie un array (chart) di N+1 elementi
18
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Il chart
•  Il chart memorizza gli stati visitati nell’analisi in modo efficiente
▫  Per ogni parola della frase il chart contiene la lista di tutti gli alberi di
analisi parziali che sono stati generati fino a quel punto
▫  Nella posizione corrispondente alla fine della frase il chart contiene una
codifica compatta di tutti gli alberi di analisi possibili
▫  I sottoalberi di analisi sono rappresentati solo una volta nel chart (la
prima volta che sono generati) e negli alberi che li contengono sono
riferiti con puntatori
▫  Ogni stato contiene tre elementi
  un sottoalbero corrispondente ad una regola grammaticale
  il grado di completamento del sottoalbero (si usa una regola puntata –
elemento LR(0))
  La posizione del sottoalbero rispetto all’ingresso codificata con una coppia di
indici corrispondenti all’inizio del sottoalbero e alla posizione del punto
19
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Stati nel Chart
book the room
0
1
2
3
S → VP , [0,0]
NP → Det Nominal , [1,2]
VP → Verb NP , [0,3]
•  L’analisi avviene elaborando gli insiemi di stati nel chart da sinistra
a destra
▫  Ad ogni passo si prende in considerazione uno stato e si applica una fra
tre possibili operazioni che può generare un nuovo stato nella posizione
corrente del chart o in quella successiva
▫  L’algoritmo procede sempre in avanti non rimuovendo stati già generati
ma aggiungendo nuovi stati
▫  La presenza dello stato S
α , [0,N] nell’ultima posizione del chart
indica un’analisi terminata con successo
20
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Operatori del parser - predictor
•  Predictor
▫  Crea nuovi stati sulla base del meccanismo di analisi top-down
▫  E’ applicato ad ogni stato che ha un non terminale alla destra del punto
▫  Si genera uno stato per ogni possibile espansione del non-terminale e lo
si inserisce nello stesso insieme del chart
▫  Il punto di inizio e fine degli stati inseriti sono gli stessi dello stato che li
ha generati
S → VP , [0,0]
S → VP , [0,0]
VP →  Verb , [0,0]
Predictor
chart[0]
VP → Verb NP, [0,0]
chart[0]
21
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Operatori del parser - scanner
•  Scanner
▫  Quando uno stato ha un elemento PoS alla destra del punto lo scanner
esamina l’input
▫  Viene creato un nuovo stato con il punto spostato alla destra della
categoria PoS predetta (la regola applicata permette di disambiguare la
PoS della parola se non è unica)
▫  Il nuovo stato è inserito nella posizione successiva del chart e la posizione
del punto è incrementata
S → VP , [0,0]
VP → Verb  NP, [0,1]
VP →  Verb , [0,0]
VP → Verb NP, [0,0]
chart[0]
Scanner
book +Noun
book +Verb
chart[1]
22
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Operatori del parser - completer
•  Completer
▫  Si applica a uno stato quando il punto ha raggiunto l’estremità destra
della produzione
▫  Corrisponde all’aver individuato una possibile applicazione della
produzione e quindi una categoria sintattica su una parte dell’input
▫  Il completer cerca tutti gli stati creati in precedenza che attendevano
questa categoria in questa posizione di ingresso
▫  Aggiunge alla posizione corrente tutti gli stati trovati con il punto
spostato avanti di una posizione
NP → Det Nominal, [1,3]
NP → Det Nominal, [1,3]
Completer
chart[3]
VP → Verb NP, [0,1]
in chart[1]
VP → Verb NP, [0,3]
chart[3]
23
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Costruzione dell’albero
•  Gli alberi di analisi validi corrispondono agli stati S
nell’ultima posizione del chart
α , [0,N]
▫  Per ricostruire l’albero occorre mantenere traccia di quali completamenti
sono stati fatti dal Completer
▫  Per ogni stato si deve tener traccia di quali stati completati hanno
generato le sue componenti
▫  Questa informazione può essere aggiunta dal completer una volta
assegnato un identificatore ad ogni stato (es. un numero progressivo)
▫  Per ricostruire un albero di analisi è sufficiente partire dalla regola
completa nella posizione N del chart e ripercorrere ricorsivamente
all’indietro le sostituzioni che sono state memorizzate
24
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Features
•  Ad ogni elemento della grammatica (terminale/non terminale) è
possibile associare un insieme di proprietà
▫  Possono essere usate per definire una rappresentazione più compatta di
certe tipologie di vincoli (accordo di numero/genere, sottocategorie di
verbi e relativi frame)
▫  Sono insiemi di coppie proprietà-valore dove il valore può essere a sua
volta un’entità strutturata
feature per una 3sgNP
rappresentazione flat
feature per una 3sgNP
rappresentazione strutturata
25
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Unificazione di feature
•  L’unificazione permette di fondere due strutture di proprietà solo
nel caso in cui esse sono compatibili
▫  E’ un operatore binario
▫  Il caso più semplice è il seguente in cui si fa una verifica di uguaglianza di
numero
  se in uno degli operandi la feature non ha un valore assegnato, la si unifica al
valore dell’altra e la fusione avviene con successo
26
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Sussunzione
•  L’unificazione di due strutture produce una struttura di feature che
è più specifica (o è uguale) rispetto agli operandi
▫  E’ più specifica nel senso che contiene più feature specificate
▫  Una struttura meno specifica (più astratta) si dice che sussume una
struttura ugualmente o più specifica
▫  La sussunzione definisce un ordinamento parziale (ci sono strutture che
non sono sussunte le une rispetto alle altre)
27
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Feature & grammatica
•  Le regole della grammatica possono essere arricchite
▫  Si associano strutture di feature sia a elementi lessicali (simboli
terminali) che a elementi sintattici (simboli non terminali)
▫  Si definisce la composizione delle strutture di feature associate agli
elementi di una produzione per ottenere la struttura associata al simbolo
a cui si riduce
▫  Si aggiungono vincoli di compatibilità
Regole “arricchite”
tipi di vincoli
  Ad esempio l’accordo di numero può esprimere come
28
Marco Maggini
Feature & rules – esempio 1
•  Accordo in una parte nominale
unifica il valore
head features
Lexicon
Tecnologie per l'elaborazione del
linguaggio
29
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Feature & rules – esempio 2
•  Sottocategorizzazione (versione semplificata)
▫  Occorre definire una categoria per ogni possibile configurazione (frame)
head features
Lexicon
30
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Parsing & constraints
•  Si possono integrare i vincoli di unificazione sulle feature associati alle
regole direttamente all’interno dell’algoritmo di parsing
▫  Si eliminano direttamente gli stati incompatibili con i vincoli
▫  Si può modificare l’algoritmo di Early per gestire sia le strutture di
feature che i vincoli associati alle produzioni della grammatica
  Si può aggiungere ad ogni stato la rappresentazione della strutturadi feature ad
esso associata
  Il modulo Predictor inserisce uno stato che rappresenta i vincoli associati alla
produzione
  Il modulo Completer combina due stati (il completamento di una produzione
con l’avanzamento di un’altra) e quindi deve gestire l’unificazione delle due
strutture associate agli stati considerati nella creazione del nuovo stato; se le
due strutture non si unificano il Completer non crea il nuovo stato
  Un nuovo stato non è aggiuntio se è sussunto da uno stato già presente (ovvero
esiste uno stato più generale)
31
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Probabilistic CF grammars
•  Il parsing probabilistico fornisce un contributo alla disambiguazione
▫  Fra gli alberi di parsing compatibili con una frase si sceglie quello a
massima probabilità
▫  Una grammatica CF stocastica (PCFG) prevede di aggiungere una
probabilità condizionata ad ogni regola
  Se si considerano tutte le possibili espansioni del non terminale A, la somma
delle probabilità associate deve essere 1
▫  Una PCFG assegna una probabilità ad ogni albero di analisi T
  Assumendo l’indipendenza nella scelta delle regole la probabilità di un albero è
32
Marco Maggini
Tecnologie per l'elaborazione del
linguaggio
Probabilistic parsing
•  Il problema dell’analisi per una grammatica PCFG è quello di produrre
l’albero di analisi più probabile per una data frase
▫  Gli algoritmi per il calcolo dell’albero di analisi più probabili sono
estensioni degli algoritmi standard (es. l’algoritmo di Earley)
•  Le probabilità possono essere stimate da un corpus che contiene frasi già
analizzate (treebank)
•  Le PCFG nella forma base hanno comunque dei limiti che derivano
dall’assunzione di indipendenza dell’espansione di un simbolo non
terminale rispetto agli altri
▫  In realtà esistono dipendenze strutturali e lessicali
  es. il modo di espandere un nodo può dipendere dalla posizione in cui si trova
nell’albero (il soggetto di una frase tende di più ad essere un pronome)
33
Marco Maggini
PCFG -
Tecnologie per l'elaborazione del
linguaggio
limiti
•  Un altro limite delle PCFG è la non dipendenza dalle parole
▫  le parole hanno un ruolo fondamentale nella selezione del parsing
corretto in caso di ambiguità
▫  Le ambiguità nelle parti coordinate sono un altro esempio in cui le
dipendenze lessicali sono importanti per la disambiguazione
  es. dogs in houses and cats -> [dog in houses] and [cats]
•  Una soluzione è associare ad ogni non terminale la parola principale (head)
della parte funzionale che rappresenta
▫  Si individua nella parte destra della produzione il termine che fornisce la
parola principale (in generale non è sempre chiaro quale prendere)
▫  Si ottiene una grammatica con attributi (le produzioni sono dipendenti
dal valore dell’attributo)
▫  I parser basati su lexicalized PCFG adattano assunzioni di indipendenza
per evitare di stimare una probabilità per ogni head/regola