Elaborazione del linguaggio
naturale
Fabio Massimo Zanzotto
FMZ
Part six
Tree Adjoining Grammars
FMZ
Our Aim
Lines of development
Grammatical Representation Power: Build a
formalism/model able to give the possibility
of reducing the unnecessary interpretations
Grammar Use: Build a formalism (and an
associated algorithm) able to represent
partial analysis
FMZ
Our Aim
Lines of development
Grammatical Representation Power:
• CFG (context free grammars)  DCG
• Feature Structures
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
What we observed
Toy Examples:
... La vecchia porta la sbarra ...
... Il vecchio porta la sbarra ...
... Flying planes can be dangerous ...
... Flying planes is dangerous ...
FMZ
Continuing the observation of the
languages
Some more toy examples:
... Il ragazzo mangia la mela con il coltello ...
... L’uomo guarda il monitor con gli occhi stralunati ...
... Le azioni della acme inc aumentano in tre settimane
da 2 euro a 3 euro ...
How many interpretations are possible for these
sentences?
FMZ
Subcategorisation frames
Necessary subcategorisation frames:
... Il ragazzo mangia la mela con il coltello ...
((NP) mangiare (NP) (PP(con)))
... L’uomo opera il paziente di appendicite ...
((NP) operare (NP) (PP(di)))
... Le azioni della acme inc aumentano in tre settimane
da 2 euri a 3 euro ...
((NP) aumentare (PP(da)) (PP(a)))
FMZ
Modelling Subcat Frames in
CFGs
Target Frame: ((NP) mangiare (NP) (PP(con)))
S  NP VP | NP VP(mangiare)
NP  NP SBAR
VP  VerbX NP | VerbX NP PP
VerbX  Verb | Modal Verb
VP(mangiare)  VerbX(mangiare) NP | VerbX (mangiare)
NP PP(con)
VerbX(mangiare)  Verb(mangiare) | Modal Verb(mangiare)
NP  Art Noun | Art Adj Noun | Noun | Verb Noun | NP PP
FMZ
PP  Prep NP
Observations
Il ragazzo mangia la mela a mezzogiorno con il
coltello
How do we modify those(?):
VP(mangiare)  VerbX(mangiare) NP | VerbX
(mangiare) NP PP(con)
VerbX(mangiare)  Verb(mangiare) | Modal
Verb(mangiare)
FMZ
Summing up
• We understood that subcategorisation can
indicate preferred sentence readings
• We want to build lexicalised rules, that is,
rules governed by lexical elements (words)
• We want to empower the grammar
FMZ
Idea!!!
• Lexicalised rules may be partial tree!
((NP) aumentare (PP(da)) (PP(a)))
S
NP
VP
PP
PP
V
aumentare
IN NP IN NP
da
a
FMZ
Defining better our aim
• We want a lexicalised grammar
– each rule (partial tree) has to at least a lexical item
• We want a grammar equivalent to the a given
grammar
– weak equivalence: equivalence in the language
recognised
– strong equivalence: equivalence in generated trees
with respect to input sentences... remember that the
structure define the “meaning”
FMZ
Operations in CFG
in the derivation, no terminal symbols are
substituted with rewriting rules headed by the
same symbol
may be understood as
tree substitution
no terminal symbols are substituted with trees
headed by the same symbol
is it sufficient to obtain the strong equivalence?
FMZ
Investigating strong equivalence
Given the grammar
and the sequence aaaa, one of the
interpretations is:
FMZ
Let’s build the lexicalised
grammar
Given the tree collection
the interpretation
cannot be obtained!
FMZ
Another example
Given the grammar
it can be lexicalised as follows:
strange rule!!!
FMZ
Another example
The same grammar may be lexicalised also
however, what about this
FMZ
Tree Adjoining Grammars
FMZ
What do we need?
• A new operation!!!
the Tree Adjoining operation
FMZ
Tree Adjoining Example
FMZ
Again the substitution
• The well know operation
FMZ
Substitution example
FMZ
Tree Adjoining again
Does it solve the problem of obtaining the
strong equivalence?
This is the solution to the example problem!!!
FMZ
Tree Adjoining again
successive adjoining of (b4)
FMZ
More examples
may give the interpretation:
FMZ
What is a grammar now?
It is a collection of:
• initial trees, represent the lexicon, e.g.,
• auxiliary trees, represent grammatical rules,
e.g.,
FMZ
Do you remember?
copy-language structures:
Pino, Gino e Rino sono rispettivamente fratello, zio e babbo
di Nino
may be read as:
a1a2a3b1b2b3
Exercise: Find a model in TAG for this problem
FMZ
What we have done?
• we have worked on the representation power of
the grammar
• we introduced:
– lexicalised rules
– the adjoining operation
• where do we pay?
– on the parsing algorithm?
FMZ
Question
Have we resolved the problem of selecting between
different readings (sentence interpretations)?
FMZ