Formale Methoden III - Arbeitsbereichecebert/teaching/05fm3/folien.pdf · I Die Attribut-Wert-Matrix besteht aus den Attribut-Wert-Paaren... hnumerus,pli hgenus,femi hkasus,nomi I

Formale Methoden III— Grundlagen der Unifikationsgrammatik —

Christian Ebert

[email protected]

Formale Methoden III, 2005 1

I Vorlesung: Donnerstag, 14-16 Uhr, Raum C0-281

Christian Ebert [email protected]

Sprechstunde: Donnerstag, 10-11 Uhr, Raum C6-214

I Tutorien:

Dienstag, 11-12 Uhr, Raum C01-264 (20 Personen)

Freitag, 9-10 Uhr, Raum C4-123 (45 Personen)

Daniel Jettka [email protected]

I Online:

http://www.dcs.kcl.ac.uk/pg/ebert/teaching/

Nach jeder Vorlesung: Folien und neues Aufgabenblatt

Abgabe der Aufgabenblatter: vor Beginn der nachsten Vorlesung


Literatur

I Kai-Uwe Carstensen, Christian Ebert, Cornelia Endriss, Susanne Je-kat, Ralf Klabunde, und Hagen Langer, (eds.) Computerlinguistik undSprachtechnologie – Eine Einfuhrung. 2. Auflage. Elsevier, 2004.

Kapitel 2.3 Graphen und Merkmalsstrukturen (von Peter Kolb)

Kapitel 3.4 Syntax und Parsing (von Hagen Langer)

I Andreas Witt und Stefan Muller. Gundlagen fur den Computereinsatzin der Linguistik: Attribute, Werte, Unifikation. In Horst M. Muller, editor,Arbeitsbuch Linguistik. Schoningh, 2002.


Literatur

I Stuart M. Shieber. An Introduction to Unification-Based Approaches toGrammar, CSLI, 1986.

I Gerald Gazdar and Chris Mellish. Natural Language Processing in Pro-log. Addison-Wesley, Wokingham, England, 1989.

I Mark Johnson. Attribute-Value Logic and the Theory of Grammar, CSLI,1988.

I Carl Pollard und Ivan Sag. Head-Driven Phrase Structure Grammar.,CSLI, 1994.

I Emily Bender, Ivan Sag und Thomas Wasow. Syntactic Theory: a FormalIntroduction. 2. Auflage, CSLI, 2003.


Unifikationsgrammatiken

— wozu eigentlich?


I. Motivation Erinnerung: Kontextfreie Grammatiken

Kontextfreie Grammatiken

Eine kontextfreie Grammatik (KFG) G = 〈N,T, P, S〉 besteht aus

1. einer Menge von Nichtterminalsymbolen N ,

2. einer Menge von Terminalsymbolen T ,

3. einer Menge von Produktionsregeln P der Form

A→ x1 . . . xn

wobei A ∈ N ein Nichtterminal ist und xi ∈ (N ∪T ) Nichtterminale oderTerminale sind, und

4. einem Startsymbol S ∈ N .



Spielzeuggrammatik

Nichtterminale: {S, NP , VP , Det , N, V }

Terminale: { der, die, den, Hund, Hunde, Katze, Katzen,schnarcht, schnarchen, beisst, beissen }

Produktionsregeln:

{ S → NP VP , N → Hund,NP → Det N , N → Hunde,VP → V , N → Katze,VP → V NP , N → Katzen,Det → der, V → schnarcht,Det → die, V → schnarchen,Det → den, V → beisst,

V → beissen }

Startsymbol: S



Die Spielzeuggrammatik erzeugt u.a. den Satz:

S

NP

Det

die

N

Katze

VP

V

beisst

NP

Det

den

N

Hund

Und auch: die Hunde beissen den Hund die Katze schnarchtder Hund beisst die Katzen die Hunde schnarchen

*die Katze beisst die Hund *die Hunde schnarcht*die Hunde beissen *die Katze schnarcht den Hund*der Katzen beisst *der Katzen schnarchen die Hund. . . . . .


I. Motivation Erweiterung einer kontextfreien Grammatik

Problem: Die Grammatik enthalt keine Beschrankungen hinsichtlich . . .

I Kongruenz

Innerhalb der NP kongruieren Artikel und Nomen bzgl. Numerus, Ge-nus und Kasus.

dersg, mask, nom Hundsg, mask, nom

diepl, fem, akk Katzenpl, fem, akk

*dersg, mask, nom Hundepl, mask, nom

*diesg, fem, nom Hundsg, mask, nom

Die Subjekt-NP und das Verb kongruieren bzgl. Numerus.

[der Hund]sg schnarchtsg

*[die Katzen]pl schnarchtsg



Problem: Die Grammatik enthalt keine Beschrankungen hinsichtlich . . .

I Subkategorisierung

Verben haben unterschiedliche Komplementanforderungen. Transiti-ve Verben verlangen ein Objekt, intransitive nicht.

[der Hund] schnarchtintrans

[die Katze] beissttrans [die Hunde ]

*[der Hund] schnarchtintrans [die Katze]

*[die Katze] beissttrans

Kasusanforderungen an die Komplemente (in unserem Beispiel Akku-sativ) inkl. dem Subjekt (Nominativ)

*[den Hund]akk schnarcht

*[der Hund]nom beisst [der Hund ]nom



Losungsidee: Stecke notige Information in Nichtterminale und Regeln.

Im Beispiel der Spielzeuggrammatik zunachst nur Unterscheidung von

sg/pl (Numerus)fem/mask (Genus)nom/akk (Kasus)trans/intrans (Subkategorisierung)

I Kongruenz in der NP.

Statt des Nichtterminals N , neue Nichtterminale

Nsg,fem,nom Nsg,fem,akk Npl,fem,nom Npl,fem,akkNsg,mask,nom Nsg,mask,akk Npl,mask,nom Npl,mask,akk




Dasselbe fur Det

Det sg,fem,nom Det sg,fem,akk Detpl,fem,nom Detpl,fem,akkDet sg,mask,nom Det sg,mask,akk Detpl,mask,nom Detpl,mask,akk

Anpassung der ’lexikalischen Regeln’ fur Det und N

Det sg,fem,nom → die, Nsg,fem,nom → Katze,Det sg,fem,akk → die, Nsg,fem,akk → Katze,

Det sg,mask,nom → der, Nsg,mask,nom → Hund,Det sg,mask,akk → den, Nsg,mask,akk → Hund,Detpl,fem,nom → die, Npl,fem,nom → Katzen,Detpl,fem,akk → die, Npl,fem,akk → Katzen,

Detpl,mask,nom → die, Npl,mask,nom → Hunde,Detpl,mask,akk → die, Npl,mask,akk → Hunde,




Anpassung der Regel(n): Statt NP → Det N

NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nomNP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk

NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nomNPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk

Damit ist die korrekte Behandlung der Kongruenz innerhalb der NPmoglich, z.B.

NP sg,nom

Det sg,fem,nom

die

Nsg,fem,nom

Katze

NPpl,akk

Detpl,mask,akk

die

Npl,mask,akk

Hunde



I Kongruenz von Subjekt und V bzgl. Numerus und Subkategorisierung.

Statt des Nichtterminals V , neue Nichtterminale

Vsg,trans Vsg,intransVpl,trans Vpl,intrans

Anpassung der ’lexikalischen Regeln’ fur V

Vsg,intrans → schnarcht, Vpl,intrans → schnarchen,Vsg,trans → beisst, Vpl,trans → beissen

Anpassung der Regel(n): Statt VP → V und VP → V NP

VP sg → Vsg,intrans VPpl → Vpl,intrans

VP sg → Vsg,trans NP sg,akk VP sg → Vsg,trans NPpl,akkVPpl → Vpl,trans NP sg,akk VPpl → Vpl,trans NPpl,akk



I Kongruenz von Subjekt und V bzgl. Numerus und Subkategorisierung.

Schließlich Anpassung der Regel S → NP VP

S → NP sg,nom VP sg S → NPpl,nom VPpl

Mit der geanderten Grammatik ist folgende Ableitung moglich

S

NP sg,nom

Det sg,fem,nom

die

Nsg,fem,nom

Katze

VP sg

Vsg,trans

beisst

NPpl,akk

Detpl,mask,akk

die

Npl,mask,akk

Hunde

Wichtiger: Ungrammatische Satze sind nicht mehr ableitbar!


I. Motivation Probleme kontextfreier Grammatiken

Probleme dieses Losungsansatzes:

I Explosionsartiges Wachstum der Menge der Nichtterminale und Re-geln:

• z.B.: aus der Regel NP → Det N entstanden acht Regeln

• Es kommt noch schlimmer! Folgende Erweiterungen vorstellbar:

∗ Genus: neutrum (neut)

∗ Kasus: Dativ und Genitiv (dat, gen)

∗ weitere Subkategorisierung der Verben: ditransitive Verben (z.B.geben), Satzkomplement-Verben (z.B. wissen), Infinitivkomplement-Verben (z.B. versuchen), etc.

∗ Adjektive, die auch innerhalb der NP mit Artikel und Nomen kon-gruieren, etc.




I Nichtterminalsymbole bei KFGn haben keine ’innere Struktur’,Umbenennung macht keinen Unterschied.

S → NP sg,nom VP sg S → NPpl,nom VPpl

VP sg → Vsg,intrans VPpl → Vpl,intrans

VP sg → Vsg,trans NP sg,akk VP sg → Vsg,trans NPpl,akk

VPpl → Vpl,trans NP sg,akk VPpl → Vpl,trans NPpl,akk

NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nom

NP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk

NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nom

NPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk

Det sg,fem,nom → die Nsg,fem,nom → KatzeDet sg,fem,akk → die Nsg,fem,akk → KatzeDet sg,mask,nom → der Nsg,mask,nom → Hund

... ...




I . . . ist aquivalent zu. . .S → B C S → E D

C → F D → G

C → H I C → H J

D → K I D → K J

B → L M B → N O

I → P Q I → R T

E → U V E → W X

J → Y Z J → A U

L → die M → KatzeP → die Q → KatzeN → der O → Hund

... ...

I So sieht man: wichtige Information steckt nicht tatsachlich in derGrammatik, sondern nur in der Benennung der Nichttermiale.




I Kategorienzugehorigkeit nicht ausgedruckt:

Nsg,fem,nom → Katze ; M → KatzeNsg,mask,nom → Hund ; O → Hund

Nicht ersichtlich: Katze und Hund gehoren zur selben Kategorie Nomen.

Vsg,intrans → schnarcht ; F → schnarchtVsg,trans → beisst ; H → beisst

Nicht ersichtlich: intransitive und transitive Verben sind Unterkategorien(Subkategorien) der Verben.




I Erwunschte Generalisierungen nicht wirklich ausgedruckt:

NP sg,nom → Det sg,fem,nom Nsg,fem,nom ; B → L MNP sg,nom → Det sg,mask,nom Nsg,mask,nom ; B → N ONP sg,akk → Det sg,fem,akk Nsg,fem,akk ; I → P QNP sg,akk → Det sg,mask,akk Nsg,mask,akk ; I → R T

Nicht ersichtlich: Determinierer und Nomen kongruieren.

Fazit: Mittels kontextfreien Grammatiken lassen sich wichtige linguisti-sche Eigenschaften und Generalisierungen nicht ausdrucken.

=⇒ Unifikationsgrammatiken



Merkmalsstrukturen

— Modelle der Unifikiationsgrammatik


II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen

Merkmalsstrukturen

I Merkmalsstrukturen modellieren linguistische Objekte

I Die wichtigste Operation mit Merkmalsstrukturen ist die Unifikation(kommt spater), daher der Name

I Mit Merkmalsstrukturen lassen sich Merkmale organisieren

I Beispiel: Das Nomen Katzen hat u.a. folgende Merkmale und Werte:

Kategorie: NomenNumerus: PluralGenus: FemininKasus: Nominativ

. . .



I Merkmalsstrukturen werden beschrieben mittels Attribut-Wert-Matrizen

I Eine Attribut-Wert-Matrix die diese Merkmalsstruktur beschreibt ist diefolgende: numerus pl

genus femkasus nom

I numerus, genus, kasus sind die Attribute und pl, fem, nom deren Werte

I Die Attribut-Wert-Matrix besteht aus den Attribut-Wert-Paaren. . .

〈numerus, pl〉〈genus, fem〉〈kasus,nom〉

I . . . die einfach untereinander in eine Matrix geschrieben werden.



Attribut-Wert-Matrizen

↓ beschreiben

Merkmalsstrukturen

↓ modellieren

linguistische Objekte

264

numerus plgenus femkasus nom

375

↙ ↓ ↘Kategorie: Nomen

. . . Numerus: Plural . . .Genus: Feminin

Kasus: Nominativ...

↓Katzen

I AVMs konnen unterspezifiziert hinsichtlich mancher Merkmale sein



I Attribute heissen auch. . .

• Features

• Merkmale

I Merkmalsstrukturen heissen auch. . .

• Feature Structures

I Attribut-Wert-Matrizen heissen auch. . .

• Attribute-Value-Matrices (AVM)

• Merkmalsstrukturen (!)

I Merkmalsstruktur und AWM werden oft synonym verwendet, obwohlAWMs nur Beschreibungen von Merkmalsstrukturen sind.



I Allgemeine Definition:Eine Attribut-Wert-Matrix ist eine (ungeordneten) Menge von Attribut-Wert-Paaren

I Die Werte konnen atomar sein, z.B. sg, pl, nom, akk, . . .

I . . . oder komplex, d.h. selbst wieder eine AVM

I Nicht-linguistisches Beispiel: Adressbucheintragname Peter Meier

adresse

strasse Blumenstr. 78plz 12345ort Berlin

telefon 030/12345678



I Detailierte Betrachtung der Attribut-Wert-Paare der AWM

name Peter Meier

adresse


telefon 030/12345678

Merkmal: name

Wert: Peter Meier

Typ: atomar




name Peter Meier

