Proceso de Dirichlet

En la teoría de la probabilidad , los procesos de Dirichlet (después de Peter Gustav Lejeune Dirichlet ) son una familia de procesos estocásticos cuyas realizaciones son distribuciones de probabilidad . En otras palabras, un proceso de Dirichlet es una distribución de probabilidad cuyo rango es en sí mismo un conjunto de distribuciones de probabilidad. A menudo se utiliza en la inferencia bayesiana para describir el conocimiento previo sobre la distribución de variables aleatorias: qué tan probable es que las variables aleatorias se distribuyan de acuerdo con una u otra distribución particular.

Se extrae del proceso de Dirichlet ${\displaystyle \operatorname {DP} (N(0,1),\alpha )}$. Las cuatro filas usan diferentes alfa ${\displaystyle \alpha }$(de arriba a abajo: 1, 10, 100 y 1000) y cada fila contiene tres repeticiones del mismo experimento. Como se ve en los gráficos, las extracciones de un proceso de Dirichlet son distribuciones discretas y se vuelven menos concentradas (más dispersas) al aumentar ${\displaystyle \alpha }$. Los gráficos se generaron utilizando la vista del proceso de rotura de palos del proceso de Dirichlet.

El proceso de Dirichlet está especificado por una distribución base ${\displaystyle H}$y un número real positivo ${\displaystyle \alpha }$llamado parámetro de concentración (también conocido como parámetro de escala). La distribución base es el valor esperado del proceso, es decir, el proceso de Dirichlet dibuja distribuciones "alrededor" de la distribución base de la misma manera que una distribución normal dibuja números reales alrededor de su media. Sin embargo, incluso si la distribución base es continua , las distribuciones extraídas del proceso de Dirichlet son casi con seguridad discretas . El parámetro de escala especifica qué tan fuerte es esta discretización: en el límite de${\displaystyle \alpha \rightarrow 0}$, las realizaciones están todas concentradas en un solo valor, mientras que en el límite de ${\displaystyle \alpha \rightarrow \infty }$las realizaciones se vuelven continuas. Entre los dos extremos, las realizaciones son distribuciones discretas con cada vez menos concentración como${\displaystyle \alpha }$ aumenta.

El proceso de Dirichlet también puede verse como la generalización de dimensión infinita de la distribución de Dirichlet . De la misma manera que la distribución de Dirichlet es el previo conjugado para la distribución categórica , el proceso de Dirichlet es el previo conjugado para distribuciones discretas infinitas no paramétricas . Una aplicación particularmente importante de los procesos de Dirichlet es como distribución de probabilidad previa en modelos de mezcla infinita .

El proceso de Dirichlet fue introducido formalmente por Thomas Ferguson en 1973. ^[1] Desde entonces se ha aplicado en la minería de datos y el aprendizaje automático , entre otros para el procesamiento del lenguaje natural , la visión por computadora y la bioinformática .

Introducción

Los procesos de Dirichlet se utilizan generalmente cuando se modelan datos que tienden a repetir valores anteriores de la forma denominada "rico se vuelve más rico". Concretamente, supongamos que la generación de valores${\displaystyle X_{1},X_{2},\dots }$ se puede simular mediante el siguiente algoritmo.

Aporte:${\displaystyle H}$ (una distribución de probabilidad llamada distribución base), ${\displaystyle \alpha }$(un número real positivo llamado parámetro de escala )

Para ${\displaystyle n\geq 1}$:

a) Con probabilidad ${\displaystyle {\frac {\alpha }{\alpha +n-1}}}$ dibujar ${\displaystyle X_{n}}$ de ${\displaystyle H}$.

b) Con probabilidad ${\displaystyle {\frac {n_{x}}{\alpha +n-1}}}$ colocar ${\displaystyle X_{n}=x}$, dónde ${\displaystyle n_{x}}$ es el número de observaciones previas de ${\displaystyle x}$.
(Formalmente, ${\displaystyle n_{x}:=|\{j:X_{j}=x{\text{ and }}j<n\}|}$ dónde ${\displaystyle |\cdot |}$ denota el número de elementos en el conjunto.)

