Où est la théorie des graphes dans les modèles graphiques?

29

Les introductions aux modèles graphiques les décrivent comme "... un mariage entre la théorie des graphes et la théorie des probabilités".

J'obtiens la partie théorie des probabilités mais j'ai du mal à comprendre où exactement la théorie des graphes s'inscrit.

Je recherche des exemples concrets, au-delà de l'utilisation évidente de la terminologie de la théorie des graphes dans les PGM, comme classer une PGM comme un "arbre" ou "bipartite" ou "non orienté", etc.

graphical-model graph-theory distributions Vimal
la source

33

Il y a très peu de vraie théorie des graphes mathématiques dans les modèles graphiques probabilistes, où par vraie théorie des graphes mathématiques, je veux dire des preuves sur les cliques, les ordres des sommets, les théorèmes de coupe minimale du débit max, etc. Même quelque chose d'aussi fondamental que le théorème d'Euler et le lemme de prise de contact ne sont pas utilisés, bien que je suppose que l'on pourrait les invoquer pour vérifier certaines propriétés du code informatique utilisé pour mettre à jour les estimations probabilistes. De plus, les modèles graphiques probabilistes utilisent rarement plus d'un sous-ensemble des classes de graphiques, comme les multi-graphiques. Les théorèmes sur les flux dans les graphiques ne sont pas utilisés dans les modèles graphiques probabilistes.

Si l'étudiant A était un expert en probabilité mais ne savait rien de la théorie des graphes, et que l'étudiant B était un expert en théorie des graphes mais ne savait rien de la probabilité, alors A apprendrait et comprendrait certainement les modèles graphiques probabilistes plus rapidement que B.

David G. Stork
la source

8

Au sens strict, la théorie des graphes semble peu reliée aux PGM. Cependant, les algorithmes graphiques sont utiles. Les PGM ont commencé par l'inférence de passage de message, qui est un sous-ensemble de la classe générale des algorithmes de passage de message sur les graphiques (c'est peut-être la raison du mot «graphique»). Les algorithmes de coupe graphique sont largement utilisés pour l'inférence de champ aléatoire de Markov en vision par ordinateur; ils sont basés sur des résultats similaires au théorème de Ford – Fulkerson (le débit max est égal à la coupe min); les algorithmes les plus populaires sont probablement Boykov – Kolmogorov et IBFS.

Les références. [Murphy, 2012 , §22.6.3] couvre l'utilisation des coupes graphiques pour l'inférence MAP. Voir également [Kolmogorom et Zabih, 2004 ; Boykov et al., PAMI 2001] , qui couvrent l'optimisation plutôt que la modélisation.

Roman Shapovalov
la source

Il est intéressant de noter que des algorithmes de coupe graphique sont utilisés dans les MRF. Pourriez-vous indiquer une référence? Sur la base de la réponse de David Stork ci-dessus, il semble que ces algorithmes se posent du fait que la théorie des graphes était un outil de modélisation utile, plutôt que d'une connexion fondamentale entre la théorie des graphes et les PGM.

Vimal

J'ai ajouté les références comme vous l'avez demandé. Depuis votre dernière déclaration, comment pouvons-nous séparer les causes, c'est-à-dire dire si elles sont fondamentales ou non?

Roman Shapovalov

@overrider pourriez-vous fournir des références complètes afin que les articles puissent être facilement recherchés ..? La recherche sur Google peut conduire les gens aux références, mais pourrait également se solder par une perte de temps pour des résultats non pertinents. Donc, les titres, les éditeurs, les noms des revues, les liens, etc. sont une bonne chose à ajouter.

Tim

2