adresse


telefon 030/12345678

Merkmal: adresse

Wert:


Typ: komplex




name Peter Meier

adresse


telefon 030/12345678

Merkmal: telefon

Wert: 030/12345678

Typ: atomar




name Peter Meier

adresse


telefon 030/12345678

I Fur die Teilstruktur


Merkmal: strasse

Wert: Blumenstr. 78

Typ: atomar




name Peter Meier

adresse


telefon 030/12345678



Merkmal: plz

Wert: 12345

Typ: atomar




name Peter Meier

adresse


telefon 030/12345678



Merkmal: ort

Wert: Berlin

Typ: atomar



I Merke: Die Attribut-Wert-Paare sind ungeordnet.

I Reihenfolge in der Matrixschreibweise spielt keine Rolle, z.B.name Peter Meier

adresse


telefon 030/12345678

≡

adresse

ort Berlinplz 12345strasse Blumenstr. 78

telefon 030/12345678name Peter Meier



I Linguistisches Beispiel:

I Zusammenfassung der Kongruenzmerkmale unter neuem Merkmalkgr

I Neues Merkmal kat fur die Kategorie eines Ausdrucks

Hund bellt der266664

kat N

kgr

264

numerus sggenus maskkasus nom

375

377775

24kat V

kgrhnumerus sg

i35

266664

kat Det

kgr

264


375

377775



I Weiteres Linguistisches Beispiel: HPSG AWM fur Peter schlaft

266666666666666666666666666666666666664

phon ’Peter schlaft’

synsem

2666664local

2666664

cat

"head 1 verbsubcat 〈〉

#

cont 3

"reln sleepsleeper 2

#3777775

3777775

dtrs

266666666666666666666664

head-dtr

26666664

phon ’schlaft’

synsem

26664local

26664cat

24head 1

subcatD

4E35

cont 3

3777537775

37777775

comp-dtr

26666666664

phon ’Peter’

synsem 4

26666664

local

2666664

cat

"head nounsubcat 〈〉

#

cont

"index 2

"num singgend masc

##3777775

37777775

37777777775

377777777777777777777775

377777777777777777777777777777777777775

I AWMs konnen ganz schon groß werden. . .


II. Merkmalsstrukturen Merkmalsstrukturen als Graphen

Merkmalsstrukturen als Graphen

I Ein Graph ist ein Paar 〈V,E〉 bestehend aus

1. einer Menge von Knoten (engl. vertex/vertices) V und

2. einer Menge von Kanten (engl. edges) E.

Jede Kante ist ein ungeordnetes Paar (v1, v2) von Knoten.

I Beispiel: Bielefeld und Restdeutschland

V = {Bielefeld, Berlin, Frankfurt, Hamburg, Munchen}E = {(Bielefeld ,Hamburg), (Bielefeld ,Berlin), (Bielefeld ,Frankfurt),

(Bielefeld ,Munchen) }



I Grafische Darstellung:

Berlin

Munchen

Hamburg

Frankfurt

Bielefeld

620

400

270

320

I Kanten (und damit der Graph) konnen auch etikettiert (markiert) sein



http://www.bielefeld.de/de/ti/anundabreise/uebersichtsplaene/



I Gerichtete Graphen: Kanten sind geordnete Paare 〈v1, v2〉 von Knoten

I d.h. Kanten haben eine Richtung

I Beispiel: Straßennetz der Bielefelder Innenstadt

V = { x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15 }E = { 〈x1, x3〉 , 〈x2, x1〉 , 〈x2, x3〉 , 〈x3, x2〉 , 〈x3, x4〉 , 〈x4, x6〉 , 〈x4, x7〉 , 〈x5, x2〉 ,

〈x5, x9〉 , 〈x6, x4〉 , 〈x6, x5〉 , 〈x7, x4〉 , 〈x7, x8〉 , 〈x7, x10〉 , 〈x8, x6〉 , 〈x8, x7〉 ,〈x8, x9〉 , 〈x8, x11〉 , 〈x9, x8〉 , 〈x9, x11〉 , 〈x10, x7〉 , 〈x11, x8〉 , 〈x11, x13〉 ,

〈x12, x11〉 , 〈x13, x11〉 , 〈x13, x14〉 , 〈x15, x13〉 }



I Grafische Darstellung:

x1

x2

x3x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

x14

x15

Mauerstr. Ritterstr.

Altstadter Kirchplatz

Renteistr.

Klosterstr.Ni

edernstr.

Hagenbruchstr.

Kla

sing

str.

Ritterstr.

I Knoten ≈ Kreuzung Kante ≈ Straße in dieser Richtung befahrbar



I Ein Pfad ist eine Reihe von Knoten, die durch Kanten verbunden sind.I z.B. x1, x3, x4, x7, x8, x6, x5, x9, x8, x11, x13

x1x3x4

x5

x6

x7

x8

x9

x11x13

x2

x10

x12

x14

x15

I Beobachtung: x8 wird zweimal durchlaufen



I Ein Graph ist azyklisch wenn es keinen Pfad gibt, in dem Knoten mehr-fach vorkommen.

I Innenstadtgraph nicht azyklisch (x8 kam zweimal im Pfad vor).

I Eine azyklische Variante des Innenstadtgraphen:

x1

x2

x3x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

x14

x15



I Merkmalsstrukturen konnen als etikettierte, gerichtete, azyklische Gra-phen verstanden werden:

I Attribute ≈ etikettierte Kanten Werte ≈ Knoten

I Prozedur zur Bestimmung der minimalen Merkmalsstruktur, die eineAWM beschreibt:

1. Weise der AWM einen Knoten zu.

2. Weise jedem Wert in der AWM einen Knoten zu.

3. Definiere eine Kante zwischen dem Knoten der AWM und jedemKnoten eines Wertes und etikettiere sie mit dem entsprechendenAttribut.

I Bei komplexen Werten, wende dieselbe Prozedur fur die Wert-AWM an



I einfaches Beispiel:


Prozedur:





Prozedur:






pl

fem

nom

Prozedur:







pl

fem

nom

numerus

genus

kasus

Prozedur:



3. Definiere eine Kante zwischen dem Knoten der AWM und jedem Kno-ten eines Wertes und etikettiere sie mit dem entsprechenden Attribut.



I komplexeres Beispiel:

kat N

kgr


Prozedur:





kat N

kgr


N

Prozedur:






kat N

kgr


Nkat

kgr

Prozedur:







kat N

kgr


Nkat

kgr

Wiederhole Prozedur fur komplexen Wert:




kat N

kgr


Nkat

kgr






kat N

kgr


Nkat

kgr

pl

fem

nom







kat N

kgr


Nkat

kgr

pl

fem

nom

numerus

genus

kasus







I Abkurzende Schreibweise fur Pfade in Merkmalsstrukturen

I Attribute werden durch”|“ getrennt aufgelistet

I Beispiel: kgr | genuskat N

kgr


Nkat

kgr

pl

fem

nom

numerus

genus

kasus

I Platzsparend bei komplexen AWMs

"phon ’Peter’synsem | local | cat | head noun

#≡

2664

phon ’Peter’

synsem

"local

�cat

hhead noun

i�#3775


II. Merkmalsstrukturen Koreferenz

Koreferente Attribute

I Erinnerung: Kongruenz zwischen Det und N innerhalb der NP

I anders formuliert:Det und N haben dieselben Werte bei den Kongruenzmerkmalen

I Modelliere dieser Generalisierung in den Merkmalsstrukturen fur NPen:

• Kategorienmerkmal kat mit Wert NP• Merkmal dtr1 fur die erste Tochter (den Determinierer)• Merkmal dtr2 fur die zweite Tochter (das Nomen)• Zusatzliche Information, dass kgr von dtr1 und kgr von dtr2 den-

selben Wert haben



die Katze

kat NP

dtr1

kat Det

kgr 1

numerus sggenus femkasus nom

dtr2

[kat Nkgr 1

]

I 1 nennt man einen Index (oder auch engl. tag)

I Ein Index ist wie eine Variable, die auf einen Wert referiert.

I Die beiden Vorkommen von 1 zeigen an, dass sich die beiden kgrMerkmale von dtr1 und dtr2 denselben Wert teilen (ko-referieren).



I Koreferenz im Graphen

266666666666664

kat NP

dtr1

266664

kat Det

kgr 1

264


375

377775

dtr2

"kat Nkgr 1

#

377777777777775

NP

Det

N

sg

fem

nom

kat

dtr1

dtr2

kat

kgr

kgr

kat

numeru

s

genuskasus

I Die beiden kgr Kanten gehen zum selben Knoten(und damit Teilgraphen)

I Die beiden kgr Merkmale teilen sich denselben Wert



I Anders als bei Merkmalsstrukturen mit gleichen Werten

26666666666666666664

kat NP

dtr1

266664

kat Det

kgr

264


375

377775

dtr2

266664

kat N

kgr

264


375

377775

37777777777777777775

NP

Det

N

sg

fem

nom

sg

fem

nom

kat

dtr1

dtr2

kat

kgr

kat

kgr

numeru

s

genuskasus

numeru

s

genuskasus

I Die beiden kgr Kanten gehen zu identischenTeilgraphen

I Die beiden kgr Merkmale haben die gleichen Werte



I Koreferenz lasst sich auch durch Pfadgleichungen ausdrucken

kat NP

dtr1

kat Det

kgr 1


dtr2

[kat Nkgr 1

]

I Zugehorige Pfadgleichung:

dtr1 | kgr = dtr2 | kgr



I Erweiterung des Beispiels: auch NPen tragen Kongruenzinformation

I Notwendig wegen Kongruenz bzgl. Numerus zwischen Subjekts-NPund VP

I Numerus einer NP wird durch den Kopf der Phrase (hier: N) bestimmt.

kat NPkgr | numerus 2

dtr1

[kat Detkgr 1

]

dtr2

kat N

kgr 1

numerus 2 sggenus femkasus nom



I Die vorige Struktur erfullt gleichzeitig zwei Pfadgleichungen:

dtr1|kgr = dtr2|kgr

kgr|numerus = dtr2|kgr|numerus

I Andere Option:NP erbt die gesamten Kongruenzmerkmale des Kopfes

dtr1|kgr = dtr2|kgr

kgr = dtr2|kgr

I Diese Informationsteilung mittels koreferenten Attributen ist ein zentra-ler Bestandteil von Unifikationsgrammatiken

I Charakteristisch fur die Head-Driven Phrase Structure Grammar(HPSG): Kopfmerkmale bestimmen die Merkmale der Phrase (→ spater)



I In diesem Zusammenhang auch haufig benutzter Begriff: Reentranz

I von engl. reentrancy (etwa: Wiedereintrittsfahigkeit)

I ein Wert (d.h. ein Knoten) wird mehr als einmal”betreten“ (d.h. be-

nutzt)

I Folgende Begriffe sind auch gebrauchlich:

• reentrante Attribute/Merkmalsstrukturen

• koreferente Attribute

• koindizierte Attribute

• structure sharing


II. Merkmalsstrukturen Subsumtion und Ordnungen

Subsumtion und Ordnungen

I AVMs beschreiben Merkmalsstrukturen

I Merkmalsstrukturen modellieren linguistische Objekte

I z.B. beschreibt A1 alle Merkmalsstrukturen, die Nomen modellieren

A1 =[kat N

]I A2 beschreibt alle Merkmalsstrukturen, die Nomen mit Kasus Nominativ

modellieren

A2 =

[kat Nkgr | kasus nom

]



I A3 beschreibt alle Merkmalsstrukturen, die Nomen mit Kasus Nominativund Genus maskulin modellieren

A3 =

kat N

kgr

[genus maskkasus nom

]

Hund Hunde

Balle BallStuhl Stuhle

KatzeKatzen

Haus HauserTante

Tanten

HundenHundes

HausHausern

TanteTanten

A3 A2 A1



I Allgemein:Eine AWM beschreibt eine Menge von Merkmalsstrukturen

Information naher spezifizieren

⇔ Hinzufugen von zusatzlichen Attribut-Wert-Paaren

⇔ Menge wird eingeschrankt

I Andersrum ausgedruckt:Attribut-Wert-Matrizen erlauben Unterspezifikation durch Weglassenvon Informationen, z.B. ist

2664

kat N

kgr

"genus mask

kasus nom

#3775

unterspezifiert bzgl. Numerus



I Attribut-Wert-Matrizen lassen sich nach Informationsgehalt ordnen

I A subsumiert A′ wenn A′ mindestens so informativ wie A ist

I Formale Schreibweise: A v A′

I Beispiel:[kat N

]v

[kat Nkgr | kasus nom

]v

kat N

kgr


]I Beziehung Subsumtion/beschriebene Mengen:

A v A′

⇒

von A beschriebene MS ⊇ von A′ beschriebene MS



Formale Definition der Subsumtion:

A subsumiert A′ genau dann, wenn folgendes gilt:

I Jedes Attribut in A ist auch in A′ vorhanden und

• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′

• ist der Wert in A komplex, so subsumiert er den Wert in A′

I Koreferente Attribute/Pfade in M sind auch koreferent in A′.



I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1

numerus plgenus femkasus akk

dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]



I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1


dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]




I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1


dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]





I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1


dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]






I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1


dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]






I Beispiel:

kat NP

kgr 1

[numerus pl

]dtr2

[kat Nkgr 1

] v

kat NP

kgr 1


dtr1

[kat Detkgr 1

]

dtr2

[kat Nkgr 1

]




I Koreferente Attribute/Pfade in A sind auch koreferent in A′.



Weitere Beispiele:

I

[kat Nkgr | genus mask

]6v

[kat N

]E Jedes Attribut in A ist auch in A′ vorhanden

I[genus mask

]6v

[genus fem

]E ist der Wert in A atomar, so hat das Attribut denselben Wert in A′

I

[kgr

[genus mask

]]6v

[kgr

[genus fem

]]E ist der Wert in A komplex, so subsumiert er den Wert in A′



Weitere Beispiele:

I

kat NP

dtr1 | kgr 1

[genus mask

]dtr2 | kgr 1

6v

kat NP

dtr1 | kgr[genus mask

]dtr2 | kgr

[genus mask

]

E Koreferente Attribute/Pfade in A sind auch koreferent in A′

I Aber:kat NP

dtr1 | kgr[genus mask

]dtr2 | kgr

[genus mask

] v

kat NP

dtr1 | kgr 1

[genus mask

]dtr2 | kgr 1



Relationen und Ordnungen

I Eine Relation R uber einer Menge D ist eine Menge von geordnetenPaaren von Elementen aus D

I R ⊆ D ×D

I Beispiel:

Grundmenge ≡ Menge der naturlichen Zahlen (also D = N)

Relation T ≡ Menge von Zahlenpaaren, z.B.

{〈n,m〉 | n ist ein Teiler von m} = {〈1, 1〉, 〈1, 2〉, 〈2, 2〉, 〈1, 3〉, 〈3, 3〉, 〈1, 4〉, 〈2, 4〉, . . .}

I 〈8, 128〉 ∈ T oder in Infix-Notation: 8 T 128 (vgl.”8 teilt 128“)




Weitere Beispiele:

I gerichteter Graph 〈V,E〉: Kantenmenge E ist Relation uber V .

I die leere Relation ∅ (kein Paar)

I die Allrelation D ×D (alle Paare)

I die Identitatsrelation idD = {〈x, x〉 | x ∈ D}




Eine Relation R heisst . . .

I reflexiv, falls fur alle x ∈ D : xRx

(alle x stehen zu sich selbst in Relation)

I irreflexiv, falls fur kein x ∈ D : xRx

(kein x steht zu sich selbst in Relation)

I Beispiel: Teilbarkeitsrelation T ist reflexiv (jede Zahl teilt sich selbst)

1T 1, 2T 2, 3T 3, 4T 4, 5T 5, 6T 6, . . .

Damit enhalt T die Identitatsrelation: idD ⊆ T





I symmetrisch, falls gilt: xRy gdw. yRx

(mit jedem Paar ist auch das umgekehrte Paar in der Relation)

I asymmetrisch, falls gilt: ist xRy , dann ist nicht yRx

(zu jedem Paar ist das umgekehrte Paar nicht in der Relation)

I antisymmetrisch, falls gilt: ist xR y und yR x so ist x = y

(es gibt keine echt ’symmetrischen’ Paare)

I Beispiel: Teilbarkeitsrelation T ist antisymmetrisch:

Nimm zwei Zahlen n,m ∈ N.

Angenommen nTm (n teilt m) und mTn (m teilt n) . . .

. . . dann muss n = m sein, d.h. man hat es mit derselben Zahl zu tun.





I transitiv, falls gilt: ist xRy und yR z so ist xRz

(die Relation ’pflanzt sich fort’)

I Beispiel: Teilbarkeitsrelation T ist transitiv:

Nimm drei Zahlen n,m, k ∈ N.

Angenommen nTm (n teilt m) und mTk (m teilt k) . . .

. . . dann teilt n auch k, d.h. nTk.

z.B. 4T 8 und 8T 32 und wegen Transitivitat auch 4T 32.





I total (konnex, linear), falls fur x, y ∈ D gilt: xRy oder yR x

(es gibt kein Paar von Elementen, die nicht irgendwie zueinander inRelation stehen)

I sonst partiell.

I Beispiel: Teilbarkeitsrelation T ist partiell:

Fur 3 und 5 gilt beispielsweise weder 3T 5 noch 5T 3.




Man unterscheidet folgende Spezialfalle:

I (schwache) Ordnungen

sind die reflexiven, antisymmetrischen und transitiven Relationen

I starke/strikte Ordnungen

sind die irreflexiven, asymmetrischen und transitiven Relationen

I Aquivalenzrelationen

sind die reflexiven, symmetrischen und transitiven Relationen

Ist ≤ eine Ordnung uber D nennt man 〈D,≤〉 eine geordnete Menge




Beispiele:

I Die Teilbarkeitsrelation T ist eine partielle schwache Ordnung

I ’kleiner-gleich’ Relation ≤ uber N ist totale schwache Ordnung

• Reflexivitat: n ≤ n

z.B. 4 ≤ 4, 42 ≤ 42, etc.• Antisymmetrie: n ≤ m und m ≤ n⇒ n = m

• Transitivitat: n ≤ m und m ≤ k ⇒ n ≤ k,

z.B. 4 ≤ 37 und 37 ≤ 45 und damit 4 ≤ 45• Totalitat: fur n,m ∈ N gilt n ≤ m oder m ≤ n

(oder beides)

I Entsprechend: ’großer-gleich’ ≥ uber N ist totale schwache Ordnung




Beispiele:I Betrachte Potenzmenge ℘(X) einer Menge X

z.B. X = {a, b, c, . . . , z} Menge der deutschen Kleinbuchstaben

I Teilmengenrelation ⊆ uber ℘(X) ist partielle schwache Ordnung

• Reflexivitat: S ⊆ S

z.B. {c, h, j, f, t} ⊆ {c, h, j, f, t}, ∅ ⊆ ∅, etc.

• Antisymmetrie: S ⊆ T und T ⊆ S ⇒ S = T

• Transitivitat: S ⊆ T und T ⊆ U ⇒ S ⊆ U ,

z.B. {e, x} ⊆ {e, x, r} und {e, x, r} ⊆ {e, x, r, d} unddamit {e, x} ⊆ {e, x, r, d}

• Partialitat: es gibt S, T fur die weder S ⊆ T noch T ⊆ S gilt

z.B. {k, l, y} 6⊆ {k,m, b} und {k,m, b} 6⊆ {k, l, y}




Beispiele:

I Die ’kleiner’ Relation < uber N ist eine totale strikte Ordnung

• Irreflexivitat: fur kein n ∈ N: n < n

z.B. gilt nicht: 4 < 4, 42 < 42, etc.

• Asymmetrie: Wenn n < m dann nicht m < n

z.B. 5 < 8 und damit nicht 8 < 5

• Transitivitat: n < m und m < k ⇒ n < k,

z.B. 4 < 37 und 37 < 45 und damit 4 < 45

• Totalitat: fur n,m ∈ N gilt n < m oder m < n

I Entsprechend: ’großer’ > uber N ist totale strikte Ordnung




Beispiele:

I Die Relation ’hat dieselbe Schuhgroße’ uber der Menge der Men-schen ist eine Aquivalenzrelation

I Schreibe xSy fur: x hat dieselbe Schuhgroße wie y

• Reflexivitat: xSxJeder Mensch hat dieselbe Schuhgroße wie er selbst

• Symmetrie: xSy ⇒ ySxHat x dieselbe Schuhgroße wie y, so hat auch y dieselbeSchuhgroße wie x

• Transitivitat: xSy und ySz ⇒ xSz,Hat x dieselbe Schuhgroße wie y und hat y dieselbe Schuh-große wie z, dann hat auch x dieselbe Schuhgroße wie z

• Totalitat: uninteressant bei symmetrischen Relationen:S total gdw. S ist Allrelation




I Ordnungen lassen sich mittels Hasse-Diagrammen grafisch darstellen

I Gilt xRy, zeichne x unterhalb von y und verbinde beide mit einer Kante

I Lasse reflexive und transitive Kanten weg

Beispiel: Teilbarkeitsrelation 〈{1, . . . , 12}, T 〉

1

5 2 3 7 11

10 4 6 9

8 12



I Beispiel: Hasse-Diagramm fur 〈℘ ({a, b, c}) ,⊆〉

∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}



Eigenschaften der Subsumtionsrelation

I Subsumtion ist eine Relation uber der Menge A der AWMs

I Jede Merkmalsstruktur subsumiert sich selbst (A v A)kat N

kgr


] v

kat N

kgr


]⇒ Subsumtion ist reflexiv

I Wenn A v A′ und A′ v A, dann A = A′

⇒ Subsumtion is antisymmetrisch




I Wenn A v A′ und A′ v A′′, dann A v A′′

Es gilt[kasus nom

]v

[kasus nomgenus fem

]

und

[kasus nomgenus fem

]v

kasus nomgenus femnumerus sg

und deshalb auch[kasus nom

]v


⇒ Subsumtion ist transitiv




I Vergleiche[kat N

]und

[kat Det

]Es gilt weder

[kat N

]v[kat Det

]noch

[kat Det

]v[kat N

]⇒ Subsumtion ist partiell

⇒ Subsumtionsrelations ist reflexiv, antisymmetrisch, transitiv, partiell

⇒ Subsumtion ist eine partielle schwache Ordnung

I Konvention: man versteht v im Sinne von ’großer-gleich’im Hasse-Diagramm: A v B gdw. A oberhalb von B

I Entsprechendes ’kleiner-gleich’: B w A gdw. A v B



I Ausschnitt aus Hasse-Diagramm von 〈A,w〉

kat N

kgr

[genus maskkasus akk

]


] kgr


] [kat Nkgr | kasus akk

]

[kgr | genus mask

] [kat N

] [kgr | kasus akk

]


II. Merkmalsstrukturen Unifikation und Verbande

Unifikation und Verbande

I Wichtigste Operation auf AWMn: Kombination der Information

I A1 =[kat N

]A2 =

[kgr | genus mask

]↑ ↑

beschreibt MSn von Nomen beschreibt MSn von maskuli-nen linguistischen Objekten

I Kombinierte Information:

A3 =


]

beschreibt MSn von maskulinen Nomen



I Diese Operation der Informationskombination heißt Unifikation

I Im Beispiel oben: A3 ist das Ergebnis der Unifikation von A1 und A2

I Schreibweise: A3 = A1 tA2

I Also: Unifikation ist eine zweistellige Operation auf AWMn

Versuch einer Definition:

I Gegeben: zwei AWMs A und B.

Gesucht: AWM C, die die Information von A und B enthalt

I d.h. C ist mindestens so informativ wie A . . .

I . . . und gleichzeitig ist C mindestens so informativ wie B



I Anders gesagt:

A subsumiert C (A v C bzw. C w A ) und

B subsumiert C (B v C bzw. C w B )

I Definitionsversuch:

A tB = die AWM, die von A und B subsumiert wird ??

I Problem hiermit: es gibt mehrere AWMn, die die Definition erfullen.



kat N

kgr


]


] kgr


] [kat Nkgr | kasus akk

]

[kgr | genus mask

] [kat N

] [kgr | kasus akk

]

. . .



I Informelle Definition:AtB = die informationsarmste AWM, die von A und B subsumiert wird

I Also:

A subsumiert C (A v C bzw. C w A ) und

B subsumiert C (B v C bzw. C w B ) und

alle anderen AWMs die von A und B subsumiert werden, werden vonC subsumiert

I Formaler:

A tB = die AWM C fur die gilt

1. C w A und C w B, und

2. fur alle D fur die D w A und D w B , gilt D w C



Beispiele:

kat N

kgr

[genus femkasus nom

] t

kat N

kgr

[kasus nomnumerus sg

]

=

kat N

kgr

genus femkasus nomnumerus sg



Beispiele:

kat NP

dtr1 | kgr 1

[genus fem

]dtr2 | kgr 1

t

dtr2

kat N

kgr


]

=

kat NP

dtr1

kgr 1


dtr2

[kat Nkgr 1

]



Beispiele:

I Betrachte[kat N

]v

kat N

kgr

[kasus nomgenus fem

]

I[kat N

]t

kat N

kgr

[kasus nomgenus fem

] =

kat N

kgr

[kasus nomgenus fem

]

I Allgemein: wenn A v B dann A tB = B



I Unifikation klappt nicht bei inkompatibler Information

I gesucht: C =[kat N

]t

[kat Det

]I Wegen

[kat N

]v C ⇒ C muss AW-Paar 〈kat, N〉 enthalten

Wegen[kat Det

]v C ⇒ C muss AW-Paar 〈kat, Det〉 enthalten

}E

I Die Unifikation schlagt fehl

I Definiere eine unmogliche AWM ⊥

Bei fehlschlagender Unifikation:[kat N

]t[kat Det

]= ⊥

I Jetzt gibt es zu zwei AWMn A und B immer eine AWM C mit A tB = C



Untere Schranken in Ordnungen

Gegeben eine geordnete Menge 〈D,�〉

Definitionen:

I c ist eine untere Schranke von x und y, wenn c � x und c � y

I c ist die großte untere Schranke bzw. das Infimum von x und y wenn

• c eine untere Schranke von x und y ist, und

• fur jede andere untere Schranke d gilt: d � c

I Schreibe inf(x, y) fur das Infimum von x und y



Beispiele: 〈℘({a, b, c}),⊆〉

∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

inf({a, b}, {b, c}) = {b}




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

inf({a, b}, {c}) = ∅




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

inf({a, b, c}, {b, c}) = {b, c}

Fur 〈℘(X),⊆〉: inf(A,B) = A ∩B



Beispiele: 〈N, T 〉

I Untere Schranken von 18 und 30 bzgl. der Teilbarkeitsrelation T uber N:

c ist untere Schranke von 18 und 30 wenn c T 18 und c T 30

(d.h. c teilt sowohl 18 als auch 30)

⇒ untere Schranken von 18 und 30 sind 1, 2, 3 und 6.

I Infimum von 18 und 30 bzgl. der Teilbarkeitsrelation T uber N:

c ist Infimum von 18 und 30 wenn c eine untere Schranke ist und

wenn fur jede andere untere Schranke d gilt: d T c (d teilt c)

⇒ inf(18, 30) = 6.

I Fur 〈N, T 〉: inf(x, y) = großter gemeinsame Teiler von x und y



Beispiele: 〈A,w〉

⊥

[kat Nkgr | kasus akk

] [kat Detkgr | kasus akk

]

[kat N

] [kgr | kasus akk

] [kat Det

]

[ ]




⊥



]

[kat N

] [kgr | kasus akk

] [kat Det

]

[ ]