Al mismo tiempo, otro modelo común de datos es que las observaciones ${\displaystyle X_{1},X_{2},\dots }$se supone que son independientes e idénticamente distribuidos (iid) de acuerdo con alguna distribución (aleatoria)${\displaystyle P}$. El objetivo de introducir los procesos de Dirichlet es poder describir el procedimiento descrito anteriormente en este modelo iid.

La ${\displaystyle X_{1},X_{2},\dots }$las observaciones en el algoritmo no son independientes , ya que tenemos que considerar los resultados anteriores al generar el siguiente valor. Sin embargo, son intercambiables . Este hecho puede demostrarse calculando la distribución de probabilidad conjunta de las observaciones y observando que la fórmula resultante solo depende de qué${\displaystyle x}$los valores ocurren entre las observaciones y cuántas repeticiones tiene cada una. Debido a esta intercambiabilidad, se aplica el teorema de representación de Finetti e implica que las observaciones${\displaystyle X_{1},X_{2},\dots }$son condicionalmente independientes dada una distribución (latente)${\displaystyle P}$. Esto${\displaystyle P}$es una variable aleatoria en sí misma y tiene una distribución. Esta distribución (sobre distribuciones) se denomina proceso de Dirichlet (${\displaystyle \operatorname {DP} }$). En resumen, esto significa que obtenemos un procedimiento equivalente al algoritmo anterior:

1. Dibuja una distribución ${\displaystyle P}$ de ${\displaystyle \operatorname {DP} \left(H,\alpha \right)}$
2. Dibujar observaciones ${\displaystyle X_{1},X_{2},\dots }$ independientemente de ${\displaystyle P}$.

En la práctica, sin embargo, trazar una distribución concreta ${\displaystyle P}$es imposible, ya que su especificación requiere una cantidad infinita de información. Este es un fenómeno común en el contexto de la estadística no paramétrica bayesiana , donde una tarea típica es aprender distribuciones en espacios funcionales, que involucran efectivamente una infinidad de parámetros. La idea clave es que en muchas aplicaciones las distribuciones de dimensión infinita aparecen solo como un dispositivo computacional intermedio y no son necesarias ni para la especificación inicial de creencias previas ni para el enunciado de la inferencia final.

Definicion formal

Dado un conjunto medible S , una distribución de probabilidad base H y un número real positivo ${\displaystyle \alpha }$, el proceso de Dirichlet ${\displaystyle \operatorname {DP} (H,\alpha )}$es un proceso estocástico cuya ruta muestral (o realización , es decir, una secuencia infinita de variables aleatorias extraídas del proceso) es una distribución de probabilidad sobre S , de modo que se cumple lo siguiente. Para cualquier partición finita medible de S , denotada${\displaystyle \{B_{i}\}_{i=1}^{n}}$,

${\displaystyle {\text{if }}X\sim \operatorname {DP} (H,\alpha )}$

${\displaystyle {\text{then }}(X(B_{1}),\dots ,X(B_{n}))\sim \operatorname {Dir} (\alpha H(B_{1}),\dots ,\alpha H(B_{n})),}$

dónde ${\displaystyle \operatorname {Dir} }$denota la distribución de Dirichlet y la notación${\displaystyle X\sim D}$ significa que la variable aleatoria ${\displaystyle X}$ tiene la distribución ${\displaystyle D}$.

Vistas alternativas

Hay varias vistas equivalentes del proceso de Dirichlet. Además de la definición formal anterior, el proceso de Dirichlet se puede definir implícitamente a través del teorema de de Finetti como se describe en la primera sección; esto a menudo se denomina proceso de restaurante chino . Una tercera alternativa es el proceso de ruptura de palos , que define el proceso de Dirichlet de manera constructiva escribiendo una distribución muestreada del proceso como${\displaystyle f(x)=\sum _{k=1}^{\infty }\beta _{k}\delta _{x_{k}}(x)}$, dónde ${\displaystyle \{x_{k}\}_{k=1}^{\infty }}$ son muestras de la distribución base ${\displaystyle H}$, ${\displaystyle \delta _{x_{k}}}$es una función indicadora centrada en${\displaystyle x_{k}}$ (cero en todas partes excepto por ${\displaystyle \delta _{x_{k}}(x_{k})=1}$) y el ${\displaystyle \beta _{k}}$están definidos por un esquema recursivo que muestra repetidamente de la distribución beta ${\displaystyle \operatorname {Beta} (1,\alpha )}$.

