Oszacowanie częstotliwości Good-Turinga

Oszacowanie częstotliwości Good-Turinga jest techniką statystyczną służącą do szacowania prawdopodobieństwa napotkania obiektu dotychczas niewidzianego gatunku, biorąc pod uwagę zestaw wcześniejszych obserwacji obiektów z różnych gatunków. Podczas wyciągania kul z urny „obiektami” byłyby kule, a „gatunkami” byłyby różne kolory kulek (skończona, ale nieznana liczba). Po narysowaniu ${\$ kulek, $Displaystyle R_ {\ tekst {czarny}}}$ czarnych kulek i ${\ Displaystyle R _ {\ tekst {zielony}}}$ zielone kule, zapytalibyśmy, jakie jest prawdopodobieństwo wylosowania kulki czerwonej, czarnej, zielonej lub o wcześniej niewidzianym kolorze.

Tło historyczne

Oszacowanie częstotliwości Good-Turinga zostało opracowane przez Alana Turinga i jego asystenta IJ Gooda jako część ich metod stosowanych w Bletchley Park do łamania niemieckich szyfrów dla maszyny Enigma podczas II wojny światowej . Turing początkowo modelował częstotliwości jako rozkład wielomianowy , ale uznał to za niedokładne. Dobrze rozwinięte wygładzania poprawiające dokładność estymatora.

Odkrycie zostało uznane za znaczące, gdy Good opublikował je w 1953 roku, ale obliczenia były trudne, więc nie zostało wykorzystane tak szeroko, jak mogłoby być. Metoda zyskała nawet literacką sławę dzięki powieści Roberta Harrisa Enigma .

W latach 90. Geoffrey Sampson współpracował z Williamem A. Gale z AT&T nad stworzeniem i wdrożeniem uproszczonego i łatwiejszego w użyciu wariantu metody Good-Turinga opisanej poniżej. Przedstawiono różne uzasadnienia heurystyczne i proste wyprowadzenie kombinatoryczne.

Metoda

Estymator Gooda-Turinga jest w dużej mierze niezależny od rozkładu częstotliwości gatunków.

Notacja

Zakładając, że ${\ Displaystyle \; 1 \ kropki, X ~.}$ $różne$ gatunki, wyliczone
Wtedy wektor częstotliwości ma elementy , które podają $\ Displaystyle \$ zaobserwowanych osobników $, {\ bar {R}} \;,$ dla gatunku ${\ Displaystyle \, x \;.}$
Częstotliwość $_$ _ _ $}$ w wektorze (tj. wśród elementów ) : ${\ Displaystyle {\ bar {R}$

{\ Displaystyle N_ {r} = {\ Bigl |} \ lewo \ {x \ mid R_ {x} = r \ prawo \} {\ Bigr |} ~.}

Na przykład ${\ displaystyle N_ {1}}$ to liczba gatunków, dla których zaobserwowano tylko jeden osobnik. Należy zauważyć, że całkowitą liczbę obserwowanych obiektów można znaleźć na podstawie ${\ displaystyle \, N \,,}$

{\ Displaystyle N = \ suma _ {r = 1} ^ {\ infty} rN_ {r} = \ suma _ {x = 1} ^ {X} R_ {x} ~.}

Obliczenie

Pierwszym krokiem w obliczeniach jest oszacowanie prawdopodobieństwa, że obserwowany w przyszłości osobnik (lub następny obserwowany osobnik) należy do nieznanego dotąd gatunku. To oszacowanie to:

{\ Displaystyle p_ {0} = {\ Frac {N_ {1}} {N}} ~.}

$razy$ , który był widziany . Dla jednego gatunku oszacowanie to wynosi:

{\ Displaystyle p_ {r} = {\ Frac {\; (r + 1) \; S (N_ {r + 1}) \;} {N \, S (N_ {r})}} ~.}

Tutaj notacja oznacza $skorygowaną$ lub wartość w nawiasach Omówienie sposobu wykonywania tego wygładzania znajduje się w następnej sekcji (patrz także empiryczna metoda Bayesa ).

$razy$ . grupy gatunków widzianych ), można użyć następującego wzoru:

{\ Displaystyle {\ Frac {\; (r + 1) \, S (N_ {r + 1}) \;} {N}} ~.}

Wygładzanie

Aby wygładzić błędne wartości w dużym $N$ , chcielibyśmy sporządzić wykres $;}$ $\ displaystyle$ kontra ${\ Displaystyle \; \ log r \;},$ ale jest to problematyczne, ponieważ dla dużego ${\ displaystyle \, r \,}$ wiele będzie wynosić zero ${\ displaystyle \, N_ {r} \,}$ . Zamiast skorygowanej ilości, ${\ Displaystyle \; \ log Z_ {r} \;,}$ jest wykreślany względem ${\ Displaystyle \; \ log r ~,}$ gdzie ${\ Displaystyle \, Z_ {r} \,}$ jest zdefiniowany Jak

{\ Displaystyle Z_ {r} = {\ Frac {N_ {r}} {\; {\ tfrac {1} {2}} \ (tq) \; }}~,}

