Syntax natürlicher Sprachen - Vorlesung 9: Unifikation und ...martin/teaching/data/syntax-ws1718/...../lmu.png GetypteMerkmalstrukturen Carpenter,Bob(1992).TheLogicofTypedFeatureStructures

../lmu.png

Syntax natürlicher SprachenVorlesung 9: Unifikation und merkmalsbasiertes Parsing

Martin Schmitt

Ludwig-Maximilians-Universität München

19.12.2017

Martin Schmitt (LMU) Syntax natürlicher Sprachen 19.12.2017 1

../lmu.png

Themen der heutigen Vorlesung

1 Formale GrundlagenMerkmalstrukturenSubsumptionUnifikationBedingungen

2 ImplementierungMerkmalstrukturenUnifikation

3 Parsing mit MerkmalstrukturenModifizierter Earley ParserKomplexität


../lmu.png

Getypte Merkmalstrukturen

Carpenter, Bob (1992). The Logic of Typed Feature Structures.Englisch. Cambridge Tracts in Theoretical Computer Science.Cambridge University Press.


../lmu.png

Typen

Definition (Type, v)Sei Type eine endliche Menge von Typen mitVererbungshierarchie v.

Wenn für A,B ∈ Type gilt, dass A v B , dannerbt B Informationen von A.wird B von A subsumiert.ist A allgemeiner als B .ist A Obertyp von B .ist B Untertyp von A.


../lmu.png

Vererbung

Eigenschaften von Type, vtransitiv (∀A,B ,C ∈ Type. A v B ∧ B v C =⇒ A v C )

reflexiv (∀A ∈ Type. A v A)

antisymmetrisch (∀A,B ∈ Type. A v B ∧ B v A =⇒ A = B)(keine Vererbungsschleifen)

→ partielle Ordnung (d. h. nicht alle Elemente von Type müssenmiteinander vergleichbar sein)

wohldefinierte Unifikationsoperation

→ Existenz eines eindeutigen allgemeinsten Typs(∃1A ∈ Type. ∀B ∈ Type. A v B)

⊥ definiert als kleinstes Element von Type bzgl. vMartin Schmitt (LMU) Syntax natürlicher Sprachen 19.12.2017 6

../lmu.png

Beispiel: Typhierarchie

3-s-mask 3-s-fem 3-s-neut

1-sing 3-sing 1-plu 3-plu

1st 3rd sing plu

⊥


../lmu.png

Noch ein Beispiel: Typhierarchie

Nominativ Akkusativ

Nom-Akk Dativ

Genitiv nicht-Genitiv

⊥

Vgl. z. B. die Paradigmen:der Hund, des Hundes, dem Hund, den Hunddas Buch, des Buches, dem Buch, das Buch


../lmu.png

Merkmale

Definition (Feat)Sei Feat eine endliche Menge von Merkmalen (engl. features).

(Ohne weitere Anforderungen an Struktur oder Eigenschaften)

BeispielFeat = {GEN, CASE, NUM, AGR, PER, MOOD, CAT, TENSE}


../lmu.png

Merkmalstrukturen

DefinitionEine Merkmalstruktur über Type und Feat ist definiert als TupelF = (Q, q̄, θ, δ) mit:

Q : endliche Menge von Knoten mit Wurzel q̄q̄ ∈ Q : Wurzelknotenθ :Q → Type : totale Typisierungsfunktionδ : Feat× Q → Q : partielle Merkmal-Wert-Funktion

Sei F die Menge aller Merkmalstrukturen.

q̄

q1 CAT θ(q1) N

q2 AGR

[q3 CASE θ(q3) Nomq4 NUM θ(q4) Pl

]Feat ={CAT,AGR,CASE,NUM}Type ={N ,Nom,Pl , agr,word,⊥}


../lmu.png

Visualisierung als Graph I

Beschrifteter GraphEin beschrifteter Graph ist definiert als TupelG = (V ,E , lV , lE , LV , LE ) mit

V : Menge der Knoten (engl. vertices)E ⊆ V × V : Menge der Kanten (engl. edges)lV :V → LV : Beschriftungsfunktion für Knoten (engl. label)lE :E → LE : Beschriftungsfunktion für KantenLX : Menge von Beschriftungen für X

A

BC D

a

b

c


../lmu.png

Visualisierung als Graph II

VisualisierungDer Graph zu einer Merkmalstruktur F = (Q, q̄, θ, δ) ist gegebendurch:

V := Q

