Proceso de restaurante chino

En teoría de la probabilidad , el proceso del restaurante chino es un proceso estocástico de tiempo discreto , análogo a sentar a los clientes en las mesas de un restaurante. Imagine un restaurante con un número infinito de mesas circulares, cada una con capacidad infinita. El cliente 1 se sienta en la primera mesa. El siguiente cliente se sienta en la misma mesa que el cliente 1, o en la siguiente mesa. Esto continúa, con cada cliente eligiendo sentarse en una mesa ocupada con una probabilidad proporcional al número de clientes que ya están allí (es decir, es más probable que se sienten en una mesa con muchos clientes que en una con pocos), o en una mesa desocupada. En el momento n , los n clientes se han repartido entre m  ≤  n mesas (o bloques de la partición). Los resultados de este proceso son intercambiables , lo que significa que el orden en el que se sientan los clientes no afecta a la probabilidad de la distribución final . Esta propiedad simplifica enormemente una serie de problemas en genética de poblaciones , análisis lingüístico y reconocimiento de imágenes .

La analogía del restaurante apareció por primera vez en un artículo de 1985 de David Aldous , ^[1] donde se le atribuyó a Jim Pitman (quien también le da crédito a Lester Dubins ). ^[2]

^{Un año antes, Fred Hoppe [3]} publicó un proceso de partición equivalente que utilizaba un "esquema de urna" similar a la urna de Pólya . En comparación con el modelo de urna de Hoppe, el proceso del restaurante chino tiene la ventaja de que se presta naturalmente a describir permutaciones aleatorias a través de su estructura cíclica, además de describir particiones aleatorias.

Para cualquier entero positivo , denotemos el conjunto de todas las particiones del conjunto . El proceso del restaurante chino toma valores en el producto cartesiano infinito .${\estilo de visualización n}$${\displaystyle {\mathcal {P}}_{n}}$${\displaystyle \{1,2,3,...,n\}\triánguloq [n]}$${\displaystyle \prod _{n\geq 1}{\mathcal {P}}_{n}}$

El valor del proceso en el momento es una partición del conjunto , cuya distribución de probabilidad se determina de la siguiente manera. En el momento , se obtiene la partición trivial (con probabilidad uno). En el momento el elemento " " es:${\estilo de visualización n}$$Estilo de visualización B_{n}$${\estilo de visualización [n]}$${\estilo de visualización n=1}$${\displaystyle B_{1}=\{\{1\}\}}$${\estilo de visualización n+1}$${\estilo de visualización n+1}$

1. se agrega a uno de los bloques de la partición , donde cada bloque se elige con probabilidad donde es el tamaño del bloque (es decir, el número de elementos), o$Estilo de visualización B_{n}$${\displaystyle |b|/(n+1)}$${\estilo de visualización |b|}$
2. añadido a la partición como un nuevo bloque singleton, con probabilidad .$Estilo de visualización B_{n}$${\estilo de visualización 1/(n+1)}$

La partición aleatoria así generada tiene algunas propiedades especiales. Es intercambiable en el sentido de que el reetiquetado no cambia la distribución de la partición, y es consistente en el sentido de que la ley de la partición obtenida al eliminar el elemento de la partición aleatoria es la misma que la ley de la partición aleatoria .${\displaystyle \{1,...,n\}}$${\estilo de visualización [n-1]}$${\estilo de visualización n}$$Estilo de visualización B_{n}$$Estilo de visualización B_{n-1}}$

La probabilidad asignada a cualquier partición particular (ignorando el orden en que los clientes se sientan alrededor de cualquier mesa en particular) es

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

donde es un bloque en la partición y es el tamaño de .${\estilo de visualización b}$${\estilo de visualización B}$${\estilo de visualización |b|}$${\estilo de visualización b}$

La definición se puede generalizar introduciendo un parámetro que modifica la probabilidad de que el nuevo cliente se siente en una nueva mesa a y, en consecuencia, modifica la probabilidad de que se siente en una mesa de tamaño a . El proceso básico introducido anteriormente se puede recuperar estableciendo . Intuitivamente, se puede interpretar como el número efectivo de clientes sentados en la primera mesa vacía.${\displaystyle \theta >0}$${\displaystyle {\frac {\theta }{n+\theta }}}$${\estilo de visualización |b|}$${\displaystyle {\frac {|b|}{n+\theta }}}$${\displaystyle \theta = 1}$${\estilo de visualización \theta}$

