Probabilistisch redeneren en bayesiaanse netwerken

Een agent ziet soms maar een deel van zijn omgeving. Een sensor kan ruis bevatten en een actie kan verschillende uitkomsten hebben. Met kansrekening kan de agent aan elke mogelijkheid een mate van geloof toekennen en die kansinschattingen herzien zodra informatie binnenkomt.

Werelden, gebeurtenissen en variabelen

De uitkomstenruimte, $\mathrm{\Omega }$, bevat elke mogelijke uitkomst. De uitkomsten sluiten elkaar uit en omvatten samen alle mogelijkheden: precies één treedt op. Een gebeurtenis is een verzameling van deze uitkomsten, zoals “de bus is te laat”. De kans daarop is de som van de kansen op de uitkomsten in de gebeurtenis.

Een stochastische variabele kent aan elke uitkomst een waarde toe. Het domein bevat de mogelijke waarden. Bijvoorbeeld: $Weather$ heeft het domein $\{sun,cloud,rain\}$ voor zon, bewolking en regen. Schrijf variabelen met een hoofdletter en waarden met kleine letters. Voor de booleaanse variabele $Rain$ betekent $r$ waar en $\mathrm{\neg }r$ onwaar. De komma in $P(r,t)$ betekent “en”.

Kansen liggen tussen 0 en 1 en de kansen op alle uitkomsten tellen op tot 1. Voor complementaire gebeurtenissen geldt $P(\mathrm{\neg }a)=1-P(a)$. Een verdeling geeft de kans op elke waarde van een variabele; een a-priorikans beschrijft een kansinschatting voordat de gegevens waarin je geïnteresseerd bent, zijn verwerkt.

Lees een gezamenlijke tabel

Een gezamenlijke kansverdeling geeft de kans op elke combinatie van waarden. Hier is een model voor weer en bus:

De zes cellen zijn de zes mogelijke werelden en tellen samen op tot 1. Een rijtotaal is de kans op dat weertype, dus een rij hoeft niet op te tellen tot 1. Voor regen is $P(rain)=\mathrm{0,08}+\mathrm{0,12}=\mathrm{0,20}$. De kolom voor te laat geeft $P(late)=\mathrm{0,10}+\mathrm{0,12}+\mathrm{0,12}=\mathrm{0,34}$.

Deze bewerking heet marginalisatie, of uitsommeren. Om $X$ te behouden en $Y$ te verwijderen, gebruik je $P(x)={\sum }_{y}P(x,y)$. Tel op over elke waarde van de variabele die je verwijdert, inclusief onware waarden voor booleaanse variabelen.

Tel een overlap één keer

De gebeurtenis “regen of te laat” omvat elke cel in de rij voor regen of de kolom voor te laat. De kans daarop is

De aftrekking verwijdert de overlap die twee keer is meegeteld. In het algemeen geldt $P(a\vee b)=P(a)+P(b)-P(a,b)$. Alleen de marginale kansen optellen zou 0,54 geven en de wereld met regen en een late bus twee keer meetellen.

Waarom volledige tabellen kostbaar worden

Een volledige gezamenlijke tabel kan elke kansvraag over zijn variabelen beantwoorden, maar groeit snel. Elke extra booleaanse variabele verdubbelt het aantal werelden. Met $n$ booleaanse variabelen zijn er $2^n$ tabelwaarden en $2^n-1$ vrije getallen, omdat de laatste waarde vastligt door het totaal van 1. Dertig booleaanse variabelen vereisen 1.073.741.824 tabelwaarden. Compacte modellen slaan lokale afhankelijkheden op in plaats van elke wereld afzonderlijk te vermelden.

Een late bus verandert welke weersomstandigheden waarschijnlijk lijken. Voorwaardelijke kans richt zich op de werelden die overeenkomen met een observatie en meet vervolgens hun relatieve aandeel. De kans nadat rekening is gehouden met waargenomen gegevens is een a-posteriorikans.

Koppel de noemer aan de waargenomen gegevens

Voor waargenomen gegevens met een positieve kans geldt:

In het weer-en-busmodel zijn de tabelwaarden voor een late bus bij zon, bewolking en regen 0,10, 0,12 en 0,12. Hun totaal is 0,34. Dus $P(rain\mid late)=\mathrm{0,12}\mathrm{/}\mathrm{0,34}\approx \mathrm{0,353}$. Als je de vraag omdraait, krijg je $P(late\mid rain)=\mathrm{0,12}\mathrm{/}\mathrm{0,20}=\mathrm{0,6}$. Beide gebruiken dezelfde cel uit de gezamenlijke tabel, maar delen elk door de kans op de eigen waargenomen gegevens.

De volledige voorwaardelijke verdeling is $P(Weather\mid late)\approx ⟨\mathrm{0,294};\mathrm{0,353};\mathrm{0,353}⟩$. Deze waarden tellen op tot 1 omdat ze alternatieve weerwaarden onder één vaste observatie beschrijven. De drie aannemelijkheden $P(late\mid sun)=\mathrm{0,2}$, $P(late\mid cloud)=\mathrm{0,4}$ en $P(late\mid rain)=\mathrm{0,6}$ gebruiken verschillende voorwaarden en hoeven niet op te tellen tot 1.

Producten en ketens

Als je de definitie herschrijft, krijg je de productregel:

Door die herhaaldelijk toe te passen krijg je de kettingregel:

Elke volgorde van variabelen werkt. Voor deze identiteit is onafhankelijkheid niet nodig; later kunnen we daarmee de lijsten met voorwaarden verkorten.

Selecteer, sommeer en normaliseer

Voor bevraagde variabele $X$, waargenomen gegevens $e$ en verborgen variabelen $Y$ gebruikt enumeratie

Selecteer eerst werelden die overeenkomen met de waargenomen gegevens. Sommeer daarna alle verborgen variabelen uit en houd voor elke bevraagde waarde een apart totaal bij. Deel ten slotte deze totalen door hun som. De normalisatieconstante $\alpha$ is het omgekeerde van die som, die gelijk is aan $P(e)$.

Neem de booleaanse variabelen griep ($F$), koorts ($V$) en hoest ($K$). Hun volledige gezamenlijke tabel is:

Om $P(F\mid v)$ te vinden, behoud je de rijen met koorts en sommeer je hoest uit. De totalen zijn $\mathrm{0,056}+\mathrm{0,024}=\mathrm{0,08}$ voor griep en $\mathrm{0,018}+\mathrm{0,072}=\mathrm{0,09}$ voor geen griep. Normaliseer met 0,17 om $P(f\mid v)\approx \mathrm{0,471}$ te krijgen.

Als ook hoest wordt waargenomen, behoud je alleen de twee rijen met koorts en hoest. Nu is $P(f\mid v,k)=\mathrm{0,056}\mathrm{/}\mathrm{0,074}\approx \mathrm{0,757}$. Voor koorts zonder hoest is $P(f\mid v,\mathrm{\neg }k)=\mathrm{0,024}\mathrm{/}\mathrm{0,096}=\mathrm{0,25}$. Als je over hoest zou sommeren, zou deze extra observatie verloren gaan. Een onbewerkt totaal zoals 0,08 is een gezamenlijke kans, niet de gevraagde voorwaardelijke kans.

Een agent weet vaak hoe een oorzaak een observatie voortbrengt, maar moet in de andere richting redeneren. Een storingsmodel kan beschrijven hoe vaak een beschadigd onderdeel een waarschuwing veroorzaakt. Na de waarschuwing heeft de agent de kans op schade nodig.

