Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 1 / 25

Parsen natürlicher Sprache

Wo steht Englisch in der Chomsky-Hierarchie?

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 2 / 25

Motivation

• Informationsextraktion

• Automatische Übersetzung

• Vorstufe zum „richtigen“ Turing-Test

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 3 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 4 / 25

Metrik für Parserqualität

Penn Treebank:

• Basiert auf Newsartikeln aus Wall-Street-Journal

• Per Hand geparste Sätze mit bis zu >100 Wörtern

• Aufgeteilt in mehrere Sektionen à ca. 2000 Sätze

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 5 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 6 / 25

Kontextfreie Grammatik

• S NP VP• NP DT NN• VP Verb NP

• Verb = be, do, like, talk, ...

• NN = ...

• S = Sentence• NP = Noun Phrase• VP = Verb Phrase• DT = Determiner• NN = Noun

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 7 / 25

CFG, Probleme

• Problem 1: Postscript language• Lösung 1: NN NN NN

• Problem 2: Postscript language input file• Lösung 2: ???

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 8 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 9 / 25

Probabilistische CFG

• Grundidee: jede Regel wird mit Wahrscheinlichkeit versehen

• Aufgabe des Parsers: finde den Baum mit maximaler Wahrscheinlichkeit

• Abschätzung der Wahrscheinlichkeiten:Im Trainingssatz angewendete Regeln nachzählen

• Problem: Postscript language input file

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 10 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 11 / 25

Head-lexicalized PCFG

• Grundidee: Für jede Regel wird ein Element (lexical head) ausgezeichnet

• S NP VPNP DT NNVP Verb NP

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 12 / 25

Head-lexicalized PCFG

S / is

NN / example

DT / this

NP / tree VP / is

NN / tree Verb / is NP / example

DT / an

This tree is an example

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 13 / 25

HPCGF, Probabilismus

Wahrscheinlichkeiten:P(category(root(T)))P(head(root(T))|category(root(T)))P(head(n)|category(n),category(parent(n)), head(parent(n))P(<word(n)>|cat(n), head(n))

Erste Wahrscheinlichkeitsabschätzung:In Trainingsdaten Häufigkeiten nachzählen

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 14 / 25

HPCFG, Sparse Data Problem

• Abschätzung z. B. durchUnabhängigkeitsannahmen:Z.B.P(<word>|cat(n), head(n)) =P(<word>)/P(cat(n),head(n))

• Es gibt auch andere Verfahren• Generell: komplizierte Geschichte

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 15 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 16 / 25

Link-Grammatik

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 17 / 25

Link-Grammatik

Der Satz ist geparst, wenn es keine freien Links mehr gibt:

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 18 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 19 / 25

Probabilistische Links (1/2)• Vereinfachung:

– Reduktion auf basis-NPs– Beschränkung von Links auf reduzierte Sätze

• Weitere Vereinfachungen:– Part-of-Speech Tagging als Preprocessing– Reduktion von basis-NPs auf head words

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 20 / 25

Basis-NPs

• Beim Training: Markierung der Zwischenräume als:(NP-)Start, Continuation, End, Between, Null:S This C sentence E is S an C example E .

• Beim Parsen: Einbeziehung der Markierungen ins Wahrscheinlichkeitsmodell

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 21 / 25

Probabilistische Links (2/2)

• Wahrscheinlichkeiten:P(ArrowFrom(modifier, head, Relation))

• Wahrscheinlichkeitsabschätzung:Count(<word1, Tag1>, <word2, Tag2>)Count(Relation|<word1, Tag1>, <word2, Tag2>) Daraus lässt sich P(ArrowFrom(...)) ausrechnen

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 22 / 25

ÜberblickKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 23 / 25

Collins-Parser• Head-lexicalized PCFG• Kompliziertes Wahrscheinlichkeitsmodell:

Wahrscheinlichkeiten für– Grammatikregeln– Links– Distanzen zwischen Wörtern– etc.

Komplizierte Ausrechnung von Einzelwahrscheinlichkeiten

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 24 / 25

Parserqualität: TrefferquotenKontextfreie

Grammatik (CFG)

ProbabilistischeCFG (PCFG)

ProbabilistischeLinks

Link-Grammatik

Head-lexicalizedPCFG

Collins-Parser

ca. 70%

ca. 75%

ca. 85%

bis 89%

Perlen der Weisheit, 15.04.2003 Leo Kof. Parsen natürlicher Sprache 25 / 25

Zusammenfassung

• Es werden immer bessere Ergebnisse erzielt. Preis: Modellkomplexität

• Es gibt immer noch keinen Parser mit 100%-Trefferquote

• Portierung für andere Sprachen oft schwierig