⊥



]

[kat N

] [kgr | kasus akk

] [kat Det

]

[ ]

I Fur 〈A,w〉: inf(A,B) = A tB Unifikation ≡ Infimum bzgl. w



Obere Schranken in Ordnungen

Gegeben eine geordnete Menge 〈D,�〉

Definitionen:

I c ist eine obere Schranke von x und y, wenn x � c und y � c

I c ist die kleinste obere Schranke bzw. das Supremum von x und y wenn

• c eine obere Schranke von x und y ist, und

• fur jede andere obere Schranke d gilt: c � d

I Schreibe sup(x, y) fur das Supremum von x und y




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

sup({a, b}, {b, c}) = {a, b, c}




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

sup({b}, {c}) = {b, c}




∅

{a} {b} {c}

{a, b} {a, c} {b, c}

{a, b, c}

sup({a}, ∅) = {a}

Fur 〈℘(X),⊆〉: sup(A,B) = A ∪B



Beispiele: 〈N, T 〉

I Obere Schranken von 6 und 15 bzgl. der Teilbarkeitsrelation T uber N:

c ist obere Schranke von 6 und 15 wenn 6T c und 15T c

(d.h. sowohl 6 als auch 15 teilen c)

⇒ obere Schranken von 6 und 15 sind 30, 60, 90, 120, 150, 180, . . ..

I Supremum von 6 und 15 bzgl. der Teilbarkeitsrelation T uber N:

c ist Sumpremum von 6 und 15 wenn c eine obere Schranke ist und

wenn fur jede andere obere Schranke d gilt: c T d (c teilt d)

⇒ sup(6, 15) = 30.

I Fur 〈N, T 〉: sup(x, y) = kleinstes gemeinsames Vielfaches von x und y



Beispiele: 〈A,w〉 Supremum bzgl. w ≡ Generalisierung

⊥



]

[kat N

] [kgr | kasus akk

] [kat Det

]

h i




⊥



]

[kat N

] [kgr | kasus akk

] [kat Det

]

h i




⊥



]

[kat N

] [kgr | kasus akk

] [kat Det

]

h i

Definition der Generalisierung:

A uB = sup(A,B) Information, die beiden AWMn gemein ist



Verbande (Lattices)

I sup und inf wurden mittels der Ordnungen (als spezielle Schranken)definiert

I allerdings gab es fur sup und inf auch entsprechende Operationen:

Menge Ordnung inf-Operation sup-Operation

naturliche Zahlen N Teilbarkeit T ggT(x, y) kgV(x, y)

Potenzmenge ℘(X) Teilmenge ⊆ A ∩B A ∪B

AWMn A Subsumtion w A tB A uB

I Andere Sichtweise:

Vergiss zunachst die Ordnung und betrachte Menge mit Operationenalleine



Ein Verband 〈D,∨,∧〉 ist eine Menge D mit zwei Operationen

join ∨ und meet ∧, die folgende Eigenschaften erfullen:

1 (a) x ∨ y = y ∨ x(b) x ∧ y = y ∧ x Kommutativgesetze

2 (a) x ∨ (y ∨ z) = (x ∨ y) ∨ z(b) x ∧ (y ∧ z) = (x ∧ y) ∧ z Assoziativgesetze

3 (a) x ∨ x = x(b) x ∧ x = x Idempotenzgesetze

4 (a) x ∨ (x ∧ y) = x(b) x ∧ (x ∨ y) = x Absorptionsgesetze



Beispiel: 〈℘(X),∪,∩〉 ist ein Verband (Mengenverband)

Wenn A,B,C Mengen aus ℘(X) sind, dann gilt immer:

1 (a) A ∪B = B ∪A(b) A ∩B = B ∩A Kommutativgesetze

2 (a) A ∪ (B ∪ C) = (A ∪B) ∪ C(b) A ∩ (B ∩ C) = (A ∩B) ∩ C Assoziativgesetze

3 (a) A ∪A = A(b) A ∩A = A Idempotenzgesetze

4 (a) A ∪ (A ∩B) = A(b) A ∩ (A ∪B) = A Absorptionsgesetze



Beispiel: 〈N, ggT, kgV〉 ist ein Verband

Wenn x, y, z ∈ N sind, dann gilt immer:

1 (a) ggT(x, y) = ggT(y, x)(b) kgV(x, y) = kgV(x, y) Kommutativgesetze

2 (a) ggT(x, ggT(y, z) ) = ggT( ggT(x, y), z) AssoziativgesetzeBeispiel:ggT( 9, ggT(12, 18) ) = ggT( ggT(9, 12), 18)ggT( 9, 6 ) = ggT( 3, 18)3 = 3

(b) kgV(x, kgV(y, z) ) = kgV( kgV(x, y), z)Beispiel:kgV( 9, kgV(12, 18) ) = kgV( kgV(9, 12), 18)kgV( 9, 36 ) = kgV( 36, 18)36 = 36



Beispiel: 〈N, ggT, kgV〉 ist ein Verband

Wenn x, y, z ∈ N sind, dann gilt immer:

3 (a) ggT(x, x) = x(b) kgV(x, x) = x Idempotenzgesetze

4 (a) ggT(x, kgV(x, y)) = x AbsorptionsgesetzeBeispiel:ggT( 9, kgV(9, 12) ) =ggT( 9, 36 ) =9

(b) kgV(x, ggT(x, y)) = x

Beispiel:kgV( 9, ggT(9, 12) ) =kgV( 9, 3 ) =9



Zusammenhang zwischen Ordnungen und Verbanden

I Ordnung ; Verband

Ist 〈D,�〉 eine geordnete Menge

und gibt es zu je zwei Elementen x, y immer sup(x, y) und inf(x, y)

dann ist 〈D, sup, inf〉 ein Verband (d.h. x∨y := sup(x, y), x∧y := inf(x, y))

I Beweis:

Zeige Verbandseigenschaften von 〈D, sup, inf〉ausgehend von Ordnungseigenschaften von 〈D,�〉



Beweise: Gegeben geordnete Menge 〈D,�〉

I Kommutativgesetze:sup(x, y) = sup(y, x) nach Definitioninf(x, y) = inf(y, x) nach Definition

I Idempotenzgesetze:sup(x, x) = x nach Definitioninf(x, x) = x nach Definition

I Assoziativgesetze: (lassen wir aus)

I Absorptionsgesetze:

Betrachte: sup(x, inf(x, y))

Es gilt nach der inf-Definition: inf(x, y) ≤ x und damit

sup(x, inf(x, y)) = x wegen der sup-Definition.



Zusammenhang zwischen Ordnungen und Verbanden

I Verband ; Ordnung

Ist 〈D,∨,∧〉 ein Verband

dann ist 〈D,�〉 eine geordnete Menge, mit x � y gdw. x = x ∧ y.

I Beweis:

Zeige Ordnungseigenschaften von �ausgehend von Verbandseigenschaften von 〈D,∨,∧〉

I Ordnungen mit Suprema/Infima und Verbande sind verschiedeneSichtweisen auf dieselbe Sache



Beweise: Gegeben Verband 〈D,∨,∧〉 und Definition: x � y gdw. x = x∧y

I Reflexivitat:

Idempotenz: x = x ∧ x und deshalb x � x.

I Antisymmetrie:

Angenommen x � y und y � x (d.h. x = x ∧ y und y = y ∧ x)

Kommutativitat: x ∧ y = y ∧ x und deshalb x = y.

I Transitivitat:

Angenommen x � y und y � z (d.h. x = x ∧ y und y = y ∧ z)

Dann: x = x ∧ y = x ∧ (y ∧ z) ∗= (x ∧ y) ∧ z = x ∧ z (Assoziativitat bei ∗=)

Damit x � z nach Definition von �.



Zur Erinnerung:

I AWMn mit Subsumtion ist eine geordnete Menge 〈A,w〉

I Unifikation von A und B ist das Infimum: A tB = inf(A,B)

I Generalisierung von A und B ist das Supremum: A uB = sup(A,B)

I Wichtige Frage jetzt: Existieren beide immer??

I Antwort: Ja!

Wegen ⊥ gibt es immer ein Unifikationsergebnis

Wegen [ ] gibt es immer ein Generalisierungsergebnis

⇒ AWMn mit Generalisierung und Unifikation 〈A,u,t〉 ist ein Verband



Damit erfullt 〈A,u,t〉 die Verbandseigenschaften

Wenn A,B,C AWMn sind, dann gilt immer:

1 (a) A uB = B uA(b) A tB = B tA Kommutativgesetze

2 (a) A u (B u C) = (A uB) u C(b) A t (B t C) = (A tB) t C Assoziativgesetze

3 (a) A uA = A(b) A tA = A Idempotenzgesetze

4 (a) A u (A tB) = A(b) A t (A uB) = A Absorptionsgesetze



Beispiel: Absorptionsgesetz A u (A tB) = A

[kat NP

]u

( [kat NP

]t[dtr1

[kat Det

]] )

=[kat NP

]u

kat NP

dtr1[kat Det

]

=[kat NP

]



Beispiel: Absorptionsgesetz A t (A uB) = A

[kat NP

]t

( [kat NP

]u[dtr1

[kat Det

]] )

=[kat NP

]t

[ ]

=[kat NP

]


II. Merkmalsstrukturen Erweiterungen von AWMn

Erweiterungen

I Artikelform dem ist entweder

im Dativ, singular, maskulin z.B. dem Hund, oder

im Dativ, singular, neutrum z.B. dem Schwein

I Zur Beschreibung dieser Information, zwei AWMn notwendig:kat Det

kgr

numerus sggenus maskkasus dat

kat Det

kgr

numerus sggenus neutkasus dat



I Vereinfachende Schreibweise mittels Disjunktion von Werten

I Schreibweise: wert1 ∨ wert2

I bedeutet soviel wie: wert1 oder wert2

I Damit nur noch eine AWM zur Beschreibung von dem notwendig:

kat Det

kgr

numerus sggenus mask ∨ neutkasus dat

I AWMn mit disjunktiven Werten beschreibt gleichzeitig mehrere inkom-patible Merkmalsstrukturen



Weitere Beispiele:

I den ist entweder im Akkusativ, singular, maskulin, (z.B. den Hund) oder

im Dativ, plural (alle Genera, z.B. den Hunden, den Katzen, den Schweinen)

I Disjunktive AWM zur Beschreibung von den:

kat Det

kgr

numerus sggenus maskkasus akk

∨

[numerus plkasus dat

]



Weitere Beispiele:

I die ist entweder im Nominativ oder Akkusativ, singular, feminin(z.B. die Katze) oder

im Nominativ oder Akkusativ, plural (alle Genera,z.B. die Hunde, die Katzen, die Schweine)

I Disjunktive AWM zur Beschreibung von die:

kat Det

kgr

numerus sggenus femkasus nom ∨ akk

∨

[numerus plkasus nom ∨ akk

]



Unifikation mit disjunktiven Werten

[genus mask ∨ neutkasus dat

]t

[numerus sg ∨ plgenus mask

]= ?

Prozedur zur Unifikation bei disjunktiven Werten:

1. Lose alle Disjunktionen auf (→”ausmultiplizieren“)

2. Unifiziere paarweise alle so entstanden AWMn

3. Bilde Disjunktion der Unifikationsergebnisse




1. Lose alle Disjunktionen auf:

I Auflosung von


]:

A1 =

[genus maskkasus dat

]A2 =

[genus neutkasus dat

]

I Auflosung von


]:

B1 =

[numerus sggenus mask

]B2 =

[numerus plgenus mask

]




2. Unifiziere paarweise alle so entstanden AWMn:

A1 tB1 =


]t


]=


A1 tB2 =


]t


]=

numerus plgenus maskkasus dat

A2 tB1 =


]t


]= ⊥

A2 tB2 =


]t


]= ⊥




3. Bilde Disjunktion der Unifikationsergebnisse:


]t


]

=


∨numerus plgenus maskkasus dat

(∨⊥ ∨ ⊥)

=

numerus sg ∨ plgenus maskkasus dat



Beispiel:kat Det

kgr


∨ [numerus plkasus dat

] t

[kgr | genus fem

]= ?


A1 =

kat Det

kgr


A2 =

kat Det

kgr


]



2. Unifiziere paarweise alle so entstanden AWMn:

A1 :

kat Det

kgr


t

[kgr | genus fem

]= ⊥

A2 :

kat Det

kgr


] t[kgr | genus fem

]

=

kat Det

kgr

numerus plgenus femkasus dat

3. Bilde Disjunktion der Unifikationsergebnisse:



I Unifikation mit Disjunktion kann sehr komplex werden

Abstraktes Beispiel:[f a ∨ bg x ∨ y

]t

[f b ∨ cg y ∨ z

]= ?


A1 =

[f ag x

]A2 =

[f ag y

]A3 =

[f bg x

]A4 =

[f bg y

]

B1 =

[f bg y

]B2 =

[f bg z

]B3 =

[f cg y

]B4 =

[f cg z

]



2. Unifiziere paarweise alle so entstanden AWMn:"f ag x

#t"f bg y

#= ⊥

"f ag x

#t"f bg z

#= ⊥

"f ag x

#t"f cg y

#= ⊥

"f ag x

#t"f cg z

#= ⊥

"f bg x

#t"f bg y

#= ⊥

"f bg x

#t"f bg z

#= ⊥

"f bg x

#t"f cg y

#= ⊥

"f bg x

#t"f cg z

#= ⊥

"f ag y

#t"f bg y

#= ⊥

"f ag y

#t"f bg z

#= ⊥

"f ag y

#t"f cg y

#= ⊥

"f ag y

#t"f cg z

#= ⊥

"f bg y

#t"f bg y

#=

"f bg y

# "f bg y

#t"f bg z

#= ⊥

"f bg y

#t"f cg y

#= ⊥

"f bg y

#t"f cg z

#= ⊥ 3. Bilde Disjunktion der

"f bg y

#Unifikationsergebnisse:



Listen