Draai een voorwaardelijke kans correct om

De twee uitdrukkingen voor een gezamenlijke kans uit de productregel geven de regel van Bayes:

Hier is $P(c)$ de a-priorikans, $P(e\mid c)$ de aannemelijkheid en $P(c\mid e)$ de a-posteriorikans. De noemer omvat alle manieren waarop de waargenomen gegevens kunnen optreden. Voor een booleaanse oorzaak geeft de regel van totale waarschijnlijkheid:

Neem bij meer dan twee oorzaakwaarden voor elke waarde één term op. Je kunt ook voor elke oorzaak een score als product van aannemelijkheid en a-priorikans berekenen en de scores normaliseren.

Werk een voorbeeld met een zeldzame aandoening uit

Stel dat een ziekte 1% van een populatie treft. Een test is positief bij 90% van de zieken en bij 5% van de gezonde mensen. De kans op een positieve uitslag is

De kans op ziek en positief is 0,009, dus

Natuurlijke frequenties maken de noemer inzichtelijker. Van 10.000 mensen zijn er 100 ziek en testen er 90 positief. Van 9.900 gezonde mensen testen er 495 positief. Er zijn in totaal 585 positieve uitslagen; 90 daarvan zijn van zieke mensen.

De sensitiviteit van 90% beantwoordt de vraag “Hoe vaak test een ziek persoon positief?” Ze beantwoordt niet de vraag “Hoe vaak is een positief geteste persoon ziek?” Bij verwaarlozing van de basiskans krijgt de a-priorikans te weinig gewicht. Bij een zeldzame aandoening zijn er aanvankelijk veel minder zieken, waardoor fout-positieve uitslagen uit de grotere gezonde groep talrijker kunnen zijn dan terecht positieve uitslagen. Als de sensitiviteit en de fout-positieve fractie gelijk blijven, verandert de a-posteriorikans nog steeds als de prevalentie verandert.

Een negatieve uitslag gebruikt de complementaire aannemelijkheden:

Werk opnieuw bij als nieuwe gegevens binnenkomen

De a-posteriorikans uit één observatie wordt de a-priorikans voor de volgende. Als een tweede testuitslag voorwaardelijk onafhankelijk is van de eerste gegeven of iemand ziek is, levert nog een positieve uitslag op:

Gebruik bij opeenvolgende berekeningen de niet-afgeronde eerste a-posteriorikans. Voorwaardelijke onafhankelijkheid doet ertoe: herhaalde metingen van dezelfde defecte sensor kunnen een fout delen, zodat de bijwerking te sterk kan uitvallen als je hun aannemelijkheden als onafhankelijk bewijs vermenigvuldigt.

Achtergrondinformatie blijft in elke relevante voorwaarde staan:

Hiermee kan een agent bijwerken binnen de populatie of situatie waarover die al kennis heeft, met de huidige a-priorikans en de toepasselijke aannemelijkheden.

Sommige observaties veranderen elkaars kansen; andere voegen geen informatie toe zodra een relevante voorwaarde bekend is. Onafhankelijkheid laat zien wanneer een lange kansuitdrukking kan worden vervangen door kleinere delen.

Onafhankelijkheid geldt voor elke waarde

Gebeurtenissen zijn onafhankelijk als $P(a,b)=P(a)P(b)$. Voor variabelen moet deze gelijkheid voor elk waardenpaar gelden. Eén paar dat niet voldoet, toont afhankelijkheid aan. In de weertabel is $P(rain,late)=\mathrm{0,12}$, terwijl $P(rain)P(late)=\mathrm{0,20}(\mathrm{0,34})=\mathrm{0,068}$, dus zijn het weer en de toestand van de bus afhankelijk.

Wederzijds uitsluitende gebeurtenissen met positieve kansen zijn afhankelijk: als je verneemt dat de ene heeft plaatsgevonden, wordt de kans op de andere nul. Onafhankelijke gebeurtenissen kunnen samen optreden. Als $n$ booleaanse variabelen allemaal onderling onafhankelijk zijn, zijn slechts $n$ kansen nodig, tegenover $2^n-1$ voor een gezamenlijke tabel zonder beperkingen.

Weet wat je vastzet

Voorwaardelijke onafhankelijkheid, geschreven als $X\perp Y\mid Z$, betekent

De gelijkheid geldt voor elke relevante combinatie van waarden. Anders gezegd: kennis van $Y$ voegt niets toe over $X$ zodra $Z$ bekend is.

In het griepmodel geldt $P(k\mid v,f)=P(k\mid f)=\mathrm{0,7}$ en $P(k\mid v,\mathrm{\neg }f)=P(k\mid \mathrm{\neg }f)=\mathrm{0,2}$. Koorts en hoest zijn voorwaardelijk onafhankelijk gegeven of iemand griep heeft. Zonder die voorwaarde zijn ze afhankelijk: $P(k)=\mathrm{0,25}$, terwijl $P(k\mid v)=\mathrm{0,074}\mathrm{/}\mathrm{0,17}\approx \mathrm{0,435}$. Koorts verandert de kansinschatting voor griep, wat de kansinschatting voor hoest verandert.

Onafhankelijkheid zonder waargenomen gegevens en onafhankelijkheid gegeven waargenomen gegevens zijn afzonderlijke beweringen. Het waarnemen van een gemeenschappelijk gevolg kan zelfs twee eerder onafhankelijke oorzaken afhankelijk maken.

Classificeer met naïeve Bayes

Een naïef Bayesmodel neemt aan dat kenmerken voorwaardelijk onafhankelijk zijn gegeven een klasse. De a-posterioriverdeling is

Een booleaanse klasse met $n$ booleaanse kenmerken heeft $1+2n$ kansen nodig. De aanname kan onvolmaakt zijn en toch nuttige classificatie ondersteunen, maar gecorreleerde kenmerken kunnen leiden tot kansen die te veel zekerheid uitdrukken.

Voor spam nemen we $P(spam)=\mathrm{0,3}$. Het woord “offer” verschijnt met kans 0,4 in spam en 0,05 in reguliere mail. Het woord “winner” verschijnt met kansen 0,2 en 0,01. Als beide woorden aanwezig zijn, zijn de scores $\mathrm{0,3}(\mathrm{0,4})(\mathrm{0,2})=\mathrm{0,024}$ voor spam en $\mathrm{0,7}(\mathrm{0,05})(\mathrm{0,01})=\mathrm{0,00035}$ voor reguliere mail. Normaliseren geeft $P(spam\mid o,w)\approx \mathrm{0,986}$.

Ook afwezigheid levert gegevens op. Als “offer” aanwezig is maar “winner” ontbreekt, worden de scores $\mathrm{0,3}(\mathrm{0,4})(\mathrm{0,8})=\mathrm{0,096}$ en $\mathrm{0,7}(\mathrm{0,05})(\mathrm{0,99})=\mathrm{0,03465}$, wat een a-posteriorikans op spam van ongeveer 0,735 geeft. Gebruik het complement van de aannemelijkheid voor een afwezig booleaans kenmerk. Een aannemelijkheid van nul maakt de hele klassescore nul. Een mogelijke gebeurtenis moet dus geen nul krijgen alleen omdat die in een kleine gegevenssteekproef ontbrak.

Een bayesiaans netwerk geeft een gezamenlijke kansverdeling weer met een gerichte acyclische graaf en lokale kansentabellen. Elke knoop is een stochastische variabele. Een pijl naar een knoop wijst een van zijn ouders aan; als je pijlen volgt, mag je nooit bij de beginknoop terugkomen.

