Inkrementelle SyntaxSynchroneous Tree UniVcation Grammar

Timm Lichte

HHU Düsseldorf, Germany

29.01.2014

SFB 991

1 / 17

Das ideale Grammatikmodell

linguistisch adäquat:Phänomene:Linearisierung, Kongruenz, Diskontinuität, Ellipse, Koordination(RNR), . . .Generalisierungen/Zusammenhänge:Valenzrahmen, Aktiv/Passiv-Diathese, Satztypen, Stellungsalter-nation, Syntax-Semantik-Schnittstelle, Kontext-/Diskursabhängigkeitintuitive Implementierung

computerlinguistisch adäquat:explizit/formalisiertentscheidbar, vielleicht sogar mit vertretbarem Aufwandbidirektional

psychlinguistisch adäquatstrikt inkrementelle Derivationenrichtige Vorhersagen bzgl. VerarbeitungskomplexitätVorhersage & VeriVkation (prediction & veriVcation)PiG

2 / 17

(strenge) Evaluation

ATN: zu prozedural, zu mächtig (Jumps + nichtmonotone Regi-steroperationen)

LAG: zu intransparent? zwingend linksassoziiert, keine Konsti-tuentenstruktur

Dynamic Syntax: formalisiert? zu intransparent/ zu wenigmodularisiert?

IM: nicht formalisiert; zwingend rechtsassoziiert

PLTAG: zu modularisiert (LTAG + inkrementelle Erweiterung)

3 / 17

Heute

STUG (Lichte, 2012):Motivation: Verhältnis von Syntax und Valenz,

Diskontinuität, Ellipse, GrammatikfaktorisierungModelltyp: automatengestützte BaumuniVkation

Ablauf:

einführendes BeispielMotivation:

EllipsenGrammatikfaktorisierungInkrementalitätKohärenz

Ausdrucksstärke

Einordnung

4 / 17

Einführendes Beispiel

Synchrone BaumuniVkationsgrammatik (STUG)

Eine STUG besteht aus Syntax-Valenz-Paaren:

⟨ VP 1©

V

isst

,

[lem essenmode ind

]1©

[case acc]lem !case nomagr 3rdsing

agent

patient

⟩

Syntaxbaum und Valenzstruktur sind getrennt, aber verlinkt!

Symmetrische Kombinationsoperation: BaumuniVkation

Linearisierungsbeschränkungen durch endlichen Automatenüber syntaktischen Kategorien

5 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

NP 3©

N

Peter

lem Petercase acc|nomagr 3rdsing

3©

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

V

isst

NP 3©

N

Peterlem Petercase acc|nomagr 3rdsing

3©[lem essenmode ind

]1©

[case acc]lem !case nomagr 3rdsing

agent

patient

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

V

isst

VP 2©

NP 3©

N

Peter[ ] 2©lem Peter

case acc|nomagr 3rdsing

3©

[lem essenmode ind

]1©

[case acc]lem !case nomagr 3rdsing

agent

patient

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

V

isst

NP 3©

N

Peter[ ] 1©lem Peter

case acc|nomagr 3rdsing

3©

[lem essenmode ind

]1©

[case acc]lem !case nomagr 3rdsing

agent

patient

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

[case acc]lem Petercase nomagr 3rdsing

3©agent

patient

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

NP 4©

Det

einen

VP 1©

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

[case acc]lem Petercase nomagr 3rdsing

3©agent

patientlemcase accagr 3rdsingdet +

4©

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

NP 4©

Det

einen

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

[case acc]lem Petercase nomagr 3rdsing

3©agent

patient

[ ] 1©

lemcase accagr 3rdsingdet +

4©

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

NP 5©

N

Apfel

VP 1©

NP 4©

Det

einen

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

case accagr 3rdsingdet +

4©lem Petercase nomagr 3rdsing

3©agent

patient

lem Apfelcase acc|nomagr 3rdsing

5©

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

NP 4©

N

Apfel

Det

einen

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

case accagr 3rdsingdet +

4©lem Petercase nomagr 3rdsing

3©agent

patient

lem Apfelcase acc|nomagr 3rdsing

4©

6 / 17

Einführendes Beispiel

(1) Peter isst einen Apfel.

VP 1©

NP 4©

N

Apfel

Det

