Proč používat faktorový graf pro Bayesiánský závěr?

Pokusím se odpovědět moje vlastní otázka.

Zpráva

Velmi důležitým pojmem faktorového grafu je message , které lze chápat jako A, říká něco o B, pokud je zpráva předána z A do B.

V kontextu pravděpodobnostního modelu zpráva z faktoru $ f $ do proměnné $ x $ lze označit jako $ \ mu_ {f \ to x} $ , které lze chápat jako $ f $ něco ví (rozdělení pravděpodobnosti v tomto případě) a říká to $ x $ .

Faktor shrnuje zprávy

V " faktoru " kontext, abychom poznali rozdělení pravděpodobnosti nějaké proměnné, musíme mít všechny zprávy připravené z jejího n faktory sousedství a poté shrnout všechny zprávy k odvození distribuce.

Například v následujícím grafu jsou hrany $ x_i $ proměnné a uzly, $ f_i $ , jsou faktory spojené hranami.

Chcete-li znát $ P (x_4) $ , potřebujeme znát $ \ mu_ {f_3 \ to x_4} $ a $ \ mu_ {f_4 \ to x_4} $ a shrnout je dohromady.

Rekurzivní struktura zpráv

Jak tedy tyto dvě zprávy znát? Například $ \ mu_ {f_4 \ to x_4} $ . Lze ji zobrazit jako zprávu po shrnutí dvou zpráv, $ \ mu_ {x_5 \ to f_4} $ a $ \ mu_ {x_6 \ to f_4} $ . A $ \ mu_ {x_6 \ to f_4} $ je v podstatě $ \ mu_ {f_6 \ to x_6} $ , kterou lze vypočítat z některých dalších zpráv.

Toto je rekurzivní struktura zpráv, zprávy lze definovat zprávami .

Rekurze je dobrá věc, jedna pro lepší pochopení, druhá pro snazší implementaci počítačového programu.

Závěr

Výhodou faktorů je:

1. Faktor, který shrnuje příchozí zprávy a vydává odchozí zprávy, umožňuje zprávy, které jsou nezbytné pro výpočet okrajových
2. faktorů, které umožňují rekurzivní strukturu výpočtu zpráv, což usnadňuje předávání zpráv nebo šíření přesvědčení pochopit a možná snadněji implementovat.

Komentáře

• Abych byl upřímný, mám pocit, že jde spíše o shrnutí toho, jak provádět odvození v faktorových grafech pomocí předávání zpráv, než odpověď na skutečné otázka.

Bayesovská síť je podle definice kolekce náhodných proměnných $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ a graf $ G $ takový, že pravděpodobnostní funkce $ P (X_1, …, X_n) $ působí jako podmíněné pravděpodobnosti způsobem určeným $ G $. Viz http://en.wikipedia.org/wiki/Factor_graph .

Nejdůležitější faktory v Bayesovské síti jsou ve tvaru $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

Faktorový graf, i když je obecnější, je stejný v tom, že jde o grafický způsob uchovávání informací o faktorizaci $ P (X_1, …, X_n) $ nebo jakékoli jiné funkce.

Rozdíl je v tom, že když se Bayesovská síť převede na faktorový graf, faktory v faktorovém grafu se seskupí. Například jedním faktorem v grafu faktorů může být $ 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}}) $. Původní bayesiánská síť to ukládala jako tři faktory, ale faktorový graf ji ukládá pouze jako jeden faktor. Obecně platí, že faktorový graf Bayesovské sítě sleduje méně faktorizací než původní Bayesiánská síť.

A faktorový graf je jen dalším znázorněním Bayesovského modelu. Pokud byste měli přesný algoritmus pro odvození v konkrétní Bayesovské síti a jiný přesný algoritmus pro odvození v příslušném grafu faktoru, byly by dva výsledky stejné. Faktorové grafy jsou jen užitečným vyjádřením pro odvození efektivních (přesných a přibližných) odvozovacích algoritmů využitím podmíněné nezávislosti mezi proměnnými v model, čímž se zmírňuje kletba dimenzionality .

Uvedeme analogii: Fourierova transformace obsahuje přesně stejné informace jako časová reprezentace signálu, ale některé úkoly jsou jednodušší dosáhnout ve frekvenční doméně a některé se snadněji dosáhnou v časové doméně. Ve stejném smyslu je faktorový graf pouze přeformulováním stejné informace (pravděpodobnostní model), což je užitečné pro odvození chytrých algoritmů, ale skutečně " nepřidá " cokoli.

Chcete-li být konkrétnější, předpokládejte, že máte zájem o odvození okrajové $ p (x_i) $ určitého množství v modelu, což vyžaduje integraci přes všechny ostatní proměnné:

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

Na vysoké -dimenzionální model, jedná se o integraci ve vysokodimenzionálním prostoru, kterou je velmi těžké vypočítat. (Tento problém marginalizace / integrace je tím, co činí závěry ve vysokých dimenzích obtížnými / neřešitelnými. Jedním z přístupů je najít chytré způsoby, jak efektivně vyhodnotit tento integrál, což je to, co Markovův řetězec Monte Metody Carlo (MCMC) ano. Je známo, že trpí notoricky dlouhými výpočtovými časy.)

Aniž bychom zacházeli do příliš mnoha podrobností, faktorový graf kóduje skutečnost, že mnoho z těchto proměnných je podmíněně nezávislých na sobě navzájem. . To umožňuje nahradit výše uvedenou vysoko-dimenzionální integraci řadou integračních problémů mnohem nižší dimenze , konkrétně výpočty různé zprávy. Využitím struktury problému tímto způsobem se odvození stane proveditelným. To je hlavní výhoda formulování závěru ve smyslu faktorových grafů.