En Kort Introduktion till Grafiska Modeller och Bayesianska Nätverk

link: http://www.cs.ubc.ca/~murphyk/Bayes/bnintro.html

Av Kevin Murphy, 1998.

“Grafiska modeller är ett äktenskap mellan sannolikhetsteori och grafteori. De ger ett naturligt verktyg för att hantera två problem som förekommer i hela tillämpad matematik och teknik — osäkerhet och komplexitet-och i synnerhet de spelar en allt viktigare roll i utformning och analys av maskinlärande algoritmer. Grundläggande idén av en grafisk modell är uppfattningen av modularitet-ett komplext system som är byggt genom att kombinera enklare delar. Sannolikhetsteori erbjuder lim där delarna är i kombination, för att säkerställa att systemet som helhet är konsekvent, och att ge möjligheter att gränssnittet modeller till data. Grafen teoretiska sidan av grafiska modeller erbjuder både ett intuitivt tilltalande gränssnitt genom vilket människor kan modellen mycket interagera uppsättningar av variabler samt en data struktur som lämpar sig naturligtvis till utformning av effektiva allmänt ändamål algoritmer.

Många av de klassiska multivariat probabalistic system som studeras inom områden som statistik, systemteknik, informations-teori, mönsterigenkänning och statistisk mekanik är specialfall av den allmänna grafiska modell formalism — exempel blandningen modeller, faktoranalys, hidden Markov-modeller, Kalman filter och Ising modeller. Den grafiska modellen ram ger ett sätt att visa alla dessa system som exempel på ett gemensamt underliggande formalism. Denna uppfattning har många fördelar, i synnerhet, specialiserade tekniker som har utvecklats i ett fält kan överföras mellan forskning och utnyttjas i större utsträckning. Dessutom, den grafiska modellen formalism ger en naturlig ram för utformningen av nya system.” — Michael Jordan, 1998.

Denna tutorial

Vi kommer att kort diskutera följande ämnen.

  • Representation, eller, vad exakt är en grafisk modell?
  • Slutsats, eller, hur kan vi använda dessa modeller för att effektivt svara på probabilistiska frågor?
  • lär dig, eller, vad gör vi om vi inte vet vad modellen?
  • beslutsteori, eller, vad som händer när det är dags att omvandla idéer till handling?
  • Program, eller, vad är allt detta bra för, egentligen?

Notera: Dan Hammerstrom har gjort en pdf – version av denna web sida. Jag har också en nära anknytning handledning i postscript eller pdf – format.

Artiklarna i den populära pressen

Följande artiklar ger mindre teknisk introduktion.

Andra källor av teknisk information

Representation

Probabilistisk grafiska modeller är grafer där noderna representerar stokastiska variabler, och (brist på) bågar representerar villkorad självständighet antaganden. Därför att de ger en kompakt representation av gemensamma sannolikhetsfördelningar. Oplanerade, grafiska modeller, även kallad Markov Slumpmässiga Områden (MRFs) eller Markov-nätverk, har en enkel definition av oberoende: två (set) noder A och B är villkorligt oberoende gett en tredje set, C, om alla vägar mellan noder i A och B är åtskilda av en nod i C. Däremot, riktad grafiska modeller även kallade Bayesianska Nätverk eller Övertygelse Nätverk (BNs), har en mer komplicerad begreppet självständighet, som tar hänsyn till riktningen av bågar, som vi beskriver nedan.

Oplanerade grafiska modeller är mer populära med fysik och vision samhällen, och regisserad modeller är mer populära med AI och statistik samhällen. (Det är möjligt att ha en modell med både riktade och oplanerade bågar, som kallas en kedja graf.) För en noggrann studie av förhållandet mellan riktad och oplanerade grafiska modeller, se böcker av Pearl88, Whittaker90, och Lauritzen96.

