Оценка частоты Гуда – Тьюринга

Оценка частоты Гуда – Тьюринга - это статистический метод оценки вероятности встречи с объектом невиданного до сих пор вида при заданном набор прошлых наблюдений за объектами разных видов. При извлечении шаров из урны «объектами» будут шары, а «разновидностями» будут различные цвета шаров (конечное, но неизвестное число). После рисования $R\; red\; \{\backslash \; displaystyle\; R\; \_\; \{\backslash \; text\; \{red\}\}\}$красных шаров, $R\; black\; \{\backslash \; displaystyle\; R\; \_\; \{\backslash \; text\; \{black\}\}\}$черные шары и $R\; зеленый\; \{\backslash \; displaystyle\; R\; \_\; \{\backslash \; text\; \{green\}\}\}$зеленые шары, мы бы спросили, какова вероятность нарисовать красный, черный или зеленый шар. или один из ранее невидимых цветов.

Содержание

• 1 Историческая справка
• 2 Метод
• 3 Выведение
• 4 См. Также
• 5 Ссылки
• 6 Библиография

Историческая справка

Хорошо– Оценка частоты Тьюринга была разработана Аланом Тьюрингом и его помощником И. J. Good как часть своих методов, используемых в Bletchley Park для взлома German шифров для машины Enigma во время Вторая мировая война. Тьюринг сначала смоделировал частоты как полиномиальное распределение, но обнаружил, что это неточно. Хорошо разработанные алгоритмы сглаживания для повышения точности оценки.

Открытие было признано значительным, когда оно было опубликовано Good в 1953 году, но расчеты были трудными, поэтому оно не использовалось так широко, как могло бы. Этот метод даже получил некоторую литературную известность благодаря роману Роберта Харриса Enigma.

. В 1990-е годы Джеффри Сэмпсон работал с Уильямом А. Гейлом из ATT для создания и реализации упрощенного и легкого в использовании варианта метода Гуда – Тьюринга, описанного ниже. Были предоставлены различные эвристические обоснования и простой комбинаторный вывод.

Метод

Обозначение

• Предполагая, что $X\; \{\backslash \; displaystyle\; X\}$наблюдались отдельные виды, пронумерованный $1,\dots ,\; X\; \{\backslash \; displaystyle\; 1,\; \backslash \; dots,\; X\}$.
• Затем вектор частоты, $R\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{R\}\}\}$, имеет элементы $R\; x\; \{\backslash \; displaystyle\; R\_\; \{x\}\}$, которые дают количество особей, которые наблюдались для видов $x\; \{\backslash \; displaystyle\; x\}$.
• Вектор частоты частот, $(N\; r)\; r\; =\; 0,\; 1,\dots \; \{\backslash \; displaystyle\; (N\_\; \{r\})\; \_\; \{r\; =\; 0,1,\; \backslash \; ldots\}\}$, показывает, во сколько раз частота r встречается в векторе $R\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{R\}\}\}$; то есть среди элементов $R\; x\; \{\backslash \; displaystyle\; R\_\; \{x\}\}$.

$N\; r\; =\; |\; \{x\; \mid \; R\; x\; =\; r\}\; |\; \{\backslash \; displaystyle\; N\_\; \{r\}\; =\; |\; \backslash \; \{x\; \backslash \; mid\; R\_\; \{x\}\; =\; r\; \backslash \}\; |\}$

Например, $N\; 1\; \{\backslash \; displaystyle\; N\_\; \{1\}\}$количество видов, для которых наблюдалась только одна особь. Обратите внимание, что общее количество наблюдаемых объектов, $N\; \{\backslash \; displaystyle\; N\}$, можно найти из

$N\; =\; \sum \; r\; =\; 1\; \infty \; r\; N\; r.\; \{\backslash \; displaystyle\; N\; =\; \backslash \; sum\; \_\; \{r\; =\; 1\}\; ^\; \{\backslash \; infty\}\; rN\_\; \{r\}.\}$

