Partielles Parsing mit kaskadierten endlichen Automatenkontext.fraunhofer.de/haenelt/kurs/Referate/Dolata_Regner_PartiellesParsingAbney.pdf · Einführung Partielles Parsing mit Kaskaden

EinführungPartielles Parsing mit Kaskaden

EvaluationZusammenfassung

Literatur

Partielles Parsing mit kaskadierten endlichenAutomaten

Der Ansatz von Steven Abney

Referierende: Franziska Regner Mateusz DolataRuprecht-Karls-Universität Heidelberg

Hauptseminar: Endliche AutomatenDozentin: PD Dr. Karin Haenelt

22. Juni 2009

Franziska Regner, Mateusz Dolata Partielles Parsing mit kaskadierten endlichen Automaten



Literatur

1 EinführungVollständiges und Partielles ParsingPartielles Parsing

2 Partielles Parsing mit KaskadenGrundlagen des Ansatzes von AbneyBeispiel - GrundlagenFeaturesBeispiel - Extended Features

3 Evaluation

4 Zusammenfassung




Literatur

Vollständiges und Partielles ParsingPartielles Parsing

Vollständiges Parsing vs. Partielles Parsing

Vollständige Parser Partielle Parservollständige und tiefe Analyse Verzicht auf vollständige und tie-

fe Analyse

closed-world-assumption bezüg-lich der Grammatik und des Lexi-kons

open-world-assumption

nur auf ausgewählte, wohlge-formte Texte anwendbar

akzeptieren auch nicht wohlge-formte Texte

die Grammatiken erzeugen am-bige Analysen

eindeutige Analyse von Phrasen

zu langsam für Massendatenver-arbeitung




Literatur


Partielles Parsing

Das Ziel partiellen Parsings besteht darin, syntaktischeInformation zuverlässig aus einem nicht wohlgeformten Texteffizient zu extrahieren unter Verlust von Vollständigkeit und Tiefeder Analyse.

Es werden Teilstrukturen erkannt, die zuverlässig nach wenigensyntaktischen Kriterien erkannt werden können.

Beispiel: Chunking.




Literatur


Chunking

(Jurafsky and Martin, 2008, Seite 451)

„ Chunking is the process of identyfying and classyfying the flat,non-overlapping segments of a sentence that constitute the basicnon-recursive phrases corresponding to the major parts-of-speechfound in most widecoverage grammars. This set typically includesnoun phrases, verb phrases, adjective phrases, and prepositionalphrases; in other words, the phrases that correspond tocontent-bearing parts-of-speech. “




Literatur


Beispiel für partielles ParsingFidditch parser (Hindle, 1983)

deterministisch - kein Backtracking, keine parallele Analyse

in einen endlichen Automaten umwandelbar

„Punt“ als die Lösung für unerkannte Elemente.

Punt

Phrasen denen keine syntaktische Rolle zugewiesen werdenkann oder bei denen die Rollenzuweisung zu Ambiguitäten führtwerden übersprungen

Dadurch entstehen unabhängige Teilbäume




Literatur


Beispiel für partielles Parsing (Fidditch)

Abney (1996b, Seite 10)




Literatur

Grundlagen des Ansatzes von AbneyBeispiel - GrundlagenFeaturesBeispiel - Extended Features

Grundlagen des Ansatzes von Abney




Literatur


Prinzipien des Ansatzes von Abney

Eine Kaskade besteht aus der Sequenz mehreren Ebenen.Phrasen einer Ebene bauen auf den Phrasen der vorherigenEbene auf.Die unerkannten Elemente werden durch „Punt“ an die nächsteEbene übergeben.Die Analyse von Abney beginnt mit der Ebene der Chunks undreicht je nach Komplexität der Grammatik bis zur Ebene dersimplex clauses

chunks

non-recursive cores (NX, VX) of major phrases (NP, VP)

simplex clauses

embedded clauses as siblings




Literatur


Vorgehensweise im Ansatz von Abney

Jede Transduktion ist definiert durch Kategorien und reguläreAusdrücke.

Reguläre Ausdrücke werden in endliche Automaten überführt.

