Elaborazione del linguaggio
naturale
Fabio Massimo Zanzotto
FMZ
Part seven
Modular and Robust parsing
FMZ
Our Aim
Lines of development
Grammatical Representation Power:
• CFG (context free grammars)  DCG
• Feature Structures
• Tree Adjoining Grammars (TAG)
Grammar Use:
• CYK
• Chart and Early Algorithm
FMZ
Lesson learnt
• Lexicon (i.e. words) is a very important
piece of the Language and of the language
model
• Words carry meaning and govern the
syntactic structure of sentences
FMZ
Limits of the previous
approaches
• When parsing or:
– one interpretation is active at each processing
step (for example, DCG in Prolog)
– all interpretations are active (for example, CYK
or Chart Parsing)
• Processing complexity depends on the
number of active interpretation
FMZ
Observation
Question:
is it possible to fix some ambiguity in early step
of the analysis?
Art
...
Prn
mangia la
...
FMZ
Decomposizione del processo
• Processori Pi che si occupano di specifici
fenomeni accoppiati con una possibile funzione di
disambiguazione basata su informazioni locali
P1
…
FMZ
Pn
Decomposizione del processo
• Ricerca di obbiettivi (o rappresentazioni)
intermedi raggiungibili (e utili)
– Criteri psicolinguistici
– Requisiti computazionali
– Esigenze applicative
• È possibile trovare soluzioni approssimate
per problemi più semplici?
FMZ
Decomposizione del processo
L'industria giapponese dei robot, una delle poche
a non risentire della grave crisi economica, ha
sfornato una versione perfezionata del robot
umanoide "Db", fatto nascere due anni fa in un
laboratorio vicino a Kyoto.
FMZ
Decomposizione del processo
• Esiste un livello di aggregazione nel testo
che si pone tra parole e frasi.
• Gli aggregati non si sovrappongono (i.e.
non sono “ricorsivi”)
FMZ
Chunking: esempio di
stratificazione di un albero
S
VP
NP
NP
NP
A
VP
NP
AdjP
N
Adj
NP
V
V
A
PP
AdjP
N
Adj
NP
PA
N
Adj
N
L’ industria giapponese ha sfornato una versione perfezionata del robot umanoide "Db”.
FMZ
Chunking: esempio di
stratificazione di un albero
S
VP
NP
AdjP
NP
VP
PP
NP
A
AdjP
N
Adj
NP
V
V
A
NP
N
Adj
PA
N
Adj
N
L’ industria giapponese ha sfornato una versione perfezionata del robot umanoide "Db”.
FMZ
Chunking: esempio di
stratificazione di un albero
S
VP
NP
NP
A
VP
NP
AdjP
N
Adj
NP
V
V
A
PP
AdjP
N
Adj
NP
PA
N
Adj
N
L’ industria giapponese ha sfornato una versione perfezionata del robot umanoide "Db”.
FMZ
Chunking: esempio di
stratificazione di un albero
NP
NP
A
VP
PP
AdjP
N
Adj
NP
V
V
A
NP
N
Adj
PA
N
Adj
N
L’ industria giapponese ha sfornato una versione perfezionata del robot umanoide "Db”.
FMZ
Decomposizione del processo
• Chunk:
– livello intermedio di rappresentazione
– giustificato psico-linguisticamente (Abney,
1991)
• Definizione (intuitiva) di chunk:
Sequenza di parole
• fortemente connessa
• con un unico portatore di significato
• costante alle differenti interpretazioni
FMZ
Decomposizione del processo
• LESSICALIZZAZIONE: Controllo
dell’ambiguità
– verbi controllano semantica delle proposizioni
– quindi controllano le relazioni sintattiche
I medici operano un paziente al femore : aveva 105 anni.
FMZ
Decomposizione del processo
• Controllo dell’ambiguità
– verbi controllano semantica delle proposizioni
– quindi controllano le relazioni sintattiche
SUBJ operare OBJ PP(a)
I medici operano un paziente al femore : aveva 105 anni.
FMZ
Definizione di chunk
• Bottom-up:
Una sequenza di parole che rappresenta il
nucleo non ricorsivo di sintagmi nominali,
preposizionali, verbali ed aggettivali
• Top-down:
Una sequenza di parole le cui relazioni non
sono influenzate dal comportamento dei verbi
FMZ
Chunk: osservazioni
Chunk
nuclei “non ricorsivi”* di sintagmi particolari
Chunk
sono riconoscibili con automi a stati finiti
* “non ricorsivi” = ricorsivi destri che
non rimandano a sintagmi superiori
FMZ
Chunking: prototipi
Prototipo:
• regola per catturare chunk
• esprimibile utilizzando informazione di
POS tags tramite
– espressioni regolari/trasduttori (Fastus,
Alembic, Chanod&Ait)
– marker iniziale e finale (ACL, 2001)
FMZ
Chunking: prototipi
Esempi di espressioni regolari:
NPK:
Art N | Art A N
VPK:
V|VV
PPK:
P Art N | P Art A N
FMZ
Chunking: prototipi
Esempi di marker iniziale e finale:
NPK:
MI: Art
MF: N
VPK:
MI: V
MF: V
PPK:
MI: P
MF: N
FMZ
Chunking: considerazioni
• Identificazione e classificazione:
– possibile nel livello sintattico
– risolvibile con macchinari semplici (i.e. FSA)
• La grammatica (ovvero i prototipi)
– indipendente dal dominio di applicazione
• Domanda: Qualora fosse la sola informazione
estratta, sarebbe utile per una qualche
applicazione?
FMZ
Prerequisiti
• Chunking
– Part-of-speech tagging
• Riconoscimento dei legami verbali:
– Individuazione dei limiti delle proposizioni
(clause boundary recognition)
FMZ
Part-of-speech tagging
• Definizione del problema
w1…wn t1…tn
NNS TO VB IN
NNS
PRP MD
VB
Strategies to use with questions you cannot answer
FMZ
Part-of-speech tagging
• Origini (1989)
sotto la spinta dell’Information Extraction
alla Message Understanding Conference
• Approcci
– approcci simbolici (regole trasformazionali,
Brill 94)
– approcci statistici (a seguire)
FMZ
POS Tagging basato sulle
trasformazioni (Brill, 94)
Dato un primo tagging (dizionario con tag
più frequenti),
applicare regole di trasformazione fino a
che l’errore non diminuisca sotto una soglia
FMZ
Trasformazioni
• Regole di riscrittura
t1  t2 se <condizione nello spazio circostante
(triggering environment)>
• Esempio
NN  VB se il tag precedente è TO
TO NN
NNS TO VB
NN IN
NNS
PRP MD
VB
FMZ
Strategies to use with questions
you cannot answer
Trasformazioni: Schemi dei
triggering environments
ti-3
ti-2 ti-1
ti
*
*
*
*
*
*
*
*
*
FMZ
ti+1
ti+2
ti+3
Trasformazioni: algoritmo di
apprendimento
• Quali trasformazioni?
• Quale ordine di applicazione?
FMZ
Trasformazioni: algoritmo di
apprendimento
C0:= Corpus con tag più frequenti
for k:=0 step 1 do
v:= trasformazione n che minimizza E(n(Ck))
if (E(Ck) - E(n(Ck))) < e then break
Ck+1 :=v(Ck)
tk+1:= v
end
OUTPUT: sequenza t1, …, tk
FMZ
POS Tagging basato sulle
trasformazioni
• Tagging delle parole sconosciute basato
sulla morfologia
– Tutte le parole sconosciute vengono taggate con
NN
– Il tag viene cambiato seguendo alcune regole
trasformazionali morfologiche
Es: NN NNS la parola termina con -s
FMZ
POS Tagging basato sulle
trasformazioni
Qualità dell’attività di POS Tagging dipende:
• dall’insieme dei tag obbiettivo
• dalla possibilità di recuperare informazione
disambiguante nei contesti di attivazione
Es.: che in italiano (pronome/congiuzione)
• dal materiale di apprendimento
FMZ
Clause boundary recognition
• Definizione del problema
( L'industria giapponese dei robot, una delle poche
( a non risentire della grave crisi economica), ha
sfornato una versione perfezionata del robot
umanoide "Db", (fatto nascere due anni fa in un
laboratorio vicino a Kyoto ). )
FMZ
Clause boundary recognition
• Proposizioni sono utili per:
– Conversione Text-to-speech
– Allineamento di testi
– Traduzione automatica
• Particolarità
– Ricorsività non presente nei chunks
FMZ
Clause boundary recognition
contribute-NP-PP(to)
value-NP-PP(at)
Inf(S1)
Inf(S2)
[ Mr. Gaubert ] [contributed] [real estate] [valued] [ at $ 25 million] [to the assets] [of Independent American]
FMZ
Clause boundary recognition
contribute-NP-PP(to)
value-NP-PP(at)
Inf(S1)
Inf(S2)
[ Mr. Gaubert ] [contributed] [real estate] [valued] [ at $ 25 million] [to the assets] [of Independent American]
FMZ
Clause boundary recognition
contribute-NP-PP(to)
value-NP-PP(at)
Inf(S1)
Inf(S2)
[ Mr. Gaubert ] [contributed] [real estate] [valued] [ at $ 25 million] [to the assets] [of Independent American]
FMZ
Clause boundary recognition
• Algoritmo:
– Ipotesi iniziale di
• minima estensione delle proposizioni
• gerarchia derivata
– Finché ci sono verbi da analizzare (da destra
verso sinistra):
• Riconoscere il legami verbali
• Espandere l’estensione minima della proposizione
FMZ
Controllo del processo
• Passi analisi:
–
–
–
–
POS Tagging
Chunking
Clause Boundary Recognition
Verb Argument Detection
FMZ
Controllo del processo
• Situazione problematica:
necessità di definire i tipi di dati trattati
P1
…
FMZ
Pn
Controllo del processo
• Situazione problematica:
necessità di definire i tipi di dati trattati
P1
…
Giudice
Pn
FMZ
Formalismo di rappresentazione
Requisiti:
• Rappresentazione di analisi parziali
• Rappresentazione di legami distanti
• Information hiding
– rendere disponibile la sola informazione
necessaria …
– ma capace di esprimere tutti i vincoli correnti
FMZ
Formalismo di rappresentazione
• Rappresentazione a costituenti
– Context-free Grammar (Tree)
– Well Formed Substring Table (WFST): chart
– Tree-Adjoint Grammar (TAG)
• Rappresentazione a dipendenze
– Link Grammar
• Rappresentazione miste
– Extended Dependency Graph (XDG)
FMZ
XDG: eXtended Dependency Graph
• an XDG is a graph:
XDG=(constituents,dependencies)
Nice property: allow to store persistent ambiguity
(for interpretations projected by the same nodes)
• Each constituent has:
– a potential governor
– a grammatical head
FMZ
Modular approach
• Syntactic parser
SP(S,K)=I  SP(S)=I
• Syntactic parsing module:
Pi(Si,Ki)=Si+1  Pi(Si)=Si+1
• Modular syntactic parser
SP = Pn... P2P1
FMZ
Classification of parsing modules
Pi(XDGi,Ki)=Pi(XDGi)=XDGi+1
• The classification is performed according
to:
– the type of information K used
– how they manipulate the sentence
representation
FMZ
Decomposizione del processo
Principi:
• Scegliere i fenomeni trattati in ogni livello
• Scegliere l’algoritmo migliore per ogni task
• Scegliere un opportuno formalismo di
rappresentazione
FMZ
Back to the beginning...
x Marinaio (x).( y Ragazza(y)  Ama (x, y))
 y Ragazza(y).(x Marinaio (x)  Ama (x, y))
conosenza simbolica
incerta
?
conosenza simbolica abilità
linguistica
apprendimento
“Tutti i marinai amano una ragazza”
FMZ
Interpreting Language Through
Syntax
Assunzione di Chomsky: i differenti significati
hanno differenti strutture sintattiche “profonde”
Esempio:
Luigina ha chiesto in prestito la borsetta di pelle di
nonna.
Possibili Costruzioni Sintattiche in alberi:
...(la borsetta di (pelle di nonna))
...(la (borsetta di pelle) di nonna)
FMZ
Where we worked
Lines of development
Grammatical Representation Power:
• CFG (context free grammars)  DCG
• Feature Structures
• Tree Adjoining Grammars (TAG)
Grammar Use:
• CYK
• Chart and Early Algorithm
• Modular Parsing and Cascades of Different
Theories (XDG)
FMZ
NLP Applications
•
•
•
•
Information Extraction
Q&A
Ontological Q&A
Textual Entailment
FMZ