Первым шагом в вычислении является оценка вероятности того, что будущий наблюдаемый индивидуум (или следующий наблюдаемый индивидуум) является представителем невидимого до сих пор вида. Эта оценка:

$p\; 0\; =\; N\; 1\; N.\; \{\backslash \; displaystyle\; p\_\; \{0\}\; =\; \{\backslash \; frac\; \{N\_\; \{1\}\}\; \{N\}\}.\}$

Следующим шагом является оценка вероятности того, что следующая наблюдаемая особь принадлежит к виду, который был замечен $г\; \{\backslash \; displaystyle\; r\}$раз. Для одного вида эта оценка составляет:

$p\; r\; =\; (r\; +\; 1)\; S\; (N\; r\; +\; 1)\; N\; S\; (N\; r).\; \{\backslash \; displaystyle\; p\_\; \{r\}\; =\; \{\backslash \; frac\; \{(r\; +\; 1)\; S\; (N\_\; \{r\; +\; 1\})\}\; \{NS\; (N\_\; \{r\})\}\}.\}$

Чтобы оценить вероятность того, что следующий наблюдаемый особь принадлежит к любому виду из этой группы (т. е. группа видов, виденных $r\; \{\backslash \; displaystyle\; r\}$раз), можно использовать следующую формулу:

$(r\; +\; 1)\; S\; (\; N\; r\; +\; 1)\; N.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{(r\; +\; 1)\; S\; (N\_\; \{r\; +\; 1\})\}\; \{N\}\}.\}$

Здесь обозначение $S\; (\cdot )\; \{\backslash \; displaystyle\; S\; (\backslash \; cdot)\; \}$означает сглаженное или скорректированное значение частоты, показанное в скобках (см. Также эмпирический метод Байеса ). Обзор того, как выполнить это сглаживание, приведен ниже.

Мы хотели бы построить график зависимости $log\; \; N\; r\; \{\backslash \; displaystyle\; \backslash \; log\; N\_\; \{r\}\}$от $log\; \; r\; \{\backslash \; displaystyle\; \backslash \; log\; r\; \}$, но это проблематично, потому что для больших $r\; \{\backslash \; displaystyle\; r\}$многие $N\; r\; \{\backslash \; displaystyle\; N\_\; \{r\}\}$будут быть нулевым. Вместо этого пересмотренная величина, $log\; \; Z\; r\; \{\backslash \; displaystyle\; \backslash \; log\; Z\_\; \{r\}\}$, отображается в сравнении с $log\; \; r\; \{\backslash \; displaystyle\; \backslash \; log\; r\}$, где Z r определяется как

$Z\; r\; =\; N\; r\; 0,5\; (N\; t\; -\; N\; q),\; \{\backslash \; displaystyle\; Z\_\; \{r\}\; =\; \{\backslash \; frac\; \{N\_\; \{r\}\}\; \{0,5\; (N\_\; \{t\}\; -N\_\; \{q\})\}\},\}$

и где q, r и t - последовательные индексы, имеющие $N\; q,\; N\; r,\; N\; t\; \{\backslash \; displaystyle\; N\_\; \{q\},\; N\_\; \{\; r\},\; N\_\; \{t\}\}$ненулевое значение. Когда r равно 1, возьмите q равным 0. Когда r - последняя ненулевая частота, возьмите $t\; \{\backslash \; displaystyle\; t\}$как $2\; r\; -\; q\; \{\backslash \; displaystyle\; 2r\; -q\}$.

Предположение оценки Гуда – Тьюринга состоит в том, что количество встречаемости для каждого вида следует биномиальному распределению.

A простая линейная регрессия затем подгоняется к графику log – log. Для небольших значений $r\; \{\backslash \; displaystyle\; r\}$разумно установить $S\; (N\; r)\; =\; N\; r\; \{\backslash \; displaystyle\; S\; (N\_\; \{r\})\; =\; N\_\; \{r\}\; \}$(то есть сглаживание не выполняется), а для больших значений r значения $S\; (N\; r)\; \{\backslash \; displaystyle\; S\; (N\_\; \{r\})\}$считываются с линии регрессии. Можно использовать автоматическую процедуру (не описанную здесь), чтобы указать, в какой момент должен происходить переход от отсутствия сглаживания к линейному сглаживанию. Код метода доступен в открытом доступе.

