Tillidsudbredelsesalgoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. juli 2022; checks kræver 3 redigeringer .

Trosudbredelsesalgoritme , tillidsudbredelsesalgoritme , også sum-produktalgoritme , er en marginaliseringsalgoritme , der bruger tovejsmeddelelser, der videresender en graf , der bruges til at konkludere om grafiske probabilistiske modeller (såsom Bayesianske og Markov-netværk ). Foreslået af J. Pearl i 1982.

Udtalelse af problemet

Overvej en funktion:

p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})

, hvor

{\displaystyle X_{j}=\{x_{i}\}_{i=1}^{n))

For at få sandsynligheden skal du normalisere den:

p(X)={\frac {1}{Z}}\prod _{j=1}^{m}f_{j}(X_{j}),Z=\sum _{X}\ prod _{j=1}^{m}f_{j}(X_{j})

Følgende opgaver overvejes:

Normaliseringsopgave : _

finde

Z=\sum _{X}\prod _{j=1}^{m}f_{j}(X_{j})

Marginaliseringens opgave :

finde

p_{i}^{*}(x_{i})=\sum _{k\neq i}p^{*}(X)

Normaliseret marginaliseringsproblem

finde

p_{i}(x_{i})=\sum _{k\neq i}p(X)

Alle disse problemer er NP-komplette , så deres worst case kompleksitet stiger eksponentielt. Nogle specielle tilfælde kan dog løses hurtigere, hvilket er hvad denne algoritme gør .

Grafstruktur

Grafen , som algoritmen bruger, består af hjørner svarende til variable og knudepunkter svarende til funktioner. Funktioner er forbundet med variabler, som de afhænger af.

Eksempel

For eksempel funktioner

p^{*}(X)=f_{1}(x_{1})f_{2}(x_{2})f_{3}(x_{3})f_{4}(x_{1 },x_{2})f_{5}(x_{2},x_{3})

svarer til følgende graf:

Besked passerer

To typer beskeder sendes i grafen: fra funktioner til variable og fra variable til funktioner.

Fra variabel til funktion : $x_{i}$ $f_{j}$

q_{i\to j}(x_{i})=\prod _{k\in ne(i)\setminus j}r_{k\to i}(x_{i})

(her er det sæt af hjørner, der støder op til i)

ne(i)

Fra funktion til variabel : $f_{j}$ $x_{i}$

r_{j\to i}(x_{i})=\sum _{X_{i}\setminus x_{i}}(f_{j}(X_{j})\prod _{k\in ne(i)\setminus j}q_{k\to j}(x_{k})

I dette tilfælde antages det tomme produkt at være lig med én. Ud fra disse formler kan det ses, at hvis et toppunkt kun har ét nabopunkt, så kan dets (vertex) besked beregnes uden at kende de indkommende beskeder.

Algoritme

Der er to tilgange, afhængigt af karakteren af den resulterende graf.

Fremgangsmåde 1

Lad os antage, at grafen er et træ . Startende fra bladene vil vi gradvist omgå alle hjørnerne og beregne meddelelser (i dette tilfælde gælder standardreglen for meddelelsesoverførsel: en meddelelse kan kun transmitteres, hvis den kan konstrueres fuldstændigt).

Derefter, i et antal trin svarende til diameteren af grafen , vil algoritmen afsluttes.

Fremgangsmåde 2

Hvis grafen ikke er et træ , så kan du starte med at få alle variable til at sende besked 1, og så ændre den når beskeder fra funktioner når dem.

Sådan en algoritme fungerer generelt forkert og udfører en masse unødvendigt arbejde, men den er stadig nyttig i praksis.

Beregning af marginer

Når distributionen af beskeder er afsluttet, beregnes marginerne efter følgende formel:

p_{i}^{*}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})

Z=\sum _{i}p_{i}^{*}(x_{i}),p(x_{i})={\frac {1}{Z}}p_{i}^{ *}(x_{i})

On-the-fly normalisering

Hvis du kun skal beregne normaliserede marginaler ( reelle sandsynligheder ), så kan du normalisere beskeder fra variable til funktioner på hvert trin:

q_{i\to j}(x_{i})=\alpha _{ij}\prod _{k\in ne(i)\setminus j}r_{k\to i}(x_{i} )

hvor er valgt så at ${\displaystyle \alpha _{ij))$

\sum _{i}q_{i\to j}(x_{i})=1

Matematisk begrundelse af algoritmen

Fra en matematisk synsvinkel gennedbryder algoritmen den oprindelige dekomponering:

p^{*}(X)=\prod _{j=1}^{m}f_{j}(X_{j})

ind i arbejdet:

p^{*}(X)=\prod _{j=1}^{m}\phi _{j}(X_{j})\prod _{i=1}^{m}\psi _{i}(x_{i})

hvor svarer til funktionsknuder, og til variable knudepunkter. ${\displaystyle \phi _{j))$ $\psi _{i}$

I første omgang, før beskeder og $\phi _{j}(X_{j})=f_{j}(X_{j})$ $\psi _{i}(x_{i})=1$

Hver gang en besked kommer fra funktionen til variablen og genberegnes: ${\displaystyle r_{j\to i))$ $\phi$ $\psi$

\psi _{i}(x_{i})=\prod _{j\in ne(i)}r_{j\to i}(x_{i})

\phi _{j}(X_{i})={\frac {f_{j}(X_{j})}{\prod _{i\in ne(j)}r_{j\to i }(x_{i})}}

Det er indlysende, at det samlede produkt ikke ændrer sig fra dette, og ved slutningen af transmissionen af meddelelser vil det blive marginalt . $\psi _{i}$ $p^{*}(x_{i})$

Links

S. Nikolenko. Probabilistisk læringskursus