Programmiertechniken in der Computerlinguistik II · Endliche Automaten, Morphologie, Lexikon, Syntaxanalyse, Merkmalstrukturen Weiterf hrendere und effiziente Programmiertechniken

Programmiertechniken in derComputerlinguistik II

Universität ZürichInstitut für ComputerlinguistikSommersemester 2003

DozentSimon Clematide ‹[email protected]›Übungsbetreuung Marc Staudacher ‹[email protected]›Webhttp://www.cl.unizh.ch/siclemat/lehre/ss03/pcl2

Programmiertechniken in derComputerlinguistik II

Sommersemester 2003

Inhaltsverzeichnis1. Organisatorisches............................................. 1

2. Tokenizer ......................................................... 2

3. Endliche Automaten ........................................ 7

4. Endliche Automaten Techniken ...................... 13

5. Reguläre Mustererkennung ............................ 16

6. Komposition und Differenzlisten ................... 19

7. Morphologie und Buchstabenbäume ............. 22

8. Left-Corner-Parsing ........................................ 28

9. Dynamische Prädikate .................................... 34

10. Charts .............................................................. 36

11. Earley-Parser ................................................... 41

12. Charts: Subsumption ...................................... 48

13. Merkmalstrukturen ......................................... 51

14. Merkmalstrukturen in PROLOG ..................... 55

15. Grammatikentwicklung ................................... 59

16. First-Argument-Indexing ................................. 62

17. Last-Call-Optimization .................................... 63

Konzept-, Prädikats-, Operatoren- und Zeichenindex

Legende: Ein Verweis wie 14.13 meint die 13. Folie des 14. Kapitels.

../2: 14.13:/2: 14.13::/2: 14.14[^…]: 5.4[…]: 5.4^: 5.6$: 5.6+: 5.8*: 5.8{n,m}: 5.10f.abolish/1: 9.7Akzeptor:

DEA 3.16f.append_dl/4: 6.9f.asserta/1: 9.4assertz/1: 9.5Bottom-Up Parsing: 8.3Chart:

als Graph: 10.4als Tabelle: 10.5

clause/2: 9.8DCG:

Morphologie: 7.5f.Effizienz:

Differenzlisten: 6.7f.Buchstabenbäume: 7.14f.First-Argument-Indexing: 16.1Last-Call-Optimization: 17.1

Exception-Handling: 1.15f.foreach/2: 11.11Fundamentalregel: 11.21f.Gepunktete Regeln: 10.10f.GULP: 14.13Kanten:

aktiv: 10.10inaktiv: 10.9

Kantensubsumption: 12.9; 12.11Left Corner Relation: 8.5Link-Relation: 8.15Look-Ahead: 1.8f.Merkmalstruktur:

als Graph: 13.5als Funktion: 13.6offene Liste: 14.8Termschemata: 14.10

Parsing:TopDown mit WFST: 10.14

Pfad: 13:4f.koreferent: 13.9

retract/1: 9.6Rekursive Übergangsnetzwerke: 4.2f.Substitutionsoperator: 5.11subsumes_chk/2: 12.9Termsubsumption: 12.7Tilgungsregeln:

Left-Corner-Parser: 8.16f.Earley-Parser: Übung 8

Top Down Parsing: 8.4,12.15f.Transduktoren: 4.7f.Unifikation:

Merkmalstrukturen: 13.10Vollformenlexikon: 7.3WFST: 10.8f.

Organisatorisches — 1

Aufbau der Lehrveranstaltung (12 DL)

Computerlinguistische Anwendungen in PROLOGElementare und weiterführende Verfahren zur Analyse von Zeichenketten, Wörtern, Phrasen, Sätzen

Endliche Automaten, Morphologie, Lexikon, Syntaxanalyse, Merkmalstrukturen

Weiterführendere und effiziente ProgrammiertechnikenException-Handling, Dynamische Prädikate, Differenzlisten, offene Listen, First-Argument-Indexing, Last-Call-Optimization

Teilakzessprüfung PCL II (bzw. APS-Prüfung PCL II)schriftliche Prüfung, Do 17.7.03, 13.15-14h im KOL-I-321


Übungen

Programmieren lernen ohne selbst am Computer zuarbeiten ist illusorisch!

Übungsaufgabennormalerweise wöchentlich (Aufwand mindestens 2h pro Woche)2 betreute Übungsdoppelstunden pro Woche

zum Erarbeiten oder Besprechen

Schriftliche Abgabe (mit kommentierter Rückgabe)E-Mail(Programmtext bitte direkt als Mail, nicht als Datei angehängt!)

Subject: Prologkurs Uebung 1

To: [email protected] .z

Teilbesprechungen jeweils in der nächsten StundeAbgabe von Musterlösungenh


Lösen der Übungsaufgaben

Offizielle Übungsstunde (Prolog unter Windows 95)PC-Schulungsraum, Rämistr.74, Raum F 021Montag 10-12hDienstag 14-16h

Weitere Übungsmöglichkeiten (Prolog unter MacOS X)In den IFI-Übungsräumen wird es möglich sein, Prolog zu benut-zen, wenn die Räume nicht belegt sind! (normalerweise ab 20h bis 22h, sowie Mi/Do 10-12h; Zeiten sind angeschlagen vor Ort). Wichtig: UniAccess Login und Passwort verfügbar haben!

• IFI, Räume 27-G-25/28• Rämistr. 74, Raum D 017


Folien und Übungsblätter

Die Folien und Übungsblätter sind im WWW verfügbar.Adresse: http://www.ifi.unizh.ch/cl/siclemat/lehre/ss03/pcl2

Format: PDF-Dateien für Adobe Acrobat

Programm zum Lesen der PDF-Dateien (Adobe Acrobat Reader 4; bei Version 3 z.T. Probleme beim Betrachten/Drucken)

auf der SICStus-CD-ROM (jeweils Unterverzeichnis READER)

Neueste Version ab WWW:http://www.adobe.com/prodindex/acrobat/readstep.html

Für alle ohne Drucker Kopiervorlage des Skripts befindet sich in IFI-Bibliothek beim CL-Gestell

Übungs- und Lösungsblätter werden in Stunde verteilt.Wer will, bitte in Liste eintragen und nächstens CHF 2.— mitbringen

Tokenizer — 1

Tokenizer

ÜbersichtWas sind Tokenizer?Der Tokenizer von Covington

Aufrufdiagramm

Definition und Arbeitsweise der einzelnen Prädikate

Programmiertechnik Look-Ahead

Wort- und Satzgrenzen erkennenTokenisieren von Dateien

Probleme mit Dateiende und get0/1

Auffangen von Exceptions mit on_exception/3Programmiertechnik Exception-Handling

Tokenizer — 2

Motivation

Bisher: Linguistische Datenverarbeitung mit Prolog-Termen

Einlesen von Texteinzelne ASCII-ZeichenProlog-Terme einlesen

MangelProlog hat keine vorgefertigte Eingabe-Möglichkeit, wo einfach ein Satz wie "The cat sleeps" zur Verarbeitung eingetippt bzw. eingelesen werden kann.

?- phrase(s, [the,cat,sleeps]).yes

?- get(X).|: aX = 97 ? yes

?- read(X).|: [a,cat,sleeps].X = [a,cat,sleeps]yes

Tokenizer — 3

Zweck und Funktion eines Tokenizers

Wie sollen Benutzende einen Satz eingeben?

|: These are words.

Praktisch für Benutzende

[these, are, words,'.']

Praktisch zum Programmieren

Ein Tokenizerkonsumiert als Eingabe eine Sequenz von Zeichen (Eingabestrom)gruppiert die Eingabezeichen zu sinnvollen Einheiten (Token)

gewisse Eingabezeichen können dabei auch modifiziert werden

produziert als Ausgabe die Sequenz der Token (Liste)

Tokenizer — 4

?- read_atomics(Eingabe).

|:

Eingabe = [these,are,words,'.'].Eingabe überTastatur

These are words.Abschluss

durch RETURN

Ein einfacher Tokenizer

Ein Tokenizer findet sich in Covington (1994: Anhang B)Aufruf des Tokenizers durch read_atomics/1

liest eine Zeile voll Buchstaben von der Standardeingabe eingibt Liste der Atome der tokenisierten Zeile als Resultat zurückGrossbuchstaben werden in Kleinbuchstaben verwandelt

Tokenizer — 5

Aufrufdiagramm des Tokenizers

Aufrufdiagramme (call graphs)Ein Prädikat ruft die Prädikate auf, zu denen ein Pfeil führt

Eingebaute oder Standard-Prädikate werden meist weggelassen

Rekursive Prädikate sind durch Schlaufen verbunden

read_atomics/1

read_char/2

char_type/3

complete_line/3

complete_word/5

Aufrufdiagramm der Tokenizer Prädikate

Haupt-Prädikat

Tokenizer — 6

Zeichen klassifizieren mit char_type/3

?- char_type(65, Type, Char).Type = alpha,Char = 97

64 @65 A66 B96 `

97 a98 b

ASCII-Codes

Das Hilfsprädikat char_type/3 klassifiziert Zeichenend – Zeilenendeblank – Leerzeichenalpha – alphanumerische Zeichen, d.h. Buchstaben und Ziffernspecial – übrige Zeichen

Zudem liefert char_type/3 das Zeichen als Klein-buchstaben zurück.

Tokenizer — 7

char_type/3

char_type(10, end, 10) :- !. % UNIX end of line markchar_type(13, end, 13) :- !. % Macintosh/DOS end of line markchar_type(-1, end, -1) :- !. % get0 end of file code

char_type(Code, blank, 32) :- % blanks, other control codes Code =< 32, !.

char_type(Code, alpha, Code) :- % digits 48 =< Code, Code =< 57, !.

char_type(Code, alpha, Code) :- % lower-case letters 97 =< Code, Code =< 122, !.

char_type(Code, alpha, NewCode) :- % upper-case letters 65 =< Code, Code =< 90, !, NewCode is Code + 32. % translate to lower case

char_type(Code, special, Code). % anything else

Tokenizer — 8

read_atomics/1 und read_char/2

read_char/2: Ein Zeichen einlesen und klassifizieren

read_atomics/1: Erstes Zeichen (look ahead) einlesen und dann den Rest verarbeiten lassen

Die Vorausschau von einem Zeichen brauchts zum Entscheid, ob das aktuelle Zeichen das letzte eines Wort-Tokens ist.

read_char(Char, Type) :- get0(EnteredChar), char_type(EnteredChar, Type, Char).

read_atomics(Atomics) :- read_char(FirstChar, FirstType), complete_line(FirstChar, FirstType, Atomics).

Tokenizer — 9

?- complete_line(97, alpha, Result).

|: bba, baba.

Result = [abba, ',', baba, '.'].

ASCII-Codes

96 `97 a98 b99 c

Beispiel-Anfrage

complete_line/3

complete_line/3 besitzt folgende Argumentedas look-ahead-Zeichen: Integerdessen Typ (als Fallunterscheidung): Atom

falls end : stoppen, da Zeile fertig eingelesen ist!

falls blank : überspringen!

falls alpha : Zeichen zum Wort-Token kompletieren!falls special : Zeichen zu eigenem Token machen!

Ergebnisliste aus den einzelnen Tokens: Liste atomarer Terme

Tokenizer — 10

complete_line(_, end, []) :- !. Rote oder grüne Cuts?

Unter der Voraussetzung, dass das 2. Argument beim Aufruf von complete_line/3 immer instanziiert ist: grün!

complete_line/3

complete_line(FirstChar, alpha, [A|Atomics]) :- complete_word(FirstChar, alpha, Word, NextChar, NextType), name(A, Word), complete_line(NextChar, NextType, Atomics).

complete_line(_, blank, Atomics) :- !, read_atomics(Atomics).

complete_line(Char, special, [A|Atomics]) :- !, name(A, [Char]), read_atomics(Atomics).

Tokenizer — 11

Spezifikation von complete_word/5

complete_word/5 besitzt folgende Argumentedas look-ahead-Zeichendessen Typeine Liste, bestehend aus den ASCII-Codesder Zeichen, die zum gegenwärtigen Wortgehörendem nächstfolgenden Zeichen, das nicht zum Wort gehört,dessen Typ

?- complete_word(97, alpha, List, FollowChar, FollowType).|: bba;

List = [97, 98, 98, 97], FollowChar = 59,FollowType = special

ASCII-Codes