Även om regisserad modeller har en mer komplicerad begreppet självständighet än oplanerade modeller, de har flera fördelar. Det viktigaste är att man kan betrakta en båge från A till B som anger att En `orsaker” B. (Se diskussionen på kausalitet.) Detta kan användas som en guide för att bygga grafen struktur. Dessutom riktas modeller kan koda deterministiska relationer, och är lättare att lära sig (passar till data). I resten av denna handledning kommer vi bara att diskutera riktade grafiska modeller, dvs, Bayesianska nätverk.
Förutom att grafen struktur, är det nödvändigt att ange parametrar i modellen. För en riktad modell, måste vi ange den betingade Sannolikheten Distribution (CPD) vid varje nod. Om variablerna är diskret, detta kan representeras som en tabell (CPT), som visar sannolikheten att barnet nod tar på var och en av dess olika värden för varje kombination av värderingar av sina föräldrar. Tänk dig följande exempel, där alla noder är binära, dvs, har två möjliga värden, som vi kommer att beteckna med T (sant) och F (falskt).

1
Vi ser att evenemanget “gräset är vått” (W=true) har två möjliga orsaker: antingen vatten sprinker är på (S=sant) eller att det regnar (R=true). Styrkan i denna relation visas i tabellen. Till exempel ser vi att Pr(B=true | S=sant, R=false) = 0.9 (andra raden), och därmed, Pr(B=false | S=sant, R=false) = 1 – 0.9 = 0.1, eftersom varje rad måste summera till en. Eftersom C-nod har inga föräldrar, sin CPT anger innan sannolikhet att det är molnigt (i det här fallet, 0.5). (Tänk på C som representerar säsongen: om det är en mulen säsong, är det mindre troligt att sprinkler är på och mer troligt att regnet är på.)

Den enklaste villkorligt oberoende relation som kodats i ett Bayesianska nätverk kan anges som följer: en nod är oberoende av dess förfäder med tanke på dess föräldrar, där förfadern/förälder-relationen är med hänsyn till vissa fasta topologiska beställning av noder.

Av kedjeregeln av sannolikhet, gemensamma sannolikheten för alla noder i grafen ovan är

P(C, S, R, W) = P(C) * P(S|C) * P(R|C,S) * P(W|C,S,R)

Med hjälp av villkorsstyrd oberoende relationer, kan vi skriva detta som

P(C, S, R, W) = P(C) * P(S|C) * P(R|C) * P(W|S,R)

där fick vi lov att förenkla den tredje termen, eftersom R är oberoende av S med tanke på dess förälder C, och den sista termen eftersom W är oberoende av C med tanke på dess föräldrar, S och R.

Vi kan se att den villkorliga oberoende relationer möjligt för oss att företräda gemensam mer kompakt. Här besparingarna är minimal, men i allmänhet, om vi hade n binära noder, full gemensamt skulle kräva O(2^n) utrymme för att representera, men vägts form skulle kräva O(n 2^k) utrymme för att representera, där k är den största fan-i en nod. Och färre parametrar, gör lärandet lättare.

“Bayesianska nätverk” Bayesian?

Trots namnet, Bayesianska nätverken inte nödvändigtvis innebär ett åtagande att Bayesiansk statistik. Ja, det är vanligt att använda frequentists metoder för att skatta parametrarna i den CPDs. Snarare är de kallas så eftersom de använda Bayes regel för probabilistisk slutledning, som vi beskriver nedan. (Begreppet “riktad grafiska modellen” är kanske mer lämpligt.) Nevetherless, Bayesianska nät är en användbar representation för hierarkisk Bayes-modeller, som utgör grunden för tillämpad Bayesiansk statistik (se t ex FEL – projektet). I en sådan modell, de parametrar som behandlas som alla andra slumpmässig variabel, och blir noder i grafen.

Slutledning

Den vanligaste uppgiften som vi vill lösa med hjälp av Bayesianska nätverk är probabilistisk slutledning. Tänk till exempel vatten sprinkler nätverk, och antag att vi betraktar det faktum att gräset är vått. Det finns två möjliga orsaker till detta: antingen det regnar eller sprinkler är på. Vilket är mer troligt? Vi kan använda Bayes’ regel för att beräkna den bakre sannolikheten för varje förklaring (där 0==false och 1==true).

2

3
där

4
är en normalisering konstant, lika med sannolikheten (risken) av data. Så ser vi att det är mer sannolikt att gräset är vått eftersom det regnar: sannolikheten förhållandet är 0.7079/0.4298 = 1.647.

Att Förklara bort

I ovanstående exempel, notera att de två orsaker “tävla” för att “förklara” den observerade data. Därför S-och R-bli villkorligt beroende med tanke på att deras gemensamma barn, W, observeras, även om de är marginellt oberoende. Till exempel, anta att gräset är vått, men som vi också vet att det regnar. Sedan bakre sannolikheten att sprinkler är att den går ner:

Pr(N=1|B=1,R=1) = 0.1945

Detta kallas att “förklara bort”. I statistik, detta är känt som Berkson paradox, eller “selection bias”. För ett dramatiskt exempel på denna effekt, anser att en högskola som medger studenter som antingen är begåvad eller sportig (eller båda!). Låt C beteckna händelsen att någon som är antagen till college, som är gjord sanna om de antingen är begåvad (B) eller sportig (S). Antag att i den allmänna befolkningen, B och S är oberoende. Vi kan vår modell villkorad självständighet antaganden med hjälp av ett diagram som är en V struktur, med pilar som pekar nedåt:

   B   S 
    \ /
     v
     C
 Titta nu på en befolkning av studenter (de för vilka C observeras att vara sant). Det kommer att vara hjärna gör du mindre sannolikt att vara sportig och vice versa, eftersom någon egendom som ensam är tillräcklig för att förklara de bevis på C (dvs. P(S=1 | C=1, B=1) <= P(S=1 | C=1)). (Om du inte tror mig, försök med denna lilla BNT demo!)

Top-down och bottom-up resonemanget

I vattnet sprinkler exempel, vi hade bevis för en effekt (vått gräs), och slutsatsen är den mest sannolika orsaken. Detta kallas för diagnostik, eller “nedifrån och upp”, resonemang, eftersom det går från verkningar av orsaker, det är en gemensam uppgift i expert systems. Bayesianska nät kan också användas för kausala, eller “uppifrån och ner”, resonemang. Till exempel, kan vi beräkna sannolikheten för att gräset ska vara blöt med tanke på att det är molnigt. Därför Bayesianska nät kallas ofta för “generativ” – modeller, eftersom de anger hur orsaker generera effekter.

Kausalitet

En av de mest spännande sakerna med Bayesianska nät är att de kan användas för att sätta diskussioner om kausalitet på en solid matematisk grund. En mycket intressant fråga är: kan vi skilja orsakssamband från ren korrelation? Svaret är “ibland”, men du behöver för att mäta sambanden mellan minst tre variabler, intution är att en av de variabler som fungerar som en “virtuell kontroll” för förhållandet mellan de två andra, så att vi inte alltid behöver göra experiment för att dra slutsatsen att det finns ett orsakssamband. Se följande böcker för detaljer.

“Kausalitet: Modeller, Resonemang och Slutsatser”, Judea Pearl, 2000, Cambridge University Press.

“Orsakssamband, Prognos och Sök efter”, Spirtes, Glymour och Scheines, 2001 (2: a upplagan), MIT Press.
“Orsak och Samband i Biologi”, Bill Shipley, 2000, Cambridge University Press.

“Beräkning, Orsakssamband och Discovery”, Glymour och Cooper (red), 1999, MIT Press.

Villkorad självständighet i Bayesianska Nät

I allmänhet är villkorligt oberoende relationer som kodats av en Bayes Net är bäst förklaras med hjälp av “Bayes Bollen” – algoritmen (på grund av Ross Shachter), som är som följer: Två (set) noder A och B är villkorligt oberoende (d-separerad) givet en uppsättning C om och endast om det inte finns något sätt för en boll för att komma från A till B i diagrammet, där tillåten förflyttning av bollen visas nedan. Dolda noder noder vars värden inte är kända och finns avbildad som oskuggade, observerad noder (de som vi har tränat på) är skuggade. De streckade pilarna anger riktningen på flödet av bollen.

bayes_ball_no_det
Den mest intressanta fallet är den första kolumnen, när vi har två pilar konvergerar på en nod X (så att X är ett “blad” med två föräldrar). Om X är dold, dess föräldrar är marginellt oberoende, och därmed kulan inte passerar genom (bollen är “vände” indikeras genom den böjda pilar); men om X är observerade, föräldrar blir beroende, och bollen inte kan passera genom, på grund av att förklara bort fenomenet. Observera att om denna graf var oplanerade barnet alltid skulle skilja föräldrar, och därför när du konverterar en riktad graf till en oplanerade diagram, vi måste lägga till länkar mellan “ogift” föräldrar som delar ett gemensamt barn (dvs, “moralize” grafen) för att hindra oss att läsa av felaktiga oberoende rapporter.

Betrakta nu den andra kolumnen där vi har två olika pilar från X (så att X är en “root”). Om X är dold, barn är beroende av, eftersom de har en dold gemensam sak, så bollen passerar igenom. Om X är observerade, barn blir villkorligt oberoende, så att bollen inte kan passera genom. Slutligen anser de fall där vi har en inkommande och utgående pil till X. Det är intuitivt att noder uppströms och nedströms X är beroende av iff X är dold, eftersom luftkonditionering på en nod bryter grafen på den punkten.

Bayesianska nät med diskreta och kontinuerliga noder

Den inledande exempel används noder med kategoriska värderingar och multinomial distributioner. Det är också möjligt att skapa Bayesianska nätverk med kontinuerliga värderas noder. Den vanligaste fördelningen för sådana variabler är Gaussiskt. För diskreta noder med kontinuerlig föräldrar, kan vi använda logistisk/softmax distribution. Med hjälp av multinomials, villkorlig Gaussians, och softmax distribution, kan vi ha en rik verktygslåda för att göra komplexa modeller. Några exempel visas nedan. För mer information, klicka här. (Cirklar beteckna kontinuerlig-värda stokastiska variabler, rutor betecknar diskret rv: s, klart betyder gömd, och skuggade innebär observerade.)

 

56

 

fa789

För mer information, se denna utmärkta papper.

En Enande Översyn av Linjära Gaussiska Modeller, Sam Roweis & Zoubin Ghahramani. Neurala Beräkningar 11(2) (1999), s. 305-345

Temporal modeller

Dynamisk Bayesianska Nätverk (DBNs) är regisserad grafiska modeller av stokastiska processer. De generalisera dold Markov-modeller (HMMs) och linjära dynamiska system (LDSs) genom att representera den dolda (och observerade) staten i form av statliga variabler, som kan ha komplexa beroendeförhållanden. Den grafiska strukturen ger ett enkelt sätt att ange dessa villkorade independencies, och därmed att ge ett kompakt parametrisering av modellen.

Observera att “temporal Bayesianska nätverk” skulle vara ett bättre namn än “dynamisk Bayesianska nätverk”, eftersom det förutsätts att den modell som strukturen inte förändras, men termen DBN har blivit bestående. Vi har också förutsätter normalt att de parametrar som inte förändringen, det vill säga, modellen är gång-invariant. Men, vi kan alltid lägga till extra dolda noder för att representera den rådande “ordningen”, och därigenom skapa blandningar av modeller för att fånga återkommande icke-stationarities. Det finns vissa fall då storleken av den statliga utrymme kan förändras över tid, till exempel spårning av en variabel, men okänt, antal objekt. I det här fallet, att vi måste ändra den modell struktur över tid.

Dolda Markov-Modeller (HMMs)

Den enklaste typen av DBN är en Hidden Markov Model (HMM), som har en diskret gömd nod och en diskret eller kontinuerlig observerade nod per skiva. Vi kan illustrera detta nedan. Som innan, cirklar beteckna kontinuerlig noder, rutor betecknar diskret noder, klart betyder gömd, skuggad innebär observerade.

10

Vi har “unrolled” modell 4 “time-slices” – struktur och parametrar antas att upprepa efter modellen är unrolled ytterligare. Därför att ange en DBN, vi måste definiera intra-skiva topologi (inom en bit), inter-skiva topologi (mellan två skivor), samt parametrarna för de två första skivor. (En sådan två-skiva timliga Bayes net kallas ofta för en 2TBN.)
Några vanliga varianter på HMMs visas nedan.

11

Linjära Dynamiska System (LDSs) och Kalman-filter

Ett Linjära Dynamiska System (LDS) har samma topologi som en HMM, men alla noder antas ha linjär-Gaussiska fördelningar, dvs.

 x(t+1) = A*x(t) + w(t), w ~ N(0, Q), x(0) ~ N(init_x, init_V)
y(t) = C*x(t) + v(t), v ~ N(0, R)

Kalman-filtret är ett sätt att göra online filtrering i denna modell. Några enkla varianter av LDSs visas nedan.

 

12131415

Kalman filter har föreslagits som en modell för hur den hjärnan integrerar visuell överblick över tid för att sluta sig till världen som den är, även om verkligheten är naturligtvis mycket mer komplicerat. Det viktigaste är inte att Kalman-filtret är rätt modell, men som hjärnan kombinerar en bottom-up och top-down ledtrådar. Figuren nedan är från en artikel som heter “Ett Kalman-Filter Modell av synbarken”, av P. Rao, Neurala Beräkningar 9(4):721–763, 1997.kfhead

Mer komplexa DBNs

Det är också möjligt att skapa temporal modeller med mycket mer komplicerat topologier, till exempel Bayesiansk Automatiserad Taxi (BAT) nätverk som visas nedan. (För enkelhetens skull har vi bara visa den observerade blad för att skiva 2. Tack för att Daphne Koller för att tillhandahålla denna siffra.)

17

När några av de observerade noder är tänkt som ingångar (handlingar), och några som utgångar (percepts), DBN blir en POMDP. Se även avsnittet om beslutsteori nedan.

En generativ modell för generativa modeller

Figuren nedan, som produceras av Zoubin Ghahramani och Sam Roweis, är en bra sammanfattning av relationer mellan några populära grafiska modeller.

18

 

SLUTLEDNING

En grafisk modell anger en komplett gemensam sannolikhetsfördelning (JPD) över alla variabler. Med tanke på den JPD, vi kan svara på alla möjliga slutsatsen frågor av marginalisering (summering över irrelevanta variabler), som illustreras i inledningen. Dock JPD har storlek O(2^n), där n är antalet noder, och vi har tagit varje nod kan ha 2 staterna. Därmed summera över JPD tar exponentiell tid. Vi nu diskuterar mer effektiva metoder.

Variabel eliminering

För en riktad grafisk modell (Bayes netto), kan vi ibland använda vägts representation av JPD att göra marginalisering på ett effektivt sätt. Den centrala tanken är att “push summor på att” så långt som möjligt när de summeras (marginalizing) bort ovidkommande villkor, till exempel för vatten sprinkler nätverk

19

 

Observera att när vi utför den innersta summor, vi skapar nya villkor, vilka måste vara summeras över i sin tur t ex,

20

där

21

Fortsätter på detta sätt,

22

där

23

Denna algoritm kallas Variabel Eliminering. Principen för att fördela belopp över produkter som kan generaliseras i hög grad att gälla för en kommutativ semiring. Detta är grunden för många vanliga algoritmer, till exempel Viterbi avkodning och den Snabba fouriertransformen. För mer information, se

Det arbete som vi utför när design och en marginell begränsas av storleken av de största term som vi stöter på. Att välja en summering (eliminering) beställning att minimera detta är NP-svårt, även om giriga algoritmer fungerar väl i praktiken.

Dynamisk programmering

Om vi vill beräkna flera marginalnummer på samma gång, kan vi använda Dynamisk Programmering (DP) för att undvika redundant beräkning som skulle vara inblandade om vi använt variabel eliminering upprepade gånger. Om den underliggande oplanerade grafen av BN är acykliska (dvs. ett träd), kan vi använda en lokal budskap som går algoritm på grund av Pearl. Detta är en generalisering av den välkända framåt-bakåt algoritm för HMMs (kedjor). För mer information, se

  • “Probabilistiska Resonemang i Intelligent Systems”, Judea Pearl, 1988, 2: a uppl.
  • “Fusion och reproduktionsmateriel med flera observationer i tron nätverk”, Peot och Shachter, AI 48 (1991) s. 299-318.

Om BN har oplanerade cykler (som i vatten sprinkler exempel), lokala budskap som går algoritmer löper risk för dubbelräkning. exempelvis information från S och R som flyter in W är inte oberoende, eftersom det kom från en vanlig orsak, C. Det vanligaste tillvägagångssättet är därför att omvandla MILJARDER euro i ett träd, genom klustring noder som tillsammans bildar vad som kallas en korsning träd, och sedan köra en lokal budskap som går algoritm på detta träd. Den message passing-system skulle kunna vara Pearl ‘ s algoritm, men det är mer vanligt att använda sig av en variant avsedd för oplanerade modeller. För mer information, klicka här

Speltid för DP-algoritmer är exponentiell i storleken av den största klustret (dessa kluster motsvarar den mellanliggande begrepp som skapats av variabel eliminering). Denna storlek kallas inducerad bredd av grafen. Minimera detta är NP-svårt.

Tillnärmning algoritmer

Många modeller av intresse, till exempel med repetitiva struktur, som i multivariata tidsserier eller bildanalys, har stora inducerad bredd, vilket gör exakt inferens mycket långsamt. Vi måste därför använda för att närma tekniker. Tyvärr, ungefärliga slutledning är #P-svårt, men vi kan ändå komma med approximationer som ofta fungerar bra i praktiken. Nedan är en lista över de stora tekniker.

  • Variational metoder. Det enklaste exemplet är medelvärdet-området approximation, som utnyttjar den stora talens lag till ungefärliga stora summor av stokastiska variabler med deras medel. I synnerhet kommer vi i huvudsak att frikoppla alla noder, och införa en ny parameter, som kallas en variational parameter för varje nod, och iterativt uppdatera dessa parametrar för att minimera cross-entropi (KL avstånd) mellan den ungefärliga och sanna sannolikhetsfördelningar. Uppdatera variational parametrar blir en proxy för inferens. Det betyder-området tillnärmning ger en lägre gräns på sannolikheten. Mer sofistikerade metoder är möjliga, vilket ger hårdare lägre (och övre) gränser.
  • Provtagning (Monte Carlo) metoder. Den enklaste typen är viktigt provtagning, där vi dra stickprov x P(X), (ovillkorlig) fördelning på de dolda variabler, och då vikten av de prover av deras sannolikhet, P(y|x), där y är bevis. En mer effektiv metod i höga dimensioner är kallad Markov Chain Monte Carlo (MCMC), och ingår som särskilda fall Gibbs sampling och Metropolis-Hasting algoritm.
  • “Loopy tro reproduktionsmateriel”. Detta innebär att Pearl ‘ s algoritm för att den ursprungliga grafen, även om det har slingor (oplanerade cykler). I teorin, då är det risk för dubbelräkning, men Yair Weiss och andra har visat att det i vissa fall (t ex, en enda slinga), händelser räknas två “lika”, och därmed “avbryt” för att ge rätt svar. Tro förökning motsvarar exakt inferens om en modifierad graf, som kallas den allmänna täcka eller oförpackade/ beräkning träd, som har samma lokal topologi som den ursprungliga grafen. Detta är samma som Bethe och hålighet/TAP metoder och statistisk fysik. Därför att det finns ett djupt samband mellan tro förökning och variational metoder att människor är för närvarande utreder.
  • Avgränsas cutset luftkonditionering. Genom att instansieras delmängder av variabler, kan vi bryta slingor i diagrammet. Tyvärr, när cutset är stor, detta är mycket långsam. Genom att instansieras endast en undergrupp av värden av cutset, kan vi beräkna undre gränser på de sannolikheter som är av intresse. Alternativt, kan vi prova cutsets gemensamt, en teknik som kallas block Gibbs sampling.
  • Parametrisk approximativa metoder. Dessa uttrycker den mellanliggande summands i en enklare form, exempelvis, genom tillnärmning av dem som en produkt av mindre faktorer. “Minibuckets” och Boyen-Koller algoritm för att hamna i denna kategori.

Ungefärliga slutledning är ett stort ämne: se referenser för mer information.

Inferens i DBNs

Den allmänna slutsatsen problem för DBNs är att beräkna P(X(t0) | y(:, t1:t2)), där X(i,t) representerar jag’e dolda variabel i tid och t Y(:,t1:t2) representerar alla bevis mellan tidpunkterna t1 och t2. (Faktum är att vi ofta också vill beräkna gemensamma distributioner av variabler över en eller flera tid slcies.) Det finns flera särskilda fall av intresse, illustreras nedan. Pilen visar t0: det är X(t0) som vi försöker att uppskatta. De skuggade regionen visar t1:t2, tillgängliga data.

24

Här är ett enkelt exempel på inferens i en LDS. Betrakta en partikel rör sig i planet vid konstant hastighet föremål för slumpmässiga störningar i dess bana. Den nya positionen (x1, x2) är den gamla position plus velocity (dx1, dx2) plus buller w.

[ x1(t) ] = [1 0 1 0] [ x1(t-1) ] + [ wx1 ]
[ x2(t) ] [0 1 0 1] [ x2(t-1) ] [ wx2 ]
[ dx1(t) ] [0 0 1 0] [ dx1(t-1) ] [ wdx1 ]
[ dx2(t) ] [0 0 0 1] [ dx2(t-1) ] [ wdx2 ]

Vi antar att vi bara följer partikelns position.

[ y1(t) ] = [1 0 0 0] [ x1(t) ] + [ vx1 ]
[ y2(t) ] [0 1 0 0] [ x2(t) ] [ vx2 ]
[ dx1(t) ] 
[ dx2(t) ]

Antag att vi börjar på position (10,10) flytta till höger med hastigheten (1,0). Vi tog prov en slumpmässig bana längd 15. Här nedan visar vi de filtrerade och jämnas banor.

2526

Mean squared error filtrerad uppskattning är 4,9; för den utjämnade uppskattar att det är 3.2. Inte bara är den utjämnade uppskattning bättre, men vi vet att det är bättre, som illustreras av mindre osäkerhet ellipser, detta kan hjälpa till exempel, data association problem. Notera hur den utjämnade ellipser är större i ändarna, eftersom dessa punkter har sett mindre data. Tänk också på hur snabbt den filtrerade ellipser nå sina steady-state (Ricatti) värden. (Se min Kalman filter toolbox för mer information.)

Att LÄRA sig

Man måste ange två saker för att beskriva en BN: diagrammet topologi (struktur) och parametrarna för varje CPD. Det är möjligt att lära sig båda av dessa data. Men att lära struktur är mycket svårare än att lära sig parametrar. Också, lärande, när några av de noder som är dolda, eller vi har data saknas, är mycket svårare än när allt är observerade. Detta ger upphov till 4 fall:

 - Struktur Observerbarhet Metod
---------------------------------------------
Känd Full Maximum Likelihood Estimation
Känd Delvis EM (eller lutning uppstigning)
Okänt Full Sökning genom modellen utrymme 
Okänd Delvis EM + sökning genom modellen utrymme 

Känd struktur, full observerbarhet

Vi antar att målet för lärande i detta fall är att hitta värden för de parametrar för varje CPD som maximerar sannolikheten för att den utbildning data, som innehåller N fall (som antas vara oberoende). Den normaliserade log-sannolikheten för att den utbildning som D är en summa av termer, en för varje nod:

27
Vi ser att log-likelihood poäng funktion bryts ned enligt den struktur av grafen, och därmed kan vi maximera bidraget till log-sannolikheten för varje nod självständigt (förutsatt att parametrarna i varje nod är oberoende av andra noder).

Överväga att beräkna den betingade Sannolikheten Tabell för W-nod. Om vi har en uppsättning av data utbildning, vi kan bara räkna antalet gånger gräset är blött när det regnar och sprinler är på N(W=1,S=1,R=1), antal gånger gräset är blött när det regnar och sprinkler är mindre, N(W=1,S=0,R=1), etc. Med tanke på dessa punkter (som är tillräcklig statistik), kan vi hitta Maximum Likelihood Skattningen av CPT enligt följande:

28

där nämnaren är N(S=s,R=r) = N(W=0,S=s,R=r) + N(W=1,S=s,R=r). Alltså att “lära sig” bara belopp för att räkna (i fall av multinomial distributioner). För Gaussian noder, kan vi beräkna provets medelvärde och varians, och använda linjär regression för att uppskatta vikten matris. För andra typer av distributioner, mer komplicerade förfaranden som är nödvändiga.

Som är väl känt från HMM litteratur, ML-skattningar av katodstrålerör för färgtelevisionsapparater är benägna att glesa data problem, som kan lösas genom att använda (blandningar) Dirichlet priors (pseudo räknas). Detta resulterar i en Maximum A Posteriori (KARTA) uppskattning. För Gaussians, kan vi använda en Wishart före, etc.

Känd struktur, delvis observerbarhet

När några av de noder som är dolda, kan vi använda EM (Förväntan Maximering) algoritm för att hitta ett (lokalt) optimal Maximum Likelihood Skattningen av parametrarna. Den grundläggande tanken bakom dem är att, om vi visste att värdena för alla noder, lärande (M steg) skulle vara lätt, som vi såg ovan. Så i den E steg, vi beräkna de förväntade värdena av alla noder med hjälp av en slutledning algoritm, och sedan behandla dessa förväntade värden som om de var observerade (distributioner). Till exempel, i fallet med W nod, vi ersätta den observerade räknas av händelser med antalet gånger vi förväntar oss att se varje händelse:

P(W=w|S=s,R=r) = E N(W=w,S=s,R=r) / E N(S=s,R=r)

där E N(x) är den förväntade antalet gånger händelsen x förekommer i hela utbildning som, med tanke på den nuvarande gissa av parametrar. Dessa förväntas räknas kan beräknas enligt följande

E N(.) = E sum_k jag(. | D(k)) = sum_k P(. | D(k))

där jag(x | D(k)) är en indikator funktion som är 1 händelse om x inträffar i utbildning fallet k och 0 annars.

Med tanke på den förväntade räknas, vi maximera parametrar, och sedan recompute den förväntade räknas, etc. Denna iterativa förfarandet är garanterad att konvergera till ett lokalt maximum av sannolikheten yta. Det är också möjligt att göra gradient uppstigning på sannolikheten yta (gradient uttryck innebär också att den förväntade räknas), men EM är vanligtvis snabbare (eftersom den använder den naturliga lutning) och enklare (eftersom inget steg parametern storlek och tar hand om parameter begränsningar (till exempel “rader” av CPT med att summera till en) automatiskt). I alla fall, vi ser än när noderna är dold, slutledning blir en subrutin som anropas av den lärande förfarande, och därför snabbt slutledning algoritmer är avgörande.

Okänd struktur, full observerbarhet

Vi börjar med att diskutera poäng funktion som vi använder för att välja modeller; vi sedan diskutera algoritmer som försöker att optimera denna funktion under loppet av modeller, och slutligen undersöka sina beräkningar och prov komplexitet.

objektiva funktion används för model selection

Den högsta sannolikheten för modellen kommer att vara en komplett graf, eftersom detta har det största antalet parametrar, och därmed kan passa för de uppgifter de bästa. En väl principfast sätt att undvika denna typ av över-montering är att sätta ett tidigare modeller, med angivande av att vi föredrar glesa modeller. Sedan, av Bayes’ regel, KORT modell är den som maximerar

29
Ta loggar, finner vi

30
, där c = – \log \Pr(D) är en konstant som är oberoende av G.

Effekten av strukturen innan P(G) är ekvivalent med att bestraffa alltför komplexa modeller. Detta är dock inte absolut nödvändigt, eftersom den marginella sannolikheten sikt

P(D|G) = \int_{\theta} P(D|G, \theta)
har en liknande effekt av att bestraffa modeller med för många parametrar (detta är känt som Occam ‘ s razor).

sökalgoritmer för att hitta den bästa modell

Målet struktur för lärande är att lära sig en dag (riktad acyklisk graf) som bäst förklarar data. Detta är ett NP-svårt problem, eftersom det i dag är på N variabler är super-exponentiellt i N. (Det är ingen sluten form formel för detta, men för att ge dig en idé, det finns 543 dags på 4 noder och O(10^18) dags på 10 noder.)

Om vi vet beställning av noder, livet blir så mycket enklare, eftersom vi kan lära oss moderbolagets ställ för varje nod oberoende (eftersom betyg är nedbrytbart), och vi behöver inte bekymra dig om acyclicity begränsningar. För varje nod finns det på de flesta

\sum_{k=0}^n \valet{n}{k} = 2^n

uppsättningar av möjliga föräldrar för varje nod, som kan ordnas i ett gitter som visas nedan för n=4. Problemet är att hitta den högsta poäng av alla led i detta gitter.

31
Det finns tre uppenbara sätt att söka denna graf: nerifrån och upp, uppifrån och ner, eller mitt ute. I bottom-up-strategi, vi startar vid botten av gallret, och utvärdera betyg på alla punkter på varje successiv nivå. Vi måste bestämma oss för om vinster i betyg produceras av en större förälder ställa är `värt det”. Det vanliga tillvägagångssättet i reconstructibility analys (RA) gemenskapen använder sig av det faktum att \chi^2(X,Y) \ca I(X,Y) N \ln(4), där N är antalet prover och jag(X,Y) är mutual information (MI) mellan X och Y. Därför kan vi använda en \chi^2-test för att avgöra om en ökning i MI betyg är statistiskt signifikant. (Detta ger oss också någon form av förtroende mått på de kopplingar som vi lär.) Alternativt kan vi använda en BIC betyg.

