Warum einen Faktorgraphen für die Bayessche Inferenz verwenden?

Ich werde versuchen zu antworten meine eigene Frage.

Nachricht

Ein sehr wichtiger Begriff des Faktorgraphen ist Nachricht , was als A verstanden werden kann, sagt etwas über B aus, wenn die Nachricht von A nach B übergeben wird.

Im Kontext des Wahrscheinlichkeitsmodells Nachricht vom Faktor $ f $ bis Variable $ x $ kann als $ \ mu_ {f \ bis x} $ bezeichnet werden , was verstanden werden kann als $ f $ weiß etwas (in diesem Fall Wahrscheinlichkeitsverteilung) und teilt es mit $ x $ .

Faktor fasst Nachrichten zusammen

Im “ -Faktor “ context, um die Wahrscheinlichkeitsverteilung einer Variablen zu kennen, müssen alle Nachrichten von ihrem n bereit sein benachbarte Faktoren und fassen dann alle Nachrichten zusammen, um die Verteilung abzuleiten.

In der folgenden Grafik sind beispielsweise die Kanten $ x_i $ Variablen und Knoten, $ f_i $ , sind Faktoren, die durch Kanten verbunden sind.

Um $ P (x_4) $ zu kennen, müssen wir den $ \ mu_ {f_3 kennen \ bis x_4} $ und $ \ mu_ {f_4 \ bis x_4} $ und fassen sie zusammen.

Rekursive Struktur von Nachrichten

Woher wissen Sie dann diese beiden Nachrichten? Beispiel: $ \ mu_ {f_4 \ bis x_4} $ . Es kann als Nachricht angesehen werden, nachdem zwei Nachrichten zusammengefasst wurden: $ \ mu_ {x_5 \ bis f_4} $ und $ \ mu_ {x_6 \ bis f_4} $ . Und $ \ mu_ {x_6 \ bis f_4} $ ist im Wesentlichen $ \ mu_ {f_6 \ bis x_6} $ , die aus einigen anderen Nachrichten berechnet werden kann.

Dies ist die rekursive Struktur von Nachrichten. Nachrichten können durch Nachrichten definiert werden.

Rekursion ist a Gut, eine zum besseren Verständnis, eine zur einfacheren Implementierung von Computerprogrammen.

Schlussfolgerung

Die Vorteile von Faktoren sind:

1. Faktor, der fasst Zuflussnachrichten zusammen und gibt die Abflussnachricht aus, aktiviert Nachrichten, die für die Berechnung von marginalen
2. Faktoren wesentlich sind, und ermöglicht die rekursive Struktur der Berechnung von Nachrichten, wodurch das Weiterleiten von Nachrichten oder der Prozess der Weitergabe von Überzeugungen erleichtert wird verstehen und möglicherweise einfacher zu implementieren.

Kommentare

• Um ehrlich zu sein, denke ich, dass dies eher eine Zusammenfassung dessen ist, wie Inferenz in Faktorgraphen mittels Nachrichtenübermittlung durchzuführen, als eine Antwort auf die tatsächliche Frage.

Ein Bayesianisches Netzwerk ist per Definition eine Sammlung von Zufallsvariablen $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ und ein Graph $ G $, so dass die Wahrscheinlichkeitsfunktion $ P (X_1, …, X_n) $ als bedingte Wahrscheinlichkeiten in einer durch $ G $ bestimmten Weise berücksichtigt wird. Siehe http://en.wikipedia.org/wiki/Factor_graph .

Am wichtigsten ist, dass die Faktoren im Bayesian Network die Form $ haben P (X_i | X_ {j_1}, .., X_ {j_n}) $.

Ein Faktordiagramm ist, obwohl es allgemeiner ist, insofern dasselbe, als es eine grafische Methode zum Speichern von Informationen ist über die Faktorisierung von $ P (X_1, …, X_n) $ oder einer anderen Funktion.

Der Unterschied besteht darin, dass bei der Konvertierung eines Bayesschen Netzwerks in ein Faktordiagramm die Faktoren im Faktordiagramm gruppiert werden. Beispielsweise kann ein Faktor im Faktorgraphen $ P (X_i | X_ {j_1}, .., X_ {j_n}) P (X_ {j_n}) P (X_ {j_1}) = P (X_i | X_ {) sein j_2}, .., X_ {j_ {n-1}}) $. Das ursprüngliche Bayessche Netzwerk hat dies als drei Faktoren gespeichert, aber das Faktordiagramm speichert es nur als einen Faktor. Im Allgemeinen zeichnet der Faktorgraph eines Bayesschen Netzwerks weniger Faktorisierungen auf als das ursprüngliche Bayessche Netzwerk.

A. Der Faktorgraph ist nur eine weitere Darstellung eines Bayesschen Modells. Wenn Sie einen exakten Inferenzalgorithmus in einem bestimmten Bayesschen Netzwerk und einen anderen exakten Inferenzalgorithmus im entsprechenden Faktordiagramm hätten, wären die beiden Ergebnisse gleich. Faktorgraphen sind zufällig eine nützliche Darstellung zum Ableiten effizienter (genauer und ungefährer) Inferenzalgorithmen durch Ausnutzen der bedingten Unabhängigkeit zwischen Variablen in das Modell, wodurch der Fluch der Dimensionalität gemindert wird.

Um eine Analogie zu geben: Die Fourier-Transformation enthält genau die gleichen Informationen wie die Zeitdarstellung eines Signals, einige Aufgaben sind jedoch einfacher im Frequenzbereich durchgeführt, und einige sind im Zeitbereich leichter zu erreichen. Im gleichen Sinne ist ein Faktorgraph nur eine Neuformulierung derselben Information (des Wahrscheinlichkeitsmodells), was hilfreich ist, um clevere Algorithmen abzuleiten, aber nicht wirklich “ “ irgendetwas.

Um genauer zu sein, nehmen Sie an, dass Sie daran interessiert sind, den marginalen $ abzuleiten p (x_i) $ einer bestimmten Menge in einem Modell, die die Integration über alle anderen Variablen erfordert:

$$ 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 $$

In einem Hoch -dimensionales Modell, Dies ist eine Integration über einen hochdimensionalen Raum, der sehr schwer zu berechnen ist. (Dieses Marginalisierungs- / Integrationsproblem macht Inferenz in hohen Dimensionen schwierig / unlösbar. Ein Ansatz besteht darin, clevere Wege zu finden, um dieses Integral effizient zu bewerten, was Markov-Kette Monte ist Carlo (MCMC) -Methoden tun dies. Es ist bekannt, dass diese unter notorisch langen Rechenzeiten leiden.)

Ohne auf zu viele Details einzugehen, codiert ein Faktorgraph die Tatsache, dass viele dieser Variablen bedingt unabhängig voneinander sind . Dies ermöglicht das Ersetzen der obigen hochdimensionalen Integration durch eine Reihe von Integrationsproblemen mit viel geringerer Dimension , nämlich die Berechnungen von die verschiedenen Nachrichten. Durch Ausnutzen der Struktur des Problems auf diese Weise wird eine Folgerung möglich. Dies ist der Hauptvorteil der Formulierung von Inferenz in Form von Faktordiagrammen.