Hvorfor bruge faktorgraf til Bayesian-slutning?

Jeg vil prøve at svare mit eget spørgsmål.

Besked

En meget vigtig forestilling om faktorgraf er besked , som kan forstås som A, fortæller noget om B, hvis meddelelsen sendes fra A til B.

I den sandsynlige modelkontekst meddelelse fra faktor $ f $ til variabel $ x $ kan betegnes som $ \ mu_ {f \ til x} $ , som kan forstås som $ f $ ved noget (sandsynlighedsfordeling i dette tilfælde) og fortæller det til $ x $ .

Faktor opsummerer meddelelser

I " faktor " kontekst, for at kende sandsynlighedsfordelingen af en eller anden variabel, skal man have alle beskeder klar fra dens n afgrænsende faktorer, og derefter opsummerer alle meddelelserne for at udlede fordelingen.

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

For at vide $ P (x_4) $ skal vi kende $ \ mu_ {f_3 \ til x_4} $ og $ \ mu_ {f_4 \ til x_4} $ og sammenfatte dem.

Rekursiv struktur af meddelelser

Hvordan kender man så disse to meddelelser? For eksempel $ \ mu_ {f_4 \ to x_4} $ . Det kan ses som meddelelsen efter at have opsummeret to meddelelser, $ \ mu_ {x_5 \ to f_4} $ og $ \ mu_ {x_6 \ til f_4} $ . Og $ \ mu_ {x_6 \ to f_4} $ er i det væsentlige $ \ mu_ {f_6 \ til x_6} $ , som kan beregnes ud fra nogle andre beskeder.

Dette er den rekursive struktur af meddelelser, beskeder kan defineres af beskeder .

Rekursion er en god ting, en for bedre forståelse, en for lettere implementering af computerprogram.

Konklusion

Fordelen ved faktorer er:

1. Faktor, som opsummerer tilstrømningsmeddelelser og udsender udstrømningsmeddelelsen, aktiverer meddelelser, der er essentielle for computermarginal
2. Faktorer muliggør den rekursive struktur til beregning af meddelelser, hvilket gør meddelelsen videregående eller trosformidling processen lettere at forstå og muligvis lettere at implementere.

Kommentarer

• For at være ærlig føler jeg, at dette mere er et resumé af, hvordan at udføre slutning i faktorgrafer ved hjælp af meddelelsesoverførsel end et svar på det faktiske spørgsmål.

Et Bayesisk netværk er pr. definition en samling af tilfældige variabler $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ og en graf $ G $ således, at sandsynligheden fungerer $ P (X_1, …, X_n) $ faktorer som betingede sandsynligheder på en måde bestemt af $ G $. Se http://en.wikipedia.org/wiki/Factor_graph .

Vigtigst af alt er faktorerne i det Bayesiske netværk af formen $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

En faktorgraf, selvom den er mere generel, er den samme, da det er en grafisk måde at opbevare information på om faktorisering af $ P (X_1, …, X_n) $ eller enhver anden funktion.

Forskellen er, at når et Bayesisk netværk konverteres til en faktorgraf, er faktorerne i faktorgrafen grupperet. 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 oprindelige Bayesiske netværk lagrede dette som tre faktorer, men faktorgrafen lagrer det kun som en faktor. Generelt holder faktorgrafen for et Bayesisk netværk spor af færre faktoriseringer end det oprindelige Bayesiske netværk gjorde.

A faktor graf er bare endnu en repræsentation af en Bayesian model. Hvis du havde en nøjagtig algoritme for inferens i et bestemt Bayesian-netværk og en anden nøjagtig algoritme for inferens i den tilsvarende faktorgraf, ville de to resultater være de samme. Faktorgrafer er tilfældigvis en nyttig repræsentation til at udlede effektive (nøjagtige og omtrentlige) inferensalgoritmer ved at udnytte betinget uafhængighed mellem variabler i modellen og derved mildne forbandelsen af dimensionalitet .

For at give en analogi: Fourier-transformen indeholder nøjagtig den samme information som tidsrepræsentationen af et signal, men alligevel er nogle opgaver lettere udføres i frekvensdomænet, og nogle opnås lettere i tidsdomænet. I samme forstand er en faktorgraf kun en omformulering af den samme information (den sandsynlige model), hvilket er nyttigt til at udlede smarte algoritmer, men ikke virkelig " tilføj " noget.

For at være mere specifik, antag at du er interesseret i at udlede marginalen $ p (x_i) $ af en vis mængde i en model, der kræver integration 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øj -dimensional model, dette er en integration over et højdimensionelt rum, som er meget svært at beregne. (Dette marginaliserings- / integrationsproblem er, hvad der gør slutning i høje dimensioner hård / uigennemtrængelig. En tilgang er at finde kloge måder til at evaluere denne integral effektivt, hvilket er hvad Markov kæder Monte Carlo (MCMC) metoder gør. Det vides, at de lider under notorisk lange beregningstider.)

Uden at gå i for mange detaljer koder en faktorgraf for, at mange af disse variabler er betinget uafhængige af hinanden . Dette muliggør erstatning af ovenstående, højdimensionel integration med en serie af integrationsproblemer med meget lavere dimension , nemlig beregningerne af de forskellige meddelelser. Ved at udnytte problemets struktur på denne måde bliver slutning mulig. Dette er den centrale fordel ved at formulere slutning i form af faktorgrafer.