96 `97 a98 b99 c100 d101 e

58 :59 ;60 <

Tokenizer — 12

complete_word(FirstChar, alpha, [FirstChar|List], FollowChar, FollowType) :- !, % red Cut read_char(NextChar, NextType), complete_word(NextChar, NextType, List, FollowChar, FollowType).

Implementation von complete_word/5

RekursionsschrittLook-ahead ist alphanumerisch!

FollowChar ist das zukünftige Look-ahead-Zeichen, das 1. Zeichen nach dem Wort!

AbbruchbedingungLook-ahead ist nicht alphanumerisch!

Es wird nichts mehr konsumiert, nur noch Wort-Zeichen-Liste abgeschlossen!

Zukünftiger Look-Ahead wird auf aktuellen gesetzt!

complete_word(FirstChar, FirstType, [], FirstChar, FirstType).

Tokenizer — 13

Schwierigere Fälle

Welche Zeichen gehören zu welchem Token?234.50Die Grille zirpt.Die Grille zirpt immer um 10.Die Grille zirpt immer am 10. Okt.Scarlett O’Hara sagte ’Schau mir in die Augen, Kleines’ und erhielt dafür ca. Fr. 1’234.--.I said ’don’t’…

Doppelklick

Tokenizer — 14

Satzgrenzen erkennen

Bezeichnet ein Punkt das Ende eines Satzes?It was due Friday by 5 p.m. Saturday would be too late.She has an appointment at 5 p.m. Saturday to get her car fixed.

Lösungsansätze»Jeder Punkt ist ein Satzende!« – 8-45% Fehlerquote (Englisch)Abkürzungswörterbuch, Regeln mit regulären Ausdrücken – < 2%Training anhand Korpus – < 2%Lösungsansatz mit Neuronalem Netz Palmer/Hearst (1994) (mit zusammenfassendem Einstieg ins Problem)…

Tokenizer — 15

Erste IdeeDatei besteht aus Folge von ZeilenEinlesen aller Zeilen durch all-solution-Prädikat

Wegen Determinismus von read_atomics/1 muss repeat/0 verwendet werden!

Aber

Zeilenweises Tokenisieren von Dateien

naive_tokenize_file(File, Lines) :- see(File), findall(Line, (repeat,read_atomics(Line)), Lines), seen.

?- naive_tokenize_file('gedicht.txt', Lines).! Existence error in get0/1! attempt to read past end of stream! goal: get0(_73)

Tokenizer — 16

ProblemDateiende darf nur einmal gelesen werden mit get0/1!Bei einem weiteren Versuch wird eine exception ausgelöst!

?- tell('leer.txt'),told.yes?- see('leer.txt').yes?- get0(C).C = -1yes?- get0(C).! Existence error in get0/1! attempt to read past end of stream! goal: get0(_73)

Ausnahmefall: Lesen über Dateiende

Tokenizer — 17

Ausnahmefälle behandeln

Das Metaprädikat catch(Goal,Pattern,Handler) kann Ausnahmefälle auffangen.

catch/3 ruft Goal aufFalls Goal gelingt oder scheitert, macht catch/3 dasselbe.Falls beim Beweis von Goal eine Exception E ausgelöst wird, passiert folgendes:

Falls E mit Pattern unifiziert werden kann, wird als neues Ziel Handler aufgerufen.Falls E nicht mit Pattern unifiziert werden kann, wird E weiter hochgegeben.

exceptions können beliebige Terme sein!exception für das Lesen über das Dateiende (leicht systemabhängig):

existence_error(_,_,_,_,past_end_of_stream)

Tokenizer — 18

Zeilenweise Tokenisieren von Dateien

IdeeTokenizer soll scheitern, falls über Dateiende gelesen wirdsafe_read_atomics/1 liest via Backtracking alle Zeilen

tokenize_file/2 liest alle Zeilen ein

safe_read_atomics(Atomics) :- catch( (repeat, read_atomics(Atomics)), % Goal existence_error(_,_,_,_,past_end_of_stream), % Pattern fail % Handler ).

tokenize_file(File, Lines) :-see(File),findall(Line, safe_read_atomics(Line), Lines),seen.

Tokenizer — 19

Literaturhinweise I

TokenizerMichael A. Covington (1994): Natural Language Processing for Prolog Programmers. Prentice Hall.

Eine verbesserte Version mit etwas anderem Output findet sich unter http://www.ai.uga.edu/~mc/et/et.zip

Palmer, David D. (2000): Tokenisation and Sentence Segmentation. In: Handbook of natural language processing, edited by R. Dale, H. Moisl and H. Somers. New York. S. 11-35

SatzgrenzenerkennungDavid D. Palmer/Marti A. Hearst (1994): Adaptive Sentence Boundary Disambiguation. In: Proceedings of the ANLP ’94, Stuttgart. http://xxx.lanl.gov/abs/cmp-lg/9411022

Tokenizer — 20

Literaturhinweise II

Programmieren mit ExceptionsSICStus Prolog Handbuch: Dokumentation zu den folgenden Prädikaten für das Auffangen und Auslösen von Ausnahmen:

catch/3throw/1

Endliche Automaten — 1

Endliche Automaten (EA)

ÜbersichtEndliche Automaten als BerechnungsmodellBeispiel-Automat: Der Lachautomat

Verabeiten von Eingabeketten

Akzeptieren von Eingabeketten

Mengentheoretische FormalisierungEndliche Automaten in PrologNicht-Deterministische Endliche AutomatenSprachen von Endlichen AutomatenReguläre AusdrückeLiteratur


Motivation

Endliche Automaten (Finite-State Automata) sind …mathematisch wohl-definiert und theoretisch aufgearbeitet

Informatik: Grundlage der Berechenbarkeitstheorie

Linguistik: Sind Teile der menschlichen Sprache mit Endlichen Automaten beschreibbar? Struktur von Wörtern, Sätzen, Dialogen…

leicht implementierbar und effizient ausführbar auf Computerin unterschiedlichsten Gebieten anwendbar

Sprachverarbeitung: Tokenizer, Morphologie, Lexikon, Informationsextraktion, Phrasenerkennung, (Partielle) syntaktische Analyse …

Eigentliches Revival der sog. finite state methods in NLP feststellbar!

Informatik: Compilertechnik, Kommunikationsprotokolle, Prozessmodellierung,…

… abstrakte Maschinenmodelle!


Graphische RepräsentationZustandsübergangdiagramm (transition diagram)

Beispiel: Ein Lachautomat

1 2 3 4

h a !

h


Eingabe des Automaten

1 2 3 4

h a !

h

Der Lachautomat erhält eine Zeichenkette als Eingabe:

h a h a !

Was macht der Automat damit?


Beginn der Verarbeitung

Zu Beginnder Automat ist im Startzustander schaut auf das erste Zeichen der Eingabe

1 2 3 4

h a !

h

h a h a !


Der Automat nimmt jenen Übergang,der vom aktuellen Zustand ausgehtund mit jenem Zeichen in der Eingabekette beschriftet ist,auf das der Automat gerade schaut.

Ein einzelner Verarbeitungsschritt

1 2 3 4

h a !

h

h a h a !


h a h a !

Ein einzelner Verarbeitungsschritt

Beim Nehmen eines Übergangsspringt der Automat in einen neuen Zustand undschaut auf das nächste Zeichen in der Eingabekette

h !

1 2 3 4

a

h

h a h a !

1 2 3 4

h a !

h


Abarbeiten der Eingabe

Der Automat konsumiert so Zeichen um Zeichen.

h1 2 3 4

h a !

h a h a !1 2 3 4

h a !

h h a h a !1 2 3 4

h a !

h h a h a !


Abarbeiten der Eingabe

1 2 3 4

h a !

h h a h a !

Der Automat konsumiert Zeichen um Zeichen,bis auch das letzte Zeichen der Eingabe konsumiert wurde.

1 2 3 4

h a !

h h a h a !Endliche Automaten — 10

Wenn die Eingabe vollständig konsumiert ist, gibt es zwei Möglichkeiten

der aktuelle Zustand ist ein EndzustandAutomat hat die Eingabe akzeptiert

der aktuelle Zustand ist kein EndzustandAutomat hat die Eingabe nicht akzeptiert

Ein Automat kann mehrere Endzustände besitzen!

Ende der Verarbeitung I

3

4


Kommt der Automat nicht weiter, weil kein Übergang zum aktuellen Eingabezeichen passt, ist die Eingabe ebenfalls nicht akzeptiert.

Ende der Verarbeitung II

1 2 3 4

h a !

h

h a i !


Akzeptoren

1 2 3 4

h a !

h

Der Lachautomat ist ein Akzeptor.Eingabe: ZeichenketteAusgabe: »akzeptiert« oder »nicht akzeptiert«

Ausgabe: Ja

ha!haha!

hahaha!

hahahaha!

hi!

hahahah!

Ausgabe: Nein

ah!aha!


Bestandteile

1 2 3 4

h a !

h

4 1

23

ZuständeStates

StartzustandStart State

1

EndzuständeFinal States

4

ÜbergängeTransitions

1 2h

3 4!

3 2h

2 3a

AlphabetAlphabet

ha

!

Bestandteile eines Endlichen Automaten

i


Mengentheoretische Definition

4 1

23

Zustände Startzustand

1

Endzustände

4

Übergänge

1 2h

3 4!

3 2h

2 3a

Alphabet

ha

!i

⟨S, s, F ⟩δ,Σ,Ein Endlicher Automat ist ein Fünf-Tupel

endliche, nicht leere Menge von Zuständen SEingabe-Alphabet Σpartielle Übergangsfunktion δ: (S × Σ ) → SStartzustand s ∈ SMenge von Endzuständen F ⊆ S


Mengentheoretischer Lachautomat

Dieser Automat sei ein 5-Tupel ⟨S, Σ, δ, s, F⟩ mitS = {1, 2, 3, 4}Σ = {a, i, h, !}δ = {⟨⟨ 1, h⟩, 2⟩ , ⟨⟨ 2, a⟩, 3⟩ , ⟨⟨ 3, h⟩, 2⟩, ⟨⟨ 3, !⟩ , 4⟩}s = 1F = {4}

1 2 3 4

h a !

h


EA-Akzeptor in Prolog I

1 2 3 4

h a !

h

start(1).

delta(1, h, 2).delta(2, a, 3).delta(3, h, 2).delta(3, !, 4). final(4).

1 41 2

h

3 4!

3 2h

2 3a

Übergänge EndzuständeStartzustand

Die Struktur


Die AbarbeitungInitialisierung

Abarbeitung der Eingabekette

EA-Akzeptor in Prolog II

1 2 3 4

h a !

h

accept([], State) :- final(State).

accept([Char|Chars], State) :- delta(State, Char, NextState), accept(Chars, NextState).

init(String) :- start(StartState), accept(String, StartState).


(Deterministische) Endliche Automaten

1 2 3 4

h a !

h

Deterministische Endliche Automaten (DEA)Deterministic Finite-State Automata (DFA)

Von einem Zustand gehen nur Übergänge mit verschiedenen Beschriftungen aus.Jeder Übergang konsumiert ein Zeichen der Eingabekette.

Es kommt immer höchstens ein Übergang in Frage.


Nicht-deterministische Endliche Automaten

Nicht-deterministische Endliche Automaten (NEA)Non-deterministic Finite-State Automata (NFA)

Mehrere gleich beschriftete Übergänge von einem Zustand möglichεεεε-Übergänge (epsilon) möglich, bei denen kein Eingabesymbol konsumiert wirdMehrere Übergänge können gewählt werden.Trotzdem: Jeder NEA kann in einen DEA konvertiert werden!

1 2 3 4

h a !

ε

1 2 3 4

h a !

a


Sprache Endlicher Automaten

Definition: Sprache eines Endlichen AutomatenDie Menge aller Eingabeketten, die von einem EndlichenAutomaten A akzeptiert werden, heisst Sprache des Automaten A, meist geschrieben als L( A ).

L(Lachautomat) = {ha!, haha!, hahaha!, hahahaha!,…}

Die Sprachen Endlicher Automaten können unendlich viele Elemente enthalten!

1 2 3 4

h a !

h


Endliche Automaten und Reguläre Ausdrücke

Die Sprachen, welche mit Endlichen Automaten erkannt werden können, heissen Regulären Sprachen.

Reguläre Sprachen können auch durch Reguläre Ausdrücke beschrieben werden:

1 2

a

1 2 3

a b

31 2

a b

ε

1 2

a

b

31 2

a b

ε

Einzelnes Symbol des Alphabets: a

Verkettung: abAlternative: ( a| b)

Optionalität: ( ab)?Repetition: ( ab)+

31 2

a b

ε

Optionale Repetition: ( ab)*


Lachen als Regulärer Ausdruck

Die Sprache, welche unser Lachautomat akzeptiert, kann als Regulärer Ausdruck spezifiziert werden.

Achtung: Gewisse Diagramme lassen sich nicht 1:1 übertragen!

Unterschiedliche Umformungensind oft möglich!

h( ah)* a!

1 2 3 4

h a !

a( ha)+ !

31 2 4

h a !

ε

ha( ha)* !

1 2 3 4

h a !

h


Endliche Automaten Generatoren

Aus Regulären Ausdrücken lassen sich automatisch Endliche Automaten generieren, die die Sprache akzeptieren, welche die Regulären Ausdrücke beschreiben!

In der Computerlinguistik oft verwendet, insbesondere für morphologische VerarbeitungAnwendungen in sogenannten lex -Werkzeugen, die für lexikalische Analyse beim Kompilieren von Programmiersprachen verwendet werdenAnwendung beim Verabeiten von Suchmustern (pattern matching), die als Reguläre Ausdrücke angegeben werden. Z.B. in den Programmiersprachen Perl, JavaScript, Java, grep -Tools von UNIX, Suche in MS Word usw.


Literaturhinweise

Mathematische Grundlagen der LinguistikBarbara H. Partee/Alice ter Meulen/Robert E. Wall: Mathematical Methods in Linguistics. Dordrecht: Kluwer Academic Publishers, 1990.

Ausführliche, gut verständliche Einführung in Mengenlehre, Logik, Algebra, Lambda-Kalkül, Automatentheorie. Empfehlenswert.

Verarbeitung Endlicher Automaten in PrologGerald Gazdar/Chris Mellis: Natural Language Processing in PROLOG: An Introduction to Computational Linguistics. Wokingham: Addison-Wesley, 1989. Seiten 21-59

Programmierung einfacher computerlinguistischer Anwendungen mit EAs

Wilhelm Weisweber: Prolog: Logische Programmierung in der Praxis: Thomson, 1997. Seiten 281-293Verarbeitung von EAs und Umwandlung von NEA zu minimalen DEA

Reguläre Ausdrücke, Endliche Automaten und Prologhttp://odur.let.rug.nl/~vannoord/prolog-rx/PrologAndRegex.html

Endliche Automaten Techniken — 1

Endliche Automaten Techniken

ÜbersichtRekursive Übergangsnetzwerke (RTN)RTN in PrologErweiterungen von RTNsVom Akzeptor zum Transducer

Beispiel: Lachautomat-Transduktor

Implementation von Transduktoren in PrologLesen oder Schreiben?Kompilieren oder Interpretieren?


Rekursive Transitionsnetzwerke (RTN)

Syntaxanalyse mit RTN —Erweiterungen gegenüber EA

Kanten sind lexikalische Kategorien!Det, N, Pn, Vt, Vi

Kanten sind selbst Automaten!Phrasen: S, VP, NP

Literatur:Gazdar/Mellish (1989: 59ff.)

Matthews (1998: 141ff.)

31 2

NP VPS:

31 2

Det NNP:

Pn

Vt

31 2

NPVP:

Vi


RTNs in Prolog I

Lexikonword(the, det).word(man, n).word(dog, n).word(peter, pn).word(smokes, vi).word(sees, vt).

final(s, 3).final(np, 3).final(vp, 3).

delta(s, 1, net(np), 2).delta(s, 2, net(vp), 3).

delta(vp, 1, vi, 3).delta(vp, 1, vt, 2).delta(vp, 2, net(np), 3).

delta(np, 1, pn, 3).delta(np, 1, det, 2).delta(np, 2, n, 3).

Die Übergänge

Startzustände

start(s, 1).start(np, 1).start(vp, 1).

Endzustände


init(String, StartNet) :-init(String, StartNet, []).

InitialisierungEine Zeichenkette gilt von einem Netzwerk als akzeptiert, falls ausgehend vom Startzustand des Netzwerks die ganze Zeichenkette abgearbeitet werden kann.

Jedes Netzwerk konsumiert soviel von der Eingabekette, wie es ausgehend von seinem Startzustand akzeptiert.

RTN in Prolog II

init(String, Net, RestString) :-start(Net, StartState),accept(String, Net, StartState, RestString).


AbarbeitungFall 1: Lexikalischer Übergang konsumiert Wort!

Fall 2: Hineinspringen in Subnetzwerk ohne Zeichenkonsum!

Fall 3: Abbruchbedingung: Endzustand des Netzwerks erreicht!

RTN in Prolog III

accept(String, Net, State, String) :-final(Net, State).

accept([Word|String], Net, State, RestString) :-word(Word, Cat),delta(Net, State, Cat, NextState),accept(String, Net, NextState, RestString).

accept(String, Net, State, RestString) :-delta(Net, State, net(SubNet), NextState),init(String, SubNet, RestStringSubNet),accept(RestStringSubNet, Net, NextState, RestString).


31 2

Det( kasus(K), numerus(N))

N( kasus(K), numerus(N))

NP( kasus(K), numerus(N)):

Pn( kasus(K), numerus(N))

31 2

NP(kasus(nom),numerus(N)) VP(numerus(N))

S( numerus(N)):

Komplexe KantenKomplexe lexikalische Kategorienspezifizieren die üblichen morphosyntaktischen BeschränkungenKomplexe Automatenbezeichungen erlauben kantenübergreifende Kongruenzbeziehungen

Allerdings: Die Welt der EA haben wir damit zugunsten mächtigerer Ausdrucksmittel verlassen.

Aber: Warum sollen wir uns künstlich beschränken?

Erweiterungen von RTNs


Endliche Automaten vs. Transduktoren

Akzeptierende EAs: Einfach, aber eingeschränkt nützlich!Einfache akzeptierende Endliche Automaten sind ein gutes Modell, aber für die Praxis oft zu eingeschränkt!Wer mehr wissen will als nur "ja" oder "nein", muss den Formalismus aufbrechen (siehe RTN).

Transducer: Einfach, und erst noch nützlich!Endliche Automaten, die zusätzlich zum Lesen auch noch Schreiben können, werden oft als Transduktoren (transducer) bezeichnet.Transduktoren können die beim Verarbeiten durchlaufenen Schritte nach Aussen kommunizieren ohne den Formalismus aufzubrechen!


Lach-Transduktor

1 2 3 4

h:h a:i !:?

h:h

h a h a ! h i h iLeseband Schreibband

Scanner-Interpretation mit Lese- und Schreibband


Transduktor in Prolog I

1 2 3 4

h:h a:i !:?

h:h

start(1).

delta(1, h, h, 2).delta(2, a, i, 3).delta(3, h, h, 2).delta(3, !, ?, 4). final(4).

1 41 2

h:h

3 4!:?

3 2h:h

2 3a:i

Übergänge EndzuständeStartzustand


TransduktorInitialisierung

Abarbeitung

Transduktor in Prolog II

transduce([], [], State) :- final(State).

transduce([InChar|InChars], [OutChar|OutChars], State) :- delta(State, InChar, OutChar, NextState), transduce(InChars, OutChars, NextState).

init(Input, Output) :- start(StartState), transduce(Input, Output, StartState).

1 2 3 4

h:h a:i !:?

h:h


Wir können in beide Richtungen schreiben bzw. lesen.

Wir können die Ein- und Ausgabesprache aufzählen lassen.

Es gibt soviele Lösungen, wie die Sprache Elemente hat…

Lesen oder Schreiben?

?- init(R, [h,i,'?']).R = [h,a,'!'];no

?- init([h,a,'!'], R).R = [h,i,'?'];no

?- length(L1, _), init(L1, L2).L1 = [h,a,'!'] L2 = [h,i,'?'];L1 = [h,a,h,a,'!'] L2 = [h,i,h,i,'?'];....


Interpretieren oder kompilieren?

Automaten müssen nicht zwangsweise interpretiert werden!

Automaten-Struktur und Abarbeitung lassen sich zu einem effizienteren, aber spezifischeren Programm verquicken!lachen(+Ausgangszustand, ?Input, ?Output)

lachen(1, [h|RestIn], [h|RestOut]) :-lachen(2, RestIn, RestOut).

lachen(2, [a|RestIn], [i|RestOut]) :-lachen(3, RestIn, RestOut).

lachen(3, [h|RestIn], [h|RestOut]) :-lachen(2, RestIn, RestOut).

lachen(3, [!], [?]).

lachen(In, Out) :-lachen(1, In, Out).

Reguläre Mustererkennung — 1

Reguläre Mustererkennung

ÜbersichtSuche von Zeichenketten mittels regulärer AusdrückeEine Anwendung von Endlicher Automaten TechnikReguläre Suchmuster:

Zeichenketten

Zeichenklassen

VerankerungenOptionalität

Disjunktion, Gruppierung

Wiederholungen

Suchstrategien: Eifrig und gierig!Ersetzen mit Regulären Ausdrücken


Mustererkennung

Mustererkennung (pattern matching) in ZeichenkettenIn Textverarbeitungsprogrammen und vielen Programmiersprachen

Hier: Mustererkennung wie es in Perl oder JavaScript 1.2 zur Verfügung steht

Leider gibt es von Programm zu Programm kleinere und grössere Unterschiede in

der konkreten Syntax. Die Prinzipen selbst sind allerdings stabil.

Zeilenweise MustererkennenZ.B. grep-Tool: Zeige alle Zeilen, in denen ein Muster vorkommtHier: Zeige das gefundene Muster in einer Zeichenkette

Einmaliges vs. mehrfaches ErkennenHier: Nur sogenannter first match

Erweiterungen mit ErsetzenMehrfaches Ersetzen bringt zusätzliche Schwierigkeiten…


Zeichenketten

Wörtliche ZeichenZeichenketten (mit relevanter Gross-/Kleinschreibung)

/Peter Pan/ matcht "Aber Peter Pan sagte:"

/die/ matcht "Die Radieschen schmecken."

Zeichen mit Sonderbedeutung Die Zeichen .?()[]{}*+|^$\ müssen mit \ geschützt werden.

Dem schützenden Steuerzeichen (escape char) zusammen mit dem geschützten Zeichen sagt man escape sequence.

/z\.B\. nicht\?/ matcht "Wer mag das z.B. nicht?"

Zeichen für SonderzeichenTabulator (\t ), Zeilenvorschub (\n ), Wagenrücklauf (\r )

/\tTabulatoren\t/ matcht "Viele Tabulatoren "


Zeichenklassen

ZeichenauswahlZwischen eckigen Klammern stehen alternative Zeichen.

/[dD]ie/ matcht "Die Birne" oder "das Radieschen"

/[1234567890] h/ matcht "Das dauert 2 h." oder "Das dauert 3 h."

ZeichenausschlussDas Dach in[^ chars] schliesst alle nachfolgenden Zeichen aus.

/[^aeiou][^aeiou]/ matcht "abba"

ZeichenbereicheDer Bindestrich erlaubt Bereiche von nachfolgenden Zeichenkodes.

/Kapitel [0-9]/ matcht "Kapitel 4.2"

/[A-Z][A-Z][A-Z]/ matcht "laut BBC wurde"


Vorgefertigte Zeichenklassen

Wildcards: Vorgefertigte ZeichenklassenDer Punkt steht für ein einzelnes Zeichen ausser \n.

/ ... / matcht "Aber der Frosch sprach"

\d steht für eine Ziffer von 0 bis 9/CH\-\d\d\d\d/ matcht "CH-8580 Amriswil"

\s steht für Layoutzeichen (Leerzeichen, Zeilenende, Tabulatoren)/,\s/ matcht "Er kommt, ich weiss es."

\w steht für ein alphanumerisches Zeichen oder Unterstrich Orientiert sich an Bezeichnern in Programmiersprachen wie C oder Perl

/\w\w\w\w/ matcht "Was, 99$ kostet das?"

Grosse Wildcards sind ausgeschlossene kleine:\D = [^\d], \S = [^\s], \W =[^\w]


Verankerungen

Verankerungen: Positionieren von SuchmusternMit dem Dach suchen wir am Anfang der Zeichenkette

/^die/ matcht "die Radieschen"

Mit dem Dollar suchen wir am Ende der Zeichenkette/die$/ matcht "die Parodie"

Mit \b suchen wir an einer Wortgrenze/\bdies\b/ matcht "Den Radieschen ist der 'dies academicus' egal."

Als Wortgrenze zählen nebst allen Zeichen, die \W matchen noch Anfang und Ende von Zeichenketten.

Mit \B suchen wir nicht an einer Wortgrenze.Praktisch: /\B...\b/ matcht Suffixe, /\b...\B/ matcht Präfixe

Die Verankerungen selbst matchen keine Zeichen!


Optionalität, Gruppierung, Disjunktion

Optionale ZeichenDas Fragezeichen macht das vorausgehende Zeichen optional:

/Microsofts?/ matcht "Microsoft verschenkt Programme."

Optionale MusterDank Klammerung lassen sich reguläre Muster optional setzen:

/(Bill )?Gates/ matcht "Gates als Wohltäter"

DisjunktionDer senkrechte Strich ist ein Infixoperator, der alternative Ausdrücke trennt — mit niedrigste Präzedenz.

/das|die/ matcht "Gates verärgert die Aktionäre."

/, (die|das|der)/ matcht "Das Programm, das niemand kauft."


Wiederholungen

+: Mindestens einmal repetierenZeichen repetieren

/\d+/ matcht "Er feiert den 25. Geburtstag."

Um Muster zu repetieren, braucht es Klammern:/([Hh]a)+!/ matcht "Er: Hahahaha!"

*: Beliebig oft wiederholenBeliebig heisst null oder mehr Mal...

/x*/ matcht "" oder "xxx"

/the*/ matcht "theee"

/Ha(ha)*!/ matcht "Hahaha!"

Achtung: Was matcht /h*/ in "d.h."?


Matching-Strategien

Matching ist mehrdeutig/h*/ matcht nicht bloss "d.h.", sondern noch ε vor und nach allen Buchstaben!D.H. "εd.h.", "dε.h.", "d.εh.", "d.hε.", "d.h.ε"

Strategie I: Sei eifrig! (eager)Matche die am weitesten links stehende Zeichenkette!

/h*/ matcht zuerst "εd.h."

Matching ist mehrdeutig/a!*/ passt nicht bloss auf "ha!!!", sondern auch auf "ha!!!", "ha!!!" und "ha!!!"

Strategie II: Sei gierig! (greedy)Matche soviele Zeichen wie möglich mit einem Ausdruck!

/a!*/ matcht "ha!!!"


Wiederholungen II

{n}: Genau n Mal wiederholen!/\d{2}(-\d{3}){2}/ matcht "Immatrikulationsnummer 99-723-362"

{min,max}: Mindestens min Mal und höchstens max Mal wiederholen

/ha{3,6}!/ matcht "haaaa!", aber nicht "haa!" oder "haaaaaaa!"

{n,}: Mindestens n Mal wiederholen!

Beispiel: Suche Sätze, die mindestens 3 Komma enthalten!/(.*,.*){3,}/

Beispiel: Suche Sätze, die genau 3 Komma enthalten!/([^,]*,[^,]*){3}/


Ersetzen mit Regulären Ausdrücken

Oft soll die gefundene Zeichenkette ersetzt werden.Ersetzungsoperator: s/ Suchmuster/ Ersetzungstext/

s/z\. ?B\./zum Beispiel/

Oft sollen nur bestimmte Teile der gefundenen Zeichenkette modifiziert werden.

Geklammerte Ausdrücke im Suchmuster stehen im Ersetzungstext als nummerierte Register ($n) zur Verfügung

n-tes Register enthält Ausdruck mit n-ter öffnender Klammer (von links nach rechts)

s/(\w+) \w+ (\w+)/$2 $1/ modifiziert "das alte Haus" zu "Haus das"

Beispiel "Satzendeerkennung"Einsetzen eines Leerzeichen vor Satzendpunkten

s/(\. ["\(«'])/ $1/ modfiziert "Er log. "Soso!" zu "Er log . "Soso!"


Literatur

Minitutorat mit Beispielen und Übungen zum Trainierenhttp://www.ifi.unizh.ch/cl/siclemat/lehre/ss03/pcl2/regextut/

LiteraturFriedl, Jeffrey E. F. (1998): Reguläre Ausdrücke.

"Bibel der Regulären Ausdrücke": Widmet sich umfassend dem Umgang mit Regulären Ausdrücken in verschiedenen UNIX-Tools und Perl.

Jurafsky, D., Martin, J. (2000): Speech and Language Processing: An Introduction to Natural Language Processing. S.21-33.

Verständliche Einführung mit einigen praktischen Beispielen.

Handbücher zur Programmiersprache PERLHilfe zu MS Word

Komposition und Differenzlisten — 1

Komposition und Differenzlisten

ÜbersichtMorphologie: Fallbeispiel Komposition

Komposition als Listenverkettung

Stämme und ihre Information

Komposition und Vererbung von InformationEffizienzprobleme mit append/3

DifferenzlistenOffene Listen + Zugriff auf Restliste

Verkettung von Differenzlisten: append_dl/3Implizites Verketten durch Variablenbindung

Differenzlisten sind wichtigste Datenstruktur in Prolog für effiziente Verarbeitung sequentieller Daten!


Komposition als Verkettung

Simple Idee zur Bildung und Analyse von KompositaListen von Buchstabenatomen repräsentieren

Einfache Worte

Allfällige Fugen (z.B. s, en, n)

Komposition ist Listenverkettung, sowohl für

AnalysewieSynthese

arbeit+s+zeit [a,r,b,e,i,t]+[s]+[z,e,i,t]

Kompositionsanalyse Repräsentation in PROLOG

?- append([b,r,o,t], N, [b,r,o,t,z,e,i,t]).N = [z,e,i,t]

?- append([b,r,o,t], [z,e,i,t], K).K = [b,r,o,t,z,e,i,t]


n_comp(Kompositum, Flexion, Genus, Fuge) :- n_stamm(Stamm1, _, _, Fuge1), append(Stamm1, Fuge1, Teil1), n_stamm(Stamm2, Flexion, Genus, Fuge), append(Teil1, Stamm2, Kompositum).

n_stamm/4 und n_comp/4

Nominalstämme: n_stamm/4i. Zeichenfolge

ii. Flexionsklasse

iii. Genusiv. Fugenforderung

Nominalkomposita: n_comp/4i. Zeichenfolge

ii. Flexionsklasse des Kompositum

iii. Genus des Kompositum

iv. Fugenforderung des Kompositum

n_stamm([a,r,b,e,i,t], 1, f, [s]).n_stamm([z,e,i,t], 1, f, []).n_stamm([b,r,o,t], 1, n, []).n_stamm([p,a,u,s,e], 2, f, [n]).


append/3

Listen verketten

append([], L2, L2).

append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).

Die Laufzeit ist proportional zur Länge der ersten Liste.rekursives Abarbeiten der ersten Listefür jedes Element der ersten Liste ein rekursiver Aufruf


Verwendung von append/3 führt zu grosser Ineffizienzum Fugenelement anzuhängen, muss das Erstglied vollständig dekomponiert werden

bevor falsches Erstglied bemerkt wird, werden alle Zweitglieder ausprobiert

es werden blind alle Kombinationen versucht, bis allenfalls die passende Struktur erscheint

Effizienzüberlegungen

3 2 Call: append([a,r,b,e,i,t],[s],_522) ? 9 8 Exit: append([],[s],[s]) ? 3 2 Exit: append([a,r,b,e,i,t],[s],[a,r,b,e,i,t,s]) ?

11 2 Call: append([a,r,b,e,i,t,s],[a,r,b,e,i,t],[b,r,o,t,z,e,i,t])11 2 Call: append([a,r,b,e,i,t,s],[z,e,i,t],[b,r,o,t,z,e,i,t])11 2 Call: append([a,r,b,e,i,t,s],[b,r,o,t],[b,r,o,t,z,e,i,t])11 2 Call: append([a,r,b,e,i,t,s],[p,a,u,s,e],[b,r,o,t,z,e,i,t])


Verbesserungsmöglichkeiten

Wie optimieren?Fallunterscheidung, falls Fugenelement "leer" istEffizienteres append/3 mit Akkumulatortechnik verwenden

Nur minime Verbesserung!

Falsche Erstglieder sofort erkennen und nicht noch Zweitglied mutierenBessere Datenstruktur wählen, die Listenverkettung zulässt, ohne dass eine Liste immer vollständig auseinander zu nehmen ist

Erstaunlicherweise gibt es eine Prolog-Datenstruktur, mit der die letzten 2 Punkte verbessert werden können:

Differenzlisten


Differenzlisten

Die Liste [1,2,3] als Differenz unterschiedlicher Listen

[1,2,3] [1,2,3,4,5] – [4,5][1,2,3] [1,2,3|[bla]] – [bla][1,2,3] [1,2,3] – [ ]

Allgemeinstes Schema

[1,2,3|X] - X

Offene Liste

Rest-Variable(durch UnifikationZugriff auf Inneres der Offenen Liste)

Differenzoperator

[1,2,3]


Differenzlisten II

Listen können leicht in Differenzlisten mit denselbenElementen umgewandelt werden:

[1,2,…] [1,2,…|X] - X

[] X - X

n_stamm_dl([z,e,i,t|X]-X, 1, f, Y-Y)

n_stamm([z,e,i,t], 1, f, []).


append_dl/3

Listen verketten mit Differenzlisten

Laufzeit ist konstantkeine Rekursion, sondern simple Term-Unifikation

append_dl(A-B, B-C, A-C).

A

B

C

A — C

A — B B — C

?- append_dl([1,2|X]-X, [4,5]-[], Z).

?- append_dl([1,2|X]-X, [4,5|Y]-Y, Z).


Anwendung von append_dl/3

A

B

C

D

C — DA — C

A — B B — C

A — D

n_comp_dl(A-D, Flexion, Genus, Fuge-E) :- n_stamm_dl(A-B, _, _, B-C), append_dl(A-B, B-C, A-C), n_stamm_dl(C-D, Flexion, Genus, Fuge-E), append_dl(A-C, C-D, A-D).

?- n_comp_dl([a,r,b,e,i,t,s,z,e,i,t]-[], Flex, Gen, Fuge-E).


n_stamm_dl/4 und n_comp_dl/4

NominalstämmeZeichenfolge

als Differenzliste

Fugenforderung als Differenzliste

Nominalkomposita: n_comp_dl/4i. Zeichenfolge

als Differenzlisteii. Flexionsklasse

iii. Genus

iv. Fugenforderungals Differenzliste

n_stamm_dl([a,r,b,e,i,t|X]-X, 1, f, [s|Y]-Y).n_stamm_dl([z,e,i,t|X]-X, 1, f, Y-Y).n_stamm_dl([b,r,o,t|X]-X, 1, n, Y-Y).n_stamm_dl([p,a,u,s,e|X]-X, 2, f, [n|Y]-Y).



Die beiden Aufrufe von append_dl sind redundant, da alle Variablen schon vorher identisch instantiiert sind.

Deshalb kurz und elegant:


Redundanz von append_dl/4

n_comp_dl(A-D, Flexion, Genus, Fuge-E) :- n_stamm_dl(A-B, _, _, B-C), n_stamm_dl(C-D, Flexion, Genus, Fuge-E).

Morphologie und Buchstabenbäume — 1

Morphologie und Buchstabenbäume

ÜbersichtVollformenMorphologie als Wortgrammatik

Simple DCG als Wortgrammatik: Stämme und Endungen, Flexionsklassen

Schnittstelle zwischen Syntax/Morphologie

Grenzen einfacher konkatenativer MorphologieÜberlegungen zur Effizienz

Tries: BuchstabenbäumeDatenstruktur Buchstabenbäume (tries)

find_word/3: Wörter finden im Buchstabenbaum

find_morph/4: Wortteile finden im BuchstabenbaumStammbäume und Suffixbäume

Konkatenative Morphologie mit Buchstabenbäumen


Motivation

Womit befasst sich die Morphologie?Wortstruktur und Wortbildung!

Flexiontrenn+en, trenn+e, trenn+test, trenn+ten, ge+trenn+t, trenn+end,…

KompositionFruchtbarkeit+s+gott,

Fruchtbarkeit+s+göttinnen+verehrung+s+zeremonie+n+meister,…

DerivationFrucht, frucht+en, frucht+bar, un+frucht+bar, Un+frucht+bar+keit,…

Wie viele Wörter gibt es?der viermillioneneinhunderttausendundzweite Schluck

das In-der-Schlange-Stehen


Vollformen-Lexikon

für jede Wortform alle möglichen Funktionen angeben

lexikalisch, morphosyntaktisch, semantisch, pragmatisch, …

Nachteileimmer unvollständig wegen produktiven Wortbildungenje nach Sprache aufwändiger

lex(kind, n, nom, sg, 'KIND').lex(kindes, n, gen, sg, 'KIND').lex(kinde, n, dat, sg, 'KIND').lex(kind, n, dat, sg, 'KIND').lex(kind, n, akk, sg, 'KIND').lex(kinder, n, nom, pl, 'KIND').lex(kinder, n, gen, pl, 'KIND').lex(kindern, n, dat, pl, 'KIND').lex(kinder, n, akk, pl, 'KIND').

Flexionsformen von »Kind«• für flexionsarmes Englisch machbar

• für flexionsreicheres Deutsch schon anspruchsvoller (pro Substantiv <8 Formen)• für Finnisch problematisch: Finnische Verben haben ~12’000 Formen

Aber: Leistungsfähigere Computersysteme ermöglichen Dinge, die vor wenigen Jahren nicht machbar waren!

Vollformen-Lexikon als Prolog-Datenbank


Morphologie als "Wortgrammatik"

Satzgrammatik = Wörter + syntaktische Kategorien + Verknüpfungsregeln

Wortgrammatik = Morpheme + morphologische Kategorien + Verknüpfungsregeln

Beide "Grammatiken" können im DCG-Formalismus notiert werden…

S

VP

V

bellt

NP

Det

der

N

Hund

N

AffixStamm

Stamm

Kind

Stamm

lied

Affix

er er


DCG: Trennen von Stamm und Endung

n_endung(nom, sg) --> "".n_endung(gen, sg) --> "es".n_endung(dat, sg) --> "".n_endung(dat, sg) --> "e".n_endung(akk, sg) --> "".n_endung(nom, pl) --> "er".n_endung(gen, pl) --> "er".n_endung(dat, pl) --> "ern".n_endung(akk, pl) --> "er".

Nominalendungen

n_stamm(s) --> "kind".n_stamm(s) --> "lied".n_stamm(s) --> "bild".

Nominalstämme

n_morph(Kas, Gen,Num) --> n_stamm(Gen), n_endung(Kas, Num).

Verknüpfungsregel

Das Auftrennen bzw. Zusammenfügen von Stamm und Endung als DCG-Regeln:


Flexionsklassen

n_endung(1, nom, sg) --> "".n_endung(1, gen, sg) --> "es".n_endung(1, dat, sg) --> "".n_endung(1, dat, sg) --> "e".n_endung(1, akk, sg) --> "".n_endung(1, nom, pl) --> "er".n_endung(1, gen, pl) --> "er".n_endung(1, dat, pl) --> "ern".n_endung(1, akk, pl) --> "er".

Nominalendungen Klasse Nr. 1

n_morph(Kas, Gen, Num) --> n_stamm(Klasse, Gen), n_endung(Klasse, Kas, Num).

Verknüpfungsregel

n_stamm(1, s) --> "kind".n_stamm(1, s) --> "lied".n_stamm(1, s) --> "bild".n_stamm(2, s) --> "brot".

Nominalstämme

n_endung(2, nom, sg) --> "".n_endung(2, gen, sg) --> "es".n_endung(2, dat, sg) --> "".n_endung(2, dat, sg) --> "e".n_endung(2, akk, sg) --> "".n_endung(2, nom, pl) --> "e" .n_endung(2, gen, pl) --> "e" .n_endung(2, dat, pl) --> "en" .n_endung(2, akk, pl) --> "e" .

Nominalendungen Klasse Nr. 2

Innerhalb eines Genus können unterschiedliche Flexionsklassen (-paradigmen) auftreten.


Morpheme oder Buchstabenlisten?

Morpheme + Kompositionsregeln?Zwischen zwei " eingeschlossene Zeichenketten stehen für die Liste der Zeichenkodes.Morpheme sind eigentlich Buchstabenlisten.Beim morphologischen Parsen müssen wir gleichzeitig noch Morphemgrenzen erkennen…

?- Kette = "kind".Kette = [107,105,110,100]

Vgl.Unterlagen zu "Ein-

und Ausgabe" im WS

n_stamm(1, s) --> "kind".

n_stamm(1, s) --> [107,105,110,100].

n_stamm(1, s) --> [107],[105],[110],[100].


DCG-Schnittstelle Syntax/Morphologie

Schnittstelle zwischen Syntax und MorphologieSyntax arbeitet mit AtomenMorphologie arbeitet mit Zeichenkodelisten

brotes "brotes"

Umwandlung mit atom_codes/2 (iso) bzw. atom_chars/2 Überführen von Atome zu Listen aus Zeichenkodes und zurück.

?- atom_chars(brotes, Buchstaben).Buchstaben = [98,114,111,116,101,115]?- atom_chars(Wort, [98,114,111,116,101,115]).Wort = brotes

≠


np(Kas, Gen, Num) -->det(Kas, Gen, Num),n(Kas, Gen, Num).

det(nom, s, sg) --> [das].det(nom, s, pl) --> [die].

n(Kas, Gen, Num) --> [Wort],{ atom_chars(Wort, Buchstaben),

phrase(n_morph(Kas, Gen, Num), Buchstaben) }.

?- phrase(np(Kasus, Gen, Numerus), [die, brote]).Kasus = nom, Gen = s, Numerus = pl?- phrase(np(Kasus, Gen, Numerus), [die, broter]).no

DCG-Schnittstelle Syntax/Morphologie

Anfragen

Vgl.Unterlagen zu "DCGs"

im Wintersemester


Grenzen konkatenativer Morphologie

Umlautung im PluralStammänderungen stellen simple konkatenative Ansätze vor konzeptuelle Probleme!Ausweg: Stammmorpheme werden als lexikalische Allomorphe eines Lemmas aufgefasst, die unterschiedliche Numeri ausdrücken können.n_stamm(Klasse, Genus, Numerus, Lemma)

N(?)

Stamm(sg)

haus

Suffix(pl)

er

N(pl)

Stamm(pl)

häus

Suffix(pl)

er

hauser*

häusern_stamm(1, s, sg, 'HAUS') --> "haus".n_stamm(1, s, pl, 'HAUS') --> "häus".n_stamm(1, s, _, 'BILD') --> "bild".n_stamm(2, s, _, 'BROT') --> "brot".

Nominalstämme


n(Kas, Gen, Num, Lemma) --> [Wort],{ atom_chars(Wort, Buchstaben),

phrase(n_morph(Kas, Gen, Num, Lemma), Buchstaben) }.

?- phrase(n(Kas,Gen,Num,Lem), [häuser]).Kas = nom, Gen = s, Num = pl, Lem = 'HAUS' ;Kas = gen, Gen = s, Num = pl, Lem = 'HAUS' ;Kas = akk, Gen = s, Num = pl, Lem = 'HAUS' ;no

Erweiterte Schnittstelle

Komplexe morphologische Kategorientransportieren die gewünschte Information nach Aussengleichen Kongruenz ab n_morph(Kas, Gen, Num, Lemma) -->

n_stamm(Klasse, Gen, Num, Lemma), n_endung(Klasse, Kas, Num).

Verknüpfungsregel


Effizienz

Wie effizient ist diese morphologische Analyse?

Buchstaben-Morphologie mit dem Standard-DCG-Parser

?- phrase(n_stamm(K, G), "kiste").2 2 Call: n_stamm(K,G,[k,i,s,t,e],[]) 3 3 Call: 'C'([k,i,s,t,e],k,R1)3 3 Exit: 'C'([[k,i,s,t,e],k,[i,s,t,e])4 3 Call: 'C'([i,s,t,e],i,R2)4 3 Exit: 'C'([i,s,t,e],i,[s,t,e])5 3 Call: 'C'([ s ,t,e], n,R3)5 3 Fail: 'C'([s,t,e],n,R3)2 2 Fail: n_stamm(K,G,[k,i,s,t,e],[])no

n_stamm(1, s) --> "kind".

n_stamm(1, s, A, B) :- 'C'(A, 107, C), 'C'(C, 105, D), 'C'(D, 110, E), 'C'(E, 100, B).

Geschönter Trace


Effizienz im Grossen

Verhalten bei grossen StammlexikaWas passiert bei der Analyse von "kiste", wenn es tausende Einträge von "aal", "kinn" bis "zinn" gibt?

Überlegungen zum Aufrufverhalten…Bei ausschöpfender Suche eines Stammes S wird jede Stammklausel (n_stamm/4) einmal aufgerufen.'C'/3 wird für jede Stammklausel einmal aufgerufen.Für jeden Buchstaben von jedem Präfix, den Stämme mit S gemeinsam haben, wird 'C'/3 einmal aufgerufen.

Das Programm verhält sich einiges ineffizienter als es sein müsste!


Kompakte Lexika: Letter Trees/Tries

Lexikon als BuchstabenbäumeEine effiziente Methode, Lexikas kompakt zu speichern und buchstabenweise auf die Einträge zuzugreifen, sind Buchstabenbäume (engl. letter tries von letter retrieval)

Buchstabenbäume bestehen auseiner Wurzel mitÄsten, an denen ein Buchstabe und/oder Lexikoneinträge hängen, wobei von den Buchstaben wieder Äste abzweigen können.

Ästevon Buchstabenbäumen sind meist alphabetisch sortiert angeordnet.


Ein englischer Buchstabenbaum

Legende

b

a

r

k

bark

h

e o

l

p

help

p

e

hope

hop

b

bark

Wurzel

Buchstabe

Eintrag


Letter Tree als Prolog-Term

Ein Buchstabenbaum ist rekursiv aus Listen gebaut.Ein Baum ist eine Liste von Ästen.Ein Ast ist entweder ein Lexikoneintrag oder eine Liste der Form [Buchstabe|Baum].

Das Entfernen des Buchstabens aus einem Ast ergibt einen Baum!Richtige Lexikoneinträge müssten natürlich alle nötigen Informationen beinhalten…

ltree([ [b, [a, [r, [k, lex(bark)]]]], [h, [e, [l, [p, lex(help)]]], [o, [p, lex(hop), [e, lex(hope)]]]] ]).


find_word([Char|Chars], Tree, LexEntry) :- member([Char|Subtree], Tree), find_word(Chars, Subtree, LexEntry).

Einfache Suche: find_word/3

find_word/3: ein simples Zugriffsprädikatfind_word(Buchstabenliste, Baum, Eintrag) findet den zur Buchstabenliste L passenden Eintrag E im Baum T

RekursionsschrittSolange L nicht leer ist, finde einen passenden Teilbaum mit dem Anfangsbuchstaben von L und suche darin rekursiv nach dem Rest von L.


Beispiel: Rekursionsschritte

?- ltree(T), find_word([h,o,p], T, lex(I)).

1. Suche [h,o,p] in

2. Suche [o,p] in

3. Suche [p] in

4. Suche [ ] in

[ [b, [a, [r, [k, lex(bark)]]]], [h, [e, [l, [p, lex(help)]]], [o, [p, lex(hop), [e, lex(hope)]]]]]

[ [e, [l, [p, lex(help)]]], [o, [p, lex(hop), [e, lex(hope)]]]]

[ [p, lex(hop), [e, lex(hope)]]]

[ lex(hop), [e, lex(hope)]]


Einfache Suche: find_word/3

AbbruchbedingungWenn L leer ist, suche einen Lexikoneintrag in diesem Ast.

Damit Lexikoneinträge nicht mit Ästen verwechselt werden, müssen sie einen andern Hauptfunktor haben als den Listenkonstruktor '.'/2.

find_word([], Tree, LexEntry) :- member(LexEntry, Tree).

?- find_word([], [lex(hop),[e,lex(hope)]], lex(I)).I = hop ;no


Ein deutscher Stammbaum

Ein StammlexikonDie Lexikoninformationkann beliebig komplexwerden…

b

i

l

d

lex(…)

h

ä

u

s

lex(…)

a

u

s

lex(…)

n_stamm_ltree([[b,[i,[l,[d, n_stamm(1,s,_,'BILD')]]]], [h,[a,[u,[s, n_stamm(1,s,sg,'HAUS')]]], [ä,[u,[s, n_stamm(1,s,pl,'HAUS')]]]]]).


Suche von Stämmen

Um Stämme in Wörtern zu finden, darf nicht die ganze Buchstabenliste konsumiert werden.

Was übrig bleibt, wird als Restliste zurückgegeben.

find_morph([Char|Chars], Tree, LexEntry, Rest ) :- member([Char|Subtree], Tree), find_morph(Chars, Subtree, LexEntry, Rest ).

find_morph( Rest , Tree, LexEntry, Rest ) :- member(LexEntry, Tree).

?- n_stamm_ltree(_T),find_morph([h,ä,u,s,e,r],_T,n_stamm(K,Gen,Num,L), R).

Kla = 1, Gen = s, Num = pl, L = 'HAUS', R = [e,r] ? ;no


Ein deutscher Suffixbaum

Flexionssuffixekönnen ebenfalls als Buchstabenbaum dargestellt werden.sind in eigenen Klassen: n_endlung_ltree(Flexionsklasse, Suffixtree)Leere Morpheme erscheinen direkt auf der Wurzelebene.

n_endung_ltree(1,[n_endung(nom,sg), n_endung(dat,sg), n_endung(akk,sg), [e,n_endung(dat,sg), [r, n_endung(nom, pl), n_endung(gen,pl), n_endung(akk,pl), [n, n_endung(dat,pl)]], [s, n_endung(gen,sg)]]]).


Morphologische Analyse mit Bäumen

Konkatenative morphologische Analyse kann effizient mit Buchstabenbäumen durchgeführt werden.

Zusätzliche Effizienz ist möglich, wenn alphabetische Sortierung bei der Suche berücksichtigt wird.

n_morph(Word, Kas, Gen, Num, Lem) :-n_stamm_ltree(T1),

find_morph(Word, T1, n_stamm(Kla,Gen,Num,Lem), Suffix),n_endung_ltree(Kla, T2),find_morph(Suffix, T2, n_endung(Kas, Num), []).

?- n_morph([h,ä,u,s,e,r], Gen, Kas, Num, Lem).Gen = nom, Kas = s, Lem = 'HAUS', Num = pl ? ;Gen = gen, Kas = s, Lem = 'HAUS', Num = pl ? ;Gen = akk, Kas = s, Lem = 'HAUS', Num = pl ? ;no


Ausblick und Literaturhinweis

Das Konstruieren von Buchstabenbäumenist eine etwas mühsame Arbeit.überlässt man am besten einem Programm, das aus lexikalischen Fakten die entsprechenden Bäume erzeugt.

Literatur zu Morphologie und BuchstabenbäumenCovington, M. (1994): Seiten 263ff.

n_stamm_ltree([[b,[i,[l,[d, n_stamm(1,s,_,'BILD')]]]], [h,[a,[u,[s, n_stamm(1,s,sg,'HAUS')]]], [ä,[u,[s, n_stamm(1,s,pl,'HAUS')]]]]]).

n_stamm(bild,1,s,_,'BILD').n_stamm(haus,1,s,sg,'HAUS').n_stamm(häus,1,s,pl,'HAUS').

Parsen: Left Corner — 1

Left-Corner-Parsing

ÜbersichtParsen von kontextfreien GrammatikenParsing-Strategien

Bottom-Up: datengesteuert

Top-Down: hypothesengesteuert

Left-Corner-Relation (Linke Ecken von Grammatikregeln)Left-Corner-Parsing-AlgorithmusVorteile gegenüber Bottom-Up und Top-Down

Problemregeln

Left-Corner-Parsing mit LinksLeft-Corner-Links berechnen

Links als transitive und reflexive Hülle der Left-Corner-Relation


Reine Parsing-StrategienTop-Down (links-rechts)

Probleme mit links-rekursiven Grammatikregeln (direkt oder indirekt)

Bottom-Up (links-rechts)Probleme mit Tilgungsregeln

Gemischte StrategieTop-Down und Bottom-UpWechsel bei Left-Corner (linker Ecke) der rechten Regelseite

Motivation

X → ε

NP → NP CONJ NP

LHS RHS

Left Corner

S → NP VP


S

VP

V

NP

Det

a

N

man sleeps①

②

③

④

⑤

⑥

⑦

⑧

⑨

Strategie des Bottom-Up-Parsing

➥ datengesteuert

Stack Wortsequenz_ a man sleeps

a man sleeps

Det man sleeps

Det man sleeps

Det N sleeps

NP sleeps

NP sleeps _

NP V _

NP VP _

S _

S → NP VPNP → Det NVP → V

Det → aN → manV → sleeps

Vgl. Folien "Shift-Reduce-Parser"


Strategie des Top-Down-Parsing



S

VP

V

NP

Det

a

N

man sleeps

①

②

③

④

⑤

⑥

⑦

⑧

⑨

➥ hypothesengesteuert

Ziele WortsequenzS a man sleeps

NP VP a man sleeps

Det N VP a man sleeps

a N VP a man sleeps

N VP man sleeps

man VP man sleeps

VP sleeps

V sleeps

sleeps sleeps

— —

Vgl. Folien "DCG" im WS


Das Grammatiksymbol LC ist linke Ecke (left corner) des Grammatiksymbols LHS, gdw. gilt, es gibt eine Grammatikregel

LHS →→→→ LC …

Left-Corner-Relation

S → NP VPNP → Det NVP → VDet → ε

left_corner(np, s).left_corner(det, np).left_corner(v, vp).

LHS RHS

Left Corner

S → NP VP


Left-Corner im Baum

Syntaktische Left-Corner-Relation in jeden TeilbaumMan zeichne…

S

VP

V

NP

Det

a

N

man sleeps




Left-Corner-Algorithmus

Eine Konstituente C left-corner-parsen heisst:

1. Nimm ein Wort von der Eingabe und bestimme seine Kategorie LC

2. Vervollständige LC zu C.a. Abbruchbedingung: Stoppe, falls LC = C ist

(Achtung: Hier ist die Bezeichnung LC ein "falscher Freund". Diese Klausel akzeptiert gerade alle Nicht-Left-Corner-Knoten!)

b. Rekursionsschritti. Finde eine Syntaxregel LHS → LC Sistersii. Left-corner-parse alle Schwester-Kategorien Sisters von LCiii. Vervollständige LHS zu C


S

VP

V

NP

Det

a

N

man sleeps①

②

③

④

⑤

⑥

⑦

⑧

⑨

Strategie des Left-Corner-Parsing

➥ daten- und hypothesengesteuert



Vorgehen beim Left-Corner-Parsing

Um S zu parsen, nimm "a" (1); es ist ein Det (2).

Um Det zu S zu vervollständigen, verwende NP-Regel (3)

NP → Det N und parse N.

Um N zu parsen, nimm "man" (4); es ist ein N (5). N vervollständigt direkt zu N.

Um NP zu S zu vervollständigen, verwende S-Regel (6) S →NP VP und parse VP.

Um VP zu parsen, nimm "sleeps" (7), es ist ein V (8).

Um V zu VP zu vervollständigen, verwende VP-Regel (9) VP → V und parse nichts mehr (keine Schwestern). VP vervollständigt direkt zu VP.

S vervollständigt direkt zu S.


Repräsentation der Eingabekette

Die Eingabekette als Differenzliste Wort: man ⇒ [man,sleeps]-[sleeps]

Phrase: a man ⇒ [a,man,sleeps]-[sleeps]

Satz: a man sleeps ⇒ [a,man,sleeps]-[]

[1,2,3|X] - X

Offene Liste

Rest-Variable(durch UnifikationZugriff auf Inneres der Offenen Liste)

Differenzoperator

[1,2,3]


Repräsentation der Regeln

Trennung von syntaktischen und lexikalischen Regeln

Det → aN → manV → sleepsConj → andAdv → now

word(a, det).word(man, n).word(sleeps, v).word(and, conj).word(now, adv).

rule(s, [np, vp]).rule(np, [det,n]).rule(np, [np, conj, np]).rule(vp, [v, adv]).rule(adv, []).

S → NP VPNP → Det NNP → NP Conj NPVP → V AdvAdv → ε


lcp(Symbol, Eingabekette)Eine Konstituente C left-corner-parsen heisst:

1. Nimm ein Wort von der Eingabe und bestimme seine Kategorie LC

2. Vervollständige LC zur Konstituente C mit dem Rest der Eingabe

lcp/2: Left-Corner-Parsen

lcp(C, [Word|Rest]-RestDiff) :-word(Word, LC),complete(LC, C, Rest-RestDiff).

12


complete/3: Vervollständigen

LC zur Kategorie C vervollständigen, heisst:a. Abbruchbedingung: Stoppe, falls LC = C ist

b. Rekursionsschritt: i. Finde eine Syntaxregel LHS → LC Sistersii. Left-corner-parse alle Schwester-Kategorien Sisters von LC iii. Vervollständige LHS zu C

complete(LC, C, S-Rest) :-rule(LHS, [LC|Sisters]),lcp_sisters(Sisters, S-SistersRest),complete(LHS, C, SistersRest-Rest).

complete(C, C, S-S).

iii

iii


lcp_sisters/2: Kategorien parsen

Eine Liste von Kategorien left-corner-parsen, heisst:Stoppen, falls die Liste leer istrekursiv jedes Element der Liste left-corner-parsen

Rest ist der Teil der Eingabekette, der nach dem Aufruf von lcp_sisters noch zu parsen bleibt, SisterRest der Teil der Eingabekette, der nach dem Aufruf von lcp noch bleibt.

lcp_sisters([], S-S).

lcp_sisters([C|Cs], S-Rest) :-lcp(C, S-SisterRest),lcp_sisters(Cs, SisterRest-Rest).


Bezüglich problematischer RegelnKein Problem mit Linksrekursion!Kein Problem mit Tilgungsregeln der Form (a),falls folgende Klausel zu lcp/2 hinzugefügt wird:

Aber Problem mit Tilgungsregeln der Form (b)Warum? Leere Produktionen an der Left-Corner-Stelle werden bottom-up geparst! Darum schlecht!

Leere Produktionen an andern Stellen werden top-down geparst! Darum kein Problem!

Vorteile von Left-Corner-Parsing

VP → V AdvAdv → ε

NP → NP Conj NP

NP → Det NDet → ε

lcp(C, S-Rest) :-rule(LHS, []),complete(LHS, C, S-Rest). Tilgungsregel der Form (a)

Tilgungsregel der Form (b)


Left-Corner-Links

Linking-Idee: Setze leere Kategorien nur dort ein, wo sie syntaktisch möglich sind!

Ein leerer Plural-Artikel ist ein möglicher Artikel, Beginn einer NP oder Beginn eines Satzes. Aber z.B. kein möglicher Beginn einer VP.Die lc_link/2-Relation hält die Links fest, die an einer Left-Corner-Position möglich sind. S

VP

V

NP

Det N

men sleepε

lc_link(np, s).lc_link(det, np).lc_link(det, s).lc_link(v, vp).

Grammatikspezifische Links



lcp/3: Left-Corner-Parsing mit Links

lcp/3 mit LinkingDer Aufruf von lc_link/2 erzwingt, dass Tilgungsregeln nur zulässig sind zur Bildung von grammatisch zulässigen Konstituenten.

lcp(C, S-Rest) :-rule(LHS, []),lc_link(LHS, C),complete(LHS, C, S-Rest).

lcp(C, [Word|Words]-Rest) :-word(Word, K),complete(K, C, Words-

Rest)


rule(np, [det,n]).rule(det, []).

word(men, n).

lc_link(np, det).

Mini-Grammatik mit Links

Keine unendlichen Suchbäume mehr bei Left-Corner-Tilgungsregeln

Sinnloses Anwenden der Tilgungsregel in der Left-Corner-Position wird verhindertSinnvolles Anwenden wird gestattet

Tilgungsproblem gelöst? Ja!

?- lcp(np, [men]-R).R = [] ? ;no

Anfrage



rule(vp, [v,adv]).rule(adv, []).

word(sleep, v).

lc_link(v, vp).

Mini-Grammatik mit Links

Leider keine Lösungen mehr bei andern Tilgungsregeln!

Ooops! Bisher problemlose Tilgungsregeln werden nicht mehr angewendet!


Tilgungsproblem gelöst? Nein!

?- lcp(vp, [sleep]-R).no

Anfrage


Grund für Nein

Logischer GrundAdv steht zu Adv nicht in der lc_link-Relation

BeobachtungBeim Parsen via lcp_sisters/2 müssen alle Kategorien mit ε-Expansion mit sich selbst gelinkt sein.

AuswegDie Anfrage ?- lc_link(X, X). muss gelingen.

VP

V Adv

sleep ε

1 1 Call: lcp(vp,[sleep]-[]) ? 2 2 Call: word(sleep,K) ? 2 2 Exit: word(sleep,v) ? 3 2 Call: complete(v,vp,[]-[]) ? 4 3 Call: rule(LHS,[v|R]) ? 4 3 Exit: rule(vp,[v,adv]) ? 5 3 Call: lcp_sisters([adv],[]-S1) ? 6 4 Call: lcp(adv,[]-S2) ? 7 5 Call: rule(LHS2,[]) ? 7 5 Exit: rule(adv,[]) ? 8 5 Call: lc_link(adv,adv) ? 8 5 Fail: lc_link(adv,adv) ?



lc_link/2 transitiv und reflexiv!

lc_link(Cat1, Cat2) beinhaltet drei Arten von InformationCat1 steht unmittelbar in der Left-Corner-Relation zu Cat2 oder Cat1 ist mittelbar durch Left-Corner-Relationen mit Cat2 verbunden (transitive Hülle)oder Cat1 und Cat2 sind identisch (reflexive Hülle)

εε

S

VP

V

NP

Det N

men sleep

Adv

lc_link(np, s).lc_link(det, np).lc_link(v, vp).

lc_link(det, s).

lc_link(X, X).

Left-Corner-Relation

Transitive Hülle

Reflexive Hülle


lc_link/2 berechnen

Berechnen von lc_link/2 aus Syntaxregeln

Probleme: Was passiert bei rekursiven Regeln? Wie lassen sich mehrfache gleiche Lösungen verhindern?

lc_link(LC, LHS) :-rule(LHS, [LC|_]). Left-Corner-Relation

Transitive Hüllelc_link(LC, C) :-

rule(LHS, [LC|_]),lc_link(LHS, C).

Reflexive Hüllelc_link(C, C).


Funktionalität und Effizienz

Left-Corner-Parsen mit (LC-)Links erlaubt insbesondere

linksrekursive Regeln

Tilgungsregeln

Damit können LinguistInnen arbeiten!

Effizienteres Left-Corner-Parser durchdirektes Implementieren der Left-Corner-Parsingstrategie (Stichwort BUP)verfeinertes Steuern der Suche


Identische Subkomponenten von GrammatikregelnIn grösseren Grammatiken treten oft gleiche Konstituenten in verschiedenen Regeln auf.

Beim Parsen eines Satzes wie wird die lange NP zweimal vollständig geparst, obwohl sie bei beiden potentiellen Analysen das Gleiche umfasst.

Die Speicherung von Zwischenresultaten (z.B. in einer sog. Chart) kann benutzt werden, um dieselbe Arbeit nicht mehrfach zu leisten.

Effizienz und Backtracking

VP → V NP PPVP → V NP NP

I sent [NPthe very pleasant salesman that I met on holiday in Marbella last year] [NPa postcard]


Literatur

Zum Left-Corner-ParsenCovington, M.(1994: 158ff.)

Unser Kode stammt von dort. Zusätzlich gibt er Beschreibungen des sog. BUP-Algorithmus, der die Regeln noch effizienter repräsentiert

Naumann, S./ Langer H. (1994): Parsing. Eine Einführung in die maschinelle Analyse natürlicher Sprache. Teubner, Stuttgart.

Das (anspruchsvolle) Parsing-Buch auf Deutsch. Unterschiedlichste Parsing-Algorithmen werden vorgestellt, analysiert und in PROLOG und LISP implementiert. Zum Left-Corner-Parser Kapitel 5 (S. 83-100)

Matthews, C.(1998): An Introduction to Natural Language Processing Through Prolog. Longman, London. (S. 220ff)Müller, St.(1998): Prolog und Computerlinguistik: Teil I — Syntax. (S. 78ff.) http://www.dfki.de/~stefan/Pub/prolog.html

Dynamische Prädikate — 1

Dynamische Prädikate

ÜbersichtWissensbasis verändern

Statische vs. dynamische Prozeduren

Deklaration dynamic/1Klauseln hinzufügen

asserta/1, assertz/1

Klauseln entfernenretract/1

Prädikate löschenabolish/1

Klauseln findenclause/2


Wissensbasis verändern

Statische vs. dynamische PrädikateBeim Einlesen eines Programmtexts werden die Prädikats-definitionen in statische Prozeduren (Programm-Stückchen) verwandelt. Diese können später nicht mehr verändert, sondern nur noch aufgerufen (ausgeführt) werden. Das ist effizient!

Dynamische Prozeduren dagegen können während des Programmablaufs gelöscht oder erschaffen werden. Dies entspricht dem Löschen oder Hinzufügen von Klauseln auf der Ebene des Programmtexts. Das ist flexibel!

Im Folgenden wird der Begriff »Klausel« weiterhin zweideutig sowohl für die textuelle Definition als auch für die entsprechende Prozedur verwendet.


dynamic(Funktor/Stelligkeit)Damit eine Prädikatsdefinition zu dynamischen Prozeduren wird, muss sie als dynamisch deklariert sein.

Die Deklaration muss immer vor der ersten Klausel des entsprechenden Prädikats notiert sein.

Guter Programmierstil deklariert auch dynamische Prädikate, für die gar keine textuelle Klausel im Programm vorkommt.

Beim Verarbeiten von :- dynamic( pred/n ). werden alle existierenden Klauseln für pred/n gelöscht.

Mehrfache dynamic-Deklarationen für das gleiche Prädikat haben keinen Effekt.

Als dynamisch deklarieren…

:- dynamic(person/1).

person(klara).person(hans).

Inhalt von Datei: "meier.pl"


Klauseln hinzufügen

asserta(Klausel)fügt Klausel am Anfang der Klauseln des dynamischen Prädikats mit gleichem Funktor und Stelligkeit hinzu.

Falls für das Prädikat noch keine Klauseln existieren, dann gilt es automatisch als dynamisch deklariert.

Wenn für das Prädikat bereits statische Klauseln existieren, gibt es eine Fehlermeldung.

?- consult('meier.pl').yes

?- asserta(person(kevin)).yes

?- person(X).X = kevin ;X = klara ;X = hans ;no

?- asserta(person(gabi)).yes

?- person(X).X = gabi ;...


Klauseln hinzufügen

assertz(Klausel)funktioniert wie asserta/1, fügt aber Klausel am Ende der Klauseln des Prädikats mit gleichem Funktor und Stelligkeit hinzu.

Wie bei asserta/1 kann das Hinzufügen bei Backtracking nicht rückgängig gemacht werden!

Damit kann über Backtracking hinweg gespeichert werden!


?- assertz(person(kevin)).yes

?- person(X).X = klara ;X = hans ;X = kevin ;no

?- asserta(person(gabi)), fail.no

?- person(gabi).yes


Klauseln löschen

retract(Klausel)entfernt die erste unifizierbare Klausel aus der Wissensbasis.

entfernt je eine weitere Klausel beim Backtracking.

Das Löschen wird beim Backtracking nicht rückgängig gemacht!


?- retract(person(hans)).yes

?- person(X).X = klara ;no

?- retract(person(_)), fail.no

?- person(X).no


Prädikate löschen

abolish(Funktor/Stelligkeit) tilgt sämtliche Spuren eines dynamischen Prädikates.

eliminiert auch die Deklaration als dynamisches Prädikat.

ISO-Prolog-Konformität: In SICStus Prolog können so auch statische Prozeduren gelöscht werden.

Kein Wiederherstellen bei Backtracking!


?- person(X).X = klara ;X = hans ;no

?- person(gabi).no

?- abolish(person/1).yes

?- person(gabi).! Existence error in user:person/1! procedure user:person/1 does not exist! goal: user:person(gabi)


Klauseln finden

clause(Kopf, Rumpf) sucht in der Wissensbasis Klauseln dynamischer Prädikate, deren Kopf mit Kopf und deren Rumpf mit Rumpf unifiziert.

Der Rumpf eines Faktums ist true .

Falls kein entsprechendes Prädikat existiert, schlägt clause/2 fehl.


?- clause(person(X), R).X = hans,R = trueyes

?- asserta( ( person(X):- lebt(X) )).yes

?- clause(person(X), R).R = lebt(X)yes

Charts — 1

Charts

ÜbersichtChart bzw. Well-Formed Substring Table (WFST)

Als azyklischer Graph, Tabelle und Relation

KantenbeschriftungenKategorien: WFST

Regeln: Passive ChartsRegelhypothesen: Aktive Charts

Chart-Parsing-VerfahrenInterpretierender Top-Down-Parser

Top-Down mit WFST

Das VollständigkeitsproblemTop-Down mit Vollständigkeitsvermerk

Charts — 2

Motivation

Mehrfachanalysen sind oft unnötig!Die RHS für jede Phrasenstrukturregel (PSR) wird separat berechnet, auch wenn sie z.T. gleiche Konstituenten haben

Wenn sich eine PSR als falsch erweist, 'vergisst' der Parser alles, was er schon erkannt hat, obwohl meist die Teilstruk-turen korrekt analysiert wurden.

Wenn eine Grammatik mehr-deutig ist, werden auch die involvierten Konstituenten immer mehrfach analysiert.

VP

V NP

Det

the

N

catsaw/chased

PP

P NP

Det N

the bone

with

VP → V NPVP → V NP PPNP → Det NNP → NP PP

NP

NP PP

VP

NP PPbzw.

Charts — 3

Frage Wie kann man verhindern, dass bei einer VP wie

und einer Grammatik wie

gemeinsame Bestandteile nicht mehrfach berechnet werden?

AntwortDurch Speichern der Teilkonstituenten in einer Chart bzw. einem Well-Formed Substring Table (WFST).

Grundfrage

VP → V NPVP → V NP PPNP → Det NNP → NP PPPP → P NP

chased the cat with the bone

Charts — 4

Chart als Graph

Visualisieren von Charts als azyklische Graphen Charts sind keine Bäume!

Zwischenpositionen sind Knoten

Terminale und Nicht-Terminale sind beschriftete verbindende Kanten

V

1

chased

2

the

3

cat

4

with

5

the

6

bone

7

Charts — 5

Chart als Tabelle

Charts in TabellenformZwischenpositionen bilden End- und Anfangspunkte.Tabelleneinträge sind die Kanten-beschriftungen.In den Spalten stehen Symbole mit gleichem Endpunkt.In den Zeilen stehen Symbole mit gleichem Anfangspunkt.

In einem Kästchen können mehrere Tabelleneinträge gemacht werden. Z.B. auch nötig bei kategoriell mehrdeutigen Wörtern

2 3 4 5 6 71 v vp vp

2 det np np

3 n

4 p pp

5 det np

6 n

Endpunkte

Anfangspunkte

Charts — 6

edge(Kategorie, Startposition, Endposition)

Chart als edge/3 PrädikatJede Klausel steht für eine Kante.Die Positionen können direkt als Zahlen repräsentiert werden.Falls zwischen zwei Punkten meh-rere Kanten möglich sind, gibt es einfach mehrere Klauseln, die sich nur in der Kategorie unterschei-den.

edge( v, 1, 2).edge( vp, 1, 4).edge( vp, 1, 7).edge(det, 2, 3).edge( np, 2, 4).edge( np, 2, 7).edge( n, 3, 4).edge( p, 4, 5).edge( pp, 4, 7).edge(det, 5, 6).edge( np, 5, 7).edge( n, 6, 7).

Chart als Prolog-Relation

Charts — 7

Position: Numerisch oder differentiell

Die Repräsentation der Positionen als Zahlen oder Dif-ferenzlisten ist äquivalent.

Ob wir eine Differenzliste als 2 Terme oder via Operator '-' verknüpfen ist einerlei…

[the,bone]

5the

6bone

7

[bone] []

edge(det, [the,bone], [bone]).

edge(det, 5, 6).

edge(det, [the,bone], [bone]). edge(det, [the,bone]-[bone]).

Charts — 8

WFST vs. Ableitungsbaum

Aus WFST kann der Ableitungsbaum nicht immer eindeu-tig rekonstruiert werden…

Aus untenstehendem abstrakten WFST allein wird nicht ersichtlich, ob E wegen einer Regel E → A D oder E → C B eingefügt wurde!

A B

DC

E

Charts — 9

Chart mit Regeln

Damit sich Ableitungsbäume aus Charts ablesen lassen, beschrifte jede Kante mit ihrer/n erzeugenden Regel/n!

Solche Kanten heissen auch passive oder inaktive KantenCharts, die aus passiven Kanten bestehen, heissen passive Charts.

Det →→→→ the N →→→→ bone

NP →→→→ Det N

Charts — 10

Chart mit Regelhypothesen

Aktive Kanten drücken Strukturhypothesen ausAktive Kanten zeigen, welche Konstituente analysiert ist, falls zu den bereits analysierten Strukturen noch bestimmte hypothetische (= noch nicht erkannte) Strukturen gefunden werden.Vor dem Punkt: Bereits gefundener TeilNach dem Punkt: Noch fehlender Teil

Charts, die aktive Kanten enthalten, heissen aktive Charts.Siehe Folien "Earley-Parser"

Det →→→→ the . N →→→→ bone .

NP →→→→ Det . N

Eine NP, der noch ein Nzur Vollständigkeit fehlt

Charts — 11

Eine gepunktete Regel (dotted rule) steht für ein Zwischenresultat des Parsers.

Mögliche Parsezustände der Regel S →→→→ NP VPS → . NP VP

Ein Satz wird gesucht, aber es wurde noch nichts erkannt.S → NP . VP

Vom gesuchten Satz wurde die NP, aber noch keine VP erkannt.S → NP VP .

Ein Satz aus NP und VP wurde vollständig erkannt.

Gepunktete Regeln

Charts — 12

Nutzen von Charts

Dank Charts (mit passiven Kanten)wird jede Konstituente nur einmal berechnetverfügen wir über eine einfache Datenstruktur, die alternative Ana-lysen repräsentieren kann.verfügen wir über einen Grad an Robustheit: Auch wenn nicht der ganze Satz analysiert werden kann, werden alle erkennbaren Teil-stücke in die Chart eingetragen.

Dank Charts mit aktiven Kantenwird sowohl das Resultat als auch der Fortschritt des Parsevorgangs einheitlich repräsentiert.kann bei ungrammatischem Input ev. Fehlendes erkannt werden.

Charts — 13

Chart-Parsing-Verfahren

Die Chart ist eine Datenstruktur… und kein bestimmtes Parsing-Verfahren!Es gibt ganz verschiedene Verfahren, die mit einer Chart arbeiten

Top-Down-Chart-Parsing

Bottom-Up-Chart-Parsing

BUP-Parsing (Left-Corner mit Charts)Earley-Algorithmus

… und zahlreiche mehr

Die Verwendung von Charts beim Parsen ist eine wich-tige und weit verbreitete Technik in der Computerlinguis-tik!

Charts — 14

Top-Down-Parser

% parse/2: Parsen einer Kategorie C

parse(C, [Word|S]-S) :- word(C, Word).

parse(C, S-Rest) :- rule(C, RHS), parse_daughters(RHS, S-Rest).

% parse_daughters/2: Parsen einer % Liste von Kategorien

parse_daughters([C|Cs], S-Rest) :- parse(C, S-S1), parse_daughters(Cs, S1-Rest).

parse_daughters([], S-S).

% Phrasen-Struktur-Regeln

rule(s, [np,vp]).%...

% Lexikon

word(d, the).%...

?- parse(vp, [chased,the,cat,with,the,bone]-[]).

Parser Grammatik

Parsen

Charts — 15

Naiver Top-Down-Parser mit WFST

% parse/2: Parsen einer Kategorie C


parse(C, S-Rest) :- edge(C, S, Rest).

parse(C, S-Rest) :- rule(C, RHS), parse_daughters(RHS, S-Rest), asserta(edge(C,S,Rest)) .

% parse_daughters/2: Parsen einer % Liste von Kategorien

parse_daughters([C|Cs], S-Rest) :- parse(C, S-S1), parse_daughters(Cs, S1-Rest).

parse_daughters([], S-S).

% Kanten:- dynamic edge/3.

% Chart saeubernclear_chart :-

retract(edge(_,_,_)),fail.

clear_chart.

?- clear_chart.?- parse(vp, [chased,the,cat,with,the,bone]-[]).

Parser Grammatikwie bisher…

Chart

Parsen

Charts — 16

Probleme des Top-Down-Erkenners

Normales Parsen und Nachschlagen in der Chart konkur-renzieren sich.Vollständigkeit der Chart ist unsicher! Weil…

Unsichere positive Information: Fehlt die Konstituente in der Chart, weil sie noch nicht analysiert wurde?Unsichere negative Information: Fehlt die Konstituente in der Chart, weil sie gar nie erscheinen kann?

AuswegHalte die Vollständigkeit der Charteinträge einer Kategorie für eine Eingabekette explizit fest, nachdem alle möglichen Konstituenten dieser Kategorie analysiert sind.

Charts — 17

:- dynamic complete/2.


parse(C, S-Rest) :- complete(C, S), !, edge(C, S, Rest).

parse(C, S-Rest) :- rule(C, RHS), parse_daughters(RHS, S- S1), asserta(edge(C, S, S1)), S1 = Rest .

parse(C,S-_) :- asserta(complete(C,S)), fail.

Vollständigkeitsvermerk

Das dynamische Prädikat complete/2 vermerkt Vollständigkeit.

Falls eine Konstituente ab Position nicht voll-ständig ist, ignoriere Chart. Falls Information vollständig ist bzgl. Kategorie und Position, aber trotzdem kein Chart-Eintrag existiert, dann scheitere hier endgültig (Cut!).

Suche alle Konstituenten C beliebiger Länge und füge sie in die Chart ein, aber gelinge nur bei der gesuchten Länge.

Falls via Klausel 3 keine Konstituente mehr gefunden wurde, d.h. alle positive Information in die Chart eingefügt ist, hat dies negative Infor-mation ergeben. C ist ab dieser Position voll-ständig geparst.

2

3

4

2

3

4

Charts — 18

Literatur

Zu Charts und Chart-ParsingCovington, M.(1994: 167ff.): Natural Language Processing for PROLOG Programmers.

Unser Kode stammt von dort.

Naumann, S./ Langer H. (1994): Parsing. Eine Einführung in die maschinelle Analyse natürlicher Sprache. Teubner, Stuttgart. Müller, St. (1998: 84ff.): Prolog und Computerlinguistik: Teil I — Syntax. Gazdar, G./Mellish, Ch. (1989: 179ff.): Natural Language Process-ing in PROLOG.

Earley-Parsing — 1

Earley-Parsing

ÜbersichtAktives Chart-Parsing für kontextfreie GrammatikenEigenschaften von Earleys VerfahrenEinzelne Komponenten

Initialisierung

Predictor

ScannerCompleter

Implementation in PrologEnde und Resultat der Analyse


Eigenschaften I

Von Jay Earley wurde 1970 ein Chart-Parsing-Verfahren für kontextfreie Grammatiken vorgestellt. Es…

parst Sätze mit n Wörtern im schlechtesten Fall in einer Zeit proportional zu n3 — Verfahren gehört zur Komplexitätsklasse O(n3)kommt mit den häufig problematischen Regeln zurecht.

linksrekursive Regeln (direkt oder indirekt)Tilgungsregeln (Code siehe Übungen)

verwendet eine aktive Chart.benützt eine gemischte Analysestrategie

von links nach rechts

top-down und bottom-up


Eigenschaften II

Der Earley-Algorithmusverfolgt jeweils für eine Satzposition alle syntaktischen Alternativen gleichzeitig.hat am Ende des Parsings sämtliche alternativen Syntaxanalysen in der Chart.ist leicht in imperativen Programmiersprachen (C, Java etc.) zu implementieren.ist nützlich und wichtig bei praktischen Anwendungender Computerlinguistik.erhielt seit 1970 zahlreiche Verbesserungsvorschläge gegenüber Earleys Original-Verfahren.


Earley-Algorithmus

Das Verfahren von Earley besteht im wesentlichen aus drei Komponenten

Predictor: Schlägt passende aktive Kanten vor.Scanner: Akzeptiert Wörter der Eingabekette.Completer: Versucht aktive Kanten zu vervollständigen, d.h. passiv zu machen.

Nach der Initialisierung werden diese drei Komponenten für jeden Knoten in der Chart aufgerufen,

jeweils solange, bis keine neuen Kanten mehr hinzukommen.


Beispiel-Grammatik

Folgende Phrasenstruktur-Grammatik mit Lexikon sei vorausgesetzt:

linguistische Motivation für links-rekursive Grammatikregeln

NP

ConjNP

DetP N

woman

NP

DetP N

man

and

Det

a

Det

a

NP

DetP N

NP

Det

the

N

king

Poss

’s

crown

S → NP VP

NP → NP Conj NPNP → DetP N

DetP → Det

DetP → NP Poss

Syntax

Det → a | theN → man | woman |…V → sleeps | chases |…Conj → andPoss → 's

Lexikon

rule(s, [np,vp]).rule(np, [np,conj,np])....

word(det, the).word(det, a)....


Die Chart

1

NP →→→→ . DetP N

2

DetP →→→→ Det .

NP →→→→ DetP . N

edge(1, 1, np, [], [detp,n]).edge(1, 2, np, [detp], [n]).edge(1, 2, detp, [det], []).Zwischen Position 1 und 2 ist eine (unvollständige)

NP, von der bereits die DetP gefunden wurde, der aberzur Vollständigkeit noch ein N fehlt.


<1,2> NP →→→→ DetP . N

edge(From, To, C, RC, SC)Dynamische edge/5-Fakten speichern aktive und passive Kanten

1. From: Startposition

2. To: Endposition

3. C: Kategorie4. RC: Liste der erkannten Kategorien

(Aus technischen Gründen in umgekehrter Reihenfolge.)

5. SC: Liste der noch zu erkennende Kategorien


Charteinträge einfügen

store/1: Einfügen von KantenIdentische Kanten dürfen nicht mehrfach in die Chart eingetragen werden, sonst gäbe es unerwünschte Mehrfachlösungen.Eine Kante wird gespeichert, d.h. der Chart hinzugefügt, falls sie nicht schon gespeichert ist.

Falls call(Edge) scheitert, wird Edge assertiert.

Falls call(Edge) gelingt, wird Edge nicht assertiert.

:- dynamic edge/5.

store(Edge) :-\+ call(Edge),asserta(Edge).


Einen Satz earley-parsen heisst,1. Chart löschen2. Chart bezüglich Startsymbol initialisieren3. von den 3 Komponenten verarbeiten lassen4. prüfen, ob in der Chart eine passive Kante

mit dem Startsymbol zu finden ist

Von den 3 Komponenten verarbeiten lassen heisst,Abbruch, falls Eingabekette leer ist.Rekursives Abarbeiten durch

1. Predictor2. Scanner3. Completer

und wieder von vorn, ein Wort weiter.

Gerüst des Earley-Algorithmus

parse(C, S) :- retractall(edge(_,_,_,_,_)), init(C), process(S, 1, LastPos), edge(1, LastPos, C, _, []).

process([], LastPos, LastPos).process([Word|Words], Pos, LastPos) :- predictor(Pos), scanner(Word, Pos, NextPos), completer(NextPos), process(Words, NextPos, LastPos).


Legende zur Metasymbolik

Metasymbole für einzelne Nicht-TerminalsymboleA, B, C

Metasymbole für beliebig lange Ketten von Grammatik-symbolen

α, β, γDie Kette kann auch leer sein! D.H. ε.

BeispieleDie gepunktete Regel S → . NP VP ist von der Form A → . α, gdw.

A = S und α = NP VP.

Die gepunktete Regel NP → NP . Conj NP ist von der Form C → α . B γ , gdw.C = NP, α = NP, B = Conj und γ = NP.

Die gepunktete Regel NP → NP Conj . NP ist von der Form C → α . B γ , gdw.C = NP, α = NP Conj, B = NP und γ = ε.


Initialisierung der Chart

init(C) :- foreach( rule(C, RHS), store(edge(1,1,C,[],RHS)) ).

1S →→→→ . NP VP

1

edge(1, 1, s, [], [np,vp]).

init/1 fügt für jede Regel mit dem Startsymbol als LHS eine aktive Kante ein.Initialisierungsregel

Falls C die gesuchte Kategorie ist, füge für jede Grammatikregel der Form C → γ die Kante ⟨ 1, 1 ⟩ C → . γ in die Chart.


foreach/2

Deterministisches Metaprädikatforeach(B, A)

So oft die Bedingung B erfüllt ist,führe die Aktion A genau einmal durch.

B und A können durch gemeinsame Variablen kommunizieren.

Verwendet once/1 als Hilfsprädikat.

Emuliert Iteration (while-Schlaufe).

once(Ziel)Beweise Ziel höchstens einmal.

foreach(B, A) :-call(B),once(A),fail.

foreach(_, _) :-true.

once(Goal) :-call(Goal),!.


Predictor-Beschreibung

S →→→→ . NP VP

Der Predictor sagt voraus, welche Grammatikregeln zum Ziel führen können.

Aktive Konstituenten werden expandiertDie aktive Konstituente steht direkt hinter dem Punkt.

Vorgehensweise des Predictors: Top-Down

Prediktorregel für die Position kSchritt I: Für jede Kante der Form ⟨ i,k ⟩ C → α . B γ und jede Regel der Form B → β, füge eine Kante ⟨k,k ⟩ B → . β ein.

Schritt II: Wende die Prediktorregel auf das Resultat ihrer eigenen Anwendung an.


Predictor-Regel graphisch

Falls i < k:

Falls i=k:

B →→→→ . ββββ

ki

C →→→→ αααα . B γγγγ

ki


C →→→→ αααα . B γγγγ B →→→→ . ββββ

k


k

B → β

Predictor

B → β

Predictor


Predictor: Beispiel Schritt I

1

1S →→→→ . NP VP

2NP →→→→ . NP Conj NP

3NP →→→→ . DetP N

1

1S →→→→ . NP VP

Regeln für NP

NP → NP Conj NP

NP → DetP N

Predictor für Position 1Weil eine aktive Kante an Position 1 die aktive Konstituente NP hat, werden anhand der NP-Regeln Kanten in die Chart eingefügt.Da unsere Grammatik zwei Regeln für NPs enthält, werdenentsprechend zwei aktive Kanten eingefügt.


Predictor: Beispiel Schritt II

1

1S →→→→ . NP VP



Regeln für NP1

1S →→→→ . NP VP



Predictor für Position 1Die frisch eingefügte Kante 2 hat wiederum eine NP als aktive Konstituente.

Daher sollen anhand der NP-Regeln neue Kanten in die Chart eingefügt werden.

Allerdings kommen so keine neuen Kanten in die Chart, da alle aktiven Kanten für NPs schon drin sind!

Keine endlose Rekursion, trotz linksrekursiver Grammatik!


Predictor: Beispiel Schritt II

Predictor für Position1, Schritt IIDie frisch eingefügte Kante Nr. 3 hat eine DetP als aktive Konstituente.

Daher sollen anhand der DetP-Regeln neue Kanten in die Chart eingefügt werden.

Die Grammatik enthält zwei Regeln für DetP, also kommen zwei neue aktive Kanten zur Chart hinzu.

Dann ist für den Predictor nichts mehr zu tun.

1

1S →→→→ . NP VP



4DetP →→→→ . NP Poss

5DetP →→→→ . Det

1

1S →→→→ . NP VP



Regeln für DetP


predict(C, Pos) :- rule(C, [Active2|Rest]), store(edge(Pos,Pos,C,[],[Active2|Rest])), predict(Active2, Pos), fail.

predict(_, _).

Predictor in Prolog

predictor/1Mache für jede Kante mit einer aktiven Konstituente an der Endposition die Voraussagen.

predict/2Schritt I: Finde eine Regel, die die vorherzusagende Kategorie als LHS hat, merke die linke Ecke als neue aktive Konstituente. Speichere die entsprechende Kante in der Chart, oder scheitere, falls sie schon gespeichert ist.

Schritt II: Wende predict/2 rekursiv auf die neue aktive Konstituente an.

predictor(To) :- foreach( edge(_, To, _, _, [Active|_]), predict(Active, To) ).


Scanner-Beschreibung

N → manN → woman

word(n, man).word(n, woman)....

Der Scanner nimmt Terminal-Symbole und bestimmt ihre lexikalischen Kategorien.

könnte z.B. Schnittstelle zu Lexikon/Morphologie aufrufenHier: Aufruf des spartanischen Lexikons in word/2

Scanner-Regel für Position kFalls das Wort W zwischen der Position k und k+1 der Eingabekette steht, füge für jede Lexikon-Regel der Form C → W die Kante ⟨ k, k+1⟩ C → W. in die Chart.


Scanner: Beispiel

Chart(-Ausschnitt) nach Laufen des Scanners für Knoten 1:

1

1S →→→→ . NP VP





2

6Det →→→→ the .


Scanner in Prolog

scanner(+Wort, +K, ?Kplus1)Für jede mögliche Kategorie, wird eine Kante mit der entsprechenden Endposition gespeichert.

Scanner bekommt das Wort von process/3 geliefert.Verbesserung gegenüber der Original-Version von Earley:

Earley hätte Präterminal-Regeln wie Det → the vom Predictor top-down verarbeiten lassen. Weil damit Terminale vorausgesagt werden, die gar nicht Teil der Eingabekette sind, ist das ineffizient — wie beim Standard-DCG-Parser.

scanner(Word, From, To) :- To is From + 1, foreach( word(Cat, Word), store(edge(From,To,Cat,[Word],[])) ).


Completer-Beschreibung

Der Completer vervollständigt aktive Kanten durch Kombination mit passiven Kanten.

Anschaulich: Der Punkt wandert in der Regel eine Kategorie nach rechts.Vorgehensweise des Completers: Bottom-Up

Completer-Regel für Position kSchritt I: Für jede passive Kante der Form ⟨ j, k ⟩ B → β .... und jede aktive Kante der Form ⟨ i, j⟩ C → α . B γ füge die Kante ⟨ i, k⟩ C → α B . γ zur Chart hinzu. (sog. Fundamentalregel)

Schritt II: Wende die Completer-Regel auf das Resultat ihrer eigenen Anwendung an.


Fundamental-Regel des Chart-Parsing


kji

NP →→→→ Det N .

N →→→→ cat .


kji

N →→→→ cat .

Wenn folgende Kanten in der Chart sind:Passive Kante zwischen Positionen j und k:

B → β . d.h. N → cat .Aktive Kante zwischen Positionen i und j:

C → α . B γ d.h. NP → Det . N

Dann füge folgende Kante zur Chart hinzu:Aktive oder passive Kante zwischen Positionen i und k:

C → α B . γ d.h. NP → Det N .


Completer: Beispiel

Completer für Position 2, Schritt IPassive Kante 6 endet in Position 2. Ihre Kategorie ist Det.

Suche aktive Kanten,

die ein Det benötigenund am Startknoten der passiven Kante enden (Position 1).

Kante 5 passt.

Füge durch Fundamentalregel die neue Kante (7) in die Chart.

1

1S →→→→ . NP VP





2

6Det →→→→ the .

1

1S →→→→ . NP VP





2

Det →→→→ the .6

DetP →→→→ Det .7


Completer: Beispiel

Completer für Position 2, Schritt IIPassive Kante 7 endet hier. Ihre Kategorie ist DetP.

Suche aktive Kanten,

die ein DetP benötigenund am Startknoten der passiven Kante enden (Position I)

Kante 3 passt

füge durch Fundamentalregel neue Kante (8) zur Chart.

1


2

7


1


2

7


8


Ausschnitt


Completer in Prolog

completer/1Vervollständige die Chart mit jeder passiven Kante, die bei Position K endet und bei J beginnt.

complete/3Schritt I: Suche aktive Kante, die bei J endet und Kategorie B benötigt. Wende die Fundamentalregel an und speichere die neue Kante. Schritt II: Falls sich bei Schritt I eine passive Kante ergeben hat, vervollständige diese rekursiv.

Achtung: Die erkannten Konstituenten sind verkehrt herum abgespeichert…

completer(K) :- foreach( edge(J, K, Passive, _, []),

complete(J, K, Passive) ).

complete(J, K, B) :- edge(I, J, A, Aphla, [B|Gamma]), store(edge(I,K,A,[B|Aphla],Gamma)), Gamma == [], complete(I, K, A), fail.

complete(_, _, _).


Analyse: Fortschritt und Ende

FortschrittWenn der Completer für Knoten 2 nicht mehr weiterkommt …

Predictor für Knoten 2 — Scanner für Knoten 2Completer für Knoten 3 — Predictor für Knoten 3 — Scanner für Knoten 3Completer für Knoten 4 — …

EndeWenn die Eingabekette leer ist und alle Kanten vervollständigt sind, ist die syntaktische Analyse beendet

Ergebnis der AnalyseDie Eingabe-Kette ist genau dann akzeptiert, wenn gilt:

I. eine passive Kante reicht von der ersten bis zur letzten PositionII. und die Kategorie dieser Kante ist das Startsymbol.


Literatur

OriginalaufsatzEarley, Jay(1970): An efficient context-free parsing-algorithm. Communications of the ACM, 14, pp. 453-60. Reprinted in "Readings in Natural Language Processing (B. J. Gross, K. Spark et al. eds), pp. 25-33, Morgan Kaufmann: Los Altos, 1986.

Implementationnahe bei Covington, M. (1994: 176ff.)aber beeinflusst von Gazdar, G./ Mellish, Ch. (1989: 179ff.): Natural Language Processing in PROLOG

Charts: Subsumption — 1

Charts: Subsumption

ÜbersichtKomplexe Grammatik-Kategorien mit Variablen

sprengen den Rahmen der kontextfreien Sprachen!

bringen deshalb zusätzliche Komplexität ein!

FallunterscheidungWo bringen variable Argumente von komplexen Grammatik-Kategorien Probleme?

Lösung: Term-Subsumption statt Term-UnifikationTerm-Subsumption in Prolog: subsumes_chk/2Kanten-Subsumption

Top-Down-WFST-ParserEarley-Parser


Einfügen von Kanten mit atomaren SymbolenEine Kante mit Kategorie np sei in der Chart.Der Parser will eine Kante mit np einfügen.Kante wird nicht eingefügt, da beide Terme unifizierbar sind.

Das ist richtig so.Es ist bereits eine NP gefunden worden.

Fall I: Atomare Symbole

np

np✗


Fall II: Instantiierter komplexer Term

Einfügen von Kanten mit komplexen Kategorien, aber ohne Variablen

Eine Kante mit der komplexen Kategorie np(singular) sei in der Chart.Der Parser will eine Kante mit np(singular) einfügen.Kante wird nicht eingefügt, da beide Terme unifizierbar sind

Das ist richtig so.Es ist ja bereits eine Singular-NP gefunden worden

np(sg)

np(sg)✗


Fall III: Komplexer Term mit Variable

Einfügen von Kanten mit komplexen Kategorien und Var-iablen

Eine Kante mit Kategorie np(X) sei in der Chart.Der Parser will eine Kante mit np(singular) einfügen.Kante wird nicht eingefügt, da beide Terme unifizierbar sind.

Das ist richtig so.Singular-NPs sind ein Spezialfall von (allgemeinen) NPs.Dass eine Singular-NP gefunden wurde, ist nichts Neues! np(X)

np(sg)✗


Einfügen von Kanten mit komplexen Kategorien mit Var-iablen

Eine Kante mit »Kategorie« np(sg) sei in der Chart.Der Parser will eine Kante mit np(X) einfügen.Kante wird nicht eingefügt, da beide Terme unifizierbar sind.

Das ist falsch!X könnte ja auch für Plural pl stehen.

Fall IV: Komplexer Term mit Variable

np(sg)

np(X) ✗np(sg)

np(X) ✔


Unifikation und Allgemeinheit

Eine neue Kante gilt als "bereits gefunden", wenn es eine Kante in der Chart gibt,

die mit der neuen Kante unifizierbar ist unddie mindestens so allgemein ist wie die neue Kante.

Ein Term A ist mindestens so allgemein wie B, falls gilt:A subsumiert B.

In Chart neue Kante neue Kante ignorieren?

f(X) f(X) ja

f(X) f(a) ja

f(a) f(X) nein


Ein Term A subsumiert einen Term B gdw. giltA und B sind unifizierbar undin B werden dabei keine Variablen instantiiert, bzw. höchstens alle Vorkommen einer Variable umbenannt.

Beispielef(X,b) subsumiert f(a,b)f(X,X) subsumiert f(Y,Y)f(a,b) subsumiert nicht f(X,b)f(a,b) subsumiert nicht f(b,a)f(X,X) subsumiert nicht f(X,Y)

Term-Subsumption


Term-Subsumption in Prolog

Das Prolog-Prädikat subsumes_chk(A, B) gelingt, falls Term A den Term B subsumiert.

In SICStus Prolog in der Term-Bibliothek vordefiniert.Für beliebige Prologs siehe Covington (1994:174-5)

Wichtig: Es werden keine Variablen gebunden in den Termen!

:- use_module(library(terms)).

?- subsumes_chk(f(X), f(X)).true ?

?- subsumes_chk(f(X), f(a)).true ?

?- subsumes_chk(f(a), f(X)) .no


WFST und Subsumptions-Check

parse(C, S-Rest) :-complete(C0, S),subsumes_chk(C0, C), % C0 subsumiert C!,C0 = C, % C0 unifiziert mit Cedge(C, S, Rest).

Im Top-Down WFST-Parser (Folien "Charts")Nur 2. Klausel von complete/2 modifizieren.Nur die Kategorie muss auf Subsumption überprüft werden.Nur auf die Chart zurückgreifen, wenn dort eine vollständige Kate-gorie vorliegt, die die gesuchte Kategorie subsumiert!


Aktive Chart und Kanten-Subsumption

Ignoriere neue Kante E, wenn eine andere Kante C bereits in der Chart ist, die folgende Bedingungen erfüllt:

Startposition von C = Startposition von EEndposition von C = Endposition von E

Die Kategorie von C subsumiert die Kategorie von E.

Der Teil vor dem Punkt von C subsumiert den Teil vor dem Punkt von E.Der Teil nach dem Punkt von C subsumiert den Teil nach dem Punkt von E.

E → αΕ . βΕ

C → αC . βCsubsumierti j


Earley-Parser mit Subsumptions-Check

store(edge(From, To, Cat, Found, ToFind)) :- \+ (edge(From, To, ChartCat, ChartFound, ChartToFind), subsumes_chk(ChartCat, Cat), subsumes_chk(ChartFound, Found), subsumes_chk(ChartToFind, ToFind)), asserta(edge(From, To, Cat, Found, ToFind)).

Im Earley-Parser ändert sich das Prädikat zur Kantens-peicherung.

Ein potientieller Charteintrag muss mit allen bestehenden Einträge mit identischer Spannweite abgecheckt werden.Kategorie, Gefundenes und Gesuchtes müssen subsumieren!


Ausblick

EffizienzDie vorgestellten Verfahren von Chart-Parsing mit dynamischen Prädikaten für die Chart sind nicht effizient!Subsumptions-Checks sind aufwändig, aber oft unnötig!

KorrektheitBei rekursiven Grammatiken kann Nicht-Termination entstehen, wenn ein variables Argument der Mutterkategorie in einer Unter-struktur einer Tochterkategorie vorkommt:

c(X) → α c(f(X) βAusweg beim Earley-Parser: Grammatikspezifische Restriktionen beim Vorhersagen von Kanten (Covington:1994:186ff.)

Merkmalstrukturen — 1

Merkmalstrukturen

ÜbersichtMerkmalstrukturen

Einfach

Komplex

DarstellungsformenKästchenGerichteter Graph

Gleichungssystem von Pfaden

Pfadekoreferente Pfade

Unifikation von MerkmalstrukturenRekursive Definition der Unifikation


Einfache Merkmalstrukturen

Kasus nominativGenus femininNumerus plural

Merkmal »Kasus«

Wert des Merkmals»Numerus«

Bestandteile einer Merkmalstruktur (feature structure)Merkmale/Attribute (features/attributes)Werte (values): immer atomar bei einfachen Merkmalstrukturen


Verschachtelte Merkmalstrukturen

Eine kompliziertere MerkmalstrukturDer Wert des Merkmals »Syntax« ist komplex und selbst wiederumeine Merkmalstruktur: Verschachtelte Struktur.


Merkmal »Syntax«

Wert des Merkmals»Syntax«

Syntax

Semantik …


Pfade

Ketten von Merkmalen heissen Pfad (path)Wert des Pfades »Syntax.Kasus«= Wert des Merkmals »Kasus« im Wert des Merkmals »Syntax«


Merkmal »Syntax«

Wert des Pfades»Syntax.Kasus«

Syntax

Semantik …

Merkmal »Kasus« im Wert desMerkmals »Syntax«


Merkmalstruktur als Graph

Merkmalstrukturen als gerichteter GraphPfade werden bildlich zu Pfaden im GraphMerkmal sind beschriftete KantenAtomare Werte sind beschriftete KnotenKomplexe Wert sind unbeschriftete Knoten

1

2

Syntax

...Semantik

nominativKasus

femininGenus

plural

Numerus


Merkmalstruktur als partielle Funktion

Für jeden Pfad enthält eine Merkmalstruktur höchstens einen Wert.

Damit ist eine Merkmalstruktur eine partielle Funktion, die Pfade zu Werten abbildet.Mindestens in dieser Einführung …Alternativen

Formalisierungen, wo immer ein Wert gefordert ist (totale Funktion) oder auch mehr als ein Wert zulässig wäre (Relation).

Formalisierungen, wo die Abbildung »unscharf« ist: »Mit einer Wahrscheinlichkeit von 80% ist der Kasus Nominativ«

Pfad → Wert


Werte von Pfaden

Wert von Syntax ist komplexe Merkmalstruktur

Wert von Syntax.Kasus ist nominativ

Wert von Syntax.Genus ist feminin

Wert von Syntax.Numerus ist pluralWert von Syntax.Tempus ist nicht definiert

Wert von Semantik ist die leere Merkmalstruktur


Syntax

Semantik


Unzulässige Merkmalstruktur

a bb da cMerkmal »a« besitzt

unterschiedliche Werte

Beispiel für eine unzulässige MerkmalstrukturEs darf keine Merkmale mit unterschiedlichen Werten geben!

Sonst wäre die Merkmal-Wert-Beziehung eine Relation und keine (partielle) Funkti-on!


Koreferente Pfade

Koreferente Pfade besitzen denselben Wert. Sie…beschreiben ein Gleichungssystem.sind wie die Variablen von Prolog.

Müssen immer denselben Wert haben (auch bei Unifikation)

werden oft als Nummer innerhalb eines Kästchens notiert.

a pb qc

1

1

k 2

m 2

Wert(k.a) = pWert(k.b)= qWert(k.c) = Wert(k.a)Wert(m) = Wert(k)

Wert(k.c) = pWert(m.a)= p…

Koreferenz als indizierteKästchen

Koreferenz als gemeinsameEndknoten im Graphen

Koreferenz als Gleichungs-system

1 2

k

m

pa

c

q

b


Unifikation von Merkmalstrukturen

Merkmalstrukturen können unifiziert werdenUm zwei Merkmalstrukturen zu unifizieren, unifiziere die Werte aller MerkmaleWenn ein Merkmal nur in einer der beiden Strukturen vorkommt

kopiere das Merkmal (zusammen mit seinem Wert) in die resultierende Struktur

Wenn ein Merkmal in beiden Strukturen vorkommt, unifiziere die beiden Werte

beides Atome: Wenn die beiden Atome gleich sind, ist das Ergebnis eben dieses; sind sie verschieden, schlägt die Unifikation fehlbeides Merkmalstrukturen: Unifikation der Strukturen (Rekursion!)

ein Atom, eine Merkmalstruktur: Unifikation schlägt fehl



Kasus nominativNumerus plural

Syntax Genus femininKasus nominativ

Syntax

Kasus nominativNumerus pluralGenus feminin

Syntax


1

Kasus nominativNumerus

SyntaxSubjekt

NumerusSyntaxPrädikat

plural

Wortlaut Kinder



SyntaxSubjekt

1

Kasus nominativNumerus

SyntaxSubjekt

1NumerusSyntaxPrädikatWortlaut Kinder

1



Kasus nominativNumerus pluralSyntax

Genus femininKasus dativSyntax

Diese Merkmalstrukturen sind nicht unifizierbar!Weil im rekursiven Schritt beim Unifizieren des Werts von »Syntax«, die Werte von »Kasus« nicht unifizierbar sind.Bei komplizierten Strukturen kann die Unifikation »tief innen« fehl-schlagen.


Literatur

Merkmalstrukturen und UnifikationMüller, Stefan(1998): Prolog und Computerlinguistik Teil I. Kapitel 10: Einführung in die Unifikation.

Frei verfügbar unter: http://www.dfki.de/~stefan/Pub/prolog.html

Covington, M.(1994: Kapitel 5.3)Jurafsky, D. (2000: Kapitel 11.4)Gazdar,G. (1989: Kapitel 7)

Merkmalstrukturen in PROLOG — 1

Merkmalstrukturen in PROLOG

ÜbersichtMerkmalstruktur- vs. Termunifikation

Normale Terme

Normale Listen: nicht destruktive Unifikation

Merkmalstrukturen als offene Listendestruktive Unifikation

Merkmalstrukturen als TermschemataÜbersetzungsrelationen

GULP von M. CovingtonÄussere und Innere Repräsentation

Verwendung

Literatur


Motivation

Merkmalstrukturbasierte GrammatikformalismenUnifikationsgrammatiken zur Beschreibung der Syntax, Lexikons und anderer Ebenen der Sprache

Lexikalisch-Funktionale Grammatik (LFG)

Generalisierte Phrasenstruktur-Grammatik (GPSG)

Unifikationsbasierte Varianten der KategorialgrammatikKopf-getriebene Phrasenstruktur-Grammatik (HPSG)

PATR I-II für Syntax, DATR für Lexikon

ComputerlinguistikEntwicklungsumgebungen/Formalismen für Unifikationsgrammatiken

ALE, GULP, YAP, PATR, ProFIT und viele andere

Vgl. Vorlesung "Formale

Grammatiken und Syntaxanalyse"


Term vs. Merkmalstruktur

Jeder (Prolog-)Term kann als Merkmalstruktur kodiert werden.

In HPSG sieht man hin und wieder etwa folgende Listen…

Leider ist es nicht so einfach, Merkmalstrukturen sinnvoll und effizient als Prolog-Terme zu kodieren…

functor farg1 aarg2 b

f(a,b)

first brest nil

first

rest

a

[a,b]


Term- vs. Merkmalstruktur-Unifikation

Merkmalstrukturen und komplexe Prolog-Terme haben unterschiedliche Unifikation

Prolog-Terme haben fixe Anzahl Unterterme und fixe ReihenfolgeMerkmalstrukturen haben freie Anzahl Unterstrukturen und freie Reihenfolge

Keine direkte Strukturähnlichkeit!

Genus femininKasus dativ

Syntax Kasus dativNumerus plural

Syntax

(syntax(genus(feminin),kasus(dativ)))

(syntax(kasus(dativ),numerus(plural)))


Term- vs. Merkmalstruktur-Unifikation

Merkmalstrukturen und Prolog-Listen haben unterschiedliche Unifikation

Prolog-Listen haben freie Anzahl Elemente, aber fixe ReihenfolgeMerkmalstrukturen haben freie Anzahl Unterstrukturen und freie Reihenfolge

ineffiziente Merkmalstrukturunifikation mit Listen ist relativ leicht möglich



Syntax

[syntax:[genus:feminin,kasus:dativ]]

[syntax:[kasus:dativ, numerus:plural]]


Merkmalstrukturen als offene Listen

Manchmal erlauben komplexere Datenstrukturen einfachere Algorithmen…

Merkmalstrukturen werden durch offene Listen repräsentiertUnifikation von Merkmalstrukturen wird merklich einfacher…

[num:sg,pers:3|_]

Offene Liste

Num sgPers 3


Syntax[syntax:[kasus:nominativ, numerus:sg|_]|_]


Destruktive Unifikation

unify_fs/2 erlaubt destruktive Unifikation von Merkmalstrukturen als offene Listen

Die 1. Klausel erledigt die Fälle, wo Termunifikation korrekt istatomare Werte oder variable Werte (bei koreferenten Pfaden)

Die 2. Klausel macht die eigentliche Merkmalstrukturunifikationdoppelte Rekursion und geschicktes Ausnützen von select/3

vorhandene bzw. fehlende Merkmal-Wert-Paare werden abgeglichen

unify_fs(FS, FS) :- !.unify_fs([F:V1|Rest1], FS) :-

select(FS, F:V2, Rest2),unify_fs(V1, V2),unif y fs ( Rest1 , Rest2 ) .


?- select([num:sg,pers:3|_], pers:3, Rest).Rest = [num:sg|_A] ? yes

Auswählen von Elementen

select(L1, E, L2) ist wahr, falls die Liste L1 gleich L2 ist, wobei das 1. Auftreten von Element E entfernt istbeim Aufruf mit offenen Listen wird E dank Unifikation in L1 eingefügt, wenn es nicht vorhanden ist!

select([X|Tail], X, Tail):- !.select([Head|Tail], Elem, [Head|Rest]) :-

select(Tail, Elem, Rest).

?- FS = [num:sg|_], select(FS, pers:3, Rest).FS = [num:sg,pers:3|_A],Rest = [num:sg|_A] ? yes


Nicht widerspruchsfrei unifizierbare Merkmalstrukturenkorrektes Scheitern dank der 1. Klausel von unify_fs/2

Semantisch nicht wohlgeformte Merkmalstrukturen führen selbstverständlich zu problematischem Verhalten (von Reihenfolge der Merkmale abhängig)

Korrektes Scheitern der Unifikation

?- unify_fs([a:b|_],[a:c|_]). 1 1 Call: unify_fs([a:b|_84],[a:c|_112]) ? 2 2 Call: select([a:c|_112],a:_1063,_1067) ? 2 2 Exit: select([a:c|_112],a:c,_112) ? 3 2 Call: unify_fs(b,c) ? 3 2 Fail: unify_fs(b,c) ? 1 1 Fail: unify_fs([a:b|_84],[a:c|_112]) ? no

?- unify_fs([a:b,a:c|_],[a:b|_]). 1 1 Call: unify_fs([a:b,a:c|_323],[a:b|_351]) ? 1 1 Exit: unify_fs([a:b,a:c|_323],[a:b,a:c|_323]) ? yes


Merkmalstrukturen als Termschemata

Term-Unifikation ist möglich, wenn Merkmalstrukturen in ein fixes Schema übersetzt werden!

Verschachtelte fs/n-Funktoren: Wert von "Syntax" ist 1. Argument, Wert von "Genus" inneres 1. Argument usw.

Einfacher, wenn für jede Sorte von Merkmalstrukturen festgelegt ist, welche Merkmale sie maximal haben kann. (getypte Merkmalstrukturen)



Syntax

fs(fs(feminin,_,dativ)) fs(fs(_,plural,dativ))

translate(syntax, FS, fs(FS).translate(genus, Gen, fs(fs(Gen,_,_)).translate(numerus, Num, fs(fs(_,Num,_)).translate(kasus, Kas, fs(fs(_,_,Kas)).


Merkmalstrukturen als Termschemata

Merkmalstrukturen als Prolog-Terme mit festzugewiesenen ArgumentstellenVorteile

normale Prolog-Term-Unifikation verwendbarsehr effizient

Nachteilemühsam zum EingebenTerme völlig unleserlich fürs menschliche Auge

AuswegTrennung von innerer und äusserer Repräsentation


Automatische Übersetzung

Direkte Term-Unifikation von Merkmalstrukturen dankautomatischer Übersetzung:

beim Einlesen der Grammatik leserliche Ausdrücke → Prolog-Terme

beim Ausgeben der Ergebnisse Prolog-Terme → leserliche Ausdrücke

Ein Beispiel für eine solche Übersetzung ist Graph Unification Logic Programming (GULP) von M. Covington

term(syntax:(genus:feminin..kasus:dativ))


Syntax

term(g__([_,_,g_(g__([g_(feminin),g_(dativ)|_]))|_])).


Konstruktoren von GULP

Konkrete Syntax von GULPAls Trenner von Merkmal und Wert wird der Infix-Operator :/2 (xfy 600) verwendet.Merkmal-Wert-Paare werden mit dem Infix-Operator ../2 (xfy 602) zusammengefügt.

Kasus nominativNumerus pluralGenus feminin

Syntax

(syntax: (kasus:nominativ

..numerus:plural

..genus:feminin))

Kästchen-Notation GULP-Notation


GULP-Integration

Zuerst muss GULP konsultiert werden

Danach können beliebige Prolog-Dateien mit Merkmalstrukturen verarbeitet werden.

?- consult('gulp.pl').

Die Verwendung von :/2 mit der automatischen

Übersetzung der Merkmalstrukturen führt in

SICStus Prolog manchmal zu Konflikten mit dem

Modulsystem. Insbesondere mit der emacs-

Schnittstelle. Deshalb verwenden wir hier eine

modifizierte Version, die mit dem Operator ::/2

arbeitet.

s --> np(case::nom..num::N), vp(num::N).

np(num::N) --> d(num::N), n(num::N).np(num::N..case::C) --> pronoun(num::N..case::C).

vp(num::N) --> v(subcat::1..num::N).vp(num::N) --> v(subcat::2..num::N), np(case::acc).

v(num::sg..subcat::1) --> [barks].v(num::pl..subcat::1) --> [bark].

d(_) --> [the].d(num::pl) --> [two].

pronoun(num::sg..case::acc) --> [him]....


Literatur zu GULP

GULP 3.1Michael A. Covington (1994): GULP 3.1: An Extension of Prolog for Unification-Based Grammar. Research Report AI-1994-06. Artificial Intelligence Center. The University of GeorgiaDokumentation zur Implementation und Anwendung von GULP 3.1

Mini-GulpMichael A. Covington(1994): Natural Language Processing for Prolog Programmers. Prentice-Hall. (130-140)Gut verständliche Erklärung zu einer vereinfachten Version von GULP.

URL: http://www.ai.uga.edu/~mc/#PROLOG


Literatur

Unifikationsbasierte GrammatikenShieber, Stuart M.: An Introduction to Unification-Based Approaches to Grammar. CSLI Lecture Notes, vol. 4. Center for the Study of Language and Information: Palo Alto, 1986.

gute Einführung in praktische linguistische Anwendungen von Merkmalstrukturen

bespricht den Einsatz von Merkmalstukturen in den damals gebräuchlichenlinguistischen Theorienempfehlenswert, auch wenn das Buch etwas an der Oberfläche bleibt

FormalismenEine Suchanfrage zu den Akronymen im Internet…

Grammatikentwicklung — 1

Grammatikentwicklung

ÜbersichtGrammatikbruchstücke für das EnglischeKongruenz

Merkmalübereinstimmung in Numerus und weitere Kategorien

Rektion/ValenzMerkmalsbestimmung und Subkategorisierung

Komplexe Merkmale in der komplexeren PraxisVerbalkomplexeSatzfragen

Ergänzungsfragen

Leere Kategorien verwalten


Kongruenz

Definition »Übereinstimmung zwischen zwei oder mehreren Satzelementen hinsichtlich ihrer morpho-syntaktischen Kategorien (Kasus, Person, Numerus, Genus).«

nach Bussmann, H. (1990): Lexikon der Sprachwissenschaft

Kongruenz (Agreement) lässt sich in Grammatikregeln mit Prolog einfach durch Variablengleichheit ausdrücken.


Kongruenzen in Numerus zwischenNomen und ihren Determinatoren

Nominalphrasen als Subjekt und dem finiten Verb

Nominalphrasen und Reflexivpronomen

zwischen Gleichsetzungsnominativen (predicate nominal)

...

np(num:N) --> det(num:N), n(num:N).

Kongruenz I

s --> np(num:N), vp(num:N).

vp(num:N) --> v(subcat:refl..num:N), np(pron:refl..num:N).

vp(num:N) --> v(subcat:pred..num:N), np(num:N).


Kongruenzphänomene mit weiteren KategorienPerson

zwischen finitem Verb und Subjekt

Kasuszwischen konjunktiv verknüpfte Nominalphrasen

Genuszwischen Possessivpronomen und seinem Bezugsnomen

Kongruenz II

He likes soccer.

The kids hate him and her most.

Shei likes heri programming style.


Rektion/Valenz

DefinitionRektion — »Lexemspezifische Eigenschaften von Verben, Adjektiven, Präpositionen oder Substantiven, die morphologische Kategorie (insbesondere den Kasus) abhängiger Elemente zu bestimmen.«

»Rektion kann unter Valenz subsumiert werden, insofern Valenzträger die morphologische Form der von ihnen 'regierten' (=abhängigen) Elemente bestimmen ('regieren').«

»Valenz ist die Fähigkeit eines Lexems, seine syntaktische Umgebung vorzustrukturieren, in dem es anderen Konstituenten im Satz Bedingungen bezüglich ihrer grammatischen Eigenschaften auferlegt.«

nach Bussmann, H. (1990): Lexikon der Sprachwissenschaft

Rektion/Valenz wird durch Merkmalspezifikation ausgedrückt Verben gleicher Valenz werden oft in Subkategorien aufgeteilt.


Finitheit und Valenz

Finite Vollverben fordern Subjekt im Nominativ

Vollverben fordern je nach Subkategorie Objekte

Finite Formen eines Verbs

s --> np(cas:nom),vp(vform:fin).

vp(vform:VF) --> v(vform:VF..subcat:1), np(cas:acc).

v(vform:fin..subcat:1) --> [take].v(vform:fin..subcat:1) --> [takes].v(vform:fin..subcat:1) --> [took].

Aus Gründen der

Übersichtlichkeit sind

nicht alle morpho-

syntaktischen Merkmale

aufgefüht.


Hilfsverben

Verbalkomplexe

Mit Hilfsverben (do,be,have), Modalverben (can, may,...) und Passivbildung durch be entstehen viele Möglichkeiten.

takes has taken is taking could have taken has been taken has been taking could have been taking

»The sherpa the wrong route.«


Rektion im Verbalkomplex

Modalverben fordern Grundformen (base)

Hilfsverb have fordert Partizip Perfekt (past partciple)

Ein Partizip Perfekt

aux(vform:fin..gov:bse) --> [could].

aux(vform:bse..gov:pastpart) --> [have].

v(vform:pastpart..subcat:1) --> [taken].


Bau des Verbalkomplexes

Verbalphrase mit Hilfsverben

vp(vform:VF) --> aux(vform:VF..gov:Required), vp(vform:Required).

VP vform: fin

VP vform:bse

AUX vform:bse gov:pastpart

AUX vform:fin gov:bse

havecould

VPvform:pastpart

V vform:pastpart subcat:1

taken

NP

the route


Satzstellung bei Ja-Nein-Fragen

Ja-Nein-Fragen involvieren Subjekt-Hilfsverb-Inversion

Das Hilfsverb steht vor dem Subjekt.

Lexikoneinträge

s_inv --> aux(vform:fin..gov:Required), np(cas:nom),

vp(vform:Required).

»Is the sherpa taking the wrong route?«

aux(vform:fin..gov:partpres) --> [is].

v(vform:partpres..subcat:1) --> [taking].


Satzstellung bei Ergänzungsfragen

Bei Subjektfragen ersetzt das Fragewort das Subjekt

Lexikoneintrag

Bei Objektfragen verändert sich die Verbalphrase

Nach dem Fragewort erscheint eine Subjekt-Hilfsverb-Inversion-Konstruktion, der das Objekt fehlt.

»Who is taking the wrong route?«

s_quest --> wh_pro(case:nom), vp(vform:fin).

wh_pron(cas:nom) --> [who].

»Whati is he taking ei ?«


Lückenforderungen

Eine Objekt-Fragewort fordert eine Subjekt-Hilfsverb-Inversion mit einer Lücke (gap) in der Verbalphrase

Revidierte Subjekt-Hilfsverb-Inversion

Lückeninformation verarbeiten

s_quest --> wh_pro(_), s_inv(vform:fin..gap:np).

s_inv(vform:VF..gap:Gap) --> aux(vform:VF..gov:Required),np(case:nom..gap:no), vp(vform:Required..gap:Gap).

vp(vform:VF..gap:G) --> v(vform:VF..subcat:1),np(cas:acc..gap:G).

np(num:N..gap:no) --> det(num:N), n(num:N).np(gap:np) --> [].

Vgl. ECL I: Gap-Threading

First-Argument-Indexing — 1

% lex_v(Lemma, Hilfsverb, Subcat)lex_v(aalen, haben, [akk]).%... 6000 weitere Klauselnlex(züngeln, haben, []).

First-Argument-Indexing

Effizienteres BeweisenDer Interpreter muss bei jedem Beweisschritt feststellen, welcher Klauselkopf mit einem Ziel unifiziert.Naives Vorgehen

Interpreter probiert der Reihe nach alle Klauseln eines Prädikats durch. Je mehr Klauseln ein Prädikat hat, umso aufwändiger wird das Durchprobieren.

Effizienteres Vorgehen mit First-Argument-IndexingHauptfunktor des 1. Arguments des Prädikats wird als Index verwendet, mit dem die passenden Klauseln direkt angesprungen werden können.

Das Abspeichern der Klauseln wird etwas aufwändiger, dafür ist der Aufwand beim Suchen eines Klauselkopfs nicht mehr abhängig von der Anzahl Klauseln eines Prädi-kats!


Die Bibliotheksmetapher

Die Bibliothek als WissensbasisEine Bibliothek besteht aus Büchern, ein Programm besteht aus Prädikaten.Ein Buch enthält Textabschnitte, ein Prädikat enthält Klauseln.

Indexgestütztes NachschlagenIn Büchern mit einem Index (Stichwortregister) kann ich gezielt Textab-schnitte nachschlagen ohne das ganze Buch zu lesen. In Programmen mit First-Argument-indizierten Klauseln kann der Interpreter Klauseln nach-schlagen ohne die ganze Prädikatsdefinition zu durchsuchen.

AdressierungStichwortregister adressieren typischerweise Seitenzahlen oder Kapitel. First-Argument-Indizes adressieren die entsprechenden Speicherstellen durch Anwendung einer Hash-Funktion auf den Hauptfunktor.


Instantiierung und Reihenfolge

1. Argument als InputargumentDamit aus dem Hauptfunktor die Speicherstelle berechnet werden kann, muss er beim Aufruf eines Ziels instantiiert sein!Vermeide Output-Argumente an erster Argumentsposition: Inpu-targumente sollten immer vor Output-Argumenten erscheinen.

Bei Prädikaten ohne eindeutige Input-/Output-Zuordnung an die Argumente müssen allenfalls 2 Hilfsprädikate definiert werden, die First-Argument-optimiert sind.

1. Argument als FallunterscheidungDie Fallunterscheidung von Klauseln sollte möglichst durch Haup-tfunktoren im Klauselkopf ausgedrückt werden.Vermeide catch-all-Klauseln: Klauseln, deren 1. Argument eine Variable ist, sollten möglichst vermieden werden.


reverse(List, Rev) :-reverse(List, [], Rev).

reverse([], Akku, Akku).reverse([X|Rest], Akku, Rev) :-

reverse(Rest, [X|Akku], Rev).

?- length(_L, 20000), time(reverse(_L, _LR)).Elapsed time: 67 ms

reverse2(List, Rev) :-reverse2(Rev, List, []).

reverse2(Akku,[], Akku).reverse2(Rev, [X|Rest], Akku) :-

reverse2(Rev, Rest, [X|Akku]).

?- length(_L, 20000), time(reverse2(_L, _LR)).Elapsed time: 100 ms

Beispiel: Effizienzgewinn

Standardreihenfolge von ArgumentenEin 1. Argument, das mit instantiiertem und fallunterscheidendem Hauptfunktor aufgerufen wird, optimiert ein Programm messbar.

admin

Last-Call-Optimization — 1

Last-Call-Optimization

Effizienteres BeweisenDer Interpreter muss bei jedem Aufruf eines Prädikats ein sog. Stack Frame im Speicher erstellen. Über dieses Stack Frame werden die Instantiierungen der Variablen des Prädikataufrufs verwaltet.Der verschachtelte Aufruf von rekursiven Prädikaten führt schnell zu einer Vielzahl von Stack Frames.

Für jedes Element in der Liste wird ein Stack Frame angelegt bei list_length/2!

Naives VorgehenDas Stack Frame bleibt bestehen, bis die allerletzte Lösung des Aufrufs berechnet wurde.

list_length([], 0).list_length([_|Rest], N) :-

list_length(Rest, M),N is M + 1.


Effizienteres Vorgehen

Last-Call-OptimizationDas Stack Frame mit den lokal benötigten Datenstrukturen eines Prädikats P

P :- R1,…, Rn

kann vor dem letzten Unteraufruf Rn (last call) freigegeben wer-

den, falls gilt:Es gibt keine weitere Klausel für P.Es gibt keine Entscheidungspunkte für die Unteraufrufe R1,...,Rn-1.


Last-Call-Optimization ermöglichen

Um Last-Call-Optimierung nicht bloss in der letzten Klau-sel zu ermöglichen:

Nütze First-Argument-Indexing aus: Prolog erkennt so, dass auch andere als die letzte Klausel Last-Call-optimierbar sind. Ein Cut vor dem letzten Aufruf in einer Klausel ermöglicht immer Last-Call-Optimierung.

Der Cut kostet allerdings auch wieder etwas Zeit!

Mache Prädikate möglichst endrekursiv! D.H. der rekursive Aufruf kommt in der letzten Klausel als letzter Aufruf.

Um Rechtsrekursion (oder Endrekursion) zu erhalten, muss manchmal ein Akkumu-lator eingeführt werden, der Zwischenresultate speichert!

P :- R1,…, !, Rn


Endrekursion dank AkkumulatorDamit Last-Call-Optimierung auf den rekursiven Aufruf möglich wird, speichert ein zusätzliches Argument die Anzahl bisher ange-troffener Elemente.

Dieses Prädikat braucht weniger Speicher, da dasselbe Stack Frame für alle rekursiven Aufrufe verwendbar ist.

list_length_accu(List, Length) :-list_length_accu(List, 0, Length).

list_length_accu([], Accu, Accu).list_length_accu([_|Rest, Accu, N) :-

NewAccu is Accu + 1,list_length_accu(Rest, NewAccu, N).

Listenlänge mit Endrekursion

Documents

Programmiertechniken in der Computerlinguistik II · Endliche Automaten, Morphologie, Lexikon, Syntaxanalyse, Merkmalstrukturen Weiterf hrendere und effiziente Programmiertechniken