Oszacowanie częstotliwości Good-Turinga - Good–Turing frequency estimation

Szacowanie częstotliwości Good-Turinga to statystyczna technika szacowania prawdopodobieństwa napotkania obiektu dotychczas niewidzianego gatunku, biorąc pod uwagę zestaw wcześniejszych obserwacji obiektów z różnych gatunków. Podczas pobierania kul z urny „przedmioty” byłyby kulami, a „gatunki” byłyby różnymi kolorami kul (skończone, ale nieznane w liczbie). Po wylosowaniu kul czerwonych, czarnych i zielonych pytamy, jakie jest prawdopodobieństwo wylosowania kuli czerwonej, czarnej, zielonej lub w niewidzianym wcześniej kolorze. ${\displaystyle R_{\tekst{czerwony}}}$${\displaystyle R_{\tekst{czarny}}}$${\displaystyle R_{\tekst{zielony}}}$

Tło historyczne

Szacowanie 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 stwierdził, że jest to niedokładne. Dobrze opracowane algorytmy wygładzania poprawiające dokładność estymatora.

Odkrycie zostało uznane za znaczące, gdy zostało opublikowane przez Good w 1953 roku, ale obliczenia były trudne, więc nie było używane 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. Podano różne heurystyczne uzasadnienia i proste wyprowadzenie kombinatoryczne.

Metoda

Notacja

• Zakładając, że zaobserwowano różne gatunki, wymieniono .${\ Displaystyle X}$${\displaystyle 1,\kropki,X}$
• Wtedy wektor częstości , , zawiera elementy, które dają liczbę osobników zaobserwowanych dla gatunku .${\displaystyle {\bar {R}}}$${\ Displaystyle R_ {x}}$${\displaystyle x}$
• Częstotliwość wektora częstotliwości, , pokazuje, ile razy częstotliwość r występuje w wektorze (tj. wśród elementów ):${\ Displaystyle (N_ {r}) _ {r = 0,1, \ ldots}}$${\displaystyle {\bar {R}}}$${\ Displaystyle R_ {x}}$

${\ Displaystyle N_ {r} = | \ {x \ średni R_ {x} = r \} |}$

Na przykład jest to liczba gatunków, dla których zaobserwowano tylko jednego osobnika. Zauważ, że całkowitą liczbę zaobserwowanych obiektów, , można znaleźć z ${\displaystyle N_{1}}$${\ Displaystyle N}$

${\ Displaystyle N = \ suma _ {r = 1} ^ {\ infty} rN_ {r}.}$

Pierwszym krokiem w obliczeniach jest oszacowanie prawdopodobieństwa, że ​​obserwowany w przyszłości osobnik (lub następny obserwowany osobnik) jest członkiem dotychczas niewidzianego gatunku. Szacunek ten wynosi:

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

Następnym krokiem jest oszacowanie prawdopodobieństwa, że ​​następny obserwowany osobnik pochodzi z gatunku, który był widziany już wiele razy. Dla pojedynczego gatunku oszacowanie to wynosi: ${\ Displaystyle r}$

${\ Displaystyle p_ {r} = {\ Frac {(r + 1) S (N_ {r + 1})} {NS (N_ {r})}}.}$

Aby oszacować prawdopodobieństwo, że następny obserwowany osobnik pochodzi z dowolnego gatunku z tej grupy (tj. grupy gatunków widzianych razy) można posłużyć się następującym wzorem: ${\ Displaystyle r}$

${\ Displaystyle {\ Frac {(r + 1) S (N_ {r + 1})} {N}}.}$

W tym przypadku notacja oznacza wygładzoną lub skorygowaną wartość częstotliwości pokazaną w nawiasie (patrz również empiryczna metoda Bayesa ). Poniżej omówiono, jak wykonać to wygładzanie. ${\displaystyle S(\cdot)}$

Chcielibyśmy stworzyć wykres kontra, ale jest to problematyczne, ponieważ dla dużych wiele będzie wynosić zero. Zamiast tego, skorygowana wielkość, , jest wykreślana w funkcji , gdzie Z _r jest zdefiniowane jako ${\ 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)}},}$

i gdzie q , r i t są kolejnymi indeksami o wartości niezerowej. Gdy r wynosi 1, weź q jako 0. Gdy r jest ostatnią niezerową częstotliwością, weź jako . ${\ Displaystyle N_ {q}, N_ {r}, N_ {t}}$${\displaystyle t}$${\displaystyle 2r-q}$

Założenie oszacowania Good-Turinga jest takie, że liczba występowania każdego gatunku jest zgodna z rozkładem dwumianowym.

Regresja liniowa jest następnie przymocowana do wykresu logarytmicznego. Dla małych wartości warto ustawić (tzn. nie wykonuje się wygładzania), natomiast dla dużych wartości r wartości są odczytywane z linii regresji. Procedura automatyczna (nie opisana tutaj) może być użyta do określenia, w którym momencie ma nastąpić przełączenie z braku wygładzania na wygładzanie liniowe. Kod metody jest dostępny w domenie publicznej. ${\ Displaystyle r}$${\ Displaystyle S (N_ {r}) = N_ {r}}$${\ Displaystyle S (N_ {r})}$

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 dwa razy z określoną częstotliwością i tak dalej. Naszym celem jest oszacowanie prawdopodobieństwa wystąpienia każdej z tych kategorii dla następnej pozycji, którą zobaczymy. Innymi słowy, chcemy wiedzieć, w jakim tempie przedmioty widziane dwa razy stają się elementami widzianymi trzykrotnie i tak dalej. Ponieważ nie zakładamy niczego na temat rozkładu prawdopodobieństwa, na początku brzmi to trochę tajemniczo. Ale niezwykle łatwo jest obliczyć te prawdopodobieństwa empirycznie dla poprzedniego elementu, który widzieliśmy, nawet zakładając, że nie pamiętamy dokładnie, który element był: Weź wszystkie elementy, które widzieliśmy do tej pory (w tym wielokrotności) — ostatni element, który widzieliśmy, był przypadkowy z nich, wszystkie równie prawdopodobne. W szczególności szansa, że ​​widzieliśmy przedmiot po raz th, jest po prostu szansą, że był to jeden z przedmiotów, które widzieliśmy teraz , a mianowicie . Innymi słowy, nasza szansa na zobaczenie przedmiotu, który był widziany wcześniej r razy, wynosiła . Więc teraz po prostu zakładamy, że ta szansa będzie mniej więcej taka sama dla następnego przedmiotu, który zobaczymy. To natychmiast daje nam powyższy wzór na , poprzez ustawienie . A dla , aby uzyskać prawdopodobieństwo, że określony jeden z elementów będzie następnym widzianym, musimy podzielić to prawdopodobieństwo (zobaczenia jakiegoś elementu, który był widziany r razy) przez możliwości, dla których konkretny element może być. To daje nam formułę . Oczywiście Twoje rzeczywiste dane będą prawdopodobnie nieco zaszumione, więc najpierw będziesz chciał wygładzić wartości, aby uzyskać lepsze oszacowanie, jak szybko rośnie liczba kategorii, co daje wzór, jak pokazano powyżej. To podejście jest w tym samym duchu, co wyprowadzenie standardowego estymatora Bernoulliego , po prostu pytając, jakie były dwa prawdopodobieństwa dla poprzedniego rzutu monetą (po zamieszaniu dotychczasowych prób), biorąc pod uwagę tylko bieżący wynik, przy założeniu niczego na temat rozkładu . ${\ 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}}}}$

Zobacz też

• Wzór na próbkowanie Ewensa
• Pseudoliczba

Bibliografia

Bibliografia