Naturligtvis, om vi inte vet om vi har uppnått den högsta möjliga poäng, vi vet inte när det ska sluta söka, och därför måste vi utvärdera alla punkter i gittret (även om vi uppenbarligen kan använda branch-and-bound). För stora n, detta är beräkningsmässigt omöjligt, så en vanlig metod är att bara söka upp till nivå K (dvs, ta en gräns för det maximala antalet föräldrar i varje nod), vilket tar O(n ^ K) tid.

Det självklara sättet att undvika den exponentiella kostnad (och behovet av en bunden, K) är att använda tumregler för att undvika att pröva alla möjliga undergrupper. (I själva verket, vi måste använda heuristik av något slag, eftersom problemet för lärande optimala strukturen är NP-svårt \cite{Chickering95}.) En strategi i RA, ram, som kallas Extended Beroende Analys (EDA) \cite{Conant88}, är som följer. Börja med att utvärdera alla delmängder av storlek på upp till två, hålla alla de med betydande (i \chi^2 mening) MI med målet nod, och tar unionen av den resulterande uppsättningen som den uppsättning av föräldrar.

Nackdelen med denna giriga teknik är att det inte kommer att hitta en uppsättning av föräldrar, om någon delmängd av storlek två har betydande MI med målvariabel. Dock, en Monte Carlo-simulering i \cite{Conant88} visar att de flesta slumpmässiga relationer har den här egenskapen. Dessutom mycket beroende av varandra uppsättningar av föräldrar (som kan misslyckas parvisa MI-test) bryter mot den kausala oberoende antagande, som är nödvändiga för att motivera användningen av noisy-ELLER och liknande CPDs.

