Held Out und Deleted Estimation

Moderator: Algorithms of Language Technology

Romeo
Erstie
Erstie
Beiträge: 12
Registriert: 16. Nov 2011 10:03

Held Out und Deleted Estimation

Beitrag von Romeo »

Hallo,
Meine Frage bezieht sich auf Smoothing bei NGram-Modellen. Bei der Berechnung der Wahrscheinlichkeit \(P_{ho}\) für die Held Out Estimation wird folgende Formel benutzt (L4.S33):
\(P_{ho} = \frac{T_r}{N_r \cdot N}\)
Wie ist das \(N\) hier definiert? Handelt es sich um die Summe über alle \(T_r\) oder ist es die Anzahl aller NGramme in Training + Held Out Data? Wenn ich die \(P_{ho}\) für alle NGramme in T+HO addiere, dann komme ich für die erste Version (Summe über \(T_r\)) auf 1, nicht jedoch für die zweite Variante.

Falls \(N\) tatsächlich als Summe über die \(T_r\) definiert ist, wie sieht das Ganze für die Deleted Estimation aus? Hier könnte man dann doch nicht beide Male das gleiche \(N\) im Nenner verwenden, da die Teile potentiell unterschiedlich groß sind.

Mache ich da gerade einen Denkfehler?

Viele Grüße,
Roland

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Held Out und Deleted Estimation

Beitrag von Seldon »

Nach diesem PDF (die Rechnung auf Seite 2 unten scheint nicht ganz zu stimmen, aber die Beispieltabelle ist sehr aufschlussreich) ist bei unserer Held-Out-Formel Nr die Anzahl der types (verschiedenen N-Gramme) der Frequenz r im Training und N die Anzahl der token (Gesamtzahl ngrams) in HO.

Beispiel (Bigramme über Alphabet {a,b}):

Code: Alles auswählen

     training       held out
ab       3              4
aa       3              2
ba       2              1
bb       0              2
-------------------------
N        8              9
Training -> Held-Out:
\(T_3\) = 6 \(N_3\) = 2
\(T_2\) = 1 \(N_2\) = 1
\(T_0\) = 2 \(N_0\) = 1

\(P_{HO}(ab) = \frac{T_3}{N \cdot N_3} = \frac{6}{9 \cdot 2} = \frac{6}{18}\)
\(P_{HO}(aa) = \frac{6}{18}\)
\(P_{HO}(ba) = \frac{1}{9}\)
\(P_{HO}(bb) = \frac{2}{9}\)

Bei Deleted Estimation geht mein Beispiel nur auf bei N = (Training + Held Out) / 2, also hier 8,5:

Held-Out -> Training:
\(T_4\) = 3 \(N_4\) = 1
\(T_2\) = 3 \(N_2\) = 2
\(T_1\) = 2 \(N_1\) = 1

\(P_{HO}(ab) = \frac{T^{T \rightarrow H}_3 + T^{H \rightarrow T}_4}{N \cdot (N^{T \rightarrow H}_3 + N^{H \rightarrow T}_4)} =\frac{6 + 3}{8.5 \cdot (2 + 1)} \approx 0.353\)
\(P_{HO}(aa) \approx 0.265\)
\(P_{HO}(ba) \approx 0.176\)
\(P_{HO}(bb) \approx 0.196\)

was sich (vermutlich wegen der Rundung) auf 0,99 summiert.

Romeo
Erstie
Erstie
Beiträge: 12
Registriert: 16. Nov 2011 10:03

Re: Held Out und Deleted Estimation

Beitrag von Romeo »

Hey!

Danke für die ausführliche Antwort. Das war auch der Weg, den ich für wahrscheinlicher hielt.

Viele Grüße,
Roland

Antworten

Zurück zu „Algorithms of Language Technology“