Parsing mit Phrasenstrukturgrammatiken Sprachorientierte ...wolfgang/lehre/syntax/n4k.pdf · Sprachorientierte KI: Syntax und Parsing Syntax als Untersuchungsgegenstand Wortartendisambiguierung

Sprachorientierte KI: Syntax und Parsing

Syntax als Untersuchungsgegenstand

Wortartendisambiguierung

Phrasenstrukturgrammatiken

Parsing mit Phrasenstrukturgrammatiken

Restringierte Phrasenstrukturgrammatiken

Unifikationsgrammatiken

Constraint-basierte Grammatiken

Robustes Parsing

Wolfgang Menzel: Sprachorientierte KI: Syntax und Parsing – p. 1

Parsing mit Phrasenstrukturgrammatiken

Strukturanalyse

flaches Parsing

CFG-Parsing

Parsingstrategien

Tabellenparsing

Chartparsing

Deterministisches Parsing

Stochastisches Parsing


Strukturanalyse

Parsing naturlicher Sprache

partes orationes: Grammatische Analyse als

Wortartenbestimmung

Zerlegung eines Satzes in seine Bestandteile

Strukturaufklarung, Ermittlung der grammatischen

Relationen zwischen den Satzbestandteilen

Ziel: Strukturbeschreibungen

Grundlage fur eine semantische Interpretation

Erkenner vs. Parser


Strukturanalyse

Ergebnisstrukturen

syntaktische Phrasenstrukturbaume

syntaktische Dependenzrelationen

semantische Reprasentationen

Hans

fahren

Auto zu Hause

AGENSINSTR

DESTIN


Flaches Parsing

Chunking: Zerlegung eines Satzes in Konstituenten ohne

Beachtung der rekursiven Einbettung

z.B. mit gewichteten endlichen Automaten

Det Adj Nom

Adv Adj

Nom


CFG-Parsing

Lexikon Grammatik

N → Marie S → NP VP

N → Hans VP → V PP

N → Park VP → V PP PP

P → auf PP → P NP

P → im NP → N

V → wartet


CFG-Parsing

Regelanwendung von links nach rechts: top down

Ableitung des Satzes aus dem Startsymbol:

S

NP VP

N V PP

Hans wartet P NP. . .

Regelanwendung von rechts nach links: bottom up

Ableitung des Startsymbols aus dem Satz:

Hans wartet auf Marie

N V P N

NP V P NP

NP V PP. . .


CFG-Parsing

alle Alternativen fur Regelanwendungen mussen berucksichtigt

werden

Mehrdeutigkeiten (Ambiguitaten)

verhindern lokale Entscheidungen

lexikalische Mehrdeutigkeiten:

laufen/VINF/VFIN/NN, schone/ADJ/NN . . .

strukturelle als Folge lexikalischer Mehrdeutigkeit

. . . dort, wo die wilden/ADJ/NN tiere jagen/Vintr/Vtr


CFG-Parsing

rein strukturelle Mehrdeutigkeit

[NP der Mann [PP mit dem Hut [PP auf der Stange]]]

[NP der Mann [PP mit dem Hut] [PP auf der Stange]]

. . . , weil [NP dem Sohn des Meisters] [NP Geld] fehlt.

. . . , weil [NP dem Sohn] [NP des Meisters Geld] fehlt.

lokale Mehrdeutigkeiten

konnen im weiteren Verlauf der Analyse aufgelost werden

globale Mehrdeutigkeiten

bleiben bis zum Abschluss der Analyse bestehen


CFG-Parsing

Parsing als Suche

alternative Regelanwendungen spannen einen Suchraum

auf


CFG Parsing

kontextfreie Phrasenstrukturregeln werden moglicherweise erst

im Parser generiert

ID/LP-Grammatiken

S → {NP,VP} NP < VP

LP-Constraints meist auf der Basis von Merkmalen fur

komplexe Kategorien formuliert


CFG Parsing

Dependenzgrammatiken

Valenzmuster

futtern: 〈 SUBJ, *, DOBJ 〉

”flache” Phrasenstrukturregel

S → C1SUBJ VFIN C2DOBJ

