Китайский ресторанный процесс - Chinese restaurant process

Для использования в других целях см. Китайский ресторан (значения).

В теория вероятности, то Китайский ресторанный процесс это дискретное время случайный процесс, аналогично рассадке клиентов за столиками в китайском ресторане. Представьте себе китайский ресторан с бесконечным количеством круглых столов, каждый с бесконечной вместимостью. Покупатель 1 сидит за первым столом. Следующий покупатель либо сидит за тем же столом, что и покупатель 1, либо за следующим столом. Это продолжается, когда каждый покупатель выбирает либо сесть за занятый стол с вероятностью, пропорциональной количеству уже присутствующих клиентов (то есть они с большей вероятностью сядут за стол с большим количеством клиентов, чем с несколькими), либо с незанятым столом. Вовремя п, то п клиенты были разделенный среди м ≤ п столы (или блоки раздела). Результаты этого процесса обмениваемый, то есть порядок, в котором сидят клиенты, не влияет на вероятность окончательного распространение. Это свойство значительно упрощает ряд проблем в популяционная генетика, лингвистический анализ, и распознавание изображений.

Дэвид Дж. Олдос приписывает аналогию с рестораном Джим Питман и Лестер Дубинс в его книге 1983 года.^[1]

Формальное определение

В любое положительное целое время п, значение процесса - раздел B_п множества {1, 2, 3, ...,п}, распределение вероятностей которого определяется следующим образом. Вовремя п = 1, тривиальное разбиение {{1}} получается с вероятностью 1. В момент времени п + 1 элемент п +1 - это либо:

1. добавлен в один из блоков раздела B_п, где каждый блок выбирается с вероятностью |б|/(п + 1) где |б| это размер блока (т.е. количество элементов), или^{[сомнительный ]}
2. добавлен в раздел B_п как новый одноэлементный блок, с вероятностью 1 / (п + 1).

Сгенерированный таким образом случайный раздел имеет некоторые особые свойства. это обмениваемый в том смысле, что изменение метки {1, ...,п} не изменяет распределение раздела, и это последовательный в том смысле, что закон разделения п - 1 получено удалением элемента п из случайного раздела во время п совпадает с законом случайного разбиения в момент времени п − 1.

Вероятность, присвоенная любому конкретному разделу (без учета порядка, в котором клиенты сидят за любым конкретным столом), равна

${displaystyle Pr(B_{n}=B)={frac {prod _{bin B}(|b|-1)!}{n!}}}$

где б это блок в разделе B и |б| это размер б.

Распределение

Стол в китайском ресторане

Параметры	${displaystyle heta >0}$ ${displaystyle min {0,1,2,ldots }}$
Поддержка	${displaystyle Lin {0,1,2,ldots ,m}}$
PMF	${displaystyle {frac {Gamma ( heta )}{Gamma (m+ heta )}}|s(m,ell )| heta ^{ell }}$
Значить	${displaystyle heta (psi ( heta +m)-psi ( heta ))}$ (увидеть дигамма функция)

В Распределение столов в китайском ресторане (CRT) это распределение вероятностей от количества столиков в китайском ресторанном процессе.^[2] Его можно понимать как сумму п независимых случайных величин, каждая со своим Распределение Бернулли:

${displaystyle {egin{aligned}L&=sum _{n=1}^{m}b_{n}[4pt]b_{n}&sim operatorname {Bernoulli} left({frac { heta }{n-1+ heta }}ight)end{aligned}}}$

Функция массы вероятности L дан кем-то ^[3]

${displaystyle f(ell )={frac {Gamma ( heta )}{Gamma (m+ heta )}}|s(m,ell )| heta ^{ell }}$

где s обозначает Числа Стирлинга первого рода.

Обобщение

Эту конструкцию можно обобщить на модель с двумя параметрами: θ & α,^[4][5] обычно называемый скидка и прочность (или концентрация) параметры. Вовремя п + 1, следующий прибывший покупатель найдет |B| заняты столами и решает с вероятностью сесть за пустой стол

${displaystyle {frac { heta +|B|alpha }{n+ heta }},}$

или за занятым столом б размера |б| с вероятностью

${displaystyle {frac {|b|-alpha }{n+ heta }}.}$

Для того, чтобы конструкция определяла действующий вероятностная мера необходимо предположить, что либо α <0 и θ = - Lα для некоторых L ∈ {1, 2, ...}; или что 0 ≤α <1 и θ > −α.

Согласно этой модели вероятность, присвоенная любому конкретному разделу B из п, с точки зрения Почхаммер k-символ, является

