Grundlagen der Merkmallogik, PATR

Dozent: Gerold Schneider

Übersicht

Mit Merkmallogik fasse ich die Arbeiten zu Merkmalstrukturen und den darauf anwendbaren Operationen zusammen. Die Themenordnung der Vorlesung sowie die Beispiele sind grösstenteils entnommen aus [Keller 93].


Unifikationsbasierte Grammatiktheorien

Grammatiktheorien wie LFG, GPSG oder HPSG werden oft zusammenfassend als unifikationsbasiert oder auch constraint-basiert bezeichnet (constraint = Bedingung, Einschränkung). Das heisst, dass innerhalb dieser Theorien linguistische Informationen (u.a.) mit Hilfe von Merkmalstrukturen repräsentiert werden. Die zentrale Operation über Merkmalstrukturen ist die Unifikation. Merkmalstrukturen können aber auch als Bedingungen bei der Regelanwendung gesehen werden, weshalb man von Constraint (dt. Bedingungs)-basierten Theorien spricht.

NP[kas=K] --> Det[kas=K]  N[kas=K]
NP --> Det N
  <NP Kasus>  = <N Kasus>
  <Det Kasus> = <N Kasus>

Diese Regel besagt, dass eine NP aus einem Determiner und einem Nomen besteht und dass diese Regel nur dann angewendet werden darf, wenn der Kasus der Gesamtphrase gleich dem Kasus des Determiners gleich dem Kasus des Nomens ist.

PATR Notation

Die erste Variante dieser Regel verwendet Prolog-Unifikation. Die Beschränkung (Constraint) in Form der Verwendung derselben Variable (K) stellt sicher, dass der Wert des Merkmals kas dasselbe ist für Det, N und die ganze Phrase.

Die zweite Variante verwendet die PATR Notation. In ihr werden die Merkmale, die denselben Wert haben müssen, explizit aufgelistet. Dem Linguisten ermöglicht das, ganz intuitiv die Kongruenz (Agreement) auszudrücken.

PATR ist keine Grammatiktheorie, sondern ein Notationsstandard, der die Formulierung komplexer Grammatiken erlaubt [Shieber 86]. Eine Reihe von Grammatikentwicklungssystemen unterstützen den PATR Formalismus, so z.B.:

Eigenschaften unifikationsbasierter Grammatiken

Solcherart unifikationsbasierte Grammatiktheorien zeichnen sich durch eine Reihe von Charakteristiken aus:

  1. Deklarativität: Die linguistische Information wird als deklaratives Wissen formuliert, d.h. ohne Berücksichtigung von Verarbeitungsaspekten.
  2. Orientierung an Oberflächenstruktur: Die linguistische Information bezieht sich auf eine Darstellungsebene. Die Unterscheidung zwischen Tiefenstruktur und Oberflächenstruktur wird aufgegeben.
  3. Constraint-Sprachen: Zur Verarbeitung der linguistischen Informationen dienen wohldefinierte, logik-basierte Constraint-Sprachen.

Trotz dieser Gemeinsamkeiten darf nicht übersehen werden, dass in unterschiedlichen Grammatiktheorien ganz unterschiedliche linguistische Informationen durch Merkmalstrukturen repräsentiert werden. So werden z.B. in GPSG syntaktische Kategorien, in LFG jedoch nur funktionale Beziehungen codiert.

Merkmalstrukturen als Mengen

Eine Merkmalstruktur kann gesehen werden als eine Menge von Merkmal-Wert Paaren, wobei jedes Merkmal ein eindeutiges Symbol ist und jeder Wert entweder ein Symbol, ein Verweis oder selbst wieder eine Merkmalstruktur. Eine leere Merkmalstruktur kann als Variable interpretiert werden. Merkmalstrukturen werden häufig in Form einer Matrix dargestellt:

(1)
-                    -
| cat NP             |
| agr [num singular] |
-                    -

Merkmalsstrukturen im Vergleich zu Prolog-Argumenten

In Prolog werden Werte der gleichen Argumentsposition verglichen.

vp('geht',sing,pers3,np)

Dieses Prädikat kann beispielweise bedeuten, dass die VP den Kopf 'geht' hat, im Singular 3. Person steht und für einen Subjekts-NP subkategorisiert. In etwas komplexeren Grammatiken wird das aber schnell unübersichtlich. Was steht genau an welcher Argumentsposition? Merkmalssrukturen identifizieren Werte über Merkmale statt über Argumentspositionen.

Merkmalstrukturen als Graphen