En alternativ teknik, populära i UAI gemenskapen, är att börja med en första gissning av modellen struktur (dvs, vid en viss punkt i gallret), och sedan utföra lokal sökning, dvs, utvärdera betyg av närliggande punkter i gittret, och flytta till den bästa sådan punkt, tills vi når ett lokalt optimum. Vi kan använda flera omstarter för att försöka hitta den globala optimal, och att lära sig en ensemble av modeller. Observera att, i delvis observerbara fallet, måste vi ha en första gissning av den modell för att uppskatta värdena för de gömda noder, och därmed den (förväntade) värdering av varje modell, som börjar med den helt skild modell (dvs, på undersidan av gallret) skulle vara en dålig idé, eftersom det skulle leda till en dålig uppskattning.

Okänd struktur, delvis observerbarhet

Slutligen kommer vi till det svåraste fallet för alla, där strukturen är okänd och det finns dolda variabler och/eller uppgifter som saknas. I detta fall, för att beräkna den Bayesianska betyg, vi måste marginalisera de dolda noder samt de parametrar. Eftersom detta är oftast svårbehandlad, är det vanligt att usean asymptotiska tillnärmning till den bakre kallas BIC (Bayesian Information Criterion), som definieras enligt följande:

\log \Pr(D|G) \cirka \log \Pr(D|G, \hat{\Theta}_G) - \frac{\log N}{2} \#G

där N är antalet prover \hat{\Theta}_G är ML-skattning av parametrar och #G är den dimension av modellen. (I fullt observerbar fall dimension för en modell antalet fria parametrar. I en modell med dolda variabler, kan det vara mindre än detta.) Den första termen är bara sannolikheten för och den andra termen är ett straff för modell komplexitet. (BIC betyg är identiskt med ett Minimum Description Length (MDL) poäng.)

Även om BIC betyg bryts ned till ett belopp av lokala villkor, en per nod, lokal sökning är fortfarande dyra, eftersom vi måste köra EM i varje steg för att beräkna \hat{\Theta}. En alternativ metod är att göra den lokala sök steg insidan av M steg av EM – detta kallas Structureal EM, och bevisat konvergerar mot ett lokalt maximum i BIC betyg (Friedman, 1997).

Uppfinna nya dolda noder

Så långt, struktur lärande har medfört att hitta rätt anslutning mellan befintliga noder. En mer intressant problem är att uppfinna dolda noder på efterfrågan. Dolda noder kan göra en modell mycket mer kompakt, som vi ser nedan.

33

(a) BN med en dolda variabel H. (b) Den enklaste nätverk som kan fånga samma fördelning utan att använda en dold variabel (som skapats med hjälp av arc återföring och nod eliminering). Om H är binärt och de andra noderna är trinary, och vi tar fullt katodstrålerör för färgtelevisionsapparater det första nätverket har 45 oberoende parametrar, och den andra har 708.

