¿Dónde está la teoría de grafos en los modelos gráficos?

29

Las introducciones a los modelos gráficos los describen como "... un matrimonio entre la teoría de gráficos y la teoría de probabilidad".

Obtengo la parte de la teoría de la probabilidad, pero tengo problemas para comprender dónde encaja exactamente la teoría de gráficos. ¿Qué ideas de la teoría de gráficos han ayudado a profundizar nuestra comprensión de las distribuciones de probabilidad y la toma de decisiones bajo incertidumbre?

Estoy buscando ejemplos concretos, más allá del uso obvio de la terminología teórica de grafos en las PGM, como clasificar una PGM como "árbol" o "bipartito" o "no dirigido", etc.

graphical-model graph-theory distributions Vimal
fuente

33

Hay muy poca teoría de grafos matemáticos verdaderos en los modelos gráficos probabilísticos, donde por teoría de grafos matemáticos verdaderos me refiero a pruebas sobre camarillas, órdenes de vértices, teoremas de corte mínimo y flujo máximo, etc. Incluso algo tan fundamental como el Teorema de Euler y el Lema del apretón de manos no se utilizan, aunque supongo que uno podría invocarlos para verificar alguna propiedad del código de computadora utilizado para actualizar las estimaciones probabilísticas. Además, los modelos gráficos probabilistas rara vez usan más que un subconjunto de las clases de gráficos, como los gráficos múltiples. Los teoremas sobre flujos en gráficos no se usan en modelos gráficos probabilísticos.

Si el estudiante A fuera un experto en probabilidad pero no supiera nada sobre teoría de grafos, y el estudiante B fuera un experto en teoría de gráficos pero no supiera nada sobre probabilidad, entonces A ciertamente aprendería y comprendería modelos gráficos probabilísticos más rápido que B.

David G. Stork
fuente

8

En un sentido estricto, la teoría de grafos parece estar poco conectada con las PGM. Sin embargo, los algoritmos gráficos son útiles. Las PGM comenzaron con la inferencia de paso de mensajes, que es un subconjunto de la clase general de algoritmos de paso de mensajes en gráficos (puede ser, esa es la razón de la palabra "gráfico" en ellos). Los algoritmos de corte de gráficos se usan ampliamente para la inferencia de campo aleatorio de Markov en visión por computadora; se basan en los resultados similares al teorema de Ford-Fulkerson (el flujo máximo es igual al corte mínimo); Los algoritmos más populares son probablemente Boykov – Kolmogorov e IBFS.

Referencias [Murphy, 2012 , §22.6.3] cubre el uso de cortes gráficos para la inferencia MAP. Ver también [Kolmogorom y Zabih, 2004 ; Boykov et al., PAMI 2001] , que cubren la optimización en lugar del modelado.

Roman Shapovalov
fuente

Es interesante observar que los algoritmos de corte de gráficos se utilizan en MRF. ¿Podría señalar una referencia? Según la respuesta anterior de David Stork, parece que estos algoritmos surgen debido al hecho de que la teoría de gráficos era una herramienta de modelado útil, en lugar de alguna conexión fundamental entre la teoría de gráficos y las PGM.

Vimal

Agregué las referencias que me pediste. A partir de su última declaración, ¿cómo podemos separar las causas, es decir, saber si es fundamental o no?

Roman Shapovalov

@overrider, ¿podría proporcionar referencias completas para que los documentos se puedan buscar fácilmente ...? Buscar en Google puede llevar a las personas a las referencias, pero también podría terminar perdiendo el tiempo para obtener resultados irrelevantes. Por lo tanto, es bueno agregar títulos, editoriales, nombres de revistas, enlaces, etc.

Tim

2

Los algoritmos de corte de gráficos son útiles en la visión por computadora, pero no en los modelos gráficos probabilísticos. Un problema en la visión estereofónica es el problema de la correspondencia: encontrar qué puntos de la imagen A corresponden a los puntos de la imagen B. Se puede configurar un gráfico donde los vértices corresponden a los puntos característicos en las dos imágenes y un gráfico representa todas las correspondencias posibles. Entonces, el problema de encontrar las correspondencias "adecuadas" se puede considerar como un problema de corte gráfico. No existe tal uso en modelos gráficos genéricos, aunque supongo que uno podría intentar mapear este problema de visión por computadora en modelos gráficos.

