процесс в китайском ресторане

Чтобы узнать о других значениях, см. Китайский ресторан (значения) .

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

Аналогия с рестораном впервые появилась в статье Дэвида Олдоса в 1985 году : где это было приписано Джиму Питману (который также упоминает Лестера Дубинса ).

Эквивалентный процесс разделения был опубликован годом ранее Фредом Хоппе . используя «схему урны», похожую на урну Полии . По сравнению с моделью урны Хоппе процесс китайского ресторана имеет то преимущество, что он, естественно, позволяет описывать случайные перестановки через их циклическую структуру в дополнение к описанию случайных разделов.

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

Для любого положительного целого числа $n$, позволять ${\mathcal {P}}_{n}$ обозначаем множество всех разбиений множества $\{1,2,3,...,n\}\triangleq [n]$. Процесс китайского ресторана принимает значения в бесконечном декартовом произведении. $\prod _{n\geq 1}{\mathcal {P}}_{n}$.

Ценность процесса во времени $n$ это раздел $B_{n}$ из набора $[n]$, распределение вероятностей которого определяется следующим образом. Во время $n=1$, тривиальный раздел $B_{1}=\{\{1\}\}$ получается (с вероятностью единица). Во время $n+1$ элемент " $n+1$"либо:

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

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

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

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

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

Определение можно обобщить, введя параметр $\theta >0$ который изменяет вероятность того, что новый клиент сядет за новый стол, на ${\frac {\theta }{n+\theta }}$ и соответственно изменяет вероятность того, что они сядут за стол размером $|b|$ к ${\frac {|b|}{n+\theta }}$. Представленный выше ванильный процесс можно восстановить, установив $\theta =1$. Интуитивно, $\theta$ можно интерпретировать как эффективное количество клиентов, сидящих за первым пустым столом.

Альтернативное определение

Эквивалентный, но несколько иной способ определения процесса в китайском ресторане — позволить новым клиентам выбирать компаньонов, а не столики. Клиент $n+1$ предпочитает сидеть за одним столом с кем-либо из $n$ сидящие клиенты с вероятностью ${\frac {1}{n+\theta }}$, или с вероятностью решит сесть за новый, незанятый стол ${\frac {\theta }{n+\theta }}$. Обратите внимание, что в этой формулировке клиент выбирает стол без необходимости подсчитывать занятость стола — нам не нужно $|b|$.

Распределение количества столов

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

Параметры	$\theta >0$ $n\in \{1,2,\ldots \}$
Поддерживать	$k\in \{1,2,\ldots ,n\}$
ПМФ	${\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k}$
Иметь в виду	$\theta (\psi (\theta +n)-\psi (\theta ))$ (см. описание функции )

Распределение столов в китайском ресторане ( CRT ) — это распределение вероятностей количества столов в процессе китайского ресторана. Его можно понимать как сумму $n$ независимые случайные величины Бернулли , каждая со своим параметром:

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

Функция массы вероятности $K$ дается

$f(k)={\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k},\quad k=1,\dots ,n,$

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

Двухпараметрическое обобщение

Эту конструкцию можно обобщить на модель с двумя параметрами: $\theta$ & $\alpha$, обычно называемые параметрами силы (или концентрации ) и скидки соответственно. Во время $n+1$, следующий пришедший клиент найдет $|B|$ занятые столы и с вероятностью решает сесть за пустой стол

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

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

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

Для того чтобы конструкция определяла действительную вероятностную меру, необходимо предположить, что либо $\alpha <0$ и $\theta =-L\alpha$ для некоторых $L\in \{1,2,,...\}$; или что $0\leq \alpha <1$ и $\theta >-\alpha$.

Согласно этой модели вероятность, присвоенная какому-либо конкретному разделу $B$ из $[n]$, может быть выражено в общем случае (при любых значениях $\theta ,\alpha$ удовлетворяющие указанным выше ограничениям) в терминах k-символа Похгаммера , как