Una forma equivalente, pero sutilmente diferente, de definir el proceso del restaurante chino es dejar que los nuevos clientes elijan acompañantes en lugar de mesas. ^[4] El cliente elige sentarse en la misma mesa que cualquiera de los clientes sentados con probabilidad , o elige sentarse en una mesa nueva, desocupada, con probabilidad . Observe que en esta formulación, el cliente elige una mesa sin tener que contar las ocupaciones de las mesas; no necesitamos .${\estilo de visualización n+1}$${\estilo de visualización n}$${\displaystyle {\frac {1}{n+\theta }}}$${\displaystyle {\frac {\theta }{n+\theta }}}$${\estilo de visualización |b|}$

Mesa de restaurante chino

Parámetros	${\displaystyle \theta >0}$ ${\displaystyle n\in \{1,2,\ldots \}}$
Apoyo	${\displaystyle k\en \{1,2,\ldots ,n\}}$
FMP	${\displaystyle {\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k}}$
Significar	${\displaystyle \theta (\psi (\theta +n)-\psi (\theta ))}$ (ver función digamma )

La distribución de mesas del restaurante chino ( CRT ) es la distribución de probabilidad del número de mesas en el proceso del restaurante chino. ^[5] Puede entenderse como la suma de variables aleatorias de Bernoulli independientes , cada una con un parámetro diferente:${\estilo de visualización n}$

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

La función de masa de probabilidad de está dada por ^[6]${\estilo de visualización K}$

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

donde denota números de Stirling del primer tipo .${\estilo de visualización s}$

Esta construcción se puede generalizar a un modelo con dos parámetros, & , ^{[2] [7]} comúnmente llamados parámetros de fuerza (o concentración ) y descuento respectivamente. En el momento , el siguiente cliente que llega encuentra mesas ocupadas y decide sentarse en una mesa vacía con probabilidad${\estilo de visualización \theta}$${\estilo de visualización \alpha}$${\estilo de visualización n+1}$${\estilo de visualización |B|}$

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

o en una mesa ocupada de tamaño con probabilidad${\estilo de visualización b}$${\estilo de visualización |b|}$

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

Para que la construcción defina una medida de probabilidad válida es necesario suponer que y para algún ; o bien que y .${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle L\en \{1,2,,...\}}$${\displaystyle 0\leq \alpha <1}$${\displaystyle \theta >-\alpha }$

Bajo este modelo, la probabilidad asignada a cualquier partición particular de , se puede expresar en el caso general (para cualquier valor de que satisfaga las restricciones mencionadas anteriormente) en términos del símbolo k de Pochhammer , como${\estilo de visualización B}$${\estilo de visualización [n]}$${\displaystyle \theta ,\alpha }$

${\displaystyle \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}}$

donde, el símbolo k de Pochhammer se define de la siguiente manera: por convención, , y para${\displaystyle (a)_{0,k}=1}$${\displaystyle m>0}$

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

donde es el factorial ascendente y es el factorial descendente . Vale la pena señalar que para la configuración de parámetros donde y , entonces , que se evalúa como cero siempre que , por lo que es un límite superior en la cantidad de bloques en la partición; consulte la subsección sobre el modelo categórico de Dirichlet a continuación para obtener más detalles.${\displaystyle x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)}$${\displaystyle x^{\underline {m}}=\prod _{i=0}^{m-1}(xi)}$${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle (\theta +\alpha )_{|B|-1,\alpha }=(|\alpha |(L-1))_{|B|-1,\alpha }}$${\displaystyle |B|>L}$${\estilo de visualización L}$

Para el caso cuando y , la probabilidad de partición se puede reescribir en términos de la función Gamma como${\displaystyle \theta >0}$${\displaystyle 0<\alpha <1}$

${\displaystyle \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 )}}.}$

En el caso de un parámetro, donde es cero, y esto se simplifica a${\estilo de visualización \alpha}$${\displaystyle \theta >0}$

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

O, cuando es cero, y${\estilo de visualización \theta}$${\displaystyle 0<\alpha <1}$

${\displaystyle \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 )}}.}$

Como antes, la probabilidad asignada a cualquier partición particular depende únicamente de los tamaños de los bloques, por lo que, como antes, la partición aleatoria es intercambiable en el sentido descrito anteriormente. La propiedad de consistencia sigue siendo válida, como antes, por construcción.

Si , la distribución de probabilidad de la partición aleatoria del entero así generado es la distribución de Ewens con parámetro , utilizada en genética de poblaciones y en la teoría neutral unificada de la biodiversidad .${\displaystyle \alpha =0}$ ${\displaystyle n}$${\displaystyle \theta }$

He aquí una forma de derivar esta probabilidad de partición. Sea el bloque aleatorio en el que se añade el número, para . Entonces${\displaystyle C_{i}}$${\displaystyle i}$${\displaystyle 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}}}$