einen

V

isst

NP 3©

N

Peter

[lem essenmode ind

]1©

lem Apfelcase accagr 3rdsingdet +

4©lem Petercase nomagr 3rdsing

3©agent

patient

6 / 17

Motivation

Warum noch ein weiterer Grammatikformalismus?

⇒ Er ist anders (vgl. LTAG):

Trennung von Syntax und Valenz (ATN?)Wache syntaktische StrukturenAbleitungsbäume uninteressant

⇒ attraktive Eigenschaften:

Ellipse ohne zusätzliche Regelnsubstantielle Verringerung der Grammatikgröße (vgl. LTAG)inkrementelles Parsen ohne Hilfsstrukturen (vgl. PLTAG)

7 / 17

Motivation: Ellipse

(2) a. Mary always laughs, and John sometimes.b. Q: Who doesn’t laugh? A: John sometimes.c. [Sue is pointing to knitting things.] Mary: John sometimes.

übliche Strategien:

Verschmelzung (vollständig, aber Überschneidung)

Tilgung (vollständig, aber phonetisch reduziert)

Füllung (vollständig, aber mit leeren Worten)

spezielle Phrase/Lexikoneinträge (unvollständig, weil defekt)

STUG-Strategie: keine speziellen Regeln, direkteModellierung

8 / 17

Motivation: Ellipse

(3) [Sue is pointing to knitting things.] Mary: John sometimes.

VP 1©

NP

N

John

VP 2©

AP

A

sometimes

[ ] 1©

lem Johncase accagr 3rdsing

3©[ ] 2©[

lem sometimescase null

]4©

9 / 17

Motivation: Ellipse

(3) [Sue is pointing to knitting things.] Mary: John sometimes.

VP 1©

AP

A

sometimes

NP

N

John

[ ] 1©[

lem sometimescase null

]4©

lem Johncase accagr 3rdsing

3©

9 / 17

Motivation: Grammatikfaktorisierung

LTAG-Motto

“complicate locally, simplify globally” (Joshi, 2004)

eine Baumschablone pro Konstruktion(= Valenzrahmen × Linearisierung × Aktiv/Passiv-Diathese)

Peter aß den Apfel.Den Apfel aß Peter. dass Peter den Apfel aßGestern aß Peter den Apfel. dass den Apfel Peter aßGestern aß den Apfel Peter.Peter aß. Der Apfel wurde gegessen.Gestern aß Peter. Der Apfel wurde von Peter gegessendass Peter aß . . .

optionale ArgumenteLinearisierungsalternativen

} viele Baumschablonen

10 / 17

Motivation: Grammatikfaktorisierung

LTAG:

XTAG enthält 1008 verbale Baumschablonen (Prolo, 2002).XTAG benutzt 50 syntaktische Merkmale, um Linearisierung,Kongruenz und Valenz zu beschränken.→ ausgetüftelte Metagrammatik-Systeme (metarules, XMG)→ bestimmte Generalisierungen in LTAG nicht ausdrückbar

lexikalische Ambiguität: laughs mit optionalem PP-Argumentkann wenigstens 10 Baumschablonen lexikalisieren.→ ausgeklügelte Disambiguierungsmethoden zur Beschleuningung

des Parsers (Gardent et al., 2011)

11 / 17

Motivation: Grammatikfaktorisierung

STUG:

⟨ VP 1©

V

isst

,

[lem essenmode ind

]1©

[case acc]lem !case nomagr 3rdsing

agent

patient

⟩

VP: qastart qb qc qd qeNP/AP/. . .

NP/AP/. . .

VVn

NP/AP/. . .

V

V

S

NP: qastart qb qc qdDet

N

Adj

Adj

N

NP

12 / 17

Motivation: Direkte Inkrementalität

PLTAG = LTAG +

prediction trees

UniVkation/VeriVkation

STUG:

unlexikalisierte Verbindungsbäume (~ prediction trees)

Vorhersage durch Verbindungsbäume und Valenzbaum

nur UniVkation

⇒ keine speziellen Komponenten für Inkrementalität

13 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

NP 3©

N

ihnlem ercase accagr 3rdsing

3©

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

NP 4©

N

Peter

NP 3©

N

ihnlem ercase accagr 3rdsing

3© lem petercase nom|acc|datagr 3rdsing

