Gut – Schätzung der Turing-Frequenz - Good–Turing frequency estimation

Die Good-Turing-Häufigkeitsschätzung ist eine statistische Methode zur Schätzung der Wahrscheinlichkeit, einem Objekt einer bisher unbekannten Art zu begegnen, wenn eine Reihe früherer Beobachtungen von Objekten verschiedener Arten gegeben ist. Beim Zeichnen von Kugeln aus einer Urne wären die „Objekte“ Kugeln und die „Spezies“ die unterschiedlichen Farben der Kugeln (endlich, aber in ihrer Zahl unbekannt). Nachdem wir rote Kugeln, schwarze Kugeln und grüne Kugeln gezogen haben, würden wir fragen, wie hoch die Wahrscheinlichkeit ist, eine rote Kugel, eine schwarze Kugel, eine grüne Kugel oder eine Kugel mit einer zuvor nicht gesehenen Farbe zu ziehen. ${\displaystyle R_{\text{rot}}}$${\displaystyle R_{\text{schwarz}}}$${\displaystyle R_{\text{grün}}}$

Historischer Hintergrund

Die Good-Turing-Frequenzschätzung wurde von Alan Turing und seinem Assistenten IJ Good als Teil ihrer Methoden entwickelt, die in Bletchley Park zum Knacken deutscher Chiffren für die Enigma-Maschine während des Zweiten Weltkriegs verwendet wurden . Turing modellierte die Frequenzen zunächst als Multinomialverteilung , fand dies jedoch ungenau. Gut entwickelte Glättungsalgorithmen zur Verbesserung der Genauigkeit des Schätzers.

Die Entdeckung wurde als bedeutend anerkannt, als sie 1953 von Good veröffentlicht wurde, aber die Berechnungen waren schwierig, sodass sie nicht so weit verbreitet war, wie sie hätte sein können. Durch den Roman Enigma von Robert Harris erlangte die Methode sogar literarischen Ruhm .

In den 1990er Jahren arbeitete Geoffrey Sampson mit William A. Gale von AT&T zusammen , um eine vereinfachte und benutzerfreundlichere Variante der unten beschriebenen Good-Turing-Methode zu entwickeln und zu implementieren. Es wurden verschiedene heuristische Begründungen und eine einfache kombinatorische Herleitung bereitgestellt.

Die Methode

Notation

• Unter der Annahme, dass verschiedene Arten beobachtet wurden, aufgezählt .${\displaystyle X}$${\displaystyle 1,\dots,X}$
• Dann enthält der Häufigkeitsvektor , Elemente , die die Anzahl der Individuen angeben, die für Arten beobachtet wurden .${\displaystyle {\bar {R}}}$${\displaystyle R_{x}}$${\displaystyle x}$
• Der Häufigkeitsvektor, , gibt an, wie oft die Häufigkeit r im Vektor (also unter den Elementen ) vorkommt:${\displaystyle (N_{r})_{r=0,1,\ldots}}$${\displaystyle {\bar {R}}}$${\displaystyle R_{x}}$

${\displaystyle N_{r}=|\{x\mid R_{x}=r\}|}$

Ist beispielsweise die Anzahl der Arten, für die nur ein Individuum beobachtet wurde. Beachten Sie, dass die Gesamtzahl der beobachteten Objekte, , aus ${\displaystyle N_{1}}$${\displaystyle N}$

${\displaystyle N=\sum_{r=1}^{\infty}rN_{r}.}$

Der erste Schritt bei der Berechnung besteht darin, die Wahrscheinlichkeit abzuschätzen, dass ein zukünftig beobachtetes Individuum (oder das nächste beobachtete Individuum) einer bisher unbekannten Art angehört. Diese Schätzung lautet:

${\displaystyle p_{0}={\frac {N_{1}}{N}}.}$

Der nächste Schritt besteht darin, die Wahrscheinlichkeit abzuschätzen, dass das nächste beobachtete Individuum von einer Art stammt, die schon oft gesehen wurde. Für eine einzelne Art ist diese Schätzung: ${\displaystyle r}$

${\displaystyle p_{r}={\frac {(r+1)S(N_{r+1})}{NS(N_{r})}}.}$

Um die Wahrscheinlichkeit abzuschätzen, dass das nächste beobachtete Individuum von einer Art aus dieser Gruppe (dh der Gruppe von Arten, die oft gesehen wurden) stammt, kann man die folgende Formel verwenden: ${\displaystyle r}$

${\displaystyle {\frac {(r+1)S(N_{r+1})}{N}}.}$

Die Notation bedeutet hier den geglätteten bzw. angepassten Wert der in Klammern angegebenen Frequenz (siehe auch empirisches Bayes-Verfahren ). Es folgt eine Übersicht über die Durchführung dieser Glättung. ${\displaystyle S(\cdot)}$

Wir möchten , dass ein Grundstück machen von gegenüber , aber dies ist problematisch , weil für große viele Nullen. Stattdessen wird eine revidierte Größe, , gegen , aufgetragen , wobei Z _r definiert ist als ${\displaystyle \log N_{r}}$${\displaystyle \log r}$${\displaystyle r}$${\displaystyle N_{r}}$${\displaystyle \log Z_{r}}$${\displaystyle \log r}$

