Waarom factorgrafiek gebruiken voor Bayesiaanse inferentie?

Ik zal proberen te beantwoorden mijn eigen vraag.

Bericht

Een zeer belangrijk begrip van factor-grafiek is bericht , wat kan worden begrepen als A iets over B vertelt, als het bericht wordt doorgegeven van A naar B.

In de probabilistische modelcontext, bericht van factor $ f $ naar variabele $ x $ kan worden aangeduid als $ \ mu_ {f \ to x} $ , wat kan worden begrepen als $ f $ iets weet (kansverdeling in dit geval) en vertelt het aan $ x $ .

Factor vat berichten samen

In de ” factor ” context, om de kansverdeling van een variabele te kennen, moet men alle berichten gereed hebben van zijn n naburige factoren en vat dan alle berichten samen om de distributie af te leiden.

In de volgende grafiek zijn de randen $ x_i $ bijvoorbeeld variabelen en knooppunten, $ f_i $ , zijn factoren verbonden door randen.

Om $ P (x_4) $ te kennen, hebben we de $ \ mu_ {f_3 nodig \ to x_4} $ en $ \ mu_ {f_4 \ to x_4} $ en vat ze samen samen.

Recursieve structuur van berichten

Hoe ken je deze twee berichten dan? Bijvoorbeeld $ \ mu_ {f_4 \ tot x_4} $ . Het kan worden gezien als het bericht na een samenvatting van twee berichten, $ \ mu_ {x_5 \ to f_4} $ en $ \ mu_ {x_6 \ tot f_4} $ . En $ \ mu_ {x_6 \ to f_4} $ is in wezen $ \ mu_ {f_6 \ to x_6} $ , die kan worden berekend op basis van enkele andere berichten.

Dit is de recursieve structuur van berichten, berichten kunnen worden gedefinieerd door berichten .

Recursie is een een goede zaak, een voor een beter begrip, een voor een eenvoudiger implementatie van het computerprogramma.

Conclusie

Het voordeel van factoren is:

1. Factor, die vat instroomberichten samen en voert het uitstroombericht uit, maakt berichten mogelijk die essentieel zijn voor het berekenen van marginale
2. Factoren maken de recursieve structuur van het berekenen van berichten mogelijk, waardoor het doorgeven van berichten of het geloofsverspreiding proces gemakkelijker wordt begrijpen en mogelijk gemakkelijker te implementeren.

Opmerkingen

• Om eerlijk te zijn, vind ik dat dit meer een samenvatting is van hoe om gevolgtrekking uit te voeren in factor grafieken door middel van het doorgeven van berichten, dan een antwoord op de werkelijke vraag.

Een Bayesiaans netwerk is per definitie een verzameling willekeurige variabelen $ \ {X_n : P \ rightarrow \ mathbb {R} \} $ en een grafiek $ G $ zodanig dat de waarschijnlijkheidsfunctie $ P (X_1, …, X_n) $ factoren als voorwaardelijke kansen op een manier bepaald door $ G $. Zie http://en.wikipedia.org/wiki/Factor_graph .

Het belangrijkste is dat de factoren in het Bayesiaanse netwerk de vorm $ hebben P (X_i | X_ {j_1}, .., X_ {j_n}) $.

Een factorgrafiek, ook al is deze algemener, is hetzelfde in die zin dat het een grafische manier is om informatie te bewaren over de factorisatie van $ P (X_1, …, X_n) $ of een andere functie.

Het verschil is dat wanneer een Bayesiaans netwerk wordt geconverteerd naar een factorgrafiek, de factoren in de factorgrafiek worden gegroepeerd. Een factor in de factorgrafiek kan bijvoorbeeld $ 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}}) $. Het oorspronkelijke Bayesiaanse netwerk heeft dit als drie factoren opgeslagen, maar in de factorgrafiek wordt het slechts als één factor opgeslagen. Over het algemeen houdt de factorgrafiek van een Bayesiaans netwerk minder factorisaties bij dan het oorspronkelijke Bayesiaanse netwerk.

A Factorgrafiek is gewoon de zoveelste weergave van een Bayesiaans model. Als u een exact algoritme had voor inferentie in een bepaald Bayesiaans netwerk, en een ander exact algoritme voor inferentie in de corresponderende factor-grafiek, zouden de twee resultaten hetzelfde zijn. Factorgrafieken zijn toevallig een nuttige weergave voor het afleiden van efficiënte (exacte en geschatte) inferentie-algoritmen door gebruik te maken van voorwaardelijke onafhankelijkheid tussen variabelen in het model, waardoor de vloek van dimensionaliteit wordt verzacht.

Om een analogie te geven: de Fourier-transformatie bevat exact dezelfde informatie als de tijdsweergave van een signaal, maar sommige taken zijn eenvoudiger bereikt in het frequentiedomein, en sommige zijn gemakkelijker te bereiken in het tijdsdomein. In dezelfde zin is een factorgrafiek slechts een herformulering van dezelfde informatie (het probabilistische model), wat handig is voor het afleiden van slimme algoritmen, maar ” voegt ” alles.

Om specifieker te zijn, neem aan dat u geïnteresseerd bent in het afleiden van de marginale $ p (x_i) $ van een hoeveelheid in een model, die integratie over alle andere variabelen vereist:

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

In een hoge -dimensionaal model, dit is een integratie in een hoog-dimensionale ruimte, die zeer moeilijk te berekenen is. (Dit marginalisatie- / integratieprobleem maakt gevolgtrekking in hoge dimensies moeilijk / onhandelbaar. Een benadering is om slimme manieren te vinden om deze integraal efficiënt te evalueren, wat Markov-keten Monte Carlo (MCMC) -methoden doen dat. Het is bekend dat die te lijden hebben onder notoir lange rekentijden.)

Zonder al te veel in details te treden, codeert een factor-grafiek het feit dat veel van deze variabelen voorwaardelijk onafhankelijk van elkaar zijn . Hierdoor is het mogelijk om de bovenstaande, hoog-dimensionale integratie te vervangen door een reeks integratieproblemen van veel kleinere afmetingen , namelijk de berekeningen van de verschillende berichten. Door op deze manier gebruik te maken van de structuur van het probleem, wordt gevolgtrekking haalbaar. Dit is het belangrijkste voordeel van het formuleren van gevolgtrekkingen in termen van factorgrafieken.