Aus mathematischer Sicht können Merkmalstrukturen als gerichtete, azyklische Graphen (engl. directed acyclic graph; DAG) gesehen werden. Die Merkmale werden dabei als Bezeichnungen für die Kanten interpretiert und die Wertsymbole sind die Knoten am Ende des Graphen. Der folgende Graph ist also gleichbedeutend mit (1).

einfacher Graph

In unifikationsbasierten Grammatiktheorien werden Merkmalstrukturen als partielle (d.h. möglicherweise unvollständige) Beschreibungen linguistischer Objekte angesehen. D.h. es ist prinzipiell immer möglich, eine Merkmalstruktur mit Merkmal-Wert Paaren zu erweitern.

Dementsprechend kann man Merkmalstrukturen bzgl. ihrer Informationsmenge ordnen und zwar mit Hilfe der Subsumptionsrelation:

Eine Merkmalstruktur X subsumiert eine Merkmalstruktur Y genau dann, wenn Y alle Merkmal-Wert Paare von X enthält (und vielleicht noch andere). Eine Variable subsumiert alle anderen Merkmalstrukturen.

Daraus folgt, dass nicht alle Merkmalstrukturen durch die Subsumptionsrelation geordnet werden können. (Man spricht deshalb von partieller Ordnung.) Die Merkmalstruktur in (2) steht nicht in einer Subsumptionsrelation zur Merkmalstruktur in (1).

(2)
-                    -
| cat NP             |
| agr [person  3   ] |
-                    -

Die Information von Merkmalstruktur (2) ist jedoch verträglich mit (1). Intuitiv kann man die Merkmalstrukturen (1) und (2) als unterschiedliche Beschreibungen des selben linguistischen Objekts ansehen. In diesem Fall können die Merkmalstrukturen unifiziert werden. Unifikation entspricht intuitiv einer Verträglichkeitsprüfung zwischen zwei Merkmalstrukturen und führt im positiven Fall zu einer Vereinigung der Merkmal-Wert Paare in einer neuen Merkmalstruktur. So ergibt die Unifikation von (1) und (2) die Merkmalstruktur in (3).

(3)
-                    -
| cat NP             |
| agr [num singular] |
|     [person  3   ] |
-                    -

Die bei der Unifikation von X und Y entstehende Merkmalstruktur ist die allgemeinste Merkmalstruktur, die sowohl von X als auch von Y subsumiert wird. Zwei Merkmalstrukturen können nicht unifiziert werden, wenn sie widersprüchliche Informationen enthalten.

(4)
-                    -
| cat NP             |
| agr [person  1   ] |
-                    -

Merkmalstruktur (4) kann nicht mit (2) unifiziert werden, da sie widersprüchliche Informationen für das Merkmal person enthalten.

Eine weitere Eigenschaft von Merkmalstrukturen ist die Möglichkeit, dass zwei Merkmale sich einen Wert teilen. (In (5) angedeutet durch die Ziffer '1' in spitzen Klammern.)

(5)
-                        -
| cat S                  |
| agr <1> [person  3   ] |
| subject [ agr <1> ]    |
-                        -

In (5) haben agr und subject:agr den selben Wert. Man spricht dabei von Koreferenz oder Koindizierung oder im Englischen auch von structure-sharing. (5) kann auch graphisch dargestellt werden:

Graph mit Koreferenz

Beachte: (5) ist nicht identisch mit (6).

(6)
-                            -
| cat S                      |
| agr     [person  3   ]     |
| subject [ agr [person 3 ]] |
-                            -

Zur Verdeutlichung mache man sich klar, was das Ergebnis einer Unifikation von einerseits (5) mit (7) und andererseits (6) mit (7) ergeben würde.

(7)
-                        -
| agr   [num singular  ] |
-                        -

Desweiteren mache man sich bewusst, dass eine zirkuläre Koreferenzierung, wie in (8) angedeutet, nicht erlaubt ist.

(8)
-                            -
| agr <1>  [head [agr <1> ]] |
-                            -

Eigenschaften der Unifikation

Die Unifikationsoperation lässt sich intuitiv als Schnittmengenoperation der Mengenlehre betrachten. Sei & das Zeichen für die Unifikation und << das Zeichen für die Subsumption und seien M1, M2 und M3 Merkmalstrukturen, so gelten die folgenden Gesetze:

Idempotenzgesetz (identische Mengen)
M1 & M1 = M1
Kommutativgesetz (Überlappung der Schnittmengen)
M1 & M2 = M2 & M1
Assoziativgesetz
M1 & (M2 & M3) = (M1 & M2) & M3

