View
112
Download
3
Category
Preview:
Citation preview
1
Algorithmus von Lappin und Leass (L&L)
für pronominale Anaphernauflösung
Resolution of Anaphora Procedure (RAP)
Nataliya Kutsenko
Philipp Kriependorf
Artjom Klein
2
Inhalt
1. Einführung2. L&L Algorithmus3. RAP4. Ergebnisse und Evaluierung5. Literatur und Ressourcen
3
1. Einführung
1.1. Motivation1.2. L&L kurz1.3. Ziel des Projekts1.4. Systemarchitektur1.5. Korpus
4
1.1 Motivation
• Anaphernbeispiel (1 Satz, deutsch z. B. „Peter kocht. Er macht Spaghetti.“)
• Es werden die Pronomina der 3. Person in allen Kasusformen aufgelöst
• Regelnbasierter Ansatz: L&L Ansatz
5
1.2 L&L Algorithmus: Kurz
• Regelbasiert
• Alle möglichen Antezedenten werden gesucht, dann ausgefiltert und der „wahrscheinlichste“ bleibt.
• Voraussetzung ist die Vorverarbeitung des Textes : - morphologische Informationen: Kasus, Numerus, Genus- grammatische Rollen (Subjekt, Objekt usw.)- Dependenzrelationen (Dependenzbäume)
6
1.3 Ziel des Projekts
• L&L für Deutsch nachimplementieren
• Mit einem Gold-Standart-Input evaluieren
7
1.4 Systemarchitektur
Parser
Konverter
RAP
Evaluierer
Parser Output
rap.input.xml
gold.rap.input.xml
Eval Output
anaphora.keys.xml
rap.ouput.xml
8
1.5 Korpus
• Tübinger Korpus des geschriebenen Deutschen• 27 000 Sätze• Zwei Versionen, die wir verwendet haben
- tuebadz3-anaphora.xmlPhasenstrukturannotation:
morphologische Informationen, Anaphernreferenz
- tuebadz3-malt.xmlDependenzstrukturannotation:
Grammatische Rollen
9
2. L&L Algorithmus
2.1. Überblick (Kurzbeschreibung)
2.2. Salienzwerte
2.3. Morphologischer Filter
2.4. Syntaktischer Filter
2.5. Beispiel
10
2.1 Lappin & Leass Algorithmus: Überblick
1. Verarbeitung der Sätze von links nach rechts
2. Alle möglichen Antezedenten im Kontext (4 Sätze vor und nach dem aktuellen Satz) finden
3. Salienzwerte berechnen
4. Anwenden der Filter, die aus der Liste der Kandidaten-NPn unmögliche Antezedenten aussortieren- morphologischer Filter- syntaktischer Filter
5. Die NP mit dem größten Salienzwert wird als Antezedens ausgewählt
11
2.2 Lappin & Leass Algorithmus: Salienzwerte
Der Salienzwert gibt an wie aktuell oder wie stark hevorgehoben ein Referent(eine Person, ein Objekt) zu einem bestimmten Moment der Textwiedergabe ist. Für Pronomenauflösung werden Referenten mit dem hohen Salienzwert bevorzugt.
SUBJECTEMPHASIS = 170ACCUSATIVE OBJECTEMPHASIS = 70DATIVE OBJECT EMPHASIS = 50GENETIVE OBJECT EMPHASIS = 50HEAD NOUN EMPHASIS = 80
CURRENT SENTENCE REWARD = 20PARALLELISM REWARD = 25SHORT DISTANCE CATAPHORA PENALTY = -80LONG DISTANCE CATAPHORA PENALTY = -175
12
2.3 Lappin & Leass Algorithmus: Morphologischer Filter
Prüft, ob Pronomen und NP in Genus und Numerus übereinstimmen (satzintern und satzextern)
Peter(i) erwartet, daß sie(k) einen Brief bekommt
13
2.4 Lappin & Leass Algorithmus: Syntaktischer Filter
Der syntaktische Filter prüft Paare Pronomen-NP, die im selben Satz stehen (satzintern).Voraussetzung: der Satz wird als Dependenzbaum dargestellt.Für Deutsche Sprache (Strube & Hahn).
Der Ansatz basiert auf Constraints. Dabei werden folgende Punkte berücksichtigt: • die Knoten und Relationen im syntaktischen Baum• die Position im Satz relativ zueinander• ob N und P Argumente vom selben Verb sind• ob N und P im Nebensatz oder im Hauptsatz stehen
14
2.5 L&L Algorithmus: Beispiel
Beispiel:
Peter(?) hat einen schönen Wagen(?) in der Halle(?) gesehen. Er(i) hat ihn seinem Bruder(?) gezeigt.
1.Die potenziellen Antezedenten finden und Salienzwerte berechnen:
[Peter = 160, Wagen = 75, Halle = 40, Bruder = 150]
15
2.5 L&L Algorithmus: Beispiel
Beispiel:
Peter(?) hat einen schönen Wagen(?) in der Halle(k) gesehen.
Er(i) hat ihn seinem Bruder(?) gezeigt.
2. Morphologischen Filter anwenden
[Peter = 160, Wagen = 75, Halle = 40, Bruder = 150]
[Peter = 160, Wagen = 75, Bruder = 150]
Morph. Filter
16
2.5 L&L Algorithmus: Beispiel
Beispiel:
Peter(?) hat einen schönen Wagen(?) in der Halle(k) gesehen.
Er(i) hat ihn seinem Bruder(m) gezeigt.
3. Syntaktischen Filter anwenden
[Peter = 160, Wagen = 75, Bruder = 150]
[Peter = 160, Wagen = 75]
Syntakt. filterihnEr
hat
Bruder
seinem
gezeigt
17
2.5 L&L Algorithmus: Beispiel
Beispiel:
Peter(i) hat einen schönen Wagen in der Halle gesehen. Er(i) hat ihn seinem Bruder gezeigt.
4. Den Kandidat mit dem größten Salienzwert auswählen
[Peter = 160, Wagen = 75]
[Peter = 160]
Auswahl
18
3. RAP
3.1. In Systemarchitektur3.2. rap.jar3.3. config.cfg3.4. Input: XML-Definition3.5. Input: PoS und grammatische Rollen3.6. Key-File3.7. Output
19
3.1 RAP in Systemarchitektur
RAP-Programm
• RAP und Evaluierungstool in einem• In Java implementiert• => RAP-Programm
Parser
Konverter
RAP
Evaluierer
Parser Output
rap.input.xml
gold.rap.input.xml
Eval Output
anaphora.keys.xml
rap.ouput.xml
20
3.2 RAP: Java-Klassen
21
3.3 RAP: rap.jar
Ausführen in Konsole: $ java –jar rap.jar <test ordner>
• Input: <test ordner>
Testordner enthält:- config.cfg (Konfiguration-Datei)- rap.input.xml (Geparster Text)- anaphora.keys.xml (Key-Datei)
• Output: eval.txt / Konsole
22
3.4 RAP: config.cfg
Durch config.cfg wird RAP „gesteuert“. Dort werden die Salienzwerte eingestellt und man kann die Filter (morphologischen und syntaktischen) ein- und ausschalten.
SENTENCESBUFFERSIZE = 9MORPHOLOGICFILTER = trueSYNTACTICFILTER = true
SUBJECTEMPHASIS = 170ACCUSATIVEOBJECTEMPHASIS = 70DATIVEOBJECTEMPHASIS = 50GENETIVEOBJECTEMPHASIS = 50HEADNOUNEMPHASIS = 80
CURRENTSENTENCEREWARD = 20PARALLELISMREWARD = 25SHORTDISTANCECATAPHORAPENALTY = -80LONGDISTANCECATAPHORAPENALTY = -175
23
3.4 RAP: Input: XML-Definition
Der Input ist eine Menge von Sätzen, jeder Satz ist eine Menge von Wörtern, jedes Wort wird wie folgt definiert:Jedes Wort hat 6 Attribute:
1.id = einheitliche Identität innerhalb eines Satzes 2.form = Wortform 3.postag = Part-of-speech4.head = Syntaktischer Kopf (Wort-Id). 5.deprel = Abhängigkeitsbeziehung zum/vom Kopf6.morph = morphologische Informationen
24
3.5 RAP: Input: Beispiel
Beispiel: “Veruntreute die AWO Spendengeld?”
<sentence id="1">
<word id="1" form="Veruntreute" postag="VFIN" head="0" deprel="ROOT" morph="-">
<word id="2" form="die" postag=“-" head="3" deprel=“-" morph="-">
<word id="3" form="AWO" postag="N" head="1" deprel="SUBJ" morph="nsf">
<word id="4" form="Spendengeld" postag="N" head="1" deprel="OBJA" morph="asn">
<word id="5" form="?" postag=“-" head="4" deprel="-" morph="-"></word>
</sentence>
25
3.6 RAP: PoS und grammatische RollenPoS Kategorien:• postag=“PPER3“ – Personalpronomen in der 3. Person singular und plural + in allen Kasusformen
(er, sie, es, ihn, ihr, ...)• postag=“N“ – alle Nomina einschiesslich Eigennamen• postag=“VFIN“ – finites Verb einschließlich modale Verben und Hilfsverben (z.B. lacht, erwartet,
konnte, hat usw.)• postag=“PREP“ – alle Präpositionen (z.B. über, zu, nach usw.)• postag=“DETPOS“ - Vorangestellte Possessivpronomina (mein Hund)
Grammatische Kategorien (Dependenzrelation zwischen dem Wort und seinem direkten Kopf):• deprel=“SUBJ“ Subjekt• deprel=“OBJA“ Akkusativobjekt• deprel=“OBJD“ Dativobjekt• deprel=“OBJG” Genitivobjekt
Alle vier sind obligatorische Argumente eines verbalen Prädikats.
• deprel=”GMOD” – vorangestelltes sowie nachgestelltes Substantiv im Genitiv mit nominalem Kopf (z.B. Peters Blume, Blume des Peters )
• deprel=“PPATT“ – Präposition PREP bei einem nominalen Kopf (die Wut auf den Lehrer)
• deprel= „DETPOSATT“ - Possessiv Pronomen DETPOS zum nominalen Kopf (z. B. Seine Blume)
26
3.7 Key-File: anaphora.keys.xml (rap.output.xml)
<anaphorapairs>
<pair id=„1" type="anaphoric"><anaphora sid="9" form="sie" pos="PPER3" wid="25"></anaphora><antecedent sid=„8" form=" Ute Wedemeier"></antecedent>
</pair>
<pair id=„2" type=„cataphoric"><anaphora sid="33" form="er" pos="PPER3" wid="12"></anaphora><antecedent sid="34" form=" Koring"></antecedent>
</pair>
</anaphorapairs>
Die Anaphorapaare (Pronomen und Antezedent) wurden aus dem Tübinger Korpus mit Hilfe eines Moduls exktrahiert.
27
3.8 RAP: Output
(a) pairs in key file = die Anzahl von Anaphorapaaren im Key-File, d. h. mit anderen Worten, die Anzahl der im Testkorpus vorkommenden Anaphern
(b) proposed pairs in rap output = die Anzahl von Personalpronomina im Input, die für die Auflösung vorgeschlagen worden sind; Anzahl der gefundenen Anaphern
(c) correct resolved pairs
= die Anzahl von Personalpronomina, für die ein korrekter Antezedent gefunden wurde.
• recall = Anzahl der korrekt aufgelösten Anaphern im Verhältnis zur Anzahl der im Testkorpus vorkommenden Anaphern
• precision = Anzahl der korrekt aufgelösten Anaphern im Verhältnis zur Anzahl der gefundenen Anaphern
28
4. Ergebnisse
pairs in key file
proposed pairs in rap output
correct resolved pairs
recall precision
5000 Sätze
„Gold“-Input
884 884 512 58% 58%
27000 Sätze
„Gold“-Input
3837 3837 2494 65% 65%
29
Literatur
• [1]. Algorithmus von Lappin und Leass für Englisch:http://acl.ldc.upenn.edu/J/J94/J94-4002.pdf
• [2]. Algorithmus von Lappin und Leass für Deutsch
http://www.sfs.uni-tuebingen.de/~wunsch/lingev06_wunsch.pdfhttp://www.sfs.uni-tuebingen.de/~wunsch/treebanks_car.pdf
• [3]. Anleitung für die Implementierung des syntaktischen Filters für Deutsch http://www.aclweb.org/anthology-new/E/E95/E95-1033.pdf
• [4]. Stylebook für Tübinger Korpus von geschriebenem Deutsch http://www.sfs.uni-tuebingen.de/resources/sty.pdf
• [5] Studienprojekteinleitung. /src/doc/Studienprojekteinleitung.pdf
Recommended