El proceso del restaurante chino

Animación de un proceso de restaurante chino con parámetro de escala ${\displaystyle \alpha =0.5}$. Las tablas se ocultan una vez que los clientes de una mesa ya no se pueden mostrar; sin embargo, cada mesa tiene un número infinito de asientos. (Grabación de una animación interactiva. ^[2] )

Una metáfora ampliamente utilizada para el proceso de Dirichlet se basa en el llamado proceso de restaurante chino . La metáfora es la siguiente:

Imagínese un restaurante chino en el que entran clientes. Un nuevo cliente se sienta en una mesa con una probabilidad proporcional al número de clientes que ya están sentados allí. Además, un cliente abre una nueva tabla con una probabilidad proporcional al parámetro de escala${\displaystyle \alpha }$. Después de ingresar un número infinito de clientes, se obtiene una distribución de probabilidad sobre un número infinito de tablas a elegir. Esta distribución de probabilidad sobre las tablas es una muestra aleatoria de las probabilidades de observaciones extraídas de un proceso de Dirichlet con parámetro de escala.${\displaystyle \alpha }$.

Si uno asocia extrae de la medida base ${\displaystyle H}$ con cada tabla, la distribución resultante sobre el espacio muestral ${\displaystyle S}$es una muestra aleatoria de un proceso de Dirichlet. El proceso del restaurante chino está relacionado con el esquema de muestreo de urnas de Pólya, que produce muestras de distribuciones de Dirichlet finitas.

Debido a que los clientes se sientan en una mesa con una probabilidad proporcional al número de clientes que ya están sentados en la mesa, se pueden deducir dos propiedades del DP:

1. El proceso de Dirichlet exhibe una propiedad que se refuerza a sí mismo: cuanto más a menudo se muestrea un valor dado en el pasado, es más probable que se muestre nuevamente.
2. Incluso si ${\displaystyle H}$es una distribución sobre un conjunto incontable , existe una probabilidad distinta de cero de que dos muestras tengan exactamente el mismo valor porque la masa de probabilidad se concentrará en un pequeño número de tablas.

El proceso de rotura de palos

Un tercer enfoque del proceso de Dirichlet es la denominada vista del proceso de rotura de palos. Recuerde que las extracciones de un proceso de Dirichlet son distribuciones sobre un conjunto${\displaystyle S}$. Como se señaló anteriormente, la distribución dibujada es discreta con probabilidad 1. En la vista del proceso de ruptura de palos, usamos explícitamente la discreción y damos la función de masa de probabilidad de esta distribución discreta (aleatoria) como:

${\displaystyle f(\theta )=\sum _{k=1}^{\infty }\beta _{k}\cdot \delta _{\theta _{k}}(\theta )}$

dónde ${\displaystyle \delta _{\theta _{k}}}$es la función indicadora que se evalúa a cero en todas partes, excepto para${\displaystyle \delta _{\theta _{k}}(\theta _{k})=1}$. Dado que esta distribución es aleatoria en sí misma, su función de masa está parametrizada por dos conjuntos de variables aleatorias: las ubicaciones${\displaystyle \left\{\theta _{k}\right\}_{k=1}^{\infty }}$ y las probabilidades correspondientes ${\displaystyle \left\{\beta _{k}\right\}_{k=1}^{\infty }}$. A continuación, presentamos sin pruebas cuáles son estas variables aleatorias.

Las localizaciones ${\displaystyle \theta _{k}}$ son independientes e idénticamente distribuidos según ${\displaystyle H}$, la distribución base del proceso de Dirichlet. Las probabilidades${\displaystyle \beta _{k}}$ se dan mediante un procedimiento que se asemeja a la rotura de un palo de longitud unitaria (de ahí el nombre):

${\displaystyle \beta _{k}=\beta '_{k}\cdot \prod _{i=1}^{k-1}\left(1-\beta '_{i}\right)}$