Det vanliga tillvägagångssättet är att fortsätta att lägga till dolda noder i taget, till en viss del av nätverket (se nedan), som utför struktur lärande vid varje steg, tills poäng sjunker. Ett problem är att välja kardinalitet (antal möjliga värden) för den dolda noden och dess typ av CPD. Ett annat problem är att välja var du ska lägga till den nya dolda noden. Det är ingen idé att göra det till ett barn, eftersom gömda barn alltid kan vara marginaliserade bort, så vi måste hitta en befintlig nod som behöver en ny förälder, när den nuvarande uppsättning av möjliga föräldrar är inte tillräckligt.

\cite{Ramachandran98} använd följande heuristik för att hitta noder som behöver nya föräldrar: de anser att en bullrig-ELLER nod som ligger nästan alltid på, även om dess icke-läckage föräldrar är borta, som en indikator på att det är en saknad förälder. Att generalisera denna teknik utöver bullriga-ORs är en intressant öppna problem. En strategi skulle kunna vara att undersöka H(X|Pa(X)): om detta är mycket hög, det innebär att de nuvarande föräldrar är otillräckliga för att `förklara” den kvarstående entropi; om Pa(X) är den bästa (i BIC eller \chi^2 mening) uppsättning av föräldrar som vi har kunnat hitta i den nuvarande modellen, att det tyder på att vi behöver för att skapa en ny nod och lägg till det att Pa(X).

En enkel heuristik för att ha uppfunnit dolda noder i fall av DBNs är att kolla om Markov egendom kränks för en viss nod. Om så är fallet, det tyder på att vi behöver anslutningar till skivor längre tillbaka i tiden. Dvs, vi kan lägga till nya lag variabler och ansluta till dem.

Naturligtvis tolka den `mening” av dolda noder är alltid knepigt, särskilt eftersom de ofta är oidentifierbara, t ex, kan vi ofta växla den tolkning av sant och falskt staterna (antar för enkelhets skull att den dolda noden är binär), under förutsättning att vi också kasta om de parametrar som på ett lämpligt sätt. (Symmetrier som detta är en orsak till att flera maxima i sannolikheten att ytan.)

