Trust Propagation Algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 juli 2022; kontroller kräver 3 redigeringar .

Trosutbredningsalgoritm , förtroendeutbredningsalgoritm , även summaproduktalgoritm , är en marginaliseringsalgoritm som använder dubbelriktade meddelanden som förmedlas på en graf , som används för att sluta sig till grafiska probabilistiska modeller (som Bayesian- och Markov-nätverk ). Föreslog av J. Pearl 1982.

Förklaring av problemet

Tänk på en funktion:

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

, var

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

För att få sannolikheten måste du normalisera den:

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

Följande uppgifter övervägs:

Normaliseringsuppgift : _

hitta

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

Marginaliseringens uppgift :

hitta

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

Normaliserat marginaliseringsproblem

hitta

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

Alla dessa problem är NP-kompletta , så deras komplexitet i värsta fall ökar exponentiellt. Vissa specialfall kan dock lösas snabbare, vilket är vad den här algoritmen gör .

Grafstruktur

Grafen som används av algoritmen består av hörn som motsvarar variabler och hörn som motsvarar funktioner. Funktioner är kopplade till variabler som de är beroende av.

Exempel

Till exempel 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})

motsvarar följande graf:

Meddelande passerar

Två typer av meddelanden skickas i grafen: från funktioner till variabler och från variabler till funktioner.

Från variabel till funktion : $x_{i}$ $f_{j}$

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

(här är uppsättningen av hörn intill i)

ne(i)

Från funktion till variabel : $f_{j}$ $x_{i}$

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

I detta fall antas den tomma produkten vara lika med en. Från dessa formler kan man se att om en vertex bara har en angränsande punkt, så kan dess (vertex) meddelande beräknas utan att känna till de inkommande meddelandena.

Algoritm

Det finns två tillvägagångssätt, beroende på karaktären av den resulterande grafen.

Tillvägagångssätt 1

Låt oss anta att grafen är ett träd . Med utgångspunkt från löven kommer vi gradvis att kringgå alla hörn och beräkna meddelanden (i det här fallet gäller standardregeln för att skicka meddelanden: ett meddelande kan bara överföras om det kan konstrueras helt).

Sedan, i ett antal steg lika med diametern på grafen , kommer algoritmen att avslutas.

Tillvägagångssätt 2

Om grafen inte är ett träd kan du börja med att låta alla variabler skicka meddelande 1 och sedan ändra det när meddelanden från funktioner når dem.

En sådan algoritm fungerar i allmänhet felaktigt och gör en hel del onödigt arbete, men den är ändå användbar i praktiken.

Beräkning av marginaler

När distributionen av meddelanden är klar, beräknas marginalerna enligt följande 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})

Normalisering i farten

Om du bara behöver beräkna normaliserade marginaler ( verkliga sannolikheter ), kan du normalisera meddelanden från variabler till funktioner i varje steg:

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

var är valda så att ${\displaystyle \alpha _{ij))$

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

Matematisk motivering av algoritmen

Ur en matematisk synvinkel sönderdelar algoritmen om den ursprungliga nedbrytningen:

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

in i arbetet:

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

där motsvarar funktionsnoder och variabla noder. ${\displaystyle \phi _{j))$ $\psi _{i}$

Inledningsvis, innan meddelanden och $\phi _{j}(X_{j})=f_{j}(X_{j})$ $\psi _{i}(x_{i})=1$

Varje gång ett meddelande kommer från funktionen till variabeln och räknas om: ${\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 är uppenbart att den totala produkten inte förändras från detta, och i slutet av överföringen av meddelanden kommer den att bli marginell . $\psi _{i}$ $p^{*}(x_{i})$

Länkar

S. Nikolenko. Probabilistiskt lärande