Die Transduktoren zwischen Ebenen entstehen durchVereinigung der Automaten, die für reguläre Ausdrücke erzeugtwurden.

In diesen Transduktoren ist jeder Endzustand mit einer Kategorieverbunden.




Literatur


Beispiel Grammatik

:chunkNP -> D? N+ | Pron;VP -> V-tns | Aux V-ing;

:ppPP -> P NP;

:clauseS -> PP* NP PP* VP PP*;

5

1

6 2

3

4

D N

N

Pron

AuxV − ing

V − tns N

31 2P NP

31 2NP VP

PP PP PP




Literatur


Erzeugen eines level transducer

NP -> D? N+ | Pron; VP -> V-tns | Aux V-ing;

1

2

3

4 NP

NP

D N

NN

Pron

1

2

3

VP

AuxV − ing

V − tns

1

5

2

3

6

4

VP

NP

NP

AuxV − ing

V − tns

D N

NN

Pron




Literatur


Kaskaden - theoretische Grundlagen

Jede Ebene besteht aus einer oder mehreren Grammatikregeln.

Pattern sind verlässliche Indikatoren für syntaktische Strukturen




Literatur


Schlüsselkonzepteeasy-first parsing

easy-first parsing (Abney, 1996a, Seite 3)

Es findet kein systematischer bottom-up Aufbau eines Parsebaumsstatt, sondern es werden nur die Features erkannt, die erkannt werdenkönnen. Werden Markierungen für Phrasen einer höheren Ebenezuverlässig erkannt, so können unsichere Strukturen inZwischenebenen mit dem Ausdruck „ANY*“ übersprungen werden unddie Verarbeitung kann gleich mit den Phrasen der höheren Ebenenfortgeführt werden.




Literatur


Schlüsselkonzeptecontainment of ambiguity

containment of ambiguity (Abney, 1996a, Seite 3)

Es werden Grammatiken verwendet, die keine ambigenRepräsentationen zulassen. Präpositionale Phrasen und ähnlicheStrukturen werden nicht angehängt an die Satzstruktur.Nomen-Nomen Modifikationen (z.B. fruit-flies) werden nicht aufgelöst.




Literatur


Schlüsselkonzepteislands of certainty

islands of certainty (Abney, 1996a, Seite 3)

Islands of certainty sind mit Sicherheit erkannte Strukturen. Siewachsen zu immer größeren Phrasen zusammen.




Literatur


Input-Datei

the dwoman nin pthe dlab ncoat nthought v-tnsyou nwere auxsleeping v-ing




Literatur


Output-Format

[S[NP

[D the][N woman]]

[PP[P in][NP

[D the][N lab][N coat]]]

[VP[V-tns thought]]]

