Probabilistisches Schließen und bayessche Netze

Ein Agent sieht möglicherweise nur einen Teil seiner Umgebung. Ein Sensor kann verrauscht sein und eine Aktion kann mehrere Ergebnisse haben. Mit Wahrscheinlichkeiten kann der Agent jeder Möglichkeit einen Grad der Überzeugung zuordnen und seine Annahmen bei neuer Information anpassen.

Welten, Ereignisse und Variablen

Der Ergebnisraum $\mathrm{\Omega }$ führt jedes mögliche Ergebnis auf. Die Ergebnisse schließen einander aus und decken alle Möglichkeiten ab: Genau eines tritt ein. Ein Ereignis ist eine Menge solcher Ergebnisse, etwa „Der Bus hat Verspätung“. Seine Wahrscheinlichkeit ist die Summe der Wahrscheinlichkeiten seiner Ergebnisse.

Eine Zufallsvariable ordnet jedem Ergebnis einen Wert zu. Ihr Wertebereich führt die möglichen Werte auf. Zum Beispiel hat $Weather$ den Wertebereich $\{sun,cloud,rain\}$. Schreibe Variablen groß und Werte klein. Für die boolesche Variable $Rain$ bedeutet $r$ wahr und $\mathrm{\neg }r$ falsch. Das Komma in $P(r,t)$ bedeutet „und“.

Wahrscheinlichkeiten liegen zwischen 0 und 1, und die Wahrscheinlichkeiten aller Ergebnisse ergeben zusammen 1. Für Gegenereignisse gilt $P(\mathrm{\neg }a)=1-P(a)$. Eine Verteilung führt die Wahrscheinlichkeit jedes Werts einer Variablen auf; eine A-priori-Wahrscheinlichkeit beschreibt eine Annahme, bevor die betrachtete Evidenz berücksichtigt wird.

Eine gemeinsame Tabelle lesen

Eine gemeinsame Verteilung gibt die Wahrscheinlichkeit jeder Wertekombination an. Hier ist ein Wetter- und Busmodell:

Die sechs Zellen sind die sechs möglichen Welten und ergeben zusammen 1. Eine Zeilensumme ist die Wahrscheinlichkeit des jeweiligen Wetters; eine Zeile muss also nicht die Summe 1 ergeben. Für Regen gilt $P(rain)=\mathrm{0,08}+\mathrm{0,12}=\mathrm{0,20}$. Die Spalte für Verspätung ergibt $P(late)=\mathrm{0,10}+\mathrm{0,12}+\mathrm{0,12}=\mathrm{0,34}$.

Diese Operation ist Marginalisierung oder Aussummieren. Um $X$ zu behalten und $Y$ zu entfernen, verwende $P(x)={\sum }_{y}P(x,y)$. Addiere über jeden Wert der entfernten Variablen, bei booleschen Variablen auch über falsche Werte.

Eine Überschneidung einmal zählen

Das Ereignis „Regen oder Verspätung“ umfasst jede Zelle in der Regenzeile oder der Verspätungsspalte. Seine Wahrscheinlichkeit ist

Die Subtraktion entfernt die doppelt gezählte Überschneidung. Allgemein gilt $P(a\vee b)=P(a)+P(b)-P(a,b)$. Das einfache Addieren der Randwahrscheinlichkeiten ergäbe 0,54 und würde die Welt mit Regen und Verspätung doppelt zählen.

Warum vollständige Tabellen aufwendig werden

Eine vollständige gemeinsame Tabelle kann jede Wahrscheinlichkeitsanfrage zu ihren Variablen beantworten, wächst aber schnell. Jede zusätzliche boolesche Variable verdoppelt die Zahl der Welten. Bei $n$ booleschen Variablen gibt es $2^n$ Einträge und $2^n-1$ freie Zahlen, da der letzte Eintrag durch die Summe 1 festgelegt ist. Dreißig boolesche Variablen benötigen 1.073.741.824 Einträge. Kompakte Modelle speichern stattdessen lokale Abhängigkeiten, statt jede Welt einzeln aufzuführen.

Ein verspäteter Bus verändert, welche Wetterlagen wahrscheinlich erscheinen. Die bedingte Wahrscheinlichkeit betrachtet die Welten, die mit einer Beobachtung vereinbar sind, und misst deren relative Anteile. Die Wahrscheinlichkeit nach Berücksichtigung der Evidenz ist eine A-posteriori-Wahrscheinlichkeit.

Den Nenner an die Evidenz binden

Für Evidenz mit positiver Wahrscheinlichkeit gilt:

Im Wetter- und Busmodell sind die Verspätungseinträge für Sonne, Wolken und Regen 0,10, 0,12 und 0,12. Ihre Summe ist 0,34. Somit gilt $P(rain\mid late)=\mathrm{0,12}\mathrm{/}\mathrm{0,34}\approx \mathrm{0,353}$. Die umgekehrte Frage ergibt $P(late\mid rain)=\mathrm{0,12}\mathrm{/}\mathrm{0,20}=\mathrm{0,6}$. Beide nutzen dieselbe Zelle der gemeinsamen Tabelle, teilen aber jeweils durch die Wahrscheinlichkeit ihrer eigenen Evidenz.

Die gesamte bedingte Verteilung ist $P(Weather\mid late)\approx ⟨\mathrm{0,294};\mathrm{0,353};\mathrm{0,353}⟩$. Diese Einträge ergeben zusammen 1, weil sie alternative Wetterwerte bei einer festen Beobachtung beschreiben. Die drei Likelihoods $P(late\mid sun)=\mathrm{0,2}$, $P(late\mid cloud)=\mathrm{0,4}$ und $P(late\mid rain)=\mathrm{0,6}$ haben unterschiedliche Bedingungen und müssen nicht die Summe 1 ergeben.

Produkte und Ketten

Durch Umstellen der Definition erhält man den Multiplikationssatz:

Wiederholte Anwendung ergibt die Kettenregel:

Jede Variablenreihenfolge funktioniert. Für diese Identität ist keine Unabhängigkeit nötig; später können wir damit aber die Bedingungslisten verkürzen.

Auswählen, summieren und normieren

Für die Anfragevariable $X$, die Evidenz $e$ und die verborgenen Variablen $Y$ gilt bei der Aufzählung:

Wähle zuerst die Welten, die zur Evidenz passen. Summiere dann alle verborgenen Variablen aus und behalte für jeden Anfragewert eine eigene Summe. Teile diese Summen schließlich durch ihre Gesamtsumme. Die Normierungskonstante $\alpha$ ist der Kehrwert dieser Summe, also von $P(e)$.

Betrachte die booleschen Variablen Grippe ($F$), Fieber ($V$) und Husten ($K$). Ihre vollständige gemeinsame Tabelle lautet:

Um $P(F\mid v)$ zu bestimmen, behalte die Fieberzeilen und summiere Husten aus. Die Summen sind $\mathrm{0,056}+\mathrm{0,024}=\mathrm{0,08}$ für Grippe und $\mathrm{0,018}+\mathrm{0,072}=\mathrm{0,09}$ für keine Grippe. Normiere durch 0,17 und erhalte $P(f\mid v)\approx \mathrm{0,471}$.

Wird auch Husten beobachtet, behalte nur die beiden Zeilen mit Fieber und Husten. Nun gilt $P(f\mid v,k)=\mathrm{0,056}\mathrm{/}\mathrm{0,074}\approx \mathrm{0,757}$. Für Fieber ohne Husten gilt $P(f\mid v,\mathrm{\neg }k)=\mathrm{0,024}\mathrm{/}\mathrm{0,096}=\mathrm{0,25}$. Das Aussummieren von Husten würde diese zusätzliche Beobachtung verlieren. Eine nicht normierte Summe wie 0,08 ist eine gemeinsame Wahrscheinlichkeit, nicht die gesuchte bedingte Wahrscheinlichkeit.

Ein Agent weiß oft, wie eine Ursache eine Beobachtung hervorbringt, muss aber in die andere Richtung schließen. Ein Fehlermodell kann beschreiben, wie oft ein beschädigtes Bauteil eine Warnung auslöst. Nach der Warnung braucht der Agent die Wahrscheinlichkeit eines Schadens.