dónde ${\displaystyle \beta '_{k}}$son variables aleatorias independientes con la distribución beta ${\displaystyle \operatorname {Beta} (1,\alpha )}$. El parecido con 'romper palos' se puede ver considerando${\displaystyle \beta _{k}}$como la longitud de un trozo de palo. Comenzamos con una varilla de longitud unitaria y en cada paso rompemos una porción de la varilla restante de acuerdo con${\displaystyle \beta '_{k}}$ y asigne esta pieza rota a ${\displaystyle \beta _{k}}$. La fórmula puede entenderse observando que después de que los primeros  valores k - 1 tengan sus porciones asignadas, la longitud del resto de la varilla es${\displaystyle \prod _{i=1}^{k-1}\left(1-\beta '_{i}\right)}$ y esta pieza se rompe según ${\displaystyle \beta '_{k}}$ y es asignado a ${\displaystyle \beta _{k}}$.

El pequeño ${\displaystyle \alpha }$ es decir, se dejará menos palo para los valores subsiguientes (en promedio), produciendo distribuciones más concentradas.

El proceso de rotura de palos es similar a la construcción en la que se toman muestras secuencialmente de distribuciones beta marginales para generar una muestra a partir de una distribución de Dirichlet . Consulte ^[3] para ver la prueba.

El esquema de la urna de Pólya

Otra forma más de visualizar el proceso de Dirichlet y el proceso del restaurante chino es como un esquema de urna Pólya modificado a veces llamado esquema de muestreo Blackwell-MacQueen . Imagina que empezamos con una urna llena de${\displaystyle \alpha }$bolas negras. Luego procedemos de la siguiente manera:

1. Cada vez que necesitamos una observación, sacamos una bola de la urna.
2. Si la bola es negra, generamos un nuevo color (no negro) uniformemente, etiquetamos una nueva bola de este color, dejamos caer la nueva bola en la urna junto con la bola que dibujamos y devolvemos el color que generamos.
3. De lo contrario, etiquete una nueva bola con el color de la bola que dibujamos, deje caer la nueva bola en la urna junto con la bola que dibujamos y devuelva el color que observamos.

La distribución resultante sobre los colores es la misma que la distribución sobre las tablas en el proceso del restaurante chino. Además, cuando dibujamos una bola negra, si en lugar de generar un nuevo color, elegimos un valor aleatorio de una distribución base${\displaystyle H}$ y use ese valor para etiquetar la nueva bola, la distribución resultante sobre las etiquetas será la misma que la distribución sobre los valores en un proceso de Dirichlet.

Utilizar como distribución previa

El Proceso de Dirichlet se puede utilizar como distribución previa para estimar la distribución de probabilidad que genera los datos. En esta sección, consideramos el modelo

${\displaystyle {\begin{aligned}P&\sim {\textrm {DP}}(H,\alpha )\\X_{1},\cdots ,X_{n}|P&{\overset {\textrm {i.i.d.}}{\sim }}P.\end{aligned}}}$

La distribución del proceso de Dirichlet satisface la conjugación previa , la consistencia posterior y el teorema de Bernstein-von Mises . ^[4]

Conjugación previa

En este modelo, la distribución posterior es nuevamente un proceso de Dirichlet. Esto significa que el proceso de Dirichlet es un previo conjugado para este modelo. La distribución posterior está dada por

${\displaystyle {\begin{aligned}P|X_{1},\cdots ,X_{n}&\sim {\textrm {DP}}\left({\frac {\alpha }{\alpha +n}}H+{\frac {1}{\alpha +n}}\sum _{i=1}^{n}\delta _{X_{i}},\;\alpha +n\right)\\&={\textrm {DP}}\left({\frac {\alpha }{\alpha +n}}H+{\frac {n}{\alpha +n}}\mathbb {P} _{n},\;\alpha +n\right)\end{aligned}}}$

dónde ${\displaystyle \mathbb {P} _{n}}$ se define a continuación.

Consistencia posterior

Si adoptamos el punto de vista frecuentista de la probabilidad, creemos que existe una verdadera distribución de probabilidad.${\displaystyle P_{0}}$que generó los datos. Entonces resulta que el proceso de Dirichlet es consistente en la topología débil , lo que significa que para cada vecindario débil${\displaystyle U}$ de ${\displaystyle P_{0}}$, la probabilidad posterior de ${\displaystyle U}$ converge a ${\displaystyle 1}$.

Teorema de Bernstein-Von Mises

Para interpretar los conjuntos creíbles como conjuntos de confianza, se necesita un teorema de Bernstein-von Mises . En el caso del proceso de Dirichlet comparamos la distribución posterior con el proceso empírico ${\displaystyle \mathbb {P} _{n}={\frac {1}{n}}\sum _{i=1}^{n}\delta _{X_{i}}}$. Suponer${\displaystyle {\mathcal {F}}}$ es un ${\displaystyle P_{0}}$-Clase Donador, es decir

${\displaystyle {\begin{aligned}{\sqrt {(}}n)\left(\mathbb {P} _{n}-P_{0}\right)\rightsquigarrow G_{P_{0}}\end{aligned}}}$

por un puente browniano ${\displaystyle G_{P_{0}}}$. Supongamos también que existe una función${\displaystyle F}$ tal que ${\displaystyle F(x)\geq \sup _{f\in {\mathcal {F}}}f(x)}$ tal que ${\displaystyle \int F^{2}\mathrm {d} H<\infty }$, luego, ${\displaystyle P_{0}}$ casi seguro

${\displaystyle {\sqrt {n}}\left(P-\mathbb {P} _{n}\right)|X_{1},\cdots ,X_{n}\rightsquigarrow G_{P_{0}}.}$

Esto implica que los conjuntos creíbles que construye son conjuntos de confianza asintóticos, y la inferencia bayesiana basada en el proceso de Dirichlet es asintóticamente también una inferencia frecuentista válida.

Uso en modelos de mezcla de Dirichlet

Simulación de 1000 observaciones extraídas de un modelo de mezcla de Dirichlet. Cada observación dentro de un grupo se extrae independientemente de la distribución normal multivariante${\displaystyle N(\mu _{k},1/4)}$. El grupo significa ${\displaystyle \mu _{k}}$ se extraen de una distribución G que a su vez se extrae de un proceso de Dirichlet con parámetro de concentración ${\displaystyle \alpha =0.5}$ y distribución base ${\displaystyle H=N(2,16)}$. Cada fila es una nueva simulación.

Para comprender qué son los procesos de Dirichlet y el problema que resuelven, consideramos el ejemplo de la agrupación de datos . Es una situación común que se asume que los puntos de datos se distribuyen de manera jerárquica, donde cada punto de datos pertenece a un grupo (elegido al azar) y los miembros de un grupo se distribuyen de forma aleatoria dentro de ese grupo.

Ejemplo 1

Por ejemplo, podríamos estar interesados ​​en cómo la gente votará sobre una serie de preguntas en las próximas elecciones. Un modelo razonable para esta situación podría ser clasificar a cada votante como liberal, conservador o moderado y luego modelar el evento en el que un votante dice "Sí" a una pregunta en particular como una variable aleatoria de Bernoulli con la probabilidad dependiendo de qué grupo político pertenecen a. Al observar cómo se emitieron los votos en años anteriores sobre leyes similares, se podría ajustar un modelo predictivo utilizando un algoritmo de agrupamiento simple como k-means . Sin embargo, ese algoritmo requiere conocer de antemano la cantidad de clústeres que generaron los datos. En muchas situaciones, no es posible determinar esto con anticipación, e incluso cuando podemos asumir razonablemente una cantidad de grupos, aún nos gustaría poder verificar esta suposición. Por ejemplo, en el ejemplo de votación anterior, la división en liberales, conservadores y moderados podría no estar lo suficientemente ajustada; Atributos como religión, clase o raza también podrían ser críticos para modelar el comportamiento de los votantes, lo que resulta en más grupos en el modelo.

Ejemplo 2

Como otro ejemplo, podríamos estar interesados ​​en modelar las velocidades de las galaxias usando un modelo simple asumiendo que las velocidades están agrupadas, por ejemplo, asumiendo que cada velocidad se distribuye de acuerdo con la distribución normal. ${\displaystyle v_{i}\sim N(\mu _{k},\sigma ^{2})}$, donde el ${\displaystyle i}$La observación pertenece a la ${\displaystyle k}$El cúmulo de galaxias con una velocidad esperada común. En este caso, está lejos de ser obvio cómo determinar a priori cuántos conglomerados (de velocidades comunes) debería haber y cualquier modelo para esto sería altamente sospechoso y debería cotejarse con los datos. Al utilizar un proceso de Dirichlet previo para la distribución de las medias de los conglomerados, evitamos la necesidad de especificar explícitamente con anticipación cuántos conglomerados hay, aunque el parámetro de concentración todavía lo controla implícitamente.

Consideramos este ejemplo con más detalle. Un primer modelo ingenuo es presuponer que existen${\displaystyle K}$grupos de velocidades normalmente distribuidas con varianza fija conocida común ${\displaystyle \sigma ^{2}}$. Denotando el evento que el${\displaystyle i}$La observación está en el ${\displaystyle k}$th cluster como ${\displaystyle z_{i}=k}$ podemos escribir este modelo como:

${\displaystyle {\begin{aligned}(v_{i}\mid z_{i}=k,\mu _{k})&\sim N(\mu _{k},\sigma ^{2})\\\operatorname {P} (z_{i}=k)&=\pi _{k}\\({\boldsymbol {\pi }}\mid \alpha )&\sim \operatorname {Dir} \left({\frac {\alpha }{K}}\cdot \mathbf {1} _{K}\right)\\\mu _{k}&\sim H(\lambda )\end{aligned}}}$

Es decir, asumimos que los datos pertenecen a ${\displaystyle K}$ grupos distintos con medios ${\displaystyle \mu _{k}}$ y eso ${\displaystyle \pi _{k}}$ es la probabilidad previa (desconocida) de que un punto de datos pertenezca al ${\displaystyle k}$th cluster. Suponemos que no tenemos información inicial que distinga los grupos, que es capturada por el simétrico anterior${\displaystyle \operatorname {Dir} \left(\alpha /K\cdot \mathbf {1} _{K}\right)}$. Aquí${\displaystyle \operatorname {Dir} }$denota la distribución de Dirichlet y${\displaystyle \mathbf {1} _{K}}$ denota un vector de longitud ${\displaystyle K}$ donde cada elemento es 1. Además, asignamos distribuciones anteriores independientes e idénticas ${\displaystyle H(\lambda )}$ a cada una de las medias del clúster, donde ${\displaystyle H}$ puede ser cualquier distribución paramétrica con parámetros indicados como ${\displaystyle \lambda }$. Los hiperparámetros${\displaystyle \alpha }$ y ${\displaystyle \lambda }$se toman como constantes fijas conocidas, elegidas para reflejar nuestras creencias previas sobre el sistema. Para comprender la conexión con los procesos previos de Dirichlet, reescribimos este modelo en una forma equivalente pero más sugerente:

${\displaystyle {\begin{aligned}(v_{i}\mid {\tilde {\mu }}_{i})&\sim N({\tilde {\mu }}_{i},\sigma ^{2})\\{\tilde {\mu }}_{i}&\sim G=\sum _{k=1}^{K}\pi _{k}\delta _{\mu _{k}}({\tilde {\mu }}_{i})\\({\boldsymbol {\pi }}\mid \alpha )&\sim \operatorname {Dir} \left({\frac {\alpha }{K}}\cdot \mathbf {1} _{K}\right)\\\mu _{k}&\sim H(\lambda )\end{aligned}}}$

En lugar de imaginar que a cada punto de datos se le asigna primero un grupo y luego se extrae de la distribución asociada a ese grupo, ahora pensamos en cada observación asociada con el parámetro ${\displaystyle {\tilde {\mu }}_{i}}$ extraído de una distribución discreta ${\displaystyle G}$ con apoyo en el ${\displaystyle K}$medio. Es decir, ahora estamos tratando el${\displaystyle {\tilde {\mu }}_{i}}$ como extraído de la distribución aleatoria ${\displaystyle G}$ y nuestra información previa se incorpora al modelo mediante la distribución sobre distribuciones ${\displaystyle G}$.

"> Reproducir medios

Animación del proceso de agrupamiento de datos unidimensionales utilizando distribuciones gaussianas extraídas de un proceso de Dirichlet. Los histogramas de los grupos se muestran en diferentes colores. Durante el proceso de estimación de parámetros, se crean nuevos clústeres y crecen con los datos. La leyenda muestra los colores del grupo y el número de puntos de datos asignados a cada grupo.