Bayesiansk nettverk

Et bayesiansk nettverk, bayesiansk nett, eller en rettet asyklisk grafisk modell er en grafisk modell for sannsynlighet. Den representerer en mengde av tilfeldige variabler og deres betingede avhengigheter fremstilt ved hjelp av en rettet asyklisk graf. Et praktisk eksempel på en bayesiansk nettverk kan være en representasjon av sannsynlighetsfordelingen mellom sykdommer og relaterte symptomer. Nettverket kan, gitt ulike symptomer, kalkulere sannsynligheten for at en person har en sykdom.

Formelt sett er et bayesiansk nettverk en rettet asyklisk graf der nodene representerer tilfeldige variabler. Ifølge Bayes teori kan variablene være observerbare kvantiteter, latente variabler, ukjente parameter eller hypoteser. Kantene i grafen representerer betingede avhengigheter, representert av betinget sannsynlighet. Noder som ikke er knyttet sammen representerer variabler som er betinget uavhengige av hverandre. Hver node er tilknyttet en sannsynlighetsfunksjon som tar som input en spesielt mengde av verdier etter nodens foreldre variabler, og gir sannsynligheten for variabelen representert i noden. For eksempel, hvis foreldrenodene er ${\displaystyle m}$ boolske variabler så kan sannsynlighetsfunksjonen representeres i en tabell av ${\displaystyle 2^{m}}$ oppføringer. Det er en for hver av de ${\displaystyle 2^{m}}$ mulige kombinasjonene av foreldrenodenes mulighet for å være sann eller falsk.

Det finnes effektive algoritmer som utfører inferens og læring i bayesianske nettverk. Bayesianske nettverk som modellerer sekvenser av variabler (eks telesignaler eller protein sekvenser) blir kalt dynamiske bayesianske nettverk. Generalisering av bayesianske nettverk som kan representere og løse beslutningsproblemer ved usikkerhet, kalles innflytelsesdiagrammer.

Definisjoner og konsepter

Det finnes flere ekvivalente definisjoner av bayesianske nettverk. For de følgende definisjonene la G = (V,E) være en rettet asyklisk graf, og la X = (X_v)_{v ∈ V} være en mengde av tilfeldige variabler indeksert av V.

Factorization definition

X er et bayesiansk nettverk med hensyn til G hvis dens felles sannsynlighet tetthetsfunksjonkan bli beskrevet som et produkt av de individuelle tetthetsfunksjonene, betinget av deres foreldre variabler:^[1]

${\displaystyle p(x)=\prod _{v\in V}p{\big (}x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}{\big )}}$

hvor pa(v) er mengden av foreldre til v (eks de toppunkter som peker direkte til v via en singel kant).

For en hvilket som helst mengde av tilfeldige variabler, er sannsynligheten til hvilket som helst medlem av felles distribusjon bli kalkulert ut i fra betingede sannsynligheter ved å bruke kjerneregelen som følger:^[1]

${\displaystyle \mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} (X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n})}$

Sammenlign denne med definisjonen over, kan det bli skrevet som:

${\displaystyle \mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} (X_{v}=x_{v}\mid X_{j}=x_{j}}$ for each ${\displaystyle X_{j}\,}$ which is a parent of ${\displaystyle X_{v}\,)}$

Forskjellen mellom de to uttrykkene er den kondisjonelle uavhengigheten til variablene fra hvilken som helst av deres ikke-etterkommere, gitt verdiene til deres foreldrevariabler.

Lokal Markov egenskap

X er et bayesiansk nettverk med hensyn til G hvis det oppfyller den lokale Markov egenskapen. Det vil si at hver variabel er betinget uavhengig av dens ikke-etterkommere gitt at dens foreldre variabler som følger^[2] :

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {de} (v)}\,|\,X_{\operatorname {pa} (v)}\quad {\text{for all }}v\in V}$

hvor de(v) er mengden av etterkommere av v.

Dette kan også bli uttrykt på en form som er maken til den første definisjonen:

${\displaystyle \mathrm {P} (X_{v}=x_{v}\mid X_{i}=x_{i}}$ for hver ${\displaystyle X_{i}\,}$ som ikke er en etterkommer av ${\displaystyle X_{v}\,)=P(X_{v}=x_{v}\mid X_{j}=x_{j}}$ for hver ${\displaystyle X_{j}\,}$ som er foreldre av ${\displaystyle X_{v}\,)}$

Legg merke til at mengden av foreldre er en delmengde av mengden av ikke-etterkommere fordi grafen er asyklisk.