La probabilidad de que sea cualquier partición particular del conjunto es el producto de estas probabilidades, que van desde hasta . Ahora, considere el tamaño del bloque : aumenta en uno cada vez que le agregamos un elemento. Cuando se agrega el último elemento del bloque, el tamaño del bloque es . Por ejemplo, considere esta secuencia de opciones: (generar un nuevo bloque )(unir )(unir )(unir ). Al final, el bloque tiene 4 elementos y el producto de los numeradores en la ecuación anterior es . Siguiendo esta lógica, obtenemos lo anterior.${\displaystyle B_{n}}$${\displaystyle \{1,...,n\}}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle b}$${\displaystyle b}$${\displaystyle |b|-1}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle \theta \cdot 1\cdot 2\cdot 3}$${\displaystyle \Pr(B_{n}=B)}$

Para el caso de un parámetro, con y , el número de mesas se distribuye de acuerdo con la distribución de mesas de un restaurante chino . El valor esperado de esta variable aleatoria, dado que hay clientes sentados, es ^[9]${\displaystyle \alpha =0}$${\displaystyle 0<\theta <\infty }$${\displaystyle n}$

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

donde es la función digamma . Para el caso de dos parámetros, para , el número esperado de mesas ocupadas es ^[7]${\displaystyle \Psi (\theta )}$${\displaystyle \alpha \neq 0}$

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

donde es el factorial ascendente (como se define arriba).${\displaystyle x^{\overline {m}}}$

Para la elección de parámetros y , donde , el proceso de restaurante chino de dos parámetros es equivalente al modelo categórico de Dirichlet , que es un modelo jerárquico que se puede definir de la siguiente manera. Observe que para esta configuración de parámetros, la probabilidad de ocupar una nueva mesa, cuando ya hay mesas ocupadas, es cero; de modo que el número de mesas ocupadas está limitado superiormente por . Si elegimos identificar las tablas con etiquetas que toman valores en , entonces para generar una partición aleatoria del conjunto , el modelo jerárquico primero extrae una distribución de etiquetas categóricas , a partir de la distribución de Dirichlet simétrica , con parámetro de concentración . Luego, de forma independiente para cada uno de los clientes, la etiqueta de la tabla se extrae de la categórica . Dado que la distribución de Dirichlet es conjugada a la categórica, la variable oculta se puede marginar para obtener la distribución predictiva posterior para el siguiente estado de etiqueta, , dadas las etiquetas anteriores${\displaystyle \alpha <0}$${\displaystyle \theta =-L\alpha }$${\displaystyle L\in \{1,2,3,\ldots \}}$${\displaystyle L}$${\displaystyle L}$${\displaystyle \{1,2,\ldots ,L\}}$${\displaystyle [n]=\{1,2,\ldots ,n\}}$${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots ,p_{L})}$${\displaystyle \gamma =-\alpha >0}$${\displaystyle n}$${\displaystyle \mathbf {p} }$${\displaystyle \mathbf {p} }$${\displaystyle \ell _{n+1}}$${\displaystyle n}$

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

donde es el número de clientes que ya están sentados en la mesa . Con y , esto concuerda con la fórmula general anterior, , para la probabilidad de sentarse en una mesa ocupada cuando . La probabilidad de sentarse en cualquiera de las mesas desocupadas, también concuerda con la fórmula general y está dada por${\displaystyle \left|{b_{i}}\right|\geq 0}$${\displaystyle i}$${\displaystyle \alpha =-\gamma }$${\displaystyle \theta =L\gamma }$${\displaystyle {\frac {|b_{i}|-\alpha }{n+\theta }}}$${\displaystyle |b_{i}|\geq 1}$${\displaystyle L-|B|}$

${\displaystyle \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 }}}$

La probabilidad marginal de las etiquetas viene dada por

${\displaystyle 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}}}}}$

donde y es el factorial ascendente . En general, sin embargo, hay múltiples estados de etiqueta que corresponden todos a la misma partición. Para una partición dada, , que tiene bloques, la cantidad de estados de etiqueta que corresponden todos a esta partición está dada por el factorial descendente , . Teniendo esto en cuenta, la probabilidad de la partición es${\displaystyle P(\ell _{1})={\frac {1}{L}}}$${\displaystyle x^{\overline {m}}=\prod _{i=0}^{m-1}(x+i)}$${\displaystyle B}$${\displaystyle \left|B\right|\leq L}$${\displaystyle L^{\underline {\left|B\right|}}=\prod _{i=0}^{\left|B\right|-1}(L-i)}$

${\displaystyle {\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}}}}}$

