Nyligen har forskare visat att "loopy tro förökning" -användningen av Pearls polytree algoritm i ett Bayesian nätverk med loopar - kan prestera bra i samband med felkorrigering koder. Det mest dramatiska exemplet på detta är den nära Shannon-limit prestandan hos "Turbo Codes" -koder vars avkodningsalgoritm är likvärdig med loody tro förökning i ett kedjestrukturerat Bayesian nätverk. I det här dokumentet frågar vi: finns det något speciellt med den felkorrigerande kodens sammanhang, eller fungerar loopy-utbredning som ett ap proximate inference system i en mer allmän miljö? Vi jämför marginalerna med att använda loopy-utbredning med de exakta i fyra Bayesianska nätverksarkitekturer, inklusive två verkliga nätverk: ALARM och QMR. Vi finner att de loopy övertygelser av tio konvergerar och när de gör det, de ger en bra approximation till de rätta marginalerna. På QMR-nätet oscillerade dock loopy be liefs och hade inget uppenbart förhållande till de rätta baksidorna. Vi presenterar några inledande undersökningar av orsaken till dessa oscillationer, och visar att vissa simple metoder för att förhindra dem leder till fel resultat. Uppgiften att beräkna bakre marginaler på noder i ett godtyckligt Bayesian nätverk är känd för att vara NP hårt [5]. Detta gäller även för den till synes enklare uppgiften att beräkna ungefärliga baksidor [6]. På grund av den uppenbara praktiska betydelsen av denna uppgift har det dock funnits ett stort intresse av att bedöma kvaliteten på olika tillnärmningssystem, i ett försök att avgränsa de typer av nät och system för vilka varje system fungerar bäst. I detta dokument undersöker vi approximationen av "loopy trosförökning". Detta avser användning av den välkända Pearl polytree algoritm [12] på ett Bayesian nätverk med loopar (oriktade cykler). Algoritmen är en exakt slutledning algoritm för individuellt anslutna nätverk - övertygelserna konvergerar till cor rect marginals i ett antal iterationer lika med diametern på grafen.1 Men, som Pearl noterade, samma algoritm kommer inte att ge rätt övertygelser för mul titly anslutna nätverk: När slingor är närvarande, nätverket är inte längre ensam ansluten och lokala propagering system kommer alltid att stöta på problem. Vi tror att det finns allmän oupptäckta teorem om utförandet av trosutbredning på loody DAGs. Dessa rems, som kanske inte har något direkt att göra med kodning eller avkodning, kommer att visa att i någon mening tro förökar sig "med hög sannolikhet till ett nästan optimalt värde" av den önskade tron på en klass av loopy DAGs [10]. Framsteg i analysen av slingrig trosspridning har gjorts när det gäller nätverk med en enda slinga [18, 19, 2, 1]. För summeringen (eller "trouppdatering" ) version kan det visas att: • Om inte alla villkorliga sannolikheter är avskräckande ministisk, tro förökning kommer att konvergera. • Det finns ett analytiskt uttryck som relaterar cor rect marginals till loopy marginals. Felet när det gäller överensstämmelse beror på meddelandenas konvergensgrad - ju snabbare konvergens desto mer exakt approximation. • Om de dolda noderna är binära, då tröskeln loody övertygelser garanteras att ge den mest sannolika uppgiften, även om det numeriska värdet av övertygelsen kan vara felaktig. Detta resultat håller bara för noder i slingan. I versionen av max-produkten (eller "trorevisionen") visade Weiss [19] att ( 1) trosförökning kan närma sig ett stabilt värde eller svänga i en gränscykel och (2) om den konvergerar är det garanterat att ge cor rect-tilldelningen av värden till de dolda noderna. Detta resultat är oberoende av rity av noderna och om noderna är inuti eller utanför loopen. För nätverk med flera slingor har Richard son [14] analyserat det speciella fallet med Turbo-koder. Han har visat att fasta punkter i sammanfattningen alltid existerar och har gett tillräckliga förutsättningar för att de skall vara unika och stabila (även om det kan vara svårt att kontrollera dessa förhållanden för stora nätverk). För att sammanfatta, vad som för närvarande är känt om loopy utbredning är att ( 1) det fungerar mycket bra i en felkorrigering kodinställning och (2) det finns villkor för ett en-loop nätverk som det kan garanteras att fungera bra. I detta dokument undersöker vi loopy prop agation empiriskt under ett bredare spektrum av förhållanden. Finns det något speciellt med kodinställningen för felkorrigering, eller fungerar loopy-utbredning som ett approximationssystem för ett bredare spektrum av nätverk? ..\ x(:x). (1) var: och: Meddelandet X passerar till sin förälder U; ges av: och meddelandet X skickar till sitt barn Y j ges av: k;Cj För bullriga-eller länkar mellan föräldrar och barn, det finns ett analytiskt uttryck för 1r( x) och Ax ( u;) som undviker den uttömmande uppräkning över förälder inställning [12]. Vi gjorde en liten ändring av uppdateringsreglerna genom att vi normaliserade både..\ och 1r meddelanden vid varje iteration. Som Pearl [12] påpekade gör en normalisering av budskapen ingen skillnad för den slutliga tron men undviker numeriskt underflöde. Noder uppdaterades parallellt: vid varje iteration beräknade alla noder sina utgående meddelanden baserat på inkommande meddelanden från sina grannar från den tidigare iterationen. Budskapen sades konvergera om ingen av troarna i på varandra följande iterationer förändrades med mer än en liten tröskel (10-4). Alla meddelanden initierades till en vektor av ettor; slumpmässig initialisering gav liknande resultat, eftersom de ursprungliga förhållandena snabbt blir "tvättade". Som jämförelse har vi också genomfört sannolikhetsvägning [17], vilket är en enkel form av viktprovtagning. Precis som alla provtagningsalgoritmer kan felen drivas mot noll genom att köra algoritmen tillräckligt länge; i det här dokumentet använde vi vanligtvis 200 sam ples, så att den totala mängden beräkningstid var ungefär jämförbar (till en storleksordning) Vi använde två syntetiska nätverk, PYRAMID och leksakQMR, och två verkliga nätverk, ALARM och QMR. De syntetiska nätverken är tillräckligt små att vi kan utföra exakta slutsatser, med hjälp av jungtion träd algoritm. Detta gör det möjligt att mäta approximeringssystemets tillförlitlighet. Alla nätverk har många slingor av olika storlekar. PYRAMID-nätverket Figur 1 visar strukturen på PYRAMID-nätet. Detta är ett flerskiktat hierarkiskt nätverk med lokala anslutningar mellan varje lager och observationer endast i det nedre skiktet. Vi valde denna struktur vara orsak nätverk av denna typ används ofta i bildanalys-det nedre skiktet skulle motsvara pix els (se till exempel (15]). Alla noder var binära och de villkorade sannolikheterna representerades av tabeller-enheter i de villkorade sannolikhetstabellerna (CPT) valdes enhetligt i intervallet (0, 1]. Leksaks-QMR-nätverket Figur 2 visar strukturen för ett leksaks-QMR-nätverk. Detta nätverk är tänkt att representera de typer av nät verk som uppstår i medicinsk diagnos - dold dis lättar i det översta lagret och observerade symtom i det nedre lagret. Här randomiserade vi över struktur och parametrar - för varje experiment föräldrarna till varje nod i det nedre lagret var en slumpmässigt vald delmängd av noderna i det översta lagret. Föräldrarna delmängd valdes med hjälp av en enkel procedur - varje förälder-barn länk var antingen närvarande eller frånvarande med en sannolikhet på 0,5. Alla noder var binära och de villkorliga sannolikheterna för bladen representerades av en bullriga-eller:? (Child= OIParents) = e-Bo-L; B,Paren t; där 110 representerar termen "läcka". Figur 3 visar strukturen för ALARM-nätverket - ett Bayesianskt nätverk för övervakning av patienter i spänd vård. Detta nätverk användes av (3] för att jämföra olika inferensalgoritmer. Nodernas aritualitet varierar från två till fyra och alla villkorade fördelningar representeras av tabeller. Strukturen och CPT laddades ner från Nir Friedmans Bayesian-nätverksarkiv på: www. Detta beslut träder i kraft den tjugonde dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Detta anslag är avsett att täcka utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet rättsliga och inrikes frågor samt administrativa utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet rättsliga och inrikes frågor. Det är ingen fara. QMR-DT är ett bipartitnätverk vars struktur är densamma som den som visas i figur 2 men storleken är mycket större. Det finns cirka 600 sjukdomar och Ap proximately 4000 findin noder, med ett antal observerade fynd som varierar per fall. På grund av formen av de bullriga-eller CPTs komplexitet inferens är exponentiell i antalet positiva fynd (7]. Fol lowing (8] fokuserade vi på de fyra CPC fall där antalet positiva resultat är mindre än 20, så att exakt slutsats är möjlig (med hjälp av QUICKSCORE algoritm (7]). Resultat Det experimentella protokollet för PYRAMID-nätverket var som följer. För varje försökskörning, vi först genererade slumpmässiga CPTs. Vi tog sedan prover från den gemensamma distributionen som definierades av nätverket och klämde fast de observerade noderna (alla noder i bottenskiktet) till deras provvärde. Med tanke på struktur och observationer körde vi sedan tre inferensalgoritmer -junction träd, loody tro förökning och provtagning. Vi fann att slingrig trosutbredning alltid begrep i detta fall med det genomsnittliga antalet iterioner lika med 10.2. Det experimentella protokollet för leksaks-QMR-nätverket liknade det för PYRAMID-nätverket förutom att vi randomiserade över struktur också. Återigen fann vi att loopy tro förökning alltid konvergerade, med det genomsnittliga antalet iterationer lika med 8.65. Figur 5 visar de två korrelationsytorna. Protokollet för ALARM-nätverksexperimenten skilde sig från de två föregående i det att strukturen och parametrarna var fasta - endast de observerade bevisen skilde sig mellan försökskörningar. Vi antog att alla blad noder observerades och beräknade pos- Figur 2: Strukturen av en leksak QMR nätverk. Detta är en bipartit struktur där den villkorliga fördelningen av bladen är bullriga eller bullriga. Det nätverk som visas representerar ett prov från slumpmässigt genererade strukturer där föräldrarna till varje symptom var en slumpmässig delmängd av sjukdomarna. främre marginaler för alla andra noder. Återigen fann vi att loopy tro förökning alltid konvergerade med det genomsnittliga antalet iterationer lika med 14,55. Bild 6 visar korrelationsytorna. Med 200 prover är korrelationen för sannolikhetsviktning ganska svag, kanske på grund av att vissa noder är större (och därmed större tillståndsutrymme); efter 1000 prover förbättras korrelationen avsevärt. De resultat som hittills presenterats visar att loopig utbredning fungerar bra för en mängd olika arkitekturer med flera slingor. Vi presenterar nu resultat för QMR-DT-nätverket som inte är lika gynnsamma. I QMR-DT-nätverket fanns ingen randomisering. Vi använde den fasta strukturen och beräknade posteriors för de fyra fall för vilka posteriors har calculated exakt av Heckerman [7]. För inget av dessa fyra fall konvergerade loopy förökning. Snarare svängde loopy marginalen mellan två ganska distinkta värden för nästan alla noder. Figur 7 a visar tre sådana marginaler. Efter två iterationer tycks marginalen konvergera till en gränscykel med period två. I figur 7 b verkar det som om de rätta baksidorna ligger inom det intervall som definieras av gränscykeln. Detta är dock inte alltid fallet (utom, naturligtvis, när intervallet är 0 till 1!). Vad våra första experiment visar är att loopy prop agation gör ett bra jobb med att approximera rätt posteriors om det konvergerar. Tyvärr, i det mest utmanande fallet-det QMR-DT nätverk-det al gorithm inte konvergerade. Vi ville se om denna oscillerande beteende i QMR-DT fallet var relaterad till storleken på nätverket - gör loopy utbredning tenderar att konvergera mindre för stora nätverk än små nätverk? För att undersöka denna fråga försökte vi orsaka oscillation i leksaks-QMR-nätverket. Vi frågade först vad, förutom storleken, är annorlunda mellan leksak QMR och verkliga QMR? En uppenbar skillnad är i parametern val ues - medan CPTs för leksak QMR är slumpmässiga, de verkliga QMR parametrar är inte. I synnerhet är den tidigare sannolikheten för att en sjukdom nod på är extremt låg i den verkliga QMR (typiskt i ordningen 10-3 ). Skulle låg tidigare orsaka svängningar i leksaks-QMR-fallet? För att besvara denna fråga upprepade vi de ex periment som rapporterades i föregående avsnitt, men i stället för att ha den tidigare sannolikheten för varje nod körs domly valt i intervallet [0, 1] valde vi den föregående enhetligt i intervallet [0, U] och varierade U. Till skillnad från tidigare simuleringar ställde vi inte in de observerade noderna genom provtagning från de gemensamma - för låga tidigare resultaten skulle alla fynd vara negativa och slutsatser skulle vara triviala. I stället var varje upptäckt på ett oberoende sätt inställd på positivt eller negativt. Figur 8 visar resultaten - för små föregångare konvergerar inte leksaks-QMR-nätverket och vi hittar samma oscillerande beteende som i det verkliga QMR-nätverksfallet. Om faktiskt små tidigare företag är ansvariga för oscillationen, då skulle vi förvänta oss att det verkliga QMR-nätverket skulle konvergera om de tidigare togs slumpmässigt i intervallet [0, 1]. För att kontrollera detta, vi reran loody propagation på hela QMR-nätverket med de fyra dragbara fall men ändrade tidigare att slumpmässigt tas prover i intervallet [0, 1]. Alla andra parametrar förblev desamma som i det verkliga QMR-nätverket. Nu fann vi konvergens i alla fyra fallen och övertygelsen gav ett mycket bra samband med dem som beräknades med QUICKSCORE. Små domar är inte det enda som orsakar oscillation. Små vikter kan också. Effekten av båda De exakta marginalerna representeras av cirklarna; ändarna av "terrorbarerna" representerar de loopiga marginalerna vid de två senaste iterationerna. Vi plottar bara de sjukdomar som hade icke-försumbar bakre sannolikhet. Loopy tros propagation. S---=-o. a-----' intervall av föregående Figur 8: Sannolikheten för konvergens i leksaks QMR fallet som den övre gräns för tidigare sjukdomar ökar. När den föregående är liten (liknar den verkliga QMR-ordningen) konvergerar leksaken QMR ganska sällan. Detta tyder på att misslyckandet med konvergensen i de verkliga QMR-fallen hänger samman med det låga tidigare är att minska sannolikheten för positiva resultat. Vi förmodade att orsaken till svängningarna är att de observerade uppgifterna, som har många positiva resultat, är mycket otypiska i detta parametersystem. Detta skulle också förklara varför vi inte hittade svängningar i de andra exemplen, där data togs från den gemensamma distributionen kodad av nätverket. För att testa denna hypotes, vi reparameterized pyra mitten nätverk så här: vi ställa in den tidigare sannolikheten för "1" tillstånd av rot noderna till 0,9, och vi använde den bullriga-OR-modellen för de andra noderna med en liten (0.1) hämningsannolikhet (förutom läckagetermen, som vi hämmade med sannolikhet 0,9). Denna parameterisering har effekten av att föröka 1s från det översta lagret till botten. Således är den verkliga marginalen vid varje blad ungefär (0,1, 0,9), dvs bladen är 1 med hög sannolikhet. Vi genererade sedan otypiska bevis på bladen genom provtagning från den enhetliga fördelningen (0,5, 0,5), eller från den skeva distributionen (0,9, 0. Första stycket ska ersättas med följande: Vi fann att den loopiga utbredningen fortfarande konvergerade2, och att de marginaler till vilka den konvergerade var i hög grad korrelerade med de rätta marginalerna. Det måste alltså finnas någon annan förklaring, förutom att bevisen är otypiska, för de os cillations som observerats i QMR. När loopy förökning pendlar mellan två stadiga tillstånd verkar det rimligt att försöka hitta ett sätt att jämföra de två värdena. Det enklaste är att räkna ut dem. Tyvärr gav detta mycket dåliga resultat, eftersom de korrekta baksidorna vanligtvis inte ligger i mitten av intervallet ( cf. Fig. 7 (b) ). 2Mer exakt, vi fann att med en konvergenströskel på 10-4, 98 av 100 fall konvergerade; när vi sänkte tröskeln till 10-3, alla 100 fall konvergerade. Vi försökte också undvika oscillationer genom att använda "momen um"; ersätta de meddelanden som sändes vid tidpunkten t med ett vägt genomsnitt av meddelandena vid tidpunkterna t och t-1. Det vill säga, vi ersatte hänvisningen till >. ) i och på liknande sätt för 11" ) i ekvation 3, där 0 :::; J.l :::; 1 är momentum sikt. Det är lätt att visa att om det modifierade ekvationssystemet konvergerar till en fast punkt F, så är F också en fast punkt i det ursprungliga systemet (eftersom om>. ) = >. -1), sedan Ekvation 7 avkastning>. ) ). I de experiment för vilka loopy förökning konkanted (PYRAMID, leksak QMR och ALARM), fann vi att lägga till momentum term inte ändra resultaten - de övertygelser som resulterade var samma vara lögner hittades utan momentum. I experimenten som inte konvergerade (leksak QMR med små tidigare och verkliga QMR), fann vi att momentum avsevärt minskade risken för oscillation. I flera fall var dock de föreställningar som algoritmen konvergerade mot helt felaktiga – se figur 9. De experimentella resultat som presenteras här tyder på att loopig utbredning kan ge exakta bakre marginaler i en mer allmän inställning än felkorrigerande kodning - PYRAMID, leksak QMR och ALARM nätverk är ganska annorlunda från felkorrigerande kodning grafer men loopy övertygelser visar hög korrelation med rätt marginaler. Vid felkorrigering koder den bakre är typiskt högt toppade och man kan tycka att denna funktion är nödvändig för god prestanda av loopy prop agation. Våra resultat tyder på att så inte är fallet - i ingen av våra simuleringar var de bakre starkt toppade runt en enda gemensam konfiguration. Om prob förmåga massa var koncentrerad på en enda punkt skulle marginal sannolikheterna alla vara nära noll eller en; detta är helt klart inte fallet som kan ses i siffrorna. Man kan förvänta sig att loopig utbredning endast skulle fungera bra för grafer med stora slingor. Men våra resultat, och tidigare resultat på turbokoder, visar att loopig utbredning också kan fungera bra för grafer med många små slingor. Samtidigt föreslår våra experimentella resultat en varnande anmärkning om loopig utbredning, som visar att marginalerna kan uppvisa oscillationer som har mycket liten korrelation med de rätta marginalerna. Vi lade fram några preliminära resultat som undersökte orsaken till svängningarna och visade att det inte är en enkel fråga om storleken på nätverket eller antalet föräldrar. Snarare samma struktur med olika parametervärden kan oscillera eller uppvisa stabil vara havior. För alla våra simuleringar, fann vi att när loopy förökning konvergerar, det ger en förvånansvärt bra ap proximation till rätt marginaler. Eftersom skillnaden mellan konvergens och svängningar är lätt att göra efter ett litet antal iterationer, kan detta leda till ett sätt att kontrollera om loopig utbredning är lämplig för ett visst problem. Vi tackar Tommi Jaakkola, David Heckerman och David MacKay för användbara diskussioner. Vi tackar även Randy Miller och universitetet i Pittsburgh för användningen av QMR-DT-databasen. Stödd av MURI ARO DAAH04-96-1-0341. Algoritm. Dessa tillvägagångssätt är garanterade att hitta lokala maxima, men utforska inte landskapet för andra lägen. Vårt tillvägagångssätt utvecklar strukturen och de uppgifter som saknas. Vi jämför våra stokastiska algoritmer och visar att de alla ger korrekta resultat.
För grafstrukturer med loopar, Loopy Belief Propagation (LBP) REF är empiriskt bevisat att utföra för diskreta variabler.
Loopy Belief Propagation for Approximate Inference: An Empirical Study
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}