Wykres czynnikowy

Nie należy mylić z rozkładem na czynniki Graph .

Wykres czynnikowy to dwudzielny wykres przedstawiający rozkład funkcji na czynniki. W teorii prawdopodobieństwa i jej zastosowaniach wykresy czynnikowe są używane do przedstawiania faktoryzacji funkcji rozkładu prawdopodobieństwa, umożliwiając wydajne obliczenia, takie jak obliczanie rozkładów krańcowych za pomocą algorytmu sumy iloczynu . Jednym z ważnych sukcesów grafów czynnikowych i algorytmu sumarycznego jest dekodowanie kodów korygujących błędy zbliżających się do wydajności , takich jak LDPC i kody turbo .

Wykresy czynnikowe uogólniają wykresy ograniczeń . Czynnik, którego wartość wynosi 0 lub 1, nazywany jest ograniczeniem. Graf ograniczeń to wykres czynnikowy, w którym wszystkie czynniki są ograniczeniami. Algorytm maksymalnego iloczynu dla wykresów czynnikowych można postrzegać jako uogólnienie algorytmu spójności łuku do przetwarzania ograniczeń.

Definicja

Wykres czynnikowy to dwudzielny wykres przedstawiający rozkład funkcji na czynniki. Biorąc pod uwagę rozkład funkcji na czynniki, ${\ Displaystyle g (X_ {1}, X_ {2}, \ kropki, X_ {n})$ }

${\ Displaystyle g (X_ {1}, X_ {2}, \ kropki, X_ {n}) = \prod _{j=1}^{m}f_{j}(S_{j}),}$

gdzie ${\ Displaystyle S_ {j} \ subseteq \ {X_ {1}, X_ {2}, \ kropki, X_ {n} \}} ,$ odpowiadające wykres czynnikowy ${\ Displaystyle G = (X, F, E)}$ się ze zmiennych wierzchołków ${\ Displaystyle X = \ {X_ {1}, X_ {2}, \ kropki, X_ {n} \}}$ , czynniki wierzchołków ${\ Displaystyle F = \ {f_ {1}, f_ { 2}, \ kropki, f_ {m} \}}$ i krawędzie ${\ displaystyle E}$ . Krawędzie zależą od rozkładu na czynniki w następujący sposób: istnieje nieskierowana krawędź między wierzchołkiem czynnika $\ Displaystyle$ zmiennej $X_ {k}}$ jeśli ${\ Displaystyle X_ {k}\w S_{j}}$ . Zakłada się milcząco, że funkcja ma wartości rzeczywiste : ${\ Displaystyle g (X_ {1}, X_ {2}, \ kropki, X_ {n}) \ w \mathbb {R}}$ .

Wykresy czynnikowe można łączyć z algorytmami przekazywania komunikatów, aby wydajnie obliczać pewne cechy funkcji sol $\ Displaystyle g (X_ {1}, X_ {2}, \ kropki, X_ { n})}$ , takie jak rozkłady krańcowe .

Przykłady

Przykładowy wykres czynnikowy

Rozważmy funkcję, która rozkłada się na czynniki w następujący sposób:

${\ 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})}$ ,

z odpowiednim wykresem czynników pokazanym po prawej stronie. Zauważ, że wykres czynnikowy ma cykl . Jeśli połączymy ${\ Displaystyle f_ {2} (X_ {1}, X_ {2}) f_ {3} (X_ {1}, X_ {2})}$ na jeden czynnik, wynikowy wykres czynników będzie drzewem . Jest to ważne rozróżnienie, ponieważ algorytmy przekazywania komunikatów są zwykle dokładne dla drzew, ale tylko przybliżone dla grafów z cyklami.

Przekazywanie wiadomości na wykresach czynnikowych

Popularnym algorytmem przekazywania komunikatów na wykresach czynnikowych jest algorytm sumy iloczynu , który skutecznie oblicza wszystkie brzegi poszczególnych zmiennych funkcji. W szczególności margines zmiennej jest zdefiniowany jako ${\ displaystyle X_ {k}}$

${\ Displaystyle g_ {k} (X_ {k}) = \ suma _ {X_ {\ bar {k}} }g(X_{1},X_{2},\kropki ,X_{n})}$

$.$ notacja $,$ że ​​sumowanie obejmuje wyjątkiem Komunikaty algorytmu sumy iloczynów są koncepcyjnie obliczane w wierzchołkach i przekazywane wzdłuż krawędzi. Wiadomość z lub do wierzchołka zmiennej jest zawsze funkcją tej konkretnej zmiennej. Na przykład, gdy zmienna jest binarna, komunikaty na krawędziach incydentnych z odpowiednim wierzchołkiem mogą być reprezentowane jako wektory o długości 2: pierwszy wpis to komunikat oceniany na 0, drugi wpis to komunikat oceniany na 1. Kiedy zmienna należy do ciała liczb rzeczywistych , komunikaty mogą być dowolnymi funkcjami i należy zachować szczególną ostrożność przy ich reprezentacji.

W praktyce algorytm sumy iloczynów jest używany do wnioskowania statystycznego , przy czym ${\ Displaystyle g (X_ {1}, X_ {2}, \ kropki, X_ {n} )}$ jest łącznym rozkładem lub wspólną funkcją wiarygodności , a faktoryzacja zależy od warunkowych zależności między zmiennymi.

Twierdzenie Hammersleya – Clifforda pokazuje, że inne modele probabilistyczne, takie jak sieci Bayesa i sieci Markowa, można przedstawić jako wykresy czynnikowe; ta druga reprezentacja jest często używana podczas przeprowadzania wnioskowania na podstawie takich sieci przy użyciu propagacji przekonań . Z drugiej strony sieci bayesowskie bardziej naturalnie nadają się do modeli generatywnych , ponieważ mogą bezpośrednio reprezentować przyczynowość modelu.

Zobacz też

• Rozpowszechnianie wiary
• Wnioskowanie bayesowskie
• Programowanie bayesowskie
• Warunkowe prawdopodobieństwo
• sieć Markowa
• Sieć bayesowska
• Twierdzenie Hammersleya-Clifforda

Linki zewnętrzne

•   Loeliger, Hans-Andrea (styczeń 2004), „Wprowadzenie do wykresów czynnikowych]” (PDF) , IEEE Signal Processing Magazine , 21 (1): 28–41, Bibcode : 2004ISPM… 21… 28L , doi : 10.1109/MSP.2004.1267047 , S2CID 7722934
• dimple narzędzie typu open source do budowania i rozwiązywania wykresów czynnikowych w MATLAB.
• Loeliger, Hans-Andrea (2008), Wprowadzenie do wykresów czynnikowych (PDF)

•   Clifford (1990), „Losowe pola Markowa w statystyce”, w: Grimmett, GR; Welsh, DJA (red.), Disorder in Physical Systems, JM Hammersley Festschrift (postscriptum) , Oxford University Press , s. 19–32, ISBN 9780198532156
•   Frey, Brendan J. (2003), „Rozszerzanie wykresów czynników tak, aby ujednolicić modele graficzne skierowane i niekierowane” , w: Jain, Nitin (red.), 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), „Wykresy czynnikowe i algorytm sumy iloczynów”, IEEE Transactions on Information Theory , 47 (2): 498–519, CiteSeerX 10.1.1.54.1570 , doi : 10.1109/18.910572 .
•   Wymeersch, Henk (2007), Iteracyjny projekt odbiornika , Cambridge University Press, ISBN 978-0-521-87315-4