Faktordiagramm - Factor graph

Ein Faktorgraph ist ein zweiteiliger Graph, der die Faktorisierung einer Funktion darstellt. In der Wahrscheinlichkeitstheorie und ihren Anwendungen werden Faktorgraphen verwendet, um die Faktorisierung einer Wahrscheinlichkeitsverteilungsfunktion darzustellen, was effiziente Berechnungen ermöglicht, z. B. die Berechnung von Randverteilungen durch den Summenprodukt-Algorithmus . Eine der wichtigsten Erfolgsgeschichten von Faktorgraphen und dem Summenproduktalgorithmus ist die Dekodierung von kapazitätsnähenden fehlerkorrigierenden Codes wie LDPC- und Turbo-Codes .

Faktorgraphen verallgemeinern Beschränkungsgraphen . Ein Faktor, dessen Wert entweder 0 oder 1 ist, wird als Einschränkung bezeichnet. Ein Beschränkungsgraph ist ein Faktorgraph, bei dem alle Faktoren Beschränkungen sind. Der Max-Product-Algorithmus für Faktorgraphen kann als eine Verallgemeinerung des Arc-Consistency-Algorithmus für die Constraint-Verarbeitung angesehen werden.

Definition

Ein Faktorgraph ist ein zweiteiliger Graph, der die Faktorisierung einer Funktion darstellt. Gegeben eine Faktorisierung einer Funktion , ${\displaystyle g(X_{1},X_{2},\dots,X_{n})}$

${\displaystyle g(X_{1},X_{2},\dots,X_{n})=\prod_{j=1}^{m}f_{j}(S_{j}),}$

wobei der entsprechende Faktorgraph aus variablen Scheitelpunkten , Faktorscheitelpunkten und Kanten besteht . Die Kanten hängen wie folgt von der Faktorisierung ab: es gibt eine ungerichtete Kante zwischen Faktorscheitelpunkt und variablem Scheitelpunkt if . Die Funktion wird stillschweigend als reellwertig angenommen : . ${\displaystyle S_{j}\subseteq \{X_{1},X_{2},\dots,X_{n}\}}$${\displaystyle G=(X,F,E)}$${\displaystyle X=\{X_{1},X_{2},\dots,X_{n}\}}$ ${\displaystyle F=\{f_{1},f_{2},\dots,f_{m}\}}$${\displaystyle E}$${\displaystyle f_{j}}$${\displaystyle X_{k}}$${\displaystyle X_{k}\in S_{j}}$${\displaystyle g(X_{1},X_{2},\dots,X_{n})\in\mathbb{R}}$

Faktorgraphen können mit Message-Passing-Algorithmen kombiniert werden, um bestimmte Merkmale der Funktion , wie zB die Randverteilungen , effizient zu berechnen . ${\displaystyle g(X_{1},X_{2},\dots,X_{n})}$

Beispiele

Ein Beispiel für ein Faktordiagramm

Betrachten Sie eine Funktion, die wie folgt faktorisiert:

${\displaystyle g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3} (X_{1},X_{2})f_{4}(X_{2},X_{3})}$,

mit einem entsprechenden Faktordiagramm auf der rechten Seite. Beachten Sie, dass der Faktorgraph einen Zyklus hat . Wenn wir zu einem einzelnen Faktor verschmelzen , ist der resultierende Faktorgraph ein Baum . Dies ist ein wichtiger Unterschied, da Nachrichtenübermittlungsalgorithmen normalerweise für Bäume exakt sind, aber nur annähernd für Graphen mit Zyklen. ${\displaystyle f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})}$

Nachrichtenweitergabe von Faktordiagrammen

Ein beliebter Message-Passing-Algorithmus für Faktorgraphen ist der Summenprodukt-Algorithmus , der alle Randbereiche der einzelnen Variablen der Funktion effizient berechnet. Insbesondere ist der Rand der Variablen definiert als ${\displaystyle X_{k}}$

${\displaystyle g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots,X_{n})}$

wobei die Notation bedeutet, dass die Summation alle Variablen außer . Die Nachrichten des Summenprodukt-Algorithmus werden konzeptionell in den Ecken berechnet und entlang der Kanten weitergegeben. Eine Nachricht von oder an einen variablen Scheitelpunkt ist immer eine Funktion dieser bestimmten Variablen. Wenn beispielsweise eine Variable binär ist, können die Nachrichten über die Kanten, die auf den entsprechenden Scheitelpunkt fallen, als Vektoren der Länge 2 dargestellt werden: der erste Eintrag ist die in 0 bewertete Nachricht, der zweite Eintrag ist die in 1 bewertete Nachricht Variable gehört zum Bereich der reellen Zahlen , Nachrichten können beliebige Funktionen sein, und deren Darstellung erfordert besondere Sorgfalt. ${\displaystyle X_{\bar {k}}}$ ${\displaystyle X_{k}}$

In der Praxis wird der Summenproduktalgorithmus für statistische Inferenz verwendet , wobei es sich um eine gemeinsame Verteilung oder eine gemeinsame Likelihood-Funktion handelt , und die Faktorisierung hängt von den bedingten Unabhängigkeiten zwischen den Variablen ab. ${\displaystyle g(X_{1},X_{2},\dots,X_{n})}$

Das Hammersley-Clifford-Theorem zeigt, dass andere Wahrscheinlichkeitsmodelle wie Bayes-Netzwerke und Markov-Netzwerke als Faktorgraphen dargestellt werden können; die letztere Darstellung wird häufig verwendet, wenn eine Inferenz über solche Netzwerke unter Verwendung von Glaubensausbreitung durchgeführt wird . Andererseits sind Bayessche Netze natürlicher für generative Modelle geeignet , da sie die Kausalitäten des Modells direkt darstellen können.

Siehe auch

• Glaubensverbreitung
• Bayes'sche Inferenz
• Bayessche Programmierung
• Bedingte Wahrscheinlichkeit
• Markov-Netzwerk
• Bayes-Netzwerk
• Hammersley-Clifford-Theorem

Externe Links

• Loeliger, Hans-Andrea (Januar 2004), "An Introduction to Factor Graphs]" (PDF) , IEEE Signal Processing Magazine , 21 (1): 28–41, Bibcode : 2004ISPM...21...28L , doi : 10.1109/MSP.2004.1267047
• dimple ein Open-Source-Tool zum Erstellen und Lösen von Faktorgraphen in MATLAB.
• Loeliger, Hans-Andrea (2008), Eine Einführung in Faktorgraphen (PDF)

Verweise

• Clifford (1990), "Markov-Zufallsfelder in der Statistik", in Grimmett, GR; Welsh, DJA (Hrsg.), Disorder in Physical Systems, JM Hammersley Festschrift (Nachschrift) , Oxford University Press , S. 19–32, ISBN 9780198532156
• Frey, Brendan J. (2003), "Extending Factor Graphs, um Directed and Undirected Graphical Models zu vereinheitlichen " , in Jain, Nitin (Hrsg.), UAI'03, Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence , Morgan Kaufmann , S. 257–264, arXiv : 1212.2486 , ISBN 0127056645
• Kschischang, Frank R. ; Frey, Brendan J.; Loeliger, Hans-Andrea (2001), "Factor Graphs and the Sum-Product Algorithm", IEEE Transactions on Information Theory , 47 (2): 498–519, CiteSeerX  10.1.1.54.1570 , doi : 10.1109/18.910572 .
• Wymeersch, Henk (2007), Iteratives Empfängerdesign , Cambridge University Press, ISBN 978-0-521-87315-4