i gdzie $q$ , $r$ i $t$ to trzy kolejne indeksy dolne z liczbami niezerowymi ${\ Displaystyle \; N_ {q}, N_ {r}, N_ {t} \;}$ . W szczególnym przypadku, gdy $r$ wynosi 1, przyjmij, że $q$ wynosi 0. W odwrotnym szczególnym przypadku, gdy ${\ mathsf {ostatni}} \;}$ _ z ostatniego $_ \,r_{\mathsf {ostatni}}-q\;,}$ niezerowa $_$ za więc ${\ Displaystyle \; Z_ {r _ {\ mathsf {ostatni}}} = {\ Frac {N_ {r _ {\ mathsf {ostatni}}}} {\; r _ {\ mathsf {ostatni}} -q \;}} ~.}$

Prosta regresja liniowa jest następnie dopasowywana do wykresu log-log.

Dla małych wartości rozsądne jest ustawienie $}$ ${\ Displaystyle \; S (N_ {r}) = N_ {r} \;$ czyli , wygładzanie nie jest wykonywane.

W przypadku dużych wartości $r$ , wartości ${\ Displaystyle \; S (N_ {r}) \;}$ są odczytywane z linii regresji. Można użyć procedury automatycznej (nieopisanej tutaj) do określenia, w którym momencie powinno nastąpić przejście z wygładzania bez wygładzania do wygładzania liniowego. ^{[ potrzebne pełne cytowanie ]} Kod metody jest dostępny w domenie publicznej.

Pochodzenie

Podano wiele różnych wyprowadzeń powyższego wzoru na ${\ displaystyle p_ {r}} .$

Jednym z najprostszych sposobów motywowania formuły jest założenie, że następny element będzie zachowywał się podobnie do poprzedniego. Ogólna idea estymatora polega na tym, że obecnie widzimy przedmioty nigdy nie widziane z określoną częstotliwością, przedmioty widziane raz z określoną częstotliwością, przedmioty widziane dwukrotnie z określoną częstotliwością i tak dalej. Naszym celem jest oszacowanie prawdopodobieństwa każdej z tych kategorii dla następnej przedmiot zobaczymy. Innymi słowy, chcemy poznać aktualne tempo, w jakim przedmioty widziane dwa razy stają się przedmiotami widzianymi trzykrotnie i tak dalej. Ponieważ nie zakładamy niczego na temat podstawowego rozkładu prawdopodobieństwa, na początku brzmi to trochę tajemniczo. empirycznie obliczyć te prawdopodobieństwa dla poprzedniego przedmiotu, który widzieliśmy, nawet zakładając, że nie pamiętamy dokładnie, który to był przedmiot: Weź wszystkie przedmioty, które widzieliśmy do tej pory (w tym wielokrotności) — ostatni przedmiot, który widzieliśmy, był losowy z nich, wszystkie równie prawdopodobne. W szczególności prawdopodobieństwo, że zobaczyliśmy przedmiot dla ${\ Displaystyle (r + 1)}$ ten czas to po prostu szansa, że był to jeden z elementów, które widzieliśmy teraz ${\ Displaystyle r + 1}$ razy, a mianowicie ${\ Displaystyle {\ Frac {(r + 1) N_ {r + 1}} {N}}}$ . Innymi słowy, nasza szansa na zobaczenie przedmiotu, który był widziany r razy wcześniej, wynosiła ${\ Displaystyle {\ Frac {(r + 1) N_ {r + 1}} {N}}}$ . Więc teraz po prostu zakładamy, że ta szansa będzie mniej więcej taka sama dla następnego przedmiotu, który zobaczymy. $\ displaystyle p_$ powyższy wzór na ustawiając ${0}}$ . Aby uzyskać prawdopodobieństwo, że konkretny element z elementów będzie następnym widzianym, musimy podzielić to prawdopodobieństwo (od r > { $N_{r}$ $r>0$ some przedmiot, który był widziany r razy) spośród $możliwości,$ być konkretny przedmiot. To daje nam wzór ${\ Displaystyle \; p_ {r} = {\ Frac {(r + 1) N_ {r + 1}} {NN_ {r }}}}$ . Rzeczywiste dane będą oczywiście prawdopodobnie nieco zaszumione, dlatego warto najpierw wygładzić wartości, aby lepiej oszacować, jak szybko rośnie liczba kategorii, co daje wzór pokazany powyżej. To podejście jest w tym samym duchu, co wyprowadzanie standardowego estymatora Bernoulliego poprzez proste pytanie, jakie były dwa prawdopodobieństwa dla poprzedniego rzutu monetą (po wymieszaniu prób widzianych do tej pory), biorąc pod uwagę tylko bieżący wynik, nie zakładając nic o podstawowym rozkładzie .

Zobacz też

Bibliografia

David A. McAllester, Robert Schapire (2000) On the Convergence Rate of Good-Turing Estimators , Proceedings of the trzynasta doroczna konferencja na temat obliczeniowej teorii uczenia się, str. 1–6
David A. McAllester, Ortiz, Luis (2003) Concentration Inequalities for the Missing Mass and Histogram Rule Error , Journal of Machine Learning Research, s. 895–911