Eine bedingte Wahrscheinlichkeit richtig umkehren

Die beiden Ausdrücke des Multiplikationssatzes für eine gemeinsame Wahrscheinlichkeit ergeben den Satz von Bayes:

Dabei ist $P(c)$ die A-priori-Wahrscheinlichkeit, $P(e\mid c)$ die Likelihood und $P(c\mid e)$ die A-posteriori-Wahrscheinlichkeit. Der Nenner umfasst alle Möglichkeiten, auf denen die Evidenz eintreten kann. Für eine boolesche Ursache ergibt der Satz der totalen Wahrscheinlichkeit:

Bei mehr als zwei Ursachenwerten nimm für jeden Wert einen Term auf. Du kannst auch für jede Ursache einen Wert aus Likelihood mal A-priori-Wahrscheinlichkeit berechnen und diese Werte normieren.

Ein Beispiel mit einer seltenen Erkrankung

Angenommen, eine Erkrankung betrifft 1 % einer Bevölkerung. Ein Test fällt bei 90 % der Erkrankten und 5 % der Gesunden positiv aus. Die Wahrscheinlichkeit eines positiven Ergebnisses ist

Die Wahrscheinlichkeit, krank und positiv getestet zu sein, beträgt 0,009, also

Natürliche Häufigkeiten machen den Nenner leichter verständlich. Unter 10.000 Menschen sind 100 krank, und 90 davon werden positiv getestet. Von 9.900 Gesunden werden 495 positiv getestet. Insgesamt gibt es 585 positive Ergebnisse; 90 davon gehören zu Erkrankten.

Die Sensitivität von 90 % beantwortet die Frage „Wie oft wird eine kranke Person positiv getestet?“. Sie beantwortet nicht „Wie oft ist eine positiv getestete Person krank?“. Vernachlässigung der Basisrate gewichtet die A-priori-Wahrscheinlichkeit zu wenig. Bei einer seltenen Erkrankung sind zunächst weit weniger Menschen krank, sodass falsch positive Ergebnisse aus der größeren Gruppe Gesunder die richtig positiven überwiegen können. Bleiben Sensitivität und Falsch-positiv-Rate gleich, verändert eine andere Häufigkeit der Erkrankung dennoch die A-posteriori-Wahrscheinlichkeit.

Ein negatives Ergebnis nutzt die komplementären Likelihoods:

Bei neuer Evidenz erneut aktualisieren

Die A-posteriori-Wahrscheinlichkeit einer Beobachtung wird zur A-priori-Wahrscheinlichkeit für die nächste. Ist ein zweites Testergebnis bei gegebenem Erkrankungsstatus vom ersten bedingt unabhängig, ergibt ein weiteres positives Ergebnis:

Runde die erste A-posteriori-Wahrscheinlichkeit bei sequenziellen Rechnungen nicht. Bedingte Unabhängigkeit ist entscheidend: Wiederholte Messungen desselben defekten Sensors können einen gemeinsamen Fehler haben. Ihre Likelihoods als unabhängige Evidenz zu multiplizieren, kann die Aktualisierung übertreiben.

Hintergrundinformationen bleiben in jeder relevanten Bedingung erhalten:

So kann ein Agent seine Einschätzung innerhalb der bereits bekannten Bevölkerung oder Situation mit seiner aktuellen A-priori-Wahrscheinlichkeit und den passenden Likelihoods aktualisieren.

Manche Beobachtungen verändern gegenseitig ihre Wahrscheinlichkeiten; andere liefern keine zusätzliche Information, sobald eine relevante Bedingung bekannt ist. Unabhängigkeit zeigt, wann ein langer Wahrscheinlichkeitsausdruck durch kleinere Teile ersetzt werden kann.

Unabhängigkeit ist eine Aussage über jeden Wert

Ereignisse sind unabhängig, wenn $P(a,b)=P(a)P(b)$ gilt. Für Variablen muss diese Gleichung für jedes Wertepaar gelten. Ein einziges Paar, für das sie nicht gilt, belegt Abhängigkeit. In der Wettertabelle gilt $P(rain,late)=\mathrm{0,12}$, während $P(rain)P(late)=\mathrm{0,20}(\mathrm{0,34})=\mathrm{0,068}$ ist. Wetter und Busstatus sind also abhängig.

Unvereinbare Ereignisse mit positiven Wahrscheinlichkeiten sind abhängig: Erfährt man, dass eines eingetreten ist, wird die Wahrscheinlichkeit des anderen null. Unabhängige Ereignisse können zusammen eintreten. Sind $n$ boolesche Variablen alle wechselseitig unabhängig, werden nur $n$ Wahrscheinlichkeiten benötigt, gegenüber $2^n-1$ für eine uneingeschränkte gemeinsame Tabelle.

Wissen, was festgehalten wird

Bedingte Unabhängigkeit, geschrieben $X\perp Y\mid Z$, bedeutet:

Die Gleichung gilt für jede relevante Wertekombination. Gleichwertig gilt: Ist $Z$ bekannt, liefert die Kenntnis von $Y$ keine zusätzliche Information über $X$.

Im Grippemodell gilt $P(k\mid v,f)=P(k\mid f)=\mathrm{0,7}$ und $P(k\mid v,\mathrm{\neg }f)=P(k\mid \mathrm{\neg }f)=\mathrm{0,2}$. Fieber und Husten sind bei gegebenem Grippestatus bedingt unabhängig. Ohne diese Bedingung sind sie abhängig: $P(k)=\mathrm{0,25}$, während $P(k\mid v)=\mathrm{0,074}\mathrm{/}\mathrm{0,17}\approx \mathrm{0,435}$ gilt. Fieber verändert die Einschätzung von Grippe und damit die Einschätzung von Husten.

Unabhängigkeit ohne Evidenz und Unabhängigkeit bei gegebener Evidenz sind getrennte Aussagen. Die Beobachtung einer gemeinsamen Wirkung kann sogar zwei zuvor unabhängige Ursachen abhängig machen.

Mit Naive Bayes klassifizieren

Ein Naive-Bayes-Modell nimmt an, dass Merkmale bei gegebener Klasse bedingt unabhängig sind. Seine A-posteriori-Verteilung lautet:

Eine boolesche Klasse mit $n$ booleschen Merkmalen benötigt $1+2n$ Wahrscheinlichkeiten. Die Annahme kann unvollkommen sein und trotzdem eine nützliche Klassifikation ermöglichen; korrelierte Merkmale können aber zu übermäßig sicheren Wahrscheinlichkeiten führen.

Für Spam sei $P(spam)=\mathrm{0,3}$. Das Wort „Angebot“ erscheint mit Wahrscheinlichkeit 0,4 in Spam und 0,05 in regulären Nachrichten. Das Wort „Gewinner“ erscheint mit den Wahrscheinlichkeiten 0,2 und 0,01. Sind beide Wörter vorhanden, sind die Werte $\mathrm{0,3}(\mathrm{0,4})(\mathrm{0,2})=\mathrm{0,024}$ für Spam und $\mathrm{0,7}(\mathrm{0,05})(\mathrm{0,01})=\mathrm{0,00035}$ für reguläre Nachrichten. Normierung ergibt $P(spam\mid o,w)\approx \mathrm{0,986}$.

Auch das Fehlen eines Merkmals liefert Evidenz. Ist „Angebot“ vorhanden, aber „Gewinner“ nicht, werden die Werte zu $\mathrm{0,3}(\mathrm{0,4})(\mathrm{0,8})=\mathrm{0,096}$ und $\mathrm{0,7}(\mathrm{0,05})(\mathrm{0,99})=\mathrm{0,03465}$. Das ergibt eine A-posteriori-Wahrscheinlichkeit für Spam von etwa 0,735. Nutze für ein fehlendes boolesches Merkmal das Komplement der Likelihood. Eine Likelihood von null macht den gesamten Klassenwert null. Daher sollte ein mögliches Ereignis nicht allein deshalb null erhalten, weil es in einer kleinen Stichprobe fehlte.

Ein bayessches Netz stellt eine gemeinsame Verteilung mit einem gerichteten azyklischen Graphen und lokalen Wahrscheinlichkeitstabellen dar. Jeder Knoten ist eine Zufallsvariable. Ein Pfeil in einen Knoten kennzeichnet einen seiner Elternknoten; folgt man den Pfeilen, darf man nie zum Ausgangsknoten zurückgelangen.

Ein Pendelmodell

Verwende fünf boolesche Variablen: Regen ($R$), Unfall ($A$), dichten Verkehr ($T$), Verspätung ($L$) und das Mitführen eines Schirms ($U$). Die Pfeile sind $R\to T$, $A\to T$, $T\to L$ und $R\to U$. Regen und Unfall haben die A-priori-Wahrscheinlichkeiten $P(r)=\mathrm{0,2}$ und $P(a)=\mathrm{0,1}$.

Die bedingte Wahrscheinlichkeitstabelle (CPT) des Verkehrs hängt von beiden Elternknoten ab:

Die übrigen Tabellen ergeben $P(l\mid t)=\mathrm{0,6}$, $P(l\mid \mathrm{\neg }t)=\mathrm{0,1}$, $P(u\mid r)=\mathrm{0,9}$ und $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$. Jede Belegung der Elternknoten wählt eine Verteilung über die Werte des Kindknotens aus. Für boolesche Knoten wird nur die Wahrscheinlichkeit für wahr gespeichert; die Wahrscheinlichkeit für falsch ist ihr Komplement. Somit gilt $P(\mathrm{\neg }t\mid r,\mathrm{\neg }a)=\mathrm{0,3}$.

Die Wahrscheinlichkeit einer vollständigen Welt berechnen

Das Netz definiert seine gemeinsame Verteilung durch

Für Regen, keinen Unfall, dichten Verkehr, Verspätung und einen Schirm wähle aus jedem Knoten einen Eintrag:

Die Faktoren beschreiben jeweils Regen, keinen Unfall, Verkehr bei diesen Werten der Elternknoten, Verspätung bei dichtem Verkehr und das Mitführen eines Schirms bei Regen. Wird ein Knoten ausgelassen, ist das Produkt unvollständig. Die Wahl von 0,95 für den Verkehr würde auch einen Unfall beschreiben und damit nicht zur betrachteten Welt passen.

Die Formel folgt aus der Kettenregel in einer topologischen Ordnung, in der Elternknoten vor Kindknoten stehen. Die bedingten Unabhängigkeiten des Netzes verkürzen jede Bedingung von allen vorangehenden Variablen auf die Elternknoten.

Parameter zählen und Randwahrscheinlichkeiten unterscheiden

Ein boolescher Knoten mit $k$ booleschen Elternknoten benötigt $2^k$ freie Wahrscheinlichkeiten. Allgemeiner benötigt ein Knoten mit $d$ Werten und $k$ Elternknoten mit je $d$ Werten $(d-1)d^k$ Werte. Das Pendelnetz benötigt $1+1+4+2+2=10$ Zahlen; eine vollständige gemeinsame Verteilung über seine fünf booleschen Variablen benötigt 31. Dreißig boolesche Knoten mit jeweils höchstens fünf Elternknoten benötigen höchstens 960 Zahlen, gegenüber mehr als einer Milliarde für eine uneingeschränkte vollständige gemeinsame Verteilung.

Ein CPT-Eintrag beantwortet eine Frage bei festgelegten Werten aller Elternknoten. Für eine Randwahrscheinlichkeit mittle über die fehlenden Werte der Elternknoten. Hier gilt

wobei die vier Terme die Verkehrszeilen mit den Wahrscheinlichkeiten ihrer Elternknoten gewichten. Ebenso gilt $P(t\mid r)=\mathrm{0,1}(\mathrm{0,95})+\mathrm{0,9}(\mathrm{0,7})=\mathrm{0,725}$. Das ist nicht der einzelne Zeilenwert 0,7.

Pfeile verlaufen oft von der Ursache zur Wirkung, weil das Modell dadurch kompakt und verständlich wird. Formal kodieren sie eine Faktorisierung und Unabhängigkeitsaussagen. Ein umgekehrter Graph mit zwei Knoten kann dieselbe gemeinsame Verteilung mit anderen Tabellen darstellen; ein Pfeil allein belegt keine Kausalität.

Ein nützliches Netz lässt unnötige Abhängigkeiten weg und behält die für die Verteilung nötigen bei. Wenige Elternknoten können viele Tabelleneinträge sparen, aber jede Auslassung legt das Modell auf eine Unabhängigkeitsaussage fest.

Das Netz in einer Reihenfolge aufbauen

Wähle Variablen und ihre Wertebereiche und ordne sie dann an. Wähle für jede Variable eine minimale Menge früherer Variablen, die sie von den anderen früheren Variablen unabhängig macht. Füge Pfeile von diesen Elternknoten hinzu und fülle die CPT anhand von Expertenschätzungen oder aus Häufigkeiten geschätzten Wahrscheinlichkeiten aus.

Eine Reihenfolge mit Ursachen zuerst ergibt für das Pendelmodell vier Pfeile und zehn freie Wahrscheinlichkeiten. Eine andere zulässige Reihenfolge ist $L,T,U,R,A$ mit den Elternmengen $T:\{L\}$, $U:\{T\}$, $R:\{T,U\}$ und $A:\{T,R\}$. Sie benötigt sechs Pfeile und $1+2+2+4+4=13$ Zahlen. Bei gegebener Verkehrslage verändert Regen die Einschätzung eines Unfalls, daher muss Regen in dieser Reihenfolge unter den Elternknoten des Unfalls bleiben.

Jede Reihenfolge kann die Verteilung darstellen, wenn jeder Knoten genügend Elternknoten erhält. Gibt man jedem Knoten alle früheren Knoten als Elternknoten, funktioniert das immer, bietet aber keine Komprimierung. Eine diagnostische Reihenfolge kann außerdem schwerer einzuschätzende Wahrscheinlichkeiten verlangen, etwa Regen bei gegebenem Verkehr und Schirm. Ein fehlender benötigter Elternknoten erzwingt eine falsche Unabhängigkeit; ein unnötiger Elternknoten vergrößert die Tabelle.

Zwei lokale Unabhängigkeitsregeln

Die lokale Markov-Eigenschaft besagt, dass ein Knoten bei gegebenen Elternknoten von seinen Nichtnachkommen unabhängig ist. Im Pendelnetz gilt $L\perp \{R,A,U\}\mid T$ und $U\perp \{A,T,L\}\mid R$. Ist die Verkehrslage bekannt, liefern die anderen Variablen keine weitere Information über eine Verspätung.

Die Markov-Decke eines Knotens enthält seine Elternknoten, seine Kindknoten und die anderen Elternknoten seiner Kindknoten. Bei gegebenen Werten dieser Variablen ist der Knoten von jeder Variablen außerhalb der Decke unabhängig. Die Decke von Regen ist $\{T,U,A\}$: Der Unfall gehört dazu, weil er der andere Elternknoten des Verkehrs ist. Die Decke des Verkehrs ist $\{R,A,L\}$, die der Verspätung enthält nur $\{T\}$. Die Decke ermöglicht lokale Aktualisierungen auch in einem großen Netz.

Eine große Tabelle durch Struktur ersetzen

Ein deterministischer Knoten ist eine feste Funktion seiner Elternknoten, etwa $Late=Traffic\vee Strike$. Seine Zeilen enthalten Nullen und Einsen. Ein Noisy-OR lässt jede zutreffende Ursache unabhängig fehlschlagen. Hat Ursache $i$ die Hemmungswahrscheinlichkeit $q_i$, bleibt die Wirkung nur aus, wenn alle aktiven Ursachen fehlschlagen:

Angenommen, ein Unfall verursacht mit Wahrscheinlichkeit 0,2 keinen Stau und eine Baustelle mit Wahrscheinlichkeit 0,4 keinen Stau. Ein Unfall allein ergibt eine Stauwahrscheinlichkeit von 0,8; eine Baustelle allein ergibt 0,6. Treten beide auf, beträgt die Wahrscheinlichkeit für keinen Stau $\mathrm{0,2}(\mathrm{0,4})=\mathrm{0,08}$, also ist die Stauwahrscheinlichkeit 0,92.

