Binary file bayesian_networks/term_paper.pdf has changed

--- a/bayesian_networks/term_paper.tex	Sun Feb 10 19:59:04 2013 +0100
+++ b/bayesian_networks/term_paper.tex	Sun Feb 10 20:36:10 2013 +0100
@@ -61,7 +61,7 @@
 \input{titlepage}
 
 \begin{abstract}
-Bayesnetze repräsentieren mehrdimensionale Zufallsvariablen platzsparend aber exakt. Diese Arbeit führt die notwendigen Begriffe der Wahrscheinlichkeitstheorie ein und definiert die bedingte Unabhängigkeit, anhand derer mithilfe der d-Separation die Semantik der Bayesnetze erarbeitet wird. Schließlich wird ein einfacher Algorithmus zur exakten Inferenz vorgestellt, die im allgemeinen Fall NP-vollständig ist, auf Polytrees jedoch in Linearzeit ausgeführt werden kann.
+Bayesnetze repräsentieren mehrdimensionale Zufallsvariablen platzsparend aber exakt. Diese Arbeit führt die notwendigen Begriffe der Wahrscheinlichkeitstheorie ein und definiert die bedingte Unabhängigkeit anhand derer mit Hilfe der d-Separation die Semantik der Bayesnetze erarbeitet wird. Schließlich wird ein einfacher Algorithmus zur exakten Inferenz vorgestellt, die im Allgemeinen NP-vollständig ist, auf Polytrees jedoch in Linearzeit ausgeführt werden kann.
 \end{abstract}
 
 \vspace{3em}
@@ -77,7 +77,7 @@
 Wissen ist selten sicher und exakt. Soll beispielsweise ein Arzt eine Diagnose stellen, so reicht perfekt logisches Schließen allein nicht aus. Jeder Patient hat eine Vorgeschichte, die unvollständig sein kann und Symptome, die vage sein können. Tests lassen mehrere alternative Schlüsse zu und Schulwissen ist fehlerbehaftet. Der Arzt muss diese Unsicherheiten abwägen und die plausibelste Diagnose und erfolgsversprechendste Therapie wählen.
 Soll dieses Vorgehen in computergestützten System modelliert werden, bietet sich ein Ansatz gestützt auf die Wahrscheinlichkeitstheorie an. Inhalt dieser Arbeit ist es, mit Bayesnetzen ein Verfahren vorzustellen, das es erlaubt unsichere Problemdomänen platzeffizient aber vollständig zu repräsentieren.
 
-Die Wahrscheinlichkeitstheorie definiert \emph{Wahrscheinlichkeitsräume} $P = (\Omega, A, \Pr)$ als ein Tupel bestehend aus einer Menge von Elementarereignissen $\Omega$, \emph{Ereignissen} $A$ und einem \emph{Wahrscheinlichkeitsfunktion} $\Pr: A \mapsto [0,1]$. $A$ bildet eine $\sigma$-Algebra über $\Omega$, erlaubt es also mehrere Elementarereignisse zu Gruppen zusammenzufassen. $\Pr$ ordnet jedem Ereignis eine Wahrscheinlichkeit zwischen 0 und 1 zu, wobei $\Pr[\Omega] = 1$ und für zwei disjunkte Mengen $A$ und $B$ gilt $\Pr[A \cup B] = \Pr[A] + \Pr[B]$.
+Die Wahrscheinlichkeitstheorie definiert einen \emph{Wahrscheinlichkeitsraum} $P = (\Omega, A, \Pr)$ als ein Tupel bestehend aus einer Menge von eindeutigen Elementarereignissen $\Omega$, \emph{Ereignissen} $A$ und einer \emph{Wahrscheinlichkeitsfunktion} $\Pr: A \mapsto [0,1]$. $A$ bildet eine $\sigma$-Algebra über $\Omega$, erlaubt es also mehrere Elementarereignisse zu Gruppen zusammenzufassen. $\Pr$ ordnet jedem Ereignis eine Wahrscheinlichkeit zwischen 0 und 1 zu, wobei $\Pr[\Omega] = 1$ und für zwei disjunkte Mengen $A$ und $B$ gilt $\Pr[A \cup B] = \Pr[A] + \Pr[B]$.
 
 Im Folgenden werden die für Bayesnetze wesentlichen Sätze und Definitionen kurz und ohne Beweis eingeführt, diese können zum Beispiel \cite{Görz} entnommen werden.
 
@@ -141,7 +141,7 @@
     \end{align*}
 \end{theorem}
 
-Zur Vereinfachung der Notation verwendet man oft $\Pr[A,B]$ statt $\Pr[A \cap B]$, um auszudrücken, dass sowohl $A$ als auch $B$ zutreffen sollen. Werden mehrere Zufallsvariablen betrachtet, so definiert man die \emph{gemeinsame Verteilung} als die Funktion, die einer beliebigen aber vollständigen Konbination von Evidenzen ihre Wahrscheinlichkeit zuordnet. Für $n$ binäre Zufallsvariablen hat diese $2^n$ Einträge.
+Zur Vereinfachung der Notation verwendet man $\Pr[A,B]$ statt $\Pr[A \cap B]$, um auszudrücken, dass sowohl $A$ als auch $B$ zutreffen sollen. Werden mehrere Zufallsvariablen betrachtet, so definiert man die \emph{gemeinsame Verteilung} als die Funktion, die einer beliebigen aber vollständigen Kombination von Evidenzen ihre Wahrscheinlichkeit zuordnet. Für $n$ binäre Zufallsvariablen hat diese $2^n$ Einträge.
 
 \begin{lemma}
     Für unabhängige Zufallsvariablen $A_1, \ldots, A_n$ gilt
@@ -218,7 +218,7 @@
 Der Ansatz, mehrdimensionale Zufallsvariablen auf Basis der Einzelverteilungen darzustellen, wird mit Hilfe von Bayesnetzen so erweitert, dass auch Systeme mit Abhängigkeiten repräsentiert werden können.
 
 \subsection{Aufbau}
-Bayesnetze stellen Abhängigkeiten in Form von gerichteten Graphen dar. Dabei sind Zufallsvariablen verbunden mit einer Kante genau dann, wenn sie sich direkt beeinflussen. Diese Darstellung führ zu einer vollständigen aber in vielen Fällen sehr kompakten Darstellung von beliebigen Zufallsvariablen. \cite{Russel} definiert Bayesnetze anhand von drei Regeln.
+Bayesnetze stellen Abhängigkeiten in Form von gerichteten Graphen dar. Dabei sind Zufallsvariablen genau dann mit einer Kante verbunden, wenn sie sich direkt beeinflussen. Diese Darstellung führt zu einer vollständigen und in vielen Fällen sehr kompakten Darstellung von beliebigen Zufallsvariablen. \cite{Russel} definiert Bayesnetze anhand von drei Regeln.
 
 \begin{definition}[Bayesnetz]
     Ein Bayesnetz ist ein gerichteter azyklischer Graph, ein \emph{DAG}.
@@ -232,7 +232,7 @@
 Im Folgenden soll gezeigt werden, dass diese Darstellung ausreichend ist, Einträge in der gemeinsamen Verteilung zu ermitteln und damit die Zufallsvariable vollständig zu beschreiben.
 
 \begin{example}[Erweiterte Nachmittagsplanung]
-    Der Student möchte das Haus nicht verlassen müssen, wenn es regnet. Deshalb halbiere er bei Regen die Wahrscheinlichkeit für Aktivitäten außer Haus. Wenn er weder Sport macht noch lernt bekommt er ein schlechtes Gewissen. Nach seinem Würfelergebnis möchte er wissen, wie groß die Wahrscheinlichkeit ist, am Abend schlecht gelaunt zu sein.
+    Der Student möchte das Haus nicht verlassen müssen, wenn es regnet. Deshalb halbiert er bei Regen die Wahrscheinlichkeit für Aktivitäten außer Haus. Wenn er weder Sport macht noch lernt bekommt er ein schlechtes Gewissen. Nach seinem Würfelergebnis möchte er wissen, wie groß die Wahrscheinlichkeit ist, am Abend schlecht gelaunt zu sein.
 \end{example}
 
 \begin{figure}[t]
@@ -283,16 +283,16 @@
             T & T & $0.1$ \\
         \end{tabu}};
     \end{tikzpicture}
-    \caption{Ein Bayesnetz zur erweiterten Nachmittagsplanung. Jede Zufallsvariable wird durch einen Knoten repräsentiert, Kanten beschreiben direkte Abhängigkeiten. Es sind sowohl die Topologie des Netzes, als auch die bedingten Wahrscheinlichkeitsverteilungen abgebildet.}
+    \caption{Ein Bayesnetz zur erweiterten Nachmittagsplanung. Jede Zufallsvariable wird durch einen Knoten repräsentiert, Kanten beschreiben direkte Abhängigkeiten. Es sind sowohl die Topologie des Netzes als auch die bedingten Wahrscheinlichkeitsverteilungen abgebildet.}
     \label{fig:rain-net}
 \end{figure}
 
 Abbildung \ref{fig:rain-net} zeigt ein Bayesnetz, das die erweiterte Nachmittagsplanung modelliert. Ob der Student am Abend ein schlechtes Gewissen hat ist allein davon abhängig, ob er Sport gemacht hat und gelernt hat. Zwar beeinflusst der Regen das schlechte Gewissen, jedoch nur indirekt, da er die Wahrscheinlichkeit für sportliche Aktivitäten verringert. Sport und Lernen haben keine Verbindung, da die Entscheidung für beide Tätigkeiten unabhängig voneinander getroffen wird.
 
-Die bedingten Verteilungen sind in Form von Tabellen dargestellt. Dabei wird jeder möglichen Kombination von Zuständen der Elternknoten eine Wahrscheinlichkeit zugewiesen. Im Gegensatz zur kompletten gemeinsamen Verteilung werden hier nur lokale Zusammenhänge repräsentiert, die im Allgemeinen einfacher und intuitiver zu bestimmen sind. Im gegebenen Netz sind alle Variablen binär, daher wird jeweils nur die Wahrscheinlichkeit $p$ für ein positives Ergebnis angegeben, da die Wahrscheinlichkeit für ein negatives Ergebnis $1-p$ betragen muss. So müssen im gegebenen Netz die Topologie und $10$ Werte gespeichert werden. Diese genügen, um alle $2^5 = 32$ Einträge der gemeinsamen Verteilung zu errechnen.
+Die bedingten Verteilungen sind in Form von Tabellen dargestellt. Dabei wird jeder möglichen Kombination von Zuständen der Elternknoten eine Wahrscheinlichkeit zugewiesen. Im Gegensatz zur kompletten gemeinsamen Verteilung werden hier nur lokale Zusammenhänge repräsentiert, die im Allgemeinen einfacher und intuitiver zu bestimmen sind. Im gegebenen Netz sind alle Variablen binär, daher wird jeweils nur die Wahrscheinlichkeit $p$ für ein positives Ergebnis angegeben, da die Wahrscheinlichkeit für ein negatives Ergebnis $1-p$ betragen muss. So müssen im gegebenen Netz die Topologie und $10$ Werte gespeichert werden. Dies genügt, um alle $2^5 = 32$ Einträge der gemeinsamen Verteilung zu errechnen.
 
 \subsection{Semantik}
-Lemma \ref{lem:independent-jd} erlaubt die Konstruktion von Einträgen in der gemeinsamen Verteilung in sehr kompakter Weise, jedoch nur für unabhängige Zufallsgrößen. Dieses Lemma soll für Abhängigkeiten verallgemeinert werden, indem diese möglichst lokal dargestellt werden. Im Beispiel der erweiterten Nachmittagsplanung kann zwar offensichtlich nicht von Unabhängigkeit aller Variablen ausgegangen werden, es sind aber immernoch Unabhängigkeiten vorhanden. Wissen darum, ob der Student am Nachmittag gelernt hat, ändert nichts an den Wahrscheinlichkeiten für sportliche Aktivität. Ist bekannt, ob der Student einkaufen war, lässt jedoch Rückschlüsse auf den Sport zu, da beides vom Regen beeinflusst wird. Dieser Rückschluss ist jedoch indirekt, ist bereits bekannt ob es geregnet hat oder nicht, so beeinflussen sich beide Variablen nicht.
+Lemma \ref{lem:independent-jd} erlaubt die Konstruktion von Einträgen in der gemeinsamen Verteilung in sehr kompakter Weise, jedoch nur für unabhängige Zufallsgrößen. Dieses Lemma soll für Abhängigkeiten verallgemeinert werden, indem diese möglichst lokal dargestellt werden. Im Beispiel der erweiterten Nachmittagsplanung kann zwar offensichtlich nicht von Unabhängigkeit aller Variablen ausgegangen werden, es sind aber immernoch Unabhängigkeiten vorhanden. Wissen darum, ob der Student am Nachmittag gelernt hat, ändert nichts an den Wahrscheinlichkeiten für sportliche Aktivität. Ist bekannt, ob der Student einkaufen war, lässt jedoch Rückschlüsse auf den Sport zu, da beides vom Regen beeinflusst wird. Dieser Rückschluss ist jedoch indirekt: Ist bereits bekannt ob es geregnet hat oder nicht, so beeinflussen sich beide Variablen nicht.
 
 Diese Beobachtung führt zur Definition der bedingten Unabhängigkeit, eine Verallgemeinerung der im vorherigen Teil eingeführten Unabhängigkeit.
 
@@ -382,7 +382,7 @@
 Intuitiv durchbricht eine d-Separation die Kette von möglichen Rückschlüssen in einem Bayesnetz durch das Hinzufügen von Evidenzen. \cite{Görz} zeigt, dass diese Intuition tatsächlich stichhaltig ist.
 
 \begin{theorem}[Bedingte Unabhängigkeiten in Bayesnetzen]
-    Zufallsvariablen $X$ und $Y$ sind in einem Bayesnetz bedingt unabhängig unter $E$ wenn $\langle X \mid E \mid Y \rangle$.\\
+    Zufallsvariablen $X$ und $Y$ sind in einem Bayesnetz bedingt unabhängig unter $E$ wenn $\langle X \mid E \mid Y \rangle$, $E$ also $X$ und $Y$ d-separiert.\\
     Speziell ist jeder Knoten bedingt unabhängig von
     \begin{enumerate}
         \item \emph{allen nicht-Nachfahren} gegeben seine Eltern.
@@ -443,7 +443,7 @@
     \Pr[G, S, \neg L, K, \neg R] &= \Pr[G \mid S, \neg L, K, \neg R] \cdot \Pr[S \mid \neg L, K, \neg R] \\
     &\qquad \cdot \Pr[\neg L \mid K, \neg R] \cdot \Pr[K \mid \neg R] \cdot \Pr[\neg R]
 \end{align*}
-Während für den Produktsatz prinzipiell eine beliebige Reihenfolge gewählt werden kann, erleichtert es die Rechnung, eine umgekehrte topologische Sortierung zu wählen. Dann ist keine Bedingung Kindknoten und der erste Satz zur Unabhängigkeit in Bayesnetzen kann direkt angewendet werden. Dadurch fallen alle Bedingungen weg, die keine direkten Elternknoten sind, man erhält
+Während für den Produktsatz prinzipiell eine beliebige Reihenfolge gewählt werden kann, erleichtert es die Rechnung, eine umgekehrte topologische Sortierung zu wählen. Dann ist keine Bedingung Kindknoten der bedingten Variable und der erste Satz zur Unabhängigkeit in Bayesnetzen kann direkt angewendet werden. Dadurch fallen alle Bedingungen weg, die keine direkten Elternknoten sind, man erhält
 
 \begin{align*}
     \Pr[G, S, \neg L, K, \neg R] &= \Pr[G \mid S, \neg L] \cdot \Pr[S \mid \neg R] \\&\qquad \cdot Pr[\neg L] \cdot \Pr[K \mid \neg R] \cdot \Pr[\neg R]\\
@@ -459,20 +459,18 @@
     \end{align*}
 \end{theorem}
 \begin{proof}
-    Die am Beispiel vorgeführte Konstruktion stützt sich nur auf \ref{thm:bayes-independence} und die Existenz einer topologischen Sortierung, die in jedem DAG existiert. Sie lässt sich also auf jedes Bayesnetz übertragen. Ein exakterer Beweis wird in \cite{Görz} geführt.
+    Die am Beispiel vorgeführte Konstruktion verwendet nur Satz \ref{thm:bayes-independence} und die Existenz einer topologischen Sortierung, die für jeden DAG gegeben ist. Sie lässt sich also auf jedes Bayesnetz übertragen. Ein exakterer Beweis wird in \cite{Görz} geführt.
 \end{proof}
 
-Durch die Konstruktion der gemeinsamen Verteilung wurde gezeigt, dass Bayesnetze eine mehrdimensionale Zufallsvariable komplett und exakt beschreiben, wenn alle Abhängigkeiten korrekt repräsentiert sind. Zwar können auf diese weise prinzipiell beliebige Verteilungen modelliert werden, bei der Konstruktion von performanten Netzen ist jedoch eine Abwägung zwischen Exaktheit und Effizienz notwendig.
+Durch die Konstruktion der gemeinsamen Verteilung wurde gezeigt, dass Bayesnetze eine mehrdimensionale Zufallsvariable komplett und exakt beschreiben, wenn alle Abhängigkeiten repräsentiert sind. Zwar können auf diese Weise prinzipiell beliebige Verteilungen modelliert werden, bei der Konstruktion von performanten Netzen ist jedoch eine Abwägung zwischen Exaktheit und Effizienz notwendig.
 