I Eine Liste ist endlich, geordnet und kann doppelte Vorkommen ha-ben.

I z.B. 〈4, 5, 6, 4〉 6= 〈4, 6, 5, 4〉 6= 〈4, 6, 5〉

sind verschiedene Listen ganzer Zahlen (vgl. mit Menge).

I Zur Darstellung von Listen in AWMn ist ein Trick notwendig:

Eine Liste ist entweder

• leer 〈〉,

• oder sie besteht aus einem ersten Element first und einer Restlisterest.



Beispiel: Betrachte Liste 〈4, 5, 6, 4〉

I first: 4 rest: 〈5, 6, 4〉

first: 5 rest: 〈6, 4〉

first: 6 rest: 〈4〉

first: 4 rest: 〈〉I Darstellung als AWM:

• Leere Liste ; atomarer Wert elist (”empty list“)

• Sonst zwei Merkmale first und rest



Beispiel: Betrachte Liste 〈4, 5, 6, 4〉

I In einer AWM:liste1

first 4

rest

first 5

rest

first 6

rest

[first 4rest elist

]

I Abkurzende Schreibweise: einfach die Liste selbst[

liste1⟨4,5,6,4

⟩]



I Die Elemente einer Liste konnen auch AWMn sein!

I Prominentes Beispiel (HPSG): Subkategorisierung von Verben

I Komplementanforderung in Liste unter Merkmal subcat erfasst

I transitives Verb (z.B. beissen) — verlangt zwei NPen (Subjekt & Objekt)

kat V

subcat

first

[kat NP

]rest

first[kat NP

]rest elist

Vereinfachte Schreibweise:

kat V

subcat

⟨[kat NP

],[kat NP

]⟩



I In der Praxis wird uber die Details oft hinweggesehen

I Oft benutzt: Verkettung ⊕ von Listen

I z.B. 〈a, b, c〉 ⊕ 〈x, y, z〉 = 〈a, b, c, x, y, z〉liste1 1 ⊕ 2

liste2 1

⟨a,b,c

⟩liste3 2

⟨x,y,z

⟩

I Manchmal auch Subtraktion von Listen

I z.B. 〈1, 4, 5, 1〉〈1, 4〉 = 〈5, 1〉

I ist nicht immer eindeutig: 〈1, 4, 5, 1〉〈1〉 = 〈1, 4, 5〉 oder 〈4, 5, 1〉


III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II

Eine Beispielgrammatik mit PATR-II

I PATR steht fur PArsing and TRanslation

I Wurde von Stuart Shieber (1986) entwickelt

I Ist ein Werkzeugformalismus:

macht keine expliziten linguistischen Annahmen

I Im Gegensatz zu Theorieformalismen, z.B. HPSG

I Im Folgenden: kleine Beispielgrammatik in PATR-II Notation

I Stellt grundlegende Technik der HPSG zur Argumentselektion vor



Eine PATR-II Grammatik besteht aus

I einem Lexikon — Wortformen mit zugehorigen AWMn

I Einfaches Beispiel:

Katze Hund Schweinkat N

kgr

[numerus sggenus fem

]kat N

kgr


kat N

kgr

numerus sggenus neutkasus akk

die das denkat Det

kgr


kat Det

kgr


kat Det

kgr




Eine PATR-II Grammatik besteht aus

I einer Menge von kontextfreien Regeln,

mit zusatzlichen Pfadgleichungen fur AWMn

I Beispiel:

kontextfreie Regel fur die Ableitung von Nominalphrasen:

NP → Det N

zusatzliche Pfadgleichung fur Kongruenz zwischen Artikel und Nomen:

〈Det kgr〉 = 〈N kgr〉

I In den Pfadgleichung heisst”=“ soviel wie

”kann unifiziert werden mit“



Mit dem Lexikon von oben lasst sich damit ableiten:

NP

Detkat Det

kgr


die

Nkat N

kgr


]Katze

denn〈Det kgr〉 = 〈N kgr〉



Hingegen lasst sich nicht ableiten:

∗NP

Detkat Det

kgr


das

Nkat N

kgr


]Katze

denn

numerus sggenus neutkasus nom

t [numerus sggenus fem

]= ⊥



Verallgemeinerung: Benutze Variablen fur Nichtterminalsymbole, Kate-gorieinformation steckt in kat Merkmal.

X0 → X1 X2

〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉[

kat NP]

kat Det

kgr


die

kat N

kgr


]Katze



Erweiterung: Kongruenzinformation wird an NP weiter gereichtX0 → X1 X2

〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉〈X0 kgr〉 = 〈X2 kgr〉

[kat NPkgr 1

]kat Det

kgr 1


die

[kat Nkgr 1

]Katze

I Generalisierung (Kongruenz innerhalb NP zwischen Det und N ) wirdrichtig erfasst! (vgl. kontextfreie Grammatik)



Weiteres Beispiel: VP mit transitivem Verb und Objekt im Akkusativ

X0 → X1 X2

〈X0 kat〉 = VP〈X1 kat〉 = Vtrans〈X2 kat〉 = NP〈X2 kgr kasus〉 = akk

[kat VP

]

[kat Vtrans

]beisst

kat NP

kgr


das Schwein

I Noch nicht ideal, denn die Subkategorisierungsinformation des Verbssteckt noch in der Regel



Benutze subcat Liste: Lexikoneintrag fur beisstkat V

subcat

⟨[kat NPkgr | kasus akk

],

kat NP

kgr

[numerus sgkasus nom

]⟩

I 〈subcat first〉 =

[kat NPkgr | kasus akk

](direktes Objekt)

I 〈subcat rest first〉 =

kat NP

kgr


] (Subjekt)

I 〈subcat rest rest〉 = elist



Regel fur Realisierung eines Komplements auf der subcat Liste:

X0 → X1 X2

〈X0 kat〉 = VP〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉 [

kat VP]

kat V

subcat

⟨1,

kat NP

kgr


]⟩

beisst

1

kat NP

kgr


das Schwein



Notwendige Erweiterung: Rest der subcat Liste wird weiter gereicht:X0 → X1 X2

〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉

[kat Vsubcat 2

]

kat V

subcat⟨

1

⟩⊕ 2

⟨kat NP

kgr


]⟩

beisst

1

kat NP

kgr


das Schwein

Beachte: Regel kann wiederholt angewandt werden, um alle Komple-mente zu realisieren.



Beispiel: Ditransitive Verben, z.B. geben

[Der Biber]nom gibt [dem Storch]dat [den Frosch]akkkat V

subcat

⟨[kat NPkgr | kasus dat

],

[kat NPkgr | kasus akk

],

kat NP

kgr


]⟩

I subcat Liste enthalt Informationen uber das indirekte Objekt, das di-rekte Objekt und das Subjekt

I Die Objekt werden mittels zweimaliger Anwendung der obigen Kom-plementregel realisiert



X0 → X1 X2


gibt + indirektes Objekt

kat V

subcat 2


],

kat NP

kgr


]⟩

kat V

subcat⟨

1

⟩⊕ 2

gibt

1

kat NP

kgr


dem Storch



X0 → X1 X2


gibt dem Storch + direktes Objekt

kat V

subcat 2

⟨kat NP

kgr


]⟩

kat V

subcat⟨

1

⟩⊕ 2

gibt dem Storch

1

kat NP

kgr


den Frosch



Schema: Komplementrealisierung mittels subcat Liste:kat V

subcat⟨

3

⟩kat V

subcat⟨

2, 3

⟩kat V

subcat⟨

1, 2, 3

⟩ 1

2



Schliesslich: Regel, um Satz aus Subjekt und VP abzuleiten

S → X1 X2

〈X2 kat〉 = V〈X2 subcat first〉 = 〈X1〉〈X2 subcat rest〉 = elist S

1

kat NP

kgr


der Biber

kat V

subcat⟨

1

⟩gibt dem Storch den Frosch

I Regel verlangt nach einem V mit nur einem Element auf der subcatListe (= Subjekt)



Schema: Subjekt- und Komplementrealisierung mittels subcat Liste:

S

3

kat V

subcat⟨

3

⟩kat V

subcat⟨

2, 3

⟩kat V

subcat⟨

1, 2, 3

⟩ 1

2



Achtung! In der Literatur wird die subcat Liste oft in anderer Reihenfolgebenutzt, d.h. das Subjekt ist das erste Element!

S

1

kat V

subcat⟨

1

⟩kat V

subcat⟨

1, 2

⟩kat V

subcat⟨

1, 2, 3

⟩ 3

2



Achtung! Weitere Unterschiede:

I subcat Merkmal heisst manchmal anders, z.B.

• val — von Valenz (valence)

• arg-st — von Argument-Struktur (argument structure)

I Subjekt von Komplementen durch separates Merkmal abgetrennt, z.B.spr 1

comps 2

arg-st 1 ⊕ 2

Subjekt: spr Merkmal — von Spezifizierer (specifier)

Komplemente: comp Merkmal — von Komplemente (complements)



Zusammenfassung der Grammatik:X0 → X1 X2 NP Regel

〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉〈X0 kgr〉 = 〈X2 kgr〉

X0 → X1 X2 Komplement-Regel〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉

S → X1 X2 Subjekt-Regel〈X2 kat〉 = V〈X2 subcat first〉 = 〈X1〉〈X2 subcat rest〉 = elist



Generalisierungen sind effizient ausgedruckt:

I Kongruenz innerhalb der NP:

X0 → X1 X2 NP Regel〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉 (Det und N kongruieren)〈X0 kgr〉 = 〈X2 kgr〉 (NP erbt Kongruenzinfo von N)

Vergleich mit kontextfreier Grammatik der ersten Sitzung:

NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nomNP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk

NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nomNPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk



I Subkategorisierung von Verben:

• Steckt im Lexikon (subcat liste)kat V

subcat


],

kat NP

kgr


]⟩

• Alle Verben haben weiterhin Kategorie V (siehe kat Merkmal)

Vergleich mit kontextfreier Grammatik der ersten Sitzung:

Vsg,trans Vsg,intrans Vpl,trans Vpl,intrans



I Kongruenz von Subjekt und VP bzgl. Numerus:

• Im Lexikon (siehe numerus Spezifikation beim Subjekt)kat V

subcat


],

kat NP

kgr


]⟩

• Generalisierungen uber das Lexikon auszudrucken ist ein wichtigesMittel der Unifikationsgrammatiken



Charakteristika unifikationsbasierter Grammatiken:

I Sehr wenige, allgemeine Regeln

I Viel (fast alle) Information im Lexikon

⇒ Lexikalismus

I Beschreibung der Grammatik mittels Constraints, die die Menge dererlaubten Baume/Ableitungen/AMWn beschrankt.

I keine destruktiven Operationen auf den Strukturen

⇒ Constraint-Based Lexikalism (CBL)


II. Merkmalsstrukturen Logische Formalisierung

Logische Formalisierung

I nach:

Mark Johnson. Features and Formulae, in: Computational Linguistics17(2), S. 131–151, 1991.

I AWMn konnen in Pradikatenlogik formalisiert werden

I Nur eine Teilklasse der Formeln der Pradikatenlogik notwendig



Erinnerung: Pradikatenlogik

I Terme bezeichnen die Objekte der Domane, uber die gesprochenwird.

I Konstantensymbole und Variablen sind Terme

I z.B. Konstantensymbole K = {peter, heidi, fido,wuffi,miezi}

I Variablen: unendlich viele

Bei uns: x, y, z, . . .



I Formeln machen Aussagen

I Atomare Formeln sind auf Pradikatensymbolen aufgebaut

I z.B. Pradikatensymbole P = {hund, katze, schlaeft,mag, beisst, gibt}

I Jedes Pradikatensymbol hat eine gewisse Stelligkeit

I z.B. hund : 1, schlaeft : 1, beisst : 2, gibt : 3, etc.

I Atomare Formeln sind von der Form

P (t1, . . . , tn)

odert1 = t2

wobei P ein n-stelliges Pradikatensymbol und t1, . . . , tn Terme sind.



Beispiele fur atomare Formeln:

I mag(peter, heidi)

Das Objekt, das peter bezeichnet, steht in der mag-Relation zum Ob-jekt, das heidi bezeichnet.

I hund(fido)

Fur das Objekt, das fido bezeichnet, gilt die hund-Eigenschaft.

I gibt(heidi, x, y)

Die Objekte, die heidi, x, und y bezeichnen, stehen in der gibt-Relation.

I wuffi = fido

Das Objekt, das wuffi bezeichnet, ist das Objekt, das fido bezeichnet.(wuffi und fido sind zwei verschiedene Namen fur diesselbe Sache)



Formeln sind wie folgt aufgebaut:

I Jede atomare Formel ist eine Formel

I Ist ϕ eine Formel, so auch ¬ϕ (Negation)

I Sind ϕ und ψ Formeln, so auch

• ϕ ∧ ψ (Konjunktion/”ϕ und ψ“)

• ϕ ∨ ψ (Disjunktion/”ϕ oder ψ“)

• ϕ→ ψ (Implikation/”wenn ϕ dann ψ“)

I Ist ϕ eine Formel und x eine Variable, so auch

• ∃xϕ (Existenzquantifikation/”es gibt ein x sodass ϕ“)

• ∀xϕ (Allquantifikation/”fur alle x gilt ϕ“)



Beispiele fur Formeln:

I mag(peter, heidi) ∧ ¬schlaeft(peter)

Peter mag Heidi und Peter schlaft nicht

I ∃y(katze(y) ∧ schlaeft(y))

Es gibt ein y, das eine Katze ist und das schlaft → Eine Katze schlaft

I ∀x(hund(x) → (schlaeft(x) ∨ beisst(x, heidi)))

Fur alle x gilt: wenn x ein Hund ist, dann schlaft x oder x beisst Heidi→ Alle Hunde schlafen oder beissen Heidi

I ∃x(hund(x) ∧ (∀y(katze(y) → beisst(x, y)))

Es gibt ein x, das ein Hund ist und sodass fur alle y gilt: wenn y eineKatze ist, dann beisst x y → Es gibt einen Hund, der alle Katzen beisst



AWMn als Formeln der Pradikatenlogik

I Knoten von gerichteten azyklischen Graphen (MS) sind die Objekteder Domane

I Konstantensymbole fur atomare Werte

I Pradikatensymbole fur Attribute

I Beispiel:

K = {mask, fem, neut, sg, pl, nom, dat, akk, gen, Det, N, NP, VP, elist}P = {numerus, genus, kasus, kgr, kat, subcat, first, rest}

I Pradikatensymbole ; Relation uber Knoten ≡ Kanten



Beispiele fur Formeln mit diesen Konstanten-/Pradikatensymbolen

I ∃x(genus(x, fem))

Es gibt einen Knoten x von dem aus eineKante genus zu einem Knoten fem fuhrt.

x femgenus

⇒ Logische Formel entspricht[genus fem

]I ∃x(numerus(x, pl) ∧ genus(x, fem) ∧ kasus(x,nom))

Es gibt einen Knoten x von dem aus eineKante numerus zu einem Knoten pl, eineKante genus zu einem Knoten fem undeine Kante kasus zu einem Knoten nomfuhrt.

x

pl

fem

nom

numerus

genus

kasus

⇒ Logische Formel entspricht




Beispiele fur Formeln mit diesen Konstanten-/Pradikatensymbolen

I ∃y∃x(kat(y,N)∧kgr(y, x)∧numerus(x, pl)∧genus(x, fem)∧kasus(x,nom)

)Es gibt einen Knoten y undeinen Knoten x, sodass von yaus eine Kante kat zu einemKnoten N fuhrt und eine weite-re Kante zu x, wobei von x auseine Kante numerus zu einemKnoten pl, . . . [siehe oben]

y

N

x

kat

kgr

pl

fem

nom

numerus

genus

kasus

⇒ Logische Formel entspricht

kat N

kgr




Beispiele von unerwunschten Modellen

I genus(akk, fem)

Ein Knoten akk ist mit einer Kante genusmit dem Knoten fem verbunden.

akk femgenus

E Keine Merkmalsstruktur (atomare Werte haben keine Attribute)

I ∃x(genus(x, fem) ∧ genus(x,mask))

Es gibt einen Knoten x von dem aus eineKante genus zu einem Knoten fem fuhrtund von dem aus eine Kante genus zueinem Knoten mask fuhrt.

x

fem

mask

genus

genus

E Keine Merkmalsstruktur (Werte mussen eindeutig sein)



Durch folgende Axiome (bzw. Axiomenschemata) werden die grundle-genden Eigenschaften von Modellen festgelegt:

I (AX1) Atomare Werte haben keine Attribute/ausgehenden Kanten

∀x(¬numerus(mask, x)) Kein Knoten mit mask uber numerus-Kante∀x(¬numerus(fem, x)) Kein Knoten mit fem uber numerus-Kante∀x(¬numerus(neut, x)) Kein Knoten mit neut uber numerus-Kante. . . . . .

∀x(¬genus(mask, x)) Kein Knoten mit mask uber genus-Kante∀x(¬genus(fem, x)) Kein Knoten mit fem uber genus-Kante∀x(¬genus(neut, x)) Kein Knoten mit neut uber genus-Kante. . . . . .

Ein Axiom fur jedes Paar aus Pradikatensymbol/Konstantensymbol



I (AX2) Werte sind eindeutig/Kantenrelationen sind Funktionen

∀x∀y∀z((numerus(x, y) ∧ numerus(x, z)) → y = z)

Geht eine numerus-Kante von x nach y und z, dann ist y = z

∀x∀y∀z((genus(x, y) ∧ genus(x, z)) → y = z)∀x∀y∀z((kasus(x, y) ∧ kasus(x, z)) → y = z). . .

Ein Axiom fur jedes Pradikatensymbol

I (AX3) atomare Werte sind unterschiedlich/keine Namensgleichheit

¬(fem = mask) ¬(fem = neut) ¬(fem = sg) . . .¬(mask = neut) ¬(mask = sg) ¬(mask = pl) . . .. . .

Ein Axiom fur jedes Paar von unterschiedlichen Konstantensymbolen



I Festlegung:Alle Modelle von Formeln mussen zusatzlich alle Axiome erfullen

I Damit sind die unerwunschten Modelle ausgeschlossen

I Beispiel 1:genus(akk, fem)

widerspricht (AX1)

∀x(¬genus(akk, x))

und ist damit nicht erfullbar (d.h. hat kein Modell).



I Beispiel 2:∃x(genus(x, fem) ∧ genus(x,mask))

Wegen (AX2)

∀x∀y∀z((genus(x, y) ∧ genus(x, z)) → y = z)

ergibt sichfem = mask

Das widerspricht aber (AX3)

¬(fem = mask)

Damit ist die obige Formel auch nicht erfullbar.



Weitere Beispiele von AWMn

I Disjunktion: Lexikoneintrag fur denkat Det

kgr


I Entsprechende Formel:

∃x∃y(kat(x,Det) ∧ kgr(x, y) ∧ numerus(y, sg)

∧ (genus(y,mask) ∨ genus(y,neut) ) ∧ kasus(y, dat))



∃x∃y(kat(x,Det) ∧ kgr(x, y) ∧ numerus(y, sg)

∧ (genus(y,mask) ∨ genus(y,neut) ) ∧ kasus(y, dat))

hat wie gewunscht zwei verschiedene Modelle:

x

Det

y

kat

kgr

sg

mask

dat

numerus

genus

kasus

x

Det

y

kat

kgr

sg

neut

dat

numerus

genus

kasus

Zeigt nochmals: Disjunktion nur auf der Ebene der Beschreibung



Problem mit unbeabsichtigter Koreferenzatt1[f a

]att2

[f a

] Entsprechende logische Formel:

∃x∃y∃z(att1(x, y) ∧ att2(x, z)∧ f(y, a)∧ f(z, a)

)

Mogliches Modell: x

y

z

att1

att2

f

fa

a

Aber auch: xy

z

att1

att2

fa

Diese MS wird aber durch folgende AWM beschrieben:

att1 1

[f a

]att2 1



Losung: Explizite Ungleichungen/Gleichheitenatt1[f a

]att2

[f a

] Eindeutige logische Entsprechung:

∃x∃y∃z(att1(x, y)∧att2(x, z)∧f(y, a)∧f(z, a)∧¬(y = z)

)

Einziges Modell: x

y

z

att1

att2

f

fa

aatt1 1

[f a

]att2 1

Eindeutige logische Entsprechung:∃x∃y

(att1(x, y) ∧ att2(x, y) ∧ f(y, a)

)

Einziges Modell: xy

att1

att2

fa



Unifikation

A1 =

kat N

kgr

[genus femkasus nom

] A2 =

kat N

kgr


]I Logische Formalisierung:

ϕ1 = ∃x∃y(kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)

)ϕ2 = ∃x′∃y′

(kat(x,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)

)I A1 t A2 beschreibt die MS, die die Information von A1 und A2 enthalt.

I Logische Entsprechung:

∃x∃y∃x′∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)∧ x = x′

)Formale Methoden III, 2005 164


Vereinfachung:

∃x∃y∃x′∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)∧ x = x′

)1. Weil x = x′: Umbennung von x′ in x und weglassen von ∃x′

∃x∃y∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x,N) ∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)

)2. kat(x,N) kommt zweimal vor: Lasse je ein Vorkommen weg

∃x∃y∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)

)



∃x∃y∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)

)3. Formel enthalt kgr(x, y) und kgr(x, y′).

Wegen (AX2)

∀x∀y∀z((kgr(x, y) ∧ kgr(x, z)) → y = z)

ergibt sich

y = y′

Neue Formel damit:

∃x∃y∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg) ∧ y = y′

)



∃x∃y∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg) ∧ y = y′

)4. Weil y = y′: Umbennung von y′ in y und weglassen von ∃y′

∃x∃y(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y) ∧ kasus(y,nom) ∧ numerus(y, sg)

)5. kgr(x, y) und kasus(y,nom) kommen je zweimal vor: Lasse ein Vorkom-men weg

∃x∃y(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ numerus(y, sg)

)

entspricht wie gewunscht:

kat N

kgr




Fehlschlagende Unifikation

A1 =

kat N

kgr

[genus femkasus nom

] A2 =

kat N

kgr

[kasus akknumerus sg

]I Logische Formalisierung:

ϕ1 = ∃x∃y(kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)

)ϕ2 = ∃x′∃y′

(kat(x,N) ∧ kgr(x′, y′) ∧ kasus(y′, akk) ∧ numerus(y′, sg)

)I Logische Entsprechung der Unifikation:

∃x∃y∃x′∃y′(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′, akk) ∧ numerus(y′, sg)∧ x = x′

)



Vereinfachung:

Schritte 1.-4. wie im vorigen Beispiel (x′ eliminieren, y = y′ ableiten, y′

eliminieren)

∃x∃y(

kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y) ∧ kasus(y, akk) ∧ numerus(y, sg)

)Formel enthalt kat(y,nom) und kat(y, akk)

Wegen (AX2)

∀x∀y∀z((kat(x, y) ∧ kat(x, z)) → y = z)

ergibt sichnom = akk



Das widerspricht aber (AX3)

¬(nom = akk)

Damit ist die obige Formel auch nicht erfullbar/Unifikation schlagt fehl

I Logische Folgerungen/Vereinfachungen ensprechen der Unifikations-prozedur



Warum das Ganze?

I Man kann bestehende Programme fur logisches Schliessen benutzen,um mit AWMn/Merkmalsstrukturen zu arbeiten

I Generelles Problem dabei: Pradikatenlogik ist unentscheidbar

I D.h. fur die Pradikatenlogik im Allgemeinen gibt es gar keine Algorith-men, die solche Folgerungen immer durchfuhren konnen.

I Aber: Alle Formeln der Formalisierung von Johnson sind von der Form∃∗∀∗, d.h. Existenzquantoren, dann Allquantoren, dann Formel ohneQuantor.

I Diese Klasse der Pradikatenlogik ist entscheidbar, d.h. es gibt Algorith-men die Folgerungen immer durchfuhren konnen.


IV. Typisierung Typen

Typen/Sorten

I Bislang keine klare Strukturierung der Attribute und Werte

I abschreckendes Beispiel:

genus akkkat sg

numerus

[genus NPkasus pl

]

I Festlegung notwendig, welche Attribute welche Art von Wert haben

I Typen/Sorten stellen Klassen von Merkmalsstrukturen dar

I Legen damit genau fest, wie Merkmalsstrukturen aussehen konnen



getypte Attribut-Wert-Matrizen

↓ beschreiben

getypte Merkmalsstrukturen

↓ modellieren


I Typen werden in zweierlei hinsicht verwendet:

1. Auf der Beschreibungsebene, d.h. in Attribut-Wert-Matrizen

2. Auf der Modellierungsebene, d.h. bei den Merkmalsstrukturen



I Typen werden in einer Typhierarchie angeordnet

I Diese Typhierarchie stellt eine Klassifikation der Merkmalsstrukturen(und damit der modellierten linguistischen Objekte) dar

I Welche es gibt und wie sie angeordnet sind hangt von der Gramma-tiktheorie ab

I Beispiel:zeichen

wort

determinierer nomen verb

phrase

nominal-phrase verbal-phrase

I Ein verb ist ein wort (und damit ein (linguistisches) zeichen), eine verbal-phrase ist eine phrase (und damit auch ein zeichen), etc.



zeichen

wort


phrase


I Man spricht von Supertypen und Subtypen

I z.B. ist

wort ein Subtyp von zeichen

zeichen ein Supertyp von wort

nominal-phrase ein Subtyp von zeichen, usw.

I Typen ohne Subtypen heissen maximale Typen



spielt fressen

schlief gibgetanzt verlassen

Katzemerkwurdig

Mexiko deswarum

auf

des mannesGib auf

auf der Reeperbahngroßen Frau

Warum stinkt Paul

Max wascht sich

verb wort zeichen

I Ist t Supertyp von t′, dann sind die MSen von t ⊇ MSen von t′

I Typhierarchie muss die Ordnungseigenschaften erfullen ⇒ Subsumtion

I t subsumiert t′, formal geschrieben als t v t′

I hier: zeichen v wort v verb



Erweiterung:

>

zeichen

wort


phrase


kategorie

lex-kat

det n v

ph-kat

np vp

I Neue Typen: kategorie mit Subtypen lex-kat, ph-kat, etc.

I Allgemeinster Typ >

I also z.B. kategorie v np, lex-kat v v, etc.



Angemessenheit von Attributen

I Fur jeden Typ gibt es Information, welche Attribute mit welchen Wertenfur ihn angemessen sind.

I Beispiel:

Jedes zeichen hat ein Attribut kat mit einem Wert vom Typ kategorie.

Angemessenheitsfunktion app (von engl. appropriateness)

app(typ,attribut) = wert-typ

also:

app(zeichen,kat) = kategorie

I Damit ist die Angemessenheitsfunktion fur diese Werte definiert (↓)

also: app(zeichen,kat) = ↓



Angemessenheit von Attributen

I Zunachst soll zeichen keine anderen Attribute haben (spater: kgr)

I d.h. fur andere Attribute ist app bei zeichen undefiniert (↑)

also z.B.: app(zeichen,genus) = ↑

I An der Definiertheit/Undefiniertheit der Angemessenheitsfunktion istablesbar, welche Attribute eine AWM haben kann.



Vererbung

I Erinnerung:

Jedes wort ist ein zeichen, d.h. zeichen v wort

I ⇒ weil kat fur zeichen angemessen, deshalb auch fur wort

I Formaler:

weil zeichen v wort und app(zeichen,kat) =↓, deshalb app(wort,kat) =↓

I Allgemein: Ein Subtyp erbt alle Merkmale seiner Supertypen

I d.h. wenn t v t′ und app(t, A) =↓, dann auch app(t′, A) =↓