Einfaches Noisy-OR ergibt keine Wirkung, wenn keine Ursache aktiv ist. Eine Leckursache, dargestellt als stets vorhandene Ursache, lässt die Wirkung durch nicht aufgeführte Ursachen entstehen. Das Modell benötigt eine Hemmungswahrscheinlichkeit pro Ursache statt einer uneingeschränkten Tabelle mit $2^k$ Zeilen. Diese Ersparnis beruht auf unabhängigem Fehlschlagen der Ursachen; für beliebige Wechselwirkungen ist ein umfangreicheres Modell nötig.

d-Separation findet bedingte Unabhängigkeiten, die der Graph eines Netzes garantiert. Sie betrachtet Pfade, ohne zu verlangen, dass die Pfeile in Laufrichtung zeigen. Die Pfeilspitzen sind dennoch wichtig, weil sie das Verhalten jedes mittleren Knotens bestimmen.

Drei Pfadmuster

In einer Kette schirmt die Kenntnis der mittleren Variablen den Einfluss der früheren Variablen ab. In $R\to T\to L$ liefert Regen keine zusätzliche Information über eine Verspätung, sobald die Verkehrslage bekannt ist. Bei einer Gabel bewirkt die Kenntnis der gemeinsamen Ursache dasselbe: Ein Schirm sagt nichts Weiteres über den Verkehr aus, sobald Regen bekannt ist.

Ein Collider oder eine gemeinsame Wirkung funktioniert umgekehrt. Der Pfad $R\to T\leftarrow A$ ist ohne Evidenz zu Verkehr oder seinen Nachkommen blockiert. Die Beobachtung des Verkehrs oder der nachgelagerten Verspätung öffnet den Collider. Zuvor unabhängige Ursachen können dann Informationen übereinander liefern.

Wegerklären

Im Pendelmodell gilt $P(a\mid r)=P(a)=\mathrm{0,1}$. Dichter Verkehr erhöht die Unfallwahrscheinlichkeit auf etwa 0,235. Kommt Regen hinzu, sinkt sie auf $P(a\mid t,r)\approx \mathrm{0,131}$; kommt die Information hinzu, dass es nicht regnet, ergibt sich $P(a\mid t,\mathrm{\neg }r)\approx \mathrm{0,308}$. Regen erklärt einen Teil des beobachteten Verkehrs, sodass ein Unfall als Erklärung weniger nötig ist. Das ist Wegerklären.

Jeden Pfad prüfen

Um $X\perp Y\mid Z$ zu prüfen:

1. Liste jeden ungerichteten Pfad zwischen den Anfragevariablen auf.
2. Bestimme an jedem inneren Knoten, ob der Pfad dort einen Collider oder einen Nicht-Collider bildet.
3. Blockiere einen Pfad, wenn er einen beobachteten Nicht-Collider oder einen Collider enthält, bei dem weder der Knoten selbst noch ein Nachkomme beobachtet wird.
4. Folgere d-Separation nur, wenn jeder Pfad blockiert ist.

Für Schirm und Unfall ist der einzige Pfad $U\leftarrow R\to T\leftarrow A$. Ohne Evidenz blockiert der Verkehr ihn, also gilt $U\perp A$. Bei gegebener Verspätung öffnet sich der Collider beim Verkehr und Regen bleibt unbeobachtet, sodass der Pfad aktiv wird. Das Zahlenmodell ergibt $P(u\mid l)\approx \mathrm{0,434}$, aber $P(u\mid a,l)\approx \mathrm{0,356}$.

Werden sowohl Verspätung als auch Regen beobachtet, bleibt der Collider beim Verkehr offen, aber Regen blockiert den Pfad als beobachteter Nicht-Collider. Daher gilt $U\perp A\mid L,R$. Ein offener Abschnitt hebt eine Blockade an anderer Stelle nicht auf.

Schirm und Verspätung haben den Pfad $U\leftarrow R\to T\to L$. Er ist ohne Evidenz aktiv und wird durch Regen oder Verkehr blockiert. Zum Beispiel gilt $P(l\mid u,r)=P(l\mid r)=\mathrm{0,4625}$.

Die Garantie des Graphen deuten

d-Separation ist korrekt: Die Unabhängigkeit gilt für jede Verteilung, die dem Graphen entspricht. Ein aktiver Pfad bedeutet, dass Unabhängigkeit nicht garantiert ist. Bestimmte CPT-Werte können die Variablen dennoch zufällig unabhängig machen. In einem Graphen mit mehreren Pfaden genügt es nicht, einen blockierten Pfad zu prüfen; ein anderer kann aktiv bleiben.

Ein Netz speichert eine gemeinsame Verteilung in lokalen Teilen. Exakte Inferenz kombiniert diese Teile zur Beantwortung einer Anfrage und summiert über Variablen, deren Werte unbekannt bleiben. Die Aufzählung ist der direkte Weg dazu.

Die drei Rollen der Variablen unterscheiden

In $P(X\mid e)$ ist $X$ die Anfragevariable und $e$ legt die Evidenz fest. Jede andere Variable ist verborgen. Setze das Produkt des Netzes in die allgemeine Aufzählungsformel ein:

Berechne für jeden Wert der Anfragevariablen eine nicht normierte Summe und teile sie dann durch ihre Gesamtsumme. Evidenzwerte bleiben in jedem Produkt fest. Verborgene Variablen durchlaufen ihre gesamten Wertebereiche.

Im Pendelmodell mit den Pfeilen $R\to T\leftarrow A$, $T\to L$ und $R\to U$ verbirgt die Anfrage $P(R\mid l)$ Unfall, Verkehr und Schirm. Jeder vollständige Term nutzt $P(R)P(A)P(T\mid R,A)P(l\mid T)P(U\mid R)$.

Ein irrelevantes Blatt entfernen

Der Schirm hat keinen beobachteten Nachkommen und ist weder Anfrage noch Evidenz. Das Summieren seiner CPT über beide Werte ergibt für jeden Regenwert ${\sum }_{u^{\mathrm{\prime }}}P(u^{\mathrm{\prime }}\mid r)=1$. Sein Beitrag entfällt.

Allgemeiner behält man Anfragevariablen, Evidenzvariablen und alle ihre Vorfahren. Andere Variablen können entfernt werden, indem man zuerst irrelevante Blätter aussummiert und sich dann rückwärts vorarbeitet. Das ist eine Aussage über ihren Beitrag zu dieser Anfrage; ein unbeobachteter Knoten kann bei einer anderen Anfrage wichtig sein.

Die beiden Summen für Regen berechnen

Die Pendeltabellen ergeben $P(r)=\mathrm{0,2}$, $P(a)=\mathrm{0,1}$, Verkehrswahrscheinlichkeiten von 0,95, 0,7, 0,8 und 0,2 für die Kombinationen der Elternknoten $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$ und Verspätungswahrscheinlichkeiten von 0,6 bei Verkehr und 0,1 ohne Verkehr.

Für Regen und einen Unfall summiere die Verkehrsalternativen: $\mathrm{0,95}(\mathrm{0,6})+\mathrm{0,05}(\mathrm{0,1})=\mathrm{0,575}$. Für Regen ohne Unfall ist das Ergebnis $\mathrm{0,7}(\mathrm{0,6})+\mathrm{0,3}(\mathrm{0,1})=\mathrm{0,45}$. Gewichte mit den Unfallwahrscheinlichkeiten und dann mit der Regenwahrscheinlichkeit:

Ohne Regen sind die entsprechenden inneren Summen 0,5 und 0,2. Das ergibt:

Normiere durch $\mathrm{0,0925}+\mathrm{0,184}=\mathrm{0,2765}$. Die Antwort ist $P(R\mid l)\approx ⟨\mathrm{0,335};\mathrm{0,665}⟩$ für wahr und falsch. Die Angabe 0,0925 würde das gemeinsame Ereignis vor der Bedingung angeben.

Summen an ihre Abhängigkeiten binden

Ein Faktor darf nur dann vor eine Summe gezogen werden, wenn keines seiner Argumente von der summierten Variablen abhängt. Zum Beispiel kann $P(r)$ vor die Summe über Unfälle gezogen werden; $P(t\mid r,a^{\mathrm{\prime }})$ nicht, weil der Unfall ein Argument für einen Elternknoten ist.

Wird der Schirm beobachtet, fällt er beim Summieren nicht mehr weg. Mit $P(u\mid r)=\mathrm{0,9}$ und $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$ ist die neue A-posteriori-Wahrscheinlichkeit $\mathrm{0,08325}\mathrm{/}(\mathrm{0,08325}+\mathrm{0,0368})\approx \mathrm{0,693}$. Aufzählung kann als Tiefensuche mit wenig Speicher ablaufen, besucht aber exponentiell viele verborgene Belegungen und wiederholt Teilrechnungen.

Aufzählung wiederholt Arbeit, weil viele vollständige Welten dieselbe Teilrechnung enthalten. Variablenelimination (VE) speichert diese Teilergebnisse als Faktoren und verwendet sie wieder. Sie berechnet dieselbe exakte A-posteriori-Verteilung in einer anderen Rechenreihenfolge.

Faktoren, Multiplikation und Evidenz

Ein Faktor ordnet Belegungen seiner Variablen nichtnegative Zahlen zu. CPTs sind Ausgangsfaktoren, Zwischenfaktoren müssen aber nicht die Summe 1 ergeben. Wende Evidenz an, indem du den beobachteten Wert behältst. Bei Evidenz für Verspätung ist $P(l\mid T)$ ein Faktor über den Verkehr mit den Einträgen 0,6 und 0,1.

Das Multiplizieren von Faktoren multipliziert passende Einträge und nutzt die Vereinigung ihrer Variablenmengen. Die Multiplikation von $P(A)$ und $P(T\mid R,A)$ ergibt einen Faktor über Regen, Unfall und Verkehr. Das Aussummieren des Unfalls addiert Einträge, die sich nur im Unfallwert unterscheiden.

Multipliziere für jede verborgene Variable alle Faktoren, die sie enthalten, summiere sie aus und ersetze diese Faktoren durch das Ergebnis. Behalte Faktoren, die sie nicht enthalten. Multipliziere am Ende die verbleibenden Faktoren und normiere über die Anfragewerte.

Unfall, dann Verkehr eliminieren

Für $P(R\mid l)$ entferne das unbeobachtete Blatt Schirm. Beginne mit $P(R)$, $P(A)$, $P(T\mid R,A)$ und $P(l\mid T)$. Die Elimination des Unfalls ergibt:

Die Werte für dichten Verkehr sind $f_1(r,t)=\mathrm{0,1}(\mathrm{0,95})+\mathrm{0,9}(\mathrm{0,7})=\mathrm{0,725}$ und $f_1(\mathrm{\neg }r,t)=\mathrm{0,1}(\mathrm{0,8})+\mathrm{0,9}(\mathrm{0,2})=\mathrm{0,26}$. Die Werte für keinen dichten Verkehr sind 0,275 und 0,74.

Eliminiere nun den Verkehr:

Das ergibt $f_2(r)=\mathrm{0,725}(\mathrm{0,6})+\mathrm{0,275}(\mathrm{0,1})=\mathrm{0,4625}$ und $f_2(\mathrm{\neg }r)=\mathrm{0,26}(\mathrm{0,6})+\mathrm{0,74}(\mathrm{0,1})=\mathrm{0,23}$. Die Multiplikation mit der A-priori-Wahrscheinlichkeit für Regen ergibt $⟨\mathrm{0,0925};\mathrm{0,184}⟩$. Teile durch 0,2765 und erhalte $⟨\mathrm{0,335};\mathrm{0,665}⟩$.

Auch die Elimination des Verkehrs zuerst funktioniert. Der Faktor $g(R,A)={\sum }_{t^{\mathrm{\prime }}}P(t^{\mathrm{\prime }}\mid R,A)P(l\mid t^{\mathrm{\prime }})$ hat die Einträge 0,575, 0,45, 0,5 und 0,2. Die anschließende Gewichtung mit der A-priori-Wahrscheinlichkeit für einen Unfall liefert dieselben beiden Likelihoods für die Verspätung.

Eine Reihenfolge mit kleinen Faktoren wählen

Ein Faktor über $k$ Variablen mit je $d$ Werten hat $d^k$ Einträge. Der größte Zwischenfaktor bestimmt meist den Aufwand. Angenommen, das verborgene $Z$ zeigt auf boolesche Variablen $X_1,\dots ,X_n$, die jeweils einen beobachteten Kindknoten $Y_i$ haben, und die Anfrage gilt $X_n$. Eliminiert man zuerst $Z$, entsteht durch Multiplikation eine Tabelle über $Z,X_1,\dots ,X_n$; danach bleiben $2^n$ Einträge. Eliminiert man stattdessen zuerst die anderen $X_i$, wird jeder Zweig auf einen Faktor über $Z$ reduziert; der größte durch Multiplikation entstehende Faktor umfasst nur $Z,X_i$ und hat vier Einträge.

Ein Polybaum hat höchstens einen ungerichteten Pfad zwischen je zwei Knoten. Bei guter Reihenfolge ist die Inferenz linear in der Gesamtgröße der CPTs. Allgemeine exakte Inferenz und die Suche nach der optimalen Eliminationsreihenfolge sind NP-schwer. Eine praktische Heuristik wählt eine Variable, die als Nächstes einen kleinen Faktor erzeugt. Behalte die Anfragevariable bis zur Normierung. Die Multiplikation eines ganzen Faktors mit einer positiven Konstante lässt das normierte Ergebnis unverändert.

Sind exakte Summen zu aufwendig, kann ein Agent Belegungen simulieren und Wahrscheinlichkeiten anhand ihrer Häufigkeiten schätzen. Die Qualität der Näherung hängt davon ab, wie viel nutzbare Information die Ziehungen enthalten.

Eine Zufallszahl in einen Wert umwandeln

Ziehe eine gleichverteilte Zahl $u$ aus $[0,1)$. Teile das Intervall in Abschnitte, deren Längen den Wahrscheinlichkeiten entsprechen. Bei den Wetterwahrscheinlichkeiten $⟨\mathrm{0,5};\mathrm{0,3};\mathrm{0,2}⟩$ belegt Sonne $[0;\mathrm{0,5})$, Wolken $[\mathrm{0,5};\mathrm{0,8})$ und Regen $[\mathrm{0,8};1)$. Eine Ziehung von 0,63 ergibt Wolken. Wähle bei einer booleschen Variablen wahr, wenn die gezogene Zahl kleiner als ihre Wahrscheinlichkeit für wahr ist.

Elternknoten vor Kindknoten ziehen

A-priori-Sampling besucht Variablen in topologischer Reihenfolge. Für jeden Knoten wird ein Wert aus der CPT-Zeile gezogen, die durch die gezogenen Werte seiner Elternknoten bestimmt ist. „A priori“ bezieht sich auf Ziehungen aus dem Netz, bevor die Stichproben auf die Evidenz der Anfrage bedingt werden.

Nutze im Pendelmodell die Reihenfolge $R,A,T,L,U$ und die Zufallszahlen 0,13, 0,57, 0,40, 0,81 und 0,35:

1. Regen ist wahr, weil $\mathrm{0,13}<\mathrm{0,2}$.
2. Unfall ist falsch, weil $\mathrm{0,57}\ge \mathrm{0,1}$.
3. Verkehr ist wahr, weil $\mathrm{0,40}<P(t\mid r,\mathrm{\neg }a)=\mathrm{0,7}$.
4. Verspätung ist falsch, weil $\mathrm{0,81}\ge P(l\mid t)=\mathrm{0,6}$.
5. Schirm ist wahr, weil $\mathrm{0,35}<P(u\mid r)=\mathrm{0,9}$.

Die Belegung ist $(r,\mathrm{\neg }a,t,\mathrm{\neg }l,u)$. Ihre Erzeugungswahrscheinlichkeit ist $\mathrm{0,2}(\mathrm{0,9})(\mathrm{0,7})(\mathrm{0,4})(\mathrm{0,9})=\mathrm{0,04536}$, genau ihre Wahrscheinlichkeit in der gemeinsamen Verteilung des Netzes. Würde ein Kindknoten vor seinen Elternknoten gezogen, stünde die benötigte CPT-Zeile noch nicht fest.

Wahrscheinlichkeiten aus Häufigkeiten schätzen

