Bayesiansk nettverk

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Et bayesiansk nettverk, bayesiansk nett, eller en rettet asyklisk grafisk modell er en grafisk modell (eng. graphical model) for sannsynlighet. Den representerer et sett av tilfeldige variabler og deres betingede avhengigheter fremstilt ved hjelp av en rettet asyklisk graf (eng: directed acyclic graph (DAG)). 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. I fø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 et spesielt sett av verdier etter nodens foreldre variabler, og gir sannsynligheten for variabelen representert i noden. For eksempel, hvis foreldrenodene er m boolske variabler så kan sannsynlighetsfunksjonen representeres i en tabell av 2^m oppføringer. Det er en for hver av de 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 (eng: Dynamic Bayesian network). Generalisering av bayesianske nettverk som kan representere og løse beslutningsproblemer ved usikkerhet, kalles innflytelsesdiagrammer.

Definisjoner og konsepter[rediger | rediger kilde]

Det finnes flere ekvivalente definisjoner av bayesianske nettverk. For de følgende definisjonene la G = (V,E) være en rettet asyklisk graf (eng: DAG), og la X = (Xv)vV være et sett av tilfeldige variabler indeksert av V.

Factorization definition[rediger | rediger kilde]

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]

 p (x) = \prod_{v \in V} p \big(x_v \,\big|\,  x_{\operatorname{pa}(v)} \big)

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

For et hvilket som helst sett av tilfeldige variabler, er sannsynligheten til hvilket som helst medlem av felles distribusjon (eng: joint distribution) bli kalkulert ut i fra betingede sannsynligheter ved å bruke kjede regelen (eng: chain rule) som følger:[1]

\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:

\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 X_j\, which is a parent of  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[rediger | rediger kilde]

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] :

 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 settet av etterkommere av v.

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

\mathrm  P(X_v=x_v \mid  X_i=x_i for hver X_i\, som ikke er en etterkommer av  X_v\, ) = P(X_v=x_v \mid X_j=x_j for hver X_j\, som er foreldre av  X_v\, )

Legg merke til at settet av foreldre er et subsett av settet av ikke-etterkommere fordi grafen er asyklisk.

Utvikling av bayesianske nettverk[rediger | rediger kilde]

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 teppe[rediger | rediger kilde]

Markov teppet (eng. Markov blanket)til en node er nodens sett 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[rediger | rediger kilde]

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) (dvs, en sti som kan gå i begge retninger) fra node u til v. Da er P sagt å være d-separert ved et sett av 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:

X_u \perp\!\!\!\perp X_v \, | \, X_Z

hvor Z er et sett der d-separerer u og v. (Markov teppet er det minimale settet av noder som d-separerer node v fra alle andre noder).

Kausale nettverk[rediger | rediger kilde]

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:


 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[rediger | rediger kilde]

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:

\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:

 \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})}
 = \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. [5] Den sier at dersom et sett 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. Sett som tilfredsstiller bakdør kriteriet kalles "tilstrekkelig" eller "tillatt." For eksempel settet 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 sett 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. (se Simpson's paradoks)

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 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 10*2^3 = 80 verdier.

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


Referanser[rediger | rediger kilde]

  1. ^ a b Stuart Russel & Peter Norvig (2003): Artificial Intelligence - a modern approach, ISBN: 0-13-080302-2, Pearson Education (side 496)
  2. ^ a b 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.