Bizalomterjesztési algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. július 21-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A hiedelemterjesztési algoritmus , a bizalomterjesztési algoritmus , vagy az összeg-szorzat algoritmus is egy marginalizációs algoritmus , amely kétirányú üzenetet továbbít egy gráfon , és grafikus valószínűségi modellekre (például Bayes- és Markov-hálózatokra ) való következtetésre használjuk. J. Pearl javasolta 1982-ben.

A probléma leírása

Tekintsünk egy függvényt:

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

, ahol

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

A valószínűség kiszámításához normalizálnia kell:

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

A következő feladatokat veszik figyelembe:

Normalizálási feladat :

megtalálja

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

A marginalizáció feladata :

megtalálja

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

Normalizált marginalizációs probléma

megtalálja

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

Mindezek a problémák NP-teljesek , így a legrosszabb eset bonyolultsága exponenciálisan növekszik. Néhány speciális eset azonban gyorsabban megoldható, amit ez az algoritmus tesz .

Grafikon szerkezete

Az algoritmus által használt gráf változóknak megfelelő csúcsokból és függvényeknek megfelelő csúcsokból áll. A függvények olyan változókhoz kapcsolódnak, amelyektől függenek.

Példa

Például függvények

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

a következő grafikonnak felel meg:

Üzenet átadása

A grafikon kétféle üzenetet küld: a függvényektől a változókig és a változóktól a függvényekig.

Változótól függvényig : $x_{i}$ $f_{j}$

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

(itt van az i-vel szomszédos csúcsok halmaza)

ne(i)

A függvénytől a változóig : $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})

Ebben az esetben az üres szorzatot eggyel egyenlőnek tételezzük fel. Ezekből a képletekből látható, hogy ha egy csúcsnak csak egy szomszédos pontja van, akkor a bejövő üzenetek ismerete nélkül kiszámítható a (csúcs) üzenete.

Algoritmus

Az eredményül kapott gráf természetétől függően két megközelítés létezik.

1. megközelítés

Tegyük fel, hogy a gráf egy fa . A levelekből kiindulva fokozatosan megkerüljük az összes csúcsot és kiszámoljuk az üzeneteket (ebben az esetben a szabványos üzenetátadási szabály érvényes: csak akkor lehet üzenetet továbbítani, ha teljesen megszerkeszthető).

Ezután a gráf átmérőjével megegyező számú lépésben az algoritmus véget ér.

2. megközelítés

Ha a grafikon nem egy fa , akkor kezdheti azzal, hogy minden változó elküldi az 1-es üzenetet, majd módosíthatja azt, amikor a függvények üzenetei megérkeznek hozzájuk.

Egy ilyen algoritmus általában helytelenül működik, és sok felesleges munkát végez, de a gyakorlatban még mindig hasznos.

Az árrés kiszámítása

Amikor az üzenetek elosztása befejeződött, a margók kiszámítása a következő képlet szerint történik:

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

Menet közbeni normalizálás

Ha csak normalizált határértékeket ( valós valószínűségeket ) kell kiszámítania, akkor minden lépésben normalizálhatja az üzeneteket a változókról a függvényekre:

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

hol vannak kiválasztva úgy $\alpha _{ij}$

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

Az algoritmus matematikai indoklása

Matematikai szempontból az algoritmus újrabontja az eredeti bontást:

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

a munkába:

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

ahol a függvénycsomópontoknak és a változó csomópontoknak felel meg. ${\displaystyle \phi _{j))$ $\psi _{i}$

Kezdetben az üzenetküldés előtt és $\phi _{j}(X_{j})=f_{j}(X_{j})$ $\psi _{i}(x_{i})=1$

Minden alkalommal, amikor üzenet érkezik a függvénytől a változóhoz, és újraszámolják: ${\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})}}

Nyilvánvaló, hogy a teljes szorzat ettől nem változik, és az üzenetküldés végén marginálissá válik . $\psi _{i}$ $p^{*}(x_{i})$

Linkek

S. Nikolenko. Valószínűségi tanulási tanfolyam