Een woon-werkverkeermodel

Gebruik vijf booleaanse variabelen: regen ($R$), een ongeluk ($A$), druk verkeer ($T$), te laat komen ($L$) en een paraplu meenemen ($U$). De pijlen zijn $R\to T$, $A\to T$, $T\to L$ en $R\to U$. Regen en een ongeluk hebben a-priorikansen $P(r)=\mathrm{0,2}$ en $P(a)=\mathrm{0,1}$.

De voorwaardelijke kansentabel van verkeer hangt af van beide ouders:

De overige tabellen geven $P(l\mid t)=\mathrm{0,6}$, $P(l\mid \mathrm{\neg }t)=\mathrm{0,1}$, $P(u\mid r)=\mathrm{0,9}$ en $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$. Elke waardetoekenning aan de ouders selecteert een verdeling over de waarden van het kind. Voor booleaanse knopen sla je alleen de kans op waar op; de kans op onwaar is het complement. Dus $P(\mathrm{\neg }t\mid r,\mathrm{\neg }a)=\mathrm{0,3}$.

Bereken de kans op een volledige wereld

Het netwerk definieert zijn gezamenlijke kansverdeling met

Voor regen, geen ongeluk, druk verkeer, te laat komen en een paraplu selecteer je uit elke knoop één tabelwaarde:

De factoren beschrijven achtereenvolgens regen, geen ongeluk, verkeer onder die ouderwaarden, te laat komen bij druk verkeer en een paraplu meenemen bij regen. Als je een knoop weglaat, krijg je een onvolledig product. Als je voor verkeer 0,95 kiest, beschrijf je ook een ongeluk en past de waarde dus niet bij de wereld die je beoordeelt.

De formule volgt uit de kettingregel in een topologische ordening, met ouders vóór kinderen. De voorwaardelijke onafhankelijkheden van het netwerk verkorten elke voorwaarde van alle voorafgaande variabelen tot alleen de ouders.

Tel parameters en onderscheid marginale kansen

Een booleaanse knoop met $k$ booleaanse ouders heeft $2^k$ vrije kansen nodig. Algemeen heeft een knoop met $d$ waarden en $k$ ouders met elk $d$ waarden er $(d-1)d^k$ nodig. Het woon-werkverkeernetwerk heeft $1+1+4+2+2=10$ getallen nodig; een volledige gezamenlijke verdeling over de vijf booleaanse variabelen heeft er 31 nodig. Dertig booleaanse knopen met elk hoogstens vijf ouders hebben hoogstens 960 getallen nodig, tegenover meer dan een miljard voor een volledige gezamenlijke verdeling zonder beperkingen.

Een waarde in een voorwaardelijke kansentabel beantwoordt een vraag waarbij elke ouder vaststaat. Om een marginale kans te vinden, neem je het gewogen gemiddelde over de ontbrekende ouderwaarden. Hier is

waarbij de vier termen de verkeersrijen wegen met hun ouderkansen. Zo is ook $P(t\mid r)=\mathrm{0,1}(\mathrm{0,95})+\mathrm{0,9}(\mathrm{0,7})=\mathrm{0,725}$. Dat is niet de afzonderlijke rijwaarde 0,7.

Pijlen lopen vaak van oorzaak naar gevolg omdat het model daardoor compact en begrijpelijk wordt. Formeel leggen ze een factorisatie en onafhankelijkheidsclaims vast. Een omgekeerde graaf met twee knopen kan dezelfde gezamenlijke kansverdeling weergeven met andere tabellen; een pijl alleen toont geen causaliteit aan.

Een bruikbaar netwerk laat afhankelijkheden weg die niet nodig zijn en behoudt de afhankelijkheden die de verdeling vereist. Door weinig ouders te kiezen kun je veel tabelwaarden besparen, maar elke weglating legt het model vast op een onafhankelijkheidsclaim.

Bouw het netwerk in een volgorde

Kies variabelen en hun domeinen en orden daarna de variabelen. Selecteer voor elke variabele een minimale verzameling eerdere variabelen die haar onafhankelijk maakt van de andere eerdere variabelen. Voeg pijlen vanuit deze ouders toe en vul de voorwaardelijke kansentabel met deskundigenoordelen of kansen die uit tellingen zijn geschat.

Een volgorde met oorzaken eerst levert voor het woon-werkverkeermodel vier pijlen en tien vrije kansen op. Een andere geldige volgorde is $L,T,U,R,A$, met ouderverzamelingen $T:\{L\}$, $U:\{T\}$, $R:\{T,U\}$ en $A:\{T,R\}$. Dit gebruikt zes pijlen en $1+2+2+4+4=13$ getallen. Gegeven het verkeer verandert regen de kansinschatting voor een ongeluk, dus moet regen in die volgorde een van de ouders van ongeluk blijven.

Elke volgorde kan de verdeling weergeven als elke knoop genoeg ouders krijgt. Elke knoop alle eerdere knopen als ouders geven werkt altijd, maar levert geen compressie op. Een diagnostische volgorde kan ook kansen vereisen die moeilijker te beoordelen zijn, zoals regen gegeven verkeer en een paraplu. Een noodzakelijke ouder weglaten dwingt een onjuiste onafhankelijkheid af; een onnodige ouder toevoegen vergroot de tabel.

Twee lokale onafhankelijkheidsregels

De lokale Markoveigenschap stelt dat een knoop onafhankelijk is van zijn niet-afstammelingen gegeven zijn ouders. In het woon-werkverkeernetwerk geldt $L\perp \{R,A,U\}\mid T$ en $U\perp \{A,T,L\}\mid R$. Zodra het verkeer bekend is, voegen de andere variabelen niets toe over te laat komen.

De Markovdeken van een knoop bevat zijn ouders, zijn kinderen en de andere ouders van zijn kinderen. Gegeven deze variabelen is de knoop onafhankelijk van elke variabele buiten de Markovdeken. De Markovdeken van regen is $\{T,U,A\}$: ongeluk hoort erbij omdat het de andere ouder van verkeer is. De Markovdeken van verkeer is $\{R,A,L\}$ en die van te laat komen bevat alleen $\{T\}$. De Markovdeken maakt lokale bijwerkingen mogelijk, ook als het volledige netwerk groot is.

Vervang een grote tabel door structuur

Een deterministische knoop is een vaste functie van zijn ouders, zoals $Late=Traffic\vee Strike$. De rijen bevatten nullen en enen. Een OF-model met ruis laat elke aanwezige oorzaak onafhankelijk falen. Als oorzaak $i$ onderdrukkingskans $q_i$ heeft, blijft het gevolg alleen uit als alle actieve oorzaken falen:

Stel dat een ongeluk met kans 0,2 geen file veroorzaakt en wegwerkzaamheden met kans 0,4 geen file veroorzaken. Een ongeluk alleen geeft een kans op file van 0,8; wegwerkzaamheden alleen geven 0,6. Als beide optreden, is de kans op geen file $\mathrm{0,2}(\mathrm{0,4})=\mathrm{0,08}$, dus is de kans op file 0,92.

Het gewone OF-model met ruis geeft geen gevolg als geen oorzaak actief is. Een achtergrondoorzaak, weergegeven als een altijd aanwezige oorzaak, maakt het mogelijk dat het gevolg door niet-vermelde oorzaken ontstaat. Het model gebruikt één onderdrukkingskans per oorzaak in plaats van een tabel zonder beperkingen met $2^k$ rijen. Deze besparing komt voort uit onafhankelijk falende oorzaken; voor willekeurige interacties is een uitgebreider model nodig.

d-separatie vindt voorwaardelijke onafhankelijkheden die door de graaf van een netwerk worden gegarandeerd. Daarbij bekijk je paden zonder te eisen dat pijlen in de gevolgde richting wijzen. De pijlpunten doen er wel toe, omdat ze bepalen hoe elke middelste knoop zich gedraagt.

Drie padpatronen

In een keten schermt kennis van de middelste variabele de eerdere variabele af. In $R\to T\to L$ voegt regen niets toe over te laat komen zodra het verkeer bekend is. In een vork doet kennis van de gemeenschappelijke oorzaak hetzelfde: een paraplu voegt niets toe over het verkeer zodra regen bekend is.

Een botsingsknoop (collider), of gemeenschappelijk gevolg, werkt andersom. Het pad $R\to T\leftarrow A$ is geblokkeerd zonder waargenomen gegevens over verkeer of zijn afstammelingen. Het waarnemen van verkeer, of verderop van te laat komen, opent de botsingsknoop. Oorzaken die onafhankelijk waren, kunnen dan informatie over elkaar geven.

Wegverklaren

In het woon-werkverkeermodel is $P(a\mid r)=P(a)=\mathrm{0,1}$. Druk verkeer verhoogt de kans op een ongeluk tot ongeveer 0,235. Als ook regen bekend is, daalt die tot $P(a\mid t,r)\approx \mathrm{0,131}$; als bekend is dat het niet regent, krijg je $P(a\mid t,\mathrm{\neg }r)\approx \mathrm{0,308}$. Regen verklaart een deel van het waargenomen verkeer, waardoor een ongeluk als verklaring minder nodig is. Dit heet wegverklaren.

Controleer elk pad

Om $X\perp Y\mid Z$ te toetsen:

1. Som elk ongericht pad tussen de bevraagde variabelen op.
2. Bepaal bij elke interne knoop of het pad een botsingsknoop of een andere knoop vormt.
3. Blokkeer een pad als het een waargenomen niet-botsingsknoop heeft, of een botsingsknoop waarvan noch de knoop zelf noch een afstammeling is waargenomen.
4. Concludeer alleen tot d-separatie als elk pad is geblokkeerd.

Voor paraplu en ongeluk is het enige pad $U\leftarrow R\to T\leftarrow A$. Zonder waargenomen gegevens blokkeert verkeer het pad, dus $U\perp A$. Gegeven te laat komen gaat de botsingsknoop bij verkeer open en blijft regen niet waargenomen, dus wordt het pad actief. Het numerieke model geeft $P(u\mid l)\approx \mathrm{0,434}$ maar $P(u\mid a,l)\approx \mathrm{0,356}$.

Als zowel te laat komen als regen is waargenomen, is de botsingsknoop bij verkeer nog steeds open, maar blokkeert regen het pad als waargenomen niet-botsingsknoop. Daarom $U\perp A\mid L,R$. Het openen van één deel van een pad heft een blokkade elders niet op.

Paraplu en te laat komen hebben het pad $U\leftarrow R\to T\to L$. Het is actief zonder waargenomen gegevens en wordt geblokkeerd door regen of verkeer. Bijvoorbeeld $P(l\mid u,r)=P(l\mid r)=\mathrm{0,4625}$.

Interpreteer de garantie van de graaf

d-separatie is correct: de onafhankelijkheid geldt voor elke verdeling die de graaf volgt. Een actief pad betekent dat onafhankelijkheid niet gegarandeerd is. Specifieke waarden in de voorwaardelijke kansentabellen kunnen de variabelen toevallig toch onafhankelijk maken. In een graaf met meerdere paden is het niet genoeg om één geblokkeerd pad te bekijken; een ander pad kan actief blijven.

Een netwerk slaat een gezamenlijke kansverdeling op als lokale onderdelen. Exacte inferentie combineert die onderdelen om een zoekvraag te beantwoorden en telt daarbij op over variabelen waarvan de waarden onbekend blijven. Enumeratie is de directe manier om dit te doen.

Onderscheid de drie rollen van variabelen

In $P(X\mid e)$ is $X$ de bevraagde variabele en legt $e$ de waargenomen gegevens vast. Elke andere variabele is verborgen. Vul het product van het netwerk in de algemene enumeratieformule in:

Bereken voor elke bevraagde waarde een niet-genormaliseerd totaal en deel die totalen door hun som. Waargenomen waarden blijven in elk product vaststaan. Verborgen variabelen doorlopen hun volledige domein.

Voor het woon-werkverkeermodel, met pijlen $R\to T\leftarrow A$, $T\to L$ en $R\to U$, zijn bij de zoekvraag $P(R\mid l)$ ongeluk, verkeer en paraplu verborgen. Elke volledige term gebruikt $P(R)P(A)P(T\mid R,A)P(l\mid T)P(U\mid R)$.

Verwijder een irrelevant blad

Paraplu heeft geen waargenomen afstammeling en is noch de bevraagde variabele noch een observatievariabele. Als je de voorwaardelijke kansentabel over beide waarden sommeert, krijg je ${\sum }_{u^{\mathrm{\prime }}}P(u^{\mathrm{\prime }}\mid r)=1$ voor elke regenwaarde. De bijdrage verdwijnt.

Algemener behoud je bevraagde variabelen, observatievariabelen en al hun voorouders. Andere variabelen kun je verwijderen door eerst irrelevante bladeren uit te sommeren en daarna terug te werken. Dit zegt iets over hun bijdrage aan deze zoekvraag; een niet-waargenomen knoop kan bij een andere zoekvraag wel van belang zijn.

Bereken de twee totalen voor regen

De woon-werktabellen geven $P(r)=\mathrm{0,2}$, $P(a)=\mathrm{0,1}$, verkeerskansen 0,95, 0,7, 0,8 en 0,2 voor oudercombinaties $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$ en kansen op te laat komen van 0,6 bij druk verkeer en 0,1 zonder druk verkeer.

Voor regen en een ongeluk sommeer je de verkeersalternatieven: $\mathrm{0,95}(\mathrm{0,6})+\mathrm{0,05}(\mathrm{0,1})=\mathrm{0,575}$. Voor regen zonder ongeluk is het resultaat $\mathrm{0,7}(\mathrm{0,6})+\mathrm{0,3}(\mathrm{0,1})=\mathrm{0,45}$. Weeg met de kansen op een ongeluk en daarna met de kans op regen:

Voor geen regen zijn de overeenkomstige binnenste totalen 0,5 en 0,2, wat geeft:

Normaliseer met $\mathrm{0,0925}+\mathrm{0,184}=\mathrm{0,2765}$. Het antwoord is $P(R\mid l)\approx ⟨\mathrm{0,335};\mathrm{0,665}⟩$ voor waar en onwaar. Met 0,0925 zou je de gezamenlijke gebeurtenis rapporteren, vóór conditionering.

Houd sommen bij hun afhankelijkheden

Een factor mag alleen buiten een som als geen van zijn argumenten afhangt van de variabele waarover wordt gesommeerd. Zo kan $P(r)$ buiten de som over ongeluk; $P(t\mid r,a^{\mathrm{\prime }})$ kan dat niet, omdat ongeluk een ouderargument is.

Als paraplu wordt waargenomen, verdwijnt die niet meer door uitsommeren. Met $P(u\mid r)=\mathrm{0,9}$ en $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$ is de nieuwe a-posteriorikans $\mathrm{0,08325}\mathrm{/}(\mathrm{0,08325}+\mathrm{0,0368})\approx \mathrm{0,693}$. Enumeratie kan diepte-eerst met weinig geheugen worden uitgevoerd, maar bezoekt exponentieel veel verborgen waardetoekenningen en herhaalt deelberekeningen.

Enumeratie herhaalt werk omdat veel volledige werelden dezelfde deelberekening delen. Variabele-eliminatie slaat deze tussenresultaten op als factoren en hergebruikt ze. De methode berekent dezelfde exacte a-posterioriverdeling in een andere rekenvolgorde.

Factoren, vermenigvuldiging en waargenomen gegevens

Een factor kent niet-negatieve getallen toe aan waardetoekenningen voor zijn variabelen. Voorwaardelijke kansentabellen zijn beginfactoren, maar tussenfactoren hoeven niet op te tellen tot 1. Verwerk waargenomen gegevens door de waargenomen waarde te behouden. Bij waarneming van te laat komen is $P(l\mid T)$ een factor over verkeer met waarden 0,6 en 0,1.

Bij factorvermenigvuldiging vermenigvuldig je overeenkomende tabelwaarden en gebruik je de vereniging van hun variabelenverzamelingen. Vermenigvuldiging van $P(A)$ en $P(T\mid R,A)$ geeft een factor over regen, ongeluk en verkeer. Bij het uitsommeren van ongeluk tel je tabelwaarden op die alleen verschillen in de waarde van ongeluk.

Vermenigvuldig voor elke verborgen variabele elke factor die de variabele bevat, sommeer die uit en vervang die factoren door het resultaat. Behoud factoren waarin de variabele niet voorkomt. Vermenigvuldig aan het einde de resterende factoren en normaliseer over de bevraagde waarden.

Elimineer ongeluk en daarna verkeer

Verwijder voor $P(R\mid l)$ het niet-waargenomen blad paraplu. Begin met $P(R)$, $P(A)$, $P(T\mid R,A)$ en $P(l\mid T)$. Eliminatie van ongeluk geeft

De waarden voor druk verkeer zijn $f_1(r,t)=\mathrm{0,1}(\mathrm{0,95})+\mathrm{0,9}(\mathrm{0,7})=\mathrm{0,725}$ en $f_1(\mathrm{\neg }r,t)=\mathrm{0,1}(\mathrm{0,8})+\mathrm{0,9}(\mathrm{0,2})=\mathrm{0,26}$. De waarden voor geen druk verkeer zijn 0,275 en 0,74.

Elimineer nu verkeer:

Dit geeft $f_2(r)=\mathrm{0,725}(\mathrm{0,6})+\mathrm{0,275}(\mathrm{0,1})=\mathrm{0,4625}$ en $f_2(\mathrm{\neg }r)=\mathrm{0,26}(\mathrm{0,6})+\mathrm{0,74}(\mathrm{0,1})=\mathrm{0,23}$. Vermenigvuldiging met de a-priorikans op regen geeft $⟨\mathrm{0,0925};\mathrm{0,184}⟩$. Deel door 0,2765 om $⟨\mathrm{0,335};\mathrm{0,665}⟩$ te krijgen.

Eerst verkeer elimineren werkt ook. De factor $g(R,A)={\sum }_{t^{\mathrm{\prime }}}P(t^{\mathrm{\prime }}\mid R,A)P(l\mid t^{\mathrm{\prime }})$ heeft waarden 0,575, 0,45, 0,5 en 0,2. Wegen met de a-priorikans op een ongeluk levert daarna dezelfde twee aannemelijkheden voor te laat komen op.

Kies een volgorde die factoren klein houdt

Een factor over $k$ variabelen met $d$ waarden heeft $d^k$ tabelwaarden. Het grootste variabelenbereik van een tussenfactor bepaalt meestal de rekenkosten. Stel dat verborgen $Z$ naar booleaanse variabelen $X_1,\dots ,X_n$ wijst, elk met een waargenomen kind $Y_i$, en dat de bevraagde variabele $X_n$ is. Als je eerst $Z$ elimineert, vermenigvuldig je tot een tabel over $Z,X_1,\dots ,X_n$, waarna $2^n$ tabelwaarden overblijven. Als je eerst de andere $X_i$ elimineert, wordt elke tak herleid tot een factor over $Z$; het grootste bereik bij vermenigvuldiging is dan alleen $Z,X_i$, met vier tabelwaarden.

Een polyboom heeft hoogstens één ongericht pad tussen elk paar knopen. Met een goede volgorde is inferentie lineair in de totale omvang van de voorwaardelijke kansentabellen. Algemene exacte inferentie en het vinden van de optimale eliminatievolgorde zijn NP-moeilijk. Een praktische heuristiek kiest een variabele die als volgende een kleine factor oplevert. Behoud de bevraagde variabele tot de normalisatie. Als je een hele factor met een positieve constante vermenigvuldigt, blijft het genormaliseerde antwoord gelijk.

Als exacte sommen te kostbaar zijn, kan een agent waardetoekenningen simuleren en kansen schatten uit hun frequenties. Steekproeftrekking levert een benadering op waarvan de kwaliteit afhangt van hoeveel bruikbare informatie de trekkingen bevatten.

Zet een toevalsgetal om in een waarde

Trek een uniform verdeeld getal $u$ uit $[0,1)$. Verdeel dat interval in stukken met lengten gelijk aan de kansen. Voor de weerkansen $⟨\mathrm{0,5};\mathrm{0,3};\mathrm{0,2}⟩$ neemt zon $[0;\mathrm{0,5})$ in, bewolking $[\mathrm{0,5};\mathrm{0,8})$ en regen $[\mathrm{0,8};1)$. Een trekking van 0,63 geeft bewolking. Kies voor een booleaanse variabele waar als de trekking kleiner is dan de kans op waar.

Trek waarden voor ouders vóór kinderen

Steekproeftrekking uit de a-prioriverdeling doorloopt variabelen in topologische volgorde. Voor elke knoop wordt een waarde getrokken uit de rij van de voorwaardelijke kansentabel die door de getrokken ouderwaarden wordt geselecteerd. “A-priori” verwijst naar trekken uit het netwerk voordat de steekproefpopulatie wordt geconditioneerd op de waargenomen gegevens van de zoekvraag.

Gebruik in het woon-werkverkeermodel volgorde $R,A,T,L,U$ en trekkingen 0,13, 0,57, 0,40, 0,81 en 0,35:

1. Regen is waar omdat $\mathrm{0,13}<\mathrm{0,2}$.
2. Ongeluk is onwaar omdat $\mathrm{0,57}\ge \mathrm{0,1}$.
3. Verkeer is waar omdat $\mathrm{0,40}<P(t\mid r,\mathrm{\neg }a)=\mathrm{0,7}$.
4. Te laat is onwaar omdat $\mathrm{0,81}\ge P(l\mid t)=\mathrm{0,6}$.
5. Paraplu is waar omdat $\mathrm{0,35}<P(u\mid r)=\mathrm{0,9}$.

De waardetoekenning is $(r,\mathrm{\neg }a,t,\mathrm{\neg }l,u)$. De kans dat die wordt gegenereerd is $\mathrm{0,2}(\mathrm{0,9})(\mathrm{0,7})(\mathrm{0,4})(\mathrm{0,9})=\mathrm{0,04536}$, precies de kans volgens de gezamenlijke verdeling van het netwerk. Als je vóór de ouders een waarde voor een kind zou trekken, zou de benodigde rij van de voorwaardelijke kansentabel nog niet vaststaan.

Schat kansen uit tellingen

De fractie steekproeven uit de a-prioriverdeling met te laat komen schat $P(l)$, die in dit model 0,2765 is. De schatter is consistent: als het aantal onafhankelijke trekkingen groeit, convergeert die naar de werkelijke kans. Een grotere steekproefreeks kan nog steeds schommelen. De gebruikelijke fout bij onafhankelijke steekproeven schaalt als $1\mathrm{/}\sqrt{N}$, dus ongeveer vier keer zoveel steekproeven halveren de fout; twee keer zoveel niet.

Conditioneer met verwerpingssteekproeftrekking

Verwerpingssteekproeftrekking genereert waardetoekenningen uit de a-prioriverdeling en gooit die weg als ze de waargenomen gegevens tegenspreken. Tel bevraagde waarden alleen binnen de behouden waardetoekenningen. Stel bijvoorbeeld dat 280 van 1.000 waardetoekenningen te laat komen bevatten en 94 daarvan ook regen. Dan is $P(r\mid l)\approx 94\mathrm{/}280\approx \mathrm{0,336}$. Delen door 1.000 zou in plaats daarvan de gezamenlijke gebeurtenis regen en te laat komen schatten.

Een steekproef mag worden afgebroken zodra die met een observatie in strijd is; dat bespaart het resterende simulatiewerk. De verwachte behouden fractie blijft $P(e)$. Alleen te laat komen behoudt ongeveer 28%; te laat komen met een paraplu behoudt ongeveer 12%, omdat $P(l,u)=\mathrm{0,12005}$. Veel observaties kunnen de combinatie van waargenomen gegevens zeldzaam maken, ook als elke observatie afzonderlijk gewoon is. Als geen steekproeven overblijven, is de voorwaardelijke schatting niet gedefinieerd en is meer bruikbare steekproeftrekking nodig.

Verwerpingssteekproeftrekking besteedt tijd aan het maken van waardetoekenningen die niet bruikbaar zijn. Aannemelijkheidsweging houdt elke observatievariabele vast en compenseert met een gewicht. Steekproeven waarvan de verborgen waarden de waargenomen gegevens waarschijnlijk maken, dragen meer bij.

Bouw een gewogen waardetoekenning op

Begin elke steekproef met gewicht 1. Doorloop knopen in topologische volgorde. Trek voor een niet-waargenomen knoop een waarde met de huidige waarden van zijn ouders. Behoud bij een observatieknoop de waargenomen waarde en vermenigvuldig het gewicht met de kans op die waarde uit de voorwaardelijke kansentabel:

Alleen kansen op waargenomen gegevens komen in dit gewicht. De kansen van de getrokken knopen bepalen al hoe vaak hun waardetoekenningen worden gegenereerd. Als je die kansen ook in het gewicht vermenigvuldigt, tel je ze twee keer.

Twee steekproeven in het woon-werkverkeermodel

Houd voor $P(R\mid l,u)$ te laat komen en paraplu op waar. Trek waarden voor regen, ongeluk en verkeer. De verkeerskansen voor $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$ zijn 0,95, 0,7, 0,8 en 0,2, met a-priorikansen $P(r)=\mathrm{0,2}$ en $P(a)=\mathrm{0,1}$.

Trekkingen 0,13, 0,57 en 0,40 geven regen, geen ongeluk en druk verkeer. Het vastgezette te laat komen draagt $P(l\mid t)=\mathrm{0,6}$ bij; de vastgezette paraplu draagt $P(u\mid r)=\mathrm{0,9}$ bij. Het gewicht van de steekproef is $\mathrm{0,6}(\mathrm{0,9})=\mathrm{0,54}$.

Trekkingen 0,66, 0,05 en 0,92 geven daarentegen geen regen, een ongeluk en geen druk verkeer. De aannemelijkheden van de waargenomen gegevens zijn nu $P(l\mid \mathrm{\neg }t)=\mathrm{0,1}$ en $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$, dus is het gewicht 0,02. Beide steekproeven komen overeen met de waargenomen gegevens omdat die waarden zijn vastgezet, maar hun bijdragen verschillen sterk.

Normaliseer gewichten, geen aantallen steekproeven

Schat een bevraagde kans met

De regenschatting met twee steekproeven is $\mathrm{0,54}\mathrm{/}(\mathrm{0,54}+\mathrm{0,02})\approx \mathrm{0,964}$. Dat ligt ver van de exacte a-posteriorikans van ongeveer 0,693; twee trekkingen zijn te weinig om de relevante verborgen waardetoekenningen weer te geven. Bij veel trekkingen convergeert de gewogen verhouding naar de a-posterioriverdeling. Als je 0,54 door twee deelt, krijg je geen schatting van een voorwaardelijke kans.

De correctie werkt omdat vermenigvuldiging van de trekkingskans met het gewicht van de waargenomen gegevens het volledige gezamenlijke product oplevert. Normalisatie verwijdert de gemeenschappelijke kans op de waargenomen gegevens en laat de voorwaardelijke verdeling over.

Herken geconcentreerde gewichten

Vastgezette waargenomen gegevens beïnvloeden hoe waarden voor hun afstammelingen worden getrokken, omdat die de gegevens in hun ouderrijen gebruiken. Voorafgaande variabelen worden nog steeds getrokken zonder terugkoppeling van latere observaties. Als zeldzame waargenomen gegevens in bladknopen zitten, kunnen de meeste voorafgaande waardetoekenningen die slecht verklaren. Hun gewichten zijn zeer klein en enkele waardetoekenningen kunnen het resultaat bepalen.

Aannemelijkheidsweging gebruikt rekenwerk vaak efficiënter dan verwerpingssteekproeftrekking, maar “geen verworpen steekproeven” betekent niet dat alle steekproeven even informatief zijn. Een lange reeks met sterk ongelijke gewichten kan nog steeds een instabiele schatting geven. Bekijk welke waardetoekenningen het totale gewicht dragen als je resultaten van verschillende reeksen vergelijkt.

Gibbs-steekproeftrekking behoudt een volledige waardetoekenning en verandert telkens één niet-waargenomen variabele. Elke verandering wordt getrokken uit de voorwaardelijke verdeling van de variabele gegeven de huidige waarden van alle andere variabelen. De reeks vormt een Markovketen-Monte-Carlosteekproeftrekking, of MCMC.

Begin een keten en houd waargenomen gegevens vast

Zet waargenomen gegevens op hun waargenomen waarden en initialiseer de overige variabelen. Begin bij deterministische nullen met een waardetoekenning die overeenkomt met de waargenomen gegevens en een positieve gezamenlijke kans heeft. Kies een niet-waargenomen variabele om bij te werken, bereken voor elke mogelijke waarde een kans, normaliseer en trek de nieuwe waarde. Alle andere waarden blijven tijdens die stap staan. Door dit proces te herhalen kunnen waargenomen gegevens zowel eerdere als latere kansinschattingen beïnvloeden.

Alleen de Markovdeken van de geselecteerde knoop is nodig: zijn ouders, kinderen en de andere ouders van zijn kinderen. Factoren buiten die Markovdeken veranderen niet als de geselecteerde waarde verandert en vallen dus weg bij normalisatie. De lokale formule is

Kinderen behouden hun huidige waarden terwijl elke kandidaatwaarde van de geselecteerde ouder wordt geprobeerd. Hun waarden in de voorwaardelijke kansentabellen kunnen daardoor veranderen, ook al worden voor de kinderen zelf niet opnieuw waarden getrokken.

Werk regen bij in het woon-werkverkeermodel

Houd te laat komen en paraplu op waar. Stel dat de huidige verborgen toestand geen regen, geen ongeluk en druk verkeer is. De Markovdeken van regen is verkeer, paraplu en ongeluk. Voor regen waar is de lokale score

Voor regen onwaar is de score $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,2})=\mathrm{0,032}$. Normaliseren geeft $P(r\mid \text{Markovdeken})=\mathrm{0,126}\mathrm{/}\mathrm{0,158}\approx \mathrm{0,797}$. Een uniforme trekking van 0,40 verandert regen daarom in waar. De factor van te laat komen ontbreekt bij deze bijwerking omdat verkeer vast blijft staan en die factor voor beide kandidaatwaarden van regen constant is.

Werk verkeer bij met de nieuwe regenwaarde

De Markovdeken van verkeer is regen, ongeluk en te laat komen. De twee scores zijn $\mathrm{0,7}(\mathrm{0,6})=\mathrm{0,42}$ voor druk verkeer en $\mathrm{0,3}(\mathrm{0,1})=\mathrm{0,03}$ voor geen druk verkeer. De kans op waar is dus $\mathrm{0,42}\mathrm{/}\mathrm{0,45}\approx \mathrm{0,933}$. Bij een bijwerking van ongeluk met regen en druk verkeer vastgezet, is de kans op waar $\mathrm{0,095}\mathrm{/}(\mathrm{0,095}+\mathrm{0,63})\approx \mathrm{0,131}$.

Tel toestanden en geef tijd om te mengen

Na elke bijwerking kan de volledige waardetoekenning als steekproef meetellen, ook bij een stap die de geselecteerde waarde onveranderd laat. Gooi een eerste inloopfase weg om de invloed van de initialisatie te verminderen. De regenfrequentie op lange termijn nadert voor deze zoekvraag ongeveer 0,693 als de keten convergeert.

Aangrenzende toestanden delen bijna al hun waarden en zijn gecorreleerd. Ze bevatten minder onafhankelijke informatie dan hetzelfde aantal onafhankelijke trekkingen. Als alle waarden in de voorwaardelijke kansentabellen strikt tussen 0 en 1 liggen, kunnen geschikte herhaalde bijwerkingen elke toestand bereiken en naar de a-posterioriverdeling convergeren. Deterministische constraints kunnen een keten die één variabele tegelijk bijwerkt vasthouden; bijna deterministische relaties kunnen die zeer langzaam laten bewegen.

Steekproeftrekking uit de a-prioriverdeling trekt uit de gezamenlijke verdeling; verwerping filtert die trekkingen; aannemelijkheidsweging zet waargenomen gegevens vast en weegt waardetoekenningen; Gibbs werkt herhaaldelijk een toestand met vastgezette waarnemingen bij. Als je alleen op ouders conditioneert, krijgt een Gibbsbijwerking de verkeerde lokale verdeling doordat de waargenomen gegevens van kinderen ontbreken.

Kansen beschrijven wat kan gebeuren; nutswaarden beschrijven hoe wenselijk de uitkomsten zijn. Een nutsfunctie kent hogere getallen toe aan uitkomsten die de voorkeur hebben. Een onzekere actie is een loterij, die uitkomsten en hun kansen opsomt.

Middel het nut over mogelijke uitkomsten

Het verwachte nut van een actie is

Vermenigvuldig het nut van elke uitkomst met de kans daarop en tel op. Bij maximaal verwacht nut kies je de actie met het hoogste resultaat. De uitkomst met het hoogste afzonderlijke nut hoeft niet bij de beste actie te horen en de waarschijnlijkste uitkomst alleen bepaalt de keuze niet. Een goede beslissing kan door toeval toch een slechte uitkomst opleveren.

Waarom samenhangende voorkeuren maximaal verwacht nut ondersteunen

De nutstheorie gebruikt deze rationaliteitseisen:

• Ordenbaarheid: elk paar loterijen is vergelijkbaar, waarbij onverschilligheid mogelijk is.
• Transitiviteit: als je A boven B en B boven C verkiest, verkies je A boven C.
• Continuïteit: een tussenliggende uitkomst kan gelijkwaardig zijn aan een loterij tussen betere en slechtere uitkomsten.
• Substitueerbaarheid: een gelijkwaardige uitkomst of loterij kan een andere binnen een grotere loterij vervangen.
• Monotoniciteit: bij loterijen met dezelfde betere en slechtere uitkomsten heeft de grotere kans op de betere uitkomst de voorkeur.
• Ontleedbaarheid: een loterij over loterijen kan worden herleid tot de kansen op de uiteindelijke uitkomsten.

Het resultaat van von Neumann-Morgenstern geeft voorkeuren die aan deze eisen voldoen weer met verwacht nut. Cyclische voorkeuren schenden transitiviteit. Als een agent een klein bedrag betaalt om van B naar A, van A naar C en van C naar B te gaan, brengen herhaalde ruilen de agent terug naar de oorspronkelijke positie terwijl het geld opraakt. Dit is het probleem van de “geldpomp”.

Geld en nut kunnen loterijen anders rangschikken

Vergelijk een zekere betaling van € 400 met 50% kans op € 1.000 en 50% kans op nul. Verwacht geld geeft de voorkeur aan de loterij, waarvan het gemiddelde € 500 is. Voor $U(x)=\sqrt{x}$ is het verwachte nut van de loterij echter $\mathrm{0,5}\sqrt{1.000}+\mathrm{0,5}\sqrt{0}\approx \mathrm{15,81}$, terwijl de zekere betaling 20 geeft. Deze agent kiest € 400.

Het zekerheidsequivalent is het zekere bedrag met het nut van de loterij. Hier is dat $(\mathrm{0,5}\sqrt{1.000}{)}^2=250$. Het verschil tussen verwacht geld en het zekerheidsequivalent is de risicopremie, in dit voorbeeld € 250.

Bij een concave nutsfunctie is een zeker bedrag ter hoogte van het gemiddelde minstens even wenselijk als de loterij met dat gemiddelde. Strikte concaviteit maakt die voorkeur strikt voor een niet-triviale loterij. Een voldoende gunstige risicovolle optie kan nog steeds beter zijn dan een minder waardevol zeker bedrag.

Verander de schaal zonder voorkeuren te veranderen

Als je nut vervangt door $U^{\mathrm{\prime }}(s)=kU(s)+c$ met $k>0$, blijven alle vergelijkingen van verwacht nut behouden. Elke verwachtingswaarde krijgt dezelfde positieve schaling en verschuiving. Een algemene stijgende transformatie behoudt de rangschikking van zekere uitkomsten, maar kan die van loterijen veranderen.

Bij vergelijking van meerdere wenselijke eigenschappen domineert een optie een andere als die op elke eigenschap minstens even goed is en op minstens één beter. Als de voorkeuren die verbeteringen waarderen, kan de gedomineerde optie worden verwijderd zonder exacte gewichten voor de eigenschappen vast te leggen.

Een beslissingsnetwerk, ook wel invloeddiagram genoemd, combineert een kansmodel met keuzes en voorkeuren. Om het op te lossen moet je zowel over onzekere toestanden redeneren als de acties vergelijken die voor de agent beschikbaar zijn.

Lees de drie soorten knopen

Toevalsknopen, meestal ovalen, hebben kansentabellen. Beslissingsknopen, meestal rechthoeken, geven acties weer waarover de agent zeggenschap heeft. Nutsknopen, meestal ruiten, kennen nut toe aan combinaties van ouderwaarden. Een pijl naar een beslissingsknoop geeft informatie aan die beschikbaar is wanneer de keuze wordt gemaakt. Het is geen gewone voorwaardelijke kansafhankelijkheid.

Bij een buitenevenement beïnvloedt regen een voorspelling en het nut van het evenement. Ook de actie beïnvloedt het nut. De voorspelling wijst naar de beslissing als die wordt waargenomen voordat de organisator kiest. Er loopt geen pijl van de actie naar regen: naar binnen gaan verandert het weer niet.

Los op zonder voorspelling

Stel $P(rain)=\mathrm{0,3}$ en gebruik deze nutstabel:

De verwachte nutswaarden zijn $EU(outdoors)=\mathrm{0,7}(100)+\mathrm{0,3}(0)=70$ en $EU(indoors)=\mathrm{0,7}(60)+\mathrm{0,3}(70)=63$. Kies zonder verdere informatie buiten; het maximale verwachte nut is 70. De beslissingsknoop krijgt een gekozen waarde, geen kansentabel om over acties te middelen.

Verwerk een voorspelling

Neem $P(wet\mid rain)=\mathrm{0,8}$ en $P(wet\mid \mathrm{\neg }rain)=\mathrm{0,1}$. De kans op een natte voorspelling is $\mathrm{0,8}(\mathrm{0,3})+\mathrm{0,1}(\mathrm{0,7})=\mathrm{0,31}$. De regel van Bayes geeft $P(rain\mid wet)=\mathrm{0,24}\mathrm{/}\mathrm{0,31}\approx \mathrm{0,774}$. Een droge voorspelling geeft $P(rain\mid dry)=\mathrm{0,06}\mathrm{/}\mathrm{0,69}\approx \mathrm{0,087}$.

Bij een natte voorspelling heeft buiten een verwacht nut van ongeveer 22,6 en binnen van ongeveer 67,7, dus kies je binnen. Bij een droge voorspelling geeft buiten ongeveer 91,3 en binnen ongeveer 60,9, dus kies je buiten. Gebruik na een observatie de a-posteriorikans; als je de a-priorikans behoudt, gooi je de informatie van de voorspelling weg.

Het resulterende beleid is “Kies binnen na een natte voorspelling; kies buiten na een droge voorspelling”. Een beleid koppelt observaties aan acties en kan dus worden vastgelegd voordat de observatie binnenkomt. Een actie is de ene keuze die wordt gemaakt zodra de bijbehorende informatie beschikbaar is.

Bepaal waar de keuze verandert

Laat $p$ de huidige kans op regen zijn. Dan is $EU(outdoors)=100(1-p)$ en $EU(indoors)=60(1-p)+70p=60+10p$. Als je ze gelijkstelt, krijg je $40=110p$, of $p=4\mathrm{/}11\approx \mathrm{0,364}$. Onder deze drempel kies je buiten; erboven binnen; op de drempel zijn de acties gelijkwaardig.

Om een ander beslissingsnetwerk op te lossen, zet je de huidige waargenomen gegevens vast, bekijk je elke actie afzonderlijk, leid je de voor het nut relevante kansverdeling af en bereken je het verwachte nut. Als een actie een onzekere uitkomst verandert, neem je de effecten van die actie op in het kansmodel voordat je verwachtingswaarden vergelijkt. Kies ten slotte de beste actie afzonderlijk voor elke mogelijke observatie die het beleid zal ontvangen.

Een observatie is waardevol als die de agent helpt een betere actie te kiezen. De waarde van perfecte informatie meet de verwachte verbetering door vóór het handelen de waarde van een variabele te leren kennen. “Perfect” beschrijft toegang tot de werkelijke waarde van die variabele; de variabele kan zelf een onvolmaakte voorspelling van iets anders zijn.

Optimaliseer binnen elke mogelijke observatie

Gegeven de huidige waargenomen gegevens $e$ is de waarde van het waarnemen van $E^{\mathrm{\prime }}$

Bepaal eerst het beste verwachte nut als je nu beslist. Werk daarna voor elke mogelijke observatie de kansen bij en kies de beste actie voor die observatie. Middel deze geoptimaliseerde nutswaarden met de kansen op de observaties. Trek het huidige maximale verwachte nut af. Als je eerst één actie kiest en daarna middelt, mis je de mogelijkheid om de actie aan te passen.

Bepaal de waarde van de voorspelling en het weer

Voor het evenementenmodel geeft buiten kiezen zonder voorspelling een maximaal verwacht nut van 70. Natte voorspellingen komen voor met kans 0,31 en leiden tot binnen, met een maximaal verwacht nut van ongeveer 67,74. Droge voorspellingen komen voor met kans 0,69 en leiden tot buiten, met een maximaal verwacht nut van ongeveer 91,30. Als je exacte waarden gebruikt, krijg je

Dus $VPI(F)=84-70=14$ nutseenheden. Als de kosten uitgedrukt als nutsverlies lager zijn dan 14, is het verkrijgen van de voorspelling de moeite waard; bij 14 is de agent onverschillig. Een geldprijs moet eerst op de nutsschaal van de agent worden beoordeeld.

Het weer zelf kennen is nuttiger. Regen leidt tot binnen met nut 70; geen regen leidt tot buiten met nut 100. Het gemiddelde is $\mathrm{0,3}(70)+\mathrm{0,7}(100)=91$, dus $VPI(Rain)=91-70=21$.

Waarom informatie een niet-negatieve verwachte waarde heeft

De agent kan gratis informatie altijd negeren en de oorspronkelijke actie behouden. Optimaliseren na het waarnemen kan het verwachte nut voordat de observatie bekend is daarom nooit verlagen. Als dezelfde actie voor elke mogelijke uitkomst het beste is, heeft informatie waarde nul. Informatie die gegeven de huidige waargenomen gegevens onafhankelijk is van alle voor het nut relevante toevalsvariabelen, heeft in dit beslissingsmodel ook waarde nul.

Een specifieke uitkomst kan toch onwelkom zijn. Na een natte voorspelling is het maximale verwachte nut ongeveer 67,7, lager dan de eerdere 70. Niet-negativiteit betreft het gemiddelde over alle uitkomsten voordat je ze ziet.

Combineer informatie zonder dubbel te tellen

De waarde van perfecte informatie is doorgaans niet additief. De voorspelling alleen is 14 waard en het weer alleen 21, maar beide leren kennen is 21 waard omdat de voorspelling niets toevoegt nadat het weer bekend is.

Na een natte voorspelling voegt het leren kennen van het weer ongeveer 9,03 toe; na een droge ongeveer 6,09. Voordat de voorspelling bekend is, is de verwachte extra waarde $\mathrm{0,31}(\mathrm{9,03})+\mathrm{0,69}(\mathrm{6,09})\approx 7$. De gezamenlijke winst is dus $14+7=21$, gelijk aan eerst het weer leren kennen en daarna nul toevoegen. Het totaal is onafhankelijk van de volgorde als alle observaties aan de actie voorafgaan en elke latere winst met de eerdere informatie wordt beoordeeld.

Een informatieverzamelende agent kan herhaaldelijk de observatie met de grootste positieve waarde van perfecte informatie min de kosten kiezen en handelen wanneer geen observatie meer de moeite waard is. Deze kortzichtige strategie beoordeelt één observatie tegelijk. Twee observaties kunnen samen nuttig zijn, ook als geen van beide afzonderlijk de beste actie verandert, zodat gulzige selectie een waardevol paar kan missen.