Mengenlehrenmässige Interpretation des Assoziativgesetzes

Subsumptionsgesetz (M1 ist Teilmenge von M2)
(M1 << M2) gdw. (M1 & M2 = M2)

(in der Bedeutung M1 subsumiert M2)

Desweiteren gilt noch die Monotonie-Eigenschaft, die besagt, dass bei einer Unifikation entweder die Information gleich bleibt oder Information hinzugefügt wird. Es kann niemals Information abgezogen werden. Information kann durch Unifikation nur spezifischer, eingeschränkter werden, oder im Extremfall (wenn zwei gleiche Strukturen unifiziert werden) gleich bleiben.

Merkmalstrukturen als Funktionen

Merkmalstrukturen können gesehen werden als partielle Funktionen von Merkmalen zu Werten. Sei F eine Menge von Merkmalen, V die Menge atomarer Merkmalwerte und D die Menge aller Merkmal-Wert Paare, dann handelt es sich bei einer Merkmalstruktur um eine Teilmenge von F × (V U D).

_         _
| f1   v1 |
| ...     |   = MS1
| fn   vn |
-         -
MS1 = {(f1,v1), ..., (fn,vn)}

Negation und Disjunktion innerhalb von Merkmalstrukturen

Bisher haben wir nur Merkmalstrukturen betrachtet, deren Bedingungen konjunktiv verknüpft sind. Jedoch gibt es viele Fälle, bei denen eine adequate und konzise Beschreibung die Verwendung von Negation und Disjunktion innerhalb von Merkmalstrukturen erfordert.

(9)
-                      -
| form 'loves'         |
| cat verb             |
| agr [num  singular ] |
|     [person 3      ] |
-                      -

Wenn wir z.B. Lexikoneinträge für englische Verben mit Merkmalstrukturen versehen wollen, so müssen wir einen Eintrag für die Form der 3. Pers. Sg. und drei weitere Einträge für die gleichlautenden Formen der 1.u.2. Pers. Sg. sowie der Pluralformen vornehmen. Besser wäre es, diese gleichlautenden Formen in einem Eintrag zu erfassen und mit der Information: 'nicht 3. Pers. Sg.' zu versehen.

(10)
-                          -
| form 'love'              |
| cat verb                 |
| agr NOT [num  singular ] |
|         [person 3      ] |
-                          -

Die Verwendung der Disjunktion lässt sich z.B. mit Angaben zum Artikel die motivieren. Er kann (u.a.) Femininum Singular und Plural im Nominativ und Akkusativ sein. Das entspräche z.B. folgender Merkmalstruktur mit Disjunktion:

(11)
-                      -
| form   'die'         |
| cat    artikel       |
| genus  femin         |
| kasus  (nom OR akk)  |
-                      -

Die Unifikation von Merkmalstrukturen mit disjunktiven Werten wird dann folgendermassen definiert. Sei X eine Merkmalstruktur mit disjunktiver Information in den Varianten X1 und X2.

  1. Ist eine Merkmalstruktur Y (ohne Disjunktion) sowohl mit X1 als auch X2 kompatibel, so wird die Unifikation unter Beibehaltung der Disjunktion ausgeführt.
  2. Ist Y mit einer Variante nicht kompatibel, so wird diese Variante bei der Unifikation eliminiert.
  3. Ist Y weder mit X1 noch mit X2 kompatibel, so scheitert die Unifikation.
[kasus (nom OR akk)] & [genus femin] ==> | kasus (nom OR akk) |
                                         | genus femin        |

[kasus (nom OR akk)] & [kasus nom]   ==> [ kasus nom ]

[kasus (nom OR akk)] & [kasus dat]   ==> fail

Es ist jedoch auch möglich, Merkmalstrukturen mit disjunktiven Merkmal-Wert Paaren zu haben.

(12)
-                                        -
| form   'der'                           |
| cat    artikel                         |
| num    singular                        |
| ([genus  femin] [kasus  [gen OR dat]]) |
|  OR ( [genus mask] [kasus  nom]  )     |
-                                        -

Die Anwedung der Unifikation auf Merkmalstrukturen mit Disjunktion ist wohl-definiert. Sie kann jedoch in der Praxis zu sehr komplexen disjunktiven Merkmalstrukturen und damit verbunden zu sehr aufwendigen Unifikationsschritten führen. Als anschauliche Übungsaufgabe überlege man sich das Ergebnis der folgenden Unifikation. Lösung

