Pourquoi utiliser le graphe factoriel pour linférence bayésienne?

Je vais essayer de répondre ma propre question.

Message

Une notion très importante de graphe de facteurs est message , qui peut être compris comme A dit quelque chose sur B, si le message est passé de A à B.

Dans le contexte du modèle probabiliste, message du facteur $ f $ à la variable $ x $ peut être désigné comme $ \ mu_ {f \ to x} $ , qui peut être compris comme $ f $ sait quelque chose (distribution de probabilité dans ce cas) et le dit à $ x $ .

Le facteur résume les messages

Dans le  » factor  » context, pour connaître la distribution de probabilité dune variable, il faut avoir tous les messages prêts à partir de ses n les facteurs voisins, puis résumez tous les messages pour dériver la distribution.

Par exemple, dans le graphique suivant, les arêtes, $ x_i $ , sont les variables et les nœuds, $ f_i $ , sont des facteurs reliés par des arêtes.

Pour connaître $ P (x_4) $ , nous devons connaître le $ \ mu_ {f_3 \ to x_4} $ et $ \ mu_ {f_4 \ to x_4} $ et les résumer ensemble.

Structure récursive des messages

Alors comment connaître ces deux messages? Par exemple, $ \ mu_ {f_4 \ to x_4} $ . Il peut être vu comme le message après avoir résumé deux messages, $ \ mu_ {x_5 \ to f_4} $ et $ \ mu_ {x_6 \ à f_4} $ . Et $ \ mu_ {x_6 \ to f_4} $ est essentiellement $ \ mu_ {f_6 \ to x_6} $ , qui peut être calculé à partir dautres messages.

Il sagit de la structure récursive des messages, les messages peuvent être définis par des messages .

La récursivité est une bonne chose, une pour une meilleure compréhension, une pour une implémentation plus facile du programme informatique.

Conclusion

Les avantages des facteurs sont:

1. Facteur, qui résume les messages entrants et sort le message sortant, active les messages qui sont essentiels pour le calcul marginal
2. Les facteurs activent la structure récursive du calcul des messages, ce qui facilite le passage du message ou le processus de propagation de croyance comprendre, et peut-être plus facile à mettre en œuvre.

Commentaires

• Pour être honnête, jestime quil sagit davantage dun résumé de la façon dont pour effectuer une inférence dans des graphes de facteurs au moyen de la transmission de messages, quune réponse au réel question.

Un réseau bayésien, par définition, est une collection de variables aléatoires $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ et un graphe $ G $ tel que la fonction de probabilité $ P (X_1, …, X_n) $ prend en compte les probabilités conditionnelles dune manière déterminée par $ G $. Voir http://en.wikipedia.org/wiki/Factor_graph .

Plus important encore, les facteurs du réseau bayésien sont de la forme $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

Un graphe de facteurs, même sil est plus général, est le même en ce sens quil sagit dune manière graphique de conserver des informations à propos de la factorisation de $ P (X_1, …, X_n) $ ou de toute autre fonction.

La différence est que lorsquun réseau bayésien est converti en un graphe factoriel, les facteurs du graphe factoriel sont regroupés. Par exemple, un facteur dans le graphe factoriel peut être $ P (X_i | X_ {j_1}, .., X_ {j_n}) P (X_ {j_n}) P (X_ {j_1}) = P (X_i | X_ { j_2}, .., X_ {j_ {n-1}}) $. Le réseau bayésien dorigine stockait cela sous forme de trois facteurs, mais le graphique de facteur ne le stockait que comme un seul facteur. En général, le graphe de facteurs dun réseau bayésien garde des traces de moins de factorisations que le réseau bayésien dorigine.

A Le graphe factoriel nest quune autre représentation dun modèle bayésien. Si vous aviez un algorithme exact pour linférence dans un réseau bayésien particulier et un autre algorithme exact pour linférence dans le graphe factoriel correspondant, les deux résultats seraient les mêmes. Les graphes de facteurs se trouvent être une représentation utile pour dériver des algorithmes dinférence efficaces (exacts et approximatifs) en exploitant lindépendance conditionnelle entre les variables dans le modèle, atténuant ainsi la malédiction de la dimensionnalité .

Pour donner une analogie: la transformée de Fourier contient exactement les mêmes informations que la représentation temporelle dun signal, mais certaines tâches sont plus faciles accomplis dans le domaine fréquentiel, et certains sont plus faciles à réaliser dans le domaine temporel. Dans le même sens, un graphe factoriel est juste une reformulation de la même information (le modèle probabiliste), ce qui est utile pour dériver des algorithmes intelligents mais ne « t vraiment pas  » add  » nimporte quoi.

Pour être plus précis, supposons que vous êtes intéressé à dériver le marginal $ p (x_i) $ dune certaine quantité dans un modèle, ce qui nécessite lintégration sur toutes les autres variables:

$$ p (x_i) = \ int p (x_1, x_2, \ ldots, x_i, \ ldots, x_N) dx_1x_2 \ ldots x_ {i-1} x_ {i + 1} \ ldots x_N $$

Dans un haut -modèle dimensionnel, il sagit dune intégration sur un espace de grande dimension, qui est très difficile à calculer. (Ce problème de marginalisation / intégration est ce qui rend linférence en grandes dimensions difficile / insoluble. Une approche consiste à trouver des moyens intelligents pour évaluer efficacement cette intégrale, ce que la chaîne de Markov Monte Les méthodes de Carlo (MCMC) le font. Celles-ci sont connues pour souffrir de temps de calcul notoirement longs.)

Sans entrer dans trop de détails, un graphe factoriel encode le fait que beaucoup de ces variables sont conditionnellement indépendantes les unes des autres . Cela permet de remplacer l’intégration de haute dimension ci-dessus par une série de problèmes d’intégration de dimension beaucoup plus faible , à savoir les calculs de les différents messages. En exploitant la structure du problème de cette manière, linférence devient possible. Cest le principal avantage de la formulation de linférence en termes de graphes de facteurs.