lo cual se puede verificar que concuerda con la versión general de la probabilidad de partición que se da arriba en términos del símbolo k de Pochhammer. Observe nuevamente que si está fuera del soporte, es decir , el factorial descendente, se evalúa a cero como debería. (Las implementaciones prácticas que evalúan la probabilidad logarítmica para particiones mediante devolverán , siempre que , como se requiere). ${\displaystyle B}$${\displaystyle |B|>L}$${\displaystyle L^{\underline {|B|}}}$${\displaystyle \log L^{\underline {|B|}}=\log \left|\Gamma (L+1)\right|-\log \left|\Gamma (L+1-|B|)\right|}$${\displaystyle -\infty }$${\displaystyle |B|>L}$

Consideremos, por un lado, el proceso de restaurante chino de un parámetro, con y , que denotamos ; y, por otro lado, el modelo categórico de Dirichlet con un entero positivo y donde elegimos , que, como se muestra arriba, es equivalente a . Esto muestra que el modelo categórico de Dirichlet se puede hacer arbitrariamente cercano a , haciendo grande.${\displaystyle \alpha =0}$${\displaystyle \theta >0}$${\displaystyle {\text{CRP}}(\alpha =0,\theta )}$${\displaystyle L}$${\displaystyle \gamma ={\frac {\theta }{L}}}$${\displaystyle {\text{CRP}}(\alpha =-{\frac {\theta }{L}},\theta )}$${\displaystyle {\text{CRP}}(0,\theta )}$${\displaystyle L}$

El proceso de restaurante chino de dos parámetros se puede definir de manera equivalente en términos de un proceso de rotura de palitos . ^[10] Para el caso donde y , el proceso de rotura de palitos se puede describir como un modelo jerárquico, muy parecido al modelo categórico de Dirichlet anterior, excepto que hay un número infinito de estados de etiqueta. Las etiquetas de la tabla se extraen independientemente de la distribución categórica infinita , cuyos componentes se muestrean utilizando la rotura de palitos : comience con un palito de longitud 1 y rómpalo aleatoriamente en dos, la longitud de la mitad izquierda es y la mitad derecha se vuelve a romper de manera recursiva para dar . Más precisamente, la fracción izquierda, , de la -ésima rotura se muestrea de la distribución beta : ${\displaystyle 0\leq \alpha <1}$${\displaystyle \theta >-\alpha }$${\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )}$${\displaystyle p_{1}}$${\displaystyle p_{2},p_{3},\ldots }$${\displaystyle f_{k}}$${\displaystyle k}$

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

Las probabilidades categóricas son:

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

Para la configuración de los parámetros y , donde es un entero positivo y donde el categórico es finito: , podemos tomar muestras de una distribución de Dirchlet ordinaria como se explicó anteriormente, pero también se puede tomar muestras con una receta de ruptura de palitos truncada , donde la fórmula para tomar muestras de las fracciones se modifica a:${\displaystyle \alpha <0}$${\displaystyle \theta =-\alpha L}$${\displaystyle L}$${\displaystyle \mathbf {p} =(p_{1},\ldots ,p_{L})}$${\displaystyle \mathbf {p} }$

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

y .${\displaystyle f_{L}=1}$

Es posible adaptar el modelo de modo que cada punto de datos ya no esté asociado únicamente con una clase (es decir, ya no estamos construyendo una partición), sino que pueda estar asociado con cualquier combinación de las clases. Esto pone a prueba la analogía de las mesas de restaurante y, por lo tanto, se asemeja a un proceso en el que una serie de comensales prueban un subconjunto de una selección infinita de platos que se ofrecen en un bufé. La probabilidad de que un comensal en particular pruebe un plato en particular es proporcional a la popularidad del plato entre los comensales hasta el momento y, además, el comensal puede probar platos no probados. Esto se ha denominado el proceso del bufé indio y se puede utilizar para inferir características latentes en los datos. ^[11]

El proceso del restaurante chino está estrechamente relacionado con los procesos de Dirichlet y el esquema de urna de Pólya y, por lo tanto, es útil en aplicaciones de estadísticas bayesianas , incluidos los métodos bayesianos no paramétricos . El proceso generalizado del restaurante chino está estrechamente relacionado con el proceso de Pitman-Yor . Estos procesos se han utilizado en muchas aplicaciones, incluido el modelado de texto, la agrupación de datos de microarrays biológicos , ^[12] el modelado de la biodiversidad y la reconstrucción de imágenes ^{[13] [14]}

• Fórmula de muestreo de Ewens
• Apego preferencial
• La paradoja de Hilbert del Grand Hotel

• Introducción a la distribución de Dirichlet y procesos relacionados por Frigyik, Kapila y Gupta
• Una charla de Michael I. Jordan sobre el CRP:
  • http://videolectures.net/icml05_jordan_dpcrp/