_            _     _              _
| f a        |     | f (a OR b)   |
| g (a OR b) |  &  | g a (c OR d) |
| h (c OR d) |     | j (a OR c)   |
-            -     -              -

Probleme treten bei der Interpretation der Negation auf. Eine Negation wie in (10) muss zunächst auf eine Disjunktion zurückgeführt werden:

agr NOT [person 3] OR agr NOT [num singular].

Bei der Unifikation tritt das zusätzliche Problem auf, dass die Abwesenheit eines Merkmals nicht die Negation des Merkmals erlaubt, da es sich bei Merkmalstrukturen um partielle Information handelt. D.h. die positive Information liegt möglicherweise zum Zeitpunkt der Unifikation noch nicht vor. Zur Behebung dieses Problems gibt es zwei Ansätze:

  1. Negation nach Misserfolg (engl. negation by failure) entspricht der Negation in der Programmiersprache Prolog. Die Negation einer Formel F gilt genau dann, wenn nicht abgeleitet werden kann, dass F gilt. Dies erfordert zumindest, dass die Unifikation mit Negationen so spät wie möglich ausgeführt werden muss.
  2. Konstruktive Negation Die Negation einer Formel F gilt nur dann, wenn es einen Gegenbeweis zu F gibt. Dabei kann der Fall auftreten, dass über den Wahrheitswert von F nicht entschieden werden kann. Um diesen Fall behandeln zu können, wird die zweiwertige Logik um einen Wert für 'undefiniert' erweitert. Die logischen Verknüpfungen sind dann neu zu definieren.

Beachte: Ist der Wertebereich eines Merkmals endlich, so sind Repräsentationen mit Disjunktionen und solche mit Negationen ineinander überführbar. Beispielsweise repräsentiert (13) den gleichen Sachverhalt wie (10). Die aufwendige Behandlung der Negation kann man sich somit ersparen.

(13)
-                                        -
| form 'love'                            |
| cat verb                               |
| agr ([num  singular ] [person 1 OR 2]) |
|      OR   [num plural]                 |
-                                        -

Implikation zwischen Merkmalstrukturen

Implikation ist nützlich, um die Beziehung zwischen verschiedenen Merkmalstrukturen auszudrücken. Ein Beispiel aus GPSG:

(14)
[inv +] ==> [aux +]
            [fin +]

Diese Implikation ist zu lesen als: Wenn eine Merkmalstruktur das Merkmal-Wert Paar [inv +] enthält, so muss sie auch die Merkmal-Wert Paare [aux +, fin +] enthalten. Die Implikation in (14) beschreibt eine Abhängigkeit des Englischen, wonach ein Satz nur dann invertiert werden kann, wenn er ein finites Hilfsverb enthält.

Wie in der Logik, so kann auch die Implikation von Merkmalstrukturen auf Negation und Disjunktion zurückgeführt werden.

(M1 ==> M2) gdw. (NOT M1 OR M2)

[Strömbäck 92] vermerkt dazu: "It is, however, common for systems that use implication to use implication as one of the basic operators and instead define negation in terms of implication. Negation can then be defined as: NOT A = (A ==> fail)."

Andere Erweiterungen

Einige der jüngeren Grammatiktheorien (allen voran HPSG) arbeiten mit Mengen und Listen als Werten in Merkmalstrukturen. Diese verkomplizieren die Unifikation von Merkmalstrukturen erheblich. Hier gebe ich nur je ein Beispiel und gehe nicht weiter auf diesen Bereich ein. (15) zeigt einen Satz, bei dem zwei Konstituenten bewegt wurden. Da diese Konstituenten nicht in der Reihenfolge auftreten wie die entsprechenden offenen Stellen, werden sie in einer Menge repräsentiert.

