View
2
Download
0
Category
Preview:
Citation preview
Komplexität und natürliche SpracheKompetenz versus Performanz
Timm Lichte & Christian Wurm
Heinrich-Heine-Universität Düsseldorf
Sommersemester 2017, 24.05.2017
SFB 991
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 1
Outline
1 Kompetenz versus Performanz
2 Äquivalenz und Normalformen
3 X-bar-Schema
4 Derivational Theory of Complexity
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 2
Outline
1 Kompetenz versus Performanz
2 Äquivalenz und Normalformen
3 X-bar-Schema
4 Derivational Theory of Complexity
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 3
Kompetenz versus Performanz
Kompetenz PerformanzWas wird charakterisiert Wie wird charakterisiertWissensinhalt WissensanwendungSprachklassen Regelmengen von Grammatiken (Kompetenz?)
Regelanwendungen für ein konkretes Wort
Sprachklassen-Komplexität
L1 ist komplexer als L2, falls L1 ⊃ L2.
Grammatik-Komplexität (Regelanzahl)
Sei L(G1) = L(G2), G1 ist komplexer als G2, falls |P1 | > |P2 |.
Grammatik-Komplexität (Ambiguität)
G1 ist komplexer als G2 bezüglich w , falls |PTR1(w)| > |PTR2(w)|.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 4
Kompetenz versus Performanz (cont.)
Grammatik/Wort-Komplexität (Ableitungslänge)
w1 ist komplexer als w2 bezüglich G, falls|S ` ... ` w1 | > |S ` ... ` w2 |
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 5
Outline
1 Kompetenz versus Performanz
2 Äquivalenz und Normalformen
3 X-bar-Schema
4 Derivational Theory of Complexity
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 6
Schwache und starke Äquivalenz von Grammatiken
Gegeben zwei kontextfreie Grammatiken G1 = 〈N1, Σ1,P1, S1〉 undG2 = 〈N2, Σ2,P2, S2〉.
Schwache Äquivalenz
G1 und G2 sind schwach äquivalent gdw. G1 und G2 erzeugendieselbe Sprache.
G1 ≡w G2 ⇔ L(G1) = L(G2)
Starke Äquivalenz
G1 und G2 sind stark äquivalent gdw. G1 und G2 erzeugen dieselbeSprache mit denselben Ableitungen.
G1 ≡s G2 ⇔ P1 = P2 ∧ S1 = S2
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 7
Schwache und starke Äquivalenz von Grammatiken (cont.)
Strukturelle Äquivalenz
G1 und G2 sind strukturell äquivalent gdw. G1 und G2 erzeugendieselbe Sprache mit den gleichen Ableitungen.
G1 ≡P G2 ⇔ Es gibt eine Bijektion f : N1 → N2, wobei f (S1) = S2,und eine Bijektion g : P1 → P2, so dass gilt: Wenn α → β1...βn ∈P1 mit α ∈ N1 und βi ∈ Σ1 ∪ N1, dann gibt es g(α → β1...βn) =f (α) → γ1...γn mit γi = βi , falls γi ∈ Σ2, oder γi = f (βi), falls γi ∈ N2.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 8
Schwache und starke Äquivalenz von Grammatikklassen
Gegeben zwei Grammatikklassen G1 und G2.
Schwache Äquivalenz
G1 und G2 sind schwach äquivalent gdw. es gibt eine Bijektionf : G1 → G2, so dass für jedes G ∈ G1 gilt:
G ≡w f (G)
Starke Äquivalenz
G1 und G2 sind stark äquivalent gdw. es gibt eine Bijektion f :G1 → G2, so dass für jedes G ∈ G1 gilt:
G ≡s f (G)
Äquivalenz von Grammatiken aus verschiedenenGrammatikformalismen?
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 9
Normalformen für kontextfreie Grammatiken
Normalform heißt: Die Regeln haben eine bestimmte Form.
Chomsky-Normalform (CNF)
A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)
Greibach-Normalform (GNF)
A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)
Lexikalisierung
A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)
Kontextfreie Grammatiken in CNF und GNF und lexikalisiertekontextfreie Grammmatiken sind schwach äquivalent zukontextfreien Grammatiken.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 10
Normalformen für kontextfreie Grammatiken
Normalform heißt: Die Regeln haben eine bestimmte Form.
Chomsky-Normalform (CNF)
A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)
Greibach-Normalform (GNF)
A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)
Lexikalisierung
A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)
Kontextfreie Grammatiken in CNF und GNF und lexikalisiertekontextfreie Grammmatiken sind schwach äquivalent zukontextfreien Grammatiken.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 10
Normalformen für kontextfreie Grammatiken
Normalform heißt: Die Regeln haben eine bestimmte Form.
Chomsky-Normalform (CNF)
A→ B C |a (mit A,B,C ∈ N , a ∈ Σ)
Greibach-Normalform (GNF)
A→ a β (mit A ∈ N , a ∈ Σ, β ∈ N∗)
Lexikalisierung
A→ α a β (mit A ∈ N , a ∈ Σ, α , β ∈ N∗)
Kontextfreie Grammatiken in CNF und GNF und lexikalisiertekontextfreie Grammmatiken sind schwach äquivalent zukontextfreien Grammatiken.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 10
Normalformen für kontextfreie Grammatiken (cont.)
Nicht schwach äquivalent zu kontextfreien Grammatiken:
lineare CFG
A→ a B |B a |a (mit A,B ∈ N , a ∈ Σ)oderA→ a B b |a (mit A,B ∈ N , a, b ∈ Σ)
Lineare CFGs können nicht die Dyck-Sprachen erzeugen.
S → ϵ |SS |(S)
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 11
Normalformen für kontextfreie Grammatiken (cont.)
Nicht schwach äquivalent zu kontextfreien Grammatiken:
lineare CFG
A→ a B |B a |a (mit A,B ∈ N , a ∈ Σ)oderA→ a B b |a (mit A,B ∈ N , a, b ∈ Σ)
Lineare CFGs können nicht die Dyck-Sprachen erzeugen.
S → ϵ |SS |(S)
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 11
Ordentliche (“proper”) CFGs[8]
Eine kontextfreie Grammatik G = 〈N , Σ,P, S〉 ist ordentlich gdw.:
keine unerreichbare Nich�erminale
∀A ∈ N : ∃α , β ∈ (Σ ∪ N)∗: S `∗G αAβ
keine unproduktive Nich�erminale
∀A ∈ N : ∃w ∈ Σ∗: A `∗G w
keine ϵ-Produktionen
�A ∈ N : A `G ϵ oder
P ⊆ N → (Σ ∪ N \ {S, ϵ})+ ∪ {S → ϵ}
keine Zyklen�A ∈ N : A `+G A
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 12
Ordentliche (“proper”) CFGs
Die Klasse der ordentlichen kontextfreien Grammatiken ist schwachäquivalent zur Klasse der kontextfreien Grammatiken.
Unerreichbare und unproduktive Nich�erminale können elim-iniert werden. [5: §7.1.1]
ϵ-Produktionen können eliminiert werden. [5: §7.1.3]
Zyklen (allgemeiner “unit pairs”) können eliminiert werden. [5:§7.1.4]
AberDurch die Eliminierung der ϵ-Produktionen und der Zyklen (bzw.“unit pairs”) kann P erheblich größer werden.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 13
Ordentliche (“proper”) CFGs
Die Klasse der ordentlichen kontextfreien Grammatiken ist schwachäquivalent zur Klasse der kontextfreien Grammatiken.
Unerreichbare und unproduktive Nich�erminale können elim-iniert werden. [5: §7.1.1]
ϵ-Produktionen können eliminiert werden. [5: §7.1.3]
Zyklen (allgemeiner “unit pairs”) können eliminiert werden. [5:§7.1.4]
AberDurch die Eliminierung der ϵ-Produktionen und der Zyklen (bzw.“unit pairs”) kann P erheblich größer werden.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 13
Outline
1 Kompetenz versus Performanz
2 Äquivalenz und Normalformen
3 X-bar-Schema
4 Derivational Theory of Complexity
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 14
X-bar-Schema
Chomsky (1970)
“To introduce a more uniform notation, letus use the symbol X for a phrase containingX as its head. Then the base rules intro-ducing N , A, and V will be replaced by aschema (48), where in place of . . . thereappears the full range of structures thatserve as complements and X can be any oneof N , A, or V :
(48) X → X . . .
Continuing with the same notation, thephrases immediately dominating N , A and V
will be designated N , A, V respectively.“
X
[Spec,X] X
X Y
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 15
Anwendungsbeispiel
ϵ-freie Regeln für NPs
NP → Alpakas | die Alpakas | freche Alpakas | die frechen Alpakas| die hungrigen frechen Alpakas | . . .
x-bar-Regeln für NPs
?Weiterentwicklung in Jackendo� (1977) und Stowell (1981).
Kritische und formal adequate Besprechung in Kornai & Pullum(1990).
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 16
Anwendungsbeispiel
ϵ-freie Regeln für NPs
NP → Alpakas | die Alpakas | freche Alpakas | die frechen Alpakas| die hungrigen frechen Alpakas | . . .
x-bar-Regeln für NPs
?Weiterentwicklung in Jackendo� (1977) und Stowell (1981).
Kritische und formal adequate Besprechung in Kornai & Pullum(1990).
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 16
X-bar-Schema nach Kornai & Pullum (1990)
Lexicality
A CFG observes Lexicality i� every nonterminal is X i , where X ∈ VT
and i > 0.
SuccessionA Lexicality observing CFG observes Succession i� every rule rewrit-ing some nonterminal Xn has a daughter labeled Xn−1.
Weak SuccessionA Lexicality observing CFG observes Weak Succession i� every rulerewriting some nonterminal Xn has a daughter labeled Xn−1 or Xn.
Uniformity
A Lexicality-observing CFG observes Uniformity i� ∃m ∈ N[VN =
{X i |1 ≤ i ≤ m,X ∈ VT }]
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 17
X-bar-Schema nach Kornai & Pullum (1990) (cont.)
Maximality
A CFG observing Lexicality and Succession observes Maximality i�for every rule Xn → YXn−1Z , the strings Y and Z are in V ∗M, whereVM = {Xm |X ∈ VT }.
Centrality
A Lexicality-observing CFG observes Centrality i� the start symbolis the maximal projection of a distinguished preterminal.
Peripherality
A Lexicality-observing CFG observes Peripherality i� in any rulerewriting X 1 as YX 0Z , either Y = ϵ or Z = ϵ .
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 18
X-bar-Schema nach Kornai & Pullum (1990) (cont.)
Optionality
A CFG G = 〈VN ,VT , P, S〉 observes Optionality i� for every rule in Pof the form α → W there exist β , W1, W2 such that
1 β ∈ (VN ∪ VT );2 W1,W2 ∈ (VN ∪ VT )∗;3 W = W1βW2; and
4 the rule α → W ′1βW
′2 in P for all strings W ′
1 and W ′2 con-
structible by deleting some elements from W1 and W2, respec-tively. In such rules, β will be called the CORE.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 19
Weniger Komplexität? (Kornai & Pullum 1990)
Standard X-bar Grammar (SXBG)
A Standard X-bar Grammar (SXBG) is a Lexicality-observing CFG inwhich the rules have the form Xn → YXn−1Z , where Y ,Z ∈ V ∗M.
Falls ϵ-frei: Ja! (wenige endliche Sprachen)Beispiel: SXBG mit genau einem Präterminal σ :
Sei G = 〈{σ 1}, {σ }, {σ 1 → σ },σ 1〉, dann L(G) = {σ }.Sei G = 〈{σ 1}, {σ }, {σ 1 → σ 1σ ,σ 1 → σ },σ 1〉, dann L(G) ={σ n |n > 0}.
Standard X-bar Grammar mit ϵ-Produktionen (SXBGϵ )
A Standard X-bar Grammar (SXBG) is a Lexicality-observing CFG inwhich the rules have the form Xn → YXn−1Z , where Y ,Z ∈ V ∗M, orX 0 → ϵ .
Falls nicht ϵ-frei: Nein! (schwach äquivalent zu CFG)Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 20
Weniger Komplexität? (Kornai & Pullum 1990) (cont.)
CAVEATX-bar-Schema wird sehr unterschiedlich eingesetzt.
Optionalität senkt die Ausdrucksstärke, wird aber kaum ver-wendet.
Implizite Grundannahme scheint zu sein: Xn mit n > 0 sindderivationell nicht ambig,
Nur Kompetenz, d.h. Sprachklassen-Komplexität, wird betra-chtet.
Was die Regelanzahl und die Ableitungslänge betri�t, sind SXBGssicherlich nicht optimal.
Anliegen ist, die Ableitungsambiguität (auch grammatik-übergreifend) zu minimieren.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 21
Outline
1 Kompetenz versus Performanz
2 Äquivalenz und Normalformen
3 X-bar-Schema
4 Derivational Theory of Complexity
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 22
Derivational Theory of Complexity (DTC)
Vermutung bezogen auf die Transformationsgrammatik
Verarbeitungskomplexität korreliert mit der Anzahl der nötigenTransformationen.
Grammatik/Wort-Komplexität (Ableitungslänge)
w1 ist komplexer als w2 bezüglich G, falls|S ` ... ` w1 | > |S ` ... ` w2 |
Ho�nung auf
explizite Performanzmodelle
Adäquatheitstests für linguistische Theorien
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 23
Transformationsgrammatik
Chomsky (1957; 1965)CFG Lexikon
Deep Structure “kernel sentences”
Conceptual StructureTransformationen
Surface Structure
Phonological Structure
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 24
Transformationsgrammatik
Chomsky (1957; 1965)“kernel sentences”
S
NP
Peter
VP
V
loves
NP
Susan
=⇒
S
NP
Susan
VP
AUX
is
V
loved
PP
P
by
NP
Peter
NP1 V NP2 → NP2 AUX V by NP1
Komplexitätstheoretisch sehr problematisch: Das Wortproblemfür TG ist unentscheidbar (Peters & Ritchie 1973).
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 25
Transformationsgrammatik
Chomsky (1957; 1965)“kernel sentences”
S
NP
Peter
VP
V
loves
NP
Susan
=⇒
S
NP
Susan
VP
AUX
is
V
loved
PP
P
by
NP
Peter
NP1 V NP2 → NP2 AUX V by NP1
Komplexitätstheoretisch sehr problematisch: Das Wortproblemfür TG ist unentscheidbar (Peters & Ritchie 1973).
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 25
Kontra DTC
Gegenevidenz (Fodor, Bever & Garre� 1974):
Passiv(1) a. The first shot the tired soldier the mosquito bit fired missed.
b. The first shot fired by the tired soldier bi�en by themosquito missed.
Ellipse
(2) a. John swims faster than Bob swims.b. John swims faster than Bob.c. John swims faster than Bob does.
Hängt stark von der Analyse ab![10]
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 26
Kontra DTC
Gegenevidenz (Fodor, Bever & Garre� 1974):
Passiv(1) a. The first shot the tired soldier the mosquito bit fired missed.
b. The first shot fired by the tired soldier bi�en by themosquito missed.
Ellipse
(2) a. John swims faster than Bob swims.b. John swims faster than Bob.c. John swims faster than Bob does.
Hängt stark von der Analyse ab![10]
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 26
Kontra DTC
Gegenevidenz (Fodor, Bever & Garre� 1974):
Passiv(1) a. The first shot the tired soldier the mosquito bit fired missed.
b. The first shot fired by the tired soldier bi�en by themosquito missed.
Ellipse
(2) a. John swims faster than Bob swims.b. John swims faster than Bob.c. John swims faster than Bob does.
Hängt stark von der Analyse ab![10]
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 26
Zusammenfassung
Unterscheidung von “Kompetenz” und “Performanz”
“Performanz” bezieht sich auf Regeln.
Äquivalenz und Normalformen
regelbezogenen Komplexitätsbegri�e (Regelanzahl, Ambiguität,Ableitungslänge)
Beispiele aus der formalen Linguistik: X-bar-Syntax und DTC
Nächste Sitzung: andere wichtige performanzbezogeneKomplexitätsbegri�e (Automatentheorie, Raum- undZeitkomplexität)
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 27
Literaturverzeichnis
[1] Chomsky, Noam. 1957. Syntactic structures. Den Haag: Mouton.[2] Chomsky, Noam. 1965. Aspects of the theory of syntax. Cambridge, MA: The MIT Press.[3] Chomsky, Noam. 1970. Remarks on nominalization. In Roderick Jacobs &
Peter Rosenbaum (eds.), Readings in English transformational grammar, 184–221.Waltham, MA: Ginn.
[4] Fodor, Jerry A., Thomas G. Bever & Merrill F. Garre�. 1974. The psychology of language:an introduction to psycholinguistics and generative grammar. McGraw-Hill.
[5] Hopcro�, John E., Rajeev Motwani & Je�rey D. Ullman. 2001. Introduction to automatatheory, languages and computation. Addison-Wesley.
[6] Jackendo�, Ray. 1977. X′ syntax: A case study of phrase structure. Cambridge, MA: MITPress.
[7] Kornai, András & Geo�rey K. Pullum. 1990. The x-bar theory of phrase structure.English. Language 66(1). 24–50. http://www.jstor.org/stable/415278.
[8] Nijholt, Anton. 1980. Context-free grammars: Covers, normal forms, and parsing.(Lecture Notes in Computer Science 93). Berlin: Springer.
[9] Peters, Stanley P. & Robert W. Ritchie. 1973. On the generative power oftransformational grammar. Information Sciences 6. 49–83.
[10] Phillips, Colin. 1996. Order and structure. Cambridge, MA: MIT Doctoral dissertation.http://dspace.mit.edu/handle/1721.1/10666.
[11] Stowell, Timothy A. 1981. Origins of phrase structure. Cambridge, MA: MIT MITdissertation.
Timm Lichte & Christian Wurm (HHU Düsseldorf) Komplexität und natürliche Sprache 28
Recommended