I Damit im Beispiel: zeichen, wort, phrase, determinierer, nomen, verb,nominal-phrase, verbal-phrase haben alle ein Merkmal kat



Vererbung

Von welchem Typ ist der Wert von katbei den Subtypen von zeichen?

kategorie

lex-kat

det n v

ph-kat

np vp

I Entweder auch vom Typ kategorie, oder von einem Subtyp von kategorie

I z.B. wort sollte nur Werte vom Typ lex-kat zulassen, und

phrase nur Werte vom Typ ph-kat

I Also: app(wort,kat) = lex-kat und app(phrase,kat) = ph-kat

I Allgemein muss gelten:

wenn t v t′ und app(t, A) = w, dann app(t′, A) = w′ wobei w v w′



Vererbung

I Genauso: Ein nomen sollte nur kat Werte vom Typ n zulassen, eineverbal-phrase nur Werte vom Typ vp, etc.

I Weiter Spezifizierung der vererbten Information:

app(determinierer,kat) = det

app(nomen,kat) = n

app(verb,kat) = v

app(nominal-phrase,kat) = np

app(verbal-phrase,kat) = vp



Vererbung

I Weitere Spezifierung: In Phrasen gibt es Tochter.

Jede Tochter ist vom Typ zeichen.

I Zwei weitere Attribute dtr1 und dtr2 sind fur phrase angemessen:

app(phrase,dtr1) = zeichen

app(phrase,dtr2) = zeichen

I Zusammenfassung:

• Subtypen konnen geerbte Merkmale weiter spezifizieren

• Subtypen konnen neue Merkmale einfuhren



Getypte AWMn

I In Attribut-Wert-Matrizen werden die Typen aussen an die Klammerngeschrieben

zeichen

[kat kategorie

]I Was vorher atomare Werte waren sind jetzt Typen!

I Eine AWM ist wohl-getypt, wenn sie die Angemessenheitsinformationwie folgt respektiert:

Fur jedes Attribut-Wert-Paar 〈A,w〉 in einer AWM vom Typ t muss gelten:

app(t, A) v w

I Im Beispiel oben ist das erfullt, denn

app(zeichen,kat) = kategorie v kategorie



Damit sind auch wohl-getypt:

zeichen

[kat ph-kat

]denn app(zeichen,kat) = kategorie v ph-kat

zeichen

[kat np

]denn app(zeichen,kat) = kategorie v np

wort

[kat v

]denn app(wort,kat) = lex-kat v v

phrase

[kat vpdtr2 zeichen

]denn app(phrase,kat) = ph-kat v vp

app(phrase,dtr2) = zeichen v zeichen

verbal-phrase

kat vpdtr1 verbdtr2 nominal-phrase

app(verbal-phrase,kat) = vp v vpapp(verbal-phrase,dtr1) = zeichen

v verbapp(verbal-phrase,dtr2) = zeichen

v nominal-phrase



Auch wohl-getypt:

verbal-phrase

kat vp

dtr1verb

[kat v

]

dtr2

nominal-phrase

kat np

dtr1determinierer

[kat det

]dtr2

nomen

[kat n

]



Aber nicht:

zeichen

[genus >

]E genus Merkmal nicht angemessen fur zeichen,

app(zeichen,genus) = ↑

wort

[kat np

]E app(wort,kat) = lex-kat 6v np

nomen

[kat np

]E app(nomen,kat) = n 6v np

Zusatzliche Restriktionen der Angemessenheit waren sinnvoll:

verbal-phrase

kat vpdtr1 nomendtr2 nomen



Erweiterung:

I zusatzliche Typen: >

numerus

sg pl

genus

mask fem neut

kasus

nom akk dat

kongruenz

I Fur den Typ kongruenz : app(kongruenz,numerus) = numerusapp(kongruenz,genus) = genusapp(kongruenz,kasus) = kasusapp(kongruenz,kat) =↑app(kongruenz,kgr) =↑

I Fur den Typ zeichen : app(zeichen,kgr) = kongruenzapp(kongruenz,numerus) =↑. . .



I Damit sind auch wohl-getypt:

zeichen

kgr

kongruenz

[numerus numeruskasus dat

]app(kongruenz,numerus) = numerus v numerus

app(kongruenz,kasus) = kasus v dat

app(zeichen,kgr) = kongruenz v kongruenz

phrase

kat vp

kgr

kongruenz

numerus sggenus femkasus dat

phrase erbt Angemessenheitsinfo

uber kgr von zeichen



I Achtung: Wert-Typen fur ein Merkmal heissen manchmal genauso wiedas Merkmal selbst

siehe app(kongruenz,numerus) = numerus

I Es mussen nicht alle angemessenen Merkmale angegeben werden(→ Unterspezifikation)

I Falls doch alle angegeben sind, heisst die AWM vollstandig

I Beispiele:

wort

kat lex-kat

kgr

kongruenz

[numerus sgkasus dat

]ist wohl-getypt, aber nicht vollstandig(genus ist angemessen fur kongruenz aber nicht vorhanden)



I

phrase

kgr

kongruenz

numerus sgkasus datgenus fem

dtr1

zeichen

[kat lex-katkgr kongruenz

]

ist wohl-getypt, aber nicht vollstandig (kat und dtr2 sind auch ange-messen fur phrase)

I

nomen

kat lex-kat

kgr

kongruenz

numerus numerusgenus neutkasus kasus

ist vollstandig wohl-getypt.



Eine AWM in der alle Typen maximal sind heisst typen-aufgelost (engl.type-resolved)

I

wort

kat lex-kat

kgr

kongruenz

numerus numerusgenus neutkasus kasus

ist nicht typen-aufgelost (lex-kat, numerus, kasus sind nicht maximal)

I

nomen

kat n

kgr

kongruenz

numerus plgenus neutkasus dat

ist typen-aufgelost



Zusammenfassung

I Typen klassifizieren Merkmalsstrukturen und damit die modellierten lin-guistischen Objekte

I Typen sind in einer Subsumtionshierarchie angeordnet

I Fur jeden Typ konnen Merkmale angemessen sein

I angemessene Merkmale vererben sich auf Subtypen, konnen aber imWert weiter spezifiziert werden

I AWM sind damit auch getypt und konnen wohl-getypt, vollstandigund typen-aufgelost sein



Getypte Merkmalsstrukturen

I Erinnerung:Merkmalsstruktur ≡ gerichteter azyklischer etikettierter Graph

I Kantenetikette ≡ Attribute

I Alle getypten Merkmalsstrukturen sind

• wohl-getypt

• vollstandig

• typen-aufgelost

I Neu: Die Knoten sind mit den Typen etikettiert



Beispiel:

nomen n

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

I Knotenetikette ≡ Typen

I Kantenetikette ≡ Attribute

I Wohlgetyptheit ≡ nur Kanten fur angemessene Attribute

I Vollstandigkeit ≡ Kanten fur alle angemessenen Attribute vorhanden

I Typaufgelostheit ≡ alle Typen maximal



AWM → Merkmalsstruktur

getypte Attribut-Wert-Matrizen

↓ beschreiben

getypte Merkmalsstrukturen

↓ modellieren


nomen

2666664

kat n

kgr

kongruenz

264


375

3777775

↓ beschreibt

nomen n

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

↓ modelliert

Frauen

I Eine wohlgetypte, vollstandige,typenaufgeloste AWM beschreibtgenau eine Merkmalsstruktur



Eine unvollstandige oder nicht-typenaufgeloste AWM beschreibtmehrere MSen (→ Unterspezifikation)

wort

kat lex-kat

kgr

kongruenz

[genus femkasus nom

]↙ beschreibt unter anderem

determ

inierer

det

kong

ruen

zkat

kgr

sg

fem

nom

numerus

genus

kasus



wort

26664

kat lex-kat

kgr

kongruenz

"genus femkasus nom

#37775

↓ beschreibt

determ

iniere

r

det

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

nom

en n

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

verb

v

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

determ

iniere

r

det

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

nom

en nko

ngru

enz

kat

kgr

pl

fem

nom

numerus

genus

kasus

verb

v

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus



Subsumtion getypter AWMen

I Erinnerung:Die Typhierarchie muss die Eigenschaften einer Subsumtionsrelation(≡ Ordnungsrelation) aufweisen.

Typ t ist Supertyp von t′ gdw. t v t′

I Damit wird die Subsumtion von getypten AWMn definiert.

Eine AWM A vom Typ t subsumiert eine AWM A′ vom Typ t′ genaudann, wenn:

• t v t′ und

• jedes Attribut in A ist auch in A′ vorhanden und der Wert in A subsu-miert den Wert in A

• Koreferente Attribute/Pfade in A sind auch koreferent in A′.



Beispiele:

zeichen

[kat ph-kat

]phrase

[kat np

]v

zeichen v phraseph-kat v np

wortverbal-phrase

[kat vp

]6v wort 6v verbal-phrase

phrase

[kat vp

]verbal-phrase

kat vp

kgrkongruenz

[numerus numerus

]v

phrase

kat ph-kat

kgr

kongruenz

[numerus numerusgenus fem

]verbal-phrase

kat vp

kgr

kongruenz

[numerus sggenus genus

]6v

fem 6v genus



Weitere Beispiele:

verbal-phrase

kat vp

dtr1

zeichen

[kat vkgr 1 kongruenz

]dtr2

nominal-phrase

[kgr 1

]

verbal-phrase

kat vp

dtr1

verb

kat v

kgr 1kongruenz

[numerus sg

]dtr2

nominal-phrase

[kgr 1

]

v



Weitere Beispiele:

verbal-phrase

kat vp

dtr1

zeichen

[kat vkgr kongruenz

]

dtr2nominal-phrase

[kgr

kongruenz

[numerus pl

]]

verbal-phrase

kat vp

dtr1

verb

kat v

kgr 1kongruenz

[numerus sg

]dtr2

nominal-phrase

[kgr 1

]

6v

(weil pl 6v sg)



Subsumtion ↔ MS-Teilmengenbeziehung A v B ⇔ MS(B) ⊆MS(A)

wort

26664

kat lex-kat

kgr

kongruenz

"genus femkasus nom

#37775 v

nomen

2666664

kat n

kgr

kongruenz

264


375

3777775

⇔

{ }⊆

{ }nomen n

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

determ

iniere

r

det

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

nom

en n

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

verb

v

kong

ruen

z

kat

kgr

sg

fem

nom

numerus

genus

kasus

determ

iniere

r

det

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

nom

en n

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus

verb

v

kong

ruen

z

kat

kgr

pl

fem

nom

numerus

genus

kasus



Unifikation getypter AWMen

I Genauso wie bei ungetypten AWMen!

I A tB = die allgemeinste AWM C, die A v C und B v C

I Dafur muss aber die Unifikation von Typen t t t′ definiert sein . . .

I Preisfrage:

Welche Bedingung muss die Typhierarchie dann erfullen ????I Fur je zwei Typen t und t′ muss das Infimum existieren, bzw.

I die Typhierarchie muss ein (Halb-)Verband sein



Noch kein Verband:

>

zeichen

wort


phrase


kategorie

lex-kat

det n v

ph-kat

np vp

⊥

I Der alte Trick: ⊥ steht fur fehlschlagende Unifikation



Beispiele:

zeichen t wort = wort

lex-kat t nomen = ⊥

zeichen

[kat n

]t

wort

[kat lex-kat

]=

wort

[kat n

]

phrase

[dtr1 zeichen

]t

zeichen

[kat kategorie

]=phrase

[kat ph-katdtr1 zeichen

]

zeichen

kgr

kongruenz

[numerus plgenus genus

]dtr1 nomen

t

verbal-phrase

kgr

kongruenz

[numerus numerusgenus fem

]dtr1

zeichen

[kat v

] = ⊥



Typhierarchie (diesmal fur nicht-linguistische Objekte); ⊥ nicht gezeigt

>

fahrzeug schiff zahl

einrad zweirad dreirad mehr-rad motorboot segelboot 1 . . . 1000

fahrrad motorrad pkw lkw

auto-normal cabrio kombi van



Angemessenheitsfunktion:

I Ein fahrzeug hat eine gewisse Anzahl Rader

app(fahrzeug,rader) = zahl

I Spezialisierung: Ein einrad hat ein Rad

app(einrad,rader) = 1(Erinnerung: t v t′ und app(t, A) = ↓, dann app(t, A) v app(t′, A)

)I Spezialisierung: Ein zweirad hat zwei Rader

app(zweirad,rader) = 2

I Spezialisierung: Ein dreirad hat drei Rader

app(dreirad,rader) = 3



Angemessenheitsfunktion:

I Spezialisierung: nicht fur mehr-rad, aber: ein pkw hat vier Rader

app(pkw,rader) = 4

I Einfuhrung neuer Attribute: Ein mehr-rad hat Turen

app(mehr-rad,turen) = zahl

I Spezialisierung: Ein cabrio hat 2 Turen

app(cabrio,turen) = 2

I Spezialisierung: Ein kombi hat 4 Turen

app(kombi,turen) = 4

I Sonst fur alle Typen t und Attribute A:

app(t, A) = ↑



AWMn uber dieser Typhierarchie

Imotorad

[rader 2

]wohl-getypt, vollstandig, typen-aufgelost

Imotorboot

[rader zahl

]nicht wohl-getypt ( app(motorboot,rader) =↑ )

I

fahrzeug

[rader 4turen 2

]nicht wohl-getypt ( app(fahrzeug,turen) =↑ )

Imehr-rad

[rader 6

] wohl-getypt, nicht vollstandig (turen),nicht typen-aufgelost (mehr-rad)

Ikombi

[turen 4

] wohl-getypt, nicht vollstandig (rader),typen-aufgelost

I

auto-normal

[rader 4turen zahl

]wohl-getypt, vollstandig,

nicht typen-aufgelost (zahl)



Erweiterung der Typhierarchie

>

fahrzeug motorantrieb schiff motor zahl






Erweiterung der Angemessenheitsfunktion:

I Ein Ding vom Typ motorantrieb hat einen Motor (vom Typ motor)

app(motorantrieb,motor) = motor

I Ein motor hat eine gewisse Anzahl Zylinder und PS

app(motor, zylinder) = zahl

app(motor,ps) = zahl

I wohl-getypte und vollstandige AWM z.B.

motorantrieb

motor

motor

[zylinder 4ps 150

]



I motorboot hat zwei (unmittelbare) Supertypen: schiff und motorantrieb

I mehr-rad hat zwei (unmittelbare) Supertypen: fahrzeug und motorantrieb

I Eine Typenhierarchie in der manche Typen mehrere (unmittelbare) Su-pertypen haben heisst multi-dimensional

I Vorsicht! Infimum zweier Typen muss weiterhin existieren fur Unifikation

I Beispiel:

fahrzeug t motorantrieb = mehr-rad

fahrzeug motorantrieb

mehr-rad



Beispiel einer unerlaubten Typhierarchie:

>





fahrzeug t motorantrieb = ?



Abhilfe: Einfuhrung von Hilfstypen:

>


einrad zweirad dreirad motor-fahrzeug

mehr-rad

motorboot segelboot 1 . . . 1000



fahrzeug t motorantrieb =motor-fahrzeug



I Erinnerung:Typen erben die Angemessenheitsinformation ihrer Supertypen

I In multi-dimensionalen Typhierarchien kann ein Typ mehrere Superty-pen haben, d.h. er erbt von mehreren Supertypen/Dimensionen

I Das nennt man Mehrfachvererbung (multiple inheritance)

I Beispiel:Ein motor-fahrzeug erbt von fahrzeug und von motorantrieb:

von fahrzeug app(fahrzeug,rader) = zahl

von motorantrieb app(motorantrieb,motor) = motor

I Damit ist z.B.

motor-fahrzeug

rader 4

motor

motor

[zylinder 4ps 120

] wohlgetypt und vollstandig



Beispiele (Wohlgetyptheit, Vollstandigkeit, Typen-aufgelostheit):

I

mehr-rad

rader zahl

motor

motor

[zylinder 9877ps zahl

] +W -V -T

I

motorrad

rader zahl

motor

motor

[zylinder 9877ps zahl

] -W app(zweirad,rader) = 2

I

kombi

rader 4turen 4

motor

motor

[zylinder 24ps 170

] +W +V +T



Beispiele (Subsumtion):

I

motorantrieb

motor

motor

[zylinder 8ps zahl

]pkw

rader 4

motor

motor

[zylinder 16ps 200

]6v

I motorantriebzweirad

[rader 2

]6v

Imotor-fahrzeug

[motor

motor

[ps zahl

]]motorboot

motor

motor

[zylinder 16ps 250

]6v

Ifahrzeug

[rader 2

]pkw

rader 4

motor

motor

[zylinder 16ps 250

]6v



Beispiele (Unifikation):

I motorantrieb tzweirad

[rader 2

]=

motorrad

[rader 2

]

Imotorantrieb

[motor

motor

[ps 340

]]t

lkw

turen 2

motormotor

[ps 355

] = ⊥

Ifahrzeug

[rader 8

]t

motorantrieb

motor

motor

[zylinder 8ps zahl

]

=

motor-fahrzeug

rader 8

motor

motor

[zylinder 8ps zahl

]



Erweiterungen: Disjunktion

I Disjunktion: wie bei ungetypten AWMn (unter Beachtung der Typen)

I Beispiel:

lkw

rader 6 ∨ 8

motormotor

[zylinder 12 ∨ 16

]steht fur

lkw

rader 6

motormotor

[zylinder 12

]lkw

rader 6

motormotor

[zylinder 16

]

lkw

rader 8

motormotor

[zylinder 12

]lkw

rader 8

motormotor

[zylinder 16

]



Erweiterungen: Negation

I Mit Typen auch moglich: Negation ¬

I Auch wieder nur abkurzend fur mehrere AWMn

I z.B. Determinierer dem ist singular, im Dativ und nicht feminin

und durch folgende AWM beschrieben (mit der zeichen-Typhierarchie):

determinierer

kat det

kgr

kongruenz

numerus sggenus ¬ femkasus dat



Erweiterungen: Negation

I Weil app(kongruenz,genus) = genus . . .

I . . . und genus die Subtypen mask, fem, neut hat. . .

I . . . steht diese AWM fur

determinierer

kat det

kgr

kongruenz




Erweiterungen: Listen

I Listen mittels Typen:

Eine Liste ist leer (elist) oder nicht-leer (nelist)elist nelist

list

I Ist die Liste nicht-leer, dann besteht sie aus einem ersten Element(first) und einer Restliste (rest)

app(nelist, first) = >

app(nelist,rest) = list

I Anstelle von > kann auch ein anderer Typ stehen,

z.B. Liste von Zahlen ; zahl, Liste von Fahrzeugen ; fahrzeug, etc.



Beispiel: (mit Typenhierarchie von vorher)⟨motorboot, 4,>,

pkw

rader zahl

motormotor

[ps 45

], schiff

⟩

nelist

first motorboot

rest

nelist

first 4

rest

nelist

first >

rest

nelist

first

pkw

rader zahl

motormotor

[ps 45

]rest

nelist

[first schiffrest elist

]



Beispiel: Liste von Zahlen (d.h. app(nelist, first) = zahl )⟨892, 3, zahl, 347, zahl, 1

⟩

nelist

first 892

rest

nelist

first 3

rest

nelist

first zahl

rest

nelist

first 347

rest

nelist

first zahl

rest

nelist

[first 1rest elist

]



Prinzipien & Type-Constraints

I Prinzipien/Typ-Constraints stellen zusatzliche Anforderungen an zuge-lassene AWMen

I Sie sind von der Form A ⇒ B

I Bedeutung: Jede AWM, die von A subsumiert wird, muss auch von Bsubsumiert werden.

I Damit lassen sich zusatzliche Generalisierungen ausdrucken.

Beispiel: In einer NP kongruieren die beiden Tochter und vererben dieKongruenzmerkmale an die NP

nominal-phrase ⇒

kgr 1

dtr1[kgr 1

]dtr2

[kgr 1

]



I Wie oben werden oft die Typen weggelassen, wenn sie klar sind.

I Damit ist z.B. folgende AVM (z.B. fur dem Hund) zugelassen:

nominal-phrase

kat npkgr 1

dtr1

determinierer

[kat detkgr 1

]

dtr2

nomen

kat n

kgr 1

kongruenz




I Erinnerung: Komplementanforderung via subcat-Liste

I Beispiel: Intransitives Verb schlaft

verb

subcat

⟨nominal-phrase

kgr

kongruenz


]⟩

I Subkategorisierungsprinzip: subcat-Liste wird abgebaut

verbal-phrase ⇒

subcat 1

⟨2

⟩dtr1

[subcat 1

]dtr2 2



I Damit u.a. zugelassen:

verbal-phrase

subcat 〈〉

dtr1verb

[subcat

⟨2

⟩]

dtr2 2

nominal-phrase

kgr

kongruenz


]

I Prinzipien/Typ-Constraints sind zentraler Bestandteil von unifikationsba-

sierten Grammatiken

I Keine Regeln mehr, sondern nur noch zugelassene linguistische Zei-chen → sign-based Grammar


Wiederholung Relationen

Relationen

Eine Relation R uber einer Menge D ist eine Menge von geordnetenPaaren von Elementen aus D. R ist . . .

I reflexiv: fur alle x ∈ D: 〈x, x〉 ∈ R

irreflexiv: fur kein x ∈ D: 〈x, x〉 ∈ R

I symmetrisch: 〈x, y〉 ∈ R, dann auch 〈y, x〉 ∈ R

asymmetrisch: 〈x, y〉 ∈ R, dann nicht 〈y, x〉 ∈ R

antisymmetrisch: 〈x, y〉 ∈ R und 〈y, x〉 ∈ R, dann x = y

I transitiv: 〈x, y〉 ∈ R und 〈y, z〉 ∈ R, dann auch 〈x, z〉 ∈ R

(sonst einfach nicht transitiv)



I total/konnex/linear: fur x, y ∈ D gilt 〈x, y〉 ∈ R oder 〈y, x〉 ∈ R

(sonst partiell)

I Relation reflexiv, antisymmetrisch und transitiv: (schwache) Ordnung

(Merke: ’kleiner-gleich’ ≤ bei Zahlen)

I Relation irreflexiv, asymmetrisch und transitiv: strikte Ordnung

(Merke: ’echt-kleiner’ < bei Zahlen)

I bei beiden noch zusatzlich: partiell vs. total)

I Relation reflexiv, symmetrisch und transitiv: Aquivalenzrelation

(Merke: ’gleich’ = bei Zahlen)



Beispiele:

I Relation: 〈x, y〉 ∈ R gdw. x ’sitzt-in-einer-Reihe-vor’ y.

irreflexiv, asymmetrisch, transitiv, partiell

R ist partielle strikte Ordnung

Wie mussten Sie sitzen, damit die Relation total wird?

In einer Reihe hintereinander!



Beispiele:

I Relation: 〈x, y〉 ∈ R gdw. x ’schreibt-in-der-Klausur-ab-von’ y.

irreflexiv, asymmetrisch, nicht-transitiv, partiell

R ist keine spezielle Relation

Wie mussten Sie voneinander abschreiben, damit die Relation einestrikte Ordnung wird?

Transitivitat:Wenn A von B abschreibt und B von C abschreibt,

dann muss A auch von C abschreiben.



Beispiele:

I Relation: 〈x, y〉 ∈ R gdw. x ’hat-die-gleiche-Klausernote-wie’ y.

reflexiv, symmetrisch, transitiv

R ist eine Aquivalenzrelation

Welche Eigenschaften anderen sich, wenn man stattdessen die Rela-tion R′

x ’hat-die-gleiche-oder-eine-bessere-Klausernote-wie’ y

betrachtet?

symmetrisch ; antisymmetrisch

R′ ist damit eine (schwache) Ordnung



Verbande

Verband als Ordnung (ausgehend von Ordnung R)

I Supremum sup(x, y) zweier Elemente: kleinste obere Schranke

〈x, c〉, 〈y, c〉 ∈ R und fur alle d mit 〈x, d〉, 〈y, d〉 ∈ R⇒ 〈c, d〉 ∈ R

I Infimum inf(x, y) zweier Elemente: großte untere Schranke

〈c, x〉, 〈c, y〉 ∈ R und fur alle d mit 〈d, x〉, 〈d, y〉 ∈ R⇒ 〈d, c〉 ∈ R

I Eine Ordnung R ist ein Verband, wenn Supremum und Infimum fur be-liebige zwei Elemente x, y immer existieren.



Verbande

Verband als algebraische Struktur

Verband 〈D,∨,∧〉 ist Menge D mit zwei Operationen join ∨ und meet ∧:

1 (a) x ∨ y = y ∨ x(b) x ∧ y = y ∧ x Kommutativgesetze

2 (a) x ∨ (y ∨ z) = (x ∨ y) ∨ z(b) x ∧ (y ∧ z) = (x ∧ y) ∧ z Assoziativgesetze

3 (a) x ∨ x = x(b) x ∧ x = x Idempotenzgesetze

4 (a) x ∨ (x ∧ y) = x(b) x ∧ (x ∨ y) = x Absorptionsgesetze



Beispiele:

I Grundmenge: {a, b, c, d, e}

Relation:R ={〈a, a〉, 〈c, c〉, 〈d, d〉, 〈e, e〉, 〈a, b〉, 〈a, c〉, 〈c, d〉, 〈a, e〉, 〈b, e〉, 〈d, e〉

}weder reflexiv noch irreflexiv, antisymmetrisch, nicht transitiv

R ist keine spezielle Relation

Welche Paare muss man dazufugen, damit aus R eine Ordnung wird?

Reflexivitat: 〈b, b〉Transitivitat: 〈a, d〉, 〈c, e〉

Ist R ein Verband?

Ja, denn fur zwei Elemente gibt es immer das Supremum und Infimumz.B. sup(b, c) = e inf(b, c) = a.


Wiederholung Logische Formalisierung

Logische Formalisierung nach Johnson

I Beschreibung der Merkmalsstrukturen (d.h. der gerichteten azykli-schen Graphen) mittels logischen Formeln.

I Objekte der Domane: Knoten dieser Graphen

I Konstantensymbole ; Knoten fur atomare Werte

Variablen ; Knoten von komplexen Werten/MS

Pradikatensymbole ; Kanten



Beispiel: name Peter Schmidt

adresse

strasse Baumweg 2plz 12345ort Merkmalshausen

Peter Schmidtname

adresse

Baumweg 2

12345

Merkmalshausen

strasse

plz

ort

∃x∃y�

name(x, peter schmidt) ∧ adresse(x, y)

∧ strasse(y, baumweg 2) ∧ plz(y, 12345)

∧ ort(y, merkmalshausen)�



I Einschrankung der moglichen Modelle mittels folgender Axiome:

I (AX1) Atomare Werte haben keine Attribute/ausgehenden Kanten:

z.B. ∀x(¬adresse(merkmalshausen, x))

I (AX2) Werte sind eindeutig/Kantenrelationen sind Funktionen

z.B. ∀x∀y∀z((adresse(x, y) ∧ adresse(x, z)) → y = z)

I (AX3) atomare Werte sind unterschiedlich/keine Namensgleichheit

z.B. ¬(12345 = merkmalshausen)

I Unifikation zweier Beschreibungen ∃x(ϕ)

und ∃x′(ϕ′):

neue Beschreibung ∃x∃x′(ϕ ∧ ϕ′

)∧ x = x′

mittels Axiomen vereinfachen.



I d


Documents

Formale Methoden III - Arbeitsbereichecebert/teaching/05fm3/folien.pdf · I Die Attribut-Wert-Matrix besteht aus den Attribut-Wert-Paaren... hnumerus,pli hgenus,femi hkasus,nomi I