läsa mer om learning

Följande är bra tutorial artiklar.

beslutsteori

Det sägs ofta att “beslutsteori = Sannolikhetsteori + Utility Theory”. Vi har som beskrivs ovan hur vi kan modellera gemensamma sannolikhetsfördelningar i ett kompakt sätt med hjälp av glesa grafer för att återspegla villkorligt oberoende relationer. Det är också möjligt att bryta ned multi-attribute utility fungerar på ett liknande sätt: vi skapa en nod för varje term i summan, som har som föräldrar alla egenskaper (variabler) som det beror på; typiskt, verktyg nod(s) har åtgärder nod(s) som föräldrar, eftersom verktyget beror både på tillståndet i världen och de åtgärder vi utför. Den resulterande grafen kallas det påverkar diagrammet. I princip kan vi sedan använda inflytande diagram för att beräkna den optimala (sekvens) åtgärd(er) för att utföra så som att maximimize förväntade nyttan, även om detta är beräkningsmässigt intractible för alla utom de allra minsta problem.

Klassisk reglerteknik är mestadels sysslar med särskilda fall där den grafiska modellen är en Linjära Dynamiska System och nyttofunktionen är negativa kvadratiska förlust, exempelvis, anser en missil spåra ett flygplan: dess mål är att minimera de kvadrerade avståndet mellan sig själv och målet. När verktyget funktion och/eller systemet blir mer komplicerat, traditionella metoder för att bryta ner och en har att använda reinforcement learning för att hitta den optimala politiken (kartläggning från staterna till åtgärder).