-Die Größe der gemeinsamen Verteilung einer Zufallsgröße mit $n$ binären Dimensionen ist $2^n$ Einträge. Um zu vermeiden, dass auch im Bayesnetz exponentiell viele Einträge existieren, muss lokale Struktur geschaffen werden. Wird davon ausgegangen, dass es eine Konstante $k$ gibt sodass alle Knoten maximal $k$ Eltern haben, so enthalten die bedingten Wahrscheinlichkeitsverteilungen gemeinsam $n \dot 2^k$ Einträge, wachsen also nurnoch linear mit der Größe des Netzwerks.
-
-Dies kann erreicht werden, indem einersetis gute Heuristiken beim Ordnen der Netzknoten angewendet werden (zum Beispiel eine Orientierung der Eltern-Kind Beziehung an Ursache-Wirkung Zusammenhängen) und andererseits indem geringe oder unwichtige Abhängigkeiten ignoriert werden.
+Die Gemeinsamen Verteilung einer Zufallsgröße mit $n$ binären Dimensionen hat $2^n$ Einträge. Um zu vermeiden, dass auch im Bayesnetz exponentiell viele Einträge existieren, muss lokale Struktur geschaffen werden. Wird davon ausgegangen, dass es eine Konstante $k$ gibt sodass alle Knoten maximal $k$ Eltern haben, so enthalten die bedingten Wahrscheinlichkeitsverteilungen gemeinsam $n 2^k$ Einträge, wachsen also nurnoch linear mit der Größe des Netzwerks. Dies kann erreicht werden, indem einersetis gute Heuristiken beim Ordnen der Netzknoten angewendet werden (zum Beispiel eine Orientierung der Eltern-Kind-Beziehung an Ursache-Wirkung-Zusammenhängen) und andererseits geringe oder unwichtige Abhängigkeiten ignoriert werden.
 
 Um kurze Laufzeiten zu erhalten, muss auch darauf geachtet werden, die Knotenverteilungen effizient zu repräsentieren. Während in dieser Arbeit nur binäre Verteilungen behandelt werden, erklärt \cite{Russel} wie auch komplizierte kontinuierliche Verteilungen mit kleinen Netzen behandelt werden können, indem kanonische Verteilungen wie die Normalverteilung geschickt kombiniert werden.
 
 
 \section{Exakte Inferenz in Bayesnetzen}
-Beim Umgang mit mehrdimensionalen Zufallsvariablen ist nicht nur das Ermitteln von Einträgen in der gemeinsamen Verteilung interessant. Das Ermitteln von A-posteriori-Wahrscheinlichkeiten stellt eine zweite wichtige Anwendung dar, wobei bestimmte Evidenzen bekannt sind und die Wahrscheinlichkeisverteilungen für weitere Zufallsvariablen bestimmt werden soll.
+Beim Umgang mit mehrdimensionalen Zufallsvariablen ist nicht nur das Ermitteln von Einträgen in der gemeinsamen Verteilung interessant. Das Ermitteln von A-posteriori-Wahrscheinlichkeiten stellt eine zweite wichtige Anwendung dar, wobei bestimmte Evidenzen bekannt sind und die Wahrscheinlichkeisverteilungen für weitere Zufallsvariablen bestimmt werden sollen.
 
 \begin{definition}[Inferenz]
     Für ein Netz mit Knotenmenge $K = \{X\} \cup E \cup Y$ soll die Wahrscheinlichkeit ermittelt werden, dass eine Variable $X$ einen Wert annimmt, unter der Bedingung, dass für die Evidenzvariablen $E$ die Werte $e$ beobachtet werden und die versteckten Variablen $Y$ unbekannt sind.
@@ -481,7 +479,7 @@
 
 Im weiteren Verlauf soll mit der Inferenz durch Aufzählen ein einfacher Inferenzalgorithmus vorgestellt werden. Hierzu wird das Beispiel der erweiterten Nachmittagsplanung in abgewandelter Form betrachtet.
 \begin{example}[Bekämpfung des schlechten Gewissens]