Utvikling av bayesianske nettverk

For å utvikle et bayesiansk nettverk må vi ofte først utvikle en DAG G slik at vi tror X oppfyller den lokale Markov egenskapen med hensyn til G. Noen ganger blir dette gjort ved å lage en kausal DAG. Dermed fastslår vi den betingede sannsynlighets distribusjon til hver variabel, gitt dens foreldre i G. I mange tilfeller, spesielt i de tilfellene hvor variablene er diskrete, hvis vi definerer felles distribusjon av X til å være produktet av disse betingede distribusjonene, så er X et bayesiansk nettverk med hensyn til G.^[3]

Markov-teppet

Markov-teppet til en node er nodens mengde av nabonoder: dens foreldre, barn og andre foreldre av dens barn. X er et bayesiansk nettverk med hensyn til G hvis hver node er betinget uavhengig av alle andre noder i nettverket, gitt dens Markov teppe^[2].

d-separasjon

Denne definisjonen kan bli laget mer generell ved å definere d-separasjonen til to noder, hvor d står for avhengighet (depencence).^[4] La P være et spor(trail) (det vil si, en sti som kan gå i begge retninger) fra node u til v. Da er P sagt å være d-separert ved en mengde noder Z hvis og bare hvis (minst) en av de følgende forhold gjelder: 1.P inneholder en kjede, i → m →j, slik at den midterste noden m er i Z, 2.P inneholder en kjede, i ← m ←j, slik at den midterste noden m er i Z, 3.P inneholder en gaffel(fork), i ← m → j, slik at den midterste noden m er i Z, eller 4.P inneholder en invertert gaffel (eller en collider), i → m ← j, slik at den midterste noden m ikke er i Z og ingen etterkommere av m er i Z. Dermed er u og v sagt å være d-separert av Z hvis alle stier mellom dem er d-separert. Hvis u og v ikke er d-separert, kalles det d-knyttet(d-connected).

X er et bayesiansk nettverk med hensyn til G, hvis for hvilke som helst to noder u, v:

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\,|\,X_{Z}}$

hvor Z er en mengde der d separerer u og v. (Markov-teppet er den minimale mengden av noder som d-separerer node v fra alle andre noder).

Kausale nettverk

Selv om bayesianske nettverk ofte brukes til å representere kausale forhold, behøver det ikke være slik: en rettet kant fra u til v krever ikke at Xv er kausalt avhengig av Xu. Dette blir bevist av fakta at de bayesianske nettverk grafene:

${\displaystyle a\longrightarrow b\longrightarrow c\qquad {\text{and}}\qquad a\longleftarrow b\longleftarrow c}$

er like: det vil si de gir nøyaktig de samme kondisjonelle uavhengighetskravene.

Et kausalt nettverk er et bayesiansk nettverk med et eksplisitt krav at forholdene er kausale. Den ytterlige semantikken til kausale nettverk spesifiserer at hvis en node X er aktivt årsak til å bli i en gitt tilstand x(en handling skrevet som do(X=x=)), så sannsynlighetstetthetsfunksjonen forandrer seg til det ene nettverket. Dette oppnås ved å kutte lenkene fra X’s foreldre til X, og sette X til den forårsakede verdien x.^[5] Ved å bruke disse semantikkene kan man forutse effekten av ekstern intervensjoner fra data innhentet før intervensjonen.

Eksempel

Et enkelt Bayesiansk nettverk.

Anta at det er to hendelser som kan føre til at gresset blir vått: enten sprinkler er på, eller det regner. Antar også at regnet har en direkte effekt på bruken av sprinkler (nemlig at når det regner, er sprinkleranlegg vanligvis ikke slått på). Denne situasjonen kan modelleres med en Bayesiansk nettverk. Alle tre variablene har to mulige verdier, T (for sann) og F (for usann). Variablene er forkortet til G = Grass våt, S = Sprinkler, og R = Regn.

Den felles sannsynligheten funksjonen er:

${\displaystyle \mathrm {P} (G,S,R)=\mathrm {P} (G|S,R)\mathrm {P} (S|R)\mathrm {P} (R)}$

Modellen kan svare på spørsmål som «Hva er sannsynligheten for at det regner, gitt gresset er vått?» ved hjelp av betinget sannsynlighet formelen og å summere over alle ordensforstyrrelser (nuisance) variabler:

${\displaystyle \mathrm {P} ({\mathit {R}}=T\mid {\mathit {G}}=T)={\frac {\mathrm {P} ({\mathit {G}}=T,{\mathit {R}}=T)}{\mathrm {P} ({\mathit {G}}=T)}}={\frac {\sum _{{\mathit {S}}\in \{T,F\}}\mathrm {P} ({\mathit {G}}=T,{\mathit {S}},{\mathit {R}}=T)}{\sum _{{\mathit {S}},{\mathit {R}}\in \{T,F\}}\mathrm {P} ({\mathit {G}}=T,{\mathit {S}},{\mathit {R}})}}}$

${\displaystyle ={\frac {(0.99\times 0.01\times 0.2=0.00198_{TTT})+(0.8\times 0.99\times 0.2=0.1584_{TFT})}{0.00198_{TTT}+0.288_{TTF}+0.1584_{TFT}+0_{TFF}}}\approx 35.77\%.}$

I eksempelet påpekes teller eksplisitt. Den felles sannsynlighetsfunksjonen brukt til å beregne hver iterasjon i summeringsfunksjonen. I telleren marginaliseres S, og i nevneren marginaliseres S og R.

Dersom, på den annen side, vi ønsker å svare på et intervensjonsspørsmål: «Hva er sannsynligheten for at det skulle regne, gitt at vi våte gresset» svaret ville bli underlagt etter intervensjonen felles distribusjon funksjonen P (S, R | gjør (G = T)) = P (S | R) P (R) som er oppnådd ved å fjerne den faktoren P (G | S, R) fra pre-intervensjon distribusjon. Som forventet, er sannsynligheten for regn upåvirket av handlingen: P (R | gjør (G = T)) = P (R).

Hvis vi ønsker å forutsi effekten av å skru sprinklene på, har vi P (R, G | gjør (S = T)) = P (R) P (G | R, S = T) med begrepet P (S = T | R) fjernet. Dette viser at handlingen har en effekt på gresset, men ikke på regnet.

Disse spådommer kan kanskje ikke være gjennomførbare når noen av variablene er uobservert, slik som i de fleste politiske evalueringsproblemer. Effekten av handlingen gjør(x) kan fortsatt bli spådd, men når et kriterium som heter «back-door» er oppfylt. Den sier at dersom en mengde Z av noder kan observeres at d-skiller (eller blokker) alle bakdørstier fra X til Y og P (Y, Z | gjøre (x)) = P (Y, Z, X = x) / P (X = x | Z). En bakdør bane er en som slutter med en pil i X. Mengder som tilfredsstiller bakdørkriteriet kalles «tilstrekkelig» eller «tillatt.» For eksempel mengden Z = R er tillatt for å forutsi effekten av S = T på G, fordi R d-skiller (bare) bakdør banen S ← R → G. Men hvis S ikke er observert, er det ingen andre mengder at d-skiller denne stien og effekten av å skru sprinkler på (S = T) på gresset (G) ikke kan forutsies fra passive observasjoner. Vi sier da at P (G | gjøre (S = T)) er ikke «identifiseres.» Dette gjenspeiler det faktum at med manglende intervensjonsdata kan vi ikke fastslå om de observerte avhengigheten mellom S og G skyldes en årsakssammenheng eller falsk grunn skapt av en felles årsak, R.

Hvis avhengigheter i felles distribusjon er få, kan man ved hjelp av et Bayesiansk nettverk kan spare betydelige mengder maskinminne. For eksempel krever den naive måte å lagre betingede sannsynligheter av 10 to-verdsatt variabler som en tabell lagringsplass for ${\displaystyle 2^{10}=1024}$ verdier. Hvis den lokale fordelinger av ingen variabler avhenger av mer enn 3 overordnede variabler, behøver den Bayesianske nettverksrepresentasjonen kun å lagre maksimalt ${\displaystyle 10*2^{3}=80}$ verdier.

En fordel med Bayesiansk nettverk er at det er intuitivt lettere for et menneske å forstå (en glissen mengde av) direkte avhengigheter og lokale utdelinger over hele felles distribusjon.

Referanser

1. Stuart Russel & Peter Norvig (2003): Artificial Intelligence - a modern approach, ISBN 0-13-080302-2, Pearson Education (side 496)
2. Stuart Russel & Peter Norvig (2003): Artificial Intelligence - a modern approach, ISBN 0-13-080302-2, Pearson Education (side 499)
3. Neapolitan, R.E.,Learning Bayesian Networks, Prentice Hall, Upper Saddle River, NJ, 2004
4. http://www.andrew.cmu.edu/user/scheines/tutor/d-sep.html
5. Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 0-521-77362-8.