Stochastische Attribut-Wert

 Documents

 21 views
of 28
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Stochastische Attribut-Wert- Grammatiken Universität Potsdam – Institut für Linguistik Hauptseminar Stochastische Lernalgorithmen Gerhard Jäger –…
Share
Transcript
Stochastische Attribut-Wert- Grammatiken Universität Potsdam – Institut für Linguistik Hauptseminar Stochastische Lernalgorithmen Gerhard Jäger – Referent: Rainer Ludwig Überblick • Stochastische kontextfreie Grammatiken – Empirical Relative Frequency • Übergang von (S)CFG zu (S)AVG • Stochastische AVG – Random Fields – Improved Iterative Scaling Stochastische CFG 1. S  AA 1 = 1/2 S 1 2. SB 2 = 1/2 3. Aa 3 = 2/3 x= A A 4. Ab 4 = 1/3 5. Baa 5 = 1/2 a a 6. Bbb 6 = 1/2 3 3 1 2 2 2 q1 ( x)  1   3   3     2 3 3 9 Parameterabschätzung • Bestimmung der Werte der Gewichte i • Diese sollen das Trainingskorpus bestmöglich reflektieren • D. h.: Die Distribution q(x), die durch die i bestimmt wird, soll der Distribution im Trainingskorpus ~ p(x) möglichst nahe kommen Empirische Distribution in einem Korpus x1 x2 x3 x4 S S S S A A A A B B a a b b a a b b c= 4x 2x 3x 3x ~p  4/12 2/12 3/12 3/12 q1 = 2/9 1/18 1/4 1/4 Kullback-Leibler-Divergenz • Maß für die Unähnlichkeit zwischen Distributionen (≙ relative Entropie) ~ p ( x) D( p || q)   p ( x) ln ~ ~ x q ( x) Empirical Relative Frequency (ERF) • Jede Regel i der Grammatik bekommt eine Häufigkeitsfunktion fi(x) zugewiesen • p[f]: Erwartungswert von f unter Wahrscheinlichkeitsverteilung p, d. h. p f    p( x) f ( x) x • i werden so gewählt, dass sie proportional zu p f i  sind ~ Empirical Relative Frequency (ERF) • ERF ermittelt die besten Gewichte für eine gegebene CFG bei einer gegebenen empirischen Distribution S -> AA S ->B A -> a A -> b B -> aa B -> bb p pf1 pf2 pf3 pf4 pf5 pf6 x1 1/3 1/3 0 2/3 0 0 0 x2 1/6 1/6 0 0 1/3 0 0 x3 1/4 0 1/4 0 0 1/4 0 x4 1/4 0 1/4 0 0 0 1/4 p[f] = 1/2 1/2 2/3 1/3 1/4 1/4 beta = 1/2 1/2 2/3 1/3 1/2 1/2 Empirische Distribution in einem Korpus x1 x2 x3 x4 S S S S A A A A B B a a b b a a b b c= 4x 2x 3x 3x ~ p 4/12 2/12 3/12 3/12 q1 = 2/9 1/18 1/4 1/4 4  q (x )  7 9  1 i 1 1 i Attribut-Wert-Grammatiken und DAGs 1. S  1:A 2:A <1 1> = <2 1> S 2. S  1:B 1 2 3. A  1:a 4. A  1:b A A 5. B  1:a 1 1 6. B  1:b a Attribut-Wert-Grammatiken und DAGs x1 x2 x3 x4 S S S S A A A A B B a b a b S  1:A 2:A <1 1> = <2 1> S  1:B A  1:a A  1:b B  1:a B  1:b Stochastische AVG 1. S  1:A 2:A <1 1> = <2 1> 1 = 1/2 2. S  1:B 2 = 1/2 3. A  1:a 3 = 2/3 4. A  1:b 4 = 1/3 5. B  1:a S 1 5 = 1/2 6. B  1:b 1 2 6 = 1/2 A A 1 2 2 2 1 1  2 ( x )  1   3   3     3 2 3 3 9 a 3 n Allgemein:  ( x)    i f i ( x ) i 1 Empirische Distribution in einem Korpus x1 x2 x3 x4 S S S S A A A A B B a b a b c= 4x 2x 3x 3x ~p  4/12 2/12 3/12 3/12 2 = 2/9 1/18 1/4 1/4 Σ = 7/9 q2 = 2/7 1/14 9/28 9/28 Σ=1 Alternative Regelgewichte 1. S  1:A 2:A <1 1> = <2 1> 1  3  2 2 62 2 2. S  1:B 2  3 62 2 3. A  1:a 3  2 1 2 4. A  1:b 4  1 1 2 5. B  1:a 5  12 6. B  1:b 6  12 Wahrscheinlichkeitsverteilung mit den neuen Gewichten x1 x2 x3 x4 S S S S A A A A B B a b a b c= 4x 2x 3x 3x ~p  4/12 2/12 3/12 3/12 3 2 3 2 93 2 93 2 3  =  7 14 28 28 3 2 q = 1/3 1/6 1/4 1/4 Random Fields • Wahrscheinlichkeitsverteilung über Konfigurationen (hier DAGs) • Gewicht einer Konfiguration ist das Produkt der Gewichte bestimmter Merkmale dieser Konfiguration  ( x)    i fi ( x ) i • Wahrscheinlichkeit einer Konfiguration ergibt sich aus der Normalisierung des Gewichts Merkmale in Random Fields • Merkmale können lokale Bäume (Regelanwendungen) sein, müssen aber nicht • Keine Beschränkung für die Summe der Gewichte von Regeln mit gleicher LHS (vorher: =1) Ein Beispiel für Merkmale Merkmale: S S S S A A A A A B B 1 B a 2 a b a b = 2 3/2 f1 = 2 0 0 0 f2 = 0 0 1 1 ~ qp = 2 1 3/2 3/2 q= 1/3 1/6 1/4 1/4 Parameterabschätzung • Es müssen nicht mehr nur die Werte der Gewichte i bestimmt werden, sondern auch die Merkmale fi ausgewählt werden • Ziel weiterhin: Minimierung der Kullback- Leibler-Divergenz D ( ~ p || q ) • Lösung: Improved Iterative Scaling Improved Iterative Scaling (IIS) 1. Beginne mit dem Nullfeld, i. e. ohne Merkmale 2. Merkmalsauswahl. Wähle das beste Merkmal und füge es dem Feld hinzu. 3. Anpassen der Gewichte. Passe für alle Merkmale die Gewichte an. 4. Iteriere, bis das Feld nicht mehr besser wird. Das Nullfeld S S S S A A A A B B a b a b ~ p 1/3 1/6 1/4 1/4 = 1 1 1 1 q= 1/4 1/4 1/4 1/4 D( ~ p || q )  0,03 Bestandteile eines Modells 1. Eine AVG G 2. Eine Menge von Initialgewichten θ für die Regeln in G  Initialdistribution p0 3. Eine Menge von Merkmalen f1,..., fn mit Gewichten β1,..., βn  Felddistribution q 1 q( x)  p0 ( x)  i fi ( x ) Z i Merkmalsauswahl • Merkmale sind in unserem Beispiel Sub-DAGs • Diese werden aus atomaren Merkmalen (= einzelnen DAG-Knoten) zusammengebaut • In Schritt 2 von IIS werden alle möglichen neuen Merkmale mit ihrem jeweils besten Gewicht betrachtet • Es wird dasjenige Merkmal ausgewählt, das die größte Reduktion der KLD bringt Merkmalsauswahl – Beispiel S S S S A A A A B B a b a b ~ p 1/3 1/6 1/4 1/4 a = 7/5 1 7/5 1 qa = 7/24 5/24 7/24 5/24 ~ p ~ p ln  0,04 – 0,04 – 0,04 0,05 D = 0,01 qa B = 1 1 1 1 qB = 1/4 1/4 1/4 1/4 ~ p ~  p ln 0,10 – 0,07 0 0 D = 0,03 qB Auswahl des Gewichts für ein gewähltes Merkmal • Das neue Gewicht β soll so gewählt werden, dass der Erwartungswert von f dem empirischen entspricht, also q   f   ~ p f  • Wenn L(G) sehr groß (unendlich) ist, lässt sich die Gleichung nicht ohne weiteres lösen  Random Sampling Anpassen der Gewichte • Nach dem Hinzufügen eines neuen Merkmals mit einem bestimmten Gewicht ist es i. a. nötig, die Gewichte (β1,..., βn) aller Merkmale anzupassen (Schritt 3 von IIS) • D. h. gesucht sind Faktoren (δ1,...,δn), um die neuen Gewichte (δ1β1,...,δnβn) zu ermitteln Anpassen der Gewichte • Auch hier soll gelten: qneu  f i   ~ p f i  • Für qneu gilt: qneu ( x)  p0 ( x)  j  j  1 f j ( x) Z j 1  qalt ( x)  j f j ( x) Z j qneu ( x)  qalt ( x)  i f j ( x) Annäherung: j  qalt ( x) i f #( x ) Anpassen der Gewichte • Annäherungsformel für die Faktoren δi:  qalt  i f#  f i  p f i  ~ • Iterieren, um die besten Gewichte zu erhalten • Auch hier muss eventuell auf Sampling zurückgegriffen werden
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks