Китайский ресторанный процесс

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

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

Формальное определение [ править ]

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

1. добавлен в один из блоков раздела B _n , где каждый блок выбирается с вероятностью | b | / ( n  + 1) где | б | размер блока (т.е. количество элементов), или
2. добавлен в раздел B _n как новый одноэлементный блок с вероятностью 1 / ( n  + 1).

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

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

${\ Displaystyle \ Pr (B_ {n} = B) = {\ frac {\ prod _ {b \ in B} (| b | -1)!} {n!}}}$

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

Распространение [ править ]

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

Параметры	${\ displaystyle \ theta> 0}$ ${\ Displaystyle м \ ин \ {0,1,2, \ ldots \}}$
Поддерживать	${\ Displaystyle L \ в \ {0,1,2, \ ldots, м \}}$
PMF	${\ displaystyle {\ frac {\ Gamma (\ theta)} {\ Gamma (m + \ theta)}} | s (m, \ ell) | \ theta ^ {\ ell}}$
Иметь в виду	${\ Displaystyle \ тета (\ пси (\ тета + м) - \ пси (\ тета))}$ (см. функцию дигаммы )

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

${\ displaystyle {\ begin {align} L & = \ sum _ {n = 1} ^ {m} b_ {n} \\ [4pt] b_ {n} & \ sim \ operatorname {Bernoulli} \ left ({\ frac {\ theta} {n-1 + \ theta}} \ right) \ end {align}}}$

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

${\ Displaystyle е (\ ell) = {\ гидроразрыва {\ Gamma (\ theta)} {\ Gamma (m + \ theta)}} | s (m, \ ell) | \ theta ^ {\ ell}}$

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

Обобщение [ править ]

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

${\ displaystyle {\ frac {\ theta + | B | \ alpha} {n + \ theta}},}$

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

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

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

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

${\displaystyle \Pr(B_{n}=B)={\frac {(\theta +\alpha )_{|B|-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{b\in 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)={\begin{cases}a^{b}&{\text{if }}c=0,\\\\{\dfrac {c^{b}\,\Gamma (a/c+b)}{\Gamma (a/c)}}&{\text{otherwise}}.\end{cases}}}$

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

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

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

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

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

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

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

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

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

Вывод [ править ]

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

${\displaystyle \Pr(C_{i}=c\mid C_{1},\ldots ,C_{i-1})={\begin{cases}{\dfrac {\theta +|B|\alpha }{\theta +i-1}}&{\text{if }}c\in {\text{new block}},\\\\{\dfrac {|b|-\alpha }{\theta +i-1}}&{\text{if }}c\in b;\end{cases}}}$

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

Ожидаемое количество столов [ править ]

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

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

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

${\displaystyle {\begin{aligned}{\frac {\Gamma (\theta +n+\alpha )\Gamma (\theta +1)}{\alpha \Gamma (\theta +n)\Gamma (\theta +\alpha )}}-{\frac {\theta }{\alpha }},\end{aligned}}}$

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

Индийский буфет [ править ]

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

Приложения [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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