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

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

Историческое прошлое

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

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

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

Метод

Обозначение

• Предполагая, что наблюдались отдельные виды, перечислялись .${\ displaystyle X}$${\ Displaystyle 1, \ точки, X}$
• Тогда частотный вектор имеет элементы, которые дают количество особей, которые наблюдались для видов .${\ displaystyle {\ bar {R}}}$${\ displaystyle R_ {x}}$${\ displaystyle x}$
• Вектор частот , показывает, сколько раз частота r встречается в векторе (т.е. среди элементов ):${\ displaystyle (N_ {r}) _ {r = 0,1, \ ldots}}$${\ displaystyle {\ bar {R}}}$${\ displaystyle R_ {x}}$

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

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

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

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

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

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

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

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

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

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

Мы хотели бы построить график зависимости, но это проблематично, потому что для больших многие будут равны нулю. Вместо этого пересмотренное количество отображается в зависимости от , где Z _r определяется как ${\ 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)}},}$

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

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

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

Вывод

Было дано много различных выводов вышеуказанной формулы для . ${\ displaystyle p_ {r}}$

Один из самых простых способов мотивировать формулу - предположить, что следующий элемент будет вести себя так же, как предыдущий. Общая идея оценщика состоит в том, что в настоящее время мы видим невидимые предметы с определенной частотой, предметы, которые видели один раз с определенной частотой, предметы, которые видели дважды с определенной частотой, и так далее. Наша цель - оценить, насколько вероятна каждая из этих категорий, для следующего пункта, который мы увидим. Другими словами, мы хотим знать текущую скорость, с которой элементы, которые дважды просмотрели, становятся элементами, которые были просмотрены трижды, и так далее. Поскольку мы ничего не предполагаем о лежащем в основе распределении вероятностей, поначалу это звучит немного загадочно. Но очень легко эмпирически вычислить эти вероятности для предыдущего предмета, который мы видели, даже если предположить, что мы точно не помним, какой это был предмет: возьмите все предметы, которые мы видели до сих пор (включая множественности) - последний предмет, который мы видели, был случайный из них, все одинаково вероятны. В частности, шанс, что мы видели предмет в -й раз, - это просто шанс, что это был один из предметов, которые мы сейчас видели раз, а именно . Другими словами, наш шанс увидеть предмет, который видели раньше r раз, был . Итак, теперь мы просто предполагаем, что этот шанс будет примерно таким же для следующего предмета, который мы увидим. Это сразу дает нам формулу выше , установив . И для того , чтобы получить вероятность того, что конкретный один из предметов будет следующим, который увидят, нам нужно разделить эту вероятность (увидеть какой-то предмет, который видели r раз) между возможностями, для которого конкретный предмет может быть. Это дает нам формулу . Конечно, ваши фактические данные, вероятно, будут немного зашумленными, поэтому вам нужно сначала сгладить значения, чтобы лучше оценить, насколько быстро растет количество категорий, и это дает формулу, как показано выше. Этот подход в том же духе, что и получение стандартной оценки Бернулли , просто спрашивая, каковы были две вероятности для предыдущего подбрасывания монеты (после скремблирования испытаний, замеченных до сих пор), учитывая только текущий результат, при этом ничего не предполагая о базовом распределении. . ${\ Displaystyle (г + 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}}}}$

Смотрите также

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

использованная литература

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