[S[NP

[N you]][VP

[Aux were]

[V-ing sleeping]]




Literatur


Grammatik-Ebene 1(Chunks, L1) und Transduktion T1 (L0:L1)

[NP the woman][P in] :chunk[NP the lab coat] NP -> D? N+ | Pron;[VP thought] VP -> V-tns | Aux V-ing;[NP you][VP were sleeping]




Literatur


Grammatik-Ebene 2(PP, L2) und Transduktion T2 (L1:L2)

[NP the woman][PP in the lab coat] :pp[VP thought] PP -> P NP;[NP you][VP were sleeping]




Literatur


Grammatik-Ebene 3(Clause, L3) und Transduktion T3 (L2:L3)

Quelle: Abney (1996a, Seite 2)

[S the woman in the lab coatthought]

:clause

[S you were sleeping] S -> PP* NP PP* VP PP*;




Literatur


Das Durchlaufen der Transduktoren für die Transduktion von EbeneLi−1 zu Ebene Li , und Transduktoren zur Erzeugung vonAktionsmuster auf einer Ebene Li erfolgt nacheinander.




Literatur


Features

Um die syntaktische, lexikalische und morphologischeInformation beim Parsing zu erfassen, werden features (Actions)eingeführt.

Die Information kann sowohl aus dem Lexikon als auch aus demAufbau der Grammatikregeln stammen.

Attributwerte (feature values) werden vererbt.

Bedingung, die Abney an die Erweiterung seines Programmesdurch Features stellt: Nur geringe Verschlechterung der Effizienz.

Die Einführung der Features stellt eine Erweiterung desGrundkonzeptes dar.




Literatur


Attributtypen

String – Zuweisung von Variablen zu Strings. Sind mehrereKinder vorhanden, dann wird der Wert des letzten Kindes vererbt.

Phrase – Zuweisung von Variablen zu Phrasen. Der Wert zeigtauf das Kind, jedoch nicht auf den Wert des Kindes.

Subset – Spezifizierung von Wörtern und/oder Phrasen. DerWert des Kindes wird mit dem Wert der Mutter „unifiziert“




Literatur


Beispiel für Phrasen und Rollen

Input Grammatik

the D phrase d;big A phrase h;bad Abear N :nplikes V NP -> d=D? A* h=Nberries N




Literatur


Automat für NP → D? A* N

1 2

3

A

D

N

N

A




Literatur


Transducer für NP -> d=D? A* h=N

1 2

3

4

5

ε : h =

A : ε

ε : d =

ε : h =

N : ε

D : ε

A : ε




Literatur


Output für Phrasen und Rolen

ohne Actions

[NP[D the][A big][A bad][N bear]]

[V likes][NP

[N berries]]

mit Actions

[NPd=[D the]

[A big][A bad]

h=[N bear]][V likes][NPh=[N berries]]




Literatur


Beispiel für String und field modifier

Input Grammatik

those d that string h, field 1;big a big string lem, field 3;bad a badbears n bear :nplumbered v lumber np -> d? a* lem=h=n;by p by




Literatur


Output für String und field modifier

ohne Actions

[np[d those][a big][a bad][n bears]]

[v lumbered][p by]

mit Actions

[np h=bears lem=bear[d h=those lem=that those][a h=big lem=big big][a h=bad lem=bad bad][n h=bears lem=bear bears]]

[v h=lumbered lem=lumber lumbered][p h=by lem=by by]




Literatur


Beispiel für Subsets

Input Grammatik

der D n|g|d subset c, range {n g d a};treue AHans N a|n :npisst V NP -> c=D? A* c=N;Spaetzle N n|agern Adv




Literatur


Output für Subsets

ohne Actions

[NP[D der][A treue][N Hans]]

[V isst][NP

[N Spaetzle]][Adv gern]

mit Actions

[NP c=n][D c=n|g|d der][A c=n|g|d|a treue][N c=n|a Hans]]

[V c=n|g|d|a isst][NP c=n|a

[N c=n|a Spaetzle]][Adv c=n|g|d|a gern]




Literatur


Internal Transducer

Subj → [NP n=D? n=[N1 A* n=N]] V

Quelle: Abney (28.04.1997, Seite 14)




Literatur

Evaluation der Geschwindigkeit

Komplexität: n x |levels| (3 < |levels| < 10)→ 100 Wörter, 10 Ebenen → O(1000)

1600 Wörter/Sekunde mit einer 9-Ebenen Grammatik auf einerSparcstation ELC(33 MHz).

1300 w/s mit 9 Ebenen auf einer Sparcstation 1(20 MHz).

ungefähr 2/3 schneller mit 2 Ebenen als mit 9 Ebenen.




Literatur

Evaluation der Geschwindigkeitdurchgeführt von Steven Abney (1996)

Vollständige Parser <1w/sTacitus 0.12w/s

„Skimming“ Parser 20-50w/sFastus 23w/sScisor 30w/sClarit 50w/s

Deterministische ParserCG 410w/s

Fidditch 1200w/sCass2 1300-2300w/sCopsy 2700w/s




Literatur

Evaluation der Genauigkeit Accuracy

Die Evaluation der Genauigkeit Accuracy durch Steven Abneyund Marc Light erfolgte anhand der entsprechend markiertenKorpuspositionen.Korpuspositionen wurden zufällig ausgewählt, die dann sowohleinmal von Abney als einmal von Light handschriftlich annotiertwurden.