”tiefe” Phrasenstrukturregeln

S → C1SUBJ C2VP

C2VP → VFIN C3DOBJ


Parsingstrategien

erwartungsgesteuert (top-down, expand-reduce)

Problem: links-/rechtsrekursive Regeln verursachen

Terminierungsprobleme

auch uber mehrere Regeln hinweg:

X → Y a

Y → X

Losung: Transformation in schwach aquivalente Grammatik

ohne Links-/Rechtsrekursion

linguistisch motivierte Ableitungsstruktur geht verloren

Ausweg: separater Strukturaufbau durch Unifikation


Parsingstrategien

datengesteuert (bottom-up, shift-reduce)

Problem: leere Produktionen X → ǫ

eventuell ”Lizensierung” durch lexikalische Knoten

Problem: unare Regeln, die Zyklen bilden

vermeiden


Parsingstrategien

Tiefe zuerst

alternative Regelanwendungen werden erst spater untersucht

Speicherung auf einem Stack

Breite zuerst

alternative Regelanwendungen werden ”gleichzeitig”

abgearbeitet

Verwaltung der Alternativen in einer Warteschlange


Parsingstrategien

links-rechts

Symbolfolgen werden von links beginnend abgearbeitet

rechts-links

Symbolfolgen werden von rechts beginnend abgearbeitet


Parsingstrategien

gemischte Strategien

Left-Corner-Parsing: Top-down-Analyse mit Aktivierung

der Regeln durch die linke Ecke

Robustheit gegenuber fehlerhaftem Input:

bottom up-Analyse mit top down-Rekonstruktion

im Fehlerfall (Mellish 1989)

Inselparsing: bidirektionale Analyse von sicheren

Hypothesen ausgehend (z.B. Spracherkennung)


Tabellenparsing

Effizienzproblem: Mehrfachanalysen in unterschiedlichen

Analysepfaden

Daten

Deutsch mit kopffinaler Verbgruppe

Normalfall: Nebensatzreihung

..., weil der Vater seine Kinder liebt.

..., weil der Vater seinen Kindern glaubt.

..., weil der Vater seinen Kindern ein Eis versprach.

..., weil der Vater seinen Kindern mit einer Strafe droht.


Tabellenparsing

Grammatik

S’ → Konj S

S → NPn VP

VP → NPa Va

VP → NPd Vd

VP → NPd NPa Vd,a

VP → NPd PPmit,d Vd,mit

NPX → DX NX

PPX,Y → PX NPY

Beispielanalyse: top-down, Tiefe-zuerst

... der Vater seinen Kindern ein Eis versprach.


Tabellenparsing

S

NPn VP

Dn Nn VP

d Nn VP

d v VP

d v NPd Vd d v NPa Va d v NPd NPa Vd,a ...

d v Dd Nd Vd d v Da Na Va d v Dd Nd NPa Vd,a

d v s Nd Vd d v s Nd NPa Vd,a

d v s K Vd d v s K NPa Vd,a

d v s K Da Na Vd,a

d v s K e Na Vd,a

d v s K e E Vd,a

d v s K e E v


Tabellenparsing

Well-formed Substring Table (Chart)

gerichteter azyklischer Graph mit

einer Quelle (Satzanfang)

einer Senke (Satzende) und

einer totalen Prazedenzrelation uber den Knoten

Kanten entsprechen erfolgreich erkannten Konstituenten


Tabellenparsing

er seinen Kindern mit einer Strafe droht

Pron

NPn

Dd Nd

NPd

Pmit Dd Nd

NPd

PPmit,d

Vd,mit

VP

S


Tabellenparsing

1 2 3 4 5 6 7

er0 Pron S

NPn

seinen NPd VP1 Dd

Kindern2 Nd

mit PPmit3 Pmit

einer NPd4 Dd

Strafe5 Nd

droht6 Vd,mit


Tabellenparsing

Cocke-Younger-Kasami-Algorithmus

(Kasami 1965, Younger 1967)

Grammatik in Chomsky-Normalform

binarverzweigende Regeln: X → Y Z

praterminale Regeln: X → a


Tabellenparsing