-    Ein schlechtes Gewissen macht den Studenten unglücklich, er will es also bekämpfen. Dies erreicht er indem er sich mit einem Film ablenkt oder Apfelringe zur Aufmunterung isst. Zur Vereinfachung der Rechnung wird der Einfluss des Regens nicht mehr beachtet.
+    Ein schlechtes Gewissen macht den Studenten unglücklich, er will es bekämpfen. Dazu lenkt er sich mit einem Film ab oder isst zur Aufmunterung Apfelringe. Zur Vereinfachung der Rechnung wird der Einfluss des Regens nicht mehr beachtet.
 \end{example}
 
 \begin{figure}[h]
@@ -546,9 +544,9 @@
         &= \alpha \cdot \Pr[\neg S, M, A]
 \end{align*}
 
-Die Bestimmung von $\Pr[M]$ und $\Pr[A]$ ist zwar auch ein Inferenzproblem, kann jedoch vermieden werden, indem die Tatsache ausgenützt wird, dass die zu errechnende Wahrscheinlichkeit und ihr Gegenereignis sich zu $1$ addieren müssen. Beide Wahrscheinlichkeiten erfahren die gleiche Normalisierung durch den Satz von Bayes, weswegen diese im Faktor $\alpha$ zusammengefasst wird. Dieser Faktor wird eliminiert, indem als letzter Schritt die Normalisierung manuell durchgeführt wird.
+Die Bestimmung von $\Pr[M]$ und $\Pr[A]$ ist zwar auch ein Inferenzproblem, kann jedoch vermieden werden, indem die Tatsache ausgenützt wird, dass die zu errechnende Wahrscheinlichkeit und ihr Gegenereignis sich zu $1$ addieren müssen. Beide Wahrscheinlichkeiten erfahren die gleiche Normalisierung durch den Satz von Bayes, weswegen diese im Faktor $\alpha$ zusammengefasst wird. Dieser Faktor wird eliminiert, indem zusätzlich auch das Gegenereignis inferiert und als letzter Schritt die Normalisierung manuell durchgeführt wird.
 
-Die resultierende Wahrscheinlichkeit enthält keine Bedingungen mehr, ist jedoch im Allgemeinen noch kein Eintrag in der gemeinsamen Verteilung, da die versteckten Variablen nicht festgelegt sind. Hier hilft der Satz der totalen Wahrscheinlichkeit weiter.
+Die resultierende Wahrscheinlichkeit enthält keine Bedingungen mehr, ist jedoch im Allgemeinen noch kein Eintrag in der gemeinsamen Verteilung, da die versteckten Variablen nicht festgelegt sind. Um diese hinzuzufügen wird der Satz der totalen Wahrscheinlichkeit angewandt.
 
 \begin{align*}
     \Pr[\neg S \mid M, A] &= \alpha \cdot \Pr[\neg S, M, A] \\
@@ -557,7 +555,7 @@
     &\approx 0.585
 \end{align*}
 
-Diese Darstellung erlaubt Inferenz, da nur über Einträge der gemeinsamen Verteilung summiert wird, benötigt jedoch exponentielle Laufzeit. Für ein Netz mit $n$ binären Zufallsvariablen muss im schlechtesten Fall über fast alle Variablen summiert werden (zum Beispiel indem die Wahrscheinlichkeit $\Pr[M]$ ausgerechnet wird). Jede Summe verdoppelt die Anzahl an zu berechnenden Einträgen in der gemeinsamen Verteilung und jeder dieser Einträge wird in linearer Zeit berechnet. Es ergibt sich eine Gesamtkomplexität von $\Oh(n \cdot 2^n)$.
+Diese Darstellung erlaubt Inferenz, da nur über Einträge der gemeinsamen Verteilung summiert wird, benötigt jedoch exponentielle Laufzeit. Für ein Netz mit $n$ binären Zufallsvariablen muss im schlechtesten Fall über fast alle Variablen summiert werden, zum Beispiel indem die Wahrscheinlichkeit $\Pr[M]$ ausgerechnet wird. Jede Summe verdoppelt die Anzahl an zu berechnenden Einträgen in der gemeinsamen Verteilung und jeder dieser Einträge wird in linearer Zeit berechnet. Es ergibt sich eine Gesamtkomplexität von $\Oh(n \cdot 2^n)$.
 
 \begin{theorem}[Inferenz durch Aufzählen]
     Für ein Netz mit Knotenmenge $K = \{X\} \cup E \cup Y$ kann die Wahrscheinlichkeit $\Pr[X \mid e]$ berechnet werden durch