Der Anteil der A-priori-Stichproben mit Verspätung schätzt $P(l)$, das in diesem Modell 0,2765 beträgt. Der Schätzer ist konsistent: Mit wachsender Anzahl unabhängiger Ziehungen konvergiert er gegen die wahre Wahrscheinlichkeit. Auch ein längerer Lauf kann schwanken. Der typische Fehler unabhängiger Stichproben skaliert wie $1\mathrm{/}\sqrt{N}$, sodass viermal so viele Stichproben den Fehler ungefähr halbieren; doppelt so viele tun das nicht.

Mit der Verwerfungsmethode bedingen

Die Verwerfungsmethode erzeugt A-priori-Belegungen und verwirft solche, die der Evidenz widersprechen. Zähle Anfragewerte nur unter den behaltenen Belegungen. Angenommen, 280 von 1.000 Belegungen enthalten eine Verspätung und 94 davon auch Regen. Dann gilt $P(r\mid l)\approx 94\mathrm{/}280\approx \mathrm{0,336}$. Eine Division durch 1.000 würde stattdessen das gemeinsame Ereignis Regen und Verspätung schätzen.

Eine Stichprobe kann abgebrochen werden, sobald sie einer Beobachtung widerspricht; das spart die restliche Simulation. Der erwartete Anteil der behaltenen Stichproben ist dennoch $P(e)$. Verspätung allein behält etwa 28 %; Verspätung mit Schirm etwa 12 %, da $P(l,u)=\mathrm{0,12005}$. Viele Beobachtungen können ihre Kombination selten machen, selbst wenn jede einzelne für sich gewöhnlich ist. Überlebt keine Stichprobe, ist die bedingte Schätzung nicht definiert und es werden mehr nutzbare Stichproben benötigt.

Die Verwerfungsmethode verbringt Zeit mit der Erzeugung unbrauchbarer Belegungen. Likelihood-Gewichtung hält jede Evidenzvariable fest und gleicht das durch ein Gewicht aus. Stichproben, deren verborgene Werte die Evidenz wahrscheinlich machen, tragen mehr bei.

Eine gewichtete Belegung erzeugen

Beginne jede Stichprobe mit Gewicht 1. Besuche Knoten in topologischer Reihenfolge. Ziehe für einen Knoten ohne Evidenz anhand der aktuellen Werte seiner Elternknoten einen Wert. Behalte bei einem Evidenzknoten seinen beobachteten Wert und multipliziere das Gewicht mit der CPT-Wahrscheinlichkeit dieses Werts:

Nur Evidenzwahrscheinlichkeiten gehen in dieses Gewicht ein. Die Wahrscheinlichkeiten der Knoten, für die Werte gezogen werden, bestimmen bereits, wie häufig ihre Belegungen erzeugt werden. Eine Multiplikation dieser Wahrscheinlichkeiten in das Gewicht würde sie doppelt zählen.

Zwei Stichproben im Pendelmodell

Für $P(R\mid l,u)$ halte Verspätung und Schirm auf wahr. Ziehe Werte für Regen, Unfall und Verkehr. Die Verkehrswahrscheinlichkeiten für $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$ sind 0,95, 0,7, 0,8 und 0,2, mit den A-priori-Wahrscheinlichkeiten $P(r)=\mathrm{0,2}$ und $P(a)=\mathrm{0,1}$.

Die Ziehungen 0,13, 0,57 und 0,40 ergeben Regen, keinen Unfall und dichten Verkehr. Die festgelegte Verspätung trägt $P(l\mid t)=\mathrm{0,6}$ bei; der festgelegte Schirm trägt $P(u\mid r)=\mathrm{0,9}$ bei. Das Gewicht der Stichprobe ist $\mathrm{0,6}(\mathrm{0,9})=\mathrm{0,54}$.

Die Ziehungen 0,66, 0,05 und 0,92 ergeben stattdessen keinen Regen, einen Unfall und keinen dichten Verkehr. Die Evidenz-Likelihoods sind nun $P(l\mid \mathrm{\neg }t)=\mathrm{0,1}$ und $P(u\mid \mathrm{\neg }r)=\mathrm{0,2}$, sodass das Gewicht 0,02 ist. Beide Stichproben passen zur Evidenz, weil diese Werte festgelegt wurden; ihre Beiträge unterscheiden sich dennoch stark.

Gewichte statt Stichprobenzahlen normieren

Schätze eine Anfragewahrscheinlichkeit durch

Die Regenschätzung aus zwei Stichproben ist $\mathrm{0,54}\mathrm{/}(\mathrm{0,54}+\mathrm{0,02})\approx \mathrm{0,964}$. Das liegt weit von der exakten A-posteriori-Wahrscheinlichkeit von etwa 0,693 entfernt; zwei Ziehungen sind zu wenige, um die relevanten verborgenen Belegungen darzustellen. Bei vielen Ziehungen konvergiert der gewichtete Quotient gegen die A-posteriori-Wahrscheinlichkeit. Eine Division von 0,54 durch zwei ergäbe keine Schätzung der bedingten Wahrscheinlichkeit.

Die Korrektur funktioniert, weil die Multiplikation der Ziehungswahrscheinlichkeit mit dem Evidenzgewicht das vollständige gemeinsame Produkt ergibt. Die Normierung entfernt die gemeinsame Wahrscheinlichkeit der Evidenz und lässt die bedingte Verteilung übrig.

Konzentrierte Gewichte erkennen

Festgelegte Evidenz beeinflusst die Ziehung ihrer Nachkommen, da diese die Evidenz in den Zeilen ihrer Elternknoten nutzen. Werte für vorgelagerte Variablen werden weiterhin ohne Rückwirkung nachgelagerter Beobachtungen gezogen. Liegt seltene Evidenz an Blattknoten, erklären die meisten vorgelagerten Belegungen sie möglicherweise schlecht. Ihre Gewichte sind winzig und einige wenige Belegungen können das Ergebnis bestimmen.

Likelihood-Gewichtung nutzt den Rechenaufwand oft effizienter als die Verwerfungsmethode, aber „keine verworfenen Stichproben“ bedeutet nicht, dass alle Stichproben gleich aussagekräftig sind. Auch ein langer Lauf mit sehr ungleichen Gewichten kann eine instabile Schätzung liefern. Prüfe beim Vergleich mehrerer Läufe, welche Belegungen das Gesamtgewicht tragen.

Gibbs-Sampling behält eine vollständige Belegung und ändert jeweils eine Variable, die keine Evidenzvariable ist. Jede Änderung wird aus der bedingten Verteilung der Variablen bei den aktuellen Werten aller anderen Variablen gezogen. Die Folge bildet ein Markov-Ketten-Monte-Carlo-Verfahren, kurz MCMC.

Eine Kette starten und Evidenz festhalten

Setze Evidenz auf ihre beobachteten Werte und initialisiere die übrigen Variablen. Beginne bei deterministischen Nullen mit einer evidenzverträglichen Belegung mit positiver gemeinsamer Wahrscheinlichkeit. Wähle eine Variable ohne Evidenz zur Aktualisierung, berechne für jeden ihrer möglichen Werte eine Wahrscheinlichkeit, normiere und ziehe den neuen Wert. Alle anderen Werte bleiben in diesem Schritt bestehen. Durch Wiederholung kann Evidenz sowohl vorgelagerte als auch nachgelagerte Einschätzungen beeinflussen.

Benötigt wird nur die Markov-Decke des gewählten Knotens: seine Elternknoten, Kindknoten und die anderen Elternknoten seiner Kindknoten. Faktoren außerhalb dieser Decke ändern sich nicht mit dem gewählten Wert und kürzen sich daher bei der Normierung heraus. Die lokale Formel lautet:

Kindknoten behalten ihre aktuellen Werte, während jeder mögliche Wert des gewählten Elternknotens erprobt wird. Ihre CPT-Einträge können sich daher ändern, obwohl für die Kindknoten selbst keine neuen Werte gezogen werden.

Regen im Pendelmodell aktualisieren

Halte Verspätung und Schirm auf wahr. Der aktuelle verborgene Zustand sei kein Regen, kein Unfall und dichter Verkehr. Die Decke des Regens besteht aus Verkehr, Schirm und Unfall. Für Regen wahr ist der lokale Wert:

Für Regen falsch ist der Wert $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,2})=\mathrm{0,032}$. Normierung ergibt $P(r\mid \text{Decke})=\mathrm{0,126}\mathrm{/}\mathrm{0,158}\approx \mathrm{0,797}$. Eine gleichverteilte Ziehung von 0,40 ändert Regen daher zu wahr. Der Faktor der Verspätung fehlt bei dieser Aktualisierung, weil der Verkehr fest bleibt und dieser Faktor für beide Regenwerte konstant ist.

Verkehr mit dem neuen Regenwert aktualisieren

Die Decke des Verkehrs besteht aus Regen, Unfall und Verspätung. Seine beiden Werte sind $\mathrm{0,7}(\mathrm{0,6})=\mathrm{0,42}$ für dichten Verkehr und $\mathrm{0,3}(\mathrm{0,1})=\mathrm{0,03}$ für keinen dichten Verkehr. Somit ist seine Wahrscheinlichkeit für wahr $\mathrm{0,42}\mathrm{/}\mathrm{0,45}\approx \mathrm{0,933}$. Bei einer Aktualisierung des Unfalls mit festem Regen und dichtem Verkehr beträgt die Wahrscheinlichkeit für wahr $\mathrm{0,095}\mathrm{/}(\mathrm{0,095}+\mathrm{0,63})\approx \mathrm{0,131}$.

Zustände zählen und Zeit zur Durchmischung geben

Nach jeder Aktualisierung kann die vollständige Belegung als Stichprobe zählen, auch wenn der gewählte Wert unverändert bleibt. Verwirf eine anfängliche Einlaufphase, um den Einfluss der Initialisierung zu verringern. Bei Konvergenz der Kette nähert sich die langfristige Regenhäufigkeit für diese Anfrage etwa 0,693.

Benachbarte Zustände teilen fast alle ihre Werte und sind korreliert. Sie enthalten weniger unabhängige Information als dieselbe Anzahl unabhängiger Ziehungen. Liegen alle CPT-Einträge strikt zwischen 0 und 1, können geeignete wiederholte Aktualisierungen jeden Zustand erreichen und gegen die A-posteriori-Verteilung konvergieren. Deterministische Constraints können eine Kette mit Aktualisierung einzelner Variablen festhalten; nahezu deterministische Beziehungen können sie sehr langsam machen.

A-priori-Sampling zieht aus der gemeinsamen Verteilung; die Verwerfungsmethode filtert diese Ziehungen; Likelihood-Gewichtung legt Evidenz fest und gewichtet Belegungen; Gibbs-Sampling aktualisiert wiederholt einen Zustand mit fester Evidenz. Eine Bedingung allein auf Elternknoten ergäbe bei einer Gibbs-Aktualisierung die falsche lokale Verteilung, weil die Evidenz der Kindknoten fehlte.

Wahrscheinlichkeiten beschreiben, was geschehen kann; Nutzenwerte beschreiben, wie wünschenswert die Ergebnisse sind. Eine Nutzenfunktion weist bevorzugten Ergebnissen höhere Zahlen zu. Eine unsichere Aktion ist eine Lotterie, die Ergebnisse und ihre Wahrscheinlichkeiten aufführt.

Den Nutzen über mögliche Ergebnisse mitteln

Der erwartete Nutzen einer Aktion ist

Multipliziere den Nutzen jedes Ergebnisses mit seiner Wahrscheinlichkeit und addiere. Das Prinzip des maximalen erwarteten Nutzens (MEU) wählt die Aktion mit dem größten Ergebnis. Das Ergebnis mit dem höchsten einzelnen Nutzen muss nicht zur besten Aktion gehören, und das wahrscheinlichste Ergebnis allein bestimmt die Wahl nicht. Eine vernünftige Entscheidung kann durch Zufall dennoch ein schlechtes Ergebnis liefern.

Warum widerspruchsfreie Präferenzen MEU stützen

Die Nutzentheorie nutzt diese Rationalitätsanforderungen:

• Vergleichbarkeit: Je zwei Lotterien können verglichen werden, wobei Indifferenz möglich ist.
• Transitivität: Wer A gegenüber B und B gegenüber C bevorzugt, bevorzugt A gegenüber C.
• Stetigkeit: Ein mittleres Ergebnis kann durch eine Lotterie zwischen einem besseren und einem schlechteren Ergebnis ausgeglichen werden.
• Substituierbarkeit: Gleichwertige Ergebnisse oder Lotterien können innerhalb einer größeren Lotterie einander ersetzen.
• Monotonie: Bei Lotterien mit denselben besseren und schlechteren Ergebnissen wird die höhere Wahrscheinlichkeit des besseren Ergebnisses bevorzugt.
• Zerlegbarkeit: Eine Lotterie über Lotterien lässt sich auf ihre Wahrscheinlichkeiten für die Endergebnisse zurückführen.

Das Ergebnis von von Neumann und Morgenstern stellt Präferenzen, die diese Anforderungen erfüllen, durch erwarteten Nutzen dar. Zyklische Präferenzen verletzen die Transitivität. Zahlt ein Agent einen kleinen Betrag, um von B zu A, von A zu C und von C zu B zu wechseln, bringen wiederholte Tauschvorgänge ihn an seine Ausgangsposition zurück und zehren dabei sein Geld auf. Das ist das Problem der „Geldpumpe“.

Geld und Nutzen können Lotterien unterschiedlich ordnen

Vergleiche eine sichere Zahlung von 400 mit einer Chance von 50 % auf 1.000 und einer Chance von 50 % auf null. Der erwartete Geldbetrag spricht für die Lotterie, deren Mittelwert 500 ist. Für $U(x)=\sqrt{x}$ beträgt der erwartete Nutzen der Lotterie jedoch $\mathrm{0,5}\sqrt{1000}+\mathrm{0,5}\sqrt{0}\approx \mathrm{15,81}$, während die sichere Zahlung 20 ergibt. Dieser Agent wählt 400.

Das Sicherheitsäquivalent ist der sichere Betrag mit dem Nutzen der Lotterie. Hier ist es $(\mathrm{0,5}\sqrt{1000}{)}^2=250$. Die Differenz zwischen erwartetem Geldbetrag und Sicherheitsäquivalent ist die Risikoprämie, in diesem Beispiel 250.

Bei konkavem Nutzen ist ein sicherer Betrag in Höhe des Erwartungswerts mindestens so wünschenswert wie die Lotterie mit diesem Erwartungswert. Strenge Konkavität macht diese Präferenz bei einer nicht trivialen Lotterie strikt. Eine hinreichend günstige riskante Option kann dennoch einen weniger wertvollen sicheren Betrag übertreffen.

Skalen ändern, ohne Präferenzen zu ändern

Der Ersatz des Nutzens durch $U^{\mathrm{\prime }}(s)=kU(s)+c$ mit $k>0$ erhält jeden Vergleich erwarteter Nutzenwerte. Jeder Erwartungswert erhält dieselbe positive Skalierung und Verschiebung. Eine allgemeine steigende Transformation erhält die Rangfolge sicherer Ergebnisse, kann aber die Rangfolge von Lotterien ändern.

Beim Vergleich mehrerer wünschenswerter Attribute dominiert eine Option die andere, wenn sie bei jedem Attribut mindestens ebenso gut und bei mindestens einem besser ist. Bei Präferenzen, die diese Verbesserungen schätzen, kann die dominierte Option ohne genaue Gewichte der Attribute entfernt werden.

Ein Entscheidungsnetz, auch Einflussdiagramm genannt, kombiniert ein Wahrscheinlichkeitsmodell mit Entscheidungen und Präferenzen. Seine Lösung erfordert sowohl Inferenz über unsichere Zustände als auch den Vergleich der dem Agenten verfügbaren Aktionen.

Die drei Knotentypen lesen

Zufallsknoten, meist Ovale, haben Wahrscheinlichkeitstabellen. Entscheidungsknoten, meist Rechtecke, stellen vom Agenten kontrollierte Aktionen dar. Nutzenknoten, meist Rauten, ordnen Kombinationen von Werten ihrer Elternknoten einen Nutzen zu. Ein Pfeil in einen Entscheidungsknoten kennzeichnet Information, die zum Entscheidungszeitpunkt verfügbar ist. Er ist keine gewöhnliche Abhängigkeit einer bedingten Wahrscheinlichkeit.

