stringtranslate.com

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.

Definición formal

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 .

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:

  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
  2. añadido a la partición como un nuevo bloque singleton, con probabilidad .

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 .

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

donde es un bloque en la partición y es el tamaño de .

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.

Definición alternativa

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 .

Distribución del número de mesas

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:

La función de masa de probabilidad de está dada por [6]

donde denota números de Stirling del primer tipo .

Generalización de dos parámetros

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

o en una mesa ocupada de tamaño con probabilidad

Para que la construcción defina una medida de probabilidad válida es necesario suponer que y para algún ; o bien que y .

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

donde, el símbolo k de Pochhammer se define de la siguiente manera: por convención, , y para

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.

Para el caso cuando y , la probabilidad de partición se puede reescribir en términos de la función Gamma como

En el caso de un parámetro, donde es cero, y esto se simplifica a

O, cuando es cero, y

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 .

Animación del proceso de un restaurante chino con parámetro de escala . Las mesas se ocultan cuando ya no se pueden visualizar los clientes de una mesa; sin embargo, cada mesa tiene una cantidad infinita de asientos. (Grabación de una animación interactiva. [8] )

Derivación

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

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.

Número esperado de mesas

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]

donde es la función digamma . Para el caso de dos parámetros, para , el número esperado de mesas ocupadas es [7]

donde es el factorial ascendente (como se define arriba).

El modelo categórico de Dirichlet

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

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

La probabilidad marginal de las etiquetas viene dada por

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

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).

Relación entre la PCR categórica de Dirichlet y la PCR monoparamétrica

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.

Proceso de rotura de palos

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 :

Las probabilidades categóricas son:

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:

y .

El proceso del buffet indio

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]

Aplicaciones

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]

Véase también

Referencias

  1. ^ Aldous, DJ (1985). "Intercambiabilidad y temas afines". Escuela de Été de Probabilités de Saint-Flour XIII — 1983 . Apuntes de conferencias de matemáticas. vol. 1117, págs. 1–198. doi :10.1007/BFb0099421. ISBN 978-3-540-15203-3. El proceso del restaurante se describe en la página 92.
  2. ^ ab Pitman, Jim (1995). "Particiones aleatorias intercambiables y parcialmente intercambiables". Teoría de la probabilidad y campos relacionados . 102 (2): 145–158. doi : 10.1007/BF01213386 . MR  1337249. S2CID  16849229.
  3. ^ Hoppe, Fred M. (1984). "Urnas tipo Pólya y la fórmula de muestreo de Ewens". Revista de biología matemática . 20 : 91–94.
  4. ^ Blei, David M.; Frazier, Peter I. (2011). "Procesos dependientes de la distancia en restaurantes chinos" (PDF) . Revista de investigación en aprendizaje automático . 12 : 2461–2488.
  5. ^ Zhou, Mingyuan; Carin, Lawrence (2012). "Recuento de procesos binomiales negativos y modelado de mezclas". IEEE Transactions on Pattern Analysis and Machine Intelligence . 37 (2): 307–20. arXiv : 1209.3442 . Bibcode :2012arXiv1209.3442Z. doi :10.1109/TPAMI.2013.211. PMID  26353243. S2CID  1937045.
  6. ^ Antoniak, Charles E (1974). "Mezclas de procesos de Dirichlet con aplicaciones a problemas no paramétricos bayesianos". Anales de Estadística . 2 (6): 1152–1174. doi : 10.1214/aos/1176342871 .
  7. ^ de Pitman, Jim (2006). Procesos estocásticos combinatorios. Vol. 1875. Berlín: Springer-Verlag. ISBN 9783540309901Archivado desde el original el 25 de septiembre de 2012. Consultado el 11 de mayo de 2011 .
  8. ^ "Proceso de Dirichlet y distribución de Dirichlet - Esquema de restaurante Polya y proceso de restaurante chino".
  9. ^ Xinhua Zhang, "Una nota muy amable sobre la construcción del proceso de Dirichlet", septiembre de 2008, Universidad Nacional de Australia, Canberra. En línea: http://users.cecs.anu.edu.au/~xzhang/pubDoc/notes/dirichlet_process.pdf Archivado el 11 de abril de 2011 en Wayback Machine .
  10. ^ Hemant Ishwaran y Lancelot F. James (2001), "Métodos de muestreo de Gibbs para priores de ruptura de palos", Journal of the American Statistical Association, vol. 96, núm. 543, marzo de 2001. En línea: https://www.jstor.org/stable/2670356
  11. ^ Griffiths, TL y Ghahramani, Z. (2005) Modelos de características latentes infinitas y el proceso buffet indio Archivado el 31 de octubre de 2008 en Wayback Machine . Informe técnico de la Unidad Gatsby GCNU-TR-2005-001.
  12. ^ Qin, Zhaohui S (2006). "Agrupamiento de datos de expresión génica de microarrays mediante el proceso ponderado de restaurante chino". Bioinformática . 22 (16): 1988–1997. doi :10.1093/bioinformatics/btl284. PMID  16766561.
  13. ^ White, JT; Ghosal, S. (2011). "Suavizado bayesiano de imágenes limitadas por fotones con aplicaciones en astronomía" (PDF) . Revista de la Royal Statistical Society, Serie B (Metodología estadística) . 73 (4): 579–599. CiteSeerX 10.1.1.308.7922 . doi :10.1111/j.1467-9868.2011.00776.x. S2CID  2342134. 
  14. ^ Li, M.; Ghosal, S. (2014). "Suavizado multiescala bayesiano de imágenes con ruido gaussiano". Análisis bayesiano . 9 (3): 733–758. doi : 10.1214/14-ba871 .

Enlaces externos