$\Pr(B_{n}=B\mid \theta ,\alpha )={\frac {(\theta +\alpha )_{|B|-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{b\in B}(1-\alpha )_{|b|-1,1}$

где k-символ Похгаммера определяется следующим образом: по соглашению, $(a)_{0,k}=1$и для $m>0$

$(a)_{m,k}=\prod _{i=0}^{m-1}(a+ik)={\begin{cases}a^{m}&{\text{if }}k=0,\\\\k^{m}\,({\frac {a}{k}})^{\overline {m}}&{\text{if }}k>0,\\\\\left|k\right|^{m}\,({\frac {a}{\left|k\right|}})^{\underline {m}}&{\text{if }}k<0\end{cases}}$

где $x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)$ является восходящим факториалом и $x^{\underline {m}}=\prod _{i=0}^{m-1}(x-i)$ это падающий факториал . Стоит отметить, что для настройки параметра, где $\alpha <0$ и $\theta =-L\alpha$, затем $(\theta +\alpha )_{|B|-1,\alpha }=(|\alpha |(L-1))_{|B|-1,\alpha }$, который равен нулю всякий раз, когда $|B|>L$, так что $L$ — верхняя граница количества блоков в разделе; см. в подразделе « Категорическая модель Дирихле» более подробную информацию ниже.

Для случая, когда $\theta >0$ и $0<\alpha <1$, вероятность разделения можно переписать через гамма-функцию как

$\Pr(B_{n}=B\mid \theta ,\alpha )={\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 )}}.$

В однопараметрическом случае, когда $\alpha$ равен нулю, и $\theta >0$ это упрощает

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

Или, когда $\theta$ равен нулю, и $0<\alpha <1$

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

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

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

Продолжительность: 27 секунд. 0:27

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

Вывод

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

$\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$: оно увеличивается на единицу каждый раз, когда мы добавляем в него один элемент. Когда последний элемент в блоке $b$ должен быть добавлен, размер блока равен $|b|-1$. Например, рассмотрим следующую последовательность вариантов: (создать новый блок $b$)(присоединиться $b$)(присоединиться $b$)(присоединиться $b$). В конце концов заблокируйте $b$ имеет 4 элемента, и произведение числителей в приведенном выше уравнении получается $\theta \cdot 1\cdot 2\cdot 3$. Следуя этой логике, получаем $\Pr(B_{n}=B)$ как указано выше.

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

Для случая с одним параметром, с $\alpha =0$ и $0<\theta <\infty$Количество столов распределяется в соответствии с распределением столов в китайском ресторане . Ожидаемое значение этой случайной величины, учитывая, что существуют $n$ сидящие клиенты, это

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

где $\Psi (\theta )$ это дигамма-функция . В общем случае ( $\alpha >0$) ожидаемое количество занятых столов равно

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

однако обратите внимание, что $\Gamma (\cdot )$ Функция здесь не является стандартной гамма-функцией .

Категориальная модель Дирихле

Для выбора параметра $\alpha <0$ и $\theta =-L\alpha$, где $L\in \{1,2,3,\ldots \}$Двухпараметрический процесс китайского ресторана эквивалентен категориальной модели Дирихле , которая представляет собой иерархическую модель, которую можно определить следующим образом. Обратите внимание, что для этой настройки параметра вероятность занятия новой таблицы, когда уже есть $L$ занятые таблицы, равно нулю; так что количество занятых столов ограничено сверху $L$. Если мы решим идентифицировать таблицы с метками , которые принимают значения в $\{1,2,\ldots ,L\}$, затем сгенерировать случайное разбиение множества $[n]=\{1,2,\ldots ,n\}$иерархическая модель сначала рисует категориальное распределение меток , $\mathbf {p} =(p_{1},p_{2},\ldots ,p_{L})$ из симметричного распределения Дирихле с параметром концентрации $\gamma =-\alpha >0$. Затем независимо для каждого из $n$ клиентов, метка таблицы взята из категориального $\mathbf {p}$. Поскольку распределение Дирихле сопряжено с категориальным, скрытая переменная $\mathbf {p}$ может быть исключено, чтобы получить апостериорное прогнозируемое распределение для следующего состояния метки, $\ell _{n+1}$, данный $n$ предыдущие ярлыки

$P(\ell _{n+1}=i\mid \ell _{1},\ldots ,\ell _{n})={\frac {\gamma +\left|{b_{i}}\right|}{L\gamma +n}}$

где $\left|{b_{i}}\right|\geq 0$ это количество клиентов, которые уже сидят за столом $i$. С $\alpha =-\gamma$ и $\theta =L\gamma$, это согласуется с приведенной выше общей формулой, ${\frac {|b_{i}|-\alpha }{n+\theta }}$, для вероятности сидеть за занятым столом, когда $|b_{i}|\geq 1$. Вероятность сидеть в любом из $L-|B|$ незанятых таблиц также согласуется с общей формулой и определяется выражением

$\sum _{i:|b_{i}|=0}P(\ell _{n+1}=i\mid \ell _{1},\ldots ,\ell _{n})={\frac {(L-|B|)\gamma }{n+L\gamma }}={\frac {\theta +|B|\alpha }{n+\theta }}$

Предельная вероятность для меток определяется выражением