4©

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 2©

NP 4©

N

Peter

VP 1©

NP 3©

N

ihn[ ] 1©lem er

case accagr 3rdsing

3©[ ] 2©lem peter

case nom|acc|datagr 3rdsing

4©

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 0©

NP 4©

N

Peter

NP 3©

N

ihn[ ] 0©lem er

case accagr 3rdsing

3©[ ] 0©lem peter

case nom|acc|datagr 3rdsing

4©

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 5©

V

zu reparieren

VP 0©

NP 4©

N

Peter

NP 3©

N

ihn[ ] 0©lem er

case accagr 3rdsing

3©[ ] 0©lem peter

case nom|acc|datagr 3rdsing

4©[lem reparierenstat 2

]5©

[case acc]

P

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 0©

V

zu reparieren

NP 4©

N

Peter

NP 3©

N

ihn

[ ] 0©lem petercase nom|acc|datagr 3rdsing

3©

[lem reparierenstat 2

]0©

lem ercase accagr 3rdsing

P

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 6©

V

versucht

VP 0©

V

zu reparieren

NP 4©

N

Peter

NP 3©

N

ihn

[ ] 0©lem petercase nom|acc|datagr 3rdsing

3©

[lem reparierenstat 2

]0©

lem ercase accagr 3rdsing

P

[lem versuchenmode ind

]6©

[lem !stat 2

]6©

lem !case nomagr 3rdsing

A T

14 / 17

Weiteres Beispiel: Kohärente Konstruktionen

(4) (dass) ihn Peter zu reparieren versuchte

VP 0©

V

versucht

V

zu reparieren

NP 4©

N

Peter

NP 3©

N

ihn

[lem versuchenmode ind

]0©

[lem reparierenstat 2

]0©

lem ercase accagr 3rdsing

4©P

lem petercase nomagr 3rdsing

3©A T

14 / 17

Ausdrucksstärke

mit STUG generierbar:

nicht-wohleingebettete Abhängigkeiten

Abzählsprache anbn mit eingebetteten Abhängigkeiten

MIX-Sprache

Abzählsprachen an1 . . . ank

mit STUG nicht generierbar (Vermutung):

Abzählsprache anbn mit kreuzenden Abhängigkeiten (bzw. Kopier-sprache)

exponentielle Abzählsprache a2n

SCRind = {σ(NP1, . . . ,NPm)Vm . . .V1|m ≥ 1 and σ is a permutation }

⇒ STUG scheint mehr und gleichtzeitig weniger Ausdrucksstärke alsLTAG zu besitzen! (vgl. LAG)

15 / 17

Einordnung

STUG ≈ ATN mit Bäumen und (monotoner) UniVkation . . .

linguistisch adäquat?⇒ Linearisierung, Kongruenz, Ellipse, Koordination?, MWE?, weite

Abhängigkeiten?⇒ Linearisierungsalternation, Valenzrahmen, Aktiv/Passiv, Dis-

kursabhängigkeit?⇒ intuitiv?

computerlinguistisch adäquat⇒ formalisiert, aber Mächtigkeit unbekannt⇒ möglicherweise bidirektional

psycholinguistisch adäquat⇒ strikt inkrementell, Vorhersagen & VeriVkation⇒ richtige Vorhersagen?

Es sind noch viele Fragen oUen!

16 / 17

Gardent, Claire, Yannick Parmentier, Guy Perrier & Sylvain Schmitz. 2011. Lexical Disambiguation in LTAG using LeftContext. In 5th language and technology conference - ltc’11, 395–399. Poznan, Poland.http://hal.archives-ouvertes.fr/hal-00629902/en/.

Joshi, Aravind K. 2004. Starting with complex primitives pays oU: complicate locally, simplify globally. Cognitive Science 28(5).637–668.

Lichte, Timm. 2012. Synchronous tree uniVcation grammar. In Proceedings of the 11th international workshop on tree adjoininggrammars and related formalisms (tag+11), 46–54. Paris, France.http://www.aclweb.org/anthology-new/W/W12/W12-4606.

Prolo, Carlos A. 2002. Generating the XTAG English grammar using metarules. In Proceedings of the 19th internationalconference on computational linguistics (coling 2002), 814–820. Taipei. Taiwan.