Varför använda faktordiagram för Bayesian-inferens?

Jag ska försöka svara min egen fråga.

Meddelande

En mycket viktig uppfattning om faktordiagram är meddelande , vilket kan förstås som A berättar något om B, om meddelandet skickas från A till B.

I den probabilistiska modellkontexten, meddelande från faktor $ f $ till variabel $ x $ kan betecknas som $ \ mu_ {f \ till x} $ , vilket kan förstås som $ f $ vet något (sannolikhetsfördelning i det här fallet) och säger att $ x $ .

Faktor sammanfattar meddelanden

I " -faktorn " context, för att känna till sannolikhetsfördelningen för någon variabel, måste man ha alla meddelanden redo från dess n kompletterande faktorer och sammanfatta sedan alla meddelanden för att härleda fördelningen.

Till exempel, i följande graf är kanterna, $ x_i $ , variabler och noder, $ f_i $ , är faktorer som är förbundna med kanter.

För att veta $ P (x_4) $ måste vi känna till $ \ mu_ {f_3 \ till x_4} $ och $ \ mu_ {f_4 \ till x_4} $ och sammanfatta dem tillsammans.

Rekursiv struktur för meddelanden

Hur känner du då till dessa två meddelanden? Till exempel $ \ mu_ {f_4 \ till x_4} $ . Det kan ses som meddelandet efter att ha sammanfattat två meddelanden, $ \ mu_ {x_5 \ to f_4} $ och $ \ mu_ {x_6 \ till f_4} $ . Och $ \ mu_ {x_6 \ to f_4} $ är i huvudsak $ \ mu_ {f_6 \ till x_6} $ , som kan beräknas från vissa andra meddelanden.

Detta är rekursiv struktur för meddelanden, meddelanden kan definieras av meddelanden .

Rekursion är en bra, en för bättre förståelse, en för enklare implementering av datorprogram.

Slutsats

Fördelen med faktorer är:

1. Faktor, vilken sammanfattar inflödesmeddelanden och skickar utflödesmeddelandet, möjliggör meddelanden som är väsentliga för beräkning av marginal
2. Faktorer möjliggör rekursiv struktur för beräkning av meddelanden, vilket gör meddelandets överföring eller trosförökning processen enklare förstå, och möjligen lättare att implementera.

Kommentarer

• För att vara ärlig känner jag att det här är mer en sammanfattning av hur att utföra slutsatser i faktorgrafer med hjälp av meddelandeöverföring än ett svar på det faktiska fråga.

Ett Bayesian-nätverk är per definition en samling slumpmässiga variabler $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ och en graf $ G $ så att sannolikheten fungerar $ P (X_1, …, X_n) $ faktorer som villkorliga sannolikheter på ett sätt som bestäms av $ G $. Se http://en.wikipedia.org/wiki/Factor_graph .

Viktigast av allt är faktorerna i Bayesian Network av formen $ P (X_i | X_ {j_1}, .., X_ {j_n}) $.

En faktordiagram, även om den är mer allmän, är densamma genom att det är ett grafiskt sätt att behålla information om faktoriseringen av $ P (X_1, …, X_n) $ eller någon annan funktion.

Skillnaden är att när ett Bayesiskt nätverk omvandlas till ett faktordiagram grupperas faktorerna i faktordiagrammet. En faktor i faktordiagrammet kan till exempel vara $ 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 ursprungliga Bayesiska nätverket lagrade detta som tre faktorer men faktordiagrammet lagrar det bara som en faktor. I allmänhet håller faktordiagrammet för ett Bayesianskt nätverk spår av färre faktoriseringar än det ursprungliga Bayesiska nätverket gjorde.

A faktordiagram är bara ännu en representation av en Bayesian-modell. Om du hade en exakt algoritm för inferens i ett visst Bayesian-nätverk och en annan exakt algoritm för inferens i motsvarande faktordiagram, skulle de två resultaten vara desamma. Faktorgrafer är bara en användbar representation för att få fram effektiva (exakta och ungefärliga) inferensalgoritmer genom att utnyttja villkorligt oberoende mellan variabler modellen och därigenom mildra förbannelsen av dimensionalitet .

För att ge en analogi: Fouriertransformen innehåller exakt samma information som tidsrepresentationen för en signal, men vissa uppgifter är lättare uppnås i frekvensdomänen, och vissa är lättare att uppnå i tidsdomänen. I samma bemärkelse är ett faktordiagram bara en omformulering av samma information (den probabilistiska modellen), vilket är användbart för att härleda smarta algoritmer men inte ”gentligen " lägger till " vad som helst.

För att vara mer specifik, antag att du är intresserad av att härleda marginalen $ p (x_i) $ av en viss mängd i en modell, som kräver integrering över alla andra 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ög -dimensionell modell, detta är en integration över ett högdimensionellt utrymme, vilket är mycket svårt att beräkna. (Detta marginaliserings- / integrationsproblem är det som gör slutsatser i höga dimensioner hårda / svåråtkomliga. Ett tillvägagångssätt är att hitta smarta sätt att utvärdera denna integral effektivt, vilket är vad Markov-kedjan Monte Carlo (MCMC) metoder gör. De är kända för att drabbas av notoriskt långa beräkningstider.)

Utan att gå in i alltför många detaljer kodar ett faktordiagram för att många av dessa variabler är villkorligt oberoende av varandra. . Detta möjliggör ersättning av ovanstående, högdimensionell integration med en serie integrationsproblem med mycket lägre dimension , nämligen beräkningarna av de olika meddelandena. Genom att utnyttja problemets struktur på detta sätt blir slutledning möjlig. Detta är den största fördelen med att formulera slutsatser i termer av faktorgrafer.