Variační předávání zpráv - Variational message passing

Variační předávání zpráv (VMP) je přibližný závěr technika pro spojitou nebo diskrétní hodnotu Bayesovské sítě, s konjugát-exponenciální rodiče, vyvinutý Johnem Winnem. VMP byl vyvinut jako prostředek k zobecnění přibližného variační metody používané takovými technikami jako Latentní Dirichletova alokace a funguje tak, že aktualizuje přibližnou distribuci v každém uzlu prostřednictvím zpráv v uzlu Markovská deka.

Pravděpodobnost dolní hranice

Vzhledem k nějaké sadě skrytých proměnných ${ displaystyle H}$ a pozorované proměnné ${ displaystyle V}$, cílem přibližné inference je snížit mez pravděpodobnosti, že je v konfiguraci grafický model ${ displaystyle V}$. Přes nějaké rozdělení pravděpodobnosti ${ displaystyle Q}$ (bude definováno později),

${ displaystyle ln P (V) = součet _ {H} Q (H) ln { frac {P (H, V)} {P (H | V)}} = součet _ {H} Q (H) { Bigg [} ln { frac {P (H, V)} {Q (H)}} - ln { frac {P (H | V)} {Q (H)}} { Bigg]}}$.

Pokud tedy definujeme naši spodní hranici

${ displaystyle L (Q) = součet _ {H} Q (H) ln { frac {P (H, V)} {Q (H)}}}$,

pak je pravděpodobnost jednoduše tato vázaná plus relativní entropie mezi ${ displaystyle P}$ a ${ displaystyle Q}$. Protože relativní entropie je nezáporná, funkce ${ displaystyle L}$ definovaný výše je skutečně dolní mez logaritmické pravděpodobnosti našeho pozorování ${ displaystyle V}$. Distribuce ${ displaystyle Q}$ bude mít jednodušší charakter než ${ displaystyle P}$ protože marginalizace skončila ${ displaystyle P}$ je neřešitelný pro všechny kromě těch nejjednodušších grafické modely. VMP používá zejména faktorizovanou distribuci ${ displaystyle Q}$:

${ displaystyle Q (H) = prod _ {i} Q_ {i} (H_ {i}),}$

kde ${ displaystyle H_ {i}}$ je disjunktní součástí grafického modelu.

Určení pravidla aktualizace

Odhad pravděpodobnosti musí být co největší; protože je to dolní mez, přibližování ${ displaystyle log P}$ zlepšuje aproximaci pravděpodobnosti protokolu. Nahrazením ve faktorizované verzi ${ displaystyle Q}$, ${ displaystyle L (Q)}$, parametrizováno přes skryté uzly ${ displaystyle H_ {i}}$ jak je uvedeno výše, je prostě negativní relativní entropie mezi ${ displaystyle Q_ {j}}$ a ${ displaystyle Q_ {j} ^ {*}}$ plus další termíny nezávislé na ${ displaystyle Q_ {j}}$ -li ${ displaystyle Q_ {j} ^ {*}}$ je definován jako

${ displaystyle Q_ {j} ^ {*} (H_ {j}) = { frac {1} {Z}} e ^ { mathbb {E} _ {- j} { ln P (H, V ) }}}$,

kde ${ displaystyle mathbb {E} _ {- j} { ln P (H, V) }}$ je očekávání ve všech distribucích ${ displaystyle Q_ {i}}$ až na ${ displaystyle Q_ {j}}$. Pokud tedy nastavíme ${ displaystyle Q_ {j}}$ být ${ displaystyle Q_ {j} ^ {*}}$, svázaný ${ displaystyle L}$ je maximalizován.

Zprávy ve variabilním předávání zpráv

Rodiče posílají svým dětem očekávání jejich dostatečná statistika zatímco děti posílají svým rodičům své přirozený parametr, což také vyžaduje, aby byly zprávy odesílány od spolucestujících uzlu.

Vztah k exponenciálním rodinám

Protože všechny uzly ve VMP pocházejí exponenciální rodiny a všichni rodiče uzlů jsou sdružené jejich dětským uzlům, očekávání dostatečná statistika lze vypočítat z normalizační faktor.

Algoritmus VMP

Algoritmus začíná výpočtem očekávané hodnoty dostatečné statistiky pro tento vektor. Potom, dokud pravděpodobnost konverguje na stabilní hodnotu (to se obvykle dosahuje nastavením malé prahové hodnoty a spuštěním algoritmu, dokud se nezvýší o méně než tuto prahovou hodnotu), proveďte v každém uzlu následující:

1. Získejte všechny zprávy od rodičů
2. Získat všechny zprávy od dětí (to může vyžadovat, aby děti dostaly zprávy od spolu rodičů)
3. Vypočítejte očekávanou hodnotu uzlů dostatečné statistiky

Omezení

Protože každé dítě musí být sdružené se svým rodičem, omezuje to typy distribucí, které lze v modelu použít. Například rodiče a Gaussovo rozdělení musí být Gaussovo rozdělení (odpovídá Znamenat ) a a gama distribuce (odpovídá přesnosti nebo jeden přes ${ displaystyle sigma}$ v běžnějších parametrizacích). Diskrétní proměnné mohou mít Dirichlet rodiče a jed a exponenciální uzly musí mít gama rodiče. Pokud však lze data modelovat tímto způsobem, VMP nabízí obecný rámec pro poskytování závěrů.

Reference

• Winn, J.M .; Bishop, C. (2005). „Variační předávání zpráv“ (PDF). Journal of Machine Learning Research. 6: 661–694.
• Beal, M. J. (2003). Variační algoritmy pro přibližnou Bayesovu inference (PDF) (PhD). Gatsby Computational Neuroscience Unit, University College London. Archivovány od originál (PDF) dne 2005-04-28. Citováno 2007-02-15.

externí odkazy

• Infer.NET: odvozovací rámec, který zahrnuje implementaci VMP s příklady.
• důlek: otevřený odvozovací systém podporující VMP.
• An starší implementace VMP s příklady použití.