@@ -665,11 +663,11 @@
     \label{fig:inference-tree}
 \end{figure}
 
-Eine Intuition zur Komplexität dieses verbesserten Algorithmus liefert Abbildung \ref{fig:inference-tree}, die veranschaulicht, dass im schlechtesten Fall immer noch exponentiell viele Berechnungen durchgeführt werden müssen. Wird in einem Netz mit $n$ binären Variablen wiederum die Wahrscheinlichkeit einer einzigen Variable errechnet, so existieren im resultierenden Baum $(n-1)$ Schichten $+$-Knoten. Diese haben immer zwei Kinder, es liegt also ein Baum vor, bei dem mindestens $(n-1)$ vollbesetzte Binärbaumschichten existieren. Jeder Knoten in diesem Baum stellt eine Rechenoperation dar, es müssen also $\Oh(2^n)$ Rechenoperationen durchgeführt werden.
+Eine Intuition zur Komplexität dieses verbesserten Algorithmus liefert Abbildung \ref{fig:inference-tree}, die veranschaulicht, dass im schlechtesten Fall immer noch exponentiell viele Berechnungen durchgeführt werden müssen. Wird in einem Netz mit $n$ binären Variablen wiederum die Wahrscheinlichkeit einer einzigen Variable errechnet, so existieren im resultierenden Baum $n-1$ Schichten aus Plus-Knoten. Diese haben immer zwei Kinder, es liegt also ein Baum vor, in dem $n-1$ vollbesetzte Binärbaumschichten existieren. Jeder Knoten in diesem Baum stellt eine Rechenoperation dar, es müssen also $\Oh(2^n)$ Rechenoperationen durchgeführt werden.
 
 Im Allgemeinen lässt sich diese Komplexität wahrscheinlich auch nicht verbessern, da das SAT-Problem auf exakte Inferenz in Bayesnetzen reduzierbar ist. Diese wird erreicht, indem in den Knoten aussagenlogische Operatoren ($\wedge$, $\vee$, $\neg$) repräsentiert werden. Exakte Inferenz auf Bayesnetzen ist NP-schwer (\cite{Russel}).
 
-Es gibt jedoch mehrere Ansätze, Inferenz auf Bayesnetzen effizienter durchzuführen. Abbildung \ref{fig:inference-tree} zeigt, dass bei der Inferenz durch Aufzählen die selben Teilbäume mehrmals berechnet werden, im Beispiel die Pfade für $M$ und $A$. Diese Redundanz kann mit einem Ansatz der dynamischen Programmierung eliminiert werden, in dem die einzelnen bedingten Wahrscheinlichkeitsverteilungen bei Bedarf zusammengefasst werden. Dieser Algorithmus mit Elimination von Variablen (\cite{Russel}) hat zwar im schlechtesten Fall auch exponentielle Laufzeit, läuft jedoch linear auf Polytrees, also Netze, die keine ungerichteten Kreise enthalten.
+Es gibt jedoch mehrere Ansätze, Inferenz auf Bayesnetzen effizienter durchzuführen. Abbildung \ref{fig:inference-tree} zeigt, dass bei der Inferenz durch Aufzählen die selben Teilbäume mehrmals berechnet werden, im Beispiel die Pfade für $M$ und $A$. Diese Redundanz kann mit einem Ansatz der dynamischen Programmierung eliminiert werden, in dem die einzelnen bedingten Wahrscheinlichkeitsverteilungen bei Bedarf zusammengefasst werden. Dieser Algorithmus mit Elimination von Variablen (\cite{Russel}) hat zwar im schlechtesten Fall auch exponentielle Laufzeit, läuft jedoch linear auf Polytrees, also Netzen, die keine ungerichteten Kreise enthalten.
 
 Eine Alternative stellen approximative Algorithmen dar, bei denen zwar kein exaktes Ergebnis erreicht werden kann, die jedoch auch auf großen oder topologisch ungünstigen Netzen einsetzbar sind. Der direkte Ansatz, bei dem sukzessive anhand der bedingten Verteilungen zufällig Belegungen erzeugt und mitgezählt werden lässt sich dabei verbessern, indem Schätzvariablen oder Markovketten eingesetzt werden, um schneller konvergierende Verfahren zu erhalten.