Bei einer Freiluftveranstaltung beeinflusst Regen eine Prognose und den Nutzen der Veranstaltung. Auch die Aktion beeinflusst den Nutzen. Die Prognose zeigt auf die Entscheidung, wenn sie vor der Wahl der veranstaltenden Person beobachtet wird. Es gibt keinen Pfeil von der Aktion zu Regen: Der Wechsel nach drinnen ändert das Wetter nicht.

Ohne Prognose lösen

Angenommen, $P(rain)=\mathrm{0,3}$, und nutze diese Nutzentabelle:

Die erwarteten Nutzenwerte sind $EU(outdoors)=\mathrm{0,7}(100)+\mathrm{0,3}(0)=70$ und $EU(indoors)=\mathrm{0,7}(60)+\mathrm{0,3}(70)=63$. Wähle ohne weitere Information draußen; der MEU ist 70. Der Entscheidungsknoten erhält einen gewählten Wert und keine Wahrscheinlichkeitstabelle, über die Aktionen gemittelt werden.

Eine Prognose einbeziehen

Es gelte $P(wet\mid rain)=\mathrm{0,8}$ und $P(wet\mid \mathrm{\neg }rain)=\mathrm{0,1}$. Die Wahrscheinlichkeit einer Regenprognose ist $\mathrm{0,8}(\mathrm{0,3})+\mathrm{0,1}(\mathrm{0,7})=\mathrm{0,31}$. Der Satz von Bayes ergibt $P(rain\mid wet)=\mathrm{0,24}\mathrm{/}\mathrm{0,31}\approx \mathrm{0,774}$. Eine Trockenprognose ergibt $P(rain\mid dry)=\mathrm{0,06}\mathrm{/}\mathrm{0,69}\approx \mathrm{0,087}$.

Bei einer Regenprognose beträgt der erwartete Nutzen draußen etwa 22,6 und drinnen etwa 67,7, also wähle drinnen. Bei einer Trockenprognose ergibt draußen etwa 91,3 und drinnen etwa 60,9, also wähle draußen. Nutze nach einer Beobachtung die A-posteriori-Wahrscheinlichkeit; das Beibehalten der A-priori-Wahrscheinlichkeit würde die Information der Prognose verwerfen.

Die entstehende Strategie lautet „Wähle bei Regenprognose drinnen; wähle bei Trockenprognose draußen“. Eine Strategie ordnet Beobachtungen Aktionen zu und kann daher vor der Beobachtung festgelegt werden. Eine Aktion ist die einzelne Wahl, sobald ihre Information verfügbar ist.

Bestimmen, wo die Wahl wechselt

Sei $p$ die aktuelle Regenwahrscheinlichkeit. Dann gilt $EU(outdoors)=100(1-p)$ und $EU(indoors)=60(1-p)+70p=60+10p$. Gleichsetzen ergibt $40=110p$ oder $p=4\mathrm{/}11\approx \mathrm{0,364}$. Unter dieser Schwelle wähle draußen; darüber drinnen; an der Schwelle sind die Aktionen gleich gut.

Um ein anderes Entscheidungsnetz zu lösen, lege die aktuelle Evidenz fest, betrachte jede Aktion einzeln, bestimme die für den Nutzen relevante Zufallsverteilung und berechne ihren erwarteten Nutzen. Ändert eine Aktion ein unsicheres Ergebnis, berücksichtige ihre Auswirkungen im Wahrscheinlichkeitsmodell, bevor du Erwartungswerte vergleichst. Wähle schließlich die beste Aktion getrennt für jede mögliche Beobachtung, die die Strategie erhält.

Eine Beobachtung ist wertvoll, wenn sie dem Agenten hilft, eine bessere Aktion zu wählen. Der Wert perfekter Information (VPI) misst die erwartete Verbesserung durch Kenntnis des Werts einer Variablen vor dem Handeln. „Perfekt“ beschreibt den Zugang zum tatsächlichen Wert dieser Variablen; die Variable selbst kann eine unvollkommene Prognose für etwas anderes sein.

Innerhalb jeder möglichen Beobachtung optimieren

Bei aktueller Evidenz $e$ ist der Wert der Beobachtung von $E^{\mathrm{\prime }}$:

Bestimme zuerst den besten erwarteten Nutzen einer sofortigen Entscheidung. Aktualisiere dann für jede mögliche Beobachtung die Wahrscheinlichkeiten und wähle die beste Aktion für diese Beobachtung. Mittle diese optimierten Nutzenwerte mit den Beobachtungswahrscheinlichkeiten. Ziehe den aktuellen MEU ab. Würde zuerst eine Aktion gewählt und dann gemittelt, bliebe die Möglichkeit unberücksichtigt, die Aktion anzupassen.

Prognose und Wetter bewerten

Im Veranstaltungsmodell ergibt die Wahl von draußen ohne Prognose einen MEU von 70. Regenprognosen treten mit Wahrscheinlichkeit 0,31 auf und führen zur Wahl drinnen, mit einem MEU von etwa 67,74. Trockenprognosen treten mit Wahrscheinlichkeit 0,69 auf und führen zur Wahl draußen, mit einem MEU von etwa 91,30. Mit exakten Werten ergibt sich:

Somit beträgt $VPI(F)=84-70=14$ Nutzeneinheiten. Kosten, die als Nutzenverlust ausgedrückt unter 14 liegen, machen das Einholen der Prognose lohnend; bei 14 ist der Agent indifferent. Ein Geldpreis muss zuerst auf der Nutzenskala des Agenten bewertet werden.

Das Wetter selbst zu kennen ist nützlicher. Regen führt zur Wahl drinnen mit Nutzen 70; kein Regen führt zur Wahl draußen mit Nutzen 100. Der Mittelwert ist $\mathrm{0,3}(70)+\mathrm{0,7}(100)=91$, also $VPI(Rain)=91-70=21$.

Warum Information einen nichtnegativen Erwartungswert hat

Der Agent kann kostenlose Information immer ignorieren und seine ursprüngliche Aktion beibehalten. Die Optimierung nach der Beobachtung kann daher den erwarteten Nutzen vor Bekanntwerden der Beobachtung nie senken. Ist für jedes mögliche Ergebnis dieselbe Aktion am besten, hat die Information den Wert null. Information, die bei aktueller Evidenz von allen für den Nutzen relevanten Zufallsvariablen unabhängig ist, hat in diesem Entscheidungsmodell ebenfalls den Wert null.

Ein bestimmtes Ergebnis kann dennoch unerwünscht sein. Nach einer Regenprognose ist der MEU etwa 67,7 und damit unter den früheren 70. Nichtnegativität betrifft den Durchschnitt über alle Ergebnisse, bevor sie bekannt sind.

Information ohne Doppelzählung kombinieren

VPI ist im Allgemeinen nicht additiv. Die Prognose allein ist 14 wert und das Wetter allein 21, doch beides zu erfahren ist 21 wert, weil die Prognose nach Kenntnis des Wetters nichts hinzufügt.

Nach einer Regenprognose fügt das Wissen über das Wetter etwa 9,03 hinzu; nach einer Trockenprognose etwa 6,09. Vor Kenntnis der Prognose ist der erwartete zusätzliche Wert $\mathrm{0,31}(\mathrm{9,03})+\mathrm{0,69}(\mathrm{6,09})\approx 7$. Der gemeinsame Gewinn ist also $14+7=21$, ebenso viel wie bei Kenntnis des Wetters zuerst und anschließendem Zuwachs von null. Der Gesamtwert ist unabhängig von der Reihenfolge, wenn alle Beobachtungen vor der Aktion erfolgen und jeder spätere Gewinn anhand der früheren Information bewertet wird.

Ein informationsbeschaffender Agent kann wiederholt die Beobachtung mit dem größten positiven VPI abzüglich Kosten wählen und handeln, wenn keine mehr lohnend ist. Diese myopische Strategie bewertet jeweils eine Beobachtung. Zwei Beobachtungen können zusammen nützlich sein, selbst wenn keine allein die beste Aktion verändert; daher kann die gierige Auswahl ein wertvolles Paar übersehen.