Hvorfor bruke faktorgraf for Bayesian inferens?

Jeg vil prøve å svare mitt eget spørsmål.

Melding

En veldig viktig forestilling om faktorgraf er melding , som kan forstås som A, forteller noe om B, hvis meldingen sendes fra A til B.

I den sannsynlige modellkonteksten, melding fra faktor $ f $ til variabel $ x $ kan betegnes som $ \ mu_ {f \ to x} $ , som kan forstås som $ f $ vet noe (sannsynlighetsfordeling i dette tilfellet) og forteller det til $ x $ .

Faktor oppsummerer meldinger

I " faktor " kontekst, for å kjenne sannsynlighetsfordelingen til noen variabler, må man ha alle meldingene klare fra n oppmuntrende faktorer, og oppsummer deretter alle meldingene for å utlede fordelingen.

For eksempel, i den følgende grafen, er kantene, $ x_i $ , variabler og noder, $ f_i $ , er faktorer forbundet med kanter.

For å vite $ P (x_4) $ , må vi vite $ \ mu_ {f_3 \ to x_4} $ og $ \ mu_ {f_4 \ to x_4} $ og oppsummere dem sammen.

Rekursiv struktur av meldinger

Så hvordan kjenner du til disse to meldingene? For eksempel $ \ mu_ {f_4 \ to x_4} $ . Det kan sees på som meldingen etter å ha oppsummert to meldinger, $ \ mu_ {x_5 \ to f_4} $ og $ \ mu_ {x_6 \ til f_4} $ . Og $ \ mu_ {x_6 \ to f_4} $ er egentlig $ \ mu_ {f_6 \ to x_6} $ , som kan beregnes fra noen andre meldinger.

Dette er rekursiv struktur for meldinger, meldinger kan defineres av meldinger .

Rekursjon er en god ting, en for bedre forståelse, en for enklere implementering av dataprogram.

Konklusjon

Fordelen med faktorer er:

1. Faktor, som oppsummerer innstrømningsmeldinger og sender ut utstrømningsmeldingen, aktiverer meldinger som er avgjørende for databehandling marginal
2. Faktorer gjør det mulig å rekursiv struktur for å beregne meldinger, noe som gjør det lettere å overføre eller troutbredelse prosessen forstå, og muligens lettere å implementere.

Kommentarer

• For å være ærlig, føler jeg at dette er mer en oppsummering av hvordan å utføre slutning i faktorgrafer ved å sende meldinger, enn et svar på det faktiske spørsmål.

Et Bayesian Network er per definisjon en samling av tilfeldige variabler $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ og en graf $ G $ slik at sannsynligheten fungerer $ P (X_1, …, X_n) $ faktorer som betingede sannsynligheter på en måte bestemt av $ G $. Se http://en.wikipedia.org/wiki/Factor_graph .

Viktigst av alt er faktorene i Bayesian Network av formen $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

En faktorgraf, selv om den er mer generell, er den samme fordi det er en grafisk måte å beholde informasjon på om faktoriseringen av $ P (X_1, …, X_n) $ eller annen funksjon.

Forskjellen er at når et Bayesiansk nettverk blir konvertert til en faktorgraf, er faktorene i faktorgrafen gruppert. For eksempel kan en faktor i faktorgrafen være $ 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}} $. Det opprinnelige Bayesian-nettverket lagret dette som tre faktorer, men faktografen lagrer det bare som en faktor. Generelt holder faktorgrafikken til et Bayesiansk nettverk spor av færre faktoriseringer enn det opprinnelige Bayesiske nettverket gjorde.

A faktorgraf er bare nok en representasjon av en Bayesian-modell. Hvis du hadde en nøyaktig algoritme for inferens i et bestemt Bayesian-nettverk, og en annen nøyaktig algoritme for inferens i den tilsvarende faktorgrafen, ville de to resultatene være de samme. Faktorgrafer er tilfeldigvis en nyttig representasjon for å utlede effektive (nøyaktige og omtrentlige) inferensalgoritmer ved å utnytte betinget uavhengighet mellom variabler i modellen, og derved redusere forbannelsen av dimensjonalitet .

For å gi en analogi: Fourier-transformasjonen inneholder nøyaktig samme informasjon som tidsrepresentasjonen til et signal, men noen oppgaver er enklere oppnådd i frekvensdomenet, og noen blir lettere oppnådd i tidsdomenet. På samme måte er en faktorgraf bare en omformulering av den samme informasjonen (den sannsynlige modellen), som er nyttig for å utlede smarte algoritmer, men ikke " legger til " hva som helst.

For å være mer spesifikk, antar du at du er interessert i å utlede marginalen $ p (x_i) $ av en mengde i en modell, som krever integrering over alle andre variabler:

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

I en høy -dimensjonal modell, dette er en integrasjon over et høyt dimensjonalt rom, som er veldig vanskelig å beregne. (Dette marginaliserings- / integreringsproblemet er det som gjør slutning i høye dimensjoner vanskelig / uoppnåelig. En tilnærming er å finne smarte måter å evaluere denne integralen effektivt, det er det Markov-kjeden Monte Carlo (MCMC) metoder gjør. Det er kjent at de lider av notorisk lange beregningstider.)

Uten å gå i for mange detaljer, koder en faktorgraf for at mange av disse variablene er uavhengig uavhengig av hverandre. . Dette muliggjør erstatning av den ovennevnte, høydimensjonale integrasjonen med en serie integrasjonsproblemer med mye lavere dimensjon , nemlig beregningene av de forskjellige meldingene. Ved å utnytte strukturen av problemet på denne måten blir inferens mulig. Dette er kjernefordelen med å formulere slutning når det gjelder faktorgrafer.