David G. Stork

2

@ DavidG.Stork Existen otros problemas de visión por computadora que aplican cortes de gráficos de manera similar: segmentación de imágenes, creación de collages, etc., por lo que el enfoque es lo suficientemente general. Esos problemas pueden expresarse naturalmente en términos de modelos gráficos no dirigidos (aunque los documentos no siempre lo hacen). Eso permite utilizar diferentes algoritmos de inferencia MRF, así como el ajuste del modelo. Por otro lado, los cortes de gráficos pueden optimizar un subconjunto bastante grande de MRF, por lo que se pueden aplicar más allá de la visión, por ejemplo, para el análisis de redes sociales (aunque no puedo recordar documentos específicos ahora).

Roman Shapovalov

4

Se ha investigado el vínculo entre la facilidad de decodificación de los códigos de verificación de paridad de baja densidad (que obtiene excelentes resultados cuando lo considera un gráfico probabilístico y aplica la propagación de creencias de bucle) y la circunferencia del gráfico formado por la matriz de verificación de paridad . Este enlace a la circunferencia se remonta a cuando se inventaron los LDPC [1], pero hubo más trabajo en la última década más o menos [2] [3] después de que Mackay et al [4] redescubrieran por separado sus propiedades. .

A menudo veo el comentario de Pearl sobre el tiempo de convergencia de la propagación de creencias dependiendo del diámetro del gráfico que se cita. Pero no conozco ningún trabajo que observe diámetros de gráficos en gráficos que no sean de árbol y qué efecto tiene.

RG Gallager. Códigos de verificación de paridad de baja densidad. MIT Press, 1963
IE Bocharova, F. Hug, R. Johannesson, BD Kudryashov y RV Satyukov. Nuevos códigos de verificación de paridad de baja densidad con gran circunferencia basados en hipergrafías. En Procedimientos de teoría de la información (ISIT), Simposio internacional IEEE 2010 en, páginas 819–823, 2010.
SC Tatikonda. Convergencia del algoritmo de suma de productos. En Taller de teoría de la información, 2003. Actas. 2003 IEEE, páginas 222 - 225, 2003
David JC MacKay y RM Neal. El rendimiento cercano al límite de Shannon de los códigos de verificación de paridad de baja densidad. Electronics Letters, 33 (6): 457–458, 1997.

Palmadita
fuente

3

Una aplicación exitosa de algoritmos gráficos a modelos gráficos probabilísticos es el algoritmo Chow-Liu . Resuelve el problema de encontrar la estructura de gráfico (árbol) óptima y se basa en el algoritmo de árboles de extensión máxima (MST).

p (x | T) = \prod_{t \in V} p (x_{t}) \prod_{(s, t) \in E} \frac{p (x_{s}, x_{t})}{p (x_{s}) p (x_{t})}

$\begin{equation} p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)} \end{equation}$

\frac{1}{N} \log P (D | θ, T) = \sum_{t \in V} \sum_{k} p_{M L} (x_{t} = k) \log p_{M L} (x_{t} = k) + \sum_{(s, t) \in E} I (x_{s}; x_{t} | θ_{s t})

$\begin{equation} \frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st}) \end{equation}$

I (x_{s}; x_{t} | θ_{s t})

$I(x_s;x_t|\theta_{st})$

x_{s}

$x_s$

x_{t}

$x_t$

x

$x$

k

$k$

T

$T$

$I(x_s;x_t|\theta_{st})$

Vadim Smolyakov
fuente

Hola vadim Gracias por su respuesta. Como una formulación en términos teóricos gráficos, tiene sentido. Pero también podría verse como un problema de optimización. El espíritu de la pregunta era investigar una conexión más fundamental. Por ejemplo, uno puede formular el problema de clasificación como una clasificación topológica en un gráfico, donde los nodos son números, y las flechas denotan una relación <=. Pero eso no establece una conexión fundamental entre la clasificación y los algoritmos de gráficos, ¿verdad?

Vimal

¿Dónde está la teoría de grafos en los modelos gráficos?

Respuestas: