HØit

Nr. 1-98

Bayeske nettverk

Steffen Log

I artikkelen, Er Deep Blue intelligent?, i siste nummer av HØit tok jeg utgangspunkt i sjakkkampen mellom datamaskinen Deep Blue og regjerende sjakkmester Garry Kasparov, som sistnevnte tapte, til å komme inn på en rekke sider ved begrepet intelligens. Denne gangen skal vi avgrense oss til programvare som har evnen til å takle usikker kunnskap og resonnering, samt kunne lære av sine erfaringer. Det er en rekke teknikker til disposisjon i denne forbindelse. En rekke artikler i HØit har omhandlet fagfeltet nevrale nettverk. Vi skal ta for oss et annet nettverk: Bayeske nettverk, som i de senere årene har fått sin renessanse.
Artikkelen, som er inspirert av [1], vil starte med ekspertsystemer for så å etterfølges av anvendelser av Bayeske nettverk, kort innføring i sannsynlighetsbegrepet, hva Bayeske nettverk er og for så å avslutte med et praktisk eksempel der tre dataingeniørstudenter har avtalt møte med deres veileder under hovedprosjektet, men to av dem dukker ikke opp til avtalt tid.

Ekspertsystemer

Et eksempel på en ekspert i arbeid er en lege som undersøker en pasient. I førstningen må legen få en oversikt før en diagnose kan stilles. Han/hun vil undersøke pasienten og lese pasientens journal. Eksperten skaffer seg med andre ord en oversikt over verdenen. Når så de nødvendige observasjoner og opplysninger foreligger, kan så eksperten ta sin beslutning. Denne beslutning er ekspertens tolking av verdenen. For pasienten vil det være en foreskriving for behandling.
Når vi har dette i bakhodet, er det ikke overraskende at man i 1960 årene kom på tanken å utvikle spesielle programvarer, såkalte ekspertsystemer, som enkelt sagt er: Putte den kunnskap og erfaring en ekspert sitter inne med inn i en datamaskin. Ideen var at eksperter kunne erstattes av datamaskinsystemer utviklet av verdens ledende ekspertise. Går vi tilbake til legeeksempelet, er det ikke unaturlig å bygge systemer basert på regler av formen, såkalte produksjonsregler,
if betingelse then aksjon (1)

der betingelsen er et logisk uttrykk. (Det er også andre teknikker.) Et regelbasert system består av en kunnskapsbase og et beslutningssystem. Kunnskapsbasen er en samling produksjonsregler og beslutningssystemet kombinerer reglene og observasjoner til å komme opp med konklusjoner om omgivelsene og aksjoner som skal utføres. Denne type system ble svært populære og svært mange er i årenes løp utviklet innenfor et vidt spenn av fagfelt. Et av de mest kjente er MYCIN (1976) til bruk ved bestemmelse av infeksjoner i blodet hos en pasient. Systemet hadde en rekke fasiliteter som at brukeren/legen og systemet kunne kommunisere sammen, dvs brukeren og systemet kunne ha en dialog på engelsk mellom seg. En mer interessant egenskap fra vår synsvinkel er at systemet kunne takle usikker kunnskap og resonnering. Det er den verden en lege jobber i. For eksempel måling av blodtrykk hos en pasient gir ikke eksakt kunnskap fordi målingens verdi må vurderes opp mot pasientens allmenne tilstand, alder osv. MYCIN benyttes seg av sikkerhetsfaktorer (CF) for å fange inn usikker kunnskap. Regelen i (1) vil i MYCINs versjon se slik ut:

if betingelse(CF: a) then aksjon (CF: b) (2)

som sier at dersom betingelsen er oppfylt har den en sikkerhetsfaktor på a og aksjonens avhengighet av betingelsen er gitt ved faktoren b. Sikkerhetsfaktoren for aksjonen vil dermed være Fastsettelse av verdien for a og b er bygd på erfaring og dermed ikke eksakt. Man brukte ikke sannsynlighetsbegrepet direkte til verdisettingen av a og b, men sannsynligheten til en hendelse lå i bunnen for sikkerhetsfaktorene. Det var også bestemte kjøre-/beslutningsregler for bruk av sikkerhetsfaktorer mellom regler. Alt dette høres tilforlatelig ut. Dessverre er det ikke mulig å gjennomføre resonnering under usikkerhet ved hjelp av slike beslutningsregler ved bruk av produksjonsregler. Årsaken ligger i at slike beslutningsregler er kontekstfrie, mens samhørende resonnering under usikkerhet er sensitiv til konteksten som sikkerhetsfaktorene er utviklet i.
I fagfeltet beslutningsteori er klassisk sannsynlighetsteori utvidet til et presist matematisk verktøy til bruk ved rasjonell beslutning, og erfaring viser at eksperter ikke alltid adlyder dette verktøyets regler. Derfor er det blitt hevdet at eksperter ikke er gode ved kvantitativ resonnering under usikkerhet og derfor trenger de støtte fra programvare når beslutninger gjøres.
Normative ekspertsystemer er et alternativ til regelbaserte ekspertsystemer. Begge type systemer forholder seg til gjentatte beslutninger basert på nesten ensartede tilfeller. Normative systemer skiller seg på tre felt fra den andre typen: (a) i stedet for å modellere eksperten, modeller omgivelsene, (b) bruk sannsynlighetsregning og beslutningsteori og (c) erstatt ikke eksperten, men støtt han/henne i stedet slik at systemet og eksperten spiller på lag.
Disse ideer er ikke nye. Allerede i 1960 årene var de i bruk, men så gikk de i dvale før de rundt 1985 fikk fornyet aktualitet. Denne utvikling minner svært mye om den nevrale nettverk har gjennomgått.

Anvendelser av Bayeske nettverk

Som vi skal se senere, gjør også Bayeske nettverk bruk av klassisk sannsynlighetsregning og beslutningsteori. Siden normative systemer og Bayeske nettverk er så beslektet, vil vi ikke skille klart mellom dem.
Vi skal ta med noen praktiske anvendelser:

Datamaskiner

Operativsystemet Windows 95 har inkorporert et slikt nettverk.
VISTA (1995) brukes av NASA ved oppskyting av romfartøy.
Systemer til å gjenoppdage informasjon (1993, 1995).

Maskinsyn

Tolke bilder i CCD-kameraer (1988).
Danne 3D informasjon basert på 2D bilder (1992).
Ved databasert radiografi av hender (1993).

Medisin

Child (1989, 1994) brukes ved å diagnostisere hjertesykdommer.
MUNIN (1989) og Paimlim (1993) brukes til å diagnostisere sykdommer i muskler og nerver.
Pathfinder (1992) brukes ved lymfeknutepatologi.
Swan (1993) til bruk for sukkersyke til å avpasse insulindosen.

Jordbruk

BOBLO (1995) til hjelp ved blodtypebestemmelse av Jersey-kveg.
Et system for kontroll av meldugg på vinterhvete (1995).

Metereologi

Hailfinder (1996) til å forutsi uvær i Colorado.

Kort innføring i sannsynlighetsregning

Vi tar ikke med mer enn det vi har behov for. La A være en stokastisk variabel som representerer en hendelse. Sannsynligheten for at A skal inntreffe skrives P(A). La for eksempel en urne inneholde 3 røde og 2 grønne kuler, dvs i alt 5 kuler. Dersom A står for å trekke en kule fra urnen, så kan A anta verdien rød eller grønn. Sannsynligheten for hvert av disse to tilfellene skriver vi P(A=rød)=3/5 og P(A=grønn)= 2/5 (3)

eller kort

P(A) = (3/5, 2/5).

Dersom vi skal finne sannsynligheten for A og vet at hendelsen B har inntruffet, skriver vi P(A|B). La oss illustrere dette ved å anta at to kuler trekkes etter hverandre fra urnen uten at den første legges tilbake. Dersom vi trekker en grønn kule i det første trekket (B), vil sannsynligheten for så å trekke en rød (A) bli:

P(A=rød |B = grønn) = 3/4

(det er jo fortsatt 3 røde kuler der det totale antall kuler er redusert til 4).
Dersom to hendelser A og B skal inntreffe samtidig, skriver vi P(A^ B). Det kan vises at

P(AB) = P(A|B)P(B) (4)

eller

P(AB) = P(B|A)P(A) (5)

Omforming av (4) gir

P(A|B) = P( A ^ B ) / P( B ) (6)

som videre kan omformes ved hjelp av (5) til

P(A|B) = (P (B | A ) P ( A )) / P(B) (7)

(7) kalles Bayes formel og er et sentralt element i Bayeske nettverk.
Går vi tilbake til situasjonen å trekke to kuler etter hverandre fra urnen, men nå kreves det at den første uttrukne kule legges tilbake før neste trekk gjøres. Dette betyr at informasjonen den første kulen gir, ikke har noen betydning. Vi sier at A og B er uavhengige, og dettes skrives

P(A|B) = P(A) (8)

Bayeske nettverk

La oss ta utgangspunkt i retningsgrafen i figur 1. Vi har tegnet inn enveis linker og samtidig merker vi oss at det ikke er mulig å gå i ring i nettverket, dvs ved å følge linkene blir vi tvunget til å gå framover i grafen. Lar vi videre bokstaven i en node representere en (stokastisk) variabel kan vi knytte sannsynlighet, ofte betegnet visshet, til noden. Figur 1 vil da være et eksempel på et Bayesk nettverk. For å kunne regne ut visshetene i nettverket må følgende vissheter være kjent på forhånd: P(A), P(B), P(C|AB), P(D|B) og P(E|CD).

Figur 1

Går vi for eksempel fra node B til node D i figur 1, ser vi at D først kan «inntreffe» når B har «inntruffet». Dette er helt i tråd med formuleringen i (1). Derfor ser vi at Bayeske nettverk gir årsakssammenhengen mellom de variable som inngår.
Sammenlikner vi (6) og (8), ser vi at i (6) har B innflytelse, men ikke i (8). Det er viktig i et Bayesk nettverk å vite om en variabel har innflytelse på en annen variabel eller ei. Et sentralt begrep i denne forbindelse er d-atskilt (‘direction-dependent separation’). Vi skal illustrere begrepet ved å se på tre sentrale nettverksstrukturer.

• Serieforbindelse
Figur 2 viser et eksempel. Dersom det foreligger visshet om A, kan den formidles via B og C til D dersom ikke visshet om B eller C foreligger. Foreligger det derimot visshet om B eller C, blir ikke vissheten om A formidlet til D, dvs A og D er d-atskilt.

Figur 2

• Divergerende forbindelse
Figur 3 viser et eksempel. Vissheten om et av barnene til A kan formidles til de andre barnene dersom visshet om A ikke foreligger. I motsatt fall blir barnene d-atskilt.

Figur 3

• Konvergerende forbindelse
Dette er det vanskeligste tilfellet å forklare. Konklusjonen for eksempel i figur 4 er at visshet mellom foreldrene til A bare kan formidles dersom visshet om A foreligger. Dette skyldes bortforklaringsprinsippet som vi mennesker benytter oss av når noe ubehagelig foreligger. Det betyr igjen at ingen visshet om A medfører at foreldrene til A er d-atskilt.

Figur 4

Eksempel

