Uskomusten leviäminen

Luonto	Algoritmi
Keksijä	Judea Pearl
Keksintöpäivä	1982
Kaava	${\ displaystyle p_ {X_ {i}} (x_ {i}) = \ summa _ {\ mathbf {x} 'x' _ {i} \ neq x_ {i}} p (\ mathbf {x} ')}$

Leviäminen uskomus (Belief eteneminen tai BP Englanti), joka tunnetaan myös sanoman lähetys summa-tuote , on algoritmi viesti kulkee tehdä päätelmiä siitä graafinen malleja , kuten Bayes-verkkojen ja Markovin satunnainen aloilla . Se laskee kunkin "havaitsemattoman" solmun marginaalijakauman , joka on ehdollistettu havaituille solmuille. Uskomusten levittämistä käytetään yleisesti tekoälyssä ja informaatioteoriassa, ja sen on empiirisesti osoitettu onnistuneen monissa sovelluksissa, mukaan lukien LDPC- koodien tai turbokoodien dekoodaus , vapaan energian lähentäminen ja tyydyttävyysmallit .

Tämän algoritmin ehdotti ensimmäisen kerran Judea Pearl , vuonna 1982. Algoritmi muotoiltiin alun perin puista ja laajennettiin sitten suuntautuneisiin puihin. Sittemmin se on osoittautunut hyödylliseksi likimääräisenä algoritmina yleisemmissä kaavioissa.

Jos X = { X i } on joukko erillisiä satunnaisia muuttujia, joilla on yhteinen todennäköisyyden jakauma p , reunajakauma yksittäisen elementin X i on yksinkertaisesti summa p yli kaikki muut muuttujat:

{\ displaystyle p_ {X_ {i}} (x_ {i}) = \ summa _ {\ mathbf {x} ': x' _ {i} = x_ {i}} p (\ mathbf {x} '). }

Tämä laskelma muuttuu kuitenkin nopeasti kohtuuttomaksi: jos binäärisiä muuttujia on 100, lasketaan yhteen 2 99 ≈ 6,338 × 10 29 mahdolliset arvot. Puun rakennetta hyödyntämällä vakaumusten leviäminen mahdollistaa marginaalien laskemisen paljon tehokkaammin.

Summatuotealgoritmin kuvaus

Erilaisia kaaviotyyppejä (erityisesti Bayesin verkot ja Markov-kentät ) varten on olemassa erilaisia variantteja vakaumuksen etenemisalgoritmista . Kuvailemme tässä muunnosta, joka toimii tekijäkaaviossa. Faktorointikaavio on kahdenvälinen kaavio, joka sisältää muuttujia V ja tekijöitä F vastaavat solmut , linkkien kanssa muuttujien ja tekijöiden välillä, joissa ne esiintyvät. Voimme sitten kirjoittaa yhteisen massafunktion:

{\ displaystyle p (\ mathbf {x}) = \ prod _ {a \ F} f_ {a} (\ mathbf {x} _ {a})}

jossa x on vektori naapurisolmuilta tekijän solmun . Mikä tahansa Bayesin verkon tai Markovin kenttä voidaan esittää tekijäkaaviona.

Algoritmi toimii "välittämällä" reaaliarvoisia toimintoja, joita kutsutaan viesteiksi piilotettujen solmujen välisten linkkien varrella. Tarkemmin sanottuna, jos v on muuttuja solmu ja a on tekijä solmu, joka on kytketty kaavioon v , v : n sanat v : lle a (merkitään ): llä ja a: sta v: hen ( ) ovat reaaliarvoisia funktioita, joiden toimialue on Dom ( v ): joukko arvoja, jotka voidaan ottaa v: ään liittyvällä satunnaismuuttujalla . Nämä viestit sisältävät "vaikutteet", joita yksi muuttuja toiselle antaa. Viestit lasketaan eri tavalla riippuen siitä, onko viesti vastaanottava solmu muuttuva solmu vai tekijäsolmu. Samat merkinnät: ${\ displaystyle \ mu _ {v \ a}}$ ${\ displaystyle \ mu _ {a \ - v}}$

Viesti muuttuvasta solmusta v tekijäsolmuun a on kaikkien muiden vierekkäisten tekijäsolmujen viestien tulo (paitsi vastaanottaja; päinvastoin, voimme sanoa, että vastaanottaja lähettää vakiofunktion viestinä, joka on yhtä suuri kuin "1"):

{\ displaystyle \ forall x_ {v} \ Dom (v), \; \ mu _ {v \ a} (x_ {v}) = \ prod _ {a ^ {*} \ N (v) \ setminus \ {a \}} \ mu _ {a ^ {*} \ - v} (x_ {v}).}

jossa N ( v ) on joukko viereisen tekijä solmujen vastaan . Jos se on tyhjä, asetetaan sitten tasainen jakauma.

{\ displaystyle N (v) \ setminus \ {a \}}

{\ displaystyle \ mu _ {v \ a} (x_ {v})}

Viesti tekijäsolmusta a muuttuvaan solmuun v on tekijän tulo, joka käyttää kaikkien muiden solmujen viestejä: marginalisoimme kaikki muuttujat paitsi v : hen liittyvän muuttujan :

{\ displaystyle \ forall x_ {v} \ in Dom (v), \; \ mu _ {a \ to v} (x_ {v}) = \ summa _ {\ mathbf {x} '_ {a}: x '_ {v} = x_ {v}} f_ {a} (\ mathbf {x}' _ {a}) \ prod _ {v ^ {*} \ N (a) \ setminus \ {v \}} \ mu _ {v ^ {*} \ a} (x '_ {v ^ {*}}).}

missä N ( a ) on a: n vierekkäisten muuttujasolmujen joukko . Jos on tyhjä, koska tässä tapauksessa .

{\ displaystyle N (a) \ setminus \ {v \}}

{\ displaystyle \ mu _ {a \ - v} (x_ {v}) = f_ {a} (x_ {v})}

{\ displaystyle x_ {v} = x_ {a}}

Kuten edellisestä kaavasta käy ilmi, täydellinen marginaalisuus supistuu siten yksinkertaisempien termien summaksi kuin koko yhteisjakelussa esiintyvät. Tästä syystä sitä kutsutaan summa-tuotealgoritmiksi.

Tyypillisessä käytössä kukin viesti päivitetään iteratiivisesti naapuriviestien edellisestä arvosta. Viestien päivittäminen voidaan ajoittaa eri tavoin. Siinä tapauksessa, että kaavio on puu, optimaalinen suunnittelu mahdollistaa konvergenssin saavuttamisen kunkin viestin laskemisen jälkeen vain kerran (katso seuraava osa). Kun kaaviossa on jaksoja, tällaista optimaalista aikataulua ei ole, ja tyypillinen valinta on päivittää kaikki viestit samanaikaisesti jokaisella iteraatiolla.

Konvergenssin aikana (jos jälkimmäinen tapahtuu) estimaatti kunkin solmun marginaalisesta jakaumasta on verrannollinen vierekkäisten tekijöiden kaikkien sanomien tulokseen (vain normalisointivakio puuttuu):

{\ displaystyle p_ {X_ {v}} (x_ {v}) \ propto \ prod _ {a \ N: ssä (v)} \ mu _ {a \ to v} (x_ {v}).}

Samoin arvio yksittäiseen tekijään kuuluvien muuttujien joukon marginaalisesta jakaumasta on verrannollinen tekijän tulokseen vierekkäisten muuttujien sanomien kanssa:

{\ displaystyle p_ {X_ {a}} (\ mathbf {x} _ {a}) \ propto f_ {a} (\ mathbf {x} _ {a}) \ prod _ {v \ N (a)} \ mu _ {v \ a} (x_ {v}).}

Siinä tapauksessa, että käyräkerroin on asyklinen (eli puu tai metsä), nämä arvioidut marginaalit yhtyvät todellisiin marginaaleihin rajallisessa määrässä iteraatioita. Mikä voidaan todistaa induktiolla .

Tarkka puiden algoritmi

Siinä tapauksessa, että kaavio on puu , vakaumusten etenemisalgoritmi mahdollistaa tarkkojen marginaalien saamisen. Lisäksi suunnittelemalla viestien päivitykset oikein, se päättyy 2 vaiheeseen. Tämä optimaalinen suunnittelu voidaan kuvata seuraavasti. Aluksi kaavio on suunnattu nimeämällä solmu juureksi ; mitä tahansa muuta vain yhteen toiseen solmuun liitettyä solmua kutsutaan lehdeksi .

Ensimmäisen vaiheen aikana viestit etenevät sisäänpäin: lehdistä alkaen kukin solmu levittää sanomaa yhden linkin kautta juurelle. Puun rakenne varmistaa, että on mahdollista saada viestejä kaikista vierekkäisistä solmuista ennen oman viestin välittämistä. Tämä jatkuu, kunnes juuri on saanut viestit kaikista vierekkäisistä solmuistaan.

Toinen vaihe on lähettää viestit takaisin ulkopuolelle: juuresta alkaen viestit lähetetään vastakkaiseen suuntaan. Algoritmi on valmis, kun kaikki lehdet ovat saaneet viestinsä.

Arvioitu algoritmi yleisille kaavioille

Kummallista kyllä, vaikka se oli alun perin suunniteltu asyklisille kaavioille. On havaittu, että vakaumuksen etenemisalgoritmia voidaan käyttää mihin tahansa kuvaajaan. Algoritmia kutsutaan silloin joskus "silmukan" uskomuksen etenemiseksi, koska kaaviot sisältävät yleensä syklejä tai silmukoita. Viestien alustus ja aikataulu päivityksiä varten on muutettava hieman (verrattuna puiden tapaukseen), koska nämä kaaviot eivät välttämättä sisällä lehtiä. Sen sijaan alustetaan kaikki muuttuvan solmun viestit arvoon 1, minkä jälkeen käytetään yllä olevaa sanomäärittelyä. Kaikki viestit päivitetään jokaisella iteraatiolla (vaikka tunnettujen lehtien tai alipuiden viestit eivät enää tarvitse päivityksiä riittävän määrän iteraatioiden jälkeen). On helppo osoittaa, että puussa tämän muokkauksen tuottamat sanomat yhtyvät edellä kuvattuihin viesteihin useiden iteraatioiden jälkeen, jotka ovat yhtä suuret kuin puun halkaisija .

Tarkkoja olosuhteita, joissa "silmukan" vakaumuksen eteneminen lähentyy, ei vielä tunneta. Tiedetään, että yhden silmukan sisältävissä kaavioissa se lähentyy useimmissa tapauksissa, mutta saadut todennäköisyydet voivat olla virheellisiä. Useat ehdot ovat riittäviä (mutta eivät välttämättömiä) yhden kiinteän lähentymispisteen olemassaolon varmistamiseksi. On kaavioita, jotka eivät lähene toisiaan tai edes värähtelevät useiden tilojen välillä useiden iteraatioiden jälkeen. EXIT: n kaltaiset tekniikat voivat tarjota likimääräisen visualisoinnin algoritmin etenemisestä ja siten karkean arvion lähentymisestä.

Marginaalien laskemiseksi on muita likimääräisiä menetelmiä, mukaan lukien variaatiomenetelmät ja Monte Carlon menetelmät .

Tarkkaa marginaalien laskentamenetelmää kutsutaan yleisesti tapaukseksi risteyspuun algoritmiksi , joka on yksinkertaisesti uskomusten leviämistä kaavion muokatun version yli, joka taataan olevan puu. Perusperiaate on poistaa syklit ryhmittelemällä ne yhteen solmuun.

Analogiset algoritmit ja monimutkaisuus

Samanlaista algoritmia kutsutaan yleisesti Viterbi-algoritmiksi , se on max-tuotteen tai min-sum-algoritmin erityistapaus maksimoinnin ongelman ratkaisemiseksi tai todennäköisin. Marginaalien laskemisen sijaan tavoitteena on löytää arvot, jotka maksimoivat kokonaisfunktion (ts. Todennäköisimmät arvot todennäköisyyskehyksessä), ja se voidaan määrittää käyttämällä max arg : a: $\ mathbf {x}$

{\ displaystyle \ operaattorin nimi {*} {arg \, max} _ {\ mathbf {x}} g (\ mathbf {x}).}

Algoritmi, joka ratkaisee tämän ongelman, on melkein identtinen uskomusten etenemisen kanssa, korvaamalla summat määritelmissä maksimilla.

Mielenkiintoista on, että päättelyongelmia , kuten marginalisointia ja optimointia, on NP-vaikea ratkaista tarkoissa ja jopa likimääräisissä tapauksissa (ainakin suhteellisen virheen vuoksi ) mille tahansa kuvaajalle. Tarkemmin sanottuna yllä määritelty marginalisointiongelma on # P-täydellinen ja maksimointiongelma on NP-täydellinen .

Muistin käyttöä uskomusten levittämisellä voidaan vähentää käyttämällä saaren algoritmia (edulliseen ajanhintaan).

Yhdistä vapaaseen energiaan

Summatuotealgoritmi liittyy vapaan energian laskemiseen termodynamiikassa . Olkoon Z on partitiofunktio . Todennäköisyysjakauma

{\ displaystyle P (\ mathbf {X}) = {\ frac {1} {Z}} \ prod _ {f_ {j}} f_ {j} (x_ {j})}

(huomioi samankaltaisuus tekijäkaavion kanssa) voidaan ajatella järjestelmän sisäisen energian mittana , joka lasketaan

{\ displaystyle E (\ mathbf {X}) = \ log \ prod _ {f_ {j}} f_ {j} (x_ {j}).}

Järjestelmän vapaa energia on silloin

{\ displaystyle F = UH = \ summa _ {\ mathbf {X}} P (\ mathbf {X}) E (\ mathbf {X}) + \ summa _ {\ mathbf {X}} P (\ mathbf {X }) \ log P (\ mathbf {X}).}

Voidaan osoittaa, että summa-tuotealgoritmin konvergenssipisteet edustavat tällaisen järjestelmän vapaan energian minimitiloja. Samoin voidaan osoittaa, että iteratiivisen vakaumuksen etenemisalgoritmin kiinteä piste syklikäyrissä on myös kiinteä piste vapaan energian lähentämisestä.

Uskomusten laaja leviäminen

Vakaumuksen etenemisalgoritmit esitetään tavallisesti yhtälöiden päivityksinä tekijäkaaviossa, joka sisältää viestejä muuttuvien solmujen ja niiden viereisten tekijäsolmujen välillä ja päinvastoin . Kaavion alueiden välisten viestien huomioon ottaminen on tapa yleistää vakaumuksen etenemisalgoritmi. On useita tapoja määrittää kaavion alueet, jotka voivat vaihtaa viestejä. Yksi menetelmä käyttää Kikuchin fyysisessä kirjallisuudessa esittämiä ideoita, ja se tunnetaan nimellä Kikuchi Cluster Variation Method.

Uskomusten etenemisalgoritmien suorituskyvyn parantaminen on mahdollista myös rikkomalla vihjeiden symmetria kenttäjakaumissa (sanomat). Tämä yleistys johtaa uuden tyyppiseen algoritmiin, jota kutsutaan etenemiskyselyksi, jonka on osoitettu olevan erittäin tehokas NP-täydellisiin ongelmiin, kuten tyydyttävyyteen ja kuvaajan väritykseen .

Klusterivariaatiomenetelmät ja etenemiskartoitus ovat kaksi erilaista parannusta uskomusten levittämiseen.

Gaussin uskomusten leviäminen

Gaussin uskonlisäys (PCG) on muunnelma uskonlisäysalgoritmista, kun taustalla olevat jakaumat ovat Gaussin . Ensimmäiset tämän erityismallin analysoijat olivat Weiss ja Freeman.

PCG-algoritmi ratkaisee seuraavan marginaalisen laskutehtävän:

{\ displaystyle P (x_ {i}) = {\ frac {1} {Z}} \ int _ {j \ neq i} \ exp (-1 / 2x ^ {T} Ax + b ^ {T} x) \, dx_ {j}}

missä Z on normalisointivakio, A on symmetrinen positiivinen määritelty matriisi (kovarianssimatriisin käänteinen eli matriisin tarkkuus) ja b on muutosvektori.

Vastaavasti voidaan osoittaa, että Gaussin mallia käytettäessä marginalisaatio-ongelman ratkaisu on sama kuin tehtäväongelman takimmainen maksimi :

{\ displaystyle {\ underderset {x} {\ operaattorin nimi {argmax}}} \ P (x) = {\ frac {1} {Z}} \ exp (-1 / 2x ^ {T} Ax + b ^ {T } x).}

Tämä ongelma vastaa seuraavaa asteen yhtälön minimointiongelmaa:

{\ displaystyle {\ underderset {x} {\ operaattorin nimi {min}}} \ 1 / 2x ^ {T} Axe-b ^ {T} x.}

Se vastaa myös lineaarista yhtälöjärjestelmää

{\ displaystyle-kirves = b.}

PCG-algoritmin lähentymistä on helpompi analysoida (suhteessa yleiseen tuomioiden ohjelmoinnin tapaukseen), ja on olemassa kaksi tunnettua riittävää lähentymisehtoa. Ensimmäisen muotoilivat Weiss et ai. vuonna 2000: kun matriisin A tiedot ovat diagonaalisesti hallitsevia . Toisen lähentymisehdon muotoilivat Johnson et ai. vuonna 2006, jolloin matriisin spektrisäde tyydyttää

{\ displaystyle \ rho (I- | D ^ {- 1/2} AD ^ {- 1/2} |) <1 \,}

missä D = lävistäjä (A).

PCG-algoritmi on liittynyt lineaariseen algebraan ja on osoitettu, että PCG-algoritmia voidaan pitää iteratiivisena algoritmina lineaarisen yhtälöjärjestelmän Ax = b ratkaisemiseksi, jossa A on informaatiomatriisi ja b on muutosvektori. Empiirisesti PCG-algoritmin havaitaan lähestyvän nopeammin kuin klassiset iteratiiviset menetelmät, kuten Jacobi-menetelmä, Gauss-Seidel- menetelmä tai peräkkäinen ylirelaxointimenetelmä ja muut. Lisäksi PCG-algoritmin on osoitettu olevan immuuni ennakkolain konjugaattigradienttimenetelmän numeerisille ongelmille.

Viitteet

Judea Pearl (1982). " Reverend Bayes päättelykoneista: hajautettu hierarkkinen lähestymistapa " julkaisussa AAAI-82: Pittsburgh, PA Proceedings of the Second National Conference on Artificial Intelligence : 133–136 s., Menlo Park, Kalifornia: AAAI Press. Käytetty 28.3.2009.
Jin H.Kim (1983). " Laskennallinen malli yhdistetystä syy- ja diagnostisesta päättelystä päättelyjärjestelmissä " julkaisussa IJCAI-83: Karlsruhe, Saksa Proceedings of the kahdeksas kansainvälinen tekoälyn yhteinen konferenssi 1 : 190–193 s. Käytetty 2016-03-20.
Judea Pearl , todennäköisyysperusteinen päättely älykkäissä järjestelmissä: uskottavien päätelmien verkostot , San Francisco, Kalifornia, Morgan Kaufmann,1988, 2 nd ed. , 552 Sivumäärä ( ISBN 1-55860-479-0 , lue verkossa )
JS Yedidia , WT Freeman ja Y. , Tekoälyn tutkiminen uudella vuosituhannella , Morgan Kaufmann,tammikuu 2003, 239–236 Sivumäärä ( ISBN 1-55860-811-7 , lue verkossa ) , "Uskonleviämisen ja sen yleistämisen ymmärtäminen"
Yair Weiss , " Paikallisen todennäköisyyden etenemisen oikeellisuus silmukoita sisältävissä graafisissa malleissa ", Neural Computation , voi. 12, n o 1,2000, s. 1–41 ( DOI 10.1162 / 089976600300015880 )
J Mooij ja H Kappen , " Riittävät olosuhteet summan lähentymiselle - tuotealgoritmi ", IEEE Transactions on Information Theory , voi. 53, n ° 12,2007, s. 4422–4437 ( DOI 10.1109 / TIT.2007.909166 )
Hans-Andrea Löliger , " Johdanto tekijäkaavioihin ", IEEE Signal Processing Magazine , voi. 21,2004, s. 28-41 ( DOI 10.1109 / msp.2004.1267047 )
JS Yedidia , WT Freeman , Y. Weiss ja Y. , " Vapaaenergiarviointien ja yleisten uskonlisäysalgoritmien rakentaminen ", IEEE Transaction on Information Theory , voi. 51, n ° 7,Heinäkuu 2005, s. 2282–2312 ( DOI 10.1109 / TIT.2005.850085 , luettu verkossa , käytetty 28. maaliskuuta 2009 )
A. Braunstein , M. Mézard ja R. Zecchina , " Tutkimuksen eteneminen: tyydyttävyyden algoritmi ", Random Structures & Algorithms , voi. 27, n ° 22005, s. 201–226 ( DOI 10.1002 / rsa.20057 )
Yair Weiss ja William T. Freeman , " Uskon etenemisen oikeellisuus mielivaltaisen topologian Gaussin graafisissa malleissa ", Neural Computation , voi. 13, n ° 10,Lokakuu 2001, s. 2173–2200 ( PMID 11570995 , DOI 10.1162 / 089976601750541769 )
Dmitry M. Malioutov , Jason K. Johnson ja Alan S. Willsky , " Kävelysummat ja uskon eteneminen Gaussin graafisissa malleissa ", Journal of Machine Learning Research , voi. 7,Lokakuu 2006, s. 2031–2064 ( luettu verkossa , kuultu 28. maaliskuuta 2009 )
Gaussin uskomusten etenemisen ratkaisija lineaaristen yhtälöjärjestelmien järjestelmille. Kirjoittanut O. Shental, D. Bickson, PH Siegel, JK Wolf ja D. Dolev, IEEE Int. Kiva. on Inform. Theory (ISIT), Toronto, Kanada, heinäkuu 2008. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ "Arkistoitu kopio" (versio 14. kesäkuuta 2011 Internet-arkistossa )
Lineaarinen tunnistus uskonlisäyksen avulla. Danny Bickson, Danny Dolev, Ori Shental, Paul H. Siegel ja Jack K. Wolf. Vuonna 45. Annual Allerton Conference on Communication, säätö- ja Computing, Allerton House, Illinois, syyskuu 7 http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ ”kopiosta” (versio 14. kesäkuuta 2011 Internet-arkistossa )
Hajautettu laajamittainen verkkoapuohjelman maksimointi. D. Bickson, Y. Tock, A. Zymnis, S. Boyd ja D. Dolev. ISIT: n kansainvälisessä symposiumissa, heinäkuu 2009. http://www.cs.huji.ac.il/labs/danss/p2p/gabp/ "Arkistoitu kopio" (versio 14. kesäkuuta 2011 Internetissä) Arkisto )

Lisälukemista

Bickson, Danny. (2009). Gaussin uskomuksen lisäämisen resurssisivu - verkkosivu, joka sisältää uusimmat julkaisut sekä Matlab-lähdekoodin.
Coughlan, James. (2009). Johdanto levittämisen uskon opetusohjelma .
Koch, Volker M. (2007). Graafisen tekijän mallipohjainen signaalin erottelumenetelmä - opinnäytetyön tyyliopetus
Hans-Andrea Löliger , " Johdanto tekijäkaavioihin ", IEEE Signal Proc. Mag. , voi. 21,2004, s. 28–41 ( lue verkossa )
Mackenzie, Dana (2005). " Tiedonsiirtonopeus lähestyy päätelaitteen nopeutta ", Uusi tutkija . 9. heinäkuuta 2005. Kysymys 2507 (Rekisteröinti vaaditaan)
Henk Wymeersch , iteratiivinen vastaanottimen suunnittelu , Cambridge University Press ,2007, 272 Sivumäärä ( ISBN 978-0-521-87315-4 ja 0-521-87315-0 , lue verkossa )
JS Yedidia , WT Freeman ja Y. Weiss , Tekoälyn tutkiminen uudella vuosituhannella , Morgan Kaufmann,tammikuu 2003, 239–236 Sivumäärä ( ISBN 1-55860-811-7 ) , "Uskon lisääntymisen ja sen yleistämisen ymmärtäminen"
JS Yedidia , WT Freeman ja Y. Weiss , " Vapaaenergiarviointien ja yleisten uskonlisäysalgoritmien rakentaminen ", IEEE Transactions on Information Theory , voi. 51, n ° 7,Heinäkuu 2005, s. 2282–2312 ( DOI 10.1109 / TIT.2005.850085 , luettu verkossa , käytetty 28. maaliskuuta 2009 )

Aiheeseen liittyvä artikkeli

Poly-puu