Les algorithmes de coupe de graphes sont utiles en vision par ordinateur mais pas les modèles graphiques probabilistes. Un problème en vision stéréo est le problème de correspondance: trouver quels points dans l'image A correspondent à des points dans l'image B. On peut mettre en place un graphique où les sommets correspondent aux points caractéristiques dans les deux images et un graphique représente toutes les correspondances possibles. Ensuite, le problème de la recherche des correspondances «appropriées» peut être présenté comme un problème graphique. Il n'y a pas une telle utilisation dans les modèles graphiques génériques, bien que je suppose que l'on pourrait essayer de cartographier ce problème de vision par ordinateur sur des modèles graphiques.

David G.Stork

2

@ DavidG.Stork Il existe d'autres problèmes de vision par ordinateur qui appliquent des coupes de graphes de la même manière: segmentation d'images, création de collages, etc., l'approche est donc assez générale. Ces problèmes peuvent s'exprimer naturellement en termes de modèles graphiques non dirigés (bien que les articles ne le fassent pas toujours). Cela permet d'utiliser différents algorithmes d'inférence MRF, ainsi que l'ajustement de modèle. D'un autre côté, les coupes graphiques peuvent optimiser un sous-ensemble assez important de MRF, donc peuvent être appliquées au-delà de la vision, par exemple pour l'analyse des réseaux sociaux (bien que je ne puisse pas me souvenir d'articles spécifiques maintenant).

Roman Shapovalov

4

Il y a eu un certain travail sur le lien entre la facilité de décodage des codes de contrôle de parité à faible densité (qui obtient d'excellents résultats lorsque vous le considérez comme un graphique probabiliste et appliquez la propagation de croyance de Loopy), et la circonférence du graphique formé par la matrice de contrôle de parité . Ce lien avec la circonférence remonte à l'époque où les LDPC ont été inventés [1], mais il y a eu d'autres travaux au cours de la dernière décennie [2] [3] après la redécouverte séparément par Mackay et al [4] et leurs propriétés remarquées .

Je vois souvent le commentaire de Pearl sur le temps de convergence de la propagation des croyances en fonction du diamètre du graphique cité. Mais je ne connais aucun travail sur les diamètres des graphes dans les graphes non arborescents et quel effet cela a.

RG Gallager. Codes de contrôle de parité à faible densité. MIT Press, 1963
IE Bocharova, F. Hug, R. Johannesson, BD Kudryashov et RV Satyukov. Nouveaux codes de contrôle de parité à faible densité avec large circonférence basés sur des hypergraphes. In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 819 –823, 2010.
SC Tatikonda. Convergence de l'algorithme somme-produit. Dans Information Theory Workshop, 2003. Actes. 2003 IEEE, pages 222-225, 2003
David JC MacKay et RM Neal. Near Shannon limite les performances des codes de contrôle de parité à faible densité. Electronics Letters, 33 (6): 457–458, 1997.

Tapoter
la source

3

L'algorithme de Chow-Liu est une application réussie des algorithmes de graphes aux modèles graphiques probabilistes . Il résout le problème de la recherche de la structure de graphe (arborescente) optimale et est basé sur l'algorithme d'arbres couvrant maximum (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} bûche P (ré | θ, T) = \sum_{t \in V} \sum_{k} p_{M L} (X_{t} = k) bûche p_{M L} (X_{t} = k) + \sum_{(s, t) \in E} je (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$

La log-vraisemblance est maximisée en calculant le poids maximal couvrant l'arbre, où les poids de bord sont les termes d'information mutuelle par paire $I(x_s;x_t|\theta_{st})$

Vadim Smolyakov
la source

Salut Vadim. Merci pour votre réponse. En tant que formulation en termes théoriques des graphes, cela a du sens. Mais on pourrait aussi le voir comme un problème d'optimisation. L'esprit de la question était de rechercher un lien plus fondamental. Par exemple, on peut formuler le problème de tri comme un tri topologique sur un graphique, où les nœuds sont des nombres et les flèches indiquent une relation <=. Mais cela ne fait pas de lien fondamental entre les algorithmes de tri et de graphe, non?

Vimal

Où est la théorie des graphes dans les modèles graphiques?

Réponses: