Luottamuksen leviämisalgoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. heinäkuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Uskomuksen leviämisalgoritmi , luottamuksen leviämisalgoritmi , myös summatuloalgoritmi , on marginalisointialgoritmi , joka käyttää kaksisuuntaista viestiä, joka välittää graafin ja jota käytetään päättelemään graafisista todennäköisyysmalleista (kuten Bayesin ja Markovin verkot ). J. Pearlin ehdotus vuonna 1982.

Ongelman selvitys

Harkitse toimintoa:

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

, missä

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

Saadaksesi todennäköisyys, sinun on normalisoitava se:

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

Seuraavat tehtävät otetaan huomioon:

Normalisointitehtävä : _

löytö

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

Syrjäytymisen tehtävä :

löytö

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

Normalisoitu syrjäytymisongelma

löytö

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

Kaikki nämä ongelmat ovat NP-täydellisiä , joten niiden pahimman tapauksen monimutkaisuus kasvaa eksponentiaalisesti. Jotkut erikoistapaukset voidaan kuitenkin ratkaista nopeammin, minkä tämä algoritmi tekee .

Kaavion rakenne

Algoritmin käyttämä graafi koostuu muuttujia vastaavista pisteistä ja funktioita vastaavista pisteistä. Funktiot on kytketty muuttujiin, joista ne riippuvat.

Esimerkki

Esimerkiksi toiminnot

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

vastaa seuraavaa kaaviota:

Viesti kulkee

Kaaviossa lähetetään kahdenlaisia viestejä: funktioista muuttujiin ja muuttujista funktioihin.

Muuttujasta funktioon : $x_{i}$ $f_{j}$

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

(tässä on joukko i:n vieressä olevia pisteitä)

ne(i)

Funktiosta muuttujaksi : $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})

Tässä tapauksessa tyhjän tuotteen oletetaan olevan yhtä suuri kuin yksi. Näistä kaavoista voidaan nähdä, että jos kärjessä on vain yksi naapuripiste, niin sen (vertex) sanoma voidaan laskea tietämättä saapuvia viestejä.

Algoritmi

On olemassa kaksi lähestymistapaa, riippuen tuloksena olevan kaavion luonteesta.

Lähestymistapa 1

Oletetaan, että graafi on puu . Lehdistä alkaen ohitamme vähitellen kaikki kärjet ja laskemme viestejä (tässä tapauksessa pätee vakioviestinvälityssääntö: viesti voidaan lähettää vain, jos se voidaan rakentaa kokonaan).

Sitten algoritmi päättyy useissa vaiheissa, jotka ovat yhtä suuria kuin kaavion halkaisija .

Lähestymistapa 2

Jos kuvaaja ei ole puu , voit aloittaa siten, että kaikki muuttujat lähettävät viestin 1, ja sitten muokata sitä, kun funktioiden viestit saavuttavat ne.

Tällainen algoritmi toimii yleensä väärin ja tekee paljon turhaa työtä, mutta käytännössä siitä on silti hyötyä.

Marginaalien laskeminen

Kun viestien jakelu on valmis, marginaalit lasketaan seuraavan kaavan mukaan:

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

Lennossa normalisointi

Jos haluat laskea vain normalisoidut marginaalit ( todelliset todennäköisyydet ), voit normalisoida viestit muuttujista funktioiksi kussakin vaiheessa:

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

missä on valittu niin ${\displaystyle \alpha _{ij))$

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

Algoritmin matemaattinen perustelu

Matemaattisesta näkökulmasta algoritmi hajottaa uudelleen alkuperäisen jaottelun:

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

työhön:

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

jossa vastaa funktiosolmuja ja muuttujasolmuja. ${\displaystyle \phi _{j))$ $\psi _{i}$

Aluksi ennen viestiä ja $\phi _{j}(X_{j})=f_{j}(X_{j})$ $\psi _{i}(x_{i})=1$

Joka kerta kun funktiosta tulee viesti muuttujalle ja lasketaan uudelleen: ${\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})}}

On selvää, että kokonaistuote ei muutu tästä, ja viestien lähetyksen lopussa siitä tulee marginaalinen . $\psi _{i}$ $p^{*}(x_{i})$

Linkit

S. Nikolenko. Todennäköisyyspohjainen oppimiskurssi