Program

Den mest använda Bayesianska Nät är utan tvekan de som är inbäddade i Microsofts produkter, inklusive svarsguiden av Office 95, Office-Assistenten (den studsiga gem kille) Office 97 och över 30 Teknisk Support Felsökare.

BNs ursprungligen uppstod ur ett försök att lägga till sannolikheter för att expert system, och detta är fortfarande den vanligaste användningen för BNs. Ett berömt exempel är QMR-DT, ett beslut-teoretisk omformulering av den Snabba Medicinska Referens (QMR) modell.

34

Här är det översta lagret representerar dold sjukdom noder, och det understa lagret representerar observerade symptom noder. Målet är att härleda den bakre sannolikheten för varje sjukdom med tanke på alla symtom (som kan vara närvarande, frånvarande eller okänd). QMR-DT är så tätt ansluten exakt inferens är omöjligt. Olika approximativa metoder har använts, inklusive provtagning, variational och loopy tro förökning.

En annan intressant delta program är Vista – systemet, som utvecklats av Eric Horvitz. Vista system är ett beslut-teoretiska system som har använts vid NASA Mission Control Center i Houston i flera år. Systemet använder Bayesianska nätverk för att tolka live telemetri och ger råd om sannolikheten för alternativa misslyckanden av rymdfärjans system för framdrivning. Det anser även tid kriticitet och rekommenderar åtgärder av de högsta förväntade nyttan. Vista system använder även beslut-teoretiska metoder för att styra visning av information för att dynamiskt identifiera den viktigaste informationen för att markera. Horvitz har gått på att försök att tillämpa liknande teknik för Microsoft-produkter, till exempel Lumiere projektet.

Särskilda fall av BNs var oberoende uppfanns av många olika grupper, för användning i exempelvis genetik (linkage analysis), taligenkänning (HMMs), viltspår (Kalman fitering), komprimering av data (densitet uppskattning) och kodning (turbocodes), etc.

För exempel på andra program, se särskild fråga av Proc. ACM 38(3), 1995, och Microsoft Beslut Teori Grupp sida.

Program till biologi

Detta är en av de hetaste områden. För en översikt, se

 Rekommenderas inledande behandlingen

Böcker

I omvänd kronologisk ordning.

  • Daphne Koller och Nir Friedman, “Probabilistisk grafiska modeller: principer och tekniker”, MIT Press 2009
  • Adnan Darwiche, “Modellering och resonemang med Bayesianska nätverk”, Cambridge 2009
  • F. V. Jensen. “Bayesianska Nätverk och Beslut Graphs”. Springer. 2001.
    Förmodligen den bästa inledande boken finns.
  • D. Edwards. “Introduktion till Grafisk Modellering”, 2: a uppl. Springer-Verlag. 2000.
    Bra behandling av oplanerade grafiska modeller från ett statistiskt perspektiv.
  • J. Pearl. “Kausalitet”. Cambridge. 2000.
    Den definitiva boken om att använda kausala DAG modellering.
  • R. G. Cowell, A. P. Dawid, S. L. Lauritzen och D. J. Spiegelhalter. “Probabilistisk Nätverk och Expert Systems”. Springer-Verlag. 1999.
    Förmodligen den bästa boken som finns, även om behandlingen är begränsad till exakt inferens.
  • M. I. Jordan (red). “Lärande i Grafiska Modeller”. MIT Press. 1998.
    Lös samling av artiklar om lärande, många med anknytning till grafiska modeller. En av de få böcker att diskutera ungefärliga slutledning.
  • B. Frey. “Grafiska modeller för lärande och digital kommunikation”, MIT Press. 1998.
    Diskuterar mönster erkännande och turbocodes hjälp (riktad) grafiska modeller.

 

  • E. Castillo och J. M. Gutierrez och A. S. Hadi. “Expertsystem och probabilistiska modeller nätverk”. Springer-Verlag, 1997.
    den spanska versionen finns tillgänglig online gratis.
  • F. Jensen. “En introduktion till Bayesianska Nätverk”. UCL Press. 1996. Slut på förlaget.
    Ersatt av hans bok från 2001.
  • S. Lauritzen. “Grafiska Modeller”, Oxford. 1996.
    Den slutgiltiga matematisk utläggning av teori av grafiska modeller.
  • S. Russell och P. Norvig. “Artificial Intelligence: A Modern Approach”. Prentice Hall. 1995.
    Populära grundutbildning lärobok som innehåller en läsbar kapitel om riktad grafiska modeller.
  • J. Whittaker. “Grafiska Modeller i Tillämpad Multivariat Statistik”, Wiley. 1990.
    Detta är den första bok utgiven på grafisk modellering ur ett statistiskt perspektiv.
  • R. Neapoliton. “Probabilistiska Resonemang i Expert Systems”. John Wiley & Söner. 1990.
  • J. Pearl. “Probabilistiska Resonemang i Intelligenta System: Nätverk av Rimlig Slutledning.” Morgan Kaufmann. 1988.
    Den bok som fick det hela började! En mycket insiktsfull bok, som fortfarande är relevant idag.

översiktsartiklar

Exakt Inferens

Ungefärliga Slutledning

Att Lära sig

DBNs