Деривация

Множество разных выводов приведенной выше формулы для $pr\; \{\backslash \; displaystyle\; p\_\; \{r\}\}$были даны.

Один из простейших способов мотивировать формулу - это предположить, что следующий элемент будет вести себя так же, как предыдущий. Общая идея оценщика состоит в том, что в настоящее время мы видим невидимые предметы с определенной частотой, предметы, которые видели один раз с определенной частотой, предметы, которые видели дважды с определенной частотой, и так далее. Наша цель - оценить, насколько вероятна каждая из этих категорий, для следующего пункта, который мы увидим. Другими словами, мы хотим знать текущую скорость, с которой элементы, которые дважды просмотрели, становятся элементами, которые были просмотрены трижды, и так далее. Поскольку мы ничего не предполагаем о лежащем в основе распределении вероятностей, поначалу это звучит немного загадочно. Но очень легко эмпирически вычислить эти вероятности для предыдущего предмета, который мы видели, даже если предположить, что мы точно не помним, какой это был предмет: возьмите все предметы, которые мы видели до сих пор (включая множественности) - последний предмет, который мы видели, был случайный из них, все одинаково вероятны. В частности, вероятность того, что мы увидели элемент в $(r\; +\; 1)\; \{\backslash \; displaystyle\; (r\; +\; 1)\}$-й раз, - это просто шанс, что это был один из элементов, которые у нас есть теперь видно $r\; +\; 1\; \{\backslash \; displaystyle\; r\; +\; 1\}$раз, а именно $(r\; +\; 1)\; N\; r\; +\; 1\; N\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{(r\; +\; 1)\; N\_\; \{r\; +\; 1\}\}\; \{N\}\}\}$. Другими словами, наш шанс увидеть предмет, который видели раньше r раз, был $(r\; +\; 1)\; N\; r\; +\; 1\; N\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{(r\; +\; 1)\; N\_\; \{r\; +\; 1\}\}\; \{N\}\}\}$. Итак, теперь мы просто предполагаем, что этот шанс будет примерно таким же для следующего предмета, который мы увидим. Это сразу дает нам формулу выше для $p\; 0\; \{\backslash \; displaystyle\; p\_\; \{0\}\}$, задав $r\; =\; 0\; \{\backslash \; displaystyle\; r\; =\; 0\}$. А для $r>0\; \{\backslash \; displaystyle\; r>0\}$, чтобы получить вероятность того, что конкретный из $N\; r\; \{\backslash \; displaystyle\; N\_\; \{r\}\}$элементов будет следующим один раз, нам нужно разделить эту вероятность (увидеть какой-то элемент, который видели r раз) между $N\; r\; \{\backslash \; displaystyle\; N\_\; \{r\}\}$возможностями для того, какой конкретный элемент может быть. Это дает нам формулу $pr\; =\; (r\; +\; 1)\; N\; r\; +\; 1\; NN\; r\; \{\backslash \; displaystyle\; \backslash ;\; p\_\; \{r\}\; =\; \{\backslash \; frac\; \{(r\; +\; 1)\; N\_\; \{r\; +\; 1\}\}\; \{NN\_\; \{r\}\}\}\}$. Конечно, ваши фактические данные, вероятно, будут немного зашумленными, поэтому вам нужно сначала сгладить значения, чтобы лучше оценить, насколько быстро растет количество категорий, и это дает формулу, показанную выше. Этот подход в том же духе, что и получение стандартной оценки Бернулли , просто спрашивая, каковы две вероятности e для предыдущего подбрасывания монеты (после скремблирования испытаний, которые мы видели до сих пор), учитывая только текущий результат, при этом ничего не предполагая о базовом распределении.

См. Также

• Формула выборки Ювенса
• Псевдосчет

Ссылки

Библиография