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

Question

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

Entiendo la parte de la teoría de la probabilidad, pero me cuesta entender dónde encaja exactamente la teoría de los gráficos. ¿Qué conocimientos de la teoría de grafos han ayudado a profundizar en nuestra comprensión de las distribuciones de probabilidad y la toma de decisiones en condiciones de incertidumbre?

Busco ejemplos concretos, más allá del uso obvio de la terminología de la teoría de grafos en los MGP, como clasificar un MGP como "árbol" o "bipartito" o "no dirigido", etc.

Answer 1

Hay muy poca teoría matemática de los grafos en los modelos gráficos probabilísticos, y por teoría matemática de los grafos me refiero a las pruebas sobre las camarillas, los órdenes de los vértices, los teoremas de corte mínimo de 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 comprobar alguna propiedad del código informático utilizado para actualizar las estimaciones probabilísticas. Además, los modelos gráficos probabilísticos rara vez utilizan más que un subconjunto de clases de grafos, como los multigrafos. Los teoremas sobre los flujos en los grafos no se utilizan en los modelos gráficos probabilísticos.

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

Answer 2

En sentido estricto, el gráfico teoría parece estar vagamente conectada a las MGP. Sin embargo, el gráfico algoritmos son muy útiles. Los PGM empezaron con la inferencia de paso de mensajes, que es un subconjunto de la clase general de algoritmos de paso de mensajes sobre grafos (puede que esa sea la razón de la palabra "gráfico" en ellos). Los algoritmos de corte de grafos se utilizan ampliamente para la inferencia de campos aleatorios de Markov en la visión por ordenador; se basan en los resultados afines 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](http://www.cs.ubc.ca/~murphyk/MLbook/) En [§22.6.3] se cubre el uso de cortes de grafos para la inferencia MAP. Véase también [Kolmogorom y Zabih, 2004](http://www.cs.cornell.edu/~rdz/papers/kz-pami04.pdf) ; [Boykov et al., PAMI 2001] que cubren la optimización más que la modelización.

Answer 3

Se han realizado algunos trabajos que investigan la relación entre la facilidad de descodificación de los códigos de comprobación de paridad de baja densidad (que obtienen excelentes resultados cuando se considera un grafo probabilístico y se aplica la propagación de creencias Loopy), y la circunferencia del grafo formado por la matriz de comprobación de paridad. Este vínculo con la circunferencia se remonta a la época en que se inventaron los LDPCs[1], pero se ha trabajado más en la última década[2][3] después de que Mackay et al[4] los redescubrieran por separado y se dieran cuenta de sus propiedades.

A menudo veo el comentario de pearl sobre el tiempo de convergencia de la propagación de la creencia en función del diámetro del gráfico que se cita. Pero no conozco ningún trabajo que analice los diámetros de los grafos que no son de árbol y qué efecto tiene.

1. R. G. Gallager. Low Density Parity Check Codes. M.I.T. Press, 1963
2. I.E. Bocharova, F. Hug, R. Johannesson, B.D. Kudryashov y R.V. Satyukov. New low-density parity-check codes with large girth based on hypergraphs. En Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, páginas 819 -823, 2010.
3. S.C. Tatikonda. Convergencia del algoritmo suma-producto. En Information Theory Workshop, 2003. Proceedings. 2003 IEEE, páginas 222 - 225, 2003
4. David J. C. MacKay y R. M. Neal. Rendimiento cercano al límite de Shannon de los códigos de comprobación de paridad de baja densidad. Electronics Letters, 33(6):457-458, 1997.

Answer 4

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

Una probabilidad conjunta sobre un modelo gráfico de árbol puede escribirse como \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} Podemos escribir una log-verosimilitud normalizada como sigue: \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} donde $I(x_s;x_t|\theta_{st})$ es la información mutua entre $x_s$ y $x_t$ dada la distribución empírica de Máxima Verosimilitud (ML) que cuenta el número de veces que un nodo $x$ estaba en el estado $k$ . Como el primer término es independiente de la topología $T$ podemos ignorarlo y centrarnos en maximizar el segundo término.

La probabilidad logarítmica se maximiza mediante el cálculo del árbol de distribución de peso máximo, en el que los pesos de las aristas son los términos de información mutua por pares $I(x_s;x_t|\theta_{st})$ . El árbol de expansión de peso máximo se puede encontrar utilizando El algoritmo de Prim y Algoritmo de Kruskal .