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

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

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

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

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

В 1990-е годы Джеффри Сэмпсон работал с Уильямом А. Гейлом из AT&T создать и реализовать упрощенный и легкий в использовании вариант метода Гуда – Тьюринга^[3][4] описано ниже. Различные эвристические обоснования^[5]и был предоставлен простой комбинаторный вывод.^[6]

Метод

Обозначение

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

${displaystyle N_{r}=|{xmid R_{x}=r}|}$

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

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

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

${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 )}$ означает сглаженное или скорректированное значение частоты, показанное в скобках (см. также эмпирический метод Байеса ). Обзор того, как выполнить это сглаживание, приведен ниже.

Мы хотим построить сюжет ${displaystyle log N_{r}}$ против ${displaystyle log r}$ но это проблематично, потому что для больших ${displaystyle r}$ много ${displaystyle N_{r}}$ будет ноль. Вместо пересмотренного количества, ${displaystyle log Z_{r}}$, строится по сравнению с ${displaystyle log r}$, куда Z_р определяется как

${displaystyle Z_{r}={frac {N_{r}}{0.5(t-q)}},}$

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

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

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

Вывод

Множество различных выводов приведенной выше формулы для ${displaystyle p_{r}}$ Был дан.^{[1][6][8][11]}

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

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

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

1. Хорошо, И.Дж. (1953). «Популяции видов и оценка популяционных параметров». Биометрика. 40 (3–4): 237–264. Дои:10.1093 / biomet / 40.3-4.237. JSTOR  2333344. МИСТЕР  0061330.
2. Newsise: Ученые объясняют и уточняют «загадочную» формулу вероятности, популярный обзор Орлицкий А., Сантханам Н.П., Чжан Дж. (2003). «Всегда хороший Тьюринг: асимптотически оптимальная оценка вероятности». Наука. 302 (5644): 427–31. Bibcode:2003Наука ... 302..427O. Дои:10.1126 / science.1088284. PMID  14564004.
3. Сэмпсон, Джеффри и Гейл, Уильям А. (1995) Оценка частоты Гуд-Тьюринга без слез
4. Орлицкий, Алон; Суреш, Ананда (2015). "Оценка конкурентного распределения: почему Гуд-Тьюринг хорош?" (PDF). Системы обработки нейронной информации (NIPS): 1–9. Получено 28 марта 2016.
5. Надас, А. (1991). «Хорошо, Елинек, Мерсер и Роббинс об оценке вероятностей Тьюринга». Американский журнал математических и управленческих наук. American Sciences Press Сиракузы, Нью-Йорк, США. 11 (3–4): 299–308. Дои:10.1080/01966324.1991.10737313.
6. Хаттер, Маркус (2014). «Преобразование офлайн в онлайн». Proc. 25-я международная конф. по теории алгоритмического обучения (ALT'14). LNAI. 8776. Блед, Словения: Springer. С. 230–244. arXiv:1407.3334. Дои:10.1007/978-3-319-11662-4_17.
7. Гейл, Уильям А. (1995). «Гуд – Тьюринг сглаживание без слез». Журнал количественной лингвистики. 2 (3): 3. CiteSeerX  10.1.1.110.8518. Дои:10.1080/09296179508590051.
8. Лекция 11: Оценка Гуда – Тьюринга. CS 6740, Корнельский университет, 2010 г. [1]
9. Церковь, К; Гейл, В. (1991). «Сравнение усовершенствованных методов оценки Гуда – Тьюринга и удаленных методов оценки вероятностей английских биграмм».
10. Сэмпсон, Джеффри (2005) Простой оценщик частоты Гуда – Тьюринга (код на C)
11. Фаваро, Стефано; Нипоти, Бернардо; Тех, Йи Уай (2016). «Повторное открытие оценок Гуда-Тьюринга через байесовские непараметрики». Биометрия. Интернет-библиотека Wiley. 72 (1): 136–145.

Рекомендации

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

• Дэвид А. Макаллестер, Роберт Шапир (2000) О скорости сходимости оценок Гуда – Тьюринга, Труды тринадцатой ежегодной конференции по вычислительной теории обучения стр. 1–6
• Дэвид А. Макаллестер, Ортис, Луис (2003) Неравенства концентраций для отсутствующей массы и ошибки правила гистограммы, Журнал исследований в области машинного обучения стр. 895–911