${displaystyle Pr(B_{n}=B)={frac {( heta +alpha )_{|B|-1,alpha }}{( heta +1)_{n-1,1}}}prod _{bin B}(1-alpha )_{|b|-1,1}}$

где по условию ${displaystyle (a)_{0,c}=1}$, и для ${displaystyle b>0}$

${displaystyle (a)_{b,c}=prod _{i=0}^{b-1}(a+ic)={egin{cases}a^{b}&{ ext{if }}c=0,\{dfrac {c^{b},Gamma (a/c+b)}{Gamma (a/c)}}&{ ext{otherwise}}.end{cases}}}$

Таким образом, для случая, когда ${displaystyle heta >0}$ вероятность разбиения может быть выражена через Гамма-функция так как

${displaystyle Pr(B_{n}=B)={frac {Gamma ( heta )}{Gamma ( heta +n)}}{dfrac {alpha ^{|B|},Gamma ( heta /alpha +|B|)}{Gamma ( heta /alpha )}}prod _{bin B}{dfrac {Gamma (|b|-alpha )}{Gamma (1-alpha )}}.}$

В однопараметрическом случае, когда ${displaystyle alpha }$ равен нулю, это упрощается до

${displaystyle Pr(B_{n}=B)={frac {Gamma ( heta ), heta ^{|B|}}{Gamma ( heta +n)}}prod _{bin B}Gamma (|b|).}$

Или, когда ${displaystyle heta }$ равно нулю,

${displaystyle Pr(B_{n}=B)={frac {alpha ^{|B|-1},Gamma (|B|)}{Gamma (n)}}prod _{bin B}{frac {Gamma (|b|-alpha )}{Gamma (1-alpha )}}.}$

Как и раньше, вероятность, присвоенная любому конкретному разделу, зависит только от размеров блока, так что, как и раньше, случайный раздел можно заменять в смысле, описанном выше. Свойство согласованности по-прежнему сохраняется по построению.

Если α = 0, распределение вероятностей случайного разделение целого числа п таким образом генерируется Распределение Ювенса с параметром θ, используемым в популяционная генетика и единая нейтральная теория биоразнообразия.

Анимация процесса китайского ресторана с параметром масштабирования ${displaystyle heta =0.5, alpha =0}$. Таблицы скрываются, когда клиенты таблицы больше не могут отображаться; однако за каждым столом бесконечно много мест. (Запись интерактивной анимации.^[6])

Вывод

Вот один из способов получить эту вероятность разделения. Позволять C_я быть случайным блоком, в который число я добавлен, для я = 1, 2, 3, .... потом

${displaystyle Pr(C_{i}=cmid C_{1},ldots ,C_{i-1})={egin{cases}{dfrac { heta +|B|alpha }{ heta +i-1}}&{ ext{if }}cin { ext{new block}},\{dfrac {|b|-alpha }{ heta +i-1}}&{ ext{if }}cin b;end{cases}}}$

Вероятность того, что B_п - любое частное разбиение множества {1, ...,п } является произведением этих вероятностей как я работает от 1 до п. Теперь рассмотрим размер блока б: он увеличивается на 1 каждый раз, когда мы добавляем в него один элемент. Когда последний элемент в блоке б должен быть добавлен, размер блока (|б| - 1). Например, рассмотрим эту последовательность вариантов: (создать новый блокб)(присоединитьсяб)(присоединитьсяб)(присоединитьсяб). В конце концов, заблокируйте б имеет 4 элемента, и произведение числителей в приведенном выше уравнении получает θ · 1 · 2 · 3. Следуя этой логике, получаем Pr (B_п = B) как указано выше.

Ожидаемое количество столов

Для однопараметрического случая с α = 0 и 0 <θ <∞, количество таблиц распределяется согласно раздача столиков в китайском ресторане. Ожидаемое значение этой случайной величины, учитывая, что есть ${displaystyle n}$ сидящих клиентов, это^[7]

${displaystyle {egin{aligned}sum _{k=1}^{n}{frac { heta }{ heta +k-1}}= heta cdot (Psi ( heta +n)-Psi ( heta ))end{aligned}}}$

где ${displaystyle Psi ( heta )}$ это функция дигаммы. В общем случае (α > 0) ожидаемое количество занятых таблиц равно^[5]

${displaystyle {egin{aligned}{frac {Gamma ( heta +n+alpha )Gamma ( heta +1)}{alpha Gamma ( heta +n)Gamma ( heta +alpha )}}-{frac { heta }{alpha }},end{aligned}}}$