E := {(q1, q2) | ∃f . δ(f , q1) = q2}LV := Type; lV := θ

LE := Feat; lE (q1, q2) := {f | δ(f , q1) = q2}

AnmerkungZur Vereinfachung werden einelementige Mengen ohneMengenklammern geschrieben.

Also a statt {a}.


../lmu.png

Beispiel: Graphdarstellung

q̄

q1

q2

q3

q4

N

Nom

Pl

word

agr

CAT

AGRCASE

NUM


../lmu.png

Variablen

VariablenVar sei eine abzählbar unendliche Menge von Variablen.Häufig wird Var = N benutzt.Es gibt aber auch andere Möglichkeiten;z. B. im NLTK: ASCII-Identifier (?x, ?y, . . . )

Definition (Zuweisungsfunktion, Valuation)Eine Zuweisung α : Var→ F ist eine totale Funktion, die alleVariablen an Merkmalstrukturen bindet.


../lmu.png

Reentrance

Reentrance (dt. Wiedereintritt)Durch das Aufstellen von Bedingungen (s. später) können Variablenan verschiedene Teile von Merkmalstrukturen gebunden werden.Diese müssen gleich sein.

Beispiel

ORTH folgt

SYN

[SBJ 1

OBJ 2

]

SEM

[AGT 1

PAT 2

]

ORTH folgt

SYN

[SBJ 1 HundOBJ 2 Katze

]

SEM

[AGT 1

PAT 2

]


../lmu.png

Subsumption

Erweiterung auf MerkmalstrukturenF = (Q, q̄, θ, δ) subsumiert F ′ = (Q ′, q̄′, θ′, δ′), genau dann wenn eseine totale Funktion h :Q → Q ′ gibt, sodass:

h(q̄) = q̄′

θ(q) v θ′(h(q)) für alle q ∈ Q

h(δ(f , q)) = δ′(f , h(q)) für alle q ∈ Q und f ∈ Feat,für die δ(f , q) definiert ist

Beispiel

q̄[q1 CAT N

]v q̄′

[q′1 CAT Nq′2 GEN mask

]h(q̄) = q̄′

h(q1) = q′1


../lmu.png

Unifikation I

Unifikation (t) für TypenDie Unifikation zweier Typen kann als mengentheoretischeVereinigung verstanden werden.

Das Ergebnis der Unifikation zweier Typen A,B ∈ Type ist ihrekleinste obere Schranke in Type bzgl. v.A t B = C ⇐⇒ A v C und B v C und

∀D ∈ Type. A v D ∧ B v D =⇒ C v D


../lmu.png

Beispiel: Typunifikation

3-s-mask 3-s-fem 3-s-neut

1-sing 3-sing 1-plu 3-plu

1st 3rd sing plu

⊥1st t plu = 1-plu sing t 3-s-mask = 3-s-mask


../lmu.png

Noch ein Beispiel: Typunifikation

Nominativ Akkusativ

Nom-Akk Dativ

Genitiv nicht-Genitiv

⊥

nicht-Genitiv t Nominativ = NominativNom-Akk t Dativ = undefiniert


../lmu.png

Unifikation II

Unifikation (t) für MerkmalstrukturenIdee: Unifikation ebenfalls kleinste obere Schranke bzgl. derSubsumptionsrelation v auf MerkmalstrukturenAlgorithmus in zwei Schritten:

1 Identifiziere korrespondierende (äquivalente) Knoten2 Unifiziere deren Typen

Formale Definition: Identifikation (Schritt 1)Für Merkmalstrukturen F = (Q, q̄, θ, δ) ,F ′ = (Q ′, q̄′, θ′, δ′) mitQ ∩ Q ′ = ∅ sei die Äquivalenzrelation ≡ wie folgt definiert:

q̄ ≡ q̄′

δ(f , q) ≡ δ′(f , q′) wenn beide Seiten definiert und q ≡ q′


../lmu.png

Formale Definition: Typunifikation (Schritt 2)Die Unifikation von F und F ′ ist dann wie folgt definiert:

F t F ′ = ((Q ∪ Q ′)/≡, [q̄]≡, θ≡, δ≡)

mitθ≡([q]≡) =

⊔{(θ ∪ θ′)(q′) | q′ ≡ q}

und

δ≡(f , [q]≡) =