Nå har vi tilstrekkelig kunnskap om Bayeske nettverk til å illustrere bruk av et slikt nettverk ved resonnering ved usikkerhet. (Læring ved hjelp av Bayeske nettverk tas ikke opp (se [1]).
La oss anta at tre dataingeniørstudenter Arne, Mia og Sven holder på med sitt hovedprosjekt og har avtalt møte med sin veileder, Lene Knutsen, kl 8.00. Til avtalt tidspunkt møter veileder og Sven, mens de to andre ikke dukker opp. Veileder har en stram tidsplan og er stemt til å avlyse møtet, da telefonen ringer. Det er Arne som over mobiltelefon forteller at han sitter i bilkø. Det er også kjent at Mia kjører til skolen og dessuten vet veileder at det foregår veiarbeid i distriktet. Veileder sier i den forbindelse til Sven at møtet utsettes da Mia også sitter i bilkø grunnet veiarbeid. Til dette bemerker Sven at han ikke så noe veiarbeid på vei til møtet. De blir derfor enige om å vente et kvarters tid til. Vi deler problemstillingen i to: før og etter ny informasjon foreligger.

Første del
Veilederen formulerer det Bayeske nettverk angitt i figur 5, jfr figur 3. (De to vertikale pilene kommenteres senere.) Hun har innført tre variable: A som står for Arne_er_forsinket, M for Mia_er_forsinket og V for veiarbeid_pågår. Hver av disse variable kan anta verdiene sann eller falsk. For eksempel betyr A = sann at Arne er forsinket, A = falsk det motsatte og V = sann at veiarbeid pågår.

Figur 5

Veileder angir videre visshetene

P(V = sann) = 0,6 og P(V = falsk) = 0,4 (9)

og de fire for P(A|V) i figur 6.

	V=sann	V=falsk
A=sann	0,7	0,1
A=falsk	0,3	0,9

Figur 6

Det er naturlig å anta at P(M|V) = P(A|V) (se figur 6).
På grunnlag av disse visshetene skal visshetene P(A) og P(M) bestemmes. Siden utregningene blir like, regnes bare den første ut.
Av (4) er P(AV)=P(A|V)P(V). (9) og visshetene i figur 6 gir nødvendig informasjon til å bestemme P(AV) (se figur 7).

	V=sann	V=falsk
A=sann	0,7 • 0,6= 0,42	0,1 • 0,4 = 0,04
A=falsk	0,3 • 0,6 = 0,18	0,9 • 0,4 = 0,36

Figur 7

P(A) finnes nå ganske enkelt av figur 7 ved såkalt marginalisering som betyr å summere linjevis i tabellen. Dette gir

P(A=sann)=0,42+0,04=0,46 (10) P(A=falsk)=0,18+0,36=0,54

Samlet har vi så langt: P(A) = P(M) = (0,46, 0,54) som betyr at vissheten til hver node i figur 5 er bestemt.

Andre del
Arnes telefon og Svens uttalelse er ny informasjon som må påvirke de fremkomne visshetene. Det de to vertikale pilene i figur 5 antyder. Siden veileder og Sven blir enige om å vente et kvarter, har veileder akseptert at Mias forsinkelse ikke skyldes veiarbeid, og det er blant annet denne visshet som nå er av interesse.
Vi starter med (7) som nå blir

P(V|A=sann)=P(A=sann|V)P(V)/P(A=sann) (11)

Siden vi må skille mellom V = sann og V = falsk, blir utregning av (11) der nødvendig data hentes fra (9), figur 6 og (10) og dessuten innfører vi V * = (V | A=sann):

P(V *) = P(V | A=sann) = (0,7• 0,6/0.46, 0,1• 0,4/0.46)=( 0.91 , 0.09 ) (12)

Dernest må P(M | V*) bestemmes. Her slipper vi lettvint fra det fordi A og M er d-atskilt (se figur 3). Dette gir

P(M | V*) = (13) P(M | (V | A=sann))=P(M | V)

Av (4) etter bruk av (13) blir P(MV*)=P(M |V)P(V*). Ved hjelp av figur 6 og (12) kan så P(MV*) beregnes (se figur 8).

	V*=sann	V*=falsk
M=sann	0,7• 0,91 = 0,637	0,1• 0,09 = 0,009
M=falsk	0,3• 0,91= 0,273	0,9• 0,09 = 0,081

Figur 8

Tilsvarende som i figur 7 marginaliserer vi i figur 8. Dette gir

P(M )=( 0,637+0.009,0.273+0,081) =(avrundet..) (0.65, 0.35) (14)

Sammenlikner vi (14) og (10), ser vi en klar forandring som skyldes informasjonen fra Arne. Til slutt, når veileder er overbevist om at Mias forsinkelse ikke skyldes veiarbeid, blir ifølge (13) og figur 6 P(M |V*=
falsk)=P(M|V=falsk)=(0.10, 0.90).

Referanser

[1] Introduction to Bayesian networks. Finn V. Jensen, UCL Press 1996. ISBN 9-781857-283327. Med boken følger også en diskett med systemet HUGIN. http://www.hugin.dk/hugintro/oil_wildcat_pane.html.

HØit Nr. 1-98