(15)
[[This bus]1, I don't think [Palo Alto]2 is very easy to get to _2 on _1.

[syntax [slash {[cat NP], [cat NP]} ]]

(16) ist ein Beispiel für eine Subkat-Liste in HPSG, die die Komplemente des Verbes in einer festgelegten Reihenfolge vorgibt (Subjekt vor Objekt).

(16)
_                                    _
| form 'wait'                        |
| cat verb                           |
| subcat <[cat NP], [cat PP]>        |
-                                    -

Typisierte Merkmalstrukturen

Bei der Benutzung von Merkmalstrukturen zur Beschreibung linguistischer Objekte kommt man schnell zu der Beobachtung, dass es Abhängigkeiten zwischen gewissen Merkmalen gibt. So tritt das Merkmal 'Kasus' nur bei nominalen Kategorien auf, während das Merkmal 'Tempus' nur bei verbalen Kategorien vorkommt. Es liegt deshalb nahe, bei bestimmten Kategorien die Einschränkung von Merkmalen zu fordern. Das wurde versucht, indem man verschiedene Typen von Merkmalstrukturen unterscheidet (z.B. in HPSG).

(17)
-                    -
| cat NP             |
| agr [num singular] |
|     [person  3   ] |
-                    -
nominal

Der Typ einer Merkmalstruktur wird typischerweise als Index am Rand der Matrix notiert. Er bestimmt, welche Merkmale innerhalb der Merkmalstruktur auftreten dürfen, was wiederum vom Grammatikschreiber zu definieren ist.

Beachte: Die Typisierung einer Merkmalstruktur ist nicht gleichwertig mit der Einführung eines Merkmals 'Typ', denn es ist nicht möglich die Zulässigkeit eines Merkmals in Abhängigkeit von einem anderen Merkmal zu definieren.

Durch die Typisierung erreicht man, ähnlich wie bei Programmiersprachen mit getypten Variablen, eine zusätzliche Kontrolle für die Wohlgeformtheit einer Merkmalstruktur sowie eine effizientere Verarbeitung.

In HPSG geht man noch einen Schritt weiter, indem die Merkmalstruktur-Typen in eine Hierarchie geordnet werden können. Ein Typ X erbt dabei alle Merkmale, die an seinem Mutterknoten definiert sind und fügt eigene hinzu. Seien also beispielsweise für den Typ 'nominal' die Merkmale cat, agr, kasus definiert, so könnte es einen Untertyp 'adjektivisch' geben, für den zusätzlich die Merkmale decl, grad erlaubt sind.

(18)
-                    -
| agr [num singular] |
|     [person  3   ] |
| grad superlativ    |
-                    -
adjektivisch

Bei getypten Merkmalstrukturen könnte man festlegen, dass Unifikation nur zwischen Merkmalstrukturen gleichen Typs erfolgen darf. Sinnvoller ist jedoch die Einordnung der Typen in eine Typen-Hierarchie und daraus die Bestimmung des bei einer Unifikation erzielten Typs: Werden zwei typisierte Merkmalstrukturen M1 und M2 unifiziert, so ist der Typ der resultierenden Merkmalstruktur der nächste allgemeinere Typ in der Hierarchie. Bei der Unifikation von (17) und (18) erhält die resultierende Merkmalstruktur den Typ 'nominal'.

Besonderheit: Default-Werte

Ein Default-Wert (dt. Vorbelegungswert) ist ein Wert, der eingesetzt wird, wenn kein fest vergebener Wert existiert. Das hat den Vorteil, dass Werte, die sehr häufig gesetzt werden müssten, an einer zentralen Stelle als Default vorgegeben werden können. Sie werden in GPSG zur Formulierung der sog. Feature Specification Defaults benutzt. Zwei Beispiele (für das Englische):

FSD 1: [INV -]
FSD 8: [NFORM] ==> [NFORM NORM]

FSD1 besagt, dass eine Merkmalstruktur als Vorbelegungswert annimmt, dass keine Inversion vorliegt. FSD 8 drückt aus, dass wenn das Merkmal für 'nominale Form' auftritt, es den Wert NORM hat, d.h. dass es sich um eine normale Subjekt-NP handelt (i.Gg. zu it oder there).

Jedoch führen Default-Werte dazu, dass die Monotonie-Eigenschaft der Unifikation verloren geht, wenn z.B. bei der Unifikation ein Default-Wert durch einen festen Wert überschrieben wird.


Zusammenfassung

  1. Merkmalstrukturen repräsentieren linguistische Objekte.
  2. Merkmalstrukturen können gesehen werden als
  3. Merkmalstrukturen können über die Subsumptionsrelation partiell geordnet werden.
  4. Die Unifikation ist die zentrale Operation über Merkmalstrukturen.
  5. Erweiterte Operationen über Merkmalstrukturen sind:
  6. Komplexe Erweiterungen von Merkmalstrukturen sind:

Gerold Schneider <gschneid@ifi.unizh.ch>, Martin Volk <volk@ifi.unizh.ch>
Date of last modification: October 17, 1999
URL dieser Seite: http://www.ifi.unizh.ch/CL/gschneid/SyntaxVorlesung/Vorl3.FeatStr.html