Diese Vorlesung
basiert zu einem Teil auf [Manning
& Schütze 1999] Kapitel 12.
In der
natürlichen Sprache ist Ambiguität viel weiter verbreitet, als man
üblicherweise annimmt. Alleine auf der syntaktischen Ebene (bei
gleichbleibender Wortklasse) finden wir z.B.
Dazu kommen
morphologische und semantische Ambiguitäten. Jede 2-fach Ambiguität verdoppelt
die Anzahl der Lesarten. Hunderte von Lesarten für komplexe Sätze sind üblich.
Bei gewissen
Sätzen ist kaum auf eine erfolgreiche maschinelle Analyse zu hoffen. Auf der
part-of-speech - Ebene fast unlösbar ist beispielsweise:
Entweder oder
ist jetzt sowohl als auch. (SBB RailLink)
Zur Unterhaltung:
http://www.departments.bucknell.edu/linguistics/synhead.html
Treebanks sind
syntaktisch annotierte Korpora. Zusätzlich zu part-of-speech tags (siehe Taggingvorlesung)
werden Projektionstags verwendet. Die Annotation versucht möglichst
theorieneutral und einfach zu bleiben, was u.A. zur Folge hat:
Beispiel 1:
( (S (NP-SBJ (NNP Mr.) (NNP Vinken) )(VP (VBZ is)
(NP-PRD (NP (NN chairman) ) (PP (IN of) (NP (NP (NNP Elsevier) (NNP N.V.) ) (, ,) (NP (DT the) (NNP Dutch) (VBG publishing) (NN group) ))))) (. .) ))
Beispiel 2:
( (S (NP-SBJ (DT The) (NN thrift) (VBG holding) (NN company) ) (VP (VBD said) (SBAR (-NONE- 0) (S (NP-SBJ-1 (PRP it) ) (VP (VBZ expects) (S (NP-SBJ (-NONE- *-1) ) (VP (TO to) (VP (VP (VB obtain) (NP (JJ regulatory) (NN approval) )) (CC and) (VP (VB complete) (NP (DT the) (NN transaction) )) (PP-TMP (IN by) (NP (NN year-end) ))))))))) (. .) ))
Beispiel 3:
( (S (NP-SBJ (PRP We) ) (VP (VBP 're) (VP (VBG talking) (PP-CLR (IN about) (ADVP-TMP (ADVP (NP (NNS years) ) (IN ago) ) (SBAR (IN before) (S (NP-SBJ (NN anyone) ) (VP (VBD heard) (PP-CLR (IN of) (S-NOM (NP-SBJ (NN asbestos) ) (VP (VBG having) (NP (DT any) (JJ questionable) (NNS properties) )))))))))))(. .) ))
Disambiguierungsentscheidungen
(meist unbewusst) beruhen auf syntaktischer und semantischer Erfahrung. Die
syntaktische Erfahrung lässt sich direkt, die semantische Erfahrung zumindest
simuliert durch ein statistisches System modellieren. Welche syntaktischen
Strukturen sind häufiger à wahrscheinlicher unter welchen Umständen?
Diese Strukturen
kann man mit verschiedenen Tools nach Mustern absuchen. Ein solches Tool heisst
tgrep. Wie der Name vorschlägt ähnelt tgrep dem UNIX tool grep,
ist aber speziell für Baumstrukturen (Trees) konzipiert.
Ein Auszug aus
dem Befehlssatz von tgrep:
A < B A immediately dominates B
A <X B B is the Xth child of A (i.e. first child is A <1 B) A <-X B B is the Xth to last child of A (i.e. last child is A <-1 B) A <- B the last child of A is B (same as A <-1 B) A << B A dominates B A >> B A is dominated by B A > B A is immediately dominated by B A <<, B B is a leftmost descendant of A A <<` B B is a rightmost descendant of A A . B A immediately precedes B A .. B A precedes B A $ B A and B are sisters (note that A $ A is FALSE) A $. B A and B are sisters and A immediately precedes B A $.. B A and B are sisters and A precedes B
Die
entsprechenden Negationen, sowie auf der Ebene der Knoten reguläre Ausdrücke
und AND/OR Verknüpfungen stehen ebenfalls zur Verfügung.
Extraktionsbeispiel:
VP-ObjNP Beziehung:
Versuch 1: (Unterstreichungen hinzugefügt)latlsun1:doc 298) tgrep 'VP << NP' | more (VP (MD will) (VP (VB join) (NP (DT the) (NN board)) (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director))) (NP-TMP (NNP Nov.) (CD 29)))) (VP (VBZ is) (NP-PRD (NP (NN chairman)) (PP (IN of) (NP (NP (NNP Elsevier) (NNP N.V.)) (, ,) (NP (DT the) (NNP Dutch) (VBG publishing) (NN group)))))) (VP (VBD was) (VP (VBN named) (S (NP-SBJ (-NONE- *-1)) (NP-PRD (NP (DT a) (JJ nonexecutive) (NN director)) (PP (IN of) (NP (DT this) (JJ British) (JJ industrial) (NN conglomerate)))))))(VP (VBZ is) (ADJP-PRD (RB unusually) (JJ resilient)) (SBAR-TMP (IN once) (S (NP-SBJ (PRP it))(VP (VBZ enters)
(NP (DT the)
(NNS lungs)))))
etc....................
Kommentar: Keine
Unterscheidung Hilfsverb/Hauptverb, viel zu grosse strukturelle Distanzen
werden akzeptiert.
Versuch 2: (Unterstreichungen hinzugefügt) latlsun1:doc 314) tgrep 'VP < /NP/' | moreplease wait, compiling/computing regular expressions...done (VP (VB join) (NP (DT the) (NN board)) (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director))) (NP-TMP (NNP Nov.) (CD 29))) (VP (VBZ is) (NP-PRD (NP (NN chairman)) (PP (IN of) (NP (NP (NNP Elsevier) (NNP N.V.)) (, ,) (NP (DT the) (NNP Dutch) (VBG publishing) (NN group)))))) (VP (VBN used) (NP (-NONE- *)) (S-CLR (NP-SBJ (-NONE- *)) (VP (TO to) (VP (VB make)(NP (NNP Kent)
(NN cigarette)
(NNS filters))))))etc....................
Kommentar: Viel
besser! Einzig die Koreferenzen werden nicht aufgelöst.
Wir haben
festegestellt: Disambiguierungsentscheidungen beruhen auf syntaktischer und
semantischer Erfahrung. Welche statistischen Abhängigkeiten bestehen aber
genau?
Die
Disambiguierungsentscheidungen aus dem Trainingskorpus werden gesammelt und in
Form von Wahrscheinlichkeiten aufgerechnet. Bei einer Enscheidung E könne man
sich für A oder B entscheiden. Freq(A) ist die Anzahl der Enscheidungen für A.
P(A | E) = Freq(A) / Freq(E)P(B | E) = Freb(B) / Freq(E) Freq(E) = Freq(A) + Freq(B) à
^P(A | E) = Freq(A) / (Freq(A) + Freq(B))^P(B | E) = Freb(B) / (Freq(A) + Freq(B)) z.B. ^P(Präp. auf) = Freq(Präp. auf) / Freq(alle Präps.)
Da man die
“wirkllichen” Wahrscheinlichkeiten in der Gesamtwelt nicht kennt, sondern nur
einen kleinen Ausschnitt, den Trainingskorpus zur Verfügung hat, sind die so
errechneten Wahrscheinlichkeiten (^P) Schätzwerte (estimation). Da man davon
ausgeht, dass ein guter, grosser Trainingskorpus die bestmögliche,
wahrscheinlichste (likely) uns zur Verfügung stehende Annäherung an die
Wirklichkeit ist, nennt man dieses Schätzverfahren Maximum Likelihood
Estimation (MLE).
Die fürs
syntaktische Parsing offensichtlichste Idee ist, PSG-Regeln
Wahrscheinlichkeiten zuzuordnen. Die Wahrscheinlichkeit eines Geasmtsatzes ist
dann das Produkt der Einzelwahrscheinlichkeiten, also aller beteiligten PSG-Regeln
à Probabiulistic context-free grammars (PCFG)
Beispiel (aus [Manning & Schütze
1999] Kapitel 12, pp. 381):
Gegeben
Z.B.
P((S à NP VP) | S) = ? (erwartungsgemäss ziemlich gross)
P((NP à astronomers) | NP) = ? (erwartungsgemäss ziemlich klein)
S |
à |
NP VP |
1.0 |
NP |
à |
NP PP |
0.4 |
|
PP |
à |
P NP |
1.0 |
NP |
à |
astronomers |
0.1 |
|
VP |
à |
V NP |
0.7 |
NP |
à |
ears |
0.18 |
|
VP |
à |
VP PP |
0.3 |
NP |
à |
saw |
0.04 |
|
P |
à |
with |
1.0 |
|
NP |
à |
stars |
0.18 |
V |
à |
saw |
1.0 |
|
NP |
à |
telescopes |
0.1 |
|
|
|
|
|
NP |
à |
planets |
0.1 |
RULE P ( (S 1.0(NP (astronomers)) 0.1
(VP 0.7(V (saw)) 1.0
(NP 0.4 (NP (stars)) 0.18 (PP 1.0 (P (with)) 1.0 (NP (ears)) 0.18 ) ) --------- ) 0.0009072) ) ========= ( (S 1.0 (NP (astronomers)) 0.1 (VP 0.3 (VP 0.7 (V (saw)) 1.0 (NP (stars)) 0.18 ) (PP 1.0 (P (with)) 1.0 (NP (ears)) 0.18) ---------
) 0.0006804) ) =========
Während PCFGs viele Strukturen richtig
disambiguieren, vernachlässigen sie einige wichtige Zusammenhänge. In
kontextfreien Grammatiken lassen sich generell nur Zusammenhänge zwischen
Mutter- und Tochterknoten abbilden, also z.B. von VP zu V oder NP zu N.
Falls die Wörter telescopes und planet
dieselbe lexikalische Wahrscheinlichkeit haben, so werden die Sätze
Jeweils gleich disambiguiert. Die obige
Beispielgrammatik gibt der Anbindung von PPs an NPs ganz simpel strukturelle
Präferenz. Die Abhängigkeit zwischen Verb und dem Nomen im PP erstreckt sich
über mehrere Syntaxregeln, wie eine unbeschränkte Abhängigkeit. Viel mächtigere
kontextsensitive Grammatiken müssten zum Einsatz kommen.
Lexikalisierte PCFGs sind wesentlich
komlexere statistische Modelle. In ihnen jeweils der lexikalische Kopf einer
Konstituente mitberücksichtigt. Die syntaktische Repräsentation der NP-PP
Anbindungsversion von Astronomers saw stars with planets ist dann (ohne
Wahrscheinlichkeitsangaben):
( (S_saw (NP_astronomers (astronomers)) (VP_saw (V_saw (saw)) (NP_stars (NP_stars (stars)) (PP_with (P_with (with)) (NP_planets (planets))
) ) ) ) )
Die Syntaxregeln
NP_stars à NP_stars PP_with
VP_saw à VP_saw PP_with
können nun auf lexikalisches Material
zurückgreifen. Sätze
wie
·
Astronomers
saw stones through telescopes
VP_saw à VP_saw PP_on
VP_saw à VP_saw PP_through
NP_stones à NP_stones PP_on
NP_stones à NP_stones PP_through
werden nun wohl richtig gewertet, da saw
eine Präferenz (=hohe Wahrscheinlichkeit) für through hat, während stones
wohl eine hohe Präferenz für on hat.
In Astronomers saw stars with planets kommt
jedoch eine wesentliche lexikalische Information vom Nomen planets
innerhalb der PP, also von Nicht-Kopf-Konstituenten in den entscheidenden
Regeln (beachte allerdings, dass LFG oder DG teilweise (auch) die Präposition
als Kopf betrachten – hier ein Grund).
Lexikalische Dependenzmodelle (LD)
konzentrieren sich direkt auf die lexikalischen Abhängigkeiten. Anstelle der
strukturellen Beziehungen verwendet man (so weit wie möglich) funktionale, z.B.
Verb-Subjekt oder Verb-Objekt. Wie üblich in DG wird die kategoriale Projektion
(z.B. N ß NP, V ß VP, allenfalls MD ß VP) allerdings als deterministsich vorausgesetzt.
(Un)abhängigkeitsannahmen, Back-Off,
Smoothing
Anders gesagt, es werden andere
statistische Abhängigkeits- und Unabhängigkeitsannahmen gemacht.
Das nicht-lexikalisierte PCFG Modell ist
Das LD Modell ist
·
Abhängig von
der lexikalischen Information in bezug auf die funktionalen Relationen (die
sich teilweise in der Struktur wiederspiegeln)
·
Unabhängig
von der Projektion, was aber dennoch verschiedene Expansionen erlaubt: V ß VP, MD ß VP.
Ein statistisch-syntaktisches Gesamtmodell
würde am liebsten überhaupt keine Unabhängigkeitsannahmen machen. Das führt
aber stets zu
PP-Anbindung ist abhängig von
Statistisch lassen sich miteinander
vergleichen:
· P(Verbanbindung | Verb, Präp, Description Noun)
· P(Nomenanbindung | Verb, Präp, Description Noun)
Nehmen wir an, dass wir aus dem
Trainingscorpus u.A. folgende lemmatisierte Frequenzangaben hätten (in
Prologformat, das Prädikat freq_verb_pp zähle dabei die Fälle von
PP-Anbindung ans Verb)
freq_noun_pp(stars, with, telescope, 1).freq_noun_pp(stars, with, planets, 12).freq_verb_pp(see, with, telescope, 15).freq_verb_pp(see, with, glass, 9).freq_verb_pp(observe, with, binocular, 5).
, und wir den Satz Astronomers see
stars with binoculars parsen wollen. Wir haben keine Angaben über (see,
with, binoculars,_) oder (stars, with, binoculars,_), weil sie im
Traininskorpus nie erschienen. Da sowohl N als V offene Wortklassen sind,
decken auch riesige Korpora längst nicht alle Fälle ab.
Wir haben ein Sparse Data Problem. Die
Vergabe des Wertes 0 für die Frequenz hätte zur Folge, dass jede Lesart Satz,
in dem see stars with binoculars erscheint, die Wahrscheinlichkeit 0
hätte. Alle anderen Parsingwertungen im gleichen Satz würden ausgelöscht, je
nach Sichtweise wird der Satz gar als unmöglich eingestuft.
Folgende miteinander kombinierbare
Rückgriffe erlauben es, die Situation dennoch zu retten:
P(Verb/Nomenanbindung | Verb/Nomen, Präp, Description Noun) P(Verb/Nomenanbindung | Verb/Nomen, Präp, Durchschnitt aller vorhandenen Description Nouns).
Für
PP-Anbindung hat sich folgendes Back-Off Schema bewährt ( A >> B
bedeutet: Falls keine Daten für A, verwende B):
P(Verb/Nomenanbindung | Verb/Nomen, Präp, Description Noun) >> P(Verb/Nomenanbindung | Verb/Nomen, Präp, Ø Description Nouns). >> P(Verb/Nomenanbindung | Ø Verben/Nomina, Präp, Description Noun). >> P(Verb/Nomenanbindung | Ø Verben/Nomina, Präp, Ø Description Nouns). >> P(Verb/Nomenanbindung | Ø Verben/Nomina, Ø Präp, Ø Description Nouns).
Die
letzte Back-Off Option wird nicht mehr unbedingt berechnet, sondern führt zur Default
NP-PP Anbindung – etwa 2/3 aller PP-Anbindungen sind NP-PP Anbindungen.
Wir haben gesehen, dass Objekte direkt
unter der VP des Hauptverbes auftreten (tgrep 'VP < /NP/')
Für lexikalische Dependenzbeziehungen
müssen die Köpfe der betroffenen Phrasen extrahiert werden. Vollverbobjekte und
Kopulakomplemente werden einander gleichgestellt. Der Backquote ` bedeutet in
der tgrep Syntax, dass nur das Resultat des unmittelbar folgenden Ausdrucks
ausgegeben wird. Die Resultate müssen nur noch mittels eines trivialen
Perlskripts z.B. in Prolog überführt werden.
1. Versuch VP<ObjNP:
tgrep 'VP << `/VB/ < (/NP$/|NP-PRD << `/NN/)'
liefert nicht unbedingt den Kopf, sondern möglicherweise nur
den ersten Nomen des untersten NPs. So in der VP
(VP (VB make)
(NP (NNP Kent)
(NN cigarette) (NNS filters))))))
, wo man als Resultat
(VB make)
(NNP Kent)
erhält.
Bei einem NP, der mehrere Nomen enthält, ist der Kopf (in aller Regel) der letzte Nomen:
2. Versuch VP<ObjNP:
tgrep 'VP << `/VB/ < (/NP$/|NP-PRD <- `/NN/)
Dies liefert aber nur Ergebnisse für nichtkomplexe NPs. Komplexe NPs dominieren nur indirekt einen Nomen und müssen separat behandelt werden.
Vorläufige Lösung VP<ObjNP:
SIMPLE tgrep 'VP << `/VB/ < (/NP$/|NP-PRD <- `/NN/)COMPLEX tgrep 'VP << `/VB/ < (/NP$/|NP-PRD << (NP <- `/NN/))Bsp.: Nomen –
PP
Wir wollen jeweils den Kopf der NP, der PP und der NP_in_der_PP extrahieren
1. Versuch VP<PP_verbhead+prep+descNoun:
tgrep 'NP << `/NN/ < (/PP/ < `/IN/ < (NP << `/NN/))'
liefert wiederum nicht unbedingt den Kopf, sondern
möglicherweise nur den ersten Nomen des Descr.NPs
(1) For simple superNP + complex descNP:tgrep '/NP/ < (NP <- `/NN/) < (/PP/ < `/IN/ < (NP << (NP <- `/NN/)))' (2) For simple superNP + simple descNP:tgrep '/NP/ < (NP <- `/NN/) < (/PP/ < `/IN/ < (NP <- `/NN/))' (3) For complex superNP + complex descNP:tgrep '/NP/ < (NP << (NP <- `/NN/) < (/PP/ < `/IN/ < (NP << (NP <- `/NN/))))' (4) For complex superNP + simple descNP:tgrep '/NP/ < (NP << (NP <- `/NN/) < (/PP/ < `/IN/ < (NP <<- `/NN/)))'
Es folgt eine Demonstration
meines Dependenzparsers mit statistischer Disambigiurungskomponente.
Zum Schluss noch ein hübsches Beispiel: Arrivals for the
week ended February 22 were 155'221 bags of 60 kilos.
end
________________________________________|________________________________________
/
|
| |
\
arriv
<-subj<-
.
->sentobj->
were
__________|__________
|
______________________|_____________________
/ | \
|
/ | | |
\
. ->modpp-> week
ended_VBD
februari <-subj<-
. ->obj->
bag
|
______|______
|
|
___________|___________
|
/ | \
|
|
/ | \
Arrivals_NNS for<-prep<- .
.
were_VBD
.
->modpp->
kilo
|
__|_
___|__
___|__
______|_____
| / \
/
\
/
\
/ | \
. the_DT .
February_NNP .
155,221_CD .
of<-prep<-
.
|
|
|
|
| __|_
|
|
|
|
| / \
for_IN week_NN
22_CD
bags_NNS .
60_CD .
|
|
|
|
of_IN kilos_NNS
à Unterscheidung Objekt/Adjunkt/Satzobjekt
auch nötig