Однако обратите внимание, что ${displaystyle Gamma (cdot )}$ функция здесь не стандартная гамма-функция.^[5]

Индийский буфет

Можно адаптировать модель таким образом, чтобы каждая точка данных больше не была однозначно связана с классом (т.е. мы больше не строим раздел), но могла быть связана с любой комбинацией классов. Это усиливает аналогию со столиками в ресторане и вместо этого сравнивается с процессом, в котором группа посетителей пробует из некоторого подмножества бесконечного выбора блюд, предлагаемых на шведском столе. Вероятность того, что конкретный посетитель попробует конкретное блюдо, пропорциональна его популярности среди посетителей, и, кроме того, посетитель может пробовать из непроверенных блюд. Это было названо Индийский буфет и может использоваться для вывода скрытых функций в данных.^[8]

Приложения

Китайский ресторанный процесс тесно связан с Процессы Дирихле и Схема урны Поли, и поэтому полезен в приложениях Байесовская статистика в том числе непараметрический Байесовские методы. Обобщенный китайский ресторанный процесс тесно связан с Процесс Питмана – Йорка. Эти процессы использовались во многих приложениях, включая моделирование текста, кластеризацию биологических микрочип данные,^[9] моделирование биоразнообразия, и реконструкция изображения ^[10][11]

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

• Формула выборки Ювенса
• Предпочтительная привязанность
• Парадокс Гильберта в Гранд Отеле

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

1. Олдос, Д. Дж. (1985). «Возможность обмена и смежные темы». École d'Été de Probabilités de Saint-Flour XIII - 1983 г.. Конспект лекций по математике. 1117. С. 1–198. Дои:10.1007 / BFb0099421. ISBN  978-3-540-15203-3.
2. Чжоу, Минъюань; Карин, Лоуренс (2012). «Отрицательный биномиальный подсчет процесса и моделирование смеси». IEEE Transactions по анализу шаблонов и машинному анализу. 37 (2): 307–20. arXiv:1209.3442. Bibcode:2012arXiv1209.3442Z. Дои:10.1109 / TPAMI.2013.211. PMID  26353243.
3. Антониак, Чарльз Э (1974). «Смеси процессов Дирихле с приложениями к байесовским непараметрическим задачам». Анналы статистики. 2 (6): 1152–1174. Дои:10.1214 / aos / 1176342871.
4. Питман, Джим (1995). «Заменяемые и частично заменяемые случайные разделы». Теория вероятностей и смежные области. 102 (2): 145–158. Дои:10.1007 / BF01213386. Г-Н  1337249.
5. Питман, Джим (2006). Комбинаторные случайные процессы. 1875. Берлин: Springer-Verlag. ISBN  9783540309901.
6. «Процесс Дирихле и распределение Дирихле - Схема ресторана Поля и китайский ресторанный процесс».
7. Синьхуа Чжан, «Очень мягкое примечание о построении процесса Дирихле», сентябрь 2008 г., Австралийский национальный университет, Канберра. Онлайн: http://users.cecs.anu.edu.au/~xzhang/pubDoc/notes/dirichlet_process.pdf В архиве 11 апреля 2011 г. Wayback Machine
8. Гриффитс, Т. и Гахрамани, З. (2005) Бесконечные модели скрытых функций и процесс индийского шведского стола. Технический отчет подразделения Гэтсби GCNU-TR-2005-001.
9. Цинь, Чжаохуэй С (2006). «Кластеризация данных экспрессии генов микроматрицы с использованием взвешенного процесса китайского ресторана». Биоинформатика. 22 (16): 1988–1997. Дои:10.1093 / биоинформатика / btl284. PMID  16766561.
10. White, J. T .; Госал, С. (2011). «Байесовское сглаживание изображений, ограниченных фотонами, с приложениями в астрономии» (PDF). Журнал Королевского статистического общества, серия B (статистическая методология). 73 (4): 579–599. CiteSeerX  10.1.1.308.7922. Дои:10.1111 / j.1467-9868.2011.00776.x.
11. Li, M .; Госал, С. (2014). «Байесовское многомасштабное сглаживание гауссовских зашумленных изображений». Байесовский анализ. 9 (3): 733–758. Дои:10.1214 / 14-ba871.

внешние ссылки

• Введение в распределение Дирихле и связанные с ним процессы Фригика, Капилы и Гупты
• Разговор Майкл И. Джордан по CRP:
  • http://videolectures.net/icml05_jordan_dpcrp/