Complexity in grammar - Formale Komplexitätsbegriffe

Complexity in grammar
Formale Komplexitätsbegriffe
Timm Lichte
HHU Düsseldorf
WS 2015/2016, 28.10.2015
SFB 991
Komplexität?
≈ Vielschichtigkeit, Schwierigkeit — Effizienz, Ökonomie, Sparsamkeit
Komplexitäten!
Komplexität einer formalen Grammatik
Komplexität einer formalen Sprache
Komplexität der Verarbeitung (Parsen/Generierung) einer
Sprache anhand einer Grammatik
Komplexität eines natürlich-sprachlichen Phänomens
Komplexität einer natürlichen Sprache
⇒ Wie lässt sich Komplexität formal präzise charakterisieren?
Was verursacht Komplexität?
Lichte (HHU)
2
Ontologie
Wir betrachten zunächst Stringsprachen:
a / w ∈ LG ∈ {LG |G ∈ Ĝ}
a
w
LG
Ĝ
ist ein Buchstabe und Element eines Alphabets Σ.
ist ein Wort und Element einer Sprache L.
ist die Sprache der Grammatik G.
ist eine Menge/Klasse von Grammatiken.
Beispiele:
Σ
=
w
=
L
=
G =
LG =
Lichte (HHU)
{a, b}
abba
{abba, abab, bbb, . . .}
hN, Σ, S, Pi
∗
{w 0 |S →PG w 0 }
(z.B. eine CFG)
3
Informatische Komplexität
Intuition
Je komplexer desto schwieriger auswendig zu lernen.
K (Σ):
K (w ):
K (L):
K (G):
K (G, w )
Lichte (HHU)
Komplexität eines Alphabets Σ = |Σ|
Komplexität eines Wortes w
= |w |, K (Σw ), Entropie
Komplexität einer Sprache L
= |L|
Komplexität einer Grammatik G = |G|, K (LG )
= |Menge der möglichen Derivationen| (Ambiguität)
= Summe der Längen der möglichen Derivationen
= |längste Derivation|
4
Beschreibungskomplexität
Intuition
Je komplexer desto aufwändiger zu beschreiben.
Derivationskomplexität:
K (G, w ) = |kürzeste Derivation|
Kolmogorov-Komplexität:[2]
K (w ) = |kürzeste Programm das w ausgibt|
Beispiel (Wikipedia)
Erzeugung einer Folge mit 1000 Nullen:
begin
for i:= 1 to 1000
print "0"
end
(Standardisierung durch die Minimal Description Length)
Lichte (HHU)
5
Relative extensionale Komplexität
Intuition
Je komplexer desto mächtiger.
Gegeben zwei Wörter w und w 0:
K (w ) > K (w 0 ) ←→ w . w 0
Gegeben zwei Grammatiken G und G 0:
K (G) > K (G 0 ) ←→ PG ⊃ PG0
K (G) > K (G 0 ) ←→ K (LG ) > K (LG0 ) ←→ LG ⊃ LG0
Gegeben zwei Grammatikklassen Ĝ und Ĝ 0:
K (Ĝ) > K (Ĝ 0 ) ←→ Für jede G 0 ∈ Ĝ 0 gibt es eine G ∈ Ĝ und PG0 = PG
K (Ĝ) > K (Ĝ 0 ) ←→ Für jede G 0 ∈ Ĝ 0 gibt es eine G ∈ Ĝ und LG0 = LG
⇒ berühmtestes Beispiel: Chomsky(-Schützenberger)-Hierarchie[1]
Lichte (HHU)
6
Relative extensionale Komplexität von Grammatikklassen
Chomsky(-Schützenberger)-Hierarchie[1]
type 0: recursively enumerable
ϕ→µ
a f (n)
type 1: context-sensitive
ϕ→µ
|ϕ | ≤ |µ |
N := die Menge der
Nichtterminale
T := die Menge der
Terminale (aka Σ)
n
a2 , an b n c n . . . , W k
type 2: context-free
A→µ
A ∈ N, µ ∈ (N ∪ T ) ∗
an bm c m d n , WW R
type 3: regular
A → wB oder A → a
A, B ∈ N, a ∈ T , w ∈ T ∗
Lichte (HHU)
an b m c k d l
7
Relative extensionale Komplexität von Grammatikklassen
Chomsky(-Schützenberger)-Hierarchie[1]
type 0: recursively enumerable
HPSG, TG, TM
a f (n)
type 1: context-sensitive
LFG, LBA
n
a2 , an b n c n . . . , W k
type 2: context-free
CFG, PDA
an bm c m d n , WW R
type 3: regular
FSA
Lichte (HHU)
an b m c k d l
7
Relative extensionale Komplexität von Grammatikklassen
Chomsky(-Schützenberger)-Hierarchie[1]
type 0: recursively enumerable
HPSG, TG, TM
af (n)
type 1: context-sensitive
LFG, LBA
n
a2 , an b n c n . . . , W k
mildly context-sensitive
TAG, EPDA
an bm c n d m , WW
type 2: context-free
CFG, PDA
NL is mildly contextsensitive? (Joshi [3])
⊃ CFL
cross-serial dep.
semi-linear
in PTIME
an bm c m d n , WW R
type 3: regular
FSA
Lichte (HHU)
an b m c k d l
7
Algorithmische Komplexität (Komplexitätstheorie)
Intuition
Je komplexer desto aufwändiger zu berechnen.
Modell: Turingmaschine (Turing 1936)
Band mit Feldern
Lese-/Schreibkopf
Programm
(aus Wikipedia)
Komponenten:
unendlich langes Speicherband von linear geordneten Feldern/Zellen
Lese-/Schreibkopf, der sich schrittweise auf dem Band bewegt
Programm (= endlicher Automat) kontrolliert den Kopf
Lichte (HHU)
8
Algorithmische Komplexität (Komplexitätstheorie)
Intuition
Je komplexer desto aufwändiger zu berechnen.
Modell: Turingmaschine (Turing 1936)
Band mit Feldern
Lese-/Schreibkopf
Programm
(aus Wikipedia)
Funktionsweise:
Start: Eingabe auf dem Band, Kopf direkt davor
Ende: Ausgabe auf dem Band, Programm im Endzustand
δ (Zustand, alter Zellinhalt) = (Zustand, neuer Zellinhalt, {R, L, N })
Lichte (HHU)
8
Algorithmische Komplexität (Komplexitätstheorie)
Intuition
Je komplexer desto aufwändiger zu berechnen.
Modell: Turingmaschine (Turing 1936)
Band mit Feldern
Lese-/Schreibkopf
Programm
(aus Wikipedia)
Wortproblem: w ∈ LG ?
⇒ Wie viele Schritte werden benötigt? (Zeitkomplexität)
⇒ Wie viele Zellen werden benötigt? (Raumkomplexität)
⇒ Hält die Turingmaschine? (Halteproblem)
Lichte (HHU)
8
Algorithmische Komplexität (Komplexitätstheorie)
semi-entscheidbar
entscheidbar
factorial time
EXPSPACE
EXPTIME
NPSPACE
PSPACE
NP(TIME)
P(TIME)
LIN
REALTIME
constant time
Lichte (HHU)
O(n!)
O(2p(n) )
O(2p(n) )
O(nc )
O(nc )
O(nc )
O(nc )
O(n)
O(n)
O(c)
“non-efficient”
“efficient”
9
Algorithmische × extensionale Komplexität
type 0: recursively enumerable
HPSG, TG, TM
af (n)
type 1: context-sensitive
LFG, LBA
n
a2 , W n
an b n c n . . . ,
Wk
NP
P
mildly context-sensitive
TAG, EPDA
an bm c n d m , WW
O(n6 )
type 2: context-free
CFG, PDA
an bm c m d n , WW R O(n3 )
type 3: regular
FSA
Lichte (HHU)
an b m c k d l
O(n)
10
Zusammenfassung
Komplexitätsbegriffe:
informatische Komplexität
Beschreibungskomplexität
extensionale Komplexität
algorithmische Komplexität
Andere Begriffe:
Monoton versus nicht-monoton
Fragen des Seminars:
Anwendung/Kritik in der theoretischen Linguistik?
z.B. Rolle der Grammatikgröße in der algorithmischen Komplexität?
Andere Komplexitätsbegriffe?
Lichte (HHU)
11
Entropie
(Shannon & Weaver 1949)
Maß für die Informationsdichte eines Wortes w = x1 . . . xn :
I(xi ) = − log2 (pxi )
Iges = I(x1 ) + I(x2 ) + . . . + I(xn ) =
n
X
I(xi )
i=1
Beispiel (aus Wikipedia)
w = Mississippi mit |w | = 11 und Σ = {i, M, p, s} und
p(i) =
4
1
2
4
, p(M) = , p(p) = , p(s) =
11
11
11
11
Iges = 4 · I(i) + 1 · I(M) + 2 · I(p) + 4 · I(s)
= 4 · 1.46bit + 1 · 3.46bit + 2 · 2.46bit + 4 · 1.46bit
= 20.06bit ≈ 21bit
zurück
Lichte (HHU)
12
[1]
Chomsky, Noam & Marcel-Paul Schützenberger. 1963. The algebraic theory of
context-free languages. In P. Braffort & D. Hirschberg (eds.), Computer programming
and formal systems (Studies in Logic and the Foundations of Mathematics 35), 118–161.
Elsevier.
[2] Cover, Thomas M., Peter Gacs & Robert M. Gray. 1989. Kolmogorov’s contributions to
information theory and algorithmic complexity. The Annals of Probability 17(3). 840–865.
http://www.jstor.org/stable/2244387.
[3] Joshi, Aravind K. 1985. Tree adjoining grammars: how much context-sensitivity is
required to provide reasonable structural descriptions. In David Dowty, Lauri Karttunen
& Arnold Zwicky (eds.), Natural language parsing, 206–250. Cambridge University Press.
[4] Shannon, Claude E. & Warren Weaver. 1949. The mathematical theory of communication.
Urbana, IL: The University of Illinois Press.
[5] Turing, Alan M. 1936. On computable numbers, with an application to the
Entscheidungsproblem. Journal of Mathematics 58(345-363). 5.

Download Report