{[(δ ∪ δ′)(f , q)]≡ falls (δ ∪ δ′)(f , q) definiertundefiniert sonst

Notation (für ≡ Äquivalenzrelation über X )[x ]≡ = {y ∈ X | y ≡ x}X/≡ = {[x ]≡ | x ∈ X}


../lmu.png

Beispiel: (Formale) Unifikation

q1

q2 CAT N

q3 AGR

[q4 NUM Sgq5 CAS nicht-Gen

] q6

q7 ORTH Hund

q8 AGR

[q9 NUM Sgq10 CAS Nom

]

1 Identifikation korrespondierender Knotenq1 ≡ q6 (Initialisierung)

Nach 1 Schritt mit δ:q3 ≡ q8

Nach 2 Schritten mit δ:q4 ≡ q9q5 ≡ q10


../lmu.png

Beispiel: (Formale) Unifikation

q1

q2 CAT N

q3 AGR

[q4 NUM Sgq5 CAS nicht-Gen

] q6

q7 ORTH Hund

q8 AGR

[q9 NUM Sgq10 CAS Nom

]2 Typunifikation

QU = {{q1, q6} , {q2} , {q7} , {q3, q8} , {q4, q9} , {q5, q10}}

q̄U = {q1, q6}

θ≡({q2}) = N, θ≡({q7}) = Hund , θ≡({q4, q9}) = Sg ,θ≡({q5, q10}) = Nom, θ≡({q1, q6}) = word,θ≡({q3, q8}) = agr

δ(CAT, {q1, q6}) = {q2}, δ(ORTH, {q1, q6}) = {q7}, . . .


../lmu.png

Theoretische Resultate

LemmaWenn F t F ′ definiert ist, dann ist F t F ′ ∈ F eine Merkmalstruktur.

TheoremF t F ′ ist die kleinste obere Schranke von F und F ′ in (F ,v), falls Fund F ′ eine obere Schranke haben.

Für Beweise siehe Carpenter (1992).


../lmu.png

Bedingungen I

PfadeSequenzen von Merkmalen werden Pfade genannt.Path = Feat∗ sei die Menge aller Pfade.Für p ∈ Path,F ∈ F sei F@p der Knoten in F , den man amEnde von Pfad p erhält.

BeispieleAGR–NUMSYN–SBJ–AGR–NUMORTHε (der leere Pfad)


../lmu.png

Bedingungen II

Definition (Beschreibung Desc)Die Menge der Beschreibungen über Type und Feat sei die kleinsteMenge, die folgende Bedingungen erfüllt:

A ∈ Desc, für alle A ∈ Type

p : d ∈ Desc, für p ∈ Path, d ∈ Desc

x ∈ Desc, für alle x ∈ Var

d ∧ e ∈ Desc, für d , e ∈ Desc

BeispielAGR–NUM : Sg

SYN–SBJ : 1 ∧ SEM–AGT : 1


../lmu.png

Bedingungen III

ErfülltheitDie Erfülltheitsrelation |=α zwischen Merkmalstrukturen undBeschreibungen ist gegeben durch:

F |=α A ⇐⇒ A ∈ Type und A v θ(q̄)

F |=α p : d ⇐⇒ F@p |=α d

F |=α x ⇐⇒ x ∈ Var und α(x) = F

F |=α d ∧ e ⇐⇒ F |=α d und F |=α e


../lmu.png

Erfülltheit: Beispiel

Sei F eine Merkmalstruktur.

F =

CAT N

AGR

[NUM 1 SgCAS Nominativ

] α( 1 ) = F@AGR–NUM

Welche Beschreibungen aus Desc erfüllt F?F |=α N ? Nein!F |=α CAT :N ? Ja!F |=α AGR–CAS : nicht-Genitiv ? Ja!

Denn: nicht-Genitiv v Nominativ

F |=α AGR–NUM : 1 ? Ja!Obige Schreibweise stellt diese Bedingung explizit an F und α.


../lmu.png

Beschreibungen als Merkmalstrukturen

MGSat (allgemeinster Erfüller)Zu jeder konsistenten (widerspruchsfreien) Beschreibung d ∈ Descgibt es eine Merkmalstruktur MGSat(d) ∈ F mit der Eigenschaft

∀F ∈ F . F |= d ⇐⇒ MGSat(d) v F

Konstruktion

Für A ∈ Type: MGSat(A) =[A]

MGSat(f1f2 . . . fn : d) =

[f1

[f2 . . .

[fn MGSat(d)

]]]Wenn Var = N, dann MGSat(1) =

[1

]MGSat(d ∧ e) = MGSat(d) tMGSat(e)


../lmu.png

Bedingungsprüfung per Unifikation: Beispiel

Grammatikregel mit ConstraintNP[CAS=?y] → DET[GEN=?x,CAS=?y] N[GEN=?x]

Bedingungen als Beschreibungentype :NP ∧ CAS : 2

type :DET ∧ GEN : 1 ∧ CAS : 2

type :N ∧ GEN : 1

Bedingungen als Merkmalstrukturen[type NPCAS 2

]→

type DETGEN 1

CAS 2

[type NGEN 1

]


../lmu.png

Merkmalstrukturen: Implementierung mit Zeigern

NULL

Sg

NULL

3

NULL

CONTENT

POINTER

NUM

PER

CONTENT

POINTER

CONTENT

POINTER


../lmu.png

Reentrance (Wiedereintritt)

NULL

folgt

NULL

NULL

NULL

Hund

Katze

NULL

NULL

NULL

NULL

CONTENT

POINTER

ORTH

SYN

SEM

CONTENT

POINTER

CONTENT

POINTER

SBJ

OBJ

CONTENT

POINTER

AGT

PAT

CONTENT

POINTER

CONTENT

POINTER

CONTENT

CONTENT

POINTERPOINTER


../lmu.png

Unifikation: Implementierung mit Zeigern[NUM Sg

]t[PER 3

]

q̄

NULL

Sg

NULL

NULL

NULL

q̄′3

CONTENT

POINTER

NUM

PER

CONTENT

POINTER

CONTENT

POINTERPOINTER

CONTENT

PERPOINTER

CONTENT


../lmu.png

Unifikationsalgorithmus

function unify(f1-orig, f2-orig)f1 ← deref(f1-orig) . Verfolgen von .pointerf2 ← deref(f2-orig)if f1, f2 ∈ Type then

return unifyValues(f1, f2) . z. B. per Typhierarchieif f1 ∈ ContPoint ∧ f1.content is NULL then

f1.pointer ← f2return f2

if f2 ∈ ContPoint ∧ f2.content is NULL thenf2.pointer ← f1return f1

if f1, f2 ∈ ContPoint thenf2.pointer ← f1return unify(f1.content, f2.content)

. . .Martin Schmitt (LMU) Syntax natürlicher Sprachen 19.12.2017 35

../lmu.png

Unifikationsalgorithmus II

function unify(f1-orig, f2-orig). . .if f1, f2 ∈ F then

for all feat2 ∈ f2 dofeat1← erstelle oder finde entsprechendes Feature in f1if unify(feat1, feat2) = failure then

return failurereturn f1

return failure . Kein Fall vorher hat zugetroffen


../lmu.png

Earley Algorithmus mit Merkmalen

1. MöglichkeitParsen wie bisher und am Ende versuchen, zu unifizierenUnschön: Zahl von möglichen Analysen wird nicht so früh wiemöglich beschränkt

→ Optimierungspotential

2. MöglichkeitMerkmalstruktur zu jedem Earley-Zustand hinzufügenComplete-Operation unifiziert die Merkmalstrukturen der beidenZuständePredict-Operation fügt neuen Zustand nur hinzu, wenn er vonkeinem vorhandenen subsumiert wirdNicht-destruktive Unifikation einsetzen! (Kopien machen!)


../lmu.png

Merkmalbasiertes Parsing: Komplexität

Unterschied gegenüber ursprünglichem Earley ParserZustandsmenge nach Zuständen durchsuchen, derenMerkmalstrukturen mit gegebener Merkmalstruktur unifizierenHäufiges Kopieren von Merkmalstrukturen (nicht-destruktiveUnifikation)

Komplexitätim Allgemeinen ist Unifikationsparsen „relativ teuer“NP-vollständig in manchen Versionenmit sehr umfangreichem Desc sogar Turing-vollständig (!)Zahlreiche Varianten existieren

Quasi-destruktive Unifikation (Hideto Tomabechi)Tractable HPSG (Gerald Penn)


../lmu.png

Rückblick: Heutige Themen

1 Formale GrundlagenMerkmalstrukturenSubsumptionUnifikationBedingungen

2 ImplementierungMerkmalstrukturenUnifikation

3 Parsing mit MerkmalstrukturenModifizierter Earley ParserKomplexität


Documents

Syntax natürlicher Sprachen - Vorlesung 9: Unifikation und ...martin/teaching/data/syntax-ws1718/...../lmu.png GetypteMerkmalstrukturen Carpenter,Bob(1992).TheLogicofTypedFeatureStructures