${\displaystyle Z_{r}={\frac {N_{r}}{0.5(tq)}},}$

und wobei q , r und t aufeinanderfolgende Indexe mit Nicht-Null sind. Wenn r 1 ist, nehmen Sie q als 0. Wenn r die letzte Nicht-Null-Frequenz ist, nehmen Sie als . ${\displaystyle N_{q},N_{r},N_{t}}$${\displaystyle t}$${\displaystyle 2r-q}$

Die Good-Turing-Schätzung geht davon aus, dass die Häufigkeit des Vorkommens für jede Art einer Binomialverteilung folgt.

Anschließend wird eine einfache lineare Regression an den Log-Log-Plot angepasst. Für kleine Werte von ist es sinnvoll zu setzen (d. h. es wird keine Glättung durchgeführt), während für große Werte von r die Werte von von der Regressionsgerade abgelesen werden. Über ein automatisches Verfahren (hier nicht beschrieben) kann festgelegt werden, an welcher Stelle von keiner Glättung auf eine lineare Glättung umgeschaltet werden soll. Code für die Methode ist im öffentlichen Bereich verfügbar. ${\displaystyle r}$${\displaystyle S(N_{r})=N_{r}}$${\displaystyle S(N_{r})}$

Ableitung

Viele verschiedene Ableitungen der obigen Formel für wurden angegeben. ${\displaystyle p_{r}}$

Eine der einfachsten Möglichkeiten, die Formel zu motivieren, besteht darin, davon auszugehen, dass sich das nächste Element ähnlich verhält wie das vorherige Element. Die Gesamtidee des Schätzers ist, dass wir derzeit nie gesehene Elemente mit einer bestimmten Häufigkeit, einmal gesehene Elemente mit einer bestimmten Häufigkeit, zweimal gesehene Elemente mit einer bestimmten Häufigkeit usw. sehen. Unser Ziel ist es, abzuschätzen, wie wahrscheinlich jede dieser Kategorien für das nächste Element ist, das wir sehen werden. Anders ausgedrückt: Wir möchten die aktuelle Rate kennen, mit der zweimal gesehene Elemente zu dreimal gesehenen Elementen werden und so weiter. Da wir nichts über die zugrunde liegende Wahrscheinlichkeitsverteilung annehmen, klingt es zunächst etwas mysteriös. Aber es ist extrem einfach, diese Wahrscheinlichkeiten für das vorherige Element, das wir gesehen haben, empirisch zu berechnen , selbst wenn wir uns nicht genau erinnern, welches Element das war: Nehmen Sie alle Elemente, die wir bisher gesehen haben (einschließlich Multiplizitäten) - das letzte Element, das wir gesehen haben, war eine zufällige davon, alle gleich wahrscheinlich. Konkret ist die Wahrscheinlichkeit, dass wir einen Gegenstand zum ten Mal gesehen haben, einfach die Chance, dass es sich um einen der Gegenstände handelte, die wir jetzt schon mal gesehen haben, nämlich . Mit anderen Worten, unsere Chance, einen Gegenstand zu sehen, der schon r- mal gesehen wurde, lag bei . Also gehen wir jetzt einfach davon aus, dass diese Chance für den nächsten Gegenstand, den wir sehen, ungefähr gleich ist. Dies gibt uns sofort die obige Formel für , indem wir . Und , um die Wahrscheinlichkeit zu erhalten , dass ein bestimmte der Elemente wird die nächste zu sehen, müssen wir diese Wahrscheinlichkeit teilen (zu sehen , einige Artikel , der gesehen wurde r - mal) unter den Möglichkeiten , für die bestimmte Element das könnte Sein. Dies gibt uns die Formel . Natürlich werden Ihre tatsächlichen Daten wahrscheinlich etwas verrauscht sein, daher sollten Sie zuerst die Werte glätten, um eine bessere Einschätzung zu erhalten, wie schnell die Kategorieanzahl wächst. Dies ergibt die Formel wie oben gezeigt. Dieser Ansatz entspricht dem Ableiten des standardmäßigen Bernoulli- Schätzers, indem einfach nach den beiden Wahrscheinlichkeiten für den vorherigen Münzwurf gefragt wird (nach dem Verwürfeln der bisher gesehenen Versuche), da nur das aktuelle Ergebnis zählt, während nichts über die zugrunde liegende Verteilung angenommen wird . ${\displaystyle (r+1)}$${\displaystyle r+1}$${\displaystyle {\frac {(r+1)N_{r+1}}{N}}}$${\displaystyle {\frac {(r+1)N_{r+1}}{N}}}$${\displaystyle p_{0}}$${\displaystyle r=0}$${\displaystyle r>0}$${\displaystyle N_{r}}$${\displaystyle N_{r}}$${\displaystyle \;p_{r}={\frac {(r+1)N_{r+1}}{NN_{r}}}}$

Siehe auch

• Ewens Probenahmeformel
• Pseudoanzahl

Verweise

Literaturverzeichnis