Po co używać wykresu czynnikowego do wnioskowania bayesowskiego?

Spróbuję odpowiedzieć moje własne pytanie.

Wiadomość

Bardzo ważnym pojęciem wykresu czynnikowego jest wiadomość , co można rozumieć jako A, mówi coś o B, jeśli wiadomość jest przekazywana z A do B.

W kontekście modelu probabilistycznego, wiadomość z czynnika $ f $ do zmiennej $ x $ można oznaczyć jako $ \ mu_ {f \ to x} $ , co można rozumieć jako $ f $ coś wie (w tym przypadku rozkład prawdopodobieństwa) i przekazuje to do $ x $ .

Współczynnik podsumowuje wiadomości

W " współczynniku " kontekst, aby poznać rozkład prawdopodobieństwa jakiejś zmiennej, trzeba mieć przygotowane wszystkie komunikaty z jej n sąsiednich czynników, a następnie podsumuj wszystkie komunikaty w celu ustalenia rozkładu.

Na przykład na poniższym wykresie krawędzie $ x_i $ są zmienne i węzły, $ f_i $ , to czynniki połączone krawędziami.

Aby wiedzieć $ P (x_4) $ , musimy znać $ \ mu_ {f_3 \ to x_4} $ i $ \ mu_ {f_4 \ to x_4} $ i podsumuj je razem.

Rekurencyjna struktura wiadomości

Więc jak poznać te dwie wiadomości? Na przykład $ \ mu_ {f_4 \ to x_4} $ . Można go zobaczyć jako wiadomość po podsumowaniu dwóch wiadomości, $ \ mu_ {x_5 \ to f_4} $ i $ \ mu_ {x_6 \ do f_4} $ . A $ \ mu_ {x_6 \ to f_4} $ to w zasadzie $ \ mu_ {f_6 \ to x_6} $ , które można obliczyć na podstawie niektórych innych wiadomości.

To jest rekurencyjna struktura wiadomości, wiadomości mogą być definiowane przez wiadomości .

Rekursja to dobra rzecz, jedna dla lepszego zrozumienia, druga dla łatwiejszej implementacji programu komputerowego.

Wniosek

Zalety czynników to:

1. Czynnik, który podsumowuje wiadomości wpływające i wyświetla komunikat wyjściowy, włącza komunikaty, które są niezbędne do obliczania marginalnych
2. Czynniki umożliwiają rekurencyjną strukturę obliczania komunikatów, ułatwiając przekazywanie wiadomości lub proces propagacji przekonań rozumieć i być może łatwiejsze do wdrożenia.

Komentarze

• Szczerze mówiąc, uważam, że jest to raczej podsumowanie tego, jak wnioskowanie na wykresach czynnikowych poprzez przekazywanie wiadomości, niż odpowiedź na rzeczywistość pytanie.

Sieć Bayesa z definicji jest zbiorem zmiennych losowych $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ oraz wykres $ G $ taki, że funkcja prawdopodobieństwa $ P (X_1, …, X_n) $ uwzględnia jako prawdopodobieństwa warunkowe w sposób określony przez $ G $. Zobacz http://en.wikipedia.org/wiki/Factor_graph .

Najważniejsze czynniki w sieci bayesowskiej mają postać $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

Wykres czynnikowy, nawet jeśli jest bardziej ogólny, jest taki sam, że jest graficznym sposobem przechowywania informacji o rozkładaniu na czynniki $ P (X_1, …, X_n) $ lub dowolnej innej funkcji.

Różnica polega na tym, że po przekształceniu sieci bayesowskiej w graf czynnikowy czynniki na wykresie czynnikowym są grupowane. Na przykład jednym czynnikiem na wykresie czynnikowym może być $ 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}}) $. Oryginalna sieć Bayesa zapisała to jako trzy czynniki, ale wykres czynnikowy przechowuje go tylko jako jeden czynnik. Ogólnie wykres czynnikowy sieci bayesowskiej śledzi mniej faktorów niż oryginalna sieć bayesowska.

A Wykres czynnikowy jest kolejną reprezentacją modelu bayesowskiego. Gdybyś miał dokładny algorytm wnioskowania w określonej sieci Bayesa i inny dokładny algorytm wnioskowania w odpowiednim grafie czynnikowym, oba wyniki byłyby takie same. Wykresy czynnikowe są po prostu użyteczną reprezentacją do wyprowadzania wydajnych (dokładnych i przybliżonych) algorytmów wnioskowania poprzez wykorzystanie warunkowej niezależności między zmiennymi w model, łagodząc w ten sposób przekleństwo wymiarowości .

Aby podać analogię: transformata Fouriera zawiera dokładnie te same informacje, co reprezentacja czasu sygnału, ale niektóre zadania są łatwiejsze dokonuje się w dziedzinie częstotliwości, a niektóre są łatwiejsze w dziedzinie czasu. W tym samym sensie wykres czynnikowy jest po prostu przeformułowaniem tych samych informacji (modelu probabilistycznego), co jest pomocne przy wyprowadzaniu sprytnych algorytmów, ale tak naprawdę nie " dodaje " cokolwiek.

Aby być bardziej szczegółowym, załóżmy, że chcesz wyprowadzić marginalne $ p (x_i) $ pewnej ilości w modelu, która wymaga integracji ze wszystkimi innymi zmiennymi:

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

W wysokim -wymiarowy model, jest to całkowanie w wielowymiarowej przestrzeni, które jest bardzo trudne do obliczenia. (Ten problem marginalizacji / integracji jest tym, co sprawia, że wnioskowanie w dużych wymiarach jest trudne / nie do rozwiązania. Jednym z podejść jest znalezienie sprytnych sposobów efektywnej oceny tej całki, co jest tym, co Markov łączy Monte Metody Carlo (MCMC) tak. Wiadomo, że cierpią one z powodu notorycznie długich czasów obliczeń.)

Bez wchodzenia w zbyt wiele szczegółów, wykres czynnikowy koduje fakt, że wiele z tych zmiennych jest warunkowo niezależnych od siebie . Umożliwia to zastąpienie powyższej, wielowymiarowej integracji serią problemów integracyjnych o znacznie mniejszym wymiarze , a mianowicie obliczeniami różne wiadomości. Wykorzystując w ten sposób strukturę problemu, wnioskowanie staje się wykonalne. Jest to podstawowa zaleta formułowania wnioskowania w postaci wykresów czynnikowych.