Von der Korpusposition beginnend wurde die Kategorie und derEndpunkt des Chunks markiert, falls er vorhanden war.Erlaubt Übereinstimmungen zwischen Steven Abneys bzw.zwischen Marc Lights Beurteilungen und dem Parser feststellenzu können.Die Kennzeichnung von Abney und Light erlaubt es die interjudgereliability abschätzen zu können.

Die Ergebnisse des Tests zeigen, dass der Unterschied zwischender menschlichen Leistung und der des Parsers nur gering ist.




Literatur

Evaluation der Genauigkeitdurchgeführt von Steven Abney und Marc Light (1996)

cass2 marcsample size N 1000

answers in common X 921 934chunks in tst t 390 381chunks in std s 394

chunks in common x 343 348per-word accuracy X/N 92.1 ± 1.7% 93.4 ± 1.5%

precision x/t 87.9 ± 3.2% 91.3 ± 2.8%

recall x/s 87.1 ± 3.3% 88.3 ± 3.2%

per-word accuracy = Prozent der korrekten AntwortenPrecision und recall berücksichtigen nur die Teilproben, dietatsächlich einen Chunk im Test oder im Standard enthalten.Der Plus-minus Betrag stellt ein 95% Konfidenzintervall, das einenormale Abschätzung zum Binomial benutzt, dar.




Literatur

Vorteile

Schnelligkeit→ Partielles Parsing→ benutzt deterministische Automaten→ keine Rekursion sondern Iteration

Genauigkeit→ Finite State Cascades

Parsen von nicht wohlgeformten Texten möglich→ Punting→ Islands of Certainty→ Easy-First Parsing




Literatur

Vorteile

Eindeutige Analyse von Phrasen→ Containment of Ambiguity→ longest Match

Platzeffizient→ komprimierte Darstellung der Daten

einfache Systementwicklung und Instandhaltung→ Modularkonstruktion und automatische Kompilierung vonSystemkomponenten




Literatur

Nachteile

keine vollständige Analyse

keine tiefe Analyse




Literatur

Zusammenfassung

nicht alle Phänomene natürlicher Sprache können mit Cassmodelliert werden

viele tatsächlich vorkommende Phänomene können mit regulärenHilfsmitteln beschrieben werden

nicht alle Anwendungen brauchen eine vollständige und tiefeAnalyse

Best case der Laufzeitkomplexität ist linear(mit niedrigemnon-Determinismus)




Literatur

Danke

Wir bedanken uns sehr herzlich für die Aufmerksamkeit.




Literatur

Steven Abney. Partial Parsing via Finite-State Cascades. InProceedings of the ESSLLI ’96 Robust Parsing Workshop. 1996a.URL http://www.vinartus.net/spa/96h.pdf.

Steven Abney. Tagging and Partial Parsing. In Ken Church, SteveYoung, and Gerrit Bloothooft, editors, Corpus-Based Methods inLanguage and Speech. 1996b. URL http://www.vinartus.net/spa/95a.pdf.

Steven Abney. The SCOL Manual: Version 0.1b, 28.04.1997. URLhttp://www.vinartus.net/spa/scol-1-12.tgz.

Karin Haenelt. Modelling Natural Language with Finite Automata withFinite Automata, 28.09.2004. URL http://kontext.fraunhofer.de/haenelt/papers/Theorietag14/HaeneltTheorietag14-L.pdf. .


http://www.vinartus.net/spa/96h.pdf

http://www.vinartus.net/spa/95a.pdf

http://www.vinartus.net/spa/95a.pdf

http://www.vinartus.net/spa/scol-1-12.tgz

http://kontext.fraunhofer.de/haenelt/papers/Theorietag14/HaeneltTheorietag14-L.pdf





Literatur

Donald Hindle. User manual for fidditch. Technical Memorandum,7590-142, 1983.

Daniel Jurafsky and James H Martin. Speech and languageprocessing: An introduction to natural language processing,computational linguistics, and speech recognition. Prentice Hall,Upper Saddle River, NJ, 2. ed. edition, 2008. ISBN 9780131873216.


Documents

Partielles Parsing mit kaskadierten endlichen Automatenkontext.fraunhofer.de/haenelt/kurs/Referate/Dolata_Regner_PartiellesParsingAbney.pdf · Einführung Partielles Parsing mit Kaskaden