$P(\ell _{1},\ldots ,\ell _{n})=P(\ell _{1})\prod _{t=1}^{n-1}P(\ell _{t+1}\mid \ell _{1},\ldots ,\ell _{t})={\frac {\prod _{i=1}^{L}\gamma ^{\overline {\left|{b_{i}}\right|}}}{(L\gamma )^{\overline {n}}}}$

где $P(\ell _{1})={\frac {1}{L}}$ и $x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)$ – это возрастающий факториал . Однако в целом существует несколько состояний меток, которые соответствуют одному и тому же разделу. Для данного раздела $B$, который имеет $\left|B\right|\leq L$ блоков, количество состояний меток, которые соответствуют этому разделу, определяется падающим факториалом , $L^{\underline {\left|B\right|}}=\prod _{i=0}^{\left|B\right|-1}(L-i)$. Учитывая это, вероятность разделения равна

${\text{Pr}}(B_{n}=B\mid \gamma ,L)=L^{\underline {\left|B\right|}}\,{\frac {\prod _{i=1}^{L}\gamma ^{\overline {\left|{b_{i}}\right|}}}{(L\gamma )^{\overline {n}}}}$

можно проверить, что она согласуется с общей версией вероятности разбиения, приведенной выше в терминах k-символа Похгаммера. Заметьте еще раз, что если $B$ находится вне опоры, т.е. $|B|>L$, падающий факториал, $L^{\underline {|B|}}$ оценивается как ноль, как и должно быть. (Практические реализации, которые оценивают вероятность журнала для разделов через $\log L^{\underline {|B|}}=\log \left|\Gamma (L+1)\right|-\log \left|\Gamma (L+1-|B|)\right|$ вернется $-\infty$, в любое время $|B|>L$, как требуется.)

Связь между категориальной Дирихле и однопараметрической CRP

Рассмотрим, с одной стороны, однопараметрический процесс китайского ресторана, в котором $\alpha =0$ и $\theta >0$, который мы обозначим ${\text{CRP}}(\alpha =0,\theta )$; и, с другой стороны, категориальная модель Дирихле с $L$ положительное целое число и где мы выбираем $\gamma ={\frac {\theta }{L}}$, что, как показано выше, эквивалентно ${\text{CRP}}(\alpha =-{\frac {\theta }{L}},\theta )$. Это показывает, что категориальную модель Дирихле можно сделать сколь угодно близкой к ${\text{CRP}}(0,\theta )$, сделав $L$ большой.

Процесс разрушения палочки

Двухпараметрический процесс китайского ресторана можно эквивалентно определить как процесс ломания палки . Для случая, когда $0\leq \alpha <1$ и $\theta >-\alpha$Процесс разрушения палочки можно описать как иерархическую модель, очень похожую на приведенную выше категориальную модель Дирихле , за исключением того, что существует бесконечное количество состояний метки. Метки таблиц рисуются независимо от бесконечного категориального распределения. $\mathbf {p} =(p_{1},p_{2},\ldots )$, компоненты которого отбираются с помощью разрушения палочки : начните с палочки длиной 1 и случайным образом разбейте ее на две части, длина левой половины равна $p_{1}$ и правая половина снова рекурсивно разбивается, чтобы дать $p_{2},p_{3},\ldots$. Точнее, левая фракция, $f_{k}$, принадлежащий $k$-th перерыв выбирается из бета-распределения :

$f_{k}\sim B(1-\alpha ,\theta +k\alpha ),\;{\text{for }}k\geq 1{\text{ and }}0\leq \alpha <1$

Категориальные вероятности:

$p_{k}=f_{k}\prod _{i=1}^{k-1}(1-f_{k}),\;{\text{where the empty product evaluates to one.}}$

Для настройки параметров $\alpha <0$ и $\theta =-\alpha L$, где $L$ является положительным целым числом, и где категориальное конечно: $\mathbf {p} =(p_{1},\ldots ,p_{L})$, мы можем попробовать $\mathbf {p}$ из обычного распределения Дирхле, как описано выше , но его также можно отобрать с помощью усеченного рецепта разрушения палочки, где формула для отбора фракций изменяется следующим образом:

$f_{k}\sim B(-\alpha ,\theta +k\alpha ),\;{\text{for }}1\leq k\leq L-1{\text{ and }}\alpha <0$

и $f_{L}=1$.

Процесс индийского шведского стола

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

Приложения

Процесс китайского ресторана тесно связан с процессами Дирихле и схемой урн Полья и поэтому полезен в приложениях байесовской статистики, включая непараметрические байесовские методы . Обобщенный китайский ресторанный процесс тесно связан с процессом Питмана-Йора . Эти процессы использовались во многих приложениях, включая моделирование текста, кластеризацию биологических микрочипов , данных моделирование биоразнообразия и реконструкция изображений

См. также

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

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

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