CYK: Eigenschaften

1. Lange der Ableitung konstant:

n lexikalische Regeln + n-1 syntaktische Regeln

2. Anzahl der Binarzerlegungen eines Satzes ist konstant: n-1

((a) (b c d))

((a b) (c d))

((a b c) (d))

3. Strukturelle Mehrdeutigkeiten durch unterschiedliche

Uberdeckung der Eingabekette entfallen

VP → NP NP V

VP → NP V

VP → VWolfgang Menzel: Sprachorientierte KI: Syntax und Parsing – p. 25

Tabellenparsing

CYK: Algorithmus

1. Initialisieren der Matrix

fur i = 0 bis n − 1:

CHARTi,i+1 ⇐ { X | X ∈ VT und wi+1 ∈ X }

2. Berechnung der ubrigen Felder

fur k = 2 bis n:

fur i = 0 bis n − k:

j ⇐ i + k

CHARTi,j ⇐ { A | (A → X Y) ∈ R ∧ ∃ m . (X ∈ CHARTi,m

∧ Y ∈ CHARTm,j , mit i < m < j }

wenn S ∈ CHART0,n

dann RETURN(true)

sonst RETURN(false)


Tabellenparsing

Bottom up-Analyse

Zeitbedarf O(n3)

Speicherbedarf O(n2)

durch Wiederverwendung von Zwischenergebnissen

Nachteil: es werden immer noch Konstituenten generiert, die

in keine ubergreifenden Strukturen eingebaut werden konnen

→ Earley-Parser


Chart-Parsing

Aktive Chart

Erweiterung: auch Versuche einer Regelanwendung werden

in die Chart eingetragen

Aktive Kanten:

offene Erwartungen fur den rechten Kontext

Notation: 〈 a, b, A → B . C D 〉

Inaktive Kanten:

vollstandig gesattigte Erwartungen fur den rechten

Kontext

Notation: 〈 a, b, A → B C D . 〉


Chart-Parsing

TD-Regel (Initialisierung)

Fur alle Regeln A → w1 bei denen A ein Startsymbol der

Grammatik ist, fuge eine Kante 〈 0, 0, A → . w1 〉 in die

Chart ein.

Regel: S → NPn VP

der Vater seinen Kindern . . .

S → . NPn VP

Dn Na Dd Nd


Chart-Parsing

TD-Regel (Kanteneinfuhrung)

Beim Eintragen einer Kante 〈 i, j, A → w1 . B w2 〉 erganze

fur jede Regel B → w3 eine Kante 〈 j, j, B → . w3 〉.

Regel: NPX → DX NX


S → . NPn VP

NPn → . Dn Nn

Dn Nn Dd Nd


Chart-Parsing

Fundamentalregel (Kantenexpansion)

Enthalt die Chart zwei Kanten 〈 i, j, A → w1 . B w2 〉

und 〈 j, k, B → w3 . 〉, dann fuge eine dritte Kante

〈 i, k, A → w1 B . w2〉 hinzu.


S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

Dn Nn Dd Nd


Chart-Parsing

Erneute Anwendung der Fundamentalregel


S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

Dn Nn Dd Nd


Chart-Parsing

Erneute Anwendung der Fundamentalregel


S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP

Dn Nn Dd Nd


Chart-Parsing

Erneute Anwendung der Top-Down-Regel


S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP

VP → . NPd NPa Vd,a

Dn Nn Dd Nd


Chart-Parsing



S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP


NPd → . Dd Nd

Dn Nn Dd Nd


Chart-Parsing

Erneute Anwendung der Fundamental-Regel


S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP


NPd → . Dd Nd

NPd → Dd . Nd

Dn Nn Dd Nd


Chart-Parsing



S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP


NPd → . Dd Nd

NPd → Dd . Nd

NPd → Dd Nd .

Dn Nn Dd Nd


Chart-Parsing



S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP


NPd → . Dd Nd

NPd → Dd . Nd

NPd → Dd Nd .

VP → NPd . NPa Vd,a

Dn Nn Dd Nd


Chart-Parsing



S → . NPn VP

NPn → . Dn Nn

NPn → Dn . Nn

NPn → Dn Nn .

S → NPn . VP


NPd → . Dd Nd

NPd → Dd . Nd

NPd → Dd Nd .

VP → NPd . NPa Vd,a

NPa → . Da Na

Dn Nn Dd Nd


Chart-Parsing

Earley-Algorithmus (Earley 1970)

fur beliebige CF-Grammatiken

auch mit Rekursion, Zyklen und Tilgungen

gemischte Top down/Bottom up-Strategie, um die

Erzeugung nicht weiter verwendbarer Konstituenten

weitgehend zu vermeiden

1. Top-Down-Bedingung:

es werden nur solche Kanten generiert, deren linker

Kontext mit der Grammatik vertraglich ist

2. Bottom up-Bedingung:

der bereits abgearbeitete Regelteil muß sich auf die

Daten ableiten lassen


Chart-Parsing

w1 wi wi+1 wj wj+1 wk wn

S

A

α β


Chart-Parsing

Operationen

Expand (Top-down-Regel, Kantenintroduktion)

Complete (Fundamentalregel, Kantenexpansion)

Shift (Einbeziehung lexikalischer Kanten)

verschiedene Suchstrategien (Tiefe/Breite) sind moglich

in Abhangigkeit von der Agenda-Verwaltung


Chart-Parsing

Earley-Algorithmus1. Initialisierung

fur alle (S → β) ∈ R: CHART0,0 ⇐ 〈S,∅, β〉

wende EXPAND solange auf die zuvor erzeugten Kanten an,

bis keine neuen Kanten mehr erzeugt werden konnen.

2. Berechnung der ubrigen Kanten

fur j = 1, . . . , n:

fur i = 0, . . . , j:

berechne CHARTi,j :

1. wende SHIFT auf alle geeigneten Kanten in CHARTi,j−1 an

2. Wende EXPAND und COMPLETE solange an, bis keine

neuen Kanten mehr erzeugt werden konnen.

wenn 〈S, β, ∅〉 ∈ CHART0,n

dann RETURN(true) sonst RETURN(false)


Chart-Parsing

Chart-basierte Algorithmen sind nur Erkenner

Erweiterung zum Parser:

Extraktion von Strukturbaumen (Ableitungen) aus der

Chart in einem separaten Schritt

Grundlage: Verwaltung eines Verweises auf die

verursachende Kante in der Fundamentalregel

”Aufsammeln” der Baume beginnend bei allen

vollstandigen S-Kanten


Chart-Parsing

Ressourcenbedarf: Zeit

O(n3 · |G2|)

fur deterministische Grammatiken: O(n2)

in vielen praktisch relevanten Fallen: O(n)

Zeitkomplexitat nur fur das Aufbauen der Chart

Resultatsextraktion kann bei exponentiell vielen Resultaten

exponentiellen Aufwand erfordern


Chart-Parsing

Ressourcenbedarf: Speicher

O(n2)

durch Wiederverwendung von Zwischenergebnissen

nur fur atomare Nichtterminalsymbole moglich

Chart ist allgemeine Datenstruktur zur Verwaltung von

Zwischenergebnissen beim Parsing

alternative Analysestrategien sind moglich

z.B. bottom-up


Chart-Parsing

Bottom-Up-Regel (Kanteneinfuhrung)

Beim Eintragen einer Kante 〈 i, j, B → w1 〉 erganze

fur jede Regel A → B w2 eine Kante 〈 i, i, A → . B w1 〉


NPn → . Dn Nn NPd → . Dd Nd

Dn Nn Dd Nd


Chart-Parsing

Anwendung der Fundamentalregel



NPn → Dn . Nn NPd → Dd . Nd

Dn Nn Dd Nd


Chart-Parsing





Dn Nn Dd Nd

NPn → Dn Nn . NPd → Dd Nd .


Chart-Parsing

Anwendung der Bottom-Up-Regel




Dn Nn Dd Nd


S → . NPn VP VP → . NPd NPa Vd,a


Chart-Parsing





Dn Nn Dd Nd


S → . NPn VP VP → . NPd NPa Vd,a

S → NPn . VP VP → NPd . NPa Vd,a


Chart-Parsing

Chart wachst monoton

Kanten werden nicht entfernt

auch gescheiterte Regelanwendungen werden aufbewahrt

nicht mehr expansionsfahige aktive Kanten

Mehrfacharbeit wird vermieden

Kante wird nur dann in die Chart eingetragen, wenn dort

noch nicht vorhanden


Chart-Parsing

Agenda

Liste der aktiven Kanten

beliebig sortierbar

Kellerspeicher: Tiefe-zuerst

Warteschlange: Breite zuerst

TD-Regel: erwartungsgesteuerte Analyse

BU-Regel: datengesteuerte Analyse


Chart-Parsing

flexible Steuerung fur Mischstrategien

left-corner-Parsing

TD-Parsing, aber nur diejenigen Regeln aktivieren, die

eine gegebene lexikalische Kategorie (linke Ecke) direkt

oder indirekt ableiten konnen

Tabelle mit der Zuordnung zwischen Regeln und ihren

moglichen linken Ecken wird aus der Grammatik berechnet

Variante: head-corner Parsing


Chart-Parsing

best-first-Parsing

Sortieren der Agenda nach Konfidenzwerten

Hypothesenbewertungen der Spracherkennung

Regelbewertungen (z.B. Haufigkeit in Korpus)


Chart-Parsing

Aufgabe der totalen Prazedenzrelation uber den Knoten:

Lattice-Parsing

Worthypothesegraphen bei der Verarbeitung gesprochener

Sprache

z.B. Ergebnisse einer HMM-Worterkennung

Aufgabe der Verbundenheit des Hypothesegraphen:

Grid-Parsing

z.B. Ergebnisse eines Wordspotters mit

Hypothesealternativen



nur fur Teilmengen der CF-Sprachen: LR(n), n=0, 1, . . . k

deterministische Sprachen

Berechnung einer Parsingtabelle aus der Grammatik vor

Beginn der Analyse

eindeutige Ermittlung der nachsten Aktion:

shift lege das nachste Wort auf den Stack

reduce reduziere den Stack

accept Satz wurde akzeptiert

error Satz wurde zuruckgewiesen, nicht in L(G)



Tomita-Parsing (Tomita 1984)

fur beliebige CF-Grammatiken (ohne Zyklen)

zwei Erweiterungen:

1. Parsingtabelle mit alternativen Eintragen

→ baumstrukturierter Stack

2. Zusammenfassen alternativer Analysevarianten

→ graphstrukturierter Stack



Tomita-Parsing

effiziente Strukturverwaltung (packed shared forests)

1. Zusammenfassen gemeinsamer Teilstrukturen

verschiedener Syntaxbaume

→ subtree sharing

2. Zusammenfassen von Teilstrukturen mit gleichem

Spitzenknoten und gleichen Terminalknoten

→ local ambiguity packing



der Mann liest das Buch im Bett

D N VD N P

NNP

NP PPNP VP

S


D N V

D N PNNP

NP PPNP

NP VPS



subtree-sharing


D N

VD N P

NNP

NP PPNP

NP VP VP

S S



subtree-sharing und local ambiguity packing


D N

VD N P

NNP

NP PP

NPNP VP VP

S S

Zeitaufwand: O(n3 · |G|2) (Kipps 1991)



Warum stochastisches Parsing?

Stochastisches Basismodell

Evaluation

Training

Parsing

Erweitertes Basismodell

Alternative Modelle



gemeinsame Probleme aller symbolischen Parser:

hohe Ergebnismehrdeutigkeit

auch bei (sehr) feiner syntaktischer Modellierung

trotz geringer Abdeckung

Ergebnismehrdeutigkeit und Abdeckungsgrad sind

typischerweise gegenlaufig



Ergebnismehrdeutigkeit

Hinter dem Betrug werden die gleichen Tater vermutet,

die wahrend der vergangenen Tage in Griechenland

gefalschte Banknoten in Umlauf brachten.







Paragram (Kuhn und Rohrer 1997): 92 Lesarten








Gepard (Langer 2001): 220 Lesarten








Gepard (Langer 2001): 220 Lesarten

durchschnittliche Ambiguitat uber ein Zeitungstextkorpus:

78 bei einer mittleren Satzlange von 11.43 syntaktischen

Wortern (Gepard)

Extremfall: 6.4875 · 1022 Lesarten fur einen Satz

(Block 1995)



Ambiguitatsquellen:

lexikalische Mehrdeutigkeit

Attachment

We saw the Eiffel Tower flying to Paris.

Koordination:

alte Manner und Frauen

NP-Klammerung

. . . der Sohn des Meisters Geld



Beispiel: PP-Attachment

der Ball mit den Punkten in der Tasche auf dem Tisch

wachst exponentiell (Catalan) mit der Anzahl der PPs

C(n) =1

n + 1

2n

n

# PPs # Parses

2 23 54 145 1326 4697 14308 4867



Abdeckung (coverage)

partieller Parser (Wauschkuhn 1996): 56.5% der Satze

Gepard: 33.51%

auf Testsuites (bessere Lexikonabdeckung, kurzere und

weniger ambige Satze) bis zu 66%



Ausweg: stochastische kontextfreie Grammatiken (PCFG)

Schatzen von Ableitungswahrscheinlichkeiten fur alle Regeln

Pr(N → ζ)

bzw.

Pr(N → ζ|N) mit∑

ζ

Pr(N → ζ) = 1

z.B.

S → NP VP 0.8S → Aux NP VP 0.15S → VP 0.05



Sprachmodelle: Zuordnung einer Wahrscheinlichkeit zu einer

Terminalkette

Pr(w1,n) =∑

t1,n

Pr(t1,n)

(mehrere Ableitungen fur einen Satz)

=∑

t1,n

∏

rj∈t1,n

Pr(rj)

Ermittlung der wahrscheinlichsten Wortfolge



Disambiguierung: Ermittlung der wahrscheinlichsten Ableitung

t1,n = arg maxt1,n∈T

Pr(t1,n)

= arg maxt1,n∈T

∏

rj∈t1,n

Pr(rj)



Unabhangigkeitsannahme:

Pr(N jk,l → ζ|N1, . . . ., N j−1, w1, . . . , wk−1, wl+1, . . . , wn)

= Pr(N jk,l → ζ)

w1wk−1 wl+1 wn

Nj

N1


Evaluation

PARSEVAL (Black et al. 1991)

Vergleich mit einer Referenzannotation (gold standard)

labelled recall

LR =# korrekte Konstituenten im Resultat

# Konstituenten in der Referenz

labelled precision

LP =# korrekte Konstituenten im Resultat

# Konstituenten im Resultat


Evaluation

crossing brackets

Ein Konstituent eines Parsebaumes enthalt Teile von zwei

Konstituenten aus der Referenz, ohne dass die beiden

vollstandig im Parseresultat enthalten sind.

Resultat: [ [ A B C ] [ D E ] ]

Referenz: [ [ A B ] [ C D E ] ]

CB =# crossing brackets

# Satze

0CB =# Satze ohne crossing brackets

# Satze


Evaluation

Wie aussagekraftig sind die Qualitatsmaße?

Referenz:

S

NP VP

I saw NP PP

a man PP in NP

with NP the park

NP and NP

a dog a cat

[I [saw [[a man] [with [[a dog] and [a cat]]]] [in [the park]]]]


Evaluation

1. Resultat: eine fehlerhafte strukturelle Anbindung

S

NP VP

I saw NP

a man PP

with NP

NP and NP

a dog NP PP

a cat in NP

the park

[I [saw [[a man] [with [[a dog] and [[a cat] [in [the park]]]]]]]]


Evaluation

2. Resultat: weitgehend flache Analyse

Vermeiden aller Entscheidungen uber strukturelle

Anbindungen

S

NP VP

I saw NP with NP and NP PP

a man a dog a cat in NP

the park

[I [saw [a man] with [a dog] and [a cat] [in [the park]]]]


Evaluation

1. Resultat

[I [saw [[a man] [with [[a dog] and [[a cat] [in [the park]]]]]]]]


LR = 7

10= 0.7 LP = 7

11= 0.64 CB = 3

1= 3

2. Resultat

[I [saw [a man] with [a dog] and [a cat] [in [the park]]]]


LR = 7

10= 0.7 LP = 7

7= 1 CB = 0

1= 0

Alternative (Lin 1996):

Transformation in eine Dependenzstruktur und Evaluation der

Anbindungsfehler


Training

Schatzen der Regelanwendungswahrscheinlichkeiten

Einfachster Fall: Treebank-Grammatiken

(Charniak 1996)

Pr(N → ζ|N) =C(N → ζ)

∑

ξ C(N → ξ)=

C(N → ζ)

C(N)

Penn-Treebank: 10605 Regeln, davon 3943 nur einmal

beobachtet

Resultate fur Satze bis max. 40 Wortformen:

LR = 80.4%, LP = 78.8%

Konstituenten ohne crossing brackets: 87.7%


Training

Training auf unannotierten Daten: inside-outside-Algorithmus

Voraussetzung:

Grammatik (incl. Lexikon)

Trainingskorpus

Parameter-Reestimation uber Ableitungsketten

aber: ein Satz kann ublicherweise auf verschiedenen

Wegen abgeleitet werden

→ wichten der Varianten mit ihren

Ableitungswahrscheinlichkeiten

→ Rekombinationsverfahren


Training

inside-Wahrscheinlichkeit: Wahrscheinlichkeit fur Expansion

eines Nichterminals zu einer bestimmten Terminalkette

≈ backward-probability

βj(k, l) = Pr(wk,l|Njk,l)

outside-Wahrscheinlichkeit: Wahrscheinlichkeit fur die

Ableitung eines Baumkontextes

≈ forward-probability

αj(k, l) = Pr(w1,k−1, Njk,l, wl+1,n)


Training

Regelwahrscheinlichkeit (fur Chomsky-Normalform)

C(N j → NpNq)

=1

Pr(w1,n)

∑

k,l,m

αj(k, l) · Pr(N j → NpNq)

· βp(k, m) · βq(m + 1, l)

C(N i → wj)

=1

Pr(w1,n)

∑

k

αi(k, k)·Pr(N i → wj, wj = wk)


Parsing

Parsing mit modifiziertem Earley/CYK-Algorithmus

dynamische Programmierung:

rekursiver Aufbau der Parsingtabelle und Auswahl der

lokal optimalen Interpretation



Problem: Unabhangigkeitsannahme ist systematisch falsch

Subjekt wird haufiger pronominalisiert als Objekt

besonders deutlich in gesprochener Sprache

Auswirkung der Informationsstruktur

Subkategorisierungspraferenzen disambiguieren

Anbindungsprobleme

NP Anbindung ist haufiger als V-Anbindung (2:1)

aber: einige Verben erzwingen Anbindung bestimmter

Prapositionen

Moscow sent more than 100.000 soldiers into Afghanistan.

send requires a direction (into)

→ Modellierung lexikalischer AbhangigkeitenWolfgang Menzel: Sprachorientierte KI: Syntax und Parsing – p. 84


lexikalische Abhangigkeiten lassen sich in PCFG nicht

ausdrucken

nur stochastische Abhangigkeit vom dominierenden

Nichtterminal

Pr(N → ζ|N)

Erweiterung des stochastischen Modells um zusatzliche

Bedingungen



→ lexikalisierte Regelanwendungswahrscheinlichkeiten

(Charniak 2000)

Pr(N → ζ|N, h(r))

lexikalische Abhangigkeiten

(Charniak 2000, Collins 1999)

vom Kopf der unmittelbar ubergeordneten Phrase

Pr(r = N → ζ|N, h(r), h(m(r)))

vom Kopf der beiden ubergeordneten Phrasenebenen

Pr(r = N → ζ|N, h(r), h(m(r)), h(m(m(r))))



Problem: Datenmangel

Backoff

Glatten

stochastische Modellierung der Schwesterknoten zum

Kopf als Markov-Prozess (Collins 1999)



Qualitat (Charniak 2000)

Satzlange ≤ 40

Parser LR LP CB 0CB 2CB

Collins 1999 88.5 88.7 0.92 66.7 87.1

Charniak 2000 90.1 90.1 0.74 70.1 89.6

Satzlange ≤ 100

Parser LR LP CB 0CB 2 CB

Collins 1999 88.1 88.3 1.06 64.0 85.1

Charniak 2000 89.6 89.5 0.88 67.6 87.7


Alternative Modelle

Parsing als stochastischer Mustervergleich

Magerman 1994

”Parsing ohne Grammatik”

Training eines binaren Entscheidungsbaumes (decision tree)

strukturelle Anbindung von Wortformen und Teilbaumen

Wahl der strukturellen Kategorie


Alternative Modelle

Merkmalsreprasentation fur Syntaxbaume

label: phrasale Kategorie (N,V,S, . . . )

nur fur nichtterminale Knoten

word: Wortform des Blattknotens bzw. des

Konstituentenkopfes

tag: Wortart des Blattknotens bzw. des

Konstituentenkopfes

extension: linke oder rechte Konstituentengrenze, bzw.

mittlere Position (right, left, up)


Alternative stochastische Modelle

SlistedVVNroot

NcharacterNN1right

VlistedVVNleft

eachDD1right

characterNN1left

isVBZright

listedVVNleft


Alternative Modelle

Training des Entscheidungsbaumes

Beschrankung der initialen Knotenmenge:

bottom-up/links-rechts Derivation: Ein Knoten wird

erst konstruiert, wenn unterhalb und links davon

bereits alle Informationen verfugbar sind

Ableitungsfenster: es werden immer nur n mogliche

Merkmalswertzuweisungen betrachtet (→ aktive

Knoten)

tatsachliche Fenstergroße: 1 . . . 2

Ziel: Optimale Reihenfolge von Entscheidungsfragen

Optimierungskriterium: Maximale Entropiereduktion fur

die Trainingsmenge


Alternative Modelle

Resultate

Trainingsdaten: Baumkorpus mit 1473 Satzen

78% korrekte Klammerstruktur (crossing-brackets score)

35% korrekte Baumstruktur (mit Wortartentagging)

50% korrekte Baumstruktur (ohne Wortartentagging)

Vergleich: 69% korrekte Klammerstruktur fur klassischen

Parser


Alternative Modelle

Datenorientiertes Parsing (DOP) (Bod 1992, 2003)

Zerlegung der Parsebaume in Teilbaume bis zu einer

maximalen Hohe n (n ≤ 6)

Schatzen der Auftretenswahrscheinlichkeit aller Teilbaume

Ermitteln der Ableitungswahrscheinlichkeit fur eine

Ergebnisstruktur als Summe uber alle Ableitungsvarianten

geschlossene Berechnung nicht mehr moglich

→ Monte-Carlo-sampling

LR=90.7%, LP=90.8% (Satzlange ≤ 100)


Alternative Modelle

Supertagging (Bangalore 1997)

Zerlegen des Parsebaumes in lexikalisierte Baumfragmente

analog zu einer Tree Adjoining Grammar (TAG)

Verwendung der Baumfragmente als strukturell

reichhaltige lexikalische Kategorien

Training eines stochastischen Taggers

Auswahl der wahrscheinlichsten Folge von

Strukturfragmenten

→ almost parsing


Alternative Modelle

Supertagging

Rekonstruktion eines Parsebaumes aus den

Baumfragmenten

bessere Resultate (geringere Perplexitat) mit einer

Constraint Dependency Grammar (Harper 2002)

auch bei Training auf fehlerhaften Baumbanken

(Harper 2003)



Anwendungen:

approximatives Parsing fur unrestringierten Text

Informationsextraktion

Diskursanalyse

Analyse ungrammatischer Außerungen

Sprachmodelle in der Spracherkennung

Lernen von Grammatiken


Documents

Parsing mit Phrasenstrukturgrammatiken Sprachorientierte ...wolfgang/lehre/syntax/n4k.pdf · Sprachorientierte KI: Syntax und Parsing Syntax als Untersuchungsgegenstand Wortartendisambiguierung