Seite 1 von 1

Held Out und Deleted Estimation

Verfasst: 29. Jul 2013 11:06
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

Re: Held Out und Deleted Estimation

Verfasst: 29. Jul 2013 15:45
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.

Re: Held Out und Deleted Estimation

Verfasst: 29. Jul 2013 16:50
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